Use a data structure better suited for large sets in SimplificationTracker.

[tamur]

Summary

D44571 changed SimplificationTracker to use SmallSetVector to keep phi nodes. As a result, when the number of phi nodes is large, the build time performance suffers badly. When building for power pc, we have a case where there are more than 600.000 nodes, and it takes too long to compile.

In this change, I partially revert D44571 to use SmallPtrSet, which does an acceptable job with any number of elements. In the original patch, having a deterministic iteration order was mentioned as a motivation, however I think it only applies to the nodes already matched in MatchPhiSet method, which I did not touch.

[bjope]

If I remember correctly a problem was that depending on the order iteration at line 3011

while (PhiNodesToMatch.size())

the end result (which PHI node that others are found out to be equivalent to) could be different. Quite annoying when trying to debug something, and when turning on -print-after-all or rebuilding using -g the result is different.

Have you, for example, tested to run llc with and without -print-after-all, or -debug, or some other options that might impact memory layout. And have you checked that we still are debug invariant (always getting the same result regardless if you build the compiler using -g, or a different -O level)?
Another way to test it could be to build two versions of llc. One that inserts at the end of AllPhiNodes and one the inserts at the front (using the SmallSetVector and some hacks to insert from different ends in the vector). Then run a bunch of tests and compare the result.

Btw, when you say 600.000 PHI nodes, is that in the same SimplificationTracker instance?
If 600.000 is some kind of total, what is the average size of AllPhiNodes when MatchPhiSet is called? Perhaps the size N (currently set to 32) of the SmallSetVector can be tuned.

lib/CodeGen/CodeGenPrepare.cpp

2651 ↗

