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