Актуальность применения подхода SSA
Как уже было упомянуто, один из этапов компиляции – синтаксический анализ. Реализующий модуль, получая на вход список токенов, в качестве выхода строит синтаксическое дерево. Такое дерево, помимо прочего, обладает определенными особенностями, среди которых были выделены преимущества и недостатки.
Преимущества:
Синтаксическое дерево легко строится напрямую из списка токенов (или даже текста программы, если лексический анализ совместить с построением дерева) за один проход фактически без дополнительных структур данных.
Синтаксическое дерево является представлением входной программы один-в-один (текст программы может быть восстановлен путем полного обхода дерева), поэтому удобно предоставлять диагностику пользователю (указание точного места в исходном коде).
Недостатки:
Процесс семантического анализа дерева нетривиален. Требуется задействовать дополнительные структуры данных для упорядочения информации (список переменных, функций) и т. д.
Применение существенных трансформаций (оптимизаций) является трудоемким: для обнаружения и проверки инвариантов требуется выполнять обходы по несколько раз (анализ использования переменных, вывод типов, поиск определений), что верно и для замены узлов дерева.
Для разрешения описанных трудностей, связанных, в частности, с анализом потока данных для выполнения трансформаций, было предложено использовать подход, похожий на SSA.
SSA (static single assignment, статическое единственное присвоение) – это представление программы, в котором у каждой переменной есть единственное определение, сопровождающееся инициализацией. Следующие примеры псевдокода демонстрируют одну и ту же программу, записанную в произвольной форме и в форме SSA.
x = 1
y = x + 1
x = 2
z = x + 1
x1 = 1
y = x1 + 1
x2 = 2
z = x2 + 1
Используя свойство единственности присваивания, можно отследить, как было получено то или иное значение, обойдя цепочку определений и использований переменных.
В классическом подходе SSA, используемом в современных компиляторах, все высокоуровневые конструкции языка, такие как ветвления и циклы, разбиваются на последовательность базовых блоков программы, между которыми явно указываются переходы. Кроме того, вводится понятие ϕ-узлов, связывающих пути, по которым приходит определение переменной из разных блоков при нелинейном исполнении .
В настоящей работе была реализована структура данных, использующая подход SSA в упрощенной форме, достаточной для достижения поставленных целей. Эта структура, названная деревом операций, описана далее.