[SLP] Initial rework for min/max horizontal reduction vectorization, NFC.

[ABataev]

Summary

All getReductionCost() functions are renamed to getArithmeticReductionCost() + added basic infrastructure to handle non-binary reduction operations.

[mkuper]

lib/Analysis/CostModel.cpp

196

Can this ever be a Value that's not an Instruction?
(Same question applies to getReductionOpcode())

lib/Transforms/Vectorize/SLPVectorizer.cpp

4094

This basically complements the change in line 4803 - 4823, right, but taken together, those two changes are NFC, regardless of everything else here, right? Or am I confused and this depends on something else?

4197

This part of the change is completely orthogonal to the name change and using matchers, right?

Anyway, I think I see where this is going. This is possibly similar to what Ayal, Gil & company are doing for LV, in terms of recipes?
Adding them to take a look.

4198

What does being valid mean in this context? Just that this is a "non-null handle"

4245

only adds at this point. :-)
Also, if you're checking the op here, I'd expect a check of isAssociative() as well.

4249

So, by "of the same kind" you mean "both a reduction op or both a reduced value", which is something you determine by either both LHS/RHS being null, or both being non-null?
Can you please be more explicit about this? Also, maybe it's worth having an explicit flag for this, instead of relying on LHS and RHS being null?

4271

I've cleaned this up in the existing code, there's no need to special-case FAdd, you can just CreateBinOp for it.

[ABataev]

Update after review

[Ayal]

lib/Analysis/CostModel.cpp

211

Can PatternMatch be put to more use, by asking it to match a BinOp whose L and R sides are both shuffles, when Level > 0?

Passing L and R by reference here saves little compared to the original direct calls to getOperand(0) and getOperand(1), and seems mostly redundant elsewhere.

404

Check if RdxOp, or use cast instead of dyn_cast?

lib/Transforms/Vectorize/SLPVectorizer.cpp

4094

V is-surely-a<BinaryOperator>, being a non-nullptr to BinaryOperator, right?

[ABataev]

lib/Analysis/CostModel.cpp

196

Of course no, only instructions can be used here. I'll convert these params to Instruction *.

211

This is just an initial patch. In future it will be extended with support of min/max patterns, that's why this kind of recognition of LHS/RHS operands is placed in function. Another thing, that it will be better just to return the record of opcode + LHS/RHS parts, rather than pass L/R by reference.

404

Yes, missed this, thanks. Will fix.

lib/Transforms/Vectorize/SLPVectorizer.cpp

4094

Yes, you're right, I'll remove these changes from this patch and prepare another one for CmpInsts.

4094

Yes, forgot to change type of parameter, will do it

4197

No, actually it is basic infrastructure for supporting horizontal reduction vectorization of not-BinOp instructions. It does not change the functionality, but allows later easily to support vectorization of other complex instructions, like min/max.

4198

Will try to remove it

4245

Yes, will fix this.
isAssociative() requires actual instruction instead of Opcode only, that's why I did not check it here.

4249

Yes, it is exactly what I meant.
Ok, will think about it.

4271

Ok, will fix it.

[Ayal]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4213

Should IsReducedValue be set to false here?

4249

The IsReducedValue explicit flag indicates if its a reduction op or reduced value, right?

To implement the behavior documented above: "Checks if two operation data are both a reduction op or both a reduced value", it's enough to have the "IsReducedValue == OD.IsReducedValue" part.

4267

re[d]uction

[ABataev]

Update after review

[ABataev]

Ping

[Ayal]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4094

I must be missing something here; tryToVectorize() is still being fed by BinaryOperator*, right? Wondering why the parameter type change. Better include this change in follow-up patch which tries to vectorize non BinaryOperators, if that's the intention.

4196

"+ validity" should be removed?

4219

Still a couple of "if (x.Opcode == 0)" cases, may as well make use of this bool().

4245

isVectorizable() is used only in conjuction with isAssociative(I), and as an assert when getOpcode() is called by getReductionCost(). Isn't it better to have isVectorizable(I) also call isAssociative?

4249

It sounds like you can

assert ((IsReducedValue != OD.IsReducedValue) || ((!LHS == !OD.LHS) && (!RHS == !OD.RHS) && Opcode == OD.Opcode) && "message");

no need to actually check them all to return true, right?

4267

typo

4269

Every other method fits with the passive, storage-type "OperationData" name of this struct, but this last method may look a bit odd doing "OperationData.createOp()". All that it's contributing is its Opcode which it can provide, and some asserts. Is there a better way of keeping OperationData's nature, or a better name for it?

4745

Not sure why you wanted this change; but how about simply "if (isa<BinaryOperator>(Inst))"?

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4094

Restored back.

4196

Removed

4219

Tried to replace all

4245

Added isVectorized(Instruction *I)

4249

Modified it a bit, still need to compare the opcode

4267

Yes, thanks, fixed

4269

Modified this method, now it accepts only Builder and optional name

4745

Restored it

[ABataev]

Update after review

[anemet]

lib/Analysis/CostModel.cpp

189

Contains

[RKSimon]

Some minor style comments

lib/Analysis/CostModel.cpp

202

No need to initialize these.

Value *L, *R;

204

Use the ReductionData constructor for clarity?

lib/Transforms/Vectorize/SLPVectorizer.cpp

4228

?

4233

Add assert message

4238

Add assert message

4243

Add assert message

4302

Use OperationData constructor for clarity

4305

Add assert message

[RKSimon]

@ABataev You marked a lot of the comments done but haven't updated the diff.

[ABataev]

Update after review.

[RKSimon]

A couple of NFC changes that will reduce this patch.

include/llvm/CodeGen/BasicTTIImpl.h

993

You should probably move this comment (unchanged) as a NFC commit right away to reduce the patch. I can't tell if you've changed anything.

include/llvm/Transforms/Vectorize/SLPVectorizer.h

85

Do this as an NFC commit now - its a tidyup that isn't relevant to the patch.

[ABataev]

Update to trunk

[RKSimon]

What's happening with this? It seems almost ready to go.

lib/Analysis/CostModel.cpp

196

Still not Instruction*

200

Worth making this an Optional<> instead of relying on Opcode == 0?

[ABataev]

lib/Analysis/CostModel.cpp

196

Investigated this problem once again, it maybe not of Instruction type, for example, it may be an Argument. So, we have to use Value * here.

200

Ok, will do

[ABataev]

Update after review

[RKSimon]

There's still a lot going on in this patch but it looks alright to me (I noticed one minor).

Does anyone have any further comments?

lib/Transforms/Vectorize/SLPVectorizer.cpp

4213

If OperationData is a struct then this public can go?

[avt77]

Could we split it on 2 sub-parts:

1 - rename (maybe NFC?)
2 - new infrastructure

In this case it will be easier and smaller.

[RKSimon]

LGTM - if possible please commit the getArithmeticReductionCost rename as a separate pre-commit.

