[ScalarEvolution] Apply Depth limit to getMulExpr

[mkazantsev]

Summary

This is a fix for PR33292 that shows a case of extremely long compilation
of a single .c file with clang, with most time spent within SCEV.

We have a mechanism of limiting recursion depth for getAddExpr to avoid
long analysis in SCEV. However, there are calls from getAddExpr to getMulExpr
and back that do not propagate the info about depth. As result of this, a chain

getAddExpr -> ... .> getAddExpr -> getMulExpr -> getAddExpr -> ... -> getAddExpr

can be extremely long, with every segment of getAddExpr's being up to max depth long.
This leads either to long compilation or crash by stack overflow. We face this situation while
analyzing big SCEVs in the test of PR33292.

This patch applies the same limit on max expression depth for getAddExpr and getMulExpr.

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

2697

Why not do the same thing here as you did in getAddExpr:

// Limit recursion calls depth
if (Depth > MaxArithDepth)
  return getOrCreateMulExpr(Ops, Flags);

[mkazantsev]

Ping

[sanjoy]

lgtm

lib/Analysis/ScalarEvolution.cpp

2630

Indent looks off?

2838–2839

Something worth considering (no need to change in this patch) -- should we be incrementing Depth on tail calls like these where there is no real recursion?

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

2838–2839

Not sure, may be reasonable to not do it since we always remove the number of ops here and cannot go to infinite recursion.

include/llvm/Analysis/ScalarEvolution.h

const SCEV *getSignExtendExprCached(const SCEV *Op, Type *Ty,
                                       ExtendCacheTy &Cache);
   const SCEV *getSignExtendExprImpl(const SCEV *Op, Type *Ty,
                                     ExtendCacheTy &Cache);
   const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
   const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
                          unsigned Depth = 0);
   const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
-                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
+                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
+                         unsigned Depth = 0) {
     SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
-    return getAddExpr(Ops, Flags);
+    return getAddExpr(Ops, Flags, Depth);
   }
   const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
-                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
+                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
+                         unsigned Depth = 0) {
     SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
-    return getAddExpr(Ops, Flags);
+    return getAddExpr(Ops, Flags, Depth);
   }
   const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
-                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
+                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
+                         unsigned Depth = 0);
   const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS,
-                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
+                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
+                         unsigned Depth = 0) {
     SmallVector<const SCEV *, 2> Ops = {LHS, RHS};
-    return getMulExpr(Ops, Flags);
+    return getMulExpr(Ops, Flags, Depth);
   }
   const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2,
-                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
+                         SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
+                         unsigned Depth = 0) {
     SmallVector<const SCEV *, 3> Ops = {Op0, Op1, Op2};
-    return getMulExpr(Ops, Flags);
+    return getMulExpr(Ops, Flags, Depth);
   }
   const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS);
   const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L,
                             SCEV::NoWrapFlags Flags);
   const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands,
                             const Loop *L, SCEV::NoWrapFlags Flags);
   const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands,
const SCEV *getNegativeSCEV(const SCEV *V,
                               SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
 
   /// Return the SCEV object corresponding to ~V.
   ///
   const SCEV *getNotSCEV(const SCEV *V);
 
   /// Return LHS-RHS.  Minus is represented in SCEV as A+B*-1.
   const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
-                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap);
+                           SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
+                           unsigned Depth = 0);
 
   /// Return a SCEV corresponding to a conversion of the input value to the
   /// specified type.  If the type must be extended, it is zero extended.
   const SCEV *getTruncateOrZeroExtend(const SCEV *V, Type *Ty);
 
   /// Return a SCEV corresponding to a conversion of the input value to the
   /// specified type.  If the type must be extended, it is sign extended.
   const SCEV *getTruncateOrSignExtend(const SCEV *V, Type *Ty);

lib/Analysis/ScalarEvolution.cpp

