"Creating an LLVM Backend for the Cpu0 Architecture"をやってみる(5. Cpu0 Architecture and LLVM Structure 続き)

LLVMにCpu0アーキテクチャを追加するチュートリアル。ちょっと飛ばしすぎたので一度立ち戻って、LLVMのアーキテクチャについてもう一度勉強し直す。

LLVMにバックエンドを追加するチュートリアル の Cpu0 architecture and LLVM structure をもう一度読み直してまとめていく。

最初の方は一生懸命自分の言葉でまとめていたけど、途中からほぼ直訳みたいになってきた。纏めた分を掲載しておく。今回は以下の項目。 前回のものはこちらから。

• LLVM Structure
  • DAG (Directed Acyclic Graph)
  • Instruction Selection
  • Caller and callee saved registers
  • Live in and live out register

---

Cpu0 architecture and LLVM structure

DAG (Directed Acyclic Graph)

局所最適化の様々な重要なテクニックを学ぶにあたり、まずは基本ブロックをDAG[15]に変換する技術から始めよう。例えば、基本ブロックとそれに対応するDAGを図9に示す。

もしb基本ブロックの外で消滅するならば、「共通式の削除」により以下の表のように変換できる。

Replace node b with node d	Replace b0, c0, d0 with b, c, d
a = b0 + c0	a = b + c
d = a – d0	d = a – d
c = d + c	c = d + c

bを削除し、DAGを下から上に(バイナリ木を深さ優先探索する)に探索すると、上記の表の1列目が得られる。

「共通式の削除」はIRとマシンコードにも適用できる。

DAGは、オペコードがノードでオペランド(レジスタ・定数・即値・オフセットなど)が葉である木構造のようなものである。ツリー内で、Prefixオーダのリストとしても表現することができる。例えば、 (+ b, c), (+ b, 1)はIRDAGの表記である。

DAGの最適化に加えて、Compiler Book[15]の8.5.5ではレジスタの「削除」についても触れられている。この再帰的はLLVMでも実装されている。

命令の選択

バックエンドの主たる機能は、図10.のように命令選択のステージにおいてIRコードをマシンコードに変換することである。

マシン命令の選択では、IRとマシン命令をDAGで表現するのが最適な選択である。簡単化のためには、図11ではレジスタの葉はスキップしている。rj+rkはIR DAG表記である(シンボルであり、LLVMのSSA形式ではない)。ADDはマシン命令である。

IR DAGとマシン命令のDAGはどちらもリスト形式として表現される。例えば(+ ri, rjj)と(- ri, 1)はIRのDAGのリストである; 一方で(ADD ri, rj)と(SUB ri, 1)はマシン命令のDAGである。

では、Cpu0InstrInfo.tdに定義されているADDiu命令をチェックしてみよう。

• lbdex/chapters/Chapter2/Cpu0InstrFormats.td

//===----------------------------------------------------------------------===//
// Format L instruction class in Cpu0 : <|opcode|ra|rb|cx|>
//===----------------------------------------------------------------------===//

class FL<bits<8> op, dag outs, dag ins, string asmstr, list<dag> pattern,
         InstrItinClass itin>: Cpu0Inst<outs, ins, asmstr, pattern, itin, FrmL>
{
  bits<4>  ra;
  bits<4>  rb;
  bits<16> imm16;

  let Opcode = op;

  let Inst{23-20} = ra;
  let Inst{19-16} = rb;
  let Inst{15-0}  = imm16;
}

• lbdex/chapters/Chapter2/Cpu0InstrInfo.td

// Node immediate fits as 16-bit sign extended on target immediate.
// e.g. addi, andi
def immSExt16  : PatLeaf<(imm), [{ return isInt<16>(N->getSExtValue()); }]>;

// Arithmetic and logical instructions with 2 register operands.
class ArithLogicI<bits<8> op, string instr_asm, SDNode OpNode,
                  Operand Od, PatLeaf imm_type, RegisterClass RC> :
  FL<op, (outs GPROut:$ra), (ins RC:$rb, Od:$imm16),
     !strconcat(instr_asm, "\t$ra, $rb, $imm16"),
     [(set GPROut:$ra, (OpNode RC:$rb, imm_type:$imm16))], IIAlu> {
  let isReMaterializable = 1;
}

// IR "add" defined in include/llvm/Target/TargetSelectionDAG.td, line 315 (def add).
def ADDiu   : ArithLogicI<0x09, "addiu", add, simm16, immSExt16, CPURegs>;

図12はIRノードのaddと、命令ノードのADDiuがどのようにしてパタンマッチするのかを示している。どちらもCpu0InstrInfo.tdに記述されている。この例では、IRノード"add %a, 5"は、IRパタン[(set RC:$ra, (OpNode RC:$rb, imm_type:$imm16))]により%aがレジスタ割り当てステージによりレジスタr1に割り当てられ、2番目のオペランドが「符号付き即値」として、"%a, 5"としてマッチして、"addiu r1, 5"に変換される。パタンマッチに加え、.tdファイルは"addiu"のアセンブリ文字列とオペコードの0x09を含んでいる。この情報により、LLVM TableGenはアセンブリコードとバイナリを自動的に生成する(バイナリ命令はobjファイルとしてELFフォーマットで生成される。これは以降の章で説明する)。どうようんいマシン命令のDAGノードのLDとSTはIR DAGノードのloadとstoreに変換される。

図12の$rbは仮想レジスタ名であり、マシンレジスタの名前ではないことに注意。

DAG命令生成では、説明したように葉のノードはデータノードでなければならない。ADDiuはLタイプの命令であり、最後のオペランドは16ビットの幅に収まっていなければならない。したがって、Cpu0InstrInfo.tdではimmSExt16型のPatLeafを定義し、LLVMシステムにPatLeafのサイズを知らせるようにしている。もしimm16の値が範囲を超えているならば、"isInt<16>(N->getSExtValue())"がfalseを返し、ADDiu命令は、命令生成のステージでは選択されない。

いくつかのCPU/FPU(Floating Point Processor)はMultiply-and-Add, fmaddの浮動小数点命令を持っている。これはDAGリストで(fadd(fmul ra, rc), rb)と表現される。この実装のため、fmaddのDAGパタンはtdで以下のようにアサインすることができる。

def FMADDS : AForm_1<59, 29,
          (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),
          "fmadds $FRT, $FRA, $FRC, $FRB",
          [(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),
                       F4RC:$FRB))]>;

ADDiuと同様に、[(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC), F4RC:$FRB))]はfmulとfaddを含むパタンマッチである。

以下の基本ブロックのIR気泡とLLVM SSA IRコードでは、

d = a * c
e = d + b
...
%d = fmul %a, %c
%e = fadd %d, %b
...

命令選択処理では、もしtdファイル内でFMADDSがFMULとFADDよりも先に登場するならば、 2つのIR DAGノード(fmul %a, %c)と(fadd %d, %b)を、2つのマシン命令ノードfmulとfaddとして変換するのではなく1つのマシン命令DAGノード(fmadd %a, %c, %b)にマージする。

%e = fmadd %a, %c, %b
...

IR記法の表現はLLVM SSA IR形式を読むよりも簡単である。したがってこの記法は本書で頻繁に登場する。

以下の基本ブロックのコードでは、

a = b + c   // IR形式での記法
d = a – d
%e = fmadd %a, %c, %b // LLVM SSA IRの記法

We can apply Fig. 7 Instruction Tree Patterns to get the following machine code,

図7. の命令ツリーパタンを適用して、以下のマシンコードを得る。

load  rb, M(sp+8); // bがsp+8に割り当てられているとする。spはスタックポインタレジスタである
load  rc, M(sp+16);
add ra, rb, rc;
load  rd, M(sp+24);
sub rd, ra, rd;
fmadd re, ra, rc, rb;

呼び出し側保存レジスタと呼び出され側保存レジスタ

• lbdex/input/ch9_caller_callee_save_registers.cpp

extern int add1(int x);

