From ee5abed3cda095115d5afb72c860819d9369fc45 Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Mon, 31 Mar 2025 04:22:52 -0600 Subject: measurestack: Split into several files --- build-aux/measurestack/analyze.py | 308 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 308 insertions(+) create mode 100644 build-aux/measurestack/analyze.py (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py new file mode 100644 index 0000000..67edd5d --- /dev/null +++ b/build-aux/measurestack/analyze.py @@ -0,0 +1,308 @@ +# build-aux/measurestack/analyze.py - Analyze stack sizes for compiled objects +# +# Copyright (C) 2024-2025 Luke T. Shumaker +# SPDX-License-Identifier: AGPL-3.0-or-later + +import re +import typing + +from . import vcg + +# pylint: disable=unused-variable +__all__ = [ + "BaseName", + "QName", + "UsageKind", + "Node", + "AnalyzeResultVal", + "AnalyzeResultGroup", + "AnalyzeResult", + "analyze", +] + + +class BaseName: + _content: str + + def __init__(self, content: str) -> None: + if ":" in content: + raise ValueError(f"invalid non-qualified name: {content!r}") + self._content = content + + def __str__(self) -> str: + return self._content + + def __repr__(self) -> str: + return f"BaseName({self._content!r})" + + def __format__(self, fmt_spec: str, /) -> str: + return repr(self) + + def __eq__(self, other: typing.Any) -> bool: + assert isinstance( + other, BaseName + ), f"comparing BaseName with {other.__class__.__name__}" + return self._content == other._content + + def __lt__(self, other: "BaseName") -> bool: + return self._content < other._content + + def __hash__(self) -> int: + return hash(self._content) + + def as_qname(self) -> "QName": + return QName(self._content) + + +class QName: + _content: str + + def __init__(self, content: str) -> None: + self._content = content + + def __str__(self) -> str: + return self._content + + def __repr__(self) -> str: + return f"QName({self._content!r})" + + def __format__(self, fmt_spec: str, /) -> str: + return repr(self) + + def __eq__(self, other: typing.Any) -> bool: + assert isinstance( + other, QName + ), f"comparing QName with {other.__class__.__name__}" + return self._content == other._content + + def __lt__(self, other: "QName") -> bool: + return self._content < other._content + + def __hash__(self) -> int: + return hash(self._content) + + def base(self) -> BaseName: + return BaseName(self._content.rsplit(":", 1)[-1].split(".", 1)[0]) + + +UsageKind: typing.TypeAlias = typing.Literal["static", "dynamic", "dynamic,bounded"] + + +class Node: + # from .title (`static` and `__weak` functions are prefixed with + # the compilation unit .c file. For static functions that's fine, + # but we'll have to handle it specially for __weak.). + funcname: QName + # .label is "{funcname}\n{location}\n{nstatic} bytes (static}\n{ndynamic} dynamic objects" + location: str + usage_kind: UsageKind + nstatic: int + ndynamic: int + + # edges with .sourcename set to this node, val is if it's + # OK/expected that the function be missing. + calls: dict[QName, bool] + + +class AnalyzeResultVal(typing.NamedTuple): + nstatic: int + cnt: int + + +class AnalyzeResultGroup(typing.NamedTuple): + rows: dict[QName, AnalyzeResultVal] + + +class AnalyzeResult(typing.NamedTuple): + groups: dict[str, AnalyzeResultGroup] + missing: set[QName] + dynamic: set[QName] + + included_funcs: set[QName] + + +class Application(typing.Protocol): + def extra_nodes(self) -> typing.Collection[Node]: ... + def indirect_callees( + self, elem: vcg.VCGElem + ) -> tuple[typing.Collection[QName], bool]: ... + def skip_call(self, chain: typing.Sequence[QName], funcname: QName) -> bool: ... + + +def analyze( + *, + ci_fnames: typing.Collection[str], + app_func_filters: dict[str, typing.Callable[[QName], tuple[int, bool]]], + app: Application, + cfg_max_call_depth: int, +) -> AnalyzeResult: + re_node_label = re.compile( + r"(?P[^\n]+)\n" + + r"(?P[^\n]+:[0-9]+:[0-9]+)\n" + + r"(?P[0-9]+) bytes \((?Pstatic|dynamic|dynamic,bounded)\)\n" + + r"(?P[0-9]+) dynamic objects" + + r"(?:\n.*)*", + flags=re.MULTILINE, + ) + + graph: dict[QName, Node] = {} + qualified: dict[BaseName, set[QName]] = {} + + def handle_elem(elem: vcg.VCGElem) -> None: + match elem.typ: + case "node": + node = Node() + node.calls = {} + skip = False + for k, v in elem.attrs.items(): + match k: + case "title": + node.funcname = QName(v) + case "label": + if elem.attrs.get("shape", "") != "ellipse": + m = re_node_label.fullmatch(v) + if not m: + raise ValueError(f"unexpected label value {v!r}") + node.location = m.group("location") + node.usage_kind = typing.cast( + UsageKind, m.group("usage_kind") + ) + node.nstatic = int(m.group("nstatic")) + node.ndynamic = int(m.group("ndynamic")) + case "shape": + if v != "ellipse": + raise ValueError(f"unexpected shape value {v!r}") + skip = True + case _: + raise ValueError(f"unknown edge key {k!r}") + if not skip: + if node.funcname in graph: + raise ValueError(f"duplicate node {node.funcname}") + graph[node.funcname] = node + if ":" in str(node.funcname): + basename = node.funcname.base() + if basename not in qualified: + qualified[basename] = set() + qualified[basename].add(node.funcname) + case "edge": + caller: QName | None = None + callee: QName | None = None + for k, v in elem.attrs.items(): + match k: + case "sourcename": + caller = QName(v) + case "targetname": + callee = QName(v) + case "label": + pass + case _: + raise ValueError(f"unknown edge key {k!r}") + if caller is None or callee is None: + raise ValueError(f"incomplete edge: {elem.attrs!r}") + if caller not in graph: + raise ValueError(f"unknown caller: {caller}") + if callee == QName("__indirect_call"): + callees, missing_ok = app.indirect_callees(elem) + for callee in callees: + if callee not in graph[caller].calls: + graph[caller].calls[callee] = missing_ok + else: + graph[caller].calls[callee] = False + case _: + raise ValueError(f"unknown elem type {elem.typ!r}") + + for ci_fname in ci_fnames: + with open(ci_fname, "r", encoding="utf-8") as fh: + for elem in vcg.parse_vcg(fh): + handle_elem(elem) + + for node in app.extra_nodes(): + if node.funcname in graph: + raise ValueError(f"duplicate node {node.funcname}") + graph[node.funcname] = node + + missing: set[QName] = set() + dynamic: set[QName] = set() + included_funcs: set[QName] = set() + + dbg = False + + def resolve_funcname(funcname: QName) -> QName | None: + # Handle `ld --wrap` functions + if QName(f"__wrap_{str(funcname)}") in graph: + return QName(f"__wrap_{str(funcname)}") + if ( + str(funcname).startswith("__real_") + and QName(str(funcname)[len("__real_") :]) in graph + ): + funcname = QName(str(funcname)[len("__real_") :]) + + # Usual case + if funcname in graph: + return funcname + + # Handle `__weak` functions + if ":" not in str(funcname): + qnames = qualified.get(BaseName(str(funcname)), set()) + if len(qnames) == 1: + return sorted(qnames)[0] + + return None + + track_inclusion: bool = True + + def nstatic( + orig_funcname: QName, + chain: typing.Sequence[QName] = (), + missing_ok: bool = False, + ) -> int: + nonlocal dbg + nonlocal track_inclusion + funcname = resolve_funcname(orig_funcname) + if not funcname: + if chain and app.skip_call(chain, orig_funcname): + if dbg: + print(f"//dbg: {'- '*len(chain)}{orig_funcname}\tskip missing") + return 0 + if not missing_ok: + missing.add(orig_funcname) + if dbg: + print(f"//dbg: {'- '*len(chain)}{orig_funcname}\tmissing") + return 0 + if chain and app.skip_call(chain, funcname): + if dbg: + print(f"//dbg: {'- '*len(chain)}{orig_funcname}\tskip") + return 0 + + if len(chain) == cfg_max_call_depth: + raise ValueError(f"max call depth exceeded: {[*chain, funcname]}") + + node = graph[funcname] + if dbg: + print(f"//dbg: {'- '*len(chain)}{funcname}\t{node.nstatic}") + if node.usage_kind == "dynamic" or node.ndynamic > 0: + dynamic.add(funcname) + if track_inclusion: + included_funcs.add(funcname) + return node.nstatic + max( + [ + 0, + *[ + nstatic(call, [*chain, funcname], missing_ok) + for call, missing_ok in node.calls.items() + ], + ] + ) + + groups: dict[str, AnalyzeResultGroup] = {} + for grp_name, grp_filter in app_func_filters.items(): + rows: dict[QName, AnalyzeResultVal] = {} + for funcname in graph: + cnt, track_inclusion = grp_filter(funcname) + if cnt: + rows[funcname] = AnalyzeResultVal(nstatic=nstatic(funcname), cnt=cnt) + groups[grp_name] = AnalyzeResultGroup(rows=rows) + + return AnalyzeResult( + groups=groups, missing=missing, dynamic=dynamic, included_funcs=included_funcs + ) -- cgit v1.2.3-2-g168b From 1a0c67835cd74c6bf2113bb14a7f1b520508c536 Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Sun, 30 Mar 2025 20:41:26 -0600 Subject: measurestack: Cache QName.base() --- build-aux/measurestack/analyze.py | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py index 67edd5d..45ac876 100644 --- a/build-aux/measurestack/analyze.py +++ b/build-aux/measurestack/analyze.py @@ -56,9 +56,11 @@ class BaseName: class QName: _content: str + _base: BaseName | None def __init__(self, content: str) -> None: self._content = content + self._base = None def __str__(self) -> str: return self._content @@ -82,7 +84,9 @@ class QName: return hash(self._content) def base(self) -> BaseName: - return BaseName(self._content.rsplit(":", 1)[-1].split(".", 1)[0]) + if self._base is None: + self._base = BaseName(self._content.rsplit(":", 1)[-1].split(".", 1)[0]) + return self._base UsageKind: typing.TypeAlias = typing.Literal["static", "dynamic", "dynamic,bounded"] -- cgit v1.2.3-2-g168b From 2ced5e02eacfc6b9e67435fe3a24dcb6c3a29037 Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Mon, 31 Mar 2025 15:58:51 -0600 Subject: measurestack: Compile all regexes upfront --- build-aux/measurestack/analyze.py | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py index 45ac876..871ff2d 100644 --- a/build-aux/measurestack/analyze.py +++ b/build-aux/measurestack/analyze.py @@ -133,6 +133,16 @@ class Application(typing.Protocol): def skip_call(self, chain: typing.Sequence[QName], funcname: QName) -> bool: ... +re_node_label = re.compile( + r"(?P[^\n]+)\n" + + r"(?P[^\n]+:[0-9]+:[0-9]+)\n" + + r"(?P[0-9]+) bytes \((?Pstatic|dynamic|dynamic,bounded)\)\n" + + r"(?P[0-9]+) dynamic objects" + + r"(?:\n.*)*", + flags=re.MULTILINE, +) + + def analyze( *, ci_fnames: typing.Collection[str], @@ -140,15 +150,6 @@ def analyze( app: Application, cfg_max_call_depth: int, ) -> AnalyzeResult: - re_node_label = re.compile( - r"(?P[^\n]+)\n" - + r"(?P[^\n]+:[0-9]+:[0-9]+)\n" - + r"(?P[0-9]+) bytes \((?Pstatic|dynamic|dynamic,bounded)\)\n" - + r"(?P[0-9]+) dynamic objects" - + r"(?:\n.*)*", - flags=re.MULTILINE, - ) - graph: dict[QName, Node] = {} qualified: dict[BaseName, set[QName]] = {} -- cgit v1.2.3-2-g168b From 571ac844642796eb899dedccabcdc3c20926cac1 Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Mon, 31 Mar 2025 22:11:20 -0600 Subject: measurestack: Avoid using sorted() during analysis --- build-aux/measurestack/analyze.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py index 871ff2d..0fb20ef 100644 --- a/build-aux/measurestack/analyze.py +++ b/build-aux/measurestack/analyze.py @@ -250,7 +250,7 @@ def analyze( if ":" not in str(funcname): qnames = qualified.get(BaseName(str(funcname)), set()) if len(qnames) == 1: - return sorted(qnames)[0] + return next(name for name in qnames) return None -- cgit v1.2.3-2-g168b From 352da947a02ff7658deb7729efa8b2cf7ce7a5cc Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Tue, 1 Apr 2025 04:41:32 -0600 Subject: measurestack: Intern QNames and BaseNames --- build-aux/measurestack/analyze.py | 37 ++++++++++++++++++++++++++++++------- 1 file changed, 30 insertions(+), 7 deletions(-) (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py index 0fb20ef..a5ac6e5 100644 --- a/build-aux/measurestack/analyze.py +++ b/build-aux/measurestack/analyze.py @@ -4,6 +4,7 @@ # SPDX-License-Identifier: AGPL-3.0-or-later import re +import sys import typing from . import vcg @@ -22,12 +23,23 @@ __all__ = [ class BaseName: - _content: str + # class ########################################################## + + _interned: dict[str, "BaseName"] = {} - def __init__(self, content: str) -> None: + def __new__(cls, content: str) -> "BaseName": if ":" in content: raise ValueError(f"invalid non-qualified name: {content!r}") - self._content = content + content = sys.intern(content) + if content not in cls._interned: + self = super().__new__(cls) + self._content = content + cls._interned[content] = self + return cls._interned[content] + + # instance ####################################################### + + _content: str def __str__(self) -> str: return self._content @@ -55,13 +67,24 @@ class BaseName: class QName: + # class ########################################################## + + _interned: dict[str, "QName"] = {} + + def __new__(cls, content: str) -> "QName": + content = sys.intern(content) + if content not in cls._interned: + self = super().__new__(cls) + self._content = content + self._base = None + cls._interned[content] = self + return cls._interned[content] + + # instance ####################################################### + _content: str _base: BaseName | None - def __init__(self, content: str) -> None: - self._content = content - self._base = None - def __str__(self) -> str: return self._content -- cgit v1.2.3-2-g168b From ab02d73a5bf6369d567d408d0544748dfd0303ea Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Tue, 1 Apr 2025 04:54:14 -0600 Subject: measurestack: Try to tidy analyze.py a bit --- build-aux/measurestack/analyze.py | 81 ++++++++++++++++++++++++--------------- 1 file changed, 51 insertions(+), 30 deletions(-) (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py index a5ac6e5..d4ca721 100644 --- a/build-aux/measurestack/analyze.py +++ b/build-aux/measurestack/analyze.py @@ -21,6 +21,8 @@ __all__ = [ "analyze", ] +# types ######################################################################## + class BaseName: # class ########################################################## @@ -156,6 +158,8 @@ class Application(typing.Protocol): def skip_call(self, chain: typing.Sequence[QName], funcname: QName) -> bool: ... +# code ######################################################################### + re_node_label = re.compile( r"(?P[^\n]+)\n" + r"(?P[^\n]+:[0-9]+:[0-9]+)\n" @@ -166,13 +170,37 @@ re_node_label = re.compile( ) -def analyze( - *, +class _Graph: + graph: dict[QName, Node] + qualified: dict[BaseName, set[QName]] + + def resolve_funcname(self, funcname: QName) -> QName | None: + # Handle `ld --wrap` functions + if QName(f"__wrap_{str(funcname)}") in self.graph: + return QName(f"__wrap_{str(funcname)}") + if ( + str(funcname).startswith("__real_") + and QName(str(funcname)[len("__real_") :]) in self.graph + ): + funcname = QName(str(funcname)[len("__real_") :]) + + # Usual case + if funcname in self.graph: + return funcname + + # Handle `__weak` functions + if ":" not in str(funcname): + qnames = self.qualified.get(BaseName(str(funcname)), set()) + if len(qnames) == 1: + return next(name for name in qnames) + + return None + + +def _make_graph( ci_fnames: typing.Collection[str], - app_func_filters: dict[str, typing.Callable[[QName], tuple[int, bool]]], app: Application, - cfg_max_call_depth: int, -) -> AnalyzeResult: +) -> _Graph: graph: dict[QName, Node] = {} qualified: dict[BaseName, set[QName]] = {} @@ -249,34 +277,27 @@ def analyze( raise ValueError(f"duplicate node {node.funcname}") graph[node.funcname] = node + ret = _Graph() + ret.graph = graph + ret.qualified = qualified + return ret + + +def analyze( + *, + ci_fnames: typing.Collection[str], + app_func_filters: dict[str, typing.Callable[[QName], tuple[int, bool]]], + app: Application, + cfg_max_call_depth: int, +) -> AnalyzeResult: + graphdata = _make_graph(ci_fnames, app) + missing: set[QName] = set() dynamic: set[QName] = set() included_funcs: set[QName] = set() dbg = False - def resolve_funcname(funcname: QName) -> QName | None: - # Handle `ld --wrap` functions - if QName(f"__wrap_{str(funcname)}") in graph: - return QName(f"__wrap_{str(funcname)}") - if ( - str(funcname).startswith("__real_") - and QName(str(funcname)[len("__real_") :]) in graph - ): - funcname = QName(str(funcname)[len("__real_") :]) - - # Usual case - if funcname in graph: - return funcname - - # Handle `__weak` functions - if ":" not in str(funcname): - qnames = qualified.get(BaseName(str(funcname)), set()) - if len(qnames) == 1: - return next(name for name in qnames) - - return None - track_inclusion: bool = True def nstatic( @@ -286,7 +307,7 @@ def analyze( ) -> int: nonlocal dbg nonlocal track_inclusion - funcname = resolve_funcname(orig_funcname) + funcname = graphdata.resolve_funcname(orig_funcname) if not funcname: if chain and app.skip_call(chain, orig_funcname): if dbg: @@ -305,7 +326,7 @@ def analyze( if len(chain) == cfg_max_call_depth: raise ValueError(f"max call depth exceeded: {[*chain, funcname]}") - node = graph[funcname] + node = graphdata.graph[funcname] if dbg: print(f"//dbg: {'- '*len(chain)}{funcname}\t{node.nstatic}") if node.usage_kind == "dynamic" or node.ndynamic > 0: @@ -325,7 +346,7 @@ def analyze( groups: dict[str, AnalyzeResultGroup] = {} for grp_name, grp_filter in app_func_filters.items(): rows: dict[QName, AnalyzeResultVal] = {} - for funcname in graph: + for funcname in graphdata.graph: cnt, track_inclusion = grp_filter(funcname) if cnt: rows[funcname] = AnalyzeResultVal(nstatic=nstatic(funcname), cnt=cnt) -- cgit v1.2.3-2-g168b From c004342a27fb135b5d3fcd6817be4a2ae588668b Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Tue, 1 Apr 2025 05:04:06 -0600 Subject: measurestack: Try to speed up resolve_funcname() --- build-aux/measurestack/analyze.py | 33 +++++++++++++++++++-------------- 1 file changed, 19 insertions(+), 14 deletions(-) (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py index d4ca721..b7b8b08 100644 --- a/build-aux/measurestack/analyze.py +++ b/build-aux/measurestack/analyze.py @@ -172,27 +172,29 @@ re_node_label = re.compile( class _Graph: graph: dict[QName, Node] - qualified: dict[BaseName, set[QName]] + qualified: dict[BaseName, QName] def resolve_funcname(self, funcname: QName) -> QName | None: + s = str(funcname) + is_qualified = ":" in s + # Handle `ld --wrap` functions - if QName(f"__wrap_{str(funcname)}") in self.graph: - return QName(f"__wrap_{str(funcname)}") - if ( - str(funcname).startswith("__real_") - and QName(str(funcname)[len("__real_") :]) in self.graph - ): - funcname = QName(str(funcname)[len("__real_") :]) + if not is_qualified: + with_wrap = QName(f"__wrap_{s}") + if with_wrap in self.graph: + return with_wrap + if s.startswith("__real_"): + without_real = QName(s[len("__real_") :]) + if without_real in self.graph: + funcname = without_real # Usual case if funcname in self.graph: return funcname - # Handle `__weak` functions - if ":" not in str(funcname): - qnames = self.qualified.get(BaseName(str(funcname)), set()) - if len(qnames) == 1: - return next(name for name in qnames) + # Handle `__weak`/`[[gnu::weak]]` functions + if not is_qualified: + return self.qualified.get(BaseName(s)) return None @@ -279,7 +281,10 @@ def _make_graph( ret = _Graph() ret.graph = graph - ret.qualified = qualified + ret.qualified = {} + for bname, qnames in qualified.items(): + if len(qnames) == 1: + ret.qualified[bname] = next(name for name in qnames) return ret -- cgit v1.2.3-2-g168b From 8eec957275cb3566b8371774a9a1e3e09f43fcde Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Tue, 1 Apr 2025 05:05:55 -0600 Subject: measurestack: Cache resolve_funcname() --- build-aux/measurestack/analyze.py | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py index b7b8b08..5b29841 100644 --- a/build-aux/measurestack/analyze.py +++ b/build-aux/measurestack/analyze.py @@ -174,7 +174,12 @@ class _Graph: graph: dict[QName, Node] qualified: dict[BaseName, QName] - def resolve_funcname(self, funcname: QName) -> QName | None: + _resolve_cache: dict[QName, QName | None] + + def __init__(self) -> None: + self._resolve_cache = {} + + def _resolve_funcname(self, funcname: QName) -> QName | None: s = str(funcname) is_qualified = ":" in s @@ -198,6 +203,11 @@ class _Graph: return None + def resolve_funcname(self, funcname: QName) -> QName | None: + if funcname not in self._resolve_cache: + self._resolve_cache[funcname] = self._resolve_funcname(funcname) + return self._resolve_cache[funcname] + def _make_graph( ci_fnames: typing.Collection[str], -- cgit v1.2.3-2-g168b From 78b16edb747834f1a9a41931a1adb7d7fe0fcbb0 Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Tue, 1 Apr 2025 06:18:00 -0600 Subject: measurestack: Bypassing hash() has measureable speedup --- build-aux/measurestack/analyze.py | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py index 5b29841..8100813 100644 --- a/build-aux/measurestack/analyze.py +++ b/build-aux/measurestack/analyze.py @@ -62,7 +62,7 @@ class BaseName: return self._content < other._content def __hash__(self) -> int: - return hash(self._content) + return self._content.__hash__() def as_qname(self) -> "QName": return QName(self._content) @@ -106,7 +106,7 @@ class QName: return self._content < other._content def __hash__(self) -> int: - return hash(self._content) + return self._content.__hash__() def base(self) -> BaseName: if self._base is None: -- cgit v1.2.3-2-g168b From 8e3d2a904fe046910ee831e6fd9d2316aafc260a Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Sun, 30 Mar 2025 03:09:19 -0600 Subject: measurestack: Rework the skip-call API to speed things up --- build-aux/measurestack/analyze.py | 123 ++++++++++++++++++++++++++++---------- 1 file changed, 90 insertions(+), 33 deletions(-) (limited to 'build-aux/measurestack/analyze.py') diff --git a/build-aux/measurestack/analyze.py b/build-aux/measurestack/analyze.py index 8100813..a93874f 100644 --- a/build-aux/measurestack/analyze.py +++ b/build-aux/measurestack/analyze.py @@ -150,12 +150,38 @@ class AnalyzeResult(typing.NamedTuple): included_funcs: set[QName] +class SkipModel(typing.NamedTuple): + """Running the skipmodel calls `.fn(chain, ...)` with the chain + consisting of the last `.nchain` items (if .nchain is an int), or + the chain starting with the *last* occurance of `.nchain` (if + .nchain is a collection). If the chain is not that long or does + not contain a member of the collection, then .fn is not called and + the call is *not* skipped. + + """ + + nchain: int | typing.Collection[BaseName] + fn: typing.Callable[[typing.Sequence[QName], QName], bool] + + def __call__(self, chain: typing.Sequence[QName], call: QName) -> tuple[bool, int]: + if isinstance(self.nchain, int): + if len(chain) >= self.nchain: + _chain = chain[-self.nchain :] + return self.fn(_chain, call), len(_chain) + else: + for i in reversed(range(len(chain))): + if chain[i].base() in self.nchain: + _chain = chain[i - 1 :] + return self.fn(_chain, call), len(_chain) + return False, 0 + + class Application(typing.Protocol): def extra_nodes(self) -> typing.Collection[Node]: ... def indirect_callees( self, elem: vcg.VCGElem ) -> tuple[typing.Collection[QName], bool]: ... - def skip_call(self, chain: typing.Sequence[QName], funcname: QName) -> bool: ... + def skipmodels(self) -> dict[BaseName, SkipModel]: ... # code ######################################################################### @@ -315,31 +341,20 @@ def analyze( track_inclusion: bool = True - def nstatic( - orig_funcname: QName, - chain: typing.Sequence[QName] = (), - missing_ok: bool = False, - ) -> int: + skipmodels = app.skipmodels() + for name, model in skipmodels.items(): + if isinstance(model.nchain, int): + assert model.nchain > 1 + else: + assert len(model.nchain) > 0 + + _nstatic_cache: dict[QName, int] = {} + + def _nstatic(chain: list[QName], funcname: QName) -> tuple[int, int]: nonlocal dbg nonlocal track_inclusion - funcname = graphdata.resolve_funcname(orig_funcname) - if not funcname: - if chain and app.skip_call(chain, orig_funcname): - if dbg: - print(f"//dbg: {'- '*len(chain)}{orig_funcname}\tskip missing") - return 0 - if not missing_ok: - missing.add(orig_funcname) - if dbg: - print(f"//dbg: {'- '*len(chain)}{orig_funcname}\tmissing") - return 0 - if chain and app.skip_call(chain, funcname): - if dbg: - print(f"//dbg: {'- '*len(chain)}{orig_funcname}\tskip") - return 0 - - if len(chain) == cfg_max_call_depth: - raise ValueError(f"max call depth exceeded: {[*chain, funcname]}") + + assert funcname in graphdata.graph node = graphdata.graph[funcname] if dbg: @@ -348,15 +363,57 @@ def analyze( dynamic.add(funcname) if track_inclusion: included_funcs.add(funcname) - return node.nstatic + max( - [ - 0, - *[ - nstatic(call, [*chain, funcname], missing_ok) - for call, missing_ok in node.calls.items() - ], - ] - ) + + max_call_nstatic = 0 + max_call_nchain = 0 + + if node.calls: + skipmodel = skipmodels.get(funcname.base()) + chain.append(funcname) + if len(chain) == cfg_max_call_depth: + raise ValueError(f"max call depth exceeded: {chain}") + for call_orig_qname, call_missing_ok in node.calls.items(): + skip_nchain = 0 + # 1. Resolve + call_qname = graphdata.resolve_funcname(call_orig_qname) + if not call_qname: + if skipmodel: + skip, _ = skipmodel(chain, call_orig_qname) + if skip: + if dbg: + print( + f"//dbg: {'- '*len(chain)}{call_orig_qname}\tskip missing" + ) + continue + if not call_missing_ok: + missing.add(call_orig_qname) + if dbg: + print(f"//dbg: {'- '*len(chain)}{call_orig_qname}\tmissing") + continue + + # 2. Skip + if skipmodel: + skip, skip_nchain = skipmodel(chain, call_qname) + max_call_nchain = max(max_call_nchain, skip_nchain) + if skip: + if dbg: + print(f"//dbg: {'- '*len(chain)}{call_qname}\tskip") + continue + + # 3. Call + if skip_nchain == 0 and call_qname in _nstatic_cache: + max_call_nstatic = max(max_call_nstatic, _nstatic_cache[call_qname]) + else: + call_nstatic, call_nchain = _nstatic(chain, call_qname) + max_call_nstatic = max(max_call_nstatic, call_nstatic) + max_call_nchain = max(max_call_nchain, call_nchain) + if skip_nchain == 0 and call_nchain == 0: + _nstatic_cache[call_qname] = call_nstatic + chain.pop() + return node.nstatic + max_call_nstatic, max(0, max_call_nchain - 1) + + def nstatic(funcname: QName) -> int: + return _nstatic([], funcname)[0] groups: dict[str, AnalyzeResultGroup] = {} for grp_name, grp_filter in app_func_filters.items(): -- cgit v1.2.3-2-g168b