Donghee

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
Intermediate Representations

==== 5.1 Introduction ====
'''IR소개'''

소스 코드를 분석하고 타겟코드로 전달 하기 위한 중간 코드로 IR을 사용한다.
보통 1개 이상의 IR을 사용한다. 
컴파일러의 각 패스사이에서 유용한 정보를 기록할 수 있어야 한다.
패스 전달 동안 필요한 정보(예를 들면 변수의 주소와 프로시져 등의 추가적인 정보)도 IR 이다.
----
IR의 디자인 알고리즘에서 문제가 online, offline 에 따라 구분된다. 보통의 컴파일러는 offline으로 작업을 한다. (offline:코드를 전달하기위한 하나의 패스 이상을 만들수 있는 상황)

컴파일러는 여러 패스를 지나는 동안 코드의 품질을 향상시킨다. 컴파일러는 이전의 패스동안 다음패스를 만들기 위한 정보를 모은다.

IR 디자인을 선택할때 컴파일러가 source language와 타겟머신의 정보에(또는 변환될 소스) 대해서도 잘 알아야 가능하다. 
컴파일러는 변환되면서 사용하는 내부 폼(internal form)은 변환되는(source또는 어셈블리)form에 점점 가까워 진다.

그외 specific IR 정보 : 기록하고 분석하고 조작할때 필요하다.
 C에서는 포인터, 자바에서는 herarchy 같은

IR을 실제 구현측면에서 고려할 사항
 IR은 효율적이어야 한다.(저렴한 연산을 사용하도록)
 컴파일 동안 발생할수 있는 모든 구조를 표현할 수 있어야 한다.
 컴파일러 쓰는 사람이 쉽고 직접적으로 접근할 수 있어야 한다.
 필요에 따라 가독성을 향상시키기위해서 추가정보도 쓰인다.(clean readble externl format을 제공하는것도 중요)

==== 5.2 Taxonomy ====

첫번째 분류 
 IR의 조직측면

'''Graphical IRs'''
 컴파일하기위한 정보를 그래프(nodes, edges, lists, trees)로 인코딩
 derivaton 표현에 사용되는 parse tree는  graphical IR이다.

'''Linear IRs'''
 추상머신을 위한 pesudocode와 비슷, 알고리즘은 연산의 단순하고 선형적인 반복이다.
 ILOC code가 linear IR 형식이다.

'''Hybrid IRs'''
 위의 장점을 섞음
 straingt-line code의 블록 자체 을 표현할때는 linear IR을 사용
 블록들 간의 콘트롤플로우 표현할때는 graph사용

----
IR의 구조는 컴파일러 작성자가 분석하고 최적화하고 코드제어레이션 하는데 많은 영향을 준다.

----
두번째 분류
 추상화 측면

'''source-level tree(high-level 표현)'''
near-source representation : procedure call은 single node에 의해 표현

Example
refence A(i,j)를 2가지 측면에서 표현해보자
A는 2차원으로 이루어 졌고, 각 차원당 10개의  element를 가지고 있다.
컴파일러가 array refenece를 쉽게 인식할 수 있다.
컴파일러가 두개의 다른 refences가 같은 메모리를 가르키고 있을때 high-level로 표현하는것이 더 가치 있다.

high-level의 추상화가 tree-based IRs(3장의parse tree의 노드를 함축적으로 표현) 성질을 반영 하는것은 아니다. 

'''low-level represiontation''' : IR의 연산자는 타겟머신의 operation 형태의 조합으로 표현
 ILOC (low-level code)
 low-level code에서 분명한 사실을 찾을 수 있다.
 컴파일러가 두개의 다른 refences가 같은 메모리를 가르키고 있을때 low-level 표현은 힘들다.
 low-level 표현은 최적화(여러곳 에서 사용되는 같은 operation을 옮기거나 제거하는일을 한다.)하는데 유리하다.
 low-level expression tree는 계산의 상세한 부분을 표현하는데 많이 이용된다.(예를 들면 A[i,j]의 address calculation 같은)

Example
address calculation 생성을 위한 경우 lower-level은 명시적으로 표현하기 때문에
 lower level of abstracon 이 더 효과적임

----
IR의 표현 능력 을 고려하자 (표현능력 : 컴파일러가 필요한 모든 정보와 procedure 선언, static 분석의 결과, 이전수행의 profile 디버깅하는데 필요한 정보)

----
==== 5.3 Graphical IRs ====
많은 IR들이 표현하는 코드는 그래프로 전달된다.
모든 graphical IR들은 노드와 엣지로 구성되어 있다. IR간의 차이는 그래프와 소스 프로그램의 관계, 그래프의 구조 에 따라 달라진다.

5.3.1 Syntax-Related Trees

'''Parse tree'''
parse tree는 소스코드 derivation, parse을 하기위한 그래프표현이다. 

컴파일러는 parse tree의 각 노드와 엣지에 메모리를 할당. 각 노드와 엣지를 돌아 댕기며 작업한다. -> 노드와 엣지를 줄일 필요가 있음

parse tree는 parsing 과 attribute grammar system 에서 주요하게 쓰이고 그외 source-level tree에서 쓰인다.
----
'''Abstract Syntax Trees(AST)'''
AST는 parse tree의 주요구조(식의 의미 와 연산자우선순위 )를 보존하고 그외 부분은 제거 한다. 

Source-to source 컴파일 시스템(컴파일러 타겟이 다른 프로그래밍 언어), language-based editor, 인터프리터, prettypring, automatic parallelization,  S식 구현할때도 유용하게 사용

Example
AST의 복소수표현
 AST for Editing ( ,가 Pair가 된다.)
 AST for Compiling (각 chind 노드를 string으로 만들어 포인터로 가리킴) -> 단순화함

AST는 source-level 표현에 많은 컴파일러가 사용함, 
마지막 AST 아래에는 보통 instrucion set 이 위치한다.

----
'''Directed Acyclic Graphs'''

DAG 
 AST의 중복 부분을 숨겨서 AST보다 더 간편함
 변수의 값이 변하지 않으면(도중에 assignment 나 procedure call로 변하지 않는것을 증명) 중복 부분 생략 가능하다.

작은 메모리를 사용하는 시스템에서 컴파일할 때 DAG를 사용하여 효과를 본다.

----
'''Level of Abstraction'''

코드의 low-level의 자세한 표현을 하는데 사용.

예 w <- x- 2 * y
source-level로 표현할때 assembly code전달을 위해서 필요한 정보들이 없다. low-level tree는 좀더 자세하고 명확하다.

low-level tree에 대한 설명
 각 타입과 value, 주소에 대해서 새로운 노드를 만들어서 표현함

----
5.3.2 Graphs

프로그램의 요소를 표현하는데 앞에서 처럼 tree 형태로만 표현하는것은 모자르다. 컴파일로는 이를 위해 IR을 표현할때 graph를 사용하기도 한다. 
DAG는 graphical IR의 한 형태(?)
----
'''Control-Flow Graph'''

CFG는 프로그램의 콘트롤의 흐름을 모델한다.

CFG는 방향성 graph 이다. 그래프의 각 노드는 basic block 이고 basic block은 같이 수행 할 수 있는 operaion의 나열이다. edge는 한블록에서 다른 블록의 콘트롤의 전달을 나타낸다.

8장 9장에서 CFG의 단순화에 대해서 이야기 한다.

CFG는 unique한 entry node n0 과 exit node nf 를 가지는데, n0은 procedure의 entry point와 관련된다. 여러개의 entry point가 있으면 n0을 삽입하고 n0으로부터의 edges를 삽입하여 여러개의 entry point를 가도록 한다. 비슷하게 nf도 procedure 의 exint point와 관련된다. 

CFG는 run-time control-flow path의 graphical 표현을 제공한다. 

5.2에서 loop 와 simple conditional의 CFG표현
AST에서 cycle을 추가하여 표현

CFG는 보통 다른 IR의 표현과 합쳐서 쓰인다.(hybrid IR) CFG는 각 블록의 관계를 표현하고 그 블록안은 다른 IR(expression-level AST, DAG, linear three-address code)로 표현된다.

CFG구현의 tradeoff
 코드를 얼마나 블록으로 표현할까? 이러한 블록은 보통 Single-statement blocks과 basic block들로  나눈다. 

single-statement block는 basic block를 사용하여 좀더 큰 CFG를 생성한다.
single-statement block은 최적화(optimization 과 code-ganeration 에 과련된 정보들이 노드나 에지로 만들어져서 CFG에 붙는다)
 
basic block은 single statement CFG보다 적은 node와 edge를 사용한다. 이러한 모델에서 각 블럭의 시작하고 끝나는 point를 찾는것은 사소한 일이다. 
좀더 추가

컴파일러에서 다른 여러가지 activities는 control-flow graph에 연관이 된다. (activities : optimization, Instruction scheduling gloval, register allocation)

----
'''Dependence Graph'''

Data-dependence Graph는 value의 흐름을 definition point 와 use points 들의 관계로 인코딩한다.

data-dependence Graph 의 Node는 operations을 나타낸다.  


----
==== 5.4 Linear IRs ====

5.4.1 Stack-Machine Code
called on-address code

