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 Instruction
*UI
= dyn_cast
<Instruction
>(U
.getUser());
25 ScopStmt
*UserStmt
= nullptr;
26 if (PHINode
*PHI
= dyn_cast
<PHINode
>(UI
))
27 UserStmt
= S
->getLastStmtFor(PHI
->getIncomingBlock(U
));
29 UserStmt
= S
->getStmtFor(UI
);
30 auto *UserScope
= LI
->getLoopFor(UserBB
);
31 return create(S
, UserStmt
, UserScope
, U
.get(), Virtual
);
34 VirtualUse
VirtualUse::create(Scop
*S
, ScopStmt
*UserStmt
, Loop
*UserScope
,
35 Value
*Val
, bool Virtual
) {
36 assert(!isa
<StoreInst
>(Val
) && "a StoreInst cannot be used");
38 if (isa
<BasicBlock
>(Val
))
39 return VirtualUse(UserStmt
, Val
, Block
, nullptr, nullptr);
41 if (isa
<llvm::Constant
>(Val
))
42 return VirtualUse(UserStmt
, Val
, Constant
, nullptr, nullptr);
44 // Is the value synthesizable? If the user has been pruned
45 // (UserStmt == nullptr), it is either not used anywhere or is synthesizable.
46 // We assume synthesizable which practically should have the same effect.
47 auto *SE
= S
->getSE();
48 if (SE
->isSCEVable(Val
->getType())) {
49 auto *ScevExpr
= SE
->getSCEVAtScope(Val
, UserScope
);
50 if (!UserStmt
|| canSynthesize(Val
, *UserStmt
->getParent(), SE
, UserScope
))
51 return VirtualUse(UserStmt
, Val
, Synthesizable
, ScevExpr
, nullptr);
54 // FIXME: Inconsistency between lookupInvariantEquivClass and
55 // getRequiredInvariantLoads. Querying one of them should be enough.
56 auto &RIL
= S
->getRequiredInvariantLoads();
57 if (S
->lookupInvariantEquivClass(Val
) || RIL
.count(dyn_cast
<LoadInst
>(Val
)))
58 return VirtualUse(UserStmt
, Val
, Hoisted
, nullptr, nullptr);
60 // ReadOnly uses may have MemoryAccesses that we want to associate with the
61 // use. This is why we look for a MemoryAccess here already.
62 MemoryAccess
*InputMA
= nullptr;
63 if (UserStmt
&& Virtual
)
64 InputMA
= UserStmt
->lookupValueReadOf(Val
);
66 // Uses are read-only if they have been defined before the SCoP, i.e., they
67 // cannot be written to inside the SCoP. Arguments are defined before any
68 // instructions, hence also before the SCoP. If the user has been pruned
69 // (UserStmt == nullptr) and is not SCEVable, assume it is read-only as it is
70 // neither an intra- nor an inter-use.
71 if (!UserStmt
|| isa
<Argument
>(Val
))
72 return VirtualUse(UserStmt
, Val
, ReadOnly
, nullptr, InputMA
);
74 auto Inst
= cast
<Instruction
>(Val
);
75 if (!S
->contains(Inst
))
76 return VirtualUse(UserStmt
, Val
, ReadOnly
, nullptr, InputMA
);
78 // A use is inter-statement if either it is defined in another statement, or
79 // there is a MemoryAccess that reads its value that has been written by
81 if (InputMA
|| (!Virtual
&& !UserStmt
->represents(Inst
->getParent())))
82 return VirtualUse(UserStmt
, Val
, Inter
, nullptr, InputMA
);
84 return VirtualUse(UserStmt
, Val
, Intra
, nullptr, nullptr);
87 void VirtualUse::print(raw_ostream
&OS
, bool Reproducible
) const {
88 OS
<< "User: [" << User
->getBaseName() << "] ";
90 case VirtualUse::Constant
:
93 case VirtualUse::Block
:
94 OS
<< "BasicBlock Op:";
96 case VirtualUse::Synthesizable
:
97 OS
<< "Synthesizable Op:";
99 case VirtualUse::Hoisted
:
100 OS
<< "Hoisted load Op:";
102 case VirtualUse::ReadOnly
:
103 OS
<< "Read-Only Op:";
105 case VirtualUse::Intra
:
108 case VirtualUse::Inter
:
116 OS
<< '"' << Val
->getName() << '"';
118 Val
->print(OS
, true);
124 if (InputMA
&& !Reproducible
)
125 OS
<< ' ' << InputMA
;
128 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
129 LLVM_DUMP_METHOD
void VirtualUse::dump() const {
130 print(errs(), false);
135 void VirtualInstruction::print(raw_ostream
&OS
, bool Reproducible
) const {
136 if (!Stmt
|| !Inst
) {
137 OS
<< "[null VirtualInstruction]";
141 OS
<< "[" << Stmt
->getBaseName() << "]";
142 Inst
->print(OS
, !Reproducible
);
145 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
146 LLVM_DUMP_METHOD
void VirtualInstruction::dump() const {
147 print(errs(), false);
152 /// Return true if @p Inst cannot be removed, even if it is nowhere referenced.
153 static bool isRoot(const Instruction
*Inst
) {
154 // The store is handled by its MemoryAccess. The load must be reached from the
155 // roots in order to be marked as used.
156 if (isa
<LoadInst
>(Inst
) || isa
<StoreInst
>(Inst
))
159 // Terminator instructions (in region statements) are required for control
161 if (isa
<TerminatorInst
>(Inst
))
164 // Writes to memory must be honored.
165 if (Inst
->mayWriteToMemory())
171 /// Return true for MemoryAccesses that cannot be removed because it represents
172 /// an llvm::Value that is used after the SCoP.
173 static bool isEscaping(MemoryAccess
*MA
) {
174 assert(MA
->isOriginalValueKind());
175 Scop
*S
= MA
->getStatement()->getParent();
176 return S
->isEscaping(cast
<Instruction
>(MA
->getAccessValue()));
179 /// Add non-removable virtual instructions in @p Stmt to @p RootInsts.
181 addInstructionRoots(ScopStmt
*Stmt
,
182 SmallVectorImpl
<VirtualInstruction
> &RootInsts
) {
183 // For region statements we must keep all instructions because we do not
184 // support removing instructions from region statements.
185 if (!Stmt
->isBlockStmt()) {
186 for (auto *BB
: Stmt
->getRegion()->blocks())
187 for (Instruction
&Inst
: *BB
)
188 RootInsts
.emplace_back(Stmt
, &Inst
);
192 for (Instruction
*Inst
: Stmt
->getInstructions())
194 RootInsts
.emplace_back(Stmt
, Inst
);
197 /// Add non-removable memory accesses in @p Stmt to @p RootInsts.
199 /// @param Local If true, all writes are assumed to escape. markAndSweep
200 /// algorithms can use this to be applicable to a single ScopStmt only without
201 /// the risk of removing definitions required by other statements.
202 /// If false, only writes for SCoP-escaping values are roots. This
203 /// is global mode, where such writes must be marked by theirs uses
204 /// in order to be reachable.
205 static void addAccessRoots(ScopStmt
*Stmt
,
206 SmallVectorImpl
<MemoryAccess
*> &RootAccs
,
208 for (auto *MA
: *Stmt
) {
212 // Writes to arrays are always used.
213 if (MA
->isLatestArrayKind())
214 RootAccs
.push_back(MA
);
216 // Values are roots if they are escaping.
217 else if (MA
->isLatestValueKind()) {
218 if (Local
|| isEscaping(MA
))
219 RootAccs
.push_back(MA
);
222 // Exit phis are, by definition, escaping.
223 else if (MA
->isLatestExitPHIKind())
224 RootAccs
.push_back(MA
);
226 // phi writes are only roots if we are not visiting the statement
227 // containing the PHINode.
228 else if (Local
&& MA
->isLatestPHIKind())
229 RootAccs
.push_back(MA
);
233 /// Determine all instruction and access roots.
234 static void addRoots(ScopStmt
*Stmt
,
235 SmallVectorImpl
<VirtualInstruction
> &RootInsts
,
236 SmallVectorImpl
<MemoryAccess
*> &RootAccs
, bool Local
) {
237 addInstructionRoots(Stmt
, RootInsts
);
238 addAccessRoots(Stmt
, RootAccs
, Local
);
241 /// Mark accesses and instructions as used if they are reachable from a root,
242 /// walking the operand trees.
244 /// @param S The SCoP to walk.
245 /// @param LI The LoopInfo Analysis.
246 /// @param RootInsts List of root instructions.
247 /// @param RootAccs List of root accesses.
248 /// @param UsesInsts[out] Receives all reachable instructions, including the
250 /// @param UsedAccs[out] Receives all reachable accesses, including the roots.
251 /// @param OnlyLocal If non-nullptr, restricts walking to a single
253 static void walkReachable(Scop
*S
, LoopInfo
*LI
,
254 ArrayRef
<VirtualInstruction
> RootInsts
,
255 ArrayRef
<MemoryAccess
*> RootAccs
,
256 DenseSet
<VirtualInstruction
> &UsedInsts
,
257 DenseSet
<MemoryAccess
*> &UsedAccs
,
258 ScopStmt
*OnlyLocal
= nullptr) {
262 SmallVector
<VirtualInstruction
, 32> WorklistInsts
;
263 SmallVector
<MemoryAccess
*, 32> WorklistAccs
;
265 WorklistInsts
.append(RootInsts
.begin(), RootInsts
.end());
266 WorklistAccs
.append(RootAccs
.begin(), RootAccs
.end());
268 auto AddToWorklist
= [&](VirtualUse VUse
) {
269 switch (VUse
.getKind()) {
270 case VirtualUse::Block
:
271 case VirtualUse::Constant
:
272 case VirtualUse::Synthesizable
:
273 case VirtualUse::Hoisted
:
275 case VirtualUse::ReadOnly
:
276 // Read-only scalars only have MemoryAccesses if ModelReadOnlyScalars is
278 if (!VUse
.getMemoryAccess())
281 case VirtualUse::Inter
:
282 assert(VUse
.getMemoryAccess());
283 WorklistAccs
.push_back(VUse
.getMemoryAccess());
285 case VirtualUse::Intra
:
286 WorklistInsts
.emplace_back(VUse
.getUser(),
287 cast
<Instruction
>(VUse
.getValue()));
293 // We have two worklists to process: Only when the MemoryAccess worklist is
294 // empty, we process the instruction worklist.
296 while (!WorklistAccs
.empty()) {
297 auto *Acc
= WorklistAccs
.pop_back_val();
299 ScopStmt
*Stmt
= Acc
->getStatement();
300 if (OnlyLocal
&& Stmt
!= OnlyLocal
)
303 auto Inserted
= UsedAccs
.insert(Acc
);
304 if (!Inserted
.second
)
308 const ScopArrayInfo
*SAI
= Acc
->getScopArrayInfo();
310 if (Acc
->isOriginalValueKind()) {
311 MemoryAccess
*DefAcc
= S
->getValueDef(SAI
);
313 // Accesses to read-only values do not have a definition.
315 WorklistAccs
.push_back(S
->getValueDef(SAI
));
318 if (Acc
->isOriginalAnyPHIKind()) {
319 auto IncomingMAs
= S
->getPHIIncomings(SAI
);
320 WorklistAccs
.append(IncomingMAs
.begin(), IncomingMAs
.end());
324 if (Acc
->isWrite()) {
325 if (Acc
->isOriginalValueKind() ||
326 (Acc
->isOriginalArrayKind() && Acc
->getAccessValue())) {
327 Loop
*Scope
= Stmt
->getSurroundingLoop();
329 VirtualUse::create(S
, Stmt
, Scope
, Acc
->getAccessValue(), true);
333 if (Acc
->isOriginalAnyPHIKind()) {
334 for (auto Incoming
: Acc
->getIncoming()) {
335 VirtualUse VUse
= VirtualUse::create(
336 S
, Stmt
, LI
->getLoopFor(Incoming
.first
), Incoming
.second
, true);
341 if (Acc
->isOriginalArrayKind())
342 WorklistInsts
.emplace_back(Stmt
, Acc
->getAccessInstruction());
346 // If both worklists are empty, stop walking.
347 if (WorklistInsts
.empty())
350 VirtualInstruction VInst
= WorklistInsts
.pop_back_val();
351 ScopStmt
*Stmt
= VInst
.getStmt();
352 Instruction
*Inst
= VInst
.getInstruction();
354 // Do not process statements other than the local.
355 if (OnlyLocal
&& Stmt
!= OnlyLocal
)
358 auto InsertResult
= UsedInsts
.insert(VInst
);
359 if (!InsertResult
.second
)
362 // Add all operands to the worklists.
363 PHINode
*PHI
= dyn_cast
<PHINode
>(Inst
);
364 if (PHI
&& PHI
->getParent() == Stmt
->getEntryBlock()) {
365 if (MemoryAccess
*PHIRead
= Stmt
->lookupPHIReadOf(PHI
))
366 WorklistAccs
.push_back(PHIRead
);
368 for (VirtualUse VUse
: VInst
.operands())
372 // If there is an array access, also add its MemoryAccesses to the worklist.
373 const MemoryAccessList
*Accs
= Stmt
->lookupArrayAccessesFor(Inst
);
377 for (MemoryAccess
*Acc
: *Accs
)
378 WorklistAccs
.push_back(Acc
);
382 void polly::markReachable(Scop
*S
, LoopInfo
*LI
,
383 DenseSet
<VirtualInstruction
> &UsedInsts
,
384 DenseSet
<MemoryAccess
*> &UsedAccs
,
385 ScopStmt
*OnlyLocal
) {
386 SmallVector
<VirtualInstruction
, 32> RootInsts
;
387 SmallVector
<MemoryAccess
*, 32> RootAccs
;
390 addRoots(OnlyLocal
, RootInsts
, RootAccs
, true);
392 for (auto &Stmt
: *S
)
393 addRoots(&Stmt
, RootInsts
, RootAccs
, false);
396 walkReachable(S
, LI
, RootInsts
, RootAccs
, UsedInsts
, UsedAccs
, OnlyLocal
);