llvm/lib/Transforms/Vectorize/VPRecipeBuilder.h

   1 //===- VPRecipeBuilder.h - Helper class to build recipes --------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
  10 #define LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
  11
  12 #include "LoopVectorizationPlanner.h"
  13 #include "VPlan.h"
  14 #include "llvm/ADT/DenseMap.h"
  15 #include "llvm/ADT/PointerUnion.h"
  16 #include "llvm/IR/IRBuilder.h"
  17
  18 namespace llvm {
  19
  20 class LoopVectorizationLegality;
  21 class LoopVectorizationCostModel;
  22 class TargetLibraryInfo;
  23
  24 using VPRecipeOrVPValueTy = PointerUnion<VPRecipeBase *, VPValue *>;
  25
  26 /// Helper class to create VPRecipies from IR instructions.
  27 class VPRecipeBuilder {
  28   /// The loop that we evaluate.
  29   Loop *OrigLoop;
  30
  31   /// Target Library Info.
  32   const TargetLibraryInfo *TLI;
  33
  34   /// The legality analysis.
  35   LoopVectorizationLegality *Legal;
  36
  37   /// The profitablity analysis.
  38   LoopVectorizationCostModel &CM;
  39
  40   PredicatedScalarEvolution &PSE;
  41
  42   VPBuilder &Builder;
  43
  44   /// When we if-convert we need to create edge masks. We have to cache values
  45   /// so that we don't end up with exponential recursion/IR. Note that
  46   /// if-conversion currently takes place during VPlan-construction, so these
  47   /// caches are only used at that stage.
  48   using EdgeMaskCacheTy =
  49       DenseMap<std::pair<BasicBlock *, BasicBlock *>, VPValue *>;
  50   using BlockMaskCacheTy = DenseMap<BasicBlock *, VPValue *>;
  51   EdgeMaskCacheTy EdgeMaskCache;
  52   BlockMaskCacheTy BlockMaskCache;
  53
  54   // VPlan-VPlan transformations support: Hold a mapping from ingredients to
  55   // their recipe. To save on memory, only do so for selected ingredients,
  56   // marked by having a nullptr entry in this map.
  57   DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
  58
  59   /// Cross-iteration reduction & first-order recurrence phis for which we need
  60   /// to add the incoming value from the backedge after all recipes have been
  61   /// created.
  62   SmallVector<VPWidenPHIRecipe *, 4> PhisToFix;
  63
  64   /// Check if \p I can be widened at the start of \p Range and possibly
  65   /// decrease the range such that the returned value holds for the entire \p
  66   /// Range. The function should not be called for memory instructions or calls.
  67   bool shouldWiden(Instruction *I, VFRange &Range) const;
  68
  69   /// Check if the load or store instruction \p I should widened for \p
  70   /// Range.Start and potentially masked. Such instructions are handled by a
  71   /// recipe that takes an additional VPInstruction for the mask.
  72   VPRecipeBase *tryToWidenMemory(Instruction *I, ArrayRef<VPValue *> Operands,
  73                                  VFRange &Range, VPlanPtr &Plan);
  74
  75   /// Check if an induction recipe should be constructed for \I. If so build and
  76   /// return it. If not, return null.
  77   VPWidenIntOrFpInductionRecipe *
  78   tryToOptimizeInductionPHI(PHINode *Phi, ArrayRef<VPValue *> Operands) const;
  79
  80   /// Optimize the special case where the operand of \p I is a constant integer
  81   /// induction variable.
  82   VPWidenIntOrFpInductionRecipe *
  83   tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands,
  84                                  VFRange &Range, VPlan &Plan) const;
  85
  86   /// Handle non-loop phi nodes. Return a VPValue, if all incoming values match
  87   /// or a new VPBlendRecipe otherwise. Currently all such phi nodes are turned
  88   /// into a sequence of select instructions as the vectorizer currently
  89   /// performs full if-conversion.
  90   VPRecipeOrVPValueTy tryToBlend(PHINode *Phi, ArrayRef<VPValue *> Operands,
  91                                  VPlanPtr &Plan);
  92
  93   /// Handle call instructions. If \p CI can be widened for \p Range.Start,
  94   /// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same
  95   /// decision from \p Range.Start to \p Range.End.
  96   VPWidenCallRecipe *tryToWidenCall(CallInst *CI, ArrayRef<VPValue *> Operands,
  97                                     VFRange &Range) const;
  98
  99   /// Check if \p I has an opcode that can be widened and return a VPWidenRecipe
 100   /// if it can. The function should only be called if the cost-model indicates
 101   /// that widening should be performed.
 102   VPWidenRecipe *tryToWiden(Instruction *I, ArrayRef<VPValue *> Operands) const;
 103
 104   /// 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.
 105   VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; }
 106
 107 public:
 108   VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI,
 109                   LoopVectorizationLegality *Legal,
 110                   LoopVectorizationCostModel &CM,
 111                   PredicatedScalarEvolution &PSE, VPBuilder &Builder)
 112       : OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), PSE(PSE),
 113         Builder(Builder) {}
 114
 115   /// Check if an existing VPValue can be used for \p Instr or a recipe can be
 116   /// create for \p I withing the given VF \p Range. If an existing VPValue can
 117   /// be used or if a recipe can be created, return it. Otherwise return a
 118   /// VPRecipeOrVPValueTy with nullptr.
 119   VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr,
 120                                              ArrayRef<VPValue *> Operands,
 121                                              VFRange &Range, VPlanPtr &Plan);
 122
 123   /// Set the recipe created for given ingredient. This operation is a no-op for
 124   /// ingredients that were not marked using a nullptr entry in the map.
 125   void setRecipe(Instruction *I, VPRecipeBase *R) {
 126     if (!Ingredient2Recipe.count(I))
 127       return;
 128     assert(Ingredient2Recipe[I] == nullptr &&
 129            "Recipe already set for ingredient");
 130     Ingredient2Recipe[I] = R;
 131   }
 132
 133   /// A helper function that computes the predicate of the block BB, assuming
 134   /// that the header block of the loop is set to True. It returns the *entry*
 135   /// mask for the block BB.
 136   VPValue *createBlockInMask(BasicBlock *BB, VPlanPtr &Plan);
 137
 138   /// A helper function that computes the predicate of the edge between SRC
 139   /// and DST.
 140   VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlanPtr &Plan);
 141
 142   /// Mark given ingredient for recording its recipe once one is created for
 143   /// it.
 144   void recordRecipeOf(Instruction *I) {
 145     assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
 146            "Recipe already set for ingredient");
 147     Ingredient2Recipe[I] = nullptr;
 148   }
 149
 150   /// Return the recipe created for given ingredient.
 151   VPRecipeBase *getRecipe(Instruction *I) {
 152     assert(Ingredient2Recipe.count(I) &&
 153            "Recording this ingredients recipe was not requested");
 154     assert(Ingredient2Recipe[I] != nullptr &&
 155            "Ingredient doesn't have a recipe");
 156     return Ingredient2Recipe[I];
 157   }
 158
 159   /// Create a replicating region for instruction \p I that requires
 160   /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
 161   VPRegionBlock *createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe,
 162                                        VPlanPtr &Plan);
 163
 164   /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
 165   /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
 166   /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
 167   /// Region. Update the packing decision of predicated instructions if they
 168   /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
 169   /// \p Range.Start to \p Range.End.
 170   VPBasicBlock *handleReplication(
 171       Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
 172       VPlanPtr &Plan);
 173
 174   /// Add the incoming values from the backedge to reduction & first-order
 175   /// recurrence cross-iteration phis.
 176   void fixHeaderPhis();
 177 };
 178 } // end namespace llvm
 179
 180 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H