프로시저 간 최적화

3. 분석

프로시저 간 최적화는 프로시저의 일반성이 특정 상황에서 불필요한 작업을 유발할 수 있다는 점을 인식하고 이러한 낭비를 줄이려고 시도한다. 프로시저가 순수 함수인지, 부작용이 있는지 등을 분석하여 불필요한 연산을 제거하고 성능을 향상시킨다.

예를 들어, F(x)를 평가하는 프로시저가 있고 F가 순수 함수이며, 코드가 F(6)의 결과를 요청한 다음 나중에 F(6)을 다시 요청하는 경우, 두 번째 평가는 거의 확실히 불필요하다. 이 간단한 최적화는 F(x)의 구현이 부작용을 가지는 순간 무효가 된다.

매개변수 전달 방식에 따라서도 최적화 결과가 달라질 수 있다. 매개변수가 값으로 전달되는 경우, 프로시저의 동작은 원래 변수에 영향을 주지 않으며, 프로시저가 환경에 아무것도 하지 않는다면 코드는 완전히 최적화될 수 있다.

만약 매개변수가 참조로 전달되는 경우에는 프로시저 내에서의 동작이 실제로 원본에 영향을 미친다. 이는 일반적으로 매개변수의 기계 주소를 프로시저에 전달하여 프로시저의 조정이 원래의 저장 영역에 적용되도록 함으로써 수행된다.

복사-입력, 복사-출력 방식은 프로시저가 종료될 때 원래 값으로 다시 복사되는 매개변수의 로컬 복사본에서 작동한다. 동일한 매개변수에 다르게 접근하는 경우 불일치가 발생할 수 있다.

4. WPO와 LTO

전체 프로그램 최적화(WPO)는 컴파일러가 프로그램 내 모든 모듈에 대한 정보를 사용하여 프로그램을 최적화하는 기법이다. 일반적인 최적화는 모듈 단위로 수행되지만, WPO는 더 광범위한 최적화를 가능하게 한다.

링크 타임 최적화(LTO)는 링크 타임에 컴파일러가 수행하는 프로그램 최적화의 한 유형이다. 이는 C나 포트란처럼 프로그램을 파일별로 컴파일한 후 함께 연결하는 프로그래밍 언어와 관련이 있으며, Java의 Just-in-time 컴파일(JIT)과는 다른 방식이다.

GNU 컴파일러 모음(GCC) 및 LLVM에서 구현된 LTO에서 컴파일러는 중간 표현(IR)을 덤프하여, 단일 실행 파일을 구성하는 모든 컴파일 단위를 단일 모듈로 최적화할 수 있다. 이렇게 하면 프로시저 간 최적화의 범위가 전체 프로그램으로 확장된다. LTO를 통해 컴파일러는 더 심층적인 분석과 최적화를 수행하여 프로그램 성능을 향상시킬 수 있다.

LTO가 항상 전체 프로그램을 최적화하는 것은 아니다. 동적으로 연결된 공유 객체인 라이브러리 함수는 의도적으로 제외된다. 정적 링크는 LTO 개념에 부합하지만, IR 객체를 포함하는 라이브러리 아카이브에서만 작동한다.^[2] 성능 문제로 인해 GCC의 WHOPR과 같은 분할 정복 스타일 LTO가 사용되기도 한다.^[1]

4. 1. Non-LTO 옵션

5. 컴파일러 지원

GNU 컴파일러 모음(GCC)은 모든 최적화 수준에서 함수 인라인 기능을 제공한다. `-O1`에서는 한 번만 호출되는 함수에만 적용되며(`-finline-functions-once`), `-O2`에서는 이 제약이 완화된다(`-finline-functions`). 기본적으로 이는 단일 파일에서만 적용되는 동작이지만, 링크 타임 최적화(`-flto`)를 사용하면 전체 프로그램으로 확장된다.^[2] Clang의 명령줄 인터페이스는 GCC와 유사하지만, `-fwhole-program` 옵션은 없다.^[8]

