编译入门那些事儿（1）：LLVM中的Pass和PassManager

0. 前言

众所周知，LLVM编译器采用的是三段式的设计，分为前端、中端和后端，如图1所示：

图1 LLVM三段式设计

不管是在中端还是后端，都存在若干条优化的Pipeline，而这些Pipeline，则是由一个个Pass组成的，对于这些Pass的管理，则是由PassManager完成的。

图2 Pipeline示例

什么是Pass和PassManager？PassManager是如何管理这些Pass的呢？下文将进行一个详细的阐述。

1. LLVM中的Pass

Pass是LLVM编译器所采用的一种结构化技术，用于完成编译对象（如IR）的分析、优化或转换等功能。Pass的执行就是编译器对编译单元进行分析和优化的过程，Pass构建了这些过程所需要的分析结果[1]。一个Pass通常会完成一项较为独立的功能，例如LoopUnroll Pass会进行循环进行展开的操作。但Pass与Pass之间可能会存在一些依赖，一些Pass的执行会依赖于其它一些Pass的分析或者转换结果。

1.1 Pass的分类

1.1.1 按Pass的功能分类

依据Pass的功能，LLVM将Pass分为三类：Analysis Pass、Transform Pass和Utility Pass。[2]

Analysis Pass计算相关IR单元的高层信息，但不对其进行修改。这些信息可以被其他Pass使用，或用于调试和程序可视化。换言之，Analysis Pass会从对应的IR单元中挖掘出需要的信息，然后进行存储，并提供查询的接口，让其它Pass去访问其所存储的信息。同时，Analysis Pass也会提供invalidate接口，因为当其它Pass修改了IR单元的内容后，可能会造成已获取的分析信息失效，此时需调用invalidate接口来告知编译器此Analysis Pass原先所存储的信息已失效。常见的Analysis Pass有Basic Alias Analysis、Scalar Evolution Analysis等。
Transform Pass可以使用Analysis Pass的分析结果，然后以某种方式改变和优化IR。也就是说，这类Pass是会改变IR的内容的，可能会改变IR中的指令，也可能会改变IR中的控制流。例如Inline Pass会将一些函数进行inline的操作，从而减少函数调用，同时在inline后可能会暴露更多的优化机会。
Utility Pass是一些功能性的实用程序，既不属于Analysis Pass，也不属于Transform Pass。例如，extract-blocks Pass将basic block从模块中提取出来供bugpoint使用，它仅完成这项工作。

1.1.2 按Pass作用的IR单元分类

依据Pass作用的IR单元的范围，可以将Pass分为：ModulePass、CallGraphSCCPass、FunctionPass、LoopPass和RegionPass等。Legacy Pass manager（需要加此限定）所管理的所有Pass都派生自Pass类（定义在llvm\include\llvm\Pass.h），具体派生关系如图3所示：

图3 Pass的继承关系

ModulePass是所有Pass中最常用的，它作用于整个程序模块，用于实现非结构化的过程间优化和分析，几乎可以对程序执行任何操作，例如对其中的函数进行增删改。例如GlobalDCELegacyPass就是由ModulePass派生的子类，它的作用就是删除unreachable internal globals。它采用了一种激进的算法，即找出可以证明是alive的全局变量，其它的全局变量则认为是dead的全局变量，将其全部删除。
ImmutablePass被称为最“简单和无聊”的Pass。其用于不需要运行、不改变状态并且不需要更新的Pass，不是常规类型的转换或分析，通常用于提供当前编译器的配置信息。虽然这类Pass非常少用，但它对于提供有关编译的当前目标机器的信息以及可能影响各种转换的其他静态信息是很重要的。例如，AMDGPU后端中的AMDGPUAAWrapperPass就是一个ImmutablePass，用于提供AMDGPUAAResult对象的包装，通过TBAA metadata为其它Pass返回别名查询结果。
CallGraphSCCPass用于在调用图（call graph）上自下往上的遍历程序，这里的SCC[3] 全称为strongly connected component，即强连通分量。CallGraphSCCPass派生类在调用图的强连通分量上运行，并且提供了用于构建和遍历调用图的机制（即以后序方式遍历图），所以可以有效地对程序中的所有调用边进行成对的过程间优化，同时逐步细化并改善这些成对优化。例如AMDGPU后端中的AMDGPUPerfHintAnalysis就是一个CallGraphSCCPass，它用于简要分析函数是否存在潜在的内存限制。
FunctionPass也是最常用的Pass之一，所有FunctionPass在程序中的每个函数上执行，独立于程序中的所有其它函数。FunctionPass子类不需要以特定顺序执行，并且不会修改外部函数，仅能对本函数进行修改。例如InstCombinePass就是一个使用非常频繁的FunctionPass，它会将一些满足某类pattern的指令组合，转换成其它更优的指令或指令组合，从而达到优化的效果。
MachineFunctionPass是FunctionPass的子类，与FunctionPass的功能和限制是一致的，也作用于每个独立的函数上，不同的是它作用于Machine IR。例如ARM后端的ARMConstantIslandPass，它的作用是将常量池分割成'islands'，然后将'islands'分散存储在函数中。
LoopPass作用于函数中的每个循环，与函数中的所有其它循环无关。LoopPass以循环嵌套顺序处理循环，最外层循环最后处理。LoopPass可能会影响loop外的代码，例如LICM Pass会将循环不变的代码外提到循环外面。
RegionPass类似于LoopPass，其在函数中每个单入口单出口Region执行。RegionPass同样以嵌套顺序处理Region，最外层的Region最后处理。RegionPass较少使用。

