在 系列的第一部分，我们看到了多态调用的低级实现。普遍认为去虚拟化可以通过通用的中间端优化技术很好地完成——常量传播、存储到加载转发和间接调用移除的组合。（例如，参见 llvm-dev上的这篇文章，GCC开发者也倾向于持有类似的观点。）这次我将展示这是如何实现的，以及为什么在中间端需要专门的去虚拟化代码才能真正优化好。

我将再次尝试使上述内容自成一体，尽管我需要涉及几个相当专业的主题。我将使用与上次相同的示例：

struct A
{
  virtual int foo (void) {return 42;}
};

int test(void)
{
  struct A a, *b=&a;
  return b->foo();
}

对中间端来说，它以以下形式呈现（在第1部分中有详细解释）：

void _ZN1AC2Ev (struct A * const this)
{
  this->_vptr.A = &_ZTV1A + 16;
}

int _ZN1A3fooEv (struct A * const this)
{
  return 42;
}

char * _ZTS1A = "1A";
struct typeinfo _ZTI1A = {&_ZTVN10__cxxabiv117__class_type_infoE + 16, &_ZTS1A}

struct vtable _ZTV1A = {0, &_ZTI1A, _ZN1A3fooEv}

int test() ()
{
  int (*__vtbl_ptr_type) () *tmp1;
  int (*__vtbl_ptr_type) () tmp2;
  struct A a;
  struct A * b;

  _ZN1AC2Ev (&a);
  b = &a;

  tmp1 = b->_vptr.A;
  tmp2 = *tmp1;
  return tmp2 (b);
}

多态调用本身并没有什么固有的魔力可以阻止标准优化器确定它们的目标。这也是GCC使用 -O2 -fno-devirtualize（第二个标志防止特殊的去虚拟化逻辑触发）时发生的情况。然而，需要几个优化协同工作才能得到结果：

  1. 首先 内联器 内联构造函数调用，并将虚表指针的初始化带入test函数体内：

    int test() ()
{
  int (*__vtbl_ptr_type) () *tmp1;
  int (*__vtbl_ptr_type) () tmp2;
  struct A a;
  struct A * b;

  a._vptr.A = &_ZTV1A + 16;
  b = &a;

  tmp1 = b->_vptr.A;
  tmp2 = *tmp1;
  return tmp2 (b);
}

  2. 常量传播 通道将所有出现的 b 替换为 &a。虽然 &a 是栈帧上的地址，因此它并不是真正的常量，但它被仅在一个函数上操作的优化器视为常量。

    int test() ()
{
  int (*__vtbl_ptr_type) () *tmp1;
  int (*__vtbl_ptr_type) () tmp2;
  struct A a;
  struct A * b;

  a._vptr.A = &_ZTV1A + 16;
  b = &a;

  tmp1 = a._vptr.A;
  tmp2 = *tmp1;
  return tmp2 (a);
}

  3. 全局值编号 将内存存储传播到加载，随后解析虚表中的查找，并将多态调用转换为直接调用。

    int test() ()
{
  int (*__vtbl_ptr_type) () *tmp1;
  int (*__vtbl_ptr_type) () tmp2;
  struct A a;
  struct A * b;

  a._vptr.A = &_ZTV1A + 16;
  b = &a;

  tmp1 = &_ZTV1A + 16;
  tmp2 = foo;
  return foo (a);
}

  4. 死代码移除 通道移除多态调用机制中不必要的剩余部分。

    int test() ()
{
  struct A a;
  a._vptr.A = &_ZTV1A + 16;
  return foo (a);
}

  5. 内联器 现在看到直接调用，并准备内联 A::foo。

    int test() ()
{
  struct A a;
  a._vptr.A = &_ZTV1A + 16;
  return 42;
}

  6. 死代码移除 现在可以移除虚表的初始化，从而也移除栈帧中 A 的实际实例。

    int test() ()
{
  return 42;
}

全部完成！

