[LV] Don't panic when encountering the IV of an outer loop.

[mkuper]

Summary

Bail out instead of asserting when we encounter this situation - which can actually happen.
Note that the assert I removed doesn't actually get hit (because it checks the wrong condition), but we assert a bit further down the line.

The reason the test uses the new PM is that the "bad" phi - incidentally - gets cleaned up by LoopSimplify. But LICM can create this kind of phi and preserve loop simplify form, so the cleanup has no chance to run.

This fixes PR31190.
We may want to solve this in a less conservative manner, since this phi is actually uniform within the inner loop (or we may want LICM to output a cleaner promotion to begin with), but I'd rather fix the crash for now.

[sanjoy]

I can't really review the code; but, did you consider writing the test case in C++ (inside unittests/)? Relying on LICM to create just the right preconditions seems somewhat fragile (that is, it is possible that a future change to LICM will make this test a no-op).

[mkuper]

In D28490#640629, @sanjoy wrote:

I can't really review the code; but, did you consider writing the test case in C++ (inside unittests/)? Relying on LICM to create just the right preconditions seems somewhat fragile (that is, it is possible that a future change to LICM will make this test a no-op).

I agree, it's fragile, but I think it would be really nice to keep this kind of test-case in IR, for the sake of maintainability.
This whole "LV requires LCSSA and LoopSimplify" issue will need to be solved as part of the move to the new pass manager. I'd prefer to leave a FIXME in the test, and set myself a reminder to actually go and fix it in a couple of months. :-)

