modelverse/kernel/modelverse_jit/bytecode_to_cfg.py

"""Converts bytecode IR to CFG IR."""

import modelverse_jit.bytecode_ir as bytecode_ir
import modelverse_jit.cfg_ir as cfg_ir
import modelverse_jit.runtime as jit_runtime

class AnalysisState(object):
    """State that is common to the bytecode->CFG transformation of a function."""
    def __init__(self, param_dict):
        self.counter = cfg_ir.SharedCounter()
        self.analyzed_instructions = set()
        self.loop_instructions = {}
        self.entry_point = cfg_ir.BasicBlock(self.counter)
        self.current_block = self.entry_point
        self.root_node = None
        self.__write_prolog(param_dict)

    def __write_prolog(self, param_dict):
        # Write a prolog in CFG IR.
        # We want to create the following definition:
        #
        #     !entry_point():
        #         $jit_locals = alloc-root-node
        #         $_ = declare-local var(...)
        #         $param_1 = resolve-local var(...)
        #         $arg_1 = function-parameter ...
        #         $_ = store $param_1, $arg_1
        #         ...
        #
        # We also want to store '$jit_locals' in an attribute, so we can
        # use it to shield locals from the GC.
        self.root_node = self.current_block.append_definition(cfg_ir.AllocateRootNode())
        for node_id, name in param_dict.items():
            variable = bytecode_ir.VariableNode(node_id, name)
            self.current_block.append_definition(cfg_ir.DeclareLocal(variable, self.root_node))
            param_i = self.current_block.append_definition(cfg_ir.ResolveLocal(variable))
            arg_i = self.current_block.append_definition(cfg_ir.FunctionParameter(name))
            self.current_block.append_definition(cfg_ir.StoreAtPointer(param_i, arg_i))

    def analyze(self, instruction):
        """Analyzes the given instruction as a basic block."""
        if instruction in self.analyzed_instructions:
            raise jit_runtime.JitCompilationFailedException(
                'Cannot jit non-tree instruction graph.')

        self.analyzed_instructions.add(instruction)

        # Find an analyzer.
        instruction_type = type(instruction)
        if instruction_type in self.instruction_analyzers:
            # Analyze the instruction.
            result = self.instruction_analyzers[instruction_type](self, instruction)

            # Check if the instruction has a 'next' instruction. If so, analyze it!
            if instruction.next_instruction is not None:
                next_result = self.analyze(instruction.next_instruction)
                if next_result.value.has_value() or (not result.value.has_value()):
                    result = next_result

            return result
        else:
            raise jit_runtime.JitCompilationFailedException(
                "Unknown instruction type: '%s'" % type(instruction))

    def emit_select(self, create_condition, create_if_body, create_else_body):
        """Emits a 'select' instruction."""
        # Create blocks that look like this:
        #
        # !current_block(...):
        #     ...
        #     $cond = <condition>
        #     select $cond, !if_block(), !else_block()
        #
        # !if_block():
        #     $if_result = <if-body>
        #     jump !phi_block($if_result)
        #
        # !else_block():
        #     $else_result = <else-body>
        #     jump !phi_block($else_result)
        #
        # !phi_block($result = block-parameter):
        #     ...
        #
        if_block = cfg_ir.BasicBlock(self.counter)
        else_block = cfg_ir.BasicBlock(self.counter)
        phi_block = cfg_ir.BasicBlock(self.counter)
        param_def = phi_block.append_parameter(cfg_ir.BlockParameter())

        condition = create_condition()
        self.current_block.flow = cfg_ir.SelectFlow(
            condition, cfg_ir.Branch(if_block), cfg_ir.Branch(else_block))

        self.current_block = if_block
        if_result = create_if_body()
        self.current_block.flow = cfg_ir.create_jump(phi_block, [if_result])

        self.current_block = else_block
        else_result = create_else_body()
        self.current_block.flow = cfg_ir.create_jump(phi_block, [else_result])

        self.current_block = phi_block
        return param_def

    def analyze_if(self, instruction):
        """Analyzes an 'if' instruction."""
        def __analyze_condition():
            condition_node = self.analyze(instruction.condition)
            return self.current_block.append_definition(cfg_ir.Read(condition_node))
        return self.emit_select(
            __analyze_condition,
            lambda: self.analyze(instruction.if_clause),
            lambda:
            self.current_block.append_definition(cfg_ir.Literal(None))
            if instruction.else_clause is None
            else self.analyze(instruction.else_clause))

    def analyze_while(self, instruction):
        """Analyzes a 'while' instruction."""
        # Create blocks that look like this:
        #
        # !current_block(...):
        #     ...
        #     jump !loop_condition()
        #
        # !loop_condition():
        #     $condition_node = <condition>
        #     $condition = read condition_node
        #     select $condition, !loop_body(), !loop_exit()
        #
        # !loop_body():
        #     $result = <body>
        #     jump !loop_condition()
        #
        # !loop_exit():
        #     $nothing = literal None
        #     ...
        loop_condition_block = cfg_ir.BasicBlock(self.counter)
        loop_body_block = cfg_ir.BasicBlock(self.counter)
        loop_exit_block = cfg_ir.BasicBlock(self.counter)
        self.loop_instructions[instruction] = (loop_condition_block, loop_exit_block)

        self.current_block.flow = cfg_ir.create_jump(loop_condition_block)

        self.current_block = loop_condition_block
        condition_node = self.analyze(instruction.condition)
        condition = self.current_block.append_definition(cfg_ir.Read(condition_node))
        self.current_block.flow = cfg_ir.SelectFlow(
            condition, cfg_ir.Branch(loop_body_block), cfg_ir.Branch(loop_exit_block))

        self.current_block = loop_body_block
        self.analyze(instruction.body)
        self.current_block.flow = cfg_ir.create_jump(loop_condition_block)

        self.current_block = loop_exit_block
        return loop_exit_block.append_definition(cfg_ir.Literal(None))

    def analyze_return(self, instruction):
        """Analyzes a 'return' instruction."""
        if instruction.value is None:
            return_value = self.current_block.append_definition(cfg_ir.Literal(None))
        else:
            return_value = self.analyze(instruction.value)
        # Don't forget to deallocate the root node.
        self.current_block.append_definition(cfg_ir.DeallocateRootNode(self.root_node))
        self.current_block.flow = cfg_ir.ReturnFlow(return_value)
        self.current_block = cfg_ir.BasicBlock(self.counter)
        return self.current_block.append_definition(cfg_ir.Literal(None))

    def analyze_constant(self, instruction):
        """Analyzes a 'constant' instruction."""
        return self.current_block.append_definition(cfg_ir.Literal(instruction.constant_id))

    def analyze_resolve(self, instruction):
        """Analyzes a 'resolve' instruction."""
        def __resolve_global_carefully():
            # We might be resolving a global that does not exist. In that case, we
            # need to throw. We want to create the following blocks:
            #
            # !current_block(...):
            #     ...
            #     $resolved_global = resolve-global global
            #     $nothing = literal None
            #     $condition = binary $resolved_global, 'is', $nothing
            #     select $condition, !no_global_block(), !global_exists_block()
            #
            # !no_global_block():
            #     $message = literal <GLOBAL_NOT_FOUND_MESSAGE_FORMAT % instruction.variable.name>
            #     $exception = direct-call "simple-positional" Exception(message=$message)
            #     throw $exception
            #
            # !global_exists_block():
            #     ...
            #
            no_global_block = cfg_ir.BasicBlock(self.counter)
            global_exists_block = cfg_ir.BasicBlock(self.counter)

            resolved_global = self.current_block.append_definition(
                cfg_ir.ResolveGlobal(instruction.variable))
            nothing = self.current_block.append_definition(cfg_ir.Literal(None))
            condition = self.current_block.append_definition(
                cfg_ir.Binary(resolved_global, 'is', nothing))
            self.current_block.flow = cfg_ir.SelectFlow(
                condition, cfg_ir.Branch(no_global_block), cfg_ir.Branch(global_exists_block))

            message = no_global_block.append_definition(
                cfg_ir.Literal(
                    jit_runtime.GLOBAL_NOT_FOUND_MESSAGE_FORMAT % instruction.variable.name))
            exception = no_global_block.append_definition(
                cfg_ir.DirectFunctionCall(
                    'Exception',
                    [('message', message)],
                    cfg_ir.SIMPLE_POSITIONAL_CALLING_CONVENTION))
            no_global_block.flow = cfg_ir.ThrowFlow(exception)

            self.current_block = global_exists_block
            return resolved_global
        return self.emit_select(
            lambda:
            self.current_block.append_definition(
                cfg_ir.CheckLocalExists(instruction.variable)),
            lambda:
            self.current_block.append_definition(
                cfg_ir.ResolveLocal(instruction.variable)),
            __resolve_global_carefully)

    def analyze_declare(self, instruction):
        """Analyzes a 'declare' instruction."""
        return self.current_block.append_definition(
            cfg_ir.DeclareLocal(instruction.variable, self.root_node))

    def analyze_global(self, instruction):
        """Analyzes a 'global' instruction."""
        resolved_global = self.current_block.append_definition(
            cfg_ir.ResolveGlobal(instruction.variable))
        nothing = self.current_block.append_definition(cfg_ir.Literal(None))
        return self.emit_select(
            lambda:
            self.current_block.append_definition(
                cfg_ir.Binary(resolved_global, 'is', nothing)),
            lambda:
            self.current_block.append_definition(
                cfg_ir.DeclareGlobal(instruction.variable)),
            lambda: resolved_global)

    def analyze_assign(self, instruction):
        """Analyzes an 'assign' instruction."""
        pointer_result = self.analyze(instruction.pointer)
        value_result = self.analyze(instruction.value)
        return self.current_block.append_definition(
            cfg_ir.StoreAtPointer(pointer_result, value_result))

    def analyze_access(self, instruction):
        """Analyzes an 'access' instruction."""
        pointer_result = self.analyze(instruction.pointer)
        return self.current_block.append_definition(cfg_ir.LoadPointer(pointer_result))

    def analyze_output(self, instruction):
        """Analyzes an 'output' instruction."""
        value_result = self.analyze(instruction.value)
        return self.current_block.append_definition(cfg_ir.Output(value_result))

    def analyze_input(self, _):
        """Analyzes an 'input' instruction."""
        return self.current_block.append_definition(cfg_ir.Input())

    def analyze_break(self, instruction):
        """Analyzes a 'break' instruction."""
        if instruction.loop not in self.loop_instructions:
            raise jit_runtime.JitCompilationFailedException(
                "'break' instruction targets a 'while' loop that has not been defined yet.")

        _, exit_block = self.loop_instructions[instruction.loop]
        self.current_block.flow = cfg_ir.create_jump(exit_block)
        self.current_block = cfg_ir.BasicBlock(self.counter)
        return self.current_block.append_definition(cfg_ir.Literal(None))

    def analyze_continue(self, instruction):
        """Analyzes a 'continue' instruction."""
        if instruction.loop not in self.loop_instructions:
            raise jit_runtime.JitCompilationFailedException(
                "'continue' instruction targets a 'while' loop that has not been defined yet.")

        cond_block, _ = self.loop_instructions[instruction.loop]
        self.current_block.flow = cfg_ir.create_jump(cond_block)
        self.current_block = cfg_ir.BasicBlock(self.counter)
        return self.current_block.append_definition(cfg_ir.Literal(None))

    def analyze_call(self, instruction):
        """Analyzes the given 'call' instruction."""
        target = self.analyze(instruction.target)
        arg_list = []
        for key, arg_instruction in instruction.argument_list:
            arg_list.append((key, self.analyze(arg_instruction)))

        return self.current_block.append_definition(cfg_ir.IndirectFunctionCall(target, arg_list))

    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
    }