[LV] Create RT checks once VF/IC are selected, track scalar cost.

[fhahn]

Summary

This patch updates LV to generate runtime after the VF & IC are selected. It
allows deciding whether to vectorize with runtime checks or not based on
their cost compared to the vector loop.

It also updates VectorizationFactor to include the scalar cost.

[lebedev.ri]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8085

Please make 0.005 an option

[lebedev.ri]

Reverse-ping, thanks.
Anything to get this going?

[fhahn]

rebase.

With the linked dependent patches, this should now successfully build test-suite with MultiSource/SPEC2000/SPEC2006.

This leads to additional vectorization with runtime checks in a few more cases:

Same hash: 223 (filtered out)
Remaining: 14
Metric: loop-vectorize.LoopsVectorized

Program patch1 patch2 diff
test-suite...Source/Benchmarks/sim/sim.test 5.00 8.00 60.0%
test-suite...rks/FreeBench/pifft/pifft.test 33.00 47.00 42.4%
test-suite...chmarks/Rodinia/srad/srad.test 3.00 4.00 33.3%
test-suite...CFP2000/177.mesa/177.mesa.test 379.00 417.00 10.0%
test-suite...CI_Purple/SMG2000/smg2000.test 78.00 84.00 7.7%
test-suite...pps-C/SimpleMOC/SimpleMOC.test 39.00 42.00 7.7%
test-suite...oxyApps-C/miniGMG/miniGMG.test 42.00 44.00 4.8%
test-suite.../CINT2000/176.gcc/176.gcc.test 97.00 100.00 3.1%
test-suite...006/450.soplex/450.soplex.test 88.00 90.00 2.3%
test-suite...lications/ClamAV/clamscan.test 91.00 93.00 2.2%
test-suite...pplications/oggenc/oggenc.test 130.00 132.00 1.5%
test-suite...006/447.dealII/447.dealII.test 958.00 970.00 1.3%

[fhahn]

Rebased on top of current trunk. This version now can build MultiSource/SPEC2006/SPEC2000 with -O3 -flto without crashing.

The current version leads to a few more vectorized loops in some benchmarks:

Tests: 236
Same hash: 200 (filtered out)
Remaining: 36
Metric: loop-vectorize.LoopsVectorized

Program                                        base   patch.lv-mem-cost diff
 test-suite...Source/Benchmarks/sim/sim.test     5.00   8.00            60.0%
 test-suite...chmarks/Rodinia/srad/srad.test     3.00   4.00            33.3%
 test-suite...rks/FreeBench/pifft/pifft.test    33.00  43.00            30.3%
 test-suite...CFP2000/177.mesa/177.mesa.test   386.00 424.00             9.8%
 test-suite...CI_Purple/SMG2000/smg2000.test    77.00  83.00             7.8%
 test-suite...pps-C/SimpleMOC/SimpleMOC.test    39.00  42.00             7.7%
 test-suite...oxyApps-C/miniGMG/miniGMG.test    44.00  46.00             4.5%
 test-suite.../CINT2000/176.gcc/176.gcc.test    99.00 102.00             3.0%
 test-suite...006/450.soplex/450.soplex.test    88.00  90.00             2.3%
 test-suite...lications/ClamAV/clamscan.test    97.00  99.00             2.1%
 test-suite...pplications/oggenc/oggenc.test   151.00 153.00             1.3%
 test-suite...006/447.dealII/447.dealII.test   970.00 982.00             1.2%

[fhahn]

rebase on top of the recent changes.

[fhahn]

rebase

[fhahn]

Rebased after recent changes to D75980

[fhahn]

Ping.

All dependent patches have been submitted now. I also pre-committed a simplified version of the test cases in 0cb9d8acbccb.

The update also adds an option to control the threshold.

[xbolva00]

llvm/test/Transforms/LoopVectorize/AArch64/runtime-check-size-based-threshold.ll

9

is too small?

[fhahn]

Fix wording in test comments, thanks!

[ebrevnov]

You better remove (WIP) suffix if this patch is ready for review. Otherwise people may think it still in progress...

[lebedev.ri]

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

265–266

Hm, why does PragmaThresholdReached not check for Hints.allowReordering()?
If i really asked for loop to be vectorized, why are there further limits on the sanity checks?
Or, for that matter, doesn't forcing vectorization disable those checks in the first place?

[ebrevnov]

I'd like to understand why you chose to go the way it is instead of taking cost of runtime checks into account in the cost model itself? To me, the cost model is the right place for that. I would expect to see something similar to what I did in https://reviews.llvm.org/D71053 for LoopVectorizationPlanner::mayDisregardRTChecksOverhead

[fhahn]

In D75981#2605728, @ebrevnov wrote:

I'd like to understand why you chose to go the way it is instead of taking cost of runtime checks into account in the cost model itself? To me, the cost model is the right place for that. I would expect to see something similar to what I did in https://reviews.llvm.org/D71053 for LoopVectorizationPlanner::mayDisregardRTChecksOverhead

That's a good point. I initially tried to keep things as closely modeled to the original code. I think the way the number of runtime checks is handled in LoopVectorizationRequirements is not ideal and makes things more difficult to follow. I am also not sure why those checks are handled separately (in doesNotMeet). I tried to see if we can remove doesNotMeet and instead move the checks at an earlier and more appropriate place.

