Compiler 개요2

Program Analysis Technique

Compiler는 프로그램을 블럭 그리고 라인 단위로 노드를 구성하여 관리하게 된다. 각각의 노드는 트리 혹은 DAG(Direct Acyclic Graph) 등으로 표현이 될 수 있을 것이다.
* DAG는 두 개 이상의 parent를 가질 수 있는 트리 구조를 가리킨다.

그리고 이러한 자료 구조를 가지고 분석을 하게 되는데 중간 산출물로 변수의 선언과 사용을 표현한 DU(Def-Use) 그리고 사용과 선언을 표현한 UD(Use-Def) Chain이 있으며 궁극적으로는 Web을 그려내게 된다. Web에서는 Data의 Flow를 분석한 결과를 보여주며 독립적으로 분리될 수 있는 변수를 굳이 하나로 관리하지 않는다.(설령 개발자가 그렇게 코딩을 하였어도 다시 재구성하게 되는 것이다.) 예를 들면

 

a=b; // (1)
c=a;
a=d; // (2)

 

위의 경우 (1)에서 굳이 (2)의 a를 (1)의 a와 동일한 변수로 표기할 필요는 없다는 것을 알 수 있다.

 

a=b;
c=a;
e=d; // (3)

 

즉, (3)과 같이 e를 사용하여도 전혀 문제가 없는 것이다. 따라서 가능하면 이렇게 블럭 혹은 라인 간의 독립성을 높혀서 표현하게 된다. 이는 이후 Code Optimization 과정을 용이하게 하며 또한 변수간의 Dependency분석에도 도움이 된다. (즉, false dependence를 제외한 true dependence만을 쉽게 추려낼 수 있게 된다.)

 

Code Optimization
- Dead-code elimination : 프로그램 결과 즉, 목적에 영향을 주지 못하는 로직을 삭제하는 것이다. 예를 들면 변수 a를 전혀 사용하고자 하는 로직이 없는데 변수 a에 복잡한 연산의 결과를 넣는 로직이 있다면 이는 제거되야할 것이다.
- Common Subｅxpression Elimination(CSE) : 반복되는 로직을 하나의 변수로 표현하는 것이다. 그러나 CSE의 단점은 변수의 수명이 길어져서 향후 전체 메모리 사용량이 증가할 수 있다는 것이다. 때문에 경우에 따라서는 반대 방향으로 변환이 적용되기도 한다.
- Loop Invariant Motion : 예를 들면 Loop 안에 있으면서 반복적으로 연산을 수행하지만 사실 매번 같은 로직으로 같은 결과만을 산출한다면 Loop 밖으로 빼는 것이 효과적일 것이다.
- Constant Propagation : 변수의 값이 고정불변한 상수값일 경우에 아예 상수로 치환하는 것이다. 만일 개발자가 const라는 키워드로 변수를 선언한다면 컴파일러는 용이하게 작업할 수 있을 것이다.
- Copy Propagation : x:=y 와 같은 로직에서 이후 x==y가 계속해서 참일 경우에 하나의 변수만을 남겨놓고 다른 하나는 제거하는 방법이다.

위의 기법들은 블럭 내부/외부에서 적용할 수 있다. 블럭 내부에서만 적용하고자 할 때에는 상대적으로 쉬운데 이렇게 사용하는 방법이 Peephoe Optimization이다. 부가적으로 아래의 기법들이 있다.
- Tail Merging : 굳이 jump 등의 분기가 필요없이 바로 다음 라인으로 항시 건너갈 때 jump등의 구문을 삭제하는 밥업이다.
- Loop Elimination : Loop 가 필요없는데 사용될 경우 제거하는 기법이다.
- Loop Inversion : while 로직을 do...while로직으로 바꾸는 기법이다. while문은 while문 그리고 while블럭 마지막에서 각각 두번의 분기 구문이 필요한데 do...while은 한번만 필요하기에 조금 더 효과적일 수 있다.