X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FAsmPrinter%2FDwarfAccelTable.cpp;h=f8cdde203187e9e5089b2a5d65787f2cc067c7de;hb=7ddee6601d49dc82ddf77910590a3f8acd12b5c5;hp=c1939992cd3888d07654f708edaf61f6ed98a68d;hpb=72c1655e0af6c87ffe687bed1f4ed263b1165c06;p=oota-llvm.git diff --git a/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp b/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp index c1939992cd3..f8cdde20318 100644 --- a/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp +++ b/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp @@ -12,11 +12,12 @@ //===----------------------------------------------------------------------===// #include "DwarfAccelTable.h" -#include "DIE.h" +#include "DwarfCompileUnit.h" #include "DwarfDebug.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Twine.h" #include "llvm/CodeGen/AsmPrinter.h" +#include "llvm/CodeGen/DIE.h" #include "llvm/MC/MCExpr.h" #include "llvm/MC/MCStreamer.h" #include "llvm/MC/MCSymbol.h" @@ -24,32 +25,20 @@ using namespace llvm; -const char *DwarfAccelTable::Atom::AtomTypeString(enum AtomType AT) { - switch (AT) { - case eAtomTypeNULL: return "eAtomTypeNULL"; - case eAtomTypeDIEOffset: return "eAtomTypeDIEOffset"; - case eAtomTypeCUOffset: return "eAtomTypeCUOffset"; - case eAtomTypeTag: return "eAtomTypeTag"; - case eAtomTypeNameFlags: return "eAtomTypeNameFlags"; - case eAtomTypeTypeFlags: return "eAtomTypeTypeFlags"; - } - llvm_unreachable("invalid AtomType!"); -} - // The length of the header data is always going to be 4 + 4 + 4*NumAtoms. -DwarfAccelTable::DwarfAccelTable(ArrayRef atomList) : - Header(8 + (atomList.size() * 4)), - HeaderData(atomList), - Entries(Allocator) { } - -DwarfAccelTable::~DwarfAccelTable() { } +DwarfAccelTable::DwarfAccelTable(ArrayRef atomList) + : Header(8 + (atomList.size() * 4)), HeaderData(atomList), + Entries(Allocator) {} -void DwarfAccelTable::AddName(StringRef Name, DIE* die, char Flags) { +void DwarfAccelTable::AddName(DwarfStringPoolEntryRef Name, const DIE *die, + char Flags) { assert(Data.empty() && "Already finalized!"); // If the string is in the list already then add this die to the list // otherwise add a new one. - DataArray &DIEs = Entries[Name]; - DIEs.push_back(new (Allocator) HashDataContents(die, Flags)); + DataArray &DIEs = Entries[Name.getString()]; + assert(!DIEs.Name || DIEs.Name == Name); + DIEs.Name = Name; + DIEs.Values.push_back(new (Allocator) HashDataContents(die, Flags)); } void DwarfAccelTable::ComputeBucketCount(void) { @@ -59,13 +48,16 @@ void DwarfAccelTable::ComputeBucketCount(void) { uniques[i] = Data[i]->HashValue; array_pod_sort(uniques.begin(), uniques.end()); std::vector::iterator p = - std::unique(uniques.begin(), uniques.end()); + std::unique(uniques.begin(), uniques.end()); uint32_t num = std::distance(uniques.begin(), p); // Then compute the bucket size, minimum of 1 bucket. - if (num > 1024) Header.bucket_count = num/4; - if (num > 16) Header.bucket_count = num/2; - else Header.bucket_count = num > 0 ? num : 1; + if (num > 1024) + Header.bucket_count = num / 4; + else if (num > 16) + Header.bucket_count = num / 2; + else + Header.bucket_count = num > 0 ? num : 1; Header.hashes_count = num; } @@ -76,15 +68,17 @@ static bool compareDIEs(const DwarfAccelTable::HashDataContents *A, return A->Die->getOffset() < B->Die->getOffset(); } -void DwarfAccelTable::FinalizeTable(AsmPrinter *Asm, const char *Prefix) { +void DwarfAccelTable::FinalizeTable(AsmPrinter *Asm, StringRef Prefix) { // Create the individual hash data outputs. - for (StringMap::iterator - EI = Entries.begin(), EE = Entries.end(); EI != EE; ++EI) { + Data.reserve(Entries.size()); + for (StringMap::iterator EI = Entries.begin(), EE = Entries.end(); + EI != EE; ++EI) { // Unique the entries. - std::stable_sort(EI->second.begin(), EI->second.end(), compareDIEs); - EI->second.erase(std::unique(EI->second.begin(), EI->second.end()), - EI->second.end()); + std::stable_sort(EI->second.Values.begin(), EI->second.Values.end(), compareDIEs); + EI->second.Values.erase( + std::unique(EI->second.Values.begin(), EI->second.Values.end()), + EI->second.Values.end()); HashData *Entry = new (Allocator) HashData(EI->getKey(), EI->second); Data.push_back(Entry); @@ -102,33 +96,42 @@ void DwarfAccelTable::FinalizeTable(AsmPrinter *Asm, const char *Prefix) { for (size_t i = 0, e = Data.size(); i < e; ++i) { uint32_t bucket = Data[i]->HashValue % Header.bucket_count; Buckets[bucket].push_back(Data[i]); - Data[i]->Sym = Asm->GetTempSymbol(Prefix, i); + Data[i]->Sym = Asm->createTempSymbol(Prefix); } + + // Sort the contents of the buckets by hash value so that hash + // collisions end up together. Stable sort makes testing easier and + // doesn't cost much more. + for (size_t i = 0; i < Buckets.size(); ++i) + std::stable_sort(Buckets[i].begin(), Buckets[i].end(), + [] (HashData *LHS, HashData *RHS) { + return LHS->HashValue < RHS->HashValue; + }); } // Emits the header for the table via the AsmPrinter. void DwarfAccelTable::EmitHeader(AsmPrinter *Asm) { - Asm->OutStreamer.AddComment("Header Magic"); + Asm->OutStreamer->AddComment("Header Magic"); Asm->EmitInt32(Header.magic); - Asm->OutStreamer.AddComment("Header Version"); + Asm->OutStreamer->AddComment("Header Version"); Asm->EmitInt16(Header.version); - Asm->OutStreamer.AddComment("Header Hash Function"); + Asm->OutStreamer->AddComment("Header Hash Function"); Asm->EmitInt16(Header.hash_function); - Asm->OutStreamer.AddComment("Header Bucket Count"); + Asm->OutStreamer->AddComment("Header Bucket Count"); Asm->EmitInt32(Header.bucket_count); - Asm->OutStreamer.AddComment("Header Hash Count"); + Asm->OutStreamer->AddComment("Header Hash Count"); Asm->EmitInt32(Header.hashes_count); - Asm->OutStreamer.AddComment("Header Data Length"); + Asm->OutStreamer->AddComment("Header Data Length"); Asm->EmitInt32(Header.header_data_len); - Asm->OutStreamer.AddComment("HeaderData Die Offset Base"); + Asm->OutStreamer->AddComment("HeaderData Die Offset Base"); Asm->EmitInt32(HeaderData.die_offset_base); - Asm->OutStreamer.AddComment("HeaderData Atom Count"); + Asm->OutStreamer->AddComment("HeaderData Atom Count"); Asm->EmitInt32(HeaderData.Atoms.size()); for (size_t i = 0; i < HeaderData.Atoms.size(); i++) { Atom A = HeaderData.Atoms[i]; - Asm->OutStreamer.AddComment(Atom::AtomTypeString(A.type)); + Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.type)); Asm->EmitInt16(A.type); - Asm->OutStreamer.AddComment(dwarf::FormEncodingString(A.form)); + Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.form)); Asm->EmitInt16(A.form); } } @@ -138,23 +141,37 @@ void DwarfAccelTable::EmitHeader(AsmPrinter *Asm) { void DwarfAccelTable::EmitBuckets(AsmPrinter *Asm) { unsigned index = 0; for (size_t i = 0, e = Buckets.size(); i < e; ++i) { - Asm->OutStreamer.AddComment("Bucket " + Twine(i)); + Asm->OutStreamer->AddComment("Bucket " + Twine(i)); if (Buckets[i].size() != 0) Asm->EmitInt32(index); else Asm->EmitInt32(UINT32_MAX); - index += Buckets[i].size(); + // Buckets point in the list of hashes, not to the data. Do not + // increment the index multiple times in case of hash collisions. + uint64_t PrevHash = UINT64_MAX; + for (auto *HD : Buckets[i]) { + uint32_t HashValue = HD->HashValue; + if (PrevHash != HashValue) + ++index; + PrevHash = HashValue; + } } } // Walk through the buckets and emit the individual hashes for each // bucket. void DwarfAccelTable::EmitHashes(AsmPrinter *Asm) { + uint64_t PrevHash = UINT64_MAX; for (size_t i = 0, e = Buckets.size(); i < e; ++i) { for (HashList::const_iterator HI = Buckets[i].begin(), - HE = Buckets[i].end(); HI != HE; ++HI) { - Asm->OutStreamer.AddComment("Hash in Bucket " + Twine(i)); - Asm->EmitInt32((*HI)->HashValue); + HE = Buckets[i].end(); + HI != HE; ++HI) { + uint32_t HashValue = (*HI)->HashValue; + if (PrevHash == HashValue) + continue; + Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(i)); + Asm->EmitInt32(HashValue); + PrevHash = HashValue; } } } @@ -163,17 +180,22 @@ void DwarfAccelTable::EmitHashes(AsmPrinter *Asm) { // element in each bucket. This is done via a symbol subtraction from the // beginning of the section. The non-section symbol will be output later // when we emit the actual data. -void DwarfAccelTable::EmitOffsets(AsmPrinter *Asm, MCSymbol *SecBegin) { +void DwarfAccelTable::emitOffsets(AsmPrinter *Asm, const MCSymbol *SecBegin) { + uint64_t PrevHash = UINT64_MAX; for (size_t i = 0, e = Buckets.size(); i < e; ++i) { for (HashList::const_iterator HI = Buckets[i].begin(), - HE = Buckets[i].end(); HI != HE; ++HI) { - Asm->OutStreamer.AddComment("Offset in Bucket " + Twine(i)); - MCContext &Context = Asm->OutStreamer.getContext(); - const MCExpr *Sub = - MCBinaryExpr::CreateSub(MCSymbolRefExpr::Create((*HI)->Sym, Context), - MCSymbolRefExpr::Create(SecBegin, Context), - Context); - Asm->OutStreamer.EmitValue(Sub, sizeof(uint32_t), 0); + HE = Buckets[i].end(); + HI != HE; ++HI) { + uint32_t HashValue = (*HI)->HashValue; + if (PrevHash == HashValue) + continue; + PrevHash = HashValue; + Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i)); + MCContext &Context = Asm->OutStreamer->getContext(); + const MCExpr *Sub = MCBinaryExpr::createSub( + MCSymbolRefExpr::create((*HI)->Sym, Context), + MCSymbolRefExpr::create(SecBegin, Context), Context); + Asm->OutStreamer->EmitValue(Sub, sizeof(uint32_t)); } } } @@ -181,41 +203,45 @@ void DwarfAccelTable::EmitOffsets(AsmPrinter *Asm, MCSymbol *SecBegin) { // Walk through the buckets and emit the full data for each element in // the bucket. For the string case emit the dies and the various offsets. // Terminate each HashData bucket with 0. -void DwarfAccelTable::EmitData(AsmPrinter *Asm, DwarfUnits *D) { - uint64_t PrevHash = UINT64_MAX; +void DwarfAccelTable::EmitData(AsmPrinter *Asm, DwarfDebug *D) { for (size_t i = 0, e = Buckets.size(); i < e; ++i) { + uint64_t PrevHash = UINT64_MAX; for (HashList::const_iterator HI = Buckets[i].begin(), - HE = Buckets[i].end(); HI != HE; ++HI) { + HE = Buckets[i].end(); + HI != HE; ++HI) { + // Terminate the previous entry if there is no hash collision + // with the current one. + if (PrevHash != UINT64_MAX && PrevHash != (*HI)->HashValue) + Asm->EmitInt32(0); // Remember to emit the label for our offset. - Asm->OutStreamer.EmitLabel((*HI)->Sym); - Asm->OutStreamer.AddComment((*HI)->Str); - Asm->EmitSectionOffset(D->getStringPoolEntry((*HI)->Str), - D->getStringPoolSym()); - Asm->OutStreamer.AddComment("Num DIEs"); - Asm->EmitInt32((*HI)->Data.size()); - for (ArrayRef::const_iterator - DI = (*HI)->Data.begin(), DE = (*HI)->Data.end(); - DI != DE; ++DI) { + Asm->OutStreamer->EmitLabel((*HI)->Sym); + Asm->OutStreamer->AddComment((*HI)->Str); + Asm->emitDwarfStringOffset((*HI)->Data.Name); + Asm->OutStreamer->AddComment("Num DIEs"); + Asm->EmitInt32((*HI)->Data.Values.size()); + for (HashDataContents *HD : (*HI)->Data.Values) { // Emit the DIE offset - Asm->EmitInt32((*DI)->Die->getOffset()); + DwarfCompileUnit *CU = D->lookupUnit(HD->Die->getUnit()); + assert(CU && "Accelerated DIE should belong to a CU."); + Asm->EmitInt32(HD->Die->getOffset() + CU->getDebugInfoOffset()); // If we have multiple Atoms emit that info too. // FIXME: A bit of a hack, we either emit only one atom or all info. if (HeaderData.Atoms.size() > 1) { - Asm->EmitInt16((*DI)->Die->getTag()); - Asm->EmitInt8((*DI)->Flags); + Asm->EmitInt16(HD->Die->getTag()); + Asm->EmitInt8(HD->Flags); } } - // Emit a 0 to terminate the data unless we have a hash collision. - if (PrevHash != (*HI)->HashValue) - Asm->EmitInt32(0); PrevHash = (*HI)->HashValue; } + // Emit the final end marker for the bucket. + if (!Buckets[i].empty()) + Asm->EmitInt32(0); } } // Emit the entire data structure to the output file. -void DwarfAccelTable::Emit(AsmPrinter *Asm, MCSymbol *SecBegin, - DwarfUnits *D) { +void DwarfAccelTable::emit(AsmPrinter *Asm, const MCSymbol *SecBegin, + DwarfDebug *D) { // Emit the header. EmitHeader(Asm); @@ -226,7 +252,7 @@ void DwarfAccelTable::Emit(AsmPrinter *Asm, MCSymbol *SecBegin, EmitHashes(Asm); // Emit the offsets. - EmitOffsets(Asm, SecBegin); + emitOffsets(Asm, SecBegin); // Emit the hash data. EmitData(Asm, D); @@ -239,26 +265,25 @@ void DwarfAccelTable::print(raw_ostream &O) { HeaderData.print(O); O << "Entries: \n"; - for (StringMap::const_iterator - EI = Entries.begin(), EE = Entries.end(); EI != EE; ++EI) { + for (StringMap::const_iterator EI = Entries.begin(), + EE = Entries.end(); + EI != EE; ++EI) { O << "Name: " << EI->getKeyData() << "\n"; - for (DataArray::const_iterator DI = EI->second.begin(), - DE = EI->second.end(); - DI != DE; ++DI) - (*DI)->print(O); + for (HashDataContents *HD : EI->second.Values) + HD->print(O); } O << "Buckets and Hashes: \n"; for (size_t i = 0, e = Buckets.size(); i < e; ++i) for (HashList::const_iterator HI = Buckets[i].begin(), - HE = Buckets[i].end(); HI != HE; ++HI) + HE = Buckets[i].end(); + HI != HE; ++HI) (*HI)->print(O); O << "Data: \n"; - for (std::vector::const_iterator - DI = Data.begin(), DE = Data.end(); DI != DE; ++DI) - (*DI)->print(O); - - + for (std::vector::const_iterator DI = Data.begin(), + DE = Data.end(); + DI != DE; ++DI) + (*DI)->print(O); } #endif