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#include "llvm/Support/BlockFrequency.h"
14#include "llvm/Support/BranchProbability.h"
15#include "llvm/Support/Compiler.h"
16
17namespace llvm {
18class DominatorTree;
19class MemoryLocation;
20class ScalarEvolution;
21class SCEV;
22class PredicatedScalarEvolution;
23class VPBuilder;
24} // namespace llvm
25
26namespace llvm {
27
28namespace vputils {
29/// Returns true if only the first lane of \p Def is used.
30bool onlyFirstLaneUsed(const VPValue *Def);
31
32/// Returns true if only the first part of \p Def is used.
33bool onlyFirstPartUsed(const VPValue *Def);
34
35/// Returns true if only scalar values of \p Def are used by all users.
36bool onlyScalarValuesUsed(const VPValue *Def);
37
38/// Get or create a VPValue that corresponds to the expansion of \p Expr. If \p
39/// Expr is a SCEVConstant or SCEVUnknown, return a VPValue wrapping the live-in
40/// value. Otherwise return a VPExpandSCEVRecipe to expand \p Expr. If \p Plan's
41/// pre-header already contains a recipe expanding \p Expr, return it. If not,
42/// create a new one.
43VPValue *getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr);
44
45/// Return the SCEV expression for \p V. Returns SCEVCouldNotCompute if no
46/// SCEV expression could be constructed.
47const SCEV *getSCEVExprForVPValue(const VPValue *V,
48 PredicatedScalarEvolution &PSE,
49 const Loop *L = nullptr);
50
51/// Returns true if \p Addr is an address SCEV that can be passed to
52/// TTI::getAddressComputationCost, i.e. the address SCEV is loop invariant, an
53/// affine AddRec (i.e. induction ), or an add expression of such operands or a
54/// sign-extended AddRec.
55bool isAddressSCEVForCost(const SCEV *Addr, ScalarEvolution &SE, const Loop *L);
56
57/// Returns true if \p VPV is a single scalar, either because it produces the
58/// same value for all lanes or only has its first lane used.
59bool isSingleScalar(const VPValue *VPV);
60
61/// Checks if \p V is uniform across all VF lanes and UF parts. It is considered
62/// as such if it is either loop invariant (defined outside the vector region)
63/// or its operands are known to be uniform across all VFs and UFs (e.g.
64/// VPDerivedIV or the canonical IV).
65bool isUniformAcrossVFsAndUFs(const VPValue *V);
66
67/// Return true if \p V is elementwise, i.e. none of the lanes are permuted.
68bool isElementwise(const VPValue *V);
69
70/// Returns true if \p R produces scalar values for all VF lanes.
71bool doesGeneratePerAllLanes(const VPRecipeBase *R);
72
73/// Returns the header block of the first, top-level loop, or null if none
74/// exist.
75VPBasicBlock *getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT);
76
77/// Get the VF scaling factor applied to the recipe's output, if the recipe has
78/// one.
79unsigned getVFScaleFactor(VPRecipeBase *R);
80
81/// Return true if we do not know how to (mechanically) hoist or sink \p R.
82/// When sinking, passing \p Sinking = true ensures that assumes aren't sunk.
83/// Returns true for recipes that access memory.
84bool cannotHoistOrSinkRecipe(const VPRecipeBase &R, bool Sinking = false);
85
86/// Return the intrinsic ID underlying a call.
87template <typename Ty> Intrinsic::ID getIntrinsicID(const Ty *R) {
88 if (const auto *Intr = dyn_cast<VPWidenIntrinsicRecipe>(R))
89 return Intr->getVectorIntrinsicID();
90 if (const auto *Call = dyn_cast<VPWidenCallRecipe>(R))
91 return Call->getCalledScalarFunction()->getIntrinsicID();
92
93 auto GetCalleeIntrinsic = [&](VPValue *CalleeOp) -> Intrinsic::ID {
94 if (!isa<VPIRValue>(Val: CalleeOp))
95 return Intrinsic::not_intrinsic;
96 auto *F = cast<Function>(Val: CalleeOp->getLiveInIRValue());
97 return F->getIntrinsicID();
98 };
99 if (const auto *Rep = dyn_cast<VPReplicateRecipe>(R))
100 if (Rep->getOpcode() == Instruction::Call)
101 // The callee is the last operand, excluding the mask if predicated.
102 return GetCalleeIntrinsic(
103 Rep->getOperand(Rep->getNumOperandsWithoutMask() - 1));
104 if (const auto *VPI = dyn_cast<VPInstruction>(R)) {
105 if (VPI->getOpcode() == Instruction::Call)
106 // The callee is the last operand, excluding the mask if masked.
107 return GetCalleeIntrinsic(
108 VPI->getOperand(VPI->getNumOperandsWithoutMask() - 1));
109 if (VPI->getOpcode() == VPInstruction::Intrinsic) {
110 return cast<VPConstantInt>(VPI->getOperand(VPI->getNumOperands() - 1))
111 ->getZExtValue();
112 }
113 }
114 return Intrinsic::not_intrinsic;
115}
116
117/// Return the instruction opcode for the recipe defining \p V or 0 for
118/// unsupported recipes and VPValues not defined by a recipe.
119unsigned getOpcode(const VPValue *V);
120
121/// Get the instruction opcode or intrinsic ID for the recipe defining \p V.
122/// Returns an optional pair, where the first element indicates whether it is an
123/// intrinsic ID.
124std::optional<std::pair<bool, unsigned>>
125getOpcodeOrIntrinsicID(const VPValue *V);
126
127/// Return a MemoryLocation for \p R with noalias metadata populated from
128/// \p R, if the recipe is supported and std::nullopt otherwise. The pointer of
129/// the location is conservatively set to nullptr.
130std::optional<MemoryLocation> getMemoryLocation(const VPRecipeBase &R);
131
132/// Extracts and returns NoWrap and FastMath flags from the induction binop in
133/// \p ID.
134inline VPIRFlags getFlagsFromIndDesc(const InductionDescriptor &ID) {
135 if (ID.getKind() == InductionDescriptor::IK_FpInduction)
136 return ID.getInductionBinOp()->getFastMathFlags();
137
138 if (auto *OBO = dyn_cast_if_present<OverflowingBinaryOperator>(
139 Val: ID.getInductionBinOp()))
140 return VPIRFlags::WrapFlagsTy(OBO->hasNoUnsignedWrap(),
141 OBO->hasNoSignedWrap());
142
143 assert(ID.getKind() == InductionDescriptor::IK_IntInduction &&
144 "Expected int induction");
145 return VPIRFlags::WrapFlagsTy(false, false);
146}
147
148/// Search \p Start's users for a recipe satisfying \p Pred, looking through
149/// recipes with definitions.
150template <typename PredT>
151inline VPRecipeBase *findRecipe(VPValue *Start, PredT Pred) {
152 SetVector<VPValue *> Worklist;
153 Worklist.insert(X: Start);
154 for (unsigned I = 0; I != Worklist.size(); ++I) {
155 VPValue *Cur = Worklist[I];
156 auto *R = Cur->getDefiningRecipe();
157 if (!R)
158 continue;
159 if (Pred(R))
160 return R;
161 for (VPUser *U : Cur->users()) {
162 for (VPValue *V : cast<VPRecipeBase>(Val: U)->definedValues())
163 Worklist.insert(X: V);
164 }
165 }
166 return nullptr;
167}
168
169/// Find the canonical IV increment of \p Plan's vector loop region. Returns
170/// nullptr if not found.
171VPInstruction *findCanonicalIVIncrement(VPlan &Plan);
172
173/// Returns the GEP nowrap flags for \p Ptr, looking through pointer casts
174/// mirroring Value::stripPointerCasts.
175GEPNoWrapFlags getGEPFlagsForPtr(VPValue *Ptr);
176
177/// Returns true if \p V is used as part of the address of another load or
178/// store.
179bool isUsedByLoadStoreAddress(const VPValue *V);
180
181/// Find the ComputeReductionResult recipe for \p PhiR, looking through selects
182/// inserted for predicated reductions or tail folding.
183VPInstruction *findComputeReductionResult(VPReductionPHIRecipe *PhiR);
184
185/// Finds the incoming alias-mask within the vector preheader.
186VPValue *findIncomingAliasMask(const VPlan &Plan);
187
188/// Returns the (early exiting block, exit block) pairs of \p Plan, i.e. all
189/// edges to an exit block that do not come from \p MiddleVPBB.
190SmallVector<std::pair<VPBasicBlock *, VPIRBasicBlock *>>
191getEarlyExits(const VPlan &Plan, const VPBlockBase *MiddleVPBB);
192
193/// Create a scalar-iv-steps recipe over \p Plan's canonical IV for an
194/// induction of \p Kind with \p InductionOpcode / \p FPBinOp, start value \p
195/// StartV and step \p Step, truncated to \p TruncI's type if \p TruncI is
196/// non-null, inserting recipes via \p Builder.
197VPScalarIVStepsRecipe *createScalarIVSteps(
198 VPlan &Plan, InductionDescriptor::InductionKind Kind,
199 Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp,
200 Instruction *TruncI, VPValue *StartV, VPValue *Step, DebugLoc DL,
201 VPBuilder &Builder, const VPIRFlags::WrapFlagsTy &Flags = {});
202
203/// Scalarize a VPWidenPointerInductionRecipe by replacing it with a PtrAdd
204/// (IndStart, ScalarIVSteps (0, Step)). This is used when the recipe only
205/// generates scalar values.
206VPValue *scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV,
207 VPlan &Plan, VPBuilder &Builder);
208
209/// Returns true if \p R is dead, i.e. none of its defined values are used and
210/// it has no side effects (with the exception of conditional assumes, which are
211/// considered dead as their conditions may be flattened).
212bool isDeadRecipe(VPRecipeBase &R);
213
214/// Recursively delete \p V and any of its operands that become dead.
215void recursivelyDeleteDeadRecipes(VPValue *V);
216
217/// Collect all users of \p V, looking through recipes that define other values.
218SmallVector<VPUser *> collectUsersRecursively(VPValue *V);
219
220/// Try to fold \p R using InstSimplifyFolder. Will succeed and return a
221/// non-nullptr VPValue for a handled opcode or intrinsic ID if corresponding \p
222/// Operands are foldable live-ins.
223VPIRValue *tryToFoldLiveIns(VPSingleDefRecipe &R, ArrayRef<VPValue *> Operands,
224 const DataLayout &DL);
225
226/// Insert phis to reconstruct SSA for a single value starting from \p VPBB. \p
227/// Defs is a map of definitions at specific blocks. Returns the
228/// reconstructed value at VPBB. Use if the CFG has been modified such that a
229/// def no longer dominates all its uses. Every block leading to VPBB must be
230/// reachable from the entry and the plan must be plain-CFG (not contain any
231/// regions).
232LLVM_ABI_FOR_TEST VPValue *
233reconstructSSA(VPBasicBlock *VPBB, DenseMap<VPBasicBlock *, VPValue *> &Defs);
234
235/// Denominator of the frequencies computed by computeExecutionFrequencies, i.e.
236/// the frequency of a block that always executes. Wider than
237/// BranchProbability's 31-bit one, which truncates rarely executed blocks to 0.
238inline constexpr uint64_t AlwaysExecutesFreq = 1ULL << 63;
239
240/// Returns \p Freq as a BranchProbability, relative to AlwaysExecutesFreq.
241BranchProbability getExecutionProbability(BlockFrequency Freq);
242
243/// Computes for each block in \p Blocks, which must be in reverse post-order,
244/// the frequency with which it executes relative to the first (header) block,
245/// and whether that frequency was composed using any estimated branch weights.
246/// The frequency of a block is the sum over its incoming edges, or std::nullopt
247/// if any edge on a path reaching it lacks branch weights. Edges to blocks
248/// outside \p Blocks are ignored.
249DenseMap<const VPBasicBlock *, std::optional<VPExecutionFrequency>>
250computeExecutionFrequencies(ArrayRef<VPBasicBlock *> Blocks);
251
252namespace detail {
253
254/// Template-independent implementation for pullOutPermutations.
255void pullOutPermutationsImpl(
256 VPlan &Plan, function_ref<VPValue *(VPValue *Op)> Perm,
257 function_ref<VPSingleDefRecipe *(VPSingleDefRecipe *X)> Build);
258} // namespace detail
259
260/// Removes the permutation pattern \p Perm from any elementwise operations
261/// in the plan, by constructing a new permutation via \p Build.
262/// e.g. binop(perm(x), perm(y)) -> perm(binop(x,y)).
263template <typename Match_t, typename Builder>
264void pullOutPermutations(VPlan &Plan, Match_t Perm, Builder Build) {
265 // Convert matcher to function returing the matched VPValue.
266 auto MatchPerm = [&Perm](VPValue *Op) -> VPValue * {
267 VPValue *X;
268 return match(Op, Perm(X)) ? X : nullptr;
269 };
270 detail::pullOutPermutationsImpl(Plan, Perm: MatchPerm, Build);
271}
272
273} // namespace vputils
274
275/// Lightweight SCEV-to-VPlan expander. Converts SCEV expressions into
276/// VPInstructions and live-ins. SCEVAddRecExprs are wrapped in a
277/// VPExpandSCEVRecipe to be expanded to IR later.
278class VPSCEVExpander {
279 VPBuilder &Builder;
280 ScalarEvolution &SE;
281 DebugLoc DL;
282
283 /// When true, nested SCEVUDivExprs are expanded so that they cannot divide by
284 /// zero, matching SCEVExpander's SafeUDivMode.
285 bool SafeUDivMode = false;
286
287 /// Try to find a loop-invariant IR value in the plan's entry block whose
288 /// SCEV matches \p S. Returns the corresponding live-in VPValue, or nullptr
289 /// if none is found.
290 VPValue *tryToReuseIRValue(const SCEV *S);
291
292public:
293 VPSCEVExpander(VPBuilder &Builder, ScalarEvolution &SE, DebugLoc DL)
294 : Builder(Builder), SE(SE), DL(DL) {}
295
296 /// Expand \p S into recipes and live-ins using the builder.
297 VPValue *expand(const SCEV *S);
298};
299//===----------------------------------------------------------------------===//
300// Utilities for modifying predecessors and successors of VPlan blocks.
301//===----------------------------------------------------------------------===//
302
303/// Class that provides utilities for VPBlockBases in VPlan.
304class VPBlockUtils {
305public:
306 VPBlockUtils() = delete;
307
308 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
309 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
310 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
311 /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
312 /// have neither successors nor predecessors.
313 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
314 assert(!NewBlock->hasSuccessors() && !NewBlock->hasPredecessors() &&
315 "Can't insert new block with predecessors or successors.");
316 NewBlock->setParent(BlockPtr->getParent());
317 transferSuccessors(Old: BlockPtr, New: NewBlock);
318 connectBlocks(From: BlockPtr, To: NewBlock);
319 }
320
321 /// Insert disconnected block \p NewBlock before \p Blockptr. First
322 /// disconnects all predecessors of \p BlockPtr and connects them to \p
323 /// NewBlock. Add \p NewBlock as predecessor of \p BlockPtr and \p BlockPtr as
324 /// successor of \p NewBlock.
325 static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
326 assert(!NewBlock->hasSuccessors() && !NewBlock->hasPredecessors() &&
327 "Can't insert new block with predecessors or successors.");
328 NewBlock->setParent(BlockPtr->getParent());
329 for (VPBlockBase *Pred : to_vector(Range: BlockPtr->predecessors())) {
330 Pred->replaceSuccessor(Old: BlockPtr, New: NewBlock);
331 NewBlock->appendPredecessor(Predecessor: Pred);
332 }
333 BlockPtr->clearPredecessors();
334 connectBlocks(From: NewBlock, To: BlockPtr);
335 }
336
337 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
338 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
339 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
340 /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
341 /// and \p IfTrue and \p IfFalse must have neither successors nor
342 /// predecessors.
343 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
344 VPBlockBase *BlockPtr) {
345 assert(!IfTrue->hasSuccessors() && "Can't insert IfTrue with successors.");
346 assert(!IfFalse->hasSuccessors() &&
347 "Can't insert IfFalse with successors.");
348 BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
349 IfTrue->setPredecessors({BlockPtr});
350 IfFalse->setPredecessors({BlockPtr});
351 IfTrue->setParent(BlockPtr->getParent());
352 IfFalse->setParent(BlockPtr->getParent());
353 }
354
355 /// Connect VPBlockBases \p From and \p To bi-directionally. If \p PredIdx is
356 /// -1, append \p From to the predecessors of \p To, otherwise set \p To's
357 /// predecessor at \p PredIdx to \p From. If \p SuccIdx is -1, append \p To to
358 /// the successors of \p From, otherwise set \p From's successor at \p SuccIdx
359 /// to \p To. Both VPBlockBases must have the same parent, which can be null.
360 /// Both VPBlockBases can be already connected to other VPBlockBases.
361 static void connectBlocks(VPBlockBase *From, VPBlockBase *To,
362 unsigned PredIdx = -1u, unsigned SuccIdx = -1u) {
363 assert((From->getParent() == To->getParent()) &&
364 "Can't connect two block with different parents");
365
366 if (SuccIdx == -1u)
367 From->appendSuccessor(Successor: To);
368 else
369 From->getSuccessors()[SuccIdx] = To;
370
371 if (PredIdx == -1u)
372 To->appendPredecessor(Predecessor: From);
373 else
374 To->getPredecessors()[PredIdx] = From;
375 }
376
377 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
378 /// from the successors of \p From and \p From from the predecessors of \p To.
379 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
380 assert(To && "Successor to disconnect is null.");
381 From->removeSuccessor(Successor: To);
382 To->removePredecessor(Predecessor: From);
383 }
384
385 /// Reassociate all the blocks connected to \p Old so that they now point to
386 /// \p New.
387 static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {
388 auto Preds = to_vector(Range&: Old->getPredecessors());
389 auto Succs = to_vector(Range&: Old->getSuccessors());
390 for (auto *Pred : Preds)
391 Pred->replaceSuccessor(Old, New);
392 for (auto *Succ : Succs)
393 Succ->replacePredecessor(Old, New);
394 New->setPredecessors(Old->getPredecessors());
395 New->setSuccessors(Old->getSuccessors());
396 Old->clearPredecessors();
397 Old->clearSuccessors();
398 }
399
400 /// Transfer successors from \p Old to \p New. \p New must have no successors.
401 static void transferSuccessors(VPBlockBase *Old, VPBlockBase *New) {
402 for (auto *Succ : Old->getSuccessors())
403 Succ->replacePredecessor(Old, New);
404 New->setSuccessors(Old->getSuccessors());
405 Old->clearSuccessors();
406 }
407
408 /// Clone the CFG for all nodes reachable from \p Entry, including cloning
409 /// the blocks and their recipes. Operands of cloned recipes will NOT be
410 /// updated. Remapping of operands must be done separately. Returns a pair
411 /// with the new entry and exiting blocks of the cloned region. If \p Entry
412 /// isn't part of a region, return nullptr for the exiting block.
413 static std::pair<VPBlockBase *, VPBlockBase *> cloneFrom(VPBlockBase *Entry);
414
415 /// Return an iterator range over \p Range which only includes \p BlockTy
416 /// blocks. The accesses are casted to \p BlockTy.
417 template <typename BlockTy, typename T> static auto blocksOnly(T &&Range) {
418 return make_isa_range<BlockTy>(std::forward<T>(Range));
419 }
420
421 /// Return an iterator range over \p Range with each block cast to \p
422 /// BlockTy. Unlike blocksOnly, all blocks in \p Range must be of type
423 /// \p BlockTy.
424 template <typename BlockTy, typename T> static auto blocksAs(T &&Range) {
425 // Create BaseTy with correct const-ness based on BlockTy.
426 using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
427 const VPBlockBase, VPBlockBase>;
428 return map_range(
429 Range, [](BaseTy *Block) -> BlockTy * { return cast<BlockTy>(Block); });
430 }
431
432 /// Returns the blocks between \p FirstBB and \p LastBB, where FirstBB
433 /// to LastBB forms a single-sucessor chain.
434 static SmallVector<VPBasicBlock *>
435 blocksInSingleSuccessorChainBetween(VPBasicBlock *FirstBB,
436 VPBasicBlock *LastBB);
437
438 /// Inserts \p BlockPtr on the edge between \p From and \p To. That is, update
439 /// \p From's successor to \p To to point to \p BlockPtr and \p To's
440 /// predecessor from \p From to \p BlockPtr. \p From and \p To are added to \p
441 /// BlockPtr's predecessors and successors respectively. There must be a
442 /// single edge between \p From and \p To.
443 static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,
444 VPBlockBase *BlockPtr) {
445 unsigned SuccIdx = From->getIndexForSuccessor(Succ: To);
446 unsigned PredIx = To->getIndexForPredecessor(Pred: From);
447 VPBlockUtils::connectBlocks(From, To: BlockPtr, PredIdx: -1, SuccIdx);
448 VPBlockUtils::connectBlocks(From: BlockPtr, To, PredIdx: PredIx, SuccIdx: -1);
449 }
450
451 /// Returns true if \p VPB is a loop header, based on regions or \p VPDT in
452 /// their absence.
453 static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
454
455 /// Returns true if \p VPB is a loop latch, using isHeader().
456 static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
457
458 /// Returns the header and latch of the outermost loop of \p Plan in plain
459 /// CFG form (before regions are formed).
460 static std::pair<VPBasicBlock *, VPBasicBlock *>
461 getPlainCFGHeaderAndLatch(const VPlan &Plan);
462
463 /// Returns the middle block of \p Plan in plain CFG form (before regions
464 /// are formed).
465 static VPBasicBlock *getPlainCFGMiddleBlock(const VPlan &Plan);
466};
467
468} // namespace llvm
469
470#endif
471