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