4 분 소요

이번 포스트에서는 컴파일러의 4번째 단계인 Intermediate Code Generator에 대해 다룬다.

Intermediate Code Generation

Intermediate Code Generator란?

Translates high-level intermediate representation into low-level intermediate representations

  • Semantic Analyzer 뒤, Code Optimizer 앞에 위치한다.
  • 소스 언어에 독립적, 타겟 머신에 독립적인 중간표현인 intermediate Representation, IR을 생성한다.

Intermediate Representation (IR)

  • 컴파일러 내부에서 사용하는 언어 중립적 표현
  • 주로 사용하는 IR
    • AST (Abstract Syntax Tree) : 구조적
    • Three-Address Code (TAC) : 명령어 나열형
      • TAC의 기본 형태 : x = y op z
      • 최대 3개의 주소 (operand)를 사용 가능하다.
      • 하나의 연산 = 하나의 명령어로 표현한다.
  • 여러 단계의 IR 사용 예

GCC 컴파일러의 실제 단계 : GENERIC(고수준 최적화), GIMPLE(중간 수준 최적화), RTL(저수준 최적화 및 코드 생성 단계)

왜 IR을 사용하는가?

1. 모듈화 (Modularity)

  • Frontend(언어별 분석기), Backend(기계 코드 생성기)를 분리가 가능하다.

2. Retargetability (Easy-to-translate)

  • 새로운 머신 코드로 쉽게 대응이 가능하다.

3. 최적화 용이 (Easy-to-optimize)

  • 고수준 소스보다 IR단계에서 최적화 알고리즘 적용이 더 쉽고 효과적이다.

핵심 : 소스 언어에 독립적, 타겟 언어에 독립적이다.

TAC

TAC = Three-Address Code

  • TAC의 기본형 : x = y op z
    • x, y, z : 변수명, 상수, 임시 변수 가능
    • op : 연산자

Instruction 구성 ( = Operations)

  1. Copy Operation
    • x = y
    • 좌변은 변수명 : 단순 복사
  2. Unary Operation
    • x = op y
    • 우변에는 반드시 한 개의 연산자
  3. Binary Operation
    • x = y op z
  4. Unconditional / Conditional Jump
    • goto L/ if x goto L
    • 논리연산 이후에 조건부 분기
  5. Indexing Pointer
    • x = y[i], x = &y
    • 배열 접근이나 포인터에 직접적인 접근이 가능
  6. Procedure calls and returns
    • 파라미터 전달, 함수 호출, 반환 값 전달
    • 간단하게 return 하여 값 반환도 가능
  • TAC는 명령어 + 피연산자 구조
    • 컴파일러 내부에서 TAC는 객체 또는 레코드 형태로 구현한다.
    • 보통 각 instruction을 하나의 데이터 구조로 표현한다.

Quadruple

  • 4항 구조
  • 각 TAC instruction은 다음 4개의 필드로 구성된다.
    • op (연산자), arg1 (첫 번째 피연산자), arg2 (두 번째 피연산자), result (결과를 저장할 대상)
  • 헷갈리는 표기법
    • L: : op: goto, result : L
    • if x goto L: op : if, arg1 : x ,result : L
    • x = call f, n: op:call, arg1 : f, arg2 : n, result : x
    • x = y[i]: op : =[], arg1 : y, arg2 : i, result : x

Quadruple 방식 : 모든 연산 결과를 임시 변수에 저장해야 한다. 이는 임시 변수가 많아 메모리 낭비를 발생시킨다.

  • 해결 아이디어 : Triple 구조 (AST to TAC 다음 설명)
    • result가 아닌 결과를 해당 instruction의 index로 참조한다.

AST to TAC

  1. 전제
    • AST의 각 노드는 어떤 연산 또는 값을 의미한다.
      • 연산자 노드
      • 값 노드

2. 트리 탐색 방식

  • DFS 방식으로 왼쪽 자식 -> 오른쪽 자식 -> 부모 순으로 방문한다.
    • 방문시에 각 서브트리에 대해 TAC 결과를 저장할 임시 변수를 만든다.
    • 부모 노드는 그 임시변수들을 이용하여 TAC instruction을 생성한다.
  1. DFS 순서 및 TAC 생성
    • DFS 를 통한 각 노드의 방문
    • 하위 노드에서 만들어진 임시 변수를 이용해 새로운 TAC 생성
    • 최종적으로 TAC 명령어들의 선형 리스트로 변환을 완료한다.

