bolt/lib/Core/CallGraphWalker.cpp

   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
  27 void 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
  61 void CallGraphWalker::walk() {
  62   TopologicalCGOrder = CG.buildTraversalOrder();
  63   traverseCG();
  64 }
  65
  66 } // namespace bolt
  67 } // namespace llvm