44#define DEBUG_TYPE "cgscc-passmgr"
51STATISTIC(MaxSCCIterations,
"Maximum CGSCCPassMgr iterations on one SCC");
70 using ModulePass::doInitialization;
71 using ModulePass::doFinalization;
80 Info.setPreservesAll();
93 P->dumpPassStructure(
Offset + 1);
98 Pass *getContainedPass(
unsigned N) {
99 assert(
N < PassVector.size() &&
"Pass number out of range!");
100 return static_cast<Pass *
>(PassVector[
N]);
109 bool &DevirtualizedCall);
113 bool &DevirtualizedCall);
115 bool IsCheckingMode);
120char CGPassManager::ID = 0;
124 bool &DevirtualizedCall) {
125 bool Changed =
false;
131 if (!CallGraphUpToDate) {
132 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG,
false);
133 CallGraphUpToDate =
true;
139 bool EmitICRemark =
M.shouldEmitInstrCountChangedRemark();
142 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
147 SCCCount =
M.getInstructionCount();
152 static_cast<int64_t
>(SCCCount) -
static_cast<int64_t
>(
InstrCount);
153 emitInstrCountChangedRemark(
P, M, Delta,
InstrCount,
154 FunctionToInstrCount);
164 RefreshCallGraph(CurSCC, CG,
true);
171 "Invalid CGPassManager member");
182 F->getContext().yield();
188 if (Changed && CallGraphUpToDate) {
189 LLVM_DEBUG(
dbgs() <<
"CGSCCPASSMGR: Pass Dirtied SCC: " <<
P->getPassName()
191 CallGraphUpToDate =
false;
212 : CurSCC) CGN->dump(););
214 bool MadeChange =
false;
215 bool DevirtualizedCall =
false;
218 unsigned FunctionNo = 0;
220 SCCIdx != E; ++SCCIdx, ++FunctionNo) {
223 if (!
F ||
F->isDeclaration())
continue;
230 unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
237 bool WasLast =
I + 1 == CGNEnd;
259 if (RemoveAndCheckForDone(
I))
266 auto *
Call = dyn_cast_or_null<CallBase>(*
I->first);
273 "CallGraphSCCPass did not update the CallGraph correctly!");
276 if (!
I->second->getFunction())
277 ++NumIndirectRemoved;
281 if (RemoveAndCheckForDone(
I))
286 assert(!Calls.
count(Call) &&
"Call site occurs in node multiple times");
291 if (!Callee || !(
Callee->isIntrinsic()))
292 Calls.
insert(std::make_pair(Call,
I->second));
299 unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
303 auto *
Call = dyn_cast<CallBase>(&
I);
307 if (Callee &&
Callee->isIntrinsic())
323 if (ExistingIt != Calls.
end()) {
327 Calls.
erase(ExistingIt);
338 if (CheckingMode &&
Call->getCalledFunction() &&
343 "CallGraphSCCPass did not update the CallGraph correctly!");
353 DevirtualizedCall =
true;
355 <<
Callee->getName() <<
"'\n");
368 "CallGraphSCCPass did not update the CallGraph correctly!");
394 if (NumIndirectRemoved > NumIndirectAdded &&
395 NumDirectRemoved < NumDirectAdded)
396 DevirtualizedCall =
true;
402 assert(Calls.
empty() &&
"Dangling pointers found in call sites map");
406 if ((FunctionNo & 15) == 15)
411 dbgs() <<
"CGSCCPASSMGR: Refreshed SCC is now:\n";
414 if (DevirtualizedCall)
415 dbgs() <<
"CGSCCPASSMGR: Refresh devirtualized a call!\n";
417 dbgs() <<
"CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
421 return DevirtualizedCall;
428 bool &DevirtualizedCall) {
429 bool Changed =
false;
438 bool CallGraphUpToDate =
true;
441 for (
unsigned PassNo = 0, e = getNumContainedPasses();
442 PassNo !=
e; ++PassNo) {
443 Pass *
P = getContainedPass(PassNo);
447 if (isPassDebuggingExecutionsOrMore()) {
448 std::string Functions;
462 initializeAnalysisImpl(
P);
464#ifdef EXPENSIVE_CHECKS
470 RunPassOnSCC(
P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall);
472 Changed |= LocalChanged;
474#ifdef EXPENSIVE_CHECKS
475 if (!LocalChanged && (RefHash !=
P->structuralHash(CG.
getModule()))) {
476 llvm::errs() <<
"Pass modifies its input and doesn't report it: "
477 <<
P->getPassName() <<
"\n";
485 verifyPreservedAnalysis(
P);
487 removeNotPreservedAnalysis(
P);
488 recordAvailableAnalysis(
P);
494 if (!CallGraphUpToDate)
495 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG,
false);
501bool CGPassManager::runOnModule(
Module &M) {
502 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
503 bool Changed = doInitialization(CG);
512 const std::vector<CallGraphNode *> &NodeVec = *CGI;
513 CurSCC.initialize(NodeVec);
528 unsigned Iteration = 0;
529 bool DevirtualizedCall =
false;
532 <<
" SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
534 DevirtualizedCall =
false;
535 Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
538 if (DevirtualizedCall)
541 <<
" times, due to -max-devirt-iterations\n");
543 MaxSCCIterations.updateMax(Iteration);
545 Changed |= doFinalization(CG);
550bool CGPassManager::doInitialization(
CallGraph &CG) {
551 bool Changed =
false;
552 for (
unsigned i = 0, e = getNumContainedPasses(); i !=
e; ++i) {
553 if (
PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
555 "Invalid CGPassManager member");
565bool CGPassManager::doFinalization(
CallGraph &CG) {
566 bool Changed =
false;
567 for (
unsigned i = 0, e = getNumContainedPasses(); i !=
e; ++i) {
568 if (
PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
570 "Invalid CGPassManager member");
586 assert(Old != New &&
"Should not replace node with self");
587 for (
unsigned i = 0; ; ++i) {
588 assert(i != Nodes.size() &&
"Node not in SCC");
589 if (Nodes[i] != Old)
continue;
593 Nodes.erase(Nodes.begin() + i);
615 while (!PMS.
empty() &&
619 assert(!PMS.
empty() &&
"Unable to handle Call Graph Pass");
623 CGP = (CGPassManager*)PMS.
top();
626 assert(!PMS.
empty() &&
"Unable to create Call Graph Pass Manager");
630 CGP =
new CGPassManager();
679 bool BannerPrinted =
false;
680 auto PrintBannerOnce = [&]() {
684 BannerPrinted =
true;
691 SCC.getCallGraph().getModule().print(
OS,
nullptr);
694 bool FoundFunction =
false;
698 FoundFunction =
true;
706 OS <<
"\nPrinting <null> Function\n";
709 if (NeedModule && FoundFunction) {
712 SCC.getCallGraph().getModule().print(
OS,
nullptr);
717 StringRef getPassName()
const override {
return "Print CallGraph IR"; }
722char PrintCallGraphPass::ID = 0;
725 const std::string &Banner)
const {
726 return new PrintCallGraphPass(Banner,
OS);
730 std::string
Desc =
"SCC (";
736 Desc +=
F->getName();
738 Desc +=
"<<null function>>";
746 SCC.getCallGraph().getModule().getContext().getOptPassGate();
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Analysis containing CSE Info
static std::string getDescription(const CallGraphSCC &SCC)
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
static unsigned InstrCount
This file defines the DenseMap class.
Module.h This file contains the declarations for the Module class.
This file declares the interface for bisecting optimizations.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
This header defines classes/functions to handle pass execution timing information with interfaces for...
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
A node in the call graph for a module.
void print(raw_ostream &OS) const
void addCalledFunction(CallBase *Call, CallGraphNode *M)
Adds a function to the list of functions called by this one.
void replaceCallEdge(CallBase &Call, CallBase &NewCall, CallGraphNode *NewNode)
Replaces the edge in the node for the specified call site with a new one.
void dump() const
Print out this call graph node.
Function * getFunction() const
Returns the function that this call graph node represents.
std::vector< CallRecord >::iterator iterator
void removeCallEdge(iterator I)
Pass * createPrinterPass(raw_ostream &OS, const std::string &Banner) const override
createPrinterPass - Get a pass that prints the Module corresponding to a CallGraph.
virtual bool runOnSCC(CallGraphSCC &SCC)=0
runOnSCC - This method should be implemented by the subclass to perform whatever action is necessary ...
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph.
bool skipSCC(CallGraphSCC &SCC) const
Optional passes call this function to check whether the pass should be skipped.
void assignPassManager(PMStack &PMS, PassManagerType PMT) override
Assign pass manager to manager this pass.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
std::vector< CallGraphNode * >::const_iterator iterator
void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)
ReplaceNode - This informs the SCC and the pass manager that the specified Old node has been deleted,...
void DeleteNode(CallGraphNode *Old)
DeleteNode - This informs the SCC and the pass manager that the specified Old node has been deleted.
The ModulePass which wraps up a CallGraph and the logic to build it.
The basic data container for the call graph of a Module of IR.
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist.
CallGraphNode * getCallsExternalNode() const
Module & getModule() const
Returns the module the call graph corresponds to.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
This pass is required by interprocedural register allocation.
FPPassManager manages BBPassManagers and FunctionPasses.
bool runOnFunction(Function &F)
run - Execute all of the passes scheduled for execution.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
virtual bool runOnModule(Module &M)=0
runOnModule - Virtual method overriden by subclasses to process the module being operated on.
A Module instance is used to store all the information related to an LLVM module.
Extensions to this class implement mechanisms to disable passes and individual optimizations at compi...
virtual bool isEnabled() const
isEnabled() should return true before calling shouldRunPass().
virtual bool shouldRunPass(const StringRef PassName, StringRef IRDescription)
IRDescription is a textual description of the IR unit the pass is running over.
PMDataManager provides the common place to manage the analysis data used by pass managers.
void dumpLastUses(Pass *P, unsigned Offset) const
virtual Pass * getAsPass()=0
PMTopLevelManager * getTopLevelManager()
unsigned getNumContainedPasses() const
virtual PassManagerType getPassManagerType() const
PMStack - This class implements a stack data structure of PMDataManager pointers.
PMDataManager * top() const
void push(PMDataManager *PM)
PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers.
void addIndirectPassManager(PMDataManager *Manager)
void schedulePass(Pass *P)
Schedule pass P for execution.
Pass interface - Implemented by all 'passes'.
virtual PMDataManager * getAsPMDataManager()
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
virtual bool doFinalization(Module &)
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
virtual void dumpPassStructure(unsigned Offset=0)
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
StringRef - Represent a constant reference to a string, i.e.
The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
A raw_ostream that writes to an std::string.
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
bool isAtEnd() const
Direct loop termination test which is more efficient than comparison with end().
void ReplaceNode(NodeRef Old, NodeRef New)
This informs the scc_iterator that the specified Old node has been deleted, and New is to be used in ...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
bool forcePrintModuleIR()
PassManagerType
Different types of internal pass managers.
@ PMT_CallGraphPassManager
CGPassManager.
@ PMT_FunctionPassManager
FPPassManager.
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Timer * getPassTimer(Pass *)
Request the timer for this legacy-pass-manager's pass instance.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isFunctionInPrintList(StringRef FunctionName)
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void forEachCallbackFunction(const CallBase &CB, UnaryFunction Func)
Apply function Func to each CB's callback function.
cl::opt< unsigned > MaxDevirtIterations("max-devirt-iterations", cl::ReallyHidden, cl::init(4))
Description of the encoding of one expression Op.