[LoopUtils, LV] Fix PR27246 (first-order recurrences)

[mssimpso]

Summary

This patch ensures that when we detect first-order recurrences, we reject a phi node if its previous is also a phi node. During vectorization the initial and previous values of the recurrence are shuffled together to create the value for the current iteration. However, phi nodes are not widened like other instructions. This fixes PR27246.

[mcrosier]

LGTM with a minor nit.

lib/Transforms/Utils/LoopUtils.cpp

544

This looks like your combining the fix with a NFC (i.e., replacing the original check with isLoopInvariant()). I'd prefer this patch only include the isa<PHINode> check and you can make the NFC in a subsequent patch.

[mssimpso]

Thanks, Chad! I'll separate this into two patches.

lib/Transforms/Utils/LoopUtils.cpp

bool RecurrenceDescriptor::isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
 
   // Ensure the phi node's incoming blocks are the loop preheader and latch.
   if (Phi->getBasicBlockIndex(Preheader) < 0 ||
       Phi->getBasicBlockIndex(Latch) < 0)
     return false;
 
   // Get the previous value. The previous value comes from the latch edge while
   // the initial value comes form the preheader edge.
-  auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
-  if (!Previous || !TheLoop->contains(Previous))
+  auto *Previous = Phi->getIncomingValueForBlock(Latch);
+  if (TheLoop->isLoopInvariant(Previous) || isa<PHINode>(Previous))
     return false;
 
   // Ensure every user of the phi node is dominated by the previous value. The
   // dominance requirement ensures the loop vectorizer will not need to
   // vectorize the initial value prior to the first iteration of the loop.
   for (User *U : Phi->users())
     if (auto *I = dyn_cast<Instruction>(U))
-      if (!DT->dominates(Previous, I))
+      if (!DT->dominates(cast<Instruction>(Previous), I))
         return false;
 
   return true;
 }
 
 /// This function returns the identity element (or neutral element) for
 /// the operation K.
 Constant *RecurrenceDescriptor::getRecurrenceIdentity(RecurrenceKind K,

test/Transforms/LoopVectorize/AArch64/first-order-recurrence.ll

for.cond.for.end_crit_edge:
   store i32 %conv2, i32* %c, align 4
   store i32 %and.lcssa, i32* %b, align 4
   store i16 %sub, i16* %e, align 2
   br label %for.end
 
 for.end:
   ret void
 }
+
+; CHECK-LABEL: @PR27246
+;
+; int PR27246() {
+;   unsigned int e, n;
+;   for (int i = 1; i < 49; ++i) {
+;     for (int k = i; k > 1; --k)
+;       e = k;
+;     n = e;
+;   }
+;   return n;
+; }
+;
+; CHECK-NOT: vector.ph:
+;
+define i32 @PR27246() {
+entry:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:
+  %i.016 = phi i32 [ 1, %entry ], [ %inc, %for.cond.cleanup3 ]
+  %e.015 = phi i32 [ undef, %entry ], [ %e.1.lcssa, %for.cond.cleanup3 ]
+  br label %for.cond1
+
+for.cond.cleanup:
+  %e.1.lcssa.lcssa = phi i32 [ %e.1.lcssa, %for.cond.cleanup3 ]
+  ret i32 %e.1.lcssa.lcssa
+
+for.cond1:
+  %e.1 = phi i32 [ %k.0, %for.cond1 ], [ %e.015, %for.cond1.preheader ]
+  %k.0 = phi i32 [ %dec, %for.cond1 ], [ %i.016, %for.cond1.preheader ]
+  %cmp2 = icmp sgt i32 %k.0, 1
+  %dec = add nsw i32 %k.0, -1
+  br i1 %cmp2, label %for.cond1, label %for.cond.cleanup3
+
+for.cond.cleanup3:
+  %e.1.lcssa = phi i32 [ %e.1, %for.cond1 ]
+  %inc = add nuw nsw i32 %i.016, 1
+  %exitcond = icmp eq i32 %inc, 49
+  br i1 %exitcond, label %for.cond.cleanup, label %for.cond1.preheader
+}