컴파일러 - Optimization

Semantic Analysis 까지가 front end이고 이제 code generation 하기 전의 최적화 과정이다. 

[용어정리]

Intermediate Representation (IR)

말그대로 중간 표현 으로, 어떤 frontend, backend를 쓰는 동일한 optimizer를 쓸 수 있다.

High-Level Assembly 

아래 설명에서는 high level assembly를 사용한다고 가정한다.

register가 무한개가 있고,

control 구조는 assembly와 비슷하며

operation code를 쓰나 일부는 higher level이다.

Igen

IR를 위한 Code generation으로 igen(e, t)이면 e를 레지스터 t로 넣는 데 필요한 코드를 뜻한다.

이때 register를 무한개라고 가정했기 때문에 간단하다.

BB(Basic Block)

no label, no jump - entry point 하나, exit point 하나

중간에 다른 곳으로 jump 하지 않는 실행단위이다.

CFG(Control Flow Graph)

BB가 노드인 그래프. 노드 끼리 연결되어 있다는 뜻은 서로 실행 연관성이 있다는 것을 뜻한다. 

그다음에 실행된다는 뜻

---

Optimization Overview

최적화는 자원의 활용을 향상하는 데 목적이 있다. 

• 실행시간
• 코드 사이즈
• 네트워크 메시지 수 

BUT. 최적화를 한다고 해서 프로그램이 하는 작업이 바뀌어서는 안 된다. (일관성)

 

Optimization Scope

• local optimization - BB(Basic Block) 안에서 optimization 하는 것이 목표
• global optimization - CFG 에서 optimization 하는 것이 목표
• Inter-procedural optimzation - procedure 간 사이에서 optimization 하는 것이 목표

Optimization Types

Dataflow Optimization 

• 데이터 변경에 관한 것들
• 중복 연산, 계산을 간단히 하는 것들이 해당됨

Local Optimization: Algebraic Simplification

 연산을 간단하게 바꾸는 것이다. 예를 들어 1를 곱하거나 0을 더하는 것들은 없애줘도 된다.

또한 곱 연산을 shift로 바꾼다거나 제곱연산을 곱연산으로 바꾸는 것들이 있다. (y := y ** 2 ➡️ y:= y*y)

 

Local Optimization: Constant Folding 

미리 계산 할 수 있는 상수들은 compiler에서 미리 계산하는 것이다. 

BUT. floating point precision  같은 문제가 발생할 수 있다. compiler와 수행하는 머신에서 반올림 정확도가 다를 때

 

Local Optimization: Unreachable Code 

도달하지 않는 BB들을 삭제하는 것이다. 예를 들면 디버깅용 코드, 라이브러리를 다 호출햇는데 일부만 사용할 때

 

Local Optimization: Dead Code Elimination

어느 곳에서도 사용하지 않는 코드를 없애 버리기

 

Global Optimization: Constant Propagation

전파 상수 - 즉 CFG 전체를 봐야 해당 변수가 상수인지 아닌 지 파악할 수 있다.

 

Global Optimization의 특징

• 특정 시점에서 X가 어떤 값인 지 증명하는 과정이다.
• 전체를 알아야 알 수 있다.
• 무조건 true 여야지 true로 친다.

 

Anaysis of Reaching Definition

어떤 값이 Basic Block b에 도달하는지 알아내는 과정이다. 

BB를 들어가기 전에 IN[b], OUT[b] 이렇게 적는다. 

• forward : IN ➡️ OUT (ex: reaching definition)
• backward : OUT ➡️ IN (ex: liveness analysis)

Reaching Definition ( forward )

GEN[b] : BB에서 새로 생기는 값

KILL[b] : 전체 값들 중에서 BB에서 사용되는 값 말고 나머지

OUT[b] = GEN[b] ∪ (IN[b] - KILL[b])

IN[b] = OUT들의 union

 

🕹️알고리즘

root에서부터 시작해 todo list에 넣는다.

