Author: Carl Friedrich Bolz <cfb...@gmx.de>
Branch: better-storesink
Changeset: r87235:c701f3c76e7c
Date: 2016-09-19 21:53 +0200
http://bitbucket.org/pypy/pypy/changeset/c701f3c76e7c/
Log: loop_blocks was broken in complex cases
diff --git a/rpython/translator/backendopt/cse.py
b/rpython/translator/backendopt/cse.py
--- a/rpython/translator/backendopt/cse.py
+++ b/rpython/translator/backendopt/cse.py
@@ -304,7 +304,46 @@
result._clear_heapcache_for_loop_blocks(loop_blocks)
return result
-def loop_blocks(graph):
+def compute_reachability_no_backedges(graph, backedges):
+ reachable = {}
+ blocks = list(graph.iterblocks())
+ # Reversed order should make the reuse path more likely.
+ for block in reversed(blocks):
+ reach = set()
+ scheduled = [block]
+ while scheduled:
+ current = scheduled.pop()
+ for link in current.exits:
+ if link in backedges:
+ continue
+ if link.target in reachable:
+ reach.add(link.target)
+ reach = reach | reachable[link.target]
+ continue
+ if link.target not in reach:
+ reach.add(link.target)
+ scheduled.append(link.target)
+ reachable[block] = reach
+ return reachable
+
+def loop_blocks(graph, backedges, entrymap):
+ reachable_no_backedges = compute_reachability_no_backedges(graph,
backedges)
+ reachable = support.compute_reachability(graph)
+ result = {}
+ for block in graph.iterblocks():
+ entering_backedges = [link for link in entrymap[block]
+ if link in backedges]
+ if not entering_backedges:
+ # no backedge entries
+ continue
+ loop_blocks = {block}
+ for target in reachable_no_backedges[block]:
+ if any(link.prevblock in reachable[target]
+ for link in entering_backedges):
+ loop_blocks.add(target)
+ result[block] = loop_blocks
+ return result
+
loop_blocks = support.find_loop_blocks(graph)
result = {}
for loop_block, start in loop_blocks.iteritems():
@@ -319,8 +358,8 @@
def transform(self, graph):
variable_families =
ssa.DataFlowFamilyBuilder(graph).get_variable_families()
entrymap = mkentrymap(graph)
- loops = loop_blocks(graph)
backedges = support.find_backedges(graph)
+ loops = loop_blocks(graph, backedges, entrymap)
todo = collections.deque([graph.startblock])
caches_to_merge = collections.defaultdict(list)
done = set()
diff --git a/rpython/translator/backendopt/test/test_cse.py
b/rpython/translator/backendopt/test/test_cse.py
--- a/rpython/translator/backendopt/test/test_cse.py
+++ b/rpython/translator/backendopt/test/test_cse.py
@@ -1,6 +1,6 @@
import pytest
from rpython.translator.translator import TranslationContext, graphof
-from rpython.translator.backendopt.cse import CSE, Cache
+from rpython.translator.backendopt.cse import CSE, Cache, loop_blocks
from rpython.flowspace.model import Variable, Constant
from rpython.translator.backendopt import removenoops
from rpython.flowspace.model import checkgraph, summary
@@ -354,6 +354,28 @@
return res
self.check(f, [int], getfield=1)
+ def test_loopinvariant_heap_merge_nested(self):
+ class A(object):
+ pass
+ def f(i):
+ res = 0
+ y = 0
+ while y < i:
+ y += 1
+ x = i
+ a = A()
+ if i == 0:
+ a.x = 1
+ else:
+ a.x = i
+ while x:
+ x -= 1
+ res += a.x
+ if x % 1000 == 1:
+ a.x = 5
+ return res
+ self.check(f, [int], getfield=1)
+
def test_direct_merge(self):
def f(i):
a = i + 1
@@ -567,3 +589,45 @@
assert not needs_adding
assert res is v2
+
+def test_loop_blocks():
+ from rpython.flowspace.model import mkentrymap
+ from rpython.translator.backendopt import support
+ class A(object): pass
+ def f(i):
+ res = 0
+ y = 0
+ while y < i: # block1
+ y += 1 # block2
+ x = i
+ a = A()
+ if i == 0:
+ a.x = 1 # block3
+ else:
+ a.x = i # block4
+ while x: # block5
+ x -= 1 # block6
+ res += a.x
+ if x % 1000 == 1:
+ a.x = 5 # block7
+ return res # block8
+
+ t = TranslationContext()
+ t.buildannotator().build_types(f, [int])
+ t.buildrtyper().specialize()
+ graph = graphof(t, f)
+ startblock = graph.startblock
+ block1 = startblock.exits[0].target
+ block2 = block1.exits[1].target
+ block3 = block2.exits[0].target
+ block4 = block2.exits[1].target
+ block5 = block4.exits[0].target
+ block6 = block5.exits[1].target
+ block7 = block6.exits[1].target
+
+ loops = loop_blocks(graph, support.find_backedges(graph),
+ mkentrymap(graph))
+ assert loops == {
+ block1: {block1, block2, block3, block4, block5, block6, block7},
+ block5: {block5, block6, block7},
+ }
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
