如何编写Pass——从LLVM源码角度剖析

CAUTION
本文内容基于 $\text{LLVM 15.0.7}$ 版本，部分内容在其他版本中可能有所不同，请注意差异。

$\text{LLVM}$ 与 $\text{Pass}$ #

$\text{LLVM}$ 并非一个具体的编译器，而是一套可复用、可组合的编译器基础设施。其设计核心是将编译过程拆解为以中间表示（ $\text{LLVM IR}$ ）为载体的不同阶段：前端负责将不同源码翻译为统一的 $\text{IR}$ ，中端围绕 $\text{IR}$ 进行分析与优化，而后端则再将优化后的 $\text{IR}$ 映射到具体的硬件架构。这里不过多介绍中间表示 $\text{IR}$ ，而是聚焦于承载实现分析与优化目的的 $\text{LLVM Pass}$ 。

$\text{LLVM} 架构图$

在 $\text{LLVM}$ 中，所有对 $\text{IR}$ 的 “计算” 都被统一抽象为 $\text{Pass}$ （在编译原理里，" $\text{Pass}$ " 被称为 “遍” 或者 “趟”，表示对代码做一次扫描）。 $\text{Pass}$ 是 $\text{LLVM}$ 执行分析和优化的基本单位，其运行在某一层级的 $\text{IR}$ 上，对程序进行分析或者修改。 $\text{Pass}$ 分为分析类 $\text{Pass}$ 和转换类 $\text{Pass}$ ，

\text{Pass} = \begin{cases} \text{分析类 Pass}: \text{只读取} \\ \text{转换类 Pass}: \text{可修改} \end{cases}

前者只读取 $\text{IR}$ 用于构建特定的分析结果，而后者则基于分析结果的基础上修改 $\text{IR}$ ，实现各种变换。无论是经典的编译优化，还是用户自定义的程序分析，本质上都是以 $\text{Pass}$ 的形式存在。

IMPORTANT
$\text{Pass}$ 在 $\text{LLVM}$ 中扮演的角色不仅是”实现优化”，更是整个中端架构的核心。

$\text{Pass}$ 分类与类设计#

前面提到， $\text{Pass}$ 分为分析类（ $\text{Analysis Pass}$ ）和转换类（ $\text{Transformation Pass}$ ）两类。实际上，按粒度不同， $\text{Pass}$ 还可以进一步划分为模块级（ $\text{ModulePass}$ ）、函数级（ $\text{FunctionPass}$ ）、循环级（ $\text{LoopPass}$ ）等不同层级的 $\text{Pass}$ 。

$\text{LLVM 15.0.7}$ 基于 $\text{NPM}$ （ $\text{New Pass Manager}$ ）的全新 $\text{Pass}$ 框架，一个核心的修改是通过 $\text{CRTP}$ 静态多态替换了旧版 $\text{Pass Manager}$ 中基于虚函数的动态多态设计。不妨来看一下 $\text{NPM}$ 中的 $\text{Pass}$ 类设计：

1
// $LLVM_HOME/include/llvm/IR/PassManager.h
2
template <typename DerivedT> struct PassInfoMixin {
3
  /// Gets the name of the pass we are mixed into.
4
  static StringRef name() {
5
    static_assert(std::is_base_of<PassInfoMixin, DerivedT>::value,
6
                  "Must pass the derived type as the template argument!");
7
    StringRef Name = getTypeName<DerivedT>();
8
    Name.consume_front("llvm::");
9
    return Name;
10
  }
11

12
  void printPipeline(raw_ostream &OS,
13
                     function_ref<StringRef(StringRef)> MapClassName2PassName) {
14
    StringRef ClassName = DerivedT::name();
15
    auto PassName = MapClassName2PassName(ClassName);
16
    OS << PassName;
17
  }
18
};

$\text{PassInfoMixin}$ 显然是一个模板混入类，通过 $\text{CRTP}$ 方式为派生类提供了两个通用的方法（基于 “反射” 实现）： $\text{name()}$ 用于获取 $\text{Pass}$ 的名称， $\text{printPipeline()}$ 用于打印 $\text{Pass}$ 管道信息。 $\text{PassInfoMixin}$ 是最顶层的 $\text{Pass}$ 模板基类，所有具体的 $\text{Pass}$ 都会直接或间接地继承自它。

TIP
可能你会疑惑，作为 $\text{CRTP}$ 模板基类的 $\text{PassInfoMixin}$ 并没有直接调用派生类 $\text{DerivedT}$ 的任何方法，和 $\text{CRTP}$ 中用法有所差异。实际上， $\text{CRTP}$ 的核心思想是通过模板参数将派生类类型传递给基类，让基类知道派生类的类型信息，从而实现静态多态，这里实际上也是如此。

分析类 $\text{Pass}$ 和转换类 $\text{Pass}$ 的区别体现在它们各自的模板基类上，分析类 $\text{Pass}$ 继承自 $\text{AnalysisInfoMixin}$ ，而转换类 $\text{Pass}$ 则继承自 $\text{PassInfoMixin}$ ，而 $\text{AnalysisInfoMixin}$ 则是继承自 $\text{PassInfoMixin}$ ：

1
// $LLVM_HOME/include/llvm/IR/PassManager.h
2
template <typename DerivedT>
3
struct AnalysisInfoMixin : PassInfoMixin<DerivedT> {
4
  static AnalysisKey *ID() {
5
    static_assert(std::is_base_of<AnalysisInfoMixin, DerivedT>::value,
6
                  "Must pass the derived type as the template argument!");
7
    return &DerivedT::Key;
8
  }
9
};

$\text{AnalysisInfoMixin}$ 继承自 $\text{PassInfoMixin}$ ，同样是一个模板混入类，专用于分析类 $\text{Pass}$ 。它为分析类 $\text{Pass}$ 提供了一个静态方法 $\text{ID()}$ 用于获取分析类 $\text{Pass}$ 的唯一标识符 $\text{AnalysisKey}$ （此 $\text{Key}$ 的实现也很有意思）。从这里我们也可以看出，继承自 $\text{AnalysisInfoMixin}$ 的分析类 $\text{Pass}$ 需定义一个静态成员变量 $\text{AnalysisKey}$ 作为其唯一的标识符。

类继承图

$\text{PassManager}$ 与 $\text{AnalysisManager}$ #

到目前为止，我们的 $\text{Pass}$ 还只是一个空壳，除了明确分析类 $\text{Pass}$ 需提供静态成员变量 $\text{AnalysisKey}$ 用于标识外，并没有任何实质性的功能。要让 $\text{Pass}$ 真正发挥作用，还需要依赖 $\text{PassManager}$ 和 $\text{AnalysisManager}$ 来调度和管理 $\text{Pass}$ 的执行。

TIP
虽然还没有介绍 $\text{Pass}$ 的 $\text{run}$ 方法，但应该有一个概念： $\text{Pass}$ 本身就是一个 “无状态” 的执行单元，既不保存分析结果，也不负责调度，这些职责都交给了 $\text{PassManager}$ 和 $\text{AnalysisManager}$ 。

$\text{PassManager}$ ： $\text{Pass}$ 的调度与执行#

很容易犯错的一个误区是将 $\text{PassManager}$ 理解为转换类 $\text{Pass}$ 的管理器，而将 $\text{AnalysisManager}$ 理解为分析类 $\text{Pass}$ 的管理器，两者负责各自 $\text{Pass}$ 的调度执行与管理。实际上， $\text{PassManager}$ 才是 $\text{Pass}$ 的真正调度者，无论是分析类 $\text{Pass}$ 还是转换类 $\text{Pass}$ ，它们的执行都是由 $\text{PassManager}$ 来负责的。

$\text{NPM}$ 中，分析类 $\text{Pass}$ 采用所谓的 “按需计算” 策略执行，即只有在某个转换类 $\text{Pass}$ 需要某个分析类 $\text{Pass}$ 的结果时，才会触发该分析类 $\text{Pass}$ 的执行。因此，在 $NPM$ 中，对分析类 $\text{Pass}$ 的调用，需要通过转换类 $\text{Pass}$ 间接触发，于是， $\text{PassManager}$ 通过直接调用转换类 $\text{Pass}$ 方式间接调用分析类 $\text{Pass}$ 。

让我们来看看 $\text{PassManager}$ 做了什么：

1
// $LLVM_HOME/include/llvm/IR/PassManager.h
2
template <typename IRUnitT,
3
          typename AnalysisManagerT = AnalysisManager<IRUnitT>,
4
          typename... ExtraArgTs>
5
class PassManager : public PassInfoMixin<
6
                        PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> {
7
public:
8
  PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,
9
                        ExtraArgTs... ExtraArgs) {
10
    PreservedAnalyses PA = PreservedAnalyses::all();
11
    PassInstrumentation PI =
12
        detail::getAnalysisResult<PassInstrumentationAnalysis>(
13
            AM, IR, std::tuple<ExtraArgTs...>(ExtraArgs...));
14

15
    for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
16
      auto *P = Passes[Idx].get();
17
      if (!PI.runBeforePass<IRUnitT>(*P, IR))
18
        continue;
19

20
      PreservedAnalyses PassPA;
21
      {
22
        TimeTraceScope TimeScope(P->name(), IR.getName());
23
        PassPA = P->run(IR, AM, ExtraArgs...);
24
      }
25

26
      PI.runAfterPass<IRUnitT>(*P, IR, PassPA);
27
      AM.invalidate(IR, PassPA);
28
      PA.intersect(std::move(PassPA));
29
    }
30

31
    PA.preserveSet<AllAnalysesOn<IRUnitT>>();
32

33
    return PA;
34
  }
35

36
  template <typename PassT>
37
  LLVM_ATTRIBUTE_MINSIZE
38
      std::enable_if_t<!std::is_same<PassT, PassManager>::value>
39
      addPass(PassT &&Pass) {
40
    using PassModelT =
41
        detail::PassModel<IRUnitT, PassT, PreservedAnalyses, AnalysisManagerT,
42
                          ExtraArgTs...>;
43
    Passes.push_back(std::unique_ptr<PassConceptT>(
44
        new PassModelT(std::forward<PassT>(Pass))));
45
  }
46

47
  template <typename PassT>
48
  LLVM_ATTRIBUTE_MINSIZE
49
      std::enable_if_t<std::is_same<PassT, PassManager>::value>
50
      addPass(PassT &&Pass) {
51
    for (auto &P : Pass.Passes)
52
      Passes.push_back(std::move(P));
53
  }
54

55
  bool isEmpty() const { return Passes.empty(); }
56
  static bool isRequired() { return true; }
57

58
protected:
59
  using PassConceptT =
60
      detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>;
61
  std::vector<std::unique_ptr<PassConceptT>> Passes;
62
};

CAUTION
鉴于篇幅过长，上面的代码片段省略了无需关注的方法和注释。

1
// $LLVM_HOME/include/llvm/IR/PassManager.h
2
template <typename IRUnitT,
3
          typename AnalysisManagerT = AnalysisManager<IRUnitT>,
4
          typename... ExtraArgTs>
5
class PassManager : public PassInfoMixin<
6
                        PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> {
7
    /* ... */
8
};

$\text{PassManager}$ 同样是一个模板类，继承自 $\text{PassInfoMixin}$ 基类且实现了特定的 $\text{run()}$ 方法，因此从技术上， $\text{PassManager}$ 也是一个合法的 $\text{Pass}$ 。 $\text{PassManager}$ 拥有三个模板参数：

$\text{IRUnitT}$ ，指定 $\text{PassManager}$ 所管理 $\text{IR}$ 单位类型，也就是转换类 $\text{Pass}$ 的运行粒度（ $\text{Module}$ 、 $\text{Function}$ 、 $\text{Loop}$ ……）；
$\text{AnalysisManagerT}$ ，指定了 $\text{PassManager}$ 需要用来管理分析结果的 $\text{AnalysisManager}$ 类型，默认粒度与 $\text{IRUnitT}$ 保持一致，当然也可以传入其他粒度的 $\text{AnalysisManager}$ ；
$\text{ExtraArgTs}$ ，这是一个可变模板参数包，允许传递额外的参数给转换类 $\text{Pass}$ ，比如需要多个不同粒度的 $\text{AnalysisManagerT}$ 时，就可以通过 $\text{ExtraArgTs}$ 传递进去。

类型擦除 $\text{PassConcept}$ #

1
// $LLVM_HOME/include/llvm/IR/PassManager.h
2
template <typename IRUnitT,
3
          typename AnalysisManagerT = AnalysisManager<IRUnitT>,
4
          typename... ExtraArgTs>
5
class PassManager : public PassInfoMixin<
6
                        PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> {
7
public:
8
  /* ... */
9

10
protected:
11
  using PassConceptT =
12
      detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>;
13

14
  std::vector<std::unique_ptr<PassConceptT>> Passes;
15
};

$\text{PassManager}$ 内部通过一个 $\text{vector}$ 来保存其所管理的转换类 $\text{Pass}$ 列表，但并非直接保存 $\text{Pass}$ 对象或其指针，而是保存了 $\text{PassConceptT}$ 智能指针。

此处的 $\text{PassConceptT}$ 实际上是一个典型的 “类型擦除（ $\text{Type Erasure}$ ）” 实现。需要知道的是，尽管 $\text{PassManager}$ 管理的是同一粒度下的转换类 $\text{Pass}$ ，但这些 $\text{Pass}$ 的具体类型不尽相同，毕竟存在可变模板参数 $\text{ExtraArgTs}$ ，无法通过静态类型来统一表示，也就无法使用 $\text{vector}$ 来统一存储。因此，需要一个抽象基类 $\text{PassConceptT}$ 来隐藏具体的 $\text{Pass}$ 类型， $\text{PassManager}$ 便可以用这个接口来统一调用。

来看看 $\text{PassConceptT}$ 的具体实现：

1
// $LLVM_HOME/include/llvm/IR/PassManagerInternal.h
2
template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
3
struct PassConcept {
4
  virtual ~PassConcept() = default;
5

6
  virtual PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,
7
                                ExtraArgTs... ExtraArgs) = 0;
8

9
  virtual void
10
  printPipeline(raw_ostream &OS,
11
                function_ref<StringRef(StringRef)> MapClassName2PassName) = 0;
12

13
  virtual StringRef name() const = 0;
14
  virtual bool isRequired() const = 0;
15
};

$\text{PassConcept}$ 是一个纯虚类，以纯虚函数的方式定义了四个接口，包括 $\text{run()}$ 、 $\text{printPipeline()}$ 、 $\text{name()}$ 和 $\text{isRequired()}$ ，要求其派生类必须实现这些方法。

其实你也应该发现了， $\text{PassConcept}$ 并非转换类 $\text{Pass}$ 的抽象基类，因为它并没有继承自 $\text{PassInfoMixin}$ ，而且也没有必要。因为 $\text{PassConcept}$ 只是一个接口类，应该与具体的 $\text{Pass}$ 类型解耦。那么，谁来拥有一个具体的转换类 $\text{Pass}$ 对象，并实现上面定义的接口？答案是 $\text{PassModel}$ ：

1
// $LLVM_HOME/include/llvm/IR/PassManagerInternal.h
2
template <typename IRUnitT, typename PassT, typename PreservedAnalysesT,
3
          typename AnalysisManagerT, typename... ExtraArgTs>
4
struct PassModel : PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...> {
5
  PreservedAnalysesT run(IRUnitT &IR, AnalysisManagerT &AM,
6
                         ExtraArgTs... ExtraArgs) override {
7
    return Pass.run(IR, AM, ExtraArgs...);
8
  }
9

10
  void printPipeline(
11
      raw_ostream &OS,
12
      function_ref<StringRef(StringRef)> MapClassName2PassName) override {
13
    Pass.printPipeline(OS, MapClassName2PassName);
14
  }
15

16
  StringRef name() const override { return PassT::name(); }
17

18
  template <typename T>
19
  using has_required_t = decltype(std::declval<T &>().isRequired());
20

21
  template <typename T>
22
  static std::enable_if_t<is_detected<has_required_t, T>::value, bool>
23
  passIsRequiredImpl() {
24
    return T::isRequired();
25
  }
26
  template <typename T>
27
  static std::enable_if_t<!is_detected<has_required_t, T>::value, bool>
28
  passIsRequiredImpl() {
29
    return false;
30
  }
31

32
  bool isRequired() const override { return passIsRequiredImpl<PassT>(); }
33

34
  PassT Pass;
35
};

