Правильно ли мое построение SSA? (Переименование)

Я узнал о ssa (статическая форма одиночного назначения), и мне дали следующий график со вставленными фи-функциями, но график не был переименован:

Данный граф ssa

Мне пришлось переименовать переменные, и вот что у меня получилось:

График ssa, который я конвертировал

Я очень не уверен, что это правильно. Я правильно переименовал переменные? Это минимальная сса? Я использую этот алгоритм из здесь (Cytron и др.), чтобы переименовать переменные. Пожалуйста помоги! :)


graph compiler-construction compiler-optimization ssa control-flow-graph
person xilpex    schedule 19.07.2020    source источник
comment
Я не понимаю график, который вам дали. Почему метка L1 находится в середине базового блока? Означает ли это, что goto L1 прыгнет в середину блока (пропустив фи-узлы)? И каковы значения t1 и т. д. при выходе из начального блока (который не дает им никакого значения)?   -  person sepp2k    schedule 28.07.2020
comment
@sepp2k -- Спасибо, что обратили внимание :) -- Нет, это не имеет никакого значения... Они просто помогают мне.   -  person xilpex    schedule 28.07.2020
comment
Извините, но я не совсем уверен, как воспринять ваш ответ. Что не имеет никакого значения? Мне кажется, что перепрыгивает ли goto L1 фи-узлы или нет и каковы начальные значения от t1 до t3, довольно важно. Например, строка t1_0 <- phi(t1_0, t1_1) имеет неправильный формат, потому что t1_0 не определена в блоке перед циклом, но я не могу сказать вам, какой будет правильная версия, потому что я даже не понимаю, что t1 <- phi(t1, t1) должен был делать в первом место.   -  person sepp2k    schedule 28.07.2020
comment
@ sepp2k - я имел в виду переходы и метки (goto L1 и метка L1).   -  person xilpex    schedule 28.07.2020
comment
Кроме того, t1_0 <- phi(t1_0, t1_1) неверно?   -  person xilpex    schedule 28.07.2020

Ответы (1)


arrow_upward
1
arrow_downward

Нет, ваш график неверен. Фи-функции и переименование для x и y правильные, проблема во временных переменных с t1 по t3. Эти переменные мертвы при входе в блок L1 и вообще не требуют фи-функций. Если вы настаиваете на фи-функциях для этих переменных, вы должны предположить, что переменные существуют и имеют какое-то неопределенное значение при входе в график. Пусть t1_0, t2_0 и t3_0 будут этими значениями и соответствующим образом обновят переименованный график.

person Johan    schedule 04.08.2020
comment
Хорошо, спасибо... Еще одна вещь: я построил сокращенный ssa, и функция phi для y исчезла (вероятно, потому что она не использовалась в блоке L1). Я понял это правильно? - person xilpex; 04.08.2020
comment
@xilpex Вам нужна фи-функция для y в L1, поскольку эта переменная имеет разные определения в зависимости от того, через какое входящее ребро вы входите. - person Johan; 05.08.2020
comment
Ах, да, но если бы y не использовалось в блоке L2, функция phi не потребовалась бы, верно? - person xilpex; 05.08.2020
comment
Это необходимо в любом случае, так как y не мертво при входе в L1 (оно используется при вычислении t2) и имеет разные определения в зависимости от того, как вы достигаете L1. Фи-функции используются для объединения входящего потока. - person Johan; 05.08.2020