[LV] Cost model for out-of-loop reductions

[anna]

Summary

When we have small trip count loops, the cost of out of loop reduction
becomes significant. We do not consider the cost of out of loop
reductions in loop vectorizer (in-loop vectorizations are handled in
cost modelling).

This patch extends the logic used by cost modelling of runtime checks to figure out the minimum trip count under which runtime checks are profitable. We reuse the same idea for out of loop reductions.

[dmgreen]

Sounds OK to me. Did you consider including the cost of reductions in the existing vectorizer cost calculations, as opposed to a hard limit?

[fhahn]

From the description, it is not clear why FMinimum/FMaximum reductions in particular should be a blocker for vectorizing small trip count loops. What about other reductions?

Given that this is for short trip counts, it might be better/more general to extend the code that computes the minimum trip count needs to negate the overhead of runtime checks to also consider the overhead of computing the final reduction value (see https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp#L10047)

[nikic]

In D154157#4468183, @fhahn wrote:

From the description, it is not clear why FMinimum/FMaximum reductions in particular should be a blocker for vectorizing small trip count loops. What about other reductions?

Given that this is for short trip counts, it might be better/more general to extend the code that computes the minimum trip count needs to negate the overhead of runtime checks to also consider the overhead of computing the final reduction value (see https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp#L10047)

Maybe this generalized version would also fix https://github.com/llvm/llvm-project/issues/57476.

[ebrevnov]

I support Florian's suggestion. We better take reduction overhead into account the same way as we did for runtime checks.
Today's cost model is very limited in its ability to predict the overhead which comes with the vectorization. For example, the overhead of the scalar epilogue loop is simply ignored. I think, one day we should generalize the cost model so that vectorization overhead is integral part of the model itself rather than a follow up "fix up".

[anna]

thank you Florian, this is a nice idea. Working on it.

[anna]

Rewrote the patch to extend existing logic for runtime checks calculation.
This now supports all kinds of out of loop reductions. Since we compute an upper-bound on MinProfitableTripCount, this maybe a more conservative estimate.

[anna]

added an option which switches this off by default. The failures above are related to ARM and RISCV targets.

[anna]

Gentle ping @fhahn. Anything I could do to move this forward? I have kept the option as off by default, since I would need to help to test this on supported targets upstream. It helps our use-case where loops are not vectorized when out-of-loop reductions are present in small trip count loops.
There maybe some fallouts where correction in reductions cost modelling will be required.

[fhahn]

In D154157#4628496, @anna wrote:

Gentle ping @fhahn. Anything I could do to move this forward? I have kept the option as off by default, since I would need to help to test this on supported targets upstream. It helps our use-case where loops are not vectorized when out-of-loop reductions are present in small trip count loops.
There maybe some fallouts where correction in reductions cost modelling will be required.

What are the regressions on ARM/RISCV? I think we should aim to enable this by default for all platforms, otherwise it is at the risk of not getting enabled. Also, those tests may show issues with the current implementation.

Do you have any numbers on the impact on X86?

[anna]

changed the flag to on by default. Fixed the ARM/RISCV tests (by updating the lines). More details will follow.

[anna]

In D154157#4628521, @fhahn wrote:

In D154157#4628496, @anna wrote:

Gentle ping @fhahn. Anything I could do to move this forward? I have kept the option as off by default, since I would need to help to test this on supported targets upstream. It helps our use-case where loops are not vectorized when out-of-loop reductions are present in small trip count loops.
There maybe some fallouts where correction in reductions cost modelling will be required.

What are the regressions on ARM/RISCV? I think we should aim to enable this by default for all platforms, otherwise it is at the risk of not getting enabled. Also, those tests may show issues with the current implementation.

The regressions on ARM and RISCV are because we have an updated minimum trip count we expect (to offset the cost of the out-of-loop reductions), so the CHECK lines have been updated accordingly. RISCV looks okay with the minimum trip count being at least 4 or 8 (we round the MinimumTripCount up to VF, so it is more conservative).

However, in the case of ARM, there is no special cost for min/max reductions. They compute a pretty expensive cost under the assumption that we expand these reductions and extract the value. On some simple tests I ran, the assembly generated supports this cost for the -mtriple=armv7-none-eabi, but the code generated is different for another triple such as -mtriple=thumbv8.1m.main-none-none-eabi. I've added more details under the respective test.

Do you have any numbers on the impact on X86?

I will have some numbers soon. The tests are still running. We see positive impact on small trip count loops on our workloads (in the range of 40% improvement) - these workloads are small trip count loops with fminimum/fmaximum reductions where we no longer vectorize.

llvm/test/Transforms/LoopVectorize/ARM/tail-fold-multiple-icmps.ll

12 ↗

(On Diff #555134)

This minimum trip count of 56 comes about because we compute the reduction cost as 140 (and there are two such reductions, with total being 280).
This is a pretty high cost which is computed through https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/CodeGen/BasicTTIImpl.h#L2372.
This is correct for a triple with mattr such as:

llc < %s -mtriple=armv7-none-eabi -float-abi=hard -mattr=+neon -verify-machineinstrs | FileCheck %s

define i8 @test_umin_v8i8(<8 x i8> %x) {
; CHECK-LABEL: test_umin_v8i8:
; CHECK:       @ %bb.0: @ %entry
; CHECK-NEXT:    vpmin.u8 d16, d0, d0
; CHECK-NEXT:    vpmin.u8 d16, d16, d16
; CHECK-NEXT:    vpmin.u8 d16, d16, d16
; CHECK-NEXT:    vmov.u8 r0, d16[0]
; CHECK-NEXT:    bx lr
entry:
  %z = call i8 @llvm.vector.reduce.umin.v8i8(<8 x i8> %x) 
  ret i8 %z
}

However, I'm not sure if this is a correct cost for other triples.

[dmgreen]

I can look into the Arm costs. Some of them were deliberately high to try and stop bad vectorization from happening (or they haven't come up much in the past).

[dmgreen]

I've made some changes for the Arm MVE and NEON costs. Can you try a rebase? Thanks

[anna]

In D154157#4638288, @dmgreen wrote:

I've made some changes for the Arm MVE and NEON costs. Can you try a rebase? Thanks

Thanks @dmgreen! The updated MinTripCount looks better now (4 instead of 56). I will update the patch.

[anna]

Our X86 results are in. Over 244 workloads, the geomean changes by about ~0.4%. Looking at individual workloads, there are no major gains or regressions in large applications (unfortunately, we cannot share the exact benchmark names publicly). However, we do see big gains in 3 of these workloads where it performs a floating point minimum/maximum reduction over a float array of 3 elements (without this change we were vectorizing it).
Overall, I think the change is still reasonable to have since we now account for out of loop reductions more accurately.

Also, based on the RISCV and ARM results, we can see the minimum trip count is more reasonable numbers (4 or 8 for both targets). I will update the rebased patch.

[anna]

rebased over changes from dmgreen with more accurate costs for ARM out-of-loop reductions.

[anna]

ping?

[anna]

Any comments to progress this further?

[nikic]

Would you mind testing whether this also fixes https://github.com/llvm/llvm-project/issues/57476 and adding it as a test case if so?

[anna]

In D154157#4648096, @nikic wrote:

Would you mind testing whether this also fixes https://github.com/llvm/llvm-project/issues/57476 and adding it as a test case if so?

Unfortunately, it doesn't help when the trip count is exactly specified at compile time. However, if it is through a branch weight profile (having same behaviour as trip-count=2), with this patch we no longer vectorize ctpop. The reason is that when exact trip count =2, we clamp the max VF to be exactly 2, the reduction cost = 1 and we still vectorize. With branch profile stating trip count will be 2, we go through VF=4 and without the patch we end up vectorizing with masked vector instructions. With the patch, the vector reduce.add with VF=4 ends up being costlier for the small trip count loop and we avoid vectorizing. I will add both test cases to show the difference.

[anna]

Added ctpop test

[anna]

Ping.

[dmgreen]

I ran some tests and they looked OK. Sometimes these RuntimeChecks costs need to be quite precise - more precise than they have needed to be for vectorization in the past, and it can end up with cases where you spend some of the overhead costs of vectorization without getting the benefits, but the results looks good from what I can tell.

I might regret mentioning this if it increases the costs, but should interleaved loops get an extra cost to account for reducing the vectors by UF, into a single vector that is then vec.reduced?

[anna]

Thanks for testing the patch @dmgreen!

I might regret mentioning this if it increases the costs, but should interleaved loops get an extra cost to account for reducing the vectors by UF, into a single vector that is then vec.reduced?

That's a good point, I think there is a higher chance of "touching a lot more cases" on vectorization :) but it seems that can be done as a later patch, if needed?

[dmgreen]

Yeah that sounds OK to me. I think the extra cost should be fairly minor.

This LGTM if no-one else has any other comments.

[nikic]

Any particular reason this hasn't been landed yet?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

static cl::opt<unsigned> TinyTripCountVectorThreshold(
     cl::desc("Loops with a constant trip count that is smaller than this "
              "value are vectorized only if no scalar iteration overheads "
              "are incurred."));
 
 static cl::opt<unsigned> VectorizeMemoryCheckThreshold(
     "vectorize-memory-check-threshold", cl::init(128), cl::Hidden,
     cl::desc("The maximum allowed number of runtime memory checks"));
 
+static cl::opt<bool> IgnoreOutOfLoopReductionCost(
+    "vectorizer-ignore-out-of-loop-reduction-cost", cl::init(true),
+    cl::desc("Ignore the cost of out-of-loop reductions in vectorizer cost "
+             "model"));
+
 // Option prefer-predicate-over-epilogue indicates that an epilogue is undesired,
 // that predication is preferred, and this lists all options. I.e., the
 // vectorizer will try to fold the tail-loop (epilogue) into the vector body
 // and predicate the instructions accordingly. If tail-folding fails, there are
 // different fallback strategies depending on these values:
 namespace PreferPredicateTy {
   enum Option {
     ScalarEpilogue = 0,
public:
 
   bool hasPredStores() const { return NumPredStores > 0; }
 
   /// Returns true if epilogue vectorization is considered profitable, and
   /// false otherwise.
   /// \p VF is the vectorization factor chosen for the original loop.
   bool isEpilogueVectorizationProfitable(const ElementCount VF) const;
 
+  /// Returns total cost for out-of-loop reductions.
+  InstructionCost getOutOfLoopReductionCost(VectorizationFactor VF);
+
 private:
   unsigned NumPredStores = 0;
 
   /// \return An upper bound for the vectorization factors for both
   /// fixed and scalable vectorization, where the minimum-known number of
   /// elements is a power-of-2 larger than zero. If scalable vectorization is
   /// disabled or unsupported, then the scalable part will be equal to
   /// ElementCount::getScalable(0).
assert(!Legal->isMaskRequired(I) &&
            "Reverse masked interleaved access not supported.");
     Cost += Group->getNumMembers() *
             TTI.getShuffleCost(TargetTransformInfo::SK_Reverse, VectorTy,
                                std::nullopt, CostKind, 0);
   }
   return Cost;
 }
 
+InstructionCost
+LoopVectorizationCostModel::getOutOfLoopReductionCost(VectorizationFactor VF) {
+  InstructionCost ReduxCost = 0;
+  if (VF.Width.isScalar() || IgnoreOutOfLoopReductionCost)
+    return ReduxCost;
+
+  TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
+  for (auto &Reduction : Legal->getReductionVars()) {
+    PHINode *Phi = Reduction.first;
+    auto *VectorTy = cast<VectorType>(ToVectorTy(Phi->getType(), VF.Width));
+    const RecurrenceDescriptor &RdxDesc = Reduction.second;
+    if (isInLoopReduction(Phi))
+      continue;
+    RecurKind RK = RdxDesc.getRecurrenceKind();
+    auto FMF = RdxDesc.getFastMathFlags();
+    switch (RK) {
+    case RecurKind::Add:
+    case RecurKind::Mul:
+    case RecurKind::Or:
+    case RecurKind::And:
+    case RecurKind::Xor:
+    case RecurKind::FAdd:
+    case RecurKind::FMul: {
+      unsigned RdxOpcode = RecurrenceDescriptor::getOpcode(RK);
+      ReduxCost +=
+          TTI.getArithmeticReductionCost(RdxOpcode, VectorTy, FMF, CostKind);
+      break;
+    }
+    case RecurKind::FMax:
+    case RecurKind::FMin:
+    case RecurKind::FMaximum:
+    case RecurKind::FMinimum:
+    case RecurKind::SMax:
+    case RecurKind::SMin:
+    case RecurKind::UMax:
+    case RecurKind::UMin: {
+      Intrinsic::ID Id = getMinMaxReductionIntrinsicOp(RK);
+      ReduxCost += TTI.getMinMaxReductionCost(Id, VectorTy, FMF, CostKind);
+      break;
+    }
+    case RecurKind::FMulAdd: {
+      unsigned RdxOpcode = RecurrenceDescriptor::getOpcode(RK);
+      ReduxCost +=
+          TTI.getArithmeticReductionCost(RdxOpcode, VectorTy, FMF, CostKind);
+      // For a call to the llvm.fmuladd intrinsic we need to add the cost of a
+      // normal fmul instruction to the cost of the fadd reduction.
+      ReduxCost +=
+          TTI.getArithmeticInstrCost(Instruction::FMul, VectorTy, CostKind);
+      break;
+    }
+    case RecurKind::FAnyOf:
+    case RecurKind::IAnyOf: {
+      // This has the cost of vector.reduce.or, but may have other costs as
+      // well. FIXME: This recur kind does not have a well defined cost yet.
+      unsigned RdxOpcode = RecurrenceDescriptor::getOpcode(RecurKind::Or);
+      ReduxCost +=
+          TTI.getArithmeticReductionCost(RdxOpcode, VectorTy, FMF, CostKind);
+      break;
+    }
+    default:
+      llvm_unreachable("Unexpected reduction operation!");
+    }
+  }
+  return ReduxCost;
+}
+
 std::optional<InstructionCost>
 LoopVectorizationCostModel::getReductionPatternCost(
     Instruction *I, ElementCount VF, Type *Ty, TTI::TargetCostKind CostKind) {
   using namespace llvm::PatternMatch;
   // Early exit for no inloop reductions
   if (InLoopReductions.empty() || VF.isScalar() || !isa<VectorType>(Ty))
     return std::nullopt;
   auto *VectorTy = cast<VectorType>(Ty);
if (isa<FPExtInst>(I) && EmittedRemark.insert(I).second)
       });
 
     for (Use &Op : I->operands())
       if (auto *OpI = dyn_cast<Instruction>(Op))
         Worklist.push_back(OpI);
   }
 }
 
-static bool areRuntimeChecksProfitable(GeneratedRTChecks &Checks,
-                                       VectorizationFactor &VF,
-                                       std::optional<unsigned> VScale, Loop *L,
-                                       ScalarEvolution &SE) {
-  InstructionCost CheckCost = Checks.getCost();
+// What makes the loop unprofitable to vectorize.
+namespace OutOfLoopCost {
+enum Reason {
+  None, // OutOfLoopCost is zero.
+  RuntimeCheck,
+  OutOfLoopReduction,
+  Some // Combination of above reasons: We have both runtime checks and out of
+       // loop reductions.
+};
+}
+
+static OutOfLoopCost::Reason areOutOfLoopComputationsProfitable(
+    InstructionCost CheckCost, InstructionCost ReduxCost,
+    VectorizationFactor &VF, std::optional<unsigned> VScale, Loop *L,
   if (!CheckCost.isValid())
-    return false;
+    return OutOfLoopCost::RuntimeCheck;
 
+  auto ReduxCostVal = *ReduxCost.getValue();
+  double RtC = *CheckCost.getValue();
+  if (!ReduxCostVal && !RtC)
+    return OutOfLoopCost::None;
   // When interleaving only scalar and vector cost will be equal, which in turn
   // would lead to a divide by 0. Fall back to hard threshold.
   if (VF.Width.isScalar()) {
     if (CheckCost > VectorizeMemoryCheckThreshold) {
       LLVM_DEBUG(
           dbgs()
           << "LV: Interleaving only is not profitable due to runtime checks\n");
-      return false;
+      return OutOfLoopCost::RuntimeCheck;
     }
-    return true;
+    if (ReduxCostVal) {
+      LLVM_DEBUG(dbgs() << "Interleaving only is not profitable due to out of "
+                           "loop reductions\n");
+      return OutOfLoopCost::OutOfLoopReduction;
+    }
+    return OutOfLoopCost::None;
   }
 
-  // The scalar cost should only be 0 when vectorizing with a user specified VF/IC. In those cases, runtime checks should always be generated.
+  // The scalar cost should only be 0 when vectorizing with a user specified
+  // VF/IC. In those cases, ignore out of loop costs.
   double ScalarC = *VF.ScalarCost.getValue();
   if (ScalarC == 0)
-    return true;
+    return OutOfLoopCost::None;
 
   // First, compute the minimum iteration count required so that the vector
   // loop outperforms the scalar loop.
   //  The total cost of the scalar loop is
   //   ScalarC * TC
   //  where
   //  * TC is the actual trip count of the loop.
   //  * ScalarC is the cost of a single scalar iteration.
   //
   //  The total cost of the vector loop is
-  //    RtC + VecC * (TC / VF) + EpiC
+  //    RtC + VecC * (TC / VF) + EpiC + ReduxCost
   //  where
   //  * RtC is the cost of the generated runtime checks
   //  * VecC is the cost of a single vector iteration.
   //  * TC is the actual trip count of the loop
   //  * VF is the vectorization factor
   //  * EpiCost is the cost of the generated epilogue, including the cost
   //    of the remaining scalar operations.
+  //  * ReduxCost is the cost of out-of-loop reductions which are executed if
+  //    the vector loop is taken.
   //
   // Vectorization is profitable once the total vector cost is less than the
   // total scalar cost:
-  //   RtC + VecC * (TC / VF) + EpiC <  ScalarC * TC
+  //   RtC + VecC * (TC / VF) + EpiC +ReduxCost <  ScalarC * TC
   //
   // Now we can compute the minimum required trip count TC as
-  //   (RtC + EpiC) / (ScalarC - (VecC / VF)) < TC
+  //   (RtC + EpiC + ReduxCost) / (ScalarC - (VecC / VF)) < TC
   //
   // For now we assume the epilogue cost EpiC = 0 for simplicity. Note that
   // the computations are performed on doubles, not integers and the result
   // is rounded up, hence we get an upper estimate of the TC.
   unsigned IntVF = VF.Width.getKnownMinValue();
   if (VF.Width.isScalable()) {
     unsigned AssumedMinimumVscale = 1;
     if (VScale)
       AssumedMinimumVscale = *VScale;
     IntVF *= AssumedMinimumVscale;
   }
   double VecCOverVF = double(*VF.Cost.getValue()) / IntVF;
-  double RtC = *CheckCost.getValue();
-  double MinTC1 = RtC / (ScalarC - VecCOverVF);
+  double MinTC1 = (RtC + ReduxCostVal) / (ScalarC - VecCOverVF);
 
   // Second, compute a minimum iteration count so that the cost of the
   // runtime checks is only a fraction of the total scalar loop cost. This
   // adds a loop-dependent bound on the overhead incurred if the runtime
   // checks fail. In case the runtime checks fail, the cost is RtC + ScalarC
   // * TC. To bound the runtime check to be a fraction 1/X of the scalar
   // cost, compute
   //   RtC < ScalarC * TC * (1 / X)  ==>  RtC * X / ScalarC < TC
+  // Note that we can ignore ReduxCost here since out-of-loop reductions are
+  // computed only if the vector loop is taken. 
   double MinTC2 = RtC * 10 / ScalarC;
 
   // Now pick the larger minimum. If it is not a multiple of VF, choose the
   // next closest multiple of VF. This should partly compensate for ignoring
   // the epilogue cost.
   uint64_t MinTC = std::ceil(std::max(MinTC1, MinTC2));
   VF.MinProfitableTripCount = ElementCount::getFixed(alignTo(MinTC, IntVF));
 
-  LLVM_DEBUG(
-      dbgs() << "LV: Minimum required TC for runtime checks to be profitable:"
+  LLVM_DEBUG(dbgs() << "LV: Minimum required TC for out-of-loop computations "
+                       "to be profitable:"
                     << VF.MinProfitableTripCount << "\n");
 
   // Skip vectorization if the expected trip count is less than the minimum
   // required trip count.
   if (auto ExpectedTC = getSmallBestKnownTC(SE, L)) {
     if (ElementCount::isKnownLT(ElementCount::getFixed(*ExpectedTC),
                                 VF.MinProfitableTripCount)) {
       LLVM_DEBUG(dbgs() << "LV: Vectorization is not beneficial: expected "
                            "trip count < minimum profitable VF ("
                         << *ExpectedTC << " < " << VF.MinProfitableTripCount
                         << ")\n");
 
-      return false;
+      // If possible, return the exact reason we cannot vectorize the small trip
+      // count loop.
+      return (!RtC)            ? OutOfLoopCost::OutOfLoopReduction
+             : !(ReduxCostVal) ? OutOfLoopCost::RuntimeCheck
+                               : OutOfLoopCost::Some;
     }
   }
-  return true;
+  return OutOfLoopCost::None;
 }
 
 LoopVectorizePass::LoopVectorizePass(LoopVectorizeOptions Opts)
     : InterleaveOnlyWhenForced(Opts.InterleaveOnlyWhenForced ||
                                !EnableLoopInterleaving),
       VectorizeOnlyWhenForced(Opts.VectorizeOnlyWhenForced ||
                               !EnableLoopVectorization) {}
 
if (MaybeVF) {
     IC = CM.selectInterleaveCount(VF.Width, VF.Cost);
 
     unsigned SelectedIC = std::max(IC, UserIC);
     //  Optimistically generate runtime checks if they are needed. Drop them if
     //  they turn out to not be profitable.
     if (VF.Width.isVector() || SelectedIC > 1)
       Checks.Create(L, *LVL.getLAI(), PSE.getPredicate(), VF.Width, SelectedIC);
 
-    // Check if it is profitable to vectorize with runtime checks.
+    // Check if it is profitable to vectorize with out of loop computations
+    // (such as reductions and runtime checks).
     bool ForceVectorization =
         Hints.getForce() == LoopVectorizeHints::FK_Enabled;
-    if (!ForceVectorization &&
-        !areRuntimeChecksProfitable(Checks, VF, getVScaleForTuning(L, *TTI), L,
-                                    *PSE.getSE())) {
+    if (!ForceVectorization) {
+      InstructionCost RTCheckCost = Checks.getCost();
+      InstructionCost ReduxCost = CM.getOutOfLoopReductionCost(VF);
+
+      auto UnprofitableReason = areOutOfLoopComputationsProfitable(
+          RTCheckCost, ReduxCost, VF, getVScaleForTuning(L, *TTI), L,
+          *PSE.getSE());
+      switch (UnprofitableReason) {
+      case OutOfLoopCost::None:
+        break;
+      case OutOfLoopCost::RuntimeCheck: {
         ORE->emit([&]() {
           return OptimizationRemarkAnalysisAliasing(
                      DEBUG_TYPE, "CantReorderMemOps", L->getStartLoc(),
                      L->getHeader())
                  << "loop not vectorized: cannot prove it is safe to reorder "
                     "memory operations";
         });
         LLVM_DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
         Hints.emitRemarkWithHints();
         return false;
       }
+      case OutOfLoopCost::OutOfLoopReduction:
+        LLVM_DEBUG(dbgs() << "LV: Costly out of loop reductions for small "
+                             "trip count loop.\n");
+        return false;
+      default:
+        LLVM_DEBUG(dbgs() << "LV: Costly out of loop computation for small "
+                             "trip count loop.\n");
+        return false;
+      }
+    }// ForceVectorization
   }
 
   // Identify the diagnostic messages that should be produced.
   std::pair<StringRef, std::string> VecDiagMsg, IntDiagMsg;
   bool VectorizeLoop = true, InterleaveLoop = true;
   if (VF.Width.isScalar()) {
     LLVM_DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n");
     VecDiagMsg = std::make_pair(

llvm/test/Transforms/LoopVectorize/X86/reduction-small-trip-count.ll

+; RUN: opt -S -passes=loop-vectorize,dce -mcpu=skylake -vectorizer-ignore-out-of-loop-reduction-cost=0 -force-vector-interleave=1  < %s | FileCheck %s
+target triple = "x86_64-unknown-linux-gnu"
+
+declare float @llvm.maximum.f32(float, float)
+declare float @llvm.fabs.f32(float)
+
+; This is a small trip count loop. The cost of the out-of-loop reduction is
+; significant in this case when we only perform a single vector iteration.  
+; However, loop vectorizer does not consider out of loop reduction costs.
+
+; CHECK-LABEL: fmaximum_intrinsic
+; CHECK-NOT: llvm.vector.reduce.fmaximum 
+define float @fmaximum_intrinsic(ptr nocapture readonly %x, ptr nocapture readonly %y, i32 %n, i32 %tc) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %i.012 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %s.011 = phi float [ 0.000000e+00, %entry ], [ %max, %for.body ]
+  %arrayidx = getelementptr inbounds float, ptr %x, i32 %i.012
+  %x_f = load float, ptr %arrayidx, align 4
+  %arrayidxy = getelementptr inbounds float, ptr %y, i32 %i.012
+  %y_f = load float, ptr %arrayidxy, align 4
+  %sub = fsub float %x_f, %y_f
+  %fabs = call float @llvm.fabs.f32(float %sub)
+  %max = tail call float @llvm.maximum.f32(float %s.011, float %fabs)
+  %inc = add nuw nsw i32 %i.012, 1
+  %exitcond = icmp ult i32 %inc, 3
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret float %max
+}
+
+; trip count of 6 is still considered non-profitable for reducing adds (min trip
+; count required is 8).
+; CHECK-LABEL: reduction_sum
+; CHECK-NOT: llvm.vector.reduce.add
+define i32 @reduction_sum(i32 %n, ptr noalias nocapture %A, ptr noalias nocapture %B) nounwind uwtable readonly noinline ssp {
+  %1 = icmp sgt i32 %n, 0
+  br i1 %1, label %.lr.ph, label %._crit_edge
+
+.lr.ph:                                           ; preds = %0, %.lr.ph
+  %indvars.iv = phi i64 [ %indvars.iv.next, %.lr.ph ], [ 0, %0 ]
+  %sum.02 = phi i32 [ %9, %.lr.ph ], [ 0, %0 ]
+  %2 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
+  %3 = load i32, ptr %2, align 4
+  %4 = getelementptr inbounds i32, ptr %B, i64 %indvars.iv
+  %5 = load i32, ptr %4, align 4
+  %6 = trunc i64 %indvars.iv to i32
+  %7 = add i32 %sum.02, %6
+  %8 = add i32 %7, %3
+  %9 = add i32 %8, %5
+  %indvars.iv.next = add i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %._crit_edge, label %.lr.ph, !prof !1
+
+._crit_edge:                                      ; preds = %.lr.ph, %0
+  %sum.0.lcssa = phi i32 [ 0, %0 ], [ %9, %.lr.ph ]
+  ret i32 %sum.0.lcssa
+}
+
+; CHECK-LABEL: reduction_mix
+; CHECK-LABEL: middle.block:
+; CHECK-NEXT: vector.reduce.add 
+; CHECK-NEXT: br
+define i32 @reduction_mix(i32 %n, ptr noalias nocapture %A, ptr noalias nocapture %B) nounwind uwtable readonly noinline ssp {
+  %1 = icmp sgt i32 %n, 0
+  br i1 %1, label %.lr.ph, label %._crit_edge
+
+.lr.ph:                                           ; preds = %0, %.lr.ph
+  %indvars.iv = phi i64 [ %indvars.iv.next, %.lr.ph ], [ 0, %0 ]
+  %sum.02 = phi i32 [ %9, %.lr.ph ], [ 0, %0 ]
+  %2 = getelementptr inbounds i32, ptr %A, i64 %indvars.iv
+  %3 = load i32, ptr %2, align 4
+  %4 = getelementptr inbounds i32, ptr %B, i64 %indvars.iv
+  %5 = load i32, ptr %4, align 4
+  %6 = mul nsw i32 %5, %3
+  %7 = trunc i64 %indvars.iv to i32
+  %8 = add i32 %sum.02, %7
+  %9 = add i32 %8, %6
+  %indvars.iv.next = add i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %._crit_edge, label %.lr.ph, !prof !2
+
+._crit_edge:                                      ; preds = %.lr.ph, %0
+  %sum.0.lcssa = phi i32 [ 0, %0 ], [ %9, %.lr.ph ]
+  ret i32 %sum.0.lcssa
+}
+
+!1 = !{!"branch_weights", i32 1, i32 5}
+!2 = !{!"branch_weights", i32 1, i32 7}