핍홀 최적화

Peephole optimization

Peephole 최적화란 컴파일러가 생성하는 명령어 중 작은 세트로 실행되는 최적화 기법입니다.작은 세트는 Peephole 또는 [1]window로 알려져 있습니다.

핍홀 최적화에는 작은 명령어 세트를 더 나은 성능을 가진 동등한 세트로 변경하는 것이 포함됩니다.

예를 들어 다음과 같습니다.

  • 레지스터 A를 스택에 밀어넣은 후 값을 레지스터 A로 바로 되돌리는 대신 핍홀 최적화를 통해 두 명령을 모두 제거할 수 있습니다.
  • A에 A를 추가하는 대신, 핍홀 최적화는 산술적 왼쪽으로 이동할 수 있다.
  • 부동소수점 레지스터에 8을 곱하는 대신, 핍홀 최적화는 부동소수점 레지스터의 지수를 3으로 스케일링할 수 있다.
  • 인덱스에 4를 곱하여 결과를 기본 주소에 추가하여 포인터 값을 얻은 다음 포인터를 역참조하는 대신, 핍홀 최적화는 하나의 명령으로 동일한 결과를 달성하는 하드웨어 주소 지정 모드를 사용할 수 있습니다.

peephole optimization이라는 용어는 [2]1965년 William Marshall McKeeman에 의해 도입되었습니다.

교환 규칙

핍홀 [3]최적화에 적용되는 일반적인 기법:

  • Null 시퀀스– 불필요한 조작을 삭제합니다.
  • 운용의 조합– 여러 운용을 동등한1개의 운용으로 치환합니다.
  • 대수법칙 – 대수법칙을 사용하여 명령을 단순화하거나 순서를 변경합니다.
  • 특수 케이스 지침 – 특수 오퍼랜드 케이스용으로 설계된 지침을 사용하십시오.
  • 주소 모드 조작– 주소 모드를 사용하여 코드를 단순화합니다.

다른 유형의 핍홀 최적화가 있을 수 있습니다.

예

느린 명령어를 빠른 명령어로 대체

다음 Java 바이트 코드

... aload 1 aload 1 mul...

대체할 수 있다

... aload 1 dup mul...

이러한 종류의 최적화는 대부분의 핍홀 최적화와 마찬가지로 명령의 효율성에 대한 특정 가정을 합니다.예를 들어, 이 경우 다음과 같이 가정합니다.dup(스택의 상단을 복제하여 푸시하는) 조작이, 보다 효율적입니다.aload Xoperation(로 식별된 로컬 변수를 로드합니다)X스택에 푸시합니다).

중복 코드 삭제 중

또 다른 예는 다중 로드 저장소를 제거하는 것입니다. 

a = b + c; d = a + e;

로서 간단하게 실장된다.

무브 b, R0  ; b를 레지스터에 복사합니다. 더하다 c, R0  ; 레지스터에 c를 더하면 레지스터는 b+c가 됩니다. 무브 R0, a  ; 레지스터를 에 복사합니다. 무브 a, R0  ; a를 레지스터에 복사합니다. 더하다 e, R0  ; 레지스터에 e를 추가하면 레지스터는 a+e [(b+c)+e]가 됩니다. 무브 R0, d  ; 레지스터를 d에 복사합니다.

최적화할 수 있습니다.

무브 b, R0  ; b를 레지스터에 복사합니다. 더하다 c, R0  ; 레지스터에 c를 추가한다(현재는 b+c(a)). 무브 R0, a  ; 레지스터를 에 복사합니다. 더하다 e, R0  ; 레지스터에 e를 추가합니다.이거는 b+c+e [(a)+e]입니다. 무브 R0, d  ; 레지스터를 d에 복사합니다.

다중 스택 명령 제거

서브루틴을 호출하기 전에 컴파일러가 레지스터를 스택에 저장하고 반환 시 레지스터를 복원하는 경우 서브루틴에 대한 연속 호출에는 다중 스택 명령이 있을 수 있습니다.

컴파일러가 각 프로시저 호출에 대해 다음 Z80 명령을 생성한다고 가정합니다.

 밀어넣다 AF  밀어넣다 BC  밀어넣다 DE  밀어넣다 HL  불러 주소  팝 HL  팝 DE  팝 BC  팝 AF

2개의 서브루틴콜이 연속해서 존재하는 경우, 그 콜은 다음과 같습니다.

 밀어넣다 AF  밀어넣다 BC  밀어넣다 DE  밀어넣다 HL  불러 _ADDR1  팝 HL  팝 DE  팝 BC  팝 AF  밀어넣다 AF  밀어넣다 BC  밀어넣다 DE  밀어넣다 HL  불러 _ADDR2  팝 HL  팝 DE  팝 BC  팝 AF

동일한 레지스터에 대해 POP regs 뒤에 PUSH가 이어지는 시퀀스는 일반적으로 중복됩니다.중복되는 경우, 핍홀 최적화는 이러한 지침을 제거합니다.이 예에서는, 이것에 의해, 다른 용장 POP/PUSH 페어가 핍홀에 표시되고, 이러한 페어가 차례로 삭제됩니다.서브루틴 _ADDR2가 이전 레지스터 값에 의존하지 않는 경우 위의 예에서 용장 코드를 모두 삭제하면 최종적으로 다음 코드가 남습니다.

 밀어넣다 AF  밀어넣다 BC  밀어넣다 DE  밀어넣다 HL  불러 _ADDR1  불러 _ADDR2  팝 HL  팝 DE  팝 BC  팝 AF

실행

최신 컴파일러는 패턴 매칭 [4]알고리즘을 사용하여 핍홀 최적화를 구현하는 경우가 많습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Muchnick, Steven Stanley (1997-08-15). Advanced Compiler Design and Implementation. Academic Press / Morgan Kaufmann. ISBN 978-1-55860-320-2.
  2. ^ McKeeman, William Marshall (July 1965). "Peephole optimization". Communications of the ACM. 8 (7): 443–444. doi:10.1145/364995.365000. S2CID 9529633.
  3. ^ Fischer, Charles N.; Cytron, Ron K.; LeBlanc, Jr., Richard J. (2010). Crafting a Compiler (PDF). Addison-Wesley. ISBN 978-0-13-606705-4. Archived from the original (PDF) on 2018-07-03. Retrieved 2018-07-02.
  4. ^ Aho, Alfred Vaino; Lam, Monica Sin-Ling; Sethi, Ravi; Ullman, Jeffrey David (2007). "Chapter 8.9.2 Code Generation by Tiling an Input Tree". Compilers – Principles, Techniques, & Tools (PDF) (2 ed.). Pearson Education. p. 540. Archived (PDF) from the original on 2018-06-10. Retrieved 2018-07-02.

외부 링크

Wiktionary에서 peephole 최적화의 사전적 정의