オリジナルLLVMバックエンド実装をまとめる(14. 条件分岐命令の生成)

制御フロー生成

いよいよLLVMバックエンドの醍醐味、制御構文の生成に入る。

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

• if_ctrl.cpp

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

./bin/clang --target=riscv32-unknown-elf if_ctrl.cpp -c -emit-llvm
./bin/llvm-dis if_ctrl.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を追加することで後で削除する)。

commit:3cda3e3d750 Implement Jump and Branch instructions

• llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td

// Jump and Link (Call)
let isCall = 1 in
class JumpLink<bits<7> opcode, string opstr, DAGOperand opnd> :
  MYRISCVX_J<opcode, (outs GPR:$rd), (ins opnd:$imm20), !strconcat(opstr, "\t$rd, $imm20"),
                 [], IIAlu> {
  let DecoderMethod = "DecodeJumpTarget";
}

// JAL
def brtarget20    : Operand<OtherVT> {
  let EncoderMethod = "getBranch20TargetOpValue";
  let OperandType   = "OPERAND_PCREL";
  let DecoderMethod = "DecodeBranch20Target";
}

• llvm-myriscvx80/lib/Target/MYRISCVX/MCTargetDesc/MYRISCVXMCCodeEmitter.cpp

/// 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("getBranch12TargetOpValue should be imm.");
}

JumpLinkは即値のジャンプで、書き込みレジスタrdと、ジャンプ先のオペランド$immを取ることができる。 RISC-VのJ形式のフォーマットで、通常は書き込み先の汎用レジスタを取るのだが、J命令の場合は書き込みレジスタをZEROに設定する。 つまり、エイリアスとして、jal(書き込みレジスタ省略版)とj(書き込みレジスタ省略かつZERO)を作成する。

def JAL : JumpLink<0b1101111, "jal", brtarget20>;
def : InstAlias<"j $offset",   (JAL  ZERO, brtarget20:$offset)>;
def : InstAlias<"jal $offset", (JAL  RA,   brtarget20:$offset)>;

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

let isBarrier = 1, isBranch = 1, isTerminator = 1 in
  def PseudoBR : MYRISCVXPseudo<(outs), (ins brtarget20:$simm20), "", [(br bb:$simm20)]>,
                 PseudoInstExpansion<(JAL ZERO, brtarget20:$simm20)>;

Pseudo命令というものを使用した。これは疑似命令を使用してその命令を展開する。 このパタン(br bb:$simm20)が現れると、この疑似命令を(JAL ZERO, brtarget20:$simm20)に展開する。

JumpLinkとJAL命令の実装

このPseudoInstExpansionで定義したパタンは、コンパイル時にMYRISCVXGenMCPseudoLowering.incに生成パタンが登録される。

• build-myriscvx80/lib/Target/MYRISCVX/MYRISCVXGenMCPseudoLowering.inc

bool MYRISCVXAsmPrinter::
emitPseudoExpansionLowering(MCStreamer &OutStreamer,
                            const MachineInstr *MI) {
  switch (MI->getOpcode()) {
    default: return false;
    case MYRISCVX::PseudoBR: {
      MCInst TmpInst;
      MCOperand MCOp;
      TmpInst.setOpcode(MYRISCVX::JAL);
      // Operand: rd
      TmpInst.addOperand(MCOperand::createReg(MYRISCVX::ZERO));
      // Operand: imm20
      lowerOperand(MI->getOperand(0), MCOp);
      TmpInst.addOperand(MCOp);
      EmitToStreamer(OutStreamer, TmpInst);
      break;
    }
  }
  return true;
}

つまりPseudoBRのノードが来たときは、JAL ZERO ジャンプ先オフセットに置き換える訳だ。 このemitPseudoExpansionLowering()は、MYRISCVXAsmPrinter.cppのMYRISCVXAsmPrinter::EmitInstruction()内に追記し、命令を生成する前に疑似命令を取り除くために使用する。

• llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXAsmPrinter.cpp

bool MYRISCVXAsmPrinter::lowerOperand(const MachineOperand &MO, MCOperand &MCOp) {
  MCOp = MCInstLowering.LowerOperand(MO);
  return MCOp.isValid();
}

// Simple pseudo-instructions have their lowering (with expansion to real
// instructions) auto-generated.
#include "MYRISCVXGenMCPseudoLowering.inc"

//@EmitInstruction {
//- EmitInstruction() must exists or will have run time error.
void MYRISCVXAsmPrinter::EmitInstruction(const MachineInstr *MI) {
  // Do any auto-generated pseudo lowerings.
  if (emitPseudoExpansionLowering(*OutStreamer, MI))
    return;
...