프로시저간 최적화

이 문서의 어조나 문체는 위키피디아에서 사용되는 백과사전적 어조를 반영하지 못할 수 있습니다. 더 나은 문서를 작성하려면 Wikipedia 가이드를 참조하십시오.(2022년 5월) (이 템플릿메시지를 삭제하는 방법과 타이밍을 학습합니다)

IPO(Interprocedureal Optimization)는 컴퓨터 프로그래밍에서 사용되는 컴파일러 기술의 집합으로, 작고 중간 길이의 많은 자주 사용되는 함수를 포함하는 프로그램의 성능을 향상시킵니다.IPO는 전체 프로그램을 분석하기 때문에 다른 컴파일러 최적화와 다릅니다. 다른 최적화에서는 단일 함수 또는 단일 코드 블록만 봅니다.

IPO는 중복 계산, 비효율적인 메모리 사용을 줄이거나 제거하고 루프와 같은 반복 시퀀스를 단순화하는 것을 추구합니다.루프 내에서 발생하는 다른 루틴에 대한 콜이 있는 경우 IPO 분석에 따라 해당 루틴을 인라인화하는 것이 최선이라고 판단될 수 있습니다.또한 IPO는 더 나은 메모리 레이아웃과 지역성을 위해 루틴을 재정렬할 수 있습니다.

IPO는 프로그램 전체의 전형적인 컴파일러 최적화를 포함할 수도 있습니다.예를 들어, 실행하지 않는 코드를 삭제하는 Dead Code Elimination(DCEdead code elimination (Dead code elimination : 데드 코드 제거)이를 위해 컴파일러는 취득하지 않은 브랜치를 테스트하고 해당 브랜치의 코드를 삭제합니다.IPO는 또한 상수의 더 나은 사용을 보장하기 위해 노력합니다.최신 컴파일러는 컴파일 시 옵션으로 IPO를 제공합니다.실제 IPO 프로세스는 사람이 읽을 수 있는 소스 코드와 완성된 실행 가능한 이진 프로그램을 생성하는 단계 사이에서 발생할 수 있습니다.

파일 단위로 컴파일 하는 언어의 경우 번역 유닛(모듈 파일) 전체에 걸쳐 효과적인 IPO를 실시하려면 프로그램 전체의 최적화(WPO)를 실행할 수 있도록 프로그램의 "엔트리 포인트"에 대한 지식이 필요합니다.프로그램 전체가 링커에 표시되기 때문에 많은 경우 이것은 Link-Time Optimization(LTO; 링크 시간 최적화) 패스로 구현됩니다.

분석.

속도 최적화의 목적은 가능한 한 빨리 프로그램을 실행하는 것입니다.문제는 컴파일러가 프로그램을 올바르게 분석하여 무엇을 할 것인지 결정하는 것이 불가능하다는 것입니다.하물며 프로그래머가 의도한 것은 더더욱 아닙니다.반면, 인간 프로그래머는 다른 쪽 끝에서 목적을 가지고 시작하며, 그 과정에서 많은 생각을 들이지 않고 이를 달성할 수 있는 프로그램을 제작하려고 시도합니다.

가독성을 포함한 다양한 이유로 프로그램은 몇 가지 일반적인 경우를 처리하는 여러 절차로 분할되는 경우가 많습니다.그러나 각 절차의 일반성으로 인해 특정 사용법에 대한 노력이 낭비될 수 있습니다.절차 간 최적화는 이러한 낭비를 줄이려는 시도를 나타냅니다.

F(x)를 평가하는 절차가 있고 코드가 F(6)의 결과를 요청하고 나중에 F(6)를 다시 요청한다고 가정합니다.이 두 번째 평가는 거의 불필요합니다.F가 순수한 함수라고 가정하면 결과는 저장되고 나중에 참조될 수 있습니다.이 단순한 최적화는 F(x)의 구현이 불순해지는 순간 좌절됩니다.즉, 실행에는 호출 간에 변경된 명시적 인수 6 이외의 파라미터에 대한 참조나 로그에 대한 메시지 인쇄, 평가 횟수 카운트, CPU 팀 축적 등의 부작용이 포함됩니다.e 소비, 관련 파라미터에 대한 후속 호출을 용이하게 하기 위해 내부 테이블 준비 등.두 번째 비평가를 통해 이러한 부작용을 잃는 것은 허용될 수도 있고 그렇지 않을 수도 있다.

보다 일반적으로 최적화를 제외하고 절차를 사용하는 두 번째 이유는 절차를 수행할 때마다 동일한 결과 또는 거의 동일한 결과를 생성하는 코드의 중복을 피하기 위함입니다.따라서 최적화에 대한 일반적인 접근법은 이를 되돌리는 것입니다. 즉, 특정 절차의 일부 또는 모든 호출이 각 코드로 대체되고 매개 변수가 적절히 대체됩니다.그런 다음 컴파일러는 결과를 최적화하려고 합니다.

WPO 및 LTO

전체 프로그램 최적화(WPO)는 프로그램 내의 모든 모듈에 대한 정보를 사용하여 프로그램을 컴파일러 최적화하는 것입니다.보통 최적화는 모듈별로 "컴파일랜드" 단위로 실행되지만, 이 접근법은 쓰기 및 테스트가 용이하고 컴파일 자체에서 리소스가 덜 요구되지만, 적극적인 인라이닝과 같은 여러 최적화의 안전성에 대한 확실성은 인정되지 않으며, 따라서 실제로 전환하더라도 이러한 최적화를 수행할 수 없습니다.out은 출력된 객체 코드의 의미를 변경하지 않는 효율성 향상입니다.

링크 시간 최적화(LTO)는 컴파일러가 링크 시간에 프로그램에 대해 수행하는 프로그램 최적화 유형입니다.링크 시간 최적화는 파일 단위로 프로그램을 컴파일한 다음 이들 파일을 한꺼번에 링크하는 프로그래밍 언어(예: Java의 JIT(Just-in-Time Compilation))와 관련이 있습니다.

모든 파일이 오브젝트 파일로 따로 컴파일되면 기존에는 컴파일러가 오브젝트 파일을 단일 파일인 실행 파일로 링크(머지)합니다.단, GNU 컴파일러 컬렉션(GCC) 또는 LLVM에 의해 구현된 LTO에서는 컴파일러는 중간 표현(GIMPLE 바이트 코드 또는 LLVM 비트 코드)을 디스크에 덤프할 수 있으므로 링크가 최종적으로 발생했을 때 단일 실행 파일을 구성하는 모든 다른 컴파일 유닛을 단일 모듈로 최적화할 수 있습니다.이것에 의해, 프로시저간 최적화의 범위가 프로그램 전체(또는 링크시에 표시되는 모든 것)로 확대됩니다.링크 타임 최적화를 통해 컴파일러는 프로그램 전체에 다양한 형식의 프로시저 간 최적화를 적용할 수 있으며, 보다 심층적인 분석, 보다 많은 최적화, 궁극적으로는 더 나은 프로그램 성능을 제공합니다.

실제로 LTO가 프로그램 전체를 항상 최적화하는 것은 아닙니다.라이브러리 기능, 특히 동적으로 링크된 공유 객체는 과도한 복제를 피하고 업데이트를 허용하기 위해 의도적으로 배제됩니다.정적 링크는 당연히 LTO의 개념에 도움이 되지만 기계 코드 전용 객체 ^[1]파일이 아닌 IR 객체를 포함하는 라이브러리 아카이브에서만 작동합니다.퍼포먼스상의 문제로 유닛 전체가 항상 직접 사용되는 것은 아닙니다.프로그램은 ^[2]GCC의 WHOPR과 같은 분할 및 정복 방식의 LTO로 분할될 수 있습니다.물론 빌드 중인 프로그램 자체가 라이브러리일 경우 최적화 기능을 통해 외부에서 사용 가능한(내보낸) 기호를 모두 유지할 수 있습니다.^[1] DCE의 일부로 너무 많이 제거할 필요는 없습니다.

GCC의 예와 같이 LTO 없이 훨씬 더 제한된 형태의 WPO가 여전히 가능합니다.-fwhole-program전환합니다.이 모드에서는 GCC는 컴파일되는 모듈에 엔트리 포인트가 포함되어 있는 것으로 간주합니다(통상은main()프로그램 전체의 다른 모든 기능을 외부에서 사용하지 않고 안전하게 최적화할 수 있도록 합니다.1개의 모듈에만 적용되므로 프로그램 전체를 포함할 수 없습니다.(이것은 1 빅모듈의 의미로 LTO와 조합할 수 있습니다.링커가 외부에서 사용되고 있는 엔트리 포인트 또는 심볼에 대해 GCC에 회신하지 않을 때 편리합니다).^[1]

예

프로그램. 예;    정수 b;              {프로시저에 대한 변수 "글로벌"}    절차. 멍청한(a,x)       한다면 x < > 0 그리고나서 a:=x + b 또 다른 a:=-6;    끝. 멍청한;              {파라미터가 아닌 b에 대한 참조는 일반적으로 Silly를 "불순한" 상태로 만듭니다.}    정수 a,x;            {이러한 변수는 파라미터의 경우에만 Silly에 표시됩니다.}    x:=7; b:=5;    멍청한(a,x); 쓰다(x);    멍청한(x,a); 쓰다(x);    멍청한(b,b); 쓰다(b); 끝. 예; 

파라미터가 값으로 전달되면 프로시저의 액션은 원래 변수에 영향을 주지 않습니다.Silly는 환경에 아무런 영향도 주지 않기 때문에(파일에서 읽기, 파일에 쓰기, b 등의 글로벌 변수 수정 등), 코드와 모든 호출이 최적화되어 정의되지 않은 값이 될 수 있습니다.중요하지 않음)을 통해 인쇄문만 유지되고 값이 일정하게 유지됩니다.

파라미터가 참조에 의해 전달되는 경우 Sily 내에서 파라미터에 대한 액션은 실제로 원본에 영향을 미칩니다.이는 보통 파라미터의 기계주소를 프로시저에 전달하여 프로시저의 조정이 원래 저장영역에 오도록 함으로써 이루어집니다.따라서 참조에 의한 콜의 경우 프로시저 Silly가 효과가 있습니다.주소별로 식별되는 파라미터가 있는 호출이 확장되어 있다고 가정합니다.코드는 다음과 같습니다.

x:=7; b:=5; 한다면 x < > 0 그리고나서 a:=x + b 또 다른 a:=-6; 쓰다(x);   {a가 변경되었습니다.} 한다면 a < > 0 그리고나서 x:=a + b 또 다른 x:=-6; 쓰다(x);   {파라미터가 스왑되었기 때문입니다.} 한다면 b < > 0 그리고나서 b:=b + b 또 다른 b:=-6; 쓰다(b);   {Silly에서 변수 b의 두 가지 버전과 글로벌 사용량.} 

컴파일러는 이 비교적 작은 예에서 논리(있는 그대로)를 따라 상수를 따를 수 있으며 if-스테이트먼트의 술어가 일정하다는 것을 알 수 있습니다.

x:=7; b:=5; a:=-6; 쓰다(7);            {b}은(는) 참조되지 않으므로 이 사용량은 "순수한" 상태로 유지됩니다.} x:=-1; 쓰다(-1);           {b가 참조됨...} b:=-6; 쓰다(-6);           {b}은(는) 해당 매개 변수 표시를 통해 수정됩니다.} 

또한 a, b 및 x에 대한 할당은 외부에 아무것도 제공하지 않으므로 출력문에도 후속 계산의 입력으로도 표시되지 않습니다(결과도 출력으로 이어집니다.그렇지 않으면 불필요합니다).이 코드에도 의미가 없습니다.그 결과, 결과는 다음과 같습니다.

쓰다(7); 쓰다(-1); 쓰다(-6); 

참조로 보이는 파라미터를 전달하기 위한 다른 방법은 복사, 복사입니다.여기서 프로시저는 프로시저를 종료할 때 값이 원래대로 복사되는 파라미터의 로컬복사에 대해 동작합니다.프로시저가 같은 파라미터에 액세스 할 수 있지만 Sily(a,a) 또는 Sily(a,b)와 같은 호출과 다른 방법으로 액세스 할 경우 불일치가 발생할 수 있습니다.따라서 파라미터가 카피인, 카피아웃에 의해 왼쪽에서 오른쪽 순서로 전달되면 Sily(b, b)가 확장됩니다.

p1:=b; p2:=b;                               {복사합니다.로컬 변수 p1과 p2는 동일합니다.} 한다면 p2 < > 0 그리고나서 p1:=p2 + b 또 다른 p1:=-6;      {따라서 p1은 p2와 동일하지 않을 수 있습니다.} b:=p1; b:=p2;                               {알겠습니다.왼쪽에서 오른쪽 순서로 p1의 값을 덮어씁니다.} 

