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