[LV] Don't vectorize if we can prove RT + vector cost >= scalar cost (alt. version)

[ebrevnov]

Summary

This change does essentially the same thing as D109368 but in a slightly different way. Instead of doing late evaluation of cost of runtime checks in LoopVectorizationPlanner here we do it directly in the CostModel.

[lebedev.ri]

Suppose D109368 lands first.
Is this particular patch an NFC change, or a functional-one?
What i'm asking is, where does this matter?
Can you add tests where the cost of the checks will be radically different for different VF's?

[ebrevnov]

Rebase after cost model restructure

[ebrevnov]

In D109444#2989903, @lebedev.ri wrote:

Suppose D109368 lands first.
Is this particular patch an NFC change, or a functional-one?
What i'm asking is, where does this matter?
Can you add tests where the cost of the checks will be radically different for different VF's?

I greatly reworked this patch since the original questions so not sure if it still matters....Anyway the intention of this patch was to replace D109368. It achieves the same effect by a slightly different way. Namely cost of runtime checks are embedded into main step of cost calculation. Note that we still can land D109368 first and apply this one later (rebase required)

[lebedev.ri]

In D109444#2997214, @ebrevnov wrote:

In D109444#2989903, @lebedev.ri wrote:

Suppose D109368 lands first.
Is this particular patch an NFC change, or a functional-one?
What i'm asking is, where does this matter?
Can you add tests where the cost of the checks will be radically different for different VF's?

I greatly reworked this patch since the original questions so not sure if it still matters....Anyway the intention of this patch was to replace D109368. It achieves the same effect by a slightly different way. Namely cost of runtime checks are embedded into main step of cost calculation. Note that we still can land D109368 first and apply this one later (rebase required)

I'm not sure this answered my question.

[ebrevnov]

Fixed build error

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 //===- LoopVectorize.cpp - A Loop Vectorizer ------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This is the LLVM loop vectorizer. This pass modifies 'vectorizable' loops

 /// In many cases vectorization is not profitable. This can happen because of
 /// a number of reasons. In this class we mainly attempt to predict the
 /// expected speedup/slowdowns due to the supported instruction set. We use the
 /// TargetTransformInfo to query the different backends for the cost of
 /// different operations.
 class LoopVectorizationCostModel {
 public:
   LoopVectorizationCostModel(ScalarEpilogueLowering SEL, Loop *L,
                              PredicatedScalarEvolution &PSE, LoopInfo *LI,
                              LoopVectorizationLegality *Legal,
                              const TargetTransformInfo &TTI,
                              const TargetLibraryInfo *TLI, DemandedBits *DB,
                              AssumptionCache *AC,
                              OptimizationRemarkEmitter *ORE, const Function *F,
                              const LoopVectorizeHints *Hints,
-                             InterleavedAccessInfo &IAI)
+                             InterleavedAccessInfo &IAI,
+                             GeneratedRTChecks &RTChecks)
       : ScalarEpilogueStatus(SEL), TheLoop(L), PSE(PSE), LI(LI), Legal(Legal),
         TTI(TTI), TLI(TLI), DB(DB), AC(AC), ORE(ORE), TheFunction(F),
-        Hints(Hints), InterleaveInfo(IAI) {}
+        Hints(Hints), InterleaveInfo(IAI), RTChecks(RTChecks) {}
 
   /// \return An upper bound for the vectorization factors (both fixed and
   /// scalable). If the factors are 0, vectorization and interleaving should be
   /// avoided up front.
   FixedScalableVFPair computeMaxVF(ElementCount UserVF, unsigned UserIC);
 
   /// \return True if runtime checks are required for vectorization, and false
   /// otherwise.
public:
 
   /// Invalidates decisions already taken by the cost model.
   void invalidateCostModelingDecisions() {
     WideningDecisions.clear();
     Uniforms.clear();
     Scalars.clear();
   }
 
+  /// 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<InstructionCost, bool>;
+
+  /// Returns the execution time cost of an instruction for a given vector
+  /// width. Vector width of one means scalar.
+  VectorizationCostTy getInstructionCost(Instruction *I, ElementCount VF) const;
+
 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).
ElementCount getMaximizedVFForTarget(unsigned ConstTripCount,
                                        unsigned SmallestType,
                                        unsigned WidestType,
                                        const ElementCount &MaxSafeVF);
 
   /// \return the maximum legal scalable VF, based on the safe max number
   /// of elements.
   ElementCount getMaxLegalScalableVF(unsigned MaxSafeElements);
 
-  /// 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<InstructionCost, bool>;
-
   /// 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. If \p Invalid is not nullptr, this function
   /// will add a pair(Instruction*, ElementCount) to \p Invalid for
   /// each instruction that has an Invalid cost for the given VF.
   using InstructionVFPair = std::pair<Instruction *, ElementCount>;
   VectorizationCostTy
   expectedCost(ElementCount VF,
                SmallVectorImpl<InstructionVFPair> *Invalid = nullptr) const;
 
-  /// Returns the execution time cost of an instruction for a given vector
-  /// width. Vector width of one means scalar.
-  VectorizationCostTy getInstructionCost(Instruction *I, ElementCount VF) const;
-
   /// The cost-computation logic from getInstructionCost which provides
   /// the vector type as an output parameter.
   InstructionCost getInstructionCost(Instruction *I, ElementCount VF,
                                      Type *&VectorTy) const;
 
   /// Return the cost of instructions in an inloop reduction pattern, if I is
   /// part of that pattern.
   Optional<InstructionCost>
public:
 
   /// Loop Vectorize Hint.
   const LoopVectorizeHints *Hints;
 
   /// The interleave access information contains groups of interleaved accesses
   /// with the same stride and close to each other.
   InterleavedAccessInfo &InterleaveInfo;
 
+  /// Structure to hold information about generated runtime checks, responsible
+  /// for cleaning the checks, if vectorization turns out unprofitable.
+  GeneratedRTChecks &RTChecks;
+
   /// Values to ignore in the cost model.
   SmallPtrSet<const Value *, 16> ValuesToIgnore;
 
   /// Values to ignore in the cost model when VF > 1.
   SmallPtrSet<const Value *, 16> VecValuesToIgnore;
 
   /// All element types found in the loop.
   SmallPtrSet<Type *, 16> ElementTypesInLoop;
class GeneratedRTChecks {
   Loop *L;
 
   SCEVExpander SCEVExp;
   SCEVExpander MemCheckExp;
 
   /// Tracks whether SCEV expressions have been expanded internally.
   bool IsSCEVChecksExpanded = false;
 
+  // Cached cost of expanded SCEV expressions.
+  InstructionCost RTCheckCost = InstructionCost::getInvalid();
 public:
   GeneratedRTChecks(PredicatedScalarEvolution &PSE,
                     LoopVectorizationLegality &LVL, DominatorTree *DT,
                     LoopInfo *LI, Loop *L, const DataLayout &DL)
       : PSE(PSE), LVL(LVL), DT(DT), LI(LI), L(L),
         SCEVExp(*PSE.getSE(), DL, "scev.check"),
         MemCheckExp(*PSE.getSE(), DL, "scev.check") {}
 
   /// Remove the created SCEV & memory runtime check blocks & instructions, if
BasicBlock *emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass,
     MemCheckBlock->getTerminator()->setDebugLoc(
         Pred->getTerminator()->getDebugLoc());
 
     // Mark the check as used, to prevent it from being removed during cleanup.
     MemRuntimeCheckCond = nullptr;
     return MemCheckBlock;
   }
 
