Cpu0のバックエンドをLLVMに追加するプロジェクト、8章では、if文などの制御文をサポートする。
今回も非常にファイル量が多くて、とりあえずLLVMをビルドするためだけにパッチを作って当てているが、LLVM 7.0は未サポートになっている部分が多く、ソースコードを書き直す必要があった。
- Chapter8の実装を追加したもの
制御フロー文
分岐命令のサポートを行う。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-jmp８が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が分かりやすかった。
条件に合わせて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'
