Разработка компиляторов

       

Представление программы


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

Граф потока управления - это ориентированный граф, в котором выделены две вершины start и stop, и удовлетворяющий следующим требованиям:

  • В start не входит ни одна дуга.
  • Из stop не выходит ни одна дуга.
  • Любая вершина достижима из start .
  • Из любой вершины достижима вершина stop .

Введем далее в рассмотрение некоторое конечное множество, которое мы будем называть алфавитом операторов ? и назовем разметкой графа потока управления произвольное отображение ? множества вершин графа в множество операторов.

Пара (G, ?), где G - граф потока управления, а ? - его разметка, и является представлением программы для оптимизации. От дополнительных свойств элементов множества операторов зависит характер оптимизаций, которые можно выразить, используя данное представление.

Заметим, что построение такого представления программы уже включает в себя широко известное оптимизирующее преобразование - удаление недостижимого кода, то есть той части программы, на которую никогда не передается управление.



Содержание раздела