1 //===------ VirtualInstruction.cpp ------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Tools for determining which instructions are within a statement and the
11 // nature of their operands.
13 //===----------------------------------------------------------------------===//
15 #include "polly/Support/VirtualInstruction.h"
16 #include "polly/Support/SCEVValidator.h"
18 using namespace polly
;
21 VirtualUse
VirtualUse ::create(Scop
*S
, const Use
&U
, LoopInfo
*LI
,
23 auto *UserBB
= getUseBlock(U
);
24 auto *UserStmt
= S
->getStmtFor(UserBB
);
25 auto *UserScope
= LI
->getLoopFor(UserBB
);
26 return create(S
, UserStmt
, UserScope
, U
.get(), Virtual
);
29 VirtualUse
VirtualUse::create(Scop
*S
, ScopStmt
*UserStmt
, Loop
*UserScope
,
30 Value
*Val
, bool Virtual
) {
31 assert(!isa
<StoreInst
>(Val
) && "a StoreInst cannot be used");
33 if (isa
<BasicBlock
>(Val
))
34 return VirtualUse(UserStmt
, Val
, Block
, nullptr, nullptr);
36 if (isa
<llvm::Constant
>(Val
))
37 return VirtualUse(UserStmt
, Val
, Constant
, nullptr, nullptr);
39 // Is the value synthesizable? If the user has been pruned
40 // (UserStmt == nullptr), it is either not used anywhere or is synthesizable.
41 // We assume synthesizable which practically should have the same effect.
42 auto *SE
= S
->getSE();
43 if (SE
->isSCEVable(Val
->getType())) {
44 auto *ScevExpr
= SE
->getSCEVAtScope(Val
, UserScope
);
45 if (!UserStmt
|| canSynthesize(Val
, *UserStmt
->getParent(), SE
, UserScope
))
46 return VirtualUse(UserStmt
, Val
, Synthesizable
, ScevExpr
, nullptr);
49 // FIXME: Inconsistency between lookupInvariantEquivClass and
50 // getRequiredInvariantLoads. Querying one of them should be enough.
51 auto &RIL
= S
->getRequiredInvariantLoads();
52 if (S
->lookupInvariantEquivClass(Val
) || RIL
.count(dyn_cast
<LoadInst
>(Val
)))
53 return VirtualUse(UserStmt
, Val
, Hoisted
, nullptr, nullptr);
55 // ReadOnly uses may have MemoryAccesses that we want to associate with the
56 // use. This is why we look for a MemoryAccess here already.
57 MemoryAccess
*InputMA
= nullptr;
58 if (UserStmt
&& Virtual
)
59 InputMA
= UserStmt
->lookupValueReadOf(Val
);
61 // Uses are read-only if they have been defined before the SCoP, i.e., they
62 // cannot be written to inside the SCoP. Arguments are defined before any
63 // instructions, hence also before the SCoP. If the user has been pruned
64 // (UserStmt == nullptr) and is not SCEVable, assume it is read-only as it is
65 // neither an intra- nor an inter-use.
66 if (!UserStmt
|| isa
<Argument
>(Val
))
67 return VirtualUse(UserStmt
, Val
, ReadOnly
, nullptr, InputMA
);
69 auto Inst
= cast
<Instruction
>(Val
);
70 if (!S
->contains(Inst
))
71 return VirtualUse(UserStmt
, Val
, ReadOnly
, nullptr, InputMA
);
73 // A use is inter-statement if either it is defined in another statement, or
74 // there is a MemoryAccess that reads its value that has been written by
76 if (InputMA
|| (!Virtual
&& !UserStmt
->represents(Inst
->getParent())))
77 return VirtualUse(UserStmt
, Val
, Inter
, nullptr, InputMA
);
79 return VirtualUse(UserStmt
, Val
, Intra
, nullptr, nullptr);
82 void VirtualUse::print(raw_ostream
&OS
, bool Reproducible
) const {
83 OS
<< "User: [" << User
->getBaseName() << "] ";
85 case VirtualUse::Constant
:
88 case VirtualUse::Block
:
89 OS
<< "BasicBlock Op:";
91 case VirtualUse::Synthesizable
:
92 OS
<< "Synthesizable Op:";
94 case VirtualUse::Hoisted
:
95 OS
<< "Hoisted load Op:";
97 case VirtualUse::ReadOnly
:
98 OS
<< "Read-Only Op:";
100 case VirtualUse::Intra
:
103 case VirtualUse::Inter
:
111 OS
<< '"' << Val
->getName() << '"';
113 Val
->print(OS
, true);
119 if (InputMA
&& !Reproducible
)
120 OS
<< ' ' << InputMA
;
123 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
124 LLVM_DUMP_METHOD
void VirtualUse::dump() const {
125 print(errs(), false);
130 void VirtualInstruction::print(raw_ostream
&OS
, bool Reproducible
) const {
131 if (!Stmt
|| !Inst
) {
132 OS
<< "[null VirtualInstruction]";
136 OS
<< "[" << Stmt
->getBaseName() << "]";
137 Inst
->print(OS
, !Reproducible
);
140 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
141 LLVM_DUMP_METHOD
void VirtualInstruction::dump() const {
142 print(errs(), false);
147 /// Return true if @p Inst cannot be removed, even if it is nowhere referenced.
148 static bool isRoot(const Instruction
*Inst
) {
149 // The store is handled by its MemoryAccess. The load must be reached from the
150 // roots in order to be marked as used.
151 if (isa
<LoadInst
>(Inst
) || isa
<StoreInst
>(Inst
))
154 // Terminator instructions (in region statements) are required for control
156 if (isa
<TerminatorInst
>(Inst
))
159 // Writes to memory must be honored.
160 if (Inst
->mayWriteToMemory())
166 /// Return true for MemoryAccesses that cannot be removed because it represents
167 /// an llvm::Value that is used after the SCoP.
168 static bool isEscaping(MemoryAccess
*MA
) {
169 assert(MA
->isOriginalValueKind());
170 Scop
*S
= MA
->getStatement()->getParent();
171 return S
->isEscaping(cast
<Instruction
>(MA
->getAccessValue()));
174 /// Add non-removable virtual instructions in @p Stmt to @p RootInsts.
176 addInstructionRoots(ScopStmt
*Stmt
,
177 SmallVectorImpl
<VirtualInstruction
> &RootInsts
) {
178 // For region statements we must keep all instructions because we do not
179 // support removing instructions from region statements.
180 if (!Stmt
->isBlockStmt()) {
181 for (auto *BB
: Stmt
->getRegion()->blocks())
182 for (Instruction
&Inst
: *BB
)
183 RootInsts
.emplace_back(Stmt
, &Inst
);
187 for (Instruction
*Inst
: Stmt
->getInstructions())
189 RootInsts
.emplace_back(Stmt
, Inst
);
192 /// Add non-removable memory accesses in @p Stmt to @p RootInsts.
194 /// @param Local If true, all writes are assumed to escape. markAndSweep
195 /// algorithms can use this to be applicable to a single ScopStmt only without
196 /// the risk of removing definitions required by other statements.
197 /// If false, only writes for SCoP-escaping values are roots. This
198 /// is global mode, where such writes must be marked by theirs uses
199 /// in order to be reachable.
200 static void addAccessRoots(ScopStmt
*Stmt
,
201 SmallVectorImpl
<MemoryAccess
*> &RootAccs
,
203 for (auto *MA
: *Stmt
) {
207 // Writes to arrays are always used.
208 if (MA
->isLatestArrayKind())
209 RootAccs
.push_back(MA
);
211 // Values are roots if they are escaping.
212 else if (MA
->isLatestValueKind()) {
213 if (Local
|| isEscaping(MA
))
214 RootAccs
.push_back(MA
);
217 // Exit phis are, by definition, escaping.
218 else if (MA
->isLatestExitPHIKind())
219 RootAccs
.push_back(MA
);
221 // phi writes are only roots if we are not visiting the statement
222 // containing the PHINode.
223 else if (Local
&& MA
->isLatestPHIKind())
224 RootAccs
.push_back(MA
);
228 /// Determine all instruction and access roots.
229 static void addRoots(ScopStmt
*Stmt
,
230 SmallVectorImpl
<VirtualInstruction
> &RootInsts
,
231 SmallVectorImpl
<MemoryAccess
*> &RootAccs
, bool Local
) {
232 addInstructionRoots(Stmt
, RootInsts
);
233 addAccessRoots(Stmt
, RootAccs
, Local
);
236 /// Mark accesses and instructions as used if they are reachable from a root,
237 /// walking the operand trees.
239 /// @param S The SCoP to walk.
240 /// @param LI The LoopInfo Analysis.
241 /// @param RootInsts List of root instructions.
242 /// @param RootAccs List of root accesses.
243 /// @param UsesInsts[out] Receives all reachable instructions, including the
245 /// @param UsedAccs[out] Receives all reachable accesses, including the roots.
246 /// @param OnlyLocal If non-nullptr, restricts walking to a single
248 static void walkReachable(Scop
*S
, LoopInfo
*LI
,
249 ArrayRef
<VirtualInstruction
> RootInsts
,
250 ArrayRef
<MemoryAccess
*> RootAccs
,
251 DenseSet
<VirtualInstruction
> &UsedInsts
,
252 DenseSet
<MemoryAccess
*> &UsedAccs
,
253 ScopStmt
*OnlyLocal
= nullptr) {
257 SmallVector
<VirtualInstruction
, 32> WorklistInsts
;
258 SmallVector
<MemoryAccess
*, 32> WorklistAccs
;
260 WorklistInsts
.append(RootInsts
.begin(), RootInsts
.end());
261 WorklistAccs
.append(RootAccs
.begin(), RootAccs
.end());
263 auto AddToWorklist
= [&](VirtualUse VUse
) {
264 switch (VUse
.getKind()) {
265 case VirtualUse::Block
:
266 case VirtualUse::Constant
:
267 case VirtualUse::Synthesizable
:
268 case VirtualUse::Hoisted
:
270 case VirtualUse::ReadOnly
:
271 // Read-only scalars only have MemoryAccesses if ModelReadOnlyScalars is
273 if (!VUse
.getMemoryAccess())
276 case VirtualUse::Inter
:
277 assert(VUse
.getMemoryAccess());
278 WorklistAccs
.push_back(VUse
.getMemoryAccess());
280 case VirtualUse::Intra
:
281 WorklistInsts
.emplace_back(VUse
.getUser(),
282 cast
<Instruction
>(VUse
.getValue()));
288 // We have two worklists to process: Only when the MemoryAccess worklist is
289 // empty, we process the instruction worklist.
291 while (!WorklistAccs
.empty()) {
292 auto *Acc
= WorklistAccs
.pop_back_val();
294 ScopStmt
*Stmt
= Acc
->getStatement();
295 if (OnlyLocal
&& Stmt
!= OnlyLocal
)
298 auto Inserted
= UsedAccs
.insert(Acc
);
299 if (!Inserted
.second
)
303 const ScopArrayInfo
*SAI
= Acc
->getScopArrayInfo();
305 if (Acc
->isOriginalValueKind()) {
306 MemoryAccess
*DefAcc
= S
->getValueDef(SAI
);
308 // Accesses to read-only values do not have a definition.
310 WorklistAccs
.push_back(S
->getValueDef(SAI
));
313 if (Acc
->isOriginalAnyPHIKind()) {
314 auto IncomingMAs
= S
->getPHIIncomings(SAI
);
315 WorklistAccs
.append(IncomingMAs
.begin(), IncomingMAs
.end());
319 if (Acc
->isWrite()) {
320 if (Acc
->isOriginalValueKind() ||
321 (Acc
->isOriginalArrayKind() && Acc
->getAccessValue())) {
322 Loop
*Scope
= Stmt
->getSurroundingLoop();
324 VirtualUse::create(S
, Stmt
, Scope
, Acc
->getAccessValue(), true);
328 if (Acc
->isOriginalAnyPHIKind()) {
329 for (auto Incoming
: Acc
->getIncoming()) {
330 VirtualUse VUse
= VirtualUse::create(
331 S
, Stmt
, LI
->getLoopFor(Incoming
.first
), Incoming
.second
, true);
336 if (Acc
->isOriginalArrayKind())
337 WorklistInsts
.emplace_back(Stmt
, Acc
->getAccessInstruction());
341 // If both worklists are empty, stop walking.
342 if (WorklistInsts
.empty())
345 VirtualInstruction VInst
= WorklistInsts
.pop_back_val();
346 ScopStmt
*Stmt
= VInst
.getStmt();
347 Instruction
*Inst
= VInst
.getInstruction();
349 // Do not process statements other than the local.
350 if (OnlyLocal
&& Stmt
!= OnlyLocal
)
353 auto InsertResult
= UsedInsts
.insert(VInst
);
354 if (!InsertResult
.second
)
357 // Add all operands to the worklists.
358 PHINode
*PHI
= dyn_cast
<PHINode
>(Inst
);
359 if (PHI
&& PHI
->getParent() == Stmt
->getEntryBlock()) {
360 if (MemoryAccess
*PHIRead
= Stmt
->lookupPHIReadOf(PHI
))
361 WorklistAccs
.push_back(PHIRead
);
363 for (VirtualUse VUse
: VInst
.operands())
367 // If there is an array access, also add its MemoryAccesses to the worklist.
368 const MemoryAccessList
*Accs
= Stmt
->lookupArrayAccessesFor(Inst
);
372 for (MemoryAccess
*Acc
: *Accs
)
373 WorklistAccs
.push_back(Acc
);
377 void polly::markReachable(Scop
*S
, LoopInfo
*LI
,
378 DenseSet
<VirtualInstruction
> &UsedInsts
,
379 DenseSet
<MemoryAccess
*> &UsedAccs
,
380 ScopStmt
*OnlyLocal
) {
381 SmallVector
<VirtualInstruction
, 32> RootInsts
;
382 SmallVector
<MemoryAccess
*, 32> RootAccs
;
385 addRoots(OnlyLocal
, RootInsts
, RootAccs
, true);
387 for (auto &Stmt
: *S
)
388 addRoots(&Stmt
, RootInsts
, RootAccs
, false);
391 walkReachable(S
, LI
, RootInsts
, RootAccs
, UsedInsts
, UsedAccs
, OnlyLocal
);