[LV] Prevent interleaving if computeMaxVF returned None.

[fhahn]

Summary

As discussed in D57382, interleaving should be avoided if computeMaxVF
returns None, same as we currently do for vectorization.

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

[hsaito]

I have a little mental barrier in accepting this change as is. I think this feeling of mine is mainly due to the name and the "stated" functionality of computeMaxVF and "indirect inference" towards using it for suppressing interleaving. Maybe I'm just being too picky here. If so, my apologies ahead of time.

Other than just the function name and the associated comment:

1. runtime ptr check && hasBranchDivergence interleave w/ VF=1 still okay?
2. For interleaving, the remaining checks other than TC==0/1 (for better diagnostics) and OptForSize appear useless. Even if TC is evenly divisible by VF or canFoldTailByMasking, we still can't interleave under OptForSize.

I think we should start thinking in terms of separate "is vectorization feasible" and "is interleaving feasible" (plus possibly "is unrolling feasible"), even if we evaluate those feasibility in one function.

Possibly going to tangent, but while we look at computeMaxVF, at the bottom, we say use pragma, but we bail out of plan() w/o checking whether UserVF exists or not.

Hopefully, this conveys enough about my feeling of uneasiness.

[rengolin]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6101

Nit: To avoid redundancy in the name, I'd just call it something like "Disabled"...

7322

This pattern feels like it could be an utility function of VectorizationFactor...

7322

None of the parameters depend on IC and this call will override the value, why initialise with 1 above?

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

6115–6116

Worth updating the comment, e.g., Cases that should not to be vectorized nor interleaved. And while touching the line, worth shortening to if (!MaybeMaxVF).

7324

UserIC should always be set to Hints.getInterleave().

llvm/test/Transforms/LoopVectorize/no-interleave-up-front.ll

7

Document where this test came from?

[fhahn]

Thanks for all the comments!

In D57837#1387764, @hsaito wrote:

Other than just the function name and the associated comment:

1. runtime ptr check && hasBranchDivergence interleave w/ VF=1 still okay?

Yep I think so.

2. For interleaving, the remaining checks other than TC==0/1 (for better diagnostics) and OptForSize appear useless. Even if TC is evenly divisible by VF or canFoldTailByMasking, we still can't interleave under OptForSize.

I think we should start thinking in terms of separate "is vectorization feasible" and "is interleaving feasible" (plus possibly "is unrolling feasible"), even if we evaluate those feasibility in one function.

Agreed, having it done implicitly in a function called computeMaxVF does not seem ideal. From the current behavior of computeMaxVF, I think what we actually want to decide whether to disable interleaving up front is just if we optimize for size or not. What do you think?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7322

In case MaybeVF is None, we want to avoid interleaving, that is why it is initialized with 1 and only computed when we have a VF.

7324

Ah I thought you meant that we should ignore UserIC, in case computeMaxVF returned None, similar to the way we ignore UserVF in that case. Did I miss something?

[dcaballe]

This comment was removed by dcaballe.

[hsaito]

In D57837#1387830, @fhahn wrote:

Agreed, having it done implicitly in a function called computeMaxVF does not seem ideal. From the current behavior of computeMaxVF, I think what we actually want to decide whether to disable interleaving up front is just if we optimize for size or not. What do you think?

That was my conclusion as well.

With that understanding, your current direction is

If VPlan is not built for vectorization purposes, also bail out on interleaving. ---- Work on enabling interleaving in a subsequent patch.

and I'm fine with that approach.

[Ayal]

In D57837#1387764, @hsaito wrote:

I have a little mental barrier in accepting this change as is. I think this feeling of mine is mainly due to the name and the "stated" functionality of computeMaxVF and "indirect inference" towards using it for suppressing interleaving. Maybe I'm just being too picky here. If so, my apologies ahead of time.

Other than just the function name and the associated comment:

1. runtime ptr check && hasBranchDivergence interleave w/ VF=1 still okay?
2. For interleaving, the remaining checks other than TC==0/1 (for better diagnostics) and OptForSize appear useless. Even if TC is evenly divisible by VF or canFoldTailByMasking, we still can't interleave under OptForSize.

I think we should start thinking in terms of separate "is vectorization feasible" and "is interleaving feasible" (plus possibly "is unrolling feasible"), even if we evaluate those feasibility in one function.

Possibly going to tangent, but while we look at computeMaxVF, at the bottom, we say use pragma, but we bail out of plan() w/o checking whether UserVF exists or not.

Hopefully, this conveys enough about my feeling of uneasiness.

This patch tries only to avoid running into the "no-VPlan-was-built-for-interleaving" problem, w/o modifying any other behavior or performing any refactoring. The latter indeed deserve to be addressed, but in separate patches.

For 1), a same runtime ptr check is needed for both vectorization and interleaving, so seems it should prevent both if one wishes to avoid introducing such branches before a loop when hasBranchDivergence. But I can't find a review explaining r309890.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7324

UserIC should remain intact. Only IC must decide not to interleave if no (suitable) VPlan was built.

[Ayal]

This LGTM with the minor documentation comments and retention of UserIC.
Seems like we've reached a consensus, correct me if not.
Thanks!

