目录

待整理:

官方文檔:

線上文章:

線上課程:

開發注意事項:

編譯 LLVM

使用範例

  • -help-hidden 可以顯示更多的選項。
  • -debug-only=<debug string> 可以只顯示屬於特定 DEBUG_TYPE 的資訊。
    • grep DEBUG_TYPE lib/* | grep pre-RA-sched 可以列出屬於同一類 DEBUG_TYPE 的檔案。
  • -filter-view-dags=<string> 可以只顯示特定 basic block 的 DAG 資訊。

LLVM IR

$ cat sum.c
int sum(int a, int b) {
  return a + b;
}
$ clang -emit-llvm -S sum.c -o sum.ll
; ModuleID = 'sum.c'
source_filename = "sum.c"
; 從底下 target datalayout 和 triple 即可知 LLVM IR 並非平台中立。
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.11.0"
 
; Function Attrs: noinline nounwind ssp uwtable
define i32 @sum(i32 %a, i32 %b) #0 {
entry:
  %a.addr = alloca i32, align 4        ; 在 stack 上分配空間給 i32，4 byte 對齊。
  %b.addr = alloca i32, align 4
  store i32 %a, i32* %a.addr, align 4  ; 將函式參數存到 stack。
  store i32 %b, i32* %b.addr, align 4
  %0 = load i32, i32* %a.addr, align 4 ; 從 stack 讀出 operand。
  %1 = load i32, i32* %b.addr, align 4
  %add = add nsw i32 %0, %1            ; 加法運算。
  ret i32 %add                         ; 返回運算結果。
}

跟 LLVM IR 相關的類如下，所在目錄為 include/llvm/IR:

較難理解的部分:

InstCombine

  • InstructionSimplify.cpp 也負責簡化 LLVM IR。和 InstCombine 不同的地方在於只做運算元折疊，不新建指令。

Example

MachineInstr

術語:

MachineCode

從匯編器角度所設計的 MCInst (MachineCode)，所帶的資訊比 MachineInstr (MI) 更少，其主要用途是讓匯編器生成目的檔，或是透過反匯編器生成 MCInst。

image1.slideserve.com_2196423_slide4-n.jpg

相關文章: 

# 產生匯編的同時，於註解加上對應的 MCInst。
$ llc -asm-show-inst sum.ll -o -
	movq	%rsp, %rbp              ## <MCInst #1741 MOV64rr
                                        ##  <MCOperand Reg:36>
                                        ##  <MCOperand Reg:44>>
# 產生匯編的同時，於註解加上對應的指令編碼。 
$ llc -show-mc-encoding sum.ll
	movq	%rsp, %rbp              ## encoding: [0x48,0x89,0xe5]
# llvm-mc 用於測試 MCInst 的匯編和反匯編。
$ echo "movq%rsp, %rbp" | llvm-mc -show-encoding
	.section	__TEXT,__text,regular,pure_instructions
	movq	%rsp, %rbp              ## encoding: [0x48,0x89,0xe5]
$ echo "0x48,0x89,0xe5" | llvm-mc -disassemble
	.section	__TEXT,__text,regular,pure_instructions
	movq	%rsp, %rbp
$ echo "0x48,0x89,0xe5" | llvm-mc -disassemble -show-inst
	.section	__TEXT,__text,regular,pure_instructions
	movq	%rsp, %rbp              ## <MCInst #1741 MOV64rr
                                        ##  <MCOperand Reg:36>
                                        ##  <MCOperand Reg:44>>

在 post-register allocation pass 之後，於 AsmPrinter 調用 EmitInstruction，將 MI 轉換成 MCInst，可以輸出匯編或是目的檔。目標平台繼承 AsmPrinter 並覆寫相關函式。

image.slidesharecdn.com_mclinker-2013-chenwj-160719142821_95_part-ii-llvm-intermediate-representation-29-638.jpg 

$ lldb llc
(lldb) b X86AsmPrinter::runOnMachineFunction
# MCAsmStreamer
(lldb) r -filetype=asm sum.ll
# MCObjectStreamer
(lldb) r -filetype=obj sum.ll

Pass

Code Generator

LLVM 後端基本上有三類 IR (LLVM + ARM = ?)，由上至下依序是:

後兩者的名稱容易被混淆:

  1. MachineInstr: SelectionDAG 最終會轉成 MachineInstr。MachineInstr 是目標機器碼的抽象，可以表示成 SSA 和 non-SSA 形式。在 register allocation 之前/後，分別為 SSA 和 non-SSA 形式。
  2. MachineCode: Code Emission 負責將 MachineInst 轉成 MachineCode。MachineCode 處理最後生成的機器碼 。

如同 Design and Implementation of a TriCore Backend for the LLVM Compiler Framework 第 12 頁所展示的，LLVM 後端的流程如下: 

LLVM IR -> DAG Lowering -> non-legalized DAGs -> DAG Legalization -> legalized DAGs
  -> Instruction Selection -> DAGs (native instructions, MI) -> Scheduling
  -> SSA Form -> SSA-based Opt -> SSA Form -> Register Allocation
  -> native instrictions with phys reg -> Post Allocation
  -> Prolog/Epilog Code Insertion -> resolved stack reference
  -> Peehole Opt -> Assembly Printing -> assembly

Tutorial: Building a backend in 24 hours (2012) 第 3 頁展示各個階段分別為何種形式的中介碼。

  1. LLVM IR → DAG (平台無關): 這一步驟是為了將來方便做 instruction selection 和 instruction scheduling。LLVM 透過 tblgen 產生部分 instruction selector，後端需要客製化的部分另外寫成 C++ 代碼。請見 Introduction to SelectionDAGs。在 instruction selection 之前包含底下幾個步驟:
  2. DAG (平台無關) → DAG (平台相關): 做 instruction selection。透過 SelectionDAGISel 遍歷 DAG 中的 SDNode，將平台無關指令替換成平台相關指令。注意! 此階段所得的目標代碼仍使用 virtual register，留待之後 register allocation 配置暫存器。
  3. DAG (平台相關) → DAG (平台相關): 做 instruction scheduling。透過 ScheduleDAG對 DAG 進行 scheduling，這裡會根據目標平台的一些限制指定節點之間的順序。
  4. DAG (平台相關) → MI: 透過 InstrEmitter 遍歷 DAG 生成 MI (MachineInstr)。此時的 MI 近似於 LLVM IR 的 SSA form (擁有 Phi Node)，可以對其做 SSA 相關優化; MI 此時使用的仍是 virtual register。經過 register allocation 之後，MI 不再是 SSA form，同時也改使用 physical register。
  5. MI → MC: 透過 AsmPrinter 遍歷 MI，轉換成 MCInst，最後輸出匯編或是目的檔。

SelectionDAG

SDNode 之間有 data 或 control (chain, 簡寫 ch) dependency。上圖中黑色箭頭代表 data dependency，藍色箭頭代表 control dependency (注意它指向節點中的 ch 欄位)，紅色箭頭代表兩個節點之間是 glue 的關係 (和 ch 相比，glue 之間不能插入其它節點)。EntryToken 和 TokenFactor 負責 control dependency。GraphRoot 代表 SelectionDAG 的最底層。每個節點中間一欄代表其 operator (ISD::NodeType)，上面一欄代表其輸入，下面一欄代表其輸出。

SelectionDAG 主要有底下幾個流程 (SelectionDAGISel::CodeGenAndEmitDAG()):

  1. Lower: 將 LLVM IR 轉換成 SelectionDAG (SelectionDAGISel::SelectAllBasicBlocks)。
    # Pop up a window to show dags before the first dag combine pass
$ llc -view-dag-combine1-dags sum.ll
  2. Combine: 將若干 SDNode 合成一個 SDNode (SelectionDAG::Combine())。
    # Pop up a window to show dags before legalize types
$ llc -view-legalize-types-dags sum.ll
  3. Legalize Type: 將目標平台不支援的型別轉換成支援的型別 (SelectionDAG::LegalizeTypes())。
    # Pop up a window to show dags before the post legalize types dag combine pass
$ llc -view-dag-combine-lt-dags sum.ll
  4. Legalize Vector: 將目標平台不支援的向量型別轉換成支援的型別。
    # Pop up a window to show dags before legalize
$ llc -view-legalize-dags sum.ll
  5. Legalize Op: 將目標平台不支援的運算轉換成支援的運算。
    # Pop up a window to show dags before the second dag combine pass
$ llc -view-dag-combine2-dags sum.ll
  6. Combine: 將若干 SDNode 合成一個 SDNode。
    # Pop up a window to show isel dags as they are selected
$ llc -view-isel-dags sum.ll
  7. Select: SDNode (平台無關) → SDNode (平台相關)。
    # Pop up a window to show sched dags as they are processed
$ llc -view-sched-dags sum.ll
  8. Schedule: 完成指令調度。
    # Pop up a window to show SUnit dags after they are processed
$ llc -view-sunit-dags sum.ll

Global Instruction Selection

LLVM IR -> Global MI (GMI) -> MI

Instruction Scheduling

Example

TableGen

Register Pair

// Calling convention for leaf functions
def CC_AMDGPU_Func : CallingConv<[
  // 針對要映射到 quad-register 的型別，調用相應的處理函式。
  CCIfType<[i64, f64, v2i32, v2f32, v4i32, v4f32, v8i32, v8f32, v16i32, v16f32, v2i64, v2f64], CCCustom<"allocateVGPRTuple">>,
  CCIfType<[v4i32, v4f32, v2i64, v2f64], CCAssignToStack<16, 4>>,
]>;

Subtarget

InstrMapping

不同版本指令之間的映射關係，例如 Hexagon 的 Dot-New 指令 (Hexagon DSP Architecture)，可以使用 InstrMapping 表示 (How To Use Instruction Mappings)。例如我們想建立 add/add.t/add.f 和 sub/sub.t/sub.f 的映射表，以 add/sub 為 key，可以取得不同版本的指令，如: add.t/sub.t 和 add.f/sub.f。

no pred true false
add add add.t add.f
sub sub sub.t sub.f

在 Hexagon Dot-New 指令 (Hexagon DSP Architecture) 的應用。原本 VLIW 的一個 bundle (packet) 內的指令不會有依賴關係，為了增加 bundle 內的指令個數，引入 Dot-New 指令，使得 bundle 內的指令可以有依賴關係。

Writing Backend

先介紹後端主要目錄結構。後端代碼位於 include/llvm 和 lib 底下幾個目錄:

這裡介紹開發後端會碰到的主要幾個檔案。參考文檔:

以 X86 為例，X86TargetMachine.h 和 X86.td 是兩個最主要的檔案。上層平台無關代碼生成算法透過 X86TargetMachine.h 的接口得到底層平台相關資訊。X86.td 描述 ISA 擴展和處理器家族，並 include 其它 *.td 檔。

JIT

其它特性

這裡放感興趣的特性。

交叉編譯

交叉編譯有底下術語:

交叉工具鏈，除了編譯器，基本牽涉到底下幾個元件:

測試

詳細請見 LLVM Testing Infrastructure Guide。

發行版測試流程請見 How To Validate a New Release。一般在預定發行日期前一個月，會公告徵求測試者 ([Release-testers] [5.0.0 Release] Schedule and call for testers)。

補丁 & 臭蟲

臭蟲請發送到這裡 並先閱讀 How To Submit A Bug。目前發送補丁方式請參照 Code Reviews with Phabricator。

外部連結

1) http://lists.llvm.org/pipermail/llvm-dev/2017-June/114489.html
2) http://lists.llvm.org/pipermail/llvm-dev/2017-May/112745.html
3) http://lists.llvm.org/pipermail/llvm-dev/2017-April/112287.html
4) https://reviews.llvm.org/D16829
5) http://lists.llvm.org/pipermail/llvm-dev/2017-May/113156.html