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 28f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/ADT/SCCIterator.h" 29c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Analysis/CallGraph.h" 300b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 31f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Pass.h" 32c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve#include "llvm/Support/CFG.h" 33ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman#include "llvm/Support/raw_ostream.h" 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 3990c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson CFGSCC() : FunctionPass(ID) {} 408d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner bool runOnFunction(Function& func); 41c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 4245cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner void print(raw_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 5190c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson CallGraphSCC() : ModulePass(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 5645cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner void print(raw_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 }; 64cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohman} 65c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 66cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohmanchar CFGSCC::ID = 0; 67cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohmanstatic RegisterPass<CFGSCC> 68cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan GohmanY("print-cfg-sccs", "Print SCCs of each function CFG"); 69c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 70cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohmanchar CallGraphSCC::ID = 0; 71cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan Gohmanstatic RegisterPass<CallGraphSCC> 72cfbe401e8b678aad7238b3d6edb366e68470f6a5Dan GohmanZ("print-callgraph-sccs", "Print SCCs of the Call Graph"); 738d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 748d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattnerbool CFGSCC::runOnFunction(Function &F) { 758d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner unsigned sccNum = 0; 7652fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "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; 8052fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "\nSCC #" << ++sccNum << " : "; 819f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner for (std::vector<BasicBlock*>::const_iterator I = nextSCC.begin(), 828d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner E = nextSCC.end(); I != E; ++I) 8352fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << (*I)->getName() << ", "; 849f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner if (nextSCC.size() == 1 && SCCI.hasLoop()) 8552fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << " (Has self-loop)."; 868d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner } 8752fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "\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; 9752fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "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; 10152fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "\nSCC #" << ++sccNum << " : "; 1029f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(), 1038d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner E = nextSCC.end(); I != E; ++I) 104a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer errs() << ((*I)->getFunction() ? (*I)->getFunction()->getName() 105a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer : "external node") << ", "; 1069f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner if (nextSCC.size() == 1 && SCCI.hasLoop()) 10752fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << " (Has self-loop)."; 1088d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner } 10952fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "\n"; 1108d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 1118d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner return true; 1128d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner} 113