PrintSCC.cpp revision 9f2a06e76d173ea20891457a22dc0f55c361844f
123ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner//===- PrintSCC.cpp - Enumerate SCCs in some key graphs -------------------===// 22b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file provides passes to print out SCCs in a CFG or a CallGraph. 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// Normally, you would not use these passes; instead, you would use the 521c62da287237d39d0d95004881ea4baae3be6daChris Lattner// TarjanSCCIterator directly to enumerate SCCs and process them in some way. 621c62da287237d39d0d95004881ea4baae3be6daChris Lattner// These passes serve three purposes: 72b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// (1) As a reference for how to use the TarjanSCCIterator. 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// (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. 1255b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner// 1355b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner// and similarly: 1455b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner// analyze -callscc [-stats] [-debug] to print SCCs in the CallGraph 1555b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner// 16c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// (3) To test the TarjanSCCIterator. 173ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands// 183ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands//===----------------------------------------------------------------------===// 193ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands 202b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman#include "llvm/Pass.h" 21c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Module.h" 223ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands#include "llvm/Analysis/CallGraph.h" 232b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman#include "llvm/Support/CFG.h" 2455b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner#include "Support/TarjanSCCIterator.h" 2523ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner 26c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Advenamespace { 27c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve struct CFGSCC : public FunctionPass { 28c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve bool runOnFunction(Function& func); 29c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 30c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve void print(std::ostream &O) const { } 31c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 32ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer AU.setPreservesAll(); 3468d033cc94d64c49aa442b3990386f95f95d5637Chris Lattner } 35d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke }; 36c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 378d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner struct CallGraphSCC : public Pass { 381997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel // run - Print out SCCs in the call graph for the specified module. 3990c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson bool run(Module &M); 408d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 41c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve void print(std::ostream &O) const { } 4245cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner 43c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve // getAnalysisUsage - This pass requires the CallGraph. 448d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 458d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner AU.setPreservesAll(); 4623ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner AU.addRequired<CallGraph>(); 478d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner } 48c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve }; 4968d033cc94d64c49aa442b3990386f95f95d5637Chris Lattner 501997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel RegisterAnalysis<CFGSCC> 5190c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson Y("cfgscc", "Print SCCs of each function CFG"); 52794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 538d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner RegisterAnalysis<CallGraphSCC> 5468d033cc94d64c49aa442b3990386f95f95d5637Chris Lattner Z("callscc", "Print SCCs of the Call Graph"); 55c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve} 5645cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner 57c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Advebool CFGSCC::runOnFunction(Function &F) { 588d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner unsigned sccNum = 0; 598d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << "SCCs for Function " << F.getName() << " in PostOrder:"; 608d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner for (TarjanSCC_iterator<Function*> SCCI = tarj_begin(&F), 618d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner E = tarj_end(&F); SCCI != E; ++SCCI) { 628d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner SCC<Function*> &nextSCC = *SCCI; 638d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << "\nSCC #" << ++sccNum << " : "; 64cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohman for (std::vector<BasicBlock*>::const_iterator I = nextSCC.begin(), 65c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve E = nextSCC.end(); I != E; ++I) 66cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohman std::cout << (*I)->getName() << ", "; 67cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohman if (nextSCC.size() == 1 && SCCI.hasLoop()) 68cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohman std::cout << " (Has self-loop)."; 69c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve } 70cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohman std::cout << "\n"; 71cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohman 72cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohman return true; 738d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner} 748d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 758d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 76ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman// run - Print out SCCs in the call graph for the specified module. 7755b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattnerbool CallGraphSCC::run(Module &M) { 7855b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); 79729d73d425430c285116af0d1ae523e95c3fa9ebChris Lattner unsigned sccNum = 0; 80ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman std::cout << "SCCs for the program in PostOrder:"; 819f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner for (TarjanSCC_iterator<CallGraphNode*> SCCI = tarj_begin(rootNode), 828d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner E = tarj_end(rootNode); SCCI != E; ++SCCI) { 83ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman const SCC<CallGraphNode*> &nextSCC = *SCCI; 849f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner std::cout << "\nSCC #" << ++sccNum << " : "; 85ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(), 868d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner E = nextSCC.end(); I != E; ++I) 87ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman std::cout << ((*I)->getFunction() ? (*I)->getFunction()->getName() 888d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner : std::string("Indirect CallGraph node")) << ", "; 898d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner if (nextSCC.size() == 1 && SCCI.hasLoop()) 908d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << " (Has self-loop)."; 918d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner } 928d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << "\n"; 938d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 9468d033cc94d64c49aa442b3990386f95f95d5637Chris Lattner return true; 958d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner} 968d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner