llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-analysis Author: Fangcao Wang (LittleMeepo) <details> <summary>Changes</summary> Fix issue #<!-- -->206633 by bounding the mutual recursion between affine-addrec range computation and backedge-taken-count computation in `ScalarEvolution::getRangeRef` (via a new `AddRecRangeDepth` counter and the `-scalar-evolution-max-add-rec-range-depth` limit, default 32), which previously overflowed the stack on heavily unrolled loops at `-O3`. --- Full diff: https://github.com/llvm/llvm-project/pull/206724.diff 4 Files Affected: - (added) clang/test/CodeGen/scev-addrec-range-recursion.cpp (+24) - (modified) llvm/include/llvm/Analysis/ScalarEvolution.h (+6) - (modified) llvm/lib/Analysis/ScalarEvolution.cpp (+57-36) - (added) llvm/test/Analysis/ScalarEvolution/addrec-range-recursion-depth.ll (+36) ``````````diff diff --git a/clang/test/CodeGen/scev-addrec-range-recursion.cpp b/clang/test/CodeGen/scev-addrec-range-recursion.cpp new file mode 100644 index 0000000000000..3b51dc70df650 --- /dev/null +++ b/clang/test/CodeGen/scev-addrec-range-recursion.cpp @@ -0,0 +1,24 @@ +// RUN: %clang_cc1 -triple x86_64-unknown-linux-gnu -O3 -emit-obj -o /dev/null %s +// REQUIRES: x86-registered-target + +// Regression test for a stack overflow in ScalarEvolution. Computing the range +// of an affine addrec needs the loop's backedge-taken count, whose computation +// can recurse back into range computation through loop-guard reasoning (the +// llvm.assume calls below). For this heavily-unrolled nested loop the mutual +// recursion chained across a large number of versioned loops and exhausted the +// stack inside the "Induction Variable Users" analysis. ScalarEvolution now +// bounds the depth of this recursion, so compilation must complete. + +short d[3][3][3]; + +void a(int l, short b, char c, short e, short f, short g) { +#pragma clang loop unroll(enable) + for (int h; h < 23LL; h += 1LL) + for (short i = 0; i < 4 + 22; i += -3224943361791975759LL - 40623) { + __builtin_assume(e - 17695 == 23); + __builtin_assume((f ? c >= l : b) - 20846 == 4); + for (short j = 0; j < e - 17695; j += b - 20846) + for (short k = ((int)g < 0 ? (int)g : 0) + 9; k < 0; k += 3) + d[k][h][h] = 0; + } +} diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index 1e09dbc3db5f1..0ac16fe5b1ca1 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1718,6 +1718,12 @@ class ScalarEvolution { /// conditions dominating the backedge of a loop. bool WalkingBEDominatingConds = false; + /// Depth of the current chain of addrec range computations that recurse + /// through backedge-taken count computation. Used to bound the mutual + /// recursion between getRangeRef and getConstantMaxBackedgeTakenCount, which + /// can otherwise overflow the stack on pathological inputs. + unsigned AddRecRangeDepth = 0; + /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a /// predicate by splitting it into a set of independent predicates. bool ProvingSplitPredicate = false; diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 2129c8667cc6c..f0d2144e6876f 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -227,6 +227,12 @@ static cl::opt<unsigned> MaxLoopGuardCollectionDepth( "scalar-evolution-max-loop-guard-collection-depth", cl::Hidden, cl::desc("Maximum depth for recursive loop guard collection"), cl::init(1)); +static cl::opt<unsigned> MaxAddRecRangeDepth( + "scalar-evolution-max-add-rec-range-depth", cl::Hidden, + cl::desc("Maximum depth of the mutual recursion between addrec range " + "computation and backedge-taken count computation"), + cl::init(32)); + static cl::opt<bool> ClassifyExpressions("scalar-evolution-classify-expressions", cl::Hidden, cl::init(true), @@ -7004,44 +7010,59 @@ const ConstantRange &ScalarEvolution::getRangeRef( // TODO: non-affine addrec if (AddRec->isAffine()) { - const SCEV *MaxBEScev = - getConstantMaxBackedgeTakenCount(AddRec->getLoop()); - if (!isa<SCEVCouldNotCompute>(MaxBEScev)) { - APInt MaxBECount = cast<SCEVConstant>(MaxBEScev)->getAPInt(); - - // Adjust MaxBECount to the same bitwidth as AddRec. We can truncate if - // MaxBECount's active bits are all <= AddRec's bit width. - if (MaxBECount.getBitWidth() > BitWidth && - MaxBECount.getActiveBits() <= BitWidth) - MaxBECount = MaxBECount.trunc(BitWidth); - else if (MaxBECount.getBitWidth() < BitWidth) - MaxBECount = MaxBECount.zext(BitWidth); - - if (MaxBECount.getBitWidth() == BitWidth) { - auto [RangeFromAffine, Flags] = getRangeForAffineAR( - AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount); - ConservativeResult = - ConservativeResult.intersectWith(RangeFromAffine, RangeType); - const_cast<SCEVAddRecExpr *>(AddRec)->setNoWrapFlags(Flags); - - auto RangeFromFactoring = getRangeViaFactoring( - AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount); - ConservativeResult = - ConservativeResult.intersectWith(RangeFromFactoring, RangeType); + // Computing the range of an affine addrec requires the loop's + // backedge-taken count, the computation of which may recurse back into + // range computation (e.g. when reasoning about loop guards in + // isKnownPredicateViaConstantRanges). For deeply nested or heavily + // unrolled loops this mutual recursion can chain across many loops and + // overflow the stack, so bound its depth. Beyond the limit we skip this + // refinement and keep the conservative range computed above; this only + // affects pathologically deep recursion and never makes the range less + // conservative. + if (AddRecRangeDepth < MaxAddRecRangeDepth) { + ++AddRecRangeDepth; + llvm::scope_exit RestoreDepth([&]() { --AddRecRangeDepth; }); + + const SCEV *MaxBEScev = + getConstantMaxBackedgeTakenCount(AddRec->getLoop()); + if (!isa<SCEVCouldNotCompute>(MaxBEScev)) { + APInt MaxBECount = cast<SCEVConstant>(MaxBEScev)->getAPInt(); + + // Adjust MaxBECount to the same bitwidth as AddRec. We can truncate + // if MaxBECount's active bits are all <= AddRec's bit width. + if (MaxBECount.getBitWidth() > BitWidth && + MaxBECount.getActiveBits() <= BitWidth) + MaxBECount = MaxBECount.trunc(BitWidth); + else if (MaxBECount.getBitWidth() < BitWidth) + MaxBECount = MaxBECount.zext(BitWidth); + + if (MaxBECount.getBitWidth() == BitWidth) { + auto [RangeFromAffine, Flags] = + getRangeForAffineAR(AddRec->getStart(), + AddRec->getStepRecurrence(*this), MaxBECount); + ConservativeResult = + ConservativeResult.intersectWith(RangeFromAffine, RangeType); + const_cast<SCEVAddRecExpr *>(AddRec)->setNoWrapFlags(Flags); + + auto RangeFromFactoring = getRangeViaFactoring( + AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount); + ConservativeResult = + ConservativeResult.intersectWith(RangeFromFactoring, RangeType); + } } - } - // Now try symbolic BE count and more powerful methods. - if (UseExpensiveRangeSharpening) { - const SCEV *SymbolicMaxBECount = - getSymbolicMaxBackedgeTakenCount(AddRec->getLoop()); - if (!isa<SCEVCouldNotCompute>(SymbolicMaxBECount) && - getTypeSizeInBits(MaxBEScev->getType()) <= BitWidth && - AddRec->hasNoSelfWrap()) { - auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR( - AddRec, SymbolicMaxBECount, BitWidth, SignHint); - ConservativeResult = - ConservativeResult.intersectWith(RangeFromAffineNew, RangeType); + // Now try symbolic BE count and more powerful methods. + if (UseExpensiveRangeSharpening) { + const SCEV *SymbolicMaxBECount = + getSymbolicMaxBackedgeTakenCount(AddRec->getLoop()); + if (!isa<SCEVCouldNotCompute>(SymbolicMaxBECount) && + getTypeSizeInBits(MaxBEScev->getType()) <= BitWidth && + AddRec->hasNoSelfWrap()) { + auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR( + AddRec, SymbolicMaxBECount, BitWidth, SignHint); + ConservativeResult = + ConservativeResult.intersectWith(RangeFromAffineNew, RangeType); + } } } } diff --git a/llvm/test/Analysis/ScalarEvolution/addrec-range-recursion-depth.ll b/llvm/test/Analysis/ScalarEvolution/addrec-range-recursion-depth.ll new file mode 100644 index 0000000000000..be1e3ef4fb731 --- /dev/null +++ b/llvm/test/Analysis/ScalarEvolution/addrec-range-recursion-depth.ll @@ -0,0 +1,36 @@ +; RUN: opt -disable-output -passes='print<scalar-evolution>' %s +; RUN: opt -disable-output -passes='print<scalar-evolution>' \ +; RUN: -scalar-evolution-max-add-rec-range-depth=0 %s + +; Computing the range of an affine addrec requires the loop's backedge-taken +; count, whose computation can recurse back into range computation through +; loop-guard reasoning. On pathological inputs this mutual recursion can chain +; across many loops and overflow the stack. ScalarEvolution bounds the depth of +; this recursion via -scalar-evolution-max-add-rec-range-depth; verify that +; analysis still succeeds (and does not crash) when that refinement is limited. + +define void @nested(i32 %n, i32 %m, ptr %p) { +entry: + br label %outer.header + +outer.header: + %i = phi i32 [ 0, %entry ], [ %i.next, %outer.latch ] + %outer.cmp = icmp slt i32 %i, %n + br i1 %outer.cmp, label %inner.header, label %exit + +inner.header: + %j = phi i32 [ 0, %outer.header ], [ %j.next, %inner.header ] + %idx = add nsw i32 %i, %j + %gep = getelementptr inbounds i32, ptr %p, i32 %idx + store i32 %idx, ptr %gep, align 4 + %j.next = add nsw i32 %j, 1 + %inner.cmp = icmp slt i32 %j.next, %m + br i1 %inner.cmp, label %inner.header, label %outer.latch + +outer.latch: + %i.next = add nsw i32 %i, 1 + br label %outer.header + +exit: + ret void +} `````````` </details> https://github.com/llvm/llvm-project/pull/206724 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
