def rewrite_can_enter_jit(self, jd, can_enter_jits):
        FUNC = jd._JIT_ENTER_FUNCTYPE
        FUNCPTR = jd._PTR_JIT_ENTER_FUNCTYPE
        jit_enter_fnptr = self.helper_func(FUNCPTR, jd._maybe_enter_jit_fn)

        if len(can_enter_jits) == 0:
            # see test_warmspot.test_no_loop_at_all
            operations = jd.portal_graph.startblock.operations
            op1 = operations[0]
            assert (op1.opname == 'jit_marker' and
                    op1.args[0].value == 'jit_merge_point')
            op0 = SpaceOperation(
                'jit_marker',
                [Constant('can_enter_jit', lltype.Void)] + op1.args[1:],
                None)
            operations.insert(0, op0)
            can_enter_jits = [(jd.portal_graph, jd.portal_graph.startblock, 0)]

        for graph, block, index in can_enter_jits:
            if graph is jd._jit_merge_point_pos[0]:
                continue

            op = block.operations[index]
            greens_v, reds_v = support.decode_hp_hint_args(op)
            args_v = greens_v + reds_v

            vlist = [Constant(jit_enter_fnptr, FUNCPTR)] + args_v

            v_result = Variable()
            v_result.concretetype = lltype.Void
            newop = SpaceOperation('direct_call', vlist, v_result)
            block.operations[index] = newop

def insert_ll_stackcheck(translator):
    from pypy.translator.backendopt.support import find_calls_from
    from pypy.rpython.module.ll_stack import ll_stack_check
    from pypy.tool.algo.graphlib import Edge, make_edge_dict, break_cycles
    rtyper = translator.rtyper
    graph = rtyper.annotate_helper(ll_stack_check, [])
    rtyper.specialize_more_blocks()
    stack_check_ptr = rtyper.getcallable(graph)
    stack_check_ptr_const = Constant(stack_check_ptr, lltype.typeOf(stack_check_ptr))
    edges = []
    graphs_to_patch = {}
    insert_in = {}
    for caller in translator.graphs:
        for block, callee in find_calls_from(translator, caller):
            if getattr(getattr(callee, 'func', None),
                       'insert_stack_check_here', False):
                insert_in[callee.startblock] = True
                continue
            edge = Edge(caller, callee)
            edge.block = block
            edges.append(edge)

    edgedict = make_edge_dict(edges)
    for edge in break_cycles(edgedict, edgedict):
        block = edge.block
        insert_in[block] = True
        
    for block in insert_in:
        v = Variable()
        v.concretetype = lltype.Void
        unwind_op = SpaceOperation('direct_call', [stack_check_ptr_const], v)
        block.operations.insert(0, unwind_op)

def test_optimize_goto_if_not__unknownop():
    v3 = Variable(); v3.concretetype = lltype.Bool
    block = Block([])
    block.operations = [SpaceOperation('foobar', [], v3)]
    block.exitswitch = v3
    block.exits = [FakeLink(False), FakeLink(True)]
    assert not Transformer().optimize_goto_if_not(block)

def test_func_simple():
    # -------------------- flowgraph building --------------------
    #     def f(x):
    #         return x+1
    x = Variable("x")
    x.concretetype = Signed
    result = Variable("result")
    result.concretetype = Signed
    one = Constant(1)
    one.concretetype = Signed
    op = SpaceOperation("int_add", [x, one], result)
    block = Block([x])
    graph = FunctionGraph("f", block)
    block.operations.append(op)
    block.closeblock(Link([result], graph.returnblock))
    graph.getreturnvar().concretetype = Signed
    # --------------------         end        --------------------
    
    F = FuncType([Signed], Signed)
    f = functionptr(F, "f", graph=graph)
    db = LowLevelDatabase()
    db.get(f)
    db.complete()
    dump_on_stdout(db)

    S = GcStruct('testing', ('fptr', Ptr(F)))
    s = malloc(S)
    s.fptr = f
    db = LowLevelDatabase()
    db.get(s)
    db.complete()
    dump_on_stdout(db)