(On Diff #172249)

The comment about SetVector is no longer valid with this patch.

[tamur]

Thank you for the explanation. OK, neither SmallPtrSet nor SmallSetVector seems suitable for this specific task, so I created a simple set implementation, that is fast and has the same iteration order with SmallSetVector; so I don't expect any behaviour change. (The problem with SmallSetVector is that it actually removes elements from the underlying vector and shifts all others, which is bad when we have many elements).

I arrived at 600.000 by putting a static variable that peeks the AllPhiNodes.size() and acts as a "maximum value tracker" inside SimplificationTracker::insertNewPhi, so it should correspond to a single activation. The code I am trying to compile is open source (EPL 1.0), if you are curious or want to verify:

• download https://www.coin-or.org/download/source/Cbc/Cbc-2.9.5.tgz
• compile Cbc-2.9.5/Cbc/src/CbcSolver.cpp with -O3 --target=powerpc64le -std=gnu++17 options.

[skatkov]

LGTM, please wait a bit and if Bjorn does not object, feel free to land.

lib/CodeGen/CodeGenPrepare.cpp

2755 ↗

(On Diff #172864)

indent?

[bjope]

lib/CodeGen/CodeGenPrepare.cpp

2713 ↗

(On Diff #172864)

Imagine that we insert the value 1,2,3,4,5 into the set, then the NodeList will be [1, 2, 3, 4, 5].
Now we remove "3", then the NodeList is untouched and FirstValidElement still points at the beginning of the NodeList.
If we later inset "3" again, then the NodeList will become [1, 2, 3, 4, 5, 3].
When iterating we now will get the order 1,2,3,4,5 and not the expected 1,2,4,5,3 (assuming that we really expect to get the insertion order).

I'm not sure if the above will ever happen for the specific use case in CodeGenPrepare, but looking at this as a general set implementation it seems faulty.

One solution, seeing this as a set of pointers, could be to now allow nullptr in the set (so add an assert for the in "insert"). And then we should not only move FirstValidElement forward here, we also need to scan the NodeList starting at FirstValidElement and replace any found entry matching Ptr with a nullptr (there should be exactly one such entry since it is a unique set).

2790 ↗

(On Diff #172864)

nit: I think it should say "elements are iterated" or "elements will be iterated"

[skatkov]

Just a note, there is a specific usage of this data structure.
Phi nodes are inserted in the initial step without any removals and then only removals are used.

So we should not see something like delete-insert.
So while data structure really suffers from what Bjorn wrote but in this specific application of this data structure I do not expect any problems...

[bjope]

In D54007#1289855, @skatkov wrote:

Just a note, there is a specific usage of this data structure.
Phi nodes are inserted in the initial step without any removals and then only removals are used.

So we should not see something like delete-insert.
So while data structure really suffers from what Bjorn wrote but in this specific application of this data structure I do not expect any problems...

Ok. Just worried that someone might find this set implementation nifty, trying to reuse it in some other part of the code or moving it to ADT, without considering this limitation regarding delete-insert.
If the extra cleanup in the NodeList is costly we could at least add some comment explaining this in the description of the set (and/or in the erase method). And maybe we can assert somehow that there are no inserts after erase (at insert the size of the NodeList and the size of the NodeSet must be equal)?
Still, if there is no big performance issue with making the data structure more general (also supporting delete-insert), such a solution could be accepatable as well.

[skatkov]

In D54007#1289874, @bjope wrote:

In D54007#1289855, @skatkov wrote:

Just a note, there is a specific usage of this data structure.
Phi nodes are inserted in the initial step without any removals and then only removals are used.

So we should not see something like delete-insert.
So while data structure really suffers from what Bjorn wrote but in this specific application of this data structure I do not expect any problems...

Ok. Just worried that someone might find this set implementation nifty, trying to reuse it in some other part of the code or moving it to ADT, without considering this limitation regarding delete-insert.

Completely agreed!

[tamur]

Oh, I had completely misseed the remove-and-add-again-later case, thanks for pointing out. I changed the underlying set from SmallPtrSet to SmallDenseMap to let it point to the valid index at the vector; I think this is the only way to handle removing in constant time (Allowing nullptr does not seem enough). It made the compilation time for my huge case to go up from 96 seconds to maybe 98 seconds, and should be unnoticable in 'normal' cases.

[bjope]

LGTM now (might wanna wait for @skatkov to take a look at the last changes as well).

[skatkov]

LGTM as well

[tamur]

Thank you both for the review. Committing.

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

private:
   bool isProfitableToFoldIntoAddressingMode(Instruction *I,
                                             ExtAddrMode &AMBefore,
                                             ExtAddrMode &AMAfter);
   bool valueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
   bool isPromotionProfitable(unsigned NewCost, unsigned OldCost,
                              Value *PromotedOperand) const;
 };
 
+class PhiNodeSet;
+
+/// An iterator for PhiNodeSet.
+class PhiNodeSetIterator {
+  PhiNodeSet * const Set;
+  size_t CurrentIndex = 0;
+
+public:
+  /// The constructor. Start should point to either a valid element, or be equal
+  /// to the size of the underlying SmallVector of the PhiNodeSet.
+  PhiNodeSetIterator(PhiNodeSet * const Set, size_t Start);
+  PHINode * operator*() const;
+  PhiNodeSetIterator& operator++();
+  bool operator==(const PhiNodeSetIterator &RHS) const;
+  bool operator!=(const PhiNodeSetIterator &RHS) const;
+};
+
+/// Keeps a set of PHINodes.
+///
+/// This is a minimal set implementation for a specific use case:
+/// It is very fast when there are very few elements, but also provides good
+/// performance when there are many. It is similar to SmallPtrSet, but also
+/// provides iteration by insertion order, which is deterministic and stable
+/// across runs. It is also similar to SmallSetVector, but provides removing
+/// elements in O(1) time. This is achieved by not actually removing the element
+/// from the underlying vector, so comes at the cost of using more memory, but
+/// that is fine, since PhiNodeSets are used as short lived objects.
+class PhiNodeSet {
+  friend class PhiNodeSetIterator;
+
+  using MapType = SmallDenseMap<PHINode *, size_t, 32>;
+  using iterator =  PhiNodeSetIterator;
+
+  /// Keeps the elements in the order of their insertion in the underlying
+  /// vector. To achieve constant time removal, it never deletes any element.
+  SmallVector<PHINode *, 32> NodeList;
+
+  /// Keeps the elements in the underlying set implementation. This (and not the
+  /// NodeList defined above) is the source of truth on whether an element
+  /// is actually in the collection.
+  MapType NodeMap;
+
+  /// Points to the first valid (not deleted) element when the set is not empty
+  /// and the value is not zero. Equals to the size of the underlying vector
+  /// when the set is empty. When the value is 0, as in the beginning, the
+  /// first element may or may not be valid.
+  size_t FirstValidElement = 0;
+
+public:
+  /// Inserts a new element to the collection.
+  /// \returns true if the element is actually added, i.e. was not in the
+  /// collection before the operation.
+  bool insert(PHINode *Ptr) {
+    if (NodeMap.insert(std::make_pair(Ptr, NodeList.size())).second) {
+      NodeList.push_back(Ptr);
+      return true;
+    }
+    return false;
+  }
+
+  /// Removes the element from the collection.
+  /// \returns whether the element is actually removed, i.e. was in the
+  /// collection before the operation.
+  bool erase(PHINode *Ptr) {
+    auto it = NodeMap.find(Ptr);
+    if (it != NodeMap.end()) {
+      NodeMap.erase(Ptr);
+      SkipRemovedElements(FirstValidElement);
+      return true;
+    }
+    return false;
+  }
+
+  /// Removes all elements and clears the collection.
+  void clear() {
+    NodeMap.clear();
+    NodeList.clear();
+    FirstValidElement = 0;
+  }
+
+  /// \returns an iterator that will iterate the elements in the order of
+  /// insertion.
+  iterator begin() {
+    if (FirstValidElement == 0)
+      SkipRemovedElements(FirstValidElement);
+    return PhiNodeSetIterator(this, FirstValidElement);
+  }
+
+  /// \returns an iterator that points to the end of the collection.
+  iterator end() { return PhiNodeSetIterator(this, NodeList.size()); }
+
+  /// Returns the number of elements in the collection.
+  size_t size() const {
+    return NodeMap.size();
+  }
+
+  /// \returns 1 if the given element is in the collection, and 0 if otherwise.
+  size_t count(PHINode *Ptr) const {
+    return NodeMap.count(Ptr);
+  }
+
+private:
+  /// Updates the CurrentIndex so that it will point to a valid element.
+  ///
+  /// If the element of NodeList at CurrentIndex is valid, it does not
+  /// change it. If there are no more valid elements, it updates CurrentIndex
+  /// to point to the end of the NodeList.
+  void SkipRemovedElements(size_t &CurrentIndex) {
+    while (CurrentIndex < NodeList.size()) {
+      auto it = NodeMap.find(NodeList[CurrentIndex]);
+      // If the element has been deleted and added again later, NodeMap will
+      // point to a different index, so CurrentIndex will still be invalid.
+      if (it != NodeMap.end() && it->second == CurrentIndex)
+        break;
+      ++CurrentIndex;
+    }
+  }
+};
+
+PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *const Set, size_t Start)
+    : Set(Set), CurrentIndex(Start) {}
+
+PHINode * PhiNodeSetIterator::operator*() const {
+  assert(CurrentIndex < Set->NodeList.size() &&
+         "PhiNodeSet access out of range");
+  return Set->NodeList[CurrentIndex];
+}
+
+PhiNodeSetIterator& PhiNodeSetIterator::operator++() {
+  assert(CurrentIndex < Set->NodeList.size() &&
+         "PhiNodeSet access out of range");
+  ++CurrentIndex;
+  Set->SkipRemovedElements(CurrentIndex);
+  return *this;
+}
+
+bool PhiNodeSetIterator::operator==(const PhiNodeSetIterator &RHS) const {
+  return CurrentIndex == RHS.CurrentIndex;
+}
+
+bool PhiNodeSetIterator::operator!=(const PhiNodeSetIterator &RHS) const {
+  return CurrentIndex != RHS.CurrentIndex;
+}
+
 /// Keep track of simplification of Phi nodes.
 /// Accept the set of all phi nodes and erase phi node from this set
 /// if it is simplified.
 class SimplificationTracker {
   DenseMap<Value *, Value *> Storage;
   const SimplifyQuery &SQ;
-  // Tracks newly created Phi nodes. We use a SetVector to get deterministic
-  // order when iterating over the set in MatchPhiSet.
-  SmallSetVector<PHINode *, 32> AllPhiNodes;
+  // Tracks newly created Phi nodes. The elements are iterated by insertion
+  // order.
+  PhiNodeSet AllPhiNodes;
   // Tracks newly created Select nodes.
   SmallPtrSet<SelectInst *, 32> AllSelectNodes;
 
 public:
   SimplificationTracker(const SimplifyQuery &sq)
       : SQ(sq) {}
 
   Value *Get(Value *V) {
while (!WorkList.empty()) {
         continue;
       if (auto *PI = dyn_cast<Instruction>(P))
         if (Value *V = SimplifyInstruction(cast<Instruction>(PI), SQ)) {
           for (auto *U : PI->users())
             WorkList.push_back(cast<Value>(U));
           Put(PI, V);
           PI->replaceAllUsesWith(V);
           if (auto *PHI = dyn_cast<PHINode>(PI))
-            AllPhiNodes.remove(PHI);
+            AllPhiNodes.erase(PHI);
           if (auto *Select = dyn_cast<SelectInst>(PI))
             AllSelectNodes.erase(Select);
           PI->eraseFromParent();
         }
     }
     return Get(Val);
   }
 
   void Put(Value *From, Value *To) {
     Storage.insert({ From, To });
   }
 
   void ReplacePhi(PHINode *From, PHINode *To) {
     Value* OldReplacement = Get(From);
     while (OldReplacement != From) {
       From = To;
       To = dyn_cast<PHINode>(OldReplacement);
       OldReplacement = Get(From);
     }
     assert(Get(To) == To && "Replacement PHI node is already replaced.");
     Put(From, To);
     From->replaceAllUsesWith(To);
-    AllPhiNodes.remove(From);
+    AllPhiNodes.erase(From);
     From->eraseFromParent();
   }
 
-  SmallSetVector<PHINode *, 32>& newPhiNodes() { return AllPhiNodes; }
+  PhiNodeSet& newPhiNodes() { return AllPhiNodes; }
 
   void insertNewPhi(PHINode *PN) { AllPhiNodes.insert(PN); }
 
   void insertNewSelect(SelectInst *SI) { AllSelectNodes.insert(SI); }
 
   unsigned countNewPhiNodes() const { return AllPhiNodes.size(); }
 
   unsigned countNewSelectNodes() const { return AllSelectNodes.size(); }
Value *findCommon(FoldAddrToValueMapping &Map) {
     }
     return Result;
   }
 
   /// Try to match PHI node to Candidate.
   /// Matcher tracks the matched Phi nodes.
   bool MatchPhiNode(PHINode *PHI, PHINode *Candidate,
                     SmallSetVector<PHIPair, 8> &Matcher,
-                    SmallSetVector<PHINode *, 32> &PhiNodesToMatch) {
+                    PhiNodeSet &PhiNodesToMatch) {
     SmallVector<PHIPair, 8> WorkList;
     Matcher.insert({ PHI, Candidate });
     WorkList.push_back({ PHI, Candidate });
     SmallSet<PHIPair, 8> Visited;
     while (!WorkList.empty()) {
       auto Item = WorkList.pop_back_val();
       if (!Visited.insert(Item).second)
         continue;
bool MatchPhiNode(PHINode *PHI, PHINode *Candidate,
     return true;
   }
 
   /// For the given set of PHI nodes (in the SimplificationTracker) try
   /// to find their equivalents.
   /// Returns false if this matching fails and creation of new Phi is disabled.
   bool MatchPhiSet(SimplificationTracker &ST, bool AllowNewPhiNodes,
                    unsigned &PhiNotMatchedCount) {
-    // Use a SetVector for Matched to make sure we do replacements (ReplacePhi)
-    // in a deterministic order below.
+    // Matched and PhiNodesToMatch iterate their elements in a deterministic
+    // order, so the replacements (ReplacePhi) are also done in a deterministic
+    // order.
     SmallSetVector<PHIPair, 8> Matched;
     SmallPtrSet<PHINode *, 8> WillNotMatch;
-    SmallSetVector<PHINode *, 32> &PhiNodesToMatch = ST.newPhiNodes();
+    PhiNodeSet &PhiNodesToMatch = ST.newPhiNodes();
     while (PhiNodesToMatch.size()) {
       PHINode *PHI = *PhiNodesToMatch.begin();
 
       // Add us, if no Phi nodes in the basic block we do not match.
       WillNotMatch.clear();
       WillNotMatch.insert(PHI);
 
       // Traverse all Phis until we found equivalent or fail to do that.
while (PhiNodesToMatch.size()) {
         continue;
       }
       // If we are not allowed to create new nodes then bail out.
       if (!AllowNewPhiNodes)
         return false;
       // Just remove all seen values in matcher. They will not match anything.
       PhiNotMatchedCount += WillNotMatch.size();
       for (auto *P : WillNotMatch)
-        PhiNodesToMatch.remove(P);
+        PhiNodesToMatch.erase(P);
     }
     return true;
   }
   /// Fill the placeholder with values from predecessors and simplify it.
   void FillPlaceholders(FoldAddrToValueMapping &Map,
                         SmallVectorImpl<ValueInBB> &TraverseOrder,
                         SimplificationTracker &ST) {
     while (!TraverseOrder.empty()) {