Алгоритмы, структуры данных


         

функции мы не можем определить


При использовании &#966- функции мы не можем определить по какому пути шло выполнение программы. Но если снабдить &#966-функцию предикатом, то, если его значение является константой, можно выбрать нужный аргумент &#966-функции, а если нет, то самое лучшее, что можно получить с помощью данного метода – это взять функцию meet от &#966-аргументов.

Чтобы выполнить данную задачу необходимо расширить SSA-представление до GSA (gated single assignment), введенное в работе [3], которое позволяет вычислять условные выражения, базирующие на предикатах. В данном представлении ?-функции заменяются на &#956- и ?-функции. Большая часть &#966-функций, расположенных в заголовках циклов переименовываются в &#956-функции, тогда как остальные – преобразуются в ?-функции. ?-функция имеет вид: v = ?(P, v1, v2), что означает, что v принимает значение v1, если P=true и v2, если P=false. В такой форме ?-функция представляет собой конструкцию if-then-else, но она может быть расширена для работы с более сложными условными конструкциями. Алгоритм для преобразования &#966-функций в &#956- и ?-функции представлен в работе [6].

В данном алгоритме используется представление программы в виде базовых блоков, состоящих из кортежей. Базовые блоки и кортежи внутри них связаны между собой и вместе образуют граф потока данных. Кортежи имеют следующие атрибуты: op, left, right, ssa_link, lattice, где op – код операции, left и right – два операнда. ssa_link – связь, порождаемая алгоритмом преобразования программы в SSA-форму. Поля left, right, ssa_link представляют собой указатели на соответствующие кортежи. Каждая операция (кортеж) также имеет ассоциированное значение – lattice, принадлежащее множеству значений из решетки и представляющее собой результат выполнения операции, который может быть получен на этапе компиляции.


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