FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

LLVMのバックエンドを作るための第一歩 (26. 制御構文の追加)

LLVM
f:id:msyksphinz:20190425001356p:plain

制御フロー生成

いよいよLLVMバックエンドの醍醐味、制御構文の生成に入る。if文やfor文などの制御構文を生成できるようにしたい。

まずは、以下のような簡単なCプログラムをClangに入力し、LLVM IRを生成してみる。どのような制御IRが必要になるのかを確認する。

int test_ifctrl()
{
  unsigned int a = 0;
  
  if (a == 0) {
    a++; // a = 1
  }
  
  return a;
}

./bin/clang --target=mips-unknown-elf ../lbdex/input/ch6_1.cpp -c -emit-llvm
./bin/llvm-dis ch8_1_1.bc -o -

; Function Attrs: noinline nounwind optnone
define dso_local i32 @_Z11test_ifctrlv() #0 {
entry:
  %a = alloca i32, align 4
  store i32 0, i32* %a, align 4
  %0 = load i32, i32* %a, align 4
  %cmp = icmp eq i32 %0, 0
  br i1 %cmp, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  %1 = load i32, i32* %a, align 4
  %inc = add i32 %1, 1
  store i32 %inc, i32* %a, align 4
  br label %if.end

if.end:                                           ; preds = %if.then, %entry
  %2 = load i32, i32* %a, align 4
  ret i32 %2
}

まずは、無条件でジャンプする命令から追加する。これはif.then節が有効である場合、最後にbr label %if.endによりif.endによりジャンプする場合に必要な命令だ(実際には不要なジャンプだが、これはPassを追加することで後で削除する)。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
// Unconditional Branch
class JumpOffset<bits<7> opcode, string instr_asm, RegisterClass RC>:
  MYRISCVX_J<opcode, (outs RC:$rd), (ins brtarget20:$addr),
  !strconcat(instr_asm, "\t$rd, $addr"), [], IIAlu> {
    let isBranch = 1;
    let isTerminator = 1;
    let isBarrier = 1;
    let hasDelaySlot = 0;
}


class JumpOffsetX0<bits<7> opcode, string instr_asm>:
  JumpOffset<opcode, instr_asm, GPR> {
    let rd = 0;
}
// JAL
def brtarget20    : Operand<OtherVT> {
  let EncoderMethod = "getBranch20TargetOpValue";
  let OperandType   = "OPERAND_PCREL";
  let DecoderMethod = "DecodeBranch20Target";
}

JumpOffsetX0は即値のジャンプで、JumpOffsetをベースにしている。JumpOffsetはRISC-VのJ形式のフォーマットで、通常は書き込み先の汎用レジスタを取るのだが、J命令の場合は$rd=0となるので、そのためにJumpOffsetX0を定義している。これを使って、J命令を定義する。

def JAL : JumpOffset<0b1101111, "jal", GPR>;
def J   : JumpOffsetX0<0b1101111, "j">;

これを用いて、ブロックへのジャンプのためのパタンを作成する。

def : Pat<(br bb:$simm20), (J bb:$simm20)>;

brつまり分岐のパタンを、J命令に割り当てる。brは以下のように定義されている。

  • llvm-myriscvx/include/llvm/Target/TargetSelectionDAG.td
def br         : SDNode<"ISD::BR"         , SDTBr,     [SDNPHasChain]>;