static cl::opt<unsigned> MaxSCEVOperationsImplicationDepth(
     cl::init(2));
 
 static cl::opt<unsigned> MaxValueCompareDepth(
     "scalar-evolution-max-value-compare-depth", cl::Hidden,
     cl::desc("Maximum depth of recursive value complexity comparisons"),
     cl::init(2));
 
 static cl::opt<unsigned>
-    MaxAddExprDepth("scalar-evolution-max-addexpr-depth", cl::Hidden,
-                    cl::desc("Maximum depth of recursive AddExpr"),
-                    cl::init(32));
+    MaxArithDepth("scalar-evolution-max-arith-depth", cl::Hidden,
+                  cl::desc("Maximum depth of recursive arithmetics"),
 
 static cl::opt<unsigned> MaxConstantEvolvingDepth(
     "scalar-evolution-max-constant-evolving-depth", cl::Hidden,
     cl::desc("Maximum depth of recursive constant evolving"), cl::init(32));
 
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//
if (LHSC->getValue()->isZero()) {
       Ops.erase(Ops.begin());
       --Idx;
     }
 
     if (Ops.size() == 1) return Ops[0];
   }
 
   // Limit recursion calls depth
-  if (Depth > MaxAddExprDepth)
+  if (Depth > MaxArithDepth)
     return getOrCreateAddExpr(Ops, Flags);
 
   // Okay, check to see if the same value occurs in the operand list more than
   // once.  If so, merge them together into an multiply expression.  Since we
   // sorted the list, these values are required to be adjacent.
   Type *Ty = Ops[0]->getType();
   bool FoundMatch = false;
   for (unsigned i = 0, e = Ops.size(); i != e-1; ++i)
     if (Ops[i] == Ops[i+1]) {      //  X + Y + Y  -->  X + Y*2
       // Scan ahead to count how many equal operands there are.
       unsigned Count = 2;
       while (i+Count != e && Ops[i+Count] == Ops[i])
         ++Count;
       // Merge the values into a multiply.
       const SCEV *Scale = getConstant(Ty, Count);
-      const SCEV *Mul = getMulExpr(Scale, Ops[i]);
+      const SCEV *Mul = getMulExpr(Scale, Ops[i], SCEV::FlagAnyWrap, Depth + 1);
       if (Ops.size() == Count)
         return Mul;
       Ops[i] = Mul;
       Ops.erase(Ops.begin()+i+1, Ops.begin()+i+Count);
       --i; e -= Count - 1;
       FoundMatch = true;
     }
   if (FoundMatch)
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
           } else if (const auto *C = dyn_cast<SCEVConstant>(M->getOperand(j))) {
             LargeMulOps.push_back(getAnyExtendExpr(C, SrcType));
           } else {
             Ok = false;
             break;
           }
         }
         if (Ok)
-          LargeOps.push_back(getMulExpr(LargeMulOps));
+          LargeOps.push_back(getMulExpr(LargeMulOps, SCEV::FlagAnyWrap, Depth + 1));
       } else {
         Ok = false;
         break;
       }
     }
     if (Ok) {
       // Evaluate the expression in the larger type.
       const SCEV *Fold = getAddExpr(LargeOps, Flags, Depth + 1);
if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant,
       // Re-generate the operands list.
       Ops.clear();
       if (AccumulatedConstant != 0)
         Ops.push_back(getConstant(AccumulatedConstant));
       for (auto &MulOp : MulOpLists)
         if (MulOp.first != 0)
           Ops.push_back(getMulExpr(
               getConstant(MulOp.first),
-              getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1)));
+              getAddExpr(MulOp.second, SCEV::FlagAnyWrap, Depth + 1),
+              SCEV::FlagAnyWrap, Depth + 1));
       if (Ops.empty())
         return getZero(Ty);
       if (Ops.size() == 1)
         return Ops[0];
       return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
     }
   }
 
