1//===------ VirtualInstruction.cpp ------------------------------*- 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// Tools for determining which instructions are within a statement and the
10// nature of their operands.
11//
12//===----------------------------------------------------------------------===//
13
14#include "polly/Support/VirtualInstruction.h"
15
16using namespace polly;
17using namespace llvm;
18
19VirtualUse VirtualUse::create(Scop *S, const Use &U, LoopInfo *LI,
20 bool Virtual) {
21 auto *UserBB = getUseBlock(U);
22 Loop *UserScope = LI->getLoopFor(BB: UserBB);
23 Instruction *UI = dyn_cast<Instruction>(Val: U.getUser());
24 ScopStmt *UserStmt = S->getStmtFor(Inst: UI);
25
26 // Uses by PHI nodes are always reading values written by other statements,
27 // except it is within a region statement.
28 if (PHINode *PHI = dyn_cast<PHINode>(Val: UI)) {
29 // Handle PHI in exit block.
30 if (S->getRegion().getExit() == PHI->getParent())
31 return VirtualUse(UserStmt, U.get(), Inter, nullptr, nullptr);
32
33 if (UserStmt->getEntryBlock() != PHI->getParent())
34 return VirtualUse(UserStmt, U.get(), Intra, nullptr, nullptr);
35
36 // The MemoryAccess is expected to be set if @p Virtual is true.
37 MemoryAccess *IncomingMA = nullptr;
38 if (Virtual) {
39 if (const ScopArrayInfo *SAI =
40 S->getScopArrayInfoOrNull(BasePtr: PHI, Kind: MemoryKind::PHI)) {
41 IncomingMA = S->getPHIRead(SAI);
42 assert(IncomingMA->getStatement() == UserStmt);
43 }
44 }
45
46 return VirtualUse(UserStmt, U.get(), Inter, nullptr, IncomingMA);
47 }
48
49 return create(S, UserStmt, UserScope, Val: U.get(), Virtual);
50}
51
52VirtualUse VirtualUse::create(Scop *S, ScopStmt *UserStmt, Loop *UserScope,
53 Value *Val, bool Virtual) {
54 assert(!isa<StoreInst>(Val) && "a StoreInst cannot be used");
55
56 if (isa<BasicBlock>(Val))
57 return VirtualUse(UserStmt, Val, Block, nullptr, nullptr);
58
59 if (isa<llvm::Constant>(Val) || isa<MetadataAsValue>(Val) ||
60 isa<InlineAsm>(Val))
61 return VirtualUse(UserStmt, Val, Constant, nullptr, nullptr);
62
63 // Is the value synthesizable? If the user has been pruned
64 // (UserStmt == nullptr), it is either not used anywhere or is synthesizable.
65 // We assume synthesizable which practically should have the same effect.
66 auto *SE = S->getSE();
67 if (SE->isSCEVable(Ty: Val->getType())) {
68 const SCEV *ScevExpr = SE->getSCEVAtScope(V: Val, L: UserScope);
69 if (!UserStmt || canSynthesize(V: Val, S: *UserStmt->getParent(), SE, Scope: UserScope))
70 return VirtualUse(UserStmt, Val, Synthesizable, ScevExpr, nullptr);
71 }
72
73 // FIXME: Inconsistency between lookupInvariantEquivClass and
74 // getRequiredInvariantLoads. Querying one of them should be enough.
75 auto &RIL = S->getRequiredInvariantLoads();
76 if (S->lookupInvariantEquivClass(Val) || RIL.count(key: dyn_cast<LoadInst>(Val)))
77 return VirtualUse(UserStmt, Val, Hoisted, nullptr, nullptr);
78
79 // ReadOnly uses may have MemoryAccesses that we want to associate with the
80 // use. This is why we look for a MemoryAccess here already.
81 MemoryAccess *InputMA = nullptr;
82 if (UserStmt && Virtual)
83 InputMA = UserStmt->lookupValueReadOf(Inst: Val);
84
85 // Uses are read-only if they have been defined before the SCoP, i.e., they
86 // cannot be written to inside the SCoP. Arguments are defined before any
87 // instructions, hence also before the SCoP. If the user has been pruned
88 // (UserStmt == nullptr) and is not SCEVable, assume it is read-only as it is
89 // neither an intra- nor an inter-use.
90 if (!UserStmt || isa<Argument>(Val))
91 return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
92
93 auto Inst = cast<Instruction>(Val);
94 if (!S->contains(I: Inst))
95 return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
96
97 // A use is inter-statement if either it is defined in another statement, or
98 // there is a MemoryAccess that reads its value that has been written by
99 // another statement.
100 if (InputMA || (!Virtual && UserStmt != S->getStmtFor(Inst)))
101 return VirtualUse(UserStmt, Val, Inter, nullptr, InputMA);
102
103 return VirtualUse(UserStmt, Val, Intra, nullptr, nullptr);
104}
105
106void VirtualUse::print(raw_ostream &OS, bool Reproducible) const {
107 OS << "User: [" << User->getBaseName() << "] ";
108 switch (Kind) {
109 case VirtualUse::Constant:
110 OS << "Constant Op:";
111 break;
112 case VirtualUse::Block:
113 OS << "BasicBlock Op:";
114 break;
115 case VirtualUse::Synthesizable:
116 OS << "Synthesizable Op:";
117 break;
118 case VirtualUse::Hoisted:
119 OS << "Hoisted load Op:";
120 break;
121 case VirtualUse::ReadOnly:
122 OS << "Read-Only Op:";
123 break;
124 case VirtualUse::Intra:
125 OS << "Intra Op:";
126 break;
127 case VirtualUse::Inter:
128 OS << "Inter Op:";
129 break;
130 }
131
132 if (Val) {
133 OS << ' ';
134 if (Reproducible)
135 OS << '"' << Val->getName() << '"';
136 else
137 Val->print(O&: OS, IsForDebug: true);
138 }
139 if (ScevExpr) {
140 OS << ' ';
141 ScevExpr->print(OS);
142 }
143 if (InputMA && !Reproducible)
144 OS << ' ' << InputMA;
145}
146
147#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
148LLVM_DUMP_METHOD void VirtualUse::dump() const {
149 print(OS&: errs(), Reproducible: false);
150 errs() << '\n';
151}
152#endif
153
154void VirtualInstruction::print(raw_ostream &OS, bool Reproducible) const {
155 if (!Stmt || !Inst) {
156 OS << "[null VirtualInstruction]";
157 return;
158 }
159
160 OS << "[" << Stmt->getBaseName() << "]";
161 Inst->print(O&: OS, IsForDebug: !Reproducible);
162}
163
164#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
165LLVM_DUMP_METHOD void VirtualInstruction::dump() const {
166 print(OS&: errs(), Reproducible: false);
167 errs() << '\n';
168}
169#endif
170
171/// Return true if @p Inst cannot be removed, even if it is nowhere referenced.
172static bool isRoot(const Instruction *Inst) {
173 // The store is handled by its MemoryAccess. The load must be reached from the
174 // roots in order to be marked as used.
175 if (isa<LoadInst>(Val: Inst) || isa<StoreInst>(Val: Inst))
176 return false;
177
178 // Terminator instructions (in region statements) are required for control
179 // flow.
180 if (Inst->isTerminator())
181 return true;
182
183 // Writes to memory must be honored.
184 if (Inst->mayWriteToMemory())
185 return true;
186
187 return false;
188}
189
190/// Return true for MemoryAccesses that cannot be removed because it represents
191/// an llvm::Value that is used after the SCoP.
192static bool isEscaping(MemoryAccess *MA) {
193 assert(MA->isOriginalValueKind());
194 Scop *S = MA->getStatement()->getParent();
195 return S->isEscaping(Inst: cast<Instruction>(Val: MA->getAccessValue()));
196}
197
198/// Add non-removable virtual instructions in @p Stmt to @p RootInsts.
199static void
200addInstructionRoots(ScopStmt *Stmt,
201 SmallVectorImpl<VirtualInstruction> &RootInsts) {
202 if (!Stmt->isBlockStmt()) {
203 // In region statements the terminator statement and all statements that
204 // are not in the entry block cannot be eliminated and consequently must
205 // be roots.
206 RootInsts.emplace_back(Args&: Stmt,
207 Args: Stmt->getRegion()->getEntry()->getTerminator());
208 for (BasicBlock *BB : Stmt->getRegion()->blocks())
209 if (Stmt->getRegion()->getEntry() != BB)
210 for (Instruction &Inst : *BB)
211 RootInsts.emplace_back(Args&: Stmt, Args: &Inst);
212 return;
213 }
214
215 for (Instruction *Inst : Stmt->getInstructions())
216 if (isRoot(Inst))
217 RootInsts.emplace_back(Args&: Stmt, Args&: Inst);
218}
219
220/// Add non-removable memory accesses in @p Stmt to @p RootInsts.
221///
222/// @param Local If true, all writes are assumed to escape. markAndSweep
223/// algorithms can use this to be applicable to a single ScopStmt only without
224/// the risk of removing definitions required by other statements.
225/// If false, only writes for SCoP-escaping values are roots. This
226/// is global mode, where such writes must be marked by theirs uses
227/// in order to be reachable.
228static void addAccessRoots(ScopStmt *Stmt,
229 SmallVectorImpl<MemoryAccess *> &RootAccs,
230 bool Local) {
231 for (auto *MA : *Stmt) {
232 if (!MA->isWrite())
233 continue;
234
235 // Writes to arrays are always used.
236 if (MA->isLatestArrayKind())
237 RootAccs.push_back(Elt: MA);
238
239 // Values are roots if they are escaping.
240 else if (MA->isLatestValueKind()) {
241 if (Local || isEscaping(MA))
242 RootAccs.push_back(Elt: MA);
243 }
244
245 // Exit phis are, by definition, escaping.
246 else if (MA->isLatestExitPHIKind())
247 RootAccs.push_back(Elt: MA);
248
249 // phi writes are only roots if we are not visiting the statement
250 // containing the PHINode.
251 else if (Local && MA->isLatestPHIKind())
252 RootAccs.push_back(Elt: MA);
253 }
254}
255
256/// Determine all instruction and access roots.
257static void addRoots(ScopStmt *Stmt,
258 SmallVectorImpl<VirtualInstruction> &RootInsts,
259 SmallVectorImpl<MemoryAccess *> &RootAccs, bool Local) {
260 addInstructionRoots(Stmt, RootInsts);
261 addAccessRoots(Stmt, RootAccs, Local);
262}
263
264/// Mark accesses and instructions as used if they are reachable from a root,
265/// walking the operand trees.
266///
267/// @param S The SCoP to walk.
268/// @param LI The LoopInfo Analysis.
269/// @param RootInsts List of root instructions.
270/// @param RootAccs List of root accesses.
271/// @param UsesInsts[out] Receives all reachable instructions, including the
272/// roots.
273/// @param UsedAccs[out] Receives all reachable accesses, including the roots.
274/// @param OnlyLocal If non-nullptr, restricts walking to a single
275/// statement.
276static void walkReachable(Scop *S, LoopInfo *LI,
277 ArrayRef<VirtualInstruction> RootInsts,
278 ArrayRef<MemoryAccess *> RootAccs,
279 DenseSet<VirtualInstruction> &UsedInsts,
280 DenseSet<MemoryAccess *> &UsedAccs,
281 ScopStmt *OnlyLocal = nullptr) {
282 UsedInsts.clear();
283 UsedAccs.clear();
284
285 SmallVector<VirtualInstruction, 32> WorklistInsts;
286 SmallVector<MemoryAccess *, 32> WorklistAccs;
287
288 WorklistInsts.append(in_start: RootInsts.begin(), in_end: RootInsts.end());
289 WorklistAccs.append(in_start: RootAccs.begin(), in_end: RootAccs.end());
290
291 auto AddToWorklist = [&](VirtualUse VUse) {
292 switch (VUse.getKind()) {
293 case VirtualUse::Block:
294 case VirtualUse::Constant:
295 case VirtualUse::Synthesizable:
296 case VirtualUse::Hoisted:
297 break;
298 case VirtualUse::ReadOnly:
299 // Read-only scalars only have MemoryAccesses if ModelReadOnlyScalars is
300 // enabled.
301 if (!VUse.getMemoryAccess())
302 break;
303 [[fallthrough]];
304 case VirtualUse::Inter:
305 assert(VUse.getMemoryAccess());
306 WorklistAccs.push_back(Elt: VUse.getMemoryAccess());
307 break;
308 case VirtualUse::Intra:
309 WorklistInsts.emplace_back(Args: VUse.getUser(),
310 Args: cast<Instruction>(Val: VUse.getValue()));
311 break;
312 }
313 };
314
315 while (true) {
316 // We have two worklists to process: Only when the MemoryAccess worklist is
317 // empty, we process the instruction worklist.
318
319 while (!WorklistAccs.empty()) {
320 auto *Acc = WorklistAccs.pop_back_val();
321
322 ScopStmt *Stmt = Acc->getStatement();
323 if (OnlyLocal && Stmt != OnlyLocal)
324 continue;
325
326 auto Inserted = UsedAccs.insert(V: Acc);
327 if (!Inserted.second)
328 continue;
329
330 if (Acc->isRead()) {
331 const ScopArrayInfo *SAI = Acc->getScopArrayInfo();
332
333 if (Acc->isLatestValueKind()) {
334 MemoryAccess *DefAcc = S->getValueDef(SAI);
335
336 // Accesses to read-only values do not have a definition.
337 if (DefAcc)
338 WorklistAccs.push_back(Elt: S->getValueDef(SAI));
339 }
340
341 if (Acc->isLatestAnyPHIKind()) {
342 auto IncomingMAs = S->getPHIIncomings(SAI);
343 WorklistAccs.append(in_start: IncomingMAs.begin(), in_end: IncomingMAs.end());
344 }
345 }
346
347 if (Acc->isWrite()) {
348 if (Acc->isOriginalValueKind() ||
349 (Acc->isOriginalArrayKind() && Acc->getAccessValue())) {
350 Loop *Scope = Stmt->getSurroundingLoop();
351 VirtualUse VUse =
352 VirtualUse::create(S, UserStmt: Stmt, UserScope: Scope, Val: Acc->getAccessValue(), Virtual: true);
353 AddToWorklist(VUse);
354 }
355
356 if (Acc->isOriginalAnyPHIKind()) {
357 for (auto Incoming : Acc->getIncoming()) {
358 VirtualUse VUse = VirtualUse::create(
359 S, UserStmt: Stmt, UserScope: LI->getLoopFor(BB: Incoming.first), Val: Incoming.second, Virtual: true);
360 AddToWorklist(VUse);
361 }
362 }
363
364 if (Acc->isOriginalArrayKind())
365 WorklistInsts.emplace_back(Args&: Stmt, Args: Acc->getAccessInstruction());
366 }
367 }
368
369 // If both worklists are empty, stop walking.
370 if (WorklistInsts.empty())
371 break;
372
373 VirtualInstruction VInst = WorklistInsts.pop_back_val();
374 ScopStmt *Stmt = VInst.getStmt();
375 Instruction *Inst = VInst.getInstruction();
376
377 // Do not process statements other than the local.
378 if (OnlyLocal && Stmt != OnlyLocal)
379 continue;
380
381 auto InsertResult = UsedInsts.insert(V: VInst);
382 if (!InsertResult.second)
383 continue;
384
385 // Add all operands to the worklists.
386 PHINode *PHI = dyn_cast<PHINode>(Val: Inst);
387 if (PHI && PHI->getParent() == Stmt->getEntryBlock()) {
388 if (MemoryAccess *PHIRead = Stmt->lookupPHIReadOf(PHI))
389 WorklistAccs.push_back(Elt: PHIRead);
390 } else {
391 for (VirtualUse VUse : VInst.operands())
392 AddToWorklist(VUse);
393 }
394
395 // If there is an array access, also add its MemoryAccesses to the worklist.
396 const MemoryAccessList *Accs = Stmt->lookupArrayAccessesFor(Inst);
397 if (!Accs)
398 continue;
399
400 for (MemoryAccess *Acc : *Accs)
401 WorklistAccs.push_back(Elt: Acc);
402 }
403}
404
405void polly::markReachable(Scop *S, LoopInfo *LI,
406 DenseSet<VirtualInstruction> &UsedInsts,
407 DenseSet<MemoryAccess *> &UsedAccs,
408 ScopStmt *OnlyLocal) {
409 SmallVector<VirtualInstruction, 32> RootInsts;
410 SmallVector<MemoryAccess *, 32> RootAccs;
411
412 if (OnlyLocal) {
413 addRoots(Stmt: OnlyLocal, RootInsts, RootAccs, Local: true);
414 } else {
415 for (auto &Stmt : *S)
416 addRoots(Stmt: &Stmt, RootInsts, RootAccs, Local: false);
417 }
418
419 walkReachable(S, LI, RootInsts, RootAccs, UsedInsts, UsedAccs, OnlyLocal);
420}
421

source code of polly/lib/Support/VirtualInstruction.cpp