[LV] Support vectorizing 'select index of minimum element' idiom. (WIP)

[fhahn]

Rebase and fix crash with VF=1 IC>1 (test added in 40621ff4b8a6214924)

[ABataev]

llvm/include/llvm/Analysis/IVDescriptors.h

130

Pass by reference?

llvm/lib/Analysis/IVDescriptors.cpp

829

Better to name it something like get..., since it returns instruction?

837–839

Just return Phi->getIncomingValueForBlock(TheLoop->getLoopLatch()) == UMinU;

855

get?

877–888

auto *P0 = dyn_cast<PHINode>(CmpOp0);
auto *P1 = dyn_cast<PHINode>(CmpOp1);
auto *P = P0 ? P0 : P1;
if (!P)
  return nullptr;
if ((UMin = isMinIdxReductionMinVal(P, TheLoop, SE))) {
   MinPhi = P;
   CurVal = P == P0 ? CmpOp1 : CmpOp0;
}

1023

The condition is same as in previous if. Is this ok?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3923

Remove the new line

3958–3959

State.Plan?

3969–3970

break?

8557

Delete new line

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

577–579

No need for braces

llvm/test/Transforms/LoopVectorize/select-min-index.ll

7

Generate the checks by the script?

[Mel-Chen]

llvm/include/llvm/Analysis/IVDescriptors.h

55–57

Interesting. I have different point. In my opinion, we should be able to reuse min/max recurrence. This prevents adding Select[Min|Max]Idx for each kind of min/max. I will share my current implementation later.

130

I use pointer too. This is because function isReductionPHI may not pass argument SE.

llvm/lib/Analysis/IVDescriptors.cpp

906–912

Canonical induction variable? It seems that there is a existing function that can be called directly, but I forgot the function name...

1194–1195

I also encountered the same problem here. I think MMI should base on full SelectCmp support. Using -1 may cause problems with unsigned index. But full support for SelectCmp is another long long story.

llvm/test/Transforms/LoopVectorize/select-min-index.ll

25–27

Your test case is single-exit. This is TODO for me. I will add a case that returns both umin and index.

[Mel-Chen]

https://reviews.llvm.org/D143465
Our views are a bit different, so I share our implementation with you. At present, the comments and commit log are not perfect, but I will make up.

[fhahn]

Abandoning since there are more recent patches making great progress in that direction and I never had time to wrap this up

llvm/include/llvm/Analysis/IVDescriptors.h

 class Loop;
 class PredicatedScalarEvolution;
 class ScalarEvolution;
 class SCEV;
 class StoreInst;
 
 /// These are the kinds of recurrences that we support.
 enum class RecurKind {
-  None,       ///< Not a recurrence.
-  Add,        ///< Sum of integers.
-  Mul,        ///< Product of integers.
-  Or,         ///< Bitwise or logical OR of integers.
-  And,        ///< Bitwise or logical AND of integers.
-  Xor,        ///< Bitwise or logical XOR of integers.
-  SMin,       ///< Signed integer min implemented in terms of select(cmp()).
-  SMax,       ///< Signed integer max implemented in terms of select(cmp()).
-  UMin,       ///< Unisgned integer min implemented in terms of select(cmp()).
-  UMax,       ///< Unsigned integer max implemented in terms of select(cmp()).
-  FAdd,       ///< Sum of floats.
-  FMul,       ///< Product of floats.
-  FMin,       ///< FP min implemented in terms of select(cmp()).
-  FMax,       ///< FP max implemented in terms of select(cmp()).
-  FMulAdd,    ///< Fused multiply-add of floats (a * b + c).
-  SelectICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is loop
+  None,         ///< Not a recurrence.
+  Add,          ///< Sum of integers.
+  Mul,          ///< Product of integers.
+  Or,           ///< Bitwise or logical OR of integers.
+  And,          ///< Bitwise or logical AND of integers.
+  Xor,          ///< Bitwise or logical XOR of integers.
+  SMin,         ///< Signed integer min implemented in terms of select(cmp()).
+  SMax,         ///< Signed integer max implemented in terms of select(cmp()).
+  UMin,         ///< Unisgned integer min implemented in terms of select(cmp()).
+  UMax,         ///< Unsigned integer max implemented in terms of select(cmp()).
+  FAdd,         ///< Sum of floats.
+  FMul,         ///< Product of floats.
+  FMin,         ///< FP min implemented in terms of select(cmp()).
+  FMax,         ///< FP max implemented in terms of select(cmp()).
+  FMulAdd,      ///< Fused multiply-add of floats (a * b + c).
+  SelectICmp,   ///< Integer select(icmp(),x,y) where one of (x,y) is loop
                 ///< invariant
-  SelectFCmp  ///< Integer select(fcmp(),x,y) where one of (x,y) is loop
-              ///< invariant
+  SelectFCmp,   ///< Integer select(fcmp(),x,y) where one of (x,y) is loop
+                ///<
+  SelectMinIdx, ///< Select of the index with minimal value, needs to be
+                ///< combined with SelectMinIdxMinVal
+  SelectMinIdxMinVal,
+
 };
 
 /// The RecurrenceDescriptor is used to identify recurrences variables in a
 /// loop. Reduction is a special case of recurrence that has uses of the
 /// recurrence variable outside the loop. The method isReductionPHI identifies
 /// reductions that are basic recurrences.
 ///
 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
public:
   /// Returns a struct describing if the instruction 'I' can be a recurrence
   /// variable of type 'Kind' for a Loop \p L and reduction PHI \p Phi.
   /// If the recurrence is a min/max pattern of select(icmp()) this function
   /// advances the instruction pointer 'I' from the compare instruction to the
   /// select instruction and stores this pointer in 'PatternLastInst' member of
   /// the returned struct.
   static InstDesc isRecurrenceInstr(Loop *L, PHINode *Phi, Instruction *I,
                                     RecurKind Kind, InstDesc &Prev,
-                                    FastMathFlags FuncFMF);
+                                    FastMathFlags FuncFMF, ScalarEvolution *SE);
 
   /// Returns true if instruction I has multiple uses in Insts
   static bool hasMultipleUsesOf(Instruction *I,
                                 SmallPtrSetImpl<Instruction *> &Insts,
                                 unsigned MaxNumUses);
 
   /// Returns true if all uses of the instruction I is within the Set.
   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
public:
   static bool isIntegerRecurrenceKind(RecurKind Kind);
 
   /// Returns true if the recurrence kind is a floating point kind.
   static bool isFloatingPointRecurrenceKind(RecurKind Kind);
 
   /// Returns true if the recurrence kind is an integer min/max kind.
   static bool isIntMinMaxRecurrenceKind(RecurKind Kind) {
     return Kind == RecurKind::UMin || Kind == RecurKind::UMax ||
-           Kind == RecurKind::SMin || Kind == RecurKind::SMax;
+           Kind == RecurKind::SMin || Kind == RecurKind::SMax ||
+           Kind == RecurKind::SelectMinIdx;
   }
 
   /// Returns true if the recurrence kind is a floating-point min/max kind.
   static bool isFPMinMaxRecurrenceKind(RecurKind Kind) {
     return Kind == RecurKind::FMin || Kind == RecurKind::FMax;
   }
 
   /// Returns true if the recurrence kind is any min/max kind.

llvm/lib/Analysis/IVDescriptors.cpp

if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
         !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0))))
       return false;
 
     // Any reduction instruction must be of one of the allowed kinds. We ignore
     // the starting value (the Phi or an AND instruction if the Phi has been
     // type-promoted).
     if (Cur != Start) {
       ReduxDesc =
-          isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF);
+          isRecurrenceInstr(TheLoop, Phi, Cur, Kind, ReduxDesc, FuncFMF, SE);
       ExactFPMathInst = ExactFPMathInst == nullptr
                             ? ReduxDesc.getExactFPMathInst()
                             : ExactFPMathInst;
       if (!ReduxDesc.isRecurrence())
         return false;
       // FIXME: FMF is allowed on phi, but propagation is not handled correctly.
       if (isa<FPMathOperator>(ReduxDesc.getPatternInst()) && !IsAPhi) {
         FastMathFlags CurFMF = ReduxDesc.getPatternInst()->getFastMathFlags();
if ((m_FAdd(m_Value(Op1), m_Value(Op2)).match(I1)  ||
     return InstDesc(Kind == RecurKind::FAdd, SI);
 
   if (m_FMul(m_Value(Op1), m_Value(Op2)).match(I1) && (I1->isFast()))
     return InstDesc(Kind == RecurKind::FMul, SI);
 
   return InstDesc(false, I);
 }
 
-RecurrenceDescriptor::InstDesc
-RecurrenceDescriptor::isRecurrenceInstr(Loop *L, PHINode *OrigPhi,
-                                        Instruction *I, RecurKind Kind,
-                                        InstDesc &Prev, FastMathFlags FuncFMF) {
+RecurrenceDescriptor::InstDesc RecurrenceDescriptor::isRecurrenceInstr(
+    Loop *L, PHINode *OrigPhi, Instruction *I, RecurKind Kind, InstDesc &Prev,
+    FastMathFlags FuncFMF, ScalarEvolution *SE) {
   assert(Prev.getRecKind() == RecurKind::None || Prev.getRecKind() == Kind);
   switch (I->getOpcode()) {
   default:
     return InstDesc(false, I);
   case Instruction::PHI:
     return InstDesc(I, Prev.getRecKind(), Prev.getExactFPMathInst());
   case Instruction::Sub:
   case Instruction::Add:
if (Insts.count(dyn_cast<Instruction>(U)))
       ++NumUses;
     if (NumUses > MaxNumUses)
       return true;
   }
 
   return false;
 }
 
+/// Check if \p Phi is a phi node selecting the index of a minimum value in the
+/// loop. It requires a second phi node that selects a minimum value in the
+/// loop. \p Phi must select the current IV, if the corresponding value of the
+/// current iteration is less than the current minimum value and \p Phi
+/// otherwise.
+static Instruction *isMinIdxReductionMinVal(PHINode *Phi, Loop *TheLoop,
+                                            ScalarEvolution &SE) {
+  auto IsUMin = [Phi, TheLoop](Value *UMinU) -> bool {
+    if (!match(UMinU,
+               m_Intrinsic<Intrinsic::umin>(m_Specific(Phi), m_Value())) &&
+        !match(UMinU, m_Intrinsic<Intrinsic::umin>(m_Value(), m_Specific(Phi))))
+      return false;
+
+    if (Phi->getIncomingValueForBlock(TheLoop->getLoopLatch()) != UMinU)
+      return false;
+    return true;
+  };
+
+  if (!Phi->hasNUses(2))
+    return nullptr;
+
+  Value *U1 = *Phi->user_begin();
+  Value *U2 = *std::next(Phi->user_begin());
+  if (IsUMin(U1))
+    return cast<Instruction>(U1);
+
+  if (IsUMin(U2))
+    return cast<Instruction>(U2);
+  return nullptr;
+}
+
+static Instruction *isMinIdxReductionMinIdx(PHINode *IdxPhi, Loop *TheLoop,
+                                            ScalarEvolution &SE) {
+  if (!IdxPhi->hasNUses(1))
+    return nullptr;
+
+  auto *IdxSel = dyn_cast<SelectInst>(*IdxPhi->user_begin());
+  if (!IdxSel)
+    return nullptr;
+
+  if (!IdxSel->getType()->isIntegerTy())
+    return nullptr;
+
+  auto *CI = dyn_cast<CmpInst>(IdxSel->getOperand(0));
+  if (!CI)
+    return nullptr;
+
+  Value *CmpOp0 = CI->getOperand(0);
+  Value *CmpOp1 = CI->getOperand(1);
+
+  PHINode *MinPhi = nullptr;
+  Value *CurVal = nullptr;
+  Value *UMin = nullptr;
+  if (auto *P = dyn_cast<PHINode>(CmpOp0)) {
+    if ((UMin = isMinIdxReductionMinVal(P, TheLoop, SE))) {
+      MinPhi = P;
+      CurVal = CmpOp1;
+    }
+  } else if (auto *P = dyn_cast<PHINode>(CmpOp1)) {
+    if ((UMin = isMinIdxReductionMinVal(P, TheLoop, SE))) {
+      MinPhi = P;
+      CurVal = CmpOp0;
+    }
+  } else
+    return nullptr;
+
+  if (!UMin || (!match(UMin, m_Intrinsic<Intrinsic::umin>(
+                                 m_Specific(MinPhi), m_Specific(CurVal))) &&
+                !match(UMin, m_Intrinsic<Intrinsic::umin>(m_Specific(CurVal),
+                                                          m_Specific(MinPhi)))))
+    return nullptr;
+
+  if (!((CI->getPredicate() == CmpInst::ICMP_UGT &&
+         CI->getOperand(0) == MinPhi) ||
+        (CI->getPredicate() == CmpInst::ICMP_ULT &&
+         CI->getOperand(1) == MinPhi)) ||
+      !CI->hasOneUse())
+    return nullptr;
+
+  Value *U = IdxSel->getOperand(1);
+  if (auto *T = dyn_cast<TruncInst>(U))
+    U = T->getOperand(0);
+  InductionDescriptor ID;
+  if (!isa<PHINode>(U) ||
+      !InductionDescriptor::isInductionPHI(cast<PHINode>(U), TheLoop, &SE, ID))
+    return nullptr;
+
+  if (!ID.getStep()->isOne() || ID.getInductionOpcode() != Instruction::Add)
+    return nullptr;
+
+  return IdxSel;
+}
+
 bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
                                           RecurrenceDescriptor &RedDes,
                                           DemandedBits *DB, AssumptionCache *AC,
                                           DominatorTree *DT,
                                           ScalarEvolution *SE) {
   BasicBlock *Header = TheLoop->getHeader();
   Function &F = *Header->getParent();
   FastMathFlags FMF;
LLVM_DEBUG(dbgs() << "Found a float conditional select reduction PHI."
                       << " PHI." << *Phi << "\n");
     return true;
   }
   if (AddReductionVar(Phi, RecurKind::FMulAdd, TheLoop, FMF, RedDes, DB, AC, DT,
                       SE)) {
     LLVM_DEBUG(dbgs() << "Found an FMulAdd reduction PHI." << *Phi << "\n");
     return true;
   }
+
+  if (Instruction *ExitI = isMinIdxReductionMinIdx(Phi, TheLoop, *SE)) {
+    FastMathFlags FMF;
+    SmallPtrSet<llvm::Instruction *, 2> Foo;
+    RecurrenceDescriptor RD(
+        Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()), ExitI,
+        nullptr, RecurKind::SelectMinIdx, FMF, nullptr, Phi->getType(), false,
+        false, Foo, -1U);
+    RedDes = RD;
+    return true;
+  }
+  if (Instruction *ExitI = isMinIdxReductionMinVal(Phi, TheLoop, *SE)) {
+    FastMathFlags FMF;
+    SmallPtrSet<llvm::Instruction *, 2> Foo;
+    RecurrenceDescriptor RD(
+        Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()), ExitI,
+        nullptr, RecurKind::SelectMinIdxMinVal, FMF, nullptr, Phi->getType(),
+        false, false, Foo, -1U);
+    RedDes = RD;
+    return true;
+  }
+
   // Not a reduction of known type.
   return false;
 }
 
 bool RecurrenceDescriptor::isFirstOrderRecurrence(
     PHINode *Phi, Loop *TheLoop,
     MapVector<Instruction *, Instruction *> &SinkAfter, DominatorTree *DT) {
 
case RecurKind::FAdd:
     // use -0.0. However, this will currently result in mixed vectors of 0.0/-0.0.
     // Instead, we should ensure that 1) the FMF from FAdd are propagated to the PHI
     // nodes where possible, and 2) PHIs with the nsz flag + -0.0 use 0.0. This would
     // mean we can then remove the check for noSignedZeros() below (see D98963).
     if (FMF.noSignedZeros())
       return ConstantFP::get(Tp, 0.0L);
     return ConstantFP::get(Tp, -0.0L);
   case RecurKind::UMin:
+  case RecurKind::SelectMinIdxMinVal:
     return ConstantInt::get(Tp, -1);
+  case RecurKind::SelectMinIdx:
+    llvm_unreachable("should not be called");
   case RecurKind::UMax:
     return ConstantInt::get(Tp, 0);
   case RecurKind::SMin:
     return ConstantInt::get(Tp,
                             APInt::getSignedMaxValue(Tp->getIntegerBitWidth()));
   case RecurKind::SMax:
     return ConstantInt::get(Tp,
                             APInt::getSignedMinValue(Tp->getIntegerBitWidth()));
unsigned RecurrenceDescriptor::getOpcode(RecurKind Kind) {
   case RecurKind::FMulAdd:
   case RecurKind::FAdd:
     return Instruction::FAdd;
   case RecurKind::SMax:
   case RecurKind::SMin:
   case RecurKind::UMax:
   case RecurKind::UMin:
   case RecurKind::SelectICmp:
+  case RecurKind::SelectMinIdxMinVal:
+  case RecurKind::SelectMinIdx:
     return Instruction::ICmp;
   case RecurKind::FMax:
   case RecurKind::FMin:
   case RecurKind::SelectFCmp:
     return Instruction::FCmp;
   default:
     llvm_unreachable("Unknown recurrence operation");
   }

llvm/lib/Transforms/Utils/LoopUtils.cpp

bool llvm::hasIterationCountInvariantInParent(Loop *InnerLoop,
 
   return true;
 }
 
 CmpInst::Predicate llvm::getMinMaxReductionPredicate(RecurKind RK) {
   switch (RK) {
   default:
     llvm_unreachable("Unknown min/max recurrence kind");
+  case RecurKind::SelectMinIdx:
+  case RecurKind::SelectMinIdxMinVal:
   case RecurKind::UMin:
     return CmpInst::ICMP_ULT;
   case RecurKind::UMax:
     return CmpInst::ICMP_UGT;
   case RecurKind::SMin:
     return CmpInst::ICMP_SLT;
   case RecurKind::SMax:
     return CmpInst::ICMP_SGT;
case RecurKind::FMul:
     return Builder.CreateFMulReduce(ConstantFP::get(SrcVecEltTy, 1.0), Src);
   case RecurKind::SMax:
     return Builder.CreateIntMaxReduce(Src, true);
   case RecurKind::SMin:
     return Builder.CreateIntMinReduce(Src, true);
   case RecurKind::UMax:
     return Builder.CreateIntMaxReduce(Src, false);
   case RecurKind::UMin:
+  case RecurKind::SelectMinIdxMinVal:
     return Builder.CreateIntMinReduce(Src, false);
+  case RecurKind::SelectMinIdx:
+    llvm_unreachable("Unhandled opcode");
   case RecurKind::FMax:
     return Builder.CreateFPMaxReduce(Src);
   case RecurKind::FMin:
     return Builder.CreateFPMinReduce(Src);
   default:
     llvm_unreachable("Unhandled opcode");
   }
 }

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

if (any_of(FirstOrderRecurrences, [LoopLatch, this](const PHINode *Phi) {
     return false;
 
   // Now we know the widest induction type, check if our found induction
   // is the same size. If it's not, unset it here and InnerLoopVectorizer
   // will create another.
   if (PrimaryInduction && WidestIndTy != PrimaryInduction->getType())
     PrimaryInduction = nullptr;
 
-  return true;
+  unsigned SelectIdx1Cnt = 0;
+  unsigned SelectIdx2Cnt = 0;
+  for (auto &KV : Reductions) {
+    SelectIdx1Cnt += KV.second.getRecurrenceKind() == RecurKind::SelectMinIdx;
+    SelectIdx2Cnt +=
+        KV.second.getRecurrenceKind() == RecurKind::SelectMinIdxMinVal;
+  }
+  return (SelectIdx1Cnt == 0 && SelectIdx2Cnt == 0) ||
+         (SelectIdx1Cnt == 1 && SelectIdx2Cnt == 1);
 }
 
 bool LoopVectorizationLegality::canVectorizeMemory() {
   LAI = &(*GetLAA)(*TheLoop);
   const OptimizationRemarkAnalysis *LAR = LAI->getReport();
   if (LAR) {
     ORE->emit([&]() {
       return OptimizationRemarkAnalysis(Hints->vectorizeAnalysisPassName(),

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (VF.isVector() && PhiTy != RdxDesc.getRecurrenceType()) {
     for (unsigned Part = 0; Part < UF; ++Part) {
       RdxParts[Part] = Builder.CreateTrunc(RdxParts[Part], RdxVecTy);
       State.reset(LoopExitInstDef, RdxParts[Part], Part);
     }
   }
 
   // Reduce all of the unrolled parts into a single vector.
   Value *ReducedPartRdx = State.get(LoopExitInstDef, 0);
+
   unsigned Op = RecurrenceDescriptor::getOpcode(RK);
 
   // The middle block terminator has already been assigned a DebugLoc here (the
   // OrigLoop's single latch terminator). We want the whole middle block to
   // appear to execute on this line because: (a) it is all compiler generated,
   // (b) these instructions are always executed after evaluating the latch
   // conditional branch, and (c) other passes may add new predecessors which
   // terminate on this line. This is the easiest way to ensure we don't
for (unsigned Part = 1; Part < UF; ++Part) {
                                            ReducedPartRdx, RdxPart);
       else
         ReducedPartRdx = createMinMaxOp(Builder, RK, ReducedPartRdx, RdxPart);
     }
   }
 
   // Create the reduction after the loop. Note that inloop reductions create the
   // target reduction in the loop using a Reduction recipe.
-  if (VF.isVector() && !PhiR->isInLoop()) {
+  if (RK == RecurKind::SelectMinIdx) {
+    const RecurrenceDescriptor *RD2 = nullptr;
+    VPReductionPHIRecipe *MinP = nullptr;
+    for (VPRecipeBase &P : PhiR->getParent()
+                               ->getPlan()
+                               ->getVectorLoopRegion()
+                               ->getEntryBasicBlock()
+                               ->phis()) {
+      auto *RedP = dyn_cast<VPReductionPHIRecipe>(&P);
+      if (!RedP)
+        continue;
+      const RecurrenceDescriptor &RdxDesc = RedP->getRecurrenceDescriptor();
+      if (RdxDesc.getRecurrenceKind() == RecurKind::SelectMinIdxMinVal) {
+        MinP = RedP;
+        RD2 = &RdxDesc;
+      }
+    }
+
+    VPValue *MinExitDef = MinP->getBackedgeValue();
+    VPValue *IndexExitDef = PhiR->getBackedgeValue();
+    auto *AllIndices = State.get(IndexExitDef, 0);
+    auto *AllMins = State.get(MinExitDef, 0);
+
+    for (unsigned Part = 1; Part < UF; ++Part) {
+      AllIndices = concatenateVectors(
+          Builder, {AllIndices, State.get(IndexExitDef, Part)});
+      AllMins =
+          concatenateVectors(Builder, {AllMins, State.get(MinExitDef, Part)});
+    }
+
+    Value *MinOfMins = Builder.CreateIntMinReduce(AllMins, false);
+    Value *Mask = Builder.CreateICmpEQ(
+        AllMins, Builder.CreateVectorSplat(State.VF * UF, MinOfMins));
+    Value *Sel = Builder.CreateSelect(
+        Mask, AllIndices,
+        Builder.CreateVectorSplat(
+            State.VF * UF,
+            ConstantInt::get(AllIndices->getType()->getScalarType(), -1)));
+    ReducedPartRdx = Builder.CreateIntMinReduce(Sel, false);
+  } else if (VF.isVector() && !PhiR->isInLoop()) {
     ReducedPartRdx =
         createTargetReduction(Builder, TTI, RdxDesc, ReducedPartRdx, OrigPhi);
     // If the reduction can be performed in a smaller type, we need to extend
     // the reduction to the wider type before we branch to the original loop.
     if (PhiTy != RdxDesc.getRecurrenceType())
       ReducedPartRdx = RdxDesc.isSigned()
                            ? Builder.CreateSExt(ReducedPartRdx, PhiTy)
                            : Builder.CreateZExt(ReducedPartRdx, PhiTy);
assert((Legal->isReductionVariable(Phi) ||
             Legal->isFirstOrderRecurrence(Phi)) &&
            "can only widen reductions and first-order recurrences here");
     VPValue *StartV = Operands[0];
     if (Legal->isReductionVariable(Phi)) {
       const RecurrenceDescriptor &RdxDesc =
           Legal->getReductionVars().find(Phi)->second;
       assert(RdxDesc.getRecurrenceStartValue() ==
              Phi->getIncomingValueForBlock(OrigLoop->getLoopPreheader()));
+
       PhiRecipe = new VPReductionPHIRecipe(Phi, RdxDesc, *StartV,
                                            CM.isInLoopReduction(Phi),
                                            CM.useOrderedReductions(RdxDesc));
     } else {
       PhiRecipe = new VPFirstOrderRecurrencePHIRecipe(Phi, *StartV);
     }
 
     // Record the incoming value from the backedge, so we can add the incoming
VPlanPtr LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
   // Remove the existing terminator of the exiting block of the top-most region.
   // A BranchOnCount will be added instead when adding the canonical IV recipes.
   auto *Term =
       Plan->getVectorLoopRegion()->getExitingBasicBlock()->getTerminator();
   Term->eraseFromParent();
 
   addCanonicalIVRecipes(*Plan, Legal->getWidestInductionType(), DebugLoc(),
                         true, CM.useActiveLaneMaskForControlFlow());
+
   return Plan;
 }
 
 // Adjust the recipes for reductions. For in-loop reductions the chain of
 // instructions leading from the loop exit instr to the phi need to be converted
 // to reductions, with one operand being vector and the other being the scalar
 // reduction chain. For other reductions, a select is introduced between the phi
 // and live-out recipes when folding the tail.

llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp

void VPWidenSelectRecipe::execute(VPTransformState &State) {
   // Instcombine will make this a no-op.
   auto *InvarCond =
       InvariantCond ? State.get(getOperand(0), VPIteration(0, 0)) : nullptr;
 
   for (unsigned Part = 0; Part < State.UF; ++Part) {
     Value *Cond = InvarCond ? InvarCond : State.get(getOperand(0), Part);
     Value *Op0 = State.get(getOperand(1), Part);
     Value *Op1 = State.get(getOperand(2), Part);
+    if (!Op1->getType()->isVectorTy())
+      Op1 = State.Builder.CreateVectorSplat(State.VF, Op1);
     Value *Sel = State.Builder.CreateSelect(Cond, Op0, Op1);
     State.set(this, Sel, Part);
     State.addMetadata(Sel, &I);
   }
 }
 
 void VPWidenRecipe::execute(VPTransformState &State) {
   auto &I = *cast<Instruction>(getUnderlyingValue());
for (unsigned Part = 0; Part < State.UF; ++Part) {
       Value *B = State.get(getOperand(1), Part);
       Value *C = nullptr;
       if (FCmp) {
         // Propagate fast math flags.
         IRBuilder<>::FastMathFlagGuard FMFG(Builder);
         Builder.setFastMathFlags(Cmp->getFastMathFlags());
         C = Builder.CreateFCmp(Cmp->getPredicate(), A, B);
       } else {
+        if (!B->getType()->isVectorTy()) {
+          B = Builder.CreateVectorSplat(State.VF, B);
+        }
         C = Builder.CreateICmp(Cmp->getPredicate(), A, B);
       }
       State.set(this, C, Part);
       State.addMetadata(C, &I);
     }
 
     break;
   }

llvm/test/Transforms/LoopVectorize/select-min-index.ll

 ; RUN: opt -passes=loop-vectorize -force-vector-width=4 -S %s | FileCheck %s
 
 ; Test cases for selecting the index with the minimum value.
 
 define i64 @test_vectorize_select_umin_idx(ptr %src) {
 ; CHECK-LABEL: @test_vectorize_select_umin_idx(
-; CHECK-NOT:   vector.body:
+; CHECK: vector.body:
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
   %gep = getelementptr i64, ptr %src, i64 %iv
   %l = load i64, ptr %gep
   %cmp = icmp ugt i64 %min.val, %l
   %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 %l)
   %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
   %iv.next = add nuw nsw i64 %iv, 1
   %exitcond.not = icmp eq i64 %iv.next, 0
   br i1 %exitcond.not, label %exit, label %loop
 
 exit:
   %res = phi i64 [ %min.idx.next, %loop ]
   ret i64 %res
 }
 
+define i64 @test_vectorize_select_umin_idx_phi_order_flipped(ptr %src) {
+; CHECK-LABEL: @test_vectorize_select_umin_idx_phi_order_flipped(
+; CHECK: vector.body:
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+  %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]
+  %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
+  %gep = getelementptr i64, ptr %src, i64 %iv
+  %l = load i64, ptr %gep
+  %cmp = icmp ugt i64 %min.val, %l
+  %min.val.next = tail call i64 @llvm.umin.i64(i64 %min.val, i64 %l)
+  %min.idx.next = select i1 %cmp, i64 %iv, i64 %min.idx
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond.not = icmp eq i64 %iv.next, 0
+  br i1 %exitcond.not, label %exit, label %loop
+
+exit:
+  %res = phi i64 [ %min.idx.next, %loop ]
+  ret i64 %res
+}
+
+
 define i64 @test_vectorize_select_umin_idx_min_ops_switched(ptr %src) {
 ; CHECK-LABEL: @test_vectorize_select_umin_idx_min_ops_switched(
-; CHECK-NOT:   vector.body:
+; CHECK: vector.body:
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
   %min.idx = phi i64 [ 0, %entry ], [ %min.idx.next, %loop ]
   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]

 
 exit:
   %res = phi i64 [ %min.idx.next, %loop ]
   ret i64 %res
 }
 
 define i32 @test_vectorize_select_umin_idx_with_trunc() {
 ; CHECK-LABEL: @test_vectorize_select_umin_idx_with_trunc(
-; CHECK-NOT:   vector.body:
+; CHECK: vector.body:
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
   %min.idx = phi i32 [ 0, %entry ], [ %min.idx.next, %loop ]
   %min.val = phi i64 [ 0, %entry ], [ %min.val.next, %loop ]