1.1 --- a/TO_DO.txt Thu Sep 01 00:35:47 2011 +0200
1.2 +++ b/TO_DO.txt Mon Sep 05 00:16:33 2011 +0200
1.3 @@ -13,11 +13,11 @@
1.4 Move common code sequences to a library routine, such as the context checking that occurs
1.5 in functions and methods.
1.6
1.7 -Return Value Optimisations
1.8 -==========================
1.9 +Dataflow Optimisations
1.10 +======================
1.11
1.12 -Attempt to use result data directly instead of transferring it explicitly to the working
1.13 -registers and then using it.
1.14 +Assignments, particularly now that no result register exists, may cause StoreTemp/LoadTemp
1.15 +instruction pairs to be produced and these could be eliminated.
1.16
1.17 Class and Module Attribute Assignment
1.18 =====================================
2.1 --- a/micropython/ast.py Thu Sep 01 00:35:47 2011 +0200
2.2 +++ b/micropython/ast.py Mon Sep 05 00:16:33 2011 +0200
2.3 @@ -473,7 +473,7 @@
2.4 self.new_op(temp_getitem)
2.5 temp_target, target, temp_context = self._generateCallFunc([compiler.ast.Const(i)], node)
2.6 self._doCallFunc(temp_target, target)
2.7 - self._endCallFunc()
2.8 + self._endCallFunc(temp_context=temp_context)
2.9
2.10 # Provide a different source value.
2.11 # NOTE: Permitting immediate usage given that neither name nor
2.12 @@ -620,12 +620,6 @@
2.13
2.14 self.dispatch(n)
2.15
2.16 - # Discard temporary storage.
2.17 -
2.18 - if self.temp_positions:
2.19 - #print "Had temp", self.temp_positions
2.20 - self.temp_positions = set()
2.21 -
2.22 # Prevent incorrect optimisation by resetting the optimiser after
2.23 # each statement.
2.24
3.1 --- a/micropython/code.py Thu Sep 01 00:35:47 2011 +0200
3.2 +++ b/micropython/code.py Mon Sep 05 00:16:33 2011 +0200
3.3 @@ -126,8 +126,8 @@
3.4
3.5 """
3.6 Record the current active value for an assignment. If the optional
3.7 - 'immediate' parameter if set to a false value always allocates new
3.8 - temporary storage to hold the recorded value; otherwise, the
3.9 + 'immediate' parameter is set to a false value, new temporary storage to
3.10 + hold the recorded value will be allocated; otherwise, the
3.11 value-providing instruction may be replicated in order to provide the
3.12 active value later on.
3.13 """
3.14 @@ -163,10 +163,31 @@
3.15 # Otherwise, insert the assignment source.
3.16
3.17 if expr is not None:
3.18 - expr = expr.copy()
3.19 - expr.target = "source"
3.20 - self.insert_op(-1, expr)
3.21 - self.last_op().source = "source"
3.22 + expr_copy = expr.copy()
3.23 + assign_op = self.last_op()
3.24 +
3.25 + # Either insert the instruction yielding the value and adjust the
3.26 + # assignment source.
3.27 +
3.28 + expr_copy.target = "source"
3.29 +
3.30 + if self.insert_op(-1, expr_copy):
3.31 + assign_op.source = "source"
3.32 + self.update_temp(expr, expr_copy)
3.33 +
3.34 + # (Now, the instruction need not be inserted.)
3.35 +
3.36 + # Or transfer the working value to the source register.
3.37 +
3.38 + elif assign_op.working == "working":
3.39 + self.insert_op(-1, Transfer(source="working_context", target="source_context"))
3.40 + self.insert_op(-1, Transfer(source="working", target="source"))
3.41 + assign_op.source = "source"
3.42 +
3.43 + # Or let the assignment use the working register.
3.44 +
3.45 + else:
3.46 + assign_op.source = "working"
3.47
3.48 def set_target(self, target):
3.49
3.50 @@ -198,13 +219,34 @@
3.51 def get_temp(self):
3.52
3.53 """
3.54 - Add a temporary storage instruction for the current value and return a
3.55 - sequence of access instructions.
3.56 + Return a temporary storage access instruction for the current value.
3.57 + Initially, this instruction is not associated with an allocated unit of
3.58 + temporary storage, and if used as a new instruction will not be added to
3.59 + the code, but if the current value changes, the 'set_temp' method will
3.60 + be called by the optimiser and a unit of storage will be allocated.
3.61 """
3.62
3.63 - position_in_frame = self.reserve_temp()
3.64 - self.new_op(StoreTemp(position_in_frame))
3.65 - return LoadTemp(position_in_frame)
3.66 + temp = LoadTemp(None)
3.67 + self.optimiser.request_active_value(temp, self.blocks[-1], len(self.blocks[-1].code))
3.68 + return temp
3.69 +
3.70 + def set_temp(self, temp, block, pos):
3.71 +
3.72 + """
3.73 + Emit a storage instruction for the given 'temp' loading instruction,
3.74 + reserving a new temporary storage location.
3.75 + """
3.76 +
3.77 + if temp.attr is None:
3.78 + temp.attr = self.reserve_temp()
3.79 + block.insert(pos, StoreTemp(temp.attr))
3.80 +
3.81 + def update_temp(self, temp, updated):
3.82 +
3.83 + "Update 'temp' using the given 'updated' instruction."
3.84 +
3.85 + if isinstance(temp, LoadTemp):
3.86 + temp.attr = updated.attr
3.87
3.88 def reserve_temp(self, temp_position=None):
3.89
3.90 @@ -240,9 +282,10 @@
3.91
3.92 "Discard any temporary storage position used by 'instruction'."
3.93
3.94 - if isinstance(instruction, LoadTemp):
3.95 + if isinstance(instruction, LoadTemp) and instruction.attr is not None:
3.96 temp_position = instruction.attr - self.unit.all_local_usage
3.97 self.free_temp(temp_position)
3.98 + self.optimiser.ignore_active_value()
3.99
3.100 def free_temp(self, temp_position):
3.101
3.102 @@ -276,22 +319,41 @@
3.103 was added.
3.104 """
3.105
3.106 - # Optimise load operations employed by this instruction.
3.107 -
3.108 - if self.optimiser.optimise_away_no_operations(op) or self.optimiser.optimise_unused_handlers(op):
3.109 + if not self.check_op(op):
3.110 return 0
3.111
3.112 # Add the operation to the current block.
3.113
3.114 - self.blocks[-1].code.append(op)
3.115 self.optimiser.set_new(op)
3.116 + self.blocks[-1].append(op)
3.117 return 1
3.118
3.119 def insert_op(self, i, op):
3.120
3.121 "Insert at index 'i' in the current block the instruction 'op'."
3.122
3.123 - self.blocks[-1].code.insert(i, op)
3.124 + if not self.check_op(op):
3.125 + return 0
3.126 +
3.127 + self.blocks[-1].insert(i, op)
3.128 + return 1
3.129 +
3.130 + def check_op(self, op):
3.131 +
3.132 + "Return whether the given 'op' is to be added to the code."
3.133 +
3.134 + # Optimise away temporary storage instructions where the active value is
3.135 + # still available and was not recorded.
3.136 +
3.137 + if isinstance(op, LoadTemp) and op.attr is None:
3.138 + return 0
3.139 +
3.140 + # Optimise load operations employed by this instruction.
3.141 +
3.142 + if self.optimiser.optimise_away_no_operations(op) or self.optimiser.optimise_unused_handlers(op):
3.143 + return 0
3.144 +
3.145 + return 1
3.146
3.147 def remove_op(self):
3.148
4.1 --- a/micropython/opt.py Thu Sep 01 00:35:47 2011 +0200
4.2 +++ b/micropython/opt.py Mon Sep 05 00:16:33 2011 +0200
4.3 @@ -52,6 +52,9 @@
4.4 # control-flow operations will flush the "active" instruction.
4.5
4.6 self.active = None
4.7 + self.saved_value_op = None
4.8 + self.saved_value_block = None
4.9 + self.saved_value_pos = None
4.10
4.11 # Instructions providing the active value.
4.12
4.13 @@ -83,6 +86,7 @@
4.14 collecting the active instructions from each of the blocks otherwise.
4.15 """
4.16
4.17 + self.store_active_value()
4.18 self.clear_active()
4.19
4.20 # Make a new collection of instructions for a new block.
4.21 @@ -111,7 +115,8 @@
4.22
4.23 "Set the value-providing active instruction."
4.24
4.25 - if isinstance(op, current_value_instructions) and op.target == "working":
4.26 + if affects_register(op, "working"):
4.27 + self.store_active_value()
4.28 self.active_values.clear()
4.29 self.active_values.add(op)
4.30
4.31 @@ -157,6 +162,36 @@
4.32
4.33 self.active = None
4.34
4.35 + # Permit the active value to be requested and restored.
4.36 +
4.37 + def request_active_value(self, temp, block, pos):
4.38 +
4.39 + """
4.40 + Request the current active value so that if the value is changed, a
4.41 + temporary storage element or equivalent will be allocated.
4.42 + """
4.43 +
4.44 + self.store_active_value()
4.45 + self.saved_value_op = temp
4.46 + self.saved_value_block = block
4.47 + self.saved_value_pos = pos
4.48 +
4.49 + def store_active_value(self):
4.50 +
4.51 + "Store the requested active value"
4.52 +
4.53 + if self.saved_value_op is not None:
4.54 + self.translation.set_temp(self.saved_value_op, self.saved_value_block, self.saved_value_pos)
4.55 + self.ignore_active_value()
4.56 +
4.57 + def ignore_active_value(self):
4.58 +
4.59 + "Ignore the active value."
4.60 +
4.61 + self.saved_value_op = None
4.62 + self.saved_value_block = None
4.63 + self.saved_value_pos = None
4.64 +
4.65 # Optimisation tests.
4.66
4.67 def should_optimise_constant_storage(self):
4.68 @@ -218,15 +253,17 @@
4.69 LoadName, LoadTemp, LoadAddress
4.70 ))
4.71
4.72 - def is_resultant_no_operation(self, instruction):
4.73 + def is_resultant_no_operation(self, instruction, last_op=None):
4.74
4.75 """
4.76 Return whether 'instruction' merely stores its input where the input
4.77 originally came from.
4.78 """
4.79
4.80 - return (
4.81 - isinstance(instruction, StoreTemp) and instruction.target == instruction.source
4.82 + last_op = last_op or self.translation.last_op()
4.83 + return last_op and last_op.attr == instruction.attr and (
4.84 + isinstance(instruction, StoreTemp) and isinstance(last_op, LoadTemp) or
4.85 + isinstance(instruction, StoreAddress) and isinstance(last_op, LoadAddress)
4.86 )
4.87
4.88 # Convenience tests on outputs.
4.89 @@ -377,7 +414,7 @@
4.90 value to be stored such that instead of subsequently accessing the
4.91 temporary storage, that instruction is substituted.
4.92
4.93 - If no optimisation can be achieved, a StoreTemp instruction is produced
4.94 + If no optimisation can be achieved, temporary storage is requested
4.95 and the appropriate LoadTemp instruction is returned.
4.96
4.97 Restriction: for use only in situations where the source of the
4.98 @@ -388,7 +425,7 @@
4.99 if self.should_optimise_temp_storage() and \
4.100 self.have_temp_compatible_access():
4.101
4.102 - # Remove the active value contributor.
4.103 + # Remove the active value contributor if possible.
4.104
4.105 removed = self.remove_active_value()
4.106 if removed is not None:
4.107 @@ -398,9 +435,14 @@
4.108 self.translation.ensure_temp(removed)
4.109 return removed
4.110
4.111 + # Otherwise, just leave it in place, but return the instruction.
4.112 +
4.113 + else:
4.114 + return self.get_active_value()
4.115 +
4.116 return self.translation.get_temp()
4.117
4.118 - def optimise_away_no_operations(self, instruction):
4.119 + def optimise_away_no_operations(self, instruction, last_op=None):
4.120
4.121 """
4.122 Optimise away operations which just store their inputs in the place
4.123 @@ -408,7 +450,7 @@
4.124 """
4.125
4.126 return self.should_optimise_away_no_operations() and \
4.127 - self.is_resultant_no_operation(instruction)
4.128 + self.is_resultant_no_operation(instruction, last_op)
4.129
4.130 def optimise_unused_results(self):
4.131
5.1 --- a/micropython/program.py Thu Sep 01 00:35:47 2011 +0200
5.2 +++ b/micropython/program.py Mon Sep 05 00:16:33 2011 +0200
5.3 @@ -37,6 +37,12 @@
5.4 def get_active_values(self):
5.5 return self.active_values
5.6
5.7 + def insert(self, pos, op):
5.8 + self.code.insert(pos, op)
5.9 +
5.10 + def append(self, op):
5.11 + self.code.append(op)
5.12 +
5.13 class DataValue:
5.14
5.15 "A representation of a raw program value."
6.1 --- a/micropython/rsvp.py Thu Sep 01 00:35:47 2011 +0200
6.2 +++ b/micropython/rsvp.py Mon Sep 05 00:16:33 2011 +0200
6.3 @@ -297,14 +297,18 @@
6.4
6.5 "A generic instruction."
6.6
6.7 + default_working = "working"
6.8 + default_target = "working"
6.9 + default_source = None
6.10 +
6.11 # NOTE: Ultimately, instructions apart from Transfer will use specific
6.12 # NOTE: registers such as "working_value" and "working_context".
6.13
6.14 - def __init__(self, attr=None, working="working", target="working", source=None):
6.15 + def __init__(self, attr=None, working=None, target=None, source=None):
6.16 self.attr = attr
6.17 - self.working = working
6.18 - self.target = target
6.19 - self.source = source
6.20 + self.working = working or self.default_working
6.21 + self.target = target or self.default_target
6.22 + self.source = source or self.default_source
6.23
6.24 def get_details(self):
6.25 return self.__class__, self.attr, self.working, self.target, self.source
6.26 @@ -333,13 +337,13 @@
6.27 return repr(operand)
6.28
6.29 def format_working(self):
6.30 - return self.working != "working" and (", working=%r" % self.working) or ""
6.31 + return self.working != self.default_working and (", working=%r" % self.working) or ""
6.32
6.33 def format_source(self):
6.34 - return self.source is not None and (", source=%r" % self.source) or ""
6.35 + return self.source != self.default_source and (", source=%r" % self.source) or ""
6.36
6.37 def format_target(self):
6.38 - return self.target != "working" and (", target=%r" % self.target) or ""
6.39 + return self.target != self.default_target and (", target=%r" % self.target) or ""
6.40
6.41 def get_operand(self):
6.42 return None
6.43 @@ -463,6 +467,7 @@
6.44 class StoreName(FR):
6.45 "Store the source value into the given local attribute/variable."
6.46 cost = 2
6.47 + default_target = None
6.48
6.49 class LoadTemp(Immediate):
6.50 "Load the current value from the given temporary location."
6.51 @@ -471,6 +476,7 @@
6.52 class StoreTemp(Immediate):
6.53 "Store the current value into the given temporary location."
6.54 cost = 2
6.55 + default_target = None
6.56
6.57 # Access to static data.
6.58
6.59 @@ -481,6 +487,8 @@
6.60 class StoreAddress(Address):
6.61 "Store the source value into the given fixed attribute address."
6.62 cost = 1
6.63 + default_working = None
6.64 + default_target = None
6.65
6.66 class LoadAddressContext(Address):
6.67 "Load the current value from the given fixed attribute address, using the current value as context."
6.68 @@ -489,6 +497,7 @@
6.69 class StoreAddressContext(Address):
6.70 "Store the current value into the given fixed attribute address, using the current value as context."
6.71 cost = 2
6.72 + default_target = None
6.73
6.74 class LoadAddressContextCond(Address):
6.75 """
6.76 @@ -514,6 +523,7 @@
6.77 class StoreAttr(AR):
6.78 "Store the source value into the given attribute of the object referenced by the current value."
6.79 cost = 2
6.80 + default_target = None
6.81
6.82 class LoadAttrIndex(Immediate):
6.83 "Load into the current value the attribute of the current value with the given index."
6.84 @@ -522,6 +532,7 @@
6.85 class StoreAttrIndex(Immediate):
6.86 "Store the source value into the attribute of the current value with the given index."
6.87 cost = 6
6.88 + default_target = None
6.89
6.90 class LoadAttrIndexContextCond(Immediate):
6.91 """
6.92 @@ -539,28 +550,34 @@
6.93 class StoreCallable(Instruction):
6.94 "Store the source value into the object referenced by the current value."
6.95 cost = 3
6.96 + default_target = None
6.97
6.98 # Access to invocation frames in preparation.
6.99
6.100 class MakeFrame(Immediate):
6.101 "Make a new invocation frame."
6.102 cost = 2
6.103 + default_target = None
6.104
6.105 class AdjustFrame(Immediate):
6.106 "Adjust the current invocation frame for corrected invocations."
6.107 cost = 2
6.108 + default_target = None
6.109
6.110 class DropFrame(Instruction):
6.111 "Drop an invocation frame."
6.112 cost = 2
6.113 + default_target = None
6.114
6.115 class StoreFrame(Immediate):
6.116 "Store the current value as an argument for the parameter with the given position."
6.117 cost = 2
6.118 + default_target = None
6.119
6.120 class StoreFrameIndex(Immediate):
6.121 "Store the source value as an argument of the current value for the parameter with the given index."
6.122 cost = 6
6.123 + default_target = None
6.124
6.125 # Context-related tests.
6.126
6.127 @@ -592,10 +609,12 @@
6.128 class FillDefaults(Immediate):
6.129 "Fill frame positions with defaults, if appropriate."
6.130 cost = 8 # variable
6.131 + default_target = None
6.132
6.133 class ExtendFrame(Immediate):
6.134 "Extend the current frame for temporary storage use."
6.135 cost = 1
6.136 + default_target = None
6.137
6.138 class CopyExtra(Immediate):
6.139 "Copy extra arguments into a separate sequence, starting from the given position."
6.140 @@ -606,46 +625,56 @@
6.141 class JumpInFrame(Instruction):
6.142 "Jump, using the current locals, to the current callable."
6.143 cost = 2
6.144 + default_target = None
6.145
6.146 class JumpWithFrame(Instruction):
6.147 "Jump, adopting the invocation frame, to the current callable."
6.148 cost = 3
6.149 + default_target = None
6.150
6.151 class JumpWithFrameDirect(Target):
6.152 "Jump to the specified address, adopting the invocation frame."
6.153 cost = 3
6.154 + default_target = None
6.155
6.156 class Return(Instruction):
6.157 "Return from a subprogram."
6.158 cost = 2
6.159 + default_target = None
6.160
6.161 # Branch-related instructions.
6.162
6.163 class Jump(Address):
6.164 "Jump unconditionally."
6.165 cost = 1
6.166 + default_target = None
6.167
6.168 class JumpIfFalse(Address):
6.169 "Jump if the last evaluation gave a false result."
6.170 cost = 2
6.171 + default_target = None
6.172
6.173 class JumpIfTrue(Address):
6.174 "Jump if the last evaluation gave a true result."
6.175 cost = 2
6.176 + default_target = None
6.177
6.178 # Exception-related instructions, using a special exception "register".
6.179
6.180 class RaiseException(Instruction):
6.181 "Raise an exception, jumping to the active handler."
6.182 cost = 2
6.183 + default_target = None
6.184
6.185 class PushHandler(Address):
6.186 "Push an exception handler onto the handler stack."
6.187 cost = 3
6.188 + default_target = None
6.189
6.190 class PopHandler(Immediate):
6.191 "Pop exception handlers from the handler stack."
6.192 cost = 3
6.193 + default_target = None
6.194
6.195 class CheckException(Instruction):
6.196 "Check the raised exception against another."
6.197 @@ -671,16 +700,15 @@
6.198
6.199 # Instructions which can affect the current value. (LoadAttrIndexContext not defined.)
6.200
6.201 -current_value_instructions = (
6.202 - Transfer,
6.203 - LoadConst, LoadClass, LoadFunction,
6.204 - LoadName, LoadTemp,
6.205 - LoadAddress, LoadAddressContext, LoadAddressContextCond,
6.206 - LoadAttr, LoadAttrIndex, LoadAttrIndexContextCond,
6.207 - LoadCallable,
6.208 - MakeInstance, MakeFragment,
6.209 - CopyExtra,
6.210 - CheckClass, CheckContext, CheckException, CheckInstance, CheckFrame, CheckExtra
6.211 - )
6.212 +def affects_register(instruction, register):
6.213 +
6.214 + """
6.215 + Returns whether 'instruction' affects the given 'register', either directly
6.216 + or as a consequence of its execution.
6.217 + """
6.218 +
6.219 + return instruction.target == register or isinstance(instruction, (
6.220 + JumpWithFrame, JumpWithFrameDirect, JumpIfTrue, JumpIfFalse, Jump
6.221 + ))
6.222
6.223 # vim: tabstop=4 expandtab shiftwidth=4
7.1 --- a/micropython/trans.py Thu Sep 01 00:35:47 2011 +0200
7.2 +++ b/micropython/trans.py Mon Sep 05 00:16:33 2011 +0200
7.3 @@ -351,7 +351,7 @@
7.4
7.5 # Recall the accessor.
7.6
7.7 - self.new_op(temp_accessor.copy())
7.8 + self.new_op(temp_accessor)
7.9
7.10 # Otherwise, perform a normal operation.
7.11
7.12 @@ -777,9 +777,10 @@
7.13 # Check the current value (the argument) against the known context
7.14 # (given as the source).
7.15
7.16 - temp_context = temp_context.copy()
7.17 - temp_context.target = "source"
7.18 - self.new_op(temp_context)
7.19 + if self.new_op(temp_context.copy()):
7.20 + self.last_op().target = "source"
7.21 + self.update_temp(temp_context, self.last_op())
7.22 +
7.23 self.new_op(temp_first_argument)
7.24 self.new_op(CheckInstance(source="source", target="status"))
7.25
7.26 @@ -824,7 +825,7 @@
7.27 self.frame_makers[-1].attr = nargs
7.28 self.frame_makers.pop()
7.29
7.30 - def _endCallFunc(self, temp_target=None, temp_context=None, load_result=1):
7.31 + def _endCallFunc(self, temp_target=None, temp_context=None):
7.32
7.33 "Finish the invocation and tidy up afterwards."
7.34
7.35 @@ -838,10 +839,6 @@
7.36 if temp_context is not None:
7.37 self.discard_temp(temp_context)
7.38
7.39 - # Reset the active values.
7.40 -
7.41 - self.optimiser.reset()
7.42 -
7.43 def _visitFunctionDeclaration(self, node):
7.44
7.45 """
7.46 @@ -861,10 +858,7 @@
7.47 self.new_op(LoadCallable(target="source"))
7.48 self.new_op(temp)
7.49 self.new_op(StoreCallable(source="source"))
7.50 -
7.51 - # Prevent the above instruction from being modified.
7.52 -
7.53 - self.new_op(temp.copy())
7.54 + self.new_op(temp)
7.55 #self.discard_temp(temp)
7.56 else:
7.57 self.new_op(LoadFunction(fn))
7.58 @@ -1024,7 +1018,7 @@
7.59 self.discard_value()
7.60
7.61 if dynamic:
7.62 - return temp.copy()
7.63 + return temp
7.64 else:
7.65 return None
7.66
7.67 @@ -1224,7 +1218,7 @@
7.68
7.69 self._populateSequence(temp, node)
7.70
7.71 - self.new_op(temp.copy())
7.72 + self.new_op(temp)
7.73 self.discard_temp(temp)
7.74
7.75 def _generateList(self, node):
7.76 @@ -1248,7 +1242,7 @@
7.77 self.assign_value()
7.78 self.discard_value()
7.79
7.80 - self.new_op(list_temp.copy())
7.81 + self.new_op(list_temp)
7.82 self.discard_temp(temp)
7.83 self.discard_temp(list_temp)
7.84
8.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
8.2 +++ b/tests/call_func_variables.py Mon Sep 05 00:16:33 2011 +0200
8.3 @@ -0,0 +1,11 @@
8.4 +#!/usr/bin/env python
8.5 +
8.6 +def f(a, b, c):
8.7 + return c
8.8 +
8.9 +a = 1
8.10 +b = 2
8.11 +c = 3
8.12 +result1_3 = f(a, b, c)
8.13 +
8.14 +# vim: tabstop=4 expandtab shiftwidth=4