Author: Richard Plangger <[email protected]>
Branch: gcstress-hypothesis
Changeset: r82986:c800d87fa7b4
Date: 2016-03-11 18:28 +0100
http://bitbucket.org/pypy/pypy/changeset/c800d87fa7b4/
Log: working on a new strategy that cuts down the search space of control
flow graphs to deterministic ones
diff --git a/rpython/jit/backend/llsupport/tl/code.py
b/rpython/jit/backend/llsupport/tl/code.py
--- a/rpython/jit/backend/llsupport/tl/code.py
+++ b/rpython/jit/backend/llsupport/tl/code.py
@@ -7,6 +7,10 @@
ctx.append_byte(self.BYTE_CODE)
@classmethod
+ def splits_control_flow(self):
+ return False
+
+ @classmethod
def filter_bytecode(self, stack):
""" filter this byte code if the stack does
not contain the right values on the stack.
@@ -210,9 +214,46 @@
def __init__(self):
pass
-def op_modifies_list(clazz):
- """ NOT_RPYTHON """
- return clazz in (DelList, InsertList)
+@requires_stack(INT_TYP)
+@leaves_on_stack()
+class CondJump(ByteCode):
+ BYTE_CODE = unique_code()
+
+ COND_EQ = 0
+ COND_LT = 1
+ COND_GT = 2
+ COND_LE = 3
+ COND_GE = 4
+ COND_ANY = 5
+
+ @requires_param(COND_TYP, INT_TYP)
+ def __init__(self, cond, offset):
+ self.cond = cond
+ self.offset = offset
+
+ def encode(self, ctx):
+ ctx.append_byte(self.BYTE_CODE)
+ ctx.append_byte(self.cond)
+ ctx.append_int(self.offset)
+
+ def splits_control_flow(self):
+ return True
+
+@requires_stack(LIST_TYP)
+@leaves_on_stack(LIST_TYP, INT_TYP)
+class LenList(ByteCode):
+ BYTE_CODE = unique_code()
+ def __init__(self):
+ pass
+
+
+#@requires_stack(INT_TYP) # TODO VAL_TYP)
+#@leaves_on_stack()
+#class ReturnFrame(ByteCode):
+# BYTE_CODE = unique_code()
+# def __init__(self):
+# pass
+#
BC_CLASSES = []
BC_NUM_TO_CLASS = {}
@@ -223,47 +264,15 @@
assert clazz.BYTE_CODE not in BC_NUM_TO_CLASS
BC_NUM_TO_CLASS[clazz.BYTE_CODE] = clazz
-# remove comment one by one!
+BC_CLASSES.remove(CondJump)
-#@requires_stack()
-#@leaves_on_stack(INT_TYP)
-#class CondJump(ByteCode):
-# BYTE_CODE = unique_code()
-#
-# COND_EQ = 0
-# COND_LT = 1
-# COND_GT = 2
-# COND_LE = 3
-# COND_GE = 4
-#
-# @requires_param(COND_TYP)
-# def __init__(self, cond):
-# self.cond = cond
-#
-# def encode(self, ctx):
-# ctx.append_byte(self.BYTE_CODE)
-# ctx.append_byte(self.cond)
-#
-#@requires_stack()
-#@leaves_on_stack()
-#class Jump(ByteCode):
-# BYTE_CODE = unique_code()
-# def __init__(self):
-# pass
-#
+# control flow byte codes
+BC_CF_CLASSES = [CondJump]
-#@requires_stack(LIST_TYP)
-#@leaves_on_stack(LIST_TYP, INT_TYP)
-#class LenList(ByteCode):
-# BYTE_CODE = unique_code()
-# def __init__(self):
-# pass
-#
-#
-#@requires_stack(INT_TYP) # TODO VAL_TYP)
-#@leaves_on_stack()
-#class ReturnFrame(ByteCode):
-# BYTE_CODE = unique_code()
-# def __init__(self):
-# pass
-#
+class ByteCodeControlFlow(object):
+ # see the deterministic control flow search startegy in
+ # test/code_strategies.py for what steps & byte_codes mean
+ def __init__(self):
+ self.blocks = []
+ self.steps = 0
+ self.byte_codes = 0
diff --git a/rpython/jit/backend/llsupport/tl/interp.py
b/rpython/jit/backend/llsupport/tl/interp.py
--- a/rpython/jit/backend/llsupport/tl/interp.py
+++ b/rpython/jit/backend/llsupport/tl/interp.py
@@ -13,6 +13,9 @@
def __init__(self, items):
self.items = items
+ def size(self):
+ return len(self.items)
+
def concat(self, space, w_lst):
assert isinstance(w_lst, W_ListObject)
return space.wrap(self.items + w_lst.items)
@@ -153,6 +156,22 @@
w_lst = stack.peek(0)
del w_lst.items[w_idx.value]
# index error, just crash the machine!!
+ elif opcode == code.LenList.BYTE_CODE:
+ w_lst = stack.peek(0)
+ assert isinstance(w_lst, W_ListObject)
+ stack.append(space.wrap(w_lst.size()))
+ elif opcode == code.CondJump.BYTE_CODE:
+ cond = runpack('b', bytecode[i+1:i+2])
+ offset = runpack('i', bytecode[i+2:i+6])
+ w_int = stack.pop(0)
+ assert isinstance(w_lst, W_IntObject)
+ i += 5
+ if CondJump.should_jump(cond, w_int.value):
+ if offset < 0:
+ pass # TODO jit driver
+ # the new position is calculated at the end of
+ # this jump instruction!!
+ i += offset
else:
print("opcode %d is not implemented" % opcode)
raise NotImplementedError
diff --git a/rpython/jit/backend/llsupport/tl/test/code_strategies.py
b/rpython/jit/backend/llsupport/tl/test/code_strategies.py
--- a/rpython/jit/backend/llsupport/tl/test/code_strategies.py
+++ b/rpython/jit/backend/llsupport/tl/test/code_strategies.py
@@ -4,6 +4,7 @@
from rpython.jit.backend.llsupport.tl import code, interp, stack
from hypothesis.searchstrategy.collections import TupleStrategy, ListStrategy
import hypothesis.internal.conjecture.utils as cu
+from collections import namedtuple
def get_strategy_for(typ):
if typ == code.INT_TYP:
@@ -107,7 +108,7 @@
@composite
def bytecode(draw, max_stack_size=4096):
# get a stack that is the same for one test run
- run_stack = draw(st.shared(st.just(stack.Stack(0)), 'stack2'))
+ run_stack = draw(st.shared(st.just(stack.Stack(0)), 'stack'))
# get a byte code class, only allow what is valid for the run_stack
clazzes = filter(lambda clazz: clazz.filter_bytecode(run_stack),
code.BC_CLASSES)
@@ -124,3 +125,51 @@
return inst
+class DeterministicControlFlowSearchStrategy(SearchStrategy):
+ """ This is flow graph search space is limited to deterministic
+ control flow. This means the execution of this program MUST
+ terminate in at most `max_steps`.
+
+ max/min_steps: one step is one execution in the interpreter loop
+ max_byte_codes: the amount of bytecodes the final program has
+ """
+
+ def __init__(self, stack, min_steps=1, max_steps=2**16,
max_byte_codes=5000):
+ SearchStrategy.__init__(self)
+
+ self.stack = stack
+ self.max_steps = float(max_steps)
+ self.min_steps = min_steps
+ self.max_byte_codes = max_byte_codes
+
+ # self.element_strategy = one_of_strategies(strategies)
+
+ def validate(self):
+ pass
+ #self.element_strategy.validate()
+
+ def do_draw(self, data):
+ bccf = code.ByteCodeControlFlow()
+ result = []
+ while True:
+ stopping_value = 1 - 1.0 / (1 + self.average_length)
+ data.start_example()
+ more = cu.biased_coin(data, stopping_value)
+ if not more:
+ data.stop_example()
+ if len(result) < self.min_size:
+ continue
+ else:
+ break
+ value = data.draw(self.element_strategy)
+ data.stop_example()
+ result.append(value)
+ return bccf
+
[email protected]_strategy
+def control_flow_graph(draw, stack=None, blocks):
+ if stack is None:
+ # get a stack that is the same for one test run
+ stack = stack.Stack(0)
+ return DeterministicControlFlowSearchStrategy(stack)
+
diff --git a/rpython/jit/backend/llsupport/tl/test/test_tl_interp.py
b/rpython/jit/backend/llsupport/tl/test/test_tl_interp.py
--- a/rpython/jit/backend/llsupport/tl/test/test_tl_interp.py
+++ b/rpython/jit/backend/llsupport/tl/test/test_tl_interp.py
@@ -5,6 +5,8 @@
from rpython.jit.backend.llsupport.tl.stack import Stack
from rpython.jit.backend.llsupport.tl.test import code_strategies as st
+STD_SPACE = interp.Space()
+
class TestByteCode(object):
def test_load_str(self):
c = code.Context()
@@ -28,7 +30,6 @@
@given(data())
def test_bytecode_class_generation(self, data):
- space = interp.Space()
stack = Stack(0)
for i in range(10):
clazz = data.draw(st.bytecode_class(stack))
@@ -36,13 +37,12 @@
@given(data())
def test_bytecode_class_generation_int(self, data):
- space = interp.Space()
stack = Stack(0)
- stack.append(space.wrap(0))
+ stack.append(STD_SPACE.wrap(0))
for i in range(10):
clazz = data.draw(st.bytecode_class(stack))
assert(clazz in self.DEFAULT_ACTION_CLASSES)
- stack.append(space.wrap(0))
+ stack.append(STD_SPACE.wrap(0))
for i in range(10):
clazz = data.draw(st.bytecode_class(stack))
assert(clazz in self.DEFAULT_ACTION_CLASSES + \
@@ -50,13 +50,12 @@
@given(data())
def test_bytecode_class_generation_str(self, data):
- space = interp.Space()
stack = Stack(0)
- stack.append(space.wrap("hello"))
+ stack.append(STD_SPACE.wrap("hello"))
for i in range(10):
clazz = data.draw(st.bytecode_class(stack))
assert(clazz in self.DEFAULT_ACTION_CLASSES)
- stack.append(space.wrap("world"))
+ stack.append(STD_SPACE.wrap("world"))
for i in range(10):
clazz = data.draw(st.bytecode_class(stack))
assert(clazz in self.DEFAULT_ACTION_CLASSES + \
@@ -64,20 +63,19 @@
@given(data())
def test_bytecode_class_generation_list(self, data):
- space = interp.Space()
stack = Stack(0)
- stack.append(space.wrap([]))
- stack.append(space.wrap(0))
+ stack.append(STD_SPACE.wrap([]))
+ stack.append(STD_SPACE.wrap(0))
for i in range(10):
clazz = data.draw(st.bytecode_class(stack))
assert(clazz not in (code.InsertList, code.DelList))
- stack.append(space.wrap([space.wrap(1)]))
- stack.append(space.wrap(0))
+ stack.append(STD_SPACE.wrap([STD_SPACE.wrap(1)]))
+ stack.append(STD_SPACE.wrap(0))
for i in range(10):
clazz = data.draw(st.bytecode_class(stack))
assert(clazz in self.DEFAULT_ACTION_CLASSES + \
(code.DelList, code.AppendList))
- stack.append(space.wrap("haskell"))
+ stack.append(STD_SPACE.wrap("haskell"))
for i in range(10):
clazz = data.draw(st.bytecode_class(stack))
assert(clazz in self.DEFAULT_ACTION_CLASSES + \
@@ -85,7 +83,6 @@
@given(data())
def test_empty_stack_no_list_op(self, data):
- space = interp.Space()
stack = Stack(0)
for i in range(10):
clazz = data.draw(st.bytecode_class(stack))
@@ -93,10 +90,26 @@
code.AppendList, code.AddList,
code.AddStr))
+ @given(data())
+ def test_control_flow_split(self, data):
+ stack = Stack(0)
+ cfg = data.draw(st.control_flow_graph(stack))
+ assert cfg.steps > 0
+ # assert that there is at least one block that ends with a cond. jump
+ assert any([isinstance(block[-1], CondJump) for block in cfg.blocks])
+
class TestInterp(object):
@given(st.basic_block(st.bytecode(), min_size=1))
def test_execute_bytecode_block(self, bc_obj_list):
+ self.execute(bc_obj_list)
+
+ @given(st.control_flow_graph())
+ def test_execute_bytecode_block(self, cfg):
+ bc_obj_list = cfg.linearize()
+ self.execute(bc_obj_list)
+
+ def execute(self, bc_obj_list):
bytecode, consts = code.Context().transform(bc_obj_list)
space = interp.Space()
pc = 0
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
