Author: Richard Plangger <r...@pasra.at>
Branch: vecopt2
Changeset: r77085:4848cc630ada
Date: 2015-03-23 15:58 +0100
http://bitbucket.org/pypy/pypy/changeset/4848cc630ada/
Log: added new dependency changes
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
@@ -1,28 +1,56 @@
from rpython.jit.metainterp.resoperation import rop
+from rpython.jit.codewriter.effectinfo import EffectInfo
+from rpython.jit.metainterp.history import BoxPtr, ConstPtr, ConstInt, BoxInt
+from rpython.rtyper.lltypesystem import llmemory
+from rpython.rlib.unroll import unrolling_iterable
+
+MODIFY_COMPLEX_OBJ = [ (rop.SETARRAYITEM_GC, 0)
+ , (rop.SETARRAYITEM_RAW, 0)
+ , (rop.RAW_STORE, 0)
+ , (rop.SETINTERIORFIELD_GC, 0)
+ , (rop.SETINTERIORFIELD_RAW, 0)
+ , (rop.SETFIELD_GC, 0)
+ , (rop.SETFIELD_RAW, 0)
+ , (rop.ZERO_PTR_FIELD, 0)
+ , (rop.ZERO_PTR_FIELD, 0)
+ , (rop.ZERO_ARRAY, 0)
+ , (rop.STRSETITEM, 0)
+ , (rop.UNICODESETITEM, 0)
+ ]
class Dependency(object):
- def __init__(self, idx_from, idx_to, arg, is_definition):
- self.defined_arg = arg
+ def __init__(self, idx_from, idx_to, arg):
+ assert idx_from != idx_to
+ self.args = []
+ if arg is not None:
+ self.args.append(arg)
+
self.idx_from = idx_from
self.idx_to = idx_to
- self.is_definition = is_definition
+
+ def adjust_dep_after_swap(self, idx_old, idx_new):
+ if self.idx_from == idx_old:
+ self.idx_from = idx_new
+ elif self.idx_to == idx_old:
+ self.idx_to = idx_new
def __repr__(self):
- return 'Dep(trace[%d] -> trace[%d], arg: %s, def-use? %d)' \
- % (self.idx_from, self.idx_to, self.defined_arg, \
- self.is_definition)
+ return 'Dep(trace[%d] -> trace[%d], arg: %s)' \
+ % (self.idx_from, self.idx_to, self.args)
class DependencyGraph(object):
""" A graph that represents one of the following dependencies:
* True dependency
- * Anti dependency
- * Ouput dependency
+ * Anti dependency (not present in SSA traces)
+ * Ouput dependency (not present in SSA traces)
Representation is an adjacent list. The number of edges between the
vertices is expected to be small.
+ Note that adjacent lists order their dependencies. They are ordered
+ by the target instruction they point to if the instruction is
+ a dependency.
"""
- def __init__(self, trace):
- self.trace = trace
- self.operations = self.trace.operations
+ def __init__(self, operations):
+ self.operations = operations
self.adjacent_list = [ [] for i in range(len(self.operations)) ]
self.build_dependencies(self.operations)
@@ -65,32 +93,119 @@
idx = defining_indices[arg]
self._put_edge(idx, i, arg)
+ # a trace has store operations on complex operations
+ # (e.g. setarrayitem). in general only once cell is updated,
+ # and in theroy it could be tracked but for simplicity, the
+ # whole is marked as redefined, thus any later usage sees
+ # only this definition.
+ self._redefine_if_complex_obj_is_modified(op, i, defining_indices)
+ if op.is_guard() and i > 0:
+ self._guard_dependency(op, i, operations, defining_indices)
+
+ def _redefine_if_complex_obj_is_modified(self, op, index,
defining_indices):
+ if not op.has_no_side_effect():
+ for arg in self._destroyed_arguments(op):
+ try:
+ # put an edge from the definition and all later uses until
this
+ # instruction to this instruction
+ def_idx = defining_indices[arg]
+ for dep in self.instr_dependencies(def_idx):
+ if dep.idx_to >= index:
+ break
+ self._put_edge(dep.idx_to, index, arg)
+ self._put_edge(def_idx, index, arg)
+ except KeyError:
+ pass
+
+ def _destroyed_arguments(self, op):
+ # conservative, if an item in array p0 is modified or a call
+ # contains a boxptr parameter, it is assumed that this is a
+ # new definition.
+ args = []
+ if op.is_call() and op.getopnum() != rop.CALL_ASSEMBLER:
+ # free destroys an argument -> connect all uses & def with it
+ descr = op.getdescr()
+ extrainfo = descr.get_extra_info()
+ if extrainfo.oopspecindex == EffectInfo.OS_RAW_FREE:
+ args.append(op.getarg(1))
+ else:
+ for opnum, i in unrolling_iterable(MODIFY_COMPLEX_OBJ):
+ if op.getopnum() == opnum:
+ arg = op.getarg(i)
+ args.append(arg)
+ return args
+
+ def _guard_dependency(self, op, i, operations, defining_indices):
+ # respect a guard after a statement that can raise!
+ assert i > 0
+
+ j = i-1
+ while j > 0:
+ prev_op = operations[j]
+ if prev_op.is_guard():
+ j -= 1
+ else:
+ break
+ prev_op = operations[j]
+
+ if op.is_guard_exception() and prev_op.can_raise():
+ self._inhert_all_dependencies(operations, j, i)
+ # respect an overflow guard after an ovf statement!
+ if op.is_guard_overflow() and prev_op.is_ovf():
+ self._inhert_all_dependencies(operations, j, i)
+ if op.getopnum() == rop.GUARD_NOT_FORCED and prev_op.can_raise():
+ self._inhert_all_dependencies(operations, j, i)
+ if op.getopnum() == rop.GUARD_NOT_FORCED_2 and prev_op.can_raise():
+ self._inhert_all_dependencies(operations, j, i)
+
+ def _inhert_all_dependencies(self, operations, op_idx, from_idx):
+ assert op_idx < from_idx
+ for dep in self.instr_dependencies(from_idx):
+ for dep in self.instr_dependencies(dep.idx_from):
+ if dep.idx_to >= op_idx:
+ break
+ self._put_edge(dep.idx_to, op_idx, None)
+ if dep.idx_from < op_idx:
+ self._put_edge(dep.idx_from, op_idx, None)
+ self._put_edge(op_idx, from_idx, None)
+
def _put_edge(self, idx_from, idx_to, arg):
- 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))
+ assert idx_from != idx_to
+ print("puttin", idx_from, idx_to)
+ dep = self.instr_dependency(idx_from, idx_to)
+ if dep is None:
+ dep = Dependency(idx_from, idx_to, arg)
+ self.adjacent_list[idx_from].append(dep)
+ self.adjacent_list[idx_to].append(dep)
+ else:
+ if arg not in dep.args:
+ dep.args.append(arg)
- 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)
- ...
+ def get_uses(self, idx):
+ deps = []
+ for dep in self.adjacent_list[idx]:
+ if idx < dep.idx_to:
+ deps.append(dep)
+ return deps
- 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 get_defs(self, idx):
+ deps = []
+ for dep in self.adjacent_list[idx]:
+ if idx > dep.idx_from:
+ deps.append(dep)
+ return deps
def instr_dependencies(self, idx):
edges = self.adjacent_list[idx]
return edges
+ def definition_dependencies(self, idx):
+ deps = []
+ for dep in self.adjacent_list[idx]:
+ for dep_def in self.adjacent_list[dep.idx_from]:
+ deps.append(dep_def)
+ return deps
+
def instr_dependency(self, from_instr_idx, to_instr_idx):
""" Does there exist a dependency from the instruction to another?
Returns None if there is no dependency or the Dependency object in
@@ -101,3 +216,25 @@
return edge
return None
+ def __repr__(self):
+ graph = "graph([\n"
+
+ for l in self.adjacent_list:
+ graph += " " + str([d.idx_to for d in l]) + "\n"
+
+ return graph + " ])"
+
+ def swap_instructions(self, ia, ib):
+ depa = self.adjacent_list[ia]
+ depb = self.adjacent_list[ib]
+
+ for d in depa:
+ d.adjust_dep_after_swap(ia, ib)
+
+ for d in depb:
+ d.adjust_dep_after_swap(ib, ia)
+
+ self.adjacent_list[ia] = depb
+ self.adjacent_list[ib] = depa
+
+
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
@@ -8,11 +8,9 @@
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)
+ return DependencyGraph(loop.operations)
def parse_loop(self, ops):
loop = self.parse(ops, postprocess=self.postprocess)
@@ -23,27 +21,6 @@
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.
@@ -53,17 +30,29 @@
for idx,edges in enumerate(edge_list):
if edges is None:
continue
- dependencies = graph.adjacent_list[idx]
+ dependencies = graph.adjacent_list[idx][:]
for edge in edges:
dependency = graph.instr_dependency(idx,edge)
+ if edge < idx:
+ dependency = graph.instr_dependency(edge, idx)
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)
+ " %d depends on instr on index %d but it does not.\n%s" \
+ % (idx, edge, graph)
dependencies.remove(dependency)
assert dependencies == [], \
- "dependencies unexpected %s" \
- % dependencies
+ "dependencies unexpected %s.\n%s" \
+ % (dependencies,graph)
+ def assert_graph_equal(self, ga, gb):
+ assert len(ga.adjacent_list) == len(gb.adjacent_list)
+ for i in range(len(ga.adjacent_list)):
+ la = ga.adjacent_list[i]
+ lb = gb.adjacent_list[i]
+ assert len(la) == len(lb)
+ assert sorted([l.idx_to for l in la]) == \
+ sorted([l.idx_to for l in lb])
+ assert sorted([l.idx_from for l in la]) == \
+ sorted([l.idx_from for l in lb])
class BaseTestDependencyGraph(DepTestHelper):
def test_dependency_empty(self):
@@ -140,5 +129,111 @@
self.assert_dependant(dep_graph,
[ [1,2,3], [0,2], [1,0], [0] ])
+ def test_swap_dependencies(self):
+ ops = """
+ [i1,i4] # 0
+ i2 = int_lt(i1,0) # 1
+ i3 = int_lt(i4,0) # 2
+ guard_value(i2,0) [] # 3
+ jump(i1,i3) # 4
+ """
+ dep_graph = self.build_dependency(ops)
+ dep_graph.swap_instructions(1,2)
+ self.assert_dependant(dep_graph,
+ [ [1,2,4], [4,0], [3,0], [2], [0,1] ])
+ dep_graph.swap_instructions(1,2)
+ self.assert_graph_equal(dep_graph, self.build_dependency(ops))
+
+ dep_graph.swap_instructions(2,3)
+ ops2 = """
+ [i1,i4] # 0
+ i2 = int_lt(i1,0) # 1
+ guard_value(i2,0) [] # 2
+ i3 = int_lt(i4,0) # 3
+ jump(i1,i3) # 4
+ """
+ dep_graph_final = self.build_dependency(ops2)
+ self.assert_graph_equal(dep_graph, dep_graph_final)
+
+ def test_dependencies_1(self):
+ ops="""
+ [i0, i1, i2] # 0
+ i4 = int_gt(i1, 0) # 1
+ guard_true(i4) [] # 2
+ i6 = int_sub(i1, 1) # 3
+ i8 = int_gt(i6, 0) # 4
+ guard_false(i8) [] # 5
+ i10 = int_add(i2, 1) # 6
+ i12 = int_sub(i0, 1) # 7
+ i14 = int_add(i10, 1) # 8
+ i16 = int_gt(i12, 0) # 9
+ guard_true(i16) [] # 10
+ jump(i12, i1, i14) # 11
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [1,3,6,7,11], [0,2], [1], [0,4], [3,5], [4],
+ # next entry is instr 6
+ [0,8], [0,9,11], [6,11], [7,10], [9], [7,0,8] ])
+
+ def test_prevent_double_arg(self):
+ ops="""
+ [i0, i1, i2]
+ i4 = int_gt(i1, i0)
+ guard_true(i4) []
+ jump(i0, i1, i2)
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [1,3], [0,2], [1], [0] ])
+
+ def test_ovf_dep(self):
+ ops="""
+ [i0, i1, i2]
+ i4 = int_sub_ovf(1, 0)
+ guard_overflow() [i2]
+ jump(i0, i1, i2)
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [1,2,3], [0,2], [0,1], [0] ])
+
+ def test_exception_dep(self):
+ ops="""
+ [p0, i1, i2]
+ i4 = call(p0, 1, descr=nonwritedescr)
+ guard_no_exception() []
+ jump(p0, i1, i2)
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [1,3], [0,2], [1], [0] ])
+
+ def test_call_dependency_on_ptr_but_not_index_value(self):
+ ops="""
+ [p0, p1, i2]
+ i3 = int_add(i2,1)
+ i4 = call(p0, i3, descr=nonwritedescr)
+ guard_no_exception() [i2]
+ p2 = getarrayitem_gc(p1,i3)
+ jump(p2, p1, i3)
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [1,2,3,4,5], [0,2,4,5], [0,1,3], [0,2], [0,1,5], [4,0,1] ])
+
+ def test_call_dependency(self):
+ ops="""
+ [p0, p1, i2, i5]
+ i3 = int_add(i2,1)
+ i4 = call(i5, i3, descr=nonwritedescr)
+ guard_no_exception() [i2]
+ p2 = getarrayitem_gc(p1,i3)
+ jump(p2, p1, i3)
+ """
+ dep_graph = self.build_dependency(ops)
+ self.assert_dependant(dep_graph,
+ [ [1,2,3,4,5], [0,2,4,5], [0,1,3], [0,2], [0,1,5], [4,0,1] ])
+
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
@@ -58,32 +58,18 @@
opt.loop.operations = opt.get_newoperations()
return opt
+ def init_pack_set(self, loop, unroll_factor = -1):
+ opt = self.vec_optimizer_unrolled(loop, unroll_factor)
+ opt.build_dependency_graph()
+ opt.find_adjacent_memory_refs()
+ opt.initialize_pack_set()
+ return opt
+
def assert_unroll_loop_equals(self, loop, expected_loop, \
unroll_factor = -1):
vec_optimizer = self.vec_optimizer_unrolled(loop, unroll_factor)
self.assert_equal(loop, expected_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_memory_ref_adjacent(self, m1, m2):
assert m1.is_adjacent_to(m2)
@@ -98,6 +84,29 @@
for i,op in enumerate(loop.operations):
print(i,op)
+ 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)
+ if edge < idx:
+ dependency = graph.instr_dependency(edge, idx)
+ assert dependency is not None, \
+ " it is expected that instruction at index" + \
+ " %d depends on instr on index %d but it does not.\n%s" \
+ % (idx, edge, graph)
+ dependencies.remove(dependency)
+ assert dependencies == [], \
+ "dependencies unexpected %s.\n%s" \
+ % (dependencies,graph)
+
class BaseTestVectorize(VecTestHelper):
def test_vectorize_skip_impossible_1(self):
@@ -246,9 +255,8 @@
"""
vopt = self.vec_optimizer_unrolled(self.parse_loop(ops),1)
vopt.build_dependency_graph()
- self.assert_no_edge(vopt.dependency_graph, [(i,i) for i in range(6)])
- self.assert_def_use(vopt.dependency_graph, [(0,1),(2,3),(4,5)])
- self.assert_no_edge(vopt.dependency_graph, [(0,4),(0,0)])
+ self.assert_dependant(vopt.dependency_graph,
+ [ [1,2,3,5], [0], [0,3,4], [0,2], [2,5], [0,4] ])
vopt.find_adjacent_memory_refs()
assert 1 in vopt.vec_info.memory_refs
@@ -514,6 +522,20 @@
vopt = self.vec_optimizer_unrolled(loop,1)
self.assert_equal(loop, self.parse_loop(ops))
+ def test_packset_init_simple(self):
+ ops = """
+ [p0,i0]
+ i3 = getarrayitem_gc(p0, i0, descr=chararraydescr)
+ i1 = int_add(i0, 1)
+ i2 = int_le(i1, 16)
+ guard_true(i2) [p0, i0]
+ jump(p0,i1)
+ """
+ loop = self.parse_loop(ops)
+ vopt = self.init_pack_set(loop,2)
+ assert vopt.pack_set is not None
+
+
class TestLLtype(BaseTestVectorize, 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
@@ -35,6 +35,7 @@
self.dependency_graph = None
self.first_debug_merge_point = False
self.last_debug_merge_point = None
+ self.pack_set = None
def emit_unrolled_operation(self, op):
if op.getopnum() == rop.DEBUG_MERGE_POINT:
@@ -189,13 +190,15 @@
self.find_adjacent_memory_refs()
def build_dependency_graph(self):
- self.dependency_graph = DependencyGraph(self.loop)
+ self.dependency_graph = DependencyGraph(self.loop.operations)
def find_adjacent_memory_refs(self):
""" the pre pass already builds a hash of memory references and the
- operations. Since it is in SSA form there is no array index. Indices
- are flattend. If there are two array accesses in the unrolled loop
- i0,i1 and i1 = int_add(i0,c), then i0 = i0 + 0, i1 = i0 + 1 """
+ operations. Since it is in SSA form there are no array indices.
+ If there are two array accesses in the unrolled loop
+ i0,i1 and i1 = int_add(i0,c), then i0 = i0 + 0, i1 = i0 + 1.
+ They are represented as a linear combination: i*c/d + e, i is a
variable,
+ all others are integers that are calculated in reverse direction"""
loop = self.loop
operations = loop.operations
integral_mod = IntegralMod(self)
@@ -206,7 +209,8 @@
for dep in self.dependency_graph.instr_dependencies(opidx):
# this is a use, thus if dep is not a defintion
# it points back to the definition
- if memref.origin == dep.defined_arg and not
dep.is_definition:
+ # if memref.origin == dep.defined_arg and not
dep.is_definition:
+ if memref.origin in dep.args and not dep.is_definition:
# if is_definition is false the params is swapped
# idx_to attributes points to definer
def_op = operations[dep.idx_to]
@@ -227,6 +231,9 @@
else:
break
+ def init_pack_set(self):
+ self.pack_set = PackSet()
+
def vectorize_trace(self, loop):
""" Implementation of the algorithm introduced by Larsen. Refer to
'''Exploiting Superword Level Parallelism
@@ -382,6 +389,9 @@
default=LoopVectorizeInfo.default_operation)
LoopVectorizeInfo.inspect_operation = dispatch_opt
+class PackSet(object):
+ pass
+
class Pack(object):
""" A pack is a set of n statements that are:
* isomorphic
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
