1 //===------ VirtualInstruction.cpp ------------------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Tools for determining which instructions are within a statement and the
11 // nature of their operands.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "polly/Support/VirtualInstruction.h"
16 #include "polly/Support/SCEVValidator.h"
17 
18 using namespace polly;
19 using namespace llvm;
20 
21 VirtualUse VirtualUse ::create(Scop *S, Use &U, LoopInfo *LI, bool Virtual) {
22   auto *UserBB = getUseBlock(U);
23   auto *UserStmt = S->getStmtFor(UserBB);
24   auto *UserScope = LI->getLoopFor(UserBB);
25   return create(S, UserStmt, UserScope, U.get(), Virtual);
26 }
27 
28 VirtualUse VirtualUse::create(Scop *S, ScopStmt *UserStmt, Loop *UserScope,
29                               Value *Val, bool Virtual) {
30   assert(!isa<StoreInst>(Val) && "a StoreInst cannot be used");
31 
32   if (isa<BasicBlock>(Val))
33     return VirtualUse(UserStmt, Val, Block, nullptr, nullptr);
34 
35   if (isa<llvm::Constant>(Val))
36     return VirtualUse(UserStmt, Val, Constant, nullptr, nullptr);
37 
38   // Is the value synthesizable? If the user has been pruned
39   // (UserStmt == nullptr), it is either not used anywhere or is synthesizable.
40   // We assume synthesizable which practically should have the same effect.
41   auto *SE = S->getSE();
42   if (SE->isSCEVable(Val->getType())) {
43     auto *ScevExpr = SE->getSCEVAtScope(Val, UserScope);
44     if (!UserStmt || canSynthesize(Val, *UserStmt->getParent(), SE, UserScope))
45       return VirtualUse(UserStmt, Val, Synthesizable, ScevExpr, nullptr);
46   }
47 
48   // FIXME: Inconsistency between lookupInvariantEquivClass and
49   // getRequiredInvariantLoads. Querying one of them should be enough.
50   auto &RIL = S->getRequiredInvariantLoads();
51   if (S->lookupInvariantEquivClass(Val) || RIL.count(dyn_cast<LoadInst>(Val)))
52     return VirtualUse(UserStmt, Val, Hoisted, nullptr, nullptr);
53 
54   // ReadOnly uses may have MemoryAccesses that we want to associate with the
55   // use. This is why we look for a MemoryAccess here already.
56   MemoryAccess *InputMA = nullptr;
57   if (UserStmt && Virtual)
58     InputMA = UserStmt->lookupValueReadOf(Val);
59 
60   // Uses are read-only if they have been defined before the SCoP, i.e., they
61   // cannot be written to inside the SCoP. Arguments are defined before any
62   // instructions, hence also before the SCoP. If the user has been pruned
63   // (UserStmt == nullptr) and is not SCEVable, assume it is read-only as it is
64   // neither an intra- nor an inter-use.
65   if (!UserStmt || isa<Argument>(Val))
66     return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
67 
68   auto Inst = cast<Instruction>(Val);
69   if (!S->contains(Inst))
70     return VirtualUse(UserStmt, Val, ReadOnly, nullptr, InputMA);
71 
72   // A use is inter-statement if either it is defined in another statement, or
73   // there is a MemoryAccess that reads its value that has been written by
74   // another statement.
75   if (InputMA || (!Virtual && !UserStmt->contains(Inst->getParent())))
76     return VirtualUse(UserStmt, Val, Inter, nullptr, InputMA);
77 
78   return VirtualUse(UserStmt, Val, Intra, nullptr, nullptr);
79 }
80 
81 void VirtualUse::print(raw_ostream &OS, bool Reproducible) const {
82   OS << "User: [" << User->getBaseName() << "] ";
83   switch (Kind) {
84   case VirtualUse::Constant:
85     OS << "Constant Op:";
86     break;
87   case VirtualUse::Block:
88     OS << "BasicBlock Op:";
89     break;
90   case VirtualUse::Synthesizable:
91     OS << "Synthesizable Op:";
92     break;
93   case VirtualUse::Hoisted:
94     OS << "Hoisted load Op:";
95     break;
96   case VirtualUse::ReadOnly:
97     OS << "Read-Only Op:";
98     break;
99   case VirtualUse::Intra:
100     OS << "Intra Op:";
101     break;
102   case VirtualUse::Inter:
103     OS << "Inter Op:";
104     break;
105   }
106 
107   if (Val) {
108     OS << ' ';
109     if (Reproducible)
110       OS << '"' << Val->getName() << '"';
111     else
112       Val->print(OS, true);
113   }
114   if (ScevExpr) {
115     OS << ' ';
116     ScevExpr->print(OS);
117   }
118   if (InputMA && !Reproducible)
119     OS << ' ' << InputMA;
120 }
121 
122 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
123 void VirtualUse::dump() const {
124   print(errs(), false);
125   errs() << '\n';
126 }
127 #endif
128