[pypy-svn] r52002 - in pypy/branch/jit-refactoring/pypy/jit/rainbow: . test
cfbolz at codespeak.net
cfbolz at codespeak.net
Sat Mar 1 16:18:27 CET 2008
Author: cfbolz
Date: Sat Mar 1 16:18:26 2008
New Revision: 52002
Modified:
pypy/branch/jit-refactoring/pypy/jit/rainbow/codewriter.py
pypy/branch/jit-refactoring/pypy/jit/rainbow/dump.py
pypy/branch/jit-refactoring/pypy/jit/rainbow/interpreter.py
pypy/branch/jit-refactoring/pypy/jit/rainbow/test/test_interpreter.py
Log:
implement switch handling
Modified: pypy/branch/jit-refactoring/pypy/jit/rainbow/codewriter.py
==============================================================================
--- pypy/branch/jit-refactoring/pypy/jit/rainbow/codewriter.py (original)
+++ pypy/branch/jit-refactoring/pypy/jit/rainbow/codewriter.py Sat Mar 1 16:18:26 2008
@@ -1,3 +1,4 @@
+import py
from pypy.rlib.unroll import unrolling_iterable
from pypy.rlib.objectmodel import we_are_translated
from pypy.objspace.flow import model as flowmodel
@@ -10,6 +11,8 @@
from pypy.jit.timeshifter.greenkey import KeyDesc
from pypy.jit.rainbow.interpreter import JitCode, JitInterpreter
from pypy.translator.backendopt.removenoops import remove_same_as
+from pypy.translator.backendopt.ssa import SSA_to_SSI
+from pypy.translator.unsimplify import varoftype
class CallDesc:
@@ -96,12 +99,14 @@
self.unfinished_graphs = []
self.num_global_mergepoints = 0
self.ptr_to_jitcode = {}
+ self.transformer = GraphTransformer(hannotator)
def can_raise(self, op):
return self.raise_analyzer.analyze(op)
def make_bytecode(self, graph, is_portal=True):
- remove_same_as(graph)
+ self.transformer.transform_graph(graph)
+ #graph.show()
if is_portal:
bytecode = JitCode.__new__(JitCode)
bytecode.is_portal = True
@@ -323,7 +328,30 @@
self.emit(*truerenaming)
self.make_bytecode_block(linktrue.target, insert_goto=True)
else:
- XXX
+ assert self.varcolor(block.exitswitch) == "green"
+ for link in block.exits:
+ if link.exitcase == 'default':
+ defaultlink = link
+ switchlinks = [link for link in block.exits
+ if link is not defaultlink]
+
+ renamings = [self.insert_renaming(link) for link in switchlinks]
+ defaultrenaming = self.insert_renaming(defaultlink)
+ cases = [flowmodel.Constant(link.exitcase,
+ block.exitswitch.concretetype)
+ for link in switchlinks]
+ cases = [self.serialize_oparg("green", case) for case in cases]
+ targets = [tlabel(link) for link in switchlinks]
+ self.emit("green_switch")
+ self.emit(self.serialize_oparg("green", block.exitswitch))
+ self.emit(len(cases), *cases)
+ self.emit(len(targets), *targets)
+ self.emit(*defaultrenaming)
+ self.make_bytecode_block(defaultlink.target, insert_goto=True)
+ for renaming, link in zip(renamings, switchlinks):
+ self.emit(label(link))
+ self.emit(*renaming)
+ self.make_bytecode_block(link.target, insert_goto=True)
def insert_merges(self, block):
if block is self.graph.returnblock:
@@ -1174,6 +1202,158 @@
return c
+class GraphTransformer(object):
+ def __init__(self, hannotator):
+ self.hannotator = hannotator
+
+ def transform_graph(self, graph):
+ self.graph = graph
+ remove_same_as(graph)
+ self.insert_splits()
+
+ def insert_splits(self):
+ hannotator = self.hannotator
+ for block in list(self.graph.iterblocks()):
+ if block.exitswitch is not None:
+ assert isinstance(block.exitswitch, flowmodel.Variable)
+ hs_switch = hannotator.binding(block.exitswitch)
+ if not hs_switch.is_green():
+ if block.exitswitch.concretetype is not lltype.Bool:
+ self.insert_switch_handling(block)
+
+ def insert_switch_handling(self, block):
+ v_redswitch = block.exitswitch
+ T = v_redswitch.concretetype
+ range_start = -py.std.sys.maxint-1
+ range_stop = py.std.sys.maxint+1
+ if T is not lltype.Signed:
+ if T is lltype.Char:
+ opcast = 'cast_char_to_int'
+ range_start = 0
+ range_stop = 256
+ elif T is lltype.UniChar:
+ opcast = 'cast_unichar_to_int'
+ range_start = 0
+ elif T is lltype.Unsigned:
+ opcast = 'cast_uint_to_int'
+ else:
+ raise AssertionError(T)
+ v_redswitch = self.genop(block, opcast, [v_redswitch],
+ resulttype=lltype.Signed, red=True)
+ block.exitswitch = v_redswitch
+ # for now, we always turn the switch back into a chain of tests
+ # that perform a binary search
+ blockset = {block: True} # reachable from outside
+ cases = {}
+ defaultlink = None
+ for link in block.exits:
+ if link.exitcase == 'default':
+ defaultlink = link
+ blockset[link.target] = False # not reachable from outside
+ else:
+ assert lltype.typeOf(link.exitcase) == T
+ intval = lltype.cast_primitive(lltype.Signed, link.exitcase)
+ cases[intval] = link
+ link.exitcase = None
+ link.llexitcase = None
+ self.insert_integer_search(block, cases, defaultlink, blockset,
+ range_start, range_stop)
+ SSA_to_SSI(blockset, self.hannotator)
+
+ def insert_integer_search(self, block, cases, defaultlink, blockset,
+ range_start, range_stop):
+ # fix the exit of the 'block' to check for the given remaining
+ # 'cases', knowing that if we get there then the value must
+ # be contained in range(range_start, range_stop).
+ if not cases:
+ assert defaultlink is not None
+ block.exitswitch = None
+ block.recloseblock(flowmodel.Link(defaultlink.args, defaultlink.target))
+ elif len(cases) == 1 and (defaultlink is None or
+ range_start == range_stop-1):
+ block.exitswitch = None
+ block.recloseblock(cases.values()[0])
+ else:
+ intvalues = cases.keys()
+ intvalues.sort()
+ if len(intvalues) <= 3:
+ # not much point in being clever with no more than 3 cases
+ intval = intvalues[-1]
+ remainingcases = cases.copy()
+ link = remainingcases.pop(intval)
+ c_intval = flowmodel.Constant(intval, lltype.Signed)
+ v = self.genop(block, 'int_eq', [block.exitswitch, c_intval],
+ resulttype=lltype.Bool, red=True)
+ link.exitcase = True
+ link.llexitcase = True
+ falseblock = flowmodel.Block([])
+ falseblock.exitswitch = block.exitswitch
+ blockset[falseblock] = False
+ falselink = flowmodel.Link([], falseblock)
+ falselink.exitcase = False
+ falselink.llexitcase = False
+ block.exitswitch = v
+ block.recloseblock(falselink, link)
+ if defaultlink is None or intval == range_stop-1:
+ range_stop = intval
+ self.insert_integer_search(falseblock, remainingcases,
+ defaultlink, blockset,
+ range_start, range_stop)
+ else:
+ intval = intvalues[len(intvalues) // 2]
+ c_intval = flowmodel.Constant(intval, lltype.Signed)
+ v = self.genop(block, 'int_ge', [block.exitswitch, c_intval],
+ resulttype=lltype.Bool, red=True)
+ falseblock = flowmodel.Block([])
+ falseblock.exitswitch = block.exitswitch
+ trueblock = flowmodel.Block([])
+ trueblock.exitswitch = block.exitswitch
+ blockset[falseblock] = False
+ blockset[trueblock] = False
+ falselink = flowmodel.Link([], falseblock)
+ falselink.exitcase = False
+ falselink.llexitcase = False
+ truelink = flowmodel.Link([], trueblock)
+ truelink.exitcase = True
+ truelink.llexitcase = True
+ block.exitswitch = v
+ block.recloseblock(falselink, truelink)
+ falsecases = {}
+ truecases = {}
+ for intval1, link1 in cases.items():
+ if intval1 < intval:
+ falsecases[intval1] = link1
+ else:
+ truecases[intval1] = link1
+ self.insert_integer_search(falseblock, falsecases,
+ defaultlink, blockset,
+ range_start, intval)
+ self.insert_integer_search(trueblock, truecases,
+ defaultlink, blockset,
+ intval, range_stop)
+
+ def genop(self, block, opname, args, resulttype=None, result_like=None, red=False):
+ # 'result_like' can be a template variable whose hintannotation is
+ # copied
+ if resulttype is not None:
+ v_res = varoftype(resulttype)
+ if red:
+ hs = hintmodel.SomeLLAbstractVariable(resulttype)
+ else:
+ hs = hintmodel.SomeLLAbstractConstant(resulttype, {})
+ self.hannotator.setbinding(v_res, hs)
+ elif result_like is not None:
+ v_res = copyvar(self.hannotator, result_like)
+ else:
+ v_res = self.new_void_var()
+
+ spaceop = flowmodel.SpaceOperation(opname, args, v_res)
+ if isinstance(block, list):
+ block.append(spaceop)
+ else:
+ block.operations.append(spaceop)
+ return v_res
+
class label(object):
def __init__(self, name):
self.name = name
Modified: pypy/branch/jit-refactoring/pypy/jit/rainbow/dump.py
==============================================================================
--- pypy/branch/jit-refactoring/pypy/jit/rainbow/dump.py (original)
+++ pypy/branch/jit-refactoring/pypy/jit/rainbow/dump.py Sat Mar 1 16:18:26 2008
@@ -105,6 +105,9 @@
args.append(jitcode.typekinds[src.load_2byte()])
elif argspec == "jumptarget":
args.append(src.load_jumptarget())
+ elif argspec == "jumptargets":
+ num = src.load_2byte()
+ args.append([src.load_jumptarget() for i in range(num)], )
elif argspec == "bool":
args.append(src.load_bool())
elif argspec == "redboxcls":
Modified: pypy/branch/jit-refactoring/pypy/jit/rainbow/interpreter.py
==============================================================================
--- pypy/branch/jit-refactoring/pypy/jit/rainbow/interpreter.py (original)
+++ pypy/branch/jit-refactoring/pypy/jit/rainbow/interpreter.py Sat Mar 1 16:18:26 2008
@@ -95,6 +95,9 @@
args += (self.frame.bytecode.typekinds[self.load_2byte()], )
elif argspec == "jumptarget":
args += (self.load_4byte(), )
+ elif argspec == "jumptargets":
+ num = self.load_2byte()
+ args += ([self.load_4byte() for i in range(num)], )
elif argspec == "bool":
args += (self.load_bool(), )
elif argspec == "redboxcls":
@@ -365,6 +368,16 @@
if arg:
self.frame.pc = target
+ @arguments("green", "green_varargs", "jumptargets")
+ def opimpl_green_switch(self, exitcase, cases, targets):
+ arg = exitcase.revealconst(lltype.Signed)
+ assert len(cases) == len(targets)
+ for i in range(len(cases)):
+ if arg == cases[i].revealconst(lltype.Signed):
+ self.frame.pc = targets[i]
+ break
+
+
@arguments("red", "jumptarget")
def opimpl_red_goto_iftrue(self, switchbox, target):
# XXX not sure about passing no green vars
Modified: pypy/branch/jit-refactoring/pypy/jit/rainbow/test/test_interpreter.py
==============================================================================
--- pypy/branch/jit-refactoring/pypy/jit/rainbow/test/test_interpreter.py (original)
+++ pypy/branch/jit-refactoring/pypy/jit/rainbow/test/test_interpreter.py Sat Mar 1 16:18:26 2008
@@ -1588,21 +1588,20 @@
assert res == -7
def test_switch(self):
- py.test.skip("not working yet")
- def g(n):
+ def g(n, x):
if n == 0:
- return 12
+ return 12 + x
elif n == 1:
- return 34
+ return 34 + x
elif n == 3:
- return 56
+ return 56 + x
elif n == 7:
- return 78
+ return 78 + x
else:
- return 90
+ return 90 + x
def f(n, m):
- x = g(n) # gives a red switch
- y = g(hint(m, concrete=True)) # gives a green switch
+ x = g(n, n) # gives a red switch
+ y = g(hint(m, concrete=True), n) # gives a green switch
return x - y
res = self.interpret(f, [7, 2], backendoptimize=True)
@@ -1611,22 +1610,21 @@
assert res == 90 - 34
def test_switch_char(self):
- py.test.skip("not working yet")
- def g(n):
+ def g(n, x):
n = chr(n)
if n == '\x00':
- return 12
+ return 12 + x
elif n == '\x01':
- return 34
+ return 34 + x
elif n == '\x02':
- return 56
+ return 56 + x
elif n == '\x03':
- return 78
+ return 78 + x
else:
- return 90
+ return 90 + x
def f(n, m):
- x = g(n) # gives a red switch
- y = g(hint(m, concrete=True)) # gives a green switch
+ x = g(n, n) # gives a red switch
+ y = g(hint(m, concrete=True), n) # gives a green switch
return x - y
res = self.interpret(f, [3, 0], backendoptimize=True)
More information about the pypy-svn
mailing list