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
14 namespace llvm {
15 class ScalarEvolution;
16 class SCEV;
17 } // namespace llvm
18
19 namespace llvm {
20
21 namespace vputils {
22 /// Returns true if only the first lane of \p Def is used.
23 bool onlyFirstLaneUsed(const VPValue *Def);
24
25 /// Returns true if only the first part of \p Def is used.
26 bool 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.
33 VPValue *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.
38 const 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.
isSingleScalar(const VPValue * VPV)42 inline 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>(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(Rep->operands(), isSingleScalar));
71 }
72 if (isa<VPWidenGEPRecipe, VPDerivedIVRecipe, VPBlendRecipe,
73 VPWidenSelectRecipe>(VPV))
74 return all_of(VPV->getDefiningRecipe()->operands(), isSingleScalar);
75 if (auto *WidenR = dyn_cast<VPWidenRecipe>(VPV)) {
76 return PreservesUniformity(WidenR->getOpcode()) &&
77 all_of(WidenR->operands(), isSingleScalar);
78 }
79 if (auto *VPI = dyn_cast<VPInstruction>(VPV))
80 return VPI->isSingleScalar() || VPI->isVectorToScalar() ||
81 (PreservesUniformity(VPI->getOpcode()) &&
82 all_of(VPI->operands(), isSingleScalar));
83
84 // VPExpandSCEVRecipes must be placed in the entry and are alway uniform.
85 return isa<VPExpandSCEVRecipe>(VPV);
86 }
87
88 /// Return true if \p V is a header mask in \p Plan.
89 bool 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).
95 bool isUniformAcrossVFsAndUFs(VPValue *V);
96
97 /// Returns the header block of the first, top-level loop, or null if none
98 /// exist.
99 VPBasicBlock *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.
107 class VPBlockUtils {
108 public:
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.
insertBlockAfter(VPBlockBase * NewBlock,VPBlockBase * BlockPtr)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(BlockPtr, NewBlock);
124 NewBlock->appendSuccessor(Succ);
125 }
126 BlockPtr->clearSuccessors();
127 connectBlocks(BlockPtr, 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.
insertBlockBefore(VPBlockBase * NewBlock,VPBlockBase * BlockPtr)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(BlockPtr->predecessors())) {
140 Pred->replaceSuccessor(BlockPtr, NewBlock);
141 NewBlock->appendPredecessor(Pred);
142 }
143 BlockPtr->clearPredecessors();
144 connectBlocks(NewBlock, 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.
insertTwoBlocksAfter(VPBlockBase * IfTrue,VPBlockBase * IfFalse,VPBlockBase * BlockPtr)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(To);
180 else
181 From->getSuccessors()[SuccIdx] = To;
182
183 if (PredIdx == -1u)
184 To->appendPredecessor(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.
disconnectBlocks(VPBlockBase * From,VPBlockBase * To)191 static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To) {
192 assert(To && "Successor to disconnect is null.");
193 From->removeSuccessor(To);
194 To->removePredecessor(From);
195 }
196
197 /// Reassociate all the blocks connected to \p Old so that they now point to
198 /// \p New.
reassociateBlocks(VPBlockBase * Old,VPBlockBase * New)199 static void reassociateBlocks(VPBlockBase *Old, VPBlockBase *New) {
200 for (auto *Pred : to_vector(Old->getPredecessors()))
201 Pred->replaceSuccessor(Old, New);
202 for (auto *Succ : to_vector(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>
blocksOnly(const T & Range)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.
insertOnEdge(VPBlockBase * From,VPBlockBase * To,VPBlockBase * BlockPtr)234 static void insertOnEdge(VPBlockBase *From, VPBlockBase *To,
235 VPBlockBase *BlockPtr) {
236 unsigned SuccIdx = From->getIndexForSuccessor(To);
237 unsigned PredIx = To->getIndexForPredecessor(From);
238 VPBlockUtils::connectBlocks(From, BlockPtr, -1, SuccIdx);
239 VPBlockUtils::connectBlocks(BlockPtr, To, PredIx, -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