320 lines · cpp
1//===-- MissingFrameInferrer.cpp - Missing frame inferrer --------- 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "MissingFrameInferrer.h"10#include "Options.h"11#include "PerfReader.h"12#include "ProfiledBinary.h"13#include "llvm/ADT/SCCIterator.h"14#include "llvm/ADT/Statistic.h"15#include <algorithm>16#include <cstdint>17#include <queue>18#include <sys/types.h>19 20#define DEBUG_TYPE "missing-frame-inferrer"21 22using namespace llvm;23using namespace sampleprof;24 25STATISTIC(TailCallUniReachable,26 "Number of frame pairs reachable via a unique tail call path");27STATISTIC(TailCallMultiReachable,28 "Number of frame pairs reachable via a multiple tail call paths");29STATISTIC(TailCallUnreachable,30 "Number of frame pairs unreachable via any tail call path");31STATISTIC(TailCallFuncSingleTailCalls,32 "Number of functions with single tail call site");33STATISTIC(TailCallFuncMultipleTailCalls,34 "Number of functions with multiple tail call sites");35STATISTIC(TailCallMaxTailCallPath, "Length of the longest tail call path");36 37static cl::opt<uint32_t>38 MaximumSearchDepth("max-search-depth", cl::init(UINT32_MAX - 1),39 cl::desc("The maximum levels the DFS-based missing "40 "frame search should go with"),41 cl::cat(ProfGenCategory));42 43void MissingFrameInferrer::initialize(44 const ContextSampleCounterMap *SampleCounters) {45 // Refine call edges based on LBR samples.46 if (SampleCounters) {47 std::unordered_map<uint64_t, std::unordered_set<uint64_t>> SampledCalls;48 std::unordered_map<uint64_t, std::unordered_set<uint64_t>> SampledTailCalls;49 50 // Populate SampledCalls based on static call sites. Similarly to51 // SampledTailCalls.52 for (const auto &CI : *SampleCounters) {53 for (auto Item : CI.second.BranchCounter) {54 auto From = Item.first.first;55 auto To = Item.first.second;56 if (CallEdges.count(From)) {57 assert(CallEdges[From].size() == 1 &&58 "A callsite should only appear once with either a known or a "59 "zero (unknown) target value at this point");60 SampledCalls[From].insert(To);61 }62 if (TailCallEdges.count(From)) {63 assert(TailCallEdges[From].size() == 1 &&64 "A callsite should only appear once with either a known or a "65 "zero (unknown) target value at this point");66 FuncRange *FromFRange = Binary->findFuncRange(From);67 FuncRange *ToFRange = Binary->findFuncRange(To);68 if (FromFRange != ToFRange)69 SampledTailCalls[From].insert(To);70 }71 }72 }73 74 // Replace static edges with dynamic edges.75 CallEdges = SampledCalls;76 TailCallEdges = SampledTailCalls;77 }78 79 // Populate function-based edges. This is to speed up address to function80 // translation.81 for (auto Call : CallEdges)82 for (auto Target : Call.second)83 if (FuncRange *ToFRange = Binary->findFuncRange(Target))84 CallEdgesF[Call.first].insert(ToFRange->Func);85 86 for (auto Call : TailCallEdges) {87 for (auto Target : Call.second) {88 if (FuncRange *ToFRange = Binary->findFuncRange(Target)) {89 TailCallEdgesF[Call.first].insert(ToFRange->Func);90 TailCallTargetFuncs.insert(ToFRange->Func);91 }92 }93 if (FuncRange *FromFRange = Binary->findFuncRange(Call.first))94 FuncToTailCallMap[FromFRange->Func].push_back(Call.first);95 }96 97#if LLVM_ENABLE_STATS98 for (auto F : FuncToTailCallMap) {99 assert(F.second.size() > 0 && "");100 if (F.second.size() > 1)101 TailCallFuncMultipleTailCalls++;102 else103 TailCallFuncSingleTailCalls++;104 }105#endif106 107#ifndef NDEBUG108 auto PrintCallTargets =109 [&](const std::unordered_map<uint64_t, std::unordered_set<uint64_t>>110 &CallTargets,111 bool IsTailCall) {112 for (const auto &Targets : CallTargets) {113 for (const auto &Target : Targets.second) {114 dbgs() << (IsTailCall ? "TailCall" : "Call");115 dbgs() << " From " << format("%8" PRIx64, Targets.first) << " to "116 << format("%8" PRIx64, Target) << "\n";117 }118 }119 };120 121 LLVM_DEBUG(dbgs() << "============================\n ";122 dbgs() << "Call targets:\n";123 PrintCallTargets(CallEdges, false);124 dbgs() << "\nTail call targets:\n";125 PrintCallTargets(CallEdges, true);126 dbgs() << "============================\n";);127#endif128}129 130uint64_t MissingFrameInferrer::computeUniqueTailCallPath(131 BinaryFunction *From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) {132 // Search for a unique path comprised of only tail call edges for a given133 // source and target frame address on the a tail call graph that consists of134 // only tail call edges. Note that only a unique path counts. Multiple paths135 // are treated unreachable.136 if (From == To)137 return 1;138 139 // Ignore cyclic paths. Since we are doing a recursive DFS walk, if the source140 // frame being visited is already in the stack, it means we are seeing a141 // cycle. This is done before querying the cached result because the cached142 // result may be computed based on the same path. Consider the following case:143 // A -> B, B -> A, A -> D144 // When computing unique reachablity from A to D, the cached result for (B,D)145 // should not be counted since the unique path B->A->D is basically the same146 // path as A->D. Counting that with invalidate the uniqueness from A to D.147 if (Visiting.contains(From))148 return 0;149 150 // If already computed, return the cached result.151 auto I = UniquePaths.find({From, To});152 if (I != UniquePaths.end()) {153 Path.append(I->second.begin(), I->second.end());154 return 1;155 }156 157 auto J = NonUniquePaths.find({From, To});158 if (J != NonUniquePaths.end()) {159 return J->second;160 }161 162 uint64_t Pos = Path.size();163 164 // DFS walk each outgoing tail call edges.165 // Bail out if we are already at the the maximum searching depth.166 if (CurSearchingDepth == MaximumSearchDepth)167 return 0;168 169 auto It = FuncToTailCallMap.find(From);170 if (It == FuncToTailCallMap.end())171 return 0;172 173 CurSearchingDepth++;174 Visiting.insert(From);175 uint64_t NumPaths = 0;176 for (auto TailCall : It->second) {177 NumPaths += computeUniqueTailCallPath(TailCall, To, Path);178 // Stop analyzing the remaining if we are already seeing more than one179 // reachable paths.180 if (NumPaths > 1)181 break;182 }183 CurSearchingDepth--;184 Visiting.erase(From);185 186 // Undo already-computed path if it is not unique.187 if (NumPaths != 1) {188 Path.pop_back_n(Path.size() - Pos);189 }190 191 // Cache the result.192 if (NumPaths == 1) {193 UniquePaths[{From, To}].assign(Path.begin() + Pos, Path.end());194#if LLVM_ENABLE_STATS195 auto &LocalPath = UniquePaths[{From, To}];196 assert((LocalPath.size() <= MaximumSearchDepth + 1) &&197 "Path should not be longer than the maximum searching depth");198 TailCallMaxTailCallPath = std::max(uint64_t(LocalPath.size()),199 TailCallMaxTailCallPath.getValue());200#endif201 } else {202 NonUniquePaths[{From, To}] = NumPaths;203 }204 205 return NumPaths;206}207 208uint64_t MissingFrameInferrer::computeUniqueTailCallPath(209 uint64_t From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) {210 auto It = TailCallEdgesF.find(From);211 if (It == TailCallEdgesF.end())212 return 0;213 Path.push_back(From);214 uint64_t NumPaths = 0;215 for (auto Target : It->second) {216 NumPaths += computeUniqueTailCallPath(Target, To, Path);217 // Stop analyzing the remaining if we are already seeing more than one218 // reachable paths.219 if (NumPaths > 1)220 break;221 }222 223 // Undo already-computed path if it is not unique.224 if (NumPaths != 1)225 Path.pop_back();226 return NumPaths;227}228 229bool MissingFrameInferrer::inferMissingFrames(230 uint64_t From, uint64_t To, SmallVectorImpl<uint64_t> &UniquePath) {231 assert(!TailCallEdgesF.count(From) &&232 "transition between From and To cannot be via a tailcall otherwise "233 "they would not show up at the same time");234 UniquePath.push_back(From);235 uint64_t Pos = UniquePath.size();236 237 FuncRange *ToFRange = Binary->findFuncRange(To);238 if (!ToFRange)239 return false;240 241 // Bail out if caller has no known outgoing call edges.242 auto It = CallEdgesF.find(From);243 if (It == CallEdgesF.end())244 return false;245 246 // Done with the inference if the calle is reachable via a single callsite.247 // This may not be accurate but it improves the search throughput.248 if (llvm::is_contained(It->second, ToFRange->Func))249 return true;250 251 // Bail out if callee is not tailcall reachable at all.252 if (!TailCallTargetFuncs.contains(ToFRange->Func))253 return false;254 255 Visiting.clear();256 CurSearchingDepth = 0;257 uint64_t NumPaths = 0;258 for (auto Target : It->second) {259 NumPaths +=260 computeUniqueTailCallPath(Target, ToFRange->Func, UniquePath);261 // Stop analyzing the remaining if we are already seeing more than one262 // reachable paths.263 if (NumPaths > 1)264 break;265 }266 267 // Undo already-computed path if it is not unique.268 if (NumPaths != 1) {269 UniquePath.pop_back_n(UniquePath.size() - Pos);270 assert(UniquePath.back() == From && "broken path");271 }272 273#if LLVM_ENABLE_STATS274 if (NumPaths == 1) {275 if (ReachableViaUniquePaths.insert({From, ToFRange->StartAddress}).second)276 TailCallUniReachable++;277 } else if (NumPaths == 0) {278 if (Unreachables.insert({From, ToFRange->StartAddress}).second) {279 TailCallUnreachable++;280 LLVM_DEBUG(dbgs() << "No path found from "281 << format("%8" PRIx64 ":", From) << " to "282 << format("%8" PRIx64 ":", ToFRange->StartAddress)283 << "\n");284 }285 } else if (NumPaths > 1) {286 if (ReachableViaMultiPaths.insert({From, ToFRange->StartAddress})287 .second) {288 TailCallMultiReachable++;289 LLVM_DEBUG(dbgs() << "Multiple paths found from "290 << format("%8" PRIx64 ":", From) << " to "291 << format("%8" PRIx64 ":", ToFRange->StartAddress)292 << "\n");293 }294 }295#endif296 297 return NumPaths == 1;298}299 300void MissingFrameInferrer::inferMissingFrames(301 const SmallVectorImpl<uint64_t> &Context,302 SmallVectorImpl<uint64_t> &NewContext) {303 if (Context.size() == 1) {304 NewContext = Context;305 return;306 }307 308 NewContext.clear();309 for (uint64_t I = 1; I < Context.size(); I++) {310 inferMissingFrames(Context[I - 1], Context[I], NewContext);311 }312 NewContext.push_back(Context.back());313 314 assert((NewContext.size() >= Context.size()) &&315 "Inferred context should include all frames in the original context");316 assert((NewContext.size() > Context.size() || NewContext == Context) &&317 "Inferred context should be exactly the same "318 "with the original context");319}320