컴파일러 최적화 질문

StackOverflow https://stackoverflow.com/questions/827489

문제

  1. 컴파일러가 반복적 인 하위 표현 재 계산을 제거하는 방법은 무엇입니까? 하위 표현을 어떻게 추적합니까? 그리고 반복 된 것을 어떻게 식별합니까?
  2. BitTise 연산자의 사용 외에도 공통 컴파일러가 사용하는 강도 감소 기술은 무엇입니까?
도움이 되었습니까?

해결책

  1. 많은 컴파일러가 SSAPRE (정적 단일 할당 부분 중복성 제거)를 사용하여 반복 표현식을 제거한다고 생각합니다. 이를 위해서는 코드가 필요합니다 SSA 양식, 더 많은 최적화를 허용합니다.

  2. 나는 이것에 대해 정말로 확신하지 못하지만 이 LLVM이 통과합니다. LLVM GCC보다 종종 더 빠른 컴파일러에 대한 최적화 IR입니다. 각 패스에 대한 작은 설명이 있습니다. 더 많은 정보가 필요한 경우이 패스의 LLVM 소스를 참조하십시오. C ++로 작성되었지만 매우 깨끗하고 이해할 수 있습니다.

편집 : 컴파일러를 개발하는 경우 LLVM을 적극 권장하는 것이 좋습니다. 사용하기가 매우 쉽고 최적화 된 코드를 생성합니다.

다른 팁

1의 경우, 원하는 최적화의 이름은 CSE (Common Sub Expression 제거)입니다. 당신의 표현에 따라, 이것은 매우 쉬울 수 있습니다. 일반적으로 컴파일러는 작업이 가능한 한 많이 분해되고 선형화되는 프로그램의 중간 표현을 갖습니다. 예를 들어, 표현 c = a * b + a * b 다음과 같이 분해 될 수 있습니다.

v1 = a * b
v2 = a * b
c = v1 + v2

따라서 동일한 연산자 및 피연산자와의 작업을 찾아 매우 낮은 수준에서 CSE를 수행 할 수 있습니다. 중복 (이 경우 v2)이 발생하면 모든 인스턴스를 원본으로 바꿉니다. 따라서 위의 코드를 단순화 할 수 있습니다.

v1 = a * b
c = v1 + v1

이것은 일반적으로 각 변수를 한 번만 할당한다고 가정하지만 (단일 정적 할당 양식), 해당 제한없이 이와 같은 것을 구현할 수 있습니다. 지점 에서이 최적화를 시도하고 수행 할 때 이것은 더욱 복잡해집니다. Zifre가 언급했듯이 부분 중복성 제거를 살펴보십시오.

어느 쪽이든, 당신은 약간의 기본 개선을 받고, 추적 해야하는 것은 기본 표현 만 있으면됩니다. 이것을 한 단계 더 발전시키고 산술 정체성을 찾고 싶을 수도 있습니다. 예를 들어, a * b 와 같다 b * a. 또한, x * (y + z) = x * y + x * z. 이로 인해 최적화가 더욱 복잡해지며 성능 향상이 많은 성능을 향상시킬 수 있다는 것은 명확하지 않습니다. 일화 적으로 CSE 최적화의 대부분은 배열 액세스와 같은 주소 계산에서 비롯되며 위의 복잡한 신원이 필요하지 않습니다.

2의 경우 강도 감소가 유용한 것은 실제로 컴파일하는 아키텍처에 달려 있습니다. 일반적으로 여기에는 곱셈과 분할을 변화, 추가 및 뺄셈으로 변환하는 것이 포함됩니다.

이 주제에 대한 두 가지 인쇄 된 참조를 강력히 추천합니다.

  1. 고급 컴파일러 설계 및 구현 Steven S. Muchnick
  2. 최적화 컴파일러 구축 Robert Morgan

Muchnick 책은 공식적인 측면에 있지만 매우 읽기 쉽고 모든 중요한 최적화 기술에 대한 좋은 설명을 가지고 있습니다. Morgan Book은 훨씬 더 실습적인 느낌을 가지고 있으며 최적화 기술에 중점을 둔 컴파일러 프로젝트의 큰 기초가 될 것입니다. 어느 책도 어휘 분석이나 구문 분석에 대해 할 말이 많지 않으며, 이러한 주제에 대한 지식은 가정되지 않습니다.

권장 사항 목록에 책 하나를 추가하려면 확인하십시오. "해커의 기쁨" Henry S. Warren. 정수 분열을 곱셈으로 변환하는 것과 같은 일반적인 작업을 최적화하기위한 훌륭한 기술의 개요입니다.

부분적 중복 제거 제거 (pre)를 찾고 있습니다. CSE (다른 답변에서)와 루프 불변 코드 모션은 모두 사전에 의해 사용됩니다. (사전의 변형은 게으른 코드 모션이며, 이는 최적이라고 생각합니다).

체크 아웃 Keith Cooper의 강의 노트, 기술을 잘 설명하는 것 같습니다.

하다 아니다 ssapre를 사용하십시오. Afaik, 이것은 HSSA로 알려진 특정 형태의 SSA가 필요하며, 여기에는 몇 가지 단점이 있습니다.

  • 꽤 복잡합니다
  • 글로벌 가치 번호가 필요합니다 (따라서 SSAPRE는 이미 존재할 것으로 예상되는 가치 번호를 제공하지 않습니다).
  • 언어가 변수를 쌓는 포인터를 지원하지 않는 경우에는 아무것도 제공하지 않습니다 (그렇다면 자신의 분석 작성을 중단하고 LLVM 또는 GCC를 사용하십시오).
  • GCC는 한동안 HSSA를 사용했지만 멀어졌습니다.
  • LLVM은 실험했지만 Afaik은 더 이상 사용하지 않습니다.

편집하다:

Muchnick의 책에는 자세한 설명이 있으며 다른 답변에 연결되어 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top