1 //===- CGSCCPassManager.cpp - Managing & running CGSCC passes -------------===//
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 #include "llvm/Analysis/CGSCCPassManager.h"
11 #include "llvm/Support/CommandLine.h"
12 #include "llvm/Support/Debug.h"
13 
14 using namespace llvm;
15 
16 static cl::opt<bool>
17 DebugPM("debug-cgscc-pass-manager", cl::Hidden,
18         cl::desc("Print CGSCC pass management debugging information"));
19 
20 PreservedAnalyses CGSCCPassManager::run(LazyCallGraph::SCC &C,
21                                         CGSCCAnalysisManager *AM) {
22   PreservedAnalyses PA = PreservedAnalyses::all();
23 
24   if (DebugPM)
25     dbgs() << "Starting CGSCC pass manager run.\n";
26 
27   for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
28     if (DebugPM)
29       dbgs() << "Running CGSCC pass: " << Passes[Idx]->name() << "\n";
30 
31     PreservedAnalyses PassPA = Passes[Idx]->run(C, AM);
32 
33     // If we have an active analysis manager at this level we want to ensure we
34     // update it as each pass runs and potentially invalidates analyses. We
35     // also update the preserved set of analyses based on what analyses we have
36     // already handled the invalidation for here and don't need to invalidate
37     // when finished.
38     if (AM)
39       PassPA = AM->invalidate(C, std::move(PassPA));
40 
41     // Finally, we intersect the final preserved analyses to compute the
42     // aggregate preserved set for this pass manager.
43     PA.intersect(std::move(PassPA));
44   }
45 
46   if (DebugPM)
47     dbgs() << "Finished CGSCC pass manager run.\n";
48 
49   return PA;
50 }
51 
52 bool CGSCCAnalysisManager::empty() const {
53   assert(CGSCCAnalysisResults.empty() == CGSCCAnalysisResultLists.empty() &&
54          "The storage and index of analysis results disagree on how many there "
55          "are!");
56   return CGSCCAnalysisResults.empty();
57 }
58 
59 void CGSCCAnalysisManager::clear() {
60   CGSCCAnalysisResults.clear();
61   CGSCCAnalysisResultLists.clear();
62 }
63 
64 CGSCCAnalysisManager::ResultConceptT &
65 CGSCCAnalysisManager::getResultImpl(void *PassID, LazyCallGraph::SCC &C) {
66   CGSCCAnalysisResultMapT::iterator RI;
67   bool Inserted;
68   std::tie(RI, Inserted) = CGSCCAnalysisResults.insert(std::make_pair(
69       std::make_pair(PassID, &C), CGSCCAnalysisResultListT::iterator()));
70 
71   // If we don't have a cached result for this function, look up the pass and
72   // run it to produce a result, which we then add to the cache.
73   if (Inserted) {
74     auto &P = lookupPass(PassID);
75     if (DebugPM)
76       dbgs() << "Running CGSCC analysis: " << P.name() << "\n";
77     CGSCCAnalysisResultListT &ResultList = CGSCCAnalysisResultLists[&C];
78     ResultList.emplace_back(PassID, P.run(C, this));
79     RI->second = std::prev(ResultList.end());
80   }
81 
82   return *RI->second->second;
83 }
84 
85 CGSCCAnalysisManager::ResultConceptT *
86 CGSCCAnalysisManager::getCachedResultImpl(void *PassID,
87                                           LazyCallGraph::SCC &C) const {
88   CGSCCAnalysisResultMapT::const_iterator RI =
89       CGSCCAnalysisResults.find(std::make_pair(PassID, &C));
90   return RI == CGSCCAnalysisResults.end() ? nullptr : &*RI->second->second;
91 }
92 
93 void CGSCCAnalysisManager::invalidateImpl(void *PassID, LazyCallGraph::SCC &C) {
94   CGSCCAnalysisResultMapT::iterator RI =
95       CGSCCAnalysisResults.find(std::make_pair(PassID, &C));
96   if (RI == CGSCCAnalysisResults.end())
97     return;
98 
99   if (DebugPM)
100     dbgs() << "Invalidating CGSCC analysis: " << lookupPass(PassID).name()
101            << "\n";
102   CGSCCAnalysisResultLists[&C].erase(RI->second);
103   CGSCCAnalysisResults.erase(RI);
104 }
105 
106 PreservedAnalyses CGSCCAnalysisManager::invalidateImpl(LazyCallGraph::SCC &C,
107                                                        PreservedAnalyses PA) {
108   // Short circuit for a common case of all analyses being preserved.
109   if (PA.areAllPreserved())
110     return std::move(PA);
111 
112   if (DebugPM)
113     dbgs() << "Invalidating all non-preserved analyses for SCC: " << C.getName()
114            << "\n";
115 
116   // Clear all the invalidated results associated specifically with this
117   // function.
118   SmallVector<void *, 8> InvalidatedPassIDs;
119   CGSCCAnalysisResultListT &ResultsList = CGSCCAnalysisResultLists[&C];
120   for (CGSCCAnalysisResultListT::iterator I = ResultsList.begin(),
121                                           E = ResultsList.end();
122        I != E;) {
123     void *PassID = I->first;
124 
125     // Pass the invalidation down to the pass itself to see if it thinks it is
126     // necessary. The analysis pass can return false if no action on the part
127     // of the analysis manager is required for this invalidation event.
128     if (I->second->invalidate(C, PA)) {
129       if (DebugPM)
130         dbgs() << "Invalidating CGSCC analysis: " << lookupPass(PassID).name()
131                << "\n";
132 
133       InvalidatedPassIDs.push_back(I->first);
134       I = ResultsList.erase(I);
135     } else {
136       ++I;
137     }
138 
139     // After handling each pass, we mark it as preserved. Once we've
140     // invalidated any stale results, the rest of the system is allowed to
141     // start preserving this analysis again.
142     PA.preserve(PassID);
143   }
144   while (!InvalidatedPassIDs.empty())
145     CGSCCAnalysisResults.erase(
146         std::make_pair(InvalidatedPassIDs.pop_back_val(), &C));
147   CGSCCAnalysisResultLists.erase(&C);
148 
149   return std::move(PA);
150 }
151 
152 char CGSCCAnalysisManagerModuleProxy::PassID;
153 
154 CGSCCAnalysisManagerModuleProxy::Result
155 CGSCCAnalysisManagerModuleProxy::run(Module &M) {
156   assert(CGAM->empty() && "CGSCC analyses ran prior to the module proxy!");
157   return Result(*CGAM);
158 }
159 
160 CGSCCAnalysisManagerModuleProxy::Result::~Result() {
161   // Clear out the analysis manager if we're being destroyed -- it means we
162   // didn't even see an invalidate call when we got invalidated.
163   CGAM->clear();
164 }
165 
166 bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
167     Module &M, const PreservedAnalyses &PA) {
168   // If this proxy isn't marked as preserved, then we can't even invalidate
169   // individual CGSCC analyses, there may be an invalid set of SCC objects in
170   // the cache making it impossible to incrementally preserve them.
171   // Just clear the entire manager.
172   if (!PA.preserved(ID()))
173     CGAM->clear();
174 
175   // Return false to indicate that this result is still a valid proxy.
176   return false;
177 }
178 
179 char ModuleAnalysisManagerCGSCCProxy::PassID;
180 
181 char FunctionAnalysisManagerCGSCCProxy::PassID;
182 
183 FunctionAnalysisManagerCGSCCProxy::Result
184 FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC &C) {
185   assert(FAM->empty() && "Function analyses ran prior to the CGSCC proxy!");
186   return Result(*FAM);
187 }
188 
189 FunctionAnalysisManagerCGSCCProxy::Result::~Result() {
190   // Clear out the analysis manager if we're being destroyed -- it means we
191   // didn't even see an invalidate call when we got invalidated.
192   FAM->clear();
193 }
194 
195 bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate(
196     LazyCallGraph::SCC &C, const PreservedAnalyses &PA) {
197   // If this proxy isn't marked as preserved, then we can't even invalidate
198   // individual function analyses, there may be an invalid set of Function
199   // objects in the cache making it impossible to incrementally preserve them.
200   // Just clear the entire manager.
201   if (!PA.preserved(ID()))
202     FAM->clear();
203 
204   // Return false to indicate that this result is still a valid proxy.
205   return false;
206 }
207 
208 char CGSCCAnalysisManagerFunctionProxy::PassID;
209