Bucket normalized perf ranges, branches, and address counts onto containing
ELF functions. Functions are selected using grouped profile mass before
expensive DWARF symbolization begins.
afdo_tools/ChangeLog:
* src/autofdo_correlate_bucket.cc: New file.
* src/autofdo_correlate_detail.h: 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_bucket.cc | 476 +++++++++++++++++++++
afdo_tools/src/autofdo_correlate_detail.h | 94 ++++
2 files changed, 570 insertions(+)
create mode 100644 afdo_tools/src/autofdo_correlate_bucket.cc
create mode 100644 afdo_tools/src/autofdo_correlate_detail.h
diff --git a/afdo_tools/src/autofdo_correlate_bucket.cc
b/afdo_tools/src/autofdo_correlate_bucket.cc
new file mode 100644
index 00000000000..b8178346f93
--- /dev/null
+++ b/afdo_tools/src/autofdo_correlate_bucket.cc
@@ -0,0 +1,476 @@
+/* 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 "autofdo_options.h"
+#include "symbol_util.h"
+
+#include <algorithm>
+#include <cstdio>
+#include <limits>
+#include <thread>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace autofdo {
+namespace correlate_detail {
+namespace {
+
+constexpr uint64_t MIN_SAMPLES_FOR_GCOV_EMIT = 10;
+
+/* Below this many branch records the threads cost more than they save. */
+constexpr size_t MIN_BRANCHES_FOR_PARALLEL_SWEEP = 4096;
+
+using func_map_key = const dwarf_debug::function_metadata *;
+using func_maps_type
+ = std::unordered_map<func_map_key, per_function_profile_maps>;
+using entry_edge_count_by_addr = std::unordered_map<uint64_t, uint64_t>;
+
+struct function_emit_group_key
+{
+ std::string parent_name;
+ std::string file_path;
+ uint64_t fallback_addr = 0;
+
+ bool operator== (const function_emit_group_key &o) const noexcept
+ {
+ return parent_name == o.parent_name && file_path == o.file_path
+ && fallback_addr == o.fallback_addr;
+ }
+};
+
+struct function_emit_group_hash
+{
+ size_t operator() (const function_emit_group_key &key) const noexcept
+ {
+ size_t h = std::hash<std::string>{}(key.parent_name);
+ hash_combine (h, std::hash<std::string>{}(key.file_path));
+ hash_combine (h, std::hash<uint64_t>{}(key.fallback_addr));
+ return h;
+ }
+};
+
+using group_mass_map = std::unordered_map<function_emit_group_key, uint64_t,
+ function_emit_group_hash>;
+
+/* Mass a function group must reach to enter the profile: the configured
+ SAMPLE_THRESHOLD_FRAC of PROFILE's total, rounded up so a group whose
+ mass equals that fraction is kept, and never below MIN_SAMPLES. */
+uint64_t
+gcov_emit_threshold (const perf_data::profile_reader &profile,
+ double sample_threshold_frac)
+{
+ uint64_t total = 0;
+ if (const auto *ranges = profile.range_counts ())
+ {
+ for (const auto &row : *ranges)
+ if (row.end >= row.beg)
+ total += row.count * (row.end - row.beg + 1);
+ }
+ else
+ for (const auto &entry : profile.get_address_frequencies ())
+ total += entry.second;
+
+ uint64_t threshold = 0;
+ if (sample_threshold_frac <= 0.0)
+ threshold = 0;
+ else if (!(sample_threshold_frac < 1.0))
+ threshold = total;
+ else
+ {
+ const long double product
+ = static_cast<long double> (sample_threshold_frac)
+ * static_cast<long double> (total);
+ if (product >= static_cast<long double> (
+ std::numeric_limits<uint64_t>::max ()))
+ threshold = std::numeric_limits<uint64_t>::max ();
+ else
+ {
+ threshold = static_cast<uint64_t> (product);
+ if (static_cast<long double> (threshold) < product
+ && threshold < std::numeric_limits<uint64_t>::max ())
+ ++threshold;
+ }
+ }
+ return std::max (threshold, MIN_SAMPLES_FOR_GCOV_EMIT);
+}
+
+/* Seed TARGET with one PC per line-table span, taken from the addresses it
+ actually sampled when it has range mass and from its whole body if not. */
+void
+collect_target_line_span_anchors (dwarf_debug::dwarf_reader &dw,
+ correlate_target &target)
+{
+ uint64_t min_addr = 0;
+ uint64_t max_addr = 0;
+ if (perf_data::branch_stack_range_bounds
+ (target.maps.range_count_map, min_addr, max_addr))
+ dw.collect_line_span_seed_pcs (
+ min_addr, max_addr + 1, target.line_span_anchor_pcs);
+ else
+ dw.collect_line_span_seed_pcs (
+ target.maps.start_addr, target.maps.end_addr,
+ target.line_span_anchor_pcs);
+}
+
+/* Key grouping FUNC with the other split parts of the same source function,
+ so the emit threshold sees their combined mass. */
+function_emit_group_key
+function_emit_group (const dwarf_debug::function_metadata &func)
+{
+ return {gcc_symbol::symbol_split_part_parent (
+ dwarf_debug::string_value (func.name)),
+ dwarf_debug::string_value (func.file_path),
+ dwarf_debug::string_empty (func.file_path) ? func.start_addr : 0};
+}
+
+/* True when MAPS has a real address range and carries mass this run can use;
+ range mass only counts when the branch stack is in play. */
+bool
+per_function_maps_have_samples (const per_function_profile_maps &maps,
+ bool use_branch_stack)
+{
+ if (maps.end_addr <= maps.start_addr)
+ return false;
+ if (!maps.addr_counts.empty () || !maps.branch_count_map.empty ())
+ return true;
+ return use_branch_stack && !maps.range_count_map.empty ();
+}
+
+/* FUNC's entry in FUNC_MAPS, seeded with its address range when first
+ created. */
+per_function_profile_maps &
+get_or_create_function_maps (func_maps_type &func_maps,
+ const dwarf_debug::function_metadata &func)
+{
+ auto it = func_maps.find (&func);
+ if (it != func_maps.end ())
+ return it->second;
+ auto inserted = func_maps.emplace (&func, per_function_profile_maps ());
+ inserted.first->second.start_addr = func.start_addr;
+ inserted.first->second.end_addr = func.end_addr;
+ return inserted.first->second;
+}
+
+/* Total sample mass in MAPS, counting a range once per address it covers. */
+uint64_t
+per_function_profile_mass (const per_function_profile_maps &maps)
+{
+ if (!maps.range_count_map.empty ())
+ {
+ uint64_t total = 0;
+ for (const auto &entry : maps.range_count_map)
+ {
+ const perf_data::branch_stack_edge &range = entry.first;
+ if (range.second >= range.first)
+ total += entry.second * (range.second - range.first + 1);
+ }
+ return total;
+ }
+ uint64_t total = 0;
+ for (const auto &entry : maps.addr_counts)
+ total += entry.second;
+ return total;
+}
+
+/* Bucket branches [BEGIN, END) onto the function each one leaves from, and
+ tally the edges entering each callee. Safe to run per worker on disjoint
+ slices, since FUNC_MAPS and ENTRY_EDGE_COUNTS are merged afterwards. */
+void
+assign_branch_edges_to_functions (
+ const std::vector<dwarf_debug::function_metadata> &symtab_functions,
+ const std::vector<perf_data::profile_branch> &branches, size_t begin,
+ size_t end, func_maps_type &func_maps,
+ entry_edge_count_by_addr &entry_edge_counts)
+{
+ uint64_t last_from = 0;
+ const dwarf_debug::function_metadata *func = nullptr;
+ for (size_t i = begin; i < end; ++i)
+ {
+ const perf_data::profile_branch &row = branches[i];
+ if (i == begin || row.from != last_from)
+ {
+ last_from = row.from;
+ func = dwarf_debug::function_containing_address (
+ symtab_functions, row.from);
+ }
+ if (func == nullptr)
+ continue;
+ get_or_create_function_maps (func_maps, *func)
+ .branch_count_map[{row.from, row.to}]
+ += row.count;
+ /* TODO: any edge to a function entry counts as a call, so a backedge to
+ this function's own entry is counted as a self-call. Telling the two
+ apart needs branch-type metadata from the sample. */
+ const dwarf_debug::function_metadata *callee
+ = dwarf_debug::function_at_entry_pc (symtab_functions, row.to);
+ if (callee != nullptr)
+ entry_edge_counts[callee->start_addr] += row.count;
+ }
+}
+
+/* Add COUNT to every function overlapping [BEGIN, END], splitting the range
+ at function boundaries and skipping the gaps between them. The scan
+ position lives in SYMTAB_SWEEP_INDEX, so ranges must arrive in order. */
+void
+assign_range_to_functions (
+ const std::vector<dwarf_debug::function_metadata> &symtab, uint64_t begin,
+ uint64_t end, uint64_t count, func_maps_type &func_maps,
+ size_t &symtab_sweep_index)
+{
+ uint64_t cursor = begin;
+ while (cursor <= end)
+ {
+ const dwarf_debug::function_metadata *func
+ = dwarf_debug::function_containing_address (symtab, cursor);
+ if (func != nullptr)
+ symtab_sweep_index = static_cast<size_t> (func - symtab.data ());
+ if (func == nullptr)
+ {
+ size_t next = symtab_sweep_index;
+ while (next < symtab.size ()
+ && symtab[next].start_addr <= cursor)
+ ++next;
+ if (next == symtab.size () || symtab[next].start_addr > end)
+ return;
+ symtab_sweep_index = next;
+ cursor = symtab[next].start_addr;
+ continue;
+ }
+ uint64_t segment_end = std::min (end, func->end_addr - 1);
+ size_t next = static_cast<size_t> (func - symtab.data ()) + 1;
+ while (next < symtab.size ()
+ && symtab[next].start_addr <= cursor)
+ ++next;
+ if (next < symtab.size ()
+ && symtab[next].start_addr <= segment_end)
+ segment_end = symtab[next].start_addr - 1;
+ get_or_create_function_maps (func_maps, *func)
+ .range_count_map[{cursor, segment_end}]
+ += count;
+ cursor = segment_end + 1;
+ }
+}
+
+/* CONFIGURED workers, capped at TASK_LIMIT so idle threads are not spawned,
+ and never fewer than one. */
+unsigned
+bounded_worker_count (unsigned configured, size_t task_limit)
+{
+ unsigned count = configured == 0 ? DEFAULT_CORRELATE_THREADS : configured;
+ if (task_limit > 0 && task_limit < count)
+ count = static_cast<unsigned> (task_limit);
+ return std::max (1u, count);
+}
+
+} /* anonymous namespace. */
+
+size_t
+estimate_correlate_target_work (const correlate_target &target,
+ unsigned addr_step)
+{
+ size_t work = target.maps.branch_count_map.size ()
+ + target.maps.addr_counts.size ()
+ + target.line_span_anchor_pcs.size ();
+ for (const auto &entry : target.maps.range_count_map)
+ {
+ const perf_data::branch_stack_edge &range = entry.first;
+ if (entry.second != 0 && range.second >= range.first)
+ work
+ += static_cast<size_t> ((range.second - range.first) / addr_step + 1);
+ }
+ return work;
+}
+
+/* Give every target a profile and builder, and seed its line-span anchors.
+ Runs single-threaded before the workers start. */
+void
+materialize_correlate_targets (correlate_context &ctx, profile_builder
&profile)
+{
+ const std::vector<dwarf_debug::function_metadata> &symtab
+ = ctx.reader.symtab_functions ();
+ profile.reserve_profiles (ctx.targets.size ());
+ ctx.emitted_hot_symbols.reserve (ctx.targets.size ());
+ for (correlate_target &target : ctx.targets)
+ {
+ ctx.emitted_hot_symbols.insert (
+ {target.func_name, target.maps.start_addr});
+ target.func_profile = &profile.get_or_create_function_profile (
+ dwarf_debug::string_value (target.func_name), target.maps.start_addr);
+ profile.init_function_builder (
+ *target.func_profile, symtab[target.symtab_index]);
+ target.func_profile->builder->add_incoming_entry_count (
+ target.maps.incoming_entry_count);
+ collect_target_line_span_anchors (ctx.reader, target);
+ }
+}
+
+/* Bucket all of PERF's mass onto symtab functions and keep, as CTX.targets,
+ those whose emit group clears the threshold. False when nothing survives,
+ which leaves no profile worth writing. */
+bool
+bucket_and_select_targets (correlate_context &ctx,
+ const perf_data::profile_reader &perf,
+ const profiler_run_options &run_opts)
+{
+ const std::vector<dwarf_debug::function_metadata> &symtab
+ = ctx.reader.symtab_functions ();
+ if (symtab.empty ())
+ {
+ fprintf (stderr,
+ _("Error: correlate failed: no ELF symtab functions\n"));
+ return false;
+ }
+
+ const uint64_t emit_threshold
+ = gcov_emit_threshold (perf, run_opts.sample_threshold_frac);
+
+ /* Range counts carry the branch-stack mass; without them the profile falls
+ back to plain address frequencies below. */
+ const auto *ranges
+ = run_opts.use_branch_stack ? perf.range_counts () : nullptr;
+ func_maps_type func_maps;
+ if (ranges != nullptr)
+ {
+ size_t sweep_index = 0;
+ for (const perf_data::profile_range &row : *ranges)
+ assign_range_to_functions
+ (symtab, row.beg, row.end, row.count, func_maps, sweep_index);
+ }
+
+ entry_edge_count_by_addr entry_edge_counts;
+ const auto *branches = perf.branch_counts ();
+ if (branches != nullptr && !branches->empty ())
+ {
+ const size_t count = branches->size ();
+ const unsigned workers
+ = bounded_worker_count (run_opts.correlate_threads, count);
+ if (workers <= 1 || count < MIN_BRANCHES_FOR_PARALLEL_SWEEP)
+ assign_branch_edges_to_functions (
+ symtab, *branches, 0, count, func_maps, entry_edge_counts);
+ else
+ {
+ const size_t chunk = (count + workers - 1) / workers;
+ std::vector<func_maps_type> partials (workers);
+ std::vector<entry_edge_count_by_addr> edge_partials (workers);
+ std::vector<std::thread> threads;
+ threads.reserve (workers);
+ for (size_t i = 0; i < workers; ++i)
+ {
+ const size_t begin = i * chunk;
+ if (begin >= count)
+ break;
+ const size_t end = std::min (count, begin + chunk);
+ threads.emplace_back (
+ [&symtab, branches, &partials, &edge_partials, i, begin, end] {
+ assign_branch_edges_to_functions (symtab,
+ *branches,
+ begin,
+ end,
+ partials[i],
+ edge_partials[i]);
+ });
+ }
+ for (std::thread &thread : threads)
+ thread.join ();
+ for (const func_maps_type &part : partials)
+ for (const auto &entry : part)
+ {
+ perf_data::branch_stack_edge_count_map &dst
+ = get_or_create_function_maps (func_maps, *entry.first)
+ .branch_count_map;
+ for (const auto &edge : entry.second.branch_count_map)
+ dst[edge.first] += edge.second;
+ }
+ for (const entry_edge_count_by_addr &part : edge_partials)
+ for (const auto &entry : part)
+ entry_edge_counts[entry.first] += entry.second;
+ }
+ }
+
+ if (ranges == nullptr)
+ for (const auto &entry : perf.get_address_frequencies ())
+ {
+ const dwarf_debug::function_metadata *func
+ = dwarf_debug::function_containing_address (symtab, entry.first);
+ if (func != nullptr)
+ get_or_create_function_maps (func_maps, *func)
+ .addr_counts[entry.first]
+ += entry.second;
+ }
+
+ if (!perf.has_sample_mass ())
+ {
+ fprintf (stderr,
+ _("Error: correlate failed: perf profile has no sample mass\n"));
+ return false;
+ }
+
+ std::unordered_map<func_map_key, function_emit_group_key> group_by_func;
+ group_mass_map group_mass;
+ group_by_func.reserve (func_maps.size ());
+ group_mass.reserve (func_maps.size ());
+ for (const auto &entry : func_maps)
+ {
+ const function_emit_group_key key = function_emit_group (*entry.first);
+ group_by_func.emplace (entry.first, key);
+ group_mass[key] += per_function_profile_mass (entry.second);
+ }
+
+ std::unordered_set<function_emit_group_key, function_emit_group_hash>
+ emitted_groups;
+ for (const auto &entry : group_mass)
+ if (entry.second >= emit_threshold)
+ emitted_groups.insert (entry.first);
+
+ ctx.targets.reserve (func_maps.size ());
+ for (auto &entry : func_maps)
+ {
+ const dwarf_debug::function_metadata *func = entry.first;
+ per_function_profile_maps &maps = entry.second;
+ if (!per_function_maps_have_samples (maps, run_opts.use_branch_stack)
+ || emitted_groups.count (group_by_func.find (func)->second) == 0)
+ continue;
+ const size_t symtab_index = static_cast<size_t> (func - symtab.data ());
+ const auto edge = entry_edge_counts.find (func->start_addr);
+ if (edge != entry_edge_counts.end ())
+ maps.incoming_entry_count = edge->second;
+ correlate_target target;
+ target.func_name = func->name;
+ target.symtab_index = symtab_index;
+ target.maps = std::move (maps);
+ ctx.targets.push_back (std::move (target));
+ }
+
+ if (ctx.targets.empty ())
+ {
+ fprintf (stderr,
+ _("Error: correlate failed: no functions above "
+ "emit threshold\n"));
+ return false;
+ }
+ ctx.num_threads
+ = bounded_worker_count (run_opts.correlate_threads, ctx.targets.size ());
+ return true;
+}
+
+} /* namespace correlate_detail. */
+} /* namespace autofdo. */
diff --git a/afdo_tools/src/autofdo_correlate_detail.h
b/afdo_tools/src/autofdo_correlate_detail.h
new file mode 100644
index 00000000000..4f20f7c1f3a
--- /dev/null
+++ b/afdo_tools/src/autofdo_correlate_detail.h
@@ -0,0 +1,94 @@
+/* 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/>. */
+
+#ifndef GCC_AUTOFDO_CORRELATE_DETAIL_H
+#define GCC_AUTOFDO_CORRELATE_DETAIL_H
+
+#include "autofdo_model.h"
+#include "dwarf_reader.h"
+#include "profile_reader.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+namespace autofdo {
+
+struct profiler_run_options;
+
+namespace correlate_detail {
+
+constexpr size_t NO_SYMTAB_INDEX = std::numeric_limits<size_t>::max ();
+
+using hot_symbol_set
+ = std::unordered_set<dwarf_debug::function_instance_key,
+ dwarf_debug::function_instance_key_hash>;
+
+/* Raw perf mass bucketed to one function, before any symbolization. */
+struct per_function_profile_maps
+{
+ uint64_t start_addr = 0;
+ uint64_t end_addr = 0;
+ uint64_t incoming_entry_count = 0;
+ perf_data::branch_stack_edge_count_map range_count_map;
+ perf_data::branch_stack_edge_count_map branch_count_map;
+ std::unordered_map<uint64_t, uint64_t> addr_counts;
+};
+
+/* One function selected for the profile, and everything a worker needs to
+ fill it in. */
+struct correlate_target
+{
+ dwarf_debug::interned_string func_name = nullptr;
+ size_t symtab_index = NO_SYMTAB_INDEX;
+ per_function_profile_maps maps;
+ std::vector<uint64_t> line_span_anchor_pcs;
+ size_t estimated_work = 0;
+ function_profile *func_profile = nullptr;
+};
+
+/* State every correlate worker shares; const once the workers start. */
+struct correlate_context
+{
+ dwarf_debug::dwarf_reader &reader;
+ std::vector<correlate_target> targets;
+ hot_symbol_set emitted_hot_symbols;
+ unsigned num_threads = 0;
+ unsigned range_mass_addr_step = 1;
+
+ explicit correlate_context (dwarf_debug::dwarf_reader &dw)
+ : reader (dw)
+ {
+ }
+};
+
+bool bucket_and_select_targets (correlate_context &,
+ const perf_data::profile_reader &,
+ const profiler_run_options &);
+void materialize_correlate_targets (correlate_context &, profile_builder &);
+size_t estimate_correlate_target_work (const correlate_target &, unsigned);
+size_t run_correlate_target_workers (correlate_context &,
+ dwarf_debug::correlate_symbolize_map *);
+
+} /* namespace correlate_detail. */
+} /* namespace autofdo. */
+
+#endif /* GCC_AUTOFDO_CORRELATE_DETAIL_H. */
--
2.34.1
