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