+  InstructionCost getCost(const LoopVectorizationCostModel &CM) {
+    if (RTCheckCost.isValid())
+      return RTCheckCost;
+
+    expandSCEVChecks();
+    RTCheckCost.setValid();
+
+    if (SCEVCheckBlock)
+      for (Instruction &I : *SCEVCheckBlock) {
+        if (SCEVCheckBlock->getTerminator() == &I)
+          continue;
+        RTCheckCost +=
+            CM.getInstructionCost(&I, ElementCount::getFixed(1)).first;
+      }
+    if (MemCheckBlock)
+      for (Instruction &I : *MemCheckBlock) {
+        if (MemCheckBlock->getTerminator() == &I)
+          continue;
+        RTCheckCost +=
+            CM.getInstructionCost(&I, ElementCount::getFixed(1)).first;
+      }
+    assert(RTCheckCost.isValid() && "Unexpected invalid runtime checks cost");
+    return RTCheckCost;
+  }
+
 private:
   /// Generate runtime checks in SCEVCheckBlock and MemCheckBlock, so we can
   /// accurately estimate the cost of the runtime checks. The blocks are
   /// un-linked from the IR and is added back during vector code generation. If
   /// there is no vector code generation, the check blocks are removed
   /// completely.
   void expandSCEVChecks() {
 
bool LoopVectorizationCostModel::isMoreProfitable(const VectorizationFactor &A,
 
   // Valid cost (A.Cost is valid at this point) is more profitable than any
   // invalid cost.
   if (!B.Cost.isValid()) {
     return true;
   }
 
   if (IsMainLoop) {
-    InstructionCost RTChecksCost = 0;
+    InstructionCost RTChecksCost = RTChecks.getCost(*this);
     InstructionCost FixedCostA = A.Width.isScalar() ? 0 : RTChecksCost;
     InstructionCost FixedCostB = B.Width.isScalar() ? 0 : RTChecksCost;
     FixedCostDiff = {128, (uint64_t)(*(FixedCostB - FixedCostA).getValue()),
                      true};
   }
 
   // When set to preferred, for now assume vscale may be larger than 1, so
   // that scalable vectorization is slightly favorable over fixed-width
static bool processLoopInVPlanNativePath(
   InterleavedAccessInfo IAI(PSE, L, DT, LI, LVL->getLAI());
 
   ScalarEpilogueLowering SEL = getScalarEpilogueLowering(
       F, L, Hints, PSI, BFI, TTI, TLI, AC, LI, PSE.getSE(), DT, *LVL);
 
   GeneratedRTChecks RTChecks(PSE, *LVL, DT, LI, L,
                              F->getParent()->getDataLayout());
   LoopVectorizationCostModel CM(SEL, L, PSE, LI, LVL, *TTI, TLI, DB, AC, ORE, F,
-                                &Hints, IAI);
+                                &Hints, IAI, RTChecks);
   // Use the planner for outer loop vectorization.
   // TODO: CM is not used at this point inside the planner. Turn CM into an
   // optional argument if we don't need it in the future.
   LoopVectorizationPlanner LVP(L, LI, TLI, TTI, LVL, CM, IAI, PSE, Hints,
                                Requirements, ORE);
 
   // Get user vectorization factor.
   ElementCount UserVF = Hints.getWidth();
#endif /* NDEBUG */
   if (UseInterleaved) {
     IAI.analyzeInterleaving(useMaskedInterleavedAccesses(*TTI));
   }
 
   GeneratedRTChecks RTChecks(PSE, LVL, DT, LI, L,
                              F->getParent()->getDataLayout());
   // Use the cost model.
   LoopVectorizationCostModel CM(SEL, L, PSE, LI, &LVL, *TTI, TLI, DB, AC, ORE,
-                                F, &Hints, IAI);
+                                F, &Hints, IAI, RTChecks);
   CM.collectValuesToIgnore();
   CM.collectElementTypesForWidening();
 
   // Use the planner for vectorization.
   LoopVectorizationPlanner LVP(L, LI, TLI, TTI, &LVL, CM, IAI, PSE, Hints,
                                Requirements, ORE);
 
   // Get user vectorization factor and interleave count.

llvm/test/Transforms/LoopVectorize/X86/pointer-runtime-checks-unprofitable.ll

+; REQUIRES: asserts
+
+; RUN: opt -runtime-memory-check-threshold=9 -passes='loop-vectorize' -mtriple=x86_64-unknown-linux -S -debug %s 2>&1 | FileCheck %s
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+
+target triple = "x86_64-unknown-linux"
+
+declare double @llvm.pow.f64(double, double)
+
+; Test case where the memory runtime checks and vector body is more expensive
+; than running the scalar loop.
+define void @test(double* nocapture %A, double* nocapture %B, double* nocapture %C, double* nocapture %D, double* nocapture %E) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT: entry:
+; CHECK-NEXT:  br label %for.body
+; CHECK-NOT: vector.memcheck
+; CHECK-NOT: vector.body
+;
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
+  %gep.A = getelementptr inbounds double, double* %A, i64 %iv
+  %l.A = load double, double* %gep.A, align 4
+  store double 0.0, double* %gep.A, align 4
+  %p.1 = call double @llvm.pow.f64(double %l.A, double 2.0)
+
+  %gep.B = getelementptr inbounds double, double* %B, i64 %iv
+  %l.B = load double, double* %gep.B, align 4
+  %p.2 = call double @llvm.pow.f64(double %l.B, double %p.1)
+  store double 0.0, double* %gep.B, align 4
+
+  %gep.C = getelementptr inbounds double, double* %C, i64 %iv
+  %l.C = load double, double* %gep.C, align 4, !noalias !5
+  %p.3 = call double @llvm.pow.f64(double %p.1, double %l.C)
+
+  %gep.D = getelementptr inbounds double, double* %D, i64 %iv
+  %l.D = load double, double* %gep.D
+  %p.4 = call double @llvm.pow.f64(double %p.3, double %l.D)
+  %p.5 = call double @llvm.pow.f64(double %p.4, double %p.3)
+  %mul = fmul double 2.0, %p.5
+  %mul.2 = fmul double %mul, 2.0
+  %mul.3 = fmul double %mul, %mul.2
+  %gep.E = getelementptr inbounds double, double* %E, i64 %iv
+  store double %mul.3, double* %gep.E, align 4, !alias.scope !5
+  %iv.next = add i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, 16
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+!0 = !{!0}
+!1 = !{!1}
+
+; Some scopes in these domains:
+!2 = !{!2, !0}
+!4 = !{!4, !1}
+
+!5 = !{!4} ; A list containing only scope !4
+