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