FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages

オリジナルLLVMバックエンド実装をまとめる(15. case文で使用されるJumpTableのサポート)

f:id:msyksphinz:20191007020939p:plain:w200

次は、if文を組み合わせたような形で登場するswitch文のサポートを考える。以下のようなコードを用意した。

  • test_switch.cpp
int test_value = 0x30;  // 0x30, 0x31, ... ,0x35
int a_val = 0;
int b_val = 0;

void test_switch ()
{
  int result = 0;

  switch (test_value)
  {
    case 0x30:
      if (a_val == b_val)
        result = 1;
      break;
    case 0x31:
      if (a_val != b_val)
        result = 1;
      break;
    case 0x32:
      if (a_val > b_val)
        result = 1;
      break;
    case 0x33:
      if (a_val < b_val)
        result = 1;
      break;
    case 0x34:
      if (a_val >= b_val)
        result = 1;
      break;
    case 0x35:
      if (a_val <= b_val)
        result = 1;
      break;
  }
  return;
}

switchとifを組み合わせたようなコードだ。これをclangでコンパイルするとどのようなIRが生成されるだろうか。

./bin/clang test_switch.cpp -c -emit-llvm --target=riscv32-unknown-elf -o test_switch.rv32.bc
./bin/llvm-dis test_switch.rv32.bc -o -
define dso_local void @_Z11test_switchv() #0 {
entry:
  %result = alloca i32, align 4
  store i32 0, i32* %result, align 4
  %0 = load i32, i32* @test_value, align 4
  switch i32 %0, label %sw.epilog [
    i32 48, label %sw.bb
    i32 49, label %sw.bb1
    i32 50, label %sw.bb5
    i32 51, label %sw.bb9
    i32 52, label %sw.bb13
    i32 53, label %sw.bb17
  ]

sw.bb:                                            ; preds = %entry
  %1 = load i32, i32* @a_val, align 4
  %2 = load i32, i32* @b_val, align 4
  %cmp = icmp eq i32 %1, %2
  br i1 %cmp, label %if.then, label %if.end
...

switchというIRが生成された。このswitchを扱い、テーブルジャンプをサポートするためには、インダイレクトジャンプ、そしてテーブルジャンプについて考慮する必要がある。

BRIND インダイレクトジャンプ。
The first operand is the chain, the second is the value to branch to, which must be of the same type as the target's pointer type.
JumpTable ジャンプテーブル。BR_JTで使用されるテーブルジャンプ。
./bin/llc -debug -march=myriscvx32 -filetype=asm test_switch.bc -o -

以下のようなメッセージが出てくる。br_jt, JumpTable IRが挿入されたことが分かる。

Total amount of phi nodes to update: 0
Creating new node: t2: i32,ch = CopyFromReg t0, Register:i32 %0
Creating new node: t4: ch = br_jt t2:1, JumpTable:i32<0>, t2
Initial selection DAG: %bb.20 '_Z10test_ctrl2v:entry'
SelectionDAG has 5 nodes:
    t0: ch = EntryToken
  t2: i32,ch = CopyFromReg t0, Register:i32 %0
  t4: ch = br_jt t2:1, JumpTable:i32<0>, t2

まずはインダイレクトジャンプについて考える。 インダイレクトジャンプでは、命令のエンコーディングに基づいてジャンプするのではなく汎用レジスタに格納されている値に対してジャンプをしたいので、使用するのはJALR命令、そして関数コールではないので戻り値を使用せず、戻りアドレスはZEROとする(実質JAL命令)。 そこで、PseudoBRINDという疑似ノードを作成する。 この疑似ノードを作成するのは、パタンとして登録する前に、この疑似ノードの特徴(isBranchなど)を明示的に指定するためだ。 この後で、疑似命令を使用した命令生成パタンを登録する。

commit:92722f2ef83 Support switch branch

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
let isBarrier = 1, isBranch = 1, isIndirectBranch = 1, isTerminator = 1 in
def PseudoBRIND : MYRISCVXPseudo<(outs), (ins GPR:$rs1, simm12:$simm12), "", []>,
                  PseudoInstExpansion<(JALR ZERO, GPR:$rs1, simm12:$simm12)>;

汎用レジスタと即値で与えれるアドレスに対してジャンプするJALR命令で、分岐命令用ではない(isCall=1としていない)で、JALR命令だ。この疑似命令を使って生成パタンを作る。

def : Pat<(brind GPR:$rs1), (PseudoBRIND GPR:$rs1, 0)>;
def : Pat<(brind (add GPR:$rs1, simm12:$simm12)),
          (PseudoBRIND GPR:$rs1, simm12:$simm12)>;

単純な汎用レジスタだけの指定であれば即値は0、そうでなければ即値を使用してジャンプする。

次にジャンプテーブルだが、そもそもテーブルジャンプはBR_JTの生成を抑制しているので出て来ない。次は、ジャンプテーブルそのものの生成を止める。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
  // BR_JT命令の生成はそもそも抑制している。
  setOperationAction(ISD::BR_CC,     XLenVT,     Expand);
  setOperationAction(ISD::BR_JT,     MVT::Other, Expand);

これには、MYRISCVXTargetLowering::MYRISCVXTargetLowering()setMinimumJumpTableEntries()を設定して、ジャンプテーブルが生成されるエントリ数の下限値を整数の最大値に設定して、無理やりテーブルの生成を止めるのが良さそうだ。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
  // Effectively disable jump table generation.
  setMinimumJumpTableEntries(INT_MAX);

それではここまでの実装を再度ビルドして実行する。

./bin/clang test_switch.cpp -c -emit-llvm --target=riscv32-unknown-elf -o test_switch.rv32.bc
./bin/llc -debug -march=myriscvx32 -filetype=asm test_switch.rv32.bc -o -
_Z11test_switchv:                       # @_Z11test_switchv

# %bb.0:                                # %entry
        addi    x2, x2, -4
        addi    x10, zero, 0
        sw      x10, 0(x2)
        lui     x10, %hi(test_value)
        ori     x10, x10, %lo(test_value)
        lw      x10, 0(x10)
        addi    x11, zero, 48
        beq     x10, x11, $BB0_6
        j       $BB0_1
$BB0_1:                                 # %entry
        addi    x11, zero, 49
        beq     x10, x11, $BB0_9
        j       $BB0_2
$BB0_2:                                 # %entry
        addi    x11, zero, 50
        beq     x10, x11, $BB0_12
        j       $BB0_3
$BB0_3:                                 # %entry
        addi    x11, zero, 51
        beq     x10, x11, $BB0_15
        j       $BB0_4
$BB0_4:                                 # %entry
        addi    x11, zero, 52
        beq     x10, x11, $BB0_18
        j       $BB0_5
$BB0_5:                                 # %entry
        addi    x11, zero, 53
        beq     x10, x11, $BB0_21
        j       $BB0_24

まずはテーブルジャンプだ。テーブルは分解され、すべて比較命令と分岐命令に置き換わっている。 比較が成立すると、switchのcaseは成立したことなり、条件成立時の動作に移行する。

$BB0_6:                                 # %sw.bb
        lui     x10, %hi(a_val)
        ori     x10, x10, %lo(a_val)
        lw      x10, 0(x10)
        lui     x11, %hi(b_val)
        ori     x11, x11, %lo(b_val)
        lw      x11, 0(x11)
        bne     x10, x11, $BB0_8
        j       $BB0_7
$BB0_7:                                 # %if.then
        addi    x10, zero, 1
        sw      x10, 0(x2)
        j       $BB0_8
$BB0_8:                                 # %if.end
        j       $BB0_24

case文のなかの動作だ。これは単純にif文なので、値をロードして比較、比較結果によりジャンプ、という流れの命令が生成されている。上手く行っているようだ。