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



         

Решение задачи анализа потоков данных (2)


Введем в рассмотрение полурешетку, представляющую собой декартову степень 2|V| исходной полурешетки L и введем в рассмотрение функцию F на ней. Данная функция принимает на вход элемент <before1, after1, ..., before|V|, after|V|> и возвращает элемент, полученный применением функций, построенных на предыдущем шаге, к соответствующим аргументам. Иными словами, если, например, для вершины 10 графа потока управления предшественниками являются вершины 2 и 3, то двадцатым элементом возвращаемого F значения будет g10,2(after2, after3) .

Легко видеть, что функция F является монотонной. Кроме того, можно показать, что ее произвольная неподвижная точка является решением системы уравнений (*), поскольку произвольный элемент решетки L2ґ|V|определяет пару разметок before , after .

Наконец, итерирование функции F, начиная с наименьшего элемента, дает в конце концов наименьшую неподвижную точку и, следовательно, искомое решение задачи анализа потоков данных.




Содержание  Назад  Вперед