WholeProgramDevirt: introduce.

[pcc]

Summary

This pass implements whole program optimization of virtual calls in cases
where we know (via bitset information) that the list of callee is fixed. This
includes the following:

• Single implementation devirtualization: if a virtual call has a single possible callee, replace all calls with a direct call to that callee.

• Virtual constant propagation: if the virtual function's return type is an integer <=64 bits and all possible callees are readnone, for each class and each list of constant arguments: evaluate the function, store the return value alongside the virtual table, and rewrite each virtual call as a load from the virtual table.

• Uniform return value optimization: if the conditions for virtual constant propagation hold and each function returns the same constant value, replace each virtual call with that constant.

• Unique return value optimization for i1 return values: if the conditions for virtual constant propagation hold and a single vtable's function returns 0, or a single vtable's function returns 1, replace each virtual call with a comparison of the vptr against that vtable's address.

[pete]

Hi Peter

This is great. Although also quite large, so apologies in advance if it takes a few rounds of review.

Firstly, can you do the evaluator stuff in another patch. I'm ok saying LGTM on that here assuming that you only extracted the code from GlobalOpt. That'll greatly reduce the scope of what we have here.

Also, I know Chandler has been passionate about data structure choices in the past. Luckily he's already CCed here, but i'd double check with him whether things like std::set and std::map are reasonable choices for what you're doing here.

Thanks,
Pete

lib/Transforms/IPO/LowerBitSets.cpp

923 ↗

(On Diff #46612)

Is this needed for this patch? I know its just an optimization, but can it be committed separately?

lib/Transforms/IPO/PassManagerBuilder.cpp

640

Before this is enabled in tree by default (I can see from the clang patch that you have an option to control this), we'll need perf testing and sign off from LTO folks. Mehdi is CCed which is good, but probably also need some other interested folks and some data to go over to justify the GlobalDCE pass as well as the new code in terms of compile/runtime.

lib/Transforms/IPO/WholeProgramDevirt.cpp

11–27

The tests you've included are very good in terms of ensuring all of this is covered. However, can you please add negative tests for everything too. At least one test for each of the main points would be good, for example, a test returning an i128 doesn't get virtual constant propagation.

113

Nitpicking: space between the ;;

116

Please use () here around the + and / operators to make it clear what precedence you want.

175

You're comparing pointers here. Is that safe/intended?

282

This method is pretty huge. Can you break it out in to one method for each type of optimization you are doing? That would make it easier to review each chunk individually.

305

This is highly unlikely, but there's no guarantee that the user is a CallInst here (or in any of the other similar casts in your patch).

Unfortunately, you could have something like 'call ... (bitcast i1 @llvm.bitset.test to ...)

308–311

As you are using an intrinsic here, seems fair to just use a cast<MetadataAsValue> instead of report_fatal_error as either way you'll know if anyone changes the intrinsic types.

334

You can use RecursivelyDeleteTriviallyDeadInstructions instead to also delete any dead arguments to the call.

[pete]

Added Gerolf who is always interested in new LTO optimizations.

[pcc]

• Remove llvm:: in a few places
• Parens
• We can't use RecursivelyDeleteTriviallyDeadInstructions
• Better casting
• Move code into functions; fix some non-determinism
• Use DenseSet
• Simplify a little
• Add negative tests

[pcc]

Firstly, can you do the evaluator stuff in another patch. I'm ok saying LGTM on that here assuming that you only extracted the code from GlobalOpt.

Done in r259621.

lib/Transforms/IPO/LowerBitSets.cpp

923 ↗

(On Diff #46612)

It isn't needed for this patch specifically. I've committed it separately in r259625.

lib/Transforms/IPO/PassManagerBuilder.cpp

640

As one data point: I timed the GlobalDCE pass running over a full LTO module of Chromium at about 3 seconds on my machine. That's less than 1% of total runtime (about 20-30 mins), so I think it's tolerable. I'll also get numbers for this new pass, but I don't think it should affect code that doesn't use the whole-program-vtables feature.

lib/Transforms/IPO/WholeProgramDevirt.cpp

113

That isn't what clang-format does, and I'd prefer to stick with that formatting where reasonable.

175

This was safe before because I was iterating over an associated std::vector. But I realized that the code can just use a MapVector instead, so I've done that.

334

It turns out that we can't do this too early because CI may be the only user of the vtable. It's probably simplest to let another pass clean up the other arguments later.

[pete]

In D16795#343746, @pcc wrote:

• Remove llvm:: in a few places
• Parens
• Better casting
• Move code into functions; fix some non-determinism
• Use DenseSet
• Simplify a little
• Add negative tests

Thanks for all of those. They look good.

Regarding this one:

• We can't use RecursivelyDeleteTriviallyDeadInstructions

I hadn't realized you were caching the found calls, so makes sense you can't delete them with this. Thanks for the comment in the code saying so.

Also, thanks for the extensive tests.

I've now gone through the whole patch. I was able to follow along very well so kudos for the good comments and sensible naming on everything.

I don't think there's anything i've commented on here that needs further review. Please fix any comments I had which you feel are reasonable, ignore those which should be ignored, and LGTM :)

lib/Transforms/IPO/PassManagerBuilder.cpp

640

Thanks for the data. 3s isn't bad at all considering how big that Module is likely to be.

I'm going to take a look at what this does to LLVM itself when we link only a single backend, but my curiously there shouldn't block further progress on this.

lib/Transforms/IPO/WholeProgramDevirt.cpp

113

Didn't realize that was the clang-format behavior. No problem keeping it the way it is then :)

208–210

I don't tend to work with InvokeInst much. I trust that what you're doing here is correct, but please add a test to cover it just to make sure it keeps being ok in future.

295

Nitpicking: Please swap the order here as checking 'VPtr == GEP->getPointerOperand()' is faster than GEP->hasAllConstantIndices()

296–298

This is pretty gross (not your fault! I looked and most other places do exactly the same thing)

But I did see one that was much nicer. Its in ConstantFolding.cpp. Can you make yours similar? I might go back and fix the others in tree.

Note, it was getting a range from a vector of indices, but I think it might be possible to do the equivalent with op_begin() + 1 and op_end().

makeArrayRef((Value * const *)Ops.data() + 1, Ops.size() - 1)));

586

Can you move this in to the 'if (!Assumes.empty()) {' below as I think its only used in there.

615

Can we test for this being non-null as the very first thing in runModule? Or do you want to erase all the assume's as in the previous loop, even if you can't find the metadata?

If you do keep the conditional here, looks like you could move BitSets inside the scope, as well as moving the "// For each (bitset, offset) pair:" loop to the end of the conditional block

630–631

In addition to these checks, it looks like BitSets is only used by tryFindVirtualCallTargets, and the first thing we do in there is check the following:

if (!BS.Bits->GV->isConstant())
    return false;

  auto Init = dyn_cast<ConstantArray>(BS.Bits->GV->getInitializer());
  if (!Init)
    return false;

Can we move those checks here so that we don't even populate BitSets[] entries unless these properties hold?

662–669

I think you could have a 'bool Changed' to track if tryVirtualConstProp ever did anything and only run this loop if thats the case. Is that right?

677–679

Please do something like 'I = 0, Size = B.Before.Bytes.Size()' so that you can avoid reevaluating the size on each iteration and inside the loop body

702

No idea if this is possible, so feel free to ignore, but if the original VT had an explicit section on it, would either NewGV or Alias here need to inherit that section? I have no idea what the correct answer would be.

For safety sake, we could always exclude VTables with explicit sections from this optimization until we have a good answer.

Either way, please add a test with an explicit section and make sure we either propagate it as required, or don't run this optimization on it.

[mehdi_amini]

Looking what's involved, I am not convinced that the current "bitset"/assume intrinsics structure is the most straightforward/efficient representation to communicate the information from the front-end to the analysis. It seems to complicate quite noticeably the implementation here.

lib/Transforms/IPO/PassManagerBuilder.cpp

644

This is the beginning of the pipeline right? When do we have unused virtual tables emitted by the front-end? I don't expect this to happen.

lib/Transforms/IPO/WholeProgramDevirt.cpp

216

That's not friendly to the new pass manager, can you refactor with a very thin wrapper class inheriting from ModulePass and a class for the Devirtualizer itself?

258

There is a INITIALIZE_PASS macro that does the job if you don't need dependencies.

558

This function is pretty long and could probably be split.

602

It seems to me that you have to reconstruct information that could have been generated by the front-end, using a representation like the intrinsic I sent by email.
This would make completely straightforward since you'd have all the uses off-hand.

616

Could be documented (and renamed maybe?)

[pcc]

• Add invoke test; fix invoke replacement bug
• Use INITIALIZE_PASS
• Move most of the code into a separate struct
• Move buildBitSets to function
• Move rebuildGlobal to function
• Address misc code review comments, add support for explicit sections

lib/Transforms/IPO/PassManagerBuilder.cpp

644

This happens after the internalizer pass. If a vtable is linked into the program but turns out to be unused from a whole-program perspective, this pass will remove it.

lib/Transforms/IPO/WholeProgramDevirt.cpp

208–210

Added a test. Good thing I did, because this code contained a bug, which is now fixed.

296–298

I don't think this will work because op_begin()..op_end() is an iterator of Uses, not Values.

602

While this is true, it isn't clear that the lowered complexity here would not be outweighed by added complexity in the rest of the compiler. For example, if we adopt a design similar to the one you proposed,other parts of the compiler (e.g. constant folding) would need to be taught about the new intrinsic, and the information from the frontend would need to be kept in sync with the program semantics. The advantage of reconstructing information from program semantics is that we know that the semantics are most likely correct, or the program wouldn't work.

Before we consider changing the design, I would like to see a concrete design proposal that takes into account existing features such as CFI. I don't think any potential new design should block this from landing though.

630–631

If we encounter one of these, we need to disable the optimization for that bitset only. I suppose we could either keep track of which bitsets we need to disable optimization for, or disable optimization for all bitsets if we see one of these (by clearing BitSets and returning), but at that point we're making the code more complicated and/or losing a feature.

702

I don't think this comes up with real vtables, but NewGV would need to inherit the section (aliases can't have explicit sections). Added test.

[pete]

lib/Transforms/IPO/WholeProgramDevirt.cpp

332–348

Sorry, don't know how to reply to this point correctly in Phab, but here goes:

So this is the current code to add an entry to BitSets[]. This is where I think we could move the following checks, as that way we know that all elements in BitSets have valid GlobalValue's according to these checks. I don't think thats too bad so long as we can move the checks here. Obviously if for some reason we had to duplicate the checks then your current code is better.

These are the checks I'm thinking of:

if (!BS.Bits->GV->isConstant())

  return false;

auto Init = dyn_cast<ConstantArray>(BS.Bits->GV->getInitializer());
if (!Init)
  return false;

[pcc]

lib/Transforms/IPO/WholeProgramDevirt.cpp

332–348

If an element has an invalid GlobalValue according to those checks, we cannot apply the optimization for that bitset, because it would be an invalid optimization. Consider:

@vt1 = global [1 x i8*] [i8* bitcast void()* @vf1 to i8*]
@vt2 = constant [1 x i8*] [i8* bitcast void()* @vf2 to i8*]


void @f(i8* %this) {
  %vtable = load %this
  llvm.assume(llvm.bitset.test(%vtable, !"bitset"))
  ; make a virtual call through %vtable
}

!0 = {!"bitset", @vt1, 0}
!1 = {!"bitset", @vt2, 0}
!llvm.bitsets = !{!0, !1}