(Actually, maybe I can avoid this whole thing by running the test with the new pass manager instead of the old one! I'll give it a shot.)

[mkuper]

Test no longer relies on LICM. Thanks, Sanjoy.

[delena]

test/Transforms/LoopVectorize/pr31190.ll

8 ↗

(On Diff #83726)

Can you add the source code to the comments? You try to vectorize the "for.body3" loop, right? What PHI belongs to the outer loop?

[mkuper]

test/Transforms/LoopVectorize/pr31190.ll

8 ↗

(On Diff #83726)

Yes, it's trying to vectorize the inner loop (for.body3).
The problematic PHI is:
%0 = phi i32 [ undef, %for.cond1.preheader ], [ %inc54, %for.body3 ]

This phi is in the inner loop, but %inc54 is an IV phi in the outer loop:
%inc54 = phi i32 [ %inc5, %for.cond1.for.inc4_crit_edge ], [ %c.promoted, %entry ]
So SCEV recognizes %0 as an AddRec, but with respect to the outer loop.

I'll add the above explanation in a comment.
Not sure about the source, though - the IR was, I think, hand-reduced by @davide from the source in PR31190, so I'm not sure having the "original" source he makes a lot of sense.

[delena]

LGTM for this patch. You can open a PR, since this loop should be vectorized and the PHI is uniform.
Please add a comment, at least to this test, pointing to the uniform PHI node.

[mssimpso]

test/Transforms/LoopVectorize/pr31190.ll

8 ↗

(On Diff #83726)

So SCEV recognizes %0 as an AddRec, but with respect to the outer loop.

I haven't tried this so I'm not really sure, but would SE->getSCEVAtScope(Phi, TheLoop) be useful here?

[mkuper]

test/Transforms/LoopVectorize/pr31190.ll

8 ↗

(On Diff #83726)

I think it will work, but that doesn't really help. We'll just end up with an unidentified phi, so we won't vectorize regardless.
I'd prefer to leave this explicit, but I don't mind trying getSCEVatScope if you think that's better.

[mssimpso]

test/Transforms/LoopVectorize/pr31190.ll

8 ↗

(On Diff #83726)

Ah, yes you're right, the phi would just be unknown. Leaving the check explicit is probably better. This looks good to me!

llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp

bool InductionDescriptor::isInductionPHI(PHINode *Phi, const Loop *TheLoop,
   const SCEV *PhiScev = Expr ? Expr : SE->getSCEV(Phi);
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev);
 
   if (!AR) {
     DEBUG(dbgs() << "LV: PHI is not a poly recurrence.\n");
     return false;
   }
 
-  assert(TheLoop->getHeader() == Phi->getParent() &&
-         "PHI is an AddRec for a different loop?!");
+  if (AR->getLoop() != TheLoop) {
+    // FIXME: We should treat this as a uniform. Unfortunately, we
+    // don't currently know how to handled uniform PHIs.
+    DEBUG(dbgs() << "LV: PHI is a recurrence with respect to an outer loop.\n");
+    return false;    
+  }
+
   Value *StartValue =
     Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader());
   const SCEV *Step = AR->getStepRecurrence(*SE);
   // Calculate the pointer stride and check if it is consecutive.
   // The stride may be a constant or a loop invariant integer value.
   const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
   if (!ConstStep && !SE->isLoopInvariant(Step, TheLoop))
     return false;

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

+; RUN: opt -passes='loop-vectorize' -debug -S < %s 2>&1 | FileCheck %s
+; REQUIRES: asserts
+
+; This checks we don't crash when the inner loop we're trying to vectorize
+; is a SCEV AddRec with respect to an outer loop.
+
+; In this case, the problematic PHI is:
+; %0 = phi i32 [ undef, %for.cond1.preheader ], [ %inc54, %for.body3 ]
+; Since %inc54 is the IV of the outer loop, and %0 equivalent to it,
+; we get the situation described above.
+
+; This test uses the new PM, because with the old PM, running loop-vectorize
+; would explicitly run loop-simplify. Even though this loop is already in
+; simplified form, loop-simplify would still clean up the phi.
+; The reason this matters is that in a real optimizer pipeline, LICM can create
+; such PHIs, and since it preserves loop simplified form, the cleanup has
+; no chance to run.
+
+; Code that leads to this situation can look something like:
+;
+; int a, b[1], c;
+; void fn1 ()
+; {
+;  for (; c; c++)
+;    for (a = 0; a; a++)
+;      b[c] = 4;
+; }
+;
+; The PHI is an artifact of the register promotion of c.
+
+@c = external global i32, align 4
+@a = external global i32, align 4
+@b = external global [1 x i32], align 4
+
+; CHECK: LV: PHI is a recurrence with respect to an outer loop.
+; CHECK: LV: Not vectorizing: Cannot prove legality.
+; CHECK-LABEL: @test
+define void @test() {
+entry:
+  %a.promoted2 = load i32, i32* @a, align 1
+  %c.promoted = load i32, i32* @c, align 1
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond1.for.inc4_crit_edge, %entry
+  %inc54 = phi i32 [ %inc5, %for.cond1.for.inc4_crit_edge ], [ %c.promoted, %entry ]
+  %inc.lcssa3 = phi i32 [ %inc.lcssa, %for.cond1.for.inc4_crit_edge ], [ %a.promoted2, %entry ]
+  br label %for.body3
+
+for.body3:                                        ; preds = %for.body3, %for.cond1.preheader
+  %inc1 = phi i32 [ %inc.lcssa3, %for.cond1.preheader ], [ %inc, %for.body3 ]
+  %0 = phi i32 [ undef, %for.cond1.preheader ], [ %inc54, %for.body3 ]
+  %idxprom = sext i32 %0 to i64
+  %arrayidx = getelementptr inbounds [1 x i32], [1 x i32]* @b, i64 0, i64 %idxprom
+  store i32 4, i32* %arrayidx, align 4
+  %inc = add nsw i32 %inc1, 1
+  %tobool2 = icmp eq i32 %inc, 0
+  br i1 %tobool2, label %for.cond1.for.inc4_crit_edge, label %for.body3
+
+for.cond1.for.inc4_crit_edge:                     ; preds = %for.body3
+  %inc.lcssa = phi i32 [ %inc, %for.body3 ]
+  %.lcssa = phi i32 [ %inc54, %for.body3 ]
+  %inc5 = add nsw i32 %.lcssa, 1
+  br label %for.cond1.preheader
+}