__author__ = "Jon Dawson"
|
__author__ = "Jon Dawson"
|
__copyright__ = "Copyright (C) 2012, Jonathan P Dawson"
|
__copyright__ = "Copyright (C) 2012, Jonathan P Dawson"
|
__version__ = "0.1"
|
__version__ = "0.1"
|
|
|
def cleanup_functions(instructions):
|
def cleanup_functions(instructions):
|
|
|
"""Remove functions that are not called"""
|
"""Remove functions that are not called"""
|
|
|
|
|
#This is an iterative processr. Once a function is removed,
|
#This is an iterative processr. Once a function is removed,
|
#there may be more unused functions
|
#there may be more unused functions
|
while 1:
|
while 1:
|
|
|
#find function calls
|
#find function calls
|
live_functions = {}
|
live_functions = {}
|
for instruction in instructions:
|
for instruction in instructions:
|
if instruction["op"] == "jmp_and_link":
|
if instruction["op"] == "jmp_and_link":
|
if instruction["label"].startswith("function"):
|
if instruction["label"].startswith("function"):
|
live_functions[instruction["label"]] = None
|
live_functions[instruction["label"]] = None
|
|
|
#remove instructions without function calls
|
#remove instructions without function calls
|
kept_instructions = []
|
kept_instructions = []
|
generate_on = True
|
generate_on = True
|
for instruction in instructions:
|
for instruction in instructions:
|
if instruction["op"] == "label":
|
if instruction["op"] == "label":
|
if instruction["label"].startswith("function"):
|
if instruction["label"].startswith("function"):
|
if instruction["label"] in live_functions:
|
if instruction["label"] in live_functions:
|
generate_on = True
|
generate_on = True
|
else:
|
else:
|
generate_on = False
|
generate_on = False
|
if generate_on:
|
if generate_on:
|
kept_instructions.append(instruction)
|
kept_instructions.append(instruction)
|
|
|
if len(instructions) == len(kept_instructions):
|
if len(instructions) == len(kept_instructions):
|
return kept_instructions
|
return kept_instructions
|
instructions = kept_instructions
|
instructions = kept_instructions
|
|
|
def reallocate_registers(instructions, registers):
|
def reallocate_registers(instructions, registers):
|
|
|
register_map = {}
|
register_map = {}
|
new_registers = {}
|
new_registers = {}
|
n = 0
|
n = 0
|
for register, definition in registers.iteritems():
|
for register, definition in registers.iteritems():
|
register_map[register] = n
|
register_map[register] = n
|
new_registers[n] = definition
|
new_registers[n] = definition
|
n+=1
|
n+=1
|
|
|
for instruction in instructions:
|
for instruction in instructions:
|
if "dest" in instruction:
|
if "dest" in instruction:
|
instruction["dest"] = register_map[instruction["dest"]]
|
instruction["dest"] = register_map[instruction["dest"]]
|
if "src" in instruction:
|
if "src" in instruction:
|
instruction["src"] = register_map[instruction["src"]]
|
instruction["src"] = register_map[instruction["src"]]
|
if "srcb" in instruction:
|
if "srcb" in instruction:
|
instruction["srcb"] = register_map[instruction["srcb"]]
|
instruction["srcb"] = register_map[instruction["srcb"]]
|
|
|
return instructions, new_registers
|
return instructions, new_registers
|
|
|
def cleanup_registers(instructions, registers):
|
def cleanup_registers(instructions, registers):
|
|
|
#find all the registers that are read from.
|
#find all the registers that are read from.
|
used_registers = {}
|
used_registers = {}
|
for instruction in instructions:
|
for instruction in instructions:
|
if "src" in instruction:
|
if "src" in instruction:
|
used_registers[instruction["src"]] = None
|
used_registers[instruction["src"]] = None
|
if "srcb" in instruction:
|
if "srcb" in instruction:
|
used_registers[instruction["srcb"]] = None
|
used_registers[instruction["srcb"]] = None
|
|
|
#remove them from the list of allocated registers
|
#remove them from the list of allocated registers
|
kept_registers = {}
|
kept_registers = {}
|
for register, description in registers.iteritems():
|
for register, description in registers.iteritems():
|
if register in used_registers:
|
if register in used_registers:
|
kept_registers[register] = description
|
kept_registers[register] = description
|
|
|
#remove all instructions that read from unused registers
|
#remove all instructions that read from unused registers
|
kept_instructions = []
|
kept_instructions = []
|
for instruction in instructions:
|
for instruction in instructions:
|
if "dest" in instruction:
|
if "dest" in instruction:
|
if instruction["dest"] in kept_registers:
|
if instruction["dest"] in kept_registers:
|
kept_instructions.append(instruction)
|
kept_instructions.append(instruction)
|
else:
|
else:
|
kept_instructions.append(instruction)
|
kept_instructions.append(instruction)
|
|
|
return reallocate_registers(kept_instructions, kept_registers)
|
return reallocate_registers(kept_instructions, kept_registers)
|
|
|
def parallelise(instructions):
|
def parallelise(instructions):
|
|
|
def modifies_register(instruction):
|
def modifies_register(instruction):
|
|
|
"""Return the register modified by this instruction if any"""
|
"""Return the register modified by this instruction if any"""
|
|
|
if "dest" in instruction:
|
if "dest" in instruction:
|
return instruction["dest"]
|
return instruction["dest"]
|
return None
|
return None
|
|
|
def uses_registers(instruction):
|
def uses_registers(instruction):
|
|
|
"""Return the registers used by this instruction if any"""
|
"""Return the registers used by this instruction if any"""
|
|
|
registers = []
|
registers = []
|
for field in ["src", "srcb"]:
|
for field in ["src", "srcb"]:
|
if field in instruction:
|
if field in instruction:
|
registers.append(instruction[field])
|
registers.append(instruction[field])
|
return registers
|
return registers
|
|
|
def memory_clash(a, b):
|
def memory_clash(a, b):
|
|
|
"""do instructions result in a memory clash"""
|
"""do instructions result in a memory clash"""
|
|
|
if a["op"] in ["memory_write", "memory_write_literal"]:
|
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"]
|
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"]:
|
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"]
|
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"]:
|
if a["op"] in ["memory_read", "memory_read_wait", "memory_read_request", "memory_write", "memory_write_literal"]:
|
return b["op"] == a["op"]
|
return b["op"] == a["op"]
|
|
|
if b["op"] in ["memory_read", "memory_read_wait", "memory_read_request", "memory_write", "memory_write_literal"]:
|
if b["op"] in ["memory_read", "memory_read_wait", "memory_read_request", "memory_write", "memory_write_literal"]:
|
return b["op"] == a["op"]
|
return b["op"] == a["op"]
|
|
|
def is_part_of_read(a, b):
|
def is_part_of_read(a, b):
|
|
|
"""requests, waits and reads with the same sequence number must not be concurrent"""
|
"""requests, waits and reads with the same sequence number must not be concurrent"""
|
|
|
read_instructions = ["memory_read_request", "memory_read_wait", "memory_read"]
|
read_instructions = ["memory_read_request", "memory_read_wait", "memory_read"]
|
if (a["op"] in read_instructions) and (b["op"] in read_instructions):
|
if (a["op"] in read_instructions) and (b["op"] in read_instructions):
|
return a["sequence"] == b["sequence"]
|
return a["sequence"] == b["sequence"]
|
return False
|
return False
|
|
|
def is_solitary(instruction):
|
def is_solitary(instruction):
|
|
|
"""Return True if an instruction cannot be executed in parallel with other instructions"""
|
"""Return True if an instruction cannot be executed in parallel with other instructions"""
|
|
|
return instruction["op"] in ["read", "write", "ready", "label", "/", "%"]
|
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):
|
def is_jump(instruction):
|
|
|
"""Return True if an instruction contains a branch or jump"""
|
"""Return True if an instruction contains a branch or jump"""
|
|
|
return instruction["op"] in ["goto", "jmp_if_true", "jmp_if_false", "jmp_and_link",
|
return instruction["op"] in ["goto", "jmp_if_true", "jmp_if_false", "jmp_and_link",
|
"jmp_to_reg"]
|
"jmp_to_reg"]
|
|
|
def is_dependent(instruction, frame, preceding):
|
def is_dependent(instruction, frame, preceding):
|
|
|
"""determine whether an instruction is dependent on the outcome of:
|
"""determine whether an instruction is dependent on the outcome of:
|
- an instruction within the current frame
|
- an instruction within the current frame
|
- preceding instructions not within the frame """
|
- preceding instructions not within the frame """
|
|
|
for i in frame + preceding:
|
for i in frame + preceding:
|
if modifies_register(i) is not None:
|
if modifies_register(i) is not None:
|
if modifies_register(i) in uses_registers(instruction):
|
if modifies_register(i) in uses_registers(instruction):
|
return True
|
return True
|
if modifies_register(i) == modifies_register(instruction):
|
if modifies_register(i) == modifies_register(instruction):
|
return True
|
return True
|
if memory_clash(i, instruction):
|
if memory_clash(i, instruction):
|
return True
|
return True
|
if is_part_of_read(i, instruction):
|
if is_part_of_read(i, instruction):
|
return True
|
return True
|
if is_jump(i):
|
if is_jump(i):
|
return True
|
return True
|
for i in preceding:
|
for i in preceding:
|
if modifies_register(instruction) is not None:
|
if modifies_register(instruction) is not None:
|
if modifies_register(instruction) in uses_registers(i):
|
if modifies_register(instruction) in uses_registers(i):
|
return True
|
return True
|
if memory_clash(i, instruction):
|
if memory_clash(i, instruction):
|
return True
|
return True
|
if is_part_of_read(i, instruction):
|
if is_part_of_read(i, instruction):
|
return True
|
return True
|
if is_jump(instruction) and preceding:
|
if is_jump(instruction) and preceding:
|
return True
|
return True
|
return False
|
return False
|
|
|
def add_instructions(frame, instructions):
|
def add_instructions(frame, instructions):
|
|
|
"""Add more instructions to the current frame if dependencies allow."""
|
"""Add more instructions to the current frame if dependencies allow."""
|
|
|
instructions_added = True
|
instructions_added = True
|
while instructions_added:
|
while instructions_added:
|
instructions_added = False
|
instructions_added = False
|
for index, instruction in enumerate(instructions):
|
for index, instruction in enumerate(instructions):
|
if is_solitary(instruction):
|
if is_solitary(instruction):
|
return
|
return
|
for i in frame:
|
for i in frame:
|
if is_jump(i):
|
if is_jump(i):
|
return
|
return
|
if is_solitary(i):
|
if is_solitary(i):
|
return
|
return
|
if not is_dependent(instruction, frame, instructions[:index]):
|
if not is_dependent(instruction, frame, instructions[:index]):
|
frame.append(instructions.pop(index))
|
frame.append(instructions.pop(index))
|
instructions_added = True
|
instructions_added = True
|
break
|
break
|
|
|
frames = []
|
frames = []
|
while instructions:
|
while instructions:
|
frame = [instructions.pop(0)]
|
frame = [instructions.pop(0)]
|
add_instructions(frame, instructions)
|
add_instructions(frame, instructions)
|
frames.append(frame)
|
frames.append(frame)
|
|
|
return frames
|
return frames
|
|
|