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