1//===- PrintSCC.cpp - Enumerate SCCs in some key graphs -------------------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file provides passes to print out SCCs in a CFG or a CallGraph. 10// Normally, you would not use these passes; instead, you would use the 11// scc_iterator directly to enumerate SCCs and process them in some way. These 12// passes serve three purposes: 13// 14// (1) As a reference for how to use the scc_iterator. 15// (2) To print out the SCCs for a CFG or a CallGraph: 16// analyze -print-cfg-sccs to print the SCCs in each CFG of a module. 17// analyze -print-cfg-sccs -stats to print the #SCCs and the maximum SCC size. 18// analyze -print-cfg-sccs -debug > /dev/null to watch the algorithm in action. 19// 20// and similarly: 21// analyze -print-callgraph-sccs [-stats] [-debug] to print SCCs in the CallGraph 22// 23// (3) To test the scc_iterator. 24// 25//===----------------------------------------------------------------------===// 26 27#include "llvm/ADT/SCCIterator.h" 28#include "llvm/Analysis/CallGraph.h" 29#include "llvm/IR/CFG.h" 30#include "llvm/IR/Module.h" 31#include "llvm/Pass.h" 32#include "llvm/Support/raw_ostream.h" 33using namespace llvm; 34 35namespace { 36 struct CFGSCC : public FunctionPass { 37 static char ID; // Pass identification, replacement for typeid 38 CFGSCC() : FunctionPass(ID) {} 39 bool runOnFunction(Function& func) override; 40 41 void print(raw_ostream &O, const Module* = nullptr) const override { } 42 43 void getAnalysisUsage(AnalysisUsage &AU) const override { 44 AU.setPreservesAll(); 45 } 46 }; 47 48 struct CallGraphSCC : public ModulePass { 49 static char ID; // Pass identification, replacement for typeid 50 CallGraphSCC() : ModulePass(ID) {} 51 52 // run - Print out SCCs in the call graph for the specified module. 53 bool runOnModule(Module &M) override; 54 55 void print(raw_ostream &O, const Module* = nullptr) const override { } 56 57 // getAnalysisUsage - This pass requires the CallGraph. 58 void getAnalysisUsage(AnalysisUsage &AU) const override { 59 AU.setPreservesAll(); 60 AU.addRequired<CallGraphWrapperPass>(); 61 } 62 }; 63} 64 65char CFGSCC::ID = 0; 66static RegisterPass<CFGSCC> 67Y("print-cfg-sccs", "Print SCCs of each function CFG"); 68 69char CallGraphSCC::ID = 0; 70static RegisterPass<CallGraphSCC> 71Z("print-callgraph-sccs", "Print SCCs of the Call Graph"); 72 73bool CFGSCC::runOnFunction(Function &F) { 74 unsigned sccNum = 0; 75 errs() << "SCCs for Function " << F.getName() << " in PostOrder:"; 76 for (scc_iterator<Function*> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI) { 77 const std::vector<BasicBlock *> &nextSCC = *SCCI; 78 errs() << "\nSCC #" << ++sccNum << " : "; 79 for (BasicBlock *BB : nextSCC) { 80 BB->printAsOperand(errs(), false); 81 errs() << ", "; 82 } 83 if (nextSCC.size() == 1 && SCCI.hasCycle()) 84 errs() << " (Has self-loop)."; 85 } 86 errs() << "\n"; 87 88 return true; 89} 90 91 92// run - Print out SCCs in the call graph for the specified module. 93bool CallGraphSCC::runOnModule(Module &M) { 94 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 95 unsigned sccNum = 0; 96 errs() << "SCCs for the program in PostOrder:"; 97 for (scc_iterator<CallGraph*> SCCI = scc_begin(&CG); !SCCI.isAtEnd(); 98 ++SCCI) { 99 const std::vector<CallGraphNode*> &nextSCC = *SCCI; 100 errs() << "\nSCC #" << ++sccNum << " : "; 101 for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(), 102 E = nextSCC.end(); I != E; ++I) 103 errs() << ((*I)->getFunction() ? (*I)->getFunction()->getName() 104 : "external node") << ", "; 105 if (nextSCC.size() == 1 && SCCI.hasCycle()) 106 errs() << " (Has self-loop)."; 107 } 108 errs() << "\n"; 109 110 return true; 111} 112