Как компилятор изменяет имена переменных?

Question

Я занимаюсь некоторыми исследованиями в этой теме и не нашел хороших конкретных ответов. Скажем, у вас есть эти выражения в коде:

B = 2 
… 
B = B + 5 
… 
B = J + B 
… 

(Это очень простые примеры, я знаю, что они не являются реалистичными)

B имеет много различных значений на протяжении этих строк. В первой строке это 2, позже он становится 7, а более поздним - 7 + J. Компилятор должен будет отслеживать эти разные значения для B, поэтому одним из способов является их переименование. Например, когда B переопределено как B = B+5, его можно изменить на B1 = B+5. Последнее переопределение тогда будет выглядеть как B2 = J+B1.

Мотивация этой идеи связана с оптимизирующей программой, которую я создаю. Это связано с заменой переменных выражениями, с которыми они связаны. Однако, если переменная переопределена, символ «B» может означать сразу несколько вещей. Метод, который я использую для отслеживания вещей, - это то, что я описал выше, переопределение имен переменных.

Это вообще не то, как работает компилятор? Есть ли имя для этого?

Я пытаюсь как можно больше узнать об этом процессе компилятора, переопределяющего переменные в случае переопределения переменных.

Если это помогает, я считаю, что это будет сделано на этапе предварительной обработки компиляции, и я считаю, что это аналогичная концепция для макроразложения.

EDIT: Я добавил немного больше контекста к вопросу.

Answer 1

Ваша догадка правильная, многие современные компиляторы используют анализ потока для переименования переменных, чтобы каждая переменная была уникальной. Полученная форма называется «одиночное статическое присвоение» или SSA для краткости.

Входной сигнал:

B = 2 
B = B + 5 
B = J + B 

Выход:

B1 = 2 
B2 = B1 + 5 
B3 = J + B2 

Есть дополнительные части к этому для работы с ветвей и петель, таких как:

Входной сигнал:

if X < 5 
    B = Y + Z 
else 
    B = 2 
B = B + 1 

Выход:

if X < 5: 
    B1 = Y + Z 
else 
    B2 = 2 
B3 = phi(B1, B2) 
B4 = B3 + 1 

Функция «phi» выбирает, какой из ее входов находится в живом режиме.

Это НЕ выполняется во время предварительной обработки, это делается после того, как код скомпилирован для некоторого IR, обычно состоящего из базовых блоков. Это НЕ похоже на макрорасширение.

Answer 2

Опишите, что вы описали, как форма статического одиночного присвоения (SSA).Это немного более агрессивны, чем «переименовывать переменные при назначении», потому что вы также должны знать «текущий» переменную для чтения из в условиях потока управления, например, если вы переписать так:

if (a) x = 0; 
else x = 1; 
print(x); 

в этом, вы должны вставить так называемый фи узел, чтобы выбрать правильное значение в print:

if (a) x0 = 0; 
else x1 = 1; 
print(<which x?>) 

как правило, ИК имеет SSA встроенный в систему и, таким образом, код включается в ССА, а переводится в ИК (или вскоре после этого). Расширение макроса происходит задолго до этого, как правило, в потоке токенов или в AST в зависимости от того, насколько мощны ваши макросы.

Обратите внимание, что это никоим образом не является обязательным. Это полезно для некоторых оптимизаций, но не требуется (и некоторые оптимизации вообще не приносят пользы). Вы можете выполнять те же оптимизации, что и с изменяемыми переменными (и многие IR-компиляторы с SSA оставляют по крайней мере кучу как не SSA), это просто менее удобно и, возможно, дороже. Например, при распространении констант вы должны убедиться, что между константой и используемой вами заменой нет других назначений, но вы можете легко проверить ее без SSA.