[SCEV] Guard movement of insertion point for loop-invariants (take 2)

[wristow]

Summary

This reinstates r347934, along with a tweak to address a problem with PHI node ordering that that commit created (or exposed). That commit was reverted at r348426, due to the PHI node issue.

Original commit message:

r320789 suppressed moving the insertion point of SCEV expressions with
dev/rem operations to the loop header in non-loop-invariant situations.
This, and similar, hoisting is also unsafe in the loop-invariant case,
since there may be a guard against a zero denominator. This is an
adjustment to the fix of r320789 to suppress the movement even in the
loop-invariant case.

This fixes PR30806.

Here is a reduced test-case that demonstrates the PHI node issue:

extern void foo(char *, unsigned , unsigned *);
extern void bar(int *, long);
extern char *processBuf(char *);

extern unsigned theSize;

void foo(char *buf, unsigned denominator, unsigned *flag) {
  int incr = (int) (theSize / denominator);
  int inx = 0;
  while (*flag) {
    int itmp = inx + incr;
    int i = (int) theSize;
    bar(&i, (long) itmp);
    buf = processBuf(buf);
    inx = itmp;
  }
}

When compiling this test-case at -O2 using r347934, an instruction is placed between PHI nodes during Induction Variable Simplification, and that causes an asssertion to fail later on:

$ clang -c -O2 tst.c
  ...
