1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
//===- VPRecipeBuilder.h - Helper class to build recipes --------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
#define LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
#include "LoopVectorizationPlanner.h"
#include "VPlan.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/IR/IRBuilder.h"
namespace llvm {
class LoopVectorizationLegality;
class LoopVectorizationCostModel;
class TargetLibraryInfo;
using VPRecipeOrVPValueTy = PointerUnion<VPRecipeBase *, VPValue *>;
/// Helper class to create VPRecipies from IR instructions.
class VPRecipeBuilder {
/// The loop that we evaluate.
Loop *OrigLoop;
/// Target Library Info.
const TargetLibraryInfo *TLI;
/// The legality analysis.
LoopVectorizationLegality *Legal;
/// The profitablity analysis.
LoopVectorizationCostModel &CM;
PredicatedScalarEvolution &PSE;
VPBuilder &Builder;
/// When we if-convert we need to create edge masks. We have to cache values
/// so that we don't end up with exponential recursion/IR. Note that
/// if-conversion currently takes place during VPlan-construction, so these
/// caches are only used at that stage.
using EdgeMaskCacheTy =
DenseMap<std::pair<BasicBlock *, BasicBlock *>, VPValue *>;
using BlockMaskCacheTy = DenseMap<BasicBlock *, VPValue *>;
EdgeMaskCacheTy EdgeMaskCache;
BlockMaskCacheTy BlockMaskCache;
// VPlan-VPlan transformations support: Hold a mapping from ingredients to
// their recipe. To save on memory, only do so for selected ingredients,
// marked by having a nullptr entry in this map.
DenseMap<Instruction *, VPRecipeBase *> Ingredient2Recipe;
/// Cross-iteration reduction & first-order recurrence phis for which we need
/// to add the incoming value from the backedge after all recipes have been
/// created.
SmallVector<VPHeaderPHIRecipe *, 4> PhisToFix;
/// Check if \p I can be widened at the start of \p Range and possibly
/// decrease the range such that the returned value holds for the entire \p
/// Range. The function should not be called for memory instructions or calls.
bool shouldWiden(Instruction *I, VFRange &Range) const;
/// Check if the load or store instruction \p I should widened for \p
/// Range.Start and potentially masked. Such instructions are handled by a
/// recipe that takes an additional VPInstruction for the mask.
VPRecipeBase *tryToWidenMemory(Instruction *I, ArrayRef<VPValue *> Operands,
VFRange &Range, VPlanPtr &Plan);
/// Check if an induction recipe should be constructed for \I. If so build and
/// return it. If not, return null.
VPWidenIntOrFpInductionRecipe *
tryToOptimizeInductionPHI(PHINode *Phi, ArrayRef<VPValue *> Operands,
VFRange &Range) const;
/// Optimize the special case where the operand of \p I is a constant integer
/// induction variable.
VPWidenIntOrFpInductionRecipe *
tryToOptimizeInductionTruncate(TruncInst *I, ArrayRef<VPValue *> Operands,
VFRange &Range, VPlan &Plan) const;
/// Handle non-loop phi nodes. Return a VPValue, if all incoming values match
/// or a new VPBlendRecipe otherwise. Currently all such phi nodes are turned
/// into a sequence of select instructions as the vectorizer currently
/// performs full if-conversion.
VPRecipeOrVPValueTy tryToBlend(PHINode *Phi, ArrayRef<VPValue *> Operands,
VPlanPtr &Plan);
/// Handle call instructions. If \p CI can be widened for \p Range.Start,
/// return a new VPWidenCallRecipe. Range.End may be decreased to ensure same
/// decision from \p Range.Start to \p Range.End.
VPWidenCallRecipe *tryToWidenCall(CallInst *CI, ArrayRef<VPValue *> Operands,
VFRange &Range) const;
/// Check if \p I has an opcode that can be widened and return a VPWidenRecipe
/// if it can. The function should only be called if the cost-model indicates
/// that widening should be performed.
VPWidenRecipe *tryToWiden(Instruction *I, ArrayRef<VPValue *> Operands) const;
/// Return a VPRecipeOrValueTy with VPRecipeBase * being set. This can be used to force the use as VPRecipeBase* for recipe sub-types that also inherit from VPValue.
VPRecipeOrVPValueTy toVPRecipeResult(VPRecipeBase *R) const { return R; }
public:
VPRecipeBuilder(Loop *OrigLoop, const TargetLibraryInfo *TLI,
LoopVectorizationLegality *Legal,
LoopVectorizationCostModel &CM,
PredicatedScalarEvolution &PSE, VPBuilder &Builder)
: OrigLoop(OrigLoop), TLI(TLI), Legal(Legal), CM(CM), PSE(PSE),
Builder(Builder) {}
/// Check if an existing VPValue can be used for \p Instr or a recipe can be
/// create for \p I withing the given VF \p Range. If an existing VPValue can
/// be used or if a recipe can be created, return it. Otherwise return a
/// VPRecipeOrVPValueTy with nullptr.
VPRecipeOrVPValueTy tryToCreateWidenRecipe(Instruction *Instr,
ArrayRef<VPValue *> Operands,
VFRange &Range, VPlanPtr &Plan);
/// Set the recipe created for given ingredient. This operation is a no-op for
/// ingredients that were not marked using a nullptr entry in the map.
void setRecipe(Instruction *I, VPRecipeBase *R) {
if (!Ingredient2Recipe.count(I))
return;
assert(Ingredient2Recipe[I] == nullptr &&
"Recipe already set for ingredient");
Ingredient2Recipe[I] = R;
}
/// A helper function that computes the predicate of the block BB, assuming
/// that the header block of the loop is set to True. It returns the *entry*
/// mask for the block BB.
VPValue *createBlockInMask(BasicBlock *BB, VPlanPtr &Plan);
/// A helper function that computes the predicate of the edge between SRC
/// and DST.
VPValue *createEdgeMask(BasicBlock *Src, BasicBlock *Dst, VPlanPtr &Plan);
/// Mark given ingredient for recording its recipe once one is created for
/// it.
void recordRecipeOf(Instruction *I) {
assert((!Ingredient2Recipe.count(I) || Ingredient2Recipe[I] == nullptr) &&
"Recipe already set for ingredient");
Ingredient2Recipe[I] = nullptr;
}
/// Return the recipe created for given ingredient.
VPRecipeBase *getRecipe(Instruction *I) {
assert(Ingredient2Recipe.count(I) &&
"Recording this ingredients recipe was not requested");
assert(Ingredient2Recipe[I] != nullptr &&
"Ingredient doesn't have a recipe");
return Ingredient2Recipe[I];
}
/// Create a replicating region for instruction \p I that requires
/// predication. \p PredRecipe is a VPReplicateRecipe holding \p I.
VPRegionBlock *createReplicateRegion(Instruction *I, VPRecipeBase *PredRecipe,
VPlanPtr &Plan);
/// Build a VPReplicationRecipe for \p I and enclose it within a Region if it
/// is predicated. \return \p VPBB augmented with this new recipe if \p I is
/// not predicated, otherwise \return a new VPBasicBlock that succeeds the new
/// Region. Update the packing decision of predicated instructions if they
/// feed \p I. Range.End may be decreased to ensure same recipe behavior from
/// \p Range.Start to \p Range.End.
VPBasicBlock *handleReplication(
Instruction *I, VFRange &Range, VPBasicBlock *VPBB,
VPlanPtr &Plan);
/// Add the incoming values from the backedge to reduction & first-order
/// recurrence cross-iteration phis.
void fixHeaderPhis();
};
} // end namespace llvm
#endif // LLVM_TRANSFORMS_VECTORIZE_VPRECIPEBUILDER_H
|