清理这样一个简单的序列需要相当大的努力。这能更容易地完成吗？嗯，部分是的。例如，常量传播通道可以跳过，因为值编号是一个复杂的通道，能够自己完成传播。然而，不能轻易改变的是，去虚拟化是基本优化通道之间相当复杂的相互作用的结果。

在Clang中，可以使用 -mllvm -print-after-all -O2 检查编译过程。事件序列基本相同。

  1. b 的替换已经由 SROA 通道（聚合的标量替换）完成；

  2. 早期的 公共子表达式消除 消除了内存访问中的冗余（有对虚表的数组索引0的访问；GCC已经在前端简化了这一点）；

  3. 内联器 将引入虚表构造函数；

  4. 全局值编号 计算出 a._vptr.A 的值；

  5. 指令组合 将产生直接调用；

  6. 内联器 将内联调用；

  7. SROA 将清理现在已死的 a。

键控类和外部虚表

由于某种原因，这里描述的方法在GCC中直到2010年才起作用，当时我修复了全局值编号中的一个错误，使其能够传播对只读变量的访问。C++前端使用了稍微非标准的方式来描述虚表的内容，中间端简单地放弃了虚表查找。修复这个问题后，我很快开始了解与C++中符号可见性工作方式相关的有趣事情。

C语言的一种遗留是可见性（即static、global或external）仅为函数和变量定义（嗯，除了在函数定义内声明类型的罕见情况外）。这是因为C中的类型本身不会在编译器的输出中产生任何代码或数据结构（除了调试信息外），因此没有真正需要控制它们的可见性。

然而在C++中，类、类型也包含（内联）方法、类数据、虚表、类型信息和其他转换为真实代码或数据结构的东西。除非使用匿名命名空间（这仍然不是很流行），否则你定义的所有类型实际上都是基于类型的唯一名称在编译单元之间共享的（稍后我将详细讨论 单一定义规则）。

因为编译器只在单个编译单元上工作，所以标准方法是将所有类数据和内联方法放入特殊的部分，这些部分由链接器透明地统一（称为 COMDAT 或 linkonce）。这是浪费的，因为出现在头文件中的类被编译多次。这导致重建时间慢，并且需要巨大的磁盘空间来存储目标文件。

有几种方法可以克服冗余编译。最透明的一种是 键控方法 的概念。如果类定义至少一个不是内联的方法，我们知道有一个编译单元定义它。因此，所有类数据都位于该单元中。

还有更多这样的机制，如显式实例化和使用存储库。所有这些技术归结为虚表已知但不在当前编译单元中输出的情况。有点像以下情况：

extern struct vtable _ZTV1A = {0, &_ZTI1A, _ZN1A3fooEv};

这对C程序员来说是一个相当不常见的概念，中间端胆怯地丢弃了这些信息。修复这个问题后，我遇到了许多有趣的问题报告。它们都基于同一个问题：我们知道虚表的内容，但因为虚表不是当前编译单元的一部分，可能有奇怪的原因使我们不允许直接引用它。

我至少会提到两个最重要的：

用户定义的可见性

作为C和C++的扩展，GCC允许指定符号的 ELF可见性。这可以通过可见性属性、-fdefault-visibility 开关或链接器脚本来完成。符号的可见性可以是 default、protected、hidden 或 internal。通常只使用default和hidden。

在构建库时，默认可见性使所有内容从库中导出，而且它允许任何其他库通过不同的定义覆盖该符号。这是一个有用的功能，但它抑制了优化。编译器永远不能确定给定的函数调用将做什么，因为当前的函数体可能被覆盖。它还使动态链接变得昂贵，因为所有引用都需要通过动态链接器处理。因此，鼓励用户仔细将不属于库接口的符号指定为hidden（例如，参见Urlich Drepper的论文 如何编写共享库）。隐藏的符号只在库本身内可见，不会导出。

与C++原生可见性（static/匿名命名空间、全局、COMDAT和`extern`）不同，ELF可见性并不真正是单一定义规则的一部分。在库内部使用和被外部程序使用时，头文件的行为不同是很常见的。

