원문 보기: https://dawoum.duckdns.org/wiki/Interprocedural_optimization
Interprocedural optimization (IPO)는 많은 자주 사용되는 작은 또는 중간 길이의 함수를 포함하는 프로그램에서 성능을 향상시키기 위해 컴퓨터 프로그래밍에 사용되는 컴파일러 기술의 모음입니다. IPO는 단일 함수 또는 코드 블록이 아닌 전체 프로그램을 분석한다는 점에서 다른 컴파일러 최적화와 다릅니다.
IPO는 중복 계산 및 메모리의 비효율적인 사용을 줄이거나 없애고 루프와 같은 반복 시퀀스를 단순화하는 것을 목표로 합니다. 만약 루프 내에서 또 다른 루틴에 대한 호출이 발생하면, IPO 분석은 해당 루틴을 인라인하는 것이 가장 적합하다고 결정할 수 있습니다. 대안적으로, IPO는 더 나은 메모리 레이아웃 및 지역성을 위해 루틴을 재정렬할 수 있습니다.
IPO에는 전체-프로그램 레벨에 적용되는 일반적인 컴파일러 최적화 (예를 들어, 실행되지 않는 코드를 제거하는 dead code elimination (DCE))도 포함될 수 있습니다. IPO는 역시 상수를 더 잘 사용하려고 시도합니다. 최신 컴파일러는 컴파일-시간에 옵션으로 IPO를 제공합니다. 실제 IPO 프로세스는 사람이 읽을 수 있는 소스 코드와 완성된 실행 가능한 바이너리 프로그램 생성 사이의 임의의 단계에서 발생할 수 있습니다.
파일별로 컴파일되는 언어에 대해, 번역 단위 (모듈 파일)에서 효과적인 IPO를 위해서는 전체 프로그램 최적화(whole program optimization, WPO)를 실행할 수 있도록 프로그램의 "진입점"에 대한 지식이 필요합니다. 많은 경우에서, 이것은 전체 프로그램이 링커에 표시되기 때문에 link-time optimization (LTO) 패스로 구현됩니다.
Analysis
속력에 대해 임의의 최적화의 목표는 프로그램을 가능한 한 빨리 실행하는 것입니다; 문제는 컴파일러가 프로그램을 올바르게 분석하고 프로그램이 무엇을 할 것인지 결정하는 것이 불가능하다는 것이며, 프로그래머가 하려고 의도한 것은 더더욱 불가능하다는 것입니다. 대조적으로, 인간 프로그래머는 다른 쪽 끝에서 목적을 가지고 시작하여 그 과정에서 많은 생각을 들이지 않고 그것을 달성할 프로그램을 만들려고 시도합니다.
가독성을 비롯한 여러 가지 이유로, 프로그램은 몇 가지 일반적인 경우를 처리하는 여러 프로시저로 나뉘는 경우가 많습니다. 어쨌든, 각 프로시저의 일반성으로 인해 특정 용도에서 노력이 낭비될 수 있습니다. 프로시저-사이 최적화는 이러한 낭비를 줄이기 위한 시도를 나타냅니다.
F(x)를 평가하는 프로시저가 있고, F가 순수 함수이고, 코드가 F(6)의 결과를 요청하고 그런-다음 나중에 F(6)의 결과를 다시 요청한다고 가정해 보십시오. 이 두 번째 평가는 거의 확실히 불필요합니다: 결과는 대신 저장되고 나중에 참조될 수 있습니다. 이 간단한 최적화는 F(x)의 구현이 비-순수로 되는 순간 좌절됩니다; 즉, 실행에는 호출 사이에 변경된 명시적 인수 6 이외의 매개 변수에 대한 참조, 또는 로그에 일부 메시지 인쇄, 평가 횟수 계산, 소비된 CPU 시간 누적, 관련 매개 변수에 대한 후속 호출이 용이하게 되도록 내부 테이블 준비, 등과 같은 부작용을 포함합니다. 두 번째 시간 비-평가를 통해 이들 부작용을 잃는 것은 허용될 수도 있고, 그렇지 않을 수도 있습니다.
보다 일반적으로, 최적화를 제외하고, 프로시저를 사용하는 두 번째 이유는 프로시저를 수행할 때마다 같은 결과, 또는 거의 같은 결과를 생성하는 코드의 중복을 피하기 위한 것입니다. 그러므로 최적화에 대한 일반적인 접근 방식은 이를 역으로 하는 것입니다: 특정 프로시저의 일부 또는 모든 호출이 관련 코드로 대체되고, 적절하게 대체된 매개변수를 가집니다. 그런 다음 컴파일러는 결과를 최적화하려고 시도할 것입니다.
WPO and LTO
Whole program optimization (WPO)는 프로그램에서 모든 모듈에 대한 정보를 사용하는 프로그램의 컴파일러 최적화입니다. 통상적으로, 최적화는 모듈당 "compiland" 기저로 수행됩니다; 그러나 이 접근 방식은, 작성과 테스트가 더 쉽고 컴파일 자체 동안 자원을 덜 요구하지만, 적극적인 인라이닝과 같은 여러 최적화의 안전성에 대한 확신을 허용하지 않고 따라서 실제로 내보낸 개체 코드의 의미론을 변경하지 않는 효율성 향상으로 판명되더라도 이를 수행할 수 없습니다.
Link-time optimization (LTO)는 링크 시간에 컴파일러에 의해 프로그램에 수행된 프로그램 최적화의 유형입니다. 링크 시간 최적화는 파일별 기저로 프로그램을 컴파일하고 그런-다음 그들 파일을 한 번에 모두 링크하는 것 (예를 들어, Java의 just-in-time compilation (JIT))이 아니라 함께 링크하는 프로그래밍 언어 (예를 들어, C 및 Fortran)와 관련이 있습니다.
한번 모든 파일이 오브젝트 파일로 개별적으로 컴파일되면, 전통적으로, 컴파일러는 오브젝트 파일을 단일 파일인 실행 파일로 연결 (병합)합니다. 어쨌든, GNU Compiler Collection (GCC)와 LLVM에 의해 구현된 LTO에서, 컴파일러는 단일 실행 파일을 구성하려는 모든 다른 컴파일 단위가 링크가 최종적으로 발생할 때 단일 모듈로 최적화될 수 있도록 각각 중간 표현 (IR), 즉 GIMPLE 바이트코드 또는 LLVM 비트코드를 덤프할 수 있습니다. 이것은 프로시저-사이 최적화의 범위를 확장하여 전체 프로그램 (또는, 오히려, 링크 시간에 볼 수 있는 모든 것)을 포괄합니다. 링크-시간 최적화와 함께, 컴파일러는 전체 프로그램에 다양한 형태의 프로시저-사이 최적화를 적용할 수 있으며, 더 심층적인 분석, 더 많은 최적화, 및 궁극적으로 더 나은 프로그램 성능을 허용합니다.
실제로, LTO가 항상 전체 프로그램을 최적화하는 것은 아닙니다—라이브러리 함수, 특히 동적으로 연결된 공유 객체는 과도한 중복을 피하고 업데이트를 허용하기 위해 의도적으로 제외됩니다. 정적 링킹은 자연스럽게 LTO의 개념에 적합하지만, 기계-코드 전용 객체 파일과 달리 IR 객체를 포함하는 라이브러리 아카이브에서만 작동합니다.[1] 성능 문제로 인해, 전체 단위가 항상 직접 사용되는 것은 아닙니다—프로그램은 GCC의 WHOPR과 같은 분할-과-정복 스타일의 LTO로 분할될 수 있습니다.[2] 그리고 물론, 빌드되는 프로그램 자체가 라이브러리일 때, 최적화는 DCE의 일부로 제거하려고 너무 열심히 시도하지 않고 외부에서 사용할 수 있는 (내보내진) 모든 각 기호를 유지합니다.[1]
GCC의 -fwhole-program 스위치에서 볼 수 있듯이 LTO 없이도 훨씬 더 제한된 형태의 WPO가 여전히 가능합니다. 이 모드는 그것 안의 모든 각 다른 함수가 외부에서 사용되지 않고 안전하게 최적화될 수 있도록 GCC에게 컴파일되는 모듈에 전체 프로그램의 진입 점이 포함되어 있다고 가정하게 만듭니다. 그것은 단일 모듈에만 적용되기 때문에, 전체 프로그램을 진정으로 포괄할 수 없습니다. 그것은 원-빅 모듈 (one-big-module) 의미에서 LTO와 결합할 수 있으며, 이는 링커가 외부에서 사용되는 진입 점이나 기호에 대해 GCC와 다시 통신하지 않을 때 유용합니다.[1]
History
ALGOL과 같은 절차적 언어에 대해, 프로시저-사이 분석 및 최적화는 1970년대 초에 상업적으로 사용된 것으로 보입니다. IBM의 PL/I Optimizing Compiler는 프로시저 호출과 예외 (PL/I 용어로 "조건으로" 캐스트됨)와[3] Fran Allen에 의한 논문에서 프로시저-사이 분석을 수행하여 프로시저-사이 분석을 수행했습니다.[4][5] APL 프로그래밍 언어의 컴파일 작업은 필연적으로 프로시저-사이 작업이었습니다.[6][7]
프로시저-사이 분석 및 최적화 기술은 1980년대와 1990년대에 학술 연구의 주제였습니다. 그것들은 1990년대 초에 Convex Computer Corporation (Convex C4에 대해 "Application Compiler")과 Ardent (Ardent Titan에 대해 컴파일러)의 컴파일러와 함께 상용 컴파일러 세계에 다시 등장했습니다. 이들 컴파일러는 기술이 상용 컴파일러에서 수용될 수 있을 만큼 충분히 빠르게 만들 수 있음을 보여주었습니다; 그 후, 프로시저-사이 기술은 여러 상업 및 비상업적 시스템에 등장했습니다.
Flags and implementation
Unix-like
GNU Compiler Collection에는 모든 최적화 수준에서 함수 인라인이 있습니다. -O1에서, 이것은 한 번만 호출되는 경우에만 적용되고 (-finline-functions-once), -O2에서 이 제약 조건이 완화됩니다 (-finline-functions). 기본적으로 이것은 단일-파일-전용 동작이지만, 링크-시간 최적화 -flto와 함께 전체 프로그램이 됩니다.[1] Clang의 명령줄 인터페이스는 -fwhole-program 옵션이 없다는 점을 제외하고는 GCC의 인터페이스와 유사합니다.[8]
LTO에 의해 생성된 객체 파일에는 링크-시간에 해석되는 컴파일러-별 중간 표현 (IR)이 포함되어 있습니다. 이것이 정적 라이브러리와 잘 작동하는지 확인하기 위해, 최신 GNU 링커에는 컴파일러가 필요할 때 객체 파일을 기계어 코드 형식으로 변환할 수 있는 "링커 플러그인" 인터페이스가 있습니다. 이 플러그인은 일반적으로 LTO 프로세스를 구동하는 데도 도움이 됩니다. 대안적으로, 기계어와 IR을 모두 포함하도록 "fat LTO" 개체를 생성할 수 있지만, 더 많은 공간을 차지합니다.[1]
GCC와 LLVM (clang)은 모두 다양한 프로그래밍 언어에서 IR을 생성할 수 있기 때문에, 링크-시간 IPO는 언어 경계를 넘어 발생할 수 있습니다. 이것은 C와 C++에서 가장 공통적으로 시연되지만,[9] LLVM은 Rust와 다른 모든 LLVM 기반 컴파일러에서도 가능합니다.[10]
Non-LTO options
GCC 및 Clang은 기본적으로 최적화 레벨 2에서 IPO를 수행합니다. 어쨌든, LTO가 비활성화될 때, IPO는 개체 파일 내에서만 발생할 수 있고 비-정적 함수는 절대 제거할 수 없기 때문에 최적화 정도가 제한됩니다. 후자의 문제에는 비-LTO 해결책이 있습니다: -fwhole-program 스위치는 main()만 비정적, 즉 외부에서 볼 수 있다고 가정하기 위해 사용될 수 있습니다.[11]
또 다른 비-LTO 기술은 "함수 섹션" (GCC 및 Clang에서 -ffunction-sections)입니다. 각 함수를 객체 파일에서 자체 섹션에 배치함으로써, 링커는 참조되지 않은 섹션을 제거함으로써 (링커 옵션 --gc-sections을 사용) IR 없이 데드 코드 제거를 수행할 수 있습니다.[12] 변수에도 비슷한 옵션을 사용할 수 있지만, 훨씬 더 나쁜 코드가 생성됩니다.
Other
인텔 C/C++ 컴파일러는 전체-프로그램 IPO를 허용합니다. 단일 파일에 대해 프로시저-사이 최적화를 사용하도록 설정하는 플래그는 -ip이고, 프로그램에서 모든 파일에 걸쳐 프로세스-사이 최적화를 사용하도록 설정하는 플래그는 -ipo입니다.[13]
Visual Studio에 통합된 MSVC 컴파일러는 전체 프로그램에서 프로시저-사이 최적화도 지원합니다.[14]
전체 프로그램 프로시저-사이 최적화를 가능하게 하는 컴파일러 독립적 인터페이스는 CMake에서 INTERPROCEDURAL_OPTIMIZATION 속성을 통해 이루어집니다.[15]