[llvm][CycleInfo] Quick look-up for block in cycle.

[sameerds]

Summary

Use a SetVector to store blocks in a cycle to ensure a quick loop-up when
querying whether the cycle contains a given block.

This follows along the same lines as the SmallPtrSet in LoopBase, introduced by
commit be640b28c0cb81b77015baaef20ca2941fc61dea

[foad]

llvm/include/llvm/ADT/GenericCycleInfo.h

67

Maybe use SmallVector<BlockT *, 8> for the vector, to "match" the SmallPtrSet?

110–111

I don't think this explanation makes any sense. There is no world in which it would be "right" for the "const" in "const key_type&" to be applied to the pointee type of key_type.

We could add a templated SetVector::contains to avoid the need for the case, like std::set has: https://en.cppreference.com/w/cpp/container/set/contains

[Pierre-vh]

llvm/include/llvm/ADT/GenericCycleInfo.h

170

Curious: Do you still need typename here?

[sameerds]

• eliminated the const_cast by improving template parameters to the SetVector

[sameerds]

llvm/include/llvm/ADT/GenericCycleInfo.h

110–111

Actually it's not about what the const is applied to. The simple fact is that when you lookup in a container, the argument has to match the key_type. The same compilation error happens with an std::set<Foo*> where you try to call set::count() with a const Foo* argument.

I think I followed the whole thing through to the most appropriate fix, which is to recognize that sometimes, the user of a SetVector wants a vector of Foo* but a set of const Foo*. Updated the SetVector to make that happen. Again, this expectation is identical to LoopInfo.

170

Yes, because BlockSetVectorT is a dependent type.

[foad]

llvm/include/llvm/ADT/SetVector.h

51–54

Since the intention here is to allow key_type and value_type to be different, you should really add some tests for that in unittests/ADT/SetVectorTest.cpp.

[sameerds]

• Added test for SetVector
• Replaced std::vector in CycleInfo with SmallVector to match SmallPtrSet

[foad]

Patch seems fine to me, but I wonder if we need to get more eyes on your SetVector changes. I don't think there is a code owner for ADT. @dblaikie?

[sameerds]

In D146136#4201388, @foad wrote:

Patch seems fine to me, but I wonder if we need to get more eyes on your SetVector changes. I don't think there is a code owner for ADT. @dblaikie?

One good thing is that this not change the way SetVector is currently used. If all the user wants is a vector and a set of the same type, then nothing changed for them. But it does allow a new use-case by giving enough rope. It's difficult to specify static constraints. Can a user have a vector of float and a set of float? Sure they can, as long as they understand the lossy hashing produced by silently converting the float to int when inserting in the set!

[foad]

In D146136#4201439, @sameerds wrote:

In D146136#4201388, @foad wrote:

Patch seems fine to me, but I wonder if we need to get more eyes on your SetVector changes. I don't think there is a code owner for ADT. @dblaikie?

One good thing is that this not change the way SetVector is currently used. If all the user wants is a vector and a set of the same type, then nothing changed for them. But it does allow a new use-case by giving enough rope. It's difficult to specify static constraints. Can a user have a vector of float and a set of float? Sure they can, as long as they understand the lossy hashing produced by silently converting the float to int when inserting in the set!

My only very slight unease was about which methods of SetVector should take key_type and which should take value_type. Is it obvious in all cases? Is there a precedent in STL (or Boost) to guide us?

[sameerds]

In D146136#4201559, @foad wrote:

In D146136#4201439, @sameerds wrote:

In D146136#4201388, @foad wrote:

Patch seems fine to me, but I wonder if we need to get more eyes on your SetVector changes. I don't think there is a code owner for ADT. @dblaikie?

One good thing is that this not change the way SetVector is currently used. If all the user wants is a vector and a set of the same type, then nothing changed for them. But it does allow a new use-case by giving enough rope. It's difficult to specify static constraints. Can a user have a vector of float and a set of float? Sure they can, as long as they understand the lossy hashing produced by silently converting the float to int when inserting in the set!

My only very slight unease was about which methods of SetVector should take key_type and which should take value_type. Is it obvious in all cases? Is there a precedent in STL (or Boost) to guide us?

I couldn't find a precedent in the release versions, at least. I don't know if there are contributing projects currently experimenting with this concept.

But to me, it was reasonably straight-forward to reason about this change because the SetVector already distinguishes between the uses of value_type and key_type. And it matched my intuition that the key_type satisfies constraints required by the set, and so it is only used in methods that rely on the properties provided by the set. Thus only two methods take key_type as argument: contains() and count(). All the other methods use value_type and they only access the vector, relying on its sequential nature. Insertion depends on the set for uniquing, and that's the only place where value_type is implicitly converted to key_type. But the insertion itself takes value_type because its primary purpose is to append to the vector.

Another way to look at the distinction is that the use of the set in any method is entirely an optimization, and hence key_type is used only where the optimization is explicitly opted into. If we look at it that way, then the hypothetical overload "contains(const value_type &V)" should do a linear search in the vector because that's what the programmer wanted when they used the value_type instead of the key_type.

[Pierre-vh]

In D146136#4201718, @sameerds wrote:

In D146136#4201559, @foad wrote:

In D146136#4201439, @sameerds wrote:

In D146136#4201388, @foad wrote:

Patch seems fine to me, but I wonder if we need to get more eyes on your SetVector changes. I don't think there is a code owner for ADT. @dblaikie?

One good thing is that this not change the way SetVector is currently used. If all the user wants is a vector and a set of the same type, then nothing changed for them. But it does allow a new use-case by giving enough rope. It's difficult to specify static constraints. Can a user have a vector of float and a set of float? Sure they can, as long as they understand the lossy hashing produced by silently converting the float to int when inserting in the set!

My only very slight unease was about which methods of SetVector should take key_type and which should take value_type. Is it obvious in all cases? Is there a precedent in STL (or Boost) to guide us?

I couldn't find a precedent in the release versions, at least. I don't know if there are contributing projects currently experimenting with this concept.

But to me, it was reasonably straight-forward to reason about this change because the SetVector already distinguishes between the uses of value_type and key_type. And it matched my intuition that the key_type satisfies constraints required by the set, and so it is only used in methods that rely on the properties provided by the set. Thus only two methods take key_type as argument: contains() and count(). All the other methods use value_type and they only access the vector, relying on its sequential nature. Insertion depends on the set for uniquing, and that's the only place where value_type is implicitly converted to key_type. But the insertion itself takes value_type because its primary purpose is to append to the vector.

Another way to look at the distinction is that the use of the set in any method is entirely an optimization, and hence key_type is used only where the optimization is explicitly opted into. If we look at it that way, then the hypothetical overload "contains(const value_type &V)" should do a linear search in the vector because that's what the programmer wanted when they used the value_type instead of the key_type.

IMO this change makes sense and is a good QoL improvement so I would tend to say it's fine as-is.

Though I would split this into two commits:

• First, commit the CycleInfo change, but use the const_cast and the current API (no SetVector change)
• Then, commit the QoL change to SetVector's API.

That way, if someone, someday says that this change is heresy, it can very easily be reverted without having to understand the rest of this patch.

[foad]

IMO this change makes sense and is a good QoL improvement so I would tend to say it's fine as-is.

Agreed.

Though I would split this into two commits:

Personally I don't mind whether you want to split it or not.

[sameerds]

In D146136#4223118, @Pierre-vh wrote:

Though I would split this into two commits:

• First, commit the CycleInfo change, but use the const_cast and the current API (no SetVector change)
• Then, commit the QoL change to SetVector's API.

That way, if someone, someday says that this change is heresy, it can very easily be reverted without having to understand the rest of this patch.

Well, they can't revert the change to SetVector because the change to CycleInfo will depend on it! And the "rest of the patch" is really just a well-defined use-case for the change to SetVector. Submitting as a single patch.

llvm/include/llvm/ADT/GenericCycleImpl.h

auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool {
     return Child == Ptr.get();
   });
   assert(Pos != CurrentContainer.end());
   NewParent->Children.push_back(std::move(*Pos));
   *Pos = std::move(CurrentContainer.back());
   CurrentContainer.pop_back();
   Child->ParentCycle = NewParent;
 
-  NewParent->Blocks.insert(NewParent->Blocks.end(), Child->block_begin(),
-                           Child->block_end());
+  NewParent->Blocks.insert(Child->block_begin(), Child->block_end());
 
   for (auto &It : BlockMapTopLevel)
     if (It.second == Child)
       It.second = NewParent;
 }
 
 /// \brief Main function of the cycle info computations.
 template <typename ContextT>
do {
         } else {
           LLVM_DEBUG(errs()
                      << "known child cycle "
                      << Info.Context.print(BlockParent->getHeader()) << "\n");
         }
       } else {
         Info.BlockMap.try_emplace(Block, NewCycle.get());
         assert(!is_contained(NewCycle->Blocks, Block));
-        NewCycle->Blocks.push_back(Block);
+        NewCycle->Blocks.insert(Block);
         ProcessPredecessors(Block);
         Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());
       }
     } while (!Worklist.empty());
 
     Info.TopLevelCycles.push_back(std::move(NewCycle));
   }
 

llvm/include/llvm/ADT/GenericCycleInfo.h

 /// - In the absence of irreducible control flow, the cycles are
 ///   exactly the natural loops in the program.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_GENERICCYCLEINFO_H
 #define LLVM_ADT_GENERICCYCLEINFO_H
 
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/GenericSSAContext.h"
 #include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Debug.h"
