Author: Carl Friedrich Bolz <cfb...@gmx.de>
Branch: better-storesink
Changeset: r87154:2f9d46642175
Date: 2016-09-06 17:43 +0200
http://bitbucket.org/pypy/pypy/changeset/2f9d46642175/

Log:    support for removing loop-invariant heap reads

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
@@ -42,7 +42,7 @@
                 self.heapcache.copy())
 
 
-    def merge(self, firstlink, tuples, backedge):
+    def merge(self, firstlink, tuples):
         purecache = {}
         block = firstlink.target
         # copy all operations that exist in *all* blocks over. need to add a 
new
@@ -102,10 +102,6 @@
         # ______________________
         # merge heapcache
         heapcache = {}
-        if backedge:
-            # can't deal with heapcache and backedges yet
-            return Cache(
-                    self.variable_families, self.analyzer, purecache, 
heapcache)
 
         # try non-straight merges
         for argindex, inputarg in enumerate(block.inputargs):
@@ -138,6 +134,7 @@
                         block.inputargs.append(newres)
                     heapcache[newkey] = newres
 
+        # regular merge
         for key, res in self.heapcache.iteritems():
             for link, cache in tuples[1:]:
                 val = cache.heapcache.get(key, None)
@@ -162,13 +159,24 @@
             if k[0].concretetype == concretetype and k[1] == fieldname:
                 del self.heapcache[k]
 
-    def _clear_heapcache_for_effects(self, op):
+    def _clear_heapcache_for_effects_of_op(self, op):
         effects = self.analyzer.analyze(op)
+        self._clear_heapcache_for_effects(effects)
+
+    def _clear_heapcache_for_effects(self, effects):
         for k in self.heapcache.keys():
             key = ('struct', k[0].concretetype, k[1])
             if key in effects:
                 del self.heapcache[k]
 
+    def _clear_heapcache_for_loop_blocks(self, blocks):
+        effects = self.analyzer.bottom_result()
+        for block in blocks:
+            for op in block.operations:
+                effects = self.analyzer.join_two_results(
+                    effects, self.analyzer.analyze(op))
+        self._clear_heapcache_for_effects(effects)
+
     def cse_block(self, block):
         def representative_arg(arg):
             if isinstance(arg, Variable):
@@ -194,7 +202,7 @@
                 self.heapcache[target, field] = op.args[2]
                 continue
             if has_side_effects(op):
-                self._clear_heapcache_for_effects(op)
+                self._clear_heapcache_for_effects_of_op(op)
                 continue
 
             # foldable operations
@@ -212,14 +220,28 @@
                 self.purecache[key] = op.result
         return added_some_same_as
 
-def _merge(tuples, variable_families, analyzer, backedge=False):
+def _merge(tuples, variable_families, analyzer, loop_blocks=None):
     if not tuples:
         return Cache(variable_families, analyzer)
     if len(tuples) == 1:
         (link, cache), = tuples
-        return cache.copy()
-    firstlink, firstcache = tuples[0]
-    return firstcache.merge(firstlink, tuples, backedge)
+        result = cache.copy()
+    else:
+        firstlink, firstcache = tuples[0]
+        result = firstcache.merge(firstlink, tuples)
+    if loop_blocks:
+        # for all blocks in the loop, clean the heapcache for their effects
+        # that way, loop-invariant reads can be removed, if no one writes to
+        # anything that can alias with them.
+        result._clear_heapcache_for_loop_blocks(loop_blocks)
+    return result
+
+def loop_blocks(graph):
+    loop_blocks = support.find_loop_blocks(graph)
+    result = {}
+    for loop_block, start in loop_blocks.iteritems():
+        result.setdefault(start, []).append(loop_block)
+    return result
 
 class CSE(object):
     def __init__(self, translator):
@@ -229,6 +251,7 @@
     def transform(self, graph):
         variable_families = 
ssa.DataFlowFamilyBuilder(graph).get_variable_families()
         entrymap = mkentrymap(graph)
+        loops = loop_blocks(graph)
         backedges = support.find_backedges(graph)
         todo = collections.deque([graph.startblock])
         caches_to_merge = collections.defaultdict(list)
@@ -238,15 +261,11 @@
 
         while todo:
             block = todo.popleft()
-            backedge = False
-            for link in entrymap[block]:
-                if link in backedges:
-                    backedge = True
-                    break
 
             if block.operations:
                 cache = _merge(
-                    caches_to_merge[block], variable_families, self.analyzer, 
backedge)
+                    caches_to_merge[block], variable_families, self.analyzer,
+                    loops.get(block, None))
                 changed_block = cache.cse_block(block)
                 added_some_same_as = changed_block or added_some_same_as
             done.add(block)
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
@@ -279,3 +279,17 @@
             return res
         self.check(f, [int], int_add=2)
 
+
+    def test_loopinvariant_heap(self):
+        class A(object):
+            pass
+        def f(i):
+            a = A()
+            a.x = i
+            res = 0
+            x = i
+            while x:
+                x -= 1
+                res += a.x
+            return res
+        self.check(f, [int], getfield=0)
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit

Reply via email to