diff options
| -rw-r--r-- | miasm2/core/graph.py | 45 | ||||
| -rw-r--r-- | test/core/graph.py | 53 |
2 files changed, 94 insertions, 4 deletions
diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index 47be1864..2565f3d1 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -145,7 +145,7 @@ shape = "box" @staticmethod def _reachable_nodes(head, next_cb): - """Generic algorithm to compute every nodes reachable from/to node + """Generic algorithm to compute all nodes reachable from/to node @head""" todo = set([head]) @@ -160,11 +160,13 @@ shape = "box" todo.add(next_node) def reachable_sons(self, head): - """Compute every nodes reachable from node @head""" + """Compute all nodes reachable from node @head. Each son is an + immediate successor of an arbitrary, already yielded son of @head""" return self._reachable_nodes(head, self.successors_iter) def reachable_parents(self, leaf): - """Compute every parents of node @leaf""" + """Compute all parents of node @leaf. Each parent is an immediate + predecessor of an arbitrary, already yielded parent of @leaf""" return self._reachable_nodes(leaf, self.predecessors_iter) @staticmethod @@ -300,3 +302,40 @@ shape = "box" return self._walk_generic_dominator(node, postdominators, self.successors_iter) + + def compute_immediate_dominators(self, head): + """Compute the immediate dominators of the graph""" + dominators = self.compute_dominators(head) + idoms = {} + + for node in dominators: + for predecessor in self.walk_dominators(node, dominators): + if predecessor in dominators[node] and node != predecessor: + idoms[node] = predecessor + break + return idoms + + def compute_dominance_frontier(self, head): + """ + Compute the dominance frontier of the graph + + Source: Cooper, Keith D., Timothy J. Harvey, and Ken Kennedy. + "A simple, fast dominance algorithm." + Software Practice & Experience 4 (2001), p. 9 + """ + idoms = self.compute_immediate_dominators(head) + frontier = {} + + for node in idoms: + if self._nodes_pred[node] >= 2: + for predecessor in self.predecessors_iter(node): + runner = predecessor + if runner not in idoms: + continue + while runner != idoms[node]: + if runner not in frontier: + frontier[runner] = set() + + frontier[runner].add(node) + runner = idoms[runner] + return frontier diff --git a/test/core/graph.py b/test/core/graph.py index eb320542..5100cf8d 100644 --- a/test/core/graph.py +++ b/test/core/graph.py @@ -54,12 +54,19 @@ g2.add_edge(2, 3) g2.add_edge(3, 4) g2.add_edge(5, 6) g2.add_edge(6, 3) +g2.add_edge(4, 7) +g2.add_edge(4, 8) +g2.add_edge(7, 9) +g2.add_edge(8, 9) dominators = g2.compute_dominators(5) assert(dominators == {3: set([3, 5, 6]), 4: set([3, 4, 5, 6]), 5: set([5]), - 6: set([5, 6])}) + 6: set([5, 6]), + 7: set([3, 4, 5, 6, 7]), + 8: set([3, 4, 5, 6, 8]), + 9: set([3, 4, 5, 6, 9])}) assert(list(g2.walk_dominators(1, dominators)) == []) @@ -68,6 +75,9 @@ assert(list(g2.walk_dominators(3, dominators)) == [6, 5]) assert(list(g2.walk_dominators(4, dominators)) == [3, 6, 5]) assert(list(g2.walk_dominators(5, dominators)) == []) assert(list(g2.walk_dominators(6, dominators)) == [5]) +assert(list(g2.walk_dominators(7, dominators)) == [4, 3, 6, 5]) +assert(list(g2.walk_dominators(8, dominators)) == [4, 3, 6, 5]) +assert(list(g2.walk_dominators(9, dominators)) == [4, 3, 6, 5]) postdominators = g1.compute_postdominators(6) assert(postdominators == {1: set([1, 2, 6]), @@ -113,3 +123,44 @@ assert(list(g2.walk_postdominators(3, postdominators)) == [4]) assert(list(g2.walk_postdominators(4, postdominators)) == []) assert(list(g2.walk_postdominators(5, postdominators)) == [6, 3, 4]) assert(list(g2.walk_postdominators(6, postdominators)) == [3, 4]) +assert(list(g2.walk_postdominators(7, postdominators)) == []) +assert(list(g2.walk_postdominators(8, postdominators)) == []) +assert(list(g2.walk_postdominators(9, postdominators)) == []) + + +idoms = g1.compute_immediate_dominators(1) +assert(idoms == {2: 1, + 3: 2, + 4: 2, + 5: 2, + 6: 2}) + +idoms = g2.compute_immediate_dominators(1) +assert(idoms == {2: 1, + 3: 2, + 4: 3, + 7: 4, + 8: 4, + 9: 4}) + +idoms = g2.compute_immediate_dominators(5) +assert(idoms == {3: 6, + 4: 3, + 6: 5, + 7: 4, + 8: 4, + 9: 4}) + +frontier = g1.compute_dominance_frontier(1) +assert(frontier == {2: set([2]), + 3: set([5]), + 4: set([5]), + 5: set([2])}) + +frontier = g2.compute_dominance_frontier(1) +assert(frontier == {7: set([9]), + 8: set([9])}) + +frontier = g2.compute_dominance_frontier(5) +assert(frontier == {7: set([9]), + 8: set([9])}) \ No newline at end of file |