I put up D98634 and D98633 to remove doesNotMeet, which moved the decision whether to vectorize with RT checks to LVP::plan(). I also updated this patch to make the cost-based decision in LVP::plan. From there it should be easy to adjust it further to use it for more cost-based decisions, as in your patch. Is this more in line what you had in mind?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

265–266

I can't really comment much on why the existing code does what it does. But it is indeed surprising that runtime checks can block vectorization if a width is explicitly set. I put up D98634 and D98633 to move the doesNotMeet restrictions to what seems more appropriate places to me. The updated code also skips the checks if an explicit VF is forced by the user.

I updated the code in this patch to always use the cost-based check if a constant TC is available here.

[fhahn]

Rebase & ping.

All dependent patches have been submitted and the decision is now made during planning.

[lebedev.ri]

LGTM.
As with other patches, i'm not the best reviewer for this, but clearly others are otherwise preoccupied.

This isn't the final form, i think this part is reasonably safe step.
Things can and will be adjusted further later.

[ebrevnov]

I don't really understand why we need this separate heuristic for runtime checks. Why don't we simply add cost of runtime checks (possibly with some small scaling to be safe) to total cost of vector loop and just use existing cost model to decide?

Please add regression tests from https://reviews.llvm.org/D71053 to this change set as well.

[lebedev.ri]

Reverse ping, thanks.

[lebedev.ri]

@fhahn Reverse ping, thanks :)

In D75981#2688505, @lebedev.ri wrote:

Reverse ping, thanks.

[lebedev.ri]

@fhahn Reverse ping, thanks :)

In D75981#2702505, @lebedev.ri wrote:

@fhahn Reverse ping, thanks :)

In D75981#2688505, @lebedev.ri wrote:

Reverse ping, thanks.

[lebedev.ri]

@fhahn Reverse ping, thanks :)

In D75981#2722103, @lebedev.ri wrote:

@fhahn Reverse ping, thanks :)

In D75981#2702505, @lebedev.ri wrote:

@fhahn Reverse ping, thanks :)

In D75981#2688505, @lebedev.ri wrote:

Reverse ping, thanks.

[lebedev.ri]

In D75981#2732814, @lebedev.ri wrote:

@fhahn Reverse ping, thanks :)

In D75981#2722103, @lebedev.ri wrote:

@fhahn Reverse ping, thanks :)

In D75981#2702505, @lebedev.ri wrote:

@fhahn Reverse ping, thanks :)

In D75981#2688505, @lebedev.ri wrote:

Reverse ping, thanks.

[lebedev.ri]

reverse-ping, thanks.

[lebedev.ri]

Futile weekly reverse-ping, thanks (:

[lebedev.ri]

Reverse ping, thanks.

[fhahn]

I finally had some time to rebase this change and fix the fallout.

In D75981#2662881, @ebrevnov wrote:

I don't really understand why we need this separate heuristic for runtime checks. Why don't we simply add cost of runtime checks (possibly with some small scaling to be safe) to total cost of vector loop and just use existing cost model to decide?

That's a good point, but I think that would be better as separate change, because that's a more aggressive change than replacing existing limit. IIUC that's more in line with your D71053.

Please add regression tests from https://reviews.llvm.org/D71053 to this change set as well.

I'm not sure that there's much benefit at the moment, because there will be no changes. The focus of those tests seems to be more about vectorizing small trip count loops with an epilogue and not the cost of memory runtime checks (there are no memory runtime checks for the test I think)

[lebedev.ri]

Bump :)

In D75981#2841271, @fhahn wrote:

I finally had some time to rebase this change and fix the fallout.

Hurray!
It would be good to finally have this resolved.

In D75981#2662881, @ebrevnov wrote:

I don't really understand why we need this separate heuristic for runtime checks. Why don't we simply add cost of runtime checks (possibly with some small scaling to be safe) to total cost of vector loop and just use existing cost model to decide?

That's a good point, but I think that would be better as separate change, because that's a more aggressive change than replacing existing limit. IIUC that's more in line with your D71053.

Please add regression tests from https://reviews.llvm.org/D71053 to this change set as well.

I'm not sure that there's much benefit at the moment, because there will be no changes. The focus of those tests seems to be more about vectorizing small trip count loops with an epilogue and not the cost of memory runtime checks (there are no memory runtime checks for the test I think)

[lebedev.ri]

reverse ping, thanks

[ebrevnov]

Sorry for long silence. Got into hospital with COVID-19 for almost a month.

In D75981#2662881, @ebrevnov wrote:

I don't really understand why we need this separate heuristic for runtime checks. Why don't we simply add cost of runtime checks (possibly with some small scaling to be safe) to total cost of vector loop and just use existing cost model to decide?

That's a good point, but I think that would be better as separate change, because that's a more aggressive change than replacing existing limit. IIUC that's more in line with your D71053.

You are right, I'm essentially asking to follow D71053. First of all, in sake of doing progress I'm not going to block this change if you promise continue working on cost model driven approach.
But I personally think that it would save a lot of time if we go with cost model based approach in the first place because most time consuming thing would be fixing performance regressions and not the implementation itself. I will leave it on you to decide :-).

