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