Stripping Leading/Trailing Zeros in Bit Vectors¶

If a bit vector contains leading or trailing zeros, we can strip them from the vector. The compiler will emit code to check if the pointer is in range of the region covered by ones, and perform the bit vector check using a truncated version of the bit vector. For example, the bit vectors for our example class hierarchy will be emitted like this:

Short Inline Bit Vectors¶

If the vector is sufficiently short, we can represent it as an inline constant on x86. This saves us a few instructions when reading the correct element of the bit vector.

If the bit vector fits in 32 bits, the code looks like this:

 dc2:       48 8b 03                mov    (%rbx),%rax
 dc5:       48 8d 15 14 1e 00 00    lea    0x1e14(%rip),%rdx
 dcc:       48 89 c1                mov    %rax,%rcx
 dcf:       48 29 d1                sub    %rdx,%rcx
 dd2:       48 c1 c1 3d             rol    $0x3d,%rcx
 dd6:       48 83 f9 03             cmp    $0x3,%rcx
 dda:       77 2f                   ja     e0b <main+0x9b>
 ddc:       ba 09 00 00 00          mov    $0x9,%edx
 de1:       0f a3 ca                bt     %ecx,%edx
 de4:       73 25                   jae    e0b <main+0x9b>
 de6:       48 89 df                mov    %rbx,%rdi
 de9:       ff 10                   callq  *(%rax)
[...]
 e0b:       0f 0b                   ud2

Or if the bit vector fits in 64 bits:

11a6:       48 8b 03                mov    (%rbx),%rax
11a9:       48 8d 15 d0 28 00 00    lea    0x28d0(%rip),%rdx
11b0:       48 89 c1                mov    %rax,%rcx
11b3:       48 29 d1                sub    %rdx,%rcx
11b6:       48 c1 c1 3d             rol    $0x3d,%rcx
11ba:       48 83 f9 2a             cmp    $0x2a,%rcx
11be:       77 35                   ja     11f5 <main+0xb5>
11c0:       48 ba 09 00 00 00 00    movabs $0x40000000009,%rdx
11c7:       04 00 00
11ca:       48 0f a3 ca             bt     %rcx,%rdx
11ce:       73 25                   jae    11f5 <main+0xb5>
11d0:       48 89 df                mov    %rbx,%rdi
11d3:       ff 10                   callq  *(%rax)
[...]
11f5:       0f 0b                   ud2

If the bit vector consists of a single bit, there is only one possible virtual table, and the check can consist of a single equality comparison:

9a2:   48 8b 03                mov    (%rbx),%rax
9a5:   48 8d 0d a4 13 00 00    lea    0x13a4(%rip),%rcx
9ac:   48 39 c8                cmp    %rcx,%rax
9af:   75 25                   jne    9d6 <main+0x86>
9b1:   48 89 df                mov    %rbx,%rdi
9b4:   ff 10                   callq  *(%rax)
[...]
9d6:   0f 0b                   ud2

Virtual Table Layout¶

The compiler lays out classes of disjoint hierarchies in separate regions of the object file. At worst, bit vectors in disjoint hierarchies only need to cover their disjoint hierarchy. But the closer that classes in sub-hierarchies are laid out to each other, the smaller the bit vectors for those sub-hierarchies need to be (see “Stripping Leading/Trailing Zeros in Bit Vectors” above). The GlobalLayoutBuilder class is responsible for laying out the globals efficiently to minimize the sizes of the underlying bitsets.

Alignment¶

If all gaps between address points in a particular bit vector are multiples of powers of 2, the compiler can compress the bit vector by strengthening the alignment requirements of the virtual table pointer. For example, given this class hierarchy:

struct A {
  virtual void f1();
  virtual void f2();
};

struct B : A {
  virtual void f1();
  virtual void f2();
  virtual void f3();
  virtual void f4();
  virtual void f5();
  virtual void f6();
};

struct C : A {
  virtual void f1();
  virtual void f2();
};

The virtual tables will be laid out like this:

Notice that each address point for A is separated by 4 words. This lets us emit a compressed bit vector for A that looks like this:

At call sites, the compiler will strengthen the alignment requirements by using a different rotate count. For example, on a 64-bit machine where the address points are 4-word aligned (as in A from our example), the rol instruction may look like this:

dd2:       48 c1 c1 3b             rol    $0x3b,%rcx

Padding to Powers of 2¶

Of course, this alignment scheme works best if the address points are in fact aligned correctly. To make this more likely to happen, we insert padding between virtual tables that in many cases aligns address points to a power of 2. Specifically, our padding aligns virtual tables to the next highest power of 2 bytes; because address points for specific base classes normally appear at fixed offsets within the virtual table, this normally has the effect of aligning the address points as well.

This scheme introduces tradeoffs between decreased space overhead for instructions and bit vectors and increased overhead in the form of padding. We therefore limit the amount of padding so that we align to no more than 128 bytes. This number was found experimentally to provide a good tradeoff.

Eliminating Bit Vector Checks for All-Ones Bit Vectors¶

If the bit vector is all ones, the bit vector check is redundant; we simply need to check that the address is in range and well aligned. This is more likely to occur if the virtual tables are padded.