待整理:

官方文檔:

線上文章:

線上課程:

開發注意事項:

  • O2 優化的 bug。基本透過裁減代碼，得到最小的測試用例以定位到問題點。目前的經驗是裁減到函式級別，隨即對該函式的匯編進行除錯。
    • 測試套儘早運行，及早抓到 bug。
    • 開發時如果沒有 debugger，需要透過 printf 打印訊息。但是要注意 printf 是否能正確執行，另外 printf 可能會影響 O2 代碼生成，請謹慎使用。
      printf("%8x %8x %8x %8x", *((unsigned int *)(&var) + 0),
                          *((unsigned int *)(&var) + 1),
                          *((unsigned int *)(&var) + 2),
                          *((unsigned int *)(&var) + 3));
    • 針對目標函式，打印 IR 的一連串變換 (LLVM IR → DAG → Machine IR → MCInstr)，觀察何時產生問題代碼。
      $ clang -O2 -c -mllvm -print-after-all -mllvm -filter-print-funcs=main func.c
    • 如果是從 GCC 移植到 LLVM，可能有有限的 debugger。必要時，對比 O0 和 O2 的匯編，觀察暫存器和內存的值，再反推源代碼出錯的位址，進而推導優化過程中的問題。匯編和源代碼的映射必須基本理解，以利反推。
  • 關於 O2 代碼生成質量，盡可能從 LLVM IR，SelectionDAG 和 TableGen 方向上優化，再考慮其它作法 (如 peephole)。
    • 參考其他後端時，從 LLVM IR 開始對比。即使只有細微差異，都可能會影響後續優化效果。
      • LLVM IR
        $ clang -O0 -emit-llvm -S -o sum.ll sum.c
# 和參考後端比較 O2 IR 生成過程中是否有差異。
$ opt -O2 sum.ll -print-after-all
      • SelectionDAG
        $ clang -O2 -emit-llvm -S -o sum.ll sum.c
# 觀察 DAG 變換過程，看是否有優化空間。
$ llc sum.ll -debug
    • 優化/減少 load/store。

編譯 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。-S 輸文字格式 LLVM IR (.ll)，-c 輸出二進制格式 LLVM IR (.bc)。
    $ clang -emit-llvm -S hello.c -o hello.ll
$ clang -emit-llvm -c hello.c -o hello.bc
  • 透過 Clang，傳命令行參數給 LLVM 後端。
    $ clang -c sum.c -mllvm -debug-pass=Structure
  • 匯編和反匯編 LLVM IR。匯編將 .ll 轉成 .bc; 反匯編將 .bc 轉成 .ll。
    $ llvm-as hello.ll -o hello.bc
$ llvm-dis hello.bc -o hello.ll
  • 如果想要使用 LLVM 的標頭檔和函式庫。
    $ gcc `llvm-config --cxxflags --ldflags` foo.c `llvm-config --libs`
  • 將 LLVM IR 編譯成目標平台匯編或目的檔。
    # 顯示隱藏選項。
$ llc -help-hidden
# 顯示在編譯過程中傳遞哪些參數給 opt。
$ llc -debug-pass=Arguments sum.ll
# 顯示在編譯過程中 PassManager 調度哪些 pass。
$ llc -debug-pass=Structure sum.ll
# 只顯示代碼中有 #define DEBUG_TYPE "legalize-types" 的 pass。
$ llc -debug-only=legalize-types sum.ll
  • 優化 LLVM IR。
    # 顯示隱藏選項。
$ opt -help-hidden
# 顯示每一個 pass 處理之後的 LLVM IR。可以用來觀察感興趣的 pass 做了哪些變換。
$ opt -S -O2 -print-after-all sum.ll

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                         ; 返回運算結果。
}
  • Data Layout: 有些優化會查詢 data layout，請注意設置是否正確。
  • Target Triple: ARCHITECTURE-VENDOR-OPERATING_SYSTEM

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

  • Module: Module 對應到一個 C 檔案。Module 包含多個 Function。
  • Function: Function 對應到一個 C 函式。Function 包含多個 BasicBlock。
  • BasicBlock: BasicBlock 包含一段 single entry single exit 的 Instruction。
  • Instruction: 是所有 LLVM IR 的基類。
  • Value: 產生 (define) 值 (Value) 的類均繼承 Value。Value 代表可以被 Instruction 使用，有型別的值 (typed value)。注意！BasicBlock 也是 Value (即為 Value 的子類)，因為 BasicBlock 可以作為分支指令的目標。
    • 一個 Value 被定義 (define) 之後，可以被多次使用 (use)。Value 維護一個 User 列表，紀錄誰使用到該 Value。提供接口取得 def-use chain 中的 use。
  • User: 使用 (use) 值 (Value) 的類均繼承 User。User 維護一個 operand 列表，代表 User 用到了哪些 Value。
    • 每個 operand 會指向它所參考的 Value。因為 LLVM IR 是 SSA，這種參考關係是唯一。提供接口取得 use-def chain 中的 def。

較難理解的部分:

  • getelementptr
    • The Often Misunderstood GEP Instruction
    • 為 aggregate type (LLVM 的 array 和 struct) 的子元素計算位址，不涉及內存存取。
      $ cat struct.c
struct RT {
  char A;
  char C;
};
 
char *func1(struct RT *s) {
  return &(s->A);
}
 
char *func2(struct RT *s) {
  return &(s->C);
}
 
char *func3(struct RT *s) {
  return &(s[1].C);
}
$ clang -emit-llvm -O1 -S struct.c -o struct.ll
      %struct.RT = type { i8, i8 }
 
; Function Attrs: norecurse nounwind readnone ssp uwtable
define i8* @func1(%struct.RT* readnone %s) local_unnamed_addr #0 {
entry:
  %A = getelementptr inbounds %struct.RT, %struct.RT* %s, i64 0, i32 0
  ret i8* %A
}
 
; Function Attrs: norecurse nounwind readnone ssp uwtable
define i8* @func2(%struct.RT* readnone %s) local_unnamed_addr #0 {
entry:
  %C = getelementptr inbounds %struct.RT, %struct.RT* %s, i64 0, i32 1
  ret i8* %C
}
 
; Function Attrs: norecurse nounwind readnone ssp uwtable
define i8* @func3(%struct.RT* readnone %s) local_unnamed_addr #0 {
entry:
  %C = getelementptr inbounds %struct.RT, %struct.RT* %s, i64 1, i32 1
  ret i8* %C
}
      • 第一個參數是 %struct.RT: 第二個參數所指類型。
      • 第二個參數是 %struct.RT* %0: 計算位址的起始位址，其型別一定是指針類型。之後的參數皆是欲對其計算位址的子元素的 index。
      • 第三個參數是 i32 0: 類似 %0[0]。LLVM 某種程度上將第二個參數視為 array。如果實際上不是 array，此值皆為 0。
      • 第四個參數是 i32 0: 類似 %0[0].A。
  • Undefined Values: 指令中帶有 undefined value，代表指令對該值為何不感興趣 (undefined value 可以代表任意的值1))。編譯器對此類情況有機會可以優化。
  • Poison Values: 指令中帶有 poison value，其結果為 undefined behavior。

InstCombine

  • InstructionSimplify.cpp 也負責簡化 LLVM IR。和 InstCombine 不同的地方在於只做運算元折疊，不新建指令。
  • InstCombine 類似於 SelectionDAG 中的 DAGCombiner，只不過一個作用於 LLVM IR，另一個作用於 SelectionDAG，目的都是簡化 IR/SelectionDAG。

Example

  • Bitfield (C - Bit Fields)
    $ cat bitfield.c
typedef struct {
   unsigned int width  : 16;
   unsigned int height : 16;
} status;
 
void foo() {
  status s;
  s.width = 4;
  s.height = 5;
}
$ clang bitfiled.c -emit-llvm -S -o bitfiled.ll
    %struct.status = type { i32 }
 
; Function Attrs: noinline nounwind ssp uwtable
define void @foo() #0 {
entry:
  %s = alloca %struct.status, align 4
  %0 = bitcast %struct.status* %s to i32*
  %bf.load = load i32, i32* %0, align 4
  %bf.clear = and i32 %bf.load, -65536    ; and FFFF0000。0000 代表先被 clear，之後要被設置的部分，取 status.width。
  %bf.set = or i32 %bf.clear, 4           ; or 0004。把 status.width 設為 4。
  store i32 %bf.set, i32* %0, align 4
  %1 = bitcast %struct.status* %s to i32*
  %bf.load1 = load i32, i32* %1, align 4
  %bf.clear2 = and i32 %bf.load1, 65535   ; and 0000FFFF。0000 代表先被 clear，之後要被設置的部分，取 status.height。
  %bf.set3 = or i32 %bf.clear2, 327680    ; or 50000。把 status.height 設為 5。
  store i32 %bf.set3, i32* %1, align 4
  ret void
}

MachineInstr

術語:

  • llc -print-machineinstrs 列出指令選擇後，各個階段的 MachineInstr。
    $ llc -print-machineinstrs sum.ll
# After Instruction Selection:
# 打印出 MachineFunction 的 Property。從 IsSSA 和 TracksLiveness 可以知道我們現在處於暫存器分配前的階段。
# Machine code for function sum: IsSSA, TracksLiveness
Frame Objects:
  fi#0: size=4, align=4, at location [SP+8]
  fi#1: size=4, align=4, at location [SP+8]
Function Live Ins: %EDI in %vreg0, %ESI in %vreg1
 
