[LV] Vectorize header phis that feed from if-convertable latch phis

[anna]

Summary

This patch teaches loop vectorizer to vectorize phi nodes that have the
following characteristics:

1. header phis that are not identified as induction/reduction/first order

recurrences.

2. feeds in from a phi in the latch block and that phi can be if-converted
3. unused outside the loop.

Condition #3 will be avoided in a follow on change.
This is to teach the vectorizer about general recurrences and cross iteration
dependencies.
The key point here is that if the header phi feeds from an if-convertable phi,
then the header phi can be vectorized. The 'resume' value extracted for this
header phi in the scalar post loop is the last element of the vectorized phi in
the latch block.

Please see added test cases. A current TODO item is we do not want to vectorize
'dead' loops, i.e. a read only loop whose values computed in the loop have no
outside users.

Please note: I will add more test cases, this is a proof of concept patch just
to make sure I've not missed some obvious legality constraint.

[anna]

lib/Transforms/Vectorize/LoopVectorize.cpp

3396

This is just a refactoring of the code from fixFirstOrderRecurrence. It is used by both fixFirstOrderRecurrence and fixCrossIterationPhiInHeader.

[anna]

clang formatted the change and added some comments. NFC wrt previous diff.

[anna]

fuzz testing this patch through our internal fuzzer shows all tests passed.

[efriedma]

Your patch miscompiles the following:

void f(int n, int *p, int *z) {
int x = 100;
#pragma clang loop vectorize(enable)
for (int i = 0; i < n; ++i) {
if (p[i] > 0) x *= p[i];
else x /= p[i];
z[i]=x;
}
}
typedef void fty(int,int*,int*);
fty*volatile ff=f;
int main() {
  int p[] = {1,-2,3,-4};
  int z[] = {1,2,3,4};
  ff(4, p, z);
  printf("%d %d %d %d\n", z[0], z[1], z[2], z[3]);
}

[anna]

In D50474#1194394, @efriedma wrote:

Your patch miscompiles the following:

void f(int n, int *p, int *z) {
int x = 100;
#pragma clang loop vectorize(enable)
for (int i = 0; i < n; ++i) {
if (p[i] > 0) x *= p[i];
else x /= p[i];
z[i]=x;
}
}
typedef void fty(int,int*,int*);
fty*volatile ff=f;
int main() {
  int p[] = {1,-2,3,-4};
  int z[] = {1,2,3,4};
  ff(4, p, z);
  printf("%d %d %d %d\n", z[0], z[1], z[2], z[3]);
}

yeah, that's right. The header phi is a predicated reduction and we'll miscompile with a splatted preheader value.
I think it would be okay if the iteration dependence distance > VF.
However, the case I'm interested in is a "predicated reduction". The header phi is just not recognized as a reduction.

[Ayal]

lib/Transforms/Utils/LoopUtils.cpp

673

Looks like one thing being asked here is: why bail out if isa<PHINode>(Previous)? @mssimpso answers that in r265983, in response to PR27246. There, Previous was a header PHINode, (specifically an Induction), which effectively means the original header PHI is a 2nd (or greater) order recurrence. It may be interesting to see if that case could be vectorized correctly.
In any case, the motivation for this patch involves Previous which isa PHINode, but not of the header block. Such Previous's get vectorized into blends, so presumably this may be safe and helpful:

   auto *Previous = dyn_cast<Instruction>(Phi->getIncomingValueForBlock(Latch));
