컴파일러 최적화

Optimizing compiler

컴퓨팅에서 최적화 컴파일러는 실행 가능한 컴퓨터 프로그램의 속성을 최소화하거나 최대화하는 컴파일러입니다.일반적인 요건은 프로그램 실행 시간, 메모리 공간, 스토리지 크기 및 전력 소비량(마지막 세 가지는 휴대용 컴퓨터에서 널리 사용됨)을 최소화하는 것입니다.

컴파일러 최적화는 일반적으로 일련의 변환 최적화 알고리즘을 사용하여 구현됩니다.이 알고리즘은 프로그램을 가져다가 의미론적으로 동등한 출력 프로그램을 생성하기 위해 더 적은 자원을 사용하거나 더 빨리 실행됩니다.일부 코드 최적화 문제는 NP-complete 또는 결정 불가능한 것으로 나타났습니다.실제로 컴파일러가 작업을 완료할 때까지 기다리는 프로그래머의 의지와 같은 요소들은 컴파일러가 제공할 수 있는 최적화에 상한을 둔다.최적화는 일반적으로 CPU와 메모리를 많이 사용하는 프로세스입니다.과거에는 컴퓨터 메모리 제한도 수행할 수 있는 최적화를 제한하는 주요 요인이었습니다.

이러한 요인 때문에 최적화는 어떤 의미에서든 "최적" 출력을 생성하는 경우가 거의 없으며, 실제로 "최적화"로 인해 성능이 저하될 수 있습니다.오히려 [1]일반적인 프로그램에서 리소스 사용을 개선하기 위한 경험적 접근 방법입니다.

최적화의 종류

최적화에 사용되는 기술은 하나의 문장에서 전체 프로그램에 이르기까지 모든 것에 영향을 미칠 수 있는 다양한 범위로 나눌 수 있습니다.일반적으로 로컬 범위 기술은 글로벌 기술보다 구현하기 쉽지만 결과적으로 더 적은 이득을 가져옵니다.스코프의 예는 다음과 같습니다.

핍홀 최적화
이러한 작업은 보통 기계 코드가 생성된 후 컴파일 프로세스 후반에 수행됩니다.이 최적화 형태는 코드에서 "피크홀을 통해 보기"와 같은 몇 가지 인접한 명령을 검사하여 단일 명령 또는 짧은 명령 [2]시퀀스로 대체할 수 있는지 확인합니다.예를 들어, 값에 2를 곱하는 것은 값을 왼쪽으로 이동하거나 값을 추가하는 것으로 보다 효율적으로 실행할 수 있습니다(이 예도 강도 감소의 인스턴스입니다).
로컬 최적화
이것들은 기본 [3]블록의 로컬 정보만 고려합니다.기본 블록에는 제어 흐름이 없기 때문에 이러한 최적화에는 분석 작업이 거의 필요하지 않으므로 시간을 절약하고 스토리지 요구사항을 줄일 수 있습니다. 그러나 점프 중에도 정보가 보존되지 않습니다.
글로벌 최적화
이것들은 「시술내 방법」이라고도 불리며,[3] 기능 전체에 작용합니다.이로 인해 더 많은 정보를 얻을 수 있지만, 많은 경우 값비싼 계산이 필요합니다.최악의 경우 함수 호출이 발생하거나 글로벌 변수에 액세스할 때 이러한 정보에 대한 정보가 거의 없기 때문에 이러한 가정을 해야 합니다.
루프 최적화
이들은 for 루프 등의 루프를 구성하는 문(예를 들어 루프 불변 코드모션)에 작용합니다.많은 프로그램이 루프 내에서 많은 시간을 [4]소비하기 때문에 루프 최적화는 상당한 영향을 미칠 수 있습니다.
사전 지식형 스토어 최적화
이를 통해 스레드 및 잠금 컨텍스트에서 허용되는 것보다 더 빨리 저장소 작업을 수행할 수 있습니다.이 프로세스에는 어떤 가치가 할당에 의해 저장될지 미리 알 수 있는 방법이 필요합니다.이 완화의 목적은 컴파일러 최적화가 적절하게 동기화된 [5]프로그램의 의미를 보존하는 특정 종류의 코드 재배열을 수행할 수 있도록 하는 것입니다.
프로시저간, 전체 프로그램 또는 링크 타임 최적화
이들은 프로그램의 모든 소스 코드를 분석합니다.추출된 정보의 양이 많다는 것은 최적화가 단일 기능 내에서 로컬 정보에만 접근할 수 있는 경우에 비해 더 효과적일 수 있다는 것을 의미한다.이러한 종류의 최적화를 통해 새로운 기술을 수행할 수도 있습니다.예를 들어 함수에 대한 호출이 함수 본문의 복사본으로 대체되는 함수 인라인입니다.
기계코드 최적화 및 객체코드 최적화
모든 실행 가능한 기계 코드가 연결된 후 프로그램의 실행 가능한 작업 이미지를 분석합니다.일반적인 명령 시퀀스를 축소하여 공간을 절약하는 매크로 압축과 같이 제한된 범위에서 적용할 수 있는 기술 중 일부는 실행 가능한 작업 이미지 전체를 [6]분석에 사용할 수 있을 때 더 효과적입니다.

스코프 최적화 외에, 최적화에는 다음의 2개의 일반적인 카테고리가 있습니다.

