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 /// Helper class to create VPRecipies from IR instructions. 25 class VPRecipeBuilder { 26 /// The VPlan new recipes are added to. 27 VPlan &Plan; 28 29 /// The loop that we evaluate. 30 Loop *OrigLoop; 31 32 /// Target Library Info. 33 const TargetLibraryInfo *TLI; 34 35 /// The legality analysis. 36 LoopVectorizationLegality *Legal; 37 38 /// The profitablity analysis. 39 LoopVectorizationCostModel &CM; 40 41 PredicatedScalarEvolution &PSE; 42 43 VPBuilder &Builder; 44 45 /// When we if-convert we need to create edge masks. We have to cache values 46 /// so that we don't end up with exponential recursion/IR. Note that 47 /// if-conversion currently takes place during VPlan-construction, so these 48 /// caches are only used at that stage. 49 using EdgeMaskCacheTy = 50 DenseMap<std::pair<BasicBlock *, BasicBlock *>, VPValue *>; 51 using BlockMaskCacheTy = DenseMap<BasicBlock *, VPValue *>; 52 EdgeMaskCacheTy EdgeMaskCache; 53 BlockMaskCacheTy BlockMaskCache; 54 55 // VPlan construction support: Hold a mapping from ingredients to 56 // their recipe. 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 VPWidenMemoryRecipe *tryToWidenMemory(Instruction *I, 73 ArrayRef<VPValue *> Operands, 74 VFRange &Range); 75 76 /// Check if an induction recipe should be constructed for \p Phi. If so build 77 /// and return it. If not, return null. 78 VPHeaderPHIRecipe *tryToOptimizeInductionPHI(PHINode *Phi, 79 ArrayRef<VPValue *> Operands, 80 VFRange &Range); 81 82 /// Optimize the special case where the operand of \p I is a constant integer 83 /// induction variable. 84 VPWidenIntOrFpInductionRecipe * 85 tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands, 86 VFRange &Range); 87 88 /// Handle non-loop phi nodes. Return a new VPBlendRecipe otherwise. Currently 89 /// all such phi nodes are turned into a sequence of select instructions as 90 /// the vectorizer currently performs full if-conversion. 91 VPBlendRecipe *tryToBlend(PHINode *Phi, ArrayRef<VPValue *> Operands); 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); 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, 103 VPBasicBlock *VPBB); 104 105 public: VPRecipeBuilder(VPlan & Plan,Loop * OrigLoop,const TargetLibraryInfo * TLI,LoopVectorizationLegality * Legal,LoopVectorizationCostModel & CM,PredicatedScalarEvolution & PSE,VPBuilder & Builder)106 VPRecipeBuilder(VPlan &Plan, Loop *OrigLoop, const TargetLibraryInfo *TLI, 107 LoopVectorizationLegality *Legal, 108 LoopVectorizationCostModel &CM, 109 PredicatedScalarEvolution &PSE, VPBuilder &Builder) 110 : Plan(Plan), OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), 111 PSE(PSE), Builder(Builder) {} 112 113 /// Create and return a widened recipe for \p I if one can be created within 114 /// the given VF \p Range. 115 VPRecipeBase *tryToCreateWidenRecipe(Instruction *Instr, 116 ArrayRef<VPValue *> Operands, 117 VFRange &Range, VPBasicBlock *VPBB); 118 119 /// Set the recipe created for given ingredient. setRecipe(Instruction * I,VPRecipeBase * R)120 void setRecipe(Instruction *I, VPRecipeBase *R) { 121 assert(!Ingredient2Recipe.contains(I) && 122 "Cannot reset recipe for instruction."); 123 Ingredient2Recipe[I] = R; 124 } 125 126 /// Create the mask for the vector loop header block. 127 void createHeaderMask(); 128 129 /// A helper function that computes the predicate of the block BB, assuming 130 /// that the header block of the loop is set to True or the loop mask when 131 /// tail folding. 132 void createBlockInMask(BasicBlock *BB); 133 134 /// Returns the *entry* mask for the block \p BB. 135 VPValue *getBlockInMask(BasicBlock *BB) const; 136 137 /// A helper function that computes the predicate of the edge between SRC 138 /// and DST. 139 VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst); 140 141 /// A helper that returns the previously computed predicate of the edge 142 /// between SRC and DST. 143 VPValue *getEdgeMask(BasicBlock *Src, BasicBlock *Dst) const; 144 145 /// Return the recipe created for given ingredient. getRecipe(Instruction * I)146 VPRecipeBase *getRecipe(Instruction *I) { 147 assert(Ingredient2Recipe.count(I) && 148 "Recording this ingredients recipe was not requested"); 149 assert(Ingredient2Recipe[I] != nullptr && 150 "Ingredient doesn't have a recipe"); 151 return Ingredient2Recipe[I]; 152 } 153 154 /// Build a VPReplicationRecipe for \p I. If it is predicated, add the mask as 155 /// last operand. Range.End may be decreased to ensure same recipe behavior 156 /// from \p Range.Start to \p Range.End. 157 VPReplicateRecipe *handleReplication(Instruction *I, VFRange &Range); 158 159 /// Add the incoming values from the backedge to reduction & first-order 160 /// recurrence cross-iteration phis. 161 void fixHeaderPhis(); 162 163 /// Returns a range mapping the values of the range \p Operands to their 164 /// corresponding VPValues. 165 iterator_range<mapped_iterator<Use *, std::function<VPValue *(Value *)>>> 166 mapToVPValues(User::op_range Operands); 167 getVPValueOrAddLiveIn(Value * V,VPlan & Plan)168 VPValue *getVPValueOrAddLiveIn(Value *V, VPlan &Plan) { 169 if (auto *I = dyn_cast<Instruction>(V)) { 170 if (auto *R = Ingredient2Recipe.lookup(I)) 171 return R->getVPSingleValue(); 172 } 173 return Plan.getOrAddLiveIn(V); 174 } 175 }; 176 } // end namespace llvm 177 178 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H 179