CAUTION
同样这里省略了部分无需关注的方法和注释，后面不再提示。

$\text{PassModel}$ 继承自上面的抽象基类 $\text{PassConcept}$ ，并实现了其定义的四个接口方法。关注到 $\text{PassModel}$ 拥有一个具体的转换类 $\text{Pass}$ 对象 $\text{PassT Pass}$ ，在除 $\text{isRequired()}$ 的接口方法实现中， $\text{PassModel}$ 都直接调用了该转换类 $\text{Pass}$ 的对应方法，从而实现了封装与调用，而对于 $\text{isRequired()}$ 方法，则通过检测具体的转换类 $\text{Pass}$ 类型是否实现了该方法，来决定是否调用，若没有则直接返回 $\text{false}$ 。

转换类 $\text{Pass}$ 继承自 $\text{PassInfoMixin}$ ，基类 $\text{PassInfoMixin}$ 提供了 $\text{name()}$ 和 $\text{printPipeline}$ 的默认实现，因此，对于转换类 $\text{Pass}$ 而言，必须实现的只有 $\text{run()}$ 方法，这为后续自定义 $\text{Pass}$ 提供了指引。

1
using PassConceptT =
2
      detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>;
3
std::vector<std::unique_ptr<PassConceptT>> Passes;

$\text{PassManager}$ 内部通过 $\text{PassConceptT}$ 的智能指针来保存其所管理的转换类 $\text{Pass}$ 列表，这是一种动态多态的实现方式，运行时，基类指针会指向具体的 $\text{PassModel}$ 对象，从而实现对不同类型转换类 $\text{Pass}$ 的统一管理与调用。

NPM 部分关系图

$\text{run()}$ ：真正的调度执行入口#

在介绍 $\text{PassManager}$ 的 $\text{run()}$ 方法前，有必要先介绍一下 $\text{PreservedAnalyses}$ 。观察 $\text{run()}$ 方法的返回值类型和局部变量类型，可以发现都使用了 $\text{PreservedAnalyses}$ 这个类。

我并不准备在这里对 $\text{PreservedAnalyses}$ 进行详细的剖析，而是做一些概念性的引入。 $\text{PreservedAnalyses}$ 用于表示在某个转换类 $\text{Pass}$ 执行后，哪些分析结果仍然有效（这些分析结果是由分析类 $\text{Pass}$ 计算得到并缓存的）。因为转换类 $\text{Pass}$ 可能会修改 $\text{IR}$ ，从而导致某些分析结果失效，所以每个转换类 $\text{Pass}$ 在执行完毕后，都需要返回一个 $\text{PreservedAnalyses}$ 对象，告诉 $\text{PassManager}$ 哪些分析结果仍然有效，而哪些需要被废弃。

回到 $\text{PassManager}$ 的 $\text{run()}$ 方法：

1
// $LLVM_HOME/include/llvm/IR/PassManager.h
2
PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,
3
                  ExtraArgTs... ExtraArgs) {
4
  PreservedAnalyses PA = PreservedAnalyses::all();
5

6
  PassInstrumentation PI =
7
      detail::getAnalysisResult<PassInstrumentationAnalysis>(
8
          AM, IR, std::tuple<ExtraArgTs...>(ExtraArgs...));
9

10
  for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
11
    auto *P = Passes[Idx].get();
12

13
    if (!PI.runBeforePass<IRUnitT>(*P, IR))
14
    continue;
15

16
    PreservedAnalyses PassPA;
17
    {
18
      TimeTraceScope TimeScope(P->name(), IR.getName());
19
      PassPA = P->run(IR, AM, ExtraArgs...);
20
    }
21

22
    PI.runAfterPass<IRUnitT>(*P, IR, PassPA);
23
    AM.invalidate(IR, PassPA);
24
    PA.intersect(std::move(PassPA));
25
  }
26

27
  PA.preserveSet<AllAnalysesOn<IRUnitT>>();
28

29
  return PA;
30
}

你应该注意到了， $\text{PassManager}$ 的 $\text{run()}$ 方法本身就是一个转换类 $\text{Pass}$ 的 $\text{run()}$ 实现。这也是为什么前面指明，从技术上来看， $\text{PassManager}$ 本身也是一个合法的 $\text{Pass}$ 实现。

考虑 $\text{run()}$ 的参数列表，其中 $\text{IRUnitT \&IR}$ 是当前 $\text{PassManager}$ 所管理的 $\text{IR}$ 单位对象的引用，这是一个具体的 $\text{IR}$ 实例，比如某个 $\text{Module}$ 或者 $\text{Function}$ 等，不要理解为 $\text{IRUnitT}$ 粒度下的所有单位对象，而是其中具体的一个。传入哪个具体的 $\text{IRUnitT}$ 对象不是 $\text{PassManager}$ 负责的，而是由上层调用者决定，这点很重要。当然，对其他的 $\text{Pass}$ 也是如此。

关注 $\text{run()}$ 方法的实现细节：

1
PreservedAnalyses PA = PreservedAnalyses::all();

这里 $\text{PA}$ 是一个通过 $\text{PreservedAnalyses::all()}$ 静态方法创建的 $\text{PreservedAnalyses}$ 对象，表示初始状态下，所有分析结果均有效。这是一个乐观的初始化，后续会根据每个转换类 $\text{Pass}$ 的执行逐步收紧。

1
PassInstrumentation PI =
2
    detail::getAnalysisResult<PassInstrumentationAnalysis>(
3
        AM, IR, std::tuple<ExtraArgTs...>(ExtraArgs...));

$\text{getAnalysisResult}$ 获取了特定 $\text{Pass}$ —— $\text{PassInstrumentationAnalysis}$ 的一个分析结果对象 $\text{PI}$ 。 $\text{PassInstrumentationAnalysis}$ 是一个特殊的分析类 $\text{Pass}$ ，用于在 $\text{Pass}$ 执行前后插入钩子函数，从而实现对 $\text{Pass}$ 执行过程的监控和记录，而其返回分析结果—— $\text{PassInstrumentation}$ 对象中则包含了一系列用于监控和度量的方法的入口。

我不准备详细介绍 $\text{PassInstrumentation}$ 的实现细节，只需要知道其提供了两个方法： $\text{runBeforePass}$ 和 $\text{runAfterPass}$ ，分别在每个转换类 $\text{Pass}$ 执行前后被调用，用于插入监控逻辑（比如在执行前判断是否需要跳过该 $\text{Pass}$ 的执行等）。

1
for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
2
  auto *P = Passes[Idx].get();
3

4
  if (!PI.runBeforePass<IRUnitT>(*P, IR))
5
  continue;
6

7
  PreservedAnalyses PassPA;
8
  {
9
    TimeTraceScope TimeScope(P->name(), IR.getName());
10
    PassPA = P->run(IR, AM, ExtraArgs...);
11
  }
12

13
  PI.runAfterPass<IRUnitT>(*P, IR, PassPA);
14
  AM.invalidate(IR, PassPA);
15
  PA.intersect(std::move(PassPA));
16
}

核心部分的逻辑就比较简单了，遍历 $\text{PassManager}$ 内部保存的所有转换类 $\text{Pass}$ 列表，依次执行每个 $\text{Pass}$ 。当然，在 $\text{Pass}$ 执行前后调用了 $\text{PassInstrumentation}$ 提供的方法进行监控和记录。

需要关注的是， $\text{AnalysisManager}$ （ $\text{AM}$ ）会在每个转换类 $\text{Pass}$ 执行结束后，根据该 $\text{Pass}$ 返回的 $\text{PreservedAnalyses}$ ，通过 $\text{invalidate()}$ 方法即时废除那些被标记为失效的分析结果缓存。与此同时， $\text{PassManager}$ 维护的聚合 $\text{PreservedAnalyses}$ （ $\text{PA}$ ）则通过不断调用 $\text{intersect()}$ 方法逐步收紧，并最终作为该 $\text{PassManager}$ 整体的保留分析集合返回给上层调用者。

