Author: Richard Plangger <r...@pasra.at> Branch: vecopt2 Changeset: r77111:53e935368706 Date: 2015-04-10 16:14 +0200 http://bitbucket.org/pypy/pypy/changeset/53e935368706/
Log: the dependency graph now wraps each operation in a Node object. This makes the arch. much cleaner and separates concerns 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,7 +2,7 @@ from rpython.jit.metainterp.optimizeopt.util import make_dispatcher_method from rpython.jit.metainterp.resoperation import rop from rpython.jit.codewriter.effectinfo import EffectInfo -from rpython.jit.metainterp.history import BoxPtr, ConstPtr, ConstInt, BoxInt, Box +from rpython.jit.metainterp.history import BoxPtr, ConstPtr, ConstInt, BoxInt, Box, Const from rpython.rtyper.lltypesystem import llmemory from rpython.rlib.unroll import unrolling_iterable from rpython.rlib.objectmodel import we_are_translated @@ -38,16 +38,190 @@ def clone(self): return Path(self.path[:]) -class OpWrapper(object): +class Node(object): def __init__(self, op, opidx): self.op = op self.opidx = opidx + self.adjacent_list = [] + self.adjacent_list_back = [] + self.memory_ref = None + self.pack = None + + def getoperation(self): + return self.op + def getindex(self): + return self.opidx + + def dependency_count(self): + return len(self.adjacent_list) def getopnum(self): return self.op.getopnum() + def getopname(self): + return self.op.getopname() + + def edge_to(self, to, arg, label=None): + assert self != to + dep = self.depends_on(to) + if not dep: + #if force or self.independent(idx_from, idx_to): + dep = Dependency(self, to, arg) + self.adjacent_list.append(dep) + dep_back = Dependency(to, self, arg) + to.adjacent_list_back.append(dep_back) + if not we_are_translated(): + if label is None: + label = '' + dep.label = label + else: + if not dep.because_of(arg): + dep.add_dependency(self,to,arg) + if not we_are_translated() and label is not None: + _label = getattr(dep, 'label', '') + dep.label = _label + ", " + label + + def depends_on(self, to): + """ 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. + """ + for edge in self.adjacent_list: + if edge.to == to: + return edge + return None + + def clear_dependencies(self): + self.adjacent_list.clear() + self.adjacent_list_back.clear() def is_guard_early_exit(self): - return self.op.getopnum() == rop.GUARD_NO_EARLY_EXIT: + return self.op.getopnum() == rop.GUARD_NO_EARLY_EXIT + + def loads_from_complex_object(self): + return rop._ALWAYS_PURE_LAST <= self.op.getopnum() <= rop._MALLOC_FIRST + + def modifies_complex_object(self): + return rop.SETARRAYITEM_GC <= self.op.getopnum() <= rop.UNICODESETITEM + + def side_effect_arguments(self): + # if an item in array p0 is modified or a call contains an argument + # it can modify it is returned in the destroyed list. + args = [] + op = self.op + if self.modifies_complex_object(): + for opnum, i, j in unrolling_iterable(MODIFY_COMPLEX_OBJ): + if op.getopnum() == opnum: + op_args = op.getarglist() + if j == -1: + args.append((op.getarg(i), None, True)) + for j in range(i+1,len(op_args)): + args.append((op.getarg(j), None, False)) + else: + args.append((op.getarg(i), op.getarg(j), True)) + for x in range(j+1,len(op_args)): + args.append((op.getarg(x), None, False)) + break + else: + # assume this destroys every argument... can be enhanced by looking + # at the effect info of a call for instance + for arg in op.getarglist(): + args.append((arg,None,True)) + return args + + def provides_count(self): + return len(self.adjacent_list) + + def provides(self): + return self.adjacent_list + + def depends_count(self, idx): + return len(self.adjacent_list_back) + + def depends(self): + return self.adjacent_list_back + + def dependencies(self): + return self.adjacent_list[:] + self.adjacent_list_back[:] + + def is_after(self, other): + return self.opidx > other.opidx + + def is_before(self, other): + return self.opidx < other.opidx + + def independent(self, other): + """ An instruction depends on another if there is a path from + self to other. """ + if self == other: + return True + # forward + worklist = [self] + while len(worklist) > 0: + node = worklist.pop() + for dep in node.provides(): + if dep.points_to(other): + # dependent. There is a path from self to other + return False + worklist.append(dep.to) + # backward + worklist = [self] + while len(worklist) > 0: + node = worklist.pop() + for dep in node.depends(): + if dep.points_to(other): + # dependent. There is a path from self to other + return False + worklist.append(dep.to) + return True + + def iterate_paths_backward(self, ai, bi): + if ai == bi: + return + if ai > bi: + ai, bi = bi, ai + worklist = [(Path([bi]),bi)] + while len(worklist) > 0: + path,idx = worklist.pop() + for dep in self.depends(idx): + if ai > dep.idx_from or dep.points_backward(): + # this points above ai (thus unrelevant) + continue + cloned_path = path.clone() + cloned_path.walk(dep.idx_from) + if dep.idx_from == ai: + yield cloned_path + else: + worklist.append((cloned_path,dep.idx_from)) + + def getedge_to(self, other): + for dep in self.adjacent_list: + if dep.to == other: + return dep + return None + + def i_remove_dependency(self, idx_at, idx_to): + at = self.nodes[idx_at] + to = self.nodes[idx_to] + self.remove_dependency(at, to) + def remove_dependency(self, at, to): + """ Removes a all dependencies that point to 'to' """ + self.adjacent_list[at] = \ + [d for d in self.adjacent_list[at] if d.to != to] + self.adjacent_list[to] = \ + [d for d in self.adjacent_list[to] if d.at != at] + + return args + def __repr__(self): + return "Node(opidx: %d)"%self.opidx + + def __ne__(self, other): + return not self.__eq__(other) + + def __eq__(self, other): + if isinstance(other, Node): + return self.opidx == other.opidx + return False + class Dependency(object): def __init__(self, at, to, arg): @@ -58,7 +232,33 @@ self.at = at self.to = to - def add_dependency(self, at, arg): + def because_of(self, var): + for arg in self.args: + if arg[1] == var: + return True + return False + + def to_index(self): + return self.to.getindex() + def at_index(self): + return self.at.getindex() + + def points_after_to(self, to): + return self.to.opidx < to.opidx + def points_above_at(self, at): + return self.at.opidx < at.opidx + def i_points_above_at(self, idx): + return self.at.opidx < idx + + def points_to(self, to): + return self.to == to + def points_at(self, at): + return self.at == at + def i_points_at(self, idx): + # REM + return self.at.opidx == idx + + def add_dependency(self, at, to, arg): self.args.append((at,arg)) def reverse_direction(self, ref): @@ -76,17 +276,17 @@ self.graph = graph self.defs = {} - def define(self, arg, index, argcell=None): + def define(self, arg, node, argcell=None): if arg in self.defs: - self.defs[arg].append((index,argcell)) + self.defs[arg].append((node,argcell)) else: - self.defs[arg] = [(index,argcell)] + self.defs[arg] = [(node,argcell)] def redefintions(self, arg): for _def in self.defs[arg]: yield _def[0] - def definition_index(self, arg, index = -1, argcell=None): + def definition(self, arg, node=None, argcell=None): def_chain = self.defs[arg] if len(def_chain) == 1: return def_chain[0][0] @@ -94,17 +294,17 @@ if argcell == None: return def_chain[-1][0] else: - assert index != -1 + assert node is not None i = len(def_chain)-1 try: - mref = self.graph.memory_refs[index] + mref = node.memory_ref while i >= 0: - def_index = def_chain[i][0] - oref = self.graph.memory_refs.get(def_index) + def_node = def_chain[i][0] + oref = def_node.memory_ref if oref is not None and mref.indices_can_alias(oref): - return def_index + return def_node elif oref is None: - return def_index + return def_node i -= 1 except KeyError: # when a key error is raised, this means @@ -114,11 +314,12 @@ def depends_on_arg(self, arg, to, argcell=None): try: - idx_at = self.definition_index(arg, to.opidx, argcell) - at = self.graph.operations[idx_at] - graph.edge(at, to, arg) + at = self.definition(arg, to, argcell) + at.edge_to(to, arg) except KeyError: - assert False, "arg %s must be defined" % arg + if not we_are_translated(): + if not isinstance(arg, Const): + assert False, "arg %s must be defined" % arg class DependencyGraph(object): @@ -141,14 +342,16 @@ the same element. """ def __init__(self, operations): - self.operations = [OpWrapper(op) for op in operations] + self.nodes = [ Node(op,i) for i,op in enumerate(operations) ] self.memory_refs = {} - self.adjacent_list = { op: [] for op in operations } self.schedulable_nodes = [0] # label is always scheduleable self.index_vars = {} self.guards = [] self.build_dependencies() + def getnode(self, i): + return self.nodes[i] + 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 @@ -161,54 +364,49 @@ # intformod = IntegralForwardModification(self.memory_refs, self.index_vars) # pass 1 - for i,opw in enumerate(self.operations): - op = opw.op + for i,node in enumerate(self.nodes): + op = node.op # the label operation defines all operations at the # beginning of the loop if op.getopnum() == rop.LABEL: # TODO is it valid that a label occurs at the end of a trace? - s = 0 - if self.operations[s+1].is_guard_early_exit(): - s = 1 - self.i_edge(0,1,label='L->EE') + ee_node = self.nodes[i+1] + if ee_node.is_guard_early_exit(): + node.edge_to(ee_node,None,label='L->EE') + node = ee_node for arg in op.getarglist(): - tracker.define(arg, s) - #if isinstance(arg, BoxInt): - # assert arg not in self.index_vars - # self.index_vars[arg] = IndexVar(arg) + tracker.define(arg, node) continue # prevent adding edge to the label itself - intformod.inspect_operation(op, i) + intformod.inspect_operation(node) # definition of a new variable if op.result is not None: # In SSA form. Modifications get a new variable - tracker.define(op.result, i) + tracker.define(op.result, node) # 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(): - tracker.depends_on_arg(arg, opw) + tracker.depends_on_arg(arg, node) elif op.is_guard(): - self.guards.append(i) + self.guards.append(node) else: - self._build_non_pure_dependencies(op, i, tracker) + self._build_non_pure_dependencies(node, tracker) # pass 2 correct guard dependencies - for guard_idx in self.guards: - self._build_guard_dependencies(guard_idx, op.getopnum(), tracker) + for guard_node in self.guards: + self._build_guard_dependencies(guard_node, op.getopnum(), tracker) # pass 3 find schedulable nodes - 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) + jump_pos = len(self.nodes)-1 + jump_node = self.nodes[jump_pos] + for node in self.nodes: + if node.dependency_count() == 0: + self.schedulable_nodes.append(node.opidx) # every leaf instruction points to the jump_op. in theory every instruction # points to jump_op. this forces the jump/finish op to be the last operation - if i != jump_pos: - for dep in self.adjacent_list[i]: - if dep.idx_to > i: - break - else: - self._put_edge(jump_pos, i, jump_pos, None) + if node != jump_node: + if node.provides_count() == 0: + node.edge_to(jump_node, None, label='jump') - def _build_guard_dependencies(self, guard_idx, guard_opnum, tracker): + def _build_guard_dependencies(self, guard_node, guard_opnum, tracker): if guard_opnum >= rop.GUARD_NOT_INVALIDATED: # ignure invalidated & future condition guard return @@ -219,14 +417,13 @@ # 'GUARD_NONNULL/1d', # 'GUARD_ISNULL/1d', # 'GUARD_NONNULL_CLASS/2d', - guard_opw = self.operations[guard_idx] - guard_op = guard_opw.op + guard_op = guard_node.op for arg in guard_op.getarglist(): - tracker.depends_on_arg(arg, guard_opw) + tracker.depends_on_arg(arg, guard_node) variables = [] - for dep in self.depends(guard_opw): - op = dep.at.op + for dep in guard_node.depends(): + op = dep.to.op for arg in op.getarglist(): if isinstance(arg, Box): variables.append(arg) @@ -235,66 +432,67 @@ # for var in variables: try: - def_idx = tracker.definition_index(var) - for dep in self.provides(def_idx): - if var in dep.args and dep.idx_to > guard_idx: - self.edge(guard_opw, dep.to, var, label='prev('+str(var)+')') + def_node = tracker.definition(var) + for dep in def_node.provides(): + if guard_node.is_before(dep.to) and dep.because_of(var): + guard_node.edge_to(dep.to, var, label='prev('+str(var)+')') except KeyError: pass # handle fail args if guard_op.getfailargs(): for arg in guard_op.getfailargs(): try: - for def_idx in tracker.redefintions(arg): - at = self.operations[def_idx] - dep = self.edge(at, guard_opw, arg, label="fail") + for at in tracker.redefintions(arg): + # later redefinitions are prohibited + if at.is_before(guard_node): + at.edge_to(guard_node, arg, label="fail") except KeyError: assert False # # guards check overflow or raise are directly dependent # find the first non guard operation - prev_op_idx = guard_idx - 1 + prev_op_idx = guard_node.opidx - 1 while prev_op_idx > 0: - prev_op = self.operations[prev_op_idx].op - if prev_op.is_guard(): + prev_node = self.nodes[prev_op_idx] + if prev_node.op.is_guard(): prev_op_idx -= 1 else: break - prev_op = self.operations[prev_op_idx].op - # - if op.is_guard_exception() and prev_op.can_raise(): - self.i_guard_inhert(prev_op_idx, guard_idx) - elif op.is_guard_overflow() and prev_op.is_ovf(): - self.i_guard_inhert(prev_op_idx, guard_idx) - elif op.getopnum() == rop.GUARD_NOT_FORCED and prev_op.can_raise(): - self.i_guard_inhert(prev_op_idx, guard_idx) - elif op.getopnum() == rop.GUARD_NOT_FORCED_2 and prev_op.can_raise(): - self.i_guard_inhert(prev_op_idx, guard_idx) + prev_node = self.nodes[prev_op_idx] + guard_op = guard_node.getoperation() + prev_op = prev_node.getoperation() + if guard_op.is_guard_exception() and prev_op.can_raise(): + self.guard_inhert(prev_node, guard_node) + elif guard_op.is_guard_overflow() and prev_op.is_ovf(): + self.guard_inhert(prev_node, guard_node) + elif guard_op.getopnum() == rop.GUARD_NOT_FORCED and prev_op.can_raise(): + self.guard_inhert(prev_node, guard_node) + elif guard_op.getopnum() == rop.GUARD_NOT_FORCED_2 and prev_op.can_raise(): + self.guard_inhert(prev_node, guard_node) - def i_guard_inhert(self, idx, guard_idx): - at = self.operation[idx] - dep = self.i_edge(idx, guard_idx, None, label='inhert') - for dep in self.provides(at): - if dep.to.opidx > guard_idx: - self.i_edge(guard_idx, dep.to.opidx, None, label='inhert') + def guard_inhert(self, at, to): + at.edge_to(to, None, label='inhert') + for dep in at.provides(): + if to.is_before(dep.to): + to.edge_to(dep.to, None, label='inhert') - def _build_non_pure_dependencies(self, op, index, tracker): - # self._update_memory_ref(op, index, tracker) - if self.loads_from_complex_object(op): + def _build_non_pure_dependencies(self, node, tracker): + op = node.op + if node.loads_from_complex_object(): # 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. for opnum, i, j in unrolling_iterable(LOAD_COMPLEX_OBJ): if opnum == op.getopnum(): cobj = op.getarg(i) index_var = op.getarg(j) - self._def_use(cobj, index, tracker, argcell=index_var) - self._def_use(index_var, index, tracker) + tracker.depends_on_arg(cobj, node, index_var) + tracker.depends_on_arg(index_var, node) else: - for arg, argcell, destroyed in self._side_effect_argument(op): + for arg, argcell, destroyed in node.side_effect_arguments(): if argcell is not None: # tracks the exact cell that is modified - self._def_use(arg, index, tracker, argcell=argcell) - self._def_use(argcell, index, tracker) + tracker.depends_on_arg(arg, node, argcell) + tracker.depends_on_arg(argcell, node) else: if destroyed: # cannot be sure that only a one cell is modified @@ -302,232 +500,47 @@ try: # 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: - break - self._put_edge(index, dep.idx_to, index, argcell, label='war') - self._put_edge(index, def_idx, index, argcell) + def_node = tracker.definition(arg) + for dep in def_node.provides(): + if dep.to != node: + dep.to.edge_to(node, argcell, label='war') + def_node.edge_to(node, argcell) except KeyError: pass else: # not destroyed, just a normal use of arg - self._def_use(arg, index, tracker) + tracker.depends_on_arg(arg, node) if destroyed: - tracker.define(arg, index, argcell=argcell) - - def _side_effect_argument(self, op): - # if an item in array p0 is modified or a call contains an argument - # it can modify it is returned in the destroyed list. - args = [] - if self.modifies_complex_object(op): - for opnum, i, j in unrolling_iterable(MODIFY_COMPLEX_OBJ): - if op.getopnum() == opnum: - op_args = op.getarglist() - if j == -1: - args.append((op.getarg(i), None, True)) - for j in range(i+1,len(op_args)): - args.append((op.getarg(j), None, False)) - else: - args.append((op.getarg(i), op.getarg(j), True)) - for x in range(j+1,len(op_args)): - args.append((op.getarg(x), None, False)) - break - else: - # assume this destroys every argument... can be enhanced by looking - # at the effect info of a call for instance - for arg in op.getarglist(): - args.append((arg,None,True)) - - return args - - def _update_memory_ref(self, op, index, tracker): - # deprecated - 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 # 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 - - def i_edge(self, idx_at, idx_to, label=None): - self._i_edge(idx_at, idx_to, None, label=label) - - def _edge(self, at, to, arg, label=None): - assert at != to - dep = self.i_directly_depends(idx_from, idx_to) - if not dep or dep.at != at: - #if force or self.independent(idx_from, idx_to): - dep = Dependency(at, to, arg) - self.adjacent_list.setdefault(at,[]).append(dep) - self.adjacent_list.setdefault(to,[]).append(dep) - if not we_are_translated() and label is not None: - dep.label = label - else: - if arg not in dep.args: - dep.add_dependency(at,to,arg) - if not we_are_translated() and label is not None: - l = getattr(dep,'label',None) - if l is None: - l = '' - dep.label = l + ", " + label - - def _i_edge(self, idx_at, idx_to, arg, label=None): - at = self.operations[idx_at] - to = self.operations[idx_to] - self._edge(at, to, arg, label) - - def provides_count(self, idx): - # TODO - i = 0 - for _ in self.provides(idx): - i += 1 - return i - - def provides(self, opw): - for dep in self.adjacent_list[opw]: - if opw.opidx < dep.to.opidx: - yield dep - - def depends_count(self, idx): - i = 0 - for _ in self.depends(idx): - i += 1 - return i - - def i_depends(self, idx): - opw = self.operations[idx] - return self.depends(opw) - def depends(self, opw): - for dep in self.adjacent_list[opw]: - if opw.opidx > dep.at.opidx: - yield dep - - def dependencies(self, idx): - return self.adjacent_list[idx] - - def independent(self, ai, bi): - """ An instruction depends on another if there is a dependency path from - A to B. It is not enough to check only if A depends on B, because - due to transitive relations. - """ - if ai == bi: - return True - if ai > bi: - ai, bi = bi, ai - stmt_indices = [bi] - while len(stmt_indices) > 0: - idx = stmt_indices.pop() - for dep in self.depends(idx): - if ai > dep.idx_from: - # this points above ai (thus unrelevant) - continue - - if dep.idx_from == ai: - # dependent. There is a path from ai to bi - return False - stmt_indices.append(dep.idx_from) - return True - - def iterate_paths_backward(self, ai, bi): - if ai == bi: - return - if ai > bi: - ai, bi = bi, ai - worklist = [(Path([bi]),bi)] - while len(worklist) > 0: - path,idx = worklist.pop() - for dep in self.depends(idx): - if ai > dep.idx_from or dep.points_backward(): - # this points above ai (thus unrelevant) - continue - cloned_path = path.clone() - cloned_path.walk(dep.idx_from) - if dep.idx_from == ai: - yield cloned_path - else: - worklist.append((cloned_path,dep.idx_from)) - - def directly_depends(self, from_idx, to_idx): - return self.instr_dependency(from_idx, to_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. - """ - if from_instr_idx > to_instr_idx: - to_instr_idx, from_instr_idx = from_instr_idx, to_instr_idx - for edge in self.instr_dependencies(from_instr_idx): - if edge.idx_to == to_instr_idx: - return edge - return None - - def i_remove_dependency(self, idx_at, idx_to): - at = self.operations[idx_at] - to = self.operations[idx_to] - self.remove_dependency(at, to) - def remove_dependency(self, at, to): - """ Removes a all dependencies that point to 'to' """ - self.adjacent_list[at] = \ - [d for d in self.adjacent_list[at] if d.to != to] - self.adjacent_list[to] = \ - [d for d in self.adjacent_list[to] if d.at != at] + tracker.define(arg, node, argcell=argcell) def __repr__(self): graph = "graph([\n" - for i,l in enumerate(self.adjacent_list): - graph += " " + str(i) + ": " - for d in l: - if i == d.idx_from: - graph += str(d.idx_to) + "," - else: - graph += str(d.idx_from) + "," + for node in self.nodes: + graph += " " + str(node.opidx) + ": " + for dep in node.provides(): + graph += "=>" + str(dep.to.opidx) + "," + graph += " | " + for dep in node.depends(): + graph += "<=" + str(dep.to.opidx) + "," graph += "\n" return graph + " ])" - def loads_from_complex_object(self, op): - return rop._ALWAYS_PURE_LAST <= op.getopnum() <= rop._MALLOC_FIRST - - def modifies_complex_object(self, op): - return rop.SETARRAYITEM_GC <= op.getopnum() <= rop.UNICODESETITEM - - def as_dot(self, operations): + def as_dot(self): if not we_are_translated(): dot = "digraph dep_graph {\n" - for i in range(len(self.adjacent_list)): - op = operations[i] + for node in self.nodes: + op = node.getoperation() op_str = str(op) if op.is_guard(): op_str += " " + str(op.getfailargs()) - dot += " n%d [label=\"[%d]: %s\"];\n" % (i,i,op_str) + dot += " n%d [label=\"[%d]: %s\"];\n" % (node.getindex(),node.getindex(),op_str) dot += "\n" - for i,alist in enumerate(self.adjacent_list): - for dep in alist: - if dep.idx_to > i: - label = '' - if getattr(dep, 'label', None): - label = '[label="%s"]' % dep.label - dot += " n%d -> n%d %s;\n" % (i,dep.idx_to,label) - elif dep.idx_to == i and dep.idx_from > i: - label = '' - if getattr(dep, 'label', None): - label = '[label="%s"]' % dep.label - dot += " n%d -> n%d %s;\n" % (dep.idx_from,dep.idx_to,label) + for node in self.nodes: + for dep in node.provides(): + label = '' + if getattr(dep, 'label', None): + label = '[label="%s"]' % dep.label + dot += " n%d -> n%d %s;\n" % (node.getindex(),dep.to_index(),label) dot += "\n}\n" return dot raise NotImplementedError("dot cannot built at runtime") @@ -562,6 +575,7 @@ def schedule_all(self, opindices): while len(opindices) > 0: + print "sched" opidx = opindices.pop() for i,node in enumerate(self.schedulable_nodes): if node == opidx: @@ -586,7 +600,7 @@ # # TODO for dep in self.graph.provides(node): # candidate = dep.idx_to - self.graph.adjacent_list[node] = [] + node.clear_dependencies() def is_schedulable(self, idx): print "is sched", idx, "count:", self.graph.depends_count(idx), self.graph.adjacent_list[idx] @@ -610,7 +624,8 @@ return var additive_func_source = """ - def operation_{name}(self, op, index): + def operation_{name}(self, node): + op = node.op box_r = op.result if not box_r: return @@ -638,7 +653,8 @@ del additive_func_source multiplicative_func_source = """ - def operation_{name}(self, op, index): + def operation_{name}(self, node): + op = node.op box_r = op.result if not box_r: return @@ -670,10 +686,12 @@ del multiplicative_func_source array_access_source = """ - def operation_{name}(self, op, index): + def operation_{name}(self, node): + op = node.getoperation() descr = op.getdescr() idx_ref = self.get_or_create(op.getarg(1)) - self.memory_refs[index] = MemoryRef(op, idx_ref, {raw_access}) + node.memory_ref = MemoryRef(op, idx_ref, {raw_access}) + self.memory_refs[node] = node.memory_ref """ exec py.code.Source(array_access_source .format(name='RAW_LOAD',raw_access=True)).compile() 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,29 +8,17 @@ IndexVar, MemoryRef) from rpython.jit.metainterp.resoperation import rop, ResOperation -class IntWrapper(object): - def __init__(self,number): - self.transitive = False - number_s = str(number) - if number_s.endswith("?"): - self.transitive = True - self.number = int(number_s[:-1]) - else: - self.number = int(number_s) - def clone(self): - iw = IntWrapper(self.number) - iw.transitive = self.transitive - return iw - def __str__(self): - return str(self.number) - class DependencyBaseTest(BaseTest): - def build_dependency(self, ops, refs = False): + def setup_method(self, method): + self.test_name = method.__name__ + + def build_dependency(self, ops): loop = self.parse_loop(ops) self.last_graph = DependencyGraph(loop.operations) - for i in range(len(self.last_graph.adjacent_list)): - self.assert_independent(i,i) + self._write_dot_and_convert_to_svg(self.last_graph, self.test_name) + for node in self.last_graph.nodes: + assert node.independent(node) return self.last_graph def parse_loop(self, ops): @@ -42,77 +30,70 @@ loop.operations[-1].setdescr(token) return loop - def assert_edges(self, graph, edge_list): + def assert_edges(self, graph, edge_list, exceptions): """ 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) + assert len(edge_list) == len(graph.nodes) for idx,edges in enumerate(edge_list): if edges is None: continue - dependencies = graph.adjacent_list[idx][:] - for edge in edges: - if isinstance(edge,int): - edge = IntWrapper(edge) - dependency = graph.instr_dependency(idx,edge.number) - if edge < idx: - dependency = graph.instr_dependency(edge.number, idx) - if dependency is None and not edge.transitive: - self._write_dot_and_convert_to_svg(graph, graph.operations, 'except') + node_a = graph.getnode(idx) + dependencies = node_a.provides()[:] + for idx_b in edges: + node_b = graph.getnode(idx_b) + dependency = node_a.getedge_to(node_b) + if dependency is None and idx_b not in exceptions.setdefault(idx,[]): + #self._write_dot_and_convert_to_svg(graph, graph.nodes, 'except') assert dependency is not None, \ " it is expected that instruction at index" + \ " %s depends on instr on index %s but it does not.\n%s" \ - % (idx, edge, graph) + % (node_a, node_b, graph) elif dependency is not None: dependencies.remove(dependency) assert 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]) - def assert_dependencies(self, ops, memref=False, full_check=True): - graph = self.build_dependency(ops, memref) + def assert_dependencies(self, ops, full_check=True): + graph = self.build_dependency(ops) import re deps = {} + exceptions = {} 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 = [] - deps[label] = [IntWrapper(d) for d in line[dep_match.end():].split(',') if len(d) > 0] + deps[label] = [] + for to in [d for d in line[dep_match.end():].split(',') if len(d) > 0]: + exception = to.endswith("?") + if exception: + to = to[:-1] + exceptions.setdefault(label,[]).append(int(to)) + deps[label].append(int(to)) 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.number > k: - iw = IntWrapper(k) - iw.transitive = rk.transitive - edges[rk.number].append(iw) - self.assert_edges(graph, edges) + self.assert_edges(graph, edges, exceptions) 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) + a = self.last_graph.getnode(a) + b = self.last_graph.getnode(b) + assert a.independent(b), "{a} and {b} are dependent!".format(a=a,b=b) def assert_dependent(self, a, b): - assert not self.last_graph.independent(a,b), "{a} and {b} are independent!".format(a=a,b=b) + a = self.last_graph.getnode(a) + b = self.last_graph.getnode(b) + assert not a.independent(b), "{a} and {b} are independent!".format(a=a,b=b) - def _write_dot_and_convert_to_svg(self, graph, ops, filename): - dot = graph.as_dot(ops) + def _write_dot_and_convert_to_svg(self, graph, filename): + dot = graph.as_dot() with open('/tmp/_'+filename+'.dot', 'w') as fd: fd.write(dot) with open('/tmp/'+filename+'.svg', 'w') as fd: @@ -136,6 +117,10 @@ assert not m1.is_adjacent_to(m2) assert not m2.is_adjacent_to(m1) + def getmemref(self, idx): + node = self.last_graph.getnode(idx) + return self.last_graph.memory_refs[node] + class BaseTestDependencyGraph(DependencyBaseTest): def test_dependency_empty(self): @@ -333,8 +318,8 @@ setarrayitem_raw(p0, i2, 2, descr=chararraydescr) # 3: 4 jump(p0, i1) # 4: """ - self.assert_dependencies(ops, memref=True, full_check=True) - assert len(self.last_graph.adjacent_list[1]) > 1 + self.assert_dependencies(ops, full_check=True) + assert self.last_graph.getnode(1).provides_count() == 1 self.assert_independent(1,2) self.assert_independent(1,3) # they modify 2 different cells @@ -363,7 +348,7 @@ guard_true(i25) [i7, i22, i5, i4, i3, i21, i19, i24] # 20: jump(i24, i19, i21, i3, i4, i5, i22, i7) # 21: """ - self.assert_dependencies(ops, memref=True, full_check=False) + self.assert_dependencies(ops, full_check=False) self.assert_dependent(2,12) class TestLLtype(BaseTestDependencyGraph, LLtypeMixin): 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 @@ -28,23 +28,12 @@ jitdriver_sd = FakeJitDriverStaticData() - def setup_method(self, method): - self.test_name = method.__name__ - - def build_dependency(self, ops): - loop = self.parse_loop(ops) - graph = DependencyGraph(loop) - self.assert_acyclic(graph) - return graph - - def assert_acyclic(self, graph): - pass - def parse_loop(self, ops): loop = self.parse(ops, postprocess=self.postprocess) token = JitCellToken() - loop.operations = [ResOperation(rop.LABEL, loop.inputargs, None, - descr=TargetToken(token))] + loop.operations + loop.operations = \ + [ResOperation(rop.LABEL, loop.inputargs, None, descr=TargetToken(token))] + \ + loop.operations if loop.operations[-1].getopnum() == rop.JUMP: loop.operations[-1].setdescr(token) return loop @@ -71,6 +60,7 @@ opt.clear_newoperations() opt.build_dependency_graph() self.last_graph = opt.dependency_graph + self._write_dot_and_convert_to_svg(self.last_graph, self.test_name) return opt def init_packset(self, loop, unroll_factor = -1): @@ -80,7 +70,6 @@ def extend_packset(self, loop, unroll_factor = -1): opt = self.vectoroptimizer_unrolled(loop, unroll_factor) - self._write_dot_and_convert_to_svg(opt.dependency_graph, opt.loop.operations, 'extend_packset') opt.find_adjacent_memory_refs() opt.extend_packset() return opt @@ -95,7 +84,6 @@ def schedule(self, loop, unroll_factor = -1): opt = self.vectoroptimizer_unrolled(loop, unroll_factor) opt.find_adjacent_memory_refs() - self._write_dot_and_convert_to_svg(opt.dependency_graph, opt.loop.operations, self.test_name) opt.extend_packset() opt.combine_packset() opt.schedule() @@ -148,6 +136,11 @@ else: pytest.fail("can't find a pack set for indices {x},{y}" \ .format(x=x,y=y)) + def assert_has_memory_ref_at(self, idx): + node = self.last_graph.nodes[idx] + assert node in self.last_graph.memory_refs, \ + "operation %s at pos %d has no memory ref!" % \ + (node.getoperation(), node.getindex()) class BaseTestVectorize(VecTestHelper): @@ -193,11 +186,13 @@ it is unrolled 16 times. (it is the smallest type in the trace) """ ops = """ [p0,i0] + guard_no_early_exit() [] raw_load(p0,i0,descr=chararraydescr) jump(p0,i0) """ opt_ops = """ [p0,i0] + guard_no_early_exit() [] {} jump(p0,i0) """.format(('\n' + ' ' *8).join(['raw_load(p0,i0,descr=chararraydescr)'] * 16)) @@ -254,9 +249,8 @@ jump(p0,i0) """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) - vopt.build_dependency_graph() - assert 1 in vopt.dependency_graph.memory_refs assert len(vopt.dependency_graph.memory_refs) == 1 + self.assert_has_memory_ref_at(1) def test_array_operation_indices_unrolled_1(self): ops = """ @@ -265,10 +259,9 @@ jump(p0,i0) """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),1) - vopt.build_dependency_graph() - assert 1 in vopt.dependency_graph.memory_refs - assert 2 in vopt.dependency_graph.memory_refs assert len(vopt.dependency_graph.memory_refs) == 2 + self.assert_has_memory_ref_at(1) + self.assert_has_memory_ref_at(2) def test_array_operation_indices_unrolled_2(self): ops = """ @@ -279,17 +272,19 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.build_dependency_graph() - assert 1 in vopt.dependency_graph.memory_refs - assert 2 in vopt.dependency_graph.memory_refs assert len(vopt.dependency_graph.memory_refs) == 2 + self.assert_has_memory_ref_at(1) + self.assert_has_memory_ref_at(2) + # vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),1) + assert len(vopt.dependency_graph.memory_refs) == 4 for i in [1,2,3,4]: - assert i in vopt.dependency_graph.memory_refs - assert len(vopt.dependency_graph.memory_refs) == 4 + self.assert_has_memory_ref_at(i) + # vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),3) + assert len(vopt.dependency_graph.memory_refs) == 8 for i in [1,2,3,4,5,6,7,8]: - assert i in vopt.dependency_graph.memory_refs - assert len(vopt.dependency_graph.memory_refs) == 8 + self.assert_has_memory_ref_at(i) def test_array_memory_ref_adjacent_1(self): ops = """ @@ -300,15 +295,15 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),1) self.assert_edges(vopt.dependency_graph, - [ [1,2,3,5], [0,5], [0,3,4], [0,2,5], [2,5], [0,4,1,3] ]) + [ [1,2,3,5], [5], [3,4], [5], [5], [] ], {}) vopt.find_adjacent_memory_refs() - assert 1 in vopt.dependency_graph.memory_refs - assert 3 in vopt.dependency_graph.memory_refs + self.assert_has_memory_ref_at(1) + self.assert_has_memory_ref_at(3) assert len(vopt.dependency_graph.memory_refs) == 2 - mref1 = vopt.dependency_graph.memory_refs[1] - mref3 = vopt.dependency_graph.memory_refs[3] + mref1 = self.getmemref(1) + mref3 = self.getmemref(3) assert isinstance(mref1, MemoryRef) assert isinstance(mref3, MemoryRef) @@ -323,7 +318,7 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref1 = vopt.dependency_graph.memory_refs[1] + mref1 = self.getmemref(1) assert isinstance(mref1, MemoryRef) assert mref1.index_var.coefficient_mul == 1 assert mref1.index_var.constant == 0 @@ -337,7 +332,7 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref1 = vopt.dependency_graph.memory_refs[2] + mref1 = self.getmemref(2) assert isinstance(mref1, MemoryRef) assert mref1.index_var.coefficient_mul == 1 assert mref1.index_var.constant == 1 @@ -351,7 +346,7 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref1 = vopt.dependency_graph.memory_refs[2] + mref1 = self.getmemref(2) assert isinstance(mref1, MemoryRef) assert mref1.index_var.coefficient_mul == 1 assert mref1.index_var.constant == -1 @@ -366,7 +361,7 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref1 = vopt.dependency_graph.memory_refs[3] + mref1 = self.getmemref(3) assert isinstance(mref1, MemoryRef) assert mref1.index_var.coefficient_mul == 3 assert mref1.index_var.constant == 3 @@ -383,7 +378,7 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref1 = vopt.dependency_graph.memory_refs[5] + mref1 = self.getmemref(5) assert isinstance(mref1, MemoryRef) assert mref1.index_var.coefficient_mul == 18 assert mref1.index_var.constant == 48 @@ -401,7 +396,7 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref1 = vopt.dependency_graph.memory_refs[7] + mref1 = self.getmemref(7) assert isinstance(mref1, MemoryRef) assert mref1.index_var.coefficient_mul == 1026 assert mref1.index_var.coefficient_div == 1 @@ -419,7 +414,7 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref1 = vopt.dependency_graph.memory_refs[5] + mref1 = self.getmemref(5) assert isinstance(mref1, MemoryRef) assert mref1.index_var.coefficient_mul == 6 assert mref1.index_var.coefficient_div == 1 @@ -450,21 +445,21 @@ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),1) self.assert_edges(vopt.dependency_graph, [ [1,2,3,4,5,7,9], - [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], - ]) + [9], [5,6], [9], [7,8], + [9], [9], [9], [9], + [], + ], {}) vopt.find_adjacent_memory_refs() for i in [1,3,5,7]: - assert i in vopt.dependency_graph.memory_refs + self.assert_has_memory_ref_at(i) assert len(vopt.dependency_graph.memory_refs) == 4 - mref1 = vopt.dependency_graph.memory_refs[1] - mref3 = vopt.dependency_graph.memory_refs[3] - mref5 = vopt.dependency_graph.memory_refs[5] - mref7 = vopt.dependency_graph.memory_refs[7] + mref1 = self.getmemref(1) + mref3 = self.getmemref(3) + mref5 = self.getmemref(5) + mref7 = self.getmemref(7) assert isinstance(mref1, MemoryRef) assert isinstance(mref3, MemoryRef) assert isinstance(mref5, MemoryRef) @@ -486,7 +481,7 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref = vopt.dependency_graph.memory_refs[3] + mref = self.getmemref(3) assert mref.index_var.coefficient_div == 16 ops = """ [p0,i0] @@ -497,7 +492,7 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref = vopt.dependency_graph.memory_refs[3] + mref = self.getmemref(3) assert mref.index_var.coefficient_div == 2 assert mref.index_var.constant == 4 ops = """ @@ -512,8 +507,8 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref = vopt.dependency_graph.memory_refs[3] - mref2 = vopt.dependency_graph.memory_refs[6] + mref = self.getmemref(3) + mref2 = self.getmemref(6) self.assert_memory_ref_not_adjacent(mref, mref2) assert mref != mref2 @@ -532,8 +527,8 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref = vopt.dependency_graph.memory_refs[3] - mref2 = vopt.dependency_graph.memory_refs[7] + mref = self.getmemref(3) + mref2 = self.getmemref(7) self.assert_memory_ref_not_adjacent(mref, mref2) assert mref == mref2 @@ -552,8 +547,8 @@ """ vopt = self.vectoroptimizer_unrolled(self.parse_loop(ops),0) vopt.find_adjacent_memory_refs() - mref = vopt.dependency_graph.memory_refs[3] - mref2 = vopt.dependency_graph.memory_refs[7] + mref = self.getmemref(3) + mref2 = self.getmemref(7) self.assert_memory_ref_not_adjacent(mref, mref2) assert mref != mref2 @@ -580,7 +575,7 @@ """ loop = self.parse_loop(ops) vopt = self.init_packset(loop,1) - assert vopt.dependency_graph.independent(1,5) + self.assert_independent(1,5) assert vopt.packset is not None assert len(vopt.dependency_graph.memory_refs) == 2 assert len(vopt.packset.packs) == 1 @@ -608,7 +603,7 @@ for i in range(3): x = (i+1)*2 y = x + 2 - assert vopt.dependency_graph.independent(x,y) + self.assert_independent(x,y) self.assert_packset_contains_pair(vopt.packset, x,y) def test_packset_init_2(self): @@ -629,19 +624,19 @@ for j in range(15): try: if i-4 == j or i+4 == j: - mref1 = vopt.dependency_graph.memory_refs[i] - mref2 = vopt.dependency_graph.memory_refs[j] + mref1 = self.getmemref(i) + mref2 = self.getmemref(j) assert mref1.is_adjacent_to(mref2) else: - mref1 = vopt.dependency_graph.memory_refs[i] - mref2 = vopt.dependency_graph.memory_refs[j] + mref1 = self.getmemref(i) + mref2 = self.getmemref(j) assert not mref1.is_adjacent_to(mref2) except KeyError: pass for i in range(15): x = (i+1)*4 y = x + 4 - assert vopt.dependency_graph.independent(x,y) + self.assert_independent(x,y) self.assert_packset_contains_pair(vopt.packset, x, y) def test_isomorphic_operations(self): @@ -680,7 +675,7 @@ loop = self.parse_loop(ops) vopt = self.extend_packset(loop,1) assert len(vopt.dependency_graph.memory_refs) == 2 - assert vopt.dependency_graph.independent(5,10) == True + self.assert_independent(5,10) assert len(vopt.packset.packs) == 2 self.assert_packset_empty(vopt.packset, len(loop.operations), [(5,10), (4,9)]) @@ -699,9 +694,9 @@ loop = self.parse_loop(ops) vopt = self.extend_packset(loop,1) assert len(vopt.dependency_graph.memory_refs) == 4 - assert vopt.dependency_graph.independent(4,10) - assert vopt.dependency_graph.independent(5,11) - assert vopt.dependency_graph.independent(6,12) + self.assert_independent(4,10) + self.assert_independent(5,11) + self.assert_independent(6,12) assert len(vopt.packset.packs) == 3 self.assert_packset_empty(vopt.packset, len(loop.operations), [(5,11), (4,10), (6,12)]) 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 @@ -5,7 +5,7 @@ from rpython.jit.metainterp.optimizeopt.optimizer import Optimizer, Optimization from rpython.jit.metainterp.optimizeopt.util import make_dispatcher_method from rpython.jit.metainterp.optimizeopt.dependency import (DependencyGraph, - MemoryRef, Scheduler, SchedulerData) + MemoryRef, Scheduler, SchedulerData, Node) from rpython.jit.metainterp.resoperation import (rop, ResOperation) from rpython.jit.metainterp.resume import Snapshot from rpython.rlib.debug import debug_print, debug_start, debug_stop @@ -61,10 +61,6 @@ def_opt = Optimizer(metainterp_sd, jitdriver_sd, loop, optimizations) def_opt.propagate_all_forward() -class OpWrapper(object): - def __init__(self, op, opidx): - self.op = op - class VectorizingOptimizer(Optimizer): """ Try to unroll the loop and find instructions to group """ @@ -252,7 +248,7 @@ def build_dependency_graph(self): self.dependency_graph = DependencyGraph(self.loop.operations) - self.relax_guard_dependencies() + #self.relax_guard_dependencies() def find_adjacent_memory_refs(self): """ the pre pass already builds a hash of memory references and the @@ -269,20 +265,18 @@ self.smallest_type_bytes) memory_refs = self.dependency_graph.memory_refs.items() # initialize the pack set - for a_opidx,a_memref in memory_refs: - for b_opidx,b_memref in memory_refs: + for node_a,memref_a in memory_refs: + for node_b,memref_b in memory_refs: # instead of compare every possible combination and # exclue a_opidx == b_opidx only consider the ones # that point forward: - if a_opidx < b_opidx: - #print "point forward[", a_opidx, "]", a_memref, "[",b_opidx,"]", b_memref - if a_memref.is_adjacent_to(b_memref): - #print " -> adjacent[", a_opidx, "]", a_memref, "[",b_opidx,"]", b_memref - if self.packset.can_be_packed(a_opidx, b_opidx, - a_memref, b_memref): - #print " =-=-> can be packed[", a_opidx, "]", a_memref, "[",b_opidx,"]", b_memref - self.packset.add_pair(a_opidx, b_opidx, - a_memref, b_memref) + if node_a.is_before(node_b): + #print "point forward[", a_opidx, "]", memref_a, "[",b_opidx,"]", memref_b + if memref_a.is_adjacent_to(memref_b): + #print " -> adjacent[", a_opidx, "]", memref_a, "[",b_opidx,"]", memref_b + if self.packset.can_be_packed(node_a, node_b): + #print " =-=-> can be packed[", a_opidx, "]", memref_a, "[",b_opidx,"]", memref_b + self.packset.add_pair(node_a, node_b) def extend_packset(self): pack_count = self.packset.pack_count() @@ -296,36 +290,30 @@ def follow_use_defs(self, pack): assert isinstance(pack, Pair) - lref = pack.left.memref - rref = pack.right.memref - for ldef in self.dependency_graph.depends(pack.left.opidx): - for rdef in self.dependency_graph.depends(pack.right.opidx): - ldef_idx = ldef.idx_from - rdef_idx = rdef.idx_from - if ldef_idx != rdef_idx and \ - self.packset.can_be_packed(ldef_idx, rdef_idx, lref, rref): - savings = self.packset.estimate_savings(ldef_idx, rdef_idx, - pack, False) + for ldep in pack.left.depends(): + for rdep in pack.right.depends(): + lnode = ldep.to + rnode = rdep.to + if lnode != rnode and self.packset.can_be_packed(lnode, rnode): + savings = self.packset.estimate_savings(lnode, rnode, pack, False) if savings >= 0: - self.packset.add_pair(ldef_idx, rdef_idx, lref, rref) + self.packset.add_pair(lnode, rnode) def follow_def_uses(self, pack): assert isinstance(pack, Pair) savings = -1 candidate = (-1,-1, None, None) - lref = pack.left.memref - rref = pack.right.memref - for luse in self.dependency_graph.provides(pack.left.opidx): - for ruse in self.dependency_graph.provides(pack.right.opidx): - luse_idx = luse.idx_to - ruse_idx = ruse.idx_to - if luse_idx != ruse_idx and \ - self.packset.can_be_packed(luse_idx, ruse_idx, lref, rref): - est_savings = self.packset.estimate_savings(luse_idx, ruse_idx, - pack, True) + for ldep in pack.left.depends(): + for rdep in pack.right.depends(): + lnode = ldep.to + rnode = rdep.to + if lnode != rnode and \ + self.packset.can_be_packed(lnode, rnode): + est_savings = \ + self.packset.estimate_savings(lnode, rnode, pack, True) if est_savings > savings: savings = est_savings - candidate = (luse_idx, ruse_idx, lref, rref) + candidate = (lnode, rnode) # if savings >= 0: self.packset.add_pair(*candidate) @@ -360,13 +348,12 @@ self.clear_newoperations() scheduler = Scheduler(self.dependency_graph, VecScheduleData()) while scheduler.has_more_to_schedule(): - candidate_index = scheduler.next_schedule_index() - candidate = self.loop.operations[candidate_index] - pack = self.packset.pack_for_operation(candidate, candidate_index) + candidate = scheduler.next_to_schedule() + pack = self.packset.pack_for_operation(candidate) if pack: self._schedule_pack(scheduler, pack) else: - self.emit_operation(candidate) + self.emit_operation(candidate.getoperation()) scheduler.schedule(0) self.loop.operations = self._newoperations[:] @@ -547,19 +534,16 @@ def pack_count(self): return len(self.packs) - def add_pair(self, lidx, ridx, lmemref=None, rmemref=None): - l = PackOpWrapper(lidx, lmemref) - r = PackOpWrapper(ridx, rmemref) + def add_pair(self, l, r): self.packs.append(Pair(l,r)) - 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): - if self.dependency_graph.independent(lop_idx, rop_idx): + def can_be_packed(self, lnode, rnode): + if isomorphic(lnode.getoperation(), rnode.getoperation()): + if lnode.independent(rnode): for pack in self.packs: - if pack.left.opidx == lop_idx or \ - pack.right.opidx == rop_idx: + # TODO save pack on Node + if pack.left.opidx == lnode.getindex() or \ + pack.right.opidx == rnode.getindex(): return False return True return False @@ -612,10 +596,10 @@ del self.packs[last_pos] return last_pos - def pack_for_operation(self, op, opidx): + def pack_for_operation(self, node): for pack in self.packs: - for op in pack.operations: - if op.getopidx() == opidx: + for node2 in pack.operations: + if node == node2: return pack return None @@ -640,8 +624,8 @@ class Pair(Pack): """ A special Pack object with only two statements. """ def __init__(self, left, right): - assert isinstance(left, PackOpWrapper) - assert isinstance(right, PackOpWrapper) + assert isinstance(left, Node) + assert isinstance(right, Node) self.left = left self.right = right Pack.__init__(self, [left, right]) @@ -650,20 +634,3 @@ if isinstance(other, Pair): 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 getopidx(self): - return self.opidx - - def __eq__(self, other): - if isinstance(other, PackOpWrapper): - return self.opidx == other.opidx and self.memref == other.memref - return False - - def __repr__(self): - return "PackOpWrapper(%d, %r)" % (self.opidx, self.memref) - _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit