[컴파일러개론] 기말고사 정리

12주차

symbol tables

semantic analysis(의미분석)

- scope관련 : 변수가 선언되기 전에 쓰였나? 두 번 정의됐나?

- type관련 : 변수와 assign되는 값과 타입이 맞는가?

1. 한 lexical마다 한 symbol table

2. scope들은 계층구조를 가짐

local 구조 : hash table 사용

global 구조 : n-ary tree(계층구조)

-> 포인터 유지 등의 비용때문에 트리 안쓰고 stack 씀

 

hierarchies of local tables

제일 마지막에 접근된 것이 바로 접근된다.

 

type checking

타입 : 값의 범위, 어떤 조건을 만족하는지

타입을 선언하고(binding), 검사(checking)

 

static vs dymanic checking

타입 검사 시점:  컴파일 시 vs 수행 시

static vs dynamic typing

타입 정의 시점 : 컴파일 시 vs 수행 시

strong vs weak typing

타입 오류 : 엄격히 방지 vs 조금 허용

Sound type systems : 모든 타입 오류를 방지하는 타입규칙 집합 및 enforce 시스템

   

타입 judgement

E : T  => E는 T 타입을 만족한다.

unit은 well typed임을 표현

 

type 유도 트리

그 밖의 의미분석

 scope, type check외에 하나더

"control flow errors"

break, continue가 while이나 for 안에 들어 있는지

goto label들이 해당 함수 안에있는지 등

기타 AST를 따라가면 어렵지 않게 알 수 있는 간단한 결들    

 

13주차

Physical 제약이 좀 더 강한, 머신 각각에 최적화된

 

Instruction Selection

Tree기반 중간코드로 시작

 

operation

- MEM(e) : 주소 e로 시작하는 메모리 한 word의 내용, MOVE의 왼쪽에 사용되면 store, 다른곳에 사용되면 fetch(읽다)의 의미

- TEMP(t) : 레지스터 t

- SEQ(s1, s2) : 문장 s1 수행후 s2 수행

- ESEQ(s, e) : 문장 s의 결과는 없고, side effect만 가지므로 ESEQ 전체의 결과를 내기 위해서는 e가 추가 수행됨

- BINOP(o, e1, e2) : o는 binary operator, 결과는 피연산자 e1, e2를 이용하여 o를 수행한 것, 결과는 메모리에 저장 후 주소 리턴

- const(i) : 정수 상수 i

 

여러 트리 중 비용이 가장 적은 것을 선택하는 과정 => 최적화

눈에 보이는 복잡도만으로 비용을 선택할 수는 없다.

s가 e1 전, 후에 실행했을 때 결과가 달라지지 않을때 동치이다.

machine이 제공하는 instruction set에 맞게 적절한, 빠른, 효율적인 option을 만들어내는 것이 instruction selection이다. 

 

Register Allocation

Low Level IR에서, Virtual registers가 무한히 있다고 가정했었다.

이 VR을 최대한 physical register에 넣고 남는 것은 memory에 spill

 

Interference : 서로 다른 두 definition이 live range에서 공통 operation을 가지고 있는 경우

live range : 정의 ~ 사용되는데까지

 

inteference graph

Node : 변수

Edges : 서로 겹치는것끼리 연결

b와 c는 live range가 겹치지 않으므로 하나의 physical register를 사용해도 문제가 없다.

 

Graph Coloring

연결된 node는 서로 다른 색으로 칠하기

 

Kempe's algorithm

1. simplify : k보다 작은 edge를 가진 node를 찾아서 edge와 함께 잘라냄

2. color : 칠하기

3. spill : 안되는 경우 변수 몇개를 골라 메모리에 저장(spill)

 

stack에 edge가 k-1개인 노드만 넣어준다.(color 즉, 레지스터의 개수가 k개 일 때)

lucky case도 존재

절대 coloring할 수 없는 그래프도 존재 => spilling

 

spilling code

code rewriting

새로운 temporary 변수 도입, 명령 재작성

 t2를 spill하기로 결정한 상태에서 add t1, t2
=> 새 virtual register인 t35 도입

mov t35, [ebp - 24]
add t1, t35

레지스터 자리가 없어서 t2를 쫓아냈는데 왜 또 새 레지스터를 도입?