-#include "llvm/Support/Printable.h"
 #include "llvm/Support/raw_ostream.h"
-#include <vector>
 
 namespace llvm {
 
 template <typename ContextT> class GenericCycleInfo;
 template <typename ContextT> class GenericCycleInfoCompute;
 
 /// A possibly irreducible generalization of a \ref Loop.
 template <typename ContextT> class GenericCycle {
private:
   /// unnecessary memory use.
   SmallVector<BlockT *, 1> Entries;
 
   /// Child cycles, if any.
   std::vector<std::unique_ptr<GenericCycle>> Children;
 
   /// Basic blocks that are contained in the cycle, including entry blocks,
   /// and including blocks that are part of a child cycle.
-  std::vector<BlockT *> Blocks;
+  using BlockSetVectorT = SetVector<BlockT *, SmallVector<BlockT *, 8>,
+                                    SmallPtrSet<const BlockT *, 8>>;
+  BlockSetVectorT Blocks;
 
   /// Depth of the cycle in the tree. The root "cycle" is at depth 0.
   ///
   /// \note Depths are not necessarily contiguous. However, child loops always
   ///       have strictly greater depth than their parents, and sibling loops
   ///       always have the same depth.
   unsigned Depth = 0;
 
   void clear() {
     Entries.clear();
     Children.clear();
     Blocks.clear();
     Depth = 0;
     ParentCycle = nullptr;
   }
 
   void appendEntry(BlockT *Block) { Entries.push_back(Block); }
-  void appendBlock(BlockT *Block) { Blocks.push_back(Block); }
+  void appendBlock(BlockT *Block) { Blocks.insert(Block); }
 
   GenericCycle(const GenericCycle &) = delete;
   GenericCycle &operator=(const GenericCycle &) = delete;
   GenericCycle(GenericCycle &&Rhs) = delete;
   GenericCycle &operator=(GenericCycle &&Rhs) = delete;
 
 public:
   GenericCycle() = default;
 
   /// \brief Whether the cycle is a natural loop.
   bool isReducible() const { return Entries.size() == 1; }
 
   BlockT *getHeader() const { return Entries[0]; }
 
   const SmallVectorImpl<BlockT *> & getEntries() const {
     return Entries;
   }
 
   /// \brief Return whether \p Block is an entry block of the cycle.
   bool isEntry(const BlockT *Block) const {
     return is_contained(Entries, Block);
   }
 
   /// \brief Return whether \p Block is contained in the cycle.
-  bool contains(const BlockT *Block) const {
-    return is_contained(Blocks, Block);
-  }
+  bool contains(const BlockT *Block) const { return Blocks.contains(Block); }
 
   /// \brief Returns true iff this cycle contains \p C.
   ///
   /// Note: Non-strict containment check, i.e. returns true if C is the
   /// same cycle.
   bool contains(const GenericCycle *C) const;
 
   const GenericCycle *getParentCycle() const { return ParentCycle; }
public:
   iterator_range<const_child_iterator> children() const {
     return llvm::make_range(const_child_iterator{Children.begin()},
                             const_child_iterator{Children.end()});
   }
   //@}
 
   /// Iteration over blocks in the cycle (including entry blocks).
   //@{
-  using const_block_iterator = typename std::vector<BlockT *>::const_iterator;
+  using const_block_iterator = typename BlockSetVectorT::const_iterator;
 
   const_block_iterator block_begin() const {
     return const_block_iterator{Blocks.begin()};
   }
   const_block_iterator block_end() const {
     return const_block_iterator{Blocks.end()};
   }
   size_t getNumBlocks() const { return Blocks.size(); }

llvm/include/llvm/ADT/SetVector.h

 
 namespace llvm {
 
 /// A vector that has set insertion semantics.
 ///
 /// This adapter class provides a way to keep a set of things that also has the
 /// property of a deterministic iteration order. The order of iteration is the
 /// order of insertion.
+///
+/// The key and value types are derived from the Set and Vector types
+/// respectively. This allows the vector-type operations and set-type operations
+/// to have different types. In particular, this is useful when storing pointers
+/// as "Foo *" values but looking them up as "const Foo *" keys.
+///
+/// No constraint is placed on the key and value types, although it is assumed
+/// that value_type can be converted into key_type for insertion. Users must be
+/// aware of any loss of information in this conversion.
 template <typename T, typename Vector = std::vector<T>,
           typename Set = DenseSet<T>>
 class SetVector {
 public:
-  using value_type = T;
-  using key_type = T;
-  using reference = T&;
-  using const_reference = const T&;
+  using value_type = typename Vector::value_type;
+  using key_type = typename Set::key_type;
+  using reference = value_type &;
+  using const_reference = const value_type &;
   using set_type = Set;
   using vector_type = Vector;
   using iterator = typename vector_type::const_iterator;
   using const_iterator = typename vector_type::const_iterator;
   using reverse_iterator = typename vector_type::const_reverse_iterator;
   using const_reverse_iterator = typename vector_type::const_reverse_iterator;
   using size_type = typename vector_type::size_type;
 
   /// Construct an empty SetVector
   SetVector() = default;
 
   /// Initialize a SetVector with a range of elements
   template<typename It>
   SetVector(It Start, It End) {
     insert(Start, End);
   }
 
-  ArrayRef<T> getArrayRef() const { return vector_; }
+  ArrayRef<value_type> getArrayRef() const { return vector_; }
 
   /// Clear the SetVector and return the underlying vector.
   Vector takeVector() {
     set_.clear();
     return std::move(vector_);
   }
 
   /// Determine if the SetVector is empty or not.
public:
   }
 
   /// Get a const_reverse_iterator to the beginning of the SetVector.
   const_reverse_iterator rend() const {
     return vector_.rend();
   }
 
   /// Return the first element of the SetVector.
-  const T &front() const {
+  const value_type &front() const {
     assert(!empty() && "Cannot call front() on empty SetVector!");
     return vector_.front();
   }
 
   /// Return the last element of the SetVector.
-  const T &back() const {
+  const value_type &back() const {
     assert(!empty() && "Cannot call back() on empty SetVector!");
     return vector_.back();
   }
 
   /// Index into the SetVector.
   const_reference operator[](size_type n) const {
     assert(n < vector_.size() && "SetVector access out of range!");
     return vector_[n];
public:
 
   /// Remove the last element of the SetVector.
   void pop_back() {
     assert(!empty() && "Cannot remove an element from an empty SetVector!");
     set_.erase(back());
     vector_.pop_back();
   }
 
-  [[nodiscard]] T pop_back_val() {
-    T Ret = back();
+  [[nodiscard]] value_type pop_back_val() {
+    value_type Ret = back();
     pop_back();
     return Ret;
   }
 
   bool operator==(const SetVector &that) const {
     return vector_ == that.vector_;
   }
 

llvm/include/llvm/ADT/SmallSet.h

class SmallSet {
   using mutable_iterator = typename SmallVector<T, N>::iterator;
 
   // In small mode SmallPtrSet uses linear search for the elements, so it is
   // not a good idea to choose this value too high. You may consider using a
   // DenseSet<> instead if you expect many elements in the set.
   static_assert(N <= 32, "N should be small");
 
 public:
+  using key_type = T;
   using size_type = size_t;
+  using value_type = T;
   using const_iterator = SmallSetIterator<T, N, C>;
 
   SmallSet() = default;
 
   [[nodiscard]] bool empty() const { return Vector.empty() && Set.empty(); }
 
   size_type size() const {
     return isSmall() ? Vector.size() : Set.size();

llvm/unittests/ADT/SetVectorTest.cpp

 //===- llvm/unittest/ADT/SetVector.cpp ------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // SetVector unit tests.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 TEST(SetVector, EraseTest) {
   SetVector<int> S;
   S.insert(0);
   S.insert(1);
TEST(SetVector, ContainsTest) {
   EXPECT_FALSE(S.contains(-1));
 
   S.insert(2);
   EXPECT_TRUE(S.contains(2));
 
   S.remove(2);
   EXPECT_FALSE(S.contains(2));
 }
+
+TEST(SetVector, ConstPtrKeyTest) {
+  SetVector<int *, SmallVector<int *, 8>, SmallPtrSet<const int *, 8>> S, T;
+  int i, j, k, m, n;
+
+  S.insert(&i);
+  S.insert(&j);
+  S.insert(&k);
+
+  EXPECT_TRUE(S.contains(&i));
+  EXPECT_TRUE(S.contains(&j));
+  EXPECT_TRUE(S.contains(&k));
+
+  EXPECT_TRUE(S.contains((const int *)&i));
+  EXPECT_TRUE(S.contains((const int *)&j));
+  EXPECT_TRUE(S.contains((const int *)&k));
+
+  EXPECT_TRUE(S.contains(S[0]));
+  EXPECT_TRUE(S.contains(S[1]));
+  EXPECT_TRUE(S.contains(S[2]));
+
+  S.remove(&k);
+  EXPECT_FALSE(S.contains(&k));
+  EXPECT_FALSE(S.contains((const int *)&k));
+
+  T.insert(&j);
+  T.insert(&m);
+  T.insert(&n);
+
+  EXPECT_TRUE(S.set_union(T));
+  EXPECT_TRUE(S.contains(&m));
+  EXPECT_TRUE(S.contains((const int *)&m));
+
+  S.set_subtract(T);
+  EXPECT_FALSE(S.contains(&j));
+  EXPECT_FALSE(S.contains((const int *)&j));
+}