网站导航
> 文章列表 > LLVM编译器后端比较功能的添加

LLVM编译器后端比较功能的添加

网友: 文章列表 2024-03-22 01:50:14

LLVM编译器后端比较功能的添加

1.动机

从机器层面上来看，控制流类的跳转指令分为无条件跳转和有条件跳转，无条件跳转 JMP，有条件跳转 JEQ、JNE、JLT、JGT、JLE、JGE，这部分指令是需要通过检查 condition code （SW 寄存器）来决定跳转条件；J 类型指令依赖的 condition code 是通过比较指令（比如 CMP）的结果来设置的。如下图所示，JNE跳转指令通过检查SW寄存器的状态以决定是否发生跳转。因此，为了支持控制流功能，首先要打通比较功能。

LLVM编译器后端比较功能的添加

2.LLVM IR 中的比较指令

LLVM IR提供的 int 类型比较指令为 icmp。其接受三个参数：比较方案以及两个比较参数。

%result = icmp ule i32 %a, %b

ule是比较方案，其中 u 为 unsigned int，le 为 lower than or equal，%a和%b就是用来比较的两个数，而icmp则返回一个i1类型的值，用来表示结果是否为真。

与ule类似的比较方案有多种，如：

  • 等于与不等于：eq、ne；

  • 无符号比较：ugt、uge、ult、ule， 分别对应无符号的大于、大于等于、小于、小于等于；

  • 有符号比较：sgt、sge、slt、sle， 分别对应有符号的大于、大于等于、小于、小于等于。

3.实现比较功能的添加

3.1 定义format

class FA<bits<8> op, dag outs, dag ins, string asmStr,list<dag> pattern, InstrItinClass itin>: Cpu0Inst<outs, ins, asmStr, pattern, itin, FrmA>
{bits<4>  ra;bits<4>  rb;bits<4>  rc;bits<12> shamt;let Opcode = op;let Inst{23-20} = ra;let Inst{19-16} = rb;let Inst{15-12} = rc;let Inst{11-0}  = shamt;
}

rb、rc为两个寄存器类型源操作数，用于存放比较的数据，ra为寄存器类型目的操作数，用来存放比较的结果。

class FL<bits<8> op, dag outs, dag ins, string asmStr,list<dag> pattern, InstrItinClass itin>: Cpu0Inst<outs, ins, asmStr, pattern, itin, FrmL>
{bits<4>  ra;bits<4>  rb;bits<16> imm16;let Opcode = op;let Inst{23-20} = ra;let Inst{19-16} = rb;let Inst{15-0}  = imm16;
}

rb为寄存器类型源操作数，用于存放比较的数据，imm16是用于比较的16位立即数，ra为寄存器类型目的操作数，用来存放比较的结果。

3.2 定义指令

class SetCC_R<bits<8> op, string instrAsm, PatFrag condOp,RegisterClass RC>: FA<op, (outs GPROut:$ra), (ins RC:$rb, RC:$rc),!strconcat(instrAsm, "\\t$ra, $rb, $rc"),[(set GPROut:$ra, (condOp RC:$rb, RC:$rc))],IIAlu>, Requires<[HasSlt]> {let shamt = 0;
}
def SLT      : SetCC_R<0x28, "slt", setlt, CPURegs>;
def SLTu     : SetCC_R<0x29, "sltu", setult, CPURegs>;

SetCC_R继承自上面定义的FA 。SLT、SLTu对应着小于、无符号小于两种比较方案

class SetCC_I<bits<8> op, string instrAsm, PatFrag condOp, Operand Od,PatLeaf immType, RegisterClass RC>: FL<op, (outs GPROut:$ra), (ins RC:$rb, Od:$imm16),!strconcat(instrAsm, "\\t$ra, $rb, $imm16"),[(set GPROut:$ra, (condOp RC:$rb, immType:$imm16))],IIAlu>, Requires<[HasSlt]>;class FMem<bits<8> op, dag outs, dag ins, string asmStr, list<dag> pattern,InstrItinClass itin>: FL<op, outs, ins, asmStr, pattern, itin> {bits<20> addr;let Inst{19-16}   = addr{19-16};let Inst{15-0}    = addr{15-0};let DecoderMethod = "DecodeMem";
}
def SLTi     : SetCC_I<0x26, "slti", setlt, simm16, immSExt16, CPURegs>;
def SLTiu    : SetCC_I<0x27, "sltiu", setult, simm16, immSExt16, CPURegs>;

