1 //===- PrintSCC.cpp - Enumerate SCCs in some key graphs -------------------===//
3 // This file provides passes to print out SCCs in a CFG or a CallGraph.
4 // Normally, you would not use these passes; instead, you would use the
5 // scc_iterator directly to enumerate SCCs and process them in some way. These
6 // passes serve three purposes:
8 // (1) As a reference for how to use the scc_iterator.
9 // (2) To print out the SCCs for a CFG or a CallGraph:
10 // analyze -cfgscc to print the SCCs in each CFG of a module.
11 // analyze -cfgscc -stats to print the #SCCs and the maximum SCC size.
12 // analyze -cfgscc -debug > /dev/null to watch the algorithm in action.
15 // analyze -callscc [-stats] [-debug] to print SCCs in the CallGraph
17 // (3) To test the scc_iterator.
19 //===----------------------------------------------------------------------===//
21 #include "llvm/Pass.h"
22 #include "llvm/Module.h"
23 #include "llvm/Analysis/CallGraph.h"
24 #include "llvm/Support/CFG.h"
25 #include "Support/SCCIterator.h"
28 struct CFGSCC : public FunctionPass {
29 bool runOnFunction(Function& func);
31 void print(std::ostream &O) const { }
33 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
38 struct CallGraphSCC : public Pass {
39 // run - Print out SCCs in the call graph for the specified module.
42 void print(std::ostream &O) const { }
44 // getAnalysisUsage - This pass requires the CallGraph.
45 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
47 AU.addRequired<CallGraph>();
51 RegisterAnalysis<CFGSCC>
52 Y("cfgscc", "Print SCCs of each function CFG");
54 RegisterAnalysis<CallGraphSCC>
55 Z("callscc", "Print SCCs of the Call Graph");
58 bool CFGSCC::runOnFunction(Function &F) {
60 std::cout << "SCCs for Function " << F.getName() << " in PostOrder:";
61 for (scc_iterator<Function*> SCCI = scc_begin(&F),
62 E = scc_end(&F); SCCI != E; ++SCCI) {
63 std::vector<BasicBlock*> &nextSCC = *SCCI;
64 std::cout << "\nSCC #" << ++sccNum << " : ";
65 for (std::vector<BasicBlock*>::const_iterator I = nextSCC.begin(),
66 E = nextSCC.end(); I != E; ++I)
67 std::cout << (*I)->getName() << ", ";
68 if (nextSCC.size() == 1 && SCCI.hasLoop())
69 std::cout << " (Has self-loop).";
77 // run - Print out SCCs in the call graph for the specified module.
78 bool CallGraphSCC::run(Module &M) {
79 CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot();
81 std::cout << "SCCs for the program in PostOrder:";
82 for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode),
83 E = scc_end(rootNode); SCCI != E; ++SCCI) {
84 const std::vector<CallGraphNode*> &nextSCC = *SCCI;
85 std::cout << "\nSCC #" << ++sccNum << " : ";
86 for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(),
87 E = nextSCC.end(); I != E; ++I)
88 std::cout << ((*I)->getFunction() ? (*I)->getFunction()->getName()
89 : std::string("Indirect CallGraph node")) << ", ";
90 if (nextSCC.size() == 1 && SCCI.hasLoop())
91 std::cout << " (Has self-loop).";