modelverse/kernel/modelverse_jit/bytecode_to_tree.py

"""Naively converts bytecode IR to tree IR."""

import modelverse_jit.bytecode_ir as bytecode_ir
import modelverse_jit.tree_ir as tree_ir
import modelverse_jit.runtime as jit_runtime
import modelverse_kernel.primitives as primitive_functions

def get_parameter_names(compiled_function):
    """Gets the given compiled function's parameter names."""
    if hasattr(compiled_function, '__code__'):
        return compiled_function.__code__.co_varnames[
            :compiled_function.__code__.co_argcount]
    elif hasattr(compiled_function, '__init__'):
        return get_parameter_names(compiled_function.__init__)[1:]
    else:
        raise ValueError("'compiled_function' must be a function or a type.")

def apply_intrinsic(intrinsic_function, named_args):
    """Applies the given intrinsic to the given sequence of named arguments."""
    param_names = get_parameter_names(intrinsic_function)
    if tuple(param_names) == tuple([n for n, _ in named_args]):
        # Perfect match. Yay!
        return intrinsic_function(**dict(named_args))
    else:
        # We'll have to store the arguments into locals to preserve
        # the order of evaluation.
        stored_args = [(name, tree_ir.StoreLocalInstruction(None, arg)) for name, arg in named_args]
        arg_value_dict = dict([(name, arg.create_load()) for name, arg in stored_args])
        store_instructions = [instruction for _, instruction in stored_args]
        return tree_ir.CompoundInstruction(
            tree_ir.create_block(*store_instructions),
            intrinsic_function(**arg_value_dict))

def retrieve_task_root():
    """Creates an instruction that stores the task_root variable in a local."""
    return tree_ir.StoreLocalInstruction(
        'task_root',
        tree_ir.LoadIndexInstruction(
            tree_ir.LoadLocalInstruction(jit_runtime.KWARGS_PARAMETER_NAME),
            tree_ir.LiteralInstruction('task_root')))

def load_kernel():
    """Creates an instruction that loads the Modelverse kernel."""
    return tree_ir.LoadIndexInstruction(
        tree_ir.LoadLocalInstruction(jit_runtime.KWARGS_PARAMETER_NAME),
        tree_ir.LiteralInstruction('mvk'))

def create_access(pointer):
    """Creates a tree that loads the given pointer's value."""
    # Accessing a variable is pretty easy. It really just boils
    # down to reading the value corresponding to the 'value' key
    # of the variable.
    #
    #     value, = yield [("RD", [returnvalue, "value"])]
    #
    return tree_ir.ReadDictionaryValueInstruction(
        pointer,
        tree_ir.LiteralInstruction('value'))

def create_assign(pointer, value):
    """Creates a tree that assigns the given value to the given pointer."""
    # Assignments work like this:
    #
    #     value_link = yield [("RDE", [variable, "value"])]
    #     _, _ =       yield [("CD", [variable, "value", value]),
    #                         ("DE", [value_link])]
    #
    variable = tree_ir.StoreLocalInstruction(None, pointer)
    value = tree_ir.StoreLocalInstruction(None, value)
    value_link = tree_ir.StoreLocalInstruction(
        'value_link',
        tree_ir.ReadDictionaryEdgeInstruction(
            variable.create_load(),
            tree_ir.LiteralInstruction('value')))

    return tree_ir.create_block(
        variable,
        value,
        value_link,
        tree_ir.CreateDictionaryEdgeInstruction(
            variable.create_load(),
            tree_ir.LiteralInstruction('value'),
            value.create_load()),
        tree_ir.DeleteEdgeInstruction(
            value_link.create_load()))

