ADT提供了的顺序和std一样包括连续内存管理的容器以及链表形式的容器。

顺序容器-连续内存

连续内存主要包括：SmallVector、Arrayref、TinyPtrVecotr。其中SmallVector和ArrayRef是最常用的数据类型。

SmallVector

这是ADT对标std::vector提供的容器，它的接口和std::vector也非常类似，一般来说它的性能优于std::vector，主要原因是smallvector在实现时进行了优化。smallvector的标准使用方式为smallvecotr<type, initial_length>，使用方式和std::vector也类似。smallvector和std::vector相比多个一个模板参数initial_length，这个参数表示smallvector预分配的内存，并且这个内存分配在栈上，而不是预分配在堆中。也就是说，当元素数量较少时，SmallVector会在栈上分配内存，避免了堆上内存分配和释放的开销。只有在元素数量超过阈值时，SmallVector才会在堆上动态分配内存，这时它的行为和std::vector类似。smallvector和std::vector在插入元素时，当超过当前容器的大小时，都会进行扩容，std::vector会重新分配更大的内存块，并将元素从旧内存复制到新内存中，这可能导致内存重新分配和复制的开销。smallvector优先在栈上分配，超过容量切换到堆上。
SmallVector实现采用了一点比较“特殊”的方式，它采用了多继承的方法实现栈+堆混合存储，代码如下：

1
2
3
4

                     SmallVectorStorage<T, N> {
           
...
}

其中SmallVectorImpl对应的是堆存储，SmallVectorStorage对应的是栈存储。SmallVectorStorage本质上是要给数组，所以它的空间是在栈上。而SmallVectorImpl会将SmallVectorStorage对应的数组地址以及数组的长度进行保存，默认情况下并不会在堆中分配空间，当往SmallVector添加元素时总是先判断数据长度是否超过数组的范围，如果超过则进行堆空间分配，如果是第一次从堆中分配，使用malloc并且将栈中数据使用memcpy复制到堆中；如果不是第一次在堆中分配内存，使用realloc分配。
SmallVector内存布局如下所示。

LLVM中提供了API，例如to_vector将std::vector转换到SmallVector，方便整个框架使用SmallVector，在转换过程中会重新构造一个SmallVector对象，同样地如果要从SmallVector转换到std::vector也是重构一个stad::vector对象。所以双方的互转成本较高，而且SmallVector并不适用于std中的各种标准算法，所以在LLVM项目中可以看到两种容器都有使用，一般来说如果需要使用标准算法，优先使用std::vector；当不涉及到算法时，两种容器都可以，如无特别要求一般使用SmallVector。

ArrayRef

ArrayRef是ADT中提供的一个简化顺序容器，它可以从std中的array、vector以及ADT中的SmallVector进行构造，该容器最大的特点是它并没有自己的内存，它和源容器共享内存。所以一般它用于从顺序容器读元素的场景。
此外ADT中还提供了MutableArrayRef和OwningArrayRef，正如它们的名字描述，MutableArrayRef也是和源容器共享内存，但是它提供了一些API可以修改源容器中元素。而OwningArrayRef则是拥有自己的内存，每次创建OwningArrayRef都会分配对应的内存空间。

TinyPtrVector

这是针对SmallVector优化的特殊类型，它适用于容器大多数时候只有0个或者1个元素的场景，对于这样的场景使用该容器可以不必使用SmallVector，相当于直接使用原始类型的指针。所以它使用了一个Union来表示其存储layout，一个是原始类型的指针，另一个是SmallVector的指针。

顺序容器-List

ADT提供了链表类型simplelist、iplist和ilist。同时开发者可以基于链表的一些基础数据结构定义自己的链表类型。

基础链表数据结构

基础链表数据结构主要是提供链表的基础操作，例如设置链表的前驱、后继。

ilist_node

这是ADT中一个常见的基类，它实现了双向链表。

ilist_node_with_parent

这是ADT另外一个比较常用的list基类，它也是双向链表，同时提供了一些基础的API用于访问派生类型的父类型。它接受两个类型，分别是当前类型以及它的父类型。
使用该类型时，需要实现实现getParent（）这样的API才能保证正确性。同时要求父类型实现getSublistAccess（）这样的API。
例如MBB继承于该类型，它的父类型为MachineFunction，两者分别需要定义对应的API。

node_options

ADT中链表结点还可以附加一些option，最典型是sentinel和tag。

ilist_sentinel

该选项表示结点是否哨兵结点。

ilist_tag

为Node添加一个标签，用于确保只有对应tag的node才能加入到list中。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