def insert_ll_stackcheck(translator):
    from pypy.translator.backendopt.support import find_calls_from
    from pypy.rlib.rstack import stack_check
    from pypy.tool.algo.graphlib import Edge, make_edge_dict, break_cycles_v

    rtyper = translator.rtyper
    graph = rtyper.annotate_helper(stack_check, [])
    rtyper.specialize_more_blocks()
    stack_check_ptr = rtyper.getcallable(graph)
    stack_check_ptr_const = Constant(stack_check_ptr, lltype.typeOf(stack_check_ptr))
    edges = set()
    insert_in = set()
    for caller in translator.graphs:
        for block, callee in find_calls_from(translator, caller):
            if getattr(getattr(callee, "func", None), "insert_stack_check_here", False):
                insert_in.add(callee.startblock)
                continue
            if block is not caller.startblock:
                edges.add((caller.startblock, block))
            edges.add((block, callee.startblock))

    edgelist = [Edge(block1, block2) for (block1, block2) in edges]
    edgedict = make_edge_dict(edgelist)
    for block in break_cycles_v(edgedict, edgedict):
        insert_in.add(block)

    for block in insert_in:
        v = Variable()
        v.concretetype = lltype.Void
        unwind_op = SpaceOperation("direct_call", [stack_check_ptr_const], v)
        block.operations.insert(0, unwind_op)
    return len(insert_in)

    def flowin(self, block, count, vars, newvarsmap):
        # in this 'block', follow where the 'var' goes to and replace
        # it by a flattened-out family of variables.  This family is given
        # by newvarsmap, whose keys are the 'flatnames'.
        self.last_removed_access = None

        def list_newvars():
            return [newvarsmap[key] for key in self.flatnames]

        assert block.operations != ()
        self.newops = []
        for op in block.operations:
            for arg in op.args[1:]:   # should be the first arg only
                assert arg not in vars
            if op.args and op.args[0] in vars:
                self.flowin_op(op, vars, newvarsmap)
            elif op.result in vars:
                assert op.opname == self.MALLOC_OP
                progress = True
                # drop the "malloc" operation
                newvarsmap = self.flatconstants.copy()   # zero initial values
                # if there are substructures, they are now individually
                # malloc'ed in an exploded way.  (They will typically be
                # removed again by the next malloc removal pass.)
                for key in self.needsubmallocs:
                    v = Variable()
                    v.concretetype = self.newvarstype[key]
                    c = Constant(v.concretetype.TO, lltype.Void)
                    if c.value == op.args[0].value:
                        progress = False   # replacing a malloc with
                                           # the same malloc!
                    newop = self.recreate_malloc(c, v)
                    self.newops.append(newop)
                    newvarsmap[key] = v
                count[0] += progress
            else:
                self.newops.append(op)

        assert block.exitswitch not in vars

        for link in block.exits:
            appended = False
            newargs = []
            for arg in link.args:
                if arg in vars:
                    if not appended:
                        newargs += list_newvars()
                        appended = True
                else:
                    newargs.append(arg)
            link.args[:] = newargs

        self.insert_keepalives(list_newvars())
        block.operations[:] = self.newops

 def insert_keepalives(self, newvars):
     if self.last_removed_access is not None:
         keepalives = []
         for v in newvars:
             T = v.concretetype
             if isinstance(T, lltype.Ptr) and T._needsgc():
                 v0 = Variable()
                 v0.concretetype = lltype.Void
                 newop = SpaceOperation('keepalive', [v], v0)
                 keepalives.append(newop)
         self.newops[self.last_removed_access:self.last_removed_access] = keepalives

    def transform_graph(self, graph):
        if graph in self.minimal_transform:
            if self.minimalgctransformer:
                self.minimalgctransformer.transform_graph(graph)
            del self.minimal_transform[graph]
            return
        if graph in self.seen_graphs:
            return
        self.seen_graphs[graph] = True

        self.links_to_split = {} # link -> vars to pop_alive across the link

        # for sanity, we need an empty block at the start of the graph
        inserted_empty_startblock = False
        if not starts_with_empty_block(graph):
            insert_empty_startblock(self.translator.annotator, graph)
            inserted_empty_startblock = True
        is_borrowed = self.compute_borrowed_vars(graph)

        for block in graph.iterblocks():
            self.transform_block(block, is_borrowed)

        for link, livecounts in self.links_to_split.iteritems():
            llops = LowLevelOpList()
            for var, livecount in livecounts.iteritems():
                for i in range(livecount):
                    self.pop_alive(var, llops)
                for i in range(-livecount):
                    self.push_alive(var, llops)
            if llops:
                if link.prevblock.exitswitch is None:
                    link.prevblock.operations.extend(llops)
                else:
                    insert_empty_block(self.translator.annotator, link, llops)

        # remove the empty block at the start of the graph, which should
        # still be empty (but let's check)
        if starts_with_empty_block(graph) and inserted_empty_startblock:
            old_startblock = graph.startblock
            graph.startblock.isstartblock = False
            graph.startblock = graph.startblock.exits[0].target
            graph.startblock.isstartblock = True

        checkgraph(graph)

        self.links_to_split = None
        v = Variable('vanishing_exc_value')
        v.concretetype = self.get_lltype_of_exception_value()
        llops = LowLevelOpList()
        self.pop_alive(v, llops)
        graph.exc_cleanup = (v, list(llops))
        return is_borrowed    # xxx for tests only

def generate_keepalive(vars, annotator=None):
    keepalive_ops = []
    for v in vars:
        if isinstance(v, Constant):
            continue
        if v.concretetype._is_atomic():
            continue
        v_keepalive = Variable()
        v_keepalive.concretetype = lltype.Void
        if annotator is not None:
            annotator.setbinding(v_keepalive, s_ImpossibleValue)
        keepalive_ops.append(SpaceOperation('keepalive', [v], v_keepalive))
    return keepalive_ops

def test_rename_on_links():
    v1 = Variable()
    v2 = Variable(); v2.concretetype = llmemory.Address
    v3 = Variable()
    block = Block([v1])
    block.operations = [SpaceOperation('cast_pointer', [v1], v2)]
    block2 = Block([v3])
    block.closeblock(Link([v2], block2))
    Transformer().optimize_block(block)
    assert block.inputargs == [v1]
    assert block.operations == []
    assert block.exits[0].target is block2
    assert block.exits[0].args == [v1]

 def transform_except_block(self, graph, block):
     # attach an except block -- let's hope that nobody uses it
     graph.exceptblock = Block([Variable('etype'),   # exception class
                                Variable('evalue')])  # exception value
     graph.exceptblock.operations = ()
     graph.exceptblock.closeblock()
     
     result = Variable()
     result.concretetype = lltype.Void
     block.operations = [SpaceOperation(
        "direct_call", [self.rpyexc_raise_ptr] + block.inputargs, result)]
     l = Link([error_constant(graph.returnblock.inputargs[0].concretetype)], graph.returnblock)
     block.recloseblock(l)

def test_optimize_goto_if_not__ptr_iszero():
    for opname in ['ptr_iszero', 'ptr_nonzero']:
        v1 = Variable()
        v3 = Variable(); v3.concretetype = lltype.Bool
        block = Block([v1])
        block.operations = [SpaceOperation(opname, [v1], v3)]
        block.exitswitch = v3
        block.exits = exits = [FakeLink(False), FakeLink(True)]
        res = Transformer().optimize_goto_if_not(block)
        assert res == True
        assert block.operations == []
        assert block.exitswitch == (opname, v1, '-live-before')
        assert block.exits == exits

 def test_regalloc_exitswitch_2(self):
     v1 = Variable(); v1.concretetype = rclass.CLASSTYPE
     v2 = Variable(); v2.concretetype = rclass.CLASSTYPE
     v3 = Variable(); v3.concretetype = rclass.CLASSTYPE
     v4 = Variable(); v4.concretetype = rclass.CLASSTYPE
     block = Block([])
     block.operations = [
         SpaceOperation('res_call', [], v1),
         SpaceOperation('-live-', [], None),
         ]
     graph = FunctionGraph('f', block, v4)
     exclink = Link([v2], graph.returnblock)
     exclink.llexitcase = 123     # normally an exception class
     exclink.last_exception = v2
     exclink.last_exc_value = "unused"
     block.exitswitch = c_last_exception
     block.closeblock(Link([v1], graph.returnblock),
                      exclink)
     #
     self.check_assembler(graph, """
         res_call -> %i0
         -live-
         catch_exception L1
         int_return %i0
         ---
         L1:
         goto_if_exception_mismatch $123, L2
         last_exception -> %i0
         int_return %i0
         ---
         L2:
         reraise
     """)

