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" 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CFG.h" 310b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 32f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Pass.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) {} 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function& func) override; 41c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 42dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void print(raw_ostream &O, const Module* = nullptr) const override { } 43c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 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. 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnModule(Module &M) override; 55c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void print(raw_ostream &O, const Module* = nullptr) const override { } 57c405daf3923a9b32fced0b75b937e3d27fb7b349Vikram S. Adve 588d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner // getAnalysisUsage - This pass requires the CallGraph. 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 608d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner AU.setPreservesAll(); 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<CallGraphWrapperPass>(); 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:"; 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (scc_iterator<Function*> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI) { 78dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const std::vector<BasicBlock *> &nextSCC = *SCCI; 7952fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "\nSCC #" << ++sccNum << " : "; 809f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner for (std::vector<BasicBlock*>::const_iterator I = nextSCC.begin(), 818d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner E = nextSCC.end(); I != E; ++I) 8252fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << (*I)->getName() << ", "; 839f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner if (nextSCC.size() == 1 && SCCI.hasLoop()) 8452fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << " (Has self-loop)."; 858d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner } 8652fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "\n"; 878d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 888d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner return true; 898d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner} 908d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 918d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 928d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner// run - Print out SCCs in the call graph for the specified module. 9368d033cc94d64c49aa442b3990386f95f95d5637Chris Lattnerbool CallGraphSCC::runOnModule(Module &M) { 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 958d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner unsigned sccNum = 0; 9652fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "SCCs for the program in PostOrder:"; 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (scc_iterator<CallGraph*> SCCI = scc_begin(&CG); !SCCI.isAtEnd(); 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++SCCI) { 99729d73d425430c285116af0d1ae523e95c3fa9ebChris Lattner const std::vector<CallGraphNode*> &nextSCC = *SCCI; 10052fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "\nSCC #" << ++sccNum << " : "; 1019f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(), 1028d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner E = nextSCC.end(); I != E; ++I) 103a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer errs() << ((*I)->getFunction() ? (*I)->getFunction()->getName() 104a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer : "external node") << ", "; 1059f2a06e76d173ea20891457a22dc0f55c361844fChris Lattner if (nextSCC.size() == 1 && SCCI.hasLoop()) 10652fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << " (Has self-loop)."; 1078d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner } 10852fdaeda759b2ef3b9048ab8651b024f864b3858Dan Gohman errs() << "\n"; 1098d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner 1108d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner return true; 1118d0a23ab42b01600118c28dbf767ed90afd4b902Chris Lattner} 112