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
