# HG changeset patch # User Paul Boddie # Date 1213574206 -7200 # Node ID de8cd27e721d58cd12225a287116b49c23b5d7df # Parent ae889a05bc32b987e52d60f667d96cabe7f15eac Added internal stack operations to instructions in order to support stack avoidance optimisations (where operands are loaded from other places than the stack). Replaced Pop with ResetStack. Added code and code_location attributes to the Importer class; made the test program's machine function use an Importer instance which provides such attributes for the initialisation of the RSVPMachine. diff -r ae889a05bc32 -r de8cd27e721d micropython/__init__.py --- a/micropython/__init__.py Mon Jun 09 21:09:37 2008 +0200 +++ b/micropython/__init__.py Mon Jun 16 01:56:46 2008 +0200 @@ -77,6 +77,11 @@ self.constant_values = {} self.constant_list = None # cache for constants + # Main program information. + + self.code = None + self.code_location = None + def constants(self): "Return a list of constants." @@ -210,6 +215,8 @@ image += code pos += len(code) + self.code = image + self.code_location = self.modules["__main__"].code_location return image def get_object_table(self): diff -r ae889a05bc32 -r de8cd27e721d micropython/ast.py --- a/micropython/ast.py Mon Jun 09 21:09:37 2008 +0200 +++ b/micropython/ast.py Mon Jun 16 01:56:46 2008 +0200 @@ -31,7 +31,7 @@ "A translated module." - supported_optimisations = ["constant_storage", "known_target", "self_access", "temp_storage", "constant_test"] + supported_optimisations = ["constant_storage", "known_target", "self_access", "temp_storage", "constant_test", "stack_access"] def __init__(self, module, importer, optimisations=None): @@ -68,16 +68,25 @@ self.exception_labels = [] # The code itself. This is limited to the code for a particular block - # being processed. + # being processed. Also retained is information about temporary values + # and the presumed state of the value stack. self.code = None self.temp_position = 0 + self.stack = [] def calculate_stack_usage(self): max_stack_usage = 0 stack_usage = 0 for op in self.code: + + # Fix stack access operands. + + op.fix_stack(stack_usage) + + # Update the stack levels. + stack_usage += op.stack_usage max_stack_usage = max(max_stack_usage, stack_usage) @@ -90,6 +99,7 @@ self.unit = self.module self.code = [] self.temp_position = self.unit.stack_local_usage + self.stack = [] if self.module.module is not None: self.dispatch(self.module.module) @@ -104,6 +114,7 @@ self.unit = unit self.code = [] self.temp_position = self.unit.stack_local_usage + self.stack = [] if unit.astnode is not None: self.dispatch(unit.astnode) @@ -176,25 +187,69 @@ "Add 'op' to the generated code." + position = len(self.code) + self._optimise_stack_access(op) + + if isinstance(op, ResetStack): + if not self.stack: + return + self.stack = [] + self.code.append(op) + if op.stack_usage == 1: + self.stack.append((position, op)) + elif op.stack_usage == -1: + for operand in op.operands: + if isinstance(operand, StackLoad): + self.stack.pop() + def new_ops(self, ops): "Add 'ops' to the generated code." - self.code += ops + for op in ops: + self.new_op(op) def replace_op(self, op): "Replace the last added instruction with 'op'." - self.code[-1] = op + self.remove_ops(1) + self.new_op(op) + + def remove_op_using_stack(self): + + "Remove the instruction which created the top stack position." + + position, op = self.stack.pop() + + # NOTE: For now, just erase the instruction. + + self.code[position] = None + + op = self.code[-1] + while op is None: + del self.code[-1] + if self.code: + op = self.code[-1] + else: + break def remove_ops(self, n): "Remove the last 'n' instructions." - del self.code[-n:] + for i in range(0, n): + op = self.code.pop() + if op.stack_usage == 1: + self.stack.pop() + elif op.stack_usage < 0: + for operand in op.operands: + if isinstance(operand, StackLoad): + raise ProcessingError, "Cannot remove instructions which reduce the stack." + elif isinstance(op, ResetStack): + raise ProcessingError, "Cannot remove instructions which reduce the stack." def last_ops(self, n): @@ -629,6 +684,9 @@ def _should_optimise_temp_storage(self): return "temp_storage" in self.optimisations + def _should_optimise_stack_access(self): + return "stack_access" in self.optimisations + def _have_constant_input(self, n): last = self.last_ops(n+1) return len(last) > n and (isinstance(last[n], LoadAddress) and last[n].attr.assignments == 1 or @@ -649,6 +707,15 @@ # NOTE: would require inspection of the stack operands. return isinstance(last, (LoadName, LoadTemp, LoadAddress, LoadConst)) + def _have_fixed_sources(self, access): + access_ops = [] + for i in xrange(0, access): + position, op = self.stack[-1 - i] + if not isinstance(op, (LoadName, LoadTemp, LoadAddress, LoadConst)): + return 0 + access_ops.append(op) + return access_ops + # Optimisation methods. See the supported_optimisations class attribute. def _optimise_temp_storage(self): @@ -768,6 +835,15 @@ else: return 0 + def _optimise_stack_access(self, instruction): + if self._should_optimise_stack_access(): + ops = self._have_fixed_sources(instruction.stack_access) + if ops: + #print "Optimised", instruction.operands, "->", ops + for i in range(0, instruction.stack_access): + self.remove_op_using_stack() + instruction.operands = ops + # Visitor methods. def default(self, node, *args): @@ -1059,7 +1135,7 @@ def visitDiscard(self, node): self.dispatch(node.expr) - self.new_op(Pop()) + self.new_op(ResetStack()) def visitDiv(self, node): self._visitBinary(node, "__div__", "__rdiv__") @@ -1132,7 +1208,7 @@ # Pop the iterator. self.set_label(exit_label) - self.new_op(Pop()) + self.new_op(ResetStack()) def visitFrom(self, node): pass diff -r ae889a05bc32 -r de8cd27e721d micropython/rsvp.py --- a/micropython/rsvp.py Mon Jun 09 21:09:37 2008 +0200 +++ b/micropython/rsvp.py Mon Jun 16 01:56:46 2008 +0200 @@ -42,22 +42,31 @@ "A generic instruction." stack_usage = 0 + stack_access = 0 def __init__(self, attr=None): self.attr = attr + self.operands = [StackLoad(-1 - n) for n in range(0, self.stack_access)] + + def fix_stack(self, level): + for operand in self.operands: + operand.fix_stack(level) + + def show_operands(self): + return self.operands and (" %s" % self.operands) or "" def __repr__(self): if self.attr is not None: - return "%s(%r)" % (self.__class__.__name__, self.attr) + return "%s(%r)%s" % (self.__class__.__name__, self.attr, self.show_operands()) else: - return "%s()" % self.__class__.__name__ + return "%s()%s" % (self.__class__.__name__, self.show_operands()) class StackRelativeInstruction(Instruction): "An instruction operating on the local value stack." def __repr__(self): - return "%s(%r)" % (self.__class__.__name__, self.get_operand()) + return "%s(%r)%s" % (self.__class__.__name__, self.get_operand(), self.show_operands()) def get_operand(self): return self.attr.position @@ -71,9 +80,9 @@ def __repr__(self): position = self.get_operand() if position is not None: - return "%s(%r) # %s" % (self.__class__.__name__, position, name(self.attr)) + return "%s(%r)%s # %s" % (self.__class__.__name__, position, self.show_operands(), name(self.attr)) else: - return "%s(%r)" % (self.__class__.__name__, name(self.attr)) + return "%s(%r)%s" % (self.__class__.__name__, self.show_operands(), name(self.attr)) def get_operand(self): return self.attr.position @@ -87,11 +96,11 @@ def __repr__(self): location, position, result = self.get_operands() if location is not None: - return "%s(%r) # %r, %r (%s)" % (self.__class__.__name__, result, location, position, name(self.attr)) + return "%s(%r)%s # %r, %r (%s)" % (self.__class__.__name__, result, self.show_operands(), location, position, name(self.attr)) elif result is not None: - return "%s(%r) # %s" % (self.__class__.__name__, result, name(self.attr)) + return "%s(%r)%s # %s" % (self.__class__.__name__, result, self.show_operands(), name(self.attr)) else: - return "%s(...) # %s" % (self.__class__.__name__, name(self.attr)) + return "%s(...)%s # %s" % (self.__class__.__name__, self.show_operands(), name(self.attr)) def get_operands(self): if isinstance(self.attr, Attr): @@ -122,7 +131,7 @@ "An instruction employing a constant." def __repr__(self): - return "%s(%r)" % (self.__class__.__name__, self.attr) + return "%s(%r)%s" % (self.__class__.__name__, self.attr, self.show_operands()) def get_operand(self): return self.attr @@ -145,17 +154,19 @@ "Indicate that the stack must shrink as an effect of this instruction." stack_usage = -1 + stack_access = 1 class StackRemove2: "Indicate that the stack must shrink as an effect of this instruction." stack_usage = -2 + stack_access = 2 # Instructions operating on the value stack. class Duplicate(StackAdd, Instruction): "Duplicate the top of the stack." -class Pop(StackRemove, Instruction): "Pop entries from the top of the stack." +class ResetStack(Instruction): "Pop entries from the stack." # Access to stored constant data. @@ -166,7 +177,7 @@ class LoadName(StackAdd, SR): "Load the object from the given local attribute/variable." class StoreName(StackRemove, SR): "Store the object in the given local attribute/variable." class LoadTemp(Immediate): "Load the object from the given temporary location." -class StoreTemp(Immediate): "Store the object in the given temporary location." +class StoreTemp(StackRemove, Immediate): "Store the object in the given temporary location." # Access to address-relative data. @@ -207,4 +218,20 @@ class TestIdentity(Instruction): "Test whether the two topmost stack values are identical." class TestIdentityAddress(Address): "Test whether the topmost stack value is identical to the given address." +# Internal stack operations for instructions. + +class StackLoad: + + "Load a value from the stack." + + def __init__(self, n): + self.n = n + self.level = None + + def fix_stack(self, level): + self.level = self.n + level + + def __repr__(self): + return "%s(%r)" % (self.__class__.__name__, self.n) + # vim: tabstop=4 expandtab shiftwidth=4 diff -r ae889a05bc32 -r de8cd27e721d test.py --- a/test.py Mon Jun 09 21:09:37 2008 +0200 +++ b/test.py Mon Jun 16 01:56:46 2008 +0200 @@ -20,10 +20,10 @@ for i, x in enumerate(code): print i, x -def machine(code, code_location): - rc = raw(code) +def machine(importer): + rc = raw(importer.code) rm = rsvp.RSVPMachine(rc) - rm.pc = code_location + rm.pc = importer.code_location return rm def attrs(obj): @@ -40,7 +40,8 @@ requested_optimisations = [] for arg in args: if arg.startswith("-o"): - requested_optimisations.append(arg[2:]) + for arg_part in arg[2:].split(","): + requested_optimisations.append(arg_part) try: builtins = i.load_from_file("lib/builtins.py", "__builtins__")