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 "VPlanPatternMatch.h"
14#include "llvm/Support/Compiler.h"
15
16namespace llvm {
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/// Return true if \p V is a header mask in \p Plan.
59bool isHeaderMask(const VPValue *V, const VPlan &Plan);
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 operand is known to be uniform across all VFs and UFs (e.g.
64/// VPDerivedIV or VPCanonicalIVPHI).
65bool isUniformAcrossVFsAndUFs(VPValue *V);
66
67/// Returns the header block of the first, top-level loop, or null if none
68/// exist.
69VPBasicBlock *getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT);
70
71/// Get the VF scaling factor applied to the recipe's output, if the recipe has
72/// one.
73unsigned getVFScaleFactor(VPRecipeBase *R);
74
75/// Returns the VPValue representing the uncountable exit comparison used by
76/// AnyOf if the recipes it depends on can be traced back to live-ins and
77/// the addresses (in GEP/PtrAdd form) of any (non-masked) load used in
78/// generating the values for the comparison. The recipes are stored in
79/// \p Recipes, and recipes forming an address for a load are also added to
80/// \p GEPs.
81LLVM_ABI_FOR_TEST
82std::optional<VPValue *>
83getRecipesForUncountableExit(VPlan &Plan,
84 SmallVectorImpl<VPRecipeBase *> &Recipes,
85 SmallVectorImpl<VPRecipeBase *> &GEPs);
86
87/// Return a MemoryLocation for \p R with noalias metadata populated from
88/// \p R, if the recipe is supported and std::nullopt otherwise. The pointer of
89/// the location is conservatively set to nullptr.
90std::optional<MemoryLocation> getMemoryLocation(const VPRecipeBase &R);
91
92/// Extracts and returns NoWrap and FastMath flags from the induction binop in
93/// \p ID.
94inline VPIRFlags getFlagsFromIndDesc(const InductionDescriptor &ID) {
95 if (ID.getKind() == InductionDescriptor::IK_FpInduction)
96 return ID.getInductionBinOp()->getFastMathFlags();
97
98 if (auto *OBO = dyn_cast_if_present<OverflowingBinaryOperator>(
99 Val: ID.getInductionBinOp()))
100 return VPIRFlags::WrapFlagsTy(OBO->hasNoUnsignedWrap(),
101 OBO->hasNoSignedWrap());
102
103 assert(ID.getKind() == InductionDescriptor::IK_IntInduction &&
104 "Expected int induction");
105 return VPIRFlags::WrapFlagsTy(false, false);
106}
107
108/// Search \p Start's users for a recipe satisfying \p Pred, looking through
109/// recipes with definitions.
110template <typename PredT>
111inline VPRecipeBase *findRecipe(VPValue *Start, PredT Pred) {
112 SetVector<VPValue *> Worklist;
113 Worklist.insert(X: Start);
114 for (unsigned I = 0; I != Worklist.size(); ++I) {
115 VPValue *Cur = Worklist[I];
116 auto *R = Cur->getDefiningRecipe();
117 if (!R)
118 continue;
119 if (Pred(R))
120 return R;
121 for (VPUser *U : Cur->users()) {
122 for (VPValue *V : cast<VPRecipeBase>(Val: U)->definedValues())
123 Worklist.insert(X: V);
124 }
125 }
126 return nullptr;
127}
128
129/// If \p V is used by a recipe matching pattern \p P, return it. Otherwise
130/// return nullptr;
131template <typename MatchT>
132static VPRecipeBase *findUserOf(VPValue *V, const MatchT &P) {
133 auto It = find_if(V->users(), match_fn(P));
134 return It == V->user_end() ? nullptr : cast<VPRecipeBase>(*It);
135}
136
137/// If \p V is used by a VPInstruction with \p Opcode, return it. Otherwise
138/// return nullptr.
139template <unsigned Opcode> static VPInstruction *findUserOf(VPValue *V) {
140 using namespace llvm::VPlanPatternMatch;
141 return cast_or_null<VPInstruction>(findUserOf(V, m_VPInstruction<Opcode>()));
142}
143
144/// Find the ComputeReductionResult recipe for \p PhiR, looking through selects
145/// inserted for predicated reductions or tail folding.
146VPInstruction *findComputeReductionResult(VPReductionPHIRecipe *PhiR);
147
148} // namespace vputils
149
150//===----------------------------------------------------------------------===//
151// Utilities for modifying predecessors and successors of VPlan blocks.
152//===----------------------------------------------------------------------===//
153
154/// Class that provides utilities for VPBlockBases in VPlan.
155class VPBlockUtils {
156public:
157 VPBlockUtils() = delete;
158
159 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
160 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
161 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
162 /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
163 /// have neither successors nor predecessors.
164 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
165 assert(NewBlock->getSuccessors().empty() &&
166 NewBlock->getPredecessors().empty() &&
167 "Can't insert new block with predecessors or successors.");
168 NewBlock->setParent(BlockPtr->getParent());
169 transferSuccessors(Old: BlockPtr, New: NewBlock);
170 connectBlocks(From: BlockPtr, To: NewBlock);
171 }
172
173 /// Insert disconnected block \p NewBlock before \p Blockptr. First
174 /// disconnects all predecessors of \p BlockPtr and connects them to \p
175 /// NewBlock. Add \p NewBlock as predecessor of \p BlockPtr and \p BlockPtr as
176 /// successor of \p NewBlock.
177 static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
178 assert(NewBlock->getSuccessors().empty() &&
179 NewBlock->getPredecessors().empty() &&
180 "Can't insert new block with predecessors or successors.");
181 NewBlock->setParent(BlockPtr->getParent());
182 for (VPBlockBase *Pred : to_vector(Range: BlockPtr->predecessors())) {
183 Pred->replaceSuccessor(Old: BlockPtr, New: NewBlock);
184 NewBlock->appendPredecessor(Predecessor: Pred);
185 }
186 BlockPtr->clearPredecessors();
187 connectBlocks(From: NewBlock, To: BlockPtr);
188 }
189
190 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
191 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
192 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
193 /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
194 /// and \p IfTrue and \p IfFalse must have neither successors nor
195 /// predecessors.
196 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
197 VPBlockBase *BlockPtr) {
198 assert(IfTrue->getSuccessors().empty() &&
199 "Can't insert IfTrue with successors.");
200 assert(IfFalse->getSuccessors().empty() &&
201 "Can't insert IfFalse with successors.");
202 BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
203 IfTrue->setPredecessors({BlockPtr});
204 IfFalse->setPredecessors({BlockPtr});
205 IfTrue->setParent(BlockPtr->getParent());
206 IfFalse->setParent(BlockPtr->getParent());
207 }
208
209 /// Connect VPBlockBases \p From and \p To bi-directionally. If \p PredIdx is
210 /// -1, append \p From to the predecessors of \p To, otherwise set \p To's
211 /// predecessor at \p PredIdx to \p From. If \p SuccIdx is -1, append \p To to
212 /// the successors of \p From, otherwise set \p From's successor at \p SuccIdx
213 /// to \p To. Both VPBlockBases must have the same parent, which can be null.
214 /// Both VPBlockBases can be already connected to other VPBlockBases.
215 static void connectBlocks(VPBlockBase *From, VPBlockBase *To,
216 unsigned PredIdx = -1u, unsigned SuccIdx = -1u) {
217 assert((From->getParent() == To->getParent()) &&
218 "Can't connect two block with different parents");
219
220 if (SuccIdx == -1u)
221 From->appendSuccessor(Successor: To);
222 else
223 From->getSuccessors()[SuccIdx] = To;
224
225 if (PredIdx == -1u)
226 To->appendPredecessor(Predecessor: From);
227 else
228 To->getPredecessors()[PredIdx] = From;
229 }
230
231 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
232 /// from the successors of \p From and \p From from the predecessors of \p To.
233 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
234 assert(To && "Successor to disconnect is null.");
235 From->removeSuccessor(Successor: To);
236 To->removePredecessor(Predecessor: From);
237 }
238
239 /// Reassociate all the blocks connected to \p Old so that they now point to
240 /// \p New.
241 static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {
242 for (auto *Pred : to_vector(Range&: Old->getPredecessors()))
243 Pred->replaceSuccessor(Old, New);
244 for (auto *Succ : to_vector(Range&: Old->getSuccessors()))
245 Succ->replacePredecessor(Old, New);
246 New->setPredecessors(Old->getPredecessors());
247 New->setSuccessors(Old->getSuccessors());
248 Old->clearPredecessors();
249 Old->clearSuccessors();
250 }
251
252 /// Transfer successors from \p Old to \p New. \p New must have no successors.
253 static void transferSuccessors(VPBlockBase *Old, VPBlockBase *New) {
254 for (auto *Succ : Old->getSuccessors())
255 Succ->replacePredecessor(Old, New);
256 New->setSuccessors(Old->getSuccessors());
257 Old->clearSuccessors();
258 }
259
260 /// Return an iterator range over \p Range which only includes \p BlockTy
261 /// blocks. The accesses are casted to \p BlockTy.
262 template <typename BlockTy, typename T>
263 static auto blocksOnly(const T &Range) {
264 // Create BaseTy with correct const-ness based on BlockTy.
265 using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
266 const VPBlockBase, VPBlockBase>;
267
268 // We need to first create an iterator range over (const) BlocktTy & instead
269 // of (const) BlockTy * for filter_range to work properly.
270 auto Mapped =
271 map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });
272 auto Filter = make_filter_range(
273 Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });
274 return map_range(Filter, [](BaseTy &Block) -> BlockTy * {
275 return cast<BlockTy>(&Block);
276 });
277 }
278
279 /// Inserts \p BlockPtr on the edge between \p From and \p To. That is, update
280 /// \p From's successor to \p To to point to \p BlockPtr and \p To's
281 /// predecessor from \p From to \p BlockPtr. \p From and \p To are added to \p
282 /// BlockPtr's predecessors and successors respectively. There must be a
283 /// single edge between \p From and \p To.
284 static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,
285 VPBlockBase *BlockPtr) {
286 unsigned SuccIdx = From->getIndexForSuccessor(Succ: To);
287 unsigned PredIx = To->getIndexForPredecessor(Pred: From);
288 VPBlockUtils::connectBlocks(From, To: BlockPtr, PredIdx: -1, SuccIdx);
289 VPBlockUtils::connectBlocks(From: BlockPtr, To, PredIdx: PredIx, SuccIdx: -1);
290 }
291
292 /// Returns true if \p VPB is a loop header, based on regions or \p VPDT in
293 /// their absence.
294 static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
295
296 /// Returns true if \p VPB is a loop latch, using isHeader().
297 static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
298};
299
300} // namespace llvm
301
302#endif
303