diff options
Diffstat (limited to 'libyasm/section.c')
| -rw-r--r-- | libyasm/section.c | 1580 |
1 files changed, 1580 insertions, 0 deletions
diff --git a/libyasm/section.c b/libyasm/section.c new file mode 100644 index 0000000..9242fb0 --- /dev/null +++ b/libyasm/section.c @@ -0,0 +1,1580 @@ +/* + * Section utility functions + * + * Copyright (C) 2001-2007 Peter Johnson + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND OTHER CONTRIBUTORS ``AS IS'' + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR OTHER CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "util.h" + +#include <limits.h> + +#include "libyasm-stdint.h" +#include "coretype.h" +#include "hamt.h" +#include "valparam.h" +#include "assocdat.h" + +#include "linemap.h" +#include "errwarn.h" +#include "intnum.h" +#include "expr.h" +#include "value.h" +#include "symrec.h" + +#include "bytecode.h" +#include "arch.h" +#include "section.h" + +#include "dbgfmt.h" +#include "objfmt.h" + +#include "inttree.h" + + +struct yasm_section { + /*@reldef@*/ STAILQ_ENTRY(yasm_section) link; + + /*@dependent@*/ yasm_object *object; /* Pointer to parent object */ + + /*@owned@*/ char *name; /* strdup()'ed name (given by user) */ + + /* associated data; NULL if none */ + /*@null@*/ /*@only@*/ yasm__assoc_data *assoc_data; + + unsigned long align; /* Section alignment */ + + unsigned long opt_flags; /* storage for optimizer flags */ + + int code; /* section contains code (instructions) */ + int res_only; /* allow only resb family of bytecodes? */ + int def; /* "default" section, e.g. not specified by + using section directive */ + + /* the bytecodes for the section's contents */ + /*@reldef@*/ STAILQ_HEAD(yasm_bytecodehead, yasm_bytecode) bcs; + + /* the relocations for the section */ + /*@reldef@*/ STAILQ_HEAD(yasm_relochead, yasm_reloc) relocs; + + void (*destroy_reloc) (/*@only@*/ void *reloc); +}; + +static void yasm_section_destroy(/*@only@*/ yasm_section *sect); + +/* Wrapper around directive for HAMT insertion */ +typedef struct yasm_directive_wrap { + const yasm_directive *directive; +} yasm_directive_wrap; + +/* + * Standard "builtin" object directives. + */ + +static void +dir_extern(yasm_object *object, yasm_valparamhead *valparams, + yasm_valparamhead *objext_valparams, unsigned long line) +{ + yasm_valparam *vp = yasm_vps_first(valparams); + yasm_symrec *sym; + sym = yasm_symtab_declare(object->symtab, yasm_vp_id(vp), YASM_SYM_EXTERN, + line); + if (objext_valparams) { + yasm_valparamhead *vps = yasm_vps_create(); + *vps = *objext_valparams; /* structure copy */ + yasm_vps_initialize(objext_valparams); /* don't double-free */ + yasm_symrec_set_objext_valparams(sym, vps); + } +} + +static void +dir_global(yasm_object *object, yasm_valparamhead *valparams, + yasm_valparamhead *objext_valparams, unsigned long line) +{ + yasm_valparam *vp = yasm_vps_first(valparams); + yasm_symrec *sym; + sym = yasm_symtab_declare(object->symtab, yasm_vp_id(vp), YASM_SYM_GLOBAL, + line); + if (objext_valparams) { + yasm_valparamhead *vps = yasm_vps_create(); + *vps = *objext_valparams; /* structure copy */ + yasm_vps_initialize(objext_valparams); /* don't double-free */ + yasm_symrec_set_objext_valparams(sym, vps); + } +} + +static void +dir_common(yasm_object *object, yasm_valparamhead *valparams, + yasm_valparamhead *objext_valparams, unsigned long line) +{ + yasm_valparam *vp = yasm_vps_first(valparams); + yasm_valparam *vp2 = yasm_vps_next(vp); + yasm_expr *size = yasm_vp_expr(vp2, object->symtab, line); + yasm_symrec *sym; + + if (!size) { + yasm_error_set(YASM_ERROR_SYNTAX, + N_("no size specified in %s declaration"), "COMMON"); + return; + } + sym = yasm_symtab_declare(object->symtab, yasm_vp_id(vp), YASM_SYM_COMMON, + line); + yasm_symrec_set_common_size(sym, size); + if (objext_valparams) { + yasm_valparamhead *vps = yasm_vps_create(); + *vps = *objext_valparams; /* structure copy */ + yasm_vps_initialize(objext_valparams); /* don't double-free */ + yasm_symrec_set_objext_valparams(sym, vps); + } +} + +static void +dir_section(yasm_object *object, yasm_valparamhead *valparams, + yasm_valparamhead *objext_valparams, unsigned long line) +{ + yasm_section *new_section = + yasm_objfmt_section_switch(object, valparams, objext_valparams, line); + if (new_section) + object->cur_section = new_section; + else + yasm_error_set(YASM_ERROR_SYNTAX, + N_("invalid argument to directive `%s'"), "SECTION"); +} + +static const yasm_directive object_directives[] = { + { ".extern", "gas", dir_extern, YASM_DIR_ID_REQUIRED }, + { ".global", "gas", dir_global, YASM_DIR_ID_REQUIRED }, + { ".globl", "gas", dir_global, YASM_DIR_ID_REQUIRED }, + { "extern", "nasm", dir_extern, YASM_DIR_ID_REQUIRED }, + { "global", "nasm", dir_global, YASM_DIR_ID_REQUIRED }, + { "common", "nasm", dir_common, YASM_DIR_ID_REQUIRED }, + { "section", "nasm", dir_section, YASM_DIR_ARG_REQUIRED }, + { "segment", "nasm", dir_section, YASM_DIR_ARG_REQUIRED }, + { NULL, NULL, NULL, 0 } +}; + +static void +directive_level2_delete(/*@only@*/ void *data) +{ + yasm_xfree(data); +} + +static void +directive_level1_delete(/*@only@*/ void *data) +{ + HAMT_destroy(data, directive_level2_delete); +} + +static void +directives_add(yasm_object *object, /*@null@*/ const yasm_directive *dir) +{ + if (!dir) + return; + + while (dir->name) { + HAMT *level2 = HAMT_search(object->directives, dir->parser); + int replace; + yasm_directive_wrap *wrap = yasm_xmalloc(sizeof(yasm_directive_wrap)); + + if (!level2) { + replace = 0; + level2 = HAMT_insert(object->directives, dir->parser, + HAMT_create(1, yasm_internal_error_), + &replace, directive_level1_delete); + } + replace = 0; + wrap->directive = dir; + HAMT_insert(level2, dir->name, wrap, &replace, + directive_level2_delete); + dir++; + } +} + +/*@-compdestroy@*/ +yasm_object * +yasm_object_create(const char *src_filename, const char *obj_filename, + /*@kept@*/ yasm_arch *arch, + const yasm_objfmt_module *objfmt_module, + const yasm_dbgfmt_module *dbgfmt_module) +{ + yasm_object *object = yasm_xmalloc(sizeof(yasm_object)); + int matched, i; + + object->src_filename = yasm__xstrdup(src_filename); + object->obj_filename = yasm__xstrdup(obj_filename); + + /* No prefix/suffix */ + object->global_prefix = yasm__xstrdup(""); + object->global_suffix = yasm__xstrdup(""); + + /* Create empty symbol table */ + object->symtab = yasm_symtab_create(); + + /* Initialize sections linked list */ + STAILQ_INIT(&object->sections); + + /* Create directives HAMT */ + object->directives = HAMT_create(1, yasm_internal_error_); + + /* Initialize the target architecture */ + object->arch = arch; + + /* Initialize things to NULL in case of error */ + object->dbgfmt = NULL; + + /* Initialize the object format */ + object->objfmt = yasm_objfmt_create(objfmt_module, object); + if (!object->objfmt) { + yasm_error_set(YASM_ERROR_GENERAL, + N_("object format `%s' does not support architecture `%s' machine `%s'"), + objfmt_module->keyword, ((yasm_arch_base *)arch)->module->keyword, + yasm_arch_get_machine(arch)); + goto error; + } + + /* Get a fresh copy of objfmt_module as it may have changed. */ + objfmt_module = ((yasm_objfmt_base *)object->objfmt)->module; + + /* Add an initial "default" section to object */ + object->cur_section = yasm_objfmt_add_default_section(object); + + /* Check to see if the requested debug format is in the allowed list + * for the active object format. + */ + matched = 0; + for (i=0; objfmt_module->dbgfmt_keywords[i]; i++) + if (yasm__strcasecmp(objfmt_module->dbgfmt_keywords[i], + dbgfmt_module->keyword) == 0) + matched = 1; + if (!matched) { + yasm_error_set(YASM_ERROR_GENERAL, + N_("`%s' is not a valid debug format for object format `%s'"), + dbgfmt_module->keyword, objfmt_module->keyword); + goto error; + } + + /* Initialize the debug format */ + object->dbgfmt = yasm_dbgfmt_create(dbgfmt_module, object); + if (!object->dbgfmt) { + yasm_error_set(YASM_ERROR_GENERAL, + N_("debug format `%s' does not work with object format `%s'"), + dbgfmt_module->keyword, objfmt_module->keyword); + goto error; + } + + /* Add directives to HAMT. Note ordering here determines priority. */ + directives_add(object, + ((yasm_objfmt_base *)object->objfmt)->module->directives); + directives_add(object, + ((yasm_dbgfmt_base *)object->dbgfmt)->module->directives); + directives_add(object, + ((yasm_arch_base *)object->arch)->module->directives); + directives_add(object, object_directives); + + return object; + +error: + yasm_object_destroy(object); + return NULL; +} +/*@=compdestroy@*/ + +/*@-onlytrans@*/ +yasm_section * +yasm_object_get_general(yasm_object *object, const char *name, + unsigned long align, int code, int res_only, + int *isnew, unsigned long line) +{ + yasm_section *s; + yasm_bytecode *bc; + + /* Search through current sections to see if we already have one with + * that name. + */ + STAILQ_FOREACH(s, &object->sections, link) { + if (strcmp(s->name, name) == 0) { + *isnew = 0; + return s; + } + } + + /* No: we have to allocate and create a new one. */ + + /* Okay, the name is valid; now allocate and initialize */ + s = yasm_xcalloc(1, sizeof(yasm_section)); + STAILQ_INSERT_TAIL(&object->sections, s, link); + + s->object = object; + s->name = yasm__xstrdup(name); + s->assoc_data = NULL; + s->align = align; + + /* Initialize bytecodes with one empty bytecode (acts as "prior" for first + * real bytecode in section. + */ + STAILQ_INIT(&s->bcs); + bc = yasm_bc_create_common(NULL, NULL, 0); + bc->section = s; + bc->offset = 0; + STAILQ_INSERT_TAIL(&s->bcs, bc, link); + + /* Initialize relocs */ + STAILQ_INIT(&s->relocs); + s->destroy_reloc = NULL; + + s->code = code; + s->res_only = res_only; + s->def = 0; + + /* Initialize object format specific data */ + yasm_objfmt_init_new_section(s, line); + + *isnew = 1; + return s; +} +/*@=onlytrans@*/ + +int +yasm_object_directive(yasm_object *object, const char *name, + const char *parser, yasm_valparamhead *valparams, + yasm_valparamhead *objext_valparams, + unsigned long line) +{ + HAMT *level2; + yasm_directive_wrap *wrap; + + level2 = HAMT_search(object->directives, parser); + if (!level2) + return 1; + + wrap = HAMT_search(level2, name); + if (!wrap) + return 1; + + yasm_call_directive(wrap->directive, object, valparams, objext_valparams, + line); + return 0; +} + +void +yasm_object_set_source_fn(yasm_object *object, const char *src_filename) +{ + yasm_xfree(object->src_filename); + object->src_filename = yasm__xstrdup(src_filename); +} + +void +yasm_object_set_global_prefix(yasm_object *object, const char *prefix) +{ + yasm_xfree(object->global_prefix); + object->global_prefix = yasm__xstrdup(prefix); +} + +void +yasm_object_set_global_suffix(yasm_object *object, const char *suffix) +{ + yasm_xfree(object->global_suffix); + object->global_suffix = yasm__xstrdup(suffix); +} + +int +yasm_section_is_code(yasm_section *sect) +{ + return sect->code; +} + +unsigned long +yasm_section_get_opt_flags(const yasm_section *sect) +{ + return sect->opt_flags; +} + +void +yasm_section_set_opt_flags(yasm_section *sect, unsigned long opt_flags) +{ + sect->opt_flags = opt_flags; +} + +int +yasm_section_is_default(const yasm_section *sect) +{ + return sect->def; +} + +void +yasm_section_set_default(yasm_section *sect, int def) +{ + sect->def = def; +} + +yasm_object * +yasm_section_get_object(const yasm_section *sect) +{ + return sect->object; +} + +void * +yasm_section_get_data(yasm_section *sect, + const yasm_assoc_data_callback *callback) +{ + return yasm__assoc_data_get(sect->assoc_data, callback); +} + +void +yasm_section_add_data(yasm_section *sect, + const yasm_assoc_data_callback *callback, void *data) +{ + sect->assoc_data = yasm__assoc_data_add(sect->assoc_data, callback, data); +} + +void +yasm_object_destroy(yasm_object *object) +{ + yasm_section *cur, *next; + + /* Delete object format, debug format, and arch. This can be called + * due to an error in yasm_object_create(), so look out for NULLs. + */ + if (object->objfmt) + yasm_objfmt_destroy(object->objfmt); + if (object->dbgfmt) + yasm_dbgfmt_destroy(object->dbgfmt); + + /* Delete sections */ + cur = STAILQ_FIRST(&object->sections); + while (cur) { + next = STAILQ_NEXT(cur, link); + yasm_section_destroy(cur); + cur = next; + } + + /* Delete directives HAMT */ + HAMT_destroy(object->directives, directive_level1_delete); + + /* Delete prefix/suffix */ + yasm_xfree(object->global_prefix); + yasm_xfree(object->global_suffix); + + /* Delete associated filenames */ + yasm_xfree(object->src_filename); + yasm_xfree(object->obj_filename); + + /* Delete symbol table */ + yasm_symtab_destroy(object->symtab); + + /* Delete architecture */ + if (object->arch) + yasm_arch_destroy(object->arch); + + yasm_xfree(object); +} + +void +yasm_object_print(const yasm_object *object, FILE *f, int indent_level) +{ + yasm_section *cur; + + /* Print symbol table */ + fprintf(f, "%*sSymbol Table:\n", indent_level, ""); + yasm_symtab_print(object->symtab, f, indent_level+1); + + /* Print sections and bytecodes */ + STAILQ_FOREACH(cur, &object->sections, link) { + fprintf(f, "%*sSection:\n", indent_level, ""); + yasm_section_print(cur, f, indent_level+1, 1); + } +} + +void +yasm_object_finalize(yasm_object *object, yasm_errwarns *errwarns) +{ + yasm_section *sect; + + /* Iterate through sections */ + STAILQ_FOREACH(sect, &object->sections, link) { + yasm_bytecode *cur = STAILQ_FIRST(§->bcs); + yasm_bytecode *prev; + + /* Skip our locally created empty bytecode first. */ + prev = cur; + cur = STAILQ_NEXT(cur, link); + + /* Iterate through the remainder, if any. */ + while (cur) { + /* Finalize */ + yasm_bc_finalize(cur, prev); + yasm_errwarn_propagate(errwarns, cur->line); + prev = cur; + cur = STAILQ_NEXT(cur, link); + } + } +} + +int +yasm_object_sections_traverse(yasm_object *object, /*@null@*/ void *d, + int (*func) (yasm_section *sect, + /*@null@*/ void *d)) +{ + yasm_section *cur; + + STAILQ_FOREACH(cur, &object->sections, link) { + int retval = func(cur, d); + if (retval != 0) + return retval; + } + return 0; +} + +/*@-onlytrans@*/ +yasm_section * +yasm_object_find_general(yasm_object *object, const char *name) +{ + yasm_section *cur; + + STAILQ_FOREACH(cur, &object->sections, link) { + if (strcmp(cur->name, name) == 0) + return cur; + } + return NULL; +} +/*@=onlytrans@*/ + +void +yasm_section_add_reloc(yasm_section *sect, yasm_reloc *reloc, + void (*destroy_func) (/*@only@*/ void *reloc)) +{ + STAILQ_INSERT_TAIL(§->relocs, reloc, link); + if (!destroy_func) + yasm_internal_error(N_("NULL destroy function given to add_reloc")); + else if (sect->destroy_reloc && destroy_func != sect->destroy_reloc) + yasm_internal_error(N_("different destroy function given to add_reloc")); + sect->destroy_reloc = destroy_func; +} + +/*@null@*/ yasm_reloc * +yasm_section_relocs_first(yasm_section *sect) +{ + return STAILQ_FIRST(§->relocs); +} + +#undef yasm_section_reloc_next +/*@null@*/ yasm_reloc * +yasm_section_reloc_next(yasm_reloc *reloc) +{ + return STAILQ_NEXT(reloc, link); +} + +void +yasm_reloc_get(yasm_reloc *reloc, yasm_intnum **addrp, yasm_symrec **symp) +{ + *addrp = reloc->addr; + *symp = reloc->sym; +} + + +yasm_bytecode * +yasm_section_bcs_first(yasm_section *sect) +{ + return STAILQ_FIRST(§->bcs); +} + +yasm_bytecode * +yasm_section_bcs_last(yasm_section *sect) +{ + return STAILQ_LAST(§->bcs, yasm_bytecode, link); +} + +yasm_bytecode * +yasm_section_bcs_append(yasm_section *sect, yasm_bytecode *bc) +{ + if (bc) { + if (bc->callback) { + bc->section = sect; /* record parent section */ + STAILQ_INSERT_TAIL(§->bcs, bc, link); + return bc; + } else + yasm_xfree(bc); + } + return (yasm_bytecode *)NULL; +} + +int +yasm_section_bcs_traverse(yasm_section *sect, + /*@null@*/ yasm_errwarns *errwarns, + /*@null@*/ void *d, + int (*func) (yasm_bytecode *bc, /*@null@*/ void *d)) +{ + yasm_bytecode *cur = STAILQ_FIRST(§->bcs); + + /* Skip our locally created empty bytecode first. */ + cur = STAILQ_NEXT(cur, link); + + /* Iterate through the remainder, if any. */ + while (cur) { + int retval = func(cur, d); + if (errwarns) + yasm_errwarn_propagate(errwarns, cur->line); + if (retval != 0) + return retval; + cur = STAILQ_NEXT(cur, link); + } + return 0; +} + +const char * +yasm_section_get_name(const yasm_section *sect) +{ + return sect->name; +} + +void +yasm_section_set_align(yasm_section *sect, unsigned long align, + unsigned long line) +{ + sect->align = align; +} + +unsigned long +yasm_section_get_align(const yasm_section *sect) +{ + return sect->align; +} + +static void +yasm_section_destroy(yasm_section *sect) +{ + yasm_bytecode *cur, *next; + yasm_reloc *r_cur, *r_next; + + if (!sect) + return; + + yasm_xfree(sect->name); + yasm__assoc_data_destroy(sect->assoc_data); + + /* Delete bytecodes */ + cur = STAILQ_FIRST(§->bcs); + while (cur) { + next = STAILQ_NEXT(cur, link); + yasm_bc_destroy(cur); + cur = next; + } + + /* Delete relocations */ + r_cur = STAILQ_FIRST(§->relocs); + while (r_cur) { + r_next = STAILQ_NEXT(r_cur, link); + yasm_intnum_destroy(r_cur->addr); + sect->destroy_reloc(r_cur); + r_cur = r_next; + } + + yasm_xfree(sect); +} + +void +yasm_section_print(const yasm_section *sect, FILE *f, int indent_level, + int print_bcs) +{ + if (!sect) { + fprintf(f, "%*s(none)\n", indent_level, ""); + return; + } + + fprintf(f, "%*sname=%s\n", indent_level, "", sect->name); + + if (sect->assoc_data) { + fprintf(f, "%*sAssociated data:\n", indent_level, ""); + yasm__assoc_data_print(sect->assoc_data, f, indent_level+1); + } + + if (print_bcs) { + yasm_bytecode *cur; + + fprintf(f, "%*sBytecodes:\n", indent_level, ""); + + STAILQ_FOREACH(cur, §->bcs, link) { + fprintf(f, "%*sNext Bytecode:\n", indent_level+1, ""); + yasm_bc_print(cur, f, indent_level+2); + } + } +} + +/* + * Robertson (1977) optimizer + * Based (somewhat loosely) on the algorithm given in: + * MRC Technical Summary Report # 1779 + * CODE GENERATION FOR SHORT/LONG ADDRESS MACHINES + * Edward L. Robertson + * Mathematics Research Center + * University of Wisconsin-Madison + * 610 Walnut Street + * Madison, Wisconsin 53706 + * August 1977 + * + * Key components of algorithm: + * - start assuming all short forms + * - build spans for short->long transition dependencies + * - if a long form is needed, walk the dependencies and update + * Major differences from Robertson's algorithm: + * - detection of cycles + * - any difference of two locations is allowed + * - handling of alignment/org gaps (offset setting) + * - handling of multiples + * + * Data structures: + * - Interval tree to store spans and associated data + * - Queues QA and QB + * + * Each span keeps track of: + * - Associated bytecode (bytecode that depends on the span length) + * - Active/inactive state (starts out active) + * - Sign (negative/positive; negative being "backwards" in address) + * - Current length in bytes + * - New length in bytes + * - Negative/Positive thresholds + * - Span ID (unique within each bytecode) + * + * How org and align and any other offset-based bytecodes are handled: + * + * Some portions are critical values that must not depend on any bytecode + * offset (either relative or absolute). + * + * All offset-setters (ORG and ALIGN) are put into a linked list in section + * order (e.g. increasing offset order). Each span keeps track of the next + * offset-setter following the span's associated bytecode. + * + * When a bytecode is expanded, the next offset-setter is examined. The + * offset-setter may be able to absorb the expansion (e.g. any offset + * following it would not change), or it may have to move forward (in the + * case of align) or error (in the case of org). If it has to move forward, + * following offset-setters must also be examined for absorption or moving + * forward. In either case, the ongoing offset is updated as well as the + * lengths of any spans dependent on the offset-setter. + * + * Alignment/ORG value is critical value. + * Cannot be combined with TIMES. + * + * How times is handled: + * + * TIMES: Handled separately from bytecode "raw" size. If not span-dependent, + * trivial (just multiplied in at any bytecode size increase). Span + * dependent times update on any change (span ID 0). If the resultant + * next bytecode offset would be less than the old next bytecode offset, + * error. Otherwise increase offset and update dependent spans. + * + * To reduce interval tree size, a first expansion pass is performed + * before the spans are added to the tree. + * + * Basic algorithm outline: + * + * 1. Initialization: + * a. Number bytecodes sequentially (via bc_index) and calculate offsets + * of all bytecodes assuming minimum length, building a list of all + * dependent spans as we go. + * "minimum" here means absolute minimum: + * - align/org (offset-based) bumps offset as normal + * - times values (with span-dependent values) assumed to be 0 + * b. Iterate over spans. Set span length based on bytecode offsets + * determined in 1a. If span is "certainly" long because the span + * is an absolute reference to another section (or external) or the + * distance calculated based on the minimum length is greater than the + * span's threshold, expand the span's bytecode, and if no further + * expansion can result, mark span as inactive. + * c. Iterate over bytecodes to update all bytecode offsets based on new + * (expanded) lengths calculated in 1b. + * d. Iterate over active spans. Add span to interval tree. Update span's + * length based on new bytecode offsets determined in 1c. If span's + * length exceeds long threshold, add that span to Q. + * 2. Main loop: + * While Q not empty: + * Expand BC dependent on span at head of Q (and remove span from Q). + * Update span: + * If BC no longer dependent on span, mark span as inactive. + * If BC has new thresholds for span, update span. + * If BC increased in size, for each active span that contains BC: + * Increase span length by difference between short and long BC length. + * If span exceeds long threshold (or is flagged to recalculate on any + * change), add it to tail of Q. + * 3. Final pass over bytecodes to generate final offsets. + */ + +typedef struct yasm_span yasm_span; + +typedef struct yasm_offset_setter { + /* Linked list in section order (e.g. offset order) */ + /*@reldef@*/ STAILQ_ENTRY(yasm_offset_setter) link; + + /*@dependent@*/ yasm_bytecode *bc; + + unsigned long cur_val, new_val; + unsigned long thres; +} yasm_offset_setter; + +typedef struct yasm_span_term { + yasm_bytecode *precbc, *precbc2; + yasm_span *span; /* span this term is a member of */ + long cur_val, new_val; + unsigned int subst; +} yasm_span_term; + +struct yasm_span { + /*@reldef@*/ TAILQ_ENTRY(yasm_span) link; /* for allocation tracking */ + /*@reldef@*/ STAILQ_ENTRY(yasm_span) linkq; /* for Q */ + + /*@dependent@*/ yasm_bytecode *bc; + + yasm_value depval; + + /* span term for relative portion of value */ + yasm_span_term *rel_term; + /* span terms in absolute portion of value */ + yasm_span_term *terms; + yasm_expr__item *items; + unsigned int num_terms; + + long cur_val; + long new_val; + + long neg_thres; + long pos_thres; + + int id; + + int active; + + /* NULL-terminated array of spans that led to this span. Used only for + * checking for circular references (cycles) with id=0 spans. + */ + yasm_span **backtrace; + int backtrace_size; + + /* First offset setter following this span's bytecode */ + yasm_offset_setter *os; +}; + +typedef struct optimize_data { + /*@reldef@*/ TAILQ_HEAD(yasm_span_head, yasm_span) spans; + /*@reldef@*/ STAILQ_HEAD(yasm_span_shead, yasm_span) QA, QB; + /*@only@*/ IntervalTree *itree; + /*@reldef@*/ STAILQ_HEAD(offset_setters_head, yasm_offset_setter) + offset_setters; + long len_diff; /* used only for optimize_term_expand */ + yasm_span *span; /* used only for check_cycle */ + yasm_offset_setter *os; +} optimize_data; + +static yasm_span * +create_span(yasm_bytecode *bc, int id, /*@null@*/ const yasm_value *value, + long neg_thres, long pos_thres, yasm_offset_setter *os) +{ + yasm_span *span = yasm_xmalloc(sizeof(yasm_span)); + + span->bc = bc; + if (value) + yasm_value_init_copy(&span->depval, value); + else + yasm_value_initialize(&span->depval, NULL, 0); + span->rel_term = NULL; + span->terms = NULL; + span->items = NULL; + span->num_terms = 0; + span->cur_val = 0; + span->new_val = 0; + span->neg_thres = neg_thres; + span->pos_thres = pos_thres; + span->id = id; + span->active = 1; + span->backtrace = NULL; + span->backtrace_size = 0; + span->os = os; + + return span; +} + +static void +optimize_add_span(void *add_span_data, yasm_bytecode *bc, int id, + const yasm_value *value, long neg_thres, long pos_thres) +{ + optimize_data *optd = (optimize_data *)add_span_data; + yasm_span *span; + span = create_span(bc, id, value, neg_thres, pos_thres, optd->os); + TAILQ_INSERT_TAIL(&optd->spans, span, link); +} + +static void +add_span_term(unsigned int subst, yasm_bytecode *precbc, + yasm_bytecode *precbc2, void *d) +{ + yasm_span *span = d; + yasm_intnum *intn; + + if (subst >= span->num_terms) { + /* Linear expansion since total number is essentially always small */ + span->num_terms = subst+1; + span->terms = yasm_xrealloc(span->terms, + span->num_terms*sizeof(yasm_span_term)); + } + span->terms[subst].precbc = precbc; + span->terms[subst].precbc2 = precbc2; + span->terms[subst].span = span; + span->terms[subst].subst = subst; + + intn = yasm_calc_bc_dist(precbc, precbc2); + if (!intn) + yasm_internal_error(N_("could not calculate bc distance")); + span->terms[subst].cur_val = 0; + span->terms[subst].new_val = yasm_intnum_get_int(intn); + yasm_intnum_destroy(intn); +} + +static void +span_create_terms(yasm_span *span) +{ + unsigned int i; + + /* Split out sym-sym terms in absolute portion of dependent value */ + if (span->depval.abs) { + span->num_terms = yasm_expr__bc_dist_subst(&span->depval.abs, span, + add_span_term); + if (span->num_terms > 0) { + span->items = yasm_xmalloc(span->num_terms*sizeof(yasm_expr__item)); + for (i=0; i<span->num_terms; i++) { + /* Create items with dummy value */ + span->items[i].type = YASM_EXPR_INT; + span->items[i].data.intn = yasm_intnum_create_int(0); + + /* Check for circular references */ + if (span->id <= 0 && + ((span->bc->bc_index > span->terms[i].precbc->bc_index && + span->bc->bc_index <= span->terms[i].precbc2->bc_index) || + (span->bc->bc_index > span->terms[i].precbc2->bc_index && + span->bc->bc_index <= span->terms[i].precbc->bc_index))) + yasm_error_set(YASM_ERROR_VALUE, + N_("circular reference detected")); + } + } + } + + /* Create term for relative portion of dependent value */ + if (span->depval.rel) { + yasm_bytecode *rel_precbc; + int sym_local; + + sym_local = yasm_symrec_get_label(span->depval.rel, &rel_precbc); + if (span->depval.wrt || span->depval.seg_of || span->depval.section_rel + || !sym_local) + return; /* we can't handle SEG, WRT, or external symbols */ + if (rel_precbc->section != span->bc->section) + return; /* not in this section */ + if (!span->depval.curpos_rel) + return; /* not PC-relative */ + + span->rel_term = yasm_xmalloc(sizeof(yasm_span_term)); + span->rel_term->precbc = NULL; + span->rel_term->precbc2 = rel_precbc; + span->rel_term->span = span; + span->rel_term->subst = ~0U; + + span->rel_term->cur_val = 0; + span->rel_term->new_val = yasm_bc_next_offset(rel_precbc) - + span->bc->offset; + } +} + +/* Recalculate span value based on current span replacement values. + * Returns 1 if span needs expansion (e.g. exceeded thresholds). + */ +static int +recalc_normal_span(yasm_span *span) +{ + span->new_val = 0; + + if (span->depval.abs) { + yasm_expr *abs_copy = yasm_expr_copy(span->depval.abs); + /*@null@*/ /*@dependent@*/ yasm_intnum *num; + + /* Update sym-sym terms and substitute back into expr */ + unsigned int i; + for (i=0; i<span->num_terms; i++) + yasm_intnum_set_int(span->items[i].data.intn, + span->terms[i].new_val); + yasm_expr__subst(abs_copy, span->num_terms, span->items); + num = yasm_expr_get_intnum(&abs_copy, 0); + if (num) + span->new_val = yasm_intnum_get_int(num); + else + span->new_val = LONG_MAX; /* too complex; force to longest form */ + yasm_expr_destroy(abs_copy); + } + + if (span->rel_term) { + if (span->new_val != LONG_MAX && span->rel_term->new_val != LONG_MAX) + span->new_val += span->rel_term->new_val >> span->depval.rshift; + else + span->new_val = LONG_MAX; /* too complex; force to longest form */ + } else if (span->depval.rel) + span->new_val = LONG_MAX; /* too complex; force to longest form */ + + if (span->new_val == LONG_MAX) + span->active = 0; + + /* If id<=0, flag update on any change */ + if (span->id <= 0) + return (span->new_val != span->cur_val); + + return (span->new_val < span->neg_thres + || span->new_val > span->pos_thres); +} + +/* Updates all bytecode offsets. For offset-based bytecodes, calls expand + * to determine new length. + */ +static int +update_all_bc_offsets(yasm_object *object, yasm_errwarns *errwarns) +{ + yasm_section *sect; + int saw_error = 0; + + STAILQ_FOREACH(sect, &object->sections, link) { + unsigned long offset = 0; + + yasm_bytecode *bc = STAILQ_FIRST(§->bcs); + yasm_bytecode *prevbc; + + /* Skip our locally created empty bytecode first. */ + prevbc = bc; + bc = STAILQ_NEXT(bc, link); + + /* Iterate through the remainder, if any. */ + while (bc) { + if (bc->callback->special == YASM_BC_SPECIAL_OFFSET) { + /* Recalculate/adjust len of offset-based bytecodes here */ + long neg_thres = 0; + long pos_thres = (long)yasm_bc_next_offset(bc); + int retval = yasm_bc_expand(bc, 1, 0, + (long)yasm_bc_next_offset(prevbc), + &neg_thres, &pos_thres); + yasm_errwarn_propagate(errwarns, bc->line); + if (retval < 0) + saw_error = 1; + } + bc->offset = offset; + offset += bc->len*bc->mult_int; + prevbc = bc; + bc = STAILQ_NEXT(bc, link); + } + } + return saw_error; +} + +static void +span_destroy(/*@only@*/ yasm_span *span) +{ + unsigned int i; + + yasm_value_delete(&span->depval); + if (span->rel_term) + yasm_xfree(span->rel_term); + if (span->terms) + yasm_xfree(span->terms); + if (span->items) { + for (i=0; i<span->num_terms; i++) + yasm_intnum_destroy(span->items[i].data.intn); + yasm_xfree(span->items); + } + if (span->backtrace) + yasm_xfree(span->backtrace); + yasm_xfree(span); +} + +static void +optimize_cleanup(optimize_data *optd) +{ + yasm_span *s1, *s2; + yasm_offset_setter *os1, *os2; + + IT_destroy(optd->itree); + + s1 = TAILQ_FIRST(&optd->spans); + while (s1) { + s2 = TAILQ_NEXT(s1, link); + span_destroy(s1); + s1 = s2; + } + + os1 = STAILQ_FIRST(&optd->offset_setters); + while (os1) { + os2 = STAILQ_NEXT(os1, link); + yasm_xfree(os1); + os1 = os2; + } +} + +static void +optimize_itree_add(IntervalTree *itree, yasm_span *span, yasm_span_term *term) +{ + long precbc_index, precbc2_index; + unsigned long low, high; + + /* Update term length */ + if (term->precbc) + precbc_index = term->precbc->bc_index; + else + precbc_index = span->bc->bc_index-1; + + if (term->precbc2) + precbc2_index = term->precbc2->bc_index; + else + precbc2_index = span->bc->bc_index-1; + + if (precbc_index < precbc2_index) { + low = precbc_index+1; + high = precbc2_index; + } else if (precbc_index > precbc2_index) { + low = precbc2_index+1; + high = precbc_index; + } else + return; /* difference is same bc - always 0! */ + + IT_insert(itree, (long)low, (long)high, term); +} + +static void +check_cycle(IntervalTreeNode *node, void *d) +{ + optimize_data *optd = d; + yasm_span_term *term = node->data; + yasm_span *depspan = term->span; + int i; + int depspan_bt_alloc; + + /* Only check for cycles in id=0 spans */ + if (depspan->id > 0) + return; + + /* Check for a circular reference by looking to see if this dependent + * span is in our backtrace. + */ + if (optd->span->backtrace) { + for (i=0; i<optd->span->backtrace_size; i++) { + if (optd->span->backtrace[i] == depspan) + yasm_error_set(YASM_ERROR_VALUE, + N_("circular reference detected")); + } + } + + /* Add our complete backtrace and ourselves to backtrace of dependent + * span. + */ + if (!depspan->backtrace) { + depspan->backtrace = yasm_xmalloc((optd->span->backtrace_size+1)* + sizeof(yasm_span *)); + if (optd->span->backtrace_size > 0) + memcpy(depspan->backtrace, optd->span->backtrace, + optd->span->backtrace_size*sizeof(yasm_span *)); + depspan->backtrace[optd->span->backtrace_size] = optd->span; + depspan->backtrace_size = optd->span->backtrace_size+1; + return; + } + + /* Add our complete backtrace, checking for duplicates */ + depspan_bt_alloc = depspan->backtrace_size; + for (i=0; i<optd->span->backtrace_size; i++) { + int present = 0; + int j; + for (j=0; j<depspan->backtrace_size; j++) { + if (optd->span->backtrace[i] == optd->span->backtrace[j]) { + present = 1; + break; + } + } + if (present) + continue; + /* Not already in array; add it. */ + if (depspan->backtrace_size >= depspan_bt_alloc) + { + depspan_bt_alloc *= 2; + depspan->backtrace = + yasm_xrealloc(depspan->backtrace, + depspan_bt_alloc*sizeof(yasm_span *)); + } + depspan->backtrace[depspan->backtrace_size] = optd->span->backtrace[i]; + depspan->backtrace_size++; + } + + /* Add ourselves. */ + if (depspan->backtrace_size >= depspan_bt_alloc) + { + depspan_bt_alloc++; + depspan->backtrace = + yasm_xrealloc(depspan->backtrace, + depspan_bt_alloc*sizeof(yasm_span *)); + } + depspan->backtrace[depspan->backtrace_size] = optd->span; + depspan->backtrace_size++; +} + +static void +optimize_term_expand(IntervalTreeNode *node, void *d) +{ + optimize_data *optd = d; + yasm_span_term *term = node->data; + yasm_span *span = term->span; + long len_diff = optd->len_diff; + long precbc_index, precbc2_index; + + /* Don't expand inactive spans */ + if (!span->active) + return; + + /* Update term length */ + if (term->precbc) + precbc_index = term->precbc->bc_index; + else + precbc_index = span->bc->bc_index-1; + + if (term->precbc2) + precbc2_index = term->precbc2->bc_index; + else + precbc2_index = span->bc->bc_index-1; + + if (precbc_index < precbc2_index) + term->new_val += len_diff; + else + term->new_val -= len_diff; + + /* If already on Q, don't re-add */ + if (span->active == 2) + return; + + /* Update term and check against thresholds */ + if (!recalc_normal_span(span)) + return; /* didn't exceed thresholds, we're done */ + + /* Exceeded thresholds, need to add to Q for expansion */ + if (span->id <= 0) + STAILQ_INSERT_TAIL(&optd->QA, span, linkq); + else + STAILQ_INSERT_TAIL(&optd->QB, span, linkq); + span->active = 2; /* Mark as being in Q */ +} + +void +yasm_object_optimize(yasm_object *object, yasm_errwarns *errwarns) +{ + yasm_section *sect; + unsigned long bc_index = 0; + int saw_error = 0; + optimize_data optd; + yasm_span *span, *span_temp; + yasm_offset_setter *os; + int retval; + unsigned int i; + + TAILQ_INIT(&optd.spans); + STAILQ_INIT(&optd.offset_setters); + optd.itree = IT_create(); + + /* Create an placeholder offset setter for spans to point to; this will + * get updated if/when we actually run into one. + */ + os = yasm_xmalloc(sizeof(yasm_offset_setter)); + os->bc = NULL; + os->cur_val = 0; + os->new_val = 0; + os->thres = 0; + STAILQ_INSERT_TAIL(&optd.offset_setters, os, link); + optd.os = os; + + /* Step 1a */ + STAILQ_FOREACH(sect, &object->sections, link) { + unsigned long offset = 0; + + yasm_bytecode *bc = STAILQ_FIRST(§->bcs); + yasm_bytecode *prevbc; + + bc->bc_index = bc_index++; + + /* Skip our locally created empty bytecode first. */ + prevbc = bc; + bc = STAILQ_NEXT(bc, link); + + /* Iterate through the remainder, if any. */ + while (bc) { + bc->bc_index = bc_index++; + bc->offset = offset; + + retval = yasm_bc_calc_len(bc, optimize_add_span, &optd); + yasm_errwarn_propagate(errwarns, bc->line); + if (retval) + saw_error = 1; + else { + if (bc->callback->special == YASM_BC_SPECIAL_OFFSET) { + /* Remember it as offset setter */ + os->bc = bc; + os->thres = yasm_bc_next_offset(bc); + + /* Create new placeholder */ + os = yasm_xmalloc(sizeof(yasm_offset_setter)); + os->bc = NULL; + os->cur_val = 0; + os->new_val = 0; + os->thres = 0; + STAILQ_INSERT_TAIL(&optd.offset_setters, os, link); + optd.os = os; + + if (bc->multiple) { + yasm_error_set(YASM_ERROR_VALUE, + N_("cannot combine multiples and setting assembly position")); + yasm_errwarn_propagate(errwarns, bc->line); + saw_error = 1; + } + } + + offset += bc->len*bc->mult_int; + } + + prevbc = bc; + bc = STAILQ_NEXT(bc, link); + } + } + + if (saw_error) { + optimize_cleanup(&optd); + return; + } + + /* Step 1b */ + TAILQ_FOREACH_SAFE(span, &optd.spans, link, span_temp) { + span_create_terms(span); + if (yasm_error_occurred()) { + yasm_errwarn_propagate(errwarns, span->bc->line); + saw_error = 1; + } else if (recalc_normal_span(span)) { + retval = yasm_bc_expand(span->bc, span->id, span->cur_val, + span->new_val, &span->neg_thres, + &span->pos_thres); + yasm_errwarn_propagate(errwarns, span->bc->line); + if (retval < 0) + saw_error = 1; + else if (retval > 0) { + if (!span->active) { + yasm_error_set(YASM_ERROR_VALUE, + N_("secondary expansion of an external/complex value")); + yasm_errwarn_propagate(errwarns, span->bc->line); + saw_error = 1; + } + } else { + TAILQ_REMOVE(&optd.spans, span, link); + span_destroy(span); + continue; + } + } + span->cur_val = span->new_val; + } + + if (saw_error) { + optimize_cleanup(&optd); + return; + } + + /* Step 1c */ + if (update_all_bc_offsets(object, errwarns)) { + optimize_cleanup(&optd); + return; + } + + /* Step 1d */ + STAILQ_INIT(&optd.QB); + TAILQ_FOREACH(span, &optd.spans, link) { + yasm_intnum *intn; + + /* Update span terms based on new bc offsets */ + for (i=0; i<span->num_terms; i++) { + intn = yasm_calc_bc_dist(span->terms[i].precbc, + span->terms[i].precbc2); + if (!intn) + yasm_internal_error(N_("could not calculate bc distance")); + span->terms[i].cur_val = span->terms[i].new_val; + span->terms[i].new_val = yasm_intnum_get_int(intn); + yasm_intnum_destroy(intn); + } + if (span->rel_term) { + span->rel_term->cur_val = span->rel_term->new_val; + if (span->rel_term->precbc2) + span->rel_term->new_val = + yasm_bc_next_offset(span->rel_term->precbc2) - + span->bc->offset; + else + span->rel_term->new_val = span->bc->offset - + yasm_bc_next_offset(span->rel_term->precbc); + } + + if (recalc_normal_span(span)) { + /* Exceeded threshold, add span to QB */ + STAILQ_INSERT_TAIL(&optd.QB, span, linkq); + span->active = 2; + } + } + + /* Do we need step 2? If not, go ahead and exit. */ + if (STAILQ_EMPTY(&optd.QB)) { + optimize_cleanup(&optd); + return; + } + + /* Update offset-setters values */ + STAILQ_FOREACH(os, &optd.offset_setters, link) { + if (!os->bc) + continue; + os->thres = yasm_bc_next_offset(os->bc); + os->new_val = os->bc->offset; + os->cur_val = os->new_val; + } + + /* Build up interval tree */ + TAILQ_FOREACH(span, &optd.spans, link) { + for (i=0; i<span->num_terms; i++) + optimize_itree_add(optd.itree, span, &span->terms[i]); + if (span->rel_term) + optimize_itree_add(optd.itree, span, span->rel_term); + } + + /* Look for cycles in times expansion (span.id==0) */ + TAILQ_FOREACH(span, &optd.spans, link) { + if (span->id > 0) + continue; + optd.span = span; + IT_enumerate(optd.itree, (long)span->bc->bc_index, + (long)span->bc->bc_index, &optd, check_cycle); + if (yasm_error_occurred()) { + yasm_errwarn_propagate(errwarns, span->bc->line); + saw_error = 1; + } + } + + if (saw_error) { + optimize_cleanup(&optd); + return; + } + + /* Step 2 */ + STAILQ_INIT(&optd.QA); + while (!STAILQ_EMPTY(&optd.QA) || !(STAILQ_EMPTY(&optd.QB))) { + unsigned long orig_len; + long offset_diff; + + /* QA is for TIMES, update those first, then update non-TIMES. + * This is so that TIMES can absorb increases before we look at + * expanding non-TIMES BCs. + */ + if (!STAILQ_EMPTY(&optd.QA)) { + span = STAILQ_FIRST(&optd.QA); + STAILQ_REMOVE_HEAD(&optd.QA, linkq); + } else { + span = STAILQ_FIRST(&optd.QB); + STAILQ_REMOVE_HEAD(&optd.QB, linkq); + } + + if (!span->active) + continue; + span->active = 1; /* no longer in Q */ + + /* Make sure we ended up ultimately exceeding thresholds; due to + * offset BCs we may have been placed on Q and then reduced in size + * again. + */ + if (!recalc_normal_span(span)) + continue; + + orig_len = span->bc->len * span->bc->mult_int; + + retval = yasm_bc_expand(span->bc, span->id, span->cur_val, + span->new_val, &span->neg_thres, + &span->pos_thres); + yasm_errwarn_propagate(errwarns, span->bc->line); + + if (retval < 0) { + /* error */ + saw_error = 1; + continue; + } else if (retval > 0) { + /* another threshold, keep active */ + for (i=0; i<span->num_terms; i++) + span->terms[i].cur_val = span->terms[i].new_val; + if (span->rel_term) + span->rel_term->cur_val = span->rel_term->new_val; + span->cur_val = span->new_val; + } else + span->active = 0; /* we're done with this span */ + + optd.len_diff = span->bc->len * span->bc->mult_int - orig_len; + if (optd.len_diff == 0) + continue; /* didn't increase in size */ + + /* Iterate over all spans dependent across the bc just expanded */ + IT_enumerate(optd.itree, (long)span->bc->bc_index, + (long)span->bc->bc_index, &optd, optimize_term_expand); + + /* Iterate over offset-setters that follow the bc just expanded. + * Stop iteration if: + * - no more offset-setters in this section + * - offset-setter didn't move its following offset + */ + os = span->os; + offset_diff = optd.len_diff; + while (os->bc && os->bc->section == span->bc->section + && offset_diff != 0) { + unsigned long old_next_offset = os->cur_val + os->bc->len; + long neg_thres_temp; + + if (offset_diff < 0 && (unsigned long)(-offset_diff) > os->new_val) + yasm_internal_error(N_("org/align went to negative offset")); + os->new_val += offset_diff; + + orig_len = os->bc->len; + retval = yasm_bc_expand(os->bc, 1, (long)os->cur_val, + (long)os->new_val, &neg_thres_temp, + (long *)&os->thres); + yasm_errwarn_propagate(errwarns, os->bc->line); + + offset_diff = os->new_val + os->bc->len - old_next_offset; + optd.len_diff = os->bc->len - orig_len; + if (optd.len_diff != 0) + IT_enumerate(optd.itree, (long)os->bc->bc_index, + (long)os->bc->bc_index, &optd, optimize_term_expand); + + os->cur_val = os->new_val; + os = STAILQ_NEXT(os, link); + } + } + + if (saw_error) { + optimize_cleanup(&optd); + return; + } + + /* Step 3 */ + update_all_bc_offsets(object, errwarns); + optimize_cleanup(&optd); +} |