Go to the documentation of this file.
44 #define DEBUG_TYPE "cgscc-passmgr"
49 STATISTIC(MaxSCCIterations,
"Maximum CGSCCPassMgr iterations on one SCC");
66 bool runOnModule(
Module &M)
override;
78 Info.setPreservesAll();
81 StringRef getPassName()
const override {
return "CallGraph Pass Manager"; }
84 Pass *getAsPass()
override {
return this; }
87 void dumpPassStructure(
unsigned Offset)
override {
91 P->dumpPassStructure(
Offset + 1);
96 Pass *getContainedPass(
unsigned N) {
97 assert(
N < PassVector.size() &&
"Pass number out of range!");
98 return static_cast<Pass *
>(PassVector[
N]);
107 bool &DevirtualizedCall);
111 bool &DevirtualizedCall);
113 bool IsCheckingMode);
122 bool &DevirtualizedCall) {
123 bool Changed =
false;
129 if (!CallGraphUpToDate) {
130 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG,
false);
131 CallGraphUpToDate =
true;
137 bool EmitICRemark =
M.shouldEmitInstrCountChangedRemark();
140 InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
145 SCCCount =
M.getInstructionCount();
150 static_cast<int64_t
>(SCCCount) -
static_cast<int64_t
>(
InstrCount);
151 emitInstrCountChangedRemark(
P, M, Delta,
InstrCount,
152 FunctionToInstrCount);
162 RefreshCallGraph(CurSCC, CG,
true);
169 "Invalid CGPassManager member");
180 F->getContext().yield();
186 if (Changed && CallGraphUpToDate) {
187 LLVM_DEBUG(
dbgs() <<
"CGSCCPASSMGR: Pass Dirtied SCC: " <<
P->getPassName()
189 CallGraphUpToDate =
false;
210 : CurSCC) CGN->
dump(););
212 bool MadeChange =
false;
213 bool DevirtualizedCall =
false;
216 unsigned FunctionNo = 0;
218 SCCIdx !=
E; ++SCCIdx, ++FunctionNo) {
221 if (!
F ||
F->isDeclaration())
continue;
228 unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
235 bool WasLast =
I + 1 == CGNEnd;
257 if (RemoveAndCheckForDone(
I))
264 auto *
Call = dyn_cast_or_null<CallBase>(*
I->first);
275 (
Call->getCalledFunction() &&
276 Call->getCalledFunction()->isIntrinsic() &&
279 "CallGraphSCCPass did not update the CallGraph correctly!");
282 if (!
I->second->getFunction())
283 ++NumIndirectRemoved;
287 if (RemoveAndCheckForDone(
I))
292 assert(!Calls.
count(Call) &&
"Call site occurs in node multiple times");
297 if (!Callee || !(
Callee->isIntrinsic()))
298 Calls.
insert(std::make_pair(Call,
I->second));
305 unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
309 auto *
Call = dyn_cast<CallBase>(&
I);
313 if (Callee &&
Callee->isIntrinsic())
329 if (ExistingIt != Calls.
end()) {
333 Calls.
erase(ExistingIt);
344 if (CheckingMode &&
Call->getCalledFunction() &&
349 "CallGraphSCCPass did not update the CallGraph correctly!");
359 DevirtualizedCall =
true;
361 <<
Callee->getName() <<
"'\n");
374 "CallGraphSCCPass did not update the CallGraph correctly!");
400 if (NumIndirectRemoved > NumIndirectAdded &&
401 NumDirectRemoved < NumDirectAdded)
402 DevirtualizedCall =
true;
408 assert(Calls.
empty() &&
"Dangling pointers found in call sites map");
412 if ((FunctionNo & 15) == 15)
417 dbgs() <<
"CGSCCPASSMGR: Refreshed SCC is now:\n";
420 if (DevirtualizedCall)
421 dbgs() <<
"CGSCCPASSMGR: Refresh devirtualized a call!\n";
423 dbgs() <<
"CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
427 return DevirtualizedCall;
434 bool &DevirtualizedCall) {
435 bool Changed =
false;
444 bool CallGraphUpToDate =
true;
447 for (
unsigned PassNo = 0,
e = getNumContainedPasses();
448 PassNo !=
e; ++PassNo) {
449 Pass *
P = getContainedPass(PassNo);
453 if (isPassDebuggingExecutionsOrMore()) {
454 std::string Functions;
468 initializeAnalysisImpl(
P);
470 #ifdef EXPENSIVE_CHECKS
471 uint64_t RefHash = StructuralHash(CG.
getModule());
476 RunPassOnSCC(
P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall);
478 Changed |= LocalChanged;
480 #ifdef EXPENSIVE_CHECKS
481 if (!LocalChanged && (RefHash != StructuralHash(CG.
getModule()))) {
482 llvm::errs() <<
"Pass modifies its input and doesn't report it: "
483 <<
P->getPassName() <<
"\n";
491 verifyPreservedAnalysis(
P);
493 removeNotPreservedAnalysis(
P);
494 recordAvailableAnalysis(
P);
500 if (!CallGraphUpToDate)
501 DevirtualizedCall |= RefreshCallGraph(CurSCC, CG,
false);
507 bool CGPassManager::runOnModule(
Module &M) {
508 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
509 bool Changed = doInitialization(CG);
518 const std::vector<CallGraphNode *> &NodeVec = *CGI;
519 CurSCC.initialize(NodeVec);
534 unsigned Iteration = 0;
535 bool DevirtualizedCall =
false;
538 <<
" SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
540 DevirtualizedCall =
false;
541 Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
544 if (DevirtualizedCall)
547 <<
" times, due to -max-devirt-iterations\n");
549 MaxSCCIterations.updateMax(Iteration);
551 Changed |= doFinalization(CG);
556 bool CGPassManager::doInitialization(
CallGraph &CG) {
557 bool Changed =
false;
558 for (
unsigned i = 0,
e = getNumContainedPasses();
i !=
e; ++
i) {
559 if (
PMDataManager *PM = getContainedPass(
i)->getAsPMDataManager()) {
561 "Invalid CGPassManager member");
571 bool CGPassManager::doFinalization(
CallGraph &CG) {
572 bool Changed =
false;
573 for (
unsigned i = 0,
e = getNumContainedPasses();
i !=
e; ++
i) {
574 if (
PMDataManager *PM = getContainedPass(
i)->getAsPMDataManager()) {
576 "Invalid CGPassManager member");
592 assert(Old != New &&
"Should not replace node with self");
593 for (
unsigned i = 0; ; ++
i) {
594 assert(
i != Nodes.size() &&
"Node not in SCC");
595 if (Nodes[
i] != Old)
continue;
599 Nodes.erase(Nodes.begin() +
i);
621 while (!PMS.
empty() &&
625 assert(!PMS.
empty() &&
"Unable to handle Call Graph Pass");
629 CGP = (CGPassManager*)PMS.
top();
632 assert(!PMS.
empty() &&
"Unable to create Call Graph Pass Manager");
636 CGP =
new CGPassManager();
677 PrintCallGraphPass(
const std::string &
B,
raw_ostream &OS)
685 bool BannerPrinted =
false;
686 auto PrintBannerOnce = [&]() {
690 BannerPrinted =
true;
700 bool FoundFunction =
false;
704 FoundFunction =
true;
712 OS <<
"\nPrinting <null> Function\n";
715 if (NeedModule && FoundFunction) {
718 SCC.getCallGraph().getModule().print(OS,
nullptr);
723 StringRef getPassName()
const override {
return "Print CallGraph IR"; }
731 const std::string &Banner)
const {
732 return new PrintCallGraphPass(Banner, OS);
736 std::string Desc =
"SCC (";
742 Desc +=
F->getName();
744 Desc +=
"<<null function>>";
This class represents lattice values for constants.
bool runOnFunction(Function &F)
run - Execute all of the passes scheduled for execution.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
std::vector< CallRecord >::iterator iterator
@ PMT_CallGraphPassManager
CGPassManager.
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
void schedulePass(Pass *P)
Schedule pass P for execution.
A raw_ostream that writes to an std::string.
virtual bool isEnabled() const
isEnabled() should return true before calling shouldRunPass().
The basic data container for the call graph of a Module of IR.
bool erase(const KeyT &Val)
PassManagerType
Different types of internal pass managers.
static unsigned InstrCount
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
void push(PMDataManager *PM)
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void removeCallEdge(iterator I)
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 ...
cl::opt< unsigned > MaxDevirtIterations("max-devirt-iterations", cl::ReallyHidden, cl::init(4))
void addCalledFunction(CallBase *Call, CallGraphNode *M)
Adds a function to the list of functions called by this one.
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist.
PMDataManager provides the common place to manage the analysis data used by pass managers.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
The TimeRegion class is used as a helper class to call the startTimer() and stopTimer() methods of th...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void dump() const
Print out this call graph node.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Extensions to this class implement mechanisms to disable passes and individual optimizations at compi...
Represent the analysis usage information of a pass.
void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)
ReplaceNode - This informs the SCC and the pass manager that the specified Old node has been deleted,...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool skipSCC(CallGraphSCC &SCC) const
Optional passes call this function to check whether the pass should be skipped.
STATISTIC(NumFunctions, "Total number of functions")
This class implements an extremely fast bulk output stream that can only output to a stream.
A node in the call graph for a module.
Analysis containing CSE Info
PMDataManager * top() const
OptPassGate & getOptPassGate() const
Access the object which can disable optional passes and individual optimizations at compile time.
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
std::vector< CallGraphNode * >::const_iterator iterator
PMTopLevelManager * getTopLevelManager()
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph.
void DeleteNode(CallGraphNode *Old)
DeleteNode - This informs the SCC and the pass manager that the specified Old node has been deleted.
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
const CallGraph & getCallGraph()
The ModulePass which wraps up a CallGraph and the logic to build it.
Pass * createPrinterPass(raw_ostream &OS, const std::string &Banner) const override
createPrinterPass - Get a pass that prints the Module corresponding to a CallGraph.
Timer * getPassTimer(Pass *)
Request the timer for this legacy-pass-manager's pass instance.
initializer< Ty > init(const Ty &Val)
bool isFunctionInPrintList(StringRef FunctionName)
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This pass is required by interprocedural register allocation.
A Module instance is used to store all the information related to an LLVM module.
void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW, bool ShouldPreserveUseListOrder=false, bool IsForDebug=false) const
Print the module to an output stream with an optional AssemblyAnnotationWriter.
virtual bool doFinalization(Module &)
doFinalization - Virtual method overriden by subclasses to do any necessary clean up after all passes...
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
StringRef - Represent a constant reference to a string, i.e.
@ PMT_FunctionPassManager
FPPassManager.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
virtual PassManagerType getPassManagerType() const
this could be done in SelectionDAGISel along with other special for
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
LLVM_NODISCARD bool empty() const
amdgpu Simplify well known AMD library false FunctionCallee Callee
Function * getFunction() const
Returns the function that this call graph node represents.
FPPassManager manages BBPassManagers and FunctionPasses.
PMStack - This class implements a stack data structure of PMDataManager pointers.
static std::string getDescription(const CallGraphSCC &SCC)
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVMContext & getContext() const
Get the global data context.
void forEachCallbackFunction(const CallBase &CB, UnaryFunction Func)
Apply function Func to each CB's callback function.
void assignPassManager(PMStack &PMS, PassManagerType PMT) override
Assign pass manager to manager this pass.
void addIndirectPassManager(PMDataManager *Manager)
Module & getModule() const
Returns the module the call graph corresponds to.
bool isAtEnd() const
Direct loop termination test which is more efficient than comparison with end().
void print(raw_ostream &OS) const
Pass interface - Implemented by all 'passes'.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
bool forcePrintModuleIR()
PMTopLevelManager manages LastUser info and collects common APIs used by top level pass managers.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
virtual bool shouldRunPass(const Pass *P, StringRef IRDescription)
IRDescription is a textual description of the IR unit the pass is running over.
CallGraphNode * getCallsExternalNode() const
virtual bool runOnSCC(CallGraphSCC &SCC)=0
runOnSCC - This method should be implemented by the subclass to perform whatever action is necessary ...
void replaceCallEdge(CallBase &Call, CallBase &NewCall, CallGraphNode *NewNode)
Replaces the edge in the node for the specified call site with a new one.