Please add regression tests from https://reviews.llvm.org/D71053 to this change set as well.

I'm not sure that there's much benefit at the moment, because there will be no changes. The focus of those tests seems to be more about vectorizing small trip count loops with an epilogue and not the cost of memory runtime checks (there are no memory runtime checks for the test I think)

I believe both test cases have vectorization with runtime checks. Look for "; CHECK: vector.memcheck:"

[lebedev.ri]

It is *really* sad to see these two patches to be stuck :(

In D75981#2903756, @ebrevnov wrote:

Sorry for long silence. Got into hospital with COVID-19 for almost a month.

In D75981#2662881, @ebrevnov wrote:

I don't really understand why we need this separate heuristic for runtime checks. Why don't we simply add cost of runtime checks (possibly with some small scaling to be safe) to total cost of vector loop and just use existing cost model to decide?

That's a good point, but I think that would be better as separate change, because that's a more aggressive change than replacing existing limit. IIUC that's more in line with your D71053.

You are right, I'm essentially asking to follow D71053. First of all, in sake of doing progress I'm not going to block this change if you promise continue working on cost model driven approach.
But I personally think that it would save a lot of time if we go with cost model based approach in the first place because most time consuming thing would be fixing performance regressions and not the implementation itself. I will leave it on you to decide :-).

Please add regression tests from https://reviews.llvm.org/D71053 to this change set as well.

I'm not sure that there's much benefit at the moment, because there will be no changes. The focus of those tests seems to be more about vectorizing small trip count loops with an epilogue and not the cost of memory runtime checks (there are no memory runtime checks for the test I think)

I believe both test cases have vectorization with runtime checks. Look for "; CHECK: vector.memcheck:"

I think the goals of these two patches are largely correlated.

I think the main problem is that it isn't quite obvious why hard cut-offs on the runtime check complexity exist.
I guess, to not generate some very large and ridiculous checks.
But clearly, the current cut-offs are just bogusly low.
But i also guess simply bumping them won't really solve the problem,
so i guess we need to redefine them. But what is the right metric,
especially if the trip count is not constant?
Cost of a single scalar loop iteration?

[lebedev.ri]

Reverse ping, thanks.

[ebrevnov]

I think the main problem is that it isn't quite obvious why hard cut-offs on the runtime check complexity exist.
I guess, to not generate some very large and ridiculous checks.

I believe those cut-offs exist for the single reason. There was no way to calculate "real" cost of SCEV generated instructions. Now there is support for that and we can/should simply take cost of runtime checks into account in cost model.

But clearly, the current cut-offs are just bogusly low.
But i also guess simply bumping them won't really solve the problem,
so i guess we need to redefine them. But what is the right metric,
especially if the trip count is not constant?
Cost of a single scalar loop iteration?

May be not the best approach, but taking some reasonable average across applications works good enough. Another metric to consider is benefit from vectorization. Thus loops with expected 3x improvement should be more likely vectorized than 1.1x.

[lebedev.ri]

Honestly in the end i'm not sure i know which approach is best, i just want to see this finally fixed :/

[fhahn]

Rebased again after recent changes.

That's a good point, but I think that would be better as separate change, because that's a more aggressive change than replacing existing limit. IIUC that's more in line with your D71053.

You are right, I'm essentially asking to follow D71053. First of all, in sake of doing progress I'm not going to block this change if you promise continue working on cost model driven approach.
But I personally think that it would save a lot of time if we go with cost model based approach in the first place because most time consuming thing would be fixing performance regressions and not the implementation itself. I will leave it on you to decide :-).

The way I see it the current patch is already using a cost-model based approach: it already computes the cost of the runtime checks and the cost of the scalar loop and compares them.

The formula used in the patch initially is conservative I think, in that it allows larger runtime checks only if them failing only adds a small overhead to the cost of scalar loop in total.

Of course we can choose other formulas, e.g. computing the cost of all vector iterations + RT checks and compare it against the cost of all scalar iterations. This is more optimistic as it assumes the runtime checks succeed.

The main reason I went for the conservative approach initially was because we are already seeing regressions in benchmarks caused by runtime checks for vector loops never taken. I don't want to make this problem worse for now.

Personally I'd prefer to start with a more conservative heuristic to start with, see how it goes & iron out issues in the infrastructure.

How does that sound?

I'm not sure that there's much benefit at the moment, because there will be no changes. The focus of those tests seems to be more about vectorizing small trip count loops with an epilogue and not the cost of memory runtime checks (there are no memory runtime checks for the test I think)

I believe both test cases have vectorization with runtime checks. Look for "; CHECK: vector.memcheck:"

Ah I see, thanks! I think I meant that the patch seems to lift a different but related limitation (tiny trip count vectorization with epilogue) vs this patch which deals with the runtime check threshold.

But clearly, the current cut-offs are just bogusly low.
But i also guess simply bumping them won't really solve the problem,
so i guess we need to redefine them. But what is the right metric,
especially if the trip count is not constant?
Cost of a single scalar loop iteration?

May be not the best approach, but taking some reasonable average across applications works good enough. Another metric to consider is benefit from vectorization. Thus loops with expected 3x improvement should be more likely vectorized than 1.1x.

Agreed, for cases where the trip count is unknown we will have to still make an educated guess. It should still be better/more informed than the single number cut-off for the number of runtime checks. But as I said, I think we should start with the cases where the trip count is known, make sure it works well for that case and move on from there. This also gives us time to iron out any issues with the infrastructure.

[lebedev.ri]

Sure, slow (but steady!) forward progress is better than being stuck with subpar status-quo.
I don't really have anything against the current patch as-is,
with big fat note that there are further follow-up changes needed:

• drop still-present hard cut-off on the number of the checks
• support variable trip count
• ???

[ebrevnov]

In D75981#2947904, @fhahn wrote:

Rebased again after recent changes.

That's a good point, but I think that would be better as separate change, because that's a more aggressive change than replacing existing limit. IIUC that's more in line with your D71053.

You are right, I'm essentially asking to follow D71053. First of all, in sake of doing progress I'm not going to block this change if you promise continue working on cost model driven approach.
But I personally think that it would save a lot of time if we go with cost model based approach in the first place because most time consuming thing would be fixing performance regressions and not the implementation itself. I will leave it on you to decide :-).

The way I see it the current patch is already using a cost-model based approach: it already computes the cost of the runtime checks and the cost of the scalar loop and compares them.

The formula used in the patch initially is conservative I think, in that it allows larger runtime checks only if them failing only adds a small overhead to the cost of scalar loop in total.

Of course we can choose other formulas, e.g. computing the cost of all vector iterations + RT checks and compare it against the cost of all scalar iterations. This is more optimistic as it assumes the runtime checks succeed.

The main reason I went for the conservative approach initially was because we are already seeing regressions in benchmarks caused by runtime checks for vector loops never taken. I don't want to make this problem worse for now.

Personally I'd prefer to start with a more conservative heuristic to start with, see how it goes & iron out issues in the infrastructure.

How does that sound?

I'm fine to go with more conservative heuristic. The change I would like to see is to move runtime checks cost calculation inside cost model. This way CM.selectVectorizationFactor would return VF with cost of runtime checks already taken into account. It would be a bit inconvenient to "merge" with existing limits for runtime checks though. What if we just effectively disable current limits by putting them under an option for now and delete entire eventually?

I'm not sure that there's much benefit at the moment, because there will be no changes. The focus of those tests seems to be more about vectorizing small trip count loops with an epilogue and not the cost of memory runtime checks (there are no memory runtime checks for the test I think)

I believe both test cases have vectorization with runtime checks. Look for "; CHECK: vector.memcheck:"

Ah I see, thanks! I think I meant that the patch seems to lift a different but related limitation (tiny trip count vectorization with epilogue) vs this patch which deals with the runtime check threshold.

I think I understand now. Indeed, for the tests to make sense we would need to allow vectorization of short trip count loops with runtime checks. The question is taken off.

But clearly, the current cut-offs are just bogusly low.
But i also guess simply bumping them won't really solve the problem,
so i guess we need to redefine them. But what is the right metric,
especially if the trip count is not constant?
Cost of a single scalar loop iteration?

May be not the best approach, but taking some reasonable average across applications works good enough. Another metric to consider is benefit from vectorization. Thus loops with expected 3x improvement should be more likely vectorized than 1.1x.

Agreed, for cases where the trip count is unknown we will have to still make an educated guess. It should still be better/more informed than the single number cut-off for the number of runtime checks. But as I said, I think we should start with the cases where the trip count is known, make sure it works well for that case and move on from there. This also gives us time to iron out any issues with the infrastructure.

Agree. This is unrelated to the current patch.

[lebedev.ri]

reverse-ping, thanks

[fhahn]

Unfortunately I do not have the bandwidth to get this unstuck at the moment. So I'm going to strip off the heuristics change and just keep the changes that set up the last bits of the infrastructure.

Also updates getCost to use InstructionCost instead of unsigned.

[ebrevnov]

In D75981#2986956, @fhahn wrote:

Unfortunately I do not have the bandwidth to get this unstuck at the moment. So I'm going to strip off the heuristics change and just keep the changes that set up the last bits of the infrastructure.

Sad to hear that. I can pick it up and try to push forward if you don't mind :-) But I'll wait while D109368 is landed since there is fair amount of dependencies. Sounds good?

[lebedev.ri]

In D75981#2988560, @ebrevnov wrote:

In D75981#2986956, @fhahn wrote:

Unfortunately I do not have the bandwidth to get this unstuck at the moment. So I'm going to strip off the heuristics change and just keep the changes that set up the last bits of the infrastructure.

Sad to hear that. I can pick it up and try to push forward if you don't mind :-) But I'll wait while D109368 is landed since there is fair amount of dependencies. Sounds good?

The thing to keep in mind is, after D109296 (and i assume/hope it succeeds) adjusts the RT check budged allowance for variable loops,
i suspect most of the loops with constant trip count will also start getting vectorized, i suspect.

[ebrevnov]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

193 ↗

