LLVM 和 Clang 中的去虚拟化
这篇博文是来自 LLVM 基金会资助的学生参与 2016 年 LLVM 开发者大会（在加州圣何塞举行）的一系列博文的一部分。请访问 LLVM 基金会的 网页 以了解有关我们旅行补助金计划的更多信息。这篇博文来自 Piotr Padlewski，讲述了他在大会上展示的工作内容：
前端完成的去虚拟化
为了将虚函数调用转换为直接调用，前端必须确保程序中没有 vfunction 的重写，或者知道对象的动态类型。编译过程一次处理一个翻译单元，因此，除了 LTO 以外，只有在少数情况下编译器才能确定没有重写：
- 类或虚函数被标记为 final
- 类在匿名命名空间中定义，并且在它的翻译单元中没有派生类
后者对于 clang 来说更复杂，clang 以即时的方式分块翻译源代码（参见：ASTProducer 和 ASTConsumer），因此无法确定在源代码的后续部分是否存在任何派生类。这个问题可以通过以下几种方式解决：
- 放弃立即生成
- 在 LLVM 中运行数据流分析，以找到传递给具有静态链接的函数的所有动态类型
- 希望在同一个翻译单元中，每个对虚函数的使用都将被 LLVM 内联 - 静态链接会提高内联的机会
LLVM 中的存储到加载传播
为了对虚函数调用进行去虚拟化，我们需要：
- vptr 的值 - 它指向哪张虚函数表
- 虚函数表槽的值 - 它是哪个具体的虚函数
因为虚函数表是常量，所以当我们有 vptr 的值时，后者的值更容易获取。我们唯一需要的是虚函数表定义，这可以通过使用 available_externally 链接来实现。
为了找出 vptr 的值，我们必须找到对同一个位置的存储，它定义了 vptr。有两个分析负责这项任务：
- MemDep（内存依赖分析）是一个简单的线性算法，它对每个查询的指令，都会迭代上面所有指令，直到找到第一个依赖项为止。由于可能对每条指令执行查询，所以我们最终会得到一个二次算法。当然，二次算法在编译器中是不受欢迎的，因此 MemDep 只能检查一定数量的指令。
- 另一方面，内存 SSA 由于缓存，拥有常数复杂度。要了解更多信息，请观看“5 分钟了解内存 SSA”（https://www.youtube.com/watch?v=bdxWmryoHak）。MemSSA 是一种非常新的分析方法，它还没有 MemDep 的所有功能，因此 MemDep 仍然被广泛使用。
查找 vptr 存储
为了找出 vptr 的值，我们需要查看构造函数的存储。为了不依赖于构造函数的可用性或内联，我们决定使用 @llvm.assume 内在函数 来指示 vptr 的值。Assume 类似于 assert - 优化器看到对 @llvm.assume(i1 %b) 的调用，可以假设 %b 在调用之后为真。我们可以通过将 vptr 与虚函数表进行比较，然后用该比较的结果来调用 @llvm.assume，来指示 vptr 的值。
call void @_ZN1AC1Ev(%struct.A* %a) ; 调用构造函数 %3 = load {...} %a ; 加载 vptr %4 = icmp eq %3, @_ZTV1A ; 将 vptr 与虚函数表进行比较 call void @llvm.assume(i1 %4)
调用多个虚函数
一个未内联的虚函数调用会破坏 vptr。换句话说，优化器必须假设虚函数可能会更改传递对象的 vptr。这听起来像是永远不会发生的事情，因为 vptr 是“const”。事实上，它比 C++ 中的 const 成员更弱，因为它在对象的构造过程中会多次发生变化（每个基类构造函数或析构函数都必须设置 vptr）。但是，vptr 在虚函数调用期间不能更改，对吧？那么，关于这个情况呢？
void A::foo() { // 虚函数 static_assert(sizeof(A) == sizeof(Derived)); new(this) Derived; }
这是对 placement new 运算符的调用 - 它不分配新内存，而是只在提供的内存位置创建一个新对象。因此，通过在类型为 A 的对象的内存位置构造一个 Derived 对象，我们更改了 vptr，使其指向 Derived 的虚函数表。这段代码合法吗？C++ 标准表示合法。
然而，事实证明，如果有人调用 foo 两次（使用同一个对象），第二次调用将是未定义行为。标准实际上表示，对指向其生命周期已结束的对象的指针的调用或解引用是 UB，并且由于标准认为从内部销毁对象会结束其生命周期，因此第二次调用是 UB。请注意，这仅仅是因为第二次调用使用了僵尸指针。placement new 返回的指针被认为是有效的，因此对该指针执行调用是有效的。请注意，我们还利用了该事实来使用 assume。
（未）破坏 vptr
我们需要以某种方式说明 vptr 在其生命周期内是不变的。我们决定为此引入一个新的元数据 - !invariant.group。 在加载/存储上存在 invariant.group 元数据，告诉优化器在同一个 invariant group 中，对同一个指针操作数的每个加载和存储都可以被认为加载或存储相同的值。使用 -fstrict-vtable-pointers Clang 会用对应于调用者指针类型的 invariant.group 元数据来修饰虚函数表加载。 （未）破坏 vptr
我们可以通过用 !invariant.load 修饰虚函数的加载（第二次加载）来增强它，这相当于说“从这个位置的加载总是相同的”，这是正确的，因为虚函数表永远不会改变。这样一来，我们就不用依赖于虚函数表的定义。
调用方式:
void g(A *a) { a->foo(); a->foo();}
将被翻译为:
define void @function(%struct.A* %a) { %1 = load {...} %a, !invariant.group !0 %2 = load {...} %1, !invariant.load !1 call void %2(%struct.A* %a)
%3 = load {...} %a, !invariant.group !0 %4 = load {...} %4, !invariant.load !1 call void %4(%struct.A* %a) ret void}
!0 = !{!"_ZTS1A"} ; mangled type name of A!1 = !{}
现在通过GVN和MemDep的魔力:
define void @function(%struct.A* %a) { %1 = load {...} %a, !invariant.group !0 %2 = load {...} %1, !invariant.load !1 call void %2(%struct.A* %a) call void %2(%struct.A* %a) ret void}
这样，LLVM-4.0 就可以在循环中对函数调用进行虚拟化消除。
屏障
为了防止中间端找到带有相同 !invariant.group 元数据的 load/store 操作（这些元数据来自已销毁动态对象的构造/析构），引入了 @llvm.invariant.group.barrier。它返回另一个与参数别名但被视为不同的指针，用于 load/store 的 !invariant.group 元数据。优化器无法识别出返回值指针是同一个，因为 intrinsics 没有定义。必须在动态对象更改的所有位置插入屏障屏障
- 构造函数
- 析构函数
- 动态对象的 placement new
处理屏障
屏障阻碍了其他一些优化。有一些想法可以解决这个问题:
- 在虚拟化消除后立即移除 invariant.group 元数据和屏障。目前是在代码生成之前完成的。问题是大多数虚拟化消除来自 GVN，而 GVN 也完成了我们可能会因屏障而错过的许多优化。GVN 很昂贵，因此只运行一次。如果我们处于 LTO 模式，它可能就没有意义了，因为这会限制链接阶段的虚拟化消除。
- 教导重要的传递过程来跨越屏障。这可能很难保留屏障的语义，但例如，通过跳过屏障来寻找不带 invariant.group 的 load 的依赖关系，以找到不带 invariant.group 的 store，可能会起作用。
- 当屏障的参数来自 alloca 并且从未使用时，移除 invariant.barrier。
关于作者