[SLPVectorizer] Ensure dominated reduction values.

[• chatur01]

Summary

When considering incoming values as part of a reduction phi, ensure the
incoming value is dominated by said phi.

Failing to ensure this property causes miscompiles.

Fixes PR25787.

Many thanks to Mattias Eriksson for reporting, reducing and analyzing the
problem for me.

[nadav]

LGTM.

Thanks for fixing this Charlie!

[• chatur01]

Thanks for the review Nadav!

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

 
 /// \brief Try and get a reduction value from a phi node.
 ///
 /// Given a phi node \p P in a block \p ParentBB, consider possible reductions
 /// if they come from either \p ParentBB or a containing loop latch.
 ///
 /// \returns A candidate reduction value if possible, or \code nullptr \endcode
 /// if not possible.
-static Value *getReductionValue(PHINode *P, BasicBlock *ParentBB,
-                                LoopInfo *LI) {
+static Value *getReductionValue(const DominatorTree *DT, PHINode *P,
+                                BasicBlock *ParentBB, LoopInfo *LI) {
+  // There are situations where the reduction value is not dominated by the
+  // reduction phi. Vectorizing such cases has been reported to cause
+  // miscompiles. See PR25787.
+  auto DominatedReduxValue = [&](Value *R) {
+    return (
+        dyn_cast<Instruction>(R) &&
+        DT->dominates(P->getParent(), dyn_cast<Instruction>(R)->getParent()));
+  };
+
   Value *Rdx = nullptr;
 
   // Return the incoming value if it comes from the same BB as the phi node.
   if (P->getIncomingBlock(0) == ParentBB) {
     Rdx = P->getIncomingValue(0);
   } else if (P->getIncomingBlock(1) == ParentBB) {
     Rdx = P->getIncomingValue(1);
   }
 
-  if (Rdx)
+  if (Rdx && DominatedReduxValue(Rdx))
     return Rdx;
 
   // Otherwise, check whether we have a loop latch to look at.
   Loop *BBL = LI->getLoopFor(ParentBB);
   if (!BBL)
-    return Rdx;
+    return nullptr;
   BasicBlock *BBLatch = BBL->getLoopLatch();
   if (!BBLatch)
-    return Rdx;
+    return nullptr;
 
   // There is a loop latch, return the incoming value if it comes from
   // that. This reduction pattern occassionaly turns up.
   if (P->getIncomingBlock(0) == BBLatch) {
     Rdx = P->getIncomingValue(0);
   } else if (P->getIncomingBlock(1) == BBLatch) {
     Rdx = P->getIncomingValue(1);
   }
 
+  if (Rdx && DominatedReduxValue(Rdx))
     return Rdx;
+
+  return nullptr;
 }
 
 /// \brief Attempt to reduce a horizontal reduction.
 /// If it is legal to match a horizontal reduction feeding
 /// the phi node P with reduction operators BI, then check if it
 /// can be done.
 /// \returns true if a horizontal reduction was matched and reduced.
 /// \returns false if a horizontal reduction was not matched.
if (isa<DbgInfoIntrinsic>(it))
       continue;
 
     // Try to vectorize reductions that use PHINodes.
     if (PHINode *P = dyn_cast<PHINode>(it)) {
       // Check that the PHI is a reduction PHI.
       if (P->getNumIncomingValues() != 2)
         return Changed;
 
-      Value *Rdx = getReductionValue(P, BB, LI);
+      Value *Rdx = getReductionValue(DT, P, BB, LI);
 
       // Check if this is a Binary Operator.
       BinaryOperator *BI = dyn_cast_or_null<BinaryOperator>(Rdx);
       if (!BI)
         continue;
 
       // Try to match and vectorize a horizontal reduction.
       if (canMatchHorizontalReduction(P, BI, R, TTI)) {