Rat의 레지스터 할당기

Rat 컴파일러가 레지스터 할당기를 584줄로 새로 써서 더 나은 코드를 냅니다.

C99 프런트엔드를 갖춘 컴파일러 백엔드 Rat의 개발자가 쓴 글입니다. 땜질을 거듭하며 1,392줄로 불어난 선형 스캔 할당기의 기능을 하나씩 측정했습니다. 그 뒤 효과 있는 것만 남겨 우선순위 기반 할당기로 다시 만들었습니다.

왜 중요한가

• 기능을 하나씩 꺼 보니 일부 기능은 시간만 쓰고 효과가 거의 없다는 것이 숫자로 드러났습니다.
• LLVM의 greedy 할당기에서 축출(이미 준 레지스터를 빼앗는 것)과 구간 분할을 빼도 이전보다 나은 코드가 나왔습니다.

핵심 내용

• 이전 할당기보다 생성 명령어는 3.6%, 메모리 저장 명령은 22% 줄었습니다.
• sqlite를 -O0로 컴파일할 때 할당기 시간은 77%, 전체 컴파일 시간은 43% 줄었습니다.
• 복사 병합(복사로 이어진 값을 한 레지스터에 묶는 것)과 힌트가 명령어를 약 3분의 1 줄여 효과가 가장 컸습니다.
• 스필(메모리로 내보낸 값)을 다시 배정해 보는 기능은 효과가 0.01%인데 할당기 시간의 37%를 써서 뺐습니다.
• 한 번 정한 배정은 바꾸지 않아 루프 밖에 mov가 세 개 남기도 하지만, 저자는 그만큼의 코드를 더할 가치는 없다고 봤습니다.

HN 반응

• SSA(정적 단일 대입) 형태에서는 할당이 다항 시간에 풀린다는 지적에, 스필과 병합 선택은 여전히 NP-완전하다는 반론이 붙었습니다.
• 기법과 문제를 잘 정리한 개요라는 평가와 함께, LLVM의 FastRegAlloc도 선형 스캔을 쓴다는 보충이 있었습니다.