PrintSCC.cpp revision 3ee8fc964952a65bcb3668b85938c46f90631e42
123ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner//===- PrintSCC.cpp - Enumerate SCCs in some key graphs -------------------===// 22b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 521c62da287237d39d0d95004881ea4baae3be6daChris Lattner// This file is distributed under the University of Illinois Open Source 621c62da287237d39d0d95004881ea4baae3be6daChris Lattner// License. See LICENSE.TXT for details. 72b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// 10c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// This file provides passes to print out SCCs in a CFG or a CallGraph. 11c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// Normally, you would not use these passes; instead, you would use the 1255b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner// scc_iterator directly to enumerate SCCs and process them in some way. These 1355b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner// passes serve three purposes: 1455b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner// 1555b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner// (1) As a reference for how to use the scc_iterator. 16c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// (2) To print out the SCCs for a CFG or a CallGraph: 173ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands// analyze -print-cfg-sccs to print the SCCs in each CFG of a module. 183ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands// analyze -print-cfg-sccs -stats to print the #SCCs and the maximum SCC size. 193ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands// analyze -print-cfg-sccs -debug > /dev/null to watch the algorithm in action. 202b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 21c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve// and similarly: 223ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands// analyze -print-callgraph-sccs [-stats] [-debug] to print SCCs in the CallGraph 232b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 2455b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner// (3) To test the scc_iterator. 2523ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner// 26c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve//===----------------------------------------------------------------------===// 27c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 28c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Pass.h" 29c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Module.h" 30c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Analysis/CallGraph.h" 31c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Support/CFG.h" 32551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/SCCIterator.h" 33954da37bb492b519f5c31dc360f2a142567e08b4Reid Spencer#include <iostream> 3468d033cc94d64c49aa442b3990386f95f95d5637Chris Lattnerusing namespace llvm; 35d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 36c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Advenamespace { 378d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner struct CFGSCC : public FunctionPass { 381997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Pass identification, replacement for typeid 39794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel CFGSCC() : FunctionPass((intptr_t)&ID) {} 408d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner bool runOnFunction(Function& func); 41c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 42ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer void print(std::ostream &O, const Module* = 0) const { } 43c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 448d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 458d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner AU.setPreservesAll(); 4623ebd75affba7de4a3bef20690609af9e42615e6Chris Lattner } 478d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner }; 48c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 4968d033cc94d64c49aa442b3990386f95f95d5637Chris Lattner struct CallGraphSCC : public ModulePass { 501997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel static char ID; // Pass identification, replacement for typeid 51794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel CallGraphSCC() : ModulePass((intptr_t)&ID) {} 52794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 538d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner // run - Print out SCCs in the call graph for the specified module. 5468d033cc94d64c49aa442b3990386f95f95d5637Chris Lattner bool runOnModule(Module &M); 55c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 56ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencer void print(std::ostream &O, const Module* = 0) const { } 57c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 588d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner // getAnalysisUsage - This pass requires the CallGraph. 598d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 608d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner AU.setPreservesAll(); 618d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner AU.addRequired<CallGraph>(); 628d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner } 638d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner }; 64c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 651997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char CFGSCC::ID = 0; 665d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattner RegisterPass<CFGSCC> 673ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands Y("print-cfg-sccs", "Print SCCs of each function CFG"); 68c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 691997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char CallGraphSCC::ID = 0; 705d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattner RegisterPass<CallGraphSCC> 713ee8fc964952a65bcb3668b85938c46f90631e42Duncan Sands Z("print-callgraph-sccs", "Print SCCs of the Call Graph"); 72c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve} 738d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 748d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattnerbool CFGSCC::runOnFunction(Function &F) { 758d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner unsigned sccNum = 0; 768d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << "SCCs for Function " << F.getName() << " in PostOrder:"; 7755b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner for (scc_iterator<Function*> SCCI = scc_begin(&F), 7855b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner E = scc_end(&F); SCCI != E; ++SCCI) { 79729d73d425430c285116af0d1ae523e95c3fa9ebChris Lattner std::vector<BasicBlock*> &nextSCC = *SCCI; 808d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << "\nSCC #" << ++sccNum << " : "; 819f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner for (std::vector<BasicBlock*>::const_iterator I = nextSCC.begin(), 828d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner E = nextSCC.end(); I != E; ++I) 838d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << (*I)->getName() << ", "; 849f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner if (nextSCC.size() == 1 && SCCI.hasLoop()) 858d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << " (Has self-loop)."; 868d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner } 878d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << "\n"; 888d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 898d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner return true; 908d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner} 918d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 928d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 938d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner// run - Print out SCCs in the call graph for the specified module. 9468d033cc94d64c49aa442b3990386f95f95d5637Chris Lattnerbool CallGraphSCC::runOnModule(Module &M) { 958d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner CallGraphNode* rootNode = getAnalysis<CallGraph>().getRoot(); 968d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner unsigned sccNum = 0; 978d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << "SCCs for the program in PostOrder:"; 9855b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode), 9955b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner E = scc_end(rootNode); SCCI != E; ++SCCI) { 100729d73d425430c285116af0d1ae523e95c3fa9ebChris Lattner const std::vector<CallGraphNode*> &nextSCC = *SCCI; 1018d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << "\nSCC #" << ++sccNum << " : "; 1029f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(), 1038d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner E = nextSCC.end(); I != E; ++I) 1048d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << ((*I)->getFunction() ? (*I)->getFunction()->getName() 1058d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner : std::string("Indirect CallGraph node")) << ", "; 1069f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner if (nextSCC.size() == 1 && SCCI.hasLoop()) 1078d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << " (Has self-loop)."; 1088d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner } 1098d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner std::cout << "\n"; 1108d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 1118d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner return true; 1128d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner} 113