Author: Richard Plangger <r...@pasra.at>
Branch: vecopt2
Changeset: r77081:bcbdc469ac7c
Date: 2015-03-17 17:16 +0100
http://bitbucket.org/pypy/pypy/changeset/bcbdc469ac7c/
Log: separated dependency graph testing from the vectorize optimization
tests. added more test cases that check fail args of guards
(extended impl as well) extended the test cases to check that no
dependency edge duplication is happening added missing vectorize
field for jiddriver_sd in the test suit for virtualstate (all tests
passing now)
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
@@ -8,7 +8,9 @@
self.is_definition = is_definition
def __repr__(self):
- return 'dep(%d -> %d, defines? %d)' % (self.idx_from, self.idx_to,
self.is_definition)
+ return 'Dep(trace[%d] -> trace[%d], arg: %s, def-use? %d)' \
+ % (self.idx_from, self.idx_to, self.defined_arg, \
+ self.is_definition)
class DependencyGraph(object):
""" A graph that represents one of the following dependencies:
@@ -36,14 +38,16 @@
defining_indices = {}
for i,op in enumerate(operations):
- # the label operation defines all operations at the beginning of
the loop
+ # the label operation defines all operations at the
+ # beginning of the loop
if op.getopnum() == rop.LABEL:
for arg in op.getarglist():
defining_indices[arg] = 0
continue # prevent adding edge to the label itself
- # TODO what about a JUMP operation? it often has many parameters
(10+) and uses
- # nearly every definition in the trace (for loops). Maybe we can
skip this operation
+ # TODO what about a JUMP operation? it often has many parameters
+ # (10+) and uses nearly every definition in the trace (for loops).
+ # Maybe we can skip this operation and let jump NEVER move...
if op.result is not None:
# the trace is always in SSA form, thus it is neither possible
to have a WAR
@@ -55,9 +59,33 @@
idx = defining_indices[arg]
self._put_edge(idx, i, arg)
+ if op.getfailargs():
+ for arg in op.getfailargs():
+ if arg in defining_indices:
+ idx = defining_indices[arg]
+ self._put_edge(idx, i, arg)
+
def _put_edge(self, idx_from, idx_to, arg):
- self.adjacent_list[idx_from].append(Dependency(idx_from, idx_to, arg,
True))
- self.adjacent_list[idx_to].append(Dependency(idx_to, idx_from, arg,
False))
+ if self._is_unique_dep(idx_from, idx_to, arg):
+ self.adjacent_list[idx_from].append(Dependency(idx_from, idx_to,
arg, True))
+ self.adjacent_list[idx_to].append(Dependency(idx_to, idx_from,
arg, False))
+
+ def _is_unique_dep(self, idx_from, idx_to, arg):
+ """ Dependencies must be unique. It is not allowed
+ to have multiple dependencies.
+ e.g. label(i1)
+ i2 = int_add(i1,i1)
+ ...
+
+ Only the label instr can only have one dep (0->1) even if it is
+ used twice in int_add. The same is true for the reverse dependency
+ (1<-0) at int_add.
+ """
+ for dep in self.adjacent_list[idx_from]:
+ if dep.idx_from == idx_from and dep.idx_to == idx_to \
+ and dep.defined_arg == arg:
+ return False
+ return True
def instr_dependencies(self, idx):
edges = self.adjacent_list[idx]
diff --git a/rpython/jit/metainterp/optimizeopt/test/test_dependency.py
b/rpython/jit/metainterp/optimizeopt/test/test_dependency.py
new file mode 100644
--- /dev/null
+++ b/rpython/jit/metainterp/optimizeopt/test/test_dependency.py
@@ -0,0 +1,144 @@
+import py
+
+from rpython.jit.metainterp.optimizeopt.test.test_util import (
+ LLtypeMixin, BaseTest, FakeMetaInterpStaticData,
convert_old_style_to_targets)
+from rpython.jit.metainterp.history import TargetToken, JitCellToken, TreeLoop
+from rpython.jit.metainterp.optimizeopt.dependency import DependencyGraph,
Dependency
+from rpython.jit.metainterp.resoperation import rop, ResOperation
+
+class DepTestHelper(BaseTest):
+
+ enable_opts =
"intbounds:rewrite:virtualize:string:earlyforce:pure:heap:unfold"
+
+ def build_dependency(self, ops):
+ loop = self.parse_loop(ops)
+ return DependencyGraph(loop)
+
+ def parse_loop(self, ops):
+ loop = self.parse(ops, postprocess=self.postprocess)
+ token = JitCellToken()
+ loop.operations = [ResOperation(rop.LABEL, loop.inputargs, None,
+ descr=TargetToken(token))] + loop.operations
+ if loop.operations[-1].getopnum() == rop.JUMP:
+ loop.operations[-1].setdescr(token)
+ return loop
+
+ def assert_no_edge(self, graph, f, t = -1):
+ if type(f) == list:
+ for _f,_t in f:
+ self.assert_no_edge(graph, _f, _t)
+ else:
+ assert graph.instr_dependency(f, t) is None, \
+ " it is expected that instruction at index" + \
+ " %d DOES NOT depend on instr on index %d but it does" \
+ % (f, t)
+
+ def assert_def_use(self, graph, from_instr_index, to_instr_index = -1):
+ if type(from_instr_index) == list:
+ for f,t in from_instr_index:
+ self.assert_def_use(graph, f, t)
+ else:
+ assert graph.instr_dependency(from_instr_index,
+ to_instr_index) is not None, \
+ " it is expected that instruction at index" + \
+ " %d depends on instr on index %d but it is not" \
+ % (from_instr_index, to_instr_index)
+
+ def assert_dependant(self, graph, edge_list):
+ """ Check if all dependencies are met. for complex cases
+ adding None instead of a list of integers skips the test.
+ This checks both if a dependency forward and backward exists.
+ """
+ assert len(edge_list) == len(graph.adjacent_list)
+ for idx,edges in enumerate(edge_list):
+ if edges is None:
+ continue
+ dependencies = graph.adjacent_list[idx]
+ for edge in edges:
+ dependency = graph.instr_dependency(idx,edge)
+ assert dependency is not None, \
+ " it is expected that instruction at index" + \
+ " %d depends on instr on index %d but it is not" \
+ % (idx, edge)
+ dependencies.remove(dependency)
+ assert dependencies == [], \
+ "dependencies unexpected %s" \
+ % dependencies
+
+class BaseTestDependencyGraph(DepTestHelper):
+ def test_dependency_empty(self):
+ ops = """
+ []
+ jump()
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph, [ [], [], ])
+
+ def test_dependency_of_constant_not_used(self):
+ ops = """
+ []
+ i1 = int_add(1,1)
+ jump()
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph, [ [], [], [] ])
+
+ def test_dependency_simple(self):
+ ops = """
+ []
+ i1 = int_add(1,1)
+ i2 = int_add(i1,1)
+ guard_value(i2,3) []
+ jump()
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [], [2], [1,3], [2], [], ])
+
+ def test_def_use_jump_use_def(self):
+ ops = """
+ [i3]
+ i1 = int_add(i3,1)
+ guard_value(i1,0) []
+ jump(i1)
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [1], [0,2,3], [1], [1] ])
+
+ def test_dependency_guard(self):
+ ops = """
+ [i3]
+ i1 = int_add(1,1)
+ guard_value(i1,0) [i3]
+ jump(i3)
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [2,3], [2], [1,0], [0] ])
+
+ def test_no_edge_duplication(self):
+ ops = """
+ [i1]
+ i2 = int_lt(i1,10)
+ guard_false(i2) [i1]
+ i3 = int_add(i1,i1)
+ jump(i3)
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [1,2,3], [0,2], [1,0], [0,4], [3] ])
+
+ def test_no_edge_duplication_in_guard_failargs(self):
+ ops = """
+ [i1]
+ i2 = int_lt(i1,10)
+ guard_false(i2) [i1,i1,i2,i1,i2,i1]
+ jump(i1)
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [1,2,3], [0,2], [1,0], [0] ])
+
+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
@@ -19,7 +19,7 @@
class FakeJitDriverStaticData(object):
vectorize=True
-class DepTestHelper(BaseTest):
+class VecTestHelper(BaseTest):
enable_opts =
"intbounds:rewrite:virtualize:string:earlyforce:pure:heap:unfold"
@@ -98,36 +98,7 @@
for i,op in enumerate(loop.operations):
print(i,op)
-class BaseTestDependencyGraph(DepTestHelper):
- def test_dependency_1(self):
- ops = """
- []
- i1 = int_add(1,1)
- i2 = int_add(i1,1)
- guard_value(i2,3) []
- jump()
- """
- dep_graph = self.build_dependency(ops)
- self.assert_no_edge(dep_graph, [(i,i) for i in range(5)])
- self.assert_def_use(dep_graph, [(1,2),(2,3)])
- self.assert_no_edge(dep_graph, [(0,1), (1,3),
- (0,2), (0,3),
- (0,4), (1,3),
- (2,4), (3,4)
- ])
-
- def test_label_def_use_jump_use_def(self):
- ops = """
- [i3]
- i1 = int_add(i3,1)
- guard_value(i1,0) []
- jump(i1)
- """
- dep_graph = self.build_dependency(ops)
- self.assert_no_edge(dep_graph, [(i,i) for i in range(4)])
- self.assert_def_use(dep_graph, 0, 1)
- self.assert_def_use(dep_graph, 1, 2)
- self.assert_def_use(dep_graph, 1, 3)
+class BaseTestVectorize(VecTestHelper):
def test_vectorize_skip_impossible_1(self):
""" this trace does not contain a raw load / raw store from an array
"""
@@ -544,5 +515,5 @@
self.assert_equal(loop, self.parse_loop(ops))
-class TestLLtype(BaseTestDependencyGraph, LLtypeMixin):
+class TestLLtype(BaseTestVectorize, LLtypeMixin):
pass
diff --git a/rpython/jit/metainterp/optimizeopt/test/test_virtualstate.py
b/rpython/jit/metainterp/optimizeopt/test/test_virtualstate.py
--- a/rpython/jit/metainterp/optimizeopt/test/test_virtualstate.py
+++ b/rpython/jit/metainterp/optimizeopt/test/test_virtualstate.py
@@ -791,7 +791,9 @@
if hasattr(self, 'callinfocollection'):
metainterp_sd.callinfocollection = self.callinfocollection
#
- optimize_trace(metainterp_sd, None, bridge, self.enable_opts)
+ class FakeJitDriverSD(object):
+ vectorize = False
+ optimize_trace(metainterp_sd, FakeJitDriverSD(), bridge,
self.enable_opts)
def optimize_bridge(self, loops, bridge, expected, expected_target='Loop',
**boxvalues):
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
