코드 최적화 : 기본 블록 및 흐름 그래프

코드최적화

- 주어진 코드에 대해 동등한 의미를 가지면서 실행 시간을 줄이거나 메모리를 줄이는 것

- 최적화는 효과가 가장 좋다는 뜻인데, 가장 효과가 좋은 코드를 만들기는 어려운 일

- 기존의 방법보다 계산 횟수를 줄이거나 실행 시간을 더 짧게, 혹은 기억 용량을 더 적게

 

코드 최적화 분류

최적화가 적용되는 프로그램의 영역

- 지역 최적화, 전역 최적화, 프로시저 간 최적화

 

기능적인 측면

- 실행 시간 최적화와 메모리 최적화

 

최적화가 많이 이뤄지는 부분

- 루프 최적화와 단일문 최적화

 

목적 기계의 의존성

- 기계 독립적 최적화, 기계 종속적 최적화

 

 

핍홀 최적화

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

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

- 중복 명령어 제거, 도달 불가능한 코드 제거

- 제어 흐름 최적화, 대수학적 간소화, 세기 감축, 하드웨어 명령어 사용

 

지역 최적화

- 부분적인 관점에서 일련의 비효율적인 코드를 구분해내고 좀 더 효율적인 코드로 만드는 것

- 코드를 분기해 나가거나 들어오는 부분이 없는 기본 블록 내에서 최적화를 수행하여 상대적으로 쉽게 수행

- 기본 블록은 어떠한 제어 흐름도 가지지 않으므로 분석이 거의 필요 없음

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

 

루프 최적화

- 한 루프 안에서의 최적화, 루프 내부 코드에 대해 계산의 복잡도를 줄이는데에 관심

- 많은 기법이 흐름 그래프에서 루프를 찾는데 많은 시간을 보냄

- 루프 최적화 기법에는 코드 이동, 세기 감축, 귀납 변수 최적화,

- 루프 융합, 루프 교환, 루프 전개 등

 

전역 최적화

- 기본 블록을 넘어서지만 하나의 프로시저 내에서 일련의 비효율적인 코드를 구분해내고 좀 더 효율적인 코드로 만드는 방법

- 더 많은 정보와 비용이 필요하니 수행하기 어려우나 지역 최적화보다 효과가 훨씬 좋음

- 자료 흐름 분석이라는 기법을 사용, 이는 프로그램 안에서 사용되는 변수의 통로(path)에 관한 정보를 수집해서 처리하는 과정

- 전역 최적화 기법에는 전역적 공통 부분식 제거, 상수 폴딩, 도달 불가능한 코드 제거 등

 

프로시저 간 최적화

- 한 프로시저의 한계를 넘어서 전체 프로그램에 적용되는 최적화

- 매개변수 전달 방법, 비지역 변수의 참조, 서로 호출 가능한 모든 프로시저 정보를 동시에 구하는 작업 등이 관련되기 때문에 구현하기가 더욱 어려움

- 컴파일러는 컴파일러가 생성한 정보를 이용하여 최적화를 수행하는 링커 없이는 프로시저 간 최적화 수행 불가

- 많은 컴파일러가 그래서 안하거나 기본적인 것만 함

 

기계 종속적 최적화

- 기계의 특성에 따라..

- 중복된 LOAD 명령어 제거, 효율적인 명령어 선택,

- 레지스터 할당, 레지스터 배정 등

---

지역, 전역, 프로시저 간, 루프 최적화는 전체 프로그램을 기본 블록 단위로 분할하여 최적화

- 기본 블록 안에서 최적화 시 지역 최적화

- 기본 블록을 노드로 가진 흐름 그래프를 만들고 흐름 그래프에서 자료의 흐름을 분석

- 전역, 프로시저 간, 루프는 흐름 그래프와 자료 흐름 분석 등을 이용

 

기본 블록

- 지역 최적화의 기본 단위

- 제어가 시작점으로 들어와서 끝점으로 나갈 때까지 정지나 분기의 가능성이 없는 연속적인 코드들의 집합

t1 = a + b t2 = a * b t3 = t1 * 5

이 경우, 중간에 제어가 정지되거나 분기되지 않으니 하나의 기본 블록임

 

기본 블록은 리더와 다음 리더 이전에 나타내는 모든 코드로 구성

-> 먼저 리더를 찾아야 함

 

리더

1. 프로그램의 시작 문장

2. 조건부 분기 또는 무조건 분기의 목적지에 있는 문장

3. 조건부 분기 바로 다음에 위치하는 문장

 

#include <stdio.h>

int main(void)
{
    int mult = 1, i = 1, n = 0;
    
    scanf("%d", &n);
    
    while( i <= n )
    {
        mult *= i;
    }
    
    printf("%d", mult);
    
    return 0;
}

이런 코드가 있을 때, 3-주소 코드는

 

1. mult = 1
2. i = 1
3. n = 0
4. scanf(&n)
5. if n > i goto 11.
6. t1 = mult * i
7. mult = t1
8. t2 = i + 1
9. i = t2
10. if i <= n goto 6
11. printf(mult)
12. halt

이렇게 됨

 

리더 찾기

1. 시작 문장

6. 조건 분기 문장 다음 분장이기도 하고 10번의 목적지

11. 조건 분기 다음이고 5번 목적지

 

기본 블록을 구하면

1. mult = 1 2. i = 1 3. n = 0 4. scanf(&n) 5. if n > i goto 11.

6. t1 = mult * i 7. mult = t1 8. t2 = i + 1 9. i = t2 10. if i <= n goto 6

11. printf(mult) 12. halt

 

제어 흐름 그래프와 DAG

- 제어 흐름 그래프 : 최적화에 이용하기 위해 기본 블록의 집합에 제어 흐름에 관한 정보를 추가해서 만든 유향 그래프

- 흐름 그래프는 노드는 기본 블록이고 간선은 조건 분기와 무조건 분기를 나타냄

- 흐름 그래프는 모든 제어 흐름의 정보를 포함, 수집된 정보는 전역 최적화 수행에 매우 중요

- 흐름 그래프에서 기본 블록 B에서 C로 간선을 추가하는 방법

    - B의 마지막 문장에서 C의 첫번째 문장으로 조건 분기 혹은 무조건 분기가 존재

    - 프로그램의 실행 순서 상 B바로 다음에 C가 나타나며 이때 B의 마지막 문장이 무조건 분기로 끝나지 않는다 (위의 조건이 우선됨, 즉 C로 무조건 분기 시 만든다는 뜻)

    - 이 경우 B는 C의 선행자 C는 B의 계승자. 마지막으로 진입 노드와 진출 노드 추가

 

이런식으로 그려짐

 

 

루프

- 루프의 입구는 단 하나이며, 루프 밖에서 루프 안으로 도달하기 위해 항상 먼저 지나는 노드가 입구

- 루프 안의 모든 노드는 강하게 연결되어 있음

 

다른 루프를 포함하지 않는 루프 -> 내부 루프

흐름 그래프의 시작 노드에서 어떤 노드 n에 이르는 모든 통로가 d를 통과하는 경우,

노드 d는 노드 n을 지배하고 d dom n이라 표현

또한 모든 노드는 자기 자신을 지배하고, 루프의 진입 노드는 그 루프의 모든 노드를 지배함

 

트리를 이용하면 지배자 정보를 쉽게 나타낼 수 있는데, 지배자 트리 라고 함

시작 노드는 루트이고, 각 노드는 그 자손을 지배

---

자료 흐름 분석이 완료된 후 기본 블록에 대한 코드 생성 시, 각 블록에 대해

DAG(Diracted Acylic Graph, 비순환 유향 그래프)가 생성

- 기본 블록 내의 한 문장이 뒤의 문장에 사용되므로 값이 어떻게 계산되는지를 그림으로 나타내줌

- 주로 블록 내부에서 사용되지만 블록 외부에서 어떤 문장이 그 문장에서 계산한 값을 사용하는지 알아볼 수 있으므로 매우 중요

- 모든 산술식에 대한 노드를 가진다. 즉 내부 노드는 연산자를 나타내고 그 자식 노드는 피연산자를 나타냄

 

DAG 구성 방법

입력: 기본 블록

출력: 터미널 노드에 대한 레이블은 식별자 혹은 상수이고 내부 노드는 연산자가 되는 기본 블록에 대한 DAG

방법:

- 생성되는 노드는 1 혹은 2개으이 자식 노드를 가짐

- 1개의 노드를 가질 경우 왼쪽과 오른쪽 자식 노드로 구분

- 1 ~ 3 단계를 블록의 각 문장에 대해 차례로 수행 (x = y op z, x = op y, x = y 세 가지 중 하나로 가정)

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

 

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단계에서 찾은 부모 노드에 있는 식별자 리스트에 x를 첨가

 

DAG 그리기

x = (x + 1) * (x + 1)

t1 = x + 1
t2 = x + 1
t3 = t1 * t2
x = t3

위 방법을 쓰면

 

1단계에서 x와 1에 대한 터미널 노드를 생성

2단계에서 + 노드를 생성, 3단계에서 식별자 t1이 이 노드에 딸리도록 식별자 리스트에 첨가

 

t2 = x + 1인데, x랑 1 노드 이미 있으니 t2를 식별자 리스트에 추가

 

t1, t2는 이미 존재하므로 새로 생성하지 않고, *노드만 생성

t3를 식별자 리스트에 첨가

 

마지막은 치환문이니 노드 생성 안하고 x를 리스트에 추가

 

 

흐름 분석

- 좋은 코드를 생성하기 위해 코드 최적화기는 프로그램의 전체적인 정보를 모으고 이 정보를 흐름 그래프의 각 블록에 제공해야 함

- 즉 최적화에 이용하기 위해 제어 흐름에 관한 정보를 기본 블록의 집합에 모아야 함

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

- 프로그램 안에서 사용되는 변수의 통로에 관한 정보를 모으는 처리 과정으로 유효 변수, 공통 부분식 등에 대한 정보를 모으는 일을 함

- 최적화 컴파일러에서 자료 흐름 분석의 가장 중요한 용도는 최적화의 기회가 제공되는 위치를 파악하고, 어떤 지점에서 코드 변형을 적용하는 것이 안전한지를 증명하는 것

-> 정적 분석법

 

3-주소 코드 x = y * z에서 x를 정의, y와 z를 사용이라 부름

- x, y, z가 다음에 어디서 사용될지를 아는 건 매우 중요한 정보.. -> 다음 사용(next-use) 정보

- 그럼 다음에 사용될 y의 값은 프로그램 어디서 정의된 값인가? -> UD 체인(use-definition chaning) 계산을 수행해야 함

- 피연산자로 각 단순 변수가 나타날 때마다 UD 체인을 제공.. 프로그램의 어느 장소에 변수의 정의가 올바르게 나타나는지를 알려줌