1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/micropython/opt.py Sun Sep 28 03:30:03 2008 +0200
1.3 @@ -0,0 +1,420 @@
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 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.rsvp import *
1.27 +
1.28 +class Optimiser:
1.29 +
1.30 + "A code optimiser."
1.31 +
1.32 + supported_optimisations = [
1.33 + "constant_storage", "known_target", "self_access",
1.34 + "temp_storage", "load_operations", "no_operations",
1.35 + "unused_results"
1.36 + ]
1.37 +
1.38 + def __init__(self, translation, optimisations=None):
1.39 +
1.40 + """
1.41 + Provide for the given 'translation' an optimiser for the desired
1.42 + 'optimisations'. See the 'supported_optimisations' attribute of this
1.43 + class for permitted values.
1.44 + """
1.45 +
1.46 + self.translation = translation
1.47 + self.optimisations = set(optimisations or [])
1.48 +
1.49 + # The current "active" instruction.
1.50 + # As a rule, this will become the last instruction, but some
1.51 + # control-flow operations will flush the "active" instruction.
1.52 +
1.53 + self.active = None
1.54 +
1.55 + # The instruction providing the active value.
1.56 +
1.57 + self.active_value = None
1.58 +
1.59 + def reset(self):
1.60 +
1.61 + "Reset the optimiser, clearing the active instructions."
1.62 +
1.63 + self.clear_active_value()
1.64 + self.clear_active()
1.65 +
1.66 + def set_new(self, op):
1.67 +
1.68 + "Set the latest 'op' as the active instruction."
1.69 +
1.70 + self.set_active(op)
1.71 + self.set_active_value(op)
1.72 +
1.73 + def set_active_value(self, op):
1.74 +
1.75 + "Set the value-providing active instruction."
1.76 +
1.77 + if isinstance(op, current_value_instructions):
1.78 + self.active_value = op
1.79 +
1.80 + def clear_active_value(self):
1.81 +
1.82 + "Clear the value-providing active instruction."
1.83 +
1.84 + self.active_value = None
1.85 +
1.86 + def remove_active_value(self):
1.87 +
1.88 + "Remove the value-providing active instruction if appropriate."
1.89 +
1.90 + if self.active_value is self.active:
1.91 + removed = self.active
1.92 + self.translation.remove_op()
1.93 + return removed
1.94 + else:
1.95 + return None
1.96 +
1.97 + def set_source(self, expr):
1.98 +
1.99 + "Set the source of the active instruction to 'expr'."
1.100 +
1.101 + if self.active is not None:
1.102 + self.active.source = expr
1.103 +
1.104 + def set_active(self, op):
1.105 +
1.106 + "Set the active instruction."
1.107 +
1.108 + self.active = op
1.109 +
1.110 + def clear_active(self):
1.111 +
1.112 + "Clear the active instruction."
1.113 +
1.114 + self.active = None
1.115 +
1.116 + # Optimisation tests.
1.117 +
1.118 + def should_optimise_constant_storage(self):
1.119 + return "constant_storage" in self.optimisations
1.120 +
1.121 + def should_optimise_known_target(self):
1.122 + return "known_target" in self.optimisations
1.123 +
1.124 + def should_optimise_self_access(self):
1.125 + return "self_access" in self.optimisations
1.126 +
1.127 + def should_optimise_temp_storage(self):
1.128 + return "temp_storage" in self.optimisations
1.129 +
1.130 + def should_optimise_load_operations(self):
1.131 + return "load_operations" in self.optimisations
1.132 +
1.133 + def should_optimise_away_no_operations(self):
1.134 + return "no_operations" in self.optimisations
1.135 +
1.136 + def should_optimise_unused_results(self):
1.137 + return "unused_results" in self.optimisations
1.138 +
1.139 + # Simple tests.
1.140 +
1.141 + def is_constant_input(self, instruction):
1.142 +
1.143 + "Return whether 'instruction' provides a constant input."
1.144 +
1.145 + return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 or \
1.146 + isinstance(instruction, LoadConst)
1.147 +
1.148 + def is_constant_target(self, instruction):
1.149 +
1.150 + "Return whether 'instruction' provides a constant target."
1.151 +
1.152 + return isinstance(instruction, (StoreName, StoreAddress)) and \
1.153 + instruction.attr.assignments == 1
1.154 +
1.155 + def is_simple_input(self, instruction):
1.156 +
1.157 + """
1.158 + Return whether 'instruction' provides a simple input (typically a load
1.159 + instruction). A simple input is something which would be represented by
1.160 + a load operation from a CPU register or special memory location.
1.161 + """
1.162 +
1.163 + return isinstance(instruction, (LoadConst, LoadName, LoadTemp, LoadResult, LoadException, LoadAddress))
1.164 +
1.165 + def is_simple_input_user(self, instruction):
1.166 +
1.167 + """
1.168 + Return whether 'instruction' can use simple input from the current
1.169 + value. Such instructions would, in a low-level implementation, be able
1.170 + to have the simple input registers as operands.
1.171 + """
1.172 +
1.173 + return isinstance(instruction, (
1.174 + StoreTemp, StoreFrame, StoreResult, StoreException, # as the value being stored
1.175 + LoadAddressContext, LoadAttr, LoadAttrIndex, # as the object being referenced
1.176 + StoreAttr, StoreAttrIndex, StoreCallable, # as the object being referenced
1.177 + LoadCallable,
1.178 + TestIdentity, TestIdentityAddress, CheckSelf, # as one of the operands
1.179 + CheckException, CheckFrame, MakeObject,
1.180 + LoadContext # as the object providing the result
1.181 + ))
1.182 +
1.183 + def is_resultant_no_operation(self, instruction):
1.184 +
1.185 + """
1.186 + Return whether 'instruction' merely stores its input where the input
1.187 + originally came from.
1.188 + """
1.189 +
1.190 + return (
1.191 + isinstance(instruction.input, LoadTemp) and isinstance(instruction, StoreTemp) and
1.192 + instruction.input.attr == instruction.attr) or (
1.193 + isinstance(instruction.input, LoadResult) and isinstance(instruction, StoreResult)
1.194 + )
1.195 +
1.196 + def is_input(self, instruction):
1.197 +
1.198 + "Return whether 'instruction' provides an input."
1.199 +
1.200 + return isinstance(instruction, current_value_instructions)
1.201 +
1.202 + # Convenience tests on outputs.
1.203 +
1.204 + def have_constant_target(self):
1.205 +
1.206 + "Return whether the active instruction provides a constant target."
1.207 +
1.208 + return self.is_constant_target(self.active)
1.209 +
1.210 + def have_constant_source(self):
1.211 +
1.212 + "Return whether the active instruction has a constant source."
1.213 +
1.214 + return self.is_constant_input(self.active.source)
1.215 +
1.216 + # Convenience tests on inputs.
1.217 +
1.218 + def have_constant_input(self):
1.219 +
1.220 + "Return whether the active instruction provides a constant input."
1.221 +
1.222 + return self.is_constant_input(self.active_value)
1.223 +
1.224 + have_known_target = have_constant_input
1.225 +
1.226 + def have_simple_input(self):
1.227 +
1.228 + "Return whether the active instruction provides a simple input."
1.229 +
1.230 + return self.is_simple_input(self.active_value)
1.231 +
1.232 + def have_input(self):
1.233 +
1.234 + "Return whether the active instruction provides an input."
1.235 +
1.236 + return self.is_input(self.active_value)
1.237 +
1.238 + def have_self_input(self):
1.239 +
1.240 + "Return whether the active instruction is a reference to self."
1.241 +
1.242 + return isinstance(self.translation.unit, Function) and \
1.243 + self.translation.unit.is_method() and isinstance(self.active_value, LoadName) and \
1.244 + self.active_value.attr.name == "self"
1.245 +
1.246 + def have_temp_compatible_access(self):
1.247 +
1.248 + """
1.249 + Indicate whether the active instruction can be used in place of access
1.250 + to a temporary variable retaining the result of the last instruction.
1.251 + """
1.252 +
1.253 + # LoadResult cannot be relied upon in general since the result register
1.254 + # could be updated since first being referenced.
1.255 +
1.256 + return isinstance(self.active_value, (LoadName, LoadTemp, LoadAddress, LoadConst)) or \
1.257 + isinstance(self.active_value, LoadResult) and self.active_value is self.active or \
1.258 + isinstance(self.active_value, LoadException) and self.active_value is self.active
1.259 +
1.260 + def have_correct_self_for_target(self, context):
1.261 +
1.262 + "Return whether the 'context' is compatible with the current value."
1.263 +
1.264 + if context is not None and self.have_self_input():
1.265 +
1.266 + parent = self.translation.unit.parent
1.267 + if parent is context or parent.has_subclass(context) or context.has_subclass(parent):
1.268 + return 1
1.269 +
1.270 + return 0
1.271 +
1.272 + # Optimisation methods. See the supported_optimisations class attribute.
1.273 +
1.274 + def optimise_constant_storage(self):
1.275 +
1.276 + """
1.277 + Where the last operation stores a constant into a target which is also
1.278 + constant, optimise away both operations.
1.279 + """
1.280 +
1.281 + if self.should_optimise_constant_storage() and \
1.282 + self.have_constant_target() and \
1.283 + self.have_constant_source():
1.284 +
1.285 + self.translation.remove_op()
1.286 + return 1
1.287 + else:
1.288 + return 0
1.289 +
1.290 + def optimise_known_target(self):
1.291 +
1.292 + """
1.293 + Where the target of an invocation is known, provide information about it
1.294 + and its context. If a class is being invoked and the conditions are
1.295 + appropriate, get information about the specific initialiser.
1.296 + """
1.297 +
1.298 + if self.should_optimise_known_target() and self.have_known_target():
1.299 + value = self.active_value
1.300 + target = value.attr.value
1.301 + context = value.attr.context
1.302 +
1.303 + return target, context
1.304 + else:
1.305 + return None
1.306 +
1.307 + def optimise_self_access(self, attrname, classes, node):
1.308 +
1.309 + """
1.310 + Where the provided 'attrname' accesses an attribute which occupies the
1.311 + same position in all possible objects which can be accessed, generate an
1.312 + instruction using one of the given 'classes', accessing the attribute
1.313 + directly.
1.314 + """
1.315 +
1.316 + AddressInstruction, AddressContextInstruction, AttrInstruction = classes
1.317 +
1.318 + if self.should_optimise_self_access() and self.have_self_input() and \
1.319 + not self.translation.unit.is_relocated(attrname):
1.320 +
1.321 + # Either generate an instruction operating on an instance attribute.
1.322 +
1.323 + try:
1.324 + attr = self.translation.unit.parent.instance_attributes()[attrname]
1.325 + self.translation.new_op(AttrInstruction(attr))
1.326 +
1.327 + # Or generate an instruction operating on a class attribute.
1.328 +
1.329 + except KeyError:
1.330 + attr = self.translation.unit.parent.all_attributes()[attrname]
1.331 +
1.332 + # Switch the context if the class attribute is compatible with
1.333 + # the instance.
1.334 +
1.335 + if attr.defined_within_hierarchy():
1.336 +
1.337 + # Only permit loading (not storing) of class attributes via self.
1.338 +
1.339 + if AddressContextInstruction is not None:
1.340 + self.translation.new_op(AddressContextInstruction(attr))
1.341 + else:
1.342 + raise TranslateError(self.translation.module.full_name(), node,
1.343 + "Storing of class attribute %r via self not permitted." % attrname)
1.344 +
1.345 + # Preserve the context if the class attribute comes from an
1.346 + # incompatible class.
1.347 +
1.348 + else:
1.349 + if AddressInstruction is not None:
1.350 + self.translation.new_op(AddressInstruction(attr))
1.351 + else:
1.352 + raise TranslateError(self.translation.module.full_name(), node,
1.353 + "Storing of class attribute %r via self not permitted." % attrname)
1.354 +
1.355 + return 1
1.356 + else:
1.357 + return 0
1.358 +
1.359 + def optimise_temp_storage(self):
1.360 +
1.361 + """
1.362 + Where the next operation would involve storing a value into temporary
1.363 + storage at 'temp_position', record and remove any simple instruction
1.364 + which produced the value to be stored such that instead of subsequently
1.365 + accessing the temporary storage, that instruction is substituted.
1.366 +
1.367 + If no optimisation can be achieved, a StoreTemp instruction is produced
1.368 + and the appropriate LoadTemp instruction is returned.
1.369 +
1.370 + Restriction: for use only in situations where the source of the
1.371 + temporary data will not be disturbed between its first access and its
1.372 + subsequent use.
1.373 + """
1.374 +
1.375 + if self.should_optimise_temp_storage() and \
1.376 + self.have_temp_compatible_access():
1.377 +
1.378 + # Remove the active value contributor.
1.379 +
1.380 + removed = self.remove_active_value()
1.381 +
1.382 + # Extend the lifetime of any temporary storage location.
1.383 +
1.384 + self.translation.ensure_temp(removed)
1.385 + return removed
1.386 + else:
1.387 + return self.translation.get_temp()
1.388 +
1.389 + def optimise_load_operations(self, instruction):
1.390 +
1.391 + """
1.392 + Incorporate previous load operations into other operations.
1.393 + """
1.394 +
1.395 + if self.should_optimise_load_operations() and \
1.396 + self.have_simple_input() and \
1.397 + self.is_simple_input_user(instruction):
1.398 +
1.399 + self.remove_active_value()
1.400 + instruction.input = self.active_value
1.401 +
1.402 + def optimise_away_no_operations(self, instruction):
1.403 +
1.404 + """
1.405 + Optimise away operations which just store their inputs in the place
1.406 + the inputs originally came from.
1.407 + """
1.408 +
1.409 + if self.should_optimise_away_no_operations() and \
1.410 + self.is_resultant_no_operation(instruction):
1.411 +
1.412 + return 1
1.413 + else:
1.414 + return 0
1.415 +
1.416 + def optimise_unused_results(self):
1.417 +
1.418 + "Discard results which will not be used."
1.419 +
1.420 + if self.should_optimise_unused_results() and self.have_simple_input():
1.421 + self.remove_active_value()
1.422 +
1.423 +# vim: tabstop=4 expandtab shiftwidth=4