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