Author: Richard Plangger <r...@pasra.at> Branch: vecopt2 Changeset: r77059:a014b8f35628 Date: 2015-03-04 11:03 +0100 http://bitbucket.org/pypy/pypy/changeset/a014b8f35628/
Log: added a file to implement the dependency graph and the first failing test for it diff --git a/.gitignore b/.gitignore --- a/.gitignore +++ b/.gitignore @@ -1,9 +1,14 @@ .hg .svn +# VIM +*.swp +*.swo + *.pyc *.pyo *~ +__pycache__/ bin/pypy-c include/*.h @@ -22,4 +27,5 @@ pypy/translator/goal/pypy-c pypy/translator/goal/target*-c release/ +!pypy/tool/release/ rpython/_cache/ diff --git a/rpython/jit/metainterp/optimizeopt/dependency.py b/rpython/jit/metainterp/optimizeopt/dependency.py new file mode 100644 --- /dev/null +++ b/rpython/jit/metainterp/optimizeopt/dependency.py @@ -0,0 +1,35 @@ + +from rpython.jit.metainterp.resoperation import rop + +class Dependency(object): + def __init__(self, index): + self.index = index + +class CrossIterationDependency(Dependency): + pass + +class DependencyGraph(object): + """ A graph that represents one of the following dependencies: + * True dependency + * Anti dependency + * Ouput dependency + Representation is an adjacent list. The number of edges between the + vertices is expected to be small. + """ + def __init__(self, optimizer, loop): + self.loop = loop + self.operations = loop.operations + self.optimizer = optimizer + self.adjacent_list = [ [] ] * len(self.operations) + + def instr_dependency(self, from_instr_idx, to_instr_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. + """ + edges = self.adjacent_list[from_instr_idx] + for edge in edges: + if edge.index == to_instr_idx: + return edge + return None + diff --git a/rpython/jit/metainterp/optimizeopt/test/test_dependency.py b/rpython/jit/metainterp/optimizeopt/test/test_dependency.py new file mode 100644 --- /dev/null +++ b/rpython/jit/metainterp/optimizeopt/test/test_dependency.py @@ -0,0 +1,54 @@ +import py +from rpython.rlib.objectmodel import instantiate +from rpython.jit.metainterp.optimizeopt.test.test_util import ( + LLtypeMixin, BaseTest, FakeMetaInterpStaticData, convert_old_style_to_targets) +from rpython.jit.metainterp.history import TargetToken, JitCellToken +from rpython.jit.metainterp.optimizeopt import optimize_trace +import rpython.jit.metainterp.optimizeopt.optimizer as optimizeopt +import rpython.jit.metainterp.optimizeopt.virtualize as virtualize +from rpython.jit.metainterp.optimizeopt.dependency import DependencyGraph +from rpython.jit.metainterp.optimize import InvalidLoop +from rpython.jit.metainterp.history import ConstInt, BoxInt, get_const_ptr_for_string +from rpython.jit.metainterp import executor, compile, resume +from rpython.jit.metainterp.resoperation import rop, ResOperation +from rpython.rlib.rarithmetic import LONG_BIT + +class BaseTestDependecyGraph(BaseTest): + + enable_opts = "intbounds:rewrite:virtualize:string:earlyforce:pure:heap:vectorize" + + def build_dependency(self, ops): + loop = self.parse(ops, postprocess=self.postprocess) + token = JitCellToken() + 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) + #self._do_optimize_loop(loop, call_pure_results, export_state=False) + #print '\n'.join([str(o) for o in loop.operations]) + #self.assert_equal(loop, expected) + + return DependencyGraph(None, loop) + + def assert_def_use(self, graph, from_instr_index, to_instr_index): + assert graph.instr_dependency(from_instr_index, + to_instr_index) is not None, \ + " it is expected that instruction at index" + \ + " %d depend on instr on index %d but it is not" \ + % (from_instr_index, to_instr_index) + +class TestDependencyGraph(BaseTestDependecyGraph): + def test_simple(self): + ops = """ + [] + i1 = int_add(1,1) + i2 = int_add(i1,1) + guard_value(i2,3) [] + jump() + """ + dep_graph = self.build_dependency(ops) + self.assert_def_use(dep_graph, 1, 2) + self.assert_def_use(dep_graph, 2, 3) + +class TestLLtype(TestDependencyGraph, LLtypeMixin): + pass _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit