[SCEVExpand] do not hoist divisions by zero (PR30935)

[sebpop]

Summary

SCEVExpand computes the insertion point for the components of a SCEV to be code generated.
When it comes to generating code for a division SCEVexpand would not be able to check (at compilation time) all the conditions necessary to avoid a division by zero.
The patch disables hoisting of expressions containing divisions by anything other than constants in order to avoid hoisting these expressions past conditions that should hold before doing the division.

The patch passes check-all on x86_64-linux.

[sanjoy]

I tried to address this some time back in rL286437, but that had to be reverted due to PR30976. Can you please take a look and make sure that this patch does not have the same problem?

Also, does the C++ unit test case from rL286437 also pass with this patch? If so, that would be nice to include too.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

1670 ↗

(On Diff #79593)

Use const auto *

1673 ↗

(On Diff #79593)

What about divisions by constant zero? If they can't happen, then add an assert here.

[sebpop]

In D27216#608086, @sanjoy wrote:

I tried to address this some time back in rL286437, but that had to be reverted due to PR30976. Can you please take a look and make sure that this patch does not have the same problem?

Also, does the C++ unit test case from rL286437 also pass with this patch? If so, that would be nice to include too.

Yes this patch also fixes PR30942: I marked it as a duplicate of the earlier PR30935.
The patch does not ICE the compiler on the testcase of PR30976.

Thanks Sanjoy for the review: I will submit an updated patch.

[sebpop]

Updated patch with all suggestions from Sanjoy.

[sebpop]

Sanjoy, I think your previous patch has fixed one more place SCEVExpander::InsertBinop():
the second assert from your unittest is still failing with the current patch:

EXPECT_EQ(DivInst->getParent(), DivFromScratchExpansionInst->getParent());

that is an expression built from scratch and inserted in the code at the same place as "x/y".
Let me fix that other place as well.

[sebpop]

Added the unittest and the change to make it pass: InsertBinop() should not hoist divisions by zero.

[sanjoy]

Hi,

I don't think this patch properly addresses PR30976 -- it only hides the symptom. For instance, this new test case crashes SCEVExpander even with this fix: https://reviews.llvm.org/differential/diff/79708/

I think the fundamental problem is that there is no clear distinction in SCEVExpander between hoisting for optimization and hoisting for correctness (i.e. for the right domination properties to hold). We need to fix that before we can fix PR30976.

llvm/lib/Analysis/ScalarEvolutionExpander.cpp

170 ↗

(On Diff #79649)

Why do you need the inline keyword here?

1679 ↗

(On Diff #79649)

This looks too complicated to be within the condition of an if -- can you extract out a bool SafeToHoist = ...?

1687 ↗

(On Diff #79649)

Why not return SC->getValue()->isZero();?

[sanjoy]

In D27216#608859, @sanjoy wrote:

Hi,

I don't think this patch properly addresses PR30976 -- it only hides the symptom. For instance, this new test case crashes SCEVExpander even with this fix: https://reviews.llvm.org/differential/diff/79708/

I think I've addressed the underlying problem with r289397 so this (along with the test case above) should be okay to go in, pending review comments.

[atrick]

How do you know this won't move division that used to be outside the loop (possibly multiple levels) inside the innermost loop?

[sebpop]

In D27216#619902, @atrick wrote:

How do you know this won't move division that used to be outside the loop (possibly multiple levels) inside the innermost loop?

You are right: expanding SCEV expressions could lead to a loss in performance.
I'm not sure we have all the information we need to generate code at least as efficient as the one we started from.

[sebpop]

In D27216#619902, @atrick wrote:

How do you know this won't move division that used to be outside the loop (possibly multiple levels) inside the innermost loop?

At least for the easy case where the expressions are the same, and one div expression is dominating the other loop nested one,
a post processing pass like PRE should be able to find the redundancy and eliminate the inner computation.

There are still two problems:

• scev folds expressions and the expressions to be code generated do not necessarily end up to be the exact expressions as computed in the code,
• in the case of Polly's use of SCEVExpand the analyzed code belongs to a different region than the place where we need to insert the code. Polly does code versioning: it places the original loop in the then clause and starts generating code in the else clause. So no matter how hard we try to find the div expression in the code above, we won't find it, because it is probably not needed in the new code except in the expansion of the scev.

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (LHSC->getValue()->isZero()) {
       Ops.erase(Ops.begin());
       --Idx;
     }
 
     if (Ops.size() == 1) return Ops[0];
   }
 
   // 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
+  // once. If so, merge them together into a 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])

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) {
   }
 
   // Cast the instruction immediately after the instruction.
   Instruction *I = cast<Instruction>(V);
   BasicBlock::iterator IP = findInsertPointAfter(I, Builder.GetInsertBlock());
   return ReuseOrCreateCast(I, Ty, Op, IP);
 }
 
+// Return true when S may contain the value zero.
+static bool mayBeValueZero(Value *V) {
+  if (ConstantInt *C = dyn_cast<ConstantInt>(V))
+    if (!C->isZero())
+      return false;
+
+  // All other expressions may have a zero value.
+  return true;
+}
+
 /// InsertBinop - Insert the specified binary operator, doing a small amount
 /// of work to avoid inserting an obviously redundant operation.
 Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode,
                                  Value *LHS, Value *RHS) {
   // Fold a binop with constant operands.
   if (Constant *CLHS = dyn_cast<Constant>(LHS))
     if (Constant *CRHS = dyn_cast<Constant>(RHS))
       return ConstantExpr::get(Opcode, CLHS, CRHS);
for (; ScanLimit; --IP, --ScanLimit) {
       if (IP == BlockBegin) break;
     }
   }
 
   // Save the original insertion point so we can restore it when we're done.
   DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc();
   SCEVInsertPointGuard Guard(Builder, this);
 
+  // Only move the insertion point up when it is not a division by zero.
+  if (Opcode != Instruction::UDiv || !mayBeValueZero(RHS)) {
     // Move the insertion point out of as many loops as we can.
     while (const Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock())) {
       if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break;
       BasicBlock *Preheader = L->getLoopPreheader();
       if (!Preheader) break;
 
       // Ok, move up a level.
       Builder.SetInsertPoint(Preheader->getTerminator());
     }
+  }
 
   // If we haven't found this binop, insert it.
   Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS));
   BO->setDebugLoc(Loc);
   rememberInstruction(BO);
 
   return BO;
 }

 // and the SCEV contains any sub scAddRecExpr type SCEV, it will be expanded
 // literally, to prevent LSR's transformed SCEV from being reverted. Otherwise,
 // the expansion will try to reuse Value from ExprValueMap, and only when it
 // fails, expand the SCEV literally.
 Value *SCEVExpander::expand(const SCEV *S) {
   // Compute an insertion point for this SCEV object. Hoist the instructions
   // as far out in the loop nest as possible.
   Instruction *InsertPt = &*Builder.GetInsertPoint();
+  bool SafeToHoist = !SCEVExprContains(S, [](const SCEV *S) {
+      if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) {
+        if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS()))
+          // Division by non-zero constants can be hoisted.
+          return SC->getValue()->isZero();
+
+        // All other divisions should not be moved as they may be divisions by
+        // zero and should be kept within the conditions of the surrounding
+        // loops that guard their execution (see PR30935.)
+        return true;
+      }
+      return false;
+    });
+  if (SafeToHoist) {
     for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
          L = L->getParentLoop())
       if (SE.isLoopInvariant(S, L)) {
         if (!L) break;
         if (BasicBlock *Preheader = L->getLoopPreheader())
           InsertPt = Preheader->getTerminator();
         else {
           // LSR sets the insertion point for AddRec start/step values to the
           // block start to simplify value reuse, even though it's an invalid
           // position. SCEVExpander must correct for this in all cases.
           InsertPt = &*L->getHeader()->getFirstInsertionPt();
         }
       } else {
         // If the SCEV is computable at this level, insert it into the header
         // after the PHIs (and after any other instructions that we've inserted
         // there) so that it is guaranteed to dominate any user inside the loop.
         if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
           InsertPt = &*L->getHeader()->getFirstInsertionPt();
         while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
                (isInsertedInstruction(InsertPt) ||
                 isa<DbgInfoIntrinsic>(InsertPt))) {
           InsertPt = &*std::next(InsertPt->getIterator());
         }
         break;
       }
