LLVM 22.0.0git
VPlanUtils.h
Go to the documentation of this file.
1//===- VPlanUtils.h - VPlan-related utilities -------------------*- 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_VPLANUTILS_H
10#define LLVM_TRANSFORMS_VECTORIZE_VPLANUTILS_H
11
12#include "VPlan.h"
13
14namespace llvm {
15class ScalarEvolution;
16class SCEV;
17} // namespace llvm
18
19namespace llvm {
20
21namespace vputils {
22/// Returns true if only the first lane of \p Def is used.
23bool onlyFirstLaneUsed(const VPValue *Def);
24
25/// Returns true if only the first part of \p Def is used.
26bool onlyFirstPartUsed(const VPValue *Def);
27
28/// Returns true if only scalar values of \p Def are used by all users.
29bool onlyScalarValuesUsed(const VPValue *Def);
30
31/// Get or create a VPValue that corresponds to the expansion of \p Expr. If \p
32/// Expr is a SCEVConstant or SCEVUnknown, return a VPValue wrapping the live-in
33/// value. Otherwise return a VPExpandSCEVRecipe to expand \p Expr. If \p Plan's
34/// pre-header already contains a recipe expanding \p Expr, return it. If not,
35/// create a new one.
37
38/// Return the SCEV expression for \p V. Returns SCEVCouldNotCompute if no
39/// SCEV expression could be constructed.
41
42/// Returns true if \p VPV is a single scalar, either because it produces the
43/// same value for all lanes or only has its first lane used.
44inline bool isSingleScalar(const VPValue *VPV) {
45 auto PreservesUniformity = [](unsigned Opcode) -> bool {
46 if (Instruction::isBinaryOp(Opcode) || Instruction::isCast(Opcode))
47 return true;
48 switch (Opcode) {
49 case Instruction::GetElementPtr:
50 case Instruction::ICmp:
51 case Instruction::FCmp:
52 case Instruction::Select:
56 return true;
57 default:
58 return false;
59 }
60 };
61
62 // A live-in must be uniform across the scope of VPlan.
63 if (VPV->isLiveIn())
64 return true;
65
66 if (auto *Rep = dyn_cast<VPReplicateRecipe>(VPV)) {
67 const VPRegionBlock *RegionOfR = Rep->getParent()->getParent();
68 // Don't consider recipes in replicate regions as uniform yet; their first
69 // lane cannot be accessed when executing the replicate region for other
70 // lanes.
71 if (RegionOfR && RegionOfR->isReplicator())
72 return false;
73 return Rep->isSingleScalar() || (PreservesUniformity(Rep->getOpcode()) &&
74 all_of(Rep->operands(), isSingleScalar));
75 }
79 if (auto *WidenR = dyn_cast<VPWidenRecipe>(VPV)) {
80 return PreservesUniformity(WidenR->getOpcode()) &&
81 all_of(WidenR->operands(), isSingleScalar);
82 }
83 if (auto *VPI = dyn_cast<VPInstruction>(VPV))
84 return VPI->isSingleScalar() || VPI->isVectorToScalar() ||
85 (PreservesUniformity(VPI->getOpcode()) &&
86 all_of(VPI->operands(), isSingleScalar));
87
88 // VPExpandSCEVRecipes must be placed in the entry and are alway uniform.
89 return isa<VPExpandSCEVRecipe>(VPV);
90}
91
92/// Return true if \p V is a header mask in \p Plan.
93bool isHeaderMask(const VPValue *V, VPlan &Plan);
94
95/// Checks if \p V is uniform across all VF lanes and UF parts. It is considered
96/// as such if it is either loop invariant (defined outside the vector region)
97/// or its operand is known to be uniform across all VFs and UFs (e.g.
98/// VPDerivedIV or VPCanonicalIVPHI).
100
101/// Returns the header block of the first, top-level loop, or null if none
102/// exist.
104
105/// Get the VF scaling factor applied to the recipe's output, if the recipe has
106/// one.
107unsigned getVFScaleFactor(VPRecipeBase *R);
108
109/// Returns the VPValue representing the uncountable exit comparison used by
110/// AnyOf if the recipes it depends on can be traced back to live-ins and
111/// the addresses (in GEP/PtrAdd form) of any (non-masked) load used in
112/// generating the values for the comparison. The recipes are stored in
113/// \p Recipes, and recipes forming an address for a load are also added to
114/// \p GEPs.
115std::optional<VPValue *>
119} // namespace vputils
120
121//===----------------------------------------------------------------------===//
122// Utilities for modifying predecessors and successors of VPlan blocks.
123//===----------------------------------------------------------------------===//
124
125/// Class that provides utilities for VPBlockBases in VPlan.
127public:
128 VPBlockUtils() = delete;
129
130 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
131 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
132 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
133 /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
134 /// have neither successors nor predecessors.
135 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
136 assert(NewBlock->getSuccessors().empty() &&
137 NewBlock->getPredecessors().empty() &&
138 "Can't insert new block with predecessors or successors.");
139 NewBlock->setParent(BlockPtr->getParent());
140 SmallVector<VPBlockBase *> Succs(BlockPtr->successors());
141 for (VPBlockBase *Succ : Succs) {
142 Succ->replacePredecessor(BlockPtr, NewBlock);
143 NewBlock->appendSuccessor(Succ);
144 }
145 BlockPtr->clearSuccessors();
146 connectBlocks(BlockPtr, NewBlock);
147 }
148
149 /// Insert disconnected block \p NewBlock before \p Blockptr. First
150 /// disconnects all predecessors of \p BlockPtr and connects them to \p
151 /// NewBlock. Add \p NewBlock as predecessor of \p BlockPtr and \p BlockPtr as
152 /// successor of \p NewBlock.
153 static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
154 assert(NewBlock->getSuccessors().empty() &&
155 NewBlock->getPredecessors().empty() &&
156 "Can't insert new block with predecessors or successors.");
157 NewBlock->setParent(BlockPtr->getParent());
158 for (VPBlockBase *Pred : to_vector(BlockPtr->predecessors())) {
159 Pred->replaceSuccessor(BlockPtr, NewBlock);
160 NewBlock->appendPredecessor(Pred);
161 }
162 BlockPtr->clearPredecessors();
163 connectBlocks(NewBlock, BlockPtr);
164 }
165
166 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
167 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
168 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
169 /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
170 /// and \p IfTrue and \p IfFalse must have neither successors nor
171 /// predecessors.
172 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
173 VPBlockBase *BlockPtr) {
174 assert(IfTrue->getSuccessors().empty() &&
175 "Can't insert IfTrue with successors.");
176 assert(IfFalse->getSuccessors().empty() &&
177 "Can't insert IfFalse with successors.");
178 BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
179 IfTrue->setPredecessors({BlockPtr});
180 IfFalse->setPredecessors({BlockPtr});
181 IfTrue->setParent(BlockPtr->getParent());
182 IfFalse->setParent(BlockPtr->getParent());
183 }
184
185 /// Connect VPBlockBases \p From and \p To bi-directionally. If \p PredIdx is
186 /// -1, append \p From to the predecessors of \p To, otherwise set \p To's
187 /// predecessor at \p PredIdx to \p From. If \p SuccIdx is -1, append \p To to
188 /// the successors of \p From, otherwise set \p From's successor at \p SuccIdx
189 /// to \p To. Both VPBlockBases must have the same parent, which can be null.
190 /// Both VPBlockBases can be already connected to other VPBlockBases.
191 static void connectBlocks(VPBlockBase *From, VPBlockBase *To,
192 unsigned PredIdx = -1u, unsigned SuccIdx = -1u) {
193 assert((From->getParent() == To->getParent()) &&
194 "Can't connect two block with different parents");
195 assert((SuccIdx != -1u || From->getNumSuccessors() < 2) &&
196 "Blocks can't have more than two successors.");
197 if (SuccIdx == -1u)
198 From->appendSuccessor(To);
199 else
200 From->getSuccessors()[SuccIdx] = To;
201
202 if (PredIdx == -1u)
203 To->appendPredecessor(From);
204 else
205 To->getPredecessors()[PredIdx] = From;
206 }
207
208 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
209 /// from the successors of \p From and \p From from the predecessors of \p To.
210 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
211 assert(To && "Successor to disconnect is null.");
212 From->removeSuccessor(To);
213 To->removePredecessor(From);
214 }
215
216 /// Reassociate all the blocks connected to \p Old so that they now point to
217 /// \p New.
218 static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {
219 for (auto *Pred : to_vector(Old->getPredecessors()))
220 Pred->replaceSuccessor(Old, New);
221 for (auto *Succ : to_vector(Old->getSuccessors()))
222 Succ->replacePredecessor(Old, New);
223 New->setPredecessors(Old->getPredecessors());
224 New->setSuccessors(Old->getSuccessors());
225 Old->clearPredecessors();
226 Old->clearSuccessors();
227 }
228
229 /// Return an iterator range over \p Range which only includes \p BlockTy
230 /// blocks. The accesses are casted to \p BlockTy.
231 template <typename BlockTy, typename T>
232 static auto blocksOnly(const T &Range) {
233 // Create BaseTy with correct const-ness based on BlockTy.
234 using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
235 const VPBlockBase, VPBlockBase>;
236
237 // We need to first create an iterator range over (const) BlocktTy & instead
238 // of (const) BlockTy * for filter_range to work properly.
239 auto Mapped =
240 map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });
242 Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });
243 return map_range(Filter, [](BaseTy &Block) -> BlockTy * {
244 return cast<BlockTy>(&Block);
245 });
246 }
247
248 /// Inserts \p BlockPtr on the edge between \p From and \p To. That is, update
249 /// \p From's successor to \p To to point to \p BlockPtr and \p To's
250 /// predecessor from \p From to \p BlockPtr. \p From and \p To are added to \p
251 /// BlockPtr's predecessors and successors respectively. There must be a
252 /// single edge between \p From and \p To.
253 static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,
254 VPBlockBase *BlockPtr) {
255 unsigned SuccIdx = From->getIndexForSuccessor(To);
256 unsigned PredIx = To->getIndexForPredecessor(From);
257 VPBlockUtils::connectBlocks(From, BlockPtr, -1, SuccIdx);
258 VPBlockUtils::connectBlocks(BlockPtr, To, PredIx, -1);
259 }
260
261 /// Returns true if \p VPB is a loop header, based on regions or \p VPDT in
262 /// their absence.
263 static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
264
265 /// Returns true if \p VPB is a loop latch, using isHeader().
266 static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
267};
268
269} // namespace llvm
270
271#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
std::pair< BasicBlock *, unsigned > BlockTy
A pair of (basic block, score).
#define T
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
This file contains the declarations of the Vectorization Plan base classes:
bool isCast() const
bool isBinaryOp() const
This class represents an analyzed expression in the program.
The main scalar evolution driver.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition VPlan.h:3764
A recipe for vectorizing a phi-node as a sequence of mask-based select instructions.
Definition VPlan.h:2403
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition VPlan.h:81
VPRegionBlock * getParent()
Definition VPlan.h:173
iterator_range< VPBlockBase ** > predecessors()
Definition VPlan.h:202
size_t getNumSuccessors() const
Definition VPlan.h:219
iterator_range< VPBlockBase ** > successors()
Definition VPlan.h:201
unsigned getIndexForSuccessor(const VPBlockBase *Succ) const
Returns the index for Succ in the blocks successor list.
Definition VPlan.h:335
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition VPlan.h:291
unsigned getIndexForPredecessor(const VPBlockBase *Pred) const
Returns the index for Pred in the blocks predecessors list.
Definition VPlan.h:328
const VPBlocksTy & getPredecessors() const
Definition VPlan.h:204
void clearSuccessors()
Remove all the successors of this block.
Definition VPlan.h:310
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition VPlan.h:282
void clearPredecessors()
Remove all the predecessor of this block.
Definition VPlan.h:307
void setParent(VPRegionBlock *P)
Definition VPlan.h:184
const VPBlocksTy & getSuccessors() const
Definition VPlan.h:198
static auto blocksOnly(const T &Range)
Return an iterator range over Range which only includes BlockTy blocks.
Definition VPlanUtils.h:232
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition VPlanUtils.h:135
static void insertOnEdge(VPBlockBase *From, VPBlockBase *To, VPBlockBase *BlockPtr)
Inserts BlockPtr on the edge between From and To.
Definition VPlanUtils.h:253
static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT)
Returns true if VPB is a loop latch, using isHeader().
Definition VPlan.cpp:237
static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT)
Returns true if VPB is a loop header, based on regions or VPDT in their absence.
Definition VPlan.cpp:220
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition VPlanUtils.h:172
static void connectBlocks(VPBlockBase *From, VPBlockBase *To, unsigned PredIdx=-1u, unsigned SuccIdx=-1u)
Connect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:191
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:210
static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New)
Reassociate all the blocks connected to Old so that they now point to New.
Definition VPlanUtils.h:218
static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected block NewBlock before Blockptr.
Definition VPlanUtils.h:153
A recipe for converting the input value IV value to the corresponding value of an IV with different s...
Definition VPlan.h:3585
Template specialization of the standard LLVM dominator tree utility for VPBlockBases.
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition VPlan.h:394
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition VPlan.h:3952
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition VPlan.h:4020
operand_range operands()
Definition VPlanValue.h:267
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition VPlan.cpp:135
bool isLiveIn() const
Returns true if this VPValue is a live-in, i.e. defined outside the VPlan.
Definition VPlanValue.h:171
A recipe for handling GEP instructions.
Definition VPlan.h:1769
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition VPlan.h:4055
bool isSingleScalar(const VPValue *VPV)
Returns true if VPV is a single scalar, either because it produces the same value for all lanes or on...
Definition VPlanUtils.h:44
bool isUniformAcrossVFsAndUFs(VPValue *V)
Checks if V is uniform across all VF lanes and UF parts.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr)
Get or create a VPValue that corresponds to the expansion of Expr.
VPBasicBlock * getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT)
Returns the header block of the first, top-level loop, or null if none exist.
bool onlyFirstPartUsed(const VPValue *Def)
Returns true if only the first part of Def is used.
const SCEV * getSCEVExprForVPValue(VPValue *V, ScalarEvolution &SE)
Return the SCEV expression for V.
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used.
bool isHeaderMask(const VPValue *V, VPlan &Plan)
Return true if V is a header mask in Plan.
bool onlyScalarValuesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users.
unsigned getVFScaleFactor(VPRecipeBase *R)
Get the VF scaling factor applied to the recipe's output, if the recipe has one.
std::optional< VPValue * > getRecipesForUncountableExit(VPlan &Plan, SmallVectorImpl< VPRecipeBase * > &Recipes, SmallVectorImpl< VPRecipeBase * > &GEPs)
Returns the VPValue representing the uncountable exit comparison used by AnyOf if the recipes it depe...
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1705
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:649
auto map_range(ContainerTy &&C, FuncTy F)
Definition STLExtras.h:366
SmallVector< ValueTypeFromRangeType< R >, Size > to_vector(R &&Range)
Given a range of type R, iterate the entire range and return a SmallVector with elements of the vecto...
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition STLExtras.h:552
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
Definition Casting.h:548
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:565
A recipe for widening select instructions.
Definition VPlan.h:1723