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