Code optimization

Intermediate code는 optimization을 고려하지 않음

=> 수많은 useless variable 생성

 

물론 machine  code로 바꿀 때도 최적화를 해야하지만, 너무 딥하기 때문에

intermediate를 최적화 하는 것을 중점적으로 본다.

 

Basic block

=> maximal sequnece of consecutive three address instruction 

그냥 대충 뭐 scope 정도로 생각하면 될듯..?

 

Control flow graphs

 

 

Type of intermediate code optimizations

local optimization 일 때 ( 하나의 block 내에서 optimize 할 때)

=> CONSTANT는 합쳐준다

t0 = 10 + 100
y = t0
==>
y = 110

 

global optimization 일 때

=> 전체 control flow를 고려 

 

 

Local optimizations

1) Common sub expressions elimination

v0 = a op b
... // 이 사이에 v0, a, b가 바뀌지 않는다면  
v1 = a op b // v1 = v0으로 최적화

 

2) Copy propagation

v0 = v1
// v0와 v1이 reassigned 되지 않는다면
a = v0 // a = v1으로 사용

 

3) Dead code elimination

v0 = v1
// v0와 v1이 reassigned 되지 않는다면
a = v0 // a = v1으로 사용

// v0가 이후에 더이상 사용되지 않는다면 지움
// copy propagation 과 자주 연동이 된다.

 

4) Arithmetic simplification

x = a * 2 // x = a << 1
x = a / 2 // x = a >> 1
// 곱셈, 나눗셈 연산보다 shift 연산이 훨씬 빠르다

 

5) Constant folding

x = 10 * 2 
// 그냥 x = 20 이렇게 해라

 

예시를 한 번 보자.

t0 = a * a
t1 = a * a
t2 = t0 + t1
t3 = t0 + t0
t4 = t3 + 1

 

이 코드를 optimize 해보자

t0 = a * a
t1 = a * a => copy propagation,  t1 = t0 => Dead code elimination
t2 = t0 + t1 => t2 = t0 + t0 => Arithmatic simplication => t2 = t0 << 1
t3 = t0 + t0 => copy propagation, t3 = t2 => Dead code elimination
t4 = t3 + 1 => t4 = t2 + 1

==>

t0 = a * a
t2 = t0 << 1
t4 = t2 +1

 

=> 이 방식은, optimize 되기 전 코드와 semantically 하게 equivalent 함을 보장한다. 

 

 

그렇다면, 이 optimization techniques를 어떻게 구현할까?

 

Available expression analysis 

처음에는 어떤 expression도 available 하지 않다.

어떤 statement가 check 되면, 해당 expression을 available 하다고 한다.

그러나, a = operation이 또 나오면, 전의 available expression은 사라지고, 새로 할당 된 expression으로 업데이트 된다.

 

 

Using Common subexpressions elimination

 

위의 예시를 들어보면, {t0 = a*a} 가 available 한 상황에서, t1 = a*a가 check 됐다. 

=> 두 RHS가 같기 때문에, 현재 statement의 RHS를, available한 expression의 LHS 로 바꾸어준다.

 

 

Using Copy propagation

아래의 예시를 보자

 

{b = a} 가 available 한 상황에서 , t1 = a*b가 check 됐다.

available expression의 LHS (b) 가 현재 statement의 RHS에 포함되어 있기 때문에,

해당 RHS 부분을, available expression의 RHS (a)로 바꾸어준다.

 

 

전체 적용 예시를 보자

 

 

Live variable analysis

live variable은,  미래에 사용 되는 variable을 hold 해놓은 것이다.

=> 미래에 사용되는지 알기 위해, live variable 은 reverse order로 간다(맨 끝에서부터 체크)

(global의 경우, 다음 block에서 사용 될 live variable의 set을 알고 있게 되는 것)

 