프로그래밍 언어에 의존하지 않는 경우와 언어에 의존하지 않는 경우
대부분의 고급 언어는 공통 프로그래밍 구조와 추상화를 공유합니다. 결정(if, switch, case), 루프(for, while, repeat).할 때까지..while) 및 캡슐화(절차, 객체)를 지정합니다.따라서 유사한 최적화 기술을 여러 언어에서 사용할 수 있습니다.그러나 특정 언어 기능은 일부 최적화를 어렵게 합니다.예를 들어 C 및 C++에 포인터가 존재하기 때문에 어레이 액세스를 최적화하는 것이 어렵습니다(에일리어스 분석 참조).그러나 PL/I와 같은 언어(포인터도 지원)는 다양한 방법으로 더 나은 성능을 달성하기 위해 정교한 최적화 컴파일러를 사용할 수 있습니다.반대로 일부 언어 기능은 특정 최적화를 쉽게 합니다.예를 들어, 일부 언어에서는 기능에 부작용이 허용되지 않습니다.그러므로, 만약 프로그램이 같은 인수로 같은 함수에 여러 개의 호출을 한다면, 컴파일러는 함수의 결과를 단 한 번만 계산할 필요가 있다고 즉시 추론할 수 있다.기능이 부작용을 일으킬 수 있는 언어에서는 다른 전략이 가능합니다.최적화 도구에서는 어떤 함수에 부작용이 없는지 확인하고 이러한 최적화를 제한하여 부작용이 없는 함수를 만들 수 있습니다.이 최적화는 옵티마이저가 호출된 함수에 액세스할 수 있는 경우에만 가능합니다.
머신에 의존하지 않는 경우와 머신에 의존하지 않는 경우의 비교
추상 프로그래밍 개념(루프, 오브젝트, 구조)으로 동작하는 많은 최적화는 컴파일러의 타깃 머신과는 독립적이지만 가장 효과적인 최적화의 대부분은 타깃 플랫폼의 특수 기능을 가장 잘 활용하는 최적화입니다.예를 들어, 0이 아닌 경우 감소 레지스터 및 분기 등 여러 작업을 동시에 수행하는 명령이 있습니다.

로컬 머신 의존 최적화의 예를 다음에 나타냅니다.레지스터를 0으로 설정하려면 레지스터 값을 상수로 설정하는 명령에서 상수 '0'을 사용하는 것이 좋습니다.덜 명백한 방법은 레지스터를 XOR하는 것입니다.어떤 명령어를 사용할지는 컴파일러에 달려 있습니다.많은 RISC 머신에서는, 양쪽 모두의 길이가 같고, 시간도 같기 때문에, 양쪽의 순서가 동등하게 적절합니다.인텔 x86 패밀리 등 다른 많은 마이크로프로세서에서는 XOR 배리언트가 더 짧고 아마도 더 빠릅니다.즉시 피연산자를 디코딩하거나 내부 "즉시 피연산자 레지스터"를 사용할 필요가 없기 때문입니다.잠재적인 문제는 XOR에 의해 레지스터의 이전 값에 대한 데이터 의존성이 발생하여 파이프라인 스톨이 발생할 수 있다는 것입니다.그러나 프로세서는 종종 레지스터의 XOR를 특별한 케이스로 가지고 있어 정지하지 않습니다.

최적화에 영향을 미치는 요인

기계 자체
최적화를 수행할 수 있고 수행해야 하는 많은 선택사항은 대상 시스템의 특성에 따라 달라집니다.머신 기술 파라미터를 변경하는 것만으로 컴파일러 코드의 단일 조각을 사용하여 다른 머신을 최적화할 수 있도록 이러한 머신 의존 요소 중 일부를 파라미터화할 수 있습니다.GNU 프로젝트의 GCC와 LLVM 컴파일러 인프라스트럭처의 Clang은 이 접근방식을 따르는 컴파일러 최적화의 예입니다.
타깃 CPU의 아키텍처
CPU 레지스터 수:어느 정도 레지스터가 많을수록 성능을 최적화하기가 쉬워집니다.로컬 변수는 스택이 아닌 레지스터로 할당할 수 있습니다.임시/중간 결과는 메모리에 쓰거나 메모리에서 다시 읽지 않고 레지스터에 남길 수 있습니다.
  • RISC vs CISC: CISC 명령어세트는 명령어 길이가 가변적인 경우가 많아 사용할 수 있는 명령어 수가 많아 명령어마다 시간이 걸릴 수 있습니다.RISC 명령어세트는 보통 일정한 길이이며 예외는 거의 없으며 레지스터와 메모리 동작의 조합이 적으며 명령 발행률(시간 간격당 완료된 명령의 수, 보통 클럭 사이클의 정수 배수)은 다음과 같습니다.일반적으로 메모리 지연 시간이 요인이 아닌 경우에는 일정합니다.CISC는 보통 RISC보다 더 많은 대체 기능을 제공하므로 특정 작업을 수행하는 방법은 여러 가지가 있습니다.컴파일러는 다양한 명령 중 상대적인 비용을 알고 최적의 명령 시퀀스를 선택해야 합니다(명령어 선택 참조).
  • 파이프라인:파이프라인은 기본적으로 조립라인으로 분할된 CPU입니다.명령 실행을 명령 디코드, 주소 디코드, 메모리 페치, 레지스터 페치, 계산, 레지스터 스토어 등 다양한 단계로 분할함으로써 CPU의 일부를 다른 명령에 사용할 수 있습니다.하나의 명령어는 레지스터 스토어 단계에 있을 수 있고 다른 명령어는 레지스터 가져오기 단계에 있을 수 있습니다.파이프라인 충돌은 파이프라인의 한 단계에 있는 명령이 파이프라인의 다른 명령 앞에 있는 다른 명령의 결과에 의존하지만 아직 완료되지 않은 경우에 발생합니다.파이프라인 경합으로 인해 파이프라인 정지(CPU가 경합이 해결되기를 기다리는 동안 사이클을 낭비)가 발생할 수 있습니다.
