Author: Armin Rigo <ar...@tunes.org>
Branch:
Changeset: r46018:afb404b14725
Date: 2011-07-27 15:47 +0200
http://bitbucket.org/pypy/pypy/changeset/afb404b14725/
Log: Merge 0cdaf4c98369, moving regalloc.py to a general tool in
pypy/tool/algo/.
diff --git a/pypy/jit/codewriter/regalloc.py b/pypy/jit/codewriter/regalloc.py
--- a/pypy/jit/codewriter/regalloc.py
+++ b/pypy/jit/codewriter/regalloc.py
@@ -1,129 +1,8 @@
-import sys
-from pypy.objspace.flow.model import Variable
-from pypy.tool.algo.color import DependencyGraph
-from pypy.tool.algo.unionfind import UnionFind
+from pypy.tool.algo import regalloc
from pypy.jit.metainterp.history import getkind
from pypy.jit.codewriter.flatten import ListOfKind
+
def perform_register_allocation(graph, kind):
- """Perform register allocation for the Variables of the given 'kind'
- in the 'graph'."""
- regalloc = RegAllocator(graph, kind)
- regalloc.make_dependencies()
- regalloc.coalesce_variables()
- regalloc.find_node_coloring()
- return regalloc
-
-
-class RegAllocator(object):
- DEBUG_REGALLOC = False
-
- def __init__(self, graph, kind):
- self.graph = graph
- self.kind = kind
-
- def make_dependencies(self):
- dg = DependencyGraph()
- for block in self.graph.iterblocks():
- # Compute die_at = {Variable: index_of_operation_with_last_usage}
- die_at = dict.fromkeys(block.inputargs, 0)
- for i, op in enumerate(block.operations):
- for v in op.args:
- if isinstance(v, Variable):
- die_at[v] = i
- elif isinstance(v, ListOfKind):
- for v1 in v:
- if isinstance(v1, Variable):
- die_at[v1] = i
- if op.result is not None:
- die_at[op.result] = i + 1
- if isinstance(block.exitswitch, tuple):
- for x in block.exitswitch:
- die_at.pop(x, None)
- else:
- die_at.pop(block.exitswitch, None)
- for link in block.exits:
- for v in link.args:
- die_at.pop(v, None)
- die_at = [(value, key) for (key, value) in die_at.items()]
- die_at.sort()
- die_at.append((sys.maxint,))
- # Done. XXX the code above this line runs 3 times
- # (for kind in KINDS) to produce the same result...
- livevars = [v for v in block.inputargs
- if getkind(v.concretetype) == self.kind]
- # Add the variables of this block to the dependency graph
- for i, v in enumerate(livevars):
- dg.add_node(v)
- for j in range(i):
- dg.add_edge(livevars[j], v)
- livevars = set(livevars)
- die_index = 0
- for i, op in enumerate(block.operations):
- while die_at[die_index][0] == i:
- try:
- livevars.remove(die_at[die_index][1])
- except KeyError:
- pass
- die_index += 1
- if (op.result is not None and
- getkind(op.result.concretetype) == self.kind):
- dg.add_node(op.result)
- for v in livevars:
- if getkind(v.concretetype) == self.kind:
- dg.add_edge(v, op.result)
- livevars.add(op.result)
- self._depgraph = dg
-
- def coalesce_variables(self):
- self._unionfind = UnionFind()
- pendingblocks = list(self.graph.iterblocks())
- while pendingblocks:
- block = pendingblocks.pop()
- # Aggressively try to coalesce each source variable with its
- # target. We start from the end of the graph instead of
- # from the beginning. This is a bit arbitrary, but the idea
- # is that the end of the graph runs typically more often
- # than the start, given that we resume execution from the
- # middle during blackholing.
- for link in block.exits:
- if link.last_exception is not None:
- self._depgraph.add_node(link.last_exception)
- if link.last_exc_value is not None:
- self._depgraph.add_node(link.last_exc_value)
- for i, v in enumerate(link.args):
- self._try_coalesce(v, link.target.inputargs[i])
-
- def _try_coalesce(self, v, w):
- if isinstance(v, Variable) and getkind(v.concretetype) == self.kind:
- assert getkind(w.concretetype) == self.kind
- dg = self._depgraph
- uf = self._unionfind
- v0 = uf.find_rep(v)
- w0 = uf.find_rep(w)
- if v0 is not w0 and v0 not in dg.neighbours[w0]:
- _, rep, _ = uf.union(v0, w0)
- assert uf.find_rep(v0) is uf.find_rep(w0) is rep
- if rep is v0:
- dg.coalesce(w0, v0)
- else:
- assert rep is w0
- dg.coalesce(v0, w0)
-
- def find_node_coloring(self):
- self._coloring = self._depgraph.find_node_coloring()
- if self.DEBUG_REGALLOC:
- for block in self.graph.iterblocks():
- print block
- for v in block.getvariables():
- print '\t', v, '\t', self.getcolor(v)
-
- def getcolor(self, v):
- return self._coloring[self._unionfind.find_rep(v)]
-
- def swapcolors(self, col1, col2):
- for key, value in self._coloring.items():
- if value == col1:
- self._coloring[key] = col2
- elif value == col2:
- self._coloring[key] = col1
+ checkkind = lambda v: getkind(v.concretetype) == kind
+ return regalloc.perform_register_allocation(graph, checkkind, ListOfKind)
diff --git a/pypy/jit/codewriter/regalloc.py b/pypy/tool/algo/regalloc.py
copy from pypy/jit/codewriter/regalloc.py
copy to pypy/tool/algo/regalloc.py
--- a/pypy/jit/codewriter/regalloc.py
+++ b/pypy/tool/algo/regalloc.py
@@ -2,13 +2,11 @@
from pypy.objspace.flow.model import Variable
from pypy.tool.algo.color import DependencyGraph
from pypy.tool.algo.unionfind import UnionFind
-from pypy.jit.metainterp.history import getkind
-from pypy.jit.codewriter.flatten import ListOfKind
-def perform_register_allocation(graph, kind):
+def perform_register_allocation(graph, consider_var, ListOfKind=()):
"""Perform register allocation for the Variables of the given 'kind'
in the 'graph'."""
- regalloc = RegAllocator(graph, kind)
+ regalloc = RegAllocator(graph, consider_var, ListOfKind)
regalloc.make_dependencies()
regalloc.coalesce_variables()
regalloc.find_node_coloring()
@@ -18,9 +16,10 @@
class RegAllocator(object):
DEBUG_REGALLOC = False
- def __init__(self, graph, kind):
+ def __init__(self, graph, consider_var, ListOfKind):
self.graph = graph
- self.kind = kind
+ self.consider_var = consider_var
+ self.ListOfKind = ListOfKind
def make_dependencies(self):
dg = DependencyGraph()
@@ -31,7 +30,7 @@
for v in op.args:
if isinstance(v, Variable):
die_at[v] = i
- elif isinstance(v, ListOfKind):
+ elif isinstance(v, self.ListOfKind):
for v1 in v:
if isinstance(v1, Variable):
die_at[v1] = i
@@ -51,7 +50,7 @@
# Done. XXX the code above this line runs 3 times
# (for kind in KINDS) to produce the same result...
livevars = [v for v in block.inputargs
- if getkind(v.concretetype) == self.kind]
+ if self.consider_var(v)]
# Add the variables of this block to the dependency graph
for i, v in enumerate(livevars):
dg.add_node(v)
@@ -67,10 +66,10 @@
pass
die_index += 1
if (op.result is not None and
- getkind(op.result.concretetype) == self.kind):
+ self.consider_var(op.result)):
dg.add_node(op.result)
for v in livevars:
- if getkind(v.concretetype) == self.kind:
+ if self.consider_var(v):
dg.add_edge(v, op.result)
livevars.add(op.result)
self._depgraph = dg
@@ -95,8 +94,8 @@
self._try_coalesce(v, link.target.inputargs[i])
def _try_coalesce(self, v, w):
- if isinstance(v, Variable) and getkind(v.concretetype) == self.kind:
- assert getkind(w.concretetype) == self.kind
+ if isinstance(v, Variable) and self.consider_var(v):
+ assert self.consider_var(w)
dg = self._depgraph
uf = self._unionfind
v0 = uf.find_rep(v)
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit
