PrintSCC.cpp revision 23ebd75affba7de4a3bef20690609af9e42615e6
123ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner//===- PrintSCC.cpp - Enumerate SCCs in some key graphs -------------------===// 2c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// 3c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// This file provides passes to print out SCCs in a CFG or a CallGraph. 4c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// Normally, you would not use these passes; instead, you would use the 5c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// TarjanSCCIterator directly to enumerate SCCs and process them in some way. 6c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// These passes serve three purposes: 7c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// (1) As a reference for how to use the TarjanSCCIterator. 8c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// (2) To print out the SCCs for a CFG or a CallGraph: 9c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// analyze -cfgscc to print the SCCs in each CFG of a module. 10c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// analyze -cfgscc -stats to print the #SCCs and the maximum SCC size. 11c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// analyze -cfgscc -debug > /dev/null to watch the algorithm in action. 12c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// 13c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// and similarly: 14c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// analyze -callscc [-stats] [-debug] to print SCCs in the CallGraph 15c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// 16c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// (3) To test the TarjanSCCIterator. 1723ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner// 18c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve//===----------------------------------------------------------------------===// 19c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 20c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Pass.h" 21c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Module.h" 22c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Analysis/CallGraph.h" 23c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Support/CFG.h" 24c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "Support/TarjanSCCIterator.h" 25c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 26c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Advenamespace { 2723ebd75affba7de4a3bef20690609af9e42615e6Chris Lattnerstruct CFGSCC: public FunctionPass { 28c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve bool runOnFunction(Function& func) { 29c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve unsigned long sccNum = 0; 30c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve std::cout << "SCCs for Function " << func.getName() << " in PostOrder:"; 3123ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner for (TarjanSCC_iterator<Function*> I = tarj_begin(&func), 3223ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner E = tarj_end(&func); I != E; ++I) { 3323ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner SCC<Function*> &nextSCC = **I; 3423ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner std::cout << "\nSCC #" << ++sccNum << " : "; 3523ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner for (SCC<Function*>::const_iterator I = nextSCC.begin(),E = nextSCC.end(); 3623ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner I != E; ++I) 3723ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner std::cout << (*I)->getName() << ", "; 3823ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner if (nextSCC.size() == 1 && nextSCC.HasLoop()) 3923ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner std::cout << " (Has self-loop)."; 4023ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner } 41c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve std::cout << "\n"; 42c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 43c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve return true; 44c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve } 45c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve void print(std::ostream &O) const { } 46c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve}; 47c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 48c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 4923ebd75affba7de4a3bef20690609af9e42615e6Chris Lattnerstruct CallGraphSCC : public Pass { 50c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve // run - Print out SCCs in the call graph for the specified module. 5123ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner bool run(Module &M) { 52c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); 53c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve unsigned long sccNum = 0; 54c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve std::cout << "SCCs for the program in PostOrder:"; 5523ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner for (TarjanSCC_iterator<CallGraphNode*> SCCI = tarj_begin(rootNode), 5623ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner E = tarj_end(rootNode); SCCI != E; ++SCCI) { 5723ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner const SCC<CallGraphNode*> &nextSCC = **SCCI; 5823ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner std::cout << "\nSCC #" << ++sccNum << " : "; 5923ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner for (SCC<CallGraphNode*>::const_iterator I = nextSCC.begin(), 6023ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner E = nextSCC.end(); I != E; ++I) 6123ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner std::cout << ((*I)->getFunction() ? (*I)->getFunction()->getName() 6223ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner : std::string("Indirect CallGraph node")) << ", "; 6323ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner if (nextSCC.size() == 1 && nextSCC.HasLoop()) 6423ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner std::cout << " (Has self-loop)."; 6523ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner } 66c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve std::cout << "\n"; 67c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 68c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve return true; 69c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve } 70c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 71c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve void print(std::ostream &O) const { } 72c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 73c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve // getAnalysisUsage - This pass requires the CallGraph. 74c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve virtual void getAnalysisUsage(AnalysisUsage &AU) const { 75c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve AU.setPreservesAll(); 76c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve AU.addRequired<CallGraph>(); 77c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve } 78c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve}; 79c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 8023ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner RegisterAnalysis<CFGSCC> 8123ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner Y("cfgscc", "Print SCCs of each function CFG"); 82c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 8323ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner RegisterAnalysis<CallGraphSCC> 8423ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner Z("callscc", "Print SCCs of the Call Graph"); 85c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve} 86