C++并没有真正区分实现细节和外部API；它们都是库头文件的一部分，类中的`public`/`private`说明符更多的是语法糖。因此，编译器需要谨慎使用它在外部变量构造函数中找到的符号。它从库头文件获得的知识可能是也可能不是预期API的一部分。

构造虚表

在对象的基类型被构造之前或对象被析构之后，其虚表被替换为一个新的虚表，称为构造虚表，它指向基类型的虚方法（这样它们的构造函数可以工作）。

通常，构造虚表只在输出它们的单元中直接访问。然而，在 PR54314 中，GCC设法优化了程序中的内存访问，直接引用libstdC++ i/o流的构造虚表。这是因为在多重继承的情况下，构造虚表被另一个数据结构VTT（ 虚表表）引用，而VTT是全局的。

LibstdC++手动控制从库导出的符号列表，而构造虚表不在列表中。你实际上可以查看错误报告本身，看看花了多长时间的讨论才决定这是GCC的错误，不应该引用这些。即使构造虚表从编译单元导出，它们的符号名称也不是由ABI标准化的，不能在外部引用。

为什么这些符号首先被导出？嗯，是为了允许COMDAT机制共享它们。这是GCC对C++符号名称修饰的扩展，使符号名称唯一。如果包含构造虚表的两个对象都是用遵循这个GCC扩展的编译器编译的，链接器将统一这两个副本。另一种方法是引入COMDAT本地（即在同一COMDAT部分内捕获的静态符号）作为VTT。然而，这将阻止甚至在包含VTT的编译单元内编译的代码引用它。

当前"解决方案"

似乎没有什么真正定义了何时可以从外部构造函数中获取符号并引用它。在这种情况下，我们只能猜测用户会做什么，或者对预期用途做出现实的假设，并在出现问题时说服用户改变他们的习惯。

我最终实现了 can_refer_decl_in_current_unit_p 谓词，它禁止引入对抽象符号、具有用户定义可见性（通过属性，而不是通过其他方法）的符号以及其主体不再可用的COMDAT或静态对象（在某个时候编译器必须决定将输出什么并丢弃其余部分）的新引用。

为了使去虚拟化更可靠，我还扩展了符号表中引用的表示，以包括外部变量的构造函数，直到内联完成。这确保COMDAT或静态虚函数不会过早被丢弃。

随着时间的推移，can_refer_decl_in_current_unit_p 已经发展成相当庞大的东西（参见 gcc/trunk/gcc/gimple-fold.c），随着gcc 4.9中COMDAT本地的引入，它需要变成符号而不是单元特定的…​

低级方法的局限性

当然，并非所有可去虚拟化的调用都可以通过这里描述的过程内低级技术处理。以下是主要问题。

虚表存储并不总是对编译器可见

在我们的示例中，总是需要内联构造函数才能进行去虚拟化。如果我们的测试用例使用 -O2 -fno-inline -fno-devirtualize（或者在clang的情况下使用 -O2 -fno-inline）编译，则调用将不会被优化。这是因为当前的过程间优化器不够聪明，无法意识到构造函数返回后，虚表指针具有已知值。这个限制将在GCC 4.9发布后通过在过程间传播中实现聚合返回函数来修复。

即使实现了这一点，这些技术也不会涵盖构造隐藏在编译器背后的情况。考虑：

struct A
{
  virtual int foo (void) {return 42;}
};

int test(struct A a)
{
  struct A *b=&a;
  return b->foo();
}

这里构造的对象来自另一个编译单元。

别名分析太弱，无法在对象的生命周期内跟踪其类型

虚表指针是对象内存布局的一部分。要将其存储（在构造函数中）传播到其加载（在多态调用中），编译器需要证明这个值在此期间没有改变。为此，有别名分析模块。该模块试图证明给定的内存修改指令（如内存存储、调用或asm语句）不会修改给定的内存位置。

这是通过一系列技术完成的。一个主要概念是跟踪给定内存位置是否从当前单元（函数或编译单元）逃逸，或者它是否保持本地。对于本地内存位置，别名分析算法可以相当精确地跟踪哪些指针可能指向对象，这种知识通常足以证明存储是无害的。然而，对于逃逸位置，别名分析算法需要相信最坏的情况。

即使相当无辜的代码也会混淆别名分析。例如：

struct A
{
  virtual int foo (void) {return 42;}
  void bar (void);
};

int test(void)
{
  struct A a, *b=&a;
  b->bar();
  return b->foo();
}

这里优化器将放弃去虚拟化，因为有一个方法 bar 对单元来说是外部的。在低级代码中，调用 b→bar() 将转换为 _ZN1A3barEv (b)。这将使别名分析模块相信 a 的地址正在逃逸，因此每个函数调用都可能改变其内存表示中的任何内容，包括虚表指针。它还会相信来自外部世界的所有内存位置可能包含指向 a 的指针。

因为多态调用通常与对象的构造函数相距甚远，所以很明显低级去虚拟化实际上更像是一个玩具而不是可靠的工具。

暴力方法并不总是胜利

编译器不能花费无限的CPU时间来完成，所以在以下测试用例中：

struct A
{
  virtual int foo (void) {return 42;}
  virtual int foo1 (void) {return foo();}
  virtual int foo2 (void) {return foo1();}
  virtual int foo3 (void) {return foo2();}
  virtual int foo4 (void) {return foo3();}
  virtual int foo5 (void) {return foo4();}
  virtual int foo6 (void) {return foo5();}
  virtual int foo7 (void) {return foo6();}
  virtual int foo8 (void) {return foo7();}
  virtual int foo9 (void) {return foo8();}
  virtual int foo10 (void) {return foo9();}
};

int test(void)
{
  struct A a, *b=&a;
  return b->foo10();
}

你会看到GCC使用 -fno-devirtualize 在2次"迭代"后放弃（GCC实际上有两个内联器），而clang在4次迭代后放弃。这是一个公平的尝试，但是调用 foo8 或 foo6 的结果代码当然是可怕的。迭代方法在 这个补丁 中为GCC提出。然而，它从未进入主线。 关于这种方法的演示。

GCC实现中缺少什么

本地（过程内）存储到加载传播做得很好。我也认为我们在向中间端提供信息方面做得很好，使其理解外部构造函数、单一声明规则、COMDAT共享（所有同名的COMDAT部分在语义上应该等价）和其他细节。

主要限制在于别名分析方面。要去虚拟化，通常至少需要解决基本的过程间问题。GCC当然应该在自动检测 malloc 属性方面做得更好，这将使其能够更好地跟踪对象的生命周期。它还应该获得一个工作的过程间指向分析（当前 -fipa-pta 的实现不够可扩展和稳定，无法默认启用，而且相当有限）。我们还应该自动检测 nocapture（noescape）和noclobber属性。由于某种原因， 实现这些属性的补丁 显然从未进入主线。自动检测应该是对现有pure-const通道的简单添加。

由于通过变量构造函数的传播方式的组织，GCC目前不会考虑它对构造虚表的了解，仅仅基于它知道它不能引用虚表本身的事实。这是因为传播是一步一步工作的，在其中一种中间形式中会有对表的无效引用。这可能可以通过允许这些引用，然后通过现有的 DECL_VALUE 机制将它们转回VTT查找来解决。

经典的值编号只能将一个已知值传播到每个临时变量。它没有考虑对象可能有多种类型，但所有类型都使用相同虚函数的情况。这可能可以通过条件值编号算法部分处理。

在未来，我将讨论C++标准在虚表指针的值上给你的额外知识。我想知道这是否可以挂钩到别名分析模块中，以及存储到加载传播是否可以使用这样一个事实，即在某些地方我们知道虚表指针而不实际看到存储。通常这不是这些优化器的工作，特别是别名分析本身就是一个困难的问题，所以也许最好不要向其中添加额外的复杂性。 最后一个重要领域是改进过程间常量传播，但我将在稍后写到这一点。

我给出了为什么中间端需要了解更多关于C++特定语义的论据。下次我将写关于类型继承图的内容。

作者：Jan Hubička, Google +

Last moify: 2022-12-04 15:11:33
Build time：2025-07-18 09:41:42
Powered By asphinx