(On Diff #371089)

Scalar cost is not VF depending so this doesn't look like the best place for it. Please take a look at https://reviews.llvm.org/D109678 where I propose to cache scalar cost inside code model. How do you like it? Will it work for you as well?

[lebedev.ri]

This needs a rebase.

[fhahn]

rebased

[fhahn]

rebase

[fhahn]

Another rebase, fixing a incorrect conflict resolution earlier. Tests should pass again.

[fhahn]

another rebase :)

[fhahn]

rebase

[fhahn]

Rebase

[fhahn]

Rebase after recent changes.

[fhahn]

Do not expose getInstructionCost, as the latest version of D109368 can simplify use TTI.

[fhahn]

strip unneeded changes, I plan to land this soon, after updating the description to reflect the state in the latest version

llvm/include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

public:
   void addUnsafeAlgebraInst(Instruction *I) {
     // First unsafe algebra instruction.
     if (!UnsafeAlgebraInst)
       UnsafeAlgebraInst = I;
   }
 
   void addRuntimePointerChecks(unsigned Num) { NumRuntimePointerChecks = Num; }
 
-  bool doesNotMeet(Function *F, Loop *L, const LoopVectorizeHints &Hints);
+  bool doesNotMeet(Function *F, Loop *L, const LoopVectorizeHints &Hints,
+                   bool CanIgnoreRTThreshold);
 
 private:
   unsigned NumRuntimePointerChecks = 0;
   Instruction *UnsafeAlgebraInst = nullptr;
 
   /// Interface to emit optimization remarks.
   OptimizationRemarkEmitter &ORE;
 };

llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

if (Name == H->Name) {
         H->Value = Val;
       else
         LLVM_DEBUG(dbgs() << "LV: ignoring invalid hint '" << Name << "'\n");
       break;
     }
   }
 }
 
