LLVM指令选择
LLVM指令选择
Fan后端部分:
作用:负责将 LLVM IR 转换成目标代码,主要过程有指令选择,寄存器分配,指令调度。
前置知识:
SelectionDAG 节点:在编译优化阶段生成的一种抽象的数据结构,用以表示程序的计算过程,帮助优化器进行高效的指令选择和调度。
Machinelnstr:机器相关的指令格式,用于描述特定目标架构下的指令集和操作码。
MCInst:机器指令,是具体的目标代码表示,包含了特定架构下的二进制编码指令。
定义一个指令
已知
1 | let Predicates = [HasExtZpn095b] in { |
此处Sched是指令模型调度相关,可以尝试对P指令和非P指令调整Latency,需要考虑指令依赖和寄存器压力。在这里RVPBinary为一个Instruction class templates
1 | let hasSideEffects = 0, mayLoad = 0, mayStore = 0, |
我们只需要填入func7,func3,和opcodestr即可定义一个具体的Instruction。
定义intrinsic
以kabs16为例,首先可以先添加一个指令class模板,用来批量添加结构相同指令
1 | let hasSideEffects = 0, mayLoad = 0, mayStore = 0, |
hasSideEffects标记计算的表达式是否有副作用,详细可查看clang/include/clang/AST/Expr.h:635. mayLoad标记是否会读取内存,mayStore标记是否会修改内存。
1 | /// Return true if this instruction could possibly read memory. |
RVPUnary继承于RVInstR,RVInstR继承于RVInstRBase
1 | class RVInstR<bits<7> funct7, bits<3> funct3, RISCVOpcode opcode, dag outs, |
需要注意的是这里RVInstRBase给出了Bits {31-25} should be set by the subclasses.而其他encoding范围已经规定好。
1 | class RVInstRBase<bits<3> funct3, RISCVOpcode opcode, dag outs, |
0-6为RISCVOpcode,已经有llvm/lib/Target/RISCV/RISCVInstrFormats.td的133-160行def过
1 | def OPC_LOAD : RISCVOpcode<"LOAD", 0b0000011>; |
每一个RISCVOpcode含有一个name和7bit的Value
1 | class RISCVOpcode<string name, bits<7> val> { |
对应白皮书
[图片]
7-11为rd,一般是返回值的寄存器,let Inst{14-12} = funct3;这个fun3一般是三个0, let Inst{19-15} = rs1;表示输入寄存器与空间,let Inst{24-20} = rs2;表示第二个输入
不过有时Encoding format并不固定,例如bitrevi:
[图片]
就需要利用llvm/lib/Target/RISCV/RISCVInstrInfo.td的uimmlog2xlen,在32Bit下是5bit的imm空间,在64Bit下是6位imm encoding空间
1 | def uimmlog2xlen : RISCVOp, ImmLeaf<XLenVT, [{ |
写一个对应的模板类
1 | let hasSideEffects = 0, mayLoad = 0, mayStore = 0, |
(待完成)
查看class Intrinsic
1 | class Intrinsic<list<LLVMType> ret_types, |
riscv的intrinsics:
1 | let TargetPrefix = "riscv" in { |
SDPatternOperator的用途为Selection DAG Pattern Operations
1 | // Selection DAG Pattern Operations |
DAG是 LLVM CodeGen框架中的一个关键数据结构,主要用于指令选择阶段(待完成)
生成指令信息表会在编译llvm期间include进去
{ 15235,3, 1, 4, 4965, 0, 0, RISCVImpOpBase + 0, 8130, 0, 0x1ULL }, // Inst #15235 = SRL8
分别代表 指令信息表,(待完成)
对Intrinsics的类型检查:
class RVPBinaryAABIntrinsics
: Intrinsic<[llvm_anyint_ty],
[LLVMMatchType<0>, llvm_anyint_ty],
[IntrNoMem]>;
multiclass RVPBinaryAABIntrinsics {
def “int_riscv_” # NAME : RVPBinaryAABIntrinsics;
}
defm ksllw : RVPBinaryAABIntrinsics;
defm kslliw : RVPBinaryAABIntrinsics;
defm kslli8 : RVPBinaryAABIntrinsics;
defm slli16 : RVPBinaryAABIntrinsics;
DAG图的组成
LLVM使用SelectionDAG类(defined in include/llvm/CodeGen/SelectionDAG.h)表示一个架构无关的底层数据依赖图, 它将串联整个指令选择流程, 所以包含了许多成员与接口, 这里我们只截取与lowering相关的部分.
1 | class SelectionDAG { |
其中TargetLowering负责处理架构相关的lowering, FunctionLoweringInfo负责处理函数调用约定, 这两个成员后面会介绍. EntryNode与Root分别指向图的入口节点与根节点, 通过根节点即可遍历整个图
lowering的目的是将IR的数据结构转换为DAG, 方便之后指令选择做模式匹配. lowering的过程就是DAG建立的过程。
待讲解
clang/lib/CodeGen/CGBuiltin.cpp
llvm/include/llvm/IR/IntrinsicsRISCV.td
llvm/lib/Target/RISCV/RISCVInstrInfo/RISCVInstrInfoP/RISCVInstrInfoP.td
llvm/lib/Target/RISCV/RISCVISelLowering.cpp
指令选择:
作用:LLVM IR 转换为目标特定的 SelectionDAG 节点,生成目标机器代码的指令序列。
有GlobalISel和SelectionDAG两种框架,目前都是SelectionDAG,SelectionDAGISel是核心类
主要动作:
指令选择,寄存器分配,指令调度,Machine Code Generation,Backend Optimizations
例如定义了一个__builtin_riscv_kabs32并加入feature限制
1 | let Features = "64bit,(zp095b|zp054b|zp053b|zp052b)" in { |
注意,prototype是返回原型,features才是要匹配的输入
intrinsic再到ISDNode再到指令
1 | class RVInstR<bits<7> funct7, bits<3> funct3, RISCVOpcode opcode, dag outs, |
指令选择
第一阶段是以LLVM IR作为输入创建DAG(有向无环图)
1 | let Predicates = [HasExtZpn095b] in { |
目前有问题的指令:
KSLLIW
思路:能正常生成ir,并且ksllw的32和64能正常生成,kslliw的64位不可以
kslliw SDNode之前出了问题,可能是intrinsic格式问题
猜测是llvm/lib/Target/RISCV/RISCVISelLowering.cpp的返回类型合法化问题
Don’t know how to custom type legalize this intrinsic!
1 | (lldb) breakpoint list |
结论:白皮书发生变动,定义修改,按照054版本来
sub64:
报错为:
1 | $CLANG -march=rv32gc_xxldsp -mabi=ilp32d -O2 -c test.c -S -o - |
按照ksub64同类型解决
其他:
有isdnode的,检查lowering过程,检查模式匹配指令是否正确,打印ir查看
调试手段:
前端未定义
1.
查看对应.inc文件,对照白皮书
2.
3.
error in backend: Cannot select
4.
1 | 打断点 |
Intrinsic: llvm.riscv.kslliw
Result VT: i32
Operands: (i32, i32)
Target: RV64
1.
参数
2.
–debug-only=isel
1.
打印出records结果
2.
1 | llvm-tblgen -I llvm/include \ |
以 KSLL32为例:
1 | def KSLL32 { // InstructionEncoding Instruction RVInstCommon RVInst RVInstRBase RVInstR RVPBinary Sched |
参考:
https://llvm.org/docs/TableGen/
https://llvm.gnu.ac.cn/docs/UserGuides.html
https://llvm.gnu.ac.cn/docs/RemoveDIsDebugInfo.html
https://blog.chiphub.top/2024/05/21/llvm-learning-define-intrinsics-1/
https://zhuanlan.zhihu.com/p/447318642
How to write a TableGen backend:
https://www.youtube.com/watch?v=UP-LBRbvI_U
lowering的过程
https://www.cnblogs.com/Five100Miles/p/12824942.html