[WIP][LoopUnrolling] Add flag to restrict the unroll with large loop size

[Allen]

Summary

Disable large loop unroll as it will exhaust the stack if without setting with ulimit -s unlimited
while getting loop count in recursion function computeBackedgeTakenCount etc.

related issue:
https://bugs.llvm.org/show_bug.cgi?id=49783

[nikic]

Skipping very large loops might make sense as a compile-time optimization (don't bother analyzing loops that definitely can't be unrolled), but I don't think it's a solution to a stack overflow in SCEV. It can happen through other ways than loop unrolling. SCEV uses recursive construction and stack overflows are a known issue -- it deals with them through various depth cutoffs. Maybe one is missing somewhere?

[Allen]

In D104679#2832502, @nikic wrote:

Skipping very large loops might make sense as a compile-time optimization (don't bother analyzing loops that definitely can't be unrolled), but I don't think it's a solution to a stack overflow in SCEV. It can happen through other ways than loop unrolling. SCEV uses recursive construction and stack overflows are a known issue -- it deals with them through various depth cutoffs. Maybe one is missing somewhere?

Yes, if a case unroll the loops manually may also happen such issue. the root reason is too many node to dispose SCEV
in this case, the recursive call between createSCEV and getSCEV, and both them don't have a depth cutoffs now. So need a cutoff in createSCEV ?

[lebedev.ri]

I'm still not fine with this approach:

1. 1000 is way too low here. E.g. for znver3 the ideal loop size after unroll is 4096, which means that even partial unroll will blow past this threshold.
2. The threshold will depend on the underlying libc, since the default stack size differs between them.
3. for testing purposes implies this never happens in real world, while the very existence of the patch implies that it does..

It would be really best to deal with the actual stack overflows.

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

1129

[reames]

Agree with others, this seems like the wrong approach.

And yes, if we need to add a depth parameter to getSCEV, we should. I really doubt we do though. We probably *do* need to add one to all of the getXExpr variants though.

[Allen]

Yes, In fact, we already have many cutoffs , but they are only limit special type of getExpr , such as:

MaxArithDepth and MaxAddRecSize is used for getMulExpr, MaxCastDepth is used for getTruncateExpr, so it is natural that
we don't cover all the path of getXExpr variants.

if I add a new cutoff for getSCEV, there will still some other cases need to add, do we have some more general idea to dispose this ?
If no, I can just add one for getSCEV firstly.

[lebedev.ri]

Let me take a look, i might have an idea how to un-recurse it..

[Allen]

In D104679#2835271, @lebedev.ri wrote:

Let me take a look, i might have an idea how to un-recurse it..

hi , do you have some idea ?

[Allen]

it seems fixed with https://reviews.llvm.org/D114650

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

static cl::opt<unsigned> UnrollMaxCount(
     cl::desc("Set the max unroll count for partial and runtime unrolling, for"
              "testing purposes"));
 
 static cl::opt<unsigned> UnrollFullMaxCount(
     "unroll-full-max-count", cl::Hidden,
     cl::desc(
         "Set the max unroll count for full unrolling, for testing purposes"));
 
+static cl::opt<unsigned> UnrollFullSizeThreshold(
+    "unroll-full-size-threshold", cl::init(1000), cl::Hidden,
+    cl::desc(
+        "Set the size threshold for full unrolling, for testing purposes"));
+
 static cl::opt<bool>
     UnrollAllowPartial("unroll-allow-partial", cl::Hidden,
                        cl::desc("Allows loops to be partially unrolled until "
                                 "-unroll-threshold loop size is reached."));
 
 static cl::opt<bool> UnrollAllowRemainder(
     "unroll-allow-remainder", cl::Hidden,
     cl::desc("Allow generation of a loop remainder (extra iterations) "
static LoopUnrollResult tryToUnrollLoop(
   if (OptForSize)
     UP.Threshold = std::max(UP.Threshold, LoopSize + 1);
 
   if (NumInlineCandidates != 0) {
     LLVM_DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");
     return LoopUnrollResult::Unmodified;
   }
 
+  if (LoopSize > UnrollFullSizeThreshold) {
+    LLVM_DEBUG(dbgs() << "  Not unrolling loop with as large loop size.\n");
+    return LoopUnrollResult::Unmodified;
+  }
+
   // Find the smallest exact trip count for any exit. This is an upper bound
   // on the loop trip count, but an exit at an earlier iteration is still
   // possible. An unroll by the smallest exact trip count guarantees that all
   // brnaches relating to at least one exit can be eliminated. This is unlike
   // the max trip count, which only guarantees that the backedge can be broken.
   unsigned TripCount = 0;
   unsigned TripMultiple = 1;
   SmallVector<BasicBlock *, 8> ExitingBlocks;