for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
           // Fold W + X + (X * Y * Z)  -->  W + (X * ((Y*Z)+1))
           const SCEV *InnerMul = Mul->getOperand(MulOp == 0);
           if (Mul->getNumOperands() != 2) {
             // If the multiply has more than two operands, we must get the
             // Y*Z term.
             SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(),
                                                 Mul->op_begin()+MulOp);
             MulOps.append(Mul->op_begin()+MulOp+1, Mul->op_end());
-            InnerMul = getMulExpr(MulOps);
+            InnerMul = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
           }
           SmallVector<const SCEV *, 2> TwoOps = {getOne(Ty), InnerMul};
           const SCEV *AddOne = getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
-          const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV);
+          const SCEV *OuterMul = getMulExpr(AddOne, MulOpSCEV,
+                                            SCEV::FlagAnyWrap, Depth + 1);
           if (Ops.size() == 2) return OuterMul;
           if (AddOp < Idx) {
             Ops.erase(Ops.begin()+AddOp);
             Ops.erase(Ops.begin()+Idx-1);
           } else {
             Ops.erase(Ops.begin()+Idx);
             Ops.erase(Ops.begin()+AddOp-1);
           }
for (unsigned MulOp = 0, e = Mul->getNumOperands(); MulOp != e; ++MulOp) {
              OMulOp != e; ++OMulOp)
           if (OtherMul->getOperand(OMulOp) == MulOpSCEV) {
             // Fold X + (A*B*C) + (A*D*E) --> X + (A*(B*C+D*E))
             const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0);
             if (Mul->getNumOperands() != 2) {
               SmallVector<const SCEV *, 4> MulOps(Mul->op_begin(),
                                                   Mul->op_begin()+MulOp);
               MulOps.append(Mul->op_begin()+MulOp+1, Mul->op_end());
-              InnerMul1 = getMulExpr(MulOps);
+              InnerMul1 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
             }
             const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0);
             if (OtherMul->getNumOperands() != 2) {
               SmallVector<const SCEV *, 4> MulOps(OtherMul->op_begin(),
                                                   OtherMul->op_begin()+OMulOp);
               MulOps.append(OtherMul->op_begin()+OMulOp+1, OtherMul->op_end());
-              InnerMul2 = getMulExpr(MulOps);
+              InnerMul2 = getMulExpr(MulOps, SCEV::FlagAnyWrap, Depth + 1);
             }
             SmallVector<const SCEV *, 2> TwoOps = {InnerMul1, InnerMul2};
             const SCEV *InnerMulSum =
                 getAddExpr(TwoOps, SCEV::FlagAnyWrap, Depth + 1);
-            const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum);
+            const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum,
+                                              SCEV::FlagAnyWrap, Depth + 1);
             if (Ops.size() == 2) return OuterMul;
             Ops.erase(Ops.begin()+Idx);
             Ops.erase(Ops.begin()+OtherMulIdx-1);
             Ops.push_back(OuterMul);
             return getAddExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
           }
       }
     }
ScalarEvolution::getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops,
   }
   S->setNoWrapFlags(Flags);
   return S;
 }
 
 static uint64_t umul_ov(uint64_t i, uint64_t j, bool &Overflow) {
   uint64_t k = i*j;
   if (j > 1 && k / j != i) Overflow = true;
   return k;
 }
 
 /// Compute the result of "n choose k", the binomial coefficient.  If an
 /// intermediate computation overflows, Overflow will be set and the return will
 /// be garbage. Overflow is not cleared on absence of overflow.
 static uint64_t Choose(uint64_t n, uint64_t k, bool &Overflow) {
   // We use the multiplicative formula:
   //     n(n-1)(n-2)...(n-(k-1)) / k(k-1)(k-2)...1 .
if (isa<SCEVAddExpr>(*CurrentExpr) || isa<SCEVMulExpr>(*CurrentExpr)) {
       Ops.append(CurrentNAry->op_begin(), CurrentNAry->op_end());
     }
   }
   return false;
 }
 
 /// Get a canonical multiply expression, or something simpler if possible.
 const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops,
