Fix a stack overflow in ScalarEvolution.

[jreiffers]

Summary

Unfortunately, this overflow is extremely hard to reproduce reliably (in fact, I was unable to do so). The issue is that:

• getOperandsToCreate sometimes skips creating an SCEV for the LHS
• then, createSCEV is called for the BinaryOp
• ... which calls getNoWrapFlagsFromUB
• ... which under certain circumstances calls isSCEVExprNeverPoison
• ... which under certain circumstances requires the SCEVs of all operands

For certain deep dependency trees, this causes a stack overflow.

[nikic]

Before doing something like this, we should evaluate compile-time impact of dropping this optimization entirely.

[jreiffers]

In D129745#3651133, @nikic wrote:

Before doing something like this, we should evaluate compile-time impact of dropping this optimization entirely.

Happy to do that. programUndefinedIfPoison looks fairly expensive on its own. I'm fairly new to this project, do you have a pointer what to run? Also, unfortunately some tests appear to depend on this optimization.

It would also be great if I could drop the optimization in a follow-up, since this bug is currently causing production issues for us (and I'm not sure how long the tests will take to fix).

[fhahn]

In D129745#3651135, @jreiffers wrote:

In D129745#3651133, @nikic wrote:

Before doing something like this, we should evaluate compile-time impact of dropping this optimization entirely.

Happy to do that. programUndefinedIfPoison looks fairly expensive on its own. I'm fairly new to this project, do you have a pointer what to run? Also, unfortunately some tests appear to depend on this optimization.

It would also be great if I could drop the optimization in a follow-up, since this bug is currently causing production issues for us (and I'm not sure how long the tests will take to fix).

Would it be possible to share a reproducer? Is this a new stack overflow?

[jreiffers]

In D129745#3652264, @fhahn wrote:

Would it be possible to share a reproducer? Is this a new stack overflow?

Here's what I've been using:

std::string replace_all(const std::string &s, const std::string &needle,
                        const std::string &replacement) {
  std::size_t prev = 0, pos;
  std::string out = s;
  while ((pos = out.find(needle, prev)) != std::string::npos) {
    prev = pos;
    out.replace(pos, needle.length(), replacement);
  }
  return out;
}

TEST_F(ScalarEvolutionsTest, StackOverflowForDeepExpression) {
#define MAX 70
#define MAX_STR "70"

  std::string kLoopBodyTemplate = R"(
    %a${n} = getelementptr inbounds i8, ptr %0, i64 14794768
    %b${n} = getelementptr inbounds [1 x [8192 x float]], ptr %a${n}, i64 0, i64 0, i64 %i${n-1}
    %c${n} = load float, ptr %b${n}, align 4
    %d${n} = getelementptr inbounds [1 x [8192 x [2 x float]]], ptr %1, i64 0, i64 0, i64 %i${n-1}, i64 0
    store float %c${n}, ptr %d${n}, align 8
    %e${n} = getelementptr inbounds i8, ptr %1, i64 14762000
    %f${n} = getelementptr inbounds [1 x [8192 x float]], ptr %e${n}, i64 0, i64 0, i64 %i${n-1}
    %g${n} = load float, ptr %f${n}, align 4
    %h${n} = getelementptr inbounds [1 x [8192 x [2 x float]]], ptr %1, i64 0, i64 0, i64 %i${n-1}, i64 1
    store float %g${n}, ptr %h${n}, align 4
    %i${n} = add nuw nsw i64 %i${n-1}, 1
    %j${n} = icmp eq i64 %i${n}, 8192
  )";

  std::string ModuleCode = R"(
    define i32 @foo() { 
    while.171.exit:
      br label %fusion.286.loop_header.dim.2.preheader
    fusion.286.loop_header.dim.2.preheader:           ; preds = %fusion.286.loop_header.dim.2.preheader, %while.171.exit
      %i0 = phi i64 [ 0, %while.171.exit ], [ %i)" MAX_STR
                              R"(, %fusion.286.loop_header.dim.2.preheader ]
      %0 = inttoptr i32 0 to ptr
      %1 = inttoptr i32 0 to ptr
  )";

  for (int i = 1; i <= MAX; ++i) {
    ModuleCode += replace_all(replace_all(kLoopBodyTemplate, "${n}", itostr(i)),
                              "${n-1}", itostr(i - 1));
  }

  ModuleCode +=
      "br i1 %j" MAX_STR
      R"(, label %fusion.286.loop_exit.dim.0, label %fusion.286.loop_header.dim.2.preheader
  fusion.286.loop_exit.dim.0:
    ret i32 0
  }
  )";

  LLVMContext C;
  SMDiagnostic Err;
  std::unique_ptr<Module> M = parseAssemblyString(ModuleCode, Err, C);

  ASSERT_EQ(Err.getMessage(), "");

  struct rlimit rl;
  ASSERT_EQ(getrlimit(RLIMIT_STACK, &rl), 0);

  rl.rlim_cur = 1;
  ASSERT_EQ(setrlimit(RLIMIT_STACK, &rl), 0);

  ASSERT_TRUE(M && "Could not parse module?");
  ASSERT_TRUE(!verifyModule(*M, &llvm::errs()) &&
              "Must have been well formed!");

  runWithSE(*M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
    auto *ScevIV = SE.getSCEV(getInstructionByName(F, "i63"));
    ASSERT_NE(ScevIV, nullptr);
  });
}

