Author: Richard Plangger <r...@pasra.at> Branch: vecopt2 Changeset: r77100:4f501c0da147 Date: 2015-03-31 12:15 +0200 http://bitbucket.org/pypy/pypy/changeset/4f501c0da147/
Log: enhanced dependency test. no boiler plate code to define dependencies (but annotate in the code instead) leaf nodes now have a dep. edge to jump op correctly redefining variables if they are destroyed by a call 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 @@ -75,7 +75,7 @@ i -= 1 except KeyError: # when a key error is raised, this means - # no information is available, assume the worst + # no information is available, safe default pass return def_chain[-1][0] @@ -102,9 +102,9 @@ self.adjacent_list = [ [] for i in range(len(self.operations)) ] self.integral_mod = IntegralMod() self.schedulable_nodes = [0] # label is always scheduleable - self.build_dependencies(self.operations) + self.build_dependencies() - def build_dependencies(self, operations): + def build_dependencies(self): """ This is basically building the definition-use chain and saving this information in a graph structure. This is the same as calculating the reaching definitions and the 'looking back' whenever it is used. @@ -113,99 +113,120 @@ the operations are in SSA form """ tracker = DefTracker(self.memory_refs) - + # guards = [] # pass 1 - for i,op in enumerate(operations): + for i,op in enumerate(self.operations): # the label operation defines all operations at the # beginning of the loop if op.getopnum() == rop.LABEL: for arg in op.getarglist(): tracker.define(arg, 0) continue # prevent adding edge to the label itself - # definition of a new variable if op.result is not None: # In SSA form. Modifications get a new variable tracker.define(op.result, i) - # usage of defined variables if op.is_always_pure() or op.is_final(): # normal case every arguments definition is set for arg in op.getarglist(): self._def_use(arg, i, tracker) + elif op.is_guard(): + guards.append(i) else: - self.put_edges_for_complex_objects(op, i, tracker) - - # guard specifics - if op.is_guard(): - guards.append(i) - # TODO - #if i > 0: - # self._guard_dependency(op, i, operations, tracker) - + self._build_non_pure_dependencies(op, i, tracker) + # # pass 2 correct guard dependencies for guard_idx in guards: - variables = [] - for dep in self.depends(guard_idx): - idx = dep.idx_from - op = operations[idx] - for arg in op.getarglist(): - if isinstance(arg, Box): - variables.append(arg) - if op.result: - variables.append(op.result) - print "\ntesting", variables - for var in variables: - try: - def_idx = tracker.definition_index(var) - print "guard", guard_idx, def_idx, "var", var, "aaa", [d.idx_to for d in self.get_uses(def_idx)] - for dep in self.provides(def_idx): - if var in dep.args and dep.idx_to > guard_idx: - self._put_edge(guard_idx, dep.idx_to, var) - print "put edge", guard_idx, dep.idx_to, var, dep.args - except KeyError: - pass - op = operations[guard_idx] - for arg in op.getfailargs(): - try: - def_idx = tracker.definition_index(arg) - self._put_edge(def_idx, i, arg) - except KeyError: - pass - + self._build_guard_dependencies(guard_idx, op.getopnum(), tracker) # pass 3 find schedulable nodes - for i,op in enumerate(operations): + jump_pos = len(self.operations)-1 + for i,op in enumerate(self.operations): if len(self.adjacent_list[i]) == 0: self.schedulable_nodes.append(i) + # every leaf instruction points to the jump_op. in theory + # every instruction points to jump_op, this is an optimization + # to prevent the scheduling of ops before the jump operation + if i != jump_pos: + for dep in self.adjacent_list[i]: + if dep.idx_to > i: + break + else: + self._put_edge(i, jump_pos, None) + def _build_guard_dependencies(self, guard_idx, guard_opnum, tracker): + if guard_opnum >= rop.GUARD_NOT_INVALIDATED: + # ignure invalidated & future condition guard + return + # 'GUARD_TRUE/1d', + # 'GUARD_FALSE/1d', + # 'GUARD_VALUE/2d', + # 'GUARD_CLASS/2d', + # 'GUARD_NONNULL/1d', + # 'GUARD_ISNULL/1d', + # 'GUARD_NONNULL_CLASS/2d', + guard_op = self.operations[guard_idx] + for arg in guard_op.getarglist(): + self._def_use(arg, guard_idx, tracker) - def update_memory_ref(self, op, index, tracker): - if index not in self.memory_refs: - return - memref = self.memory_refs[index] - self.integral_mod.reset() - try: - curidx = tracker.definition_index(memref.origin) - except KeyError: - return - curop = self.operations[curidx] - while True: - self.integral_mod.inspect_operation(curop) - if self.integral_mod.is_const_mod: - self.integral_mod.update_memory_ref(memref) + variables = [] + for dep in self.depends(guard_idx): + idx = dep.idx_from + op = self.operations[idx] + for arg in op.getarglist(): + if isinstance(arg, Box): + variables.append(arg) + if op.result: + variables.append(op.result) + # + for var in variables: + try: + def_idx = tracker.definition_index(var) + print "guard", guard_idx, def_idx, "var", var, "aaa", [d.idx_to for d in self.get_uses(def_idx)] + for dep in self.provides(def_idx): + if var in dep.args and dep.idx_to > guard_idx: + self._put_edge(guard_idx, dep.idx_to, var) + print "put edge", guard_idx, dep.idx_to, var, dep.args + except KeyError: + pass + # handle fail args + op = self.operations[guard_idx] + for arg in op.getfailargs(): + try: + def_idx = tracker.definition_index(arg) + self._put_edge(def_idx, guard_idx, arg) + except KeyError: + assert False + # + # guards check overflow or raise are directly dependent + # find the first non guard operation + prev_op_idx = guard_idx - 1 + while prev_op_idx > 0: + prev_op = self.operations[prev_op_idx] + if prev_op.is_guard(): + prev_op_idx -= 1 else: - break # an operation that is not tractable - for dep in self.depends(curidx): - curop = self.operations[dep.idx_from] - if curop.result == memref.origin: - curidx = dep.idx_from - break - else: - break # cannot go further, this might be the label, or a constant + break + prev_op = self.operations[prev_op_idx] + # + if op.is_guard_exception() and prev_op.can_raise(): + self._guard_inhert(prev_op_idx, guard_idx) + elif op.is_guard_overflow() and prev_op.is_ovf(): + self._guard_inhert(prev_op_idx, guard_idx) + elif op.getopnum() == rop.GUARD_NOT_FORCED and prev_op.can_raise(): + self._guard_inhert(prev_op_idx, guard_idx) + elif op.getopnum() == rop.GUARD_NOT_FORCED_2 and prev_op.can_raise(): + self._guard_inhert(prev_op_idx, guard_idx) - def put_edges_for_complex_objects(self, op, index, tracker): - self.update_memory_ref(op, index, tracker) + def _guard_inhert(self, idx, guard_idx): + self._put_edge(idx, guard_idx, None) + for dep in self.provides(idx): + if dep.idx_to > guard_idx: + self._put_edge(guard_idx, dep.idx_to, None) + + def _build_non_pure_dependencies(self, op, index, tracker): + self._update_memory_ref(op, index, tracker) if self.loads_from_complex_object(op): # If this complex object load operation loads an index that has been # modified, the last modification should be used to put a def-use edge. @@ -221,15 +242,13 @@ # tracks the exact cell that is modified self._def_use(arg, index, tracker, argcell=argcell) self._def_use(argcell, index, tracker) - if destroyed: - tracker.define(arg, index, argcell=argcell) else: if destroyed: - # we cannot be sure that only a one cell is modified - # assume the worst, this is a complete redefintion + # cannot be sure that only a one cell is modified + # assume all cells are (equivalent to a redefinition) try: - # A trace is not in SSA form, but this complex object - # modification introduces a WAR/WAW dependency + # A trace is not entirely in SSA form. complex object + # modification introduces WAR/WAW dependencies def_idx = tracker.definition_index(arg) for dep in self.provides(def_idx): if dep.idx_to >= index: @@ -241,6 +260,8 @@ else: # not destroyed, just a normal use of arg self._def_use(arg, index, tracker) + if destroyed: + tracker.define(arg, index, argcell=argcell) def _def_use(self, arg, index, tracker, argcell=None): try: @@ -274,46 +295,34 @@ 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 + def _update_memory_ref(self, op, index, tracker): + if index not in self.memory_refs: + return + memref = self.memory_refs[index] + self.integral_mod.reset() + try: + curidx = tracker.definition_index(memref.origin) + except KeyError: + return + curop = self.operations[curidx] + while True: + self.integral_mod.inspect_operation(curop) + if self.integral_mod.is_const_mod: + self.integral_mod.update_memory_ref(memref) 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 # an operation that is not tractable + for dep in self.depends(curidx): + curop = self.operations[dep.idx_from] + if curop.result == memref.origin: + curidx = dep.idx_from 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) + else: + break # cannot go further, this might be the label, or a constant def _put_edge(self, idx_from, idx_to, arg): assert idx_from != idx_to - if idx_from == 6 and idx_to == 9: - assert False - dep = self.instr_dependency(idx_from, idx_to) - if dep is None: + dep = self.directly_depends(idx_from, idx_to) + if not dep: dep = Dependency(idx_from, idx_to, arg) self.adjacent_list[idx_from].append(dep) self.adjacent_list[idx_to].append(dep) @@ -347,6 +356,8 @@ if idx > dep.idx_from: yield dep + def dependencies(self, idx): + return self.adjacent_list[idx] def instr_dependencies(self, idx): edges = self.adjacent_list[idx] return edges @@ -363,7 +374,7 @@ stmt_indices = [bi] while len(stmt_indices) > 0: idx = stmt_indices.pop() - for dep in self.instr_dependencies(idx): + for dep in self.dependencies(idx): if idx < dep.idx_to: # this dependency points downwards (thus unrelevant) continue @@ -378,13 +389,17 @@ return True def definition_dependencies(self, idx): + # XXX remove 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 directly_depends(self, from_idx, to_idx): + return self.instr_dependency(from_idx, to_idx) def instr_dependency(self, from_instr_idx, to_instr_idx): + # XXX """ 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. @@ -404,15 +419,13 @@ idx = follow_dep.idx_from if idx == point_to_idx: idx = follow_dep.idx_to - - preount = len(self.adjacent_list[idx]) + #preount = len(self.adjacent_list[idx]) self.adjacent_list[idx] = [d for d in self.adjacent_list[idx] \ if d.idx_to != point_to_idx and d.idx_from != point_to_idx] #print "reduced", idx, "from",preount,"to",len(self.adjacent_list[idx]) def __repr__(self): graph = "graph([\n" - for i,l in enumerate(self.adjacent_list): graph += " " + str(i) + ": " for d in l: @@ -421,25 +434,20 @@ else: graph += str(d.idx_from) + "," graph += "\n" - return graph + " ])" def loads_from_complex_object(self, op): - opnum = op.getopnum() - return rop._ALWAYS_PURE_LAST <= opnum and opnum <= rop._MALLOC_FIRST + return rop._ALWAYS_PURE_LAST <= op.getopnum() <= rop._MALLOC_FIRST def modifies_complex_object(self, op): - opnum = op.getopnum() - return rop.SETARRAYITEM_GC<= opnum and opnum <= rop.UNICODESETITEM + return rop.SETARRAYITEM_GC <= op.getopnum() <= rop.UNICODESETITEM def as_dot(self, operations): if not we_are_translated(): dot = "digraph dep_graph {\n" - for i in range(len(self.adjacent_list)): op = operations[i] dot += " n%d [label=\"[%d]: %s\"];\n" % (i,i,str(op)) - dot += "\n" for i,alist in enumerate(self.adjacent_list): for dep in alist: @@ -447,7 +455,6 @@ dot += " n%d -> n%d;\n" % (i,dep.idx_to) dot += "\n}\n" return dot - return "" class Scheduler(object): @@ -476,14 +483,16 @@ print "shifting", index, "(", node ,")","to", len(self.schedulable_nodes)-1, "sched", self.schedulable_nodes def schedule_all(self, opindices): - indices = [] while len(opindices) > 0: opidx = opindices.pop() for i,node in enumerate(self.schedulable_nodes): if node == opidx: - indices.append(i) - for index in indices: - self.schedule(index) + print "will sch[",i,"]",node + break + else: + i = -1 + if i != -1: + self.schedule(i) def schedule(self, index): node = self.schedulable_nodes[index] @@ -494,7 +503,7 @@ for dep in adj_list: self.graph.remove_depencency(dep, node) # - for dep in self.graph.provideso(node): + for dep in self.graph.provides(node): candidate = dep.idx_to if self.is_schedulable(dep.idx_to): self.schedulable_nodes.append(dep.idx_to) 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 @@ -65,6 +65,29 @@ assert sorted([l.idx_from for l in la]) == \ sorted([l.idx_from for l in lb]) + def assert_dependencies(self, ops, memref=False, full_check=True): + graph = self.build_dependency(ops, memref) + import re + deps = {} + for i,line in enumerate(ops.splitlines()): + dep_pattern = re.compile("#\s*(\d+):") + dep_match = dep_pattern.search(line) + if dep_match: + label = int(dep_match.group(1)) + deps_list = [int(d) for d in line[dep_match.end():].split(',') if len(d) > 0] + deps[label] = deps_list + + if full_check: + edges = [ None ] * len(deps) + for k,l in deps.items(): + edges[k] = l + for k,l in deps.items(): + for rk in l: + if rk > k: + edges[rk].append(k) + self.assert_edges(graph, edges) + return graph + def assert_independent(self, a, b): assert self.last_graph.independent(a,b), "{a} and {b} are dependent!".format(a=a,b=b) @@ -82,208 +105,155 @@ class BaseTestDependencyGraph(DepTestHelper): def test_dependency_empty(self): ops = """ - [] - jump() + [] # 0: 1 + jump() # 1: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, [ [], [], ]) + self.assert_dependencies(ops, full_check=True) def test_dependency_of_constant_not_used(self): ops = """ - [] - i1 = int_add(1,1) - jump() + [] # 0: 2 + i1 = int_add(1,1) # 1: 2 + jump() # 2: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, [ [], [], [] ]) + self.assert_dependencies(ops, full_check=True) def test_dependency_simple(self): ops = """ - [] - i1 = int_add(1,1) - i2 = int_add(i1,1) - guard_value(i2,3) [] - jump() + [] # 0: 4 + i1 = int_add(1,1) # 1: 2 + i2 = int_add(i1,1) # 2: 3 + guard_value(i2,3) [] # 3: 4 + jump() # 4: """ - graph = self.build_dependency(ops) - self.assert_edges(graph, - [ [], [2], [1,3], [2], [], ]) - for i in range(0,5): - self.assert_independent(0,i) + graph = self.assert_dependencies(ops, full_check=True) + self.assert_independent(0,1) + self.assert_independent(0,2) + self.assert_independent(0,3) self.assert_dependent(1,2) self.assert_dependent(2,3) self.assert_dependent(1,3) - self.assert_independent(2,4) - self.assert_independent(3,4) + self.assert_dependent(2,4) + self.assert_dependent(3,4) def test_def_use_jump_use_def(self): ops = """ - [i3] - i1 = int_add(i3,1) - guard_value(i1,0) [] - jump(i1) + [i3] # 0: 1 + i1 = int_add(i3,1) # 1: 2, 3 + guard_value(i1,0) [] # 2: 3 + jump(i1) # 3: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1], [0,2,3], [1], [1] ]) + self.assert_dependencies(ops, full_check=True) def test_dependency_guard(self): ops = """ - [i3] - i1 = int_add(1,1) - guard_value(i1,0) [i3] - jump(i3) + [i3] # 0: 2,3 + i1 = int_add(1,1) # 1: 2 + guard_value(i1,0) [i3] # 2: 3 + jump(i3) # 3: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [2,3], [2], [1,0], [0] ]) + self.assert_dependencies(ops, full_check=True) - #def test_dependency_guard_2(self): - # ops = """ - # [i1] - # i2 = int_le(i1, 10) - # guard_true(i2) [i1] - # i3 = int_add(i1,1) - # jump(i3) - # """ - # dep_graph = self.build_dependency(ops) - # self.assert_edges(dep_graph, - # [ [1], [0,2], [1], [2,4], [3] ]) + def test_dependency_guard_2(self): + ops = """ + [i1] # 0: 1,2,3 + i2 = int_le(i1, 10) # 1: 2 + guard_true(i2) [i1] # 2: 3 + i3 = int_add(i1,1) # 3: 4 + jump(i3) # 4: + """ + self.assert_dependencies(ops, full_check=True) def test_no_edge_duplication(self): ops = """ - [i1] - i2 = int_lt(i1,10) - guard_false(i2) [i1] - i3 = int_add(i1,i1) - jump(i3) + [i1] # 0: 1,2,3 + i2 = int_lt(i1,10) # 1: 2 + guard_false(i2) [i1] # 2: 3 + i3 = int_add(i1,i1) # 3: 4 + jump(i3) # 4: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1,2,3], [0,2], [1,0], [0,4], [3] ]) + self.assert_dependencies(ops, full_check=True) def test_no_edge_duplication_in_guard_failargs(self): ops = """ - [i1] - i2 = int_lt(i1,10) - guard_false(i2) [i1,i1,i2,i1,i2,i1] - jump(i1) + [i1] # 0: 1,2,3 + i2 = int_lt(i1,10) # 1: 2 + guard_false(i2) [i1,i1,i2,i1,i2,i1] # 2: 3 + jump(i1) # 3: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1,2,3], [0,2], [1,0], [0] ]) + self.assert_dependencies(ops, full_check=True) self.assert_dependent(0,1) self.assert_dependent(0,2) self.assert_dependent(0,3) - 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_edges(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 + [i0, i1, i2] # 0: 1,3,6,7,11 + i4 = int_gt(i1, 0) # 1: 2 + guard_true(i4) [] # 2: 3, 11 + i6 = int_sub(i1, 1) # 3: 4 + i8 = int_gt(i6, 0) # 4: 5 + guard_false(i8) [] # 5: 11 + i10 = int_add(i2, 1) # 6: 8 + i12 = int_sub(i0, 1) # 7: 9, 11 + i14 = int_add(i10, 1) # 8: 11 + i16 = int_gt(i12, 0) # 9: 10 + guard_true(i16) [] # 10: 11 + jump(i12, i1, i14) # 11: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(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] ]) + self.assert_dependencies(ops, full_check=True) self.assert_independent(6, 2) self.assert_independent(6, 1) self.assert_dependent(6, 0) def test_prevent_double_arg(self): ops=""" - [i0, i1, i2] - i4 = int_gt(i1, i0) - guard_true(i4) [] - jump(i0, i1, i2) + [i0, i1, i2] # 0: 1,3 + i4 = int_gt(i1, i0) # 1: 2 + guard_true(i4) [] # 2: 3 + jump(i0, i1, i2) # 3: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1,3], [0,2], [1], [0] ]) + self.assert_dependencies(ops, full_check=True) def test_ovf_dep(self): ops=""" - [i0, i1, i2] - i4 = int_sub_ovf(1, 0) - guard_overflow() [i2] - jump(i0, i1, i2) + [i0, i1, i2] # 0: 2,3 + i4 = int_sub_ovf(1, 0) # 1: 2 + guard_overflow() [i2] # 2: 3 + jump(i0, i1, i2) # 3: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1,2,3], [0,2], [0,1], [0] ]) + self.assert_dependencies(ops, full_check=True) def test_exception_dep(self): ops=""" - [p0, i1, i2] - i4 = call(p0, 1, descr=nonwritedescr) - guard_no_exception() [] - jump(p0, i1, i2) + [p0, i1, i2] # 0: 1,3 + i4 = call(p0, 1, descr=nonwritedescr) # 1: 2,3 + guard_no_exception() [] # 2: 3 + jump(p0, i1, i2) # 3: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1,3], [0,2], [1], [0] ]) + self.assert_dependencies(ops, full_check=True) 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) + [p0, p1, i2] # 0: 1,2,3,4,5 + i3 = int_add(i2,1) # 1: 2 + i4 = call(p0, i3, descr=nonwritedescr) # 2: 3,4,5 + guard_no_exception() [i2] # 3: 4,5 + p2 = getarrayitem_gc(p1,i3) # 4: 5 + jump(p2, p1, i3) # 5: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1,2,3,4,5], [0,2,4,5], [0,1,3], [0,2], [0,1,5], [4,0,1] ]) + self.assert_dependencies(ops, full_check=True) 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) + [p0, p1, i2, i5] # 0: 1,2,3,4,5 + i3 = int_add(i2,1) # 1: 2 + i4 = call(i5, i3, descr=nonwritedescr) # 2: 3,4,5 + guard_no_exception() [i2] # 3: 4,5 + p2 = getarrayitem_gc(p1,i3) # 4: 5 + jump(p2, p1, i3) # 5: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1,2,3,4,5], [0,2,4,5], [0,1,3], [0,2], [0,1,5], [4,0,1] ]) + self.assert_dependencies(ops, full_check=True) def test_setarrayitem_dependency(self): ops=""" @@ -312,25 +282,29 @@ self.assert_dependent(1,2) self.assert_dependent(0,3) - def test_setarrayitem_same_modified_var_not_aliased(self): - # #1 does NOT depend on #2, i1 and i2 are not aliased + def test_setarrayitem_depend_with_no_memref_info(self): ops=""" - [p0, i1] - setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) #1 - i2 = int_add(i1,1) - setarrayitem_raw(p0, i2, 2, descr=floatarraydescr) #2 - jump(p0, i1) + [p0, i1] # 0: 1,2,4 + setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) # 1: 3 + i2 = int_add(i1,1) # 2: 3 + setarrayitem_raw(p0, i2, 2, descr=floatarraydescr) # 3: 4 + jump(p0, i1) # 4: """ - 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_dependencies(ops, full_check=True) self.assert_independent(1,2) self.assert_dependent(1,3) + def test_setarrayitem_dont_depend_with_memref_info(self): + ops=""" + [p0, i1] # 0: 1,2,3,4 + setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) # 1: 4 + i2 = int_add(i1,1) # 2: 3 + setarrayitem_raw(p0, i2, 2, descr=floatarraydescr) # 3: 4 + jump(p0, i1) # 4: + """ + self.assert_dependencies(ops, memref=True, full_check=True) + self.assert_independent(1,2) + self.assert_independent(1,3) # they modify 2 different cells + 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 @@ -340,7 +340,7 @@ vopt = self.vec_optimizer_unrolled(self.parse_loop(ops),1) vopt.build_dependency_graph() self.assert_edges(vopt.dependency_graph, - [ [1,2,3,5], [0], [0,3,4], [0,2], [2,5], [0,4] ]) + [ [1,2,3,5], [0,5], [0,3,4], [0,2,5], [2,5], [0,4,1,3] ]) vopt.find_adjacent_memory_refs() assert 1 in vopt.vec_info.memory_refs @@ -498,9 +498,9 @@ vopt.build_dependency_graph() self.assert_edges(vopt.dependency_graph, [ [1,2,3,4,5,7,9], - [0], [0,5,6], [0], [0,7,8], - [0,2], [2,9], [0,4], [4,9], - [0,6,8], + [0,9], [0,5,6], [0,9], [0,7,8], + [0,2,9], [2,9], [0,4,9], [4,9], + [0,6,8,1,3,5,7], ]) vopt.find_adjacent_memory_refs() @@ -862,22 +862,24 @@ """.format(op=op) vops = """ [p0,p1,p2,i0] - i10 = int_le(i1, 128) - guard_true(i10) [] + i10 = int_le(i0, 128) + guard_true(i10) [p0,p1,p2,i0] i1 = int_add(i0, 1) - i12 = int_le(i11, 128) - guard_true(i12) [] - i11 = int_add(i1, 1) - i2 = vec_raw_load(p0, i0, 4, descr=floatarraydescr) - i3 = vec_raw_load(p1, i0, 4, descr=floatarraydescr) - i4 = {op}(i2,i3,4,descr=floatarraydescr) - vec_raw_store(p2, i0, i4, 4, descr=floatarraydescr) + i11 = int_le(i1, 128) + guard_true(i11) [p0,p1,p2,i0] + i2 = vec_raw_load(p0, i0, 2, descr=floatarraydescr) + i3 = vec_raw_load(p1, i0, 2, descr=floatarraydescr) + i12 = int_add(i1, 1) + i4 = {op}(i2,i3,2) + vec_raw_store(p2, i0, i4, 2, descr=floatarraydescr) jump(p0,p1,p2,i12) """.format(op=vop) loop = self.parse_loop(ops) vopt = self.schedule(loop,1) + oo = self.vec_optimizer_unrolled(self.parse_loop(ops), 1) + self._write_dot_and_convert_to_svg(vopt.dependency_graph, oo.loop.operations, 'test_2') self.debug_print_operations(vopt.loop) - #self.assert_equal(loop, self.parse_loop(vops)) + self.assert_equal(loop, self.parse_loop(vops)) 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 @@ -290,7 +290,6 @@ def schedule(self): self.clear_newoperations() scheduler = Scheduler(self.dependency_graph) - i = 0 while scheduler.has_more_to_schedule(): candidate_index = scheduler.next_schedule_index() candidate = self.loop.operations[candidate_index] @@ -300,10 +299,6 @@ else: self.emit_operation(candidate) scheduler.schedule(0) - i+=1 - if i > 20: - print self.dependency_graph - break self.loop.operations = self._newoperations[:] _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit