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->getRegion();
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));
88 return false;
90 return true;
91 if (auto *Expr = dyn_cast<VPExpressionRecipe>(VPV))
92 return Expr->isSingleScalar();
93
94 // VPExpandSCEVRecipes must be placed in the entry and are alway uniform.
95 return isa<VPExpandSCEVRecipe>(VPV);
96}
97
98/// Return true if \p V is a header mask in \p Plan.
99bool isHeaderMask(const VPValue *V, const VPlan &Plan);
100
101/// Checks if \p V is uniform across all VF lanes and UF parts. It is considered
102/// as such if it is either loop invariant (defined outside the vector region)
103/// or its operand is known to be uniform across all VFs and UFs (e.g.
104/// VPDerivedIV or VPCanonicalIVPHI).
106
107/// Returns the header block of the first, top-level loop, or null if none
108/// exist.
110
111/// Get the VF scaling factor applied to the recipe's output, if the recipe has
112/// one.
113unsigned getVFScaleFactor(VPRecipeBase *R);
114
115/// Returns the VPValue representing the uncountable exit comparison used by
116/// AnyOf if the recipes it depends on can be traced back to live-ins and
117/// the addresses (in GEP/PtrAdd form) of any (non-masked) load used in
118/// generating the values for the comparison. The recipes are stored in
119/// \p Recipes, and recipes forming an address for a load are also added to
120/// \p GEPs.
121std::optional<VPValue *>
125} // namespace vputils
126
127//===----------------------------------------------------------------------===//
128// Utilities for modifying predecessors and successors of VPlan blocks.
129//===----------------------------------------------------------------------===//
130
131/// Class that provides utilities for VPBlockBases in VPlan.
133public:
134 VPBlockUtils() = delete;
135
136 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
137 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
138 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
139 /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
140 /// have neither successors nor predecessors.
141 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
142 assert(NewBlock->getSuccessors().empty() &&
143 NewBlock->getPredecessors().empty() &&
144 "Can't insert new block with predecessors or successors.");
145 NewBlock->setParent(BlockPtr->getParent());
146 SmallVector<VPBlockBase *> Succs(BlockPtr->successors());
147 for (VPBlockBase *Succ : Succs) {
148 Succ->replacePredecessor(BlockPtr, NewBlock);
149 NewBlock->appendSuccessor(Succ);
150 }
151 BlockPtr->clearSuccessors();
152 connectBlocks(BlockPtr, NewBlock);
153 }
154
155 /// Insert disconnected block \p NewBlock before \p Blockptr. First
156 /// disconnects all predecessors of \p BlockPtr and connects them to \p
157 /// NewBlock. Add \p NewBlock as predecessor of \p BlockPtr and \p BlockPtr as
158 /// successor of \p NewBlock.
159 static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
160 assert(NewBlock->getSuccessors().empty() &&
161 NewBlock->getPredecessors().empty() &&
162 "Can't insert new block with predecessors or successors.");
163 NewBlock->setParent(BlockPtr->getParent());
164 for (VPBlockBase *Pred : to_vector(BlockPtr->predecessors())) {
165 Pred->replaceSuccessor(BlockPtr, NewBlock);
166 NewBlock->appendPredecessor(Pred);
167 }
168 BlockPtr->clearPredecessors();
169 connectBlocks(NewBlock, BlockPtr);
170 }
171
172 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
173 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
174 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
175 /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
176 /// and \p IfTrue and \p IfFalse must have neither successors nor
177 /// predecessors.
178 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
179 VPBlockBase *BlockPtr) {
180 assert(IfTrue->getSuccessors().empty() &&
181 "Can't insert IfTrue with successors.");
182 assert(IfFalse->getSuccessors().empty() &&
183 "Can't insert IfFalse with successors.");
184 BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
185 IfTrue->setPredecessors({BlockPtr});
186 IfFalse->setPredecessors({BlockPtr});
187 IfTrue->setParent(BlockPtr->getParent());
188 IfFalse->setParent(BlockPtr->getParent());
189 }
190
191 /// Connect VPBlockBases \p From and \p To bi-directionally. If \p PredIdx is
192 /// -1, append \p From to the predecessors of \p To, otherwise set \p To's
193 /// predecessor at \p PredIdx to \p From. If \p SuccIdx is -1, append \p To to
194 /// the successors of \p From, otherwise set \p From's successor at \p SuccIdx
195 /// to \p To. Both VPBlockBases must have the same parent, which can be null.
196 /// Both VPBlockBases can be already connected to other VPBlockBases.
197 static void connectBlocks(VPBlockBase *From, VPBlockBase *To,
198 unsigned PredIdx = -1u, unsigned SuccIdx = -1u) {
199 assert((From->getParent() == To->getParent()) &&
200 "Can't connect two block with different parents");
201 assert((SuccIdx != -1u || From->getNumSuccessors() < 2) &&
202 "Blocks can't have more than two successors.");
203 if (SuccIdx == -1u)
204 From->appendSuccessor(To);
205 else
206 From->getSuccessors()[SuccIdx] = To;
207
208 if (PredIdx == -1u)
209 To->appendPredecessor(From);
210 else
211 To->getPredecessors()[PredIdx] = From;
212 }
213
214 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
215 /// from the successors of \p From and \p From from the predecessors of \p To.
216 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
217 assert(To && "Successor to disconnect is null.");
218 From->removeSuccessor(To);
219 To->removePredecessor(From);
220 }
221
222 /// Reassociate all the blocks connected to \p Old so that they now point to
223 /// \p New.
224 static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {
225 for (auto *Pred : to_vector(Old->getPredecessors()))
226 Pred->replaceSuccessor(Old, New);
227 for (auto *Succ : to_vector(Old->getSuccessors()))
228 Succ->replacePredecessor(Old, New);
229 New->setPredecessors(Old->getPredecessors());
230 New->setSuccessors(Old->getSuccessors());
231 Old->clearPredecessors();
232 Old->clearSuccessors();
233 }
234
235 /// Return an iterator range over \p Range which only includes \p BlockTy
236 /// blocks. The accesses are casted to \p BlockTy.
237 template <typename BlockTy, typename T>
238 static auto blocksOnly(const T &Range) {
239 // Create BaseTy with correct const-ness based on BlockTy.
240 using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
241 const VPBlockBase, VPBlockBase>;
242
243 // We need to first create an iterator range over (const) BlocktTy & instead
244 // of (const) BlockTy * for filter_range to work properly.
245 auto Mapped =
246 map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });
248 Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });
249 return map_range(Filter, [](BaseTy &Block) -> BlockTy * {
250 return cast<BlockTy>(&Block);
251 });
252 }
253
254 /// Inserts \p BlockPtr on the edge between \p From and \p To. That is, update
255 /// \p From's successor to \p To to point to \p BlockPtr and \p To's
256 /// predecessor from \p From to \p BlockPtr. \p From and \p To are added to \p
257 /// BlockPtr's predecessors and successors respectively. There must be a
258 /// single edge between \p From and \p To.
259 static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,
260 VPBlockBase *BlockPtr) {
261 unsigned SuccIdx = From->getIndexForSuccessor(To);
262 unsigned PredIx = To->getIndexForPredecessor(From);
263 VPBlockUtils::connectBlocks(From, BlockPtr, -1, SuccIdx);
264 VPBlockUtils::connectBlocks(BlockPtr, To, PredIx, -1);
265 }
266
267 /// Returns true if \p VPB is a loop header, based on regions or \p VPDT in
268 /// their absence.
269 static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
270
271 /// Returns true if \p VPB is a loop latch, using isHeader().
272 static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
273};
274
275} // namespace llvm
276
277#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:3800
A recipe for vectorizing a phi-node as a sequence of mask-based select instructions.
Definition VPlan.h:2406
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition VPlan.h:80
VPRegionBlock * getParent()
Definition VPlan.h:172
iterator_range< VPBlockBase ** > predecessors()
Definition VPlan.h:201
size_t getNumSuccessors() const
Definition VPlan.h:218
iterator_range< VPBlockBase ** > successors()
Definition VPlan.h:200
unsigned getIndexForSuccessor(const VPBlockBase *Succ) const
Returns the index for Succ in the blocks successor list.
Definition VPlan.h:334
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition VPlan.h:290
unsigned getIndexForPredecessor(const VPBlockBase *Pred) const
Returns the index for Pred in the blocks predecessors list.
Definition VPlan.h:327
const VPBlocksTy & getPredecessors() const
Definition VPlan.h:203
void clearSuccessors()
Remove all the successors of this block.
Definition VPlan.h:309
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition VPlan.h:281
void clearPredecessors()
Remove all the predecessor of this block.
Definition VPlan.h:306
void setParent(VPRegionBlock *P)
Definition VPlan.h:183
const VPBlocksTy & getSuccessors() const
Definition VPlan.h:197
static auto blocksOnly(const T &Range)
Return an iterator range over Range which only includes BlockTy blocks.
Definition VPlanUtils.h:238
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition VPlanUtils.h:141
static void insertOnEdge(VPBlockBase *From, VPBlockBase *To, VPBlockBase *BlockPtr)
Inserts BlockPtr on the edge between From and To.
Definition VPlanUtils.h:259
static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT)
Returns true if VPB is a loop latch, using isHeader().
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.
static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBases IfTrue and IfFalse after BlockPtr.
Definition VPlanUtils.h:178
static void connectBlocks(VPBlockBase *From, VPBlockBase *To, unsigned PredIdx=-1u, unsigned SuccIdx=-1u)
Connect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:197
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:216
static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New)
Reassociate all the blocks connected to Old so that they now point to New.
Definition VPlanUtils.h:224
static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected block NewBlock before Blockptr.
Definition VPlanUtils.h:159
A recipe for converting the input value IV value to the corresponding value of an IV with different s...
Definition VPlan.h:3621
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:386
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition VPlan.h:3988
bool isReplicator() const
An indicator whether this region is to generate multiple replicated instances of output IR correspond...
Definition VPlan.h:4056
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:1773
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition VPlan.h:4112
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 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.
bool isHeaderMask(const VPValue *V, const VPlan &Plan)
Return true if V is a header mask in Plan.
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:1725
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
auto map_range(ContainerTy &&C, FuncTy F)
Definition STLExtras.h:364
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:550
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:547
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559
A recipe for widening select instructions.
Definition VPlan.h:1727