def test_optimize_goto_if_not():
    v1 = Variable()
    v2 = Variable()
    v3 = Variable(); v3.concretetype = lltype.Bool
    sp1 = SpaceOperation('foobar', [], None)
    sp2 = SpaceOperation('foobaz', [], None)
    block = Block([v1, v2])
    block.operations = [sp1, SpaceOperation('int_gt', [v1, v2], v3), sp2]
    block.exitswitch = v3
    block.exits = exits = [FakeLink(False), FakeLink(True)]
    res = Transformer().optimize_goto_if_not(block)
    assert res == True
    assert block.operations == [sp1, sp2]
    assert block.exitswitch == ('int_gt', v1, v2)
    assert block.exits == exits

    def create_proxy_graph(self, op):
        """ creates a graph which calls the original function, checks for
        raised exceptions, fetches and then raises them again. If this graph is
        inlined, the correct exception matching blocks are produced."""
        # XXX slightly annoying: construct a graph by hand
        # but better than the alternative
        result = copyvar(None, op.result)
        opargs = []
        inputargs = []
        callargs = []
        ARGTYPES = []
        for var in op.args:
            if isinstance(var, Variable):
                v = Variable()
                v.concretetype = var.concretetype
                inputargs.append(v)
                opargs.append(v)
                callargs.append(var)
                ARGTYPES.append(var.concretetype)
            else:
                opargs.append(var)
        newop = SpaceOperation(op.opname, opargs, result)
        startblock = Block(inputargs)
        startblock.operations.append(newop) 
        newgraph = FunctionGraph("dummy_exc1", startblock)
        startblock.closeblock(Link([result], newgraph.returnblock))
        newgraph.returnblock.inputargs[0].concretetype = op.result.concretetype
        self.gen_exc_check(startblock, newgraph.returnblock)
        excblock = Block([])

        llops = rtyper.LowLevelOpList(None)
        var_value = self.gen_getfield('exc_value', llops)
        var_type  = self.gen_getfield('exc_type' , llops)
        #
        c_check1 = self.c_assertion_error_ll_exc_type
        c_check2 = self.c_n_i_error_ll_exc_type
        llops.genop('debug_catch_exception', [var_type, c_check1, c_check2])
        #
        self.gen_setfield('exc_value', self.c_null_evalue, llops)
        self.gen_setfield('exc_type',  self.c_null_etype,  llops)
        excblock.operations[:] = llops
        newgraph.exceptblock.inputargs[0].concretetype = self.lltype_of_exception_type
        newgraph.exceptblock.inputargs[1].concretetype = self.lltype_of_exception_value
        excblock.closeblock(Link([var_type, var_value], newgraph.exceptblock))
        startblock.exits[True].target = excblock
        startblock.exits[True].args = []
        fptr = self.constant_func("dummy_exc1", ARGTYPES, op.result.concretetype, newgraph)
        return newgraph, SpaceOperation("direct_call", [fptr] + callargs, op.result) 

 def transform_jump_to_except_block(self, graph, entrymap, link):
     reraise = self.comes_from_last_exception(entrymap, link)
     result = Variable()
     result.concretetype = lltype.Void
     block = Block([copyvar(None, v) for v in graph.exceptblock.inputargs])
     if reraise:
         block.operations = [SpaceOperation("direct_call", [self.rpyexc_reraise_ptr] + block.inputargs, result)]
     else:
         block.operations = [
             SpaceOperation("direct_call", [self.rpyexc_raise_ptr] + block.inputargs, result),
             SpaceOperation("debug_record_traceback", [], varoftype(lltype.Void)),
         ]
     link.target = block
     RETTYPE = graph.returnblock.inputargs[0].concretetype
     l = Link([error_constant(RETTYPE)], graph.returnblock)
     block.recloseblock(l)

def prepare_constant_fold_link(link, constants, splitblocks):
    block = link.target
    if not block.operations:
        # when the target block has no operation, there is nothing we can do
        # except trying to fold an exitswitch
        if block.exitswitch is not None and block.exitswitch in constants:
            llexitvalue = constants[block.exitswitch].value
            rewire_link_for_known_exitswitch(link, llexitvalue)
        return

    folded_count = fold_op_list(block.operations, constants, exit_early=True)

    n = len(block.operations)
    if block.exitswitch == c_last_exception:
        n -= 1
    # is the next, non-folded operation an indirect_call?
    m = folded_count
    while m < n and block.operations[m].opname == 'keepalive':
        m += 1
    if m < n:
        nextop = block.operations[m]
        if nextop.opname == 'indirect_call' and nextop.args[0] in constants:
            # indirect_call -> direct_call
            callargs = [constants[nextop.args[0]]]
            constants1 = constants.copy()
            complete_constants(link, constants1)
            newkeepalives = []
            for i in range(folded_count, m):
                [v] = block.operations[i].args
                v = constants1.get(v, v)
                v_void = Variable()
                v_void.concretetype = lltype.Void
                newkeepalives.append(SpaceOperation('keepalive', [v], v_void))
            for v in nextop.args[1:-1]:
                callargs.append(constants1.get(v, v))
            v_result = Variable(nextop.result)
            v_result.concretetype = nextop.result.concretetype
            constants[nextop.result] = v_result
            callop = SpaceOperation('direct_call', callargs, v_result)
            newblock = insert_empty_block(None, link, newkeepalives + [callop])
            [link] = newblock.exits
            assert link.target is block
            folded_count = m+1

    if folded_count > 0:
        splits = splitblocks.setdefault(block, [])
        splits.append((folded_count, link, constants))

