136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===- PassManager.cpp - Infrastructure for managing & running IR passes --===// 2f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth// 3f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth// The LLVM Compiler Infrastructure 4f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth// 5f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth// This file is distributed under the University of Illinois Open Source 6f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth// License. See LICENSE.TXT for details. 7f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth// 8f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth//===----------------------------------------------------------------------===// 9f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 10f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth#include "llvm/ADT/STLExtras.h" 11dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/IR/LLVMContext.h" 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/PassManager.h" 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/CommandLine.h" 1436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/Debug.h" 15f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 16f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruthusing namespace llvm; 17f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic cl::opt<bool> 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesDebugPM("debug-pass-manager", cl::Hidden, 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::desc("Print pass management debugging information")); 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesPreservedAnalyses ModulePassManager::run(Module *M, ModuleAnalysisManager *AM) { 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PreservedAnalyses PA = PreservedAnalyses::all(); 2436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DebugPM) 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines dbgs() << "Starting module pass manager run.\n"; 27f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) { 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DebugPM) 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines dbgs() << "Running module pass: " << Passes[Idx]->name() << "\n"; 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PreservedAnalyses PassPA = Passes[Idx]->run(M, AM); 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (AM) 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AM->invalidate(M, PassPA); 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PA.intersect(std::move(PassPA)); 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines M->getContext().yield(); 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DebugPM) 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines dbgs() << "Finished module pass manager run.\n"; 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return PA; 44f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth} 45f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesModuleAnalysisManager::ResultConceptT & 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesModuleAnalysisManager::getResultImpl(void *PassID, Module *M) { 4836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ModuleAnalysisResultMapT::iterator RI; 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Inserted; 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::tie(RI, Inserted) = ModuleAnalysisResults.insert(std::make_pair( 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PassID, std::unique_ptr<detail::AnalysisResultConcept<Module *>>())); 52f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If we don't have a cached result for this module, look up the pass and run 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // it to produce a result, which we then add to the cache. 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Inserted) 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RI->second = std::move(lookupPass(PassID).run(M, this)); 57f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return *RI->second; 59f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth} 60f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesModuleAnalysisManager::ResultConceptT * 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesModuleAnalysisManager::getCachedResultImpl(void *PassID, Module *M) const { 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ModuleAnalysisResultMapT::const_iterator RI = 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ModuleAnalysisResults.find(PassID); 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return RI == ModuleAnalysisResults.end() ? nullptr : &*RI->second; 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid ModuleAnalysisManager::invalidateImpl(void *PassID, Module *M) { 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ModuleAnalysisResults.erase(PassID); 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid ModuleAnalysisManager::invalidateImpl(Module *M, 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const PreservedAnalyses &PA) { 74f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth // FIXME: This is a total hack based on the fact that erasure doesn't 75f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth // invalidate iteration for DenseMap. 76f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth for (ModuleAnalysisResultMapT::iterator I = ModuleAnalysisResults.begin(), 77f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth E = ModuleAnalysisResults.end(); 78f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth I != E; ++I) 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I->second->invalidate(M, PA)) 80f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth ModuleAnalysisResults.erase(I); 81f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth} 82f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesPreservedAnalyses FunctionPassManager::run(Function *F, 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FunctionAnalysisManager *AM) { 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PreservedAnalyses PA = PreservedAnalyses::all(); 86f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DebugPM) 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines dbgs() << "Starting function pass manager run.\n"; 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) { 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DebugPM) 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines dbgs() << "Running function pass: " << Passes[Idx]->name() << "\n"; 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PreservedAnalyses PassPA = Passes[Idx]->run(F, AM); 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (AM) 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AM->invalidate(F, PassPA); 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PA.intersect(std::move(PassPA)); 98dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 99dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines F->getContext().yield(); 100f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth } 101f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DebugPM) 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines dbgs() << "Finished function pass manager run.\n"; 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return PA; 106f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth} 107f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool FunctionAnalysisManager::empty() const { 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(FunctionAnalysisResults.empty() == 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FunctionAnalysisResultLists.empty() && 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "The storage and index of analysis results disagree on how many there " 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "are!"); 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return FunctionAnalysisResults.empty(); 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 115f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid FunctionAnalysisManager::clear() { 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FunctionAnalysisResults.clear(); 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FunctionAnalysisResultLists.clear(); 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesFunctionAnalysisManager::ResultConceptT & 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesFunctionAnalysisManager::getResultImpl(void *PassID, Function *F) { 123f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth FunctionAnalysisResultMapT::iterator RI; 124f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth bool Inserted; 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::tie(RI, Inserted) = FunctionAnalysisResults.insert(std::make_pair( 126f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth std::make_pair(PassID, F), FunctionAnalysisResultListT::iterator())); 127f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If we don't have a cached result for this function, look up the pass and 12936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // run it to produce a result, which we then add to the cache. 130f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth if (Inserted) { 131f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth FunctionAnalysisResultListT &ResultList = FunctionAnalysisResultLists[F]; 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ResultList.emplace_back(PassID, lookupPass(PassID).run(F, this)); 13336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines RI->second = std::prev(ResultList.end()); 134f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth } 135f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 136f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth return *RI->second->second; 137f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth} 138f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 13936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesFunctionAnalysisManager::ResultConceptT * 14036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesFunctionAnalysisManager::getCachedResultImpl(void *PassID, Function *F) const { 14136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FunctionAnalysisResultMapT::const_iterator RI = 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FunctionAnalysisResults.find(std::make_pair(PassID, F)); 143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return RI == FunctionAnalysisResults.end() ? nullptr : &*RI->second->second; 144f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth} 145f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid FunctionAnalysisManager::invalidateImpl(void *PassID, Function *F) { 147d515e98ebf711d7e80589e4029f27c206573b400Chandler Carruth FunctionAnalysisResultMapT::iterator RI = 148d515e98ebf711d7e80589e4029f27c206573b400Chandler Carruth FunctionAnalysisResults.find(std::make_pair(PassID, F)); 149f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth if (RI == FunctionAnalysisResults.end()) 150f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth return; 151f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth 152f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth FunctionAnalysisResultLists[F].erase(RI->second); 153f348c9782c5c31309dfd2d04e3dbee21fefe07ffChandler Carruth} 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid FunctionAnalysisManager::invalidateImpl(Function *F, 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const PreservedAnalyses &PA) { 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Clear all the invalidated results associated specifically with this 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // function. 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<void *, 8> InvalidatedPassIDs; 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FunctionAnalysisResultListT &ResultsList = FunctionAnalysisResultLists[F]; 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (FunctionAnalysisResultListT::iterator I = ResultsList.begin(), 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines E = ResultsList.end(); 16336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I != E;) 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I->second->invalidate(F, PA)) { 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines InvalidatedPassIDs.push_back(I->first); 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I = ResultsList.erase(I); 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } else { 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++I; 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 17036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines while (!InvalidatedPassIDs.empty()) 17136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FunctionAnalysisResults.erase( 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::make_pair(InvalidatedPassIDs.pop_back_val(), F)); 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (ResultsList.empty()) 174dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines FunctionAnalysisResultLists.erase(F); 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hineschar FunctionAnalysisManagerModuleProxy::PassID; 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesFunctionAnalysisManagerModuleProxy::Result 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesFunctionAnalysisManagerModuleProxy::run(Module *M) { 18136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(FAM->empty() && "Function analyses ran prior to the module proxy!"); 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Result(*FAM); 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesFunctionAnalysisManagerModuleProxy::Result::~Result() { 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Clear out the analysis manager if we're being destroyed -- it means we 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // didn't even see an invalidate call when we got invalidated. 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FAM->clear(); 18936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 19036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool FunctionAnalysisManagerModuleProxy::Result::invalidate( 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Module *M, const PreservedAnalyses &PA) { 19336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If this proxy isn't marked as preserved, then we can't even invalidate 19436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // individual function analyses, there may be an invalid set of Function 19536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // objects in the cache making it impossible to incrementally preserve them. 19636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Just clear the entire manager. 19736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!PA.preserved(ID())) 19836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines FAM->clear(); 19936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Return false to indicate that this result is still a valid proxy. 20136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 20236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 20336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hineschar ModuleAnalysisManagerFunctionProxy::PassID; 205