-                                        SCEV::NoWrapFlags Flags) {
+                                        SCEV::NoWrapFlags Flags,
+                                        unsigned Depth) {
   assert(Flags == maskFlags(Flags, SCEV::FlagNUW | SCEV::FlagNSW) &&
          "only nuw or nsw allowed");
   assert(!Ops.empty() && "Cannot get empty mul!");
   if (Ops.size() == 1) return Ops[0];
 #ifndef NDEBUG
   Type *ETy = getEffectiveSCEVType(Ops[0]->getType());
   for (unsigned i = 1, e = Ops.size(); i != e; ++i)
     assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy &&
            "SCEVMulExpr operand types don't match!");
 #endif
 
   // Sort by complexity, this groups all similar expression types together.
   GroupByComplexity(Ops, &LI, DT);
 
   Flags = StrengthenNoWrapFlags(this, scMulExpr, Ops, Flags);
 
+  if (Depth <= MaxArithDepth) {
     // If there are any constants, fold them together.
     unsigned Idx = 0;
     if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
 
       // C1*(C2+V) -> C1*C2 + C1*V
       if (Ops.size() == 2)
           if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1]))
             // If any of Add's ops are Adds or Muls with a constant,
             // apply this transformation as well.
             if (Add->getNumOperands() == 2)
               if (containsConstantSomewhere(Add))
-              return getAddExpr(getMulExpr(LHSC, Add->getOperand(0)),
-                                getMulExpr(LHSC, Add->getOperand(1)));
+                return getAddExpr(getMulExpr(LHSC, Add->getOperand(0),
+                                             SCEV::FlagAnyWrap, Depth + 1),
+                                  getMulExpr(LHSC, Add->getOperand(1),
+                                             SCEV::FlagAnyWrap, Depth + 1),
+                                  SCEV::FlagAnyWrap, Depth + 1);
 
       ++Idx;
       while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
         // We found two constants, fold them together!
         ConstantInt *Fold =
             ConstantInt::get(getContext(), LHSC->getAPInt() * RHSC->getAPInt());
         Ops[0] = getConstant(Fold);
         Ops.erase(Ops.begin()+1);  // Erase the folded element
         if (Ops.size() == 1) return Ops[0];
         LHSC = cast<SCEVConstant>(Ops[0]);
       }
 
       // If we are left with a constant one being multiplied, strip it off.
       if (cast<SCEVConstant>(Ops[0])->getValue()->equalsInt(1)) {
         Ops.erase(Ops.begin());
         --Idx;
       } else if (cast<SCEVConstant>(Ops[0])->getValue()->isZero()) {
         // If we have a multiply of zero, it will always be zero.
         return Ops[0];
       } else if (Ops[0]->isAllOnesValue()) {
         // If we have a mul by -1 of an add, try distributing the -1 among the
         // add operands.
         if (Ops.size() == 2) {
           if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Ops[1])) {
             SmallVector<const SCEV *, 4> NewOps;
             bool AnyFolded = false;
             for (const SCEV *AddOp : Add->operands()) {
-            const SCEV *Mul = getMulExpr(Ops[0], AddOp);
+              const SCEV *Mul = getMulExpr(Ops[0], AddOp, SCEV::FlagAnyWrap,
+                                           Depth + 1);
               if (!isa<SCEVMulExpr>(Mul)) AnyFolded = true;
               NewOps.push_back(Mul);
             }
             if (AnyFolded)
-            return getAddExpr(NewOps);
+              return getAddExpr(NewOps, SCEV::FlagAnyWrap, Depth + 1);
           } else if (const auto *AddRec = dyn_cast<SCEVAddRecExpr>(Ops[1])) {
             // Negation preserves a recurrence's no self-wrap property.
             SmallVector<const SCEV *, 4> Operands;
             for (const SCEV *AddRecOp : AddRec->operands())
-            Operands.push_back(getMulExpr(Ops[0], AddRecOp));
+              Operands.push_back(getMulExpr(Ops[0], AddRecOp, SCEV::FlagAnyWrap,
+                                            Depth + 1));
 
             return getAddRecExpr(Operands, AddRec->getLoop(),
                                  AddRec->getNoWrapFlags(SCEV::FlagNW));
           }
         }
       }
 
       if (Ops.size() == 1)
         return Ops[0];
     }
 
     // Skip over the add expression until we get to a multiply.
     while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr)
       ++Idx;
 
     // If there are mul operands inline them all into this expression.
     if (Idx < Ops.size()) {
       bool DeletedMul = false;
       while (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(Ops[Idx])) {
         if (Ops.size() > MulOpsInlineThreshold)
           break;
-      // If we have an mul, expand the mul operands onto the end of the operands
-      // list.
+        // If we have an mul, expand the mul operands onto the end of the
+        // operands list.
         Ops.erase(Ops.begin()+Idx);
         Ops.append(Mul->op_begin(), Mul->op_end());
         DeletedMul = true;
       }
 
-    // If we deleted at least one mul, we added operands to the end of the list,
-    // and they are not necessarily sorted.  Recurse to resort and resimplify
-    // any operands we just acquired.
+      // If we deleted at least one mul, we added operands to the end of the
+      // list, and they are not necessarily sorted.  Recurse to resort and
+      // resimplify any operands we just acquired.
       if (DeletedMul)
-      return getMulExpr(Ops);
+        return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
     }
 
     // If there are any add recurrences in the operands list, see if any other
     // added values are loop invariant.  If so, we can fold them into the
     // recurrence.
     while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scAddRecExpr)
       ++Idx;
 
     // Scan over all recurrences, trying to fold loop invariants into them.
     for (; Idx < Ops.size() && isa<SCEVAddRecExpr>(Ops[Idx]); ++Idx) {
-    // Scan all of the other operands to this mul and add them to the vector if
-    // they are loop invariant w.r.t. the recurrence.
+      // Scan all of the other operands to this mul and add them to the vector
+      // if they are loop invariant w.r.t. the recurrence.
       SmallVector<const SCEV *, 8> LIOps;
       const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(Ops[Idx]);
       const Loop *AddRecLoop = AddRec->getLoop();
       for (unsigned i = 0, e = Ops.size(); i != e; ++i)
         if (isAvailableAtLoopEntry(Ops[i], AddRecLoop)) {
           LIOps.push_back(Ops[i]);
           Ops.erase(Ops.begin()+i);
           --i; --e;
         }
 
       // If we found some loop invariants, fold them into the recurrence.
       if (!LIOps.empty()) {
         //  NLI * LI * {Start,+,Step}  -->  NLI * {LI*Start,+,LI*Step}
         SmallVector<const SCEV *, 4> NewOps;
         NewOps.reserve(AddRec->getNumOperands());
-      const SCEV *Scale = getMulExpr(LIOps);
+        const SCEV *Scale = getMulExpr(LIOps, SCEV::FlagAnyWrap, Depth + 1);
         for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i)
-        NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i)));
+          NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i),
+                                      SCEV::FlagAnyWrap, Depth + 1));
 
         // Build the new addrec. Propagate the NUW and NSW flags if both the
         // outer mul and the inner addrec are guaranteed to have no overflow.
         //
         // No self-wrap cannot be guaranteed after changing the step size, but
         // will be inferred if either NUW or NSW is true.
         Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW));
         const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags);
 
         // If all of the other operands were loop invariant, we are done.
         if (Ops.size() == 1) return NewRec;
 
         // Otherwise, multiply the folded AddRec by the non-invariant parts.
         for (unsigned i = 0;; ++i)
           if (Ops[i] == AddRec) {
             Ops[i] = NewRec;
             break;
           }
