1 /* 2 * Section utility functions 3 * 4 * Copyright (C) 2001-2007 Peter Johnson 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND OTHER CONTRIBUTORS ``AS IS'' 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR OTHER CONTRIBUTORS BE 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 21 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 22 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 23 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 24 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 25 * POSSIBILITY OF SUCH DAMAGE. 26 */ 27 #include "util.h" 28 29 #include <limits.h> 30 31 #include "libyasm-stdint.h" 32 #include "coretype.h" 33 #include "hamt.h" 34 #include "valparam.h" 35 #include "assocdat.h" 36 37 #include "linemap.h" 38 #include "errwarn.h" 39 #include "intnum.h" 40 #include "expr.h" 41 #include "value.h" 42 #include "symrec.h" 43 44 #include "bytecode.h" 45 #include "arch.h" 46 #include "section.h" 47 48 #include "dbgfmt.h" 49 #include "objfmt.h" 50 51 #include "inttree.h" 52 53 54 struct yasm_section { 55 /*@reldef@*/ STAILQ_ENTRY(yasm_section) link; 56 57 /*@dependent@*/ yasm_object *object; /* Pointer to parent object */ 58 59 /*@owned@*/ char *name; /* strdup()'ed name (given by user) */ 60 61 /* associated data; NULL if none */ 62 /*@null@*/ /*@only@*/ yasm__assoc_data *assoc_data; 63 64 unsigned long align; /* Section alignment */ 65 66 unsigned long opt_flags; /* storage for optimizer flags */ 67 68 int code; /* section contains code (instructions) */ 69 int res_only; /* allow only resb family of bytecodes? */ 70 int def; /* "default" section, e.g. not specified by 71 using section directive */ 72 73 /* the bytecodes for the section's contents */ 74 /*@reldef@*/ STAILQ_HEAD(yasm_bytecodehead, yasm_bytecode) bcs; 75 76 /* the relocations for the section */ 77 /*@reldef@*/ STAILQ_HEAD(yasm_relochead, yasm_reloc) relocs; 78 79 void (*destroy_reloc) (/*@only@*/ void *reloc); 80 }; 81 82 static void yasm_section_destroy(/*@only@*/ yasm_section *sect); 83 84 /* Wrapper around directive for HAMT insertion */ 85 typedef struct yasm_directive_wrap { 86 const yasm_directive *directive; 87 } yasm_directive_wrap; 88 89 /* 90 * Standard "builtin" object directives. 91 */ 92 93 static void 94 dir_extern(yasm_object *object, yasm_valparamhead *valparams, 95 yasm_valparamhead *objext_valparams, unsigned long line) 96 { 97 yasm_valparam *vp = yasm_vps_first(valparams); 98 yasm_symrec *sym; 99 sym = yasm_symtab_declare(object->symtab, yasm_vp_id(vp), YASM_SYM_EXTERN, 100 line); 101 if (objext_valparams) { 102 yasm_valparamhead *vps = yasm_vps_create(); 103 *vps = *objext_valparams; /* structure copy */ 104 yasm_vps_initialize(objext_valparams); /* don't double-free */ 105 yasm_symrec_set_objext_valparams(sym, vps); 106 } 107 } 108 109 static void 110 dir_global(yasm_object *object, yasm_valparamhead *valparams, 111 yasm_valparamhead *objext_valparams, unsigned long line) 112 { 113 yasm_valparam *vp = yasm_vps_first(valparams); 114 yasm_symrec *sym; 115 sym = yasm_symtab_declare(object->symtab, yasm_vp_id(vp), YASM_SYM_GLOBAL, 116 line); 117 if (objext_valparams) { 118 yasm_valparamhead *vps = yasm_vps_create(); 119 *vps = *objext_valparams; /* structure copy */ 120 yasm_vps_initialize(objext_valparams); /* don't double-free */ 121 yasm_symrec_set_objext_valparams(sym, vps); 122 } 123 } 124 125 static void 126 dir_common(yasm_object *object, yasm_valparamhead *valparams, 127 yasm_valparamhead *objext_valparams, unsigned long line) 128 { 129 yasm_valparam *vp = yasm_vps_first(valparams); 130 yasm_valparam *vp2 = yasm_vps_next(vp); 131 yasm_expr *size = yasm_vp_expr(vp2, object->symtab, line); 132 yasm_symrec *sym; 133 134 if (!size) { 135 yasm_error_set(YASM_ERROR_SYNTAX, 136 N_("no size specified in %s declaration"), "COMMON"); 137 return; 138 } 139 sym = yasm_symtab_declare(object->symtab, yasm_vp_id(vp), YASM_SYM_COMMON, 140 line); 141 yasm_symrec_set_common_size(sym, size); 142 if (objext_valparams) { 143 yasm_valparamhead *vps = yasm_vps_create(); 144 *vps = *objext_valparams; /* structure copy */ 145 yasm_vps_initialize(objext_valparams); /* don't double-free */ 146 yasm_symrec_set_objext_valparams(sym, vps); 147 } 148 } 149 150 static void 151 dir_section(yasm_object *object, yasm_valparamhead *valparams, 152 yasm_valparamhead *objext_valparams, unsigned long line) 153 { 154 yasm_section *new_section = 155 yasm_objfmt_section_switch(object, valparams, objext_valparams, line); 156 if (new_section) 157 object->cur_section = new_section; 158 else 159 yasm_error_set(YASM_ERROR_SYNTAX, 160 N_("invalid argument to directive `%s'"), "SECTION"); 161 } 162 163 static const yasm_directive object_directives[] = { 164 { ".extern", "gas", dir_extern, YASM_DIR_ID_REQUIRED }, 165 { ".global", "gas", dir_global, YASM_DIR_ID_REQUIRED }, 166 { ".globl", "gas", dir_global, YASM_DIR_ID_REQUIRED }, 167 { "extern", "nasm", dir_extern, YASM_DIR_ID_REQUIRED }, 168 { "global", "nasm", dir_global, YASM_DIR_ID_REQUIRED }, 169 { "common", "nasm", dir_common, YASM_DIR_ID_REQUIRED }, 170 { "section", "nasm", dir_section, YASM_DIR_ARG_REQUIRED }, 171 { "segment", "nasm", dir_section, YASM_DIR_ARG_REQUIRED }, 172 { NULL, NULL, NULL, 0 } 173 }; 174 175 static void 176 directive_level2_delete(/*@only@*/ void *data) 177 { 178 yasm_xfree(data); 179 } 180 181 static void 182 directive_level1_delete(/*@only@*/ void *data) 183 { 184 HAMT_destroy(data, directive_level2_delete); 185 } 186 187 static void 188 directives_add(yasm_object *object, /*@null@*/ const yasm_directive *dir) 189 { 190 if (!dir) 191 return; 192 193 while (dir->name) { 194 HAMT *level2 = HAMT_search(object->directives, dir->parser); 195 int replace; 196 yasm_directive_wrap *wrap = yasm_xmalloc(sizeof(yasm_directive_wrap)); 197 198 if (!level2) { 199 replace = 0; 200 level2 = HAMT_insert(object->directives, dir->parser, 201 HAMT_create(1, yasm_internal_error_), 202 &replace, directive_level1_delete); 203 } 204 replace = 0; 205 wrap->directive = dir; 206 HAMT_insert(level2, dir->name, wrap, &replace, 207 directive_level2_delete); 208 dir++; 209 } 210 } 211 212 /*@-compdestroy@*/ 213 yasm_object * 214 yasm_object_create(const char *src_filename, const char *obj_filename, 215 /*@kept@*/ yasm_arch *arch, 216 const yasm_objfmt_module *objfmt_module, 217 const yasm_dbgfmt_module *dbgfmt_module) 218 { 219 yasm_object *object = yasm_xmalloc(sizeof(yasm_object)); 220 int matched, i; 221 222 object->src_filename = yasm__xstrdup(src_filename); 223 object->obj_filename = yasm__xstrdup(obj_filename); 224 225 /* No prefix/suffix */ 226 object->global_prefix = yasm__xstrdup(""); 227 object->global_suffix = yasm__xstrdup(""); 228 229 /* Create empty symbol table */ 230 object->symtab = yasm_symtab_create(); 231 232 /* Initialize sections linked list */ 233 STAILQ_INIT(&object->sections); 234 235 /* Create directives HAMT */ 236 object->directives = HAMT_create(1, yasm_internal_error_); 237 238 /* Initialize the target architecture */ 239 object->arch = arch; 240 241 /* Initialize things to NULL in case of error */ 242 object->dbgfmt = NULL; 243 244 /* Initialize the object format */ 245 object->objfmt = yasm_objfmt_create(objfmt_module, object); 246 if (!object->objfmt) { 247 yasm_error_set(YASM_ERROR_GENERAL, 248 N_("object format `%s' does not support architecture `%s' machine `%s'"), 249 objfmt_module->keyword, ((yasm_arch_base *)arch)->module->keyword, 250 yasm_arch_get_machine(arch)); 251 goto error; 252 } 253 254 /* Get a fresh copy of objfmt_module as it may have changed. */ 255 objfmt_module = ((yasm_objfmt_base *)object->objfmt)->module; 256 257 /* Add an initial "default" section to object */ 258 object->cur_section = yasm_objfmt_add_default_section(object); 259 260 /* Check to see if the requested debug format is in the allowed list 261 * for the active object format. 262 */ 263 matched = 0; 264 for (i=0; objfmt_module->dbgfmt_keywords[i]; i++) 265 if (yasm__strcasecmp(objfmt_module->dbgfmt_keywords[i], 266 dbgfmt_module->keyword) == 0) 267 matched = 1; 268 if (!matched) { 269 yasm_error_set(YASM_ERROR_GENERAL, 270 N_("`%s' is not a valid debug format for object format `%s'"), 271 dbgfmt_module->keyword, objfmt_module->keyword); 272 goto error; 273 } 274 275 /* Initialize the debug format */ 276 object->dbgfmt = yasm_dbgfmt_create(dbgfmt_module, object); 277 if (!object->dbgfmt) { 278 yasm_error_set(YASM_ERROR_GENERAL, 279 N_("debug format `%s' does not work with object format `%s'"), 280 dbgfmt_module->keyword, objfmt_module->keyword); 281 goto error; 282 } 283 284 /* Add directives to HAMT. Note ordering here determines priority. */ 285 directives_add(object, 286 ((yasm_objfmt_base *)object->objfmt)->module->directives); 287 directives_add(object, 288 ((yasm_dbgfmt_base *)object->dbgfmt)->module->directives); 289 directives_add(object, 290 ((yasm_arch_base *)object->arch)->module->directives); 291 directives_add(object, object_directives); 292 293 return object; 294 295 error: 296 yasm_object_destroy(object); 297 return NULL; 298 } 299 /*@=compdestroy@*/ 300 301 /*@-onlytrans@*/ 302 yasm_section * 303 yasm_object_get_general(yasm_object *object, const char *name, 304 unsigned long align, int code, int res_only, 305 int *isnew, unsigned long line) 306 { 307 yasm_section *s; 308 yasm_bytecode *bc; 309 310 /* Search through current sections to see if we already have one with 311 * that name. 312 */ 313 STAILQ_FOREACH(s, &object->sections, link) { 314 if (strcmp(s->name, name) == 0) { 315 *isnew = 0; 316 return s; 317 } 318 } 319 320 /* No: we have to allocate and create a new one. */ 321 322 /* Okay, the name is valid; now allocate and initialize */ 323 s = yasm_xcalloc(1, sizeof(yasm_section)); 324 STAILQ_INSERT_TAIL(&object->sections, s, link); 325 326 s->object = object; 327 s->name = yasm__xstrdup(name); 328 s->assoc_data = NULL; 329 s->align = align; 330 331 /* Initialize bytecodes with one empty bytecode (acts as "prior" for first 332 * real bytecode in section. 333 */ 334 STAILQ_INIT(&s->bcs); 335 bc = yasm_bc_create_common(NULL, NULL, 0); 336 bc->section = s; 337 bc->offset = 0; 338 STAILQ_INSERT_TAIL(&s->bcs, bc, link); 339 340 /* Initialize relocs */ 341 STAILQ_INIT(&s->relocs); 342 s->destroy_reloc = NULL; 343 344 s->code = code; 345 s->res_only = res_only; 346 s->def = 0; 347 348 /* Initialize object format specific data */ 349 yasm_objfmt_init_new_section(s, line); 350 351 *isnew = 1; 352 return s; 353 } 354 /*@=onlytrans@*/ 355 356 int 357 yasm_object_directive(yasm_object *object, const char *name, 358 const char *parser, yasm_valparamhead *valparams, 359 yasm_valparamhead *objext_valparams, 360 unsigned long line) 361 { 362 HAMT *level2; 363 yasm_directive_wrap *wrap; 364 365 level2 = HAMT_search(object->directives, parser); 366 if (!level2) 367 return 1; 368 369 wrap = HAMT_search(level2, name); 370 if (!wrap) 371 return 1; 372 373 yasm_call_directive(wrap->directive, object, valparams, objext_valparams, 374 line); 375 return 0; 376 } 377 378 void 379 yasm_object_set_source_fn(yasm_object *object, const char *src_filename) 380 { 381 yasm_xfree(object->src_filename); 382 object->src_filename = yasm__xstrdup(src_filename); 383 } 384 385 void 386 yasm_object_set_global_prefix(yasm_object *object, const char *prefix) 387 { 388 yasm_xfree(object->global_prefix); 389 object->global_prefix = yasm__xstrdup(prefix); 390 } 391 392 void 393 yasm_object_set_global_suffix(yasm_object *object, const char *suffix) 394 { 395 yasm_xfree(object->global_suffix); 396 object->global_suffix = yasm__xstrdup(suffix); 397 } 398 399 int 400 yasm_section_is_code(yasm_section *sect) 401 { 402 return sect->code; 403 } 404 405 unsigned long 406 yasm_section_get_opt_flags(const yasm_section *sect) 407 { 408 return sect->opt_flags; 409 } 410 411 void 412 yasm_section_set_opt_flags(yasm_section *sect, unsigned long opt_flags) 413 { 414 sect->opt_flags = opt_flags; 415 } 416 417 int 418 yasm_section_is_default(const yasm_section *sect) 419 { 420 return sect->def; 421 } 422 423 void 424 yasm_section_set_default(yasm_section *sect, int def) 425 { 426 sect->def = def; 427 } 428 429 yasm_object * 430 yasm_section_get_object(const yasm_section *sect) 431 { 432 return sect->object; 433 } 434 435 void * 436 yasm_section_get_data(yasm_section *sect, 437 const yasm_assoc_data_callback *callback) 438 { 439 return yasm__assoc_data_get(sect->assoc_data, callback); 440 } 441 442 void 443 yasm_section_add_data(yasm_section *sect, 444 const yasm_assoc_data_callback *callback, void *data) 445 { 446 sect->assoc_data = yasm__assoc_data_add(sect->assoc_data, callback, data); 447 } 448 449 void 450 yasm_object_destroy(yasm_object *object) 451 { 452 yasm_section *cur, *next; 453 454 /* Delete object format, debug format, and arch. This can be called 455 * due to an error in yasm_object_create(), so look out for NULLs. 456 */ 457 if (object->objfmt) 458 yasm_objfmt_destroy(object->objfmt); 459 if (object->dbgfmt) 460 yasm_dbgfmt_destroy(object->dbgfmt); 461 462 /* Delete sections */ 463 cur = STAILQ_FIRST(&object->sections); 464 while (cur) { 465 next = STAILQ_NEXT(cur, link); 466 yasm_section_destroy(cur); 467 cur = next; 468 } 469 470 /* Delete directives HAMT */ 471 HAMT_destroy(object->directives, directive_level1_delete); 472 473 /* Delete prefix/suffix */ 474 yasm_xfree(object->global_prefix); 475 yasm_xfree(object->global_suffix); 476 477 /* Delete associated filenames */ 478 yasm_xfree(object->src_filename); 479 yasm_xfree(object->obj_filename); 480 481 /* Delete symbol table */ 482 yasm_symtab_destroy(object->symtab); 483 484 /* Delete architecture */ 485 if (object->arch) 486 yasm_arch_destroy(object->arch); 487 488 yasm_xfree(object); 489 } 490 491 void 492 yasm_object_print(const yasm_object *object, FILE *f, int indent_level) 493 { 494 yasm_section *cur; 495 496 /* Print symbol table */ 497 fprintf(f, "%*sSymbol Table:\n", indent_level, ""); 498 yasm_symtab_print(object->symtab, f, indent_level+1); 499 500 /* Print sections and bytecodes */ 501 STAILQ_FOREACH(cur, &object->sections, link) { 502 fprintf(f, "%*sSection:\n", indent_level, ""); 503 yasm_section_print(cur, f, indent_level+1, 1); 504 } 505 } 506 507 void 508 yasm_object_finalize(yasm_object *object, yasm_errwarns *errwarns) 509 { 510 yasm_section *sect; 511 512 /* Iterate through sections */ 513 STAILQ_FOREACH(sect, &object->sections, link) { 514 yasm_bytecode *cur = STAILQ_FIRST(§->bcs); 515 yasm_bytecode *prev; 516 517 /* Skip our locally created empty bytecode first. */ 518 prev = cur; 519 cur = STAILQ_NEXT(cur, link); 520 521 /* Iterate through the remainder, if any. */ 522 while (cur) { 523 /* Finalize */ 524 yasm_bc_finalize(cur, prev); 525 yasm_errwarn_propagate(errwarns, cur->line); 526 prev = cur; 527 cur = STAILQ_NEXT(cur, link); 528 } 529 } 530 } 531 532 int 533 yasm_object_sections_traverse(yasm_object *object, /*@null@*/ void *d, 534 int (*func) (yasm_section *sect, 535 /*@null@*/ void *d)) 536 { 537 yasm_section *cur; 538 539 STAILQ_FOREACH(cur, &object->sections, link) { 540 int retval = func(cur, d); 541 if (retval != 0) 542 return retval; 543 } 544 return 0; 545 } 546 547 /*@-onlytrans@*/ 548 yasm_section * 549 yasm_object_find_general(yasm_object *object, const char *name) 550 { 551 yasm_section *cur; 552 553 STAILQ_FOREACH(cur, &object->sections, link) { 554 if (strcmp(cur->name, name) == 0) 555 return cur; 556 } 557 return NULL; 558 } 559 /*@=onlytrans@*/ 560 561 void 562 yasm_section_add_reloc(yasm_section *sect, yasm_reloc *reloc, 563 void (*destroy_func) (/*@only@*/ void *reloc)) 564 { 565 STAILQ_INSERT_TAIL(§->relocs, reloc, link); 566 if (!destroy_func) 567 yasm_internal_error(N_("NULL destroy function given to add_reloc")); 568 else if (sect->destroy_reloc && destroy_func != sect->destroy_reloc) 569 yasm_internal_error(N_("different destroy function given to add_reloc")); 570 sect->destroy_reloc = destroy_func; 571 } 572 573 /*@null@*/ yasm_reloc * 574 yasm_section_relocs_first(yasm_section *sect) 575 { 576 return STAILQ_FIRST(§->relocs); 577 } 578 579 #undef yasm_section_reloc_next 580 /*@null@*/ yasm_reloc * 581 yasm_section_reloc_next(yasm_reloc *reloc) 582 { 583 return STAILQ_NEXT(reloc, link); 584 } 585 586 void 587 yasm_reloc_get(yasm_reloc *reloc, yasm_intnum **addrp, yasm_symrec **symp) 588 { 589 *addrp = reloc->addr; 590 *symp = reloc->sym; 591 } 592 593 594 yasm_bytecode * 595 yasm_section_bcs_first(yasm_section *sect) 596 { 597 return STAILQ_FIRST(§->bcs); 598 } 599 600 yasm_bytecode * 601 yasm_section_bcs_last(yasm_section *sect) 602 { 603 return STAILQ_LAST(§->bcs, yasm_bytecode, link); 604 } 605 606 yasm_bytecode * 607 yasm_section_bcs_append(yasm_section *sect, yasm_bytecode *bc) 608 { 609 if (bc) { 610 if (bc->callback) { 611 bc->section = sect; /* record parent section */ 612 STAILQ_INSERT_TAIL(§->bcs, bc, link); 613 return bc; 614 } else 615 yasm_xfree(bc); 616 } 617 return (yasm_bytecode *)NULL; 618 } 619 620 int 621 yasm_section_bcs_traverse(yasm_section *sect, 622 /*@null@*/ yasm_errwarns *errwarns, 623 /*@null@*/ void *d, 624 int (*func) (yasm_bytecode *bc, /*@null@*/ void *d)) 625 { 626 yasm_bytecode *cur = STAILQ_FIRST(§->bcs); 627 628 /* Skip our locally created empty bytecode first. */ 629 cur = STAILQ_NEXT(cur, link); 630 631 /* Iterate through the remainder, if any. */ 632 while (cur) { 633 int retval = func(cur, d); 634 if (errwarns) 635 yasm_errwarn_propagate(errwarns, cur->line); 636 if (retval != 0) 637 return retval; 638 cur = STAILQ_NEXT(cur, link); 639 } 640 return 0; 641 } 642 643 const char * 644 yasm_section_get_name(const yasm_section *sect) 645 { 646 return sect->name; 647 } 648 649 void 650 yasm_section_set_align(yasm_section *sect, unsigned long align, 651 unsigned long line) 652 { 653 sect->align = align; 654 } 655 656 unsigned long 657 yasm_section_get_align(const yasm_section *sect) 658 { 659 return sect->align; 660 } 661 662 static void 663 yasm_section_destroy(yasm_section *sect) 664 { 665 yasm_bytecode *cur, *next; 666 yasm_reloc *r_cur, *r_next; 667 668 if (!sect) 669 return; 670 671 yasm_xfree(sect->name); 672 yasm__assoc_data_destroy(sect->assoc_data); 673 674 /* Delete bytecodes */ 675 cur = STAILQ_FIRST(§->bcs); 676 while (cur) { 677 next = STAILQ_NEXT(cur, link); 678 yasm_bc_destroy(cur); 679 cur = next; 680 } 681 682 /* Delete relocations */ 683 r_cur = STAILQ_FIRST(§->relocs); 684 while (r_cur) { 685 r_next = STAILQ_NEXT(r_cur, link); 686 yasm_intnum_destroy(r_cur->addr); 687 sect->destroy_reloc(r_cur); 688 r_cur = r_next; 689 } 690 691 yasm_xfree(sect); 692 } 693 694 void 695 yasm_section_print(const yasm_section *sect, FILE *f, int indent_level, 696 int print_bcs) 697 { 698 if (!sect) { 699 fprintf(f, "%*s(none)\n", indent_level, ""); 700 return; 701 } 702 703 fprintf(f, "%*sname=%s\n", indent_level, "", sect->name); 704 705 if (sect->assoc_data) { 706 fprintf(f, "%*sAssociated data:\n", indent_level, ""); 707 yasm__assoc_data_print(sect->assoc_data, f, indent_level+1); 708 } 709 710 if (print_bcs) { 711 yasm_bytecode *cur; 712 713 fprintf(f, "%*sBytecodes:\n", indent_level, ""); 714 715 STAILQ_FOREACH(cur, §->bcs, link) { 716 fprintf(f, "%*sNext Bytecode:\n", indent_level+1, ""); 717 yasm_bc_print(cur, f, indent_level+2); 718 } 719 } 720 } 721 722 /* 723 * Robertson (1977) optimizer 724 * Based (somewhat loosely) on the algorithm given in: 725 * MRC Technical Summary Report # 1779 726 * CODE GENERATION FOR SHORT/LONG ADDRESS MACHINES 727 * Edward L. Robertson 728 * Mathematics Research Center 729 * University of Wisconsin-Madison 730 * 610 Walnut Street 731 * Madison, Wisconsin 53706 732 * August 1977 733 * 734 * Key components of algorithm: 735 * - start assuming all short forms 736 * - build spans for short->long transition dependencies 737 * - if a long form is needed, walk the dependencies and update 738 * Major differences from Robertson's algorithm: 739 * - detection of cycles 740 * - any difference of two locations is allowed 741 * - handling of alignment/org gaps (offset setting) 742 * - handling of multiples 743 * 744 * Data structures: 745 * - Interval tree to store spans and associated data 746 * - Queues QA and QB 747 * 748 * Each span keeps track of: 749 * - Associated bytecode (bytecode that depends on the span length) 750 * - Active/inactive state (starts out active) 751 * - Sign (negative/positive; negative being "backwards" in address) 752 * - Current length in bytes 753 * - New length in bytes 754 * - Negative/Positive thresholds 755 * - Span ID (unique within each bytecode) 756 * 757 * How org and align and any other offset-based bytecodes are handled: 758 * 759 * Some portions are critical values that must not depend on any bytecode 760 * offset (either relative or absolute). 761 * 762 * All offset-setters (ORG and ALIGN) are put into a linked list in section 763 * order (e.g. increasing offset order). Each span keeps track of the next 764 * offset-setter following the span's associated bytecode. 765 * 766 * When a bytecode is expanded, the next offset-setter is examined. The 767 * offset-setter may be able to absorb the expansion (e.g. any offset 768 * following it would not change), or it may have to move forward (in the 769 * case of align) or error (in the case of org). If it has to move forward, 770 * following offset-setters must also be examined for absorption or moving 771 * forward. In either case, the ongoing offset is updated as well as the 772 * lengths of any spans dependent on the offset-setter. 773 * 774 * Alignment/ORG value is critical value. 775 * Cannot be combined with TIMES. 776 * 777 * How times is handled: 778 * 779 * TIMES: Handled separately from bytecode "raw" size. If not span-dependent, 780 * trivial (just multiplied in at any bytecode size increase). Span 781 * dependent times update on any change (span ID 0). If the resultant 782 * next bytecode offset would be less than the old next bytecode offset, 783 * error. Otherwise increase offset and update dependent spans. 784 * 785 * To reduce interval tree size, a first expansion pass is performed 786 * before the spans are added to the tree. 787 * 788 * Basic algorithm outline: 789 * 790 * 1. Initialization: 791 * a. Number bytecodes sequentially (via bc_index) and calculate offsets 792 * of all bytecodes assuming minimum length, building a list of all 793 * dependent spans as we go. 794 * "minimum" here means absolute minimum: 795 * - align/org (offset-based) bumps offset as normal 796 * - times values (with span-dependent values) assumed to be 0 797 * b. Iterate over spans. Set span length based on bytecode offsets 798 * determined in 1a. If span is "certainly" long because the span 799 * is an absolute reference to another section (or external) or the 800 * distance calculated based on the minimum length is greater than the 801 * span's threshold, expand the span's bytecode, and if no further 802 * expansion can result, mark span as inactive. 803 * c. Iterate over bytecodes to update all bytecode offsets based on new 804 * (expanded) lengths calculated in 1b. 805 * d. Iterate over active spans. Add span to interval tree. Update span's 806 * length based on new bytecode offsets determined in 1c. If span's 807 * length exceeds long threshold, add that span to Q. 808 * 2. Main loop: 809 * While Q not empty: 810 * Expand BC dependent on span at head of Q (and remove span from Q). 811 * Update span: 812 * If BC no longer dependent on span, mark span as inactive. 813 * If BC has new thresholds for span, update span. 814 * If BC increased in size, for each active span that contains BC: 815 * Increase span length by difference between short and long BC length. 816 * If span exceeds long threshold (or is flagged to recalculate on any 817 * change), add it to tail of Q. 818 * 3. Final pass over bytecodes to generate final offsets. 819 */ 820 821 typedef struct yasm_span yasm_span; 822 823 typedef struct yasm_offset_setter { 824 /* Linked list in section order (e.g. offset order) */ 825 /*@reldef@*/ STAILQ_ENTRY(yasm_offset_setter) link; 826 827 /*@dependent@*/ yasm_bytecode *bc; 828 829 unsigned long cur_val, new_val; 830 unsigned long thres; 831 } yasm_offset_setter; 832 833 typedef struct yasm_span_term { 834 yasm_bytecode *precbc, *precbc2; 835 yasm_span *span; /* span this term is a member of */ 836 long cur_val, new_val; 837 unsigned int subst; 838 } yasm_span_term; 839 840 struct yasm_span { 841 /*@reldef@*/ TAILQ_ENTRY(yasm_span) link; /* for allocation tracking */ 842 /*@reldef@*/ STAILQ_ENTRY(yasm_span) linkq; /* for Q */ 843 844 /*@dependent@*/ yasm_bytecode *bc; 845 846 yasm_value depval; 847 848 /* span term for relative portion of value */ 849 yasm_span_term *rel_term; 850 /* span terms in absolute portion of value */ 851 yasm_span_term *terms; 852 yasm_expr__item *items; 853 unsigned int num_terms; 854 855 long cur_val; 856 long new_val; 857 858 long neg_thres; 859 long pos_thres; 860 861 int id; 862 863 int active; 864 865 /* NULL-terminated array of spans that led to this span. Used only for 866 * checking for circular references (cycles) with id=0 spans. 867 */ 868 yasm_span **backtrace; 869 int backtrace_size; 870 871 /* First offset setter following this span's bytecode */ 872 yasm_offset_setter *os; 873 }; 874 875 typedef struct optimize_data { 876 /*@reldef@*/ TAILQ_HEAD(yasm_span_head, yasm_span) spans; 877 /*@reldef@*/ STAILQ_HEAD(yasm_span_shead, yasm_span) QA, QB; 878 /*@only@*/ IntervalTree *itree; 879 /*@reldef@*/ STAILQ_HEAD(offset_setters_head, yasm_offset_setter) 880 offset_setters; 881 long len_diff; /* used only for optimize_term_expand */ 882 yasm_span *span; /* used only for check_cycle */ 883 yasm_offset_setter *os; 884 } optimize_data; 885 886 static yasm_span * 887 create_span(yasm_bytecode *bc, int id, /*@null@*/ const yasm_value *value, 888 long neg_thres, long pos_thres, yasm_offset_setter *os) 889 { 890 yasm_span *span = yasm_xmalloc(sizeof(yasm_span)); 891 892 span->bc = bc; 893 if (value) 894 yasm_value_init_copy(&span->depval, value); 895 else 896 yasm_value_initialize(&span->depval, NULL, 0); 897 span->rel_term = NULL; 898 span->terms = NULL; 899 span->items = NULL; 900 span->num_terms = 0; 901 span->cur_val = 0; 902 span->new_val = 0; 903 span->neg_thres = neg_thres; 904 span->pos_thres = pos_thres; 905 span->id = id; 906 span->active = 1; 907 span->backtrace = NULL; 908 span->backtrace_size = 0; 909 span->os = os; 910 911 return span; 912 } 913 914 static void 915 optimize_add_span(void *add_span_data, yasm_bytecode *bc, int id, 916 const yasm_value *value, long neg_thres, long pos_thres) 917 { 918 optimize_data *optd = (optimize_data *)add_span_data; 919 yasm_span *span; 920 span = create_span(bc, id, value, neg_thres, pos_thres, optd->os); 921 TAILQ_INSERT_TAIL(&optd->spans, span, link); 922 } 923 924 static void 925 add_span_term(unsigned int subst, yasm_bytecode *precbc, 926 yasm_bytecode *precbc2, void *d) 927 { 928 yasm_span *span = d; 929 yasm_intnum *intn; 930 931 if (subst >= span->num_terms) { 932 /* Linear expansion since total number is essentially always small */ 933 span->num_terms = subst+1; 934 span->terms = yasm_xrealloc(span->terms, 935 span->num_terms*sizeof(yasm_span_term)); 936 } 937 span->terms[subst].precbc = precbc; 938 span->terms[subst].precbc2 = precbc2; 939 span->terms[subst].span = span; 940 span->terms[subst].subst = subst; 941 942 intn = yasm_calc_bc_dist(precbc, precbc2); 943 if (!intn) 944 yasm_internal_error(N_("could not calculate bc distance")); 945 span->terms[subst].cur_val = 0; 946 span->terms[subst].new_val = yasm_intnum_get_int(intn); 947 yasm_intnum_destroy(intn); 948 } 949 950 static void 951 span_create_terms(yasm_span *span) 952 { 953 unsigned int i; 954 955 /* Split out sym-sym terms in absolute portion of dependent value */ 956 if (span->depval.abs) { 957 span->num_terms = yasm_expr__bc_dist_subst(&span->depval.abs, span, 958 add_span_term); 959 if (span->num_terms > 0) { 960 span->items = yasm_xmalloc(span->num_terms*sizeof(yasm_expr__item)); 961 for (i=0; i<span->num_terms; i++) { 962 /* Create items with dummy value */ 963 span->items[i].type = YASM_EXPR_INT; 964 span->items[i].data.intn = yasm_intnum_create_int(0); 965 966 /* Check for circular references */ 967 if (span->id <= 0 && 968 ((span->bc->bc_index > span->terms[i].precbc->bc_index && 969 span->bc->bc_index <= span->terms[i].precbc2->bc_index) || 970 (span->bc->bc_index > span->terms[i].precbc2->bc_index && 971 span->bc->bc_index <= span->terms[i].precbc->bc_index))) 972 yasm_error_set(YASM_ERROR_VALUE, 973 N_("circular reference detected")); 974 } 975 } 976 } 977 978 /* Create term for relative portion of dependent value */ 979 if (span->depval.rel) { 980 yasm_bytecode *rel_precbc; 981 int sym_local; 982 983 sym_local = yasm_symrec_get_label(span->depval.rel, &rel_precbc); 984 if (span->depval.wrt || span->depval.seg_of || span->depval.section_rel 985 || !sym_local) 986 return; /* we can't handle SEG, WRT, or external symbols */ 987 if (rel_precbc->section != span->bc->section) 988 return; /* not in this section */ 989 if (!span->depval.curpos_rel) 990 return; /* not PC-relative */ 991 992 span->rel_term = yasm_xmalloc(sizeof(yasm_span_term)); 993 span->rel_term->precbc = NULL; 994 span->rel_term->precbc2 = rel_precbc; 995 span->rel_term->span = span; 996 span->rel_term->subst = ~0U; 997 998 span->rel_term->cur_val = 0; 999 span->rel_term->new_val = yasm_bc_next_offset(rel_precbc) - 1000 span->bc->offset; 1001 } 1002 } 1003 1004 /* Recalculate span value based on current span replacement values. 1005 * Returns 1 if span needs expansion (e.g. exceeded thresholds). 1006 */ 1007 static int 1008 recalc_normal_span(yasm_span *span) 1009 { 1010 span->new_val = 0; 1011 1012 if (span->depval.abs) { 1013 yasm_expr *abs_copy = yasm_expr_copy(span->depval.abs); 1014 /*@null@*/ /*@dependent@*/ yasm_intnum *num; 1015 1016 /* Update sym-sym terms and substitute back into expr */ 1017 unsigned int i; 1018 for (i=0; i<span->num_terms; i++) 1019 yasm_intnum_set_int(span->items[i].data.intn, 1020 span->terms[i].new_val); 1021 yasm_expr__subst(abs_copy, span->num_terms, span->items); 1022 num = yasm_expr_get_intnum(&abs_copy, 0); 1023 if (num) 1024 span->new_val = yasm_intnum_get_int(num); 1025 else 1026 span->new_val = LONG_MAX; /* too complex; force to longest form */ 1027 yasm_expr_destroy(abs_copy); 1028 } 1029 1030 if (span->rel_term) { 1031 if (span->new_val != LONG_MAX && span->rel_term->new_val != LONG_MAX) 1032 span->new_val += span->rel_term->new_val >> span->depval.rshift; 1033 else 1034 span->new_val = LONG_MAX; /* too complex; force to longest form */ 1035 } else if (span->depval.rel) 1036 span->new_val = LONG_MAX; /* too complex; force to longest form */ 1037 1038 if (span->new_val == LONG_MAX) 1039 span->active = 0; 1040 1041 /* If id<=0, flag update on any change */ 1042 if (span->id <= 0) 1043 return (span->new_val != span->cur_val); 1044 1045 return (span->new_val < span->neg_thres 1046 || span->new_val > span->pos_thres); 1047 } 1048 1049 /* Updates all bytecode offsets. For offset-based bytecodes, calls expand 1050 * to determine new length. 1051 */ 1052 static int 1053 update_all_bc_offsets(yasm_object *object, yasm_errwarns *errwarns) 1054 { 1055 yasm_section *sect; 1056 int saw_error = 0; 1057 1058 STAILQ_FOREACH(sect, &object->sections, link) { 1059 unsigned long offset = 0; 1060 1061 yasm_bytecode *bc = STAILQ_FIRST(§->bcs); 1062 yasm_bytecode *prevbc; 1063 1064 /* Skip our locally created empty bytecode first. */ 1065 prevbc = bc; 1066 bc = STAILQ_NEXT(bc, link); 1067 1068 /* Iterate through the remainder, if any. */ 1069 while (bc) { 1070 if (bc->callback->special == YASM_BC_SPECIAL_OFFSET) { 1071 /* Recalculate/adjust len of offset-based bytecodes here */ 1072 long neg_thres = 0; 1073 long pos_thres = (long)yasm_bc_next_offset(bc); 1074 int retval = yasm_bc_expand(bc, 1, 0, 1075 (long)yasm_bc_next_offset(prevbc), 1076 &neg_thres, &pos_thres); 1077 yasm_errwarn_propagate(errwarns, bc->line); 1078 if (retval < 0) 1079 saw_error = 1; 1080 } 1081 bc->offset = offset; 1082 offset += bc->len*bc->mult_int; 1083 prevbc = bc; 1084 bc = STAILQ_NEXT(bc, link); 1085 } 1086 } 1087 return saw_error; 1088 } 1089 1090 static void 1091 span_destroy(/*@only@*/ yasm_span *span) 1092 { 1093 unsigned int i; 1094 1095 yasm_value_delete(&span->depval); 1096 if (span->rel_term) 1097 yasm_xfree(span->rel_term); 1098 if (span->terms) 1099 yasm_xfree(span->terms); 1100 if (span->items) { 1101 for (i=0; i<span->num_terms; i++) 1102 yasm_intnum_destroy(span->items[i].data.intn); 1103 yasm_xfree(span->items); 1104 } 1105 if (span->backtrace) 1106 yasm_xfree(span->backtrace); 1107 yasm_xfree(span); 1108 } 1109 1110 static void 1111 optimize_cleanup(optimize_data *optd) 1112 { 1113 yasm_span *s1, *s2; 1114 yasm_offset_setter *os1, *os2; 1115 1116 IT_destroy(optd->itree); 1117 1118 s1 = TAILQ_FIRST(&optd->spans); 1119 while (s1) { 1120 s2 = TAILQ_NEXT(s1, link); 1121 span_destroy(s1); 1122 s1 = s2; 1123 } 1124 1125 os1 = STAILQ_FIRST(&optd->offset_setters); 1126 while (os1) { 1127 os2 = STAILQ_NEXT(os1, link); 1128 yasm_xfree(os1); 1129 os1 = os2; 1130 } 1131 } 1132 1133 static void 1134 optimize_itree_add(IntervalTree *itree, yasm_span *span, yasm_span_term *term) 1135 { 1136 long precbc_index, precbc2_index; 1137 unsigned long low, high; 1138 1139 /* Update term length */ 1140 if (term->precbc) 1141 precbc_index = term->precbc->bc_index; 1142 else 1143 precbc_index = span->bc->bc_index-1; 1144 1145 if (term->precbc2) 1146 precbc2_index = term->precbc2->bc_index; 1147 else 1148 precbc2_index = span->bc->bc_index-1; 1149 1150 if (precbc_index < precbc2_index) { 1151 low = precbc_index+1; 1152 high = precbc2_index; 1153 } else if (precbc_index > precbc2_index) { 1154 low = precbc2_index+1; 1155 high = precbc_index; 1156 } else 1157 return; /* difference is same bc - always 0! */ 1158 1159 IT_insert(itree, (long)low, (long)high, term); 1160 } 1161 1162 static void 1163 check_cycle(IntervalTreeNode *node, void *d) 1164 { 1165 optimize_data *optd = d; 1166 yasm_span_term *term = node->data; 1167 yasm_span *depspan = term->span; 1168 int i; 1169 int depspan_bt_alloc; 1170 1171 /* Only check for cycles in id=0 spans */ 1172 if (depspan->id > 0) 1173 return; 1174 1175 /* Check for a circular reference by looking to see if this dependent 1176 * span is in our backtrace. 1177 */ 1178 if (optd->span->backtrace) { 1179 for (i=0; i<optd->span->backtrace_size; i++) { 1180 if (optd->span->backtrace[i] == depspan) 1181 yasm_error_set(YASM_ERROR_VALUE, 1182 N_("circular reference detected")); 1183 } 1184 } 1185 1186 /* Add our complete backtrace and ourselves to backtrace of dependent 1187 * span. 1188 */ 1189 if (!depspan->backtrace) { 1190 depspan->backtrace = yasm_xmalloc((optd->span->backtrace_size+1)* 1191 sizeof(yasm_span *)); 1192 if (optd->span->backtrace_size > 0) 1193 memcpy(depspan->backtrace, optd->span->backtrace, 1194 optd->span->backtrace_size*sizeof(yasm_span *)); 1195 depspan->backtrace[optd->span->backtrace_size] = optd->span; 1196 depspan->backtrace_size = optd->span->backtrace_size+1; 1197 return; 1198 } 1199 1200 /* Add our complete backtrace, checking for duplicates */ 1201 depspan_bt_alloc = depspan->backtrace_size; 1202 for (i=0; i<optd->span->backtrace_size; i++) { 1203 int present = 0; 1204 int j; 1205 for (j=0; j<depspan->backtrace_size; j++) { 1206 if (optd->span->backtrace[i] == optd->span->backtrace[j]) { 1207 present = 1; 1208 break; 1209 } 1210 } 1211 if (present) 1212 continue; 1213 /* Not already in array; add it. */ 1214 if (depspan->backtrace_size >= depspan_bt_alloc) 1215 { 1216 depspan_bt_alloc *= 2; 1217 depspan->backtrace = 1218 yasm_xrealloc(depspan->backtrace, 1219 depspan_bt_alloc*sizeof(yasm_span *)); 1220 } 1221 depspan->backtrace[depspan->backtrace_size] = optd->span->backtrace[i]; 1222 depspan->backtrace_size++; 1223 } 1224 1225 /* Add ourselves. */ 1226 if (depspan->backtrace_size >= depspan_bt_alloc) 1227 { 1228 depspan_bt_alloc++; 1229 depspan->backtrace = 1230 yasm_xrealloc(depspan->backtrace, 1231 depspan_bt_alloc*sizeof(yasm_span *)); 1232 } 1233 depspan->backtrace[depspan->backtrace_size] = optd->span; 1234 depspan->backtrace_size++; 1235 } 1236 1237 static void 1238 optimize_term_expand(IntervalTreeNode *node, void *d) 1239 { 1240 optimize_data *optd = d; 1241 yasm_span_term *term = node->data; 1242 yasm_span *span = term->span; 1243 long len_diff = optd->len_diff; 1244 long precbc_index, precbc2_index; 1245 1246 /* Don't expand inactive spans */ 1247 if (!span->active) 1248 return; 1249 1250 /* Update term length */ 1251 if (term->precbc) 1252 precbc_index = term->precbc->bc_index; 1253 else 1254 precbc_index = span->bc->bc_index-1; 1255 1256 if (term->precbc2) 1257 precbc2_index = term->precbc2->bc_index; 1258 else 1259 precbc2_index = span->bc->bc_index-1; 1260 1261 if (precbc_index < precbc2_index) 1262 term->new_val += len_diff; 1263 else 1264 term->new_val -= len_diff; 1265 1266 /* If already on Q, don't re-add */ 1267 if (span->active == 2) 1268 return; 1269 1270 /* Update term and check against thresholds */ 1271 if (!recalc_normal_span(span)) 1272 return; /* didn't exceed thresholds, we're done */ 1273 1274 /* Exceeded thresholds, need to add to Q for expansion */ 1275 if (span->id <= 0) 1276 STAILQ_INSERT_TAIL(&optd->QA, span, linkq); 1277 else 1278 STAILQ_INSERT_TAIL(&optd->QB, span, linkq); 1279 span->active = 2; /* Mark as being in Q */ 1280 } 1281 1282 void 1283 yasm_object_optimize(yasm_object *object, yasm_errwarns *errwarns) 1284 { 1285 yasm_section *sect; 1286 unsigned long bc_index = 0; 1287 int saw_error = 0; 1288 optimize_data optd; 1289 yasm_span *span, *span_temp; 1290 yasm_offset_setter *os; 1291 int retval; 1292 unsigned int i; 1293 1294 TAILQ_INIT(&optd.spans); 1295 STAILQ_INIT(&optd.offset_setters); 1296 optd.itree = IT_create(); 1297 1298 /* Create an placeholder offset setter for spans to point to; this will 1299 * get updated if/when we actually run into one. 1300 */ 1301 os = yasm_xmalloc(sizeof(yasm_offset_setter)); 1302 os->bc = NULL; 1303 os->cur_val = 0; 1304 os->new_val = 0; 1305 os->thres = 0; 1306 STAILQ_INSERT_TAIL(&optd.offset_setters, os, link); 1307 optd.os = os; 1308 1309 /* Step 1a */ 1310 STAILQ_FOREACH(sect, &object->sections, link) { 1311 unsigned long offset = 0; 1312 1313 yasm_bytecode *bc = STAILQ_FIRST(§->bcs); 1314 yasm_bytecode *prevbc; 1315 1316 bc->bc_index = bc_index++; 1317 1318 /* Skip our locally created empty bytecode first. */ 1319 prevbc = bc; 1320 bc = STAILQ_NEXT(bc, link); 1321 1322 /* Iterate through the remainder, if any. */ 1323 while (bc) { 1324 bc->bc_index = bc_index++; 1325 bc->offset = offset; 1326 1327 retval = yasm_bc_calc_len(bc, optimize_add_span, &optd); 1328 yasm_errwarn_propagate(errwarns, bc->line); 1329 if (retval) 1330 saw_error = 1; 1331 else { 1332 if (bc->callback->special == YASM_BC_SPECIAL_OFFSET) { 1333 /* Remember it as offset setter */ 1334 os->bc = bc; 1335 os->thres = yasm_bc_next_offset(bc); 1336 1337 /* Create new placeholder */ 1338 os = yasm_xmalloc(sizeof(yasm_offset_setter)); 1339 os->bc = NULL; 1340 os->cur_val = 0; 1341 os->new_val = 0; 1342 os->thres = 0; 1343 STAILQ_INSERT_TAIL(&optd.offset_setters, os, link); 1344 optd.os = os; 1345 1346 if (bc->multiple) { 1347 yasm_error_set(YASM_ERROR_VALUE, 1348 N_("cannot combine multiples and setting assembly position")); 1349 yasm_errwarn_propagate(errwarns, bc->line); 1350 saw_error = 1; 1351 } 1352 } 1353 1354 offset += bc->len*bc->mult_int; 1355 } 1356 1357 prevbc = bc; 1358 bc = STAILQ_NEXT(bc, link); 1359 } 1360 } 1361 1362 if (saw_error) { 1363 optimize_cleanup(&optd); 1364 return; 1365 } 1366 1367 /* Step 1b */ 1368 TAILQ_FOREACH_SAFE(span, &optd.spans, link, span_temp) { 1369 span_create_terms(span); 1370 if (yasm_error_occurred()) { 1371 yasm_errwarn_propagate(errwarns, span->bc->line); 1372 saw_error = 1; 1373 } else if (recalc_normal_span(span)) { 1374 retval = yasm_bc_expand(span->bc, span->id, span->cur_val, 1375 span->new_val, &span->neg_thres, 1376 &span->pos_thres); 1377 yasm_errwarn_propagate(errwarns, span->bc->line); 1378 if (retval < 0) 1379 saw_error = 1; 1380 else if (retval > 0) { 1381 if (!span->active) { 1382 yasm_error_set(YASM_ERROR_VALUE, 1383 N_("secondary expansion of an external/complex value")); 1384 yasm_errwarn_propagate(errwarns, span->bc->line); 1385 saw_error = 1; 1386 } 1387 } else { 1388 TAILQ_REMOVE(&optd.spans, span, link); 1389 span_destroy(span); 1390 continue; 1391 } 1392 } 1393 span->cur_val = span->new_val; 1394 } 1395 1396 if (saw_error) { 1397 optimize_cleanup(&optd); 1398 return; 1399 } 1400 1401 /* Step 1c */ 1402 if (update_all_bc_offsets(object, errwarns)) { 1403 optimize_cleanup(&optd); 1404 return; 1405 } 1406 1407 /* Step 1d */ 1408 STAILQ_INIT(&optd.QB); 1409 TAILQ_FOREACH(span, &optd.spans, link) { 1410 yasm_intnum *intn; 1411 1412 /* Update span terms based on new bc offsets */ 1413 for (i=0; i<span->num_terms; i++) { 1414 intn = yasm_calc_bc_dist(span->terms[i].precbc, 1415 span->terms[i].precbc2); 1416 if (!intn) 1417 yasm_internal_error(N_("could not calculate bc distance")); 1418 span->terms[i].cur_val = span->terms[i].new_val; 1419 span->terms[i].new_val = yasm_intnum_get_int(intn); 1420 yasm_intnum_destroy(intn); 1421 } 1422 if (span->rel_term) { 1423 span->rel_term->cur_val = span->rel_term->new_val; 1424 if (span->rel_term->precbc2) 1425 span->rel_term->new_val = 1426 yasm_bc_next_offset(span->rel_term->precbc2) - 1427 span->bc->offset; 1428 else 1429 span->rel_term->new_val = span->bc->offset - 1430 yasm_bc_next_offset(span->rel_term->precbc); 1431 } 1432 1433 if (recalc_normal_span(span)) { 1434 /* Exceeded threshold, add span to QB */ 1435 STAILQ_INSERT_TAIL(&optd.QB, span, linkq); 1436 span->active = 2; 1437 } 1438 } 1439 1440 /* Do we need step 2? If not, go ahead and exit. */ 1441 if (STAILQ_EMPTY(&optd.QB)) { 1442 optimize_cleanup(&optd); 1443 return; 1444 } 1445 1446 /* Update offset-setters values */ 1447 STAILQ_FOREACH(os, &optd.offset_setters, link) { 1448 if (!os->bc) 1449 continue; 1450 os->thres = yasm_bc_next_offset(os->bc); 1451 os->new_val = os->bc->offset; 1452 os->cur_val = os->new_val; 1453 } 1454 1455 /* Build up interval tree */ 1456 TAILQ_FOREACH(span, &optd.spans, link) { 1457 for (i=0; i<span->num_terms; i++) 1458 optimize_itree_add(optd.itree, span, &span->terms[i]); 1459 if (span->rel_term) 1460 optimize_itree_add(optd.itree, span, span->rel_term); 1461 } 1462 1463 /* Look for cycles in times expansion (span.id==0) */ 1464 TAILQ_FOREACH(span, &optd.spans, link) { 1465 if (span->id > 0) 1466 continue; 1467 optd.span = span; 1468 IT_enumerate(optd.itree, (long)span->bc->bc_index, 1469 (long)span->bc->bc_index, &optd, check_cycle); 1470 if (yasm_error_occurred()) { 1471 yasm_errwarn_propagate(errwarns, span->bc->line); 1472 saw_error = 1; 1473 } 1474 } 1475 1476 if (saw_error) { 1477 optimize_cleanup(&optd); 1478 return; 1479 } 1480 1481 /* Step 2 */ 1482 STAILQ_INIT(&optd.QA); 1483 while (!STAILQ_EMPTY(&optd.QA) || !(STAILQ_EMPTY(&optd.QB))) { 1484 unsigned long orig_len; 1485 long offset_diff; 1486 1487 /* QA is for TIMES, update those first, then update non-TIMES. 1488 * This is so that TIMES can absorb increases before we look at 1489 * expanding non-TIMES BCs. 1490 */ 1491 if (!STAILQ_EMPTY(&optd.QA)) { 1492 span = STAILQ_FIRST(&optd.QA); 1493 STAILQ_REMOVE_HEAD(&optd.QA, linkq); 1494 } else { 1495 span = STAILQ_FIRST(&optd.QB); 1496 STAILQ_REMOVE_HEAD(&optd.QB, linkq); 1497 } 1498 1499 if (!span->active) 1500 continue; 1501 span->active = 1; /* no longer in Q */ 1502 1503 /* Make sure we ended up ultimately exceeding thresholds; due to 1504 * offset BCs we may have been placed on Q and then reduced in size 1505 * again. 1506 */ 1507 if (!recalc_normal_span(span)) 1508 continue; 1509 1510 orig_len = span->bc->len * span->bc->mult_int; 1511 1512 retval = yasm_bc_expand(span->bc, span->id, span->cur_val, 1513 span->new_val, &span->neg_thres, 1514 &span->pos_thres); 1515 yasm_errwarn_propagate(errwarns, span->bc->line); 1516 1517 if (retval < 0) { 1518 /* error */ 1519 saw_error = 1; 1520 continue; 1521 } else if (retval > 0) { 1522 /* another threshold, keep active */ 1523 for (i=0; i<span->num_terms; i++) 1524 span->terms[i].cur_val = span->terms[i].new_val; 1525 if (span->rel_term) 1526 span->rel_term->cur_val = span->rel_term->new_val; 1527 span->cur_val = span->new_val; 1528 } else 1529 span->active = 0; /* we're done with this span */ 1530 1531 optd.len_diff = span->bc->len * span->bc->mult_int - orig_len; 1532 if (optd.len_diff == 0) 1533 continue; /* didn't increase in size */ 1534 1535 /* Iterate over all spans dependent across the bc just expanded */ 1536 IT_enumerate(optd.itree, (long)span->bc->bc_index, 1537 (long)span->bc->bc_index, &optd, optimize_term_expand); 1538 1539 /* Iterate over offset-setters that follow the bc just expanded. 1540 * Stop iteration if: 1541 * - no more offset-setters in this section 1542 * - offset-setter didn't move its following offset 1543 */ 1544 os = span->os; 1545 offset_diff = optd.len_diff; 1546 while (os->bc && os->bc->section == span->bc->section 1547 && offset_diff != 0) { 1548 unsigned long old_next_offset = os->cur_val + os->bc->len; 1549 long neg_thres_temp; 1550 1551 if (offset_diff < 0 && (unsigned long)(-offset_diff) > os->new_val) 1552 yasm_internal_error(N_("org/align went to negative offset")); 1553 os->new_val += offset_diff; 1554 1555 orig_len = os->bc->len; 1556 retval = yasm_bc_expand(os->bc, 1, (long)os->cur_val, 1557 (long)os->new_val, &neg_thres_temp, 1558 (long *)&os->thres); 1559 yasm_errwarn_propagate(errwarns, os->bc->line); 1560 1561 offset_diff = os->new_val + os->bc->len - old_next_offset; 1562 optd.len_diff = os->bc->len - orig_len; 1563 if (optd.len_diff != 0) 1564 IT_enumerate(optd.itree, (long)os->bc->bc_index, 1565 (long)os->bc->bc_index, &optd, optimize_term_expand); 1566 1567 os->cur_val = os->new_val; 1568 os = STAILQ_NEXT(os, link); 1569 } 1570 } 1571 1572 if (saw_error) { 1573 optimize_cleanup(&optd); 1574 return; 1575 } 1576 1577 /* Step 3 */ 1578 update_all_bc_offsets(object, errwarns); 1579 optimize_cleanup(&optd); 1580 } 1581
