做的网站百度搜索不出来,WordPress分段插件,360浏览器打开是2345网址导航,销售平台系统llvm后端之指令选择源码分析 引言1 主要流程1.1 参数降级1.2 构建DAG1.3 类型合法化1.4 向量合法化1.5 DAG合法化1.6 DAG合并 2 目标实现2.1 TargetLowering2.2 SelectionDAGISel 引言
llvm后端指令选择主要是class SelectionDAGISel的子类实现。整个过程将llvm IR转为有向无环… llvm后端之指令选择源码分析 引言1 主要流程1.1 参数降级1.2 构建DAG1.3 类型合法化1.4 向量合法化1.5 DAG合法化1.6 DAG合并 2 目标实现2.1 TargetLowering2.2 SelectionDAGISel 引言
llvm后端指令选择主要是class SelectionDAGISel的子类实现。整个过程将llvm IR转为有向无环图节点通过系列替换合并最终生成目标相关的DAG。最后再将目标DAG通过td规则匹配成目标指令MachineInstr。
llvm后端支持三种指令选择
SelectionDagISel SDAG指令选择FastISel 快速指令选择GlobalISel 全局指令选择
注本文重点介绍SDAG实现参考源码路径为 https://github.com/llvm/llvm-project/tree/release/10.x
1 主要流程
1.1 参数降级
参数降级由SelectionDAGISel::LowerArguments(const Function F)实现。其主要过程如下
首先构建TargetLowering::LowerFormalArguments方法的Ins参数调用由TargetLowering子类重写的LowerFormalArguments方法将Ins参数中打散成寄存器粒度的节点合并为参数分拆类型节点由ISD::BUILD_PAIR节点合并
构建Ins参数
当函数不能降级return则会插入一个存返回地址的额外参数。对于每个参数通过ComputeValueVTs函数计算每个参数的IR类型转换后的EVT类型再对每个EVT类型通过TargetLowering子类可重写的getRegisterTypeForCallingConv和getNumRegistersForCallingConv方法计算分配的需要分配的寄存器类型和个数并构建ISD::InputArg放入Ins参数中
注1 ComputeValueVTs是根据IR阶段的Type类型生成EVT类型过程中会对结构体和数组展开为基本类型所以是一对多生成EVT类型 注2 getRegisterTypeForCallingConv和getNumRegistersForCallingConv是TargetLowering子类可重写方法用于计算每个参数需要寄存器类型和个数。每个基本类型占用一个或多个寄存器。
调用LowerFormalArguments方法
该方法由TargetLowering子类重写用于计算参数拆分到寄存器粒度后对应的SDValue节点以RISCV为例其实现主要是借助class CCState实现参数寄存器分配或参数栈分配
注一般地在参数寄存器还可以分配的时候会优先使用CCState::AllocateReg分配参数寄存器否则才会通过CCState::AllocateStack分配栈空间。
合并参数寄存器
对LowerFormalArguments返回的SDValue节点通过ISD::BUILD_PAIR合并成更大类型也就是ComputeValueVTs分拆的EVT类型然后通过ISD::MERGE_VALUES将ComputeValueVTs分拆的EVT类型以参数为粒度合并为一个节点
1.2 构建DAG
在对于每个基本块执行SelectionDAGISel::SelectBasicBlock方法在该方法内对每个指令调用SelectionDAGBuilder::visit构建DAG。其主要流程如下
如果IR指令是终结指令通过SelectionDAGBuilder::HandlePHINodesInSuccessorBlocks对后继节点使用该基本块为输入值的PHI指令转为寄存器拷贝通过SelectionDAGBuilder::visit(unsigned Opcode, const User I)方法对指令进行生成DAG操作该方法通过switch将不同的IR指令XXInst转为调用visitXXInst方法。例如CallBrInst则调用SelectionDAGBuilder::visitCallBr方法最后对一些特殊的IR指令做一些后处理。
处理每个PHI后继节点
对每个后继节点使用了该基本块作为输入的PHI指令取其为PHI单独分配的寄存器记录PHI替换指令与对应拆分的源寄存器号的对应关系。
注1为PHI指令分配寄存器是在SelectionDAGISel::runOnMachineFunction调用FuncInfo-set方法完成的。在该方法内部会FunctionLoweringInfo的InitializeRegForValue为PHI指令分配目的寄存器最后再调用BuildMI创建一个目标的PHI指令并将目的寄存器添加进去。 注2 PHI指令的源寄存器是在SelectionDAGISel::FinishBasicBlock方法中通过建立的映射关系添加的。
AllocaInst转DAG
首先通过指令的数组维度乘以类型大小最后加上对其长度最后通过生成ISD::DYNAMIC_STACKALLOC节点即栈分配节点
ReturnInst转DAG CallInst转DAG
1.3 类型合法化
类型合法化是在DAGTypeLegalizer::run中完成的它在向量合法化前后都会执行。主要有如下步骤
初始化Worklist将叶子节点加入并setNodeId为ReadyToProcess即0; 非叶子节点设置为Unanalyzed即-2然后进入while循环处理Worklist中的节点在while开始处于是先合法化节点输出类型跳转到NodeDone处理在NodeDone段中将处理节点的使用节点的NodeId设置为操作数个数减1最后等所有操作数的输出值都合法化后便将其加入到Worklist中最后回到while开始处继续大多数节点不需要处理操作数因为操作数依赖的节点输出类型已经先行类型合法化。对于一些特殊节点(例如输出本身合法、没有输出值、register/TargetConstant节点)则会进入ScanOperands段对操作数类型合法化
注整个类型合法化依赖TargetLoweringBase::computeRegisterProperties初始化设置
TargetLowering::TypePromoteInteger
该枚举会将int类型上提到合法的长度类型处理输出值合法化时通过DAGTypeLegalizer::PromotedIntegers成员记录原输出SDValue与转换后的输出SDValue的映射后续节点合法化时通过前面的映射找到转换后的SDValue替换
TargetLowering::TypeExpandInteger
该枚举会将不支持的过长int类型分拆为两个更小的长度类型处理输出值合法化时通过DAGTypeLegalizer::ExpandedIntegers成员记录原输出SDValue与转换后的两个分拆输出SDValue的映射后续节点合法化时通过前面的映射找到转换后的SDValue进行替换
注TypeExpandInteger与TypePromoteInteger不同的时经过一次TypeExpandInteger可能还不是合法类型
TargetLowering::TypeSoftenFloat
该枚举是当硬件不支持某类型浮点运算时先将其转同长度int然后由软件实现模拟浮点运算。即调用软件实现的libcall处理输出值合法化时通过DAGTypeLegalizer::SoftenedFloats成员记录原输出SDValue与转换后输出的SDValue的映射后续节点合法化时通过前面的映射找到转换后的SDValue进行替换
TargetLowering::TypeExpandFloat
该枚举是将较大类型拆分为两个较短类型与TypeSoftenFloat一样两个较短类型的运算也是由软件模拟实现处理输出值合法化时通过DAGTypeLegalizer::ExpandedFloats成员记录原输出SDValue与转换后的两个分拆节点SDValue的映射后续节点合法化时通过前面的映射找到转换后的SDValue进行替换
TargetLowering::TypePromoteFloat
该枚举将较小的不合法浮点类型上提到较大的浮点类型它只是进行类型转换不会软件模拟处理输出值合法化时通过DAGTypeLegalizer::PromotedFloats成员记录原输出SDValue与转换后输出SDValue的映射后续节点合法化时通过前面的映射找到转换后的SDValue进行替换
TargetLowering::TypeScalarizeVector
该枚举是当向量只有一个元素时直接使用元素类型操作它通过DAGTypeLegalizer::ScalarizedVectors记录转换映射
TargetLowering::TypeSplitVector
该枚举是将一个较长向量拆分为两个维度较短向量它通过DAGTypeLegalizer::SplitVectors记录转换映射
TargetLowering::TypeWidenVector
该枚举将一个较短向量扩展为维度较大的向量。扩展的元素用undef初始化通过ISD::CONCAT_VECTORS合并为一个较大向量它通过DAGTypeLegalizer::WidenedVectors记录转换映射
1.4 向量合法化
类型合法化是在VectorLegalizer::Run中完成的在Run中如果DAG中至少有一个节点使用了向量类型则会对每个DAG节点调用VectorLegalizer::LegalizeOp。LegalizeOp方法的主要有如下步骤
当节点已经合法化后则直接返回VectorLegalizer::LegalizedNodes成员缓存的合法化后的节点。否则继续递归调用LegalizeOp对节点的操作数合法化并通过DAG.UpdateNodeOperands替换掉当前节点的操作数。后续处理节点输出值转换对load和store节点做特别处理。如果load节点是向量类型且为扩展load类型、或store节点是向量类型且是截断存储则会根据TargetLowering::getLoadExtAction返回值作不同处理(Custom则会调用TargetLowering子类重写的LowerOperation方法、Expand则会调用VectorLegalizer::ExpandLoad/ExpandStore)对于其他节点类型只要操作数或输出值类型只要有一个向量类型则进行通用处理。通用节点处理共分为三步 通过TargetLowering::getOperationAction获取节点的action(有些是根据输出值有些是根据输入值) 根据action作不同的处理为Promote枚举调用VectorLegalizer::Promote方法、为Custom枚举调用TargetLowering子类重写的LowerOperation方法、为Expand枚举调用VectorLegalizer::Expand方法 在VectorLegalizer::LegalizedNodes成员中建立节点的输出值到转换后的输出节点的映射缓存(如果没有转换则缓存当前节点)。
注整个向量合法化依赖TargetLowering::setOperationAction和TargetLowering::setLoadExtAction初始化设置
VectorLegalizer::ExpandLoad
对于Load的内存源类型是字节对齐(存储对齐)的、或其向量长度为1则会通过TargetLowering::scalarizeVectorLoad处理Load节点。它会将对向量的Load分拆为单个元素的Load并通过ISD::BUILD_VECTOR将Load值合并为一个向量对于Load的内存源类型不是字节对齐的、且其向量长度大于1则会分拆为目标指针类型大小Load(不够分拆则按幂退大小)然后经过系列位操作组合元素最后再将元素通过ISD::BUILD_VECTOR合并为一个向量
VectorLegalizer::ExpandStore
通过TargetLowering::scalarizeVectorStore处理如果store节点的内存类型不是字节对齐的则将每个向量元素截断为单个元素内存类型再零扩展为与整个向量内存类型等bit长度的int类型然后通过移位和ISD::OR合并为一个值最后生成新的store节点存储合并的值如果store节点的内存类型是字节对齐的则对每个元素截断存储为单个元素的内存类型最后通过ISD::TokenFactor组合为一个节点。
VectorLegalizer::Promote
除了少数节点需要单独处理大多数节点根据TargetLowering::getTypeToPromoteTo获取节点输出值的上提类型然后重新生成相关操作节点最后通过ISD::BITCAST或ISD::FP_ROUND上提前的原类型
VectorLegalizer::Expand
一部分节点需要单独处理例如ISD::MERGE_VALUES将合并的值分拆返回便是其他节点则通过SelectionDAG::UnrollVectorOp展开向量本质上对向量的操作展开为相应位置的元素操作最后再通过ISD::BUILD_VECTOR合并成一个向量。
1.5 DAG合法化
DAG合法化是最后一个合法化阶段它在SelectionDAG::Legalize中完成它会不断通过SelectionDAGLegalize::LegalizeOp对每个节点合法化直到所有节点都不再需要合法化结束。SelectionDAGLegalize::LegalizeOp的主要流程如下
在LegalizeOp中同样会对Load和Store单独处理会分别调用SelectionDAGLegalize::LegalizeLoadOps / LegalizeStoreOps进行处理对其他节点先通过TargetLowering::getOperationAction获取LegalizeAction再通过action不同做不同处理 为Legal不处理 为Custom调用TargetLowering子类重写的LowerOperation方法 为Promote则调用SelectionDAGLegalize::PromoteNode处理 为Expand则调用SelectionDAGLegalize::ExpandNode处理 为LibCall则调用SelectionDAGLegalize::ConvertNodeToLibcall处理
SelectionDAGLegalize::LegalizeLoadOps
对于非扩展的Load节点根据输出值类型调用TargetLowering::getOperationAction根据返回值不同处理不同。对于扩展的Load节点如果内存源类型没有字节对齐且内存源类型不为MVT::i1或i1的getLoadExtAction返回为Promote行为则将内存源类型上提到字节对齐类型生成新扩展Load最后按未上提的内存源类型扩展输出值。 后续则是内存源类型字节对齐、或内存源类型为MVT::i1且i1的getLoadExtAction不为Promote行为对于扩展的Load节点如果内存源类型位宽为2的幂次方则根据大小端分拆为两个扩展Load最后再通过移位操作合并为大类型对于扩展的Load节点如果内存源类型位宽不是2的幂次方(隐含条件字节对齐)调用TargetLowering::getLoadExtAction根据返回值不同处理方式不同
注TargetLowering::expandUnalignedLoad用于处理不支持对齐的Load。对浮点或向量的不合法内存源类型会拆分为寄存器类型粒度分别从栈上load对于其他类型例如int拆分为两个更小的长度类型load再通过位操作合并为一个节点
SelectionDAGLegalize::LegalizeStoreOps
非截断store节点根据待存储值类型调用TargetLowering::getOperationAction根据返回值不同处理不同。截断store节点如果内存类型为非字节对齐则将内存类型上提到字节对齐类型同时对存储值超过的位截断为0再重新生成新截断store节点截断store节点如果内存类型字节对齐且位宽为2的幂次方则根据大小端分拆为两个较小类型存储最后通过ISD::TokenFactor合并为一个节点截断store节点如果内存类型字节对齐但位宽不是2的幂次方根据内存类型调用TargetLowering::getTruncStoreAction根据返回值不同处理方式不同
SelectionDAGLegalize::PromoteNode
根据节点第0个输出类型获取上提类型特别地一些特殊节点是根据操作数的类型获取上提类型根据节点类型不同作不同处理以ISD::MUL为例对操作数全部扩展为上提类型再对输出值截断为上提前的类型最后通过ReplaceNode函数将引用原节点的use关系替换为Results(此外还会将新节点添加到更新列表)一般Results个数为1
SelectionDAGLegalize::ExpandNode
根据节点类型不同作不同处理以ISD::MERGE_VALUES为例直接将合并的值取出来放到Results中最后通过ReplaceNode函数将引用原节点的use关系替换为Results(此外还会将新节点添加到更新列表)。其内部实现是调用SelectionDAG::ReplaceAllUsesWith实现的Results数组代表的是每个原节点的输出值
SelectionDAGLegalize::ConvertNodeToLibcall
根据节点类型不同调用不同的Libcall转换并将节点加入到Results列表最后与PromoteNode和ExpandNode一样通过ReplaceNode替换原节点的输出值
1.6 DAG合并
从构建DAG开始每个阶段完成后都要进行一次DAG合并通过调用DAGCombiner::Run实现DAG合并。其主要流程如下
首先将所有节点加入Worklist中然后进入while循环处理如果当前节点没有被引用则通过recursivelyDeleteUnusedNodes函数向上检索并删除没有使用的节点(其实前面的几个阶段也有无用节点的删除)如果AtLevel大于等于阶段AfterLegalizeDAG(即合法化DAG之后)则再次通过SelectionDAGLegalize::LegalizeOp对当前节点进行DAG合法化并将全部新转换的节点添加到Worklist中将当前节点加入CombinedNodes缓存中并把当前节点的每个还没加入到CombinedNodes缓存的操作数节点加入到Worklist中最后调用DAGCombiner::combine执行真正的节点合并如果DAG合并后返回的节点发生了变化(即不等于合并前的节点)将引用原节点的引用关系替换为引用新节点并将新节点和引用它的节点添加到Worklist通过recursivelyDeleteUnusedNodes从原节点向上检索并删除没有使用的节点然后继续下一轮循环
函数DAGCombiner::combine实现真正的DAG合并主要流程如下
首先调用DAGCombiner::visit执行标准合并会根据节点类型不同作不同的合并策略如果visit后没有返回新节点(即没有合并处理)、且原节点的操作类型为自定义类型或TargetLowering::hasTargetDAGCombine返回目标可以合并则调用TargetLowering子类重写的PerformDAGCombine方法如果至此还没有合并处理则对特定节点类型执行合并操作。具体由DAGCombiner的四个方法处理PromoteIntBinOp、PromoteIntShiftOp、PromoteExtend、PromoteLoad如果至此还没有合并处理、且TargetLowering可重写的isCommutativeBinOp方法返回该节点是可以交换的操作(例如加法可交换、减法不可交换)、且原节点输出值个数为1那么对于两个操作数不同、且第0个操作数是常量或第1个不是常量那么就试图从缓存中找到交换两个操作数后的节点返回。这种替换的隐含条件是llvm除了load/store外都是ssa形式
DAGCombiner::visit
在visit中根据不同节点操作类型调用不同函数以ISD::ADD为例它会操作尽量合并或者说折叠例如a 3 6 - a 9、add x, undef - undef、(add Z, C sub C, Z - Z等
调用PerformDAGCombine方法
该方法由TargetLowering子类重写实现目标平台对节点的特殊合并处理以RISCV处理RISCVISD::SplitF64为例 当节点第0个操作数为RISCVISD::BuildPairF64直接调用DCI.CombineTo将BuildPairF64节点的两个操作数替换SplitF64节点 当节点第0个操作数为ConstantFPSDNode将浮点类型转int再拆分为两个32位int常量最后调用DCI.CombineTo将两个32位常量替换当前SplitF64节点 如果节点第0个操作数节点的类型为ISD::FNEG、且该节点只有当前SplitF64节点一个引用则先新生成输出int32类型的SplitF64然后取出两个输出值(第0个对应f64低字节部分、第1个对应f64高字节部分), 再通过APInt::getSignMask取出32位符号数置1、其余位置0的整数SignBit并且将SignBit与f64高字节部分通过ISD::XOR节点将符号位取反、其余位保持不变最后将f64低字节部分和符号位取反的高字节部分替换原节点 如果节点第0个操作数节点的类型为ISD::FABS、且该节点只有当前SplitF64节点一个引用与FNEG类似操作只是转换逻辑不一样
注DCI.CombineTo最终调用DAGCombiner::CombineTo内部会用新节点引用替换旧节点引用。并将新引用节点及其使用者节点添加到DAGCombiner::Worklist成员中
DAGCombiner::PromoteIntBinOp
如果当前阶段是在向量合法化之前(即AtLevel AfterLegalizeVectorOps)则不合并处理如果当前节点输出值为向量类型或非int类型则不合并处理通过调用TargetLowering子类可重写的isTypeDesirableForOp得出平台可以支持该节点对应的输出类型则不合并处理通过调用TargetLowering子类可重写的IsDesirableToPromoteOp得出平台希望对该节点的输出该类型上提则进行如下处理 将该节点两个操作数上提为输出类型的上提类型 用两个操作数重新生成该节点并通过ISD::TRUNCATE截断为上提前的输出类型 把旧节点操作数节点和新节点加入到DAGCombiner::Worklist中 同时从DAGCombiner::Worklist种移除旧节点
DAGCombiner::PromoteIntShiftOp
如果当前阶段是在向量合法化之前(即AtLevel AfterLegalizeVectorOps)则不合并处理如果当前节点输出值为向量类型或非int类型则不合并处理通过调用TargetLowering子类可重写的isTypeDesirableForOp得出平台可以支持该节点对应的输出类型则不合并处理通过调用TargetLowering子类可重写的IsDesirableToPromoteOp得出平台希望对该节点的输出该类型上提则进行如下处理 将该节点第0个操作数(移位操作的值)上提为输出类型的上提类型 重新生成移位操作节点并通过ISD::TRUNCATE截断为上提前的输出类型 把旧节点操作数节点和新节点加入到DAGCombiner::Worklist中 同时从DAGCombiner::Worklist种移除旧节点
DAGCombiner::PromoteExtend
如果当前阶段是在向量合法化之前(即AtLevel AfterLegalizeVectorOps)则不合并处理如果当前节点输出值为向量类型或非int类型则不合并处理通过调用TargetLowering子类可重写的isTypeDesirableForOp得出平台可以支持该节点对应的输出类型则不合并处理通过调用TargetLowering子类可重写的IsDesirableToPromoteOp得出平台希望对该节点的输出该类型上提则进行如下处理折叠多次扩展为一次扩展(不过llvm 10中该处应该有BUG代码与注释不一致)
DAGCombiner::PromoteLoad
如果当前阶段是在向量合法化之前(即AtLevel AfterLegalizeVectorOps)则不合并处理与前几个Promote不同的是PromoteLoad还不会处理地址索引模式MemIndexedMode不为UNINDEXED的Load节点如果当前节点输出值为向量类型或非int类型则不合并处理通过调用TargetLowering子类可重写的isTypeDesirableForOp得出平台可以支持该节点对应的输出类型则不合并处理通过调用TargetLowering子类可重写的IsDesirableToPromoteOp得出平台希望对该节点的输出该类型上提则进行如下处理 用上提类型重新生成ExtLoad再截断为原类型 用新生成的节点输出值替换旧节点的被引用关系 把旧节点操作数节点和新节点加入到DAGCombiner::Worklist中 同时从DAGCombiner::Worklist种移除旧节点
2 目标实现
实现SDAG指令选择
实现TargetLowering子类将其实例化注册到Subtarget的子类中通过重写的getTargetLowering方法返回TargetLowering引用。重点是实现TargetLowering子类实现SelectionDAGISel子类先实现TargetPassConfig子类并重写addInstSelector方法在addInstSelector中添加SelectionDAGISel子类实现。
实现快速指令选择
实现全局指令选择
2.1 TargetLowering
2.2 SelectionDAGISel
