컴파일러는 어떻게 변수 이름을 변경합니까?

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'문자는 여러 항목을 한꺼번에 의미 할 수 있습니다. 사물을 추적하는 데 사용하는 방법은 위에서 설명한대로 변수 이름을 다시 정의하는 것입니다.

컴파일러의 작업 방법은 무엇입니까? 이 이름이 있나요?

변수를 재정의 할 때 변수를 재정의하는이 컴파일러 프로세스에 대해 최대한 알기 위해 노력하고 있습니다.

도움이된다면 컴파일 전 단계에서이 작업을 수행 할 수 있다고 생각합니다. 매크로 확장과 비슷한 개념이라고 생각합니다.

편집 : 질문에 조금 더 많은 내용을 추가했습니다.

Answer 1

직감이 정확합니다. 많은 현대 컴파일러는 흐름 분석을 사용하여 변수의 이름을 변경하여 각 변수가 고유하도록합니다. 결과 양식은 "단일 정적 지정" 또는 줄여서 SSA라고합니다.

입력 :

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

출력 :

입력 :

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

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

같은 나뭇 가지와 루프, 작업이 추가적인 부분이 있습니다

출력 :

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?>) 

일반적으로 IR은 SSA가 내장되어 있으며이 IR로 번역하는 동안 따라서 코드가 SSA로 전환됩니다 (또는 잠시 후). 매크로 확장은 매크로가 얼마나 강력한 지에 따라 그 이전에, 일반적으로 토큰 스트림이나 AST에서 발생합니다.

그러나 이것은 필수적인 것은 아닙니다. 일부 최적화에는 유용하지만 필수는 아닙니다 (일부 최적화는 전혀 이점이 없습니다). 변경 가능한 변수 (SSA를 특징으로하는 많은 컴파일러 IR이 적어도 SSA가 아닌 힙을 남겨 둡니다)를 사용하여 동일한 최적화 작업을 수행 할 수 있습니다. 예를 들어 상수를 전파 할 때 상수와 대체 할 용도 사이에 다른 지정이 없는지 확인해야하지만 SSA가 없으면 쉽게 확인할 수 있습니다.