[hsaito]

In D57837#1387990, @Ayal wrote:

This LGTM with the minor documentation comments and retention of UserIC.
Seems like we've reached a consensus, correct me if not.
Thanks!

I'm fine addressing my concerns in updated comments and later commits.

[dcaballe]

LGTM (as you could see in my previous message :))

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7324

The problem is we pick either UserIC or the computed IC a bit later on, so if we initialize UserIC unconditionally, we still hit exactly the problem in the test case. We could move the code to choose IC or UserIC into the conditional (together with the diagnostic messages)

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7324

Ah, right, my bad. How about setting InterleaveLoop below to false, with suitable debug/report message. That is actually the only change really needed: always calling CM.selectInterleaveCount() would in most cases return 1 immediately anyhow due to OptForSize (including the test case), and perform redundant computation only for the runtime ptr check && hasBranchDivergence case. But it is logical to avoid calling CM.selectInterleaveCount() below; or leave it to a separate refactoring of how VF&IC are set, possibly noting the potential waste in a TODO.

[fhahn]

Move selection of IC into conditional.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7324

Right, I moved the code to pick IC or UserIC and the diagnostics into the conditional. I also moved the VF == 1 diagnostic and the requirements check, as we might get different diagnostic ordering otherwise. What do you think?

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7324

Above thought was simply to add another

if (!MaybeVF && UserIC > 1) {
  // Tell the user interleaving was avoided up-front, despite being explicitly requested. 
  LLVM_DEBUG(dbgs() << "LV: ...\n");
  IntDiagMsg = std::make_pair(...);
  InterleaveLoop = false;
} else if // other cases for setting InterleaveLoop to false;

following the previous structure of setting

UserIC = Hints.getInterleave();
if (MaybeVF) {
  VF = *MaybeVF;
  IC = CM.selectInterleaveCount(OptForSize, VF.Width, VF.Cost);
}

Sounds right?

[fhahn]

Simplified as per Ayal's comment, thanks.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7324

Right, let's go with the less invasive change first. I've updated the code. Note that it sets UserIC = 1 if it was ignored, so we do not display any other UserIC related messages later on.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7324

Original suggestion was to continue setting VF and IC above, and add a 3rd cascaded-if case that sets InterleaveCount to false below, w/o resetting UserIC, thereby retaining the current structure amap. But if you prefer fusing them together to check MaybeVF only once that's also ok.

7329

Separate with an empty line.

[fhahn]

Thanks Ayal! I'll add the line before committing. Are you ok for the latest iteration to go in?

[Ayal]

In D57837#1389439, @fhahn wrote:

Thanks Ayal! I'll add the line before committing. Are you ok for the latest iteration to go in?

Yes, I'm ok. Would have preferred the separate if (MaybeVF) { VF=..; IC=..; } and if (!MaybeVF && UserIC >0) { InterleaveCount = false; ... } else if ... version, but leave it for you to decide.

[fhahn]

In D57837#1389513, @Ayal wrote:

In D57837#1389439, @fhahn wrote:

Thanks Ayal! I'll add the line before committing. Are you ok for the latest iteration to go in?

Yes, I'm ok. Would have preferred the separate if (MaybeVF) { VF=..; IC=..; } and if (!MaybeVF && UserIC >0) { InterleaveCount = false; ... } else if ... version, but leave it for you to decide.

I'll update it before committing.

[Ayal]

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

7360 ↗

