FPGA開発日記

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

"Creating an LLVM Backend for the Cpu0 Architecture"をやってみる(13. 制御文のサポート)

f:id:msyksphinz:20181123225150p:plain

Cpu0のバックエンドをLLVMに追加するプロジェクト、8章では、if文などの制御文をサポートする。

今回も非常にファイル量が多くて、とりあえずLLVMをビルドするためだけにパッチを作って当てているが、LLVM 7.0は未サポートになっている部分が多く、ソースコードを書き直す必要があった。

  • Chapter8の実装を追加したもの

github.com

github.com

制御フロー文

分岐命令のサポートを行う。if文をコンパイルすると、icmp文が生成される。

  %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
}

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

$ bin/llc -march=cpu0 -mcpu=cpu032I -relocation-model=pic -filetype=asm ch8_1_1.bc -o -
        ld      $3, 4($sp)
        cmp     $sw, $3, $2
        jne     $sw, $BB0_2
        jmp     $BB0_1
$BB0_1:                                 # %if.then
        ld      $2, 4($sp)
        addiu   $2, $2, 1
        st      $2, 4($sp)
        jmp     $BB0_2
$BB0_2:                                 # %if.end
        ld      $2, 4($sp)
        addiu   $sp, $sp, 8
        ret     $lr

cpu032Iとcpu032IIで生成される命令が異なる。cpu032IIはconditional branchが使えるので生成される命令が異なる。

$ bin/llc -march=cpu0 -mcpu=cpu032II -relocation-model=pic -filetype=asm ch8_1_1.bc -o -
        ld      $2, 4($sp)
        bne     $2, $zero, $BB0_2
        jmp     $BB0_1
$BB0_1:                                 # %if.then
        ld      $2, 4($sp)
        addiu   $2, $2, 1
        st      $2, 4($sp)
        jmp     $BB0_2
$BB0_2:                                 # %if.end
        ld      $2, 4($sp)
        addiu   $sp, $sp, 8
        ret     $lr

長距離分岐サポート

cpu032IIでは、ジャンプのオフセットが24-bitから16-bitに削減されている。もしも16-bitよりも遠い距離をジャンプすることになると、cpu032IIはコードの生成に失敗する。そこで、長距離分岐をサポートする。

./bin/clang -c -target mips-unknown-linux-gnu ../lbdex/input/ch8_2_longbranch.cpp -emit-llvm -o ch8_2_longbranch.bc
        ld      $2, 12($sp)
        ld      $3, 8($sp)
        slt     $2, $2, $3
        beq     $2, $zero, $BB0_2
        nop
# %bb.1:                                # %if.then
        addiu   $2, $zero, 1
        st      $2, 4($sp)
$BB0_2:                                 # %if.end
        ld      $2, 4($sp)
        addiu   $sp, $sp, 16
        ret     $lr

Cpu0バックエンド最適化: 未使用JMP命令の削除

ここでは、未使用のJMP命令を削除するバックエンド最適化を追加する。このアルゴリズムはシンプルで、最適化のチュートリアルに適している。

DelJmp関数は不要なジャンプ命令を削除している。不要なジャンプ命令とは、ジャンプ先が次の命令だった場合である。Cpu0::JMPのジャンプ先が次のブロック(=&MBBN)出会った場合に削除する。

  if (I->getOpcode() == Cpu0::JMP && I->getOperand(0).getMBB() == &MBBN) {
    // I is the instruction of "jmp #offset=0", as follows,
    //     jmp  $BB0_3
    // $BB0_3:
    //     ld   $4, 28($sp)
    ++NumDelJmp;
    MBB.erase(I);   // delete the "JMP 0" instruction
    Changed = true; // Notify LLVM kernel Changed
  }
./bin/clang -c -target mips-unknown-linux-gnu ../lbdex/input/ch8_2_deluselessjmp.cpp -emit-llvm -o ch8_2_deluselessjmp.bc
bin/llc -march=cpu0 -mcpu=cpu032II -relocation-model=pic -filetype=asm -stats ch8_2_deluselessjmp.bc -o -

del-jmp8が8回適用されている。

===-------------------------------------------------------------------------===
                          ... Statistics Collected ...
===-------------------------------------------------------------------------===

46 asm-printer       - Number of machine instrs printed
34 bitcode-reader    - Number of Metadata records loaded
 2 bitcode-reader    - Number of MDStrings loaded
14 dagcombine        - Number of dag nodes combined
 8 del-jmp           - Number of useless jmp deleted
 5 delay-slot-filler - Number of delay slots filled
10 isel              - Number of blocks selected using DAG
32 isel              - Number of times dag isel has to try another path
 1 isel              - Number of entry blocks encountered
16 prologepilog      - Number of bytes used for stack in all functions
28 regalloc          - Number of registers assigned
 1 regalloc          - Number of identity moves eliminated after rewriting
 1 stackmaps         - Number of functions skipped
 1 stackmaps         - Number of functions visited

分岐遅延スロットを埋める最適化

まずは、分岐遅延スロットをNOPで埋める処理を行う。

  for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
    if (!hasUnoccupiedSlot(&*I))
      continue;

    ++FilledSlots;
    Changed = true;

    // Bundle the NOP to the instruction with the delay slot.
    BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Cpu0::NOP));
    MIBundleBuilder(MBB, I, std::next(I, 2));
  }

分岐命令

分岐命令を生成する。2項演算子による選択は、selectが使用される。

./bin/clang -c -target mips-unknown-linux-gnu ../lbdex/input/ch8_2_select.cpp -emit-llvm -o ch8_2_select.bc
./bin/llvm-dis ch8_2_select.bc -o -
entry:
  %a = alloca i32, align 4
  %c = alloca i32, align 4
  store volatile i32 1, i32* %a, align 4
  store i32 0, i32* %c, align 4
  %0 = load volatile i32, i32* %a, align 4
  %tobool = icmp ne i32 %0, 0
  %lnot = xor i1 %tobool, true
  %1 = zext i1 %lnot to i64
  %cond = select i1 %lnot, i32 1, i32 3
  store i32 %cond, i32* %c, align 4
  %2 = load i32, i32* %c, align 4
  ret i32 %2
}

最終的には、movzなどの命令が使用される。

$ ./bin/llc -march=cpu0 -mcpu=cpu032I -relocation-model=pic -filetype=asm ch8_2_select.bc -o -
        ld      $3, 4($sp)
        addiu   $4, $zero, 3
        movn    $2, $4, $3
        st      $2, 0($sp)
        ld      $2, 0($sp)
        addiu   $sp, $sp, 8
        ret     $lr

Phiノード

ここでは、Phiノードのサポートを行う。Phiノードというのは知らなかったのだが、SSAにおける最適化の一手法らしい。

Phiノードの説明はWikipediaが分かりやすかった。

静的単一代入 - Wikipedia

f:id:msyksphinz:20181227232842p:plain
https://upload.wikimedia.org/wikipedia/commons/8/84/SSA_example1.3.png より引用。

条件に合わせてy1とy2のどちらかがy3に格納されるのだが、通常はそれを決める手段がない。 そこで、PhiノードというΦ(y1, y2)の関数を追加して、最後のブロックで正しいyを参照できるようになる。

これを試験するためには、lbdex/inputs/ch8_2_phinode.cppを使用する。

  • lbdex/inputs/ch8_2_phinode.cpp
/// start
int test_phinode(int a , int b, int c)
{
  int d = 2;

  if (a == 0) {
    a++; // a = 1
  }
  else if (b != 0) {
    a--; // b = 2
  }
  else if (c == 0) {
    a += 2;
  }
  d = a + b;

  return d;
}

以下のように-O3を追加することでPhiノードを追加する。

$ ./bin/clang -O3 -c -target mips-unknown-linux-gnu ../lbdex/input/ch8_2_phinode.cpp -emit-llvm -o ch8_2_phinode.bc
$ bin/llvm-dis ch8_2_phinode.bc -o -
entry:
  %cmp = icmp eq i32 %a, 0
  br i1 %cmp, label %if.end7, label %if.else

if.else:                                          ; preds = %entry
  %cmp1 = icmp eq i32 %b, 0
  br i1 %cmp1, label %if.else3, label %if.then2

if.then2:                                         ; preds = %if.else
  %dec = add nsw i32 %a, -1
  br label %if.end7

if.else3:                                         ; preds = %if.else
  %cmp4 = icmp eq i32 %c, 0
  %add = add nsw i32 %a, 2
  %spec.select = select i1 %cmp4, i32 %add, i32 %a
  br label %if.end7

if.end7:                                          ; preds = %entry, %if.else3, %if.then2
  %a.addr.0 = phi i32 [ %dec, %if.then2 ], [ %spec.select, %if.else3 ], [ 1, %entry ]
  %add8 = add nsw i32 %a.addr.0, %b
  ret i32 %add8

最後に、%a.addr.0 = phi i32 [ %dec, %if.then2 ], [ %spec.select, %if.else3 ], [ 1, %entry ]が追加されている。これがPhiノードというものらしい。

実際にllcを実行してみると、エラーとなった。これはノードが足りないらしい。

$ bin/llc -march=cpu0 -mcpu=cpu032I -relocation-model=pic -filetype=asm ch8_2_phinode.bc -o -
        .text
        .section .mdebug.abiO32
        .previous
        .file   "ch8_2_phinode.cpp"
llc: /home/msyksphinz/work/riscv/llvm-msyksphinz/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:9025: void llvm::SelectionDAGISel::LowerArguments(const llvm::Function &): Assertion `InVals.size() == Ins.size() && "LowerFormalArguments didn't emit the correct number of values!"' failed.
Stack dump:
0.      Program arguments: bin/llc -march=cpu0 -mcpu=cpu032I -relocation-model=pic -filetype=asm ch8_2_phinode.bc -o -
1.      Running pass 'Function Pass Manager' on module 'ch8_2_phinode.bc'.
2.      Running pass 'CPU0 DAG->DAG Pattern Instruction Selection' on function '@_Z12test_phinodeiii'