[LoopOptimizer][Fix]PR32859, PR24738

[dtemirbulatov]

Summary

The Loop vectorizer pass introduced undef value while it is fixing output of LCSSA form.
Here it is:

before: %e.0.ph = phi i32 [ 0, %for.inc.2.i ]
after: %e.0.ph = phi i32 [ 0, %for.inc.2.i ], [ undef, %middle.block ]

and after this change we have:

%e.0.ph = phi i32 [ 0, %for.inc.2.i ]
%e.0.ph = phi i32 [ 0, %for.inc.2.i ], [ 0, %middle.block ]

Ok to commit?

[davide]

Can you explain your fix? Why replacing undef with 0 just works?

test/Transforms/LoopVectorize/pr32859.ll

1–2 ↗

(On Diff #98487)

This is, unfortunately, really really brittle.
You may want to rewrite this to only run -loop-vectorize.

143–154 ↗

(On Diff #98487)

This test can be greatly reduced using bugpoint and or delta. For example, I think all these lines (attributes/metadata) aren't really needed).

[dtemirbulatov]

Well, Out of the LCSSA for we could have "phi i32 [ 0, %for.inc.2.i ]" or "phi i32 [ undef, %for.inc.2.i ]" like in PR14725, but the IR Verifier requires for PHI one entry for each predecessor of its parent basic block. The original PR14725 just added 'undef' for an predecessor BB and it is not correct. We copy the real value for another predecessor instead of bringing 'undef'.

test/Transforms/LoopVectorize/pr32859.ll

143–154 ↗

(On Diff #98487)

yes, correct.

[• dberlin]

In D33055#751254, @dtemirbulatov wrote:

Well, Out of the LCSSA for we could have "phi i32 [ 0, %for.inc.2.i ]" or "phi i32 [ undef, %for.inc.2.i ]" like in PR14725, but the IR Verifier requires for PHI one entry for each predecessor of its parent basic block. The original PR14725 just added 'undef' for an predecessor BB and it is not correct. We copy the real value for another predecessor instead of bringing 'undef'.

Not all LCSSA phis are single variable phis.

Any loop exit with multiple predecessors will have multiple incoming edges.
Why is "0" the right predecessor to pick there?
ISTM the right predecessor would be the one that we would have gone through before we split the loop.

IE if the loop is split at block B, the right predecessor is whichever would have been reached by B.

[dtemirbulatov]

I think in the particular case we are limited here to just one predecessor, there is "LCSSAPhi->getNumIncomingValues() == 1" condition above.

[• dberlin]

In D33055#751286, @dtemirbulatov wrote:

I think in the particular case we are limited here to just one predecessor, there is "LCSSAPhi->getNumIncomingValues() == 1" condition above.

Yeah, i'm not sure why (LCSSA.cpp definitely has code to create LCSSA phis that have multiple incoming values, which surprised me, since normally LCSSA is single-valued phis, but ...)
This whole thing seems like a brutal hack (i'm not sure how it's not breaking LCSSA in some cases if we really allow multi-value phis).
But your change should at least be correct for what it does :)

[davide]

Also, can you please make sure we don't miscompile any of the dups of the original bug with this patch?

[dtemirbulatov]

Also, can you please make sure we don't miscompile any of the dups of the original bug with this patch?

you mean PRPR14725's testcase? yes this one looks correct to me after this change.

[davide]

In D33055#751522, @dtemirbulatov wrote:

Also, can you please make sure we don't miscompile any of the dups of the original bug with this patch?

you mean PRPR14725's testcase? yes this one looks correct to me after this change.

Yes, you can just run the examples in:
https://bugs.llvm.org/show_bug.cgi?id=32859
and
https://bugs.llvm.org/show_bug.cgi?id=32935

and make sure they return the wrong result after NewGVN.

Thanks!

[dtemirbulatov]

yes, both examples from PR32935, PR32859 are fixed by this change

[dtemirbulatov]

update after review.

[davide]

This patch seems at least to plug a sane value rather than undef for the phi arg.
I don't think this should go in without a vectorizer expert signing it off (i.e. @mkuper or @mssimpso).

test/Transforms/LoopVectorize/pr32859.ll

1–2 ↗

(On Diff #98660)

And add a comment explaining what this test does/fixes.

26 ↗

(On Diff #98660)

I think you can probably get rid of some attributes.

28–30 ↗

(On Diff #98660)

Do you really need this?

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

4349 ↗

(On Diff #98660)

This makes sense to me. My only suggestion might would be to add an assert that LCSSAPhi->getIncomingValue(0) is loop-invariant in the original loop. We allow external uses of inductions and reductions, but we fix those phis differently before calling fixLCSSAPHIs. So if a phi doesn't yet have an entry for the middle block by the time we get to fixLCSSAPHIs, we know the incoming value should be loop-invariant.

test/Transforms/LoopVectorize/pr32859.ll

1 ↗

(On Diff #98660)

You don't need the "2>&1"

26–30 ↗

(On Diff #98660)

You don't need the attributes and metadata.

[dtemirbulatov]

another update after review. Erased attributes for the test added test's explanation. Added an assert that LCSSAPhi->getIncomingValue(0) is loop-invariant in the original loop

[dtemirbulatov]

Fixed some typos.

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
   /// Fix a first-order recurrence. This is the second phase of vectorizing
   /// this phi node.
   void fixFirstOrderRecurrence(PHINode *Phi);
 
   /// Fix a reduction cross-iteration phi. This is the second phase of
   /// vectorizing this phi node.
   void fixReduction(PHINode *Phi);
 
-  /// \brief The Loop exit block may have single value PHI nodes where the
-  /// incoming value is 'Undef'. While vectorizing we only handled real values
-  /// that were defined inside the loop. Here we fix the 'undef case'.
-  /// See PR14725.
+  /// \brief The Loop exit block may have single value PHI nodes with some
+  /// incoming value. While vectorizing we only handled real values
+  /// that were defined inside the loop and we should have one value for
+  /// each predecessor of its parent basic block. See PR14725.
   void fixLCSSAPHIs();
 
   /// Iteratively sink the scalarized operands of a predicated instruction into
   /// the block that was created for it.
   void sinkScalarOperands(Instruction *PredInst);
 
   /// Predicate conditional instructions that require predication on their
   /// respective conditions.
void InnerLoopVectorizer::fixReduction(PHINode *Phi) {
   Phi->setIncomingValue(IncomingEdgeBlockIdx, LoopExitInst);
 }
 
 void InnerLoopVectorizer::fixLCSSAPHIs() {
   for (Instruction &LEI : *LoopExitBlock) {
     auto *LCSSAPhi = dyn_cast<PHINode>(&LEI);
     if (!LCSSAPhi)
       break;
-    if (LCSSAPhi->getNumIncomingValues() == 1)
-      LCSSAPhi->addIncoming(UndefValue::get(LCSSAPhi->getType()),
-                            LoopMiddleBlock);
+    if (LCSSAPhi->getNumIncomingValues() == 1) {
+      assert(OrigLoop->isLoopInvariant(LCSSAPhi->getIncomingValue(0)) &&
+             "Incoming value isn't loop invariant");
+      LCSSAPhi->addIncoming(LCSSAPhi->getIncomingValue(0), LoopMiddleBlock);
+    }
   }
 }
 
 void InnerLoopVectorizer::sinkScalarOperands(Instruction *PredInst) {
 
   // The basic block and loop containing the predicated instruction.
   auto *PredBB = PredInst->getParent();
   auto *VectorLoop = LI->getLoopFor(PredBB);

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

+; RUN: opt < %s -loop-vectorize -S | FileCheck %s
+
+; Out of the LCSSA form we could have 'phi i32 [ loop-invariant, %for.inc.2.i ]'
+; but the IR Verifier requires for PHI one entry for each predecessor of
+; it's parent basic block. The original PR14725 solution for the issue just
+; added 'undef' for an predecessor BB and which is not correct. We copy the real
+; value for another predecessor instead of bringing 'undef'.
+
+; CHECK-LABEL: for.cond.preheader:
+; CHECK: %e.0.ph = phi i32 [ 0, %if.end.2.i ], [ 0, %middle.block ]
+
+; Function Attrs: nounwind uwtable
+define void @main() #0 {
+entry:
+  br label %for.cond1.preheader.i
+
+for.cond1.preheader.i:                            ; preds = %if.end.2.i, %entry
+  %c.06.i = phi i32 [ 0, %entry ], [ %inc5.i, %if.end.2.i ]
+  %tobool.i = icmp ne i32 undef, 0
+  br label %if.end.2.i
+
+if.end.2.i:                                       ; preds = %for.cond1.preheader.i
+  %inc5.i = add nsw i32 %c.06.i, 1
+  %cmp.i = icmp slt i32 %inc5.i, 16
+  br i1 %cmp.i, label %for.cond1.preheader.i, label %for.cond.preheader
+
+for.cond.preheader:                               ; preds = %if.end.2.i
+  %e.0.ph = phi i32 [ 0, %if.end.2.i ]
+  unreachable
+}