Add the symbol-name, source-path and function-lookup helpers shared by
the DWARF reader and the two correlation passes.
A profile must be keyed on the names a later compilation looks up, so
clone suffixes (.isra.N, .constprop.N, .cold, ...) are stripped, and
source paths are canonicalized when interned and compared component-wise
because DWARF spells one file differently between compilation units.
Merging a name into its parent is a separate, narrower rule, so a
specialized clone keeps its own counts rather than being absorbed by a
sibling.
Address lookup allows for the overlapping ranges that aliases, ICF and
.cold partitioning produce; callees resolve only at an exact entry PC.
afdo_tools/ChangeLog:
* src/symbol_util.cc: New file.
* src/symbol_util.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/symbol_util.cc | 246 ++++++++++++++++++++++++++++++++++
afdo_tools/src/symbol_util.h | 69 ++++++++++
2 files changed, 315 insertions(+)
create mode 100644 afdo_tools/src/symbol_util.cc
create mode 100644 afdo_tools/src/symbol_util.h
diff --git a/afdo_tools/src/symbol_util.cc b/afdo_tools/src/symbol_util.cc
new file mode 100644
index 00000000000..cc868049e92
--- /dev/null
+++ b/afdo_tools/src/symbol_util.cc
@@ -0,0 +1,246 @@
+/* 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 "symbol_util.h"
+
+#include <algorithm>
+
+namespace gcc_symbol {
+
+namespace {
+
+const char *const GCC_GENERATED_SUFFIX_TAGS[] = {
+ ".isra", ".constprop", ".part", ".__part", ".lto_priv", ".clone",
+ ".cold", ".hot"
+};
+
+const char *const GCC_SPLIT_PART_TAGS[] = {".cold", ".hot"};
+const char *const GCC_DOTTED_COPY_TAGS[] = {".llvm.", ".__part."};
+
+bool
+is_digit_suffix (const std::string &s)
+{
+ if (s.empty ())
+ return false;
+ for (unsigned char c : s)
+ if (c < '0' || c > '9')
+ return false;
+ return true;
+}
+
+bool
+is_gcc_generated_suffix_tag (const std::string &tag)
+{
+ for (const char *candidate : GCC_GENERATED_SUFFIX_TAGS)
+ if (tag == candidate)
+ return true;
+ return false;
+}
+
+void
+erase_last_tag (std::string &name, const std::string &tag)
+{
+ const size_t at = name.rfind (tag);
+ if (at == std::string::npos)
+ return;
+ const size_t after = at + tag.size ();
+ if (after == name.size ())
+ {
+ name.erase (at);
+ return;
+ }
+ if (name[after] == '.' && is_digit_suffix (name.substr (after + 1)))
+ name.erase (at);
+}
+
+void
+erase_last_dotted_tag (std::string &name, const std::string &tag)
+{
+ const size_t at = name.rfind (tag);
+ if (at == std::string::npos)
+ return;
+ const size_t app = at + tag.size ();
+ const size_t next = name.find ('.', app);
+ const size_t app_end = next == std::string::npos ? name.size () : next;
+ if (app == app_end
+ || !is_digit_suffix (name.substr (app, app_end - app)))
+ return;
+ name.erase (at, app_end - at);
+}
+
+} /* anonymous namespace. */
+
+std::string
+symbol_base_name (std::string name)
+{
+ for (;;)
+ {
+ const size_t dot = name.rfind ('.');
+ if (dot == std::string::npos || dot + 1 >= name.size ())
+ break;
+
+ const std::string tail = name.substr (dot + 1);
+ if (tail == "cold" || tail == "hot")
+ {
+ name.erase (dot);
+ continue;
+ }
+
+ if (dot == 0 || !is_digit_suffix (tail))
+ break;
+
+ const size_t prev = name.rfind ('.', dot - 1);
+ if (prev == std::string::npos
+ || !is_gcc_generated_suffix_tag (name.substr (prev, dot - prev)))
+ break;
+
+ name.erase (prev);
+ }
+ return name;
+}
+
+std::string
+symbol_split_part_parent (std::string name)
+{
+ for (const char *tag : GCC_SPLIT_PART_TAGS)
+ erase_last_tag (name, tag);
+ for (const char *tag : GCC_DOTTED_COPY_TAGS)
+ erase_last_dotted_tag (name, tag);
+ return name;
+}
+
+bool
+name_equivalent (const std::string &a, const std::string &b)
+{
+ if (a.empty () || b.empty ())
+ return false;
+ if (a == b)
+ return true;
+ const std::string a_part = symbol_split_part_parent (a);
+ const std::string b_part = symbol_split_part_parent (b);
+ if (a_part == b_part)
+ return true;
+ const std::string a_base = symbol_base_name (a_part);
+ const std::string b_base = symbol_base_name (b_part);
+ return a_base == b_base && (a_part == a_base || b_part == b_base);
+}
+
+} /* namespace gcc_symbol. */
+
+namespace source_path {
+
+bool
+ends_with (const std::string &s, const std::string &suffix)
+{
+ return s.size () >= suffix.size ()
+ && s.compare (s.size () - suffix.size (), suffix.size (), suffix) == 0;
+}
+
+bool
+equivalent (const std::string &a, const std::string &b)
+{
+ if (a == b)
+ return true;
+ if (a.empty () || b.empty ())
+ return false;
+ const auto is_separator = [] (char c) { return c == '/' || c == '\\'; };
+ const std::string &longer = a.size () > b.size () ? a : b;
+ const std::string &shorter = a.size () > b.size () ? b : a;
+ if (is_separator (shorter[0]) || !ends_with (longer, shorter))
+ return false;
+ const size_t start = longer.size () - shorter.size ();
+ return start != 0 && is_separator (longer[start - 1]);
+}
+
+} /* namespace source_path. */
+
+namespace dwarf_debug {
+
+namespace {
+
+bool
+function_has_valid_range (const function_metadata &func)
+{
+ return func.end_addr > func.start_addr;
+}
+
+bool
+address_in_function_range (const function_metadata &func, uint64_t address)
+{
+ return address >= func.start_addr && address < func.end_addr;
+}
+
+} /* anonymous namespace. */
+
+const function_metadata *
+function_containing_address (const std::vector<function_metadata> &funcs,
+ uint64_t address)
+{
+ if (funcs.empty ())
+ return nullptr;
+ auto it
+ = std::upper_bound (funcs.begin (),
+ funcs.end (),
+ address,
+ [] (uint64_t addr, const function_metadata &func)
+ {
+ return addr < func.start_addr;
+ });
+ if (it == funcs.begin ())
+ return nullptr;
+ size_t last = static_cast<size_t> (it - funcs.begin ()) - 1;
+ while (true)
+ {
+ const function_metadata &func = funcs[last];
+ if (address_in_function_range (func, address))
+ {
+ const function_metadata *best = &func;
+ while (last > 0 && funcs[last - 1].start_addr == func.start_addr)
+ {
+ --last;
+ if (address_in_function_range (funcs[last], address))
+ best = &funcs[last];
+ }
+ return best;
+ }
+ if (last == 0)
+ return nullptr;
+ --last;
+ }
+}
+
+const function_metadata *
+function_at_entry_pc (const std::vector<function_metadata> &funcs, uint64_t pc)
+{
+ if (funcs.empty ())
+ return nullptr;
+ auto it
+ = std::lower_bound (funcs.begin (),
+ funcs.end (),
+ pc,
+ [] (const function_metadata &func, uint64_t addr)
+ {
+ return func.start_addr < addr;
+ });
+ for (; it != funcs.end () && it->start_addr == pc; ++it)
+ if (!string_empty (it->name) && function_has_valid_range (*it))
+ return &*it;
+ return nullptr;
+}
+
+} /* namespace dwarf_debug. */
diff --git a/afdo_tools/src/symbol_util.h b/afdo_tools/src/symbol_util.h
new file mode 100644
index 00000000000..77ce5f7c2e2
--- /dev/null
+++ b/afdo_tools/src/symbol_util.h
@@ -0,0 +1,69 @@
+/* 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_SYMBOL_UTIL_H
+#define GCC_SYMBOL_UTIL_H
+
+#include "dwarf_types.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <string>
+#include <vector>
+
+namespace gcc_symbol {
+
+/* NAME with every trailing GCC clone suffix stripped: .isra.N, .constprop.N,
+ .lto_priv.N, .cold, .hot, ... */
+std::string symbol_base_name (std::string name);
+
+/* Name shared by a function and its split parts for emit accounting. */
+std::string symbol_split_part_parent (std::string name);
+
+/* Match split parts or a generated variant with its unsuffixed function. */
+bool name_equivalent (const std::string &a, const std::string &b);
+
+} /* namespace gcc_symbol. */
+
+namespace source_path {
+
+/* C++14 stand-in for std::string::ends_with (C++20). */
+bool ends_with (const std::string &s, const std::string &suffix);
+
+/* True when paths are equal or one is a relative component suffix of the
+ other. */
+bool equivalent (const std::string &a, const std::string &b);
+
+} /* namespace source_path. */
+
+namespace dwarf_debug {
+
+/* Find the function containing ADDRESS in a start-sorted function list.
+ Overlapping ranges require checking earlier starts too. */
+const function_metadata *
+function_containing_address (const std::vector<function_metadata> &funcs,
+ uint64_t address);
+
+/* Resolve a callee only at an exact symtab entry PC. */
+const function_metadata *
+function_at_entry_pc (const std::vector<function_metadata> &funcs,
+ uint64_t pc);
+
+} /* namespace dwarf_debug. */
+
+#endif /* GCC_SYMBOL_UTIL_H. */
--
2.34.1