그리고 이 경우 p1의 값(변경)을 b로 복사하는 것은 의미가 없습니다.p2의 값에 의해 즉시 덮어쓰게 됩니다.p2의 값은 원래 값 b에서 변경되어 있지 않기 때문에 세 번째 스테이트먼트가 됩니다.

쓰다(5);          {비 -6} 

이러한 행동 차이는 혼란스러움을 야기할 가능성이 높으며, 파라미터가 복사되는 순서에 대한 질문으로 인해 악화될 수 있습니다.출구 및 진입 시 왼쪽에서 오른쪽으로 이동해야 하는가?이러한 자세한 내용은 컴파일러 매뉴얼에 자세히 설명되어 있지 않을 수 있습니다.설명되어 있는 경우 즉시 수행해야 할 작업과 관련이 없는 것으로 간주되어 문제가 발생할 때까지 오랫동안 잊혀집니다.(가능성이 높은) 임시값이 스택스토리지 스킴을 통해 제공되는 경우, 카피백프로세스는 카피인의 역순서이며, 이 예에서는 p1이 대신 b로 반환되는 마지막 값임을 의미합니다.

파라미터가 변경되고 특정 호출이 상수를 파라미터로 사용할 때 구문 오류가 발생할 수 있기 때문에 인라인 프로시저를 확장하는 프로세스는 (매크로 확장과 같이) 텍스트 대체의 변형으로 간주해서는 안 됩니다.파라미터로 제공되는 상수가 그 값을 변경하지 않도록 하는 것이 중요하기 때문에(변수 그대로의 상수를 메모리에 유지할 수 있다), 그 상수의 후속 사용법(메모리 위치에 대한 참조를 통해 이루어짐)이 잘못되지 않도록 컴파일러가 상수의 값을 변환하는 코드를 생성하는 것이 일반 기술입니다.주소가 프로시저에 전달되어 그 값이 변경되어도 상수의 위치에 복사되지 않는 임시 변수.

바꿔 말하면 파라미터가 값 또는 참조에 의해 전달되는지 여부, 그리고 사용되는 경우 어떤 종류의 복사 및 복사 방식을 보고할 수 있습니다.단, 다양성은 무한합니다.심플한 파라미터는 복사로 전달될 수 있지만 어레이 등의 대규모 애그리게이트는 참조로 전달될 수 있습니다.또한 특수한 머신 코드(Clear, LoadZ 등)에 의해 0과 같은 단순한 상수가 생성될 수 있으며 i를 수정하려고 하면 읽기 전용으로 태그 지정된 메모리에 더 복잡한 상수가 저장될 수 있습니다.t 프로그램 즉시 종료 등 종료

