[SLPVectorizer] Try to vectorize in the range from MaxVecRegSize to MinVecRegSize

[JongwonLee]

Summary

The previous SLP-vectorizer tried to vectorize for only one kind of vector register size, MinVecRegSize.
With this patch, we can try to vectorize in the range from MaxVecRegSize to MinVecRegSize.

[mcrosier]

lib/Transforms/Vectorize/SLPVectorizer.cpp

3427

I'm thinking this should be a TTI hook, so each target can define the MinVecRegSize.

3723

Maybe use VecRegSize, rather than Size here?

3747

I believe you've addressed this fix me, correct?

3987

Same. Remove FIXME.

4342

Maybe use VecRegSize, rather than Size here?

4419

I assume this should be deleted, rather than commented out.

4489

I don't think you need the temporary variable.

for () {
  if (tryToVectorizeList()) {
    Changed = true;
    it = BB->begin();
    e = BB->end();
    break;
  }
}

4586

Please remove.

4587

I don't think you need this temporary value. You can just do something like the below, correct?

for (...)
  if (tryToVectorizeList()) {
    Changed = true;
    break;
  }

[mzolotukhin]

Hi Jongwon,

Thanks for working on this, I think that's a natural improvement over what we have now. I agree with Chad's remarks and have some more comments.

The patch now includes two semantical parts:

• Change default MinVecRegSize value for AArch64.
• Actually use MinVecRegSize in tryToVectorizeList and friends.

They look to me completely separated (and, in the end, needed), so I'd suggest tackling them in separate patches.

For the first part - changing the default value - I totally agree with Chad that it should be done via a target hook. You could take a look at how MaxVecRegSize is implemented. In general, SLPVectorizer.cpp shouldn't contain any target-specific code, and all target-dependent info should be requested via hooks (i.e. having a variable IsAArch64 might be a bad idea).
Also, for this kind of change it would be nice to show the impact on compilation and execution time. LLVM test-suite is good for this, results on other popular testsuites (e.g. SPEC) are also valueable.

The second part is good in general, one possible improvement you could do (if you have time for this) is to refactor vectorizeStoreChain and tryToVectorizeList functions. They'll be very similar when tryToVectorizeList is parametrized with a size too. That potentially should remove a lot of duplication in the code, which is always good.

Also, you'll need new tests for the second part, currently I assume the test you have is for the first part.

Thanks,
Michael

[JongwonLee]

lib/Transforms/Vectorize/SLPVectorizer.cpp

3427

I'll separate this from the current patch. The current patch will only handle the range of the size of vectorizable registers.

3747

Yes. The comment are removed.

[mcrosier]

lib/Transforms/Vectorize/SLPVectorizer.cpp

3664

Why not just return true here and remove the unnecessary temp variable?

3668

return false (assuming you do the suggestion above).

4279

Shouldn't the call to tryToVectorizeList() still be predicated on NumElts > 1?

[JongwonLee]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4279

Fixed the code to call tryToVectorizeList() when NumElts > 1 is satisfied.

[mcrosier]

I should have suggested this earlier (sorry), but do you think it make sense to push the loops into tryToVectorizeList and canMatchHorizontalReduction? I think it does; it avoids a lot of duplicated code at each call site.

lib/Transforms/Vectorize/SLPVectorizer.cpp

4279

No that this logic is cleaned up you don't need the temporary bool.

for (unsigned VecRegSize = MaxVecRegSize; VecRegSize >= MinVecRegSize; VecRegSize /= 2) {
  if (tryToVectorizeList(makeArrayRef(IncIt, NumElts), R, None, false, VecRegSize)) {
    // Success start over because instructions might have been changed.
    HaveVectorizedPhiNodes = true;
    Changed = true;
    break;
  }
}

[mzolotukhin]

do you think it make sense to push the loops into tryToVectorizeList and canMatchHorizontalReduction?

Actually, it might make sense to keep it as is, the reason being the current form is closer to what we have in vectorizeStoreChain. Eventually, it would be cool to merge these two functions together to reduce code duplication. What do you think?

Michael

[mcrosier]

In D18237#380399, @mzolotukhin wrote:

do you think it make sense to push the loops into tryToVectorizeList and canMatchHorizontalReduction?

Actually, it might make sense to keep it as is, the reason being the current form is closer to what we have in vectorizeStoreChain. Eventually, it would be cool to merge these two functions together to reduce code duplication. What do you think?

That's fine by me, Michael.

[JongwonLee]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4279

Removed the temporary bool.

[JongwonLee]

Removed the function 'vectorizeStoreChain' and modified the function 'tryToVectroizeList'.

[mzolotukhin]

Hi Jongwon,

Thanks for the work, please find some comments below.

Michael

lib/Transforms/Vectorize/SLPVectorizer.cpp

3696

Nitpick: I'd rather swap if and else blocks to avoid negation in the condition.

3705–3706

I think this check should be combined with the one below:

if (!isPowerOf2_32(OpsWidth) || OpsWidth < 2)
  break;

and it should be done independently on vectorizeStoreChain flag.

4545

SLPCostThreshold disappeared after this change. Was it intentional?

[mssimpso]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4545

SLPCostThreshold is a command line option, so it doesn't need to be passed as a function parameter.

[mzolotukhin]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4545

Ah, right, thanks for pointing that out!

[JongwonLee]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4545

Yes. mssimpso is right.

[JongwonLee]

ping!

[JongwonLee]

ping~!

[mssimpso]

Hi Jongwon,

I've inlined a few comments. And I agree with Michael about the compile-time experiments. It would be helpful to see what kind of impact trying different register sizes will have. Thanks!

lib/Transforms/Vectorize/SLPVectorizer.cpp

3501

Unless I missed something, it looks to me like every use of tryToVectorizeList passes VecRegSize. Why make the parameter optional?

4222

I think it would be less confusing and more consistent if MinRegSize was renamed to VecRegSize here.

[JongwonLee]

This comment was removed by JongwonLee.

[JongwonLee]

This patch doesn't change the default value of MinVecRegSize, so it does not affect the performance.
(On top of this patch, another patch(http://reviews.llvm.org/D19151) is needed to change the default value of MinVecRegSize.)
In commercial benchmark, I found that clang lost the chance of 64-bit SLP vectorization in AArch64.
Although there would be side effect of extension of 64-bit SLP vectorization, the compiler should handle 64-bit SLP vectorization in AArch64. The side effect, if any, should be handled with another patch.

I tried to upload the data about compile-time and execution-time, but .csv file is not attached in the comment box. Please guide me how to upload .csv file if possible.

[mssimpso]

Hey Jongwon,

I think it's common to just paste in the most significant execution and compile time improvements and regressions. It's not necessary to report every data point.

Even though you're not changing the value of MinVecRegSize here, I think it makes sense to evaluate this patch and D19151 together so we can see the effect (particularly in compile time) that looping over potential register sizes will have.

[JongwonLee]

In SPEC benchmark, compile-time increases by 2.8%. In LLVM test-suite, compile-time decreases by 9 %. The data are measured from the average of three times executions.

lib/Transforms/Vectorize/SLPVectorizer.cpp

bool runOnFunction(Function &F) override {
     else
       MaxVecRegSize = TTI->getRegisterBitWidth(true);
 
     MinVecRegSize = MinVectorRegSizeOption;
 
     // Don't vectorize when the attribute NoImplicitFloat is used.
     if (F.hasFnAttribute(Attribute::NoImplicitFloat))
       return false;
 
     DEBUG(dbgs() << "SLP: Analyzing blocks in " << F.getName() << ".\n");
 
     // Use the bottom up slp vectorizer to construct chains that start with
     // store instructions.
     BoUpSLP R(&F, SE, TTI, TLI, AA, LI, DT, AC, DB, DL);
 
     // A general note: the vectorizer must use BoUpSLP::eraseInstruction() to
     // delete instructions.
private:
   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
   bool tryToVectorizePair(Value *A, Value *B, BoUpSLP &R);
 
   /// \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, BoUpSLP &R,
+                          unsigned VecRegSize = 128,
+                          bool vectorizeStoreChain = false,
                           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, BoUpSLP &R);
 
   /// \brief Vectorize the store instructions collected in Stores.
   bool vectorizeStoreChains(BoUpSLP &R);
 
   /// \brief Vectorize the index computations of the getelementptr instructions
   /// collected in GEPs.
   bool vectorizeGEPIndices(BasicBlock *BB, BoUpSLP &R);
 
   /// \brief Scan the basic block and look for patterns that are likely to start
   /// a vectorization chain.
   bool vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R);
 
-  bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
-                           BoUpSLP &R, unsigned VecRegSize);
-
-  bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
-                       BoUpSLP &R);
+  bool vectorizeStores(ArrayRef<StoreInst *> Stores, BoUpSLP &R);
 
   /// The store instructions in a basic block organized by base pointer.
   StoreListMap Stores;
 
   /// The getelementptr instructions in a basic block organized by base pointer.
   WeakVHListMap GEPs;
 
   /// The number of store instructions in a basic block.

 /// to become invalid. We track when this has happened in the WeakVH array.
 static bool hasValueBeenRAUWed(ArrayRef<Value *> VL, ArrayRef<WeakVH> VH,
                                unsigned SliceBegin, unsigned SliceSize) {
   VL = VL.slice(SliceBegin, SliceSize);
   VH = VH.slice(SliceBegin, SliceSize);
   return !std::equal(VL.begin(), VL.end(), VH.begin());
 }
 
