[VPlan] Allow building a VPlan to may fail.

[fhahn]

Summary

Update the planning code constructing VPlan to allow building VPlans to
fail. This allows us to gradually shift some legality checks to VPlan
construction. The first candidate is checking if all users of
first-order recurrence phis can be sunk past the recipe computing the
previous value.

[Ayal]

Adding a couple of nits. The optional functionality added cannot yet be exercised (with a test)?

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

352

What can be said about Range.End if this returns empty handed? As explained above, Range.End is possibly decreased according to the relevant VF's if this returns a VPlanPtr.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7598

Worth printing/reporting something if no plan was built?

[fhahn]

In D142885#4097064, @Ayal wrote:

Adding a couple of nits. The optional functionality added cannot yet be exercised (with a test)?

Unfortunately I don't think it can be tested independently. D142886 starts exercising the code path.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

352

Range.End must be greater than Range.Start in order to make forward progress even if a VPlan cannot be built for Range.Start. Suffice to say that if a VPlan cannot be built for Range.Start then Range.End must be set such that a VPlan cannot be built for any VF between Range.Start (inclusive) and Range.End (exclusive), where Range.End must be greater than Range.Start?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7598

Above LLVM_DEBUG() probably prints nothing and no report is issued for ignoring UserVF if no plan was built?

7628

ditto?

[fhahn]

Address comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

352

I updated the comment to try to make things clearer. If no VPlan can be built for a given range, the largest VF included in Range will be set to the maximum VF for which no plan could be built.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7598

Updated to print if no plan could be built.

7628

Thanks, added a debug print below.

[fhahn]

ping :)

[Ayal]

This is fine, adding a minor nit.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8737

nit: why is std::move() needed here now, because buildVPlanWithVPRecipes() now returns an std::optional<VPlanPtr> instead of a VPlanPtr? Could nullptr be returned instead of optional?

[fhahn]

Thanks for taking a look! I think it would be good to land this together with a concrete use of the new functionality, which would be D142886 (still needing review :))

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8737

IIUC it's needed because std::unique_ptr doesn't allow copying.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8737

Ok, but can an empty unique_ptr initialized to null be returned, instead of optional and move?

[tschuett]

Now that building may fail, you could even call it tryBuildVPlanWithVPRecipes .

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8737

std::nullopt is the modern and saver version of nullptr. It is more obvious that std::nullopt denotes failure.

[fhahn]

Rename to tryToBuildVPlanWithVPRecipes as suggested, thanks!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8737

We cannot avoid the move I think, regardless of whether std::optional is used or not. Without the move, std::unique_ptr's copy constructor would be called which is deleted.

I could change it to not use std::optional while retaining the move if you have a strong preference to avoid std::optional.

[tschuett]

In D142885#4209221, @fhahn wrote:

Rename to tryToBuildVPlanWithVPRecipes as suggested, thanks!

I was never questioning the move. I just wanted to note that I prefer std::nullopt over nullptr to denote failure.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8737

No strong preference, patch was accepted as is, just wanted to clarify the options.
The optional is optional - had a standard pointer been returned rather than a unique_ptr, it would have been more natural to return null rather than optional, so it seems natural to also do so here and return an empty unique_ptr rather than wrap with optional.
(The move can be avoided, by always storing the VPlanPtr in VPlans, even when it is empty. But then one must check for empty VPlans whenever iterating over them.)

[fhahn]

Rebase before landing.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

 
 private:
   /// Build a VPlan according to the information gathered by Legal. \return a
   /// VPlan for vectorization factors \p Range.Start and up to \p Range.End
   /// exclusive, possibly decreasing \p Range.End.
   VPlanPtr buildVPlan(VFRange &Range);
 
   /// Build a VPlan using VPRecipes according to the information gather by
   /// Legal. This method is only used for the legacy inner loop vectorizer.
-  VPlanPtr
-  buildVPlanWithVPRecipes(VFRange &Range,
-                          SmallPtrSetImpl<Instruction *> &DeadInstructions);
+  /// \p Range's largest included VF is restricted to the maximum VF the
+  /// returned VPlan is valid for. If no VPlan can be built for the input range,
+  /// set the largest included VF to the maximum VF for which no plan could be
+  /// built.
+  std::optional<VPlanPtr> tryToBuildVPlanWithVPRecipes(
+      VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions);
 
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
   /// according to the information gathered by Legal when it checked if it is
   /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
   void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF);
 
   // Adjust the recipes for reductions. For in-loop reductions the chain of
   // instructions leading from the loop exit instr to the phi need to be

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

