303 lines · cpp
1//===- bolt/Core/BinaryFunctionCallGraph.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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the BinaryFunctionCallGraph class.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Core/BinaryFunctionCallGraph.h"14#include "bolt/Core/BinaryContext.h"15#include "bolt/Core/BinaryFunction.h"16#include "llvm/Support/CommandLine.h"17#include "llvm/Support/Timer.h"18#include <stack>19 20#define DEBUG_TYPE "callgraph"21 22using namespace llvm;23 24namespace opts {25 26extern cl::opt<bool> TimeOpts;27extern cl::opt<unsigned> Verbosity;28extern cl::OptionCategory BoltCategory;29 30static cl::opt<std::string>31 DumpCGDot("dump-cg", cl::desc("dump callgraph to the given file"),32 cl::cat(BoltCategory));33 34} // namespace opts35 36namespace llvm {37namespace bolt {38 39CallGraph::NodeId BinaryFunctionCallGraph::addNode(BinaryFunction *BF,40 uint32_t Size,41 uint64_t Samples) {42 NodeId Id = CallGraph::addNode(Size, Samples);43 assert(size_t(Id) == Funcs.size());44 Funcs.push_back(BF);45 FuncToNodeId[BF] = Id;46 assert(Funcs[Id] == BF);47 return Id;48}49 50std::deque<BinaryFunction *> BinaryFunctionCallGraph::buildTraversalOrder() {51 NamedRegionTimer T1("buildcgorder", "Build cg traversal order",52 "CG breakdown", "CG breakdown", opts::TimeOpts);53 std::deque<BinaryFunction *> TopologicalOrder;54 enum NodeStatus { NEW, VISITING, VISITED };55 std::vector<NodeStatus> NodeStatus(Funcs.size());56 std::stack<NodeId> Worklist;57 58 for (BinaryFunction *Func : Funcs) {59 auto It = FuncToNodeId.find(Func);60 assert(It != FuncToNodeId.end());61 const NodeId Id = It->second;62 Worklist.push(Id);63 NodeStatus[Id] = NEW;64 }65 66 while (!Worklist.empty()) {67 const NodeId FuncId = Worklist.top();68 Worklist.pop();69 70 if (NodeStatus[FuncId] == VISITED)71 continue;72 73 if (NodeStatus[FuncId] == VISITING) {74 TopologicalOrder.push_back(Funcs[FuncId]);75 NodeStatus[FuncId] = VISITED;76 continue;77 }78 79 assert(NodeStatus[FuncId] == NEW);80 NodeStatus[FuncId] = VISITING;81 Worklist.push(FuncId);82 for (const NodeId Callee : successors(FuncId)) {83 if (NodeStatus[Callee] == VISITING || NodeStatus[Callee] == VISITED)84 continue;85 Worklist.push(Callee);86 }87 }88 89 return TopologicalOrder;90}91 92BinaryFunctionCallGraph93buildCallGraph(BinaryContext &BC, CgFilterFunction Filter, bool CgFromPerfData,94 bool IncludeSplitCalls, bool UseFunctionHotSize,95 bool UseSplitHotSize, bool UseEdgeCounts,96 bool IgnoreRecursiveCalls) {97 NamedRegionTimer T1("buildcg", "Callgraph construction", "CG breakdown",98 "CG breakdown", opts::TimeOpts);99 BinaryFunctionCallGraph Cg;100 static constexpr uint64_t COUNT_NO_PROFILE =101 BinaryBasicBlock::COUNT_NO_PROFILE;102 103 // Compute function size104 auto functionSize = [&](const BinaryFunction *Function) {105 return UseFunctionHotSize && Function->isSplit()106 ? Function->estimateHotSize(UseSplitHotSize)107 : Function->estimateSize();108 };109 110 // Add call graph nodes.111 auto lookupNode = [&](BinaryFunction *Function) {112 const CallGraph::NodeId Id = Cg.maybeGetNodeId(Function);113 if (Id == CallGraph::InvalidId) {114 // It's ok to use the hot size here when the function is split. This is115 // because emitFunctions will emit the hot part first in the order that is116 // computed by ReorderFunctions. The cold part will be emitted with the117 // rest of the cold functions and code.118 const size_t Size = functionSize(Function);119 // NOTE: for functions without a profile, we set the number of samples120 // to zero. This will keep these functions from appearing in the hot121 // section. This is a little weird because we wouldn't be trying to122 // create a node for a function unless it was the target of a call from123 // a hot block. The alternative would be to set the count to one or124 // accumulate the number of calls from the callsite into the function125 // samples. Results from performance testing seem to favor the zero126 // count though, so I'm leaving it this way for now.127 return Cg.addNode(Function, Size, Function->getKnownExecutionCount());128 }129 return Id;130 };131 132 // Add call graph edges.133 uint64_t NotProcessed = 0;134 uint64_t TotalCallsites = 0;135 uint64_t NoProfileCallsites = 0;136 uint64_t NumFallbacks = 0;137 uint64_t RecursiveCallsites = 0;138 for (auto &It : BC.getBinaryFunctions()) {139 BinaryFunction *Function = &It.second;140 141 if (Filter(*Function))142 continue;143 144 const CallGraph::NodeId SrcId = lookupNode(Function);145 // Offset of the current basic block from the beginning of the function146 uint64_t Offset = 0;147 148 auto recordCall = [&](const MCSymbol *DestSymbol, const uint64_t Count) {149 BinaryFunction *DstFunc =150 DestSymbol ? BC.getFunctionForSymbol(DestSymbol) : nullptr;151 if (!DstFunc) {152 LLVM_DEBUG(if (opts::Verbosity > 1) dbgs()153 << "BOLT-DEBUG: buildCallGraph: no function for symbol\n");154 return false;155 }156 157 if (DstFunc == Function) {158 LLVM_DEBUG(dbgs() << "BOLT-INFO: recursive call detected in "159 << *DstFunc << "\n");160 ++RecursiveCallsites;161 if (IgnoreRecursiveCalls)162 return false;163 }164 if (Filter(*DstFunc)) {165 LLVM_DEBUG(if (opts::Verbosity > 1) dbgs()166 << "BOLT-DEBUG: buildCallGraph: filtered " << *DstFunc167 << '\n');168 return false;169 }170 171 const CallGraph::NodeId DstId = lookupNode(DstFunc);172 const bool IsValidCount = Count != COUNT_NO_PROFILE;173 const uint64_t AdjCount = UseEdgeCounts && IsValidCount ? Count : 1;174 if (!IsValidCount)175 ++NoProfileCallsites;176 Cg.incArcWeight(SrcId, DstId, AdjCount, Offset);177 LLVM_DEBUG(if (opts::Verbosity > 1) {178 dbgs() << "BOLT-DEBUG: buildCallGraph: call " << *Function << " -> "179 << *DstFunc << " @ " << Offset << "\n";180 });181 return true;182 };183 184 // Pairs of (symbol, count) for each target at this callsite.185 using TargetDesc = std::pair<const MCSymbol *, uint64_t>;186 using CallInfoTy = std::vector<TargetDesc>;187 188 // Get pairs of (symbol, count) for each target at this callsite.189 // If the call is to an unknown function the symbol will be nullptr.190 // If there is no profiling data the count will be COUNT_NO_PROFILE.191 auto getCallInfo = [&](const BinaryBasicBlock *BB, const MCInst &Inst) {192 CallInfoTy Counts;193 const MCSymbol *DstSym = BC.MIB->getTargetSymbol(Inst);194 195 // If this is an indirect call use perf data directly.196 if (!DstSym && BC.MIB->hasAnnotation(Inst, "CallProfile")) {197 const auto &ICSP = BC.MIB->getAnnotationAs<IndirectCallSiteProfile>(198 Inst, "CallProfile");199 for (const IndirectCallProfile &CSI : ICSP)200 if (CSI.Symbol)201 Counts.emplace_back(CSI.Symbol, CSI.Count);202 } else {203 const uint64_t Count = BC.MIB->getAnnotationWithDefault(204 Inst, "Count", BB->getExecutionCount());205 Counts.emplace_back(DstSym, Count);206 }207 208 return Counts;209 };210 211 // If the function has an invalid profile, try to use the perf data212 // directly (if requested). If there is no perf data for this function,213 // fall back to the CFG walker which attempts to handle missing data.214 if (!Function->hasValidProfile() && CgFromPerfData &&215 !Function->getAllCallSites().empty()) {216 LLVM_DEBUG(217 dbgs() << "BOLT-DEBUG: buildCallGraph: Falling back to perf data"218 << " for " << *Function << "\n");219 ++NumFallbacks;220 const size_t Size = functionSize(Function);221 for (const IndirectCallProfile &CSI : Function->getAllCallSites()) {222 ++TotalCallsites;223 224 if (!CSI.Symbol)225 continue;226 227 // The computed offset may exceed the hot part of the function; hence,228 // bound it by the size.229 Offset = CSI.Offset;230 if (Offset > Size)231 Offset = Size;232 233 if (!recordCall(CSI.Symbol, CSI.Count))234 ++NotProcessed;235 }236 } else {237 for (BinaryBasicBlock *BB : Function->getLayout().blocks()) {238 // Don't count calls from split blocks unless requested.239 if (BB->isSplit() && !IncludeSplitCalls)240 continue;241 242 // Determine whether the block is included in Function's (hot) size243 // See BinaryFunction::estimateHotSize244 bool BBIncludedInFunctionSize = false;245 if (UseFunctionHotSize && Function->isSplit()) {246 if (UseSplitHotSize)247 BBIncludedInFunctionSize = !BB->isSplit();248 else249 BBIncludedInFunctionSize = BB->getKnownExecutionCount() != 0;250 } else {251 BBIncludedInFunctionSize = true;252 }253 254 for (MCInst &Inst : *BB) {255 // Find call instructions and extract target symbols from each one.256 if (BC.MIB->isCall(Inst)) {257 const CallInfoTy CallInfo = getCallInfo(BB, Inst);258 259 if (!CallInfo.empty()) {260 for (const TargetDesc &CI : CallInfo) {261 ++TotalCallsites;262 if (!recordCall(CI.first, CI.second))263 ++NotProcessed;264 }265 } else {266 ++TotalCallsites;267 ++NotProcessed;268 }269 }270 // Increase Offset if needed271 if (BBIncludedInFunctionSize)272 Offset += BC.computeCodeSize(&Inst, &Inst + 1);273 }274 }275 }276 }277 278#ifndef NDEBUG279 bool PrintInfo = DebugFlag && isCurrentDebugType("callgraph");280#else281 bool PrintInfo = false;282#endif283 if (PrintInfo || opts::Verbosity > 0)284 BC.outs() << format("BOLT-INFO: buildCallGraph: %u nodes, %u callsites "285 "(%u recursive), density = %.6lf, %u callsites not "286 "processed, %u callsites with invalid profile, "287 "used perf data for %u stale functions.\n",288 Cg.numNodes(), TotalCallsites, RecursiveCallsites,289 Cg.density(), NotProcessed, NoProfileCallsites,290 NumFallbacks);291 292 if (opts::DumpCGDot.getNumOccurrences()) {293 Cg.printDot(opts::DumpCGDot, [&](CallGraph::NodeId Id) {294 return Cg.nodeIdToFunc(Id)->getPrintName();295 });296 }297 298 return Cg;299}300 301} // namespace bolt302} // namespace llvm303