일반적으로

이 예는 매우 간단하지만, 합병증은 이미 명백합니다.컴파일러의 최적화를 가능하게 하는 다양한 추론 가능 속성 또는 프로그래머 선언 속성을 가지는 많은 프로시저가 존재할 가능성이 높습니다.프로시저의 파라미터는 읽기 전용, 쓰기, 읽기 및 쓰기가 모두 가능하며, 일시적 변수를 통한 보호가 필요 없는 상수 등의 기회를 발생시킬 수 있지만, 주어진 호출에서 발생하는 일은 복잡한 고려사항에 따라 달라질 수 있습니다.다른 절차, 특히 함수 유사 절차에는 특정 호출에서 일부 작업을 회피할 수 있는 특정 동작이 있다. 예를 들어, 정수 매개변수를 사용하여 호출할 경우 감마 함수를 정수 인자를 포함하는 계산으로 변환할 수 있다.

어떤 컴퓨터 언어들, 더 기회를 변수 값 일부 세트(예를 들어, 6<)≤ 28)에 따라서, 그리고 또 사에 가치 있는 점검을 제공하는 데에 최적화 과정을 통해 불만을 위한 향후 이익을 제공하는 제한되고 선언하는 것을 제공하면 매개 변수의 사용에(또는 심지어 요구하는)주장할 수 있는그녀.소스 코드를 입력하여 오류를 검출합니다.그러나 이것은 결코 충분하지 않습니다. 일부 변수만 단순한 제약 조건을 부여할 수 있는 반면, 다른 변수들은 복잡한 사양을 필요로 합니다. 변수 P를 소수라고 어떻게 지정할 수 있을까요? 만약 그렇다면 값 1이 포함됩니까?복잡성은 즉시 발생합니다.M이 월 번호인 경우 day-of-month D의 유효한 범위는 무엇입니까?그리고 모든 위반이 즉시 종료될 가치가 있는가?이 모든 것을 처리할 수 있다고 해도 그에 따른 이점은 무엇일까요?그리고 어떤 대가를 치르죠?완전한 사양은 프로그램의 기능을 다른 형태로 다시 기술하는 것과 같기 때문에 컴파일러가 그것들을 처리하는 데 소비하는 시간을 제외하면 버그가 발생할 수 있습니다.대신 제공되는 런타임 범위 검사에서는 단순한 사양만 허용됩니다.

프로그램이 입력을 읽지 않는 경우(예시와 같이), 컴파일러의 분석이 진행되어 일련의 인쇄문 또는 그러한 값을 쉽게 생성하는 루프가 발생할 수 있습니다.그런 다음 소수 생성 프로그램을 인식하고, 이를 위해 가장 잘 알려진 방법으로 변환하거나, 대신 라이브러리에 대한 참조를 제공할 것인가?그럴 리 없어!일반적으로 이를 방지하기 위해 임의로 복잡한 고려사항(Entscheidungsproblem)이 발생하며 제한된 개선만으로 코드를 실행할 수 밖에 없습니다.

역사

프로시저 또는 ALGOL과 유사한 언어의 경우, 프로시저 간 분석과 최적화가 1970년대 초에 상용화된 것으로 보인다.IBM의 PL/I Optimizing 컴파일러는 프로시저 간 분석을 수행하여 프로시저 호출과 예외(PL/I 용어로 "조건에 대한")^[3] 및 Fran ^[4][5]Allen의 논문에서 부작용을 파악했습니다.APL 프로그래밍 언어의 컴파일 작업은 필연적으로 절차 ^[6][7]간 작업이었습니다.

1980년대와 1990년대에는 절차 간 분석과 최적화 기술이 학술 연구의 주제였다.그들은 1990년대 초에 Colves Computer Corporation (C4용 "응용 프로그램 컴파일러")와 Folt (Fortent Titan용 컴파일러)의 컴파일러로 상업용 컴파일러 세계에 다시 등장했습니다.이들 컴파일러는 테크놀로지가 상용 컴파일러에서 받아들여질 만큼 충분히 빠르게 만들어질 수 있다는 것을 증명했습니다.그 후 프로시저간 기술은 많은 상용 및 비상용 시스템에 등장했습니다.

