1.1 --- a/micropython/ast.py Sat Jun 21 17:23:23 2008 +0200
1.2 +++ b/micropython/ast.py Sun Jun 22 02:20:56 2008 +0200
1.3 @@ -75,22 +75,8 @@
1.4 self.temp_position = 0
1.5 self.stack = []
1.6
1.7 - def calculate_stack_usage(self):
1.8 - max_stack_usage = 0
1.9 - stack_usage = 0
1.10 -
1.11 - for op in self.code:
1.12 -
1.13 - # Fix stack access operands.
1.14 -
1.15 - op.fix_stack(stack_usage)
1.16 -
1.17 - # Update the stack levels.
1.18 -
1.19 - stack_usage += op.stack_usage
1.20 - max_stack_usage = max(max_stack_usage, stack_usage)
1.21 -
1.22 - self.unit.stack_usage = max_stack_usage
1.23 + def __repr__(self):
1.24 + return "Translation(%r)" % self.module
1.25
1.26 def get_module_code(self):
1.27
1.28 @@ -104,7 +90,6 @@
1.29 if self.module.module is not None:
1.30 self.dispatch(self.module.module)
1.31
1.32 - self.calculate_stack_usage()
1.33 return self.code
1.34
1.35 def get_code(self, unit):
1.36 @@ -119,12 +104,8 @@
1.37 if unit.astnode is not None:
1.38 self.dispatch(unit.astnode)
1.39
1.40 - self.calculate_stack_usage()
1.41 return self.code
1.42
1.43 - def __repr__(self):
1.44 - return "Translation(%r)" % self.module
1.45 -
1.46 def get_scope(self, name):
1.47 if self.unit.has_key(name):
1.48 return "local"
1.49 @@ -133,7 +114,47 @@
1.50 else:
1.51 return "builtins"
1.52
1.53 - # Code writing methods.
1.54 + # Code feature methods.
1.55 +
1.56 + def reset_stack(self):
1.57 +
1.58 + "Reset the stack for the current unit."
1.59 +
1.60 + self.stack = []
1.61 +
1.62 + def adjust_stack(self, op):
1.63 +
1.64 + "Adjust the stack according to the effect of 'op'."
1.65 +
1.66 + position = len(self.code)
1.67 + stack_level = len(self.stack)
1.68 +
1.69 + op.fix_stack(stack_level)
1.70 + effect = op.get_effect()
1.71 +
1.72 + if effect == 1:
1.73 + self.stack.append((position, op))
1.74 + elif effect < 0:
1.75 + while effect != 0:
1.76 + self.stack.pop()
1.77 + effect += 1
1.78 +
1.79 + # Update the stack levels.
1.80 +
1.81 + self.unit.stack_usage = max(self.unit.stack_usage, stack_level)
1.82 +
1.83 + def revert_stack(self, op):
1.84 +
1.85 + "Revert the stack affected by 'op'."
1.86 +
1.87 + effect = op.get_effect()
1.88 +
1.89 + if effect > 0:
1.90 + while effect != 0:
1.91 + self.stack.pop()
1.92 + effect -= 1
1.93 + elif effect < 0:
1.94 + raise ProcessingError, "Cannot remove instructions which reduce the stack."
1.95
1.96 def new_label(self):
1.97
1.98 @@ -183,33 +204,35 @@
1.99 if isinstance(temp, LoadTemp):
1.100 self.temp_position -= 1
1.101
1.102 + # Code writing methods.
1.103 +
1.104 def new_op(self, op):
1.105
1.106 "Add 'op' to the generated code."
1.107
1.108 position = len(self.code)
1.109 self._optimise_stack_access(op)
1.110 -
1.111 - if isinstance(op, ResetStack):
1.112 - if not self.stack:
1.113 - return
1.114 - self.stack = []
1.115 + self.adjust_stack(op)
1.116
1.117 self.code.append(op)
1.118
1.119 - if op.stack_usage == 1:
1.120 - self.stack.append((position, op))
1.121 - elif op.stack_usage == -1:
1.122 - for operand in op.operands:
1.123 - if isinstance(operand, StackLoad):
1.124 - self.stack.pop()
1.125 -
1.126 def new_ops(self, ops):
1.127
1.128 - "Add 'ops' to the generated code."
1.129 + """
1.130 + Add copies of 'ops' to the generated code. This is typically used in
1.131 + connection with sequences of temporary storage instructions.
1.132 + """
1.133
1.134 for op in ops:
1.135 - self.new_op(op)
1.136 + self.new_op(op.copy())
1.137 +
1.138 + def remove_ops(self, n):
1.139 +
1.140 + "Remove the last 'n' instructions."
1.141 +
1.142 + for i in range(0, n):
1.143 + op = self.code.pop()
1.144 + self.revert_stack(op)
1.145
1.146 def replace_op(self, op):
1.147
1.148 @@ -236,21 +259,6 @@
1.149 else:
1.150 break
1.151
1.152 - def remove_ops(self, n):
1.153 -
1.154 - "Remove the last 'n' instructions."
1.155 -
1.156 - for i in range(0, n):
1.157 - op = self.code.pop()
1.158 - if op.stack_usage == 1:
1.159 - self.stack.pop()
1.160 - elif op.stack_usage < 0:
1.161 - for operand in op.operands:
1.162 - if isinstance(operand, StackLoad):
1.163 - raise ProcessingError, "Cannot remove instructions which reduce the stack."
1.164 - elif isinstance(op, ResetStack):
1.165 - raise ProcessingError, "Cannot remove instructions which reduce the stack."
1.166 -
1.167 def last_ops(self, n):
1.168
1.169 "Return the last 'n' added instructions in reverse chronological order."
1.170 @@ -547,6 +555,7 @@
1.171 self.new_op(RaiseException())
1.172 self.set_label(continue_label)
1.173
1.174 + first = 0
1.175 frame_pos += 1
1.176
1.177 # NOTE: Extra keywords are not supported.
1.178 @@ -704,7 +713,7 @@
1.179 def _have_temp_compatible_access(self):
1.180 last = self.last_op()
1.181 # NOTE: Should expand to cover LoadAttr and LoadAttrIndex, but this
1.182 - # NOTE: would require inspection of the stack operands.
1.183 + # NOTE: would require inspection of the stack operations.
1.184 return isinstance(last, (LoadName, LoadTemp, LoadAddress, LoadConst))
1.185
1.186 def _have_fixed_sources(self, access):
1.187 @@ -836,13 +845,24 @@
1.188 return 0
1.189
1.190 def _optimise_stack_access(self, instruction):
1.191 +
1.192 + """
1.193 + Optimise stack access for the given 'instruction', replacing stack
1.194 + operations with instructions directly accessing the required data.
1.195 + """
1.196 +
1.197 if self._should_optimise_stack_access():
1.198 ops = self._have_fixed_sources(instruction.stack_access)
1.199 if ops:
1.200 - #print "Optimised", instruction.operands, "->", ops
1.201 + #print "Optimised", instruction.accesses, "->", ops
1.202 for i in range(0, instruction.stack_access):
1.203 self.remove_op_using_stack()
1.204 - instruction.operands = ops
1.205 + instruction.accesses = ops
1.206 +
1.207 + # Remove the stack side-effects of these accesses.
1.208 +
1.209 + for op in ops:
1.210 + op.remove_results()
1.211
1.212 # Visitor methods.
1.213
1.214 @@ -1135,7 +1155,6 @@
1.215
1.216 def visitDiscard(self, node):
1.217 self.dispatch(node.expr)
1.218 - self.new_op(ResetStack())
1.219
1.220 def visitDiv(self, node):
1.221 self._visitBinary(node, "__div__", "__rdiv__")
1.222 @@ -1208,7 +1227,6 @@
1.223 # Pop the iterator.
1.224
1.225 self.set_label(exit_label)
1.226 - self.new_op(ResetStack())
1.227
1.228 def visitFrom(self, node): pass
1.229
1.230 @@ -1332,6 +1350,7 @@
1.231 def visitStmt(self, node):
1.232 for n in node.nodes:
1.233 self.dispatch(n)
1.234 + self.reset_stack()
1.235
1.236 def visitSub(self, node):
1.237 self._visitBinary(node, "__sub__", "__rsub__")
2.1 --- a/micropython/rsvp.py Sat Jun 21 17:23:23 2008 +0200
2.2 +++ b/micropython/rsvp.py Sun Jun 22 02:20:56 2008 +0200
2.3 @@ -41,32 +41,63 @@
2.4
2.5 "A generic instruction."
2.6
2.7 - stack_usage = 0
2.8 + stack_storage = 0
2.9 stack_access = 0
2.10
2.11 def __init__(self, attr=None):
2.12 self.attr = attr
2.13 - self.operands = [StackLoad(-1 - n) for n in range(0, self.stack_access)]
2.14 + self.accesses = [StackLoad(-1 - n) for n in range(0, self.stack_access)]
2.15 + self.results = [StackSave(n) for n in range(0, self.stack_storage)]
2.16 +
2.17 + def copy(self):
2.18 + return self.__class__(self.attr)
2.19 +
2.20 + def remove_results(self):
2.21 +
2.22 + "Remove the stack side-effects for instructions replacing stack operations."
2.23 +
2.24 + self.results = []
2.25
2.26 def fix_stack(self, level):
2.27 - for operand in self.operands:
2.28 - operand.fix_stack(level)
2.29 +
2.30 + """
2.31 + Use the given 'level' to fix the details of this instruction's internal
2.32 + stack operations.
2.33 + """
2.34 +
2.35 + effect = 0
2.36 + for stack_op in self.accesses:
2.37 + stack_op.fix_stack(level)
2.38 + effect += stack_op.get_effect()
2.39
2.40 - def show_operands(self):
2.41 - return self.operands and (" %s" % self.operands) or ""
2.42 + level += effect
2.43 + for stack_op in self.results:
2.44 + stack_op.fix_stack(level)
2.45 +
2.46 + def get_effect(self):
2.47 + effect = 0
2.48 + for stack_op in self.accesses + self.results:
2.49 + effect += stack_op.get_effect()
2.50 + return effect
2.51 +
2.52 + def show_stack_ops(self):
2.53 + return "%s%s" % (
2.54 + self.accesses and (" <- %s" % self.accesses) or "",
2.55 + self.results and (" -> %s" % self.results) or ""
2.56 + )
2.57
2.58 def __repr__(self):
2.59 if self.attr is not None:
2.60 - return "%s(%r)%s" % (self.__class__.__name__, self.attr, self.show_operands())
2.61 + return "%s(%r)%s" % (self.__class__.__name__, self.attr, self.show_stack_ops())
2.62 else:
2.63 - return "%s()%s" % (self.__class__.__name__, self.show_operands())
2.64 + return "%s()%s" % (self.__class__.__name__, self.show_stack_ops())
2.65
2.66 class StackRelativeInstruction(Instruction):
2.67
2.68 "An instruction operating on the local value stack."
2.69
2.70 def __repr__(self):
2.71 - return "%s(%r)%s" % (self.__class__.__name__, self.get_operand(), self.show_operands())
2.72 + return "%s(%r)%s" % (self.__class__.__name__, self.get_operand(), self.show_stack_ops())
2.73
2.74 def get_operand(self):
2.75 return self.attr.position
2.76 @@ -80,9 +111,9 @@
2.77 def __repr__(self):
2.78 position = self.get_operand()
2.79 if position is not None:
2.80 - return "%s(%r)%s # %s" % (self.__class__.__name__, position, self.show_operands(), name(self.attr))
2.81 + return "%s(%r)%s # %s" % (self.__class__.__name__, position, self.show_stack_ops(), name(self.attr))
2.82 else:
2.83 - return "%s(%r)%s" % (self.__class__.__name__, self.show_operands(), name(self.attr))
2.84 + return "%s(%r)%s" % (self.__class__.__name__, self.show_stack_ops(), name(self.attr))
2.85
2.86 def get_operand(self):
2.87 return self.attr.position
2.88 @@ -96,11 +127,14 @@
2.89 def __repr__(self):
2.90 location, position, result = self.get_operands()
2.91 if location is not None:
2.92 - return "%s(%r)%s # %r, %r (%s)" % (self.__class__.__name__, result, self.show_operands(), location, position, name(self.attr))
2.93 + return "%s(%r)%s # %r, %r (%s)" % (
2.94 + self.__class__.__name__, result, self.show_stack_ops(), location, position, name(self.attr))
2.95 elif result is not None:
2.96 - return "%s(%r)%s # %s" % (self.__class__.__name__, result, self.show_operands(), name(self.attr))
2.97 + return "%s(%r)%s # %s" % (
2.98 + self.__class__.__name__, result, self.show_stack_ops(), name(self.attr))
2.99 else:
2.100 - return "%s(...)%s # %s" % (self.__class__.__name__, self.show_operands(), name(self.attr))
2.101 + return "%s(...)%s # %s" % (
2.102 + self.__class__.__name__, self.show_stack_ops(), name(self.attr))
2.103
2.104 def get_operands(self):
2.105 if isinstance(self.attr, Attr):
2.106 @@ -131,7 +165,7 @@
2.107 "An instruction employing a constant."
2.108
2.109 def __repr__(self):
2.110 - return "%s(%r)%s" % (self.__class__.__name__, self.attr, self.show_operands())
2.111 + return "%s(%r)%s" % (self.__class__.__name__, self.attr, self.show_stack_ops())
2.112
2.113 def get_operand(self):
2.114 return self.attr
2.115 @@ -147,26 +181,35 @@
2.116 instruction.
2.117 """
2.118
2.119 - stack_usage = 1
2.120 + stack_storage = 1
2.121
2.122 class StackRemove:
2.123
2.124 "Indicate that the stack must shrink as an effect of this instruction."
2.125
2.126 - stack_usage = -1
2.127 + stack_storage = -1
2.128 stack_access = 1
2.129
2.130 class StackRemove2:
2.131
2.132 "Indicate that the stack must shrink as an effect of this instruction."
2.133
2.134 - stack_usage = -2
2.135 + stack_storage = -2
2.136 stack_access = 2
2.137
2.138 +class StackReplace:
2.139 +
2.140 + """
2.141 + Indicate that the stack remains at the same level due to the replacement of
2.142 + the topmost element.
2.143 + """
2.144 +
2.145 + stack_storage = 1
2.146 + stack_access = 1
2.147 +
2.148 # Instructions operating on the value stack.
2.149
2.150 class Duplicate(StackAdd, Instruction): "Duplicate the top of the stack."
2.151 -class ResetStack(Instruction): "Pop entries from the stack."
2.152
2.153 # Access to stored constant data.
2.154
2.155 @@ -176,15 +219,15 @@
2.156
2.157 class LoadName(StackAdd, SR): "Load the object from the given local attribute/variable."
2.158 class StoreName(StackRemove, SR): "Store the object in the given local attribute/variable."
2.159 -class LoadTemp(Immediate): "Load the object from the given temporary location."
2.160 +class LoadTemp(StackAdd, Immediate): "Load the object from the given temporary location."
2.161 class StoreTemp(StackRemove, Immediate): "Store the object in the given temporary location."
2.162
2.163 # Access to address-relative data.
2.164
2.165 class MakeObject(StackAdd, Instruction): "Make a new object. There isn't a complementary DropObject."
2.166 -class LoadAttr(AR): "Load the object from the given attribute."
2.167 +class LoadAttr(StackReplace, AR): "Load the object from the given attribute."
2.168 class StoreAttr(StackRemove2, AR): "Store an object in the given attribute."
2.169 -class LoadAttrIndex(Immediate): "Load the object for the attribute with the given index."
2.170 +class LoadAttrIndex(StackReplace, Immediate): "Load the object for the attribute with the given index."
2.171 class StoreAttrIndex(StackRemove2, Immediate): "Store an object in the attribute with the given index."
2.172 class LoadAddress(StackAdd, Address): "Load the object from the given fixed attribute address."
2.173 class StoreAddress(StackRemove, Address): "Store an object in the given fixed attribute address."
2.174 @@ -205,12 +248,12 @@
2.175 class JumpIfFalse(Address): "Jump if the last evaluation gave a false result."
2.176 class JumpIfTrue(Address): "Jump if the last evaluation gave a true result."
2.177 class LoadCallable(Instruction): "Load the target of an invocation."
2.178 -class LoadContext(Instruction): "Load the context of an invocation."
2.179 +class LoadContext(StackReplace, Instruction): "Load the context of an invocation."
2.180 class CheckContext(Instruction): """Check the context of an invocation against the target,
2.181 potentially discarding the context."""
2.182 class CheckSelf(Instruction): "Check the first argument of an invocation against the target."
2.183 -class RaiseException(Instruction): "Raise an exception."
2.184 -class Return(Instruction): "Return a value from a subprogram."
2.185 +class RaiseException(StackRemove, Instruction): "Raise an exception."
2.186 +class Return(StackRemove, Instruction): "Return a value from a subprogram."
2.187 class CheckException(Instruction): "Check the raised exception against another."
2.188
2.189 # General instructions.
2.190 @@ -220,18 +263,35 @@
2.191
2.192 # Internal stack operations for instructions.
2.193
2.194 -class StackLoad:
2.195 +class StackOp:
2.196
2.197 - "Load a value from the stack."
2.198 + "A generic stack operation."
2.199
2.200 def __init__(self, n):
2.201 self.n = n
2.202 self.level = None
2.203
2.204 + def __repr__(self):
2.205 + return "%s(%s)" % (self.__class__.__name__, self.level == 0 and "0" or self.level or self.n)
2.206 +
2.207 +class StackLoad(StackOp):
2.208 +
2.209 + "Load a value from the stack."
2.210 +
2.211 def fix_stack(self, level):
2.212 self.level = self.n + level
2.213
2.214 - def __repr__(self):
2.215 - return "%s(%r)" % (self.__class__.__name__, self.n)
2.216 + def get_effect(self):
2.217 + return -1
2.218 +
2.219 +class StackSave(StackOp):
2.220 +
2.221 + "Save a value onto the stack."
2.222 +
2.223 + def fix_stack(self, level):
2.224 + self.level = self.n + level
2.225 +
2.226 + def get_effect(self):
2.227 + return 1
2.228
2.229 # vim: tabstop=4 expandtab shiftwidth=4