-bool LoopVectorizationRequirements::doesNotMeet(
-    Function *F, Loop *L, const LoopVectorizeHints &Hints) {
+bool LoopVectorizationRequirements::doesNotMeet(Function *F, Loop *L,
+                                                const LoopVectorizeHints &Hints,
+                                                bool IgnoreRTThreshold) {
   const char *PassName = Hints.vectorizeAnalysisPassName();
   bool Failed = false;
   if (UnsafeAlgebraInst && !Hints.allowReordering()) {
     ORE.emit([&]() {
       return OptimizationRemarkAnalysisFPCommute(
                  PassName, "CantReorderFPOps", UnsafeAlgebraInst->getDebugLoc(),
                  UnsafeAlgebraInst->getParent())
              << "loop not vectorized: cannot prove it is safe to reorder "
                 "floating-point operations";
     });
     Failed = true;
   }
 
   // Test if runtime memcheck thresholds are exceeded.
   bool PragmaThresholdReached =
       NumRuntimePointerChecks > PragmaVectorizeMemoryCheckThreshold;
   bool ThresholdReached =
       NumRuntimePointerChecks > VectorizerParams::RuntimeMemoryCheckThreshold;
-  if ((ThresholdReached && !Hints.allowReordering()) ||
-      PragmaThresholdReached) {
+  bool DoubleThresholdReached =
+      NumRuntimePointerChecks >
+      2 * VectorizerParams::RuntimeMemoryCheckThreshold;
+  if ((!IgnoreRTThreshold && ((ThresholdReached && !Hints.allowReordering()) ||
+                              PragmaThresholdReached)) ||
+      (DoubleThresholdReached && !Hints.allowReordering())) {
     ORE.emit([&]() {
       return OptimizationRemarkAnalysisAliasing(PassName, "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");

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (auto EstimatedTC = getLoopEstimatedTripCount(L))
       return EstimatedTC;
 
   // Check if upper bound estimate is known.
   if (unsigned ExpectedTC = SE.getSmallConstantMaxTripCount(L))
     return ExpectedTC;
 
   return None;
 }
+
 struct GeneratedRTChecks;
+
 namespace llvm {
 /// InnerLoopVectorizer vectorizes loops which contain only one basic
 /// block to a specified vectorization factor (VF).
 /// This class performs the widening of scalars into vectors, or multiple
 /// scalars. This class also implements the following features:
 /// * It inserts an epilogue loop for handling loops that don't have iteration
 ///   counts that are known to be a multiple of the vectorization factor.
 /// * It handles the code generation for reduction variables.
public:
 
   /// Invalidates decisions already taken by the cost model.
   void invalidateCostModelingDecisions() {
     WideningDecisions.clear();
     Uniforms.clear();
     Scalars.clear();
   }
 
-private:
-  unsigned NumPredStores = 0;
-
   /// \return An upper bound for the vectorization factor, a power-of-2 larger
   /// than zero. One is returned if vectorization should best be avoided due
   /// to cost.
   unsigned computeFeasibleMaxVF(unsigned ConstTripCount);
 
   /// The vectorization cost is a combination of the cost itself and a boolean
   /// indicating whether any of the contributing operations will actually
   /// operate on
   /// vector values after type legalization in the backend. If this latter value
   /// is
   /// false, then all operations will be scalarized (i.e. no vectorization has
   /// actually taken place).
   using VectorizationCostTy = std::pair<unsigned, bool>;
 
+  /// Returns the execution time cost of an instruction for a given vector
+  /// width. Vector width of one means scalar.
+  VectorizationCostTy getInstructionCost(Instruction *I, unsigned VF);
+
+  float ScalarCost;
+
+private:
+  unsigned NumPredStores = 0;
+
   /// Returns the expected execution cost. The unit of the cost does
   /// not matter because we use the 'cost' units to compare different
   /// vector widths. The cost that is returned is *not* normalized by
   /// the factor width.
   VectorizationCostTy expectedCost(unsigned VF);
 
-  /// Returns the execution time cost of an instruction for a given vector
-  /// width. Vector width of one means scalar.
-  VectorizationCostTy getInstructionCost(Instruction *I, unsigned VF);
 
   /// The cost-computation logic from getInstructionCost which provides
   /// the vector type as an output parameter.
   unsigned getInstructionCost(Instruction *I, unsigned VF, Type *&VectorTy);
 
   /// Calculate vectorization cost of memory instruction \p I.
   unsigned getMemoryInstructionCost(Instruction *I, unsigned VF);
 
void Create(Loop *L, const LoopAccessInfo &LAI,
     TmpBlock->replaceAllUsesWith(Preheader);
     TmpBlock->getTerminator()->moveBefore(Preheader->getTerminator());
     Preheader->getTerminator()->eraseFromParent();
     DT->changeImmediateDominator(LoopHeader, Preheader);
     DT->eraseNode(TmpBlock);
     LI->removeBlock(TmpBlock);
   }
 
+  unsigned getCost(LoopVectorizationCostModel &CM) {
+    unsigned RTCheckCost = 0;
+    for (Instruction &I : *TmpBlock)
+      RTCheckCost += CM.getInstructionCost(&I, 1).first;
+    return RTCheckCost;
+  }
+
   ~GeneratedRTChecks() {
     if (!TmpBlock) {
       Cleaner.markResultUsed();
       return;
     }
 
     if (!SCEVCheck && TmpBlock->empty()) {
       Cleaner.markResultUsed();
if (TTI.shouldMaximizeVectorBandwidth(!isScalarEpilogueAllowed()) ||
     }
   }
   return MaxVF;
 }
 
 VectorizationFactor
 LoopVectorizationCostModel::selectVectorizationFactor(unsigned MaxVF) {
   float Cost = expectedCost(1).first;
-  const float ScalarCost = Cost;
+  ScalarCost = Cost;
   unsigned Width = 1;
   LLVM_DEBUG(dbgs() << "LV: Scalar loop costs: " << (int)ScalarCost << ".\n");
 
   bool ForceVectorization = Hints->getForce() == LoopVectorizeHints::FK_Enabled;
   if (ForceVectorization && MaxVF > 1) {
     // Ignore scalar width, because the user explicitly wants vectorization.
     // Initialize cost to max so that VF = 2 is, at least, chosen during cost
     // evaluation.
if (MaybeVF) {
     IC = CM.selectInterleaveCount(VF.Width, VF.Cost);
   }
 
   // Optimistically generate runtime checks. Drop them if they turn out to not
   // be profitable.
   GeneratedRTChecks Checks(L->getLoopPreheader(), *PSE.getSE(), DT);
   Checks.Create(L, *LVL.getLAI(), PSE.getUnionPredicate(), LI);
 
+  bool CanIgnoreRTThreshold = false;
+  unsigned RTCost = Checks.getCost(CM);
+  if (ExpectedTC) {
+    // If the expected cost of the runtime checks is a small fraction of the
+    // expected cost of the scalar loop, we can be more aggressive with using
+    // runtime checks.
+    CanIgnoreRTThreshold = RTCost < (*ExpectedTC * CM.ScalarCost * 0.005);
+    LLVM_DEBUG(dbgs() << "LV: Cost of runtime check: " << RTCost << " "
+                      << *ExpectedTC * CM.ScalarCost << "\n");
+  }
+
   // Identify the diagnostic messages that should be produced.
   std::pair<StringRef, std::string> VecDiagMsg, IntDiagMsg;
   bool VectorizeLoop = true, InterleaveLoop = true;
-  if (Requirements.doesNotMeet(F, L, Hints)) {
+  if (Requirements.doesNotMeet(F, L, Hints, CanIgnoreRTThreshold)) {
     LLVM_DEBUG(dbgs() << "LV: Not vectorizing: loop did not meet vectorization "
                          "requirements.\n");
     Hints.emitRemarkWithHints();
     return false;
   }
 
   if (VF.Width == 1) {
     LLVM_DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n");

llvm/test/Transforms/LoopVectorize/AArch64/runtime-check-size-based-threshold.ll

+; RUN: opt -loop-vectorize -mtriple=arm64-apple-iphoneos -S %s | FileCheck %s
+
+%struct.snork = type <{ i32, i32, i16, [6 x i8], %struct.snork.0, i32, [4 x i8] }>
+%struct.snork.0 = type { [4 x %struct.zot] }
+%struct.zot = type { %struct.baz }
+%struct.baz = type { %struct.pluto }
+%struct.pluto = type { %struct.quux }
+%struct.quux = type { %struct.widget }
+%struct.widget = type { %struct.baz.1* }
+%struct.baz.1 = type { i32 (...)**, %struct.zot.2 }
+%struct.zot.2 = type { %struct.pluto.3 }
+%struct.pluto.3 = type { %struct.bar }
+%struct.bar = type { %struct.barney, %struct.blam.4 }
+%struct.barney = type { %struct.blam }
+%struct.blam = type { i8 }
+%struct.blam.4 = type { i16*, i16*, i16* }
+%struct.foo = type { i32, i16*, i32, i32 }
+%struct.blam.5 = type { i32, i16*, i32, i32 }
+
+; The trip count in the loop in this function is too to warrant large runtime checks.
+; CHECK-LABEL: define {{.*}} @test_tc_too_small
+; CHECK-NOT: vector.memcheck
+; CHECK-NOT: vector.body
+define void @test_tc_too_small(%struct.snork* nocapture readonly %arg, %struct.foo* nocapture readonly byval(%struct.foo) align 8 %arg1, %struct.blam.5* nocapture readonly byval(%struct.blam.5) align 8 %arg2, %struct.blam.5* nocapture readonly byval(%struct.blam.5) align 8 %arg3) {
+entry:
+  %tmp11 = getelementptr inbounds %struct.blam.5, %struct.blam.5* %arg3, i64 0, i32 0
+  %tmp12 = load i32, i32* %tmp11, align 8
+  %tmp13 = getelementptr inbounds %struct.blam.5, %struct.blam.5* %arg3, i64 0, i32 1
+  %tmp14 = load i16*, i16** %tmp13, align 8
+  %tmp17 = getelementptr inbounds %struct.blam.5, %struct.blam.5* %arg2, i64 0, i32 1
+  %tmp18 = load i16*, i16** %tmp17, align 8
+  %tmp19 = getelementptr inbounds %struct.foo, %struct.foo* %arg1, i64 0, i32 0
+  %tmp20 = load i32, i32* %tmp19, align 8
+  %tmp21 = getelementptr inbounds %struct.foo, %struct.foo* %arg1, i64 0, i32 1
+  %tmp22 = load i16*, i16** %tmp21, align 8
+  %tmp23 = getelementptr inbounds %struct.snork, %struct.snork* %arg, i64 0, i32 1
+  %tmp24 = load i32, i32* %tmp23, align 4
+  %tmp26 = icmp sgt i32 %tmp24, 0
+  %tmp39 = sext i32 %tmp12 to i64
+  %tmp40 = shl nsw i64 %tmp39, 1
+  %tmp41 = sext i32 %tmp20 to i64
+  %tmp42 = getelementptr inbounds i16, i16* %tmp22, i64 %tmp41
+  br label %bb54
+
+bb54:                                             ; preds = %bb54, %bb37
+  %tmp55 = phi i64 [ 0, %entry ], [ %tmp88, %bb54 ]
+  %tmp56 = getelementptr inbounds i16, i16* %tmp18, i64 %tmp55
+  %tmp57 = load i16, i16* %tmp56, align 2
+  %tmp58 = sext i16 %tmp57 to i32
+  %tmp59 = getelementptr inbounds i16, i16* %tmp14, i64 %tmp55
+  %tmp60 = load i16, i16* %tmp59, align 2
+  %tmp61 = sext i16 %tmp60 to i32
+  %tmp62 = mul nsw i32 %tmp61, 11
+  %tmp63 = getelementptr inbounds i16, i16* %tmp59, i64 %tmp39
+  %tmp64 = load i16, i16* %tmp63, align 2
+  %tmp65 = sext i16 %tmp64 to i32
+  %tmp66 = mul nsw i32 %tmp65, -4
+  %tmp67 = getelementptr inbounds i16, i16* %tmp59, i64 %tmp40
+  %tmp68 = load i16, i16* %tmp67, align 2
+  %tmp69 = sext i16 %tmp68 to i32
+  %tmp70 = add nsw i32 %tmp62, 4
+  %tmp71 = add nsw i32 %tmp70, %tmp66
+  %tmp72 = add nsw i32 %tmp71, %tmp69
+  %tmp73 = lshr i32 %tmp72, 3
+  %tmp74 = add nsw i32 %tmp73, %tmp58
+  %tmp75 = lshr i32 %tmp74, 1
+  %tmp76 = mul nsw i32 %tmp61, 5
+  %tmp77 = shl nsw i32 %tmp65, 2
+  %tmp78 = add nsw i32 %tmp76, 4
+  %tmp79 = add nsw i32 %tmp78, %tmp77
+  %tmp80 = sub nsw i32 %tmp79, %tmp69
+  %tmp81 = lshr i32 %tmp80, 3
+  %tmp82 = sub nsw i32 %tmp81, %tmp58
+  %tmp83 = lshr i32 %tmp82, 1
+  %tmp84 = trunc i32 %tmp75 to i16
+  %tmp85 = getelementptr inbounds i16, i16* %tmp22, i64 %tmp55
+  store i16 %tmp84, i16* %tmp85, align 2
+  %tmp86 = trunc i32 %tmp83 to i16
+  %tmp87 = getelementptr inbounds i16, i16* %tmp42, i64 %tmp55
+  store i16 %tmp86, i16* %tmp87, align 2
+  %tmp88 = add nuw nsw i64 %tmp55, 1
+  %tmp89 = icmp ult i64 %tmp55, 50
+  br i1 %tmp89, label %bb54, label %bb90
+
+bb90:                                             ; preds = %bb54, %bb27, %bb
+  ret void
+}
+
+; The trip count in the loop in this function high enough to warrant large runtime checks.
+; CHECK-LABEL: define {{.*}} @test_tc_big_enough
+; CHECK: vector.memcheck
+; CHECK: vector.body
+define void @test_tc_big_enough(%struct.snork* nocapture readonly %arg, %struct.foo* nocapture readonly byval(%struct.foo) align 8 %arg1, %struct.blam.5* nocapture readonly byval(%struct.blam.5) align 8 %arg2, %struct.blam.5* nocapture readonly byval(%struct.blam.5) align 8 %arg3) {
+entry:
+  %tmp11 = getelementptr inbounds %struct.blam.5, %struct.blam.5* %arg3, i64 0, i32 0
+  %tmp12 = load i32, i32* %tmp11, align 8
+  %tmp13 = getelementptr inbounds %struct.blam.5, %struct.blam.5* %arg3, i64 0, i32 1
+  %tmp14 = load i16*, i16** %tmp13, align 8
+  %tmp17 = getelementptr inbounds %struct.blam.5, %struct.blam.5* %arg2, i64 0, i32 1
+  %tmp18 = load i16*, i16** %tmp17, align 8
+  %tmp19 = getelementptr inbounds %struct.foo, %struct.foo* %arg1, i64 0, i32 0
+  %tmp20 = load i32, i32* %tmp19, align 8
+  %tmp21 = getelementptr inbounds %struct.foo, %struct.foo* %arg1, i64 0, i32 1
+  %tmp22 = load i16*, i16** %tmp21, align 8
+  %tmp23 = getelementptr inbounds %struct.snork, %struct.snork* %arg, i64 0, i32 1
+  %tmp24 = load i32, i32* %tmp23, align 4
+  %tmp26 = icmp sgt i32 %tmp24, 0
+  %tmp39 = sext i32 %tmp12 to i64
+  %tmp40 = shl nsw i64 %tmp39, 1
+  %tmp41 = sext i32 %tmp20 to i64
+  %tmp42 = getelementptr inbounds i16, i16* %tmp22, i64 %tmp41
+  br label %bb54
+
+bb54:                                             ; preds = %bb54, %bb37
+  %tmp55 = phi i64 [ 0, %entry ], [ %tmp88, %bb54 ]
+  %tmp56 = getelementptr inbounds i16, i16* %tmp18, i64 %tmp55
+  %tmp57 = load i16, i16* %tmp56, align 2
+  %tmp58 = sext i16 %tmp57 to i32
+  %tmp59 = getelementptr inbounds i16, i16* %tmp14, i64 %tmp55
+  %tmp60 = load i16, i16* %tmp59, align 2
+  %tmp61 = sext i16 %tmp60 to i32
+  %tmp62 = mul nsw i32 %tmp61, 11
+  %tmp63 = getelementptr inbounds i16, i16* %tmp59, i64 %tmp39
+  %tmp64 = load i16, i16* %tmp63, align 2
+  %tmp65 = sext i16 %tmp64 to i32
+  %tmp66 = mul nsw i32 %tmp65, -4
+  %tmp67 = getelementptr inbounds i16, i16* %tmp59, i64 %tmp40
+  %tmp68 = load i16, i16* %tmp67, align 2
+  %tmp69 = sext i16 %tmp68 to i32
+  %tmp70 = add nsw i32 %tmp62, 4
+  %tmp71 = add nsw i32 %tmp70, %tmp66
+  %tmp72 = add nsw i32 %tmp71, %tmp69
+  %tmp73 = lshr i32 %tmp72, 3
+  %tmp74 = add nsw i32 %tmp73, %tmp58
+  %tmp75 = lshr i32 %tmp74, 1
+  %tmp76 = mul nsw i32 %tmp61, 5
+  %tmp77 = shl nsw i32 %tmp65, 2
+  %tmp78 = add nsw i32 %tmp76, 4
+  %tmp79 = add nsw i32 %tmp78, %tmp77
+  %tmp80 = sub nsw i32 %tmp79, %tmp69
+  %tmp81 = lshr i32 %tmp80, 3
+  %tmp82 = sub nsw i32 %tmp81, %tmp58
+  %tmp83 = lshr i32 %tmp82, 1
+  %tmp84 = trunc i32 %tmp75 to i16
+  %tmp85 = getelementptr inbounds i16, i16* %tmp22, i64 %tmp55
+  store i16 %tmp84, i16* %tmp85, align 2
+  %tmp86 = trunc i32 %tmp83 to i16
+  %tmp87 = getelementptr inbounds i16, i16* %tmp42, i64 %tmp55
+  store i16 %tmp86, i16* %tmp87, align 2
+  %tmp88 = add nuw nsw i64 %tmp55, 1
+  %tmp89 = icmp ult i64 %tmp55, 500
+  br i1 %tmp89, label %bb54, label %bb90
+
+bb90:                                             ; preds = %bb54, %bb27, %bb
+  ret void
+}