제 11 장  코드 최적화

제 11 장  코드 최적화 최적화는 여러 단계를 거쳐 생성한 중간 코드를 분석하여 실행시간이나 메모리 공간을 줄이도록 코드를 개선하는 작업이다. 그러므로 실행 시간을 줄일 것인지 메모리 공간을 줄일 것인지에 따라 여러 기법을 사용한다. 어떤 기법은 실행 시간을 줄여서 프로그램 속도를 향상시키고, 어떤 기법은 메모리 공간을 줄인다.

그림 11.1 컴파일러의 최적화 단계

11.1 기본 블록과 DAG 아래 프로그램 문장을 몇 개의 단위로 나누어 보자. k = (a - b) + (c - d) 이 문장을 중간 코드로 번역하면 아래와 같다.         sub  a,  b,  t1         sub  c,  d,  t2         add  t1, t2,  t3         sto  t3,   ,  k

이 중간 코드는 아래와 같이 여러 단위로 분리할 수 있다. 중간 코드1  sub  a,  b,  t1 중간 코드2  sub  c,  d,  t2 중간 코드3  add  t1, t2,  t3 중간 코드4  sto  t3,    ,  k

아래 할당문을 중간 코드로 번역하고 연산자를 중심으로한 제어 흐름 그래프를 구성하면 그림 11.2와 같다.            a = (b + c) * (b + c) 이 할당문을 번역한 중간 코드는 아래와 같다.         add  b,  c,  t1         add  b,  c,  t2         mul  t1, t2,  t3         sto  t3,   ,  a

연산자 중심 제어 흐름 그래프 예 그림 11.2 a = (b + c) * (b + c)의 연산자 중심 제어 흐름 그래프

여기에서 살펴보아야 할 것은 더하기 중간 코드(add) 하나와 저장(sto) 중간 코드를 제거한 중간 코드는 아래와 같다. 이것이 코드를 최적화한 것이다. add  b,  c,  t1                 mul  t1,  t1, a

그림 11.3은 그림 11.2의 제어 흐름 그래프를 최적화한 것이다. 그림 11.3 할당문 a = (b + c) * (b + c)의 최적화 제어 흐름 그래프

기본 블록 기본 블록은 프로그램에서 if, while, repeat, case 같은 문장의 단순 문장을 묶은 복합 문장이나 구조를 이루는 여러 문장을 기본 블록이라 한다.

C 언어로 구성한 아래 프로그램 일부를 살펴보자. a = k + (f - 100) + t; c = a + (f * 100) / 56.7; if (a == b ) {         a = k + 100;         k = a * 100;         }      else {              a = k - 100;              k = a / 100;            } t = a - k + (f - 100) + r;

