1 #!/usr/bin/env python 2 3 """ 4 Optimise code produced by the AST translator. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011 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", "no_operations", "unused_results", 34 "unused_handlers", "accesses_by_usage", 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 # Instructions providing the active value. 57 58 self.active_values = set() 59 60 def get_attribute_store_instructions(self): 61 62 """ 63 Return an appropriate set of instructions available when storing 64 attributes. 65 """ 66 67 ca = self.should_optimise_accesses_by_attribute_usage() 68 69 return ( 70 ca and StoreAddress or None, # plain assignment 71 ca and StoreAddressContext or None, # assignment via class 72 ca and StoreAddressContext or None, # assignment via class (never via instance) 73 StoreAttr, # assignment via instance 74 StoreAttrIndex, # special assignment via instance 75 None 76 ) 77 78 def reset(self, block=None, blocks=None): 79 80 """ 81 Reset the optimiser for the given 'block' (or the current block), 82 clearing the active value instructions if no 'blocks' are given, or 83 collecting the active instructions from each of the blocks otherwise. 84 """ 85 86 self.clear_active() 87 88 # Make a new collection of instructions for a new block. 89 90 if block: 91 self.active_values = set() 92 block.set_active_values(self.active_values) 93 94 # Otherwise, clear the collection for an existing block. 95 96 else: 97 self.active_values.clear() 98 99 if blocks: 100 for b in blocks: 101 self.active_values.update(b.get_active_values()) 102 103 def set_new(self, op): 104 105 "Set the latest 'op' as the active instruction." 106 107 self.set_active(op) 108 self.set_active_value(op) 109 110 def set_active_value(self, op): 111 112 "Set the value-providing active instruction." 113 114 if isinstance(op, current_value_instructions) and op.target == "working": 115 self.active_values.clear() 116 self.active_values.add(op) 117 118 def get_active_value(self): 119 120 "Get any single active value or None if none or more than one exist." 121 122 if len(self.active_values) == 1: 123 return list(self.active_values)[0] 124 else: 125 return None 126 127 def remove_active_value(self): 128 129 """ 130 Remove the value-providing active instruction from the generated code, 131 if appropriate, but keep a record of the active instruction itself. 132 """ 133 134 if self.active in self.active_values: 135 removed = self.active 136 self.translation.remove_op() 137 return removed 138 else: 139 return None 140 141 def set_target(self, target): 142 143 "Set the target of the active instruction to 'target'." 144 145 for expr in self.active_values: 146 expr.target = target 147 148 def set_active(self, op): 149 150 "Set the active instruction." 151 152 self.active = op 153 154 def clear_active(self): 155 156 "Clear the active instructions." 157 158 self.active = None 159 160 # Optimisation tests. 161 162 def should_optimise_constant_storage(self): 163 return "constant_storage" in self.optimisations 164 165 def should_optimise_constant_accessor(self): 166 return "constant_accessor" in self.optimisations 167 168 def should_optimise_known_target(self): 169 return "known_target" in self.optimisations 170 171 def should_optimise_self_access(self): 172 return "self_access" in self.optimisations 173 174 def should_optimise_temp_storage(self): 175 return "temp_storage" in self.optimisations 176 177 def should_optimise_away_no_operations(self): 178 return "no_operations" in self.optimisations 179 180 def should_optimise_unused_results(self): 181 return "unused_results" in self.optimisations 182 183 def should_optimise_unused_handlers(self): 184 return "unused_handlers" in self.optimisations 185 186 def should_optimise_accesses_by_attribute_usage(self): 187 return "accesses_by_usage" in self.optimisations 188 189 # Simple tests. 190 191 def is_constant_input(self, instruction): 192 193 "Return whether 'instruction' provides a constant input." 194 195 return isinstance(instruction, LoadAddress) and instruction.attr.assignments == 1 and \ 196 isinstance(instruction.attr.get_value(), Constant) or \ 197 isinstance(instruction, (LoadConst, LoadClass, LoadFunction)) 198 199 def is_constant_target(self, instruction): 200 201 "Return whether 'instruction' provides a constant target." 202 203 # NOTE: Removed StoreName, since this would then demand population of 204 # NOTE: locals/frames. 205 206 return isinstance(instruction, (StoreAddress, StoreAddressContext)) and \ 207 instruction.attr.assignments == 1 208 209 def is_simple_input(self, instruction): 210 211 """ 212 Return whether 'instruction' provides a simple input (typically a load 213 instruction). A simple input is something which would be represented by 214 a load operation from a CPU register or special memory location. 215 """ 216 217 return isinstance(instruction, (LoadConst, LoadClass, LoadFunction, 218 LoadName, LoadTemp, LoadAddress 219 )) 220 221 def is_resultant_no_operation(self, instruction): 222 223 """ 224 Return whether 'instruction' merely stores its input where the input 225 originally came from. 226 """ 227 228 return ( 229 isinstance(instruction, StoreTemp) and instruction.target == instruction.source 230 ) 231 232 # Convenience tests on outputs. 233 234 def have_constant_target(self): 235 236 "Return whether the active instruction provides a constant target." 237 238 return self.is_constant_target(self.active) 239 240 def have_constant_source(self, expr): 241 242 "Return whether the active assignment source instruction is constant." 243 244 return self.is_constant_input(expr) 245 246 # Convenience tests on inputs. 247 248 def have_constant_input(self): 249 250 "Return whether the active instruction provides a constant input." 251 252 return self.get_active_value() and self.is_constant_input(self.get_active_value()) 253 254 def have_simple_input(self): 255 256 "Return whether the active instruction provides a simple input." 257 258 return self.get_active_value() and self.is_simple_input(self.get_active_value()) 259 260 # Indicate whether the active instruction can be used in place of access 261 # to a temporary variable retaining the result of the last instruction. 262 263 have_temp_compatible_access = have_simple_input 264 265 def have_self_input(self, unit): 266 267 """ 268 Return whether the active instruction is a reference to self in the 269 given 'unit'. 270 """ 271 272 if not (isinstance(unit, Function) and unit.is_method()): 273 return 0 274 275 expr = self.get_active_value() 276 return expr and isinstance(expr, LoadName) and expr.attr.name == "self" 277 278 def have_correct_self_for_target(self, context, unit): 279 280 "Return whether the 'context' is compatible with the given 'unit'." 281 282 if context is not None and self.have_self_input(unit): 283 284 parent = unit.parent 285 if parent is context or parent.has_subclass(context) or context.has_subclass(parent): 286 return 1 287 288 return 0 289 290 def have_empty_handler(self, instruction): 291 292 """ 293 Return whether the active instruction defined a handler for exceptions 294 which is then discarded by the given 'instruction'. 295 """ 296 297 return isinstance(self.translation.last_op(), PushHandler) and isinstance(instruction, PopHandler) 298 299 # Optimisation methods. See the supported_optimisations class attribute. 300 301 def optimise_constant_storage(self, expr=None): 302 303 """ 304 Where the last operation stores a constant into a target which is also 305 constant, indicate that both operations should be optimised away. 306 """ 307 308 return self.should_optimise_constant_storage() and \ 309 self.have_constant_target() and \ 310 self.have_constant_source(expr) 311 312 def optimise_constant_accessor(self): 313 314 """ 315 Where the object whose attribute is being accessed is constant, provide 316 information about the object and its full name. 317 """ 318 319 if self.should_optimise_constant_accessor() and self.have_constant_input(): 320 value = self.get_active_value() 321 322 # Get the details of the access. 323 324 if isinstance(value.attr, Const): 325 return value.attr, value.attr.value_type_name() 326 else: 327 target = value.attr.get_value() 328 329 if target is None: 330 return None # no clearly defined target 331 elif isinstance(target, Const): 332 return target, target.value_type_name() 333 elif isinstance(target, Instance): 334 return None # skip production of optimised code 335 else: 336 return target, target.full_name() 337 338 else: 339 return None 340 341 def optimise_known_target(self): 342 343 """ 344 Where the target of an invocation is known, provide information about it 345 and its context. If a class is being invoked and the conditions are 346 appropriate, get information about the specific initialiser. 347 """ 348 349 if self.should_optimise_known_target() and self.have_constant_input(): 350 value = self.get_active_value() 351 target = value.attr.get_value() 352 context = value.attr.get_context() 353 354 # Return target details only if this is clearly defined. 355 356 if target is not None: 357 return target, context 358 359 return None 360 361 def optimise_self_access(self, unit, attrname): 362 363 """ 364 Return whether code in the given 'unit' is able to access the given 365 'attrname' through the same position in all possible objects which might 366 be accessed. 367 """ 368 369 return self.should_optimise_self_access() and \ 370 self.have_self_input(unit) and not unit.is_relocated(attrname) 371 372 def optimise_temp_storage(self): 373 374 """ 375 Where the next operation would involve storing a value into temporary 376 storage, record and remove any simple instruction which produced the 377 value to be stored such that instead of subsequently accessing the 378 temporary storage, that instruction is substituted. 379 380 If no optimisation can be achieved, a StoreTemp instruction is produced 381 and the appropriate LoadTemp instruction is returned. 382 383 Restriction: for use only in situations where the source of the 384 temporary data will not be disturbed between its first access and its 385 subsequent use. 386 """ 387 388 if self.should_optimise_temp_storage() and \ 389 self.have_temp_compatible_access(): 390 391 # Remove the active value contributor. 392 393 removed = self.remove_active_value() 394 if removed is not None: 395 396 # Extend the lifetime of any temporary storage location. 397 398 self.translation.ensure_temp(removed) 399 return removed 400 401 return self.translation.get_temp() 402 403 def optimise_away_no_operations(self, instruction): 404 405 """ 406 Optimise away operations which just store their inputs in the place 407 the inputs originally came from. 408 """ 409 410 return self.should_optimise_away_no_operations() and \ 411 self.is_resultant_no_operation(instruction) 412 413 def optimise_unused_results(self): 414 415 "Discard results which will not be used." 416 417 if self.should_optimise_unused_results() and self.have_simple_input(): 418 self.remove_active_value() 419 420 def optimise_unused_handlers(self, instruction): 421 422 "Discard handlers which will not be used." 423 424 if self.should_optimise_unused_handlers() and self.have_empty_handler(instruction): 425 self.translation.remove_op() 426 return 1 427 else: 428 return 0 429 430 # vim: tabstop=4 expandtab shiftwidth=4