Index: lld/trunk/COFF/InputFiles.h =================================================================== --- lld/trunk/COFF/InputFiles.h +++ lld/trunk/COFF/InputFiles.h @@ -15,6 +15,7 @@ #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" +#include "llvm/DebugInfo/CodeView/TypeHashing.h" #include "llvm/DebugInfo/CodeView/TypeRecord.h" #include "llvm/LTO/LTO.h" #include "llvm/Object/Archive.h" @@ -28,7 +29,7 @@ namespace pdb { class DbiModuleDescriptorBuilder; } -} +} // namespace llvm namespace lld { namespace coff { @@ -38,10 +39,10 @@ using llvm::COFF::IMAGE_FILE_MACHINE_UNKNOWN; using llvm::COFF::MachineTypes; using llvm::object::Archive; -using llvm::object::COFFObjectFile; -using llvm::object::COFFSymbolRef; using llvm::object::coff_import_header; using llvm::object::coff_section; +using llvm::object::COFFObjectFile; +using llvm::object::COFFSymbolRef; class Chunk; class Defined; @@ -55,7 +56,14 @@ // The root class of input files. class InputFile { public: - enum Kind { ArchiveKind, ObjectKind, ImportKind, BitcodeKind }; + enum Kind { + ArchiveKind, + ObjectKind, + ImportKind, + BitcodeKind, + PDBKind, + PCHKind + }; Kind kind() const { return FileKind; } virtual ~InputFile() {} @@ -106,6 +114,7 @@ // .obj or .o file. This may be a member of an archive file. class ObjFile : public InputFile { public: + explicit ObjFile(Kind K, MemoryBufferRef M) : InputFile(K, M) {} explicit ObjFile(MemoryBufferRef M) : InputFile(ObjectKind, M) {} static bool classof(const InputFile *F) { return F->kind() == ObjectKind; } void parse() override; @@ -119,9 +128,7 @@ // Returns a Symbol object for the SymbolIndex'th symbol in the // underlying object file. - Symbol *getSymbol(uint32_t SymbolIndex) { - return Symbols[SymbolIndex]; - } + Symbol *getSymbol(uint32_t SymbolIndex) { return Symbols[SymbolIndex]; } // Returns the underlying COFF file. COFFObjectFile *getCOFFObj() { return COFFObj.get(); } @@ -154,7 +161,9 @@ // When using Microsoft precompiled headers, this is the PCH's key. // The same key is used by both the precompiled object, and objects using the // precompiled object. Any difference indicates out-of-date objects. - llvm::Optional EndPrecomp; + llvm::Optional PCHSignature; + + std::vector OwnedHashes; private: void initializeChunks(); Index: lld/trunk/COFF/PDB.cpp =================================================================== --- lld/trunk/COFF/PDB.cpp +++ lld/trunk/COFF/PDB.cpp @@ -52,6 +52,7 @@ #include "llvm/Support/Errc.h" #include "llvm/Support/FormatVariadic.h" #include "llvm/Support/JamCRC.h" +#include "llvm/Support/Parallel.h" #include "llvm/Support/Path.h" #include "llvm/Support/ScopedPrinter.h" #include @@ -68,12 +69,17 @@ static Timer TotalPdbLinkTimer("PDB Emission (Cumulative)", Timer::root()); static Timer AddObjectsTimer("Add Objects", TotalPdbLinkTimer); +static Timer GlobalHashTimer("Global hashing", AddObjectsTimer); static Timer TypeMergingTimer("Type Merging", AddObjectsTimer); +static Timer HashtableLookupTimer("Hashtable lookup", TypeMergingTimer); static Timer SymbolMergingTimer("Symbol Merging", AddObjectsTimer); static Timer GlobalsLayoutTimer("Globals Stream Layout", TotalPdbLinkTimer); static Timer TpiStreamLayoutTimer("TPI Stream Layout", TotalPdbLinkTimer); static Timer DiskCommitTimer("Commit to Disk", TotalPdbLinkTimer); +void startGlobalHashTimer() { HashtableLookupTimer.start(); } +void stopGlobalHashTimer() { HashtableLookupTimer.stop(); } + namespace { /// Map from type index and item index in a type server PDB to the /// corresponding index in the destination PDB. @@ -84,6 +90,50 @@ bool IsPrecompiledTypeMap = false; }; +// A PDB type server, which might be a dependency of another OBJ +class PDBDependency : public InputFile { +public: + explicit PDBDependency(MemoryBufferRef M) : InputFile(PDBKind, M) { + // Mark this map as a type server map. + IndexMap.IsTypeServerMap = true; + } + static bool classof(const InputFile *F) { return F->kind() == PDBKind; } + + void parse() override {} + + static std::map Instances; + + std::unique_ptr Session; + CVIndexMap IndexMap; + + std::vector TpiHashes; + std::vector IpiHashes; +}; + +std::map PDBDependency::Instances; + +// A PCH (precompiled header OBJ, which might be a dependency of another OBJ +class PCHDependency : public InputFile { +public: + explicit PCHDependency(ObjFile *O) : InputFile(PCHKind, O->MB) { + RefObj = O; + // Mark this map as a precompiled types map. + IndexMap.IsPrecompiledTypeMap = true; + } + static bool classof(const InputFile *F) { return F->kind() == PCHKind; } + + void parse() override {} + + ObjFile *refObj() const { return RefObj; } + + static std::map Instances; + + ObjFile *RefObj; + CVIndexMap IndexMap; +}; + +std::map PCHDependency::Instances; + class DebugSHandler; class PDBLinker { @@ -108,10 +158,12 @@ /// Link CodeView from each object file in the symbol table into the PDB. void addObjectsToPDB(); + Error mergeAllOBJ(); + /// Link CodeView from a single object file into the target (output) PDB. /// When a precompiled headers object is linked, its TPI map might be provided /// externally. - void addObjFile(ObjFile *File, CVIndexMap *ExternIndexMap = nullptr); + void mergeSymbols(ObjFile *File, CVIndexMap *IndexMap); /// Produce a mapping from the type and item indices used in the object /// file to those in the destination PDB. @@ -124,19 +176,26 @@ /// If the object does not use a type server PDB (compiled with /Z7), we merge /// all the type and item records from the .debug$S stream and fill in the /// caller-provided ObjectIndexMap. - Expected mergeDebugT(ObjFile *File, - CVIndexMap *ObjectIndexMap); + + Expected computeHash(InputFile *File); + + Error openDependencies(InputFile *File); + + Expected mergeTypes(InputFile *File, CVIndexMap &TIStorage); + + void mergeTypeStream(ObjFile *File, CVTypeArray &Types, + CVIndexMap &ObjectIndexMap); /// Reads and makes available a PDB. - Expected maybeMergeTypeServerPDB(ObjFile *File, - const CVType &FirstType); + Expected openPDB(ObjFile *File, const CVType &FirstType); + unsigned computePDBHashes(PDBDependency *D); + void mergePDB(PDBDependency *D); /// Merges a precompiled headers TPI map into the current TPI map. The /// precompiled headers object will also be loaded and remapped in the /// process. - Expected - mergeInPrecompHeaderObj(ObjFile *File, const CVType &FirstType, - CVIndexMap *ObjectIndexMap); + Error mergeInPCH(ObjFile *File, CVTypeArray &Stream, + CVIndexMap &ObjectIndexMap); /// Reads and makes available a precompiled headers object. /// @@ -147,12 +206,7 @@ /// /// If the precompiled headers object was already loaded, this function will /// simply return its (remapped) TPI map. - Expected aquirePrecompObj(ObjFile *File, - PrecompRecord Precomp); - - /// Adds a precompiled headers object signature -> TPI mapping. - std::pair - registerPrecompiledHeaders(uint32_t Signature); + Expected openPCH(ObjFile *File); void mergeSymbolRecords(ObjFile *File, const CVIndexMap &IndexMap, std::vector &StringTableRefs, @@ -204,23 +258,7 @@ llvm::SmallString<128> NativePath; - /// A list of other PDBs which are loaded during the linking process and which - /// we need to keep around since the linking operation may reference pointers - /// inside of these PDBs. - llvm::SmallVector, 2> LoadedPDBs; - std::vector SectionMap; - - /// Type index mappings of type server PDBs that we've loaded so far. - std::map TypeServerIndexMappings; - - /// Type index mappings of precompiled objects type map that we've loaded so - /// far. - std::map PrecompTypeIndexMappings; - - /// List of TypeServer PDBs which cannot be loaded. - /// Cached to prevent repeated load attempts. - std::map MissingTypeServerPDBs; }; class DebugSHandler { @@ -266,7 +304,7 @@ void handleDebugS(lld::coff::SectionChunk &DebugS); void finish(); }; -} +} // namespace // Visual Studio's debugger requires absolute paths in various places in the // PDB to work without additional configuration: @@ -379,12 +417,15 @@ // must be same for all objects which depend on the precompiled object. // Recompiling the precompiled headers will generate a new PCH key and thus // invalidate all the dependent objects. -static uint32_t extractPCHSignature(ObjFile *File) { +static void extractPCHSignature(ObjFile *File) { + if (File->PCHSignature) + return; + auto DbgIt = find_if(File->getDebugChunks(), [](SectionChunk *C) { return C->getSectionName() == ".debug$S"; }); if (!DbgIt) - return 0; + return; ArrayRef Contents = consumeDebugMagic((*DbgIt)->getContents(), ".debug$S"); @@ -402,108 +443,145 @@ consumeError(Sym.takeError()); continue; } - if (auto ObjName = SymbolDeserializer::deserializeAs(Sym.get())) - return ObjName->Signature; + if (auto ObjName = + SymbolDeserializer::deserializeAs(Sym.get())) { + File->PCHSignature.emplace(ObjName->Signature); + return; + } } - return 0; + return; } -Expected -PDBLinker::mergeDebugT(ObjFile *File, CVIndexMap *ObjectIndexMap) { - ScopedTimer T(TypeMergingTimer); - - bool IsPrecompiledHeader = false; - - ArrayRef Data = getDebugSection(File, ".debug$T"); - if (Data.empty()) { - // Try again, Microsoft precompiled headers use .debug$P instead of - // .debug$T - Data = getDebugSection(File, ".debug$P"); - IsPrecompiledHeader = true; +template +unsigned computeTypeHashes( + ObjFile *File, Range &&Types, + ArrayRef PrecompHashes = {}) { + if (Config->DebugGHashes) { + Optional> DebugH = getDebugH(File); + if (!DebugH) { + assert(File->OwnedHashes.empty()); + File->OwnedHashes = GloballyHashedType::hashTypes(Types, PrecompHashes); + return File->OwnedHashes.size() - PrecompHashes.size(); + } } - if (Data.empty()) - return *ObjectIndexMap; // no debug info + return 0; +} - // Precompiled headers objects need to save the index map for further - // reference by other objects which use the precompiled headers. - if (IsPrecompiledHeader) { - uint32_t PCHSignature = extractPCHSignature(File); - if (PCHSignature == 0) - fatal("No signature found for the precompiled headers OBJ (" + - File->getName() + ")"); +namespace { +enum TypeStreamKind { NoDebugInfo, RegularOBJ, PCH, UsingPCH, PDB, UsingPDB }; - // When a precompiled headers object comes first on the command-line, we - // update the mapping here. Otherwise, if an object referencing the - // precompiled headers object comes first, the mapping is created in - // aquirePrecompObj(), thus we would skip this block. - if (!ObjectIndexMap->IsPrecompiledTypeMap) { - auto R = registerPrecompiledHeaders(PCHSignature); - if (R.second) - fatal( - "A precompiled headers OBJ with the same signature was already " - "provided! (" + - File->getName() + ")"); +struct Ident { + TypeStreamKind Kind; + CVTypeArray Types; +}; +} // namespace - ObjectIndexMap = &R.first; - } - } +static Ident identifyTypeStream(InputFile *File) { + if (isa(File)) + return {PDB, {}}; + if (isa(File)) + return {PCH, identifyTypeStream(cast(File)->refObj()).Types}; + + ObjFile *Obj = cast(File); + + extractPCHSignature(Obj); + + bool IsPCH = false; + + auto Data = getDebugSection(Obj, ".debug$P"); + if (!Data.empty()) + IsPCH = true; + else + Data = getDebugSection(Obj, ".debug$T"); + + if (Data.empty()) + return {NoDebugInfo, {}}; - BinaryByteStream Stream(Data, support::little); CVTypeArray Types; - BinaryStreamReader Reader(Stream); + BinaryStreamReader Reader(Data, support::little); if (auto EC = Reader.readArray(Types, Reader.getLength())) fatal("Reader::readArray failed: " + toString(std::move(EC))); auto FirstType = Types.begin(); if (FirstType == Types.end()) - return *ObjectIndexMap; + return {NoDebugInfo, {}}; - if (FirstType->kind() == LF_TYPESERVER2) { - // Look through type servers. If we've already seen this type server, - // don't merge any type information. - return maybeMergeTypeServerPDB(File, *FirstType); + if (IsPCH) { + return {PCH, Types}; + } else if (FirstType->kind() == LF_TYPESERVER2) { + return {UsingPDB, Types}; } else if (FirstType->kind() == LF_PRECOMP) { - // This object was compiled with /Yu, so process the corresponding - // precompiled headers object (/Yc) first. Some type indices in the current - // object are referencing data in the precompiled headers object, so we need - // both to be loaded. - auto E = mergeInPrecompHeaderObj(File, *FirstType, ObjectIndexMap); + return {UsingPCH, Types}; + } + return {RegularOBJ, Types}; +} + +Error PDBLinker::openDependencies(InputFile *File) { + auto Stream = identifyTypeStream(File); + if (Stream.Kind == UsingPDB) { + auto E = openPDB(cast(File), *Stream.Types.begin()); + if (!E) + return E.takeError(); + } else if (Stream.Kind == PCH) { + auto E = openPCH(cast(File)); if (!E) return E.takeError(); + } + return Error::success(); +} - // Drop LF_PRECOMP record from the input stream, as it needs to be replaced - // with the precompiled headers object type stream. - Types.drop_front(); +Expected PDBLinker::mergeTypes(InputFile *File, + CVIndexMap &TIStorage) { + ScopedTimer T1(TypeMergingTimer); + + auto Stream = identifyTypeStream(File); + if (Stream.Kind == NoDebugInfo) + return nullptr; + + if (Stream.Kind == UsingPCH) { + if (auto E = mergeInPCH(cast(File), Stream.Types, TIStorage)) + return std::move(E); + mergeTypeStream(cast(File), Stream.Types, TIStorage); + } else if (Stream.Kind == RegularOBJ) { + mergeTypeStream(cast(File), Stream.Types, TIStorage); + } else if (Stream.Kind == PCH) { + PCHDependency *D = cast(File); + mergeTypeStream(D->refObj(), Stream.Types, D->IndexMap); + } else if (Stream.Kind == PDB) { + PDBDependency *D = cast(File); + mergePDB(D); + return &D->IndexMap; } + return &TIStorage; +} - // Fill in the temporary, caller-provided ObjectIndexMap. +void PDBLinker::mergeTypeStream(ObjFile *File, CVTypeArray &Types, + CVIndexMap &ObjectIndexMap) { if (Config->DebugGHashes) { ArrayRef Hashes; - std::vector OwnedHashes; if (Optional> DebugH = getDebugH(File)) Hashes = getHashesFromDebugH(*DebugH); else { - OwnedHashes = GloballyHashedType::hashTypes(Types); - Hashes = OwnedHashes; + Hashes = File->OwnedHashes; } if (auto Err = mergeTypeAndIdRecords(GlobalIDTable, GlobalTypeTable, - ObjectIndexMap->TPIMap, Types, Hashes, - File->EndPrecomp)) + ObjectIndexMap.TPIMap, Types, Hashes, + &File->PCHSignature)) fatal("codeview::mergeTypeAndIdRecords failed: " + toString(std::move(Err))); + } else { if (auto Err = - mergeTypeAndIdRecords(IDTable, TypeTable, ObjectIndexMap->TPIMap, - Types, File->EndPrecomp)) + mergeTypeAndIdRecords(IDTable, TypeTable, ObjectIndexMap.TPIMap, + Types, &File->PCHSignature)) fatal("codeview::mergeTypeAndIdRecords failed: " + toString(std::move(Err))); } - return *ObjectIndexMap; } -static Expected> -tryToLoadPDB(const GUID &GuidFromObj, StringRef TSPath) { +static Expected +tryToLoadPDB(const llvm::codeview::GUID &GuidFromObj, StringRef TSPath) { // Ensure the file exists before anything else. We want to return ENOENT, // "file not found", even if the path points to a removable device (in which // case the return message would be EAGAIN, "resource unavailable try again") @@ -534,46 +612,40 @@ // PDB file doesn't mean it matches. For it to match the InfoStream's GUID // must match the GUID specified in the TypeServer2 record. if (ExpectedInfo->getGuid() != GuidFromObj) - return make_error(pdb::pdb_error_code::signature_out_of_date); + return make_error( + pdb::pdb_error_code::signature_out_of_date); - return std::move(NS); + PDBDependency *D = make(*MBOrErr.get()); + D->Session = std::move(NS); + return D; } -Expected -PDBLinker::maybeMergeTypeServerPDB(ObjFile *File, const CVType &FirstType) { +// Look through type servers. If we've already seen this type server, +// don't merge any type information. +Expected PDBLinker::openPDB(ObjFile *DependentFile, + const CVType &FirstType) { TypeServer2Record TS; if (auto EC = TypeDeserializer::deserializeAs(const_cast(FirstType), TS)) fatal("error reading record: " + toString(std::move(EC))); - const GUID &TSId = TS.getGuid(); + const auto &TSId = TS.getGuid(); StringRef TSPath = TS.getName(); - // First, check if the PDB has previously failed to load. - auto PrevErr = MissingTypeServerPDBs.find(TSId); - if (PrevErr != MissingTypeServerPDBs.end()) - return createFileError( - TSPath, - make_error(PrevErr->second, inconvertibleErrorCode())); - - // Second, check if we already loaded a PDB with this GUID. Return the type - // index mapping if we have it. - auto Insertion = TypeServerIndexMappings.insert({TSId, CVIndexMap()}); - CVIndexMap &IndexMap = Insertion.first->second; - if (!Insertion.second) - return IndexMap; - - // Mark this map as a type server map. - IndexMap.IsTypeServerMap = true; + // Check if we already loaded a PDB with this GUID. + auto I = PDBDependency::Instances.find(TSId); + if (I != PDBDependency::Instances.end()) + return I->second; // Check for a PDB at: // 1. The given file path // 2. Next to the object file or archive file - auto ExpectedSession = handleExpected( + auto ExpectedPDB = handleExpected( tryToLoadPDB(TSId, TSPath), [&]() { - StringRef LocalPath = - !File->ParentName.empty() ? File->ParentName : File->getName(); + StringRef LocalPath = !DependentFile->ParentName.empty() + ? DependentFile->ParentName + : DependentFile->getName(); SmallString<128> Path = sys::path::parent_path(LocalPath); // Currently, type server PDBs are only created by cl, which only runs // on Windows, so we can assume type server paths are Windows style. @@ -591,105 +663,141 @@ return Error(std::move(EC)); }); - if (auto E = ExpectedSession.takeError()) { - TypeServerIndexMappings.erase(TSId); - - // Flatten the error to a string, for later display, if the error occurs - // again on the same PDB. - std::string ErrMsg; - raw_string_ostream S(ErrMsg); - S << E; - MissingTypeServerPDBs.emplace(TSId, S.str()); - + if (auto E = ExpectedPDB.takeError()) { + PDBDependency::Instances.emplace(TSId, nullptr); return createFileError(TSPath, std::move(E)); } - pdb::NativeSession *Session = ExpectedSession->get(); - - // Keep a strong reference to this PDB, so that it's safe to hold pointers - // into the file. - LoadedPDBs.push_back(std::move(*ExpectedSession)); + PDBDependency *D = *ExpectedPDB; + PDBDependency::Instances.insert({TSId, D}); - auto ExpectedTpi = Session->getPDBFile().getPDBTpiStream(); + auto ExpectedTpi = D->Session->getPDBFile().getPDBTpiStream(); if (auto E = ExpectedTpi.takeError()) fatal("Type server does not have TPI stream: " + toString(std::move(E))); - auto ExpectedIpi = Session->getPDBFile().getPDBIpiStream(); + auto ExpectedIpi = D->Session->getPDBFile().getPDBIpiStream(); if (auto E = ExpectedIpi.takeError()) fatal("Type server does not have TPI stream: " + toString(std::move(E))); + return D; +} + +unsigned PDBLinker::computePDBHashes(PDBDependency *D) { if (Config->DebugGHashes) { + auto ExpectedTpi = D->Session->getPDBFile().getPDBTpiStream(); + auto ExpectedIpi = D->Session->getPDBFile().getPDBIpiStream(); // PDBs do not actually store global hashes, so when merging a type server // PDB we have to synthesize global hashes. To do this, we first synthesize // global hashes for the TPI stream, since it is independent, then we // synthesize hashes for the IPI stream, using the hashes for the TPI stream // as inputs. - auto TpiHashes = GloballyHashedType::hashTypes(ExpectedTpi->typeArray()); - auto IpiHashes = - GloballyHashedType::hashIds(ExpectedIpi->typeArray(), TpiHashes); + D->TpiHashes = GloballyHashedType::hashTypes(ExpectedTpi->typeArray()); + D->IpiHashes = + GloballyHashedType::hashIds(ExpectedIpi->typeArray(), D->TpiHashes); + return D->TpiHashes.size() + D->IpiHashes.size(); + } + return 0; +} - Optional EndPrecomp; +void PDBLinker::mergePDB(PDBDependency *D) { + auto ExpectedTpi = D->Session->getPDBFile().getPDBTpiStream(); + auto ExpectedIpi = D->Session->getPDBFile().getPDBIpiStream(); + if (Config->DebugGHashes) { // Merge TPI first, because the IPI stream will reference type indices. - if (auto Err = mergeTypeRecords(GlobalTypeTable, IndexMap.TPIMap, - ExpectedTpi->typeArray(), TpiHashes, EndPrecomp)) + if (auto Err = mergeTypeRecords(GlobalTypeTable, D->IndexMap.TPIMap, + ExpectedTpi->typeArray(), D->TpiHashes)) fatal("codeview::mergeTypeRecords failed: " + toString(std::move(Err))); // Merge IPI. - if (auto Err = - mergeIdRecords(GlobalIDTable, IndexMap.TPIMap, IndexMap.IPIMap, - ExpectedIpi->typeArray(), IpiHashes)) + if (auto Err = mergeIdRecords(GlobalIDTable, D->IndexMap.TPIMap, + D->IndexMap.IPIMap, ExpectedIpi->typeArray(), + D->IpiHashes)) fatal("codeview::mergeIdRecords failed: " + toString(std::move(Err))); } else { // Merge TPI first, because the IPI stream will reference type indices. - if (auto Err = mergeTypeRecords(TypeTable, IndexMap.TPIMap, + if (auto Err = mergeTypeRecords(TypeTable, D->IndexMap.TPIMap, ExpectedTpi->typeArray())) fatal("codeview::mergeTypeRecords failed: " + toString(std::move(Err))); // Merge IPI. - if (auto Err = mergeIdRecords(IDTable, IndexMap.TPIMap, IndexMap.IPIMap, - ExpectedIpi->typeArray())) + if (auto Err = mergeIdRecords(IDTable, D->IndexMap.TPIMap, + D->IndexMap.IPIMap, ExpectedIpi->typeArray())) fatal("codeview::mergeIdRecords failed: " + toString(std::move(Err))); } - - return IndexMap; } -Expected -PDBLinker::mergeInPrecompHeaderObj(ObjFile *File, const CVType &FirstType, - CVIndexMap *ObjectIndexMap) { +Expected> +findPCH(ObjFile *File, CVTypeArray &Stream) { + uint32_t Signature = File->PCHSignature.getValueOr(0); + if (!Signature) + fatal("No signature found for the PCH-dependent OBJ (" + File->getName() + + ")"); + PrecompRecord Precomp; - if (auto EC = TypeDeserializer::deserializeAs(const_cast(FirstType), - Precomp)) + if (auto EC = TypeDeserializer::deserializeAs( + const_cast(*Stream.begin()), Precomp)) fatal("error reading record: " + toString(std::move(EC))); - auto E = aquirePrecompObj(File, Precomp); - if (!E) - return E.takeError(); + if (File->PCHSignature.getValue() != Precomp.getSignature()) + fatal("Corrupted file, the signature does not match the precomp record (" + + File->getName() + ")"); + + // link.exe requires that the PCH OBJ must always be provided + // on the command-line, even if its path could be infered from the precomp + // record. + auto PCH = PCHDependency::Instances.find(*File->PCHSignature); + if (PCH == PCHDependency::Instances.end()) { + // Cross-compile warning: given that Clang doesn't generate LF_PRECOMP + // records, we assume the OBJ comes from MSVC. Thusly, the paths embedded in + // the OBJs are in the Windows format. + SmallString<128> PrecompFileName = sys::path::filename( + Precomp.getPrecompFilePath(), sys::path::Style::windows); + return createFileError( + PrecompFileName.str(), + make_error(pdb::pdb_error_code::external_cmdline_ref)); + } + return std::pair{PCH->second, Precomp}; +} - const CVIndexMap &PrecompIndexMap = *E; - assert(PrecompIndexMap.IsPrecompiledTypeMap); +// This object was compiled with /Yu, the corresponding precompiled headers +// object (/Yc) has to be already loaded. Some type indices in the current +// object are referencing data in the precompiled headers object, so we need +// both to be in memory. +Error PDBLinker::mergeInPCH(ObjFile *File, CVTypeArray &Stream, + CVIndexMap &ObjectIndexMap) { + auto PCH = findPCH(File, Stream); + if (!PCH) + return PCH.takeError(); + + // Drop LF_PRECOMP record from the input stream, as it needs to be + // replaced with the PCH OBJ type stream below. + Stream.drop_front(); - if (PrecompIndexMap.TPIMap.empty()) - return PrecompIndexMap; + PCHDependency *D = PCH->first; + PrecompRecord &Precomp = PCH->second; + + const CVIndexMap &PrecompIndexMap = D->IndexMap; + assert(PrecompIndexMap.IsPrecompiledTypeMap); assert(Precomp.getStartTypeIndex() == TypeIndex::FirstNonSimpleIndex); assert(Precomp.getTypesCount() <= PrecompIndexMap.TPIMap.size()); + // Use the previously remapped index map from the precompiled headers. - ObjectIndexMap->TPIMap.append(PrecompIndexMap.TPIMap.begin(), - PrecompIndexMap.TPIMap.begin() + - Precomp.getTypesCount()); - return *ObjectIndexMap; + ObjectIndexMap.TPIMap.append(PrecompIndexMap.TPIMap.begin(), + PrecompIndexMap.TPIMap.begin() + + Precomp.getTypesCount()); + return Error::success(); } -static bool equals_path(StringRef path1, StringRef path2) { +/*static bool equals_path(StringRef path1, StringRef path2) { #if defined(_WIN32) return path1.equals_lower(path2); #else return path1.equals(path2); #endif -} +}*/ // Find by name an OBJ provided on the command line -static ObjFile *findObjByName(StringRef FileNameOnly) { +/*static ObjFile *findObjByName(StringRef FileNameOnly) { SmallString<128> CurrentPath; for (ObjFile *F : ObjFile::Instances) { @@ -700,28 +808,36 @@ return F; } return nullptr; -} +}*/ -std::pair -PDBLinker::registerPrecompiledHeaders(uint32_t Signature) { - auto Insertion = PrecompTypeIndexMappings.insert({Signature, CVIndexMap()}); - CVIndexMap &IndexMap = Insertion.first->second; - if (!Insertion.second) - return {IndexMap, true}; - // Mark this map as a precompiled types map. - IndexMap.IsPrecompiledTypeMap = true; - return {IndexMap, false}; -} - -Expected -PDBLinker::aquirePrecompObj(ObjFile *File, PrecompRecord Precomp) { - // First, check if we already loaded the precompiled headers object with this - // signature. Return the type index mapping if we've already seen it. - auto R = registerPrecompiledHeaders(Precomp.getSignature()); - if (R.second) - return R.first; +Expected PDBLinker::openPCH(ObjFile *File) { + uint32_t Signature = File->PCHSignature.getValueOr(0); + if (!Signature) + fatal("No signature found for the precompiled headers OBJ (" + + File->getName() + ")"); + + /*if (File->PCHSignature.getValue() != Precomp.getSignature()) + fatal("Corrupted file, the signature does not match the precomp record (" + + File->getName() + ")");*/ + + auto I = PCHDependency::Instances.find(Signature); + if (I != PCHDependency::Instances.end()) { + if (I->second->refObj()->getName() != File->getName()) + fatal("A precompiled headers OBJ with the same signature was already " + "provided! (" + + File->getName() + ")"); + return I->second; + } + + PCHDependency *D = make(File); + PCHDependency::Instances[Signature] = D; + + auto P = find(ObjFile::Instances, File); + ObjFile::Instances.erase(P); - CVIndexMap &IndexMap = R.first; + return D; + + /*CVIndexMap &IndexMap = R.first; // Cross-compile warning: given that Clang doesn't generate LF_PRECOMP // records, we assume the OBJ comes from a Windows build of cl.exe. Thusly, @@ -747,7 +863,44 @@ Precomp.getPrecompFilePath().str(), make_error(pdb::pdb_error_code::signature_out_of_date)); - return IndexMap; + return IndexMap;*/ +} + +Expected PDBLinker::computeHash(InputFile *File) { + auto Stream = identifyTypeStream(File); + switch (Stream.Kind) { + case PDB: + return computePDBHashes(cast(File)); + break; + case PCH: { + return computeTypeHashes(cast(File)->refObj(), Stream.Types); + } break; + case UsingPCH: { + auto PCH = findPCH(cast(File), Stream.Types); + if (!PCH) + return PCH.takeError(); + auto PrecompStream = identifyTypeStream(PCH->first); + + // We need to merge the previously computed PCH's hashes, however only the + // ones in the range [0, Precomp.TypesCount], where Precomp is the first + // LF_PRECOMP record read from the current OBJ. + auto PrecompHashes = makeArrayRef(PCH->first->refObj()->OwnedHashes.data(), + PCH->second.getTypesCount()); + + // Don't take into account LF_PRECOMP, because it is replaced (virtually in + // this case) by the PCH's stream + Stream.Types.drop_front(); + + return computeTypeHashes(cast(File), Stream.Types, PrecompHashes); + } break; + case RegularOBJ: + return computeTypeHashes(cast(File), Stream.Types); + break; + case UsingPDB: + case NoDebugInfo: + break; + } + return 0; } static bool remapTypeIndex(TypeIndex &TI, ArrayRef TypeIndexMap) { @@ -1292,18 +1445,52 @@ File.ModuleDBI->addDebugSubsection(std::move(NewChecksums)); } -void PDBLinker::addObjFile(ObjFile *File, CVIndexMap *ExternIndexMap) { - if (File->wasProcessedForPDB()) +struct ExitStep : ErrorInfo { + static char ID; +}; + +StringRef getFileNamePath(InputFile *File, SmallString<128> &Path) { + bool InArchive = !File->ParentName.empty(); + Path = InArchive ? File->ParentName : File->getName(); + pdbMakeAbsolute(Path); + StringRef Name = InArchive ? File->getName() : StringRef(Path); + return Name; +} + +/*void PDBLinker::mergeTypes(InputFile *File) { + // Before we can process symbol substreams from .debug$S, we need to process + // type information, file checksums, and the string table. Add type info to + // the PDB first, so that we can get the map from object file type and item + // indices to PDB type and item indices. + CVIndexMap ObjectIndexMap; + auto IndexMapResult = mergeDebugT(File, &ObjectIndexMap); + + if (IndexMapResult && !*IndexMapResult) return; + + // if (!IndexMapResult && IndexMapResult.errorIsA()) + // return; // probably a step that requests exiting + + // If the .debug$T sections fail to merge, assume there is no debug info. + if (!IndexMapResult) { + SmallString<128> Path; + StringRef Name = getFileNamePath(File, Path); + warn("Cannot use debug info for '" + sys::path::filename(Path) + "'\n" + + ">>> failed to load reference " + + StringRef(toString(IndexMapResult.takeError()))); + return; + } +}*/ + +void PDBLinker::mergeSymbols(ObjFile *File, CVIndexMap *IndexMap) { + + SmallString<128> Path; + StringRef Name = getFileNamePath(File, Path); + // Add a module descriptor for every object file. We need to put an absolute // path to the object into the PDB. If this is a plain object, we make its // path absolute. If it's an object in an archive, we make the archive path // absolute. - bool InArchive = !File->ParentName.empty(); - SmallString<128> Path = InArchive ? File->ParentName : File->getName(); - pdbMakeAbsolute(Path); - StringRef Name = InArchive ? File->getName() : StringRef(Path); - pdb::DbiStreamBuilder &DbiBuilder = Builder.getDbiBuilder(); File->ModuleDBI = &ExitOnErr(DbiBuilder.addModuleInfo(Name)); File->ModuleDBI->setObjFileName(Path); @@ -1319,26 +1506,12 @@ break; } - // Before we can process symbol substreams from .debug$S, we need to process - // type information, file checksums, and the string table. Add type info to - // the PDB first, so that we can get the map from object file type and item - // indices to PDB type and item indices. - CVIndexMap ObjectIndexMap; - auto IndexMapResult = - mergeDebugT(File, ExternIndexMap ? ExternIndexMap : &ObjectIndexMap); - - // If the .debug$T sections fail to merge, assume there is no debug info. - if (!IndexMapResult) { - auto FileName = sys::path::filename(Path); - warn("Cannot use debug info for '" + FileName + "'\n" + - ">>> failed to load reference " + - StringRef(toString(IndexMapResult.takeError()))); - return; - } + if (!IndexMap) + return; // no debug info ScopedTimer T(SymbolMergingTimer); - DebugSHandler DSH(*this, *File, *IndexMapResult); + DebugSHandler DSH(*this, *File, *IndexMap); // Now do all live .debug$S and .debug$F sections. for (SectionChunk *DebugChunk : File->getDebugChunks()) { if (!DebugChunk->Live || DebugChunk->getSize() == 0) @@ -1387,12 +1560,78 @@ return Pub; } +std::atomic TotalHashes{}; + +Error PDBLinker::mergeAllOBJ() { + + for (ObjFile *Obj : std::vector(ObjFile::Instances)) + if (auto E = openDependencies(Obj)) + return E; + + std::vector Depends; + for_each(PDBDependency::Instances, + [&](auto KV) { Depends.push_back(KV.second); }); + for_each(PCHDependency::Instances, + [&](auto KV) { Depends.push_back(KV.second); }); + + Optional LastError; + auto ComputeH = [&](InputFile *F) { + if (LastError) + return; + auto E = computeHash(F); + if (!E) { + if (LastError) + LastError = joinErrors(std::move(*LastError), E.takeError()); + else + LastError = E.takeError(); + } + TotalHashes += *E; + }; + + GlobalHashTimer.start(); + + // Compute Type GHASH-es for all indirect PDB/PCH files + for_each(parallel::par, Depends.begin(), Depends.end(), ComputeH); + + // Compute Type GHASH-es for all remaining OBJ files + for_each(parallel::par, ObjFile::Instances.begin(), ObjFile::Instances.end(), + ComputeH); + GlobalHashTimer.stop(); + + if (LastError) + return std::move(*LastError); + + // Merge Types in PDB/PCH files + for (InputFile *File : Depends) { + CVIndexMap TIStorage; + auto R = mergeTypes(File, TIStorage); + if (!R) + return R.takeError(); + + if (isa(File)) + mergeSymbols(cast(File)->refObj(), *R); + } + + // Merge Types and Symbols in all remaining OBJ files + for (ObjFile *File : ObjFile::Instances) { + CVIndexMap TIStorage; + auto R = mergeTypes(File, TIStorage); + if (!R) + return R.takeError(); + + mergeSymbols(File, *R); + } + return Error::success(); +} + // Add all object files to the PDB. Merge .debug$T sections into IpiData and // TpiData. void PDBLinker::addObjectsToPDB() { + ScopedTimer T1(AddObjectsTimer); - for (ObjFile *File : ObjFile::Instances) - addObjFile(File); + auto E = mergeAllOBJ(); + if (E) + fatal("Error merging OBJ: " + toString(std::move(E))); Builder.getStringTableBuilder().setStrings(PDBStrTab); T1.stop(); @@ -1416,10 +1655,14 @@ if (!Publics.empty()) { // Sort the public symbols and add them to the stream. - std::sort(Publics.begin(), Publics.end(), + sort(parallel::par, Publics.begin(), Publics.end(), + [](const PublicSym32 &L, const PublicSym32 &R) { + return L.Name < R.Name; + }); + /*std::sort(Publics.begin(), Publics.end(), [](const PublicSym32 &L, const PublicSym32 &R) { return L.Name < R.Name; - }); + });*/ for (const PublicSym32 &Pub : Publics) GsiBuilder.addPublicSymbol(Pub); } @@ -1518,7 +1761,7 @@ std::string ArgStr = quote(Args); EBS.Fields.push_back("cwd"); SmallString<64> cwd; - if (Config->PDBSourcePath.empty()) + if (Config->PDBSourcePath.empty()) sys::fs::current_path(cwd); else cwd = Config->PDBSourcePath; Index: llvm/trunk/include/llvm/DebugInfo/CodeView/GlobalTypeDenseMap.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/CodeView/GlobalTypeDenseMap.h +++ llvm/trunk/include/llvm/DebugInfo/CodeView/GlobalTypeDenseMap.h @@ -0,0 +1,466 @@ +//===- llvm/ADT/GlobalTypeDenseMap.h - Dense probed hash table ------------*- +// 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 the GlobalTypeDenseMap class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_DEBUGINFO_CODEVIEW_GLOBALTYPEDENSEMAP_H +#define LLVM_DEBUGINFO_CODEVIEW_GLOBALTYPEDENSEMAP_H + +#include "llvm/ADT/EpochTracker.h" +#include "llvm/DebugInfo/CodeView/TypeHashing.h" +#include "llvm/Support/AlignOf.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/Memory.h" +#include "llvm/Support/ReverseIteration.h" +#include "llvm/Support/type_traits.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace llvm { +namespace codeview { + +struct GloballyHashedInfo { + static unsigned getHash(uint64_t Key, unsigned BucketMask) { + return (Key >> 32) & BucketMask; + } + void packKeyValue(uint64_t Key, uint32_t Value, + unsigned BucketNo, unsigned BucketMask) { + KV = (Key & ~((uint64_t)BucketMask << 32)) | ((uint64_t)Value << 32); + //auto T = extractKeyValue(BucketNo, BucketMask); + //assert((T == std::pair(Key, Value))); + } + std::pair extractKeyValue(unsigned BucketNo, + unsigned BucketMask) const { + // SHA1 generates keys padded to 0 if the record is too short. The topmost + // 32-bits are reliable. + uint64_t K = + (KV & ~((uint64_t)BucketMask << 32)) | ((uint64_t)BucketNo << 32); + uint32_t V = (KV >> 32) & BucketMask; + return {K, V}; + } + bool isEmpty() const { return !KV; } + unsigned isEqualOrEmpty(const uint64_t Other, unsigned BucketNo, + unsigned BucketMask) const { + if (!KV) + return 2; // empty + auto Extracted = extractKeyValue(BucketNo, BucketMask); + if (Extracted.first == Other) + return 1; // equal + return 0; + } + uint64_t KV; +}; + +template +class GlobalTypeDenseMapIterator; + + template +class GlobalTypeDenseMap : public DebugEpochBase { + template + using const_arg_type_t = typename const_pointer_or_const_ref::type; + +public: + using size_type = unsigned; + using key_type = KeyT; + using mapped_type = ValueT; + using value_type = BucketT; + + using iterator = GlobalTypeDenseMapIterator; + using const_iterator = + GlobalTypeDenseMapIterator; + + inline iterator begin() { + // When the map is empty, avoid the overhead of advancing/retreating past + // empty buckets. + if (empty()) + return end(); + if (shouldReverseIterate()) + return makeIterator(getBucketsEnd() - 1, getBuckets(), *this); + return makeIterator(getBuckets(), getBucketsEnd(), *this); + } + inline iterator end() { + return makeIterator(getBucketsEnd(), getBucketsEnd(), *this, true); + } + inline const_iterator begin() const { + if (empty()) + return end(); + if (shouldReverseIterate()) + return makeConstIterator(getBucketsEnd() - 1, getBuckets(), *this); + return makeConstIterator(getBuckets(), getBucketsEnd(), *this); + } + inline const_iterator end() const { + return makeConstIterator(getBucketsEnd(), getBucketsEnd(), *this, true); + } + + LLVM_NODISCARD bool empty() const { return getNumEntries() == 0; } + unsigned size() const { return getNumEntries(); } + + /// Grow the densemap so that it can contain at least \p NumEntries items + /// before resizing again. + /*void reserve(size_type NumEntries) { + auto NumBuckets = getMinBucketToReserveForEntries(NumEntries); + incrementEpoch(); + if (NumBuckets > getNumBuckets()) + grow(NumBuckets); + }*/ + + uint64_t getBucketsMask() const { return getNumBuckets() - 1; } + + // Inserts key,value pair into the map if the key isn't already in the map. + // The value is constructed in-place if the key is not in the map, otherwise + // it is not moved. + template + std::pair try_emplace(const GloballyHashedType &Key, + const uint32_t &Value, + RehashFunc Rehash) { + uint64_t InsertKey = *(uint64_t*)const_cast(Key.Hash.data()); + + auto R = LookupBucketFor(InsertKey); + if (std::get<2>(R)) { + auto KV = + std::get<1>(R)->extractKeyValue(std::get<0>(R), getBucketsMask()); + return {KV.second, false /*already there*/}; + } + + // Otherwise, insert the new element. + InsertIntoBucket({std::get<0>(R), std::get<1>(R)}, InsertKey, Value, Rehash); + return {Value, true /*inserted*/}; + } + +protected: + + /// Returns the number of buckets to allocate to ensure that the + /// GlobalTypeDenseMap can accommodate \p NumEntries without need to grow(). + unsigned getMinBucketToReserveForEntries(unsigned NumEntries) { + // Ensure that "NumEntries * 4 < NumBuckets * 3" + if (NumEntries == 0) + return 0; + // +1 is required because of the strict equality. + // For example if NumEntries is 48, we need to return 401. + return NextPowerOf2(NumEntries * 4 / 3 + 1); + } + + /*void moveFromOldBuckets(BucketT *OldBucketsBegin, BucketT *OldBucketsEnd) { + // initEmpty(); + + const unsigned OldBucketMask = (OldBucketsEnd - OldBucketsBegin) - 1; + const unsigned NewBucketMask = (getBucketsEnd() - getBuckets()) - 1; + // Re-hash all the old elements. + for (BucketT *B = OldBucketsBegin, *E = OldBucketsEnd; B != E; ++B) { + if (!B->isEmpty()) { + // Insert the key/value into the new table. + auto KV = B->extractKeyValue(B - OldBucketsBegin, OldBucketMask); + auto R = LookupBucketFor(KV.first); + assert(!R.second && "Key already in new map?"); + R.first->packKeyValue(KV.first, KV.second, R.first - getBuckets(), NewBucketMask); + incrementNumEntries(); + } + } + }*/ + +private: + + void incrementNumEntries() { setNumEntries(getNumEntries() + 1); } + + void decrementNumEntries() { setNumEntries(getNumEntries() - 1); } + + BucketT *getBucketsEnd() { return getBuckets() + getNumBuckets(); } + + const BucketT *getBucketsEnd() const { + return getBuckets() + getNumBuckets(); + } + + template + void InsertIntoBucket(std::pair TheBucket, + const uint64_t &Key, const uint32_t &Value, + RehashFunc Rehash) { + incrementEpoch(); + + // If the load of the hash table is more than 3/4, grow the table. + // + // The later case is tricky. For example, if we had one empty bucket with + // tons of tombstones, failing lookups (e.g. for insertion) would have to + // probe almost the entire table until it found the empty bucket. If the + // table completely filled with tombstones, no lookup would ever succeed, + // causing infinite loops in lookup. + unsigned NewNumEntries = getNumEntries() + 1; + unsigned NumBuckets = getNumBuckets(); + if (LLVM_UNLIKELY(NewNumEntries * 4 >= NumBuckets * 3)) { + NumEntries = 0; + grow(NumBuckets * 2, Rehash); + auto R = LookupBucketFor(Key); + assert(!std::get<2>(R)); + TheBucket = {std::get<0>(R), std::get<1>(R)}; + } + assert(std::get<1>(TheBucket)); + + // Only update the state after we've grown our bucket space appropriately + // so that when growing buckets we have self-consistent entry count. + incrementNumEntries(); + + std::get<1>(TheBucket)->packKeyValue(Key, Value, std::get<0>(TheBucket), + getBucketsMask()); + } + + /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in + /// FoundBucket. If the bucket contains the key and a value, this returns + /// true, otherwise it returns a bucket with an empty marker or tombstone and + /// returns false. + std::tuple + LookupBucketFor(const uint64_t &Key) { + if (getNumBuckets() == 0) + return {0, nullptr, false}; + + assert(Key && "Empty value shouldn't be inserted into map!"); + + BucketT *BucketsPtr = getBuckets(); + const unsigned BucketsMask = getBucketsMask(); + unsigned BucketNo = BucketT::getHash(Key, BucketsMask); + unsigned InitialBucketNo = BucketNo; + unsigned ProbeAmt = 1; + while (true) { + BucketT *ThisBucket = BucketsPtr + BucketNo; + + if (ProbeAmt > MaxProbes) + MaxProbes = ProbeAmt; + if (ProbeAmt <= MAX_PROBES) + Probes[ProbeAmt - 1]++; + + auto R = ThisBucket->isEqualOrEmpty(Key, InitialBucketNo, BucketsMask); + if (LLVM_LIKELY(R)) { + return {InitialBucketNo, ThisBucket, + R == 1 ? true /*bucket equals provided Key*/ + : false /*bucket empty*/}; + } + + // Otherwise, it's a hash collision, continue quadratic probing. + BucketNo += ProbeAmt++; + BucketNo &= BucketsMask; + } + } + +public: + /// Return the approximate size (in bytes) of the actual map. + /// This is just the raw memory used by GlobalTypeDenseMap. + /// If entries are pointers to objects, the size of the referenced objects + /// are not included. + size_t getMemorySize() const { return getNumBuckets() * sizeof(BucketT); } + +private: + + BucketT *Buckets = nullptr; + unsigned NumEntries = 0; + unsigned NumBuckets = 0; + llvm::sys::MemoryBlock MB; + unsigned MaxProbes = 0; + enum { MAX_PROBES = 256 }; + unsigned Probes[MAX_PROBES]{}; + +public: + GlobalTypeDenseMap() { init(0); } + + ~GlobalTypeDenseMap() { + deleteBuckets(MB); + Buckets = nullptr; + NumBuckets = 0; + NumEntries = 0; + } + + void init(unsigned InitNumEntries) { + auto InitBuckets = getMinBucketToReserveForEntries(InitNumEntries); + allocateBuckets(InitBuckets); + } + + template + void grow(unsigned AtLeast, RehashFunc Rehash) { + BucketT *OldBuckets = Buckets; + unsigned NewNumBuckets = std::max( + 64, static_cast(NextPowerOf2(AtLeast - 1))); + allocateBuckets(NewNumBuckets); + assert(Buckets); + if (OldBuckets) + Rehash(); + } + +private: + unsigned getNumEntries() const { return NumEntries; } + + void setNumEntries(unsigned Num) { NumEntries = Num; } + + BucketT *getBuckets() const { return Buckets; } + + unsigned getNumBuckets() const { return NumBuckets; } + + bool allocateBuckets(unsigned Num) { + if (Num == 0) + return false; + + size_t BlockSize = sizeof(BucketT) * Num; + + if (MB.size()) { + BucketT *MBEnd = (BucketT *)((uint8_t *)MB.base() + MB.size()); + if ((Buckets + NumBuckets + Num) <= MBEnd) { + Buckets += NumBuckets; + NumBuckets = Num; + return true; + } + if (BlockSize <= MB.size()) { + ::memset(MB.base(), 0, BlockSize); + Buckets = (BucketT *)MB.base(); + NumBuckets = Num; + return true; + } + } + + deleteBuckets(MB); + + std::error_code EC; + MB = llvm::sys::Memory::allocateMappedMemory(BlockSize, nullptr, + sys::Memory::MF_READ | + sys::Memory::MF_WRITE | + llvm::sys::Memory::MF_HUGE, + EC); + Buckets = static_cast(MB.base()); + NumBuckets = Num; + return true; + } + static void deleteBuckets(llvm::sys::MemoryBlock &MB) { + if (MB.size()) { + llvm::sys::Memory::releaseMappedMemory(MB); + } + } +}; + +template +class GlobalTypeDenseMapIterator : DebugEpochBase::HandleBase { + friend class GlobalTypeDenseMapIterator; + friend class GlobalTypeDenseMapIterator; + + using ConstIterator = GlobalTypeDenseMapIterator; + +public: + using difference_type = ptrdiff_t; + using value_type = + typename std::conditional::type; + using pointer = value_type *; + using reference = value_type &; + using iterator_category = std::forward_iterator_tag; + +private: + pointer Ptr = nullptr; + pointer End = nullptr; + +public: + GlobalTypeDenseMapIterator() = default; + + GlobalTypeDenseMapIterator(pointer Pos, pointer E, + const DebugEpochBase &Epoch, + bool NoAdvance = false) + : DebugEpochBase::HandleBase(&Epoch), Ptr(Pos), End(E) { + assert(isHandleInSync() && "invalid construction!"); + + if (NoAdvance) + return; + if (shouldReverseIterate()) { + RetreatPastEmptyBuckets(); + return; + } + AdvancePastEmptyBuckets(); + } + + // Converting ctor from non-const iterators to const iterators. SFINAE'd out + // for const iterator destinations so it doesn't end up as a user defined copy + // constructor. + template ::type> + GlobalTypeDenseMapIterator( + const GlobalTypeDenseMapIterator &I) + : DebugEpochBase::HandleBase(I), Ptr(I.Ptr), End(I.End) {} + + reference operator*() const { + assert(isHandleInSync() && "invalid iterator access!"); + if (shouldReverseIterate()) + return Ptr[-1]; + return *Ptr; + } + pointer operator->() const { + assert(isHandleInSync() && "invalid iterator access!"); + if (shouldReverseIterate()) + return &(Ptr[-1]); + return Ptr; + } + + bool operator==(const ConstIterator &RHS) const { + assert((!Ptr || isHandleInSync()) && "handle not in sync!"); + assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); + assert(getEpochAddress() == RHS.getEpochAddress() && + "comparing incomparable iterators!"); + return Ptr == RHS.Ptr; + } + bool operator!=(const ConstIterator &RHS) const { + assert((!Ptr || isHandleInSync()) && "handle not in sync!"); + assert((!RHS.Ptr || RHS.isHandleInSync()) && "handle not in sync!"); + assert(getEpochAddress() == RHS.getEpochAddress() && + "comparing incomparable iterators!"); + return Ptr != RHS.Ptr; + } + + inline GlobalTypeDenseMapIterator &operator++() { // Preincrement + assert(isHandleInSync() && "invalid iterator access!"); + if (shouldReverseIterate()) { + --Ptr; + RetreatPastEmptyBuckets(); + return *this; + } + ++Ptr; + AdvancePastEmptyBuckets(); + return *this; + } + GlobalTypeDenseMapIterator operator++(int) { // Postincrement + assert(isHandleInSync() && "invalid iterator access!"); + GlobalTypeDenseMapIterator tmp = *this; + ++*this; + return tmp; + } + +private: + void AdvancePastEmptyBuckets() { + assert(Ptr <= End); + + while (Ptr != End && Ptr->isEmpty()) + ++Ptr; + } + + void RetreatPastEmptyBuckets() { + assert(Ptr >= End); + + while (Ptr != End && Ptr[-1]->isEmpty()) + --Ptr; + } +}; + +} // end namespace codeview +} // end namespace llvm + +#endif // LLVM_DEBUGINFO_CODEVIEW_GLOBALTYPEDENSEMAP_H Index: llvm/trunk/include/llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h +++ llvm/trunk/include/llvm/DebugInfo/CodeView/GlobalTypeTableBuilder.h @@ -14,6 +14,7 @@ #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/DebugInfo/CodeView/CodeView.h" +#include "llvm/DebugInfo/CodeView/GlobalTypeDenseMap.h" #include "llvm/DebugInfo/CodeView/SimpleTypeSerializer.h" #include "llvm/DebugInfo/CodeView/TypeCollection.h" #include "llvm/DebugInfo/CodeView/TypeHashing.h" @@ -24,11 +25,16 @@ #include #include +extern void startGlobalHashTimer(); +extern void stopGlobalHashTimer(); + namespace llvm { namespace codeview { class ContinuationRecordBuilder; +#define FAST_HASH + class GlobalTypeTableBuilder : public TypeCollection { /// Storage for records. These need to outlive the TypeTableBuilder. BumpPtrAllocator &RecordStorage; @@ -39,8 +45,11 @@ SimpleTypeSerializer SimpleSerializer; /// Hash table. - DenseMap HashedRecords; - +#ifdef FAST_HASH + GlobalTypeDenseMap<> HashedRecords; +#else + DenseMap HashedRecords2; +#endif /// Contains a list of all records indexed by TypeIndex.toArrayIndex(). SmallVector, 2> SeenRecords; @@ -61,7 +70,6 @@ uint32_t capacity() override; // public interface - void reset(); TypeIndex nextTypeIndex() const; BumpPtrAllocator &getAllocator() { return RecordStorage; } @@ -72,17 +80,28 @@ template TypeIndex insertRecordAs(GloballyHashedType Hash, size_t RecordSize, CreateFunc Create) { - auto Result = HashedRecords.try_emplace(Hash, nextTypeIndex()); + // startGlobalHashTimer(); +#ifdef FAST_HASH + auto R = HashedRecords.try_emplace(Hash, SeenRecords.size(), + [&]() { rehashMap(); }); +#else + auto R = HashedRecords2.try_emplace(Hash, nextTypeIndex()); + // assert(R.first == R2.first->second.getIndex()); + // assert(R.second == R2.second); +#endif + // stopGlobalHashTimer(); - if (LLVM_UNLIKELY(Result.second)) { + if (LLVM_UNLIKELY(R.second)) { uint8_t *Stable = RecordStorage.Allocate(RecordSize); MutableArrayRef Data(Stable, RecordSize); SeenRecords.push_back(Create(Data)); SeenHashes.push_back(Hash); } - - // Update the caller's copy of Record to point a stable copy. - return Result.first->second; +#ifdef FAST_HASH + return TypeIndex::fromArrayIndex(R.first); +#else + return R.first->second; +#endif } TypeIndex insertRecordBytes(ArrayRef Data); @@ -92,6 +111,9 @@ ArrayRef Data = SimpleSerializer.serialize(Record); return insertRecordBytes(Data); } + +private: + void rehashMap(); }; } // end namespace codeview Index: llvm/trunk/include/llvm/DebugInfo/CodeView/RecordSerialization.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/CodeView/RecordSerialization.h +++ llvm/trunk/include/llvm/DebugInfo/CodeView/RecordSerialization.h @@ -34,6 +34,8 @@ struct RecordPrefix { ulittle16_t RecordLen; // Record length, starting from &RecordKind. ulittle16_t RecordKind; // Record kind enum (SymRecordKind or TypeRecordKind) + + unsigned size() const { return RecordLen + sizeof(RecordKind); } }; /// Reinterpret a byte array as an array of characters. Does not interpret as Index: llvm/trunk/include/llvm/DebugInfo/CodeView/TypeHashing.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/CodeView/TypeHashing.h +++ llvm/trunk/include/llvm/DebugInfo/CodeView/TypeHashing.h @@ -106,8 +106,10 @@ /// Given a sequence of combined type and ID records, compute global hashes /// for each of them, returning the results in a vector of hashed types. template - static std::vector hashTypes(Range &&Records) { + static std::vector + hashTypes(Range &&Records, ArrayRef PrevTypeHashes = {}) { std::vector Hashes; + Hashes.insert(Hashes.end(), PrevTypeHashes.begin(), PrevTypeHashes.end()); for (const auto &R : Records) Hashes.push_back(hashType(R, Hashes, Hashes)); @@ -184,23 +186,23 @@ } }; -template <> struct format_provider { -public: - static void format(const codeview::LocallyHashedType &V, - llvm::raw_ostream &Stream, StringRef Style) { - write_hex(Stream, V.Hash, HexPrintStyle::Upper, 8); - } -}; + template <> struct format_provider { + public: + static void format(const codeview::LocallyHashedType &V, + llvm::raw_ostream &Stream, StringRef Style) { + write_hex(Stream, V.Hash, HexPrintStyle::Upper, 8); + } + }; -template <> struct format_provider { -public: - static void format(const codeview::GloballyHashedType &V, - llvm::raw_ostream &Stream, StringRef Style) { - for (uint8_t B : V.Hash) { - write_hex(Stream, B, HexPrintStyle::Upper, 2); + template <> struct format_provider { + public: + static void format(const codeview::GloballyHashedType &V, + llvm::raw_ostream &Stream, StringRef Style) { + for (uint8_t B : V.Hash) { + write_hex(Stream, B, HexPrintStyle::Upper, 2); + } } - } -}; + }; } // namespace llvm Index: llvm/trunk/include/llvm/DebugInfo/CodeView/TypeIndexDiscovery.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/CodeView/TypeIndexDiscovery.h +++ llvm/trunk/include/llvm/DebugInfo/CodeView/TypeIndexDiscovery.h @@ -19,10 +19,12 @@ namespace codeview { enum class TiRefKind { TypeRef, IndexRef }; struct TiReference { - TiRefKind Kind; - uint32_t Offset; - uint32_t Count; -}; + TiReference(TiRefKind K, unsigned O, unsigned C) + : Offset((uint16_t)O), Count((uint16_t)C), Kind(K) {} + uint16_t Offset; // cannot be more than llvm::codeview::MaxRecordLength + uint16_t Count : 15; + TiRefKind Kind : 1; +}; // namespace codeview void discoverTypeIndices(ArrayRef RecordData, SmallVectorImpl &Refs); @@ -41,7 +43,7 @@ SmallVectorImpl &Refs); bool discoverTypeIndicesInSymbol(ArrayRef RecordData, SmallVectorImpl &Indices); -} +} // namespace llvm } #endif Index: llvm/trunk/include/llvm/DebugInfo/CodeView/TypeStreamMerger.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/CodeView/TypeStreamMerger.h +++ llvm/trunk/include/llvm/DebugInfo/CodeView/TypeStreamMerger.h @@ -84,20 +84,20 @@ MergingTypeTableBuilder &DestTypes, SmallVectorImpl &SourceToDest, const CVTypeArray &IdsAndTypes, - Optional &EndPrecomp); + Optional *PCHSignature = nullptr); Error mergeTypeAndIdRecords(GlobalTypeTableBuilder &DestIds, GlobalTypeTableBuilder &DestTypes, SmallVectorImpl &SourceToDest, const CVTypeArray &IdsAndTypes, ArrayRef Hashes, - Optional &EndPrecomp); + Optional *PCHSignature = nullptr); Error mergeTypeRecords(GlobalTypeTableBuilder &Dest, SmallVectorImpl &SourceToDest, const CVTypeArray &Types, ArrayRef Hashes, - Optional &EndPrecomp); + Optional *PCHSignature = nullptr); Error mergeIdRecords(GlobalTypeTableBuilder &Dest, ArrayRef Types, SmallVectorImpl &SourceToDest, Index: llvm/trunk/include/llvm/Support/Memory.h =================================================================== --- llvm/trunk/include/llvm/Support/Memory.h +++ llvm/trunk/include/llvm/Support/Memory.h @@ -46,9 +46,12 @@ class Memory { public: enum ProtectionFlags { - MF_READ = 0x1000000, - MF_WRITE = 0x2000000, - MF_EXEC = 0x4000000 + MF_READ = 0x1000000, + MF_WRITE = 0x2000000, + MF_EXEC = 0x4000000, + MF_RWE_MASK = 0x7000000, + + MF_HUGE = 0x0000001 }; /// This method allocates a block of memory that is suitable for loading Index: llvm/trunk/lib/DebugInfo/CodeView/GlobalTypeTableBuilder.cpp =================================================================== --- llvm/trunk/lib/DebugInfo/CodeView/GlobalTypeTableBuilder.cpp +++ llvm/trunk/lib/DebugInfo/CodeView/GlobalTypeTableBuilder.cpp @@ -87,11 +87,6 @@ return SeenHashes; } -void GlobalTypeTableBuilder::reset() { - HashedRecords.clear(); - SeenRecords.clear(); -} - TypeIndex GlobalTypeTableBuilder::insertRecordBytes(ArrayRef Record) { GloballyHashedType GHT = GloballyHashedType::hashType(Record, SeenHashes, SeenHashes); @@ -112,3 +107,17 @@ TI = insertRecordBytes(C.RecordData); return TI; } + +void GlobalTypeTableBuilder::rehashMap() { +#ifdef FAST_HASH + static bool Reentrance = false; + assert(!Reentrance); + Reentrance = true; + for (size_t I = 0; I < SeenHashes.size(); ++I) { + auto R = HashedRecords.try_emplace(SeenHashes[I], I, [](){}); + (void)R; + assert(R.second /*inserted*/); + } + Reentrance = false; +#endif +} Index: llvm/trunk/lib/DebugInfo/CodeView/TypeHashing.cpp =================================================================== --- llvm/trunk/lib/DebugInfo/CodeView/TypeHashing.cpp +++ llvm/trunk/lib/DebugInfo/CodeView/TypeHashing.cpp @@ -30,12 +30,16 @@ return {llvm::hash_value(RecordData), RecordData}; } +static uint32_t MaxDiscover = 0; + GloballyHashedType GloballyHashedType::hashType(ArrayRef RecordData, ArrayRef PreviousTypes, ArrayRef PreviousIds) { - SmallVector Refs; + SmallVector Refs; discoverTypeIndices(RecordData, Refs); + if (Refs.size() > MaxDiscover) + MaxDiscover = Refs.size(); SHA1 S; S.init(); uint32_t Off = 0; Index: llvm/trunk/lib/DebugInfo/CodeView/TypeStreamMerger.cpp =================================================================== --- llvm/trunk/lib/DebugInfo/CodeView/TypeStreamMerger.cpp +++ llvm/trunk/lib/DebugInfo/CodeView/TypeStreamMerger.cpp @@ -77,8 +77,7 @@ // Local hashing entry points Error mergeTypesAndIds(MergingTypeTableBuilder &DestIds, MergingTypeTableBuilder &DestTypes, - const CVTypeArray &IdsAndTypes, - Optional &EP); + const CVTypeArray &IdsAndTypes, Optional &S); Error mergeIdRecords(MergingTypeTableBuilder &Dest, ArrayRef TypeSourceToDest, const CVTypeArray &Ids); @@ -90,14 +89,14 @@ GlobalTypeTableBuilder &DestTypes, const CVTypeArray &IdsAndTypes, ArrayRef Hashes, - Optional &EP); + Optional &S); Error mergeIdRecords(GlobalTypeTableBuilder &Dest, ArrayRef TypeSourceToDest, const CVTypeArray &Ids, ArrayRef Hashes); Error mergeTypeRecords(GlobalTypeTableBuilder &Dest, const CVTypeArray &Types, ArrayRef Hashes, - Optional &EP); + Optional &S); private: Error doit(const CVTypeArray &Types); @@ -197,7 +196,7 @@ /// its type indices. SmallVector RemapStorage; - Optional EndPrecomp; + Optional PCHSignature; }; } // end anonymous namespace @@ -275,12 +274,12 @@ Error TypeStreamMerger::mergeTypesAndIds(MergingTypeTableBuilder &DestIds, MergingTypeTableBuilder &DestTypes, const CVTypeArray &IdsAndTypes, - Optional &EP) { + Optional &S) { DestIdStream = &DestIds; DestTypeStream = &DestTypes; UseGlobalHashes = false; auto Err = doit(IdsAndTypes); - EP = EndPrecomp; + S = PCHSignature; return Err; } @@ -288,12 +287,12 @@ Error TypeStreamMerger::mergeTypeRecords(GlobalTypeTableBuilder &Dest, const CVTypeArray &Types, ArrayRef Hashes, - Optional &EP) { + Optional &S) { DestGlobalTypeStream = &Dest; UseGlobalHashes = true; GlobalHashes = Hashes; auto Err = doit(Types); - EP = EndPrecomp; + S = PCHSignature; return Err; } @@ -313,13 +312,13 @@ GlobalTypeTableBuilder &DestTypes, const CVTypeArray &IdsAndTypes, ArrayRef Hashes, - Optional &EP) { + Optional &S) { DestGlobalIdStream = &DestIds; DestGlobalTypeStream = &DestTypes; UseGlobalHashes = true; GlobalHashes = Hashes; auto Err = doit(IdsAndTypes); - EP = EndPrecomp; + S = PCHSignature; return Err; } @@ -402,7 +401,7 @@ ArrayRef TypeStreamMerger::remapIndices(const CVType &OriginalType, MutableArrayRef Storage) { - SmallVector Refs; + SmallVector Refs; discoverTypeIndices(OriginalType.RecordData, Refs); if (Refs.empty()) return OriginalType.RecordData; @@ -445,28 +444,32 @@ Error llvm::codeview::mergeTypeAndIdRecords( MergingTypeTableBuilder &DestIds, MergingTypeTableBuilder &DestTypes, SmallVectorImpl &SourceToDest, const CVTypeArray &IdsAndTypes, - Optional &EndPrecomp) { + Optional *PCHSignature) { + Optional TempPCHSignature; TypeStreamMerger M(SourceToDest); - return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes, EndPrecomp); + return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes, + PCHSignature ? *PCHSignature : TempPCHSignature); } Error llvm::codeview::mergeTypeAndIdRecords( GlobalTypeTableBuilder &DestIds, GlobalTypeTableBuilder &DestTypes, SmallVectorImpl &SourceToDest, const CVTypeArray &IdsAndTypes, - ArrayRef Hashes, - Optional &EndPrecomp) { + ArrayRef Hashes, Optional *PCHSignature) { + Optional TempPCHSignature; TypeStreamMerger M(SourceToDest); return M.mergeTypesAndIds(DestIds, DestTypes, IdsAndTypes, Hashes, - EndPrecomp); + PCHSignature ? *PCHSignature : TempPCHSignature); } Error llvm::codeview::mergeTypeRecords(GlobalTypeTableBuilder &Dest, SmallVectorImpl &SourceToDest, const CVTypeArray &Types, ArrayRef Hashes, - Optional &EndPrecomp) { + Optional *PCHSignature) { + Optional TempPCHSignature; TypeStreamMerger M(SourceToDest); - return M.mergeTypeRecords(Dest, Types, Hashes, EndPrecomp); + return M.mergeTypeRecords(Dest, Types, Hashes, + PCHSignature ? *PCHSignature : TempPCHSignature); } Error llvm::codeview::mergeIdRecords(GlobalTypeTableBuilder &Dest, @@ -483,11 +486,13 @@ // signature, through EndPrecompRecord. This is done here for performance // reasons, to avoid re-parsing the Types stream. if (Type.kind() == LF_ENDPRECOMP) { - assert(!EndPrecomp); - EndPrecomp.emplace(); + EndPrecompRecord EP; if (auto EC = TypeDeserializer::deserializeAs(const_cast(Type), - EndPrecomp.getValue())) + EP)) return joinErrors(std::move(EC), errorCorruptRecord()); + if (PCHSignature.hasValue()) + return errorCorruptRecord(); + PCHSignature.emplace(EP.getSignature()); return false; } return true; Index: llvm/trunk/lib/Support/Windows/Memory.inc =================================================================== --- llvm/trunk/lib/Support/Windows/Memory.inc +++ llvm/trunk/lib/Support/Windows/Memory.inc @@ -23,7 +23,7 @@ namespace { DWORD getWindowsProtectionFlags(unsigned Flags) { - switch (Flags) { + switch (Flags & llvm::sys::Memory::MF_RWE_MASK) { // Contrary to what you might expect, the Windows page protection flags // are not a bitwise combination of RWX values case llvm::sys::Memory::MF_READ: @@ -57,6 +57,31 @@ return Info.dwAllocationGranularity; } +size_t getLargePageSize() { + HANDLE Token = 0; + size_t LargePageMin = GetLargePageMinimum(); + if (LargePageMin) + OpenProcessToken(GetCurrentProcess(), TOKEN_ADJUST_PRIVILEGES | TOKEN_QUERY, + &Token); + if (Token) { + LUID Luid; + if (LookupPrivilegeValue(0, SE_LOCK_MEMORY_NAME, &Luid)) { + TOKEN_PRIVILEGES TP{}; + TP.PrivilegeCount = 1; + TP.Privileges[0].Luid = Luid; + TP.Privileges[0].Attributes = SE_PRIVILEGE_ENABLED; + if (AdjustTokenPrivileges(Token, FALSE, &TP, 0, 0, 0)) { + DWORD E = GetLastError(); + if (E == ERROR_SUCCESS) { + return LargePageMin; + } + } + } + CloseHandle(Token); + } + return 0; +} + } // namespace namespace llvm { @@ -87,7 +112,13 @@ GranularityCached = Granularity; } - const size_t NumBlocks = (NumBytes+Granularity-1)/Granularity; + static size_t LargePageSize = getLargePageSize(); + unsigned HugePages = ((Flags & MF_HUGE) && LargePageSize) ? MEM_LARGE_PAGES : 0; + if (HugePages) { + Granularity = LargePageSize; + } + + size_t NumBlocks = (NumBytes+Granularity-1)/Granularity; uintptr_t Start = NearBlock ? reinterpret_cast(NearBlock->base()) + NearBlock->size() @@ -99,10 +130,10 @@ Start += Granularity - Start % Granularity; DWORD Protect = getWindowsProtectionFlags(Flags); - + void *PA = ::VirtualAlloc(reinterpret_cast(Start), NumBlocks*Granularity, - MEM_RESERVE | MEM_COMMIT, Protect); + MEM_RESERVE | MEM_COMMIT | HugePages, Protect); if (PA == NULL) { if (NearBlock) { // Try again without the NearBlock hint Index: llvm/trunk/tools/llvm-readobj/COFFDumper.cpp =================================================================== --- llvm/trunk/tools/llvm-readobj/COFFDumper.cpp +++ llvm/trunk/tools/llvm-readobj/COFFDumper.cpp @@ -1248,9 +1248,7 @@ error(object_error::parse_failed); } SmallVector SourceToDest; - Optional EndPrecomp; - if (auto EC = mergeTypeAndIdRecords(CVIDs, CVTypes, SourceToDest, Types, - EndPrecomp)) + if (auto EC = mergeTypeAndIdRecords(CVIDs, CVTypes, SourceToDest, Types)) return error(std::move(EC)); } }