From 6c2f49b969dbb2d4490ff2aa150a00086280b116 Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Sun, 10 May 2015 00:35:20 +0200 Subject: graph.py: added computation of immediate dominators --- miasm2/core/graph.py | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index 47be1864..c647ede8 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -300,3 +300,15 @@ 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 n in dominators.keys(): + for p in self.reachable_parents(n): + if p in dominators[n] and n != p: + idoms[n] = p + break + return idoms -- cgit 1.4.1 From 9dd0d7c43f9079fddda74d58c5cc9caca26479fe Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Sun, 10 May 2015 00:36:44 +0200 Subject: graph.py: added computation of the dominance frontier --- miasm2/core/graph.py | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index c647ede8..0d129b3d 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -312,3 +312,26 @@ shape = "box" idoms[n] = p 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) + df = {} + + for n in idoms: + if self._nodes_pred[n] >= 2: + for p in self.predecessors_iter(n): + runner = p + while runner != idoms[n]: + if n not in df: + df[n] = set() + + df[n].add(runner) + runner = idoms[runner] + return df -- cgit 1.4.1 From 7912f1870e2aa87753d1c8537e03826f82801166 Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Sun, 10 May 2015 01:21:49 +0200 Subject: graph.py: replaced line for readability --- miasm2/core/graph.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index 0d129b3d..cd4da705 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -306,7 +306,7 @@ shape = "box" dominators = self.compute_dominators(head) idoms = {} - for n in dominators.keys(): + for n in dominators: for p in self.reachable_parents(n): if p in dominators[n] and n != p: idoms[n] = p -- cgit 1.4.1 From 8635555509e768655f5503792ad39ae1b6b3ff76 Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Tue, 12 May 2015 19:07:19 +0200 Subject: DiGraph: fixed dominance_frontier for graphs with multiple heads --- miasm2/core/graph.py | 2 ++ 1 file changed, 2 insertions(+) diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index cd4da705..b11c2dd8 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -328,6 +328,8 @@ shape = "box" if self._nodes_pred[n] >= 2: for p in self.predecessors_iter(n): runner = p + if runner not in idoms: + continue while runner != idoms[n]: if n not in df: df[n] = set() -- cgit 1.4.1 From 2677cffbb49008488ac37684a3657aa4c3298afa Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Tue, 12 May 2015 19:40:19 +0200 Subject: Tests/graph: extended regression tests --- test/core/graph.py | 42 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 41 insertions(+), 1 deletion(-) diff --git a/test/core/graph.py b/test/core/graph.py index eb320542..4ef37040 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)) == []) @@ -113,3 +120,36 @@ 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]) + +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, 5]), + 5: set([3, 4])}) + +frontier = g2.compute_dominance_frontier(1) +assert(frontier == {9: set([7, 8])}) + +frontier = g2.compute_dominance_frontier(5) +assert(frontier == {9: set([7, 8])}) \ No newline at end of file -- cgit 1.4.1 From 31908bddf6ef9443fcbc057c7d8e3cc8514d2cda Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Thu, 14 May 2015 17:21:14 +0200 Subject: DiGraph: renamed variables in dominance frontier and immediate dominators --- miasm2/core/graph.py | 28 ++++++++++++++-------------- 1 file changed, 14 insertions(+), 14 deletions(-) diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index b11c2dd8..b1a51c14 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -306,10 +306,10 @@ shape = "box" dominators = self.compute_dominators(head) idoms = {} - for n in dominators: - for p in self.reachable_parents(n): - if p in dominators[n] and n != p: - idoms[n] = p + for node in dominators: + for predecessor in self.reachable_parents(node): + if predecessor in dominators[node] and node != predecessor: + idoms[node] = predecessor break return idoms @@ -322,18 +322,18 @@ shape = "box" Software Practice & Experience 4 (2001), p. 9 """ idoms = self.compute_immediate_dominators(head) - df = {} + frontier = {} - for n in idoms: - if self._nodes_pred[n] >= 2: - for p in self.predecessors_iter(n): - runner = p + 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[n]: - if n not in df: - df[n] = set() + while runner != idoms[node]: + if node not in frontier: + frontier[node] = set() - df[n].add(runner) + frontier[node].add(runner) runner = idoms[runner] - return df + return frontier -- cgit 1.4.1 From 9af5b22b6daaefbae6caadc8943a12baee785329 Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Fri, 15 May 2015 03:31:19 +0200 Subject: DiGraph: refactored comments --- miasm2/core/graph.py | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index b1a51c14..b0dc70d6 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 @@ -302,7 +304,12 @@ shape = "box" self.successors_iter) def compute_immediate_dominators(self, head): - """Compute the immediate dominators of the graph""" + """ + Compute the immediate dominators of the graph + + Depends on the implementation characteristics of reachable_parents. + Modifications could break this algorithm. + """ dominators = self.compute_dominators(head) idoms = {} -- cgit 1.4.1 From 5fc740de493c80731de0d0767c54fb6c9516b617 Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Sat, 16 May 2015 03:45:50 +0200 Subject: DiGraph: fixed order in dominance_frontier --- miasm2/core/graph.py | 6 +++--- test/core/graph.py | 12 ++++++++---- 2 files changed, 11 insertions(+), 7 deletions(-) diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index b0dc70d6..00c30d62 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -338,9 +338,9 @@ shape = "box" if runner not in idoms: continue while runner != idoms[node]: - if node not in frontier: - frontier[node] = set() + if runner not in frontier: + frontier[runner] = set() - frontier[node].add(runner) + frontier[runner].add(node) runner = idoms[runner] return frontier diff --git a/test/core/graph.py b/test/core/graph.py index 4ef37040..85218a1c 100644 --- a/test/core/graph.py +++ b/test/core/graph.py @@ -145,11 +145,15 @@ assert(idoms == {3: 6, 9: 4}) frontier = g1.compute_dominance_frontier(1) -assert(frontier == {2: set([2, 5]), - 5: set([3, 4])}) +assert(frontier == {2: set([2]), + 3: set([5]), + 4: set([5]), + 5: set([2])}) frontier = g2.compute_dominance_frontier(1) -assert(frontier == {9: set([7, 8])}) +assert(frontier == {7: set([9]), + 8: set([9])}) frontier = g2.compute_dominance_frontier(5) -assert(frontier == {9: set([7, 8])}) \ No newline at end of file +assert(frontier == {7: set([9]), + 8: set([9])}) \ No newline at end of file -- cgit 1.4.1 From 7a63b077f44fa37ad2aecf3ce9c7f2379038f76e Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Mon, 1 Jun 2015 22:54:45 +0200 Subject: DiGraph: compute_immediate_dominators depends now on walk_dominators --- miasm2/core/graph.py | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) diff --git a/miasm2/core/graph.py b/miasm2/core/graph.py index 00c30d62..2565f3d1 100644 --- a/miasm2/core/graph.py +++ b/miasm2/core/graph.py @@ -304,17 +304,12 @@ shape = "box" self.successors_iter) def compute_immediate_dominators(self, head): - """ - Compute the immediate dominators of the graph - - Depends on the implementation characteristics of reachable_parents. - Modifications could break this algorithm. - """ + """Compute the immediate dominators of the graph""" dominators = self.compute_dominators(head) idoms = {} for node in dominators: - for predecessor in self.reachable_parents(node): + for predecessor in self.walk_dominators(node, dominators): if predecessor in dominators[node] and node != predecessor: idoms[node] = predecessor break -- cgit 1.4.1 From f6e00985a3e59f1f4813751572b5981d4dd1e6f4 Mon Sep 17 00:00:00 2001 From: Tim Blazytko Date: Tue, 2 Jun 2015 15:39:19 +0200 Subject: Test/Graph: extended regression tests for g2 --- test/core/graph.py | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/test/core/graph.py b/test/core/graph.py index 85218a1c..5100cf8d 100644 --- a/test/core/graph.py +++ b/test/core/graph.py @@ -75,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]), @@ -120,6 +123,10 @@ 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, -- cgit 1.4.1