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@450 | 6 | Copyright (C) 2007, 2008, 2009, 2010, 2011 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@167 | 31 | # Code generation optimisations: |
paul@155 | 32 | "constant_storage", "constant_accessor", "known_target", "self_access", |
paul@450 | 33 | "temp_storage", "no_operations", "unused_results", |
paul@268 | 34 | "unused_handlers", "accesses_by_usage", |
paul@167 | 35 | # Inspection optimisations: |
paul@167 | 36 | "unused_objects" |
paul@154 | 37 | ] |
paul@154 | 38 | |
paul@154 | 39 | def __init__(self, translation, optimisations=None): |
paul@154 | 40 | |
paul@154 | 41 | """ |
paul@154 | 42 | Provide for the given 'translation' an optimiser for the desired |
paul@154 | 43 | 'optimisations'. See the 'supported_optimisations' attribute of this |
paul@154 | 44 | class for permitted values. |
paul@154 | 45 | """ |
paul@154 | 46 | |
paul@154 | 47 | self.translation = translation |
paul@154 | 48 | self.optimisations = set(optimisations or []) |
paul@154 | 49 | |
paul@154 | 50 | # The current "active" instruction. |
paul@154 | 51 | # As a rule, this will become the last instruction, but some |
paul@154 | 52 | # control-flow operations will flush the "active" instruction. |
paul@154 | 53 | |
paul@154 | 54 | self.active = None |
paul@464 | 55 | self.saved_value_op = None |
paul@464 | 56 | self.saved_value_block = None |
paul@464 | 57 | self.saved_value_pos = None |
paul@154 | 58 | |
paul@452 | 59 | # Instructions providing the active value. |
paul@154 | 60 | |
paul@452 | 61 | self.active_values = set() |
paul@154 | 62 | |
paul@405 | 63 | def get_attribute_store_instructions(self): |
paul@405 | 64 | |
paul@405 | 65 | """ |
paul@405 | 66 | Return an appropriate set of instructions available when storing |
paul@405 | 67 | attributes. |
paul@405 | 68 | """ |
paul@405 | 69 | |
paul@405 | 70 | ca = self.should_optimise_accesses_by_attribute_usage() |
paul@405 | 71 | |
paul@405 | 72 | return ( |
paul@405 | 73 | ca and StoreAddress or None, # plain assignment |
paul@405 | 74 | ca and StoreAddressContext or None, # assignment via class |
paul@405 | 75 | ca and StoreAddressContext or None, # assignment via class (never via instance) |
paul@405 | 76 | StoreAttr, # assignment via instance |
paul@405 | 77 | StoreAttrIndex, # special assignment via instance |
paul@405 | 78 | None |
paul@405 | 79 | ) |
paul@405 | 80 | |
paul@452 | 81 | def reset(self, block=None, blocks=None): |
paul@452 | 82 | |
paul@452 | 83 | """ |
paul@452 | 84 | Reset the optimiser for the given 'block' (or the current block), |
paul@452 | 85 | clearing the active value instructions if no 'blocks' are given, or |
paul@452 | 86 | collecting the active instructions from each of the blocks otherwise. |
paul@452 | 87 | """ |
paul@452 | 88 | |
paul@464 | 89 | self.store_active_value() |
paul@452 | 90 | self.clear_active() |
paul@452 | 91 | |
paul@452 | 92 | # Make a new collection of instructions for a new block. |
paul@154 | 93 | |
paul@452 | 94 | if block: |
paul@452 | 95 | self.active_values = set() |
paul@452 | 96 | block.set_active_values(self.active_values) |
paul@452 | 97 | |
paul@452 | 98 | # Otherwise, clear the collection for an existing block. |
paul@154 | 99 | |
paul@452 | 100 | else: |
paul@452 | 101 | self.active_values.clear() |
paul@452 | 102 | |
paul@452 | 103 | if blocks: |
paul@452 | 104 | for b in blocks: |
paul@452 | 105 | self.active_values.update(b.get_active_values()) |
paul@154 | 106 | |
paul@154 | 107 | def set_new(self, op): |
paul@154 | 108 | |
paul@154 | 109 | "Set the latest 'op' as the active instruction." |
paul@154 | 110 | |
paul@154 | 111 | self.set_active(op) |
paul@154 | 112 | self.set_active_value(op) |
paul@154 | 113 | |
paul@154 | 114 | def set_active_value(self, op): |
paul@154 | 115 | |
paul@154 | 116 | "Set the value-providing active instruction." |
paul@154 | 117 | |
paul@464 | 118 | if affects_register(op, "working"): |
paul@464 | 119 | self.store_active_value() |
paul@452 | 120 | self.active_values.clear() |
paul@452 | 121 | self.active_values.add(op) |
paul@154 | 122 | |
paul@452 | 123 | def get_active_value(self): |
paul@154 | 124 | |
paul@452 | 125 | "Get any single active value or None if none or more than one exist." |
paul@154 | 126 | |
paul@452 | 127 | if len(self.active_values) == 1: |
paul@452 | 128 | return list(self.active_values)[0] |
paul@452 | 129 | else: |
paul@452 | 130 | return None |
paul@154 | 131 | |
paul@154 | 132 | def remove_active_value(self): |
paul@154 | 133 | |
paul@156 | 134 | """ |
paul@156 | 135 | Remove the value-providing active instruction from the generated code, |
paul@156 | 136 | if appropriate, but keep a record of the active instruction itself. |
paul@156 | 137 | """ |
paul@154 | 138 | |
paul@452 | 139 | if self.active in self.active_values: |
paul@468 | 140 | removed = self.translation.remove_op() |
paul@468 | 141 | self.active_values.remove(removed) |
paul@154 | 142 | return removed |
paul@154 | 143 | else: |
paul@154 | 144 | return None |
paul@154 | 145 | |
paul@450 | 146 | def set_target(self, target): |
paul@154 | 147 | |
paul@450 | 148 | "Set the target of the active instruction to 'target'." |
paul@154 | 149 | |
paul@452 | 150 | for expr in self.active_values: |
paul@452 | 151 | expr.target = target |
paul@154 | 152 | |
paul@154 | 153 | def set_active(self, op): |
paul@154 | 154 | |
paul@154 | 155 | "Set the active instruction." |
paul@154 | 156 | |
paul@154 | 157 | self.active = op |
paul@154 | 158 | |
paul@154 | 159 | def clear_active(self): |
paul@154 | 160 | |
paul@450 | 161 | "Clear the active instructions." |
paul@154 | 162 | |
paul@154 | 163 | self.active = None |
paul@154 | 164 | |
paul@464 | 165 | # Permit the active value to be requested and restored. |
paul@464 | 166 | |
paul@464 | 167 | def request_active_value(self, temp, block, pos): |
paul@464 | 168 | |
paul@464 | 169 | """ |
paul@464 | 170 | Request the current active value so that if the value is changed, a |
paul@464 | 171 | temporary storage element or equivalent will be allocated. |
paul@464 | 172 | """ |
paul@464 | 173 | |
paul@464 | 174 | self.store_active_value() |
paul@464 | 175 | self.saved_value_op = temp |
paul@464 | 176 | self.saved_value_block = block |
paul@464 | 177 | self.saved_value_pos = pos |
paul@464 | 178 | |
paul@464 | 179 | def store_active_value(self): |
paul@464 | 180 | |
paul@464 | 181 | "Store the requested active value" |
paul@464 | 182 | |
paul@464 | 183 | if self.saved_value_op is not None: |
paul@464 | 184 | self.translation.set_temp(self.saved_value_op, self.saved_value_block, self.saved_value_pos) |
paul@464 | 185 | self.ignore_active_value() |
paul@464 | 186 | |
paul@464 | 187 | def ignore_active_value(self): |
paul@464 | 188 | |
paul@464 | 189 | "Ignore the active value." |
paul@464 | 190 | |
paul@464 | 191 | self.saved_value_op = None |
paul@464 | 192 | self.saved_value_block = None |
paul@464 | 193 | self.saved_value_pos = None |
paul@464 | 194 | |
paul@154 | 195 | # Optimisation tests. |
paul@154 | 196 | |
paul@154 | 197 | def should_optimise_constant_storage(self): |
paul@154 | 198 | return "constant_storage" in self.optimisations |
paul@154 | 199 | |
paul@155 | 200 | def should_optimise_constant_accessor(self): |
paul@155 | 201 | return "constant_accessor" in self.optimisations |
paul@155 | 202 | |
paul@154 | 203 | def should_optimise_known_target(self): |
paul@154 | 204 | return "known_target" in self.optimisations |
paul@154 | 205 | |
paul@154 | 206 | def should_optimise_self_access(self): |
paul@154 | 207 | return "self_access" in self.optimisations |
paul@154 | 208 | |
paul@154 | 209 | def should_optimise_temp_storage(self): |
paul@154 | 210 | return "temp_storage" in self.optimisations |
paul@154 | 211 | |
paul@154 | 212 | def should_optimise_away_no_operations(self): |
paul@154 | 213 | return "no_operations" in self.optimisations |
paul@154 | 214 | |
paul@154 | 215 | def should_optimise_unused_results(self): |
paul@154 | 216 | return "unused_results" in self.optimisations |
paul@154 | 217 | |
paul@232 | 218 | def should_optimise_unused_handlers(self): |
paul@232 | 219 | return "unused_handlers" in self.optimisations |
paul@232 | 220 | |
paul@268 | 221 | def should_optimise_accesses_by_attribute_usage(self): |
paul@268 | 222 | return "accesses_by_usage" in self.optimisations |
paul@268 | 223 | |
paul@154 | 224 | # Simple tests. |
paul@154 | 225 | |
paul@154 | 226 | def is_constant_input(self, instruction): |
paul@154 | 227 | |
paul@154 | 228 | "Return whether 'instruction' provides a constant input." |
paul@154 | 229 | |
paul@243 | 230 | return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 and \ |
paul@243 | 231 | isinstance(instruction.attr.get_value(), Constant) or \ |
paul@237 | 232 | isinstance(instruction, (LoadConst, LoadClass, LoadFunction)) |
paul@154 | 233 | |
paul@154 | 234 | def is_constant_target(self, instruction): |
paul@154 | 235 | |
paul@154 | 236 | "Return whether 'instruction' provides a constant target." |
paul@154 | 237 | |
paul@202 | 238 | # NOTE: Removed StoreName, since this would then demand population of |
paul@202 | 239 | # NOTE: locals/frames. |
paul@202 | 240 | |
paul@223 | 241 | return isinstance(instruction, (StoreAddress, StoreAddressContext)) and \ |
paul@468 | 242 | instruction.attr.is_constant() and \ |
paul@468 | 243 | instruction.attr.is_strict_constant() |
paul@154 | 244 | |
paul@154 | 245 | def is_simple_input(self, instruction): |
paul@154 | 246 | |
paul@154 | 247 | """ |
paul@154 | 248 | Return whether 'instruction' provides a simple input (typically a load |
paul@154 | 249 | instruction). A simple input is something which would be represented by |
paul@154 | 250 | a load operation from a CPU register or special memory location. |
paul@154 | 251 | """ |
paul@154 | 252 | |
paul@430 | 253 | return isinstance(instruction, (LoadConst, LoadClass, LoadFunction, |
paul@450 | 254 | LoadName, LoadTemp, LoadAddress |
paul@430 | 255 | )) |
paul@154 | 256 | |
paul@464 | 257 | def is_resultant_no_operation(self, instruction, last_op=None): |
paul@154 | 258 | |
paul@154 | 259 | """ |
paul@154 | 260 | Return whether 'instruction' merely stores its input where the input |
paul@154 | 261 | originally came from. |
paul@154 | 262 | """ |
paul@154 | 263 | |
paul@464 | 264 | last_op = last_op or self.translation.last_op() |
paul@464 | 265 | return last_op and last_op.attr == instruction.attr and ( |
paul@464 | 266 | isinstance(instruction, StoreTemp) and isinstance(last_op, LoadTemp) or |
paul@468 | 267 | isinstance(instruction, StoreAddress) and isinstance(last_op, LoadAddress) or |
paul@468 | 268 | last_op.source == instruction.target and ( |
paul@468 | 269 | isinstance(instruction, LoadTemp) and isinstance(last_op, StoreTemp) or |
paul@468 | 270 | isinstance(instruction, LoadAddress) and isinstance(last_op, StoreAddress) |
paul@468 | 271 | )) |
paul@154 | 272 | |
paul@154 | 273 | # Convenience tests on outputs. |
paul@154 | 274 | |
paul@154 | 275 | def have_constant_target(self): |
paul@154 | 276 | |
paul@154 | 277 | "Return whether the active instruction provides a constant target." |
paul@154 | 278 | |
paul@154 | 279 | return self.is_constant_target(self.active) |
paul@154 | 280 | |
paul@450 | 281 | def have_constant_source(self, expr): |
paul@154 | 282 | |
paul@450 | 283 | "Return whether the active assignment source instruction is constant." |
paul@154 | 284 | |
paul@450 | 285 | return self.is_constant_input(expr) |
paul@154 | 286 | |
paul@154 | 287 | # Convenience tests on inputs. |
paul@154 | 288 | |
paul@154 | 289 | def have_constant_input(self): |
paul@154 | 290 | |
paul@154 | 291 | "Return whether the active instruction provides a constant input." |
paul@154 | 292 | |
paul@452 | 293 | return self.get_active_value() and self.is_constant_input(self.get_active_value()) |
paul@154 | 294 | |
paul@154 | 295 | def have_simple_input(self): |
paul@154 | 296 | |
paul@154 | 297 | "Return whether the active instruction provides a simple input." |
paul@154 | 298 | |
paul@452 | 299 | return self.get_active_value() and self.is_simple_input(self.get_active_value()) |
paul@154 | 300 | |
paul@453 | 301 | # Indicate whether the active instruction can be used in place of access |
paul@453 | 302 | # to a temporary variable retaining the result of the last instruction. |
paul@453 | 303 | |
paul@453 | 304 | have_temp_compatible_access = have_simple_input |
paul@453 | 305 | |
paul@158 | 306 | def have_self_input(self, unit): |
paul@154 | 307 | |
paul@158 | 308 | """ |
paul@158 | 309 | Return whether the active instruction is a reference to self in the |
paul@158 | 310 | given 'unit'. |
paul@158 | 311 | """ |
paul@154 | 312 | |
paul@452 | 313 | if not (isinstance(unit, Function) and unit.is_method()): |
paul@452 | 314 | return 0 |
paul@154 | 315 | |
paul@452 | 316 | expr = self.get_active_value() |
paul@452 | 317 | return expr and isinstance(expr, LoadName) and expr.attr.name == "self" |
paul@154 | 318 | |
paul@158 | 319 | def have_correct_self_for_target(self, context, unit): |
paul@154 | 320 | |
paul@158 | 321 | "Return whether the 'context' is compatible with the given 'unit'." |
paul@154 | 322 | |
paul@158 | 323 | if context is not None and self.have_self_input(unit): |
paul@154 | 324 | |
paul@158 | 325 | parent = unit.parent |
paul@154 | 326 | if parent is context or parent.has_subclass(context) or context.has_subclass(parent): |
paul@154 | 327 | return 1 |
paul@154 | 328 | |
paul@154 | 329 | return 0 |
paul@154 | 330 | |
paul@232 | 331 | def have_empty_handler(self, instruction): |
paul@232 | 332 | |
paul@232 | 333 | """ |
paul@232 | 334 | Return whether the active instruction defined a handler for exceptions |
paul@232 | 335 | which is then discarded by the given 'instruction'. |
paul@232 | 336 | """ |
paul@232 | 337 | |
paul@232 | 338 | return isinstance(self.translation.last_op(), PushHandler) and isinstance(instruction, PopHandler) |
paul@232 | 339 | |
paul@154 | 340 | # Optimisation methods. See the supported_optimisations class attribute. |
paul@154 | 341 | |
paul@468 | 342 | def optimise_constant_storage(self, expr): |
paul@154 | 343 | |
paul@154 | 344 | """ |
paul@154 | 345 | Where the last operation stores a constant into a target which is also |
paul@156 | 346 | constant, indicate that both operations should be optimised away. |
paul@154 | 347 | """ |
paul@154 | 348 | |
paul@156 | 349 | return self.should_optimise_constant_storage() and \ |
paul@154 | 350 | self.have_constant_target() and \ |
paul@450 | 351 | self.have_constant_source(expr) |
paul@154 | 352 | |
paul@155 | 353 | def optimise_constant_accessor(self): |
paul@155 | 354 | |
paul@155 | 355 | """ |
paul@155 | 356 | Where the object whose attribute is being accessed is constant, provide |
paul@401 | 357 | information about the object and its full name. |
paul@155 | 358 | """ |
paul@155 | 359 | |
paul@155 | 360 | if self.should_optimise_constant_accessor() and self.have_constant_input(): |
paul@452 | 361 | value = self.get_active_value() |
paul@155 | 362 | |
paul@155 | 363 | # Get the details of the access. |
paul@155 | 364 | |
paul@155 | 365 | if isinstance(value.attr, Const): |
paul@450 | 366 | return value.attr, value.attr.value_type_name() |
paul@155 | 367 | else: |
paul@192 | 368 | target = value.attr.get_value() |
paul@155 | 369 | |
paul@192 | 370 | if target is None: |
paul@192 | 371 | return None # no clearly defined target |
paul@192 | 372 | elif isinstance(target, Const): |
paul@401 | 373 | return target, target.value_type_name() |
paul@155 | 374 | elif isinstance(target, Instance): |
paul@155 | 375 | return None # skip production of optimised code |
paul@155 | 376 | else: |
paul@401 | 377 | return target, target.full_name() |
paul@155 | 378 | |
paul@155 | 379 | else: |
paul@155 | 380 | return None |
paul@155 | 381 | |
paul@154 | 382 | def optimise_known_target(self): |
paul@154 | 383 | |
paul@154 | 384 | """ |
paul@154 | 385 | Where the target of an invocation is known, provide information about it |
paul@154 | 386 | and its context. If a class is being invoked and the conditions are |
paul@154 | 387 | appropriate, get information about the specific initialiser. |
paul@154 | 388 | """ |
paul@154 | 389 | |
paul@452 | 390 | if self.should_optimise_known_target() and self.have_constant_input(): |
paul@452 | 391 | value = self.get_active_value() |
paul@192 | 392 | target = value.attr.get_value() |
paul@192 | 393 | context = value.attr.get_context() |
paul@192 | 394 | |
paul@192 | 395 | # Return target details only if this is clearly defined. |
paul@154 | 396 | |
paul@192 | 397 | if target is not None: |
paul@192 | 398 | return target, context |
paul@192 | 399 | |
paul@192 | 400 | return None |
paul@154 | 401 | |
paul@156 | 402 | def optimise_self_access(self, unit, attrname): |
paul@154 | 403 | |
paul@154 | 404 | """ |
paul@156 | 405 | Return whether code in the given 'unit' is able to access the given |
paul@156 | 406 | 'attrname' through the same position in all possible objects which might |
paul@156 | 407 | be accessed. |
paul@154 | 408 | """ |
paul@154 | 409 | |
paul@156 | 410 | return self.should_optimise_self_access() and \ |
paul@158 | 411 | self.have_self_input(unit) and not unit.is_relocated(attrname) |
paul@154 | 412 | |
paul@154 | 413 | def optimise_temp_storage(self): |
paul@154 | 414 | |
paul@154 | 415 | """ |
paul@154 | 416 | Where the next operation would involve storing a value into temporary |
paul@368 | 417 | storage, record and remove any simple instruction which produced the |
paul@368 | 418 | value to be stored such that instead of subsequently accessing the |
paul@368 | 419 | temporary storage, that instruction is substituted. |
paul@154 | 420 | |
paul@464 | 421 | If no optimisation can be achieved, temporary storage is requested |
paul@154 | 422 | and the appropriate LoadTemp instruction is returned. |
paul@154 | 423 | |
paul@154 | 424 | Restriction: for use only in situations where the source of the |
paul@154 | 425 | temporary data will not be disturbed between its first access and its |
paul@154 | 426 | subsequent use. |
paul@154 | 427 | """ |
paul@154 | 428 | |
paul@465 | 429 | if self.should_optimise_temp_storage(): |
paul@465 | 430 | |
paul@465 | 431 | # Emitted instructions can be obtained. |
paul@465 | 432 | |
paul@465 | 433 | if self.have_temp_compatible_access(): |
paul@154 | 434 | |
paul@465 | 435 | # Remove the active value contributor if possible. |
paul@154 | 436 | |
paul@465 | 437 | removed = self.remove_active_value() |
paul@465 | 438 | if removed is not None: |
paul@465 | 439 | |
paul@465 | 440 | # Extend the lifetime of any temporary storage location. |
paul@154 | 441 | |
paul@465 | 442 | self.translation.ensure_temp(removed) |
paul@465 | 443 | return removed |
paul@154 | 444 | |
paul@465 | 445 | # Otherwise, just leave it in place, but return the instruction. |
paul@154 | 446 | |
paul@465 | 447 | else: |
paul@465 | 448 | return self.get_active_value() |
paul@464 | 449 | |
paul@465 | 450 | # Or provisional temporary instructions. |
paul@465 | 451 | |
paul@465 | 452 | elif self.saved_value_op is not None: |
paul@465 | 453 | return self.saved_value_op |
paul@464 | 454 | |
paul@450 | 455 | return self.translation.get_temp() |
paul@154 | 456 | |
paul@464 | 457 | def optimise_away_no_operations(self, instruction, last_op=None): |
paul@154 | 458 | |
paul@154 | 459 | """ |
paul@154 | 460 | Optimise away operations which just store their inputs in the place |
paul@154 | 461 | the inputs originally came from. |
paul@154 | 462 | """ |
paul@154 | 463 | |
paul@156 | 464 | return self.should_optimise_away_no_operations() and \ |
paul@464 | 465 | self.is_resultant_no_operation(instruction, last_op) |
paul@154 | 466 | |
paul@154 | 467 | def optimise_unused_results(self): |
paul@154 | 468 | |
paul@154 | 469 | "Discard results which will not be used." |
paul@154 | 470 | |
paul@154 | 471 | if self.should_optimise_unused_results() and self.have_simple_input(): |
paul@154 | 472 | self.remove_active_value() |
paul@154 | 473 | |
paul@232 | 474 | def optimise_unused_handlers(self, instruction): |
paul@232 | 475 | |
paul@232 | 476 | "Discard handlers which will not be used." |
paul@232 | 477 | |
paul@232 | 478 | if self.should_optimise_unused_handlers() and self.have_empty_handler(instruction): |
paul@232 | 479 | self.translation.remove_op() |
paul@232 | 480 | return 1 |
paul@232 | 481 | else: |
paul@232 | 482 | return 0 |
paul@232 | 483 | |
paul@154 | 484 | # vim: tabstop=4 expandtab shiftwidth=4 |