if (!UserVF.isZero() && UserVFIsLegal) {
     assert(isPowerOf2_32(UserVF.getKnownMinValue()) &&
            "VF needs to be a power of two");
     // Collect the instructions (and their associated costs) that will be more
     // profitable to scalarize.
     if (CM.selectUserVectorizationFactor(UserVF)) {
       LLVM_DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n");
       CM.collectInLoopReductions();
       buildVPlansWithVPRecipes(UserVF, UserVF);
+      if (!hasPlanWithVF(UserVF)) {
+        LLVM_DEBUG(dbgs() << "LV: No VPlan could be built for " << UserVF
+                          << ".\n");
+        return std::nullopt;
+      }
+
       LLVM_DEBUG(printPlans(dbgs()));
       return {{UserVF, 0, 0}};
     } else
       reportVectorizationInfo("UserVF ignored because of invalid costs.",
                               "InvalidCost", ORE, OrigLoop);
   }
 
   // Populate the set of Vectorization Factor Candidates.
   ElementCountSet VFCandidates;
for (const auto &VF : VFCandidates) {
     if (VF.isVector())
       CM.collectInstsToScalarize(VF);
   }
 
   CM.collectInLoopReductions();
   buildVPlansWithVPRecipes(ElementCount::getFixed(1), MaxFactors.FixedVF);
   buildVPlansWithVPRecipes(ElementCount::getScalable(1), MaxFactors.ScalableVF);
 
   LLVM_DEBUG(printPlans(dbgs()));
   if (!MaxFactors.hasVector())
     return VectorizationFactor::Disabled();
 
   // Select the optimal vectorization factor.
   VectorizationFactor VF = CM.selectVectorizationFactor(VFCandidates);
   assert((VF.Width.isScalar() || VF.ScalarCost > 0) && "when vectorizing, the scalar cost must be non-zero.");
+  if (!hasPlanWithVF(VF.Width)) {
+    LLVM_DEBUG(dbgs() << "LV: No VPlan could be built for " << VF.Width
+                      << ".\n");
+    return std::nullopt;
+  }
   return VF;
 }
 
 VPlan &LoopVectorizationPlanner::getBestPlanFor(ElementCount VF) const {
   assert(count_if(VPlans,
                   [VF](const VPlanPtr &Plan) { return Plan->hasVF(VF); }) ==
              1 &&
          "Best VF has not a single VPlan.");
void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
   // control flow is preserved, we should keep them.
   SmallPtrSet<Instruction *, 4> DeadInstructions;
   auto &ConditionalAssumes = Legal->getConditionalAssumes();
   DeadInstructions.insert(ConditionalAssumes.begin(), ConditionalAssumes.end());
 
   auto MaxVFTimes2 = MaxVF * 2;
   for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFTimes2);) {
     VFRange SubRange = {VF, MaxVFTimes2};
-    VPlans.push_back(buildVPlanWithVPRecipes(SubRange, DeadInstructions));
+    if (auto Plan = tryToBuildVPlanWithVPRecipes(SubRange, DeadInstructions))
+      VPlans.push_back(std::move(*Plan));
     VF = SubRange.End;
   }
 }
 
 // Add the necessary canonical IV and branch recipes required to control the
 // loop.
 static void addCanonicalIVRecipes(VPlan &Plan, Type *IdxTy, DebugLoc DL,
                                   TailFoldingStyle Style) {
static void addUsersInExitBlock(VPBasicBlock *HeaderVPBB,
   for (PHINode &ExitPhi : ExitBB->phis()) {
     Value *IncomingValue =
         ExitPhi.getIncomingValueForBlock(ExitingBB);
     VPValue *V = Plan.getOrAddVPValue(IncomingValue, true);
     Plan.addLiveOut(&ExitPhi, V);
   }
 }
 
-VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
+std::optional<VPlanPtr> LoopVectorizationPlanner::tryToBuildVPlanWithVPRecipes(
     VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions) {
 
   SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
 
   VPRecipeBuilder RecipeBuilder(OrigLoop, TLI, Legal, CM, PSE, Builder);
 
   // ---------------------------------------------------------------------------
   // Pre-construction: record ingredients whose recipes we'll need to further