Example:
x-2*y => push x, push 2, push y, multiply, push x, subtract

장점
 Stack-macine code is compact
 Implict name space => shrinks the size of a program
 simple to generate and to execute

Smalltalk80, Java에서 사용

5.4.2 Three-Address Code

모든 operation이 x <- y op z 형태를 가진다.

Example:
x - 2 x y
 t1 <- 2
 t2 <- y
 t3 <- t1*t2
 t4 <- x
 t5 <- t4-t1

장점
 Resembles many machines
 Introduce a new set of names
 Compace form

5.4.3 Representing Linear Codes
linear IR을 구현하는데 여러가지 자료구조가 이용된다.

Three-address code는 quadruples로 구현 될곤 한다.
quadruples 는 operator, two operands, 와 destination으로 구성된다.  
 간단한 레코드 구조
 쉽게 순서를 변경 할 수 있다.
 명확한 이름

compiler의 front end 부분에서는 IR생성을 하므로 linked list를 선택하는 것이 낫고,
instruction scheduler하는 부분에서는 array가 낫다.

==== 5.5 Static Single-Assignment Form ====
control flow 와 data flow 모두를 program text에 추가한다. (?)

장점
 각각의 name은 한번에 정의한다..(o-function이 가능하게 해줌)
 o-function의 위치는 컴파일러에게 flow of values 에 대한 정보를 준다.
 shaper analysis
 o-function five hints about placement(?)
 빠른 알고리즘

5.6 Mapping values to Names
IR의 종류나 추상화 레벨에따라 컴파일러가 하는 operation을 결정하는데 도움이 된다.

5.6.1 Naming tempory values
mapping name to value

5.6.2 메모리 모델

Register-to-Register model
 모든 value는 하나의 레지스터에 저장될 수 있다.
 register allocator는 extra load, store 을 추가해야 한다.
 
Memory-to-Memory model
 모든 value는 메모리안에 있다고 가정
 values는 사용되기전에 memory에서 register로 이동
 register-to-register에 비해 register가 적다.
 loads나 stores를 지움으로써 allocalocator는 code속도를 빠르게 할 수 있다.(왜 가능하지?)

RISC machine을 위한 컴파일러는 보통 Register-to-Register이다.
 RISC구조가 프로그래밍 모드를 반영하기 때문에
 레지스터가 안정한지 미리 알수 있다.(레지스터 사용되는것은 미리 알 수 있다.)
 
==== 5.7 Symbol Tables ====
IR정보를 기록하는데 AST를 사용하면 비효율적이다. 아이디어는 IR에 관련된 계산된것(정보) 을 테이블에 집어 넣자는 생각.

5.7.1 Hash Tables
  * 효율성이 좋음(constant-time)
  * hash function 을 이용한다.
  * collision : hash function이 같은 레코드를 가리킬때 문제 발생

5.7.2 Buinding a Symbol Table
컴파일러 부분에서 사용하느 symbol table 의 두가지 interface
  * LoopUp(name) : 테이블에서 name에 관련된 레코드 찾음
  * Insert(name,record) : 테이블에 새로운 record 집어 넣음

5.7.3 Handling Nested Scopes
scope : name space , lifetime of values(or function)

여러 Scope를 어떻게 보조 할것인가?  
 scoped symbol table을 이용한다. ( level, name)

name resolution : 각 변수가 선언을 참조하는 것을 name resolution 이라고 함

lexically scoped symbol table
  * 새로운 scope에서는 새로운 symbold table을 생성한다.
  * 각 symbol table에 레벨을 두어 LookUp(name)을 실행하여 현재 레벨의 테이블을 검사한후, 없으면 상위 레벨을 올라가서 검사한다.
  * <level, offset>을 통해서 각 symbol table을 나눈다.

InitializeScope()
 : 현재 레벨에서 새로운 Symbol table을 생성한다.
FinalizeScope()
 : scope를 떠날때 실행한다. 메모리에서 scope정보 제거

5.7.4 The Many Uses for Symbol Tables

Separate Table
 각 레코드 정의(record definition)를 위해서 사용할 수 있다.

Selector Table
 field name을 위해서 사용할 수 있다.
 다른 구조들의 필드들의 혼동을 피하게 해준다.

Unified Table
 제약어(qualifed names)를 사용할때 사용

Linked Tables for Name Resolution in an Object-Oriented Language
 코드 구조뿐만 아니라 데이터 구조도 잘 관리 해주어야 한다.
 scope의 레벨 뿐만 아니라 상속을 따라 scope가 이동된다.
 global table은 현재 import된 패키지 정보까지 가지고 잇어야 한다.