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