[LoopUtils] Avoid expanding complicated SCEVNAry when rewriteLoopExitValues

[guopeilin]

Details are recorded in https://bugs.llvm.org/show_bug.cgi?id=50442.

[nikic]

Why is this not already covered by the isHighCostExpansion() check?

[lebedev.ri]

I'm not a fan of this direction.
Which stack overflow are you seeing?

llvm/lib/Transforms/Utils/LoopUtils.cpp

1436–1468

Because we expand regardless of the high cost,
because we need to do isValidRewrite() sanity check first,
before calling canLoopBeDeleted(), just in case the latter
returns true and we'd want to expand anyways.

[guopeilin]

In D103007#2776571, @nikic wrote:

Why is this not already covered by the isHighCostExpansion() check?

Firstly，within the function isHighCostExpansion, only the SCEVUDivExpr and SCEVMinMaxExpr could have the chance to return true.
Secondly, even though function isHighCostExpansion return true, the result is used in the following code:

// Only do the rewrite when the ExitValue can be expanded cheaply.
// If LoopCanBeDel is true, rewrite exit value aggressively.
if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
  DeadInsts.push_back(ExitVal);
  continue;
}

And in this case, the variable LoopCanBeDel is true, this means we will expand anyway.
So I guess we need some early-return way to avoid this extremely complicated cases.

[guopeilin]

In D103007#2776598, @lebedev.ri wrote:

I'm not a fan of this direction.
Which stack overflow are you seeing?

The details are that the variable %add.i.2.i can be computed by SCEV, and after expanding the SCEV value, this variable contains thousands of operands.
During ISel, we need to build a SelectionDAG first, so we need to visit all the operands to build SDNodes, and this will exhaust the stack due to plenty of operands.

Also, if you use opt -indvars -S, you can see that the program keeps printing the IR for a very long long time. More specifically, the program keeps printing the replaced variable.

[lebedev.ri]

In D103007#2776920, @guopeilin wrote:

In D103007#2776571, @nikic wrote:

Why is this not already covered by the isHighCostExpansion() check?

Firstly，within the function isHighCostExpansion, only the SCEVUDivExpr and SCEVMinMaxExpr could have the chance to return true.

You are looking at the wrong function.

Secondly, even though function isHighCostExpansion return true, the result is used in the following code:

// Only do the rewrite when the ExitValue can be expanded cheaply.
// If LoopCanBeDel is true, rewrite exit value aggressively.
if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
  DeadInsts.push_back(ExitVal);
  continue;
}

And in this case, the variable LoopCanBeDel is true, this means we will expand anyway.
So I guess we need some early-return way to avoid this extremely complicated cases.

[lebedev.ri]

I'm very wary of more magic numbers.
Could you please specify, is the problem the time the transformation takes,
or it's effect on some further passes?

[guopeilin]

Actually, this transformation doesn't take too much time. However the IR it generated is very long. And this will have a great effect on the further pass. More specifically, the expanding SCEV which replaces the variable %add.i.2.i contains thousands of operands.
So if you use opt -indvars -S, you can see the program keeps printing the IR all the time.
Besides, I use clang -O3 test.cpp and find that the program gets a segment fault with a stack dump like the followings:

...
llvm::sys::RunSignalHandlers()
SignalHandler(int)
llvm::IntegerType::classof(llvm::Type const*)
llvm::isa_impl<llvm::IntegerType, llvm::Type, void>::doit(llvm::Type const&)
llvm::isa_impl_cl<llvm::IntegerType, llvm::Type const*>::doit(llvm::Type const*) 
llvm::isa_impl_wrap<llvm::IntegerType, llvm::Type const*, llvm::Type const*>::doit(llvm::Type const* const&)
llvm::isa_impl_wrap<llvm::IntegerType, llvm::Type* const, llvm::Type const*>::doit(llvm::Type* const&) 
bool llvm::isa<llvm::IntegerType, llvm::Type*>(llvm::Type* const&) 
llvm::cast_retty<llvm::IntegerType, llvm::Type*>::ret_type llvm::cast<llvm::IntegerType, llvm::Type>(llvm::Type*)
llvm::EVT::getEVT(llvm::Type*, bool)
llvm::TargetLoweringBase::getValueType(llvm::DataLayout const&, llvm::Type*, bool) const
llvm::SelectionDAGBuilder::getValueImpl(llvm::Value const*)
llvm::SelectionDAGBuilder::getValue(llvm::Value const*)
llvm::SelectionDAGBuilder::visitSelect(llvm::User const&)
llvm::SelectionDAGBuilder::visit(unsigned int, llvm::User const&)
llvm::SelectionDAGBuilder::getValueImpl(llvm::Value const*)
llvm::SelectionDAGBuilder::getValue(llvm::Value const*)
llvm::SelectionDAGBuilder::visitSelect(llvm::User const&)
llvm::SelectionDAGBuilder::visit(unsigned int, llvm::User const&)
llvm::SelectionDAGBuilder::getValueImpl(llvm::Value const*)
llvm::SelectionDAGBuilder::getValue(llvm::Value const*)
llvm::SelectionDAGBuilder::visitBinary(llvm::User const&, unsigned int)
llvm::SelectionDAGBuilder::visitAdd(llvm::User const&)
llvm::SelectionDAGBuilder::visit(unsigned int, llvm::User const&) 
llvm::SelectionDAGBuilder::getValueImpl(llvm::Value const*)
llvm::SelectionDAGBuilder::getValue(llvm::Value const*)
llvm::SelectionDAGBuilder::visitICmp(llvm::User const&)
(handreds of other function visit and getValue and so on)
...
...
clang-10: error: unable to execute command: Segmentation fault (core dumped)

From the stack dump, we can see that during the building SelectionDAG, visit thousands of operands finally exhaust the stack and left no enough space for a new Value. And the incomplete Value finally causes Segment Fault.
In short, any way that tries to visit the operands generated by expanding the extremely complicated SCEV computed in this test case will get stuck. 1. we using -S to print the IR will get stuck. 2. Building SelectionDAG by visiting all operands will get stuck.
One more thing is that ISel pass is controlled by llc, so I cannot reproduce the segment fault here cause commands opt -indvars test-case.ll | llc doesn't work as I want. This will still get stuck in opt cause it wants to generate IR first. It would be greatly appreciated if you have any ideas about this.

As for the magic number, I guess that the key point is that we need to add a case for complicated SCEV. And there might have another way to determine whether a SCEV is complicated rather than counting the operands.

In D103007#2777055, @lebedev.ri wrote:

I'm very wary of more magic numbers.
Could you please specify, is the problem the time the transformation takes,
or it's effect on some further passes?

[lebedev.ri]

I believe this will be resolved once we no longer expand high-cost SCEV's because we no longer need to check their validity, D108043

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 /// be computed, substitute the exit values from the loop into any instructions
 /// outside of the loop that use the final values of the current expressions.
 /// Return the number of loop exit values that have been replaced, and the
 /// corresponding phi node will be added to DeadInsts.
 int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
                           ScalarEvolution *SE, const TargetTransformInfo *TTI,
                           SCEVExpander &Rewriter, DominatorTree *DT,
                           ReplaceExitVal ReplaceExitValue,
-                          SmallVector<WeakTrackingVH, 16> &DeadInsts);
+                          SmallVector<WeakTrackingVH, 16> &DeadInsts,
+                          unsigned SCEVNAryLimit = 32);
 
 /// Set weights for \p UnrolledLoop and \p RemainderLoop based on weights for
 /// \p OrigLoop and the following distribution of \p OrigLoop iteration among \p
 /// UnrolledLoop and \p RemainderLoop. \p UnrolledLoop receives weights that
 /// reflect TC/UF iterations, and \p RemainderLoop receives weights that reflect
 /// the remaining TC%UF iterations.
 ///
 /// Note that \p OrigLoop may be equal to either \p UnrolledLoop or \p

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

static cl::opt<ReplaceExitVal> ReplaceExitValue(
     cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"),
                clEnumValN(OnlyCheapRepl, "cheap",
                           "only replace exit value when the cost is cheap"),
                clEnumValN(NoHardUse, "noharduse",
                           "only replace exit values when loop def likely dead"),
                clEnumValN(AlwaysRepl, "always",
                           "always replace exit value whenever possible")));
 
