Subversion Repositories tcp_socket

__author__ = "Jon Dawson"

__copyright__ = "Copyright (C) 2012, Jonathan P Dawson"

__version__ = "0.1"

def cleanup_functions(instructions):

    """Remove functions that are not called"""

    #This is an iterative processr. Once a function is removed,

    #there may be more unused functions

    while 1:

        #find function calls

        live_functions = {}

        for instruction in instructions:

            if instruction["op"] == "jmp_and_link":

                if instruction["label"].startswith("function"):

                    live_functions[instruction["label"]] = None

        #remove instructions without function calls

        kept_instructions = []

        generate_on = True

        for instruction in instructions:

            if instruction["op"] == "label":

                if instruction["label"].startswith("function"):

                    if instruction["label"] in live_functions:

                        generate_on = True

                    else:

                        generate_on = False

            if generate_on:

                kept_instructions.append(instruction)

        if len(instructions) == len(kept_instructions):

            return kept_instructions

        instructions = kept_instructions

def reallocate_registers(instructions, registers):

    register_map = {}

    new_registers = {}

    n = 0

    for register, definition in registers.iteritems():

        register_map[register] = n

        new_registers[n] = definition

        n+=1

    for instruction in instructions:

        if "dest" in instruction:

            instruction["dest"] = register_map[instruction["dest"]]

        if "src" in instruction:

            instruction["src"] = register_map[instruction["src"]]

        if "srcb" in instruction:

            instruction["srcb"] = register_map[instruction["srcb"]]

    return instructions, new_registers

def cleanup_registers(instructions, registers):

    #find all the registers that are read from.

    used_registers = {}

    for instruction in instructions:

        if "src" in instruction:

            used_registers[instruction["src"]] = None

        if "srcb" in instruction:

            used_registers[instruction["srcb"]] = None

    #remove them from the list of allocated registers

    kept_registers = {}

    for register, description in registers.iteritems():

        if register in used_registers:

            kept_registers[register] = description

    #remove all instructions that read from unused registers

    kept_instructions = []

    for instruction in instructions:

        if "dest" in instruction:

            if instruction["dest"] in kept_registers:

                kept_instructions.append(instruction)

        else:

            kept_instructions.append(instruction)

    return reallocate_registers(kept_instructions, kept_registers)

def parallelise(instructions):

    def modifies_register(instruction):

        """Return the register modified by this instruction if any"""

        if "dest" in instruction:

            return instruction["dest"]

        return None

    def uses_registers(instruction):

        """Return the registers used by this instruction if any"""

        registers = []

        for field in ["src", "srcb"]:

            if field in instruction:

                registers.append(instruction[field])

        return registers

    def memory_clash(a, b):

        """do instructions result in a memory clash"""

        if a["op"] in ["memory_write", "memory_write_literal"]:

            return b["op"] in ["memory_write", "memory_write_literal", "memory_read", "memory_read_wait", "memory_read_request"]

        if b["op"] in ["memory_write", "memory_write_literal"]:

            return a["op"] in ["memory_write", "memory_write_literal", "memory_read", "memory_read_wait", "memory_read_request"]

        if a["op"] in ["memory_read", "memory_read_wait", "memory_read_request", "memory_write", "memory_write_literal"]:

            return b["op"] == a["op"]

        if b["op"] in ["memory_read", "memory_read_wait", "memory_read_request", "memory_write", "memory_write_literal"]:

            return b["op"] == a["op"]

    def is_part_of_read(a, b):

        """requests, waits and reads with the same sequence number must not be concurrent"""

        read_instructions = ["memory_read_request", "memory_read_wait", "memory_read"]

        if (a["op"] in read_instructions) and (b["op"] in read_instructions):

            return a["sequence"] == b["sequence"]

        return False

    def is_solitary(instruction):

        """Return True if an instruction cannot be executed in parallel with other instructions"""

        if "type" in instruction and instruction["type"] == "float":

            if instruction["op"] in ["+", "-", "/", "*"]:

                return True

        return instruction["op"] in ["read", "write", "ready", "label", "/", "%", "int_to_float", "float_to_int", "file_write", "file_read"]

    def is_jump(instruction):

        """Return True if an instruction contains a branch or jump"""

        return instruction["op"] in ["goto", "jmp_if_true", "jmp_if_false", "jmp_and_link",

                                     "jmp_to_reg"]

    def is_dependent(instruction, frame, preceding):

        """determine whether an instruction is dependent on the outcome of:

        - an instruction within the current frame

        - preceding instructions not within the frame """

        for i in frame + preceding:

            if modifies_register(i) is not None:

                if modifies_register(i) in uses_registers(instruction):

                    return True

                if modifies_register(i) == modifies_register(instruction):

                    return True

            if memory_clash(i, instruction):

                return True

            if is_part_of_read(i, instruction):

                return True

            if is_jump(i):

                return True

        for i in preceding:

            if modifies_register(instruction) is not None:

                if modifies_register(instruction) in uses_registers(i):

                    return True

            if memory_clash(i, instruction):

                return True

            if is_part_of_read(i, instruction):

                return True

        if is_jump(instruction) and preceding:

            return True

        return False

    def add_instructions(frame, instructions):

        """Add more instructions to the current frame if dependencies allow."""

        instructions_added = True

        while instructions_added:

            instructions_added = False

            for index, instruction in enumerate(instructions):

                if is_solitary(instruction):

                    return

                for i in frame:

                    if is_jump(i):

                        return

                    if is_solitary(i):

                        return

                if not is_dependent(instruction, frame, instructions[:index]):

                    frame.append(instructions.pop(index))

                    instructions_added = True

                    break

    frames = []

    while instructions:

        frame = [instructions.pop(0)]

        add_instructions(frame, instructions)

        frames.append(frame)

    return frames