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