1 #!/usr/bin/env python 2 3 """ 4 Optimise code produced by the AST translator. 5 6 Copyright (C) 2007, 2008 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.rsvp import * 24 25 class Optimiser: 26 27 "A code optimiser." 28 29 supported_optimisations = [ 30 "constant_storage", "known_target", "self_access", 31 "temp_storage", "load_operations", "no_operations", 32 "unused_results" 33 ] 34 35 def __init__(self, translation, optimisations=None): 36 37 """ 38 Provide for the given 'translation' an optimiser for the desired 39 'optimisations'. See the 'supported_optimisations' attribute of this 40 class for permitted values. 41 """ 42 43 self.translation = translation 44 self.optimisations = set(optimisations or []) 45 46 # The current "active" instruction. 47 # As a rule, this will become the last instruction, but some 48 # control-flow operations will flush the "active" instruction. 49 50 self.active = None 51 52 # The instruction providing the active value. 53 54 self.active_value = None 55 56 def reset(self): 57 58 "Reset the optimiser, clearing the active instructions." 59 60 self.clear_active_value() 61 self.clear_active() 62 63 def set_new(self, op): 64 65 "Set the latest 'op' as the active instruction." 66 67 self.set_active(op) 68 self.set_active_value(op) 69 70 def set_active_value(self, op): 71 72 "Set the value-providing active instruction." 73 74 if isinstance(op, current_value_instructions): 75 self.active_value = op 76 77 def clear_active_value(self): 78 79 "Clear the value-providing active instruction." 80 81 self.active_value = None 82 83 def remove_active_value(self): 84 85 "Remove the value-providing active instruction if appropriate." 86 87 if self.active_value is self.active: 88 removed = self.active 89 self.translation.remove_op() 90 return removed 91 else: 92 return None 93 94 def set_source(self, expr): 95 96 "Set the source of the active instruction to 'expr'." 97 98 if self.active is not None: 99 self.active.source = expr 100 101 def set_active(self, op): 102 103 "Set the active instruction." 104 105 self.active = op 106 107 def clear_active(self): 108 109 "Clear the active instruction." 110 111 self.active = None 112 113 # Optimisation tests. 114 115 def should_optimise_constant_storage(self): 116 return "constant_storage" in self.optimisations 117 118 def should_optimise_known_target(self): 119 return "known_target" in self.optimisations 120 121 def should_optimise_self_access(self): 122 return "self_access" in self.optimisations 123 124 def should_optimise_temp_storage(self): 125 return "temp_storage" in self.optimisations 126 127 def should_optimise_load_operations(self): 128 return "load_operations" in self.optimisations 129 130 def should_optimise_away_no_operations(self): 131 return "no_operations" in self.optimisations 132 133 def should_optimise_unused_results(self): 134 return "unused_results" in self.optimisations 135 136 # Simple tests. 137 138 def is_constant_input(self, instruction): 139 140 "Return whether 'instruction' provides a constant input." 141 142 return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 or \ 143 isinstance(instruction, LoadConst) 144 145 def is_constant_target(self, instruction): 146 147 "Return whether 'instruction' provides a constant target." 148 149 return isinstance(instruction, (StoreName, StoreAddress)) and \ 150 instruction.attr.assignments == 1 151 152 def is_simple_input(self, instruction): 153 154 """ 155 Return whether 'instruction' provides a simple input (typically a load 156 instruction). A simple input is something which would be represented by 157 a load operation from a CPU register or special memory location. 158 """ 159 160 return isinstance(instruction, (LoadConst, LoadName, LoadTemp, LoadResult, LoadException, LoadAddress)) 161 162 def is_simple_input_user(self, instruction): 163 164 """ 165 Return whether 'instruction' can use simple input from the current 166 value. Such instructions would, in a low-level implementation, be able 167 to have the simple input registers as operands. 168 """ 169 170 return isinstance(instruction, ( 171 StoreTemp, StoreFrame, StoreResult, StoreException, # as the value being stored 172 LoadAddressContext, LoadAttr, LoadAttrIndex, # as the object being referenced 173 StoreAttr, StoreAttrIndex, StoreCallable, # as the object being referenced 174 LoadCallable, 175 TestIdentity, TestIdentityAddress, CheckSelf, # as one of the operands 176 CheckException, CheckFrame, MakeObject, 177 LoadContext # as the object providing the result 178 )) 179 180 def is_resultant_no_operation(self, instruction): 181 182 """ 183 Return whether 'instruction' merely stores its input where the input 184 originally came from. 185 """ 186 187 return ( 188 isinstance(instruction.input, LoadTemp) and isinstance(instruction, StoreTemp) and 189 instruction.input.attr == instruction.attr) or ( 190 isinstance(instruction.input, LoadResult) and isinstance(instruction, StoreResult) 191 ) 192 193 def is_input(self, instruction): 194 195 "Return whether 'instruction' provides an input." 196 197 return isinstance(instruction, current_value_instructions) 198 199 # Convenience tests on outputs. 200 201 def have_constant_target(self): 202 203 "Return whether the active instruction provides a constant target." 204 205 return self.is_constant_target(self.active) 206 207 def have_constant_source(self): 208 209 "Return whether the active instruction has a constant source." 210 211 return self.is_constant_input(self.active.source) 212 213 # Convenience tests on inputs. 214 215 def have_constant_input(self): 216 217 "Return whether the active instruction provides a constant input." 218 219 return self.is_constant_input(self.active_value) 220 221 have_known_target = have_constant_input 222 223 def have_simple_input(self): 224 225 "Return whether the active instruction provides a simple input." 226 227 return self.is_simple_input(self.active_value) 228 229 def have_input(self): 230 231 "Return whether the active instruction provides an input." 232 233 return self.is_input(self.active_value) 234 235 def have_self_input(self): 236 237 "Return whether the active instruction is a reference to self." 238 239 return isinstance(self.translation.unit, Function) and \ 240 self.translation.unit.is_method() and isinstance(self.active_value, LoadName) and \ 241 self.active_value.attr.name == "self" 242 243 def have_temp_compatible_access(self): 244 245 """ 246 Indicate whether the active instruction can be used in place of access 247 to a temporary variable retaining the result of the last instruction. 248 """ 249 250 # LoadResult cannot be relied upon in general since the result register 251 # could be updated since first being referenced. 252 253 return isinstance(self.active_value, (LoadName, LoadTemp, LoadAddress, LoadConst)) or \ 254 isinstance(self.active_value, LoadResult) and self.active_value is self.active or \ 255 isinstance(self.active_value, LoadException) and self.active_value is self.active 256 257 def have_correct_self_for_target(self, context): 258 259 "Return whether the 'context' is compatible with the current value." 260 261 if context is not None and self.have_self_input(): 262 263 parent = self.translation.unit.parent 264 if parent is context or parent.has_subclass(context) or context.has_subclass(parent): 265 return 1 266 267 return 0 268 269 # Optimisation methods. See the supported_optimisations class attribute. 270 271 def optimise_constant_storage(self): 272 273 """ 274 Where the last operation stores a constant into a target which is also 275 constant, optimise away both operations. 276 """ 277 278 if self.should_optimise_constant_storage() and \ 279 self.have_constant_target() and \ 280 self.have_constant_source(): 281 282 self.translation.remove_op() 283 return 1 284 else: 285 return 0 286 287 def optimise_known_target(self): 288 289 """ 290 Where the target of an invocation is known, provide information about it 291 and its context. If a class is being invoked and the conditions are 292 appropriate, get information about the specific initialiser. 293 """ 294 295 if self.should_optimise_known_target() and self.have_known_target(): 296 value = self.active_value 297 target = value.attr.value 298 context = value.attr.context 299 300 return target, context 301 else: 302 return None 303 304 def optimise_self_access(self, attrname, classes, node): 305 306 """ 307 Where the provided 'attrname' accesses an attribute which occupies the 308 same position in all possible objects which can be accessed, generate an 309 instruction using one of the given 'classes', accessing the attribute 310 directly. 311 """ 312 313 AddressInstruction, AddressContextInstruction, AttrInstruction = classes 314 315 if self.should_optimise_self_access() and self.have_self_input() and \ 316 not self.translation.unit.is_relocated(attrname): 317 318 # Either generate an instruction operating on an instance attribute. 319 320 try: 321 attr = self.translation.unit.parent.instance_attributes()[attrname] 322 self.translation.new_op(AttrInstruction(attr)) 323 324 # Or generate an instruction operating on a class attribute. 325 326 except KeyError: 327 attr = self.translation.unit.parent.all_attributes()[attrname] 328 329 # Switch the context if the class attribute is compatible with 330 # the instance. 331 332 if attr.defined_within_hierarchy(): 333 334 # Only permit loading (not storing) of class attributes via self. 335 336 if AddressContextInstruction is not None: 337 self.translation.new_op(AddressContextInstruction(attr)) 338 else: 339 raise TranslateError(self.translation.module.full_name(), node, 340 "Storing of class attribute %r via self not permitted." % attrname) 341 342 # Preserve the context if the class attribute comes from an 343 # incompatible class. 344 345 else: 346 if AddressInstruction is not None: 347 self.translation.new_op(AddressInstruction(attr)) 348 else: 349 raise TranslateError(self.translation.module.full_name(), node, 350 "Storing of class attribute %r via self not permitted." % attrname) 351 352 return 1 353 else: 354 return 0 355 356 def optimise_temp_storage(self): 357 358 """ 359 Where the next operation would involve storing a value into temporary 360 storage at 'temp_position', record and remove any simple instruction 361 which produced the value to be stored such that instead of subsequently 362 accessing the temporary storage, that instruction is substituted. 363 364 If no optimisation can be achieved, a StoreTemp instruction is produced 365 and the appropriate LoadTemp instruction is returned. 366 367 Restriction: for use only in situations where the source of the 368 temporary data will not be disturbed between its first access and its 369 subsequent use. 370 """ 371 372 if self.should_optimise_temp_storage() and \ 373 self.have_temp_compatible_access(): 374 375 # Remove the active value contributor. 376 377 removed = self.remove_active_value() 378 379 # Extend the lifetime of any temporary storage location. 380 381 self.translation.ensure_temp(removed) 382 return removed 383 else: 384 return self.translation.get_temp() 385 386 def optimise_load_operations(self, instruction): 387 388 """ 389 Incorporate previous load operations into other operations. 390 """ 391 392 if self.should_optimise_load_operations() and \ 393 self.have_simple_input() and \ 394 self.is_simple_input_user(instruction): 395 396 self.remove_active_value() 397 instruction.input = self.active_value 398 399 def optimise_away_no_operations(self, instruction): 400 401 """ 402 Optimise away operations which just store their inputs in the place 403 the inputs originally came from. 404 """ 405 406 if self.should_optimise_away_no_operations() and \ 407 self.is_resultant_no_operation(instruction): 408 409 return 1 410 else: 411 return 0 412 413 def optimise_unused_results(self): 414 415 "Discard results which will not be used." 416 417 if self.should_optimise_unused_results() and self.have_simple_input(): 418 self.remove_active_value() 419 420 # vim: tabstop=4 expandtab shiftwidth=4