Какая программа будет иметь ромбовидный интерференционный граф, упомянутый в BRIGGS94?

Я читаю Briggs94 Улучшения в размещении регистров раскраски графиков.

Просто интересно, в какой программе будет ромбовидный интерференционный график? То есть для четырех диапазонов действия w, x, y, z: w мешает x, x мешает z, z мешает y, а y мешает w. И других помех больше нет.

Поскольку и w, и z мешают x и y, на шкале времени должна быть дыра между живым диапазоном x и y. И w, и z пересекут эту дыру, что приведет к противоречию w с z, противоречие.

(Вот ссылка на документ: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.253&rep=rep1&type=pdf)


compiler-construction compiler-optimization register-allocation
person sillyfd    schedule 02.08.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Петля вроде

loop:        // live range w     x     y     z  
  x:=y+z;    //                start  end    |
  w:=z+x;    //          start   |          end 
  y:=x+w;    //            |    end  start  
  z:=w+y;    //           end          |   start
  goto loop; //                        |     |

генерирует такой интерференционный граф.

person FPK    schedule 03.08.2013
comment
Хорошая конструкция. Я пропустил сценарий петель. - person sillyfd; 05.08.2013