하나씩 pop 해서 해당 BB의 IN, OUT을 계산하고 successor(갈 수 있는 BB)를 todo list에 넣는다.

반복한다. 

 

Liveness Analysis ( backward )

dead code를 찾는 것이 목적임

이게 약간 줄넘기 반대로 하는 것처럼 헷갈렸다. 

OUT ➡️ IN으로 가면 된다. 

USE[b] = BB에서 사용되는 것들

DEF[b] = 재정의 되는 값

IN[b] = USE[b] ∪ (OUT[b] - DEF[b])                                                                                    

OUT[b] = IN 들의 union

 

🕹️알고리즘

exit 에서부터 시작한다. worklist에서 하나씩 빼면서 각 BB의 OUT, IN을 계산한다. 

predecessor들을 worklist에 넣는다.

Constant Propagation(상수 전파)

특정 시점에서 constant로 바꿀 수 있는지 알아내기. 

x = T : constant가 아닐 수 있음

x = c : constant

x = Ʇ : bottom, initialize 된 값

 

block 내에서 할당될 때 c이거나 T이면 value 값이 된다.  - 정확한 값을 유지하기 위해서

edge에서는 T 이면 T이고, Ʇ이면 놔두고, value가 있으면 그걸로 업데이트해준다. 

 

Control flow Optimization

• 코드 실행 순서에 관한 문제
• unreachable code를 없애거나, 연산 수를 줄이거나

Dominator

• 각 BB는 자기 자신을 지배한다.
• 만약 x가 y를 dominate 하고 y가 z를 dominate 하면 x는 z를 dominate 한다.

Dominator Tree

• 초기 노드는 root
• parent노드는 그 아래 후손들을 다 dominate 함

Natural Loops

• Loop 전체를 지배하는 header가 존재함
• backedge는 target이 source를 dominate 한다. backedge는 적어도 한 개의 loop의 일부여야 한다.
  • 3 ➡️ 4로 가는 데 4가 3을 dominate 하는 경우

Algorithms to Find Natural Loops

1. CFG에서 dominator 관계를 찾는다.
2. back edge를 찾는다.
3. back edge와 관련해 natural loop을 찾는다.

Back Edge는 각 edge를 DFS like 하게 돌면서 target이 source를 dominate 하는지 확인.  

 

Important Concepts in a Loop

• header and Loop BB
• Back edges
• Exit Edges
• Preheader -  iteration 동안 한 번만 실행됨

Loop Invariant Compuation

loop 내에서 변하지 않는 연산 찾기 

 

LICM(Loop Invariant Code Motion) - Loop invariant를 code의 preheader로 옮기자

LICM Formulation

1. loop invariant code를 찾고
2. pre-header로 옮길 수 있는지 확인하기 (Code Motion -  모든 invariant를 preheader로 옮길 수 있는 건 아니다)

Code Motion의 조건들 - preheader로 옮길 때

• 모든 loop exit에서 dominate 해야 함, 즉 빠져나갈 수 있는 구멍이 있으면 안 됨. 실행 안될 수도 있어서
• loop안에서 한 번만 정의되어야 함
• loop 이전에 live 해서는 안됨, d = 0이고 만약 loop에 들어오자마자 쓰이면 이건 live 한 거임

More Aggressize Optimizations

• Liveness aware relaxation : 만약 loop 이후에 live 하지 않는 것들이 있다면 그건 모든 exit에 대해서 dominant 하지 않아도 됨
• Landing pads : condition을 먼저 하고 loop enter

Loop Unrolling

• Type 1: 루프 반복 횟수를 알고 있어서 그만큼 펼쳐서 수행
• Type 2: 루프 횟수를 정확히 알지는 못하나 대부분 unroll 하고 나머지 수행
• Type 3: while문에서 쓰이는 것으로 데이터 의존성을 줄임

Profile based Optimization

• taken, non-taken을 조사해서 수행
• 연속적인 메모리 주소에서 읽어오는 게 유리하니까 확률을 보고 그것을 연속적으로 배치해 두는 것