paul@154 | 1 | #!/usr/bin/env python |
paul@154 | 2 | |
paul@154 | 3 | """ |
paul@154 | 4 | Optimise code produced by the AST translator. |
paul@154 | 5 | |
paul@154 | 6 | Copyright (C) 2007, 2008 Paul Boddie <paul@boddie.org.uk> |
paul@154 | 7 | |
paul@154 | 8 | This program is free software; you can redistribute it and/or modify it under |
paul@154 | 9 | the terms of the GNU General Public License as published by the Free Software |
paul@154 | 10 | Foundation; either version 3 of the License, or (at your option) any later |
paul@154 | 11 | version. |
paul@154 | 12 | |
paul@154 | 13 | This program is distributed in the hope that it will be useful, but WITHOUT |
paul@154 | 14 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
paul@154 | 15 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more |
paul@154 | 16 | details. |
paul@154 | 17 | |
paul@154 | 18 | You should have received a copy of the GNU General Public License along with |
paul@154 | 19 | this program. If not, see <http://www.gnu.org/licenses/>. |
paul@154 | 20 | """ |
paul@154 | 21 | |
paul@154 | 22 | from micropython.common import * |
paul@155 | 23 | from micropython.data import * |
paul@154 | 24 | from micropython.rsvp import * |
paul@154 | 25 | |
paul@154 | 26 | class Optimiser: |
paul@154 | 27 | |
paul@154 | 28 | "A code optimiser." |
paul@154 | 29 | |
paul@154 | 30 | supported_optimisations = [ |
paul@155 | 31 | "constant_storage", "constant_accessor", "known_target", "self_access", |
paul@155 | 32 | "temp_storage", "load_operations", "no_operations", "unused_results" |
paul@154 | 33 | ] |
paul@154 | 34 | |
paul@154 | 35 | def __init__(self, translation, optimisations=None): |
paul@154 | 36 | |
paul@154 | 37 | """ |
paul@154 | 38 | Provide for the given 'translation' an optimiser for the desired |
paul@154 | 39 | 'optimisations'. See the 'supported_optimisations' attribute of this |
paul@154 | 40 | class for permitted values. |
paul@154 | 41 | """ |
paul@154 | 42 | |
paul@154 | 43 | self.translation = translation |
paul@154 | 44 | self.optimisations = set(optimisations or []) |
paul@154 | 45 | |
paul@154 | 46 | # The current "active" instruction. |
paul@154 | 47 | # As a rule, this will become the last instruction, but some |
paul@154 | 48 | # control-flow operations will flush the "active" instruction. |
paul@154 | 49 | |
paul@154 | 50 | self.active = None |
paul@154 | 51 | |
paul@154 | 52 | # The instruction providing the active value. |
paul@154 | 53 | |
paul@154 | 54 | self.active_value = None |
paul@154 | 55 | |
paul@154 | 56 | def reset(self): |
paul@154 | 57 | |
paul@154 | 58 | "Reset the optimiser, clearing the active instructions." |
paul@154 | 59 | |
paul@154 | 60 | self.clear_active_value() |
paul@154 | 61 | self.clear_active() |
paul@154 | 62 | |
paul@154 | 63 | def set_new(self, op): |
paul@154 | 64 | |
paul@154 | 65 | "Set the latest 'op' as the active instruction." |
paul@154 | 66 | |
paul@154 | 67 | self.set_active(op) |
paul@154 | 68 | self.set_active_value(op) |
paul@154 | 69 | |
paul@154 | 70 | def set_active_value(self, op): |
paul@154 | 71 | |
paul@154 | 72 | "Set the value-providing active instruction." |
paul@154 | 73 | |
paul@154 | 74 | if isinstance(op, current_value_instructions): |
paul@154 | 75 | self.active_value = op |
paul@154 | 76 | |
paul@154 | 77 | def clear_active_value(self): |
paul@154 | 78 | |
paul@154 | 79 | "Clear the value-providing active instruction." |
paul@154 | 80 | |
paul@154 | 81 | self.active_value = None |
paul@154 | 82 | |
paul@154 | 83 | def remove_active_value(self): |
paul@154 | 84 | |
paul@156 | 85 | """ |
paul@156 | 86 | Remove the value-providing active instruction from the generated code, |
paul@156 | 87 | if appropriate, but keep a record of the active instruction itself. |
paul@156 | 88 | """ |
paul@154 | 89 | |
paul@154 | 90 | if self.active_value is self.active: |
paul@154 | 91 | removed = self.active |
paul@154 | 92 | self.translation.remove_op() |
paul@154 | 93 | return removed |
paul@154 | 94 | else: |
paul@154 | 95 | return None |
paul@154 | 96 | |
paul@154 | 97 | def set_source(self, expr): |
paul@154 | 98 | |
paul@154 | 99 | "Set the source of the active instruction to 'expr'." |
paul@154 | 100 | |
paul@154 | 101 | if self.active is not None: |
paul@154 | 102 | self.active.source = expr |
paul@154 | 103 | |
paul@154 | 104 | def set_active(self, op): |
paul@154 | 105 | |
paul@154 | 106 | "Set the active instruction." |
paul@154 | 107 | |
paul@154 | 108 | self.active = op |
paul@154 | 109 | |
paul@154 | 110 | def clear_active(self): |
paul@154 | 111 | |
paul@154 | 112 | "Clear the active instruction." |
paul@154 | 113 | |
paul@154 | 114 | self.active = None |
paul@154 | 115 | |
paul@154 | 116 | # Optimisation tests. |
paul@154 | 117 | |
paul@154 | 118 | def should_optimise_constant_storage(self): |
paul@154 | 119 | return "constant_storage" in self.optimisations |
paul@154 | 120 | |
paul@155 | 121 | def should_optimise_constant_accessor(self): |
paul@155 | 122 | return "constant_accessor" in self.optimisations |
paul@155 | 123 | |
paul@154 | 124 | def should_optimise_known_target(self): |
paul@154 | 125 | return "known_target" in self.optimisations |
paul@154 | 126 | |
paul@154 | 127 | def should_optimise_self_access(self): |
paul@154 | 128 | return "self_access" in self.optimisations |
paul@154 | 129 | |
paul@154 | 130 | def should_optimise_temp_storage(self): |
paul@154 | 131 | return "temp_storage" in self.optimisations |
paul@154 | 132 | |
paul@154 | 133 | def should_optimise_load_operations(self): |
paul@154 | 134 | return "load_operations" in self.optimisations |
paul@154 | 135 | |
paul@154 | 136 | def should_optimise_away_no_operations(self): |
paul@154 | 137 | return "no_operations" in self.optimisations |
paul@154 | 138 | |
paul@154 | 139 | def should_optimise_unused_results(self): |
paul@154 | 140 | return "unused_results" in self.optimisations |
paul@154 | 141 | |
paul@154 | 142 | # Simple tests. |
paul@154 | 143 | |
paul@154 | 144 | def is_constant_input(self, instruction): |
paul@154 | 145 | |
paul@154 | 146 | "Return whether 'instruction' provides a constant input." |
paul@154 | 147 | |
paul@154 | 148 | return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 or \ |
paul@154 | 149 | isinstance(instruction, LoadConst) |
paul@154 | 150 | |
paul@154 | 151 | def is_constant_target(self, instruction): |
paul@154 | 152 | |
paul@154 | 153 | "Return whether 'instruction' provides a constant target." |
paul@154 | 154 | |
paul@154 | 155 | return isinstance(instruction, (StoreName, StoreAddress)) and \ |
paul@154 | 156 | instruction.attr.assignments == 1 |
paul@154 | 157 | |
paul@154 | 158 | def is_simple_input(self, instruction): |
paul@154 | 159 | |
paul@154 | 160 | """ |
paul@154 | 161 | Return whether 'instruction' provides a simple input (typically a load |
paul@154 | 162 | instruction). A simple input is something which would be represented by |
paul@154 | 163 | a load operation from a CPU register or special memory location. |
paul@154 | 164 | """ |
paul@154 | 165 | |
paul@154 | 166 | return isinstance(instruction, (LoadConst, LoadName, LoadTemp, LoadResult, LoadException, LoadAddress)) |
paul@154 | 167 | |
paul@154 | 168 | def is_simple_input_user(self, instruction): |
paul@154 | 169 | |
paul@154 | 170 | """ |
paul@154 | 171 | Return whether 'instruction' can use simple input from the current |
paul@154 | 172 | value. Such instructions would, in a low-level implementation, be able |
paul@154 | 173 | to have the simple input registers as operands. |
paul@154 | 174 | """ |
paul@154 | 175 | |
paul@154 | 176 | return isinstance(instruction, ( |
paul@154 | 177 | StoreTemp, StoreFrame, StoreResult, StoreException, # as the value being stored |
paul@154 | 178 | LoadAddressContext, LoadAttr, LoadAttrIndex, # as the object being referenced |
paul@154 | 179 | StoreAttr, StoreAttrIndex, StoreCallable, # as the object being referenced |
paul@154 | 180 | LoadCallable, |
paul@154 | 181 | TestIdentity, TestIdentityAddress, CheckSelf, # as one of the operands |
paul@154 | 182 | CheckException, CheckFrame, MakeObject, |
paul@154 | 183 | LoadContext # as the object providing the result |
paul@154 | 184 | )) |
paul@154 | 185 | |
paul@154 | 186 | def is_resultant_no_operation(self, instruction): |
paul@154 | 187 | |
paul@154 | 188 | """ |
paul@154 | 189 | Return whether 'instruction' merely stores its input where the input |
paul@154 | 190 | originally came from. |
paul@154 | 191 | """ |
paul@154 | 192 | |
paul@154 | 193 | return ( |
paul@154 | 194 | isinstance(instruction.input, LoadTemp) and isinstance(instruction, StoreTemp) and |
paul@154 | 195 | instruction.input.attr == instruction.attr) or ( |
paul@154 | 196 | isinstance(instruction.input, LoadResult) and isinstance(instruction, StoreResult) |
paul@154 | 197 | ) |
paul@154 | 198 | |
paul@154 | 199 | def is_input(self, instruction): |
paul@154 | 200 | |
paul@154 | 201 | "Return whether 'instruction' provides an input." |
paul@154 | 202 | |
paul@154 | 203 | return isinstance(instruction, current_value_instructions) |
paul@154 | 204 | |
paul@154 | 205 | # Convenience tests on outputs. |
paul@154 | 206 | |
paul@154 | 207 | def have_constant_target(self): |
paul@154 | 208 | |
paul@154 | 209 | "Return whether the active instruction provides a constant target." |
paul@154 | 210 | |
paul@154 | 211 | return self.is_constant_target(self.active) |
paul@154 | 212 | |
paul@154 | 213 | def have_constant_source(self): |
paul@154 | 214 | |
paul@154 | 215 | "Return whether the active instruction has a constant source." |
paul@154 | 216 | |
paul@154 | 217 | return self.is_constant_input(self.active.source) |
paul@154 | 218 | |
paul@154 | 219 | # Convenience tests on inputs. |
paul@154 | 220 | |
paul@154 | 221 | def have_constant_input(self): |
paul@154 | 222 | |
paul@154 | 223 | "Return whether the active instruction provides a constant input." |
paul@154 | 224 | |
paul@154 | 225 | return self.is_constant_input(self.active_value) |
paul@154 | 226 | |
paul@154 | 227 | have_known_target = have_constant_input |
paul@154 | 228 | |
paul@154 | 229 | def have_simple_input(self): |
paul@154 | 230 | |
paul@154 | 231 | "Return whether the active instruction provides a simple input." |
paul@154 | 232 | |
paul@154 | 233 | return self.is_simple_input(self.active_value) |
paul@154 | 234 | |
paul@154 | 235 | def have_input(self): |
paul@154 | 236 | |
paul@154 | 237 | "Return whether the active instruction provides an input." |
paul@154 | 238 | |
paul@154 | 239 | return self.is_input(self.active_value) |
paul@154 | 240 | |
paul@154 | 241 | def have_self_input(self): |
paul@154 | 242 | |
paul@154 | 243 | "Return whether the active instruction is a reference to self." |
paul@154 | 244 | |
paul@154 | 245 | return isinstance(self.translation.unit, Function) and \ |
paul@154 | 246 | self.translation.unit.is_method() and isinstance(self.active_value, LoadName) and \ |
paul@154 | 247 | self.active_value.attr.name == "self" |
paul@154 | 248 | |
paul@154 | 249 | def have_temp_compatible_access(self): |
paul@154 | 250 | |
paul@154 | 251 | """ |
paul@154 | 252 | Indicate whether the active instruction can be used in place of access |
paul@154 | 253 | to a temporary variable retaining the result of the last instruction. |
paul@154 | 254 | """ |
paul@154 | 255 | |
paul@154 | 256 | # LoadResult cannot be relied upon in general since the result register |
paul@154 | 257 | # could be updated since first being referenced. |
paul@154 | 258 | |
paul@154 | 259 | return isinstance(self.active_value, (LoadName, LoadTemp, LoadAddress, LoadConst)) or \ |
paul@154 | 260 | isinstance(self.active_value, LoadResult) and self.active_value is self.active or \ |
paul@154 | 261 | isinstance(self.active_value, LoadException) and self.active_value is self.active |
paul@154 | 262 | |
paul@154 | 263 | def have_correct_self_for_target(self, context): |
paul@154 | 264 | |
paul@154 | 265 | "Return whether the 'context' is compatible with the current value." |
paul@154 | 266 | |
paul@154 | 267 | if context is not None and self.have_self_input(): |
paul@154 | 268 | |
paul@154 | 269 | parent = self.translation.unit.parent |
paul@154 | 270 | if parent is context or parent.has_subclass(context) or context.has_subclass(parent): |
paul@154 | 271 | return 1 |
paul@154 | 272 | |
paul@154 | 273 | return 0 |
paul@154 | 274 | |
paul@154 | 275 | # Optimisation methods. See the supported_optimisations class attribute. |
paul@154 | 276 | |
paul@154 | 277 | def optimise_constant_storage(self): |
paul@154 | 278 | |
paul@154 | 279 | """ |
paul@154 | 280 | Where the last operation stores a constant into a target which is also |
paul@156 | 281 | constant, indicate that both operations should be optimised away. |
paul@154 | 282 | """ |
paul@154 | 283 | |
paul@156 | 284 | return self.should_optimise_constant_storage() and \ |
paul@154 | 285 | self.have_constant_target() and \ |
paul@156 | 286 | self.have_constant_source() |
paul@154 | 287 | |
paul@155 | 288 | def optimise_constant_accessor(self): |
paul@155 | 289 | |
paul@155 | 290 | """ |
paul@155 | 291 | Where the object whose attribute is being accessed is constant, provide |
paul@155 | 292 | information about its full name. |
paul@155 | 293 | """ |
paul@155 | 294 | |
paul@155 | 295 | if self.should_optimise_constant_accessor() and self.have_constant_input(): |
paul@155 | 296 | value = self.active_value |
paul@155 | 297 | |
paul@155 | 298 | # Get the details of the access. |
paul@155 | 299 | |
paul@155 | 300 | if isinstance(value.attr, Const): |
paul@155 | 301 | target_name = value.attr.value_type_name() |
paul@155 | 302 | else: |
paul@155 | 303 | target = value.attr.value |
paul@155 | 304 | |
paul@155 | 305 | if isinstance(target, Const): |
paul@155 | 306 | return target.value_type_name() |
paul@155 | 307 | elif isinstance(target, Instance): |
paul@155 | 308 | return None # skip production of optimised code |
paul@155 | 309 | else: |
paul@155 | 310 | return target.full_name() |
paul@155 | 311 | |
paul@155 | 312 | else: |
paul@155 | 313 | return None |
paul@155 | 314 | |
paul@154 | 315 | def optimise_known_target(self): |
paul@154 | 316 | |
paul@154 | 317 | """ |
paul@154 | 318 | Where the target of an invocation is known, provide information about it |
paul@154 | 319 | and its context. If a class is being invoked and the conditions are |
paul@154 | 320 | appropriate, get information about the specific initialiser. |
paul@154 | 321 | """ |
paul@154 | 322 | |
paul@154 | 323 | if self.should_optimise_known_target() and self.have_known_target(): |
paul@154 | 324 | value = self.active_value |
paul@154 | 325 | target = value.attr.value |
paul@154 | 326 | context = value.attr.context |
paul@154 | 327 | |
paul@154 | 328 | return target, context |
paul@154 | 329 | else: |
paul@154 | 330 | return None |
paul@154 | 331 | |
paul@156 | 332 | def optimise_self_access(self, unit, attrname): |
paul@154 | 333 | |
paul@154 | 334 | """ |
paul@156 | 335 | Return whether code in the given 'unit' is able to access the given |
paul@156 | 336 | 'attrname' through the same position in all possible objects which might |
paul@156 | 337 | be accessed. |
paul@154 | 338 | """ |
paul@154 | 339 | |
paul@156 | 340 | return self.should_optimise_self_access() and \ |
paul@156 | 341 | self.have_self_input() and not unit.is_relocated(attrname) |
paul@154 | 342 | |
paul@154 | 343 | def optimise_temp_storage(self): |
paul@154 | 344 | |
paul@154 | 345 | """ |
paul@154 | 346 | Where the next operation would involve storing a value into temporary |
paul@154 | 347 | storage at 'temp_position', record and remove any simple instruction |
paul@154 | 348 | which produced the value to be stored such that instead of subsequently |
paul@154 | 349 | accessing the temporary storage, that instruction is substituted. |
paul@154 | 350 | |
paul@154 | 351 | If no optimisation can be achieved, a StoreTemp instruction is produced |
paul@154 | 352 | and the appropriate LoadTemp instruction is returned. |
paul@154 | 353 | |
paul@154 | 354 | Restriction: for use only in situations where the source of the |
paul@154 | 355 | temporary data will not be disturbed between its first access and its |
paul@154 | 356 | subsequent use. |
paul@154 | 357 | """ |
paul@154 | 358 | |
paul@154 | 359 | if self.should_optimise_temp_storage() and \ |
paul@154 | 360 | self.have_temp_compatible_access(): |
paul@154 | 361 | |
paul@154 | 362 | # Remove the active value contributor. |
paul@154 | 363 | |
paul@154 | 364 | removed = self.remove_active_value() |
paul@154 | 365 | |
paul@154 | 366 | # Extend the lifetime of any temporary storage location. |
paul@154 | 367 | |
paul@154 | 368 | self.translation.ensure_temp(removed) |
paul@154 | 369 | return removed |
paul@154 | 370 | else: |
paul@154 | 371 | return self.translation.get_temp() |
paul@154 | 372 | |
paul@154 | 373 | def optimise_load_operations(self, instruction): |
paul@154 | 374 | |
paul@154 | 375 | """ |
paul@154 | 376 | Incorporate previous load operations into other operations. |
paul@154 | 377 | """ |
paul@154 | 378 | |
paul@154 | 379 | if self.should_optimise_load_operations() and \ |
paul@154 | 380 | self.have_simple_input() and \ |
paul@154 | 381 | self.is_simple_input_user(instruction): |
paul@154 | 382 | |
paul@154 | 383 | self.remove_active_value() |
paul@154 | 384 | instruction.input = self.active_value |
paul@154 | 385 | |
paul@154 | 386 | def optimise_away_no_operations(self, instruction): |
paul@154 | 387 | |
paul@154 | 388 | """ |
paul@154 | 389 | Optimise away operations which just store their inputs in the place |
paul@154 | 390 | the inputs originally came from. |
paul@154 | 391 | """ |
paul@154 | 392 | |
paul@156 | 393 | return self.should_optimise_away_no_operations() and \ |
paul@156 | 394 | self.is_resultant_no_operation(instruction) |
paul@154 | 395 | |
paul@154 | 396 | def optimise_unused_results(self): |
paul@154 | 397 | |
paul@154 | 398 | "Discard results which will not be used." |
paul@154 | 399 | |
paul@154 | 400 | if self.should_optimise_unused_results() and self.have_simple_input(): |
paul@154 | 401 | self.remove_active_value() |
paul@154 | 402 | |
paul@154 | 403 | # vim: tabstop=4 expandtab shiftwidth=4 |