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

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

indent?

[bjope]

lib/CodeGen/CodeGenPrepare.cpp

2653

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

2713

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).

[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.

lib/CodeGen/CodeGenPrepare.cpp

 };
 
 /// 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;
+  SmallPtrSet<PHINode *, 32> 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; }
+  SmallPtrSet<PHINode *, 32>& 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(); }
 
private:
 
   /// The field in which the AddrModes differ, when we have more than one.
   ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
 
   /// Are the AddrModes that we have all just equal to their original values?
   bool AllAddrModesTrivial = true;
 
   /// Common Type for all different fields in addressing modes.
   Type *CommonType;
 
   /// SimplifyQuery for simplifyInstruction utility.
   const SimplifyQuery &SQ;
 
   /// Original Address.
   ValueInBB Original;
 
 public:
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) {
+                    SmallPtrSet<PHINode *, 32> &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;
private:
   /// 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.
     SmallSetVector<PHIPair, 8> Matched;
     SmallPtrSet<PHINode *, 8> WillNotMatch;
-    SmallSetVector<PHINode *, 32> &PhiNodesToMatch = ST.newPhiNodes();
+    SmallPtrSet<PHINode *, 32> &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()) {