Тема 05(2016)Машинно-независимая оптимизация (Лекции), страница 3

Объединить Bi и Bj нельзя, таккак у Bj есть еще предшественники (если бы их не было,Bi и Bj уже были бы объединены Преобразованием 3).BiBjBiBj505.5. Оптимизация потока управления5.5.3. Функция Clean()Clean()while ГПУ продолжает изменятьсяcomputePostorderOnePass()OnePass()for each block Bi|| in postorderif (Bi оканчивается ветвлением)if (обе цели одинаковы)заменить ветвление на переходif (Bi оканчивается переходом на Bj)if (Bi пуст)заменить все переходы на Bi переходами на Bjif (Bj имеет только одного предшественника)совместить Bi и Bjif (Bj пуст и оканчивается ветвлением)заменить Bi переходна копию ветвления из Bj/* 1 *//* 2 *//* 3 *//* 4 */515.5.

Оптимизация потока управления5.5.3. Функция Clean()Функция Clean()многократно вызывает функцииPostorder()(обычная нумерация блоков) и OnePass()(однократный проход), выполняя последовательностьпреобразований 1 – 4 итеративно до тех пор, пока ГПУоптимизируемой процедуры продолжает изменяться.В начале каждой итерации выполняется новая нумерация блоков,так как после каждого применения четверки преобразований ГПУможет сильно измениться.Функция Clean()не может самостоятельно удалить пустойцикл (цикл с пустым телом).

Это показывает следующий пример.525.5. Оптимизация потока управления5.5.4. ПримерРассмотрим процедуру, ГПУ которой изображен на рисунке.Пусть блок B2 пуст.Ни одно из преобразований функции Clean() не может удалитьблок B2 :ветвление в конце B2 не избыточно;B2 не завершается переходом, и Clean() не можетобъединить его с B3;предшественник B2 блок B1 оканчивается ветвлением,а не переходом, и Clean() не может ни объединить егос B1, ни свернуть его ветвление в B1.B1B2B3Исходный ГПУ535.5. Оптимизация потока управления5.5.4. ПримерОднако если исходный ГПУ предварительно обработать спомощью Mark & Sweep, рассматриваемый пустой цикл удастсяудалить.Блоки B1 и B3 содержат полезные инструкции, а блок B2 нет,проход Mark решит, что ветвление в конце B2 бесполезно,так как B2  RDF(B3).Если ветвление бесполезно, бесполезен и код, вычисляющийусловие ветвления.

Поэтому Sweep удалит из B2 все инструкциии преобразует ветвление в конце B2 в переход на ближайшийполезный постдоминатор B3. Получится ГПУ на правом рисунке.B1B2B1B2B3B3Исходный ГПУГПУ после Mark & Sweep545.5. Оптимизация потока управления5.5.4. ПримерClean загоняет B2 в B1, в результате получается ГПУ,изображенный на третьем рисунке слева.Теперь ветвление в конце B1 становится избыточным, и Cleanзаменяет его переходом, в результате получается ГПУ,изображенный на четвертом рисунке слева.Наконец, если окажется, что B1 – единственный предшественникB3, Clean объединит эти два блока в один блок.B1B2B1B1B1B2B3B3B3B3Исходный ГПУГПУ послеMark & SweepГПУ послеудаления B2.ГПУ послесворачиванияизбыточнойветви.55.