subgraph_between_nodes() copied the whole graph and then ran a fresh
networkx.has_path() search for every (candidate successor, frontier node)
pair, so its worst case was O(candidate_edges * frontier_nodes * (V + E)).
Negative queries are the expensive ones: a successor that cannot reach any
frontier node forces a full traversal of everything reachable from it, once
per frontier node.
RegionIdentifier._find_initial_loop_nodes() calls this for every loop it
recovers, so a loop head whose successors lead into a large region that only
returns to the head (which the function's own "remove all incoming edges of
the source" step makes unable to reach any latch) makes loop recovery
quadratic. On a 1.1k-node AArch64 CFG built to have that shape, decompilation
spends 40.5s of 52.5s inside 608,847 has_path() calls.
Replace the repeated searches with a single reverse multi-source BFS from the
frontier that stops at the source; membership in the resulting set answers
every reachability question the forward walk asks. Stopping the reverse walk
at the source is exactly equivalent to deleting all incoming edges of the
source, so the graph copy is no longer needed either. Also peel dead leaves
with a degree worklist instead of rescanning all nodes after each removal.
Results are unchanged, including node/edge insertion order and edge
attributes: 6,000 randomized fixed-seed comparisons (3,000 graphs x both
include_frontier modes) against the previous implementation are identical, as
is the decompiler output on the CFG above (52.5s -> 12.5s end to end, 0
has_path() calls).
One behaviour change is deliberate: frontier is now turned into a set before
the "source not in graph or any(node not in graph for node in frontier)"
check rather than after it. In the old order an iterator argument was consumed
by that check, so the subsequent set(frontier) was empty and the function
silently sliced with no frontier at all. Every in-tree caller passes a list or
a set, so no in-tree behaviour changes.
* Enable ruff isort rule
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
- Scan for long repeating byte patterns and mark them as no-decode.
- Reuse the previous segment's segment sort when finding aligned
addresses.
- Mark nodecode when an address cannot be lifted as ARM or THUMB code.
* Add experimental Rust SegmnentList implementation
* Add rust to RTD environment
* Fix cargo check
* Add update method to avoid ._list
* Change rust version to latest
* Fix some inconsistencies with original implementation
* Fix iterator
* Fix lint issues
* Disable setuptools_rust check in setup.py
* Fix import
* Use asdf to install rust
* Specify latest version
* Also set the rust version globally
* Revert "Disable setuptools_rust check in setup.py"
This reverts commit 0fd2a4b61c.
* Add a note about rust in the docs
* Refactor SegmentList tests into own file
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix lint
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
