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
dir_extern(yasm_object * object,yasm_valparamhead * valparams,yasm_valparamhead * objext_valparams,unsigned long line)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
dir_global(yasm_object * object,yasm_valparamhead * valparams,yasm_valparamhead * objext_valparams,unsigned long line)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
dir_common(yasm_object * object,yasm_valparamhead * valparams,yasm_valparamhead * objext_valparams,unsigned long line)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
dir_section(yasm_object * object,yasm_valparamhead * valparams,yasm_valparamhead * objext_valparams,unsigned long line)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
directive_level2_delete(void * data)176 directive_level2_delete(/*@only@*/ void *data)
177 {
178 yasm_xfree(data);
179 }
180
181 static void
directive_level1_delete(void * data)182 directive_level1_delete(/*@only@*/ void *data)
183 {
184 HAMT_destroy(data, directive_level2_delete);
185 }
186
187 static void
directives_add(yasm_object * object,const yasm_directive * dir)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 *
yasm_object_create(const char * src_filename,const char * obj_filename,yasm_arch * arch,const yasm_objfmt_module * objfmt_module,const yasm_dbgfmt_module * dbgfmt_module)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 *
yasm_object_get_general(yasm_object * object,const char * name,unsigned long align,int code,int res_only,int * isnew,unsigned long line)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
yasm_object_directive(yasm_object * object,const char * name,const char * parser,yasm_valparamhead * valparams,yasm_valparamhead * objext_valparams,unsigned long line)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
yasm_object_set_source_fn(yasm_object * object,const char * src_filename)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
yasm_object_set_global_prefix(yasm_object * object,const char * prefix)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
yasm_object_set_global_suffix(yasm_object * object,const char * suffix)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
yasm_section_is_code(yasm_section * sect)400 yasm_section_is_code(yasm_section *sect)
401 {
402 return sect->code;
403 }
404
405 unsigned long
yasm_section_get_opt_flags(const yasm_section * sect)406 yasm_section_get_opt_flags(const yasm_section *sect)
407 {
408 return sect->opt_flags;
409 }
410
411 void
yasm_section_set_opt_flags(yasm_section * sect,unsigned long opt_flags)412 yasm_section_set_opt_flags(yasm_section *sect, unsigned long opt_flags)
413 {
414 sect->opt_flags = opt_flags;
415 }
416
417 int
yasm_section_is_default(const yasm_section * sect)418 yasm_section_is_default(const yasm_section *sect)
419 {
420 return sect->def;
421 }
422
423 void
yasm_section_set_default(yasm_section * sect,int def)424 yasm_section_set_default(yasm_section *sect, int def)
425 {
426 sect->def = def;
427 }
428
429 yasm_object *
yasm_section_get_object(const yasm_section * sect)430 yasm_section_get_object(const yasm_section *sect)
431 {
432 return sect->object;
433 }
434
435 void *
yasm_section_get_data(yasm_section * sect,const yasm_assoc_data_callback * callback)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
yasm_section_add_data(yasm_section * sect,const yasm_assoc_data_callback * callback,void * data)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
yasm_object_destroy(yasm_object * object)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
yasm_object_print(const yasm_object * object,FILE * f,int indent_level)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
yasm_object_finalize(yasm_object * object,yasm_errwarns * errwarns)508 yasm_object_finalize(yasm_object *object, yasm_errwarns *errwarns)
509 {
510 yasm_section *sect;
511
512 /* Iterate through sections */
513 STAILQ_FOREACH(sect, &object->sections, link) {
514 yasm_bytecode *cur = STAILQ_FIRST(§->bcs);
515 yasm_bytecode *prev;
516
517 /* Skip our locally created empty bytecode first. */
518 prev = cur;
519 cur = STAILQ_NEXT(cur, link);
520
521 /* Iterate through the remainder, if any. */
522 while (cur) {
523 /* Finalize */
524 yasm_bc_finalize(cur, prev);
525 yasm_errwarn_propagate(errwarns, cur->line);
526 prev = cur;
527 cur = STAILQ_NEXT(cur, link);
528 }
529 }
530 }
531
532 int
yasm_object_sections_traverse(yasm_object * object,void * d,int (* func)(yasm_section * sect,void * d))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 *
yasm_object_find_general(yasm_object * object,const char * name)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
yasm_section_add_reloc(yasm_section * sect,yasm_reloc * reloc,void (* destroy_func)(void * reloc))562 yasm_section_add_reloc(yasm_section *sect, yasm_reloc *reloc,
563 void (*destroy_func) (/*@only@*/ void *reloc))
564 {
565 STAILQ_INSERT_TAIL(§->relocs, reloc, link);
566 if (!destroy_func)
567 yasm_internal_error(N_("NULL destroy function given to add_reloc"));
568 else if (sect->destroy_reloc && destroy_func != sect->destroy_reloc)
569 yasm_internal_error(N_("different destroy function given to add_reloc"));
570 sect->destroy_reloc = destroy_func;
571 }
572
573 /*@null@*/ yasm_reloc *
yasm_section_relocs_first(yasm_section * sect)574 yasm_section_relocs_first(yasm_section *sect)
575 {
576 return STAILQ_FIRST(§->relocs);
577 }
578
579 #undef yasm_section_reloc_next
580 /*@null@*/ yasm_reloc *
yasm_section_reloc_next(yasm_reloc * reloc)581 yasm_section_reloc_next(yasm_reloc *reloc)
582 {
583 return STAILQ_NEXT(reloc, link);
584 }
585
586 void
yasm_reloc_get(yasm_reloc * reloc,yasm_intnum ** addrp,yasm_symrec ** symp)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 *
yasm_section_bcs_first(yasm_section * sect)595 yasm_section_bcs_first(yasm_section *sect)
596 {
597 return STAILQ_FIRST(§->bcs);
598 }
599
600 yasm_bytecode *
yasm_section_bcs_last(yasm_section * sect)601 yasm_section_bcs_last(yasm_section *sect)
602 {
603 return STAILQ_LAST(§->bcs, yasm_bytecode, link);
604 }
605
606 yasm_bytecode *
yasm_section_bcs_append(yasm_section * sect,yasm_bytecode * bc)607 yasm_section_bcs_append(yasm_section *sect, yasm_bytecode *bc)
608 {
609 if (bc) {
610 if (bc->callback) {
611 bc->section = sect; /* record parent section */
612 STAILQ_INSERT_TAIL(§->bcs, bc, link);
613 return bc;
614 } else
615 yasm_xfree(bc);
616 }
617 return (yasm_bytecode *)NULL;
618 }
619
620 int
yasm_section_bcs_traverse(yasm_section * sect,yasm_errwarns * errwarns,void * d,int (* func)(yasm_bytecode * bc,void * d))621 yasm_section_bcs_traverse(yasm_section *sect,
622 /*@null@*/ yasm_errwarns *errwarns,
623 /*@null@*/ void *d,
624 int (*func) (yasm_bytecode *bc, /*@null@*/ void *d))
625 {
626 yasm_bytecode *cur = STAILQ_FIRST(§->bcs);
627
628 /* Skip our locally created empty bytecode first. */
629 cur = STAILQ_NEXT(cur, link);
630
631 /* Iterate through the remainder, if any. */
632 while (cur) {
633 int retval = func(cur, d);
634 if (errwarns)
635 yasm_errwarn_propagate(errwarns, cur->line);
636 if (retval != 0)
637 return retval;
638 cur = STAILQ_NEXT(cur, link);
639 }
640 return 0;
641 }
642
643 const char *
yasm_section_get_name(const yasm_section * sect)644 yasm_section_get_name(const yasm_section *sect)
645 {
646 return sect->name;
647 }
648
649 void
yasm_section_set_align(yasm_section * sect,unsigned long align,unsigned long line)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
yasm_section_get_align(const yasm_section * sect)657 yasm_section_get_align(const yasm_section *sect)
658 {
659 return sect->align;
660 }
661
662 static void
yasm_section_destroy(yasm_section * sect)663 yasm_section_destroy(yasm_section *sect)
664 {
665 yasm_bytecode *cur, *next;
666 yasm_reloc *r_cur, *r_next;
667
668 if (!sect)
669 return;
670
671 yasm_xfree(sect->name);
672 yasm__assoc_data_destroy(sect->assoc_data);
673
674 /* Delete bytecodes */
675 cur = STAILQ_FIRST(§->bcs);
676 while (cur) {
677 next = STAILQ_NEXT(cur, link);
678 yasm_bc_destroy(cur);
679 cur = next;
680 }
681
682 /* Delete relocations */
683 r_cur = STAILQ_FIRST(§->relocs);
684 while (r_cur) {
685 r_next = STAILQ_NEXT(r_cur, link);
686 yasm_intnum_destroy(r_cur->addr);
687 sect->destroy_reloc(r_cur);
688 r_cur = r_next;
689 }
690
691 yasm_xfree(sect);
692 }
693
694 void
yasm_section_print(const yasm_section * sect,FILE * f,int indent_level,int print_bcs)695 yasm_section_print(const yasm_section *sect, FILE *f, int indent_level,
696 int print_bcs)
697 {
698 if (!sect) {
699 fprintf(f, "%*s(none)\n", indent_level, "");
700 return;
701 }
702
703 fprintf(f, "%*sname=%s\n", indent_level, "", sect->name);
704
705 if (sect->assoc_data) {
706 fprintf(f, "%*sAssociated data:\n", indent_level, "");
707 yasm__assoc_data_print(sect->assoc_data, f, indent_level+1);
708 }
709
710 if (print_bcs) {
711 yasm_bytecode *cur;
712
713 fprintf(f, "%*sBytecodes:\n", indent_level, "");
714
715 STAILQ_FOREACH(cur, §->bcs, link) {
716 fprintf(f, "%*sNext Bytecode:\n", indent_level+1, "");
717 yasm_bc_print(cur, f, indent_level+2);
718 }
719 }
720 }
721
722 /*
723 * Robertson (1977) optimizer
724 * Based (somewhat loosely) on the algorithm given in:
725 * MRC Technical Summary Report # 1779
726 * CODE GENERATION FOR SHORT/LONG ADDRESS MACHINES
727 * Edward L. Robertson
728 * Mathematics Research Center
729 * University of Wisconsin-Madison
730 * 610 Walnut Street
731 * Madison, Wisconsin 53706
732 * August 1977
733 *
734 * Key components of algorithm:
735 * - start assuming all short forms
736 * - build spans for short->long transition dependencies
737 * - if a long form is needed, walk the dependencies and update
738 * Major differences from Robertson's algorithm:
739 * - detection of cycles
740 * - any difference of two locations is allowed
741 * - handling of alignment/org gaps (offset setting)
742 * - handling of multiples
743 *
744 * Data structures:
745 * - Interval tree to store spans and associated data
746 * - Queues QA and QB
747 *
748 * Each span keeps track of:
749 * - Associated bytecode (bytecode that depends on the span length)
750 * - Active/inactive state (starts out active)
751 * - Sign (negative/positive; negative being "backwards" in address)
752 * - Current length in bytes
753 * - New length in bytes
754 * - Negative/Positive thresholds
755 * - Span ID (unique within each bytecode)
756 *
757 * How org and align and any other offset-based bytecodes are handled:
758 *
759 * Some portions are critical values that must not depend on any bytecode
760 * offset (either relative or absolute).
761 *
762 * All offset-setters (ORG and ALIGN) are put into a linked list in section
763 * order (e.g. increasing offset order). Each span keeps track of the next
764 * offset-setter following the span's associated bytecode.
765 *
766 * When a bytecode is expanded, the next offset-setter is examined. The
767 * offset-setter may be able to absorb the expansion (e.g. any offset
768 * following it would not change), or it may have to move forward (in the
769 * case of align) or error (in the case of org). If it has to move forward,
770 * following offset-setters must also be examined for absorption or moving
771 * forward. In either case, the ongoing offset is updated as well as the
772 * lengths of any spans dependent on the offset-setter.
773 *
774 * Alignment/ORG value is critical value.
775 * Cannot be combined with TIMES.
776 *
777 * How times is handled:
778 *
779 * TIMES: Handled separately from bytecode "raw" size. If not span-dependent,
780 * trivial (just multiplied in at any bytecode size increase). Span
781 * dependent times update on any change (span ID 0). If the resultant
782 * next bytecode offset would be less than the old next bytecode offset,
783 * error. Otherwise increase offset and update dependent spans.
784 *
785 * To reduce interval tree size, a first expansion pass is performed
786 * before the spans are added to the tree.
787 *
788 * Basic algorithm outline:
789 *
790 * 1. Initialization:
791 * a. Number bytecodes sequentially (via bc_index) and calculate offsets
792 * of all bytecodes assuming minimum length, building a list of all
793 * dependent spans as we go.
794 * "minimum" here means absolute minimum:
795 * - align/org (offset-based) bumps offset as normal
796 * - times values (with span-dependent values) assumed to be 0
797 * b. Iterate over spans. Set span length based on bytecode offsets
798 * determined in 1a. If span is "certainly" long because the span
799 * is an absolute reference to another section (or external) or the
800 * distance calculated based on the minimum length is greater than the
801 * span's threshold, expand the span's bytecode, and if no further
802 * expansion can result, mark span as inactive.
803 * c. Iterate over bytecodes to update all bytecode offsets based on new
804 * (expanded) lengths calculated in 1b.
805 * d. Iterate over active spans. Add span to interval tree. Update span's
806 * length based on new bytecode offsets determined in 1c. If span's
807 * length exceeds long threshold, add that span to Q.
808 * 2. Main loop:
809 * While Q not empty:
810 * Expand BC dependent on span at head of Q (and remove span from Q).
811 * Update span:
812 * If BC no longer dependent on span, mark span as inactive.
813 * If BC has new thresholds for span, update span.
814 * If BC increased in size, for each active span that contains BC:
815 * Increase span length by difference between short and long BC length.
816 * If span exceeds long threshold (or is flagged to recalculate on any
817 * change), add it to tail of Q.
818 * 3. Final pass over bytecodes to generate final offsets.
819 */
820
821 typedef struct yasm_span yasm_span;
822
823 typedef struct yasm_offset_setter {
824 /* Linked list in section order (e.g. offset order) */
825 /*@reldef@*/ STAILQ_ENTRY(yasm_offset_setter) link;
826
827 /*@dependent@*/ yasm_bytecode *bc;
828
829 unsigned long cur_val, new_val;
830 unsigned long thres;
831 } yasm_offset_setter;
832
833 typedef struct yasm_span_term {
834 yasm_bytecode *precbc, *precbc2;
835 yasm_span *span; /* span this term is a member of */
836 long cur_val, new_val;
837 unsigned int subst;
838 } yasm_span_term;
839
840 struct yasm_span {
841 /*@reldef@*/ TAILQ_ENTRY(yasm_span) link; /* for allocation tracking */
842 /*@reldef@*/ STAILQ_ENTRY(yasm_span) linkq; /* for Q */
843
844 /*@dependent@*/ yasm_bytecode *bc;
845
846 yasm_value depval;
847
848 /* span term for relative portion of value */
849 yasm_span_term *rel_term;
850 /* span terms in absolute portion of value */
851 yasm_span_term *terms;
852 yasm_expr__item *items;
853 unsigned int num_terms;
854
855 long cur_val;
856 long new_val;
857
858 long neg_thres;
859 long pos_thres;
860
861 int id;
862
863 int active;
864
865 /* NULL-terminated array of spans that led to this span. Used only for
866 * checking for circular references (cycles) with id=0 spans.
867 */
868 yasm_span **backtrace;
869 int backtrace_size;
870
871 /* First offset setter following this span's bytecode */
872 yasm_offset_setter *os;
873 };
874
875 typedef struct optimize_data {
876 /*@reldef@*/ TAILQ_HEAD(yasm_span_head, yasm_span) spans;
877 /*@reldef@*/ STAILQ_HEAD(yasm_span_shead, yasm_span) QA, QB;
878 /*@only@*/ IntervalTree *itree;
879 /*@reldef@*/ STAILQ_HEAD(offset_setters_head, yasm_offset_setter)
880 offset_setters;
881 long len_diff; /* used only for optimize_term_expand */
882 yasm_span *span; /* used only for check_cycle */
883 yasm_offset_setter *os;
884 } optimize_data;
885
886 static yasm_span *
create_span(yasm_bytecode * bc,int id,const yasm_value * value,long neg_thres,long pos_thres,yasm_offset_setter * os)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
optimize_add_span(void * add_span_data,yasm_bytecode * bc,int id,const yasm_value * value,long neg_thres,long pos_thres)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
add_span_term(unsigned int subst,yasm_bytecode * precbc,yasm_bytecode * precbc2,void * d)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
span_create_terms(yasm_span * span)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
recalc_normal_span(yasm_span * span)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
update_all_bc_offsets(yasm_object * object,yasm_errwarns * errwarns)1053 update_all_bc_offsets(yasm_object *object, yasm_errwarns *errwarns)
1054 {
1055 yasm_section *sect;
1056 int saw_error = 0;
1057
1058 STAILQ_FOREACH(sect, &object->sections, link) {
1059 unsigned long offset = 0;
1060
1061 yasm_bytecode *bc = STAILQ_FIRST(§->bcs);
1062 yasm_bytecode *prevbc;
1063
1064 /* Skip our locally created empty bytecode first. */
1065 prevbc = bc;
1066 bc = STAILQ_NEXT(bc, link);
1067
1068 /* Iterate through the remainder, if any. */
1069 while (bc) {
1070 if (bc->callback->special == YASM_BC_SPECIAL_OFFSET) {
1071 /* Recalculate/adjust len of offset-based bytecodes here */
1072 long neg_thres = 0;
1073 long pos_thres = (long)yasm_bc_next_offset(bc);
1074 int retval = yasm_bc_expand(bc, 1, 0,
1075 (long)yasm_bc_next_offset(prevbc),
1076 &neg_thres, &pos_thres);
1077 yasm_errwarn_propagate(errwarns, bc->line);
1078 if (retval < 0)
1079 saw_error = 1;
1080 }
1081 bc->offset = offset;
1082 offset += bc->len*bc->mult_int;
1083 prevbc = bc;
1084 bc = STAILQ_NEXT(bc, link);
1085 }
1086 }
1087 return saw_error;
1088 }
1089
1090 static void
span_destroy(yasm_span * span)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
optimize_cleanup(optimize_data * optd)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
optimize_itree_add(IntervalTree * itree,yasm_span * span,yasm_span_term * term)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
check_cycle(IntervalTreeNode * node,void * d)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
optimize_term_expand(IntervalTreeNode * node,void * d)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
yasm_object_optimize(yasm_object * object,yasm_errwarns * errwarns)1283 yasm_object_optimize(yasm_object *object, yasm_errwarns *errwarns)
1284 {
1285 yasm_section *sect;
1286 unsigned long bc_index = 0;
1287 int saw_error = 0;
1288 optimize_data optd;
1289 yasm_span *span, *span_temp;
1290 yasm_offset_setter *os;
1291 int retval;
1292 unsigned int i;
1293
1294 TAILQ_INIT(&optd.spans);
1295 STAILQ_INIT(&optd.offset_setters);
1296 optd.itree = IT_create();
1297
1298 /* Create an placeholder offset setter for spans to point to; this will
1299 * get updated if/when we actually run into one.
1300 */
1301 os = yasm_xmalloc(sizeof(yasm_offset_setter));
1302 os->bc = NULL;
1303 os->cur_val = 0;
1304 os->new_val = 0;
1305 os->thres = 0;
1306 STAILQ_INSERT_TAIL(&optd.offset_setters, os, link);
1307 optd.os = os;
1308
1309 /* Step 1a */
1310 STAILQ_FOREACH(sect, &object->sections, link) {
1311 unsigned long offset = 0;
1312
1313 yasm_bytecode *bc = STAILQ_FIRST(§->bcs);
1314 yasm_bytecode *prevbc;
1315
1316 bc->bc_index = bc_index++;
1317
1318 /* Skip our locally created empty bytecode first. */
1319 prevbc = bc;
1320 bc = STAILQ_NEXT(bc, link);
1321
1322 /* Iterate through the remainder, if any. */
1323 while (bc) {
1324 bc->bc_index = bc_index++;
1325 bc->offset = offset;
1326
1327 retval = yasm_bc_calc_len(bc, optimize_add_span, &optd);
1328 yasm_errwarn_propagate(errwarns, bc->line);
1329 if (retval)
1330 saw_error = 1;
1331 else {
1332 if (bc->callback->special == YASM_BC_SPECIAL_OFFSET) {
1333 /* Remember it as offset setter */
1334 os->bc = bc;
1335 os->thres = yasm_bc_next_offset(bc);
1336
1337 /* Create new placeholder */
1338 os = yasm_xmalloc(sizeof(yasm_offset_setter));
1339 os->bc = NULL;
1340 os->cur_val = 0;
1341 os->new_val = 0;
1342 os->thres = 0;
1343 STAILQ_INSERT_TAIL(&optd.offset_setters, os, link);
1344 optd.os = os;
1345
1346 if (bc->multiple) {
1347 yasm_error_set(YASM_ERROR_VALUE,
1348 N_("cannot combine multiples and setting assembly position"));
1349 yasm_errwarn_propagate(errwarns, bc->line);
1350 saw_error = 1;
1351 }
1352 }
1353
1354 offset += bc->len*bc->mult_int;
1355 }
1356
1357 prevbc = bc;
1358 bc = STAILQ_NEXT(bc, link);
1359 }
1360 }
1361
1362 if (saw_error) {
1363 optimize_cleanup(&optd);
1364 return;
1365 }
1366
1367 /* Step 1b */
1368 TAILQ_FOREACH_SAFE(span, &optd.spans, link, span_temp) {
1369 span_create_terms(span);
1370 if (yasm_error_occurred()) {
1371 yasm_errwarn_propagate(errwarns, span->bc->line);
1372 saw_error = 1;
1373 } else if (recalc_normal_span(span)) {
1374 retval = yasm_bc_expand(span->bc, span->id, span->cur_val,
1375 span->new_val, &span->neg_thres,
1376 &span->pos_thres);
1377 yasm_errwarn_propagate(errwarns, span->bc->line);
1378 if (retval < 0)
1379 saw_error = 1;
1380 else if (retval > 0) {
1381 if (!span->active) {
1382 yasm_error_set(YASM_ERROR_VALUE,
1383 N_("secondary expansion of an external/complex value"));
1384 yasm_errwarn_propagate(errwarns, span->bc->line);
1385 saw_error = 1;
1386 }
1387 } else {
1388 TAILQ_REMOVE(&optd.spans, span, link);
1389 span_destroy(span);
1390 continue;
1391 }
1392 }
1393 span->cur_val = span->new_val;
1394 }
1395
1396 if (saw_error) {
1397 optimize_cleanup(&optd);
1398 return;
1399 }
1400
1401 /* Step 1c */
1402 if (update_all_bc_offsets(object, errwarns)) {
1403 optimize_cleanup(&optd);
1404 return;
1405 }
1406
1407 /* Step 1d */
1408 STAILQ_INIT(&optd.QB);
1409 TAILQ_FOREACH(span, &optd.spans, link) {
1410 yasm_intnum *intn;
1411
1412 /* Update span terms based on new bc offsets */
1413 for (i=0; i<span->num_terms; i++) {
1414 intn = yasm_calc_bc_dist(span->terms[i].precbc,
1415 span->terms[i].precbc2);
1416 if (!intn)
1417 yasm_internal_error(N_("could not calculate bc distance"));
1418 span->terms[i].cur_val = span->terms[i].new_val;
1419 span->terms[i].new_val = yasm_intnum_get_int(intn);
1420 yasm_intnum_destroy(intn);
1421 }
1422 if (span->rel_term) {
1423 span->rel_term->cur_val = span->rel_term->new_val;
1424 if (span->rel_term->precbc2)
1425 span->rel_term->new_val =
1426 yasm_bc_next_offset(span->rel_term->precbc2) -
1427 span->bc->offset;
1428 else
1429 span->rel_term->new_val = span->bc->offset -
1430 yasm_bc_next_offset(span->rel_term->precbc);
1431 }
1432
1433 if (recalc_normal_span(span)) {
1434 /* Exceeded threshold, add span to QB */
1435 STAILQ_INSERT_TAIL(&optd.QB, span, linkq);
1436 span->active = 2;
1437 }
1438 }
1439
1440 /* Do we need step 2? If not, go ahead and exit. */
1441 if (STAILQ_EMPTY(&optd.QB)) {
1442 optimize_cleanup(&optd);
1443 return;
1444 }
1445
1446 /* Update offset-setters values */
1447 STAILQ_FOREACH(os, &optd.offset_setters, link) {
1448 if (!os->bc)
1449 continue;
1450 os->thres = yasm_bc_next_offset(os->bc);
1451 os->new_val = os->bc->offset;
1452 os->cur_val = os->new_val;
1453 }
1454
1455 /* Build up interval tree */
1456 TAILQ_FOREACH(span, &optd.spans, link) {
1457 for (i=0; i<span->num_terms; i++)
1458 optimize_itree_add(optd.itree, span, &span->terms[i]);
1459 if (span->rel_term)
1460 optimize_itree_add(optd.itree, span, span->rel_term);
1461 }
1462
1463 /* Look for cycles in times expansion (span.id==0) */
1464 TAILQ_FOREACH(span, &optd.spans, link) {
1465 if (span->id > 0)
1466 continue;
1467 optd.span = span;
1468 IT_enumerate(optd.itree, (long)span->bc->bc_index,
1469 (long)span->bc->bc_index, &optd, check_cycle);
1470 if (yasm_error_occurred()) {
1471 yasm_errwarn_propagate(errwarns, span->bc->line);
1472 saw_error = 1;
1473 }
1474 }
1475
1476 if (saw_error) {
1477 optimize_cleanup(&optd);
1478 return;
1479 }
1480
1481 /* Step 2 */
1482 STAILQ_INIT(&optd.QA);
1483 while (!STAILQ_EMPTY(&optd.QA) || !(STAILQ_EMPTY(&optd.QB))) {
1484 unsigned long orig_len;
1485 long offset_diff;
1486
1487 /* QA is for TIMES, update those first, then update non-TIMES.
1488 * This is so that TIMES can absorb increases before we look at
1489 * expanding non-TIMES BCs.
1490 */
1491 if (!STAILQ_EMPTY(&optd.QA)) {
1492 span = STAILQ_FIRST(&optd.QA);
1493 STAILQ_REMOVE_HEAD(&optd.QA, linkq);
1494 } else {
1495 span = STAILQ_FIRST(&optd.QB);
1496 STAILQ_REMOVE_HEAD(&optd.QB, linkq);
1497 }
1498
1499 if (!span->active)
1500 continue;
1501 span->active = 1; /* no longer in Q */
1502
1503 /* Make sure we ended up ultimately exceeding thresholds; due to
1504 * offset BCs we may have been placed on Q and then reduced in size
1505 * again.
1506 */
1507 if (!recalc_normal_span(span))
1508 continue;
1509
1510 orig_len = span->bc->len * span->bc->mult_int;
1511
1512 retval = yasm_bc_expand(span->bc, span->id, span->cur_val,
1513 span->new_val, &span->neg_thres,
1514 &span->pos_thres);
1515 yasm_errwarn_propagate(errwarns, span->bc->line);
1516
1517 if (retval < 0) {
1518 /* error */
1519 saw_error = 1;
1520 continue;
1521 } else if (retval > 0) {
1522 /* another threshold, keep active */
1523 for (i=0; i<span->num_terms; i++)
1524 span->terms[i].cur_val = span->terms[i].new_val;
1525 if (span->rel_term)
1526 span->rel_term->cur_val = span->rel_term->new_val;
1527 span->cur_val = span->new_val;
1528 } else
1529 span->active = 0; /* we're done with this span */
1530
1531 optd.len_diff = span->bc->len * span->bc->mult_int - orig_len;
1532 if (optd.len_diff == 0)
1533 continue; /* didn't increase in size */
1534
1535 /* Iterate over all spans dependent across the bc just expanded */
1536 IT_enumerate(optd.itree, (long)span->bc->bc_index,
1537 (long)span->bc->bc_index, &optd, optimize_term_expand);
1538
1539 /* Iterate over offset-setters that follow the bc just expanded.
1540 * Stop iteration if:
1541 * - no more offset-setters in this section
1542 * - offset-setter didn't move its following offset
1543 */
1544 os = span->os;
1545 offset_diff = optd.len_diff;
1546 while (os->bc && os->bc->section == span->bc->section
1547 && offset_diff != 0) {
1548 unsigned long old_next_offset = os->cur_val + os->bc->len;
1549 long neg_thres_temp;
1550
1551 if (offset_diff < 0 && (unsigned long)(-offset_diff) > os->new_val)
1552 yasm_internal_error(N_("org/align went to negative offset"));
1553 os->new_val += offset_diff;
1554
1555 orig_len = os->bc->len;
1556 retval = yasm_bc_expand(os->bc, 1, (long)os->cur_val,
1557 (long)os->new_val, &neg_thres_temp,
1558 (long *)&os->thres);
1559 yasm_errwarn_propagate(errwarns, os->bc->line);
1560
1561 offset_diff = os->new_val + os->bc->len - old_next_offset;
1562 optd.len_diff = os->bc->len - orig_len;
1563 if (optd.len_diff != 0)
1564 IT_enumerate(optd.itree, (long)os->bc->bc_index,
1565 (long)os->bc->bc_index, &optd, optimize_term_expand);
1566
1567 os->cur_val = os->new_val;
1568 os = STAILQ_NEXT(os, link);
1569 }
1570 }
1571
1572 if (saw_error) {
1573 optimize_cleanup(&optd);
1574 return;
1575 }
1576
1577 /* Step 3 */
1578 update_all_bc_offsets(object, errwarns);
1579 optimize_cleanup(&optd);
1580 }
1581