Index: include/llvm/Bitcode/LLVMBitCodes.h =================================================================== --- include/llvm/Bitcode/LLVMBitCodes.h +++ include/llvm/Bitcode/LLVMBitCodes.h @@ -263,10 +263,25 @@ // Index-wide flags FS_FLAGS = 20, // Maps type identifier to summary information for that type identifier. + // Produced by the thin link (only lives in combined index). // TYPE_ID: [typeid, kind, bitwidth, align, size, bitmask, inlinebits, // n x (typeid, kind, name, numrba, // numrba x (numarg, numarg x arg, kind, info, byte, bit))] FS_TYPE_ID = 21, + // Maps type identifier to summary information for that type identifier + // computed from type metadata: the valueid of each vtable definition + // decorated with a type metadata for that identifier, and the offset from + // the corresponding type metadata. + // Exists in the per-module summary to provide information to thin link + // for index-based whole program devirtualization. + // TYPE_ID_METADATA: [typeid, n x (valueid, offset)] + FS_TYPE_ID_METADATA = 22, + // Summarizes vtable definition for use in index-based whole program + // devirtualization during the thin link. + // PERMODULE_VTABLE_GLOBALVAR_INIT_REFS: [valueid, flags, varflags, + // numrefs, numrefs x valueid, + // n x (valueid, offset)] + FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS = 23, }; enum MetadataCodes { Index: include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- include/llvm/IR/ModuleSummaryIndex.h +++ include/llvm/IR/ModuleSummaryIndex.h @@ -665,6 +665,12 @@ } }; +/// Pair of function ValueInfo and offset within a vtable definition +/// initializer array. +using VirtFuncOffsetPair = std::pair; +/// List of functions referenced by a particular vtable definition. +using VTableFuncList = std::vector; + /// Global variable summary information to aid decisions and /// implementation of importing. /// @@ -672,6 +678,11 @@ /// modified during the program run or not. This affects ThinLTO /// internalization class GlobalVarSummary : public GlobalValueSummary { +private: + /// For vtable definitions this holds the list of functions and + /// their corresponding offsets within the initializer array. + std::unique_ptr VTableFuncs; + public: struct GVarFlags { GVarFlags(bool ReadOnly = false) : ReadOnly(ReadOnly) {} @@ -692,6 +703,17 @@ GVarFlags varflags() const { return VarFlags; } void setReadOnly(bool RO) { VarFlags.ReadOnly = RO; } bool isReadOnly() const { return VarFlags.ReadOnly; } + + void setVTableFuncs(VTableFuncList Funcs) { + assert(!VTableFuncs); + VTableFuncs = llvm::make_unique(std::move(Funcs)); + } + + ArrayRef vTableFuncs() const { + if (VTableFuncs) + return *VTableFuncs; + return {}; + } }; struct TypeTestResolution { @@ -790,6 +812,14 @@ using TypeIdSummaryMapTy = std::multimap>; +/// Holds information about vtable definitions decorated with type metadata: +/// the vtable definition value and its offset in the corresponding type +/// metadata. +using TypeIdOffsetGVPair = std::pair; +/// List of vtable definitions decorated by the same type id metadata, +/// and their corresponding offsets in the type id metadata. +using TypeIdGVInfo = std::vector; + /// Class to hold module path string table and global value map, /// and encapsulate methods for operating on them. class ModuleSummaryIndex { @@ -802,9 +832,14 @@ ModulePathStringTableTy ModulePathStringTable; /// Mapping from type identifier GUIDs to type identifier and its summary - /// information. + /// information. Produced by thin link. TypeIdSummaryMapTy TypeIdMap; + /// Mapping from type identifier to information about vtables decorated + /// with that type identifier's metadata. Produced by per module summary + /// analysis and consumed by thin link. + std::map TypeIdMetadataMap; + /// Mapping from original ID to GUID. If original ID can map to multiple /// GUIDs, it will be mapped to 0. std::map OidGuidMap; @@ -1162,6 +1197,27 @@ return nullptr; } + const std::map &typeIdMetadataMap() const { + return TypeIdMetadataMap; + } + + /// Return an existing or new TypeIdMetadataMap entry for \p TypeId. + /// This accessor can mutate the map and therefore should not be used in + /// the ThinLTO backends. + TypeIdGVInfo &getOrInsertTypeIdMetadataSummary(StringRef TypeId) { + return TypeIdMetadataMap[TypeId]; + } + + /// For the given \p TypeId, this returns either a pointer to the + /// TypeIdMetadataMap entry (if present in the summary map) or null + /// (if not present). This may be used when importing. + const TypeIdGVInfo *getTypeIdMetadataSummary(StringRef TypeId) const { + auto I = TypeIdMetadataMap.find(TypeId); + if (I == TypeIdMetadataMap.end()) + return nullptr; + return &I->second; + } + /// Collect for the given module the list of functions it defines /// (GUID -> Summary). void collectDefinedFunctionsForModule(StringRef ModulePath, Index: lib/Analysis/ModuleSummaryAnalysis.cpp =================================================================== --- lib/Analysis/ModuleSummaryAnalysis.cpp +++ lib/Analysis/ModuleSummaryAnalysis.cpp @@ -405,9 +405,98 @@ Index.addGlobalValueSummary(F, std::move(FuncSummary)); } -static void -computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V, - DenseSet &CantBePromoted) { +/// Find function pointers referenced within the given vtable initializer +/// (or subset of an initializer) \p I. The starting offset of \p I within +/// the vtable initializer is \p StartingOffset. Any discovered function +/// pointers are added to \p VTableFuncs along with their cumulative offset +/// within the initializer. +static void findFuncPointers(const Constant *I, uint64_t StartingOffset, + const Module &M, ModuleSummaryIndex &Index, + VTableFuncList &VTableFuncs) { + // First check if this is a function pointer. + if (I->getType()->isPointerTy()) { + auto Fn = dyn_cast(I->stripPointerCasts()); + // We can disregard __cxa_pure_virtual as a possible call target, as + // calls to pure virtuals are UB. + if (Fn && Fn->getName() != "__cxa_pure_virtual") + VTableFuncs.push_back( + std::make_pair(Index.getOrInsertValueInfo(Fn), StartingOffset)); + return; + } + + // Walk through the elements in the constant struct or array and recursively + // look for virtual function pointers. + const DataLayout &DL = M.getDataLayout(); + if (auto *C = dyn_cast(I)) { + StructType *STy = dyn_cast(C->getType()); + assert(STy); + const StructLayout *SL = DL.getStructLayout(C->getType()); + + for (StructType::element_iterator EB = STy->element_begin(), EI = EB, + EE = STy->element_end(); + EI != EE; ++EI) { + auto Offset = SL->getElementOffset(EI - EB); + unsigned Op = SL->getElementContainingOffset(Offset); + findFuncPointers(cast(I->getOperand(Op)), + StartingOffset + Offset, M, Index, VTableFuncs); + } + } else if (auto *C = dyn_cast(I)) { + ArrayType *ATy = C->getType(); + Type *EltTy = ATy->getElementType(); + uint64_t EltSize = DL.getTypeAllocSize(EltTy); + for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) { + findFuncPointers(cast(I->getOperand(i)), + StartingOffset + i * EltSize, M, Index, VTableFuncs); + } + } +} + +// Identify the function pointers referenced by vtable definition \p V. +static void computeVTableFuncs(ModuleSummaryIndex &Index, + const GlobalVariable &V, const Module &M, + VTableFuncList &VTableFuncs) { + if (!V.isConstant()) + return; + + findFuncPointers(V.getInitializer(), /*StartingOffset=*/0, M, Index, + VTableFuncs); + +#ifndef NDEBUG + // Validate that the VTableFuncs list is ordered by offset. + uint64_t PrevOffset = 0; + for (auto &P : VTableFuncs) { + // The findVFuncPointers traversal should have encountered the + // functions in offset order. We need to use ">=" since PrevOffset + // starts at 0. + assert(P.second >= PrevOffset); + PrevOffset = P.second; + } +#endif +} + +/// Record vtable definition \p V for each type metadata it references. +static void recordTypeIdMetadataReferences(ModuleSummaryIndex &Index, + const GlobalVariable &V, + SmallVectorImpl &Types) { + for (MDNode *Type : Types) { + auto TypeID = Type->getOperand(1).get(); + + uint64_t Offset = + cast( + cast(Type->getOperand(0))->getValue()) + ->getZExtValue(); + + if (auto *TypeId = dyn_cast(TypeID)) + Index.getOrInsertTypeIdMetadataSummary(TypeId->getString()) + .push_back({Offset, Index.getOrInsertValueInfo(&V)}); + } +} + +static void computeVariableSummary(ModuleSummaryIndex &Index, + const GlobalVariable &V, + DenseSet &CantBePromoted, + const Module &M, + SmallVectorImpl &Types) { SetVector RefEdges; SmallPtrSet Visited; bool HasBlockAddress = findRefEdges(Index, &V, RefEdges, Visited); @@ -415,6 +504,21 @@ GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal, /* Live = */ false, V.isDSOLocal()); + VTableFuncList VTableFuncs; + // If splitting is not enabled, then we compute the summary information + // necessary for index-based whole program devirtualization. + if (!Index.enableSplitLTOUnit()) { + Types.clear(); + V.getMetadata(LLVMContext::MD_type, Types); + if (!Types.empty()) { + // Identify the function pointers referenced by this vtable definition. + computeVTableFuncs(Index, V, M, VTableFuncs); + + // Record this vtable definition for each type metadata it references. + recordTypeIdMetadataReferences(Index, V, Types); + } + } + // Don't mark variables we won't be able to internalize as read-only. GlobalVarSummary::GVarFlags VarFlags( !V.hasComdat() && !V.hasAppendingLinkage() && !V.isInterposable() && @@ -425,6 +529,8 @@ CantBePromoted.insert(V.getGUID()); if (HasBlockAddress) GVarSummary->setNotEligibleToImport(); + if (!VTableFuncs.empty()) + GVarSummary->setVTableFuncs(VTableFuncs); Index.addGlobalValueSummary(V, std::move(GVarSummary)); } @@ -567,10 +673,11 @@ // Compute summaries for all variables defined in module, and save in the // index. + SmallVector Types; for (const GlobalVariable &G : M.globals()) { if (G.isDeclaration()) continue; - computeVariableSummary(Index, G, CantBePromoted); + computeVariableSummary(Index, G, CantBePromoted, M, Types); } // Compute summaries for all aliases defined in module, and save in the Index: lib/AsmParser/LLLexer.cpp =================================================================== --- lib/AsmParser/LLLexer.cpp +++ lib/AsmParser/LLLexer.cpp @@ -748,6 +748,8 @@ KEYWORD(critical); KEYWORD(relbf); KEYWORD(variable); + KEYWORD(vTableFuncs); + KEYWORD(virtFunc); KEYWORD(aliasee); KEYWORD(refs); KEYWORD(typeIdInfo); @@ -760,6 +762,7 @@ KEYWORD(offset); KEYWORD(args); KEYWORD(typeid); + KEYWORD(typeidMetadata); KEYWORD(summary); KEYWORD(typeTestRes); KEYWORD(kind); Index: lib/AsmParser/LLParser.h =================================================================== --- lib/AsmParser/LLParser.h +++ lib/AsmParser/LLParser.h @@ -368,9 +368,11 @@ IdToIndexMapType &IdToIndexMap, unsigned Index); bool ParseVFuncId(FunctionSummary::VFuncId &VFuncId, IdToIndexMapType &IdToIndexMap, unsigned Index); + bool ParseOptionalVTableFuncs(VTableFuncList &VTableFuncs); bool ParseOptionalRefs(std::vector &Refs); bool ParseTypeIdEntry(unsigned ID); bool ParseTypeIdSummary(TypeIdSummary &TIS); + bool ParseTypeIdMetadataEntry(unsigned ID); bool ParseTypeTestResolution(TypeTestResolution &TTRes); bool ParseOptionalWpdResolutions( std::map &WPDResMap); Index: lib/AsmParser/LLParser.cpp =================================================================== --- lib/AsmParser/LLParser.cpp +++ lib/AsmParser/LLParser.cpp @@ -821,6 +821,9 @@ case lltok::kw_typeid: return ParseTypeIdEntry(SummaryID); break; + case lltok::kw_typeidMetadata: + return ParseTypeIdMetadataEntry(SummaryID); + break; default: return Error(Lex.getLoc(), "unexpected summary kind"); } @@ -7256,6 +7259,90 @@ return false; } +static ValueInfo EmptyVI = + ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8); + +/// TypeIdMetadataEntry +/// ::= 'typeidMetadata' ':' '(' 'name' ':' STRINGCONSTANT ',' TypeIdGVInfo +/// ')' +bool LLParser::ParseTypeIdMetadataEntry(unsigned ID) { + assert(Lex.getKind() == lltok::kw_typeidMetadata); + Lex.Lex(); + + std::string Name; + if (ParseToken(lltok::colon, "expected ':' here") || + ParseToken(lltok::lparen, "expected '(' here") || + ParseToken(lltok::kw_name, "expected 'name' here") || + ParseToken(lltok::colon, "expected ':' here") || + ParseStringConstant(Name)) + return true; + + TypeIdGVInfo &TI = Index->getOrInsertTypeIdMetadataSummary(Name); + if (ParseToken(lltok::comma, "expected ',' here") || + ParseToken(lltok::kw_summary, "expected 'summary' here") || + ParseToken(lltok::colon, "expected ':' here") || + ParseToken(lltok::lparen, "expected '(' here")) + return true; + + IdToIndexMapType IdToIndexMap; + // Parse each call edge + do { + uint64_t Offset; + if (ParseToken(lltok::lparen, "expected '(' here") || + ParseToken(lltok::kw_offset, "expected 'offset' here") || + ParseToken(lltok::colon, "expected ':' here") || ParseUInt64(Offset) || + ParseToken(lltok::comma, "expected ',' here")) + return true; + + LocTy Loc = Lex.getLoc(); + unsigned GVId; + ValueInfo VI; + if (ParseGVReference(VI, GVId)) + return true; + + // Keep track of the TypeIdGVInfo array index needing a forward reference. + // We will save the location of the ValueInfo needing an update, but + // can only do so once the std::vector is finalized. + if (VI == EmptyVI) + IdToIndexMap[GVId].push_back(std::make_pair(TI.size(), Loc)); + TI.push_back({Offset, VI}); + + if (ParseToken(lltok::rparen, "expected ')' in call")) + return true; + } while (EatIfPresent(lltok::comma)); + + // Now that the TI vector is finalized, it is safe to save the locations + // of any forward GV references that need updating later. + for (auto I : IdToIndexMap) { + for (auto P : I.second) { + assert(TI[P.first].second == EmptyVI && + "Forward referenced ValueInfo expected to be empty"); + auto FwdRef = ForwardRefValueInfos.insert(std::make_pair( + I.first, std::vector>())); + FwdRef.first->second.push_back( + std::make_pair(&TI[P.first].second, P.second)); + } + } + + if (ParseToken(lltok::rparen, "expected ')' here") || + ParseToken(lltok::rparen, "expected ')' here")) + return true; + + // Check if this ID was forward referenced, and if so, update the + // corresponding GUIDs. + auto FwdRefTIDs = ForwardRefTypeIds.find(ID); + if (FwdRefTIDs != ForwardRefTypeIds.end()) { + for (auto TIDRef : FwdRefTIDs->second) { + assert(!*TIDRef.first && + "Forward referenced type id GUID expected to be 0"); + *TIDRef.first = GlobalValue::getGUID(Name); + } + ForwardRefTypeIds.erase(FwdRefTIDs); + } + + return false; +} + /// TypeTestResolution /// ::= 'typeTestRes' ':' '(' 'kind' ':' /// ( 'unsat' | 'byteArray' | 'inline' | 'single' | 'allOnes' ) ',' @@ -7763,6 +7850,7 @@ /*Live=*/false, /*IsLocal=*/false); GlobalVarSummary::GVarFlags GVarFlags(/*ReadOnly*/ false); std::vector Refs; + VTableFuncList VTableFuncs; if (ParseToken(lltok::colon, "expected ':' here") || ParseToken(lltok::lparen, "expected '(' here") || ParseModuleReference(ModulePath) || @@ -7771,10 +7859,20 @@ ParseGVarFlags(GVarFlags)) return true; - // Parse optional refs field - if (EatIfPresent(lltok::comma)) { - if (ParseOptionalRefs(Refs)) - return true; + // Parse optional fields + while (EatIfPresent(lltok::comma)) { + switch (Lex.getKind()) { + case lltok::kw_vTableFuncs: + if (ParseOptionalVTableFuncs(VTableFuncs)) + return true; + break; + case lltok::kw_refs: + if (ParseOptionalRefs(Refs)) + return true; + break; + default: + return Error(Lex.getLoc(), "expected optional variable summary field"); + } } if (ParseToken(lltok::rparen, "expected ')' here")) @@ -7784,6 +7882,7 @@ llvm::make_unique(GVFlags, GVarFlags, std::move(Refs)); GS->setModulePath(ModulePath); + GS->setVTableFuncs(std::move(VTableFuncs)); AddGlobalValueToIndex(Name, GUID, (GlobalValue::LinkageTypes)GVFlags.Linkage, ID, std::move(GS)); @@ -8001,6 +8100,67 @@ return false; } +/// OptionalVTableFuncs +/// := 'vTableFuncs' ':' '(' VTableFunc [',' VTableFunc]* ')' +/// VTableFunc ::= '(' 'virtFunc' ':' GVReference ',' 'offset' ':' UInt64 ')' +bool LLParser::ParseOptionalVTableFuncs(VTableFuncList &VTableFuncs) { + assert(Lex.getKind() == lltok::kw_vTableFuncs); + Lex.Lex(); + + if (ParseToken(lltok::colon, "expected ':' in vTableFuncs") | + ParseToken(lltok::lparen, "expected '(' in vTableFuncs")) + return true; + + IdToIndexMapType IdToIndexMap; + // Parse each virtual function pair + do { + ValueInfo VI; + if (ParseToken(lltok::lparen, "expected '(' in vTableFunc") || + ParseToken(lltok::kw_virtFunc, "expected 'callee' in vTableFunc") || + ParseToken(lltok::colon, "expected ':'")) + return true; + + LocTy Loc = Lex.getLoc(); + unsigned GVId; + if (ParseGVReference(VI, GVId)) + return true; + + uint64_t Offset; + if (ParseToken(lltok::comma, "expected comma") || + ParseToken(lltok::kw_offset, "expected offset") || + ParseToken(lltok::colon, "expected ':'") || ParseUInt64(Offset)) + return true; + + // Keep track of the VTableFuncs array index needing a forward reference. + // We will save the location of the ValueInfo needing an update, but + // can only do so once the std::vector is finalized. + if (VI == EmptyVI) + IdToIndexMap[GVId].push_back(std::make_pair(VTableFuncs.size(), Loc)); + VTableFuncs.push_back(std::make_pair(VI, Offset)); + + if (ParseToken(lltok::rparen, "expected ')' in vTableFunc")) + return true; + } while (EatIfPresent(lltok::comma)); + + // Now that the VTableFuncs vector is finalized, it is safe to save the + // locations of any forward GV references that need updating later. + for (auto I : IdToIndexMap) { + for (auto P : I.second) { + assert(VTableFuncs[P.first].first == EmptyVI && + "Forward referenced ValueInfo expected to be empty"); + auto FwdRef = ForwardRefValueInfos.insert(std::make_pair( + I.first, std::vector>())); + FwdRef.first->second.push_back( + std::make_pair(&VTableFuncs[P.first].first, P.second)); + } + } + + if (ParseToken(lltok::rparen, "expected ')' in vTableFuncs")) + return true; + + return false; +} + /// OptionalRefs /// := 'refs' ':' '(' GVReference [',' GVReference]* ')' bool LLParser::ParseOptionalRefs(std::vector &Refs) { Index: lib/AsmParser/LLToken.h =================================================================== --- lib/AsmParser/LLToken.h +++ lib/AsmParser/LLToken.h @@ -378,6 +378,8 @@ kw_critical, kw_relbf, kw_variable, + kw_vTableFuncs, + kw_virtFunc, kw_aliasee, kw_refs, kw_typeIdInfo, @@ -390,6 +392,7 @@ kw_offset, kw_args, kw_typeid, + kw_typeidMetadata, kw_summary, kw_typeTestRes, kw_kind, Index: lib/Bitcode/Reader/BitcodeReader.cpp =================================================================== --- lib/Bitcode/Reader/BitcodeReader.cpp +++ lib/Bitcode/Reader/BitcodeReader.cpp @@ -747,6 +747,9 @@ bool HasRelBF); Error parseEntireSummary(unsigned ID); Error parseModuleStringTable(); + void parseTypeIdMetadataSummaryRecord(ArrayRef Record); + void parseTypeIdGVInfo(ArrayRef Record, size_t &Slot, + TypeIdGVInfo &TypeId); std::pair getValueInfoFromValueId(unsigned ValueId); @@ -5223,6 +5226,24 @@ parseWholeProgramDevirtResolution(Record, Strtab, Slot, TypeId); } +void ModuleSummaryIndexBitcodeReader::parseTypeIdGVInfo( + ArrayRef Record, size_t &Slot, TypeIdGVInfo &TypeId) { + uint64_t Offset = Record[Slot++]; + ValueInfo Callee = getValueInfoFromValueId(Record[Slot++]).first; + TypeId.push_back({Offset, Callee}); +} + +void ModuleSummaryIndexBitcodeReader::parseTypeIdMetadataSummaryRecord( + ArrayRef Record) { + size_t Slot = 0; + TypeIdGVInfo &TypeId = TheIndex.getOrInsertTypeIdMetadataSummary( + {Strtab.data() + Record[Slot], static_cast(Record[Slot + 1])}); + Slot += 2; + + while (Slot < Record.size()) + parseTypeIdGVInfo(Record, Slot, TypeId); +} + static void setImmutableRefs(std::vector &Refs, unsigned Count) { // Read-only refs are in the end of the refs list. for (unsigned RefNo = Refs.size() - Count; RefNo < Refs.size(); ++RefNo) @@ -5440,6 +5461,34 @@ TheIndex.addGlobalValueSummary(GUID.first, std::move(FS)); break; } + // FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS: [valueid, flags, varflags, + // numrefs, numrefs x valueid, + // n x (valueid, offset)] + case bitc::FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS: { + unsigned ValueID = Record[0]; + uint64_t RawFlags = Record[1]; + GlobalVarSummary::GVarFlags GVF = getDecodedGVarFlags(Record[2]); + unsigned NumRefs = Record[3]; + unsigned RefListStartIndex = 4; + unsigned VTableListStartIndex = RefListStartIndex + NumRefs; + auto Flags = getDecodedGVSummaryFlags(RawFlags, Version); + std::vector Refs = makeRefList( + ArrayRef(Record).slice(RefListStartIndex, NumRefs)); + VTableFuncList VTableFuncs; + for (unsigned I = VTableListStartIndex, E = Record.size(); I != E; ++I) { + ValueInfo Callee = getValueInfoFromValueId(Record[I]).first; + uint64_t Offset = Record[++I]; + VTableFuncs.push_back({Callee, Offset}); + } + auto VS = + llvm::make_unique(Flags, GVF, std::move(Refs)); + VS->setModulePath(getThisModule()->first()); + VS->setVTableFuncs(VTableFuncs); + auto GUID = getValueInfoFromValueId(ValueID); + VS->setOriginalName(GUID.second); + TheIndex.addGlobalValueSummary(GUID.first, std::move(VS)); + break; + } // FS_COMBINED: [valueid, modid, flags, instcount, fflags, numrefs, // numrefs x valueid, n x (valueid)] // FS_COMBINED_PROFILE: [valueid, modid, flags, instcount, fflags, numrefs, @@ -5609,6 +5658,10 @@ case bitc::FS_TYPE_ID: parseTypeIdSummaryRecord(Record, Strtab, TheIndex); break; + + case bitc::FS_TYPE_ID_METADATA: + parseTypeIdMetadataSummaryRecord(Record); + break; } } llvm_unreachable("Exit infinite loop"); Index: lib/Bitcode/Writer/BitcodeWriter.cpp =================================================================== --- lib/Bitcode/Writer/BitcodeWriter.cpp +++ lib/Bitcode/Writer/BitcodeWriter.cpp @@ -214,7 +214,8 @@ const Function &F); void writeModuleLevelReferences(const GlobalVariable &V, SmallVector &NameVals, - unsigned FSModRefsAbbrev); + unsigned FSModRefsAbbrev, + unsigned FSModVTableRefsAbbrev); void assignValueId(GlobalValue::GUID ValGUID) { GUIDToValueIdMap[ValGUID] = ++GlobalValueId; @@ -3527,6 +3528,18 @@ W.second); } +static void writeTypeIdMetadataSummaryRecord( + SmallVector &NameVals, StringTableBuilder &StrtabBuilder, + const std::string &Id, const TypeIdGVInfo &Summary, ValueEnumerator &VE) { + NameVals.push_back(StrtabBuilder.add(Id)); + NameVals.push_back(Id.size()); + + for (auto &P : Summary) { + NameVals.push_back(P.first); + NameVals.push_back(VE.getValueID(P.second.getValue())); + } +} + // Helper to emit a single function summary record. void ModuleBitcodeWriterBase::writePerModuleFunctionSummaryRecord( SmallVector &NameVals, GlobalValueSummary *Summary, @@ -3571,7 +3584,7 @@ // and emit them in a summary record. void ModuleBitcodeWriterBase::writeModuleLevelReferences( const GlobalVariable &V, SmallVector &NameVals, - unsigned FSModRefsAbbrev) { + unsigned FSModRefsAbbrev, unsigned FSModVTableRefsAbbrev) { auto VI = Index->getValueInfo(V.getGUID()); if (!VI || VI.getSummaryList().empty()) { // Only declarations should not have a summary (a declaration might however @@ -3585,6 +3598,10 @@ NameVals.push_back(getEncodedGVSummaryFlags(VS->flags())); NameVals.push_back(getEncodedGVarFlags(VS->varflags())); + auto VTableFuncs = VS->vTableFuncs(); + if (!VTableFuncs.empty()) + NameVals.push_back(VS->refs().size()); + unsigned SizeBeforeRefs = NameVals.size(); for (auto &RI : VS->refs()) NameVals.push_back(VE.getValueID(RI.getValue())); @@ -3592,8 +3609,20 @@ // been initialized from a DenseSet. llvm::sort(NameVals.begin() + SizeBeforeRefs, NameVals.end()); - Stream.EmitRecord(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS, NameVals, - FSModRefsAbbrev); + if (!VTableFuncs.empty()) { + // VTableFuncs pairs should already be sorted by offset. + for (auto &P : VTableFuncs) { + NameVals.push_back(VE.getValueID(P.first.getValue())); + NameVals.push_back(P.second); + } + } + + if (VTableFuncs.empty()) + Stream.EmitRecord(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS, NameVals, + FSModRefsAbbrev); + else + Stream.EmitRecord(bitc::FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS, NameVals, + FSModVTableRefsAbbrev); NameVals.clear(); } @@ -3674,6 +3703,17 @@ Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); unsigned FSModRefsAbbrev = Stream.EmitAbbrev(std::move(Abbv)); + // Abbrev for FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS. + Abbv = std::make_shared(); + Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // flags + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // numrefs + // numrefs x valueid, n x (valueid , offset) + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); + unsigned FSModVTableRefsAbbrev = Stream.EmitAbbrev(std::move(Abbv)); + // Abbrev for FS_ALIAS. Abbv = std::make_shared(); Abbv->Add(BitCodeAbbrevOp(bitc::FS_ALIAS)); @@ -3682,6 +3722,16 @@ Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid unsigned FSAliasAbbrev = Stream.EmitAbbrev(std::move(Abbv)); + // Abbrev for FS_TYPE_ID_METADATA + Abbv = std::make_shared(); + Abbv->Add(BitCodeAbbrevOp(bitc::FS_TYPE_ID_METADATA)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // typeid strtab index + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // typeid length + // n x (valueid , offset) + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array)); + Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); + unsigned TypeIdMetadataAbbrev = Stream.EmitAbbrev(std::move(Abbv)); + SmallVector NameVals; // Iterate over the list of functions instead of the Index to // ensure the ordering is stable. @@ -3706,7 +3756,8 @@ // Capture references from GlobalVariable initializers, which are outside // of a function scope. for (const GlobalVariable &G : M.globals()) - writeModuleLevelReferences(G, NameVals, FSModRefsAbbrev); + writeModuleLevelReferences(G, NameVals, FSModRefsAbbrev, + FSModVTableRefsAbbrev); for (const GlobalAlias &A : M.aliases()) { auto *Aliasee = A.getBaseObject(); @@ -3724,6 +3775,16 @@ NameVals.clear(); } + if (!Index->typeIdMetadataMap().empty()) { + for (auto &S : Index->typeIdMetadataMap()) { + writeTypeIdMetadataSummaryRecord(NameVals, StrtabBuilder, S.first, + S.second, VE); + Stream.EmitRecord(bitc::FS_TYPE_ID_METADATA, NameVals, + TypeIdMetadataAbbrev); + NameVals.clear(); + } + } + Stream.ExitBlock(); } Index: lib/IR/AsmWriter.cpp =================================================================== --- lib/IR/AsmWriter.cpp +++ lib/IR/AsmWriter.cpp @@ -1037,6 +1037,9 @@ TidIter != TheIndex->typeIds().end(); TidIter++) CreateTypeIdSlot(TidIter->second.first); + for (auto &TId : TheIndex->typeIdMetadataMap()) + CreateGUIDSlot(GlobalValue::getGUID(TId.first)); + ST_DEBUG("end processIndex!\n"); } @@ -2392,6 +2395,7 @@ void printGlobalVarSummary(const GlobalVarSummary *GS); void printFunctionSummary(const FunctionSummary *FS); void printTypeIdSummary(const TypeIdSummary &TIS); + void printTypeIdMetadataSummary(const TypeIdGVInfo &TI); void printTypeTestResolution(const TypeTestResolution &TTRes); void printArgs(const std::vector &Args); void printWPDRes(const WholeProgramDevirtResolution &WPDRes); @@ -2694,6 +2698,15 @@ printTypeIdSummary(TidIter->second.second); Out << ") ; guid = " << TidIter->first << "\n"; } + + // Print the TypeIdMetadataMap entries. + for (auto &TId : TheIndex->typeIdMetadataMap()) { + auto GUID = GlobalValue::getGUID(TId.first); + Out << "^" << Machine.getGUIDSlot(GUID) << " = typeidMetadata: (name: \"" + << TId.first << "\""; + printTypeIdMetadataSummary(TId.second); + Out << ") ; guid = " << GUID << "\n"; + } } static const char * @@ -2776,6 +2789,18 @@ Out << ")"; } +void AssemblyWriter::printTypeIdMetadataSummary(const TypeIdGVInfo &TI) { + Out << ", summary: ("; + FieldSeparator FS; + for (auto &P : TI) { + Out << FS; + Out << "(offset: " << P.first << ", "; + Out << "^" << Machine.getGUIDSlot(P.second.getGUID()); + Out << ")"; + } + Out << ")"; +} + void AssemblyWriter::printArgs(const std::vector &Args) { Out << "args: ("; FieldSeparator FS; @@ -2845,6 +2870,19 @@ void AssemblyWriter::printGlobalVarSummary(const GlobalVarSummary *GS) { Out << ", varFlags: (readonly: " << GS->VarFlags.ReadOnly << ")"; + + auto VTableFuncs = GS->vTableFuncs(); + if (!VTableFuncs.empty()) { + Out << ", vTableFuncs: ("; + FieldSeparator FS; + for (auto &P : VTableFuncs) { + Out << FS; + Out << "(virtFunc: ^" << Machine.getGUIDSlot(P.first.getGUID()) + << ", offset: " << P.second; + Out << ")"; + } + Out << ")"; + } } static std::string getLinkageName(GlobalValue::LinkageTypes LT) { Index: lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp =================================================================== --- lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp +++ lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp @@ -417,34 +417,55 @@ } } -// Returns whether this module needs to be split because splitting is -// enabled and it uses type metadata. -bool requiresSplit(Module &M) { - // First check if the LTO Unit splitting has been enabled. +// Check if the LTO Unit splitting has been enabled. +bool enableSplitLTOUnit(Module &M) { bool EnableSplitLTOUnit = false; if (auto *MD = mdconst::extract_or_null( M.getModuleFlag("EnableSplitLTOUnit"))) EnableSplitLTOUnit = MD->getZExtValue(); - if (!EnableSplitLTOUnit) - return false; + return EnableSplitLTOUnit; +} - // Module only needs to be split if it contains type metadata. +// Returns whether this module needs to be split because it uses type metadata. +bool hasTypeMetadata(Module &M) { for (auto &GO : M.global_objects()) { if (GO.hasMetadata(LLVMContext::MD_type)) return true; } - return false; } void writeThinLTOBitcode(raw_ostream &OS, raw_ostream *ThinLinkOS, function_ref AARGetter, Module &M, const ModuleSummaryIndex *Index) { - // Split module if splitting is enabled and it contains any type metadata. - if (requiresSplit(M)) - return splitAndWriteThinLTOBitcode(OS, ThinLinkOS, AARGetter, M); + std::unique_ptr NewIndex = nullptr; + // See if this module has any type metadata. If so, we try to split it + // or at least promote type ids to enable WPD. + if (hasTypeMetadata(M)) { + if (enableSplitLTOUnit(M)) + return splitAndWriteThinLTOBitcode(OS, ThinLinkOS, AARGetter, M); + else { + // Promote type ids as needed for index-based WPD. + std::string ModuleId = getUniqueModuleId(&M); + if (!ModuleId.empty()) { + promoteTypeIds(M, ModuleId); + // Need to rebuild the index so that it contains type metadata + // for the newly promoted type ids. + // FIXME: Probably should not bother building the index at all + // in the caller of writeThinLTOBitcode (which does so via the + // ModuleSummaryIndexAnalysis pass), since we have to rebuild it + // anyway whenever there is type metadata (here or in + // splitAndWriteThinLTOBitcode). Just always build it once via the + // buildModuleSummaryIndex when Module(s) are ready. + ProfileSummaryInfo PSI(M); + NewIndex = llvm::make_unique( + buildModuleSummaryIndex(M, nullptr, &PSI)); + Index = NewIndex.get(); + } + } + } - // Otherwise we can just write it out as a regular module. + // Write it out as an unsplit ThinLTO module. // Save the module hash produced for the full bitcode, which will // be used in the backends, and use that in the minimized bitcode Index: tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp =================================================================== --- tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp +++ tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp @@ -316,6 +316,7 @@ STRINGIFY_CODE(FS, PERMODULE_PROFILE) STRINGIFY_CODE(FS, PERMODULE_RELBF) STRINGIFY_CODE(FS, PERMODULE_GLOBALVAR_INIT_REFS) + STRINGIFY_CODE(FS, PERMODULE_VTABLE_GLOBALVAR_INIT_REFS) STRINGIFY_CODE(FS, COMBINED) STRINGIFY_CODE(FS, COMBINED_PROFILE) STRINGIFY_CODE(FS, COMBINED_GLOBALVAR_INIT_REFS) @@ -333,6 +334,7 @@ STRINGIFY_CODE(FS, CFI_FUNCTION_DEFS) STRINGIFY_CODE(FS, CFI_FUNCTION_DECLS) STRINGIFY_CODE(FS, TYPE_ID) + STRINGIFY_CODE(FS, TYPE_ID_METADATA) } case bitc::METADATA_ATTACHMENT_ID: switch(CodeID) {