컴파일러 최적화
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
컴파일러 최적화는 컴파일러가 소스 코드를 기계어로 변환하는 과정에서 코드의 실행 속도, 크기, 전력 소비 등을 향상시키기 위해 수행하는 기술이다. 1960년대부터 발전해온 이 기술은 적용 범위에 따라 피홀, 로컬, 루프, 프로시저 간 최적화 등으로 나뉘며, 언어 및 기계 의존성, 고수준/저수준 표현 방식에 따라서도 분류된다. 컴파일러 최적화는 대상 머신의 CPU 아키텍처, 메모리 구조, 코드의 용도 등 다양한 요인에 영향을 받으며, 중복 제거, 코드 크기 감소, 분기 줄이기, 지역성, 메모리 계층 고려 등 다양한 기법을 사용한다. 루프 최적화, 데이터 흐름 최적화, 정적 단일 할당 기반 최적화, 코드 생성 최적화, 함수형 언어 최적화 등 다양한 최적화 기법이 존재하며, 프로그램 표현, 최적화의 한계와 문제점, 프로시저 간 최적화, 최적화에서의 프로그램 표현, 최적화의 한계와 문제점 등이 존재한다.
더 읽어볼만한 페이지
- 컴파일러 최적화 - 데이터 흐름 분석
데이터 흐름 분석은 프로그램의 제어 흐름 그래프를 바탕으로 변수의 정의, 사용, 생존 여부를 분석하며, 전이 함수와 결합 연산을 통해 데이터 흐름 정보를 계산하고 반복적으로 갱신하여 해를 구한다. - 컴파일러 최적화 - 느긋한 계산법
느긋한 계산법은 계산 결과가 필요할 때까지 계산을 늦추는 방식으로, 함수형 프로그래밍 언어에서 유용하게 사용되며 무한 데이터 구조를 다루거나 불필요한 계산을 피하는 데 효과적이다. - 프로그래밍 언어 구현 - 어셈블리어
어셈블리어는 사람이 이해하기 쉬운 니모닉 기호로 기계어 명령을 표현하는 저수준 프로그래밍 언어로서, 각 프로세서마다 사양이 다른 어셈블리어가 존재하며 하드웨어 직접 제어, 성능 최적화, 저수준 시스템 프로그래밍 등에 활용된다. - 프로그래밍 언어 구현 - 컴파일러
컴파일러는 고급 프로그래밍 언어로 작성된 소스 코드를 컴퓨터가 이해할 수 있는 저급 언어로 변환하는 프로그램으로, 어휘 분석, 구문 분석, 의미 분석, 최적화, 코드 생성 등의 단계를 거쳐 목적 코드를 생성하며, 네이티브 컴파일러, 크로스 컴파일러 등으로 분류되어 다양한 분야에서 활용된다. - 컴파일러 구성 - 구문 분석
구문 분석은 입력 데이터를 구조화된 형태로 변환하는 과정으로, 컴퓨터 언어에서는 소스 코드를 분석하여 추상 구문 트리를 생성하고, 자연어 처리에서는 텍스트의 문장 구조와 의미를 분석한다. - 컴파일러 구성 - 바이너리 재컴파일러
| 컴파일러 최적화 | |
|---|---|
| 일반 정보 | |
| 유형 | 컴파일러 기술 |
| 목표 | 생성된 코드의 품질 향상 |
| 방법 | 코드 변환 및 분석 |
| 대상 | 실행 속도 코드 크기 전력 소비 |
| 개요 | |
| 설명 | 컴파일러 최적화는 컴파일러가 코드를 더 효율적으로 실행되도록 수정하는 프로세스이다. |
| 목표 | 실행 시간 단축 메모리 사용량 감소 전력 소비 감소 |
| 최적화 기법 | |
| 종류 | 인라인 확장 루프 풀기 공통 하위 표현식 제거 상수 폴딩 죽은 코드 제거 레지스터 할당 명령어 스케줄링 |
| 최적화 수준 | |
| 설명 | 컴파일러는 일반적으로 다양한 수준의 최적화를 제공하며, 각 수준은 성능 향상과 컴파일 시간 사이의 절충점을 나타낸다. |
| 예시 | `-O0`: 최적화 없음 (디버깅에 유용) `-O1`: 기본 최적화 `-O2`: 고급 최적화 `-O3`: 공격적인 최적화 (코드 크기 증가 가능성 있음) |
| 장단점 | |
| 장점 | 프로그램 성능 향상 리소스 사용량 감소 |
| 단점 | 컴파일 시간 증가 코드 디버깅 어려움 증가 특정 최적화는 플랫폼에 따라 다른 결과를 초래할 수 있음 |
| 추가 정보 | |
| 관련 주제 | 프로파일링 정적 분석 동적 컴파일 |
2. 역사
1960년대 초기 컴파일러들은 코드를 올바르고 효율적으로 컴파일하여 컴파일 시간을 최소화하는 데 주력했다. 초기의 저명한 최적화 컴파일러 중 하나는 1970년 BLISS의 것이었으며, 1975년 최적화 컴파일러의 디자인에 기술되었다. 1980년대에는 컴파일러 최적화 기술이 발전하여 어셈블리어로 프로그래밍할 필요가 없을 정도로 효율성이 높아졌다.
최적화는 크게 소스 프로그래밍 언어에 가까운 표현의 중간 언어에 대해 수행되는 고수준 최적화와 기계어에 가까운 표현의 중간 언어에 적용되는 저수준 최적화로 나뉜다.
3. 최적화의 종류
또한, 최적화 기법은 적용 범위(스코프)에 따라 분류할 수 있다. 스코프는 문 단위에서 프로그램 전체까지 다양하며, 일반적으로 범위가 좁을수록 구현은 쉽지만 효과는 작다.
'''적용 범위에 따른 분류'''
'''언어 및 기계 의존성에 따른 분류'''
3. 1. 적용 범위에 따른 분류
최적화 기법은 그 적용 범위(스코프)에 따라 분류할 수 있으며, 스코프는 문 단위에서 프로그램 전체까지 다양하다. 일반적으로 스코프가 좁은 기법일수록 구현은 쉽지만 효과는 작다.
적용 범위에 따른 분류 외에도 다음과 같은 두 가지 분류가 있다.3. 2. 언어 및 기계 의존성에 따른 분류
최적화는 소스 언어(프로그래밍 언어)에 가까운 표현의 중간 언어에 대해 수행되는 고수준 최적화와 기계어에 가까운 표현의 중간 언어에 적용되는 저수준 최적화로 분류된다.
최적화 기법은 그 "스코프"로 분류할 수 있는데, 문 단위에서 프로그램 전체까지 다양하다. 일반적으로 스코프가 좁은 기법이 더 넓은 것보다 구현이 용이하지만 효과는 작다.
최적화는 다음 두 가지로도 분류할 수 있다.
: 많은 고급 언어의 구문 요소와 추상화는 공통적이다. 분기(if, switch, case), 루프(for, while, repeat...until, do...while), 캡슐화(구조체, 객체) 등이 있다. 이 특징을 이용하여 언어에 의존하지 않는 최적화 기법을 이용할 수 있다. 하지만, 언어에 따라서는 어떤 종류의 최적화가 쉽거나, 반대로 어렵기도 하다. 예를 들어, C 언어나 C++(C++)는 포인터가 있기 때문에, 배열 접근 최적화가 어렵다. 반대로, 일부 언어에서는 함수가 부작용을 가질 수 없다. 이 때문에, 같은 인수로 같은 함수를 여러 번 호출하는 경우, 컴파일러는 이것을 최적화하여 한 번만 그 함수를 호출하고, 그 후에는 그 결과를 재사용할 수 있다.
: 추상적인 개념(루프, 객체, 구조체 등)에 관한 최적화는 컴파일러가 대상으로 하는 머신과는 관계없이 실시할 수 있다. 하지만, 효과적인 최적화의 많은 부분은 대상 플랫폼 특유의 기능을 고려한 것이다.
머신 의존적인 최적화의 구체적인 예로 레지스터에 0을 설정하는 방법을 들 수 있다. 가장 간단한 방법은 0이라는 상수(즉시 값)을 레지스터에 설정하는 것이다. 또 다른 방법으로는, 레지스터를 자신과의 XOR 연산 결과로 대체하는 방법이 있다. RISC의 경우, 두 가지 방법 모두 명령 길이와 실행 시간에 차이가 없다. 인텔 x86 계열 등에서는, XOR를 사용한 방법이 더 짧고 빠르다.
4. 최적화에 영향을 미치는 요인
컴파일러 최적화는 여러 요인에 의해 영향을 받는다.
- '''대상 머신 및 CPU 아키텍처'''
컴파일러가 생성하는 코드는 대상 머신(컴퓨터의 하드웨어) 특성에 크게 의존한다. CPU의 레지스터 수, RISC와 CISC 명령어 집합 구조, 파이프라인 구조, 기능 유닛 수 등이 최적화에 영향을 미친다. GCC는 머신 의존적인 요소를 변수로 만들어 최적화를 수행하는 대표적인 예이다.
- '''대상 머신의 메모리 구조'''
인라인 전개나 루프 전개와 같은 최적화 기법은 코드 크기를 증가시켜 참조의 지역성을 떨어뜨릴 수 있다. 자주 실행되는 코드가 캐시에 들어가지 않으면 성능이 크게 저하될 수 있다.
- '''생성된 코드의 용도'''
컴파일된 코드가 어떤 용도로 사용되는지에 따라서도 최적화 방식이 달라진다. 개발 과정에서는 컴파일 속도가 빨라야 하므로 최적화를 최소화하고, 디버깅을 쉽게 하기 위해 명령어 재배열을 하지 않는다. 반면, 특정 머신에서만 동작하는 소프트웨어는 해당 머신의 특성에 맞게 최대한 최적화할 수 있다.
4. 1. 대상 머신 및 CPU 아키텍처
대상 머신의 특성에 따라 적용 가능하고 적용해야 할 최적화가 달라진다. 경우에 따라 머신 의존적인 요소를 변수로 만들 수 있으며, 머신을 지정하는 변수에 따라 코드에 적용하는 최적화를 변경할 수도 있다. GCC는 그러한 기법을 채택한 예이다.- '''CPU의 레지스터 수'''
레지스터가 많을수록 성능 최적화가 더 용이해지는 경우가 있다. 레지스터가 많으면 지역 변수를 호출 스택 대신 레지스터에 할당할 수 있는 비율이 더 높아진다. 임시 결과를 레지스터에 보관함으로써 메모리 읽기/쓰기 횟수를 줄일 수 있다.
- '''RISC와 CISC'''
CISC 명령어 집합의 명령어 길이는 가변적인 경우가 많고, 명령어 수도 많으며, 각 명령어의 실행 간격도 일정하지 않다. RISC 명령어 집합은 명령어 길이가 고정되어 있고, 어드레싱 모드도 CISC보다 적으며, 각 명령어는 일정 간격으로 실행된다 (실행 시간은 반드시 일정하지 않음). 동일한 처리를 코드로 작성할 때 CISC가 RISC보다 다양하다. 컴파일러는 각 명령어와 명령어 조합에 따른 비용을 고려하여 코드를 생성한다 (명령어 선택).
- '''파이프라인'''
파이프라인은 CPU를 기능별로 분할하여 공장의 생산 라인처럼 배열한 것이라고 할 수 있다. 기본적인 파이프라인 단계는 명령어 읽기, 명령어 해독, 연산, 메모리 접근, 레지스터에 저장이다. 이를 통해 CPU의 각 부분이 서로 다른 명령의 서로 다른 처리를 할 수 있게 된다. 즉, 어떤 명령의 연산을 수행하는 동안 동시에 다른 명령을 해독할 수 있다. 파이프라인의 특정 단계에 있는 명령이 더 앞선 단계에 있는 미완료된 명령의 결과를 필요로 할 때, 파이프라인 해저드가 발생한다. 해저드는 파이프라인 정지(스톨)를 초래하며, 해저드가 해결될 때까지 CPU는 처리를 지연시킨다.
컴파일러는 의존 관계가 있는 명령어 그룹을 실행 결과에 영향을 미치지 않도록 주의하면서 재배치하여 스톨이 일어나기 어렵게 한다.
- '''기능 유닛의 수'''
일부 CPU는 여러 개의 ALU와 FPU를 갖추고 있어, 여러 명령을 동시에 실행할 수 있다. 동시에 실행할 수 있는 명령어 종류에는 제한이 있을 수 있으며, 각 유닛이 실행할 수 있는 명령어 종류에도 제한이 있을 수 있다. 이들은 파이프라인 충돌과 유사한 문제를 가지고 있다.
컴파일러는 이러한 경우에도 명령어를 적절히 배치하여 각 기능 유닛이 가능한 항상 동작하도록 스케줄링할 수 있다.
4. 2. 대상 머신의 메모리 구조
인라인 전개나 루프 전개 등의 기법은 코드의 크기를 증가시키고, 참조의 지역성을 손상시킨다. 빈번하게 실행되는 코드 덩어리가 캐시에 수용되지 않으면 성능은 극적으로 저하된다. 완전 연관이 아닌 캐시에서는 캐시 상에서의 충돌이 발생하기 쉽다. 컴파일러는 캐시 미스가 발생했을 경우의 페널티 정도를 알 수 있는데, 이러한 정보를 필요로 하는 것은 주로 일부 특수한 애플리케이션이다.4. 3. 생성된 코드의 용도
프로그래머는 애플리케이션 개발 중에 컴파일을 자주 하기 때문에 컴파일 속도는 빨라야 한다. 그래서 대부분의 최적화는 디버깅 중에는 수행되지 않는다. 또한 디버깅 중인 코드는 디버거로 단계별 실행을 하기 때문에, 명령을 재배열하는 최적화를 하면 디버깅이 어려워진다 (어떤 명령이 소스 코드의 어느 부분에 해당하는지 알기 어려워진다). 하지만 컴파일러 최적화를 수행하면서 발생하는 문제도 드물게 있으며, 이 경우에는 최적화된 코드로 디버깅을 할 수밖에 없다.패키지 소프트웨어는 보통 명령어 집합이 같은 CPU를 탑재한 여러 머신에서 실행될 것으로 예상된다. 이러한 머신들은 타이밍이나 메모리 등의 특성이 다르다. 따라서 코드를 특정 CPU에 맞게 최적화할 수는 없고, 가장 일반적인 CPU에 맞춰 최적화하면서, 다른 CPU에서도 어느 정도 성능을 낼 수 있도록 한다.
특정 머신에서 동작하는 것이 결정된 소프트웨어는 해당 머신에 맞게 최적화할 수 있다. 예를 들어, 병렬 컴퓨터나 벡터 컴퓨터용 병렬화 컴파일러가 있다.
5. 최적화 기법
컴파일러 최적화는 소스 언어(프로그래밍 언어)에 가까운 중간 언어를 대상으로 하는 고수준 최적화와 기계어에 가까운 중간 언어를 대상으로 하는 저수준 최적화로 나뉜다.
최적화 기법은 적용 범위(스코프)에 따라 분류할 수 있으며, 스코프는 문장 단위부터 프로그램 전체까지 다양하다. 일반적으로 범위가 좁은 기법은 구현이 쉽지만 효과는 작고, 범위가 넓은 기법은 구현이 어렵지만 효과는 크다.
- '''구멍 엿보기 최적화''': 컴파일러가 기계어를 생성한 후 수행하는 최적화이다. 인접한 몇 개의 명령어를 더 짧은 명령어로 대체하거나, 가능하다면 하나의 명령어로 대체한다. 예를 들어, 어떤 값에 2를 곱하는 경우, 시프트 명령이나 덧셈 명령(자신을 더하는 것)으로 바꾸어 더 빠르게 실행할 수 있다. (이는 연산자 강도 감소에 해당한다).
- '''루프 최적화''': for문과 같은 루프를 구성하는 문 블록에 대해 수행하는 최적화이다. 프로그램 실행 시간의 대부분은 루프 내에서 소요되므로, 루프 최적화는 성능에 큰 영향을 미친다.
- '''지역 최적화 (프로시저 내 최적화)''': 하나의 함수 정의 내의 정보만 고려하는 최적화이다. 분석은 비교적 간단하지만, 전역 변수나 함수 내에서 다른 함수를 호출하는 부분에 대해서는 최악의 경우를 가정해야 한다.
- '''프로시저 간 최적화 (프로그램 전체 최적화)''': 프로그램 소스 코드 전체를 분석하는 최적화이다. 더 많은 정보를 얻을 수 있어 효율적인 최적화가 가능하며, 인라인 전개와 같은 새로운 기법도 적용할 수 있다.
최적화 기법은 적용 범위 외에도 프로그래밍 언어 의존성 여부와 머신(CPU) 의존성 여부에 따라 분류할 수 있다.
- '''프로그래밍 언어 비의존/의존 최적화''': 많은 고급 언어는 분기(if, switch, case), 루프(for, while), 캡슐화(구조체, 객체) 등 공통적인 구문 요소와 추상화를 가진다. 이러한 특징을 이용하면 언어에 의존하지 않는 최적화가 가능하다. 그러나 C/C++처럼 포인터가 있는 언어는 배열 접근 최적화가 어렵고, 일부 언어에서는 함수가 부작용을 가질 수 없다는 제약 때문에 최적화가 쉬워지기도 한다.
- '''머신(CPU) 비의존/의존 최적화''': 추상적인 개념(루프, 객체, 구조체 등)에 관한 최적화는 대상 머신과 관계없이 수행할 수 있다. 그러나 대부분의 효과적인 최적화는 대상 플랫폼의 특수한 기능을 고려해야 한다.
머신 의존적인 최적화의 예로, 인텔 x86 계열 프로세서에서는 0을 레지스터에 설정할 때 XOR 연산을 사용하는 것이 더 빠르다. 이는 즉시 값을 디코딩할 필요가 없고, 내부 레지스터를 사용하지 않기 때문이다. 또한 XOR 명령은 레지스터 의존성에 따른 파이프라인 정지를 유발할 수 있지만, 자신과의 XOR 연산은 파이프라인을 정지시키지 않는다.
컴파일러 최적화의 주요 목적은 다음과 같으며, 이들은 때로는 서로 상충될 수 있다.
5. 1. 루프 최적화
주로 루프를 조작하는 최적화 기법으로, 다음과 같은 것들이 있다.- 귀납 변수 분석: 루프 내의 변수가 루프 변수의 간단한 식으로 계산되는 경우 (예: `j:= i*4`), 루프 변수의 갱신 시 동시에 그 변수도 갱신할 수 있다(예를 들어, `i:=i+1`이면 `j:=j+4`). 이는 일종의 연산자 강도 감소이며, 동시에 루프 변수를 다른 곳에 사용하지 않는다면 데드 코드 제거도 수반한다. 이 정보는 경계 검사 제거(후술)나 의존성 분석 등에도 이용된다.
- 루프 분할/분산: 하나의 루프를 복수의 동일한 인덱스 범위의 루프로 분할한다(각 루프에는 오리지널 루프 내의 처리의 일부가 들어간다). 루프 내에서 참조되는 데이터와 루프 내의 코드 양면에서 참조의 지역성을 높인다.
- 루프 융합/결합: 루프 회수가 같은 복수의 루프를 묶음으로써 루프에 의한 오버헤드를 저감한다.
- 루프 전치: ''while'' 루프를 등가인 ''do/while''이나 ''repeat/until'' 루프로 변환함으로써 조건 비교 회수를 줄인다. 통상, 루프 전에 조건문을 추가할 필요가 있으며, 코드의 크기는 증대하지만, 명령어 파이프라인을 스무스하게 하는 효과가 있는 경우도 있다. 또한, 컴파일 시에 초기 조건이 명확하고, 또한 부작용의 문제도 없는 경우, 최초의 조건문을 제거할 수 있다.
- 루프 교환: 중첩된 루프에서, 안쪽 루프와 바깥쪽 루프를 교체한다. 루프 변수군이 배열의 인덱스였을 경우, 이 최적화로 참조의 지역성을 높일 수 있는 경우도 있다(배열의 정렬 방식에 의존한다).
- 루프 불변 코드 이동: 매번, 어떤 값이 루프 내에서 계산되고, 매번 같은 값일 경우, 그것을 루프 전에 1회만 계산함으로써 최적화한다. 배열에 대한 루프에서 주소를 계산하는 식 등에서 특히 유효하다. 모든 코드가 루프 밖에서 계산할 수 있는 것은 아니므로, 루프 전치와 함께 실시하는 것이 일반적이다.
- 중첩 루프 최적화: 행렬의 곱셈 등은 메모리 액세스가 많고, 캐시 적중률도 나쁘다. 중첩 루프 최적화에서는, 루프 교환 등의 기법을 사용하여 캐시 적중률을 향상시킨다.
- 루프 반전: 루프 변수의 값의 변화하는 순서를 반전시킨다(예를 들어, 0부터 10이었던 것을 10부터 0으로 한다). 이는 미묘한 최적화이며, 의존성 분석을 생략하는 효과가 있거나, 다른 최적화가 가능해지는 등의 효과를 기대할 수 있다.
- 루프 전개: 루프 안의 코드를 복수 회 배치하여 루프 조건의 체크 회수를 줄이거나, 분기 회수를 줄임으로써 오버헤드를 저감시킨다. 루프를 완전히 전개하면 오버헤드는 제로가 되지만, 컴파일 시에 루프 회수가 명확하게 되어 있지 않으면 안 된다.
- 루프 분할: 하나의 루프를 복수로 분할하지만, 각 루프 안의 내용은 같고, 루프 변수의 범위가 달라지도록 한다. 예를 들어, 일반적으로 루프의 1번째 실행에서는 각종 처리가 여분으로 필요하게 되어 있는 경우가 있다. 이것을 1번째만 분할해 보면, 그 후의 루프에서는 각종 최적화가 가능하게 되는 경우가 있다.
- 루프와 조건문의 교체(Loop unswitching): 루프 내의 조건문을 밖으로 내보내고, 조건문의 then부와 else부에 원래 루프의 복사본을 둔다. 병렬성을 높이는 등의 효과가 있다.
5. 2. 데이터 흐름 최적화
데이터 흐름 최적화는 데이터 흐름 분석을 기반으로 수행되며, 특정 데이터의 특성이 제어 흐름 그래프 내의 제어 에지에서 어떻게 전파되는지에 따라 달라진다. 다음과 같은 기술이 있다.- 공통 부분식 제거
- : 예를 들어, `(a+b)-(a+b)/4`라는 식이 있을 때, `(a+b)`는 두 번 나타난다. 공통 부분식 제거는 `(a+b)`가 이 사이에 변경되지 않는다고 판단하여, 한 번만 계산하도록 최적화한다.
- 상수 폴딩과 상수 전파
- : 상수들로 구성된 식(예: `3 + 5`)을 컴파일 시에 계산 결과(`8`)로 대체한다. 최근의 언어 처리 시스템에서는 거의 항상 수행된다.
- 귀납 변수의 인식 및 제거
- 에일리어스 분류와 포인터 분석
- : 포인터가 있는 언어에서는, 변수를 포인터를 통해 참조하고 조작할 가능성이 있으므로 최적화가 어렵다. 이 때문에, 어떤 포인터가 어떤 변수의 에일리어스(별칭)인지 식별함으로써, 관련 없는 포인터를 무시하는 최적화를 수행한다.
5. 3. 정적 단일 할당 (SSA) 기반 최적화
정적 단일 할당(SSA) 형식으로 변환된 프로그램에 대해 수행되는 최적화 기법은 다음과 같다. SSA에서는 각 변수가 한 곳에서만 할당된다. SSA로 변환하지 않고도 최적화를 수행할 수 있지만, 다음 기법들은 SSA와 함께 사용할 때 가장 효과적이다.; 전역 값 넘버링(Global Value Numbering)
: 프로그램의 값 그래프를 생성하여 중복을 제거하고, 같은 식으로 계산되는 값을 찾는다. 공통 부분식 제거로는 불가능한 중복 제거가 가능하지만, 반대로 공통 부분식 제거로만 가능한 중복 제거도 있다.
; 희소 조건부 상수 전파(sparse conditional constant propagation)
: 상수 전파, 상수 폴딩, 데드 코드 제거를 변화가 없을 때까지 반복하는 것과 거의 같지만, 더 효율적이다. 이 최적화는 프로그램을 기호적으로 실행하고, 상수 값을 전파하며, 도달할 수 없는 부분을 제어 흐름 그래프에서 제거한다.
5. 4. 코드 생성 최적화
; 레지스터 할당: 가장 자주 사용되는 변수를 레지스터에 할당하여 빠르게 접근할 수 있도록 한다. 어떤 변수를 레지스터에 배치할지를 결정하기 위해 간섭 그래프(interference-graph)를 작성한다. 각 변수를 노드로 나타내고, 동시에 사용되는 두 변수 사이를 선으로 잇는다. 이 그래프에 차이틴의 알고리즘 등을 적용하여 색을 입혀, 같은 색상의 변수를 레지스터에 할당한다. 색칠이 실패하여 같은 색상의 변수 일부가 레지스터에 할당되지 못하게 된 경우, 색칠을 재시도한다.
; 명령 선택
: 풍부한 어드레싱 모드를 가진 CISC 아키텍처에서는 동일한 연산을 수행하는 여러 가지 방법이 존재하며, 각 기법에 따라 명령어가 완전히 다르다. 명령 선택은 저수준의 중간 표현을 명령어로 대체할 때 어떤 명령어를 사용하는 것이 가장 효율적인지를 판단하여 선택한다. 예를 들어, MC68000 계열 프로세서에서는 "lea 25(a1,d5*4), a0"와 같은 복잡한 어드레싱 모드가 사용되며, 한 명령어로 상당히 복잡한 연산이 수행된다.
; 명령 스케줄링
: 명령 스케줄링은 파이프라인 프로세서에서 중요한 최적화 기법이며, 파이프라인 위험의 발생을 최소화하기 위해 프로그램의 의미를 변경하지 않는 범위 내에서 명령의 순서를 재정렬하여 수행한다.
; 재실체화 (Rematerialization)
: 메모리에서 로드하지 않고 재계산을 수행하여 실행 시간을 절약한다. 이는 레지스터 할당 최적화와 동시에 수행된다. 재계산 비용과 메모리 접근 비용의 트레이드 오프에 따라 선택된다.
; 계산 재배치
: 선형 계획법에 기초하여 계산을 재배치함으로써 참조 지역성을 향상시키거나, 병렬성을 이끌어낸다.
; CPU 고유 명령 사용
: 확장 명령( MMX나 SSE 등)을 사용하는 기계어를 생성한다. 대신, 이러한 명령을 지원하지 않는 CPU에서는 동작하지 않게 된다.
5. 5. 함수형 언어 최적화
여기서 제시하는 최적화 기법은 함수형 언어 외에도 적용 가능한 경우가 많지만, LISP나 ML과 같은 함수형 프로그래밍 언어를 위해 개발된 기법이다.; 재귀 호출 제거
: 꼬리 재귀 알고리즘은 단순한 반복으로 변환할 수 있으며, 함수 호출의 오버헤드를 제거할 수 있다. 꼬리 재귀 제거라고도 부른다. 재귀는 비용이 많이 든다. 함수 호출은 호출 스택을 사용하고, 인수를 전달하는 오버헤드가 발생하며, 명령어 캐시가 플러시된다.
; 자료 구조 융합
: Haskell 등 함수형 언어에서의 자료 구조의 특징으로, 임시적인 자료 구조를 생성·사용하는 복수의 재귀 함수를 결합할 수 있어, 자료 구조 구축에 드는 시간을 절약할 수 있다.
; 람다 계산에서 콤비네이터 논리로의 변환
: 대부분의 함수형 언어는 계산 모델로서 람다 계산을 채택하고 있다. 하지만, 람다 계산에서의 식의 평가는 매우 복잡하며, 컴퓨터에 큰 부하를 준다. 대조적으로, 콤비네이터 논리의 식의 평가는 치환이라는 개념이 존재하지 않기 때문에 훨씬 간단하며 계산 부하를 줄일 수 있다.
5. 6. 기타 최적화
컴파일러 최적화는 크게 고수준 최적화와 저수준 최적화로 나뉜다. 고수준 최적화는 소스 언어(프로그래밍 언어)에 가까운 표현의 중간 언어에 대해 수행되고, 저수준 최적화는 기계어에 가까운 표현의 중간 언어에 적용된다.최적화 기법은 그 "스코프"로 분류할 수 있는데, 스코프는 문 단위에서 프로그램 전체까지 다양하다. 일반적으로 스코프가 좁은 기법이 더 넓은 것보다 구현이 용이하지만 효과는 작다. 스코프에는 다음과 같은 것들이 있다.
- '''구멍 엿보기 최적화''': 컴파일러가 기계어를 생성한 후에 수행되는 최적화이다. 인접한 몇 개의 명령어를 더 짧게, 경우에 따라 1개의 명령으로 대체할 수 있는지 검토한다. 예를 들어, 어떤 값에 2를 곱하는 경우, 시프트 명령이나 덧셈 명령(자신을 더하는)으로 바꾸는 것이 더 빨라지는 경우가 있다 (이것은 연산자 강도 감소이기도 하다).
- '''루프 최적화''': 루프를 구성하는 문 블록(예: for문)에 대해 최적화를 수행한다 (루프 불변량 코드 이동 등). 프로그램 실행 시간의 대부분은 어떤 루프 내에 있기 때문에 루프 최적화는 성능에 중대한 영향을 미칠 수 있다.
- '''지역 최적화, 프로시저 내 최적화''': 하나의 함수 정의 내의 정보만 고려하는 최적화이다. 분석의 수고가 줄어들지만, 전역 변수나 그 함수 내에서 다른 함수를 호출하는 부분에 대해 최악의 경우를 가정할 필요가 있다.
- '''프로시저 간 최적화, 프로그램 전체 최적화''': 프로그램의 소스 코드 전체를 분석하는 최적화이다. 더 많은 정보를 얻을 수 있으므로, 더욱 효율적인 최적화가 가능하다. 예를 들어 인라인 전개 기법을 사용하면, 함수 호출을 함수 그 자체로 대체하게 된다.
스코프에 의한 분류 외에, 프로그래밍 언어 비의존과 프로그래밍 언어 의존, 머신(CPU) 비의존과 머신 의존 두 가지 최적화 분류가 있다.
- '''프로그래밍 언어 비의존과 프로그래밍 언어 의존''': 많은 고급 언어의 구문 요소와 추상화는 공통적이다. 분기(if, switch, case), 루프(for, while, repeat...until, do...while), 캡슐화(구조체, 객체) 등이 있다. 이 특징을 이용하여 언어에 의존하지 않는 최적화 기법을 이용할 수 있다. 하지만, 언어에 따라서는 어떤 종류의 최적화가 쉽거나, 반대로 어렵기도 하다. 예를 들어, C 언어나 C++(C++)는 포인터가 있기 때문에, 배열 접근 최적화가 어렵다. 반대로, 일부 언어에서는 함수가 부작용을 가질 수 없다. 이 때문에, 같은 인수로 같은 함수를 여러 번 호출하는 경우, 컴파일러는 이것을 최적화하여 한 번만 그 함수를 호출하고, 그 후에는 그 결과를 재사용할 수 있다.
- '''머신(CPU) 비의존과 머신 의존''': 추상적인 개념(루프, 객체, 구조체 등)에 관한 최적화는 컴파일러가 대상으로 하는 머신과는 관계없이 실시할 수 있다. 하지만, 효과적인 최적화의 많은 부분은 대상 플랫폼 특유의 기능을 고려한 것이다.
머신 의존적인 최적화의 구체적인 예로 인텔 x86 계열 등에서는, XOR를 사용한 방법이 더 짧고 빠르다. 이는 즉시 값을 디코딩할 필요가 없고, 내부의 immediate operand register를 사용하지 않기 때문이다. 또한 XOR 명령이 레지스터의 의존 관계에 따라 파이프라인 정지를 초래할 수 있지만, 자신과의 XOR에서는 파이프라인이 정지하지 않는다.
컴파일러 최적화의 주요 목적은 다음과 같으며, 이들은 때로는 서로 모순되기도 한다.
- 일반적인 경우의 최적화
- 중복성 제거
- 코드 크기 줄이기
- 분기 줄이기
- 지역성 향상
- 메모리 계층 고려
- 자동 병렬화
- 멀티 프로세서 상에서 프로그램을 여러 스레드로 동작하도록 변환
- 더 정밀한 정보 획득
- 경계 검사 제거
- 분기 오프셋 최적화(머신 독립적)
- 블록 재배치
- 데드 코드 제거
- 불변식 묶어내기
- 분기 스레딩 (jump threading)
- 연산자 강도 감소
- 캐시 충돌 감소
- 스택 사용 깊이 감소
- 조건식 재정렬
5. 7. 프로시저 간 최적화
프로시저 간 최적화는 프로그램 전체를 대상으로 하며, 프로시저나 파일의 경계를 넘어서는 최적화이다. 프로시저 간에 관련된 부분에 작용하며, 국소적인 최적화와 전역적인 최적화의 협조를 통해 수행된다. 주요 프로시저 간 최적화로는 인라인 전개, 프로시저 간 데드 코드 제거, 프로시저 간 상수 전파, 프로시저 재배치 등이 있다. 일반적으로 최적화 전에 프로시저 간 분석이 필요하며, 프로시저 간 별칭 분석, 배열 접근 분석, 콜 그래프 구축 등이 있다.프로시저 간 최적화는 최근의 상용 컴파일러(실리콘 그래픽스, 인텔, 마이크로소프트, 썬 마이크로시스템즈)에 대부분 갖춰져 있다. GCC에는 오랫동안 프로시저 간 최적화가 없다는 것이 약점으로 여겨졌지만, 현재는 프로시저 간 최적화를 구현하고 있다. 그 외의 오픈 소스 컴파일러 중 프로시저 간 최적화를 갖춘 것으로는 Open64가 있으며, 연구용이나 상용으로도 이용되고 있다.
프로시저 간 최적화 및 이를 위한 분석에는 시간과 메모리가 소요되므로, 기본적으로는 실행하지 않도록 설정된 컴파일러가 많다. 사용자는 명시적으로 옵션을 지정하여 최적화를 지시해야 한다.
; 인라인 전개
: 어떤 코드가 프로시저를 호출하는 경우, 해당 프로시저 본체를 호출 측 코드 내에 전개한다. 이를 통해 프로시저 호출의 오버헤드를 줄이고, 동시에 전개된 부분에 추가적인 최적화를 적용할 수 있다. 그러나 프로시저의 코드가 호출 측에 복사되므로 메모리 사용량은 증가한다. 일반적으로 인라인 전개는 작은 프로시저를 여러 번 호출하는 경우에 유효하다.
6. 최적화에서의 프로그램 표현
컴파일러 최적화 처리에서는 해당 처리 내용에 따라 다양한 표현을 적절히 사용한다. 다음은 대표적인 표현들이다.
- 추상 구문 트리
- : 입력 프로그램에 가까운 표현. 인라인 전개 등 고수준의 최적화를 적용할 때 이용한다.
- 정적 단일 할당 형식 (SSA-form)
- : 각 변수의 정의가 프로그램 내에서 하나만 존재하도록 변환한 형식. 변수의 정의·사용 관계가 명확해진다는 장점이 있다. 루프나 조건문에서 정의값의 합류를 표현하기 위해 Φ-함수라고 불리는 특수한 함수를 도입한다.
- 3주소 코드
- : 각 문장을 하나의 정의처, 두 개의 참조처의 3개 묶음으로 표현하는 형식. 복잡한 식이 간략화되고, 명령 수준의 표현에 가까워진다는 장점이 있다.
- 제어 흐름 그래프
- : 프로그램의 제어 흐름을 그래프로 표현한 형식. 유사한 표현으로 데이터의 흐름을 나타내는 데이터 흐름 그래프 등이 있다.
- 의사 명령
- : 가상적인 기계의 명령.
7. 최적화의 한계와 문제점
컴파일러 초창기에는 컴파일러에 의한 최적화가 사람이 직접 작성한 코드만큼 좋지 못했다. 그러나 컴파일러 기술이 발전하면서, 컴파일러가 인간 프로그래머보다 더 나은 코드를 생성할 수 있게 되었다. RISC 아키텍처나 VLIW에서는 컴파일러 최적화가 효율적인 코드를 얻기 위한 핵심 요소이다. RISC의 명령어 집합은 작아서, 사람이 직접 스케줄을 짜거나 효율적인 결과를 얻는 것은 어렵기 때문이다.
하지만, 최적화 컴파일러는 완벽하지 않다. 컴파일러가 모든 소스 코드에 대해 최적의 코드를 생성할 수는 없다. 어떤 소스 코드에 대해서도 최상의 최적화를 수행하는 컴파일러가 존재한다면, 튜링 머신 정지 문제의 해가 도출되어 모순이 발생한다. 따라서 그러한 컴파일러는 존재하지 않는다.
최적화 컴파일러 기술에는 몇 가지 현실적인 문제가 있다.
- 최적화 컴파일러는 저수준의 국소적인 수정을 수행한다. 반면, 고수준에서의 소스 프로그램의 비효율성(예: 채택한 알고리즘의 비효율성)은 수정되지 않는다.
- 최근의 서드파티 컴파일러는 다양한 요구에 부응해야 한다. 따라서, 각각을 적절히 처리하지만, 어느 것도 최선을 다하지 않는다.
- 컴파일러는, 어떤 시점에서는 프로그램 전체의 극히 일부만 보게 되는 것이 일반적이다. 기껏해야 하나의 모듈을 보는 정도이며, 일반적으로 프로시저 단위로만 본다. 이 때문에, 중요한 문맥 정보를 놓칠 가능성이 있다.
- 컴파일러 최적화의 오버헤드 제약. 고도로 최적화를 수행하려고 하면 시간이 걸린다. 프로시저 간 최적화는 그런 의미에서 매우 비용이 많이 든다.
- 컴파일러 최적화의 각 단계 간의 상호 작용. 어떻게 단계를 조합하는 것이 최적인지, 어떤 순서로 수행하면 시간을 절약할 수 있는지 등의 문제가 있다.
최적화 기법을 개선하려는 시도가 계속되고 있다. 한 가지 시도로는 "포스트 패스" 옵티마이저가 있다. 이것은 최적화 컴파일러의 출력인 실행 파일에 대해 추가로 최적화를 수행하는 도구이다. 컴파일러 최적화가 프로그램의 중간 표현에 대해 작용하는 데 반해, 포스트 패스 옵티마이저는 어셈블리 언어 레벨에 대해 작용한다. 그러나 포스트 패스 컴파일러에도 한계가 있는데, 원본 소스 코드에 존재했던 정보의 대부분이 실행 파일에서는 손실되기 때문이다.
프로세서의 성능 향상은 메모리 대역폭의 향상보다 빠르다. 따라서 불필요한 명령을 실행해야 하더라도, 사용하는 메모리 대역폭을 줄이는 최적화가 유효해졌다. 예를 들어, 중첩 루프 최적화나 재구현이 그러한 최적화의 예이다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com