Author: Richard Plangger <r...@pasra.at>
Branch: vecopt2
Changeset: r77094:e515a3389dbb
Date: 2015-03-26 17:24 +0100
http://bitbucket.org/pypy/pypy/changeset/e515a3389dbb/
Log: dependency graph now tracks array modifications and discards edges
of proven cell access to not overlap
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
@@ -1,4 +1,5 @@
-from rpython.jit.metainterp.optimizeopt.util import MemoryRef
+import py
+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
@@ -52,13 +53,12 @@
self.defs = {}
def define(self, arg, index, argcell=None):
- print "def", arg, "at", index, "cell", argcell
if arg in self.defs:
self.defs[arg].append((index,argcell))
else:
self.defs[arg] = [(index,argcell)]
- def definition_index(self, arg, index, argcell=None):
+ def definition_index(self, arg, index = -1, argcell=None):
def_chain = self.defs[arg]
if len(def_chain) == 1:
return def_chain[0][0]
@@ -66,13 +66,16 @@
if argcell == None:
return def_chain[-1][0]
else:
+ assert index != -1
i = len(def_chain)-1
try:
mref = self.memory_refs[index]
while i >= 0:
def_index = def_chain[i][0]
- oref = self.memory_refs[def_index]
- if mref.indices_can_alias(oref):
+ oref = self.memory_refs.get(def_index)
+ if oref is not None and mref.indices_can_alias(oref):
+ return def_index
+ elif oref is None:
return def_index
i -= 1
except KeyError:
@@ -102,8 +105,8 @@
self.operations = operations
self.memory_refs = memory_refs
self.adjacent_list = [ [] for i in range(len(self.operations)) ]
+ self.integral_mod = IntegralMod()
self.build_dependencies(self.operations)
- self.integral_mod = IntegralMod()
def build_dependencies(self, operations):
""" This is basically building the definition-use chain and saving this
@@ -134,7 +137,6 @@
for arg in op.getarglist():
self._def_use(arg, i, tracker)
else:
- self.update_memory_ref(op, i, integral_mod)
self.put_edges_for_complex_objects(op, i, tracker)
# guard specifics
@@ -144,27 +146,32 @@
if i > 0:
self._guard_dependency(op, i, operations, tracker)
- def update_memory_ref(self, op, index):
+ def update_memory_ref(self, op, index, tracker):
if index not in self.memory_refs:
return
memref = self.memory_refs[index]
self.integral_mod.reset()
+ try:
+ curidx = tracker.definition_index(memref.origin)
+ except KeyError:
+ return
+ curop = self.operations[curidx]
while True:
- for dep in self.get_defs(index):
- op = operations[dep.idx_from]
- if op.result == memref.origin:
- index = dep.idx_from
- break
- else:
- break # cannot go further, this might be the label, or a
constant
- self.integral_mod.inspect_operation(op)
+ 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.get_defs(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 put_edges_for_complex_objects(self, op, index, tracker):
- self.update_memory_ref(op, index)
+ self.update_memory_ref(op, index, tracker)
if self.loads_from_complex_object(op):
# If this complex object load operation loads an index that has
been
# modified, the last modification should be used to put a def-use
edge.
@@ -189,7 +196,7 @@
try:
# A trace is not in SSA form, but this complex
object
# modification introduces a WAR/WAW dependency
- def_idx = tracker.definition_index(arg, index)
+ def_idx = tracker.definition_index(arg)
for dep in self.get_uses(def_idx):
if dep.idx_to >= index:
break
@@ -368,11 +375,6 @@
opnum = op.getopnum()
return rop.SETARRAYITEM_GC<= opnum and opnum <= rop.UNICODESETITEM
-
-# Utilities for array references.
-# Needed by dependency.py and vectorize.py
-# ____________________________________________________________
-
class IntegralMod(object):
""" Calculates integral modifications on an integer object.
The operations must be provided in backwards direction and of one
@@ -380,8 +382,7 @@
See MemoryRef for an example.
"""
- def __init__(self, optimizer):
- self.optimizer = optimizer
+ def __init__(self):
self.reset()
def reset(self):
@@ -403,17 +404,15 @@
def operation_{name}(self, op):
box_a0 = op.getarg(0)
box_a1 = op.getarg(1)
- a0 = self.optimizer.getvalue(box_a0)
- a1 = self.optimizer.getvalue(box_a1)
self.is_const_mod = True
- if self.is_const_integral(a0) and self.is_const_integral(a1):
+ if self.is_const_integral(box_a0) and self.is_const_integral(box_a1):
self.used_box = None
self.constant += self._update_additive(box_a0.getint() {op} \
box_a1.getint())
- elif self.is_const_integral(a0):
+ elif self.is_const_integral(box_a0):
self.constant {op}= self._update_additive(box_a0.getint())
self.used_box = box_a1
- elif self.is_const_integral(a1):
+ elif self.is_const_integral(box_a1):
self.constant {op}= self._update_additive(box_a1.getint())
self.used_box = box_a0
else:
@@ -429,19 +428,17 @@
def operation_{name}(self, op):
box_a0 = op.getarg(0)
box_a1 = op.getarg(1)
- a0 = self.optimizer.getvalue(box_a0)
- a1 = self.optimizer.getvalue(box_a1)
self.is_const_mod = True
- if self.is_const_integral(a0) and self.is_const_integral(a1):
+ if self.is_const_integral(box_a0) and self.is_const_integral(box_a1):
# here this factor becomes a constant, thus it is
# handled like any other additive operation
self.used_box = None
self.constant += self._update_additive(box_a0.getint() {cop} \
box_a1.getint())
- elif a0.is_constant():
+ elif self.is_const_integral(box_a0):
self.coefficient_{tgt} {op}= box_a0.getint()
self.used_box = box_a1
- elif self.is_const_integral(a1):
+ elif self.is_const_integral(box_a1):
self.coefficient_{tgt} {op}= box_a1.getint()
self.used_box = box_a0
else:
@@ -511,7 +508,7 @@
"""
match, off = self.calc_difference(other)
if match:
- return off != 0
+ return off == 0
return False
def __eq__(self, other):
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
@@ -4,19 +4,21 @@
LLtypeMixin, BaseTest, FakeMetaInterpStaticData,
convert_old_style_to_targets)
from rpython.jit.metainterp.history import TargetToken, JitCellToken, TreeLoop
from rpython.jit.metainterp.optimizeopt.dependency import (DependencyGraph,
Dependency,
- IntegralMod)
+ IntegralMod, MemoryRef)
+from rpython.jit.metainterp.optimizeopt.vectorize import LoopVectorizeInfo
from rpython.jit.metainterp.resoperation import rop, ResOperation
class DepTestHelper(BaseTest):
- def build_dependency(self, ops, memory_refs = False):
+ def build_dependency(self, ops, refs = False):
loop = self.parse_loop(ops)
- refs = {}
- if memory_refs:
- opt = Optimizer(None, None, loop)
-
-
- self.last_graph = DependencyGraph(loop.operations, refs)
+ lvi = LoopVectorizeInfo()
+ if refs:
+ lvi.track_memory_refs = True
+ for i,op in enumerate(loop.operations):
+ lvi.index = i
+ lvi.inspect_operation(op)
+ self.last_graph = DependencyGraph(loop.operations, lvi.memory_refs)
for i in range(len(self.last_graph.adjacent_list)):
self.assert_independent(i,i)
return self.last_graph
@@ -298,12 +300,12 @@
setarrayitem_raw(p0, i2, 2, descr=floatarraydescr) #2
jump(p0, i1)
"""
+ dep_graph = self.build_dependency(ops, True)
+ self.assert_edges(dep_graph,
+ [ [1,2,3,4], [0], [0,3], [0,2,4], [0,3] ])
dep_graph = self.build_dependency(ops)
self.assert_edges(dep_graph,
- [ [1,2,4], [0,3], [0,3], [0,1,2,4], [0,3] ])
- dep_graph = self.build_dependency(ops, memory_refs=True)
- self.assert_edges(dep_graph,
- [ [1,2,3,4], [0], [0,3], [0,2,4], [0,3] ])
+ [ [1,2,4], [0,3], [0,3], [1,2,4], [0,3] ])
class TestLLtype(BaseTestDependencyGraph, LLtypeMixin):
pass
diff --git a/rpython/jit/metainterp/optimizeopt/vectorize.py
b/rpython/jit/metainterp/optimizeopt/vectorize.py
--- a/rpython/jit/metainterp/optimizeopt/vectorize.py
+++ b/rpython/jit/metainterp/optimizeopt/vectorize.py
@@ -2,9 +2,9 @@
import py
from rpython.rtyper.lltypesystem import lltype, rffi
from rpython.jit.metainterp.optimizeopt.optimizer import Optimizer,
Optimization
-from rpython.jit.metainterp.optimizeopt.util import (make_dispatcher_method,
+from rpython.jit.metainterp.optimizeopt.util import make_dispatcher_method
+from rpython.jit.metainterp.optimizeopt.dependency import (DependencyGraph,
MemoryRef, IntegralMod)
-from rpython.jit.metainterp.optimizeopt.dependency import DependencyGraph
from rpython.jit.metainterp.resoperation import rop
from rpython.jit.metainterp.resume import Snapshot
from rpython.rlib.debug import debug_print, debug_start, debug_stop
@@ -31,7 +31,7 @@
def __init__(self, metainterp_sd, jitdriver_sd, loop, optimizations):
Optimizer.__init__(self, metainterp_sd, jitdriver_sd, loop,
optimizations)
- self.vec_info = LoopVectorizeInfo(self)
+ self.vec_info = LoopVectorizeInfo()
self.memory_refs = []
self.dependency_graph = None
self.first_debug_merge_point = False
@@ -71,6 +71,7 @@
op = loop.operations[i].clone()
operations.append(op)
self.emit_unrolled_operation(op)
+ self.vec_info.index = len(self._newoperations)-1
self.vec_info.inspect_operation(op)
orig_jump_args = jump_op.getarglist()[:]
@@ -112,6 +113,7 @@
copied_op.result = new_assigned_box
#
self.emit_unrolled_operation(copied_op)
+ self.vec_info.index = len(self._newoperations)-1
self.vec_info.inspect_operation(copied_op)
# the jump arguments have been changed
@@ -343,22 +345,19 @@
return self.opidx == other.opidx and self.memref == other.memref
return False
-
-
class LoopVectorizeInfo(object):
- def __init__(self, optimizer):
- self.optimizer = optimizer
+ def __init__(self):
self.smallest_type_bytes = 0
self.memory_refs = {}
self.track_memory_refs = False
+ self.index = 0
array_access_source = """
def operation_{name}(self, op):
descr = op.getdescr()
if self.track_memory_refs:
- idx = len(self.optimizer._newoperations)-1
- self.memory_refs[idx] = \
+ self.memory_refs[self.index] = \
MemoryRef(op.getarg(0), op.getarg(1), op.getdescr())
if not descr.is_array_of_pointers():
byte_count = descr.get_item_size_in_bytes()
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
