Compiler 7 - Optimization

 code optimizer(intermediate code optimizer)
이전 단계인 intermediate code generator의 결과(TAC 등)를 최적화하여 runtime performance, memory, power 등을 개선하는 과정. 단, 이 최적화 과정을 거친 코드 역시 original code의 semantic과 동일해야 한다. (일반적으로 이 부분은 optional 한 부분이므로 없어도 컴파일러는 작동 가능하다)

intermediate code는 최적화를 고려하지 않고 필요 없는 다수의 변수를 사용하는 경우가 많고, 프로그래머 역시 효율적이지 않은 코드를 작성하는 경우가 많다. 따라서 이런 비효율을 해결하기 위해 code optimization을 시행한다.

이 후에도 machine language를 가지고 알맞은 ISA에 대한 optimization을 할 수 있다. 그러나 이를 거친 machine code는 해당 기기에서만 실행될 수 있게 된다.




Basic Block
consecutive three address instruction의 maximal sequence. program은 basic block의 첫 instruction을 통해서만 해당 block에 들어갈 수 있다. 그리고 program은 last instruction을 수행하고 기다리거나 branch 하지 않고 해당 block을 떠난다. 이런 sequential한 특징을 가지는 것이 basic block이다.

Control flow graph
basic block의 흐름을 나타내는 그래프

이 둘을 가지고 local & global optimization을 수행할 수 있다. 만약 최적화가 single basic block 내부에서 일어나면 이를 local optimization이라 하고, 전체 control flow graph에서 일어날 경우 이를 global이라 한다.

Local optimizations
-common sub expressions elimination : 같은 연산값이 서로 다른 변수에 넣어질 경우, 연산을 재수행하지 않고 이전에 사용한 변수의 값을 가져오도록 변경. (단, 그 사이에 해당 값들이 변경되지 않음)

-copy propagation : 위와 같이 값이 바뀌지 않았다면, 변수 자리에 이전 값을 그대로 사용. (간단한 만큼 혼자 사용되어서는 효과가 크지 않음, 다만 이들은 컴파일 타임에 변환되므로 런타임 성능이 개선될 수 있다)

-dead code elimination : 어떤 변수에 assignment한 값이 한 번도 사용되지 않을 경우(그리고 미래에도 사용되지 않을 떼) 이는 쓸모 없는 변수이다. 따라서 해당 라인을 제거 한다. 이는 위와 합쳐질 경우 효과가 좋다. 예를 들어 copy propagation을 통해 사용하지 않는 변수가 발생하면, 그 라인을 지울 수 있다.

-arithmetic simplification : *2 연산을 <<1 연산으로 바꾸는 등 기존 연산자를 더 효율적인 연산으로 치환하는 것.

-constant folding : 만약 결과값이 상수가 되는 연산이라면, compile-time에 expression의 값을 계산하여 대입하는 것. (a = 10 * 2라면, a=20으로 교환)


Implementation of Local optimization
1. Available expression analysis : common sub expression elimination & copy propagation
어떤 expr의 variable이 up-to-date인 value를 가지고 있을 때, 이 expression은 available하다. 따라서 초기의 empty available set부터 시작하여 코드를 한 줄씩 읽으며 expression에 추가해 나간다. 만약 기존 변수에 새로운 값이 할당된다면, 이전의 할당 값은 unavailable이 되고, 새로운 값이 available이 된다. (해당 변수의 값을 가지고 있던 모든 expression이 unavailable하게 된다. 따라서 그 변수를 가질 수 있는 라인은 새로운 값을 할당한 바로 그 라인 뿐이다. )
주의할 점은 a=a+1과 같은 형식의 식은 RHS는 이전값, LHS은 최신값이 되므로 해당 라인이 실행한 직후라도 available set에 추가될 수 없다.

이를 통해 만약 available expression set에 있는 것과 동일한 식이 추가된다면, 이 값을 그대로 대체하여 common sub expression elimination을 수행할 수 있다.
마찬가지로 어떤 값이 set에 저장되어 있고 그 값이 다른 곳에서 다시 사용된다면, 이를 교체하여 copy propagation을 수행할 수 있다.
(available expression set의 RHS가 TAC에서 다시 출현할 경우, set의 LHS로 교체한다)

2. Live variable analysis : dead code elimination
미래에 사용될 값을 가지고 있는 variable을 live variable이라 한다. 만약 값의 새로운 할당이 일어나고, 그 뒤에 그 값이 사용된다면, 이전 값은 필요없게 되므로 새로운 할당 전까지는 live variable에 포함되지 않는다는 것을 주의해야 한다.

그러나 어떤 변수가 미래에 사용될 지 아닐 지 확인하기 위해서는 basic block의 statement들을 reverse order로 확인해야 한다. 마찬가지로 control flow graph에서도 하위 block부터 시작해 역순으로 확인하며 가장 초기 block에서 필요한 live variable을 확인할 수 있다. 따라서 이 경우, live variable set의 initial 값이 존재한다.

따라서 실제로 set을 얻을 때는 어떤 statement의 LHS를 제거하고, RHS를 추가하여 역순으로 가장 initial live variable set을 구할 수 있다.
그리고 이전과 반대로, a=a+1과 같을 때, 이전 값이 사용되어야 하므로 해당 식이 실행되기 전에 a는 live variable이다.

따라서 역순으로 block의 expression을 확인하며 올라갈 때 어떤 expression에 값이 할당된 후에, 그 expression이 live variable set에 포함되지 않는다면 제거하는 방식으로 dead code elimination을 수행할 수 있다. (지금까지 형성된 자신 하위의 live set을 확인해 자신이 있는지 없는지 확인. 없다면 추후로도 필요하지 않다는 의미이므로 제거. 왜냐하면 이 검사는 역순으로 올라가므로)

상기한 3개의 optimization을 제외한 나머지 arithmetic simplification이나 constant folding은 이런 복잡한 analysis가 필요하지 않고 어떤 rule을 설정하여 해당 조건에 부합하면 교체하는 식으로 실현 가능하다.

종합하면, local optimization은 normal 순서로 진행하여 1, 2를 수행하고, 역순으로 3번(live variable)을 수행하는 것으로 구현된다.

Global optimization
전체 control flow graph에 적용된다. 또한 local optimization technique 들을 전역에 적용할 수도 있다.

- code elimination
실제로 local live variable analysis를 하려면, 처음 주어진 live variable set을 구하기 위해 전역 block에서 해당 optimization을 수행해야 한다. 따라서 전체 코드의 마지막 block부터 dead code elimination을 역순으로 진행해가면, global live variable set을 구할 수 있고, 상위의 block들도 live variable set을 계산할 수 있다.

만약 control flow graph에서 어떤 block이 여러 개의 previous block을 가지고 있다면, 해당 block의 live variable set은 이전 블록들에게 모두 전달된다. 마찬가지로, 어떤 블록이 여러 개의 다음 블록으로 분기된다면, 해당 블록의 live variable set은 분기된 블록들의 live variable set의 합집합으로 계산한다.

그러나 만약 블록 간의 loop가 존재하는 control flow가 있다면, global live variable을 생각하기가 좀 더 어려워진다. 이 경우, 마지막 블록에서 동일하게 시작하고 global live variable set을 구한다. 단, 이 때 dead code elimination은 진행하지 않는다. 그리고 loop의 exit block의 live variable set과 initial block을 비교하여 exit block을 업데이트 한다. (initial과 exit를 union하여 exit의 live variable set을 업데이트) 그리고 더 이상 변하지 않을 때까지 이를 반복한다. (루프를 반복했을 때와 루프에서 빠져나왔을 때 를 모두 고려. 왜냐하면 loop의 마지막 블록은 해당 loop를 다시 진행할 경우, initial block으로 돌아갈 수 있기 때문) 그 다음, dead code elimination을 하면 된다.


- copy propagation & common subexpression elimination
앞서 local에서 해당 작업들을 했던 것 처럼, available expression analysis를 global scope에서 진행하면 된다. 앞서 했던 것과는 정반대로, initial block부터 시작하여 available set을 만들고 각 블록마다 순서대로 copy propagation/common subexpression elimination을 진행하면 된다.

앞서와 마찬가지로 분기가 있을 경우, 이전 값을 그대로 상속받게 된다. 그러나 여러 개가 하나의 block으로 합쳐지는 경우에는 앞서와 달리 union이 아니라 intersection이 다음 블록의 available set이 된다. (왜냐하면, 어느 분기를 선택하느냐에 따라 업데이트 되는 값이 다를 수 있기 때문에 최적화 결과가 올바르지 않을 수 있다. 따라서 모든 분기가 공통으로 공유하는 값, 업데이트된 값에 대해서만 최적화를 해야 한다. 따라서 여기서는 합집합이 아니라 교집합으로 고려한다.)

그리고 만약 loop 등의 복잡한 control이 있을 경우, 앞서와 global available set을 계산하고 optimization은 진행하지 않는다. 그리고 exit block과 entry block의 이전 block을 intersection 하여 entry block의 available set을 새로 구한다. 그리고 이 값이 더 이상 바뀌지 않을 때까지 반복한다. 이후 optimization을 진행하면 된다.

두 경우 모두 local에서 가능하던 최적화가 global scope에서는 불가능할 때가 많다. 그러나 적용하는 기본적인 원리는 동일하며 반대로, global scope에서만 가능하고 local에서는 불가능한 최적화도 있다. (code motion : code의 위치를 다른 블록으로 옮기는 것 등)