컴파일러 설계강의 정리

오전 10:52 2007-04-25
조경민 컴파일러 설계강의 정리

frontend
-----------------------------------
lexical analysis
- word check [scanning]
   => fsm (not string tokenizer)

syntax analysis
- sentance(grammer) check [parsing]
   => parsor = fsm+stack

semantic analysis
- type checking
   => symbol table

intermediate representation
- AST or 3-address code(Text) IR

syntax-directed translation


back end
-----------------------------------
optimization
- formulation (goal:size,speed)
- analysis
- transform, perf. estimation

CFA(Control Flow Analysis)
  - Build CFG (Basic Blocks)
     => DFS (Depth First Search) => DFT 생성 가능(Edge) => Unreachable code elimination 활용
  - Build Dominatance(Dominator Tree, postdominance) => CSE 활용
  - Find Loop (back edge with DFT)

DFA(Data Flow Analysis)
  - DFI
  - Local Data flow Analysis
  - Global Data flow Analysis
  - Def-Use/Use-Def chains

  DFA로 풀수 있는 문제
  1. available expression problem: 이전에 사용한 변수가 변경이 없었는지 확인
  2. reaching definition problem: 값 정의된 변수가 어디서 사용되는지
  3. aliasing problem: 어떤 변수가 같은 메모리를 가리키는지
  4. live variables problem.

대부분 DFA 기술은 DFI (Data)와 DFE (Data Flow Equations, SET의 수학표현, 함수, 필터)로 표현됨

Reaching Definition: Fs(in[S]) = gen[S] ∪ (in[S] - kill[S])
Available Expression:
for each basic block B do
   out[B] = egen[B] ∪ (Universal - ekill[B])
od
while changes to any out[B] occur do
   for each segment X in DFS order do
     in[B] = ∩ out [Pb]; // all predecessors Pb of B
     out[B] = egen[B] ∪ (in[B] - ekill[B]);
   od
od

Dependency Analysis
- Read After Write: flow dependence(true dependency)
- Write After Read: anti dependence (false)
- Write After Write: output dependence (false)

Optimization
A. Elimination of redundancies
    a. Dead code (mark instruction essential results)
    b. Redundant computations or expressions
       - Value numbering and common subexpression elimination)
       - code motion and hoisting/sinking
       - partial redundancy elimination
       - algebraic transformations
      CSE (Common subexpression elimination)
perform DFA to compute in[B]; // available expression collect
for each expression e in in[B] of every block B do
   locate the evaluation of e at a statement s in B;
   if s = null or // if there is no statement in B that evaluates e
     e has been killed before s then continue;
   R <- a set of statements Si in all predecessors Pi of B
     such that e is evaluated in Si;
   substitute a new temporary Te for e in s;
   for each Si in R do
     insert 'Te = e' immediately before Si;
     substitute Te for e in Si;
   od
  od
B. Progpagation of data
   a. constants propagation
   b. constants folding
   c. copy propagation
C. Peephole Optimizations
   a. DAG(Directed Acyclic Graph)사용
   b. Machine idioms
   c. Peephole of control flow
     - Tail merging
     - Straightening : 불필요한 브렌치 제거
     - Branch simplifications : branch시 안가는 코드, 브렌치 전체 제거
D. Loop Optimizations
   a. Unswitching : loop안 branch를 loop 밖으로
   b. loop elimination: zero count loop 제거
   c. loop inversion: while -> do while
   d. strip mining
   e. loop unrolling
   f. optimizations of induction variables

code generation
-----------------------------------
Instruction selection
a. macro expansion
b. L-R parsing
c. tree parsing(pattern matching)
d. machine description
Register allocation
a. Web (from DU chain)
b. Register coalescing (맞닿은 copy 변수 변수 없애기)
c. Graph coloring (with Interference graph)
Instruction cheduling