FPGA開発日記

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

LLVMのバックエンドを作るための第一歩 (28. SELECTノードをMYRISCVXISD::SELECT_CCに変換する)

LLVM

SELECTノードは以下の実装を用いてMYRISCVXISD::SELECT_CCに変換する。SELECTノードはカスタム実装に置き換え、(MYRISCVXISDではないデフォルトの)SELECT_CCはCombine時に生成しないようにする。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
MYRISCVXTargetLowering::MYRISCVXTargetLowering(const MYRISCVXTargetMachine &TM,
                                               const MYRISCVXSubtarget &STI)
...
  // SELECTノードはカスタム実装に置き換え
  setOperationAction(ISD::SELECT,    MVT::i32, Custom);
  // MYRISCVXISDではないデフォルトのSELECT_CCはCombine時に生成しない
  setOperationAction(ISD::SELECT_CC, MVT::i32, Expand);

そして、MYRISCVXTargetLowering::lowerOperation()でSELECTノードの処理をMYRISCVXTargetLowering::lowerSELECT()で処理するように仕向ける。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
SDValue MYRISCVXTargetLowering::
LowerOperation(SDValue Op, SelectionDAG &DAG) const
{
  switch (Op.getOpcode())
  {
    case ISD::SELECT           : return lowerSELECT(Op, DAG);
...

MYRISCVXTargetLowering::lowerSELECT()の実装を覗いてみる。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
SDValue MYRISCVXTargetLowering::
lowerSELECT(SDValue Op, SelectionDAG &DAG) const
{
  SDValue CondV = Op.getOperand(0);
  SDValue TrueV = Op.getOperand(1);
  SDValue FalseV = Op.getOperand(2);
  SDLoc DL(Op);

  // (select condv, truev, falsev)
  // -> (MYRISCVXISD::SELECT_CC condv, zero, setne, truev, falsev)
  SDValue Zero = DAG.getConstant(0, DL, MVT::i32);
  SDValue SetNE = DAG.getConstant(ISD::SETNE, DL, MVT::i32);

  SDVTList VTs = DAG.getVTList(Op.getValueType(), MVT::Glue);
  SDValue Ops[] = {CondV, Zero, SetNE, TrueV, FalseV};

  return DAG.getNode(MYRISCVXISD::SELECT_CC, DL, VTs, Ops);
}

ここでは、SELECTノードをMYRISCVXISD::SELECT_CCに置き換えるためのノードの組み立てを行っている。比較対象のオペランドOpとZeroをSETNEで比較し、比較結果によってTrueVとFalseVのどちらかを選択するというSELECT_CCを組み立てた。SELECTはMYRISCVXISD::SELECT_CCに置き換えられ、最終的に命令に変換されることになる。

MYRISCVXISD::SELECT_CCノードから命令を組み立てる

MYRISCVXISD::SELECT_CCノードは以下のように定義されている。MYRISCVXSelectCCというノードを作り、その制約条件をSDT_MYRISCVXSelectCCに記述する。この制約はISD::SelectCCと同様だ。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
# MYRISCVX::SELECT_CCの条件。出力ノードは1つ、入力ノードは5つ。
def SDT_MYRISCVXSelectCC   : SDTypeProfile<1, 5, [SDTCisSameAs<1, 2>,
                                               SDTCisSameAs<0, 4>,
                                               SDTCisSameAs<4, 5>]>;
# MYRISCVX::SELECT_CCを定義する。SDT_MYRISCVXSelectCCのノード制約を使用する。
def MYRISCVXSelectCC : SDNode<"MYRISCVXISD::SELECT_CC", SDT_MYRISCVXSelectCC,
                      [SDNPInGlue]>;
let usesCustomInserter = 1 in
class SelectCC_rrirr<RegisterClass RC, RegisterClass cmpty>
    : MYRISCVXPseudo<(outs RC:$dst),
             (ins cmpty:$lhs, cmpty:$rhs, simm12:$imm,
              RC:$truev, RC:$falsev),
              "",
             [(set RC:$dst,
               (MYRISCVXSelectCC cmpty:$lhs,
                         cmpty:$rhs,
                         (i32 imm:$imm),
                         RC:$truev,
                         RC:$falsev))]>;

def Select_GPR_Using_CC_GPR : SelectCC_rrirr<GPR, GPR>;

このMYRISCVXSelectCCを用いてパタンを作成する。比較対象のcmpty:$lhs, cmpty:$rhsに対して比較結果がTrueの場合にはRC:$truevが、不成立の場合にはRC:$falsevが選択され出力RC:$dstが返されるようにしている。ただし、このままではどのような比較演算が実行されるのかが分からない。これは、実際にCコード側で組み立てていくことになる。

このとき、このusesCustomInserterがとても大切になる。これは、この変換後に作られたMYRISCVXSelectCCのIRを、手動で変換する処理が入る、という印になる。逆に言うと、このusesCustomInserterを置いておかないと、後続の命令変換の最中にSELECT_CCを変換することができないとしてエラーが出力されてしまうのだ。

以下に、MYRISCVXISD::SELECT_CCを具体的な命令に置き換える実装を示す。

3項演算子を実現するので、以下のようなフローになる。

  1. 比較演算が成立した場合の値を、Destination Registerに格納しておく。
  2. 比較演算を実行する。
  3. 比較結果がFalseであれば、Destination RegisterにFalse側の値を格納する。

このため、大きく分けて以下のマシンコードブロックを作成する。

  • HeadMBB : 先頭のブロック(与えられたMachineBasicBlock *BBに相当)
  • TailMBB : 3項演算子ブロックの末尾。TrueでもFalseでも最終的にここに飛んでくる。

  • IfFalseMBB : 比較結果がFalseである場合飛んでくる。False時の値を設定する。

  • llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp

MachineBasicBlock *
MYRISCVXTargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
                                                    MachineBasicBlock *BB) const {

  const TargetInstrInfo &TII = *BB->getParent()->getSubtarget().getInstrInfo();
  const BasicBlock *LLVM_BB = BB->getBasicBlock();
  DebugLoc DL = MI.getDebugLoc();
  MachineFunction::iterator I = ++BB->getIterator();

  MachineBasicBlock *HeadMBB = BB;
  MachineFunction *F = BB->getParent();
  MachineBasicBlock *TailMBB = F->CreateMachineBasicBlock(LLVM_BB);
  MachineBasicBlock *IfFalseMBB = F->CreateMachineBasicBlock(LLVM_BB);

  F->insert(I, IfFalseMBB);
  F->insert(I, TailMBB);
  // Move all remaining instructions to TailMBB.
  TailMBB->splice(TailMBB->begin(), HeadMBB,
                  std::next(MachineBasicBlock::iterator(MI)), HeadMBB->end());
  // Update machine-CFG edges by transferring all successors of the current
  // block to the new block which will contain the Phi node for the select.
  TailMBB->transferSuccessorsAndUpdatePHIs(HeadMBB);
  // Set the successors for HeadMBB.
  HeadMBB->addSuccessor(IfFalseMBB);
  HeadMBB->addSuccessor(TailMBB);

  // Insert appropriate branch.
  unsigned LHS = MI.getOperand(1).getReg();
  unsigned RHS = MI.getOperand(2).getReg();
  auto CC = static_cast<ISD::CondCode>(MI.getOperand(3).getImm());
  unsigned Opcode = getBranchOpcodeForIntCondCode(CC);

  BuildMI(HeadMBB, DL, TII.get(Opcode))
    .addReg(LHS)
    .addReg(RHS)
    .addMBB(TailMBB);

  // IfFalseMBB just falls through to TailMBB.
  IfFalseMBB->addSuccessor(TailMBB);

  // %Result = phi [ %TrueValue, HeadMBB ], [ %FalseValue, IfFalseMBB ]
  BuildMI(*TailMBB, TailMBB->begin(), DL, TII.get(MYRISCVX::PHI),
          MI.getOperand(0).getReg())
      .addReg(MI.getOperand(4).getReg())
      .addMBB(HeadMBB)
      .addReg(MI.getOperand(5).getReg())
      .addMBB(IfFalseMBB);

  MI.eraseFromParent(); // The pseudo instruction is gone now.
  return TailMBB;
}

EmitInstrWithCustomInserter()の中で比較とその結果に基づく選択の命令を抽出する。まず左右の条件どうしを比較する命令を作成する。

  BuildMI(HeadMBB, DL, TII.get(Opcode))
    .addReg(LHS)
    .addReg(RHS)
    .addMBB(TailMBB);

OpCodeはgetBranchOpcodeForIntCondCode()で選択する。比較演算によって条件分岐命令を選択しているが、つまりBEQ LHS, RHS, TailMBBという命令を組み立て、LHSとRHSの比較を行っている。

次に、PHIノードを組み立てる。PHIノードはざっくりと説明すると、「飛んできたブロックによって選択する値を選ぶ」というノードだ。上記の比較命令により、LHSとRHSの比較結果がTrueである場合TailMBBに飛ぶ訳だが、そうでない場合は、HeadMBBからIfFalseMBBに飛ぶわけだので、

  HeadMBB->addSuccessor(IfFalseMBB);

IfFalseMBBから来た場合はオペランド5(False時の値)、そうでなくHeadMBBから来た場合はオペランド4(True時の値)を選択するようにPHIノードを構築している。これは最終的に分岐命令に分解され、命令が出力される。

  BuildMI(*TailMBB, TailMBB->begin(), DL, TII.get(MYRISCVX::PHI),
          MI.getOperand(0).getReg())
      .addReg(MI.getOperand(4).getReg())
      .addMBB(HeadMBB)
      .addReg(MI.getOperand(5).getReg())
      .addMBB(IfFalseMBB);
f:id:msyksphinz:20190622124712p:plain
MYRISCVXISD::SELECTを変換したときのDAGグラフ

再ビルドを行い、上記のサンプルプログラムを動かした時の出力結果は以下のようになる。

# %bb.0:                                # %entry
        addi    x2, x2, -8
        addi    x10, zero, 1
        sb      x10, 4(x2)
        addi    x12, zero, 0
        sw      x12, 0(x2)
        lbu     x10, 4(x2)
        andi    x13, x10, 1
        addi    x11, zero, 20
        addi    x10, zero, 10
        bne     x13, x12, $BB0_2
# %bb.1:                                # %entry
        addi    x10, x11, 0
$BB0_2:                                 # %entry
        sw      x10, 0(x2)
        lw      x10, 0(x2)
        addi    x2, x2, 8
        ret     x1