$\text{AnalysisManager}$ ：分析结果的管理与缓存#

$\text{AnalysisManager}$ 类模板定义与核心成员如下：

1
// $LLVM_HOME/include/llvm/IR/PassManager.h
2
template <typename IRUnitT, typename... ExtraArgTs>
3
class AnalysisManager {
4
public:
5
  class Invalidator;
6
private:
7
  using ResultConceptT =
8
      detail::AnalysisResultConcept<IRUnitT, PreservedAnalyses, Invalidator>;
9

10
  using PassConceptT =
11
      detail::AnalysisPassConcept<IRUnitT, PreservedAnalyses, Invalidator,
12
                                  ExtraArgTs...>;
13

14
  using AnalysisResultListT =
15
      std::list<std::pair<AnalysisKey *, std::unique_ptr<ResultConceptT>>>;
16

17
  using AnalysisResultListMapT = DenseMap<IRUnitT *, AnalysisResultListT>;
18

19
  using AnalysisResultMapT =
20
      DenseMap<std::pair<AnalysisKey *, IRUnitT *>,
21
               typename AnalysisResultListT::iterator>;
22

23
  using AnalysisPassMapT =
24
      DenseMap<AnalysisKey *, std::unique_ptr<PassConceptT>>;
25

26
  AnalysisPassMapT AnalysisPasses;
27
  AnalysisResultListMapT AnalysisResultLists;
28
  AnalysisResultMapT AnalysisResults;
29
};

同样，我们先关注 $\text{AnalysisManager}$ 的模板参数。和 $\text{PassManager}$ 一样， $\text{IRUnitT}$ 指定了 $\text{AnalysisManager}$ 所管理的 $\text{IR}$ 单位类型，而 $\text{ExtraArgTs}$ 同样是一个可变模板参数包，用于传递额外的参数给分析类 $\text{Pass}$ 。

类型擦除 $\text{AnalysisPassConcept}$ 与 $\text{AnalysisResultConcept}$ #

在私有成员中， $\text{AnalysisPasses}$ 保存了所有注册的分析类 $\text{Pass}$ ，其类型为 $\text{AnalysisPassMapT}$ ，即以 $\text{AnalysisKey*}$ 为键， $\text{PassConceptT}$ 智能指针为值的 $\text{DenseMap}$ 。 $\text{PassConceptT}$ 是 $\text{AnalysisPassConcept}$ 的一个类型别名，看到此处，你应该已经猜到了，此处的 $\text{PassConceptT}$ 也是一个 “类型擦除” 的实现。

我们来看看抽象基类 $\text{AnalysisPassConcept}$ 的定义：

1
// $LLVM_HOME/include/llvm/IR/PassManagerInternal.h
2
template <typename IRUnitT, typename PreservedAnalysesT, typename InvalidatorT,
3
          typename... ExtraArgTs>
4
struct AnalysisPassConcept {
5
  virtual ~AnalysisPassConcept() = default;
6
  virtual std::unique_ptr<
7
      AnalysisResultConcept<IRUnitT, PreservedAnalysesT, InvalidatorT>>
8
  run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
9
      ExtraArgTs... ExtraArgs) = 0;
10
  virtual StringRef name() const = 0;
11
};

可以看到， $\text{AnalysisPassConcept}$ 定义了两个纯虚函数： $\text{run()}$ 和 $\text{name()}$ 作为派生类必须实现的接口。于是，我们查看其派生类 $\text{AnalysisPassModel}$ 实现：

1
// $LLVM_HOME/include/llvm/IR/PassManagerInternal.h
2
template <typename IRUnitT, typename PassT, typename PreservedAnalysesT,
3
          typename InvalidatorT, typename... ExtraArgTs>
4
struct AnalysisPassModel : AnalysisPassConcept<IRUnitT, PreservedAnalysesT,
5
                                               InvalidatorT, ExtraArgTs...> {
6
  using ResultModelT =
7
      AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
8
                          PreservedAnalysesT, InvalidatorT>;
9

10
  std::unique_ptr<
11
      AnalysisResultConcept<IRUnitT, PreservedAnalysesT, InvalidatorT>>
12
  run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
13
      ExtraArgTs... ExtraArgs) override {
14
    return std::make_unique<ResultModelT>(
15
        Pass.run(IR, AM, std::forward<ExtraArgTs>(ExtraArgs)...));
16
  }
17

18
  StringRef name() const override { return PassT::name(); }
19

20
  PassT Pass;
21
};

我们只关注 $\text{run()}$ 接口实现。 $\text{AnalysisPassModel}$ 同样拥有一个具体的分析类 $\text{Pass}$ ，并在 $\text{run()}$ 方法中调用了该 $\text{Pass}$ 的 $\text{run()}$ 方法，获取其分析结果后，封装为 $\text{ResultModelT}$ 智能指针并返回。看到这里，我们应该明白， $\text{AnalysisPassModel}$ 对分析类 $\text{Pass}$ 的实现同样有具体的约束，即必须实现 $\text{run()}$ 方法，并返回一个分析结果对象。

仔细考虑 $\text{run()}$ 方法中的这句代码：

1
return std::make_unique<ResultModelT>(
2
        Pass.run(IR, AM, std::forward<ExtraArgTs>(ExtraArgs)...));

你可能会想， $\text{Pass.run()}$ 返回值用于构造 $\text{ResultModelT}$ 的智能指针，那 $Pass.run()$ 肯定返回一个 $\text{ResultModelT}$ 的对象。对吗？不对！想要确定分析类 $\text{Pass}$ 究竟返回什么类型的分析结果，我们需要剖析另一个 “类型擦除” 的实现—— $\text{AnalysisResultConcept}$ 。

1
template <typename IRUnitT, typename PreservedAnalysesT, typename InvalidatorT>
2
struct AnalysisResultConcept {
3
  virtual ~AnalysisResultConcept() = default;
4
  virtual bool invalidate(IRUnitT &IR, const PreservedAnalysesT &PA,
5
                          InvalidatorT &Inv) = 0;
6
};

和 $\text{Pass}$ 一样，分析结果也有不同的静态类型，如何将其统一存储管理，就需要借助 $\text{AnalysisResultConcept}$ 实现分析结果的 “类型擦除”。看看其定义的纯虚函数，只有一个 $\text{invalidate()}$ 接口，这是用于分析结果失效检查的方法，这部分后面会详细介绍。 $\text{AnalysisResultModel}$ 继承自此抽象基类：

1
// $LLVM_HOME/include/llvm/IR/PassManagerInternal.h
2
template <typename IRUnitT, typename PassT, typename ResultT,
3
          typename PreservedAnalysesT, typename InvalidatorT>
4
struct AnalysisResultModel<IRUnitT, PassT, ResultT, PreservedAnalysesT,
5
                           InvalidatorT, false>
6
    : AnalysisResultConcept<IRUnitT, PreservedAnalysesT, InvalidatorT> {
7

8
  explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {}
9
  AnalysisResultModel(const AnalysisResultModel &Arg) : Result(Arg.Result) {}
10
  AnalysisResultModel(AnalysisResultModel &&Arg)
11
      : Result(std::move(Arg.Result)) {}
12

13
  bool invalidate(IRUnitT &, const PreservedAnalysesT &PA,
14
                  InvalidatorT &) override {
15
    auto PAC = PA.template getChecker<PassT>();
16
    return !PAC.preserved() &&
17
           !PAC.template preservedSet<AllAnalysesOn<IRUnitT>>();
18
  }
19

20
  ResultT Result;
21
};

我们先解决前面的问题：

1
return std::make_unique<ResultModelT>(
2
        Pass.run(IR, AM, std::forward<ExtraArgTs>(ExtraArgs)...));

$\text{Pass.run()}$ 返回了一个分析结果对象 $\text{Result}$ 后，实际上调用了 $\text{AnalysisResultModel(ResultT Result)}$ 构造函数，构造了一个包含该分析结果的 $\text{AnalysisResultModel}$ 对象。

