Add the common machinery for translating branch-stack samples and runtime
mappings into file-relative ranges and edges. Backend-specific readers
build on this normalization layer.
afdo_tools/ChangeLog:
* src/branch_stack_reader_base.cc: New file.
* src/branch_stack_reader_base.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/branch_stack_reader_base.cc | 221 +++++++++++++++++++++
afdo_tools/src/branch_stack_reader_base.h | 96 +++++++++
2 files changed, 317 insertions(+)
create mode 100644 afdo_tools/src/branch_stack_reader_base.cc
create mode 100644 afdo_tools/src/branch_stack_reader_base.h
diff --git a/afdo_tools/src/branch_stack_reader_base.cc
b/afdo_tools/src/branch_stack_reader_base.cc
new file mode 100644
index 00000000000..36ead47edef
--- /dev/null
+++ b/afdo_tools/src/branch_stack_reader_base.cc
@@ -0,0 +1,221 @@
+/* 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 "branch_stack_reader_base.h"
+
+#include "profile_reader.h"
+
+#include <algorithm>
+#include <cstddef>
+
+namespace perf_data {
+namespace {
+
+/* Upper bound on a plausible fall-through range between two consecutive
+ branches. Anything larger is treated as a bogus/wrong-path interval and
+ dropped rather than inflating range mass. */
+constexpr uint64_t MAX_BETWEEN_BRANCH_RANGE_BYTES = 1ull << 20;
+
+bool
+branch_entry_wrong_path (uint64_t flags) noexcept
+{
+ return (flags & perf_branch_spec::MASK) == perf_branch_spec::WRONG_PATH;
+}
+
+size_t
+skip_wrong_path_prefix (const perf_branch_stack_entry *entries, size_t n)
+{
+ size_t i = 0;
+ while (i < n && branch_entry_wrong_path (entries[i].flags))
+ ++i;
+ return i;
+}
+
+/* Translate the inclusive range from RUNTIME_START to RUNTIME_END when both
+ ends share one mapping. HINT_INDEX, when provided, is tried first and
+ updated on success. */
+bool
+translate_runtime_range_with_mmaps (const std::vector<simple_mmap> &mmaps,
+ uint64_t runtime_start,
+ uint64_t runtime_end, uint64_t *file_start,
+ uint64_t *file_end,
+ size_t *hint_index = nullptr)
+{
+ if (file_start == nullptr || file_end == nullptr
+ || runtime_end < runtime_start)
+ return false;
+
+ const auto try_one = [&] (const simple_mmap &m) -> bool {
+ if (runtime_start < m.start_addr || runtime_end >= m.end_addr)
+ return false;
+ *file_start = m.to_dwarf_address (runtime_start);
+ *file_end = m.to_dwarf_address (runtime_end);
+ return true;
+ };
+
+ if (hint_index != nullptr && *hint_index < mmaps.size ())
+ {
+ if (try_one (mmaps[*hint_index]))
+ return true;
+ }
+
+ for (size_t i = 0; i < mmaps.size (); ++i)
+ {
+ if (!try_one (mmaps[i]))
+ continue;
+ if (hint_index != nullptr)
+ *hint_index = i;
+ return true;
+ }
+ return false;
+}
+
+} /* namespace. */
+
+/* LBR ingest: skip WRONG_PATH at stack head; record head branch; walk older
+ entries for [to, prev.from) ranges and explicit (from, to) edges. */
+bool
+branch_stack_reader_base::accumulate_branch_stack_sample (
+ const perf_branch_stack_entry *entries, uint64_t num_branches,
+ profile_reader ×tamps, uint64_t sample_time,
+ const std::vector<simple_mmap> &target_mmaps,
+ branch_stack_edge_count_map &range_count_map,
+ branch_stack_edge_count_map &branch_count_map) const
+{
+ if (entries == nullptr || num_branches == 0
+ || num_branches > static_cast<uint64_t> (SIZE_MAX))
+ return false;
+
+ const size_t n = static_cast<size_t> (num_branches);
+ const size_t start = skip_wrong_path_prefix (entries, n);
+ if (start >= n)
+ return false;
+
+ bool any = false;
+
+ /* LBR/BRBE has no per-entry timestamps. Use the enclosing sample time as
+ an upper bound for accepted branch and range endpoints. */
+ const perf_branch_stack_entry &head = entries[start];
+ uint64_t head_from = 0;
+ uint64_t head_to = 0;
+ if (try_translate_runtime_with_mmaps (target_mmaps, head.from, &head_from)
+ && try_translate_runtime_with_mmaps (target_mmaps, head.to, &head_to))
+ {
+ branch_count_map[{head_from, head_to}]++;
+ timestamps.note_sample_timestamp (head_from, sample_time);
+ timestamps.note_sample_timestamp (head_to, sample_time);
+ any = true;
+ }
+
+ bool adjacent_to_newer_entry = true;
+ for (size_t i = start + 1; i < n; ++i)
+ {
+ const perf_branch_stack_entry &e = entries[i];
+ if (branch_entry_wrong_path (e.flags))
+ {
+ /* A rejected entry leaves no known fall-through path between the
+ entries on either side. Do not bridge across it. */
+ adjacent_to_newer_entry = false;
+ continue;
+ }
+ uint64_t edge_to = 0;
+ const bool target_to
+ = try_translate_runtime_with_mmaps (target_mmaps, e.to, &edge_to);
+ if (adjacent_to_newer_entry && target_to)
+ {
+ const uint64_t begin = e.to;
+ const uint64_t end = entries[i - 1].from;
+ if (end >= begin
+ && end - begin <= MAX_BETWEEN_BRANCH_RANGE_BYTES)
+ {
+ uint64_t dwarf_begin = 0;
+ uint64_t dwarf_end = 0;
+ if (translate_runtime_range_with_mmaps (
+ target_mmaps, begin, end, &dwarf_begin, &dwarf_end))
+ {
+ range_count_map[{dwarf_begin, dwarf_end}]++;
+ timestamps.note_sample_timestamp (dwarf_begin, sample_time);
+ any = true;
+ }
+ }
+ }
+
+ uint64_t edge_from = 0;
+ if (target_to
+ && try_translate_runtime_with_mmaps (
+ target_mmaps, e.from, &edge_from))
+ {
+ branch_count_map[{edge_from, edge_to}]++;
+ timestamps.note_sample_timestamp (edge_from, sample_time);
+ any = true;
+ }
+ adjacent_to_newer_entry = true;
+ }
+ return any;
+}
+
+/* Publish already-translated range and branch maps. */
+void
+branch_stack_reader_base::publish_dwarf_branch_stack_maps (
+ branch_stack_edge_count_map &range_count_map,
+ branch_stack_edge_count_map &branch_count_map,
+ std::vector<uint64_t> *touch_pcs_out)
+{
+ sorted_ranges_.clear ();
+ sorted_ranges_.reserve (range_count_map.size ());
+ for (const auto &entry : range_count_map)
+ sorted_ranges_.push_back (
+ profile_range{entry.first.first, entry.first.second, entry.second});
+ range_count_map.clear ();
+ range_count_map.rehash (0);
+ std::sort (sorted_ranges_.begin (), sorted_ranges_.end ());
+
+ sorted_branches_.clear ();
+ sorted_branches_.reserve (branch_count_map.size ());
+ for (const auto &entry : branch_count_map)
+ sorted_branches_.push_back (
+ profile_branch{entry.first.first, entry.first.second, entry.second});
+ branch_count_map.clear ();
+ branch_count_map.rehash (0);
+ std::sort (sorted_branches_.begin (), sorted_branches_.end ());
+
+ branch_stack_finalized_ = true;
+ build_sorted_touch_pcs_from_ranges (touch_pcs_out);
+}
+
+/* Fill TOUCH_PCS with the unique sorted endpoints of the finalized ranges. */
+void
+branch_stack_reader_base::build_sorted_touch_pcs_from_ranges (
+ std::vector<uint64_t> *touch_pcs) const
+{
+ if (touch_pcs == nullptr || sorted_ranges_.empty ())
+ return;
+
+ touch_pcs->clear ();
+ touch_pcs->reserve (sorted_ranges_.size () * 2);
+ for (const profile_range &row : sorted_ranges_)
+ {
+ touch_pcs->push_back (row.beg);
+ touch_pcs->push_back (row.end);
+ }
+ std::sort (touch_pcs->begin (), touch_pcs->end ());
+ touch_pcs->erase (
+ std::unique (touch_pcs->begin (), touch_pcs->end ()), touch_pcs->end ());
+}
+
+} /* namespace perf_data. */
diff --git a/afdo_tools/src/branch_stack_reader_base.h
b/afdo_tools/src/branch_stack_reader_base.h
new file mode 100644
index 00000000000..c0773cfd877
--- /dev/null
+++ b/afdo_tools/src/branch_stack_reader_base.h
@@ -0,0 +1,96 @@
+/* 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_BRANCH_STACK_READER_BASE_H
+#define GCC_BRANCH_STACK_READER_BASE_H
+
+#include "perf.h"
+
+#include <cstdint>
+#include <unordered_map>
+#include <vector>
+
+namespace perf_data {
+
+class profile_reader;
+
+/* Shared branch-stack and range ingestion for profile readers. */
+class branch_stack_reader_base
+{
+public:
+ virtual ~branch_stack_reader_base () = default;
+
+ /* Stop folding sample IPs into the address frequencies. Readers that never
+ accumulate them are unaffected. */
+ void disable_sample_ip_accumulation ()
+ {
+ accumulate_sample_ips_ = false;
+ }
+
+ /* Instruction granularity for expanding branch-stack range mass. */
+ virtual unsigned range_mass_addr_step () const { return 1; }
+
+ bool has_finalized_profile () const { return branch_stack_finalized_; }
+
+ const std::vector<profile_range> &sorted_ranges () const
+ {
+ return sorted_ranges_;
+ }
+
+ const std::vector<profile_branch> &sorted_branches () const
+ {
+ return sorted_branches_;
+ }
+
+protected:
+ bool branch_stack_finalized_ = false;
+ bool accumulate_sample_ips_ = true;
+ std::vector<profile_range> sorted_ranges_;
+ std::vector<profile_branch> sorted_branches_;
+
+ /* Discard the profile built by a previous load so it can be rebuilt. */
+ void reset_branch_stack_profile ()
+ {
+ branch_stack_finalized_ = false;
+ sorted_ranges_.clear ();
+ sorted_branches_.clear ();
+ }
+
+ /* Publish maps whose keys are already DWARF addresses. */
+ void publish_dwarf_branch_stack_maps (
+ branch_stack_edge_count_map &range_count_map,
+ branch_stack_edge_count_map &branch_count_map,
+ std::vector<uint64_t> *touch_pcs_out);
+
+ /* Collect the unique sorted range endpoints into TOUCH_PCS. */
+ void
+ build_sorted_touch_pcs_from_ranges (std::vector<uint64_t> *touch_pcs) const;
+
+ /* Fold one sample's branch stack into the range and edge maps; returns
+ true when anything was accumulated. */
+ bool accumulate_branch_stack_sample (
+ const perf_branch_stack_entry *entries, uint64_t num_branches,
+ profile_reader ×tamps, uint64_t sample_time,
+ const std::vector<simple_mmap> &target_mmaps,
+ branch_stack_edge_count_map &range_count_map,
+ branch_stack_edge_count_map &branch_count_map) const;
+};
+
+} /* namespace perf_data. */
+
+#endif /* GCC_BRANCH_STACK_READER_BASE_H. */
--
2.34.1
