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 = [set()] + 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 381 # Prevent re-evaluation of any dynamic expression by storing it. 382 383 if original_accessor == "<expr>": 384 emit(("__set_accessor", original_accessor)) 385 accessor = context_var = ("<accessor>",) 386 else: 387 accessor = context_var = (original_accessor,) 388 389 # Assigning does not set the context. 390 391 elif context in ("final-accessor", "unset") and access_first_attribute: 392 393 # Prevent re-evaluation of any dynamic expression by storing it. 394 395 if original_accessor == "<expr>": 396 emit(("__set_accessor", original_accessor)) 397 accessor = ("<accessor>",) 398 else: 399 accessor = (original_accessor,) 400 401 # Apply any test. 402 403 if test == "specific-type": 404 accessor = ("__test_specific_type", accessor, test_type) 405 elif test == "specific-instance": 406 accessor = ("__test_specific_instance", accessor, test_type) 407 elif test == "specific-object": 408 accessor = ("__test_specific_object", accessor, test_type) 409 elif test == "common-type": 410 accessor = ("__test_common_type", accessor, test_type) 411 elif test == "common-instance": 412 accessor = ("__test_common_instance", accessor, test_type) 413 elif test == "common-object": 414 accessor = ("__test_common_object", accessor, test_type) 415 416 # Perform the first or final access. 417 # The access only needs performing if the resulting accessor is used. 418 419 remaining = len(traversed + attrnames) 420 421 if access_first_attribute: 422 423 if first_method == "relative-class": 424 if assigning: 425 emit(("__store_via_class", accessor, attrname, "<assexpr>")) 426 else: 427 accessor = ("__load_via_class", accessor, attrname) 428 429 elif first_method == "relative-object": 430 if assigning: 431 emit(("__store_via_object", accessor, attrname, "<assexpr>")) 432 else: 433 accessor = ("__load_via_object", accessor, attrname) 434 435 elif first_method == "relative-object-class": 436 if assigning: 437 emit(("__get_class_and_store", accessor, attrname, "<assexpr>")) 438 else: 439 accessor = ("__get_class_and_load", accessor, attrname) 440 441 elif first_method == "check-class": 442 if assigning: 443 emit(("__check_and_store_via_class", accessor, attrname, "<assexpr>")) 444 else: 445 accessor = ("__check_and_load_via_class", accessor, attrname) 446 447 elif first_method == "check-object": 448 if assigning: 449 emit(("__check_and_store_via_object", accessor, attrname, "<assexpr>")) 450 else: 451 accessor = ("__check_and_load_via_object", accessor, attrname) 452 453 elif first_method == "check-object-class": 454 if assigning: 455 emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>")) 456 else: 457 accessor = ("__check_and_load_via_any", accessor, attrname) 458 459 # Traverse attributes using the accessor. 460 461 if traversed: 462 for attrname, traversal_mode in zip(traversed, traversal_modes): 463 assigning = remaining == 1 and final_method == "assign" 464 465 # Set the context, if appropriate. 466 467 if remaining == 1 and final_method != "assign" and context == "final-accessor": 468 emit(("__set_context", accessor)) 469 accessor = context_var = "<context>" 470 471 # Perform the access only if not achieved directly. 472 473 if remaining > 1 or final_method in ("access", "assign"): 474 475 if traversal_mode == "class": 476 if assigning: 477 emit(("__store_via_class", accessor, attrname, "<assexpr>")) 478 else: 479 accessor = ("__load_via_class", accessor, attrname) 480 else: 481 if assigning: 482 emit(("__store_via_object", accessor, attrname, "<assexpr>")) 483 else: 484 accessor = ("__load_via_object", accessor, attrname) 485 486 remaining -= 1 487 488 if attrnames: 489 for attrname in attrnames: 490 assigning = remaining == 1 and final_method == "assign" 491 492 # Set the context, if appropriate. 493 494 if remaining == 1 and final_method != "assign" and context == "final-accessor": 495 emit(("__set_context", accessor)) 496 accessor = context_var = "<context>" 497 498 # Perform the access only if not achieved directly. 499 500 if remaining > 1 or final_method in ("access", "assign"): 501 502 if assigning: 503 emit(("__check_and_store_via_any", accessor, attrname, "<assexpr>")) 504 else: 505 accessor = ("__check_and_load_via_any", accessor, attrname) 506 507 remaining -= 1 508 509 # Define or emit the means of accessing the actual target. 510 511 if final_method == "static-assign": 512 parent, attrname = origin.rsplit(".", 1) 513 emit(("__store_via_object", parent, attrname, "<assexpr>")) 514 515 elif final_method == "static": 516 accessor = ("__load_static", origin) 517 518 elif final_method == "static-invoke": 519 kind = self.importer.get_object(origin).get_kind() 520 accessor = ("__encode_callable", origin, kind) 521 522 # Wrap accesses in context operations. 523 524 if context_test == "test": 525 emit(("__test_context", context_var, accessor)) 526 527 elif context_test == "replace": 528 529 # Static invocation targets have a context added but no other 530 # transformation performed. 531 532 if final_method == "static-invoke": 533 emit(("__update_context", context_var, accessor)) 534 535 # Other invocation targets gain a context and have the bound 536 # version of the callable activated. 537 538 else: 539 emit(("__replace_context", context_var, accessor)) 540 541 elif final_method not in ("assign", "static-assign"): 542 emit(accessor) 543 544 self.access_instructions[access_location] = instructions 545 546 def get_ambiguity_for_attributes(self, attrnames): 547 548 """ 549 Return a list of attribute position alternatives corresponding to each 550 of the given 'attrnames'. 551 """ 552 553 ambiguity = [] 554 555 for attrname in attrnames: 556 position = self.attr_locations[attrname] 557 ambiguity.append(len(self.locations[position])) 558 559 return ambiguity 560 561 def position_parameters(self): 562 563 "Position the parameters for each function's parameter table." 564 565 # Reverse the location mappings. 566 567 param_locations = self.param_locations = {} 568 569 for i, argnames in enumerate(self.arg_locations): 570 571 # Position the arguments. 572 573 for argname in argnames: 574 param_locations[argname] = i 575 576 for name, argnames in self.importer.function_parameters.items(): 577 578 # Allocate an extra context parameter in the table. 579 580 l = self.parameters[name] = [None] + [None] * len(argnames) 581 582 # Store an entry for the name along with the name's position in the 583 # parameter list. 584 585 for pos, argname in enumerate(argnames): 586 587 # Position the argument in the table. 588 589 position = param_locations[argname] 590 if position >= len(l): 591 l.extend([None] * (position - len(l) + 1)) 592 593 # Indicate an argument list position starting from 1 (after the 594 # initial context argument). 595 596 l[position] = (argname, pos + 1) 597 598 def populate_tables(self): 599 600 """ 601 Assign identifiers to attributes and encode structure information using 602 these identifiers. 603 """ 604 605 self.all_attrnames, d = self._get_name_mapping(self.attr_locations) 606 607 # Record the numbers indicating the locations of the names. 608 609 for key, attrnames in self.structures.items(): 610 l = self.attr_table[key] = [] 611 for attrname in attrnames: 612 if attrname is None: 613 l.append(None) 614 else: 615 l.append(d[attrname]) 616 617 self.all_paramnames, d = self._get_name_mapping(self.param_locations) 618 619 # Record the numbers indicating the locations of the names. 620 621 for key, values in self.parameters.items(): 622 l = self.param_table[key] = [] 623 for value in values: 624 if value is None: 625 l.append(None) 626 else: 627 name, pos = value 628 l.append((d[name], pos)) 629 630 def _get_name_mapping(self, locations): 631 632 """ 633 Get a sorted list of names from 'locations', then map them to 634 identifying numbers. Return the list and the mapping. 635 """ 636 637 all_names = locations.keys() 638 all_names.sort() 639 return all_names, dict([(name, i) for i, name in enumerate(all_names)]) 640 641 def populate_constants(self): 642 643 """ 644 Obtain a collection of distinct constant literals, building a mapping 645 from constant references to those in this collection. 646 """ 647 648 # Obtain mappings from constant values to identifiers. 649 650 self.constants = {} 651 652 for path, constants in self.importer.all_constants.items(): 653 for constant, n in constants.items(): 654 655 # Record constants and obtain a number for them. 656 657 add_counter_item(self.constants, constant) 658 659 self.constant_numbers = {} 660 661 for name, (value, value_type) in self.importer.all_constant_values.items(): 662 self.constant_numbers[name] = self.constants[value] 663 664 def combine_rows(a, b): 665 c = [] 666 for i, j in zip(a, b): 667 if i is None or j is None: 668 c.append(i or j) 669 else: 670 return None 671 return c 672 673 def get_attributes_and_sizes(d): 674 675 """ 676 Return a matrix of attributes, a list of type names corresponding to columns 677 in the matrix, and a list of ranked sizes each indicating... 678 679 * a weighted size depending on the kind of object 680 * the minimum size of an object employing an attribute 681 * the number of free columns in the matrix for the attribute 682 * the attribute name itself 683 """ 684 685 attrs = {} 686 sizes = {} 687 objtypes = {} 688 689 for name, attrnames in d.items(): 690 objtype, _name = name 691 692 for attrname in attrnames: 693 694 # Record each type supporting the attribute. 695 696 init_item(attrs, attrname, set) 697 attrs[attrname].add(name) 698 699 # Maintain a record of the smallest object size supporting the given 700 # attribute. 701 702 if not sizes.has_key(attrname): 703 sizes[attrname] = len(attrnames) 704 else: 705 sizes[attrname] = min(sizes[attrname], len(attrnames)) 706 707 # Record the object types/kinds supporting the attribute. 708 709 init_item(objtypes, attrname, set) 710 objtypes[attrname].add(objtype) 711 712 # Obtain attribute details in order of size and occupancy. 713 714 names = d.keys() 715 716 rsizes = [] 717 for attrname, size in sizes.items(): 718 priority = "<instance>" in objtypes[attrname] and 0.5 or 1 719 occupied = len(attrs[attrname]) 720 key = (priority * size, size, len(names) - occupied, attrname) 721 rsizes.append(key) 722 723 rsizes.sort() 724 725 # Make a matrix of attributes. 726 727 matrix = {} 728 for attrname, types in attrs.items(): 729 row = [] 730 for name in names: 731 if name in types: 732 row.append(attrname) 733 else: 734 row.append(None) 735 matrix[attrname] = row 736 737 return matrix, names, rsizes 738 739 def get_parameters_and_sizes(d): 740 741 """ 742 Return a matrix of parameters, a list of functions corresponding to columns 743 in the matrix, and a list of ranked sizes each indicating... 744 745 * a weighted size depending on the kind of object 746 * the minimum size of a parameter list employing a parameter 747 * the number of free columns in the matrix for the parameter 748 * the parameter name itself 749 750 This is a slightly simpler version of the above 'get_attributes_and_sizes' 751 function. 752 """ 753 754 params = {} 755 sizes = {} 756 757 for name, argnames in d.items(): 758 for argname in argnames: 759 760 # Record each function supporting the parameter. 761 762 init_item(params, argname, set) 763 params[argname].add(name) 764 765 # Maintain a record of the smallest parameter list supporting the 766 # given parameter. 767 768 if not sizes.has_key(argname): 769 sizes[argname] = len(argnames) 770 else: 771 sizes[argname] = min(sizes[argname], len(argnames)) 772 773 # Obtain attribute details in order of size and occupancy. 774 775 names = d.keys() 776 777 rsizes = [] 778 for argname, size in sizes.items(): 779 occupied = len(params[argname]) 780 key = (size, size, len(names) - occupied, argname) 781 rsizes.append(key) 782 783 rsizes.sort() 784 785 # Make a matrix of parameters. 786 787 matrix = {} 788 for argname, types in params.items(): 789 row = [] 790 for name in names: 791 if name in types: 792 row.append(argname) 793 else: 794 row.append(None) 795 matrix[argname] = row 796 797 return matrix, names, rsizes 798 799 def get_allocated_locations(d, fn): 800 801 """ 802 Return a list where each element corresponds to a structure location and 803 contains a set of attribute names that may be stored at that location, given 804 a mapping 'd' whose keys are (object type, object name) tuples and whose 805 values are collections of attributes. 806 """ 807 808 matrix, names, rsizes = fn(d) 809 allocated = [] 810 811 x = 0 812 while x < len(rsizes): 813 weight, size, free, attrname = rsizes[x] 814 base = matrix[attrname] 815 y = x + 1 816 while y < len(rsizes): 817 _weight, _size, _free, _attrname = rsizes[y] 818 occupied = len(names) - _free 819 if occupied > free: 820 break 821 new = combine_rows(base, matrix[_attrname]) 822 if new: 823 del matrix[_attrname] 824 del rsizes[y] 825 base = new 826 free -= occupied 827 else: 828 y += 1 829 allocated.append(base) 830 x += 1 831 832 # Return the list of attribute names from each row of the allocated 833 # attributes table. 834 835 locations = [] 836 for attrnames in allocated: 837 l = set() 838 for attrname in attrnames: 839 if attrname: 840 l.add(attrname) 841 locations.append(l) 842 return locations 843 844 # vim: tabstop=4 expandtab shiftwidth=4