1 //===- bolt/Core/CallGraphWalker.cpp ------------------------------------===// 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 implements the CallGraphWalker class. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "bolt/Core/CallGraphWalker.h" 14 #include "bolt/Core/BinaryFunctionCallGraph.h" 15 #include "llvm/Support/CommandLine.h" 16 #include "llvm/Support/Timer.h" 17 #include <queue> 18 #include <set> 19 20 namespace opts { 21 extern llvm::cl::opt<bool> TimeOpts; 22 } 23 24 namespace llvm { 25 namespace bolt { 26 traverseCG()27void CallGraphWalker::traverseCG() { 28 NamedRegionTimer T1("CG Traversal", "CG Traversal", "CG breakdown", 29 "CG breakdown", opts::TimeOpts); 30 std::queue<BinaryFunction *> Queue; 31 std::set<BinaryFunction *> InQueue; 32 33 for (BinaryFunction *Func : TopologicalCGOrder) { 34 Queue.push(Func); 35 InQueue.insert(Func); 36 } 37 38 while (!Queue.empty()) { 39 BinaryFunction *Func = Queue.front(); 40 Queue.pop(); 41 InQueue.erase(Func); 42 43 bool Changed = false; 44 for (CallbackTy Visitor : Visitors) { 45 bool CurVisit = Visitor(Func); 46 Changed = Changed || CurVisit; 47 } 48 49 if (Changed) { 50 for (CallGraph::NodeId CallerID : CG.predecessors(CG.getNodeId(Func))) { 51 BinaryFunction *CallerFunc = CG.nodeIdToFunc(CallerID); 52 if (InQueue.count(CallerFunc)) 53 continue; 54 Queue.push(CallerFunc); 55 InQueue.insert(CallerFunc); 56 } 57 } 58 } 59 } 60 walk()61void CallGraphWalker::walk() { 62 TopologicalCGOrder = CG.buildTraversalOrder(); 63 traverseCG(); 64 } 65 66 } // namespace bolt 67 } // namespace llvm 68