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/// Collect the header mask with the pattern:
149/// (ICMP_ULE, WideCanonicalIV, backedge-taken-count)
150/// TODO: Introduce explicit recipe for header-mask instead of searching
151/// the header-mask pattern manually.
152VPSingleDefRecipe *findHeaderMask(VPlan &Plan);
153
154} // namespace vputils
155
156//===----------------------------------------------------------------------===//
157// Utilities for modifying predecessors and successors of VPlan blocks.
158//===----------------------------------------------------------------------===//
159
160/// Class that provides utilities for VPBlockBases in VPlan.
161class VPBlockUtils {
162public:
163 VPBlockUtils() = delete;
164
165 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
166 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
167 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
168 /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
169 /// have neither successors nor predecessors.
170 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
171 assert(NewBlock->getSuccessors().empty() &&
172 NewBlock->getPredecessors().empty() &&
173 "Can't insert new block with predecessors or successors.");
174 NewBlock->setParent(BlockPtr->getParent());
175 transferSuccessors(Old: BlockPtr, New: NewBlock);
176 connectBlocks(From: BlockPtr, To: NewBlock);
177 }
178
179 /// Insert disconnected block \p NewBlock before \p Blockptr. First
180 /// disconnects all predecessors of \p BlockPtr and connects them to \p
181 /// NewBlock. Add \p NewBlock as predecessor of \p BlockPtr and \p BlockPtr as
182 /// successor of \p NewBlock.
183 static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
184 assert(NewBlock->getSuccessors().empty() &&
185 NewBlock->getPredecessors().empty() &&
186 "Can't insert new block with predecessors or successors.");
187 NewBlock->setParent(BlockPtr->getParent());
188 for (VPBlockBase *Pred : to_vector(Range: BlockPtr->predecessors())) {
189 Pred->replaceSuccessor(Old: BlockPtr, New: NewBlock);
190 NewBlock->appendPredecessor(Predecessor: Pred);
191 }
192 BlockPtr->clearPredecessors();
193 connectBlocks(From: NewBlock, To: BlockPtr);
194 }
195
196 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
197 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
198 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
199 /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
200 /// and \p IfTrue and \p IfFalse must have neither successors nor
201 /// predecessors.
202 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
203 VPBlockBase *BlockPtr) {
204 assert(IfTrue->getSuccessors().empty() &&
205 "Can't insert IfTrue with successors.");
206 assert(IfFalse->getSuccessors().empty() &&
207 "Can't insert IfFalse with successors.");
208 BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
209 IfTrue->setPredecessors({BlockPtr});
210 IfFalse->setPredecessors({BlockPtr});
211 IfTrue->setParent(BlockPtr->getParent());
212 IfFalse->setParent(BlockPtr->getParent());
213 }
214
215 /// Connect VPBlockBases \p From and \p To bi-directionally. If \p PredIdx is
216 /// -1, append \p From to the predecessors of \p To, otherwise set \p To's
217 /// predecessor at \p PredIdx to \p From. If \p SuccIdx is -1, append \p To to
218 /// the successors of \p From, otherwise set \p From's successor at \p SuccIdx
219 /// to \p To. Both VPBlockBases must have the same parent, which can be null.
220 /// Both VPBlockBases can be already connected to other VPBlockBases.
221 static void connectBlocks(VPBlockBase *From, VPBlockBase *To,
222 unsigned PredIdx = -1u, unsigned SuccIdx = -1u) {
223 assert((From->getParent() == To->getParent()) &&
224 "Can't connect two block with different parents");
225
226 if (SuccIdx == -1u)
227 From->appendSuccessor(Successor: To);
228 else
229 From->getSuccessors()[SuccIdx] = To;
230
231 if (PredIdx == -1u)
232 To->appendPredecessor(Predecessor: From);
233 else
234 To->getPredecessors()[PredIdx] = From;
235 }
236
237 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
238 /// from the successors of \p From and \p From from the predecessors of \p To.
239 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
240 assert(To && "Successor to disconnect is null.");
241 From->removeSuccessor(Successor: To);
242 To->removePredecessor(Predecessor: From);
243 }
244
245 /// Reassociate all the blocks connected to \p Old so that they now point to
246 /// \p New.
247 static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {
248 for (auto *Pred : to_vector(Range&: Old->getPredecessors()))
249 Pred->replaceSuccessor(Old, New);
250 for (auto *Succ : to_vector(Range&: Old->getSuccessors()))
251 Succ->replacePredecessor(Old, New);
252 New->setPredecessors(Old->getPredecessors());
253 New->setSuccessors(Old->getSuccessors());
254 Old->clearPredecessors();
255 Old->clearSuccessors();
256 }
257
258 /// Transfer successors from \p Old to \p New. \p New must have no successors.
259 static void transferSuccessors(VPBlockBase *Old, VPBlockBase *New) {
260 for (auto *Succ : Old->getSuccessors())
261 Succ->replacePredecessor(Old, New);
262 New->setSuccessors(Old->getSuccessors());
263 Old->clearSuccessors();
264 }
265
266 /// Return an iterator range over \p Range which only includes \p BlockTy
267 /// blocks. The accesses are casted to \p BlockTy.
268 template <typename BlockTy, typename T>
269 static auto blocksOnly(const T &Range) {
270 // Create BaseTy with correct const-ness based on BlockTy.
271 using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
272 const VPBlockBase, VPBlockBase>;
273
274 // We need to first create an iterator range over (const) BlocktTy & instead
275 // of (const) BlockTy * for filter_range to work properly.
276 auto Mapped =
277 map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });
278 auto Filter = make_filter_range(
279 Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });
280 return map_range(Filter, [](BaseTy &Block) -> BlockTy * {
281 return cast<BlockTy>(&Block);
282 });
283 }
284
285 /// Inserts \p BlockPtr on the edge between \p From and \p To. That is, update
286 /// \p From's successor to \p To to point to \p BlockPtr and \p To's
287 /// predecessor from \p From to \p BlockPtr. \p From and \p To are added to \p
288 /// BlockPtr's predecessors and successors respectively. There must be a
289 /// single edge between \p From and \p To.
290 static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,
291 VPBlockBase *BlockPtr) {
292 unsigned SuccIdx = From->getIndexForSuccessor(Succ: To);
293 unsigned PredIx = To->getIndexForPredecessor(Pred: From);
294 VPBlockUtils::connectBlocks(From, To: BlockPtr, PredIdx: -1, SuccIdx);
295 VPBlockUtils::connectBlocks(From: BlockPtr, To, PredIdx: PredIx, SuccIdx: -1);
296 }
297
298 /// Returns true if \p VPB is a loop header, based on regions or \p VPDT in
299 /// their absence.
300 static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
301
302 /// Returns true if \p VPB is a loop latch, using isHeader().
303 static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
304};
305
306} // namespace llvm
307
308#endif
309