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 @@ -40,6 +40,9 @@ bool isValid() const { return U && Die; } explicit operator bool() const { return isValid(); } + bool operator ==(const DWARFDie &RHS) const { + return Die == RHS.Die && U == RHS.U; + } const DWARFDebugInfoEntry *getDebugInfoEntry() const { return Die; } DWARFUnit *getDwarfUnit() const { return U; } @@ -82,23 +85,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,8 @@ 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 +238,6 @@ // skeleton CU DIE, so that DWARF users not aware of it are not broken. } - setDIERelations(); return DieArray.size(); } @@ -409,4 +380,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(); } +TEST(DWARFDebugInfo, TestRelations) { + // Test the DWARF APIs related to accessing the DW_AT_low_pc and + // DW_AT_high_pc. + uint16_t Version = 4; + + const uint8_t AddrSize = sizeof(void *); + 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(); + + enum class Tag: uint16_t { + A = dwarf::DW_TAG_lo_user, + B, + B1, + B2, + C, + C1 + }; + // Scope to allow us to re-use the same DIE names + { + // Create DWARF tree that looks like: + // + // CU + // A + // B + // B1 + // B2 + // C + // C1 + dwarfgen::DIE CUDie = CU.getUnitDIE(); + CUDie.addChild((dwarf::Tag)Tag::A); + dwarfgen::DIE B = CUDie.addChild((dwarf::Tag)Tag::B); + dwarfgen::DIE C = CUDie.addChild((dwarf::Tag)Tag::C); + B.addChild((dwarf::Tag)Tag::B1); + B.addChild((dwarf::Tag)Tag::B2); + C.addChild((dwarf::Tag)Tag::C1); + } + + 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 CUDie = U->getUnitDIE(false); + EXPECT_TRUE(CUDie.isValid()); + // DieDG.dump(llvm::outs(), U, UINT32_MAX); + + // The compile unit doesn't have a parent or a sibling. + auto ParentDie = CUDie.getParent(); + EXPECT_FALSE(ParentDie.isValid()); + auto SiblingDie = CUDie.getSibling(); + EXPECT_FALSE(SiblingDie.isValid()); + + // Get the children of the compile unit + auto A = CUDie.getFirstChild(); + auto B = A.getSibling(); + auto C = B.getSibling(); + auto Null = C.getSibling(); + + // Verify NULL Die is NULL and has no children or siblings + EXPECT_TRUE(Null.isNULL()); + EXPECT_FALSE(Null.getSibling().isValid()); + EXPECT_FALSE(Null.getFirstChild().isValid()); + + // Verify all children of the compile unit DIE are correct. + EXPECT_EQ(A.getTag(), (dwarf::Tag)Tag::A); + EXPECT_EQ(B.getTag(), (dwarf::Tag)Tag::B); + EXPECT_EQ(C.getTag(), (dwarf::Tag)Tag::C); + + // Verify who has children + EXPECT_FALSE(A.hasChildren()); + EXPECT_TRUE(B.hasChildren()); + EXPECT_TRUE(C.hasChildren()); + + // Make sure the parent of all the children of the compile unit are the + // compile unit. + EXPECT_EQ(A.getParent(), CUDie); + EXPECT_EQ(B.getParent(), CUDie); + EXPECT_EQ(C.getParent(), CUDie); + EXPECT_EQ(Null.getParent(), CUDie); + + EXPECT_FALSE(A.getFirstChild().isValid()); + + // Verify the children of the B DIE + auto B1 = B.getFirstChild(); + auto B2 = B1.getSibling(); + EXPECT_TRUE(B2.getSibling().isNULL()); + + // Verify all children of the B DIE correctly valid or invalid. + EXPECT_EQ(B1.getTag(), (dwarf::Tag)Tag::B1); + EXPECT_EQ(B2.getTag(), (dwarf::Tag)Tag::B2); + + // Verify we get invalid children. + EXPECT_FALSE(B1.getFirstChild().isValid()); + EXPECT_FALSE(B2.getFirstChild().isValid()); + + // Make sure the parent of all the children of the B are the B. + EXPECT_EQ(B1.getParent(), B); + EXPECT_EQ(B2.getParent(), B); + + // Verify the children of the C DIE + auto C1 = C.getFirstChild(); + EXPECT_TRUE(C1.getSibling().isNULL()); + + // Verify all children of the C DIE correctly valid or invalid. + EXPECT_TRUE(C1.isValid()); + + // Verify all children of the C DIE have the right tag. + EXPECT_EQ(C1.getTag(), (dwarf::Tag)Tag::C1); + + // Verify we get invalid children. + EXPECT_FALSE(C1.getFirstChild().isValid()); + + // Make sure the parent of all the children of the C are the C. + EXPECT_EQ(C1.getParent(), C); + + // 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()); +} + + } // end anonymous namespace