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