Add the correlation-side profile builders used to accumulate function,
source-position, callsite, and indirect-call counts. This model is
independent of perf ingestion and GCOV serialization.
afdo_tools/ChangeLog:
* src/autofdo_model.cc: New file.
* src/autofdo_model.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_model.cc | 324 ++++++++++++++++++++++++++++++++
afdo_tools/src/autofdo_model.h | 190 +++++++++++++++++++
2 files changed, 514 insertions(+)
create mode 100644 afdo_tools/src/autofdo_model.cc
create mode 100644 afdo_tools/src/autofdo_model.h
diff --git a/afdo_tools/src/autofdo_model.cc b/afdo_tools/src/autofdo_model.cc
new file mode 100644
index 00000000000..dab8c2b466b
--- /dev/null
+++ b/afdo_tools/src/autofdo_model.cc
@@ -0,0 +1,324 @@
+/* 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_model.h"
+
+#include "dwarf_reader.h"
+#include "gcov_discriminator_encoding.h"
+#include "profile_reader.h"
+
+#include <algorithm>
+#include <map>
+#include <memory>
+#include <string>
+#include <vector>
+
+namespace autofdo {
+
+function_builder::function_builder (const function_builder &other)
+ : name (other.name), file_path (other.file_path),
+ start_line (other.start_line), discriminator (other.discriminator),
+ head_count (other.head_count),
+ position_count_values (other.position_count_values),
+ position_target_values (other.position_target_values)
+{
+ for (const auto &entry : other.callsite_nodes)
+ callsite_nodes.emplace (
+ entry.first, std::make_unique<function_builder> (*entry.second));
+}
+
+/* Give FUNC_PROFILE a builder seeded from FUNC's name, file and decl line,
+ if it does not have one yet. */
+void
+profile_builder::init_function_builder (
+ function_profile &func_profile, const dwarf_debug::function_metadata &func)
+{
+ if (!func_profile.builder)
+ {
+ auto builder = std::make_unique<function_builder> ();
+ builder->name = dwarf_debug::string_value (func.name);
+ builder->file_path = dwarf_debug::string_value (func.file_path);
+ /* start_line: DECL_SOURCE_LINE base for relative offsets. */
+ builder->start_line = func.start_line;
+ func_profile.builder = std::move (builder);
+ }
+}
+
+/* The profile for NAME at START_ADDR, created empty on first request. */
+function_profile &
+profile_builder::get_or_create_function_profile (const std::string &name,
+ uint64_t start_addr)
+{
+ function_profile_key key{name, start_addr};
+ auto it = function_profiles.find (key);
+ if (it != function_profiles.end ())
+ return it->second;
+
+ auto inserted
+ = function_profiles.emplace (std::move (key), function_profile ());
+ inserted.first->second.start_addr = start_addr;
+ return inserted.first->second;
+}
+
+/* Attach PERF's per-function timestamps to the profiles now that correlation
+ has created them. */
+void
+profile_builder::finalize_after_correlate (
+ const perf_data::profile_reader &perf)
+{
+ for (const auto &entry : perf.function_timestamps ())
+ {
+ const uint64_t timestamp = entry.second;
+ if (timestamp == 0)
+ continue;
+ const function_profile_key &fp_key = entry.first;
+ auto fp_it = function_profiles.find (fp_key);
+ if (fp_it == function_profiles.end () || fp_it->second.builder ==
nullptr)
+ continue;
+ fp_it->second.timestamp = timestamp;
+ }
+
+ for (auto &kv : function_profiles)
+ {
+ function_profile &func_profile = kv.second;
+ if (!func_profile.builder)
+ continue;
+ func_profile.builder->collapse_copy_ids ();
+ func_profile.builder->estimate_head_count (/*toplevel=*/true);
+ func_profile.head_count = func_profile.builder->head_count;
+ func_profile.total_samples = func_profile.builder->compute_total_count
();
+ }
+}
+
+/* Give every alias in ALIASES its own profile copied from the primary it was
+ folded onto, so GCC can annotate whichever name it sees. */
+void
+profile_builder::materialize_alias_profiles (
+ const std::vector<dwarf_debug::function_metadata> &functions,
+ const std::vector<dwarf_debug::function_alias_metadata> &aliases)
+{
+ for (const dwarf_debug::function_alias_metadata &alias : aliases)
+ {
+ if (alias.primary_index >= functions.size ())
+ continue;
+ const dwarf_debug::function_metadata &primary
+ = functions[alias.primary_index];
+ const function_profile_key primary_key{
+ dwarf_debug::string_value (primary.name), primary.start_addr};
+ const auto primary_it = function_profiles.find (primary_key);
+ if (primary_it == function_profiles.end ()
+ || primary_it->second.builder == nullptr
+ || primary_it->second.total_samples == 0)
+ continue;
+
+ const dwarf_debug::function_metadata &alias_func = alias.function;
+ const function_profile_key alias_key{
+ dwarf_debug::string_value (alias_func.name), alias_func.start_addr};
+ if (function_profiles.find (alias_key) != function_profiles.end ())
+ continue;
+
+ function_profile copy;
+ copy.start_addr = alias_func.start_addr;
+ copy.total_samples = primary_it->second.total_samples;
+ copy.head_count = primary_it->second.head_count;
+ copy.timestamp = primary_it->second.timestamp;
+ copy.builder
+ = std::make_unique<function_builder> (*primary_it->second.builder);
+ copy.builder->name = dwarf_debug::string_value (alias_func.name);
+ copy.builder->file_path
+ = dwarf_debug::string_value (alias_func.file_path);
+ function_profiles.emplace (alias_key, std::move (copy));
+ }
+}
+
+/* Function-tree operations. */
+
+bool
+function_builder::has_sampled_mass () const
+{
+ for (const auto &entry : position_count_values)
+ if (entry.second != 0)
+ return true;
+ for (const auto &entry : callsite_nodes)
+ if (entry.second->has_sampled_mass ())
+ return true;
+ return false;
+}
+
+/* Give each callsite a position count equal to the entry count of the callee
+ it opens, so an inlined body's calls show up in the caller's line counts.
+
+ TODO: callsites nested inside an inlined body are left alone. Recursing
+ gives an offset that already holds a callsite a position count as well,
+ which inflates the totals reported for the enclosing functions. */
+void
+function_builder::materialize_callsite_entry_counts ()
+{
+ if (start_line == 0)
+ return;
+ for (auto &entry : callsite_nodes)
+ {
+ function_builder &child = *entry.second;
+ child.estimate_head_count (/*toplevel=*/false);
+ if (child.head_count == 0 || entry.first.call_line < start_line)
+ continue;
+
+ const uint32_t offset = entry.first.call_line - start_line;
+ if (!gcov_offset_fields_representable (offset))
+ continue;
+ const uint32_t disc = entry.first.call_disc != 0
+ ? entry.first.call_disc
+ : get_base_discriminator (child.discriminator);
+ uint64_t &count
+ = position_count_values[gcov_pack_line_disc (offset, disc)];
+ count = std::max (count, child.head_count);
+ }
+}
+
+/* Total count of this builder and everything inlined beneath it. */
+uint64_t
+function_builder::compute_total_count ()
+{
+ uint64_t t = 0;
+ for (const auto &kv : position_count_values)
+ t += kv.second;
+ for (auto &kv : callsite_nodes)
+ t += kv.second->compute_total_count ();
+ return t;
+}
+
+/* Work out the entry count when no incoming edge measured one, taking it
+ from mass at relative line 0 and leaving it alone otherwise. TOPLEVEL
+ functions fall back to 1 so GCC still sees them as executed. */
+void
+function_builder::estimate_head_count (bool toplevel)
+{
+ /* Keep a measured incoming-edge head_count. */
+ if (head_count != 0)
+ return;
+
+ /* Only relative line 0 is entry mass; do not promote body samples. */
+ for (const auto &pos_kv : position_count_values)
+ {
+ if (gcov_rel_line_from_packed (pos_kv.first) != 0)
+ break;
+ if (pos_kv.second == 0)
+ continue;
+ head_count = pos_kv.second;
+ break;
+ }
+ for (const auto &cs : callsite_nodes)
+ {
+ if (head_count != 0)
+ break;
+ const uint64_t cs_off
+ = profile_offset (cs.first.call_line, cs.first.call_disc);
+ if (cs_off == INVALID_PROFILE_OFFSET
+ || gcov_rel_line_from_packed (cs_off) != 0)
+ continue;
+ cs.second->estimate_head_count (/*toplevel=*/false);
+ head_count = cs.second->head_count;
+ }
+ if (head_count != 0)
+ return;
+
+ /* Top-level only: head_count=1 for unsampled entries GCC must annotate. */
+ if (toplevel && has_sampled_mass ())
+ head_count = 1;
+}
+
+/* Merge discriminators that differ only by copy id, so counts split across
+ loop or clone copies of one source position add back together. */
+void
+function_builder::collapse_copy_ids ()
+{
+ for (auto &kv : callsite_nodes)
+ kv.second->collapse_copy_ids ();
+
+ std::map<uint64_t, uint64_t> new_pos;
+ for (const auto &kv : position_count_values)
+ new_pos[gcov_repack_with_base_discriminator (kv.first)] += kv.second;
+ position_count_values = std::move (new_pos);
+
+ std::map<uint64_t, pos_target_map> new_targets;
+ for (auto &kv : position_target_values)
+ {
+ auto &slot = new_targets[gcov_repack_with_base_discriminator (kv.first)];
+ for (auto &tgt : kv.second)
+ slot[tgt.first] += tgt.second;
+ }
+ position_target_values = std::move (new_targets);
+}
+
+/* LINE and DISC_FULL packed as an offset relative to this function's decl
+ line, or INVALID_PROFILE_OFFSET when GCOV cannot represent it. */
+uint64_t
+function_builder::profile_offset (uint32_t line, uint32_t disc_full) const
+{
+ /* Relative offsets need a known DECL_SOURCE_LINE base. */
+ if (line == 0 || start_line == 0)
+ return INVALID_PROFILE_OFFSET;
+ if (line < start_line)
+ return INVALID_PROFILE_OFFSET;
+ const uint32_t rel = line - start_line;
+ const uint32_t disc_key = strip_multiplicity (disc_full);
+ if (!gcov_offset_fields_representable (rel))
+ return INVALID_PROFILE_OFFSET;
+ return gcov_pack_line_disc (rel, disc_key);
+}
+
+/* Open a child builder for the callsite KEY describes. */
+function_builder &
+function_builder::create_callsite (const callsite_key &key)
+{
+ auto child = std::make_unique<function_builder> ();
+ child->name = dwarf_debug::string_value (key.function_name);
+ child->discriminator = key.call_disc;
+ const auto inserted = callsite_nodes.emplace (key, std::move (child));
+ return *inserted.first->second;
+}
+
+/* Record COUNT at LINE and DISC, keeping the largest count seen there rather
+ than accumulating, since several PCs can map to one source position. */
+void
+function_builder::deposit_position_max (uint32_t line, uint32_t disc,
+ uint64_t count)
+{
+ const uint64_t offset = profile_offset (line, disc);
+ if (offset == INVALID_PROFILE_OFFSET)
+ return;
+ uint64_t &position_count = position_count_values[offset];
+ position_count = std::max (position_count, count);
+}
+
+/* Record COUNT calls to CALLEE_NAME at LINE and DISC, again keeping the
+ largest count rather than accumulating. */
+void
+function_builder::record_call_target_max (
+ uint32_t line, uint32_t disc, dwarf_debug::interned_string callee_name,
+ uint64_t count)
+{
+ const uint64_t offset = profile_offset (line, disc);
+ if (offset == INVALID_PROFILE_OFFSET)
+ return;
+ position_count_values.emplace (offset, 0);
+ uint64_t &target_count = position_target_values[offset][callee_name];
+ target_count = std::max (target_count, count);
+}
+
+} /* namespace autofdo. */
diff --git a/afdo_tools/src/autofdo_model.h b/afdo_tools/src/autofdo_model.h
new file mode 100644
index 00000000000..c5b92b3acd1
--- /dev/null
+++ b/afdo_tools/src/autofdo_model.h
@@ -0,0 +1,190 @@
+/* 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_MODEL_H
+#define GCC_AUTOFDO_MODEL_H
+
+#include "dwarf_types.h"
+#include "gcov.h"
+#include "hash_util.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <limits>
+#include <map>
+#include <memory>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+namespace dwarf_debug {
+class dwarf_reader;
+struct function_alias_metadata;
+struct function_metadata;
+} // namespace dwarf_debug
+
+namespace perf_data {
+class profile_reader;
+}
+
+namespace autofdo {
+
+/* Key for inline callsites. */
+struct callsite_key
+{
+ uint32_t call_line = 0;
+ uint32_t call_disc = 0;
+ dwarf_debug::interned_string function_name = nullptr;
+
+ bool operator< (const callsite_key &o) const noexcept
+ {
+ if (call_line != o.call_line)
+ return call_line < o.call_line;
+ if (call_disc != o.call_disc)
+ return call_disc < o.call_disc;
+ return dwarf_debug::string_value (function_name)
+ < dwarf_debug::string_value (o.function_name);
+ }
+};
+
+struct interned_string_less
+{
+ bool operator() (dwarf_debug::interned_string a,
+ dwarf_debug::interned_string b) const noexcept
+ {
+ return dwarf_debug::string_value (a) < dwarf_debug::string_value (b);
+ }
+};
+
+using pos_target_map
+ = std::map<dwarf_debug::interned_string, uint64_t, interned_string_less>;
+
+class function_builder
+{
+public:
+ using callsite_map
+ = std::map<callsite_key, std::unique_ptr<function_builder>>;
+ using position_count_map = std::map<uint64_t, uint64_t>;
+ using position_target_map = std::map<uint64_t, pos_target_map>;
+
+ /* profile_offset() result for a position GCOV cannot encode. */
+ static constexpr uint64_t INVALID_PROFILE_OFFSET
+ = std::numeric_limits<uint64_t>::max ();
+
+ function_builder () = default;
+ function_builder (const function_builder &);
+
+ std::string name;
+ std::string file_path;
+ uint32_t start_line = 0;
+ uint32_t discriminator = 0;
+ uint64_t head_count = 0;
+
+ uint64_t compute_total_count ();
+ void collapse_copy_ids ();
+ void estimate_head_count (bool toplevel);
+ uint64_t profile_offset (uint32_t line, uint32_t disc_full) const;
+ function_builder &create_callsite (const callsite_key &key);
+ void add_incoming_entry_count (uint64_t count)
+ {
+ head_count += count;
+ }
+ void deposit_position_max (uint32_t line, uint32_t disc, uint64_t count);
+ void record_call_target_max (uint32_t line, uint32_t disc,
+ dwarf_debug::interned_string callee_name,
+ uint64_t count);
+
+ const callsite_map &callsites () const { return callsite_nodes; }
+ const position_count_map &position_counts () const
+ {
+ return position_count_values;
+ }
+ const position_target_map &position_targets () const
+ {
+ return position_target_values;
+ }
+
+private:
+ friend class profile_builder;
+
+ bool has_sampled_mass () const;
+ void materialize_callsite_entry_counts ();
+
+ callsite_map callsite_nodes;
+ position_count_map position_count_values;
+ position_target_map position_target_values;
+};
+
+using function_profile_key = std::pair<std::string, uint64_t>;
+
+struct function_profile_key_hash
+{
+ size_t operator() (const function_profile_key &k) const noexcept
+ {
+ size_t h = std::hash<std::string>{}(k.first);
+ hash_combine (h, std::hash<uint64_t>{}(k.second));
+ return h;
+ }
+};
+
+struct function_profile
+{
+ uint64_t start_addr = 0;
+ uint64_t total_samples = 0;
+ uint64_t head_count = 0;
+ uint64_t timestamp = 0;
+ std::unique_ptr<function_builder> builder;
+
+ function_profile () = default;
+};
+
+class profile_builder
+{
+public:
+ using function_profile_map
+ = std::unordered_map<function_profile_key, function_profile,
+ function_profile_key_hash>;
+
+ void reserve_profiles (size_t n)
+ {
+ function_profiles.reserve (n);
+ }
+
+ function_profile &get_or_create_function_profile (const std::string &name,
+ uint64_t start_addr);
+
+ void init_function_builder (function_profile &func_profile,
+ const dwarf_debug::function_metadata &func);
+
+ void build_gcov_profile (gcov::gcov_profile &out);
+
+ void finalize_after_correlate (const perf_data::profile_reader &perf);
+ void materialize_alias_profiles (
+ const std::vector<dwarf_debug::function_metadata> &functions,
+ const std::vector<dwarf_debug::function_alias_metadata> &aliases);
+
+ profile_builder () = default;
+
+private:
+ function_profile_map function_profiles;
+};
+
+} /* namespace autofdo. */
+
+#endif /* GCC_AUTOFDO_MODEL_H. */
--
2.34.1
