概述编译器前端将源代码转换为等效形式的IRIR经过优化器优化后传递到后端由代码生成器将IR 代码转换为汇编代码或目标代码在这个过程中后端首先通过指令选择器目标机器支持的指令来实现IR指令至于指令的顺序可由后续的指令调度器决定指令选择器指令选择器选择指令的基本要求是确保指令能在目标机器上实现与IR相同的功能。其次在特定的目标机器上尽量使某些指令序列在执行时比其他指令效率更高指令选择器应在条件允许下尽可能选择高效的指令序列。因此指令选择的目标可以归结为两个方面即模式匹配和模式选择模式匹配模式匹配要解决的问题是找出可以实现IR的候选指令序列这类候选指令序列通常有若干个模式选择模式选择要解决的问题是从若干个候选指令集中选出性能最好的指令序列模式选择问题可以看作一个优化问题即指令序列中每条指令的执行都有代价模式选择的目标是最小化所选指令序列的代价的总和指令选择的目标指令执行代价的度量标准多种多样可以是执行时间、占用内存大小或功耗最常见的度量标准是执行时间通过指令执行时间的最小化实现程序在目标机器上整体执行性能的最大化这里的目标机器通常是指程序编译针对的硬件平台目标机器中必须包括可以连续解释和执行机器代码的处理器目标机器的所有可用指令集合称为指令集其行为由目标机器的指令集架构(Instruction Set Architecture, ISA) 规定指令的实现方式在LLVM中有三种指令选择实现方式基于SelectionDAG的指令选择、快速指令选择和全局指令选择所有的指令选择pass 都是基于MachineFunctioinPass类在LLVM的指令选择阶段Instrcution 类表示的LLVM IR 转换为 MachineInstr实例MachineInstr类可用于表示后端所有目标相关机器指令与Instrunction类相比MachineInstr类表示的指令更接近目标平台。LLVM后端的SelectionDAGBuilder模块通过遍历LLVM IR 文件将其中的基本块转换为图形式的SelectionDAG对象构建SelectionDAG对象是指令选择的第一步。为了适应指令选择的需要SelectionDAG类以低阶数据依赖DAG的形式表示LLVM IR在此基础上可以实现目标相关优化和代码简化SelectionDAG 类的定义(代码 llvm_root/llvm/include/llvm/CodeGen/SelectionDAG.h)LLVM 后端将LLVM IR 转换为机器指令的标准方式是通过DAG实现的。即目标无关的SelectionDAG经过指令选择后转换为目标相关的、包含机器代码的新DAG利用目标描述中提供的模式IR指令通过模块匹配可转换为机器指令。为此LLVM实现了一种复杂的模式匹配算法在编译LLVM工程时会调用到TableGen工具。TableGen是LLVM 项目的重要的组成部分该工具根据.td目标描述文件中的指令定义生成模式匹配表并建立ISD(Instrunction Selection DAG) 和 ISD 与机器指令之间的映射关系以AMDGPU后端的S_NOT_B64指令定义为例def S_NOT_B64 : SOP1_64 s_not_b64, [(set i64:$sdet, (not i64: $src0))]其中[(set i64: $ sdst, (not i64: $src0))] 是S_NOT_B64指令的选择模式not 是LLVM的预定义操作符定义如下:def not: PatFrag(ops node: $in), (xor node: $in, -1)PatFrag 类也定义在TargetSelectionDAG.td 文件中其作用类似于 “%result xor i64 % a, -1” 的匹配片段(matching fragment) 替换为not 预定操作符S_NOT_B64 指令的选择模式描述了S_NOT_B64指令的功能即调用具有64位整数类型参数的not节点并返回64位整数类型的结果当指令选择器在DAG中检测到符合模式的序列时即会将其匹配到S_NOT_B64指令上述选择模式是最简单的用法。除此之外TableGen还支持多种模式类型如PatFrags、OutPatFrag等。这种模式类型定义参见TargetSelectioinDAG.td参考资料编译入门那些事儿7指令选择
指令选择原理与实现方式
概述编译器前端将源代码转换为等效形式的IRIR经过优化器优化后传递到后端由代码生成器将IR 代码转换为汇编代码或目标代码在这个过程中后端首先通过指令选择器目标机器支持的指令来实现IR指令至于指令的顺序可由后续的指令调度器决定指令选择器指令选择器选择指令的基本要求是确保指令能在目标机器上实现与IR相同的功能。其次在特定的目标机器上尽量使某些指令序列在执行时比其他指令效率更高指令选择器应在条件允许下尽可能选择高效的指令序列。因此指令选择的目标可以归结为两个方面即模式匹配和模式选择模式匹配模式匹配要解决的问题是找出可以实现IR的候选指令序列这类候选指令序列通常有若干个模式选择模式选择要解决的问题是从若干个候选指令集中选出性能最好的指令序列模式选择问题可以看作一个优化问题即指令序列中每条指令的执行都有代价模式选择的目标是最小化所选指令序列的代价的总和指令选择的目标指令执行代价的度量标准多种多样可以是执行时间、占用内存大小或功耗最常见的度量标准是执行时间通过指令执行时间的最小化实现程序在目标机器上整体执行性能的最大化这里的目标机器通常是指程序编译针对的硬件平台目标机器中必须包括可以连续解释和执行机器代码的处理器目标机器的所有可用指令集合称为指令集其行为由目标机器的指令集架构(Instruction Set Architecture, ISA) 规定指令的实现方式在LLVM中有三种指令选择实现方式基于SelectionDAG的指令选择、快速指令选择和全局指令选择所有的指令选择pass 都是基于MachineFunctioinPass类在LLVM的指令选择阶段Instrcution 类表示的LLVM IR 转换为 MachineInstr实例MachineInstr类可用于表示后端所有目标相关机器指令与Instrunction类相比MachineInstr类表示的指令更接近目标平台。LLVM后端的SelectionDAGBuilder模块通过遍历LLVM IR 文件将其中的基本块转换为图形式的SelectionDAG对象构建SelectionDAG对象是指令选择的第一步。为了适应指令选择的需要SelectionDAG类以低阶数据依赖DAG的形式表示LLVM IR在此基础上可以实现目标相关优化和代码简化SelectionDAG 类的定义(代码 llvm_root/llvm/include/llvm/CodeGen/SelectionDAG.h)LLVM 后端将LLVM IR 转换为机器指令的标准方式是通过DAG实现的。即目标无关的SelectionDAG经过指令选择后转换为目标相关的、包含机器代码的新DAG利用目标描述中提供的模式IR指令通过模块匹配可转换为机器指令。为此LLVM实现了一种复杂的模式匹配算法在编译LLVM工程时会调用到TableGen工具。TableGen是LLVM 项目的重要的组成部分该工具根据.td目标描述文件中的指令定义生成模式匹配表并建立ISD(Instrunction Selection DAG) 和 ISD 与机器指令之间的映射关系以AMDGPU后端的S_NOT_B64指令定义为例def S_NOT_B64 : SOP1_64 s_not_b64, [(set i64:$sdet, (not i64: $src0))]其中[(set i64: $ sdst, (not i64: $src0))] 是S_NOT_B64指令的选择模式not 是LLVM的预定义操作符定义如下:def not: PatFrag(ops node: $in), (xor node: $in, -1)PatFrag 类也定义在TargetSelectionDAG.td 文件中其作用类似于 “%result xor i64 % a, -1” 的匹配片段(matching fragment) 替换为not 预定操作符S_NOT_B64 指令的选择模式描述了S_NOT_B64指令的功能即调用具有64位整数类型参数的not节点并返回64位整数类型的结果当指令选择器在DAG中检测到符合模式的序列时即会将其匹配到S_NOT_B64指令上述选择模式是最简单的用法。除此之外TableGen还支持多种模式类型如PatFrags、OutPatFrag等。这种模式类型定义参见TargetSelectioinDAG.td参考资料编译入门那些事儿7指令选择
