libyasm/section.c

   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(&sect->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(&sect->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(&sect->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(&sect->bcs);
 598 }
 599
 600 yasm_bytecode *
 601 yasm_section_bcs_last(yasm_section *sect)
 602 {
 603     return STAILQ_LAST(&sect->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(&sect->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(&sect->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(&sect->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(&sect->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, &sect->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(&sect->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(&sect->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 }