# MachineBasicBlock 可以連結到相關的 LLVM IR BasicBlock。
BB#0: derived from LLVM BB %entry
    Live Ins: %EDI %ESI
	%vreg1<def> = COPY %ESI; GR32:%vreg1
	%vreg0<def> = COPY %EDI; GR32:%vreg0
	MOV32mr <fi#0>, 1, %noreg, 0, %noreg, %vreg0; mem:ST4[%a.addr] GR32:%vreg0
	MOV32mr <fi#1>, 1, %noreg, 0, %noreg, %vreg1; mem:ST4[%b.addr] GR32:%vreg1
	%vreg2<def,tied1> = ADD32rm %vreg1<tied0>, <fi#0>, 1, %noreg, 0, %noreg, %EFLAGS<imp-def,dead>; mem:LD4[%a.addr](dereferenceable) GR32:%vreg2,%vreg1
	%EAX<def> = COPY %vreg2; GR32:%vreg2
	RET 0, %EAX
    • %vreg 是虛擬暫存器，%ESI 是物理暫存器。
      • <def> 表示該暫存器於該指令被定義，沒有 <def> 代表該暫存器於該指令被使用。
      • <dead> 代表被定義的暫存器在該指令之後沒有被使用。 <kill> 代表該指令是最後一條使用該暫存器的指令。
      • imp-def 和 imp-use 表示該暫存器是被隱式定義或使用，不出現在匯編指令中，如 %EFLAGS。
      • 對於同時使用和定義的暫存器，以 tied 表示。其餘 flag 的意義請見 MachineOperand。
    • <fi#0> 表示存取虛擬棧上第幾個 index 的位置。在經過 PrologEpilogInserter.cpp 之後，<fi#0> 會轉換成目標平台的棧指針計算。
      • 棧指針計算過程中，可能因為立即數超過範圍，必須將中間結果存在臨時的暫存器。但注意，PrologEpilogInserter.cpp 發生在暫存器分配之後，此時需要 RegisterScavenging.cpp 清出可用的暫存器。
  • 針對 MI pass 的測試。
    $ llc -stop-after=isel sum.ll -o sum.mir
$ llc -run-pass=machine-scheduler sum.mir -o sum_scheduled.mir
$ llc -start-after=machine-scheduler sum_scheduled.mir -o sum.s
    $ llc -verify-machineinstrs sum.ll

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

  • LLVM's Analysis and Transform Passes
    • Pass 主要可以分為兩類，Analysis Passes 和 Transform Passes。Transform 依賴 Analysis 的結果。Pass Manager 根據 Pass 之間的依賴關係執行調度。比如要先執行 use analysis 再執行 dead code elimination。
    • 可以用 opt 在 LLVM IR 上運行各種 Pass，如: mem2reg 。
      # 對 sum.ll 運行 mem2reg Pass，再將其產生的 LLVM bitcode 反組譯成 LLVM IR。
$ opt -mem2reg sum.ll | llvm-dis
      ; Function Attrs: noinline nounwind ssp uwtable
define i32 @sum(i32 %a, i32 %b) #0 {
entry:
  %add = add nsw i32 %a, %b ; 可以觀察到 alloca 被消除。
  ret i32 %add
}
  • 加入自己的 Pass 請見 Writing an LLVM Pass
    $ opt -load=install/lib/libLLVMHello.so -hello < hello.bc > /dev/null
    • 如果出現底下錯誤訊息，請確定 opt 和 libLLVMHello.so 是同一份源碼和設定編譯而成。
      Error opening 'install/lib/libLLVMHello.so': install/lib/libLLVMHello.so: undefined symbol: _ZN4llvm4Pass26getAdjustedAnalysisPointerEPKv
  -load request ignored.
  • PassManager
    • Demystifying The LLVM Pass Manager 描述舊版 Pass Manager。
    • Passes in LLVM (2014/04) (Video) 和 The LLVM PassManager Part 2 (2014/10) (Video) 描述 PassManagerBuilder。
      • PassManagerBuilder 根據優化等級建立 pass pipeline。以 opt 為例: 
        static void AddOptimizationPasses(legacy::PassManagerBase &MPM,
                                  legacy::FunctionPassManager &FPM,
                                  TargetMachine *TM, unsigned OptLevel,
                                  unsigned SizeLevel) {
  if (!NoVerify || VerifyEach)
    FPM.add(createVerifierPass()); // Verify that input is correct
 
  PassManagerBuilder Builder;
  Builder.OptLevel = OptLevel;
  Builder.SizeLevel = SizeLevel;
 
  if (DisableInline) {
    // No inlining pass
  } else if (OptLevel > 1) {
    Builder.Inliner = createFunctionInliningPass(OptLevel, SizeLevel, false);
  } else {
    Builder.Inliner = createAlwaysInlinerLegacyPass();
  }
 
  Builder.populateFunctionPassManager(FPM);
  Builder.populateModulePassManager(MPM);
}
    • 舊版 PassManager 透過繼承，決定是 Function 還是 Module PassManager。
    • 新版 PassManager 透過模板參數，決定是 Function 還是 Module PassManager。
      extern template class PassManager<Module>;
typedef PassManager<Module> ModulePassManager;
 
extern template class PassManager<Function>;
typedef PassManager<Function> FunctionPassManager
  • TargetPassConfig
    • 目標平台在 TargetMachine.cpp 實現 TargetPassConfig，可以將目標平台所需的 pass 添加進 pipeline。

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，最後輸出匯編或是目的檔。
  • 延伸閱讀:
    • Register Allocation
      • LLVM Register Allocation (2008)
      • Future Works in LLVM Register Allocation (2009)
      • Register Allocation in LLVM 3.0 (2011)
      • LLVM Register Allocation (2nd Version)
      • Phi-Elimination → Register Coalescing → Register Allocation → Virtual Register Rewriter。
        $ llc -debug-pass=Structure sum.ll
      Eliminate PHI nodes for register allocation
      Simple Register Coalescing
      Greedy Register Allocator
      Virtual Register Rewriter
        • PHIElimination.cpp: PHIElimination::LowerPHINode() 改用 COPY 指令取代 PHI 指令。
        • RegisterCoalescer.cpp: RegisterCoalescer::joinCopy() 如果 COPY 指令的來源和目的暫存器其 interval 相同，消除該 COPY 指令。
        • VirtRegMap.cpp: 暫存器分配的結果存在 VirtRegMap，紀錄虛擬暫存器和物理暫存器的對應，VirtRegRewriter::runOnMachineFunction() 再根據 VirtRegMap 將 MI 中的虛擬暫存器改寫成物理暫存器。
      • 底下範例可以看到 PHI 消除前後，COPY 被置換成目標平台指令和虛擬暫存器轉為物理暫存器的過程。
        $ cat phi.c
void func(bool r, bool y) {
  bool l = y || r;
}
$ clang++ -O0 phi.c -mllvm -print-machineinstrs -c
# After Instruction Selection:
# Machine code for function func: IsSSA, TracksLiveness
 
BB#2: derived from LLVM BB %lor.end
    Predecessors according to CFG: BB#0 BB#1
        %vreg1<def> = PHI %vreg6, <BB#0>, %vreg13, <BB#1>; GR8:%vreg1,%vreg6,%vreg13
        %vreg15<def,tied1> = AND8ri %vreg1<tied0>, 1, %EFLAGS<imp-def>; GR8:%vreg15,%vreg1
        MOV8mr <fi#2>, 1, %noreg, 0, %noreg, %vreg15<kill>; mem:ST1[%l] GR8:%vreg15
        RETQ
 
# After Eliminate PHI nodes for register allocation:
# Machine code for function func: NoPHIs, TracksLiveness
 
BB#2: derived from LLVM BB %lor.end
    Predecessors according to CFG: BB#0 BB#1
        %vreg1<def> = COPY %vreg16; GR8:%vreg1,%vreg16
        %vreg15<def,tied1> = AND8ri %vreg1<tied0>, 1, %EFLAGS<imp-def>; GR8:%vreg15,%vreg1
        MOV8mr <fi#2>, 1, %noreg, 0, %noreg, %vreg15<kill>; mem:ST1[%l] GR8:%vreg15
        RETQ
 
# After Fast Register Allocator:
# Machine code for function func: NoPHIs, TracksLiveness, NoVRegs
 
BB#2: derived from LLVM BB %lor.end
    Predecessors according to CFG: BB#0 BB#1
        %AL<def> = MOV8rm <fi#3>, 1, %noreg, 0, %noreg; mem:LD1[FixedStack3]
        %AL<def,tied1> = AND8ri %AL<tied0>, 1, %EFLAGS<imp-def>
        MOV8mr <fi#2>, 1, %noreg, 0, %noreg, %AL<kill>; mem:ST1[%l]
        RETQ
    • MC

SelectionDAG

  • Introduction to SelectionDAGs
    • 一個 DAG 基本對應一個 BasicBlock，DAG 中的每一個節點 (SDNode) 基本對應一條 LLVM IR。TargetSelectionDAG.td 定義了 LLVM IR 對應的 SDNode。SDNode 之間是 producer-consumer 的關係，producer 產生 SDValue 給 consumer。SDValue 有底下三種型別:
      • concrete value type: 對映黑色實線。
      • Other: 對映藍色虛線。
      • Glue: 對映紅色實線。

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
  • X86ISelDAGToDAG.cpp
    • 負責將平台無關的 SDNode 換成平台相關的 SDNode。一般較為簡單的替換會寫成 *.td 檔 (SelectionDAG Select Phase，善用 TargetSelectionDAG.td 定義的 SDNode 寫匹配規則)，複雜的替換在此檔寫成 C++ 函式。
    • X86DAGToDAGISel::Select() 是入口點。
      • 預設經由 SelectCode(Node) 透過 *.td 檔所寫的匹配規則選擇指令，或者也可以針對特定 SDNode 生成其它 SDNode 進行置換。函式 SelectCode(Node) 由 tblgen 產生。

Global Instruction Selection

LLVM IR -> Global MI (GMI) -> MI
  • LLVM IR → Global MI (GMI): IRTranslator 負責將 LLVM IR 轉成 GMI，一條 LLVM IR 對映到零到多條 GMI。
  • GMI → MI: GMI 會經過 legalize 和 register bank select，再做 instruction selection 得到 MI。

Instruction Scheduling

  • SelectionDAG Scheduling and Formation Phase
    • 使用 list scheduling (Instruction scheduling)。list scheduling 作用於一個 basic block。首先為該 basic block 建立一個 data dependency graph，根據 hardware resource 和 data dependence 為每個節點計算出 priority。從 cycle 0 開始，從 data dependency graph 挑出 priority 最高的節點，放進空閒的 function unit 執行。更新 data dependency graph，重新計算 priority，重複前一個步驟。
    • 前述方法為 top-down list scheduling。如果把 data dependency graph 上面的 edge 反向，則為 bottom-up list scheduling。top-down list scheduling 是看節點的 depth 是否小於當前 cycle; bottom-up list scheduling 則是看節點的 high 是否小於當前 cycle，來決定是否要挑選該節點。
  • 在 LLVM 中，instruction scheduler 共有三類。
    • 兩類是 pre-register allocation scheduler，一類是 post-register allocation scheduler。
    • 兩類中的第一個作用在 SelectionDAG，後兩者作用在 MI。
    • 目前作用在 SelectionDAG 的 pre-register allocation scheduler 基本只負責將 SelectionDAG 轉成 MI。真正做調度的是作用在 MI 的 scheduler。
      # 顯示 SDNode Sched DAG。
$ llc -view-sunit-dags sum.ll
# 顯示 MI Sched DAG, pre-RA 和 post-RA。
$ llc -view-misched-dags sum.ll
# pre-RA, SDNode
$ llc -pre-RA-sched
# pre-RA, MI
$ llc -enable-misched
# post-RA, MI
$ llc -enable-post-misched
  • 術語:
    • SUnit (Scheduling Unit)
      • 提供一層抽象，既可表示 SDNode，也可以表示 MachineInstr，以便能在 SelectionDAG 和 MI 做指令調度。
    • SDep (Scheduling dependency)
      • 調度圖中，SUnit 是節點 (指令)，SDep 是節點之間的有向邊 (表示依賴關係)。SUnit 的 depth 代表從該節點向上，直到沒有 predecessor 的節點為止，最長的路徑; SUnit 的 high 代表從該節點向下，直到沒有 successor 的節點為止，最長的路徑。
    • SchedRegion
      • basic block 中，不考慮被調度的指令被視為 scheduling boundary，將 basic block 切分成數個 region。調度時，針對 region 依序處理。
    • Itinerary
      • 原意為旅程，描述指令執行會經過的 pipeline stage。
    • Bypass: 即 data forwarding (Pipelining with bypassing)。複習 Classic RISC pipeline。Interlock 是處理 data hazard 的另一種方式，即在指令之間插入 nop。
  • TD 檔案:
    • TargetSchedule.td 用 SchedMachineModel，SchedReadWrite 和 Itineraries 來描述調度訊息。
      • SchedMachineModel 定義最基本的調度屬性。
        class SchedMachineModel {
  int IssueWidth = -1;
  int MicroOpBufferSize = -1;
  int LoopMicroOpBufferSize = -1;

  int LoadLatency = -1;
  int HighLatency = -1;
  int MispredictPenalty = -1;

  ProcessorItineraries Itineraries = NoItineraries;
  bit PostRAScheduler = 0;
  bit CompleteModel = 1;
  list<Predicate> UnsupportedFeatures = [];
  bit NoModel = 0;
}
        • 一般 subtarget 都會定義自己的 SchedMachineModel。HexagonScheduleV60.td
          def HexagonModelV60 : SchedMachineModel {
  // Max issue per cycle == bundle width.
  let IssueWidth = 4;
  let Itineraries = HexagonItinerariesV60;
  let LoadLatency = 1;
  let CompleteModel = 0;
}
      • SchedReadWrite 可以針對指令的輸入輸出做更精細的設定。
        • Writing Great Machine Schedulers (2017)
          class SchedReadWrite;

class Sched<list<SchedReadWrite> schedrw> {
  list<SchedReadWrite> SchedRW = schedrw;
}

class SchedWrite : SchedReadWrite;

class SchedRead  : SchedReadWrite;

class ProcResource<int num> : ProcResourceKind,
  ProcResourceUnits<EponymousProcResourceKind, num>;
  
class WriteRes<SchedWrite write, list<ProcResourceKind> resources>
  : ProcWriteResources<resources> {
  SchedWrite WriteType = write;
}

class ReadAdvance<SchedRead read, int cycles, list<SchedWrite> writes = []>
  : ProcReadAdvance<cycles, writes> {
  SchedRead ReadType = read;
}
        • 針對目標平台的 FuncUnit，定義 SchedRead/SchedWrite 和 ProcResource。再將指令操作數和對應的 SchedRead/SchedWrite 綁定。針對 SchedRead 設定 ReadAdvance; 針對 SchedWrite 設定 WriteRes。ARMSchedule.td 和 ARMScheduleR52.td
          // Basic ALU operation.
def WriteALU : SchedWrite;
def ReadALU : SchedRead;

def R52UnitALU    : ProcResource<2> { let BufferSize = 0; } // Int ALU

def : WriteRes<WriteALU, [R52UnitALU]> { let Latency = 3; }

def : ReadAdvance<ReadALU, 1>;
        • 針對 subtarget 微調。SchedWriteRes SchedReadAdvance 搭配 InstRW 和 instregex 使用。
      • TargetItinerary.td 定義指令調度所需要的資訊。FuncUnit 描述功能單元。Bypass 描述可以將運算結果 forward 的通路。InstrItinData 針對屬於同一個 InstrItinClass 的指令，描述其 InstrStage (InstrStage 描述指令完成該 stage 所需的 FuncUnit 和 cycle 數)，其運算元於第幾個 cycle 準備好，以及 Bypass 訊息。
        class ProcessorItineraries<list<FuncUnit> fu, list<Bypass> bp,
                           list<InstrItinData> iid> {
  list<FuncUnit> FU = fu;
  list<Bypass> BP = bp;
  list<InstrItinData> IID = iid;
}
        • HexagonSchedule.td 定義基本的FuncUnit，Bypass 和 InstrItinClass。不同系列的晶片可以定義自己的指令調度資訊，例如: HexagonScheduleV4.td 定義 ProcessorItineraries 和 SchedMachineModel，其中 SchedMachineModel 會使用到 ProcessorItineraries。
  • 其它檔案:
    • ScheduleDAG.h
    • MachineScheduler.h 是 MI scheduler 重要檔案。
      • ScheduleDAGMILive
        • 基本上 MI scheduler 都繼承於它。入口點是 schedule，在 MachineScheduler/PostMachineScheduler/PostRASchedulerList 的 runOnMachineFunction 被調用。
      • ScheduleDAGMutation
        • 可以調整 DAG 節點之間的依賴關係。於 ScheduleDAGMI::postprocessDAG 在 ScheduleDAGMILive::schedule 被調用。
        • 參考 HexagonSubtarget::HVXMemLatencyMutation。注意，調整 latency，必須同時調整 predecessor 和 successor 的 latency。改變 successor 的 latency，必須將 predecessor 的 height 設成 dirty; 反之，改變 predecessor 的 latency，必須將 successor 的 depth 設成 dirty。
      • MachineSchedStrategy
        • MachineSchedStrategy 可以作為參數傳遞給 ScheduleDAGMILive。其客製化的 pickNode 和 schedNode 在 ScheduleDAGMILive::schedule 被調用。。
        • GenericScheduler 為 MachineSchedStrategy 預設實現。
    • MachineScheduler.cpp 和 PostRASchedulerList 是 MI scheduler pass 重要檔案。MI scheduler pass 在 runOnMachineFunction 中，會調用到 MI scheduler 的 schedule 進行調度。
      • MachineScheduler 是 pre-register allocation scheduler pass。
      • PostMachineScheduler 是 post-register allocation scheduler pass。
      • PostRASchedulerList 是 post-register allocation scheduler pass。預設執行這一個，而不是前面的 PostMachineScheduler。
  • ScheduleDAGMI 和 ScheduleDAGMILive 主要差異請看各自的 schedule() 實現 (ScheduleDAGMI::schedule()ScheduleDAGMILive::schedule())。
    • ScheduleDAGMILive 基本上是在 ScheduleDAGMI 的基礎上，增加暫存器壓力的紀錄。
        buildSchedGraph(AA);
 
  findRootsAndBiasEdges(TopRoots, BotRoots);
 
  SchedImpl->initialize(this); // SchedImpl 為 MachineSchedStrategy 的實例。
 
  initQueues(TopRoots, BotRoots);
 
  bool IsTopNode = false;
  while (true) {
    // 如果 SU 為 nullptr，或為非法，跳出循環。
    SUnit *SU = SchedImpl->pickNode(IsTopNode);
 
    // ScheduleDAGMILive 調用 scheduleMI，其基礎為原來 ScheduleDAGMI 的代碼。
    // 此處透過 moveInstruction 調整 SU 對應 MI 在原來 basic block 的位置。
 
    SchedImpl->schedNode(SU, IsTopNode);
 
    updateQueues(SU, IsTopNode);
  }
  • Hexagon 使用到 VILW 相關的指令調度。
    • VLIW Packetizer
    • 術語:
      • Packet: 即 VLIW 中的 bundle。
      • RPTracker: RegPressureTracker。用來紀錄當前 virtual register pressure，避免指令調度造成後續暫存器分配產生 spill。
        • RPTracker will cover the entire DAG region, TopTracker and BottomTracker will be initialized to the top and bottom of the DAG region without covereing any unscheduled instruction.
    • PreRA scheduler
      • HexagonMachineScheduler.h
        • VLIWResourceModel
          • 包裝 DFAPacketizer (ResourcesModel) 和 TargetSchedModel (SchedModel)。主要用來看 SU 是否能放在當前的 Packet (VLIWResourceModel::isResourceAvailable())。
        • VLIWMachineScheduler
          • VLIWMachineScheduler 繼承 ScheduleDAGMILive，ScheduleDAGMILive 做 instruction scheduling 的同時，也考慮 register pressure。因此可以知道 VLIWMachineScheduler 在 register allocation 之前執行。VLIWMachineScheduler 基本只是 override ScheduleDAGMILive 的 schedule() 接口，供上層回調。
        • ConvergingVLIWScheduler
          • ConvergingVLIWScheduler 繼承 MachineSchedStrategy，主要 override MachineSchedStrategy 的 pickNode 和 schedNode。
      • HexagonMachineScheduler.cpp
        • 入口點位於 schedule()。實際挑選節點，並更新 data dependency graph 各節點 priority 的工作交給 SchedImpl (即 ConvergingVLIWScheduler)。
      • HexagonPassConfig 複寫 createMachineScheduler，回傳 VLIWMachineScheduler。createMachineScheduler 在 MachineScheduler::runOnMachineFunction 被調用。透過這樣的方式，Hexagon 執行自己的 PreRA scheduler。
    • PostRA scheduler
      • 採用 PostRASchedulerList。Hexagon 分別透過 getHazardType 和 EmitInstruction 改變調度結果。
        ScheduleHazardRecognizer::HazardType