int caller()
{ 
  int t1 = 3;
  int result = add1(t1);  
  result = result - t1;
  
  return result;
}

上記のソースコードに対してMipsのバックエンドを実行すると、以下の結果を得る。

JonathantekiiMac:input Jonathan$ ~/llvm/release/cmake_debug_build/Debug/bin/llc
-O0 -march=mips -relocation-model=static -filetype=asm
ch9_caller_callee_save_registers.bc -o -
      .text
      .abicalls
      .option pic0
      .section        .mdebug.abi32,"",@progbits
      .nan    legacy
      .file   "ch9_caller_callee_save_registers.bc"
      .text
      .globl  _Z6callerv
      .align  2
      .type   _Z6callerv,@function
      .set    nomicromips
      .set    nomips16
      .ent    _Z6callerv
_Z6callerv:                             # @_Z6callerv
      .cfi_startproc
      .frame  $fp,32,$ra
      .mask   0xc0000000,-4
      .fmask  0x00000000,0
      .set    noreorder
      .set    nomacro
      .set    noat
# BB#0:
      addiu   $sp, $sp, -32
$tmp0:
      .cfi_def_cfa_offset 32
      sw      $ra, 28($sp)            # 4-byte Folded Spill
      sw      $fp, 24($sp)            # 4-byte Folded Spill
$tmp1:
      .cfi_offset 31, -4
$tmp2:
      .cfi_offset 30, -8
      move     $fp, $sp
$tmp3:
      .cfi_def_cfa_register 30
      addiu   $1, $zero, 3
      sw      $1, 20($fp)   # store t1 to 20($fp)
      move     $4, $1
      jal     _Z4add1i
      nop
      sw      $2, 16($fp)   # $2 : the return vaule for fuction add1()
      lw      $1, 20($fp)   # load t1 from 20($fp)
      subu    $1, $2, $1
      sw      $1, 16($fp)
      move     $2, $1     # move result to return register $2
      move     $sp, $fp
      lw      $fp, 24($sp)            # 4-byte Folded Reload
      lw      $ra, 28($sp)            # 4-byte Folded Reload
      addiu   $sp, $sp, 32
      jr      $ra
      nop
      .set    at
      .set    macro
      .set    reorder
      .end    _Z6callerv
$func_end0:
      .size   _Z6callerv, ($func_end0)-_Z6callerv
      .cfi_endproc

上記のアセンブリコードでは、Mipsはt1変数をレジスタ$1に割り当てている。$1は呼び出し側が保存するレジスタなので、$$1をスピルする必要はない。一方で$raは呼び出され側が保存するレジスタなので、アセンブリ出力においてスピルが行われている。$raはjalで使用するため、保存する必要があるのだ。Cpu0の$lrはMipsの$raレジスタと同様である。従ってCpu0SEFrameLowering.cpp内のdetermineCalleeSaves()内においてsetAliasRegs(MF, SavedRegs, Cpu0::LR)を呼び出す必要がある。

Live inレジスタとlive out レジスタ

上記のセクションで、$raは呼び出し側によりリターンアドレスが決まるため、"live in"レジスタである。$2は関数のreturn値がこのレジスタに保存されており、呼び出し側がこのレジスタを直接読むことによって結果を得られるので、"live out"レジスタである。"live in"と"live out"レジスタをマークすることによって、バックエンドはLLVMのミドル例や情報として不必要な変数アクセスを行う命令を削除することができる。もちろん、これまでの章で説明したように、LLVMはDAGの解析を行ってこれらの不要な命令を削除する。C言語は異なる関数を別々にコンパイルすることをサポートしているため、"live in"と"live out"の情報がバックエンドから提供されると、LLVMは解析する機会を増やすことができる。LLVMはaddLiveIn()関数により"live in"なレジスタをマークすることができるが、addLiveOut()関数は提供されていない。その代わりに"live out"のレジスタは、MipsのバックエンドはDAG=DAG.getCopyToReg(..., $2, ...)によりマークし、DAGを返す。これにより関数を抜けた後にすべてのローカル変数が存在しなくなるわけではない。