But it's not very reliable, you may have to run it a few times and/or fiddle with MAX. For me it fails about 30% of the time.

[fhahn]

Thanks, I'll give that a try!

But it's not very reliable, you may have to run it a few times and/or fiddle with MAX. For me it fails about 30% of the time.

This seems very surprising. I'd expect the stack overflow to reproduce consistently as each run should produce the same call stack with the same size (at least if the depth is deep enough). There's probably some non-determinism somewhere that should also be fixed.

[nikic]

In D129745#3651135, @jreiffers wrote:

In D129745#3651133, @nikic wrote:

Before doing something like this, we should evaluate compile-time impact of dropping this optimization entirely.

Happy to do that. programUndefinedIfPoison looks fairly expensive on its own. I'm fairly new to this project, do you have a pointer what to run? Also, unfortunately some tests appear to depend on this optimization.

Ah sorry, my wording here was really ambiguous: By "optimization" I was referring to the compile-time optimization of combining operands from multiple add/muls, rather than just creating pairwise expressions. The preservation of nowrap flags via UB reasoning is important, and not something that can be dropped.

[jreiffers]

In D129745#3652395, @nikic wrote:

Ah sorry, my wording here was really ambiguous: By "optimization" I was referring to the compile-time optimization of combining operands from multiple add/muls, rather than just creating pairwise expressions. The preservation of nowrap flags via UB reasoning is important, and not something that can be dropped.

I also meant just trying to drop the special-casing of add and mul in getOperandsToCreate. I didn't run the tests myself, but bkramer mentioned that doing this (i.e. always enqueueing LHS and RHS here) broke some tests.

In D129745#3652383, @fhahn wrote:

This seems very surprising. I'd expect the stack overflow to reproduce consistently as each run should produce the same call stack with the same size (at least if the depth is deep enough). There's probably some non-determinism somewhere that should also be fixed.

I agree, it's somewhat weird. However, I was running this on our internal test infrastructure, so the tests may have been running on different architectures/CPUs. Maybe that plays a role.

[nikic]

Compile-time impact on CTMark for removing the special handling: http://llvm-compile-time-tracker.com/compare.php?from=2659e1bf4b54cf9c2fadac0813e5e0ab4d2c49d5&to=38c11e7340b66928403db9eceb302bb216ca060b&stat=instructions

[jreiffers]

In D129745#3655221, @nikic wrote:

Compile-time impact on CTMark for removing the special handling: http://llvm-compile-time-tracker.com/compare.php?from=2659e1bf4b54cf9c2fadac0813e5e0ab4d2c49d5&to=38c11e7340b66928403db9eceb302bb216ca060b&stat=instructions

Thanks! What's the conclusion?

[jreiffers]

Friendly ping on this.

[jreiffers]

Rebase changes.

[bkramer]

Can we land this? The deep recursion is actively causing trouble for LLVM users by crashing the compiler. Even if it's not a perfect fix it's still better than overflowing the stack.

[fhahn]

Yeah, let me try to reproduce this locally tomorrow and land it over wise. @jreiffers could you share the interesting bit of the stack-trace causing the overflow?

[jreiffers]

@fhahn The recursion loop is createSCEV -> isSCEVExprNeverPoison -> createSCEVIter -> createSCEV (see also the summary of this change).

[fhahn]