次に、比較命令とジャンプを実装する。比較命令は、RISC-Vでは以下の命令を定義する。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
// Branch instructions with 2 register operands.
class CondBranch12<bits<7> opcode, bits<3> funct3,
                string instr_asm,
                PatFrag cond_op, RegisterClass RC> :
  MYRISCVX_B<opcode, funct3, (outs), (ins RC:$rs1, RC:$rs2, brtarget12:$imm12),
  !strconcat(instr_asm, "\t$rs1, $rs2, $imm12"),
  [], IIAlu> {
    let isBranch = 1;
    let isTerminator = 1;
}
// BEQ, BNE
def brtarget12    : Operand<OtherVT> {
  let EncoderMethod = "getBranch12TargetOpValue";
  let OperandType   = "OPERAND_PCREL";
  let DecoderMethod = "DecodeBranch12Target";
}
def BEQ     : CondBranch12<0b1100011, 0b000, "beq" , seteq,  GPR>;
def BNE     : CondBranch12<0b1100011, 0b001, "bne" , setne,  GPR>;
def BLT     : CondBranch12<0b1100011, 0b100, "blt" , setlt,  GPR>;
def BGE     : CondBranch12<0b1100011, 0b101, "bge" , setge,  GPR>;
def BLTU    : CondBranch12<0b1100011, 0b110, "bltu", setult, GPR>;
def BGEU    : CondBranch12<0b1100011, 0b111, "bgeu", setuge, GPR>;

RISC-Vではレジスタ間条件分岐はB命令形式で定義される。B命令形式を使用したCondBranch12クラスを作成し、それをベースにして命令を定義する。

JAL命令と条件分岐命令では、それぞれ20ビット、12ビットのオフセット値を使用する。これらのオフセットを扱うためのノードとしてbrtarget20, brtarget12を定義した。これらのオペランドを表示するためのメソッドとしてgetBranch20TargetOpValueおよびgetBranch12TargetOpValueを定義する。

  • llvm-myriscvx/lib/Target/MYRISCVX/MCTargetDesc/MYRISCVXMCCodeEmitter.cpp
/// getBranch12TargetOpValue - Return binary encoding of the branch
/// target operand. If the machine operand requires relocation,
/// record the relocation and return zero.
unsigned MYRISCVXMCCodeEmitter::
getBranch12TargetOpValue(const MCInst &MI, unsigned OpNo,
                         SmallVectorImpl<MCFixup> &Fixups,
                         const MCSubtargetInfo &STI) const {
  const MCOperand &MO = MI.getOperand(OpNo);

  if (MO.isImm()) {
    return static_cast<unsigned>(MO.getImm());
  }
  llvm_unreachable("getBranch12TargetOpValue should be imm.");
}


/// getBranch20TargetOpValue - Return binary encoding of the branch
/// target operand. If the machine operand requires relocation,
/// record the relocation and return zero.
unsigned MYRISCVXMCCodeEmitter::
getBranch20TargetOpValue(const MCInst &MI, unsigned OpNo,
                         SmallVectorImpl<MCFixup> &Fixups,
                         const MCSubtargetInfo &STI) const {
  const MCOperand &MO = MI.getOperand(OpNo);

  if (MO.isImm()) {
    return static_cast<unsigned>(MO.getImm());
  }
  llvm_unreachable("getBranch20TargetOpValue should be imm.");
}

このCondBranch12クラスは、パラメータとして$rs1, $rs2, $imm12を取りる。これらの命令を使って条件分岐のパタンを作り上げていく。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
// brcond for slt instruction
multiclass BrcondPatsSlt<RegisterClass RC, Instruction BEQOp, Instruction BNEOp,
                      Instruction SLTOp, Instruction SLTuOp, Instruction SLTiOp,
                      Instruction SLTiuOp, Register ZEROReg> {
def : Pat<(brcond (i32 (setne RC:$lhs, 0)), bb:$dst),
              (BNEOp RC:$lhs, ZEROReg, bb:$dst)>;
def : Pat<(brcond (i32 (seteq RC:$lhs, 0)), bb:$dst),
              (BEQOp RC:$lhs, ZEROReg, bb:$dst)>;

def : Pat<(brcond (i32 (seteq RC:$lhs, RC:$rhs)), bb:$dst),
              (BEQOp RC:$lhs, RC:$rhs, bb:$dst)>;
def : Pat<(brcond (i32 (setueq RC:$lhs, RC:$rhs)), bb:$dst),
              (BEQOp RC:$lhs, RC:$rhs, bb:$dst)>;
def : Pat<(brcond (i32 (setne RC:$lhs, RC:$rhs)), bb:$dst),
              (BNEOp RC:$lhs, RC:$rhs, bb:$dst)>;
def : Pat<(brcond (i32 (setune RC:$lhs, RC:$rhs)), bb:$dst),
              (BNEOp RC:$lhs, RC:$rhs, bb:$dst)>;
def : Pat<(brcond (i32 (setlt RC:$lhs, RC:$rhs)), bb:$dst),
              (BNE (SLTOp RC:$lhs, RC:$rhs), ZERO, bb:$dst)>;
def : Pat<(brcond (i32 (setult RC:$lhs, RC:$rhs)), bb:$dst),
              (BNE (SLTuOp RC:$lhs, RC:$rhs), ZERO, bb:$dst)>;
def : Pat<(brcond (i32 (setgt RC:$lhs, RC:$rhs)), bb:$dst),
              (BNE (SLTOp RC:$rhs, RC:$lhs), ZERO, bb:$dst)>;
def : Pat<(brcond (i32 (setugt RC:$lhs, RC:$rhs)), bb:$dst),
              (BNE (SLTuOp RC:$rhs, RC:$lhs), ZERO, bb:$dst)>;
def : Pat<(brcond (i32 (setle RC:$lhs, RC:$rhs)), bb:$dst),
              (BEQ (SLTOp RC:$rhs, RC:$lhs), ZERO, bb:$dst)>;
def : Pat<(brcond (i32 (setule RC:$lhs, RC:$rhs)), bb:$dst),
              (BEQ (SLTuOp RC:$rhs, RC:$lhs), ZERO, bb:$dst)>;
def : Pat<(brcond (i32 (setge RC:$lhs, RC:$rhs)), bb:$dst),
              (BEQ (SLTOp RC:$lhs, RC:$rhs), ZERO, bb:$dst)>;
def : Pat<(brcond (i32 (setuge RC:$lhs, RC:$rhs)), bb:$dst),
              (BEQ (SLTuOp RC:$lhs, RC:$rhs), ZERO, bb:$dst)>;
def : Pat<(brcond RC:$cond, bb:$dst),
              (BNEOp RC:$cond, ZEROReg, bb:$dst)>;
}

defm : BrcondPatsSlt<GPR, BEQ, BNE, SLT, SLTU, SLTI, SLTIU, ZERO>;

符号付整数比較、符号なし整数比較について、==, !=, <, <=, >, >=について定義している。これれらのパタンにより、比較演算および条件分岐が実装される。

./bin/llc -march=myriscvx32 -mcpu=simple32 -relocation-model=pic -filetype=asm ch8_1_1.bc -o -
_Z11test_ifctrlv:
        .frame  $x8,8,$x1
        .mask   0x00000000,0
        .set    noreorder
        .set    nomacro
# %bb.0:                                # %entry
        addi    x2, x2, -8
        addi    x10, zero, 0
        sw      x10, 4(x2)
        lw      x10, 4(x2)
        bne     x10, zero, $BB0_2
        j       x10, $BB0_1
$BB0_1:                                 # %if.then
        lw      x10, 4(x2)
        addi    x10, x10, 1
        sw      x10, 4(x2)
        j       x10, $BB0_2
$BB0_2:                                 # %if.end
        lw      x10, 4(x2)
        addi    x2, x2, 8
        ret     x1

正しく生成できていることが分かる。x10にロードした値をbne命令によりゼロと比較し、ゼロでなければ関数から出るために$BB0_2までジャンプする。そうでなければ$BB0_1にジャンプし、1のインクリメントを行ってメモリへストア、そして$BB0_2にジャンプする。命令として効率はさておき、正しい動きをしていることが分かる。

f:id:msyksphinz:20190619005150p:plain