Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -315,6 +315,7 @@ void initializeLoopLoadEliminationPass(PassRegistry&); void initializeFunctionImportPassPass(PassRegistry &); void initializeLoopVersioningPassPass(PassRegistry &); +void initializeWholeProgramDevirtPass(PassRegistry &); } #endif Index: include/llvm/Transforms/IPO.h =================================================================== --- include/llvm/Transforms/IPO.h +++ include/llvm/Transforms/IPO.h @@ -226,6 +226,10 @@ /// \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. Index: include/llvm/Transforms/IPO/PassManagerBuilder.h =================================================================== --- include/llvm/Transforms/IPO/PassManagerBuilder.h +++ include/llvm/Transforms/IPO/PassManagerBuilder.h @@ -157,6 +157,7 @@ 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); Index: include/llvm/Transforms/IPO/WholeProgramDevirt.h =================================================================== --- /dev/null +++ include/llvm/Transforms/IPO/WholeProgramDevirt.h @@ -0,0 +1,215 @@ +//===- 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 +#include +#include +#include + +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 Bytes; + + // Bits in BytesUsed[I] are 1 if matching bit in Bytes[I] is used, 0 if not. + std::vector BytesUsed; + + std::pair 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 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 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 Targets, + uint64_t AllocAfter, unsigned BitWidth, + int64_t &OffsetByte, uint64_t &OffsetBit); + +} +} + +#endif Index: lib/Transforms/IPO/CMakeLists.txt =================================================================== --- lib/Transforms/IPO/CMakeLists.txt +++ lib/Transforms/IPO/CMakeLists.txt @@ -27,6 +27,7 @@ SampleProfile.cpp StripDeadPrototypes.cpp StripSymbols.cpp + WholeProgramDevirt.cpp ADDITIONAL_HEADER_DIRS ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms Index: lib/Transforms/IPO/IPO.cpp =================================================================== --- lib/Transforms/IPO/IPO.cpp +++ lib/Transforms/IPO/IPO.cpp @@ -53,6 +53,7 @@ initializeEliminateAvailableExternallyPass(Registry); initializeSampleProfileLoaderPass(Registry); initializeFunctionImportPassPass(Registry); + initializeWholeProgramDevirtPass(Registry); } void LLVMInitializeIPO(LLVMPassRegistryRef R) { Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -637,6 +637,16 @@ 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. @@ -661,6 +671,9 @@ if (VerifyInput) PM.add(createVerifierPass()); + if (OptLevel != 0) + addEarlyLTOOptimizationPasses(PM); + if (OptLevel > 1) addLTOOptimizationPasses(PM); Index: lib/Transforms/IPO/WholeProgramDevirt.cpp =================================================================== --- /dev/null +++ lib/Transforms/IPO/WholeProgramDevirt.cpp @@ -0,0 +1,726 @@ +//===- 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 + +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 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> Used; + for (const VirtualCallTarget &Target : Targets) { + ArrayRef 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 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 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 { + static VTableSlot getEmptyKey() { + return {DenseMapInfo::getEmptyKey(), + DenseMapInfo::getEmptyKey()}; + } + static VTableSlot getTombstoneKey() { + return {DenseMapInfo::getTombstoneKey(), + DenseMapInfo::getTombstoneKey()}; + } + static unsigned getHashValue(const VTableSlot &I) { + return DenseMapInfo::getHashValue(I.BitSetID) ^ + DenseMapInfo::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(CS.getInstruction())) { + BranchInst::Create(II->getNormalDest(), CS.getInstruction()); + II->getUnwindDest()->removePredecessor(II->getParent()); + } + CS->eraseFromParent(); + } +}; + +struct DevirtModule { + Module &M; + IntegerType *Int8Ty; + PointerType *Int8PtrTy; + IntegerType *Int32Ty; + + MapVector> CallSlots; + + DevirtModule(Module &M) + : M(M), Int8Ty(Type::getInt8Ty(M.getContext())), + Int8PtrTy(Type::getInt8PtrTy(M.getContext())), + Int32Ty(Type::getInt32Ty(M.getContext())) {} + void findLoadCallsAtConstantOffset(Metadata *BitSet, Value *Ptr, + uint64_t Offset, Value *VTable); + void findCallsAtConstantOffset(Metadata *BitSet, Value *Ptr, uint64_t Offset, + Value *VTable); + + void buildBitSets(std::vector &Bits, + DenseMap> &BitSets); + bool tryFindVirtualCallTargets(std::vector &TargetsForSlot, + const std::set &BitSetInfos, + uint64_t ByteOffset); + bool trySingleImplDevirt(ArrayRef TargetsForSlot, + MutableArrayRef CallSites); + bool tryEvaluateFunctionsWithArgs( + MutableArrayRef TargetsForSlot, + ArrayRef Args); + bool tryUniformRetValOpt(IntegerType *RetType, + ArrayRef TargetsForSlot, + MutableArrayRef CallSites); + bool tryUniqueRetValOpt(unsigned BitWidth, + ArrayRef TargetsForSlot, + MutableArrayRef CallSites); + bool tryVirtualConstProp(MutableArrayRef TargetsForSlot, + ArrayRef CallSites); + + void rebuildGlobal(VTableBits &B); + + bool run(); +}; + +struct WholeProgramDevirt : public ModulePass { + static char ID; + WholeProgramDevirt() : ModulePass(ID) { + initializeWholeProgramDevirtPass(*PassRegistry::getPassRegistry()); + } + bool runOnModule(Module &M) { return DevirtModule(M).run(); } +}; + +} // anonymous namespace + +INITIALIZE_PASS(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 DevirtModule::findCallsAtConstantOffset(Metadata *BitSet, Value *FPtr, + uint64_t Offset, Value *VTable) { + for (const Use &U : FPtr->uses()) { + Value *User = U.getUser(); + if (isa(User)) { + findCallsAtConstantOffset(BitSet, User, Offset, VTable); + } else if (auto CI = dyn_cast(User)) { + CallSlots[{BitSet, Offset}].push_back({VTable, CI}); + } else if (auto II = dyn_cast(User)) { + CallSlots[{BitSet, Offset}].push_back({VTable, II}); + } + } +} + +// Search for virtual calls that load from VPtr and add them to CallSlots. +void DevirtModule::findLoadCallsAtConstantOffset(Metadata *BitSet, Value *VPtr, + uint64_t Offset, + Value *VTable) { + for (const Use &U : VPtr->uses()) { + Value *User = U.getUser(); + if (isa(User)) { + findLoadCallsAtConstantOffset(BitSet, User, Offset, VTable); + } else if (isa(User)) { + findCallsAtConstantOffset(BitSet, User, Offset, VTable); + } else if (auto GEP = dyn_cast(User)) { + // Take into account the GEP offset. + if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) { + SmallVector Indices(GEP->op_begin() + 1, GEP->op_end()); + uint64_t GEPOffset = M.getDataLayout().getIndexedOffsetInType( + GEP->getSourceElementType(), Indices); + findLoadCallsAtConstantOffset(BitSet, User, Offset + GEPOffset, VTable); + } + } + } +} + +void DevirtModule::buildBitSets( + std::vector &Bits, + DenseMap> &BitSets) { + NamedMDNode *BitSetNM = M.getNamedMetadata("llvm.bitsets"); + if (!BitSetNM) + return; + + DenseMap GVToBits; + Bits.reserve(BitSetNM->getNumOperands()); + for (auto Op : BitSetNM->operands()) { + auto OpConstMD = dyn_cast_or_null(Op->getOperand(1)); + if (!OpConstMD) + continue; + auto BitSetID = Op->getOperand(0).get(); + + Constant *OpConst = OpConstMD->getValue(); + if (auto GA = dyn_cast(OpConst)) + OpConst = GA->getAliasee(); + auto OpGlobal = dyn_cast(OpConst); + if (!OpGlobal) + continue; + + uint64_t Offset = + cast( + cast(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}); + } + + return; +} + +bool DevirtModule::tryFindVirtualCallTargets( + std::vector &TargetsForSlot, + const std::set &BitSetInfos, uint64_t ByteOffset) { + for (const BitSetInfo &BS : BitSetInfos) { + if (!BS.Bits->GV->isConstant()) + return false; + + auto Init = dyn_cast(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(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 DevirtModule::trySingleImplDevirt( + ArrayRef TargetsForSlot, + MutableArrayRef 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 DevirtModule::tryEvaluateFunctionsWithArgs( + MutableArrayRef TargetsForSlot, + ArrayRef 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 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(RetVal)) + return false; + Target.RetVal = cast(RetVal)->getZExtValue(); + } + return true; +} + +bool DevirtModule::tryUniformRetValOpt( + IntegerType *RetType, ArrayRef TargetsForSlot, + MutableArrayRef 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 DevirtModule::tryUniqueRetValOpt( + unsigned BitWidth, ArrayRef TargetsForSlot, + MutableArrayRef 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 DevirtModule::tryVirtualConstProp( + MutableArrayRef TargetsForSlot, + ArrayRef CallSites) { + // This only works if the function returns an integer. + auto RetType = dyn_cast(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 &A, + const std::vector &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, + ByAPIntValue> + VCallSitesByConstantArg; + for (auto &&VCallSite : CallSites) { + std::vector Args; + if (VCallSite.CS.getType() != RetType) + continue; + for (auto &&Arg : + make_range(VCallSite.CS.arg_begin() + 1, VCallSite.CS.arg_end())) { + if (!isa(Arg)) + break; + Args.push_back(cast(&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( + (AllocBefore + 7) / 8 - Target.allocatedBeforeBytes() - 1, 0); + TotalPaddingAfter += std::max( + (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 { + Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo()); + Value *Val = B.CreateLoad(RetType, ValAddr); + Call.replaceAndErase(Val); + } + } + } + return true; +} + +void DevirtModule::rebuildGlobal(VTableBits &B) { + if (B.Before.Bytes.empty() && B.After.Bytes.empty()) + return; + + // 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 (size_t I = 0, Size = B.Before.Bytes.size(); I != Size / 2; ++I) + std::swap(B.Before.Bytes[I], 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->setSection(B.GV->getSection()); + 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{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(); +} + +bool DevirtModule::run() { + 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 SeenPtrs; + for (auto I = BitSetTestFunc->use_begin(), E = BitSetTestFunc->use_end(); + I != E;) { + auto CI = dyn_cast(I->getUser()); + ++I; + if (!CI) + continue; + + // Find llvm.assume intrinsics for this llvm.bitset.test call. + SmallVector Assumes; + for (const Use &CIU : CI->uses()) { + auto AssumeCI = dyn_cast(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()) { + Metadata *BitSet = + cast(CI->getArgOperand(1))->getMetadata(); + 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. + std::vector Bits; + DenseMap> BitSets; + buildBitSets(Bits, BitSets); + if (BitSets.empty()) + return true; + + // For each (bitset, offset) pair: + bool DidVirtualConstProp = false; + 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 TargetsForSlot; + if (!tryFindVirtualCallTargets(TargetsForSlot, BitSets[S.first.BitSetID], + S.first.ByteOffset)) + continue; + + if (trySingleImplDevirt(TargetsForSlot, S.second)) + continue; + + DidVirtualConstProp |= tryVirtualConstProp(TargetsForSlot, S.second); + } + + // Rebuild each global we touched as part of virtual constant propagation to + // include the before and after bytes. + if (DidVirtualConstProp) + for (VTableBits &B : Bits) + rebuildGlobal(B); + + return true; +} Index: test/Transforms/WholeProgramDevirt/bad-read-from-vtable.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/bad-read-from-vtable.ll @@ -0,0 +1,61 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/constant-arg.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/constant-arg.ll @@ -0,0 +1,76 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/devirt-single-impl.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/devirt-single-impl.ll @@ -0,0 +1,30 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/non-array-vtable.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/non-array-vtable.ll @@ -0,0 +1,28 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/non-constant-vtable.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/non-constant-vtable.ll @@ -0,0 +1,28 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/uniform-retval-invoke.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/uniform-retval-invoke.ll @@ -0,0 +1,42 @@ +; 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) personality i8* undef { + %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: br label %[[RET:[0-9A-Za-z]*]] + %result = invoke i32 %fptr_casted(i8* %obj) to label %ret unwind label %unwind + +unwind: + %x = landingpad i32 cleanup + unreachable + +ret: + ; CHECK: [[RET]]: + ; CHECK-NEXT: 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} Index: test/Transforms/WholeProgramDevirt/uniform-retval.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/uniform-retval.ll @@ -0,0 +1,35 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/unique-retval.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/unique-retval.ll @@ -0,0 +1,58 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/vcp-accesses-memory.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/vcp-accesses-memory.ll @@ -0,0 +1,34 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/vcp-no-this.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/vcp-no-this.ll @@ -0,0 +1,34 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/vcp-non-constant-arg.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/vcp-non-constant-arg.ll @@ -0,0 +1,34 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/vcp-too-wide-ints.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/vcp-too-wide-ints.ll @@ -0,0 +1,34 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/vcp-type-mismatch.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/vcp-type-mismatch.ll @@ -0,0 +1,64 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/vcp-uses-this.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/vcp-uses-this.ll @@ -0,0 +1,36 @@ +; 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} Index: test/Transforms/WholeProgramDevirt/virtual-const-prop-begin.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/virtual-const-prop-begin.ll @@ -0,0 +1,134 @@ +; 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 }, section "vt1sec" +@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*) +], section "vt1sec" + +; 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} Index: test/Transforms/WholeProgramDevirt/virtual-const-prop-end.ll =================================================================== --- /dev/null +++ test/Transforms/WholeProgramDevirt/virtual-const-prop-end.ll @@ -0,0 +1,128 @@ +; 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} Index: test/tools/gold/X86/disable-verify.ll =================================================================== --- test/tools/gold/X86/disable-verify.ll +++ test/tools/gold/X86/disable-verify.ll @@ -14,7 +14,7 @@ ; -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 Index: unittests/Transforms/IPO/CMakeLists.txt =================================================================== --- unittests/Transforms/IPO/CMakeLists.txt +++ unittests/Transforms/IPO/CMakeLists.txt @@ -6,4 +6,5 @@ add_llvm_unittest(IPOTests LowerBitSets.cpp + WholeProgramDevirt.cpp ) Index: unittests/Transforms/IPO/WholeProgramDevirt.cpp =================================================================== --- /dev/null +++ unittests/Transforms/IPO/WholeProgramDevirt.cpp @@ -0,0 +1,164 @@ +//===- 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{1}, VT1.Before.Bytes); + EXPECT_EQ(std::vector{1}, VT1.Before.BytesUsed); + EXPECT_EQ(std::vector{0}, VT2.Before.Bytes); + EXPECT_EQ(std::vector{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{1}, VT1.Before.Bytes); + EXPECT_EQ(std::vector{0x81}, VT1.Before.BytesUsed); + EXPECT_EQ(std::vector{0x80}, VT2.Before.Bytes); + EXPECT_EQ(std::vector{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{1, 12}), VT1.Before.Bytes); + EXPECT_EQ((std::vector{0x81, 0xff}), VT1.Before.BytesUsed); + EXPECT_EQ((std::vector{0x80, 34}), VT2.Before.Bytes); + EXPECT_EQ((std::vector{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{1, 12, 0, 56}), VT1.Before.Bytes); + EXPECT_EQ((std::vector{0x81, 0xff, 0xff, 0xff}), + VT1.Before.BytesUsed); + EXPECT_EQ((std::vector{0x80, 34, 0, 78}), VT2.Before.Bytes); + EXPECT_EQ((std::vector{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{1}, VT1.After.Bytes); + EXPECT_EQ(std::vector{1}, VT1.After.BytesUsed); + EXPECT_EQ(std::vector{0}, VT2.After.Bytes); + EXPECT_EQ(std::vector{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{1}, VT1.After.Bytes); + EXPECT_EQ(std::vector{0x81}, VT1.After.BytesUsed); + EXPECT_EQ(std::vector{0x80}, VT2.After.Bytes); + EXPECT_EQ(std::vector{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{1, 12}), VT1.After.Bytes); + EXPECT_EQ((std::vector{0x81, 0xff}), VT1.After.BytesUsed); + EXPECT_EQ((std::vector{0x80, 34}), VT2.After.Bytes); + EXPECT_EQ((std::vector{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{1, 12, 56, 0}), VT1.After.Bytes); + EXPECT_EQ((std::vector{0x81, 0xff, 0xff, 0xff}), + VT1.After.BytesUsed); + EXPECT_EQ((std::vector{0x80, 34, 78, 0}), VT2.After.Bytes); + EXPECT_EQ((std::vector{0x81, 0xff, 0xff, 0xff}), + VT2.After.BytesUsed); +}