Advanced Compilers Reuse Optimization

Advanced Compilers Reuse Optimization

Reuse Optimization 

Idea

중복되는 것을 제거 하자.

How do redundancies arise ?

Types of reuse optimization

- vn(value numbering)

- cse(common subexpression elimination)

- pre (partial redundancy elimination)

Value Numbering

Determines that two computations are equivalent and eliminates one of them.

Local Value Numbering

Idea

각각의 변수 표현 상수는 unique number로 어사인 된다.

변수, 표현 상수 들이 어떤 숫자로 이미 지정되어져 있었다면,

그것들을 그 상수로 사용한다.

그렇지 않다면 그것을 새로운 숫자로 사용한다.

같은 number는 같은 변수이다.

Loca의 경우는 별다른 어려움 없이 된다.

Global Value Numbering

두가지 기법이 있다.

Pessimistic

어떤 변수도 일치하지 않는다로 가정 한다.

지속적을 일치하는 것을 합쳐 나간다.

Optimistic (Slower but better results)

확실히 다른것이 아니면 모두 같다고 생각한다.

Pessimistic Global Value Numbering

Limitations of Pessimistic Approach

Considers operands before variables that depend upon it

Can't deal with code containing loops !

-> Ignore back edges or make conservative (worst case) assumption for previously unseen variables

Loop 에서 결국 문제가 발생한다.

후방 edge에 대한 고려를 전혀 하지 않게 되는 현상이 발생 한다. 이것이 문제다.

Comparisons 

Constant propagation 또는 ( partial)  redundancy elimination은 두개의 expression이 동일하다면,그것이 constant인지 아닌지 결정 할 수 없다.

read a 이런게 있으면 불가능 하다.

Constant propagation은 b와 d가 7이라는 것을 알수 있다.

하지만 value numbering은 알 수 없다.