-      return getMulExpr(Ops);
+        return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
       }
 
-    // Okay, if there weren't any loop invariants to be folded, check to see if
-    // there are multiple AddRec's with the same loop induction variable being
-    // multiplied together.  If so, we can fold them.
+      // Okay, if there weren't any loop invariants to be folded, check to see
+      // if there are multiple AddRec's with the same loop induction variable
+      // being multiplied together.  If so, we can fold them.
 
       // {A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L>
       // = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [
       //       choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z
       //   ]]],+,...up to x=2n}.
       // Note that the arguments to choose() are always integers with values
       // known at compile time, never SCEV objects.
       //
       // The implementation avoids pointless extra computations when the two
       // addrec's are of different length (mathematically, it's equivalent to
       // an infinite stream of zeros on the right).
       bool OpsModified = false;
       for (unsigned OtherIdx = Idx+1;
            OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);
            ++OtherIdx) {
         const SCEVAddRecExpr *OtherAddRec =
           dyn_cast<SCEVAddRecExpr>(Ops[OtherIdx]);
         if (!OtherAddRec || OtherAddRec->getLoop() != AddRecLoop)
           continue;
 
         bool Overflow = false;
         Type *Ty = AddRec->getType();
         bool LargerThan64Bits = getTypeSizeInBits(Ty) > 64;
         SmallVector<const SCEV*, 7> AddRecOps;
         for (int x = 0, xe = AddRec->getNumOperands() +
                OtherAddRec->getNumOperands() - 1; x != xe && !Overflow; ++x) {
           const SCEV *Term = getZero(Ty);
           for (int y = x, ye = 2*x+1; y != ye && !Overflow; ++y) {
             uint64_t Coeff1 = Choose(x, 2*x - y, Overflow);
             for (int z = std::max(y-x, y-(int)AddRec->getNumOperands()+1),
                    ze = std::min(x+1, (int)OtherAddRec->getNumOperands());
                  z < ze && !Overflow; ++z) {
               uint64_t Coeff2 = Choose(2*x - y, x-z, Overflow);
               uint64_t Coeff;
               if (LargerThan64Bits)
                 Coeff = umul_ov(Coeff1, Coeff2, Overflow);
               else
                 Coeff = Coeff1*Coeff2;
               const SCEV *CoeffTerm = getConstant(Ty, Coeff);
               const SCEV *Term1 = AddRec->getOperand(y-z);
               const SCEV *Term2 = OtherAddRec->getOperand(z);
-            Term = getAddExpr(Term, getMulExpr(CoeffTerm, Term1,Term2));
+              Term = getAddExpr(Term, getMulExpr(CoeffTerm, Term1, Term2,
+                                                 SCEV::FlagAnyWrap, Depth + 1),
+                                SCEV::FlagAnyWrap, Depth + 1);
             }
           }
           AddRecOps.push_back(Term);
         }
         if (!Overflow) {
           const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(),
                                                 SCEV::FlagAnyWrap);
           if (Ops.size() == 2) return NewAddRec;
           Ops[Idx] = NewAddRec;
           Ops.erase(Ops.begin() + OtherIdx); --OtherIdx;
           OpsModified = true;
           AddRec = dyn_cast<SCEVAddRecExpr>(NewAddRec);
           if (!AddRec)
             break;
         }
       }
       if (OpsModified)
-      return getMulExpr(Ops);
+        return getMulExpr(Ops, SCEV::FlagAnyWrap, Depth + 1);
 
       // Otherwise couldn't fold anything into this recurrence.  Move onto the
       // next one.
     }
+  }
 
   // Okay, it looks like we really DO need an mul expr.  Check to see if we
   // already have one, otherwise create a new one.
   FoldingSetNodeID ID;
   ID.AddInteger(scMulExpr);
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
   void *IP = nullptr;
const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) {
   Type *Ty = V->getType();
   Ty = getEffectiveSCEVType(Ty);
   const SCEV *AllOnes =
                    getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty)));
   return getMinusSCEV(AllOnes, V);
 }
 
 const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
-                                          SCEV::NoWrapFlags Flags) {
+                                          SCEV::NoWrapFlags Flags,
+                                          unsigned Depth) {
   // Fast path: X - X --> 0.
   if (LHS == RHS)
     return getZero(LHS->getType());
 
   // We represent LHS - RHS as LHS + (-1)*RHS. This transformation
   // makes it so that we cannot make much use of NUW.
   auto AddFlags = SCEV::FlagAnyWrap;
   const bool RHSIsNotMinSigned =
const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS,
   // RHS is NSW and LHS >= 0.
   //
   // The difficulty here is that the NSW flag may have been proven
   // relative to a loop that is to be found in a recurrence in LHS and
   // not in RHS. Applying NSW to (-1)*M may then let the NSW have a
   // larger scope than intended.
   auto NegFlags = RHSIsNotMinSigned ? SCEV::FlagNSW : SCEV::FlagAnyWrap;
 
-  return getAddExpr(LHS, getNegativeSCEV(RHS, NegFlags), AddFlags);
+  return getAddExpr(LHS, getNegativeSCEV(RHS, NegFlags), AddFlags, Depth);
 }
 
 const SCEV *
 ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty) {
   Type *SrcTy = V->getType();
   assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) &&
          (Ty->isIntegerTy() || Ty->isPointerTy()) &&
          "Cannot truncate or zero extend with non-integer arguments!");

lib/Transforms/Utils/SimplifyIndVar.cpp

 }
 
 bool SimplifyIndvar::eliminateOverflowIntrinsic(CallInst *CI) {
   auto *F = CI->getCalledFunction();
   if (!F)
     return false;
 
   typedef const SCEV *(ScalarEvolution::*OperationFunctionTy)(
-      const SCEV *, const SCEV *, SCEV::NoWrapFlags);
+      const SCEV *, const SCEV *, SCEV::NoWrapFlags, unsigned);
   typedef const SCEV *(ScalarEvolution::*ExtensionFunctionTy)(
       const SCEV *, Type *);
 
   OperationFunctionTy Operation;
   ExtensionFunctionTy Extension;
 
   Instruction::BinaryOps RawOp;
 
