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