至此已对LLVM中的Pass进行了一个简单的概述。LLVM中存在大量的中端和后端Pass，并且某些Pass之间还存在着依赖关系，那么LLVM是如何通过PassManager来管理如此庞杂的Pass的呢？

2. LLVM中的PassManager

LLVM的PassManager是LLVM编译工具链调度驱动的核心组件，它控制和管理着编译Pipeline的运作以及对编译Pass的扩展，它主要负责注册、调度Pass，并维护Pass之间的依赖关系，同时还负责对Analysis Pass的分析结果进行管理，让其它Pass可以共享这个分析结果，从而避免重复计算。PassManager确保在运行Pass之前获得所需的分析结果，并确保在编译过程结束销毁PassManager时一并销毁其管理的Pass。当前LLVM系统中存在2套PassManager，分别是LegacyPassManager和NewPassManager。[4] [5]

2.1 LegacyPassManager

LegacyPassManager已经有很长一段历史了，在LLVM15版本之前，默认使用的都是LegacyPassManager。从LLVM15版本开始，才将中端Pipeline的管理权默认交给NewPassManager，后端Pipeline仍由LegacyPassManager管理。

图4为LLVM官网提供的一个LegacyPassManager管理Pass的简单示例，示例中使用opt工具来运行GVN和LICM这两个优化Pass。这里通过添加--debug-pass=Structure选项来打印所有需要运行的Pass。可以看出，除了显示指定的GVN和LICM优化Pass，示例中还运行了Dominator Tree Construction、Natural Loop Information等多个Pass。其实这些Pass都是GVN和LICM所依赖的分析Pass，并且GVN、LICM和ModuleVerifier Pass的运行都依赖Dominator Tree Construction Pass的分析结果，而Dominator Tree Construction Pass却只需要执行一遍。这都要归功于LegacyPassManager对于这些Pass的管理。

图4 LegacyPassManager管理Pass示例

2.1.1 LegacyPassManager的设计框架

接下来，我们先剖析一下LegacyPassManager的基本框架（未包含所有类），如图5所示：

图5 LegacyPassManager框架中的类继承关系

此类图中，各个类的功能如表1所示：

表1 LegacyPassManager框架中相关类说明

2.1.2 LegacyPassManager的工作流程

对LegacyPassManager的设计框架和其相关类的作用有了一定的了解后，再看一下LegacyPassManager是如何完成Pass的注册、调度和执行的。

LegacyPassManager中Pass的注册和调度的具体流程如图6所示。xxxPassManager是提供给用户开发的外部接口类，用户通过xxxPassManager实例的xxxPassManager::add接口将自定义的Pass加入到Pipeline中。PMTopLevelManager的schedulePass接口以完成对Pass的xxxPassManager分配、依赖Pass的创建和递归调度，调度后会生成由PMTopLevelManager作为Root的PassTree。每个层次由PMDataManager管理按照依赖关系排列的Pass数组。这里需要划一个重点：LegacyPassManager会依据AnalysisUsage中的信息，提前解析出Pass之间的依赖关系，然后排布好Pass的执行顺序，也就是说Pass的依赖解析是在Pass运行之前就已经确定了[6] [7]。

图6 LegacyPassManager中Pass的注册和调度

LegacyPassManager的执行过程其实就是以pre-order遍历PassTree的过程（所有Pass的依赖Pass在调度中都已经以post-order的遍历添加到PassVector中），然后执行对应的run接口。不同类型Pass的执行流程较为相似，以FunctionPass的执行过程为例，如图7所示。

图7 LegacyPassManager中FunctionPass的执行过程

2.1.3 自定义LegacyPassManager管理的Pass

了解了LegacyPassManager的工作原理，本文借用LLVM官网中的用例，来说明一下如何去自定义一个LegacyPassManager管理的Pass。

#include "llvm/Pass.h"  
#include "llvm/IR/Function.h"  
#include "llvm/Support/raw_ostream.h"  
  
#include "llvm/IR/LegacyPassManager.h"  
  
using namespace llvm;  
  
namespace {  
struct Hello : public FunctionPass {  
 static char ID;  
 Hello() : FunctionPass(ID) {}  
  
 bool runOnFunction(Function &F) override {  
  errs() << "Hello: ";  
  errs().write_escaped(F.getName()) << '\n';  
  return false;  
 }  
    
 void getAnalysisUsage(AnalysisUsage &AU) const override {  
  AU.setPreservesAll();  
 }  
}; // end of struct Hello  
}  // end of anonymous namespace  
  
char Hello::ID = 0;  
static RegisterPass<Hello> X("hello", "Hello World Pass",  
                             false /* Only looks at CFG */,  
                             false /* Analysis Pass */);

新增LegacyPassManager所管理的Pass，必须显示为其定义一个ID来标识此Pass，并且需要通过指定其父类(ModulePass，FunctionPass等)明确Pass作用的IR单元，相应的需要实现runOnXXX方法。如果Pass需要使用某些Analysis Pass的分析结果，则需要通过实现getAnalysisUsage(AnalysisUsage &AU)方法来显示指定依赖关系，通过required来指定需要依赖的Analysis Pass，如果此Pass没有修改依赖的Analysis Pass的分析结果，则可以通过preserved接口来指定保留原来的分析结果，减少重复计算。在Pass定义完成以后，需要通过RegisterPass将Pass添加到PassRegistry中。

如图8所示，在使用opt工具去调试Pass时，可以通过添加

 -hello

来调用Hello这个FunctionPass。

图8 Hello Pass 示例1

值得强调的是，Hello Pass中未对IR单元做任何修改，因此添加了AU.setPreserveAll()来告知LegacyPassManager之前分析Pass的结果仍有效。若不添加此语句，LegacyPassManager会认为Hello Pass使得之前的分析结果失效，Pass的调度则会如图9所示，可以看出Dominator Tree Construction这个分析Pass执行了两次，这将会增加编译时间。

图9 Hello Pass 示例2

至此，相信读者对于LegacyPassManager已经有了一定的认知。那么问题来了，LegacyPassManager存在哪些不足呢？为什么要在中端使用NewPassManager来替换LegacyPassManager？我们可以看一个简单的示例。在图10中，存在调用关系foo -> bar -> foo，它们形成了一个CGSCC（SCC的概念可以参见 [3] ）。当这个CGSCC被优化后，会得到图11的结果，此时foo和bar分别属于不同的SCC。[8]

图10 CGSCC 示例1

图11 CGSCC 示例2

与Module、Function不同的是，CGSCC只是一个中间的分析结果，它没有持久性的载体，LegacyPassManager仅仅是存储了CGSCC中每个函数的信息，其没有记录整个CGSCC的信息。并且由前文可知LegacyPassManager对于依赖的解析是在Pass运行之前，这将带来一个问题：当某个Pass的执行改变了CGSCC的结构，CGSCC的信息无法得到更新，那么后续执行的CGSCC Pass所获取到的将会是一个错误的SCC的信息，除非开发者提前识别出这个问题，并在CGSCC的结构被更新后，更新整个Module的CallGraph信息。这对开发者提出了很高的要求，并大大增加了编译时间。

那么为什么急于在“中端”使用NewPassManager来替换LegacyPassManager呢？想必读者心中已经有了答案：因为中端存在CGSCC Pass。如图12所示，中端default的优化Pipeline分为module simplication Pipeline和module optimization Pipeline前后两部分，module simplification Pipeline主要对IR做一些结构上的简化，例如函数inline，SimplifyCFG等。module simplification的核心则是CGSCC Pass，最为典型的就是inliner。[9]

图12 中端优化pipeline结构示例

那么NewPassManager是如何解决这个问题的呢？下文将对NewPassManager进行详细的介绍。

2.2 NewPassManager

