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