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.
53   DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
54 
55   /// Set the recipe created for given ingredient. This operation is a no-op for
56   /// ingredients that were not marked using a nullptr entry in the map.
57   void setRecipe(Instruction *I, VPRecipeBase *R) {
58     if (!Ingredient2Recipe.count(I))
59       return;
60     assert(Ingredient2Recipe[I] == nullptr &&
61            "Recipe already set for ingredient");
62     Ingredient2Recipe[I] = R;
63   }
64 
65 public:
66   /// A helper function that computes the predicate of the block BB, assuming
67   /// that the header block of the loop is set to True. It returns the *entry*
68   /// mask for the block BB.
69   VPValue *createBlockInMask(BasicBlock *BB, VPlanPtr &Plan);
70 
71   /// A helper function that computes the predicate of the edge between SRC
72   /// and DST.
73   VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlanPtr &Plan);
74 
75   /// Mark given ingredient for recording its recipe once one is created for
76   /// it.
77   void recordRecipeOf(Instruction *I) {
78     assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
79            "Recipe already set for ingredient");
80     Ingredient2Recipe[I] = nullptr;
81   }
82 
83   /// Return the recipe created for given ingredient.
84   VPRecipeBase *getRecipe(Instruction *I) {
85     assert(Ingredient2Recipe.count(I) &&
86            "Recording this ingredients recipe was not requested");
87     assert(Ingredient2Recipe[I] != nullptr &&
88            "Ingredient doesn't have a recipe");
89     return Ingredient2Recipe[I];
90   }
91 
92   /// Check if \I is a memory instruction to be widened for \p Range.Start and
93   /// potentially masked. Such instructions are handled by a recipe that takes
94   /// an additional VPInstruction for the mask.
95   VPWidenMemoryInstructionRecipe *
96   tryToWidenMemory(Instruction *I, VFRange &Range, VPlanPtr &Plan);
97 
98   /// Check if an induction recipe should be constructed for \I within the given
99   /// VF \p Range. If so build and return it. If not, return null. \p Range.End
100   /// may be decreased to ensure same decision from \p Range.Start to
101   /// \p Range.End.
102   VPWidenIntOrFpInductionRecipe *tryToOptimizeInduction(Instruction *I,
103                                                         VFRange &Range);
104 
105   /// Handle non-loop phi nodes. Currently all such phi nodes are turned into
106   /// a sequence of select instructions as the vectorizer currently performs
107   /// full if-conversion.
108   VPBlendRecipe *tryToBlend(Instruction *I, VPlanPtr &Plan);
109 
110   /// Handle call instruction. If \p I is a call that can be widened for \p
111   /// Range.Start, return a new VPWidenCallRecipe. Range.End may be decreased to
112   /// ensure same decision from \p Range.Start to \p Range.End.
113   VPWidenCallRecipe *tryToWidenCall(Instruction *I, VFRange &Range);
114 
115   /// Check if \p I can be widened within the given VF \p Range. If \p I can be
116   /// widened for \p Range.Start, build a new VPWidenRecipe and return it.
117   /// Range.End may be decreased to ensure same decision from \p Range.Start to
118   /// \p Range.End.
119   VPWidenRecipe *tryToWiden(Instruction *I, 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