컴파일러는 파이프라인 정지 빈도를 낮추기 위해 명령을 예약하거나 순서를 변경할 수 있습니다.
  • 기능 유닛 수:일부 CPU에는 여러 ALU와 FPU가 있습니다.이를 통해 여러 명령을 동시에 실행할 수 있습니다.어떤 명령이 어떤 다른 명령과 페어링할 수 있는지("페어링"은 두 개 이상의 명령이 동시에 실행됨) 및 어떤 기능 유닛이 어떤 명령을 실행할 수 있는지에 제한이 있을 수 있습니다.또한 파이프라인 충돌과 유사한 문제가 있습니다.
여기서도 다양한 기능 유닛에 실행 명령이 완전히 공급되도록 명령을 스케줄링해야 합니다.
기계의 아키텍처
  • 캐시 크기(256kiB~12MiB) 및 유형(직접 매핑, 2-/4-/8-/16-way 어소시에이션, 완전 어소시에이션):인라인 확장이나 루프 언롤링 등의 기술은 생성된 코드의 크기를 증가시켜 코드 인접성을 감소시킬 수 있습니다.활용도가 높은 코드 섹션(다양한 알고리즘의 내부 루프 등)이 갑자기 캐시에 들어가지 않으면 프로그램이 급격히 느려질 수 있습니다.또한 완전히 연관되지 않은 캐시는 채워지지 않은 캐시에서도 캐시 충돌이 발생할 가능성이 높습니다.
  • 캐시/메모리 전송 속도:이를 통해 컴파일러는 캐시 누락에 대한 패널티를 알 수 있습니다.이것은 주로 전문 어플리케이션에서 사용됩니다.
생성된 코드의 용도
디버깅
응용 프로그램을 작성하는 동안 프로그래머는 재컴파일 및 테스트를 자주 하기 때문에 컴파일이 빨라야 합니다.이것이 대부분의 최적화가 테스트/디버깅 단계에서 의도적으로 회피되는 이유 중 하나입니다.또한, 프로그램 코드는 보통 심볼릭 디버거를 사용하여 "스텝 스루"(프로그램 애니메이션 참조)되며, 변환, 특히 코드를 재정렬하는 변환을 최적화하는 것은 출력 코드를 원래 소스 코드의 라인 번호와 관련짓는 것을 어렵게 할 수 있습니다.이로 인해 디버깅툴과 디버깅툴을 사용하는 프로그래머가 혼동을 일으킬 수 있습니다.
범용 용도
패키지화된 소프트웨어는 같은 명령 세트를 공유하지만 타이밍, 캐시 또는 메모리 특성이 다른 다양한 머신과 CPU에서 실행되는 경우가 많습니다.그 결과 코드는 특정 CPU에 맞춰져 있지 않거나 가장 일반적인 CPU에서 가장 잘 동작하도록 조정되어도 다른 CPU에서는 정상적으로 동작합니다.
특수 용도
소프트웨어가 하나 또는 몇 대의 매우 유사한 머신에서 사용되도록 컴파일 되어 있고, 이미 알려진 특성을 가진 경우 컴파일러는 생성된 코드를 특정 머신에 맞게 크게 조정할 수 있습니다.중요한 특수한 경우로는 병렬 프로세서 및 벡터 프로세서용으로 설계된 코드가 있으며, 이 코드에는 특수 병렬화 컴파일러가 사용됩니다.
임베디드 시스템
이것들은 특수한 용도로 사용되는 일반적인 경우입니다.임베디드 소프트웨어는 정확한 CPU 및 메모리 크기에 맞게 엄격하게 조정할 수 있습니다.또한 코드 속도보다 시스템 비용 또는 신뢰성이 더 중요할 수 있습니다.예를 들어 임베디드 소프트웨어용 컴파일러는 보통 속도를 희생하면서 코드 크기를 줄이는 옵션을 제공합니다.메모리는 임베디드 컴퓨터의 주요 비용이기 때문입니다.코드의 타이밍은 가능한 한 빠르지 않고 예측 가능해야 하므로 코드 캐싱은 이를 필요로 하는 컴파일러 최적화와 함께 비활성화될 수 있습니다.

공통 테마

대부분의 컴파일러 최적화 기법은 다음과 같은 테마를 가지고 있으며, 이는 때때로 충돌합니다.

