1 //===- PrintSCC.cpp - Enumerate SCCs in some key graphs -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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 -cfgscc to print the SCCs in each CFG of a module.
18 // analyze -cfgscc -stats to print the #SCCs and the maximum SCC size.
19 // analyze -cfgscc -debug > /dev/null to watch the algorithm in action.
22 // analyze -callscc [-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/ADT/SCCIterator.h"
37 struct CFGSCC : public FunctionPass {
38 bool runOnFunction(Function& func);
40 void print(std::ostream &O) const { }
42 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
47 struct CallGraphSCC : public ModulePass {
48 // run - Print out SCCs in the call graph for the specified module.
49 bool runOnModule(Module &M);
51 void print(std::ostream &O) const { }
53 // getAnalysisUsage - This pass requires the CallGraph.
54 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
56 AU.addRequired<CallGraph>();
60 RegisterAnalysis<CFGSCC>
61 Y("cfgscc", "Print SCCs of each function CFG");
63 RegisterAnalysis<CallGraphSCC>
64 Z("callscc", "Print SCCs of the Call Graph");
67 bool CFGSCC::runOnFunction(Function &F) {
69 std::cout << "SCCs for Function " << F.getName() << " in PostOrder:";
70 for (scc_iterator<Function*> SCCI = scc_begin(&F),
71 E = scc_end(&F); SCCI != E; ++SCCI) {
72 std::vector<BasicBlock*> &nextSCC = *SCCI;
73 std::cout << "\nSCC #" << ++sccNum << " : ";
74 for (std::vector<BasicBlock*>::const_iterator I = nextSCC.begin(),
75 E = nextSCC.end(); I != E; ++I)
76 std::cout << (*I)->getName() << ", ";
77 if (nextSCC.size() == 1 && SCCI.hasLoop())
78 std::cout << " (Has self-loop).";
86 // run - Print out SCCs in the call graph for the specified module.
87 bool CallGraphSCC::runOnModule(Module &M) {
88 CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot();
90 std::cout << "SCCs for the program in PostOrder:";
91 for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode),
92 E = scc_end(rootNode); SCCI != E; ++SCCI) {
93 const std::vector<CallGraphNode*> &nextSCC = *SCCI;
94 std::cout << "\nSCC #" << ++sccNum << " : ";
95 for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(),
96 E = nextSCC.end(); I != E; ++I)
97 std::cout << ((*I)->getFunction() ? (*I)->getFunction()->getName()
98 : std::string("Indirect CallGraph node")) << ", ";
99 if (nextSCC.size() == 1 && SCCI.hasLoop())
100 std::cout << " (Has self-loop).";