(On Diff #185847)

This UserIC = 1 is now redundant, right?

Thanks!

[fhahn]

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

7360 ↗

(On Diff #185847)

Of course, just moved the code around.... Removed in rGf557a94aa32c.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

 /// We need to streamline them.
 
 /// Information about vectorization costs
 struct VectorizationFactor {
   // Vector width with best cost
   unsigned Width;
   // Cost of the loop with that width
   unsigned Cost;
+
+  // Width 1 means no vectorization, cost 0 means uncomputed cost.
+  static VectorizationFactor Disabled() { return {1, 0}; }
 };
 
 /// Planner drives the vectorization process after having passed
 /// Legality checks.
 class LoopVectorizationPlanner {
   /// The loop that we evaluate.
   Loop *OrigLoop;
 

 
 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, or None if
+  /// vectorization and interleaving should be avoided up front.
+  Optional<VectorizationFactor> plan(bool OptForSize, unsigned UserVF);
 
   /// 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,
                              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
-  /// vectorization should be avoided up front.
+  /// vectorization and interleaving 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);
 
for (auto &Induction : *Legal->getInductionVars()) {
     const SmallVectorImpl<Instruction *> &Casts = IndDes.getCastInsts();
     VecValuesToIgnore.insert(Casts.begin(), Casts.end());
   }
 }
 
 VectorizationFactor
 LoopVectorizationPlanner::planInVPlanNativePath(bool OptForSize,
                                                 unsigned UserVF) {
-  // Width 1 means no vectorization, cost 0 means uncomputed cost.
-  const VectorizationFactor NoVectorization = {1U, 0U};
-
   // Outer loop handling: They may require CFG and instruction level
   // transformations before even evaluating whether vectorization is profitable.
   // Since we cannot modify the incoming IR, we need to build VPlan upfront in
   // the vectorization pipeline.
   if (!OrigLoop->empty()) {
     // TODO: If UserVF is not provided, we set UserVF to 4 for stress testing.
     // This won't be necessary when UserVF is not required in the VPlan-native
     // path.
     if (VPlanBuildStressTest && !UserVF)
       UserVF = 4;
 
     assert(EnableVPlanNativePath && "VPlan-native path is not enabled.");
     assert(UserVF && "Expected UserVF for outer loop vectorization.");
     assert(isPowerOf2_32(UserVF) && "VF needs to be a power of two");
     LLVM_DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n");
     buildVPlans(UserVF, UserVF);
 
     // For VPlan build stress testing, we bail out after VPlan construction.
     if (VPlanBuildStressTest)
-      return NoVectorization;
+      return VectorizationFactor::Disabled();
 
     return {UserVF, 0};
   }
 
   LLVM_DEBUG(
       dbgs() << "LV: Not vectorizing. Inner loops aren't supported in the "
                 "VPlan-native path.\n");
-  return NoVectorization;
+  return VectorizationFactor::Disabled();
 }
 
-VectorizationFactor
-LoopVectorizationPlanner::plan(bool OptForSize, unsigned UserVF) {
+Optional<VectorizationFactor> LoopVectorizationPlanner::plan(bool OptForSize,
+                                                             unsigned UserVF) {
   assert(OrigLoop->empty() && "Inner loop expected.");
-  // Width 1 means no vectorization, cost 0 means uncomputed cost.
-  const VectorizationFactor NoVectorization = {1U, 0U};
   Optional<unsigned> MaybeMaxVF = CM.computeMaxVF(OptForSize);
-  if (!MaybeMaxVF.hasValue()) // Cases considered too costly to vectorize.
-    return NoVectorization;
+  if (!MaybeMaxVF) // Cases that should not to be vectorized nor interleaved.
+    return None;
 
   // 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");
     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}};
   }
 
   unsigned MaxVF = MaybeMaxVF.getValue();
   assert(MaxVF != 0 && "MaxVF is zero.");
 
   for (unsigned VF = 1; 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)
       CM.collectInstsToScalarize(VF);
   }
 
   buildVPlansWithVPRecipes(1, MaxVF);
   LLVM_DEBUG(printPlans(dbgs()));
   if (MaxVF == 1)
-    return NoVectorization;
+    return VectorizationFactor::Disabled();
 
   // Select the optimal vectorization factor.
   return CM.selectVectorizationFactor(MaxVF);
 }
 
 void LoopVectorizationPlanner::setBestPlan(unsigned VF, unsigned UF) {
   LLVM_DEBUG(dbgs() << "Setting best plan to VF=" << VF << ", UF=" << UF
                     << '\n');
#endif /* NDEBUG */
 
   // 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);
+  Optional<VectorizationFactor> MaybeVF = LVP.plan(OptForSize, UserVF);
 
-  // Get user interleave count.
+  VectorizationFactor VF = VectorizationFactor::Disabled();
+  unsigned IC = 1;
   unsigned UserIC = Hints.getInterleave();
 
   // Identify the diagnostic messages that should be produced.
   std::pair<StringRef, std::string> VecDiagMsg, IntDiagMsg;
   bool VectorizeLoop = true, InterleaveLoop = true;
+  if (MaybeVF) {
+    VF = *MaybeVF;
+    // Select the interleave count.
+    IC = CM.selectInterleaveCount(OptForSize, VF.Width, VF.Cost);
+  } else if (UserIC > 1) {
+    // Tell the user interleaving was avoided up-front, despite being explicitly
+    // requested.
+    LLVM_DEBUG(dbgs() << "LV: Ignoring UserIC, because vectorization and "
+                         "interleaving should be avoided up front\n");
+    IntDiagMsg = std::make_pair(
+        "InterleavingAvoided",
+        "Ignoring UserIC, because interleaving was avoided up front");
+    InterleaveLoop = false;
+    UserIC = 1;
+  }
+
   if (Requirements.doesNotMeet(F, L, Hints)) {
     LLVM_DEBUG(dbgs() << "LV: Not vectorizing: loop did not meet vectorization "
                          "requirements.\n");
     Hints.emitRemarkWithHints();
     return false;
   }
 
   if (VF.Width == 1) {

llvm/test/Transforms/LoopVectorize/no-interleave-up-front.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"
+
+; Test case based on reproducer for
+; http://bugs.chromium.org/p/oss-fuzz/issues/detail?id=6477
+
+define void @test1(i32 %n) #0 {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    br i1 false, label [[DOTLR_PH_PREHEADER:%.*]], label [[DOT_CRIT_EDGE:%.*]]
+; CHECK:       .lr.ph.preheader:
+; CHECK-NEXT:    br label [[DOTLR_PH:%.*]]
+; CHECK:       .lr.ph:
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[DOTLR_PH]] ], [ 0, [[DOTLR_PH_PREHEADER]] ]
+; 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 !0
+; 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}