def test_is_pure():
    from pypy.objspace.flow.model import Variable, Constant
    from pypy.rpython import rclass
    assert llop.bool_not.is_pure([Variable()])
    assert llop.debug_assert.is_pure([Variable()])
    assert not llop.int_add_ovf.is_pure([Variable(), Variable()])
    #
    S1 = lltype.GcStruct('S', ('x', lltype.Signed), ('y', lltype.Signed))
    v_s1 = Variable()
    v_s1.concretetype = lltype.Ptr(S1)
    assert not llop.setfield.is_pure([v_s1, Constant('x'), Variable()])
    assert not llop.getfield.is_pure([v_s1, Constant('y')])
    #
    A1 = lltype.GcArray(lltype.Signed)
    v_a1 = Variable()
    v_a1.concretetype = lltype.Ptr(A1)
    assert not llop.setarrayitem.is_pure([v_a1, Variable(), Variable()])
    assert not llop.getarrayitem.is_pure([v_a1, Variable()])
    assert llop.getarraysize.is_pure([v_a1])
    #
    S2 = lltype.GcStruct('S', ('x', lltype.Signed), ('y', lltype.Signed),
                         hints={'immutable': True})
    v_s2 = Variable()
    v_s2.concretetype = lltype.Ptr(S2)
    assert not llop.setfield.is_pure([v_s2, Constant('x'), Variable()])
    assert llop.getfield.is_pure([v_s2, Constant('y')])
    #
    A2 = lltype.GcArray(lltype.Signed, hints={'immutable': True})
    v_a2 = Variable()
    v_a2.concretetype = lltype.Ptr(A2)
    assert not llop.setarrayitem.is_pure([v_a2, Variable(), Variable()])
    assert llop.getarrayitem.is_pure([v_a2, Variable()])
    assert llop.getarraysize.is_pure([v_a2])
    #
    for kind in [rclass.IR_MUTABLE, rclass.IR_IMMUTABLE,
                 rclass.IR_IMMUTABLE_ARRAY, rclass.IR_QUASIIMMUTABLE,
                 rclass.IR_QUASIIMMUTABLE_ARRAY]:
        accessor = rclass.FieldListAccessor()
        S3 = lltype.GcStruct('S', ('x', lltype.Signed), ('y', lltype.Signed),
                             hints={'immutable_fields': accessor})
        accessor.initialize(S3, {'x': kind})
        v_s3 = Variable()
        v_s3.concretetype = lltype.Ptr(S3)
        assert not llop.setfield.is_pure([v_s3, Constant('x'), Variable()])
        assert not llop.setfield.is_pure([v_s3, Constant('y'), Variable()])
        assert llop.getfield.is_pure([v_s3, Constant('x')]) is kind
        assert not llop.getfield.is_pure([v_s3, Constant('y')])

def test_optimize_goto_if_not__exit():
    # this case occurs in practice, e.g. with RPython code like:
    #     return bool(p) and p.somefield > 0
    v1 = Variable()
    v2 = Variable()
    v3 = Variable(); v3.concretetype = lltype.Bool
    block = Block([v1, v2])
    block.operations = [SpaceOperation('int_gt', [v1, v2], v3)]
    block.exitswitch = v3
    block.exits = exits = [FakeLink(False), FakeLink(True)]
    block.exits[1].args = [v3]
    res = Transformer().optimize_goto_if_not(block)
    assert res == True
    assert block.operations == []
    assert block.exitswitch == ('int_gt', v1, v2)
    assert block.exits == exits
    assert exits[1].args == [const(True)]

 def genop(self, opname, args_v, resulttype=None):
     try:
         for v in args_v:
             v.concretetype
     except AttributeError:
         raise AssertionError("wrong level!  you must call hop.inputargs()"
                              " and pass its result to genop(),"
                              " never hop.args_v directly.")
     vresult = Variable()
     self.append(SpaceOperation(opname, args_v, vresult))
     if resulttype is None:
         vresult.concretetype = Void
         return None
     else:
         if isinstance(resulttype, Repr):
             resulttype = resulttype.lowleveltype
         assert isinstance(resulttype, LowLevelType)
         vresult.concretetype = resulttype
         return vresult