Author: Richard Plangger <r...@pasra.at> Branch: vecopt-merge Changeset: r79050:a376c01d579f Date: 2015-08-19 11:55 +0200 http://bitbucket.org/pypy/pypy/changeset/a376c01d579f/
Log: testing the path iteration, there is still a problem in analyse_index_calculation 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 @@ -112,6 +112,7 @@ # save the operation that produces the result for the first argument # only for guard_true/guard_false self.guard_bool_bool_node = None + self._stack = False def getoperation(self): return self.op @@ -285,28 +286,31 @@ else: iterdir = node.provides() if index >= len(iterdir): - if blacklist: - blacklist_visit[node] = None + #if blacklist: + #blacklist_visit[node] = None + # print "blacklisting 1", node, "path", '->'.join([str(p.opidx) for p in path.path]) continue else: next_dep = iterdir[index] next_node = next_dep.to index += 1 + if index < len(iterdir): + worklist.append((index, node, pathlen)) + else: + print "blacklisting 2", node, "path", '->'.join([str(p.opidx) for p in path.path]) + blacklist_visit[node] = None + path.cut_off_at(pathlen) + path.walk(next_node) if blacklist and next_node in blacklist_visit: yield Path(path.path[:]) continue - if index < len(iterdir): - worklist.append((index, node, pathlen)) - else: - blacklist_visit[node] = None - path.cut_off_at(pathlen) - path.walk(next_node) pathlen += 1 if next_node is to or (path_max_len > 0 and pathlen >= path_max_len): yield Path(path.path[:]) - if blacklist: - blacklist_visit[next_node] = None + # note that the destiantion node ``to'' is never blacklisted + #if blacklist: + # blacklist_visit[next_node] = None else: worklist.append((0, next_node, pathlen)) @@ -731,6 +735,17 @@ # and the next guard instruction tracker.add_non_pure(node) + def cycles(self): + """ NOT_RPYTHON """ + stack = [] + for node in self.nodes: + node._stack = False + # + label = self.nodes[0] + if _first_cycle(stack, label): + return stack + return None + def __repr__(self): graph = "graph([\n" for node in self.nodes: @@ -744,6 +759,7 @@ return graph + " ])" def as_dot(self): + """ NOT_RPTYHON """ if not we_are_translated(): dot = "digraph dep_graph {\n" for node in self.nodes: @@ -765,6 +781,49 @@ return dot raise NotImplementedError("dot only for debug purpose") +def _first_cycle(stack, node): + node._stack = True + stack.append(node) + + for dep in node.provides(): + succ = dep.to + if succ._stack: + # found cycle! + while stack[0] is not succ: + del stack[0] + return True + else: + return _first_cycle(stack, succ) + + return False + +def _strongly_connect(index, stack, cycles, node): + """ currently unused """ + node._scc_index = index + node._scc_lowlink = index + index += 1 + stack.append(node) + node._scc_stack = True + + for dep in node.provides(): + succ = dep.to + if succ._scc_index == -1: + index = _strongly_connect(index, stack, cycles, succ) + node._scc_lowlink = min(node._scc_lowlink, succ._scc_lowlink) + elif succ._scc_stack: + node._scc_lowlink = min(node._scc_lowlink, succ._scc_index) + + if node._scc_lowlink == node._scc_index: + cycle = [] + while True: + w = stack.pop() + w._scc_stack = False + cycle.append(w) + if w is node: + break + cycles.append(cycle) + return index + class IntegralForwardModification(object): """ Calculates integral modifications on integer boxes. """ def __init__(self, memory_refs, index_vars, comparison_vars, invariant_vars): 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 @@ -17,6 +17,10 @@ def __repr__(self): return "n%d" % self.opidx +class FakeDependencyGraph(DependencyGraph): + def __init__(self): + pass + class DependencyBaseTest(BaseTest): def setup_method(self, method): @@ -391,7 +395,7 @@ self.assert_dependencies(trace, full_check=True) - def test_iterate_paths(self): + def test_iterate(self): n1,n2,n3,n4,n5 = [FakeNode(i+1) for i in range(5)] # n1 -> n2 -> n4 -> n5 # +---> n3 --^ @@ -434,7 +438,7 @@ for i in r: assert paths[i].as_str() == "n0 -> %s -> n%d" % (nodes[i], len(r)+1) - def test_iterate_paths_blacklist_diamond(self): + def test_iterate_blacklist_diamond(self): blacklist = {} n1,n2,n3,n4 = [FakeNode(i+1) for i in range(4)] # n1 -> n2 -> n4 @@ -445,9 +449,9 @@ paths = list(n1.iterate_paths(n4, blacklist=True)) assert len(paths) == 2 assert paths[0].as_str() == "n1 -> n2 -> n4" - assert paths[1].as_str() == "n1 -> n3" + assert paths[1].as_str() == "n1 -> n3 -> n4" - def test_iterate_paths_blacklist_double_diamond(self): + def test_iterate_blacklist_double_diamond(self): blacklist = {} n1,n2,n3,n4,n5,n6,n7,n8 = [FakeNode(i+1) for i in range(8)] # n1 -> n2 -> n4 -> n5 -> n6 --> n8 @@ -461,8 +465,56 @@ paths = list(n1.iterate_paths(n8, blacklist=True)) assert len(paths) == 3 assert paths[0].as_str() == "n1 -> n2 -> n4 -> n5 -> n6 -> n8" - assert paths[1].as_str() == "n1 -> n2 -> n4 -> n5 -> n7" - assert paths[2].as_str() == "n1 -> n3" + assert paths[1].as_str() == "n1 -> n2 -> n4 -> n5 -> n7 -> n8" + assert paths[2].as_str() == "n1 -> n3 -> n4" + + def test_iterate_blacklist_split_path(self): + blacklist = {} + n1,n2,n3,n4,n5,n6,n7,n8 = [FakeNode(i+1) for i in range(8)] + n1.edge_to(n2); + n3.edge_to(n2); + n2.edge_to(n4); + n3.edge_to(n4); + + paths = list(n4.iterate_paths(n3, backwards=True, blacklist=True)) + assert len(paths) == 2 + assert paths[0].as_str() == "n4 -> n2 -> n3" + assert paths[1].as_str() == "n4 -> n3" + + n5.edge_to(n1) + n5.edge_to(n3) + + paths = list(n4.iterate_paths(n5, backwards=True, blacklist=True)) + assert len(paths) == 3 + assert paths[0].as_str() == "n4 -> n2 -> n1 -> n5" + assert paths[1].as_str() == "n4 -> n2 -> n3 -> n5" + assert paths[2].as_str() == "n4 -> n3" + + def test_sccs(self): + n1,n2 = FakeNode(1), FakeNode(2) + n1.edge_to(n2); n2.edge_to(n1) + + graph = FakeDependencyGraph() + graph.nodes = [n1,n2] + cycle = graph.cycles() + assert cycle == [n1, n2] + + n3 = FakeNode(0) + graph.nodes = [n3] + cycle = graph.cycles() + assert cycle is None + + def test_cycles_2(self): + n1,n2,n3,n4 = FakeNode(1), FakeNode(2), FakeNode(3), FakeNode(4) + n1.edge_to(n3); n3.edge_to(n4); n4.edge_to(n1) + + graph = FakeDependencyGraph() + graph.nodes = [n1,n2,n3] + cycle = graph.cycles() + assert cycle is not None + assert cycle == [n1,n3,n4] + + class TestLLtype(BaseTestDependencyGraph, LLtypeMixin): pass 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 @@ -93,6 +93,9 @@ self.show_dot_graph(DependencyGraph(opt.loop), "original_" + self.test_name) opt.analyse_index_calculations() if opt.dependency_graph is not None: + cycle = opt.dependency_graph.cycles() + if cycle is not None: + print "CYCLE found %s" % cycle self.show_dot_graph(opt.dependency_graph, "early_exit_" + self.test_name) opt.schedule(False) opt.unroll_loop_iterations(loop, unroll_factor) 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 @@ -515,23 +515,27 @@ label_node = graph.getnode(0) ee_guard_node = graph.getnode(ee_pos) guards = graph.guards + unique = set() for guard_node in guards: if guard_node is ee_guard_node: continue modify_later = [] last_prev_node = None - i = 0 for path in guard_node.iterate_paths(ee_guard_node, backwards=True, blacklist=True): + p = '->'.join([str(p.opidx) for p in path.path]) + if p in unique: + assert 0 + else: + unique.add(p) + print "PATH:", p if not we_are_translated(): path.check_acyclic() - print "loop", i - i+=1 prev_node = path.second() dep = prev_node.depends_on(guard_node) if dep.is_failarg(): # this dependency we are able to break because it is soley # relevant due to one or multiple fail args - if prev_node == last_prev_node: + if prev_node is not last_prev_node: # ... # o o # \ / @@ -540,18 +544,19 @@ # (g) # this graph yields 2 paths from (g), thus (a) is # remembered and skipped the second time visited - continue - modify_later.append((prev_node, guard_node)) + modify_later.append((prev_node, guard_node)) + print " => remove guard -> second" + last_prev_node = prev_node + continue + if path.is_always_pure(exclude_first=True, exclude_last=True): + path.set_schedule_priority(10) + if path.last() is ee_guard_node: + modify_later.append((path.last_but_one(), None)) + print " => always pure" else: - if path.is_always_pure(exclude_first=True, exclude_last=True): - path.set_schedule_priority(10) - if path.last() is ee_guard_node: - modify_later.append((path.last_but_one(), None)) - else: - # transformation is invalid. - # exit and do not enter else branch! - break - last_prev_node = prev_node + # transformation is invalid. + # exit and do not enter else branch! + break else: # transformation is valid, modify the graph and execute # this guard earlier diff --git a/rpython/jit/metainterp/warmstate.py b/rpython/jit/metainterp/warmstate.py --- a/rpython/jit/metainterp/warmstate.py +++ b/rpython/jit/metainterp/warmstate.py @@ -304,6 +304,8 @@ self.vec = bool(value) def set_param_vec_params(self, value): + if NonConstant(False): + value = 'blah' # not a constant '' values = value.split(":") self.vec_all = bool(values[0]) self.vec_cost = 0 _______________________________________________ pypy-commit mailing list pypy-commit@python.org https://mail.python.org/mailman/listinfo/pypy-commit