MinMax Index Pattern Identification

[magabari]

Summary

[LV] Handling MinMax Index Pattern (part 1)
The following patch is to identify MinMax Pattern in Loop Vectorizer, e.g. :

for ( ... ) {

if(x>cur_max) {
  cur_max = x;
  cur_max_idx = i;
}

}

Currently it support simple induction case with step 1.

[magabari]

small compilation fix in the prev revision

[delena]

Any test?

[magabari]

added test file

[delena]

Some minor comments inside.

lib/Transforms/Vectorize/LoopVectorize.cpp

4943

Instruction *LoopExit = dyn_cast<SelectInst>(RedDes.getLoopExitInstr());
if (LoopExit ..

4950

A short form:
for (auto reduction_it : Reductions) {

[delena]

include/llvm/Transforms/Utils/LoopUtils.h

169

line alignment

213

You don't need to check the Kind here - it is just get/set.

lib/Transforms/Utils/LoopUtils.cpp

387

remove {}

423

line alignment

541

The code here is difficult to read. I suggest to separate Select form FCmp and ICmp

544

remove {}

602

What FIX should be done here?

lib/Transforms/Vectorize/LoopVectorize.cpp

4896

Why FP min/max does not require extra verification?

4932

I suggest to take this verification in a separate function.

[magabari]

include/llvm/Transforms/Utils/LoopUtils.h

213

this field not relevant if the Kind != MinMax / MinMaxIdx, i just wrote that assert for sanity check

lib/Transforms/Utils/LoopUtils.cpp

602

its suspected to be a reduction not 100% sure of that.

lib/Transforms/Vectorize/LoopVectorize.cpp

4896

notice that the Index pattern needs the verification not the min\max itself,there is no floatMinMaxIdx type, it's only Integer.

[mkuper]

Two notes, before I start the actual review:

First - next time, please don't add llvm-commits after the patch has already been put up for review.
Rather, cancel the existing review, and start a new one with llvm-commits as a subscriber to begin with. Some people feel strongly about having the patch appear in the review thread on llvm-commits.

Second - is this a complete patch? The "return Maybe; //TODO: FIX" looks fishy. And I didn't see anything actually using the Maybe return value.
If this isn't complete, then I'm not entirely sure what's up for review. In that case, please start a new review with the complete patch - with llvm-commits subscribed from the beginning, per point 1. If it is supposed to be complete, then can you explain what the deal with the Maybe is?
(Breaking a patch into smaller units is generally good - but each such unit should be standalone, and this patch doesn't look like it.)

[magabari]

In D22341#495519, @mkuper wrote:

Two notes, before I start the actual review:

First - next time, please don't add llvm-commits after the patch has already been put up for review.
Rather, cancel the existing review, and start a new one with llvm-commits as a subscriber to begin with. Some people feel strongly about having the patch appear in the review thread on llvm-commits.

Second - is this a complete patch? The "return Maybe; //TODO: FIX" looks fishy. And I didn't see anything actually using the Maybe return value.
If this isn't complete, then I'm not entirely sure what's up for review. In that case, please start a new review with the complete patch - with llvm-commits subscribed from the beginning, per point 1. If it is supposed to be complete, then can you explain what the deal with the Maybe is?
(Breaking a patch into smaller units is generally good - but each such unit should be standalone, and this patch doesn't look like it.)

Regarding your first point Okay.
Second point: This is part 1 from 2 this patch deals with the identification of Min Max Index pattern only (it won't vectorize it) although it's a standalone commit but i think i will wait and commit both parts together.
The "Maybe" is just a bad name, need to understand that MinMax Index Pattern rely on the fact that we have found MinMax pattern, so in the first phase i can only say that its a good candidate for MinMax Index reduction (this is why i return Maybe i think it's better to return Candidate) and i put this in ExtraVerificationRequiredList to verify that we have found Min Max pattern. In the 2nd phase i move over all those candidates and make sure that they are real reductions.

[mkuper]

The problem is that as long as the Yes/No/Maybe interface doesn't get used, it's really hard to understand whether it makes sense.
There may be a better way to handle this, and it's really hard to know without seeing the use.

In this case, I suggest you post a more complete patch (for a new review, with llvm-commits subscribed), even if thought it'll be larger.
Also, please clang-format the code you're adding before you post the patch for review. There are a lot of 80-column violations here, among other things.

[mkuper]

Is this still alive?

include/llvm/Transforms/Utils/LoopUtils.h

 class LoopInfo;
 class Pass;
 class PredicatedScalarEvolution;
 class PredIteratorCache;
 class ScalarEvolution;
 class SCEV;
 class TargetLibraryInfo;
 
+/// \enum for query result
+enum QueryResult {
+  False = 0,
+  True,
+  Maybe
+};
+
 /// \brief Captures loop safety information.
 /// It keep information for loop & its header may throw exception.
 struct LoopSafetyInfo {
   bool MayThrow;       // The current loop contains an instruction which
                        // may throw.
   bool HeaderMayThrow; // Same as previous, but specific to loop header
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
public:
   enum RecurrenceKind {
     RK_NoRecurrence,  ///< Not a recurrence.
     RK_IntegerAdd,    ///< Sum of integers.
     RK_IntegerMult,   ///< Product of integers.
     RK_IntegerOr,     ///< Bitwise or logical OR of numbers.
     RK_IntegerAnd,    ///< Bitwise or logical AND of numbers.
     RK_IntegerXor,    ///< Bitwise or logical XOR of numbers.
     RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()).
+    RK_IntegerMinMaxIdx,///< Min/max index implemented in terms of select(cmp(),idx).
     RK_FloatAdd,      ///< Sum of floats.
     RK_FloatMult,     ///< Product of floats.
     RK_FloatMinMax    ///< Min/max implemented in terms of select(cmp()).
   };
 
   // This enum represents the kind of minmax recurrence.
   enum MinMaxRecurrenceKind {
     MRK_Invalid,
     MRK_UIntMin,
     MRK_UIntMax,
     MRK_SIntMin,
     MRK_SIntMax,
     MRK_FloatMin,
     MRK_FloatMax
   };
 
   RecurrenceDescriptor()
       : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoRecurrence),
         MinMaxKind(MRK_Invalid), UnsafeAlgebraInst(nullptr),
-        RecurrenceType(nullptr), IsSigned(false) {}
+        RecurrenceType(nullptr), IsSigned(false), CmpInstr(nullptr) {}
 
   RecurrenceDescriptor(Value *Start, Instruction *Exit, RecurrenceKind K,
                        MinMaxRecurrenceKind MK, Instruction *UAI, Type *RT,
                        bool Signed, SmallPtrSetImpl<Instruction *> &CI)
       : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK),
-        UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed) {
+        UnsafeAlgebraInst(UAI), RecurrenceType(RT), IsSigned(Signed), 
+        CmpInstr(nullptr) {
     CastInsts.insert(CI.begin(), CI.end());
   }
 
   /// This POD struct holds information about a potential recurrence operation.
   class InstDesc {
 
   public:
     InstDesc(bool IsRecur, Instruction *I, Instruction *UAI = nullptr)
private:
     Instruction *UnsafeAlgebraInst;
   };
 
   /// Returns a struct describing if the instruction 'I' can be a recurrence
   /// variable of type 'Kind'. 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(Instruction *I, RecurrenceKind Kind,
+  static InstDesc isRecurrenceInstr(ScalarEvolution *SE, Instruction *I, RecurrenceKind Kind,
                                     InstDesc &Prev, bool HasFunNoNaNAttr);
 
   /// Returns true if instruction I has multiple uses in Insts
   static bool hasMultipleUsesOf(Instruction *I,
                                 SmallPtrSetImpl<Instruction *> &Insts);
 
   /// Returns true if all uses of the instruction I is within the Set.
   static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
 
   /// Returns a struct describing if the instruction if the instruction is a
   /// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y)
   /// or max(X, Y).
-  static InstDesc isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev);
+  static InstDesc isMinMaxSelectCmpPattern(ScalarEvolution *SE, Instruction *I, 
+                                           InstDesc &Prev);
+
+  /// Checks if the given Operands matches MinMax Index Pattern  
+  static bool isMinMaxIndexOperands(ScalarEvolution *SE, Value *InductionCandidate,
+                                    Value *OldValueCandidate, Value *Result);
+
+  /// Returns true if the given select instruction matches a select of index
+  /// e.g. select A, B; while one of A/B is a reduction and other one is phi 
+  static bool isMinMaxIndexCandidate(ScalarEvolution *SE, SelectInst *SI);
 
   /// Returns identity corresponding to the RecurrenceKind.
   static Constant *getRecurrenceIdentity(RecurrenceKind K, Type *Tp);
 
   /// Returns the opcode of binary operation corresponding to the
   /// RecurrenceKind.
   static unsigned getRecurrenceBinOp(RecurrenceKind Kind);
 
   /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
   static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxRecurrenceKind RK,
                                Value *Left, Value *Right);
 
   /// Returns true if Phi is a reduction of type Kind and adds it to the
   /// RecurrenceDescriptor.
-  static bool AddReductionVar(PHINode *Phi, RecurrenceKind Kind, Loop *TheLoop,
-                              bool HasFunNoNaNAttr,
+  static bool AddReductionVar(ScalarEvolution *SE, PHINode *Phi, RecurrenceKind Kind, 
+                              Loop *TheLoop, bool HasFunNoNaNAttr,
                               RecurrenceDescriptor &RedDes);
 
-  /// Returns true if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
+  /// Returns True if Phi is a reduction in TheLoop. The RecurrenceDescriptor is
   /// returned in RedDes.
-  static bool isReductionPHI(PHINode *Phi, Loop *TheLoop,
-                             RecurrenceDescriptor &RedDes);
+  static QueryResult isReductionPHI(ScalarEvolution *SE, PHINode *Phi, 
+                                    Loop *TheLoop, RecurrenceDescriptor &RedDes);
 
   /// Returns true if Phi is a first-order recurrence. A first-order recurrence
   /// is a non-reduction recurrence relation in which the value of the
   /// recurrence in the current loop iteration equals a value defined in the
   /// previous iteration.
   static bool isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
                                      DominatorTree *DT);
 
   RecurrenceKind getRecurrenceKind() { return Kind; }
 
   MinMaxRecurrenceKind getMinMaxRecurrenceKind() { return MinMaxKind; }
 
   TrackingVH<Value> getRecurrenceStartValue() { return StartValue; }
 
   Instruction *getLoopExitInstr() { return LoopExitInstr; }
 
+  void setCmpInstr(Instruction *Instr) { 
+    assert(((Kind == RK_IntegerMinMax) || (Kind == RK_FloatMinMax)) &&
+           "Should be MinMax Recurrence");
+    CmpInstr = Instr; 
+  }
+
+  Instruction* getCmpInstr() {
+    assert(((Kind == RK_IntegerMinMax) || (Kind == RK_FloatMinMax)) &&
+           "Should be MinMax Recurrence");
+    return CmpInstr;
+  }
+
   /// Returns true if the recurrence has unsafe algebra which requires a relaxed
   /// floating-point model.
   bool hasUnsafeAlgebra() { return UnsafeAlgebraInst != nullptr; }
 
   /// Returns first unsafe algebra instruction in the PHI node's use-chain.
   Instruction *getUnsafeAlgebraInst() { return UnsafeAlgebraInst; }
 
   /// Returns true if the recurrence kind is an integer kind.
private:
   // First occurance of unasfe algebra in the PHI's use-chain.
   Instruction *UnsafeAlgebraInst;
   // The type of the recurrence.
   Type *RecurrenceType;
   // True if all source operands of the recurrence are SExtInsts.
   bool IsSigned;
   // Instructions used for type-promoting the recurrence.
   SmallPtrSet<Instruction *, 8> CastInsts;
+  // In case of minmax kind we can point to the cmp instruction
+  // used in case if cmp is shared between minmax and minmax index
+  Instruction *CmpInstr; 
 };
 
 /// A struct for saving information about induction variables.
 class InductionDescriptor {
 public:
   /// This enum represents the kinds of inductions that we support.
   enum InductionKind {
     IK_NoInduction,  ///< Not an induction variable.

lib/Transforms/Scalar/LoopInterchange.cpp

#endif
   }
 };
 
 } // end of namespace
 bool LoopInterchangeLegality::areAllUsesReductions(Instruction *Ins, Loop *L) {
   return !std::any_of(Ins->user_begin(), Ins->user_end(), [=](User *U) -> bool {
     PHINode *UserIns = dyn_cast<PHINode>(U);
     RecurrenceDescriptor RD;
-    return !UserIns || !RecurrenceDescriptor::isReductionPHI(UserIns, L, RD);
+    return !UserIns || RecurrenceDescriptor::isReductionPHI(SE, UserIns, L, RD) != True;
   });
 }
 
 bool LoopInterchangeLegality::containsUnsafeInstructionsInHeader(
     BasicBlock *BB) {
   for (auto I = BB->begin(), E = BB->end(); I != E; ++I) {
     // Load corresponding to reduction PHI's are safe while concluding if
     // tightly nested.
bool LoopInterchangeLegality::findInductionAndReductions(
   if (!L->getLoopLatch() || !L->getLoopPredecessor())
     return false;
   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
     RecurrenceDescriptor RD;
     InductionDescriptor ID;
     PHINode *PHI = cast<PHINode>(I);
     if (InductionDescriptor::isInductionPHI(PHI, SE, ID))
       Inductions.push_back(PHI);
-    else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD))
+    else if (RecurrenceDescriptor::isReductionPHI(SE, PHI, L, RD) == True)
       Reductions.push_back(PHI);
     else {
       DEBUG(
           dbgs() << "Failed to recognize PHI as an induction or reduction.\n");
       return false;
     }
   }
   return true;

