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<VPHeaderPHIRecipe *, 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 \p Phi. If so build
  76   /// and return it. If not, return null.
  77   VPRecipeBase *tryToOptimizeInductionPHI(PHINode *Phi,
  78                                           ArrayRef<VPValue *> Operands,
  79                                           VPlan &Plan, VFRange &Range);
  80
  81   /// Optimize the special case where the operand of \p I is a constant integer
  82   /// induction variable.
  83   VPWidenIntOrFpInductionRecipe *
  84   tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands,
  85                                  VFRange &Range, VPlan &Plan);
  86
  87   /// Handle non-loop phi nodes. Return a VPValue, if all incoming values match
  88   /// or a new VPBlendRecipe otherwise. Currently all such phi nodes are turned
  89   /// into a sequence of select instructions as the vectorizer currently
  90   /// performs full if-conversion.
  91   VPRecipeOrVPValueTy tryToBlend(PHINode *Phi, ArrayRef<VPValue *> Operands,
  92                                  VPlanPtr &Plan);
  93
  94   /// Handle call instructions. If \p CI can be widened for \p Range.Start,
  95   /// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same
  96   /// decision from \p Range.Start to \p Range.End.
  97   VPWidenCallRecipe *tryToWidenCall(CallInst *CI, ArrayRef<VPValue *> Operands,
  98                                     VFRange &Range, VPlanPtr &Plan);
  99
 100   /// Check if \p I has an opcode that can be widened and return a VPWidenRecipe
 101   /// if it can. The function should only be called if the cost-model indicates
 102   /// that widening should be performed.
 103   VPRecipeBase *tryToWiden(Instruction *I, ArrayRef<VPValue *> Operands,
 104                            VPBasicBlock *VPBB, VPlanPtr &Plan);
 105
 106   /// 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.
 107   VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; }
 108
 109 public:
 110   VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI,
 111                   LoopVectorizationLegality *Legal,
 112                   LoopVectorizationCostModel &CM,
 113                   PredicatedScalarEvolution &PSE, VPBuilder &Builder)
 114       : OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), PSE(PSE),
 115         Builder(Builder) {}
 116
 117   /// Check if an existing VPValue can be used for \p Instr or a recipe can be
 118   /// create for \p I withing the given VF \p Range. If an existing VPValue can
 119   /// be used or if a recipe can be created, return it. Otherwise return a
 120   /// VPRecipeOrVPValueTy with nullptr.
 121   VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr,
 122                                              ArrayRef<VPValue *> Operands,
 123                                              VFRange &Range, VPBasicBlock *VPBB,
 124                                              VPlanPtr &Plan);
 125
 126   /// Set the recipe created for given ingredient. This operation is a no-op for
 127   /// ingredients that were not marked using a nullptr entry in the map.
 128   void setRecipe(Instruction *I, VPRecipeBase *R) {
 129     if (!Ingredient2Recipe.count(I))
 130       return;
 131     assert(Ingredient2Recipe[I] == nullptr &&
 132            "Recipe already set for ingredient");
 133     Ingredient2Recipe[I] = R;
 134   }
 135
 136   /// Create the mask for the vector loop header block.
 137   void createHeaderMask(VPlan &Plan);
 138
 139   /// A helper function that computes the predicate of the block BB, assuming
 140   /// that the header block of the loop is set to True or the loop mask when
 141   /// tail folding.
 142   void createBlockInMask(BasicBlock *BB, VPlan &Plan);
 143
 144   /// Returns the *entry* mask for the block \p BB.
 145   VPValue *getBlockInMask(BasicBlock *BB) const;
 146
 147   /// A helper function that computes the predicate of the edge between SRC
 148   /// and DST.
 149   VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlan &Plan);
 150
 151   /// Mark given ingredient for recording its recipe once one is created for
 152   /// it.
 153   void recordRecipeOf(Instruction *I) {
 154     assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
 155            "Recipe already set for ingredient");
 156     Ingredient2Recipe[I] = nullptr;
 157   }
 158
 159   /// Return the recipe created for given ingredient.
 160   VPRecipeBase *getRecipe(Instruction *I) {
 161     assert(Ingredient2Recipe.count(I) &&
 162            "Recording this ingredients recipe was not requested");
 163     assert(Ingredient2Recipe[I] != nullptr &&
 164            "Ingredient doesn't have a recipe");
 165     return Ingredient2Recipe[I];
 166   }
 167
 168   /// Build a VPReplicationRecipe for \p I. If it is predicated, add the mask as
 169   /// last operand. Range.End may be decreased to ensure same recipe behavior
 170   /// from \p Range.Start to \p Range.End.
 171   VPRecipeOrVPValueTy handleReplication(Instruction *I, VFRange &Range,
 172                                         VPlan &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