HexagonHazardRecognizer::getHazardType(SUnit *SU, int stalls) {
  if (!Resources->canReserveResources(*MI)) {
    DEBUG(dbgs() << "*** Hazard in cycle " << PacketNum << ", " << *MI);
    HazardType RetVal = Hazard;
    if (TII->mayBeNewStore(*MI)) {
      // Make sure the register to be stored is defined by an instruction in the
      // packet.
      MachineOperand &MO = MI->getOperand(MI->getNumOperands() - 1);
      if (!MO.isReg() || RegDefs.count(MO.getReg()) == 0)
        return Hazard;
      // The .new store version uses different resources so check if it
      // causes a hazard.
      MachineFunction *MF = MI->getParent()->getParent();
      MachineInstr *NewMI =
        MF->CreateMachineInstr(TII->get(TII->getDotNewOp(*MI)),
                               MI->getDebugLoc());
      if (Resources->canReserveResources(*NewMI))
        RetVal = NoHazard;
      DEBUG(dbgs() << "*** Try .new version? " << (RetVal == NoHazard) << "\n");
      MF->DeleteMachineInstr(NewMI);
    }
    return RetVal;
  }
}
    • Packetizer
    • Hexagon 有 packetize 的測試用例。
      $ lldb llc
(lldb) b HexagonPacketizer::runOnMachineFunction
(lldb) b VLIWPacketizerList::PacketizeMIs
(lldb) r test/CodeGen/Hexagon/packetize_cond_inst.ll
  • TargetPassConfig 有兩個虛擬函式 createMachineScheduler 和 createPostMachineScheduler 可以被覆寫。可以返回 ScheduleDAGInstrs 的子類，或是只返回 ScheduleDAGInstrs 的實例，傳入客制的 MachineSchedStrategy。又或是透過 substitutePass 將預設執行的 PostRASchedulerList 替換成 PostMachineScheduler。
    • 目前有 ARM/AArch64 和 SystemZ 使用 PostMachineScheduler。ARM/AArch64 使用預設的 MachineSchedStrategy，PostGenericScheduler，並加上自訂的 Mutation。SystemZ 使用自訂的 SystemZPostRASchedStrategy。
    • PostGenericScheduler 和用於 pre-register allocation 的 GenericScheduler 不同。PostGenericScheduler 只做 top-down scheduling。專注 PostGenericScheduler::pickNode。
    • SchedCandidate: 存放候選節點相關訊息。tryCandidate() 挑選節點。
      • CandPolicy: 於此候選節點所在區域中，挑選下一個候選節點所採用的策略。可以傾向 resource 受限或是 latency 受限，前者反映 structural hazard，後者反映 data hazard。透過 setPolicy() 設置。
      • CandReason: 表示該節點被選上的原因。原因之間有優先級之分。以 tryLess() 為例:
        // 取 TryVal 和 CandVal 中最小的。
static bool tryLess(int TryVal, int CandVal,
                    GenericSchedulerBase::SchedCandidate &TryCand,
                    GenericSchedulerBase::SchedCandidate &Cand,
                    GenericSchedulerBase::CandReason Reason) {
  if (TryVal < CandVal) {
    TryCand.Reason = Reason;
    return true;
  }
  if (TryVal > CandVal) {
    // Reason 越小，優先級越高。把 Cand.Reason 替換掉。
    if (Cand.Reason > Reason)
      Cand.Reason = Reason;
    return true;
  }
  return false;
}
        • 如果 TryVal 和 CandVal 相等，返回 false，進行下一條件比較。

Example

  • 以 Hexagon 為例，觀察其使用的 scheduler。
    $ llc -O2 -debug-pass=Structure test/CodeGen/Hexagon/packetize_cond_inst.ll
    • Machine Instruction Scheduler (MachineScheduler.cpp): pre-register allocation MI scheduler。
    • Post RA top-down list latency scheduler (PostRASchedulerList.cpp): post-register allocation MI scheduler。
      • 從 runOnMachine 開始，直到 SchedulePostRATDList::ListScheduleTopDown 開始實際的調度。
        void SchedulePostRATDList::ListScheduleTopDown() {
  while (!AvailableQueue.empty() || !PendingQueue.empty()) {
 
  }
        • 主要維持兩個佇列，AvailableQueue 和 PendingQueue。如果 PendingQueue 中的指令，其結果已經運算完成，會被放到 AvailableQueue。最終會從 AvailableQueue 中挑出當前 cycle 要執行的指令。
  • 以 Hexagon 為例，判讀 debug 訊息。
    $ llc -O2 -debug-only=post-RA-sched test/CodeGen/Hexagon/packetize_cond_inst.ll
********** List Scheduling **********
SU(0):   %P0<def> = C4_cmplte %R2, %R1
  # preds left       : 0
  # succs left       : 3
  # rdefs left       : 0
  Latency            : 1
  Depth              : 0
  Height             : 4
  Successors:
    SU(2): Data Latency=1 Reg=%P0
    SU(1): Data Latency=1 Reg=%P0
    SU(1): Anti Latency=0
 
SU(1):   %R1<def> = A2_paddt %P0, %R2<kill>, %R1<kill>
  # preds left       : 2
  # succs left       : 2
  # rdefs left       : 0
  Latency            : 1
  Depth              : 1
  Height             : 3
  Predecessors:
    SU(0): Data Latency=1 Reg=%P0
    SU(0): Anti Latency=0
  Successors:
    SU(2): Out  Latency=1
    SU(2): Data Latency=1 Reg=%R1
    • 一開始印出 SUnit 在 dependency graph 中的各種屬性，以及和其它 SUnit 的依賴關係。
    • 接著打印出調度的過程。
      Reset hazard recognizer

*** Examining Available
*** Scheduling [0]: SU(0):   %P0<def> = C4_cmplte %R2, %R1
 Add instruction %P0<def> = C4_cmplte %R2, %R1

*** Examining Available
*** Finished cycle 0
Advance cycle, clear state

TableGen

  • TableGen: TableGen 語法近似 C++ class template，借用函數式編程相關的語法。
    • TableGen Language Introduction: 需要寫 *.td 可以參考這份文件。
      • TableGen 裡所提到的 backend (TableGen BackEnds)，指的是其命令行選項，如: -print-records (-print-records 是預設後端)。
      • TableGen 裡的 class 和 def 都是 record。 class 類似 C++ 裡的 Class，def 類似 C++ 裡的 Object。
    • TableGen Language Reference: 需要 parsing *.td 可以參考這份文件。
  • Register (Target.td)
    • SubRegIndex
      • list<Register> SubRegs 和 list<SubRegIndex> SubRegIndices 一起搭配。前者定義此 register 包含哪些 sub-register，後者用來定位 (index) 這些 sub-register。以 X86RegisterInfo.td 為例:
        class X86Reg<string n, bits<16> Enc, list<Register> subregs = []> : Register<n> {
  let Namespace = "X86";
  let HWEncoding = Enc;
  let SubRegs = subregs;
}

let Namespace = "X86" in {
  def sub_8bit    : SubRegIndex<8>;
  def sub_8bit_hi : SubRegIndex<8, 8>; // 此 subreg 大小為 8 bit，在 reg 從 offset 8 bit 開始。
  def sub_16bit   : SubRegIndex<16>;
  def sub_32bit   : SubRegIndex<32>;
  def sub_xmm     : SubRegIndex<128>;
  def sub_ymm     : SubRegIndex<256>;
}

let SubRegIndices = [sub_8bit, sub_8bit_hi], CoveredBySubRegs = 1 in {
def AX : X86Reg<"ax", 0, [AL,AH]>; // AX 由 AL 和 AH 兩個 subreg 組成，AL 和 AH 如何在 AX 佔位由 SubRegIndices 描述。
def DX : X86Reg<"dx", 2, [DL,DH]>;
def CX : X86Reg<"cx", 1, [CL,CH]>;
def BX : X86Reg<"bx", 3, [BL,BH]>;
}
    • RegisterClass。以 X86RegisterInfo.td 為例:
      class RegisterClass<string namespace, list<ValueType> regTypes, int alignment,
                    dag regList, RegAltNameIndex idx = NoRegAltName>

def GR32 : RegisterClass<"X86", [i32], 32,
                         (add EAX, ECX, EDX, ESI, EDI, EBX, EBP, ESP,
                              R8D, R9D, R10D, R11D, R14D, R15D, R12D, R13D)>;
  • Instruction (Target.td)
    • 其中的 list<dag> Pattern 欄位即是用來撰寫指令選擇所需要的 pattern match。
    • 目標平台撰寫的指令都是 Instruction 的子類。以 Sparc 為例 (SparcInstrInfo.td)
      def XNORrr  : F3_1<2, 0b000111,
                   (outs IntRegs:$rd), 輸出
                   (ins IntRegs:$rs1, IntRegs:$rs2), 輸入
                   "xnor $rs1, $rs2, $rd", // 匯編指令
                   [(set i32:$rd, (not (xor i32:$rs1, i32:$rs2)))] // DAG 匹配樣式，$rd = not ($rs1 xor $rs2)
                   >;
      • F3_1 定義於 SparcInstrFormats.td，繼承自 Instruction (Target.td)。
      • 匹配到 DAG $rd = not ($rs1 xor $rs2) 之後，會將其替換成 XNORrr。
  • Operand (Target.td)
    • ValueType (ValueTypes.td)
      class Operand<ValueType ty> : DAGOperand {
  ValueType Type = ty;
  string PrintMethod = "printOperand";
  string EncoderMethod = "";
  bit hasCompleteDecoder = 1;
  string OperandType = "OPERAND_UNKNOWN";
  dag MIOperandInfo = (ops);
  
  ...
}
    • Target.td 有定義一些 operand，但針對地址計算這一類的 operand 而言，一般要目標平台自行定義。
      /// PointerLikeRegClass - Values that are designed to have pointer width are
/// derived from this.  TableGen treats the register class as having a symbolic
/// type that it doesn't know, and resolves the actual regclass to use by using
/// the TargetRegisterInfo::getPointerRegClass() hook at codegen time.
class PointerLikeRegClass<int Kind> {
  int RegClassKind = Kind;
}


/// ptr_rc definition - Mark this operand as being a pointer value whose
/// register class is resolved dynamically via a callback to TargetInstrInfo.
/// FIXME: We should probably change this to a class which contain a list of
/// flags. But currently we have but one flag.
def ptr_rc : PointerLikeRegClass<0>;

def MEMrr : Operand<iPTR> {
  let PrintMethod = "printMemOperand";
  let MIOperandInfo = (ops ptr_rc, ptr_rc);
  let ParserMatchClass = SparcMEMrrAsmOperand;
}
def MEMri : Operand<iPTR> {
  let PrintMethod = "printMemOperand";
  let MIOperandInfo = (ops ptr_rc, i32imm);
  let ParserMatchClass = SparcMEMriAsmOperand;
}
  • Calling Convention (TargetCallingConv.td)
    • Calling Conventions
    • 一般寫在各自的 CallingConv.td。例如: X86CallingConv.td。又或者寫在 RegisterInfo.td。例如: HexagonRegisterInfo.td。
    • 定義 callee saved register。
      class CalleeSavedRegs<dag saves> {
  dag SaveList = saves;
  dag OtherPreserved;
}

def HexagonCSR
  : CalleeSavedRegs<(add R16, R17, R18, R19, R20, R21, R22, R23,
                         R24, R25, R26, R27)>;
    • 根據參數型別，透過特定暫存器傳遞，這是一種 action。TargetCallingConv.td 提供多種 action 設定方式。
      class CCIfType<list<ValueType> vts, CCAction A> : CCPredicateAction<A> {
  list<ValueType> VTs = vts;
}

class CCAssignToReg<list<Register> regList> : CCAction {
  list<Register> RegList = regList;
}

CCIfType<[f32,f64], CCAssignToReg<[R0, R1]>>
    • 可以將數條 action 打包在一起，作為一組 calling convention。例如針對不同返回值，透過不同暫存器傳遞。
      class CallingConv<list<CCAction> actions> {
  list<CCAction> Actions = actions;
  bit Custom = 0;
}

def RetCC_Sparc32 : CallingConv<[
  CCIfType<[i32], CCAssignToReg<[I0, I1]>>,
  CCIfType<[f32], CCAssignToReg<[F0]>>,
  CCIfType<[f64], CCAssignToReg<[D0]>>
]>;
  • Intrinsics
    • [llvm-dev] add intrinsic function support for customized backend
    • [llvm-dev] ADDING A CUSTOM INSTRINSIC
    • 先在 LLVM 加上支持，再修改 Clang 處理 intrinsic。
      __builtin_yyy -> @llvm.xxx.yyy -> yyy
      • Clang
        • 各平台的 intrinsic 各自定義在 tools/clang/include/clang/Basic/ 底下。例如: BuiltinsARM.def。會用到 Builtins.def 定義的型別和屬性。
          BUILTIN(__builtin_atan2 ,      "ddd"   ,    "Fnc"    )
         builtin 函式名     返回和參數型別   builtin 屬性
        • CodeGenFunction.h: 宣告 Clang 遇到 builtin/intrinsic 時要調用的 Emit 函式。例如: EmitARMBuiltinExpr。
        • CGBuiltin.cpp: 定義 Clang 遇到 builtin/intrinsic 時要調用的 Emit 函式。例如: EmitARMBuiltinExpr。EmitTargetArchBuiltinExpr() 調用定義前述的 Emit 函式。
        • SemaChecking.cpp: 如有需要，添加對 intrinsic 參數的檢查。例如: Sema::CheckARMBuiltinFunctionCall。
      • LLVM
        • 在 include/llvm/IR/ 底下平台各自定義 LLVM IR 階段會產生的 intrinsic，以 llvm.xxx 開頭，其中 xxx 為目標平台名稱。例如: IntrinsicsHexagon.td。會用到 Intrinsics.td 中定義的型別和屬性。注意！在 Intrinsics.td 最後要引用自己定義的 *.td 檔。
          def int_xxx_foo : Intrinsic<[llvm_i32_ty], [llvm_i32_ty, llvm_i32_ty], [IntrReadArgMem]>;
                               返回型別               參數型別                  屬性
        • 在 lib/Target/ 底下各自的目錄定義如何將 LLVM IR 中的 intrinsic 對應到實際的指令。例如: HexagonIntrinsics.td。
          let isPseudo = 1 in {
  def FOO : PseudoI<(outs i32mem:$dst),
                    (ins i32mem:$src1, i32mem:$src2,),
                    [(set i32mem:$dst, (int_xxx_foo i32mem:$src1, i32mem:$src2))]>;
}
  • TargetSelectionDAG.td
    • SDNode
      class SDNode<string opcode, SDTypeProfile typeprof,
             list<SDNodeProperty> props = [], string sdclass = "SDNode">
             : SDPatternOperator {
  string Opcode  = opcode;
  string SDClass = sdclass;
  let Properties = props;
  SDTypeProfile TypeProfile = typeprof;
}

def imm        : SDNode<"ISD::Constant"  , SDTIntLeaf , [], "ConstantSDNode">;
    • PatFrag/OutPatFrag/PatLeaf/ImmLeaf
      class PatFrag<dag ops, dag frag, code pred = [{}],
              SDNodeXForm xform = NOOP_SDNodeXForm> : SDPatternOperator {
  dag Operands = ops;
  dag Fragment = frag;
  code PredicateCode = pred;
  code ImmediateCode = [{}];
  SDNodeXForm OperandTransform = xform;
}
    • Pattern/Pat
      class Pattern<dag patternToMatch, list<dag> resultInstrs> {
  dag             PatternToMatch  = patternToMatch;
  list<dag>       ResultInstrs    = resultInstrs;
  list<Predicate> Predicates      = [];  // See class Instruction in Target.td.
  int             AddedComplexity = 0;   // See class Instruction in Target.td.
}

class Pat<dag pattern, dag result> : Pattern<pattern, [result]>;
                匹配         輸出
      • dag 是 TableGen 自定義型別。Pat 會匹配 pattern，輸出 result。dag 可以使用的 operator 來自 Target.td (如: COPY_TO_REGCLASS) 或是 TargetSelectionDAG.td (如: add)。
        • HexagonIntrinsics.td
          class T_I_pat <InstHexagon MI, Intrinsic IntID>
  : Pat <(IntID imm:$Is), // 匹配
         (MI imm:$Is)>;   // 輸出
        • HexagonPatterns.td
          def: Pat<(i64 (add I64:$Rs, I64:$Rt)), (A2_addp I64:$Rs, I64:$Rt)>;
                     匹配                          輸出

Register Pair

  • 支持 quad-register (SIRegisterInfo.td)。
    class RegisterTuples<list<SubRegIndex> Indices, list<dag> Regs> {
  // SubRegs - N lists of registers to be zipped up. Super-registers are
  // synthesized from the first element of each SubRegs list, the second
  // element and so on.
  list<dag> SubRegs = Regs;

  // SubRegIndices - N SubRegIndex instances. This provides the names of the
  // sub-registers in the synthesized super-registers.
  list<SubRegIndex> SubRegIndices = Indices;
}

// VGPR_32 共有 VGPR0 ~ VGPR255 個暫存器。
def VGPR_32 : RegisterClass<"AMDGPU", [i32, f32, i16, f16, v2i16, v2f16], 32,
                            (add (sequence "VGPR%u", 0, 255))> {
  let AllocationPriority = 1;
  let Size = 32;
}

// VGPR 128-bit registers
def VGPR_128 : RegisterTuples<[sub0, sub1, sub2, sub3],
                              [(add (trunc VGPR_32, 253)), // VGPR0 ~ VGPR252
                               (add (shl VGPR_32, 1)),     // VGPR1 ~ VGPR255
                               (add (shl VGPR_32, 2)),     // VGPR2 ~ VGPR255
                               (add (shl VGPR_32, 3))]>;   // VGPR3 ~ VGPR255
                               
def VReg_128 : RegisterClass<"AMDGPU", [v4i32, v4f32, v2i64, v2f64], 32, (add VGPR_128)> {
  let Size = 128;

  // Requires 4 v_mov_b32 to copy
  let CopyCost = 4;
  let AllocationPriority = 4;
}
    • trunc 將第 N 個元素以後的元素從集合中截去。
    • shl 移除集合中前 N 個元素。
    • decimate 從集合中挑出所有第 N 個元素。
// 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

  • 區分不同 subtaregt 的指令。Predicates 和 Requires 只對有寫 pattern match 的指令起作用。Predicates 是 Pat 父類別 Pattern 的成員，Requires 是獨立的類別。
    def HasV5T : Predicate<"HST->hasV5TOps()">, AssemblerPredicate<"ArchV5">;

let Predicates = [HasV5T] in {
  def: Pat<(f32 (fminnum F32:$Rs, F32:$Rt)), (F2_sfmin F32:$Rs, F32:$Rt)>;
  def: Pat<(f32 (fmaxnum F32:$Rs, F32:$Rt)), (F2_sfmax F32:$Rs, F32:$Rt)>;
}

def: Pat<(sra (add (sra I64:$src, u6_0ImmPred:$u6), 1), (i32 1)),
         (S2_asr_i_p_rnd DoubleRegs:$src, imm:$u6)>, Requires<[HasV5T]>;

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 為例。Hexagon.td 定義多個 InstrMapping (Target.td)。此處定義的 InstrMapping，如: getPredOpcode，會生成為一個函式供人調用。
    def getPredOpcode : InstrMapping {
  // 描述此 mapping 的字串。
  let FilterClass = "PredRel";

  // add/add.t/add.f 和 sub/sub.t/sub.f 分別有相同的 RowFields。
  let RowFields = ["BaseOpcode", "isNVStore", "PNewValue", "isBrTaken", "isNT"];

  // add/sub，add.t/sub.t 和 add.f/sub.f 分別有相同的 ColFields。   
  let ColFields = ["PredSense"];
  
  // 取 ColFields 某值作為 mapping 中的 key。這裡取 add 和 sub 作為 key。
  let KeyCol = [""];
  
  // 取 ColFields 某值作為 mapping 中的 value。add 映射到 add.t/add.f，sub 映射到 sub.t/sub.f。
  let ValueCols = [["true"], ["false"]]; 
}
  • HexagonInstrFormats.td 在 InstHexagon 中添加 InstrMapping 所需要的欄位。
    class InstHexagon<dag outs, dag ins, string asmstr, list<dag> pattern,
                  string cstr, InstrItinClass itin, IType type>
  : Instruction {
  let Namespace = "Hexagon";

  // Fields used for relation models.
  string isNT = ""; // set to "true" for non-temporal vector stores.
  string BaseOpcode = "";
  string PredSense = "";
  string PNewValue = "";
  string isBrTaken = !if(isTaken, "true", "false"); // Set to "true"/"false" for jump instructions

  let PredSense = !if(isPredicated, !if(isPredicatedFalse, "false", "true"),
                                    "");
  let PNewValue = !if(isPredicatedNew, "new", "");
  let NValueST = !if(isNVStore, "true", "false");
  let isNT = !if(isNonTemporal, "true", "false");
}
    • 此處搭配 TSFlag (Target.td) 設置 RowFields 和 ColFields。
  • HexagonDepInstrInfo.td 定義彼此互有關聯的指令。
    class HInst<dag outs, dag ins, string asmstr, InstrItinClass itin, IType type> :
      InstHexagon<outs, ins, asmstr, [], "", itin, type>;

def A2_add : HInst<
(outs IntRegs:$Rd32),
(ins IntRegs:$Rs32, IntRegs:$Rt32),
"$Rd32 = add($Rs32,$Rt32)",
tc_548f402d, TypeALU32_3op>, Enc_5ab2be, PredNewRel, ImmRegRel {
let Inst{7-5} = 0b000;
let Inst{13-13} = 0b0;
let Inst{31-21} = 0b11110011000;
let hasNewValue = 1;
let opNewValue = 0;
let CextOpcode = "A2_add";
let InputType = "reg";
let BaseOpcode = "A2_add";
let isCommutable = 1;
let isPredicable = 1;
}
      
def A2_paddf : HInst<
(outs IntRegs:$Rd32),
(ins PredRegs:$Pu4, IntRegs:$Rs32, IntRegs:$Rt32),
"if (!$Pu4) $Rd32 = add($Rs32,$Rt32)",
tc_1b6011fb, TypeALU32_3op>, Enc_ea4c54, PredNewRel, ImmRegRel {
let Inst{7-7} = 0b1;
let Inst{13-13} = 0b0;
let Inst{31-21} = 0b11111011000;
let isPredicated = 1;
let isPredicatedFalse = 1;
let hasNewValue = 1;
let opNewValue = 0;
let CextOpcode = "A2_add";
let InputType = "reg";
let BaseOpcode = "A2_add";
}

def A2_paddt : HInst<
(outs IntRegs:$Rd32),
(ins PredRegs:$Pu4, IntRegs:$Rs32, IntRegs:$Rt32),
"if ($Pu4) $Rd32 = add($Rs32,$Rt32)",
tc_1b6011fb, TypeALU32_3op>, Enc_ea4c54, PredNewRel, ImmRegRel {
let Inst{7-7} = 0b0;
let Inst{13-13} = 0b0;
let Inst{31-21} = 0b11111011000;
let isPredicated = 1;
let hasNewValue = 1;
let opNewValue = 0;
let CextOpcode = "A2_add";
let InputType = "reg";
let BaseOpcode = "A2_add";
}
  • HexagonInstrInfo.cpp 再利用之前定義的 InstrMapping 接口，取得不同版本的的指令。
    int HexagonInstrInfo::getCondOpcode(int Opc, bool invertPredicate) const {
  enum Hexagon::PredSense inPredSense;
  inPredSense = invertPredicate ? Hexagon::PredSense_false :
                                  Hexagon::PredSense_true;
  int CondOpcode = Hexagon::getPredOpcode(Opc, inPredSense);
  if (CondOpcode >= 0) // Valid Conditional opcode/instruction
    return CondOpcode;
 
  llvm_unreachable("Unexpected predicable instruction");
}

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

  • isLegalToPacketizeTogether 檢視 SUI 是否能和 SUJ 做成一個 packet。
    bool HexagonPacketizerList::isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
 
  // SUJ 是當前 packet 內已存在的指令，檢查 SUI 是否和 SUJ 有依賴，以及該種依賴是否可以處理，
  // 使得 SUI 和 SUJ 可以放在同一個 packet。
  for (unsigned i = 0; i < SUJ->Succs.size(); ++i) {
    if (SUJ->Succs[i].getSUnit() != SUI)
      continue;
 
    // SUI 和 SUJ 是何種依賴?
    SDep::Kind DepType = SUJ->Succs[i].getKind();
 
    // For instructions that can be promoted to dot-new, try to promote.
    if (DepType == SDep::Data) {
      if (canPromoteToDotNew(I, SUJ, DepReg, II, RC)) {
        if (promoteToDotNew(I, DepType, II, RC)) {
          PromotedToDotNew = true;
          if (cannotCoexist(I, J))
            FoundSequentialDependence = true;
          continue;
        }
      }
      if (HII->isNewValueJump(I))
        continue;
    }
    • promoteToDotNew 透過 InstrMapping 生成的接口，返回當前指令對應的 Dot-New 版本。
      // Promote an instruction to its .new form. At this time, we have already
// made a call to canPromoteToDotNew and made sure that it can *indeed* be
// promoted.
bool HexagonPacketizerList::promoteToDotNew(MachineInstr &MI,
      SDep::Kind DepType, MachineBasicBlock::iterator &MII,
      const TargetRegisterClass* RC) {
  assert (DepType == SDep::Data);
  int NewOpcode;
  if (RC == &Hexagon::PredRegsRegClass)
    NewOpcode = HII->getDotNewPredOp(MI, MBPI);
  else
    NewOpcode = HII->getDotNewOp(MI);
  MI.setDesc(HII->get(NewOpcode));
  return true;
}

Writing Backend

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

  • CodeGen: 通用代碼生成算法。
  • MC: 匯編/反匯編相關。
  • TableGen: tblgen 代碼。LLVM 利用 tblgen 讀取目標平台 *.td 檔生成 instruction selector，instruction scheduling，register allocation 和 assembly printing。
    $ cd lib/Target/X86
$ llvm-tblgen X86.td -print-enums -class=Register -I ../../../include/
$ llvm-tblgen X86.td -print-enums -class=Instruction -I ../../../include/
    • TableGen
      • tblgen 語法近似 C++ template。*.td 檔主體為 record，record 分為兩類: class 和 definition。class 是模板 record，definition 是實例 record。
    • TableGen Language Introduction
      $ cat insns.td
// 指令基類
class Insn<bits <4> MajOpc, bit MinOpc> {
  bits<32> insnEncoding; // 指令編碼，長度 32 位。
  let insnEncoding{15-12} = MajOpc; // 第 15 至 12 位為 MajOpc
  let insnEncoding{11} = MinOpc;    // 第 11 位為 MinOpc
}
 
multiclass RegAndImmInsn<bits <4> opcode> {
  def rr : Insn<0x00, 0>; // MajOpc 皆為 0x00, MinOpc 分別為 0 和 1。
  def ri : Insn<0x00, 1>;
}
 
// SUB 指令
def SUB: Insn<0x00, 0>; // MajOpc = 0x00, MinOpc = 0
 
// ADD 指令。運算元可以是暫存器 + 暫存器，或是暫存器 + 立即數。
defm ADD : RegAndImmInsn<0x01>;
$ llvm-tblgen -print-records inst.td
  • Target: 不同後端有各自的子目錄。

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

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

JIT

其它特性

這裡放感興趣的特性。
  • Exception handling
    • Exception Handling support on the target
    • 在後端搜尋關鍵字 EH 和 CFI。
      • MCCFIInstruction
        • MCCFIInstruction::createDefCfaOffset: .cfi_def_cfa_offset
        • MCCFIInstruction::createOffset: .cfi_offset
      • X86FrameLowering.cpp
        • 注意 BuildCFI。
        • 分有無 FP 的情況。基本上在保存 callee-saved 暫存器，或是保存 FP 之後，需要生成 CFI。
      • 後端 TargetLowering 必須實現 getExceptionPointerRegister 和 getExceptionSelectorRegister。參考 X86ISelLowering.cpp。例外處理需要傳遞兩個指針，一個指向例外本身，另一個指向例外的型別。前者由 getExceptionPointerRegister 傳遞，後者由 getExceptionSelectorRegister 傳遞。
      • 關於 EH_RETURN，以 Mips 為例。參考 MipsInstrInfo.td 的註解:
        // Exception handling related node and instructions.
// The conversion sequence is:
// ISD::EH_RETURN -> MipsISD::EH_RETURN ->
// MIPSeh_return -> (stack change + indirect branch)
        • 在 MipsTargetLowering::lowerEH_RETURN (MipsISelLowering.cpp) 將 ISD::EH_RETURN 替換成 MipsISD::EH_RETURN。ISD::EH_RETURN 的 offset 和 handler 選擇可用的暫存器傳遞，MipsTargetLowering::lowerEH_RETURN 選擇使用暫存器 V0 和 V1 傳遞。
        • MipsDAGToDAGISel::Select (MipsDAGToDAGISel.cpp) 將 MipsISD::EH_RETURN 匹配成 MIPSeh_return32/MIPSeh_return64。MIPSeh_return32/MIPSeh_return64 是在 MipsInstrInfo.td 定義的偽指令。
          def SDT_MipsEHRET : SDTypeProfile<0, 2, [SDTCisInt<0>, SDTCisPtrTy<1>]>;

def MIPSehret : SDNode<"MipsISD::EH_RETURN", SDT_MipsEHRET,
                      [SDNPHasChain, SDNPOptInGlue, SDNPVariadic]>;

let Uses = [V0, V1], isTerminator = 1, isReturn = 1, isBarrier = 1, isCTI = 1 in {
  def MIPSeh_return32 : MipsPseudo<(outs), (ins GPR32:$spoff, GPR32:$dst),
                                [(MIPSehret GPR32:$spoff, GPR32:$dst)]>;   // lowerEH_RETURN 生成 (MipsISD::EH_RETURN V0, V1)
                                                                           // 和此處需要一致。
  def MIPSeh_return64 : MipsPseudo<(outs), (ins GPR64:$spoff,
                                                GPR64:$dst),
                                [(MIPSehret GPR64:$spoff, GPR64:$dst)]>;
}
        • MipsSEInstrInfo::expandEhReturn (MipsSEInstrInfo.cpp) 擴展偽指令 MIPSeh_return32/MIPSeh_return64，並生成指令，用 V0 調整棧，並將 V1 作為返回地址。
      • 關於 EH_RETURN，以 XCore 為例。於 XCoreInstrInfo.td 定義 EH_RETURN 偽指令。於 XCoreISelLowering.h 定義 XCoreISD::EH_RETURN。
        • 於 XCoreTargetLowering::LowerEH_RETURN (XCoreISelLowering.cpp) 將 ISD::EH_RETURN 轉成 XCoreISD::EH_RETURN，並將 offset 和 handler 保存至暫存器 R2 和 R3。__builtin_eh_return 在 _Unwind_RaiseException 被調用，其中 caller-saved 暫存器 R0 和 R1 已被 personality function 用於傳參，因此這裡使用暫存器 R2 和 R3 傳遞 offset 和 handler。 XCoreDAGToDAGISel::Select (XCoreISelDAGToDAG.cpp) 將 XCoreISD::EH_RETURN 替換成 EH_RETURN 偽指令。
        • XCoreFrameLowering::emitEpilogue (XCoreFrameLowering.cpp) 擴展偽指令 XCore::EH_RETURN，並生成指令，用 R2 調整棧，並將 R3 作為返回地址。
      • 關於 EH_RETURN，以 Hexagon 為例。
        • 於 HexagonPseudo.td 定義 EH_RETURN_JMPR 偽指令，於 HexagonPatterns.td 定義 pattern。
        • HexagonTargetLowering::LowerEH_RETURN (HexagonISelLowering.cpp) 將 ISD::EH_RETURN 轉成 HexagonISD::EH_RETURN，並將 offset 存到暫存器 R28，handler 存到暫存器 R30 所指向的內存。
        • HexagonDAGToDAGISel::Select (HexagonISelDAGToDAG.cpp) 將 HexagonISD::EH_RETURN 替換成 EH_RETURN_JMPR 偽指令。
        • HexagonFrameLowering::insertEpilogueInBlock (HexagonFrameLowering.cpp) 替換 EH_RETURN_JMPR 偽指令，並生成指令，用 R28 調整棧，並將 R30 所存的值作為返回地址。
      • 關於 EH_RETURN，以 X86 為例。
        • 於 X86InstrInfo.td 為 X86ISD::EH_RETURN 定義 X86ehret SDNode。X86InstrCompiler.td 定義偽指令 EH_RETURN。
        • X86TargetLowering::LowerEH_RETURN (X86ISelLowering.cpp) 將 ISD::EH_RETURN 轉成 X86ISD::EH_RETURN，並將 handler 存在 frame + offset 偏移處，且將 frame + offset 存在 ECX。
        • X86DAGToDAGISel::Select 將 X86ISD::EH_RETURN 替換成 X86::EH_RETURN 偽指令。
        • X86ExpandPseudo::ExpandMI (X86ExpandPseudo.cpp) 替換 X86::EH_RETURN 偽指令，並生成指令，將棧指針調整至 ECX 所指的位址。
  • 關於 emitPrologue/emitEpilogue，以 Mips 為例。可以透過 MipsFunctionInfo 或是 MachineFunctionInfo 定義的 callsEHReturn 得知函式是否有調用 eh_return。
    • MipsSEFrameLowering::emitPrologue (MipsSEFrameLowering.cpp)。注意！此處需要為例外處理需要用到的暫存器生成對應的 cfi。
         if (MipsFI->callsEhReturn()) {
     // Insert instructions that spill eh data registers.
     for (int I = 0; I < 4; ++I) {
       if (!MBB.isLiveIn(ABI.GetEhDataReg(I)))
         MBB.addLiveIn(ABI.GetEhDataReg(I));
       TII.storeRegToStackSlot(MBB, MBBI, ABI.GetEhDataReg(I), false,
                               MipsFI->getEhDataRegFI(I), RC, &RegInfo);
     }
 
     // Emit .cfi_offset directives for eh data registers.
     for (int I = 0; I < 4; ++I) {
       int64_t Offset = MFI.getObjectOffset(MipsFI->getEhDataRegFI(I));
       unsigned Reg = MRI->getDwarfRegNum(ABI.GetEhDataReg(I), true);
       unsigned CFIIndex = MF.addFrameInst(
           MCCFIInstruction::createOffset(nullptr, Reg, Offset));
       BuildMI(MBB, MBBI, dl, TII.get(TargetOpcode::CFI_INSTRUCTION))
           .addCFIIndex(CFIIndex);
     }
   }
    • MipsSEFrameLowering::emitEpilogue (MipsSEFrameLowering.cpp)。
         if (MipsFI->callsEhReturn()) {
     const TargetRegisterClass *RC =
         ABI.ArePtrs64bit() ? &Mips::GPR64RegClass : &Mips::GPR32RegClass;
 
     // Find first instruction that restores a callee-saved register.
     MachineBasicBlock::iterator I = MBBI;
     for (unsigned i = 0; i < MFI.getCalleeSavedInfo().size(); ++i)
       --I;
 
     // Insert instructions that restore eh data registers.
     for (int J = 0; J < 4; ++J) {
       TII.loadRegFromStackSlot(MBB, I, ABI.GetEhDataReg(J),
                                MipsFI->getEhDataRegFI(J), RC, &RegInfo);
     }
   }
    • MipsSEFrameLowering::determineCalleeSaves (MipsSEFrameLowering.cpp) 會調用 MipsFunctionInfo::createEhDataRegsFI (MipsMachineFunction.cpp) 為例外處理使用到的暫存器，創建 spill 空間。emitPrologue/emitEpilogue 依據該位置生成 load/store 代碼。
  • 關於 emitPrologue/emitEpilogue，以 XCore 為例。
    • XCoreFrameLowering::emitPrologue (XCoreFrameLowering.cpp)。
           if (XFI->hasEHSpillSlot()) {
       // The unwinder requires stack slot & CFI offsets for the exception info.
       // We do not save/spill these registers.
       const Function *Fn = &MF.getFunction();
       const Constant *PersonalityFn =
           Fn->hasPersonalityFn() ? Fn->getPersonalityFn() : nullptr;
       SmallVector<StackSlotInfo, 2> SpillList;
       GetEHSpillList(SpillList, MFI, XFI, PersonalityFn,
                      MF.getSubtarget().getTargetLowering());
       assert(SpillList.size()==2 && "Unexpected SpillList size");
       EmitCfiOffset(MBB, MBBI, dl, TII,
                     MRI->getDwarfRegNum(SpillList[0].Reg, true),
                     SpillList[0].Offset);
       EmitCfiOffset(MBB, MBBI, dl, TII,
                     MRI->getDwarfRegNum(SpillList[1].Reg, true),
                     SpillList[1].Offset);
     }
    • XCoreFrameLowering::emitPrologue (XCoreFrameLowering.cpp)。
         if (RetOpcode == XCore::EH_RETURN) {
     // 'Restore' the exception info the unwinder has placed into the stack
     // slots.
     const Function *Fn = &MF.getFunction();
     const Constant *PersonalityFn =
         Fn->hasPersonalityFn() ? Fn->getPersonalityFn() : nullptr;
     SmallVector<StackSlotInfo, 2> SpillList;
     GetEHSpillList(SpillList, MFI, XFI, PersonalityFn,
                    MF.getSubtarget().getTargetLowering());
     RestoreSpillList(MBB, MBBI, dl, TII, RemainingAdj, SpillList);
 
     // Return to the landing pad.
     unsigned EhStackReg = MBBI->getOperand(0).getReg();
     unsigned EhHandlerReg = MBBI->getOperand(1).getReg();
     BuildMI(MBB, MBBI, dl, TII.get(XCore::SETSP_1r)).addReg(EhStackReg);
     BuildMI(MBB, MBBI, dl, TII.get(XCore::BAU_1r)).addReg(EhHandlerReg);
     MBB.erase(MBBI);  // Erase the previous return instruction.
     return;
   }
    • XCoreFrameLowering::determineCalleeSaves (XCoreFrameLowering.cpp) 會調用 XCoreFunctionInfo::createEHSpillSlot (XCoreMachineFunctionInfo.cpp) 為例外處理使用到的暫存器，創建 spill 空間。emitPrologue/emitEpilogue 依據該位置生成 load/store 代碼。
  • Software pipelining
    • 將多個 loop iteration 排進流水線，最大化 ILP。需要考慮 data dependency (data dependency graph) 和硬件資源的限制 (resource reservation table)。
      • Swing Modulo Scheduling for GCC
      • AN IMPLEMENTATION OF SWING MODULO SCHEDULING WITH EXTENSIONS FOR SUPERBLOCKS
        • Modulo Scheduling 試圖讓多個 iteration 並行，縮小 iteration 之間的啟動 (initiation) 間距，盡可能填滿 CPU pipeline。
          • 建立 Data Dependence Graph (DDG)，藉此計算兩個連續的 iteration 啟動之間所需的 cycle，此值稱為 MII (Minimum Initiation Interval)。以 MII 作為 II (Initiation Interval)) 的初始值，試著把所有指令放進 II 區間。如果不行，II 放寬一個 cycle，重複前一個步驟。
            • MII 取 Res (Resource constrained) MII 和 Rec (Recurrence constrained) MII 的最大值。
          • 最後將原來的 loop 重構成 prologue，kernel 和 epilogue。
        • Swing Modulo Scheduling (SMS) 另外考慮到 register pressure。如果 scheduling 過於激進，並行的指令使用超過硬件所能提供的 register，spilling 會發生，抵銷 scheduling 所拿到的效能增長。將相依賴的指令盡可能排在鄰近執行，減小 register 的生命週期，增加 register 的使用率。
      • A high-level implementation of software pipelining in LLVM (Video Paper)
  • LibCall
    • RuntimeLibcalls.h
    • 4 The GCC low-level runtime library
    • 用意在於如果產生目標平台不支援的指令 (和是否開啟 O2 沒有關係)，可以調用 libgcc 的實現 5)。以 DAGTypeLegalizer::ExpandIntRes_Shift 為例 
        // 如果之前的代碼都不能處理，看是否能調用 libcall。
  if (LC != RTLIB::UNKNOWN_LIBCALL && TLI.getLibcallName(LC)) {
    SDValue Ops[2] = { N->getOperand(0), N->getOperand(1) };
    SplitInteger(TLI.makeLibCall(DAG, LC, VT, Ops, isSigned, dl).first, Lo, Hi);
    return;
  }
 
  // 如果 LC 對應的函式名為 nullptr，嘗試 ExpandShiftWithUnknownAmountBit 是否能加以處理。
  if (!ExpandShiftWithUnknownAmountBit(N, Lo, Hi))
    llvm_unreachable("Unsupported shift!");
  • MathExtras.h 提供 helper function。例如: 判斷常量的二進制是否是連續的 1-bit。
      if (countTrailingOnes(Imm) == countPopulation(Imm))
  • Peephole Optimizer
    • PeepholeOptimizer.cpp 是通用的優化，目標平台透過實現 TargetInstrInfo 的函式供其調用。
    • PPCMIPeephole.cpp 是 PowerPC 特定的優化。 PPCMIPeephole::simplifyCode() 搜尋特定的 MachineInstr 加以優化。

