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