Optimization

Directed Acyclic Graph (DAG)

자료 흐름 분석이 완료된 후 기본 블록에 대한 코드를 생성할 때, 각 블록에 대해 DAG(directed acyclic graph)

생성하여 활용한다.

● DAG는 값이 어떻게 계산되는지를 그림으로 나타내준다.

● DAG는 주로 블록 내부에서 사용되지만, 블록 외부에서 어떤 문장이 그 문장에서 계산한 값을 사용하는지

      알아볼 수 있으므로 매우 중요하다.

 

DAG는 모든 산술식에 대한 노드를 가진다.

● 내부 노드(interior node)는 연산자를 나타내고 그 자식 노드는 피연산자를 나타낸다.

● 터미널 노드는 id나 constant이고 중간 노드는 연산자이다.

● 노드 옆에 여러 개의 id를 놓을 수 있으며, 이는 노드의 계산 결과를 이 id들이 공유함을 나타낸다.

 

 

[알고리즘] DAG

● [입력] 기본 블록

● [출력] 터미널 노드 레이블은 id 혹은 constant, 내부 노드는 op인 기본 블록에 대한 DAG

● [방법]

*생성되는 노드는 1개나 2개의 자식 노드를 가지게 된다.

   1개의 자식 노드를 가질 경우 ‘왼쪽’과 ‘오른쪽’ 자식 노드로 구분된다.

* x = y op z, x = op y, x = y 세 가지 중 하나의 3-주소 코드가 주어졌다고 가정한다.

* if i <= 20 goto _ 와 같은 경우에 는 x = y op z에서 x가 정의되지 않은 것으로 간주한다.

 

DAG 구성은 다음 1-3단계를 블록의 각 문장에 대해 차례로 수행하면 된다.

 

1. x = y op z의 경우에는 만약 node(y)와 node(z)가 정의되어 있지 않다면 터미널 노드 y와 z를 생성한다.

2.

      ● x = y op z의 경우에는 왼쪽 자식이 node(y)이고 오른쪽 자식이 node(z)이면서 똑같은 노드 op가 존재하는

           지 알아보고, 만약 존 재하지 않으면 새 노드 node(op)를 생성한다. 이때 부모 노드는 이미 만들어진 노드를

           찾거나 아니면 새롭게 생성되는 노드가 된 다.

      ● x = op y의 경우에는 node(y) 하나만을 자식으로 가지고 있는 노드 op가 존재하는지 알아보고, 만약 존재하지

          않으면 새 노드를 생성한다. 이때 부모 노드는 이미 만들어진 노드를 찾거나 아니면 새롭게 생성되는 노드가 된다.

      ● x = y의 경우에는 새로운 노드를 생성하지 않는다.

3. 2단계에서 찾은 부모 노드에 있는 id 리스트에 x를 첨가한다.

 

 

Example

치환문 x = (x + 1) * (x + 1)에 대해 3-주소 코드로 변환하고 [알고리즘]를 적용 하여 DAG를 그려보자.

 

3-address code

t1 = x + 1

t2 = x + 1

t3 = t1 * t2

x = t3

 

 

Flow Analysis (간략하게만 보고 넘어가기)

 

Code optimizer:

● 프로그램의 전체적인 정보를 모으고, 이 정보를 흐름 그래프의 각 블록에 제공

● 최적화에 이용하기 위해 제어 흐름에 관한 정보를 기본 블록의 집합에 정리

 

자료 흐름 분석: 프로그램이 실행되었을 때 어떤 일이 발생할지 추론하여 발견하는 것

● 즉 프로그램 안에서 사용되는 변수의 통로에 관한 정보를 모으는 처리 과정

● 유효 변수(live variables), 공통 부분식 등에 대한 정보를 모으는 일을 한다.

 

정적 분석법(static analysis):

● 최적화의 적용되는 위치를 파악하고,

● 어떤 지점에서 코드를 변경했을 때 안전한지 여부를 증명하는 것

 

변수 값이 다음에 언제 사용될지를 아는 것은 좋은 코드를 생성하는 데 필수적

 

3- 주소 코드 x = y * z에서

