목차
*
여러가지 중간코드 중 3-addr Code로 바꾸는 걸 보자.
HIR code가 C코드 혹은 상위언어코드 혹은 AST 등으로 생각할 수 있고, 이걸 LIR 즉 3-addr 코드같은걸로 바꿀땐 nested 구조때문에 필연적으로 한 줄의 HIR 코드가 여러줄의 LIR 코드로 바뀐다.
이렇게 여러줄로 바뀔때 중간중간 임시변수를 정의하고 가져다 쓰는 형태로 바뀐다.
이때 여러줄로 바뀔 때 규칙이 있음.컴파일러가 하는 일. 그 방법에 대해 알아보자.
빨간글씨가 notation. 연산. 속에 들어가는 e는 하이레벨코드가 하나이상 섞여있는 코드.이게 [[ ]]를 만나면 LIR expression이 나온다.
t = [[e]]에서 e가 어떤 표현식. 마지막 결과값을 t에 저장하자. t가 임시변수.
t = [[v]]에서 일반적인 변수 v 값을 임시변수 t에 복사하자.
*
• Issues – HIR code 1줄 → LIR 코드 여러줄 • eg. nested structures : nested while, if.. • Algorithmic way – HIR Tree 의 각 노드마다 LIR로 변환하는 방법 정의 • Notation – [[e]] : HIR e 에 대한 LIR expression • 주로 sequence of LIR instruction 임 – t = [[e]] : e 가 표현식일 때, 결과값을 t에 저장 • t = [[v]] : 변수 v 의 값을 (임시변수) t에 copy
🌱 Arithmatic/Logic op
*
e1와 e2가 binary 연산으로 묶여있는거를 보자. [[ ]] 로 둘러싸서 LIR 3-addr 코드를 만든다. 그리고 이 결과 전체가 t에 저장된다.
변환 방법 : left child에 해당하는 e1을 모두 변환 후 t1에 저장. right child에 해당하는 e2를 모두 변환 후 t2에 저장. 두 임시변수에 저장된 값을 OP로 연결한 후 t에 저장. 마지막 줄 보면 오퍼레이터가 하나, address로 표현할 수 있는, 주소값이나 메모리 공간을 가지거나 레지스터인 거 3개. 3-addr 코드의 형태가 됨.
unary 오퍼레이터는 e1에 대한 결과값을 t1에 넣고 t1 앞에 OP라고 붙여주면 됨. 이게 가능한 이유는 binary 오퍼레이터와 unary 오퍼레이터는 3-addr코드나 상위 c언어 등이 다 가지고 있는 연산. 그래서 공동으로 쓰임. 위에서 말한것처럼 각괄호 안의 OP e1은 HIR. 근데 이제 왼쪽 변환 과정에서 t = OP t1은 3-addr 코드. 이때 쓰인 OP는 LIR. 즉 HIR과 LIR 둘 다 OP를 사용하고 있음.
*
🌱 Array Access
*
일반적으로 array는 HIR에 있고 LIR에는 없음. 그래서 이걸 어떤식으로 바꿀것이냐?
a[x+1]일때 x+1을 계산하고 a의 시작주소로부터 x+1칸만큼 떨어진 곳의 값을 가져온다. 이걸 3-addr 코드로 나타내야한다.
가장 먼저 시작주소를 나타낼 때 addr v라고 표현. v가 나타내는 address의 시작주소. 이게 t1에 들어가고,
x+1에 해당하는 부분이 적절히 3-addr 코드로 바뀌어서 t2에 들어감.
a의 시작주소로부터 x+1칸만큼 떨어진 곳의 값을 가져와야하는데, 이때 한 칸의 크기가 S, t2는 몇칸째에 있는지. 그래서 x+1만큼 떨어진 곳을 구할 때 t2 * S로 구함. 즉 시작주소부터 원하는 값이 있는 곳까지의 거리가 t3에 저장됨.
최종 위치를 구하면 시작주소 + 원하는값이 있는곳까지의 거리 = t1 + t3를 t4에 저장
마지막으로, [t4]로 t4위치의 값을 load.
요약하면 주소 계산해서 load하는거.
이때, c언어에서 a[2]에 접근해보자. a[0], a[1], a[2]까지, a가 int 배열이라면 한 칸의 사이즈가 int 크기의 사이즈. c언어에서는 이 크기를 보장해줌. 근데 c는 a라고 쓰면 이게 &a[0]라는 뜻인데, 3-addr코드에서 a라는 배열의 시작 주소는 addr a라고 씀.
*
🌱 Structure Access
*
어떤 변수 v가 있을때, v가 structure. v의 주소를 구한 다음 얼마나 가야하는지 계산하고 그 주소로 가서 load하면 끝.
v의 시작주소는 addr v로 구함.
f라는 offset이 시작위치로부터 얼마나 떨어져있는지와, 사이즈 S는 컴파일러가 타입같은거 보고 알아서 구해줌. 일반적으로 structure 안에 layout이 있고, a, f, i 등등의 field가 있는 형태. 이 전체가 하나의 객체 혹은 structural 데이터이고, a의 시작주소가 시작주소라고 한다면 f값을 얻기 위해 얼마나 가야하는지에 대해 미리 계산해둔게 S.
*
🌱 Short-cut OR
*
e1 SC-OR e2는 하이레벨 언어. c언어. 여기서 이제 OR, || 오퍼레이터를 보자. 만약 c에서 x > 0 || 어쩌구식 이라는 expression이 있다고 하자. 만약 x > 0이 참이면 어쩌구식과 관계없이 결과가 참이고, x > 0이 거짓이면 어쩌구식의 결과가 최종 결과가 된다. 이게 logic.
먼저 e1을 번역해서 t에 넣는다. 이후 t가 참인지 거짓인지 보는데, t가 참이면 결과가 참이므로 e2 번역은 하지 않고 Lend로 건너뛴다.
e1이 거짓이면, e2의 결과값이 최종 결과값이므로 e2의 번역 결과를 t에 덮어씌운다.
*
🌱 Short-cur AND
e1이 거짓이면 e2와 관계없이 최종 결과는 거짓.
e1이 참이면 e2의 결과가 최종 결과가 됨.
🌱 Statement Seq.
*
그냥 여러 문장이 있을 때. 각각에 대해 번역한다음에 계속 써주면 됨. 한가지 다른게 있는데, 위에는 t = [[~]] 형태, 즉 결과값이 중요한 형태였는데 이거는 t가 없음. 그래서 이럴땐 단순 연결하면 됨. 즉 결과가 있는 식은 expression이라고 부르고 이것처럼 결과가 없는 식은 statement라고 부른다.
*
🌱 Assignment
*
assignment중 첫번째로 그냥 expression을 assign하는 경우가 있음. OP처럼 assginment랑 변수 이름도 HIR이랑 LIR이 둘 다 사용함. 이때 HIR부분에서 e만, e에 별 코드들이 다 섞여있을 수 있으므로 얘만 [[e]]로 잘 LIR로 바꿔주면 됨.
두번째로 array assignment가 있음. 결국 주소를 가지고 있고 그 주소에 e2를 넣어주는거. addr v로 시작주소를 찾고, t2, t3 줄로 인덱스를 찾는다. 그리고 t4로 시작주소랑 더해서 셀의 주소를 구하고, 이다음에 일단 [[e2]]로 계산해서 t5에 저장하고, t4의 주소값에 t5를 그대로 넣어줌.
*
🌱 If
*
3-addr 코드로 if문을 바꾸는 방법.
이게 structual한 표현, 구조가 있는 표현.
먼저 if e then s를 보면 cjump를 이용. cjump는 조건부 점프.
먼저 [[e]]로 번역해서 t1에 넣고, t1에 neg를 취해서 반대로 바꾼 후 t2에 넣는다. t2가 참이면, 즉 t1이 거짓이면 Lend로 건너뛰어라. 만약 t2가 거짓이면, [[s]] 수행.
if then else도 비슷. 한가지 짚고 넘어가야할 점은, Lthen [[s1]] 실행 이후 가만히 두면 Lelse:까지 실행할것이므로, jump Lend를 꼭 넣어줘야함.
*
🌱 While
*
while문은 if문과 굉장히 유사.
t2가 참이면 Lend로 밖으로 빠져나간다.
*
🌱 Switch
*
if문의 나열과 같음.
먼저 [[e]]를 t로 넣은 후, v1과 t가 같지 않으면 다음으로 점프 하는 방식.
만약 같으면 [[s1]]를 수행하는데, 이후 스위치문의 break와 같이 jump Lend로 스위치문을 벗어나게 해야함.
그런데, 이렇게 변환될 수도 있지만 컴파일러에 따라 테이블 lookup으로 변환되는 경우도 있음. [[e]] 값이 무엇이냐에 따라 jump해야하는 타겟 주소를 해쉬값으로 담은 테이블을 만들고 사용하기도 함. 만약 아래 방식처럼 변환하는 경우, 후반까지 비교하는 경우 O(n)의 시간이 소요됨. 하지만 테이블을 사용하면 O(1)의 시간이 걸림.
하지만 테이블 내에 주소가 데이터로 들어있을 경우 security 측면에서 좋지 않기도 함. 또 테이블 내의 데이터 형태로 존재하게 되면 컴파일러가 최적화하는 방법을 찾기 어려워함. 키워드나 명령어로 존재하는것보다 컴파일러 입장의 가시성이 떨어져서 최적화가 잘 안될 수 있음. 그래서 두 방법 중 더 나은 방법은 없고 상황에 따라 다르게 사용.
*
🌱 Function Call/Return
*
모든 actual parameter들을 계산해서 t1~tN에 넣은 후 call할 때 넣어서 불러줌.
리턴할땐 리턴값을 계산해서 리턴.
이때 call, return이라는 LIR 명령이 다 있다는 가정하에 이렇게 변환할 수 있는거임. 만약 생각보다 더 로우레벨해서 call이나 return이라는 명령이 없다면, 변수 내에 들어있는 값을 다 끄집어내서 다른 함수인 f의 시작주소까지 가져다 주고, 제어도 넘겨줘야함.
*
🌱 Statement Expressions
*
*
• Statement 도 expression 처럼 값을 가지도록 확장해보자 – Block statements – If-then-else – Assignment statements • Notation – t = [[ s ]] :LIR code for statement s – a sequence of LIR instructions – 임시변수 t 에 해당 s 의 결과값이 저장
🌱 nested expression
