LLVM 23의 -O3 빌드에서 이루어진 주요 컴파일 시간 개선 사항을 살펴봅니다.
LLVM 23은 -O3 빌드에서 -6.75%(sqlite3: -10.53%)라는 상당한 컴파일 시간 개선을 이루었습니다. 이 글에서는 이러한 개선의 주요 원인을 설명합니다.
별도 언급이 없는 한, 모든 성능 수치는 LLVM compile-time-tracker의 stage2-O3 구성 기준입니다.
LLVM이 광범위하게 사용하는 해시 맵/세트에는 세 가지 중요한 개선이 있었습니다(여기에도 설명되어 있음). 첫째, 이차 탐사를 사용하는 해시 테이블에서 선형 탐사와 개선된 삭제 방식으로 전환하여(DenseMap (-1.27%), SmallPtrSet (-0.24%), StringMap (-0.10%)) 툼스톤 키가 더 이상 필요하지 않게 되었습니다. 둘째, DenseMap의 점유 상태를 빈 키 대신 압축 비트 배열에 저장하게 되어(+0.13%), 대역 내 예약값이 전혀 필요 없어졌습니다. Clang으로 빌드한 Clang에서 명령어 수 측면으로는 나쁘지만, 사이클은 개선되고 분기 및 캐시 미스는 줄어듭니다. 부수적으로 빈 키와 툼스톤 키를 제거하면서, 일부 동등성 함수가 더는 이를 명시적으로 검사할 필요가 없어 해시 테이블 조회도 더 효율적으로 되었습니다(−0.04%). 셋째, CityHash 및 약한 포인터 해시 함수에서 xxh3로 전환한 것(−0.18%)은 기존 해시 테이블에서도 이미 성능을 개선했으며, 앞선 변경의 전제 조건이었습니다.
SmallVector에서는 자명하게 복사 가능한 push_back의 확장 경로를 인라인 밖으로 옮기고 꼬리 호출 최적화를 허용하도록 변경했습니다(여기에도 설명되어 있음) (-0.50%). 그 결과 일부 경우 레지스터의 라이브 범위가 짧아지고, 빠른 경로의 명령어 수가 줄며, shrink wrapping이 늘어나고, 코드가 작아져 인라이닝도 더 많이 이루어졌습니다.
BumpAllocator는 일부 정리 작업을 거쳤습니다(−0.17%, +0.06%). 인라이닝 휴리스틱 때문에 컴파일 시간 수치는 다소 엇갈렸습니다. 더 작은 할당 함수가 인라이닝 경계를 옮겨 서로 다른 “짝홀” 인라이닝을 초래했습니다. (예를 들어 A -> B -> C -> D에서 D가 인라인되지 않으면 B는 C 안으로 인라인됩니다. D가 작아지면 C 안으로 인라인되지만, 그러면 C는 더 이상 B 안으로 인라인되지 않고 B가 A 안으로 인라인됩니다. 그러나 이 경우 C를 B 안으로 인라인할 때 가능한 중요한 단순화를 놓칠 수 있습니다.)
post_order 순회는 반복자 자체에 순회 상태를 더 이상 저장하지 않도록 다시 작성되었습니다(−0.18%). 여전히 이상적이지는 않지만, 이로써 반복자 이동 비용이 줄고 일부 반복자 함수에서 인라이닝이 가능해졌습니다.
지배자 트리 표현은 자식 벡터를 저장하는 방식에서 자식-형제 표현으로 변경되어(−0.13%) 할당을 피하게 되었습니다. 여러 패스가 자식 순서에 의존하며, 순서가 뒤집히면 크게 달라진 출력을 만들기 때문에 자식 순서를 바꾸지 않도록 주의해야 합니다. 노드에 bump allocator를 사용하면(−0.50%) 컴파일 중 구성되는 지배자 트리의 수를 고려할 때 malloc()/free() 호출 횟수가 눈에 띄게 줄었습니다.
지배자 트리 구성에는 몇 가지 개선이 있었습니다. 특히 후속 노드를 구체화하지 않는 변경(−0.21%)과 선행 노드를 에지 목록으로 저장하는 변경(−0.11%)이 가장 큰 단일 개선을 제공했습니다.
구성 알고리즘은 최악의 경우 O(n^2)임에도 큰 프로그램에서도 상당히 빠릅니다. 하지만 지배자 트리 표현은 기존 순회 패턴과의 호환성을 유지하고 갱신을 지원하기 위해 여전히 다소 비효율적입니다. 실제로 구성 시간의 상당 부분은 결과를 DominatorTreeBase 데이터 구조로 구체화하는 데만 쓰입니다.
successors()를 Use 범위 위의 반복자로 구현한 것(−0.21%)은 오래된 비효율성을 해소합니다. 이전에는 매 사용 접근이 종결자 명령어 유형에 따라 반복적으로 디스패치하는 인라인 밖 함수 호출이었습니다. 이를 위해 모든 종결자에서 후속 노드가 연속적으로 저장되도록 준비 작업이 필요했습니다(SwitchInst 변경이 필요했고, 케이스 값은 더 이상 Use가 아니라 일반 ConstantInt*입니다). 또한 이를 구분하는 비트필드 접근을 피하기 위해 Br opcode를 별도의 UncondBr 및 CondBr opcode로 분리하는 더 큰 작업도 필요했습니다(−0.08%). 그럼에도 successors()는 종결자 opcode 접근 시의 캐시 미스와 종결자 유형 switch에서의 분기 미스를 주된 이유로, 자체 시간 기준 가장 뜨거운 함수 15개 안에 여전히 남아 있습니다.
BasicBlock::getTerminator()에서 올바른 형식의 IR을 요구하고(−0.07%), successors()에서도 이를 요구하며(−0.12%), 지배자 트리에서 널이 아닌 블록을 요구한 것(−0.06%)도 개선을 제공했습니다. 비용이 싼 검사라도 자주 수행하면 어느 정도 비쌉니다. 비슷한 맥락에서 선행 노드 순회도 빨라졌습니다. LLVM은 기본 블록의 선행 노드를 사용 목록을 통해 저장하고, 종결자는 후속 블록을 사용합니다. 이전에는 기본 블록의 다른 사용자 유형으로 BlockAddress가 있었는데, 이는 매우 드물게 발생했습니다(C의 계산된 goto에만 필요). 따라서 선행 노드 반복자는 모든 블록 사용이 종결자인지 검사해야 했습니다. BlockAddress가 더 이상 기본 블록을 사용하지 않도록 변경하면서(−0.06%) 이 검사를 제거할 수 있었습니다. 몇 릴리스 전부터 전용 intrinsic으로 정규화되는 icmp+select 기반의, 오늘날 비정규적인 정수 최소값/최대값 패턴 매칭을 제거한 것도 일부 개선을 제공했습니다(−0.09%). 이는 주로 이제 인라인되는 더 작은 패턴 매칭 함수 덕분입니다.
상당히 많은 명령어에는 예를 들어 디버그 정보나 유형 기반 별칭 분석을 위한 메타데이터가 연결됩니다. Debuginfo에는 명령어용 빠른 경로가 있지만, 다른 모든 메타데이터 연결은 컨텍스트에 저장되며, 이전에는 Value 포인터를 키로 하고 연결 목록 벡터를 값으로 하는 해시 맵에 있었습니다. 이 연결을 단일 벡터에 저장하고(−0.35%) 벡터 항목들로 여러 연결 목록을 구성하며, 명령어에 연결 목록의 시작점을 저장함으로써 메타데이터 질의가 훨씬 저렴해졌습니다. SmallVector를 사용하면 증가 시 모든 TrackingMDNodeRef를 이동해야 한다는 단점이 있지만, 간접 참조 계층을 하나 추가하는 데이터 구조(예: 수정한 PagedVector) 실험에서는 성능이 더 나빴습니다. 하지만 메타데이터는 여전히 비용이 큰 메커니즘이며, 메타데이터를 가질 가능성이 있는 명령어, 특히 별칭 분석 관련 명령어에는 아마 언젠가 이 정보를 인라인으로 저장해야 할 것입니다. 메타데이터 획득이 여전히 비싸다는 점은 InstCombine의 !annotation 메타데이터 접근을 지연하도록 한 변경으로도 알 수 있습니다(−0.07%). Debuginfo 메타데이터는 디버그 위치를 가리킬 때 TrackingMDNodeRef 대신 일반 MDNode 포인터를 사용하도록 개선되었습니다(stage2-O3: -0.50%, stage2-O0-g: -1.15%). 디버그 위치는 절대 교체되지 않으므로 이것이 가능합니다. IRBuilder는 임의의 메타데이터를 연결하는 기능을 잃었고(−0.04%), 거의 한 번도 적중하지 않는 검사를 삽입되는 모든 명령어에서 절약하게 되었습니다.
Constant::isNullValue는 미리 계산하여 그 비트를 SubclassOptionalData에 저장하도록 변경되어(−0.14%), 상수 유형에 대한 빈번한 switch를 피하게 되었습니다.
기본 블록 키를 사용하던 여러 해시 맵이 제거되었습니다. 이는 블록 번호를 도입하며 2024년에 시작한 작업의 연속입니다. 처음에는 Machine IR과 인프라를 공유하기 위해, 이를 사용하는 모든 데이터 분석이 블록 번호가 다시 매겨지는 경우를 지원해야 했습니다. 이것은 제약이 되었고, 재번호 매기기를 쉽게 지원할 수 없는 LoopInfo 등의 도입을 막았습니다. 더 안정적인 별도의 분석 블록 번호를 Machine IR에 도입하면서 여러 다른 용도가 가능해졌습니다. 이제 블록 번호는 MemoryDependenceAnalysis (-0.14%), BlockFrequencyInfo (-0.15%), LazyValueInfo (-0.02%), LoopInfo (-0.15%), BranchProbabilityInfo (-0.05%), removeUnreachableBlocks() (-0.03%), 그리고 post-order 순회(−0.18%)에도 사용됩니다. SimplifyCFG 뒤에 블록을 재번호 매기면(−0.05%) 번호를 조밀하게 유지하는 데도 도움이 됩니다. 몇몇 다른 위치에서도 이렇게 하는 것이 유익할 수 있습니다.
블록 포인터 대신 블록 번호를 사용하는 부수 효과는 BlockFrequencyInfo와 BranchProbabilityInfo가 기본 블록을 데이터 구조에서 제거하기 위해 더 이상 비싼 ValueHandles를 사용할 필요가 없다는 점입니다. 포인터가 재사용될 경우 잘못된 데이터를 방지하려면 이전에는 이것이 필요했습니다. ValueHandles는 계속해서 상당한 오버헤드 원천이며 장기적으로는 아마 제거해야 합니다.
아마도 언젠가는 명령어 선택 백엔드를 대체할 GlobalISel은 상당한 개선을 보았습니다. 주로 기본값으로 사용되는 AArch64 -O0에 초점을 맞췄습니다. FastISel 대비 엔드투엔드 저하는 12.71%에서 9.39%로 낮아졌습니다(sqlite3: 31.81%에서 26.13%). 가장 마음에 드는 개선은 -O0 파이프라인에서 localizer를 제거한 것(stage1-aarch64-O0-g: -1.10%)으로, 이전에는 기본 블록당 상수 개수에 대해 이차적인 컴파일 시간을 일으켰습니다. (안타깝게도 이 변경은 되돌려졌습니다. 즉, Disarm과 TPDE 같은 사용자 빌드 시에는 여전히 GlobalISel을 강제로 비활성화해야 합니다.) GlobalISel이 FastISel을 어느 정도까지 따라잡을 수 있을지는 두고 봐야 합니다.
그 외에 백엔드에는 소수의 개선만 있었습니다(−0.21%, −0.10%, −0.23%).
SimplifyCFG에서 switch로부터 정적 조회 테이블을 생성하기 위한 최소 밀도를 40%에서 10%로 낮춘 것은 C++ 프로그램의 Clang 성능을 개선했습니다(stage2-O0-g: -0.17%). clang::Decl::castToDeclContext의 밀도는 38%이며, 이전에는 상수 포인터 오프셋을 계산하기 위해 자주 잘못 예측되는 분기가 발생했습니다. 이는 컴파일 시간 개선이 최적화 개선에서 비롯되는 드문 사례 중 하나입니다.
현재 위치 메타데이터를 다시 계산하지 않도록 한 것은 디버그 정보가 있는 빌드를 개선했지만(stage2-O0-g -3.53%), 사이클 개선은 그 절반에 불과했습니다(c-t-t와 자체 측정 모두에서).
많은 배포판은 LLVM을 공유 라이브러리로 빌드합니다. 이는 패키지 크기와 빌드 시간을 크게 줄이기 때문입니다. 그러나 정적으로 링크된 비-PIE 빌드와 비교하면 두 가지 단점이 있습니다. 첫째, 다른 함수와 전역 객체를 참조하려면 이제 시작 시 처리해야 하는 동적 재배치가 필요합니다. 이는 특히 vtable과 문자열 포인터를 포함하는 데이터 구조(예: const char * 또는 StringRef)에 영향을 줍니다. (참고: 비싼 것은 재배치 자체가 아니라 주로 재배치가 일으키는 페이지 폴트입니다.) 둘째, LLVM의 옵션 구문 분석(llvm::cl)은 모든 옵션이 각각의 전역 생성자에서 자신을 초기화하고 등록하는 방식에 기반합니다. 이는 특히 페이지 폴트 측면에서 비용이 큽니다. 거의 각 객체의 ctor 함수 코드 페이지에서 폴트가 나고, 옵션 문자열 접근에서 폴트가 나며, .bss의 옵션 구조체(각각 >=184B) 접근에서 폴트가 나고, DenseMap을 여러 번 확장하면서도 폴트가 납니다.
llvm::cl에서 벗어나는 일은 더 큰 작업입니다. 새 옵션 구문 분석 프레임워크를 작성해야 하며, 아마 TableGen에 기반할 것이고 LLVM 24에서 이루어지기를 바랍니다. 한편 시작 시 페이지 폴트 수를 줄이기 위해 .data.rel.ro/.data를 줄이고 재배치를 감소시키는 작업을 했습니다. 주목할 만한 개선으로는 레코드에 연결된 문자열을 레코드 상대 오프셋으로 저장하는 새 압축 enum 테이블 추가, unique_function 재작성, formatv와 format에서 vtable 제거, FeatureKV, SubTypeKV, 검색 가능한 테이블에 StringTable 사용, 그리고 TargetRegClass를 MCRegClass로 병합한 것이 있습니다.
LLVM 23 분기 직전에 LLVM 23 기준 dylib 관련 시작 비용을 여기에 요약했습니다.
엄밀히 말해 컴파일 시간 개선은 아니지만 관련된 내용입니다. LLVM과 트리 내부 종속 항목의 빌드 방식에 큰 변화가 생겨, 이제 LLVM은 거의 모든 컴파일 단위에 사전 컴파일 헤더를 사용하며 LLVM/Clang의 빌드 시간을 약 45% 개선합니다. 이전에는 LLVM 컴파일이 프런트엔드 집약적이어서 릴리스 빌드에서도 80% 이상을 프런트엔드에서 쓰며 C++ 표준 라이브러리와 LLVM Support를 반복하여 구문 분석했습니다. PCH를 사용하면 프런트엔드 시간은 약 55%까지 내려갑니다. 현재 PCH는 다섯 개입니다(LLVM Support (-14.73%), LLVM Core (-12.70%), LLVM CodeGen (-6.33%) (모든 대상을 빌드할 때 더 유익함), clangAST (-13.85%), 그리고 얼마 후의 clangCodeGen (-8.12%)). MSVC 또는 Clang으로 빌드할 때 PCH 빌드는 기본적으로 켜집니다. GCC는 추가 템플릿 인스턴스화가, Clang과 달리 이를 캐시하지 않는 GCC에서는 이점을 상쇄하고 GCC의 PCH 파일도 상당히 크기 때문에 비활성화됩니다.
변경 대부분을 검토해 준 Nikita Popov와 Fangrui Song에게 감사드립니다. LLVM compile-time-tracker를 호스팅해 준 Nikita Popov에게 감사드립니다. LLVM 23의 컴파일 시간 개선 대부분은 Cullen Rhodes, Fangrui Song, 그리고 제가 작성했습니다.
