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