Алгоритмы восстановления формы ssaa после модификации графа потока вызовов

Question

Я изучаю оптимизацию компилятора в форме ssa. Одна трудность, с которой я сталкиваюсь, заключается в том, как сохранить/восстановить/восстановить форму ssa после изменения структуры графа потока вызовов.

Предположим, у меня есть следующий cfg (переменные a, b, c являются фиктивными, не обращайте на них внимания):

Теперь я хочу вставить узел, который предшествует узлу while, чтобы результат был таким:

Как видно, новый узел меняет границы доминирования для x_1 и x_2 и требует, чтобы phi-узел для блока while был «разделен» на два.

Какими алгоритмами это можно сделать? Я просмотрел книги и слайды, но не нашел ничего, что объясняло бы, как это сделать эффективно.

Answer 1

Я, вероятно, опаздываю на вечеринку, но в книге Inria Forge SSA есть глава «Реконструкция SSA» ( зеркало ), в которой говорится об этой теме.