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