C++中的去虚拟化，第一部分

去虚拟化是一种将多态调用转换为直接调用的优化技术。在这个系列中，我想描述C程序中的调用优化。编译器优化的这个领域在文献中并没有得到很好的覆盖（似乎所有的研究都是在Java或解释型语言上进行的）。我将详细解释去虚拟化在 link:http://gcc.gnu.org/[GCC] 中的工作原理。稍后我还将展示从更大的应用程序（如Firefox或LibreOffice）收集的一些统计数据，很明显C程序员倾向于滥用C++中的 virtual 关键字，并对生成的代码有各种（非）现实的假设。

多态调用是如何实现的

为了让非编译器开发人员也能理解这个系列，让我们展示一个小例子：

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

在 test 中调用方法 foo 是多态的。在底层，test 被翻译成以下代码（我将使用基于GCC的 GIMPLE 的完全随机的类C语言）：

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;

  _ZN1AC2Ev (&a);

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

乍一看这可能很可怕。确切的布局由 link:http://refspecs.linuxbase.org/cxxabi-1.83.html[Itanium C 应用程序二进制接口] 指定（是的，它也用于非Itanium架构）。有一个小工具 `cfilt` 可以帮助翻译编译器自动生成的各个东西的名称混淆：

_ZN1AC2Ev 是构造函数（A::A），它将虚表指针存储到结构 A 的每个实例中。
_ZN1A3fooEv 是方法 A::foo 本身。
_ZTV1A 是结构A的虚表。它由顶部偏移指针（如果A在更大的类中）、RTTI指针和指向各个虚方法的指针数组组成，在这种情况下，有一个指向 A::foo 的指针。
_ZTI1A 是结构A的RTTI（运行时类型信息）。可以通过 -fno-rtti 抑制这些"垃圾"的生成。

函数 test 最终变成了构造函数（A::A）的调用，然后是标准的多态调用序列，通过虚表查找方法的地址。

事实上，我刚刚注意到GCC前端还生成了一个虚拟的 try…finally 区域，以便在 A::foo 抛出异常的情况下执行空析构函数。我发送了一个补丁来修复这个问题。更新： 似乎情况并不那么简单，为了优化死存储，需要try…finally区域，请参见补丁后的讨论。

大多数用户会期望优化编译器生成：

int test(void)
{
  return 42;
}

这也是每个像样的C++编译器会做的事情。让我们看看它是如何完成的。

前端中的去虚拟化

每个现代编译器都分为特定语言部分（前端）、负责目标无关优化的部分（中端）和负责代码生成的部分（后端）。去虚拟化本质上是特定语言的优化，因此对于像我这样懒惰的中端开发人员来说，期望它在前端实现是很自然的。

事实上，这正是GCC中的C++前端（或LLVM中的 clang）所做的，我不得不禁用这种转换才能让上面的测试用例完全显示出其复杂性。

实现方式很简单。前端寻找虚方法的调用，在这些调用中它立即知道不允许派生类型，并生成直接调用。即使在 -O0 下，这种优化也会在以下所有情况下发生：

int test(void)
{
  struct A a;
  return a.foo();
}

struct A a;
int test(void)
{
  return a.foo();
}

int test(struct A a)
{
  return a.foo();
}

前端还特别处理构造函数和析构函数中的调用，因为这是this指针类型已知的情况。因此，即使以下调用也会被优化：

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

对于那些勇敢到深入GCC源代码的人，可以在 cp/class.c 中的 resolves_to_fixed_type_p 和 fixed_type_or_null 中看到确切的规则。

因为前端的工作不是努力优化跨语句边界，所以当你使用指针或引用时，调用将保持多态。因此，以下测试用例将不会被优化：

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

帮助去虚拟化的一种方法是使用C++11添加的 final 关键字，如下面这个与前一个等效的测试用例：

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

前端错过的去虚拟化机会

我认为前端（clang和GCC）至少在三种情况下是懒惰的。显然，它们只实现了C++标准要求发生的情况。

在以下测试用例中，可以去虚拟化，因为类型在匿名命名空间中，前端可以轻松使用没有派生的事实：

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

在这里，可以使用 foo 是自递归的事实，并将其编译成无限循环：

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

这种转换似乎特别有用，因为自递归虚函数出人意料地频繁。

更新： 我太快了。在以下测试用例中：

#include <stdio.h>
struct A
{
  virtual int foo (void) {return foo()+1;}
};
struct B: public A
{
  virtual int foo (void) {return 1;}
};
main()
{
  struct B b;
  printf("%i\n",b.A::foo());
}

不能对自递归做假设。A::foo() 的调用"递归"到 B::foo()。这可能是一个足够罕见的情况，值得跟踪这种对虚函数的显式调用，并特别小心处理它们，但仅限于我们知道对于给定单元是本地的类型。

最后一个看似重要的情况是当类是其他结构的子字段或包含在数组中时。这里再次不允许派生类型：

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

struct B {
  struct A a;
};
struct A a[7];

int test(void)
{
  return a[3].foo();
}

int test2(struct B *b)
{
  return b->a.foo();
}

好吧，这些情况现在在 PR59883 中被跟踪。让我们看看C++前端开发人员是否同意。

这就是全部内容；关于前端内部去虚拟化实现及其限制的所有你从未想知道的内容。下次我将写关于基本中端技术的内容。

作者：Jan Hubička, Google +