1. About LLVM
IR (Intermediate Representation)
LLVM 은 SSA-based 컴파일러입니다. SSA(Static Single Assignment)는 변수가 한번만 할당되도록 하여 변수의 복잡성을 줄이는 것입니다. LLVM의 큰 장점은 원하는 기능을 새로 추가하기 쉬운 것입니다. 오픈소스이면서 API가 잘 문서화 되어있고, 기능이 라이브러리로 분리되어 동작하기 때문입니다.
LLVM의 코어 라이브러리는 Optimizer이고 Optimizer의 소스와 타겟에 독립적인 중간 표현인 intermediate representation(IR)을 받아 최적화하여 새로운 IR을 도출합니다. 현실의 CPU는 레지스터가 한정되어 있지만, IR은 타겟의 레지스터 수와 관계가 없어야 하기 때문에 가상 레지스터의 수를 계속 늘리면서 작성됩니다. LLVM에서의 SSA는 레지스터에 적용되어 프론트엔드에 부담이 덜합니다.
LLVM을 타겟팅하는 프론트엔드는 소스코드를 넣어주면 LLVM IR을 생성하며, 대표적으로는 C/C++/Objective-C 소스코드를 받는 Clang이 있습니다. IR이 optimizer을 지나면 pass들이 적용되어 새로운 IR이 생성됩니다. 여기서 pass란 IR을 변형할 수도 있고, IR을 가지고 특정한 계산을 할 수도 있는 라이브러리를 말합니다. 이 IR은 미들엔드를(optimizer) 또 지나거나 백엔드로 넘겨져 머신코드가 생성됩니다.
Figure 1. Source- and target-independent optimizer 1
LLVM optimizer에는 수십개의 pass가 있습니다. 이를 크게 Analysis pass와 Transform pass로 분류합니다. Analysis pass는 IR을 분석하여 유의미한 정보들을 만듭니다. Transform pass는 이 정보를 이용하여 IR을 변형하여 퍼포먼스를 향상시킵니다. Optimizer의 Pass Manager는 Transform pass만 적용하여도 여기에 필요한 Analysis Pass를 알아서 불러와주고, 이전에 분석해놓은 정보가 유효하다면 그대로 사용하도록 합니다.
2. LLVM BasicBlock
LLVM IR 모듈은 Control Flow Graph(CFG) 구조를 가지며 instruction으로 구성되어 있습니다. CFG에서 분기가 일어나기 전까지의 instruction 들을 묶은 것이 BasicBlock 입니다. 큰단위부터 정렬하면 Module > Function > BasicBlock > Instruction 입니다.
LLVM의 optimizer에는 CFG를 시각화해주는 analysis pass(‘-dot-cfg', ‘-view-cfg')가 있어 유저가 CFG를 보며 flow를 잡아내고 디버깅 하는 데 도움이 됩니다. 이때 CFG의 노드는 BasicBlock에 해당합니다. 하지만 Figure 2에서 볼 수 있듯이 이렇게 얻은 CFG는 optimizer에서 최적화를 해주면 그래프가 확 바뀌어 알아보기 힘들다는 단점이 있습니다.
Figure 2. Control Flow Graphs of DoReplace
위의 문제를 해결하기 위하여 LLVM optimizer에서 pass가 어떻게 동작하고, IR에 BasicBlock에 대한 정보가 어떻게 남는지 연구하였습니다.
-
전/후 IR의 BasicBlock address를 확인하여 optimizer 전/후 address가 동일하다면 같은 BasicBlock임을 알 수 있을 것이라고 예상하였습니다. 이를 토대로 analysis pass를 개발한 결과, address는 IR을 생성할 때마다 새로 부여되는 것임을 확인하였습니다.
-
optimizer는 IR을 받아서 IR을 생성하지만 두 IR 간의 연결점은 optimization remarks에만 존재합니다. 하지만 일부 pass에 대해서만 기록해 주기 때문에 사용이 한정적입니다. 그래서 optimizer pass 전후의 IR 사이의 연결을 직접 해주어야했습니다.
-
하지만 변환된 IR에는 이전 IR의 BasicBlock에 대한 충분한 정보가 없어서 소스코드에서 힌트를 얻기로 하였습니다. clang에 -g 옵션을 줄 경우 IR에 debug information 이 붙기 때문에 소스코드와 IR을 연결 지을 수 있습니다. IR이 optimizer을 지나 새로운 IR이 만들어져도 debug info는 잘 유지됩니다. 이 정보를 이용한 결과 IR 사이에 같은 basicblock을 찾아내는 것이 가능했습니다. 두 개의 IR을 받아서 비교해야 하기 때문에 analysis pass의 형태가 아닌 tool 형태로 개발하였습니다.
3. LLVM-BLOCK tool 소개
LLVM-BLOCK tool은 KC-ML2 Github repo에 공개되어있습니다.
[Build]의 명령어로 tool을 설치 한 뒤 [Quick Commands]을 따라 쉽게 사용하실 수 있습니다.
LLVM-BLOCK은 다음과 같이 작동하도록 하였습니다. 2~3번 과정은 원하는 만큼 반복할 수 있습니다.
-
Frontend: 소스코드
IR_before ‘-g’ option
-
Optimizer: IR_before
IR_after One or more passes
-
LLVM-BLOCK: IR_before와 IR_after의 debug info를 비교하여 Function 별 동일한 BasicBlock head 리스트 도출
-
IR에서 debug info 제거
'-strip-debug' option
-
Code Generator: IR_after
machine code
LLVM-BLOCK에 Figure 2(a) 에 해당하는 모듈을 IR_before, Figure 2(b) 에 해당하는 모듈을 IR_after로 넣어주면 Figure 3와 같은 결과가 나옵니다.
Figure 3. Output
두 개의 CFG와 동일 BasicBlock 리스트를 주면, 최소한의 변화로 두 그래프를 시각화해주는 페이지 를 만들었습니다.아래 프로젝트인 LLVM Automatic Tuning에 visualization tool로서 활용할 예정입니다.
4. LLVM Automatic Tuning
모든 유저가 모든 pass들에 대해 모두 완벽하게 이해하기는 어렵습니다. 그래서 컴파일러에는 미리 준비된 몇 가지의 optimization level이 있습니다. -O1, -O2, -O3가 대표적이며 숫자가 클 수록 많은 pass를 쓰기 때문에 컴파일타임도 커집니다. 컴파일러 개발자들이 pass에 대한 지식을 가지고 여러 pass를 조합하여 만든 heuristics 입니다. 유저들은 보통 optimization level을 사용하여 컴파일된 코드의 성능을 향상시킵니다. 그러나 이는 본인의 코드에 가장 좋은 pass set이 아닙니다. 코드에 맞는 최적 pass sequence를 찾는 것은 예전부터 풀고자 했던 문제입니다. (Finding effective optimization phase sequences problem)
-
Spatial Based Feature Generation for Machine Learning Based Optimization Compilation
-
Automatic Static Feature Generation for Compiler Optimization Problems
위에서 제시한 논문들은 classical machine learning으로 문제에 접근하였습니다. feature selection, feature extraction을 거쳐 여러번 컴파일을 통해 training set을 만든다는 점에서 개선할 여지가 많습니다. 각 논문에서 설정한 feature들이 pass sequence와의 상관성이 얼마나 높은 지 알 수 없으며, training set은 모든 pass sequence를 포함하지 못합니다.
End-to-End Recurrent Reinforcement Learning
Figure 4. Design overview
Observation
CFG의 노드인 basicblock을 Data Dependence Graph로 나타낸 그래프를 사용하여 control flow와 data dependencies를 알 수 있도록 하였습니다.
-
Graph neural network로 DDG를 vector로 표현하여 각각의 노드가 vector인 CFG 생성합니다.
-
이 CFG를 Graph neural network에 넣어 나온 vector가 observation이 됩니다.
Action
Action은 IR에 pass를 하나 적용하는 것으로 정의하였습니다.
Analysis pass는 굳이 넣어주지 않아도 PassManager가 관리하기 때문에 action에는 transform pass만 넣어주어 action space를 작게 설정하였습니다.
Recurrent Policy
transform pass 중에서는 하나만 쓰였을 때 퍼포먼스에 별다른 영향을 주지 않지만, 다른 Transform pass와 연달아 쓰이면 퍼포먼스를 향상시키는 pass가 있습니다. 다시 말해 이전 action과 현재의 action이 상관성이 있습니다. 그래서 Recurrent Layer를 통해 agent가 연달아쓰이는 조합을 배우도록 하였습니다.
Reward
end-to-end이기 때문에 Reward가 계산되어 Graph Neural Network, Recurrent Neural Network layer에 backpropagation 합니다.
최적화를 하지 않은 코드의 실행 시간을
