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.type.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,31 @@ +//===- 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 pass create a interleaved layout of vtables and lower calls to +// llvm.type.test to appropriate range checks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_INTERLEAVEVTABLES_H +#define LLVM_TRANSFORMS_IPO_INTERLEAVEVTABLES_H + +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class Module; + +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 @@ -36,31 +36,32 @@ // Create the fixed metadata kinds. This is done in the same order as the // MD_* enum values so that they correspond. std::pair MDKinds[] = { - {MD_dbg, "dbg"}, - {MD_tbaa, "tbaa"}, - {MD_prof, "prof"}, - {MD_fpmath, "fpmath"}, - {MD_range, "range"}, - {MD_tbaa_struct, "tbaa.struct"}, - {MD_invariant_load, "invariant.load"}, - {MD_alias_scope, "alias.scope"}, - {MD_noalias, "noalias"}, - {MD_nontemporal, "nontemporal"}, - {MD_mem_parallel_loop_access, "llvm.mem.parallel_loop_access"}, - {MD_nonnull, "nonnull"}, - {MD_dereferenceable, "dereferenceable"}, - {MD_dereferenceable_or_null, "dereferenceable_or_null"}, - {MD_make_implicit, "make.implicit"}, - {MD_unpredictable, "unpredictable"}, - {MD_invariant_group, "invariant.group"}, - {MD_align, "align"}, - {MD_loop, "llvm.loop"}, - {MD_type, "type"}, - {MD_section_prefix, "section_prefix"}, - {MD_absolute_symbol, "absolute_symbol"}, - {MD_associated, "associated"}, - {MD_callees, "callees"}, - {MD_irr_loop, "irr_loop"}, + {MD_dbg, "dbg"}, + {MD_tbaa, "tbaa"}, + {MD_prof, "prof"}, + {MD_fpmath, "fpmath"}, + {MD_range, "range"}, + {MD_tbaa_struct, "tbaa.struct"}, + {MD_invariant_load, "invariant.load"}, + {MD_alias_scope, "alias.scope"}, + {MD_noalias, "noalias"}, + {MD_nontemporal, "nontemporal"}, + {MD_mem_parallel_loop_access, "llvm.mem.parallel_loop_access"}, + {MD_nonnull, "nonnull"}, + {MD_dereferenceable, "dereferenceable"}, + {MD_dereferenceable_or_null, "dereferenceable_or_null"}, + {MD_make_implicit, "make.implicit"}, + {MD_unpredictable, "unpredictable"}, + {MD_invariant_group, "invariant.group"}, + {MD_align, "align"}, + {MD_loop, "llvm.loop"}, + {MD_type, "type"}, + {MD_section_prefix, "section_prefix"}, + {MD_absolute_symbol, "absolute_symbol"}, + {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,885 @@ +//===- 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/MapVector.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 + SetVector 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 ByteOffset; + GlobalVariable *Global; +}; + +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()); + ArrayType *OffsetGVTy = ArrayType::get(Int32Ty, 0); + 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 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 addType(Metadata *TypdId, ArrayRef Globals, + std::map &TypeMap); + void buildHierarchy( + std::vector>> + &TypeGlobals); + void + handleDisjointSet(ArrayRef 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) + +ModulePass *llvm::createInterleaveVTablesPass() { + return new InterleaveVTables; +} + +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 &TypeIdAndUserInfo : TypeIdUsers) { + Metadata *TypeId = TypeIdAndUserInfo.first; + TypeIdUserInfo &TIUI = TypeIdAndUserInfo.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(); + 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; + + // Initialize UpperEntries 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 EntryGroup &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; + int64_t NewOffsetInBytes = NewOffset * EntrySize; + OffsetGlobal->replaceAllUsesWith( + ConstantExpr::getIntToPtr(ConstantInt::get(IntPtrTy, NewOffsetInBytes), + PointerType::get(OffsetGVTy, 0))); + 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.ByteOffset / EntrySize; + assert(Offset != -1 && Offset != -2 && + "There should not be any offset global variables for offset-to-top " + "or RTTI"); + 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 vectors + 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. +#ifdef ENABLE_EXPENSIVE_CHECKS + for (const auto &GV : OrderedGlobals) { + Constant *Array = GV->getInitializer(); + bool IsDataArray = false; + if (ConstantDataArray *CDA = dyn_cast(Array)) + IsDataArray = true; + int64_t Size = IsDataArray + ? dyn_cast(Array)->getNumElements() + : dyn_cast(Array)->getNumOperands(); + for (int64_t I = 0; I < Size; ++I) { + if (OldToNewOffsets[GV].find(I - (int64_t)AddressPointIndices[GV]) == + OldToNewOffsets[GV].end()) + continue; + int64_t OldOffsetFromAddrPt = I - (int64_t)AddressPointIndices[GV]; + int64_t NewOffsetFromAddrPt = OldToNewOffsets[GV][OldOffsetFromAddrPt]; + uint64_t NewOffsetFromBeginning = + (uint64_t)(NewOffsetFromAddrPt + AddrPoints[GV]); + if (Array->getAggregateElement(I) == + InterleavedEntries[NewOffsetFromBeginning]) + continue; + + 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."); + } + } +#endif + + // Make sure that each element in InterleavedEntries is of type Int8Ptr + for (auto &Elem : InterleavedEntries) + if (Elem->getType() != Int8PtrTy) { + if (Elem->getType()->isPointerTy()) + Elem = ConstantExpr::getBitCast(Elem, Int8PtrTy); + else + 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. Note that the + // front-end calculates the address point of a vtable by adding the offset + // between the start of the vtable and the address point in the original + // layout to the start of the vtable. To ensure this calculation still works, + // we replace each reference to a vtable with the address of the new address + // point minus the the offset between the start of the vtable and the address + // point in the original layout. + + // The first address point in the interleaved layout always starts at offset + // 2, and the beginnings of two adjacent address points are off by two. + int32_t StartOffset = 2; + for (auto GV : OrderedGlobals) { + + Constant *CombinedGlobalIdxs[] = { + ConstantInt::get(Int32Ty, 0), + ConstantInt::get(Int32Ty, StartOffset - AddressPointIndices[GV])}; + 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. +/// +/// OrderedGlobals: 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) { + TypeInterleavingInfo &TII = InterleavingInfoMap[BaseType]; + + // Set the start index of the vtable in the list for the type. + TII.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. + OrderedGlobals.insert(OrderedGlobals.end(), TII.ExclusiveVTables.begin(), + TII.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. + for (size_t I = 0; I < TII.Offsets.size(); I++) { + int64_t Offset = TII.Offsets[I]; + GlobalVariable *GV = TII.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 : TII.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. + TII.EndIndex = OrderedGlobals.size(); +} + +/// Add a type and the set of compatible vtables to the type hierarchy. It +/// is assumed that this function is called with types of increasing size of +/// compatible vtable sets. +void InterleaveVTablesModule::addType( + Metadata *TypdId, ArrayRef Globals, + std::map &TypeMap) { + + TypeInterleavingInfo &TII = InterleavingInfoMap[TypdId]; + for (auto GV : Globals) { + // If we haven't seen this vtable, it means that it is exclusive to this + // type. + if (TypeMap.find(GV) == TypeMap.end()) + TII.ExclusiveVTables.push_back(GV); + // If we have seen this vtable, the last seen type of this vtable is a child + // of the current type. + else + TII.ChildrenTypes.insert(TypeMap[GV]); + TypeMap[GV] = TypdId; + } +} + +/// Given the list of sorted types and corresponding compatible vtables in the +/// order of increasing size of compatible set, build the type hierarchy. Since +/// vtables have been split, this function does a depth-first traversal in the +/// type hierarchy and builds it from bottom up. +void InterleaveVTablesModule::buildHierarchy( + std::vector>> + &TypeGlobals) { + // Map from a vtable to the last seen type that this vtable is compatible + // with. + std::map TypeMap; + + for (auto &TypeAndGlobals : TypeGlobals) { + Metadata *TypeId = TypeAndGlobals.first; + std::vector &Globals = TypeAndGlobals.second; + addType(TypeId, Globals, TypeMap); + } +} + +void InterleaveVTablesModule::handleDisjointSet( + ArrayRef TypeIds, ArrayRef Globals, + DenseMap &AddressPointIndices) { + // For each type identifier, build a set of vtables that refer to members of + // the type identifier. + MapVector> TypeMembersMap; + + for (auto TypeId : TypeIds) + TypeMembersMap.insert( + std::make_pair(TypeId, std::vector{})); + + for (GlobalTypeMember *GTM : Globals) { + for (MDNode *Type : GTM->types()) { + // Type = { offset, type identifier } + Metadata *TypeId = Type->getOperand(1); + // We only care about type id's that appear in TypeIds + if (TypeMembersMap.find(TypeId) != TypeMembersMap.end()) + TypeMembersMap[TypeId].push_back(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(); + }); + + // Build the type hierarchy. + buildHierarchy(TypeMembersVector); + + // 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. + std::stable_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; + return LeftSize > RightSize; + }); + + // 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() != 2) + report_fatal_error( + "All operands of offset.type metadata must have 2 elements"); + // offset.type metadata has the format {type id, offset} + TypeInterleavingInfo &TII = InterleavingInfoMap[Type->getOperand(0)]; + const ConstantInt *CI = + mdconst::dyn_extract(Type->getOperand(1)); + if (!CI) + report_fatal_error( + "The second operand of offset.type metadata must be an integer"); + int64_t Offset = CI->getSExtValue(); + 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; + }); + + // Interleave virtual tables and lower calls to llvm.type.test. + handleDisjointSet(TypeIds, 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,83 @@ +; 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*)] + +; CHECK: @a = alias i8*, getelementptr inbounds ([12 x i8*], [12 x i8*]* @interleavedvtable, i32 0, i32 0) +; CHECK: @b = alias i8*, getelementptr inbounds ([12 x i8*], [12 x i8*]* @interleavedvtable, i32 0, i32 2) +; CHECK: @c = alias i8*, getelementptr inbounds ([12 x i8*], [12 x i8*]* @interleavedvtable, i32 0, i32 4) +@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]+}}$ + +@__typeid1$0 = global [0 x i32] zeroinitializer, !offset.type !3 +@__typeid1$8 = global [0 x i32] zeroinitializer, !offset.type !4 +@__typeid2$0 = global [0 x i32] zeroinitializer, !offset.type !5 +@__typeid2$8 = global [0 x i32] zeroinitializer, !offset.type !6 +@__typeid3$0 = global [0 x i32] zeroinitializer, !offset.type !7 +@__typeid3$8 = global [0 x i32] zeroinitializer, !offset.type !8 + +!0 = !{i64 16, !"typeid1"} +!1 = !{i64 16, !"typeid2"} +!2 = !{i64 16, !"typeid3"} + +!3 = !{!"typeid1", i64 0} +!4 = !{!"typeid1", i64 8} +!5 = !{!"typeid2", i64 0} +!6 = !{!"typeid2", i64 8} +!7 = !{!"typeid3", i64 0} +!8 = !{!"typeid3", i64 8} + +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 +} + +; CHECK: @foo4() +define void @foo4() { + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 32 to [0 x i32]*) to i64 + %x0 = ptrtoint [0 x i32]* @__typeid1$0 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 40 to [0 x i32]*) to i64 + %x1 = ptrtoint [0 x i32]* @__typeid1$8 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 32 to [0 x i32]*) to i64 + %x2 = ptrtoint [0 x i32]* @__typeid2$0 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 40 to [0 x i32]*) to i64 + %x3 = ptrtoint [0 x i32]* @__typeid2$8 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 32 to [0 x i32]*) to i64 + %x4 = ptrtoint [0 x i32]* @__typeid3$0 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 40 to [0 x i32]*) to i64 + %x5 = ptrtoint [0 x i32]* @__typeid3$8 to i64 + ret void +} \ No newline at end of file Index: llvm/test/Transforms/InterleaveVTables/incomplete.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/InterleaveVTables/incomplete.ll @@ -0,0 +1,83 @@ +; 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 initialized with offset-to-top entries: [0, 4, 8] +; The second list initialized 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] + +; CHECK: @a = alias i8*, getelementptr inbounds ([12 x i8*], [12 x i8*]* @interleavedvtable, i32 0, i32 0) +; CHECK: @b = alias i8*, getelementptr inbounds ([12 x i8*], [12 x i8*]* @interleavedvtable, i32 0, i32 2) +; CHECK: @c = alias i8*, getelementptr inbounds ([12 x i8*], [12 x i8*]* @interleavedvtable, i32 0, i32 4) +@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]+}}$ + +@__typeid1$0 = global [0 x i32] zeroinitializer, !offset.type !3 +@__typeid2$0 = global [0 x i32] zeroinitializer, !offset.type !4 +@__typeid2$8 = global [0 x i32] zeroinitializer, !offset.type !5 +@__typeid3$8 = global [0 x i32] zeroinitializer, !offset.type !6 + +!0 = !{i64 16, !"typeid1"} +!1 = !{i64 16, !"typeid2"} +!2 = !{i64 16, !"typeid3"} + +!3 = !{!"typeid1", i64 0} +!4 = !{!"typeid2", i64 0} +!5 = !{!"typeid2", i64 8} +!6 = !{!"typeid3", i64 8} + +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 +} + +; CHECK: @foo4() +define void @foo4() { + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 32 to [0 x i32]*) to i64 + %x0 = ptrtoint [0 x i32]* @__typeid1$0 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 32 to [0 x i32]*) to i64 + %x1 = ptrtoint [0 x i32]* @__typeid2$0 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 24 to [0 x i32]*) to i64 + %x2 = ptrtoint [0 x i32]* @__typeid2$8 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 24 to [0 x i32]*) to i64 + %x3 = ptrtoint [0 x i32]* @__typeid3$8 to i64 + ret void +} \ No newline at end of file Index: llvm/test/Transforms/InterleaveVTables/vbase.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/InterleaveVTables/vbase.ll @@ -0,0 +1,113 @@ +; 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 initialized with offset-to-top entries: [0, 5, 11] +; The second list initialized 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] + +; CHECK: @a = alias i8*, getelementptr inbounds ([16 x i8*], [16 x i8*]* @interleavedvtable, i32 0, i32 0) +; CHECK: @b = alias i8*, getelementptr inbounds ([16 x i8*], [16 x i8*]* @interleavedvtable, i32 0, i32 1) +; CHECK: @c = alias i8*, getelementptr inbounds ([16 x i8*], [16 x i8*]* @interleavedvtable, i32 0, i32 2) +@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$-24 = global [0 x i32] zeroinitializer, !offset.type !6 +@__typeid3$-24 = global [0 x i32] zeroinitializer, !offset.type !7 +@__typeid3$-32 = global [0 x i32] zeroinitializer, !offset.type !8 + +@__typeid1$0 = global [0 x i32] zeroinitializer, !offset.type !9 +@__typeid1$8 = global [0 x i32] zeroinitializer, !offset.type !10 +@__typeid2$0 = global [0 x i32] zeroinitializer, !offset.type !11 +@__typeid2$8 = global [0 x i32] zeroinitializer, !offset.type !12 +@__typeid3$0 = global [0 x i32] zeroinitializer, !offset.type !13 +@__typeid3$8 = global [0 x i32] zeroinitializer, !offset.type !14 + +!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 = !{!"typeid2", i64 -24} +!7 = !{!"typeid3", i64 -24} +!8 = !{!"typeid3", i64 -32} + +!9 = !{!"typeid1", i64 0} +!10 = !{!"typeid1", i64 8} +!11 = !{!"typeid2", i64 0} +!12 = !{!"typeid2", i64 8} +!13 = !{!"typeid3", i64 0} +!14 = !{!"typeid3", i64 8} + +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 +} + +; CHECK: @foo4() +define void @foo4() { + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 64 to [0 x i32]*) to i64 + %x0 = ptrtoint [0 x i32]* @__typeid2$-24 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 64 to [0 x i32]*) to i64 + %x1 = ptrtoint [0 x i32]* @__typeid3$-24 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 56 to [0 x i32]*) to i64 + %x2 = ptrtoint [0 x i32]* @__typeid3$-32 to i64 + + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 32 to [0 x i32]*) to i64 + %x3 = ptrtoint [0 x i32]* @__typeid1$0 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 32 to [0 x i32]*) to i64 + %x4 = ptrtoint [0 x i32]* @__typeid2$0 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 32 to [0 x i32]*) to i64 + %x5 = ptrtoint [0 x i32]* @__typeid3$0 to i64 + + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 40 to [0 x i32]*) to i64 + %x6 = ptrtoint [0 x i32]* @__typeid1$8 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 40 to [0 x i32]*) to i64 + %x7 = ptrtoint [0 x i32]* @__typeid2$8 to i64 + ; CHECK-NEXT: ptrtoint [0 x i32]* inttoptr (i64 40 to [0 x i32]*) to i64 + %x8 = ptrtoint [0 x i32]* @__typeid3$8 to i64 + + ret void +} \ No newline at end of file