Index: llvm/include/llvm/ADT/BitVector.h =================================================================== --- llvm/include/llvm/ADT/BitVector.h +++ llvm/include/llvm/ADT/BitVector.h @@ -15,7 +15,6 @@ #define LLVM_ADT_BITVECTOR_H #include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/STLExtras.h" #include "llvm/Support/MathExtras.h" #include #include @@ -163,6 +162,25 @@ return -1; } + /// find_last - Returns the index of the last set bit, -1 if none of the bits + /// are set. + int find_last() const { + if (Size == 0) + return -1; + + unsigned N = NumBitWords(size()); + assert(N > 0); + + unsigned i = N - 1; + while (i > 0) { + if (Bits[i] != BitWord(0)) + break; + --i; + } + + return int((i + 1) * BITWORD_SIZE - countLeadingZeros(Bits[i])) - 1; + } + /// find_first_unset - Returns the index of the first unset bit, -1 if all /// of the bits are set. int find_first_unset() const { @@ -174,6 +192,34 @@ return -1; } + /// find_last_unset - Returns the index of the last unset bit, -1 if all of + /// the bits are set. + int find_last_unset() const { + if (Size == 0) + return -1; + + const unsigned N = NumBitWords(size()); + assert(N > 0); + + unsigned i = N - 1; + BitWord W = Bits[i]; + + // The last word in the BitVector has some unused bits, so we need to set + // them all to 1 first. Set them all to 1 so they don't get treated as + // valid unset bits. + unsigned UnusedCount = BITWORD_SIZE - size() % BITWORD_SIZE; + W |= maskLeadingOnes(UnusedCount); + + if (W == ~BitWord(0)) { + while (--i > 0) { + if ((W = Bits[i]) == ~BitWord(0)) + continue; + } + } + + return int((i + 1) * BITWORD_SIZE - countLeadingOnes(W)) - 1; + } + /// find_next - Returns the index of the next set bit following the /// "Prev" bit. Returns -1 if the next set bit is not found. int find_next(unsigned Prev) const { Index: llvm/include/llvm/ADT/SmallBitVector.h =================================================================== --- llvm/include/llvm/ADT/SmallBitVector.h +++ llvm/include/llvm/ADT/SmallBitVector.h @@ -117,9 +117,7 @@ } // Return the size. - size_t getSmallSize() const { - return getSmallRawBits() >> SmallNumDataBits; - } + size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; } void setSmallSize(size_t Size) { setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); @@ -216,6 +214,16 @@ return getPointer()->find_first(); } + int find_last() const { + if (isSmall()) { + uintptr_t Bits = getSmallBits(); + if (Bits == 0) + return -1; + return NumBaseBits - countLeadingZeros(Bits); + } + return getPointer()->find_last(); + } + /// Returns the index of the first unset bit, -1 if all of the bits are set. int find_first_unset() const { if (isSmall()) { @@ -228,6 +236,17 @@ return getPointer()->find_first_unset(); } + int find_last_unset() const { + if (isSmall()) { + if (count() == getSmallSize()) + return -1; + + uintptr_t Bits = getSmallBits(); + return NumBaseBits - countLeadingOnes(Bits); + } + return getPointer()->find_last_unset(); + } + /// Returns the index of the next set bit following the "Prev" bit. /// Returns -1 if the next set bit is not found. int find_next(unsigned Prev) const { Index: llvm/include/llvm/DebugInfo/PDB/UDTLayout.h =================================================================== --- llvm/include/llvm/DebugInfo/PDB/UDTLayout.h +++ llvm/include/llvm/DebugInfo/PDB/UDTLayout.h @@ -44,6 +44,7 @@ virtual ~LayoutItemBase() {} uint32_t deepPaddingSize() const; + virtual uint32_t tailPadding() const; const UDTLayoutBase *getParent() const { return Parent; } StringRef getName() const { return Name; } @@ -117,6 +118,8 @@ const std::string &Name, uint32_t OffsetInParent, uint32_t Size, bool IsElided); + uint32_t tailPadding() const override; + ArrayRef layout_items() const { return LayoutItems; } ArrayRef bases() const { return AllBases; } Index: llvm/lib/DebugInfo/PDB/UDTLayout.cpp =================================================================== --- llvm/lib/DebugInfo/PDB/UDTLayout.cpp +++ llvm/lib/DebugInfo/PDB/UDTLayout.cpp @@ -54,6 +54,13 @@ return UsedBytes.size() - UsedBytes.count(); } +uint32_t LayoutItemBase::tailPadding() const { + int Last = UsedBytes.find_last(); + + return UsedBytes.size() - (Last + 1); +} + + DataMemberLayoutItem::DataMemberLayoutItem( const UDTLayoutBase &Parent, std::unique_ptr Member) : LayoutItemBase(&Parent, Member.get(), Member->getName(), @@ -104,6 +111,19 @@ UsedBytes.resize(LayoutSize); } +uint32_t UDTLayoutBase::tailPadding() const { + uint32_t Abs = LayoutItemBase::tailPadding(); + if (!LayoutItems.empty()) { + const LayoutItemBase *Back = LayoutItems.back(); + uint32_t ChildPadding = Back->LayoutItemBase::tailPadding(); + if (Abs < ChildPadding) + Abs = 0; + else + Abs -= ChildPadding; + } + return Abs; +} + ClassLayout::ClassLayout(const PDBSymbolTypeUDT &UDT) : UDTLayoutBase(nullptr, UDT, UDT.getName(), 0, UDT.getLength(), false), UDT(UDT) {} @@ -207,11 +227,7 @@ // ended when writing something, and put our virtual base there. // Note that virtual bases get elided unless this is a top-most derived // class. - uint32_t Offset = 0; - if (!LayoutItems.empty()) { - auto Last = LayoutItems.back(); - Offset = Last->getOffsetInParent() + Last->getSize(); - } + uint32_t Offset = UsedBytes.find_last() + 1; bool Elide = (Parent != nullptr); auto BL = llvm::make_unique(*this, Offset, Elide, std::move(VB)); @@ -223,6 +239,8 @@ addChildToLayout(std::move(BL)); } VirtualBases = makeArrayRef(AllBases).drop_front(NonVirtualBases.size()); + + LayoutSize = UsedBytes.find_last() + 1; } bool UDTLayoutBase::hasVBPtrAtOffset(uint32_t Off) const { @@ -238,9 +256,7 @@ void UDTLayoutBase::addChildToLayout(std::unique_ptr Child) { uint32_t Begin = Child->getOffsetInParent(); - if (Child->isElided()) { - LayoutSize -= Child->getSize(); - } else { + if (!Child->isElided()) { BitVector ChildBytes = Child->usedBytes(); // Suppose the child occupies 4 bytes starting at offset 12 in a 32 byte Index: llvm/tools/llvm-pdbdump/PrettyClassDefinitionDumper.cpp =================================================================== --- llvm/tools/llvm-pdbdump/PrettyClassDefinitionDumper.cpp +++ llvm/tools/llvm-pdbdump/PrettyClassDefinitionDumper.cpp @@ -62,7 +62,7 @@ DumpedAnything = false; Printer.NewLine(); - uint32_t Size = Layout.getLayoutSize(); + uint32_t Size = Layout.getSize(); const PDBSymbolTypeUDT &Class = Layout.getClass(); WithColor(Printer, PDB_ColorItem::Keyword).get() << Class.getUdtKind() << " "; Index: llvm/tools/llvm-pdbdump/PrettyClassLayoutGraphicalDumper.cpp =================================================================== --- llvm/tools/llvm-pdbdump/PrettyClassLayoutGraphicalDumper.cpp +++ llvm/tools/llvm-pdbdump/PrettyClassLayoutGraphicalDumper.cpp @@ -63,15 +63,18 @@ if (auto Sym = Item->getSymbol()) Sym->dump(*this); } - } - if (NextPaddingByte >= 0 && Layout.getLayoutSize() > 1) { - uint32_t Amount = Layout.getLayoutSize() - NextPaddingByte; - if (Amount > 0) { - Printer.NewLine(); - WithColor(Printer, PDB_ColorItem::Padding).get() << " (" - << Amount << " bytes)"; + if (Item->getLayoutSize() > 0) { + uint32_t Prev = RelativeOffset + Item->getLayoutSize() - 1; + NextPaddingByte = UseMap.find_next_unset(Prev); } + } + + auto TailPadding = Layout.tailPadding(); + if (TailPadding > 0) { + Printer.NewLine(); + WithColor(Printer, PDB_ColorItem::Padding).get() << " (" + << TailPadding << " bytes)"; DumpedAnything = true; } Index: llvm/unittests/ADT/BitVectorTest.cpp =================================================================== --- llvm/unittests/ADT/BitVectorTest.cpp +++ llvm/unittests/ADT/BitVectorTest.cpp @@ -186,7 +186,9 @@ // Test finding in an empty BitVector. TypeParam A; EXPECT_EQ(-1, A.find_first()); + EXPECT_EQ(-1, A.find_last()); EXPECT_EQ(-1, A.find_first_unset()); + EXPECT_EQ(-1, A.find_last_unset()); EXPECT_EQ(-1, A.find_next(0)); EXPECT_EQ(-1, A.find_next_unset(0)); @@ -196,12 +198,14 @@ A.set(13); A.set(75); + EXPECT_EQ(75, A.find_last()); EXPECT_EQ(12, A.find_first()); EXPECT_EQ(13, A.find_next(12)); EXPECT_EQ(75, A.find_next(13)); EXPECT_EQ(-1, A.find_next(75)); EXPECT_EQ(0, A.find_first_unset()); + EXPECT_EQ(99, A.find_last_unset()); EXPECT_EQ(14, A.find_next_unset(11)); EXPECT_EQ(14, A.find_next_unset(12)); EXPECT_EQ(14, A.find_next_unset(13)); @@ -213,12 +217,16 @@ A.set(0, 100); EXPECT_EQ(100U, A.count()); EXPECT_EQ(0, A.find_first()); + EXPECT_EQ(99, A.find_last()); EXPECT_EQ(-1, A.find_first_unset()); + EXPECT_EQ(-1, A.find_last_unset()); A.reset(0, 100); EXPECT_EQ(0U, A.count()); EXPECT_EQ(-1, A.find_first()); + EXPECT_EQ(-1, A.find_last()); EXPECT_EQ(0, A.find_first_unset()); + EXPECT_EQ(99, A.find_last_unset()); } TYPED_TEST(BitVectorTest, CompoundAssignment) {