指令选择(instruction selection)是将中间语言转换成汇编或机器代码的过程。在LLVM后端中具体表现为模式匹配，目标指令选择阶段会把后端td文件里面的DAG模式和selection DAG的节点相匹配，如果找到一个匹配，则匹配的节点会被有具体机器指令（或者伪指令）的节点代替。

1. LLVM IR基本概念

LLVM IR是一门中间语言，向上承接C、JAVA等高级语言，向下可以被翻译成面向具体目标的汇编语言，在编译器中的位置如下图所示。其一个主要优点是LLVM项目已经构建了多种针对LLVM IR的优化方法，因此很多高级语言在转换为LLVM IR后可以使用现有的基础设施进行优化。

• 前端：将程序源代码转换为LLVM IR的编译器步骤，包括词法分析器、语法分析器、语义分析器、LLVM IR生成器。Clang执行了所有与前端相关的步骤，并提供了一个插件接口和一个单独的静态分析工具来进行更深入的分析

• 中间表示：LLVM IR可以以可读文本代码和二进制代码两种形式呈现。LLVM库中提供了对IR进行构造、组装和拆卸的接口。LLVM优化器也在IR上进行操作，并在IR上进行了大部分优化。

• 后端：负责汇编码或机器码生成的步骤，将LLVM IR转换为特定机器架构的汇编代码或而二进制代码，包括寄存器分配、循环转换、窥视孔优化器、特定机器架构的优化和转换等步骤。

编译器的三段式设计

根据上文所述，可以看出支持一种新的编程语言只需重新实现一个前端，支持一种新的目标架构只需重新实现一个后端，前端和后端连接枢纽就是LLVM IR。下面将主要介绍LLVM IR的基础表达指令：

• 终结指令 Terminator Instructions

  • ret指令函数返回指令，对应C/C++中的return。
  • br指令，br是“分支”的英文branch的缩写，分为非条件分支和条件分支，对应C/C++的if语句无条件分支类似有x86汇编中的jmp指令，条件分支类似于x86汇编中的jnz，je等条件跳转指令

• 比较指令

  • icmp指令，整数或指针的比较指令，条件cond可以是eq（相等），ne（不相等），ugt（无符号相等）
  • fcmp指令，浮点数的比较指令，条件cond可以是oeq（ordered and equal），ueq（unordered or equal）
  • switch指令，分支指令，可看做是br指令的升级版，支持的分支更多，但使用也更复杂，对应C/C++中的switch

• 二元运算

  • add指令
  • sub指令
  • mul指令
  • udiv指令，无符号整数除法指令
  • sdiv指令，有符号整数除法指令
  • urem指令，无符号整数取余指令
  • srem指令，有符号整数取余指令

• 按位二元运算

  • shl指令，整数左移操作指令
  • lshr指令，整数右移指令
  • ashr指令，整数算数右移指令
  • and指令，整数按位与运算指令
  • or指令，整数按位或运算指令
  • xor指令，整数按位异或运算指令

• 内存访问和寻址操作

  • alloca指令，内存分配指令，在栈中分配一块空间并获得指向该空间的指针，类似与C/C++中的malloc函数
  • store指令，内存存储指令，向指针指向的内存中存储数据，类似与C/C++中的指针引用后的赋值操作
  • load指令， 内存加载指令，从内存中读取数值

• 数据类型转换操作

  • trunc..to指令，截断指令，将一种类型的变量截断为另一种类型的变量。
  • zext..to指令，零扩展指令，将一种类型的变量拓展为另一种类型的变量，高位补0。
  • sext..to指令，符号位拓展指令，通过复制符号位（最高位）将一种类型的变量拓展为另一种类型的变量

• 其他操作 Other Operations

  • phi指令，由静态单赋值引起的问题
  • select指令，? : 三元运算符
  • call指令，call指令用来调用某个函数，对应C/C++中的函数调用，与x86汇编中的call指令类似
  • intrinsic函数，非标准函数操作，例如abs、min、max、sqrt等

