1 #!/usr/bin/env python 2 3 """ 4 Optimise object layouts. 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, 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 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.refine_access_plans() 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 " " attributes to traverse " " attribute ambiguity 115 " " context " " access method " " static attribute 116 117 Locations have the following format: 118 119 qualified name of scope "." local name ":" name version 120 121 ---- 122 123 The structures are presented as a table in the following format: 124 125 qualified name " " attribute names 126 127 The attribute names are separated by ", " characters and indicate the 128 attribute provided at each position in the structure associated with the 129 given type. Where no attribute is provided at a particular location 130 within a structure, "-" is given. 131 132 ---- 133 134 The parameters are presented as a table in the following format: 135 136 qualified name " " parameter details 137 138 The parameter details are separated by ", " characters and indicate 139 the parameter name and list position for each parameter described at 140 each location in the parameter table associated with the given 141 function. Where no parameter details are provided at a particular 142 location within a parameter table, "-" is given. The name and list 143 position are separated by a colon (":"). 144 145 ---- 146 147 The attribute table is presented as a table in the following format: 148 149 qualified name " " attribute identifiers 150 151 Instead of attribute names, identifiers defined according to the order 152 given in the "attrnames" file are employed to denote the attributes 153 featured in each type's structure. Where no attribute is provided at a 154 particular location within a structure, "-" is given. 155 156 ---- 157 158 The parameter table is presented as a table in the following format: 159 160 qualified name " " parameter details 161 162 Instead of parameter names, identifiers defined according to the order 163 given in the "paramnames" file are employed to denote the parameters 164 featured in each function's parameter table. Where no parameter is 165 provided at a particular location within a table, "-" is given. 166 167 ---- 168 169 The ordered list of attribute names is given in the "attrnames" file. 170 171 ---- 172 173 The ordered list of parameter names is given in the "paramnames" file. 174 175 ---- 176 177 The ordered list of constant literals is given in the "constants" file. 178 """ 179 180 f = open(join(self.output, "locations"), "w") 181 try: 182 for attrnames in self.locations: 183 print >>f, sorted_output(attrnames) 184 185 finally: 186 f.close() 187 188 f = open(join(self.output, "parameter_locations"), "w") 189 try: 190 for argnames in self.arg_locations: 191 print >>f, sorted_output(argnames) 192 193 finally: 194 f.close() 195 196 f = open(join(self.output, "attribute_plans"), "w") 197 try: 198 access_plans = self.access_plans.items() 199 access_plans.sort() 200 201 for location, (name, test, test_type, base, 202 traversed, traversed_ambiguity, 203 attrnames, attrnames_ambiguity, context, method, attr) in access_plans: 204 205 print >>f, encode_access_location(location), \ 206 name, test, test_type or "{}", \ 207 base or "{}", \ 208 ".".join(traversed) or "{}", \ 209 ".".join(map(str, traversed_ambiguity)) or "{}", \ 210 ".".join(map(str, attrnames_ambiguity)) or "{}", \ 211 ".".join(attrnames) or "{}", \ 212 context, method, attr or "{}" 213 214 finally: 215 f.close() 216 217 f = open(join(self.output, "structures"), "w") 218 try: 219 structures = self.structures.items() 220 structures.sort() 221 222 for name, attrnames in structures: 223 print >>f, name, ", ".join([s or "-" for s in attrnames]) 224 225 finally: 226 f.close() 227 228 f = open(join(self.output, "parameters"), "w") 229 try: 230 parameters = self.parameters.items() 231 parameters.sort() 232 233 for name, argnames in parameters: 234 print >>f, name, ", ".join([s and ("%s:%d" % s) or "-" for s in argnames]) 235 236 finally: 237 f.close() 238 239 f = open(join(self.output, "attrtable"), "w") 240 try: 241 attr_table = self.attr_table.items() 242 attr_table.sort() 243 244 for name, attrcodes in attr_table: 245 print >>f, name, ", ".join([i is not None and str(i) or "-" for i in attrcodes]) 246 247 finally: 248 f.close() 249 250 f = open(join(self.output, "paramtable"), "w") 251 try: 252 param_table = self.param_table.items() 253 param_table.sort() 254 255 for name, paramcodes in param_table: 256 print >>f, name, ", ".join([s and ("%d:%d" % s) or "-" for s in paramcodes]) 257 258 finally: 259 f.close() 260 261 f = open(join(self.output, "attrnames"), "w") 262 try: 263 for name in self.all_attrnames: 264 print >>f, name 265 266 finally: 267 f.close() 268 269 f = open(join(self.output, "paramnames"), "w") 270 try: 271 for name in self.all_paramnames: 272 print >>f, name 273 274 finally: 275 f.close() 276 277 f = open(join(self.output, "constants"), "w") 278 try: 279 constants = [(n, value) for (value, n) in self.constants.items()] 280 constants.sort() 281 for n, value in constants: 282 print >>f, repr(value) 283 284 finally: 285 f.close() 286 287 def populate_objects(self): 288 289 "Populate objects using attribute and usage information." 290 291 all_attrs = {} 292 293 # Partition attributes into separate sections so that class and instance 294 # attributes are treated separately. 295 296 for source, objtype in [ 297 (self.importer.all_class_attrs, "<class>"), 298 (self.importer.all_instance_attrs, "<instance>"), 299 (self.importer.all_module_attrs, "<module>") 300 ]: 301 for name, attrs in source.items(): 302 all_attrs[(objtype, name)] = attrs 303 304 self.locations = get_allocated_locations(all_attrs, get_attributes_and_sizes) 305 306 def populate_parameters(self): 307 308 "Populate parameter tables using parameter information." 309 310 self.arg_locations = get_allocated_locations(self.importer.function_parameters, get_parameters_and_sizes) 311 312 def position_attributes(self): 313 314 "Position specific attribute references." 315 316 # Reverse the location mappings. 317 318 attr_locations = self.attr_locations = {} 319 320 for i, attrnames in enumerate(self.locations): 321 for attrname in attrnames: 322 attr_locations[attrname] = i 323 324 # Record the structures. 325 326 for source, objtype in [ 327 (self.importer.all_class_attrs, "<class>"), 328 (self.importer.all_instance_attrs, "<instance>"), 329 (self.importer.all_module_attrs, "<module>") 330 ]: 331 332 for name, attrnames in source.items(): 333 key = Reference(objtype, name) 334 l = self.structures[key] = [None] * len(attrnames) 335 for attrname in attrnames: 336 position = attr_locations[attrname] 337 if position >= len(l): 338 l.extend([None] * (position - len(l) + 1)) 339 l[position] = attrname 340 341 def refine_access_plans(self): 342 343 "Augment deduced access plans with attribute position information." 344 345 for access_location, access_plan in self.deducer.access_plans.items(): 346 347 # Obtain the access details. 348 349 name, test, test_type, base, traversed, attrnames, \ 350 context, method, attr = access_plan 351 352 traversed_ambiguity = self.get_ambiguity_for_attributes(traversed) 353 attrnames_ambiguity = self.get_ambiguity_for_attributes(attrnames) 354 355 self.access_plans[access_location] = \ 356 name, test, test_type, base, traversed, traversed_ambiguity, \ 357 attrnames, attrnames_ambiguity, context, method, attr 358 359 def get_ambiguity_for_attributes(self, attrnames): 360 361 """ 362 Return a list of attribute position alternatives corresponding to each 363 of the given 'attrnames'. 364 """ 365 366 ambiguity = [] 367 368 for attrname in attrnames: 369 position = self.attr_locations[attrname] 370 ambiguity.append(len(self.locations[position])) 371 372 return ambiguity 373 374 def position_parameters(self): 375 376 "Position the parameters for each function's parameter table." 377 378 # Reverse the location mappings. 379 380 param_locations = self.param_locations = {} 381 382 for i, argnames in enumerate(self.arg_locations): 383 for argname in argnames: 384 param_locations[argname] = i 385 386 for name, argnames in self.importer.function_parameters.items(): 387 l = self.parameters[name] = [None] * len(argnames) 388 389 # Store an entry for the name along with the name's position in the 390 # parameter list. 391 392 for pos, argname in enumerate(argnames): 393 position = param_locations[argname] 394 if position >= len(l): 395 l.extend([None] * (position - len(l) + 1)) 396 l[position] = (argname, pos) 397 398 def populate_tables(self): 399 400 """ 401 Assign identifiers to attributes and encode structure information using 402 these identifiers. 403 """ 404 405 self.all_attrnames, d = self._get_name_mapping(self.attr_locations) 406 407 # Record the numbers indicating the locations of the names. 408 409 for key, attrnames in self.structures.items(): 410 l = self.attr_table[key] = [] 411 for attrname in attrnames: 412 if attrname is None: 413 l.append(None) 414 else: 415 l.append(d[attrname]) 416 417 self.all_paramnames, d = self._get_name_mapping(self.param_locations) 418 419 # Record the numbers indicating the locations of the names. 420 421 for key, values in self.parameters.items(): 422 l = self.param_table[key] = [] 423 for value in values: 424 if value is None: 425 l.append(None) 426 else: 427 name, pos = value 428 l.append((d[name], pos)) 429 430 def _get_name_mapping(self, locations): 431 432 """ 433 Get a sorted list of names from 'locations', then map them to 434 identifying numbers. Return the list and the mapping. 435 """ 436 437 all_names = locations.keys() 438 all_names.sort() 439 return all_names, dict([(name, i) for i, name in enumerate(all_names)]) 440 441 def populate_constants(self): 442 443 """ 444 Obtain a collection of distinct constant literals, building a mapping 445 from constant references to those in this collection. 446 """ 447 448 # Obtain mappings from constant values to identifiers. 449 450 self.constants = {} 451 452 for path, constants in self.importer.all_constants.items(): 453 for constant, n in constants.items(): 454 455 # Record constants and obtain a number for them. 456 457 add_counter_item(self.constants, constant) 458 459 self.constant_numbers = {} 460 461 for name, (value, value_type) in self.importer.all_constant_values.items(): 462 self.constant_numbers[name] = self.constants[value] 463 464 def combine_rows(a, b): 465 c = [] 466 for i, j in zip(a, b): 467 if i is None or j is None: 468 c.append(i or j) 469 else: 470 return None 471 return c 472 473 def get_attributes_and_sizes(d): 474 475 """ 476 Return a matrix of attributes, a list of type names corresponding to columns 477 in the matrix, and a list of ranked sizes each indicating... 478 479 * a weighted size depending on the kind of object 480 * the minimum size of an object employing an attribute 481 * the number of free columns in the matrix for the attribute 482 * the attribute name itself 483 """ 484 485 attrs = {} 486 sizes = {} 487 objtypes = {} 488 489 for name, attrnames in d.items(): 490 objtype, _name = name 491 492 for attrname in attrnames: 493 494 # Record each type supporting the attribute. 495 496 init_item(attrs, attrname, set) 497 attrs[attrname].add(name) 498 499 # Maintain a record of the smallest object size supporting the given 500 # attribute. 501 502 if not sizes.has_key(attrname): 503 sizes[attrname] = len(attrnames) 504 else: 505 sizes[attrname] = min(sizes[attrname], len(attrnames)) 506 507 # Record the object types/kinds supporting the attribute. 508 509 init_item(objtypes, attrname, set) 510 objtypes[attrname].add(objtype) 511 512 # Obtain attribute details in order of size and occupancy. 513 514 names = d.keys() 515 516 rsizes = [] 517 for attrname, size in sizes.items(): 518 priority = "<instance>" in objtypes[attrname] and 0.5 or 1 519 occupied = len(attrs[attrname]) 520 key = (priority * size, size, len(names) - occupied, attrname) 521 rsizes.append(key) 522 523 rsizes.sort() 524 525 # Make a matrix of attributes. 526 527 matrix = {} 528 for attrname, types in attrs.items(): 529 row = [] 530 for name in names: 531 if name in types: 532 row.append(attrname) 533 else: 534 row.append(None) 535 matrix[attrname] = row 536 537 return matrix, names, rsizes 538 539 def get_parameters_and_sizes(d): 540 541 """ 542 Return a matrix of parameters, a list of functions corresponding to columns 543 in the matrix, and a list of ranked sizes each indicating... 544 545 * a weighted size depending on the kind of object 546 * the minimum size of a parameter list employing a parameter 547 * the number of free columns in the matrix for the parameter 548 * the parameter name itself 549 550 This is a slightly simpler version of the above 'get_attributes_and_sizes' 551 function. 552 """ 553 554 params = {} 555 sizes = {} 556 557 for name, argnames in d.items(): 558 for argname in argnames: 559 560 # Record each function supporting the parameter. 561 562 init_item(params, argname, set) 563 params[argname].add(name) 564 565 # Maintain a record of the smallest parameter list supporting the 566 # given parameter. 567 568 if not sizes.has_key(argname): 569 sizes[argname] = len(argnames) 570 else: 571 sizes[argname] = min(sizes[argname], len(argnames)) 572 573 # Obtain attribute details in order of size and occupancy. 574 575 names = d.keys() 576 577 rsizes = [] 578 for argname, size in sizes.items(): 579 occupied = len(params[argname]) 580 key = (size, size, len(names) - occupied, argname) 581 rsizes.append(key) 582 583 rsizes.sort() 584 585 # Make a matrix of parameters. 586 587 matrix = {} 588 for argname, types in params.items(): 589 row = [] 590 for name in names: 591 if name in types: 592 row.append(argname) 593 else: 594 row.append(None) 595 matrix[argname] = row 596 597 return matrix, names, rsizes 598 599 def get_allocated_locations(d, fn): 600 601 """ 602 Return a list where each element corresponds to a structure location and 603 contains a set of attribute names that may be stored at that location, given 604 a mapping 'd' whose keys are (object type, object name) tuples and whose 605 values are collections of attributes. 606 """ 607 608 matrix, names, rsizes = fn(d) 609 allocated = [] 610 611 x = 0 612 while x < len(rsizes): 613 weight, size, free, attrname = rsizes[x] 614 base = matrix[attrname] 615 y = x + 1 616 while y < len(rsizes): 617 _weight, _size, _free, _attrname = rsizes[y] 618 occupied = len(names) - _free 619 if occupied > free: 620 break 621 new = combine_rows(base, matrix[_attrname]) 622 if new: 623 del matrix[_attrname] 624 del rsizes[y] 625 base = new 626 free -= occupied 627 else: 628 y += 1 629 allocated.append(base) 630 x += 1 631 632 # Return the list of attribute names from each row of the allocated 633 # attributes table. 634 635 return [set([attrname for attrname in attrnames if attrname]) for attrnames in allocated] 636 637 # vim: tabstop=4 expandtab shiftwidth=4