[ADT] CoalescingBitVector: Avoid initial heap allocation, NFC

[vsk]

Summary

Avoid making a heap allocation when constructing a CoalescingBitVector.

This reduces time spent in LiveDebugValues when compiling sqlite3 by
700ms (0.5% of the total User Time).

rdar://60046261

[aprantl]

Should we then call it SmallCoalescingBitVector? Probably not :-)

[jmorse]

LGTM

llvm/include/llvm/ADT/CoalescingBitVector.h

 
 #include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <algorithm>
 #include <initializer_list>
-#include <memory>
 
 namespace llvm {
 
 /// A bitvector that, under the hood, relies on an IntervalMap to coalesce
 /// elements into intervals. Good for representing sets which predominantly
 /// contain contiguous ranges. Bad for representing sets with lots of gaps
 /// between elements.
 ///
 /// Compared to SparseBitVector, CoalescingBitVector offers more predictable
 /// performance for non-sequential find() operations.
 ///
 /// \tparam IndexT - The type of the index into the bitvector.
-/// \tparam N - The first N coalesced intervals of set bits are stored in-place
-/// (in the initial heap allocation).
+/// \tparam N - The first N coalesced intervals of set bits are stored in-place.
 template <typename IndexT, unsigned N = 16> class CoalescingBitVector {
   static_assert(std::is_unsigned<IndexT>::value,
                 "Index must be an unsigned integer.");
 
   using ThisT = CoalescingBitVector<IndexT, N>;
 
   /// An interval map for closed integer ranges. The mapped values are unused.
   using MapT = IntervalMap<IndexT, char, N>;
 
   using UnderlyingIterator = typename MapT::const_iterator;
 
   using IntervalT = std::pair<IndexT, IndexT>;
 
 public:
   using Allocator = typename MapT::Allocator;
 
   /// Construct by passing in a CoalescingBitVector<IndexT>::Allocator
   /// reference.
   CoalescingBitVector(Allocator &Alloc)
-      : Alloc(&Alloc), Intervals(std::make_unique<MapT>(Alloc)) {}
+      : Alloc(&Alloc), Intervals(Alloc) {}
 
   /// \name Copy/move constructors and assignment operators.
   /// @{
 
   CoalescingBitVector(const ThisT &Other)
-      : Alloc(Other.Alloc), Intervals(std::make_unique<MapT>(*Other.Alloc)) {
+      : Alloc(Other.Alloc), Intervals(*Other.Alloc) {
     set(Other);
   }
 
   ThisT &operator=(const ThisT &Other) {
     clear();
     set(Other);
     return *this;
   }
 
-  CoalescingBitVector(ThisT &&Other)
-      : Alloc(Other.Alloc), Intervals(std::move(Other.Intervals)) {}
-
-  ThisT &operator=(ThisT &&Other) {
-    Alloc = Other.Alloc;
-    Intervals = std::move(Other.Intervals);
-    return *this;
-  }
+  CoalescingBitVector(ThisT &&Other) = delete;
+  ThisT &operator=(ThisT &&Other) = delete;
 
   /// @}
 
   /// Clear all the bits.
-  void clear() { Intervals->clear(); }
+  void clear() { Intervals.clear(); }
 
   /// Check whether no bits are set.
-  bool empty() const { return Intervals->empty(); }
+  bool empty() const { return Intervals.empty(); }
 
   /// Count the number of set bits.
   unsigned count() const {
     unsigned Bits = 0;
-    for (auto It = Intervals->begin(), End = Intervals->end(); It != End; ++It)
+    for (auto It = Intervals.begin(), End = Intervals.end(); It != End; ++It)
       Bits += 1 + It.stop() - It.start();
     return Bits;
   }
 
   /// Set the bit at \p Index.
   ///
   /// This method does /not/ support setting a bit that has already been set,
   /// for efficiency reasons. If possible, restructure your code to not set the
   /// same bit multiple times, or use \ref test_and_set.
   void set(IndexT Index) {
     assert(!test(Index) && "Setting already-set bits not supported/efficient, "
                            "IntervalMap will assert");
     insert(Index, Index);
   }
 
   /// Set the bits set in \p Other.
   ///
   /// This method does /not/ support setting already-set bits, see \ref set
   /// for the rationale. For a safe set union operation, use \ref operator|=.
   void set(const ThisT &Other) {
-    for (auto It = Other.Intervals->begin(), End = Other.Intervals->end();
+    for (auto It = Other.Intervals.begin(), End = Other.Intervals.end();
          It != End; ++It)
       insert(It.start(), It.stop());
   }
 
   /// Set the bits at \p Indices. Used for testing, primarily.
   void set(std::initializer_list<IndexT> Indices) {
     for (IndexT Index : Indices)
       set(Index);
   }
 
   /// Check whether the bit at \p Index is set.
   bool test(IndexT Index) const {
-    const auto It = Intervals->find(Index);
-    if (It == Intervals->end())
+    const auto It = Intervals.find(Index);
+    if (It == Intervals.end())
       return false;
     assert(It.stop() >= Index && "Interval must end after Index");
     return It.start() <= Index;
   }
 
   /// Set the bit at \p Index. Supports setting an already-set bit.
   void test_and_set(IndexT Index) {
     if (!test(Index))
       set(Index);
   }
 
   /// Reset the bit at \p Index. Supports resetting an already-unset bit.
   void reset(IndexT Index) {
-    auto It = Intervals->find(Index);
-    if (It == Intervals->end())
+    auto It = Intervals.find(Index);
+    if (It == Intervals.end())
       return;
 
     // Split the interval containing Index into up to two parts: one from
     // [Start, Index-1] and another from [Index+1, Stop]. If Index is equal to
     // either Start or Stop, we create one new interval. If Index is equal to
     // both Start and Stop, we simply erase the existing interval.
     IndexT Start = It.start();
     if (Index < Start)
public:
   /// Set union. If \p RHS is guaranteed to not overlap with this, \ref set may
   /// be a faster alternative.
   void operator|=(const ThisT &RHS) {
     // Get the overlaps between the two interval maps.
     SmallVector<IntervalT, 8> Overlaps;
     getOverlaps(RHS, Overlaps);
 
     // Insert the non-overlapping parts of all the intervals from RHS.
-    for (auto It = RHS.Intervals->begin(), End = RHS.Intervals->end();
+    for (auto It = RHS.Intervals.begin(), End = RHS.Intervals.end();
          It != End; ++It) {
       IndexT Start = It.start();
       IndexT Stop = It.stop();
       SmallVector<IntervalT, 8> NonOverlappingParts;
       getNonOverlappingParts(Start, Stop, Overlaps, NonOverlappingParts);
       for (IntervalT AdditivePortion : NonOverlappingParts)
         insert(AdditivePortion.first, AdditivePortion.second);
     }
void intersectWithComplement(const ThisT &Other) {
     }
 
     // Delete the overlapping intervals. Split up intervals that only partially
     // intersect an overlap.
     for (IntervalT Overlap : Overlaps) {
       IndexT OlapStart, OlapStop;
       std::tie(OlapStart, OlapStop) = Overlap;
 
-      auto It = Intervals->find(OlapStart);
+      auto It = Intervals.find(OlapStart);
       IndexT CurrStart = It.start();
       IndexT CurrStop = It.stop();
       assert(CurrStart <= OlapStart && OlapStop <= CurrStop &&
              "Expected some intersection!");
 
       // Split the overlap interval into up to two parts: one from [CurrStart,
       // OlapStart-1] and another from [OlapStop+1, CurrStop]. If OlapStart is
       // equal to CurrStart, the first split interval is unnecessary. Ditto for
       // when OlapStop is equal to CurrStop, we omit the second split interval.
       It.erase();
       if (CurrStart < OlapStart)
         insert(CurrStart, OlapStart - 1);
       if (OlapStop < CurrStop)
         insert(OlapStop + 1, CurrStop);
     }
   }
 
   bool operator==(const ThisT &RHS) const {
     // We cannot just use std::equal because it checks the dereferenced values
     // of an iterator pair for equality, not the iterators themselves. In our
     // case that results in comparison of the (unused) IntervalMap values.
-    auto ItL = Intervals->begin();
-    auto ItR = RHS.Intervals->begin();
-    while (ItL != Intervals->end() && ItR != RHS.Intervals->end() &&
+    auto ItL = Intervals.begin();
+    auto ItR = RHS.Intervals.begin();
+    while (ItL != Intervals.end() && ItR != RHS.Intervals.end() &&
            ItL.start() == ItR.start() && ItL.stop() == ItR.stop()) {
       ++ItL;
       ++ItR;
     }
-    return ItL == Intervals->end() && ItR == RHS.Intervals->end();
+    return ItL == Intervals.end() && ItR == RHS.Intervals.end();
   }
 
   bool operator!=(const ThisT &RHS) const { return !operator==(RHS); }
 
   class const_iterator
       : public std::iterator<std::forward_iterator_tag, IndexT> {
     friend class CoalescingBitVector;
 
public:
 
     const_iterator operator++(int) { // Post-increment (It++).
       const_iterator tmp = *this;
       operator++();
       return tmp;
     }
   };
 
-  const_iterator begin() const { return const_iterator(Intervals->begin()); }
+  const_iterator begin() const { return const_iterator(Intervals.begin()); }
 
   const_iterator end() const { return const_iterator(); }
 
   /// Return an iterator pointing to the first set bit AT, OR AFTER, \p Index.
   /// If no such set bit exists, return end(). This is like std::lower_bound.
   const_iterator find(IndexT Index) const {
-    auto UnderlyingIt = Intervals->find(Index);
-    if (UnderlyingIt == Intervals->end())
+    auto UnderlyingIt = Intervals.find(Index);
+    if (UnderlyingIt == Intervals.end())
       return end();
     auto It = const_iterator(UnderlyingIt);
     It.advanceTo(Index);
     return It;
   }
 
   void print(raw_ostream &OS) const {
     OS << "{";
-    for (auto It = Intervals->begin(), End = Intervals->end(); It != End;
+    for (auto It = Intervals.begin(), End = Intervals.end(); It != End;
          ++It) {
       OS << "[" << It.start();
       if (It.start() != It.stop())
         OS << ", " << It.stop();
       OS << "]";
     }
     OS << "}";
   }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const {
     // LLDB swallows the first line of output after callling dump(). Add
     // newlines before/after the braces to work around this.
     dbgs() << "\n";
     print(dbgs());
     dbgs() << "\n";
   }
 #endif
 
 private:
-  void insert(IndexT Start, IndexT End) { Intervals->insert(Start, End, 0); }
+  void insert(IndexT Start, IndexT End) { Intervals.insert(Start, End, 0); }
 
   /// Record the overlaps between \p this and \p Other in \p Overlaps. Return
   /// true if there is any overlap.
   bool getOverlaps(const ThisT &Other,
                    SmallVectorImpl<IntervalT> &Overlaps) const {
-    for (IntervalMapOverlaps<MapT, MapT> I(*Intervals, *Other.Intervals);
+    for (IntervalMapOverlaps<MapT, MapT> I(Intervals, Other.Intervals);
          I.valid(); ++I)
       Overlaps.emplace_back(I.start(), I.stop());
     assert(std::is_sorted(Overlaps.begin(), Overlaps.end(),
                           [](IntervalT LHS, IntervalT RHS) {
                             return LHS.second < RHS.first;
                           }) &&
            "Overlaps must be sorted");
     return !Overlaps.empty();
for (IntervalT Overlap : Overlaps) {
       if (NextUncoveredBit > Stop)
         break;
     }
     if (NextUncoveredBit <= Stop)
       NonOverlappingParts.emplace_back(NextUncoveredBit, Stop);
   }
 
   Allocator *Alloc;
-  std::unique_ptr<MapT> Intervals;
+  MapT Intervals;
 };
 
 } // namespace llvm
 
 #endif // LLVM_ADT_COALESCINGBITVECTOR_H

llvm/lib/CodeGen/LiveDebugValues.cpp

public:
     /// Retrieve the unique VarLoc associated with \p ID.
     const VarLoc &operator[](LocIndex ID) const {
       auto LocIt = Loc2Vars.find(ID.Location);
       assert(LocIt != Loc2Vars.end() && "Location not tracked");
       return LocIt->second[ID.Index];
     }
   };
 
-  using VarLocInMBB = SmallDenseMap<const MachineBasicBlock *, VarLocSet>;
+  using VarLocInMBB =
+      SmallDenseMap<const MachineBasicBlock *, std::unique_ptr<VarLocSet>>;
   struct TransferDebugPair {
     MachineInstr *TransferInst; ///< Instruction where this transfer occurs.
     LocIndex LocationID;        ///< Location number for the transfer dest.
   };
   using TransferMap = SmallVector<TransferDebugPair, 4>;
 
   // Types for recording sets of variable fragments that overlap. For a given
   // local variable, we record all other fragments of that variable that could
void collectIDsForReg(VarLocSet &Collected, uint32_t Reg,
                         const VarLocSet &CollectFrom) const;
 
   /// Get the registers which are used by VarLocs of kind RegisterKind tracked
   /// by \p CollectFrom.
   void getUsedRegs(const VarLocSet &CollectFrom,
                    SmallVectorImpl<uint32_t> &UsedRegs) const;
 
   VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, VarLocInMBB &Locs) {
-    auto Result = Locs.try_emplace(MBB, Alloc);
-    return Result.first->second;
+    std::unique_ptr<VarLocSet> &VLS = Locs[MBB];
+    if (!VLS)
+      VLS = std::make_unique<VarLocSet>(Alloc);
+    return *VLS.get();
   }
 
   const VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB,
                                    const VarLocInMBB &Locs) const {
     auto It = Locs.find(MBB);
     assert(It != Locs.end() && "MBB not in map");
-    return It->second;
+    return *It->second.get();
   }
 
   /// Tests whether this instruction is a spill to a stack location.
   bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
 
   /// Decide if @MI is a spill instruction and return true if it is. We use 2
   /// criteria to make this decision:
   /// - Is this instruction a store to a spill slot?
for (auto p : MBB.predecessors()) {
     }
     auto OL = OutLocs.find(p);
     // Join is null in case of empty OutLocs from any of the pred.
     if (OL == OutLocs.end())
       return false;
 
     // Just copy over the Out locs to incoming locs for the first visited
     // predecessor, and for all other predecessors join the Out locs.
+    VarLocSet &OutLocVLS = *OL->second.get();
     if (!NumVisited)
-      InLocsT = OL->second;
+      InLocsT = OutLocVLS;
     else
-      InLocsT &= OL->second;
+      InLocsT &= OutLocVLS;
 
     LLVM_DEBUG({
       if (!InLocsT.empty()) {
         for (uint64_t ID : InLocsT)
           dbgs() << "  gathered candidate incoming var: "
                  << VarLocIDs[LocIndex::fromRawInteger(ID)]
                         .Var.getVariable()
                         ->getName()

 
 void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs,
                                        VarLocMap &VarLocIDs) {
   // PendingInLocs records all locations propagated into blocks, which have
   // not had DBG_VALUE insts created. Go through and create those insts now.
   for (auto &Iter : PendingInLocs) {
     // Map is keyed on a constant pointer, unwrap it so we can insert insts.
     auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
-    VarLocSet &Pending = Iter.second;
+    VarLocSet &Pending = *Iter.second.get();
 
     for (uint64_t ID : Pending) {
       // The ID location is live-in to MBB -- work out what kind of machine
       // location it is and create a DBG_VALUE.
       const VarLoc &DiffIt = VarLocIDs[LocIndex::fromRawInteger(ID)];
       if (DiffIt.isEntryBackupLoc())
         continue;
       MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent());
bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   for (auto &MI : First_MBB) {
     collectRegDefs(MI, DefinedRegs, TRI);
       if (MI.isDebugValue())
         recordEntryValue(MI, DefinedRegs, OpenRanges, VarLocIDs);
   }
 
   // Initialize per-block structures and scan for fragment overlaps.
   for (auto &MBB : MF) {
-    PendingInLocs.try_emplace(&MBB, Alloc);
+    PendingInLocs[&MBB] = std::make_unique<VarLocSet>(Alloc);
 
     for (auto &MI : MBB) {
       if (MI.isDebugValue())
         accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
     }
   }
 
   auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {

llvm/unittests/ADT/CoalescingBitVectorTest.cpp

TEST(CoalescingBitVector, Copy) {
   EXPECT_TRUE(elementsMatch(BV1, {0}));
   EXPECT_TRUE(elementsMatch(BV2, {0}));
   BV2.set(5);
   BV2 = BV1;
   EXPECT_TRUE(elementsMatch(BV1, {0}));
   EXPECT_TRUE(elementsMatch(BV2, {0}));
 }
 
-TEST(CoalescingBitVector, Move) {
-  UBitVec::Allocator Alloc;
-  UBitVec BV1(Alloc);
-  BV1.set(0);
-  UBitVec BV2 = std::move(BV1);
-  EXPECT_TRUE(elementsMatch(BV2, {0}));
-  BV2.set(5);
-  BV1 = std::move(BV2);
-  EXPECT_TRUE(elementsMatch(BV1, {0, 5}));
-}
-
 TEST(CoalescingBitVectorTest, Iterators) {
   UBitVec::Allocator Alloc;
   UBitVec BV(Alloc);
 
   BV.set({0, 1, 2});
 
   auto It = BV.begin();
   EXPECT_TRUE(It == BV.begin());