自LLVM15版本开始，LLVM已经将NewPassManager作为中端优化Pipeline的默认管理者。[8]相比于LegacyPassManager，NewPassManager的设计更加完善，极大提高了编译的效率。

2.2.1 NewPassManager的设计框架

同样的，我们先剖析一下NewPassManager的基本框架(未包含所有类)，如图13所示：

图13 NewPassManager框架中的类继承关系

此类图中，各个类的功能如表2所示：

表2 NewPassManager框架中相关类说明

2.2.2 NewPassManager的工作流程

对NewPassManager的设计框架和其相关类的作用有了一定的了解后，再看一下NewPassManager是如何完成Pass的注册和执行的。NewPassManager中的Pass注册和执行过程相比较于LegacyPassManager更加简单，如图14所示。

图14 NewPassManager中Pass的注册和运行

与LegacyPassManager不同，NewPassManager提供了PassBuilder来辅助Pass的注册过程，并且NewPassManager对Analysis Pass和Tranform Pass做了明确的区分，分别使用RegisterAnalysis和RegisterPasses接口来完成注册工作，然后对应的PassManager将生成的Pass对象保存到对应的容器中。同时，AnalysisManager还负责分析Result的缓存。

Pass注册完成后，可以得到以PassManager为Root的PassTree，并且对应的AnalysisPass均以AnalysisKey作为ID保存在AnalysisManager中，当通过PassManager::run执行Pipeline，PassManager会从Pass列表中逐个运行Pass::run执行对应的Pass。如果执行的Pass需要使用某个AnalysisPass的分析结果，则可以通过getResult或getCachedResult接口获取想要的分析结果（这两个接口的区别在于如果对应的分析结果没有缓存，getResult接口会触发对应AnalysisPass的执行，getCachedResult则直接返回nullptr）。当Pass执行完，需要设置并返回PreservedAnalyses，来告知PassManager此Pass是否修改了代码内容从而使得某些AnalysisResult失效，对于未失效的AnalysisResult则继续缓存，从而避免重复计算。

不知读者发现没，NewPassManager与LegacyPassManager对于Pass的管理存在一个很大的区别：NewPassManager对于Pass依赖的解析是在Pass运行以后，通过getResult接口来完成的。那么当SCC发生变化时，后续的CGSCC Pass在运行时能够及时更新。当然，NewPassManager对于CGSCC PassManager也做了很大的改进，从而使得CallGraph信息的更新变得更加高效，有兴趣的读者可以去阅读一下相关的源码。

2.2.3 自定义NewPassManager管理的Pass

了解了NewPassManager的工作原理，通过一个简单的用例来说明一下如何去自定义一个NewPassManager管理的Pass。

class HelloPass : public PassInfoMixin<HelloPass> {  
public:  
 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);  
};  
  
class HelloAnalysis : public AnalysisInfoMixin<HelloAnalysis> {  
public:  
 static AnalysisKey Key; // AnalysisPass ID  
 struct AnalysisResult {  
 };  
 using Result = AnalysisResult;  
 Result run(Function &F, FunctionAnalysisManager &AM);  
};

NewPassManager所管理的Pass不再需要定义INITIALIZE_PASS宏注册Pass, 不再需要明确继承ModulePass、FunctionPass等来指定其操作的IR单元，只需要在重写的run方法中指定参数的类型即可。因为NewPassManager明确区分了transform Pass和analysis Pass，因此不再需要为transform Pass定义ID，但仍需要为analysis Pass定义一个唯一的标识AnalysisKey,从而去索引对应的AnalysisPass和对应的分析结果。NewPassManager管理的Pass直接通过getResult来获取需要的analysis Pass的分析结果，确定依赖关系，不再需要指定required和preserved，其需要保存的分析结果直接通过函数返回值来确定。

2.3 LegacyPassManager vs NewPassManager

本文在设计和约束这两个维度上，将LegacyPassManager和NewPassManager进行了总结对比，如表3所示：

表3 LegacyPassManager与NewPassManager的对比

3. 总结

本文介绍了LLVM中Pass和Pass Manager的相关概念，并深入剖析了LegacyPassManager和NewPassManager的工作原理和流程。目前LLVM仅在中端优化Pipeline上使能了NewPassManager，后端仍在使用LegacyPassManager。LLVM社区上已有部分开发者在着手后端上NewPassManager的切换工作，有兴趣的读者可以实时跟进一下社区的进展。

参考资料

作者：姜靖
文章来源：毕昇编译

推荐阅读

更多嵌入式AI干货请关注嵌入式AI专栏。欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。