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