일반적인 케이스의 최적화
일반적인 경우 저속 경로를 희생하여 고속 경로를 허용하는 고유한 속성을 가질 수 있습니다.패스트 패스를 가장 자주 사용하면 전체적인 퍼포먼스가 향상됩니다.
용장성 회피
이미 계산된 결과를 다시 계산하지 않고 나중에 사용하기 위해 재사용하고 저장합니다.
코드 감소
불필요한 계산과 중간값을 삭제합니다.CPU, 캐시 및 메모리의 작업량이 적으면 일반적으로 실행 속도가 빨라집니다.또는 임베디드 시스템에서는 코드 수가 적을수록 제품 비용이 절감됩니다.
분기 없는 코드라고도 하는 직선 코드를 사용하여 점프를 줄임
덜 복잡한 코드.점프(조건부 또는 조건부 분기)는 명령어 프리페치를 방해하여 코드 속도를 늦춥니다.인라인 또는 루프 언롤링을 사용하면 바이너리 파일 크기를 반복 코드 길이만큼 늘리는 대신 분기를 줄일 수 있습니다.이것은 몇 개의 기본 블록을 하나로 병합하는 경향이 있습니다.
지역
시간 내에 밀접하게 액세스되는 코드와 데이터는 참조의 공간적 인접성을 높이기 위해 메모리에 밀접하게 배치해야 합니다.
메모리 계층 이용
메모리 계층의 각 레벨에 따라 메모리에 대한 액세스 비용이 점점 더 비싸지고 있습니다.따라서 가장 일반적으로 사용되는 항목을 먼저 레지스터에 넣은 다음 캐시하고 메인 메모리에 저장한 후 디스크로 이동합니다.
병렬화
명령, 메모리 또는 스레드 수준에서 여러 계산을 병렬로 수행할 수 있도록 작업을 재정렬합니다.
정보가 정확할수록 좋다
컴파일러는 정보가 더 정확할수록 이러한 최적화 기법 중 하나 또는 모두를 더 잘 사용할 수 있습니다.
런타임 메트릭이 도움이 됩니다.
테스트 실행 중에 수집된 정보는 프로파일 유도 최적화에 사용할 수 있습니다.JIT 컴파일러는 실행 시 수집된 정보를 최소한의 오버헤드로 사용하여 최적화를 동적으로 개선할 수 있습니다.
강도 저하
복잡하거나 어렵거나 비용이 많이 드는 작업을 단순한 작업으로 대체하십시오.예를 들어, 나눗셈을 상수로 역수로 곱셈으로 치환하거나 유도 변수 분석을 사용하여 곱셈을 루프 인덱스로 덧셈으로 치환합니다.

특정 기술

루프 최적화

주요 기사:루프 최적화

주로 루프에서 동작하도록 설계된 최적화 기법에는 다음과 같은 것이 있습니다.

유도 변수 분석
대략적으로, 루프의 변수가 인덱스 변수의 단순한 선형 함수인 경우 다음과 같습니다.j := 4*i + 1루프 변수가 변경될 때마다 적절히 갱신할 수 있습니다.이는 강도를 감소시키는 것으로 인덱스 변수의 정의가 [7]데드 코드가 될 수도 있습니다.이 정보는 특히 경계 검사 제거 및 종속성 분석에도 유용합니다.
루프 핵분열 또는 루프 분포
루프 핵분열은 루프를 동일한 지수 범위에 걸쳐 여러 루프로 분할하려고 시도하지만 각각은 루프 본체의 일부만 취합니다.이를 통해 루프에서 액세스되는 데이터와 루프 본체의 코드가 모두 참조의 인접성을 향상시킬 수 있습니다.
루프 퓨전 또는 루프 결합 또는 루프 래밍 또는 루프 방해
루프 오버헤드를 줄이기 위한 또 다른 기술입니다.인접한 2개의 루프가 컴파일 시에 그 번호가 알려져 있는지 여부에 관계없이 동일한 횟수를 반복하는 경우, 서로의 데이터를 참조하지 않는 한 두 개의 본문을 결합할 수 있습니다.
루프 반전
이 기술은 루프 실행 시 루프를 조건부로 감싼 실행/시간 중 루프(repeat/until이라고도 함)로 변경하여 점프 횟수를 2회 줄입니다.이렇게 하면 상태 확인(코드 크기 증가)이 중복되지만 일반적으로 점프가 파이프라인 정지를 일으키기 때문에 더 효율적입니다.또한 컴파일 시에 초기 조건이 알려져 있고 부작용이 없는 것으로 알려진 경우 if 가드를 건너뛸 수 있습니다.
루프 인터체인지
이러한 최적화는 내부 루프를 외부 루프와 교환합니다.루프 변수가 배열에 인덱싱되면 이러한 변환을 통해 배열의 레이아웃에 따라 참조 인접성이 향상될 수 있습니다.
루프 불변 코드모션
반복할 때마다 루프 내부에서 수량이 계산되고 그 값이 각 반복마다 동일할 경우 루프 외부에 호이스트하여 루프가 [4]시작되기 전에 한 번만 값을 계산하는 것이 효율이 크게 향상됩니다.이는 특히 어레이 상의 루프에 의해 생성되는 주소 계산식에서 중요합니다.모든 코드를 루프 외부에 호이스트 하는 것이 안전하다고는 할 수 없기 때문에, 올바른 실장을 위해서는, 이 기술을 루프 인버전시에 사용할 필요가 있습니다.
루프 네스트 최적화
매트릭스 곱셈과 같은 일부 퍼베이시브 알고리즘은 캐시 동작이 매우 불량하고 메모리 액세스가 과도합니다.루프 네스트 최적화는 작은 블록에 걸쳐 작업을 수행하고 루프 교환을 사용함으로써 캐시 히트 수를 늘립니다.
루프 반전
루프 반전은 값이 인덱스 변수에 할당되는 순서를 반대로 합니다.이는 의존성을 제거하고 다른 최적화를 가능하게 하는 데 도움이 되는 미묘한 최적화입니다.또한 일부 아키텍처에서는 루프인덱스가 감소했을 때 실행 중인 프로그램이 루프를 종료하기 위해 충족해야 하는 조건이 0과의 비교가 되기 때문에 루프 반전은 더 작은 코드에 기여합니다.이 명령어는 숫자와의 비교와는 달리 파라미터가 필요 없는 특수한 명령인 경우가 많습니다.따라서 루프 반전을 사용하여 파라미터 저장에 필요한 바이트 수를 절약할 수 있습니다.또한 비교 번호가 플랫폼의 워드 크기를 초과할 경우 표준 루프 순서로 비교를 평가하기 위해 여러 명령을 실행해야 합니다.이것은 루프 반전과는 다릅니다.
루프 언롤링
언롤링은 루프 상태를 테스트하는 횟수와 점프 횟수를 줄이기 위해 루프 본체를 여러 번 복제합니다.이 경우 명령 파이프라인에 장애가 발생하여 성능이 저하됩니다."점프 수가 적은" 최적화가 이루어집니다.루프를 완전히 풀면 모든 오버헤드가 제거되지만 컴파일 시 반복 횟수를 알아야 합니다.
루프 분할
루프 분할은 루프를 여러 개의 루프로 분할하여 단순화하거나 의존관계를 제거하려고 합니다.이 루프는 같은 본체를 가지지만 인덱스 범위의 서로 다른 인접 부분에 걸쳐 반복됩니다.유용한 특수한 경우는 루프 박리입니다.루프에 들어가기 전에 그 반복을 개별적으로 실행함으로써 문제가 있는 첫 번째 반복으로 루프를 단순화할 수 있습니다.
루프를 스위칭하지 않다
unswitching은 조건의 if 및 else 구를 각각 복제하여 루프 내부에서 루프 외부로 조건을 이동합니다.
소프트웨어 파이프라인화
반복에서 수행된 작업이 여러 부분으로 분할되고 여러 반복에 걸쳐 수행되도록 루프가 재구성됩니다.타이트 루프에서는 이 기술은 로드와 값 사용 사이의 지연을 숨깁니다.
자동 병렬화
루프는 멀티코어 머신을 포함한 Shared-Memory Multiprocessor(SMP; 공유 메모리 멀티프로세서) 머신에서 여러 프로세서를 동시에 이용하기 위해 멀티스레드 또는 벡터화(또는 그 양쪽 모두) 코드로 변환됩니다.

