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.active 141 self.translation.remove_op() 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.assignments == 1 243 244 def is_simple_input(self, instruction): 245 246 """ 247 Return whether 'instruction' provides a simple input (typically a load 248 instruction). A simple input is something which would be represented by 249 a load operation from a CPU register or special memory location. 250 """ 251 252 return isinstance(instruction, (LoadConst, LoadClass, LoadFunction, 253 LoadName, LoadTemp, LoadAddress 254 )) 255 256 def is_resultant_no_operation(self, instruction, last_op=None): 257 258 """ 259 Return whether 'instruction' merely stores its input where the input 260 originally came from. 261 """ 262 263 last_op = last_op or self.translation.last_op() 264 return last_op and last_op.attr == instruction.attr and ( 265 isinstance(instruction, StoreTemp) and isinstance(last_op, LoadTemp) or 266 isinstance(instruction, StoreAddress) and isinstance(last_op, LoadAddress) 267 ) 268 269 # Convenience tests on outputs. 270 271 def have_constant_target(self): 272 273 "Return whether the active instruction provides a constant target." 274 275 return self.is_constant_target(self.active) 276 277 def have_constant_source(self, expr): 278 279 "Return whether the active assignment source instruction is constant." 280 281 return self.is_constant_input(expr) 282 283 # Convenience tests on inputs. 284 285 def have_constant_input(self): 286 287 "Return whether the active instruction provides a constant input." 288 289 return self.get_active_value() and self.is_constant_input(self.get_active_value()) 290 291 def have_simple_input(self): 292 293 "Return whether the active instruction provides a simple input." 294 295 return self.get_active_value() and self.is_simple_input(self.get_active_value()) 296 297 # Indicate whether the active instruction can be used in place of access 298 # to a temporary variable retaining the result of the last instruction. 299 300 have_temp_compatible_access = have_simple_input 301 302 def have_self_input(self, unit): 303 304 """ 305 Return whether the active instruction is a reference to self in the 306 given 'unit'. 307 """ 308 309 if not (isinstance(unit, Function) and unit.is_method()): 310 return 0 311 312 expr = self.get_active_value() 313 return expr and isinstance(expr, LoadName) and expr.attr.name == "self" 314 315 def have_correct_self_for_target(self, context, unit): 316 317 "Return whether the 'context' is compatible with the given 'unit'." 318 319 if context is not None and self.have_self_input(unit): 320 321 parent = unit.parent 322 if parent is context or parent.has_subclass(context) or context.has_subclass(parent): 323 return 1 324 325 return 0 326 327 def have_empty_handler(self, instruction): 328 329 """ 330 Return whether the active instruction defined a handler for exceptions 331 which is then discarded by the given 'instruction'. 332 """ 333 334 return isinstance(self.translation.last_op(), PushHandler) and isinstance(instruction, PopHandler) 335 336 # Optimisation methods. See the supported_optimisations class attribute. 337 338 def optimise_constant_storage(self, expr=None): 339 340 """ 341 Where the last operation stores a constant into a target which is also 342 constant, indicate that both operations should be optimised away. 343 """ 344 345 return self.should_optimise_constant_storage() and \ 346 self.have_constant_target() and \ 347 self.have_constant_source(expr) 348 349 def optimise_constant_accessor(self): 350 351 """ 352 Where the object whose attribute is being accessed is constant, provide 353 information about the object and its full name. 354 """ 355 356 if self.should_optimise_constant_accessor() and self.have_constant_input(): 357 value = self.get_active_value() 358 359 # Get the details of the access. 360 361 if isinstance(value.attr, Const): 362 return value.attr, value.attr.value_type_name() 363 else: 364 target = value.attr.get_value() 365 366 if target is None: 367 return None # no clearly defined target 368 elif isinstance(target, Const): 369 return target, target.value_type_name() 370 elif isinstance(target, Instance): 371 return None # skip production of optimised code 372 else: 373 return target, target.full_name() 374 375 else: 376 return None 377 378 def optimise_known_target(self): 379 380 """ 381 Where the target of an invocation is known, provide information about it 382 and its context. If a class is being invoked and the conditions are 383 appropriate, get information about the specific initialiser. 384 """ 385 386 if self.should_optimise_known_target() and self.have_constant_input(): 387 value = self.get_active_value() 388 target = value.attr.get_value() 389 context = value.attr.get_context() 390 391 # Return target details only if this is clearly defined. 392 393 if target is not None: 394 return target, context 395 396 return None 397 398 def optimise_self_access(self, unit, attrname): 399 400 """ 401 Return whether code in the given 'unit' is able to access the given 402 'attrname' through the same position in all possible objects which might 403 be accessed. 404 """ 405 406 return self.should_optimise_self_access() and \ 407 self.have_self_input(unit) and not unit.is_relocated(attrname) 408 409 def optimise_temp_storage(self): 410 411 """ 412 Where the next operation would involve storing a value into temporary 413 storage, record and remove any simple instruction which produced the 414 value to be stored such that instead of subsequently accessing the 415 temporary storage, that instruction is substituted. 416 417 If no optimisation can be achieved, temporary storage is requested 418 and the appropriate LoadTemp instruction is returned. 419 420 Restriction: for use only in situations where the source of the 421 temporary data will not be disturbed between its first access and its 422 subsequent use. 423 """ 424 425 if self.should_optimise_temp_storage(): 426 427 # Emitted instructions can be obtained. 428 429 if self.have_temp_compatible_access(): 430 431 # Remove the active value contributor if possible. 432 433 removed = self.remove_active_value() 434 if removed is not None: 435 436 # Extend the lifetime of any temporary storage location. 437 438 self.translation.ensure_temp(removed) 439 return removed 440 441 # Otherwise, just leave it in place, but return the instruction. 442 443 else: 444 return self.get_active_value() 445 446 # Or provisional temporary instructions. 447 448 elif self.saved_value_op is not None: 449 return self.saved_value_op 450 451 return self.translation.get_temp() 452 453 def optimise_away_no_operations(self, instruction, last_op=None): 454 455 """ 456 Optimise away operations which just store their inputs in the place 457 the inputs originally came from. 458 """ 459 460 return self.should_optimise_away_no_operations() and \ 461 self.is_resultant_no_operation(instruction, last_op) 462 463 def optimise_unused_results(self): 464 465 "Discard results which will not be used." 466 467 if self.should_optimise_unused_results() and self.have_simple_input(): 468 self.remove_active_value() 469 470 def optimise_unused_handlers(self, instruction): 471 472 "Discard handlers which will not be used." 473 474 if self.should_optimise_unused_handlers() and self.have_empty_handler(instruction): 475 self.translation.remove_op() 476 return 1 477 else: 478 return 0 479 480 # vim: tabstop=4 expandtab shiftwidth=4