Refactor identification of reductions and expose them as utility functions

[karthikthecool]

Summary

Hi All,
I would like to reuse LoopVectorizer's code to identify/categorize reductions in one of my Pass.
Refactor functions/code required to identify a reduction and expose them as utility functions.
No functionality change.
Please let me know if this is good to commit.

Thanks and Regards
Karthik Bhat

[jmolloy]

Hi Karthik,

I like the general direction. We have reduction detection logic in too many places already (LoopReroller, I'm looking at you!) and this will enable us to only have one.

However, the functions you've ripped out of LoopVectorizationLegality no longer make sense to be in LoopVectorize.cpp - they should be in lib/Transforms/Utils to avoid a layering violation.

Cheers,

James

[karthikthecool]

Hi James,
Thanks for the review. Yes it makes sense to move it out of LoopVectorizer.cpp. Updated the code as per reveiw comments.
Added a file LoopUtils.cpp in lib/Transforms/Utils with refactored code. We can add any additional common loop functionalities in this util file.

Please let me know if this looks good to you.

Thanks and Regards
Karthik Bhat

[rengolin]

Hi Karthik,

This is looking a lot better, thanks!

I have two main comment inline, and I'm assuming it passes all check-all tests and maybe the test-suite in at least one major platform.

Also, please remember to add "NFC" (meaning non-functional-change) to your commit message, since this is just the refactoring part of your patch.

Finally, it'd be good to see how your pass looks like with this change, to make sure we won't need additional refactorings to this piece of code. Can you add a new diff to the loop interchange pass that assumes these changes are applied?

cheers,
--renato

include/llvm/Transforms/Utils/LoopUtils.h

46

These enums now have llvm namespace. While RK clearly means "reduction kind" in the context of the loop vectorizer, it doesn't in a general context. I'm not sure what's best in this case, to add a namespace or move it inside some of the structs below. @jmolloy?

lib/Transforms/Utils/LoopUtils.cpp

194

Change this comment here to state that the exit instruction will be saved as you create the reduction descriptor below.

[karthikthecool]

Hi Renato,
Thanks for your valuable inputs. I have addressed one of your comments and modified the comments as per your suggestion.
Will wait for your/James input on if to move the enums into namespace/structure.

Yes I have run make check-all on X86 and there are no regressions.

Sure I will update the LoopInterchange pass assuming this change. We wont need any additional refactoring and we can reuse these functions as it is.

Thanks once again for your time and support.

Thanks & Regards
Karthik Bhat

[rengolin]

In D9046#157023, @karthikthecool wrote:

Will wait for your/James input on if to move the enums into namespace/structure.

Yes, and maybe @aschwaighofer, too.

Yes I have run make check-all on X86 and there are no regressions.

Good. Thanks!

Sure I will update the LoopInterchange pass assuming this change. We wont need any additional refactoring and we can reuse these functions as it is.

Excellent. Looking forward to seeing it.

cheers,
--renato

[anemet]

include/llvm/Transforms/Utils/LoopUtils.h

45–62

I haven't dealt with this part of the vectorizer yet so I only have general comments about some interface improvements, now, that these interfaces are made public.

Are these enums local to the structures that follow right after? If yes, they should be local to those structs.

123–126

These are missing comments. Also if they operate on a ReductionDesc, they should probably made a member function. And possibly turning the struct into classes to describe the public interface of the class.

128–130

These don't look like loop-related utilities. Are you using these in your pass?

In that case you either want to move them to Instruction.h or make them static member of the above classes if these are specific to the algorithm finding reductions.

[rengolin]

include/llvm/Transforms/Utils/LoopUtils.h

45–62

Almost, but I think we can make it be. The only other function that uses it is createMinMaxOp() down there, but it could also be part of this structure/class. Then, moving this enum in there would be trivial. Same goes for ReductionKind and getReductionBinOp().

Internally, using the struct as context on external functions would also work.

123–126

If there are no private members, there isn't much point in making it into a class. But I agree, missing comments.

128–130

These were local functions to the loop vectorizer and loop interchange, and I agree they're very generic. Instruction.h seems like a better place.

[karthikthecool]

Hi All,
Updated the code to address Adam,Renato's comments.
Following are the changes-

1. Moved Enums inside structs.
2. Marked local functions in struct as static.
3. Moved functions inside of ReductionDescriptor.

No functionality change/No Regressions observed.
Please let me know your comments on the same.

Thanks and Regards
Karthik Bhat

[rengolin]

include/llvm/Transforms/Utils/LoopUtils.h

64

Now that these structs are public, we may want to make them classes to hide these implementation details. Same for ReductionDescriptor.

136

Probably most of these functions can be static. Only the ones operating on the internal memebers should be non-static.

151

I don't think this is necessary, just use ReductionKind::RK_IntegerMinMax or even ReductionKind::IntegerMinMax.

lib/Transforms/Vectorize/LoopVectorize.cpp

2714

Keep the comparison with the enum value here.

2727

this should be static function.

[karthikthecool]

Hi Renato,
Thanks for the review. Addressing review comments.
I have made ReductionInstDesc and ReductionDescriptor as class as per your suggestion. Made member variables as private and exposed them through get functions so that they can be used in LoopVectorizer. I hope you are ok with this change?

Thanks for your time and awaiting for your inputs.

Regards
Karthik Bhat

[anemet]

I'll let Renato OK this, but there is one more thing I've noticed. Thanks.

include/llvm/Transforms/Utils/LoopUtils.h

19–21

It does not look like you tried to minimize the included headers by relying on forward decls. See http://llvm.org/docs/CodingStandards.html#include-as-little-as-possible

[karthikthecool]

Hi Adam,
Thanks for the link. It was quite useful. Updated the code to remove redundant #includes.
Please let me know if you have any other comments.
Thanks and Regards
Karthik Bhat

[rengolin]

Hi Karthik,

Thanks for the extended changes, I know it took a while, but it looks a lot better now, thanks!

LGTM.

cheers,
--renato

[karthikthecool]

Thanks Renato. Comitted as r235284.

[karthikthecool]

This has been submitted as r235284.
Not getting an option to close revision hence abondoning it..:(

[rengolin]

The option to close it in the drop-down menu of the comment section. I know, hidden... :)

include/llvm/Transforms/Utils/LoopUtils.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/Dominators.h"
 
 namespace llvm {
 class AliasAnalysis;
 class AliasSet;
 class AliasSetTracker;
 class AssumptionCache;
 class BasicBlock;
 class DataLayout;
 class DominatorTree;
 class Loop;
 class LoopInfo;
 class Pass;
 class PredIteratorCache;
 class ScalarEvolution;
 class TargetLibraryInfo;
 
 /// \brief Captures loop safety information.
 /// It keep information for loop & its header may throw exception.
 struct LICMSafetyInfo {
   bool MayThrow;           // The current loop contains an instruction which
                            // may throw.
   bool HeaderMayThrow;     // Same as previous, but specific to loop header
   LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false)
   {}
 };
 
+/// This enum represents the kinds of reductions that we support.
+enum ReductionKind {
+  RK_NoReduction,   ///< Not a reduction.
+  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_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 reduction.
+enum MinMaxReductionKind {
+  MRK_Invalid,
+  MRK_UIntMin,
+  MRK_UIntMax,
+  MRK_SIntMin,
+  MRK_SIntMax,
+  MRK_FloatMin,
+  MRK_FloatMax
+};
+
+/// This struct holds information about reduction variables.
+struct ReductionDescriptor {
+  ReductionDescriptor()
+      : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoReduction),
+        MinMaxKind(MRK_Invalid) {}
+
+  ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K,
+                      MinMaxReductionKind MK)
+      : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {}
+
+  // The starting value of the reduction.
+  // It does not have to be zero!
+  TrackingVH<Value> StartValue;
+  // The instruction who's value is used outside the loop.
+  Instruction *LoopExitInstr;
+  // The kind of the reduction.
+  ReductionKind Kind;
+  // If this a min/max reduction the kind of reduction.
+  MinMaxReductionKind MinMaxKind;
+};
+
+/// This POD struct holds information about a potential reduction operation.
+struct ReductionInstDesc {
+  ReductionInstDesc(bool IsRedux, Instruction *I)
+      : IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {}
+
+  ReductionInstDesc(Instruction *I, MinMaxReductionKind K)
+      : IsReduction(true), PatternLastInst(I), MinMaxKind(K) {}
+
+  // Is this instruction a reduction candidate.
+  bool IsReduction;
+  // The last instruction in a min/max pattern (select of the select(icmp())
+  // pattern), or the current reduction instruction otherwise.
+  Instruction *PatternLastInst;
+  // If this is a min/max pattern the comparison predicate.
+  MinMaxReductionKind MinMaxKind;
+};
+
+/// 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).
+ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I,
+                                           ReductionInstDesc &Prev);
+
+/// Returns a struct describing if the instruction 'I' can be a reduction
+/// variable of type 'Kind'. If the reduction 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.
+ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind,
+                                   ReductionInstDesc &Prev,
+                                   bool HasFunNoNaNAttr);
+
+bool AddReductionVar(PHINode *Phi, ReductionKind Kind, Loop *TheLoop,
+                     bool HasFunNoNaNAttr, ReductionDescriptor &RedDes);
+
+bool isReductionPHI(PHINode *Phi, Loop *TheLoop, ReductionDescriptor &RedDes);
+
+bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl<Instruction *> &Insts);
+
+bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set);
+
 BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
 
 /// \brief Simplify each loop in a loop nest recursively.
 ///
 /// This takes a potentially un-simplified loop L (and its children) and turns
 /// it into a simplified loop nest with preheaders and single backedges. It
 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
 /// passed into it.
 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
                   AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr,
                   AssumptionCache *AC = nullptr);
 
 /// \brief Put loop into LCSSA form.
 ///
 /// Looks at all instructions in the loop which have uses outside of the
 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
 /// the loop are rewritten to use this node.
 ///
 /// LoopInfo and DominatorTree are required and preserved.
 ///
 /// If ScalarEvolution is passed in, it will be preserved.
 ///
 /// Returns true if any modifications are made to the loop.
 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
                ScalarEvolution *SE = nullptr);
 
 /// \brief Put a loop nest into LCSSA form.
 ///

lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   InlineFunction.cpp
   InstructionNamer.cpp
   IntegerDivision.cpp
   LCSSA.cpp
   Local.cpp
   LoopSimplify.cpp
   LoopUnroll.cpp
   LoopUnrollRuntime.cpp
+  LoopUtils.cpp
   LowerInvoke.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
   MetaRenamer.cpp
   ModuleUtils.cpp
   PromoteMemoryToRegister.cpp
   SSAUpdater.cpp
   SimplifyCFG.cpp

lib/Transforms/Utils/LoopUtils.cpp

+//===-- LoopUtils.cpp - Loop Utility functions -------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines common loop utility functions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/ValueHandle.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Utils/LoopUtils.h"
+
+using namespace llvm;
+using namespace llvm::PatternMatch;
+
+#define DEBUG_TYPE "loop-utils"
+
+bool llvm::areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set) {
+  for (User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
+    if (!Set.count(dyn_cast<Instruction>(*Use)))
+      return false;
+  return true;
+}
+
+bool llvm::AddReductionVar(PHINode *Phi, ReductionKind Kind, Loop *TheLoop,
+                           bool HasFunNoNaNAttr, ReductionDescriptor &RedDes) {
+  if (Phi->getNumIncomingValues() != 2)
+    return false;
+
+  // Reduction variables are only found in the loop header block.
+  if (Phi->getParent() != TheLoop->getHeader())
+    return false;
+
+  // Obtain the reduction start value from the value that comes from the loop
+  // preheader.
+  Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
+
+  // ExitInstruction is the single value which is used outside the loop.
+  // We only allow for a single reduction value to be used outside the loop.
+  // This includes users of the reduction, variables (which form a cycle
+  // which ends in the phi node).
+  Instruction *ExitInstruction = nullptr;
+  // Indicates that we found a reduction operation in our scan.
+  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;
+
+  // 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;
+  ReductionInstDesc ReduxDesc(false, nullptr);
+
+  SmallPtrSet<Instruction *, 8> VisitedInsts;
+  SmallVector<Instruction *, 8> Worklist;
+  Worklist.push_back(Phi);
+  VisitedInsts.insert(Phi);
+
+  // A value in the reduction can be used:
+  //  - By the reduction:
+  //      - Reduction operation:
+  //        - One use of reduction value (safe).
+  //        - Multiple use of reduction value (not safe).
+  //      - PHI:
+  //        - All uses of the PHI must be the reduction (safe).
+  //        - Otherwise, not safe.
+  //  - By one instruction outside of the loop (safe).
+  //  - By further instructions outside of the loop (not safe).
+  //  - By an instruction that is not part of the reduction (not safe).
+  //    This is either:
+  //      * An instruction type other than PHI or the reduction operation.
+  //      * A PHI in the header other than the initial PHI.
+  while (!Worklist.empty()) {
+    Instruction *Cur = Worklist.back();
+    Worklist.pop_back();
+
+    // No Users.
+    // If the instruction has no users then this is a broken chain and can't be
+    // a reduction variable.
+    if (Cur->use_empty())
+      return false;
+
+    bool IsAPhi = isa<PHINode>(Cur);
+
+    // A header PHI use other than the original PHI.
+    if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
+      return false;
+
+    // Reductions of instructions such as Div, and Sub is only possible if the
+    // LHS is the reduction variable.
+    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.
+    ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr);
+    if (!ReduxDesc.IsReduction)
+      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;
+
+    // All inputs to a PHI node must be a reduction value.
+    if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
+      return false;
+
+    if (Kind == RK_IntegerMinMax &&
+        (isa<ICmpInst>(Cur) || isa<SelectInst>(Cur)))
+      ++NumCmpSelectPatternInst;
+    if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || isa<SelectInst>(Cur)))
+      ++NumCmpSelectPatternInst;
+
+    // Check  whether we found a reduction operator.
+    FoundReduxOp |= !IsAPhi;
+
+    // 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);
+
+      // 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)
+          return false;
+
+        // The instruction used by an outside user must be the last instruction
+        // before we feed back to the reduction phi. Otherwise, we loose VF-1
+        // operations on the value.
+        if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end())
+          return false;
+
+        ExitInstruction = Cur;
+        continue;
+      }
+
+      // Process instructions only once (termination). Each reduction cycle
+      // value must only be used once, except by phi nodes and min/max
+      // reductions which are represented as a cmp followed by a select.
+      ReductionInstDesc IgnoredVal(false, nullptr);
+      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).IsReduction))
+        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)
+    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.
+
+  // This instruction is allowed to have out-of-loop users.
+
+  // Save the description of this reduction variable.
+  ReductionDescriptor RD(RdxStart, ExitInstruction, Kind, ReduxDesc.MinMaxKind);
+
+  RedDes = RD;
+
+  return true;
+}
+
+/// 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).
+ReductionInstDesc llvm::isMinMaxSelectCmpPattern(Instruction *I,
+                                                 ReductionInstDesc &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))) {
+    if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
+      return ReductionInstDesc(false, I);
+    return ReductionInstDesc(Select, Prev.MinMaxKind);
+  }
+
+  // Only handle single use cases for now.
+  if (!(Select = dyn_cast<SelectInst>(I)))
+    return ReductionInstDesc(false, I);
+  if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
+      !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
+    return ReductionInstDesc(false, I);
+  if (!Cmp->hasOneUse())
+    return ReductionInstDesc(false, I);
+
+  Value *CmpLeft;
+  Value *CmpRight;
+
+  // Look for a min/max pattern.
+  if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
+    return ReductionInstDesc(Select, MRK_UIntMin);
+  else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
+    return ReductionInstDesc(Select, MRK_UIntMax);
+  else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
+    return ReductionInstDesc(Select, MRK_SIntMax);
+  else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
+    return ReductionInstDesc(Select, MRK_SIntMin);
+  else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
+    return ReductionInstDesc(Select, MRK_FloatMin);
+  else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
+    return ReductionInstDesc(Select, MRK_FloatMax);
+  else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
+    return ReductionInstDesc(Select, MRK_FloatMin);
+  else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
+    return ReductionInstDesc(Select, MRK_FloatMax);
+
+  return ReductionInstDesc(false, I);
+}
+
+ReductionInstDesc llvm::isReductionInstr(Instruction *I, ReductionKind Kind,
+                                         ReductionInstDesc &Prev,
+                                         bool HasFunNoNaNAttr) {
+  bool FP = I->getType()->isFloatingPointTy();
+  bool FastMath = FP && I->hasUnsafeAlgebra();
+  switch (I->getOpcode()) {
+  default:
+    return ReductionInstDesc(false, I);
+  case Instruction::PHI:
+    if (FP &&
+        (Kind != RK_FloatMult && Kind != RK_FloatAdd && Kind != RK_FloatMinMax))
+      return ReductionInstDesc(false, I);
+    return ReductionInstDesc(I, Prev.MinMaxKind);
+  case Instruction::Sub:
+  case Instruction::Add:
+    return ReductionInstDesc(Kind == RK_IntegerAdd, I);
+  case Instruction::Mul:
+    return ReductionInstDesc(Kind == RK_IntegerMult, I);
+  case Instruction::And:
+    return ReductionInstDesc(Kind == RK_IntegerAnd, I);
+  case Instruction::Or:
+    return ReductionInstDesc(Kind == RK_IntegerOr, I);
+  case Instruction::Xor:
+    return ReductionInstDesc(Kind == RK_IntegerXor, I);
+  case Instruction::FMul:
+    return ReductionInstDesc(Kind == RK_FloatMult && FastMath, I);
+  case Instruction::FSub:
+  case Instruction::FAdd:
+    return ReductionInstDesc(Kind == RK_FloatAdd && FastMath, I);
+  case Instruction::FCmp:
+  case Instruction::ICmp:
+  case Instruction::Select:
+    if (Kind != RK_IntegerMinMax &&
+        (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
+      return ReductionInstDesc(false, I);
+    return isMinMaxSelectCmpPattern(I, Prev);
+  }
+}
+
+bool llvm::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 llvm::isReductionPHI(PHINode *Phi, Loop *TheLoop,
+                          ReductionDescriptor &RedDes) {
+
+  bool HasFunNoNaNAttr = false;
+  BasicBlock *Header = TheLoop->getHeader();
+  Function &F = *Header->getParent();
+  if (F.hasFnAttribute("no-nans-fp-math"))
+    HasFunNoNaNAttr =
+        F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true";
+
+  if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
+    DEBUG(dbgs() << "Found an ADD reduction PHI." << *Phi << "\n");
+    return true;
+  }
+  if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
+    DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n");
+    return true;
+  }
+  if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) {
+    DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n");
+    return true;
+  }
+  if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) {
+    DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n");
+    return true;
+  }
+  if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) {
+    DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n");
+    return true;
+  }
+  if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr,
+                      RedDes)) {
+    DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n");
+    return true;
+  }
+  if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) {
+    DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n");
+    return true;
+  }
+  if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) {
+    DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n");
+    return true;
+  }
+  if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) {
+    DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n");
+    return true;
+  }
+  // Not a reduction of known type.
+  return false;
+}

lib/Transforms/Vectorize/LoopVectorize.cpp

public:
   LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
                             TargetLibraryInfo *TLI, AliasAnalysis *AA,
                             Function *F, const TargetTransformInfo *TTI,
                             LoopAccessAnalysis *LAA)
       : NumPredStores(0), TheLoop(L), SE(SE), TLI(TLI), TheFunction(F),
         TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr), Induction(nullptr),
         WidestIndTy(nullptr), HasFunNoNaNAttr(false) {}
 
-  /// This enum represents the kinds of reductions that we support.
-  enum ReductionKind {
-    RK_NoReduction, ///< Not a reduction.
-    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_FloatAdd,    ///< Sum of floats.
-    RK_FloatMult,   ///< Product of floats.
-    RK_FloatMinMax  ///< Min/max implemented in terms of select(cmp()).
-  };
-
   /// This enum represents the kinds of inductions that we support.
   enum InductionKind {
     IK_NoInduction,  ///< Not an induction variable.
     IK_IntInduction, ///< Integer induction variable. Step = C.
     IK_PtrInduction  ///< Pointer induction var. Step = C / sizeof(elem).
   };
 
-  // This enum represents the kind of minmax reduction.
-  enum MinMaxReductionKind {
-    MRK_Invalid,
-    MRK_UIntMin,
-    MRK_UIntMax,
-    MRK_SIntMin,
-    MRK_SIntMax,
-    MRK_FloatMin,
-    MRK_FloatMax
-  };
-
-  /// This struct holds information about reduction variables.
-  struct ReductionDescriptor {
-    ReductionDescriptor() : StartValue(nullptr), LoopExitInstr(nullptr),
-      Kind(RK_NoReduction), MinMaxKind(MRK_Invalid) {}
-
-    ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K,
-                        MinMaxReductionKind MK)
-        : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {}
-
-    // The starting value of the reduction.
-    // It does not have to be zero!
-    TrackingVH<Value> StartValue;
-    // The instruction who's value is used outside the loop.
-    Instruction *LoopExitInstr;
-    // The kind of the reduction.
-    ReductionKind Kind;
-    // If this a min/max reduction the kind of reduction.
-    MinMaxReductionKind MinMaxKind;
-  };
-
-  /// This POD struct holds information about a potential reduction operation.
-  struct ReductionInstDesc {
-    ReductionInstDesc(bool IsRedux, Instruction *I) :
-      IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {}
-
-    ReductionInstDesc(Instruction *I, MinMaxReductionKind K) :
-      IsReduction(true), PatternLastInst(I), MinMaxKind(K) {}
-
-    // Is this instruction a reduction candidate.
-    bool IsReduction;
-    // The last instruction in a min/max pattern (select of the select(icmp())
-    // pattern), or the current reduction instruction otherwise.
-    Instruction *PatternLastInst;
-    // If this is a min/max pattern the comparison predicate.
-    MinMaxReductionKind MinMaxKind;
-  };
-
   /// A struct for saving information about induction variables.
   struct InductionInfo {
     InductionInfo(Value *Start, InductionKind K, ConstantInt *Step)
         : StartValue(Start), IK(K), StepValue(Step) {
       assert(IK != IK_NoInduction && "Not an induction");
       assert(StartValue && "StartValue is null");
       assert(StepValue && !StepValue->isZero() && "StepValue is zero");
       assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) &&
private:
   /// Collect the variables that need to stay uniform after vectorization.
   void collectLoopUniforms();
 
   /// Return true if all of the instructions in the block can be speculatively
   /// executed. \p SafePtrs is a list of addresses that are known to be legal
   /// and we know that we can read from them without segfault.
   bool blockCanBePredicated(BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs);
 
-  /// Returns True, if 'Phi' is the kind of reduction variable for type
-  /// 'Kind'. If this is a reduction variable, it adds it to ReductionList.
-  bool AddReductionVar(PHINode *Phi, ReductionKind Kind);
-  /// Returns a struct describing if the instruction 'I' can be a reduction
-  /// variable of type 'Kind'. If the reduction 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.
-  ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind,
-                                     ReductionInstDesc &Desc);
-  /// 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).
-  static ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I,
-                                                    ReductionInstDesc &Prev);
   /// Returns the induction kind of Phi and record the step. This function may
   /// return NoInduction if the PHI is not an induction variable.
   InductionKind isInductionVariable(PHINode *Phi, ConstantInt *&StepValue);
 
   /// \brief Collect memory access with loop invariant strides.
   ///
   /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop
   /// invariant.