+static cl::opt<unsigned> SCEVNAryLimit(
+    "scev-nary-limit", cl::Hidden, cl::init(32),
+    cl::desc("Limitation of the count of NAry-type operands to determine "
+              "whether to expand a NArySCEVExpr for replacing loop exit value"));
+
 static cl::opt<bool> UsePostIncrementRanges(
   "indvars-post-increment-ranges", cl::Hidden,
   cl::desc("Use post increment control-dependent ranges in IndVarSimplify"),
   cl::init(true));
 
 static cl::opt<bool>
 DisableLFTR("disable-lftr", cl::Hidden, cl::init(false),
             cl::desc("Disable Linear Function Test Replace optimization"));
#endif
   Rewriter.disableCanonicalMode();
   Changed |= simplifyAndExtend(L, Rewriter, LI);
 
   // Check to see if we can compute the final value of any expressions
   // that are recurrent in the loop, and substitute the exit values from the
   // loop into any instructions outside of the loop that use the final values
   // of the current expressions.
   if (ReplaceExitValue != NeverRepl) {
     if (int Rewrites = rewriteLoopExitValues(L, LI, TLI, SE, TTI, Rewriter, DT,
-                                             ReplaceExitValue, DeadInsts)) {
+                                             ReplaceExitValue, DeadInsts,
+                                             SCEVNAryLimit)) {
       NumReplaced += Rewrites;
       Changed = true;
     }
   }
 
   // Eliminate redundant IV cycles.
   NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);
 

llvm/lib/Transforms/Utils/LoopUtils.cpp

static bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
   return true;
 }
 
 int llvm::rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI,
                                 ScalarEvolution *SE,
                                 const TargetTransformInfo *TTI,
                                 SCEVExpander &Rewriter, DominatorTree *DT,
                                 ReplaceExitVal ReplaceExitValue,
-                                SmallVector<WeakTrackingVH, 16> &DeadInsts) {
+                                SmallVector<WeakTrackingVH, 16> &DeadInsts,
+                                unsigned SCEVNAryLimit) {
   // Check a pre-condition.
   assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
          "Indvars did not preserve LCSSA!");
 
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getUniqueExitBlocks(ExitBlocks);
 
   SmallVector<RewritePhi, 8> RewritePhiSet;
