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