Алгоритм распространения констант, использующий GSA-представление
Алгоритм распространения констант, описанный в [8] использует SSA-представление (Static Single Assignment) программы. В SSA-форму программа трансформируется таким образом, что только одно присваивание может достигнуть точки использования. Так как программы имеют ветвления и точки объединения нескольких путей, то в точках объединения необходимо добавить специальную форму присваивания, названную ?-функцией. ?-функция имеет форму V ← φ(R, S, …), где V, R, S, … – переменные. Количество операндов такой функции равняется количеству предшественников данного узла. Эти предшественники перечисляются в некотором определенном порядке и j-й операнд ?-функции ассоциируется с j?м предшественником узла. Если путь выполнения программы лежит через j?го предка узла, то переменная V получает значение, связанное с j?м аргументом. Каждое исполнение ?-функции использует только один из аргументов, но который именно – зависит от того, из которого узла получил управление данный узел.
В работе [8] алгоритмы распространения констант разделены на те, которые находят простые и условные константы. Алгоритм Sparse Conditional Constant Propagation находит все простые, а также некоторые условные константы. Время работы такого алгоритма пропорционально размеру SSA-графа и каждое SSA-ребро обрабатывается максимум два раза.
Когда необходимо классифицировать переменную в точке слияния, мы используем функцию meet для аргументов ее ?-функции. Но если в процессе своего выполнения программа всегда идет только по одной ветке было бы лучше использовать то значение переменной, которое порождается именно в ней. В методе, описанном в предыдущем разделе, если значение предиката будет постоянным, то выполняемое ребро будет добавлено к рабочему списку. Поэтому в точке слияния выражения будут вычисляться с использованием информации о входящих выполняемых ребрах, что может приводить к неоднократному вычислению одних и тех же выражений.
В методе, использующем GSA, если символ использует значение из точки слияния, то вычисляется значение предиката и определяется путь из которого берется значение.
При использовании φ- функции мы не можем определить по какому пути шло выполнение программы. Но если снабдить φ-функцию предикатом, то, если его значение является константой, можно выбрать нужный аргумент φ-функции, а если нет, то самое лучшее, что можно получить с помощью данного метода – это взять функцию meet от φ-аргументов.
Чтобы выполнить данную задачу необходимо расширить SSA-представление до GSA (gated single assignment), введенное в работе [3], которое позволяет вычислять условные выражения, базирующие на предикатах. В данном представлении ?-функции заменяются на μ- и ?-функции. Большая часть φ-функций, расположенных в заголовках циклов переименовываются в μ-функции, тогда как остальные – преобразуются в ?-функции. ?-функция имеет вид: v = ?(P, v1, v2), что означает, что v принимает значение v1, если P=true и v2, если P=false. В такой форме ?-функция представляет собой конструкцию if-then-else, но она может быть расширена для работы с более сложными условными конструкциями. Алгоритм для преобразования φ-функций в μ- и ?-функции представлен в работе [6].
В данном алгоритме используется представление программы в виде базовых блоков, состоящих из кортежей. Базовые блоки и кортежи внутри них связаны между собой и вместе образуют граф потока данных. Кортежи имеют следующие атрибуты: op, left, right, ssa_link, lattice, где op – код операции, left и right – два операнда. ssa_link – связь, порождаемая алгоритмом преобразования программы в SSA-форму. Поля left, right, ssa_link представляют собой указатели на соответствующие кортежи. Каждая операция (кортеж) также имеет ассоциированное значение – lattice, принадлежащее множеству значений из решетки и представляющее собой результат выполнения операции, который может быть получен на этапе компиляции.
