[SLP] Limit compilation time of look-ahead operand reordering heuristic.

[vporpo]

Summary

This is a fix for the compilation time increase caused by D60897. It caps the exploration performed by the look-ahead heuristic.

[vporpo]

Please try this patch @phosek . Please let us know if it fixes the compilation-time issue. Thanks!

[lebedev.ri]

The defaults should probably be a new cl::opt<int>, and would be good to document the defaults somehow?

[vporpo]

Yes, I agree @lebedev.ri they should be options with some documentation describing what they do.
Let's first get a confirmation that this is the actual cause of the compilation-time increase.

[phosek]

I'm getting the following error with this change:

ld.lld: llvm-project/llvm/include/llvm/IR/User.h:170: llvm::Value *llvm::User::getOperand(unsigned int) const: Assertion `i < NumUserOperands && "getOperand() out of range!"' failed.

[vporpo]

Fixed the failure.

[vporpo]

Oops sorry about that @phosek . I wonder how none of the lit tests failed. Please try this one.

[phosek]

I tried the updated version and the build successfully finished and the build times are back to normal. Thank you for looking into this so promptly. Is it possible to land this change?

[vporpo]

Thank you @phosek for testing it, I am glad it fixed the issue.
Let me add reviewers. I will push the change as soon as it gets approved by someone.

[rcorcs]

Just a very minor thing.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

158

Maybe it is better to call this variable Look*A*headOperandsBudget, similar to the other ones.

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

158

Yes, good point.

[vporpo]

Updated option variable names.

[phosek]

Do you think you'll be able to land this change today or shall I revert D60897? Our bots have been broken since Thursday and we don't have any test coverage for our toolchain as a consequence.

[vporpo]

Let's ping some of the reviewers.
@RKSimon @ABataev @dtemirbulatov any comments?

[ABataev]

Tests?

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

921

Do you really need this limit?

[vporpo]

Not sure what kind of test would be suitable for this change. It simply restricts the look-ahead heuristic to not visit more than 2 operands and 2 uses, which is not something visible in the output IR.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

921

Yes, because it could be a call /phi instruction with many operands.

[ABataev]

In D63948#1565229, @vporpo wrote:

Not sure what kind of test would be suitable for this change. It simply restricts the look-ahead heuristic to not visit more than 2 operands and 2 uses, which is not something visible in the output IR.

You still need the test that demonstrates the effect of this change. You need to show that the option really affects the vectorization somehow.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

921

Does this really the cause of the problems? It would be good to see some additional investigation if this is really required.

[vporpo]

OK let me try to create a test that causes a change in the IR.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

921

This can cause problems if you have a look-ahead depth > 2. Consider the case where you have chains of phis or calls. You can spend a lot of time visiting all their operands.
Though I agree, restricting the uses is more important.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

921

I would suggest investigating if this is really required. Most probably, users lookup budget should be enough. If the second change is really required, I would suggest to prepare it as a separate patch.

[chandlerc]

Since this review is ongoing, please revert the original patch to unblock people. There is no harm in reverting and landing with the fix once it is ready. =]

[rupprecht]

We're seeing several compilation timeouts as well. Temporarily reverted in r364846 since this review is ongoing.

[vporpo]

Abandoning this patch. The fix can now be found in D60897.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

static cl::opt<unsigned> MinTreeSize(
     cl::desc("Only vectorize small trees if they are fully vectorizable"));
 
 // The maximum depth that the look-ahead score heuristic will explore.
 // The higher this value, the higher the compilation time overhead.
 static cl::opt<int> LookAheadMaxDepth(
     "slp-max-look-ahead-depth", cl::init(2), cl::Hidden,
     cl::desc("The maximum look-ahead depth for operand reordering scores"));
 
+// Look-ahead explores the operands of the bundle. To avoid compilation time
+// increase we limit the number of operands visited to this value.
+static cl::opt<unsigned> LookaheadOperandsBudget(
+    "slp-look-ahead-operands-budget", cl::init(2), cl::Hidden,
+    cl::desc("The maximum number of operands to consider while visiting the "
+             "predecessors. This prevents compilation time increase"));
+
+// Look-ahead goes through the users ot the bundle to calculate the users cost
+// in getExternalUsesCost(). To avoid compilation time increase we limit the
+// number of users visited to this value.
+static cl::opt<unsigned> LookaheadUsersBudget(
+    "slp-look-ahead-users-budget", cl::init(2), cl::Hidden,
+    cl::desc("The maximum number of users to visit while visiting the "
+             "predecessors. This prevents compilation time increase."));
+
 static cl::opt<bool>
     ViewSLPTree("view-slp-tree", cl::Hidden,
                 cl::desc("Display the SLP trees with Graphviz"));
 
 // Limit the number of alias checks. The limit is chosen so that
 // it has no negative effect on the llvm benchmarks.
 static const unsigned AliasedCheckLimit = 10;
 
int getExternalUsesCost(const std::pair<Value *, int> &LHS,
       int Cost = 0;
       SmallVector<std::pair<Value *, int>, 2> Values = {LHS, RHS};
       for (int Idx = 0, IdxE = Values.size(); Idx != IdxE; ++Idx) {
         Value *V = Values[Idx].first;
         // Calculate the absolute lane, using the minimum relative lane of LHS
         // and RHS as base and Idx as the offset.
         int Ln = std::min(LHS.second, RHS.second) + Idx;
         assert(Ln >= 0 && "Bad lane calculation");
+        unsigned UsersBudget = LookaheadUsersBudget;
         for (User *U : V->users()) {
           if (const TreeEntry *UserTE = R.getTreeEntry(U)) {
             // The user is in the VectorizableTree. Check if we need to insert.
             auto It = llvm::find(UserTE->Scalars, U);
             assert(It != UserTE->Scalars.end() && "U is in UserTE");
             int UserLn = std::distance(UserTE->Scalars.begin(), It);
             assert(UserLn >= 0 && "Bad lane");
             if (UserLn != Ln)
               Cost += UserInDiffLaneCost;
           } else {
             // Check if the user is in the look-ahead code.
             auto It2 = InLookAheadValues.find(U);
             if (It2 != InLookAheadValues.end()) {
               // The user is in the look-ahead code. Check the lane.
               if (It2->second != Ln)
                 Cost += UserInDiffLaneCost;
             } else {
               // The user is neither in SLP tree nor in the look-ahead code.
               Cost += ExternalUseCost;
             }
           }
+          // Limit the number of visited uses to cap compilation time.
+          if (--UsersBudget == 0)
+            break;
         }
       }
       return Cost;
     }
 
     /// Go through the operands of \p LHS and \p RHS recursively until \p
     /// MaxLevel, and return the cummulative score. For example:
     /// \verbatim
int getScoreAtLevelRec(const std::pair<Value *, int> &LHS,
       InLookAheadValues[V1] = Lane1;
       InLookAheadValues[V2] = Lane2;
 
       // Contains the I2 operand indexes that got matched with I1 operands.
       SmallSet<unsigned, 4> Op2Used;
 
       // Recursion towards the operands of I1 and I2. We are trying all possbile
       // operand pairs, and keeping track of the best score.
-      for (unsigned OpIdx1 = 0, NumOperands1 = I1->getNumOperands();
+      for (unsigned OpIdx1 = 0,
+                    NumOperands1 = std::min(I1->getNumOperands(),
+                                            LookaheadOperandsBudget.getValue());
            OpIdx1 != NumOperands1; ++OpIdx1) {
         // Try to pair op1I with the best operand of I2.
         int MaxTmpScore = 0;
         unsigned MaxOpIdx2 = 0;
         bool FoundBest = false;
         // If I2 is commutative try all combinations.
         unsigned FromIdx = isCommutative(I2) ? 0 : OpIdx1;
+        // Limit the number of operands to visit to reduce compilation time.
         unsigned ToIdx = isCommutative(I2)
-                             ? I2->getNumOperands()
+                             ? std::min(I2->getNumOperands(),
+                                        LookaheadOperandsBudget.getValue())
                              : std::min(I2->getNumOperands(), OpIdx1 + 1);
         assert(FromIdx <= ToIdx && "Bad index");
         for (unsigned OpIdx2 = FromIdx; OpIdx2 != ToIdx; ++OpIdx2) {
           // Skip operands already paired with OpIdx1.
           if (Op2Used.count(OpIdx2))
             continue;
           // Recursively calculate the cost at each level
           int TmpScore = getScoreAtLevelRec({I1->getOperand(OpIdx1), Lane1},