-bool SLPVectorizer::vectorizeStoreChain(ArrayRef<Value *> Chain,
-                                        int CostThreshold, BoUpSLP &R,
-                                        unsigned VecRegSize) {
-  unsigned ChainLen = Chain.size();
-  DEBUG(dbgs() << "SLP: Analyzing a store chain of length " << ChainLen
-        << "\n");
-  unsigned Sz = R.getVectorElementSize(Chain[0]);
-  unsigned VF = VecRegSize / Sz;
-
-  if (!isPowerOf2_32(Sz) || VF < 2)
-    return false;
-
-  // Keep track of values that were deleted by vectorizing in the loop below.
-  SmallVector<WeakVH, 8> TrackValues(Chain.begin(), Chain.end());
-
-  bool Changed = false;
-  // Look for profitable vectorizable trees at all offsets, starting at zero.
-  for (unsigned i = 0, e = ChainLen; i < e; ++i) {
-    if (i + VF > e)
-      break;
-
-    // Check that a previous iteration of this loop did not delete the Value.
-    if (hasValueBeenRAUWed(Chain, TrackValues, i, VF))
-      continue;
-
-    DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i
-          << "\n");
-    ArrayRef<Value *> Operands = Chain.slice(i, VF);
-
-    R.buildTree(Operands);
-    R.computeMinimumValueSizes();
-
-    int Cost = R.getTreeCost();
-
-    DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n");
-    if (Cost < CostThreshold) {
-      DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n");
-      R.vectorizeTree();
-
-      // Move to the next bundle.
-      i += VF - 1;
-      Changed = true;
-    }
-  }
-
-  return Changed;
-}
-
-bool SLPVectorizer::vectorizeStores(ArrayRef<StoreInst *> Stores,
-                                    int costThreshold, BoUpSLP &R) {
+bool SLPVectorizer::vectorizeStores(ArrayRef<StoreInst *> Stores, BoUpSLP &R) {
   SetVector<StoreInst *> Heads, Tails;
   SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain;
 
   // We may run into multiple chains that merge into a single chain. We mark the
   // stores that we vectorized so that we don't visit the same store twice.
   BoUpSLP::ValueSet VectorizedStores;
   bool Changed = false;
 
while (Tails.count(I) || Heads.count(I)) {
         break;
       Operands.push_back(I);
       // Move to the next value in the chain.
       I = ConsecutiveChain[I];
     }
 
     // FIXME: Is division-by-2 the correct step? Should we assert that the
     // register size is a power-of-2?
-    for (unsigned Size = MaxVecRegSize; Size >= MinVecRegSize; Size /= 2) {
-      if (vectorizeStoreChain(Operands, costThreshold, R, Size)) {
+    for (unsigned VecRegSize = MaxVecRegSize; VecRegSize >= MinVecRegSize;
+         VecRegSize /= 2) {
+      if (tryToVectorizeList(Operands, R, VecRegSize, true)) {
         // Mark the vectorized stores so that we don't vectorize them again.
         VectorizedStores.insert(Operands.begin(), Operands.end());
         Changed = true;
         break;
       }
     }
   }
 
for (Instruction &I : *BB) {
     }
   }
 }
 
 bool SLPVectorizer::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) {
   if (!A || !B)
     return false;
   Value *VL[] = { A, B };
-  return tryToVectorizeList(VL, R, None, true);
+  for (unsigned VecRegSize = MaxVecRegSize; VecRegSize >= MinVecRegSize;
+       VecRegSize /= 2) {
+    if (tryToVectorizeList(VL, R, VecRegSize, false, None, true))
+      return true;
+  }
+  return false;
 }
 
 bool SLPVectorizer::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
+                                       unsigned VecRegSize,
+                                       bool vectorizeStoreChain,
                                        ArrayRef<Value *> BuildVector,
                                        bool allowReorder) {
   if (VL.size() < 2)
     return false;
 
   DEBUG(dbgs() << "SLP: Vectorizing a list of length = " << VL.size() << ".\n");
 
   // Check that all of the parts are scalar instructions of the same type.
   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
   if (!I0)
     return false;
 
   unsigned Opcode0 = I0->getOpcode();
-
-  // FIXME: Register size should be a parameter to this function, so we can
-  // try different vectorization factors.
   unsigned Sz = R.getVectorElementSize(I0);
-  unsigned VF = MinVecRegSize / Sz;
+  unsigned VF = VecRegSize / Sz;
 
+  if (vectorizeStoreChain == false) {
     for (Value *V : VL) {
       Type *Ty = V->getType();
       if (!isValidElementType(Ty))
         return false;
       Instruction *Inst = dyn_cast<Instruction>(V);
       if (!Inst || Inst->getOpcode() != Opcode0)
         return false;
     }
+  }
 
   bool Changed = false;
 
   // Keep track of values that were deleted by vectorizing in the loop below.
   SmallVector<WeakVH, 8> TrackValues(VL.begin(), VL.end());
 
   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
-    unsigned OpsWidth = 0;
+    unsigned OpsWidth = VF;
 
-    if (i + VF > e)
-      OpsWidth = e - i;
+    if (i + VF > e) {
+      if (vectorizeStoreChain)
+        break;
       else
-      OpsWidth = VF;
+        OpsWidth = e - i;
+    }
 
     if (!isPowerOf2_32(OpsWidth) || OpsWidth < 2)
       break;
 
     // Check that a previous iteration of this loop did not delete the Value.
     if (hasValueBeenRAUWed(VL, TrackValues, i, OpsWidth))
       continue;
 
     DEBUG(dbgs() << "SLP: Analyzing " << OpsWidth << " operations "
                  << "\n");
     ArrayRef<Value *> Ops = VL.slice(i, OpsWidth);
 
     ArrayRef<Value *> BuildVectorSlice;
     if (!BuildVector.empty())
       BuildVectorSlice = BuildVector.slice(i, OpsWidth);
 
     R.buildTree(Ops, BuildVectorSlice);
     // TODO: check if we can allow reordering also for other cases than
     // tryToVectorizePair()
     if (allowReorder && R.shouldReorder()) {
       assert(Ops.size() == 2);
       assert(BuildVectorSlice.empty());
       Value *ReorderedOps[] = { Ops[1], Ops[0] };
       R.buildTree(ReorderedOps, None);
     }
     R.computeMinimumValueSizes();
     int Cost = R.getTreeCost();
 
     if (Cost < -SLPCostThreshold) {
       DEBUG(dbgs() << "SLP: Vectorizing list at cost:" << Cost << ".\n");
       Value *VectorizedRoot = R.vectorizeTree();
 
       // Reconstruct the build vector by extracting the vectorized root. This
       // way we handle the case where some elements of the vector are undefined.
       //  (return (inserelt <4 xi32> (insertelt undef (opd0) 0) (opd1) 2))
       if (!BuildVectorSlice.empty()) {
         // The insert point is the last build vector instruction. The vectorized
         // root will precede it. This guarantees that we get an instruction. The
         // vectorized tree could have been constant folded.
         Instruction *InsertAfter = cast<Instruction>(BuildVectorSlice.back());
         unsigned VecIdx = 0;
         for (auto &V : BuildVectorSlice) {
           IRBuilder<NoFolder> Builder(InsertAfter->getParent(),
                                       ++BasicBlock::iterator(InsertAfter));
public:
   unsigned MinVecRegSize;
 
   HorizontalReduction(unsigned MinVecRegSize)
       : ReductionRoot(nullptr), ReductionPHI(nullptr), ReductionOpcode(0),
         ReducedValueOpcode(0), IsPairwiseReduction(false), ReduxWidth(0),
         MinVecRegSize(MinVecRegSize) {}
 
   /// \brief Try to find a reduction tree.
-  bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B) {
+  bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B,
+                                 unsigned VecRegSize) {
     assert((!Phi ||
             std::find(Phi->op_begin(), Phi->op_end(), B) != Phi->op_end()) &&
            "Thi phi needs to use the binary operator");
 
     // 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) {
bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B,
 
     Type *Ty = B->getType();
     if (!isValidElementType(Ty))
       return false;
 
     const DataLayout &DL = B->getModule()->getDataLayout();
     ReductionOpcode = B->getOpcode();
     ReducedValueOpcode = 0;
-    // FIXME: Register size should be a parameter to this function, so we can
-    // try different vectorization factors.
-    ReduxWidth = MinVecRegSize / DL.getTypeSizeInBits(Ty);
+    ReduxWidth = VecRegSize / DL.getTypeSizeInBits(Ty);
     ReductionRoot = B;
     ReductionPHI = Phi;
 
     if (ReduxWidth < 4)
       return false;
 
     // We currently only support adds.
     if (ReductionOpcode != Instruction::Add &&
while (!Stack.empty()) {
       // We currently only allow BinaryOperator's and SelectInst's as reduction
       // values in our tree.
       if (isa<BinaryOperator>(NextV) || isa<SelectInst>(NextV))
         Stack.push_back(std::make_pair(cast<Instruction>(NextV), 0));
       else if (NextV != Phi)
         return false;
     }
     return true;
   }
 
   /// \brief Attempt to vectorize the tree found by
   /// matchAssociativeReduction.
   bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) {
     if (ReducedVals.empty())
       return false;
 
     unsigned NumReducedVals = ReducedVals.size();

 /// \brief Attempt to reduce a horizontal reduction.
 /// If it is legal to match a horizontal reduction feeding
 /// the phi node P with reduction operators BI, 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 canMatchHorizontalReduction(PHINode *P, BinaryOperator *BI,
                                         BoUpSLP &R, TargetTransformInfo *TTI,
                                         unsigned MinRegSize) {
   if (!ShouldVectorizeHor)
     return false;
 
   HorizontalReduction HorRdx(MinRegSize);
-  if (!HorRdx.matchAssociativeReduction(P, BI))
+  if (!HorRdx.matchAssociativeReduction(P, BI, MinRegSize))
     return false;
 
   // If there is a sufficient number of reduction values, reduce
   // to a nearby power-of-2. Can safely generate oversized
   // vectors and rely on the backend to split them to legal sizes.
   HorRdx.ReduxWidth =
     std::max((uint64_t)4, PowerOf2Floor(HorRdx.numReductionValues()));
 
for (SmallVector<Value *, 4>::iterator IncIt = Incoming.begin(),
              (*SameTypeIt)->getType() == (*IncIt)->getType()) {
         VisitedInstrs.insert(*SameTypeIt);
         ++SameTypeIt;
       }
 
       // Try to vectorize them.
       unsigned NumElts = (SameTypeIt - IncIt);
       DEBUG(errs() << "SLP: Trying to vectorize starting at PHIs (" << NumElts << ")\n");
-      if (NumElts > 1 && tryToVectorizeList(makeArrayRef(IncIt, NumElts), R)) {
-        // Success start over because instructions might have been changed.
+      if (NumElts > 1) {
+        for (unsigned VecRegSize = MaxVecRegSize; VecRegSize >= MinVecRegSize;
+             VecRegSize /= 2) {
+          if (tryToVectorizeList(makeArrayRef(IncIt, NumElts), R, VecRegSize)) {
             HaveVectorizedPhiNodes = true;
             Changed = true;
             break;
           }
-
+        }
+        if (Changed)
+          break;
+      }
       // Start over at the next instruction of a different type (or the end).
       IncIt = SameTypeIt;
     }
   }
 
   VisitedInstrs.clear();
 
   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; it++) {
if (PHINode *P = dyn_cast<PHINode>(it)) {
       Value *Rdx = getReductionValue(DT, P, BB, LI);
 
       // Check if this is a Binary Operator.
       BinaryOperator *BI = dyn_cast_or_null<BinaryOperator>(Rdx);
       if (!BI)
         continue;
 
       // Try to match and vectorize a horizontal reduction.
-      if (canMatchHorizontalReduction(P, BI, R, TTI, MinVecRegSize)) {
+      bool SuccessToMatchHorizontalReduction = false;
+      for (unsigned VecRegSize = MaxVecRegSize; VecRegSize >= MinVecRegSize;
+           VecRegSize /= 2) {
+        if (canMatchHorizontalReduction(P, BI, R, TTI, VecRegSize)) {
+          SuccessToMatchHorizontalReduction = true;
+          break;
+        }
+      }
+      if (SuccessToMatchHorizontalReduction) {
         Changed = true;
         it = BB->begin();
         e = BB->end();
         continue;
       }
 
      Value *Inst = BI->getOperand(0);
       if (Inst == P)
         Inst = BI->getOperand(1);
 
       if (tryToVectorize(dyn_cast<BinaryOperator>(Inst), R)) {
         // We would like to start over since some instructions are deleted
         // and the iterator may become invalid value.
         Changed = true;
         it = BB->begin();
         e = BB->end();
         continue;
       }
 
       continue;
     }
 
     if (ShouldStartVectorizeHorAtStore)
       if (StoreInst *SI = dyn_cast<StoreInst>(it))
         if (BinaryOperator *BinOp =
                 dyn_cast<BinaryOperator>(SI->getValueOperand())) {
+          bool SuccessToMatchHorizontalReduction = false;
+          for (unsigned VecRegSize = MaxVecRegSize; VecRegSize >= MinVecRegSize;
+               VecRegSize /= 2) {
             if (canMatchHorizontalReduction(nullptr, BinOp, R, TTI,
-                                          MinVecRegSize) ||
-              tryToVectorize(BinOp, R)) {
+                                            VecRegSize)) {
+              SuccessToMatchHorizontalReduction = true;
+              break;
+            }
+          }
+          if (SuccessToMatchHorizontalReduction || tryToVectorize(BinOp, R)) {
             Changed = true;
             it = BB->begin();
             e = BB->end();
             continue;
           }
         }
 
     // Try to vectorize horizontal reductions feeding into a return.
for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; it++) {
 
     // 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;
 
       // Vectorize starting with the build vector operands ignoring the
       // BuildVector instructions for the purpose of scheduling and user
       // extraction.
-      if (tryToVectorizeList(BuildVectorOpds, R, BuildVector)) {
+      for (unsigned VecRegSize = MaxVecRegSize; VecRegSize >= MinVecRegSize;
+           VecRegSize /= 2) {
+        if (tryToVectorizeList(BuildVectorOpds, R, VecRegSize, false,
+                               BuildVector, false)) {
           Changed = true;
           it = BB->begin();
           e = BB->end();
+          break;
+        }
       }
-
       continue;
     }
   }
 
   return Changed;
 }
 
 bool SLPVectorizer::vectorizeGEPIndices(BasicBlock *BB, BoUpSLP &R) {
for (unsigned BI = 0, BE = Entry.second.size(); BI < BE; BI += 16) {
           if (isa<SCEVConstant>(SE->getMinusSCEV(SCEVI, SCEVJ))) {
             Candidates.remove(GEPList[I]);
             Candidates.remove(GEPList[J]);
           } else if (GEPI->idx_begin()->get() == GEPJ->idx_begin()->get()) {
             Candidates.remove(GEPList[J]);
           }
         }
       }
 
       // We break out of the above computation as soon as we know there are
       // fewer than two candidates remaining.
       if (Candidates.size() < 2)
         continue;
 
       // Add the single, non-constant index of each candidate to the bundle. We
       // ensured the indices met these constraints when we originally collected
       // the getelementptrs.
for (unsigned BI = 0, BE = Entry.second.size(); BI < BE; BI += 16) {
       // gather-like cases of the form:
       //
       // ... = g[a[0] - b[0]] + g[a[1] - b[1]] + ...
       //
       // where the loads of "a", the loads of "b", and the subtractions can be
       // performed in parallel. It's likely that detecting this pattern in a
       // bottom-up phase will be simpler and less costly than building a
       // full-blown top-down phase beginning at the consecutive loads.
-      Changed |= tryToVectorizeList(Bundle, R);
+      for (unsigned VecRegSize = MaxVecRegSize; VecRegSize >= MinVecRegSize;
+           VecRegSize /= 2) {
+        if (tryToVectorizeList(Bundle, R, VecRegSize)) {
+          Changed = true;
+          break;
+        }
+      }
     }
   }
   return Changed;
 }
 
 bool SLPVectorizer::vectorizeStoreChains(BoUpSLP &R) {
   bool Changed = false;
   // Attempt to sort and vectorize each of the store-groups.
   for (StoreListMap::iterator it = Stores.begin(), e = Stores.end(); it != e;
        ++it) {
     if (it->second.size() < 2)
       continue;
 
     DEBUG(dbgs() << "SLP: Analyzing a store chain of length "
           << it->second.size() << ".\n");
 
     // Process the stores in chunks of 16.
     // TODO: The limit of 16 inhibits greater vectorization factors.
     //       For example, AVX2 supports v32i8. Increasing this limit, however,
     //       may cause a significant compile-time increase.
     for (unsigned CI = 0, CE = it->second.size(); CI < CE; CI+=16) {
       unsigned Len = std::min<unsigned>(CE - CI, 16);
-      Changed |= vectorizeStores(makeArrayRef(&it->second[CI], Len),
-                                 -SLPCostThreshold, R);
+      Changed |= vectorizeStores(makeArrayRef(&it->second[CI], Len), R);
     }
   }
   return Changed;
 }
 
 } // end anonymous namespace
 
 char SLPVectorizer::ID = 0;
 static const char lv_name[] = "SLP Vectorizer";
 INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 INITIALIZE_PASS_DEPENDENCY(DemandedBits)
 INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false)
 
 namespace llvm {
 Pass *createSLPVectorizerPass() { return new SLPVectorizer(); }
 }

