컴파일러 입문 제 11 장 코드 최적화.

Presentation on theme: "컴파일러 입문 제 11 장 코드 최적화."— Presentation transcript:

1 컴파일러 입문 제 11 장 코드 최적화

2 목 차 기본 블록 지역 최적화 루프 최적화 전역 최적화 기계 종속적 최적화

3 Code Optimization Definition 분류 Preserve programming meaning
Speed up on average Be worth the effort 분류 최적화 범위 지역 최적화(local optimization) 전역 최적화(global optimization) 최적화 코드 기계 독립적 최적화(machine-independent optimzation) 기계 종속적 최적화(machine-dependent optimization)

4 Getting Better Performance
Front End Code Generator source code intermediate code target code Compiler can : Use registers Select instructions Peephole transformations User can : Profile program Change algorithm Transform loops Compiler can : Improve loops Procedure calls Address calculations

5 Basic Block (1/5) 지역 최적화의 기본 단위 시작부터 끝까지 순서적으로만 수행되는 문장 범위 [정의] 기본 블록
블록의 시작과 끝을 제외하고 블록의 내부 또는 외부로의 분기가 발생하지 않는 분해된 기본 코드들의 시퀀스 기본 블록

6 Basic Block (2/5) 기본 블록 구성 leader와 다음 leader 이전에 나타나는 모든 코드
프로그램의 시작 문장 조건부 분기 또는 무조건 분기의 목적지에 있는 문장 조건부 분기 바로 다음에 위치하는 문장

7 Basic Block (3/5) i := 1 GOTO L2 L1 : Statement1 i := i + 1;
L2 : IF i <= N GOTO L1 Statement2 FOR i := 1 TO N DO Statement1; Statement2;

8 Basic Block (4/5) - Flow Graph
기본 블록에 제어 흐름 정보를 추가한 방향 그래프 전역 최적화에 필수 initial i := 1 GOTO L2 B1 B2 L2 : IF i <= N GOTO L1 L1: Statement1 i := i + 1 B3 Statement2 B4

9 B1 B3 B2 B4 B3 B5 B2 B6 initial B4 B5 B1 B6 B8 B7 B8 GOTO Itest
Iloop : J := 1 GOTO Jtest Jloop: T1 := 4 * J T2 := A[T1] T3 := J + 1 T4 := 4 * T3 T5 := A[T4] IF T2 <= T5 GOTO Jplus T6 := 4 * J Temp := A[T6] A[T12] := Temp Jplus : J := J + 1 Jtest : IF J <= I GOTO Jloop Iplus : I := I + 1 Itest : IF I <= n – 1 GOTO ILoop B1 B2 B8 B1 B6 B3 B4 B5 initial B2 B3 B4 B5 B6 B7 B8

10 지역 최적화 기본 블록 내에서 최적화를 수행 기법 : Common subexpression elimination
Strength reduction Constant folding Constant propagation Algebraic simplification

11 Common Subexpression Elimination
공통 부분식의 제거 공통된 부분이 반복되어 나타나는 경우를 제거하는 방법 T := B + C; A := T + D; E := T + F; K := T * G; A := B + C + D; E := B + C + F; K := (B + C) * G;

12 Strength Reduction 연산 강도 경감 연산자의 비용이 적은 연산자로 바꾸는 방법
거듭제곱 -> 승산 -> 가산 제산, 승산 -> 비트이동(shift) A = X * X; Y = A + A + A; X = A * 0.2; X = A rshr 2 A = X ** 2; Y = 3 * A; X = A / 5; X = A / 4;

13 Constant Folding 상수 폴딩 컴파일 시간에 상수식을 직접 계산하여 그 결과를 사용하는 방법
X := A + 2 * 3 X := A + 6

14 Constant Propagation 상수 전파 고정된 값을 갖는 변수를 상수로 대치하는 방법 I := 2 . . .
Constant folding 컴파일 시간에 계산이 가능한 연산을 계산함으로써 실행 시간과 코드의 크기를 줄일 수 있다. I := 2 . . . T1 := 8

15 Algebraic Simplification
대수학적 간소화 수학적인 대수 법칙을 이용하여 식을 간소화하는 방법 X = A + 0; X = 1 * A; Constant * Symbol A := 2 * B / 2; X = A; Symbol * Constant A := B; T1 := 4 * J – 1 . . . T7 := T1 + 1 T1 := 4 * J – 1 . . . T7 := 4 * J

16 Loop Optimization 전체 코드의 10%가 실행시간의 90%를 차지 대부분의 실행 시간을 루프 내에서 소모 기법 :
루프 불변 코드 이동 연산 강도 경감 루프 언롤링 루프 융합 영으로의 카운트

17 Loop Invariant FOR k := 1 TO 1000 DO
c[k] := 2 * (p – q) * (n – k + 1) / (sqr(n) + n) ; fact := 2 * (p – q) ; denom := sqr(n) + n ; FOR k := 1 TO 1000 DO c[k] := fact * (n – k + 1) / denom ;

18 Loop Unrolling 루프의 반복 횟수를 감소시키는 방법 FOR k := 1 TO 1000 DO c[k] := 0 ;
FOR k := 1 TO 1000 STEP 2 DO BEGIN c[k] := 0 ; c[k + 1] := 0 ; END

19 Count up to Zero 루프의 종료 조건을 검사하는 경우 0인지 아닌지를 검사하는 경우가 효율적
FOR k := 0 TO N - 1 DO BEGIN … k END FOR k := N – 1 DOWNTO 0 DO BEGIN … N - k END

20 전역 최적화 기본 블록 간의 정보와 흐름 그래프를 이용하여 프로그램의 전체적인 흐름 분석을 통한 최적화 기법 :
공통 부분식의 제거 전역 상수 폴딩과 전파 도달될 수 없는 코드의 제거 조건문의 재구성 연속 GOTO 축약

21 전역 최적화 X := 1 Y : =2 T := X * Y If (T = 2) X := 1 Y : =2 T := 2
TRUE FALSE X := 1 Y : =2 T := 2 If (2 = 2) TRUE FALSE X := 1 Y : =2 T := 2 If (2 = 2) TRUE

22 기계 종속적 최적화 Postcode optimizer 기법 : 중복된 load 제거 효율적인 명령어 선택 레지스터 할당과 배정
연산 순서 재조정 목적 코드 Postcode optimizer 최적화된 목적 코드

23 중복된 load의 제거 LOAD R1, Y STORE R1, X LOAD R1, X X := Y ; ADD R1, =1
STORE R1, Z X := Y ; Z := X + 1 ;