[pypy-commit] pypy stmgc-c8: do optimal evaluation order for forward flow analysis

[Raemi]

Author: Remi Meier <remi.me...@gmail.com>
Branch: stmgc-c8
Changeset: r80997:c4bb2166366b
Date: 2015-11-27 12:56 +0100
http://bitbucket.org/pypy/pypy/changeset/c4bb2166366b/

Log:    do optimal evaluation order for forward flow analysis

diff --git a/rpython/translator/backendopt/dataflow.py 
b/rpython/translator/backendopt/dataflow.py
--- a/rpython/translator/backendopt/dataflow.py
+++ b/rpython/translator/backendopt/dataflow.py
@@ -36,7 +36,17 @@
         raise NotImplementedError("abstract base class")
 
 
-
+def postorder_block_list(graph):
+    visited = set()
+    blocks = []
+    def dfs_recurse(block):
+        visited.add(block)
+        for link in block.exits:
+            if link.target not in visited:
+                dfs_recurse(link.target)
+        blocks.append(block)
+    dfs_recurse(graph.startblock)
+    return blocks
 
 
 class AbstractForwardDataFlowAnalysis(AbstractDataFlowAnalysis):
@@ -86,18 +96,16 @@
 
         #
         # iterate:
-        # todo: ordered set? reverse post-order?
-        blocks.remove(graph.startblock)
-        pending = collections.deque(blocks)
-        pending.append(graph.startblock)
+        # todo: ordered set?
+        pending = collections.deque(reversed(postorder_block_list(graph)))
         while pending:
-            block = pending.pop()
+            block = pending.popleft()
             if self._update_in_state_of(block, entrymap, in_states, 
out_states):
                 block_out = self.transfer_function(block, in_states[block])
                 if block_out != out_states[block]:
                     out_states[block] = block_out
                     for link in block.exits:
                         if link.target not in pending:
-                            pending.appendleft(link.target)
+                            pending.append(link.target)
         #
         return in_states, out_states
diff --git a/rpython/translator/backendopt/test/test_dataflow.py 
b/rpython/translator/backendopt/test/test_dataflow.py
--- a/rpython/translator/backendopt/test/test_dataflow.py
+++ b/rpython/translator/backendopt/test/test_dataflow.py
@@ -1,6 +1,7 @@
 import random
 from rpython.tool.algo.unionfind import UnionFind
-from rpython.translator.backendopt.dataflow import 
AbstractForwardDataFlowAnalysis
+from rpython.translator.backendopt.dataflow import (
+    AbstractForwardDataFlowAnalysis, postorder_block_list)
 
 import pytest
 
@@ -85,3 +86,42 @@
     assert len(sfa.seen) == 5
     assert ins[g.startblock] == sfa.entry_state(None)
     assert outs[g.returnblock] == sfa.entry_state(None)
+
+
+def test_postorder_block_list():
+    def f(x):
+        pass
+    t = TranslationContext()
+    g = t.buildflowgraph(f)
+    pobl = postorder_block_list(g)
+    assert len(set(pobl)) == 2 # start & return
+
+    def f2(x):
+        if x:
+            x=x+1
+        else:
+            x=x+2
+        return x
+    t = TranslationContext()
+    g = t.buildflowgraph(f2)
+    pobl = postorder_block_list(g)
+    assert len(pobl[0].exits) == 0
+    assert len(pobl[1].exits) == 1
+    assert len(pobl[2].exits) == 1
+    assert len(pobl[3].exits) == 2
+    assert len(set(pobl)) == 4
+
+
+def test_postorder_block_list2():
+    def f(x):
+        if x < 0:
+            while x:
+                pass
+            return x
+        else:
+            while x:
+                if x-1:
+                    return x
+    t = TranslationContext()
+    g = t.buildflowgraph(f)
+    assert len(set(postorder_block_list(g))) == 5
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit