22 Loop *UserScope = LI->getLoopFor(UserBB);
23 Instruction *UI = dyn_cast<Instruction>(U.getUser());
28 if (PHINode *
PHI = dyn_cast<PHINode>(UI)) {
30 if (
S->getRegion().getExit() ==
PHI->getParent())
41 IncomingMA =
S->getPHIRead(SAI);
49 return create(
S, UserStmt, UserScope, U.get(), Virtual);
54 assert(!isa<StoreInst>(
Val) &&
"a StoreInst cannot be used");
56 if (isa<BasicBlock>(
Val))
59 if (isa<llvm::Constant>(
Val) || isa<MetadataAsValue>(
Val) ||
66 auto *SE =
S->getSE();
67 if (SE->isSCEVable(
Val->getType())) {
68 const SCEV *
ScevExpr = SE->getSCEVAtScope(
Val, UserScope);
75 auto &RIL =
S->getRequiredInvariantLoads();
76 if (
S->lookupInvariantEquivClass(
Val) || RIL.count(dyn_cast<LoadInst>(
Val)))
82 if (UserStmt && Virtual)
90 if (!UserStmt || isa<Argument>(
Val))
93 auto Inst = cast<Instruction>(
Val);
94 if (!
S->contains(Inst))
100 if (
InputMA || (!Virtual && UserStmt !=
S->getStmtFor(Inst)))
107 OS <<
"User: [" <<
User->getBaseName() <<
"] ";
110 OS <<
"Constant Op:";
113 OS <<
"BasicBlock Op:";
116 OS <<
"Synthesizable Op:";
119 OS <<
"Hoisted load Op:";
122 OS <<
"Read-Only Op:";
135 OS <<
'"' <<
Val->getName() <<
'"';
137 Val->print(OS,
true);
147#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
149 print(errs(),
false);
156 OS <<
"[null VirtualInstruction]";
160 OS <<
"[" <<
Stmt->getBaseName() <<
"]";
161 Inst->print(OS, !Reproducible);
164#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
166 print(errs(),
false);
172static bool isRoot(
const Instruction *Inst) {
175 if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
180 if (Inst->isTerminator())
184 if (Inst->mayWriteToMemory())
201 SmallVectorImpl<VirtualInstruction> &RootInsts) {
206 RootInsts.emplace_back(Stmt,
207 Stmt->
getRegion()->getEntry()->getTerminator());
208 for (BasicBlock *BB : Stmt->
getRegion()->blocks())
210 for (Instruction &Inst : *BB)
211 RootInsts.emplace_back(Stmt, &Inst);
217 RootInsts.emplace_back(Stmt, Inst);
229 SmallVectorImpl<MemoryAccess *> &RootAccs,
231 for (
auto *MA : *Stmt) {
236 if (MA->isLatestArrayKind())
237 RootAccs.push_back(MA);
240 else if (MA->isLatestValueKind()) {
242 RootAccs.push_back(MA);
246 else if (MA->isLatestExitPHIKind())
247 RootAccs.push_back(MA);
251 else if (Local && MA->isLatestPHIKind())
252 RootAccs.push_back(MA);
258 SmallVectorImpl<VirtualInstruction> &RootInsts,
259 SmallVectorImpl<MemoryAccess *> &RootAccs,
bool Local) {
277 ArrayRef<VirtualInstruction> RootInsts,
278 ArrayRef<MemoryAccess *> RootAccs,
279 DenseSet<VirtualInstruction> &UsedInsts,
280 DenseSet<MemoryAccess *> &UsedAccs,
285 SmallVector<VirtualInstruction, 32> WorklistInsts;
286 SmallVector<MemoryAccess *, 32> WorklistAccs;
288 WorklistInsts.append(RootInsts.begin(), RootInsts.end());
289 WorklistAccs.append(RootAccs.begin(), RootAccs.end());
292 switch (VUse.getKind()) {
301 if (!VUse.getMemoryAccess())
305 assert(VUse.getMemoryAccess());
306 WorklistAccs.push_back(VUse.getMemoryAccess());
309 WorklistInsts.emplace_back(VUse.getUser(),
310 cast<Instruction>(VUse.getValue()));
319 while (!WorklistAccs.empty()) {
320 auto *Acc = WorklistAccs.pop_back_val();
322 ScopStmt *Stmt = Acc->getStatement();
323 if (OnlyLocal && Stmt != OnlyLocal)
326 auto Inserted = UsedAccs.insert(Acc);
327 if (!Inserted.second)
333 if (Acc->isLatestValueKind()) {
338 WorklistAccs.push_back(
S->getValueDef(SAI));
341 if (Acc->isLatestAnyPHIKind()) {
342 auto IncomingMAs =
S->getPHIIncomings(SAI);
343 WorklistAccs.append(IncomingMAs.begin(), IncomingMAs.end());
347 if (Acc->isWrite()) {
348 if (Acc->isOriginalValueKind() ||
349 (Acc->isOriginalArrayKind() && Acc->getAccessValue())) {
356 if (Acc->isOriginalAnyPHIKind()) {
357 for (
auto Incoming : Acc->getIncoming()) {
359 S, Stmt, LI->getLoopFor(Incoming.first), Incoming.second,
true);
364 if (Acc->isOriginalArrayKind())
365 WorklistInsts.emplace_back(Stmt, Acc->getAccessInstruction());
370 if (WorklistInsts.empty())
378 if (OnlyLocal && Stmt != OnlyLocal)
381 auto InsertResult = UsedInsts.insert(VInst);
382 if (!InsertResult.second)
386 PHINode *
PHI = dyn_cast<PHINode>(Inst);
389 WorklistAccs.push_back(PHIRead);
401 WorklistAccs.push_back(Acc);
406 DenseSet<VirtualInstruction> &UsedInsts,
407 DenseSet<MemoryAccess *> &UsedAccs,
409 SmallVector<VirtualInstruction, 32> RootInsts;
410 SmallVector<MemoryAccess *, 32> RootAccs;
413 addRoots(OnlyLocal, RootInsts, RootAccs,
true);
415 for (
auto &Stmt : *
S)
416 addRoots(&Stmt, RootInsts, RootAccs,
false);
419 walkReachable(
S, LI, RootInsts, RootAccs, UsedInsts, UsedAccs, OnlyLocal);
static void walkReachable(Scop *S, LoopInfo *LI, ArrayRef< VirtualInstruction > RootInsts, ArrayRef< MemoryAccess * > RootAccs, DenseSet< VirtualInstruction > &UsedInsts, DenseSet< MemoryAccess * > &UsedAccs, ScopStmt *OnlyLocal=nullptr)
Mark accesses and instructions as used if they are reachable from a root, walking the operand trees.
static void addInstructionRoots(ScopStmt *Stmt, SmallVectorImpl< VirtualInstruction > &RootInsts)
Add non-removable virtual instructions in Stmt to RootInsts.
static bool isEscaping(MemoryAccess *MA)
Return true for MemoryAccesses that cannot be removed because it represents an llvm::Value that is us...
static void addRoots(ScopStmt *Stmt, SmallVectorImpl< VirtualInstruction > &RootInsts, SmallVectorImpl< MemoryAccess * > &RootAccs, bool Local)
Determine all instruction and access roots.
static void addAccessRoots(ScopStmt *Stmt, SmallVectorImpl< MemoryAccess * > &RootAccs, bool Local)
Add non-removable memory accesses in Stmt to RootInsts.
static bool isRoot(const Instruction *Inst)
Return true if Inst cannot be removed, even if it is nowhere referenced.
Represent memory accesses in statements.
bool isOriginalValueKind() const
Was this MemoryAccess detected as a scalar dependences?
ScopStmt * getStatement() const
Get the statement that contains this memory access.
Value * getAccessValue() const
Return the access value of this memory access.
A class to store information about arrays in the SCoP.
BasicBlock * getEntryBlock() const
Return a BasicBlock from this statement.
const std::vector< Instruction * > & getInstructions() const
bool isBlockStmt() const
Return true if this statement represents a single basic block.
const MemoryAccessList * lookupArrayAccessesFor(const Instruction *Inst) const
Find all array accesses for Inst.
Region * getRegion() const
Get the region represented by this ScopStmt (if any).
MemoryAccess * lookupPHIReadOf(PHINode *PHI) const
Return the MemoryAccess that loads a PHINode value, or nullptr if not existing, respectively not yet ...
Loop * getSurroundingLoop() const
Return the closest innermost loop that contains this statement, but is not contained in it.
MemoryAccess * lookupValueReadOf(Value *Inst) const
Return the MemoryAccess that reloads a value, or nullptr if not existing, respectively not yet added.
This class represents a "virtual instruction", an instruction in a ScopStmt, effectively a ScopStmt/I...
ScopStmt * getStmt() const
Return the ScopStmt this virtual instruction is in.
Instruction * Inst
The instruction of a statement.
llvm::iterator_range< VirtualOperandIterator > operands() const
Returns a list of virtual operands.
ScopStmt * Stmt
The statement this virtual instruction is in.
void print(raw_ostream &OS, bool Reproducible=true) const
Print a description of this object.
Instruction * getInstruction() const
Return the instruction in the statement.
Determine the nature of a value's use within a statement.
ScopStmt * User
The statement where a value is used.
static VirtualUse create(Scop *S, const Use &U, LoopInfo *LI, bool Virtual)
Get a VirtualUse for an llvm::Use.
const SCEV * ScevExpr
The value represented as llvm::SCEV expression.
VirtualUse(ScopStmt *User, Value *Val, UseKind Kind, const SCEV *ScevExpr, MemoryAccess *InputMA)
Value * Val
The value that is used.
void print(raw_ostream &OS, bool Reproducible=true) const
Print a description of this object.
MemoryAccess * InputMA
If this is an inter-statement (or read-only) use, contains the MemoryAccess that makes the value avai...
UseKind Kind
The type of value use.
This file contains the declaration of the PolyhedralInfo class, which will provide an interface to ex...
std::forward_list< MemoryAccess * > MemoryAccessList
Ordered list type to hold accesses.
@ Value
MemoryKind::Value: Models an llvm::Value.
@ PHI
MemoryKind::PHI: Models PHI nodes within the SCoP.
void markReachable(Scop *S, LoopInfo *LI, DenseSet< VirtualInstruction > &UsedInsts, DenseSet< MemoryAccess * > &UsedAccs, ScopStmt *OnlyLocal=nullptr)
Find all reachable instructions and accesses.
llvm::BasicBlock * getUseBlock(const llvm::Use &U)
Return the block in which a value is used.
bool canSynthesize(const llvm::Value *V, const Scop &S, llvm::ScalarEvolution *SE, llvm::Loop *Scope)
Check whether a value an be synthesized by the code generator.