=> t35의 live range가 매우 짧으므로 interference 가능성은 t2에 비해 거의 없다.

 

Instruction Scheduling

instruction의 순서를 바꿔 stall 개수 등을 줄여 수행 속도를 높임

stall : 다른 명령의 수행을 기다리느라 CPU를 낭비하는 것

레지스터 개수는 하나 증가했지만 cycle은 7이나 줄었다.

일반적으로 오른쪽이 더 선호됨

 

wasting time을 줄이면서, 동일한 코드가 나와야하고, register spilling을 피해야 함

 

levels of static scheduling(컴파일 타임에 하는)

1. precedence graph를 만든다.

2. 각 노드에 priority function을 적용한다.

3. ready-operation queue를 두고, 매 cycle마다 scheduling

set에서 오래걸리는 녀석부터 선택한다.

 

14주차

최적화 : 입력 프로그램과 의미적으로 동등하면서 좀 더 효율적인(실행시간이 짧고, 기억장소 요구량이 최소화된)코드로 바꾸는 것

분석

control flow 분석 vs data flow분석

최적화

inner basic block(local) opt. vs inter basic block(global) opt.

cyclic(loop) code opt. vs acyclic opt.(비순환)

 

Control Flow

프로그램의 실행순서, 관심있는 것은 분기(Branch)

compiler는 static control flow 즉, 눈으로 보고 worst case를 생각해서 예측(정확한 예측은 불가능)

 

CFA(Control Flow Analysis)

CFG를 만들고 정적 성질을 도출하여 코드를 최적화하는것이 목적

 

Basic Blocks(BB)

동일한 execution condition을 적용 받는 instruction의 묶음

- BB의 첫 instruction(leader) 구하기

1. 프로그램의 시작

2. branch의 target instruction

3. branch 직후의 instruction

 

CFG

노드가 BB이고 edge가 이들의 수행 순서를 나타내는 그래프

 

Weighted CFG

프로파일링(몇 번 돌려보고) 빈도를 얻음 => 자주 일어나는 상황에 대해 효과적인 optimization이 가능

 

Acyclic Code Optimization

Acyclic Code : Loop가 없는, 분석 및 최적화가 상대적으로 쉬움

1. Inner basic block opt.

2. Inter-basic block opt.

 

1. Inner basic block opt

- commmon subexpression elimination

공통 부분이 반복해서 나타나는 경우, 한 번만 계산

 

- Algebraic simplification

수학적인 대수 법칙을 이용하여 식을 간소화

- Strength reduction

같은 의미를 가지면서 좀 더 연산자의 비용이 적은연산자로 바꾸는 것

- Constant folding / propagation

folding : 컴파일 시간에 상수식을 직접 계산함

propagation : 고정된 값을 가지는 변수를 상수로 대체

 

 

Inter-Basic Block Optimization

1. global common subexpression elimination

basic block간에 나타나는 공통 부분식에 대해서도 한 번만 계산

(단 그 요소가 바뀌지 않아야 가능)

2. global constant folding / propagation

변수의 정의와 사용이 서로 다른 block에 걸쳐 있는 경우에 대해서도 상수를 인식하여 폴딩과 전파가 가능

 

unreachable code elimination

mark(e) {
    e.visited = true
    for all successors e' of e
        mark(e')
}

1로 모두 초기화해두고, reachable = 0으로

 

loop unrolling

loop body를 펼쳐서 반복 횟수 branch등을 줄임, loop body가 적을 때 유용

 

loop invariant

매번 동일한 값을 내는 문장은 loop 밖으로 이동

 

 

Dataflow Analysis

control flow와 다른점 : 각 노드에 내용을 적는다.(control flow는 번호)

프로그램 내에 각 data들이 생성/소멸되는 정보를 모으는 것

 

Reaching Definition Analysis(RD)

- GEN/KIILL (한 BLOCK 내)

- IN/OUT (BLOCK간)

 

GEN : 현재 블록에 존재하는 generation

KILL

IN : 공집합으로 초기화

OUT : GEN으로 초기화 

OUT = GEN(X) + (IN(X) - KILL(X))

 

while을 이용하여 변하지 않을 때까지 계속 반복