If we do those checks here, the pass would add only @vt2 to BitSets["bitset"], and it would later apply single-implementation devirtualization to turn the virtual call in @f into a direct call to @vf2. But that would not be correct, because it could potentially be a call to @vf1 (or potentially any other function, if some other code overwrites the pointer in @vt1).

Because we expect this case to never arise in practice, the simplest thing to do is to handle it in the loop later.

[mehdi_amini]

LGTM, unless Pete has more changes to ask pre-commit?

lib/Transforms/IPO/PassManagerBuilder.cpp

644

I didn't expect internalize alone to expose such opportunities, but yes thinking more about it I can foresee that.

lib/Transforms/IPO/WholeProgramDevirt.cpp

604

I still regret that the design of the IR representation haven't been considered any further. In many other cases such a feature would be block on such consideration (Technical debt). As much as this is not widespread, it still involves changes in the frontend, so it is not completly isolated. It seems to me that CFI acts as a Trojan horse here. It is not clear to me if the actual "bitset" has any other justification for its existence that being the clever and efficient *runtime* system that CFI is using. Now I can be totally wrong and it is possible that when CFI was integrated, the IR representation was carefully designed independently of the actual CFI runtime, I just don't have time to dig in the history.

[pcc]

lib/Transforms/IPO/WholeProgramDevirt.cpp

604

I feel in general that it's best not to do too much design up-front in cases where it can be avoided, as that can lead to a sub-optimal design. In this case, we control the frontend, so it's certainly possible to reverse out of any bad decisions we make here. Instead, I feel it's best to revisit the design in response to feature requirements. For example, as I implement llvm.bitset.check and some of the ABI breaking features discussed on the proposal thread I expect I'll end up tweaking the design in response to them, and the ultimate design will be better for it.

include/llvm/InitializePasses.h

 void initializeFloat2IntPass(PassRegistry&);
 void initializeLoopDistributePass(PassRegistry&);
 void initializeSjLjEHPreparePass(PassRegistry&);
 void initializeDemandedBitsPass(PassRegistry&);
 void initializeFuncletLayoutPass(PassRegistry &);
 void initializeLoopLoadEliminationPass(PassRegistry&);
 void initializeFunctionImportPassPass(PassRegistry &);
 void initializeLoopVersioningPassPass(PassRegistry &);
+void initializeWholeProgramDevirtPass(PassRegistry &);
 }
 
 #endif

include/llvm/Transforms/IPO.h

 
 /// \brief This pass lowers bitset metadata and the llvm.bitset.test intrinsic
 /// to bitsets.
 ModulePass *createLowerBitSetsPass();
 
 /// \brief This pass export CFI checks for use by external modules.
 ModulePass *createCrossDSOCFIPass();
 
+/// \brief This pass implements whole-program devirtualization using bitset
+/// metadata.
+ModulePass *createWholeProgramDevirtPass();
+
 //===----------------------------------------------------------------------===//
 // SampleProfilePass - Loads sample profile data from disk and generates
 // IR metadata to reflect the profile.
 ModulePass *createSampleProfileLoaderPass();
 ModulePass *createSampleProfileLoaderPass(StringRef Name);
 
 } // End llvm namespace
 
 #endif

include/llvm/Transforms/IPO/PassManagerBuilder.h

public:
   static void addGlobalExtension(ExtensionPointTy Ty, ExtensionFn Fn);
   void addExtension(ExtensionPointTy Ty, ExtensionFn Fn);
 
 private:
   void addExtensionsToPM(ExtensionPointTy ETy,
                          legacy::PassManagerBase &PM) const;
   void addInitialAliasAnalysisPasses(legacy::PassManagerBase &PM) const;
   void addLTOOptimizationPasses(legacy::PassManagerBase &PM);
+  void addEarlyLTOOptimizationPasses(legacy::PassManagerBase &PM);
   void addLateLTOOptimizationPasses(legacy::PassManagerBase &PM);
   void addPGOInstrPasses(legacy::PassManagerBase &MPM);
 
 public:
   /// populateFunctionPassManager - This fills in the function pass manager,
   /// which is expected to be run on each function immediately as it is
   /// generated.  The idea is to reduce the size of the IR in memory.
   void populateFunctionPassManager(legacy::FunctionPassManager &FPM);

include/llvm/Transforms/IPO/WholeProgramDevirt.h

+//===- WholeProgramDevirt.h - Whole-program devirt pass ---------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines parts of the whole-program devirtualization pass
+// implementation that may be usefully unit tested.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
+#define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMapInfo.h"
+#include <utility>
+#include <vector>
+#include <assert.h>
+#include <stdint.h>
+
+namespace llvm {
+
+class Function;
+class GlobalVariable;
+
+namespace wholeprogramdevirt {
+
+// A bit vector that keeps track of which bits are used. We use this to
+// pack constant values compactly before and after each virtual table.
+struct AccumBitVector {
+  std::vector<uint8_t> Bytes;
+
+  // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not.
+  std::vector<uint8_t> BytesUsed;
+
+  std::pair<uint8_t *, uint8_t *> getPtrToData(uint64_t Pos, uint8_t Size) {
+    if (Bytes.size() < Pos + Size) {
+      Bytes.resize(Pos + Size);
+      BytesUsed.resize(Pos + Size);
+    }
+    return std::make_pair(Bytes.data() + Pos, BytesUsed.data() + Pos);
+  }
+
+  // Set little-endian value Val with size Size at bit position Pos,
+  // and mark bytes as used.
+  void setLE(uint64_t Pos, uint64_t Val, uint8_t Size) {
+    assert(Pos % 8 == 0);
+    auto DataUsed = getPtrToData(Pos / 8, Size);
+    for (unsigned I = 0; I != Size; ++I) {
+      DataUsed.first[I] = Val >> (I * 8);
+      assert(!DataUsed.second[I]);
+      DataUsed.second[I] = 0xff;
+    }
+  }
+
+  // Set big-endian value Val with size Size at bit position Pos,
+  // and mark bytes as used.
+  void setBE(uint64_t Pos, uint64_t Val, uint8_t Size) {
+    assert(Pos % 8 == 0);
+    auto DataUsed = getPtrToData(Pos / 8, Size);
+    for (unsigned I = 0; I != Size; ++I) {
+      DataUsed.first[Size - I - 1] = Val >> (I * 8);
+      assert(!DataUsed.second[Size - I - 1]);
+      DataUsed.second[Size - I - 1] = 0xff;
+    }
+  }
+
+  // Set bit at bit position Pos to b and mark bit as used.
+  void setBit(uint64_t Pos, bool b) {
+    auto DataUsed = getPtrToData(Pos / 8, 1);
+    if (b)
+      *DataUsed.first |= 1 << (Pos % 8);
+    assert(!(*DataUsed.second & (1 << Pos % 8)));
+    *DataUsed.second |= 1 << (Pos % 8);
+  }
+};
+
+// The bits that will be stored before and after a particular vtable.
+struct VTableBits {
+  // The vtable global.
+  GlobalVariable *GV;
+
+  // Cache of the vtable's size in bytes.
+  uint64_t ObjectSize = 0;
+
+  // The bit vector that will be laid out before the vtable. Note that these
+  // bytes are stored in reverse order until the globals are rebuilt. This means
+  // that any values in the array must be stored using the opposite endianness
+  // from the target.
+  AccumBitVector Before;
+
+  // The bit vector that will be laid out after the vtable.
+  AccumBitVector After;
+};
+
+// Information about an entry in a particular bitset.
+struct BitSetInfo {
+  // The VTableBits for the vtable.
+  VTableBits *Bits;
+
+  // The offset in bytes from the start of the vtable (i.e. the address point).
+  uint64_t Offset;
+
+  bool operator<(const BitSetInfo &other) const {
+    return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset);
+  }
+};
+
+// A virtual call target, i.e. an entry in a particular vtable.
+struct VirtualCallTarget {
+  VirtualCallTarget(Function *Fn, const BitSetInfo *BS);
+
+  // For testing only.
+  VirtualCallTarget(const BitSetInfo *BS, bool IsBigEndian)
+      : Fn(nullptr), BS(BS), IsBigEndian(IsBigEndian) {}
+
+  // The function stored in the vtable.
+  Function *Fn;
+
+  // A pointer to the bitset through which the pointer to Fn is accessed.
+  const BitSetInfo *BS;
+
+  // When doing virtual constant propagation, this stores the return value for
+  // the function when passed the currently considered argument list.
+  uint64_t RetVal;
+
+  // Whether the target is big endian.
+  bool IsBigEndian;
+
+  // The minimum byte offset before the address point. This covers the bytes in
+  // the vtable object before the address point (e.g. RTTI, access-to-top,
+  // vtables for other base classes) and is equal to the offset from the start
+  // of the vtable object to the address point.
+  uint64_t minBeforeBytes() const { return BS->Offset; }
+
+  // The minimum byte offset after the address point. This covers the bytes in
+  // the vtable object after the address point (e.g. the vtable for the current
+  // class and any later base classes) and is equal to the size of the vtable
+  // object minus the offset from the start of the vtable object to the address
+  // point.
+  uint64_t minAfterBytes() const { return BS->Bits->ObjectSize - BS->Offset; }
+
+  // The number of bytes allocated (for the vtable plus the byte array) before
+  // the address point.
+  uint64_t allocatedBeforeBytes() const {
+    return minBeforeBytes() + BS->Bits->Before.Bytes.size();
+  }
+
+  // The number of bytes allocated (for the vtable plus the byte array) after
+  // the address point.
+  uint64_t allocatedAfterBytes() const {
+    return minAfterBytes() + BS->Bits->After.Bytes.size();
+  }
+
+  // Set the bit at position Pos before the address point to RetVal.
+  void setBeforeBit(uint64_t Pos) {
+    assert(Pos >= 8 * minBeforeBytes());
+    BS->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal);
+  }
+
+  // Set the bit at position Pos after the address point to RetVal.
+  void setAfterBit(uint64_t Pos) {
+    assert(Pos >= 8 * minAfterBytes());
+    BS->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal);
+  }
+
+  // Set the bytes at position Pos before the address point to RetVal.
+  // Because the bytes in Before are stored in reverse order, we use the
+  // opposite endianness to the target.
+  void setBeforeBytes(uint64_t Pos, uint8_t Size) {
+    assert(Pos >= 8 * minBeforeBytes());
+    if (IsBigEndian)
+      BS->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size);
+    else
+      BS->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size);
+  }
+
+  // Set the bytes at position Pos after the address point to RetVal.
+  void setAfterBytes(uint64_t Pos, uint8_t Size) {
+    assert(Pos >= 8 * minAfterBytes());
+    if (IsBigEndian)
+      BS->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size);
+    else
+      BS->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size);
+  }
+};
+
+// Find the minimum offset that we may store a value of size Size bits at. If
+// IsAfter is set, look for an offset before the object, otherwise look for an
+// offset after the object.
+uint64_t findLowestOffset(ArrayRef<VirtualCallTarget> Targets, bool IsAfter,
+                          uint64_t Size);
+
+// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
+// given allocation offset before the vtable address. Stores the computed
+// byte/bit offset to OffsetByte/OffsetBit.
+void setBeforeReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
+                           uint64_t AllocBefore, unsigned BitWidth,
+                           int64_t &OffsetByte, uint64_t &OffsetBit);
+
+// Set the stored value in each of Targets to VirtualCallTarget::RetVal at the
+// given allocation offset after the vtable address. Stores the computed
+// byte/bit offset to OffsetByte/OffsetBit.
+void setAfterReturnValues(MutableArrayRef<VirtualCallTarget> Targets,
+                          uint64_t AllocAfter, unsigned BitWidth,
+                          int64_t &OffsetByte, uint64_t &OffsetBit);
+
+}
+}
+
+#endif

lib/Transforms/IPO/CMakeLists.txt

add_llvm_library(LLVMipo
   LowerBitSets.cpp
   MergeFunctions.cpp
   PartialInlining.cpp
   PassManagerBuilder.cpp
   PruneEH.cpp
   SampleProfile.cpp
   StripDeadPrototypes.cpp
   StripSymbols.cpp
+  WholeProgramDevirt.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/IPO
   )
 
 add_dependencies(LLVMipo intrinsics_gen)

lib/Transforms/IPO/IPO.cpp

void llvm::initializeIPO(PassRegistry &Registry) {
   initializeStripSymbolsPass(Registry);
   initializeStripDebugDeclarePass(Registry);
   initializeStripDeadDebugInfoPass(Registry);
   initializeStripNonDebugSymbolsPass(Registry);
   initializeBarrierNoopPass(Registry);
   initializeEliminateAvailableExternallyPass(Registry);
   initializeSampleProfileLoaderPass(Registry);
   initializeFunctionImportPassPass(Registry);
+  initializeWholeProgramDevirtPass(Registry);
 }
 
 void LLVMInitializeIPO(LLVMPassRegistryRef R) {
   initializeIPO(*unwrap(R));
 }
 
 void LLVMAddArgumentPromotionPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createArgumentPromotionPass());

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
 
   // Cleanup and simplify the code after the scalar optimizations.
   PM.add(createInstructionCombiningPass());
   addExtensionsToPM(EP_Peephole, PM);
 
   PM.add(createJumpThreadingPass());
 }
 
+void PassManagerBuilder::addEarlyLTOOptimizationPasses(
+    legacy::PassManagerBase &PM) {
+  // Remove unused virtual tables to improve the quality of code generated by
+  // whole-program devirtualization and bitset lowering.
+  PM.add(createGlobalDCEPass());
+
+  // Apply whole-program devirtualization and virtual constant propagation.
+  PM.add(createWholeProgramDevirtPass());
+}
+
 void PassManagerBuilder::addLateLTOOptimizationPasses(
     legacy::PassManagerBase &PM) {
   // Delete basic blocks, which optimization passes may have killed.
   PM.add(createCFGSimplificationPass());
 
   // Drop bodies of available externally objects to improve GlobalDCE.
   PM.add(createEliminateAvailableExternallyPass());
 
   // Now that we have optimized the program, discard unreachable functions.
   PM.add(createGlobalDCEPass());
 
   // FIXME: this is profitable (for compiler time) to do at -O0 too, but
   // currently it damages debug info.
   if (MergeFunctions)
     PM.add(createMergeFunctionsPass());
 }
 
 void PassManagerBuilder::populateLTOPassManager(legacy::PassManagerBase &PM) {
   if (LibraryInfo)
     PM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
 
   if (VerifyInput)
     PM.add(createVerifierPass());
 
+  if (OptLevel != 0)
+    addEarlyLTOOptimizationPasses(PM);
+
   if (OptLevel > 1)
     addLTOOptimizationPasses(PM);
 
   // Create a function that performs CFI checks for cross-DSO calls with targets
   // in the current module.
   PM.add(createCrossDSOCFIPass());
 
   // Lower bit sets to globals. This pass supports Clang's control flow

lib/Transforms/IPO/WholeProgramDevirt.cpp

+//===- WholeProgramDevirt.cpp - Whole program virtual call optimization ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass implements whole program optimization of virtual calls in cases
+// where we know (via bitset information) that the list of callee is fixed. This
+// includes the following:
+// - Single implementation devirtualization: if a virtual call has a single
+//   possible callee, replace all calls with a direct call to that callee.
+// - Virtual constant propagation: if the virtual function's return type is an
+//   integer <=64 bits and all possible callees are readnone, for each class and
+//   each list of constant arguments: evaluate the function, store the return
+//   value alongside the virtual table, and rewrite each virtual call as a load
+//   from the virtual table.
+// - Uniform return value optimization: if the conditions for virtual constant
+//   propagation hold and each function returns the same constant value, replace
+//   each virtual call with that constant.
+// - Unique return value optimization for i1 return values: if the conditions
+//   for virtual constant propagation hold and a single vtable's function
+//   returns 0, or a single vtable's function returns 1, replace each virtual
+//   call with a comparison of the vptr against that vtable's address.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO/WholeProgramDevirt.h"
+#include "llvm/Transforms/IPO.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/Evaluator.h"
+#include "llvm/Transforms/Utils/Local.h"
+
+#include <set>
+
+using namespace llvm;
+using namespace wholeprogramdevirt;
+
+#define DEBUG_TYPE "wholeprogramdevirt"
+
+// Find the minimum offset that we may store a value of size Size bits at. If
+// IsAfter is set, look for an offset before the object, otherwise look for an
+// offset after the object.
+uint64_t
+wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets,
+                                     bool IsAfter, uint64_t Size) {
+  // Find a minimum offset taking into account only vtable sizes.
+  uint64_t MinByte = 0;
+  for (const VirtualCallTarget &Target : Targets) {
+    if (IsAfter)
+      MinByte = std::max(MinByte, Target.minAfterBytes());
+    else
+      MinByte = std::max(MinByte, Target.minBeforeBytes());
+  }
+
+  // Build a vector of arrays of bytes covering, for each target, a slice of the
+  // used region (see AccumBitVector::BytesUsed above) starting at MinByte.
+  // Effectively, this aligns the used regions to start at MinByte.
+  //
+  // In this example, A, B and C are vtables, # is a byte already allocated for
+  // a virtual function pointer, AAAA... (etc.) are the used regions for the
+  // vtables and Offset(X) is the value computed for the Offset variable below
+  // for X.
+  //
+  //                    Offset(A)
+  //                    |       |
+  //                            |MinByte
+  // A: ################AAAAAAAA|AAAAAAAA
+  // B: ########BBBBBBBBBBBBBBBB|BBBB
+  // C: ########################|CCCCCCCCCCCCCCCC
+  //            |   Offset(B)   |
+  //
+  // This code produces the slices of A, B and C that appear after the divider
+  // at MinByte.
+  std::vector<ArrayRef<uint8_t>> Used;
+  for (const VirtualCallTarget &Target : Targets) {
+    ArrayRef<uint8_t> VTUsed = IsAfter ? Target.BS->Bits->After.BytesUsed
+                                       : Target.BS->Bits->Before.BytesUsed;
+    uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes()
+                              : MinByte - Target.minBeforeBytes();
+
+    // Disregard used regions that are smaller than Offset. These are
+    // effectively all-free regions that do not need to be checked.
+    if (VTUsed.size() > Offset)
+      Used.push_back(VTUsed.slice(Offset));
+  }
+
+  if (Size == 1) {
+    // Find a free bit in each member of Used.
+    for (unsigned I = 0;; ++I) {
+      uint8_t BitsUsed = 0;
+      for (auto &&B : Used)
+        if (I < B.size())
+          BitsUsed |= B[I];
+      if (BitsUsed != 0xff)
+        return (MinByte + I) * 8 +
+               countTrailingZeros(uint8_t(~BitsUsed), ZB_Undefined);
+    }
+  } else {
+    // Find a free (Size/8) byte region in each member of Used.
+    // FIXME: see if alignment helps.
+    for (unsigned I = 0;; ++I) {
+      for (auto &&B : Used) {
+        unsigned Byte = 0;
+        while ((I + Byte) < B.size() && Byte < (Size / 8)) {
+          if (B[I + Byte])
+            goto NextI;
+          ++Byte;
+        }
+      }
+      return (MinByte + I) * 8;
+    NextI:;
+    }
+  }
+}
+
+void wholeprogramdevirt::setBeforeReturnValues(
+    MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocBefore,
+    unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
+  if (BitWidth == 1)
+    OffsetByte = -(AllocBefore / 8 + 1);
+  else
+    OffsetByte = -((AllocBefore + 7) / 8 + (BitWidth + 7) / 8);
+  OffsetBit = AllocBefore % 8;
+
+  for (VirtualCallTarget &Target : Targets) {
+    if (BitWidth == 1)
+      Target.setBeforeBit(AllocBefore);
+    else
+      Target.setBeforeBytes(AllocBefore, (BitWidth + 7) / 8);
+  }
+}
+
+void wholeprogramdevirt::setAfterReturnValues(
+    MutableArrayRef<VirtualCallTarget> Targets, uint64_t AllocAfter,
+    unsigned BitWidth, int64_t &OffsetByte, uint64_t &OffsetBit) {
+  if (BitWidth == 1)
+    OffsetByte = AllocAfter / 8;
+  else
+    OffsetByte = (AllocAfter + 7) / 8;
+  OffsetBit = AllocAfter % 8;
+
+  for (VirtualCallTarget &Target : Targets) {
+    if (BitWidth == 1)
+      Target.setAfterBit(AllocAfter);
+    else
+      Target.setAfterBytes(AllocAfter, (BitWidth + 7) / 8);
+  }
+}
+
+VirtualCallTarget::VirtualCallTarget(Function *Fn, const BitSetInfo *BS)
+    : Fn(Fn), BS(BS),
+      IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()) {}
+
+namespace {
+
+// A slot in a set of virtual tables. The BitSetID identifies the set of virtual
+// tables, and the ByteOffset is the offset in bytes from the address point to
+// the virtual function pointer.
+struct VTableSlot {
+  Metadata *BitSetID;
+  uint64_t ByteOffset;
+};
+
+}
+
+template <> struct DenseMapInfo<VTableSlot> {
+  static VTableSlot getEmptyKey() {
+    return {DenseMapInfo<Metadata *>::getEmptyKey(),
+            DenseMapInfo<uint64_t>::getEmptyKey()};
+  }
+  static VTableSlot getTombstoneKey() {
+    return {DenseMapInfo<Metadata *>::getTombstoneKey(),
+            DenseMapInfo<uint64_t>::getTombstoneKey()};
+  }
+  static unsigned getHashValue(const VTableSlot &I) {
+    return DenseMapInfo<Metadata *>::getHashValue(I.BitSetID) ^
+           DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);
+  }
+  static bool isEqual(const VTableSlot &LHS,
+                      const VTableSlot &RHS) {
+    return LHS.BitSetID == RHS.BitSetID && LHS.ByteOffset == RHS.ByteOffset;
+  }
+};
+
+namespace {
+
+// A virtual call site. VTable is the loaded virtual table pointer, and CS is
+// the indirect virtual call.
+struct VirtualCallSite {
+  Value *VTable;
+  CallSite CS;
+
+  void replaceAndErase(Value *New) {
+    CS->replaceAllUsesWith(New);
+    if (auto II = dyn_cast<InvokeInst>(CS.getInstruction())) {
+      BranchInst::Create(II->getUnwindDest(), CS.getInstruction());
+      II->getUnwindDest()->removePredecessor(II->getParent());
+    }
+    CS->eraseFromParent();
+  }
+};
+
+struct WholeProgramDevirt : public ModulePass {
+  static char ID;
+  Module *M;
+  IntegerType *Int8Ty;
+  PointerType *Int8PtrTy;
+  IntegerType *Int32Ty;
+
+  MapVector<VTableSlot, std::vector<VirtualCallSite>> CallSlots;
+
+  WholeProgramDevirt() : ModulePass(ID) {
+    initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry());
+  }
+  void findLoadCallsAtConstantOffset(Metadata *BitSet, Value *Ptr,
+                                     uint64_t Offset, Value *VTable);
+  void findCallsAtConstantOffset(Metadata *BitSet, Value *Ptr, uint64_t Offset,
+                                 Value *VTable);
+
+  bool tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
+                                 const std::set<BitSetInfo> &BitSetInfos,
+                                 uint64_t ByteOffset);
+  bool trySingleImplDevirt(ArrayRef<VirtualCallTarget> TargetsForSlot,
+                           MutableArrayRef<VirtualCallSite> CallSites);
+  bool tryEvaluateFunctionsWithArgs(
+      MutableArrayRef<VirtualCallTarget> TargetsForSlot,
+      ArrayRef<ConstantInt *> Args);
+  bool tryUniformRetValOpt(IntegerType *RetType,
+                           ArrayRef<VirtualCallTarget> TargetsForSlot,
+                           MutableArrayRef<VirtualCallSite> CallSites);
+  bool tryUniqueRetValOpt(unsigned BitWidth,
+                          ArrayRef<VirtualCallTarget> TargetsForSlot,
+                          MutableArrayRef<VirtualCallSite> CallSites);
+  bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
+                           ArrayRef<VirtualCallSite> CallSites);
+
+  bool runOnModule(Module &M);
+};
+
+} // anonymous namespace
+
+INITIALIZE_PASS_BEGIN(WholeProgramDevirt, "wholeprogramdevirt",
+                      "Whole program devirtualization", false, false)
+INITIALIZE_PASS_END(WholeProgramDevirt, "wholeprogramdevirt",
+                    "Whole program devirtualization", false, false)
+char WholeProgramDevirt::ID = 0;
+
+ModulePass *llvm::createWholeProgramDevirtPass() {
+  return new WholeProgramDevirt;
+}
+
+// Search for virtual calls that call FPtr and add them to CallSlots.
+void WholeProgramDevirt::findCallsAtConstantOffset(Metadata *BitSet,
+                                                   Value *FPtr,
+                                                   uint64_t Offset,
+                                                   Value *VTable) {
+  for (const Use &U : FPtr->uses()) {
+    Value *User = U.getUser();
+    if (isa<BitCastInst>(User)) {
+      findCallsAtConstantOffset(BitSet, User, Offset, VTable);
+    } else if (auto CI = dyn_cast<CallInst>(User)) {
+      CallSlots[{BitSet, Offset}].push_back({VTable, CI});
+    } else if (auto II = dyn_cast<InvokeInst>(User)) {
+      CallSlots[{BitSet, Offset}].push_back({VTable, II});
+    }
+  }
+}
+
+// Search for virtual calls that load from VPtr and add them to CallSlots.
+void WholeProgramDevirt::findLoadCallsAtConstantOffset(Metadata *BitSet,
+                                                       Value *VPtr,
+                                                       uint64_t Offset,
+                                                       Value *VTable) {
+  for (const Use &U : VPtr->uses()) {
+    Value *User = U.getUser();
+    if (isa<BitCastInst>(User)) {
+      findLoadCallsAtConstantOffset(BitSet, User, Offset, VTable);
+    } else if (isa<LoadInst>(User)) {
+      findCallsAtConstantOffset(BitSet, User, Offset, VTable);
+    } else if (auto GEP = dyn_cast<GetElementPtrInst>(User)) {
+      // Take into account the GEP offset.
+      if (GEP->hasAllConstantIndices() && VPtr == GEP->getPointerOperand()) {
+        SmallVector<Value *, 8> Indices(GEP->op_begin() + 1, GEP->op_end());
+        uint64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType(
+            GEP->getSourceElementType(), Indices);
+        findLoadCallsAtConstantOffset(BitSet, User, Offset + GEPOffset, VTable);
+      }
+    }
+  }
+}
+
+bool WholeProgramDevirt::tryFindVirtualCallTargets(
+    std::vector<VirtualCallTarget> &TargetsForSlot,
+    const std::set<BitSetInfo> &BitSetInfos, uint64_t ByteOffset) {
+  for (const BitSetInfo &BS : BitSetInfos) {
+    if (!BS.Bits->GV->isConstant())
+      return false;
+
+    auto Init = dyn_cast<ConstantArray>(BS.Bits->GV->getInitializer());
+    if (!Init)
+      return false;
+    ArrayType *VTableTy = Init->getType();
+
+    uint64_t ElemSize =
+        M->getDataLayout().getTypeAllocSize(VTableTy->getElementType());
+    uint64_t GlobalSlotOffset = BS.Offset + ByteOffset;
+    if (GlobalSlotOffset % ElemSize != 0)
+      return false;
+
+    unsigned Op = GlobalSlotOffset / ElemSize;
+    if (Op >= Init->getNumOperands())
+      return false;
+
+    auto Fn = dyn_cast<Function>(Init->getOperand(Op)->stripPointerCasts());
+    if (!Fn)
+      return false;
+
+    // We can disregard __cxa_pure_virtual as a possible call target, as
+    // calls to pure virtuals are UB.
+    if (Fn->getName() == "__cxa_pure_virtual")
+      continue;
+
+    TargetsForSlot.push_back({Fn, &BS});
+  }
+
+  // Give up if we couldn't find any targets.
+  return !TargetsForSlot.empty();
+}
+
+bool WholeProgramDevirt::trySingleImplDevirt(
+    ArrayRef<VirtualCallTarget> TargetsForSlot,
+    MutableArrayRef<VirtualCallSite> CallSites) {
+  // See if the program contains a single implementation of this virtual
+  // function.
+  Function *TheFn = TargetsForSlot[0].Fn;
+  for (auto &&Target : TargetsForSlot)
+    if (TheFn != Target.Fn)
+      return false;
+
+  // If so, update each call site to call that implementation directly.
+  for (auto &&VCallSite : CallSites) {
+    VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
+        TheFn, VCallSite.CS.getCalledValue()->getType()));
+  }
+  return true;
+}
+
+bool WholeProgramDevirt::tryEvaluateFunctionsWithArgs(
+    MutableArrayRef<VirtualCallTarget> TargetsForSlot,
+    ArrayRef<ConstantInt *> Args) {
+  // Evaluate each function and store the result in each target's RetVal
+  // field.
+  for (VirtualCallTarget &Target : TargetsForSlot) {
+    if (Target.Fn->arg_size() != Args.size() + 1)
+      return false;
+    for (unsigned I = 0; I != Args.size(); ++I)
+      if (Target.Fn->getFunctionType()->getParamType(I + 1) !=
+          Args[I]->getType())
+        return false;
+
+    Evaluator Eval(M->getDataLayout(), nullptr);
+    SmallVector<Constant *, 2> EvalArgs;
+    EvalArgs.push_back(
+        Constant::getNullValue(Target.Fn->getFunctionType()->getParamType(0)));
+    EvalArgs.insert(EvalArgs.end(), Args.begin(), Args.end());
+    Constant *RetVal;
+    if (!Eval.EvaluateFunction(Target.Fn, RetVal, EvalArgs) ||
+        !isa<ConstantInt>(RetVal))
+      return false;
+    Target.RetVal = cast<ConstantInt>(RetVal)->getZExtValue();
+  }
+  return true;
+}
+
+bool WholeProgramDevirt::tryUniformRetValOpt(
+    IntegerType *RetType, ArrayRef<VirtualCallTarget> TargetsForSlot,
+    MutableArrayRef<VirtualCallSite> CallSites) {
+  // Uniform return value optimization. If all functions return the same
+  // constant, replace all calls with that constant.
+  uint64_t TheRetVal = TargetsForSlot[0].RetVal;
+  for (const VirtualCallTarget &Target : TargetsForSlot)
+    if (Target.RetVal != TheRetVal)
+      return false;
+
+  auto TheRetValConst = ConstantInt::get(RetType, TheRetVal);
+  for (auto Call : CallSites)
+    Call.replaceAndErase(TheRetValConst);
+  return true;
+}
+
+bool WholeProgramDevirt::tryUniqueRetValOpt(
+    unsigned BitWidth, ArrayRef<VirtualCallTarget> TargetsForSlot,
+    MutableArrayRef<VirtualCallSite> CallSites) {
+  // IsOne controls whether we look for a 0 or a 1.
+  auto tryUniqueRetValOptFor = [&](bool IsOne) {
+    const BitSetInfo *UniqueBitSet = 0;
+    for (const VirtualCallTarget &Target : TargetsForSlot) {
+      if (Target.RetVal == IsOne ? 1 : 0) {
+        if (UniqueBitSet)
+          return false;
+        UniqueBitSet = Target.BS;
+      }
+    }
+
+    // We should have found a unique bit set or bailed out by now. We already
+    // checked for a uniform return value in tryUniformRetValOpt.
+    assert(UniqueBitSet);
+
+    // Replace each call with the comparison.
+    for (auto &&Call : CallSites) {
+      IRBuilder<> B(Call.CS.getInstruction());
+      Value *OneAddr = B.CreateBitCast(UniqueBitSet->Bits->GV, Int8PtrTy);
+      OneAddr = B.CreateConstGEP1_64(OneAddr, UniqueBitSet->Offset);
+      Value *Cmp = B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
+                                Call.VTable, OneAddr);
+      Call.replaceAndErase(Cmp);
+    }
+    return true;
+  };
+
+  if (BitWidth == 1) {
+    if (tryUniqueRetValOptFor(true))
+      return true;
+    if (tryUniqueRetValOptFor(false))
+      return true;
+  }
+  return false;
+}
+
+bool WholeProgramDevirt::tryVirtualConstProp(
+    MutableArrayRef<VirtualCallTarget> TargetsForSlot,
+    ArrayRef<VirtualCallSite> CallSites) {
+  // This only works if the function returns an integer.
+  auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
+  if (!RetType)
+    return false;
+  unsigned BitWidth = RetType->getBitWidth();
+  if (BitWidth > 64)
+    return false;
+
+  // Make sure that each function does not access memory, takes at least one
+  // argument, does not use its first argument (which we assume is 'this'),
+  // and has the same return type.
+  for (VirtualCallTarget &Target : TargetsForSlot) {
+    if (!Target.Fn->doesNotAccessMemory() || Target.Fn->arg_empty() ||
+        !Target.Fn->arg_begin()->use_empty() ||
+        Target.Fn->getReturnType() != RetType)
+      return false;
+  }
+
+  // Group call sites by the list of constant arguments they pass.
+  // The comparator ensures deterministic ordering.
+  struct ByAPIntValue {
+    bool operator()(const std::vector<ConstantInt *> &A,
+                    const std::vector<ConstantInt *> &B) const {
+      return std::lexicographical_compare(
+          A.begin(), A.end(), B.begin(), B.end(),
+          [](ConstantInt *AI, ConstantInt *BI) {
+            return AI->getValue().ult(BI->getValue());
+          });
+    }
+  };
+  std::map<std::vector<ConstantInt *>, std::vector<VirtualCallSite>,
+           ByAPIntValue>
+      VCallSitesByConstantArg;
+  for (auto &&VCallSite : CallSites) {
+    std::vector<ConstantInt *> Args;
+    if (VCallSite.CS.getType() != RetType)
+      continue;
+    for (auto &&Arg :
+         make_range(VCallSite.CS.arg_begin() + 1, VCallSite.CS.arg_end())) {
+      if (!isa<ConstantInt>(Arg))
+        break;
+      Args.push_back(cast<ConstantInt>(&Arg));
+    }
+    if (Args.size() + 1 != VCallSite.CS.arg_size())
+      continue;
+
+    VCallSitesByConstantArg[Args].push_back(VCallSite);
+  }
+
+  for (auto &&CSByConstantArg : VCallSitesByConstantArg) {
+    if (!tryEvaluateFunctionsWithArgs(TargetsForSlot, CSByConstantArg.first))
+      continue;
+
+    if (tryUniformRetValOpt(RetType, TargetsForSlot, CSByConstantArg.second))
+      continue;
+
+    if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second))
+      continue;
+
+    // Find an allocation offset in bits in all vtables in the bitset.
+    uint64_t AllocBefore =
+        findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
+    uint64_t AllocAfter =
+        findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
+
+    // Calculate the total amount of padding needed to store a value at both
+    // ends of the object.
+    uint64_t TotalPaddingBefore = 0, TotalPaddingAfter = 0;
+    for (auto &&Target : TargetsForSlot) {
+      TotalPaddingBefore += std::max<int64_t>(
+          (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0);
+      TotalPaddingAfter += std::max<int64_t>(
+          (AllocAfter + 7) / 8 - Target.allocatedAfterBytes() - 1, 0);
+    }
+
+    // If the amount of padding is too large, give up.
+    // FIXME: do something smarter here.
+    if (std::min(TotalPaddingBefore, TotalPaddingAfter) > 128)
+      continue;
+
+    // Calculate the offset to the value as a (possibly negative) byte offset
+    // and (if applicable) a bit offset, and store the values in the targets.
+    int64_t OffsetByte;
+    uint64_t OffsetBit;
+    if (TotalPaddingBefore <= TotalPaddingAfter)
+      setBeforeReturnValues(TargetsForSlot, AllocBefore, BitWidth, OffsetByte,
+                            OffsetBit);
+    else
+      setAfterReturnValues(TargetsForSlot, AllocAfter, BitWidth, OffsetByte,
+                           OffsetBit);
+
+    // Rewrite each call to a load from OffsetByte/OffsetBit.
+    for (auto Call : CSByConstantArg.second) {
+      IRBuilder<> B(Call.CS.getInstruction());
+      Value *Addr = B.CreateConstGEP1_64(Call.VTable, OffsetByte);
+      if (BitWidth == 1) {
+        Value *Bits = B.CreateLoad(Addr);
+        Value *Bit = ConstantInt::get(Int8Ty, 1 << OffsetBit);
+        Value *BitsAndBit = B.CreateAnd(Bits, Bit);
+        auto IsBitSet = B.CreateICmpNE(BitsAndBit, ConstantInt::get(Int8Ty, 0));
+        Call.replaceAndErase(IsBitSet);
+      } else {
+        IntegerType *IntTy = Type::getIntNTy(M->getContext(), BitWidth);
+        Value *ValAddr = B.CreateBitCast(Addr, IntTy->getPointerTo());
+        Value *Val = B.CreateLoad(IntTy, ValAddr);
+        Call.replaceAndErase(Val);
+      }
+    }
+  }
+  return true;
+}
+
+bool WholeProgramDevirt::runOnModule(Module &Mod) {
+  M = &Mod;
+  Int8Ty = Type::getInt8Ty(M->getContext());
+  Int8PtrTy = Type::getInt8PtrTy(M->getContext());
+  Int32Ty = Type::getInt32Ty(M->getContext());
+
+  Function *BitSetTestFunc =
+      M->getFunction(Intrinsic::getName(Intrinsic::bitset_test));
+  if (!BitSetTestFunc || BitSetTestFunc->use_empty())
+    return false;
+
+  Function *AssumeFunc = M->getFunction(Intrinsic::getName(Intrinsic::assume));
+  if (!AssumeFunc || AssumeFunc->use_empty())
+    return false;
+
+  // Find all virtual calls via a virtual table pointer %p under an assumption
+  // of the form llvm.assume(llvm.bitset.test(%p, %md)). This indicates that %p
+  // points to a vtable in the bitset %md. Group calls by (bitset, offset) pair
+  // (effectively the identity of the virtual function) and store to
+  // CallsBySlot.
+  DenseSet<Value *> SeenPtrs;
+  for (auto I = BitSetTestFunc->use_begin(), E = BitSetTestFunc->use_end();
+       I != E;) {
+    auto CI = dyn_cast<CallInst>(I->getUser());
+    ++I;
+    if (!CI)
+      continue;
+
+    auto BitSet = cast<MetadataAsValue>(CI->getArgOperand(1))->getMetadata();
+
+    // Find llvm.assume intrinsics for this llvm.bitset.test call.
+    SmallVector<CallInst *, 1> Assumes;
+    for (const Use &CIU : CI->uses()) {
+      auto AssumeCI = dyn_cast<CallInst>(CIU.getUser());
+      if (AssumeCI && AssumeCI->getCalledValue() == AssumeFunc)
+        Assumes.push_back(AssumeCI);
+    }
+
+    // If we found any, search for virtual calls based on %p and add them to
+    // CallsBySlot.
+    if (!Assumes.empty()) {
+      Value *Ptr = CI->getArgOperand(0)->stripPointerCasts();
+      if (SeenPtrs.insert(Ptr).second)
+        findLoadCallsAtConstantOffset(BitSet, Ptr, 0, CI->getArgOperand(0));
+    }
+
+    // We no longer need the assumes or the bitset test.
+    for (auto Assume : Assumes)
+      Assume->eraseFromParent();
+    // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we
+    // may use the vtable argument later.
+    if (CI->use_empty())
+      CI->eraseFromParent();
+  }
+
+  // Rebuild llvm.bitsets metadata into a map for easy lookup.
+  DenseMap<Metadata *, std::set<BitSetInfo>> BitSets;
+  NamedMDNode *BitSetNM = M->getNamedMetadata("llvm.bitsets");
+  std::vector<VTableBits> Bits;
+  if (BitSetNM) {
+    DenseMap<GlobalVariable *, VTableBits *> GVToBits;
+    Bits.reserve(BitSetNM->getNumOperands());
+    for (auto Op : BitSetNM->operands()) {
+      auto OpConstMD = dyn_cast_or_null<ConstantAsMetadata>(Op->getOperand(1));
+      if (!OpConstMD)
+        continue;
+      auto BitSetID = Op->getOperand(0).get();
+
+      Constant *OpConst = OpConstMD->getValue();
+      if (auto GA = dyn_cast<GlobalAlias>(OpConst))
+        OpConst = GA->getAliasee();
+      auto OpGlobal = dyn_cast<GlobalVariable>(OpConst);
+      if (!OpGlobal)
+        continue;
+
+      uint64_t Offset =
+          cast<ConstantInt>(
+              cast<ConstantAsMetadata>(Op->getOperand(2))->getValue())
+              ->getZExtValue();
+
+      VTableBits *&BitsPtr = GVToBits[OpGlobal];
+      if (!BitsPtr) {
+        Bits.emplace_back();
+        Bits.back().GV = OpGlobal;
+        Bits.back().ObjectSize = M->getDataLayout().getTypeAllocSize(
+            OpGlobal->getInitializer()->getType());
+        BitsPtr = &Bits.back();
+      }
+      BitSets[BitSetID].insert({BitsPtr, Offset});
+    }
+  }
+
+  // For each (bitset, offset) pair:
+  for (auto &S : CallSlots) {
+    // Search each of the vtables in the bitset for the virtual function
+    // implementation at offset S.first.ByteOffset, and add to TargetsForSlot.
+    std::vector<VirtualCallTarget> TargetsForSlot;
+    if (!tryFindVirtualCallTargets(TargetsForSlot, BitSets[S.first.BitSetID],
+                                   S.first.ByteOffset))
+      continue;
+
+    if (trySingleImplDevirt(TargetsForSlot, S.second))
+      continue;
+
+    tryVirtualConstProp(TargetsForSlot, S.second);
+  }
+
+  // Rebuild each global we touched as part of virtual constant propagation to
+  // include the before and after bytes.
+  for (VTableBits &B : Bits) {
+    if (B.Before.Bytes.empty() && B.After.Bytes.empty())
+      continue;
+
+    // Align each byte array to pointer width.
+    unsigned PointerSize = M->getDataLayout().getPointerSize();
+    B.Before.Bytes.resize(alignTo(B.Before.Bytes.size(), PointerSize));
+    B.After.Bytes.resize(alignTo(B.After.Bytes.size(), PointerSize));
+
+    // Before was stored in reverse order; flip it now.
+    for (unsigned I = 0; I != B.Before.Bytes.size() / 2; ++I)
+      std::swap(B.Before.Bytes[I],
+                B.Before.Bytes[B.Before.Bytes.size() - 1 - I]);
+
+    // Build an anonymous global containing the before bytes, followed by the
+    // original initializer, followed by the after bytes.
+    auto NewInit = ConstantStruct::getAnon(
+        {ConstantDataArray::get(M->getContext(), B.Before.Bytes),
+         B.GV->getInitializer(),
+         ConstantDataArray::get(M->getContext(), B.After.Bytes)});
+    auto NewGV =
+        new GlobalVariable(*M, NewInit->getType(), B.GV->isConstant(),
+                           GlobalVariable::PrivateLinkage, NewInit, "", B.GV);
+    NewGV->setComdat(B.GV->getComdat());
+
+    // Build an alias named after the original global, pointing at the second
+    // element (the original initializer).
+    auto Alias = GlobalAlias::create(
+        B.GV->getInitializer()->getType(), 0, B.GV->getLinkage(), "",
+        ConstantExpr::getGetElementPtr(
+            NewInit->getType(), NewGV,
+            ArrayRef<Constant *>{ConstantInt::get(Int32Ty, 0),
+                                 ConstantInt::get(Int32Ty, 1)}),
+        M);
+    Alias->setVisibility(B.GV->getVisibility());
+    Alias->takeName(B.GV);
+
+    B.GV->replaceAllUsesWith(Alias);
+    B.GV->eraseFromParent();
+  }
+
+  return true;
+}

