1 #!/usr/bin/env python 2 3 """ 4 Optimise object layouts and generate access instruction plans. 5 6 Copyright (C) 2014, 2015, 2016 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 common import add_counter_item, get_attrname_from_location, init_item, \ 23 sorted_output 24 from encoders import encode_access_location, encode_instruction, get_kinds 25 from os.path import exists, join 26 from os import makedirs 27 from referencing import Reference 28 29 class Optimiser: 30 31 "Optimise objects in a program." 32 33 def __init__(self, importer, deducer, output): 34 35 """ 36 Initialise an instance using the given 'importer' and 'deducer' that 37 will perform the arrangement of attributes for program objects, writing 38 the results to the given 'output' directory. 39 """ 40 41 self.importer = importer 42 self.deducer = deducer 43 self.output = output 44 45 # Locations/offsets of attributes in objects. 46 47 self.locations = None 48 self.attr_locations = None 49 self.all_attrnames = None 50 51 # Locations of parameters in parameter tables. 52 53 self.arg_locations = None 54 self.param_locations = None 55 self.all_paramnames = None 56 57 # Specific attribute access information. 58 59 self.access_plans = {} 60 self.access_instructions = {} 61 62 # Object structure information. 63 64 self.structures = {} 65 self.attr_table = {} 66 67 # Parameter list information. 68 69 self.parameters = {} 70 self.param_table = {} 71 72 # Constant literal information. 73 74 self.constants = [] 75 self.constant_numbers = {} 76 77 # Optimiser activities. 78 79 self.populate_objects() 80 self.position_attributes() 81 self.populate_parameters() 82 self.position_parameters() 83 self.populate_tables() 84 self.populate_constants() 85 self.initialise_access_instructions() 86 87 def to_output(self): 88 89 "Write the output files using optimisation information." 90 91 if not exists(self.output): 92 makedirs(self.output) 93 94 self.write_objects() 95 96 def write_objects(self): 97 98 """ 99 Write object-related output. 100 101 The locations are a list of positions indicating the attributes residing 102 at each position in the different structures in a program. 103 104 ---- 105 106 The parameter locations are a list of positions indicating the parameters 107 residing at each position in the different parameter lists in a program. 108 109 ---- 110 111 Each attribute plan provides attribute details in the following format: 112 113 location " " name " " test " " test type " " base 114 " " traversed attributes " " traversed attribute ambiguity 115 " " traversal access modes 116 " " attributes to traverse " " attribute ambiguity 117 " " context " " access method " " static attribute 118 119 Locations have the following format: 120 121 qualified name of scope "." local name ":" name version 122 123 Traversal access modes are either "class" (obtain accessor class to 124 access attribute) or "object" (obtain attribute directly from accessor). 125 126 ---- 127 128 The structures are presented as a table in the following format: 129 130 qualified name " " attribute names 131 132 The attribute names are separated by ", " characters and indicate the 133 attribute provided at each position in the structure associated with the 134 given type. Where no attribute is provided at a particular location 135 within a structure, "-" is given. 136 137 ---- 138 139 The parameters are presented as a table in the following format: 140 141 qualified name " " parameter details 142 143 The parameter details are separated by ", " characters and indicate 144 the parameter name and list position for each parameter described at 145 each location in the parameter table associated with the given 146 function. Where no parameter details are provided at a particular 147 location within a parameter table, "-" is given. The name and list 148 position are separated by a colon (":"). 149 150 ---- 151 152 The attribute table is presented as a table in the following format: 153 154 qualified name " " attribute identifiers 155 156 Instead of attribute names, identifiers defined according to the order 157 given in the "attrnames" file are employed to denote the attributes 158 featured in each type's structure. Where no attribute is provided at a 159 particular location within a structure, "-" is given. 160 161 ---- 162 163 The parameter table is presented as a table in the following format: 164 165 qualified name " " parameter details 166 167 Instead of parameter names, identifiers defined according to the order 168 given in the "paramnames" file are employed to denote the parameters 169 featured in each function's parameter table. Where no parameter is 170 provided at a particular location within a table, "-" is given. 171 172 ---- 173 174 The ordered list of attribute names is given in the "attrnames" file. 175 176 ---- 177 178 The ordered list of parameter names is given in the "paramnames" file. 179 180 ---- 181 182 The ordered list of constant literals is given in the "constants" file. 183 """ 184 185 f = open(join(self.output, "locations"), "w") 186 try: 187 for attrnames in self.locations: 188 print >>f, sorted_output(attrnames) 189 190 finally: 191 f.close() 192 193 f = open(join(self.output, "parameter_locations"), "w") 194 try: 195 for argnames in self.arg_locations: 196 print >>f, sorted_output(argnames) 197 198 finally: 199 f.close() 200 201 f = open(join(self.output, "instruction_plans"), "w") 202 try: 203 access_instructions = self.access_instructions.items() 204 access_instructions.sort() 205 206 for location, instructions in access_instructions: 207 print >>f, encode_access_location(location), "..." 208 for instruction in instructions: 209 print >>f, encode_instruction(instruction) 210 print >>f 211 212 finally: 213 f.close() 214 215 f = open(join(self.output, "structures"), "w") 216 try: 217 structures = self.structures.items() 218 structures.sort() 219 220 for name, attrnames in structures: 221 print >>f, name, ", ".join([s or "-" for s in attrnames]) 222 223 finally: 224 f.close() 225 226 f = open(join(self.output, "parameters"), "w") 227 try: 228 parameters = self.parameters.items() 229 parameters.sort() 230 231 for name, argnames in parameters: 232 print >>f, name, ", ".join([s and ("%s:%d" % s) or "-" for s in argnames]) 233 234 finally: 235 f.close() 236 237 f = open(join(self.output, "attrtable"), "w") 238 try: 239 attr_table = self.attr_table.items() 240 attr_table.sort() 241 242 for name, attrcodes in attr_table: 243 print >>f, name, ", ".join([i is not None and str(i) or "-" for i in attrcodes]) 244 245 finally: 246 f.close() 247 248 f = open(join(self.output, "paramtable"), "w") 249 try: 250 param_table = self.param_table.items() 251 param_table.sort() 252 253 for name, paramcodes in param_table: 254 print >>f, name, ", ".join([s and ("%d:%d" % s) or "-" for s in paramcodes]) 255 256 finally: 257 f.close() 258 259 f = open(join(self.output, "attrnames"), "w") 260 try: 261 for name in self.all_attrnames: 262 print >>f, name 263 264 finally: 265 f.close() 266 267 f = open(join(self.output, "paramnames"), "w") 268 try: 269 for name in self.all_paramnames: 270 print >>f, name 271 272 finally: 273 f.close() 274 275 f = open(join(self.output, "constants"), "w") 276 try: 277 constants = [(n, value) for (value, n) in self.constants.items()] 278 constants.sort() 279 for n, value in constants: 280 print >>f, repr(value) 281 282 finally: 283 f.close() 284 285 def populate_objects(self): 286 287 "Populate objects using attribute and usage information." 288 289 all_attrs = {} 290 291 # Partition attributes into separate sections so that class and instance 292 # attributes are treated separately. 293 294 for source, objtype in [ 295 (self.importer.all_class_attrs, "<class>"), 296 (self.importer.all_instance_attrs, "<instance>"), 297 (self.importer.all_module_attrs, "<module>") 298 ]: 299 for name, attrs in source.items(): 300 all_attrs[(objtype, name)] = attrs 301 302 self.locations = get_allocated_locations(all_attrs, get_attributes_and_sizes) 303 304 def populate_parameters(self): 305 306 "Populate parameter tables using parameter information." 307 308 self.arg_locations = get_allocated_locations(self.importer.function_parameters, get_parameters_and_sizes) 309 310 def position_attributes(self): 311 312 "Position specific attribute references." 313 314 # Reverse the location mappings. 315 316 attr_locations = self.attr_locations = {} 317 318 for i, attrnames in enumerate(self.locations): 319 for attrname in attrnames: 320 attr_locations[attrname] = i 321 322 # Record the structures. 323 324 for source, objtype in [ 325 (self.importer.all_class_attrs, "<class>"), 326 (self.importer.all_instance_attrs, "<instance>"), 327 (self.importer.all_module_attrs, "<module>") 328 ]: 329 330 for name, attrnames in source.items(): 331 key = Reference(objtype, name) 332 l = self.structures[key] = [None] * len(attrnames) 333 for attrname in attrnames: 334 position = attr_locations[attrname] 335 if position >= len(l): 336 l.extend([None] * (position - len(l) + 1)) 337 l[position] = attrname 338 339 def initialise_access_instructions(self): 340 341 "Expand access plans into instruction sequences." 342 343 for access_location, access_plan in self.access_plans.items(): 344 345 # Obtain the access details. 346 347 name, test, test_type, base, traversed, traversal_modes, \ 348 attrnames, context, first_method, final_method, origin = access_plan 349 350 instructions = [] 351 emit = instructions.append 352 353 if base: 354 original_accessor = base 355 else: 356 original_accessor = "<expr>" # use a generic placeholder 357 358 # Prepare for any first attribute access. 359 360 if traversed: 361 attrname = traversed[0] 362 del traversed[0] 363 elif attrnames: 364 attrname = attrnames[0] 365 del attrnames[0] 366 367 access_first_attribute = final_method == "access" or traversed or attrnames 368 369 # Set the context if already available. 370 371 if context == "original-accessor": 372 emit(("set_context", original_accessor)) 373 accessor = "context" 374 elif context == "base": 375 emit(("set_context", base)) 376 accessor = "context" 377 elif context == "final-accessor" or access_first_attribute: 378 emit(("set_accessor", original_accessor)) 379 accessor = "accessor" 380 381 # Apply any test. 382 383 if test == "specific-type": 384 emit(("test_specific_type", accessor, test_type)) 385 elif test == "specific-instance": 386 emit(("test_specific_instance", accessor, test_type)) 387 elif test == "specific-object": 388 emit(("test_specific_object", accessor, test_type)) 389 elif test == "common-type": 390 emit(("test_common_type", accessor, test_type)) 391 elif test == "common-instance": 392 emit(("test_common_instance", accessor, test_type)) 393 elif test == "common-object": 394 emit(("test_common_object", accessor, test_type)) 395 396 # Perform the first or final access. 397 # The access only needs performing if the resulting accessor is used. 398 399 if access_first_attribute: 400 401 if first_method == "relative-class": 402 emit(("set_accessor", ("load_via_class", accessor, attrname))) 403 elif first_method == "relative-object": 404 emit(("set_accessor", ("load_via_object", accessor, attrname))) 405 elif first_method == "relative-object-class": 406 emit(("set_accessor", ("get_class_and_load", accessor, attrname))) 407 elif first_method == "check-class": 408 emit(("set_accessor", ("check_and_load_via_class", accessor, attrname))) 409 elif first_method == "check-object": 410 emit(("set_accessor", ("check_and_load_via_object", accessor, attrname))) 411 elif first_method == "check-object-class": 412 emit(("set_accessor", ("check_and_load_via_any", accessor, attrname))) 413 414 # Obtain an accessor. 415 416 remaining = len(traversed + attrnames) 417 418 if traversed: 419 for attrname, traversal_mode in zip(traversed, traversal_modes): 420 421 # Set the context, if appropriate. 422 423 if remaining == 1 and context == "final-accessor": 424 emit(("set_context", "accessor")) 425 426 # Perform the access only if not achieved directly. 427 428 if remaining > 1 or final_method == "access": 429 if traversal_mode == "class": 430 emit(("set_accessor", ("load_via_class", "accessor", attrname))) 431 else: 432 emit(("set_accessor", ("load_via_object", "accessor", attrname))) 433 434 remaining -= 1 435 436 if attrnames: 437 for attrname in attrnames: 438 439 # Set the context, if appropriate. 440 441 if remaining == 1 and context == "final-accessor": 442 emit(("set_context", "accessor")) 443 444 # Perform the access only if not achieved directly. 445 446 if remaining > 1 or final_method == "access": 447 emit(("set_accessor", ("check_and_load_via_any", "accessor", attrname))) 448 449 remaining -= 1 450 451 if final_method == "assign": 452 emit(("store_member", origin, "<expr>")) 453 elif final_method == "static": 454 emit(("load_static", origin)) 455 456 self.access_instructions[access_location] = instructions 457 458 def get_ambiguity_for_attributes(self, attrnames): 459 460 """ 461 Return a list of attribute position alternatives corresponding to each 462 of the given 'attrnames'. 463 """ 464 465 ambiguity = [] 466 467 for attrname in attrnames: 468 position = self.attr_locations[attrname] 469 ambiguity.append(len(self.locations[position])) 470 471 return ambiguity 472 473 def position_parameters(self): 474 475 "Position the parameters for each function's parameter table." 476 477 # Reverse the location mappings. 478 479 param_locations = self.param_locations = {} 480 481 for i, argnames in enumerate(self.arg_locations): 482 for argname in argnames: 483 param_locations[argname] = i 484 485 for name, argnames in self.importer.function_parameters.items(): 486 l = self.parameters[name] = [None] * len(argnames) 487 488 # Store an entry for the name along with the name's position in the 489 # parameter list. 490 491 for pos, argname in enumerate(argnames): 492 position = param_locations[argname] 493 if position >= len(l): 494 l.extend([None] * (position - len(l) + 1)) 495 l[position] = (argname, pos) 496 497 def populate_tables(self): 498 499 """ 500 Assign identifiers to attributes and encode structure information using 501 these identifiers. 502 """ 503 504 self.all_attrnames, d = self._get_name_mapping(self.attr_locations) 505 506 # Record the numbers indicating the locations of the names. 507 508 for key, attrnames in self.structures.items(): 509 l = self.attr_table[key] = [] 510 for attrname in attrnames: 511 if attrname is None: 512 l.append(None) 513 else: 514 l.append(d[attrname]) 515 516 self.all_paramnames, d = self._get_name_mapping(self.param_locations) 517 518 # Record the numbers indicating the locations of the names. 519 520 for key, values in self.parameters.items(): 521 l = self.param_table[key] = [] 522 for value in values: 523 if value is None: 524 l.append(None) 525 else: 526 name, pos = value 527 l.append((d[name], pos)) 528 529 def _get_name_mapping(self, locations): 530 531 """ 532 Get a sorted list of names from 'locations', then map them to 533 identifying numbers. Return the list and the mapping. 534 """ 535 536 all_names = locations.keys() 537 all_names.sort() 538 return all_names, dict([(name, i) for i, name in enumerate(all_names)]) 539 540 def populate_constants(self): 541 542 """ 543 Obtain a collection of distinct constant literals, building a mapping 544 from constant references to those in this collection. 545 """ 546 547 # Obtain mappings from constant values to identifiers. 548 549 self.constants = {} 550 551 for path, constants in self.importer.all_constants.items(): 552 for constant, n in constants.items(): 553 554 # Record constants and obtain a number for them. 555 556 add_counter_item(self.constants, constant) 557 558 self.constant_numbers = {} 559 560 for name, (value, value_type) in self.importer.all_constant_values.items(): 561 self.constant_numbers[name] = self.constants[value] 562 563 def combine_rows(a, b): 564 c = [] 565 for i, j in zip(a, b): 566 if i is None or j is None: 567 c.append(i or j) 568 else: 569 return None 570 return c 571 572 def get_attributes_and_sizes(d): 573 574 """ 575 Return a matrix of attributes, a list of type names corresponding to columns 576 in the matrix, and a list of ranked sizes each indicating... 577 578 * a weighted size depending on the kind of object 579 * the minimum size of an object employing an attribute 580 * the number of free columns in the matrix for the attribute 581 * the attribute name itself 582 """ 583 584 attrs = {} 585 sizes = {} 586 objtypes = {} 587 588 for name, attrnames in d.items(): 589 objtype, _name = name 590 591 for attrname in attrnames: 592 593 # Record each type supporting the attribute. 594 595 init_item(attrs, attrname, set) 596 attrs[attrname].add(name) 597 598 # Maintain a record of the smallest object size supporting the given 599 # attribute. 600 601 if not sizes.has_key(attrname): 602 sizes[attrname] = len(attrnames) 603 else: 604 sizes[attrname] = min(sizes[attrname], len(attrnames)) 605 606 # Record the object types/kinds supporting the attribute. 607 608 init_item(objtypes, attrname, set) 609 objtypes[attrname].add(objtype) 610 611 # Obtain attribute details in order of size and occupancy. 612 613 names = d.keys() 614 615 rsizes = [] 616 for attrname, size in sizes.items(): 617 priority = "<instance>" in objtypes[attrname] and 0.5 or 1 618 occupied = len(attrs[attrname]) 619 key = (priority * size, size, len(names) - occupied, attrname) 620 rsizes.append(key) 621 622 rsizes.sort() 623 624 # Make a matrix of attributes. 625 626 matrix = {} 627 for attrname, types in attrs.items(): 628 row = [] 629 for name in names: 630 if name in types: 631 row.append(attrname) 632 else: 633 row.append(None) 634 matrix[attrname] = row 635 636 return matrix, names, rsizes 637 638 def get_parameters_and_sizes(d): 639 640 """ 641 Return a matrix of parameters, a list of functions corresponding to columns 642 in the matrix, and a list of ranked sizes each indicating... 643 644 * a weighted size depending on the kind of object 645 * the minimum size of a parameter list employing a parameter 646 * the number of free columns in the matrix for the parameter 647 * the parameter name itself 648 649 This is a slightly simpler version of the above 'get_attributes_and_sizes' 650 function. 651 """ 652 653 params = {} 654 sizes = {} 655 656 for name, argnames in d.items(): 657 for argname in argnames: 658 659 # Record each function supporting the parameter. 660 661 init_item(params, argname, set) 662 params[argname].add(name) 663 664 # Maintain a record of the smallest parameter list supporting the 665 # given parameter. 666 667 if not sizes.has_key(argname): 668 sizes[argname] = len(argnames) 669 else: 670 sizes[argname] = min(sizes[argname], len(argnames)) 671 672 # Obtain attribute details in order of size and occupancy. 673 674 names = d.keys() 675 676 rsizes = [] 677 for argname, size in sizes.items(): 678 occupied = len(params[argname]) 679 key = (size, size, len(names) - occupied, argname) 680 rsizes.append(key) 681 682 rsizes.sort() 683 684 # Make a matrix of parameters. 685 686 matrix = {} 687 for argname, types in params.items(): 688 row = [] 689 for name in names: 690 if name in types: 691 row.append(argname) 692 else: 693 row.append(None) 694 matrix[argname] = row 695 696 return matrix, names, rsizes 697 698 def get_allocated_locations(d, fn): 699 700 """ 701 Return a list where each element corresponds to a structure location and 702 contains a set of attribute names that may be stored at that location, given 703 a mapping 'd' whose keys are (object type, object name) tuples and whose 704 values are collections of attributes. 705 """ 706 707 matrix, names, rsizes = fn(d) 708 allocated = [] 709 710 x = 0 711 while x < len(rsizes): 712 weight, size, free, attrname = rsizes[x] 713 base = matrix[attrname] 714 y = x + 1 715 while y < len(rsizes): 716 _weight, _size, _free, _attrname = rsizes[y] 717 occupied = len(names) - _free 718 if occupied > free: 719 break 720 new = combine_rows(base, matrix[_attrname]) 721 if new: 722 del matrix[_attrname] 723 del rsizes[y] 724 base = new 725 free -= occupied 726 else: 727 y += 1 728 allocated.append(base) 729 x += 1 730 731 # Return the list of attribute names from each row of the allocated 732 # attributes table. 733 734 return [set([attrname for attrname in attrnames if attrname]) for attrnames in allocated] 735 736 # vim: tabstop=4 expandtab shiftwidth=4