IMPORTANT
现在我们基本上勾勒出了分析类 $\text{Pass}$ 的 “形状”。在前面介绍 $\text{Pass}$ 分类与类设计时提到，分析类 $\text{Pass}$ 都必须定义一个 $\text{AnalysisKey}$ 作为其唯一的身份标识，这里我们又要求分析类 $\text{Pass}$ 需要实现一个 $\text{run()}$ 方法，该方法返回一个分析结果对象。

实际上这里对分析结果对象并没有过多的约束。你可能注意到， $\text{AnalysisResultModel}$ 的 $\text{invalidate()}$ 实现并没有调用任何与 $\text{Result}$ 相关的方法，这实际上是 $\text{LLVM}$ 的一个设计哲学。 $\text{AnalysisResultModel}$ 被设计为分析结果提供统一接口，当然也包括一套默认的失效检查方法的实现，即 $\text{invalidate()}$ 方法。 $\text{AnalysisManager}$ 通过 $\text{AnalysisResultModel}$ 实现对分析结果的统一管理， $\text{AM}$ 在检查分析结果是否失效时正是调用了这里的统一接口实现。这当然也降低了自定义 $\text{Pass}$ 编写的复杂度。

IMPORTANT
你可能会想，如果我自定义的分析类 $\text{Pass}$ 的分析结果对象 $\text{Result}$ 需要自定义的失效检查方法呢，又该如何实现？很简单，借助模板特化。实际上自定义实现失效检查方法是一个相当普遍的需求，因为当一个分析类 $\text{Pass}$ 依赖其他分析结果时，就必须自定义分析结果类的失效检查方法。如何实现 $\text{AnalysisResultModel}$ 针对特定实现了自定义 $\text{invalidate()}$ 方法的分析结果类的特化呢，需要自己编写吗？答案是不用！
不知道你是否注意到上面 $\text{AnalysisResultModel}$ 模板参数中的 $\text{false}$ ，其实还存在一个对应的 $\text{true}$ 版本的 $\text{AnalysisResultModel}$ 实现：
1
// $LLVM_HOME/include/llvm/IR/PassManagerInternal.h
2
template <typename IRUnitT, typename PassT, typename ResultT,
3
          typename PreservedAnalysesT, typename InvalidatorT>
4
struct AnalysisResultModel<IRUnitT, PassT, ResultT, PreservedAnalysesT,
5
                           InvalidatorT, true>
6
    : AnalysisResultConcept<IRUnitT, PreservedAnalysesT, InvalidatorT> {
7
  explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {}
8

9
  bool invalidate(IRUnitT &IR, const PreservedAnalysesT &PA,
10
                  InvalidatorT &Inv) override {
11
    return Result.invalidate(IR, PA, Inv);
12
  }
13

14
  ResultT Result;
15
};
在这个版本里， $\text{invalidate()}$ 调用了分析结果 $\text{Result}$ 自定义实现的 $\text{invalidate()}$ 方法。
这里的模板参数 $\text{false}$ 和 $\text{true}$ 是怎么来的，有何含义？相信你已经猜到了， $\text{true}$ 版本对应分析结果类实现了自定义失效检查方法的情况， $\text{false}$ 则对应了未实现而使用默认检查逻辑的情况，这两个都是特化（偏特化）的版本。我们可以看看主模板声明：
1
template <typename IRUnitT, typename PassT, typename ResultT,
2
          typename PreservedAnalysesT, typename InvalidatorT,
3
          bool HasInvalidateHandler =
4
              ResultHasInvalidateMethod<IRUnitT, ResultT>::Value>
5
struct AnalysisResultModel;
其中类型模板参数 $\text{HasInvalidateHandler}$ 就是上面两个偏特化版本的来源。这里不深入讨论 $\text{LLVM}$ 内部提供的 $\text{SFINAE}$ 方法，只需要知道：当 $\text{ResultT}$ 实现了自定义 $\text{invalidate()}$ 方法时， $\text{HasInvalidateHandler}$ 为 $\text{true}$ ，否则为 $\text{false}$ ，这些都是在编译期可确定的，于是根据这个结果特化出两个偏特化版本。

TIP
$\text{true}$ 模板参数对应于的偏特化版本正是后面失效检查时依赖传递实现的基础。

在 $\text{AnalysisManager}$ 余下的私有成员中， $\text{AnalysisResultLists}$ 保存了具体的 $\text{IRUnitT}$ 实例指针到 $\text{AnalysisResultListT}$ 的映射，其中 $\text{AnalysisResultListT}$ 是一个链表，链上节点存储着分析类 $\text{Pass}$ 的唯一标识和其对应的分析结果。而 $\text{AnalysisResults}$ 则保存了 $\text{<AnalysisKey *, IRUnitT *>}$ 到 $\text{AnalysisResultListT::iterator}$ 的映射，即给出了具体分析类 $\text{Pass}$ 在具体 $\text{IRUnitT}$ 下的分析结果指针（迭代器）。

失效器： $\text{Invalidator}$ #

$\text{AnalysisManager}$ 实现分析结果的管理和缓存很重要的一个任务就是做好分析结果失效状态的管理和更新。 $\text{AnalysisManager}$ 类定义了一个嵌套类，用于分析结果的失效检查：

1
// $LLVM_HOME/include/llvm/IR/PassManagerInternal.h
2
class Invalidator {
3
public:
4
  template <typename PassT>
5
  bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
6
    using ResultModelT =
7
        detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
8
                                    PreservedAnalyses, Invalidator>;
9

10
    return invalidateImpl<ResultModelT>(PassT::ID(), IR, PA);
11
  }
12

13
  bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) {
14
    return invalidateImpl<>(ID, IR, PA);
15
  }
16

17
private:
18
  friend class AnalysisManager;
19

20
  template <typename ResultT = ResultConceptT>
21
  bool invalidateImpl(AnalysisKey *ID, IRUnitT &IR,
22
                      const PreservedAnalyses &PA) {
23
    auto IMapI = IsResultInvalidated.find(ID);
24
    if (IMapI != IsResultInvalidated.end())
25
      return IMapI->second;
26

27
    auto RI = Results.find({ID, &IR});
28
    assert(RI != Results.end() &&
29
            "Trying to invalidate a dependent result that isn't in the "
30
            "manager's cache is always an error, likely due to a stale result "
31
            "handle!");
32

33
    auto &Result = static_cast<ResultT &>(*RI->second->second);
34

35
    bool Inserted;
36
    std::tie(IMapI, Inserted) =
37
        IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)});
38
    (void)Inserted;
39
    assert(Inserted && "Should not have already inserted this ID, likely "
40
                        "indicates a dependency cycle!");
41
    return IMapI->second;
42
  }
43

44
  Invalidator(SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated,
45
              const AnalysisResultMapT &Results)
46
      : IsResultInvalidated(IsResultInvalidated), Results(Results) {}
47

48
  SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated;
49
  const AnalysisResultMapT &Results;
50
};

$\text{Invaildtor}$ 负责管理和传播分析结果的失效，我们只需要将关注点放在 $\text{invalidate()}$ 方法的实现上， $\text{Invaildtor}$ 提供了两个 $\text{invalidate()}$ 的实现：

1
template <typename PassT>
2
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
3
  using ResultModelT =
4
      detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
5
                                  PreservedAnalyses, Invalidator>;
6

7
  return invalidateImpl<ResultModelT>(PassT::ID(), IR, PA);
8
}
9

10
bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) {
11
  return invalidateImpl<>(ID, IR, PA);
12
}

这两种实现都使用了同一个核心方法 $\text{invalidateImpl()}$ 。尽管都是对同一方法的封装，但两者却存在明显的区别，特别是在运行性能上。看看 $\text{invalidateImpl()}$ 的具体实现：

1
template <typename ResultT = ResultConceptT>
2
bool invalidateImpl(AnalysisKey *ID, IRUnitT &IR,
3
                    const PreservedAnalyses &PA) {
4
  auto IMapI = IsResultInvalidated.find(ID);
5
  if (IMapI != IsResultInvalidated.end())
6
    return IMapI->second;
7

8
  auto RI = Results.find({ID, &IR});
9
  assert(RI != Results.end() &&
10
          "Trying to invalidate a dependent result that isn't in the "
11
          "manager's cache is always an error, likely due to a stale result "
12
          "handle!");
13

14
  auto &Result = static_cast<ResultT &>(*RI->second->second);
15

16
  bool Inserted;
17
  std::tie(IMapI, Inserted) =
18
      IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)});
