코드 최적화 : 최적화 기법

핍홀 최적화 기법

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

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

- 연속적인 몇 개 명령어의 집합을 핍홀(peephole)또는 창(window)라고 부름

- 중복 명령어 제거, 도달 불가능한 코드 제거, 제어 흐름 최적화, 대수학적 간소화, 세기 감축, 하드웨어 명령어 사용 등

 

중복 명령어 제거

- 중복되는 LOAD나 STORE 명령문 제거

LOAD R1, x STORE x, R1

여기서 스토어는 제거 가능

어차피 x의 값이 R1에 적재되어 있기 때문

 

x = y; z = x + 10;

을 목적 코드로 변환하고 중복된 명령어가 있는지 찾기

LOAD R1, y STORE x, R1 LOAD R1, x ADD R1, 10 STORE z, R1

두번째 로드는 불필요함

 

도달 불가능한 코드 제거

불필요한 코드는 도달 불가능한 코드와 죽은 코드

- 죽은 코드는 지역 최적화 기법에서 설명

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

 

    if A = B then goto L3
    A = 2
    goto L5
L3: if A = B then goto L5
    A = 3
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

 

세기 감축

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

- 거듭 제곱은 곱셉, 곱셈은 덧셈, 나눗셈은 곱셈..

 

세기 감축하기 (^을 거듭 제곱이라 가정)

y = x ^ 2 => y = x * x y = x * 2 => y = x + x y = x / 5 => x * 0.2

 

하드웨어 명령어 사용

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

- 어떤 기계는 자동 증가와 자동 감소 모드는 피연산자로부터 값을 사용하기 전이나 후에 피연산자에 1을 증가시키거나 감소시킬 때 사용.. 하드웨어로 구현하기에 매우 큰 비용 절감

- 매개변수 전달에서 자료를 스택에 삽입하거나 삭제할 때도 명령어를 사용하여 품질을 향상

 

 

지역 최적화 기법

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

- 기본 블록 안에서 최적화가 이뤄짐

- 공통 부분식 제거, 복사 전파, 죽은 코드 제거, 상수 폴딩, 대수학적 간소화 등

 

공통 부분식 제거

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

- 공통 부분식이 한 번만 계산되도록 함으로써 코드를 효율적으로 만들 수 있는데 이러한 방법이 공통 부분식 제거

 

A = B + C + D;
E = B + C + F;
K = (B + C) * G;

B + C는 3개의 치환문에 공통

T1 = B + C;
A = T1 + D;
E = T1 + F;
K = T1 * G;

 

복사 전파

f = g 형태를 치환문이라 하는데, 이후 가능하면 f 대신 g를 사용하는 것

이후 안쓰이면 치환문을 삭제 (죽은 코드 제거로)

 

x = t3;
a[t2] = t5;
a[t4] = x;
goto B2

이를

x = t3;
a[t2] = t5;
a[t4] = t3;
goto B2

로 가능

 

죽은 코드 제거

어떤 변수가 특정 프로그램 지정 이후 전혀 사용하지 않는 값을 계산하는 문장

a[t2] = t5;
a[t4] = t3;
goto B2

위 예시가 이렇게 됨

 

상수 폴딩

컴파일을 할 때 상수를 포함하는 연산이 계산될 수 있으면 미리 계산해서 코드 줄이는 거

X = 3.14
Y = 2 * X

여기서 Y = 6.28로 변환됨

 

대수학적 간소화

- 핍홀 최적화에서 설명됨

 

 

루프 최적화 기법

전체 코드의 10%가 실행 시간의 90%를 차지하는 게 루프, 최적화에서 매우 중요

- while, do-while, for 등..

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

 

코드 이동

어떤 식의 값이 루프 수행 횟수와 상관없이 항상 같은 값(루프 불변)이라면 루프 수행 전에 미리 계산할 수 있도록 루프 내부로 들어가기 전의 루프 외부로 이동하는 것

 

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

를

fact = 2 * (p - q);
denom = sqrt(n) + n;
for(k = 1; k <= 1000; k++)
    c[k] = fact * (n - k + 1) / denom;

로 가능

 

세기 감축

- 핍홀 최적화에서 설명됨

 

귀납 변수 최적화

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

- 세기 감축으로 최적화 가능

- 이러한 변수로는 반복문 제어 변수 및 반복문 제어 변수에 특정 형태로 의존하는 다른 변수들

- 선정된 귀납 변수는 레지스터에 할당되어 보다 간단히 계산 가능

- 코드를 변경하는 데는 코드 이동도 포함될 수 있음

 

L1: j = j - 1
    t4 = 4 * j
    t5 = a[t4]
    if t5 > v goto L1

귀납 변수는 1씩 감소하는 t와 4씩 감소하는 t4

L1: j = j - 1
    t4 = t4 - 4
    t5 = a[t4]
    if t5 > v goto L1

이렇게 세기 감축 가능

 

루프 융합

루프의 오버헤드를 줄이기 위한 방법, 루프의 범위가 같은 경우 하나의 루프로 만드는 것

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];

이렇게 묶을 수 있음

 

루프 교환

내부 루프와 외부 루프를 교환하는 것

- 참조 지역성을 개선

for(j = 1; j <= 100; j++)
{
    for(k = 1; k <= 200; k++)
    {
        a[j, k] = j + k;
    }
}

이걸

for(k = 1; j <= 200; k++)
{
    for(j = 1; j <= 100; j++)
    {
        a[j, k] = j + k;
    }
}

로 변경

 

루프 전개

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

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

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

- store나 조건부 분기 명령은 선행 제어를 어렵게 하여 이런 경우 효과가 반감될 수 있음

- 루프 전개를 위해선 반복 횟수를 컴파일 시간에 알아야 함

 

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);
}

이렇게 가능

 

 

전역 최적화 기법

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

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

- 전역적 공통 부분식 제거, 상수 폴딩, 도달 불가능한 코드 제거

 

전역적 공통 부분식 제거

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

 

상수 폴딩

- 하나의 기본 블록 내에서 정의를 못 찾으면 이전 블록에서 찾아서 폴딩

 

도달 불가능한 코드 제거

- 예를 들어, 상수 폴딩 후 발견된 갈 수 없는 기본 블록에 대한 제거 ()

 

 

기계 종속적 최적화 기법

기계의 특성에 따라 아주 달라질 수 있음

- 중복된 LOAD 명령어 제거, 효율적인 명령어 선택, 레지스터 할당과 배정, 명령어 스케줄링 등

 

중복 명령어 제거

- 핍홀 최적화에서 설명됨

 

효율적인 명령어 선택

- 동일한 기능을 가진 더 효율적인 명령어로 대치함으로써 최적화

소스코드  x = x + 1에 대한 명령어는..

LOAD R1, x

ADD R1, 10

STORE x, R1

- 이와 같은 명령어에 대해 컴퓨터가 레지스터나 메모리에서 1을 증가시키는 INC 명령어를 가진다면?

INC x

- 로 대치 가능

 

레지스터 할당과 배정

목적 코드의 생성에서 중요한 고려 대상 중의 하나는 레지스터를 어떻게 이용하느냐 하는 것

레지스터가 더 빠르니까 중요. 저정과 로드를 위한 명령이 필요 없어짐, 하지만 레지스터는 극히 한정, 레지스터 할당 방법이 문제가 됨

 

레지스터 할당 방법은 지역적 할당 방법과 전역적 할당 방법이 있음

지역적 할당 방법

- 프로그램을 기본 블록으로 분할했을 때 각 기본 블록 내에서 변수를 레지스터에 할당하는 방법

전역적 할당 방법

- 전체 프로시저를 고려하여 할당

 

레지스터 할당 방법은 그래프 착색 방법으로 NP 완전 문제라 경험적인 방법에 의해 할당해되 전역적으로 잘 사용되는 자료는 되도록 레지스터에 넣어두는 편이 좋고, 지역적으로는 한 번 레지스터로 꺼내온 자료를 되도록 그곳에 보관하고 이용하는 편이 좋다

 

명령어 스케줄링

- 식의 연산 순서 변경에 의해 연산이 임시 결과를 저장하거나 로드하는 횟수를 최소화

- 임시 변수 기억 공간을 절약하고 효율적인 코드를 생산

 

하나의 레지스터로 효율적인 명령어 만들기

A * B - C * D를 계산하는데 하나의 레지스터 R0만을 이용할 수 있고, 일반적인 연산자 우선순위라 가정하면 다음과 같은 8개의 명령을 가짐

LOAD R0, A MULT R0, B STORE temp1, R0 LOAD R0, C MULT R0, D STORE temp2, R0 LOAD R0, temp1 SUBT R0, temp2

식의 순서를 변경하여 효율적인 명령어를 만들면?

 

A * B가 계산되기 전에 C * D를 먼저 계산하게 하면

LOAD R0, C MULT R0, D STORE temp1, R0 LOAD R0, A MULT R0, B SUBT R0, temp1