OptimizeCompile

Basic of Compiler Optimization

Topology

현재 프로세서의 속도는 무어의 법칙에 따라 극한으로 속도가 증가하고 있다. 이러한 상황에서는 예전처럼 CPU 의 속도 에 프로그램의 실행속도가 크게 영향 받지는 않으므로, 컴파일러의 최적화 작업도 더이상 연산(computation)을 줄이는 것 만이 목적이 되는 것이 아니라, 좀 더 메모리 계층구조를 효율적으로 사용하는 것에 관심이 기울여지게 된다.

Local optimization 과 Global optimization.

프로그램(translation unit)은 진행방향이 분기에 의해 변하지 않는 부분의 집합인 basic block 들로 나눌 수 있는데 이 각각의 block 에 대하여 최적화 하는 것을 local optimization 이라 하고, 둘 이상의 block 에 대하여, 혹은 프로그램 전체를 총괄하는 부분에 대하여 최적화 하는 것을 global optimization 이라고 한다.

모든 최적화 작업은 시간 효율에 대하여, 혹은 공간 효율에 대하여 최적화를 하게 되는데, 밑의 각 섹션에 따라 분리 할 수 있다. 이 작업들은 서로 상호 보완적으로 이루어지거나 혹은 상호 배제적으로 이루어 질 수 있다. (e.g. latency 를 줄일 경우 코드 길이가 길어지거나 복잡도가 증가할 수 있다.)

Reduction of computation

실행 시간(run time) 중의 계산을 줄이는 것이 목적이다. 이 최적화는 '미리 컴파일 시간에 계산(precomputaion in compile time)' 할 수 있거나, '미리 계산된 값을 재사용(reuse a previously computated value)' 할 수 있는 상황에서 적용된다.

Constant propagation

변수가 값을 할당 받아서, 다시 새로운 값으로 할당 받기 전까지, 그 변수는 일종의 constant 라고 볼 수 있다. 컴파일러는 이를 감지해서 최적화를 수행하게 된다.

PI = 3.14159;
...
area = 2 * PI * radius;

위와 같은 부분에서, PI 의 값이 중간에 변경되지 않는다면, 위의 코드는

PI = 3.14159;
...
area = 2 * 3.14159 * radius;

와 같이 바뀔 수 있다.

Constant folding

연산에서 두개 이상의 constant 들은, 미리 계산되어 하나의 constant 값으로 바꿀 수 있다. 위의 예에 적용하자면

PI = 3.14159;
...
area = 6.28318 * radius;

가 된다.

컴파일러는 constant propagation 과 constant folding 을 반복하여 수행한다. 각각 서로의 가능성을 만들어 줄 수 있으므로, 더이상 진행 할 수 없을 때까지 진행한다.

Copy propagation

Common subexpression elimination

a = x + y;
b = x + y;
temp = x + y;

a = temp;

b = temp;

Partial redundancy analysis

Removing loop invariant code

Reduction of space consumption

Reduction of code size

Reduction of complexity

Strength reduction

컴퓨터가 할 수 있는 연산 들은 각각 그 연산이 수행되는데 걸리는 시간의 차이가 있다. 연산에 복잡도에 의해서 이루어지는 현상인데, 극단적인 예를 들자면, shift 연산은 보통 2 클럭에 처리되는 반면에, 나누기 연산의 경우 80-90 클럭을 소모하게 된다.(i8088자료) 이런 연산에 대한 computation time 의 차이를 줄이는 최적화 방법을 strength reduction 이라고 한다.

x = y / 6

와 같은 문장이 있을때, 나누기 연산은 곱하기 연산보다 좀더 많은 시간을 소요하므로 컴파일러는

x = y * (1 / 6)

으로 바꿀 수 있다.

배열의 참조 연산 또한 좋은 예가 될 수 있다. a[i] 와 같은 표현식에서 a[i]의 주소는 배열 a 의 시작주소로부터 a의 타입 크기 * i 만큼 떨어진 곳이 된다.

double a[ARRSIZE], b[ARRSIZE];
for (i = 0; i < ARRSIZE; i++)
    a[i] = b[i];

와 같은 코드에서 a[i] 의 주소는 루프가 진행됨에 따라 계속 evaluate 된다. 그럼 a + (i * 8) 이 매번 반복되게 된다. 이러한 연산은 단순히 루프가 진행되며 a 의 주소에 8 씩을 더해주는 것으로 해결될 수 있다.

Algebraic simplification

수학적으로 같은 값을 가지는 수로 대치하는 것이 바로 algebraic simplification 이다.

e.g.

Expression	Equivalent expression
x + 0	x
x * 0	0
x * 1	x
x^2	x * x
x * 2	x + x
x / 1	x

Reduction of latency

cpu architecture 차원에서 지원한다.

e.g. instruction prefetching, branch prediction, out-of-order execution

Distribution of work

역시.. cpu 차원에서...

e.g. pipelining, superscalar

More advanced mothodology of compiler optimization

coming soon.