Разработка компиляторов
На слайде приведен пример программы
На слайде приведен пример программы (слева) и ее представления в виде размеченного графа управления (справа). В качестве алфавита операторов выступает множество, состоящее из изображений элементарных операторов данной программы, то есть множество
{'g=a', 'm=b', 'a<b', 'm', 's=g', 'g=m', 'g=b', 'm=a', 'm=s%m'}
Далее мы рассмотрим несколько полезных вариантов определения множества операторов, применимых для формализации основных оптимизирующих преобразований.
На слайде приведен пример преобразования потока управления к форме, эквивалентной в описанном выше смысле (а именно, преобразование цикла с постусловием в цикл с предусловием). Пунктирными стрелками указаны образы вершин при отображении m .
Нетрудно заметить, что данное отображение необратимо, и, следовательно, определяемое им отношение несимметрично. Таким образом, введенное нами отношение, строго говоря, не является отношением эквивалентности. Это несоответствие может быть устранено, однако для наших целей этого не потребуется.
Рассмотрим представление программы, приведенной в разделе "Представление программы", с использованием def-use chains.
Здесь входы операторов обозначены с помощью кружков, расположенных слева он операторов, выходы - с помощью кружков, расположенных справа. Пунктирные стрелки ведут из выходов одних операторов к входам других и обозначают образы при отображении DU.
Построение данного представления опирается на решение одной из задач из области анализа потоков данных, а именно - задачи о достижимых определениях. Подробно данная задача рассмотрена в лекции 13.
Далее мы рассмотрим примеры оптимизирующих преобразований и те представления, которые необходимо использовать для их проведения.
На слайде приведен пример программы (слева) и ее представления в виде размеченного графа управления (справа). В качестве алфавита операторов выступает множество, состоящее из изображений элементарных операторов данной программы, то есть множество
{'g=a', 'm=b', 'a<b', 'm', 's=g', 'g=m', 'g=b', 'm=a', 'm=s%m'}
Далее мы рассмотрим несколько полезных вариантов определения множества операторов, применимых для формализации основных оптимизирующих преобразований.
На слайде приведен пример преобразования потока управления к форме, эквивалентной в описанном выше смысле (а именно, преобразование цикла с постусловием в цикл с предусловием). Пунктирными стрелками указаны образы вершин при отображении m .
Нетрудно заметить, что данное отображение необратимо, и, следовательно, определяемое им отношение несимметрично. Таким образом, введенное нами отношение, строго говоря, не является отношением эквивалентности. Это несоответствие может быть устранено, однако для наших целей этого не потребуется.
Рассмотрим представление программы, приведенной в разделе "Представление программы", с использованием def-use chains.
Здесь входы операторов обозначены с помощью кружков, расположенных слева он операторов, выходы - с помощью кружков, расположенных справа. Пунктирные стрелки ведут из выходов одних операторов к входам других и обозначают образы при отображении DU.
Построение данного представления опирается на решение одной из задач из области анализа потоков данных, а именно - задачи о достижимых определениях. Подробно данная задача рассмотрена в лекции 13.
Далее мы рассмотрим примеры оптимизирующих преобразований и те представления, которые необходимо использовать для их проведения.
