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