test/Transforms/WholeProgramDevirt/bad-read-from-vtable.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt = global [2 x i8*] [i8* zeroinitializer, i8* bitcast (void (i8*)* @vf to i8*)]
+
+define void @vf(i8* %this) {
+  ret void
+}
+
+; CHECK: define void @unaligned
+define void @unaligned(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr i8, i8* %vtablei8, i32 1
+  %fptrptr_casted = bitcast i8* %fptrptr to i8**
+  %fptr = load i8*, i8** %fptrptr_casted
+  %fptr_casted = bitcast i8* %fptr to void (i8*)*
+  ; CHECK: call void %
+  call void %fptr_casted(i8* %obj)
+  ret void
+}
+
+; CHECK: define void @outofbounds
+define void @outofbounds(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr i8, i8* %vtablei8, i32 16
+  %fptrptr_casted = bitcast i8* %fptrptr to i8**
+  %fptr = load i8*, i8** %fptrptr_casted
+  %fptr_casted = bitcast i8* %fptr to void (i8*)*
+  ; CHECK: call void %
+  call void %fptr_casted(i8* %obj)
+  ret void
+}
+
+; CHECK: define void @nonfunction
+define void @nonfunction(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr i8, i8* %vtablei8, i32 0
+  %fptrptr_casted = bitcast i8* %fptrptr to i8**
+  %fptr = load i8*, i8** %fptrptr_casted
+  %fptr_casted = bitcast i8* %fptr to void (i8*)*
+  ; CHECK: call void %
+  call void %fptr_casted(i8* %obj)
+  ret void
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [2 x i8*]* @vt, i32 0}
+!llvm.bitsets = !{!0}

