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
18namespace llvm {
19
20class LoopVectorizationLegality;
21class LoopVectorizationCostModel;
22class TargetLibraryInfo;
23
24/// Helper class to create VPRecipies from IR instructions.
25class VPRecipeBuilder {
26 /// The VPlan new recipes are added to.
27 VPlan &Plan;
28
29 /// The loop that we evaluate.
30 Loop *OrigLoop;
31
32 /// Target Library Info.
33 const TargetLibraryInfo *TLI;
34
35 /// The legality analysis.
36 LoopVectorizationLegality *Legal;
37
38 /// The profitablity analysis.
39 LoopVectorizationCostModel &CM;
40
41 PredicatedScalarEvolution &PSE;
42
43 VPBuilder &Builder;
44
45 /// When we if-convert we need to create edge masks. We have to cache values
46 /// so that we don't end up with exponential recursion/IR. Note that
47 /// if-conversion currently takes place during VPlan-construction, so these
48 /// caches are only used at that stage.
49 using EdgeMaskCacheTy =
50 DenseMap<std::pair<BasicBlock *, BasicBlock *>, VPValue *>;
51 using BlockMaskCacheTy = DenseMap<BasicBlock *, VPValue *>;
52 EdgeMaskCacheTy EdgeMaskCache;
53 BlockMaskCacheTy BlockMaskCache;
54
55 // VPlan construction support: Hold a mapping from ingredients to
56 // their recipe.
57 DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
58
59 /// Cross-iteration reduction & first-order recurrence phis for which we need
60 /// to add the incoming value from the backedge after all recipes have been
61 /// created.
62 SmallVector<VPHeaderPHIRecipe *, 4> PhisToFix;
63
64 /// Check if \p I can be widened at the start of \p Range and possibly
65 /// decrease the range such that the returned value holds for the entire \p
66 /// Range. The function should not be called for memory instructions or calls.
67 bool shouldWiden(Instruction *I, VFRange &Range) const;
68
69 /// Check if the load or store instruction \p I should widened for \p
70 /// Range.Start and potentially masked. Such instructions are handled by a
71 /// recipe that takes an additional VPInstruction for the mask.
72 VPWidenMemoryRecipe *tryToWidenMemory(Instruction *I,
73 ArrayRef<VPValue *> Operands,
74 VFRange &Range);
75
76 /// Check if an induction recipe should be constructed for \p Phi. If so build
77 /// and return it. If not, return null.
78 VPHeaderPHIRecipe *tryToOptimizeInductionPHI(PHINode *Phi,
79 ArrayRef<VPValue *> Operands,
80 VFRange &Range);
81
82 /// Optimize the special case where the operand of \p I is a constant integer
83 /// induction variable.
84 VPWidenIntOrFpInductionRecipe *
85 tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands,
86 VFRange &Range);
87
88 /// Handle non-loop phi nodes. Return a new VPBlendRecipe otherwise. Currently
89 /// all such phi nodes are turned into a sequence of select instructions as
90 /// the vectorizer currently performs full if-conversion.
91 VPBlendRecipe *tryToBlend(PHINode *Phi, ArrayRef<VPValue *> Operands);
92
93 /// Handle call instructions. If \p CI can be widened for \p Range.Start,
94 /// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same
95 /// decision from \p Range.Start to \p Range.End.
96 VPWidenCallRecipe *tryToWidenCall(CallInst *CI, ArrayRef<VPValue *> Operands,
97 VFRange &Range);
98
99 /// Check if \p I has an opcode that can be widened and return a VPWidenRecipe
100 /// if it can. The function should only be called if the cost-model indicates
101 /// that widening should be performed.
102 VPWidenRecipe *tryToWiden(Instruction *I, ArrayRef<VPValue *> Operands,
103 VPBasicBlock *VPBB);
104
105public:
106 VPRecipeBuilder(VPlan &Plan, Loop *OrigLoop, const TargetLibraryInfo *TLI,
107 LoopVectorizationLegality *Legal,
108 LoopVectorizationCostModel &CM,
109 PredicatedScalarEvolution &PSE, VPBuilder &Builder)
110 : Plan(Plan), OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM),
111 PSE(PSE), Builder(Builder) {}
112
113 /// Create and return a widened recipe for \p I if one can be created within
114 /// the given VF \p Range.
115 VPRecipeBase *tryToCreateWidenRecipe(Instruction *Instr,
116 ArrayRef<VPValue *> Operands,
117 VFRange &Range, VPBasicBlock *VPBB);
118
119 /// Set the recipe created for given ingredient.
120 void setRecipe(Instruction *I, VPRecipeBase *R) {
121 assert(!Ingredient2Recipe.contains(I) &&
122 "Cannot reset recipe for instruction.");
123 Ingredient2Recipe[I] = R;
124 }
125
126 /// Create the mask for the vector loop header block.
127 void createHeaderMask();
128
129 /// A helper function that computes the predicate of the block BB, assuming
130 /// that the header block of the loop is set to True or the loop mask when
131 /// tail folding.
132 void createBlockInMask(BasicBlock *BB);
133
134 /// Returns the *entry* mask for the block \p BB.
135 VPValue *getBlockInMask(BasicBlock *BB) const;
136
137 /// A helper function that computes the predicate of the edge between SRC
138 /// and DST.
139 VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst);
140
141 /// A helper that returns the previously computed predicate of the edge
142 /// between SRC and DST.
143 VPValue *getEdgeMask(BasicBlock *Src, BasicBlock *Dst) const;
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 /// Build a VPReplicationRecipe for \p I. If it is predicated, add the mask as
155 /// last operand. Range.End may be decreased to ensure same recipe behavior
156 /// from \p Range.Start to \p Range.End.
157 VPReplicateRecipe *handleReplication(Instruction *I, VFRange &Range);
158
159 /// Add the incoming values from the backedge to reduction & first-order
160 /// recurrence cross-iteration phis.
161 void fixHeaderPhis();
162
163 /// Returns a range mapping the values of the range \p Operands to their
164 /// corresponding VPValues.
165 iterator_range<mapped_iterator<Use *, std::function<VPValue *(Value *)>>>
166 mapToVPValues(User::op_range Operands);
167
168 VPValue *getVPValueOrAddLiveIn(Value *V, VPlan &Plan) {
169 if (auto *I = dyn_cast<Instruction>(Val: V)) {
170 if (auto *R = Ingredient2Recipe.lookup(Val: I))
171 return R->getVPSingleValue();
172 }
173 return Plan.getOrAddLiveIn(V);
174 }
175};
176} // end namespace llvm
177
178#endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
179