交叉編譯

交叉編譯有底下術語:

  • host: 運行交叉工具鏈的平台。
  • build: 編譯交叉工具鏈的平台。
  • target: 運行交叉工具鏈得到的執行檔，其運行的平台。
  • multilib: 在系統上同時安裝支援不同 ABI 的函式庫，讓交叉編譯加以鏈結。如: /lib/n32 和 /lib/n64 分別是支持 MIPS n32 和 n64 ABI 的函式庫。
  • sysroot: 交叉編譯時，從指定的根目錄搜尋所需的標頭檔或函式庫。

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

  • –target=<triple> (Triple.h)
    • triple 格式為 <arch><sub>-<vendor>-<sys>-<abi>。例如: x86_64-apple-macosx10.11.0，<arch>-<vendor>-<sys>。
    • 底下選項用來更加精確的指定目標平台:
      • -march=<arch>: 指定指令集架構版本。如: armv4t。此選項同時會設置預設的 CPU。
      • -mcpu=<cpu>: 指定 CPU。如: cortex-a8。此選項同時會設置預設的 float-abi。
      • -mfloat-abi=<abi>: 指定軟浮點或是硬浮點，以及 abi。

測試

詳細請見 LLVM Testing Infrastructure Guide。

  • FileCheck
    $ ./build.Ninja/bin/llvm-lit llvm/test/CodeGen/*
$ ./build.Ninja/bin/llvm-lit llvm/tools/clang/test/CodeGen/*
    • FileCheck，llvm-lit 這一類開發者使用的工具不會被裝在安裝目錄底下，都放在編譯目錄。

發行版測試流程請見 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。

  • git diff -U999999 master > b.patch
  • 在 Phabricator 開啟帳戶。目前以 GitHub 帳戶登入。
  • 可以選擇訂閱 llvm-commits 郵件列表。
    • 透過 Phabricator 發送的 code review，最好將 llvm-commits 加入 subscriber list。code review 的主題前面加上被修改的模塊名稱，如: [Doc]。
    • 確定登入帳戶的 email 有訂閱 llvm-commits。如果沒有的話，Phabricator 以此帳戶發送信件至 llvm-commits 會被 moderate (即受到管制，不能被馬上看到)。
    • 可以透過 Phabricator 網頁介面，或是命令行發送 patch。
    • 如果 patch 被 approved，但自己沒有 commit 權限，在 comment 上留言表示自己沒有權限，請他人幫忙 commit。

外部連結

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
登录