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

Алгоритм распространения констант, использующий GSA-представление


Алгоритм распространения констант, описанный в [8] использует SSA-представление (Static Single Assignment) программы. В SSA-форму программа трансформируется таким образом, что только одно присваивание может достигнуть точки использования. Так как программы имеют ветвления и точки объединения нескольких путей, то в точках объединения необходимо добавить специальную форму присваивания, названную ?-функцией. ?-функция имеет форму V &#8592 &#966(R, S, …), где V, R, S, … – переменные. Количество операндов такой функции равняется количеству предшественников данного узла. Эти предшественники перечисляются в некотором определенном порядке и j-й операнд ?-функции ассоциируется с j?м предшественником узла. Если путь выполнения программы лежит через j?го предка узла, то переменная V получает значение, связанное с j?м аргументом. Каждое исполнение ?-функции использует только один из аргументов, но который именно – зависит от того, из которого узла получил управление данный узел.

В работе [8] алгоритмы распространения констант разделены на те, которые находят простые и условные константы. Алгоритм Sparse Conditional Constant Propagation находит все простые, а также некоторые условные константы. Время работы такого алгоритма пропорционально размеру SSA-графа и каждое SSA-ребро обрабатывается максимум два раза.

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

В методе, использующем GSA, если символ использует значение из точки слияния, то вычисляется значение предиката и определяется путь из которого берется значение.
При использовании &#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, принадлежащее множеству значений из решетки и представляющее собой результат выполнения операции, который может быть получен на этапе компиляции.


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