SetCC_I继承自上面定义的FL 。SLTi、SLTiu对应着立即数小于、立即数无符号小于两种比较方案。

3.3 定义Pattern

上述四条指令只提到了小于、无符号小于两种比较方案，另外的比较方案没有定义。针对这种指令集中没有定义的比较方案需要借助Pattern定义。

指令选择过程就是DAG的模式匹配过程，模式的定义其主要在td文件中进行描述。当一个匹配找到后，将其DAG中的Node替换为具体的机器指令或伪指令。所以td文件中的Pattern的定义对于指令选择起到至关重要的作用。

每一个Pattern记录继承自 Pat class，其有两个参数，第一个参数DAG图中待匹配的模式，第二个参数是一个由机器指令组成DAG，当一个 Pattern 匹配后，将使用第二个参数替换第一个参数。以大于和大于等于为例，比较方案的模式定义如下：

  • 大于(setgt、setugt)

multiclass SetgtPatsSlt<RegisterClass RC, Instruction SLTOp, Instruction SLTuOp> {def : Pat<(setgt RC:$lhs, RC:$rhs),// a > b is equal to b < a is equal to setlt(b, a)(SLTOp RC:$rhs, RC:$lhs)>;def : Pat<(setugt RC:$lhs, RC:$rhs),(SLTuOp RC:$rhs, RC:$lhs)>;
}defm : SetgtPatsSlt<CPURegs, SLT, SLTu>;

  • 大于等于(setge、setuge)

multiclass SetgePatsSlt<RegisterClass RC, Instruction SLTOp, Instruction SLTuOp> {def : Pat<(setge RC:$lhs, RC:$rhs),// a >= b is equal to b <= a(XORi (SLTOp RC:$lhs, RC:$rhs), 1)>;def : Pat<(setuge RC:$lhs, RC:$rhs),(XORi (SLTuOp RC:$lhs, RC:$rhs), 1)>;
}defm : SetgePatsSlt<CPURegs, SLT, SLTu>;

4.测试 (以大于为例)

  • 测试用例

int test_setxx()
{int a = 5;int b = 3;int c;c = (a > b);   // sgt, c = 1return (c);
}

  • LLVM IR

%a = alloca i32, align 4%b = alloca i32, align 4%c = alloca i32, align 4store i32 5, i32* %a, align 4store i32 3, i32* %b, align 4%0 = load i32, i32* %a, align 4%1 = load i32, i32* %b, align 4%cmp = icmp sgt i32 %0, %1%conv = zext i1 %cmp to i32store i32 %conv, i32* %c, align 4%2 = load i32, i32* %c, align 4ret i32 %2
}

  • 指令选择前后的DAG

LLVM编译器后端比较功能的添加

LLVM编译器后端比较功能的添加

  • 汇编

test_setxx:.frame $fp,16,$lr.mask  0x00000000,0.set noreorder.set nomacro
# %bb.0:                                # %entryaddiu $sp, $sp, -16addiu $2, $zero, 5st $2, 12($sp)addiu $2, $zero, 3st $2, 8($sp)ld $2, 12($sp)ld $3, 8($sp)cmp $sw, $3, $2andi $2, $sw, 1st $2, 4($sp)ld $2, 4($sp)addiu $sp, $sp, 16ret $lrnop.set macro.set reorder.end test_setxx
$func_end0:.size test_setxx, ($func_end0)-test_setxx# -- End function

5.总结

LLVM编译器后端的主要工作是将LLVM中间端表达式（IR）转换成汇编文件，Cpu0 是一个非常简单的 RISC 架构处理器，本文以Cpu0作为硬件的例子，来构建能适配它的编译器后端，主要讲述了比较指令在整个控制流当中的作用并梳理了在LLVM后端中添加比较功能的过程。在编译器后端的开发过程中有一定的参考作用。可能存在认知上的偏差，也请大佬多多指教，笔者也会在学习中一步步改正错误，欢迎交流技术心得。

LLVM编译器后端比较功能的添加

参考文献

  • https://llvm.org/docs/WritingAnLLVMBackend.html

  • https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl05.html

  • https://zhuanlan.zhihu.com/p/386457923

  • https://zhuanlan.zhihu.com/p/163328574

网络标签：

相关问题