+  }
 
   // Check to see if we already expanded this here.
   auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
   if (I != InsertedExpressions.end())
     return I->second;
 
   SCEVInsertPointGuard Guard(Builder, this);
   Builder.SetInsertPoint(InsertPt);

llvm/trunk/test/Transforms/LoopIdiom/pr30935.ll

+; RUN: opt -loop-idiom -S < %s | FileCheck %s
+
+; CHECK-LABEL: define i32 @main(
+; CHECK: udiv
+; CHECK-NOT: udiv
+; CHECK: call void @llvm.memset.p0i8.i64
+
+@a = common local_unnamed_addr global [4 x i8] zeroinitializer, align 1
+@b = common local_unnamed_addr global i32 0, align 4
+@c = common local_unnamed_addr global i32 0, align 4
+@d = common local_unnamed_addr global i32 0, align 4
+@e = common local_unnamed_addr global i32 0, align 4
+@f = common local_unnamed_addr global i32 0, align 4
+@g = common local_unnamed_addr global i32 0, align 4
+@h = common local_unnamed_addr global i64 0, align 8
+
+
+define i32 @main() local_unnamed_addr #0 {
+entry:
+  %0 = load i32, i32* @e, align 4
+  %tobool19 = icmp eq i32 %0, 0
+  %1 = load i32, i32* @c, align 4
+  %cmp10 = icmp eq i32 %1, 0
+  %2 = load i32, i32* @g, align 4
+  %3 = load i32, i32* @b, align 4
+  %tobool = icmp eq i32 %0, 0
+  br label %for.cond
+
+for.cond.loopexit:                                ; preds = %for.inc14
+  br label %for.cond.backedge
+
+for.cond:                                         ; preds = %for.cond.backedge, %entry
+  %.pr = load i32, i32* @f, align 4
+  %cmp20 = icmp eq i32 %.pr, 0
+  br i1 %cmp20, label %for.cond2.preheader.preheader, label %for.cond.backedge
+
+for.cond.backedge:                                ; preds = %for.cond, %for.cond.loopexit
+  br label %for.cond
+
+for.cond2.preheader.preheader:                    ; preds = %for.cond
+  br label %for.cond2.preheader
+
+for.cond2.preheader:                              ; preds = %for.cond2.preheader.preheader, %for.inc14
+  br i1 %tobool19, label %for.cond9, label %for.body3.lr.ph
+
+for.body3.lr.ph:                                  ; preds = %for.cond2.preheader
+  %div = udiv i32 %2, %3
+  %conv = zext i32 %div to i64
+  br label %for.body3
+
+for.cond4.for.cond2.loopexit_crit_edge:           ; preds = %for.body6
+  store i32 0, i32* @d, align 4
+  br label %for.cond2.loopexit
+
+for.cond2.loopexit:                               ; preds = %for.cond4.for.cond2.loopexit_crit_edge, %for.body3
+  br i1 %tobool, label %for.cond2.for.cond9_crit_edge, label %for.body3
+
+for.body3:                                        ; preds = %for.body3.lr.ph, %for.cond2.loopexit
+  %.pr17 = load i32, i32* @d, align 4
+  %tobool518 = icmp eq i32 %.pr17, 0
+  br i1 %tobool518, label %for.cond2.loopexit, label %for.body6.preheader
+
+for.body6.preheader:                              ; preds = %for.body3
+  %4 = zext i32 %.pr17 to i64
+  br label %for.body6
+
+for.body6:                                        ; preds = %for.body6.preheader, %for.body6
+  %indvars.iv = phi i64 [ %4, %for.body6.preheader ], [ %indvars.iv.next, %for.body6 ]
+  %add = add nuw nsw i64 %conv, %indvars.iv
+  %arrayidx = getelementptr inbounds [4 x i8], [4 x i8]* @a, i64 0, i64 %add
+  store i8 1, i8* %arrayidx, align 1
+  %5 = trunc i64 %indvars.iv to i32
+  %inc = add i32 %5, 1
+  %tobool5 = icmp eq i32 %inc, 0
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br i1 %tobool5, label %for.cond4.for.cond2.loopexit_crit_edge, label %for.body6
+
+for.cond2.for.cond9_crit_edge:                    ; preds = %for.cond2.loopexit
+  store i64 %conv, i64* @h, align 8
+  br label %for.cond9
+
+for.cond9:                                        ; preds = %for.cond2.for.cond9_crit_edge, %for.cond2.preheader
+  br i1 %cmp10, label %for.body12, label %for.inc14
+
+for.body12:                                       ; preds = %for.cond9
+  ret i32 0
+
+for.inc14:                                        ; preds = %for.cond9
+  %6 = load i32, i32* @f, align 4
+  %inc15 = add i32 %6, 1
+  store i32 %inc15, i32* @f, align 4
+  %cmp = icmp eq i32 %inc15, 0
+  br i1 %cmp, label %for.cond2.preheader, label %for.cond.loopexit
+}

llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp

 
 static Instruction *getInstructionByName(Function &F, StringRef Name) {
   for (auto &I : instructions(F))
     if (I.getName() == Name)
       return &I;
   llvm_unreachable("Expected to find instruction!");
 }
 
+static Argument *getArgByName(Function &F, StringRef Name) {
+  for (auto &A : F.args())
+    if (A.getName() == Name)
+      return &A;
+  llvm_unreachable("Expected to find argument!");
+}
+
 TEST_F(ScalarEvolutionsTest, CommutativeExprOperandOrder) {
   LLVMContext C;
   SMDiagnostic Err;
   std::unique_ptr<Module> M = parseAssemblyString(
       "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
       " "
       "@var_0 = external global i32, align 4"
       "@var_1 = external global i32, align 4"
TEST_F(ScalarEvolutionsTest, SCEVCompareComplexity) {
 
   ReturnInst::Create(Context, nullptr, ExitBB);
 
   ScalarEvolution SE = buildSE(*F);
 
   EXPECT_NE(nullptr, SE.getSCEV(Acc[0]));
 }
 
+TEST_F(ScalarEvolutionsTest, BadHoistingSCEVExpander_PR30942) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(
+      "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
+      " "
+      "define void @f_1(i32 %x, i32 %y, i32 %n, i1* %cond_buf) "
+      "    local_unnamed_addr { "
+      "entry: "
+      "  %entrycond = icmp sgt i32 %n, 0 "
+      "  br i1 %entrycond, label %loop.ph, label %for.end "
+      " "
+      "loop.ph: "
+      "  br label %loop "
+      " "
+      "loop: "
+      "  %iv1 = phi i32 [ %iv1.inc, %right ], [ 0, %loop.ph ] "
+      "  %iv1.inc = add nuw nsw i32 %iv1, 1 "
+      "  %cond = load volatile i1, i1* %cond_buf  "
+      "  br i1 %cond, label %left, label %right  "
+      "  "
+      "left: "
+      "  %div = udiv i32 %x, %y  "
+      "  br label %right  "
+      "  "
+      "right: "
+      "  %exitcond = icmp eq i32 %iv1.inc, %n "
+      "  br i1 %exitcond, label %for.end.loopexit, label %loop "
+      " "
+      "for.end.loopexit: "
+      "  br label %for.end "
+      " "
+      "for.end: "
+      "  ret void "
+      "} ",
+      Err, C);
+
+  assert(M && "Could not parse module?");
+  assert(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithFunctionAndSE(*M, "f_1", [&](Function &F, ScalarEvolution &SE) {
+    SCEVExpander Expander(SE, M->getDataLayout(), "unittests");
+    auto *DivInst = getInstructionByName(F, "div");
+
+    {
+      auto *DivSCEV = SE.getSCEV(DivInst);
+      auto *DivExpansion = Expander.expandCodeFor(
+          DivSCEV, DivSCEV->getType(), DivInst->getParent()->getTerminator());
+      auto *DivExpansionInst = dyn_cast<Instruction>(DivExpansion);
+      ASSERT_NE(DivExpansionInst, nullptr);
+      EXPECT_EQ(DivInst->getParent(), DivExpansionInst->getParent());
+    }
+
+    {
+      auto *ArgY = getArgByName(F, "y");
+      auto *DivFromScratchSCEV =
+          SE.getUDivExpr(SE.getOne(ArgY->getType()), SE.getSCEV(ArgY));
+
+      auto *DivFromScratchExpansion = Expander.expandCodeFor(
+          DivFromScratchSCEV, DivFromScratchSCEV->getType(),
+          DivInst->getParent()->getTerminator());
+      auto *DivFromScratchExpansionInst =
+          dyn_cast<Instruction>(DivFromScratchExpansion);
+      ASSERT_NE(DivFromScratchExpansionInst, nullptr);
+      EXPECT_EQ(DivInst->getParent(), DivFromScratchExpansionInst->getParent());
+    }
+  });
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm