Author: Richard Plangger <r...@pasra.at> Branch: vecopt2 Changeset: r77089:11954a265325 Date: 2015-03-25 10:20 +0100 http://bitbucket.org/pypy/pypy/changeset/11954a265325/
Log: impl. follow def use chain. packset is extended by independent follow up instructions that reuse the definition 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 @@ -91,13 +91,32 @@ for i,op in enumerate(loop.operations): print(i,op) + def assert_packset_empty(self, packset, instr_count, exceptions): + + for a,b in exceptions: + self.assert_packset_contains(packset, a, b) + import itertools + combintations = set(itertools.product(range(instr_count), + range(instr_count))) + combintations -= set([(5,10),(4,9)]) + for a,b in combintations: + self.assert_packset_not_contains(packset, a, b) + + def assert_packset_not_contains(self, packset, x, y): + for pack in packset.packs: + if pack.left.opidx == x and \ + pack.right.opidx == y: + pytest.fail("must not find packset with indices {x},{y}" \ + .format(x=x,y=y)) + def assert_packset_contains(self, packset, x, y): for pack in packset.packs: - if pack.left.op_idx == x and \ - pack.right.op_idx == y: + if pack.left.opidx == x and \ + pack.right.opidx == y: break else: - pytest.fail("must find a pack set for {x},{y}".format(x=x,y=y)) + pytest.fail("can't find a pack set for indices {x},{y}" \ + .format(x=x,y=y)) def assert_edges(self, graph, edge_list): """ Check if all dependencies are met. for complex cases @@ -645,28 +664,29 @@ assert isomorphic(ops[1], ops[4]) assert not isomorphic(ops[0], ops[1]) assert not isomorphic(ops[0], ops[5]) - assert not isomorphic(ops[4], ops[5]) - assert not isomorphic(ops[5], ops[6]) - assert not isomorphic(ops[4], ops[6]) - assert not isomorphic(ops[1], ops[6]) + # TODO strong assumptions do hold here? + #assert not isomorphic(ops[4], ops[5]) + #assert not isomorphic(ops[5], ops[6]) + #assert not isomorphic(ops[4], ops[6]) + #assert not isomorphic(ops[1], ops[6]) def test_packset_extend_simple(self): ops = """ - [p0,i0,i10] + [p0,i0] i1 = int_add(i0, 1) i2 = int_le(i1, 16) guard_true(i2) [p0, i0] i3 = getarrayitem_gc(p0, i1, descr=chararraydescr) - i4 = int_add(i10, i3) - jump(p0,i1, i4) + i4 = int_add(i3, 1) + jump(p0,i1) """ loop = self.parse_loop(ops) vopt = self.extend_pack_set(loop,1) assert len(vopt.vec_info.memory_refs) == 2 + assert vopt.dependency_graph.independant(5,10) == True assert len(vopt.pack_set.packs) == 2 - assert vopt.dependency_graph.independant(5,10) - self.assert_packset_contains(vopt.pack_set, 5, 10) - + self.assert_packset_empty(vopt.pack_set, len(loop.operations), + [(5,10), (4,9)]) 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 @@ -223,15 +223,32 @@ # that point forward: if a_opidx < b_opidx: if a_memref.is_adjacent_to(b_memref): - if self.pack_set.can_be_packed(a_memref, b_memref): - self.pack_set.packs.append(Pair(a_memref, b_memref)) + if self.pack_set.can_be_packed(a_opidx, b_opidx): + self.pack_set.add_pair(a_opidx, b_opidx, + a_memref, b_memref) def extend_pack_set(self): for p in self.pack_set.packs: self.follow_def_uses(p) def follow_def_uses(self, pack): - pass + assert isinstance(pack, Pair) + savings = -1 + candidate = (-1,-1) + for luse in self.dependency_graph.get_uses(pack.left.opidx): + for ruse in self.dependency_graph.get_uses(pack.right.opidx): + luse_idx = luse.idx_to + ruse_idx = ruse.idx_to + if luse_idx != ruse_idx and \ + self.pack_set.can_be_packed(luse_idx, ruse_idx): + est_savings = self.pack_set.estimate_savings(luse_idx, + ruse_idx) + if est_savings > savings: + savings = est_savings + candidate = (luse_idx, ruse_idx) + + if savings >= 0: + self.pack_set.add_pair(*candidate) def isomorphic(l_op, r_op): """ Described in the paper ``Instruction-Isomorphism in Program Execution''. @@ -239,19 +256,21 @@ For now it must have the same instruction type, the array parameter must be equal, and it must be of the same type (both size in bytes and type of array). """ - if l_op.getopnum() == r_op.getopnum() and \ - l_op.getarg(0) == r_op.getarg(0): - l_d = l_op.getdescr() - r_d = r_op.getdescr() - if l_d is not None and r_d is not None: - if l_d.get_item_size_in_bytes() == r_d.get_item_size_in_bytes(): - if l_d.getflag() == r_d.getflag(): - return True - - elif l_d is None and r_d is None: - return True - - return False + if l_op.getopnum() == r_op.getopnum(): + return True + # the stronger counterpart. TODO which structural equivalence is + # needed here? + #if l_op.getopnum() == r_op.getopnum() and \ + # l_op.getarg(0) == r_op.getarg(0): + # l_d = l_op.getdescr() + # r_d = r_op.getdescr() + # if l_d is not None and r_d is not None: + # if l_d.get_item_size_in_bytes() == r_d.get_item_size_in_bytes(): + # if l_d.getflag() == r_d.getflag(): + # return True + # elif l_d is None and r_d is None: + # return True + #return False class PackSet(object): @@ -263,17 +282,31 @@ def pack_count(self): return len(self.packs) - def can_be_packed(self, lh_ref, rh_ref): - l_op = self.operations[lh_ref.op_idx] - r_op = self.operations[lh_ref.op_idx] + def add_pair(self, lidx, ridx, lmemref = None, rmemref = None): + l = PackOpWrapper(lidx, lmemref) + r = PackOpWrapper(ridx, rmemref) + self.packs.append(Pair(l,r)) + + def can_be_packed(self, lop_idx, rop_idx): + l_op = self.operations[lop_idx] + r_op = self.operations[rop_idx] if isomorphic(l_op, r_op): - if self.dependency_graph.independant(lh_ref.op_idx, rh_ref.op_idx): + if self.dependency_graph.independant(lop_idx, rop_idx): for pack in self.packs: - if pack.left == lh_ref or pack.right == rh_ref: + if pack.left.opidx == lop_idx or \ + pack.right.opidx == rop_idx: return False return True return False + def estimate_savings(self, lopidx, ropidx): + """ estimate the number of savings to add this pair. + Zero is the minimum value returned. This should take + into account the benefit of executing this instruction + as SIMD instruction. + """ + return 0 + class Pack(object): """ A pack is a set of n statements that are: @@ -287,8 +320,8 @@ class Pair(Pack): """ A special Pack object with only two statements. """ def __init__(self, left, right): - assert isinstance(left, MemoryRef) - assert isinstance(right, MemoryRef) + assert isinstance(left, PackOpWrapper) + assert isinstance(right, PackOpWrapper) self.left = left self.right = right Pack.__init__(self, [left, right]) @@ -298,9 +331,18 @@ return self.left == other.left and \ self.right == other.right +class PackOpWrapper(object): + def __init__(self, opidx, memref = None): + self.opidx = opidx + self.memref = memref + + def __eq__(self, other): + if isinstance(other, PackOpWrapper): + return self.opidx == other.opidx and self.memref == other.memref + return False + class MemoryRef(object): - def __init__(self, op_idx, array, origin, descr): - self.op_idx = op_idx + def __init__(self, array, origin, descr): self.array = array self.origin = origin self.descr = descr @@ -426,12 +468,10 @@ def update_memory_ref(self, memref): - #print("updating memory ref pre: ", memref) memref.constant = self.constant memref.coefficient_mul = self.coefficient_mul memref.coefficient_div = self.coefficient_div memref.origin = self.used_box - #print("updating memory ref post: ", memref) def default_operation(self, operation): pass @@ -454,7 +494,7 @@ if self.track_memory_refs: idx = len(self.optimizer._newoperations)-1 self.memory_refs[idx] = \ - MemoryRef(idx, op.getarg(0), op.getarg(1), op.getdescr()) + 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 \ _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit