1.1 --- a/micropython/opt.py Fri Jun 28 21:17:02 2013 +0200
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,538 +0,0 @@
1.4 -#!/usr/bin/env python
1.5 -
1.6 -"""
1.7 -Optimise code produced by the AST translator.
1.8 -
1.9 -Copyright (C) 2007, 2008, 2009, 2010, 2011 Paul Boddie <paul@boddie.org.uk>
1.10 -
1.11 -This program is free software; you can redistribute it and/or modify it under
1.12 -the terms of the GNU General Public License as published by the Free Software
1.13 -Foundation; either version 3 of the License, or (at your option) any later
1.14 -version.
1.15 -
1.16 -This program is distributed in the hope that it will be useful, but WITHOUT
1.17 -ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.18 -FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
1.19 -details.
1.20 -
1.21 -You should have received a copy of the GNU General Public License along with
1.22 -this program. If not, see <http://www.gnu.org/licenses/>.
1.23 -"""
1.24 -
1.25 -from micropython.common import *
1.26 -from micropython.data import *
1.27 -from micropython.rsvp import *
1.28 -
1.29 -class Optimiser:
1.30 -
1.31 - "A code optimiser."
1.32 -
1.33 - supported_optimisations = [
1.34 - # Code generation optimisations:
1.35 - "constant_storage", "constant_accessor", "known_target", "self_access",
1.36 - "temp_storage", "no_operations", "unused_results",
1.37 - "unused_handlers", "accesses_by_usage",
1.38 - # Inspection optimisations:
1.39 - "unused_objects"
1.40 - ]
1.41 -
1.42 - def __init__(self, translation, optimisations=None):
1.43 -
1.44 - """
1.45 - Provide for the given 'translation' an optimiser for the desired
1.46 - 'optimisations'. See the 'supported_optimisations' attribute of this
1.47 - class for permitted values.
1.48 - """
1.49 -
1.50 - self.translation = translation
1.51 - self.optimisations = set(optimisations or [])
1.52 -
1.53 - # The current "active" instruction.
1.54 - # As a rule, this will become the last instruction, but some
1.55 - # control-flow operations will flush the "active" instruction.
1.56 -
1.57 - self.active = None
1.58 -
1.59 - # Information about instructions providing the active values for
1.60 - # registers.
1.61 -
1.62 - self.saved_value_op = {}
1.63 - self.saved_value_block = {}
1.64 - self.saved_value_pos = {}
1.65 -
1.66 - # Sets of instructions providing the active value for each register.
1.67 -
1.68 - self.active_values = {}
1.69 -
1.70 - def get_attribute_store_instructions(self):
1.71 -
1.72 - """
1.73 - Return an appropriate set of instructions available when storing
1.74 - attributes.
1.75 - """
1.76 -
1.77 - ca = self.should_optimise_accesses_by_attribute_usage()
1.78 -
1.79 - return (
1.80 - ca and StoreAddress or None, # plain assignment
1.81 - ca and StoreAddressContext or None, # assignment via class
1.82 - ca and StoreAddressContext or None, # assignment via class (never via instance)
1.83 - StoreAttr, # assignment via instance
1.84 - StoreAttrIndex, # special assignment via instance
1.85 - None
1.86 - )
1.87 -
1.88 - def reset(self, block=None, blocks=None):
1.89 -
1.90 - """
1.91 - Reset the optimiser for the given 'block' (or the current block),
1.92 - clearing the active value instructions if no 'blocks' are given, or
1.93 - collecting the active instructions from each of the blocks otherwise.
1.94 - """
1.95 -
1.96 - self.store_active_values()
1.97 - self.clear_active()
1.98 -
1.99 - # Make a new collection of instructions for a new block.
1.100 -
1.101 - if block:
1.102 - self.active_values = {}
1.103 - block.set_active_values(self.active_values)
1.104 -
1.105 - # Otherwise, clear the collection for an existing block.
1.106 -
1.107 - else:
1.108 - self.active_values.clear()
1.109 -
1.110 - if blocks:
1.111 - for b in blocks:
1.112 - self.active_values.update(b.get_active_values())
1.113 -
1.114 - def set_new(self, register, op):
1.115 -
1.116 - "For 'register', set the latest 'op' as the active instruction."
1.117 -
1.118 - self.set_active(op)
1.119 - self.set_active_value(register, op)
1.120 -
1.121 - def set_active_value(self, register, op):
1.122 -
1.123 - "For 'register', set 'op' as the value-providing active instruction."
1.124 -
1.125 - # Since the current value provider may eventually be used, it needs to
1.126 - # store its output if appropriate.
1.127 -
1.128 - self.store_active_value(register)
1.129 - self.active_values[register] = set([op])
1.130 -
1.131 - def get_active_value(self, register):
1.132 -
1.133 - """
1.134 - Get any single active value for the given 'register' or None if none or
1.135 - more than one exist.
1.136 - """
1.137 -
1.138 - if self.active_values.has_key(register) and \
1.139 - len(self.active_values[register]) == 1:
1.140 -
1.141 - return list(self.active_values[register])[0]
1.142 -
1.143 - else:
1.144 - return None
1.145 -
1.146 - def remove_active_value(self, register):
1.147 -
1.148 - """
1.149 - Remove the active instruction providing 'register' with its value from
1.150 - the generated code, if appropriate, and return the active instruction.
1.151 - """
1.152 -
1.153 - if self.active_values.has_key(register) and \
1.154 - self.active in self.active_values[register]:
1.155 -
1.156 - removed = self.translation.remove_op()
1.157 - self.active_values[register].remove(removed)
1.158 - return removed
1.159 -
1.160 - else:
1.161 - return None
1.162 -
1.163 - def set_target(self, register, target):
1.164 -
1.165 - """
1.166 - Set the target of the active instruction involving 'register' to
1.167 - 'target'.
1.168 - """
1.169 -
1.170 - if self.active_values.has_key(register):
1.171 - for expr in self.active_values[register]:
1.172 - expr.target = target
1.173 -
1.174 - # Transfer the active instructions to their new target.
1.175 -
1.176 - if not self.active_values.has_key(target):
1.177 - self.active_values[target] = self.active_values[register]
1.178 - else:
1.179 - self.active_values[target].update(self.active_values[register])
1.180 -
1.181 - # Remove the association between the instructions and the specified
1.182 - # register.
1.183 -
1.184 - del self.active_values[register]
1.185 -
1.186 - def set_active(self, op):
1.187 -
1.188 - "Set the active instruction."
1.189 -
1.190 - self.active = op
1.191 -
1.192 - def clear_active(self):
1.193 -
1.194 - "Clear the active instructions."
1.195 -
1.196 - self.active = None
1.197 -
1.198 - # Permit the active value to be requested and restored.
1.199 -
1.200 - def request_active_value(self, register, temp, block, pos):
1.201 -
1.202 - """
1.203 - Request the current active value for 'register' so that if the value is
1.204 - changed, a temporary storage element or equivalent will be allocated.
1.205 - """
1.206 -
1.207 - # Cause any previously active value for the register to be saved.
1.208 -
1.209 - self.store_active_value(register)
1.210 -
1.211 - # Redefine the active value for the register.
1.212 -
1.213 - self.saved_value_op[register] = temp
1.214 - self.saved_value_block[register] = block
1.215 - self.saved_value_pos[register] = pos
1.216 -
1.217 - def store_active_values(self):
1.218 -
1.219 - "Store all active values."
1.220 -
1.221 - for register in self.active_values.keys():
1.222 - self.store_active_value(register)
1.223 -
1.224 - def store_active_value(self, register):
1.225 -
1.226 - "Store the requested active value for 'register'."
1.227 -
1.228 - if self.saved_value_op.has_key(register):
1.229 -
1.230 - # Cause an instruction to be inserted to store the active value for
1.231 - # the register, thus keeping it available for any subsequent usage.
1.232 -
1.233 - self.translation.set_temp(
1.234 - self.saved_value_op[register], # cause the storage of the value
1.235 - self.saved_value_block[register], # in the appropriate block
1.236 - self.saved_value_pos[register] # at the appropriate location
1.237 - )
1.238 -
1.239 - # Discard the existing active value information.
1.240 -
1.241 - self.ignore_active_value(register)
1.242 -
1.243 - def ignore_active_value(self, register):
1.244 -
1.245 - "Ignore the active value in 'register'."
1.246 -
1.247 - if self.saved_value_op.has_key(register):
1.248 - del self.saved_value_op[register]
1.249 - del self.saved_value_block[register]
1.250 - del self.saved_value_pos[register]
1.251 -
1.252 - # Optimisation tests.
1.253 -
1.254 - def should_optimise_constant_storage(self):
1.255 - return "constant_storage" in self.optimisations
1.256 -
1.257 - def should_optimise_constant_accessor(self):
1.258 - return "constant_accessor" in self.optimisations
1.259 -
1.260 - def should_optimise_known_target(self):
1.261 - return "known_target" in self.optimisations
1.262 -
1.263 - def should_optimise_self_access(self):
1.264 - return "self_access" in self.optimisations
1.265 -
1.266 - def should_optimise_temp_storage(self):
1.267 - return "temp_storage" in self.optimisations
1.268 -
1.269 - def should_optimise_away_no_operations(self):
1.270 - return "no_operations" in self.optimisations
1.271 -
1.272 - def should_optimise_unused_results(self):
1.273 - return "unused_results" in self.optimisations
1.274 -
1.275 - def should_optimise_unused_handlers(self):
1.276 - return "unused_handlers" in self.optimisations
1.277 -
1.278 - def should_optimise_accesses_by_attribute_usage(self):
1.279 - return "accesses_by_usage" in self.optimisations
1.280 -
1.281 - # Simple tests.
1.282 -
1.283 - def is_constant_input(self, instruction):
1.284 -
1.285 - "Return whether 'instruction' provides a constant input."
1.286 -
1.287 - return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 and \
1.288 - isinstance(instruction.attr.get_value(), Constant) or \
1.289 - isinstance(instruction, (LoadConst, LoadClass, LoadFunction))
1.290 -
1.291 - def is_constant_target(self, instruction):
1.292 -
1.293 - "Return whether 'instruction' provides a constant target."
1.294 -
1.295 - # NOTE: Removed StoreName, since this would then demand population of
1.296 - # NOTE: locals/frames.
1.297 -
1.298 - return isinstance(instruction, (StoreAddress, StoreAddressContext)) and \
1.299 - instruction.attr.is_constant() and \
1.300 - instruction.attr.is_strict_constant()
1.301 -
1.302 - def is_simple_input(self, instruction):
1.303 -
1.304 - """
1.305 - Return whether 'instruction' provides a simple input (typically a load
1.306 - instruction). A simple input is something which would be represented by
1.307 - a load operation from a CPU register or special memory location.
1.308 - """
1.309 -
1.310 - return isinstance(instruction, (LoadConst, LoadClass, LoadFunction,
1.311 - LoadName, LoadTemp, LoadAddress
1.312 - ))
1.313 -
1.314 - def is_resultant_no_operation(self, instruction, last_op=None):
1.315 -
1.316 - """
1.317 - Return whether 'instruction' merely stores its input where the input
1.318 - originally came from.
1.319 - """
1.320 -
1.321 - last_op = last_op or self.translation.last_op()
1.322 - return last_op and last_op.attr == instruction.attr and (
1.323 - isinstance(instruction, StoreTemp) and isinstance(last_op, LoadTemp) or
1.324 - isinstance(instruction, StoreAddress) and isinstance(last_op, LoadAddress) or
1.325 - last_op.source == instruction.target and (
1.326 - isinstance(instruction, LoadTemp) and isinstance(last_op, StoreTemp) or
1.327 - isinstance(instruction, LoadAddress) and isinstance(last_op, StoreAddress)
1.328 - ))
1.329 -
1.330 - # Convenience tests on outputs.
1.331 -
1.332 - def have_constant_target(self):
1.333 -
1.334 - "Return whether the active instruction provides a constant target."
1.335 -
1.336 - return self.is_constant_target(self.active)
1.337 -
1.338 - def have_constant_source(self, expr):
1.339 -
1.340 - "Return whether the active assignment source instruction is constant."
1.341 -
1.342 - return self.is_constant_input(expr)
1.343 -
1.344 - # Convenience tests on inputs.
1.345 -
1.346 - def have_constant_input(self):
1.347 -
1.348 - "Return whether the active instruction provides a constant input."
1.349 -
1.350 - return self.get_active_value("working") and self.is_constant_input(self.get_active_value("working"))
1.351 -
1.352 - def have_simple_input(self):
1.353 -
1.354 - "Return whether the active instruction provides a simple input."
1.355 -
1.356 - return self.get_active_value("working") and self.is_simple_input(self.get_active_value("working"))
1.357 -
1.358 - # Indicate whether the active instruction can be used in place of access
1.359 - # to a temporary variable retaining the result of the last instruction.
1.360 -
1.361 - have_temp_compatible_access = have_simple_input
1.362 -
1.363 - def have_self_input(self, unit):
1.364 -
1.365 - """
1.366 - Return whether the active instruction is a reference to self in the
1.367 - given 'unit'.
1.368 - """
1.369 -
1.370 - if not (isinstance(unit, Function) and unit.is_method()):
1.371 - return False
1.372 -
1.373 - expr = self.get_active_value("working")
1.374 - return expr and isinstance(expr, LoadName) and expr.attr.name == "self"
1.375 -
1.376 - def have_correct_self_for_target(self, context, unit):
1.377 -
1.378 - "Return whether the 'context' is compatible with the given 'unit'."
1.379 -
1.380 - if context is not None and self.have_self_input(unit):
1.381 -
1.382 - parent = unit.parent
1.383 - if parent is context or parent.has_subclass(context) or context.has_subclass(parent):
1.384 - return True
1.385 -
1.386 - return False
1.387 -
1.388 - def have_empty_handler(self, instruction):
1.389 -
1.390 - """
1.391 - Return whether the active instruction defined a handler for exceptions
1.392 - which is then discarded by the given 'instruction'.
1.393 - """
1.394 -
1.395 - return isinstance(self.translation.last_op(), PushHandler) and isinstance(instruction, PopHandler)
1.396 -
1.397 - # Optimisation methods. See the supported_optimisations class attribute.
1.398 -
1.399 - def optimise_constant_storage(self, expr):
1.400 -
1.401 - """
1.402 - Where the last operation stores a constant into a target which is also
1.403 - constant, indicate that both operations should be optimised away.
1.404 - """
1.405 -
1.406 - return self.should_optimise_constant_storage() and \
1.407 - self.have_constant_target() and \
1.408 - self.have_constant_source(expr)
1.409 -
1.410 - def optimise_constant_accessor(self):
1.411 -
1.412 - """
1.413 - Where the object whose attribute is being accessed is constant, provide
1.414 - information about the object and its full name.
1.415 - """
1.416 -
1.417 - if self.should_optimise_constant_accessor() and self.have_constant_input():
1.418 - value = self.get_active_value("working")
1.419 -
1.420 - # Get the details of the access.
1.421 -
1.422 - if isinstance(value.attr, Const):
1.423 - return value.attr, value.attr.value_type_name()
1.424 - else:
1.425 - target = value.attr.get_value()
1.426 -
1.427 - if target is None:
1.428 - return None # no clearly defined target
1.429 - elif isinstance(target, Const):
1.430 - return target, target.value_type_name()
1.431 - elif isinstance(target, Instance):
1.432 - return None # skip production of optimised code
1.433 - else:
1.434 - return target, target.full_name()
1.435 -
1.436 - else:
1.437 - return None
1.438 -
1.439 - def optimise_known_target(self):
1.440 -
1.441 - """
1.442 - Where the target of an invocation is known, provide information about it
1.443 - and its context. If a class is being invoked and the conditions are
1.444 - appropriate, get information about the specific initialiser.
1.445 - """
1.446 -
1.447 - if self.should_optimise_known_target() and self.have_constant_input():
1.448 - value = self.get_active_value("working")
1.449 - target = value.attr.get_value()
1.450 - context = value.attr.get_context()
1.451 -
1.452 - # Return target details only if this is clearly defined.
1.453 -
1.454 - if target is not None:
1.455 - return target, context
1.456 -
1.457 - return None
1.458 -
1.459 - def optimise_self_access(self, unit, attrname):
1.460 -
1.461 - """
1.462 - Return whether code in the given 'unit' is able to access the given
1.463 - 'attrname' through the same position in all possible objects which might
1.464 - be accessed.
1.465 - """
1.466 -
1.467 - return self.should_optimise_self_access() and \
1.468 - self.have_self_input(unit) and not unit.is_relocated(attrname)
1.469 -
1.470 - def optimise_temp_storage(self):
1.471 -
1.472 - """
1.473 - Where the next operation would involve storing a value into temporary
1.474 - storage, record and remove any simple instruction which produced the
1.475 - value to be stored such that instead of subsequently accessing the
1.476 - temporary storage, that instruction is substituted.
1.477 -
1.478 - If no optimisation can be achieved, temporary storage is requested
1.479 - and the appropriate LoadTemp instruction is returned.
1.480 -
1.481 - Restriction: for use only in situations where the source of the
1.482 - temporary data will not be disturbed between its first access and its
1.483 - subsequent use.
1.484 - """
1.485 -
1.486 - if self.should_optimise_temp_storage():
1.487 -
1.488 - # Emitted instructions can be obtained.
1.489 -
1.490 - if self.have_temp_compatible_access():
1.491 -
1.492 - # Remove the active value contributor if possible.
1.493 -
1.494 - removed = self.remove_active_value("working")
1.495 - if removed is not None:
1.496 -
1.497 - # Extend the lifetime of any temporary storage location.
1.498 -
1.499 - self.translation.ensure_temp(removed)
1.500 - return removed
1.501 -
1.502 - # Otherwise, just leave it in place, but return the instruction.
1.503 -
1.504 - else:
1.505 - return self.get_active_value("working")
1.506 -
1.507 - # Or provisional temporary instructions.
1.508 -
1.509 - elif self.saved_value_op.has_key("working"):
1.510 - return self.saved_value_op["working"]
1.511 -
1.512 - return self.translation.get_temp()
1.513 -
1.514 - def optimise_away_no_operations(self, instruction, last_op=None):
1.515 -
1.516 - """
1.517 - Optimise away operations which just store their inputs in the place
1.518 - the inputs originally came from.
1.519 - """
1.520 -
1.521 - return self.should_optimise_away_no_operations() and \
1.522 - self.is_resultant_no_operation(instruction, last_op)
1.523 -
1.524 - def optimise_unused_results(self):
1.525 -
1.526 - "Discard results which will not be used."
1.527 -
1.528 - if self.should_optimise_unused_results() and self.have_simple_input():
1.529 - self.remove_active_value("working")
1.530 -
1.531 - def optimise_unused_handlers(self, instruction):
1.532 -
1.533 - "Discard handlers which will not be used."
1.534 -
1.535 - if self.should_optimise_unused_handlers() and self.have_empty_handler(instruction):
1.536 - self.translation.remove_op()
1.537 - return True
1.538 - else:
1.539 - return False
1.540 -
1.541 -# vim: tabstop=4 expandtab shiftwidth=4