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