struct A {};
struct B {};
//定义结点，包括标签A、B
struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {};

void foo() {
  // ListA只能接受结点有Tag A的节点
  simple_ilist<N, ilist_tag<A>> ListA;
  // ListB只能接受结点有Tag B的结点
  simple_ilist<N, ilist_tag<B>> ListB;
  N N1;
  ListA.push_back(N1);
  ListB.push_back(N1);
}

simple_list

基于ilist_node实现的双向链表，它并不支持真正的Delete，它的remove、erase接口都是将结点从链表中移除，并不会执行结点的析构函数。另外simple_list也不支持traits，所以也不会在结点变化时执行额外的操作。

push_back只能接受引用类型，不会执行对象的析构函数
一些例子：

1. simple_ilist给出默认值。
2. simple_ilist<T,ilist_sentinel_tracking>启用ilist_node::isSentinel() API。
3. simple_ilist<T, ilist_tag ,ilist_sentinel_tracking> 指定 A 标签，并且应该关闭跟踪。
4. simple_ilist<T,ilist_sentinel_tracking, ilist_tag > 和3相同。

Iplist/ilist

继承于simple-list，ADT中支持的双向链表，并且这个链表可以支持多态类型的存储，所以是Intrusive Polymorphic的链表。它最大的创新点有两个：
1）在于iplist可以支持基类以及派生类对象，例如instructions和basicblock。
2）位list添加一个traits，在list中对象删除、添加、转移等动作时可以调用Callback进行处理。
注意ilist是iplist的别名。

push_back只能接受指针类型

ImmutableList

提供一个不可变的List，对于该类型不能直接创建，通常都是ImmutableListFactory完成对象创建。

本章主要介绍了LLVM中实现的3种指令选择算法的基本原理和实现细节，从上述章节的描述中，我们可以大致看出3种算法是具有一些相似性的，同时也有许多方面是不同的。因此，本节将3种算法放到了一起，通过简单的比较，定性地给出3个算法的差异情况和使用场景。

SelectionDAGISel经过了多年的发展，功能完善且可靠性高。但是它存在着三个主要的问题。

SelectionDAGISel算法经过了LLVM IR的DAG化、合法化、匹配表查找等复杂过程，会耗费大量时间。为了提高指令选择的速度，LLVM实现了一个快速指令选择算法（FastISel），这一算法只适用于部分后端的O0阶段，是以牺牲指令选择的质量来换取编译时间。

SelectionDAGIsel是一种局部指令选择算法，它以函数中的基本块为粒度，针对基本块内的LLVM IR生成最优的MIR指令，不考虑跨基本块间的指令处理。但是基本块中有一个特殊的指令φ函数需要特别处理，一方面是因为φ函数在后端中并没有一条指令与之对应，另一方面则是因为φ函数表达的是基本块之间的汇聚关系，在处理当前基本块时，编译器并不知道控制流汇聚的情况。所以SelectionDAGIsel实现时将指令分成2类处理。

在编译器中，将高级语言映射到目标架构指令的过程称为指令选择。无论是简单的编译器（直接将高级语言转为目标架构指令），还是优化能力较强的编译器（通过IR进行优化后再转为目标架构指令）都会有这样一个阶段。这是因为高级语言（或者中间表示语言）与目标架构指令之间存在语义差异，需要通过一定的规则才能将高级语言指令转为对应的目标架构指令。规则有可能很简单、也可能很复杂。

代码生成是编译器后端的统称，在编译器的实现中占据着非常重要的地位，也是非常复杂的模块。以LLVM 15为例，整个项目代码行数超过1000万^1，其中clang相关代码超过400万行，LLVM中端优化以及后端代码生成相关代码也已经有近400万行代码。其中代码生成代码量约为200万行，包含了架构无关的代码和架构相关的代码。其中架构无关代码约为50万行，架构相关约为150万行。架构无关的代码主要包了含指令选择、指令调度、寄存器分配和机器码生成；架构相关代码是LLVM所有支持的后端代码总和，目前LLVM已经支持超过20种后端，有些后端的实现非常复杂，如X86后端代码量超过了20万行，而有些又非常简单，如BPF后端代码量只有1万行左右。

基础数据类型

ADT的基础类型有APInt、APSInt、APFloat和APFixedPoint。

ADT（Abstract Data Type）是LLVM定义的一套高级数据类型，是LLVM项目的基础组件。ADT定义了“基础类型”、“容器”、“算法”、“迭代器”，具体来说：

方言概述

MLIR社区提供的方言超过40余个方言，理解全部的方言已经非常困难。下面是有一个部分重要方言的降级流程图。