| 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-exception |
| 6 | // |
| 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 | |
| 22 | using namespace llvm; |
| 23 | using namespace sampleprof; |
| 24 | |
| 25 | STATISTIC(TailCallUniReachable, |
| 26 | "Number of frame pairs reachable via a unique tail call path" ); |
| 27 | STATISTIC(TailCallMultiReachable, |
| 28 | "Number of frame pairs reachable via a multiple tail call paths" ); |
| 29 | STATISTIC(TailCallUnreachable, |
| 30 | "Number of frame pairs unreachable via any tail call path" ); |
| 31 | STATISTIC(TailCallFuncSingleTailCalls, |
| 32 | "Number of functions with single tail call site" ); |
| 33 | STATISTIC(TailCallFuncMultipleTailCalls, |
| 34 | "Number of functions with multiple tail call sites" ); |
| 35 | STATISTIC(TailCallMaxTailCallPath, "Length of the longest tail call path" ); |
| 36 | |
| 37 | void MissingFrameInferrer::initialize( |
| 38 | const ContextSampleCounterMap *SampleCounters) { |
| 39 | // Refine call edges based on LBR samples. |
| 40 | if (SampleCounters) { |
| 41 | DenseMap<uint64_t, DenseSet<uint64_t>> SampledCalls; |
| 42 | DenseMap<uint64_t, DenseSet<uint64_t>> SampledTailCalls; |
| 43 | |
| 44 | // Populate SampledCalls based on static call sites. Similarly to |
| 45 | // SampledTailCalls. |
| 46 | for (const auto &CI : *SampleCounters) { |
| 47 | for (auto Item : CI.second.BranchCounter) { |
| 48 | auto From = Item.first.first; |
| 49 | auto To = Item.first.second; |
| 50 | if (CallEdges.count(Val: From)) { |
| 51 | assert(CallEdges[From].size() == 1 && |
| 52 | "A callsite should only appear once with either a known or a " |
| 53 | "zero (unknown) target value at this point" ); |
| 54 | SampledCalls[From].insert(V: To); |
| 55 | } |
| 56 | if (TailCallEdges.count(Val: From)) { |
| 57 | assert(TailCallEdges[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 | FuncRange *FromFRange = Binary->findFuncRange(Address: From); |
| 61 | FuncRange *ToFRange = Binary->findFuncRange(Address: To); |
| 62 | if (FromFRange != ToFRange) |
| 63 | SampledTailCalls[From].insert(V: To); |
| 64 | } |
| 65 | } |
| 66 | } |
| 67 | |
| 68 | // Replace static edges with dynamic edges. |
| 69 | CallEdges = std::move(SampledCalls); |
| 70 | TailCallEdges = std::move(SampledTailCalls); |
| 71 | } |
| 72 | |
| 73 | // Populate function-based edges. This is to speed up address to function |
| 74 | // translation. |
| 75 | for (auto Call : CallEdges) |
| 76 | for (auto Target : Call.second) |
| 77 | if (FuncRange *ToFRange = Binary->findFuncRange(Address: Target)) |
| 78 | CallEdgesF[Call.first].insert(Ptr: ToFRange->Func); |
| 79 | |
| 80 | for (auto Call : TailCallEdges) { |
| 81 | for (auto Target : Call.second) { |
| 82 | if (FuncRange *ToFRange = Binary->findFuncRange(Address: Target)) { |
| 83 | TailCallEdgesF[Call.first].insert(Ptr: ToFRange->Func); |
| 84 | TailCallTargetFuncs.insert(V: ToFRange->Func); |
| 85 | } |
| 86 | } |
| 87 | if (FuncRange *FromFRange = Binary->findFuncRange(Address: Call.first)) |
| 88 | FuncToTailCallMap[FromFRange->Func].push_back(x: Call.first); |
| 89 | } |
| 90 | |
| 91 | #if LLVM_ENABLE_STATS |
| 92 | for (auto F : FuncToTailCallMap) { |
| 93 | assert(F.second.size() > 0 && "" ); |
| 94 | if (F.second.size() > 1) |
| 95 | TailCallFuncMultipleTailCalls++; |
| 96 | else |
| 97 | TailCallFuncSingleTailCalls++; |
| 98 | } |
| 99 | #endif |
| 100 | |
| 101 | #ifndef NDEBUG |
| 102 | auto PrintCallTargets = |
| 103 | [&](const DenseMap<uint64_t, DenseSet<uint64_t>> &CallTargets, |
| 104 | bool IsTailCall) { |
| 105 | for (const auto &Targets : CallTargets) { |
| 106 | for (const auto &Target : Targets.second) { |
| 107 | dbgs() << (IsTailCall ? "TailCall" : "Call" ); |
| 108 | dbgs() << " From " << format("%8" PRIx64, Targets.first) << " to " |
| 109 | << format("%8" PRIx64, Target) << "\n" ; |
| 110 | } |
| 111 | } |
| 112 | }; |
| 113 | |
| 114 | LLVM_DEBUG({ |
| 115 | dbgs() << "============================\n " ; |
| 116 | dbgs() << "Call targets:\n" ; |
| 117 | PrintCallTargets(CallEdges, false); |
| 118 | dbgs() << "\nTail call targets:\n" ; |
| 119 | PrintCallTargets(TailCallEdges, true); |
| 120 | dbgs() << "============================\n" ; |
| 121 | }); |
| 122 | #endif |
| 123 | } |
| 124 | |
| 125 | uint64_t MissingFrameInferrer::computeUniqueTailCallPath( |
| 126 | BinaryFunction *From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) { |
| 127 | // Search for a unique path comprised of only tail call edges for a given |
| 128 | // source and target frame address on the a tail call graph that consists of |
| 129 | // only tail call edges. Note that only a unique path counts. Multiple paths |
| 130 | // are treated unreachable. |
| 131 | if (From == To) { |
| 132 | ++NumFoundPaths; |
| 133 | return 1; |
| 134 | } |
| 135 | |
| 136 | // Ignore cyclic paths. Since we are doing a recursive DFS walk, if the source |
| 137 | // frame being visited is already in the stack, it means we are seeing a |
| 138 | // cycle. Frames stay visited after the walk returns from them, so each frame |
| 139 | // is walked once. |
| 140 | if (Visiting.contains(V: From)) |
| 141 | return 0; |
| 142 | |
| 143 | uint64_t Pos = Path.size(); |
| 144 | |
| 145 | // DFS walk each outgoing tail call edges. |
| 146 | auto It = FuncToTailCallMap.find(Val: From); |
| 147 | if (It == FuncToTailCallMap.end()) |
| 148 | return 0; |
| 149 | |
| 150 | Visiting.insert(V: From); |
| 151 | uint64_t NumPaths = 0; |
| 152 | for (auto TailCall : It->second) { |
| 153 | NumPaths += computeUniqueTailCallPath(From: TailCall, To, UniquePath&: Path); |
| 154 | // Stop analyzing the remaining if we are already seeing more than one |
| 155 | // reachable paths. |
| 156 | if (NumFoundPaths > 1) |
| 157 | break; |
| 158 | } |
| 159 | |
| 160 | // Undo already-computed path if it is not unique. |
| 161 | if (NumPaths != 1) { |
| 162 | Path.pop_back_n(NumItems: Path.size() - Pos); |
| 163 | } |
| 164 | |
| 165 | return NumPaths; |
| 166 | } |
| 167 | |
| 168 | uint64_t MissingFrameInferrer::searchUniqueTailCallPath( |
| 169 | BinaryFunction *From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) { |
| 170 | // If already computed, return the cached result. The result of a walk |
| 171 | // depends on the frames visited before it, so only whole searches are cached. |
| 172 | auto I = UniquePaths.find(Val: {From, To}); |
| 173 | if (I != UniquePaths.end()) { |
| 174 | Path.append(in_start: I->second.begin(), in_end: I->second.end()); |
| 175 | return 1; |
| 176 | } |
| 177 | |
| 178 | auto J = NonUniquePaths.find(Val: {From, To}); |
| 179 | if (J != NonUniquePaths.end()) { |
| 180 | return J->second; |
| 181 | } |
| 182 | |
| 183 | uint64_t Pos = Path.size(); |
| 184 | Visiting.clear(); |
| 185 | NumFoundPaths = 0; |
| 186 | uint64_t NumPaths = computeUniqueTailCallPath(From, To, Path); |
| 187 | if (NumPaths == 1 && |
| 188 | hasOtherTailCallPath(Path: ArrayRef(Path).drop_front(N: Pos), To)) { |
| 189 | NumPaths = 2; |
| 190 | Path.pop_back_n(NumItems: Path.size() - Pos); |
| 191 | } |
| 192 | |
| 193 | // Cache the result. |
| 194 | if (NumPaths == 1) { |
| 195 | UniquePaths[{From, To}].assign(first: Path.begin() + Pos, last: Path.end()); |
| 196 | #if LLVM_ENABLE_STATS |
| 197 | auto &LocalPath = UniquePaths[{From, To}]; |
| 198 | TailCallMaxTailCallPath = std::max(uint64_t(LocalPath.size()), |
| 199 | TailCallMaxTailCallPath.getValue()); |
| 200 | #endif |
| 201 | } else { |
| 202 | NonUniquePaths[{From, To}] = NumPaths; |
| 203 | } |
| 204 | |
| 205 | return NumPaths; |
| 206 | } |
| 207 | |
| 208 | bool MissingFrameInferrer::hasOtherTailCallPath(ArrayRef<uint64_t> Path, |
| 209 | BinaryFunction *To) { |
| 210 | // Another simple path leaves this one at a frame through another tail call |
| 211 | // and rejoins it at a later frame, from which `To` is reachable. Walk from |
| 212 | // the frames of the path in order, keeping frames visited: the frames |
| 213 | // visited without reaching `To` reach no later frame of the path. |
| 214 | SmallVector<BinaryFunction *, 8> Funcs; |
| 215 | for (uint64_t Site : Path) |
| 216 | Funcs.push_back(Elt: Binary->findFuncRange(Address: Site)->Func); |
| 217 | Funcs.push_back(Elt: To); |
| 218 | Visiting.clear(); |
| 219 | // Count the path itself, so that a walk stops at the first path it finds. |
| 220 | NumFoundPaths = 1; |
| 221 | SmallVector<uint64_t, 8> OtherPath; |
| 222 | for (auto [I, PathSite] : enumerate(First&: Path)) { |
| 223 | Visiting.insert(V: Funcs[I]); |
| 224 | for (uint64_t Site : FuncToTailCallMap.find(Val: Funcs[I])->second) { |
| 225 | auto It = TailCallEdgesF.find(Val: Site); |
| 226 | if (It == TailCallEdgesF.end()) |
| 227 | continue; |
| 228 | for (BinaryFunction *Target : It->second) |
| 229 | if ((Site != PathSite || Target != Funcs[I + 1]) && |
| 230 | computeUniqueTailCallPath(From: Target, To, Path&: OtherPath)) |
| 231 | return true; |
| 232 | } |
| 233 | } |
| 234 | return false; |
| 235 | } |
| 236 | |
| 237 | uint64_t MissingFrameInferrer::computeUniqueTailCallPath( |
| 238 | uint64_t From, BinaryFunction *To, SmallVectorImpl<uint64_t> &Path) { |
| 239 | auto It = TailCallEdgesF.find(Val: From); |
| 240 | if (It == TailCallEdgesF.end()) |
| 241 | return 0; |
| 242 | Path.push_back(Elt: From); |
| 243 | uint64_t NumPaths = 0; |
| 244 | for (auto Target : It->second) { |
| 245 | NumPaths += computeUniqueTailCallPath(From: Target, To, Path); |
| 246 | // Stop analyzing the remaining if we are already seeing more than one |
| 247 | // reachable paths. |
| 248 | if (NumFoundPaths > 1) |
| 249 | break; |
| 250 | } |
| 251 | |
| 252 | // Undo already-computed path if it is not unique. |
| 253 | if (NumPaths != 1) |
| 254 | Path.pop_back(); |
| 255 | return NumPaths; |
| 256 | } |
| 257 | |
| 258 | bool MissingFrameInferrer::inferMissingFrames( |
| 259 | uint64_t From, uint64_t To, SmallVectorImpl<uint64_t> &UniquePath) { |
| 260 | assert(!TailCallEdgesF.count(From) && |
| 261 | "transition between From and To cannot be via a tailcall otherwise " |
| 262 | "they would not show up at the same time" ); |
| 263 | UniquePath.push_back(Elt: From); |
| 264 | uint64_t Pos = UniquePath.size(); |
| 265 | |
| 266 | FuncRange *ToFRange = Binary->findFuncRange(Address: To); |
| 267 | if (!ToFRange) |
| 268 | return false; |
| 269 | |
| 270 | // Bail out if caller has no known outgoing call edges. |
| 271 | auto It = CallEdgesF.find(Val: From); |
| 272 | if (It == CallEdgesF.end()) |
| 273 | return false; |
| 274 | |
| 275 | // Done with the inference if the calle is reachable via a single callsite. |
| 276 | // This may not be accurate but it improves the search throughput. |
| 277 | if (llvm::is_contained(Range&: It->second, Element: ToFRange->Func)) |
| 278 | return true; |
| 279 | |
| 280 | // Bail out if callee is not tailcall reachable at all. |
| 281 | if (!TailCallTargetFuncs.contains(V: ToFRange->Func)) |
| 282 | return false; |
| 283 | |
| 284 | uint64_t NumPaths = 0; |
| 285 | for (auto Target : It->second) { |
| 286 | NumPaths += searchUniqueTailCallPath(From: Target, To: ToFRange->Func, Path&: UniquePath); |
| 287 | // Stop analyzing the remaining if we are already seeing more than one |
| 288 | // reachable paths. |
| 289 | if (NumPaths > 1) |
| 290 | break; |
| 291 | } |
| 292 | |
| 293 | // Undo already-computed path if it is not unique. |
| 294 | if (NumPaths != 1) { |
| 295 | UniquePath.pop_back_n(NumItems: UniquePath.size() - Pos); |
| 296 | assert(UniquePath.back() == From && "broken path" ); |
| 297 | } |
| 298 | |
| 299 | #if LLVM_ENABLE_STATS |
| 300 | if (NumPaths == 1) { |
| 301 | if (ReachableViaUniquePaths.insert({From, ToFRange->StartAddress}).second) |
| 302 | TailCallUniReachable++; |
| 303 | } else if (NumPaths == 0) { |
| 304 | if (Unreachables.insert({From, ToFRange->StartAddress}).second) { |
| 305 | TailCallUnreachable++; |
| 306 | LLVM_DEBUG(dbgs() << "No path found from " |
| 307 | << format("%8" PRIx64 ":" , From) << " to " |
| 308 | << format("%8" PRIx64 ":" , ToFRange->StartAddress) |
| 309 | << "\n" ); |
| 310 | } |
| 311 | } else if (NumPaths > 1) { |
| 312 | if (ReachableViaMultiPaths.insert({From, ToFRange->StartAddress}) |
| 313 | .second) { |
| 314 | TailCallMultiReachable++; |
| 315 | LLVM_DEBUG(dbgs() << "Multiple paths found from " |
| 316 | << format("%8" PRIx64 ":" , From) << " to " |
| 317 | << format("%8" PRIx64 ":" , ToFRange->StartAddress) |
| 318 | << "\n" ); |
| 319 | } |
| 320 | } |
| 321 | #endif |
| 322 | |
| 323 | return NumPaths == 1; |
| 324 | } |
| 325 | |
| 326 | void MissingFrameInferrer::inferMissingFrames( |
| 327 | const SmallVectorImpl<uint64_t> &Context, |
| 328 | SmallVectorImpl<uint64_t> &NewContext) { |
| 329 | if (Context.size() == 1) { |
| 330 | NewContext = Context; |
| 331 | return; |
| 332 | } |
| 333 | |
| 334 | NewContext.clear(); |
| 335 | for (uint64_t I = 1; I < Context.size(); I++) { |
| 336 | inferMissingFrames(From: Context[I - 1], To: Context[I], UniquePath&: NewContext); |
| 337 | } |
| 338 | NewContext.push_back(Elt: Context.back()); |
| 339 | |
| 340 | assert((NewContext.size() >= Context.size()) && |
| 341 | "Inferred context should include all frames in the original context" ); |
| 342 | assert((NewContext.size() > Context.size() || NewContext == Context) && |
| 343 | "Inferred context should be exactly the same " |
| 344 | "with the original context" ); |
| 345 | } |
| 346 | |