Author: Richard Plangger <r...@pasra.at>
Branch: vecopt-merge
Changeset: r79050:a376c01d579f
Date: 2015-08-19 11:55 +0200
http://bitbucket.org/pypy/pypy/changeset/a376c01d579f/
Log: testing the path iteration, there is still a problem in
analyse_index_calculation
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
@@ -112,6 +112,7 @@
# save the operation that produces the result for the first argument
# only for guard_true/guard_false
self.guard_bool_bool_node = None
+ self._stack = False
def getoperation(self):
return self.op
@@ -285,28 +286,31 @@
else:
iterdir = node.provides()
if index >= len(iterdir):
- if blacklist:
- blacklist_visit[node] = None
+ #if blacklist:
+ #blacklist_visit[node] = None
+ # print "blacklisting 1", node, "path",
'->'.join([str(p.opidx) for p in path.path])
continue
else:
next_dep = iterdir[index]
next_node = next_dep.to
index += 1
+ if index < len(iterdir):
+ worklist.append((index, node, pathlen))
+ else:
+ print "blacklisting 2", node, "path",
'->'.join([str(p.opidx) for p in path.path])
+ blacklist_visit[node] = None
+ path.cut_off_at(pathlen)
+ path.walk(next_node)
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
+ # note that the destiantion node ``to'' is never
blacklisted
+ #if blacklist:
+ # blacklist_visit[next_node] = None
else:
worklist.append((0, next_node, pathlen))
@@ -731,6 +735,17 @@
# and the next guard instruction
tracker.add_non_pure(node)
+ def cycles(self):
+ """ NOT_RPYTHON """
+ stack = []
+ for node in self.nodes:
+ node._stack = False
+ #
+ label = self.nodes[0]
+ if _first_cycle(stack, label):
+ return stack
+ return None
+
def __repr__(self):
graph = "graph([\n"
for node in self.nodes:
@@ -744,6 +759,7 @@
return graph + " ])"
def as_dot(self):
+ """ NOT_RPTYHON """
if not we_are_translated():
dot = "digraph dep_graph {\n"
for node in self.nodes:
@@ -765,6 +781,49 @@
return dot
raise NotImplementedError("dot only for debug purpose")
+def _first_cycle(stack, node):
+ node._stack = True
+ stack.append(node)
+
+ for dep in node.provides():
+ succ = dep.to
+ if succ._stack:
+ # found cycle!
+ while stack[0] is not succ:
+ del stack[0]
+ return True
+ else:
+ return _first_cycle(stack, succ)
+
+ return False
+
+def _strongly_connect(index, stack, cycles, node):
+ """ currently unused """
+ node._scc_index = index
+ node._scc_lowlink = index
+ index += 1
+ stack.append(node)
+ node._scc_stack = True
+
+ for dep in node.provides():
+ succ = dep.to
+ if succ._scc_index == -1:
+ index = _strongly_connect(index, stack, cycles, succ)
+ node._scc_lowlink = min(node._scc_lowlink, succ._scc_lowlink)
+ elif succ._scc_stack:
+ node._scc_lowlink = min(node._scc_lowlink, succ._scc_index)
+
+ if node._scc_lowlink == node._scc_index:
+ cycle = []
+ while True:
+ w = stack.pop()
+ w._scc_stack = False
+ cycle.append(w)
+ if w is node:
+ break
+ cycles.append(cycle)
+ return index
+
class IntegralForwardModification(object):
""" Calculates integral modifications on integer boxes. """
def __init__(self, memory_refs, index_vars, comparison_vars,
invariant_vars):
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
@@ -17,6 +17,10 @@
def __repr__(self):
return "n%d" % self.opidx
+class FakeDependencyGraph(DependencyGraph):
+ def __init__(self):
+ pass
+
class DependencyBaseTest(BaseTest):
def setup_method(self, method):
@@ -391,7 +395,7 @@
self.assert_dependencies(trace, full_check=True)
- def test_iterate_paths(self):
+ def test_iterate(self):
n1,n2,n3,n4,n5 = [FakeNode(i+1) for i in range(5)]
# n1 -> n2 -> n4 -> n5
# +---> n3 --^
@@ -434,7 +438,7 @@
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):
+ def test_iterate_blacklist_diamond(self):
blacklist = {}
n1,n2,n3,n4 = [FakeNode(i+1) for i in range(4)]
# n1 -> n2 -> n4
@@ -445,9 +449,9 @@
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"
+ assert paths[1].as_str() == "n1 -> n3 -> n4"
- def test_iterate_paths_blacklist_double_diamond(self):
+ def test_iterate_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
@@ -461,8 +465,56 @@
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"
+ assert paths[1].as_str() == "n1 -> n2 -> n4 -> n5 -> n7 -> n8"
+ assert paths[2].as_str() == "n1 -> n3 -> n4"
+
+ def test_iterate_blacklist_split_path(self):
+ blacklist = {}
+ n1,n2,n3,n4,n5,n6,n7,n8 = [FakeNode(i+1) for i in range(8)]
+ n1.edge_to(n2);
+ n3.edge_to(n2);
+ n2.edge_to(n4);
+ n3.edge_to(n4);
+
+ paths = list(n4.iterate_paths(n3, backwards=True, blacklist=True))
+ assert len(paths) == 2
+ assert paths[0].as_str() == "n4 -> n2 -> n3"
+ assert paths[1].as_str() == "n4 -> n3"
+
+ n5.edge_to(n1)
+ n5.edge_to(n3)
+
+ paths = list(n4.iterate_paths(n5, backwards=True, blacklist=True))
+ assert len(paths) == 3
+ assert paths[0].as_str() == "n4 -> n2 -> n1 -> n5"
+ assert paths[1].as_str() == "n4 -> n2 -> n3 -> n5"
+ assert paths[2].as_str() == "n4 -> n3"
+
+ def test_sccs(self):
+ n1,n2 = FakeNode(1), FakeNode(2)
+ n1.edge_to(n2); n2.edge_to(n1)
+
+ graph = FakeDependencyGraph()
+ graph.nodes = [n1,n2]
+ cycle = graph.cycles()
+ assert cycle == [n1, n2]
+
+ n3 = FakeNode(0)
+ graph.nodes = [n3]
+ cycle = graph.cycles()
+ assert cycle is None
+
+ def test_cycles_2(self):
+ n1,n2,n3,n4 = FakeNode(1), FakeNode(2), FakeNode(3), FakeNode(4)
+ n1.edge_to(n3); n3.edge_to(n4); n4.edge_to(n1)
+
+ graph = FakeDependencyGraph()
+ graph.nodes = [n1,n2,n3]
+ cycle = graph.cycles()
+ assert cycle is not None
+ assert cycle == [n1,n3,n4]
+
+
class TestLLtype(BaseTestDependencyGraph, LLtypeMixin):
pass
diff --git a/rpython/jit/metainterp/optimizeopt/test/test_vectorize.py
b/rpython/jit/metainterp/optimizeopt/test/test_vectorize.py
--- a/rpython/jit/metainterp/optimizeopt/test/test_vectorize.py
+++ b/rpython/jit/metainterp/optimizeopt/test/test_vectorize.py
@@ -93,6 +93,9 @@
self.show_dot_graph(DependencyGraph(opt.loop), "original_" +
self.test_name)
opt.analyse_index_calculations()
if opt.dependency_graph is not None:
+ cycle = opt.dependency_graph.cycles()
+ if cycle is not None:
+ print "CYCLE found %s" % cycle
self.show_dot_graph(opt.dependency_graph, "early_exit_" +
self.test_name)
opt.schedule(False)
opt.unroll_loop_iterations(loop, unroll_factor)
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
@@ -515,23 +515,27 @@
label_node = graph.getnode(0)
ee_guard_node = graph.getnode(ee_pos)
guards = graph.guards
+ unique = set()
for guard_node in guards:
if guard_node is ee_guard_node:
continue
modify_later = []
last_prev_node = None
- i = 0
for path in guard_node.iterate_paths(ee_guard_node,
backwards=True, blacklist=True):
+ p = '->'.join([str(p.opidx) for p in path.path])
+ if p in unique:
+ assert 0
+ else:
+ unique.add(p)
+ print "PATH:", p
if not we_are_translated():
path.check_acyclic()
- print "loop", i
- i+=1
prev_node = path.second()
dep = prev_node.depends_on(guard_node)
if dep.is_failarg():
# this dependency we are able to break because it is soley
# relevant due to one or multiple fail args
- if prev_node == last_prev_node:
+ if prev_node is not last_prev_node:
# ...
# o o
# \ /
@@ -540,18 +544,19 @@
# (g)
# this graph yields 2 paths from (g), thus (a) is
# remembered and skipped the second time visited
- continue
- modify_later.append((prev_node, guard_node))
+ modify_later.append((prev_node, guard_node))
+ print " => remove guard -> second"
+ last_prev_node = prev_node
+ continue
+ if path.is_always_pure(exclude_first=True, exclude_last=True):
+ path.set_schedule_priority(10)
+ if path.last() is ee_guard_node:
+ modify_later.append((path.last_but_one(), None))
+ print " => always pure"
else:
- if path.is_always_pure(exclude_first=True,
exclude_last=True):
- path.set_schedule_priority(10)
- 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!
- break
- last_prev_node = prev_node
+ # transformation is invalid.
+ # exit and do not enter else branch!
+ break
else:
# transformation is valid, modify the graph and execute
# this guard earlier
diff --git a/rpython/jit/metainterp/warmstate.py
b/rpython/jit/metainterp/warmstate.py
--- a/rpython/jit/metainterp/warmstate.py
+++ b/rpython/jit/metainterp/warmstate.py
@@ -304,6 +304,8 @@
self.vec = bool(value)
def set_param_vec_params(self, value):
+ if NonConstant(False):
+ value = 'blah' # not a constant ''
values = value.split(":")
self.vec_all = bool(values[0])
self.vec_cost = 0
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