从LLVM IR的指令可以看出，其表达抽象程度比汇编语言要高，例如add二元加法运算，所有的i8、i16、i32的加法都要用其进行表示，甚至vector的加法也要使用该运算符表示，因此具有一定抽象能力。但是要想运行到目标硬件需要将LLVM IR转换为基于目标的汇编指令，该过程主要有LLVM的后端完成，一个主要工作就是进行指令选择，为抽象的LLVM运算符、内存操作符等选择对应的目标硬件指令，其主要依赖于DAG图的模式匹配技术。

2. 指令选择的总体流程

指令选择的输入是LLVM IR，输出是使用无限寄存器组的指令序列，整个过程可以如下几个阶段：

1. 创建初始化DAG
2. 优化
3. 合法化Types
4. 优化
5. 合法化Operations
6. 优化
7. 指令选择
8. 调度并格式化

本文将以一个简单的示例解释整个指令选择的过程，此函数的C程序如下，其实现了一个无符号的64-bit参数x和32-bit的参数y的乘积，返回值以32-bit无符号整形返回。

unsigned int MUL(unsigned long long int x, unsigned int y)
{
    return x * y;
}

 2.1 创建DAG

指令选择的第一阶段是以LLVM IR作为输入创建DAG(有向无环图)，后序的每个阶段都是对这个DAG进行处理，指导发射称为指令序列。上述C程序对应的LLVM IR表示如下，可由Clang工具生成IR表示。

define dso_local i32 @MUL(i64 %x, i32 %y) local_unnamed_addr #0 {
entry:
  %0 = trunc i64 %x to i32
  %conv1 = mul i32 %0, %y
  ret i32 %conv1
}

一个Selection DAG表示一个basic block，每个basic block是一个没有分支的指令连续指令序列。上述MUl函数只有一个entry block,但是一般函数可能具有多个basic block，下面的hello函数则具有4个basic block：entry、if.then、if.else、return四个基本块，将每个基本块分别创建一个DAG。

define dso_local i32 @hello(i32 %x) local_unnamed_addr #0 {
entry:
  %cmp = icmp eq i32 %x, 100
  br i1 %cmp, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  %call = tail call i32 bitcast (i32 (...)* @hello100 to i32 (i32)*)(i32 100) #2
  br label %return

if.else:                                          ; preds = %entry
  %call1 = tail call i32 bitcast (i32 (...)* @helloOther to i32 (i32)*)(i32 %x) #2
  br label %return

return:                                           ; preds = %if.else, %if.then
  %retval.0 = phi i32 [ %call, %if.then ], [ %call1, %if.else ]
  ret i32 %retval.0
}

SelectionDAG 简单理解：

• 每个node 代表一个SDNode实例表示一个操作，例如add、sub等
• 每个node有一个或多个输入操作数，每个输入是一个SDvalue实例，其由每个节点的出边表示，定义了使用的输入数据来自哪个节点。
• 每个节点的输出值，具有一个数据类型,例如 i1、i8
• chain value既是一个输入数据也是一个输出数据，其类型为MTV::Other 一般load、return等具有副作用的节点上有该值，其保证在chain上各个节点的指令先后顺序
• ISD::EntryToken作为入口节点
• 根节点一般是最后一个具有副作用的并且有chain操作数的节点

下面就是MUL函数的初始化SelectionDAG:

初始化DAG

 

2.2 优化

在指令选择过程中共有3次优化，第一次优化是在创建初始化DAG后，其余两次在合法化后，优化的目的主要是简化复杂的SelectionDAG。下图是第一次优化的结果，其变化是使用t13节点替代了t3和t4,优化器将64-bit数据的高32位删除，因为函数中乘法只要求返回32-bit整数，因此可以删除t3和t4。LLVM的第一次优化过程中只优化于目标独立的算子，例如add、sub、load等。LLVM后端开发者可以通过复写 PerformDAGCombine函数实现依赖于自定义目标的优化。

第一阶段优化

2.3 合法化 Types 和 Operations

完成第一阶段优化后，可以看到t7节点产生64-bit的结果，但是后端RISCW目标硬件只支持32-bit数据，本阶段将解决这个问题。首先进行Types合法化，将所有的数据转化为目标机器支持的数据类型，一般需要进行数据的转换、提升、扩展，例如将i1->i32，i64->i32。下图中的DAG就是合法的，将t3和t7删除将保证DAG使用i32整数。

合法化DAG

 

Operations合法化在第二次优化后，将DAG中的operations转换为目标支持的操作，例如DAG中有 rotl node 但是目标指令集中不支持，因此可以将其转换为bit shift 和 or两个操作进行。有3种方法进行是opertions合法化。第一种方法，complier将其展开为支持的操作。第二种可以将其数据类型进行提升。第三种通过手写C++编码定制器合法化过程。

2.5 指令选择

在指令选择前，大多数DAG的node是目标无关的operations，例如add、sub，同时也会有依赖于目标的操作节点例如RISCWISD::Ret，所以我们需要将这些抽象的节点映射到具体的依赖于目标机器的指令，LLVM中在指令选择阶段实现。其主要思想也比较简单，就是通过模式将node匹配到机器指令。指令的描述和模式由 LLVM 后端开发者进行编写，主要使用TableGen语法在td文件中进行描述。同时复杂的模式也可以通过直接C++编码实现。下图是指令选择完成后的DAG图，可以看出t9使用MUL代替了原来的mul,t12节点使用PseudoRET代替了RISCWISD::Ret。

指令选择完DAG 

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

每一个 Pattern 记录继承子 Pat class，其有两个参数，第一个参数DAG图中待匹配的模式，第二个参数是一个由机器指令组成DAG,当一个 Pattern 匹配后，将使用第二个参数替换第一个参数。示例如下：

class PatGprGpr<SDPatternOperator OpNode, RWInst Inst>
    : Pat<(OpNode GPR:$rs1, GPR:$rs2), (Inst GPR:$rs1, GPR:$rs2)>;
class PatGprSimm12<SDPatternOperator OpNode, RWInstI Inst>
    : Pat<(OpNode GPR:$rs1, simm12:$imm12), (Inst GPR:$rs1, simm12:$imm12)>;

PatGprGpr用于替换两个通用寄存器操作数的指令，Pattern定义方法如下,其中add为llvm ir中操作， ADD为依赖于机器的指令操作。

def : PatGprGpr<add, ADD>;

PatGprSimm12 替换一个操作数为通用寄存器,另一个操作数为立即数的指令。其中simm12是一个用于匹配12bit立即数的模式。

def : PatGprSimm12<add, ADDI>;

2.6 调度和格式化

在这个阶段是将指令选择完成的DAG转化为指令序列，该过程中可以设置符合目标硬件的调度策略。如下是MUL函数的指令序列，在此序列中仍然是使用虚拟寄存器表示，后续会有寄存器分配阶段来完成，下面序列中有部分寄存器活性信息。

bb.0.entry:
  liveins: $x0, $x2
  %2:gpr = COPY $x2
  %0:gpr = COPY $x0
  %3:gpr = MUL %0:gpr, %2:gpr
  $x0 = COPY %3:gpr
  PseudoRET implicit $x0

3 总结

上文主要讲述了LLVM IR的语法基础及将IR的抽象表达指令转换到底层的汇编指令。LLVM IR作为编译器的中间组件，起到了承上启下的作用，给上层开发新语言提供了接口，也给下层支持新硬件提供了开发框架,同时LLVM提供了多种优化模块及数据分析模块帮助编译器开发者实现优化，极大的降低了编译器开发的门槛。同时文中也详细阐述了LLVM指令的选择过程，展示如何将ISD的SDNode转换为汇编指令操作，帮助编译器开发者理解LLVM后端的工作机制，以方便开发者添加自己的芯片后端。

在AI芯片行业蓬勃发展的当下，不但要求有高水准的芯片设计能力和高水平的芯片制造能力，同时也需要更强的软件能力，拥有一个优化水平高的编译器是一款成功芯片的关键，它可以在相同成本的情况获得更快更好的AI服务，因此编译器的研究在当前的芯片行业变得尤为重要。

参考文献

• https://sourcecodeartisan.com/2020/11/17/llvm-backend-4.html
• https://www.cnblogs.com/Five100Miles/p/12822190.html
• https://llvm.org/docs/LangRef.html#abstract
• https://apsarasx.com/docs/llvm-tutorials