+
+  // If the SCEVNAryExpr has too many operands, then it would be
+  // extremely complicated after expanding, thus cause stack exhaust
+  // if we want to traverse this IR's operands.
+  // eg: We might get segment fault during ISel cause building
+  // SelectionDAG needs to visit all the operands.
+  auto IsSCEVNAryExtremelyComplicated = [&](const SCEV *ExitValue) {
+    auto *NAry = cast<SCEVNAryExpr>(ExitValue);
+    SmallVector<const SCEVNAryExpr*, 4> NAryVec;
+    NAryVec.push_back(NAry);
+    unsigned cnt = 0;
+    while (!NAryVec.empty()) {
+      NAry = NAryVec.pop_back_val();
+      for (auto *Op : NAry->operands()) {
+        if (isa<SCEVNAryExpr>(Op)) {
+          NAryVec.push_back(cast<SCEVNAryExpr>(Op));
+        } else {
+          ++cnt;
+          if (cnt > SCEVNAryLimit) {
+            return true;
+          }
+        }
+      }
+    }
+    return false;
+  };
   // Find all values that are computed inside the loop, but used outside of it.
   // Because of LCSSA, these values will only occur in LCSSA PHI Nodes.  Scan
   // the exit blocks of the loop to find them.
   for (BasicBlock *ExitBB : ExitBlocks) {
     // If there are no PHI nodes in this exit block, then no values defined
     // inside the loop are used on this path, skip it.
     PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
     if (!PN) continue;
while ((PN = dyn_cast<PHINode>(BBI++))) {
 
         // Okay, this instruction has a user outside of the current loop
         // and varies predictably *inside* the loop.  Evaluate the value it
         // contains when the loop exits, if possible.  We prefer to start with
         // expressions which are true for all exits (so as to maximize
         // expression reuse by the SCEVExpander), but resort to per-exit
         // evaluation if that fails.
         const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
+        if (isa<SCEVNAryExpr>(ExitValue) &&
+            IsSCEVNAryExtremelyComplicated(ExitValue)) {
+          continue;
+        }
         if (isa<SCEVCouldNotCompute>(ExitValue) ||
             !SE->isLoopInvariant(ExitValue, L) ||
             !isSafeToExpand(ExitValue, *SE)) {
           // TODO: This should probably be sunk into SCEV in some way; maybe a
           // getSCEVForExit(SCEV*, L, ExitingBB)?  It can be generalized for
           // most SCEV expressions and other recurrence types (e.g. shift
           // recurrences).  Is there existing code we can reuse?
           const SCEV *ExitCount = SE->getExitCount(L, PN->getIncomingBlock(i));
while ((PN = dyn_cast<PHINode>(BBI++))) {
         RewritePhiSet.emplace_back(PN, i, ExitValue, Inst, HighCost);
       }
     }
   }
 
   // Now that we've done preliminary filtering and billed all the SCEV's,
   // we can perform the last sanity check - the expansion must be valid.
   for (RewritePhi &Phi : RewritePhiSet) {
     Phi.Expansion = Rewriter.expandCodeFor(Phi.ExpansionSCEV, Phi.PN->getType(),
                                            Phi.ExpansionPoint);
 
     LLVM_DEBUG(dbgs() << "rewriteLoopExitValues: AfterLoopVal = "
                       << *(Phi.Expansion) << '\n'
                       << "  LoopVal = " << *(Phi.ExpansionPoint) << "\n");
 
     // FIXME: isValidRewrite() is a hack. it should be an assert, eventually.
     Phi.ValidRewrite = isValidRewrite(SE, Phi.ExpansionPoint, Phi.Expansion);
     if (!Phi.ValidRewrite) {
       DeadInsts.push_back(Phi.Expansion);
       continue;
     }
 
 #ifndef NDEBUG
     // If we reuse an instruction from a loop which is neither L nor one of
     // its containing loops, we end up breaking LCSSA form for this loop by
     // creating a new use of its instruction.
     if (auto *ExitInsn = dyn_cast<Instruction>(Phi.Expansion))
       if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
         if (EVL != L)
           assert(EVL->contains(L) && "LCSSA breach detected!");
 #endif
   }
 
   // TODO: after isValidRewrite() is an assertion, evaluate whether
   // it is beneficial to change how we calculate high-cost:
   // if we have SCEV 'A' which we know we will expand, should we calculate
   // the cost of other SCEV's after expanding SCEV 'A',
   // thus potentially giving cost bonus to those other SCEV's?
 
   bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
   int NumReplaced = 0;
 
   // Transformation.
   for (const RewritePhi &Phi : RewritePhiSet) {
     if (!Phi.ValidRewrite)
       continue;
 
     PHINode *PN = Phi.PN;
     Value *ExitVal = Phi.Expansion;

llvm/test/Transforms/IndVarSimplify/avoid-rewriting-loop-exit-value.ll

+;RUN: opt -indvars -S < %s | FileCheck %s
+
+%struct.ad = type { i8 }
+%struct.ae = type { %struct.ad }
+@aj = dso_local global [5 x [0 x [5 x %struct.ad]]] zeroinitializer, align 1
+@al = dso_local global %struct.ae zeroinitializer, align 1
+
+define dso_local i32 @_Z2aqv() local_unnamed_addr {
+; CHECK-LABEL: @_Z2aqv(
+; CHECK:       _ZL2apiPiiS_.exit:
+; CHECK-NEXT:    [[ADD_I_2_I_LCSSA:%.*]] = phi i32 [ [[ADD_I_2_I:%.*]], [[FOR_COND4_PREHEADER_I:%.*]] ]
+; CHECK-NEXT:    [[CONV8_I:%.*]] = sext i32 [[ADD_I_2_I_LCSSA:%.*]] to i64
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %for.cond4.preheader.i
+
+for.cond4.preheader.i:                            ; preds = %for.cond4.preheader.i, %entry
+  %av.addr.04.i = phi i32 [ 0, %entry ], [ %sub.i.2.i, %for.cond4.preheader.i ]
+  %aw.sroa.0.03.i = phi i32 [ 0, %entry ], [ %dec.i, %for.cond4.preheader.i ]
+  %add.i.i = add nsw i32 %av.addr.04.i, zext (i1 icmp eq (%struct.ad* bitcast (i8* getelementptr inbounds ([5 x [0 x [5 x %struct.ad]]], [5 x [0 x [5 x %struct.ad]]]* @aj, i64 0, i64 0, i64 9, i64 1, i32 0) to %struct.ad*), %struct.ad* getelementptr inbounds (%struct.ae, %struct.ae* @al, i64 0, i32 0)) to i32)
+  %cmp.i.i = icmp sgt i32 %av.addr.04.i, 7
+  %add.i.i.op = shl i32 %add.i.i, 16
+  %add.i.i.op.op = ashr i32 %add.i.i.op, 31
+  %add.i.i.op.op.op = xor i32 %add.i.i.op.op, -1
+  %sext.i.lobit.not = select i1 %cmp.i.i, i32 -1, i32 %add.i.i.op.op.op
+  %sub.i.i = add i32 %sext.i.lobit.not, %av.addr.04.i
+  %add.i.1.i = add nsw i32 %sub.i.i, zext (i1 icmp eq (%struct.ad* bitcast (i8* getelementptr inbounds ([5 x [0 x [5 x %struct.ad]]], [5 x [0 x [5 x %struct.ad]]]* @aj, i64 0, i64 0, i64 9, i64 1, i32 0) to %struct.ad*), %struct.ad* getelementptr inbounds (%struct.ae, %struct.ae* @al, i64 0, i32 0)) to i32)
+  %cmp.i.1.i = icmp sgt i32 %sub.i.i, 7
+  %add.i.1.i.op = shl i32 %add.i.1.i, 16
+  %add.i.1.i.op.op = ashr i32 %add.i.1.i.op, 31
+  %add.i.1.i.op.op.op = xor i32 %add.i.1.i.op.op, -1
+  %sext.1.i.lobit.not = select i1 %cmp.i.1.i, i32 -1, i32 %add.i.1.i.op.op.op
+  %sub.i.1.i = add i32 %sext.1.i.lobit.not, %sub.i.i
+  %add.i.2.i = add nsw i32 %sub.i.1.i, zext (i1 icmp eq (%struct.ad* bitcast (i8* getelementptr inbounds ([5 x [0 x [5 x %struct.ad]]], [5 x [0 x [5 x %struct.ad]]]* @aj, i64 0, i64 0, i64 9, i64 1, i32 0) to %struct.ad*), %struct.ad* getelementptr inbounds (%struct.ae, %struct.ae* @al, i64 0, i32 0)) to i32)
+  %cmp.i.2.i = icmp sgt i32 %sub.i.1.i, 7
+  %add.i.2.i.op = shl i32 %add.i.2.i, 16
+  %add.i.2.i.op.op = ashr i32 %add.i.2.i.op, 31
+  %add.i.2.i.op.op.op = xor i32 %add.i.2.i.op.op, -1
+  %sext.2.i.lobit.not = select i1 %cmp.i.2.i, i32 -1, i32 %add.i.2.i.op.op.op
+  %sub.i.2.i = add i32 %sext.2.i.lobit.not, %sub.i.1.i
+  %dec.i = add nsw i32 %aw.sroa.0.03.i, -1
+  %cmp.i = icmp sgt i32 %aw.sroa.0.03.i, -10
+  br i1 %cmp.i, label %for.cond4.preheader.i, label %_ZL2apiPiiS_.exit
+
+_ZL2apiPiiS_.exit:                                ; preds = %for.cond4.preheader.i
+  %add.i.2.i.lcssa = phi i32 [ %add.i.2.i, %for.cond4.preheader.i ]
+  %conv8.i = sext i32 %add.i.2.i.lcssa to i64
+  ret i32 0
+}
+