LGTM thanks! I managed to reproduce this locally with much larger value for MAX & co. It looks like avoiding the optimization is the only option here, as createSCEV itself will create SCEVs for all intermediate binary expressions in those cases......

It might be good to adjust the commit message to be a bit more precise about the actual fix.

[jreiffers]

Thanks for the reviews and discussion!

[frasercrmck]

llvm/lib/Analysis/ScalarEvolution.cpp

7318

Correct me if I'm wrong but we're not yet able to use C++17 features. This is causing a build bot failure: https://lab.llvm.org/buildbot#builders/77/builds/20381

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

7318

@jreiffers what's the status of this? Does the commit need reverting?

[fhahn]

It might be good to adjust the commit message to be a bit more precise about the actual fix.

It would have been good to improve the commit title....

[jreiffers]

In D129745#3702054, @fhahn wrote:

It might be good to adjust the commit message to be a bit more precise about the actual fix.

It would have been good to improve the commit title....

Sorry, missed that. Also, I don't know what improvement you had in mind. I find it pretty clear.

llvm/lib/Analysis/ScalarEvolution.cpp

7318

This was fixed in https://reviews.llvm.org/rG3e9e43b48eb7a6a9b317e4c32ba0ee672630842b.

[fhahn]

In D129745#3702070, @jreiffers wrote:

In D129745#3702054, @fhahn wrote:

It might be good to adjust the commit message to be a bit more precise about the actual fix.

It would have been good to improve the commit title....

Sorry, missed that. Also, I don't know what improvement you had in mind. I find it pretty clear.

It's too generic, it should ideally be more clear about which stack overflow was fixed for example.

[jreiffers]

In D129745#3702072, @fhahn wrote:

It's too generic, it should ideally be more clear about which stack overflow was fixed for example.

There's a description of what causes the stack overflow in the summary. I don't really have anything to add to that.

llvm/lib/Analysis/ScalarEvolution.cpp

else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
     return getUnknown(V);
   } else if (!isa<ConstantExpr>(V))
     return getUnknown(V);
 
   Operator *U = cast<Operator>(V);
   if (auto BO = MatchBinaryOp(U, DT)) {
     bool IsConstArg = isa<ConstantInt>(BO->RHS);
     switch (BO->Opcode) {
-    case Instruction::Add: {
+    case Instruction::Add:
+    case Instruction::Mul: {
       // For additions and multiplications, traverse add/mul chains for which we
       // can potentially create a single SCEV, to reduce the number of
       // get{Add,Mul}Expr calls.
       do {
         if (BO->Op) {
           if (BO->Op != V && getExistingSCEV(BO->Op)) {
             Ops.push_back(BO->Op);
             break;
           }
         }
         Ops.push_back(BO->RHS);
         auto NewBO = MatchBinaryOp(BO->LHS, DT);
-        if (!NewBO || (NewBO->Opcode != Instruction::Add &&
-                       NewBO->Opcode != Instruction::Sub)) {
+        if (!NewBO ||
+            (U->getOpcode() == Instruction::Add &&
+             (NewBO->Opcode != Instruction::Add &&
+              NewBO->Opcode != Instruction::Sub)) ||
+            (U->getOpcode() == Instruction::Mul &&
+             NewBO->Opcode != Instruction::Mul)) {
           Ops.push_back(BO->LHS);
           break;
         }
-        BO = NewBO;
-      } while (true);
-      return nullptr;
-    }
-
-    case Instruction::Mul: {
-      do {
-        if (BO->Op) {
-          if (BO->Op != V && getExistingSCEV(BO->Op)) {
-            Ops.push_back(BO->Op);
-            break;
-          }
-        }
-        Ops.push_back(BO->RHS);
-        auto NewBO = MatchBinaryOp(BO->LHS, DT);
-        if (!NewBO || NewBO->Opcode != Instruction::Mul) {
+        // CreateSCEV calls getNoWrapFlagsFromUB, which under certain conditions
+        // requires a SCEV for the LHS.
+        if (NewBO->Op && (NewBO->IsNSW || NewBO->IsNUW)) {
+          if (auto *I = dyn_cast<Instruction>(NewBO->Op);
+              I && programUndefinedIfPoison(I)) {
             Ops.push_back(BO->LHS);
             break;
           }
+        }
         BO = NewBO;
       } while (true);
       return nullptr;
     }
     case Instruction::Sub:
     case Instruction::UDiv:
     case Instruction::URem:
       break;