Author: Richard Plangger <r...@pasra.at> Branch: vecopt2 Changeset: r77107:6aa7a2193f3f Date: 2015-04-08 18:18 +0200 http://bitbucket.org/pypy/pypy/changeset/6aa7a2193f3f/
Log: updated tests to ignore non present transitive dependencies, nearly completed the new integral forward modification migration 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 @@ -72,7 +72,7 @@ while i >= 0: def_index = def_chain[i][0] oref = self.memory_refs.get(def_index) - if oref is not None and mref.indices_can_alias(oref): + if oref is not None and not mref.indices_can_alias(oref): return def_index elif oref is None: return def_index @@ -88,6 +88,8 @@ * True dependency * Anti dependency (not present in SSA traces) * Ouput dependency (not present in SSA traces) + Traces in RPython are not in SSA form when it comes to complex + object modification such as array or object side effects. Representation is an adjacent list. The number of edges between the vertices is expected to be small. Note that adjacent lists order their dependencies. They are ordered @@ -100,15 +102,14 @@ modifications of one array even if the indices can never point to the same element. """ - def __init__(self, operations, memory_refs): + def __init__(self, operations): self.operations = operations - self.memory_refs = memory_refs + self.memory_refs = {} self.adjacent_list = [ [] for i in range(len(self.operations)) ] - self.integral_mod = IntegralMod() self.schedulable_nodes = [0] # label is always scheduleable - self.build_dependencies() self.index_vars = {} self.guards = [] + self.build_dependencies() def build_dependencies(self): """ This is basically building the definition-use chain and saving this @@ -120,7 +121,7 @@ """ tracker = DefTracker(self.memory_refs) # - intformod = IntegralForwardModification(self.index_vars) + intformod = IntegralForwardModification(self.memory_refs, self.index_vars) # pass 1 for i,op in enumerate(self.operations): # the label operation defines all operations at the @@ -132,6 +133,7 @@ assert arg not in self.index_vars self.index_vars[arg] = IndexVar(arg) continue # prevent adding edge to the label itself + intformod.inspect_operation(op, i) # definition of a new variable if op.result is not None: # In SSA form. Modifications get a new variable @@ -145,7 +147,6 @@ self.guards.append(i) else: self._build_non_pure_dependencies(op, i, tracker) - intformod.inspect_operation(op, i) # pass 2 correct guard dependencies for guard_idx in self.guards: self._build_guard_dependencies(guard_idx, op.getopnum(), tracker) @@ -236,7 +237,7 @@ self._put_edge(guard_idx, dep.idx_to, None) def _build_non_pure_dependencies(self, op, index, tracker): - self._update_memory_ref(op, index, tracker) + # 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. @@ -463,7 +464,7 @@ dot += " n%d -> n%d;\n" % (i,dep.idx_to) dot += "\n}\n" return dot - return "" + raise NotImplementedError("dot cannot built at runtime") class SchedulerData(object): pass @@ -523,8 +524,9 @@ class IntegralForwardModification(object): """ Calculates integral modifications on an integer box. """ - def __init__(self, index_vars): + def __init__(self, memory_refs, index_vars): self.index_vars = index_vars + self.memory_refs = memory_refs def is_const_integral(self, box): if isinstance(box, ConstInt): @@ -540,27 +542,27 @@ box_a1 = op.getarg(1) if self.is_const_integral(box_a0) and self.is_const_integral(box_a1): idx_ref = IndexVar(box_r) - idx_ref.constant = box_a0.getint() {op} box_a1.getint()) + idx_ref.constant = box_a0.getint() {op} box_a1.getint() self.index_vars[box_r] = idx_ref elif self.is_const_integral(box_a0): + idx_ref = self.index_vars[box_a1] + idx_ref = idx_ref.clone() + idx_ref.constant {op}= box_a1.getint() + self.index_vars[box_r] = idx_ref + elif self.is_const_integral(box_a1): idx_ref = self.index_vars[box_a0] - idx_ref = idx_ref.clone(box_r) + idx_ref = idx_ref.clone() idx_ref.constant {op}= box_a0.getint() self.index_vars[box_r] = idx_ref - elif self.is_const_integral(box_a1): - idx_ref = self.index_vars[box_a1] - idx_ref = idx_ref.clone(box_r) - idx_ref.constant {op}= box_a1.getint() - self.index_vars[box_r] = idx_ref """ - exec py.code.Source(additive_func_source.format(name='INT_ADD', - op='+')).compile() - exec py.code.Source(additive_func_source.format(name='INT_SUB', - op='-')).compile() + exec py.code.Source(additive_func_source + .format(name='INT_ADD', op='+')).compile() + exec py.code.Source(additive_func_source + .format(name='INT_SUB', op='-')).compile() del additive_func_source multiplicative_func_source = """ - def operation_{name}(self, op): + def operation_{name}(self, op, index): box_r = op.result if not box_r: return @@ -568,129 +570,52 @@ box_a1 = op.getarg(1) if self.is_const_integral(box_a0) and self.is_const_integral(box_a1): idx_ref = IndexVar(box_r) - idx_ref.constant = box_a0.getint() {cop} box_a1.getint()) + idx_ref.constant = box_a0.getint() {cop} box_a1.getint() self.index_vars[box_r] = idx_ref elif self.is_const_integral(box_a0): - idx_ref = self.index_vars[box_a0] - idx_ref = idx_ref.clone(box_r) - self.coefficient_{tgt} *= box_a0.getint() - self.constant {cop}= box_a0.getint() + idx_ref = self.index_vars[box_a1] + idx_ref = idx_ref.clone() + idx_ref.coefficient_{tgt} *= box_a1.getint() + idx_ref.constant {cop}= box_a1.getint() self.index_vars[box_r] = idx_ref elif self.is_const_integral(box_a1): - idx_ref = self.index_vars[box_a1] - idx_ref = idx_ref.clone(box_r) - self.coefficient_{tgt} {op}= box_a1.getint() - self.constant {cop}= box_a1.getint() + idx_ref = self.index_vars[box_a0] + idx_ref = idx_ref.clone() + idx_ref.coefficient_{tgt} {op}= box_a0.getint() + idx_ref.constant {cop}= box_a0.getint() self.index_vars[box_r] = idx_ref """ - exec py.code.Source(multiplicative_func_source.format(name='INT_MUL', - op='*', tgt='mul', - cop='*')).compile() - exec py.code.Source(multiplicative_func_source.format(name='INT_FLOORDIV', - op='*', tgt='div', - cop='/')).compile() - exec py.code.Source(multiplicative_func_source.format(name='UINT_FLOORDIV', - op='*', tgt='div', - cop='/')).compile() + exec py.code.Source(multiplicative_func_source + .format(name='INT_MUL', op='*', tgt='mul', cop='*')).compile() + exec py.code.Source(multiplicative_func_source + .format(name='INT_FLOORDIV', op='*', tgt='div', cop='/')).compile() + exec py.code.Source(multiplicative_func_source + .format(name='UINT_FLOORDIV', op='*', tgt='div', cop='/')).compile() del multiplicative_func_source + array_access_source = """ + def operation_{name}(self, op, index): + descr = op.getdescr() + idx_ref = self.index_vars[op.getarg(1)] + self.memory_refs[index] = MemoryRef(op, idx_ref, {raw_access}) + """ + exec py.code.Source(array_access_source + .format(name='RAW_LOAD',raw_access=True)).compile() + exec py.code.Source(array_access_source + .format(name='RAW_STORE',raw_access=True)).compile() + exec py.code.Source(array_access_source + .format(name='GETARRAYITEM_GC',raw_access=False)).compile() + exec py.code.Source(array_access_source + .format(name='SETARRAYITEM_GC',raw_access=False)).compile() + exec py.code.Source(array_access_source + .format(name='GETARRAYITEM_RAW',raw_access=False)).compile() + exec py.code.Source(array_access_source + .format(name='SETARRAYITEM_RAW',raw_access=False)).compile() + del array_access_source integral_dispatch_opt = make_dispatcher_method(IntegralForwardModification, 'operation_') IntegralForwardModification.inspect_operation = integral_dispatch_opt del integral_dispatch_opt -class IntegralMod(object): - """ Calculates integral modifications on an integer object. - The operations must be provided in backwards direction and of one - variable only. Call reset() to reuse this object for other variables. - See MemoryRef for an example. - """ - - def __init__(self): - self.reset() - - def reset(self): - self.is_const_mod = False - self.coefficient_mul = 1 - self.coefficient_div = 1 - self.constant = 0 - self.used_box = None - - def _update_additive(self, i): - return (i * self.coefficient_mul) / self.coefficient_div - - additive_func_source = """ - def operation_{name}(self, op): - box_a0 = op.getarg(0) - box_a1 = op.getarg(1) - self.is_const_mod = True - 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(box_a0): - self.constant {op}= self._update_additive(box_a0.getint()) - self.used_box = box_a1 - elif self.is_const_integral(box_a1): - self.constant {op}= self._update_additive(box_a1.getint()) - self.used_box = box_a0 - else: - self.is_const_mod = False - """ - exec py.code.Source(additive_func_source.format(name='INT_ADD', - op='+')).compile() - exec py.code.Source(additive_func_source.format(name='INT_SUB', - op='-')).compile() - del additive_func_source - - multiplicative_func_source = """ - def operation_{name}(self, op): - box_a0 = op.getarg(0) - box_a1 = op.getarg(1) - self.is_const_mod = True - 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 self.is_const_integral(box_a0): - self.coefficient_{tgt} {op}= box_a0.getint() - self.used_box = box_a1 - elif self.is_const_integral(box_a1): - self.coefficient_{tgt} {op}= box_a1.getint() - self.used_box = box_a0 - else: - self.is_const_mod = False - """ - exec py.code.Source(multiplicative_func_source.format(name='INT_MUL', - op='*', tgt='mul', - cop='*')).compile() - exec py.code.Source(multiplicative_func_source.format(name='INT_FLOORDIV', - op='*', tgt='div', - cop='/')).compile() - exec py.code.Source(multiplicative_func_source.format(name='UINT_FLOORDIV', - op='*', tgt='div', - cop='/')).compile() - del multiplicative_func_source - - def is_const_integral(self, box): - if isinstance(box, ConstInt): - return True - return False - - def update_memory_ref(self, memref): - memref.constant = self.constant - memref.coefficient_mul = self.coefficient_mul - memref.coefficient_div = self.coefficient_div - memref.origin = self.used_box - - def default_operation(self, operation): - pass -integral_dispatch_opt = make_dispatcher_method(IntegralMod, 'operation_', - default=IntegralMod.default_operation) -IntegralMod.inspect_operation = integral_dispatch_opt -del integral_dispatch_opt - class IndexVar(object): def __init__(self, var): self.var = var @@ -706,8 +631,8 @@ def __ne__(self, other): return not self.__eq__(other) - def clone(self, box): - c = IndexVar(box) + def clone(self): + c = IndexVar(self.var) c.coefficient_mul = self.coefficient_mul c.coefficient_div = self.coefficient_div c.constant = self.constant @@ -715,6 +640,7 @@ def same_variable(self, other): assert isinstance(other, IndexVar) + print other.var, "==", self.var, "?" return other.var == self.var def diff(self, other): @@ -729,7 +655,7 @@ self.coefficient_div, self.constant) class MemoryRef(object): - """ a memory reference to an array object. IntegralMod is able + """ a memory reference to an array object. IntegralForwardModification is able to propagate changes to this object if applied in backwards direction. Example: @@ -739,12 +665,12 @@ will result in the linear combination i0 * (2/1) + 2 """ - def __init__(self, array, origin, descr, index_ref, byte_index=False): - assert descr is not None - self.array = array - self.descr = descr + def __init__(self, op, index_ref, raw_access=False): + assert op.getdescr() is not None + self.array = op.getarg(0) + self.descr = op.getdescr() self.index_ref = index_ref - self.byte_index = byte_index + self.raw_access = raw_access def is_adjacent_to(self, other): """ this is a symmetric relation """ @@ -756,12 +682,12 @@ def match(self, other): assert isinstance(other, MemoryRef) if self.array == other.array and self.descr == other.descr: - return self.index_ref.same_variable(other.index_ref): + return self.index_ref.same_variable(other.index_ref) return False def stride(self): """ the stride in bytes """ - if not self.byte_index: + if not self.raw_access: return 1 return self.descr.get_item_size_in_bytes() @@ -777,12 +703,12 @@ self.origin != other.origin, or their linear combination point to the same element. """ - if self.index_ref.same_variable(other.index_ref): + if not self.index_ref.same_variable(other.index_ref): return True stride = self.stride() if self.match(other): - return abs(self.index_ref.diff(other.index_ref)) < stride - return False + return not abs(self.index_ref.diff(other.index_ref)) < stride + return True def __eq__(self, other): if self.match(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 @@ -5,21 +5,30 @@ 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, MemoryRef) -from rpython.jit.metainterp.optimizeopt.vectorize import LoopVectorizeInfo + 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 DepTestHelper(BaseTest): def build_dependency(self, ops, refs = False): loop = self.parse_loop(ops) - 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) + self.last_graph = DependencyGraph(loop.operations) for i in range(len(self.last_graph.adjacent_list)): self.assert_independent(i,i) return self.last_graph @@ -44,14 +53,19 @@ continue dependencies = graph.adjacent_list[idx][:] for edge in edges: - dependency = graph.instr_dependency(idx,edge) + if isinstance(edge,int): + edge = IntWrapper(edge) + dependency = graph.instr_dependency(idx,edge.number) if edge < idx: - dependency = graph.instr_dependency(edge, idx) - assert dependency is not None, \ - " it is expected that instruction at index" + \ - " %d depends on instr on index %d but it does not.\n%s" \ - % (idx, edge, graph) - dependencies.remove(dependency) + 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') + 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) + elif dependency is not None: + dependencies.remove(dependency) assert dependencies == [], \ "dependencies unexpected %s.\n%s" \ % (dependencies,graph) @@ -75,8 +89,8 @@ dep_match = dep_pattern.search(line) if dep_match: label = int(dep_match.group(1)) - deps_list = [int(d) for d in line[dep_match.end():].split(',') if len(d) > 0] - deps[label] = deps_list + deps_list = [] + deps[label] = [IntWrapper(d) for d in line[dep_match.end():].split(',') if len(d) > 0] if full_check: edges = [ None ] * len(deps) @@ -84,8 +98,10 @@ edges[k] = l for k,l in deps.items(): for rk in l: - if rk > k: - edges[rk].append(k) + if rk.number > k: + iw = IntWrapper(k) + iw.transitive = rk.transitive + edges[rk.number].append(iw) self.assert_edges(graph, edges) return graph @@ -97,11 +113,12 @@ def _write_dot_and_convert_to_svg(self, graph, ops, filename): dot = graph.as_dot(ops) - with open('/home/rich/' + filename + '.dot', 'w') as fd: + print"gogogogog" + with open('/tmp/_'+filename+'.dot', 'w') as fd: fd.write(dot) - with open('/home/rich/'+filename+'.svg', 'w') as fd: + with open('/tmp/'+filename+'.svg', 'w') as fd: import subprocess - subprocess.Popen(['dot', '-Tsvg', '/home/rich/'+filename+'.dot'], stdout=fd).communicate() + subprocess.Popen(['dot', '-Tsvg', '/tmp/_'+filename+'.dot'], stdout=fd).communicate() class BaseTestDependencyGraph(DepTestHelper): def test_dependency_empty(self): @@ -147,7 +164,6 @@ self.assert_dependencies(ops, full_check=True) def test_dependency_guard(self): - pytest.skip("fail guard TODO") ops = """ [i3] # 0: 2,3 i1 = int_add(1,1) # 1: 2 @@ -157,9 +173,8 @@ self.assert_dependencies(ops, full_check=True) def test_dependency_guard_2(self): - pytest.skip("fail guard TODO") ops = """ - [i1] # 0: 1,2,3 + [i1] # 0: 1,2?,3? i2 = int_le(i1, 10) # 1: 2 guard_true(i2) [i1] # 2: 3 i3 = int_add(i1,1) # 3: 4 @@ -168,9 +183,8 @@ self.assert_dependencies(ops, full_check=True) def test_no_edge_duplication(self): - pytest.skip("fail guard TODO") ops = """ - [i1] # 0: 1,2,3 + [i1] # 0: 1,2?,3 i2 = int_lt(i1,10) # 1: 2 guard_false(i2) [i1] # 2: 3 i3 = int_add(i1,i1) # 3: 4 @@ -179,9 +193,8 @@ self.assert_dependencies(ops, full_check=True) def test_no_edge_duplication_in_guard_failargs(self): - pytest.skip("fail guard TODO") ops = """ - [i1] # 0: 1,2,3 + [i1] # 0: 1,2?,3? i2 = int_lt(i1,10) # 1: 2 guard_false(i2) [i1,i1,i2,i1,i2,i1] # 2: 3 jump(i1) # 3: @@ -193,9 +206,9 @@ def test_dependencies_1(self): ops=""" - [i0, i1, i2] # 0: 1,3,6,7,11 + [i0, i1, i2] # 0: 1,3,6,7,11? i4 = int_gt(i1, 0) # 1: 2 - guard_true(i4) [] # 2: 3, 11 + guard_true(i4) [] # 2: 3, 11? i6 = int_sub(i1, 1) # 3: 4 i8 = int_gt(i6, 0) # 4: 5 guard_false(i8) [] # 5: 11 @@ -221,7 +234,6 @@ self.assert_dependencies(ops, full_check=True) def test_ovf_dep(self): - pytest.skip("fail guard TODO") ops=""" [i0, i1, i2] # 0: 2,3 i4 = int_sub_ovf(1, 0) # 1: 2 @@ -232,7 +244,7 @@ def test_exception_dep(self): ops=""" - [p0, i1, i2] # 0: 1,3 + [p0, i1, i2] # 0: 1,3? i4 = call(p0, 1, descr=nonwritedescr) # 1: 2,3 guard_no_exception() [] # 2: 3 jump(p0, i1, i2) # 3: @@ -240,77 +252,72 @@ self.assert_dependencies(ops, full_check=True) def test_call_dependency_on_ptr_but_not_index_value(self): - pytest.skip("fail guard TODO") ops=""" - [p0, p1, i2] # 0: 1,2,3,4,5 + [p0, p1, i2] # 0: 1,2?,3?,4?,5? i3 = int_add(i2,1) # 1: 2 - i4 = call(p0, i3, descr=nonwritedescr) # 2: 3,4,5 - guard_no_exception() [i2] # 3: 4,5 - p2 = getarrayitem_gc(p1,i3) # 4: 5 + i4 = call(p0, i3, descr=nonwritedescr) # 2: 3,4,5? + guard_no_exception() [i2] # 3: 4,5? + p2 = getarrayitem_gc(p1,i3,descr=intarraydescr) # 4: 5 jump(p2, p1, i3) # 5: """ self.assert_dependencies(ops, full_check=True) def test_call_dependency(self): - pytest.skip("fail guard TODO") ops=""" - [p0, p1, i2, i5] # 0: 1,2,3,4,5 + [p0, p1, i2, i5] # 0: 1,2?,3?,4?,5? i3 = int_add(i2,1) # 1: 2 - i4 = call(i5, i3, descr=nonwritedescr) # 2: 3,4,5 - guard_no_exception() [i2] # 3: 4,5 - p2 = getarrayitem_gc(p1,i3) # 4: 5 + i4 = call(i5, i3, descr=nonwritedescr) # 2: 3,4,5? + guard_no_exception() [i2] # 3: 4,5? + p2 = getarrayitem_gc(p1,i3,descr=chararraydescr) # 4: 5 jump(p2, p1, i3) # 5: """ self.assert_dependencies(ops, full_check=True) def test_setarrayitem_dependency(self): ops=""" - [p0, i1] - setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) # redef p0[i1] - i2 = getarrayitem_raw(p0, i1, descr=floatarraydescr) # use of redef above - setarrayitem_raw(p0, i1, 2, descr=floatarraydescr) # redef of p0[i1] - jump(p0, i2) + [p0, i1] # 0: 1,2?,3?,4? + setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) # 1: 2,3 + i2 = getarrayitem_raw(p0, i1, descr=floatarraydescr) # 2: 4 + setarrayitem_raw(p0, i1, 2, descr=floatarraydescr) # 3: 4 + jump(p0, i2) # 4: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1,2,3], [0,2,3], [0,1,4], [0,1,4], [2,3] ]) + self.assert_dependencies(ops, full_check=True) def test_setarrayitem_alias_dependency(self): # #1 depends on #2, i1 and i2 might alias, reordering would destroy # coorectness ops=""" - [p0, i1, i2] - setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) #1 - setarrayitem_raw(p0, i2, 2, descr=floatarraydescr) #2 - jump(p0, i1, i2) + [p0, i1, i2] # 0: 1,2?,3? + setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) # 1: 2 + setarrayitem_raw(p0, i2, 2, descr=floatarraydescr) # 2: 3 + jump(p0, i1, i2) # 3: """ - dep_graph = self.build_dependency(ops) - self.assert_edges(dep_graph, - [ [1,2,3], [0,2], [0,1,3], [0,2] ]) + self.assert_dependencies(ops, full_check=True) self.assert_dependent(1,2) self.assert_dependent(0,3) def test_setarrayitem_depend_with_no_memref_info(self): ops=""" - [p0, i1] # 0: 1,2,4 - setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) # 1: 3 + [p0, i1] # 0: 1,2,3?,4? + setarrayitem_raw(p0, i1, 1, descr=floatarraydescr) # 1: 3,4? i2 = int_add(i1,1) # 2: 3 setarrayitem_raw(p0, i2, 2, descr=floatarraydescr) # 3: 4 jump(p0, i1) # 4: """ self.assert_dependencies(ops, full_check=True) self.assert_independent(1,2) - self.assert_dependent(1,3) + self.assert_independent(1,3) def test_setarrayitem_dont_depend_with_memref_info(self): ops=""" - [p0, i1] # 0: 1,2,3,4 - setarrayitem_raw(p0, i1, 1, descr=chararraydescr) # 1: 4 + [p0, i1] # 0: 1,2,3?,4? + setarrayitem_raw(p0, i1, 1, descr=chararraydescr) # 1: 3?,4? i2 = int_add(i1,1) # 2: 3 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_independent(1,2) self.assert_independent(1,3) # they modify 2 different cells @@ -340,7 +347,7 @@ jump(i24, i19, i21, i3, i4, i5, i22, i7) # 21: """ self.assert_dependencies(ops, memref=True, full_check=False) - self.assert_independent(2,12) + self.assert_dependent(2,12) 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 @@ -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, IntegralMod, Scheduler, SchedulerData) + MemoryRef, Scheduler, SchedulerData) 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 @@ -65,13 +65,13 @@ def __init__(self, metainterp_sd, jitdriver_sd, loop, optimizations): Optimizer.__init__(self, metainterp_sd, jitdriver_sd, loop, optimizations) - self.vec_info = LoopVectorizeInfo() self.memory_refs = [] self.dependency_graph = None self.first_debug_merge_point = False self.last_debug_merge_point = None self.packset = None self.unroll_count = 0 + self.smallest_type_bytes = 0 def emit_operation(self, op): self._last_emitted_op = op @@ -99,8 +99,7 @@ assert label_op.getopnum() == rop.LABEL assert jump_op.is_final() or jump_op.getopnum() == rop.LABEL - - self.vec_info.track_memory_refs = True + # XXX self.vec_info.track_memory_refs = True self.emit_unrolled_operation(label_op) @@ -113,8 +112,8 @@ 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) + #self.vec_info.index = len(self._newoperations)-1 + #self.vec_info.inspect_operation(op) orig_jump_args = jump_op.getarglist()[:] # it is assumed that #label_args == #jump_args @@ -154,8 +153,8 @@ self.clone_snapshot(copied_op.rd_snapshot, rename_map) # self.emit_unrolled_operation(copied_op) - self.vec_info.index = len(self._newoperations)-1 - self.vec_info.inspect_operation(copied_op) + #self.vec_info.index = len(self._newoperations)-1 + #self.vec_info.inspect_operation(copied_op) # the jump arguments have been changed # if label(iX) ... jump(i(X+1)) is called, at the next unrolled loop @@ -192,15 +191,21 @@ new_boxes) return snapshot - def _gather_trace_information(self, loop, track_memref = False): - self.vec_info.track_memory_refs = track_memref + def linear_find_smallest_type(self, loop): + # O(#operations) for i,op in enumerate(loop.operations): - self.vec_info.inspect_operation(op) + if op.is_array_op(): + descr = op.getdescr() + if not descr.is_array_of_pointers(): + byte_count = descr.get_item_size_in_bytes() + if self.smallest_type_bytes == 0 \ + or byte_count < self.smallest_type_bytes: + self.smallest_type_bytes = byte_count def get_unroll_count(self): """ This is an estimated number of further unrolls """ # this optimization is not opaque, and needs info about the CPU - byte_count = self.vec_info.smallest_type_bytes + byte_count = self.smallest_type_bytes if byte_count == 0: return 0 simd_vec_reg_bytes = 16 # TODO get from cpu @@ -211,9 +216,9 @@ self.clear_newoperations() - self._gather_trace_information(self.loop) + self.linear_find_smallest_type(self.loop) - byte_count = self.vec_info.smallest_type_bytes + byte_count = self.smallest_type_bytes if byte_count == 0: # stop, there is no chance to vectorize this trace raise NotAVectorizeableLoop() @@ -232,9 +237,9 @@ self.schedule() def relax_guard_dependencies(self): - int_mod = IntegralMod() - for idx, guard in self.vec_info.guards.items(): - int_mod.reset() + return + for guard_idx in self.dependency_graph.guards: + guard = self.operations[guard_idx] for dep in self.dependency_graph.depends(idx): op = self.operations[dep.idx_from] if op.returns_bool_result(): @@ -247,7 +252,7 @@ def build_dependency_graph(self): self.dependency_graph = \ - DependencyGraph(self.loop.operations, self.vec_info.memory_refs) + DependencyGraph(self.loop.operations) self.relax_guard_dependencies() def find_adjacent_memory_refs(self): @@ -611,53 +616,3 @@ def __repr__(self): return "PackOpWrapper(%d, %r)" % (self.opidx, self.memref) -class LoopVectorizeInfo(object): - - def __init__(self): - self.smallest_type_bytes = 0 - self.memory_refs = {} - self.guards = {} - self.track_memory_refs = False - self.index = 0 - - guard_source = """ - def operation_{name}(self, op): - if self.track_memory_refs: - self.guards[self.index] = op - """ - for op in ['GUARD_TRUE','GUARD_FALSE']: - exec py.code.Source(guard_source.format(name=op)).compile() - del guard_source - - array_access_source = """ - def operation_{name}(self, op): - descr = op.getdescr() - if self.track_memory_refs: - self.memory_refs[self.index] = \ - MemoryRef(op.getarg(0), op.getarg(1), op.getdescr(), {elemidx}) - if not descr.is_array_of_pointers(): - byte_count = descr.get_item_size_in_bytes() - if self.smallest_type_bytes == 0 \ - or byte_count < self.smallest_type_bytes: - self.smallest_type_bytes = byte_count - """ - exec py.code.Source(array_access_source - .format(name='RAW_LOAD',elemidx=True)).compile() - exec py.code.Source(array_access_source - .format(name='RAW_STORE',elemidx=True)).compile() - exec py.code.Source(array_access_source - .format(name='GETARRAYITEM_GC',elemidx=False)).compile() - exec py.code.Source(array_access_source - .format(name='SETARRAYITEM_GC',elemidx=False)).compile() - exec py.code.Source(array_access_source - .format(name='GETARRAYITEM_RAW',elemidx=False)).compile() - exec py.code.Source(array_access_source - .format(name='SETARRAYITEM_RAW',elemidx=False)).compile() - del array_access_source - - def default_operation(self, operation): - pass -dispatch_opt = make_dispatcher_method(LoopVectorizeInfo, 'operation_', - default=LoopVectorizeInfo.default_operation) -LoopVectorizeInfo.inspect_operation = dispatch_opt - _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit