Page MenuHomePhabricator

Implementation of a vtable interleaving algorithm
Needs ReviewPublic

Authored by zhaomo on Aug 14 2018, 7:33 PM.



This patch implements a vtable interleaving algorithm, which can be used to efficiently implement vcall cfi and/or shrink the binary size.
More background and description about the algorithm can be found at

Diff Detail

Event Timeline

zhaomo created this revision.Aug 14 2018, 7:33 PM
zhaomo retitled this revision from Implementation of interleaving algorithm to Implementation of a vtable interleaving algorithm.Aug 14 2018, 7:38 PM
zhaomo edited the summary of this revision. (Show Details)
zhaomo updated this revision to Diff 160743.Aug 14 2018, 7:44 PM
pcc added a comment.Aug 15 2018, 3:22 PM

Please make sure that your patch is formatted to match the LLVM style. clang-format can do that for you.

A couple of other global style comments that clang-format won't take care of for you:

  • instead of writing (>baz, please write>baz.
  • no braces around the body of an if, for etc. statement if it consists of a single statement. That includes nested statements which should be rewritten as
if (foo)
  for (auto bar : baz)

There's a problem here that I only just noticed (sorry). Type identifiers are not guaranteed to be MDStrings -- they can also be distinct MDNodes if the type has internal linkage (see for how this is handled in the frontend) -- these MDNodes are deliberately not convertible to strings because they need to be scoped to the translation unit. So I think you will need to create a new metadata kind here: and attach it to the global variables that you create in order to provide the mapping from global variables to metadata.


I don't think we should expect there to be any particular type of initializer on these variables; the initializer that they're created with in the frontend is arbitrary because nobody should be reading from them.


I think you can replace this function with a call to getAggregateElement:


I'd declare a struct type for this data structure instead of using std::tuple so that you can give an appropriate name to each field.


Why is this commented out?


I don't think you need this line because you should always expect there to be at least one global in the set.


The comment should talk about how this is a requirement in order to group the vtables correctly.


I'd inline the verifyTypeMDNode function here because the function's name doesn't correspond to its return value.


This should assert that all offsets are the same. We shouldn't expect to see different offsets here except for with the metadata associated with virtual member function pointers. And on the frontend side we should disable member function pointer metadata when interleaving is enabled since there would need to be a number of other things fixed before we could turn that on.


I'd call this something like -enable-vtable-interleaving. The name of the variable should also match the name of the flag like the other variables.


I'd expect this line to be in an else clause after your if statement above.

zhaomo updated this revision to Diff 161878.EditedAug 21 2018, 7:15 PM

Addressed issues pointed out by pcc

pcc added inline comments.Aug 22 2018, 3:51 PM

I think this function can still be simplified. For example, do you still need the Fragments array? It seems like you only need to keep track of whether each GlobalVariable has been seen before and which Metadata it was last seen with.


This will end up adding the globals in an order determined by their pointer values, which I believe will make the order of the elements added to ExclusiveVTables non-deterministic. As I mentioned in another comment I think this should take a vector (or, perhaps better, an ArrayRef).


You can just insert the new type, the set will take care of deduplication. Since this will be another source of non-determinism, I'd suggest using a SetVector instead of a std::set.


Maybe do the lookup once:

TypeInterleavingInfo &Info = InterleavingInfoMap[BaseType];

and use Info in the rest of the code?


I think that for determinism this needs to be a MapVector and the set needs to be a vector. I think you could initialize it here by adding empty values for each element of TypeIds here (after following my other suggestion to pass that instead of TypeAndUniqueIds).


With my above suggestion this can now be a lookup on TypeMembersMap.


Could this be a std::stable_sort on the size alone?


What do you think about putting the offset in the metadata as an additional operand?


Is it necessary to create this map? It looks like handleDisjointSet never uses the values so you can just pass in TypeIds.


Shouldn't there be a part of this test (and others) that uses these variables so that you can check that they've been replaced with the correct values?


typ -> type


nit: Bad wrapping


These STL includes don't seem like they're required here.


nit: more bad line wrapping


nit: Variable*


nit: Typd -> Type


nit: -d


nit: no brackets here


nit: vectors


Should this be OrderedGlobals?

1 ↗(On Diff #161878)

File name typo: incomplete

9 ↗(On Diff #161878)

initialized (here and the line below)


initialized (here and the line below)

zhaomo updated this revision to Diff 162314.Aug 23 2018, 5:45 PM

Fix the issues pointed out by Peter and Vlad.

pcc added inline comments.Aug 24 2018, 6:04 PM

Nit: UpperEntries


Please write the type here instead of auto. We generally write out the type unless it's obvious what it is.


Should this be in an #ifdef ENABLE_EXPENSIVE_CHECKS block?


Can the block of code that handles ConstantDataArray be removed if you use getAggregateElement above?


I think this won't correctly handle pointers that are not of type i8* (because inttoptr doesn't work on pointers). This should use a bitcast if the operand is a pointer.


Please write the type here.


You don't need this variable, you can just write TII.ExclusiveVTables everywhere.


Same for these.

zhaomo updated this revision to Diff 162733.Aug 27 2018, 1:15 PM
zhaomo updated this revision to Diff 162783.Aug 27 2018, 5:52 PM
zhaomo updated this revision to Diff 164782.Sep 10 2018, 6:34 PM

Fixed some bugs

pcc added inline comments.Sep 11 2018, 1:18 PM



Maybe move this check to interleaveGlobalVariables where you access the global variables?


Instead of using PointerType::get(OffsetGVTy, 0) here you can just use OGV->getType() and drop the OffsetGVTy field.

zhaomo updated this revision to Diff 165416.Sep 13 2018, 9:10 PM

Fixed issues pointed out by Peter.

pcc added inline comments.Sep 13 2018, 9:23 PM

You could write this as GlobalVariable &GV = *I++; and save needing to increment the iterator in several places below.


You don't need the continue on this line or the one below.

zhaomo updated this revision to Diff 195167.Apr 15 2019, 6:00 AM

Fixed some bugs in the previous implementation.

Herald added a project: Restricted Project. · View Herald TranscriptApr 15 2019, 6:00 AM
zhaomo updated this revision to Diff 221138.Sep 20 2019, 4:55 PM
ychen added a subscriber: ychen.Sep 20 2019, 5:00 PM
zhaomo updated this revision to Diff 221141.Sep 20 2019, 5:03 PM

This patch fixed a few bugs that can be triggered by some corner cases involved with virtual inheritance.

I tested the implementation with the Android and the Linux versions of Chromium, and SPEC 2006.

For the Android version of Chromium, this implementation introduces about 2.5% code bloat overhead (baseline: full LTO, O1 for LTO, CFI-VCall disabled). In comparison, the upstream LLVM CFI-VCall introduces about 5.5%.

Currently this passes relies on offset global variables and calls to llvm.type.test to determine the set of types that are subject to vtable interleaving. If we have a way to do so without using calls to llvm.type.test, we can decouple this pass and CFI, making it a more independent optimization pass.

Because the offset global variables captures all the vtable accesses to the vtables subject to interleaving, this pass can remove unused vtable entries. Similarly, we could use offset global variables to remove unused virtual member functions. I wrote a separate pass for this and it works quite well.