1dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===- CGSCCPassManager.cpp - Managing & running CGSCC passes -------------===// 2dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 3dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// The LLVM Compiler Infrastructure 4dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 5dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// This file is distributed under the University of Illinois Open Source 6dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// License. See LICENSE.TXT for details. 7dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 8dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===----------------------------------------------------------------------===// 9dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 10dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Analysis/CGSCCPassManager.h" 11dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Support/CommandLine.h" 12dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Support/Debug.h" 13dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 14dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesusing namespace llvm; 15dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 16dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic cl::opt<bool> 17dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesDebugPM("debug-cgscc-pass-manager", cl::Hidden, 18dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines cl::desc("Print CGSCC pass management debugging information")); 19dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 20dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesPreservedAnalyses CGSCCPassManager::run(LazyCallGraph::SCC *C, 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisManager *AM) { 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PreservedAnalyses PA = PreservedAnalyses::all(); 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 24dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (DebugPM) 25dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << "Starting CGSCC pass manager run.\n"; 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) { 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (DebugPM) 29dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << "Running CGSCC pass: " << Passes[Idx]->name() << "\n"; 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PreservedAnalyses PassPA = Passes[Idx]->run(C, AM); 32dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (AM) 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AM->invalidate(C, PassPA); 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PA.intersect(std::move(PassPA)); 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (DebugPM) 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << "Finished CGSCC pass manager run.\n"; 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 40dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return PA; 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 42dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 43dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool CGSCCAnalysisManager::empty() const { 44dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(CGSCCAnalysisResults.empty() == CGSCCAnalysisResultLists.empty() && 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "The storage and index of analysis results disagree on how many there " 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "are!"); 47dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return CGSCCAnalysisResults.empty(); 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid CGSCCAnalysisManager::clear() { 51dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResults.clear(); 52dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResultLists.clear(); 53dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 54dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesCGSCCAnalysisManager::ResultConceptT & 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesCGSCCAnalysisManager::getResultImpl(void *PassID, LazyCallGraph::SCC *C) { 57dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResultMapT::iterator RI; 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool Inserted; 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::tie(RI, Inserted) = CGSCCAnalysisResults.insert(std::make_pair( 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::make_pair(PassID, C), CGSCCAnalysisResultListT::iterator())); 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If we don't have a cached result for this function, look up the pass and 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // run it to produce a result, which we then add to the cache. 64dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Inserted) { 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResultListT &ResultList = CGSCCAnalysisResultLists[C]; 66dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ResultList.emplace_back(PassID, lookupPass(PassID).run(C, this)); 67dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RI->second = std::prev(ResultList.end()); 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 69dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 70dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return *RI->second->second; 71dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 73dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesCGSCCAnalysisManager::ResultConceptT * 74dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesCGSCCAnalysisManager::getCachedResultImpl(void *PassID, 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC *C) const { 76dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResultMapT::const_iterator RI = 77dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResults.find(std::make_pair(PassID, C)); 78dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return RI == CGSCCAnalysisResults.end() ? nullptr : &*RI->second->second; 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 80dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 81dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid CGSCCAnalysisManager::invalidateImpl(void *PassID, LazyCallGraph::SCC *C) { 82dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResultMapT::iterator RI = 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResults.find(std::make_pair(PassID, C)); 84dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (RI == CGSCCAnalysisResults.end()) 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 86dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 87dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResultLists[C].erase(RI->second); 88dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 89dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 90dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid CGSCCAnalysisManager::invalidateImpl(LazyCallGraph::SCC *C, 91dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const PreservedAnalyses &PA) { 92dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Clear all the invalidated results associated specifically with this 93dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // function. 94dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallVector<void *, 8> InvalidatedPassIDs; 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResultListT &ResultsList = CGSCCAnalysisResultLists[C]; 96dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (CGSCCAnalysisResultListT::iterator I = ResultsList.begin(), 97dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines E = ResultsList.end(); 98dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines I != E;) 99dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (I->second->invalidate(C, PA)) { 100dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines InvalidatedPassIDs.push_back(I->first); 101dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines I = ResultsList.erase(I); 102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } else { 103dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++I; 104dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 105dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (!InvalidatedPassIDs.empty()) 106dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResults.erase( 107dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::make_pair(InvalidatedPassIDs.pop_back_val(), C)); 108dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGSCCAnalysisResultLists.erase(C); 109dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 110dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 111dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hineschar CGSCCAnalysisManagerModuleProxy::PassID; 112dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 113dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesCGSCCAnalysisManagerModuleProxy::Result 114dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesCGSCCAnalysisManagerModuleProxy::run(Module *M) { 115dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(CGAM->empty() && "CGSCC analyses ran prior to the module proxy!"); 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Result(*CGAM); 117dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 118dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesCGSCCAnalysisManagerModuleProxy::Result::~Result() { 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Clear out the analysis manager if we're being destroyed -- it means we 121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // didn't even see an invalidate call when we got invalidated. 122dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGAM->clear(); 123dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 124dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 125dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool CGSCCAnalysisManagerModuleProxy::Result::invalidate( 126dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Module *M, const PreservedAnalyses &PA) { 127dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If this proxy isn't marked as preserved, then we can't even invalidate 128dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // individual CGSCC analyses, there may be an invalid set of SCC objects in 129dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // the cache making it impossible to incrementally preserve them. 130dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Just clear the entire manager. 131dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!PA.preserved(ID())) 132dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CGAM->clear(); 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 134dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Return false to indicate that this result is still a valid proxy. 135dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 136dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 137dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 138dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hineschar ModuleAnalysisManagerCGSCCProxy::PassID; 139dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 140dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hineschar FunctionAnalysisManagerCGSCCProxy::PassID; 141dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 142dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesFunctionAnalysisManagerCGSCCProxy::Result 143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesFunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC *C) { 144dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(FAM->empty() && "Function analyses ran prior to the CGSCC proxy!"); 145dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Result(*FAM); 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 147dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 148dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesFunctionAnalysisManagerCGSCCProxy::Result::~Result() { 149dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Clear out the analysis manager if we're being destroyed -- it means we 150dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // didn't even see an invalidate call when we got invalidated. 151dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines FAM->clear(); 152dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 153dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 154dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool FunctionAnalysisManagerCGSCCProxy::Result::invalidate( 155dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LazyCallGraph::SCC *C, const PreservedAnalyses &PA) { 156dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If this proxy isn't marked as preserved, then we can't even invalidate 157dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // individual function analyses, there may be an invalid set of Function 158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // objects in the cache making it impossible to incrementally preserve them. 159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Just clear the entire manager. 160dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!PA.preserved(ID())) 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines FAM->clear(); 162dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Return false to indicate that this result is still a valid proxy. 164dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 165dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 166dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 167dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hineschar CGSCCAnalysisManagerFunctionProxy::PassID; 168