Lines Matching refs:span
748 * Each span keeps track of:
749 * - Associated bytecode (bytecode that depends on the span length)
763 * order (e.g. increasing offset order). Each span keeps track of the next
764 * offset-setter following the span's associated bytecode.
779 * TIMES: Handled separately from bytecode "raw" size. If not span-dependent,
781 * dependent times update on any change (span ID 0). If the resultant
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
801 * span's threshold, expand the span's bytecode, and if no further
802 * expansion can result, mark span as inactive.
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.
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
835 yasm_span *span; /* span this term is a member of */
848 /* span term for relative portion of value */
850 /* span terms in absolute portion of value */
865 /* NULL-terminated array of spans that led to this span. Used only for
871 /* First offset setter following this span's bytecode */
882 yasm_span *span; /* used only for check_cycle */
890 yasm_span *span = yasm_xmalloc(sizeof(yasm_span));
892 span->bc = bc;
894 yasm_value_init_copy(&span->depval, value);
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;
911 return span;
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);
928 yasm_span *span = d;
931 if (subst >= span->num_terms) {
933 span->num_terms = subst+1;
934 span->terms = yasm_xrealloc(span->terms,
935 span->num_terms*sizeof(yasm_span_term));
937 span->terms[subst].precbc = precbc;
938 span->terms[subst].precbc2 = precbc2;
939 span->terms[subst].span = span;
940 span->terms[subst].subst = subst;
945 span->terms[subst].cur_val = 0;
946 span->terms[subst].new_val = yasm_intnum_get_int(intn);
951 span_create_terms(yasm_span *span)
956 if (span->depval.abs) {
957 span->num_terms = yasm_expr__bc_dist_subst(&span->depval.abs, span,
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++) {
963 span->items[i].type = YASM_EXPR_INT;
964 span->items[i].data.intn = yasm_intnum_create_int(0);
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)))
979 if (span->depval.rel) {
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
987 if (rel_precbc->section != span->bc->section)
989 if (!span->depval.curpos_rel)
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;
998 span->rel_term->cur_val = 0;
999 span->rel_term->new_val = yasm_bc_next_offset(rel_precbc) -
1000 span->bc->offset;
1004 /* Recalculate span value based on current span replacement values.
1005 * Returns 1 if span needs expansion (e.g. exceeded thresholds).
1008 recalc_normal_span(yasm_span *span)
1010 span->new_val = 0;
1012 if (span->depval.abs) {
1013 yasm_expr *abs_copy = yasm_expr_copy(span->depval.abs);
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);
1024 span->new_val = yasm_intnum_get_int(num);
1026 span->new_val = LONG_MAX; /* too complex; force to longest form */
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;
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 */
1038 if (span->new_val == LONG_MAX)
1039 span->active = 0;
1042 if (span->id <= 0)
1043 return (span->new_val != span->cur_val);
1045 return (span->new_val < span->neg_thres
1046 || span->new_val > span->pos_thres);
1091 span_destroy(/*@only@*/ yasm_span *span)
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);
1105 if (span->backtrace)
1106 yasm_xfree(span->backtrace);
1107 yasm_xfree(span);
1134 optimize_itree_add(IntervalTree *itree, yasm_span *span, yasm_span_term *term)
1143 precbc_index = span->bc->bc_index-1;
1148 precbc2_index = span->bc->bc_index-1;
1167 yasm_span *depspan = term->span;
1176 * span is in our backtrace.
1178 if (optd->span->backtrace) {
1179 for (i=0; i<optd->span->backtrace_size; i++) {
1180 if (optd->span->backtrace[i] == depspan)
1187 * span.
1190 depspan->backtrace = yasm_xmalloc((optd->span->backtrace_size+1)*
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;
1202 for (i=0; i<optd->span->backtrace_size; i++) {
1206 if (optd->span->backtrace[i] == optd->span->backtrace[j]) {
1221 depspan->backtrace[depspan->backtrace_size] = optd->span->backtrace[i];
1233 depspan->backtrace[depspan->backtrace_size] = optd->span;
1242 yasm_span *span = term->span;
1247 if (!span->active)
1254 precbc_index = span->bc->bc_index-1;
1259 precbc2_index = span->bc->bc_index-1;
1267 if (span->active == 2)
1271 if (!recalc_normal_span(span))
1275 if (span->id <= 0)
1276 STAILQ_INSERT_TAIL(&optd->QA, span, linkq);
1278 STAILQ_INSERT_TAIL(&optd->QB, span, linkq);
1279 span->active = 2; /* Mark as being in Q */
1289 yasm_span *span, *span_temp;
1368 TAILQ_FOREACH_SAFE(span, &optd.spans, link, span_temp) {
1369 span_create_terms(span);
1371 yasm_errwarn_propagate(errwarns, span->bc->line);
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);
1381 if (!span->active) {
1384 yasm_errwarn_propagate(errwarns, span->bc->line);
1388 TAILQ_REMOVE(&optd.spans, span, link);
1389 span_destroy(span);
1393 span->cur_val = span->new_val;
1409 TAILQ_FOREACH(span, &optd.spans, link) {
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);
1418 span->terms[i].cur_val = span->terms[i].new_val;
1419 span->terms[i].new_val = yasm_intnum_get_int(intn);
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;
1429 span->rel_term->new_val = span->bc->offset -
1430 yasm_bc_next_offset(span->rel_term->precbc);
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;
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);
1463 /* Look for cycles in times expansion (span.id==0) */
1464 TAILQ_FOREACH(span, &optd.spans, link) {
1465 if (span->id > 0)
1467 optd.span = span;
1468 IT_enumerate(optd.itree, (long)span->bc->bc_index,
1469 (long)span->bc->bc_index, &optd, check_cycle);
1471 yasm_errwarn_propagate(errwarns, span->bc->line);
1492 span = STAILQ_FIRST(&optd.QA);
1495 span = STAILQ_FIRST(&optd.QB);
1499 if (!span->active)
1501 span->active = 1; /* no longer in Q */
1507 if (!recalc_normal_span(span))
1510 orig_len = span->bc->len * span->bc->mult_int;
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);
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;
1529 span->active = 0; /* we're done with this span */
1531 optd.len_diff = span->bc->len * span->bc->mult_int - orig_len;
1536 IT_enumerate(optd.itree, (long)span->bc->bc_index,
1537 (long)span->bc->bc_index, &optd, optimize_term_expand);
1544 os = span->os;
1546 while (os->bc && os->bc->section == span->bc->section