llvm/include/llvm/IR/Instructions.h:2714: llvm::Value* llvm::PHINode::getOperand(unsigned int) const: Assertion `i_nocapture < OperandTraits<PHINode>::operands(this) && "getOperand() out of range!"' failed.
  ...
$

The test-case "pr30806-phi-scev.ll" in this proposed patch shows the issue when running opt with -indvars:

$ opt -S -indvars -o x.ll pr30806-phi-scev.ll
PHI nodes not grouped at top of basic block!
  %buf.addr.07 = phi i8* [ %buf, %while.body.lr.ph ], [ %call, %while.body ]
label %while.body
in function foo
LLVM ERROR: Broken function found, compilation aborted!
$

To be clear, this PHI node problem doesn't happen with current ToT, because r347934 was reverted at r348426 (although the integer-div-by-0 problem of PR30806 does still happen with ToT). The patch proposed here is the original work of r347934, with an adjustment to the insertion-point, by checking whether the insertion-point is at a PHI node. Specifically, it adds the following two lines of code (along with an additional test-case) to the commit of r347934:

if (isa<PHINode>(*InsertPt))
  InsertPt = &*InsertPt->getParent()->getFirstInsertionPt();

Bluntly, I feel this is safe, but I wonder whether it is "brute-force". That is, when the InsertPt is a PHINode, it's not legal -- and calling getFirstInsertPt() as shown above will fix it. But I wonder whether the underlying bug is that the InsertPt should be guaranteed to never be a PHINode at that point in the code?

To put it another way, this problem didn't manifest prior to r347934 (or from a historical perspective, the same issue appeared when a similar SCEV fix was made at r289412, but which was reverted shortly thereafter at r289453). Suppressing the hoisting of some expressions (which is what r347934 did) seems like it should be safe. So it feels like there is a deeper issue in that suppressing the hoisting (because SafeToHoist returned false) surprisingly resulted in the placement of a non-PHI-node instruction between two PHI-nodes. I thought if I could come up with a test-case that has this PHI-node issue irrespective of whether SafeToHoist returned true or false (that is, even before r347934 was made), I might have better luck analyzing it and finding a deeper root cause. But I was unable to find a test-case that triggered this when the SafeToHoist returned true. From that perspective, I considered only adding the two new lines that move the InsertPt when SafeToHoist was false, but if the addition of the above two lines is a "proper solution", it seems like it's perfectly reasonable to do that irrespective of what SafeToHoist returns.

[wristow]

ping

[mkazantsev]

I did not look into this too deeply, but the problem you're describing sounds like it can be solved by setting InsertPt to getFirstNonPHI at some point.

[wristow]

In D57428#1397625, @mkazantsev wrote:

I did not look into this too deeply, but the problem you're describing sounds like it can be solved by setting InsertPt to getFirstNonPHI at some point.

Thanks for the comment @mkazantsev. I think the two lines I added (relative to the commit of r347934, which exposed this PHINode issue):

if (isa<PHINode>(*InsertPt))
  InsertPt = &*InsertPt->getParent()->getFirstInsertionPt();

are doing essentially that (with a slight tweak). Specifically, that call to getFirstInsertionPt() does call getFirstNonPHI(), and then also checks to see whether that gets to a LandingPad instruction (and if so, skips over the LandingPad, too). Since the other adjustments to InsertPt in this code also use this "wrapper" of getFirstInsertionPt() rather than calling getFirstNonPHI() directly, I felt safer using that approach.

[wristow]

ping

[wristow]

ping

[wristow]

ping x 3

[sanjoy]

Apologies for the late review Warren.

I agree that it is weird that the insert point is a PHI node. Have you traced through the code to see how we're ending up in that situation? Is IndVarSimplify choosing this insertion point?

[wristow]

In D57428#1430436, @sanjoy wrote:

Apologies for the late review Warren.

I agree that it is weird that the insert point is a PHI node. Have you traced through the code to see how we're ending up in that situation? Is IndVarSimplify choosing this insertion point?

Thanks for the comment, Sanjoy.

Loosely, yes, IndVarSimplify is choosing this insertion point. To elaborate, it selects that insertion point in WidenIV::createWideIV(), in the following code:

// The rewriter provides a value for the desired IV expression. This may
// either find an existing phi or materialize a new one. Either way, we
// expect a well-formed cyclic phi-with-increments. i.e. any operand not part
// of the phi-SCC dominates the loop entry.
Instruction *InsertPt = &L->getHeader()->front();
WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt));

where the header Basic Block starts out with 2 PHI nodes.

(Side note: The AddRec here is:

{0,+,(sext i32 (%0 /u %denominator) to i64)}<nsw><%while.body>

More on this point below.)

To me, it doesn't feel like changing the above code to use getFirstInsertionPt() on the parent BB of InsertPt is a good approach. I just experimented with that now, and I found it solved the first instance of the insertion point being a PHI node, but as the above AddRec was recursively processed, it eventually called SCEVExpander::getAddRecExprPHILiterally(), which has the following code:

// Expand the step somewhere that dominates the loop header.
Value *StepV = expandCodeFor(Step, IntTy, &L->getHeader()->front());

That &L->getHeader()->front() arg to expandCodeFor() is passed to setInsertPoint(), and this again causes the same trouble. If I change this to also get the getFirstInsertionPt() on the parent BB of &L->getHeader()->front(), then my test-case passes.

So tweaking these two points (WidenIV::createWideIV() and SCEVExpander::getAddRecExprPHILiterally()) is another possible solution to investigate. But (a) I don't feel like these changes are safe (but I'm not experienced in this area), and (b) I wonder whether there are other places that would need similar changes but just aren't triggered by my test-case.

One further observation about the AddRec:

{0,+,(sext i32 (%0 /u %denominator) to i64)}<nsw><%while.body>

All that is really being attempted here is to hoist the sign-extension of the quotient out of a loop. The actual division is before the loop in the input .ll file (and it was before the loop in the original C++ code). In other words, we aren't trying to hoist an unsafe division out of the loop because the division never was even in the loop. But SafeToHoist() isn't aware of that -- it "sees" the /u in the expression, and decides it shouldn't hoist it. If instead, we could somehow know that the only expression that we're considering hoisting is the sext (and then allow that expression to be hoisted), then all would be fine (FTR, the sext eventually does get hoisted by other optimizations). I say this with the caveat that I don't deeply understand this SCEV mechanism.

[sanjoy]

Ok, looks like we're somewhat sloppy with our choice of insertion points here (and it should not be incumbent on you to fix this). Can you please add a comment that mentions that this is due to indvarsimplify?

[wristow]

Thanks for the review @sanjoy . I've updated it with a comment about IndVarSimplify, and will commit.

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

 // 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();
-  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 {
-      // We can move insertion point only if there is no div or rem operations
-      // otherwise we are risky to move it over the check for zero denominator.
-      auto SafeToHoist = [](const SCEV *S) {
-        return !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 PR35406).
-                    return true;
-                  }
-                  return false;
-                });
-      };
+
+  if (SafeToHoist(S)) {
+    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) &&
-          SafeToHoist(S))
+        if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
           InsertPt = &*L->getHeader()->getFirstInsertionPt();
         while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
                (isInsertedInstruction(InsertPt) ||
-              isa<DbgInfoIntrinsic>(InsertPt))) {
+                isa<DbgInfoIntrinsic>(InsertPt)))
           InsertPt = &*std::next(InsertPt->getIterator());
-      }
         break;
       }
+    }
+  }
+
+  // IndVarSimplify sometimes sets the insertion point at the block start, even
+  // when there are PHIs at that point.  We must correct for this.
+  if (isa<PHINode>(*InsertPt)) 
+    InsertPt = &*InsertPt->getParent()->getFirstInsertionPt();
 
   // 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/LoopVectorize/pr30806-phi-scev.ll

+; RUN: opt -S -indvars < %s | FileCheck %s
+
+; Produced from the test-case:
+;
+; extern void foo(char *, unsigned , unsigned *);
+; extern void bar(int *, long);
+; extern char *processBuf(char *);
+;
+; extern unsigned theSize;
+;
+; void foo(char *buf, unsigned denominator, unsigned *flag) {
+;   int incr = (int) (theSize / denominator);
+;   int inx = 0;
+;   while (*flag) {
+;     int itmp = inx + incr;
+;     int i = (int) theSize;
+;     bar(&i, (long) itmp);
+;     buf = processBuf(buf);
+;     inx = itmp;
+;   }
+; }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+@theSize = external local_unnamed_addr global i32, align 4
+
+define void @foo(i8* %buf, i32 %denominator, i32* %flag) local_unnamed_addr {
+entry:
+  %i = alloca i32, align 4
+  %0 = load i32, i32* @theSize, align 4
+  %div = udiv i32 %0, %denominator
+  %1 = load i32, i32* %flag, align 4
+  %tobool5 = icmp eq i32 %1, 0
+  br i1 %tobool5, label %while.end, label %while.body.lr.ph
+
+while.body.lr.ph:                                 ; preds = %entry
+  %2 = bitcast i32* %i to i8*
+  br label %while.body
+
+while.body:                                       ; preds = %while.body.lr.ph, %while.body
+; Check that there are two PHIs followed by a 'sext' in the same block, and that
+; the test does not crash.
+; CHECK:        phi
+; CHECK-NEXT:   phi
+; CHECK-NEXT:   sext
+  %buf.addr.07 = phi i8* [ %buf, %while.body.lr.ph ], [ %call, %while.body ]
+  %inx.06 = phi i32 [ 0, %while.body.lr.ph ], [ %add, %while.body ]
+  %add = add nsw i32 %inx.06, %div
+  %3 = load i32, i32* @theSize, align 4
+  store i32 %3, i32* %i, align 4
+  %conv = sext i32 %add to i64
+  call void @bar(i32* nonnull %i, i64 %conv)
+  %call = call i8* @processBuf(i8* %buf.addr.07)
+  %4 = load i32, i32* %flag, align 4
+  %tobool = icmp eq i32 %4, 0
+  br i1 %tobool, label %while.end.loopexit, label %while.body
+
+while.end.loopexit:                               ; preds = %while.body
+  br label %while.end
+
+while.end:                                        ; preds = %while.end.loopexit, %entry
+  ret void
+}
+
+declare void @bar(i32*, i64) local_unnamed_addr
+declare i8* @processBuf(i8*) local_unnamed_addr

llvm/trunk/test/Transforms/LoopVectorize/pr30806.ll

+; RUN: opt -loop-vectorize -S < %s 2>&1 | FileCheck %s
+
+; Produced from test-case:
+;
+; void testGuardedInnerLoop(uint32_t *ptr, uint32_t denom, uint32_t numer, uint32_t outer_lim)
+; {
+;   for(uint32_t outer_i = 0; outer_i < outer_lim; ++outer_i) {
+;     if (denom > 0) {
+;       const uint32_t lim = numer / denom;
+;
+;       for (uint32_t i = 0; i < lim; ++i)
+;         ptr[i] = 1;
+;     }
+;   }
+; }
+
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @testGuardedInnerLoop(i32* %ptr, i32 %denom, i32 %numer, i32 %outer_lim) {
+entry:
+  %cmp1 = icmp eq i32 %outer_lim, 0
+  br i1 %cmp1, label %exit, label %loop1.preheader
+
+; Verify that a 'udiv' does not appear between the 'loop1.preheader' label, and
+; whatever label comes next.
+loop1.preheader:
+; CHECK-LABEL: loop1.preheader:
+; CHECK-NOT: udiv
+; CHECK-LABEL: :
+  br label %loop1
+
+loop1:
+  %outer_i = phi i32 [ %inc1, %loop2.exit ], [ 0, %loop1.preheader ]
+  %0 = add i32 %denom, -1
+  %1 = icmp ult i32 %0, %numer
+  br i1 %1, label %loop2.preheader, label %loop2.exit
+
+; Verify that a 'udiv' does appear between the 'loop2.preheader' label, and
+; whatever label comes next.
+loop2.preheader:
+; CHECK-LABEL: loop2.preheader:
+; CHECK: udiv
+; CHECK-LABEL: :
+  %lim = udiv i32 %numer, %denom
+  %2 = zext i32 %lim to i64
+  br label %loop2
+
+loop2:
+  %indvar.loop2 = phi i64 [ 0, %loop2.preheader ], [ %indvar.loop2.next, %loop2 ]
+  %arrayidx = getelementptr inbounds i32, i32* %ptr, i64 %indvar.loop2
+  store i32 1, i32* %arrayidx, align 4
+  %indvar.loop2.next = add nuw nsw i64 %indvar.loop2, 1
+  %cmp2 = icmp ult i64 %indvar.loop2.next, %2
+  br i1 %cmp2, label %loop2, label %loop2.exit
+
+loop2.exit:
+  %inc1 = add nuw i32 %outer_i, 1
+  %exitcond = icmp eq i32 %inc1, %outer_lim
+  br i1 %exitcond, label %exit, label %loop1
+
+exit:
+  ret void
+}