Index: llvm/include/llvm/IR/LLVMContext.h =================================================================== --- llvm/include/llvm/IR/LLVMContext.h +++ llvm/include/llvm/IR/LLVMContext.h @@ -102,6 +102,7 @@ MD_associated = 22, // "associated" MD_callees = 23, // "callees" MD_irr_loop = 24, // "irr_loop" + MD_offset_type = 25, // "offset.type" }; /// Known operand bundle tag IDs, which always have the same value. All Index: llvm/include/llvm/InitializePasses.h =================================================================== --- llvm/include/llvm/InitializePasses.h +++ llvm/include/llvm/InitializePasses.h @@ -181,6 +181,7 @@ void initializeInstructionCombiningPassPass(PassRegistry&); void initializeInstructionSelectPass(PassRegistry&); void initializeInterleavedAccessPass(PassRegistry&); +void initializeInterleaveVTablesPass(PassRegistry &); void initializeInternalizeLegacyPassPass(PassRegistry&); void initializeIntervalPartitionPass(PassRegistry&); void initializeJumpThreadingPass(PassRegistry&); Index: llvm/include/llvm/Transforms/IPO.h =================================================================== --- llvm/include/llvm/Transforms/IPO.h +++ llvm/include/llvm/Transforms/IPO.h @@ -235,6 +235,9 @@ ModulePass *createLowerTypeTestsPass(ModuleSummaryIndex *ExportSummary, const ModuleSummaryIndex *ImportSummary); +/// This pass interleaves vtables and lowers llvm.typ.test intrinsic. +ModulePass *createInterleaveVTablesPass(); + /// This pass export CFI checks for use by external modules. ModulePass *createCrossDSOCFIPass(); Index: llvm/include/llvm/Transforms/IPO/InterleaveVTables.h =================================================================== --- /dev/null +++ llvm/include/llvm/Transforms/IPO/InterleaveVTables.h @@ -0,0 +1,39 @@ +//===- InterleaveVTables.h - VTables interleaving 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 vtable interleaving pass implementation that +// may be easily unit tested. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_INTERLEAVEVTABLES_H +#define LLVM_TRANSFORMS_IPO_INTERLEAVEVTABLES_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/PassManager.h" +#include +#include +#include +#include +#include + +namespace llvm { + +class Module; +class raw_ostream; + +class InterleaveVTablesPass : public PassInfoMixin { +public: + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); +}; + +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H Index: llvm/lib/IR/LLVMContext.cpp =================================================================== --- llvm/lib/IR/LLVMContext.cpp +++ llvm/lib/IR/LLVMContext.cpp @@ -61,6 +61,7 @@ {MD_associated, "associated"}, {MD_callees, "callees"}, {MD_irr_loop, "irr_loop"}, + {MD_offset_type, "offset.type"}, }; for (auto &MDKind : MDKinds) { Index: llvm/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/lib/Passes/PassBuilder.cpp +++ llvm/lib/Passes/PassBuilder.cpp @@ -61,7 +61,6 @@ #include "llvm/Support/Regex.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h" -#include "llvm/Transforms/Instrumentation/CGProfile.h" #include "llvm/Transforms/IPO/AlwaysInliner.h" #include "llvm/Transforms/IPO/ArgumentPromotion.h" #include "llvm/Transforms/IPO/CalledValuePropagation.h" @@ -77,6 +76,7 @@ #include "llvm/Transforms/IPO/GlobalSplit.h" #include "llvm/Transforms/IPO/InferFunctionAttrs.h" #include "llvm/Transforms/IPO/Inliner.h" +#include "llvm/Transforms/IPO/InterleaveVTables.h" #include "llvm/Transforms/IPO/Internalize.h" #include "llvm/Transforms/IPO/LowerTypeTests.h" #include "llvm/Transforms/IPO/PartialInlining.h" @@ -87,6 +87,7 @@ #include "llvm/Transforms/IPO/WholeProgramDevirt.h" #include "llvm/Transforms/InstCombine/InstCombine.h" #include "llvm/Transforms/Instrumentation/BoundsChecking.h" +#include "llvm/Transforms/Instrumentation/CGProfile.h" #include "llvm/Transforms/Instrumentation/GCOVProfiler.h" #include "llvm/Transforms/Instrumentation/InstrProfiling.h" #include "llvm/Transforms/Instrumentation/PGOInstrumentation.h" Index: llvm/lib/Passes/PassRegistry.def =================================================================== --- llvm/lib/Passes/PassRegistry.def +++ llvm/lib/Passes/PassRegistry.def @@ -53,6 +53,7 @@ MODULE_PASS("inferattrs", InferFunctionAttrsPass()) MODULE_PASS("insert-gcov-profiling", GCOVProfilerPass()) MODULE_PASS("instrprof", InstrProfiling()) +MODULE_PASS("interleavevtables", InterleaveVTablesPass()) MODULE_PASS("internalize", InternalizePass()) MODULE_PASS("invalidate", InvalidateAllAnalysesPass()) MODULE_PASS("ipsccp", IPSCCPPass()) Index: llvm/lib/Transforms/IPO/CMakeLists.txt =================================================================== --- llvm/lib/Transforms/IPO/CMakeLists.txt +++ llvm/lib/Transforms/IPO/CMakeLists.txt @@ -20,6 +20,7 @@ InferFunctionAttrs.cpp InlineSimple.cpp Inliner.cpp + InterleaveVTables.cpp Internalize.cpp LoopExtractor.cpp LowerTypeTests.cpp Index: llvm/lib/Transforms/IPO/IPO.cpp =================================================================== --- llvm/lib/Transforms/IPO/IPO.cpp +++ llvm/lib/Transforms/IPO/IPO.cpp @@ -38,6 +38,7 @@ initializeAlwaysInlinerLegacyPassPass(Registry); initializeSimpleInlinerPass(Registry); initializeInferFunctionAttrsLegacyPassPass(Registry); + initializeInterleaveVTablesPass(Registry); initializeInternalizeLegacyPassPass(Registry); initializeLoopExtractorPass(Registry); initializeBlockExtractorPass(Registry); Index: llvm/lib/Transforms/IPO/InterleaveVTables.cpp =================================================================== --- /dev/null +++ llvm/lib/Transforms/IPO/InterleaveVTables.cpp @@ -0,0 +1,949 @@ +//===- InterleaveVTables.cpp - VTables interleaving pass +//-------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Create a interleaved layout for all the virtual tables in a disjoint +// inheritance hierarchy and lower calls to llvm.type.test. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/IPO/InterleaveVTables.h" +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/EquivalenceClasses.h" +#include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/TinyPtrVector.h" +#include "llvm/ADT/Triple.h" +#include "llvm/Analysis/TypeMetadataUtils.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Attributes.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/GlobalAlias.h" +#include "llvm/IR/GlobalObject.h" +#include "llvm/IR/GlobalValue.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InlineAsm.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Intrinsics.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/PassManager.h" +#include "llvm/IR/Type.h" +#include "llvm/IR/Use.h" +#include "llvm/IR/User.h" +#include "llvm/IR/Value.h" +#include "llvm/Pass.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/TrailingObjects.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/ModuleUtils.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +using namespace llvm; + +#define DEBUG_TYPE "interleavevtables" + +STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers"); + +namespace { + +/// A POD-like structure that we use to store a global reference together with +/// its metadata types. In this pass we frequently need to query the set of +/// metadata types referenced by a global, which at the IR level is an expensive +/// operation involving a map lookup; this data structure helps to reduce the +/// number of times we need to do this lookup. +class GlobalTypeMember final : TrailingObjects { + friend TrailingObjects; + + GlobalVariable *GV; + size_t NTypes; + + size_t numTrailingObjects(OverloadToken) const { return NTypes; } + +public: + static GlobalTypeMember *create(BumpPtrAllocator &Alloc, GlobalVariable *GV, + ArrayRef Types) { + auto *GTM = static_cast(Alloc.Allocate( + totalSizeToAlloc(Types.size()), alignof(GlobalTypeMember))); + GTM->GV = GV; + GTM->NTypes = Types.size(); + std::uninitialized_copy(Types.begin(), Types.end(), + GTM->getTrailingObjects()); + return GTM; + } + + GlobalVariable *getGlobal() const { return GV; } + + ArrayRef types() const { + return makeArrayRef(getTrailingObjects(), NTypes); + } +}; + +/// This struct stores related information of each type for interleaving +struct TypeInterleavingInfo { + // Set of immediate children types + std::set ChildrenTypes; + // List of vtables that are only referenced by this type + std::vector ExclusiveVTables; + // List of offset global variables and offsets referenced in the + // compatible vtables of the type + std::vector OffsetGlobals; + std::vector Offsets; + // The index of the first compatible vtable in the ordered vtable list for the + // type + size_t StartIndex; + // One past the index of the last compatible vtable in the ordered vtable list + // for the type + size_t EndIndex; +}; + +/// All the vtable entries in a disjoint hierarchy that must have the same +/// distance from their address points form a entry group. +/// Each group is identified by a (type, offset) pair. +/// Also we keep a pointer to one of offset global variables that reference +/// the entries and this global variable will be replaced once the interleaving +/// layout is decided. +struct EntryGroup { + Metadata *TypeId; + int64_t Offset; + GlobalVariable *Global; +}; + +/// This class builds the type hierarchy of the disjoint type set. The disjoint +/// type set is a tree because vtables have already been split. By starting +/// with the types having the smallest referenced vtable sets, this class +/// rebuild the hierarchy tree by doing a depth-first traversal of it. +struct HierarchyBuilder { + /// The computed layout. Each element of this vector contains a fragment of + /// layout (which may be empty) consisting of pointers to global variables. + std::vector> Fragments; + + /// Mapping from vtable to fragment index. + std::map FragmentMap; + + /// Mapping from fragment index to type. + std::map TypeMap; + + HierarchyBuilder() : Fragments(1), FragmentMap(), TypeMap() {} + + /// Add GlobalSet to the layout while trying to keep its global variables + /// contiguous. Also, populate TypeInterleavingInfo of the type for later + /// interleaving. If a previously seen fragment uses any of GlobalSet's global + /// variables, that fragment will be laid out inside GlobalSet. + void addFragment(Metadata *Type, const std::set &GlobalSet, + TypeInterleavingInfo &TII); +}; + +class InterleaveVTablesModule { + Module &M; + + PointerType *Int8PtrTy = Type::getInt8PtrTy(M.getContext()); + PointerType *Int64PtrTy = Type::getInt64PtrTy(M.getContext()); + IntegerType *Int32Ty = Type::getInt32Ty(M.getContext()); + IntegerType *Int64Ty = Type::getInt64Ty(M.getContext()); + IntegerType *IntPtrTy = M.getDataLayout().getIntPtrType(M.getContext(), 0); + // Size in byte of an vtable entry + uint64_t EntrySize; + + // Mapping from type identifiers to the call sites that test them + struct TypeIdUserInfo { + std::vector CallSites; + }; + DenseMap TypeIdUsers; + + DenseMap InterleavingInfoMap; + + void getOffsetFromGlobalVaribleName(StringRef GlobalVaribleName, + int64_t &Offset); + void traverseHierarchy(Metadata *BaseType, + std::vector &OrderedGlobals, + std::vector &Groups, + std::map ProcessedGroups); + void lowerTypeTestCalls(GlobalVariable *CombinedVTableAddr); + void interleaveGlobalVariables( + std::vector &Groups, + std::vector &OrderedGlobals, + DenseMap &AddressPointIndices); + void + handleDisjointSet(std::map TypeIds, + ArrayRef Globals, + DenseMap &AddressPointIndices); + +public: + InterleaveVTablesModule(Module &M); + + bool lower(); +}; + +struct InterleaveVTables : public ModulePass { + static char ID; + + InterleaveVTables() : ModulePass(ID) { + initializeInterleaveVTablesPass(*PassRegistry::getPassRegistry()); + } + + bool runOnModule(Module &M) override { + return InterleaveVTablesModule(M).lower(); + } +}; + +} // end anonymous namespace + +char InterleaveVTables::ID = 0; + +INITIALIZE_PASS(InterleaveVTables, "interleavevtables", "Interleave vtables", + false, false) + +void HierarchyBuilder::addFragment(Metadata *Type, + const std::set &GlobalSet, + TypeInterleavingInfo &TII) { + // Create a new fragment to hold the layout for F. + Fragments.emplace_back(); + std::vector &Fragment = Fragments.back(); + uint64_t FragmentIndex = Fragments.size() - 1; + + for (auto GV : GlobalSet) { + if (FragmentMap.find(GV) == FragmentMap.end()) { + // We haven't seen this vtable before, so just add it to the current + // fragment. + Fragment.push_back(GV); + // Since we haven't seen this vtable, it means that it is exclusive to + // this type. + TII.ExclusiveVTables.push_back(GV); + } else { + // Since we have seen this vtable in a old fragment, that fragment must + // belong to a children type of this type. + uint64_t OldFragmentIndex = FragmentMap[GV]; + Metadata *ChildType = TypeMap[OldFragmentIndex]; + if (TII.ChildrenTypes.find(ChildType) == TII.ChildrenTypes.end()) + TII.ChildrenTypes.emplace(ChildType); + + // This index belongs to an existing fragment. Copy the elements of the + // old fragment into this one and clear the old fragment. We don't update + // the fragment map just yet, this ensures that any further references to + // indices from the old fragment in this fragment do not insert any more + // indices. + std::vector &OldFragment = Fragments[OldFragmentIndex]; + Fragment.insert(Fragment.end(), OldFragment.begin(), OldFragment.end()); + OldFragment.clear(); + } + } + + // Update the fragment map to point our object indices to this fragment. + for (GlobalVariable *GV : Fragment) + FragmentMap[GV] = FragmentIndex; + + // Update the type map to point the fragment to this type. + TypeMap[FragmentIndex] = Type; +} + +ModulePass *llvm::createInterleaveVTablesPass() { + return new InterleaveVTables; +} + +/// This function parse the name of each global variable. +/// Offset global variables' name have the format: __[type name]$[offset] +void InterleaveVTablesModule::getOffsetFromGlobalVaribleName(StringRef GVName, + int64_t &Offset) { + if (!GVName.contains("$")) + report_fatal_error( + "The name of the offset global variable has an unexpected name."); + + size_t Loc = GVName.find('$') + 1; + if (Loc >= GVName.size()) + report_fatal_error( + "The name of the offset global variable has an unexpected name."); + StringRef OffsetStr = GVName.substr(Loc); + + // When consumeInteger failed to parse the string, + // it returns true. + if (OffsetStr.consumeInteger(10, Offset)) + report_fatal_error( + "The name of the offset global variable has an unexpected name."); +} + +static bool isKnownTypeIdMember(Metadata *TypeId, const DataLayout &DL, + Value *V, uint64_t COffset) { + if (auto GV = dyn_cast(V)) { + SmallVector Types; + GV->getMetadata(LLVMContext::MD_type, Types); + for (MDNode *Type : Types) { + if (Type->getOperand(1) != TypeId) + continue; + uint64_t Offset = + cast( + cast(Type->getOperand(0))->getValue()) + ->getZExtValue(); + if (COffset == Offset) + return true; + } + return false; + } + + if (auto GEP = dyn_cast(V)) { + APInt APOffset(DL.getPointerSizeInBits(0), 0); + bool Result = GEP->accumulateConstantOffset(DL, APOffset); + if (!Result) + return false; + COffset += APOffset.getZExtValue(); + return isKnownTypeIdMember(TypeId, DL, GEP->getPointerOperand(), COffset); + } + + if (auto Op = dyn_cast(V)) { + if (Op->getOpcode() == Instruction::BitCast) + return isKnownTypeIdMember(TypeId, DL, Op->getOperand(0), COffset); + + if (Op->getOpcode() == Instruction::Select) + return isKnownTypeIdMember(TypeId, DL, Op->getOperand(1), COffset) && + isKnownTypeIdMember(TypeId, DL, Op->getOperand(2), COffset); + } + + return false; +} + +/// Replace each call to llvm.type.test with a corresponding range check. +void InterleaveVTablesModule::lowerTypeTestCalls( + GlobalVariable *InterleavedVTable) { + for (auto &TypdIdAndUserInfo : TypeIdUsers) { + Metadata *TypeId = TypdIdAndUserInfo.first; + TypeIdUserInfo &TIUI = TypdIdAndUserInfo.second; + + // The index of address point of the first compatible vtable + // in the interleaved layout. + size_t FirstAddrPtIndex = 2 * InterleavingInfoMap[TypeId].StartIndex + 2; + size_t Range = InterleavingInfoMap[TypeId].EndIndex - + InterleavingInfoMap[TypeId].StartIndex; + + Constant *InterleavedVTIdxs[] = { + ConstantInt::get(Int32Ty, 0), + ConstantInt::get(Int32Ty, FirstAddrPtIndex)}; + Type *VTableType = InterleavedVTable->getValueType(); + errs() << "VTableType = " << *VTableType << "\n"; + Constant *FirstAddrPt = ConstantExpr::getGetElementPtr( + VTableType, InterleavedVTable, InterleavedVTIdxs); + Constant *FirstAddrPtAsInt = + ConstantExpr::getPtrToInt(FirstAddrPt, IntPtrTy); + + for (auto &CI : TIUI.CallSites) { + // Value to replace calls to llvm.type.test + Value *Lowered = nullptr; + Value *Ptr = CI->getArgOperand(0); + const DataLayout &DL = M.getDataLayout(); + if (isKnownTypeIdMember(TypeId, DL, Ptr, 0)) + Lowered = ConstantInt::getTrue(M.getContext()); + else { + IRBuilder<> B(CI); + Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy); + if (Range == 1) + Lowered = B.CreateICmpEQ(PtrAsInt, FirstAddrPtAsInt); + else { + // We need to check that the offset both falls within our range and is + // suitably aligned. We can check both properties at the same time by + // performing a right rotate by log2(2*entry_size) followed by an + // integer comparison against the range size. The rotate will move the + // lower order bits that need to be zero into the higher order bits of + // the result, causing the comparison to fail if they are nonzero. + Value *PtrOffset = B.CreateSub(PtrAsInt, FirstAddrPtAsInt); + size_t RotateAmount = countTrailingZeros(EntrySize * 2, ZB_Undefined); + Constant *RotateAmountConstant = + ConstantInt::get(IntPtrTy, RotateAmount); + Value *OffsetSHR = B.CreateLShr(PtrOffset, RotateAmountConstant); + Constant *RangeConstant = ConstantInt::get(IntPtrTy, Range - 1); + Lowered = B.CreateICmpULE(OffsetSHR, RangeConstant); + } + } + CI->replaceAllUsesWith(Lowered); + CI->eraseFromParent(); + } + } +} + +/// Interleave the vtables and lower the llvm.type.test calls. +void InterleaveVTablesModule::interleaveGlobalVariables( + std::vector &Groups, + std::vector &OrderedGlobals, + // Map each vtable to the index of the entry at the address point + DenseMap &AddressPointIndices) { + // Two temporary vectors of entries to be interleaved: + // UpperEntries is initialized with offset-to-top entries. + // LowerEntreis is initialized with RTTI entries. + std::vector UpperEntries; + std::vector LowerEntries; + + // The interleaved layout after merging UpperEntries and LowerEntries. + std::vector InterleavedEntries; + + // Map each vtable to the index of its address point in the interleaved + // layout. + DenseMap AddrPoints; + + // For each vtable, map the old offset of each entry to the new offset in the + // interleaved layout of the entry. This table is also used for verifying the + // interleaved layout. + DenseMap> OldToNewOffsets; + + // Initialized UpperEntires and LowerEntries. + for (auto GV : OrderedGlobals) { + UpperEntries.push_back(GV->getInitializer()->getAggregateElement( + (unsigned)AddressPointIndices[GV] - 2)); + LowerEntries.push_back(GV->getInitializer()->getAggregateElement( + (unsigned)AddressPointIndices[GV] - 1)); + + // In the interleaving layout, the index of the address point for each + // vtable is the index of the entry immediately following the RTTI entry. + // Since we store RTTI entries in LowerEntries, the twice of its size is the + // index of the entry at the address point. + AddrPoints[GV] = LowerEntries.size() * 2; + + // Offsets for offset-to-top and RTTI do not change. + OldToNewOffsets[GV][-2] = -2; + OldToNewOffsets[GV][-1] = -1; + } + + std::vector *CurList; + + // Index of the first entry of each group in the interleaved layout. + int64_t InterleavedIndex; + for (const auto &Group : Groups) { + Metadata *TypeId = Group.TypeId; + + // Choose the shorter list to add the entries of current entry group. + if (UpperEntries.size() <= LowerEntries.size()) { + CurList = &UpperEntries; + InterleavedIndex = 2 * UpperEntries.size(); + } else { + CurList = &LowerEntries; + InterleavedIndex = 2 * LowerEntries.size() + 1; + } + + // All the entries in a entry group will have the same offset from their + // corresponding address points, so we only need to calculate the offset of + // the first entry of the group from its address point. + GlobalVariable *FirstVT = + OrderedGlobals[InterleavingInfoMap[TypeId].StartIndex]; + int64_t NewOffset = InterleavedIndex - AddrPoints[FirstVT]; + + // Replace references to the offset global variable with the newly computed + // offset in the interleaving layout. + GlobalVariable *OffsetGlobal = Group.Global; + OffsetGlobal->replaceAllUsesWith(ConstantExpr::getIntToPtr( + ConstantInt::get(Int64Ty, NewOffset), Int64PtrTy)); + OffsetGlobal->eraseFromParent(); + + // Iterate through the compatible vtables of this entry group and + // add all the entries of this group to CurList. + size_t StartIndex = InterleavingInfoMap[TypeId].StartIndex; + size_t EndIndex = InterleavingInfoMap[TypeId].EndIndex; + int64_t Offset = Group.Offset; + for (size_t I = StartIndex; I < EndIndex; I++) { + GlobalVariable *GV = OrderedGlobals[I]; + OldToNewOffsets[GV][Offset] = NewOffset; + CurList->push_back(GV->getInitializer()->getAggregateElement( + Offset + (int64_t)AddressPointIndices[GV])); + } + } + + // Pad the shorter list + if (UpperEntries.size() != LowerEntries.size()) { + CurList = UpperEntries.size() < LowerEntries.size() ? &UpperEntries + : &LowerEntries; + while (UpperEntries.size() != LowerEntries.size()) { + CurList->push_back(ConstantPointerNull::get(Int8PtrTy)); + } + } + + // Interleave the two vector + for (size_t I = 0; I < UpperEntries.size(); I++) { + InterleavedEntries.push_back(UpperEntries[I]); + InterleavedEntries.push_back(LowerEntries[I]); + } + + // Verify that each entry in a old VTable has the same content as the + // corresponding entry in the interleaved table does. + for (const auto &GV : OrderedGlobals) { + ConstantArray *OldArray = dyn_cast(GV->getInitializer()); + if (OldArray != nullptr) { + for (int64_t I = 0; I < OldArray->getNumOperands(); ++I) { + if (OldToNewOffsets[GV].count(I - (int64_t)AddressPointIndices[GV]) == + 0) + continue; + int64_t OldOffsetFromAddrPt = I - (int64_t)AddressPointIndices[GV]; + int64_t NewOffsetFromAddrPt = OldToNewOffsets[GV][OldOffsetFromAddrPt]; + uint64_t NewOffsetFromBeginning = + (uint64_t)(NewOffsetFromAddrPt + AddrPoints[GV]); + if (OldArray->getOperand(I) != + InterleavedEntries[NewOffsetFromBeginning]) { + LLVM_DEBUG({ + dbgs() + << "The original VTable " << *GV + << " and the interleaved VTable have different values for the " + << I << "th entry\n"; + }); + report_fatal_error( + "The old VTable and the interleaved VTable are inconsistent."); + } + } + } else { // The initialzer of the global variable is a ConstantDataArray + ConstantDataArray *OldDataArray = + dyn_cast(GV->getInitializer()); + for (int64_t I = 0; I < OldDataArray->getNumElements(); ++I) { + if (OldToNewOffsets[GV].count(I - (int64_t)AddressPointIndices[GV]) == + 0) + continue; + int64_t OldOffsetFromAddrPt = I - (int64_t)AddressPointIndices[GV]; + int64_t NewOffsetFromAddrPt = OldToNewOffsets[GV][OldOffsetFromAddrPt]; + uint64_t NewOffsetFromBeginning = + (uint64_t)(NewOffsetFromAddrPt + AddrPoints[GV]); + ConstantInt *CInterleaved = + cast(InterleavedEntries[NewOffsetFromBeginning]); + ConstantInt *COriginal = + cast(OldDataArray->getElementAsConstant(I)); + if (COriginal->getSExtValue() != CInterleaved->getSExtValue()) { + LLVM_DEBUG({ + dbgs() + << "The original VTable " << *GV + << " and the interleaved VTable have different values for the " + << I << "th entry\n"; + }); + report_fatal_error( + "The old VTable and the interleaved VTable are inconsistent."); + } + } + } + } + + // Make sure that each element in InterleavedEntries is of type Int8Ptr + for (auto &Elem : InterleavedEntries) + if (Elem->getType() != Int8PtrTy) + Elem = ConstantExpr::getIntToPtr(Elem, Int8PtrTy); + + Constant *NewInit = ConstantArray::get( + ArrayType::get(Int8PtrTy, InterleavedEntries.size()), InterleavedEntries); + auto *InterleavedVTable = new GlobalVariable(M, NewInit->getType(), true, + GlobalValue::PrivateLinkage, + NewInit, "interleavedvtable"); + + // Lower calls to llvm.type.test + lowerTypeTestCalls(InterleavedVTable); + + // Build aliases pointing to offsets into the interleaved vtable for each + // vtable from which we built the interleaved one, and replace references + // to the original vtables with references to the aliases. + int32_t StartOffset = 0; + for (auto GV : OrderedGlobals) { + // The first vtable in the interleaved layout always starts at offset 0, and + // the beginnings of two adjacent vtable are off by two. + Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0), + ConstantInt::get(Int32Ty, StartOffset)}; + Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr( + NewInit->getType(), InterleavedVTable, CombinedGlobalIdxs); + assert(GV->getType()->getAddressSpace() == 0); + GlobalAlias *GAlias = GlobalAlias::create(Int8PtrTy, 0, GV->getLinkage(), + "", CombinedGlobalElemPtr, &M); + GAlias->setVisibility(GV->getVisibility()); + GAlias->takeName(GV); + GV->replaceAllUsesWith(ConstantExpr::getBitCast(GAlias, GV->getType())); + GV->eraseFromParent(); + StartOffset += 2; + } +} + +// Traverse the type hierarchy in the pre-order to +// (1) order vtables by a pre-order traversal of the type hierarchy +// This ensures that for any class all the compatible virtual tables +// will appear consecutively. +// (2) collect the range of vtables that each type is compatible with. +// (3) collect unique entry groups. +// +// BaseType: the root type of the disjoint hierarchy. +// Since this pass only runs after vtables have been split, +// it is guaranteed that there is only one base type. +// +// OrderedGTMs: the result of all the vtables ordered +// by a pre-order traversal of the disjoint hierarchy. +// +// Groups: the result of all the unique entry groups. +// +// ProcessedGroups: all the entry groups that the +// current types's ancestor types have and one offset +// global variable for this entry group. We need this because +// we only want to add entry groups we haven't seen to +// Groups. +void InterleaveVTablesModule::traverseHierarchy( + Metadata *BaseType, std::vector &OrderedGlobals, + std::vector &Groups, + std::map ProcessedGroups) { + + // Set the start index of the vtable in the list for the type. + InterleavingInfoMap[BaseType].StartIndex = OrderedGlobals.size(); + + // Add each type's exclusive vtables to the list. Since we traverse the + // hierarchy in the pre-order, all the compatible vtables of a type will + // appear consecutively. + std::vector &ExclusiveVTables = + InterleavingInfoMap[BaseType].ExclusiveVTables; + OrderedGlobals.insert(OrderedGlobals.end(), ExclusiveVTables.begin(), + ExclusiveVTables.end()); + + // Now we add referenced offsets of the type to Groups + // Note that it is possible that we already add that entry group when + // we processed an ancestor type of this type, so we only add groups + // that are not in ProcessedGroups. + std::vector &Offsets = InterleavingInfoMap[BaseType].Offsets; + std::vector &OffsetGlobals = + InterleavingInfoMap[BaseType].OffsetGlobals; + for (size_t I = 0; I < Offsets.size(); I++) { + int64_t Offset = Offsets[I]; + GlobalVariable *GV = OffsetGlobals[I]; + + // If we have added this entry group, we don't want to do it again. + // Instead, we will replace all uses of the offset global variable + // associated with the one we saw first. + if (ProcessedGroups.find(Offset) != ProcessedGroups.end()) { + GV->replaceAllUsesWith(ProcessedGroups[Offset]); + GV->eraseFromParent(); + continue; + } + ProcessedGroups[Offset] = GV; + Groups.emplace_back(EntryGroup{BaseType, Offset, GV}); + } + + // Now call this function recursively on all the children types. + for (auto Child : InterleavingInfoMap[BaseType].ChildrenTypes) + traverseHierarchy(Child, OrderedGlobals, Groups, ProcessedGroups); + + // Now that all the compatible vtables of BaseType have been added to the + // ordered list, we can set the end index of the compatible vtable range. + InterleavingInfoMap[BaseType].EndIndex = OrderedGlobals.size(); +} + +void InterleaveVTablesModule::handleDisjointSet( + std::map TypeAndUniqueIds, + ArrayRef Globals, + DenseMap &AddressPointIndices) { + // For each type identifier, build a set of vtables that refer to members of + // the type identifier. + std::map> TypeMembersMap; + + for (GlobalTypeMember *GTM : Globals) { + for (MDNode *Type : GTM->types()) { + // Type = { offset, type identifier } + Metadata *TypeId = Type->getOperand(1); + if (TypeAndUniqueIds.find(TypeId) != TypeAndUniqueIds.end()) + TypeMembersMap[TypeId].insert(GTM->getGlobal()); + } + } + + // Order the sets of vtables by size. + std::vector>> + TypeMembersVector(TypeMembersMap.begin(), TypeMembersMap.end()); + std::stable_sort( + TypeMembersVector.begin(), TypeMembersVector.end(), + [](const std::pair> &O1, + const std::pair> &O2) { + return O1.second.size() < O2.second.size(); + }); + + // Create a HierarchyBuilder and provide it with vtable sets with increasing + // size as layout fragments. Since vtables have been split, this will ensure a + // depth-first traversal in the type hierarchy. During the traversal, the + // HierarchyBuilder builds the type hierarchy from bottom up and this + // hierarchy will be used to order vtables by a pre-order traversal, which + // guarantees that for each type the compatible vtables are consecutive in the + // ordered vtable list. + HierarchyBuilder HB; + for (const auto &TypeAndGlobalSet : TypeMembersVector) { + TypeInterleavingInfo &TII = InterleavingInfoMap[TypeAndGlobalSet.first]; + HB.addFragment(TypeAndGlobalSet.first, TypeAndGlobalSet.second, TII); + } + + // All the entry groups in this disjoint hierarchy + std::vector Groups; + + // A vector of vtables ordered by a pre-order + // traversal of the disjoint hierarchy + std::vector OrderedGlobals; + + // Since we have sorted TypeMembers in the order of increasing size, + // the last element in it is the base type of this disjoint hierarchy. + Metadata *BaseType = TypeMembersVector.back().first; + + traverseHierarchy(BaseType, OrderedGlobals, Groups, {}); + + // Sort entry groups in the order of decreasing size + llvm::sort(Groups.begin(), Groups.end(), + [&](const EntryGroup &Left, const EntryGroup &Right) { + size_t LeftSize = InterleavingInfoMap[Left.TypeId].EndIndex - + InterleavingInfoMap[Left.TypeId].StartIndex; + size_t RightSize = InterleavingInfoMap[Right.TypeId].EndIndex - + InterleavingInfoMap[Right.TypeId].StartIndex; + uint64_t LeftIndex = TypeAndUniqueIds[Left.TypeId]; + uint64_t RightIndex = TypeAndUniqueIds[Right.TypeId]; + if (LeftSize != RightSize) + return LeftSize > RightSize; + if (Left.Offset != Right.Offset) + return Left.Offset < Right.Offset; + return LeftIndex < RightIndex; + }); + + // Create the interleaved layout + interleaveGlobalVariables(Groups, OrderedGlobals, AddressPointIndices); +} + +/// Lower all type tests in this module. +InterleaveVTablesModule::InterleaveVTablesModule(Module &M) : M(M) {} + +bool InterleaveVTablesModule::lower() { + Function *TypeTestFunc = + M.getFunction(Intrinsic::getName(Intrinsic::type_test)); + if (!TypeTestFunc || TypeTestFunc->use_empty()) + return false; + + // Equivalence class set containing type identifiers and the vtables that + // reference them. This is used to partition the set of type identifiers in + // the module into disjoint sets. + using GlobalClassesTy = + EquivalenceClasses>; + GlobalClassesTy GlobalClasses; + + // Verify the type metadata and build a few data structures to let us + // efficiently enumerate the type identifiers associated with a vtable: + // a list of GlobalTypeMembers (a vtable stored alongside a vector + // of associated type metadata) and a mapping from type identifiers to their + // list of GlobalTypeMembers and last observed index in the list of vtables. + // The indices will be used later to deterministically order the list of type + // identifiers. + BumpPtrAllocator Alloc; + struct TIInfo { + unsigned UniqueId; + std::vector RefGlobals; + }; + DenseMap TypeIdInfo; + unsigned CurUniqueId = 0; + SmallVector TypeNodes; + + // Map each vtable to the offset of the address point in bytes + DenseMap AddressPointIndices; + for (GlobalVariable &GV : M.globals()) { + if (GV.isDeclarationForLinker()) + continue; + + TypeNodes.clear(); + + // Each entry group in vtables are identified by + // a (type id, offset in vtable) pair. The front-end generates + // a global variable for each used offset in vtable with + // offset.type metadata to associate each offset global variable with + // its type id. In the loop through all the global variables, + // we collect referenced offsets of each vtable. + GV.getMetadata(LLVMContext::MD_offset_type, TypeNodes); + if (!TypeNodes.empty()) { + if (TypeNodes.size() != 1) + report_fatal_error("A global variable can only be associated with one " + "type offset metadata"); + MDNode *Type = TypeNodes[0]; + if (Type->getNumOperands() != 1) + report_fatal_error( + "All operands of offset.type metadata must have 1 element"); + int64_t Offset; + getOffsetFromGlobalVaribleName(GV.getName(), Offset); + TypeInterleavingInfo &TII = InterleavingInfoMap[Type->getOperand(0)]; + TII.Offsets.emplace_back(Offset); + TII.OffsetGlobals.emplace_back(&GV); + continue; + } + + TypeNodes.clear(); + GV.getMetadata(LLVMContext::MD_type, TypeNodes); + if (TypeNodes.empty()) + continue; + + // We can only interleave vtables when they have been split + // so first check if the vtables have been split + Constant *Init = GV.getInitializer(); + if (!Init->getType()->isArrayTy()) + report_fatal_error("The global initializer is not an array."); + ArrayType *InitTy = cast(Init->getType()); + Type *ElemType = InitTy->getElementType(); + const DataLayout &DL = GV.getParent()->getDataLayout(); + EntrySize = DL.getTypeAllocSize(ElemType); + + auto *GTM = GlobalTypeMember::create(Alloc, &GV, TypeNodes); + uint64_t BytesBeforeAddrPt = UINT64_MAX; + for (MDNode *Type : TypeNodes) { + // Verify type metadata + if (Type->getNumOperands() != 2) + report_fatal_error( + "All operands of type metadata must have 2 elements"); + if (GV.isThreadLocal()) + report_fatal_error("Bit set element may not be thread-local"); + if (GV.hasSection()) + report_fatal_error( + "A member of a type identifier may not have an explicit section"); + + // FIXME: We previously checked that global var member of a type + // identifier must be a definition, but the IR linker may leave type + // metadata on declarations. We should restore this check after fixing + // PR31759. + + auto OffsetConstMD = dyn_cast(Type->getOperand(0)); + if (!OffsetConstMD) + report_fatal_error("Type offset must be a constant"); + auto OffsetInt = dyn_cast(OffsetConstMD->getValue()); + if (!OffsetInt) + report_fatal_error("Type offset must be an integer constant"); + + // Offset of type metadata + uint64_t Offset = OffsetInt->getZExtValue(); + + // Type metadata of a virtual table should have the same offset + if (BytesBeforeAddrPt == UINT64_MAX) + BytesBeforeAddrPt = Offset; + else if (BytesBeforeAddrPt != Offset) + report_fatal_error("Multiple type metadata offsets."); + + auto &Info = TypeIdInfo[Type->getOperand(1)]; + Info.UniqueId = ++CurUniqueId; + Info.RefGlobals.push_back(GTM); + } + AddressPointIndices[GTM->getGlobal()] = BytesBeforeAddrPt / EntrySize; + } + + auto AddTypeIdUse = [&](Metadata *TypeId) -> TypeIdUserInfo & { + // Add the call site to the list of call sites for this type identifier. We + // also use TypeIdUsers to keep track of whether we have seen this type + // identifier before. If we have, we don't need to re-add the referenced + // vtables to the equivalence class. + auto Ins = TypeIdUsers.insert({TypeId, {}}); + if (Ins.second) { + // Add the type identifier to the equivalence class. + GlobalClassesTy::iterator GCI = GlobalClasses.insert(TypeId); + GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI); + + // Add the referenced vtables to the type identifier's equivalence class. + for (GlobalTypeMember *GTM : TypeIdInfo[TypeId].RefGlobals) + CurSet = GlobalClasses.unionSets( + CurSet, GlobalClasses.findLeader(GlobalClasses.insert(GTM))); + } + + return Ins.first->second; + }; + + for (const Use &U : TypeTestFunc->uses()) { + auto CI = cast(U.getUser()); + + auto TypeIdMDVal = dyn_cast(CI->getArgOperand(1)); + if (!TypeIdMDVal) + report_fatal_error("Second argument of llvm.type.test must be metadata"); + auto TypeId = TypeIdMDVal->getMetadata(); + auto TypeIdStr = dyn_cast(TypeId); + if (!TypeIdStr) + report_fatal_error( + "Second argument of llvm.type.test must be a metadata string"); + AddTypeIdUse(TypeId).CallSites.push_back(CI); + } + + if (GlobalClasses.empty()) + return false; + + // Build a list of disjoint sets ordered by their maximum global index for + // determinism. + std::vector> Sets; + for (GlobalClassesTy::iterator I = GlobalClasses.begin(), + E = GlobalClasses.end(); + I != E; ++I) { + if (!I->isLeader()) + continue; + ++NumTypeIdDisjointSets; + + unsigned MaxUniqueId = 0; + for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I); + MI != GlobalClasses.member_end(); ++MI) { + if (auto *MD = MI->dyn_cast()) + MaxUniqueId = std::max(MaxUniqueId, TypeIdInfo[MD].UniqueId); + } + Sets.emplace_back(I, MaxUniqueId); + } + llvm::sort(Sets.begin(), Sets.end(), + [](const std::pair &S1, + const std::pair &S2) { + return S1.second < S2.second; + }); + + // For each disjoint set we found + for (const auto &S : Sets) { + // Build the list of type identifiers in this disjoint set. + std::vector TypeIds; + std::vector Globals; + for (GlobalClassesTy::member_iterator MI = + GlobalClasses.member_begin(S.first); + MI != GlobalClasses.member_end(); ++MI) { + if (MI->is()) + TypeIds.push_back(MI->get()); + else if (MI->is()) + Globals.push_back(MI->get()); + } + + // Order type identifiers by unique ID for determinism. This ordering is + // stable as there is a one-to-one mapping between metadata and unique IDs. + llvm::sort(TypeIds.begin(), TypeIds.end(), [&](Metadata *M1, Metadata *M2) { + return TypeIdInfo[M1].UniqueId < TypeIdInfo[M2].UniqueId; + }); + + // Create a map from TypeIds to the corresponding UniqueIds + std::map TypeAndUniqueIds; + for (auto TypeId : TypeIds) + TypeAndUniqueIds[TypeId] = TypeIdInfo[TypeId].UniqueId; + + // Interleave virtual tables and lower calls to llvm.type.test. + handleDisjointSet(TypeAndUniqueIds, Globals, AddressPointIndices); + } + + return true; +} + +PreservedAnalyses InterleaveVTablesPass::run(Module &M, + ModuleAnalysisManager &AM) { + bool Changed = InterleaveVTablesModule(M).lower(); + if (!Changed) + return PreservedAnalyses::all(); + return PreservedAnalyses::none(); +} Index: llvm/lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -152,6 +152,10 @@ "enable-gvn-sink", cl::init(false), cl::Hidden, cl::desc("Enable the GVN sinking pass (default = off)")); +static cl::opt + EnableVTableInterleaving("enable-vtable-interleaving", cl::init(false), + cl::desc("Enable VTables interleaving")); + PassManagerBuilder::PassManagerBuilder() { OptLevel = 2; SizeLevel = 0; @@ -953,10 +957,14 @@ // in the current module. PM.add(createCrossDSOCFIPass()); - // Lower type metadata and the type.test intrinsic. This pass supports Clang's - // control flow integrity mechanisms (-fsanitize=cfi*) and needs to run at - // link time if CFI is enabled. The pass does nothing if CFI is disabled. - PM.add(createLowerTypeTestsPass(ExportSummary, nullptr)); + if (EnableVTableInterleaving) + PM.add(createInterleaveVTablesPass()); + else + // Lower type metadata and the type.test intrinsic. This pass supports + // Clang's control flow integrity mechanisms (-fsanitize=cfi*) and needs to + // run at link time if CFI is enabled. The pass does nothing if CFI is + // disabled. + PM.add(createLowerTypeTestsPass(ExportSummary, nullptr)); if (OptLevel != 0) addLateLTOOptimizationPasses(PM); Index: llvm/test/ThinLTO/X86/lazyload_metadata.ll =================================================================== --- llvm/test/ThinLTO/X86/lazyload_metadata.ll +++ llvm/test/ThinLTO/X86/lazyload_metadata.ll @@ -10,13 +10,13 @@ ; RUN: llvm-lto -thinlto-action=import %t2.bc -thinlto-index=%t3.bc \ ; RUN: -o /dev/null -stats \ ; RUN: 2>&1 | FileCheck %s -check-prefix=LAZY -; LAZY: 55 bitcode-reader - Number of Metadata records loaded +; LAZY: 57 bitcode-reader - Number of Metadata records loaded ; LAZY: 2 bitcode-reader - Number of MDStrings loaded ; RUN: llvm-lto -thinlto-action=import %t2.bc -thinlto-index=%t3.bc \ ; RUN: -o /dev/null -disable-ondemand-mds-loading -stats \ ; RUN: 2>&1 | FileCheck %s -check-prefix=NOTLAZY -; NOTLAZY: 64 bitcode-reader - Number of Metadata records loaded +; NOTLAZY: 66 bitcode-reader - Number of Metadata records loaded ; NOTLAZY: 7 bitcode-reader - Number of MDStrings loaded Index: llvm/test/Transforms/InterleaveVTables/basic.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/InterleaveVTables/basic.ll @@ -0,0 +1,59 @@ +; RUN: opt -S -interleavevtables < %s | FileCheck %s + +target datalayout = "e-p:64:64" + +; Tests that this set of globals is interleaved according to our interleaving algorithm. +; (see interleaveGlobalVariables in lib/Transforms/IPO/InterleaveVTables.cpp). + +; CHECK: [[G:@[^ ]*]] = private constant [12 x i8*] [i8* null, i8* inttoptr (i64 1 to i8*), i8* inttoptr (i64 4 to i8*), i8* inttoptr (i64 5 to i8*), i8* inttoptr (i64 8 to i8*), i8* inttoptr (i64 9 to i8*), i8* inttoptr (i64 2 to i8*), i8* inttoptr (i64 3 to i8*), i8* inttoptr (i64 6 to i8*), i8* inttoptr (i64 7 to i8*), i8* inttoptr (i64 10 to i8*), i8* inttoptr (i64 11 to i8*)] +@a = constant [4 x i64] [i64 0, i64 1, i64 2, i64 3], !type !0 +@b = constant [4 x i64] [i64 4, i64 5, i64 6, i64 7], !type !0, !type !1 +@c = constant [4 x i64] [i64 8, i64 9, i64 10, i64 11], !type !0, !type !2 + +; CHECK-NOT: @__typeid{{[1-3]+}}${{0|1}} = + +@__typeid1$0 = constant i64 0, !offset.type !3 +@__typeid1$1 = constant i64 1, !offset.type !3 +@__typeid2$0 = constant i64 0, !offset.type !4 +@__typeid2$1 = constant i64 1, !offset.type !4 +@__typeid3$0 = constant i64 0, !offset.type !5 +@__typeid3$1 = constant i64 1, !offset.type !5 + +!0 = !{i64 16, !"typeid1"} +!1 = !{i64 16, !"typeid2"} +!2 = !{i64 16, !"typeid3"} + +!3 = !{!"typeid1"} +!4 = !{!"typeid2"} +!5 = !{!"typeid3"} + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +; CHECK: @foo1(i8* [[A0:%[^ ]*]]) +define i1 @foo1(i8* %p) { + ; CHECK: [[R0:%[^ ]*]] = ptrtoint i8* [[A0]] to i64 + ; CHECK: [[R1:%[^ ]*]] = icmp eq i64 [[R0]], ptrtoint (i8** getelementptr inbounds ([12 x i8*], [12 x i8*]* [[G]], i32 0, i32 4) to i64) + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid2") + ; CHECK: ret i1 [[R1]] + ret i1 %x +} + +; CHECK: @foo2(i8* [[B0:%[^ ]*]]) +define i1 @foo2(i8* %p) { + ; CHECK: [[S0:%[^ ]*]] = ptrtoint i8* [[B0]] to i64 + ; CHECK: [[S1:%[^ ]*]] = icmp eq i64 [[S0]], ptrtoint (i8** getelementptr inbounds ([12 x i8*], [12 x i8*]* [[G]], i32 0, i32 6) to i64) + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid3") + ; CHECK: ret i1 [[S1]] + ret i1 %x +} + +; CHECK: @foo3(i8* [[C0:%[^ ]*]]) +define i1 @foo3(i8* %p) { + ; CHECK: [[T0:%[^ ]*]] = ptrtoint i8* [[C0]] to i64 + ; CHECK: [[T1:%[^ ]*]] = sub i64 [[T0]], ptrtoint (i8** getelementptr inbounds ([12 x i8*], [12 x i8*]* [[G]], i32 0, i32 2) to i64) + ; CHECK: [[T2:%[^ ]*]] = lshr i64 [[T1]], 4 + ; CHECK: [[T3:%[^ ]*]] = icmp ule i64 [[T2]], 2 + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1") + ; CHECK: ret i1 [[T3]] + ret i1 %x +} \ No newline at end of file Index: llvm/test/Transforms/InterleaveVTables/imcomplete.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/InterleaveVTables/imcomplete.ll @@ -0,0 +1,65 @@ +; RUN: opt -S -interleavevtables < %s | FileCheck %s + +target datalayout = "e-p:64:64" + +; Tests that this set of globals is interleaved according to our interleaving algorithm. +; (see interleaveGlobalVariables in lib/Transforms/IPO/InterleaveVTables.cpp). +; This test is similar to basic.ll but some entries in the virtual tables are not referenced. + +; The first list initilized with offset-to-top entries: [0, 4, 8] +; The second list initilized with RTTI entries: [1, 5, 9] +; Lists of entries that have to have the same distance [2, 6, 10] [7] [11] +; The first list before merging: [0, 4, 8, 2, 6, 10] +; The second list before merging: [1, 5, 9, 7, 11, 0] +; The final layout: [0, 1, 4, 5, 8, 9, 2, 7, 6, 11, 10, 0] + +; CHECK: [[G:@[^ ]*]] = private constant [12 x i8*] [i8* null, i8* inttoptr (i64 1 to i8*), i8* inttoptr (i64 4 to i8*), i8* inttoptr (i64 5 to i8*), i8* inttoptr (i64 8 to i8*), i8* inttoptr (i64 9 to i8*), i8* inttoptr (i64 2 to i8*), i8* inttoptr (i64 7 to i8*), i8* inttoptr (i64 6 to i8*), i8* inttoptr (i64 11 to i8*), i8* inttoptr (i64 10 to i8*), i8* null] +@a = constant [4 x i64] [i64 0, i64 1, i64 2, i64 3], !type !0 +@b = constant [4 x i64] [i64 4, i64 5, i64 6, i64 7], !type !0, !type !1 +@c = constant [4 x i64] [i64 8, i64 9, i64 10, i64 11], !type !0, !type !2 + +; CHECK-NOT: @__typeid{{[1-3]+}}${{0|1}} = + +@__typeid1$0 = constant i64 0, !offset.type !3 +@__typeid2$0 = constant i64 0, !offset.type !4 +@__typeid2$1 = constant i64 1, !offset.type !4 +@__typeid3$1 = constant i64 1, !offset.type !5 + +!0 = !{i64 16, !"typeid1"} +!1 = !{i64 16, !"typeid2"} +!2 = !{i64 16, !"typeid3"} + +!3 = !{!"typeid1"} +!4 = !{!"typeid2"} +!5 = !{!"typeid3"} + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +; CHECK: @foo1(i8* [[A0:%[^ ]*]]) +define i1 @foo1(i8* %p) { + ; CHECK: [[R0:%[^ ]*]] = ptrtoint i8* [[A0]] to i64 + ; CHECK: [[R1:%[^ ]*]] = icmp eq i64 [[R0]], ptrtoint (i8** getelementptr inbounds ([12 x i8*], [12 x i8*]* [[G]], i32 0, i32 4) to i64) + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid2") + ; CHECK: ret i1 [[R1]] + ret i1 %x +} + +; CHECK: @foo2(i8* [[B0:%[^ ]*]]) +define i1 @foo2(i8* %p) { + ; CHECK: [[S0:%[^ ]*]] = ptrtoint i8* [[B0]] to i64 + ; CHECK: [[S1:%[^ ]*]] = icmp eq i64 [[S0]], ptrtoint (i8** getelementptr inbounds ([12 x i8*], [12 x i8*]* [[G]], i32 0, i32 6) to i64) + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid3") + ; CHECK: ret i1 [[S1]] + ret i1 %x +} + +; CHECK: @foo3(i8* [[C0:%[^ ]*]]) +define i1 @foo3(i8* %p) { + ; CHECK: [[T0:%[^ ]*]] = ptrtoint i8* [[C0]] to i64 + ; CHECK: [[T1:%[^ ]*]] = sub i64 [[T0]], ptrtoint (i8** getelementptr inbounds ([12 x i8*], [12 x i8*]* [[G]], i32 0, i32 2) to i64) + ; CHECK: [[T2:%[^ ]*]] = lshr i64 [[T1]], 4 + ; CHECK: [[T3:%[^ ]*]] = icmp ule i64 [[T2]], 2 + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1") + ; CHECK: ret i1 [[T3]] + ret i1 %x +} Index: llvm/test/Transforms/InterleaveVTables/vbase.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/InterleaveVTables/vbase.ll @@ -0,0 +1,77 @@ +; RUN: opt -S -interleavevtables < %s | FileCheck %s + +target datalayout = "e-p:64:64" + +; Tests that this set of globals is interleaved according to our interleaving algorithm. +; (see interleaveGlobalVariables in lib/Transforms/IPO/InterleaveVTables.cpp). +; This test simulates vtables with virtual bases. + +; The first list initilized with offset-to-top entries: [0, 5, 11] +; The second list initilized with RTTI entries: [1, 6, 12] +; Lists of entries that have to have the same distance [2, 7, 13] [3, 8, 14] [4, 10] [9] +; The first list before merging: [0, 5, 11, 2, 7, 13, 4, 10] +; The second list before merging: [1, 6, 12, 3, 8, 14, 9, 0] +; The final layout: [0, 1, 5, 6, 11, 12, 2, 3, 7, 8, 13, 14, 4, 9, 10, 0] + +; CHECK: [[G:@[^ ]*]] = private constant [16 x i8*] [i8* null, i8* inttoptr (i64 1 to i8*), i8* inttoptr (i64 5 to i8*), i8* inttoptr (i64 6 to i8*), i8* inttoptr (i64 11 to i8*), i8* inttoptr (i64 12 to i8*), i8* inttoptr (i64 2 to i8*), i8* inttoptr (i64 3 to i8*), i8* inttoptr (i64 7 to i8*), i8* inttoptr (i64 8 to i8*), i8* inttoptr (i64 13 to i8*), i8* inttoptr (i64 14 to i8*), i8* inttoptr (i64 4 to i8*), i8* inttoptr (i64 9 to i8*), i8* inttoptr (i64 10 to i8*), i8* null] + +@a = constant [4 x i64] [i64 0, i64 1, i64 2, i64 3], !type !0 +@b = constant [5 x i64] [i64 4, i64 5, i64 6, i64 7, i64 8], !type !1, !type !2 +@c = constant [6 x i64] [i64 9, i64 10, i64 11, i64 12, i64 13, i64 14], !type !3, !type !4, !type !5 + +; CHECK-NOT: @__typeid{{[1-3]+}}$ + +@__typeid2$-3 = constant i64 -3, !offset.type !7 +@__typeid3$-3 = constant i64 -3, !offset.type !8 +@__typeid3$-4 = constant i64 -4, !offset.type !8 + +@__typeid1$0 = constant i64 0, !offset.type !6 +@__typeid1$1 = constant i64 1, !offset.type !6 +@__typeid2$0 = constant i64 0, !offset.type !7 +@__typeid2$1 = constant i64 1, !offset.type !7 +@__typeid3$0 = constant i64 0, !offset.type !8 +@__typeid3$1 = constant i64 1, !offset.type !8 + +!0 = !{i64 16, !"typeid1"} +!1 = !{i64 24, !"typeid1"} +!2 = !{i64 24, !"typeid2"} +!3 = !{i64 32, !"typeid1"} +!4 = !{i64 32, !"typeid2"} +!5 = !{i64 32, !"typeid3"} + +!6 = !{!"typeid1"} +!7 = !{!"typeid2"} +!8 = !{!"typeid3"} + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +; CHECK: @foo1(i8* [[A0:%[^ ]*]]) +define i1 @foo1(i8* %p) { + ; CHECK: [[R0:%[^ ]*]] = ptrtoint i8* [[A0]] to i64 + ; CHECK: [[R1:%[^ ]*]] = icmp eq i64 [[R0]], ptrtoint (i8** getelementptr inbounds ([16 x i8*], [16 x i8*]* [[G]], i32 0, i32 6) to i64) + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid3") + ; CHECK: ret i1 [[R1]] + ret i1 %x +} + +; CHECK: @foo2(i8* [[B0:%[^ ]*]]) +define i1 @foo2(i8* %p) { + ; CHECK: [[S0:%[^ ]*]] = ptrtoint i8* [[B0]] to i64 + ; CHECK: [[S1:%[^ ]*]] = sub i64 [[S0]], ptrtoint (i8** getelementptr inbounds ([16 x i8*], [16 x i8*]* [[G]], i32 0, i32 4) to i64) + ; CHECK: [[S2:%[^ ]*]] = lshr i64 [[S1]], 4 + ; CHECK: [[S3:%[^ ]*]] = icmp ule i64 [[S2]], 1 + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid2") + ; CHECK: ret i1 [[S3]] + ret i1 %x +} + +; CHECK: @foo3(i8* [[C0:%[^ ]*]]) +define i1 @foo3(i8* %p) { + ; CHECK: [[T0:%[^ ]*]] = ptrtoint i8* [[C0]] to i64 + ; CHECK: [[T1:%[^ ]*]] = sub i64 [[T0]], ptrtoint (i8** getelementptr inbounds ([16 x i8*], [16 x i8*]* [[G]], i32 0, i32 2) to i64) + ; CHECK: [[T2:%[^ ]*]] = lshr i64 [[T1]], 4 + ; CHECK: [[T3:%[^ ]*]] = icmp ule i64 [[T2]], 2 + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1") + ; CHECK: ret i1 [[T3]] + ret i1 %x +}