==> 이전 단계(더 미래에 쓰이는 것, reverse order라고 했다)의 live variable과  현재 TAC 를 보고, 다음 live variable set을 예측할 수 있음

미래의 live variable이 {b, d}

1) {b, d}는 더 미래에 쓰이는거니까, 과거의 live variable에도 {b, d}가 있다고 예측할 수 있음

2) 사이의 TAC의 LHS는, 이 단계에서 할당이 된 것이므로, 더 과거의 live variable에 존재할 수 x => 지움

(재 할당인 경우에도 할당 된 값이 바뀌는거라 마찬가지임)

3) 사이의 TAC의 RHS는, 지금 사용이 된 것이므로, 과거의 live variable에 존재해야함 => 추가

==> {b,d} - {a} + {a,c} = {a,b,c,d} 

 

 

Using Dead code elimination

현재 코드를 보자.

t1 =  a * a 가 실행 되고 난 후 live variable에 t1이 존재하지 않는다.

=> 이후에 t1이 사용되지 않는다는 의미 ==> Dead code를 의미한다.

 

==> Dead code elimination

 

전체 예시를 보자

live variable을 구한 후, 해당 코드의 LHS가 다음 live variable에 포함되지 않는다면, 

해당 코드는 미래에 쓰이지 않는 것이기 때문에 Dead code로 간주하고 제거한다.

 

 

Global optimization

local 에 적용했던 technique를 그대로 control flow를 보며 적용 가능

 

Dead code elimination

 

걍 local이랑 똑같이 하면 된다.

**  주의점 => Dead code elimination은 local 내에서 생기면 바로바로 쳐내준다.

                => 합쳐질 때는, 합집합으로 쓴다.

 

이건 간단한 예시였고, loop 문을 global하게 보면 좀 복잡해진다.

일단 loop 는 global 하게 하려면 loop 밖에서 시작해야 한다.

 

 

아까와 다르게 local 내에서 dead code가 생겨도 지우지 않고 살려둔다.

loop를 다 돌고, loop 처음의 live variable을 구했으면, loop 끝 부분의 live variable을 update 해준다.

(loop를 다시 돌지, loop를 빠져나갈 지 알 수 없기 때문에)

 

이후에 더이상 바뀌는게 없을 때까지 반복해준다.

반복이 끝나면 그 때 전체적인 dead code elimination을 진행한다.

 

 

Copy propagation / Common subexpressions elimination

이것도 local이랑 비슷하게 진행해주되, 주의 사항이 있다.

=> b = 1 + b 처럼, RHS에 자기 자신이 포함되어 있으면, available이 될 수 없다. 

=> b = b +1 로 새로 할당 된 것이고, 딱 이 시점에서만 예전 b + 현재 b를 다 쓰는건데

=> 이걸 available에 넣어버리면 뒤의 코드들은 현재 b의 영향만 받으므로 안됨

& 합칠 때는 교집합만 가져온다.

 

이것도 loop문을 가져와 보자.

global dead code elimination과 마찬가지로, loop 밖에서 먼저 설정을 해준다.

이후 진행을 하면서 local optimization 없이 그냥 진행을 하다가, loop 의 끝과 loop의 시작을 다시 비교

=> 교집합이 있으면 해당 교집합을 차용하지만 이 예시에선 교집합이 없어서 empty set이 된다.

=> 다시  변경사항이 없을 때까지 반복

=> 정해진 available expression으로  optimization을 진행한다.

 

---------------------------------------------

 

끝

 

누가 수업 끝이래

 

어떤  optimization은 local에서는 안되고, global일 때만 되는 경우도 있다

==> ex) code motion :  moving code from one basic block into another to avoid unnecessary computations

// 쓸데없는 계산을 피하기 위해 여기로 옮긴다
L0:
    t0 = y+z  //이 부분은 루프 내에서 계속 반복 될 필요가 없으므로
    t1 = x <to
    if not t1 goto L1
    x = x+1
    goto L0
L1: