llvm后端之DAG设计

引言

llvm后端将中端的IR转为有向无环图，即DAG。如下图：

图中黑色箭头为数据依赖；蓝色线和红色线为控制依赖。蓝色表示指令序列化时两个节点中间可以插入其他节点对应的指令，而红色节点表示两个节点生成的指令中间不能插入其他节点的指令。

注：本文参考源码路径为 https://github.com/llvm/llvm-project/tree/release/10.x

1 核心类设计

DAG图是围绕SDNode、SDUse、SDValue组织，如下图：

• DAG图中每个节点，用SDNode表示。节点有依赖节点，用OperandList表示；节点可以有多个输出值，其输出值类型用ValueList表示；
• 用SDValue表示每个节点的输出值，其中记录了SDNode和输出值序号ResNo；
• SDUse表示DAG图的依赖箭头。用Val表示箭头指向的节点，即被依赖的节点输出值；用User表示箭头起点的节点，即使用节点；
• 每个SDUse设置Val时，会将自己添加到SDNode的UseList链表中。这样每个Node就可以遍历到使用自己的其他节点。

2 类型系统

llvm后端DAG的类型系统分为三个层级，从外到内为：EVT、MVT、SimpleValueType。如下图：

2.1 MVT::SimpleValueType

SimpleValueType是基本数据类型的枚举定义，其中包括：

• 整数类型
• 浮点类型
• 向量类型：其中包括按类型分类有整数向量和浮点向量，按长度分类有固定长度向量和变长向量
• 其他类型

2.2 MVT

MVT是对SimpleValueType值的封装。并提供常规的方法：

• isValid : 为整数类型、浮点类、向量类型以及x86mmx、Glue、isVoid、Untyped、exnref，则为true；
• isFloatingPoint / isInteger : 整数/浮点及其相应类型的向量为true；
• isScalarInteger : 非向量的整数类型则为true；
• isScalableVector : 变长向量则为true；
• isFixedLengthVector ：定长向量则为true；
• isOverloaded : 可重载类型，就是由内置函数可以解释的任意长度类型。有Any、iAny、vAny、fAny、iPTRAny；
• isPow2VectorType ：向量元素个数为2的N次方，则为true；
• getPow2VectorType : 返回元素个数扩展为2的N次方的新向量类型，例如16个不扩展，5个则扩展为8个；
• getHalfNumVectorElementsVT : 将向量元素个数截断为原来的一半并返回其类型；
• getScalarType : 为向量则返回元素类型，否则返回自身相同类型；
• getVectorNumElements : 返回向量元素个数，变长向量则返回最小向量元素个数；
• getSizeInBits : 返回类型的bit位数，变长向量则返回最小元素个数乘以元素类型的bit数。
• getScalarSizeInBits : 返回getScalarType类型的bit位数；
• getStoreSize : 返回类型从存储长度，即扩展为字节长度。例如1位int扩展为8位int；
• bitsGT / bitsGE / bitsLT / bitsLE : 比较MVT的getSizeInBits值；

此外，还提供了根据bit位返回类型的系列静态方法。

2.3 EVT

EVT是对MVT的封装，此外还提供了对MVT类型的扩展。当表示MVT之外的类型时，其V.SimpleTy为INVALID_SIMPLE_VALUE_TYPE。例如，当定义一个1024位的int，此时就是一个扩展类型。

3 节点类型

DAG节点的类型(也就是操作类型，对应于指令类型)是定义在llvm::ISD::NodeType枚举类型中；此外，可以基于BUILTIN_OP_END往后自定义目标的操作类型。llvm::ISD::NodeType的节点类型包括：