[LV] Switch to using pre-computed VF ranges instead clamping.

[fhahn]

Summary

This patch replaces the current logic to clamp the vectorization factors
during recipe creation with using pre-computed VF ranges. The clamp is
replaced with a assertion checking that the same decision is taken for
all VFs in the current range.

The main motivation is untangling the VF range clamping from recipe
creation. Computing the ranges of VFs with matching decisions up-front
will enable us to break down VPlan creation into more modular steps.

[fhahn]

I changed focus on transitioning sinking of scalar operands to a VPlan-to-VPlan transform in D100258.

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

return any_of(VPlans, [&](const VPlanPtr &Plan) {
       });
     });
   }
 
   /// Test a \p Predicate on a \p Range of VF's. Return the value of applying
   /// \p Predicate on Range.Start, possibly decreasing Range.End such that the
   /// returned value holds for the entire \p Range.
   static bool
-  getDecisionAndClampRange(const std::function<bool(ElementCount)> &Predicate,
-                           VFRange &Range);
+  checkDecisionAcrossRange(const std::function<bool(ElementCount)> &Predicate,
+                           const VFRange &Range);
 
 protected:
   /// Collect the instructions from the original loop that would be trivially
   /// dead in the vectorized loop if generated.
   void collectTriviallyDeadInstructions(
       SmallPtrSetImpl<Instruction *> &DeadInstructions);
 
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

 }
 
 void EpilogueVectorizerEpilogueLoop::printDebugTracesAtEnd() {
   DEBUG_WITH_TYPE(VerboseDebug, {
     dbgs() << "final fn:\n" << *Induction->getFunction() << "\n";
   });
 }
 
-bool LoopVectorizationPlanner::getDecisionAndClampRange(
-    const std::function<bool(ElementCount)> &Predicate, VFRange &Range) {
+bool LoopVectorizationPlanner::checkDecisionAcrossRange(
+    const std::function<bool(ElementCount)> &Predicate, const VFRange &Range) {
   assert(!Range.isEmpty() && "Trying to test an empty VF range.");
   bool PredicateAtRangeStart = Predicate(Range.Start);
 
   for (ElementCount TmpVF = Range.Start * 2;
        ElementCount::isKnownLT(TmpVF, Range.End); TmpVF *= 2)
-    if (Predicate(TmpVF) != PredicateAtRangeStart) {
-      Range.End = TmpVF;
-      break;
-    }
+    if (Predicate(TmpVF) != PredicateAtRangeStart)
+      return false;
 
-  return PredicateAtRangeStart;
+  return true;
 }
 
 /// Build VPlans for the full range of feasible VF's = {\p MinVF, 2 * \p MinVF,
 /// 4 * \p MinVF, ..., \p MaxVF} by repeatedly building a VPlan for a sub-range
 /// of VF's starting at a given VF and extending it as much as possible. Each
 /// vectorization decision can potentially shorten this sub-range during
 /// buildVPlan().
 void LoopVectorizationPlanner::buildVPlans(ElementCount MinVF,
for (auto *Predecessor : predecessors(BB)) {
     }
 
     BlockMask = Builder.createOr(BlockMask, EdgeMask);
   }
 
   return BlockMaskCache[BB] = BlockMask;
 }
 
