[Compiler Design] Analysis and Optimization

 

 

 

Machine Dependent Processing에서는 가상의 코드를 실제 하드웨어에 맞춰서 매핑하는 작업을 수행함.

Instruction Selection - Instruction Scheduling - Register Allocation 

 

Machine Independent Optimization에서는 특정 하드웨어와 상관없이 논리적으로 코드를 개선하는 작업을 수행함.

Control Flow Analysis를 통해 프로그램의 분기 구조를 파악하고 최적화한다.

 

최적화의 목표는 실행 시간 단축 + 메모리 사용량 최소화.

코드를 분석하고, 분석 결과를 통해 최적화를 수행해보자.

 

 

 

---

 

 

 

Control Flow는 프로그램의 실행 순서를 의미함.

그냥 위에서부터 순차적으로 쭉~ 실행되면 분석할거도 없는데, 분기문으로 실행 순서가 바뀌는게 문제임.

 

Dynamic Control Flow - 실제 실행 시 어느 쪽으로 분기하는지 예측.

Static Control Flow - 입력값을 모르는 상황에서 코드만 보고 가능한 모든 경우를 예측. 

 

여기서 Control Flow Analysis는 프로그램을 실행하지 않고, Static Property를 분석해 Control Flow Graph를 만들고 최적화 하는게 목표로 한다.

컴파일러는 코드의 분기 구조를 실행 전에 분석해 CFG를 만들고 최적화함.

 

CFG를 그리기 위해 코드를 자르는 최소 단위를 Basic Block 이라고 부른다.

제어 흐름이 첫 번째 명령어로만 진입하고, 마지막 명령어로만 빠져나가는 명령어 묶음을 의미하는데.. 이게 먼소리냐면

대충 컴파일러 입장에서 원자적이라고 보면 된다. 첫 번째 줄이 실행되면 나머지 줄도 100% 실행되어야 함. 

 

이게 왜 중요하냐?

컴파일러 입장에서는 특정 블록의 첫 줄이 실행됐을 때 중간에 무슨 일어나는지 고민할 필요 없이 블록 끝까지는 무조건 실행된다고 간주할 수 있어서 편하게 최적화 할 수 있기 때문.. 

 

그러면 일단 블록의 시작점인 Leader를 찾아야 한다. 

 

L1: r7 = [r8]          <-- Leader (프로그램 시작)
L2: r1 = r2 + r3       <-- Leader (L6 분기의 Target)
L3: beq r1, 0, L10
L4: r4 = r5 * r6       <-- Leader (L3 분기 직후)
L5: r1 = r1 + 1
L6: beq r1, 100, L2
L7: beq r2, 100, L10   <-- Leader (L6 분기 직후)
L8: r5 = r9 + 1        <-- Leader (L7 분기 직후)
...
L10: r9 = [r3]         <-- Leader (L3, L7 분기의 Target)

 

 

1. 프로그램의 제일 첫 번째 명령어는 Leader 

2. Branch의 목적지가 되는 명령어는 Leader

3. Branch 바로 다음에 오는 명령어는 Leader 

 

Leader를 찾으면, 그 Leader부터 다음 Leader 바로 앞 까지가 하나의 Basic Block으로 설정할 수 있다.

 

 

Basic Block을 나눴으면 이제 저 블록들을 연결해서 흐름을 보여주는 CFG를 그릴 수 있다. 

 

 

 

 

 

예시를 보면 쉽게 이해 가능..

 

이전 작업에서 구한 Basic Block를 노드로 사용한다.

 

간선은 실행 순서를 나타낸다. 

특정 Basic Block의 끝에서 다른 Basic Block의 시작으로 이동할 수 있으면 간선을 그린다.

이 때 goto, if 등으로 분기하는 경우도 있고, 분기 없이 바로 아래 코드로 이어지는 경우도 있음.

 

컴파일러는 분석의 편의를 위해 실제 코드에는 없지만 Entry와 Exit노드 두 개를 추가한다.

 

 

 

