Phoenix: Speed up acyclic graph conversion. (angr#5548)

* Phoenix: Speed up acyclic graph conversion. Also switches to deterministic post-ordering when possible for improved speed. * Add a missing node order update. * Lint code. * Properly handle multi-headed acyclic graphs. * Fix another place where node_order is not updated when new nodes are created. * Fix one more missed place. * Add a missed list(reversed(...)). * Adjust the tr.build_spec_list test case.
rodriguezzfran · BrunoGugli · Jun 10, 2025 · Jun 10, 2025 · Jun 11, 2025 · Jun 12, 2025
commit d5fd0b5475eae99b0e327f38c8d1924c771cd07e
diff --git a/angr/analyses/decompiler/structuring/phoenix.py b/angr/analyses/decompiler/structuring/phoenix.py
@@ -126,6 +126,12 @@ def __init__(
         self._improve_algorithm = improve_algorithm
         self._edge_virtualization_hints = []
 
+        # node_order keeps a dictionary of nodes and their order in a quasi-topological sort of the region full graph
+        # (graph_with_successors). _generate_node_order() initializes this dictionary. we then update this dictionary
+        # when new nodes are created. we do not populate this dictionary when working on acyclic graphs because it's
+        # not used for acyclic graphs.
+        self._node_order: dict[Any, int] | None = None
+
         self._use_multistmtexprs = use_multistmtexprs
         self._multistmtexpr_stmt_threshold = multistmtexpr_stmt_threshold
         self._analyze()
@@ -221,8 +227,11 @@ def _analyze(self):
 
     def _analyze_cyclic(self) -> bool:
         any_matches = False
-        acyclic_graph = to_acyclic_graph(self._region.graph, loop_heads=[self._region.head])
-        for node in list(reversed(GraphUtils.quasi_topological_sort_nodes(acyclic_graph))):
+
+        if self._node_order is None:
+            self._generate_node_order()
+        acyclic_graph = to_acyclic_graph(self._region.graph, node_order=self._node_order)
+        for node in list(GraphUtils.dfs_postorder_nodes_deterministic(acyclic_graph, self._region.head)):
             if node not in self._region.graph:
                 continue
             matched = self._match_cyclic_schemas(
@@ -499,6 +508,10 @@ def _match_cyclic_while_with_single_successor(
         self.replace_nodes(full_graph, node, loop_node, self_loop=False)
         full_graph.add_edge(loop_node, successor_node)
 
+        if self._node_order is not None:
+            self._node_order[loop_node] = self._node_order[node]
+            self._node_order[successor_node] = self._node_order[loop_node]
+
         return True, loop_node, successor_node
 
     def _cyclic_while_with_single_successor_must_return(self, successor_node: SequenceNode) -> bool:
@@ -1035,7 +1048,7 @@ def _match_acyclic_schemas(self, graph: networkx.DiGraph, full_graph: networkx.D
 
             self._assert_graph_ok(acyclic_graph, "Removed wrong edges")
 
-        for node in list(reversed(GraphUtils.quasi_topological_sort_nodes(acyclic_graph))):
+        for node in list(GraphUtils.dfs_postorder_nodes_deterministic(acyclic_graph, head)):
             if node not in graph:
                 continue
             if graph.has_edge(node, head):
@@ -1141,6 +1154,8 @@ def _match_acyclic_switch_cases_incomplete_switch_head(self, node, graph, full_g
             node_default = Block(SWITCH_MISSING_DEFAULT_NODE_ADDR, 0, statements=[jmp_to_default_node])
             graph.add_edge(node, node_default)
             full_graph.add_edge(node, node_default)
+            if self._node_order is not None:
+                self._node_order[node_default] = self._node_order[node]
         r = self._make_switch_cases_core(
             node,
             self.cond_proc.claripy_ast_from_ail_condition(last_stmt.switch_variable),
@@ -1246,6 +1261,8 @@ def _match_acyclic_switch_cases_address_loaded_from_memory(self, node, graph, fu
         # un-structure IncompleteSwitchCaseNode
         if isinstance(node_a, SequenceNode) and node_a.nodes and isinstance(node_a.nodes[0], IncompleteSwitchCaseNode):
             _, new_seq_node = self._unpack_sequencenode_head(graph, node_a)
+            if new_seq_node is not None and self._node_order is not None:
+                self._node_order[new_seq_node] = self._node_order[node_a]
             self._unpack_sequencenode_head(full_graph, node_a, new_seq=new_seq_node)
             # update node_a
             node_a = next(iter(nn for nn in graph.nodes if nn.addr == target))
@@ -1256,6 +1273,8 @@ def _match_acyclic_switch_cases_address_loaded_from_memory(self, node, graph, fu
             self._unpack_incompleteswitchcasenode(full_graph, node_a)  # this shall not fail
             # update node_a
             node_a = next(iter(nn for nn in graph.nodes if nn.addr == target))
+            if self._node_order is not None:
+                self._generate_node_order()
 
         better_node_a = node_a
         if isinstance(node_a, SequenceNode) and is_empty_or_label_only_node(node_a.nodes[0]) and len(node_a.nodes) == 2:
@@ -1600,6 +1619,8 @@ def _match_acyclic_incomplete_switch_cases(
                 self.replace_nodes(full_graph, node, new_node)
                 if out_nodes:
                     full_graph.add_edge(new_node, out_nodes[0])
+                if self._node_order:
+                    self._node_order[new_node] = self._node_order[node]
                 return True
         return False
 
@@ -1781,6 +1802,8 @@ def _make_switch_cases_core(
 
         graph.add_edge(head, scnode)
         full_graph.add_edge(head, scnode)
+        if self._node_order is not None:
+            self._node_order[scnode] = self._node_order[head]
 
         if out_edges:
             # for all out edges going to head, we ensure there is a goto at the end of each corresponding case node
@@ -2511,7 +2534,7 @@ def _last_resort_refinement(self, head, graph: networkx.DiGraph, full_graph: net
         if networkx.is_directed_acyclic_graph(full_graph):
             acyclic_graph = full_graph
         else:
-            acyclic_graph = to_acyclic_graph(full_graph, loop_heads=[head])
+            acyclic_graph = to_acyclic_graph(full_graph, node_order=self._node_order)
         for src, dst in acyclic_graph.edges:
             if src is dst:
                 continue
@@ -2527,7 +2550,20 @@ def _last_resort_refinement(self, head, graph: networkx.DiGraph, full_graph: net
                 if (src.addr, dst.addr) not in self.whitelist_edges:
                     other_edges.append((src, dst))
 
-        ordered_nodes = GraphUtils.quasi_topological_sort_nodes(acyclic_graph, loop_heads=[head])
+        # acyclic graph may contain more than one entry node, so we may add a temporary head node to ensure all nodes
+        # are accounted for in node_seq
+        graph_entries = [nn for nn in acyclic_graph if acyclic_graph.in_degree[nn] == 0]
+        postorder_head = head
+        if len(graph_entries) > 1:
+            postorder_head = Block(0, 0)
+            for nn in graph_entries:
+                acyclic_graph.add_edge(postorder_head, nn)
+        ordered_nodes = list(
+            reversed(list(GraphUtils.dfs_postorder_nodes_deterministic(acyclic_graph, postorder_head)))
+        )
+        if len(graph_entries) > 1:
+            ordered_nodes.remove(postorder_head)
+            acyclic_graph.remove_node(postorder_head)
         node_seq = {nn: (len(ordered_nodes) - idx) for (idx, nn) in enumerate(ordered_nodes)}  # post-order
 
         if all_edges_wo_dominance:
@@ -2607,6 +2643,8 @@ def _virtualize_edge(self, graph, full_graph, src, dst):
             self.virtualized_edges.add((src, dst))
         if new_src is not None:
             self.replace_nodes(graph, src, new_src)
+            if self._node_order is not None:
+                self._node_order[new_src] = self._node_order[src]
         if full_graph is not None:
             self.virtualized_edges.add((src, dst))
             full_graph.remove_edge(src, dst)
@@ -2916,10 +2954,29 @@ def _sort_edge(edge_):
             src, dst = edge_
             dst_in_degree = graph.in_degree[dst]
             src_out_degree = graph.out_degree[src]
-            return -node_seq.get(dst), dst_in_degree, src_out_degree, -src.addr, -dst.addr  # type: ignore
+            return -node_seq[dst], dst_in_degree, src_out_degree, -src.addr, -dst.addr  # type: ignore
 
         return sorted(edges, key=_sort_edge, reverse=True)
 
+    def _generate_node_order(self):
+        the_graph = (
+            self._region.graph_with_successors if self._region.graph_with_successors is not None else self._region.graph
+        )
+        the_head = self._region.head
+        ordered_nodes = GraphUtils.quasi_topological_sort_nodes(
+            the_graph,
+            loop_heads=[the_head],
+        )
+        self._node_order = {n: i for i, n in enumerate(ordered_nodes)}
+
+    def replace_nodes(self, graph, old_node_0, new_node, old_node_1=None, self_loop=True):
+        super().replace_nodes(graph, old_node_0, new_node, old_node_1=old_node_1, self_loop=self_loop)
+        if self._node_order is not None and graph is self._region.graph_with_successors:
+            if old_node_1 is not None:
+                self._node_order[new_node] = min(self._node_order[old_node_0], self._node_order[old_node_1])
+            else:
+                self._node_order[new_node] = self._node_order[old_node_0]
+
     @staticmethod
     def _replace_node_in_edge_list(edge_list: list[tuple], old_node, new_node) -> None:
         for idx in range(len(edge_list)):  # pylint:disable=consider-using-enumerate

diff --git a/angr/analyses/decompiler/structuring/structurer_base.py b/angr/analyses/decompiler/structuring/structurer_base.py
@@ -6,9 +6,9 @@
 
 import networkx
 
-import angr.ailment as ailment
 import claripy
 
+from angr import ailment
 from angr.analyses import Analysis
 from angr.analyses.decompiler.condition_processor import ConditionProcessor
 from angr.analyses.decompiler.sequence_walker import SequenceWalker
@@ -971,8 +971,7 @@ def _update_new_sequences(self, removed_sequences: set[SequenceNode], replaced_s
                     new_sequences.append(new_seq_)
         self._new_sequences = new_sequences
 
-    @staticmethod
-    def replace_nodes(graph, old_node_0, new_node, old_node_1=None, self_loop=True):
+    def replace_nodes(self, graph, old_node_0, new_node, old_node_1=None, self_loop=True):  # pylint:disable=no-self-use
         in_edges = list(graph.in_edges(old_node_0, data=True))
         out_edges = list(graph.out_edges(old_node_0, data=True))
         if old_node_1 is not None:

diff --git a/angr/utils/graph.py b/angr/utils/graph.py
@@ -673,6 +673,21 @@ def find_widening_points(function_addr, function_endpoints, graph):  # pylint: d
 
         return list(widening_addrs)
 
+    @staticmethod
+    def dfs_postorder_nodes_deterministic(graph: networkx.DiGraph, source):
+        visited = set()
+        stack = [source]
+        while stack:
+            node = stack[-1]
+            if node not in visited:
+                visited.add(node)
+                for succ in sorted(graph.successors(node), key=GraphUtils._sort_node):
+                    if succ not in visited:
+                        stack.append(succ)
+            else:
+                yield node
+                stack.pop()
+
     @staticmethod
     def reverse_post_order_sort_nodes(graph, nodes=None):
         """

diff --git a/tests/analyses/decompiler/test_decompiler.py b/tests/analyses/decompiler/test_decompiler.py
@@ -2275,11 +2275,7 @@ def test_decompiling_tr_build_spec_list(self, decompiler_options=None):
         )
         self._print_decompilation_result(d)
 
-        assert d.codegen.text.count("goto ") == 3
-        # `LABEL_400d08` is the label `try_bracketed_repeat` found in the source, which is jumped to twice
-        assert d.codegen.text.count("goto LABEL_400d08;") == 2
-        # this goto may go away in the future if the loops are structured correctly
-        assert d.codegen.text.count("goto LABEL_400d2a;") == 1
+        assert d.codegen.text.count("goto") == 0
 
     @structuring_algo("sailr")
     def test_decompiling_sha384sum_digest_bsd_split_3(self, decompiler_options=None):
@@ -3531,7 +3527,7 @@ def test_decompiling_tr_O2_parse_str(self, decompiler_options=None):
 
         f = proj.kb.functions["parse_str"]
         proj.analyses.CompleteCallingConventions(cfg=cfg, recover_variables=True, analyze_callsites=True)
-        d = proj.analyses[Decompiler](f, cfg=cfg.model, options=decompiler_options)
+        d = proj.analyses[Decompiler].prep(fail_fast=True)(f, cfg=cfg.model, options=decompiler_options)
         self._print_decompilation_result(d)
 
         line_count = d.codegen.text.count("\n")
@@ -3584,6 +3580,8 @@ def test_dd_iread_ret_dup_region(self, decompiler_options=None):
         proj.analyses.CompleteCallingConventions(cfg=cfg, recover_variables=True)
         f = proj.kb.functions["iread"]
         d = proj.analyses[Decompiler].prep(fail_fast=True)(f, cfg=cfg.model, options=decompiler_options)
+        assert d.codegen is not None and d.codegen.text is not None
+        self._print_decompilation_result(d)
         text = d.codegen.text
 
         assert "{\n}" not in text