-VPRecipeBase *VPRecipeBuilder::tryToWidenMemory(Instruction *I, VFRange &Range,
+VPRecipeBase *VPRecipeBuilder::tryToWidenMemory(Instruction *I,
+                                                const VFRange &Range,
                                                 VPlanPtr &Plan) {
   assert((isa<LoadInst>(I) || isa<StoreInst>(I)) &&
          "Must be called with either a load or store");
 
   auto willWiden = [&](ElementCount VF) -> bool {
     return CM.shouldWidenMemory(I, VF);
   };
 
-  if (!LoopVectorizationPlanner::getDecisionAndClampRange(willWiden, Range))
+  assert(LoopVectorizationPlanner::checkDecisionAcrossRange(willWiden, Range));
+  if (!willWiden(Range.Start))
     return nullptr;
 
   VPValue *Mask = nullptr;
   if (Legal->isMaskRequired(I))
     Mask = createBlockInMask(I->getParent(), Plan);
 
   VPValue *Addr = Plan->getOrAddVPValue(getLoadStorePointerOperand(I));
   if (LoadInst *Load = dyn_cast<LoadInst>(I))
if (II.getKind() == InductionDescriptor::IK_IntInduction ||
     const SmallVectorImpl<Instruction *> &Casts = II.getCastInsts();
     return new VPWidenIntOrFpInductionRecipe(
         Phi, Start, Casts.empty() ? nullptr : Casts.front());
   }
 
   return nullptr;
 }
 
-VPWidenIntOrFpInductionRecipe *
-VPRecipeBuilder::tryToOptimizeInductionTruncate(TruncInst *I, VFRange &Range,
-                                                VPlan &Plan) const {
+VPWidenIntOrFpInductionRecipe *VPRecipeBuilder::tryToOptimizeInductionTruncate(
+    TruncInst *I, const VFRange &Range, VPlan &Plan) const {
   // Optimize the special case where the source is a constant integer
   // induction variable. Notice that we can only optimize the 'trunc' case
   // because (a) FP conversions lose precision, (b) sext/zext may wrap, and
   // (c) other casts depend on pointer size.
 
   // Determine whether \p K is a truncation based on an induction variable that
   // can be optimized.
-  auto isOptimizableIVTruncate =
-      [&](Instruction *K) -> std::function<bool(ElementCount)> {
-    return [=](ElementCount VF) -> bool {
-      return CM.isOptimizableIVTruncate(K, VF);
-    };
+  auto isOptimizableIVTruncate = [this, I](ElementCount VF) {
+    return CM.isOptimizableIVTruncate(I, VF);
   };
 
-  if (LoopVectorizationPlanner::getDecisionAndClampRange(
-          isOptimizableIVTruncate(I), Range)) {
+  assert(LoopVectorizationPlanner::checkDecisionAcrossRange(
+      isOptimizableIVTruncate, Range));
+  if (!isOptimizableIVTruncate(Range.Start))
+    return nullptr;
 
-    InductionDescriptor II =
-        Legal->getInductionVars().lookup(cast<PHINode>(I->getOperand(0)));
-    VPValue *Start = Plan.getOrAddVPValue(II.getStartValue());
-    return new VPWidenIntOrFpInductionRecipe(cast<PHINode>(I->getOperand(0)),
-                                             Start, nullptr, I);
-  }
-  return nullptr;
-}
 
 VPRecipeOrVPValueTy VPRecipeBuilder::tryToBlend(PHINode *Phi, VPlanPtr &Plan) {
   // If all incoming values are equal, the incoming VPValue can be used directly
   // instead of creating a new VPBlendRecipe.
   Value *FirstIncoming = Phi->getIncomingValue(0);
   if (all_of(Phi->incoming_values(), [FirstIncoming](const Value *Inc) {
         return FirstIncoming == Inc;
       })) {
assert((EdgeMask || NumIncoming == 1) &&
            "Multiple predecessors with one having a full mask");
     Operands.push_back(Plan->getOrAddVPValue(Phi->getIncomingValue(In)));
     if (EdgeMask)
       Operands.push_back(EdgeMask);
   }
   return toVPRecipeResult(new VPBlendRecipe(Phi, Operands));
 }
 
-VPWidenCallRecipe *VPRecipeBuilder::tryToWidenCall(CallInst *CI, VFRange &Range,
+VPWidenCallRecipe *VPRecipeBuilder::tryToWidenCall(CallInst *CI,
+                                                   const VFRange &Range,
                                                    VPlan &Plan) const {
 
-  bool IsPredicated = LoopVectorizationPlanner::getDecisionAndClampRange(
-      [this, CI](ElementCount VF) {
-        return CM.isScalarWithPredication(CI, VF);
-      },
-      Range);
+  auto willPredicate = [this, CI](ElementCount VF) {
+  };
 
-  if (IsPredicated)
+  assert(
+      LoopVectorizationPlanner::checkDecisionAcrossRange(willPredicate, Range));
+  if (willPredicate(Range.Start))
     return nullptr;
 
   auto willWiden = [&](ElementCount VF) -> bool {
     return CM.shouldWidenCall(CI, VF);
   };
 
-  if (!LoopVectorizationPlanner::getDecisionAndClampRange(willWiden, Range))
+  assert(LoopVectorizationPlanner::checkDecisionAcrossRange(willWiden, Range));
+  if (!willWiden(Range.Start))
     return nullptr;
 
   return new VPWidenCallRecipe(*CI, Plan.mapToVPValues(CI->arg_operands()));
 }
 
-bool VPRecipeBuilder::shouldWiden(Instruction *I, VFRange &Range) const {
+bool VPRecipeBuilder::shouldWiden(Instruction *I, const VFRange &Range) const {
   assert(!isa<BranchInst>(I) && !isa<PHINode>(I) && !isa<LoadInst>(I) &&
          !isa<StoreInst>(I) && "Instruction should have been handled earlier");
   // Instruction should be widened, unless it is scalar after vectorization,
   // scalarization is profitable or it is predicated.
   auto ShouldScalarize = [this, I](ElementCount VF) -> bool {
     return CM.shouldScalarize(I, VF);
   };
-  return !LoopVectorizationPlanner::getDecisionAndClampRange(ShouldScalarize,
-                                                             Range);
+  assert(LoopVectorizationPlanner::checkDecisionAcrossRange(ShouldScalarize,
+                                                            Range));
+  return !ShouldScalarize(Range.Start);
 }
 
 VPWidenRecipe *VPRecipeBuilder::tryToWiden(Instruction *I, VPlan &Plan) const {
   auto IsVectorizableOpcode = [](unsigned Opcode) {
     switch (Opcode) {
     case Instruction::Add:
     case Instruction::And:
     case Instruction::AShr:
VPWidenRecipe *VPRecipeBuilder::tryToWiden(Instruction *I, VPlan &Plan) const {
 
   if (!IsVectorizableOpcode(I->getOpcode()))
     return nullptr;
 
   // Success: widen this instruction.
   return new VPWidenRecipe(*I, Plan.mapToVPValues(I->operands()));
 }
 
-VPBasicBlock *VPRecipeBuilder::handleReplication(
-    Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
+VPBasicBlock *VPRecipeBuilder::handleReplication(Instruction *I,
+                                                 const VFRange &Range,
+                                                 VPBasicBlock *VPBB,
                                                  VPlanPtr &Plan) {
-  bool IsUniform = LoopVectorizationPlanner::getDecisionAndClampRange(
-      [&](ElementCount VF) { return CM.isUniformAfterVectorization(I, VF); },
-      Range);
-
-  bool IsPredicated = LoopVectorizationPlanner::getDecisionAndClampRange(
-      [&](ElementCount VF) { return CM.isScalarWithPredication(I, VF); },
-      Range);
+  auto IsUniformCheck = [&](ElementCount VF) {
+    return CM.isUniformAfterVectorization(I, VF);
+  };
+  assert(LoopVectorizationPlanner::checkDecisionAcrossRange(IsUniformCheck,
+                                                            Range));
+  bool IsUniform = IsUniformCheck(Range.Start);
+
+  auto IsPredicatedFn = [&](ElementCount VF) {
+    return CM.isScalarWithPredication(I, VF);
+  };
+  assert(LoopVectorizationPlanner::checkDecisionAcrossRange(IsPredicatedFn,
+                                                            Range));
+  bool IsPredicated = IsPredicatedFn(Range.Start);
 
   auto *Recipe = new VPReplicateRecipe(I, Plan->mapToVPValues(I->operands()),
                                        IsUniform, IsPredicated);
   setRecipe(I, Recipe);
   Plan->addVPValue(I, Recipe);
 
   // Find if I uses a predicated instruction. If so, it will use its scalar
   // value. Avoid hoisting the insert-element which packs the scalar value into
VPRegionBlock *VPRecipeBuilder::createReplicateRegion(Instruction *Instr,
   // Note: first set Entry as region entry and then connect successors starting
   // from it in order, to propagate the "parent" of each VPBasicBlock.
   VPBlockUtils::insertTwoBlocksAfter(Pred, Exit, BlockInMask, Entry);
   VPBlockUtils::connectBlocks(Pred, Exit);
 
   return Region;
 }
 
-VPRecipeOrVPValueTy VPRecipeBuilder::tryToCreateWidenRecipe(Instruction *Instr,
-                                                            VFRange &Range,
-                                                            VPlanPtr &Plan) {
+VPRecipeOrVPValueTy
+VPRecipeBuilder::tryToCreateWidenRecipe(Instruction *Instr,
+                                        const VFRange &Range, VPlanPtr &Plan) {
   // First, check for specific widening recipes that deal with calls, memory
   // operations, inductions and Phi nodes.
   if (auto *CI = dyn_cast<CallInst>(Instr))
     return toVPRecipeResult(tryToWidenCall(CI, Range, *Plan));
 
   if (isa<LoadInst>(Instr) || isa<StoreInst>(Instr))
     return toVPRecipeResult(tryToWidenMemory(Instr, Range, Plan));
 
void LoopVectorizationPlanner::buildVPlansWithVPRecipes(ElementCount MinVF,
   DeadInstructions.insert(ConditionalAssumes.begin(), ConditionalAssumes.end());
 
   DenseMap<Instruction *, Instruction *> &SinkAfter = Legal->getSinkAfter();
   // Dead instructions do not need sinking. Remove them from SinkAfter.
   for (Instruction *I : DeadInstructions)
     SinkAfter.erase(I);
 
   auto Ranges = computeRanges(MinVF, MaxVF, DeadInstructions);
-  auto MaxVFPlusOne = MaxVF.getWithIncrement(1);
-  unsigned I = 0;
-  for (ElementCount VF = MinVF; ElementCount::isKnownLT(VF, MaxVFPlusOne);) {
-    VFRange SubRange = {VF, MaxVFPlusOne};
+  for (auto &SubRange : Ranges)
     VPlans.push_back(
         buildVPlanWithVPRecipes(SubRange, DeadInstructions, SinkAfter));
-    VF = SubRange.End;
-    assert(Ranges[I].Start == SubRange.Start && Ranges[I].End == SubRange.End &&
-           "clamped range should match computed range");
-    I++;
-  }
-
-  assert(Ranges.size() == VPlans.size() &&
-         "should have the same number of clamped and computed ranges");
 }
 
 VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
     VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
     const DenseMap<Instruction *, Instruction *> &SinkAfter) {
 
   SmallPtrSet<const InterleaveGroup<Instruction> *, 1> InterleaveGroups;
 
for (auto &R : ReductionOperations) {
         RecipeBuilder.recordRecipeOf(cast<Instruction>(R->getOperand(0)));
     }
   }
 
   // For each interleave group which is relevant for this (possibly trimmed)
   // Range, add it to the set of groups to be later applied to the VPlan and add
   // placeholders for its members' Recipes which we'll be replacing with a
   // single VPInterleaveRecipe.
+  if (Range.Start.isVector()) {
     for (InterleaveGroup<Instruction> *IG : IAI.getInterleaveGroups()) {
       auto applyIG = [IG, this](ElementCount VF) -> bool {
         return (VF.isVector() && // Query is illegal for VF == 1
                 CM.getWideningDecision(IG->getInsertPos(), VF) ==
                     LoopVectorizationCostModel::CM_Interleave);
       };
-    if (!getDecisionAndClampRange(applyIG, Range))
+      assert(checkDecisionAcrossRange(applyIG, Range));
+      if (!applyIG(Range.Start))
         continue;
       InterleaveGroups.insert(IG);
       for (unsigned i = 0; i < IG->getFactor(); i++)
         if (Instruction *Member = IG->getMember(i))
           RecipeBuilder.recordRecipeOf(Member);
-  };
+    }
+  }
 
   // ---------------------------------------------------------------------------
   // Build initial VPlan: Scan the body of the loop in a topological order to
   // visit each basic block after having visited its predecessor basic blocks.
   // ---------------------------------------------------------------------------
 
   // Create a dummy pre-entry VPBasicBlock to start building the VPlan.
   auto Plan = std::make_unique<VPlan>();

llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

class VPRecipeBuilder {
   // VPlan-VPlan transformations support: Hold a mapping from ingredients to
   // their recipe. To save on memory, only do so for selected ingredients,
   // marked by having a nullptr entry in this map.
   DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
 
   /// Check if \p I can be widened at the start of \p Range and possibly
   /// decrease the range such that the returned value holds for the entire \p
   /// Range. The function should not be called for memory instructions or calls.
-  bool shouldWiden(Instruction *I, VFRange &Range) const;
+  bool shouldWiden(Instruction *I, const VFRange &Range) const;
 
   /// Check if the load or store instruction \p I should widened for \p
   /// Range.Start and potentially masked. Such instructions are handled by a
   /// recipe that takes an additional VPInstruction for the mask.
-  VPRecipeBase *tryToWidenMemory(Instruction *I, VFRange &Range,
+  VPRecipeBase *tryToWidenMemory(Instruction *I, const VFRange &Range,
                                  VPlanPtr &Plan);
 
   /// Check if an induction recipe should be constructed for \I. If so build and
   /// return it. If not, return null.
   VPWidenIntOrFpInductionRecipe *tryToOptimizeInductionPHI(PHINode *Phi,
                                                            VPlan &Plan) const;
 
   /// Optimize the special case where the operand of \p I is a constant integer
   /// induction variable.
   VPWidenIntOrFpInductionRecipe *
-  tryToOptimizeInductionTruncate(TruncInst *I, VFRange &Range,
+  tryToOptimizeInductionTruncate(TruncInst *I, const VFRange &Range,
                                  VPlan &Plan) const;
 
   /// Handle non-loop phi nodes. Return a VPValue, if all incoming values match
   /// or a new VPBlendRecipe otherwise. Currently all such phi nodes are turned
   /// into a sequence of select instructions as the vectorizer currently
   /// performs full if-conversion.
   VPRecipeOrVPValueTy tryToBlend(PHINode *Phi, VPlanPtr &Plan);
 
   /// Handle call instructions. If \p CI can be widened for \p Range.Start,
   /// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same
   /// decision from \p Range.Start to \p Range.End.
-  VPWidenCallRecipe *tryToWidenCall(CallInst *CI, VFRange &Range,
+  VPWidenCallRecipe *tryToWidenCall(CallInst *CI, const VFRange &Range,
                                     VPlan &Plan) const;
 
   /// Check if \p I has an opcode that can be widened and return a VPWidenRecipe
   /// if it can. The function should only be called if the cost-model indicates
   /// that widening should be performed.
   VPWidenRecipe *tryToWiden(Instruction *I, VPlan &Plan) const;
 
   /// Return a VPRecipeOrValueTy with VPRecipeBase * being set. This can be used to force the use as VPRecipeBase* for recipe sub-types that also inherit from VPValue.
   VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; }
 
 public:
   VPRecipeBuilder(Loop *OrigLoop, LoopVectorizationLegality *Legal,
                   LoopVectorizationCostModel &CM,
                   PredicatedScalarEvolution &PSE, VPBuilder &Builder)
       : OrigLoop(OrigLoop), Legal(Legal), CM(CM), PSE(PSE), Builder(Builder) {}
 
   /// Check if an existing VPValue can be used for \p Instr or a recipe can be
   /// create for \p I withing the given VF \p Range. If an existing VPValue can
   /// be used or if a recipe can be created, return it. Otherwise return a
   /// VPRecipeOrVPValueTy with nullptr.
-  VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr, VFRange &Range,
+  VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr,
+                                             const VFRange &Range,
                                              VPlanPtr &Plan);
 
   /// Set the recipe created for given ingredient. This operation is a no-op for
   /// ingredients that were not marked using a nullptr entry in the map.
   void setRecipe(Instruction *I, VPRecipeBase *R) {
     if (!Ingredient2Recipe.count(I))
       return;
     assert(Ingredient2Recipe[I] == nullptr &&
VPRegionBlock *createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe,
                                        VPlanPtr &Plan);
 
   /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
   /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
   /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
   /// Region. Update the packing decision of predicated instructions if they
   /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
   /// \p Range.Start to \p Range.End.
-  VPBasicBlock *handleReplication(
-      Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
-      VPlanPtr &Plan);
+  VPBasicBlock *handleReplication(Instruction *I, const VFRange &Range,
+                                  VPBasicBlock *VPBB, VPlanPtr &Plan);
 };
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H