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