Author: Richard Plangger <planri...@gmail.com>
Branch: gcstress-hypothesis
Changeset: r83086:65a4e92ce40f
Date: 2016-03-15 11:31 +0100
http://bitbucket.org/pypy/pypy/changeset/65a4e92ce40f/
Log: generating control flow using basic blocks, need conditions and
loops
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
@@ -92,6 +92,12 @@
code.append(struct.pack(typ, nmr))
return ''.join(code)
+ def transform_blocks(self, blocks):
+ for block in blocks:
+ for code_obj in block.opcodes:
+ code_obj.encode(self)
+ return self.to_string(), self.consts
+
def transform(self, code_objs):
for code_obj in code_objs:
code_obj.encode(self)
@@ -239,6 +245,14 @@
def splits_control_flow(self):
return True
+ @staticmethod
+ def should_jump(cond, value):
+ # TODO
+ if value == 0 and cond == 0:
+ return True
+ return False
+
+
@requires_stack(LIST_TYP)
@leaves_on_stack(LIST_TYP, INT_TYP)
class LenList(ByteCode):
@@ -269,6 +283,15 @@
# control flow byte codes
BC_CF_CLASSES = [CondJump]
+class ByteCodeBlock(object):
+ def __init__(self, stack):
+ self.init_stack = stack.copy()
+ self.exit_stack = None
+ self.opcodes = []
+
+ def interp_steps(self):
+ return len(self.opcodes)
+
class ByteCodeControlFlow(object):
# see the deterministic control flow search startegy in
# test/code_strategies.py for what steps & byte_codes mean
@@ -276,3 +299,35 @@
self.blocks = []
self.steps = 0
self.byte_codes = 0
+
+ def interp_steps(self):
+ """ how many steps does the interpreter perform to
+ reach the end of the current control flow?
+ """
+ return self.steps
+
+ def linearize(self):
+ from rpython.jit.backend.llsupport.tl import code
+ ctx = code.Context()
+ bytecode, consts = ctx.transform_blocks(self.blocks)
+ return bytecode, consts
+
+ def generate_block(self, data, last_block, strat):
+ if last_block:
+ stack = last_block.init_stack
+ else:
+ from rpython.jit.backend.llsupport.tl.stack import Stack
+ stack = Stack(0)
+
+ bcb = ByteCodeBlock(stack)
+ opcodes = data.draw(strat.draw_from(stack, self))
+ if not opcodes:
+ return None
+ bcb.exit_stack = stack.copy()
+ bcb.opcodes = opcodes
+ self.steps += bcb.interp_steps()
+ self.byte_codes += len(opcodes)
+ self.blocks.append(bcb)
+ return bcb
+
+
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
@@ -161,17 +161,19 @@
assert isinstance(w_lst, W_ListObject)
stack.append(space.wrap(w_lst.size()))
elif opcode == code.CondJump.BYTE_CODE:
+ assert i >= 0
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)
+ w_int = stack.pop()
+ assert isinstance(w_int, W_IntObject)
i += 5
- if CondJump.should_jump(cond, w_int.value):
+ if code.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
+ assert i >= 0
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
@@ -2,7 +2,9 @@
from hypothesis.control import assume
from hypothesis.strategies import composite
from rpython.jit.backend.llsupport.tl import code, interp, stack
+from rpython.jit.backend.llsupport.tl.stack import Stack
from hypothesis.searchstrategy.collections import TupleStrategy, ListStrategy
+from hypothesis.searchstrategy.strategies import SearchStrategy,
one_of_strategies
import hypothesis.internal.conjecture.utils as cu
from collections import namedtuple
@@ -33,12 +35,12 @@
def runtime_stack(min_size=0, average_size=5, max_size=4096,
types=code.all_types):
if max_size == 0:
- return st.just(stack.Stack(0))
+ return st.just(Stack(0))
stack_entries = st.lists(stack_entry(all_types), min_size=min_size,
average_size=average_size,
max_size=max_size)
return stack_entries.map(lambda elems: \
- stack.Stack.from_items(STD_SPACE, elems))
+ Stack.from_items(STD_SPACE, elems))
def get_byte_code_class(num):
return code.BC_NUM_TO_CLASS[num]
@@ -63,7 +65,6 @@
data.draw(self.element_strategy)
for _ in range(self.min_size)
]
-
stopping_value = 1 - 1.0 / (1 + self.average_length)
result = []
while True:
@@ -94,9 +95,12 @@
@st.defines_strategy
def basic_block(strategy, min_size=1, average_size=8, max_size=128):
+ assert max_size >= 1
+ if average_size < max_size:
+ average_size = max_size//2
return BasicBlockStrategy([strategy], min_size=min_size,
average_length=average_size,
- max_size=max_size)
+ max_size=int(max_size))
@st.defines_strategy
def bytecode_class(stack):
@@ -106,9 +110,10 @@
@composite
-def bytecode(draw, max_stack_size=4096):
+def bytecode(draw, run_stack=None):
# get a stack that is the same for one test run
- run_stack = draw(st.shared(st.just(stack.Stack(0)), 'stack'))
+ if run_stack is None:
+ run_stack = draw(st.shared(st.just(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)
@@ -134,42 +139,52 @@
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):
+ def __init__(self, stack, min_steps=1, max_steps=2**16,
max_byte_codes=4000):
SearchStrategy.__init__(self)
self.stack = stack
self.max_steps = float(max_steps)
self.min_steps = min_steps
+ self.average_steps = (self.max_steps - self.min_steps) / 2.0
self.max_byte_codes = max_byte_codes
- # self.element_strategy = one_of_strategies(strategies)
-
def validate(self):
pass
#self.element_strategy.validate()
+ def draw_from(self, stack, bccf):
+ left = int(self.max_steps - bccf.interp_steps())
+ if left <= 0:
+ return st.just(None)
+ if left > 32:
+ left = 32
+ # either draw a normal basic block
+ strats = [basic_block(bytecode(stack), max_size=left)]
+ # or draw a loop
+ #strats.append(deterministic_loop(bytecode(stack)))
+ # or draw a conditional
+ #strats.append(conditional(bytecode(stack)))
+ return one_of_strategies(strats)
+
def do_draw(self, data):
bccf = code.ByteCodeControlFlow()
- result = []
+ last_block = None
+ stopping_value = 1 - 1.0 / (1 + self.average_steps)
while True:
- stopping_value = 1 - 1.0 / (1 + self.average_length)
data.start_example()
+ block = bccf.generate_block(data, last_block, self)
+ data.stop_example()
+ if block is None:
+ break # enough is enough!
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)
+ break
return bccf
@st.defines_strategy
-def control_flow_graph(draw, stack=None, blocks):
+def control_flow_graph(stack=None):
if stack is None:
# get a stack that is the same for one test run
- stack = stack.Stack(0)
+ 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
@@ -101,16 +101,18 @@
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)
+ def test_execute_block(self, bc_obj_list):
+ bytecode, consts = code.Context().transform(bc_obj_list)
+ self.execute(bytecode, consts)
@given(st.control_flow_graph())
- def test_execute_bytecode_block(self, cfg):
- bc_obj_list = cfg.linearize()
- self.execute(bc_obj_list)
+ @settings(perform_health_check=False, min_satisfying_examples=1000)
+ def test_execute_cfg(self, cfg):
+ print("execute_cfg: cfg with steps:", cfg.interp_steps())
+ bytecode, consts = cfg.linearize()
+ self.execute(bytecode, consts)
- def execute(self, bc_obj_list):
- bytecode, consts = code.Context().transform(bc_obj_list)
+ def execute(self, bytecode, consts):
space = interp.Space()
pc = 0
end = len(bytecode)
diff --git a/rpython/jit/backend/llsupport/tl/test/zrpy_gc_hypo_test.py
b/rpython/jit/backend/llsupport/tl/test/zrpy_gc_hypo_test.py
--- a/rpython/jit/backend/llsupport/tl/test/zrpy_gc_hypo_test.py
+++ b/rpython/jit/backend/llsupport/tl/test/zrpy_gc_hypo_test.py
@@ -1,5 +1,5 @@
import py
-from hypothesis import given
+from hypothesis import given, settings
from hypothesis.strategies import lists
from rpython.tool.udir import udir
from rpython.jit.metainterp.optimize import SpeculativeError
@@ -68,3 +68,13 @@
if result != 0:
raise Exception(("could not run program. returned %d"
" stderr:\n%s\nstdout:\n%s\n") % (result, err,
out))
+
+ @given(st.control_flow_graph())
+ @settings(perform_health_check=False, min_satisfying_examples=1000)
+ def test_execute_cfg(self, cfg):
+ print "execute_cfg: cfg with steps:", cfg.interp_steps()
+ bytecode, consts = cfg.linearize()
+ result, out, err = self.execute(bytecode, consts)
+ if result != 0:
+ raise Exception(("could not run program. returned %d"
+ " stderr:\n%s\nstdout:\n%s\n") % (result, err,
out))
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
