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