def create_input(use_input_function=False):
    """Creates an instruction that pops a value from the input queue."""
    # Possible alternative to the explicit syntax tree: just call the jit_runtime.__get_input
    # function.
    if use_input_function:
        return tree_ir.create_jit_call(
            tree_ir.LoadGlobalInstruction(jit_runtime.GET_INPUT_FUNCTION_NAME),
            [],
            tree_ir.LoadLocalInstruction(jit_runtime.KWARGS_PARAMETER_NAME))

    # The plan is to generate this tree:
    #
    #     value = None
    #     while True:
    #         _input = yield [("RD", [task_root, "input"])]
    #         value = yield [("RD", [_input, "value"])]
    #
    #         if value is None:
    #             kwargs['mvk'].success = False # to avoid blocking
    #             yield None # nop/interrupt
    #         else:
    #             break
    #
    #     _next = yield [("RD", [_input, "next"])]
    #     yield [("CD", [task_root, "input", _next])]
    #     yield [("CE", [jit_locals, value])]
    #     yield [("DN", [_input])]

    task_root = retrieve_task_root()
    _input = tree_ir.StoreLocalInstruction(
        None,
        tree_ir.ReadDictionaryValueInstruction(
            task_root.create_load(),
            tree_ir.LiteralInstruction('input')))

    value = tree_ir.StoreLocalInstruction(
        None,
        tree_ir.ReadDictionaryValueInstruction(
            _input.create_load(),
            tree_ir.LiteralInstruction('value')))

    raise primitive_functions.PrimitiveFinished(
        tree_ir.CompoundInstruction(
            tree_ir.create_block(
                task_root,
                value.create_store(tree_ir.LiteralInstruction(None)),
                tree_ir.LoopInstruction(
                    tree_ir.create_block(
                        _input,
                        value,
                        tree_ir.SelectInstruction(
                            tree_ir.BinaryInstruction(
                                value.create_load(),
                                'is',
                                tree_ir.LiteralInstruction(None)),
                            tree_ir.create_block(
                                tree_ir.StoreMemberInstruction(
                                    load_kernel(),
                                    'success',
                                    tree_ir.LiteralInstruction(False)),
                                tree_ir.NopInstruction()),
                            tree_ir.BreakInstruction()))),
                tree_ir.CreateDictionaryEdgeInstruction(
                    task_root.create_load(),
                    tree_ir.LiteralInstruction('input'),
                    tree_ir.ReadDictionaryValueInstruction(
                        _input.create_load(),
                        tree_ir.LiteralInstruction('next'))),
                tree_ir.CreateEdgeInstruction(
                    tree_ir.LoadLocalInstruction(jit_runtime.LOCALS_NODE_NAME),
                    value.create_load()),
                tree_ir.DeleteNodeInstruction(_input.create_load())),
            value.create_load()))

def create_output(output_value):
    """Creates an output instruction that outputs the given value."""
    # The plan is to basically generate this tree:
    #
    # value = <some tree>
    # last_output, last_output_link, new_last_output = \
    #                 yield [("RD", [task_root, "last_output"]),
    #                        ("RDE", [task_root, "last_output"]),
    #                        ("CN", []),
    #                       ]
    # _, _, _, _ = \
    #                 yield [("CD", [last_output, "value", value]),
    #                        ("CD", [last_output, "next", new_last_output]),
    #                        ("CD", [task_root, "last_output", new_last_output]),
    #                        ("DE", [last_output_link])
    #                       ]
    # yield None

    value_local = tree_ir.StoreLocalInstruction('value', output_value)

    store_task_root = retrieve_task_root()
    last_output = tree_ir.StoreLocalInstruction(
        'last_output',
        tree_ir.ReadDictionaryValueInstruction(
            store_task_root.create_load(),
            tree_ir.LiteralInstruction('last_output')))

    last_output_link = tree_ir.StoreLocalInstruction(
        'last_output_link',
        tree_ir.ReadDictionaryEdgeInstruction(
            store_task_root.create_load(),
            tree_ir.LiteralInstruction('last_output')))

    new_last_output = tree_ir.StoreLocalInstruction(
        'new_last_output',
        tree_ir.CreateNodeInstruction())

    return tree_ir.create_block(
        value_local,
        store_task_root,
        last_output,
        last_output_link,
        new_last_output,
        tree_ir.CreateDictionaryEdgeInstruction(
            last_output.create_load(),
            tree_ir.LiteralInstruction('value'),
            value_local.create_load()),
        tree_ir.CreateDictionaryEdgeInstruction(
            last_output.create_load(),
            tree_ir.LiteralInstruction('next'),
            new_last_output.create_load()),
        tree_ir.CreateDictionaryEdgeInstruction(
            store_task_root.create_load(),
            tree_ir.LiteralInstruction('last_output'),
            new_last_output.create_load()),
        tree_ir.DeleteEdgeInstruction(last_output_link.create_load()),
        tree_ir.NopInstruction())