-  if (!Previous || !TheLoop->contains(Previous) || isa<PHINode>(Previous) ||
+  if (!Previous || !TheLoop->contains(Previous) ||
+      (isa<PHINode>(Previous) &&
+       Previous->getParent() == TheLoop->getHeader()) ||
       SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.

Note however that for 1st order recurrence to work, Previous (including if it's a PHI of a non-header block) must dominate all users of the original header PHI. Or be made to dominate them by Sinking the users After Previous. In particular, Previous cannot be data-dependent on the original header PHI, which will close a dependence cycle.

In the tests below, %phiuseout2 which is the candidate Previous of %hdrphi1, also depends on it (e.g., via %tmp50), disqualifying it from being a 1st order recurrence. Every such dependence cycle must be broken, if possible, or rather expanded into a cycle of distance VF, as done for Inductions and Reductions, in order for vectorization to succeed. Efforts to handle more cyclic dependencies include D49168 and D22341. Not sure I follow how the tests below with their cyclic dependencies are expected to be vectorized, nor the "over vectorized" argument - perhaps related to D50480(?).

[anna]

lib/Transforms/Utils/LoopUtils.cpp

673

hi Ayal,
Thanks for the comments about the first order recurrence.

For the test below, as you mentioned, it is not a first order recurrence. However, I think of it as a "predicated reduction".
The computation I'm interested in vectorizing:

hdrphi1 = boolarr[i+c] == 1 ? intarr[i+c] + (hdrphi2 == 0 ? hdrphi1 : 0) : (!(hdrphi2 == 0) ? hdrphi1 : -1)

if boolarr[i+c] is 1 (and hdrphi2 is 0), then this computation reduces to a reduction:

hdrphi1 = intarr[i+c] +hdrphi1

if boolarr[i+c] != 1, then hdrphi1 is not dependent on previous iteration (it's either hdrphi1 itself or -1).
if boolarr[i+c] is 1 and hdrphi2 != 0, then
hdrphi1 = intarr[i+c]

Some forms of predicated reduction is already supported today (when tested on clang), such as:

if (a[i] > 0)
 x *= a[i];

I think it's because we have the identity vector for the else case? i.e. this becomes:

if (a[i] > 0)
 x *= a[i];
else
 x *= 1;

[anna]

lib/Transforms/Utils/LoopUtils.cpp

673

I have come to the conclusion that the case I have simply cannot be treated as a predicated reduction, because the else part of the predicate is not a reduction.
Specifically, cases such as these aren't vectorizable:

for (i = 0; i < n; ++i) {
    if (p[i] > 0) x += p[i];
    else x =0; <-- this bites us because it cannot be expressed as a reduction since the dependence distance cannot be widened to VF.
}

[Ayal]

lib/Transforms/Utils/LoopUtils.cpp

673

Agreed. If a conditional update can be folded into

x *= (a[i] > 0 ? a[i] : 1);

then we're good. See, e.g., D49168 as referenced earlier. But resetting the accumulator while reduction is in progress is indeed a bummer. Reductions are vectorized based on their ability to reassociate; which does not hold for floating-point computations (w/o fast-math), nor for such resets.

[anna]

We cannot vectorize predicated reductions where the else part of the predicate is a reset of the reduction val.

lib/Transforms/Utils/LoopUtils.cpp

673

yes, unfortunately, here we are resetting the accumulator.

include/llvm/Transforms/Utils/LoopUtils.h

private:
   // Instructions used for type-casts of the induction variable,
   // that are redundant when guarded with a runtime SCEV overflow check.
   SmallVector<Instruction *, 2> RedundantCasts;
 };
 
 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
                                    bool PreserveLCSSA);
 
+// These are general cross iteration phis in the header. They do not fit into
+// the reduction/induction/first order recurrence phis. We identify such phis
+// when their incoming value from the loop is also a phi node (coming from the
+// latch).
+bool isCrossIterationPhiInHeader(PHINode *Phi, Loop *TheLoop);
+
 /// Ensure that all exit blocks of the loop are dedicated exits.
 ///
 /// For any loop exit block with non-loop predecessors, we split the loop
 /// predecessors to use a dedicated loop exit block. We update the dominator
 /// tree and loop info if provided, and will preserve LCSSA if requested.
 bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
                              bool PreserveLCSSA);
 

include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

public:
   InductionList *getInductionVars() { return &Inductions; }
 
   /// Return the first-order recurrences found in the loop.
   RecurrenceSet *getFirstOrderRecurrences() { return &FirstOrderRecurrences; }
 
   /// Return the set of instructions to sink to handle first-order recurrences.
   DenseMap<Instruction *, Instruction *> &getSinkAfter() { return SinkAfter; }
 
+  RecurrenceSet *getCrossIterationPhisInHeader() {
+    return &CrossIterationPhisInHeader;
+  }
+
   /// Returns the widest induction type.
   Type *getWidestInductionType() { return WidestIndTy; }
 
   /// Returns True if V is a Phi node of an induction variable in this loop.
   bool isInductionPhi(const Value *V);
 
   /// Returns True if V is a cast that is part of an induction def-use chain,
   /// and had been proven to be redundant under a runtime guard (in other
   /// words, the cast has the same SCEV expression as the induction phi).
   bool isCastedInductionVariable(const Value *V);
 
   /// Returns True if V can be considered as an induction variable in this
   /// loop. V can be the induction phi, or some redundant cast in the def-use
   /// chain of the inducion phi.
   bool isInductionVariable(const Value *V);
 
   /// Returns True if PN is a reduction variable in this loop.
   bool isReductionVariable(PHINode *PN) { return Reductions.count(PN); }
 
   /// Returns True if Phi is a first-order recurrence in this loop.
   bool isFirstOrderRecurrence(const PHINode *Phi);
 
+  bool isCrossIterationPhiInHeader(const PHINode *PN) {
+    return CrossIterationPhisInHeader.count(PN);
+  }
+
   /// Return true if the block BB needs to be predicated in order for the loop
   /// to be vectorized.
   bool blockNeedsPredication(BasicBlock *BB);
 
   /// Check if this pointer is consecutive when vectorizing. This happens
   /// when the last index of the GEP is the induction variable, or that the
   /// pointer itself is an induction variable.
   /// This check allows us to vectorize A[idx] into a wide load/store.
private:
   /// variables, and that have been proven to be redundant (possibly under a
   /// runtime guard). These casts can be ignored when creating the vectorized
   /// loop body.
   SmallPtrSet<Instruction *, 4> InductionCastsToIgnore;
 
   /// Holds the phi nodes that are first-order recurrences.
   RecurrenceSet FirstOrderRecurrences;
 
+  /// These are header phis that are neither induction, reduction or first
+  /// order recurrences. However, they fit the general recurrence pattern with
+  /// incoming value from the loop belonging to an if-convertable phi node in
+  /// the latch.
+  RecurrenceSet CrossIterationPhisInHeader;
+
   /// Holds instructions that need to sink past other instructions to handle
   /// first-order recurrences.
   DenseMap<Instruction *, Instruction *> SinkAfter;
 
   /// Holds the widest induction type encountered.
   Type *WidestIndTy = nullptr;
 
   /// Allowed outside users. This holds the induction and reduction

lib/Transforms/Utils/LoopUtils.cpp

if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes, DB,
     LLVM_DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi
                       << "\n");
     return true;
   }
   // Not a reduction of known type.
   return false;
 }
 
-bool RecurrenceDescriptor::isFirstOrderRecurrence(
-    PHINode *Phi, Loop *TheLoop,
-    DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
-
+static bool isValidPhiForRecurrence(PHINode *Phi, Loop *TheLoop) {
   // Ensure the phi node is in the loop header and has two incoming values.
   if (Phi->getParent() != TheLoop->getHeader() ||
       Phi->getNumIncomingValues() != 2)
     return false;
 
   // Ensure the loop has a preheader and a single latch block. The loop
   // vectorizer will need the latch to set up the next iteration of the loop.
   auto *Preheader = TheLoop->getLoopPreheader();
   auto *Latch = TheLoop->getLoopLatch();
   if (!Preheader || !Latch)
     return false;
 
   // Ensure the phi node's incoming blocks are the loop preheader and latch.
   if (Phi->getBasicBlockIndex(Preheader) < 0 ||
       Phi->getBasicBlockIndex(Latch) < 0)
     return false;
+  return true;
+}
+
+bool llvm::isCrossIterationPhiInHeader(PHINode *Phi, Loop *TheLoop) {
+  if (!isValidPhiForRecurrence(Phi, TheLoop))
+    return false;
+
+  auto *Latch = TheLoop->getLoopLatch();
+
+  // 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<PHINode>(Phi->getIncomingValueForBlock(Latch));
+  if (!Previous || !TheLoop->contains(Previous))
+    return false;
+
+  // Now look at the properties of Previous.
+  // It should be if-convertable phi node - for now we only handle two element
+  // phi nodes.
+  if (Previous->getNumIncomingValues() != 2)
+    return false;
+
+  auto hasOutsideLoopUsers = [TheLoop](PHINode *P) {
+    // Check that all of the users of the loop are inside the BB.
+    for (User *U : P->users()) {
+      Instruction *UI = cast<Instruction>(U);
+      if (!TheLoop->contains(UI))
+        return true;
+    }
+    return false;
+  };
+
+  // For now, Previous and Phi should not have outside uses.
+  if (hasOutsideLoopUsers(Phi) || hasOutsideLoopUsers(Previous))
+    return false;
+
+  return true;
+}
+
+bool RecurrenceDescriptor::isFirstOrderRecurrence(
+    PHINode *Phi, Loop *TheLoop,
+    DenseMap<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
+
+  if (!isValidPhiForRecurrence(Phi, TheLoop))
+    return false;
+
+  auto *Latch = TheLoop->getLoopLatch();
 
   // 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) || isa<PHINode>(Previous) ||
       SinkAfter.count(Previous)) // Cannot rely on dominance due to motion.
     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.
   // TODO: Consider extending this sinking to handle other kinds of instructions
   // and expressions, beyond sinking a single cast past Previous.

lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

for (Instruction &I : *BB) {
 
         // As a last resort, coerce the PHI to a AddRec expression
         // and re-try classifying it a an induction PHI.
         if (InductionDescriptor::isInductionPHI(Phi, TheLoop, PSE, ID, true)) {
           addInductionPhi(Phi, ID, AllowedExit);
           continue;
         }
 
+        // If nothing worked, see if it's a phi feeding from another
+        // if-convertable phi in the latch.
+        if (llvm::isCrossIterationPhiInHeader(Phi, TheLoop)) {
+           CrossIterationPhisInHeader.insert(Phi);
+           continue;
+        }
+
         ORE->emit(createMissedAnalysis("NonReductionValueUsedOutsideLoop", Phi)
                   << "value that could not be identified as "
                      "reduction is used outside the loop");
         LLVM_DEBUG(dbgs() << "LV: Found an unidentified PHI." << *Phi << "\n");
         return false;
       } // end of PHI handling
 
       // We handle calls that:

lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
 
   /// Handle all cross-iteration phis in the header.
   void fixCrossIterationPHIs();
 
   /// Fix a first-order recurrence. This is the second phase of vectorizing
   /// this phi node.
   void fixFirstOrderRecurrence(PHINode *Phi);
 
+  /// Fix up the scalar post loop for recurrence loops. Phi is the recurrence
+  /// phi, ScalarInit and VectorInitForScalar are the value for the scalar
+  /// loop from the preheader and the vector loop respectively.
+  /// Previous represents the scalar value from the loop iteration that feeds
+  /// into Phi.
+  void fixScalarLoopAndOutsideUsesForRecurrence(PHINode &Phi,
+                                                Value *VectorInitForScalar,
+                                                Value *ScalarInit,
+                                                Value *Previous);
+
   /// Fix a reduction cross-iteration phi. This is the second phase of
   /// vectorizing this phi node.
   void fixReduction(PHINode *Phi);
 
+  /// Fix the general vectorizable phi in header case. These are general
+  /// recurrences that feed from an (if-convertable) phi node in the latch. This is the second phase
+  /// of vectorizing this phi node.
+  void fixCrossIterationPhiInHeader(PHINode *Phi);
+
   /// 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 InnerLoopVectorizer::fixCrossIterationPHIs() {
   // original loop is widened to a vector form so we can use them to construct
   // the incoming edges.
   for (PHINode &Phi : OrigLoop->getHeader()->phis()) {
     // Handle first-order recurrences and reductions that need to be fixed.
     if (Legal->isFirstOrderRecurrence(&Phi))
       fixFirstOrderRecurrence(&Phi);
     else if (Legal->isReductionVariable(&Phi))
       fixReduction(&Phi);
+    else if (Legal->isCrossIterationPhiInHeader(&Phi))
+      fixCrossIterationPhiInHeader(&Phi);
+  }
+}
+
+void InnerLoopVectorizer::fixScalarLoopAndOutsideUsesForRecurrence(
+    PHINode &Phi, Value *VectorInitForScalar, Value *ScalarInit,
+    Value *Previous) {
+  // Extract the last vector element in the middle block. This will be the
+  // initial value for the recurrence when jumping to the scalar loop.
+  auto *ExtractForScalar = VectorInitForScalar;
+  if (VF > 1) {
+    Builder.SetInsertPoint(LoopMiddleBlock->getTerminator());
+    ExtractForScalar = Builder.CreateExtractElement(
+        ExtractForScalar, Builder.getInt32(VF - 1), "vector.recur.extract");
+  }
+  // Extract the second last element in the middle block if the
+  // Phi is used outside the loop. We need to extract the phi itself
+  // and not the last element (the phi update in the current iteration). This
+  // will be the value when jumping to the exit block from the LoopMiddleBlock,
+  // when the scalar loop is not run at all.
+  Value *ExtractForPhiUsedOutsideLoop = nullptr;
+  if (VF > 1)
+    ExtractForPhiUsedOutsideLoop = Builder.CreateExtractElement(
+        VectorInitForScalar, Builder.getInt32(VF - 2),
+        "vector.recur.extract.for.phi");
+  // When loop is unrolled without vectorizing, initialize
+  // ExtractForPhiUsedOutsideLoop with the value just prior to unrolled value of
+  // `Incoming`. This is analogous to the vectorized case above: extracting the
+  // second last element when VF > 1.
+  else if (UF > 1)
+    ExtractForPhiUsedOutsideLoop = getOrCreateVectorValue(Previous, UF - 2);
+
+  // Fix the initial value of the original recurrence in the scalar loop.
+  Builder.SetInsertPoint(&*LoopScalarPreHeader->begin());
+  auto *Start = Builder.CreatePHI(Phi.getType(), 2, "scalar.recur.init");
+  for (auto *BB : predecessors(LoopScalarPreHeader)) {
+    auto *Incoming = BB == LoopMiddleBlock ? ExtractForScalar : ScalarInit;
+    Start->addIncoming(Incoming, BB);
+  }
+
+  Phi.setIncomingValue(Phi.getBasicBlockIndex(LoopScalarPreHeader), Start);
+  Phi.setName("scalar.recur");
+
+  // Finally, fix users of the recurrence outside the loop. The users will need
+  // either the last value of the scalar recurrence or the last value of the
+  // vector recurrence we extracted in the middle block. Since the loop is in
+  // LCSSA form, we just need to find all the phi nodes for the original scalar
+  // recurrence in the exit block, and then add an edge for the middle block.
+  for (PHINode &LCSSAPhi : LoopExitBlock->phis()) {
+    if (LCSSAPhi.getIncomingValue(0) == &Phi) {
+      LCSSAPhi.addIncoming(ExtractForPhiUsedOutsideLoop, LoopMiddleBlock);
+    }
+  }
+}
+
+void InnerLoopVectorizer::fixCrossIterationPhiInHeader(PHINode *Phi) {
+
+  auto *Preheader = OrigLoop->getLoopPreheader();
+  auto *Latch = OrigLoop->getLoopLatch();
+
+  // Get the initial and previous values of the scalar recurrence.
+  auto *ScalarInit = Phi->getIncomingValueForBlock(Preheader);
+  auto *Previous = Phi->getIncomingValueForBlock(Latch);
+
+  assert(isa<PHINode>(Previous) && "value from latch should be a phi!");
+  // Create a vector from the initial value.
+  auto *VectorInit = ScalarInit;
+  if (VF > 1) {
+    Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
+    VectorInit = Builder.CreateInsertElement(
+        UndefValue::get(VectorType::get(VectorInit->getType(), VF)), VectorInit,
+        Builder.getInt32(VF - 1), "vector.recur.init");
+  }
+
+  // We constructed a temporary phi node in the first phase of vectorization.
+  // This phi node will eventually be deleted.
+  Builder.SetInsertPoint(
+      cast<Instruction>(VectorLoopValueMap.getVectorValue(Phi, 0)));
+
+  // Create a phi node for the new recurrence. The current value will either be
+  // the initial value inserted into a vector or loop-varying vector value.
+  auto *VecPhi = Builder.CreatePHI(VectorInit->getType(), 2, "vector.recur");
+  VecPhi->addIncoming(VectorInit, LoopVectorPreHeader);
+
+  // Get the vectorized previous value of the last part UF - 1. It appears last
+  // among all unrolled iterations, due to the order of their construction.
+  Value *PreviousLastPart = getOrCreateVectorValue(Previous, UF - 1);
+  VecPhi->addIncoming(PreviousLastPart,
+                      LI->getLoopFor(LoopVectorBody)->getLoopLatch());
+
+  // The vector from which to take the initial value for the current iteration
+  // (actual or unrolled). Initially, this is the vector phi node.
+  Value *Incoming = VecPhi;
+
+  // Update the vector parts.
+  for (unsigned Part = 0; Part < UF; ++Part) {
+    Value *PreviousPart = getOrCreateVectorValue(Previous, Part);
+    Value *PhiPart = VectorLoopValueMap.getVectorValue(Phi, Part);
+    PhiPart->replaceAllUsesWith(Incoming);
+    cast<Instruction>(PhiPart)->eraseFromParent();
+    VectorLoopValueMap.resetVectorValue(Phi, Part, PreviousPart);
+    Incoming = PreviousPart;
   }
+
+  fixScalarLoopAndOutsideUsesForRecurrence(*Phi, Incoming, ScalarInit,
+                                           Previous);
+  // assert this vector phi has no uses outside the loop.
+#ifdef NDEBUG
+  for (PHINode &LCSSAPhi : LoopExitBlock->phis())
+    assert((LCSSAPhi.getIncomingValue(0) != Phi &&
+            LCSSAPhi.getIncomingValue(0) != Previous) &&
+           "no user expected outside loop!");
+#endif
 }
 
 void InnerLoopVectorizer::fixFirstOrderRecurrence(PHINode *Phi) {
   // This is the second phase of vectorizing first-order recurrences. An
   // overview of the transformation is described below. Suppose we have the
   // following loop.
   //
   //   for (int i = 0; i < n; ++i)
for (unsigned Part = 0; Part < UF; ++Part) {
     cast<Instruction>(PhiPart)->eraseFromParent();
     VectorLoopValueMap.resetVectorValue(Phi, Part, Shuffle);
     Incoming = PreviousPart;
   }
 
   // Fix the latch value of the new recurrence in the vector loop.
   VecPhi->addIncoming(Incoming, LI->getLoopFor(LoopVectorBody)->getLoopLatch());
 
-  // Extract the last vector element in the middle block. This will be the
-  // initial value for the recurrence when jumping to the scalar loop.
-  auto *ExtractForScalar = Incoming;
-  if (VF > 1) {
-    Builder.SetInsertPoint(LoopMiddleBlock->getTerminator());
-    ExtractForScalar = Builder.CreateExtractElement(
-        ExtractForScalar, Builder.getInt32(VF - 1), "vector.recur.extract");
-  }
-  // Extract the second last element in the middle block if the
-  // Phi is used outside the loop. We need to extract the phi itself
-  // and not the last element (the phi update in the current iteration). This
-  // will be the value when jumping to the exit block from the LoopMiddleBlock,
-  // when the scalar loop is not run at all.
-  Value *ExtractForPhiUsedOutsideLoop = nullptr;
-  if (VF > 1)
-    ExtractForPhiUsedOutsideLoop = Builder.CreateExtractElement(
-        Incoming, Builder.getInt32(VF - 2), "vector.recur.extract.for.phi");
-  // When loop is unrolled without vectorizing, initialize
-  // ExtractForPhiUsedOutsideLoop with the value just prior to unrolled value of
-  // `Incoming`. This is analogous to the vectorized case above: extracting the
-  // second last element when VF > 1.
-  else if (UF > 1)
-    ExtractForPhiUsedOutsideLoop = getOrCreateVectorValue(Previous, UF - 2);
-
-  // Fix the initial value of the original recurrence in the scalar loop.
-  Builder.SetInsertPoint(&*LoopScalarPreHeader->begin());
-  auto *Start = Builder.CreatePHI(Phi->getType(), 2, "scalar.recur.init");
-  for (auto *BB : predecessors(LoopScalarPreHeader)) {
-    auto *Incoming = BB == LoopMiddleBlock ? ExtractForScalar : ScalarInit;
-    Start->addIncoming(Incoming, BB);
-  }
-
-  Phi->setIncomingValue(Phi->getBasicBlockIndex(LoopScalarPreHeader), Start);
-  Phi->setName("scalar.recur");
-
-  // Finally, fix users of the recurrence outside the loop. The users will need
-  // either the last value of the scalar recurrence or the last value of the
-  // vector recurrence we extracted in the middle block. Since the loop is in
-  // LCSSA form, we just need to find all the phi nodes for the original scalar
-  // recurrence in the exit block, and then add an edge for the middle block.
-  for (PHINode &LCSSAPhi : LoopExitBlock->phis()) {
-    if (LCSSAPhi.getIncomingValue(0) == Phi) {
-      LCSSAPhi.addIncoming(ExtractForPhiUsedOutsideLoop, LoopMiddleBlock);
-    }
-  }
+  fixScalarLoopAndOutsideUsesForRecurrence(*Phi, Incoming, ScalarInit,
+                                           Previous);
 }
 
 void InnerLoopVectorizer::fixReduction(PHINode *Phi) {
   Constant *Zero = Builder.getInt32(0);
 
   // Get it's reduction variable descriptor.
   assert(Legal->isReductionVariable(Phi) &&
          "Unable to find the reduction variable");
void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN, unsigned UF,
   assert(PN->getParent() == OrigLoop->getHeader() &&
          "Non-header phis should have been handled elsewhere");
 
   PHINode *P = cast<PHINode>(PN);
   // In order to support recurrences we need to be able to vectorize Phi nodes.
   // Phi nodes have cycles, so we need to vectorize them in two stages. This is
   // stage #1: We create a new vector PHI node with no incoming edges. We'll use
   // this value when we vectorize all of the instructions that use the PHI.
-  if (Legal->isReductionVariable(P) || Legal->isFirstOrderRecurrence(P)) {
+  if (Legal->isReductionVariable(P) || Legal->isFirstOrderRecurrence(P) ||
+      Legal->isCrossIterationPhiInHeader(P)) {
     for (unsigned Part = 0; Part < UF; ++Part) {
       // This is phase one of vectorizing PHIs.
       Type *VecTy =
           (VF == 1) ? PN->getType() : VectorType::get(PN->getType(), VF);
       Value *EntryPart = PHINode::Create(
           VecTy, 2, "vec.phi", &*LoopVectorBody->getFirstInsertionPt());
       VectorLoopValueMap.setVectorValue(P, Part, EntryPart);
     }

test/Transforms/LoopVectorize/vectorize-general-recurrence.ll

+; RUN: opt < %s  -loop-vectorize -force-vector-width=4 -dce -instcombine -S | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+
+declare i8 @foo()
+declare i64 @bar()
+
+; general recurrence predicated with selects.
+; hdrphi1 = boolarr[i+c] == 1 ? boolarr[i+c] + (hdrphi2 == 0 ? hdrphi1 : 0) : (!(hdrphi2 == 0) ? hdrphi1 : -1)
+define i64 @recurrence_with_select(i64 %N, i64 %c, i8 * %boolarr) {
+;CHECK-LABEL: @recurrence_with_select(
+; CHECK-LABEL:  vector.body:
+; CHECK:          phi <4 x i64>
+; CHECK:          phi <4 x i8>
+; CHECK:          load <4 x i8>
+; CHECK-LABEL:  middle.block:
+; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <4 x i64>
+; CHECK:          [[E2:%[a-zA-Z0-9.]+]] = extractelement <4 x i8>
+; CHECK-LABEL:  scalar.ph:
+; CHECK:          [[SRI1:%[a-zA-Z0-9.]+]] = phi i8 [ [[E2]], %middle.block ], [ %tmp, %prehdr ]
+; CHECK:          [[SRI2:%[a-zA-Z0-9.]+]]  = phi i64 [ [[E1]], %middle.block ], [ %hdrphi1.ph.init, %prehdr ]
+; CHECK-LABEL:  hdr:
+; CHECK:         phi i64 [ %phiuseout2, %latch ], [ [[SRI2]], %scalar.ph ]
+; CHECK:         phi i8 [ %phiuseout1, %latch ], [ [[SRI1]], %scalar.ph ]
+
+prehdr:
+  %tmp = call i8 @foo()
+  %hdrphi1.ph.init = call i64 @bar()
+  br label %hdr
+
+hdr:                                             ; preds = %latch, %prehdr
+  %hdrphi1 = phi i64 [ %phiuseout2, %latch ], [ %hdrphi1.ph.init, %prehdr ]
+  %hdrphi2 = phi i8 [ %phiuseout1, %latch ], [ %tmp, %prehdr ]
+  %iv = phi i64 [ %iv.next, %latch ], [ 0, %prehdr ]
+  %iv.derived = add nuw nsw i64 %iv, %c
+  %tmp17 = getelementptr inbounds i8, i8 * %boolarr, i64 %iv.derived
+  %boolarrload = load i8, i8 * %tmp17, align 1
+  %tmp34 = icmp eq i8 %hdrphi2, 0
+  %tmp19 = icmp eq i8 %boolarrload, 1
+  br i1 %tmp19, label %bb36, label %bb46
+
+bb36:                                             ; preds = %bb30
+  %tmp41 = select i1 %tmp34, i64 %hdrphi1, i64 0
+  %tmp44 = sext i8 %boolarrload to i64
+  %tmp45 = add i64 %tmp41, %tmp44
+  br label %latch
+
+bb46:                                             ; preds = %bb30, %bb28
+  %tmp48 = xor i1 %tmp34, true
+  %tmp49 = zext i1 %tmp48 to i8
+  %tmp50 = select i1 %tmp48, i64 %hdrphi1, i64 -1
+  br label %latch
+
+latch:                                             ; preds = %bb46, %bb36
+  %phiuseout1 = phi i8 [ 0, %bb36 ], [ %tmp49, %bb46 ]
+  %phiuseout2 = phi i64 [ %tmp45, %bb36 ], [ %tmp50, %bb46 ]
+  %iv.next = add nuw nsw i64 %iv, 1
+  %tmp55 = icmp ult i64 %iv.next, %N
+  br i1 %tmp55, label %hdr, label %bb56
+
+bb56:                                             ; preds = %latch
+  %phi.iv.lcssa = phi i64 [ %iv.next, %latch ]
+  ret i64 %phi.iv.lcssa
+}
+
+; predicated stores in the loop
+define void @recurrence_with_select_and_store(i64 %N, i64 %c, i8 * %boolarr, i64 * %array) {
+; CHECK-LABEL: vector.memcheck:
+; CHECK:         br i1 %found.conflict, label %scalar.ph, label %vector.ph
+
+; CHECK-LABEL: vector.body:
+; CHECK:         phi <4 x i64>
+; CHECK:         phi <4 x i8>
+
+; CHECK-LABEL:  middle.block:
+; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <4 x i64>
+; CHECK:          [[E2:%[a-zA-Z0-9.]+]] = extractelement <4 x i8>
+
+; CHECK-LABEL:  scalar.ph:
+; CHECK:          [[SRI1:%[a-zA-Z0-9.]+]] = phi i8 [ [[E2]], %middle.block ], [ %tmp, %vector.memcheck ], [ %tmp, %prehdr ]
+; CHECK:          [[SRI2:%[a-zA-Z0-9.]+]] = phi i64 [ [[E1]], %middle.block ], [ %hdrphi1.ph.init, %vector.memcheck ], [ %hdrphi1.ph.init, %prehdr ]
+prehdr:
+  %tmp = call i8 @foo()
+  %hdrphi1.ph.init = call i64 @bar()
+  br label %hdr
+
+hdr:                                             ; preds = %latch, %prehdr
+  %hdrphi1 = phi i64 [ %phiuseout2, %latch ], [ %hdrphi1.ph.init, %prehdr ]
+  %hdrphi2 = phi i8 [ %phiuseout1, %latch ], [ %tmp, %prehdr ]
+  %iv = phi i64 [ %iv.next, %latch ], [ 0, %prehdr ]
+  %iv.derived = add nuw nsw i64 %iv, %c
+  %tmp17 = getelementptr inbounds i8, i8 * %boolarr, i64 %iv.derived
+  %boolarrload = load i8, i8 * %tmp17, align 1
+  %tmp34 = icmp eq i8 %hdrphi2, 0
+  %tmp19 = icmp eq i8 %boolarrload, 1
+  br i1 %tmp19, label %bb36, label %bb46
+
+bb36:                                             ; preds = %bb30
+  %tmp41 = select i1 %tmp34, i64 %hdrphi1, i64 0
+  %tmp44 = sext i8 %boolarrload to i64
+  %tmp45 = add i64 %tmp41, %tmp44
+  br label %latch
+
+bb46:                                             ; preds = %bb30, %bb28
+  %tmp48 = xor i1 %tmp34, true
+  %tmp49 = zext i1 %tmp48 to i8
+  %tmp50 = select i1 %tmp48, i64 %hdrphi1, i64 -1
+  %addr = getelementptr inbounds i64, i64 * %array, i64 %iv.derived
+  store i64 %tmp50, i64* %addr, align 1
+  br label %latch
+
+latch:                                             ; preds = %bb46, %bb36
+  %phiuseout1 = phi i8 [ 0, %bb36 ], [ %tmp49, %bb46 ]
+  %phiuseout2 = phi i64 [ %tmp45, %bb36 ], [ %tmp50, %bb46 ]
+  %iv.next = add nuw nsw i64 %iv, 1
+  %tmp55 = icmp ult i64 %iv.next, %N
+  br i1 %tmp55, label %hdr, label %bb56
+
+bb56:                                             ; preds = %latch
+  ret void
+}