Author: Richard Plangger <r...@pasra.at> Branch: vecopt2 Changeset: r77075:b794697698a8 Date: 2015-03-12 15:35 +0100 http://bitbucket.org/pypy/pypy/changeset/b794697698a8/
Log: impl & test memory adjacent 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 @@ -2,16 +2,14 @@ from rpython.jit.metainterp.resoperation import rop class Dependency(object): - def __init__(self, ifrom, ito, is_definition): - self.ifrom = ifrom - self.ito = ito + def __init__(self, idx_from, idx_to, arg, is_definition): + self.defined_arg = arg + self.idx_from = idx_from + self.idx_to = idx_to self.is_definition = is_definition def __repr__(self): - return 'dep(%d,%d)' % (self.ifrom, self.ito) - -class CrossIterationDependency(Dependency): - pass + return 'dep(%d -> %d, defines? %d)' % (self.idx_from, self.idx_to, self.is_definition) class DependencyGraph(object): """ A graph that represents one of the following dependencies: @@ -57,20 +55,23 @@ for arg in op.getarglist(): if arg in defining_indices: idx = defining_indices[arg] - self._put_edge(idx, i) + self._put_edge(idx, i, arg) - def _put_edge(self, idx_from, idx_to): - self.adjacent_list[idx_from].append(Dependency(idx_from, idx_to, True)) - self.adjacent_list[idx_to].append(Dependency(idx_to, idx_from, False)) + 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)) + + def instr_dependencies(self, idx): + edges = self.adjacent_list[idx] + return edges 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 any other case. """ - edges = self.adjacent_list[from_instr_idx] - for edge in edges: - if edge.ito == to_instr_idx: + for edge in self.instr_dependencies(from_instr_idx): + if edge.idx_to == to_instr_idx: return edge return None 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 @@ -83,6 +83,14 @@ " %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) + assert m2.is_adjacent_to(m1) + + def assert_memory_ref_not_adjacent(self, m1, m2): + assert not m1.is_adjacent_to(m2) + assert not m2.is_adjacent_to(m1) + class BaseTestDependencyGraph(DepTestHelper): def test_dependency_1(self): ops = """ @@ -259,7 +267,14 @@ jump(p0,i1) """ vopt = self.vec_optimizer_unrolled(self.parse_loop(ops),2) + print() + for i,op in enumerate(vopt.optimizer.loop.operations): + print(i,op) 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)]) + vopt.find_adjacent_memory_refs() assert 1 in vopt.vec_info.memory_refs assert 3 in vopt.vec_info.memory_refs @@ -270,12 +285,44 @@ assert isinstance(mref1, MemoryRef) assert isinstance(mref3, MemoryRef) - 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)]) - assert mref1.is_adjacent_to(mref3) assert mref3.is_adjacent_to(mref1) + def test_array_memory_ref_not_adjacent_1(self): + ops = """ + [p0,i0,i4] + i3 = raw_load(p0,i0,descr=chararraydescr) + i1 = int_add(i0,1) + i5 = raw_load(p0,i4,descr=chararraydescr) + i6 = int_add(i4,1) + jump(p0,i1,i6) + """ + vopt = self.vec_optimizer_unrolled(self.parse_loop(ops),2) + 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),(0,2),(0,3),(0,4),(2,5)]) + self.assert_no_edge(vopt.dependency_graph, [(1,3),(2,4)]) + + vopt.find_adjacent_memory_refs() + + for i in [1,3,5,7]: + assert i in vopt.vec_info.memory_refs + assert len(vopt.vec_info.memory_refs) == 4 + + mref1 = vopt.vec_info.memory_refs[1] + mref3 = vopt.vec_info.memory_refs[3] + mref5 = vopt.vec_info.memory_refs[5] + mref7 = vopt.vec_info.memory_refs[7] + assert isinstance(mref1, MemoryRef) + assert isinstance(mref3, MemoryRef) + assert isinstance(mref5, MemoryRef) + assert isinstance(mref7, MemoryRef) + + self.assert_memory_ref_adjacent(mref1, mref5) + self.assert_memory_ref_not_adjacent(mref1, mref3) + self.assert_memory_ref_not_adjacent(mref1, mref7) + self.assert_memory_ref_adjacent(mref3, mref7) + + 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 @@ -7,11 +7,17 @@ from rpython.jit.metainterp.resoperation import rop from rpython.jit.metainterp.resume import Snapshot from rpython.rlib.debug import debug_print, debug_start, debug_stop +from rpython.jit.metainterp.jitexc import JitException + +class NotAVectorizeableLoop(JitException): + def __str__(self): + return 'NotAVectorizeableLoop()' def optimize_vector(metainterp_sd, jitdriver_sd, loop, optimizations): opt = OptVectorize(metainterp_sd, jitdriver_sd, loop, optimizations) - opt_loop = opt.propagate_all_forward() - if not opt.vectorized: + try: + opt.propagate_all_forward() + except NotAVectorizeableLoop: # vectorization is not possible, propagate only normal optimizations def_opt = Optimizer(metainterp_sd, jitdriver_sd, loop, optimizations) def_opt.propagate_all_forward() @@ -28,7 +34,6 @@ loop, optimizations) self.vec_info = LoopVectorizeInfo() self.memory_refs = [] - self.vectorized = False self.dependency_graph = None def _rename_arguments_ssa(self, rename_map, label_args, jump_args): @@ -135,7 +140,7 @@ byte_count = self.vec_info.smallest_type_bytes if byte_count == 0: # stop, there is no chance to vectorize this trace - return loop + raise NotAVectorizeableLoop() unroll_factor = self.get_estimated_unroll_factor() @@ -143,8 +148,6 @@ self.build_dependencies() - self.vectorized = True - def build_dependency_graph(self): self.dependency_graph = DependencyGraph(self.optimizer, self.optimizer.loop) @@ -154,9 +157,40 @@ 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 """ - considered_vars = [] + loop = self.optimizer.loop + operations = loop.operations + integral_mod = IntegralMod(self.optimizer) for opidx,memref in self.vec_info.memory_refs.items(): - considered_vars.append(memref.origin) + print("trying ref", memref, "op idx", opidx) + while True: + op = operations[opidx] + if op.getopnum() == rop.LABEL: + break + + print("checking op at idx", opidx) + 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 + print(memref.origin, " == ", dep.defined_arg) + if memref.origin == dep.defined_arg 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] + opidx = dep.idx_to + break + else: + # this is an error in the dependency graph + raise RuntimeError("a variable usage does not have a " + + " definition. Cannot continue!") + + print("reset") + integral_mod.reset() + print("inspect ", def_op) + integral_mod.inspect_operation(def_op) + if integral_mod.is_const_mod: + integral_mod.update_memory_ref(memref) + else: + break def vectorize_trace(self, loop): """ Implementation of the algorithm introduced by Larsen. Refer to @@ -175,6 +209,51 @@ # was not able to vectorize return False +class IntegralMod(object): + + def __init__(self, optimizer): + self.optimizer = optimizer + self.reset() + + def reset(self): + self.is_const_mod = False + self.factor_c = 1 + self.factor_d = 0 + self.used_box = None + + def operation_INT_ADD(self, op): + print("int_add") + box_a0 = op.getarg(0) + box_a1 = op.getarg(1) + a0 = self.optimizer.getvalue(box_a0) + a1 = self.optimizer.getvalue(box_a1) + if a0.is_constant() and a1.is_constant(): + # this means that the overall array offset is not + # added to a variable, but is constant + self.is_const_mod = True + self.factor_d += box_a1.getint() + box_a0.getint() + self.used_box = None + elif a0.is_constant(): + self.is_const_mod = True + self.factor_d += box_a0.getint() + self.used_box = box_a1 + elif a1.is_constant(): + self.is_const_mod = True + self.factor_d += box_a1.getint() + self.used_box = box_a0 + + def update_memory_ref(self, memref): + memref.factor_d = self.factor_d + memref.factor_c = self.factor_c + memref.origin = self.used_box + print("update", memref.factor_d, memref.factor_c, memref.origin) + + def default_operation(self, operation): + pass +integral_dispatch_opt = make_dispatcher_method(IntegralMod, 'operation_', + default=IntegralMod.default_operation) +IntegralMod.inspect_operation = integral_dispatch_opt + class LoopVectorizeInfo(object): def __init__(self): @@ -183,13 +262,10 @@ self.memory_refs = {} self.label_op = None - def operation_LABEL(self, op): - self.label = op - def operation_RAW_LOAD(self, op): descr = op.getdescr() self.memory_refs[self._op_index] = \ - MemoryRef(op.getarg(0), op.getarg(1)) + MemoryRef(op.getarg(0), op.getarg(1), op.getdescr()) if not descr.is_array_of_pointers(): byte_count = descr.get_item_size_in_bytes() if self.smallest_type_bytes == 0 \ @@ -222,16 +298,22 @@ class MemoryRef(object): - def __init__(self, array, origin): + def __init__(self, array, origin, descr): self.array = array self.origin = origin - self.offset = None + self.descr = descr + self.factor_c = 1 + self.factor_d = 0 - def is_adjacent_to(self, mem_acc): + def is_adjacent_to(self, other): """ this is a symmetric relation """ + if self.array == other.array \ + and self.origin == other.origin: + my_off = (self.factor_c * self.factor_d) + other_off = (other.factor_c * other.factor_d) + diff = my_off - other_off + return diff == 1 or diff == -1 return False - if self.array == mem_acc.array: - # TODO - return self.offset == mem_acc.offset - + def __repr__(self): + return 'MemoryRef(%s,%s,%s)' % (self.origin, self.factor_c, self.factor_d) _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit