# HG changeset patch # User Paul Boddie # Date 1315174593 -7200 # Node ID 04c6f309c52fdc9427cfd1d205f99a04cbdc4f10 # Parent 3e1478c9fb018d88ab568a03793ccc4eeb5980c0 Attempted to introduce optimisations to avoid temporary storage allocation and to defer the production of instructions that save values in temporary storage. Changed the assignment handling to attempt to make use of "live" working values. Changed the default target of various instructions and simplified the testing of instructions that affect the working value. Added default source and working register values for instructions. Removed the redundant load_result parameter for _endCallFunc. diff -r 3e1478c9fb01 -r 04c6f309c52f TO_DO.txt --- a/TO_DO.txt Thu Sep 01 00:35:47 2011 +0200 +++ b/TO_DO.txt Mon Sep 05 00:16:33 2011 +0200 @@ -13,11 +13,11 @@ Move common code sequences to a library routine, such as the context checking that occurs in functions and methods. -Return Value Optimisations -========================== +Dataflow Optimisations +====================== -Attempt to use result data directly instead of transferring it explicitly to the working -registers and then using it. +Assignments, particularly now that no result register exists, may cause StoreTemp/LoadTemp +instruction pairs to be produced and these could be eliminated. Class and Module Attribute Assignment ===================================== diff -r 3e1478c9fb01 -r 04c6f309c52f micropython/ast.py --- a/micropython/ast.py Thu Sep 01 00:35:47 2011 +0200 +++ b/micropython/ast.py Mon Sep 05 00:16:33 2011 +0200 @@ -473,7 +473,7 @@ self.new_op(temp_getitem) temp_target, target, temp_context = self._generateCallFunc([compiler.ast.Const(i)], node) self._doCallFunc(temp_target, target) - self._endCallFunc() + self._endCallFunc(temp_context=temp_context) # Provide a different source value. # NOTE: Permitting immediate usage given that neither name nor @@ -620,12 +620,6 @@ self.dispatch(n) - # Discard temporary storage. - - if self.temp_positions: - #print "Had temp", self.temp_positions - self.temp_positions = set() - # Prevent incorrect optimisation by resetting the optimiser after # each statement. diff -r 3e1478c9fb01 -r 04c6f309c52f micropython/code.py --- a/micropython/code.py Thu Sep 01 00:35:47 2011 +0200 +++ b/micropython/code.py Mon Sep 05 00:16:33 2011 +0200 @@ -126,8 +126,8 @@ """ Record the current active value for an assignment. If the optional - 'immediate' parameter if set to a false value always allocates new - temporary storage to hold the recorded value; otherwise, the + 'immediate' parameter is set to a false value, new temporary storage to + hold the recorded value will be allocated; otherwise, the value-providing instruction may be replicated in order to provide the active value later on. """ @@ -163,10 +163,31 @@ # Otherwise, insert the assignment source. if expr is not None: - expr = expr.copy() - expr.target = "source" - self.insert_op(-1, expr) - self.last_op().source = "source" + expr_copy = expr.copy() + assign_op = self.last_op() + + # Either insert the instruction yielding the value and adjust the + # assignment source. + + expr_copy.target = "source" + + if self.insert_op(-1, expr_copy): + assign_op.source = "source" + self.update_temp(expr, expr_copy) + + # (Now, the instruction need not be inserted.) + + # Or transfer the working value to the source register. + + elif assign_op.working == "working": + self.insert_op(-1, Transfer(source="working_context", target="source_context")) + self.insert_op(-1, Transfer(source="working", target="source")) + assign_op.source = "source" + + # Or let the assignment use the working register. + + else: + assign_op.source = "working" def set_target(self, target): @@ -198,13 +219,34 @@ def get_temp(self): """ - Add a temporary storage instruction for the current value and return a - sequence of access instructions. + Return a temporary storage access instruction for the current value. + Initially, this instruction is not associated with an allocated unit of + temporary storage, and if used as a new instruction will not be added to + the code, but if the current value changes, the 'set_temp' method will + be called by the optimiser and a unit of storage will be allocated. """ - position_in_frame = self.reserve_temp() - self.new_op(StoreTemp(position_in_frame)) - return LoadTemp(position_in_frame) + temp = LoadTemp(None) + self.optimiser.request_active_value(temp, self.blocks[-1], len(self.blocks[-1].code)) + return temp + + def set_temp(self, temp, block, pos): + + """ + Emit a storage instruction for the given 'temp' loading instruction, + reserving a new temporary storage location. + """ + + if temp.attr is None: + temp.attr = self.reserve_temp() + block.insert(pos, StoreTemp(temp.attr)) + + def update_temp(self, temp, updated): + + "Update 'temp' using the given 'updated' instruction." + + if isinstance(temp, LoadTemp): + temp.attr = updated.attr def reserve_temp(self, temp_position=None): @@ -240,9 +282,10 @@ "Discard any temporary storage position used by 'instruction'." - if isinstance(instruction, LoadTemp): + if isinstance(instruction, LoadTemp) and instruction.attr is not None: temp_position = instruction.attr - self.unit.all_local_usage self.free_temp(temp_position) + self.optimiser.ignore_active_value() def free_temp(self, temp_position): @@ -276,22 +319,41 @@ was added. """ - # Optimise load operations employed by this instruction. - - if self.optimiser.optimise_away_no_operations(op) or self.optimiser.optimise_unused_handlers(op): + if not self.check_op(op): return 0 # Add the operation to the current block. - self.blocks[-1].code.append(op) self.optimiser.set_new(op) + self.blocks[-1].append(op) return 1 def insert_op(self, i, op): "Insert at index 'i' in the current block the instruction 'op'." - self.blocks[-1].code.insert(i, op) + if not self.check_op(op): + return 0 + + self.blocks[-1].insert(i, op) + return 1 + + def check_op(self, op): + + "Return whether the given 'op' is to be added to the code." + + # Optimise away temporary storage instructions where the active value is + # still available and was not recorded. + + if isinstance(op, LoadTemp) and op.attr is None: + return 0 + + # Optimise load operations employed by this instruction. + + if self.optimiser.optimise_away_no_operations(op) or self.optimiser.optimise_unused_handlers(op): + return 0 + + return 1 def remove_op(self): diff -r 3e1478c9fb01 -r 04c6f309c52f micropython/opt.py --- a/micropython/opt.py Thu Sep 01 00:35:47 2011 +0200 +++ b/micropython/opt.py Mon Sep 05 00:16:33 2011 +0200 @@ -52,6 +52,9 @@ # control-flow operations will flush the "active" instruction. self.active = None + self.saved_value_op = None + self.saved_value_block = None + self.saved_value_pos = None # Instructions providing the active value. @@ -83,6 +86,7 @@ collecting the active instructions from each of the blocks otherwise. """ + self.store_active_value() self.clear_active() # Make a new collection of instructions for a new block. @@ -111,7 +115,8 @@ "Set the value-providing active instruction." - if isinstance(op, current_value_instructions) and op.target == "working": + if affects_register(op, "working"): + self.store_active_value() self.active_values.clear() self.active_values.add(op) @@ -157,6 +162,36 @@ self.active = None + # Permit the active value to be requested and restored. + + def request_active_value(self, temp, block, pos): + + """ + Request the current active value so that if the value is changed, a + temporary storage element or equivalent will be allocated. + """ + + self.store_active_value() + self.saved_value_op = temp + self.saved_value_block = block + self.saved_value_pos = pos + + def store_active_value(self): + + "Store the requested active value" + + if self.saved_value_op is not None: + self.translation.set_temp(self.saved_value_op, self.saved_value_block, self.saved_value_pos) + self.ignore_active_value() + + def ignore_active_value(self): + + "Ignore the active value." + + self.saved_value_op = None + self.saved_value_block = None + self.saved_value_pos = None + # Optimisation tests. def should_optimise_constant_storage(self): @@ -218,15 +253,17 @@ LoadName, LoadTemp, LoadAddress )) - def is_resultant_no_operation(self, instruction): + def is_resultant_no_operation(self, instruction, last_op=None): """ Return whether 'instruction' merely stores its input where the input originally came from. """ - return ( - isinstance(instruction, StoreTemp) and instruction.target == instruction.source + last_op = last_op or self.translation.last_op() + return last_op and last_op.attr == instruction.attr and ( + isinstance(instruction, StoreTemp) and isinstance(last_op, LoadTemp) or + isinstance(instruction, StoreAddress) and isinstance(last_op, LoadAddress) ) # Convenience tests on outputs. @@ -377,7 +414,7 @@ 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 + If no optimisation can be achieved, temporary storage is requested and the appropriate LoadTemp instruction is returned. Restriction: for use only in situations where the source of the @@ -388,7 +425,7 @@ if self.should_optimise_temp_storage() and \ self.have_temp_compatible_access(): - # Remove the active value contributor. + # Remove the active value contributor if possible. removed = self.remove_active_value() if removed is not None: @@ -398,9 +435,14 @@ self.translation.ensure_temp(removed) return removed + # Otherwise, just leave it in place, but return the instruction. + + else: + return self.get_active_value() + return self.translation.get_temp() - def optimise_away_no_operations(self, instruction): + def optimise_away_no_operations(self, instruction, last_op=None): """ Optimise away operations which just store their inputs in the place @@ -408,7 +450,7 @@ """ return self.should_optimise_away_no_operations() and \ - self.is_resultant_no_operation(instruction) + self.is_resultant_no_operation(instruction, last_op) def optimise_unused_results(self): diff -r 3e1478c9fb01 -r 04c6f309c52f micropython/program.py --- a/micropython/program.py Thu Sep 01 00:35:47 2011 +0200 +++ b/micropython/program.py Mon Sep 05 00:16:33 2011 +0200 @@ -37,6 +37,12 @@ def get_active_values(self): return self.active_values + def insert(self, pos, op): + self.code.insert(pos, op) + + def append(self, op): + self.code.append(op) + class DataValue: "A representation of a raw program value." diff -r 3e1478c9fb01 -r 04c6f309c52f micropython/rsvp.py --- a/micropython/rsvp.py Thu Sep 01 00:35:47 2011 +0200 +++ b/micropython/rsvp.py Mon Sep 05 00:16:33 2011 +0200 @@ -297,14 +297,18 @@ "A generic instruction." + default_working = "working" + default_target = "working" + default_source = None + # NOTE: Ultimately, instructions apart from Transfer will use specific # NOTE: registers such as "working_value" and "working_context". - def __init__(self, attr=None, working="working", target="working", source=None): + def __init__(self, attr=None, working=None, target=None, source=None): self.attr = attr - self.working = working - self.target = target - self.source = source + self.working = working or self.default_working + self.target = target or self.default_target + self.source = source or self.default_source def get_details(self): return self.__class__, self.attr, self.working, self.target, self.source @@ -333,13 +337,13 @@ return repr(operand) def format_working(self): - return self.working != "working" and (", working=%r" % self.working) or "" + return self.working != self.default_working and (", working=%r" % self.working) or "" def format_source(self): - return self.source is not None and (", source=%r" % self.source) or "" + return self.source != self.default_source and (", source=%r" % self.source) or "" def format_target(self): - return self.target != "working" and (", target=%r" % self.target) or "" + return self.target != self.default_target and (", target=%r" % self.target) or "" def get_operand(self): return None @@ -463,6 +467,7 @@ class StoreName(FR): "Store the source value into the given local attribute/variable." cost = 2 + default_target = None class LoadTemp(Immediate): "Load the current value from the given temporary location." @@ -471,6 +476,7 @@ class StoreTemp(Immediate): "Store the current value into the given temporary location." cost = 2 + default_target = None # Access to static data. @@ -481,6 +487,8 @@ class StoreAddress(Address): "Store the source value into the given fixed attribute address." cost = 1 + default_working = None + default_target = None class LoadAddressContext(Address): "Load the current value from the given fixed attribute address, using the current value as context." @@ -489,6 +497,7 @@ class StoreAddressContext(Address): "Store the current value into the given fixed attribute address, using the current value as context." cost = 2 + default_target = None class LoadAddressContextCond(Address): """ @@ -514,6 +523,7 @@ class StoreAttr(AR): "Store the source value into the given attribute of the object referenced by the current value." cost = 2 + default_target = None class LoadAttrIndex(Immediate): "Load into the current value the attribute of the current value with the given index." @@ -522,6 +532,7 @@ class StoreAttrIndex(Immediate): "Store the source value into the attribute of the current value with the given index." cost = 6 + default_target = None class LoadAttrIndexContextCond(Immediate): """ @@ -539,28 +550,34 @@ class StoreCallable(Instruction): "Store the source value into the object referenced by the current value." cost = 3 + default_target = None # Access to invocation frames in preparation. class MakeFrame(Immediate): "Make a new invocation frame." cost = 2 + default_target = None class AdjustFrame(Immediate): "Adjust the current invocation frame for corrected invocations." cost = 2 + default_target = None class DropFrame(Instruction): "Drop an invocation frame." cost = 2 + default_target = None class StoreFrame(Immediate): "Store the current value as an argument for the parameter with the given position." cost = 2 + default_target = None class StoreFrameIndex(Immediate): "Store the source value as an argument of the current value for the parameter with the given index." cost = 6 + default_target = None # Context-related tests. @@ -592,10 +609,12 @@ class FillDefaults(Immediate): "Fill frame positions with defaults, if appropriate." cost = 8 # variable + default_target = None class ExtendFrame(Immediate): "Extend the current frame for temporary storage use." cost = 1 + default_target = None class CopyExtra(Immediate): "Copy extra arguments into a separate sequence, starting from the given position." @@ -606,46 +625,56 @@ class JumpInFrame(Instruction): "Jump, using the current locals, to the current callable." cost = 2 + default_target = None class JumpWithFrame(Instruction): "Jump, adopting the invocation frame, to the current callable." cost = 3 + default_target = None class JumpWithFrameDirect(Target): "Jump to the specified address, adopting the invocation frame." cost = 3 + default_target = None class Return(Instruction): "Return from a subprogram." cost = 2 + default_target = None # Branch-related instructions. class Jump(Address): "Jump unconditionally." cost = 1 + default_target = None class JumpIfFalse(Address): "Jump if the last evaluation gave a false result." cost = 2 + default_target = None class JumpIfTrue(Address): "Jump if the last evaluation gave a true result." cost = 2 + default_target = None # Exception-related instructions, using a special exception "register". class RaiseException(Instruction): "Raise an exception, jumping to the active handler." cost = 2 + default_target = None class PushHandler(Address): "Push an exception handler onto the handler stack." cost = 3 + default_target = None class PopHandler(Immediate): "Pop exception handlers from the handler stack." cost = 3 + default_target = None class CheckException(Instruction): "Check the raised exception against another." @@ -671,16 +700,15 @@ # Instructions which can affect the current value. (LoadAttrIndexContext not defined.) -current_value_instructions = ( - Transfer, - LoadConst, LoadClass, LoadFunction, - LoadName, LoadTemp, - LoadAddress, LoadAddressContext, LoadAddressContextCond, - LoadAttr, LoadAttrIndex, LoadAttrIndexContextCond, - LoadCallable, - MakeInstance, MakeFragment, - CopyExtra, - CheckClass, CheckContext, CheckException, CheckInstance, CheckFrame, CheckExtra - ) +def affects_register(instruction, register): + + """ + Returns whether 'instruction' affects the given 'register', either directly + or as a consequence of its execution. + """ + + return instruction.target == register or isinstance(instruction, ( + JumpWithFrame, JumpWithFrameDirect, JumpIfTrue, JumpIfFalse, Jump + )) # vim: tabstop=4 expandtab shiftwidth=4 diff -r 3e1478c9fb01 -r 04c6f309c52f micropython/trans.py --- a/micropython/trans.py Thu Sep 01 00:35:47 2011 +0200 +++ b/micropython/trans.py Mon Sep 05 00:16:33 2011 +0200 @@ -351,7 +351,7 @@ # Recall the accessor. - self.new_op(temp_accessor.copy()) + self.new_op(temp_accessor) # Otherwise, perform a normal operation. @@ -777,9 +777,10 @@ # Check the current value (the argument) against the known context # (given as the source). - temp_context = temp_context.copy() - temp_context.target = "source" - self.new_op(temp_context) + if self.new_op(temp_context.copy()): + self.last_op().target = "source" + self.update_temp(temp_context, self.last_op()) + self.new_op(temp_first_argument) self.new_op(CheckInstance(source="source", target="status")) @@ -824,7 +825,7 @@ self.frame_makers[-1].attr = nargs self.frame_makers.pop() - def _endCallFunc(self, temp_target=None, temp_context=None, load_result=1): + def _endCallFunc(self, temp_target=None, temp_context=None): "Finish the invocation and tidy up afterwards." @@ -838,10 +839,6 @@ if temp_context is not None: self.discard_temp(temp_context) - # Reset the active values. - - self.optimiser.reset() - def _visitFunctionDeclaration(self, node): """ @@ -861,10 +858,7 @@ self.new_op(LoadCallable(target="source")) self.new_op(temp) self.new_op(StoreCallable(source="source")) - - # Prevent the above instruction from being modified. - - self.new_op(temp.copy()) + self.new_op(temp) #self.discard_temp(temp) else: self.new_op(LoadFunction(fn)) @@ -1024,7 +1018,7 @@ self.discard_value() if dynamic: - return temp.copy() + return temp else: return None @@ -1224,7 +1218,7 @@ self._populateSequence(temp, node) - self.new_op(temp.copy()) + self.new_op(temp) self.discard_temp(temp) def _generateList(self, node): @@ -1248,7 +1242,7 @@ self.assign_value() self.discard_value() - self.new_op(list_temp.copy()) + self.new_op(list_temp) self.discard_temp(temp) self.discard_temp(list_temp) diff -r 3e1478c9fb01 -r 04c6f309c52f tests/call_func_variables.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/call_func_variables.py Mon Sep 05 00:16:33 2011 +0200 @@ -0,0 +1,11 @@ +#!/usr/bin/env python + +def f(a, b, c): + return c + +a = 1 +b = 2 +c = 3 +result1_3 = f(a, b, c) + +# vim: tabstop=4 expandtab shiftwidth=4