# HG changeset patch # User Paul Boddie # Date 1222565403 -7200 # Node ID 69e4ee444ea04fca9fcd9364400989dab8519fa5 # Parent c34b409b96e54524154b3479cf6fc84a28b1d068 Moved the Optimiser class into its own module, taking the responsibility for maintaining active instruction information with it. diff -r c34b409b96e5 -r 69e4ee444ea0 micropython/__init__.py --- a/micropython/__init__.py Fri Sep 26 23:48:05 2008 +0200 +++ b/micropython/__init__.py Sun Sep 28 03:30:03 2008 +0200 @@ -35,6 +35,7 @@ from micropython.common import * import micropython.ast +import micropython.opt import micropython.inspect import micropython.table import os @@ -50,7 +51,7 @@ class supports the generation of a program image. """ - supported_optimisations = micropython.ast.Optimiser.supported_optimisations + supported_optimisations = micropython.opt.Optimiser.supported_optimisations def __init__(self, path=None, verbose=0): diff -r c34b409b96e5 -r 69e4ee444ea0 micropython/ast.py --- a/micropython/ast.py Fri Sep 26 23:48:05 2008 +0200 +++ b/micropython/ast.py Sun Sep 28 03:30:03 2008 +0200 @@ -19,349 +19,19 @@ this program. If not, see . """ +from micropython.opt import Optimiser from micropython.common import * from micropython.data import * from micropython.rsvp import * import compiler.ast from compiler.visitor import ASTVisitor -class Optimiser: - - "A code optimiser." - - supported_optimisations = [ - "constant_storage", "known_target", "self_access", - "temp_storage", "load_operations", "no_operations", - "unused_results" - ] - - def __init__(self, translation, optimisations=None): - - """ - Provide for the given 'translation' an optimiser for the desired - 'optimisations'. See the 'supported_optimisations' attribute of this - class for permitted values. - """ - - self.translation = translation - self.optimisations = set(optimisations or []) - - # Optimisation tests. - - def should_optimise_constant_storage(self): - return "constant_storage" in self.optimisations - - def should_optimise_known_target(self): - return "known_target" in self.optimisations - - def should_optimise_self_access(self): - return "self_access" in self.optimisations - - def should_optimise_temp_storage(self): - return "temp_storage" in self.optimisations - - def should_optimise_load_operations(self): - return "load_operations" in self.optimisations - - def should_optimise_away_no_operations(self): - return "no_operations" in self.optimisations - - def should_optimise_unused_results(self): - return "unused_results" in self.optimisations - - # Simple tests. - - def is_constant_input(self, instruction): - - "Return whether 'instruction' provides a constant input." - - return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 or \ - isinstance(instruction, LoadConst) - - def is_constant_target(self, instruction): - - "Return whether 'instruction' provides a constant target." - - return isinstance(instruction, (StoreName, StoreAddress)) and \ - instruction.attr.assignments == 1 - - def is_simple_input(self, instruction): - - """ - Return whether 'instruction' provides a simple input (typically a load - instruction). A simple input is something which would be represented by - a load operation from a CPU register or special memory location. - """ - - return isinstance(instruction, (LoadConst, LoadName, LoadTemp, LoadResult, LoadException, LoadAddress)) - - def is_simple_input_user(self, instruction): - - """ - Return whether 'instruction' can use simple input from the current - value. Such instructions would, in a low-level implementation, be able - to have the simple input registers as operands. - """ - - return isinstance(instruction, ( - StoreTemp, StoreFrame, StoreResult, StoreException, # as the value being stored - LoadAddressContext, LoadAttr, LoadAttrIndex, # as the object being referenced - StoreAttr, StoreAttrIndex, StoreCallable, # as the object being referenced - LoadCallable, - TestIdentity, TestIdentityAddress, CheckSelf, # as one of the operands - CheckException, CheckFrame, MakeObject, - LoadContext # as the object providing the result - )) - - def is_resultant_no_operation(self, instruction): - - """ - Return whether 'instruction' merely stores its input where the input - originally came from. - """ - - return ( - isinstance(instruction.input, LoadTemp) and isinstance(instruction, StoreTemp) and - instruction.input.attr == instruction.attr) or ( - isinstance(instruction.input, LoadResult) and isinstance(instruction, StoreResult) - ) - - def is_input(self, instruction): - - "Return whether 'instruction' provides an input." - - return isinstance(instruction, current_value_instructions) - - # Convenience tests on outputs. - - def have_constant_target(self): - - "Return whether the active instruction provides a constant target." - - return self.is_constant_target(self.translation.active) - - def have_constant_source(self): - - "Return whether the active instruction has a constant source." - - return self.is_constant_input(self.translation.active.source) - - # Convenience tests on inputs. - - def have_constant_input(self): - - "Return whether the active instruction provides a constant input." - - return self.is_constant_input(self.translation.active_value) - - have_known_target = have_constant_input - - def have_simple_input(self): - - "Return whether the active instruction provides a simple input." - - return self.is_simple_input(self.translation.active_value) - - def have_input(self): - - "Return whether the active instruction provides an input." - - return self.is_input(self.translation.active_value) - - def have_self_input(self): - - "Return whether the active instruction is a reference to self." - - return isinstance(self.translation.unit, Function) and \ - self.translation.unit.is_method() and isinstance(self.translation.active_value, LoadName) and \ - self.translation.active_value.attr.name == "self" - - def have_temp_compatible_access(self): - - """ - Indicate whether the active instruction can be used in place of access - to a temporary variable retaining the result of the last instruction. - """ - - # LoadResult cannot be relied upon in general since the result register - # could be updated since first being referenced. - - return isinstance(self.translation.active_value, (LoadName, LoadTemp, LoadAddress, LoadConst)) or \ - isinstance(self.translation.active_value, LoadResult) and self.translation.active_value is self.translation.active or \ - isinstance(self.translation.active_value, LoadException) and self.translation.active_value is self.translation.active - - def have_correct_self_for_target(self, context): - - "Return whether the 'context' is compatible with the current value." - - if context is not None and self.have_self_input(): - - parent = self.translation.unit.parent - if parent is context or parent.has_subclass(context) or context.has_subclass(parent): - return 1 - - return 0 - - # Optimisation methods. See the supported_optimisations class attribute. - - def optimise_constant_storage(self): - - """ - Where the last operation stores a constant into a target which is also - constant, optimise away both operations. - """ - - if self.should_optimise_constant_storage() and \ - self.have_constant_target() and \ - self.have_constant_source(): - - self.translation.remove_op() - return 1 - else: - return 0 - - def optimise_known_target(self): - - """ - Where the target of an invocation is known, provide information about it - and its context. If a class is being invoked and the conditions are - appropriate, get information about the specific initialiser. - """ - - if self.should_optimise_known_target() and self.have_known_target(): - last = self.translation.active_value - target = last.attr.value - context = last.attr.context - - return target, context - else: - return None - - def optimise_self_access(self, attrname, classes, node): - - """ - Where the provided 'attrname' accesses an attribute which occupies the - same position in all possible objects which can be accessed, generate an - instruction using one of the given 'classes', accessing the attribute - directly. - """ - - AddressInstruction, AddressContextInstruction, AttrInstruction = classes - - if self.should_optimise_self_access() and self.have_self_input() and \ - not self.translation.unit.is_relocated(attrname): - - # Either generate an instruction operating on an instance attribute. - - try: - attr = self.translation.unit.parent.instance_attributes()[attrname] - self.translation.new_op(AttrInstruction(attr)) - - # Or generate an instruction operating on a class attribute. - - except KeyError: - attr = self.translation.unit.parent.all_attributes()[attrname] - - # Switch the context if the class attribute is compatible with - # the instance. - - if attr.defined_within_hierarchy(): - - # Only permit loading (not storing) of class attributes via self. - - if AddressContextInstruction is not None: - self.translation.new_op(AddressContextInstruction(attr)) - else: - raise TranslateError(self.translation.module.full_name(), node, - "Storing of class attribute %r via self not permitted." % attrname) - - # Preserve the context if the class attribute comes from an - # incompatible class. - - else: - if AddressInstruction is not None: - self.translation.new_op(AddressInstruction(attr)) - else: - raise TranslateError(self.translation.module.full_name(), node, - "Storing of class attribute %r via self not permitted." % attrname) - - return 1 - else: - return 0 - - def optimise_temp_storage(self): - - """ - Where the next operation would involve storing a value into temporary - storage at 'temp_position', record and remove any simple instruction - which produced the value to be stored such that instead of subsequently - accessing the temporary storage, that instruction is substituted. - - If no optimisation can be achieved, a StoreTemp instruction is produced - and the appropriate LoadTemp instruction is returned. - - Restriction: for use only in situations where the source of the - temporary data will not be disturbed between its first access and its - subsequent use. - """ - - if self.should_optimise_temp_storage() and \ - self.have_temp_compatible_access(): - - # Remove the active value contributor. - - removed = self.translation.active - self.translation.remove_active_value() - - # Extend the lifetime of any temporary storage location. - - self.translation.ensure_temp(removed) - return removed - else: - return self.translation.get_temp() - - def optimise_load_operations(self, instruction): - - """ - Incorporate previous load operations into other operations. - """ - - if self.should_optimise_load_operations() and \ - self.have_simple_input() and \ - self.is_simple_input_user(instruction): - - self.translation.remove_active_value() - instruction.input = self.translation.active_value - - def optimise_away_no_operations(self, instruction): - - """ - Optimise away operations which just store their inputs in the place - the inputs originally came from. - """ - - if self.should_optimise_away_no_operations() and \ - self.is_resultant_no_operation(instruction): - - return 1 - else: - return 0 - - def optimise_unused_results(self): - - "Discard results which will not be used." - - if self.should_optimise_unused_results() and self.have_simple_input(): - self.translation.remove_active_value() - # Program visitors. class Translation(ASTVisitor): "A translated module." - supported_optimisations = Optimiser.supported_optimisations - # Attribute access instructions, for use with the appropriate handlers. attribute_load_instructions = (LoadAddress, LoadAddressContext, LoadAttr, LoadAttrIndex) @@ -376,8 +46,7 @@ """ Initialise the translation with an inspected 'module', the 'importer' - and optional 'optimisations'. See the 'supported_optimisations' - attribute of this class for permitted values. + and optional 'optimisations'. """ ASTVisitor.__init__(self) @@ -399,13 +68,6 @@ self.unit = None - # The current "active" instruction. - # As a rule, this will become the last instruction, but some - # control-flow operations will flush the "active" instruction. - - self.active = None - self.active_value = None - # The temporary storage used by the current assignment expression. self.expr_temp = [] @@ -607,8 +269,7 @@ self.discard_temp(self.expr_temp.pop()) def set_source(self): - if self.active is not None: - self.active.source = self.expr_temp[-1] + self.optimiser.set_source(self.expr_temp[-1]) # Optimise away constant storage if appropriate. @@ -669,26 +330,14 @@ return self.code.append(op) - self.active = op - - # Record specific types of instructions for optimisation. - - if isinstance(op, current_value_instructions): - self.active_value = op + self.optimiser.set_new(op) def remove_op(self): "Remove the last instruction." op = self.code.pop() - self.active = None - - def remove_active_value(self): - - "Remove the value-providing active instruction if appropriate." - - if self.active_value is self.active: - self.remove_op() + self.optimiser.clear_active() def replace_op(self, op): @@ -703,7 +352,7 @@ Replace the value-providing active instruction with 'op' if appropriate. """ - self.remove_active_value() + self.optimiser.remove_active_value() self.new_op(op) def last_op(self): @@ -715,13 +364,6 @@ except IndexError: return None - def clear_active(self): - - "Prevent incorrect optimisation." - - self.active = None - self.active_value = None - # Visitor methods. def default(self, node, *args): @@ -754,7 +396,7 @@ # constant... if self.optimiser.have_constant_input(): - last = self.active_value + last = self.optimiser.active_value # Get the details of the access. @@ -1041,7 +683,7 @@ continue_label = self.new_label() self.new_op(CheckSelf()) - self.active.source = temp + self.optimiser.set_source(temp) self.new_op(JumpIfTrue(continue_label)) # Where the context is inappropriate, drop the incomplete frame and @@ -1301,7 +943,7 @@ # Prevent incorrect optimisation. - self.clear_active() + self.optimiser.reset() self.set_label(end_label) @@ -1386,7 +1028,7 @@ # Prevent incorrect optimisation. - self.clear_active() + self.optimiser.reset() self.set_label(end_label) return temp_out @@ -1538,7 +1180,7 @@ # Prevent incorrect optimisation. - self.clear_active() + self.optimiser.reset() self.new_op(temp) self.discard_temp(temp) @@ -2050,7 +1692,7 @@ # Prevent incorrect optimisation. - self.clear_active() + self.optimiser.reset() def visitOr(self, node): end_label = self.new_label() @@ -2071,7 +1713,7 @@ # Prevent incorrect optimisation. - self.clear_active() + self.optimiser.reset() self.new_op(temp) self.discard_temp(temp) @@ -2231,7 +1873,7 @@ # Prevent incorrect optimisation. - self.clear_active() + self.optimiser.reset() def visitWith(self, node): raise TranslationNotImplementedError(self.module.full_name(), node, "With") diff -r c34b409b96e5 -r 69e4ee444ea0 micropython/opt.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/micropython/opt.py Sun Sep 28 03:30:03 2008 +0200 @@ -0,0 +1,420 @@ +#!/usr/bin/env python + +""" +Optimise code produced by the AST translator. + +Copyright (C) 2007, 2008 Paul Boddie + +This program is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free Software +Foundation; either version 3 of the License, or (at your option) any later +version. + +This program is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more +details. + +You should have received a copy of the GNU General Public License along with +this program. If not, see . +""" + +from micropython.common import * +from micropython.rsvp import * + +class Optimiser: + + "A code optimiser." + + supported_optimisations = [ + "constant_storage", "known_target", "self_access", + "temp_storage", "load_operations", "no_operations", + "unused_results" + ] + + def __init__(self, translation, optimisations=None): + + """ + Provide for the given 'translation' an optimiser for the desired + 'optimisations'. See the 'supported_optimisations' attribute of this + class for permitted values. + """ + + self.translation = translation + self.optimisations = set(optimisations or []) + + # The current "active" instruction. + # As a rule, this will become the last instruction, but some + # control-flow operations will flush the "active" instruction. + + self.active = None + + # The instruction providing the active value. + + self.active_value = None + + def reset(self): + + "Reset the optimiser, clearing the active instructions." + + self.clear_active_value() + self.clear_active() + + def set_new(self, op): + + "Set the latest 'op' as the active instruction." + + self.set_active(op) + self.set_active_value(op) + + def set_active_value(self, op): + + "Set the value-providing active instruction." + + if isinstance(op, current_value_instructions): + self.active_value = op + + def clear_active_value(self): + + "Clear the value-providing active instruction." + + self.active_value = None + + def remove_active_value(self): + + "Remove the value-providing active instruction if appropriate." + + if self.active_value is self.active: + removed = self.active + self.translation.remove_op() + return removed + else: + return None + + def set_source(self, expr): + + "Set the source of the active instruction to 'expr'." + + if self.active is not None: + self.active.source = expr + + def set_active(self, op): + + "Set the active instruction." + + self.active = op + + def clear_active(self): + + "Clear the active instruction." + + self.active = None + + # Optimisation tests. + + def should_optimise_constant_storage(self): + return "constant_storage" in self.optimisations + + def should_optimise_known_target(self): + return "known_target" in self.optimisations + + def should_optimise_self_access(self): + return "self_access" in self.optimisations + + def should_optimise_temp_storage(self): + return "temp_storage" in self.optimisations + + def should_optimise_load_operations(self): + return "load_operations" in self.optimisations + + def should_optimise_away_no_operations(self): + return "no_operations" in self.optimisations + + def should_optimise_unused_results(self): + return "unused_results" in self.optimisations + + # Simple tests. + + def is_constant_input(self, instruction): + + "Return whether 'instruction' provides a constant input." + + return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 or \ + isinstance(instruction, LoadConst) + + def is_constant_target(self, instruction): + + "Return whether 'instruction' provides a constant target." + + return isinstance(instruction, (StoreName, StoreAddress)) and \ + instruction.attr.assignments == 1 + + def is_simple_input(self, instruction): + + """ + Return whether 'instruction' provides a simple input (typically a load + instruction). A simple input is something which would be represented by + a load operation from a CPU register or special memory location. + """ + + return isinstance(instruction, (LoadConst, LoadName, LoadTemp, LoadResult, LoadException, LoadAddress)) + + def is_simple_input_user(self, instruction): + + """ + Return whether 'instruction' can use simple input from the current + value. Such instructions would, in a low-level implementation, be able + to have the simple input registers as operands. + """ + + return isinstance(instruction, ( + StoreTemp, StoreFrame, StoreResult, StoreException, # as the value being stored + LoadAddressContext, LoadAttr, LoadAttrIndex, # as the object being referenced + StoreAttr, StoreAttrIndex, StoreCallable, # as the object being referenced + LoadCallable, + TestIdentity, TestIdentityAddress, CheckSelf, # as one of the operands + CheckException, CheckFrame, MakeObject, + LoadContext # as the object providing the result + )) + + def is_resultant_no_operation(self, instruction): + + """ + Return whether 'instruction' merely stores its input where the input + originally came from. + """ + + return ( + isinstance(instruction.input, LoadTemp) and isinstance(instruction, StoreTemp) and + instruction.input.attr == instruction.attr) or ( + isinstance(instruction.input, LoadResult) and isinstance(instruction, StoreResult) + ) + + def is_input(self, instruction): + + "Return whether 'instruction' provides an input." + + return isinstance(instruction, current_value_instructions) + + # Convenience tests on outputs. + + def have_constant_target(self): + + "Return whether the active instruction provides a constant target." + + return self.is_constant_target(self.active) + + def have_constant_source(self): + + "Return whether the active instruction has a constant source." + + return self.is_constant_input(self.active.source) + + # Convenience tests on inputs. + + def have_constant_input(self): + + "Return whether the active instruction provides a constant input." + + return self.is_constant_input(self.active_value) + + have_known_target = have_constant_input + + def have_simple_input(self): + + "Return whether the active instruction provides a simple input." + + return self.is_simple_input(self.active_value) + + def have_input(self): + + "Return whether the active instruction provides an input." + + return self.is_input(self.active_value) + + def have_self_input(self): + + "Return whether the active instruction is a reference to self." + + return isinstance(self.translation.unit, Function) and \ + self.translation.unit.is_method() and isinstance(self.active_value, LoadName) and \ + self.active_value.attr.name == "self" + + def have_temp_compatible_access(self): + + """ + Indicate whether the active instruction can be used in place of access + to a temporary variable retaining the result of the last instruction. + """ + + # LoadResult cannot be relied upon in general since the result register + # could be updated since first being referenced. + + return isinstance(self.active_value, (LoadName, LoadTemp, LoadAddress, LoadConst)) or \ + isinstance(self.active_value, LoadResult) and self.active_value is self.active or \ + isinstance(self.active_value, LoadException) and self.active_value is self.active + + def have_correct_self_for_target(self, context): + + "Return whether the 'context' is compatible with the current value." + + if context is not None and self.have_self_input(): + + parent = self.translation.unit.parent + if parent is context or parent.has_subclass(context) or context.has_subclass(parent): + return 1 + + return 0 + + # Optimisation methods. See the supported_optimisations class attribute. + + def optimise_constant_storage(self): + + """ + Where the last operation stores a constant into a target which is also + constant, optimise away both operations. + """ + + if self.should_optimise_constant_storage() and \ + self.have_constant_target() and \ + self.have_constant_source(): + + self.translation.remove_op() + return 1 + else: + return 0 + + def optimise_known_target(self): + + """ + Where the target of an invocation is known, provide information about it + and its context. If a class is being invoked and the conditions are + appropriate, get information about the specific initialiser. + """ + + if self.should_optimise_known_target() and self.have_known_target(): + value = self.active_value + target = value.attr.value + context = value.attr.context + + return target, context + else: + return None + + def optimise_self_access(self, attrname, classes, node): + + """ + Where the provided 'attrname' accesses an attribute which occupies the + same position in all possible objects which can be accessed, generate an + instruction using one of the given 'classes', accessing the attribute + directly. + """ + + AddressInstruction, AddressContextInstruction, AttrInstruction = classes + + if self.should_optimise_self_access() and self.have_self_input() and \ + not self.translation.unit.is_relocated(attrname): + + # Either generate an instruction operating on an instance attribute. + + try: + attr = self.translation.unit.parent.instance_attributes()[attrname] + self.translation.new_op(AttrInstruction(attr)) + + # Or generate an instruction operating on a class attribute. + + except KeyError: + attr = self.translation.unit.parent.all_attributes()[attrname] + + # Switch the context if the class attribute is compatible with + # the instance. + + if attr.defined_within_hierarchy(): + + # Only permit loading (not storing) of class attributes via self. + + if AddressContextInstruction is not None: + self.translation.new_op(AddressContextInstruction(attr)) + else: + raise TranslateError(self.translation.module.full_name(), node, + "Storing of class attribute %r via self not permitted." % attrname) + + # Preserve the context if the class attribute comes from an + # incompatible class. + + else: + if AddressInstruction is not None: + self.translation.new_op(AddressInstruction(attr)) + else: + raise TranslateError(self.translation.module.full_name(), node, + "Storing of class attribute %r via self not permitted." % attrname) + + return 1 + else: + return 0 + + def optimise_temp_storage(self): + + """ + Where the next operation would involve storing a value into temporary + storage at 'temp_position', record and remove any simple instruction + which produced the value to be stored such that instead of subsequently + accessing the temporary storage, that instruction is substituted. + + If no optimisation can be achieved, a StoreTemp instruction is produced + and the appropriate LoadTemp instruction is returned. + + Restriction: for use only in situations where the source of the + temporary data will not be disturbed between its first access and its + subsequent use. + """ + + if self.should_optimise_temp_storage() and \ + self.have_temp_compatible_access(): + + # Remove the active value contributor. + + removed = self.remove_active_value() + + # Extend the lifetime of any temporary storage location. + + self.translation.ensure_temp(removed) + return removed + else: + return self.translation.get_temp() + + def optimise_load_operations(self, instruction): + + """ + Incorporate previous load operations into other operations. + """ + + if self.should_optimise_load_operations() and \ + self.have_simple_input() and \ + self.is_simple_input_user(instruction): + + self.remove_active_value() + instruction.input = self.active_value + + def optimise_away_no_operations(self, instruction): + + """ + Optimise away operations which just store their inputs in the place + the inputs originally came from. + """ + + if self.should_optimise_away_no_operations() and \ + self.is_resultant_no_operation(instruction): + + return 1 + else: + return 0 + + def optimise_unused_results(self): + + "Discard results which will not be used." + + if self.should_optimise_unused_results() and self.have_simple_input(): + self.remove_active_value() + +# vim: tabstop=4 expandtab shiftwidth=4