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, ArrayRef<VPValue *> Operands,
68                                  VFRange &Range, 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 *
73   tryToOptimizeInductionPHI(PHINode *Phi, ArrayRef<VPValue *> Operands) 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, ArrayRef<VPValue *> Operands,
79                                  VFRange &Range, 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, ArrayRef<VPValue *> Operands,
86                                  VPlanPtr &Plan);
87 
88   /// Handle call instructions. If \p CI can be widened for \p Range.Start,
89   /// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same
90   /// decision from \p Range.Start to \p Range.End.
91   VPWidenCallRecipe *tryToWidenCall(CallInst *CI, ArrayRef<VPValue *> Operands,
92                                     VFRange &Range) const;
93 
94   /// Check if \p I has an opcode that can be widened and return a VPWidenRecipe
95   /// if it can. The function should only be called if the cost-model indicates
96   /// that widening should be performed.
97   VPWidenRecipe *tryToWiden(Instruction *I, ArrayRef<VPValue *> Operands) const;
98 
99   /// 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.
100   VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; }
101 
102 public:
103   VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI,
104                   LoopVectorizationLegality *Legal,
105                   LoopVectorizationCostModel &CM,
106                   PredicatedScalarEvolution &PSE, VPBuilder &Builder)
107       : OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), PSE(PSE),
108         Builder(Builder) {}
109 
110   /// Check if an existing VPValue can be used for \p Instr or a recipe can be
111   /// create for \p I withing the given VF \p Range. If an existing VPValue can
112   /// be used or if a recipe can be created, return it. Otherwise return a
113   /// VPRecipeOrVPValueTy with nullptr.
114   VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr,
115                                              ArrayRef<VPValue *> Operands,
116                                              VFRange &Range, VPlanPtr &Plan);
117 
118   /// Set the recipe created for given ingredient. This operation is a no-op for
119   /// ingredients that were not marked using a nullptr entry in the map.
120   void setRecipe(Instruction *I, VPRecipeBase *R) {
121     if (!Ingredient2Recipe.count(I))
122       return;
123     assert(Ingredient2Recipe[I] == nullptr &&
124            "Recipe already set for ingredient");
125     Ingredient2Recipe[I] = R;
126   }
127 
128   /// A helper function that computes the predicate of the block BB, assuming
129   /// that the header block of the loop is set to True. It returns the *entry*
130   /// mask for the block BB.
131   VPValue *createBlockInMask(BasicBlock *BB, VPlanPtr &Plan);
132 
133   /// A helper function that computes the predicate of the edge between SRC
134   /// and DST.
135   VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlanPtr &Plan);
136 
137   /// Mark given ingredient for recording its recipe once one is created for
138   /// it.
139   void recordRecipeOf(Instruction *I) {
140     assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
141            "Recipe already set for ingredient");
142     Ingredient2Recipe[I] = nullptr;
143   }
144 
145   /// Return the recipe created for given ingredient.
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   /// Create a replicating region for instruction \p I that requires
155   /// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
156   VPRegionBlock *createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe,
157                                        VPlanPtr &Plan);
158 
159   /// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
160   /// is predicated. \return \p VPBB augmented with this new recipe if \p I is
161   /// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
162   /// Region. Update the packing decision of predicated instructions if they
163   /// feed \p I. Range.End may be decreased to ensure same recipe behavior from
164   /// \p Range.Start to \p Range.End.
165   VPBasicBlock *handleReplication(
166       Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
167       VPlanPtr &Plan);
168 };
169 } // end namespace llvm
170 
171 #endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
172