7. Basic Blocks and Traces

IR Tree의 문제점

CJUMP의 경우 원래는 true와 faluse에 따라서 다른 label로 이동을 해야하지만 실제는 false인 경우 그냥 다음 instruction을 실행한다.

 

ESEQ, CALL의 경우 동작을 하면서 side effect가 발생할 수 있어 동작의 예측을 하기 힘들다.

그리고 이러한 특성 때문에 계산하는 순서에 따라서 결과가 다르게 나오는 문제가 생긴다.

 

Canonicalization

canonical tree는 SEQ와 ESEQ를 없애고, 각각의 CALL의 parent는 EXP이거나 MOVE이어야한다.

 

canonicalization은 다음과 같은 방법으로 수행이 된다.1. ESEQ를 제거하도록 tree를 수정한다.2. CALL이 있으면 CALL의 parent가 EXP나 MOVE가 되도록 tree의 위로 옮겨준다.3. SEQ를 다 없애고 나열한다.

 

예를들어 아래와 같은 tree가 있으면 각각의 연산이 실행되는 순서를 지켜서 ESEQ를 위로 올리면

BINOP(op, ESEQ(s, e1), e2)

ESEQ(s, BINOP(op, e1, e2))

위와 같이 바꿀 수 있다.

 

그런데 아래와 같이 e1이 먼저 실행이 되어야하는 경우는 ESEQ를 먼저 실행할 경우 side effect에 의해서 e1의 실행 결과가 변경될 수 있기 때문에 TEMP로 값을 먼저 저장을 하고 뒤의 연산을 할 수 있게 해야한다.

BINOP(op, e1, ESEQ(s, e2))

 

즉,  다음과 같이 하면 된다.

ESEQ(MOVE(TEMP t, e1), ESEQ(s, BINOP(op, TEMP t, e2)))

ESEQ lift예시

다만 ESEQ에서의 s가 e1에 영향을 안준다면 다음과 같이도 바꿀 수 있다.

ESEQ(s,BINOP(op, e1, e2))

 

s가 e1과 무관한 경우

Basic Block

하나의 entry와 exit point를 가지는 assembly instruction이다.

여기서 entry는 label name으로 들어올 수 있는 부분이고 exit point는 jump로 나갈 수 있는 수단이다.

이러한 측면 때문에 basic block은 순서를 바꾸더라도 상관없이 동작한다.

 

Trace

실제 프로그램을 실행시킬 때 연속적으로 싱행되는 부분으로 이러한 특성 때문에 trace에서는 jump가 필수가 아니다.

 

covering set of trace

trace를 만들어서 전체 프로그램을 커버하는 trace의 집합이다.

이는 jump의 수를 최소화 하여 실행의 효율성을 높인다.

그리고 trace의 수도 최소화 하여 관리와 최적화를 용이하게 한다.