test/Transforms/SLPVectorizer/AArch64/slp-vectorized-from-max-to-min.ll

+;RUN: opt -S -slp-vectorizer -slp-max-reg-size=128 -slp-min-reg-size=64 -slp-threshold=-13 < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+; CHECK: @foo
+; CHECK: add nsw  <2 x i64>
+; CHECK: add nsw  <2 x i64>
+
+define i64 @foo(i64* nocapture readonly %a) #0 {
+entry:
+  %idx1 = getelementptr inbounds i64, i64* %a, i64 1
+  %idx2 = getelementptr inbounds i64, i64* %a, i64 2
+  %idx3 = getelementptr inbounds i64, i64* %a, i64 3
+  %idx4 = getelementptr inbounds i64, i64* %a, i64 4
+  %idx5 = getelementptr inbounds i64, i64* %a, i64 5
+  %idx6 = getelementptr inbounds i64, i64* %a, i64 6
+  %idx7 = getelementptr inbounds i64, i64* %a, i64 7
+  %0 = load i64, i64* %a, align 4
+  %1 = load i64, i64* %idx1, align 4
+  %2 = load i64, i64* %idx2, align 4
+  %3 = load i64, i64* %idx3, align 4
+  %4 = load i64, i64* %idx4, align 4
+  %5 = load i64, i64* %idx5, align 4
+  %6 = load i64, i64* %idx6, align 4
+  %7 = load i64, i64* %idx7, align 4
+  %add = add nsw i64 %1, %0
+  %add1 = add nsw i64 %3, %2
+  %add2 = add nsw i64 %5, %4
+  %add3 = add nsw i64 %7, %6
+  %add8 = add nsw i64 %add1, %add
+  %add9 = add nsw i64 %add3, %add2
+  %add12 = add nsw i64 %add9, %add8
+  ret i64 %add12
+}
+
+