bool SimplifyIndvar::eliminateOverflowIntrinsic(CallInst *CI) {
   const SCEV *LHS = SE->getSCEV(CI->getArgOperand(0));
   const SCEV *RHS = SE->getSCEV(CI->getArgOperand(1));
 
   auto *NarrowTy = cast<IntegerType>(LHS->getType());
   auto *WideTy =
     IntegerType::get(NarrowTy->getContext(), NarrowTy->getBitWidth() * 2);
 
   const SCEV *A =
-      (SE->*Extension)((SE->*Operation)(LHS, RHS, SCEV::FlagAnyWrap), WideTy);
+      (SE->*Extension)((SE->*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0u),
+                       WideTy);
   const SCEV *B =
       (SE->*Operation)((SE->*Extension)(LHS, WideTy),
-                       (SE->*Extension)(RHS, WideTy), SCEV::FlagAnyWrap);
+                       (SE->*Extension)(RHS, WideTy), SCEV::FlagAnyWrap, 0u);
 
   if (A != B)
     return false;
 
   // Proved no overflow, nuke the overflow check and, if possible, the overflow
   // intrinsic as well.
 
   BinaryOperator *NewResult = BinaryOperator::Create(

 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
                                                     Value *IVOperand) {
 
   // Fastpath: we don't have any work to do if `BO` is `nuw` and `nsw`.
   if (BO->hasNoUnsignedWrap() && BO->hasNoSignedWrap())
     return false;
 
   const SCEV *(ScalarEvolution::*GetExprForBO)(const SCEV *, const SCEV *,
-                                               SCEV::NoWrapFlags);
-
+                                               SCEV::NoWrapFlags, unsigned);
   switch (BO->getOpcode()) {
   default:
     return false;
 
   case Instruction::Add:
     GetExprForBO = &ScalarEvolution::getAddExpr;
     break;
 
bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator *BO,
   const SCEV *RHS = SE->getSCEV(BO->getOperand(1));
 
   bool Changed = false;
 
   if (!BO->hasNoUnsignedWrap()) {
     const SCEV *ExtendAfterOp = SE->getZeroExtendExpr(SE->getSCEV(BO), WideTy);
     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
       SE->getZeroExtendExpr(LHS, WideTy), SE->getZeroExtendExpr(RHS, WideTy),
-      SCEV::FlagAnyWrap);
+      SCEV::FlagAnyWrap, 0u);
     if (ExtendAfterOp == OpAfterExtend) {
       BO->setHasNoUnsignedWrap();
       SE->forgetValue(BO);
       Changed = true;
     }
   }
 
   if (!BO->hasNoSignedWrap()) {
     const SCEV *ExtendAfterOp = SE->getSignExtendExpr(SE->getSCEV(BO), WideTy);
     const SCEV *OpAfterExtend = (SE->*GetExprForBO)(
       SE->getSignExtendExpr(LHS, WideTy), SE->getSignExtendExpr(RHS, WideTy),
-      SCEV::FlagAnyWrap);
+      SCEV::FlagAnyWrap, 0u);
     if (ExtendAfterOp == OpAfterExtend) {
       BO->setHasNoSignedWrap();
       SE->forgetValue(BO);
       Changed = true;
     }
   }
 
   return Changed;

test/Analysis/ScalarEvolution/limit-depth.ll

+; RUN: opt -scalar-evolution-max-arith-depth=0 -analyze -scalar-evolution < %s | FileCheck %s
+
+; Check that depth set to 0 prevents getAddExpr and getMulExpr from making
+; transformations in SCEV. We expect the result to be very straightforward.
+
+define void @test_add(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f) {
+; CHECK-LABEL: @test_add
+; CHECK:       %s2 = add i32 %s1, %p3
+; CHECK-NEXT:   -->  (%a + %a + %b + %b + %c + %c + %d + %d + %e + %e + %f + %f)
+  %tmp0 = add i32 %a, %b
+  %tmp1 = add i32 %b, %c
+  %tmp2 = add i32 %c, %d
+  %tmp3 = add i32 %d, %e
+  %tmp4 = add i32 %e, %f
+  %tmp5 = add i32 %f, %a
+
+  %p1 = add i32 %tmp0, %tmp3
+  %p2 = add i32 %tmp1, %tmp4
+  %p3 = add i32 %tmp2, %tmp5
+
+  %s1 = add i32 %p1, %p2
+  %s2 = add i32 %s1, %p3
+  ret void
+}
+
+define void @test_mul(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f) {
+; CHECK-LABEL: @test_mul
+; CHECK:       %s2 = mul i32 %s1, %p3
+; CHECK-NEXT:  -->  (2 * 3 * 4 * 5 * 6 * 7 * %a * %b * %c * %d * %e * %f)
+  %tmp0 = mul i32 %a, 2
+  %tmp1 = mul i32 %b, 3
+  %tmp2 = mul i32 %c, 4
+  %tmp3 = mul i32 %d, 5
+  %tmp4 = mul i32 %e, 6
+  %tmp5 = mul i32 %f, 7
+
+  %p1 = mul i32 %tmp0, %tmp3
+  %p2 = mul i32 %tmp1, %tmp4
+  %p3 = mul i32 %tmp2, %tmp5
+
+  %s1 = mul i32 %p1, %p2
+  %s2 = mul i32 %s1, %p3
+  ret void
+}