1 //===- PrintSCC.cpp - Enumerate SCCs in some key graphs -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides passes to print out SCCs in a CFG or a CallGraph.
11 // Normally, you would not use these passes; instead, you would use the
12 // scc_iterator directly to enumerate SCCs and process them in some way. These
13 // passes serve three purposes:
15 // (1) As a reference for how to use the scc_iterator.
16 // (2) To print out the SCCs for a CFG or a CallGraph:
17 // analyze -print-cfg-sccs to print the SCCs in each CFG of a module.
18 // analyze -print-cfg-sccs -stats to print the #SCCs and the maximum SCC size.
19 // analyze -print-cfg-sccs -debug > /dev/null to watch the algorithm in action.
22 // analyze -print-callgraph-sccs [-stats] [-debug] to print SCCs in the CallGraph
24 // (3) To test the scc_iterator.
26 //===----------------------------------------------------------------------===//
28 #include "llvm/Pass.h"
29 #include "llvm/Module.h"
30 #include "llvm/Analysis/CallGraph.h"
31 #include "llvm/Support/CFG.h"
32 #include "llvm/Support/raw_ostream.h"
33 #include "llvm/ADT/SCCIterator.h"
37 struct CFGSCC
: public FunctionPass
{
38 static char ID
; // Pass identification, replacement for typeid
39 CFGSCC() : FunctionPass(ID
) {}
40 bool runOnFunction(Function
& func
);
42 void print(raw_ostream
&O
, const Module
* = 0) const { }
44 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
49 struct CallGraphSCC
: public ModulePass
{
50 static char ID
; // Pass identification, replacement for typeid
51 CallGraphSCC() : ModulePass(ID
) {}
53 // run - Print out SCCs in the call graph for the specified module.
54 bool runOnModule(Module
&M
);
56 void print(raw_ostream
&O
, const Module
* = 0) const { }
58 // getAnalysisUsage - This pass requires the CallGraph.
59 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
61 AU
.addRequired
<CallGraph
>();
67 Y("print-cfg-sccs", "Print SCCs of each function CFG");
69 char CallGraphSCC::ID
= 0;
70 RegisterPass
<CallGraphSCC
>
71 Z("print-callgraph-sccs", "Print SCCs of the Call Graph");
74 bool CFGSCC::runOnFunction(Function
&F
) {
76 outs() << "SCCs for Function " << F
.getName() << " in PostOrder:";
77 for (scc_iterator
<Function
*> SCCI
= scc_begin(&F
),
78 E
= scc_end(&F
); SCCI
!= E
; ++SCCI
) {
79 std::vector
<BasicBlock
*> &nextSCC
= *SCCI
;
80 outs() << "\nSCC #" << ++sccNum
<< " : ";
81 for (std::vector
<BasicBlock
*>::const_iterator I
= nextSCC
.begin(),
82 E
= nextSCC
.end(); I
!= E
; ++I
)
83 outs() << (*I
)->getName() << ", ";
84 if (nextSCC
.size() == 1 && SCCI
.hasLoop())
85 outs() << " (Has self-loop).";
93 // run - Print out SCCs in the call graph for the specified module.
94 bool CallGraphSCC::runOnModule(Module
&M
) {
95 CallGraphNode
* rootNode
= getAnalysis
<CallGraph
>().getRoot();
97 outs() << "SCCs for the program in PostOrder:";
98 for (scc_iterator
<CallGraphNode
*> SCCI
= scc_begin(rootNode
),
99 E
= scc_end(rootNode
); SCCI
!= E
; ++SCCI
) {
100 const std::vector
<CallGraphNode
*> &nextSCC
= *SCCI
;
101 outs() << "\nSCC #" << ++sccNum
<< " : ";
102 for (std::vector
<CallGraphNode
*>::const_iterator I
= nextSCC
.begin(),
103 E
= nextSCC
.end(); I
!= E
; ++I
)
104 outs() << ((*I
)->getFunction() ? (*I
)->getFunction()->getNameStr()
105 : std::string("external node")) << ", ";
106 if (nextSCC
.size() == 1 && SCCI
.hasLoop())
107 outs() << " (Has self-loop).";