LLVM 24.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"
16
17namespace llvm {
18class MemoryLocation;
19class ScalarEvolution;
20class SCEV;
21class SCEVNAryExpr;
23} // namespace llvm
24
25namespace llvm {
26
27namespace vputils {
28/// Returns true if checking whether \p U uses the first lane of \p Op requires
29/// recursively checking \p Op's users.
30bool propagatesFirstLaneUse(const VPUser *U, const VPValue *Op);
31
32/// Returns true if only the first lane of \p Def is used by all users.
33bool onlyFirstLaneUsed(const VPValue *Def);
34
35/// Returns true if only the first part of \p Def is used by all users.
36bool onlyFirstPartUsed(const VPValue *Def);
37
38/// Returns true if only scalar values of \p Def are used by all users.
39bool onlyScalarValuesUsed(const VPValue *Def);
40
41/// Returns true if only scalar values of \p Def are used by all users, either
42/// directly or by extracting a constant lane.
44
45/// Get or create a VPValue that corresponds to the expansion of \p Expr. If \p
46/// Expr is a SCEVConstant or SCEVUnknown, return a VPValue wrapping the live-in
47/// value. Otherwise return a VPExpandSCEVRecipe to expand \p Expr. If \p Plan's
48/// pre-header already contains a recipe expanding \p Expr, return it. If not,
49/// create a new one. \p ExpandInIR is forwarded to the VPExpandSCEVRecipe.
51 bool ExpandInIR = false);
52
53/// Return the SCEV expression for \p V. Returns SCEVCouldNotCompute if no
54/// SCEV expression could be constructed.
57 const Loop *L = nullptr);
58
59/// If the pointer operand \p Addr of a memory access is an affine AddRec
60/// w.r.t. \p L with a constant stride, return the stride in units of
61/// \p AccessTy. Otherwise return std::nullopt.
62std::optional<int64_t> getConstantStride(VPValue *Addr, Type *AccessTy,
64 const Loop *L);
65
66/// Returns true if \p Addr is an address SCEV that can be passed to
67/// TTI::getAddressComputationCost, i.e. the address SCEV is loop invariant, an
68/// affine AddRec (i.e. induction ), or an add expression of such operands or a
69/// sign-extended AddRec.
70bool isAddressSCEVForCost(const SCEV *Addr, ScalarEvolution &SE, const Loop *L);
71
72/// Returns true if \p VPV is a single scalar, either because it produces the
73/// same value for all lanes or only has its first lane used.
74bool isSingleScalar(const VPValue *VPV);
75
76/// Checks if \p V is uniform across all VF lanes and UF parts. It is considered
77/// as such if it is either loop invariant (defined outside the vector region)
78/// or its operands are known to be uniform across all VFs and UFs (e.g.
79/// VPDerivedIV or the canonical IV).
81
82/// Return true if \p V is elementwise, i.e. none of the lanes are permuted.
83bool isElementwise(const VPValue *V);
84
85/// Returns true if \p R produces scalar values for all VF lanes.
87
88/// Returns the header block of the first, top-level loop, or null if none
89/// exist.
91
92/// Get the VF scaling factor applied to the recipe's output, if the recipe has
93/// one.
95
96/// Return true if we do not know how to (mechanically) hoist or sink \p R.
97/// When sinking, passing \p Sinking = true ensures that assumes aren't sunk.
98/// Returns true for recipes that access memory.
99bool cannotHoistOrSinkRecipe(const VPRecipeBase &R, bool Sinking = false);
100
101/// Return the intrinsic ID underlying a call.
102template <typename Ty> Intrinsic::ID getIntrinsicID(const Ty *R) {
103 if (const auto *Intr = dyn_cast<VPWidenIntrinsicRecipe>(R))
104 return Intr->getVectorIntrinsicID();
105 if (const auto *Call = dyn_cast<VPWidenCallRecipe>(R))
106 return Call->getCalledScalarFunction()->getIntrinsicID();
107
108 auto GetCalleeIntrinsic = [&](VPValue *CalleeOp) -> Intrinsic::ID {
109 if (!isa<VPIRValue>(CalleeOp))
111 auto *F = cast<Function>(CalleeOp->getLiveInIRValue());
112 return F->getIntrinsicID();
113 };
114 if (const auto *Rep = dyn_cast<VPReplicateRecipe>(R))
115 if (Rep->getOpcode() == Instruction::Call)
116 // The callee is the last operand, excluding the mask if predicated.
117 return GetCalleeIntrinsic(
118 Rep->getOperand(Rep->getNumOperandsWithoutMask() - 1));
119 if (const auto *VPI = dyn_cast<VPInstruction>(R)) {
120 if (VPI->getOpcode() == Instruction::Call)
121 // The callee is the last operand, excluding the mask if masked.
122 return GetCalleeIntrinsic(
123 VPI->getOperand(VPI->getNumOperandsWithoutMask() - 1));
124 if (VPI->getOpcode() == VPInstruction::Intrinsic) {
125 return cast<VPConstantInt>(VPI->getLastOperand())->getZExtValue();
126 }
127 }
129}
130
131/// Return the instruction opcode for the recipe defining \p V or 0 for
132/// unsupported recipes and VPValues not defined by a recipe.
133unsigned getOpcode(const VPValue *V);
134
135/// Get the instruction opcode or intrinsic ID for the recipe defining \p V.
136/// Returns an optional pair, where the first element indicates whether it is an
137/// intrinsic ID.
138std::optional<std::pair<bool, unsigned>>
140
141/// Return a MemoryLocation for \p R with noalias metadata populated from
142/// \p R, if the recipe is supported and std::nullopt otherwise. The pointer of
143/// the location is conservatively set to nullptr.
144std::optional<MemoryLocation> getMemoryLocation(const VPRecipeBase &R);
145
146/// Extracts and returns NoWrap flags from \p PhiR and fast-math flags from \p
147/// ID.
149 const VPPhi *PhiR);
150
151/// Search \p Start's users for a recipe satisfying \p Pred, looking through
152/// recipes with definitions.
153template <typename PredT>
154inline VPRecipeBase *findRecipe(VPValue *Start, PredT Pred) {
155 SetVector<VPValue *> Worklist;
156 Worklist.insert(Start);
157 for (unsigned I = 0; I != Worklist.size(); ++I) {
158 VPValue *Cur = Worklist[I];
159 auto *R = Cur->getDefiningRecipe();
160 if (!R)
161 continue;
162 if (Pred(R))
163 return R;
164 for (VPUser *U : Cur->users()) {
165 for (VPValue *V : cast<VPRecipeBase>(U)->definedValues())
166 Worklist.insert(V);
167 }
168 }
169 return nullptr;
170}
171
172/// Find the canonical IV increment of \p Plan's vector loop region. Returns
173/// nullptr if not found.
175
176/// Returns the GEP nowrap flags for \p Ptr, looking through pointer casts
177/// mirroring Value::stripPointerCasts.
179
180/// Returns true if \p V is used as part of the address of another load or
181/// store.
183
184/// Find the ComputeReductionResult recipe for \p PhiR, looking through selects
185/// inserted for predicated reductions or tail folding.
187
188/// Finds the incoming alias-mask within the vector preheader.
190
191/// Returns the (early exiting block, exit block) pairs of \p Plan, i.e. all
192/// edges to an exit block that do not come from \p MiddleVPBB.
194getEarlyExits(const VPlan &Plan, const VPBlockBase *MiddleVPBB);
195
196/// Create a scalar-iv-steps recipe over \p Plan's canonical IV for an
197/// induction of \p Kind with \p InductionOpcode / \p FPBinOp, start value \p
198/// StartV and step \p Step, truncated to \p ResultTy, inserting recipes via \p
199/// Builder.
202 Instruction::BinaryOps InductionOpcode,
203 FPMathOperator *FPBinOp, Type *ResultTy, VPValue *StartV,
204 VPValue *Step, DebugLoc DL, VPBuilder &Builder,
205 const VPIRFlags::WrapFlagsTy &Flags = {});
206
207/// Scalarize a VPWidenPointerInductionRecipe by replacing it with a PtrAdd
208/// (IndStart, ScalarIVSteps (0, Step)). This is used when the recipe only
209/// generates scalar values.
210VPValue *scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV,
211 VPlan &Plan, VPBuilder &Builder);
212
213/// Returns true if \p R is dead, i.e. none of its defined values are used and
214/// it has no side effects (with the exception of conditional assumes, which are
215/// considered dead as their conditions may be flattened).
216bool isDeadRecipe(VPRecipeBase &R);
217
218/// Recursively delete \p V and any of its operands that become dead.
219void recursivelyDeleteDeadRecipes(VPValue *V);
220
221/// Collect all users of \p V, looking through recipes that define other values.
223
224/// Try to fold \p R using InstSimplifyFolder. Will succeed and return a
225/// non-nullptr VPValue for a handled opcode or intrinsic ID if corresponding \p
226/// Operands are foldable live-ins.
227VPIRValue *tryToFoldLiveIns(VPSingleDefRecipe &R, ArrayRef<VPValue *> Operands,
228 const DataLayout &DL);
229
230/// Insert phis to reconstruct SSA for a single value starting from \p VPBB. \p
231/// Defs is a map of definitions at specific blocks. Returns the
232/// reconstructed value at VPBB. Use if the CFG has been modified such that a
233/// def no longer dominates all its uses. Every block leading to VPBB must be
234/// reachable from the entry and the plan must be plain-CFG (not contain any
235/// regions).
236LLVM_ABI_FOR_TEST VPValue *
237reconstructSSA(VPBasicBlock *VPBB, DenseMap<VPBasicBlock *, VPValue *> &Defs);
238
239/// Returns \p Freq as a BranchProbability, relative to the full mass.
240BranchProbability getExecutionProbability(BlockFrequency Freq);
241
242/// Computes for each block in \p Blocks, which must be in reverse post-order,
243/// the frequency with which it executes relative to the first (header) block,
244/// and whether that frequency was composed using any estimated branch weights.
245/// The frequency of a block is the sum over its incoming edges, or std::nullopt
246/// if any edge on a path reaching it lacks branch weights. Edges to blocks
247/// outside \p Blocks are ignored.
248DenseMap<const VPBasicBlock *, std::optional<VPExecutionFrequency>>
250
251/// Get the value type of a VPInstruction or VPReplicateRecipe load or store.
253 bool IsLoad = vputils::getOpcode(R) == Instruction::Load;
254 return (IsLoad ? R : R->getOperand(0))->getScalarType();
255}
256
257namespace detail {
258
259/// Template-independent implementation for pullOutPermutations.
261 VPlan &Plan, function_ref<VPValue *(VPValue *Op)> Perm,
263} // namespace detail
264
265/// Removes the permutation pattern \p Perm from any elementwise operations
266/// in the plan, by constructing a new permutation via \p Build.
267/// e.g. binop(perm(x), perm(y)) -> perm(binop(x,y)).
268template <typename Match_t, typename Builder>
269void pullOutPermutations(VPlan &Plan, Match_t Perm, Builder Build) {
270 // Convert matcher to function returing the matched VPValue.
271 auto MatchPerm = [&Perm](VPValue *Op) -> VPValue * {
272 VPValue *X;
273 return match(Op, Perm(X)) ? X : nullptr;
274 };
275 detail::pullOutPermutationsImpl(Plan, MatchPerm, Build);
276}
277
278} // namespace vputils
279
280/// Lightweight SCEV-to-VPlan expander. Converts SCEV expressions into
281/// VPInstructions and live-ins. Canonical IVs and non-affine SCEVAddRecExprs
282/// are wrapped in a VPExpandSCEVRecipe to be expanded to IR later. Expansions
283/// are reused across calls to expand(), so the builder's insert point must
284/// only move to positions dominated by all earlier insert points.
286 VPBuilder &Builder;
287 ScalarEvolution &SE;
288 DebugLoc DL;
289
290 /// When true, nested SCEVUDivExprs are expanded so that they cannot divide by
291 /// zero, matching SCEVExpander's SafeUDivMode.
292 bool SafeUDivMode = false;
293
294 /// If set, expressions invariant in this loop are expanded in IR via
295 /// VPExpandSCEVRecipes, which hoists them out of it.
296 const Loop *HoistOutOf;
297
299 InsertedExpressions;
300
301 /// Try to find a loop-invariant IR value in the plan's entry block whose
302 /// SCEV matches \p S. Returns the corresponding live-in VPValue, or nullptr
303 /// if none is found.
304 VPValue *tryToReuseIRValue(const SCEV *S);
305
306 /// Returns true if \p S can be expanded in IR, hoisted out of HoistOutOf.
307 bool canExpandInIR(const SCEV *S);
308
309 /// Expand the sum of \p Operands, with \p WrapFlags on the adds.
311 VPIRFlags::WrapFlagsTy WrapFlags);
312
313 /// Expand pointer-typed \p S as a ptradd of its pointer base and offset.
314 VPValue *expandAsPtrAdd(const SCEVNAryExpr *S);
315
316 VPValue *expandImpl(const SCEV *S);
317
318public:
320 const Loop *HoistOutOf = nullptr)
321 : Builder(Builder), SE(SE), DL(DL), HoistOutOf(HoistOutOf) {}
322
323 /// Expand \p S into recipes and live-ins using the builder.
324 VPValue *expand(const SCEV *S);
325
326 /// Expand the expression of \p R, or return \p R if it must be expanded in
327 /// IR.
329 return R.expandInIR() ? &R : expand(R.getSCEV());
330 }
331};
332//===----------------------------------------------------------------------===//
333// Utilities for modifying predecessors and successors of VPlan blocks.
334//===----------------------------------------------------------------------===//
335
336/// Class that provides utilities for VPBlockBases in VPlan.
338public:
339 VPBlockUtils() = delete;
340
341 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
342 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
343 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
344 /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
345 /// have neither successors nor predecessors.
346 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
347 assert(!NewBlock->hasSuccessors() && !NewBlock->hasPredecessors() &&
348 "Can't insert new block with predecessors or successors.");
349 NewBlock->setParent(BlockPtr->getParent());
350 transferSuccessors(BlockPtr, NewBlock);
351 connectBlocks(BlockPtr, NewBlock);
352 }
353
354 /// Insert disconnected block \p NewBlock before \p Blockptr. First
355 /// disconnects all predecessors of \p BlockPtr and connects them to \p
356 /// NewBlock. Add \p NewBlock as predecessor of \p BlockPtr and \p BlockPtr as
357 /// successor of \p NewBlock.
358 static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
359 assert(!NewBlock->hasSuccessors() && !NewBlock->hasPredecessors() &&
360 "Can't insert new block with predecessors or successors.");
361 NewBlock->setParent(BlockPtr->getParent());
362 for (VPBlockBase *Pred : to_vector(BlockPtr->predecessors()))
363 replaceSuccessor(Pred, BlockPtr, NewBlock);
364 connectBlocks(NewBlock, BlockPtr);
365 }
366
367 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
368 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
369 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
370 /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
371 /// and \p IfTrue and \p IfFalse must have neither successors nor
372 /// predecessors.
373 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
374 VPBlockBase *BlockPtr) {
375 assert(!IfTrue->hasSuccessors() && "Can't insert IfTrue with successors.");
376 assert(!IfFalse->hasSuccessors() &&
377 "Can't insert IfFalse with successors.");
378 BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
379 IfTrue->setPredecessors({BlockPtr});
380 IfFalse->setPredecessors({BlockPtr});
381 IfTrue->setParent(BlockPtr->getParent());
382 IfFalse->setParent(BlockPtr->getParent());
383 }
384
385 /// Connect VPBlockBases \p From and \p To bi-directionally. If \p PredIdx is
386 /// -1, append \p From to the predecessors of \p To, otherwise set \p To's
387 /// predecessor at \p PredIdx to \p From. If \p SuccIdx is -1, append \p To to
388 /// the successors of \p From, otherwise set \p From's successor at \p SuccIdx
389 /// to \p To. Both VPBlockBases must have the same parent, which can be null.
390 /// Both VPBlockBases can be already connected to other VPBlockBases.
391 static void connectBlocks(VPBlockBase *From, VPBlockBase *To,
392 unsigned PredIdx = -1u, unsigned SuccIdx = -1u) {
393 assert((From->getParent() == To->getParent()) &&
394 "Can't connect two block with different parents");
395
396 if (SuccIdx == -1u)
397 From->appendSuccessor(To);
398 else
399 From->getSuccessors()[SuccIdx] = To;
400
401 if (PredIdx == -1u)
402 To->appendPredecessor(From);
403 else
404 To->getPredecessors()[PredIdx] = From;
405 }
406
407 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
408 /// from the successors of \p From and \p From from the predecessors of \p To.
409 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
410 assert(To && "Successor to disconnect is null.");
411 From->removeSuccessor(To);
412 To->removePredecessor(From);
413 }
414
415 /// Redirect the edge from \p From to \p OldSucc to \p NewSucc, keeping \p
416 /// From's successor order. \p From is removed from \p OldSucc's predecessors
417 /// and appended to \p NewSucc's.
418 static void replaceSuccessor(VPBlockBase *From, VPBlockBase *OldSucc,
419 VPBlockBase *NewSucc) {
420 From->replaceSuccessor(OldSucc, NewSucc);
421 OldSucc->removePredecessor(From);
422 NewSucc->appendPredecessor(From);
423 }
424
425 /// Reassociate all the blocks connected to \p Old so that they now point to
426 /// \p New.
427 static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {
428 auto Preds = to_vector(Old->getPredecessors());
429 auto Succs = to_vector(Old->getSuccessors());
430 for (auto *Pred : Preds)
431 Pred->replaceSuccessor(Old, New);
432 for (auto *Succ : Succs)
433 Succ->replacePredecessor(Old, New);
434 New->setPredecessors(Old->getPredecessors());
435 New->setSuccessors(Old->getSuccessors());
436 Old->clearPredecessors();
437 Old->clearSuccessors();
438 }
439
440 /// Transfer successors from \p Old to \p New. \p New must have no successors.
442 for (auto *Succ : Old->getSuccessors())
443 Succ->replacePredecessor(Old, New);
444 New->setSuccessors(Old->getSuccessors());
445 Old->clearSuccessors();
446 }
447
448 /// Clone the CFG for all nodes reachable from \p Entry, including cloning
449 /// the blocks and their recipes. Operands of cloned recipes will NOT be
450 /// updated. Remapping of operands must be done separately. Returns a pair
451 /// with the new entry and exiting blocks of the cloned region. If \p Entry
452 /// isn't part of a region, return nullptr for the exiting block.
453 static std::pair<VPBlockBase *, VPBlockBase *> cloneFrom(VPBlockBase *Entry);
454
455 /// Return an iterator range over \p Range which only includes \p BlockTy
456 /// blocks. The accesses are casted to \p BlockTy.
457 template <typename BlockTy, typename T> static auto blocksOnly(T &&Range) {
458 return make_isa_range<BlockTy>(std::forward<T>(Range));
459 }
460
461 /// Return an iterator range over \p Range with each block cast to \p
462 /// BlockTy. Unlike blocksOnly, all blocks in \p Range must be of type
463 /// \p BlockTy.
464 template <typename BlockTy, typename T> static auto blocksAs(T &&Range) {
465 // Create BaseTy with correct const-ness based on BlockTy.
466 using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
467 const VPBlockBase, VPBlockBase>;
468 return map_range(
469 Range, [](BaseTy *Block) -> BlockTy * { return cast<BlockTy>(Block); });
470 }
471
472 /// Returns the blocks between \p FirstBB and \p LastBB, where FirstBB
473 /// to LastBB forms a single-sucessor chain.
476 VPBasicBlock *LastBB);
477
478 /// Inserts \p BlockPtr on the edge between \p From and \p To. That is, update
479 /// \p From's successor to \p To to point to \p BlockPtr and \p To's
480 /// predecessor from \p From to \p BlockPtr. \p From and \p To are added to \p
481 /// BlockPtr's predecessors and successors respectively. There must be a
482 /// single edge between \p From and \p To.
483 static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,
484 VPBlockBase *BlockPtr) {
485 unsigned SuccIdx = From->getIndexForSuccessor(To);
486 unsigned PredIx = To->getIndexForPredecessor(From);
487 VPBlockUtils::connectBlocks(From, BlockPtr, -1, SuccIdx);
488 VPBlockUtils::connectBlocks(BlockPtr, To, PredIx, -1);
489 }
490
491 /// Returns true if \p VPB is a loop header, based on regions or \p VPDT in
492 /// their absence.
493 static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
494
495 /// Returns true if \p VPB is a loop latch, using isHeader().
496 static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
497
498 /// Returns the header and latch of the outermost loop of \p Plan in plain
499 /// CFG form (before regions are formed).
500 static std::pair<VPBasicBlock *, VPBasicBlock *>
501 getPlainCFGHeaderAndLatch(const VPlan &Plan);
502
503 /// Returns the middle block of \p Plan in plain CFG form (before regions
504 /// are formed).
505 static VPBasicBlock *getPlainCFGMiddleBlock(const VPlan &Plan);
506};
507
508} // namespace llvm
509
510#endif
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define X(NUM, ENUM, NAME)
Definition ELF.h:665
#define LLVM_ABI_FOR_TEST
Definition Compiler.h:216
std::pair< BasicBlock *, unsigned > BlockTy
A pair of (basic block, score).
#define F(x, y, z)
Definition MD5.cpp:54
#define I(x, y, z)
Definition MD5.cpp:57
#define T
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
SI Fold Operands
This file contains the declarations of the Vectorization Plan base classes:
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
A debug info location.
Definition DebugLoc.h:126
Utility class for floating point operations which can have information about relaxed accuracy require...
Definition Operator.h:202
Represents flags for the getelementptr instruction/expression.
A struct for saving information about induction variables.
InductionKind
This enum represents the kinds of inductions that we support.
Represents a single loop in the control flow graph.
Definition LoopInfo.h:40
Representation for a specific memory location.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
This node is a base class providing common functionality for n'ary operators.
This class represents an analyzed expression in the program.
The main scalar evolution driver.
A vector that has set insertion semantics.
Definition SetVector.h:57
size_type size() const
Determine the number of elements in the SetVector.
Definition SetVector.h:103
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition SetVector.h:157
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition Type.h:46
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition VPlan.h:4540
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition VPlan.h:95
VPRegionBlock * getParent()
Definition VPlan.h:193
iterator_range< VPBlockBase ** > predecessors()
Definition VPlan.h:226
bool hasPredecessors() const
Returns true if this block has any predecessors.
Definition VPlan.h:223
unsigned getIndexForSuccessor(const VPBlockBase *Succ) const
Returns the index for Succ in the blocks successor list.
Definition VPlan.h:340
void setPredecessors(ArrayRef< VPBlockBase * > NewPreds)
Set each VPBasicBlock in NewPreds as predecessor of this VPBlockBase.
Definition VPlan.h:296
unsigned getIndexForPredecessor(const VPBlockBase *Pred) const
Returns the index for Pred in the blocks predecessors list.
Definition VPlan.h:333
bool hasSuccessors() const
Returns true if this block has any successors.
Definition VPlan.h:221
const VPBlocksTy & getPredecessors() const
Definition VPlan.h:228
void clearSuccessors()
Remove all the successors of this block.
Definition VPlan.h:315
void setTwoSuccessors(VPBlockBase *IfTrue, VPBlockBase *IfFalse)
Set two given VPBlockBases IfTrue and IfFalse to be the two successors of this VPBlockBase.
Definition VPlan.h:287
void clearPredecessors()
Remove all the predecessor of this block.
Definition VPlan.h:312
void setParent(VPRegionBlock *P)
Definition VPlan.h:203
const VPBlocksTy & getSuccessors() const
Definition VPlan.h:217
static auto blocksAs(T &&Range)
Return an iterator range over Range with each block cast to BlockTy.
Definition VPlanUtils.h:464
static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected VPBlockBase NewBlock after BlockPtr.
Definition VPlanUtils.h:346
static void insertOnEdge(VPBlockBase *From, VPBlockBase *To, VPBlockBase *BlockPtr)
Inserts BlockPtr on the edge between From and To.
Definition VPlanUtils.h:483
static void replaceSuccessor(VPBlockBase *From, VPBlockBase *OldSucc, VPBlockBase *NewSucc)
Redirect the edge from From to OldSucc to NewSucc, keeping From's successor order.
Definition VPlanUtils.h:418
static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT)
Returns true if VPB is a loop latch, using isHeader().
static VPBasicBlock * getPlainCFGMiddleBlock(const VPlan &Plan)
Returns the middle block of Plan in plain CFG form (before regions are formed).
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:373
static void connectBlocks(VPBlockBase *From, VPBlockBase *To, unsigned PredIdx=-1u, unsigned SuccIdx=-1u)
Connect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:391
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition VPlanUtils.h:409
static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New)
Reassociate all the blocks connected to Old so that they now point to New.
Definition VPlanUtils.h:427
static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr)
Insert disconnected block NewBlock before Blockptr.
Definition VPlanUtils.h:358
static auto blocksOnly(T &&Range)
Return an iterator range over Range which only includes BlockTy blocks.
Definition VPlanUtils.h:457
static std::pair< VPBasicBlock *, VPBasicBlock * > getPlainCFGHeaderAndLatch(const VPlan &Plan)
Returns the header and latch of the outermost loop of Plan in plain CFG form (before regions are form...
static void transferSuccessors(VPBlockBase *Old, VPBlockBase *New)
Transfer successors from Old to New. New must have no successors.
Definition VPlanUtils.h:441
static SmallVector< VPBasicBlock * > blocksInSingleSuccessorChainBetween(VPBasicBlock *FirstBB, VPBasicBlock *LastBB)
Returns the blocks between FirstBB and LastBB, where FirstBB to LastBB forms a single-sucessor chain.
static std::pair< VPBlockBase *, VPBlockBase * > cloneFrom(VPBlockBase *Entry)
Clone the CFG for all nodes reachable from Entry, including cloning the blocks and their recipes.
Definition VPlan.cpp:653
Template specialization of the standard LLVM dominator tree utility for VPBlockBases.
Recipe to expand a SCEV expression.
Definition VPlan.h:4134
Class to record and manage LLVM IR flags.
Definition VPlan.h:683
This is a concrete Recipe that models a single VPlan-level instruction.
Definition VPlan.h:1322
@ Intrinsic
Calls a scalar intrinsic. The intrinsic ID is the last operand.
Definition VPlan.h:1449
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition VPlan.h:402
A recipe for handling reduction phis.
Definition VPlan.h:2883
VPValue * expand(VPExpandSCEVRecipe &R)
Expand the expression of R, or return R if it must be expanded in IR.
Definition VPlanUtils.h:328
VPSCEVExpander(VPBuilder &Builder, ScalarEvolution &SE, DebugLoc DL, const Loop *HoistOutOf=nullptr)
Definition VPlanUtils.h:319
VPValue * expand(const SCEV *S)
Expand S into recipes and live-ins using the builder.
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition VPlan.h:4371
VPSingleDefRecipe is a base class for recipes that model a sequence of one or more output IR that def...
Definition VPlan.h:605
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition VPlanValue.h:396
This is the base class of the VPlan Def/Use graph, used for modeling the data flow into,...
Definition VPlanValue.h:50
VPRecipeBase * getDefiningRecipe()
Returns the recipe defining this VPValue or nullptr if it is not defined by a recipe,...
Definition VPlan.cpp:119
user_range users()
Definition VPlanValue.h:157
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition VPlan.h:4958
An efficient, type-erasing, non-owning reference to a callable.
CallInst * Call
bool match(Val *V, const Pattern &P)
void pullOutPermutationsImpl(VPlan &Plan, function_ref< VPValue *(VPValue *Op)> Perm, function_ref< VPSingleDefRecipe *(VPSingleDefRecipe *X)> Build)
Template-independent implementation for pullOutPermutations.
BranchProbability getExecutionProbability(BlockFrequency Freq)
Returns Freq as a BranchProbability, relative to the full mass.
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...
bool cannotHoistOrSinkRecipe(const VPRecipeBase &R, bool Sinking=false)
Return true if we do not know how to (mechanically) hoist or sink R.
unsigned getOpcode(const VPValue *V)
Return the instruction opcode for the recipe defining V or 0 for unsupported recipes and VPValues not...
std::optional< int64_t > getConstantStride(VPValue *Addr, Type *AccessTy, PredicatedScalarEvolution &PSE, const Loop *L)
If the pointer operand Addr of a memory access is an affine AddRec w.r.t.
VPBasicBlock * getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT)
Returns the header block of the first, top-level loop, or null if none exist.
bool isAddressSCEVForCost(const SCEV *Addr, ScalarEvolution &SE, const Loop *L)
Returns true if Addr is an address SCEV that can be passed to TTI::getAddressComputationCost,...
LLVM_ABI_FOR_TEST VPValue * reconstructSSA(VPBasicBlock *VPBB, DenseMap< VPBasicBlock *, VPValue * > &Defs)
Insert phis to reconstruct SSA for a single value starting from VPBB.
bool onlyFirstPartUsed(const VPValue *Def)
Returns true if only the first part of Def is used by all users.
Intrinsic::ID getIntrinsicID(const Ty *R)
Return the intrinsic ID underlying a call.
Definition VPlanUtils.h:102
VPInstruction * findComputeReductionResult(VPReductionPHIRecipe *PhiR)
Find the ComputeReductionResult recipe for PhiR, looking through selects inserted for predicated redu...
VPInstruction * findCanonicalIVIncrement(VPlan &Plan)
Find the canonical IV increment of Plan's vector loop region.
std::optional< MemoryLocation > getMemoryLocation(const VPRecipeBase &R)
Return a MemoryLocation for R with noalias metadata populated from R, if the recipe is supported and ...
bool onlyFirstLaneUsed(const VPValue *Def)
Returns true if only the first lane of Def is used by all users.
VPIRValue * tryToFoldLiveIns(VPSingleDefRecipe &R, ArrayRef< VPValue * > Operands, const DataLayout &DL)
Try to fold R using InstSimplifyFolder.
SmallVector< std::pair< VPBasicBlock *, VPIRBasicBlock * > > getEarlyExits(const VPlan &Plan, const VPBlockBase *MiddleVPBB)
Returns the (early exiting block, exit block) pairs of Plan, i.e.
VPValue * findIncomingAliasMask(const VPlan &Plan)
Finds the incoming alias-mask within the vector preheader.
DenseMap< const VPBasicBlock *, std::optional< VPExecutionFrequency > > computeExecutionFrequencies(ArrayRef< VPBasicBlock * > Blocks)
Computes for each block in Blocks, which must be in reverse post-order, the frequency with which it e...
Type * getLoadStoreValueType(VPSingleDefRecipe *R)
Get the value type of a VPInstruction or VPReplicateRecipe load or store.
Definition VPlanUtils.h:252
VPScalarIVStepsRecipe * createScalarIVSteps(VPlan &Plan, InductionDescriptor::InductionKind Kind, Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp, Type *ResultTy, VPValue *StartV, VPValue *Step, DebugLoc DL, VPBuilder &Builder, const VPIRFlags::WrapFlagsTy &Flags={})
Create a scalar-iv-steps recipe over Plan's canonical IV for an induction of Kind with InductionOpcod...
bool propagatesFirstLaneUse(const VPUser *U, const VPValue *Op)
Returns true if checking whether U uses the first lane of Op requires recursively checking Op's users...
void recursivelyDeleteDeadRecipes(VPValue *V)
Recursively delete V and any of its operands that become dead.
bool doesGeneratePerAllLanes(const VPRecipeBase *R)
Returns true if R produces scalar values for all VF lanes.
VPIRFlags getFlagsForInduction(const InductionDescriptor &ID, const VPPhi *PhiR)
Extracts and returns NoWrap flags from PhiR and fast-math flags from ID.
bool isDeadRecipe(VPRecipeBase &R)
Returns true if R is dead, i.e.
VPRecipeBase * findRecipe(VPValue *Start, PredT Pred)
Search Start's users for a recipe satisfying Pred, looking through recipes with definitions.
Definition VPlanUtils.h:154
bool isElementwise(const VPValue *V)
Return true if V is elementwise, i.e. none of the lanes are permuted.
bool onlyScalarValuesOrLanesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users, either directly or by extracting a c...
bool onlyScalarValuesUsed(const VPValue *Def)
Returns true if only scalar values of Def are used by all users.
LLVM_ABI_FOR_TEST bool isUniformAcrossVFsAndUFs(const VPValue *V)
Checks if V is uniform across all VF lanes and UF parts.
VPValue * getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, bool ExpandInIR=false)
Get or create a VPValue that corresponds to the expansion of Expr.
bool isUsedByLoadStoreAddress(const VPValue *V)
Returns true if V is used as part of the address of another load or store.
std::optional< std::pair< bool, unsigned > > getOpcodeOrIntrinsicID(const VPValue *V)
Get the instruction opcode or intrinsic ID for the recipe defining V.
VPValue * scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV, VPlan &Plan, VPBuilder &Builder)
Scalarize a VPWidenPointerInductionRecipe by replacing it with a PtrAdd (IndStart,...
GEPNoWrapFlags getGEPFlagsForPtr(VPValue *Ptr)
Returns the GEP nowrap flags for Ptr, looking through pointer casts mirroring Value::stripPointerCast...
LLVM_ABI_FOR_TEST const SCEV * getSCEVExprForVPValue(const VPValue *V, PredicatedScalarEvolution &PSE, const Loop *L=nullptr)
Return the SCEV expression for V.
void pullOutPermutations(VPlan &Plan, Match_t Perm, Builder Build)
Removes the permutation pattern Perm from any elementwise operations in the plan, by constructing a n...
Definition VPlanUtils.h:269
unsigned getVFScaleFactor(VPRecipeBase *R)
Get the VF scaling factor applied to the recipe's output, if the recipe has one.
SmallVector< VPUser * > collectUsersRecursively(VPValue *V)
Collect all users of V, looking through recipes that define other values.
This is an optimization pass for GlobalISel generic memory operations.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:643
VPBuilderBase<> VPBuilder
Definition VPlan.h:66
auto map_range(ContainerTy &&C, FuncTy F)
Return a range that applies F to the elements of C.
Definition STLExtras.h:366
auto make_isa_range(RangeT &&Range)
Return a range over Range containing only elements for which isa<T> holds, casting each of them to T.
Definition STLExtras.h:567
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...
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
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
DWARFExpression::Operation Op
ArrayRef(const T &OneElt) -> ArrayRef< T >
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
Definition Casting.h:559