Author: Richard Plangger <r...@pasra.at>
Branch: vecopt-merge
Changeset: r79042:4886c173125a
Date: 2015-08-18 17:49 +0200
http://bitbucket.org/pypy/pypy/changeset/4886c173125a/
Log: path iteration on a dependecy graph can enable blacklisting nodes
that have already been visited.this cuts down the search space. this
is only valid if a property must hold along all the paths and once
for one path proven, any subpath must not be checked anymore (is the
case in guard early exit
diff --git a/rpython/jit/metainterp/optimizeopt/dependency.py
b/rpython/jit/metainterp/optimizeopt/dependency.py
--- a/rpython/jit/metainterp/optimizeopt/dependency.py
+++ b/rpython/jit/metainterp/optimizeopt/dependency.py
@@ -44,7 +44,12 @@
def last_but_one(self):
if len(self.path) < 2:
return None
- return self.path[len(self.path)-2]
+ return self.path[-2]
+
+ def last(self):
+ if len(self.path) < 1:
+ return None
+ return self.path[-1]
def is_always_pure(self, exclude_first=False, exclude_last=False):
last = len(self.path)-1
@@ -261,10 +266,16 @@
worklist.append(dep.to)
return True
- def iterate_paths(self, to, backwards=False, path_max_len=-1):
- """ yield all nodes from self leading to 'to' """
+ def iterate_paths(self, to, backwards=False, path_max_len=-1,
blacklist=False):
+ """ yield all nodes from self leading to 'to'. backwards determines
+ the iteration direction and blacklist marks nodes that have already
been visited.
+ blacklist comes in handy if a property must hold for every path. not
*every* possible
+ instance must be iterated, but trees that have already been visited
can be ignored
+ after the have been visited
+ """
if self is to:
return
+ blacklist_visit = {}
path = Path([self])
worklist = [(0, self, 1)]
while len(worklist) > 0:
@@ -274,19 +285,28 @@
else:
iterdir = node.provides()
if index >= len(iterdir):
+ if blacklist:
+ blacklist_visit[node] = None
continue
else:
next_dep = iterdir[index]
next_node = next_dep.to
index += 1
+ if blacklist and next_node in blacklist_visit:
+ yield Path(path.path[:])
+ continue
if index < len(iterdir):
worklist.append((index, node, pathlen))
+ else:
+ blacklist_visit[node] = None
path.cut_off_at(pathlen)
path.walk(next_node)
pathlen += 1
if next_node is to or (path_max_len > 0 and pathlen >=
path_max_len):
yield Path(path.path[:])
+ if blacklist:
+ blacklist_visit[next_node] = None
else:
worklist.append((0, next_node, pathlen))
diff --git a/rpython/jit/metainterp/optimizeopt/test/test_dependency.py
b/rpython/jit/metainterp/optimizeopt/test/test_dependency.py
--- a/rpython/jit/metainterp/optimizeopt/test/test_dependency.py
+++ b/rpython/jit/metainterp/optimizeopt/test/test_dependency.py
@@ -434,5 +434,35 @@
for i in r:
assert paths[i].as_str() == "n0 -> %s -> n%d" % (nodes[i],
len(r)+1)
+ def test_iterate_paths_blacklist_diamond(self):
+ blacklist = {}
+ n1,n2,n3,n4 = [FakeNode(i+1) for i in range(4)]
+ # n1 -> n2 -> n4
+ # +---> n3 --^
+ n1.edge_to(n2); n2.edge_to(n4);
+ n1.edge_to(n3); n3.edge_to(n4);
+
+ paths = list(n1.iterate_paths(n4, blacklist=True))
+ assert len(paths) == 2
+ assert paths[0].as_str() == "n1 -> n2 -> n4"
+ assert paths[1].as_str() == "n1 -> n3"
+
+ def test_iterate_paths_blacklist_double_diamond(self):
+ blacklist = {}
+ n1,n2,n3,n4,n5,n6,n7,n8 = [FakeNode(i+1) for i in range(8)]
+ # n1 -> n2 -> n4 -> n5 -> n6 --> n8
+ # +---> n3 --^ +---> n7 --^
+ n1.edge_to(n2); n2.edge_to(n4);
+ n1.edge_to(n3); n3.edge_to(n4);
+ n4.edge_to(n5)
+ n5.edge_to(n6); n6.edge_to(n8);
+ n5.edge_to(n7); n7.edge_to(n8);
+
+ paths = list(n1.iterate_paths(n8, blacklist=True))
+ assert len(paths) == 3
+ assert paths[0].as_str() == "n1 -> n2 -> n4 -> n5 -> n6 -> n8"
+ assert paths[1].as_str() == "n1 -> n2 -> n4 -> n5 -> n7"
+ assert paths[2].as_str() == "n1 -> n3"
+
class TestLLtype(BaseTestDependencyGraph, LLtypeMixin):
pass
diff --git a/rpython/jit/metainterp/optimizeopt/vectorize.py
b/rpython/jit/metainterp/optimizeopt/vectorize.py
--- a/rpython/jit/metainterp/optimizeopt/vectorize.py
+++ b/rpython/jit/metainterp/optimizeopt/vectorize.py
@@ -521,7 +521,7 @@
modify_later = []
last_prev_node = None
i = 0
- for path in guard_node.iterate_paths(ee_guard_node, True):
+ for path in guard_node.iterate_paths(ee_guard_node,
backwards=True, blacklist=True):
if not we_are_translated():
path.check_acyclic()
print "loop", i
@@ -545,7 +545,8 @@
else:
if path.is_always_pure(exclude_first=True,
exclude_last=True):
path.set_schedule_priority(10)
- modify_later.append((path.last_but_one(), None))
+ if path.last() is ee_guard_node:
+ modify_later.append((path.last_but_one(), None))
else:
# transformation is invalid.
# exit and do not enter else branch!
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
