Author: Richard Plangger <r...@pasra.at> Branch: vecopt2 Changeset: r77095:c675e35448fb Date: 2015-03-27 11:34 +0100 http://bitbucket.org/pypy/pypy/changeset/c675e35448fb/
Log: packset combination (need to rewrite for rpython) and tests 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 @@ -289,10 +289,11 @@ dep_graph = self.build_dependency(ops) self.assert_edges(dep_graph, [ [1,2,3], [0,2], [0,1,3], [0,2] ]) + self.assert_dependent(1,2) + self.assert_dependent(0,3) def test_setarrayitem_same_modified_var_not_aliased(self): - # #1 depends on #2, i1 and i2 might alias, reordering would destroy - # coorectness + # #1 does NOT depend on #2, i1 and i2 are not aliased ops=""" [p0, i1] setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) #1 @@ -303,9 +304,13 @@ dep_graph = self.build_dependency(ops, True) self.assert_edges(dep_graph, [ [1,2,3,4], [0], [0,3], [0,2,4], [0,3] ]) + self.assert_independent(1,2) + self.assert_independent(1,3) dep_graph = self.build_dependency(ops) self.assert_edges(dep_graph, [ [1,2,4], [0,3], [0,3], [1,2,4], [0,3] ]) + self.assert_independent(1,2) + self.assert_dependent(1,3) 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 @@ -10,7 +10,8 @@ import rpython.jit.metainterp.optimizeopt.virtualize as virtualize from rpython.jit.metainterp.optimizeopt.dependency import DependencyGraph from rpython.jit.metainterp.optimizeopt.unroll import Inliner -from rpython.jit.metainterp.optimizeopt.vectorize import VectorizingOptimizer, MemoryRef, isomorphic +from rpython.jit.metainterp.optimizeopt.vectorize import (VectorizingOptimizer, MemoryRef, + isomorphic, Pair) from rpython.jit.metainterp.optimize import InvalidLoop from rpython.jit.metainterp.history import ConstInt, BoxInt, get_const_ptr_for_string from rpython.jit.metainterp import executor, compile, resume @@ -59,17 +60,25 @@ opt.loop.operations = opt.get_newoperations() return opt - def init_pack_set(self, loop, unroll_factor = -1): + def init_packset(self, loop, unroll_factor = -1): opt = self.vec_optimizer_unrolled(loop, unroll_factor) opt.build_dependency_graph() opt.find_adjacent_memory_refs() return opt - def extend_pack_set(self, loop, unroll_factor = -1): + def extend_packset(self, loop, unroll_factor = -1): opt = self.vec_optimizer_unrolled(loop, unroll_factor) opt.build_dependency_graph() opt.find_adjacent_memory_refs() - opt.extend_pack_set() + opt.extend_packset() + return opt + + def combine_packset(self, loop, unroll_factor = -1): + opt = self.vec_optimizer_unrolled(loop, unroll_factor) + opt.build_dependency_graph() + opt.find_adjacent_memory_refs() + opt.extend_packset() + opt.combine_packset() return opt def assert_unroll_loop_equals(self, loop, expected_loop, \ @@ -91,29 +100,34 @@ for i,op in enumerate(loop.operations): print(i,op) + def assert_pack(self, pack, indices): + assert len(pack.operations) == len(indices) + for op,i in zip(pack.operations, indices): + assert op.opidx == i + def assert_packset_empty(self, packset, instr_count, exceptions): - for a,b in exceptions: - self.assert_packset_contains(packset, a, b) + self.assert_packset_contains_pair(packset, a, b) import itertools combintations = set(itertools.product(range(instr_count), range(instr_count))) combintations -= set(exceptions) for a,b in combintations: - self.assert_packset_not_contains(packset, a, b) + self.assert_packset_not_contains_pair(packset, a, b) - def assert_packset_not_contains(self, packset, x, y): + def assert_packset_not_contains_pair(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): + def assert_packset_contains_pair(self, packset, x, y): for pack in packset.packs: - if pack.left.opidx == x and \ - pack.right.opidx == y: - break + if isinstance(pack, Pair): + if pack.left.opidx == x and \ + pack.right.opidx == y: + break else: pytest.fail("can't find a pack set for indices {x},{y}" \ .format(x=x,y=y)) @@ -582,11 +596,11 @@ jump(p0,i1) """ loop = self.parse_loop(ops) - vopt = self.init_pack_set(loop,1) + vopt = self.init_packset(loop,1) assert vopt.dependency_graph.independent(1,5) - assert vopt.pack_set is not None + assert vopt.packset is not None assert len(vopt.vec_info.memory_refs) == 2 - assert len(vopt.pack_set.packs) == 1 + assert len(vopt.packset.packs) == 1 def test_packset_init_raw_load_not_adjacent_and_adjacent(self): ops = """ @@ -595,9 +609,9 @@ jump(p0,i0) """ loop = self.parse_loop(ops) - vopt = self.init_pack_set(loop,3) + vopt = self.init_packset(loop,3) assert len(vopt.vec_info.memory_refs) == 4 - assert len(vopt.pack_set.packs) == 0 + assert len(vopt.packset.packs) == 0 ops = """ [p0,i0] i2 = int_add(i0,1) @@ -605,14 +619,14 @@ jump(p0,i2) """ loop = self.parse_loop(ops) - vopt = self.init_pack_set(loop,3) + vopt = self.init_packset(loop,3) assert len(vopt.vec_info.memory_refs) == 4 - assert len(vopt.pack_set.packs) == 3 + assert len(vopt.packset.packs) == 3 for i in range(3): x = (i+1)*2 y = x + 2 assert vopt.dependency_graph.independent(x,y) - self.assert_packset_contains(vopt.pack_set, x,y) + self.assert_packset_contains_pair(vopt.packset, x,y) def test_packset_init_2(self): ops = """ @@ -624,9 +638,9 @@ jump(p0,i1) """ loop = self.parse_loop(ops) - vopt = self.init_pack_set(loop,15) + vopt = self.init_packset(loop,15) assert len(vopt.vec_info.memory_refs) == 16 - assert len(vopt.pack_set.packs) == 15 + assert len(vopt.packset.packs) == 15 # assure that memory refs are not adjacent for all for i in range(15): for j in range(15): @@ -645,7 +659,7 @@ x = (i+1)*4 y = x + 4 assert vopt.dependency_graph.independent(x,y) - self.assert_packset_contains(vopt.pack_set, x, y) + self.assert_packset_contains_pair(vopt.packset, x, y) def test_isomorphic_operations(self): ops_src = """ @@ -681,12 +695,11 @@ jump(p0,i1) """ loop = self.parse_loop(ops) - vopt = self.extend_pack_set(loop,1) - self.debug_print_operations(loop) + vopt = self.extend_packset(loop,1) assert len(vopt.vec_info.memory_refs) == 2 assert vopt.dependency_graph.independent(5,10) == True - assert len(vopt.pack_set.packs) == 2 - self.assert_packset_empty(vopt.pack_set, len(loop.operations), + assert len(vopt.packset.packs) == 2 + self.assert_packset_empty(vopt.packset, len(loop.operations), [(5,10), (4,9)]) def test_packset_extend_load_modify_store(self): @@ -701,15 +714,76 @@ jump(p0,i1) """ loop = self.parse_loop(ops) - vopt = self.extend_pack_set(loop,1) - self.debug_print_operations(loop) + vopt = self.extend_packset(loop,1) assert len(vopt.vec_info.memory_refs) == 4 assert vopt.dependency_graph.independent(4,10) assert vopt.dependency_graph.independent(5,11) assert vopt.dependency_graph.independent(6,12) - assert len(vopt.pack_set.packs) == 3 - self.assert_packset_empty(vopt.pack_set, len(loop.operations), + assert len(vopt.packset.packs) == 3 + self.assert_packset_empty(vopt.packset, len(loop.operations), [(5,11), (4,10), (6,12)]) + def test_packset_combine_simple(self): + ops = """ + [p0,i0] + i3 = getarrayitem_gc(p0, i0, descr=floatarraydescr) + i1 = int_add(i0,1) + jump(p0,i1) + """ + loop = self.parse_loop(ops) + vopt = self.combine_packset(loop,3) + assert len(vopt.vec_info.memory_refs) == 4 + assert len(vopt.packset.packs) == 1 + self.assert_pack(vopt.packset.packs[0], (1,3,5,7)) + + def test_packset_combine_2_loads_in_trace(self): + ops = """ + [p0,i0] + i3 = getarrayitem_gc(p0, i0, descr=floatarraydescr) + i1 = int_add(i0,1) + i4 = getarrayitem_gc(p0, i1, descr=floatarraydescr) + i2 = int_add(i1,1) + jump(p0,i2) + """ + loop = self.parse_loop(ops) + vopt = self.combine_packset(loop,3) + assert len(vopt.vec_info.memory_refs) == 8 + assert len(vopt.packset.packs) == 1 + self.assert_pack(vopt.packset.packs[0], (1,3,5,7,9,11,13,15)) + + def test_packset_combine_2_loads_one_redundant(self): + ops = """ + [p0,i0] + i3 = getarrayitem_gc(p0, i0, descr=floatarraydescr) + i1 = int_add(i0,1) + i4 = getarrayitem_gc(p0, i1, descr=floatarraydescr) + jump(p0,i1) + """ + pytest.skip("loop unrolling must apply redundant loop unrolling") + loop = self.parse_loop(ops) + vopt = self.combine_packset(loop,3) + assert len(vopt.vec_info.memory_refs) == 4 + assert len(vopt.packset.packs) == 1 + self.assert_pack(vopt.packset.packs[0], (1,3,5,7)) + + def test_packset_combine_no_candidates_packset_empty(self): + ops = """ + [] + jump() + """ + vopt = self.combine_packset(self.parse_loop(ops),15) + assert len(vopt.vec_info.memory_refs) == 0 + assert len(vopt.packset.packs) == 0 + + ops = """ + [p0,i0] + i3 = getarrayitem_gc(p0, i0, descr=floatarraydescr) + jump(p0,i3) + """ + loop = self.parse_loop(ops) + vopt = self.combine_packset(loop,15) + assert len(vopt.vec_info.memory_refs) == 16 + assert len(vopt.packset.packs) == 0 + 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 @@ -36,7 +36,8 @@ self.dependency_graph = None self.first_debug_merge_point = False self.last_debug_merge_point = None - self.pack_set = None + self.packset = None + self.unroll_count = 0 def emit_unrolled_operation(self, op): if op.getopnum() == rop.DEBUG_MERGE_POINT: @@ -175,9 +176,9 @@ # stop, there is no chance to vectorize this trace raise NotAVectorizeableLoop() - unroll_count = self.get_unroll_count() + self.unroll_count = self.get_unroll_count() - self.unroll_loop_iterations(self.loop, unroll_count) + self.unroll_loop_iterations(self.loop, self.unroll_count) self.loop.operations = self.get_newoperations(); self.clear_newoperations(); @@ -199,7 +200,9 @@ loop = self.loop operations = loop.operations - self.pack_set = PackSet(self.dependency_graph, operations) + self.packset = PackSet(self.dependency_graph, operations, + self.unroll_count, + self.vec_info.smallest_type_bytes) memory_refs = self.vec_info.memory_refs.items() # initialize the pack set for a_opidx,a_memref in memory_refs: @@ -209,50 +212,76 @@ # that point forward: if a_opidx < b_opidx: if a_memref.is_adjacent_to(b_memref): - if self.pack_set.can_be_packed(a_opidx, b_opidx): - self.pack_set.add_pair(a_opidx, b_opidx, + if self.packset.can_be_packed(a_opidx, b_opidx, + a_memref, b_memref): + self.packset.add_pair(a_opidx, b_opidx, a_memref, b_memref) - def extend_pack_set(self): - pack_count = self.pack_set.pack_count() + def extend_packset(self): + pack_count = self.packset.pack_count() while True: - for pack in self.pack_set.packs: + for pack in self.packset.packs: self.follow_use_defs(pack) self.follow_def_uses(pack) - if pack_count == self.pack_set.pack_count(): + if pack_count == self.packset.pack_count(): break - pack_count = self.pack_set.pack_count() + pack_count = self.packset.pack_count() def follow_use_defs(self, pack): assert isinstance(pack, Pair) + lref = pack.left.memref + rref = pack.right.memref for ldef in self.dependency_graph.get_defs(pack.left.opidx): for rdef in self.dependency_graph.get_defs(pack.right.opidx): ldef_idx = ldef.idx_from rdef_idx = rdef.idx_from if ldef_idx != rdef_idx and \ - self.pack_set.can_be_packed(ldef_idx, rdef_idx): - savings = self.pack_set.estimate_savings(ldef_idx, rdef_idx) + self.packset.can_be_packed(ldef_idx, rdef_idx, lref, rref): + savings = self.packset.estimate_savings(ldef_idx, rdef_idx) if savings >= 0: - self.pack_set.add_pair(ldef_idx, rdef_idx) + self.packset.add_pair(ldef_idx, rdef_idx, lref, rref) def follow_def_uses(self, pack): assert isinstance(pack, Pair) savings = -1 - candidate = (-1,-1) + candidate = (-1,-1, None, None) + lref = pack.left.memref + rref = pack.right.memref 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, + self.packset.can_be_packed(luse_idx, ruse_idx, lref, rref): + est_savings = self.packset.estimate_savings(luse_idx, ruse_idx) if est_savings > savings: savings = est_savings - candidate = (luse_idx, ruse_idx) + candidate = (luse_idx, ruse_idx, lref, rref) + # + if savings >= 0: + self.packset.add_pair(*candidate) - if savings >= 0: - self.pack_set.add_pair(*candidate) + def combine_packset(self): + changed = False + while True: + changed = False + for i,pack1 in enumerate(self.packset.packs): + for j,pack2 in enumerate(self.packset.packs): + if i == j: + continue + if pack1.rightmost_match_leftmost(pack2): + self.packset.combine(i,j) + changed = True + break + if pack2.rightmost_match_leftmost(pack1): + self.packset.combine(j,i) + changed = True + break + if changed: + break + if not changed: + break def isomorphic(l_op, r_op): """ Described in the paper ``Instruction-Isomorphism in Program Execution''. @@ -278,20 +307,23 @@ class PackSet(object): - def __init__(self, dependency_graph, operations): + def __init__(self, dependency_graph, operations, unroll_count, + smallest_type_bytes): self.packs = [] self.dependency_graph = dependency_graph self.operations = operations + self.unroll_count = unroll_count + self.smallest_type_bytes = smallest_type_bytes def pack_count(self): return len(self.packs) - def add_pair(self, lidx, ridx, lmemref = None, rmemref = None): + 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): + def can_be_packed(self, lop_idx, rop_idx, lmemref, rmemref): l_op = self.operations[lop_idx] r_op = self.operations[rop_idx] if isomorphic(l_op, r_op): @@ -311,6 +343,15 @@ """ return 0 + def combine(self, i, j): + print "combine", i, j + pack_i = self.packs[i] + pack_j = self.packs[j] + operations = pack_i.operations + for op in pack_j.operations[1:]: + operations.append(op) + self.packs[i] = Pack(operations) + del self.packs[j] class Pack(object): """ A pack is a set of n statements that are: @@ -321,6 +362,15 @@ def __init__(self, ops): self.operations = ops + def rightmost_match_leftmost(self, other): + assert isinstance(other, Pack) + rightmost = self.operations[-1] + leftmost = other.operations[0] + return rightmost == leftmost + + def __repr__(self): + return "Pack(%r)" % self.operations + class Pair(Pack): """ A special Pack object with only two statements. """ def __init__(self, left, right): @@ -345,6 +395,9 @@ return self.opidx == other.opidx and self.memref == other.memref return False + def __repr__(self): + return "PackOpWrapper(%d, %r)" % (self.opidx, self.memref) + class LoopVectorizeInfo(object): def __init__(self): _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit