Analysis and Optimization - [2] Optimization

난독화 vs 최적화

항목	최적화 (Optimization)	난독화 (Obfuscation)
목적	성능 향상, 코드 간결화	리버스 엔지니어링 방지, 보안성 향상
방향성	코드 간결화, 구조 단순화	코드 복잡화, 구조 숨기기
예시	상수 전파, 공통 표현 제거	변수명 난독화, 흐름 흐트러뜨리기
기법 기반	제어 흐름, 표현식 분석	같은 분석 기법을 바탕으로 반대 방향으로 활용
결과	사람이 읽기 쉬운 코드 또는 빠른 코드	사람이 읽기 어려운 코드

공통점

• 난독화도 최적화도 코드를 분석해야 실행 가능
• 특히 다음과 같은 분석 기법들이 공통적으로 사용
  • Control Flow Graph (CFG)
  • Data Flow Analysis
  • Liveness Analysis
  • Use-Def Chain

    분석 기술이 같고, 분석 후의 조작 방향이 반대.

Acyclic Code opt.

• Loop가 없는 코드 -> 모든 경로가 유한함 -> 분석 및 최적화가 상대적으로 쉬움
• Contrl Flow Graph 에서 Cycle이 없음.

Inner basic block opt ( = Intra opt, Local opt )

• 단일 블록 내에서 비효율적인 코드를 구분해내고 좀 더 효율적인 코드로 개선
• 흐름을 고려하지 않고 짧은ㅇ 코드 범위에서 비효율적인 부분을 개선한다.

Basic block : 중간에 branch 없이 연속적으로 실행되는 명령어들의 묶음.

• 1개의 진입점. 블록의 첫 명령어는 외부에서만 진입 가능하다.
• 1개의 탈출점. 블록이 끝나기 전까지는 다른곳으로 branch 하지 않는다.
• 연속 실행. 한 블록 내의 명령어는 항상 순차적으로 실행

Common subexpression elimination

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

// Before
a = b + c;
d = b + c + e;

// After
temp = b + c;
a = temp;
d = temp + e;

Algebraic simplification

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

// Before
x = x * 1;
y = y + 0;

// After
x = x;
y = y;

Strength reduction

같은 의미를 가지며 좀 더 연산자의 비용이 적은 연산자로 바꿈 -> 반복문에서 많이 사용한다.

// Before
x = y * 2;

// After
x = y + y;

Constant folding / propagation

folding : 컴파일 시간에 상수식을 직접 계산하여 필요한 곳에 사용

// Before
y = 4;
x = 3 * y;

// After
x = 3 * 4;

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

// Before
x = 3 * 4;

// After
x = 12;

Inter-basic block opt ( = Global opt )

• 어려 basic block 간의 관계를 고려하여 최적화
• 제어 흐름 전체를 분석하며, 함수 또는 프로그램 단위에서의 최적화
• Dead Code Elimination, Constant Propagation .. 등

Global application of inner-basic block

Global common subexpression

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

// Before
if (x > 0) {
    a = b + c;
} else {
    d = b + c + e;
}

// After
t = b + c;
if (x > 0) {
    a = t;
} else {
    d = t + e;
}

Global constant folding / propagation

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

// Before
a = 5;
if (cond) {
    b = a + 3;
} else {
    c = a * 2;
}
// After
// a = 5 이므로 상수 전파 및 폴딩 적용
if (cond) {
    b = 8;
} else {
    c = 10;
}

Other transformations

Branch의 숫자를 줄이고, basic block을 더 크게 만들기, 코드 길이 줄이기 등

Branch to unconditional branch

조건 분기가 항상 특정한 방향으로만 갈 경우, 무조건 분기로 단순화

// Before
if (1) {
    goto L1;
}
// After
goto L1;

Unconditional branch to branch

무조건 분기가 또 다른 무조건 분기를 가리킬 경우, 중간 단계 생략

// Before
goto L1;
// ...
L1: goto L2;

// After
goto L2;

Branch to next basic block

분기 명령이 다음에 실행될 블록을 가리키면 분기 없이 흐름에 맡김

// Before
goto L1;
// ...
L1: x = 3;

// After
// goto 생략
x = 3;

Basic block merging

연속된 블록 사이에 분기가 불필요하면 하나로 병합

// Before
L1: x = 1;
L2: y = 2;
// After
L1: x = 1;
    y = 2;

Branch to same target

여러 분기가 동일한 target을 가리킬 경우, 중복 분기를 제거

// Before
if (a) goto L1;
if (b) goto L1;

// After
if (a || b) goto L1;

Branch target expansion

여러개의 작은 블록들이 동일한 타겟을 참조할 경우, 코드를 해당 위치로 확장하여 분기 제거

// Before
if (a) goto L1;
...
L1: x = 1;

// After
if (a) {
    x = 1;
}

Unreachble Code Elimination

도달 할 수 없는 블록 제거

// Before
return;
x = 10; // never reached
// After
return;
// x = 10 제거됨

Example

위의 프로그램을 최대한 최적화 해보자.

L1: if (a < b) goto L9 // L11: goto L9 → 바로 연결
if (c < d) goto L13 // L2→L7
if (e < f) goto L9 // L14 조건 유지
stuff13 // L13
L13_end:
stuff9 // L9
if (a < c) goto L4 // L10 → L3 → L4
L4: stuff4 // L4
if (c < d) goto L15 // L5
L15: stuff15 // L15
L16: rts // L16

1. 중복 분기 제거
   L2,L3,L6,L8,L11,L12

2. 조건 분기 직접 연걸
   if -> 실제 실행되는 블록으로 바로 연결

3. GOTO 제거

4. basic block 병합

Loop Optimization

루프는 한번 최적화 해두면 효과가 크다. 여러번 반복되기 때문. 따라서 누적 성능 향상을 기대할 수 있다.

• Common Subexpression Elimination : 동일 계산 제거
• Algebraic Simplification : 수학적으로 단순화
• Strength Reduction : 더 효율적인 연산으로 바꾸기

Loop 고유의 opt

Loop unrolling

Loop body를 펼쳐서 반복 회수 branch 등을 줄임, 다른 최적화 기회도 높인다.
loop body가 적을 때 유용. 반복 횟수가 정해져있거나 작을 때 효과가 크다.

for (int i = 0; i < 4; i++) {
    a[i] = a[i] * 2;
}
->
a[0] = a[0] * 2;
a[1] = a[1] * 2;
a[2] = a[2] * 2;
a[3] = a[3] * 2;

Loop invariant

매번 동일한 값을 내는 문장은 loop 밖으로 이동하여 한번만 계산

for (int i = 0; i < n; i++) {
    y = x * 10; // 매번 같은 계산
    a[i] = y + i;
}
->
y = x * 10;
for (int i = 0; i < n; i++) {
    a[i] = y + i;
}

Count up to zero

loop의 종료 조건을 동일한 의미를 가지면서 0과 비교하는 식으로 바꾸기

for (int i = 0; i < n; i++) {
    process(i);
}
->
for (int i = n; i != 0; i--) {
    process(n - i);
}