1.1 --- a/micropython/ast.py Fri Sep 26 23:48:05 2008 +0200
1.2 +++ b/micropython/ast.py Sun Sep 28 03:30:03 2008 +0200
1.3 @@ -19,349 +19,19 @@
1.4 this program. If not, see <http://www.gnu.org/licenses/>.
1.5 """
1.6
1.7 +from micropython.opt import Optimiser
1.8 from micropython.common import *
1.9 from micropython.data import *
1.10 from micropython.rsvp import *
1.11 import compiler.ast
1.12 from compiler.visitor import ASTVisitor
1.13
1.14 -class Optimiser:
1.15 -
1.16 - "A code optimiser."
1.17 -
1.18 - supported_optimisations = [
1.19 - "constant_storage", "known_target", "self_access",
1.20 - "temp_storage", "load_operations", "no_operations",
1.21 - "unused_results"
1.22 - ]
1.23 -
1.24 - def __init__(self, translation, optimisations=None):
1.25 -
1.26 - """
1.27 - Provide for the given 'translation' an optimiser for the desired
1.28 - 'optimisations'. See the 'supported_optimisations' attribute of this
1.29 - class for permitted values.
1.30 - """
1.31 -
1.32 - self.translation = translation
1.33 - self.optimisations = set(optimisations or [])
1.34 -
1.35 - # Optimisation tests.
1.36 -
1.37 - def should_optimise_constant_storage(self):
1.38 - return "constant_storage" in self.optimisations
1.39 -
1.40 - def should_optimise_known_target(self):
1.41 - return "known_target" in self.optimisations
1.42 -
1.43 - def should_optimise_self_access(self):
1.44 - return "self_access" in self.optimisations
1.45 -
1.46 - def should_optimise_temp_storage(self):
1.47 - return "temp_storage" in self.optimisations
1.48 -
1.49 - def should_optimise_load_operations(self):
1.50 - return "load_operations" in self.optimisations
1.51 -
1.52 - def should_optimise_away_no_operations(self):
1.53 - return "no_operations" in self.optimisations
1.54 -
1.55 - def should_optimise_unused_results(self):
1.56 - return "unused_results" in self.optimisations
1.57 -
1.58 - # Simple tests.
1.59 -
1.60 - def is_constant_input(self, instruction):
1.61 -
1.62 - "Return whether 'instruction' provides a constant input."
1.63 -
1.64 - return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 or \
1.65 - isinstance(instruction, LoadConst)
1.66 -
1.67 - def is_constant_target(self, instruction):
1.68 -
1.69 - "Return whether 'instruction' provides a constant target."
1.70 -
1.71 - return isinstance(instruction, (StoreName, StoreAddress)) and \
1.72 - instruction.attr.assignments == 1
1.73 -
1.74 - def is_simple_input(self, instruction):
1.75 -
1.76 - """
1.77 - Return whether 'instruction' provides a simple input (typically a load
1.78 - instruction). A simple input is something which would be represented by
1.79 - a load operation from a CPU register or special memory location.
1.80 - """
1.81 -
1.82 - return isinstance(instruction, (LoadConst, LoadName, LoadTemp, LoadResult, LoadException, LoadAddress))
1.83 -
1.84 - def is_simple_input_user(self, instruction):
1.85 -
1.86 - """
1.87 - Return whether 'instruction' can use simple input from the current
1.88 - value. Such instructions would, in a low-level implementation, be able
1.89 - to have the simple input registers as operands.
1.90 - """
1.91 -
1.92 - return isinstance(instruction, (
1.93 - StoreTemp, StoreFrame, StoreResult, StoreException, # as the value being stored
1.94 - LoadAddressContext, LoadAttr, LoadAttrIndex, # as the object being referenced
1.95 - StoreAttr, StoreAttrIndex, StoreCallable, # as the object being referenced
1.96 - LoadCallable,
1.97 - TestIdentity, TestIdentityAddress, CheckSelf, # as one of the operands
1.98 - CheckException, CheckFrame, MakeObject,
1.99 - LoadContext # as the object providing the result
1.100 - ))
1.101 -
1.102 - def is_resultant_no_operation(self, instruction):
1.103 -
1.104 - """
1.105 - Return whether 'instruction' merely stores its input where the input
1.106 - originally came from.
1.107 - """
1.108 -
1.109 - return (
1.110 - isinstance(instruction.input, LoadTemp) and isinstance(instruction, StoreTemp) and
1.111 - instruction.input.attr == instruction.attr) or (
1.112 - isinstance(instruction.input, LoadResult) and isinstance(instruction, StoreResult)
1.113 - )
1.114 -
1.115 - def is_input(self, instruction):
1.116 -
1.117 - "Return whether 'instruction' provides an input."
1.118 -
1.119 - return isinstance(instruction, current_value_instructions)
1.120 -
1.121 - # Convenience tests on outputs.
1.122 -
1.123 - def have_constant_target(self):
1.124 -
1.125 - "Return whether the active instruction provides a constant target."
1.126 -
1.127 - return self.is_constant_target(self.translation.active)
1.128 -
1.129 - def have_constant_source(self):
1.130 -
1.131 - "Return whether the active instruction has a constant source."
1.132 -
1.133 - return self.is_constant_input(self.translation.active.source)
1.134 -
1.135 - # Convenience tests on inputs.
1.136 -
1.137 - def have_constant_input(self):
1.138 -
1.139 - "Return whether the active instruction provides a constant input."
1.140 -
1.141 - return self.is_constant_input(self.translation.active_value)
1.142 -
1.143 - have_known_target = have_constant_input
1.144 -
1.145 - def have_simple_input(self):
1.146 -
1.147 - "Return whether the active instruction provides a simple input."
1.148 -
1.149 - return self.is_simple_input(self.translation.active_value)
1.150 -
1.151 - def have_input(self):
1.152 -
1.153 - "Return whether the active instruction provides an input."
1.154 -
1.155 - return self.is_input(self.translation.active_value)
1.156 -
1.157 - def have_self_input(self):
1.158 -
1.159 - "Return whether the active instruction is a reference to self."
1.160 -
1.161 - return isinstance(self.translation.unit, Function) and \
1.162 - self.translation.unit.is_method() and isinstance(self.translation.active_value, LoadName) and \
1.163 - self.translation.active_value.attr.name == "self"
1.164 -
1.165 - def have_temp_compatible_access(self):
1.166 -
1.167 - """
1.168 - Indicate whether the active instruction can be used in place of access
1.169 - to a temporary variable retaining the result of the last instruction.
1.170 - """
1.171 -
1.172 - # LoadResult cannot be relied upon in general since the result register
1.173 - # could be updated since first being referenced.
1.174 -
1.175 - return isinstance(self.translation.active_value, (LoadName, LoadTemp, LoadAddress, LoadConst)) or \
1.176 - isinstance(self.translation.active_value, LoadResult) and self.translation.active_value is self.translation.active or \
1.177 - isinstance(self.translation.active_value, LoadException) and self.translation.active_value is self.translation.active
1.178 -
1.179 - def have_correct_self_for_target(self, context):
1.180 -
1.181 - "Return whether the 'context' is compatible with the current value."
1.182 -
1.183 - if context is not None and self.have_self_input():
1.184 -
1.185 - parent = self.translation.unit.parent
1.186 - if parent is context or parent.has_subclass(context) or context.has_subclass(parent):
1.187 - return 1
1.188 -
1.189 - return 0
1.190 -
1.191 - # Optimisation methods. See the supported_optimisations class attribute.
1.192 -
1.193 - def optimise_constant_storage(self):
1.194 -
1.195 - """
1.196 - Where the last operation stores a constant into a target which is also
1.197 - constant, optimise away both operations.
1.198 - """
1.199 -
1.200 - if self.should_optimise_constant_storage() and \
1.201 - self.have_constant_target() and \
1.202 - self.have_constant_source():
1.203 -
1.204 - self.translation.remove_op()
1.205 - return 1
1.206 - else:
1.207 - return 0
1.208 -
1.209 - def optimise_known_target(self):
1.210 -
1.211 - """
1.212 - Where the target of an invocation is known, provide information about it
1.213 - and its context. If a class is being invoked and the conditions are
1.214 - appropriate, get information about the specific initialiser.
1.215 - """
1.216 -
1.217 - if self.should_optimise_known_target() and self.have_known_target():
1.218 - last = self.translation.active_value
1.219 - target = last.attr.value
1.220 - context = last.attr.context
1.221 -
1.222 - return target, context
1.223 - else:
1.224 - return None
1.225 -
1.226 - def optimise_self_access(self, attrname, classes, node):
1.227 -
1.228 - """
1.229 - Where the provided 'attrname' accesses an attribute which occupies the
1.230 - same position in all possible objects which can be accessed, generate an
1.231 - instruction using one of the given 'classes', accessing the attribute
1.232 - directly.
1.233 - """
1.234 -
1.235 - AddressInstruction, AddressContextInstruction, AttrInstruction = classes
1.236 -
1.237 - if self.should_optimise_self_access() and self.have_self_input() and \
1.238 - not self.translation.unit.is_relocated(attrname):
1.239 -
1.240 - # Either generate an instruction operating on an instance attribute.
1.241 -
1.242 - try:
1.243 - attr = self.translation.unit.parent.instance_attributes()[attrname]
1.244 - self.translation.new_op(AttrInstruction(attr))
1.245 -
1.246 - # Or generate an instruction operating on a class attribute.
1.247 -
1.248 - except KeyError:
1.249 - attr = self.translation.unit.parent.all_attributes()[attrname]
1.250 -
1.251 - # Switch the context if the class attribute is compatible with
1.252 - # the instance.
1.253 -
1.254 - if attr.defined_within_hierarchy():
1.255 -
1.256 - # Only permit loading (not storing) of class attributes via self.
1.257 -
1.258 - if AddressContextInstruction is not None:
1.259 - self.translation.new_op(AddressContextInstruction(attr))
1.260 - else:
1.261 - raise TranslateError(self.translation.module.full_name(), node,
1.262 - "Storing of class attribute %r via self not permitted." % attrname)
1.263 -
1.264 - # Preserve the context if the class attribute comes from an
1.265 - # incompatible class.
1.266 -
1.267 - else:
1.268 - if AddressInstruction is not None:
1.269 - self.translation.new_op(AddressInstruction(attr))
1.270 - else:
1.271 - raise TranslateError(self.translation.module.full_name(), node,
1.272 - "Storing of class attribute %r via self not permitted." % attrname)
1.273 -
1.274 - return 1
1.275 - else:
1.276 - return 0
1.277 -
1.278 - def optimise_temp_storage(self):
1.279 -
1.280 - """
1.281 - Where the next operation would involve storing a value into temporary
1.282 - storage at 'temp_position', record and remove any simple instruction
1.283 - which produced the value to be stored such that instead of subsequently
1.284 - accessing the temporary storage, that instruction is substituted.
1.285 -
1.286 - If no optimisation can be achieved, a StoreTemp instruction is produced
1.287 - and the appropriate LoadTemp instruction is returned.
1.288 -
1.289 - Restriction: for use only in situations where the source of the
1.290 - temporary data will not be disturbed between its first access and its
1.291 - subsequent use.
1.292 - """
1.293 -
1.294 - if self.should_optimise_temp_storage() and \
1.295 - self.have_temp_compatible_access():
1.296 -
1.297 - # Remove the active value contributor.
1.298 -
1.299 - removed = self.translation.active
1.300 - self.translation.remove_active_value()
1.301 -
1.302 - # Extend the lifetime of any temporary storage location.
1.303 -
1.304 - self.translation.ensure_temp(removed)
1.305 - return removed
1.306 - else:
1.307 - return self.translation.get_temp()
1.308 -
1.309 - def optimise_load_operations(self, instruction):
1.310 -
1.311 - """
1.312 - Incorporate previous load operations into other operations.
1.313 - """
1.314 -
1.315 - if self.should_optimise_load_operations() and \
1.316 - self.have_simple_input() and \
1.317 - self.is_simple_input_user(instruction):
1.318 -
1.319 - self.translation.remove_active_value()
1.320 - instruction.input = self.translation.active_value
1.321 -
1.322 - def optimise_away_no_operations(self, instruction):
1.323 -
1.324 - """
1.325 - Optimise away operations which just store their inputs in the place
1.326 - the inputs originally came from.
1.327 - """
1.328 -
1.329 - if self.should_optimise_away_no_operations() and \
1.330 - self.is_resultant_no_operation(instruction):
1.331 -
1.332 - return 1
1.333 - else:
1.334 - return 0
1.335 -
1.336 - def optimise_unused_results(self):
1.337 -
1.338 - "Discard results which will not be used."
1.339 -
1.340 - if self.should_optimise_unused_results() and self.have_simple_input():
1.341 - self.translation.remove_active_value()
1.342 -
1.343 # Program visitors.
1.344
1.345 class Translation(ASTVisitor):
1.346
1.347 "A translated module."
1.348
1.349 - supported_optimisations = Optimiser.supported_optimisations
1.350 -
1.351 # Attribute access instructions, for use with the appropriate handlers.
1.352
1.353 attribute_load_instructions = (LoadAddress, LoadAddressContext, LoadAttr, LoadAttrIndex)
1.354 @@ -376,8 +46,7 @@
1.355
1.356 """
1.357 Initialise the translation with an inspected 'module', the 'importer'
1.358 - and optional 'optimisations'. See the 'supported_optimisations'
1.359 - attribute of this class for permitted values.
1.360 + and optional 'optimisations'.
1.361 """
1.362
1.363 ASTVisitor.__init__(self)
1.364 @@ -399,13 +68,6 @@
1.365
1.366 self.unit = None
1.367
1.368 - # The current "active" instruction.
1.369 - # As a rule, this will become the last instruction, but some
1.370 - # control-flow operations will flush the "active" instruction.
1.371 -
1.372 - self.active = None
1.373 - self.active_value = None
1.374 -
1.375 # The temporary storage used by the current assignment expression.
1.376
1.377 self.expr_temp = []
1.378 @@ -607,8 +269,7 @@
1.379 self.discard_temp(self.expr_temp.pop())
1.380
1.381 def set_source(self):
1.382 - if self.active is not None:
1.383 - self.active.source = self.expr_temp[-1]
1.384 + self.optimiser.set_source(self.expr_temp[-1])
1.385
1.386 # Optimise away constant storage if appropriate.
1.387
1.388 @@ -669,26 +330,14 @@
1.389 return
1.390
1.391 self.code.append(op)
1.392 - self.active = op
1.393 -
1.394 - # Record specific types of instructions for optimisation.
1.395 -
1.396 - if isinstance(op, current_value_instructions):
1.397 - self.active_value = op
1.398 + self.optimiser.set_new(op)
1.399
1.400 def remove_op(self):
1.401
1.402 "Remove the last instruction."
1.403
1.404 op = self.code.pop()
1.405 - self.active = None
1.406 -
1.407 - def remove_active_value(self):
1.408 -
1.409 - "Remove the value-providing active instruction if appropriate."
1.410 -
1.411 - if self.active_value is self.active:
1.412 - self.remove_op()
1.413 + self.optimiser.clear_active()
1.414
1.415 def replace_op(self, op):
1.416
1.417 @@ -703,7 +352,7 @@
1.418 Replace the value-providing active instruction with 'op' if appropriate.
1.419 """
1.420
1.421 - self.remove_active_value()
1.422 + self.optimiser.remove_active_value()
1.423 self.new_op(op)
1.424
1.425 def last_op(self):
1.426 @@ -715,13 +364,6 @@
1.427 except IndexError:
1.428 return None
1.429
1.430 - def clear_active(self):
1.431 -
1.432 - "Prevent incorrect optimisation."
1.433 -
1.434 - self.active = None
1.435 - self.active_value = None
1.436 -
1.437 # Visitor methods.
1.438
1.439 def default(self, node, *args):
1.440 @@ -754,7 +396,7 @@
1.441 # constant...
1.442
1.443 if self.optimiser.have_constant_input():
1.444 - last = self.active_value
1.445 + last = self.optimiser.active_value
1.446
1.447 # Get the details of the access.
1.448
1.449 @@ -1041,7 +683,7 @@
1.450
1.451 continue_label = self.new_label()
1.452 self.new_op(CheckSelf())
1.453 - self.active.source = temp
1.454 + self.optimiser.set_source(temp)
1.455 self.new_op(JumpIfTrue(continue_label))
1.456
1.457 # Where the context is inappropriate, drop the incomplete frame and
1.458 @@ -1301,7 +943,7 @@
1.459
1.460 # Prevent incorrect optimisation.
1.461
1.462 - self.clear_active()
1.463 + self.optimiser.reset()
1.464
1.465 self.set_label(end_label)
1.466
1.467 @@ -1386,7 +1028,7 @@
1.468
1.469 # Prevent incorrect optimisation.
1.470
1.471 - self.clear_active()
1.472 + self.optimiser.reset()
1.473
1.474 self.set_label(end_label)
1.475 return temp_out
1.476 @@ -1538,7 +1180,7 @@
1.477
1.478 # Prevent incorrect optimisation.
1.479
1.480 - self.clear_active()
1.481 + self.optimiser.reset()
1.482
1.483 self.new_op(temp)
1.484 self.discard_temp(temp)
1.485 @@ -2050,7 +1692,7 @@
1.486
1.487 # Prevent incorrect optimisation.
1.488
1.489 - self.clear_active()
1.490 + self.optimiser.reset()
1.491
1.492 def visitOr(self, node):
1.493 end_label = self.new_label()
1.494 @@ -2071,7 +1713,7 @@
1.495
1.496 # Prevent incorrect optimisation.
1.497
1.498 - self.clear_active()
1.499 + self.optimiser.reset()
1.500
1.501 self.new_op(temp)
1.502 self.discard_temp(temp)
1.503 @@ -2231,7 +1873,7 @@
1.504
1.505 # Prevent incorrect optimisation.
1.506
1.507 - self.clear_active()
1.508 + self.optimiser.reset()
1.509
1.510 def visitWith(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "With")
1.511