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@154 | 140 | removed = self.active |
paul@154 | 141 | self.translation.remove_op() |
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@154 | 242 | instruction.attr.assignments == 1 |
paul@154 | 243 | |
paul@154 | 244 | def is_simple_input(self, instruction): |
paul@154 | 245 | |
paul@154 | 246 | """ |
paul@154 | 247 | Return whether 'instruction' provides a simple input (typically a load |
paul@154 | 248 | instruction). A simple input is something which would be represented by |
paul@154 | 249 | a load operation from a CPU register or special memory location. |
paul@154 | 250 | """ |
paul@154 | 251 | |
paul@430 | 252 | return isinstance(instruction, (LoadConst, LoadClass, LoadFunction, |
paul@450 | 253 | LoadName, LoadTemp, LoadAddress |
paul@430 | 254 | )) |
paul@154 | 255 | |
paul@464 | 256 | def is_resultant_no_operation(self, instruction, last_op=None): |
paul@154 | 257 | |
paul@154 | 258 | """ |
paul@154 | 259 | Return whether 'instruction' merely stores its input where the input |
paul@154 | 260 | originally came from. |
paul@154 | 261 | """ |
paul@154 | 262 | |
paul@464 | 263 | last_op = last_op or self.translation.last_op() |
paul@464 | 264 | return last_op and last_op.attr == instruction.attr and ( |
paul@464 | 265 | isinstance(instruction, StoreTemp) and isinstance(last_op, LoadTemp) or |
paul@464 | 266 | isinstance(instruction, StoreAddress) and isinstance(last_op, LoadAddress) |
paul@154 | 267 | ) |
paul@154 | 268 | |
paul@154 | 269 | # Convenience tests on outputs. |
paul@154 | 270 | |
paul@154 | 271 | def have_constant_target(self): |
paul@154 | 272 | |
paul@154 | 273 | "Return whether the active instruction provides a constant target." |
paul@154 | 274 | |
paul@154 | 275 | return self.is_constant_target(self.active) |
paul@154 | 276 | |
paul@450 | 277 | def have_constant_source(self, expr): |
paul@154 | 278 | |
paul@450 | 279 | "Return whether the active assignment source instruction is constant." |
paul@154 | 280 | |
paul@450 | 281 | return self.is_constant_input(expr) |
paul@154 | 282 | |
paul@154 | 283 | # Convenience tests on inputs. |
paul@154 | 284 | |
paul@154 | 285 | def have_constant_input(self): |
paul@154 | 286 | |
paul@154 | 287 | "Return whether the active instruction provides a constant input." |
paul@154 | 288 | |
paul@452 | 289 | return self.get_active_value() and self.is_constant_input(self.get_active_value()) |
paul@154 | 290 | |
paul@154 | 291 | def have_simple_input(self): |
paul@154 | 292 | |
paul@154 | 293 | "Return whether the active instruction provides a simple input." |
paul@154 | 294 | |
paul@452 | 295 | return self.get_active_value() and self.is_simple_input(self.get_active_value()) |
paul@154 | 296 | |
paul@453 | 297 | # Indicate whether the active instruction can be used in place of access |
paul@453 | 298 | # to a temporary variable retaining the result of the last instruction. |
paul@453 | 299 | |
paul@453 | 300 | have_temp_compatible_access = have_simple_input |
paul@453 | 301 | |
paul@158 | 302 | def have_self_input(self, unit): |
paul@154 | 303 | |
paul@158 | 304 | """ |
paul@158 | 305 | Return whether the active instruction is a reference to self in the |
paul@158 | 306 | given 'unit'. |
paul@158 | 307 | """ |
paul@154 | 308 | |
paul@452 | 309 | if not (isinstance(unit, Function) and unit.is_method()): |
paul@452 | 310 | return 0 |
paul@154 | 311 | |
paul@452 | 312 | expr = self.get_active_value() |
paul@452 | 313 | return expr and isinstance(expr, LoadName) and expr.attr.name == "self" |
paul@154 | 314 | |
paul@158 | 315 | def have_correct_self_for_target(self, context, unit): |
paul@154 | 316 | |
paul@158 | 317 | "Return whether the 'context' is compatible with the given 'unit'." |
paul@154 | 318 | |
paul@158 | 319 | if context is not None and self.have_self_input(unit): |
paul@154 | 320 | |
paul@158 | 321 | parent = unit.parent |
paul@154 | 322 | if parent is context or parent.has_subclass(context) or context.has_subclass(parent): |
paul@154 | 323 | return 1 |
paul@154 | 324 | |
paul@154 | 325 | return 0 |
paul@154 | 326 | |
paul@232 | 327 | def have_empty_handler(self, instruction): |
paul@232 | 328 | |
paul@232 | 329 | """ |
paul@232 | 330 | Return whether the active instruction defined a handler for exceptions |
paul@232 | 331 | which is then discarded by the given 'instruction'. |
paul@232 | 332 | """ |
paul@232 | 333 | |
paul@232 | 334 | return isinstance(self.translation.last_op(), PushHandler) and isinstance(instruction, PopHandler) |
paul@232 | 335 | |
paul@154 | 336 | # Optimisation methods. See the supported_optimisations class attribute. |
paul@154 | 337 | |
paul@450 | 338 | def optimise_constant_storage(self, expr=None): |
paul@154 | 339 | |
paul@154 | 340 | """ |
paul@154 | 341 | Where the last operation stores a constant into a target which is also |
paul@156 | 342 | constant, indicate that both operations should be optimised away. |
paul@154 | 343 | """ |
paul@154 | 344 | |
paul@156 | 345 | return self.should_optimise_constant_storage() and \ |
paul@154 | 346 | self.have_constant_target() and \ |
paul@450 | 347 | self.have_constant_source(expr) |
paul@154 | 348 | |
paul@155 | 349 | def optimise_constant_accessor(self): |
paul@155 | 350 | |
paul@155 | 351 | """ |
paul@155 | 352 | Where the object whose attribute is being accessed is constant, provide |
paul@401 | 353 | information about the object and its full name. |
paul@155 | 354 | """ |
paul@155 | 355 | |
paul@155 | 356 | if self.should_optimise_constant_accessor() and self.have_constant_input(): |
paul@452 | 357 | value = self.get_active_value() |
paul@155 | 358 | |
paul@155 | 359 | # Get the details of the access. |
paul@155 | 360 | |
paul@155 | 361 | if isinstance(value.attr, Const): |
paul@450 | 362 | return value.attr, value.attr.value_type_name() |
paul@155 | 363 | else: |
paul@192 | 364 | target = value.attr.get_value() |
paul@155 | 365 | |
paul@192 | 366 | if target is None: |
paul@192 | 367 | return None # no clearly defined target |
paul@192 | 368 | elif isinstance(target, Const): |
paul@401 | 369 | return target, target.value_type_name() |
paul@155 | 370 | elif isinstance(target, Instance): |
paul@155 | 371 | return None # skip production of optimised code |
paul@155 | 372 | else: |
paul@401 | 373 | return target, target.full_name() |
paul@155 | 374 | |
paul@155 | 375 | else: |
paul@155 | 376 | return None |
paul@155 | 377 | |
paul@154 | 378 | def optimise_known_target(self): |
paul@154 | 379 | |
paul@154 | 380 | """ |
paul@154 | 381 | Where the target of an invocation is known, provide information about it |
paul@154 | 382 | and its context. If a class is being invoked and the conditions are |
paul@154 | 383 | appropriate, get information about the specific initialiser. |
paul@154 | 384 | """ |
paul@154 | 385 | |
paul@452 | 386 | if self.should_optimise_known_target() and self.have_constant_input(): |
paul@452 | 387 | value = self.get_active_value() |
paul@192 | 388 | target = value.attr.get_value() |
paul@192 | 389 | context = value.attr.get_context() |
paul@192 | 390 | |
paul@192 | 391 | # Return target details only if this is clearly defined. |
paul@154 | 392 | |
paul@192 | 393 | if target is not None: |
paul@192 | 394 | return target, context |
paul@192 | 395 | |
paul@192 | 396 | return None |
paul@154 | 397 | |
paul@156 | 398 | def optimise_self_access(self, unit, attrname): |
paul@154 | 399 | |
paul@154 | 400 | """ |
paul@156 | 401 | Return whether code in the given 'unit' is able to access the given |
paul@156 | 402 | 'attrname' through the same position in all possible objects which might |
paul@156 | 403 | be accessed. |
paul@154 | 404 | """ |
paul@154 | 405 | |
paul@156 | 406 | return self.should_optimise_self_access() and \ |
paul@158 | 407 | self.have_self_input(unit) and not unit.is_relocated(attrname) |
paul@154 | 408 | |
paul@154 | 409 | def optimise_temp_storage(self): |
paul@154 | 410 | |
paul@154 | 411 | """ |
paul@154 | 412 | Where the next operation would involve storing a value into temporary |
paul@368 | 413 | storage, record and remove any simple instruction which produced the |
paul@368 | 414 | value to be stored such that instead of subsequently accessing the |
paul@368 | 415 | temporary storage, that instruction is substituted. |
paul@154 | 416 | |
paul@464 | 417 | If no optimisation can be achieved, temporary storage is requested |
paul@154 | 418 | and the appropriate LoadTemp instruction is returned. |
paul@154 | 419 | |
paul@154 | 420 | Restriction: for use only in situations where the source of the |
paul@154 | 421 | temporary data will not be disturbed between its first access and its |
paul@154 | 422 | subsequent use. |
paul@154 | 423 | """ |
paul@154 | 424 | |
paul@465 | 425 | if self.should_optimise_temp_storage(): |
paul@465 | 426 | |
paul@465 | 427 | # Emitted instructions can be obtained. |
paul@465 | 428 | |
paul@465 | 429 | if self.have_temp_compatible_access(): |
paul@154 | 430 | |
paul@465 | 431 | # Remove the active value contributor if possible. |
paul@154 | 432 | |
paul@465 | 433 | removed = self.remove_active_value() |
paul@465 | 434 | if removed is not None: |
paul@465 | 435 | |
paul@465 | 436 | # Extend the lifetime of any temporary storage location. |
paul@154 | 437 | |
paul@465 | 438 | self.translation.ensure_temp(removed) |
paul@465 | 439 | return removed |
paul@154 | 440 | |
paul@465 | 441 | # Otherwise, just leave it in place, but return the instruction. |
paul@154 | 442 | |
paul@465 | 443 | else: |
paul@465 | 444 | return self.get_active_value() |
paul@464 | 445 | |
paul@465 | 446 | # Or provisional temporary instructions. |
paul@465 | 447 | |
paul@465 | 448 | elif self.saved_value_op is not None: |
paul@465 | 449 | return self.saved_value_op |
paul@464 | 450 | |
paul@450 | 451 | return self.translation.get_temp() |
paul@154 | 452 | |
paul@464 | 453 | def optimise_away_no_operations(self, instruction, last_op=None): |
paul@154 | 454 | |
paul@154 | 455 | """ |
paul@154 | 456 | Optimise away operations which just store their inputs in the place |
paul@154 | 457 | the inputs originally came from. |
paul@154 | 458 | """ |
paul@154 | 459 | |
paul@156 | 460 | return self.should_optimise_away_no_operations() and \ |
paul@464 | 461 | self.is_resultant_no_operation(instruction, last_op) |
paul@154 | 462 | |
paul@154 | 463 | def optimise_unused_results(self): |
paul@154 | 464 | |
paul@154 | 465 | "Discard results which will not be used." |
paul@154 | 466 | |
paul@154 | 467 | if self.should_optimise_unused_results() and self.have_simple_input(): |
paul@154 | 468 | self.remove_active_value() |
paul@154 | 469 | |
paul@232 | 470 | def optimise_unused_handlers(self, instruction): |
paul@232 | 471 | |
paul@232 | 472 | "Discard handlers which will not be used." |
paul@232 | 473 | |
paul@232 | 474 | if self.should_optimise_unused_handlers() and self.have_empty_handler(instruction): |
paul@232 | 475 | self.translation.remove_op() |
paul@232 | 476 | return 1 |
paul@232 | 477 | else: |
paul@232 | 478 | return 0 |
paul@232 | 479 | |
paul@154 | 480 | # vim: tabstop=4 expandtab shiftwidth=4 |