case  RK_FloatAdd:
     // Adding zero to a number does not change it.
     return ConstantFP::get(Tp, 0.0L);
   default:
     llvm_unreachable("Unknown reduction kind");
   }
 }
 
 /// This function translates the reduction kind to an LLVM binary operator.
-static unsigned
-getReductionBinOp(LoopVectorizationLegality::ReductionKind Kind) {
+static unsigned getReductionBinOp(ReductionKind Kind) {
   switch (Kind) {
-    case LoopVectorizationLegality::RK_IntegerAdd:
+  case RK_IntegerAdd:
       return Instruction::Add;
-    case LoopVectorizationLegality::RK_IntegerMult:
+  case RK_IntegerMult:
       return Instruction::Mul;
-    case LoopVectorizationLegality::RK_IntegerOr:
+  case RK_IntegerOr:
       return Instruction::Or;
-    case LoopVectorizationLegality::RK_IntegerAnd:
+  case RK_IntegerAnd:
       return Instruction::And;
-    case LoopVectorizationLegality::RK_IntegerXor:
+  case RK_IntegerXor:
       return Instruction::Xor;
-    case LoopVectorizationLegality::RK_FloatMult:
+  case RK_FloatMult:
       return Instruction::FMul;
-    case LoopVectorizationLegality::RK_FloatAdd:
+  case RK_FloatAdd:
       return Instruction::FAdd;
-    case LoopVectorizationLegality::RK_IntegerMinMax:
+  case RK_IntegerMinMax:
       return Instruction::ICmp;
-    case LoopVectorizationLegality::RK_FloatMinMax:
+  case RK_FloatMinMax:
       return Instruction::FCmp;
     default:
       llvm_unreachable("Unknown reduction operation");
   }
 }
 
-static Value *createMinMaxOp(IRBuilder<> &Builder,
-                             LoopVectorizationLegality::MinMaxReductionKind RK,
+static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxReductionKind RK,
                              Value *Left, Value *Right) {
   CmpInst::Predicate P = CmpInst::ICMP_NE;
   switch (RK) {
   default:
     llvm_unreachable("Unknown min/max reduction kind");
-  case LoopVectorizationLegality::MRK_UIntMin:
+  case MRK_UIntMin:
     P = CmpInst::ICMP_ULT;
     break;
-  case LoopVectorizationLegality::MRK_UIntMax:
+  case MRK_UIntMax:
     P = CmpInst::ICMP_UGT;
     break;
-  case LoopVectorizationLegality::MRK_SIntMin:
+  case MRK_SIntMin:
     P = CmpInst::ICMP_SLT;
     break;
-  case LoopVectorizationLegality::MRK_SIntMax:
+  case MRK_SIntMax:
     P = CmpInst::ICMP_SGT;
     break;
-  case LoopVectorizationLegality::MRK_FloatMin:
+  case MRK_FloatMin:
     P = CmpInst::FCMP_OLT;
     break;
-  case LoopVectorizationLegality::MRK_FloatMax:
+  case MRK_FloatMax:
     P = CmpInst::FCMP_OGT;
     break;
   }
 
   Value *Cmp;
-  if (RK == LoopVectorizationLegality::MRK_FloatMin ||
-      RK == LoopVectorizationLegality::MRK_FloatMax)
+  if (RK == MRK_FloatMin || RK == MRK_FloatMax)
     Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp");
   else
     Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp");
 
   Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select");
   return Select;
 }
 
void InnerLoopVectorizer::vectorizeLoop() {
   for (PhiVector::iterator it = RdxPHIsToFix.begin(), e = RdxPHIsToFix.end();
        it != e; ++it) {
     PHINode *RdxPhi = *it;
     assert(RdxPhi && "Unable to recover vectorized PHI");
 
     // Find the reduction variable descriptor.
     assert(Legal->getReductionVars()->count(RdxPhi) &&
            "Unable to find the reduction variable");
-    LoopVectorizationLegality::ReductionDescriptor RdxDesc =
-    (*Legal->getReductionVars())[RdxPhi];
+    ReductionDescriptor RdxDesc = (*Legal->getReductionVars())[RdxPhi];
 
     setDebugLocFromInst(Builder, RdxDesc.StartValue);
 
     // We need to generate a reduction vector from the incoming scalar.
     // To do so, we need to generate the 'identity' vector and override
     // one of the elements with the incoming scalar reduction. We need
     // to do it in the vector-loop preheader.
     Builder.SetInsertPoint(LoopBypassBlocks[1]->getTerminator());
 
     // This is the vector-clone of the value that leaves the loop.
     VectorParts &VectorExit = getVectorValue(RdxDesc.LoopExitInstr);
     Type *VecTy = VectorExit[0]->getType();
 
     // Find the reduction identity variable. Zero for addition, or, xor,
     // one for multiplication, -1 for And.
     Value *Identity;
     Value *VectorStart;
-    if (RdxDesc.Kind == LoopVectorizationLegality::RK_IntegerMinMax ||
-        RdxDesc.Kind == LoopVectorizationLegality::RK_FloatMinMax) {
+    if (RdxDesc.Kind == RK_IntegerMinMax || RdxDesc.Kind == RK_FloatMinMax) {
       // MinMax reduction have the start value as their identify.
       if (VF == 1) {
         VectorStart = Identity = RdxDesc.StartValue;
       } else {
         VectorStart = Identity = Builder.CreateVectorSplat(VF,
                                                            RdxDesc.StartValue,
                                                            "minmax.ident");
       }
     } else {
       // Handle other reduction kinds:
       Constant *Iden =
       LoopVectorizationLegality::getReductionIdentity(RdxDesc.Kind,
                                                       VecTy->getScalarType());
       if (VF == 1) {
         Identity = Iden;
         // This vector is the Identity vector where the first element is the
         // incoming scalar reduction.
         VectorStart = RdxDesc.StartValue;
       } else {
         Identity = ConstantVector::getSplat(VF, Iden);
 
for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
             emitAnalysis(VectorizationReport(it) <<
                          "use of induction value outside of the "
                          "loop is not handled by vectorizer");
             return false;
           }
 
           continue;
         }
-
-        if (AddReductionVar(Phi, RK_IntegerAdd)) {
-          DEBUG(dbgs() << "LV: Found an ADD reduction PHI."<< *Phi <<"\n");
-          continue;
-        }
-        if (AddReductionVar(Phi, RK_IntegerMult)) {
-          DEBUG(dbgs() << "LV: Found a MUL reduction PHI."<< *Phi <<"\n");
-          continue;
-        }
-        if (AddReductionVar(Phi, RK_IntegerOr)) {
-          DEBUG(dbgs() << "LV: Found an OR reduction PHI."<< *Phi <<"\n");
-          continue;
-        }
-        if (AddReductionVar(Phi, RK_IntegerAnd)) {
-          DEBUG(dbgs() << "LV: Found an AND reduction PHI."<< *Phi <<"\n");
-          continue;
-        }
-        if (AddReductionVar(Phi, RK_IntegerXor)) {
-          DEBUG(dbgs() << "LV: Found a XOR reduction PHI."<< *Phi <<"\n");
-          continue;
-        }
-        if (AddReductionVar(Phi, RK_IntegerMinMax)) {
-          DEBUG(dbgs() << "LV: Found a MINMAX reduction PHI."<< *Phi <<"\n");
-          continue;
-        }
-        if (AddReductionVar(Phi, RK_FloatMult)) {
-          DEBUG(dbgs() << "LV: Found an FMult reduction PHI."<< *Phi <<"\n");
-          continue;
-        }
-        if (AddReductionVar(Phi, RK_FloatAdd)) {
-          DEBUG(dbgs() << "LV: Found an FAdd reduction PHI."<< *Phi <<"\n");
-          continue;
-        }
-        if (AddReductionVar(Phi, RK_FloatMinMax)) {
-          DEBUG(dbgs() << "LV: Found an float MINMAX reduction PHI."<< *Phi <<
-                "\n");
+        if (isReductionPHI(Phi, TheLoop, Reductions[Phi])) {
+          AllowedExit.insert(Reductions[Phi].LoopExitInstr);
           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;
emitAnalysis(VectorizationReport()
                  << VectorizerParams::RuntimeMemoryCheckThreshold
                  << " dependent memory operations checked at runtime");
     DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
     return false;
   }
   return true;
 }
 
-static bool 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;
-}
-
-static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl<Instruction *> &Set) {
-  for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use)
-    if (!Set.count(dyn_cast<Instruction>(*Use)))
-      return false;
-  return true;
-}
-
-bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi,
-                                                ReductionKind Kind) {
-  if (Phi->getNumIncomingValues() != 2)
-    return false;
-
-  // Reduction variables are only found in the loop header block.
-  if (Phi->getParent() != TheLoop->getHeader())
-    return false;
-
-  // Obtain the reduction start value from the value that comes from the loop
-  // preheader.
-  Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader());
-
-  // ExitInstruction is the single value which is used outside the loop.
-  // We only allow for a single reduction value to be used outside the loop.
-  // This includes users of the reduction, variables (which form a cycle
-  // which ends in the phi node).
-  Instruction *ExitInstruction = nullptr;
-  // Indicates that we found a reduction operation in our scan.
-  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;
-
-  // 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;
-  ReductionInstDesc ReduxDesc(false, nullptr);
-
-  SmallPtrSet<Instruction *, 8> VisitedInsts;
-  SmallVector<Instruction *, 8> Worklist;
-  Worklist.push_back(Phi);
-  VisitedInsts.insert(Phi);
-
-  // A value in the reduction can be used:
-  //  - By the reduction:
-  //      - Reduction operation:
-  //        - One use of reduction value (safe).
-  //        - Multiple use of reduction value (not safe).
-  //      - PHI:
-  //        - All uses of the PHI must be the reduction (safe).
-  //        - Otherwise, not safe.
-  //  - By one instruction outside of the loop (safe).
-  //  - By further instructions outside of the loop (not safe).
-  //  - By an instruction that is not part of the reduction (not safe).
-  //    This is either:
-  //      * An instruction type other than PHI or the reduction operation.
-  //      * A PHI in the header other than the initial PHI.
-  while (!Worklist.empty()) {
-    Instruction *Cur = Worklist.back();
-    Worklist.pop_back();
-
-    // No Users.
-    // If the instruction has no users then this is a broken chain and can't be
-    // a reduction variable.
-    if (Cur->use_empty())
-      return false;
-
-    bool IsAPhi = isa<PHINode>(Cur);
-
-    // A header PHI use other than the original PHI.
-    if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent())
-      return false;
-
-    // Reductions of instructions such as Div, and Sub is only possible if the
-    // LHS is the reduction variable.
-    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.
-    ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc);
-    if (!ReduxDesc.IsReduction)
-      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;
-
-    // All inputs to a PHI node must be a reduction value.
-    if(IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts))
-      return false;
-
-    if (Kind == RK_IntegerMinMax && (isa<ICmpInst>(Cur) ||
-                                     isa<SelectInst>(Cur)))
-      ++NumCmpSelectPatternInst;
-    if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) ||
-                                   isa<SelectInst>(Cur)))
-      ++NumCmpSelectPatternInst;
-
-    // Check  whether we found a reduction operator.
-    FoundReduxOp |= !IsAPhi;
-
-    // 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);
-
-      // 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)
-          return false;
-
-        // The instruction used by an outside user must be the last instruction
-        // before we feed back to the reduction phi. Otherwise, we loose VF-1
-        // operations on the value.
-        if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end())
-         return false;
-
-        ExitInstruction = Cur;
-        continue;
-      }
-
-      // Process instructions only once (termination). Each reduction cycle
-      // value must only be used once, except by phi nodes and min/max
-      // reductions which are represented as a cmp followed by a select.
-      ReductionInstDesc IgnoredVal(false, nullptr);
-      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).IsReduction))
-        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)
-    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.
-
-  // This instruction is allowed to have out-of-loop users.
-  AllowedExit.insert(ExitInstruction);
-
-  // Save the description of this reduction variable.
-  ReductionDescriptor RD(RdxStart, ExitInstruction, Kind,
-                         ReduxDesc.MinMaxKind);
-  Reductions[Phi] = RD;
-  // We've ended the cycle. This is a reduction variable if we have an
-  // outside user and it has a binary op.
-
-  return true;
-}
-
-/// 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).
-LoopVectorizationLegality::ReductionInstDesc
-LoopVectorizationLegality::isMinMaxSelectCmpPattern(Instruction *I,
-                                                    ReductionInstDesc &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))) {
-    if (!Cmp->hasOneUse() || !(Select = dyn_cast<SelectInst>(*I->user_begin())))
-      return ReductionInstDesc(false, I);
-    return ReductionInstDesc(Select, Prev.MinMaxKind);
-  }
-
-  // Only handle single use cases for now.
-  if (!(Select = dyn_cast<SelectInst>(I)))
-    return ReductionInstDesc(false, I);
-  if (!(Cmp = dyn_cast<ICmpInst>(I->getOperand(0))) &&
-      !(Cmp = dyn_cast<FCmpInst>(I->getOperand(0))))
-    return ReductionInstDesc(false, I);
-  if (!Cmp->hasOneUse())
-    return ReductionInstDesc(false, I);
-
-  Value *CmpLeft;
-  Value *CmpRight;
-
-  // Look for a min/max pattern.
-  if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
-    return ReductionInstDesc(Select, MRK_UIntMin);
-  else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
-    return ReductionInstDesc(Select, MRK_UIntMax);
-  else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
-    return ReductionInstDesc(Select, MRK_SIntMax);
-  else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
-    return ReductionInstDesc(Select, MRK_SIntMin);
-  else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
-    return ReductionInstDesc(Select, MRK_FloatMin);
-  else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
-    return ReductionInstDesc(Select, MRK_FloatMax);
-  else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
-    return ReductionInstDesc(Select, MRK_FloatMin);
-  else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select))
-    return ReductionInstDesc(Select, MRK_FloatMax);
-
-  return ReductionInstDesc(false, I);
-}
-
-LoopVectorizationLegality::ReductionInstDesc
-LoopVectorizationLegality::isReductionInstr(Instruction *I,
-                                            ReductionKind Kind,
-                                            ReductionInstDesc &Prev) {
-  bool FP = I->getType()->isFloatingPointTy();
-  bool FastMath = FP && I->hasUnsafeAlgebra();
-  switch (I->getOpcode()) {
-  default:
-    return ReductionInstDesc(false, I);
-  case Instruction::PHI:
-      if (FP && (Kind != RK_FloatMult && Kind != RK_FloatAdd &&
-                 Kind != RK_FloatMinMax))
-        return ReductionInstDesc(false, I);
-    return ReductionInstDesc(I, Prev.MinMaxKind);
-  case Instruction::Sub:
-  case Instruction::Add:
-    return ReductionInstDesc(Kind == RK_IntegerAdd, I);
-  case Instruction::Mul:
-    return ReductionInstDesc(Kind == RK_IntegerMult, I);
-  case Instruction::And:
-    return ReductionInstDesc(Kind == RK_IntegerAnd, I);
-  case Instruction::Or:
-    return ReductionInstDesc(Kind == RK_IntegerOr, I);
-  case Instruction::Xor:
-    return ReductionInstDesc(Kind == RK_IntegerXor, I);
-  case Instruction::FMul:
-    return ReductionInstDesc(Kind == RK_FloatMult && FastMath, I);
-  case Instruction::FSub:
-  case Instruction::FAdd:
-    return ReductionInstDesc(Kind == RK_FloatAdd && FastMath, I);
-  case Instruction::FCmp:
-  case Instruction::ICmp:
-  case Instruction::Select:
-    if (Kind != RK_IntegerMinMax &&
-        (!HasFunNoNaNAttr || Kind != RK_FloatMinMax))
-      return ReductionInstDesc(false, I);
-    return isMinMaxSelectCmpPattern(I, Prev);
-  }
-}
-
 bool llvm::isInductionPHI(PHINode *Phi, ScalarEvolution *SE,
                           ConstantInt *&StepValue) {
   Type *PhiTy = Phi->getType();
   // We only handle integer and pointer inductions variables.
   if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy())
     return false;
 
   // Check that the PHI is consecutive.