| //===-- MissingFrameInferrer.cpp - Missing frame inferrer --------- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "MissingFrameInferrer.h" |
| #include "PerfReader.h" |
| #include "ProfiledBinary.h" |
| #include "llvm/ADT/SCCIterator.h" |
| #include "llvm/ADT/Statistic.h" |
| #include <algorithm> |
| #include <cstdint> |
| #include <iterator> |
| #include <queue> |
| #include <sys/types.h> |
| |
| #define DEBUG_TYPE "missing-frame-inferrer" |
| |
| using namespace llvm; |
| using namespace sampleprof; |
| |
| STATISTIC(TailCallUniReachable, |
| "Number of frame pairs reachable via a unique tail call path"); |
| STATISTIC(TailCallMultiReachable, |
| "Number of frame pairs reachable via a multiple tail call paths"); |
| STATISTIC(TailCallUnreachable, |
| "Number of frame pairs unreachable via any tail call path"); |
| STATISTIC(TailCallFuncSingleTailCalls, |
| "Number of functions with single tail call site"); |
| STATISTIC(TailCallFuncMultipleTailCalls, |
| "Number of functions with multiple tail call sites"); |
| STATISTIC(TailCallMaxTailCallPath, "Length of the longest tail call path"); |
| |
| static cl::opt<uint32_t> |
| MaximumSearchDepth("max-search-depth", cl::init(UINT32_MAX - 1), |
| cl::desc("The maximum levels the DFS-based missing " |
| "frame search should go with")); |
| |
| void MissingFrameInferrer::initialize( |
| const ContextSampleCounterMap *SampleCounters) { |
| // Refine call edges based on LBR samples. |
| if (SampleCounters) { |
| std::unordered_map<uint64_t, std::unordered_set<uint64_t>> SampledCalls; |
| std::unordered_map<uint64_t, std::unordered_set<uint64_t>> SampledTailCalls; |
| |
| // Populate SampledCalls based on static call sites. Similarly to |
| // SampledTailCalls. |
| for (const auto &CI : *SampleCounters) { |
| for (auto Item : CI.second.BranchCounter) { |
| auto From = Item.first.first; |
| auto To = Item.first.second; |
| if (CallEdges.count(From)) { |
| assert(CallEdges[From].size() == 1 && |
| "A callsite should only appear once with either a known or a " |
| "zero (unknown) target value at this point"); |
| SampledCalls[From].insert(To); |
| } |
| if (TailCallEdges.count(From)) { |
| assert(TailCallEdges[From].size() == 1 && |
| "A callsite should only appear once with either a known or a " |
| "zero (unknown) target value at this point"); |
| FuncRange *FromFRange = Binary->findFuncRange(From); |
| FuncRange *ToFRange = Binary->findFuncRange(To); |
| if (FromFRange != ToFRange) |
| SampledTailCalls[From].insert(To); |
| } |
| } |
| } |
| |
| // Replace static edges with dynamic edges. |
| CallEdges = SampledCalls; |
| TailCallEdges = SampledTailCalls; |
| } |
| |
| // Populate function-based edges. This is to speed up address to function |
| // translation. |
| for (auto Call : CallEdges) |
| for (auto Target : Call.second) |
| if (FuncRange *ToFRange = Binary->findFuncRange(Target)) |
| CallEdgesF[Call.first].insert(ToFRange->Func); |
| |
| for (auto Call : TailCallEdges) { |
| for (auto Target : Call.second) { |
| if (FuncRange *ToFRange = Binary->findFuncRange(Target)) { |
| TailCallEdgesF[Call.first].insert(ToFRange->Func); |
| TailCallTargetFuncs.insert(ToFRange->Func); |
| } |
| } |
| if (FuncRange *FromFRange = Binary->findFuncRange(Call.first)) |
| FuncToTailCallMap[FromFRange->Func].push_back(Call.first); |
| } |
| |
| #if LLVM_ENABLE_STATS |
| for (auto F : FuncToTailCallMap) { |
| assert(F.second.size() > 0 && ""); |
| if (F.second.size() > 1) |
| TailCallFuncMultipleTailCalls++; |
| else |
| TailCallFuncSingleTailCalls++; |
| } |
| #endif |
| |
| #ifndef NDEBUG |
| auto PrintCallTargets = |
| [&](const std::unordered_map<uint64_t, std::unordered_set<uint64_t>> |
| &CallTargets, |
| bool IsTailCall) { |
| for (const auto &Targets : CallTargets) { |
| for (const auto &Target : Targets.second) { |
| dbgs() << (IsTailCall ? "TailCall" : "Call"); |
| dbgs() << " From " << format("%8" PRIx64, Targets.first) << " to " |
| << format("%8" PRIx64, Target) << "\n"; |
| } |
| } |
| }; |
| |
| LLVM_DEBUG(dbgs() << "============================\n "; |
| dbgs() << "Call targets:\n"; |
| PrintCallTargets(CallEdges, false); |
| dbgs() << "\nTail call targets:\n"; |
| PrintCallTargets(CallEdges, true); |
| dbgs() << "============================\n";); |
| #endif |
| } |
| |
| uint64_t MissingFrameInferrer::computeUniqueTailCallPath( |
| BinaryFunction *From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) { |
| // Search for a unique path comprised of only tail call edges for a given |
| // source and target frame address on the a tail call graph that consists of |
| // only tail call edges. Note that only a unique path counts. Multiple paths |
| // are treated unreachable. |
| if (From == To) |
| return 1; |
| |
| // Ignore cyclic paths. Since we are doing a recursive DFS walk, if the source |
| // frame being visited is already in the stack, it means we are seeing a |
| // cycle. This is done before querying the cached result because the cached |
| // result may be computed based on the same path. Consider the following case: |
| // A -> B, B -> A, A -> D |
| // When computing unique reachablity from A to D, the cached result for (B,D) |
| // should not be counted since the unique path B->A->D is basically the same |
| // path as A->D. Counting that with invalidate the uniqueness from A to D. |
| if (Visiting.contains(From)) |
| return 0; |
| |
| // If already computed, return the cached result. |
| auto I = UniquePaths.find({From, To}); |
| if (I != UniquePaths.end()) { |
| Path.append(I->second.begin(), I->second.end()); |
| return 1; |
| } |
| |
| auto J = NonUniquePaths.find({From, To}); |
| if (J != NonUniquePaths.end()) { |
| return J->second; |
| } |
| |
| uint64_t Pos = Path.size(); |
| |
| // DFS walk each outgoing tail call edges. |
| // Bail out if we are already at the the maximum searching depth. |
| if (CurSearchingDepth == MaximumSearchDepth) |
| return 0; |
| |
| |
| if (!FuncToTailCallMap.count(From)) |
| return 0; |
| |
| CurSearchingDepth++; |
| Visiting.insert(From); |
| uint64_t NumPaths = 0; |
| for (auto TailCall : FuncToTailCallMap[From]) { |
| NumPaths += computeUniqueTailCallPath(TailCall, To, Path); |
| // Stop analyzing the remaining if we are already seeing more than one |
| // reachable paths. |
| if (NumPaths > 1) |
| break; |
| } |
| CurSearchingDepth--; |
| Visiting.erase(From); |
| |
| // Undo already-computed path if it is not unique. |
| if (NumPaths != 1) { |
| Path.pop_back_n(Path.size() - Pos); |
| } |
| |
| // Cache the result. |
| if (NumPaths == 1) { |
| UniquePaths[{From, To}].assign(Path.begin() + Pos, Path.end()); |
| #if LLVM_ENABLE_STATS |
| auto &LocalPath = UniquePaths[{From, To}]; |
| assert((LocalPath.size() <= MaximumSearchDepth + 1) && |
| "Path should not be longer than the maximum searching depth"); |
| TailCallMaxTailCallPath = std::max(uint64_t(LocalPath.size()), |
| TailCallMaxTailCallPath.getValue()); |
| #endif |
| } else { |
| NonUniquePaths[{From, To}] = NumPaths; |
| } |
| |
| return NumPaths; |
| } |
| |
| uint64_t MissingFrameInferrer::computeUniqueTailCallPath( |
| uint64_t From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) { |
| if (!TailCallEdgesF.count(From)) |
| return 0; |
| Path.push_back(From); |
| uint64_t NumPaths = 0; |
| for (auto Target : TailCallEdgesF[From]) { |
| NumPaths += computeUniqueTailCallPath(Target, To, Path); |
| // Stop analyzing the remaining if we are already seeing more than one |
| // reachable paths. |
| if (NumPaths > 1) |
| break; |
| } |
| |
| // Undo already-computed path if it is not unique. |
| if (NumPaths != 1) |
| Path.pop_back(); |
| return NumPaths; |
| } |
| |
| bool MissingFrameInferrer::inferMissingFrames( |
| uint64_t From, uint64_t To, SmallVectorImpl<uint64_t> &UniquePath) { |
| assert(!TailCallEdgesF.count(From) && |
| "transition between From and To cannot be via a tailcall otherwise " |
| "they would not show up at the same time"); |
| UniquePath.push_back(From); |
| uint64_t Pos = UniquePath.size(); |
| |
| FuncRange *ToFRange = Binary->findFuncRange(To); |
| if (!ToFRange) |
| return false; |
| |
| // Bail out if caller has no known outgoing call edges. |
| if (!CallEdgesF.count(From)) |
| return false; |
| |
| // Done with the inference if the calle is reachable via a single callsite. |
| // This may not be accurate but it improves the search throughput. |
| if (llvm::is_contained(CallEdgesF[From], ToFRange->Func)) |
| return true; |
| |
| // Bail out if callee is not tailcall reachable at all. |
| if (!TailCallTargetFuncs.contains(ToFRange->Func)) |
| return false; |
| |
| Visiting.clear(); |
| CurSearchingDepth = 0; |
| uint64_t NumPaths = 0; |
| for (auto Target : CallEdgesF[From]) { |
| NumPaths += |
| computeUniqueTailCallPath(Target, ToFRange->Func, UniquePath); |
| // Stop analyzing the remaining if we are already seeing more than one |
| // reachable paths. |
| if (NumPaths > 1) |
| break; |
| } |
| |
| // Undo already-computed path if it is not unique. |
| if (NumPaths != 1) { |
| UniquePath.pop_back_n(UniquePath.size() - Pos); |
| assert(UniquePath.back() == From && "broken path"); |
| } |
| |
| #if LLVM_ENABLE_STATS |
| if (NumPaths == 1) { |
| if (ReachableViaUniquePaths.insert({From, ToFRange->StartAddress}).second) |
| TailCallUniReachable++; |
| } else if (NumPaths == 0) { |
| if (Unreachables.insert({From, ToFRange->StartAddress}).second) { |
| TailCallUnreachable++; |
| LLVM_DEBUG(dbgs() << "No path found from " |
| << format("%8" PRIx64 ":", From) << " to " |
| << format("%8" PRIx64 ":", ToFRange->StartAddress) |
| << "\n"); |
| } |
| } else if (NumPaths > 1) { |
| if (ReachableViaMultiPaths.insert({From, ToFRange->StartAddress}) |
| .second) { |
| TailCallMultiReachable++; |
| LLVM_DEBUG(dbgs() << "Multiple paths found from " |
| << format("%8" PRIx64 ":", From) << " to " |
| << format("%8" PRIx64 ":", ToFRange->StartAddress) |
| << "\n"); |
| } |
| } |
| #endif |
| |
| return NumPaths == 1; |
| } |
| |
| void MissingFrameInferrer::inferMissingFrames( |
| const SmallVectorImpl<uint64_t> &Context, |
| SmallVectorImpl<uint64_t> &NewContext) { |
| if (Context.size() == 1) { |
| NewContext = Context; |
| return; |
| } |
| |
| NewContext.clear(); |
| for (uint64_t I = 1; I < Context.size(); I++) { |
| inferMissingFrames(Context[I - 1], Context[I], NewContext); |
| } |
| NewContext.push_back(Context.back()); |
| |
| assert((NewContext.size() >= Context.size()) && |
| "Inferred context should include all frames in the original context"); |
| assert((NewContext.size() > Context.size() || NewContext == Context) && |
| "Inferred context should be exactly the same " |
| "with the original context"); |
| } |