Index: include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h =================================================================== --- include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h +++ include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h @@ -31,13 +31,14 @@ /// Offset within the .debug_info of the start of this entry. uint32_t Offset; - /// How many to add to "this" to get the sibling. - uint32_t SiblingIdx; + /// The integer depth of this DIE within the compile unit DIEs where the + /// compile/type unit DIE has a depth of zero. + uint32_t Depth; const DWARFAbbreviationDeclaration *AbbrevDecl; public: DWARFDebugInfoEntry() - : Offset(0), SiblingIdx(0), AbbrevDecl(nullptr) {} + : Offset(0), Depth(0), AbbrevDecl(nullptr) {} /// Extracts a debug info entry, which is a child of a given unit, /// starting at a given offset. If DIE can't be extracted, returns false and @@ -45,33 +46,16 @@ bool extractFast(const DWARFUnit &U, uint32_t *OffsetPtr); /// High performance extraction should use this call. bool extractFast(const DWARFUnit &U, uint32_t *OffsetPtr, - const DataExtractor &DebugInfoData, uint32_t UEndOffset); + const DataExtractor &DebugInfoData, + uint32_t UEndOffset, + uint32_t Depth); uint32_t getOffset() const { return Offset; } + uint32_t getDepth() const { return Depth; } + dwarf::Tag getTag() const { + return AbbrevDecl ? AbbrevDecl->getTag() : dwarf::DW_TAG_null; + } bool hasChildren() const { return AbbrevDecl && AbbrevDecl->hasChildren(); } - - // We know we are kept in a vector of contiguous entries, so we know - // our sibling will be some index after "this". - const DWARFDebugInfoEntry *getSibling() const { - return SiblingIdx > 0 ? this + SiblingIdx : nullptr; - } - - // We know we are kept in a vector of contiguous entries, so we know - // we don't need to store our child pointer, if we have a child it will - // be the next entry in the list... - const DWARFDebugInfoEntry *getFirstChild() const { - return hasChildren() ? this + 1 : nullptr; - } - - void setSibling(const DWARFDebugInfoEntry *Sibling) { - if (Sibling) { - // We know we are kept in a vector of contiguous entries, so we know - // our sibling will be some index after "this". - SiblingIdx = Sibling - this; - } else - SiblingIdx = 0; - } - const DWARFAbbreviationDeclaration *getAbbreviationDeclarationPtr() const { return AbbrevDecl; } Index: include/llvm/DebugInfo/DWARF/DWARFDie.h =================================================================== --- include/llvm/DebugInfo/DWARF/DWARFDie.h +++ include/llvm/DebugInfo/DWARF/DWARFDie.h @@ -82,23 +82,26 @@ /// Returns true if DIE represents a subprogram or an inlined subroutine. bool isSubroutineDIE() const; - - /// Get the silbing of this DIE object. + /// Get the parent of this DIE object. /// + /// \returns a valid DWARFDie instance if this object has a parent or an + /// invalid DWARFDie instance if it doesn't. + DWARFDie getParent() const; + + /// Get the sibling of this DIE object. + /// /// \returns a valid DWARFDie instance if this object has a sibling or an /// invalid DWARFDie instance if it doesn't. - DWARFDie getSibling() const { - assert(isValid() && "must check validity prior to calling"); - return DWARFDie(U, Die->getSibling()); - } + DWARFDie getSibling() const; /// Get the first child of this DIE object. /// /// \returns a valid DWARFDie instance if this object has children or an /// invalid DWARFDie instance if it doesn't. DWARFDie getFirstChild() const { - assert(isValid() && "must check validity prior to calling"); - return DWARFDie(U, Die->getFirstChild()); + if (isValid() && Die->hasChildren()) + return DWARFDie(U, Die + 1); + return DWARFDie(); } /// Dump the DIE and all of its attributes to the supplied stream. Index: include/llvm/DebugInfo/DWARF/DWARFUnit.h =================================================================== --- include/llvm/DebugInfo/DWARF/DWARFUnit.h +++ include/llvm/DebugInfo/DWARF/DWARFUnit.h @@ -140,6 +140,12 @@ const DWARFUnitIndex::Entry *IndexEntry; + uint32_t getDIEIndex(const DWARFDebugInfoEntry *Die) { + auto First = DieArray.data(); + assert(Die >= First && Die < First + DieArray.size()); + return Die - First; + } + protected: virtual bool extractImpl(DataExtractor debug_info, uint32_t *offset_ptr); /// Size in bytes of the unit header. @@ -251,10 +257,7 @@ /// method on a DIE that isn't accessible by following /// children/sibling links starting from this unit's getUnitDIE(). uint32_t getDIEIndex(const DWARFDie &D) { - auto DIE = D.getDebugInfoEntry(); - assert(!DieArray.empty() && DIE >= &DieArray[0] && - DIE < &DieArray[0] + DieArray.size()); - return DIE - &DieArray[0]; + return getDIEIndex(D.getDebugInfoEntry()); } /// \brief Return the DIE object at the given index. @@ -264,6 +267,9 @@ return DWARFDie(); } + DWARFDie getParent(const DWARFDebugInfoEntry *Die); + DWARFDie getSibling(const DWARFDebugInfoEntry *Die); + /// \brief Return the DIE object for a given offset inside the /// unit's DIE vector. /// @@ -298,10 +304,6 @@ /// extractDIEsToVector - Appends all parsed DIEs to a vector. void extractDIEsToVector(bool AppendCUDie, bool AppendNonCUDIEs, std::vector &DIEs) const; - /// setDIERelations - We read in all of the DIE entries into our flat list - /// of DIE entries and now we need to go back through all of them and set the - /// parent, sibling and child pointers for quick DIE navigation. - void setDIERelations(); /// clearDIEs - Clear parsed DIEs to keep memory usage low. void clearDIEs(bool KeepCUDie); Index: lib/DebugInfo/DWARF/DWARFDebugInfoEntry.cpp =================================================================== --- lib/DebugInfo/DWARF/DWARFDebugInfoEntry.cpp +++ lib/DebugInfo/DWARF/DWARFDebugInfoEntry.cpp @@ -26,13 +26,13 @@ uint32_t *OffsetPtr) { DataExtractor DebugInfoData = U.getDebugInfoExtractor(); const uint32_t UEndOffset = U.getNextUnitOffset(); - return extractFast(U, OffsetPtr, DebugInfoData, UEndOffset); + return extractFast(U, OffsetPtr, DebugInfoData, UEndOffset, 0); } -bool DWARFDebugInfoEntry::extractFast(const DWARFUnit &U, - uint32_t *OffsetPtr, - const DataExtractor &DebugInfoData, - uint32_t UEndOffset) { +bool DWARFDebugInfoEntry::extractFast(const DWARFUnit &U, uint32_t *OffsetPtr, + const DataExtractor &DebugInfoData, + uint32_t UEndOffset, uint32_t D) { Offset = *OffsetPtr; + Depth = D; if (Offset >= UEndOffset || !DebugInfoData.isValidOffset(Offset)) return false; uint64_t AbbrCode = DebugInfoData.getULEB128(OffsetPtr); Index: lib/DebugInfo/DWARF/DWARFDie.cpp =================================================================== --- lib/DebugInfo/DWARF/DWARFDie.cpp +++ lib/DebugInfo/DWARF/DWARFDie.cpp @@ -428,3 +428,14 @@ std::reverse(InlinedChain.begin(), InlinedChain.end()); } +DWARFDie DWARFDie::getParent() const { + if (isValid()) + return U->getParent(Die); + return DWARFDie(); +} + +DWARFDie DWARFDie::getSibling() const { + if (isValid()) + return U->getSibling(Die); + return DWARFDie(); +} Index: lib/DebugInfo/DWARF/DWARFUnit.cpp =================================================================== --- lib/DebugInfo/DWARF/DWARFUnit.cpp +++ lib/DebugInfo/DWARF/DWARFUnit.cpp @@ -158,35 +158,6 @@ return getUnitDIE().getAttributeValueAsUnsignedConstant(DW_AT_GNU_dwo_id); } -void DWARFUnit::setDIERelations() { - if (DieArray.size() <= 1) - return; - - std::vector ParentChain; - DWARFDebugInfoEntry *SiblingChain = nullptr; - for (auto &DIE : DieArray) { - if (SiblingChain) { - SiblingChain->setSibling(&DIE); - } - if (const DWARFAbbreviationDeclaration *AbbrDecl = - DIE.getAbbreviationDeclarationPtr()) { - // Normal DIE. - if (AbbrDecl->hasChildren()) { - ParentChain.push_back(&DIE); - SiblingChain = nullptr; - } else { - SiblingChain = &DIE; - } - } else { - // NULL entry terminates the sibling chain. - SiblingChain = ParentChain.back(); - ParentChain.pop_back(); - } - } - assert(SiblingChain == nullptr || SiblingChain == &DieArray[0]); - assert(ParentChain.empty()); -} - void DWARFUnit::extractDIEsToVector( bool AppendCUDie, bool AppendNonCUDies, std::vector &Dies) const { @@ -202,7 +173,7 @@ uint32_t Depth = 0; bool IsCUDie = true; - while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset)) { + while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset, Depth)) { if (IsCUDie) { if (AppendCUDie) Dies.push_back(DIE); @@ -266,7 +237,6 @@ // skeleton CU DIE, so that DWARF users not aware of it are not broken. } - setDIERelations(); return DieArray.size(); } @@ -409,4 +379,42 @@ return Context.getTUIndex(); } +DWARFDie DWARFUnit::getParent(const DWARFDebugInfoEntry *Die) { + if (!Die) + return DWARFDie(); + const uint32_t Depth = Die->getDepth(); + // Unit DIEs always have a depth of zero and never have parents. + if (Depth == 0) + return DWARFDie(); + // Depth of 1 always means parent is the compile/type unit. + if (Depth == 1) + return getUnitDIE(); + // Look for previous DIE with a depth that is one less than the Die's depth. + const uint32_t ParentDepth = Depth - 1; + for (uint32_t I = getDIEIndex(Die) - 1; I > 0; --I) { + if (DieArray[I].getDepth() == ParentDepth) + return getDIEAtIndex(I); + } + return DWARFDie(); +} + +DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) { + if (!Die) + return DWARFDie(); + uint32_t Depth = Die->getDepth(); + // Unit DIEs always have a depth of zero and never have siblings. + if (Depth == 0) + return DWARFDie(); + // NULL DIEs don't have siblings. + if (Die->getAbbreviationDeclarationPtr() == nullptr) + return DWARFDie(); + + // Find the next DIE whose depth is the same as the Die's depth. + for (size_t I=getDIEIndex(Die)+1, EndIdx = DieArray.size(); I(); } + +template void TestRelations() { + // Test the DWARF APIs related to accessing the DW_AT_low_pc and + // DW_AT_high_pc. + const uint8_t AddrSize = sizeof(AddrType); + initLLVMIfNeeded(); + Triple Triple = getHostTripleForAddrSize(AddrSize); + auto ExpectedDG = dwarfgen::Generator::create(Triple, Version); + if (HandleExpectedError(ExpectedDG)) + return; + dwarfgen::Generator *DG = ExpectedDG.get().get(); + dwarfgen::CompileUnit &CU = DG->addCompileUnit(); + dwarfgen::DIE CUDie = CU.getUnitDIE(); + + CUDie.addAttribute(DW_AT_name, DW_FORM_strp, "/tmp/main.c"); + CUDie.addAttribute(DW_AT_language, DW_FORM_data2, DW_LANG_C); + dwarfgen::DIE IntDie = CUDie.addChild(DW_TAG_base_type); + IntDie.addAttribute(DW_AT_name, DW_FORM_strp, "int"); + IntDie.addAttribute(DW_AT_encoding, DW_FORM_data1, DW_ATE_signed); + IntDie.addAttribute(DW_AT_byte_size, DW_FORM_data1, 4); + + // Create a subprogram DIE with a low and high PC. + dwarfgen::DIE SubprogramDie = CUDie.addChild(DW_TAG_subprogram); + SubprogramDie.addAttribute(DW_AT_name, DW_FORM_strp, "test"); + SubprogramDie.addAttribute(DW_AT_low_pc, DW_FORM_addr, 0x1000U); + SubprogramDie.addAttribute(DW_AT_high_pc, DW_FORM_addr, 0x1100U); + + dwarfgen::DIE Arg1Die = SubprogramDie.addChild(DW_TAG_formal_parameter); + Arg1Die.addAttribute(DW_AT_name, DW_FORM_strp, "i"); + Arg1Die.addAttribute(DW_AT_type, DW_FORM_ref_addr, IntDie); + + dwarfgen::DIE Arg2Die = SubprogramDie.addChild(DW_TAG_formal_parameter); + Arg2Die.addAttribute(DW_AT_name, DW_FORM_strp, "j"); + Arg2Die.addAttribute(DW_AT_type, DW_FORM_ref_addr, IntDie); + + MemoryBufferRef FileBuffer(DG->generate(), "dwarf"); + auto Obj = object::ObjectFile::createObjectFile(FileBuffer); + EXPECT_TRUE((bool)Obj); + DWARFContextInMemory DwarfContext(*Obj.get()); + + // Verify the number of compile units is correct. + uint32_t NumCUs = DwarfContext.getNumCompileUnits(); + EXPECT_EQ(NumCUs, 1u); + DWARFCompileUnit *U = DwarfContext.getCompileUnitAtIndex(0); + + // Get the compile unit DIE is valid. + auto CUDieDG = U->getUnitDIE(false); + EXPECT_TRUE(CUDieDG.isValid()); + // DieDG.dump(llvm::outs(), U, UINT32_MAX); + + // The compile unit doesn't have a parent or a sibling. + auto ParentDie = CUDieDG.getParent(); + EXPECT_FALSE(ParentDie.isValid()); + auto SiblingDie = CUDieDG.getSibling(); + EXPECT_FALSE(SiblingDie.isValid()); + + // The first child of the compile unit is our integer type DIE. + auto IntDieDG = CUDieDG.getFirstChild(); + EXPECT_TRUE(IntDieDG.isValid()); + EXPECT_EQ(IntDieDG.getTag(), DW_TAG_base_type); + + // Make sure the parent of the integer type DIE is the compile unit. + ParentDie = IntDieDG.getParent(); + EXPECT_TRUE(ParentDie.isValid()); + EXPECT_EQ(ParentDie.getOffset(), CUDieDG.getOffset()); + + // The the integer type DIE doesn't have any children. + auto IntDieChild = IntDieDG.getFirstChild(); + EXPECT_FALSE(IntDieChild.isValid()); + + // The sibling of the integer type DIE should be our subprogram DIE. + auto SubprogramDieDG = IntDieDG.getSibling(); + EXPECT_TRUE(SubprogramDieDG.isValid()); + EXPECT_EQ(SubprogramDieDG.getTag(), DW_TAG_subprogram); + + // Make sure the parent of the subprogram DIE is the compile unit. + ParentDie = SubprogramDieDG.getParent(); + EXPECT_TRUE(ParentDie.isValid()); + EXPECT_EQ(ParentDie.getOffset(), CUDieDG.getOffset()); + // Make sure the sibling of the subprogram is a NULL die + auto NullDie = SubprogramDieDG.getSibling(); + EXPECT_TRUE(NullDie.isValid()); + EXPECT_TRUE(NullDie.isNULL()); + + // Make sure the NULL die's parent is the compile unit + ParentDie = NullDie.getParent(); + EXPECT_TRUE(ParentDie.isValid()); + EXPECT_EQ(ParentDie.getOffset(), CUDieDG.getOffset()); + + // Make sure a NULL die doesn't have any sibling or child + EXPECT_FALSE(NullDie.getSibling().isValid()); + EXPECT_FALSE(NullDie.getFirstChild().isValid()); + + // Make sure a default constructed DWARFDie doesn't have any parent, sibling + // or child; + DWARFDie DefaultDie; + EXPECT_FALSE(DefaultDie.getParent().isValid()); + EXPECT_FALSE(DefaultDie.getFirstChild().isValid()); + EXPECT_FALSE(DefaultDie.getSibling().isValid()); +} + +TEST(DWARFDebugInfo, TestDWARF32Version2Addr4Relations) { + // Test that we can decode address values in DWARF32, version 2, with 4 byte + // addresses. + typedef uint32_t AddrType; + TestRelations<2, AddrType>(); +} + +TEST(DWARFDebugInfo, TestDWARF32Version2Addr8Relations) { + // Test that we can decode address values in DWARF32, version 2, with 8 byte + // addresses. + typedef uint64_t AddrType; + TestRelations<2, AddrType>(); +} + +TEST(DWARFDebugInfo, TestDWARF32Version3Addr4Relations) { + // Test that we can decode address values in DWARF32, version 3, with 4 byte + // addresses. + typedef uint32_t AddrType; + TestRelations<3, AddrType>(); +} + +TEST(DWARFDebugInfo, TestDWARF32Version3Addr8Relations) { + // Test that we can decode address values in DWARF32, version 3, with 8 byte + // addresses. + typedef uint64_t AddrType; + TestRelations<3, AddrType>(); +} + +TEST(DWARFDebugInfo, TestDWARF32Version4Addr4Relations) { + // Test that we can decode address values in DWARF32, version 4, with 4 byte + // addresses. + typedef uint32_t AddrType; + TestRelations<4, AddrType>(); +} + +TEST(DWARFDebugInfo, TestDWARF32Version4Addr8Relations) { + // Test that we can decode address values in DWARF32, version 4, with 8 byte + // addresses. + typedef uint64_t AddrType; + TestRelations<4, AddrType>(); +} + } // end anonymous namespace