[BitVector] Add find_last() and find_last_unset()

[zturner]

Summary

BitVector currently provides find_first() and find_first_unset(), this adds methods to search in reverse.

[chandlerc]

llvm/include/llvm/ADT/BitVector.h

169–172

The for loop above seems simpler?

If you really want, you can use:

for (unsigned i : llvm::reverse(llvm::seq(0, NumBitWords(size())))

201–207

Rather than this, what about just handling the last word outside the loop?

[zturner]

Updated based on feedback from chandlerc.

[zturner]

Fix an inverted conditional / break statement.

[chandlerc]

LGTM with some loop simplifications.

llvm/include/llvm/ADT/BitVector.h

175–179

I this can be written as:

while (i > 0 && Bits[i] != Bitword(0))
  --i;

213–218

I think this is the same as:

while (W == ~BitWord(0) && --i > 0)
  W = Bits[i];

llvm/include/llvm/ADT/BitVector.h

 // This file implements the BitVector class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_BITVECTOR_H
 #define LLVM_ADT_BITVECTOR_H
 
 #include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <cassert>
 #include <climits>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
 #include <utility>
public:
   /// of the bits are set.
   int find_first() const {
     for (unsigned i = 0; i < NumBitWords(size()); ++i)
       if (Bits[i] != 0)
         return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
     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 {
     for (unsigned i = 0; i < NumBitWords(size()); ++i)
       if (Bits[i] != ~0UL) {
         unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Bits[i]);
         return Result < size() ? Result : -1;
       }
     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<BitWord>(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 {
     ++Prev;
     if (Prev >= Size)
       return -1;
 
     unsigned WordPos = Prev / BITWORD_SIZE;

llvm/include/llvm/ADT/SmallBitVector.h

private:
   }
 
   void setSmallRawBits(uintptr_t NewRawBits) {
     assert(isSmall());
     X = (NewRawBits << 1) | uintptr_t(1);
   }
 
   // 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));
   }
 
   // Return the element bits.
   uintptr_t getSmallBits() const {
     return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
if (isSmall()) {
       uintptr_t Bits = getSmallBits();
       if (Bits == 0)
         return -1;
       return countTrailingZeros(Bits);
     }
     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()) {
       if (count() == getSmallSize())
         return -1;
 
       uintptr_t Bits = getSmallBits();
       return countTrailingOnes(Bits);
     }
     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 {
     if (isSmall()) {
       uintptr_t Bits = getSmallBits();
       // Mask off previous bits.
       Bits &= ~uintptr_t(0) << (Prev + 1);
       if (Bits == 0 || Prev + 1 >= getSmallSize())

llvm/include/llvm/DebugInfo/PDB/UDTLayout.h

 class LayoutItemBase {
 public:
   LayoutItemBase(const UDTLayoutBase *Parent, const PDBSymbol *Symbol,
                  const std::string &Name, uint32_t OffsetInParent,
                  uint32_t Size, bool IsElided);
   virtual ~LayoutItemBase() {}
 
   uint32_t deepPaddingSize() const;
+  virtual uint32_t tailPadding() const;
 
   const UDTLayoutBase *getParent() const { return Parent; }
   StringRef getName() const { return Name; }
   uint32_t getOffsetInParent() const { return OffsetInParent; }
   uint32_t getSize() const { return SizeOf; }
   uint32_t getLayoutSize() const { return LayoutSize; }
   const PDBSymbol *getSymbol() const { return Symbol; }
   const BitVector &usedBytes() const { return UsedBytes; }

 class UDTLayoutBase : public LayoutItemBase {
   template <typename T> using UniquePtrVector = std::vector<std::unique_ptr<T>>;
 
 public:
   UDTLayoutBase(const UDTLayoutBase *Parent, const PDBSymbol &Sym,
                 const std::string &Name, uint32_t OffsetInParent, uint32_t Size,
                 bool IsElided);
 
+  uint32_t tailPadding() const override;
+
   ArrayRef<LayoutItemBase *> layout_items() const { return LayoutItems; }
 
   ArrayRef<BaseClassLayout *> bases() const { return AllBases; }
   ArrayRef<BaseClassLayout *> regular_bases() const { return NonVirtualBases; }
   ArrayRef<BaseClassLayout *> virtual_bases() const { return VirtualBases; }
 
   uint32_t directVirtualBaseCount() const { return DirectVBaseCount; }
 

llvm/lib/DebugInfo/PDB/UDTLayout.cpp

: Symbol(Symbol), Parent(Parent), Name(Name),
       IsElided(IsElided) {
   UsedBytes.resize(SizeOf, true);
 }
 
 uint32_t LayoutItemBase::deepPaddingSize() const {
   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<PDBSymbolData> Member)
     : LayoutItemBase(&Parent, Member.get(), Member->getName(),
                      Member->getOffset(), getTypeLength(*Member), false),
       DataMember(std::move(Member)) {
   auto Type = DataMember->getType();
   if (auto UDT = unique_dyn_cast<PDBSymbolTypeUDT>(Type)) {
     UdtLayout = llvm::make_unique<ClassLayout>(std::move(UDT));
UDTLayoutBase::UDTLayoutBase(const UDTLayoutBase *Parent, const PDBSymbol &Sym,
   // uninitialized.
   UsedBytes.reset(0, Size);
 
   initializeChildren(Sym);
   if (LayoutSize < Size)
     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) {}
 
 ClassLayout::ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT)
     : ClassLayout(*UDT) {
   OwnedStorage = std::move(UDT);
 }
if (!hasVBPtrAtOffset(VBPO)) {
         addChildToLayout(std::move(VBPL));
       }
     }
 
     // Virtual bases always go at the end.  So just look for the last place we
     // 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<BaseClassLayout>(*this, Offset, Elide, std::move(VB));
     AllBases.push_back(BL.get());
 
     // Only lay this virtual base out directly inside of *this* class if this
     // is a top-most derived class.  Keep track of it regardless, but only
     // physically lay it out if it's a topmost derived class.
     addChildToLayout(std::move(BL));
   }
   VirtualBases = makeArrayRef(AllBases).drop_front(NonVirtualBases.size());
+
+  LayoutSize = UsedBytes.find_last() + 1;
 }
 
 bool UDTLayoutBase::hasVBPtrAtOffset(uint32_t Off) const {
   if (VBPtr && VBPtr->getOffsetInParent() == Off)
     return true;
   for (BaseClassLayout *BL : AllBases) {
     if (BL->hasVBPtrAtOffset(Off - BL->getOffsetInParent()))
       return true;
   }
   return false;
 }
 
 void UDTLayoutBase::addChildToLayout(std::unique_ptr<LayoutItemBase> 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
     // class.  When we call ChildBytes.resize(32), the Child's storage will
     // still begin at offset 0, so we need to shift it left by offset bytes
     // to get it into the right position.
     ChildBytes.resize(UsedBytes.size());
     ChildBytes <<= Child->getOffsetInParent();
     UsedBytes |= ChildBytes;
 
     if (ChildBytes.count() > 0) {
       auto Loc = std::upper_bound(LayoutItems.begin(), LayoutItems.end(), Begin,
                                   [](uint32_t Off, const LayoutItemBase *Item) {
                                     return (Off < Item->getOffsetInParent());
                                   });
 
       LayoutItems.insert(Loc, Child.get());
     }
   }
 
   ChildStorage.push_back(std::move(Child));
 }
 No newline at end of file

llvm/tools/llvm-pdbdump/PrettyClassDefinitionDumper.cpp

void ClassDefinitionDumper::start(const ClassLayout &Layout) {
 
   prettyPrintClassOutro(Layout);
 }
 
 void ClassDefinitionDumper::prettyPrintClassIntro(const ClassLayout &Layout) {
   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() << " ";
   WithColor(Printer, PDB_ColorItem::Type).get() << Class.getName();
   WithColor(Printer, PDB_ColorItem::Comment).get() << " [sizeof = " << Size
                                                    << "]";
   uint32_t BaseCount = Layout.bases().size();
   if (BaseCount > 0) {

llvm/tools/llvm-pdbdump/PrettyClassLayoutGraphicalDumper.cpp

if (Item->isVBPtr()) {
       VTableLayoutItem &Layout = static_cast<VTableLayoutItem &>(*CurrentItem);
 
       VariableDumper VarDumper(Printer);
       VarDumper.startVbptr(CurrentAbsoluteOffset, Layout.getSize());
     } else {
       if (auto Sym = Item->getSymbol())
         Sym->dump(*this);
     }
+
+    if (Item->getLayoutSize() > 0) {
+      uint32_t Prev = RelativeOffset + Item->getLayoutSize() - 1;
+      NextPaddingByte = UseMap.find_next_unset(Prev);
+    }
   }
 
-  if (NextPaddingByte >= 0 && Layout.getLayoutSize() > 1) {
-    uint32_t Amount = Layout.getLayoutSize() - NextPaddingByte;
-    if (Amount > 0) {
-      Printer.NewLine();
-      WithColor(Printer, PDB_ColorItem::Padding).get() << "<padding> ("
-                                                       << Amount << " bytes)";
-    }
+  auto TailPadding = Layout.tailPadding();
+  if (TailPadding > 0) {
+      << TailPadding << " bytes)";
     DumpedAnything = true;
   }
 
   return DumpedAnything;
 }
 
 void PrettyClassLayoutGraphicalDumper::printPaddingRow(uint32_t Amount) {
   if (Amount == 0)

llvm/unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, TrivialOperation) {
   EXPECT_TRUE(Vec.none());
   EXPECT_TRUE(Vec.empty());
 }
 
 TYPED_TEST(BitVectorTest, FindOperations) {
   // 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));
 
   // Test finding next set and unset bits in a BitVector with multiple words
   A.resize(100);
   A.set(12);
   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));
   EXPECT_EQ(16, A.find_next_unset(15));
   EXPECT_EQ(76, A.find_next_unset(74));
   EXPECT_EQ(76, A.find_next_unset(75));
   EXPECT_EQ(-1, A.find_next_unset(99));
 
   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) {
   TypeParam A;
   A.resize(10);
   A.set(4);
   A.set(7);