[LV] Move interleave count computation to LVP::plan().

[fhahn]

Summary

This patch moves the interleave count computation into LVP::plan(). It
makes sure VPlans are built in all cases we could generate code in the
vectorizer. If we know we do not generate any code (MaxVF == 1, no
interleaving), we can avoid building any VPlans.

Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=6477

[dcaballe]

Hey Florian! Thanks a lot for taking care of this! I'm leaving a comment below. Please, let me know what you think.

Diego

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6168

I wondered if we could make LoopVectorizationPlanner::plan more interleave group aware, since the code above also builds a vplan for VF=1 and and returns NoVectorization. Maybe we don't have to modify computeMaxVF but just pass InterleaveGroup flag to LoopVectorizationPlanner::plan and make sure a vplan is built when the flag is true. We are already passing UserVF so it would be more of the same. In that way we wouldn't need a independent handling for interleaving cases. I wouldn't worried about compile time since the code executed for InterleaveGroup would be mostly the code that you have in the new planForInterleaving, right?. What do you think?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6168

The interleave count is currently determined by CM.selectInterleaveCount (or the user provided one, as in the test case) and depends on the vectorization factor. It might make sense to determine the interleave count in plan as well, and return a pair of VF and interleave count. What do you think?

(Please note that the interleave count I am talking about is not related to (Memory) InterleaveGroups)

[dcaballe]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6168

Sorry, I didn't mean interleave "group" but interleave "loop" in my previous message (including the flag, line 7212) :).
Yes, IMO what you suggest is the the right think to do. VPlan is meant to be used for vectorization and interleaving. We mostly focused on the first one but we should catch up on the second.

[fhahn]

Update the patch to move interleave count computation into LVP::plan(). The early exit if computeMaxVF == None made it a bit tricky.

As it is at the moment, we need to know the selected vectorization factor to compute the interleave count. And we need to know the interleave count to know if we need to generate VPlans. Maybe with this refactor it would also make sense to only generate a VPlan for the selected vectorization factor for now? There is no need to build VPlans for multiple vectorization factors in the legacy planning and we have the VPlan native path which builds the VPlans up front for planning.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

845

Left over, I'll remove it before committing.

[hsaito]

In D57382#1386147, @fhahn wrote:

As it is at the moment, we need to know the selected vectorization factor to compute the interleave count. And we need to know the interleave count to know if we need to generate VPlans. Maybe with this refactor it would also make sense to only generate a VPlan for the selected vectorization factor for now? There is no need to build VPlans for multiple vectorization factors in the legacy planning and we have the VPlan native path which builds the VPlans up front for planning.

I don't disagree with you in principle, but let's wait until planInVPlanNativePath() actually starts to build VPlans for multiple VFs. I hate to see the rest of the things getting bit rotten before that happens.
This is partly because I haven't worked on the legacy side of CM running on VPlan as much as I should --- so, I can't complain. Once that version of CM is ready, once again, I'll have to build multiple VPlans.
Please be forewarned.

[hsaito]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6147

Need to take UserIC into account here as well?

[dcaballe]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6134

Merge with next line?

6154

Shouldn't VF now starts from 1 and 6160 be removed?

6170–6176

multiple? do you mean at least one?

[fhahn]

Address comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6147

Unfortunately the logic to decide between UserIC and computed IC is currently tightly tied with debug messages/optimization remarks. I think it would make sense to move that to plan() as well, but I would prefer to do it in a follow up patch, if that is OK with.

[Ayal]

The bug revealed by the test is rather subtle; does it match the original https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=6477 ?

LV decided (rightfully) not the vectorize the loop in the test having trip-count == 1, but does decide to interleave it (wrongfully, see below). LVP::plan() returns {VF=1,Cost=0} representing the decision not to vectorize, but w/o building any VPlan, which breaks the interleaving decision taken afterwards.

LVP::plan() builds a VPlan for VF=1 only to serve interleaving. So one simple possible fix for this bug is to always build such a VPlan. This patch tries to be smarter, and have LVP::plan() build this single VPlan only if interleaving will actually need it. Another way to building this VPlan only if needed, is to build it on demand, if it's missing, once IC is determined (and before/at setBestPlan() which raised the assert). But note that LVP::plan() refrains from building a VPlan for VF=1 only if MaybeMaxVF is None, meaning "vectorization should be avoided up front". In such cases, interleaving should also be avoided up front! This "up frontness" can be propagated from CM.computeMaxVF() to CM.selectInterleaveCount() in one of several ways: raising a "CM.up-front" flag; have LVP::plan() return (1) an Optional<VectorizationFactor>; (2) a std::tie(VF, NoIC), similar to the current patch, but where NoIC is a boolean indicating IC should be set to 1; (3) a {VF=0,Cost=0} to denote that vectorization and interleaving are to be avoided up-front --- note that {VF=1,Cost=0} *also* represents UserVF=1, which *is* subject to interleaving.

It would be good to build VPlans more selectively to save compile-time, and possibly refactor how VF and IC decisions are taken, but better in a separate patch from one that fixes an erroneously missing VPlan?

[fhahn]

In D57382#1387143, @Ayal wrote:

The bug revealed by the test is rather subtle; does it match the original https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=6477 ?

LV decided (rightfully) not the vectorize the loop in the test having trip-count == 1, but does decide to interleave it (wrongfully, see below). LVP::plan() returns {VF=1,Cost=0} representing the decision not to vectorize, but w/o building any VPlan, which breaks the interleaving decision taken afterwards.

LVP::plan() builds a VPlan for VF=1 only to serve interleaving. So one simple possible fix for this bug is to always build such a VPlan. This patch tries to be smarter, and have LVP::plan() build this single VPlan only if interleaving will actually need it. Another way to building this VPlan only if needed, is to build it on demand, if it's missing, once IC is determined (and before/at setBestPlan() which raised the assert). But note that LVP::plan() refrains from building a VPlan for VF=1 only if MaybeMaxVF is None, meaning "vectorization should be avoided up front". In such cases, interleaving should also be avoided up front! This "up frontness" can be propagated from CM.computeMaxVF() to CM.selectInterleaveCount() in one of several ways: raising a "CM.up-front" flag; have LVP::plan() return (1) an Optional<VectorizationFactor>; (2) a std::tie(VF, NoIC), similar to the current patch, but where NoIC is a boolean indicating IC should be set to 1; (3) a {VF=0,Cost=0} to denote that vectorization and interleaving are to be avoided up-front --- note that {VF=1,Cost=0} *also* represents UserVF=1, which *is* subject to interleaving.

It would be good to build VPlans more selectively to save compile-time, and possibly refactor how VF and IC decisions are taken, but better in a separate patch from one that fixes an erroneously missing VPlan?

Thanks Ayal! Do I understand correctly that you propose to first fix the missing VPlan issue by make interleaving respect the fact that interleaving should be avoided when computeMaxVF returns None? If that is the intended behavior, then I think it makes sense to fix that first and I'll prepare a separate patch.

[Ayal]

In D57382#1387166, @fhahn wrote:

In D57382#1387143, @Ayal wrote:

The bug revealed by the test is rather subtle; does it match the original https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=6477 ?

LV decided (rightfully) not the vectorize the loop in the test having trip-count == 1, but does decide to interleave it (wrongfully, see below). LVP::plan() returns {VF=1,Cost=0} representing the decision not to vectorize, but w/o building any VPlan, which breaks the interleaving decision taken afterwards.

