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