FPGA開発日記

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

オリジナルLLVMバックエンド実装をまとめる(14. 分岐の際に発生する不要なジャンプを削除するPassの追加)

前回の制御構文を追加した際に、不要なジャンプ命令が発生しているのが気になった。例えば、LLVM IRをダンプし時に以下のようなIRが出力されたはずだ。 この時、br label %if.endはすぐ後ろの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
}
f:id:msyksphinz:20191004000339p:plain
DelJmp Passにより削除する命令のパタン

最適化のPassを追加する

ここで最適化のPassを追加するのだが、マシンコードが生成される前に最適化のPassを追加する。この場合、TargetPassConfig::addPreEmitPass()を通じてPassを追加する。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXTargetMachine.cpp
//@MYRISCVXPassConfig {
/// MYRISCVX Code Generator Pass Configuration Options.
class MYRISCVXPassConfig : public TargetPassConfig {
 public:
...
   void addPreEmitPass() override;
...
void MYRISCVXPassConfig::addPreEmitPass() {
  MYRISCVXTargetMachine &TM = getMYRISCVXTargetMachine();
  addPass (createMYRISCVXDelJmpPass(TM));
  return;
}

createMYRISCVXDelJmpPassというPassを追加した。このPassはMYRISCVXDelUselessJMP.cppで追加する。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXDelUselessJMP.cpp
#define DEBUG_TYPE "del-jmp"

STATISTIC(NumDelJmp, "Number of useless jmp deleted");

static cl::opt<bool> EnableDelJmp(
    "enable-MYRISCVX-del-useless-jmp",
    cl::init(true),
    cl::desc("Delete useless jmp instructions: jmp 0."),
    cl::Hidden);

Passの定義を行う。このPassはDelJmpというもので、デフォルトで有効だ。-enable-MYRISCVX-del-useless-jmpオプションで有効無効を制御することができる。 例えば、-enable-MYRISCVX-del-useless-jmp=falseとすることでこのPassを無効化することができる。

DelJmpクラスを定義する。このクラスは、MachineFunctionPassクラスから派生している。MachineFunctionPassクラスに記述したPassは、runOnMachineFunction()関数を呼び出すことにより実行される。

virtual bool runOnMachineFunction(MachineFunction &MF) = 0;

では、DelJmpクラスのrunOnMachineFunction()関数を実装してみる。

  bool runOnMachineFunction(MachineFunction &F) {
    bool Changed = false;
    if (EnableDelJmp) {
      MachineFunction::iterator FJ = F.begin();
      if (FJ != F.end())
        FJ++;
      if (FJ == F.end())
        return Changed;
      for (MachineFunction::iterator FI = F.begin(), FE = F.end();
           FJ != FE; ++FI, ++FJ)
        // In STL style, F.end() is the dummy BasicBlock() like '\0' in
        //  C string.
        // FJ is the next BasicBlock of FI; When FI range from F.begin() to
        //  the PreviousBasicBlock of F.end() call runOnMachineBasicBlock().
        Changed |= runOnMachineBasicBlock(*FI, *FJ);
    }
    return Changed;
  }

このコードでは、マシンコードからBasicBlockをひとつづつ取り出してPassを適用するという形をとっている。 FIイテレータがターゲットとなるBasic Blockを示しており、一つずらしたFJイテレータFIの次のブロックを示している。つまり、

  • FIイテレータの一番最後のコードがジャンプ命令であり、
  • ジャンプ先がFJの先頭であれば、FIの最後のジャンプ命令を削除しても良い

ということになり、この処理をrunOnMachineBasicBlock()に記述している。最終的にコードの変更を行った場合は、Changed変数をTrueに設定して戻る。

bool DelJmp::
runOnMachineBasicBlock(MachineBasicBlock &MBB, MachineBasicBlock &MBBN) {
  bool Changed = false;

  MachineBasicBlock::iterator I = MBB.end();
  if (I != MBB.begin())
    I--;    // set I to the last instruction
  else
    return Changed;

  if (I->getOpcode() == MYRISCVX::PseudoBR &&
      I->getOperand(0).getType() == MachineOperand::MO_MachineBasicBlock &&
      I->getOperand(0).getMBB() == &MBBN) {
    // I is the instruction of "jmp #offset=0", as follows,
    //     jal     zero, $BB0_3
    // $BB0_3:
    //     ld  $4, 28($sp)
    ++NumDelJmp;
    MBB.erase(I);   // delete the "JMP 0" instruction
    Changed = true;    // Notify LLVM kernel Changed
  }

  return Changed;
}

runOnMachineBasicBasicBlockでは、BasicBlockMBBと次のBasicBlockMBBNを使って最適化処理を行っている。 MBBの最後の命令が対象となる命令で、イテレータIで示されている。IRISC-VのPseudoBR、つまりJAL ZERO命令であり、さらに第1オペランドが示している先がMBBN(次のBasic Blockの先頭)であれば、削除可能だ。MBB.erase(I)により命令の削除を行い、ChangeをTrueに設定、そして最適化を行った回数を示すNumDelJmpをインクリメントする。

このNumDelJmp変数は、llcの-statsオプションにより参照することができる。

では、ここまでの変更を施したコードでLLVMをビルドしてみる。

# DelJmpPassを有効にした場合
# -enable-MYRISCVX-del-useless-jmp=true と同等
./bin/llc -debug -march=myriscvx32 -filetype=asm if_ctrl.rv32.bc -stats -o -
# DelJmpPassを無効にした場合
./bin/llc -debug -march=myriscvx32 -enable-MYRISCVX-del-useless-jmp=false -filetype=asm if_ctrl.rv32.bc -o -

それぞれ生成されたコードは以下のようになった。

  • DelJmpPassを無効にした場合
_Z11test_ifctrlv:                       # @_Z11test_ifctrlv

# %bb.0:                                # %entry
        addi    x2, x2, -4
        addi    x10, zero, 0
        sw      x10, 0(x2)
        lw      x10, 0(x2)
        bne     x10, zero, $BB0_2
        j       $BB0_1
$BB0_1:                                 # %if.then
        lw      x10, 0(x2)
        addi    x10, x10, 1
        sw      x10, 0(x2)
        j       $BB0_2
$BB0_2:                                 # %if.end
        addi    x2, x2, 4
        ret
  • DelJmpPassを有効にした場合
_Z11test_ifctrlv:                       # @_Z11test_ifctrlv

# %bb.0:                                # %entry
        addi    x2, x2, -4
        addi    x10, zero, 0
        sw      x10, 0(x2)
        lw      x10, 0(x2)
        bne     x10, zero, $BB0_2
# %bb.1:                                # %if.then
        lw      x10, 0(x2)
        addi    x10, x10, 1
        sw      x10, 0(x2)
$BB0_2:                                 # %if.end
        addi    x2, x2, 4
        ret

不要なJ命令が削除されているのが分かる。不要なJ命令がどれだけ削除されたのか-statsオプションを付けて確認してみようと思う。

./bin/llc -march=myriscvx32 -stats -filetype=asm if_ctrl.rv32.bc -o -
===-------------------------------------------------------------------------===
                          ... Statistics Collected ...
===-------------------------------------------------------------------------===

10 asm-printer    - Number of machine instrs printed
35 bitcode-reader - Number of Metadata records loaded
 2 bitcode-reader - Number of MDStrings loaded
 1 dagcombine     - Number of dag nodes combined
 2 del-jmp        - Number of useless jmp deleted
 3 isel           - Number of blocks selected using DAG
30 isel           - Number of times dag isel has to try another path
 1 isel           - Number of entry blocks encountered
 4 prologepilog   - Number of bytes used for stack in all functions
 1 prologepilog   - Number of functions seen in PEI
 4 regalloc       - Number of registers assigned
 1 stackmaps      - Number of functions skipped
 1 stackmaps      - Number of functions visited

del-jmp Passにより、2つの命令が削除されていることが分かった。