코드 생성 및 최적화

코드 생성 및 최적화는 중간 표현을 효율적인 타겟 코드로 변환하여 프로그램의 의미를 보존하면서 더 빠르게 실행되거나 더 적은 리소스를 사용하도록 변환합니다.

Definition

코드 생성은 중간 표현으로부터 타겟(기계어 또는 바이트코드) 명령어를 생성하는 것이며, 최적화는 프로그램의 속도, 크기 또는 리소스 사용을 개선하는 의미 보존 변환을 적용하는 것입니다.

Scope

이 주제는 컴파일러의 백엔드 및 미들엔드를 다룹니다: 정적 단일 할당(SSA) 형식과 같은 중간 표현, 데이터 흐름 분석, 고전적 최적화(상수 전파, 공통 부분식 제거, 루프 최적화), 명령어 선택, 명령어 스케줄링, 레지스터 할당. 또한 변환이 성능을 향상시키면서 프로그램의 의미를 어떻게 보존하는지 다룹니다.

Core questions

• 프로그램 변환은 동작을 변경하지 않고 어떻게 성능을 향상시킬 수 있는가?
• 어떤 중간 표현이 최적화 분석을 효율적으로 만드는가?
• 제한된 기계 레지스터가 많은 프로그램 값에 어떻게 할당되는가?
• 공격적인 최적화에서 정확성과 성능은 어떻게 절충되는가?

Key theories

정적 단일 할당 형식

Cytron과 동료들은 각 변수가 한 번만 할당되는 SSA 형식으로 프로그램을 변환하는 효율적인 알고리즘을 제시했으며, 이는 많은 데이터 흐름 기반 최적화를 극적으로 단순화합니다.

그래프 색칠을 통한 레지스터 할당

Chaitin은 레지스터 할당을 간섭 그래프의 그래프 색칠로 모델링하여, 제한된 수의 기계 레지스터에 프로그램 값을 할당하는 기본적인 접근 방식을 제공했습니다.

데이터 흐름 기반 최적화

Muchnick과 Dragon Book은 데이터 흐름 분석을 고전적 최적화의 기본 프레임워크로 공식화하며, 안전한 변환을 정당화하는 데 필요한 프로그램 속성을 계산합니다.

Clinical relevance

코드 생성 최적화는 프로그램이 프로세서와 메모리를 얼마나 효율적으로 사용하는지를 결정하며, 에너지 사용 및 대규모 비용에 광범위한 영향을 미칩니다. SSA 형식과 그래프 색칠 레지스터 할당은 생산 컴파일러 및 JIT(Just-In-Time) 시스템의 핵심으로 남아 있습니다.

History

최적화는 Fortran 컴파일러와 함께 시작되었고 1970년대 Allen과 Cocke의 데이터 흐름 분석을 통해 성숙했습니다. Chaitin의 1981-82년 그래프 색칠 레지스터 할당과 Cytron 등의 1991년 효율적인 SSA 구성은 현대 컴파일러의 초석이 되어 오늘날 툴체인에서 사용되는 정교한 최적화 파이프라인을 가능하게 했습니다.

Debates

최적화의 공격성과 정확성 및 예측 가능성

컴파일러 설계자들은 최적화의 공격성에 대해 논쟁합니다. 정의되지 않은 동작을 이용하고 순서를 재배치하는 것이 속도를 높일 수 있지만, 예상치 못한 또는 안전하지 않은 결과를 초래할 수 있기 때문에 검증되고 예측 가능한 최적화에 대한 관심이 높아지고 있습니다.

Key figures

• Frances Allen
• Gregory Chaitin
• Ron Cytron
• Steven Muchnick
• Alfred Aho

Seminal works

• cytron1991
• chaitin1982
• muchnick1997
• aho2006

Frequently asked questions

SSA 형식이란 무엇인가요?

정적 단일 할당 형식은 모든 변수가 정확히 한 번 할당되고 사용이 단일 정의에 연결되는 중간 표현으로, 많은 컴파일러 최적화를 단순화하고 강화합니다.

레지스터 할당이 왜 어려운가요?

프로그램은 일반적으로 기계 레지스터보다 훨씬 많은 값을 사용하므로, 컴파일러는 어떤 값이 레지스터를 공유하고 어떤 값이 메모리로 스필(spill)될지 결정해야 합니다. 이 핵심 문제는 그래프 색칠과 동일하며, 이는 일반적으로 계산적으로 어렵습니다.