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