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