X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FAsmPrinter%2FDwarfAccelTable.cpp;h=4ad3e1867328f242c10bc27eeb62f169ac3c87e6;hb=3808efa2e6e2da057c29c4fdc4ef083a244f9371;hp=370d42ab68e672589131c05a29a715f93af69394;hpb=7eabae3f50d43af1b76f2bcc5ac6c47700d12b8b;p=oota-llvm.git diff --git a/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp b/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp index 370d42ab68e..4ad3e186732 100644 --- a/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp +++ b/lib/CodeGen/AsmPrinter/DwarfAccelTable.cpp @@ -11,104 +11,76 @@ // //===----------------------------------------------------------------------===// +#include "DwarfAccelTable.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" #include "llvm/Support/Debug.h" -#include "DwarfAccelTable.h" -#include "DwarfDebug.h" -#include "DIE.h" using namespace llvm; -const char *DwarfAccelTable::Atom::AtomTypeString(enum AtomType AT) { - switch (AT) { - default: llvm_unreachable("invalid AtomType!"); - case eAtomTypeNULL: return "eAtomTypeNULL"; - case eAtomTypeDIEOffset: return "eAtomTypeDIEOffset"; - case eAtomTypeCUOffset: return "eAtomTypeCUOffset"; - case eAtomTypeTag: return "eAtomTypeTag"; - case eAtomTypeNameFlags: return "eAtomTypeNameFlags"; - case eAtomTypeTypeFlags: return "eAtomTypeTypeFlags"; - } -} - -// The general case would need to have a less hard coded size for the -// length of the HeaderData, however, if we're constructing based on a -// single Atom then we know it will always be: 4 + 4 + 2 + 2. -DwarfAccelTable::DwarfAccelTable(DwarfAccelTable::Atom atom) : - Header(12), - HeaderData(atom) { -} - // The length of the header data is always going to be 4 + 4 + 4*NumAtoms. -DwarfAccelTable::DwarfAccelTable(std::vector &atomList) : - Header(8 + (atomList.size() * 4)), - HeaderData(atomList) { -} - -DwarfAccelTable::~DwarfAccelTable() { - for (size_t i = 0, e = Data.size(); i < e; ++i) - delete Data[i]; - for (StringMap::iterator - EI = Entries.begin(), EE = Entries.end(); EI != EE; ++EI) - for (DataArray::iterator DI = (*EI).second.begin(), - DE = (*EI).second.end(); DI != DE; ++DI) - delete (*DI); -} +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 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) { +void DwarfAccelTable::ComputeBucketCount() { // First get the number of unique hashes. - std::vector uniques; - uniques.resize(Data.size()); + std::vector uniques(Data.size()); for (size_t i = 0, e = Data.size(); i < e; ++i) uniques[i] = Data[i]->HashValue; - std::stable_sort(uniques.begin(), uniques.end()); + 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; } -namespace { - // DIESorter - comparison predicate that sorts DIEs by their offset. - struct DIESorter { - bool operator()(const struct DwarfAccelTable::HashDataContents *A, - const struct DwarfAccelTable::HashDataContents *B) const { - return A->Die->getOffset() < B->Die->getOffset(); - } - }; +// compareDIEs - comparison predicate that sorts DIEs by their offset. +static bool compareDIEs(const DwarfAccelTable::HashDataContents *A, + const DwarfAccelTable::HashDataContents *B) { + 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) { - struct HashData *Entry = new HashData((*EI).getKeyData()); + 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(), DIESorter()); - (*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()); - for (DataArray::const_iterator DI = (*EI).second.begin(), - DE = (*EI).second.end(); - DI != DE; ++DI) - Entry->addData((*DI)); + HashData *Entry = new (Allocator) HashData(EI->getKey(), EI->second); Data.push_back(Entry); } @@ -124,60 +96,83 @@ 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); } } -// Walk through and emit the buckets for the table. This will look -// like a list of numbers of how many elements are in each bucket. +// Walk through and emit the buckets for the table. Each index is +// an offset into the list of hashes. 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; + } } } @@ -185,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)); } } } @@ -204,39 +204,43 @@ void DwarfAccelTable::EmitOffsets(AsmPrinter *Asm, MCSymbol *SecBegin) { // the bucket. For the string case emit the dies and the various offsets. // Terminate each HashData bucket with 0. void DwarfAccelTable::EmitData(AsmPrinter *Asm, DwarfDebug *D) { - uint64_t PrevHash = UINT64_MAX; 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->getStringPool()); - Asm->OutStreamer.AddComment("Num DIEs"); - Asm->EmitInt32((*HI)->Data.size()); - for (std::vector::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, +void DwarfAccelTable::emit(AsmPrinter *Asm, const MCSymbol *SecBegin, DwarfDebug *D) { // Emit the header. EmitHeader(Asm); @@ -248,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); @@ -261,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) { - O << "Name: " << (*EI).getKeyData() << "\n"; - for (DataArray::const_iterator DI = (*EI).second.begin(), - DE = (*EI).second.end(); - DI != DE; ++DI) - (*DI)->print(O); + for (StringMap::const_iterator EI = Entries.begin(), + EE = Entries.end(); + EI != EE; ++EI) { + O << "Name: " << EI->getKeyData() << "\n"; + 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