Разработка компиляторов
Чистка циклов вверх
увеличить изображение
Данное преобразование применяется к сильно связным подграфам графа управления (т.е. подграфам, состоящим из взаимно достижимых вершин). Таким образом, для его проведения необходима фрагментация программы на уровне сильно связных подграфов. Алгоритм выделения сильно связных подграфов будет рассмотрен в лекции 12.
Если такой подграф выделен, то для него определяется множество входных вершин, то есть таких его вершин, в которые существует путь из вершины start, лежащий целиком за пределами этого подграфа. На иллюстрации входные вершины подграфа S обозначены темными кружками и символами e1, …, ek .
Чистка цикла вверх заключается в том, что вершина, лежащая в сильно связном подграфе, заменяется на несколько копий вне его, каждая из которых непосредственно предшествует входным вершинам. Такое преобразование возможно только в случае, когда оператор, которым помечена данная вершина, использует только данные операторов, недостижимых изнутри выбранного сильно связного подграфа.
Легко видеть, что данное преобразование также повторно по отношению к самому себе.