19
  (void)Inserted;
20
  assert(Inserted && "Should not have already inserted this ID, likely "
21
                      "indicates a dependency cycle!");
22
  return IMapI->second;
23
}

$\text{invalidateImpl()}$ 首先检查了当前标识对应的分析类 $\text{Pass}$ 是否已经进行过失效检查，若没有则根据标识和具体的 $\text{IRUnitT}$ 实例获取指向对应分析结果的迭代器，并通过 $\text{static\_cast}$ 获取对应的分析结果 $\text{Result}$ ，最后通过 $\text{Result}$ 调用 $\text{invalidate()}$ 执行失效检查逻辑。

第一种实现将模板参数 $\text{ResultModelT}$ 传递给了 $\text{invalidateImpl()}$ ，使其在编译期便获知分析结果的具体类型，因此后续通过 $\text{Result}$ 调用 $\text{invalidate()}$ 是通过静态类型调用的方式，这一点很重要。而对于 $\text{invalidate()}$ 的第二种实现，并没有传递具体的分析结果类型参数 $\text{ResultT}$ ，因此 $\text{invalidateImpl()}$ 使用了默认的类型模板参数，即 $\text{ResultT = ResultConcept}$ 。也许你仍记得， $\text{ResultConcept}$ 是抽象基类，因此在通过 $\text{Result}$ 调用 $\text{invalidate()}$ 方法时其实是通过虚函数实现的动态分派。这就是两者存在的关键区别，也是运行性能差异的关键所在。

IMPORTANT
我们说 $\text{Invalidator}$ 支持依赖传播的失效检查，其实在分析 $\text{AnalysisResultModel}$ 模板特化的时候已经有所体现。当一个分析类 $\text{Pass}$ $\text{A}$ 依赖其他分析类 $\text{Pass}$ $\text{B}$ 的分析结果时，为保证 $\text{A}$ 的分析结果在 $\text{B}$ 失效时也能及时标识失效， $\text{LLVM}$ 采用了依赖者主动检查，即 $\text{Pull}$ 模式。在这种模式下， $\text{Pass}$ $\text{A}$ 需要在其分析结果类中实现自定义的 $\text{invalidate()}$ 方法，并在方法内部主动调用 $\text{Invalidator}$ 去检查其所依赖的 $\text{Pass}$ $\text{B}$ 的分析结果是否失效，从而实现失效信息的传播。

$\text{AnalysisManager}$ ：分析结果的失效管理#

前面我们介绍了 $\text{Invalidator}$ 提供的对具体分析结果 $\text{Result}$ 执行具有依赖传播的失效检查，那么 $\text{AnalysisManager}$ 是如何借助 $\text{Invalidator}$ 实现其所管理分析类 $\text{Pass}$ 分析结果的统一失效检查？

我们查看 $\text{AnalysisManager}$ 中 $\text{invalidate()}$ 方法的具体实现：

1
// $LLVM_HOME/include/llvm/IR/PassManagerImpl.h
2
template <typename IRUnitT, typename... ExtraArgTs>
3
inline void AnalysisManager<IRUnitT, ExtraArgTs...>::invalidate(
4
    IRUnitT &IR, const PreservedAnalyses &PA) {
5
  if (PA.allAnalysesInSetPreserved<AllAnalysesOn<IRUnitT>>())
6
    return;
7

8
  SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated;
9
  Invalidator Inv(IsResultInvalidated, AnalysisResults);
10
  AnalysisResultListT &ResultsList = AnalysisResultLists[&IR];
11
  for (auto &AnalysisResultPair : ResultsList) {
12
    AnalysisKey *ID = AnalysisResultPair.first;
13
    auto &Result = *AnalysisResultPair.second;
14

15
    auto IMapI = IsResultInvalidated.find(ID);
16
    if (IMapI != IsResultInvalidated.end())
17
      continue;
18

19
    bool Inserted =
20
        IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, Inv)}).second;
21
    (void)Inserted;
22
    assert(Inserted && "Should never have already inserted this ID, likely "
23
                      "indicates a cycle!");
24
  }
25

26
  if (!IsResultInvalidated.empty()) {
27
    for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) {
28
      AnalysisKey *ID = I->first;
29
      if (!IsResultInvalidated.lookup(ID)) {
30
        ++I;
31
        continue;
32
      }
33

34
      if (auto *PI = getCachedResult<PassInstrumentationAnalysis>(IR))
35
        PI->runAnalysisInvalidated(this->lookUpPass(ID), IR);
36

37
      I = ResultsList.erase(I);
38
      AnalysisResults.erase({ID, &IR});
39
    }
40
  }
41

42
  if (ResultsList.empty())
43
    AnalysisResultLists.erase(&IR);
44
}

$\text{AnalysisManager::invalidate()}$ 实现可以分为两个部分。

1
SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated;
2
Invalidator Inv(IsResultInvalidated, AnalysisResults);
3
AnalysisResultListT &ResultsList = AnalysisResultLists[&IR];
4
for (auto &AnalysisResultPair : ResultsList) {
5
  AnalysisKey *ID = AnalysisResultPair.first;
6
  auto &Result = *AnalysisResultPair.second;
7

8
  auto IMapI = IsResultInvalidated.find(ID);
9
  if (IMapI != IsResultInvalidated.end())
10
    continue;
11

12
  bool Inserted =
13
      IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, Inv)}).second;
14
  (void)Inserted;
15
  assert(Inserted && "Should never have already inserted this ID, likely "
16
                    "indicates a cycle!");
17
}

首先遍历具体 $\text{IRUnitT}$ 实例对应的分析结果列表，取出每个节点记录的分析类 $\text{Pass}$ 的唯一标识和对应分析结果 $\text{Result}$ 。通过 $\text{Result}$ 调用 $\text{invalidate()}$ 执行失效检查逻辑（不要忘了，这里的 $\text{Result}$ 实际上是 $\text{AnalysisResultModel}$ ），并将检查结果插入到 $\text{IsResultInvalidated}$ 中。

IMPORTANT
$\text{IsResultInvalidated}$ 是 $\text{AnalysisManager}$ 在一次失效检查过程中维护的判定缓存表，扮演了关键的角色。依赖传播是递归的，而同一个分析结果的失效判定只能做一次，否则重复调用 $\text{invalidate()}$ 方法带来的将是指数级的复杂度。
可以确保的是 $\text{LLVM}$ 不存在分析结果的循环依赖，失效检查方法 $\text{invalidate()}$ 也就不会存在无穷递归的情况，你可以思考一下为什么（但是 $\text{Pass}$ 之间的循环依赖却可能造成 $\text{run()}$ 方法的无穷递归调用）。

1
if (!IsResultInvalidated.empty()) {
2
  for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) {
3
    AnalysisKey *ID = I->first;
4
    if (!IsResultInvalidated.lookup(ID)) {
5
      ++I;
6
      continue;
7
    }
8

9
    if (auto *PI = getCachedResult<PassInstrumentationAnalysis>(IR))
10
      PI->runAnalysisInvalidated(this->lookUpPass(ID), IR);
11

12
    I = ResultsList.erase(I);
13
    AnalysisResults.erase({ID, &IR});
14
  }
15
}

当失效检查标记完所有分析结果缓存后才开始执行真正的”失效”的过程。遍历 $\text{IRUnitT}$ 实例对应的分析结果列表，根据失效判定缓存表 $\text{IsResultInvalidated}$ 中存储的结果，当标记为 $\text{true}$ 是将改分析结果缓存移除（即失效），否则跳过仍保留该分析结果缓存。

逻辑相对简单，但是我们仍可以有很多思考。在 $\text{AnalysisManager}$ 对分析结果缓存执行失效检查过程中，失效器 $\text{Inv}$ 的角色是什么？我们回顾 $\text{AnalysisResultModel}$ 提供的 $\text{invalidate()}$ 接口实现：