Static Analysis로 부족할 때 실제로 프로그램을 실행(Profiling)해보고 그 결과를 CFG에 붙일 수 있다.

 

Edge Profile : 분기에서 A로몇 번, B로 몇 번 갔는지 횟수를 기록.

Weighted CFG : CFG의 엣지에 실행 빈도를 기록 

 

자주 실행되는 경로를 알 수 있고, 이걸 바탕으로 또 최적화 할 수 있음.

웬만하면 1번 실행되는 코드보다 100번 실행되는 코드를 깎는게 합리적이니까..

 

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

Acyclic Code Optimization은 말 그대로 루프가 없는 코드를 최적화 한다는거임.

루프가 없으니까 분석이 훨씬 쉽다. 

 

Inner Basic Block Optimization

한 개의 Basic Block 안에서만 비효율적인 부분을 최적화한다.

 

이걸 수행하는 4가지 기법이 있음.

 

1. Common Subexpression Elimination

수능 수학에서 많이 쓰던 테크닉 같은... 공통 부분식을 묶는 작업이다.

x = a + c; y = a + c + d; 가 있으면 y = x + d; 로 대체해서 계산함.

 

2. Algebraic Simplification

0을 더하고 빼거나 1을 곱하는 연산은 하나 마나 결과가 똑같다. 이런 연산을 제거함.

 

3. Constant Folding / Propagation

Folding은 컴파일 시간에 미리 계산하는걸 의미함. 

변수가 상수인게 확실하다면 상수로 바꿔서 계산한다.

 

4. Strength Reduction

제곱 연산, 실수 연산은 오버헤드가 크다. 정수 나눗셈, 곱셈 및 Shift 연산으로 바꾼다.

 

 

Inter Basic Block Optimization

위에서 다룬 기법을 블록 경계를 넘어서 적용한다고 보면 된다.

블록 1에서 x = 1; 을 정의했는데, 블록 2에서 x가 변하지 않았으면 2에서도 x를 1로 취급하고 사용한다.

 

CFG의 구조를 단순하게 바꾸는 작업을 수행한다.

 

1. 어차피 바로 밑에 있는 블록으로 점프한다면 관련 코드를 지워도 괜찮다.

2. 두 블록 사이의 연결이 하나 뿐이라면 두 블록을 하나로 합쳐서 사용한다.

3. Entry 블록에서 시작해 절대 도달할 수 없는 블록이 있을 수 있음. 이런 코드를 삭제해준다.

다만.. 보안 관점에서는 Dead Code를 더미 코드로 둬서 분석을 방해하는 경우도 있음.

 

 

 

 

---

 

 

 

 

루프를 최적화해야 한다. 그냥 루프가 문제임. 이걸 최적화해두면 앞으로가 편해진다.

앞에서 다룬 기법을 그대로 루프 내부에 적용하는것도 당연히 가능하지만, Loop Optimization 만을 위한 최적화 방식이 몇 개 있음.

 

1. Loop Unrolling

반복 횟수를 최대한 줄이기 위해 한 번 돌 때 여러 일을 처리하도록 코드를 펼친다.

루프 제어에 사용되는 오버헤드를 줄이고 펼친 코드 안에서 최적화 진행. 

 

이게뭔소리임? 코드를 보자.

 

// Before
i = 0;
while (i < 1000) {
    z[i] = 0;
    i++;
}

// After
i = 0;
while (i < 1000) {
    z[i] = 0;
    z[i+1] = 0; 
    i += 2;     
}

 

 

아~ 펼친다는게 이런 소리구나~ 뭔말알~

 

 

2. Loop Invariant Code Motion

루프가 돌 때 값이 변하지 않는 계산을 굳이 해야 함? 그냥 루프 밖으로 빼자.

 

// Before
for (i=0; i < 1000; i++) {
    z[i] = cos(x) + i * sin(x); 
}

// After
c = cos(x);
s = sin(x);
for (i=0; i < 1000; i++) {
    z[i] = c + i * s;
}

 

 