lib/Transforms/Utils/LoopUtils.cpp

bool RecurrenceDescriptor::isIntegerRecurrenceKind(RecurrenceKind Kind) {
   default:
     break;
   case RK_IntegerAdd:
   case RK_IntegerMult:
   case RK_IntegerOr:
   case RK_IntegerAnd:
   case RK_IntegerXor:
   case RK_IntegerMinMax:
+  case RK_IntegerMinMaxIdx:
     return true;
   }
   return false;
 }
 
 bool RecurrenceDescriptor::isFloatingPointRecurrenceKind(RecurrenceKind Kind) {
   return (Kind != RK_NoRecurrence) && !isIntegerRecurrenceKind(Kind);
 }
for (Use &U : I->operands()) {
       // cost model.
       if (SrcSize == DstSize)
         CI.insert(Cast);
     }
   }
   return true;
 }
 
-bool RecurrenceDescriptor::AddReductionVar(PHINode *Phi, RecurrenceKind Kind,
-                                           Loop *TheLoop, bool HasFunNoNaNAttr,
+bool RecurrenceDescriptor::AddReductionVar(ScalarEvolution *SE, PHINode *Phi, 
+                                           RecurrenceKind Kind, Loop *TheLoop,
+                                           bool HasFunNoNaNAttr, 
                                            RecurrenceDescriptor &RedDes) {
   if (Phi->getNumIncomingValues() != 2)
     return false;
 
   // Reduction variables are only found in the loop header block.
   if (Phi->getParent() != TheLoop->getHeader())
     return false;
 
bool RecurrenceDescriptor::AddReductionVar(ScalarEvolution *SE, PHINode *Phi,
   bool FoundReduxOp = false;
 
   // We start with the PHI node and scan for all of the users of this
   // instruction. All users must be instructions that can be used as reduction
   // variables (such as ADD). We must have a single out-of-block user. The cycle
   // must include the original PHI.
   bool FoundStartPHI = false;
 
+  // Turns to true if we found minmax index candidate in minmax pattern, in this
+  // case minmax value may or may not have an external usage (ExitInstruction)
+  // because it's already used in minmax index calculation
+  bool MinMaxIndexUseFound = false;
+  Instruction *MinMaxSharedCmpInstr = nullptr;
+
   // To recognize min/max patterns formed by a icmp select sequence, we store
   // the number of instruction we saw from the recognized min/max pattern,
   //  to make sure we only see exactly the two instructions.
   unsigned NumCmpSelectPatternInst = 0;
   InstDesc ReduxDesc(false, nullptr);
 
   // Data used for determining if the recurrence has been type-promoted.
   Type *RecurrenceType = Phi->getType();
if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) &&
         !isa<ICmpInst>(Cur) && !isa<FCmpInst>(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(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
+      ReduxDesc = isRecurrenceInstr(SE, Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
       if (!ReduxDesc.isRecurrence())
         return false;
     }
 
     // A reduction operation must only have one use of the reduction value.
     if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax &&
         hasMultipleUsesOf(Cur, VisitedInsts))
       return false;
while (!Worklist.empty()) {
     // Process users of current instruction. Push non-PHI nodes after PHI nodes
     // onto the stack. This way we are going to have seen all inputs to PHI
     // nodes once we get to them.
     SmallVector<Instruction *, 8> NonPHIs;
     SmallVector<Instruction *, 8> PHIs;
     for (User *U : Cur->users()) {
       Instruction *UI = cast<Instruction>(U);
 
+      // Skip min-max index select (will be checked later with the relevant Phi)
+      if((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) && isa<SelectInst>(UI)
+          && (isa<ICmpInst>(Cur) || isa<FCmpInst>(Cur)) 
+          && isMinMaxIndexCandidate(SE, dyn_cast<SelectInst>(UI))) {
+        MinMaxIndexUseFound = true;
+        MinMaxSharedCmpInstr = dyn_cast<Instruction>(UI->getOperand(0));
+        continue;
+      }
+
       // Check if we found the exit user.
       BasicBlock *Parent = UI->getParent();
       if (!TheLoop->contains(Parent)) {
         // Exit if you find multiple outside users or if the header phi node is
         // being used. In this case the user uses the value of the previous
         // iteration, in which case we would loose "VF-1" iterations of the
         // reduction operation if we vectorize.
         if (ExitInstruction != nullptr || Cur == Phi)
for (User *U : Cur->users()) {
       if (VisitedInsts.insert(UI).second) {
         if (isa<PHINode>(UI))
           PHIs.push_back(UI);
         else
           NonPHIs.push_back(UI);
       } else if (!isa<PHINode>(UI) &&
                  ((!isa<FCmpInst>(UI) && !isa<ICmpInst>(UI) &&
                    !isa<SelectInst>(UI)) ||
-                  !isMinMaxSelectCmpPattern(UI, IgnoredVal).isRecurrence()))
+                  !isMinMaxSelectCmpPattern(SE, UI, IgnoredVal).isRecurrence()))
         return false;
 
       // Remember that we completed the cycle.
       if (UI == Phi)
         FoundStartPHI = true;
     }
     Worklist.append(PHIs.begin(), PHIs.end());
     Worklist.append(NonPHIs.begin(), NonPHIs.end());
   }
 
   // This means we have seen one but not the other instruction of the
   // pattern or more than just a select and cmp.
   if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) &&
       NumCmpSelectPatternInst != 2)
     return false;
 
-  if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction)
+  if (!FoundStartPHI || !FoundReduxOp || (!ExitInstruction && !MinMaxIndexUseFound)) 
     return false;
 
   // If we think Phi may have been type-promoted, we also need to ensure that
   // all source operands of the reduction are either SExtInsts or ZEstInsts. If
   // so, we will be able to evaluate the reduction in the narrower bit width.
   if (Start != Phi)
     if (!getSourceExtensionKind(Start, ExitInstruction, RecurrenceType,
                                 IsSigned, VisitedInsts, CastInsts))
       return false;
 
   // We found a reduction var if we have reached the original phi node and we
   // only have a single instruction with out-of-loop users.
 
   // The ExitInstruction(Instruction which is allowed to have out-of-loop users)
   // is saved as part of the RecurrenceDescriptor.
 
   // Save the description of this reduction variable.
   RecurrenceDescriptor RD(
       RdxStart, ExitInstruction, Kind, ReduxDesc.getMinMaxKind(),
       ReduxDesc.getUnsafeAlgebraInst(), RecurrenceType, IsSigned, CastInsts);
