1 //===- PrintSCC.cpp - Enumerate SCCs in some key graphs ---------*- C++ -*-===//
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 // TarjanSCCIterator directly to enumerate SCCs and process them in some way.
6 // These passes serve three purposes:
7 // (1) As a reference for how to use the TarjanSCCIterator.
8 // (2) To print out the SCCs for a CFG or a CallGraph:
9 // analyze -cfgscc to print the SCCs in each CFG of a module.
10 // analyze -cfgscc -stats to print the #SCCs and the maximum SCC size.
11 // analyze -cfgscc -debug > /dev/null to watch the algorithm in action.
14 // analyze -callscc [-stats] [-debug] to print SCCs in the CallGraph
16 // (3) To test the TarjanSCCIterator.
17 //===----------------------------------------------------------------------===//
19 #include "llvm/Pass.h"
20 #include "llvm/Module.h"
21 #include "llvm/Function.h"
22 #include "llvm/BasicBlock.h"
23 #include "llvm/Analysis/CallGraph.h"
24 #include "llvm/Support/CFG.h"
25 #include "Support/TarjanSCCIterator.h"
29 class CFGSCC: public FunctionPass {
31 bool runOnFunction(Function& func) {
32 unsigned long sccNum = 0;
33 const SCC<Function*>* nextSCC;
34 std::cout << "SCCs for Function " << func.getName() << " in PostOrder:";
35 for (TarjanSCC_iterator<Function*> tarjSCCiter = tarj_begin(&func);
36 (nextSCC = *tarjSCCiter); ++tarjSCCiter)
38 std::cout << "\nSCC #" << ++sccNum << " : ";
39 for (SCC<Function*>::const_iterator I=nextSCC->begin(),E=nextSCC->end();
41 std::cout << (*I)->getName() << ", ";
42 if (nextSCC->size() == 1 && nextSCC->HasLoop())
43 std::cout << " (Has self-loop).";
49 void print(std::ostream &O) const { }
53 class CallGraphSCC: public Pass {
55 // run - Print out SCCs in the call graph for the specified module.
57 CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot();
58 unsigned long sccNum = 0;
59 const SCC<CallGraphNode*>* nextSCC;
60 std::cout << "SCCs for the program in PostOrder:";
61 for (TarjanSCC_iterator<CallGraphNode*> tarjSCCiter = tarj_begin(rootNode);
62 (nextSCC = *tarjSCCiter); ++tarjSCCiter)
64 std::cout << "\nSCC #" << ++sccNum << " : ";
65 for (SCC<CallGraphNode*>::const_iterator I=nextSCC->begin(),
66 E=nextSCC->end(); I != E; ++I)
67 std::cout << ((*I)->getFunction()? (*I)->getFunction()->getName()
68 : std::string("Null CallGraph node"))
70 if (nextSCC->size() == 1 && nextSCC->HasLoop())
71 std::cout << " (Has self-loop).";
78 void print(std::ostream &O) const { }
80 // getAnalysisUsage - This pass requires the CallGraph.
81 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
83 AU.addRequired<CallGraph>();
87 static RegisterAnalysis<CFGSCC>
88 Y("cfgscc", "Print SCCs of each function CFG");
90 static RegisterAnalysis<CallGraphSCC>
91 Z("callscc", "Print SCCs of the Call Graph");