● x를 정의(define), y와 z를 사용(use)이라고 부른다

● 변수 x, y, z가 다음에 어디서 사용될지를 아는 것은 매우 중요한 정보

● 어떤 변수가 다음에 어디서 사용될 것인가를 다음 사용(next-use) 정보라 한다.

 

그럼 다음에 사용될 y의 값은 프로그램 어디서 정의된 값인가?

● 이 질문의 답을 구하려면 ‘UD 체인(use-definition chaining)’ 계산을 수행해야 한다.

● 이 분석 방법은 피연산자로 각 단순 변수가 나타날 때마다 해당하는 UD 체인을 제공한다.

      ○ UD 체인은 프로그램의 어느 장소에 변수의 정의가 올바르게 나타나는지를 알려준다.

 

 

Peephole Optimization

 

Peephole (window): 연속적인 명령어들의 집합

Peephole optimization:

     ● 몇 개의 연속적인 명령어를 하나의 명령어나 더 짧은 명령어로 변환

     ● 일반적으로 목적 코드가 생성된 다음 수행

 

중복 명령어 제거

중복되는 로드(LOAD) 명령문이나 저장(STORE) 명령문을 제거하는 방법

 

예시)

LOAD R1, x     // x을 R1에 적재한다.

STORE x, R1  // R1을 x에 저장한다.

 

저장 명령어를 삭제할 수 있다.

x의 값이 이미 레지스터 R1에 적재되어 있기 때문이다.

 

 

Example

다음 목적코드에 대해 중복된 명령어가 있는지 찾아보자.

 

LOAD R1, y

STORE x, R1

LOAD R1, x

ADD R1, 10

STORE z, R1

 

R1 = y   ( <- )

ㅌ = x   ( -> )

R1 = x   ( <- )   LOAD R1, x 를 제거하기

 

도달 불가능한 코드 제거

불필요한 코드(useless code)

● 도달 불가능한 코드

● 죽은 코드

 

도달 불가능한 코드는 무조건 분기 문장 바로 다음에 오는 라벨이 없는 명령어 같은 것으로, 이는 도달할 수 없기

때문에 제거할 수 있다.

 

Example

다음 3-주소 코드에 있는 도달 불가능한 코드를 제거해보자.

 

       if A = B then goto L3

       A = 2

       GOTO L5

L3: if A = B then goto L5

       A = 3

L5: 

 

L3 라벨에서 무조건 A = B 이기 때문에 L5 으로 무조건 이동한다.

따라서 라벨이 없는 명령어로 A = 3 제거하기

 

제어 흐름 최적화

중간 코드 생성은 분기에 대한 분기, 조건 분기에 대한 분기, 분기에 대한 조건 분기를 생성하는데 이러한 불필요한

분기들을 제거할 수 있다.

다음 코드를 살펴보자.

 

       goto L5

              ⋮

L5 : goto L1

 

이 코드는 다음과 같이 변환할 수 있으며, 이렇게 함으로써 실행 시간을 줄일 수 있다.

 

       goto L1

             ⋮

L5 : goto L1

 

대수학적 간소화

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

x = y + 0 ⇒ x = y (덧셈의 항등 법칙)

x = 0 + y ⇒ x = y (덧셈의 항등 법칙)

x = y – 0 ⇒ x = y (뺄셈의 항등 법칙)

x = y * 1 ⇒ x = y (곱셈의 항등 법칙)

x + y ⇒ y + x (덧셈의 교환 법칙)

 

교환 법칙을 만족하는 연산자를 필요할 때마다 적용하여 식을 간소화할 수 있다.

예를 들어 a = 3 * b / 3은 *가 교환 법칙을 만족하여 a = b * 3 / 3이므로 a = b * 1이 되고 결국 a = b가 된다.

 

세기 감축 (strength reduction)

수행 비용이 높은 연산자를 수행 비용이 낮은 연산자로 대체하는 것

거듭 제곱 연산자는 곱셈 연산자로, 곱셈 연산자는 덧셈 연산자로, 나눗셈 연산자는 곱셈 연산자로 바꾼다.

 

