# HG changeset patch # User Paul Boddie # Date 1209258672 -7200 # Node ID 221517a873b36ddd1611ff7eb3526d9c5d1691c6 # Parent 445e08d9d4fb50f70fb940541f7af18efb905b85 Changed the Translation class to take the importer as a parameter when initialising instances. Introduced separate LoadAddress and SaveAddress instructions which work with known addresses, as opposed to LoadAttr and SaveAttr which now work with values on the stack only. Introduced accounting measures for stack and temporary storage elements. diff -r 445e08d9d4fb -r 221517a873b3 micropython/__init__.py --- a/micropython/__init__.py Sat Apr 26 18:35:18 2008 +0200 +++ b/micropython/__init__.py Sun Apr 27 03:11:12 2008 +0200 @@ -117,7 +117,7 @@ # Position the module in the image and make a translation. module.location = pos - trans = micropython.ast.Translation(module, objtable, paramtable, self.modules.get("__builtins__"), optimisations) + trans = micropython.ast.Translation(module, self, optimisations) # Add header details. diff -r 445e08d9d4fb -r 221517a873b3 micropython/ast.py --- a/micropython/ast.py Sat Apr 26 18:35:18 2008 +0200 +++ b/micropython/ast.py Sun Apr 27 03:11:12 2008 +0200 @@ -50,19 +50,24 @@ supported_optimisations = ["constant_storage", "known_target", "self_access"] - def __init__(self, module, objtable, paramtable, builtins=None, optimisations=None): + def __init__(self, module, importer, optimisations=None): """ - Initialise the translation with an inspected 'module' and an attribute - table 'objtable' and parameter table 'paramtable'. + Initialise the translation with an inspected 'module', the 'importer' + and optional 'optimisations'. See the 'supported_optimisations' + attribute of this class for permitted values. """ ASTVisitor.__init__(self) self.visitor = self self.module = module - self.objtable = objtable - self.paramtable = paramtable - self.builtins = builtins + + # Global program dependencies. + + self.importer = importer + self.objtable = self.importer.get_object_table() + self.paramtable = self.importer.get_parameter_table() + self.builtins = self.importer.modules.get("__builtins__") # Desired optimisations. @@ -79,10 +84,26 @@ self.loop_labels = [] self.exception_labels = [] - # The code itself. + # The code itself. This is limited to the code for a particular block + # being processed. self.code = None + def calculate_stack_usage(self): + max_stack_usage = 0 + max_stack_temp_usage = 0 + stack_usage = 0 + stack_temp_usage = 0 + + for op in self.code: + stack_usage += op.stack_usage + stack_temp_usage += op.stack_temp_usage + max_stack_usage = max(max_stack_usage, stack_usage) + max_stack_temp_usage = max(max_stack_temp_usage, stack_temp_usage) + + self.unit.stack_usage = max_stack_usage + self.unit.stack_temp_usage = max_stack_temp_usage + def get_module_code(self): "Return the top-level module code." @@ -91,6 +112,7 @@ self.code = [] if self.module.module is not None: self.dispatch(self.module.module) + self.calculate_stack_usage() return self.code def get_code(self, unit): @@ -101,6 +123,7 @@ self.code = [] if unit.node is not None: self.dispatch(unit.node) + self.calculate_stack_usage() return self.code def get_default_code(self, unit): @@ -111,7 +134,7 @@ for attr, default in zip(unit.default_attrs, unit.defaults): self.dispatch(default) self.new_op(LoadConst(unit)) - self.new_op(StoreAttr(attr)) + self.new_op(StoreAddress(attr)) return self.code def __repr__(self): @@ -217,7 +240,7 @@ Generate code for the access to 'attrname' using the given 'classes'. """ - AttrInstruction, AttrIndexInstruction = classes + AddressInstruction, AttrInstruction, AttrIndexInstruction = classes # NOTE: Only simple cases are used for optimisations. last = self.last_op() @@ -229,7 +252,7 @@ # Optimise away the constant storage if appropriate. - if self._optimise_constant_storage(AttrInstruction, 1): + if self._optimise_constant_storage(AddressInstruction, 1): return # Get the details of the access. @@ -249,7 +272,10 @@ raise TranslateError(self.module.full_name(), node, "No attribute entry exists for name %r in target %r." % (attrname, target_name)) - self.replace_op(AttrInstruction(pos)) + if isinstance(target, micropython.inspect.Instance): + self.replace_op(AttrInstruction(pos)) + else: + self.replace_op(AddressInstruction(pos)) # Where the last operation involves the special 'self' name, check to # see if the attribute is acceptably positioned and produce a direct @@ -476,7 +502,7 @@ 'classes', and using the given 'node' as the source of the access. """ - NameInstruction, AttrInstruction = classes + NameInstruction, AddressInstruction = classes if self._optimise_constant_storage(NameInstruction, 0): return @@ -486,21 +512,21 @@ if isinstance(unit, micropython.inspect.Function): self.new_op(NameInstruction(unit.all_locals()[name])) elif isinstance(unit, micropython.inspect.Class): - self.new_op(AttrInstruction(unit.all_class_attributes()[name])) + self.new_op(AddressInstruction(unit.all_class_attributes()[name])) elif isinstance(unit, micropython.inspect.Module): - self.new_op(AttrInstruction(unit.module_attributes()[name])) + self.new_op(AddressInstruction(unit.module_attributes()[name])) else: raise TranslateError(self.module.full_name(), node, "Program unit %r has no local %r." % (unit, name)) elif scope == "global": globals = self.module.module_attributes() if globals.has_key(name): - self.new_op(AttrInstruction(globals[name])) + self.new_op(AddressInstruction(globals[name])) else: raise TranslateError(self.module.full_name(), node, "Module %r has no attribute %r." % (self.module, name)) else: - self.new_op(AttrInstruction(self._get_builtin(name, node))) + self.new_op(AddressInstruction(self._get_builtin(name, node))) def _get_builtin(self, name, node): if self.builtins is not None: @@ -546,7 +572,7 @@ """ if self._should_optimise_constant_storage() and \ - instruction in (StoreAttr, StoreName) and \ + instruction in (StoreAddress, StoreName) and \ self._have_constant_input(n) and \ (n == 0 or self._have_constant_input(n-1)): @@ -633,7 +659,7 @@ self._startCallFunc() self.new_op(LoadTemp(1)) - self._generateAttr(node, left_method, (LoadAttr, LoadAttrIndex)) + self._generateAttr(node, left_method, (LoadAddress, LoadAttr, LoadAttrIndex)) self.new_op(LoadTemp(1)) # Explicit context as first argument. self.new_op(LoadTemp(2)) self._endCallFunc() @@ -647,7 +673,7 @@ self.set_label(right_label) self._startCallFunc() self.new_op(LoadTemp(2)) - self._generateAttr(node, right_method, (LoadAttr, LoadAttrIndex)) + self._generateAttr(node, right_method, (LoadAddress, LoadAttr, LoadAttrIndex)) self.new_op(LoadTemp(2)) # Explicit context as first argument. self.new_op(LoadTemp(1)) self._endCallFunc() @@ -667,12 +693,12 @@ self.dispatch(n) def visitAssAttr(self, node): - self._visitAttr(node, (StoreAttr, StoreAttrIndex)) + self._visitAttr(node, (StoreAddress, StoreAttr, StoreAttrIndex)) def visitAssList(self, node): pass def visitAssName(self, node): - self._visitName(node, (StoreName, StoreAttr)) + self._visitName(node, (StoreName, StoreAddress)) visitAssTuple = visitAssList @@ -760,7 +786,7 @@ self._startCallFunc() self.dispatch(node.list) - self._generateAttr(node, "__iter__", (LoadAttr, LoadAttrIndex)) + self._generateAttr(node, "__iter__", (LoadAddress, LoadAttr, LoadAttrIndex)) self._generateCallFunc([], node) self._endCallFunc() @@ -774,7 +800,7 @@ self._startCallFunc() self.new_op(Duplicate()) - self._generateAttr(node, "next", (LoadAttr, LoadAttrIndex)) + self._generateAttr(node, "next", (LoadAddress, LoadAttr, LoadAttrIndex)) self._generateCallFunc([], node) self._endCallFunc() @@ -820,7 +846,7 @@ if self.unit is not node.unit: self.new_op(LoadConst(node.unit)) - self._visitName(node, (StoreName, StoreAttr)) + self._visitName(node, (StoreName, StoreAddress)) # Visiting of the code occurs when get_code is invoked on this node. @@ -839,7 +865,7 @@ def visitGenExprInner(self, node): pass def visitGetattr(self, node): - self._visitAttr(node, (LoadAttr, LoadAttrIndex)) + self._visitAttr(node, (LoadAddress, LoadAttr, LoadAttrIndex)) def visitGlobal(self, node): pass @@ -890,7 +916,7 @@ self._visitBinary(node, "__mul__", "__rmul__") def visitName(self, node): - self._visitName(node, (LoadName, LoadAttr)) + self._visitName(node, (LoadName, LoadAddress)) def visitNot(self, node): pass diff -r 445e08d9d4fb -r 221517a873b3 micropython/inspect.py --- a/micropython/inspect.py Sat Apr 26 18:35:18 2008 +0200 +++ b/micropython/inspect.py Sun Apr 27 03:11:12 2008 +0200 @@ -322,6 +322,11 @@ self.code_location = None self.instantiator = None + # Program-related details. + + self.stack_usage = None + self.stack_temp_usage = None + def __repr__(self): if self.location is not None: return "Class(%r, %r, location=%r)" % (self.name, self.parent, self.location) @@ -621,6 +626,11 @@ self.location = None self.code_location = None + # Program-related details. + + self.stack_usage = None + self.stack_temp_usage = None + def _add_parameters(self, argnames): for name in argnames: if isinstance(name, tuple): @@ -764,6 +774,10 @@ NamespaceDict.__init__(self, self) self.name = name + # Original location details. + + self.node = None + # Complete lists of classes and functions. self.all_objects = set() @@ -782,9 +796,10 @@ self.location = None self.code_location = None - # Original location details. + # Program-related details. - self.node = None + self.stack_usage = None + self.stack_temp_usage = None def full_name(self): return self.name diff -r 445e08d9d4fb -r 221517a873b3 micropython/rsvp.py --- a/micropython/rsvp.py Sat Apr 26 18:35:18 2008 +0200 +++ b/micropython/rsvp.py Sun Apr 27 03:11:12 2008 +0200 @@ -25,6 +25,9 @@ "A generic instruction." + stack_usage = 0 + stack_temp_usage = 0 + def __init__(self, attr=None): self.attr = attr @@ -85,48 +88,86 @@ Immediate = ImmediateInstruction +# Mix-in classes for stack effects. + +class StackAdd: + + """ + Indicate that the stack must grow to accommodate the result of this + instruction. + """ + + stack_usage = 1 + +class StackRemove: + + "Indicate that the stack must shrink as an effect of this instruction." + + stack_usage = -1 + +class StackRemove2: + + "Indicate that the stack must shrink as an effect of this instruction." + + stack_usage = -2 + +class TempAdd: + + "Indicate that one more temporary storage location is now required." + + stack_temp_usage = 1 + +class TempRemove: + + "Indicate that one fewer temporary storage location is now required." + + stack_temp_usage = -1 + # Instructions operating on the value stack. -class LoadConst(Address): "Load the constant from the specified location." -class Duplicate(Instruction): "Duplicate the top of stack." -class Pop(Instruction): "Pop the top of stack." +class LoadConst(StackAdd, Address): "Load the constant from the specified location." +class Duplicate(StackAdd, Instruction): "Duplicate the top of the stack." +class Pop(StackRemove, Immediate): "Pop entries from the top of the stack." # Access within an invocation frame. -class LoadName(SR): "Load the object from the given local attribute/variable." -class StoreName(SR): "Store the object in the given local attribute/variable." -class LoadTemp(SR): "Load the object from the given temporary location." -class StoreTemp(SR): "Store the object in the given temporary location." +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(TempAdd, SR): "Load the object from the given temporary location." +class StoreTemp(SR): "Store the object in the given temporary location." # Access to address-relative data. -class MakeObject(Instruction): "Make a new object." -# ... DropObject not defined: Assume garbage collection. -class LoadAttr(AR): "Load the object from the given attribute." -class StoreAttr(AR): "Store an object in the given attribute." -class LoadAttrIndex(Immediate): "Load the object for the attribute with the given index." -class StoreAttrIndex(Immediate): "Store an object in the attribute with the given index." +class MakeObject(StackAdd, Instruction): "Make a new object." +# ... DropObject not defined: Assume garbage collection. +class LoadAttr(AR): "Load the object from the given attribute." +class StoreAttr(StackRemove2, AR): "Store an object in the given attribute." +class LoadAttrIndex(Immediate): "Load the object for the attribute with the given index." +class StoreAttrIndex(StackRemove2, Immediate): "Store an object in the attribute with the given index." +class LoadAddress(StackAdd, AR): "Load the object from the given fixed attribute address." +class StoreAddress(StackRemove, AR): "Store an object in the given fixed attribute address." # Access to invocation frames in preparation. -class MakeFrame(Instruction): "Make a new invocation frame." -class ReserveFrame(Immediate): "Reserve the given number of entries for the invocation frame." -class DropFrame(Instruction): "Drop an invocation frame." -class StoreFrame(Instruction): "Store an argument at the given frame location." -class StoreFrameIndex(Immediate): "Store an argument for the parameter with the given index." -class CheckFrame(Instruction): "Check the invocation frame for the target." -class JumpWithFrame(Instruction): "Jump, adopting the invocation frame." +class MakeFrame(Instruction): "Make a new invocation frame." +class ReserveFrame(Immediate): "Reserve the given number of entries for the invocation frame." +class DropFrame(Instruction): "Drop an invocation frame." +class StoreFrame(StackRemove, Instruction): "Store an argument at the given frame location." +class StoreFrameIndex(StackRemove, Immediate): "Store an argument for the parameter with the given index." +class CheckFrame(Instruction): "Check the invocation frame for the target." +class JumpWithFrame(Instruction): "Jump, adopting the invocation frame." # Invocation-related instructions. -class Jump(Instruction): "Jump unconditionally." -class JumpIfFalse(Instruction): "Jump if the last evaluation gave a false result." -class JumpIfTrue(Instruction): "Jump if the last evaluation gave a true result." -class LoadCallable(Instruction): "Load the target of an invocation." -class LoadContext(Instruction): "Load the context of an invocation." -class CheckContext(Instruction): "Check the context of an invocation against the target, potentially discarding the context." -class RaiseException(Instruction): "Raise an exception." -class Return(Instruction): "Return a value from a subprogram." -class CheckException(Instruction): "Check the raised exception against another." +class Jump(Instruction): "Jump unconditionally." +class JumpIfFalse(Instruction): "Jump if the last evaluation gave a false result." +class JumpIfTrue(Instruction): "Jump if the last evaluation gave a true result." +class LoadCallable(Instruction): "Load the target of an invocation." +class LoadContext(Instruction): "Load the context of an invocation." +class CheckContext(Instruction): """Check the context of an invocation against the target, + potentially discarding the context.""" +class RaiseException(Instruction): "Raise an exception." +class Return(Instruction): "Return a value from a subprogram." +class CheckException(Instruction): "Check the raised exception against another." # vim: tabstop=4 expandtab shiftwidth=4 diff -r 445e08d9d4fb -r 221517a873b3 rsvp.py --- a/rsvp.py Sat Apr 26 18:35:18 2008 +0200 +++ b/rsvp.py Sun Apr 27 03:11:12 2008 +0200 @@ -228,6 +228,9 @@ self.value_stack[frame + n] = self.pull() self.pc += 2 + LoadTemp = LoadName + StoreTemp = StoreName + def LoadConst(self): """ @@ -270,6 +273,35 @@ self.save(self.pull() + n, value) self.pc += 2 + def LoadAddress(self): + + """ + LoadAddress addr, #n + Load from position n in reference at addr: get the contents of position + n in the memory referenced by addr, adding the retrieved value to the + top of the stack. + """ + + red = self.load(self.pc + 1) + n = self.load(self.pc + 2) + self.push(self.load(ref + n)) + self.pc += 3 + + def StoreAddress(self): + + """ + StoreAddress addr, #n + Save to position n in reference at addr: pull a value from the stack and + save it to position n in the memory referenced by addr, also removing + the value on the top of the stack. + """ + + ref = self.load(self.pc + 1) + n = self.load(self.pc + 2) + value = self.pull() + self.save(ref + n, value) + self.pc += 3 + def Return(self): """