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