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"""

    return instruction["op"] in ["read", "write", "ready", "label", "/", "%"]

  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