명령 선택

Instruction selection

컴퓨터 과학에서 명령 선택이란 컴파일러 백엔드의 중간 수준 중간 표현(IR)을 낮은 수준의 IR로 변환하는 단계입니다.일반적인 컴파일러에서 명령 선택은 명령 스케줄링과 레지스터 할당보다 우선합니다.따라서 출력 IR은 무한대의 의사 레지스터 세트(종종 임시로 알려져 있음)를 가지며 여전히 핍홀 최적화의 대상이 될 수 있습니다.그렇지 않으면 대상 기계 코드, 바이트 코드 또는 어셈블리 언어와 매우 유사합니다.

예를 들어 다음과 같은 중간 수준의 IR 코드 시퀀스의 경우

t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1

x86 아키텍처에 적합한 명령 시퀀스는 다음과 같습니다.

무브 EAX, a XCHG EAX, b 더하다 a, EAX

명령 선택에 대한 포괄적인 조사에 대해서는 을 참조하십시오.[1] [2]

매크로 확장

명령 선택에 대한 가장 간단한 접근법은 매크로[3] 확장 또는 해석 코드 [4][5][6]생성으로 알려져 있습니다.매크로 확장 명령 셀렉터는 중간 레벨 IR에 템플릿을 매칭함으로써 동작한다.일치하면 IR의 일치 부분을 입력으로 사용하여 해당 매크로가 실행되며, 이 매크로가 적절한 대상 명령을 내보냅니다.매크로 확장은 중간 수준의 [7][8]IR의 텍스트 표현에 직접 수행하거나 IR을 먼저 깊이 우선으로 횡단하는 그래픽 [9]표현으로 변환할 수 있습니다.후자의 경우 템플릿은 그래프 내의 하나 이상의 인접 노드와 일치합니다.

타깃 머신이 매우 단순하지 않은 경우 매크로 확장을 단독으로 수행하면 비효율적인 코드가 생성됩니다.이 제한을 완화하기 위해 이 접근방식을 적용하는 컴파일러는 일반적으로 간단한 명령의 조합을 성능을 높이고 코드 크기를 줄이는 더 복잡한 동등한 명령으로 대체하기 위해 이 접근방식을 핍홀 최적화와 결합합니다.이는 Davidson-Fraser 접근법으로 알려져 있으며 현재 GCC에 [10]적용되고 있습니다.

그래프 커버

또 다른 접근법은 먼저 중간 수준의 IR을 그래프로 변환한 다음 패턴을 사용하여 그래프를 커버하는 것입니다.패턴은 그래프의 일부와 일치하는 템플릿이며 대상 시스템에서 제공하는 단일 명령을 사용하여 구현할 수 있습니다.목표는 선택된 패턴의 총 비용이 최소화되도록 그래프를 포괄하는 것입니다. 여기서 비용은 일반적으로 명령을 실행하는 데 걸리는 사이클 수를 나타냅니다.트리 모양의 그래프의 경우, [11]동적 프로그래밍을 사용하여 최소 비용 커버가 선형 시간 내에 발견될 수 있지만 DAG와 본격적인 그래프의 경우 문제는 NP-완전이 되고, 따라서 대부분의 경우 탐욕 알고리즘 또는 조합 [12]최적화 방법을 사용하여 해결된다.[13] [14]

최소 공통분모 전략

최소 공통분모 전략은 실행 가능한 프로그램을 다양한 컴퓨터 간에 이식할 수 있도록 프로세서 보조 명령이 존재하는 플랫폼에서 사용되는 명령 선택 기술입니다.최소 공통분모 전략 하에서 컴파일러의 기본 동작은 최소 공통 아키텍처를 구축하는 것입니다.사용 가능한 프로세서 확장 기능은 명령줄 스위치로 명시적으로 켜지지 않는 한 기본적으로는 꺼집니다.

최소공통분모전략을사용한다는것은프로세서보조명령어및기능이기본적으로사용되지않는것을의미합니다.

레퍼런스

  1. ^ Blindell, Gabriel S. Hjort (2013). Survey on Instruction Selection: An Extensive and Modern Literature Review (Report). arXiv:1306.4898. ISBN 978-91-7501-898-0.
  2. ^ Blindell, Gabriel S. Hjort (2016). Instruction Selection: Principles, Methods, & Applications. Springer. doi:10.1007/978-3-319-34019-7. ISBN 978-3-319-34017-3. S2CID 13390131.
  3. ^ Brown, P. (1969). "A Survey of Macro Processors". Annual Review in Automatic Programming. 6 (2): 37–88. doi:10.1016/0066-4138(69)90001-9. ISSN 0066-4138.
  4. ^ Cattell, R. G. G. (1979). "A Survey and Critique of Some Models of Code Generation" (PDF). School of Computer Science, Carnegie Mellon University (Technical report). Archived (PDF) from the original on May 23, 2019.
  5. ^ Ganapathi, M.; Fischer, C. N.; Hennessy, J. L. (1982). "Retargetable Compiler Code Generation". Computing Surveys. 14 (4): 573–592. doi:10.1145/356893.356897. ISSN 0360-0300. S2CID 2361347.
  6. ^ Lunell, H. (1983). Code Generator Writing Systems (Doctoral thesis). Linköping, Sweden: Linköping University.
  7. ^ Ammann, U.; Nori, K. V.; Jensen, K.; Nägeli, H. (1974). "The PASCAL (P) Compiler Implementation Notes". Instituts für Informatik (Technical report).
  8. ^ Orgass, R. J.; Waite, W. M. (1969). "A Base for a Mobile Programming System". Communications of the ACM. 12 (9): 507–510. doi:10.1145/363219.363226. S2CID 8164996.
  9. ^ Wilcox, T. R. (1971). Generating Machine Code for High-Level Programming Languages (Doctoral thesis). Ithaca, New York, USA: Cornell University.
  10. ^ Davidson, J. W.; Fraser, C. W. (1984). "Code Selection Through Object Code Optimization". ACM Transactions on Programming Languages and Systems. 6 (4): 505–526. CiteSeerX 10.1.1.76.3796. doi:10.1145/1780.1783. ISSN 0164-0925. S2CID 10315537.
  11. ^ Aho, A. V.; Ganapathi, M.; Tjiang, S. W. K. (1989). "Code Generation Using Tree Matching and Dynamic Programming". ACM Transactions on Programming Languages and Systems. 11 (4): 491–516. CiteSeerX 10.1.1.456.9102. doi:10.1145/69558.75700. S2CID 1165995.
  12. ^ Wilson, T.; Grewal, G.; Halley, B.; Banerji, D. (1994). An Integrated Approach to Retargetable Code Generation. Proceedings of the 7th International Symposium on High-Level Synthesis (ISSS'94). pp. 70–75. CiteSeerX 10.1.1.521.8288. doi:10.1109/ISHLS.1994.302339. ISBN 978-0-8186-5785-6. S2CID 14384424.
  13. ^ Bashford, Steven; Leupers, Rainer (1999). "Constraint driven code selection for fixed-point DSPS". Proceedings of the 36th ACM/IEEE conference on Design automation conference - DAC '99. pp. 817–822. CiteSeerX 10.1.1.331.390. doi:10.1145/309847.310076. ISBN 978-1581331097. S2CID 5513238.
  14. ^ Floch, A.; Wolinski, C.; Kuchcinski, K. (2010). "Combined Scheduling and Instruction Selection for Processors with Reconfigurable Cell Fabric". Proceedings of the 21st International Conference on Application-Specific Architectures and Processors (ASAP'10): 167–174.

외부 링크