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 phis for which we need to add the incoming value 60 /// from the backedge after all recipes have been created. 61 SmallVector<VPWidenPHIRecipe *, 4> PhisToFix; 62 63 /// Check if \p I can be widened at the start of \p Range and possibly 64 /// decrease the range such that the returned value holds for the entire \p 65 /// Range. The function should not be called for memory instructions or calls. 66 bool shouldWiden(Instruction *I, VFRange &Range) const; 67 68 /// Check if the load or store instruction \p I should widened for \p 69 /// Range.Start and potentially masked. Such instructions are handled by a 70 /// recipe that takes an additional VPInstruction for the mask. 71 VPRecipeBase *tryToWidenMemory(Instruction *I, ArrayRef<VPValue *> Operands, 72 VFRange &Range, VPlanPtr &Plan); 73 74 /// Check if an induction recipe should be constructed for \I. If so build and 75 /// return it. If not, return null. 76 VPWidenIntOrFpInductionRecipe * 77 tryToOptimizeInductionPHI(PHINode *Phi, ArrayRef<VPValue *> Operands) const; 78 79 /// Optimize the special case where the operand of \p I is a constant integer 80 /// induction variable. 81 VPWidenIntOrFpInductionRecipe * 82 tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands, 83 VFRange &Range, VPlan &Plan) const; 84 85 /// Handle non-loop phi nodes. Return a VPValue, if all incoming values match 86 /// or a new VPBlendRecipe otherwise. Currently all such phi nodes are turned 87 /// into a sequence of select instructions as the vectorizer currently 88 /// performs full if-conversion. 89 VPRecipeOrVPValueTy tryToBlend(PHINode *Phi, ArrayRef<VPValue *> Operands, 90 VPlanPtr &Plan); 91 92 /// Handle call instructions. If \p CI can be widened for \p Range.Start, 93 /// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same 94 /// decision from \p Range.Start to \p Range.End. 95 VPWidenCallRecipe *tryToWidenCall(CallInst *CI, ArrayRef<VPValue *> Operands, 96 VFRange &Range) const; 97 98 /// Check if \p I has an opcode that can be widened and return a VPWidenRecipe 99 /// if it can. The function should only be called if the cost-model indicates 100 /// that widening should be performed. 101 VPWidenRecipe *tryToWiden(Instruction *I, ArrayRef<VPValue *> Operands) const; 102 103 /// 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. toVPRecipeResult(VPRecipeBase * R)104 VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; } 105 106 public: VPRecipeBuilder(Loop * OrigLoop,const TargetLibraryInfo * TLI,LoopVectorizationLegality * Legal,LoopVectorizationCostModel & CM,PredicatedScalarEvolution & PSE,VPBuilder & Builder)107 VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI, 108 LoopVectorizationLegality *Legal, 109 LoopVectorizationCostModel &CM, 110 PredicatedScalarEvolution &PSE, VPBuilder &Builder) 111 : OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), PSE(PSE), 112 Builder(Builder) {} 113 114 /// Check if an existing VPValue can be used for \p Instr or a recipe can be 115 /// create for \p I withing the given VF \p Range. If an existing VPValue can 116 /// be used or if a recipe can be created, return it. Otherwise return a 117 /// VPRecipeOrVPValueTy with nullptr. 118 VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr, 119 ArrayRef<VPValue *> Operands, 120 VFRange &Range, VPlanPtr &Plan); 121 122 /// Set the recipe created for given ingredient. This operation is a no-op for 123 /// ingredients that were not marked using a nullptr entry in the map. setRecipe(Instruction * I,VPRecipeBase * R)124 void setRecipe(Instruction *I, VPRecipeBase *R) { 125 if (!Ingredient2Recipe.count(I)) 126 return; 127 assert(Ingredient2Recipe[I] == nullptr && 128 "Recipe already set for ingredient"); 129 Ingredient2Recipe[I] = R; 130 } 131 132 /// A helper function that computes the predicate of the block BB, assuming 133 /// that the header block of the loop is set to True. It returns the *entry* 134 /// mask for the block BB. 135 VPValue *createBlockInMask(BasicBlock *BB, VPlanPtr &Plan); 136 137 /// A helper function that computes the predicate of the edge between SRC 138 /// and DST. 139 VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlanPtr &Plan); 140 141 /// Mark given ingredient for recording its recipe once one is created for 142 /// it. recordRecipeOf(Instruction * I)143 void recordRecipeOf(Instruction *I) { 144 assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) && 145 "Recipe already set for ingredient"); 146 Ingredient2Recipe[I] = nullptr; 147 } 148 149 /// Return the recipe created for given ingredient. getRecipe(Instruction * I)150 VPRecipeBase *getRecipe(Instruction *I) { 151 assert(Ingredient2Recipe.count(I) && 152 "Recording this ingredients recipe was not requested"); 153 assert(Ingredient2Recipe[I] != nullptr && 154 "Ingredient doesn't have a recipe"); 155 return Ingredient2Recipe[I]; 156 } 157 158 /// Create a replicating region for instruction \p I that requires 159 /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I. 160 VPRegionBlock *createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe, 161 VPlanPtr &Plan); 162 163 /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it 164 /// is predicated. \return \p VPBB augmented with this new recipe if \p I is 165 /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new 166 /// Region. Update the packing decision of predicated instructions if they 167 /// feed \p I. Range.End may be decreased to ensure same recipe behavior from 168 /// \p Range.Start to \p Range.End. 169 VPBasicBlock *handleReplication( 170 Instruction *I, VFRange &Range, VPBasicBlock *VPBB, 171 VPlanPtr &Plan); 172 173 /// Add the incoming values from the backedge to reduction cross-iteration 174 /// phis. 175 void fixHeaderPhis(); 176 }; 177 } // end namespace llvm 178 179 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H 180