플래그와 구현

Unix와 같은

GNU 컴파일러 컬렉션에는 모든 최적화 수준에서 함수의 인라인 기능이 있습니다.앳-O1이것은, 1 회만 콜 됩니다(-finline-functions-once), 。-O2이 제약은 완화된다(-finline-functions디폴트로는 이것은 단일 파일만의 동작이지만 링크 타임 최적화에 의한 동작입니다.-flto 프로그램 ^[1]전체가 됩니다.Clang의 명령줄 인터페이스는 GCC와 유사하지만 GCC는 없습니다.-fwhole-program옵션을 선택합니다.^[8]

LTO에 의해 생성되는 오브젝트 파일에는 링크 시 해석되는 컴파일러 고유의 Intermediate Representation(IR; 중간 표현)이 포함되어 있습니다.이것이 스태틱 라이브러리에서 잘 작동하도록 하기 위해 새로운 GNU 링커에는 필요할 때 컴파일러가 오브젝트 파일을 머신 코드 형식으로 변환할 수 있는 "링커 플러그인" 인터페이스가 있습니다.이 플러그인은 일반적으로 LTO 프로세스를 구동하는 데도 도움이 됩니다.또는 기계 코드와 IR을 모두 포함하는 "팻 LTO" 객체를 생성할 수 있지만, 이 작업은 더 많은 공간을 ^[1]차지합니다.

GCC와 LLVM(Clang) 모두 다양한 프로그래밍 언어에서 IR을 생성할 수 있기 때문에 링크 타임 IPO는 언어 경계를 넘어 발생할 수 있습니다.이는 C 및 C++^[9]에서 가장 많이 볼 수 있지만 LLVM을 사용하면 Rust 및 기타 모든 LLVM 기반 컴파일러에서도 가능합니다.^[10]

비 LTO 옵션

GCC와 Clang은 디폴트로 최적화 레벨2에서 IPO를 수행합니다.단, IPO는 오브젝트 파일 내에서만 실행할 수 있고 비정적 기능을 제거할 수 없기 때문에 LTO가 비활성화되면 최적화 정도가 제한됩니다.후자의 문제에는 비 LTO 솔루션이 있습니다.-fwhole-program스위치를 사용하면, 다음과 같이 가정할 수 있습니다.main()정전기 방지, ^[11]즉 외부에서 볼 수 있습니다.

또 다른 비 LTO 기법은 "기능 섹션"입니다.-ffunction-sections(GCC 및 Clang)로 설정합니다.각 함수를 오브젝트 파일 내의 자체 섹션에 배치함으로써 링커는 참조되지 않은 섹션을 삭제함으로써 IR 없이 데드코드 삭제를 수행할 수 있습니다.--gc-sections변수에도 유사한 옵션을 사용할 수 있지만, 이로 인해 훨씬 더 나쁜 코드가 생성됩니다.^[12]

다른.

인텔 C/C++ 컴파일러는 프로그램 전체의 IPO를 가능하게 합니다.단일 파일에 대해 프로시저 간 최적화를 활성화하기 위한 플래그는 다음과 같습니다.-ip프로그램 내의 모든 파일에 걸쳐 프로시저 간 최적화를 가능하게 하는 플래그는 다음과 같습니다.-ipo를 클릭합니다.^[13][14]

Visual Studio에 통합된 MSVC 컴파일러는 전체 ^[15]프로그램에서 프로시저 간 최적화도 지원합니다.

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

「 」를 참조해 주세요.

• 프로파일 가이드 최적화(PGO)
• 단일 컴파일 유닛

레퍼런스

외부 링크

• C/C++ 컴파일러가 끔찍한 코드를 생성하도록 속이는 방법