1 //===- bolt/Core/CallGraphWalker.h ----------------------------*- C++ -*-===// 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 #ifndef BOLT_PASSES_CALLGRAPHWALKER_H 10 #define BOLT_PASSES_CALLGRAPHWALKER_H 11 12 #include <deque> 13 #include <functional> 14 #include <vector> 15 16 namespace llvm { 17 namespace bolt { 18 class BinaryFunction; 19 class BinaryFunctionCallGraph; 20 21 /// Perform a bottom-up walk of the call graph with the intent of computing 22 /// a property that depends on callees. In the event of a CG cycles, this will 23 /// re-visit functions until their observed property converges. 24 class CallGraphWalker { 25 BinaryFunctionCallGraph &CG; 26 27 /// DFS or reverse post-ordering of the call graph nodes to allow us to 28 /// traverse the call graph bottom-up 29 std::deque<BinaryFunction *> TopologicalCGOrder; 30 31 /// Stores all visitor functions to call when traversing the call graph 32 typedef std::function<bool(BinaryFunction *)> CallbackTy; 33 std::vector<CallbackTy> Visitors; 34 35 /// Do the bottom-up traversal 36 void traverseCG(); 37 38 public: 39 /// Initialize core context references but don't do anything yet CallGraphWalker(BinaryFunctionCallGraph & CG)40 CallGraphWalker(BinaryFunctionCallGraph &CG) : CG(CG) {} 41 42 /// Register a new callback function to be called for each function when 43 /// traversing the call graph bottom-up. Function should return true iff 44 /// whatever information it is keeping track of has changed. Function must 45 /// converge with time, ie, it must eventually return false, otherwise the 46 /// call graph walk will never finish. registerVisitor(CallbackTy Callback)47 void registerVisitor(CallbackTy Callback) { Visitors.emplace_back(Callback); } 48 49 /// Build the call graph, establish a traversal order and traverse it. 50 void walk(); 51 }; 52 53 } // namespace bolt 54 } // namespace llvm 55 56 #endif 57