-  RedDes = RD;
 
+  // in case of minmax with a suspect of minmax index candidate save the shared 
+  // cmp instruction for a later checks
+  if (((RD.getRecurrenceKind() == RK_IntegerMinMax) || 
+      (RD.getRecurrenceKind() == RK_FloatMinMax)) && MinMaxIndexUseFound ) {
+    if (MinMaxSharedCmpInstr) 
+      RD.setCmpInstr(MinMaxSharedCmpInstr);
+  }
+
+  RedDes = RD;
   return true;
 }
 
+bool RecurrenceDescriptor::isMinMaxIndexOperands(ScalarEvolution *SE, Value *InductionCandidate, 
+                                                 Value *OldValueCandidate, Value *Result) {
+  if(isa<PHINode>(OldValueCandidate)) {
+    PHINode* Phi = dyn_cast<PHINode>(OldValueCandidate);
+    // first check the result is incoming value for that phi
+    bool found = false;
+    for(unsigned i = 0; i < Phi->getNumIncomingValues(); ++i) {
+      if(Phi->getIncomingValue(i) == Result) found = true;
+    }
+    // result is not incoming value for that phi 
+    if (!found) return false;
+
+    // Need to check the InductionCandidate
+    // Currently we support induction with step 1
+    const SCEV* MayInduction = SE->getSCEV(InductionCandidate);
+    if(const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(MayInduction)) {
+      const SCEV *Step = AR->getStepRecurrence(*SE);
+      return Step->isOne();
+    }
+    return false;
+  }
+  return false;
+} 
+
+bool RecurrenceDescriptor::isMinMaxIndexCandidate(ScalarEvolution *SE, SelectInst *SI) {
+  assert(SI && "given null select instr");
+
+  return isMinMaxIndexOperands(SE, SI->getTrueValue(), SI->getFalseValue(), SI) ||
+         isMinMaxIndexOperands(SE, SI->getFalseValue(), SI->getTrueValue(), SI);
+}
+
 /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction
 /// pattern corresponding to a min(X, Y) or max(X, Y).
 RecurrenceDescriptor::InstDesc
-RecurrenceDescriptor::isMinMaxSelectCmpPattern(Instruction *I, InstDesc &Prev) {
+RecurrenceDescriptor::isMinMaxSelectCmpPattern(ScalarEvolution *SE, Instruction *I, 
+                                               InstDesc &Prev) {
 
   assert((isa<ICmpInst>(I) || isa<FCmpInst>(I) || isa<SelectInst>(I)) &&
          "Expect a select instruction");
   Instruction *Cmp = nullptr;
   SelectInst *Select = nullptr;
 
   // We must handle the select(cmp()) as a single instruction. Advance to the
   // select.
   if ((Cmp = dyn_cast<ICmpInst>(I)) || (Cmp = dyn_cast<FCmpInst>(I))) {
+    // we allow cmp to have more than one use only if it may be minmax index 
+    // reduction type e.g.:
+    //         %a = cmp    CC, %X, %Y
+    //  user1: %b = select %a, %X, %Y             ;  for minmax value
+    //  user2: %c = select %a, OldIndex, CurIndex ;  for minmax index  
+    if (Cmp->getNumUses() == 2) {
+      // minmax index user should be select between itself(Old) and induction
+      // minmax value user can be different (min\max value)
+      SelectInst* Candidate = nullptr; 
+      for (User *U : Cmp->users()) {
+        SelectInst *SI = dyn_cast<SelectInst>(U);
+        if(!SI) 
+          return InstDesc(false, I);
+
+        if(!isMinMaxIndexCandidate(SE, SI)) {
+          // If we already have a minmax value candidate return false
+          if(Candidate) return InstDesc(false, I);
+          // In case we still dont have a minmax value candidate then mark this select
+          Candidate = SI;
+        }
+      }
+      // If we dont have minmax value candidate return false
+      if(!Candidate)
+        return InstDesc(false, I);
+      return InstDesc(Candidate, Prev.getMinMaxKind()); 
+    }
+    // otherwise
     if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
       return InstDesc(false, I);
     return InstDesc(Select, Prev.getMinMaxKind());
   }
 
   // Only handle single use cases for now.
   if (!(Select = dyn_cast<SelectInst>(I)))
     return InstDesc(false, I);
   if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
       !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
     return InstDesc(false, I);
-  if (!Cmp->hasOneUse())
-    return InstDesc(false, I);
 
   Value *CmpLeft;
   Value *CmpRight;
 
   // Look for a min/max pattern.
   if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
     return InstDesc(Select, MRK_UIntMin);
   else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
     return InstDesc(Select, MRK_FloatMin);
   else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
     return InstDesc(Select, MRK_FloatMax);
 
   return InstDesc(false, I);
 }
 
 RecurrenceDescriptor::InstDesc
-RecurrenceDescriptor::isRecurrenceInstr(Instruction *I, RecurrenceKind Kind,
-                                        InstDesc &Prev, bool HasFunNoNaNAttr) {
+RecurrenceDescriptor::isRecurrenceInstr(ScalarEvolution *SE, Instruction *I, 
+                                        RecurrenceKind Kind, InstDesc &Prev,
+                                        bool HasFunNoNaNAttr) {
   bool FP = I->getType()->isFloatingPointTy();
   Instruction *UAI = Prev.getUnsafeAlgebraInst();
   if (!UAI && FP && !I->hasUnsafeAlgebra())
     UAI = I; // Found an unsafe (unvectorizable) algebra instruction.
 
   switch (I->getOpcode()) {
   default:
     return InstDesc(false, I);
case Instruction::Or:
     return InstDesc(Kind == RK_IntegerOr, I);
   case Instruction::Xor:
     return InstDesc(Kind == RK_IntegerXor, I);
   case Instruction::FMul:
     return InstDesc(Kind == RK_FloatMult, I, UAI);
   case Instruction::FSub:
   case Instruction::FAdd:
     return InstDesc(Kind == RK_FloatAdd, I, UAI);
+  case Instruction::Select:
+    if (Kind == RK_IntegerMinMaxIdx) {
+      // We have a minmax index candidate
+      if (isMinMaxIndexCandidate(SE, dyn_cast<SelectInst>(I))) 
+        return InstDesc(true, I);
+    }
   case Instruction::FCmp:
   case Instruction::ICmp:
-  case Instruction::Select:
     if (Kind != RK_IntegerMinMax &&
         (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
       return InstDesc(false, I);
-    return isMinMaxSelectCmpPattern(I, Prev);
+    return isMinMaxSelectCmpPattern(SE, I, Prev);
   }
 }
 
 bool RecurrenceDescriptor::hasMultipleUsesOf(
     Instruction *I, SmallPtrSetImpl<Instruction *> &Insts) {
   unsigned NumUses = 0;
   for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E;
        ++Use) {
     if (Insts.count(dyn_cast<Instruction>(*Use)))
       ++NumUses;
     if (NumUses > 1)
       return true;
   }
 
   return false;
 }
-bool RecurrenceDescriptor::isReductionPHI(PHINode *Phi, Loop *TheLoop,
-                                          RecurrenceDescriptor &RedDes) {
+QueryResult RecurrenceDescriptor::isReductionPHI(ScalarEvolution* SE, PHINode *Phi, 
+                                                 Loop *TheLoop, RecurrenceDescriptor &RedDes) {
 
   BasicBlock *Header = TheLoop->getHeader();
   Function &F = *Header->getParent();
   bool HasFunNoNaNAttr =
       F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
 
-  if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
+  if (AddReductionVar(SE, Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
     DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
-    return true;
+    return True;
   }
-  if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
+  if (AddReductionVar(SE, Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
     DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
-    return true;
+    return True;
   }
-  if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
+  if (AddReductionVar(SE, Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
     DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
-    return true;
+    return True;
   }
-  if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
+  if (AddReductionVar(SE, Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
     DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
-    return true;
+    return True;
   }
-  if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
+  if (AddReductionVar(SE, Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
     DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
-    return true;
+    return True;
   }
-  if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
+  if (AddReductionVar(SE, Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
                       RedDes)) {
     DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
-    return true;
+    return True;
+  }
+  if (AddReductionVar(SE, Phi, RK_IntegerMinMaxIdx, TheLoop, HasFunNoNaNAttr,
+                      RedDes)) {
+    DEBUG(dbgs() << "Suspect a MINMAX INDEX reduction PHI." << *Phi << "\n");
+    return Maybe; //TODO: FIX
   }
-  if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
+  if (AddReductionVar(SE, Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
     DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
-    return true;
+    return True;
   }
-  if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
+  if (AddReductionVar(SE, Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
     DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
-    return true;
+    return True;
   }
-  if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
+  if (AddReductionVar(SE, Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
     DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
-    return true;
+    return True;
   }
   // Not a reduction of known type.
-  return false;
+  return False;
 }
 
 bool RecurrenceDescriptor::isFirstOrderRecurrence(PHINode *Phi, Loop *TheLoop,
                                                   DominatorTree *DT) {
 
   // Ensure the phi node is in the loop header and has two incoming values.
   if (Phi->getParent() != TheLoop->getHeader() ||
       Phi->getNumIncomingValues() != 2)

lib/Transforms/Vectorize/LoopVectorize.cpp

   /// ReductionList contains the reduction descriptors for all
   /// of the reductions that were found in the loop.
   typedef DenseMap<PHINode *, RecurrenceDescriptor> ReductionList;
 
   /// InductionList saves induction variables and maps them to the
   /// induction descriptor.
   typedef MapVector<PHINode *, InductionDescriptor> InductionList;
 
+  // VerificationList contains all the suspected complex reductions
+  // which need another extra verification phase after we move over all
+  // other reductions
+  typedef DenseMap<PHINode *, RecurrenceDescriptor> VerificationList;
+
   /// RecurrenceSet contains the phi nodes that are recurrences other than
   /// inductions and reductions.
   typedef SmallPtrSet<const PHINode *, 8> RecurrenceSet;
 
   /// Returns true if it is legal to vectorize this loop.
   /// This does not mean that it is profitable to vectorize this
   /// loop, only that it is legal to do so.
   bool canVectorize();

   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);
 
+  /// Returns True if it succeded to identify all the given list as Reductions
+  /// and add them to the Reduction list
+  bool handleSecondOrderReductions(VerificationList& ExtraVerificationRequired);
+
   /// 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.

   // back into the PHI node may have external users.
   AllowedExit.insert(Phi);
   AllowedExit.insert(Phi->getIncomingValueForBlock(TheLoop->getLoopLatch()));
 
   DEBUG(dbgs() << "LV: Found an induction variable.\n");
   return;
 }
 
+bool LoopVectorizationLegality::handleSecondOrderReductions(
+    VerificationList& ExtraVerificationRequired) {
+  unsigned identifiedItems = 0;
+  // Move over all the items in the verification list and check if each item can be considered 
+  // a Reduction (relying on the Reduction List)
+  for(VerificationList::iterator it = ExtraVerificationRequired.begin();
+      it != ExtraVerificationRequired.end(); it++) {
+    // Extract pair elements
+    PHINode *PhiMinMaxIdCandidate = it->first;
+    RecurrenceDescriptor RedDes = it->second;
+    // We currently handle MinMax Idx pattern which depends on MinMax pattern
+    if (RedDes.getRecurrenceKind() == RecurrenceDescriptor::RK_IntegerMinMaxIdx) {
+      Instruction *LoopExit = dyn_cast<SelectInst>(RedDes.getLoopExitInstr());
+      if (LoopExit &&
+          (isa<ICmpInst>(LoopExit->getOperand(0)) || isa<FCmpInst>(LoopExit->getOperand(0)))) {
+        Instruction *CmpInstr = dyn_cast<Instruction>(LoopExit->getOperand(0));
+        // Move over all the reductions we have found and see if the suspected Cmp
+        // is used in min max pattern if yes then we have found a minmax index pattern
+        for (auto reduction_it : Reductions) {
+          RecurrenceDescriptor Des = reduction_it.second;
+          if (((Des.getRecurrenceKind() == RecurrenceDescriptor::RK_IntegerMinMax) ||
+              (Des.getRecurrenceKind() == RecurrenceDescriptor::RK_FloatMinMax)) &&
+              Des.getCmpInstr() == CmpInstr) {
+            DEBUG(dbgs() << "LV: Found a minmax index PHI: " << *PhiMinMaxIdCandidate
+                         << "\nDepends On: " << *(reduction_it.first) << "\n");
+            Reductions[PhiMinMaxIdCandidate] = RedDes;
+            identifiedItems++;
+            break;
+          }
+        }
+      }
+    }
+  }
+  // If we did not identify all the listed items report an error
+  if (identifiedItems != ExtraVerificationRequired.size()) {
+    // Unknown type found halt
+    DEBUG(dbgs() << "LV: Extra verification required of unsupported kind.\n");
+    return false;
+  }
+  // We have identified all the listed items
+  return true;
+}
+
 bool LoopVectorizationLegality::canVectorizeInstrs() {
+  VerificationList ExtraVerificationRequired;
   BasicBlock *Header = TheLoop->getHeader();
 
   // Look for the attribute signaling the absence of NaNs.
   Function &F = *Header->getParent();
   HasFunNoNaNAttr =
       F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
 
   // For each block in the loop.
   for (Loop::block_iterator bb = TheLoop->block_begin(),
                             be = TheLoop->block_end();
        bb != be; ++bb) {
 
     // Scan the instructions in the block and look for hazards.
     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
          ++it) {
 

           emitAnalysis(VectorizationReport(&*it)
                        << "value could not be identified as "
                           "an induction or reduction variable");
           return false;
         }
 
         // We only allow if-converted PHIs with exactly two incoming values.
         if (Phi->getNumIncomingValues() != 2) {
           emitAnalysis(VectorizationReport(&*it)
                        << "control flow not understood by vectorizer");
           DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
           return false;
         }
 
         RecurrenceDescriptor RedDes;
-        if (RecurrenceDescriptor::isReductionPHI(Phi, TheLoop, RedDes)) {
+        if (RecurrenceDescriptor::isReductionPHI(PSE.getSE(), Phi, TheLoop, RedDes) != False) {
+          // in case of minmax index still we should make sure that the 2nd pair is minmax
+          // this extra verification will be done in a later phase after we move over all
+          // the Phi's
+          if (RedDes.getRecurrenceKind() == RecurrenceDescriptor::RK_IntegerMinMaxIdx) {
+            ExtraVerificationRequired[Phi] = RedDes;
+            continue;
+          }
           if (RedDes.hasUnsafeAlgebra())
             Requirements->addUnsafeAlgebraInst(RedDes.getUnsafeAlgebraInst());
           AllowedExit.insert(RedDes.getLoopExitInstr());
           Reductions[Phi] = RedDes;
           continue;
         }
 
         InductionDescriptor ID;
         if (InductionDescriptor::isInductionPHI(Phi, PSE, ID)) {
           addInductionPhi(Phi, ID, AllowedExit);
           continue;
         }

 
         emitAnalysis(VectorizationReport(&*it)
                      << "value that could not be identified as "
                         "reduction is used outside the loop");
         DEBUG(dbgs() << "LV: Found an unidentified PHI." << *Phi << "\n");
         return false;
       } // end of PHI handling
 
+      // We have Reductions that need extra verfication phase (depends on other
+      // reductions results)  
+      if (!ExtraVerificationRequired.empty() &&
+        !handleSecondOrderReductions(ExtraVerificationRequired))
+        return false;
+
       // We handle calls that:
       //   * Are debug info intrinsics.
       //   * Have a mapping to an IR intrinsic.
       //   * Have a vector version available.
       CallInst *CI = dyn_cast<CallInst>(it);
       if (CI && !getVectorIntrinsicIDForCall(CI, TLI) &&
           !isa<DbgInfoIntrinsic>(CI) &&
           !(CI->getCalledFunction() && TLI &&

test/Transforms/LoopVectorize/minmax_index_identification.ll

+;RUN: opt < %s  -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -debug -S 2>&1 >/dev/null | FileCheck %s
+
+; ModuleID = 'tmp.c'
+source_filename = "tmp.c"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: norecurse nounwind readonly uwtable
+define i32 @max_idx_before(i32* nocapture readonly %arr, i32 %N) local_unnamed_addr  {
+entry:
+  %cmp14 = icmp sgt i32 %N, 0
+  br i1 %cmp14, label %for.body.preheader, label %for.cond.cleanup
+
+for.body.preheader:                               ; preds = %entry
+  %0 = load i32, i32* %arr, align 4
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  %idx.0.lcssa = phi i32 [ 0, %entry ], [ %i.0.idx.0, %for.body ]
+  ret i32 %idx.0.lcssa
+
+for.body:                                         ; preds = %for.body, %for.body.preheader
+; CHECK-LABEL: max_idx_before
+; CHECK: LV: Found a minmax index PHI:   %idx.016
+; CHECK: Depends On:   %max.015  
+  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
+  %idx.016 = phi i32 [ 0, %for.body.preheader ], [ %i.0.idx.0, %for.body ]
+  %max.015 = phi i32 [ %0, %for.body.preheader ], [ %.max.0, %for.body ]
+  %arrayidx1 = getelementptr inbounds i32, i32* %arr, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx1, align 4
+  %cmp2 = icmp slt i32 %max.015, %1
+  %.max.0 = select i1 %cmp2, i32 %1, i32 %max.015
+  %2 = trunc i64 %indvars.iv to i32
+  %i.0.idx.0 = select i1 %cmp2, i32 %2, i32 %idx.016
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+define i32 @max_idx_after(i32* nocapture readonly %arr, i32 %N) local_unnamed_addr  {
+entry:
+  %cmp14 = icmp sgt i32 %N, 0
+  br i1 %cmp14, label %for.body.preheader, label %for.cond.cleanup
+
+for.body.preheader:                               ; preds = %entry
+  %0 = load i32, i32* %arr, align 4
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  %idx.0.lcssa = phi i32 [ 0, %entry ], [ %i.0.idx.0, %for.body ]
+  ret i32 %idx.0.lcssa
+
+for.body:                                         ; preds = %for.body, %for.body.preheader
+; CHECK-LABEL: max_idx_after
+; CHECK: LV: Found a minmax index PHI:   %idx.016
+; CHECK: Depends On:   %max.015
+  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
+  %max.015 = phi i32 [ %0, %for.body.preheader ], [ %.max.0, %for.body ]
+  %idx.016 = phi i32 [ 0, %for.body.preheader ], [ %i.0.idx.0, %for.body ]
+  %arrayidx1 = getelementptr inbounds i32, i32* %arr, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx1, align 4
+  %cmp2 = icmp slt i32 %max.015, %1
+  %.max.0 = select i1 %cmp2, i32 %1, i32 %max.015
+  %2 = trunc i64 %indvars.iv to i32
+  %i.0.idx.0 = select i1 %cmp2, i32 %2, i32 %idx.016
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %N
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+