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
14namespace llvm {
15class ScalarEvolution;
16class SCEV;
17} // namespace llvm
18
19namespace llvm {
20
21namespace vputils {
22/// Returns true if only the first lane of \p Def is used.
23bool onlyFirstLaneUsed(const VPValue *Def);
24
25/// Returns true if only the first part of \p Def is used.
26bool onlyFirstPartUsed(const VPValue *Def);
27
28/// Get or create a VPValue that corresponds to the expansion of \p Expr. If \p
29/// Expr is a SCEVConstant or SCEVUnknown, return a VPValue wrapping the live-in
30/// value. Otherwise return a VPExpandSCEVRecipe to expand \p Expr. If \p Plan's
31/// pre-header already contains a recipe expanding \p Expr, return it. If not,
32/// create a new one.
33VPValue *getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr,
34 ScalarEvolution &SE);
35
36/// Return the SCEV expression for \p V. Returns SCEVCouldNotCompute if no
37/// SCEV expression could be constructed.
38const SCEV *getSCEVExprForVPValue(VPValue *V, ScalarEvolution &SE);
39
40/// Returns true if \p VPV is a single scalar, either because it produces the
41/// same value for all lanes or only has its first lane used.
42inline bool isSingleScalar(const VPValue *VPV) {
43 auto PreservesUniformity = [](unsigned Opcode) -> bool {
44 if (Instruction::isBinaryOp(Opcode) || Instruction::isCast(Opcode))
45 return true;
46 switch (Opcode) {
47 case Instruction::GetElementPtr:
48 case Instruction::ICmp:
49 case Instruction::FCmp:
50 case VPInstruction::Broadcast:
51 case VPInstruction::PtrAdd:
52 return true;
53 default:
54 return false;
55 }
56 };
57
58 // A live-in must be uniform across the scope of VPlan.
59 if (VPV->isLiveIn())
60 return true;
61
62 if (auto *Rep = dyn_cast<VPReplicateRecipe>(Val: VPV)) {
63 const VPRegionBlock *RegionOfR = Rep->getParent()->getParent();
64 // Don't consider recipes in replicate regions as uniform yet; their first
65 // lane cannot be accessed when executing the replicate region for other
66 // lanes.
67 if (RegionOfR && RegionOfR->isReplicator())
68 return false;
69 return Rep->isSingleScalar() || (PreservesUniformity(Rep->getOpcode()) &&
70 all_of(Range: Rep->operands(), P: isSingleScalar));
71 }
72 if (isa<VPWidenGEPRecipe, VPDerivedIVRecipe, VPBlendRecipe,
73 VPWidenSelectRecipe>(Val: VPV))
74 return all_of(Range: VPV->getDefiningRecipe()->operands(), P: isSingleScalar);
75 if (auto *WidenR = dyn_cast<VPWidenRecipe>(Val: VPV)) {
76 return PreservesUniformity(WidenR->getOpcode()) &&
77 all_of(Range: WidenR->operands(), P: isSingleScalar);
78 }
79 if (auto *VPI = dyn_cast<VPInstruction>(Val: VPV))
80 return VPI->isSingleScalar() || VPI->isVectorToScalar() ||
81 (PreservesUniformity(VPI->getOpcode()) &&
82 all_of(Range: VPI->operands(), P: isSingleScalar));
83
84 // VPExpandSCEVRecipes must be placed in the entry and are alway uniform.
85 return isa<VPExpandSCEVRecipe>(Val: VPV);
86}
87
88/// Return true if \p V is a header mask in \p Plan.
89bool isHeaderMask(const VPValue *V, VPlan &Plan);
90
91/// Checks if \p V is uniform across all VF lanes and UF parts. It is considered
92/// as such if it is either loop invariant (defined outside the vector region)
93/// or its operand is known to be uniform across all VFs and UFs (e.g.
94/// VPDerivedIV or VPCanonicalIVPHI).
95bool isUniformAcrossVFsAndUFs(VPValue *V);
96
97/// Returns the header block of the first, top-level loop, or null if none
98/// exist.
99VPBasicBlock *getFirstLoopHeader(VPlan &Plan, VPDominatorTree &VPDT);
100} // namespace vputils
101
102//===----------------------------------------------------------------------===//
103// Utilities for modifying predecessors and successors of VPlan blocks.
104//===----------------------------------------------------------------------===//
105
106/// Class that provides utilities for VPBlockBases in VPlan.
107class VPBlockUtils {
108public:
109 VPBlockUtils() = delete;
110
111 /// Insert disconnected VPBlockBase \p NewBlock after \p BlockPtr. Add \p
112 /// NewBlock as successor of \p BlockPtr and \p BlockPtr as predecessor of \p
113 /// NewBlock, and propagate \p BlockPtr parent to \p NewBlock. \p BlockPtr's
114 /// successors are moved from \p BlockPtr to \p NewBlock. \p NewBlock must
115 /// have neither successors nor predecessors.
116 static void insertBlockAfter(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
117 assert(NewBlock->getSuccessors().empty() &&
118 NewBlock->getPredecessors().empty() &&
119 "Can't insert new block with predecessors or successors.");
120 NewBlock->setParent(BlockPtr->getParent());
121 SmallVector<VPBlockBase *> Succs(BlockPtr->successors());
122 for (VPBlockBase *Succ : Succs) {
123 Succ->replacePredecessor(Old: BlockPtr, New: NewBlock);
124 NewBlock->appendSuccessor(Successor: Succ);
125 }
126 BlockPtr->clearSuccessors();
127 connectBlocks(From: BlockPtr, To: NewBlock);
128 }
129
130 /// Insert disconnected block \p NewBlock before \p Blockptr. First
131 /// disconnects all predecessors of \p BlockPtr and connects them to \p
132 /// NewBlock. Add \p NewBlock as predecessor of \p BlockPtr and \p BlockPtr as
133 /// successor of \p NewBlock.
134 static void insertBlockBefore(VPBlockBase *NewBlock, VPBlockBase *BlockPtr) {
135 assert(NewBlock->getSuccessors().empty() &&
136 NewBlock->getPredecessors().empty() &&
137 "Can't insert new block with predecessors or successors.");
138 NewBlock->setParent(BlockPtr->getParent());
139 for (VPBlockBase *Pred : to_vector(Range: BlockPtr->predecessors())) {
140 Pred->replaceSuccessor(Old: BlockPtr, New: NewBlock);
141 NewBlock->appendPredecessor(Predecessor: Pred);
142 }
143 BlockPtr->clearPredecessors();
144 connectBlocks(From: NewBlock, To: BlockPtr);
145 }
146
147 /// Insert disconnected VPBlockBases \p IfTrue and \p IfFalse after \p
148 /// BlockPtr. Add \p IfTrue and \p IfFalse as succesors of \p BlockPtr and \p
149 /// BlockPtr as predecessor of \p IfTrue and \p IfFalse. Propagate \p BlockPtr
150 /// parent to \p IfTrue and \p IfFalse. \p BlockPtr must have no successors
151 /// and \p IfTrue and \p IfFalse must have neither successors nor
152 /// predecessors.
153 static void insertTwoBlocksAfter(VPBlockBase *IfTrue, VPBlockBase *IfFalse,
154 VPBlockBase *BlockPtr) {
155 assert(IfTrue->getSuccessors().empty() &&
156 "Can't insert IfTrue with successors.");
157 assert(IfFalse->getSuccessors().empty() &&
158 "Can't insert IfFalse with successors.");
159 BlockPtr->setTwoSuccessors(IfTrue, IfFalse);
160 IfTrue->setPredecessors({BlockPtr});
161 IfFalse->setPredecessors({BlockPtr});
162 IfTrue->setParent(BlockPtr->getParent());
163 IfFalse->setParent(BlockPtr->getParent());
164 }
165
166 /// Connect VPBlockBases \p From and \p To bi-directionally. If \p PredIdx is
167 /// -1, append \p From to the predecessors of \p To, otherwise set \p To's
168 /// predecessor at \p PredIdx to \p From. If \p SuccIdx is -1, append \p To to
169 /// the successors of \p From, otherwise set \p From's successor at \p SuccIdx
170 /// to \p To. Both VPBlockBases must have the same parent, which can be null.
171 /// Both VPBlockBases can be already connected to other VPBlockBases.
172 static void connectBlocks(VPBlockBase *From, VPBlockBase *To,
173 unsigned PredIdx = -1u, unsigned SuccIdx = -1u) {
174 assert((From->getParent() == To->getParent()) &&
175 "Can't connect two block with different parents");
176 assert((SuccIdx != -1u || From->getNumSuccessors() < 2) &&
177 "Blocks can't have more than two successors.");
178 if (SuccIdx == -1u)
179 From->appendSuccessor(Successor: To);
180 else
181 From->getSuccessors()[SuccIdx] = To;
182
183 if (PredIdx == -1u)
184 To->appendPredecessor(Predecessor: From);
185 else
186 To->getPredecessors()[PredIdx] = From;
187 }
188
189 /// Disconnect VPBlockBases \p From and \p To bi-directionally. Remove \p To
190 /// from the successors of \p From and \p From from the predecessors of \p To.
191 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
192 assert(To && "Successor to disconnect is null.");
193 From->removeSuccessor(Successor: To);
194 To->removePredecessor(Predecessor: From);
195 }
196
197 /// Reassociate all the blocks connected to \p Old so that they now point to
198 /// \p New.
199 static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {
200 for (auto *Pred : to_vector(Range&: Old->getPredecessors()))
201 Pred->replaceSuccessor(Old, New);
202 for (auto *Succ : to_vector(Range&: Old->getSuccessors()))
203 Succ->replacePredecessor(Old, New);
204 New->setPredecessors(Old->getPredecessors());
205 New->setSuccessors(Old->getSuccessors());
206 Old->clearPredecessors();
207 Old->clearSuccessors();
208 }
209
210 /// Return an iterator range over \p Range which only includes \p BlockTy
211 /// blocks. The accesses are casted to \p BlockTy.
212 template <typename BlockTy, typename T>
213 static auto blocksOnly(const T &Range) {
214 // Create BaseTy with correct const-ness based on BlockTy.
215 using BaseTy = std::conditional_t<std::is_const<BlockTy>::value,
216 const VPBlockBase, VPBlockBase>;
217
218 // We need to first create an iterator range over (const) BlocktTy & instead
219 // of (const) BlockTy * for filter_range to work properly.
220 auto Mapped =
221 map_range(Range, [](BaseTy *Block) -> BaseTy & { return *Block; });
222 auto Filter = make_filter_range(
223 Mapped, [](BaseTy &Block) { return isa<BlockTy>(&Block); });
224 return map_range(Filter, [](BaseTy &Block) -> BlockTy * {
225 return cast<BlockTy>(&Block);
226 });
227 }
228
229 /// Inserts \p BlockPtr on the edge between \p From and \p To. That is, update
230 /// \p From's successor to \p To to point to \p BlockPtr and \p To's
231 /// predecessor from \p From to \p BlockPtr. \p From and \p To are added to \p
232 /// BlockPtr's predecessors and successors respectively. There must be a
233 /// single edge between \p From and \p To.
234 static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,
235 VPBlockBase *BlockPtr) {
236 unsigned SuccIdx = From->getIndexForSuccessor(Succ: To);
237 unsigned PredIx = To->getIndexForPredecessor(Pred: From);
238 VPBlockUtils::connectBlocks(From, To: BlockPtr, PredIdx: -1, SuccIdx);
239 VPBlockUtils::connectBlocks(From: BlockPtr, To, PredIdx: PredIx, SuccIdx: -1);
240 }
241
242 /// Returns true if \p VPB is a loop header, based on regions or \p VPDT in
243 /// their absence.
244 static bool isHeader(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
245
246 /// Returns true if \p VPB is a loop latch, using isHeader().
247 static bool isLatch(const VPBlockBase *VPB, const VPDominatorTree &VPDT);
248};
249
250} // namespace llvm
251
252#endif
253