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 https://reviews.llvm.org/D50372
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 (foo.bar)->baz, please write foo.bar->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) f(bar);
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 http://llvm-cs.pcc.me.uk/tools/clang/lib/CodeGen/CodeGenModule.cpp#4986 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: http://llvm-cs.pcc.me.uk/include/llvm/IR/LLVMContext.h#99 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: http://llvm-cs.pcc.me.uk/lib/IR/Constants.cpp#328
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.
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: Typd -> Type
nit: no brackets here
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)
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.
Restore the #ifdef ENABLE_EXPENSIVE_CHECKS.
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.
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.