Опис документа

Рассмотрены вопросы эффективного построения формы статического единственного присваивания (Static Single Assignment (SSA)) программы, которая является одной из самых распространенных форм представления потока данных программы и активно используется в большинстве современных оптимизирующих компиляторов. Ключевым шагом в построении SSA-формы является нахождение мест размещения Ф-функции, в предположении, что задано множество узлов управляющего графа, которые содержат записи в некоторую переменную программы. Проблема нахождения мест размещения Ф-функции в свою очередь сводится к проблеме нахождения множества iterated dominance frontier для множества узлов управляющего графа, содержащих операции записи в переменную, для которой строится SSA- форма. При построении SSA-формы для программы эта процедура применяется ко всем переменным, участвующим в построении. В настоящий момент разработано много алгоритмов нахождения множества iterated dominance frontier для заданного множества узлов управляющего графа, на основе которых эффективно решается задача построения SSA-формы для отдельной переменной. В нашей работе сделан обзор известных алгоритмов нахождения множества iterated dominance frontier, имеющих наилучшую временную асимптотическую оценку, и предложена модификация этих алгоритмов, позволяющая существенно ускорить алгоритмы построения Ф-функций для множества переменных и, как следствие, ускорить построение SSA-формы для всей программы.