[컴개/CI] IR Translation to 3-addr code

HIR to LIR

HIR는 상위 언어, 혹은 AST 등으로 생각할 수 있는데, 이러한 HIR을 LIR 즉, 3-addr code와 같은 형태로 바꿀 때 nested 구조(while, if, etc)로 인해 필연적으로 한 줄의 HIR코드는 여러 줄의 LIR 코드로 바뀐다.

 

여러 줄로 바뀌는 과정에서 임시 변수를 정의하고 임시 변수를 가져다 쓰는 형태로 바뀐다. 이때, 여러 줄로 바뀌는 규칙이 존재한다.

 

Notation

[[ e ]]

HIR e에 대한 LIR expression.

즉, e는 하이레벨 코드가 하나 이상 섞인 HIR이며, [[]]에 들어가게 되면 LIR expr로 나오게 된다. 주로 sequence of LIR instruction이다.

 

t = [[ e ]]

e가 표현식일 때, 결과 값을 t에 저장한다.

즉, e는 어떠한 표현식이고, 마지막 결과값을 t에 저장하는데, 이때 t는 임시변수이다.

 

t = [[ v ]]

일반적인 변수값 v를 임시변수 t에 복사한다.

 

3-주소 Translation 규칙: Arithmatic/Logic op

 

e1과 e2가 바이너리 연산으로 묶인 경우다.

명령어를 [[ ]]로 싸서 3-addr code로 만들고, 이를 임시변수 t에 저장한다.

 

변환하는 방법은, left child인 e1을 변환하여 t1에 저장하고,

right child인 e2를 변환하여 t2에 저장한 후 두 임시변수 t1, t2를 OP로 연결한 후 t에 저장한다.

 

위 예제에서 임시변수 t를 확인하면 t, t1, t2 모두 주소값을 가지고 있는 형태로 3-addr code가 된다.

 

 

unary 오퍼레이터는 e1에 [[]]을 취한 결과값을 t1에 넣고, e1 앞에 OP를 붙여준다.

 

이렇게 표기하는 것이 가능한 이유는 binary 오퍼레이터나, unary 오퍼레이터는 3-addr code와 c 언어 등 모두가 가지고 있는 연산이다. 따라서 공동으로 사용된다.

 

이때, [[ ]] 안의 OP와 임시 변수 t에 할당된 OP는 같은 의미를 가진 서로 다른 OP이다.

[[ ]] 안의 OP는 HIR에서의 OP이고, 임시 변수 t에 할당된 OP는 LIR에서의 OP이다.

즉, HIR과 LIR은 모두 OP를 사용한다.

 

3-주소 Translation 규칙: Array Access

 

일반적으로 배열(array)과 같은 구조는 HIR에만 존재하고, LIR에는 존재하지 않는다.

이때 LIR에서 array를 표현하는 방식은 아래와 같다.

 

a[x+1]이라는 값을 찾고 싶을 때, 가장 먼저 x+1에 대한 연산을 한다.

이후, a의 시작주소로부터 x+1만큼 떨어진 곳의 값을 가져온다.

 

시작 주소를 나타낼 때 addr v로 나타내는데, v의 시작 주소가 t1의 값으로 들어간다.

이후 [[ ]]을 통해 e의 값을 LIR로 표현한 후 t2에 넣는다.

v의 시작 주소로부터 t2만큼 떨어진 곳의 값을 가져와야 하는데, array의 한 칸 크기를 S라고 한 후 시작 주소로부터 t2 * S만큼 떨어진 값을 가져와야 한다.

 

이후, 시작주소로부터 떨어진 거리를 구했으면 t4에 v의 시작 주소인 t1과 떨어진 거리인 t3을 더한 값을 넣어준다. 마지막으로 [t4]를 통해 t4 위치의 값을 읽어(load)준다.

 

c는 배열에 대해 접근할 때, 만약 접근하는 배열이 int형이라면 a[1]일 때 한 칸의 사이즈가 int의 사이즈이다. 이때, c에서는 한 칸의 크기가 int의 크기라고 보장해준다.

 

또한 c에서 &a[0]의 값은 a와 동일하지만, 다른 언어에서는 array의 주소가 c와 같지 않으므로 3-addr code에서는 배열의 시작 주소를 로드할 때 addr v를 사용한다.

 

3-주소 Translation 규칙: Structure Access

 

어떤 변수 v가 있을때, v가 structure라고 하자. v의 주소를 구한 다음 해당 필드 값을 가져오기 위해 얼마나 가야하는지를 계산하고 그 주소로 가서 load하면 된다.

v의 시작주소는 array와 마찬가지로 addr v로 구한다.

f라는 offset이 시작 위치로부터 얼마나 떨어져 있는지와, 사이즈 S는 컴파일러가 타입 등을 보고 알아서 계산한다.

 

일반적으로 structure는 안에 layout이 있고, a, f, i 등의 field가 있는 형태이다.

이 전체가 하나의 객체 혹은 structural 데이터이고, a의 시작주소가 구조체의 시작주소라고 한다면 f값을 얻기 위해 얼마나 가야 하는지에 대해 미리 계산해 둔 값이 S이다.

 

3-주소 Translation 규칙: Short-cut OR

 

High-level 언어에서 OR 연산에 대한 LIR을 나타내는 것이다.

이때, 'e1 || e2'에 대해 e1이 참이면 e2를 계산할 필요 없이 결과가 참이 된다.

하지만 e2이 거짓이라면 결과값은 e2에 의해 결정된다.

 

따라서 [[e1]]의 값을 t에 넣는데, cjump를 통해 t의 값이 참이라면 Lend로 점프한다.

t가 거짓이라면 분기하지 않고 [[e2]]를 계산하여 t에 대입하는데,

앞서 [[e1]]이 거짓이라면 결과값은 [[e2]]에 의해 결정되므로 t는 [[e2]]의 결과값을 덮어쓰게 된다.

 

'e1 || e2'의 경우 [[e1]]이 참이라면 [[e2]]는 계산되지 않는다.

즉, "True || getchar() != '\n'"의 경우라면 getchar()는 실행되지 않는다.

따라서 이러한 계산에 따른 side effect가 없도록 코드를 구성해야 한다.