LLVM API Documentation
00001 //===- PrintSCC.cpp - Enumerate SCCs in some key graphs -------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file provides passes to print out SCCs in a CFG or a CallGraph. 00011 // Normally, you would not use these passes; instead, you would use the 00012 // scc_iterator directly to enumerate SCCs and process them in some way. These 00013 // passes serve three purposes: 00014 // 00015 // (1) As a reference for how to use the scc_iterator. 00016 // (2) To print out the SCCs for a CFG or a CallGraph: 00017 // analyze -cfgscc to print the SCCs in each CFG of a module. 00018 // analyze -cfgscc -stats to print the #SCCs and the maximum SCC size. 00019 // analyze -cfgscc -debug > /dev/null to watch the algorithm in action. 00020 // 00021 // and similarly: 00022 // analyze -callscc [-stats] [-debug] to print SCCs in the CallGraph 00023 // 00024 // (3) To test the scc_iterator. 00025 // 00026 //===----------------------------------------------------------------------===// 00027 00028 #include "llvm/Pass.h" 00029 #include "llvm/Module.h" 00030 #include "llvm/Analysis/CallGraph.h" 00031 #include "llvm/Support/CFG.h" 00032 #include "llvm/ADT/SCCIterator.h" 00033 #include <iostream> 00034 using namespace llvm; 00035 00036 namespace { 00037 struct CFGSCC : public FunctionPass { 00038 bool runOnFunction(Function& func); 00039 00040 void print(std::ostream &O) const { } 00041 00042 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00043 AU.setPreservesAll(); 00044 } 00045 }; 00046 00047 struct CallGraphSCC : public ModulePass { 00048 // run - Print out SCCs in the call graph for the specified module. 00049 bool runOnModule(Module &M); 00050 00051 void print(std::ostream &O) const { } 00052 00053 // getAnalysisUsage - This pass requires the CallGraph. 00054 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00055 AU.setPreservesAll(); 00056 AU.addRequired<CallGraph>(); 00057 } 00058 }; 00059 00060 RegisterAnalysis<CFGSCC> 00061 Y("cfgscc", "Print SCCs of each function CFG"); 00062 00063 RegisterAnalysis<CallGraphSCC> 00064 Z("callscc", "Print SCCs of the Call Graph"); 00065 } 00066 00067 bool CFGSCC::runOnFunction(Function &F) { 00068 unsigned sccNum = 0; 00069 std::cout << "SCCs for Function " << F.getName() << " in PostOrder:"; 00070 for (scc_iterator<Function*> SCCI = scc_begin(&F), 00071 E = scc_end(&F); SCCI != E; ++SCCI) { 00072 std::vector<BasicBlock*> &nextSCC = *SCCI; 00073 std::cout << "\nSCC #" << ++sccNum << " : "; 00074 for (std::vector<BasicBlock*>::const_iterator I = nextSCC.begin(), 00075 E = nextSCC.end(); I != E; ++I) 00076 std::cout << (*I)->getName() << ", "; 00077 if (nextSCC.size() == 1 && SCCI.hasLoop()) 00078 std::cout << " (Has self-loop)."; 00079 } 00080 std::cout << "\n"; 00081 00082 return true; 00083 } 00084 00085 00086 // run - Print out SCCs in the call graph for the specified module. 00087 bool CallGraphSCC::runOnModule(Module &M) { 00088 CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); 00089 unsigned sccNum = 0; 00090 std::cout << "SCCs for the program in PostOrder:"; 00091 for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), 00092 E = scc_end(rootNode); SCCI != E; ++SCCI) { 00093 const std::vector<CallGraphNode*> &nextSCC = *SCCI; 00094 std::cout << "\nSCC #" << ++sccNum << " : "; 00095 for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(), 00096 E = nextSCC.end(); I != E; ++I) 00097 std::cout << ((*I)->getFunction() ? (*I)->getFunction()->getName() 00098 : std::string("Indirect CallGraph node")) << ", "; 00099 if (nextSCC.size() == 1 && SCCI.hasLoop()) 00100 std::cout << " (Has self-loop)."; 00101 } 00102 std::cout << "\n"; 00103 00104 return true; 00105 }