a = k + (f - 100) +t; c = a + (f * 100) / 56.7; if (a == b ) { 블록1 a = k + (f - 100) +t; c = a + (f * 100) / 56.7; 블록2 if (a == b ) 블록3      {        a = k + 100;        k = a * 100;      } 블록4 else {        a = k - 100;        k = a / 100;       } 블록5 t = a - k + (f -100) +r; 블록6 ....

DAG 예 그림 11.4는 블록으로 분리한 위의 프로그램을 제어의 흐름에 따라 그래프로 표현한 것이다. 그림 11.4 프로그램의 제어 흐름 그래프

그림 11.5 DAG은 프로그램 제어의 흐름에 따라 기본 블록과 기본 블록을 연결하는 그래프로 제어의 흐름에 따른 방향이 있고 어떤 기본 블록에서 자신의 블록으로 되돌아오는 경로(사이클)가 없다.  그림 11.5 제어 흐름 그래프의 DAG

간단한 산술 수식과 할당문의 DAG 만들기 단계1. 한 중간 코드를 가져온다. 단계2. 연산자와 피연산자가 이미 만들어진 DAG의 일부와 매치하면 (즉, DAG 의 일부이면), 결과 레이블을 부모에게 있는 레이블 리스트에 추가하고 단계 1부터 반복한다. 아니면, 이미 DAG에 없는 각 피연산자에 대해 새 로운 노드를 할당 한다. 또 연산자 노드도 할당하고 노드에 이름을 붙인 다. 단계3. 연산자 노드를 두 개의 피연산자 노드에 방향이 있는 선으로 연결한다. 연산자 우선순위를 위하여 왼쪽 피연산자인지 오른쪽 피연산자인지 명 확히 한다. 단계4. 단계 1부터 반복한다.

산술수식 (a + b) + (a + b) + (a + b)의 DAG를 구성하여 보자. 이 수식에는 연산을 여러 번 하는 공통 수식이 있기 때문에 최적화할 필요가 있다. 이 수식을 번역하면 중간 코드는 아래와 같다.         add  a,  b,  t1         add  a,  b,  t2         add  t1, t2,  t3         add  a,  b,  t4         add  t3, t4,  t5

그림 11.6 산술수식 (a + b) + (a + b) + (a + b)의 DAG 구성 예

이 예에서 DAG를 기본 블록으로 변환할 준비가 되면 아래 단계로 모든 공통 수식을 한 번만 연산하는 중간 코드로 최적화한다. 단계1. 자신에게 들어오는 아크가 없는 임의의 노드를 고른다. 단계2. 그 노드의 연산자와 피연산자에 대한 중간 코드를 출력한다. 단계3. DAG에서 이 노드와 나가는 아크를 제거한다. 단계4. DAG 안에 아직 연산자 노드가 남아있지 않을 때 까지 단계 1 부터 반복한다.

그림 11.7은 위의 공통 수식 제거 방법을 그림 11.6의 DAG에 적용한 것으로 알고리즘이 순환할 때마다의 DAG의 결과이다. 그림 11.7 산술수식 (a + b) + (a + b) + (a + b)의 최적화(공통 수식 제거)

수식 a * b + c + d * (a * b) / c 에 대한 DAG 예 mul  a,  b,  t1 add  t1,  c,  t2 mul  a,  b,  t3 mul  d,  t3,  t4 div  t4,  c,  t5 add  t2, t5,  t6

최적화한 코드와 DAG mul a, b, t1.3 mul d, t1.3, t4 div t4, c, t5         add  t1.3, c, t2         add  t2, t5, t6  그림 11.8 수식 a * b + c + d * (a * b) / c 에 대한 DAG

11.2 전역 코드 최적화 기본 블록으로 구성한 DAG을 바탕으로 몇 개의 전역 최적화 기법을 살펴본다.

11.2.1 실행하지 않는 코드 제거 중간 코드에서 제어의 흐름이 도달하지 않아 실행하지 않는 중간 코드가 있으면 그 중간 코드를 제거하는 기법이다.         jmp  L2         mul  a,   b,  t1          sub  t1,  c,  t2                add  t2,  d,  t3          L2:  add  a,   c,  t4         ....

11.2.2 죽은 코드 제거 원시 프로그램의 특정 부분이 실행하는지 아닌지를 알아내어 실행하지 않는 부분은 제거하는 것이다.                .....         {            a = b + c * d;  /*  이 문장의 결과 값 a 는 아래 문장에 아무런  */            b = j *  d / i;            c = c - 3 + b;            a = b - c + 6;            printf (b, c);         }                ......

11.2.3 순환에서 변하지 않는 코드 이동 ..... for (i = 1; i< 1000; i++) {                         .....         for (i = 1; i< 1000; i++) {               a = sqrt (x);     /*    순환 동안 결과 값이 변하지 않음    */               network[i] = i * a + 120;             }                        ..... 아래같이 변환하면 a = sqrt(x);는 적어도 999번은 호출과 연산을 하지 않는다.            .....         a = sqrt (x);         /*    순환 동안 결과 값이 변하지 않음   */           .....

11.2.4 상수 접기 아래 프로그램에서 변수 a에 대하여 상수 연산 4 * 5를 미리 연산하여 20을 할당하고 a + a에는 40을 미리 할당한다.            .....          {            a = 4 * 5;       /*   a 는 20 이다        */             b = c * (a + a);  /*   a + a 는 40 이다  */          }            .....

아래는 상수 접기에 의해 변환한 프로그램 일부이다.           .....         {            a = 20;              b = c * 40;          }            .....

11.2.5 강세 감소 실행 도중에 연산 시간이 많이 소요하는 연산자를 시간이 적게 드는 연산자로 바꾼다. 곱하기보다는 더하기 연산이 시간을 적게 들기 때문에 곱하기 연산자를 더하기 연산자로 바꾼다. 곱하기 3 * x 는 x + x + x로 변환할 수 있으며 연산 시간도 적게 든다. 지수 연산 x**2(x의 제곱)는 x * x 로 변환할 수 있다.

11.2.6 대수적 변환 아래와 같은 두 할당문의 수식에서 공통 수식 b + c 를 연산할 때 교환법칙으로 제거하거나 바꿀 수 있다.         a = b + c;           b = c + d + b; 위의 두 할당문은 아래와 같이 변환할 수 있다.         b = b + c + d; 그러므로 b + c 는 a 로 대치하여 아래와 같이 최적화한다.         a  = b + c;         b  = a + d;

전체적인 최적화 예 L1: tst a, b, , =10, L2 sub a, =10, a         mul   x, =20,  b          /*   강세 감소   */         add   x,  y, z              /*   죽은 코드 제거  */         add   =20,  =30,  z     /*  상수 접기와 순환 내 무변화   */         jmp   L1         sub   a,  b,  a             /*  이 코드는 실행하지 않는다    */         mul   x,  2,  z             /*   이 코드는 실행하지 않는다   */ L2:       ......

최적화한 최종 결과 mov =50, z L1: tst a, b, , =10, L2 sub a, =10, a         add    x,  x,  b         jmp   L1         lbl     L2

11.3 지역 코드 최적화 지역 최적화는 목적 프로그램에서 중간 코드를 변환하는 기법이다. 이 절에서는 최적화 기법으로 로드/저장 최적화, 점프 최적화, 대수적인 최적화, 레지스터 할당 기법을 살펴본다.

11.3.1 로드/저장 최적화 수식 s + t - r 의 중간 코드 add s, t, t1 sub t1, r, t2 코드 생성기는 아래와 같은 인스트럭션으로 번역한다.         lod      r1, s         add     r1, t         sto      r1, t1         lod      r1, t1         sub     r1, r         sto      r1, t2

여섯 개의 인스트럭션에서 이 두 인스트럭션 lod와 sto를 제거하면 아래와 같이 네 개의 인스트럭션으로 최적화한다.         lod     r1, s         add    r1, t         sub    r1, r         sto     r1, t2

11.3.2 점프 최적화 이 기법은 불필요한 점프를 제거하는 것이다. 아래 문장을 살펴보자. 이 기법은 불필요한 점프를 제거하는 것이다. 아래 문장을 살펴보자.          if ( a > b)  a = b; 위 문장은 아래의 중간 코드로 번역된다.         tst a, b, , 3, L1         jmp L2 L1:         mov b, , a L2:     .....

이 중간 코드의 의미는 “a 가 b 보다 큰지 검사하고 참이면(크면) 할당문으로 점프하고 아니면 할당문 밖으로 점프하라” 이다.         lod      r2, a         cmp    r2, b, 3         /*  r2>b?        */         jmp    L1         cmp    0, 0, 0          /*  무조건 점프  */         jmp    L2 L1:         lod     r2, b         sto     r2, a L2:     .....

여기에서 살펴보면 점프 인스트럭션이 두 개씩 필요하지 않다.         lod      r2, a         cmp    r2, b, 4         /*  r2<=b?  */         jmp    L1         lod     r2, b         sto     r2, a L1:     .....

11.3.3 전체 최적화 예 cmp r1, a, 2 /* 점프 */ jmp L1 cmp 0, 0, 0 jmp L2         lod     r1, b         add     r1, c         sto     r1, t1      /* 로드/저장  */         lod     r1, t1         sub     r1, a         sto     r1, t2      /*   로드/저장  */         lod     r1, t2         sto     r1, a         sub     r1, 0      /*   대수적인 변환  */         sto     r1, b L2:      ......

최적화한 최종 결과는 아래와 같다.         cmp    r1, a, 5         /*  r1>=a 면 점프  */         jmp    L2         lod     r1, b         add    r1, c         sub    r1, a         sto     r1, a         sto     r1, b L2:     ........

제 11 장 끝