1.1 --- a/micropython/ast.py Fri Jul 18 01:18:22 2008 +0200
1.2 +++ b/micropython/ast.py Sat Jul 19 00:39:50 2008 +0200
1.3 @@ -31,7 +31,7 @@
1.4
1.5 "A translated module."
1.6
1.7 - supported_optimisations = ["constant_storage", "known_target", "self_access", "temp_storage"]
1.8 + supported_optimisations = ["constant_storage", "known_target", "self_access", "temp_storage", "load_operations"]
1.9
1.10 attribute_load_instructions = (LoadAddress, LoadAddressContext, LoadAttr, LoadAttrIndex)
1.11 attribute_store_instructions = (StoreAddress, StoreAddressContext, StoreAttr, StoreAttrIndex)
1.12 @@ -69,6 +69,10 @@
1.13
1.14 self.active = None
1.15
1.16 + # The temporary storage used by the current assignment expression.
1.17 +
1.18 + self.expr_temp = None
1.19 +
1.20 # Wiring within the code.
1.21
1.22 self.labels = {}
1.23 @@ -216,6 +220,10 @@
1.24 if self._optimise_constant_storage(op):
1.25 return
1.26
1.27 + # Optimise load operations employed by this instruction.
1.28 +
1.29 + self._optimise_load_operations(op)
1.30 +
1.31 self.code.append(op)
1.32 self.active = op
1.33
1.34 @@ -242,6 +250,207 @@
1.35 except IndexError:
1.36 return None
1.37
1.38 + # Optimisation tests.
1.39 +
1.40 + def _should_optimise_constant_storage(self):
1.41 + return "constant_storage" in self.optimisations
1.42 +
1.43 + def _should_optimise_known_target(self):
1.44 + return "known_target" in self.optimisations
1.45 +
1.46 + def _should_optimise_self_access(self):
1.47 + return "self_access" in self.optimisations
1.48 +
1.49 + def _should_optimise_temp_storage(self):
1.50 + return "temp_storage" in self.optimisations
1.51 +
1.52 + def _should_optimise_load_operations(self):
1.53 + return "load_operations" in self.optimisations
1.54 +
1.55 + # Simple tests.
1.56 +
1.57 + def _is_constant_input(self, instruction):
1.58 +
1.59 + "Return whether 'instruction' provides a constant input."
1.60 +
1.61 + return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 or \
1.62 + isinstance(instruction, LoadConst)
1.63 +
1.64 + def _is_constant_target(self, instruction):
1.65 +
1.66 + "Return whether 'instruction' provides a constant target."
1.67 +
1.68 + return isinstance(instruction, (StoreName, StoreAddress)) and \
1.69 + instruction.attr.assignments == 1
1.70 +
1.71 + def _is_simple_input(self, instruction):
1.72 +
1.73 + "Return whether 'instruction' provides a simple input."
1.74 +
1.75 + return isinstance(instruction, (LoadName, LoadTemp, LoadResult, LoadAddress))
1.76 +
1.77 + def _is_simple_input_user(self, instruction):
1.78 +
1.79 + "Return whether 'instruction' can use simple input."
1.80 +
1.81 + return isinstance(instruction,
1.82 + (StoreName, StoreTemp, StoreFrame, StoreAddress, RaiseException) + self.attribute_store_instructions)
1.83 +
1.84 + # Convenience tests.
1.85 +
1.86 + def _have_constant_input(self):
1.87 +
1.88 + "Return whether the active instruction provides a constant input."
1.89 +
1.90 + return self._is_constant_input(self.active)
1.91 +
1.92 + _have_known_target = _have_constant_input
1.93 +
1.94 + def _have_simple_input(self):
1.95 +
1.96 + "Return whether the active instruction provides a local input."
1.97 +
1.98 + return self._is_simple_input(self.active)
1.99 +
1.100 + def _have_self_input(self):
1.101 +
1.102 + "Return whether the active instruction is a reference to self."
1.103 +
1.104 + return isinstance(self.unit, Function) and \
1.105 + self.unit.is_method() and isinstance(self.active, LoadName) and \
1.106 + self.active.attr.name == "self"
1.107 +
1.108 + def _have_temp_compatible_access(self):
1.109 +
1.110 + """
1.111 + Indicate whether the active instruction can be used in place of access
1.112 + to a temporary variable retaining the result of the last instruction.
1.113 + """
1.114 +
1.115 + return isinstance(self.active, (LoadName, LoadTemp, LoadAddress, LoadConst))
1.116 +
1.117 + # Optimisation methods. See the supported_optimisations class attribute.
1.118 +
1.119 + def _optimise_constant_storage(self, instruction):
1.120 +
1.121 + """
1.122 + Where this operation should store a constant into a target which is
1.123 + also constant, optimise away both operations.
1.124 + """
1.125 +
1.126 + if self._should_optimise_constant_storage() and \
1.127 + self._is_constant_target(instruction) and \
1.128 + self._have_constant_input():
1.129 +
1.130 + self.remove_op()
1.131 + return 1
1.132 + else:
1.133 + return 0
1.134 +
1.135 + def _optimise_known_target(self):
1.136 +
1.137 + """
1.138 + Where the target of an invocation is known, provide information about it
1.139 + and its context. If a class is being invoked and the conditions are
1.140 + appropriate, get information about the specific initialiser.
1.141 + """
1.142 +
1.143 + if self._should_optimise_known_target() and self._have_known_target():
1.144 + last = self.last_op()
1.145 + target = last.attr.value
1.146 + context = last.attr.context
1.147 +
1.148 + # Handle calls to classes.
1.149 +
1.150 + if isinstance(target, Class):
1.151 + target = target.get_instantiator()
1.152 + context = Instance()
1.153 +
1.154 + # A special context is chosen to avoid generating unnecessary
1.155 + # context loading and checking instructions.
1.156 +
1.157 + return target, context
1.158 + else:
1.159 + return None
1.160 +
1.161 + def _optimise_self_access(self, attrname, classes):
1.162 +
1.163 + """
1.164 + Where the provided 'attrname' accesses an attribute which occupies the
1.165 + same position in all possible objects which can be accessed, generate an
1.166 + instruction using one of the given 'classes', accessing the attribute
1.167 + directly.
1.168 + """
1.169 +
1.170 + AddressInstruction, AddressContextInstruction, AttrInstruction = classes
1.171 +
1.172 + if self._should_optimise_self_access() and self._have_self_input() and \
1.173 + not self.unit.is_relocated(attrname):
1.174 +
1.175 + # Either generate an instruction operating on an instance attribute.
1.176 +
1.177 + try:
1.178 + attr = self.unit.parent.instance_attributes()[attrname]
1.179 + self.new_op(AttrInstruction(attr))
1.180 +
1.181 + # Or generate an instruction operating on a class attribute.
1.182 +
1.183 + except KeyError:
1.184 + attr = self.unit.parent.all_attributes()[attrname]
1.185 + new_attr = attr.via_instance()
1.186 + self.new_op(AddressContextInstruction(new_attr))
1.187 +
1.188 + return 1
1.189 + else:
1.190 + return 0
1.191 +
1.192 + def _optimise_temp_storage(self):
1.193 +
1.194 + """
1.195 + Where the next operation would involve storing a value into temporary
1.196 + storage at 'temp_position', record and remove any simple instruction
1.197 + which produced the value to be stored such that instead of subsequently
1.198 + accessing the temporary storage, that instruction is substituted.
1.199 +
1.200 + If no optimisation can be achieved, a StoreTemp instruction is produced
1.201 + and the appropriate LoadTemp instruction is returned.
1.202 +
1.203 + Restriction: for use only in situations where the source of the
1.204 + temporary data will not be disturbed between its first access and its
1.205 + subsequent use.
1.206 + """
1.207 +
1.208 + if self._should_optimise_temp_storage() and \
1.209 + self._have_temp_compatible_access():
1.210 +
1.211 + last = self.last_op()
1.212 + self.remove_op()
1.213 + return last
1.214 + else:
1.215 + return self.get_temp()
1.216 +
1.217 + def _optimise_load_operations(self, instruction):
1.218 +
1.219 + """
1.220 + Incorporate previous load operations into other operations.
1.221 + """
1.222 +
1.223 + if self._should_optimise_load_operations() and \
1.224 + self._have_simple_input() and \
1.225 + self._is_simple_input_user(instruction):
1.226 +
1.227 + last = self.last_op()
1.228 + self.remove_op()
1.229 + instruction.input = last
1.230 +
1.231 + # Visitor methods.
1.232 +
1.233 + def default(self, node, *args):
1.234 + raise TranslateError(self.module.full_name(), node, "Node class %r is not supported." % node.__class__)
1.235 +
1.236 + def dispatch(self, node, *args):
1.237 + return ASTVisitor.dispatch(self, node, *args)
1.238 +
1.239 # Internal helper methods.
1.240
1.241 def _visitAttr(self, node, classes):
1.242 @@ -623,177 +832,6 @@
1.243 else:
1.244 self.new_op(AddressInstruction(self.get_builtin(name, node)))
1.245
1.246 - # Optimisation tests.
1.247 -
1.248 - def _should_optimise_constant_storage(self):
1.249 - return "constant_storage" in self.optimisations
1.250 -
1.251 - def _should_optimise_known_target(self):
1.252 - return "known_target" in self.optimisations
1.253 -
1.254 - def _should_optimise_self_access(self):
1.255 - return "self_access" in self.optimisations
1.256 -
1.257 - def _should_optimise_temp_storage(self):
1.258 - return "temp_storage" in self.optimisations
1.259 -
1.260 - # Simple tests.
1.261 -
1.262 - def _is_constant_input(self, instruction):
1.263 -
1.264 - "Return whether 'instruction' provides a constant input."
1.265 -
1.266 - return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 or \
1.267 - isinstance(instruction, LoadConst)
1.268 -
1.269 - def _is_constant_target(self, instruction):
1.270 -
1.271 - "Return whether 'instruction' provides a constant target."
1.272 -
1.273 - return isinstance(instruction, (StoreName, StoreAddress)) and \
1.274 - instruction.attr.assignments == 1
1.275 -
1.276 - def _is_local_input(self, instruction):
1.277 -
1.278 - "Return whether 'instruction' provides a local input."
1.279 -
1.280 - return isinstance(instruction, (LoadName, LoadTemp))
1.281 -
1.282 - # Convenience tests.
1.283 -
1.284 - def _have_constant_input(self):
1.285 -
1.286 - "Return whether the active instruction provides a constant input."
1.287 -
1.288 - return self._is_constant_input(self.active)
1.289 -
1.290 - _have_known_target = _have_constant_input
1.291 -
1.292 - def _have_self_input(self):
1.293 -
1.294 - "Return whether the active instruction is a reference to self."
1.295 -
1.296 - return isinstance(self.unit, Function) and \
1.297 - self.unit.is_method() and isinstance(self.active, LoadName) and \
1.298 - self.active.attr.name == "self"
1.299 -
1.300 - def _have_temp_compatible_access(self):
1.301 -
1.302 - """
1.303 - Indicate whether the active instruction can be used in place of access
1.304 - to a temporary variable retaining the result of the last instruction.
1.305 - """
1.306 -
1.307 - return isinstance(self.active, (LoadName, LoadTemp, LoadAddress, LoadConst))
1.308 -
1.309 - # Optimisation methods. See the supported_optimisations class attribute.
1.310 -
1.311 - def _optimise_temp_storage(self):
1.312 -
1.313 - """
1.314 - Where the next operation would involve storing a value into temporary
1.315 - storage at 'temp_position', record and remove any simple instruction
1.316 - which produced the value to be stored such that instead of subsequently
1.317 - accessing the temporary storage, that instruction is substituted.
1.318 -
1.319 - If no optimisation can be achieved, a StoreTemp instruction is produced
1.320 - and the appropriate LoadTemp instruction is returned.
1.321 -
1.322 - Restriction: for use only in situations where the source of the
1.323 - temporary data will not be disturbed between its first access and its
1.324 - subsequent use.
1.325 - """
1.326 -
1.327 - if self._should_optimise_temp_storage() and \
1.328 - self._have_temp_compatible_access():
1.329 -
1.330 - last = self.last_op()
1.331 - self.remove_op()
1.332 - return last
1.333 - else:
1.334 - return self.get_temp()
1.335 -
1.336 - def _optimise_constant_storage(self, instruction):
1.337 -
1.338 - """
1.339 - Where this operation should store a constant into a target which is
1.340 - also constant, optimise away both operations.
1.341 - """
1.342 -
1.343 - if self._should_optimise_constant_storage() and \
1.344 - self._is_constant_target(instruction) and \
1.345 - self._have_constant_input():
1.346 -
1.347 - self.remove_op()
1.348 - return 1
1.349 - else:
1.350 - return 0
1.351 -
1.352 - def _optimise_known_target(self):
1.353 -
1.354 - """
1.355 - Where the target of an invocation is known, provide information about it
1.356 - and its context. If a class is being invoked and the conditions are
1.357 - appropriate, get information about the specific initialiser.
1.358 - """
1.359 -
1.360 - if self._should_optimise_known_target() and self._have_known_target():
1.361 - last = self.last_op()
1.362 - target = last.attr.value
1.363 - context = last.attr.context
1.364 -
1.365 - # Handle calls to classes.
1.366 -
1.367 - if isinstance(target, Class):
1.368 - target = target.get_instantiator()
1.369 - context = Instance()
1.370 -
1.371 - # A special context is chosen to avoid generating unnecessary
1.372 - # context loading and checking instructions.
1.373 -
1.374 - return target, context
1.375 - else:
1.376 - return None
1.377 -
1.378 - def _optimise_self_access(self, attrname, classes):
1.379 -
1.380 - """
1.381 - Where the provided 'attrname' accesses an attribute which occupies the
1.382 - same position in all possible objects which can be accessed, generate an
1.383 - instruction using one of the given 'classes', accessing the attribute
1.384 - directly.
1.385 - """
1.386 -
1.387 - AddressInstruction, AddressContextInstruction, AttrInstruction = classes
1.388 -
1.389 - if self._should_optimise_self_access() and self._have_self_input() and \
1.390 - not self.unit.is_relocated(attrname):
1.391 -
1.392 - # Either generate an instruction operating on an instance attribute.
1.393 -
1.394 - try:
1.395 - attr = self.unit.parent.instance_attributes()[attrname]
1.396 - self.new_op(AttrInstruction(attr))
1.397 -
1.398 - # Or generate an instruction operating on a class attribute.
1.399 -
1.400 - except KeyError:
1.401 - attr = self.unit.parent.all_attributes()[attrname]
1.402 - new_attr = attr.via_instance()
1.403 - self.new_op(AddressContextInstruction(new_attr))
1.404 -
1.405 - return 1
1.406 - else:
1.407 - return 0
1.408 -
1.409 - # Visitor methods.
1.410 -
1.411 - def default(self, node, *args):
1.412 - raise TranslateError(self.module.full_name(), node, "Node class %r is not supported." % node.__class__)
1.413 -
1.414 - def dispatch(self, node, *args):
1.415 - return ASTVisitor.dispatch(self, node, *args)
1.416 -
1.417 def _visitUnary(self, node, method):
1.418
1.419 """
1.420 @@ -981,6 +1019,8 @@
1.421 self.discard_temp(temp1)
1.422 self.discard_temp(temp2)
1.423
1.424 + # Concrete visitor methods.
1.425 +
1.426 def visitAdd(self, node):
1.427 self._visitBinary(node, "__add__", "__radd__")
1.428
1.429 @@ -1003,20 +1043,25 @@
1.430
1.431 def visitAssign(self, node):
1.432 self.dispatch(node.expr)
1.433 - temp = self.get_temp()
1.434 + self.expr_temp = self._optimise_temp_storage()
1.435
1.436 for n in node.nodes:
1.437 self.dispatch(n)
1.438
1.439 - self.discard_temp(temp)
1.440 + self.discard_temp(self.expr_temp)
1.441 + self.expr_temp = None
1.442
1.443 def visitAssAttr(self, node):
1.444 self._visitAttr(node, self.attribute_store_instructions)
1.445 + if self.active is not None:
1.446 + self.active.source = self.expr_temp
1.447
1.448 def visitAssList(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "AssList")
1.449
1.450 def visitAssName(self, node):
1.451 self._visitName(node, (StoreName, StoreAddress))
1.452 + if self.active is not None:
1.453 + self.active.source = self.expr_temp
1.454
1.455 visitAssTuple = visitAssList
1.456
1.457 @@ -1360,13 +1405,13 @@
1.458
1.459 self.new_op(PushHandler(handler_label))
1.460 self.dispatch(node.body)
1.461 - self.new_op(PopHandler(handler_label))
1.462 + self.new_op(PopHandler())
1.463 self.new_op(Jump(exit_label))
1.464
1.465 # Start of handlers.
1.466
1.467 self.set_label(handler_label)
1.468 - self.new_op(PopHandler(handler_label))
1.469 + self.new_op(PopHandler())
1.470
1.471 for name, assignment, handler in node.handlers:
1.472 next_label = self.new_label()
2.1 --- a/micropython/rsvp.py Fri Jul 18 01:18:22 2008 +0200
2.2 +++ b/micropython/rsvp.py Sat Jul 19 00:39:50 2008 +0200
2.3 @@ -43,22 +43,33 @@
2.4
2.5 def __init__(self, attr=None):
2.6 self.attr = attr
2.7 + self.input = None
2.8 + self.source = None # for storage instructions
2.9
2.10 def copy(self):
2.11 return self.__class__(self.attr)
2.12
2.13 def __repr__(self):
2.14 if self.attr is not None:
2.15 - return "%s(%r)" % (self.__class__.__name__, self.attr)
2.16 + return "%s(%r)%s" % (self.__class__.__name__, self.attr, self.show_input())
2.17 else:
2.18 - return "%s()" % (self.__class__.__name__)
2.19 + return "%s()%s" % (self.__class__.__name__, self.show_input())
2.20 +
2.21 + def show_input(self):
2.22 + if self.input is not None:
2.23 + if self.source is not None:
2.24 + return " <- (%r, %r)" % (self.input, self.source)
2.25 + else:
2.26 + return " <- %r" % self.input
2.27 + else:
2.28 + return ""
2.29
2.30 class FrameRelativeInstruction(Instruction):
2.31
2.32 "An instruction operating on the current frame."
2.33
2.34 def __repr__(self):
2.35 - return "%s(%r)" % (self.__class__.__name__, self.get_operand())
2.36 + return "%s(%r)%s" % (self.__class__.__name__, self.get_operand(), self.show_input())
2.37
2.38 def get_operand(self):
2.39 return self.attr.position
2.40 @@ -72,9 +83,9 @@
2.41 def __repr__(self):
2.42 position = self.get_operand()
2.43 if position is not None:
2.44 - return "%s(%r) # %s" % (self.__class__.__name__, position, name(self.attr))
2.45 + return "%s(%r)%s # %s" % (self.__class__.__name__, position, self.show_input(), name(self.attr))
2.46 else:
2.47 - return "%s(%r)" % (self.__class__.__name__, name(self.attr))
2.48 + return "%s(%r)%s" % (self.__class__.__name__, name(self.attr), self.show_input())
2.49
2.50 def get_operand(self):
2.51 return self.attr.position
2.52 @@ -88,14 +99,14 @@
2.53 def __repr__(self):
2.54 location, position, result = self.get_operands()
2.55 if location is not None:
2.56 - return "%s(%r) # %r, %r (%s)" % (
2.57 - self.__class__.__name__, result, location, position, name(self.attr))
2.58 + return "%s(%r)%s # %r, %r (%s)" % (
2.59 + self.__class__.__name__, result, self.show_input(), location, position, name(self.attr))
2.60 elif result is not None:
2.61 - return "%s(%r) # %s" % (
2.62 - self.__class__.__name__, result, name(self.attr))
2.63 + return "%s(%r)%s # %s" % (
2.64 + self.__class__.__name__, result, self.show_input(), name(self.attr))
2.65 else:
2.66 - return "%s(...) # %s" % (
2.67 - self.__class__.__name__, name(self.attr))
2.68 + return "%s(...)%s # %s" % (
2.69 + self.__class__.__name__, self.show_input(), name(self.attr))
2.70
2.71 def get_operands(self):
2.72 if isinstance(self.attr, Attr):
2.73 @@ -126,7 +137,7 @@
2.74 "An instruction employing a constant."
2.75
2.76 def __repr__(self):
2.77 - return "%s(%r)" % (self.__class__.__name__, self.attr)
2.78 + return "%s(%r)%s" % (self.__class__.__name__, self.attr, self.show_input())
2.79
2.80 def get_operand(self):
2.81 return self.attr
2.82 @@ -188,7 +199,7 @@
2.83 class RaiseException(Instruction): "Raise an exception."
2.84 class CheckException(Instruction): "Check the raised exception against another."
2.85 class PushHandler(Address): "Push an exception handler onto the handler stack."
2.86 -class PopHandler(Address): "Pop an exception handler from the handler stack."
2.87 +class PopHandler(Instruction): "Pop an exception handler from the handler stack."
2.88
2.89 # General instructions.
2.90