LVP::plan() builds a VPlan for VF=1 only to serve interleaving. So one simple possible fix for this bug is to always build such a VPlan. This patch tries to be smarter, and have LVP::plan() build this single VPlan only if interleaving will actually need it. Another way to building this VPlan only if needed, is to build it on demand, if it's missing, once IC is determined (and before/at setBestPlan() which raised the assert). But note that LVP::plan() refrains from building a VPlan for VF=1 only if MaybeMaxVF is None, meaning "vectorization should be avoided up front". In such cases, interleaving should also be avoided up front! This "up frontness" can be propagated from CM.computeMaxVF() to CM.selectInterleaveCount() in one of several ways: raising a "CM.up-front" flag; have LVP::plan() return (1) an Optional<VectorizationFactor>; (2) a std::tie(VF, NoIC), similar to the current patch, but where NoIC is a boolean indicating IC should be set to 1; (3) a {VF=0,Cost=0} to denote that vectorization and interleaving are to be avoided up-front --- note that {VF=1,Cost=0} *also* represents UserVF=1, which *is* subject to interleaving.

It would be good to build VPlans more selectively to save compile-time, and possibly refactor how VF and IC decisions are taken, but better in a separate patch from one that fixes an erroneously missing VPlan?

Thanks Ayal! Do I understand correctly that you propose to first fix the missing VPlan issue by make interleaving respect the fact that interleaving should be avoided when computeMaxVF returns None? If that is the intended behavior, then I think it makes sense to fix that first and I'll prepare a separate patch.

Yes, that's right. Just curious if that'll indeed fix the original bug.

[fhahn]

In D57382#1387174, @Ayal wrote:

In D57382#1387166, @fhahn wrote:

Thanks Ayal! Do I understand correctly that you propose to first fix the missing VPlan issue by make interleaving respect the fact that interleaving should be avoided when computeMaxVF returns None? If that is the intended behavior, then I think it makes sense to fix that first and I'll prepare a separate patch.

Yes, that's right. Just curious if that'll indeed fix the original bug.

Yep it fixes the original bug. I've created D57837. Once that is resolved, I'll update this patch.

[fhahn]

I'll come back to this and will try to update it with the improvements discussed here and at D57837. Thanks everyone for all the feedback!

[fhahn]

This is not needed any longer.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

 
 public:
   LoopVectorizationPlanner(Loop *L, LoopInfo *LI, const TargetLibraryInfo *TLI,
                            const TargetTransformInfo *TTI,
                            LoopVectorizationLegality *Legal,
                            LoopVectorizationCostModel &CM)
       : OrigLoop(L), LI(LI), TLI(TLI), TTI(TTI), Legal(Legal), CM(CM) {}
 
-  /// Plan how to best vectorize, return the best VF and its cost.
-  VectorizationFactor plan(bool OptForSize, unsigned UserVF);
+  /// Plan how to best vectorize, return the best VF and its cost, together with
+  /// the interleave count.
+  std::pair<VectorizationFactor, unsigned>
+  plan(bool OptForSize, unsigned UserVF, unsigned UserIC);
 
   /// Use the VPlan-native path to plan how to best vectorize, return the best
   /// VF and its cost.
   VectorizationFactor planInVPlanNativePath(bool OptForSize, unsigned UserVF);
 
   /// Finalize the best decision and dispose of all other VPlans.
   void setBestPlan(unsigned VF, unsigned UF);
 

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

LoopVectorizationCostModel(Loop *L, PredicatedScalarEvolution &PSE,
                              const TargetLibraryInfo *TLI, DemandedBits *DB,
                              AssumptionCache *AC,
                              OptimizationRemarkEmitter *ORE, const Function *F,
                              const LoopVectorizeHints *Hints,
                              InterleavedAccessInfo &IAI)
       : TheLoop(L), PSE(PSE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI), DB(DB),
     AC(AC), ORE(ORE), TheFunction(F), Hints(Hints), InterleaveInfo(IAI) {}
 
-  /// \return An upper bound for the vectorization factor, or None if
+  /// \return An upper bound for the vectorization factor, or 1 if
   /// vectorization should be avoided up front.
   Optional<unsigned> computeMaxVF(bool OptForSize);
 
   /// \return The most profitable vectorization factor and the cost of that VF.
   /// This method checks every power of two up to MaxVF. If UserVF is not ZERO
   /// then this vectorization factor will be selected if vectorization is
   /// possible.
   VectorizationFactor selectVectorizationFactor(unsigned MaxVF);
LoopVectorizationPlanner::planInVPlanNativePath(bool OptForSize,
   }
 
   LLVM_DEBUG(
       dbgs() << "LV: Not vectorizing. Inner loops aren't supported in the "
                 "VPlan-native path.\n");
   return NoVectorization;
 }
 
-VectorizationFactor
-LoopVectorizationPlanner::plan(bool OptForSize, unsigned UserVF) {
+std::pair<VectorizationFactor, unsigned>
+LoopVectorizationPlanner::plan(bool OptForSize, unsigned UserVF,
+                               unsigned UserIC) {
   assert(OrigLoop->empty() && "Inner loop expected.");
-  // Width 1 means no vectorization, cost 0 means uncomputed cost.
-  const VectorizationFactor NoVectorization = {1U, 0U};
+
+  // Assume no vectorization until proven otherwise. Width 1 means no
+  // vectorization, cost 0 means uncomputed cost.
+  VectorizationFactor VF = {1U, 0U};
+
+  // Start with pessimistic MaxVF and extend it if MaybeMaxVF is valid.
+  unsigned MaxVF = 1;
+
   Optional<unsigned> MaybeMaxVF = CM.computeMaxVF(OptForSize);
-  if (!MaybeMaxVF.hasValue()) // Cases considered too costly to vectorize.
-    return NoVectorization;
 
+  if (MaybeMaxVF) {
     // Invalidate interleave groups if all blocks of loop will be predicated.
     if (CM.blockNeedsPredication(OrigLoop->getHeader()) &&
         !useMaskedInterleavedAccesses(*TTI)) {
-    LLVM_DEBUG(
-        dbgs()
-        << "LV: Invalidate all interleaved groups due to fold-tail by masking "
-           "which requires masked-interleaved support.\n");
+      LLVM_DEBUG(dbgs() << "LV: Invalidate all interleaved groups due to "
+                           "fold-tail by masking which requires "
+                           "masked-interleaved support.\n");
       CM.InterleaveInfo.reset();
     }
 
     if (UserVF) {
       LLVM_DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n");
       assert(isPowerOf2_32(UserVF) && "VF needs to be a power of two");
       // Collect the instructions (and their associated costs) that will be more
       // profitable to scalarize.
       CM.selectUserVectorizationFactor(UserVF);
       buildVPlansWithVPRecipes(UserVF, UserVF);
       LLVM_DEBUG(printPlans(dbgs()));
-    return {UserVF, 0};
+      return {{UserVF, 0}, CM.selectInterleaveCount(OptForSize, UserVF, 0)};
     }
 
-  unsigned MaxVF = MaybeMaxVF.getValue();
+    MaxVF = *MaybeMaxVF;
     assert(MaxVF != 0 && "MaxVF is zero.");
 
-  for (unsigned VF = 1; VF <= MaxVF; VF *= 2) {
+    if (MaxVF > 1) {
+      CM.collectUniformsAndScalars(1);
+      for (unsigned VF = 2; VF <= MaxVF; VF *= 2) {
         // Collect Uniform and Scalar instructions after vectorization with VF.
         CM.collectUniformsAndScalars(VF);
 
-    // Collect the instructions (and their associated costs) that will be more
-    // profitable to scalarize.
-    if (VF > 1)
+        // Collect the instructions (and their associated costs) that will be
+        // more profitable to scalarize.
         CM.collectInstsToScalarize(VF);
       }
+      // Select the optimal vectorization factor.
+      VF = CM.selectVectorizationFactor(MaxVF);
+    }
+  }
+
+  unsigned IC = CM.selectInterleaveCount(OptForSize, VF.Width, VF.Cost);
 
+  // Build VPlans if we either have at least possible vectorization factor
+  // (MaxVF > 1)  or decided to interleave.
+  if (MaxVF > 1 || UserIC > 1 || IC > 1) {
     buildVPlansWithVPRecipes(1, MaxVF);
     LLVM_DEBUG(printPlans(dbgs()));
-  if (MaxVF == 1)
-    return NoVectorization;
-
-  // Select the optimal vectorization factor.
-  return CM.selectVectorizationFactor(MaxVF);
+  }
+  return {VF, IC};
 }
 
 void LoopVectorizationPlanner::setBestPlan(unsigned VF, unsigned UF) {
   LLVM_DEBUG(dbgs() << "Setting best plan to VF=" << VF << ", UF=" << UF
                     << '\n');
   BestVF = VF;
   BestUF = UF;
 
#endif /* NDEBUG */
   CM.collectValuesToIgnore();
 
   // Use the planner for vectorization.
   LoopVectorizationPlanner LVP(L, LI, TLI, TTI, &LVL, CM);
 
   // Get user vectorization factor.
   unsigned UserVF = Hints.getWidth();
 
-  // Plan how to best vectorize, return the best VF and its cost.
-  VectorizationFactor VF = LVP.plan(OptForSize, UserVF);
-
-  // Select the interleave count.
-  unsigned IC = CM.selectInterleaveCount(OptForSize, VF.Width, VF.Cost);
-
   // Get user interleave count.
   unsigned UserIC = Hints.getInterleave();
 
+  // Plan how to best vectorize, return the best VF and its cost.
+  VectorizationFactor VF;
+  unsigned IC;
+  std::tie(VF, IC) = LVP.plan(OptForSize, UserVF, UserIC);
+
   // 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)) {
     LLVM_DEBUG(dbgs() << "LV: Not vectorizing: loop did not meet vectorization "
                          "requirements.\n");
     Hints.emitRemarkWithHints();
     return false;

llvm/test/Transforms/LoopVectorize/interleave-need-vplan.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -loop-vectorize -S | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @inc(i32 %n) #0 {
+; CHECK-LABEL: @inc(
+; CHECK-NEXT:    br i1 false, label [[DOTLR_PH_PREHEADER:%.*]], label [[DOT_CRIT_EDGE:%.*]]
+; CHECK:       .lr.ph.preheader:
+; CHECK-NEXT:    br i1 true, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[INDUCTION:%.*]] = add i64 [[INDEX]], 0
+; CHECK-NEXT:    [[INDUCTION1:%.*]] = add i64 [[INDEX]], 1
+; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[INDEX_NEXT]], 0
+; CHECK-NEXT:    br i1 [[TMP1]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !0
+; CHECK:       middle.block:
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i64 1, 0
+; CHECK-NEXT:    br i1 [[CMP_N]], label [[DOT_CRIT_EDGE_LOOPEXIT:%.*]], label [[SCALAR_PH]]
+; CHECK:       scalar.ph:
+; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i64 [ 0, [[MIDDLE_BLOCK]] ], [ 0, [[DOTLR_PH_PREHEADER]] ]
+; CHECK-NEXT:    br label [[DOTLR_PH:%.*]]
+; CHECK:       .lr.ph:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[DOTLR_PH]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    br i1 true, label [[DOT_CRIT_EDGE_LOOPEXIT]], label [[DOTLR_PH]], !llvm.loop !3
+; CHECK:       ._crit_edge.loopexit:
+; CHECK-NEXT:    br label [[DOT_CRIT_EDGE]]
+; CHECK:       ._crit_edge:
+; CHECK-NEXT:    ret void
+;
+  br i1 false, label %.lr.ph, label %._crit_edge
+
+.lr.ph:                                           ; preds = %.lr.ph, %0
+  %indvars.iv = phi i64 [ %indvars.iv.next, %.lr.ph ], [ 0, %0 ]
+  %indvars.iv.next = add i64 %indvars.iv, 1
+  br i1 true, label %._crit_edge, label %.lr.ph, !llvm.loop !0
+
+._crit_edge:                                      ; preds = %.lr.ph, %0
+  ret void
+}
+
+!0 = distinct !{!0, !1}
+!1 = !{!"llvm.loop.interleave.count", i32 2}