include/llvm/Analysis/TargetTransformInfo.h

public:
   /// at every reduction level.
   ///
   /// Pairwise:
   ///  (v0, v1, v2, v3)
   ///  ((v0+v1), (v2, v3), undef, undef)
   /// Split:
   ///  (v0, v1, v2, v3)
   ///  ((v0+v2), (v1+v3), undef, undef)
-  int getReductionCost(unsigned Opcode, Type *Ty, bool IsPairwiseForm) const;
+  int getArithmeticReductionCost(unsigned Opcode, Type *Ty,
+                                 bool IsPairwiseForm) const;
 
   /// \returns The cost of Intrinsic instructions. Types analysis only.
   int getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                             ArrayRef<Type *> Tys, FastMathFlags FMF) const;
 
   /// \returns The cost of Intrinsic instructions. Analyses the real arguments.
   int getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                             ArrayRef<Value *> Args, FastMathFlags FMF) const;
public:
   virtual int getGatherScatterOpCost(unsigned Opcode, Type *DataTy,
                                      Value *Ptr, bool VariableMask,
                                      unsigned Alignment) = 0;
   virtual int getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy,
                                          unsigned Factor,
                                          ArrayRef<unsigned> Indices,
                                          unsigned Alignment,
                                          unsigned AddressSpace) = 0;
-  virtual int getReductionCost(unsigned Opcode, Type *Ty,
+  virtual int getArithmeticReductionCost(unsigned Opcode, Type *Ty,
                                          bool IsPairwiseForm) = 0;
   virtual int getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                                     ArrayRef<Type *> Tys,
                                     FastMathFlags FMF) = 0;
   virtual int getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                                     ArrayRef<Value *> Args,
                                     FastMathFlags FMF) = 0;
   virtual int getCallInstrCost(Function *F, Type *RetTy,
                                ArrayRef<Type *> Tys) = 0;
return Impl.getGatherScatterOpCost(Opcode, DataTy, Ptr, VariableMask,
                                        Alignment);
   }
   int getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy, unsigned Factor,
                                  ArrayRef<unsigned> Indices, unsigned Alignment,
                                  unsigned AddressSpace) override {
     return Impl.getInterleavedMemoryOpCost(Opcode, VecTy, Factor, Indices,
                                            Alignment, AddressSpace);
   }
-  int getReductionCost(unsigned Opcode, Type *Ty,
+  int getArithmeticReductionCost(unsigned Opcode, Type *Ty,
                                  bool IsPairwiseForm) override {
-    return Impl.getReductionCost(Opcode, Ty, IsPairwiseForm);
+    return Impl.getArithmeticReductionCost(Opcode, Ty, IsPairwiseForm);
   }
   int getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy, ArrayRef<Type *> Tys,
                             FastMathFlags FMF) override {
     return Impl.getIntrinsicInstrCost(ID, RetTy, Tys, FMF);
   }
   int getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy,
                             ArrayRef<Value *> Args,
                             FastMathFlags FMF) override {

include/llvm/Analysis/TargetTransformInfoImpl.h

public:
 
   unsigned getNumberOfParts(Type *Tp) { return 0; }
 
   unsigned getAddressComputationCost(Type *Tp, ScalarEvolution *,
                                      const SCEV *) {
     return 0; 
   }
 
-  unsigned getReductionCost(unsigned, Type *, bool) { return 1; }
+  unsigned getArithmeticReductionCost(unsigned, Type *, bool) { return 1; }
 
   unsigned getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) { return 0; }
 
   bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info) {
     return false;
   }
 
   Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,

include/llvm/CodeGen/BasicTTIImpl.h

unsigned getNumberOfParts(Type *Tp) {
     return LT.first;
   }
 
   unsigned getAddressComputationCost(Type *Ty, ScalarEvolution *,
                                      const SCEV *) {
     return 0; 
   }
 
