Deposit selected function mass onto source locations and inline callsite
trees. The implementation coalesces equivalent ranges and records direct
and indirect call edges without double counting source positions.
afdo_tools/ChangeLog:
* src/autofdo_correlate_deposit.cc: New file.
Signed-off-by: Kugan Vivekanandarajah <[email protected]>
Co-authored-by: Dhruv Chawla <[email protected]>
Co-authored-by: Rahul Shinde <[email protected]>
---
afdo_tools/src/autofdo_correlate_deposit.cc | 801 ++++++++++++++++++++
1 file changed, 801 insertions(+)
create mode 100644 afdo_tools/src/autofdo_correlate_deposit.cc
diff --git a/afdo_tools/src/autofdo_correlate_deposit.cc
b/afdo_tools/src/autofdo_correlate_deposit.cc
new file mode 100644
index 00000000000..89431cd71cc
--- /dev/null
+++ b/afdo_tools/src/autofdo_correlate_deposit.cc
@@ -0,0 +1,801 @@
+/* Copyright The GNU Toolchain Authors
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#include "autofdo_correlate_detail.h"
+
+#include "afdo_assert.h"
+#include "gcov_discriminator_encoding.h"
+#include "hash_util.h"
+#include "symbol_util.h"
+
+#include <algorithm>
+#include <atomic>
+#include <cstdio>
+#include <limits>
+#include <mutex>
+#include <thread>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+namespace autofdo {
+namespace correlate_detail {
+
+namespace {
+
+constexpr size_t CORRELATE_PROGRESS_REPORT_DIVISOR = 40;
+
+/* Address spans up to this wide get a directly indexed per-PC map. */
+constexpr uint64_t DENSE_ADDR_MASS_MAX_SPAN = 1ull << 18;
+
+struct inline_path_cache_entry;
+
+/* One PC's symbolization, resolved on first use and reused after that.
+ LOCATIONS[0] is the primary location; the rest are alternates. */
+struct instruction_map_entry
+{
+ bool valid = false;
+ const std::vector<dwarf_debug::source_location> *locations = nullptr;
+ const std::vector<dwarf_debug::inline_frame> *inline_stack = nullptr;
+ uint64_t inline_stack_hash = 0;
+ inline_path_cache_entry *inline_path = nullptr;
+};
+
+/* Per-PC entries for one function, indexed directly when the function is
+ small enough and hashed otherwise. */
+struct function_inst_map
+{
+ uint64_t base = 0;
+ std::vector<instruction_map_entry> dense;
+ std::unordered_map<uint64_t, instruction_map_entry> sparse;
+
+ bool dense_p () const { return !dense.empty (); }
+
+ /* A map covering [START, END), dense when that span is small enough to
+ index directly and sparse otherwise. */
+ static function_inst_map make (uint64_t start, uint64_t end)
+ {
+ function_inst_map map;
+ if (end > start && end - start <= DENSE_ADDR_MASS_MAX_SPAN)
+ {
+ map.base = start;
+ map.dense.resize (static_cast<size_t> (end - start));
+ }
+ return map;
+ }
+
+ instruction_map_entry &operator[] (uint64_t addr)
+ {
+ if (dense_p ())
+ {
+ const uint64_t offset = addr - base;
+ if (offset < dense.size ())
+ return dense[static_cast<size_t> (offset)];
+ }
+ return sparse[addr];
+ }
+};
+
+/* Hash of STACK by content, so equal inline stacks collide on purpose. */
+uint64_t
+hash_inline_frame_stack (
+ const std::vector<dwarf_debug::inline_frame> &stack)
+{
+ uint64_t h = 0;
+ for (const dwarf_debug::inline_frame &frame : stack)
+ {
+ autofdo::hash_combine (
+ h,
+ static_cast<uint64_t> (
+ std::hash<dwarf_debug::interned_string>{}(frame.function_name)));
+ autofdo::hash_combine (
+ h,
+ static_cast<uint64_t> (
+ std::hash<dwarf_debug::interned_string>{}(frame.file_path)));
+ autofdo::hash_combine (
+ h,
+ static_cast<uint64_t> (
+ std::hash<dwarf_debug::interned_string>{}(frame.caller_file_path)));
+ autofdo::hash_combine (
+ h, static_cast<uint64_t> (std::hash<uint32_t>{}(frame.line_number)));
+ autofdo::hash_combine (
+ h, static_cast<uint64_t> (std::hash<uint32_t>{}(frame.call_line)));
+ autofdo::hash_combine (
+ h, static_cast<uint64_t> (std::hash<uint32_t>{}(frame.discriminator)));
+ }
+ return h;
+}
+
+/* An inline stack's identity, compared by hash first and contents second. */
+struct inline_path_cache_key
+{
+ inline_path_cache_key (const std::vector<dwarf_debug::inline_frame> &stack,
+ uint64_t stack_hash)
+ : inline_stack (&stack), inline_stack_hash (stack_hash)
+ {}
+
+ const std::vector<dwarf_debug::inline_frame> *inline_stack;
+ uint64_t inline_stack_hash;
+
+ bool operator== (const inline_path_cache_key &o) const noexcept
+ {
+ if (inline_stack_hash != o.inline_stack_hash)
+ return false;
+ if (inline_stack == o.inline_stack)
+ return true;
+ return dwarf_debug::inline_stacks_equal (*inline_stack, *o.inline_stack);
+ }
+};
+
+struct inline_path_cache_key_hash
+{
+ size_t operator() (const inline_path_cache_key &k) const noexcept
+ {
+ return static_cast<size_t> (k.inline_stack_hash);
+ }
+};
+
+/* The builders along one inline stack, outermost first, leaf last. */
+struct inline_path_cache_entry
+{
+ function_builder *leaf_builder = nullptr;
+ std::vector<function_builder *> path;
+};
+
+using inline_path_cache
+ = std::unordered_map<inline_path_cache_key, inline_path_cache_entry,
+ inline_path_cache_key_hash>;
+
+/* Source identity of a PC, so that PCs resolving to the same locations and
+ inline stack deposit their mass once rather than repeatedly. */
+struct range_mass_coalesce_key
+{
+ const std::vector<dwarf_debug::source_location> *locations = nullptr;
+ const std::vector<dwarf_debug::inline_frame> *inline_stack = nullptr;
+ uint64_t locations_hash = 0;
+ uint64_t inline_stack_hash = 0;
+
+ bool operator== (const range_mass_coalesce_key &o) const noexcept
+ {
+ if (locations_hash != o.locations_hash
+ || inline_stack_hash != o.inline_stack_hash)
+ return false;
+ if (locations != o.locations
+ && !dwarf_debug::source_locations_equal (*locations, *o.locations))
+ return false;
+ if (inline_stack == o.inline_stack)
+ return true;
+ return dwarf_debug::inline_stacks_equal
+ (dwarf_debug::inline_stack_or_empty (inline_stack),
+ dwarf_debug::inline_stack_or_empty (o.inline_stack));
+ }
+};
+
+struct range_mass_coalesce_key_hash
+{
+ size_t operator() (const range_mass_coalesce_key &k) const noexcept
+ {
+ size_t h = static_cast<size_t> (k.locations_hash);
+ hash_combine (h, static_cast<size_t> (k.inline_stack_hash));
+ return h;
+ }
+};
+
+/* True when FRAME names NAME, allowing for GCC's clone and part suffixes. */
+bool
+frame_matches_name (const dwarf_debug::inline_frame &frame,
+ const std::string &name)
+{
+ if (name.empty () || dwarf_debug::string_empty (frame.function_name))
+ return false;
+ if (dwarf_debug::string_value (frame.function_name) == name)
+ return true;
+ return gcc_symbol::name_equivalent (
+ dwarf_debug::string_value (frame.function_name), name);
+}
+
+/* Callsite of FRAME already open under PARENT, or null if there is none or
+ several equally good ones. Matches on the frame's discriminator first, then
+ on any discriminator at the same line. */
+function_builder *
+find_callsite_child (function_builder &parent,
+ const dwarf_debug::inline_frame &frame, uint32_t call_line)
+{
+ if (call_line == 0 || dwarf_debug::string_empty (frame.function_name))
+ return nullptr;
+ const uint32_t frame_disc = get_base_discriminator (frame.discriminator);
+ const function_builder::callsite_map &callsites = parent.callsites ();
+ const callsite_key key{call_line, frame_disc, frame.function_name};
+ auto it = callsites.find (key);
+ if (it != callsites.end ())
+ return it->second.get ();
+
+ const callsite_key same_disc{call_line, frame_disc, nullptr};
+ function_builder *candidate = nullptr;
+ for (it = callsites.lower_bound (same_disc);
+ it != callsites.end () && it->first.call_line == call_line
+ && it->first.call_disc == frame_disc;
+ ++it)
+ if (frame_matches_name (frame, it->second->name))
+ {
+ if (candidate != nullptr)
+ return nullptr;
+ candidate = it->second.get ();
+ }
+ if (candidate != nullptr)
+ return candidate;
+
+ const callsite_key line_start{call_line, 0, nullptr};
+ candidate = nullptr;
+ for (it = callsites.lower_bound (line_start);
+ it != callsites.end () && it->first.call_line == call_line;
+ ++it)
+ {
+ if (!frame_matches_name (frame, it->second->name))
+ continue;
+ const uint32_t child_disc
+ = it->first.call_disc != 0
+ ? it->first.call_disc
+ : get_base_discriminator (it->second->discriminator);
+ if (frame_disc == 0 || frame_disc == child_disc)
+ {
+ if (candidate != nullptr)
+ return nullptr;
+ candidate = it->second.get ();
+ }
+ }
+ return candidate;
+}
+
+/* Fill in whatever CHILD is still missing about the callee FRAME names,
+ resolving its declaration against CALLER_FILE only when needed. */
+void
+fill_callsite_child_from_frame (function_builder &child,
+ const dwarf_debug::inline_frame &frame,
+ const dwarf_debug::dwarf_reader &reader,
+ const std::string &caller_file)
+{
+ if (child.name.empty ())
+ child.name = dwarf_debug::string_value (frame.function_name);
+ if (!child.file_path.empty () && child.start_line != 0)
+ return;
+ const dwarf_debug::source_location decl
+ = reader.resolve_inline_frame_decl_location (frame, caller_file);
+ if (child.file_path.empty ())
+ child.file_path = dwarf_debug::string_value (decl.file_path);
+ if (child.start_line == 0)
+ child.start_line = decl.line_number;
+}
+
+/* Walk INLINE_STACK down from ROOT, opening any callsite that is not already
+ there, and return the builder for the innermost frame. When PATH is given
+ it receives every builder along the way, ROOT first. */
+function_builder *
+build_inline_path (function_builder &root,
+ const std::vector<dwarf_debug::inline_frame> &inline_stack,
+ const dwarf_debug::dwarf_reader &reader,
+ std::vector<function_builder *> *path)
+{
+ function_builder *node = &root;
+ if (path != nullptr)
+ {
+ path->clear ();
+ path->reserve (inline_stack.size () + 1);
+ path->push_back (node);
+ }
+ for (const dwarf_debug::inline_frame &frame : inline_stack)
+ {
+ /* Skip frames without a callsite. */
+ if (frame.call_line == 0)
+ continue;
+ function_builder *child
+ = find_callsite_child (*node, frame, frame.call_line);
+ if (child == nullptr && !dwarf_debug::string_empty (frame.function_name))
+ {
+ /* Nothing open matches this frame, so open its callsite. */
+ const callsite_key key{frame.call_line,
+ get_base_discriminator (frame.discriminator),
+ frame.function_name};
+ child = &node->create_callsite (key);
+ fill_callsite_child_from_frame
+ (*child, frame, reader, node->file_path);
+ }
+ /* An unnamed frame cannot own a callsite; stay at this node. */
+ if (child != nullptr)
+ node = child;
+ if (path != nullptr)
+ path->push_back (node);
+ }
+ return node;
+}
+
+/* The builder on PATH that LOC belongs to: the caller whose callsite LOC
+ names if there is one, else the innermost frame whose file matches and
+ whose declaration starts at or before it. Null when nothing fits. */
+function_builder *
+source_owner_along_inline_path (
+ const std::vector<function_builder *> &path,
+ const std::vector<dwarf_debug::inline_frame> &stack,
+ const dwarf_debug::source_location &loc)
+{
+ afdo_assert (!path.empty ());
+ size_t caller_index = 0;
+ for (const dwarf_debug::inline_frame &frame : stack)
+ {
+ if (frame.call_line == 0)
+ continue;
+ if (caller_index >= path.size ())
+ break;
+ if (loc.line_number == frame.call_line)
+ {
+ dwarf_debug::interned_string call_file = frame.caller_file_path;
+ if (dwarf_debug::string_empty (call_file))
+ call_file = frame.file_path;
+ const bool same_file
+ = dwarf_debug::string_empty (loc.file_path)
+ || dwarf_debug::string_empty (call_file)
+ || source_path::equivalent (
+ dwarf_debug::string_value (loc.file_path),
+ dwarf_debug::string_value (call_file));
+ const uint32_t frame_disc
+ = get_base_discriminator (frame.discriminator);
+ const uint32_t loc_disc = get_base_discriminator (loc.discriminator);
+ if (same_file
+ && (frame_disc == 0 || loc_disc == 0 || frame_disc == loc_disc))
+ return path[caller_index];
+ }
+ ++caller_index;
+ }
+
+ function_builder *best = nullptr;
+ for (function_builder *node : path)
+ if (node->start_line != 0 && loc.line_number >= node->start_line
+ && !dwarf_debug::string_empty (loc.file_path)
+ && !node->file_path.empty ()
+ && source_path::equivalent (
+ dwarf_debug::string_value (loc.file_path), node->file_path)
+ && (best == nullptr || node->start_line >= best->start_line))
+ best = node;
+ return best;
+}
+
+/* Record COUNT calls to CALLEE_NAME at LOCATION, ignoring edges the profile
+ cannot place. */
+void
+record_call_edge (function_builder &builder,
+ const dwarf_debug::source_location &location,
+ dwarf_debug::interned_string callee_name, uint64_t count)
+{
+ if (count == 0 || dwarf_debug::string_empty (callee_name)
+ || location.line_number == 0)
+ return;
+ builder.record_call_target_max (
+ location.line_number, location.discriminator, callee_name, count);
+}
+
+/* INST's inline path, built on first use and then remembered both in CACHE,
+ keyed by inline stack, and on INST itself. */
+inline_path_cache_entry &
+resolve_inline_path_for_inst (const correlate_context &ctx,
+ function_profile &func_profile,
+ instruction_map_entry &inst,
+ inline_path_cache &cache)
+{
+ afdo_assert (func_profile.builder != nullptr);
+ const std::vector<dwarf_debug::inline_frame> &stack
+ = dwarf_debug::inline_stack_or_empty (inst.inline_stack);
+ if (inst.inline_path == nullptr)
+ {
+ const inline_path_cache_key key{stack, inst.inline_stack_hash};
+ inline_path_cache_entry &entry = cache[key];
+ if (entry.leaf_builder == nullptr)
+ entry.leaf_builder = build_inline_path
+ (*func_profile.builder, stack, ctx.reader, &entry.path);
+ inst.inline_path = &entry;
+ }
+ return *inst.inline_path;
+}
+
+/* Fill ENTRY with ADDR's source locations and inline stack, doing nothing if
+ it is already resolved. False when ADDR has no usable debug info. */
+bool
+symbolize_pc_entry (const dwarf_debug::dwarf_reader &reader, uint64_t addr,
+ instruction_map_entry &entry,
+ const dwarf_debug::function_metadata &func_hint,
+ dwarf_debug::correlate_session &session)
+{
+ if (entry.valid)
+ return true;
+ const dwarf_debug::symbolized_result result
+ = reader.symbolize (addr, session, func_hint);
+ if (result.function == nullptr
+ || result.locations == nullptr
+ || result.locations->empty ())
+ return false;
+ entry.valid = true;
+ entry.locations = result.locations;
+ entry.inline_stack = result.inline_stack;
+ entry.inline_stack_hash = hash_inline_frame_stack
+ (dwarf_debug::inline_stack_or_empty (entry.inline_stack));
+ return true;
+}
+
+/* Deposit COUNT at every source location INST resolves to, charging each one
+ to the inline frame that owns it and scaling by the discriminator's
+ multiplicity. */
+void
+apply_source_counts (const correlate_context &ctx,
+ function_profile &func_profile,
+ instruction_map_entry &inst, uint64_t count,
+ inline_path_cache &path_cache)
+{
+ inline_path_cache_entry &inline_path
+ = resolve_inline_path_for_inst (ctx, func_profile, inst, path_cache);
+ if (inst.locations == nullptr)
+ return;
+
+ const std::vector<dwarf_debug::inline_frame> &resolved_stack
+ = dwarf_debug::inline_stack_or_empty (inst.inline_stack);
+ for (size_t i = 0; i < inst.locations->size (); ++i)
+ {
+ const dwarf_debug::source_location &loc = (*inst.locations)[i];
+ if (loc.line_number == 0)
+ continue;
+ function_builder *owner
+ = source_owner_along_inline_path (
+ inline_path.path, resolved_stack, loc);
+ if (owner == nullptr && i == 0)
+ owner = inline_path.leaf_builder;
+ if (owner != nullptr)
+ {
+ const uint64_t weighted
+ = count * static_cast<uint64_t> (
+ get_multiplicity (loc.discriminator));
+ owner->deposit_position_max (
+ loc.line_number, loc.discriminator, weighted);
+ }
+ }
+}
+
+/* Hash of LOCATIONS by content, so equal location lists collide on purpose.
*/
+uint64_t
+hash_source_locations (
+ const std::vector<dwarf_debug::source_location> &locations)
+{
+ uint64_t hash = 0;
+ for (const dwarf_debug::source_location &loc : locations)
+ {
+ hash_combine (
+ hash, std::hash<dwarf_debug::interned_string>{}(loc.file_path));
+ hash_combine (hash, std::hash<uint32_t>{}(loc.line_number));
+ hash_combine (hash, std::hash<uint32_t>{}(loc.discriminator));
+ }
+ return hash;
+}
+
+/* INST's source identity, used to fold PCs that land on the same position. */
+range_mass_coalesce_key
+make_range_mass_coalesce_key (const instruction_map_entry &inst)
+{
+ afdo_assert (inst.locations != nullptr);
+ return {inst.locations,
+ inst.inline_stack,
+ hash_source_locations (*inst.locations),
+ inst.inline_stack_hash};
+}
+
+/* RANGE clipped to [MIN_ADDR, MAX_ADDR] as LO and HI; false when COUNT is
+ zero or nothing of RANGE survives the clip. */
+bool
+clip_branch_stack_range (const perf_data::branch_stack_edge &range,
+ uint64_t count, uint64_t min_addr, uint64_t max_addr,
+ uint64_t &lo, uint64_t &hi)
+{
+ if (count == 0 || range.second < range.first)
+ return false;
+ lo = std::max (range.first, min_addr);
+ hi = std::min (range.second, max_addr);
+ return hi >= lo;
+}
+
+/* Spread TARGET's branch-stack range mass across the PCs it covers and
+ deposit it. PCs resolving to the same source position keep only their
+ heaviest address, so a wide range counts once per position. */
+void
+deposit_range_mass (const correlate_context &ctx,
+ function_profile &func_profile,
+ const dwarf_debug::function_metadata &func_meta,
+ const correlate_target &target, function_inst_map &inst_map,
+ inline_path_cache &path_cache,
+ dwarf_debug::correlate_session &session)
+{
+ const perf_data::branch_stack_edge_count_map &ranges
+ = target.maps.range_count_map;
+ uint64_t min_addr = 0;
+ uint64_t max_addr = 0;
+ if (!perf_data::branch_stack_range_bounds (ranges, min_addr, max_addr))
+ return;
+
+ std::unordered_map<range_mass_coalesce_key,
+ std::pair<uint64_t, uint64_t>,
+ range_mass_coalesce_key_hash>
+ coalesced;
+ const auto visit_mass_pc = [&] (uint64_t addr, uint64_t mass)
+ {
+ instruction_map_entry &inst = inst_map[addr];
+ if (!symbolize_pc_entry (ctx.reader, addr, inst, func_meta, session))
+ return;
+ const range_mass_coalesce_key key = make_range_mass_coalesce_key (inst);
+ const auto inserted = coalesced.emplace (key, std::make_pair (addr, mass));
+ if (!inserted.second && mass > inserted.first->second.second)
+ inserted.first->second = std::make_pair (addr, mass);
+ };
+
+ /* A dense mass array over the whole span would be enormous for a sparse
+ function, so accumulate one window at a time. Stop before lo_addr +=
+ window wraps when min_addr is near UINT64_MAX. */
+ const unsigned addr_step = ctx.range_mass_addr_step;
+ if (addr_step == 0)
+ return;
+ const uint64_t window = DENSE_ADDR_MASS_MAX_SPAN;
+ for (uint64_t lo_addr = min_addr;;)
+ {
+ uint64_t hi_addr = max_addr;
+ if (lo_addr <= std::numeric_limits<uint64_t>::max () - (window - 1))
+ hi_addr = std::min (lo_addr + (window - 1), max_addr);
+ const uint64_t span = hi_addr - lo_addr + 1;
+ if (addr_step == 1)
+ {
+ /* Every PC is its own step, so lay the ranges down as a difference
+ array and sweep the running sum across the window. */
+ std::vector<__int128> diff (static_cast<size_t> (span + 1), 0);
+ for (const auto &entry : ranges)
+ {
+ uint64_t lo = 0;
+ uint64_t hi = 0;
+ if (!clip_branch_stack_range
+ (entry.first, entry.second, lo_addr, hi_addr, lo, hi))
+ continue;
+ diff[static_cast<size_t> (lo - lo_addr)] += entry.second;
+ diff[static_cast<size_t> (hi - lo_addr + 1)]
+ -= entry.second;
+ }
+ __int128 running = 0;
+ for (uint64_t off = 0; off < span; ++off)
+ {
+ running += diff[static_cast<size_t> (off)];
+ if (running > 0)
+ visit_mass_pc (lo_addr + off,
+ static_cast<uint64_t> (running));
+ }
+ }
+ else
+ {
+ std::vector<uint64_t> mass (static_cast<size_t> (span), 0);
+ for (const auto &entry : ranges)
+ {
+ uint64_t lo = 0;
+ uint64_t hi = 0;
+ if (!clip_branch_stack_range
+ (entry.first, entry.second, lo_addr, hi_addr, lo, hi))
+ continue;
+ for (uint64_t addr = lo;;)
+ {
+ mass[static_cast<size_t> (addr - lo_addr)]
+ += entry.second;
+ if (addr >= hi || hi - addr < addr_step)
+ break;
+ addr += addr_step;
+ }
+ }
+ for (uint64_t off = 0; off < span; off += addr_step)
+ if (mass[static_cast<size_t> (off)] != 0)
+ visit_mass_pc (lo_addr + off,
+ mass[static_cast<size_t> (off)]);
+ }
+
+ if (hi_addr >= max_addr)
+ break;
+ if (lo_addr > std::numeric_limits<uint64_t>::max () - window)
+ break;
+ lo_addr += window;
+ }
+
+ /* coalesced hashes interned-string addresses, so its iteration order shifts
+ with intern order; deposit by address to keep the profile reproducible.
*/
+ std::vector<std::pair<uint64_t, uint64_t>> ordered;
+ ordered.reserve (coalesced.size ());
+ for (const auto &entry : coalesced)
+ ordered.push_back (entry.second);
+ std::sort (ordered.begin (), ordered.end ());
+ for (const auto &entry : ordered)
+ {
+ instruction_map_entry &inst = inst_map[entry.first];
+ afdo_assert (inst.valid);
+ apply_source_counts (ctx, func_profile, inst, entry.second, path_cache);
+ }
+}
+
+/* Deposit TARGET's body mass, preferring branch-stack ranges and falling
+ back to per-address sample counts. */
+void
+correlate_function_body_counts (const correlate_context &ctx,
+ function_profile &func_profile,
+ const dwarf_debug::function_metadata &func_meta,
+ const correlate_target &target,
+ function_inst_map &inst_map,
+ inline_path_cache &path_cache,
+ dwarf_debug::correlate_session &session)
+{
+ if (!target.maps.range_count_map.empty ())
+ {
+ deposit_range_mass (
+ ctx, func_profile, func_meta, target, inst_map, path_cache, session);
+ return;
+ }
+ for (const auto &entry : target.maps.addr_counts)
+ {
+ const uint64_t addr = entry.first;
+ if (addr < target.maps.start_addr || addr >= target.maps.end_addr)
+ continue;
+ instruction_map_entry &inst = inst_map[addr];
+ if (symbolize_pc_entry (ctx.reader, addr, inst, func_meta, session))
+ apply_source_counts (ctx, func_profile, inst, entry.second, path_cache);
+ }
+}
+
+/* Record TARGET's outgoing calls, keeping only edges whose callee is itself
+ hot enough to be emitted. */
+void
+deposit_call_edges (const correlate_context &ctx,
+ function_profile &func_profile,
+ const dwarf_debug::function_metadata &func_meta,
+ const correlate_target &target, function_inst_map &inst_map,
+ inline_path_cache &path_cache,
+ dwarf_debug::correlate_session &session)
+{
+ for (const auto &entry : target.maps.branch_count_map)
+ {
+ const uint64_t from = entry.first.first;
+ if (from < target.maps.start_addr || from >= target.maps.end_addr)
+ continue;
+ instruction_map_entry &inst = inst_map[from];
+ if (!symbolize_pc_entry (ctx.reader, from, inst, func_meta, session))
+ continue;
+ const dwarf_debug::function_metadata *callee
+ = dwarf_debug::function_at_entry_pc (
+ ctx.reader.symtab_functions (), entry.first.second);
+ if (callee == nullptr
+ || ctx.emitted_hot_symbols.count ({callee->name, callee->start_addr})
+ == 0)
+ continue;
+ inline_path_cache_entry &inline_path
+ = resolve_inline_path_for_inst (
+ ctx, func_profile, inst, path_cache);
+ const std::vector<dwarf_debug::inline_frame> &stack
+ = dwarf_debug::inline_stack_or_empty (inst.inline_stack);
+ const dwarf_debug::source_location &loc = (*inst.locations)[0];
+ function_builder *owner
+ = source_owner_along_inline_path (inline_path.path, stack, loc);
+ if (owner == nullptr)
+ owner = inline_path.leaf_builder;
+ record_call_edge (*owner, loc, callee->name, entry.second);
+ }
+}
+
+/* Build one target's whole profile: open its callsite tree, deposit its body
+ mass, then its call edges. This is the unit of work a worker claims. */
+void
+correlate_per_function_profile (const correlate_context &ctx,
+ correlate_target &target,
+ dwarf_debug::correlate_session &session)
+{
+ afdo_assert (target.func_profile != nullptr);
+ function_profile &profile = *target.func_profile;
+ afdo_assert (profile.builder != nullptr);
+ const dwarf_debug::function_metadata &metadata
+ = ctx.reader.symtab_functions ()[target.symtab_index];
+ function_inst_map inst_map = function_inst_map::make (
+ target.maps.start_addr, target.maps.end_addr);
+ inline_path_cache path_cache;
+ path_cache.reserve (target.line_span_anchor_pcs.size ()
+ + target.maps.addr_counts.size ()
+ + target.maps.branch_count_map.size ()
+ + target.maps.range_count_map.size ());
+ /* Complete the callsite tree before caching paths through it. */
+ for (uint64_t addr : target.line_span_anchor_pcs)
+ {
+ instruction_map_entry &inst = inst_map[addr];
+ if (symbolize_pc_entry (ctx.reader, addr, inst, metadata, session))
+ build_inline_path
+ (*profile.builder,
+ dwarf_debug::inline_stack_or_empty (inst.inline_stack),
+ ctx.reader,
+ nullptr);
+ }
+ correlate_function_body_counts (
+ ctx, profile, metadata, target, inst_map, path_cache, session);
+ if (!target.maps.branch_count_map.empty ())
+ deposit_call_edges (
+ ctx, profile, metadata, target, inst_map, path_cache, session);
+}
+
+} /* anonymous namespace. */
+
+/* Correlate every target in CTX, sharing them out over CTX.num_threads
+ workers, and return how many were done. When SYMBOLIZE_OUT is given each
+ worker's symbolize cache is merged into it. */
+size_t
+run_correlate_target_workers (
+ correlate_context &ctx, dwarf_debug::correlate_symbolize_map *symbolize_out)
+{
+ std::vector<correlate_target> &targets = ctx.targets;
+ const size_t target_count = targets.size ();
+ const size_t progress_interval
+ = std::max<size_t> (1, target_count / CORRELATE_PROGRESS_REPORT_DIVISOR);
+ std::atomic<size_t> next_target{0};
+ std::atomic<size_t> functions_done{0};
+ std::mutex progress_mutex;
+ std::vector<dwarf_debug::correlate_symbolize_map> worker_snapshots;
+ if (symbolize_out != nullptr)
+ worker_snapshots.resize (ctx.num_threads);
+
+ const auto run_worker = [&] (unsigned worker_id)
+ {
+ dwarf_debug::correlate_session session;
+ for (size_t i = next_target.fetch_add (1); i < target_count;
+ i = next_target.fetch_add (1))
+ {
+ correlate_target &target = targets[i];
+ afdo_assert (target.func_profile != nullptr);
+ correlate_per_function_profile (ctx, target, session);
+ const size_t done
+ = functions_done.fetch_add (1, std::memory_order_relaxed) + 1;
+ if (done % progress_interval == 0 || done == target_count)
+ {
+ std::lock_guard<std::mutex> lock (progress_mutex);
+ fprintf (stderr,
+ _("AFDO: correlate %zu/%zu functions...\n"),
+ done,
+ target_count);
+ }
+ }
+ if (symbolize_out != nullptr)
+ session.drain_symbolize_snapshot_into (worker_snapshots[worker_id]);
+ };
+
+ if (ctx.num_threads == 1)
+ run_worker (0);
+ else
+ {
+ std::vector<std::thread> threads;
+ threads.reserve (ctx.num_threads);
+ for (unsigned i = 0; i < ctx.num_threads; ++i)
+ threads.emplace_back (run_worker, i);
+ for (std::thread &thread : threads)
+ thread.join ();
+ }
+ if (symbolize_out != nullptr)
+ for (dwarf_debug::correlate_symbolize_map &snapshot : worker_snapshots)
+ for (auto &entry : snapshot)
+ symbolize_out->emplace (entry.first, std::move (entry.second));
+ return functions_done.load (std::memory_order_relaxed);
+}
+
+} /* namespace correlate_detail. */
+} /* namespace autofdo. */
--
2.34.1