test/Transforms/WholeProgramDevirt/constant-arg.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+; CHECK: private constant { [8 x i8], [1 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\00\00\00\00\01", [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf1 to i8*)], [0 x i8] zeroinitializer }
+; CHECK: private constant { [8 x i8], [1 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\00\00\00\00\02", [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf2 to i8*)], [0 x i8] zeroinitializer }
+; CHECK: private constant { [8 x i8], [1 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\00\00\00\00\01", [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf4 to i8*)], [0 x i8] zeroinitializer }
+; CHECK: private constant { [8 x i8], [1 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\00\00\00\00\02", [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf8 to i8*)], [0 x i8] zeroinitializer }
+
+@vt1 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf1 to i8*)]
+@vt2 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf2 to i8*)]
+@vt4 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf4 to i8*)]
+@vt8 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf8 to i8*)]
+
+define i1 @vf1(i8* %this, i32 %arg) readnone {
+  %and = and i32 %arg, 1
+  %cmp = icmp ne i32 %and, 0
+  ret i1 %cmp
+}
+
+define i1 @vf2(i8* %this, i32 %arg) readnone {
+  %and = and i32 %arg, 2
+  %cmp = icmp ne i32 %and, 0
+  ret i1 %cmp
+}
+
+define i1 @vf4(i8* %this, i32 %arg) readnone {
+  %and = and i32 %arg, 4
+  %cmp = icmp ne i32 %and, 0
+  ret i1 %cmp
+}
+
+define i1 @vf8(i8* %this, i32 %arg) readnone {
+  %and = and i32 %arg, 8
+  %cmp = icmp ne i32 %and, 0
+  ret i1 %cmp
+}
+
+; CHECK: define i1 @call1
+define i1 @call1(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)*
+  ; CHECK: getelementptr {{.*}} -1
+  ; CHECK: and {{.*}}, 1
+  %result = call i1 %fptr_casted(i8* %obj, i32 5)
+  ret i1 %result
+}
+
+; CHECK: define i1 @call2
+define i1 @call2(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)*
+  ; CHECK: getelementptr {{.*}} -1
+  ; CHECK: and {{.*}}, 2
+  %result = call i1 %fptr_casted(i8* %obj, i32 10)
+  ret i1 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0}
+!2 = !{!"bitset", [1 x i8*]* @vt4, i32 0}
+!3 = !{!"bitset", [1 x i8*]* @vt8, i32 0}
+!llvm.bitsets = !{!0, !1, !2, !3}

test/Transforms/WholeProgramDevirt/devirt-single-impl.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt1 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)]
+@vt2 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)]
+
+define void @vf(i8* %this) {
+  ret void
+}
+
+; CHECK: define void @call
+define void @call(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to void (i8*)*
+  ; CHECK: call void @vf(
+  call void %fptr_casted(i8* %obj)
+  ret void
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0}
+!llvm.bitsets = !{!0, !1}

test/Transforms/WholeProgramDevirt/non-array-vtable.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt = constant i8* bitcast (void (i8*)* @vf to i8*)
+
+define void @vf(i8* %this) {
+  ret void
+}
+
+; CHECK: define void @call
+define void @call(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to void (i8*)*
+  ; CHECK: call void %
+  call void %fptr_casted(i8* %obj)
+  ret void
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", i8** @vt, i32 0}
+!llvm.bitsets = !{!0}

test/Transforms/WholeProgramDevirt/non-constant-vtable.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt = global [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)]
+
+define void @vf(i8* %this) {
+  ret void
+}
+
+; CHECK: define void @call
+define void @call(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to void (i8*)*
+  ; CHECK: call void %
+  call void %fptr_casted(i8* %obj)
+  ret void
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt, i32 0}
+!llvm.bitsets = !{!0}

test/Transforms/WholeProgramDevirt/uniform-retval.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt1 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf1 to i8*)]
+@vt2 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf2 to i8*)]
+
+define i32 @vf1(i8* %this) readnone {
+  ret i32 123
+}
+
+define i32 @vf2(i8* %this) readnone {
+  ret i32 123
+}
+
+; CHECK: define i32 @call
+define i32 @call(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*)*
+  %result = call i32 %fptr_casted(i8* %obj)
+  ; CHECK-NOT: call
+  ; CHECK: ret i32 123
+  ret i32 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0}
+!llvm.bitsets = !{!0, !1}

test/Transforms/WholeProgramDevirt/unique-retval.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt1 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf0 to i8*)]
+@vt2 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf0 to i8*)]
+@vt3 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf1 to i8*)]
+@vt4 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf1 to i8*)]
+
+define i1 @vf0(i8* %this) readnone {
+  ret i1 0
+}
+
+define i1 @vf1(i8* %this) readnone {
+  ret i1 1
+}
+
+; CHECK: define i1 @call1
+define i1 @call1(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  ; CHECK: [[VT1:%[^ ]*]] = bitcast [1 x i8*]* {{.*}} to i8*
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset1")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*)*
+  ; CHECK: [[RES1:%[^ ]*]] = icmp eq i8* [[VT1]], bitcast ([1 x i8*]* @vt3 to i8*)
+  %result = call i1 %fptr_casted(i8* %obj)
+  ; CHECK: ret i1 [[RES1]]
+  ret i1 %result
+}
+
+; CHECK: define i1 @call2
+define i1 @call2(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  ; CHECK: [[VT2:%[^ ]*]] = bitcast [1 x i8*]* {{.*}} to i8*
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset2")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*)*
+  ; CHECK: [[RES1:%[^ ]*]] = icmp ne i8* [[VT1]], bitcast ([1 x i8*]* @vt2 to i8*)
+  %result = call i1 %fptr_casted(i8* %obj)
+  ret i1 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset1", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset1", [1 x i8*]* @vt2, i32 0}
+!2 = !{!"bitset1", [1 x i8*]* @vt3, i32 0}
+!3 = !{!"bitset2", [1 x i8*]* @vt2, i32 0}
+!4 = !{!"bitset2", [1 x i8*]* @vt3, i32 0}
+!5 = !{!"bitset2", [1 x i8*]* @vt4, i32 0}
+!llvm.bitsets = !{!0, !1, !2, !3, !4, !5}

test/Transforms/WholeProgramDevirt/vcp-accesses-memory.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1 to i8*)]
+@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2 to i8*)]
+
+define i32 @vf1(i8* %this, i32 %arg) {
+  ret i32 %arg
+}
+
+define i32 @vf2(i8* %this, i32 %arg) {
+  ret i32 %arg
+}
+
+; CHECK: define i32 @call
+define i32 @call(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*, i32)*
+  ; CHECK: call i32 %
+  %result = call i32 %fptr_casted(i8* %obj, i32 1)
+  ret i32 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0}
+!llvm.bitsets = !{!0}

test/Transforms/WholeProgramDevirt/vcp-no-this.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt1 = global [1 x i8*] [i8* bitcast (i32 ()* @vf1 to i8*)]
+@vt2 = global [1 x i8*] [i8* bitcast (i32 ()* @vf2 to i8*)]
+
+define i32 @vf1() readnone {
+  ret i32 1
+}
+
+define i32 @vf2() readnone {
+  ret i32 2
+}
+
+; CHECK: define i32 @call
+define i32 @call(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 ()*
+  ; CHECK: call i32 %
+  %result = call i32 %fptr_casted()
+  ret i32 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0}
+!llvm.bitsets = !{!0}

test/Transforms/WholeProgramDevirt/vcp-non-constant-arg.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1 to i8*)]
+@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2 to i8*)]
+
+define i32 @vf1(i8* %this, i32 %arg) readnone {
+  ret i32 %arg
+}
+
+define i32 @vf2(i8* %this, i32 %arg) readnone {
+  ret i32 %arg
+}
+
+; CHECK: define void @call
+define void @call(i8* %obj, i32 %arg) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*, i32)*
+  ; CHECK: call i32 %
+  %result = call i32 %fptr_casted(i8* %obj, i32 %arg)
+  ret void
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0}
+!llvm.bitsets = !{!0}

test/Transforms/WholeProgramDevirt/vcp-too-wide-ints.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt1 = global [1 x i8*] [i8* bitcast (i128 (i8*, i128)* @vf1 to i8*)]
+@vt2 = global [1 x i8*] [i8* bitcast (i128 (i8*, i128)* @vf2 to i8*)]
+
+define i128 @vf1(i8* %this, i128 %arg) readnone {
+  ret i128 %arg
+}
+
+define i128 @vf2(i8* %this, i128 %arg) readnone {
+  ret i128 %arg
+}
+
+; CHECK: define i128 @call
+define i128 @call(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i128 (i8*, i128)*
+  ; CHECK: call i128 %
+  %result = call i128 %fptr_casted(i8* %obj, i128 1)
+  ret i128 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0}
+!llvm.bitsets = !{!0}

test/Transforms/WholeProgramDevirt/vcp-type-mismatch.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1 to i8*)]
+@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2 to i8*)]
+
+define i32 @vf1(i8* %this, i32 %arg) readnone {
+  ret i32 %arg
+}
+
+define i32 @vf2(i8* %this, i32 %arg) readnone {
+  ret i32 %arg
+}
+
+; CHECK: define i32 @bad_arg_type
+define i32 @bad_arg_type(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*, i64)*
+  ; CHECK: call i32 %
+  %result = call i32 %fptr_casted(i8* %obj, i64 1)
+  ret i32 %result
+}
+
+; CHECK: define i32 @bad_arg_count
+define i32 @bad_arg_count(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*, i64, i64)*
+  ; CHECK: call i32 %
+  %result = call i32 %fptr_casted(i8* %obj, i64 1, i64 2)
+  ret i32 %result
+}
+
+; CHECK: define i64 @bad_return_type
+define i64 @bad_return_type(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i64 (i8*, i32)*
+  ; CHECK: call i64 %
+  %result = call i64 %fptr_casted(i8* %obj, i32 1)
+  ret i64 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0}
+!llvm.bitsets = !{!0}

test/Transforms/WholeProgramDevirt/vcp-uses-this.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*)* @vf1 to i8*)]
+@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*)* @vf2 to i8*)]
+
+define i32 @vf1(i8* %this) readnone {
+  %this_int = ptrtoint i8* %this to i32
+  ret i32 %this_int
+}
+
+define i32 @vf2(i8* %this) readnone {
+  %this_int = ptrtoint i8* %this to i32
+  ret i32 %this_int
+}
+
+; CHECK: define i32 @call
+define i32 @call(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*)*
+  ; CHECK: call i32 %
+  %result = call i32 %fptr_casted(i8* %obj)
+  ret i32 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0}
+!llvm.bitsets = !{!0}

test/Transforms/WholeProgramDevirt/virtual-const-prop-begin.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+; CHECK: [[VT1DATA:@[^ ]*]] = private constant { [8 x i8], [3 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\01\01\00\00\00", [3 x i8*] [i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf1i32 to i8*)], [0 x i8] zeroinitializer }
+@vt1 = constant [3 x i8*] [
+i8* bitcast (i1 (i8*)* @vf0i1 to i8*),
+i8* bitcast (i1 (i8*)* @vf1i1 to i8*),
+i8* bitcast (i32 (i8*)* @vf1i32 to i8*)
+]
+
+; CHECK: [[VT2DATA:@[^ ]*]] = private constant { [8 x i8], [3 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\02\02\00\00\00", [3 x i8*] [i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf2i32 to i8*)], [0 x i8] zeroinitializer }
+@vt2 = constant [3 x i8*] [
+i8* bitcast (i1 (i8*)* @vf1i1 to i8*),
+i8* bitcast (i1 (i8*)* @vf0i1 to i8*),
+i8* bitcast (i32 (i8*)* @vf2i32 to i8*)
+]
+
+; CHECK: [[VT3DATA:@[^ ]*]] = private constant { [8 x i8], [3 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\01\03\00\00\00", [3 x i8*] [i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf3i32 to i8*)], [0 x i8] zeroinitializer }
+@vt3 = constant [3 x i8*] [
+i8* bitcast (i1 (i8*)* @vf0i1 to i8*),
+i8* bitcast (i1 (i8*)* @vf1i1 to i8*),
+i8* bitcast (i32 (i8*)* @vf3i32 to i8*)
+]
+
+; CHECK: [[VT4DATA:@[^ ]*]] = private constant { [8 x i8], [3 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\02\04\00\00\00", [3 x i8*] [i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf4i32 to i8*)], [0 x i8] zeroinitializer }
+@vt4 = constant [3 x i8*] [
+i8* bitcast (i1 (i8*)* @vf1i1 to i8*),
+i8* bitcast (i1 (i8*)* @vf0i1 to i8*),
+i8* bitcast (i32 (i8*)* @vf4i32 to i8*)
+]
+
+@vt5 = constant [3 x i8*] [
+i8* bitcast (void ()* @__cxa_pure_virtual to i8*),
+i8* bitcast (void ()* @__cxa_pure_virtual to i8*),
+i8* bitcast (void ()* @__cxa_pure_virtual to i8*)
+]
+
+; CHECK: @vt1 = alias [3 x i8*], getelementptr inbounds ({ [8 x i8], [3 x i8*], [0 x i8] }, { [8 x i8], [3 x i8*], [0 x i8] }* [[VT1DATA]], i32 0, i32 1)
+; CHECK: @vt2 = alias [3 x i8*], getelementptr inbounds ({ [8 x i8], [3 x i8*], [0 x i8] }, { [8 x i8], [3 x i8*], [0 x i8] }* [[VT2DATA]], i32 0, i32 1)
+; CHECK: @vt3 = alias [3 x i8*], getelementptr inbounds ({ [8 x i8], [3 x i8*], [0 x i8] }, { [8 x i8], [3 x i8*], [0 x i8] }* [[VT3DATA]], i32 0, i32 1)
+; CHECK: @vt4 = alias [3 x i8*], getelementptr inbounds ({ [8 x i8], [3 x i8*], [0 x i8] }, { [8 x i8], [3 x i8*], [0 x i8] }* [[VT4DATA]], i32 0, i32 1)
+
+define i1 @vf0i1(i8* %this) readnone {
+  ret i1 0
+}
+
+define i1 @vf1i1(i8* %this) readnone {
+  ret i1 1
+}
+
+define i32 @vf1i32(i8* %this) readnone {
+  ret i32 1
+}
+
+define i32 @vf2i32(i8* %this) readnone {
+  ret i32 2
+}
+
+define i32 @vf3i32(i8* %this) readnone {
+  ret i32 3
+}
+
+define i32 @vf4i32(i8* %this) readnone {
+  ret i32 4
+}
+
+; CHECK: define i1 @call1(
+define i1 @call1(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [3 x i8*]**
+  %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr
+  ; CHECK: [[VT1:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8*
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*)*
+  ; CHECK: [[VTGEP1:%[^ ]*]] = getelementptr i8, i8* [[VT1]], i64 -5
+  ; CHECK: [[VTLOAD1:%[^ ]*]] = load i8, i8* [[VTGEP1]]
+  ; CHECK: [[VTAND1:%[^ ]*]] = and i8 [[VTLOAD1]], 2
+  ; CHECK: [[VTCMP1:%[^ ]*]] = icmp ne i8 [[VTAND1]], 0
+  %result = call i1 %fptr_casted(i8* %obj)
+  ; CHECK: ret i1 [[VTCMP1]]
+  ret i1 %result
+}
+
+; CHECK: define i1 @call2(
+define i1 @call2(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [3 x i8*]**
+  %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr
+  ; CHECK: [[VT2:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8*
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 1
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*)*
+  ; CHECK: [[VTGEP2:%[^ ]*]] = getelementptr i8, i8* [[VT2]], i64 -5
+  ; CHECK: [[VTLOAD2:%[^ ]*]] = load i8, i8* [[VTGEP2]]
+  ; CHECK: [[VTAND2:%[^ ]*]] = and i8 [[VTLOAD2]], 1
+  ; CHECK: [[VTCMP2:%[^ ]*]] = icmp ne i8 [[VTAND2]], 0
+  %result = call i1 %fptr_casted(i8* %obj)
+  ; CHECK: ret i1 [[VTCMP2]]
+  ret i1 %result
+}
+
+; CHECK: define i32 @call3(
+define i32 @call3(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [3 x i8*]**
+  %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr
+  ; CHECK: [[VT3:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8*
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 2
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*)*
+  ; CHECK: [[VTGEP3:%[^ ]*]] = getelementptr i8, i8* [[VT3]], i64 -4
+  ; CHECK: [[VTBC3:%[^ ]*]] = bitcast i8* [[VTGEP3]] to i32*
+  ; CHECK: [[VTLOAD3:%[^ ]*]] = load i32, i32* [[VTBC3]]
+  %result = call i32 %fptr_casted(i8* %obj)
+  ; CHECK: ret i32 [[VTLOAD3]]
+  ret i32 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+declare void @__cxa_pure_virtual()
+
+!0 = !{!"bitset", [3 x i8*]* @vt1, i32 0}
+!1 = !{!"bitset", [3 x i8*]* @vt2, i32 0}
+!2 = !{!"bitset", [3 x i8*]* @vt3, i32 0}
+!3 = !{!"bitset", [3 x i8*]* @vt4, i32 0}
+!4 = !{!"bitset", [3 x i8*]* @vt5, i32 0}
+!llvm.bitsets = !{!0, !1, !2, !3, !4}

test/Transforms/WholeProgramDevirt/virtual-const-prop-end.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck %s
+
+; CHECK: [[VT1DATA:@[^ ]*]] = private constant { [0 x i8], [4 x i8*], [8 x i8] } { [0 x i8] zeroinitializer, [4 x i8*] [i8* null, i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf1i32 to i8*)], [8 x i8] c"\01\00\00\00\01\00\00\00" }
+@vt1 = constant [4 x i8*] [
+i8* null,
+i8* bitcast (i1 (i8*)* @vf0i1 to i8*),
+i8* bitcast (i1 (i8*)* @vf1i1 to i8*),
+i8* bitcast (i32 (i8*)* @vf1i32 to i8*)
+]
+
+; CHECK: [[VT2DATA:@[^ ]*]] = private constant { [0 x i8], [3 x i8*], [8 x i8] } { [0 x i8] zeroinitializer, [3 x i8*] [i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf2i32 to i8*)], [8 x i8] c"\02\00\00\00\02\00\00\00" }
+@vt2 = constant [3 x i8*] [
+i8* bitcast (i1 (i8*)* @vf1i1 to i8*),
+i8* bitcast (i1 (i8*)* @vf0i1 to i8*),
+i8* bitcast (i32 (i8*)* @vf2i32 to i8*)
+]
+
+; CHECK: [[VT3DATA:@[^ ]*]] = private constant { [0 x i8], [4 x i8*], [8 x i8] } { [0 x i8] zeroinitializer, [4 x i8*] [i8* null, i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf3i32 to i8*)], [8 x i8] c"\03\00\00\00\01\00\00\00" }
+@vt3 = constant [4 x i8*] [
+i8* null,
+i8* bitcast (i1 (i8*)* @vf0i1 to i8*),
+i8* bitcast (i1 (i8*)* @vf1i1 to i8*),
+i8* bitcast (i32 (i8*)* @vf3i32 to i8*)
+]
+
+; CHECK: [[VT4DATA:@[^ ]*]] = private constant { [0 x i8], [3 x i8*], [8 x i8] } { [0 x i8] zeroinitializer, [3 x i8*] [i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf4i32 to i8*)], [8 x i8] c"\04\00\00\00\02\00\00\00" }
+@vt4 = constant [3 x i8*] [
+i8* bitcast (i1 (i8*)* @vf1i1 to i8*),
+i8* bitcast (i1 (i8*)* @vf0i1 to i8*),
+i8* bitcast (i32 (i8*)* @vf4i32 to i8*)
+]
+
+; CHECK: @vt1 = alias [4 x i8*], getelementptr inbounds ({ [0 x i8], [4 x i8*], [8 x i8] }, { [0 x i8], [4 x i8*], [8 x i8] }* [[VT1DATA]], i32 0, i32 1)
+; CHECK: @vt2 = alias [3 x i8*], getelementptr inbounds ({ [0 x i8], [3 x i8*], [8 x i8] }, { [0 x i8], [3 x i8*], [8 x i8] }* [[VT2DATA]], i32 0, i32 1)
+; CHECK: @vt3 = alias [4 x i8*], getelementptr inbounds ({ [0 x i8], [4 x i8*], [8 x i8] }, { [0 x i8], [4 x i8*], [8 x i8] }* [[VT3DATA]], i32 0, i32 1)
+; CHECK: @vt4 = alias [3 x i8*], getelementptr inbounds ({ [0 x i8], [3 x i8*], [8 x i8] }, { [0 x i8], [3 x i8*], [8 x i8] }* [[VT4DATA]], i32 0, i32 1)
+
+define i1 @vf0i1(i8* %this) readnone {
+  ret i1 0
+}
+
+define i1 @vf1i1(i8* %this) readnone {
+  ret i1 1
+}
+
+define i32 @vf1i32(i8* %this) readnone {
+  ret i32 1
+}
+
+define i32 @vf2i32(i8* %this) readnone {
+  ret i32 2
+}
+
+define i32 @vf3i32(i8* %this) readnone {
+  ret i32 3
+}
+
+define i32 @vf4i32(i8* %this) readnone {
+  ret i32 4
+}
+
+; CHECK: define i1 @call1(
+define i1 @call1(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [3 x i8*]**
+  %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr
+  ; CHECK: [[VT1:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8*
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*)*
+  ; CHECK: [[VTGEP1:%[^ ]*]] = getelementptr i8, i8* [[VT1]], i64 28
+  ; CHECK: [[VTLOAD1:%[^ ]*]] = load i8, i8* [[VTGEP1]]
+  ; CHECK: [[VTAND1:%[^ ]*]] = and i8 [[VTLOAD1]], 2
+  ; CHECK: [[VTCMP1:%[^ ]*]] = icmp ne i8 [[VTAND1]], 0
+  %result = call i1 %fptr_casted(i8* %obj)
+  ; CHECK: ret i1 [[VTCMP1]]
+  ret i1 %result
+}
+
+; CHECK: define i1 @call2(
+define i1 @call2(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [3 x i8*]**
+  %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr
+  ; CHECK: [[VT2:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8*
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 1
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*)*
+  ; CHECK: [[VTGEP2:%[^ ]*]] = getelementptr i8, i8* [[VT2]], i64 28
+  ; CHECK: [[VTLOAD2:%[^ ]*]] = load i8, i8* [[VTGEP2]]
+  ; CHECK: [[VTAND2:%[^ ]*]] = and i8 [[VTLOAD2]], 1
+  ; CHECK: [[VTCMP2:%[^ ]*]] = icmp ne i8 [[VTAND2]], 0
+  %result = call i1 %fptr_casted(i8* %obj)
+  ; CHECK: ret i1 [[VTCMP2]]
+  ret i1 %result
+}
+
+; CHECK: define i32 @call3(
+define i32 @call3(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [3 x i8*]**
+  %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr
+  ; CHECK: [[VT3:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8*
+  %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 2
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*)*
+  ; CHECK: [[VTGEP3:%[^ ]*]] = getelementptr i8, i8* [[VT3]], i64 24
+  ; CHECK: [[VTBC3:%[^ ]*]] = bitcast i8* [[VTGEP3]] to i32*
+  ; CHECK: [[VTLOAD3:%[^ ]*]] = load i32, i32* [[VTBC3]]
+  %result = call i32 %fptr_casted(i8* %obj)
+  ; CHECK: ret i32 [[VTLOAD3]]
+  ret i32 %result
+}
+
+declare i1 @llvm.bitset.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{!"bitset", [4 x i8*]* @vt1, i32 8}
+!1 = !{!"bitset", [3 x i8*]* @vt2, i32 0}
+!2 = !{!"bitset", [4 x i8*]* @vt3, i32 8}
+!3 = !{!"bitset", [3 x i8*]* @vt4, i32 0}
+!llvm.bitsets = !{!0, !1, !2, !3}

test/tools/gold/X86/disable-verify.ll

 ; RUN: llvm-as %s -o %t.o
 ; REQUIRES: asserts
 
 ; RUN: %gold -m elf_x86_64 -plugin %llvmshlibdir/LLVMgold.so \
 ; RUN:    --plugin-opt=disable-verify \
 ; RUN:    --plugin-opt=-debug-pass=Arguments \
 ; RUN:    -shared %t.o -o %t2.o 2>&1 | FileCheck %s
 
 ; RUN: %gold -m elf_x86_64 -plugin %llvmshlibdir/LLVMgold.so \
 ; RUN:    --plugin-opt=-debug-pass=Arguments \
 ; RUN:    -shared %t.o -o %t2.o 2>&1 | FileCheck %s -check-prefix=VERIFY
 
 target triple = "x86_64-unknown-linux-gnu"
 
 ; -disable-verify should disable output verification from the optimization
 ; pipeline.
-; CHECK: Pass Arguments: {{.*}} -verify -forceattrs
+; CHECK: Pass Arguments: {{.*}} -verify -
 ; CHECK-NOT: -verify
 
 ; VERIFY: Pass Arguments: {{.*}} -verify {{.*}} -verify
 
 define void @f() {
 entry:
   ret void
 }

unittests/Transforms/IPO/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Core
   Support
   IPO
   )
 
 add_llvm_unittest(IPOTests
   LowerBitSets.cpp
+  WholeProgramDevirt.cpp
   )

unittests/Transforms/IPO/WholeProgramDevirt.cpp

+//===- WholeProgramDevirt.cpp - Unit tests for whole-program devirt -------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO/WholeProgramDevirt.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+using namespace wholeprogramdevirt;
+
+TEST(WholeProgramDevirt, findLowestOffset) {
+  VTableBits VT1;
+  VT1.ObjectSize = 8;
+  VT1.Before.BytesUsed = {1 << 0};
+  VT1.After.BytesUsed = {1 << 1};
+
+  VTableBits VT2;
+  VT2.ObjectSize = 8;
+  VT2.Before.BytesUsed = {1 << 1};
+  VT2.After.BytesUsed = {1 << 0};
+
+  BitSetInfo BS1{&VT1, 0};
+  BitSetInfo BS2{&VT2, 0};
+  VirtualCallTarget Targets[] = {
+    {&BS1, /*IsBigEndian=*/false},
+    {&BS2, /*IsBigEndian=*/false},
+  };
+
+  EXPECT_EQ(2ull, findLowestOffset(Targets, /*IsAfter=*/false, 1));
+  EXPECT_EQ(66ull, findLowestOffset(Targets, /*IsAfter=*/true, 1));
+
+  EXPECT_EQ(8ull, findLowestOffset(Targets, /*IsAfter=*/false, 8));
+  EXPECT_EQ(72ull, findLowestOffset(Targets, /*IsAfter=*/true, 8));
+
+  BS1.Offset = 4;
+  EXPECT_EQ(33ull, findLowestOffset(Targets, /*IsAfter=*/false, 1));
+  EXPECT_EQ(65ull, findLowestOffset(Targets, /*IsAfter=*/true, 1));
+
+  EXPECT_EQ(40ull, findLowestOffset(Targets, /*IsAfter=*/false, 8));
+  EXPECT_EQ(72ull, findLowestOffset(Targets, /*IsAfter=*/true, 8));
+
+  BS1.Offset = 8;
+  BS2.Offset = 8;
+  EXPECT_EQ(66ull, findLowestOffset(Targets, /*IsAfter=*/false, 1));
+  EXPECT_EQ(2ull, findLowestOffset(Targets, /*IsAfter=*/true, 1));
+
+  EXPECT_EQ(72ull, findLowestOffset(Targets, /*IsAfter=*/false, 8));
+  EXPECT_EQ(8ull, findLowestOffset(Targets, /*IsAfter=*/true, 8));
+
+  VT1.After.BytesUsed = {0xff, 0, 0, 0, 0xff};
+  VT2.After.BytesUsed = {0xff, 1, 0, 0, 0};
+  EXPECT_EQ(16ull, findLowestOffset(Targets, /*IsAfter=*/true, 16));
+  EXPECT_EQ(40ull, findLowestOffset(Targets, /*IsAfter=*/true, 32));
+}
+
+TEST(WholeProgramDevirt, setReturnValues) {
+  VTableBits VT1;
+  VT1.ObjectSize = 8;
+
+  VTableBits VT2;
+  VT2.ObjectSize = 8;
+
+  BitSetInfo BS1{&VT1, 0};
+  BitSetInfo BS2{&VT2, 0};
+  VirtualCallTarget Targets[] = {
+    {&BS1, /*IsBigEndian=*/false},
+    {&BS2, /*IsBigEndian=*/false},
+  };
+
+  BS1.Offset = 4;
+  BS2.Offset = 4;
+
+  int64_t OffsetByte;
+  uint64_t OffsetBit;
+
+  Targets[0].RetVal = 1;
+  Targets[1].RetVal = 0;
+  setBeforeReturnValues(Targets, 32, 1, OffsetByte, OffsetBit);
+  EXPECT_EQ(-5ll, OffsetByte);
+  EXPECT_EQ(0ull, OffsetBit);
+  EXPECT_EQ(std::vector<uint8_t>{1}, VT1.Before.Bytes);
+  EXPECT_EQ(std::vector<uint8_t>{1}, VT1.Before.BytesUsed);
+  EXPECT_EQ(std::vector<uint8_t>{0}, VT2.Before.Bytes);
+  EXPECT_EQ(std::vector<uint8_t>{1}, VT2.Before.BytesUsed);
+
+  Targets[0].RetVal = 0;
+  Targets[1].RetVal = 1;
+  setBeforeReturnValues(Targets, 39, 1, OffsetByte, OffsetBit);
+  EXPECT_EQ(-5ll, OffsetByte);
+  EXPECT_EQ(7ull, OffsetBit);
+  EXPECT_EQ(std::vector<uint8_t>{1}, VT1.Before.Bytes);
+  EXPECT_EQ(std::vector<uint8_t>{0x81}, VT1.Before.BytesUsed);
+  EXPECT_EQ(std::vector<uint8_t>{0x80}, VT2.Before.Bytes);
+  EXPECT_EQ(std::vector<uint8_t>{0x81}, VT2.Before.BytesUsed);
+
+  Targets[0].RetVal = 12;
+  Targets[1].RetVal = 34;
+  setBeforeReturnValues(Targets, 40, 8, OffsetByte, OffsetBit);
+  EXPECT_EQ(-6ll, OffsetByte);
+  EXPECT_EQ(0ull, OffsetBit);
+  EXPECT_EQ((std::vector<uint8_t>{1, 12}), VT1.Before.Bytes);
+  EXPECT_EQ((std::vector<uint8_t>{0x81, 0xff}), VT1.Before.BytesUsed);
+  EXPECT_EQ((std::vector<uint8_t>{0x80, 34}), VT2.Before.Bytes);
+  EXPECT_EQ((std::vector<uint8_t>{0x81, 0xff}), VT2.Before.BytesUsed);
+
+  Targets[0].RetVal = 56;
+  Targets[1].RetVal = 78;
+  setBeforeReturnValues(Targets, 48, 16, OffsetByte, OffsetBit);
+  EXPECT_EQ(-8ll, OffsetByte);
+  EXPECT_EQ(0ull, OffsetBit);
+  EXPECT_EQ((std::vector<uint8_t>{1, 12, 0, 56}), VT1.Before.Bytes);
+  EXPECT_EQ((std::vector<uint8_t>{0x81, 0xff, 0xff, 0xff}),
+            VT1.Before.BytesUsed);
+  EXPECT_EQ((std::vector<uint8_t>{0x80, 34, 0, 78}), VT2.Before.Bytes);
+  EXPECT_EQ((std::vector<uint8_t>{0x81, 0xff, 0xff, 0xff}),
+            VT2.Before.BytesUsed);
+
+  Targets[0].RetVal = 1;
+  Targets[1].RetVal = 0;
+  setAfterReturnValues(Targets, 32, 1, OffsetByte, OffsetBit);
+  EXPECT_EQ(4ll, OffsetByte);
+  EXPECT_EQ(0ull, OffsetBit);
+  EXPECT_EQ(std::vector<uint8_t>{1}, VT1.After.Bytes);
+  EXPECT_EQ(std::vector<uint8_t>{1}, VT1.After.BytesUsed);
+  EXPECT_EQ(std::vector<uint8_t>{0}, VT2.After.Bytes);
+  EXPECT_EQ(std::vector<uint8_t>{1}, VT2.After.BytesUsed);
+
+  Targets[0].RetVal = 0;
+  Targets[1].RetVal = 1;
+  setAfterReturnValues(Targets, 39, 1, OffsetByte, OffsetBit);
+  EXPECT_EQ(4ll, OffsetByte);
+  EXPECT_EQ(7ull, OffsetBit);
+  EXPECT_EQ(std::vector<uint8_t>{1}, VT1.After.Bytes);
+  EXPECT_EQ(std::vector<uint8_t>{0x81}, VT1.After.BytesUsed);
+  EXPECT_EQ(std::vector<uint8_t>{0x80}, VT2.After.Bytes);
+  EXPECT_EQ(std::vector<uint8_t>{0x81}, VT2.After.BytesUsed);
+
+  Targets[0].RetVal = 12;
+  Targets[1].RetVal = 34;
+  setAfterReturnValues(Targets, 40, 8, OffsetByte, OffsetBit);
+  EXPECT_EQ(5ll, OffsetByte);
+  EXPECT_EQ(0ull, OffsetBit);
+  EXPECT_EQ((std::vector<uint8_t>{1, 12}), VT1.After.Bytes);
+  EXPECT_EQ((std::vector<uint8_t>{0x81, 0xff}), VT1.After.BytesUsed);
+  EXPECT_EQ((std::vector<uint8_t>{0x80, 34}), VT2.After.Bytes);
+  EXPECT_EQ((std::vector<uint8_t>{0x81, 0xff}), VT2.After.BytesUsed);
+
+  Targets[0].RetVal = 56;
+  Targets[1].RetVal = 78;
+  setAfterReturnValues(Targets, 48, 16, OffsetByte, OffsetBit);
+  EXPECT_EQ(6ll, OffsetByte);
+  EXPECT_EQ(0ull, OffsetBit);
+  EXPECT_EQ((std::vector<uint8_t>{1, 12, 56, 0}), VT1.After.Bytes);
+  EXPECT_EQ((std::vector<uint8_t>{0x81, 0xff, 0xff, 0xff}),
+            VT1.After.BytesUsed);
+  EXPECT_EQ((std::vector<uint8_t>{0x80, 34, 78, 0}), VT2.After.Bytes);
+  EXPECT_EQ((std::vector<uint8_t>{0x81, 0xff, 0xff, 0xff}),
+            VT2.After.BytesUsed);
+}