From 20416d5ae946d4defbfea66c53e58761cf885b73 Mon Sep 17 00:00:00 2001 From: Peter Wu Date: Thu, 1 Dec 2011 18:28:36 +0000 Subject: WIP for func parameter support and local (automatic) variables --- Function.py | 12 ++++++++ LinkedNode.py | 9 ++++-- Registers.py | 5 +++- Variables.py | 91 ++++++++++++++++++++++++++++++++++++++++++++--------------- pp2cc.py | 75 +++++++++++++++++++++++++++++++++++------------- 5 files changed, 147 insertions(+), 45 deletions(-) diff --git a/Function.py b/Function.py index 6621fb8..de0c49d 100644 --- a/Function.py +++ b/Function.py @@ -22,9 +22,21 @@ class Function(object): def __init__(self, node): self.name = node.decl.name self.node = node + self.reserved_stack = 0 def labelBegin(self): """Returns a label pointing to the begin of a function""" return "fn_" + self.name def labelEnd(self): """Returns a label pointing to the end of a function""" return "fne_" + self.name + def allocStack(self, count=1): + """Reserve some memory (for local variables and params) on the stack + and return the begin of the allocated memory + + Keyword arguments: + count -- The number of words to be allocated which should be at least 1 + """ + assert count > 0, "The stack allocation count must be at least 1" + begin_address = self.reserved_stack + 1 + self.reserved_stack += count + return begin_address diff --git a/LinkedNode.py b/LinkedNode.py index 864f708..88bc6da 100644 --- a/LinkedNode.py +++ b/LinkedNode.py @@ -59,7 +59,12 @@ class LinkedNode(object): # the node appears to have an own variable scope if defined_names is None: raise RuntimeError("No object found for storing variables") - self.variables = Variables(defined_names, parent_variables) + # pass function object for local variables allocation + function = self.getFunctionNode() + if function: + function = function.function + self.variables = Variables(parent_variables, defined_names, + function=function) # Identifiers which are in use (think of variables and labels) self.defined_names = defined_names if not self.variables: @@ -93,7 +98,7 @@ class LinkedNode(object): "Enum", # enum type "Enumerator", # enum value "EnumeratorList", # list of enum values - "FuncDecl", "Goto", "Label", "ParamList", "PtrDecl", "Struct", + "Goto", "Label", "ParamList", "PtrDecl", "Struct", "TypeDecl", "Typedef", "Union") def getStatementNode(self): """Returns the nearest LinkedNode which is a statement node type""" diff --git a/Registers.py b/Registers.py index 2a070d4..1d080f1 100644 --- a/Registers.py +++ b/Registers.py @@ -31,6 +31,9 @@ class Registers(object): self.registers = {} for reg in range(0, 8): self.registers[str(reg)] = False + # the "Base Pointer", local variables are relative to this address. The + # value of this register points to a location in the stack + self.BP = "R5" def alloc(self, register=None): """Retrieves a register which is marked unused, marks it as in use and return it""" @@ -42,7 +45,7 @@ class Registers(object): if self.registers[register]: raise RuntimeError("Register 'R{}' is already in use".format(register)) else: - for register in range(0, 6): + for register in range(0, 5): register = str(register) # find a free register if not self.registers[register]: diff --git a/Variables.py b/Variables.py index 1d37f0f..338cfdf 100644 --- a/Variables.py +++ b/Variables.py @@ -19,42 +19,89 @@ __maintainer__ = "Peter Wu" __email__ = "uwretep@gmail.com" class Variables(object): - def __init__(self, defined_names, parent_variables): + def __init__(self, parent_variables, defined_names, function=None): """A scope for holding variable names Keywords arguments: - defined_names -- A list of defined variables to which additional - variables might be appended parent_variables -- the parent Variables object. If None, it's a global variable scope + defined_names -- A list of defined variables to which additional + variables might be appended + function -- The function object used for allocating memory. If not set, + the variables object will ask the parent_variables object for it """ - self.local_vars = {} - self.defined_names = defined_names self.parent_variables = parent_variables + self.function = function + # if there is a parent_variables object, it must be a function + if self.parent_variables: + # key: name, value: address n relative to BP (n >= 1) + self.local_vars = {} + self.param_vars = [] + if not self.function: + self.function = self.parent_variables.function + else: + # key: name of var, value: label of var + self.global_vars = {} + self.defined_names = defined_names def uniqName(self, name): - """Returns an unique variable name""" + """Returns an unique global variable name for assembly""" uniq_name = name i = 0 while uniq_name in self.defined_names: uniq_name = name + "_" + str(i) i += 1 return uniq_name - def getName(self, name): - """Gets the name of a declared variable as it appears in the @DATA - section""" - if name in self.local_vars: - return self.local_vars[name] + def getAddress(self, name): + """Gets the address for a variable as a tuple containing a register and + displacement + + To get the address of the variable, add the register value and + displacement + """ + # first try the local scope + if self.function: + if name in self.local_vars: + # XXX don't hardcode R5 + return ("R5", str(self.local_vars[name])) + try: + return ("R5", str(-self.param_vars.index(name))) + except ValueError: + pass + else: + # lookup in global vars + if name in self.global_vars: + return ("GB", self.global_vars[name]) + # lookup in the parent if self.parent_variables: - return self.parent_variables.getName(name) + return self.parent_variables.getAddress(name) raise RuntimeError("Use of undefined variable '{}'".format(name)) - def declName(self, name, size=1, prefix="var"): - """Declares a variable in the nearest scope and returns the label - name""" - if name in self.local_vars: + def declName(self, name, size=1, is_param=False): + """Declares a variable in the nearest scope + + Keyword arguments: + name -- The symbolic name of the variable + size -- The size of the memory to be allocated in words (default 1) + is_param -- Whether the name is a function parameter or not + """ + already_defined = False + if self.function: + already_defined = name in self.local_vars or name in self.param_vars + else: + already_defined = name in self.global_vars + if already_defined: raise RuntimeError("Redeclaration of variable '{}'".format(name)) - # global variables are prefixed "var_", locals with "varl_" - var_name = prefix + ("l_" if self.parent_variables else "_") + name - var_name = self.uniqName(var_name) - self.local_vars[name] = var_name - self.defined_names[var_name] = size - return var_name + + if self.function: + # parameters do not need a special allocation because the callee + # pushes it into the stack + if is_param: + self.param_vars.append(name) + else: + self.local_vars[name] = self.function.allocStack(size) + elif is_param: + raise RuntimeError("Parameter '{}' declared in global context".format(name)) + else: + # global variables are prefixed "var_" + var_name = "var_" + name + self.global_vars[name] = var_name + self.defined_names[var_name] = size diff --git a/pp2cc.py b/pp2cc.py index 15d451a..5a079c8 100755 --- a/pp2cc.py +++ b/pp2cc.py @@ -155,16 +155,20 @@ class Parse(object): self.addLabel(lbl_end) linked_node.setFunction(function) - lines = [self.asm.noop(lbl_func)] + # save Base Pointer + lines = [self.asm.push(self.registers.BP, lbl_func)] + lines.append(self.asm.binary_op("LOAD", self.registers.BP, "SP")) + # parse function declaration (which will parse params as well) + lines += self.parseStatement(node.decl, linked_node) lines += self.parseStatement(node.body, linked_node) self.asm.level = linked_node.level - - # functions other than main() are subroutines - #if funcname != "main": - # since main should never be left, add the instruction anyway. - # Otherwise, it'd crash anyway because it loops into the stack (if it - # had not crashed before) + + # restore stack pointer + lines.append(self.asm.binary_op("LOAD", "SP", self.registers.BP)) + # restore Base Pointer + lines.append(self.asm.pull(self.registers.BP)) + # return from function lines.append(self.asm.format_line("RTS", label=lbl_end)) # add an extra newline lines.append("") @@ -580,8 +584,8 @@ class Parse(object): def parseID(self, linked_node, register="R0"): """Returns the name for a name""" # XXX this is not made for functions - var_name = linked_node.variables.getName(linked_node.node.name) - return [self.asm.binary_op("LOAD", register, "[GB+" + var_name + "]")] + addr = "+".join(linked_node.variables.getAddress(linked_node.node.name)) + return [self.asm.binary_op("LOAD", register, "[" + addr + "]")] def parseIf(self, linked_node): linked_node.incrementLevel() node = linked_node.node @@ -836,9 +840,9 @@ class Parse(object): lines.append(self.asm.binary_op("LOAD", register, "[" + register + "]")) elif linked_node.type == "ID": - var_name = linked_node.variables.getName(linked_node.node.name) - lines.append(self.asm.binary_op("LOAD", register, "GB")) - lines.append(self.asm.binary_op("ADD", register, var_name)) + var_reg, var_disp = linked_node.variables.getAddress(linked_node.node.name) + lines.append(self.asm.binary_op("LOAD", register, var_reg)) + lines.append(self.asm.binary_op("ADD", register, var_disp)) else: raise RuntimeError("Expected a lvalue (pointer or names)") return lines @@ -846,7 +850,7 @@ class Parse(object): lines = [] size = 1 linked_type = LinkedNode(linked_node.node.type, linked_node) - var_name = linked_node.variables.declName(linked_node.node.name, 1) + name = linked_node.node.name if linked_type.type == "ArrayDecl": if linked_type.node.dim is not None: size = self.determineConstValue(LinkedNode(linked_type.node.dim, @@ -865,15 +869,23 @@ class Parse(object): # it's an error if the array dimension is unavailable, e.g.: # int a[]; if size is None: - raise RuntimeError("Array size missing in '{}'".format(var_name)) - var_array = linked_node.variables.declName(var_name, size, - prefix="arr") + raise RuntimeError("Array size missing in '{}'".format(name)) elif linked_type.type == "PtrDecl": # no check whether the pointer is valid or not pass elif linked_type.type == "TypeDecl": if not linked_type.node.type.names[0] in ("int", "void"): self.logger.warning("Only void and int types are supported", linked_node) + elif linked_type.type == "FuncDecl": + # a function declaration does not accept an initializaer, but it's + # still special because it has params + return self.parseStatement(linked_type.node, linked_node) + else: + raise RuntimeError("Unknown declaration type '{}'".format(linked_type.type)) + + linked_node.variables.declName(name, size) + # address of variable split up in register and displacement + var_reg, var_disp = linked_node.variables.getAddress(name) # if the declaration also has a definition if linked_node.node.init: @@ -885,10 +897,15 @@ class Parse(object): # contains the address of the first array element reg_array = "R1" # store the address of the first array element in the pointer - init_vals.append(self.asm.binary_op("LOAD", reg_array, "GB")) - init_vals.append(self.asm.binary_op("ADD", reg_array, var_array)) + init_vals.append(self.asm.binary_op("LOAD", reg_array, var_reg)) + init_vals.append(self.asm.binary_op("ADD", reg_array, var_arr)) + # in this particular case, it happens that the array values are + # next to the pointer to the array + init_vals.append(self.asm.binary_op("ADD", reg_array, 1)) + # store address of the first array element in the array pointer init_vals.append(self.asm.binary_op("STOR", reg_array, - "[GB+" + var_name + "]")) + "[" + var_reg + "+" + + var_disp + "]")) array_index = 0 for array_elm in linked_init.node.exprs: linked_arrelm = LinkedNode(array_elm, linked_init) @@ -912,7 +929,8 @@ class Parse(object): linked_node) result_reg = self.registers.find_register(init_vals) init_vals.append(self.asm.binary_op("STOR", result_reg, - "[GB+" + var_name + "]")) + "[" + var_reg + "+" + + var_disp + "]")) # if global context (i.e. not in a function) if linked_node.getFunctionNode() is None: @@ -1023,6 +1041,23 @@ class Parse(object): """ label_name = linked_node.lookupLabel(linked_node.node.name) return [self.asm.branch_op("BRA", label_name)] + def parseFuncDecl(self, linked_node): + lines = [] + node = linked_node.node + if node.args: + argstype = type(node.args).__name__ + assert argstype == "ParamList", "Expected function arguments, found '{}' instead".format(argstype) + lines += self.parseStatement(node.args, linked_node) + return lines + def parseParamList(self, linked_node): + """Processes function parameters and returns assembly for modifying SP + """ + lines = [] + variables = linked_node.getFunctionNode().variables + params = linked_node.node.params + for param in params: + variables.declName(param.name, is_param=True) + return lines def parseStatement(self, node, parent_linked_node, level_increment=False): linked_node = LinkedNode(node, parent_linked_node, level_increment=level_increment) self.asm.level = linked_node.level -- cgit v1.2.1