LTO로 생성된 객체 파일은 링크 타임에 해석되는 컴파일러 고유의 중간 표현(IR)을 포함한다. 이것이 정적 라이브러리와 잘 작동하도록 하기 위해, 새로운 GNU 링커는 필요할 때 컴파일러가 객체 파일을 기계어 형태로 변환할 수 있도록 하는 "링커 플러그인" 인터페이스를 가지고 있다. 이 플러그인은 또한 일반적으로 LTO 프로세스를 진행하는 데 도움을 준다. 기계 코드와 IR을 모두 포함하는 "fat LTO" 객체를 생성할 수도 있지만, 이 경우 더 많은 공간이 필요하다.^[2]

GCC와 LLVM (clang) 모두 다양한 프로그래밍 언어에서 IR을 생성할 수 있으므로, 링크 타임 IPO는 언어 경계를 넘어 발생할 수 있다. 이는 C와 C++로 가장 흔하게 시연되지만,^[9] LLVM은 Rust 및 기타 모든 LLVM 기반 컴파일러에서도 이를 가능하게 한다.^[10]

인텔 C/C++ 컴파일러는 전체 프로그램 IPO를 허용한다. 단일 파일에 대한 프로시저 간 최적화를 활성화하는 플래그는 `-ip`이고, 프로그램의 모든 파일에서 프로시저 간 최적화를 활성화하는 플래그는 `-ipo`이다.^[13][14]

MSVC 컴파일러는 비주얼 스튜디오에 통합되어 있으며, 전체 프로그램에 대한 프로시저 간 최적화도 지원한다.^[15]

전체 프로그램 프로시저 간 최적화를 활성화하기 위한 컴파일러 독립적인 인터페이스는 CMake의 `INTERPROCEDURAL_OPTIMIZATION` 속성을 사용하는 것이다.^[16]

6. 예시

다음은 프로시저 간 최적화가 어떻게 작동하는지를 보여주는 파스칼 코드 예시이다.



Program example;

integer b; {프로시저 Silly에 "전역적"인 변수.}

Procedure Silly(a,x)

if x < 0 then a:=x + b else a:=-6;

End Silly; {b를 참조하며, 매개변수가 아니므로, 일반적으로 Silly는 "순수하지 않다".}

integer a,x; {이 변수들은 매개변수일 경우에만 Silly에서 볼 수 있다.}

x:=7; b:=5;

Silly(a,x); write(x);

Silly(x,a); write(x);

Silly(b,b); write(b);

End example;



`Silly` 프로시저의 매개변수가 값으로 전달되는 경우, 프로시저의 동작은 원래 변수에 영향을 주지 않는다. `Silly`는 환경에 아무런 영향을 주지 않으므로 (파일 읽기, 쓰기, `b`와 같은 전역 변수 수정 등), 해당 코드와 호출은 완전히 최적화될 수 있다. `a`의 값은 정의되지 않은 상태로 남지만, 이는 중요하지 않다. 따라서 `write` 문만 남아서 상수 값을 출력한다.

매개변수가 참조로 전달되면 `Silly` 내에서의 동작은 실제로 원본 변수에 영향을 미친다. 이는 일반적으로 매개변수의 주소를 프로시저에 전달하여 프로시저의 수정이 원래 저장 영역에 적용되도록 함으로써 수행된다. 프로시저 `Silly`의 호출이 인라인으로 확장되고 매개변수가 주소로 식별된다면, 코드는 다음과 같이 된다.



x:=7; b:=5;

if x < 0 then a:=x + b else a:=-6; write(x); {a가 변경된다.}

if a < 0 then x:=a + b else x:=-6; write(x); {매개변수가 교환되었기 때문이다.}

if b < 0 then b:=b + b else b:=-6; write(b); {Silly 안의 변수 b의 두 버전, 더하기 전역 사용.}



컴파일러는 이 예제에서 논리를 따라 상수를 찾고, `if` 문의 조건이 상수임을 발견하여 다음과 같이 최적화할 수 있다.



x:=7; b:=5;

a:=-6; write(7); {b는 참조되지 않으므로, 이 사용법은 "순수"하게 유지된다.}

x:=-1; write(-1); {b가 참조된다...}

b:=-6; write(-6); {b는 매개변수 표시를 통해 수정된다.}



`a`, `b`, `x`에 대한 할당은 출력문에 나타나지 않고, 후속 계산의 입력으로도 사용되지 않으므로 의미가 없다. 따라서 이 코드는 다음과 같이 단순화될 수 있다.



write(7);

write(-1);

write(-6);



매개변수를 전달하는 또 다른 방법은 복사-입력, 복사-출력 방식이다. 이 방식에서는 프로시저가 종료될 때 원래 값으로 다시 복사되는 매개변수의 로컬 복사본에서 작동한다. `Silly(a, a)` 또는 `Silly(a, b)`와 같이 동일한 매개변수에 다르게 접근하는 경우 불일치가 발생할 수 있다. 예를 들어, 매개변수가 왼쪽에서 오른쪽으로 복사-입력, 복사-출력 방식으로 전달된다면, `Silly(b, b)`는 다음과 같이 확장된다.



p1:=b; p2:=b; {복사 입력. 로컬 변수 p1과 p2는 같다.}

if p2 < 0 then p1:=p2 + b else p1:=-6; {따라서 p1은 p2와 더 이상 같지 않을 수 있다.}

b:=p1; b:=p2; {복사 출력. 왼쪽에서 오른쪽 순서로 p1의 값이 덮어쓰여진다.}



이 경우 `p1`의 값(변경된 값)을 `b`로 복사하는 것은 무의미하다. `p2`의 값으로 즉시 덮어쓰여지기 때문이다. `p2`의 값은 프로시저 내에서 원래 `b` 값에서 수정되지 않았으므로, 세 번째 문은 `write(5);`가 된다.

이러한 동작 차이는 혼란을 야기할 수 있으며, 매개변수가 복사되는 순서에 대한 질문으로 인해 더욱 복잡해진다. 컴파일러 매뉴얼에 이러한 세부 사항이 명확하게 설명되지 않거나, 설명되더라도 잊혀질 수 있다.

참조

_[1] 웹사이트 LTO Overview https://gcc.gnu.org/[...]
_[2] 웹사이트 Optimize Options https://gcc.gnu.org/[...]
_[3] 논문 "Exposing side effects in a PL/I optimizing compiler" North-Holland Publishing Company
_[4] 논문 Interprocedural Data Flow Analysis 1974
_[5] 간행물 Determining the Data Flow Relationships in a Collection of Procedures IBM Research 1974-08
_[6] 보고서 An APL Machine Stanford University Computer Science Department 1970-02
_[7] 학위논문 Tentative Compilation: A Design for an APL Compiler Yale University 1978
_[8] 웹사이트 Clang command line argument reference https://clang.llvm.o[...]
_[9] 웹사이트 Can LTO for gcc or clang optimize across C and C++ methods https://stackoverflo[...]
_[10] 웹사이트 Closing the gap: cross-language LTO between Rust and C/C++ http://blog.llvm.org[...] 2019-09-19
_[11] 웹사이트 Optimize Options https://gcc.gnu.org/[...]
_[12] 웹사이트 Function sections https://elinux.org/F[...]
_[13] 웹사이트 Intel compiler 8 documentation https://web.archive.[...] 2007-02-13
_[14] 웹사이트 Intel Visual Fortran Compiler 9.1, Standard and Professional Editions, for Windows* - Intel Software Network http://www.intel.com[...]
_[15] 웹사이트 /GL (Whole Program Optimization) https://docs.microso[...] 2019-03-12
_[16] 웹사이트 INTERPROCEDURAL_OPTIMIZATION https://cmake.org/cm[...]
_[17] 논문 "Exposing side effects in a PL/I optimizing compiler" North-Holland Publishing Company