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