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


         

Алгоритм распространения констант, использующий 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, если символ использует значение из точки слияния, то вычисляется значение предиката и определяется путь из которого берется значение.

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