3. Count up to Zero

CPU 하드웨어의 특성상 비교할 때 Zero Flag를 쓰는게 오버헤드가 훨씬 적다.

 

for(int i=1; i<n; i++) { ... } 이거 보다는

for(int i=n; i>0; i--) { ... } 이렇게 0이랑 비교시키는게 미세하게 더 효과적임.

 

 

 

 

---

 

 

 

 

Control Flow Analysis로는 코드가 어떻게 뻗어나가는지를 확인하고, Dataflow Analysis는 그 길 위를 지나다니는 데이터의 LifeCycle을 추적한다.

CFA는 단순히 A -> B 로 간다는 정보만으로는 최적화 할 수 없다. Basic Block 내부의 연산을 보고 값의 LifeCycle을 추적해야 함.

 

 

 

Reaching Definition Analysis

 

Definition : x = 1; 에서 x를 의미한다.

Kill : 같은 변수에 새로운 값을 대입하면 kill 됐다고 표현함.

Reach : 정의 d가 특정 지점인 p에 도달했다는건, d - p 까지의 경로 중 d를 죽이는 정의가 없음을 의미한다.

 

1번줄에서의 Definition인 r1은 5번줄까지 Reach 한다.

이후 9번줄에서 r1 = 4; 가 있다면 d1은 Killed 된다.

 

 

 

 

 

GEN (Generated) : Basic Block에서 새로 태어난 정의들을 의미함.

KILL : Basic Block 때문에 죽어버린 프로그램 전체의 다른 정의들을 의미함.

IN : 현재 Basic Block의 Entry 시점에 살아있는 정의들을 의미함.

OUT : 현재 Basic Block의 Exit 시점에 살아있는 정의들을 의미함.

 

 

 

 

 

각 블록별로 블록 내부를 한 줄씩 읽으면서 GEN / KILL 을 계산한다.

블록들은 서로 연결되어있으니, 데이터가 흘러다니는걸 계산한다. 

Fixed-Point 개념을 적용해... 값이 변하지 않을 때 까지 계속 반복해준다.

 

 

현대 컴파일러는 이 개념을 좀 더 발전시켜서 Static Single Assignment 폼을 사용한다.

사실상 SSA가 컴파일러 최적화의 표준임. 보안에서도 Binary Analysis할 때 SSA 형태로 변환해서 분석한다.

 

모든 변수는 코드상에서 딱 한 번만 할당되어야 한다.

 

// BEFORE
x = 1;
x = 2;
y = x;

// AFTER
x1 = 1;
x2 = 2;
y1 = x2;

 

 

코드를 작성할 때 변수 값을 계속 바꿀 수 있음. 하지만 SSA는 그걸 허용하지 않는다.

 

 

// BEFORE
if (...) {
    x = 5;
} else {
    x = 3;
}
y = x; // ?? 뭘 선택해야 함?

// AFTER
if (...) {
    x1 = 5;
} else {
    x2 = 3;
}

x3 = phi(x1, x2);
y1 = x3;

 

 

분기문을 처리할 때는 phi 함수를 사용한다. 

제어 흐름이 어디서 도달했는지에 따라서 적절한 값을 선택해주는~ 아주 편한 함수.

 

 

그냥 변수만 늘어나고 아무런 이점이 없는 것 같아 보이지만, 분석이 굉장히 편해진다.

이 변수가 어디서 왔는지 찾을 때, 일반 코드는 위로 쭉~ 스캔해야 하지만, SSA를 쓰면 이름과 정의가 1:1로 매치돼서 편하다.

즉, Dead Code Elimination, Constant Propagation 등 최적화 알고리즘을 훨씬 빠르고 정확하게 수행할 수 있음.

 

 

 

 

 

LLVM IR 은 설계할 때 SSA를 기본으로 채택함.

LLVM IR 코드를 보면 %1 처럼 뒤에 번호나 이름이 붙은 임시변수들이 계속 새로 생기는데, 이게 SSA라는 증거임.