1
// $LLVM_HOME/include/llvm/IR/PassManagerInternal.h
2
template <typename IRUnitT, typename PassT, typename ResultT,
3
          typename PreservedAnalysesT, typename InvalidatorT>
4
struct AnalysisResultModel<IRUnitT, PassT, ResultT, PreservedAnalysesT,
5
                           InvalidatorT, true>
6
    : AnalysisResultConcept<IRUnitT, PreservedAnalysesT, InvalidatorT> {
7
  explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {}
8

9
  bool invalidate(IRUnitT &IR, const PreservedAnalysesT &PA,
10
                  InvalidatorT &Inv) override {
11
    return Result.invalidate(IR, PA, Inv);
12
  }
13

14
  ResultT Result;
15
};

可以看到，其只是简单地将失效器 $\text{Inv}$ 传递给了分析结果类自定义实现的失效检查方法 $\text{invalidate()}$ 中，为什么呢，你可能会有疑问：难道分析结果类 $\text{invalidate()}$ 方法就必须借助失效器 $\text{Inv}$ 来执行所依赖分析结果的失效检查逻辑，不能直接调用所依赖分析结果的 $\text{invalidate()}$ 方法吗？答案是不能，因为不借助失效器 $\text{Inv}$ 根本拿不到该分析结果。我们不妨看看分析结果类 $\text{invalidate()}$ 的方法签名：

1
bool invalidate(IRUnitT &IR,
2
                const PreservedAnalyses &PA,
3
                Invalidator &Inv);

发现根本没有传入任何 $\text{AnalysisManager}$ 或 $\text{AnalysisResultMap}$ 等可以获取到指定分析结果缓存的参数。而 $\text{Invalidator}$ 中恰好保存了 $\text{Results}$ ：

1
const AnalysisResultMapT &Results

当然这不是唯一的原因，失效器 $\text{Inv}$ 的另一个作用是传递失效判定缓存 $\text{IsResultInvalidated}$ ，其作用这里就不用赘述了吧。

TIP
前面我们也提到过，分析类 $\text{Pass}$ 采用所谓的 “按需计算” 的策略，只有当某转换类 $\text{Pass}$ 依赖其分析结果，且缓存没有命中时才会触发该分析类 $\text{Pass}$ 的执行。这里需要注意的是，这部分逻辑并不由转换类 $\text{Pass}$ 实现，而是交由 $\text{AnalysisManager}$ 负责管理，这也是会在转换类 $\text{Pass}$ 的 $\text{run()}$ 方法函数签名中看到 $\text{AnalysisManager}$ 的原因：
1
PreservedAnalysesT run(IRUnitT &IR, AnalysisManagerT &AM,
2
                         ExtraArgTs... ExtraArgs)

PassManager关系图

动手写一个 $\text{Pass}$ #

我们已经学习了编写一个 $\text{Pass}$ 需要得一切基础知识，现在让我们动手写一个分析类 $\text{Pass}$ 用于打印一个 $\text{Module}$ 实例中所有函数名称及其所含基本块数目（跳过函数声明）。

回顾一下，分析类 $\text{Pass}$ 继承自 $\text{AnalysisInfoMixin}$ ，并且有一个静态成员变量 $\text{AnalysisKey}$ $\text{Key}$ 作为其唯一得标识。

1
#include "llvm/IR/PassManager.h"
2

3
struct FuncBBCountAnalysis: llvm::AnalysisInfoMixin<FuncBBCountAnalysis> {
4
    // 分析类 Pass ID
5
    static llvm::AnalysisKey Key;
6
};

此外，我们需要为其定义 $\text{run()}$ 方法，以实现该 $\text{Pass}$ 具体逻辑，不过在此之前，需要定义一个分析结果类作为 $\text{run()}$ 方法返回的分析结果。

1
#include "llvm/IR/PassManager.h"
2
#include <map>
3

4
// 前向声明
5
struct FuncBBCountAnalysis;
6

7
// 分析结果类
8
struct FuncBBCountResult {
9
    std::map<std::string, unsigned> FuncBBMap;
10

11
    // 失效检查方法，可以省略
12
    bool invalidate(llvm::Module &M, const llvm::PreservedAnalyses &PA
13
                , llvm::ModuleAnalysisManager::Invalidator &Inv) {
14
        auto PAC = PA.getChecker<FuncBBCountAnalysis>();
15
        if (PAC.preserved() || PAC.preservedSet<llvm::AllAnalysesOn<llvm::Module>>()) {
16
            return false;
17
        }
18
        return true;
19
    }
20
};
21

22
struct FuncBBCountAnalysis: llvm::AnalysisInfoMixin<FuncBBCountAnalysis> {
23
    // Pass ID
24
    static llvm::AnalysisKey Key;
25
};

你应该发现了，这里定义的分析结果类的 $\text{invalidate()}$ 方法与 $\text{AnalysisPassModel}$ 提供的默认失效检查逻辑是一致的。我们将要实现的 $\text{FuncBBCountAnalysis}$ $\text{Pass}$ 并不依赖任何其他分析结果，因此这里可以省略编写 $\text{invalidate()}$ 而使用默认实现。

1
#include "llvm/IR/PassManager.h"
2
#include <map>
3

4
// 不再需要
5
// // 前向声明
6
// struct FuncBBCountAnalysis;
7

8
// 分析结果类
9
struct FuncBBCountResult {
10
    std::map<std::string, unsigned> FuncBBMap;
11

12
    // 省略
13
    // // 失效检查方法，可以省略
14
    // bool invalidate(llvm::Module &M, const llvm::PreservedAnalyses &PA
15
    //             , llvm::ModuleAnalysisManager::Invalidator &Inv) {
16
    //     auto PAC = PA.getChecker<FuncBBCountAnalysis>();
17
    //     if (PAC.preserved() || PAC.preservedSet<llvm::AllAnalysesOn<llvm::Module>>()) {
18
    //         return false;
19
    //     }
20
    //     return true;
21
    // }
22
};
23

24
struct FuncBBCountAnalysis: llvm::AnalysisInfoMixin<FuncBBCountAnalysis> {
25
    // Pass ID
26
    static llvm::AnalysisKey Key;
27
};

现在有了分析结果类 $\text{FuncBBCountResult}$ ，那么就可以着手 $\text{run()}$ 方法的编写了。逻辑比较简单：遍历 $\text{Module}$ 中的所有 $\text{Function}$ 并通过相关接口获取信息即可：

1
/// ModuleFuncBBPrinter.h
2
/// Header file for Module Function Basic Block Printer Pass
3

4
#ifndef MODULE_FUNC_BB_PRINTER_H
5
#define MODULE_FUNC_BB_PRINTER_H
6

7
#include "llvm/IR/PassManager.h"
8
#include "llvm/IR/Module.h"
9
#include <string>
10
#include <map>
11

12
// 分析结果类：存储[函数名->基本块数目]的映射
13
struct FuncBBCountResult {
14
    std::map<std::string, unsigned> FuncBBMap;
15
};
16

17
struct FuncBBCountAnalysis: llvm::AnalysisInfoMixin<FuncBBCountAnalysis> {
18
    using Result = FuncBBCountResult;
19

20
    Result run(llvm::Module &M, llvm::ModuleAnalysisManager &AM) {
21
        FuncBBCountResult Result;
22

23
        // 遍历 Module 中的所有函数
24
        for (auto &F: M){
25
            // 跳过声明
26
            if (F.isDeclaration()) continue;
27
            std::string FuncName = F.getName().str();
28
            unsigned BBCount = F.size();
29
            llvm::errs() << "Function: " << FuncName << ", Basic Blocks: " << BBCount << "\n";
30

31
            Result.FuncBBMap[FuncName] = BBCount;
32
        }
33

34
        return Result;
35
    }
36

37
    // Pass ID
38
    static llvm::AnalysisKey Key;
39
};
40
#endif

这个分析类 $\text{Pass}$ 我们就编写完成了，前面讲过，分析类 $\text{Pass}$ 需要通过转换类 $\text{Pass}$ 间接触发运行，因此我们需要为其包装一个转换类 $\text{Pass}$ ：

1
/// FuncBBCountPrinter.cpp
2
#include "ModuleFuncBBPrinter.h"
3
#include "llvm/Passes/PassBuilder.h"
4
#include "llvm/Passes/PassPlugin.h"
5
#include "llvm/IR/PassManager.h"
6