def create_indirect_call(target, argument_list):
    """Creates an indirect call to the function defined by the node with the id computed
       by the first argument."""
    # Call the __call_function function to run the interpreter, like so:
    #
    # __call_function(function_id, { first_param_name : first_param_val, ... }, **kwargs)
    #
    dict_literal = tree_ir.DictionaryLiteralInstruction(
        [(tree_ir.LiteralInstruction(key), val) for key, val in argument_list])
    return tree_ir.create_jit_call(
        tree_ir.LoadGlobalInstruction(jit_runtime.CALL_FUNCTION_NAME),
        [('function_id', target), ('named_arguments', dict_literal)],
        tree_ir.LoadLocalInstruction(jit_runtime.KWARGS_PARAMETER_NAME))

class LocalNameMap(object):
    """A map that converts local variable nodes to identifiers."""
    def __init__(self, local_mapping=None):
        if local_mapping is None:
            local_mapping = {}
        self.local_mapping = local_mapping

    def get_local_name(self, local_variable_id):
        """Gets the name for the local variable node with the given id."""
        if local_variable_id not in self.local_mapping:
            self.local_mapping[local_variable_id] = 'local%d' % local_variable_id
        return self.local_mapping[local_variable_id]

class AnalysisState(object):
    """The state of a bytecode analysis call graph."""
    def __init__(self, jit, body_id, task_root, local_mapping, max_instructions=None):
        self.analyzed_instructions = set()
        self.function_vars = set()
        self.local_vars = set()
        self.body_id = body_id
        self.max_instructions = max_instructions
        self.task_root = task_root
        self.jit = jit
        self.local_name_map = LocalNameMap(local_mapping)
        self.function_name = jit.jitted_entry_points[body_id]
        self.enclosing_loop_instruction = None

    def register_local_var(self, local_id):
        """Registers the given variable node id as a local."""
        if local_id in self.function_vars:
            raise jit_runtime.JitCompilationFailedException(
                "Local is used as target of function call.")
        self.local_vars.add(local_id)

    def register_function_var(self, local_id):
        """Registers the given variable node id as a function."""
        if local_id in self.local_vars:
            raise jit_runtime.JitCompilationFailedException(
                "Local is used as target of function call.")
        self.function_vars.add(local_id)

    def analyze(self, instruction):
        """Tries to build an intermediate representation from the instruction with the
        given id."""
        # Check the analyzed_instructions set for instruction_id to avoid
        # infinite loops.
        if instruction in self.analyzed_instructions:
            raise jit_runtime.JitCompilationFailedException(
                'Cannot jit non-tree instruction graph.')
        elif (self.max_instructions is not None and
              len(self.analyzed_instructions) > self.max_instructions):
            raise jit_runtime.JitCompilationFailedException(
                'Maximum number of instructions exceeded.')

        self.analyzed_instructions.add(instruction)
        instruction_type = type(instruction)
        if instruction_type in self.instruction_analyzers:
            # Analyze the instruction itself.
            outer_result, = yield [
                ("CALL_ARGS", [self.instruction_analyzers[instruction_type], (self, instruction)])]
            if self.jit.tracing_enabled and instruction.debug_information is not None:
                outer_result = tree_ir.with_debug_info_trace(
                    outer_result, instruction.debug_information, self.function_name)
            # Check if the instruction has a 'next' instruction.
            if instruction.next_instruction is None:
                raise primitive_functions.PrimitiveFinished(outer_result)
            else:
                next_result, = yield [
                    ("CALL_ARGS", [self.analyze, (instruction.next_instruction,)])]
                raise primitive_functions.PrimitiveFinished(
                    tree_ir.CompoundInstruction(
                        outer_result,
                        next_result))
        else:
            raise jit_runtime.JitCompilationFailedException(
                "Unknown instruction type: '%s'" % type(instruction))

    def analyze_all(self, instruction_ids):
        """Tries to compile a list of IR trees from the given list of instruction ids."""
        results = []
        for inst in instruction_ids:
            analyzed_inst, = yield [("CALL_ARGS", [self.analyze, (inst,)])]
            results.append(analyzed_inst)

        raise primitive_functions.PrimitiveFinished(results)

    def analyze_return(self, instruction):
        """Tries to analyze the given 'return' instruction."""
        def create_return(return_value):
            return tree_ir.ReturnInstruction(
                tree_ir.CompoundInstruction(
                    return_value,
                    tree_ir.DeleteEdgeInstruction(
                        tree_ir.LoadLocalInstruction(jit_runtime.LOCALS_EDGE_NAME))))

        if instruction.value is None:
            raise primitive_functions.PrimitiveFinished(
                create_return(
                    tree_ir.EmptyInstruction()))
        else:
            retval, = yield [("CALL_ARGS", [self.analyze, (instruction.value,)])]
            raise primitive_functions.PrimitiveFinished(
                create_return(retval))

    def analyze_if(self, instruction):
        """Tries to analyze the given 'if' instruction."""
        if instruction.else_clause is None:
            (cond_r, true_r), = yield [
                ("CALL_ARGS",
                 [self.analyze_all,
                  ([instruction.condition, instruction.if_clause],)])]
            false_r = tree_ir.EmptyInstruction()
        else:
            (cond_r, true_r, false_r), = yield [
                ("CALL_ARGS",
                 [self.analyze_all,
                  ([instruction.condition, instruction.if_clause, instruction.else_clause],)])]

        raise primitive_functions.PrimitiveFinished(
            tree_ir.SelectInstruction(
                tree_ir.ReadValueInstruction(cond_r),
                true_r,
                false_r))

    def analyze_while(self, instruction):
        """Tries to analyze the given 'while' instruction."""
        # Analyze the condition.
        cond_r, = yield [("CALL_ARGS", [self.analyze, (instruction.condition,)])]
        # Store the old enclosing loop on the stack, and make this loop the
        # new enclosing loop.
        old_loop_instruction = self.enclosing_loop_instruction
        self.enclosing_loop_instruction = instruction
        body_r, = yield [("CALL_ARGS", [self.analyze, (instruction.body,)])]
        # Restore hte old enclosing loop.
        self.enclosing_loop_instruction = old_loop_instruction
        if self.jit.nop_insertion_enabled:
            create_loop_body = lambda check, body: tree_ir.create_block(
                check,
                body_r,
                tree_ir.NopInstruction())
        else:
            create_loop_body = tree_ir.CompoundInstruction

        raise primitive_functions.PrimitiveFinished(
            tree_ir.LoopInstruction(
                create_loop_body(
                    tree_ir.SelectInstruction(
                        tree_ir.ReadValueInstruction(cond_r),
                        tree_ir.EmptyInstruction(),
                        tree_ir.BreakInstruction()),
                    body_r)))

    def analyze_constant(self, instruction):
        """Tries to analyze the given 'constant' (literal) instruction."""
        raise primitive_functions.PrimitiveFinished(
            tree_ir.LiteralInstruction(instruction.constant_id))

    def analyze_output(self, instruction):
        """Tries to analyze the given 'output' instruction."""
        value_val, = yield [("CALL_ARGS", [self.analyze, (instruction.value,)])]
        raise primitive_functions.PrimitiveFinished(create_output(value_val))

    def analyze_input(self, _):
        """Tries to analyze the given 'input' instruction."""
        raise primitive_functions.PrimitiveFinished(create_input(self.jit.input_function_enabled))

    def analyze_resolve(self, instruction):
        """Tries to analyze the given 'resolve' instruction."""
        # To resolve a variable, we'll do something along the
        # lines of:
        #
        #     if 'local_var' in locals():
        #         tmp = local_var
        #     else:
        #         _globals, = yield [("RD", [task_root, "globals"])]
        #         global_var, = yield [("RD", [_globals, var_name])]
        #
        #         if global_var is None:
        #             raise Exception("Not found as global: %s" % (var_name))
        #
        #         tmp = global_var

        name = self.local_name_map.get_local_name(instruction.variable.node_id)

        if instruction.variable.name is None:
            raise primitive_functions.PrimitiveFinished(
                tree_ir.LoadLocalInstruction(name))

        task_root = retrieve_task_root()
        global_var = tree_ir.StoreLocalInstruction(
            'global_var',
            tree_ir.ReadDictionaryValueInstruction(
                tree_ir.ReadDictionaryValueInstruction(
                    task_root.create_load(),
                    tree_ir.LiteralInstruction('globals')),
                tree_ir.LiteralInstruction(instruction.variable.name)))

        err_block = tree_ir.SelectInstruction(
            tree_ir.BinaryInstruction(
                global_var.create_load(),
                'is',
                tree_ir.LiteralInstruction(None)),
            tree_ir.RaiseInstruction(
                tree_ir.CallInstruction(
                    tree_ir.LoadGlobalInstruction('Exception'),
                    [tree_ir.LiteralInstruction(
                        jit_runtime.GLOBAL_NOT_FOUND_MESSAGE_FORMAT % instruction.variable.name)
                    ])),
            tree_ir.EmptyInstruction())

        raise primitive_functions.PrimitiveFinished(
            tree_ir.SelectInstruction(
                tree_ir.LocalExistsInstruction(name),
                tree_ir.LoadLocalInstruction(name),
                tree_ir.CompoundInstruction(
                    tree_ir.create_block(
                        task_root,
                        global_var,
                        err_block),
                    global_var.create_load())))

    def analyze_declare(self, instruction):
        """Tries to analyze the given 'declare' function."""
        self.register_local_var(instruction.variable.node_id)

        name = self.local_name_map.get_local_name(instruction.variable.node_id)

        # The following logic declares a local:
        #
        #     if 'local_name' not in locals():
        #         local_name, = yield [("CN", [])]
        #         yield [("CE", [LOCALS_NODE_NAME, local_name])]

        raise primitive_functions.PrimitiveFinished(
            tree_ir.SelectInstruction(
                tree_ir.LocalExistsInstruction(name),
                tree_ir.EmptyInstruction(),
                tree_ir.create_new_local_node(
                    name,
                    tree_ir.LoadLocalInstruction(jit_runtime.LOCALS_NODE_NAME))))

    def analyze_global(self, instruction):
        """Tries to analyze the given 'global' (declaration) instruction."""
        # To declare a variable, we'll do something along the
        # lines of:
        #
        #     _globals, = yield [("RD", [task_root, "globals"])]
        #     global_var = yield [("RD", [_globals, var_name])]
        #
        #     if global_var is None:
        #         global_var, = yield [("CN", [])]
        #         yield [("CD", [_globals, var_name, global_var])]
        #
        #     tmp = global_var

        task_root = retrieve_task_root()
        _globals = tree_ir.StoreLocalInstruction(
            '_globals',
            tree_ir.ReadDictionaryValueInstruction(
                task_root.create_load(),
                tree_ir.LiteralInstruction('globals')))

        global_var = tree_ir.StoreLocalInstruction(
            'global_var',
            tree_ir.ReadDictionaryValueInstruction(
                _globals.create_load(),
                tree_ir.LiteralInstruction(instruction.variable.name)))

        raise primitive_functions.PrimitiveFinished(
            tree_ir.CompoundInstruction(
                tree_ir.create_block(
                    task_root,
                    _globals,
                    global_var,
                    tree_ir.SelectInstruction(
                        tree_ir.BinaryInstruction(
                            global_var.create_load(),
                            'is',
                            tree_ir.LiteralInstruction(None)),
                        tree_ir.create_block(
                            global_var.create_store(
                                tree_ir.CreateNodeInstruction()),
                            tree_ir.CreateDictionaryEdgeInstruction(
                                _globals.create_load(),
                                tree_ir.LiteralInstruction(
                                    instruction.variable.name),
                                global_var.create_load())),
                        tree_ir.EmptyInstruction())),
                global_var.create_load()))

    def analyze_assign(self, instruction):
        """Tries to analyze the given 'assign' instruction."""
        (var_r, value_r), = yield [
            ("CALL_ARGS", [self.analyze_all, ([instruction.pointer, instruction.value],)])]

        raise primitive_functions.PrimitiveFinished(create_assign(var_r, value_r))

    def analyze_access(self, instruction):
        """Tries to analyze the given 'access' instruction."""
        var_r, = yield [("CALL_ARGS", [self.analyze, (instruction.pointer,)])]
        raise primitive_functions.PrimitiveFinished(create_access(var_r))

    def analyze_direct_call(self, callee_id, callee_name, argument_list):
        """Tries to analyze a direct 'call' instruction."""
        body_id, = yield [("RD", [callee_id, jit_runtime.FUNCTION_BODY_KEY])]

        # Make this function dependent on the callee.
        if body_id in self.jit.compilation_dependencies:
            self.jit.compilation_dependencies[body_id].add(self.body_id)

        # Figure out if the function might be an intrinsic.
        intrinsic = self.jit.get_intrinsic(callee_name)

        if intrinsic is None:
            if callee_name is not None:
                self.jit.register_global(body_id, callee_name)
                compiled_func = self.jit.lookup_compiled_function(callee_name)
            else:
                compiled_func = None

            if compiled_func is None:
                # Compile the callee.
                yield [
                    ("CALL_ARGS", [self.jit.jit_compile, (self.task_root, body_id, callee_name)])]

            # Get the callee's name.
            compiled_func_name = self.jit.get_compiled_name(body_id)

            # This handles the corner case where a constant node is called, like
            # 'call(constant(9), ...)'. In this case, `callee_name` is `None`
            # because 'constant(9)' doesn't give us a name. However, we can look up
            # the name of the function at a specific node. If that turns out to be
            # an intrinsic, then we still want to pick the intrinsic over a call.
            intrinsic = self.jit.get_intrinsic(compiled_func_name)

        # Analyze the argument dictionary.
        named_args, = yield [("CALL_ARGS", [self.analyze_arguments, (argument_list,)])]

        if intrinsic is not None:
            raise primitive_functions.PrimitiveFinished(
                apply_intrinsic(intrinsic, named_args))
        else:
            raise primitive_functions.PrimitiveFinished(
                tree_ir.create_jit_call(
                    tree_ir.LoadGlobalInstruction(compiled_func_name),
                    named_args,
                    tree_ir.LoadLocalInstruction(jit_runtime.KWARGS_PARAMETER_NAME)))

    def analyze_arguments(self, argument_list):
        """Analyzes the given parameter-to-value mapping."""
        named_args = []
        for param_name, arg in argument_list:
            param_val, = yield [("CALL_ARGS", [self.analyze, (arg,)])]
            named_args.append((param_name, param_val))

        raise primitive_functions.PrimitiveFinished(named_args)

    def analyze_indirect_call(self, target, argument_list):
        """Analyzes a call to an unknown function."""
        # First off, let's analyze the callee and the argument list.
        func_val, = yield [("CALL_ARGS", [self.analyze, (target,)])]
        named_args, = yield [("CALL_ARGS", [self.analyze_arguments, (argument_list,)])]
        func_val = tree_ir.StoreLocalInstruction(None, func_val)
        raise primitive_functions.PrimitiveFinished(
            tree_ir.create_block(
                func_val,
                create_indirect_call(func_val.create_load(), named_args)))

    def try_analyze_direct_call(self, target, argument_list):
        """Tries to analyze the given 'call' instruction as a direct call."""
        if not self.jit.direct_calls_allowed:
            raise jit_runtime.JitCompilationFailedException(
                'Direct calls are not allowed by the JIT.')

        # Figure out what the 'func' instruction's type is.
        if isinstance(target, bytecode_ir.AccessInstruction):
            # 'access(resolve(var))' instructions are translated to direct calls.
            if isinstance(target.pointer, bytecode_ir.ResolveInstruction):
                self.register_function_var(target.pointer.variable.node_id)
                resolved_var_name = target.pointer.variable.name

                if self.jit.thunks_enabled:
                    # Analyze the argument dictionary.
                    named_args, = yield [("CALL_ARGS", [self.analyze_arguments, (argument_list,)])]

                    # Try to resolve the callee as an intrinsic.
                    intrinsic = self.jit.get_intrinsic(resolved_var_name)
                    if intrinsic is not None:
                        raise primitive_functions.PrimitiveFinished(
                            apply_intrinsic(intrinsic, named_args))

                    # Otherwise, build a thunk.
                    thunk_name = self.jit.jit_thunk_global(target.pointer.variable.name)
                    raise primitive_functions.PrimitiveFinished(
                        tree_ir.create_jit_call(
                            tree_ir.LoadGlobalInstruction(thunk_name),
                            named_args,
                            tree_ir.LoadLocalInstruction(jit_runtime.KWARGS_PARAMETER_NAME)))
                else:
                    # Try to look up the name as a global.
                    _globals, = yield [("RD", [self.task_root, "globals"])]
                    global_var, = yield [("RD", [_globals, resolved_var_name])]
                    global_val, = yield [("RD", [global_var, "value"])]

                    if global_val is not None:
                        result, = yield [("CALL_ARGS", [self.analyze_direct_call, (
                            global_val, resolved_var_name, argument_list)])]
                        raise primitive_functions.PrimitiveFinished(result)
        elif isinstance(target, bytecode_ir.ConstantInstruction):
            # 'const(func_id)' instructions are also translated to direct calls.
            result, = yield [("CALL_ARGS", [self.analyze_direct_call, (
                target.constant_id, None, argument_list)])]
            raise primitive_functions.PrimitiveFinished(result)

        raise jit_runtime.JitCompilationFailedException(
            "Cannot JIT function calls that target an unknown value as direct calls.")

    def analyze_call(self, instruction):
        """Tries to analyze the given 'call' instruction."""
        def handle_exception(_):
            # Looks like we'll have to compile it as an indirect call.
            gen = self.analyze_indirect_call(instruction.target, instruction.argument_list)
            result, = yield [("CALL", [gen])]
            raise primitive_functions.PrimitiveFinished(result)

        # Try to analyze the call as a direct call.
        yield [("TRY", [])]
        yield [("CATCH", [jit_runtime.JitCompilationFailedException, handle_exception])]
        result, = yield [
            ("CALL_ARGS",
             [self.try_analyze_direct_call, (instruction.target, instruction.argument_list)])]
        yield [("END_TRY", [])]
        raise primitive_functions.PrimitiveFinished(result)

    def analyze_break(self, instruction):
        """Tries to analyze the given 'break' instruction."""
        if instruction.loop == self.enclosing_loop_instruction:
            raise primitive_functions.PrimitiveFinished(tree_ir.BreakInstruction())
        else:
            raise jit_runtime.JitCompilationFailedException(
                "Multilevel 'break' is not supported by the baseline JIT.")

    def analyze_continue(self, instruction):
        """Tries to analyze the given 'continue' instruction."""
        if instruction.loop == self.enclosing_loop_instruction:
            raise primitive_functions.PrimitiveFinished(tree_ir.ContinueInstruction())
        else:
            raise jit_runtime.JitCompilationFailedException(
                "Multilevel 'continue' is not supported by the baseline JIT.")

    instruction_analyzers = {
        bytecode_ir.SelectInstruction : analyze_if,
        bytecode_ir.WhileInstruction : analyze_while,
        bytecode_ir.ReturnInstruction : analyze_return,
        bytecode_ir.ConstantInstruction : analyze_constant,
        bytecode_ir.ResolveInstruction : analyze_resolve,
        bytecode_ir.DeclareInstruction : analyze_declare,
        bytecode_ir.GlobalInstruction : analyze_global,
        bytecode_ir.AssignInstruction : analyze_assign,
        bytecode_ir.AccessInstruction : analyze_access,
        bytecode_ir.OutputInstruction : analyze_output,
        bytecode_ir.InputInstruction : analyze_input,
        bytecode_ir.CallInstruction : analyze_call,
        bytecode_ir.BreakInstruction : analyze_break,
        bytecode_ir.ContinueInstruction : analyze_continue
    }