Cpu0のバックエンドをLLVMに追加するプロジェクト、今回からは4章に入って、算術論理演算命令を追加する。まずは算術演算から。
算術演算において、特殊な演算ケースの場合は演算を最適化できる場合がある。この方式についても見ていく。
実装は以下。cpu0_chapter4ブランチに実装した。
github.com
以下の章を参考にした。
Arithmetic and Logic Instructions
Cpu0の算術演算を追加する。本章ではIRをGraphvizで表示する。DAGの変換のいくつかはGraphvizを使って説明する。算術演算命令を追加した後に、論理演算命令を追加する。
C言語のプログラムをコンパイルする中で、読者はC言語のプログラムがどのように変換されるのかについてみる。バックエンドの構造に加えて、読者はC言語の演算子がLLVM noIRにどのようにマッピングするのかについて説明する。本章ではHILOとC0レジスタクラスを追加する。読者は、汎用レジスタクラスだけでなく、このような特殊なレジスタの使用方法について学ぶ。
算術演算
+, -, *, <<, >> 演算子
+, -, *, SHL, SHLV(<<), SRA, SRAV, SHR, SHRV(>>)のための演算子が定義されている。
Chapter4_1では、C言語で言う +, -, *, <<, >> を扱うことができる。LLVM IRでadd, sub, mul, shl, ashrが定義されている。ashr命令(arithmetic shift right)命令は第1オペランドを符号拡張した形で右シフトする。
@@ -304,11 +405,36 @@ let Predicates = [DisableOverflow] in {
def ADDu : ArithLogicR<0x11, "addu", add, IIAlu, CPURegs, 1>;
}
}
+let Predicates = [Ch4_1] in {
+let Predicates = [DisableOverflow] in {
+def SUBu : ArithLogicR<0x12, "subu", sub, IIAlu, CPURegs>;
+}
+let Predicates = [EnableOverflow] in {
+def ADD : ArithLogicR<0x13, "add", add, IIAlu, CPURegs, 1>;
+def SUB : ArithLogicR<0x14, "sub", sub, IIAlu, CPURegs>;
+}
+def MUL : ArithLogicR<0x17, "mul", mul, IIImul, CPURegs, 1>;
+}
/// Shift Instructions
+let Predicates = [Ch4_1] in {
+// sra is IR node for ashr llvm IR instruction of .bc
+def ROL : shift_rotate_imm32<0x1b, 0x01, "rol", rotl>;
+def ROR : shift_rotate_imm32<0x1c, 0x01, "ror", rotr>;
+def SRA : shift_rotate_imm32<0x1d, 0x00, "sra", sra>;
+}
let Predicates = [Ch3_5] in {
def SHL : shift_rotate_imm32<0x1e, 0x00, "shl", shl>;
}
+let Predicates = [Ch4_1] in {
+// srl is IR node for lshr llvm IR instruction of .bc
+def SHR : shift_rotate_imm32<0x1f, 0x00, "shr", srl>;
+def SRAV : shift_rotate_reg<0x20, 0x00, "srav", sra, CPURegs>;
+def SHLV : shift_rotate_reg<0x21, 0x00, "shlv", shl, CPURegs>;
+def SHRV : shift_rotate_reg<0x22, 0x00, "shrv", srl, CPURegs>;
+def ROLV : shift_rotate_reg<0x23, 0x01, "rolv", rotl, CPURegs>;
+def RORV : shift_rotate_reg<0x24, 0x01, "rorv", rotr, CPURegs>;
+}
def JR : JumpFR<0x3c, "jr", GPROut>;
例えば、shift_rotate_immは以下のように定義されている。srlなどの演算子はOpNodeに格納されれう。"shr"はstring instr_asmに格納されている。
class shift_rotate_imm<bits<8> op, bits<4> isRotate, string instr_asm,
SDNode OpNode, PatFrag PF, Operand ImmOpnd,
RegisterClass RC>:
FA<op, (outs GPROut:$ra), (ins RC:$rb, ImmOpnd:$shamt),
!strconcat(instr_asm, "\t$ra, $rb, $shamt"),
[(set GPROut:$ra, (OpNode RC:$rb, PF:$shamt))], IIAlu> {
let rc = 0;
}
- lshr: Logical SHift Right
- ashr: Arithmetic SHift right
- srl: Shift Right Logically
- sra: Shift Right Arithmetically
- shr: SHift Right
x >> 1は、x = x/2であると考えるとすると、演算子>>の実装ではlshrは符号付値では失敗する。同様にashrでは符号なし値で失敗する。したがって、符号付と符号なしの両方で演算を実行するためには、lshrとashrの両方が必要になる。
<<実装はlshrは"符号なしx = 1G"を満たすが、"符号付きx = 1G"では失敗することがわかる。 2Gは32ビット符号付き整数範囲（-2G〜2G-1）の外にあるので問題ない。 オーバーフローの場合、正しい結果をレジスタに保持する方法はない。 したがって、レジスタ内の値はすべて問題ない。 すべてのx << 1に対してlshrがx = x * 2を満たし、xの結果が範囲外でないことを確認できる。オペランドxが符号付きまたは符号なし整数であっても問題ない。
define i32 @_Z9test_mathv()
%a = alloca i32, align 4
%b = alloca i32, align 4
%1 = load i32, i32* %a, align 4
%2 = load i32, i32* %b, align 4
%3 = add nsw i32 %1, %2
%4 = sub nsw i32 %1, %2
%5 = mul nsw i32 %1, %2
%6 = shl i32 %1, 2
%7 = ashr i32 %1, 2
%8 = lshr i32 %1, 30
%9 = shl i32 1, %2
%10 = ashr i32 128, %2
%11 = ashr i32 %1, %2
%12 = add nsw i32 %3, %4
%13 = add nsw i32 %12, %5
%14 = add nsw i32 %13, %6
%15 = add nsw i32 %14, %7
%16 = add nsw i32 %15, %8
%17 = add nsw i32 %16, %9
%18 = add nsw i32 %17, %10
%19 = add nsw i32 %18, %11
ret i32 %19
}
$ ./bin/llc -march=cpu0 -relocation-model=pic -filetype=asm ../lbdex/input/ch4_math.ll -o -
.text
.section .mdebug.abiO32
.previous
.file "ch4_math.ll"
.globl _Z9test_mathv
.p2align 2
.type _Z9test_mathv,@function
.ent _Z9test_mathv
_Z9test_mathv:
.cfi_startproc
.frame $sp,8,$lr
.mask 0x00000000,0
.set noreorder
.set nomacro
addiu $sp, $sp, -8
.cfi_def_cfa_offset 8
ld $2, 0($sp)
ld $3, 4($sp)
subu $4, $3, $2
addu $5, $3, $2
addu $4, $5, $4
mul $5, $3, $2
addu $4, $4, $5
shl $5, $3, 2
addu $4, $4, $5
sra $5, $3, 2
addu $4, $4, $5
addiu $5, $zero, 128
shrv $5, $5, $2
addiu $t9, $zero, 1
shlv $t9, $t9, $2
srav $2, $3, $2
shr $3, $3, 30
addu $3, $4, $3
addu $3, $3, $t9
addu $3, $3, $5
addu $2, $3, $2
addiu $sp, $sp, 8
ret $lr
.set macro
.set reorder
.end _Z9test_mathv
$func_end0:
.size _Z9test_mathv, ($func_end0)-_Z9test_mathv
.cfi_endproc
.section ".note.GNU-stack","",@progbits
オーバフローの検出を行う。
$ ./bin/clang -target mips-unknown-linux-gnu -c ch4_1_addsuboverflow.cpp -emit-llvm -o ch4_1_addsuboverflow.bc
$ llvm-dis ch4_1_addsuboverflow.bc -o -
%add = add nsw i32 %0, %1
%sub = sub nsw i32 %0, %1
-cpu0-enable-overflow=true を追加した場合
$ ./bin/llc -march=cpu0 -relocation-model=pic -filetype=asm -cpu0-enable-overflow=true ch4_1_addsuboverflow.bc -o -
add $3, $3, $4
...
sub $3, $3, $4
-cpu0-enable-overflow=falseを追加した場合(デフォルト)
$ ./bin/llc -march=cpu0 -relocation-model=pic -filetype=asm -cpu0-enable-overflow=true ch4_1_addsuboverflow.bc -o -
addu $3, $3, $4
...
subu $3, $3, $4
現代のCPUでは、プログラマは加減算においてオーバフローを省略できる命令を利用することができる。しかし-cpu0-enable-overflow=trueを追加することにより、プログラマはオーバフロー例外を発生させることができる。通常、このオプションはデバッグ目的に利用する。
$ bin/clang -target mips-unknown-linux-gnu -c ../lbdex/input/ch4_1_mult.cpp -emit-llvm -o ch4_1_mult.bc
$ bin/llc -view-dag-combine1-dags -march=cpu0 -relocation-model=pic -filetype=asm ./ch4_1_mult.bc -o ch4_1_mult.cpu0.s
%演算子はsrem IRに相当する。
LLVMはsrem除算を乗算に変換し、DIVの演算コストを削減する。例えば、"int b = 11; b = (b+1)%12" はDAG上で図18のように最適化される。
この変換は少しややこしい。0xC x 0x2AAAAAAB = 0x2_00000004 となる(mulhs 0xC, 0x2AAAAAAAB) は、符号付乗算の上位32ビットを取得することを意味す。1ワードずつの数値の乗算結果は、通常、2ワード分の値を生成する(0x2, 0xAAAAAAAB)。この場合の上位の値、つまり0x2である。最終的な結果は(sub 12, 12)となり結果は0となる。これは(0x11+1)%12に相当する。
どうもこの0x2AAAAAABというのはマジック値であるらしい。%12で割り算をするためには、このような方法がとられるのか。
Armの解法
/// Multiply and Divide Instructions.
def SMMUL : ArithLogicR<0x41, "smmul", mulhs, IIImul, CPURegs, 1>;
def UMMUL : ArithLogicR<0x42, "ummul", mulhu, IIImul, CPURegs, 1>;
//def MULT : Mult32<0x41, "mult", IIImul>;
//def MULTu : Mult32<0x42, "multu", IIImul>;
SMMUL命令とUMMUL命令を使用して、乗算の結果から上位の32bitを取得することができる。
addiu $2, $zero, 12
smmul $3, $2, $3
shr $4, $3, 31
def mulhs : SDNode<"ISD::MULHS" , SDTIntBinOp, [SDNPCommutative]>;
def mulhu : SDNode<"ISD::MULHU" , SDTIntBinOp, [SDNPCommutative]>;
MIPSの場合は、HILOレジスタに乗算命令の結果を格納するので、HIレジスタから値を持ってくればよい。
addiu $2, $zero, 12
mult $2, $3
mfhi $3
shr $4, $3, 31
%演算と/演算の完全サポート
上記の演算をより一般化して、"(b+1)%a"を計算する場合、LLVMはエラーを出してしまう。上記の剰余を乗算に変換する計算は、一般化したコードとして出力でき兄からだ。したがって、一般的には、上除算命令を実行した後にHILOレジスタから値を取ってくる方法が取られる。"c = a / b"は、"div a, b"と、"mflo c"の2つに分割される。
完全な"%"と"/"をサポートするためには、Chapter4_1のように以下を追加する。
- SDIV, UDIVを
Cpu0InstrInfo.tdに追加する。
copyPhysReg()を追加する。setOperationAction(ISD::SDIV, MVT::i32, Expand), ... setTargetDAGCombine(ISD::SDIVREM)と、PerformDivRemCombine()とPerformDAGCombine()を追加する。
static SDValue performDivRemCombine(SDNode *N, SelectionDAG& DAG,
TargetLowering::DAGCombinerInfo &DCI,
const Cpu0Subtarget &Subtarget) {
...
if (N->hasAnyUseOfValue(0)) {
SDValue CopyFromLo = DAG.getCopyFromReg(InChain, DL, LO, Ty,
InGlue);
DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), CopyFromLo);
InChain = CopyFromLo.getValue(1);
InGlue = CopyFromLo.getValue(2);
}
...
return SDValue();
}
以下のコードを実行すると、div命令とmfhiが出力された。
lbdex/input/ch4_1_mult2.cpp
int test_mult()
{
int b = 11;
int a = 12;
b = (b+1)%a;
return b;
}
ld $2, 4($sp)
addiu $2, $2, 1
ld $3, 0($sp)
div $2, $3
mfhi $2
st $2, 4($sp)
ローテート命令
ローテート命令も同様に追加した。演算子自体は、以下で追加しているものと思われる。これで、Cのコードからローテートを推論できる。
/// Shift Instructions
let Predicates = [Ch4_1] in {
// sra is IR node for ashr llvm IR instruction of .bc
def ROL : shift_rotate_imm32<0x1b, 0x01, "rol", rotl>;
def ROR : shift_rotate_imm32<0x1c, 0x01, "ror", rotr>;
def SRA : shift_rotate_imm32<0x1d, 0x00, "sra", sra>;
}
&, |, ^, ! ==, !=, <, <=, >, >= 演算子をサポートする。以下のファイルに実装の追加を行う。
lib/Target/Cpu0/Cpu0ISelLowering.cpplib/Target/Cpu0/Cpu0InstrInfo.tdlib/Target/Cpu0/Cpu0Subtarget.h
-mcpu=cpu032Iと-mcpu=cpu032IIで生成されるプログラムが異なる。cpu032Iはcmp命令で処理、cpu032IIは比較命令で処理。cpu032Iとcpu032IIの命令セットの違いは、以下を確認。
ld $2, 28($sp)
ld $3, 24($sp)
cmp $sw, $2, $3
ld $2, 28($sp)
ld $3, 24($sp)
slt $2, $2, $3