7
// 初始化分析 ID
8
llvm::AnalysisKey FuncBBCountAnalysis::Key;
9

10
struct FuncBBCountPrinterPass : public llvm::PassInfoMixin<FuncBBCountPrinterPass> {
11
  llvm::PreservedAnalyses run(llvm::Module &M, llvm::ModuleAnalysisManager &AM) {
12
    // 获取分析结果，间接触发分析 Pass 的调用
13
    auto &Result = AM.getResult<FuncBBCountAnalysis>(M);
14
    return llvm::PreservedAnalyses::all();
15
  }
16
};

该转换类 $\text{Pass}$ 只是简单地通过 $\text{AnalysisManager}$ 获取该自定义分析类 $\text{Pass}$ 的分析结果。当缓存不命中时，就会触发 $\text{FuncBBCountAnalysis}$ 的执行。其实这里可以验证一下：

1
struct FuncBBCountPrinterPass : public llvm::PassInfoMixin<FuncBBCountPrinterPass> {
2
  llvm::PreservedAnalyses run(llvm::Module &M, llvm::ModuleAnalysisManager &AM) {
3
    // 获取分析结果，间接触发分析 Pass 的调用
4
    llvm::errs() << "First time get result of FuncBBCountAnalysis:\n";
5
    auto &Result = AM.getResult<FuncBBCountAnalysis>(M);
6
    // 再次获取，期望命中缓存，无打印信息输出
7
    llvm::errs() << "Second time get result of FuncBBCountAnalysis:\n";
8
    auto &CachedResult = AM.getResult<FuncBBCountAnalysis>(M);
9
    // 保留所有分析缓存
10
    return llvm::PreservedAnalyses::all();
11
  }
12
};

下面就是 $\text{Pass}$ 的注册逻辑了，鉴于篇幅原因便不在此深入。下面给出完整代码：

1
/// FuncBBCountPrinter.cpp
2
#include "ModuleFuncBBPrinter.h"
3
#include "llvm/Passes/PassBuilder.h"
4
#include "llvm/Passes/PassPlugin.h"
5
#include "llvm/IR/PassManager.h"
6

7
// 初始化分析 ID
8
llvm::AnalysisKey FuncBBCountAnalysis::Key;
9

10
struct FuncBBCountPrinterPass : public llvm::PassInfoMixin<FuncBBCountPrinterPass> {
11
  llvm::PreservedAnalyses run(llvm::Module &M, llvm::ModuleAnalysisManager &AM) {
12
    llvm::errs() << "First time get result of FuncBBCountAnalysis:\n";
13
    auto &Result = AM.getResult<FuncBBCountAnalysis>(M);
14
    // 再次获取，期望命中缓存，无打印信息输出
15
    llvm::errs() << "Second time get result of FuncBBCountAnalysis:\n";
16
    auto &CachedResult = AM.getResult<FuncBBCountAnalysis>(M);
17
    // 保留所有分析缓存
18
    return llvm::PreservedAnalyses::all();
19
  }
20
};
21

22
// 注册分析 Pass 与 转换 Pass
23
llvm::PassPluginLibraryInfo getFuncBBCountPluginInfo() {
24
  return {
25
    LLVM_PLUGIN_API_VERSION,
26
    "FuncBBCountAnalysis",
27
    LLVM_VERSION_STRING,
28
    [](llvm::PassBuilder &PB) {
29
      // 注册分析 Pass 到 ModuleAnalysisManager
30
      PB.registerAnalysisRegistrationCallback(
31
        [](llvm::ModuleAnalysisManager &MAM) {
32
          MAM.registerPass([] { return FuncBBCountAnalysis(); });
33
        }
34
      );
35

36
      // 注册可直接调用的转换 Pass 到 ModulePassManager
37
      PB.registerPipelineParsingCallback(
38
        [](llvm::StringRef Name, llvm::ModulePassManager &MPM,
39
           llvm::ArrayRef<llvm::PassBuilder::PipelineElement>) {
40
          // Pass 名称：func-bb-count，命令行调用此名称
41
          if (Name == "func-bb-count") {
42
            MPM.addPass(FuncBBCountPrinterPass());
43
            return true;
44
          }
45
          return false;
46
        }
47
      );
48
    }
49
  };
50
}
51

52
// 插件入口
53
extern "C" LLVM_ATTRIBUTE_WEAK ::llvm::PassPluginLibraryInfo
54
llvmGetPassPluginInfo() {
55
  return getFuncBBCountPluginInfo();
56
}

$\text{CMakeLists.txt}$ 作参考：

1
cmake_minimum_required(VERSION 3.18)
2
project(FuncBBCountAnalysis LANGUAGES C CXX)
3

4
set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
5

6
find_package(LLVM REQUIRED CONFIG)
7

8
message(STATUS "LLVM Version      : ${LLVM_PACKAGE_VERSION}")
9
message(STATUS "LLVM_DIR          : ${LLVM_DIR}")
10
message(STATUS "LLVM Include Dirs : ${LLVM_INCLUDE_DIRS}")
11

12
set(CMAKE_CXX_STANDARD 17)
13
set(CMAKE_CXX_STANDARD_REQUIRED ON)
14

15
include_directories(${LLVM_INCLUDE_DIRS})
16
add_definitions(${LLVM_DEFINITIONS})
17

18
add_library(FuncBBCountAnalysis MODULE
19
  ModuleFuncBBPrinter.cpp
20
)
21

22
set_target_properties(FuncBBCountAnalysis PROPERTIES
23
  PREFIX ""
24
  SUFFIX ".so"
25
  COMPILE_FLAGS "-fno-rtti -fPIC"
26
)
27

28
if (EXISTS "${CMAKE_BINARY_DIR}/compile_commands.json")
29
  execute_process(
30
    COMMAND ${CMAKE_COMMAND} -E copy_if_different
31
            ${CMAKE_BINARY_DIR}/compile_commands.json
32
            ${CMAKE_SOURCE_DIR}/compile_commands.json
33
  )
34
endif()

构建、运行参考下面命令：

1
mkdir build && cd build
2
cmake -DCMAKE_BUILD_TYPE=[Debug|Release] ..
3
make -j$(nproc)
4

5
cd ..
6

7
opt \
8
  -load-pass-plugin=./build/FuncBBCountAnalysis.so \
9
  -passes=func-bb-count \
10
  test.ll \
11
  -o /dev/null

运行结果： result

LLVM\text{LLVM}LLVM 与 Pass\text{Pass}Pass#

Pass\text{Pass}Pass 分类与类设计#

PassManager\text{PassManager}PassManager 与 AnalysisManager\text{AnalysisManager}AnalysisManager#

PassManager\text{PassManager}PassManager：Pass\text{Pass}Pass 的调度与执行#

类型擦除 PassConcept\text{PassConcept}PassConcept#

run()\text{run()}run()：真正的调度执行入口#

AnalysisManager\text{AnalysisManager}AnalysisManager：分析结果的管理与缓存#

类型擦除 AnalysisPassConcept\text{AnalysisPassConcept}AnalysisPassConcept 与 AnalysisResultConcept\text{AnalysisResultConcept}AnalysisResultConcept#

失效器：Invalidator\text{Invalidator}Invalidator#

AnalysisManager\text{AnalysisManager}AnalysisManager：分析结果的失效管理#

动手写一个 Pass\text{Pass}Pass#

$\text{LLVM}$ 与 $\text{Pass}$ #

$\text{Pass}$ 分类与类设计#

$\text{PassManager}$ 与 $\text{AnalysisManager}$ #

$\text{PassManager}$ ： $\text{Pass}$ 的调度与执行#

类型擦除 $\text{PassConcept}$ #

$\text{run()}$ ：真正的调度执行入口#

$\text{AnalysisManager}$ ：分析结果的管理与缓存#

类型擦除 $\text{AnalysisPassConcept}$ 与 $\text{AnalysisResultConcept}$ #

失效器： $\text{Invalidator}$ #

$\text{AnalysisManager}$ ：分析结果的失效管理#

动手写一个 $\text{Pass}$ #