Triple

  • TAC의 구현 방법 중 하나이다. (3항)
  • op, arg1, arg2 총 3가지의 field를 가지고 있다.
  • result를 없애는 대신에 연산 결과를 instruction 번호 (index) 자체로 참조한다.
  • 장점
    • 메모리 효율성 : 인덱스 참조이기 때문
    • 구조가 간단하다.
    • 최적화에 유리하다.
  • 단점
    • 유지보수, 코드를 이동할 때 어렵다.
      • instruction의 순서를 변경시에 index 참조 관계도 업데이트를 해야 한다.

Indirect Triple

  • Triple의 Instruction 순서 변경 최적화에서의 문제 해결을 위한 구조
  • Triple 리스트에 직접 접근하는 것이 아닌, 별도의 포인터 테이블을 통한 간접 접근을 한다.
  • 장점
    • 코드 이동 시에 (Instruction의 순서가 변해도) Pointer Table은 그대로 유지가 가능하다.
    • 따라서 Index-based 참조가 깨지지 않는다. 이는 유지보수와 최적화에 유리하다.

Control Flow

Control Flow = 제어 흐름

  • Control Flow (조건문 : if-else, while, for 등)은 어떻게 TAC로 바꿀까?
  • 머신 레벨, TAC에서는 결국 Jump (분기)와 Label로 표현된다.

Flow-of-Control Statements 일반적인 패턴

1. if ( B ) S1

  • Boolean Expression이 True인지, False인지에 따라 분기
  • Attribute
    • code (S.code, B.code) : 실제로 해당 부분이 어떤 TAC instruction으로 번역되는지 나타내는 속성
    • true / false : 각각 label (레이블)을 나타낸다. TAC는 결국 Label + Goto 명령어로 분기 처리 된다.
      • B.Cdoe 내부에서 이 true/false 라벨이 (위치가) 결정된다.
    • next : S.next -> 해당 statement 이후로 실행이 이어질 위치를 나타낸다.

  • Semantic Rules

    B.true = newlabel()
B.false = S.next = S₁.next
S.code = B.code || label(B.true) || S₁.code || label(B.false)

Q1 ) S.code에서 || 는 OR이 아니다.

Semantic Rules 표기법에서는 “코드 나열 (Sequence of Code)”를 나타낸다.

Q2) How can we translate it into TAC?

Synthesized Attribute

  • 자식 노드로부터 계산된 결과를 부모 노드가 가져오는 것
  • Bottom - Up 방식
  • S.code를 계산하기 위해서는 B.code와 S1.code가 필요하다.
    • 따라서 B.code 먼저 계산하고, S1.code 계산후에 그 결과로 S.code를 만든다.

Inherited Attribute

  • 부모 노드가 자식 노드에게 속성을 전달하는 것
  • Top - Down 방식
  • 자식 노드에게 B가 true일때나 false 일때 어디로 가라고 하는지 미리 알려주는 것

2. if ( B ) S1 else S2

  • if-else 문으로 B.code가 True 이거나 False 일때를 다 고려하는 경우

  • Semantic rules

    B.true = newlabel()
B.false = newlabel()
S₁.next = S₂.next = S.next
  
S.code = 
    B.code
    label(B.true) S₁.code goto S.next
    label(B.false) S₂.code

3. while ( B ) S1

  • 구조적으로 반복하기 때문에 begin label이 필요하다. (루프의 시작 위치)

  • Semantic Rules

    B.true = newlabel()
B.false = S.next
S₁.next = begin
  
S.code = 
    label(begin) B.code
    label(B.true) S₁.code goto begin

Short-circuiting

  • 논리 연산자를 평가할 때 불필요한 평가를 건너뛰는 기법
  • 목적
    • 성능 최적화 : 불필요한 계산을 방지해준다.
    • 부작용 방지 : 평가 중에 부작용이 발생할 수 있으므로 안 해도 되면 스킵한다.
  • 예시)

A && B: A가 false이면 사실상 B를 계산하지 않아도 결과는 False이다.

Backpatching

  • Control Flow에서 Jump Target Label을 미리 알 수가 없다.
  • TAC 생성 시점에는 아직 모르기에 나중에 채워야 한다.

  • Jump Target을 비워둔 채로 TAC를 생성하여 나중에 label 위치가 결정되면 거기에 채워넣는 과정이다.

  • 과정
  1. Jump를 만들 때, 빈 label로 만들어서 목록에 기록한다.
  2. 코드가 더 생성될 때 나중에 label 위치가 결정된다.
  3. BackPatch를 수행한다.

태그:

카테고리:

업데이트:

참고

Concurrency, Locks

8 분 소요

이번 포스트는 OS의 Concurrency와 Locks에 대해 다룬다.