Лекция 06. Машинно-независимая оптимизация (1157464), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Если другиеоптимизации убрали из этих блоков все инструкции,то второе из основных преобразований могло породитьлевый граф, показанный на рисунке).406.5. Оптимизация потока управления6.5.2. Основные преобразования. Преобразование 2. 2.Удалить пустой блок: Если блок Bi содержиттолько инструкцию перехода, то он поглощаетсясвоим последователем – блоком Bj.BiBjBjТакая ситуация возникает, когдапредшествующие оптимизации удаляют всеинструкции из блока Bi.Так как у Bi всего один последователь, Bj,преобразование перенаправляет дуги, входящиев Bi, к Bj и исключает Bi из Pred(Bj), что упрощаетГПУ и ускоряет выполнение.416.5.

Оптимизация потока управления6.5.2. Основные преобразования. Преобразование 3. 3.Объединение блоков: Если имеется блок Bi, которыйоканчивается переходом на Bj, у которого всего одинпредшественник, Bi, он может объединить эти блоки какпоказано на рисунке внизу, что позволяет исключитьпереход из Bi в Bj.BiBj426.5.

Оптимизация потока управления6.5.2. Основные преобразования. Преобразование 4. 4.Подъём ветвлений. В ситуации, когда блок Bi, которыйоканчивается переходом в пустой блок Bj, а блок Bjоканчивается ветвлением, переход в конце блоказаменяется на копию ветвления из блока Bj. Такоепреобразование поднимает ветвление из Bj в Bi.Ситуация может возникнуть, если другие оптимизацииудалят все операции из Bj, оставив только ветвление.К ГПУ добавится ребро. Объединить Bi и Bj нельзя, таккак у Bj есть еще предшественники (если бы их не было,Bi и Bj уже были бы объединены Преобразованием 3).BiBjBiBj436.5.

Оптимизация потока управления6.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 */446.5. Оптимизация потока управления6.5.3. Функция Clean()Функция Clean()многократно вызывает функцииPostorder()(обычная нумерация блоков) и OnePass()(однократный проход), выполняя последовательностьпреобразований 1 – 4 итеративно до тех пор, пока ГПУоптимизируемой процедуры продолжает изменяться.В начале каждой итерации выполняется новая нумерация блоков,так как после каждого применения четверки преобразований ГПУможет сильно измениться.Функция Clean()не может самостоятельно удалить пустойцикл (цикл с пустым телом).

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

ПримерОднако если исходный ГПУ предварительно обработать спомощью Mark & Sweep, рассматриваемый пустой цикл удастсяудалить.Блоки B1 и B3 содержат полезные инструкции, а блок B2 нет,проход Mark решит, что ветвление в конце B2 бесполезно,так как B2  RDF(B3).Если ветвление бесполезно, бесполезен и код, вычисляющийусловие ветвления. Поэтому Sweep удалит из B2 все инструкциии преобразует ветвление в конце B2 в переход на ближайшийполезный постдоминатор B3. Получится ГПУ на правом рисунке.B1B2B1B2B3B3Исходный ГПУГПУ после Mark & Sweep476.5. Оптимизация потока управления6.5.4. ПримерClean загоняет B2 в B1, в результате получается ГПУ,изображенный на третьем рисунке слева.Теперь ветвление в конце B1 становится избыточным, и Cleanзаменяет его переходом, в результате получается ГПУ,изображенный на четвертом рисунке слева.Наконец, если окажется, что B1 – единственный предшественникB3, Clean объединит эти два блока в один блок.B1B2B1B1B1B2B3B3B3B3Исходный ГПУГПУ послеMark & SweepГПУ послеудаления B2.ГПУ послесворачиванияизбыточнойветви.48.

Характеристики

Список файлов лекций