Re-land: "[Support] Replace HashString with djbHash."
This patch removes the HashString function from StringExtraces and
replaces its uses with calls to djbHash from DJB.h.
This change is *almost* NFC. While the algorithm is identical, the
djbHash implementation in StringExtras used 0 as its default seed while
the implementation in DJB uses 5381. The latter has been shown to result
in less collisions and improved avalanching and is used by the DWARF
accelerator tables.
Because some test were implicitly relying on the hash order, I've
reverted to using zero as a seed for the following two files:
lld/include/lld/Core/SymbolTable.h
llvm/lib/Support/StringMap.cpp
Differential revision: https://reviews.llvm.org/D43615
llvm-svn: 326091
diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp
index 8c5863e..53e09b3 100644
--- a/clang/lib/Serialization/ASTWriter.cpp
+++ b/clang/lib/Serialization/ASTWriter.cpp
@@ -82,13 +82,13 @@
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Bitcode/BitCodes.h"
#include "llvm/Bitcode/BitstreamWriter.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Compression.h"
+#include "llvm/Support/DJB.h"
#include "llvm/Support/Endian.h"
#include "llvm/Support/EndianStream.h"
#include "llvm/Support/Error.h"
@@ -453,7 +453,7 @@
Code = TYPE_DEPENDENT_SIZED_EXT_VECTOR;
}
-void
+void
ASTTypeWriter::VisitDependentAddressSpaceType(
const DependentAddressSpaceType *T) {
Record.AddTypeRef(T->getPointeeType());
@@ -661,7 +661,7 @@
SourceRange range = TL.getAttrOperandParensRange();
Record.AddSourceLocation(range.getBegin());
Record.AddSourceLocation(range.getEnd());
- Record.AddStmt(TL.getAttrExprOperand());
+ Record.AddStmt(TL.getAttrExprOperand());
}
void TypeLocWriter::VisitDependentSizedExtVectorTypeLoc(
@@ -1294,7 +1294,7 @@
RECORD(DECL_PRAGMA_COMMENT);
RECORD(DECL_PRAGMA_DETECT_MISMATCH);
RECORD(DECL_OMP_DECLARE_REDUCTION);
-
+
// Statements and Exprs can occur in the Decls and Types block.
AddStmtsExprs(Stream, Record);
@@ -1445,7 +1445,7 @@
Stream.EnterSubblock(CONTROL_BLOCK_ID, 5);
RecordData Record;
-
+
// Metadata
auto MetadataAbbrev = std::make_shared<BitCodeAbbrev>();
MetadataAbbrev->Add(BitCodeAbbrevOp(METADATA));
@@ -1912,11 +1912,11 @@
// Trait used for the on-disk hash table of header search information.
class HeaderFileInfoTrait {
ASTWriter &Writer;
-
+
// Keep track of the framework names we've used during serialization.
SmallVector<char, 128> FrameworkStringData;
llvm::StringMap<unsigned> FrameworkNameOffset;
-
+
public:
HeaderFileInfoTrait(ASTWriter &Writer) : Writer(Writer) {}
@@ -1929,7 +1929,7 @@
using UnresolvedModule =
llvm::PointerIntPair<Module *, 2, ModuleMap::ModuleHeaderRole>;
-
+
struct data_type {
const HeaderFileInfo &HFI;
ArrayRef<ModuleMap::KnownHeader> KnownHeaders;
@@ -1939,14 +1939,14 @@
using hash_value_type = unsigned;
using offset_type = unsigned;
-
+
hash_value_type ComputeHash(key_type_ref key) {
// The hash is based only on size/time of the file, so that the reader can
// match even when symlinking or excess path elements ("foo/../", "../")
// change the form of the name. However, complete path is still the key.
return llvm::hash_combine(key.Size, key.ModTime);
}
-
+
std::pair<unsigned, unsigned>
EmitKeyDataLength(raw_ostream& Out, key_type_ref key, data_type_ref Data) {
using namespace llvm::support;
@@ -1981,14 +1981,14 @@
endian::Writer<little> LE(Out);
uint64_t Start = Out.tell(); (void)Start;
-
+
unsigned char Flags = (Data.HFI.isImport << 5)
| (Data.HFI.isPragmaOnce << 4)
| (Data.HFI.DirInfo << 1)
| Data.HFI.IndexHeaderMapHeader;
LE.write<uint8_t>(Flags);
LE.write<uint16_t>(Data.HFI.NumIncludes);
-
+
if (!Data.HFI.ControllingMacro)
LE.write<uint32_t>(Data.HFI.ControllingMacroID);
else
@@ -2001,10 +2001,10 @@
= FrameworkNameOffset.find(Data.HFI.Framework);
if (Pos == FrameworkNameOffset.end()) {
Offset = FrameworkStringData.size() + 1;
- FrameworkStringData.append(Data.HFI.Framework.begin(),
+ FrameworkStringData.append(Data.HFI.Framework.begin(),
Data.HFI.Framework.end());
FrameworkStringData.push_back(0);
-
+
FrameworkNameOffset[Data.HFI.Framework] = Offset;
} else
Offset = Pos->second;
@@ -2028,14 +2028,14 @@
assert(Out.tell() - Start == DataLen && "Wrong data length");
}
-
+
const char *strings_begin() const { return FrameworkStringData.begin(); }
const char *strings_end() const { return FrameworkStringData.end(); }
};
} // namespace
-/// \brief Write the header search block for the list of files that
+/// \brief Write the header search block for the list of files that
///
/// \param HS The header search structure to save.
void ASTWriter::WriteHeaderSearch(const HeaderSearch &HS) {
@@ -2101,7 +2101,7 @@
SmallVector<const FileEntry *, 16> FilesByUID;
HS.getFileMgr().GetUniqueIDMapping(FilesByUID);
-
+
if (FilesByUID.size() > HS.header_file_size())
FilesByUID.resize(HS.header_file_size());
@@ -2163,13 +2163,13 @@
Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
unsigned TableAbbrev = Stream.EmitAbbrev(std::move(Abbrev));
-
+
// Write the header search table
RecordData::value_type Record[] = {HEADER_SEARCH_TABLE, BucketOffset,
NumHeaderSearchEntries, TableData.size()};
TableData.append(GeneratorTrait.strings_begin(),GeneratorTrait.strings_end());
Stream.EmitRecordWithBlob(TableAbbrev, Record, TableData);
-
+
// Free all of the strings we had to duplicate.
for (unsigned I = 0, N = SavedStrings.size(); I != N; ++I)
free(const_cast<char *>(SavedStrings[I]));
@@ -2269,7 +2269,7 @@
Record.push_back(InputFileIDs[Content->OrigEntry]);
Record.push_back(File.NumCreatedFIDs);
-
+
FileDeclIDsTy::iterator FDI = FileDeclIDs.find(FID);
if (FDI != FileDeclIDs.end()) {
Record.push_back(FDI->second->FirstDeclIndex);
@@ -2278,9 +2278,9 @@
Record.push_back(0);
Record.push_back(0);
}
-
+
Stream.EmitRecordWithAbbrev(SLocFileAbbrv, Record);
-
+
if (Content->BufferOverridden || Content->IsTransient)
EmitBlob = true;
} else {
@@ -2641,8 +2641,8 @@
// If the preprocessor has a preprocessing record, emit it.
unsigned NumPreprocessingRecords = 0;
using namespace llvm;
-
- // Set up the abbreviation for
+
+ // Set up the abbreviation for
unsigned InclusionAbbrev = 0;
{
auto Abbrev = std::make_shared<BitCodeAbbrev>();
@@ -2654,15 +2654,15 @@
Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
InclusionAbbrev = Stream.EmitAbbrev(std::move(Abbrev));
}
-
- unsigned FirstPreprocessorEntityID
- = (Chain ? PPRec.getNumLoadedPreprocessedEntities() : 0)
+
+ unsigned FirstPreprocessorEntityID
+ = (Chain ? PPRec.getNumLoadedPreprocessedEntities() : 0)
+ NUM_PREDEF_PP_ENTITY_IDS;
unsigned NextPreprocessorEntityID = FirstPreprocessorEntityID;
RecordData Record;
for (PreprocessingRecord::iterator E = PPRec.local_begin(),
EEnd = PPRec.local_end();
- E != EEnd;
+ E != EEnd;
(void)++E, ++NumPreprocessingRecords, ++NextPreprocessorEntityID) {
Record.clear();
@@ -2703,7 +2703,7 @@
Stream.EmitRecordWithBlob(InclusionAbbrev, Record, Buffer);
continue;
}
-
+
llvm_unreachable("Unhandled PreprocessedEntity in ASTWriter");
}
Stream.ExitBlock();
@@ -2783,14 +2783,14 @@
for (auto Sub = Mod->submodule_begin(), SubEnd = Mod->submodule_end();
Sub != SubEnd; ++Sub)
ChildModules += getNumberOfModules(*Sub);
-
+
return ChildModules + 1;
}
void ASTWriter::WriteSubmodules(Module *WritingModule) {
// Enter the submodule description block.
Stream.EnterSubblock(SUBMODULE_BLOCK_ID, /*bits for abbreviations*/5);
-
+
// Write the abbreviations needed for the submodules block.
using namespace llvm;
@@ -2883,7 +2883,7 @@
getNumberOfModules(WritingModule),
FirstSubmoduleID - NUM_PREDEF_SUBMODULE_IDS};
Stream.EmitRecord(SUBMODULE_METADATA, Record);
-
+
// Write all of the submodules.
std::queue<Module *> Q;
Q.push(WritingModule);
@@ -2959,7 +2959,7 @@
Stream.EmitRecordWithBlob(TopHeaderAbbrev, Record, H->getName());
}
- // Emit the imports.
+ // Emit the imports.
if (!Mod->Imports.empty()) {
RecordData Record;
for (auto *I : Mod->Imports)
@@ -2967,7 +2967,7 @@
Stream.EmitRecord(SUBMODULE_IMPORTS, Record);
}
- // Emit the exports.
+ // Emit the exports.
if (!Mod->Exports.empty()) {
RecordData Record;
for (const auto &E : Mod->Exports) {
@@ -3017,12 +3017,12 @@
RecordData::value_type Record[] = {SUBMODULE_EXPORT_AS};
Stream.EmitRecordWithBlob(ExportAsAbbrev, Record, Mod->ExportAsModule);
}
-
+
// Queue up the submodules of this module.
for (auto *M : Mod->submodules())
Q.push(M);
}
-
+
Stream.ExitBlock();
assert((NextSubmoduleID - FirstSubmoduleID ==
@@ -3061,7 +3061,7 @@
unsigned &DiagStateID = DiagStateIDMap[State];
Record.push_back(DiagStateID);
-
+
if (DiagStateID == 0) {
DiagStateID = ++CurrID;
@@ -3546,7 +3546,7 @@
bool IsModule;
bool NeedDecls;
ASTWriter::RecordData *InterestingIdentifierOffsets;
-
+
/// \brief Determines whether this is an "interesting" identifier that needs a
/// full IdentifierInfo structure written into the hash table. Notably, this
/// doesn't check whether the name has macros defined; use PublicMacroIterator
@@ -3582,7 +3582,7 @@
bool needDecls() const { return NeedDecls; }
static hash_value_type ComputeHash(const IdentifierInfo* II) {
- return llvm::HashString(II->getName());
+ return llvm::djbHash(II->getName());
}
bool isInterestingIdentifier(const IdentifierInfo *II) {
@@ -3694,7 +3694,7 @@
/// The identifier table consists of a blob containing string data
/// (the actual identifiers themselves) and a separate "offsets" index
/// that maps identifier IDs to locations within the blob.
-void ASTWriter::WriteIdentifierTable(Preprocessor &PP,
+void ASTWriter::WriteIdentifierTable(Preprocessor &PP,
IdentifierResolver &IdResolver,
bool IsModule) {
using namespace llvm;
@@ -4298,16 +4298,16 @@
void ASTWriter::WriteObjCCategories() {
SmallVector<ObjCCategoriesInfo, 2> CategoriesMap;
RecordData Categories;
-
+
for (unsigned I = 0, N = ObjCClassesWithCategories.size(); I != N; ++I) {
unsigned Size = 0;
unsigned StartIndex = Categories.size();
-
+
ObjCInterfaceDecl *Class = ObjCClassesWithCategories[I];
-
+
// Allocate space for the size.
Categories.push_back(0);
-
+
// Add the categories.
for (ObjCInterfaceDecl::known_categories_iterator
Cat = Class->known_categories_begin(),
@@ -4316,10 +4316,10 @@
assert(getDeclID(*Cat) != 0 && "Bogus category");
AddDeclRef(*Cat, Categories);
}
-
+
// Update the size.
Categories[StartIndex] = Size;
-
+
// Record this interface -> category map.
ObjCCategoriesInfo CatInfo = { getDeclID(Class), StartIndex };
CategoriesMap.push_back(CatInfo);
@@ -4579,7 +4579,7 @@
WritingAST = true;
ASTHasCompilerErrors = hasErrors;
-
+
// Emit the file header.
Stream.Emit((unsigned)'C', 8);
Stream.Emit((unsigned)'P', 8);
@@ -4627,7 +4627,7 @@
// Make sure that the AST reader knows to finalize itself.
if (Chain)
Chain->finalizeForWriting();
-
+
ASTContext &Context = SemaRef.Context;
Preprocessor &PP = SemaRef.PP;
@@ -4668,7 +4668,7 @@
// headers.
RecordData TentativeDefinitions;
AddLazyVectorDecls(*this, SemaRef.TentativeDefinitions, TentativeDefinitions);
-
+
// Build a record containing all of the file scoped decls in this file.
RecordData UnusedFileScopedDecls;
if (!isModule)
@@ -4789,7 +4789,7 @@
NewGlobalKindDeclPairs.push_back(GetDeclRef(D));
}
}
-
+
auto Abv = std::make_shared<BitCodeAbbrev>();
Abv->Add(llvm::BitCodeAbbrevOp(TU_UPDATE_LEXICAL));
Abv->Add(llvm::BitCodeAbbrevOp(llvm::BitCodeAbbrevOp::Blob));
@@ -4811,7 +4811,7 @@
// If we have any extern "C" names, write out a visible update for them.
if (Context.ExternCContext)
WriteDeclContextVisibleUpdate(Context.ExternCContext);
-
+
// If the translation unit has an anonymous namespace, and we don't already
// have an update block for it, write it as an update block.
// FIXME: Why do we not do this if there's already an update block?
@@ -4900,7 +4900,7 @@
// declaration-id:i32
// c++-base-specifiers-id:i32
// type-id:i32)
- //
+ //
// module-kind is the ModuleKind enum value. If it is MK_PrebuiltModule or
// MK_ExplicitModule, then the module-name is the module name. Otherwise,
// it is the module file name.
@@ -4994,7 +4994,7 @@
WriteOpenCLExtensionDecls(SemaRef);
WriteCUDAPragmas(SemaRef);
- // If we're emitting a module, write out the submodule information.
+ // If we're emitting a module, write out the submodule information.
if (WritingModule)
WriteSubmodules(WritingModule);
@@ -5044,7 +5044,7 @@
// Write the record containing CUDA-specific declaration references.
if (!CUDASpecialDeclRefs.empty())
Stream.EmitRecord(CUDA_SPECIAL_DECL_REFS, CUDASpecialDeclRefs);
-
+
// Write the delegating constructors.
if (!DelegatingCtorDecls.empty())
Stream.EmitRecord(DELEGATING_CTORS, DelegatingCtorDecls);
@@ -5347,7 +5347,7 @@
MacroID ASTWriter::getMacroID(MacroInfo *MI) {
if (!MI || MI->isBuiltinMacro())
return 0;
-
+
assert(MacroIDs.find(MI) != MacroIDs.end() && "Macro not emitted!");
return MacroIDs[MI];
}
@@ -5491,12 +5491,12 @@
if (!D) {
return 0;
}
-
+
// If D comes from an AST file, its declaration ID is already known and
// fixed.
if (D->isFromASTFile())
return D->getGlobalID();
-
+
assert(!(reinterpret_cast<uintptr_t>(D) & 0x01) && "Invalid decl pointer");
DeclID &ID = DeclIDs[D];
if (ID == 0) {
@@ -5818,7 +5818,7 @@
AddTemplateName(subst->getReplacement());
break;
}
-
+
case TemplateName::SubstTemplateTemplateParmPack: {
SubstTemplateTemplateParmPackStorage *SubstPack
= Name.getAsSubstTemplateTemplateParmPack();
@@ -5918,7 +5918,7 @@
Record->push_back(Base.getInheritConstructors());
AddTypeSourceInfo(Base.getTypeSourceInfo());
AddSourceRange(Base.getSourceRange());
- AddSourceLocation(Base.isPackExpansion()? Base.getEllipsisLoc()
+ AddSourceLocation(Base.isPackExpansion()? Base.getEllipsisLoc()
: SourceLocation());
}
@@ -6052,9 +6052,9 @@
AddUnresolvedSet(Data.Conversions.get(*Writer->Context));
AddUnresolvedSet(Data.VisibleConversions.get(*Writer->Context));
- // Data.Definition is the owning decl, no need to write it.
+ // Data.Definition is the owning decl, no need to write it.
AddDeclRef(D->getFirstFriend());
-
+
// Add lambda-specific data.
if (Data.IsLambda) {
auto &Lambda = D->getLambdaData();
@@ -6347,7 +6347,7 @@
assert(!WritingAST && "Already writing the AST!");
if (!IFD->isFromASTFile())
return; // Declaration not imported from PCH.
-
+
assert(IFD->getDefinition() && "Category on a class without a definition?");
ObjCClassesWithCategories.insert(
const_cast<ObjCInterfaceDecl *>(IFD->getDefinition()));