데이터 흐름 최적화

데이터 흐름 분석을 기반으로 한 데이터 흐름 최적화는 주로 제어 흐름 그래프의 제어 가장자리에 의해 데이터의 특정 속성이 전파되는 방식에 따라 달라집니다.그 중 몇 가지는 다음과 같습니다.

공통 하위 표현식 제거
표현 중에(a + b) - (a + b)/4, 「공통 서브 표현식」은, 중복된 서브 표현식을 참조합니다.(a + b). 이 기술을 구현하는 컴파일러는 다음과 같은 사실을 인식합니다.(a + b)값은 변경되지 않으므로 한 [8]번만 계산하십시오.
지속적인 접힘 및 전파
[9] 상수로 구성된 식을 대체합니다(예:3 + 5(최종값 포함)8런타임에 계산을 하지 않고 컴파일 시).대부분의 현대 언어에서 사용됩니다.
유도 변수 인식 및 제거
유도 변수 분석에 대한 위의 설명을 참조하십시오.
에일리어스 분류 및 포인터 분석
포인터가 있는 경우 메모리 위치가 할당될 때 변수가 변경될 수 있기 때문에 최적화가 전혀 어렵습니다.어떤 포인터가 어떤 변수에 별칭을 지정할 수 있는지 지정함으로써 관련 없는 포인터를 무시할 수 있습니다.
데드스토어 제거
변수의 수명이 끝나거나 첫 번째 값을 덮어쓰는 후속 할당 때문에 후속적으로 읽히지 않는 변수에 대한 할당 제거.

SSA 기반 최적화

이러한 최적화는 프로그램을 Static Single Assignment라는 특수 형식으로 변환한 후 수행되도록 고안되었습니다. 이 형식에서는 모든 변수가 한 곳에서만 할당됩니다.SSA가 없어도 기능하는 것도 있습니다만, SSA가 있으면 가장 효과적입니다.다른 섹션에 나열된 많은 최적화도 레지스터 할당과 같은 특별한 변경 없이 유용합니다.

글로벌 값 번호부여부
GVN은 프로그램의 값 그래프를 작성한 후 동등한 식에 의해 계산되는 값을 결정함으로써 용장성을 제거합니다.GVN은 일반적인 서브표현 삭제에서는 확인할 수 없는 용장성을 특정할 수 있습니다.또, 그 반대의 경우도 마찬가지입니다.
스파스 조건부 상수 전파
연속 전파, 연속 폴딩 및 데드 코드 제거를 결합하여 개별적으로 [10][11]실행함으로써 가능한 것을 개선합니다.이 최적화에 의해 프로그램이 심볼적으로 실행되어 상수 값이 동시에 전파되며 도달 불능이 되는 제어 흐름 그래프의 일부가 제거됩니다.

코드 생성기 최적화

레지스터 할당
가장 자주 사용되는 변수는 가장 빠른 액세스를 위해 프로세서 레지스터에 보관해야 합니다.레지스터에 넣을 변수를 찾기 위해 간섭 그래프가 생성됩니다.각 변수는 꼭지점이며 두 변수가 동시에 사용되는 경우(교차하는 간 범위가 있음) 둘 사이에 모서리가 있습니다.이 그래프는 예를 들어 Chaitin의 알고리즘을 사용하여 레지스터와 동일한 수의 색을 입힙니다.색칠에 실패하면 하나의 변수가 메모리에 "스필"되고 색칠이 재시도됩니다.
명령 선택
대부분의 아키텍처, 특히 CISC 아키텍처와 많은 어드레싱 모드를 사용하는 아키텍처는 완전히 다른 일련의 명령을 사용하여 특정 작업을 수행하는 여러 가지 다른 방법을 제공합니다.명령 선택기의 역할은 낮은 수준의 중간 표현에서 어떤 명령을 구현할 것인지 선택하는 것을 전반적으로 잘 수행하는 것입니다.예를 들어 68000 시리즈의 많은 프로세서 및 x86 아키텍처에서는 복잡한 어드레싱 모드를 "lea 25 (a1, d5*4)", a0"과 같은 문장으로 사용할 수 있습니다.이것에 의해, 1개의 명령으로 보다 적은 스토리지로 대량의 연산을 실행할 수 있습니다.
명령 스케줄링
명령어 스케줄링은 최신 파이프라인 프로세서에 중요한 최적화입니다.이것에 의해, 원래의 의미를 유지하면서, 의존하지 않는 명령어를 클러스터링 하는 것으로써, 파이프라인의 정지나 거품을 회피할 수 있습니다.
재물질화
재소재화는 메모리로부터 값을 로드하는 대신 값을 재계산하여 메모리 액세스를 방지합니다.이는 레지스터 할당과 함께 실행되어 유출을 방지합니다.
코드 팩터링
여러 코드 시퀀스가 동일하거나 파라미터화 또는 순서를 변경할 수 있는 경우 공유 서브루틴 호출로 대체할 수 있습니다.이것은 서브루틴 셋업 및 경우에 따라서는 테일 [12]재귀용 코드를 공유할 수 있습니다.
트램폴린
많은[citation needed] CPU에서는 낮은 메모리에 액세스하기 위한 서브루틴 호출 명령이 더 작습니다.컴파일러는 코드 본문에 이러한 작은 호출을 사용함으로써 공간을 절약할 수 있습니다.메모리가 적은 점프 명령은 임의의 주소에서 루틴에 액세스할 수 있습니다.이를 통해 코드 [12]팩터링을 통한 공간 절약이 배가됩니다.
계산 순서 변경
재구성 컴파일러는 정수 선형 프로그래밍에 기반하여 데이터 인접성을 높이고 연산 순서를 변경함으로써 더 많은 병렬성을 노출합니다.공간 최적화 컴파일러는 서브루틴에 인수화할 수 있는 시퀀스를 길게 하기 위해 코드를 재정렬할 수 있습니다.

기능 언어 최적화

이들 대부분은 비기능 언어에도 적용되지만 Lisp나 ML과 같은 기능 언어에서 유래하거나 특히 중요한 언어입니다.

테일콜 최적화
함수 호출은 스택스페이스를 소비하며 명령 캐시의 전달 및 플러싱 파라미터와 관련된 오버헤드를 포함합니다.테일 재귀 알고리즘은 테일 재귀 제거 또는 테일 콜 최적화라고 불리는 프로세스를 통해 반복으로 변환할 수 있습니다.
삼림 벌채(데이터 구조 융합)
일련의 변환이 목록에 적용되는 것이 일반적인 언어에서는 삼림 벌채가 중간 데이터 구조의 구성을 제거하려고 시도한다.
부분평가

기타 최적화

경계 검사 제거
Java와 같은 많은 언어는 모든 어레이 액세스에 대해 경계 검사를 시행합니다.이는 과학 코드와 같은 특정 애플리케이션에서 심각한 성능 병목 현상입니다.경계 검사 제거를 통해 컴파일러는 인덱스가 유효한 경계 내에 있어야 한다고 판단할 수 있는 많은 상황에서 경계 검사를 안전하게 제거할 수 있습니다. 예를 들어, 단순한 루프 변수인지 여부입니다.
분기 오프셋 최적화(머신에 따라 다름)
표적에 도달하는 가장 짧은 분기 변위를 선택합니다.
코드 블록 순서 변경
코드 블록 순서 변경은 조건부 분기를 줄이고 참조 인접성을 개선하기 위해 프로그램 내 기본 블록의 순서를 변경합니다.
데드 코드 제거
프로그램의 동작에 영향을 주지 않는 명령(예: 데드 코드)을 제거합니다.이것에 의해, 코드 사이즈가 작아져 불필요한 계산이 불필요하게 됩니다.
불변량 제외(루프 불변량)
조건이 충족되었을 때와 충족되지 않았을 때 모두 식을 수행할 경우 조건문 밖에서 한 번만 작성할 수 있습니다.마찬가지로 특정 유형의 표현식(예를 들어 변수에 상수 할당)이 루프 내에 나타나면 여러 번 실행하든 한 번만 실행하든 효과가 같기 때문에 루프 밖으로 이동할 수 있습니다.이것은 완전 용장성 제거라고도 불립니다.유사하지만 보다 강력한 최적화는 부분 용장성 제거(PRE)입니다.
인라인 확장 또는 매크로 확장
일부 코드가 프로시저를 호출하면, 프로시저 본문을 콜링 코드내에 직접 삽입할 수 있습니다.이렇게 하면 프로시저 콜에 관련된 오버헤드가 절감될 뿐만 아니라 다양한 파라미터 고유의 최적화를 할 수 있는 기회도 얻을 수 있습니다.단, 프로시저가 인라인으로 호출될 때마다 프로시저 본문이 복제됩니다.일반적으로 인라이닝은 소규모 프로시저에 다수의 콜을 발신하는 퍼포먼스가 중요한 코드에 도움이 됩니다."점프 수가 적은" 최적화가[sentence fragment] 이루어집니다.명령형 프로그래밍 언어의 문장도 이러한 최적화의 한 예입니다.명령문은 함수 호출을 사용하여 구현할 수 있지만, 거의 항상 코드 인라이닝으로 구현됩니다.
점프 스레드화
이 최적화에서는, 같은 조건의 전부 또는 부분적으로 예측되는 연속적인 조건부 점프가 병합된다.
예.,if (c) { foo; } if (c) { bar; }로.if (c) { foo; bar; },
그리고.if (c) { foo; } if (!c) { bar; }로.if (c) { foo; } else { bar; }.
매크로 압축
공통 코드 시퀀스를 인식하고 공통 코드를 포함하는 서브 프로그램("코드 매크로")을 생성하여 공통 코드 시퀀스의 발생을 대응하는 서브 [6]프로그램에 대한 호출로 대체하는 공간 최적화입니다.이는 모든 코드가 존재할 때 기계 코드 최적화로 가장 효과적으로 수행됩니다.이 기술은 마이크로컴퓨터의 [13]매크로 스피트볼 구현에 사용되는 해석 바이트 스트림의 공간을 절약하기 위해 처음 사용되었습니다.주어진 코드 세그먼트에 필요한 공간을 최소화하는 최적의 매크로 세트를 결정하는 문제는 [6]NP-완전하다고 알려져 있지만 효율적인 휴리스틱스는 거의 최적의 [14]결과를 얻을 수 있습니다.
캐시 충돌 감소
(예를 들어 페이지 내 정렬을 방해함)
스택 높이 감소
식 트리를 재정렬하여 식 평가에 필요한 리소스를 최소화합니다.
순서 변경 테스트
어떤 조건의 두 가지 테스트가 있는 경우, 먼저 간단한 테스트(예를 들어 변수와 무엇인가를 비교하는 것)와 그 다음 복잡한 테스트(예를 들어 함수 호출이 필요한 테스트)를 처리할 수 있습니다.이 기술은 게으른 평가를 보완하지만 테스트가 서로 종속되지 않을 때만 사용할 수 있습니다.이것은, 시멘틱스 단락에 의해서 곤란해질 가능성이 있습니다.

프로시저간 최적화

프로시저간 최적화는 프로시저와 파일 경계를 넘어 전체 프로그램에서 작동합니다.국소부 및 글로벌부의 협력을 받아 시술내 담당자와 긴밀히 협력합니다.일반적인 프로시저 간 최적화에는 프로시저 인라인화, 프로시저 간 데드코드 제거, 프로시저 간 상수 전파 및 프로시저 순서 변경 등이 있습니다.평소처럼 컴파일러는 실제 최적화 전에 프로시저 간 분석을 수행해야 합니다.프로시저 간 분석에는 에일리어스 분석, 어레이 액세스 분석 및 콜 그래프 구축이 포함됩니다.

프로시저간 최적화는 SGI, Intel, Microsoft 및 Sun Microsystems의 최신 상용 컴파일러에서 일반적입니다.오랫동안 오픈 소스 GCC는 강력한 프로시저 간 분석과 최적화가 부족하다는 비판을[citation needed] 받았으나 현재는 [citation needed]개선되고 있습니다.완전한 분석과 최적화 인프라스트럭처를 갖춘 또 다른 오픈 소스 컴파일러는 Open64입니다.

프로시저간 분석에 필요한 추가 시간과 공간이 있기 때문에 대부분의 컴파일러는 기본적으로 이 작업을 수행하지 않습니다.사용자는 컴파일러에 프로시저 간 분석 및 기타 고가의 최적화를 활성화하도록 지시하기 위해 컴파일러 옵션을 명시적으로 사용해야 합니다.

실제 고려 사항

컴파일러가 실행할 수 있는 최적화에는 컴파일 시간이 거의 걸리지 않는 단순하고 간단한 것부터 상당한 컴파일 [15]시간을 필요로 하는 정교하고 복잡한 것까지 다양합니다.따라서 컴파일러는 종종 제어 명령 또는 프로시저에 옵션을 제공하여 컴파일러 사용자가 어느 정도의 최적화를 요청할지를 선택할 수 있도록 합니다. 예를 들어 IBM FORTRAN H 컴파일러는 사용자가 최적화, 레지스터 레벨에서의 최적화 또는 [16]전체 최적화를 지정하지 않도록 합니다.2000년대까지 Clang과 같은 컴파일러에는 익숙한 것부터 시작하여 다양한 최적화 옵션에 영향을 줄 수 있는 다수의 컴파일러 명령어 옵션이 일반적으로 제공되었습니다.-O2전환합니다.[17]

최적화를 분리하는 접근방식은 이른바 포스트 패스 옵티마이저를 사용하는 것입니다(일부 [18]상용 버전은 1970년대 후반 메인프레임 소프트웨어로 거슬러 올라갑니다).이러한 툴은 최적화 컴파일러의 실행 가능 출력을 가져와 더욱 최적화합니다.포스트 패스 옵티마이저는 보통 어셈블리 언어 또는 머신 코드 수준에서 작동합니다(프로그램의 중간 표현을 최적화하는 컴파일러와는 대조적으로).예를 들어 1980년대의 Portable C 컴파일러(PCC)가 있습니다.이 컴파일러는 생성된 어셈블리 [19]코드에 대한 사후 최적화를 실행하는 옵션 패스를 가지고 있습니다.

또 다른 고려사항은 최적화 알고리즘이 복잡하고 특히 크고 복잡한 프로그래밍 언어를 컴파일할 때 생성된 코드에 오류가 발생하거나 컴파일 중에 내부 오류가 발생하는 버그가 포함될 수 있다는 것입니다.어떤 종류의 컴파일러 오류도 사용자에게 혼란을 줄 수 있지만, 최적화 로직이 [20]고장났다는 것은 분명하지 않기 때문에 특히 그렇습니다.내부 에러의 경우, 이 문제는 컴파일러의 최적화 로직을 코드화하여 장애가 트랩되고 경고 메시지가 발행되며 컴파일러의 나머지 컴파일이 성공적으로 [21]완료되도록 하는 "페일 세이프" 프로그래밍 기술에 의해 부분적으로 개선될 수 있습니다.

역사

1960년대의 초기 컴파일러들은 주로 코드 컴파일을 정확하고 효율적으로 하는 것에 주로 관심을 가졌기 때문에 컴파일 시간이 주요 관심사였다.주목할 만한 초기 최적화 컴파일러는 1960년대 [16]후반의 IBM FORTRAN H 컴파일러였다.몇 가지 고급 기술을 개척한 최초의 중요한 최적화 컴파일러 중 하나는 The Design of a Optimizing Compiler (1975)[22]에서 설명한 BLIS(1970)입니다.1980년대 후반에는 컴파일러의 최적화가 충분히 효과적이어서 어셈블리 언어의 프로그래밍은 감소했습니다.이는 RISC 칩과 명령 스케줄링 및 추측 실행과 같은 고급 프로세서 기능의 개발과 함께 진화했습니다. 이 기능은 인간이 작성한 [citation needed]어셈블리 코드가 아닌 컴파일러를 최적화하도록 설계되었습니다.

정적 코드 분석 목록

「 」를 참조해 주세요.

레퍼런스

  1. ^ Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools. Reading, Massachusetts: Addison-Wesley. p. 585. ISBN 0-201-10088-6.
  2. ^ 아호, 세티, 울만, 컴파일러, 페이지 554
  3. ^ a b Cooper, Keith D.; Torczon, Linda (2003) [2002-01-01]. Engineering a Compiler. Morgan Kaufmann. pp. 404, 407. ISBN 978-1-55860-698-2.
  4. ^ a b Aho, Sethi, 및 Ulman, 컴파일러, 페이지 596.
  5. ^ "MSDN - Prescient Store Actions". Microsoft. Retrieved 2014-03-15.
  6. ^ a b c Clinton F. Goss (August 2013) [First published June 1986]. Machine Code Optimization - Improving Executable Object Code (PDF) (Ph.D. dissertation). Vol. Computer Science Department Technical Report #246. Courant Institute, New York University. arXiv:1308.4815. Bibcode:2013arXiv1308.4815G. Retrieved 22 Aug 2013.
  7. ^ Aho, Sethi, 및 Ulman, 컴파일러, 596–598페이지.
  8. ^ Aho, Sethi, 및 Ulman, 컴파일러, 592-594페이지.
  9. ^ Steven Muchnick; Muchnick and Associates (15 August 1997). Advanced Compiler Design Implementation. Morgan Kaufmann. pp. 329–. ISBN 978-1-55860-320-2. constant folding.
  10. ^ Wegman, Mark N., Zadek, F. Kenneth."조건부로 일정한 전파"ACM Transactions on Programming Languages and Systems, 13(2), 1991년 4월, 181-210페이지.
  11. ^ 클릭, 클리포드와 쿠퍼, 키스프로그래밍 언어와 시스템에 관한 ACM 트랜잭션(Combining Analysis, Combining Optimizations on Programming Language and Systems, 1995년 3월, 181-196페이지)
  12. ^ a b Cx51 컴파일러 매뉴얼, 버전 09.2001, p155, Keil Software Inc.
  13. ^ Robert B. K. Dewar; Martin Charles Golumbic; Clinton F. Goss (August 2013) [First published October 1979]. MICRO SPITBOL. Computer Science Department Technical Report. Vol. No. 11. Courant Institute of Mathematical Sciences. arXiv:1308.6096. Bibcode:2013arXiv1308.6096D.
  14. ^ Martin Charles Golumbic; Robert B. K. Dewar; Clinton F. Goss (1980). "Macro Substitutions in MICRO SPITBOL - a Combinatorial Analysis". Proc. 11th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, Utilitas Math., Winnipeg, Canada. 29: 485–495.
  15. ^ 아호, 세티, 울만, 컴파일러, 15페이지
  16. ^ a b 아호, 세티, 울만, 컴파일러, 페이지 737
  17. ^ Guelton, Serge (August 5, 2019). "Customize the compilation process with Clang: Optimization options". Red Hat.
  18. ^ Cobol 환경을 위한 소프트웨어 엔지니어링.Portal.acm.org 를 참조해 주세요.2013년 8월 10일 취득.
  19. ^ Aho, Sethi, 및 Ulman, 컴파일러, 페이지 736.
  20. ^ Sun, Chengnian; et al. (July 18–20, 2016). "Toward understanding compiler bugs in GCC and LLVM". ISSTA 2016: Proceedings of the 25th International Symposium on Software Testing and Analysis. Issta 2016: 294–305. doi:10.1145/2931037.2931074. ISBN 9781450343909. S2CID 8339241.
  21. ^ Schilling, Jonathan L. (August 1993). "Fail-safe programming in compiler optimization". ACM SIGPLAN Notices. 28 (8): 39–42. doi:10.1145/163114.163118. S2CID 2224606.
  22. ^ Aho, Sethi 및 Ulman, 컴파일러, 페이지 740, 779.

외부 링크