From d74b6f53e0969efc586d52776fa3b6d40b92a650 Mon Sep 17 00:00:00 2001 From: idatui Date: Sun, 9 Aug 2026 14:17:13 +0200 Subject: Graph: never hand triskel a block its root cannot reach "EMPTY BL" in the status bar is triskel's own bracket-list assertion from its SESE pass, and it turned out to be the mild version of the problem. Triskel's graph root is whichever node was created FIRST, and every analysis walks out from it. Anything unreachable from that node is undefined behaviour. We were: - creating nodes in id order, so the root was the lowest-numbered block rather than the entry, and - splitting only WEAKLY connected components, which says nothing about reachability. A 7-block CFG whose entry has no successors -- IDA hands those out for thunks and for dead code it could not resolve -- SEGFAULTS the interpreter. That is unsurvivable: it takes the session down and there is no exception to fall back from. Now the entry is created first, orphan blocks are attached to it with phantom edges that steer placement but are never drawn (one edge usually adopts a whole orphan subgraph, attached at a node no other orphan reaches), and reachability is asserted in python BEFORE crossing into C++. This replaces the component splitting entirely: one layout instead of N stacked side by side, and triskel gets to place the orphans. The reproducer is now a test (t_unreachable_entry). Remaining fallbacks on the ls corpus are 8/1200 layouts, all the upstream box-overlap defect, all but one on 300-500 block functions. --- tests/test_graph.py | 30 +++++++++++++++++++++++++++++- 1 file changed, 29 insertions(+), 1 deletion(-) (limited to 'tests/test_graph.py') diff --git a/tests/test_graph.py b/tests/test_graph.py index 96d4f85..a75ff68 100644 --- a/tests/test_graph.py +++ b/tests/test_graph.py @@ -161,6 +161,33 @@ def t_unreachable() -> None: check(len(lay.nodes) == 3, "unreachable: every block is placed") +def t_unreachable_entry() -> None: + """Blocks the entry cannot reach, including an entry with no successors. + + IDA hands these out routinely -- dead code, an unresolved jump table -- and + triskel's root is whichever node was created first, with every analysis + walking out from there. Anything it cannot reach is undefined behaviour: + this exact 7-block shape SEGFAULTED the interpreter, and lesser versions + threw "EMPTY BL" from its SESE bracket lists. A crash cannot be fallen back + from, so the engine must never be handed one. + """ + # entry 0 is a sink; 2 and 3 jump INTO it; 1 and 6 self-loop. + lay = layout(mk({0: [], 1: [(5, "switch"), (1, "fall"), (4, "switch")], + 2: [(5, "jump"), (0, "uncond")], 3: [(0, "switch")], + 4: [], 5: [(4, "jump")], + 6: [(2, "jump"), (6, "switch"), (3, "jump")]}), entry=0) + invariants(lay, "unreachable_entry") + check(len(lay.nodes) == 7, "unreachable_entry: every block is placed") + check(lay.stats.get("engine_error") is None, + f"unreachable_entry: no fallback ({lay.stats.get('engine_error')})") + + # An entry that reaches nothing at all, with everything hanging off nodes + # it cannot see, is the degenerate version of the same thing. + lay = layout(mk({0: [], 1: [(2, "jump")], 2: [(1, "jump")]}), entry=0) + invariants(lay, "orphan_pair") + check(len(lay.nodes) == 3, "orphan_pair: every block is placed") + + def t_long_edge() -> None: """An edge spanning many layers gets dummies, so it reserves real space.""" chain = {i: [(i + 1, "uncond")] for i in range(6)} @@ -280,7 +307,8 @@ def main() -> int: ENGINE = engine print(f"\nengine: {engine}") for fn in (t_linear, t_diamond, t_selfloop, t_loop, t_switch, - t_unreachable, t_long_edge, t_empty, t_row_query, t_hit_test): + t_unreachable, t_unreachable_entry, t_long_edge, t_empty, + t_row_query, t_hit_test): print(f" {fn.__name__}") fn() for path in sys.argv[1:]: -- cgit v1.3.1-sl0p