-  unsigned getReductionCost(unsigned Opcode, Type *Ty, bool IsPairwise) {
+  /// Try to calculate arithmetic and shuffle op costs for reduction operations.
+  /// We're assuming that reduction operation are performing the following way:
+  /// 1. Non-pairwise reduction
+  /// %val1 = shufflevector<n x t> %val, <n x t> %undef,
+  /// <n x i32> <i32 n/2, i32 n/2 + 1, ..., i32 n, i32 undef, ..., i32 undef>
+  ///            \----------------v-------------/  \----------v------------/
+  ///                            n/2 elements               n/2 elements
+  /// %red1 = op <n x t> %val, <n x t> val1
+  /// After this operation we have a vector %red1 where only the first n/2
+  /// elements are meaningful, the second n/2 elements are undefined and can be
+  /// dropped. All other operations are actually working with the vector of
+  /// length n/2, not n, though the real vector length is still n.
+  /// %val2 = shufflevector<n x t> %red1, <n x t> %undef,
+  /// <n x i32> <i32 n/4, i32 n/4 + 1, ..., i32 n/2, i32 undef, ..., i32 undef>
+  ///            \----------------v-------------/  \----------v------------/
+  ///                            n/4 elements               3*n/4 elements
+  /// %red2 = op <n x t> %red1, <n x t> val2  - working with the vector of
+  /// length n/2, the resulting vector has length n/4 etc.
+  /// 2. Pairwise reduction:
+  /// Everything is the same except for an additional shuffle operation which
+  /// is used to produce operands for pairwise kind of reductions.
+  /// %val1 = shufflevector<n x t> %val, <n x t> %undef,
+  /// <n x i32> <i32 0, i32 2, ..., i32 n-2, i32 undef, ..., i32 undef>
+  ///            \-------------v----------/  \----------v------------/
+  ///                   n/2 elements               n/2 elements
+  /// %val2 = shufflevector<n x t> %val, <n x t> %undef,
+  /// <n x i32> <i32 1, i32 3, ..., i32 n-1, i32 undef, ..., i32 undef>
+  ///            \-------------v----------/  \----------v------------/
+  ///                   n/2 elements               n/2 elements
+  /// %red1 = op <n x t> %val1, <n x t> val2
+  /// Again, the operation is performed on <n x t> vector, but the resulting
+  /// vector %red1 is <n/2 x t> vector.
+  ///
+  /// The cost model should take into account that the actual length of the
+  /// vector is reduced on each iteration.
+  unsigned getArithmeticReductionCost(unsigned Opcode, Type *Ty,
+                                      bool IsPairwise) {
     assert(Ty->isVectorTy() && "Expect a vector type");
     Type *ScalarTy = Ty->getVectorElementType();
     unsigned NumVecElts = Ty->getVectorNumElements();
     unsigned NumReduxLevels = Log2_32(NumVecElts);
-    // Try to calculate arithmetic and shuffle op costs for reduction operations.
-    // We're assuming that reduction operation are performing the following way:
-    // 1. Non-pairwise reduction
-    // %val1 = shufflevector<n x t> %val, <n x t> %undef,
-    // <n x i32> <i32 n/2, i32 n/2 + 1, ..., i32 n, i32 undef, ..., i32 undef>
-    //            \----------------v-------------/  \----------v------------/
-    //                            n/2 elements               n/2 elements
-    // %red1 = op <n x t> %val, <n x t> val1
-    // After this operation we have a vector %red1 with only maningfull the
-    // first n/2 elements, the second n/2 elements are undefined and can be
-    // dropped. All other operations are actually working with the vector of
-    // length n/2, not n. though the real vector length is still n.
-    // %val2 = shufflevector<n x t> %red1, <n x t> %undef,
-    // <n x i32> <i32 n/4, i32 n/4 + 1, ..., i32 n/2, i32 undef, ..., i32 undef>
-    //            \----------------v-------------/  \----------v------------/
-    //                            n/4 elements               3*n/4 elements
-    // %red2 = op <n x t> %red1, <n x t> val2  - working with the vector of
-    // length n/2, the resulting vector has length n/4 etc.
-    // 2. Pairwise reduction:
-    // Everything is the same except for an additional shuffle operation which
-    // is used to produce operands for pairwise kind of reductions.
-    // %val1 = shufflevector<n x t> %val, <n x t> %undef,
-    // <n x i32> <i32 0, i32 2, ..., i32 n-2, i32 undef, ..., i32 undef>
-    //            \-------------v----------/  \----------v------------/
-    //                   n/2 elements               n/2 elements
-    // %val2 = shufflevector<n x t> %val, <n x t> %undef,
-    // <n x i32> <i32 1, i32 3, ..., i32 n-1, i32 undef, ..., i32 undef>
-    //            \-------------v----------/  \----------v------------/
-    //                   n/2 elements               n/2 elements
-    // %red1 = op <n x t> %val1, <n x t> val2
-    // Again, the operation is performed on <n x t> vector, but the resulting
-    // vector %red1 is <n/2 x t> vector.
-    //
-    // The cost model should take into account that the actual length of the
-    // vector is reduced on each iteration.
     unsigned ArithCost = 0;
     unsigned ShuffleCost = 0;
     auto *ConcreteTTI = static_cast<T *>(this);
     std::pair<unsigned, MVT> LT =
         ConcreteTTI->getTLI()->getTypeLegalizationCost(DL, Ty);
     unsigned LongVectorCount = 0;
     unsigned MVTLen =
         LT.second.isVector() ? LT.second.getVectorNumElements() : 1;

include/llvm/Transforms/Vectorize/SLPVectorizer.h

private:
   /// \brief Try to vectorize a list of operands.
   /// \@param BuildVector A list of users to ignore for the purpose of
   ///                     scheduling and that don't need extracting.
   /// \returns true if a value was vectorized.
   bool tryToVectorizeList(ArrayRef<Value *> VL, slpvectorizer::BoUpSLP &R,
                           ArrayRef<Value *> BuildVector = None,
                           bool AllowReorder = false);
 
   /// \brief Try to vectorize a chain that may start at the operands of \V;
-  bool tryToVectorize(BinaryOperator *V, slpvectorizer::BoUpSLP &R);
+  bool tryToVectorize(Instruction *I, slpvectorizer::BoUpSLP &R);
 
   /// \brief Vectorize the store instructions collected in Stores.
   bool vectorizeStoreChains(slpvectorizer::BoUpSLP &R);
 
   /// \brief Vectorize the index computations of the getelementptr instructions
   /// collected in GEPs.
   bool vectorizeGEPIndices(BasicBlock *BB, slpvectorizer::BoUpSLP &R);
 

lib/Analysis/CostModel.cpp

 
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/Passes.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
+using namespace PatternMatch;
 
 #define CM_NAME "cost-model"
 #define DEBUG_TYPE CM_NAME
 
 static cl::opt<bool> EnableReduxCost("costmodel-reduxcost", cl::init(false),
                                      cl::Hidden,
                                      cl::desc("Recognize reduction patterns."));
 
static bool matchPairwiseShuffleMask(ShuffleVectorInst *SI, bool IsLeft,
   // we look at the left or right side.
   for (unsigned i = 0, e = (1 << Level), val = !IsLeft; i != e; ++i, val += 2)
     Mask[i] = val;
 
   SmallVector<int, 16> ActualMask = SI->getShuffleMask();
   return Mask == ActualMask;
 }
 
-static bool matchPairwiseReductionAtLevel(const BinaryOperator *BinOp,
-                                          unsigned Level, unsigned NumLevels) {
+static unsigned getReductionOpcode(Value *V, Value *&L, Value *&R) {
+  L = nullptr;
+  R = nullptr;
+  if (m_BinOp(m_Value(L), m_Value(R)).match(V))
+    return cast<BinaryOperator>(V)->getOpcode();
+  return 0;
+}
+
+static bool matchPairwiseReductionAtLevel(Value *V, unsigned Level,
+                                          unsigned NumLevels) {
   // Match one level of pairwise operations.
   // %rdx.shuf.0.0 = shufflevector <4 x float> %rdx, <4 x float> undef,
   //       <4 x i32> <i32 0, i32 2 , i32 undef, i32 undef>
   // %rdx.shuf.0.1 = shufflevector <4 x float> %rdx, <4 x float> undef,
   //       <4 x i32> <i32 1, i32 3, i32 undef, i32 undef>
   // %bin.rdx.0 = fadd <4 x float> %rdx.shuf.0.0, %rdx.shuf.0.1
-  if (BinOp == nullptr)
+  if (!V)
     return false;
 
-  assert(BinOp->getType()->isVectorTy() && "Expecting a vector type");
+  assert(V->getType()->isVectorTy() && "Expecting a vector type");
 
-  unsigned Opcode = BinOp->getOpcode();
-  Value *L = BinOp->getOperand(0);
-  Value *R = BinOp->getOperand(1);
+  Value *L;
+  Value *R;
+  unsigned Opcode = getReductionOpcode(V, L, R);
+  if (!Opcode)
+    return false;
 
   ShuffleVectorInst *LS = dyn_cast<ShuffleVectorInst>(L);
   if (!LS && Level)
     return false;
   ShuffleVectorInst *RS = dyn_cast<ShuffleVectorInst>(R);
   if (!RS && Level)
     return false;
 
else if (NextLevelOpR && NextLevelOpR != L)
       return false;
 
     NextLevelOp = NextLevelOpL ? R : L;
   } else
     return false;
 
   // Check that the next levels binary operation exists and matches with the
   // current one.
-  BinaryOperator *NextLevelBinOp = nullptr;
-  if (Level + 1 != NumLevels) {
-    if (!(NextLevelBinOp = dyn_cast<BinaryOperator>(NextLevelOp)))
+  if (Level + 1 != NumLevels)
+    if (Opcode != getReductionOpcode(NextLevelOp, L, R))
       return false;
-    else if (NextLevelBinOp->getOpcode() != Opcode)
-      return false;
-  }
 
   // Shuffle mask for pairwise operation must match.
-  if (matchPairwiseShuffleMask(LS, true, Level)) {
-    if (!matchPairwiseShuffleMask(RS, false, Level))
+  if (matchPairwiseShuffleMask(LS, /*IsLeft=*/true, Level)) {
+    if (!matchPairwiseShuffleMask(RS, /*IsLeft=*/false, Level))
       return false;
-  } else if (matchPairwiseShuffleMask(RS, true, Level)) {
-    if (!matchPairwiseShuffleMask(LS, false, Level))
+  } else if (matchPairwiseShuffleMask(RS, /*IsLeft=*/true, Level)) {
+    if (!matchPairwiseShuffleMask(LS, /*IsLeft=*/false, Level))
       return false;
   } else
     return false;
 
   if (++Level == NumLevels)
     return true;
 
   // Match next level.
-  return matchPairwiseReductionAtLevel(NextLevelBinOp, Level, NumLevels);
+  return matchPairwiseReductionAtLevel(NextLevelOp, Level, NumLevels);
 }
 
 static bool matchPairwiseReduction(const ExtractElementInst *ReduxRoot,
                                    unsigned &Opcode, Type *&Ty) {
   if (!EnableReduxCost)
     return false;
 
   // Need to extract the first element.
   ConstantInt *CI = dyn_cast<ConstantInt>(ReduxRoot->getOperand(1));
   unsigned Idx = ~0u;
   if (CI)
     Idx = CI->getZExtValue();
   if (Idx != 0)
     return false;
 
-  BinaryOperator *RdxStart = dyn_cast<BinaryOperator>(ReduxRoot->getOperand(0));
-  if (!RdxStart)
+  Value *L;
+  Value *R;
+  Value *RdxStart = ReduxRoot->getOperand(0);
+  unsigned RdxOpcode = getReductionOpcode(RdxStart, L, R);
+  if (RdxOpcode == 0)
     return false;
 
-  Type *VecTy = ReduxRoot->getOperand(0)->getType();
+  Type *VecTy = RdxStart->getType();
   unsigned NumVecElems = VecTy->getVectorNumElements();
   if (!isPowerOf2_32(NumVecElems))
     return false;
 
   // We look for a sequence of shuffle,shuffle,add triples like the following
   // that builds a pairwise reduction tree.
   //
   //  (X0, X1, X2, X3)
static bool matchPairwiseReduction(const ExtractElementInst *ReduxRoot,
   //       <4 x i32> <i32 0, i32 undef, i32 undef, i32 undef>
   // %rdx.shuf.1.1 = shufflevector <4 x float> %bin.rdx.0, <4 x float> undef,
   //       <4 x i32> <i32 1, i32 undef, i32 undef, i32 undef>
   // %bin.rdx8 = fadd <4 x float> %rdx.shuf.1.0, %rdx.shuf.1.1
   // %r = extractelement <4 x float> %bin.rdx8, i32 0
   if (!matchPairwiseReductionAtLevel(RdxStart, 0,  Log2_32(NumVecElems)))
     return false;
 
-  Opcode = RdxStart->getOpcode();
+  Opcode = RdxOpcode;
   Ty = VecTy;
 
   return true;
 }
 
 static std::pair<Value *, ShuffleVectorInst *>
-getShuffleAndOtherOprd(BinaryOperator *B) {
-
-  Value *L = B->getOperand(0);
-  Value *R = B->getOperand(1);
+getShuffleAndOtherOprd(Value *L, Value *R) {
   ShuffleVectorInst *S = nullptr;
 
   if ((S = dyn_cast<ShuffleVectorInst>(L)))
     return std::make_pair(R, S);
 
   S = dyn_cast<ShuffleVectorInst>(R);
   return std::make_pair(L, S);
 }
 
 static bool matchVectorSplittingReduction(const ExtractElementInst *ReduxRoot,
                                           unsigned &Opcode, Type *&Ty) {
   if (!EnableReduxCost)
     return false;
 
   // Need to extract the first element.
   ConstantInt *CI = dyn_cast<ConstantInt>(ReduxRoot->getOperand(1));
   unsigned Idx = ~0u;
   if (CI)
     Idx = CI->getZExtValue();
   if (Idx != 0)
     return false;
 
-  BinaryOperator *RdxStart = dyn_cast<BinaryOperator>(ReduxRoot->getOperand(0));
-  if (!RdxStart)
+  Value *L;
+  Value *R;
+  Value *RdxStart = ReduxRoot->getOperand(0);
+  unsigned RdxOpcode = getReductionOpcode(RdxStart, L, R);
+  if (RdxOpcode == 0)
     return false;
-  unsigned RdxOpcode = RdxStart->getOpcode();
 
   Type *VecTy = ReduxRoot->getOperand(0)->getType();
   unsigned NumVecElems = VecTy->getVectorNumElements();
   if (!isPowerOf2_32(NumVecElems))
     return false;
 
   // We look for a sequence of shuffles and adds like the following matching one
   // fadd, shuffle vector pair at a time.
   //
   // %rdx.shuf = shufflevector <4 x float> %rdx, <4 x float> undef,
   //                           <4 x i32> <i32 2, i32 3, i32 undef, i32 undef>
   // %bin.rdx = fadd <4 x float> %rdx, %rdx.shuf
   // %rdx.shuf7 = shufflevector <4 x float> %bin.rdx, <4 x float> undef,
   //                          <4 x i32> <i32 1, i32 undef, i32 undef, i32 undef>
   // %bin.rdx8 = fadd <4 x float> %bin.rdx, %rdx.shuf7
   // %r = extractelement <4 x float> %bin.rdx8, i32 0
 
   unsigned MaskStart = 1;
   Value *RdxOp = RdxStart;
   SmallVector<int, 32> ShuffleMask(NumVecElems, 0);
   unsigned NumVecElemsRemain = NumVecElems;
   while (NumVecElemsRemain - 1) {
     // Check for the right reduction operation.
-    BinaryOperator *BinOp;
-    if (!(BinOp = dyn_cast<BinaryOperator>(RdxOp)))
-      return false;
-    if (BinOp->getOpcode() != RdxOpcode)
+    Value *Op = RdxOp;
+    if (getReductionOpcode(Op, L, R) != RdxOpcode)
       return false;
 
     Value *NextRdxOp;
     ShuffleVectorInst *Shuffle;
-    std::tie(NextRdxOp, Shuffle) = getShuffleAndOtherOprd(BinOp);
+    std::tie(NextRdxOp, Shuffle) = getShuffleAndOtherOprd(L, R);
 
     // Check the current reduction operation and the shuffle use the same value.
     if (Shuffle == nullptr)
       return false;
     if (Shuffle->getOperand(0) != NextRdxOp)
       return false;
 
     // Check that shuffle masks matches.
     for (unsigned j = 0; j != MaskStart; ++j)
       ShuffleMask[j] = MaskStart + j;
     // Fill the rest of the mask with -1 for undef.
     std::fill(&ShuffleMask[MaskStart], ShuffleMask.end(), -1);
 
     SmallVector<int, 16> Mask = Shuffle->getShuffleMask();
     if (ShuffleMask != Mask)
       return false;
 
     RdxOp = NextRdxOp;
     NumVecElemsRemain /= 2;
     MaskStart *= 2;
   }
 
   Opcode = RdxOpcode;
   Ty = VecTy;
   return true;
 }
case Instruction::ExtractElement: {
     if (CI)
       Idx = CI->getZExtValue();
 
     // Try to match a reduction sequence (series of shufflevector and vector
     // adds followed by a extractelement).
     unsigned ReduxOpCode;
     Type *ReduxType;
 
-    if (matchVectorSplittingReduction(EEI, ReduxOpCode, ReduxType))
-      return TTI->getReductionCost(ReduxOpCode, ReduxType, false);
-    else if (matchPairwiseReduction(EEI, ReduxOpCode, ReduxType))
-      return TTI->getReductionCost(ReduxOpCode, ReduxType, true);
+    if (matchVectorSplittingReduction(EEI, ReduxOpCode, ReduxType)) {
+      return TTI->getArithmeticReductionCost(ReduxOpCode, ReduxType,
+                                             /*IsPairwiseForm=*/false);
+    }
+    if (matchPairwiseReduction(EEI, ReduxOpCode, ReduxType)) {
+      return TTI->getArithmeticReductionCost(ReduxOpCode, ReduxType,
+                                             /*IsPairwiseForm=*/true);
+    }
 
     return TTI->getVectorInstrCost(I->getOpcode(),
                                    EEI->getOperand(0)->getType(), Idx);
   }
   case Instruction::InsertElement: {
     const InsertElementInst * IE = cast<InsertElementInst>(I);
     ConstantInt *CI = dyn_cast<ConstantInt>(IE->getOperand(2));
     unsigned Idx = -1;

lib/Analysis/TargetTransformInfo.cpp

 int TargetTransformInfo::getAddressComputationCost(Type *Tp,
                                                    ScalarEvolution *SE,
                                                    const SCEV *Ptr) const {
   int Cost = TTIImpl->getAddressComputationCost(Tp, SE, Ptr);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
-int TargetTransformInfo::getReductionCost(unsigned Opcode, Type *Ty,
+int TargetTransformInfo::getArithmeticReductionCost(unsigned Opcode, Type *Ty,
                                                     bool IsPairwiseForm) const {
-  int Cost = TTIImpl->getReductionCost(Opcode, Ty, IsPairwiseForm);
+  int Cost = TTIImpl->getArithmeticReductionCost(Opcode, Ty, IsPairwiseForm);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
 unsigned
 TargetTransformInfo::getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) const {
   return TTIImpl->getCostOfKeepingLiveOverCall(Tys);
 }

lib/Target/X86/X86TargetTransformInfo.h

public:
   int getAddressComputationCost(Type *PtrTy, ScalarEvolution *SE,
                                 const SCEV *Ptr);
 
   int getIntrinsicInstrCost(Intrinsic::ID IID, Type *RetTy,
                             ArrayRef<Type *> Tys, FastMathFlags FMF);
   int getIntrinsicInstrCost(Intrinsic::ID IID, Type *RetTy,
                             ArrayRef<Value *> Args, FastMathFlags FMF);
 
-  int getReductionCost(unsigned Opcode, Type *Ty, bool IsPairwiseForm);
+  int getArithmeticReductionCost(unsigned Opcode, Type *Ty,
+                                 bool IsPairwiseForm);
 
   int getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy,
                                  unsigned Factor, ArrayRef<unsigned> Indices,
                                  unsigned Alignment, unsigned AddressSpace);
   int getInterleavedMemoryOpCostAVX512(unsigned Opcode, Type *VecTy,
                                  unsigned Factor, ArrayRef<unsigned> Indices,
                                  unsigned Alignment, unsigned AddressSpace);
 

lib/Target/X86/X86TargetTransformInfo.cpp

if (!BaseT::isStridedAccess(Ptr))
       return NumVectorInstToHideOverhead;
     if (!BaseT::getConstantStrideStep(SE, Ptr))
       return 1;
   }
 
   return BaseT::getAddressComputationCost(Ty, SE, Ptr);
 }
 
-int X86TTIImpl::getReductionCost(unsigned Opcode, Type *ValTy,
+int X86TTIImpl::getArithmeticReductionCost(unsigned Opcode, Type *ValTy,
                                            bool IsPairwise) {
 
   std::pair<int, MVT> LT = TLI->getTypeLegalizationCost(DL, ValTy);
 
   MVT MTy = LT.second;
 
   int ISD = TLI->InstructionOpcodeToISD(Opcode);
   assert(ISD && "Invalid opcode");
 
if (ST->hasAVX())
       if (const auto *Entry = CostTableLookup(AVX1CostTblNoPairWise, ISD, MTy))
         return LT.first * Entry->Cost;
 
     if (ST->hasSSE42())
       if (const auto *Entry = CostTableLookup(SSE42CostTblNoPairWise, ISD, MTy))
         return LT.first * Entry->Cost;
   }
 
-  return BaseT::getReductionCost(Opcode, ValTy, IsPairwise);
+  return BaseT::getArithmeticReductionCost(Opcode, ValTy, IsPairwise);
 }
 
 /// \brief Calculate the cost of materializing a 64-bit value. This helper
 /// method might only calculate a fraction of a larger immediate. Therefore it
 /// is valid to return a cost of ZERO.
 int X86TTIImpl::getIntImmCost(int64_t Val) {
   if (Val == 0)
     return TTI::TCC_Free;

lib/Transforms/Vectorize/SLPVectorizer.cpp

 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/NoFolder.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Vectorize.h"
 #include <algorithm>
 #include <memory>
 
 using namespace llvm;
+using namespace llvm::PatternMatch;
 using namespace slpvectorizer;
 
 #define SV_NAME "slp-vectorizer"
 #define DEBUG_TYPE "SLP"
 
 STATISTIC(NumVectorInstructions, "Number of vector instructions generated");
 
 static cl::opt<int>
for (unsigned I = NextInst; I < MaxInst; ++I) {
         Changed = true;
       }
     }
   }
 
   return Changed;
 }
 
-bool SLPVectorizerPass::tryToVectorize(BinaryOperator *V, BoUpSLP &R) {
-  if (!V)
+bool SLPVectorizerPass::tryToVectorize(Instruction *I, BoUpSLP &R) {
+  if (!I)
+    return false;
+
+  if (!isa<BinaryOperator>(I) && !isa<CmpInst>(I))
     return false;
 
-  Value *P = V->getParent();
+  Value *P = I->getParent();
 
   // Vectorize in current basic block only.
-  auto *Op0 = dyn_cast<Instruction>(V->getOperand(0));
-  auto *Op1 = dyn_cast<Instruction>(V->getOperand(1));
+  auto *Op0 = dyn_cast<Instruction>(I->getOperand(0));
+  auto *Op1 = dyn_cast<Instruction>(I->getOperand(1));
   if (!Op0 || !Op1 || Op0->getParent() != P || Op1->getParent() != P)
     return false;
 
   // Try to vectorize V.
   if (tryToVectorizePair(Op0, Op1, R))
     return true;
 
   auto *A = dyn_cast<BinaryOperator>(Op0);

 ///     +
 ///     |
 ///   *p =
 ///
 class HorizontalReduction {
   SmallVector<Value *, 16> ReductionOps;
   SmallVector<Value *, 32> ReducedVals;
 
-  BinaryOperator *ReductionRoot = nullptr;
+  /// Contains info about operation, like its opcode, left and right operands +
+  /// validity.
+  struct OperationData {
+    /// true if data is valid and represents one of the instructions.
+    bool Validity = false;
+    /// Opcode of the instruction.
+    unsigned Opcode = 0;
+    /// Left operand of the instruction.
+    Value *LHS = nullptr;
+    /// Right operand of the instruction.
+    Value *RHS = nullptr;
+
+  public:
+    explicit OperationData() = default;
+    /// Construction for reduced values. They are identified by opcode only and
+    /// don't have associated LHS/RHS values.
+    explicit OperationData(Value *V) {
+      if (auto *I = dyn_cast<Instruction>(V)) {
+        Validity = true;
+        Opcode = I->getOpcode();
+      }
+    }
+    /// Constructor for binary reduction operations with opcode and its left and
+    /// right operands.
+    OperationData(unsigned Opcode, Value *LHS, Value *RHS)
+        : Validity(true), Opcode(Opcode), LHS(LHS), RHS(RHS) {}
+    operator bool() const { return Validity; }
+    /// Get the index of the first operand of the reduction operation.
+    unsigned getFirstOperandIndex() const {
+      assert(Validity && LHS && RHS);
+      return 0;
+    }
+    /// Total number of operands in the reduction operation.
+    unsigned getNumberOfOperands() const {
+      assert(Validity && LHS && RHS);
+      return 2;
+    }
+    /// Expected number of uses for reduction operations/reduced values.
+    unsigned getRequiredNumberOfUses() const {
+      assert(Validity && LHS && RHS);
+      return 1;
+    }
+    /// Checks if instruction is associative and can be vectorized.
+    bool isAssociative(Instruction *I) const {
+      assert(Validity && LHS && RHS);
+      return I->isAssociative();
+    }
+    /// Checks if the reduction operation can be vectorized.
+    bool isVectorizable() const {
+      return Validity && LHS && RHS &&
+             // We currently only support adds and min/max.
+             (Opcode == Instruction::Add || Opcode == Instruction::FAdd);
+    }
+    /// Checks if two operation data represent reduction operation/reduced
+    /// value of the same kind.
+    bool operator==(const OperationData &OD) {
+      return this == &OD || (Validity == OD.Validity && (!LHS == !OD.LHS) &&
+                             (!RHS == !OD.RHS) && Opcode == OD.Opcode);
+    }
+    bool operator!=(const OperationData &OD) { return !(*this == OD); }
+    void clear() {
+      Validity = false;
+      LHS = nullptr;
+      RHS = nullptr;
+      Opcode = 0;
+    }
+    unsigned getOpcode() const {
+      assert(isVectorizable());
+      return Opcode;
+    }
+    Value *getLHS() const { return LHS; }
+    Value *getRHS() const { return RHS; }
+    /// Creates reuction operation with the current opcode.
+    Value *createOp(IRBuilder<> &Builder, Value *L, Value *R,
+                    const Twine &Name = "") const {
+      assert(Opcode == Instruction::FAdd || Opcode == Instruction::Add);
+      if (Opcode == Instruction::FAdd)
+        return Builder.CreateFAdd(L, R, Name);
+      return Builder.CreateBinOp((Instruction::BinaryOps)Opcode, L, R, Name);
+    }
+  };
+
+  Instruction *ReductionRoot = nullptr;
   // After successfull horizontal reduction vectorization attempt for PHI node
   // vectorizer tries to update root binary op by combining vectorized tree and
   // the ReductionPHI node. But during vectorization this ReductionPHI can be
   // vectorized itself and replaced by the undef value, while the instruction
   // itself is marked for deletion. This 'marked for deletion' PHI node then can
   // be used in new binary operation, causing "Use still stuck around after Def
   // is destroyed" crash upon PHI node deletion.
   WeakVH ReductionPHI;
 
-  /// The opcode of the reduction.
-  Instruction::BinaryOps ReductionOpcode = Instruction::BinaryOpsEnd;
-  /// The opcode of the values we perform a reduction on.
-  unsigned ReducedValueOpcode = 0;
+  /// The operation data of the reduction operation.
+  OperationData ReductionData;
+  /// The operation data of the values we perform a reduction on.
+  OperationData ReducedValueData;
   /// Should we model this reduction as a pairwise reduction tree or a tree that
   /// splits the vector in halves and adds those halves.
   bool IsPairwiseReduction = false;
 
+  static OperationData getOperationData(Value *V) {
+    if (!V)
+      return OperationData();
+
+    Value *LHS;
+    Value *RHS;
+    if (m_BinOp(m_Value(LHS), m_Value(RHS)).match(V))
+      return {cast<BinaryOperator>(V)->getOpcode(), LHS, RHS};
+    return OperationData(V);
+  }
+
 public:
   HorizontalReduction() = default;
 
   /// \brief Try to find a reduction tree.
-  bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B) {
+  bool matchAssociativeReduction(PHINode *Phi, Instruction *B) {
     assert((!Phi || is_contained(Phi->operands(), B)) &&
            "Thi phi needs to use the binary operator");
 
+    ReductionData = getOperationData(B);
+
     // We could have a initial reductions that is not an add.
     //  r *= v1 + v2 + v3 + v4
     // In such a case start looking for a tree rooted in the first '+'.
     if (Phi) {
-      if (B->getOperand(0) == Phi) {
+      if (ReductionData.getLHS() == Phi) {
         Phi = nullptr;
-        B = dyn_cast<BinaryOperator>(B->getOperand(1));
-      } else if (B->getOperand(1) == Phi) {
+        B = dyn_cast<Instruction>(ReductionData.getRHS());
+        ReductionData = getOperationData(B);
+      } else if (ReductionData.getRHS() == Phi) {
         Phi = nullptr;
-        B = dyn_cast<BinaryOperator>(B->getOperand(0));
+        B = dyn_cast<Instruction>(ReductionData.getLHS());
+        ReductionData = getOperationData(B);
       }
     }
 
-    if (!B)
+    if (!ReductionData.isVectorizable() || !ReductionData.isAssociative(B))
       return false;
 
     Type *Ty = B->getType();
     if (!isValidElementType(Ty))
       return false;
 
-    ReductionOpcode = B->getOpcode();
-    ReducedValueOpcode = 0;
+    ReducedValueData.clear();
     ReductionRoot = B;
     ReductionPHI = Phi;
 
-    // We currently only support adds.
-    if ((ReductionOpcode != Instruction::Add &&
-         ReductionOpcode != Instruction::FAdd) ||
-        !B->isAssociative())
-      return false;
-
     // Post order traverse the reduction tree starting at B. We only handle true
-    // trees containing only binary operators or selects.
+    // trees containing only binary operators.
     SmallVector<std::pair<Instruction *, unsigned>, 32> Stack;
-    Stack.push_back(std::make_pair(B, 0));
+    Stack.push_back(std::make_pair(B, ReductionData.getFirstOperandIndex()));
+    const unsigned NUses = ReductionData.getRequiredNumberOfUses();
     while (!Stack.empty()) {
       Instruction *TreeN = Stack.back().first;
       unsigned EdgeToVist = Stack.back().second++;
-      bool IsReducedValue = TreeN->getOpcode() != ReductionOpcode;
+      OperationData OpData = getOperationData(TreeN);
+      bool IsReducedValue = OpData != ReductionData;
 
       // Postorder vist.
-      if (EdgeToVist == 2 || IsReducedValue) {
+      if (IsReducedValue || EdgeToVist == OpData.getNumberOfOperands()) {
         if (IsReducedValue)
           ReducedVals.push_back(TreeN);
         else
           ReductionOps.push_back(TreeN);
         // Retract.
         Stack.pop_back();
         continue;
       }
 
       // Visit left or right.
       Value *NextV = TreeN->getOperand(EdgeToVist);
       if (NextV != Phi) {
         auto *I = dyn_cast<Instruction>(NextV);
+        OpData = getOperationData(I);
         // Continue analysis if the next operand is a reduction operation or
         // (possibly) a reduced value. If the reduced value opcode is not set,
         // the first met operation != reduction operation is considered as the
         // reduced value class.
-        if (I && (!ReducedValueOpcode || I->getOpcode() == ReducedValueOpcode ||
-                  I->getOpcode() == ReductionOpcode)) {
+        if (I && (!ReducedValueData || OpData == ReducedValueData ||
+                  OpData == ReductionData)) {
           // Only handle trees in the current basic block.
           if (I->getParent() != B->getParent())
             return false;
 
-          // Each tree node needs to have one user except for the ultimate
-          // reduction.
-          if (!I->hasOneUse() && I != B)
+          // Each tree node needs to have minimal number of users except for the
+          // ultimate reduction.
+          if (!I->hasNUses(NUses) && I != B)
             return false;
 
-          if (I->getOpcode() == ReductionOpcode) {
+          if (OpData == ReductionData) {
             // We need to be able to reassociate the reduction operations.
-            if (!I->isAssociative())
+            if (!OpData.isAssociative(I))
               return false;
-          } else if (ReducedValueOpcode &&
-                     ReducedValueOpcode != I->getOpcode()) {
+          } else if (ReducedValueData &&
+                     ReducedValueData != OpData) {
             // Make sure that the opcodes of the operations that we are going to
             // reduce match.
             return false;
-          } else if (!ReducedValueOpcode)
-            ReducedValueOpcode = I->getOpcode();
+          } else if (!ReducedValueData)
+            ReducedValueData = OpData;
 
-          Stack.push_back(std::make_pair(I, 0));
+          Stack.push_back(std::make_pair(I, OpData.getFirstOperandIndex()));
           continue;
         }
         return false;
       }
     }
     return true;
   }
 
while (i < NumReducedVals - ReduxWidth + 1 && ReduxWidth > 2) {
       DebugLoc Loc = cast<Instruction>(ReducedVals[i])->getDebugLoc();
       Value *VectorizedRoot = V.vectorizeTree();
 
       // Emit a reduction.
       Value *ReducedSubTree =
           emitReduction(VectorizedRoot, Builder, ReduxWidth);
       if (VectorizedTree) {
         Builder.SetCurrentDebugLocation(Loc);
-        VectorizedTree = Builder.CreateBinOp(ReductionOpcode, VectorizedTree,
+        VectorizedTree = ReductionData.createOp(Builder, VectorizedTree,
                                                 ReducedSubTree, "bin.rdx");
       } else
         VectorizedTree = ReducedSubTree;
       i += ReduxWidth;
       ReduxWidth = PowerOf2Floor(NumReducedVals - i);
     }
 
     if (VectorizedTree) {
       // Finish the reduction.
       for (; i < NumReducedVals; ++i) {
         Builder.SetCurrentDebugLocation(
           cast<Instruction>(ReducedVals[i])->getDebugLoc());
-        VectorizedTree = Builder.CreateBinOp(ReductionOpcode, VectorizedTree,
-                                             ReducedVals[i]);
+        VectorizedTree =
+            ReductionData.createOp(Builder, VectorizedTree, ReducedVals[i]);
       }
       // Update users.
       if (ReductionPHI && !isa<UndefValue>(ReductionPHI)) {
         assert(ReductionRoot && "Need a reduction operation");
         ReductionRoot->setOperand(0, VectorizedTree);
         ReductionRoot->setOperand(1, ReductionPHI);
       } else
         ReductionRoot->replaceAllUsesWith(VectorizedTree);
     }
     return VectorizedTree != nullptr;
   }
 
   unsigned numReductionValues() const {
     return ReducedVals.size();
   }
 
 private:
   /// \brief Calculate the cost of a reduction.
   int getReductionCost(TargetTransformInfo *TTI, Value *FirstReducedVal,
                        unsigned ReduxWidth) {
     Type *ScalarTy = FirstReducedVal->getType();
     Type *VecTy = VectorType::get(ScalarTy, ReduxWidth);
 
-    int PairwiseRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, true);
-    int SplittingRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, false);
+    int PairwiseRdxCost =
+        TTI->getArithmeticReductionCost(ReductionData.getOpcode(), VecTy,
+                                        /*IsPairwiseForm=*/true);
+    int SplittingRdxCost =
+        TTI->getArithmeticReductionCost(ReductionData.getOpcode(), VecTy,
+                                        /*IsPairwiseForm=*/false);
 
     IsPairwiseReduction = PairwiseRdxCost < SplittingRdxCost;
     int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost;
 
     int ScalarReduxCost =
         (ReduxWidth - 1) *
-        TTI->getArithmeticInstrCost(ReductionOpcode, ScalarTy);
+        TTI->getArithmeticInstrCost(ReductionData.getOpcode(), ScalarTy);
 
     DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost
                  << " for reduction that starts with " << *FirstReducedVal
                  << " (It is a "
                  << (IsPairwiseReduction ? "pairwise" : "splitting")
                  << " reduction)\n");
 
     return VecReduxCost - ScalarReduxCost;
for (unsigned i = ReduxWidth / 2; i != 0; i >>= 1) {
         Value *RightMask =
           createRdxShuffleMask(ReduxWidth, i, true, false, Builder);
 
         Value *LeftShuf = Builder.CreateShuffleVector(
           TmpVec, UndefValue::get(TmpVec->getType()), LeftMask, "rdx.shuf.l");
         Value *RightShuf = Builder.CreateShuffleVector(
           TmpVec, UndefValue::get(TmpVec->getType()), (RightMask),
           "rdx.shuf.r");
-        TmpVec = Builder.CreateBinOp(ReductionOpcode, LeftShuf, RightShuf,
-                                     "bin.rdx");
+        TmpVec =
+            ReductionData.createOp(Builder, LeftShuf, RightShuf, "bin.rdx");
       } else {
         Value *UpperHalf =
           createRdxShuffleMask(ReduxWidth, i, false, false, Builder);
         Value *Shuf = Builder.CreateShuffleVector(
           TmpVec, UndefValue::get(TmpVec->getType()), UpperHalf, "rdx.shuf");
-        TmpVec = Builder.CreateBinOp(ReductionOpcode, TmpVec, Shuf, "bin.rdx");
+        TmpVec = ReductionData.createOp(Builder, TmpVec, Shuf, "bin.rdx");
       }
     }
 
     // The result is in the first element of the vector.
     return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
   }
 };
 } // end anonymous namespace

 } // namespace
 
 /// \brief Attempt to reduce a horizontal reduction.
 /// If it is legal to match a horizontal reduction feeding
 /// the phi node P with reduction operators Root in a basic block BB, then check
 /// if it can be done.
 /// \returns true if a horizontal reduction was matched and reduced.
 /// \returns false if a horizontal reduction was not matched.
-static bool canBeVectorized(
-    PHINode *P, Instruction *Root, BasicBlock *BB, BoUpSLP &R,
+static bool
+canBeVectorized(PHINode *P, Instruction *Root, BasicBlock *BB, BoUpSLP &R,
                 TargetTransformInfo *TTI,
-    const function_ref<bool(BinaryOperator *, BoUpSLP &)> Vectorize) {
+                const function_ref<bool(Instruction *, BoUpSLP &)> Vectorize) {
   if (!ShouldVectorizeHor)
     return false;
 
   if (!Root)
     return false;
 
   if (Root->getParent() != BB)
     return false;
   SmallVector<WeakVHWithLevel, 8> Stack(1, Root);
   SmallSet<Value *, 8> VisitedInstrs;
   bool Res = false;
   while (!Stack.empty()) {
     Value *V = Stack.back();
     if (!V) {
       Stack.pop_back();
       continue;
     }
     auto *Inst = dyn_cast<Instruction>(V);
     if (!Inst || isa<PHINode>(Inst)) {
       Stack.pop_back();
       continue;
     }
     if (Stack.back().isInitial()) {
       Stack.back().clearInitial();
-      if (auto *BI = dyn_cast<BinaryOperator>(Inst)) {
+      auto *BI = dyn_cast<BinaryOperator>(Inst);
+      if (BI) {
         HorizontalReduction HorRdx;
-        if (HorRdx.matchAssociativeReduction(P, BI)) {
+        if (HorRdx.matchAssociativeReduction(P, Inst)) {
           if (HorRdx.tryToReduce(R, TTI)) {
             Res = true;
             P = nullptr;
             continue;
           }
         }
         if (P) {
           Inst = dyn_cast<Instruction>(BI->getOperand(0));
           if (Inst == P)
             Inst = dyn_cast<Instruction>(BI->getOperand(1));
           if (!Inst) {
             P = nullptr;
             continue;
           }
         }
       }
       P = nullptr;
-      if (Vectorize(dyn_cast<BinaryOperator>(Inst), R)) {
+      if (Vectorize(Inst, R)) {
         Res = true;
         continue;
       }
     }
     if (Stack.back().isFinal()) {
       Stack.pop_back();
       continue;
     }
bool SLPVectorizerPass::vectorizeRootInstruction(PHINode *P, Value *V,
   auto *I = dyn_cast<Instruction>(V);
   if (!I)
     return false;
 
   if (!isa<BinaryOperator>(I))
     P = nullptr;
   // Try to match and vectorize a horizontal reduction.
   return canBeVectorized(P, I, BB, R, TTI,
-                         [this](BinaryOperator *BI, BoUpSLP &R) -> bool {
-                           return tryToVectorize(BI, R);
+                         [this](Instruction *I, BoUpSLP &R) -> bool {
+                           return tryToVectorize(I, R);
                          });
 }
 
 bool SLPVectorizerPass::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) {
   bool Changed = false;
   SmallVector<Value *, 4> Incoming;
   SmallSet<Value *, 16> VisitedInstrs;
 
if (ReturnInst *RI = dyn_cast<ReturnInst>(it)) {
           it = BB->begin();
           e = BB->end();
           continue;
         }
       }
     }
 
     // Try to vectorize trees that start at compare instructions.
-    if (CmpInst *CI = dyn_cast<CmpInst>(it)) {
-      if (tryToVectorizePair(CI->getOperand(0), CI->getOperand(1), R)) {
-        Changed = true;
-        // We would like to start over since some instructions are deleted
-        // and the iterator may become invalid value.
-        it = BB->begin();
-        e = BB->end();
+    if (auto *BI = dyn_cast<BranchInst>(it)) {
+      if (!BI->isConditional())
         continue;
-      }
 
-      for (int I = 0; I < 2; ++I) {
-        if (vectorizeRootInstruction(nullptr, CI->getOperand(I), BB, R, TTI)) {
-          Changed = true;
-          // We would like to start over since some instructions are deleted
-          // and the iterator may become invalid value.
-          it = BB->begin();
-          e = BB->end();
-          break;
-        }
-      }
+      if (vectorizeRootInstruction(nullptr, BI->getCondition(), BB, R, TTI)) {
         continue;
       }
+    }
 
     // Try to vectorize trees that start at insertelement instructions.
     if (InsertElementInst *FirstInsertElem = dyn_cast<InsertElementInst>(it)) {
       SmallVector<Value *, 16> BuildVector;
       SmallVector<Value *, 16> BuildVectorOpds;
       if (!findBuildVector(FirstInsertElem, BuildVector, BuildVectorOpds))
         continue;