Example

다음 문장에 대해 각각 세기 감축을 해보자.

y = x ^ 2   =>  y = x * x

y = x * 2   =>  y = x + x

y = x / 5   =>  y = x * 0.2 (곱셈이 훨씬 효율적)

 

x * 3 = x + x + x    <=  이거는 다루지 않음(x * 2 만 알아두기)

 

하드웨어 명령어 사용

 

● 어떤 특정 연산을 효율적으로 구현하기 위한 하드웨어 명령어 포함

● 어떤 기계는 자동 증가(auto-increment)와 자동 감소(auto-decrement) 모드는 피연산자로부터 값을

     사용하기 전이나 후에 피연산자에 1을 증가시키거나 감 소시킬 때 사용하는데, 하드웨어로 구현하기 때문에

     매우 큰 비용을 절감

 

 

Local Optimization

 

지역최적화Local Optimization

● 부분적인 관점에서 비효율적인 코드를 구분해내고 좀 더 효율적인 코드로 개선하는 방법

● 기본적으로 기본 블록 안에서 최적화가 이뤄짐

 

공통 부분식 제거

● 공통 부분식은 프로그램에서 공통된 부분이 여러 번 나타나는 경우

● 공통 부분식이 한 번만 계산되도록 처리

 

 

Example

다음 치환문에서 공통 부분식을 제거해보자.

A = B + C + D;

E = B + C + F;

K = (B + C) * G;

 

B + C 부분이 공통으로 들어가는 것을 알 수 있음.

따라서 T1 = B + C 저장한다.

A = T1 + D;

E = T1 + F;

K = T1 * G;

 

 

복사 전파

   ● 치환문 f = g가 나타난 이후에 가능하면 f 대신에 g를 사용하는 것.

   ● 즉 치환문을 삭제하고 삭제된 치환문의 l-값 대신에 r-값을 사용하는 방법

 

Example)

x = t3;

a[t2] = t5;

a[t4] = x;

goto B2;

 

a[t4] = t3; 으로 변경한다.

 

죽은 코드 제거: 어떤 변수가 특정 프로그램 지점 이후 전혀 사용하지 않는 값을 계산하는 문장을 말한다

 

Example) 다음 코드에서 죽은 코드를 제거해보자.

x = t3;

a[t2] = t5;

a[t4] = t3;

goto B2; 

 

x = t3; 을 제거하면 된다.

 

상수 폴딩

컴파일 시간에 상수를 포함하는 연산이 계산될 수 있으면 계산을 미리 함으로써 코드를 줄이는 방법

 

Example) 다음 치환문에서 상수 폴딩을 해보자.

X = 3.14;

Y = 2 * X;

 

Y = 6.28; 으로 바로 변환하는 것임

 

 

Loop Optimization 

 

루프 최적화Loop Optimization

● 실행 시간의 대부분을 차지하므로 최적화에서 매우 중요한 부분

● 코드 이동, 세기 감축, 귀납 변수 최적화, 루프 융합, 루프 교환, 루프 전개

 

코드 이동 루프 수행 횟수와 상관없이 항상 같은 값을 가진 루프 불변(loop invariant)이 있는 경우,

루프 불변을 그 루프의 바로 전 위치로 이동

 

 

Example

 

다음 반복문에서 코드 이동을 해보자.

for(k = 1; k ＜= 1000; k++)      

      c[k] = 2 * (p - q) * (n - k + 1) / (sqrt(n) + n);

 

(p - q)랑 (sqrt(n) + n) 를 루프 밖으로 빼서 변수로 설정해가지고 하면 좋을듯 하다.

 

a = p - q;

b = sqrt(n) + n;

f =  n - 1;

for(k = 1; k ＜= 1000; k++)

      c[k] = 2 * a * (f - k) / b;

 

다른 방법으로 ...

 

a = p - q;

b = sqrt(n) + n;

f =  n + 1;

d = 2 * a / b;

for(k = 1; k ＜= 1000; k++)

      c[k] = d * (f - k);

 

와 같은 방법도 존재한다.

 

 

귀납 변수: 루프를 돌 때마다 값이 일률적으로 변하는 변수

 

귀납 변수 최적화

● 세기 감축으로 최적화할 수 있다.

      ○ ex) 반복문 제어 변수, 반복문 제어 변수에 특정 형태로 의존하는 변수들

● 선택된 귀납 변수는 레지스터에 할당되어 보다 효율적으로 계산 가능

 

 

Example

 

3-주소 코드의 기본 블록에 대해 귀납 변수 최적화를 해보자.

L1 : j = j - 1

       t4 = 4 * j

       t5 = a[t4]

       if t5 ＞ v goto L1 

 

t4 = 4 * j

L1 : t4 = t4 - 4

        t5 = a[t4]

         if t5 > v goto L1

 

루프 융합

● 루프의 오버헤드를 줄이기 위한 방법

● 루프의 범위가 같을 경우, 여러 개의 루프를 하나의 루프로 만듬

 

Example) 다음 문장에 대해 루프 융합을 해보자.

 

for (j = 1; j ＜= 100; j++)

      a[j] = b[j] + c[j];

for (j = 1; j ＜= 100; j++)

      b[j] = 5 + c[j];

 

for(j = 1; j < = 100; j++)

      a[j] = b[j] + c[j];

      b[j] = 5 + c[j];

 

 

루프 교환

● 내부 루프와 외부 루프를 교환

 

Example) 다음 문장에 대해 루프 교환을 해보자.

for (j = 1; j ＜= 100; j++)

{

      for (k = 1; k ＜= 200; k++)

      {

            a [j,k] = j + k;

      }

}

 

위 경우에는 row major 일 경우 효율적인 루프문이다.

column major 일 경우를 고려하여 루프 교환을 하면 아래와 같다.

 

for (k = 1; k ＜= 100; k++)

{

      for (j = 1; j ＜= 200; j++)

      {

            a [j,k] = j + k;

      }

}

 

 

루프 전개

● 루프의 계산을 빠르게 하기 위해 루프를 펼치는 방법

● 증가와 조건 검사의 횟수가 감소하기 때문에 수행되는 명령어의 수가 줄어듦

      ○ 제어 변수의 최종 값을 증가시킬 수도 있고, 제어 변수의 값을 바꿔서 구현할 수도 있음

      ○ store라든가 조건부 분기 명령(conditional jump)은 선행 제어를 어렵게 하므로 이런 경우 효과가

           반감될 수 있음

 

 

Example

다음 문장에 대해 루프 전개 해보자.

 

int x;

for (x = 0; x ＜ 100; x++)

{

      delete(x);

}

 

루프 전개는 다음과 같다

 

int x;

for(x = 0; x < 100; x +=5)

{

      delete(x);

      delete(x + 1);

      delete(x + 2);

      delete(x + 3);

      delete(x + 4);

}

 

 

Global Optimization 

 

전역 최적화 기법

● 프로그램의 전체적인 흐름 분석을 통해 좀 더 효율적인 코드로 만드는 방법

● 지역 최적화와는 달리 기본 블록 간 정보와 흐름 그래프를 이용하고 프로그램 의 전체적인 흐름 분석을 통한

      최적화 기법

 

전역적 공통 부분식 제거

기본 블록 간에 나타나는 공통 부분식에 대해서 단 한 번만 계산하도록 함으로써 코드를 개선

 

 

*좀 더 최적화하면 세기 감축이 가능하다. x3 = a / 5 + t를 x3 = a * 0.2 + t로 최적화할 수 있다.

 

 

상수 폴딩

하나의 기본 블록 내에 어떤 변수에 대한 정의가 존재하지 않는다면?

이 블록으로 도달할 수 있는 이전 블록 어 딘가에 그 변수에 대한 정의가 있을 것.

이러한 특성을 이용하여 기본 블록 간 상수 폴딩을 수행

 

 

도달 불가능한 코드 제거

흐름 그래프의 입구에서부터 도달할 수 없는 기본 블록은 제거가 가능

앞서 상수 폴딩 예시의 경우에는 제어문 이 항상 true이므로 false로 가는 것을 제거할 수 있다.