libyasm/expr.c

   1 /*
   2  * Expression handling
   3  *
   4  *  Copyright (C) 2001-2007  Michael Urman, 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 "libyasm-stdint.h"
  30 #include "coretype.h"
  31 #include "bitvect.h"
  32
  33 #include "errwarn.h"
  34 #include "intnum.h"
  35 #include "floatnum.h"
  36 #include "expr.h"
  37 #include "symrec.h"
  38
  39 #include "bytecode.h"
  40 #include "section.h"
  41
  42 #include "arch.h"
  43
  44
  45 static /*@only@*/ yasm_expr *expr_level_op
  46     (/*@returned@*/ /*@only@*/ yasm_expr *e, int fold_const,
  47      int simplify_ident, int simplify_reg_mul);
  48 static int expr_traverse_nodes_post(/*@null@*/ yasm_expr *e,
  49                                     /*@null@*/ void *d,
  50                                     int (*func) (/*@null@*/ yasm_expr *e,
  51                                                  /*@null@*/ void *d));
  52 static void expr_delete_term(yasm_expr__item *term, int recurse);
  53
  54 /* Bitmap of used items.  We should really never need more than 2 at a time,
  55  * so 31 is pretty much overkill.
  56  */
  57 static unsigned long itempool_used = 0;
  58 static yasm_expr__item itempool[31];
  59
  60 /* allocate a new expression node, with children as defined.
  61  * If it's a unary operator, put the element in left and set right=NULL. */
  62 /*@-compmempass@*/
  63 yasm_expr *
  64 yasm_expr_create(yasm_expr_op op, yasm_expr__item *left,
  65                  yasm_expr__item *right, unsigned long line)
  66 {
  67     yasm_expr *ptr, *sube;
  68     unsigned long z;
  69     ptr = yasm_xmalloc(sizeof(yasm_expr));
  70
  71     ptr->op = op;
  72     ptr->numterms = 0;
  73     ptr->terms[0].type = YASM_EXPR_NONE;
  74     ptr->terms[1].type = YASM_EXPR_NONE;
  75     if (left) {
  76         ptr->terms[0] = *left;  /* structure copy */
  77         z = (unsigned long)(left-itempool);
  78         if (z>=31)
  79             yasm_internal_error(N_("could not find expritem in pool"));
  80         itempool_used &= ~(1<<z);
  81         ptr->numterms++;
  82
  83         /* Search downward until we find something *other* than an
  84          * IDENT, then bring it up to the current level.
  85          */
  86         while (ptr->terms[0].type == YASM_EXPR_EXPR &&
  87                ptr->terms[0].data.expn->op == YASM_EXPR_IDENT) {
  88             sube = ptr->terms[0].data.expn;
  89             ptr->terms[0] = sube->terms[0];     /* structure copy */
  90             /*@-usereleased@*/
  91             yasm_xfree(sube);
  92             /*@=usereleased@*/
  93         }
  94     } else {
  95         yasm_internal_error(N_("Right side of expression must exist"));
  96     }
  97
  98     if (right) {
  99         ptr->terms[1] = *right; /* structure copy */
 100         z = (unsigned long)(right-itempool);
 101         if (z>=31)
 102             yasm_internal_error(N_("could not find expritem in pool"));
 103         itempool_used &= ~(1<<z);
 104         ptr->numterms++;
 105
 106         /* Search downward until we find something *other* than an
 107          * IDENT, then bring it up to the current level.
 108          */
 109         while (ptr->terms[1].type == YASM_EXPR_EXPR &&
 110                ptr->terms[1].data.expn->op == YASM_EXPR_IDENT) {
 111             sube = ptr->terms[1].data.expn;
 112             ptr->terms[1] = sube->terms[0];     /* structure copy */
 113             /*@-usereleased@*/
 114             yasm_xfree(sube);
 115             /*@=usereleased@*/
 116         }
 117     }
 118
 119     ptr->line = line;
 120
 121     return expr_level_op(ptr, 1, 1, 0);
 122 }
 123 /*@=compmempass@*/
 124
 125 /* helpers */
 126 static yasm_expr__item *
 127 expr_get_item(void)
 128 {
 129     int z = 0;
 130     unsigned long v = itempool_used & 0x7fffffff;
 131
 132     while (v & 1) {
 133         v >>= 1;
 134         z++;
 135     }
 136     if (z>=31)
 137         yasm_internal_error(N_("too many expritems"));
 138     itempool_used |= 1<<z;
 139     return &itempool[z];
 140 }
 141
 142 yasm_expr__item *
 143 yasm_expr_precbc(yasm_bytecode *precbc)
 144 {
 145     yasm_expr__item *e = expr_get_item();
 146     e->type = YASM_EXPR_PRECBC;
 147     e->data.precbc = precbc;
 148     return e;
 149 }
 150
 151 yasm_expr__item *
 152 yasm_expr_sym(yasm_symrec *s)
 153 {
 154     yasm_expr__item *e = expr_get_item();
 155     e->type = YASM_EXPR_SYM;
 156     e->data.sym = s;
 157     return e;
 158 }
 159
 160 yasm_expr__item *
 161 yasm_expr_expr(yasm_expr *x)
 162 {
 163     yasm_expr__item *e = expr_get_item();
 164     e->type = YASM_EXPR_EXPR;
 165     e->data.expn = x;
 166     return e;
 167 }
 168
 169 yasm_expr__item *
 170 yasm_expr_int(yasm_intnum *i)
 171 {
 172     yasm_expr__item *e = expr_get_item();
 173     e->type = YASM_EXPR_INT;
 174     e->data.intn = i;
 175     return e;
 176 }
 177
 178 yasm_expr__item *
 179 yasm_expr_float(yasm_floatnum *f)
 180 {
 181     yasm_expr__item *e = expr_get_item();
 182     e->type = YASM_EXPR_FLOAT;
 183     e->data.flt = f;
 184     return e;
 185 }
 186
 187 yasm_expr__item *
 188 yasm_expr_reg(uintptr_t reg)
 189 {
 190     yasm_expr__item *e = expr_get_item();
 191     e->type = YASM_EXPR_REG;
 192     e->data.reg = reg;
 193     return e;
 194 }
 195
 196 /* Transforms instances of symrec-symrec [symrec+(-1*symrec)] into single
 197  * expritems if possible.  Uses a simple n^2 algorithm because n is usually
 198  * quite small.  Also works for precbc-precbc (or symrec-precbc,
 199  * precbc-symrec).
 200  */
 201 static /*@only@*/ yasm_expr *
 202 expr_xform_bc_dist_base(/*@returned@*/ /*@only@*/ yasm_expr *e,
 203                         /*@null@*/ void *cbd,
 204                         int (*callback) (yasm_expr__item *ei,
 205                                          yasm_bytecode *precbc,
 206                                          yasm_bytecode *precbc2,
 207                                          void *cbd))
 208 {
 209     int i;
 210     /*@dependent@*/ yasm_section *sect;
 211     /*@dependent@*/ /*@null@*/ yasm_bytecode *precbc;
 212     int numterms;
 213
 214     /* Handle symrec-symrec in ADD exprs by looking for (-1*symrec) and
 215      * symrec term pairs (where both symrecs are in the same segment).
 216      */
 217     if (e->op != YASM_EXPR_ADD)
 218         return e;
 219
 220     for (i=0; i<e->numterms; i++) {
 221         int j;
 222         yasm_expr *sube;
 223         yasm_intnum *intn;
 224         yasm_symrec *sym = NULL;
 225         /*@dependent@*/ yasm_section *sect2;
 226         /*@dependent@*/ /*@null@*/ yasm_bytecode *precbc2;
 227
 228         /* First look for an (-1*symrec) term */
 229         if (e->terms[i].type != YASM_EXPR_EXPR)
 230             continue;
 231         sube = e->terms[i].data.expn;
 232         if (sube->op != YASM_EXPR_MUL || sube->numterms != 2)
 233             continue;
 234
 235         if (sube->terms[0].type == YASM_EXPR_INT &&
 236             (sube->terms[1].type == YASM_EXPR_SYM ||
 237              sube->terms[1].type == YASM_EXPR_PRECBC)) {
 238             intn = sube->terms[0].data.intn;
 239             if (sube->terms[1].type == YASM_EXPR_PRECBC)
 240                 precbc = sube->terms[1].data.precbc;
 241             else
 242                 sym = sube->terms[1].data.sym;
 243         } else if ((sube->terms[0].type == YASM_EXPR_SYM ||
 244                     sube->terms[0].type == YASM_EXPR_PRECBC) &&
 245                    sube->terms[1].type == YASM_EXPR_INT) {
 246             if (sube->terms[0].type == YASM_EXPR_PRECBC)
 247                 precbc = sube->terms[0].data.precbc;
 248             else
 249                 sym = sube->terms[0].data.sym;
 250             intn = sube->terms[1].data.intn;
 251         } else
 252             continue;
 253
 254         if (!yasm_intnum_is_neg1(intn))
 255             continue;
 256
 257         if (sym && !yasm_symrec_get_label(sym, &precbc))
 258             continue;
 259         sect2 = yasm_bc_get_section(precbc);
 260
 261         /* Now look for a symrec term in the same segment */
 262         for (j=0; j<e->numterms; j++) {
 263             if (((e->terms[j].type == YASM_EXPR_SYM &&
 264                   yasm_symrec_get_label(e->terms[j].data.sym, &precbc2)) ||
 265                  (e->terms[j].type == YASM_EXPR_PRECBC &&
 266                   (precbc2 = e->terms[j].data.precbc))) &&
 267                 (sect = yasm_bc_get_section(precbc2)) &&
 268                 sect == sect2 &&
 269                 callback(&e->terms[j], precbc, precbc2, cbd)) {
 270                 /* Delete the matching (-1*symrec) term */
 271                 yasm_expr_destroy(sube);
 272                 e->terms[i].type = YASM_EXPR_NONE;
 273                 break;  /* stop looking for matching symrec term */
 274             }
 275         }
 276     }
 277
 278     /* Clean up any deleted (EXPR_NONE) terms */
 279     numterms = 0;
 280     for (i=0; i<e->numterms; i++) {
 281         if (e->terms[i].type != YASM_EXPR_NONE)
 282             e->terms[numterms++] = e->terms[i]; /* structure copy */
 283     }
 284     if (e->numterms != numterms) {
 285         e->numterms = numterms;
 286         e = yasm_xrealloc(e, sizeof(yasm_expr)+((numterms<2) ? 0 :
 287                           sizeof(yasm_expr__item)*(numterms-2)));
 288         if (numterms == 1)
 289             e->op = YASM_EXPR_IDENT;
 290     }
 291
 292     return e;
 293 }
 294
 295 static int
 296 expr_xform_bc_dist_cb(yasm_expr__item *ei, yasm_bytecode *precbc,
 297                       yasm_bytecode *precbc2, /*@null@*/ void *d)
 298 {
 299     yasm_intnum *dist = yasm_calc_bc_dist(precbc, precbc2);
 300     if (!dist)
 301         return 0;
 302     /* Change the term to an integer */
 303     ei->type = YASM_EXPR_INT;
 304     ei->data.intn = dist;
 305     return 1;
 306 }
 307
 308 /* Transforms instances of symrec-symrec [symrec+(-1*symrec)] into integers if
 309  * possible.
 310  */
 311 static /*@only@*/ yasm_expr *
 312 expr_xform_bc_dist(/*@returned@*/ /*@only@*/ yasm_expr *e)
 313 {
 314     return expr_xform_bc_dist_base(e, NULL, expr_xform_bc_dist_cb);
 315 }
 316
 317 typedef struct bc_dist_subst_cbd {
 318     void (*callback) (unsigned int subst, yasm_bytecode *precbc,
 319                       yasm_bytecode *precbc2, void *cbd);
 320     void *cbd;
 321     unsigned int subst;
 322 } bc_dist_subst_cbd;
 323
 324 static int
 325 expr_bc_dist_subst_cb(yasm_expr__item *ei, yasm_bytecode *precbc,
 326                       yasm_bytecode *precbc2, /*@null@*/ void *d)
 327 {
 328     bc_dist_subst_cbd *my_cbd = d;
 329     assert(my_cbd != NULL);
 330     /* Call higher-level callback */
 331     my_cbd->callback(my_cbd->subst, precbc, precbc2, my_cbd->cbd);
 332     /* Change the term to an subst */
 333     ei->type = YASM_EXPR_SUBST;
 334     ei->data.subst = my_cbd->subst;
 335     my_cbd->subst++;
 336     return 1;
 337 }
 338
 339 static yasm_expr *
 340 expr_xform_bc_dist_subst(yasm_expr *e, void *d)
 341 {
 342     return expr_xform_bc_dist_base(e, d, expr_bc_dist_subst_cb);
 343 }
 344
 345 int
 346 yasm_expr__bc_dist_subst(yasm_expr **ep, void *cbd,
 347                          void (*callback) (unsigned int subst,
 348                                            yasm_bytecode *precbc,
 349                                            yasm_bytecode *precbc2,
 350                                            void *cbd))
 351 {
 352     bc_dist_subst_cbd my_cbd;   /* callback info for low-level callback */
 353     my_cbd.callback = callback;
 354     my_cbd.cbd = cbd;
 355     my_cbd.subst = 0;
 356     *ep = yasm_expr__level_tree(*ep, 1, 1, 1, 0, &expr_xform_bc_dist_subst,
 357                                 &my_cbd);
 358     return my_cbd.subst;
 359 }
 360
 361 /* Negate just a single ExprItem by building a -1*ei subexpression */
 362 static void
 363 expr_xform_neg_item(yasm_expr *e, yasm_expr__item *ei)
 364 {
 365     yasm_expr *sube = yasm_xmalloc(sizeof(yasm_expr));
 366
 367     /* Build -1*ei subexpression */
 368     sube->op = YASM_EXPR_MUL;
 369     sube->line = e->line;
 370     sube->numterms = 2;
 371     sube->terms[0].type = YASM_EXPR_INT;
 372     sube->terms[0].data.intn = yasm_intnum_create_int(-1);
 373     sube->terms[1] = *ei;       /* structure copy */
 374
 375     /* Replace original ExprItem with subexp */
 376     ei->type = YASM_EXPR_EXPR;
 377     ei->data.expn = sube;
 378 }
 379
 380 /* Negates e by multiplying by -1, with distribution over lower-precedence
 381  * operators (eg ADD) and special handling to simplify result w/ADD, NEG, and
 382  * others.
 383  *
 384  * Returns a possibly reallocated e.
 385  */
 386 static /*@only@*/ yasm_expr *
 387 expr_xform_neg_helper(/*@returned@*/ /*@only@*/ yasm_expr *e)
 388 {
 389     yasm_expr *ne;
 390     int i;
 391
 392     switch (e->op) {
 393         case YASM_EXPR_ADD:
 394             /* distribute (recursively if expr) over terms */
 395             for (i=0; i<e->numterms; i++) {
 396                 if (e->terms[i].type == YASM_EXPR_EXPR)
 397                     e->terms[i].data.expn =
 398                         expr_xform_neg_helper(e->terms[i].data.expn);
 399                 else
 400                     expr_xform_neg_item(e, &e->terms[i]);
 401             }
 402             break;
 403         case YASM_EXPR_SUB:
 404             /* change op to ADD, and recursively negate left side (if expr) */
 405             e->op = YASM_EXPR_ADD;
 406             if (e->terms[0].type == YASM_EXPR_EXPR)
 407                 e->terms[0].data.expn =
 408                     expr_xform_neg_helper(e->terms[0].data.expn);
 409             else
 410                 expr_xform_neg_item(e, &e->terms[0]);
 411             break;
 412         case YASM_EXPR_NEG:
 413             /* Negating a negated value?  Make it an IDENT. */
 414             e->op = YASM_EXPR_IDENT;
 415             break;
 416         case YASM_EXPR_IDENT:
 417             /* Negating an ident?  Change it into a MUL w/ -1 if there's no
 418              * floatnums present below; if there ARE floatnums, recurse.
 419              */
 420             if (e->terms[0].type == YASM_EXPR_FLOAT)
 421                 yasm_floatnum_calc(e->terms[0].data.flt, YASM_EXPR_NEG, NULL);
 422             else if (e->terms[0].type == YASM_EXPR_INT)
 423                 yasm_intnum_calc(e->terms[0].data.intn, YASM_EXPR_NEG, NULL);
 424             else if (e->terms[0].type == YASM_EXPR_EXPR &&
 425                 yasm_expr__contains(e->terms[0].data.expn, YASM_EXPR_FLOAT))
 426                     expr_xform_neg_helper(e->terms[0].data.expn);
 427             else {
 428                 e->op = YASM_EXPR_MUL;
 429                 e->numterms = 2;
 430                 e->terms[1].type = YASM_EXPR_INT;
 431                 e->terms[1].data.intn = yasm_intnum_create_int(-1);
 432             }
 433             break;
 434         default:
 435             /* Everything else.  MUL will be combined when it's leveled.
 436              * Make a new expr (to replace e) with -1*e.
 437              */
 438             ne = yasm_xmalloc(sizeof(yasm_expr));
 439             ne->op = YASM_EXPR_MUL;
 440             ne->line = e->line;
 441             ne->numterms = 2;
 442             ne->terms[0].type = YASM_EXPR_INT;
 443             ne->terms[0].data.intn = yasm_intnum_create_int(-1);
 444             ne->terms[1].type = YASM_EXPR_EXPR;
 445             ne->terms[1].data.expn = e;
 446             return ne;
 447     }
 448     return e;
 449 }
 450
 451 /* Transforms negatives into expressions that are easier to combine:
 452  * -x -> -1*x
 453  * a-b -> a+(-1*b)
 454  *
 455  * Call post-order on an expression tree to transform the entire tree.
 456  *
 457  * Returns a possibly reallocated e.
 458  */
 459 static /*@only@*/ yasm_expr *
 460 expr_xform_neg(/*@returned@*/ /*@only@*/ yasm_expr *e)
 461 {
 462     switch (e->op) {
 463         case YASM_EXPR_NEG:
 464             /* Turn -x into -1*x */
 465             e->op = YASM_EXPR_IDENT;
 466             return expr_xform_neg_helper(e);
 467         case YASM_EXPR_SUB:
 468             /* Turn a-b into a+(-1*b) */
 469
 470             /* change op to ADD, and recursively negate right side (if expr) */
 471             e->op = YASM_EXPR_ADD;
 472             if (e->terms[1].type == YASM_EXPR_EXPR)
 473                 e->terms[1].data.expn =
 474                     expr_xform_neg_helper(e->terms[1].data.expn);
 475             else
 476                 expr_xform_neg_item(e, &e->terms[1]);
 477             break;
 478         default:
 479             break;
 480     }
 481
 482     return e;
 483 }
 484
 485 /* Look for simple identities that make the entire result constant:
 486  * 0*&x, -1|x, etc.
 487  */
 488 static int
 489 expr_is_constant(yasm_expr_op op, yasm_intnum *intn)
 490 {
 491     int iszero = yasm_intnum_is_zero(intn);
 492     return ((iszero && op == YASM_EXPR_MUL) ||
 493             (iszero && op == YASM_EXPR_AND) ||
 494             (iszero && op == YASM_EXPR_LAND) ||
 495             (yasm_intnum_is_neg1(intn) && op == YASM_EXPR_OR));
 496 }
 497
 498 /* Look for simple "left" identities like 0+x, 1*x, etc. */
 499 static int
 500 expr_can_destroy_int_left(yasm_expr_op op, yasm_intnum *intn)
 501 {
 502     int iszero = yasm_intnum_is_zero(intn);
 503     return ((yasm_intnum_is_pos1(intn) && op == YASM_EXPR_MUL) ||
 504             (iszero && op == YASM_EXPR_ADD) ||
 505             (yasm_intnum_is_neg1(intn) && op == YASM_EXPR_AND) ||
 506             (!iszero && op == YASM_EXPR_LAND) ||
 507             (iszero && op == YASM_EXPR_OR) ||
 508             (iszero && op == YASM_EXPR_LOR));
 509 }
 510
 511 /* Look for simple "right" identities like x+|-0, x*&/1 */
 512 static int
 513 expr_can_destroy_int_right(yasm_expr_op op, yasm_intnum *intn)
 514 {
 515     int iszero = yasm_intnum_is_zero(intn);
 516     int ispos1 = yasm_intnum_is_pos1(intn);
 517     return ((ispos1 && op == YASM_EXPR_MUL) ||
 518             (ispos1 && op == YASM_EXPR_DIV) ||
 519             (iszero && op == YASM_EXPR_ADD) ||
 520             (iszero && op == YASM_EXPR_SUB) ||
 521             (yasm_intnum_is_neg1(intn) && op == YASM_EXPR_AND) ||
 522             (!iszero && op == YASM_EXPR_LAND) ||
 523             (iszero && op == YASM_EXPR_OR) ||
 524             (iszero && op == YASM_EXPR_LOR) ||
 525             (iszero && op == YASM_EXPR_SHL) ||
 526             (iszero && op == YASM_EXPR_SHR));
 527 }
 528
 529 /* Check for and simplify identities.  Returns new number of expr terms.
 530  * Sets e->op = EXPR_IDENT if numterms ends up being 1.
 531  * Uses numterms parameter instead of e->numterms for basis of "new" number
 532  * of terms.
 533  * Assumes int_term is *only* integer term in e.
 534  * NOTE: Really designed to only be used by expr_level_op().
 535  */
 536 static int
 537 expr_simplify_identity(yasm_expr *e, int numterms, int *int_term,
 538                        int simplify_reg_mul)
 539 {
 540     int i;
 541     int save_numterms;
 542
 543     /* Don't do this step if it's 1*REG.  Save and restore numterms so
 544      * yasm_expr__contains() works correctly.
 545      */
 546     save_numterms = e->numterms;
 547     e->numterms = numterms;
 548     if (simplify_reg_mul || e->op != YASM_EXPR_MUL
 549         || !yasm_intnum_is_pos1(e->terms[*int_term].data.intn)
 550         || !yasm_expr__contains(e, YASM_EXPR_REG)) {
 551         /* Check for simple identities that delete the intnum.
 552          * Don't delete if the intnum is the only thing in the expn.
 553          */
 554         if ((*int_term == 0 && numterms > 1 &&
 555              expr_can_destroy_int_left(e->op, e->terms[0].data.intn)) ||
 556             (*int_term > 0 &&
 557              expr_can_destroy_int_right(e->op,
 558                                         e->terms[*int_term].data.intn))) {
 559             /* Delete the intnum */
 560             yasm_intnum_destroy(e->terms[*int_term].data.intn);
 561
 562             /* Slide everything to its right over by 1 */
 563             if (*int_term != numterms-1) /* if it wasn't last.. */
 564                 memmove(&e->terms[*int_term], &e->terms[*int_term+1],
 565                         (numterms-1-*int_term)*sizeof(yasm_expr__item));
 566
 567             /* Update numterms */
 568             numterms--;
 569             *int_term = -1;     /* no longer an int term */
 570         }
 571     }
 572     e->numterms = save_numterms;
 573
 574     /* Check for simple identites that delete everything BUT the intnum.
 575      * Don't bother if the intnum is the only thing in the expn.
 576      */
 577     if (numterms > 1 && *int_term != -1 &&
 578         expr_is_constant(e->op, e->terms[*int_term].data.intn)) {
 579         /* Loop through, deleting everything but the integer term */
 580         for (i=0; i<e->numterms; i++)
 581             if (i != *int_term)
 582                 expr_delete_term(&e->terms[i], 1);
 583
 584         /* Move integer term to the first term (if not already there) */
 585         if (*int_term != 0)
 586             e->terms[0] = e->terms[*int_term];  /* structure copy */
 587
 588         /* Set numterms to 1 */
 589         numterms = 1;
 590     }
 591
 592     /* Compute NOT, NEG, and LNOT on single intnum. */
 593     if (numterms == 1 && *int_term == 0 &&
 594         (e->op == YASM_EXPR_NOT || e->op == YASM_EXPR_NEG ||
 595          e->op == YASM_EXPR_LNOT))
 596         yasm_intnum_calc(e->terms[0].data.intn, e->op, NULL);
 597
 598     /* Change expression to IDENT if possible. */
 599     if (numterms == 1)
 600         e->op = YASM_EXPR_IDENT;
 601
 602     /* Return the updated numterms */
 603     return numterms;
 604 }
 605
 606 /* Levels the expression tree starting at e.  Eg:
 607  * a+(b+c) -> a+b+c
 608  * (a+b)+(c+d) -> a+b+c+d
 609  * Naturally, only levels operators that allow more than two operand terms.
 610  * NOTE: only does *one* level of leveling (no recursion).  Should be called
 611  *  post-order on a tree to combine deeper levels.
 612  * Also brings up any IDENT values into the current level (for ALL operators).
 613  * Folds (combines by evaluation) *integer* constant values if fold_const != 0.
 614  *
 615  * Returns a possibly reallocated e.
 616  */
 617 /*@-mustfree@*/
 618 static /*@only@*/ yasm_expr *
 619 expr_level_op(/*@returned@*/ /*@only@*/ yasm_expr *e, int fold_const,
 620               int simplify_ident, int simplify_reg_mul)
 621 {
 622     int i, j, o, fold_numterms, level_numterms, level_fold_numterms;
 623     int first_int_term = -1;
 624
 625     /* Determine how many operands will need to be brought up (for leveling).
 626      * Go ahead and bring up any IDENT'ed values.
 627      */
 628     while (e->op == YASM_EXPR_IDENT && e->terms[0].type == YASM_EXPR_EXPR) {
 629         yasm_expr *sube = e->terms[0].data.expn;
 630         yasm_xfree(e);
 631         e = sube;
 632     }
 633
 634     /* If non-numeric expression, don't fold constants. */
 635     if (e->op > YASM_EXPR_NONNUM)
 636         fold_const = 0;
 637
 638     level_numterms = e->numterms;
 639     level_fold_numterms = 0;
 640     for (i=0; i<e->numterms; i++) {
 641         /* Search downward until we find something *other* than an
 642          * IDENT, then bring it up to the current level.
 643          */
 644         while (e->terms[i].type == YASM_EXPR_EXPR &&
 645                e->terms[i].data.expn->op == YASM_EXPR_IDENT) {
 646             yasm_expr *sube = e->terms[i].data.expn;
 647             e->terms[i] = sube->terms[0];
 648             yasm_xfree(sube);
 649         }
 650
 651         if (e->terms[i].type == YASM_EXPR_EXPR &&
 652             e->terms[i].data.expn->op == e->op) {
 653                 /* It's an expression w/the same operator, add in its numterms.
 654                  * But don't forget to subtract one for the expr itself!
 655                  */
 656                 level_numterms += e->terms[i].data.expn->numterms - 1;
 657
 658                 /* If we're folding constants, count up the number of constants
 659                  * that will be merged in.
 660                  */
 661                 if (fold_const)
 662                     for (j=0; j<e->terms[i].data.expn->numterms; j++)
 663                         if (e->terms[i].data.expn->terms[j].type ==
 664                             YASM_EXPR_INT)
 665                             level_fold_numterms++;
 666         }
 667
 668         /* Find the first integer term (if one is present) if we're folding
 669          * constants.
 670          */
 671         if (fold_const && first_int_term == -1 &&
 672             e->terms[i].type == YASM_EXPR_INT)
 673             first_int_term = i;
 674     }
 675
 676     /* Look for other integer terms if there's one and combine.
 677      * Also eliminate empty spaces when combining and adjust numterms
 678      * variables.
 679      */
 680     fold_numterms = e->numterms;
 681     if (first_int_term != -1) {
 682         for (i=first_int_term+1, o=first_int_term+1; i<e->numterms; i++) {
 683             if (e->terms[i].type == YASM_EXPR_INT) {
 684                 yasm_intnum_calc(e->terms[first_int_term].data.intn, e->op,
 685                                  e->terms[i].data.intn);
 686                 fold_numterms--;
 687                 level_numterms--;
 688                 /* make sure to delete folded intnum */
 689                 yasm_intnum_destroy(e->terms[i].data.intn);
 690             } else if (o != i) {
 691                 /* copy term if it changed places */
 692                 e->terms[o++] = e->terms[i];
 693             } else
 694                 o++;
 695         }
 696
 697         if (simplify_ident) {
 698             int new_fold_numterms;
 699             /* Simplify identities and make IDENT if possible. */
 700             new_fold_numterms =
 701                 expr_simplify_identity(e, fold_numterms, &first_int_term,
 702                                        simplify_reg_mul);
 703             level_numterms -= fold_numterms-new_fold_numterms;
 704             fold_numterms = new_fold_numterms;
 705         }
 706         if (fold_numterms == 1)
 707             e->op = YASM_EXPR_IDENT;
 708     }
 709
 710     /* Only level operators that allow more than two operand terms.
 711      * Also don't bother leveling if it's not necessary to bring up any terms.
 712      */
 713     if ((e->op != YASM_EXPR_ADD && e->op != YASM_EXPR_MUL &&
 714          e->op != YASM_EXPR_OR && e->op != YASM_EXPR_AND &&
 715          e->op != YASM_EXPR_LOR && e->op != YASM_EXPR_LAND &&
 716          e->op != YASM_EXPR_LXOR && e->op != YASM_EXPR_XOR) ||
 717         level_numterms <= fold_numterms) {
 718         /* Downsize e if necessary */
 719         if (fold_numterms < e->numterms && e->numterms > 2)
 720             e = yasm_xrealloc(e, sizeof(yasm_expr)+((fold_numterms<2) ? 0 :
 721                               sizeof(yasm_expr__item)*(fold_numterms-2)));
 722         /* Update numterms */
 723         e->numterms = fold_numterms;
 724         return e;
 725     }
 726
 727     /* Adjust numterms for constant folding from terms being "pulled up".
 728      * Careful: if there's no integer term in e, then save space for it.
 729      */
 730     if (fold_const) {
 731         level_numterms -= level_fold_numterms;
 732         if (first_int_term == -1 && level_fold_numterms != 0)
 733             level_numterms++;
 734     }
 735
 736     /* Alloc more (or conceivably less, but not usually) space for e */
 737     e = yasm_xrealloc(e, sizeof(yasm_expr)+((level_numterms<2) ? 0 :
 738                       sizeof(yasm_expr__item)*(level_numterms-2)));
 739
 740     /* Copy up ExprItem's.  Iterate from right to left to keep the same
 741      * ordering as was present originally.
 742      * Combine integer terms as necessary.
 743      */
 744     for (i=fold_numterms-1, o=level_numterms-1; i>=0; i--) {
 745         if (e->terms[i].type == YASM_EXPR_EXPR &&
 746             e->terms[i].data.expn->op == e->op) {
 747             /* bring up subexpression */
 748             yasm_expr *sube = e->terms[i].data.expn;
 749
 750             /* copy terms right to left */
 751             for (j=sube->numterms-1; j>=0; j--) {
 752                 if (fold_const && sube->terms[j].type == YASM_EXPR_INT) {
 753                     /* Need to fold it in.. but if there's no int term already,
 754                      * just copy into a new one.
 755                      */
 756                     if (first_int_term == -1) {
 757                         first_int_term = o--;
 758                         e->terms[first_int_term] = sube->terms[j];  /* struc */
 759                     } else {
 760                         yasm_intnum_calc(e->terms[first_int_term].data.intn,
 761                                          e->op, sube->terms[j].data.intn);
 762                         /* make sure to delete folded intnum */
 763                         yasm_intnum_destroy(sube->terms[j].data.intn);
 764                     }
 765                 } else {
 766                     if (o == first_int_term)
 767                         o--;
 768                     e->terms[o--] = sube->terms[j];     /* structure copy */
 769                 }
 770             }
 771
 772             /* delete subexpression, but *don't delete nodes* (as we've just
 773              * copied them!)
 774              */
 775             yasm_xfree(sube);
 776         } else if (o != i) {
 777             /* copy operand if it changed places */
 778             if (o == first_int_term)
 779                 o--;
 780             e->terms[o] = e->terms[i];
 781             /* If we moved the first_int_term, change first_int_num too */
 782             if (i == first_int_term)
 783                 first_int_term = o;
 784             o--;
 785         } else
 786             o--;
 787     }
 788
 789     /* Simplify identities, make IDENT if possible, and save to e->numterms. */
 790     if (simplify_ident && first_int_term != -1) {
 791         e->numterms = expr_simplify_identity(e, level_numterms,
 792                                              &first_int_term, simplify_reg_mul);
 793     } else {
 794         e->numterms = level_numterms;
 795         if (level_numterms == 1)
 796             e->op = YASM_EXPR_IDENT;
 797     }
 798
 799     return e;
 800 }
 801 /*@=mustfree@*/
 802
 803 typedef SLIST_HEAD(yasm__exprhead, yasm__exprentry) yasm__exprhead;
 804 typedef struct yasm__exprentry {
 805     /*@reldef@*/ SLIST_ENTRY(yasm__exprentry) next;
 806     /*@null@*/ const yasm_expr *e;
 807 } yasm__exprentry;
 808
 809 static yasm_expr *
 810 expr_expand_equ(yasm_expr *e, yasm__exprhead *eh)
 811 {
 812     int i;
 813     yasm__exprentry ee;
 814
 815     /* traverse terms */
 816     for (i=0; i<e->numterms; i++) {
 817         const yasm_expr *equ_expr;
 818
 819         /* Expand equ's. */
 820         if (e->terms[i].type == YASM_EXPR_SYM &&
 821             (equ_expr = yasm_symrec_get_equ(e->terms[i].data.sym))) {
 822             yasm__exprentry *np;
 823
 824             /* Check for circular reference */
 825             SLIST_FOREACH(np, eh, next) {
 826                 if (np->e == equ_expr) {
 827                     yasm_error_set(YASM_ERROR_TOO_COMPLEX,
 828                                    N_("circular reference detected"));
 829                     return e;
 830                 }
 831             }
 832
 833             e->terms[i].type = YASM_EXPR_EXPR;
 834             e->terms[i].data.expn = yasm_expr_copy(equ_expr);
 835
 836             /* Remember we saw this equ and recurse */
 837             ee.e = equ_expr;
 838             SLIST_INSERT_HEAD(eh, &ee, next);
 839             e->terms[i].data.expn = expr_expand_equ(e->terms[i].data.expn, eh);
 840             SLIST_REMOVE_HEAD(eh, next);
 841         } else if (e->terms[i].type == YASM_EXPR_EXPR)
 842             /* Recurse */
 843             e->terms[i].data.expn = expr_expand_equ(e->terms[i].data.expn, eh);
 844     }
 845
 846     return e;
 847 }
 848
 849 static yasm_expr *
 850 expr_level_tree(yasm_expr *e, int fold_const, int simplify_ident,
 851                 int simplify_reg_mul, int calc_bc_dist,
 852                 yasm_expr_xform_func expr_xform_extra,
 853                 void *expr_xform_extra_data)
 854 {
 855     int i;
 856
 857     e = expr_xform_neg(e);
 858
 859     /* traverse terms */
 860     for (i=0; i<e->numterms; i++) {
 861         /* Recurse */
 862         if (e->terms[i].type == YASM_EXPR_EXPR)
 863             e->terms[i].data.expn =
 864                 expr_level_tree(e->terms[i].data.expn, fold_const,
 865                                 simplify_ident, simplify_reg_mul, calc_bc_dist,
 866                                 expr_xform_extra, expr_xform_extra_data);
 867     }
 868
 869     /* Check for SEG of SEG:OFF, if we match, simplify to just the segment */
 870     if (e->op == YASM_EXPR_SEG && e->terms[0].type == YASM_EXPR_EXPR &&
 871         e->terms[0].data.expn->op == YASM_EXPR_SEGOFF) {
 872         e->op = YASM_EXPR_IDENT;
 873         e->terms[0].data.expn->op = YASM_EXPR_IDENT;
 874         /* Destroy the second (offset) term */
 875         e->terms[0].data.expn->numterms = 1;
 876         expr_delete_term(&e->terms[0].data.expn->terms[1], 1);
 877     }
 878
 879     /* do callback */
 880     e = expr_level_op(e, fold_const, simplify_ident, simplify_reg_mul);
 881     if (calc_bc_dist || expr_xform_extra) {
 882         if (calc_bc_dist)
 883             e = expr_xform_bc_dist(e);
 884         if (expr_xform_extra)
 885             e = expr_xform_extra(e, expr_xform_extra_data);
 886         e = expr_level_tree(e, fold_const, simplify_ident, simplify_reg_mul,
 887                             0, NULL, NULL);
 888     }
 889     return e;
 890 }
 891
 892 /* Level an entire expn tree, expanding equ's as we go */
 893 yasm_expr *
 894 yasm_expr__level_tree(yasm_expr *e, int fold_const, int simplify_ident,
 895                       int simplify_reg_mul, int calc_bc_dist,
 896                       yasm_expr_xform_func expr_xform_extra,
 897                       void *expr_xform_extra_data)
 898 {
 899     yasm__exprhead eh;
 900     SLIST_INIT(&eh);
 901
 902     if (!e)
 903         return 0;
 904
 905     e = expr_expand_equ(e, &eh);
 906     e = expr_level_tree(e, fold_const, simplify_ident, simplify_reg_mul,
 907                         calc_bc_dist, expr_xform_extra, expr_xform_extra_data);
 908
 909     return e;
 910 }
 911
 912 /* Comparison function for expr_order_terms().
 913  * Assumes ExprType enum is in canonical order.
 914  */
 915 static int
 916 expr_order_terms_compare(const void *va, const void *vb)
 917 {
 918     const yasm_expr__item *a = va, *b = vb;
 919     return (a->type - b->type);
 920 }
 921
 922 /* Reorder terms of e into canonical order.  Only reorders if reordering
 923  * doesn't change meaning of expression.  (eg, doesn't reorder SUB).
 924  * Canonical order: REG, INT, FLOAT, SYM, EXPR.
 925  * Multiple terms of a single type are kept in the same order as in
 926  * the original expression.
 927  * NOTE: Only performs reordering on *one* level (no recursion).
 928  */
 929 void
 930 yasm_expr__order_terms(yasm_expr *e)
 931 {
 932     /* don't bother reordering if only one element */
 933     if (e->numterms == 1)
 934         return;
 935
 936     /* only reorder some types of operations */
 937     switch (e->op) {
 938         case YASM_EXPR_ADD:
 939         case YASM_EXPR_MUL:
 940         case YASM_EXPR_OR:
 941         case YASM_EXPR_AND:
 942         case YASM_EXPR_XOR:
 943         case YASM_EXPR_LOR:
 944         case YASM_EXPR_LAND:
 945         case YASM_EXPR_LXOR:
 946             /* Use mergesort to sort.  It's fast on already sorted values and a
 947              * stable sort (multiple terms of same type are kept in the same
 948              * order).
 949              */
 950             yasm__mergesort(e->terms, (size_t)e->numterms,
 951                             sizeof(yasm_expr__item), expr_order_terms_compare);
 952             break;
 953         default:
 954             break;
 955     }
 956 }
 957
 958 static void
 959 expr_item_copy(yasm_expr__item *dest, const yasm_expr__item *src)
 960 {
 961     dest->type = src->type;
 962     switch (src->type) {
 963         case YASM_EXPR_SYM:
 964             /* Symbols don't need to be copied */
 965             dest->data.sym = src->data.sym;
 966             break;
 967         case YASM_EXPR_PRECBC:
 968             /* Nor do direct bytecode references */
 969             dest->data.precbc = src->data.precbc;
 970             break;
 971         case YASM_EXPR_EXPR:
 972             dest->data.expn = yasm_expr__copy_except(src->data.expn, -1);
 973             break;
 974         case YASM_EXPR_INT:
 975             dest->data.intn = yasm_intnum_copy(src->data.intn);
 976             break;
 977         case YASM_EXPR_FLOAT:
 978             dest->data.flt = yasm_floatnum_copy(src->data.flt);
 979             break;
 980         case YASM_EXPR_REG:
 981             dest->data.reg = src->data.reg;
 982             break;
 983         case YASM_EXPR_SUBST:
 984             dest->data.subst = src->data.subst;
 985             break;
 986         default:
 987             break;
 988     }
 989 }
 990
 991 /* Copy entire expression EXCEPT for index "except" at *top level only*. */
 992 yasm_expr *
 993 yasm_expr__copy_except(const yasm_expr *e, int except)
 994 {
 995     yasm_expr *n;
 996     int i;
 997
 998     n = yasm_xmalloc(sizeof(yasm_expr) +
 999                      sizeof(yasm_expr__item)*(e->numterms<2?0:e->numterms-2));
1000
1001     n->op = e->op;
1002     n->line = e->line;
1003     n->numterms = e->numterms;
1004     for (i=0; i<e->numterms; i++) {
1005         if (i != except)
1006             expr_item_copy(&n->terms[i], &e->terms[i]);
1007     }
1008
1009     return n;
1010 }
1011
1012 static void
1013 expr_delete_term(yasm_expr__item *term, int recurse)
1014 {
1015     switch (term->type) {
1016         case YASM_EXPR_INT:
1017             yasm_intnum_destroy(term->data.intn);
1018             break;
1019         case YASM_EXPR_FLOAT:
1020             yasm_floatnum_destroy(term->data.flt);
1021             break;
1022         case YASM_EXPR_EXPR:
1023             if (recurse)
1024                 yasm_expr_destroy(term->data.expn);
1025             break;
1026         default:
1027             break;
1028     }
1029 }
1030
1031 static int
1032 expr_destroy_each(/*@only@*/ yasm_expr *e, /*@unused@*/ void *d)
1033 {
1034     int i;
1035     for (i=0; i<e->numterms; i++)
1036         expr_delete_term(&e->terms[i], 0);
1037     yasm_xfree(e);      /* free ourselves */
1038     return 0;   /* don't stop recursion */
1039 }
1040
1041 /*@-mustfree@*/
1042 void
1043 yasm_expr_destroy(yasm_expr *e)
1044 {
1045     expr_traverse_nodes_post(e, NULL, expr_destroy_each);
1046 }
1047 /*@=mustfree@*/
1048
1049 int
1050 yasm_expr_is_op(const yasm_expr *e, yasm_expr_op op)
1051 {
1052     return (e->op == op);
1053 }
1054
1055 static int
1056 expr_contains_callback(const yasm_expr__item *ei, void *d)
1057 {
1058     yasm_expr__type *t = d;
1059     return (ei->type & *t);
1060 }
1061
1062 int
1063 yasm_expr__contains(const yasm_expr *e, yasm_expr__type t)
1064 {
1065     return yasm_expr__traverse_leaves_in_const(e, &t, expr_contains_callback);
1066 }
1067
1068 typedef struct subst_cbd {
1069     unsigned int num_items;
1070     const yasm_expr__item *items;
1071 } subst_cbd;
1072
1073 static int
1074 expr_subst_callback(yasm_expr__item *ei, void *d)
1075 {
1076     subst_cbd *cbd = d;
1077     if (ei->type != YASM_EXPR_SUBST)
1078         return 0;
1079     if (ei->data.subst >= cbd->num_items)
1080         return 1;   /* error */
1081     expr_item_copy(ei, &cbd->items[ei->data.subst]);
1082     return 0;
1083 }
1084
1085 int
1086 yasm_expr__subst(yasm_expr *e, unsigned int num_items,
1087                  const yasm_expr__item *items)
1088 {
1089     subst_cbd cbd;
1090     cbd.num_items = num_items;
1091     cbd.items = items;
1092     return yasm_expr__traverse_leaves_in(e, &cbd, expr_subst_callback);
1093 }
1094
1095 /* Traverse over expression tree, calling func for each operation AFTER the
1096  * branches (if expressions) have been traversed (eg, postorder
1097  * traversal).  The data pointer d is passed to each func call.
1098  *
1099  * Stops early (and returns 1) if func returns 1.  Otherwise returns 0.
1100  */
1101 static int
1102 expr_traverse_nodes_post(yasm_expr *e, void *d,
1103                          int (*func) (/*@null@*/ yasm_expr *e,
1104                                       /*@null@*/ void *d))
1105 {
1106     int i;
1107
1108     if (!e)
1109         return 0;
1110
1111     /* traverse terms */
1112     for (i=0; i<e->numterms; i++) {
1113         if (e->terms[i].type == YASM_EXPR_EXPR &&
1114             expr_traverse_nodes_post(e->terms[i].data.expn, d, func))
1115             return 1;
1116     }
1117
1118     /* do callback */
1119     return func(e, d);
1120 }
1121
1122 /* Traverse over expression tree in order, calling func for each leaf
1123  * (non-operation).  The data pointer d is passed to each func call.
1124  *
1125  * Stops early (and returns 1) if func returns 1.  Otherwise returns 0.
1126  */
1127 int
1128 yasm_expr__traverse_leaves_in_const(const yasm_expr *e, void *d,
1129     int (*func) (/*@null@*/ const yasm_expr__item *ei, /*@null@*/ void *d))
1130 {
1131     int i;
1132
1133     if (!e)
1134         return 0;
1135
1136     for (i=0; i<e->numterms; i++) {
1137         if (e->terms[i].type == YASM_EXPR_EXPR) {
1138             if (yasm_expr__traverse_leaves_in_const(e->terms[i].data.expn, d,
1139                                                     func))
1140                 return 1;
1141         } else {
1142             if (func(&e->terms[i], d))
1143                 return 1;
1144         }
1145     }
1146     return 0;
1147 }
1148
1149 /* Traverse over expression tree in order, calling func for each leaf
1150  * (non-operation).  The data pointer d is passed to each func call.
1151  *
1152  * Stops early (and returns 1) if func returns 1.  Otherwise returns 0.
1153  */
1154 int
1155 yasm_expr__traverse_leaves_in(yasm_expr *e, void *d,
1156     int (*func) (/*@null@*/ yasm_expr__item *ei, /*@null@*/ void *d))
1157 {
1158     int i;
1159
1160     if (!e)
1161         return 0;
1162
1163     for (i=0; i<e->numterms; i++) {
1164         if (e->terms[i].type == YASM_EXPR_EXPR) {
1165             if (yasm_expr__traverse_leaves_in(e->terms[i].data.expn, d, func))
1166                 return 1;
1167         } else {
1168             if (func(&e->terms[i], d))
1169                 return 1;
1170         }
1171     }
1172     return 0;
1173 }
1174
1175 yasm_expr *
1176 yasm_expr_extract_deep_segoff(yasm_expr **ep)
1177 {
1178     yasm_expr *retval;
1179     yasm_expr *e = *ep;
1180     int i;
1181
1182     /* Try to extract at this level */
1183     retval = yasm_expr_extract_segoff(ep);
1184     if (retval)
1185         return retval;
1186
1187     /* Not at this level?  Search any expr children. */
1188     for (i=0; i<e->numterms; i++) {
1189         if (e->terms[i].type == YASM_EXPR_EXPR) {
1190             retval = yasm_expr_extract_deep_segoff(&e->terms[i].data.expn);
1191             if (retval)
1192                 return retval;
1193         }
1194     }
1195
1196     /* Didn't find one */
1197     return NULL;
1198 }
1199
1200 yasm_expr *
1201 yasm_expr_extract_segoff(yasm_expr **ep)
1202 {
1203     yasm_expr *retval;
1204     yasm_expr *e = *ep;
1205
1206     /* If not SEG:OFF, we can't do this transformation */
1207     if (e->op != YASM_EXPR_SEGOFF)
1208         return NULL;
1209
1210     /* Extract the SEG portion out to its own expression */
1211     if (e->terms[0].type == YASM_EXPR_EXPR)
1212         retval = e->terms[0].data.expn;
1213     else {
1214         /* Need to build IDENT expression to hold non-expression contents */
1215         retval = yasm_xmalloc(sizeof(yasm_expr));
1216         retval->op = YASM_EXPR_IDENT;
1217         retval->numterms = 1;
1218         retval->terms[0] = e->terms[0]; /* structure copy */
1219     }
1220
1221     /* Delete the SEG: portion by changing the expression into an IDENT */
1222     e->op = YASM_EXPR_IDENT;
1223     e->numterms = 1;
1224     e->terms[0] = e->terms[1];  /* structure copy */
1225
1226     return retval;
1227 }
1228
1229 yasm_expr *
1230 yasm_expr_extract_wrt(yasm_expr **ep)
1231 {
1232     yasm_expr *retval;
1233     yasm_expr *e = *ep;
1234
1235     /* If not WRT, we can't do this transformation */
1236     if (e->op != YASM_EXPR_WRT)
1237         return NULL;
1238
1239     /* Extract the right side portion out to its own expression */
1240     if (e->terms[1].type == YASM_EXPR_EXPR)
1241         retval = e->terms[1].data.expn;
1242     else {
1243         /* Need to build IDENT expression to hold non-expression contents */
1244         retval = yasm_xmalloc(sizeof(yasm_expr));
1245         retval->op = YASM_EXPR_IDENT;
1246         retval->numterms = 1;
1247         retval->terms[0] = e->terms[1]; /* structure copy */
1248     }
1249
1250     /* Delete the right side portion by changing the expr into an IDENT */
1251     e->op = YASM_EXPR_IDENT;
1252     e->numterms = 1;
1253
1254     return retval;
1255 }
1256
1257 /*@-unqualifiedtrans -nullderef -nullstate -onlytrans@*/
1258 yasm_intnum *
1259 yasm_expr_get_intnum(yasm_expr **ep, int calc_bc_dist)
1260 {
1261     *ep = yasm_expr_simplify(*ep, calc_bc_dist);
1262
1263     if ((*ep)->op == YASM_EXPR_IDENT && (*ep)->terms[0].type == YASM_EXPR_INT)
1264         return (*ep)->terms[0].data.intn;
1265     else
1266         return (yasm_intnum *)NULL;
1267 }
1268 /*@=unqualifiedtrans =nullderef -nullstate -onlytrans@*/
1269
1270 /*@-unqualifiedtrans -nullderef -nullstate -onlytrans@*/
1271 const yasm_symrec *
1272 yasm_expr_get_symrec(yasm_expr **ep, int simplify)
1273 {
1274     if (simplify)
1275         *ep = yasm_expr_simplify(*ep, 0);
1276
1277     if ((*ep)->op == YASM_EXPR_IDENT && (*ep)->terms[0].type == YASM_EXPR_SYM)
1278         return (*ep)->terms[0].data.sym;
1279     else
1280         return (yasm_symrec *)NULL;
1281 }
1282 /*@=unqualifiedtrans =nullderef -nullstate -onlytrans@*/
1283
1284 /*@-unqualifiedtrans -nullderef -nullstate -onlytrans@*/
1285 const uintptr_t *
1286 yasm_expr_get_reg(yasm_expr **ep, int simplify)
1287 {
1288     if (simplify)
1289         *ep = yasm_expr_simplify(*ep, 0);
1290
1291     if ((*ep)->op == YASM_EXPR_IDENT && (*ep)->terms[0].type == YASM_EXPR_REG)
1292         return &((*ep)->terms[0].data.reg);
1293     else
1294         return NULL;
1295 }
1296 /*@=unqualifiedtrans =nullderef -nullstate -onlytrans@*/
1297
1298 void
1299 yasm_expr_print(const yasm_expr *e, FILE *f)
1300 {
1301     char opstr[8];
1302     int i;
1303
1304     if (!e) {
1305         fprintf(f, "(nil)");
1306         return;
1307     }
1308
1309     switch (e->op) {
1310         case YASM_EXPR_ADD:
1311             strcpy(opstr, "+");
1312             break;
1313         case YASM_EXPR_SUB:
1314             strcpy(opstr, "-");
1315             break;
1316         case YASM_EXPR_MUL:
1317             strcpy(opstr, "*");
1318             break;
1319         case YASM_EXPR_DIV:
1320             strcpy(opstr, "/");
1321             break;
1322         case YASM_EXPR_SIGNDIV:
1323             strcpy(opstr, "//");
1324             break;
1325         case YASM_EXPR_MOD:
1326             strcpy(opstr, "%");
1327             break;
1328         case YASM_EXPR_SIGNMOD:
1329             strcpy(opstr, "%%");
1330             break;
1331         case YASM_EXPR_NEG:
1332             fprintf(f, "-");
1333             opstr[0] = 0;
1334             break;
1335         case YASM_EXPR_NOT:
1336             fprintf(f, "~");
1337             opstr[0] = 0;
1338             break;
1339         case YASM_EXPR_OR:
1340             strcpy(opstr, "|");
1341             break;
1342         case YASM_EXPR_AND:
1343             strcpy(opstr, "&");
1344             break;
1345         case YASM_EXPR_XOR:
1346             strcpy(opstr, "^");
1347             break;
1348         case YASM_EXPR_XNOR:
1349             strcpy(opstr, "XNOR");
1350             break;
1351         case YASM_EXPR_NOR:
1352             strcpy(opstr, "NOR");
1353             break;
1354         case YASM_EXPR_SHL:
1355             strcpy(opstr, "<<");
1356             break;
1357         case YASM_EXPR_SHR:
1358             strcpy(opstr, ">>");
1359             break;
1360         case YASM_EXPR_LOR:
1361             strcpy(opstr, "||");
1362             break;
1363         case YASM_EXPR_LAND:
1364             strcpy(opstr, "&&");
1365             break;
1366         case YASM_EXPR_LNOT:
1367             strcpy(opstr, "!");
1368             break;
1369         case YASM_EXPR_LXOR:
1370             strcpy(opstr, "^^");
1371             break;
1372         case YASM_EXPR_LXNOR:
1373             strcpy(opstr, "LXNOR");
1374             break;
1375         case YASM_EXPR_LNOR:
1376             strcpy(opstr, "LNOR");
1377             break;
1378         case YASM_EXPR_LT:
1379             strcpy(opstr, "<");
1380             break;
1381         case YASM_EXPR_GT:
1382             strcpy(opstr, ">");
1383             break;
1384         case YASM_EXPR_LE:
1385             strcpy(opstr, "<=");
1386             break;
1387         case YASM_EXPR_GE:
1388             strcpy(opstr, ">=");
1389             break;
1390         case YASM_EXPR_NE:
1391             strcpy(opstr, "!=");
1392             break;
1393         case YASM_EXPR_EQ:
1394             strcpy(opstr, "==");
1395             break;
1396         case YASM_EXPR_SEG:
1397             fprintf(f, "SEG ");
1398             opstr[0] = 0;
1399             break;
1400         case YASM_EXPR_WRT:
1401             strcpy(opstr, " WRT ");
1402             break;
1403         case YASM_EXPR_SEGOFF:
1404             strcpy(opstr, ":");
1405             break;
1406         case YASM_EXPR_IDENT:
1407             opstr[0] = 0;
1408             break;
1409         default:
1410             strcpy(opstr, " !UNK! ");
1411             break;
1412     }
1413     for (i=0; i<e->numterms; i++) {
1414         switch (e->terms[i].type) {
1415             case YASM_EXPR_PRECBC:
1416                 fprintf(f, "{%lx}",
1417                         yasm_bc_next_offset(e->terms[i].data.precbc));
1418                 break;
1419             case YASM_EXPR_SYM:
1420                 fprintf(f, "%s", yasm_symrec_get_name(e->terms[i].data.sym));
1421                 break;
1422             case YASM_EXPR_EXPR:
1423                 fprintf(f, "(");
1424                 yasm_expr_print(e->terms[i].data.expn, f);
1425                 fprintf(f, ")");
1426                 break;
1427             case YASM_EXPR_INT:
1428                 yasm_intnum_print(e->terms[i].data.intn, f);
1429                 break;
1430             case YASM_EXPR_FLOAT:
1431                 yasm_floatnum_print(e->terms[i].data.flt, f);
1432                 break;
1433             case YASM_EXPR_REG:
1434                 /* FIXME */
1435                 /*yasm_arch_reg_print(arch, e->terms[i].data.reg, f);*/
1436                 break;
1437             case YASM_EXPR_SUBST:
1438                 fprintf(f, "[%u]", e->terms[i].data.subst);
1439                 break;
1440             case YASM_EXPR_NONE:
1441                 break;
1442         }
1443         if (i < e->numterms-1)
1444             fprintf(f, "%s", opstr);
1445     }
1446 }
1447
1448 unsigned int
1449 yasm_expr_size(const yasm_expr *e)
1450 {
1451     int i;
1452     int seen = 0;
1453     unsigned int size = 0, newsize;
1454
1455     if (e->op == YASM_EXPR_IDENT) {
1456         if (e->terms[0].type == YASM_EXPR_SYM)
1457             return yasm_symrec_get_size(e->terms[0].data.sym);
1458         return 0;
1459     }
1460     if (e->op != YASM_EXPR_ADD && e->op != YASM_EXPR_SUB)
1461         return 0;
1462
1463     for (i=0; i<e->numterms; i++) {
1464         newsize = 0;
1465         switch (e->terms[i].type) {
1466         case YASM_EXPR_EXPR:
1467             newsize = yasm_expr_size(e->terms[i].data.expn);
1468             break;
1469         case YASM_EXPR_SYM:
1470             newsize = yasm_symrec_get_size(e->terms[i].data.sym);
1471             break;
1472         default:
1473             break;
1474         }
1475         if (newsize) {
1476             size = newsize;
1477             if (seen)
1478                 /* either sum of idents (?!) or substract of idents */
1479                 return 0;
1480             seen = 1;
1481         }
1482     }
1483     /* exactly one offset */
1484     return size;
1485 }
1486
1487 const char *
1488 yasm_expr_segment(const yasm_expr *e)
1489 {
1490     int i;
1491     int seen = 0;
1492     const char *segment = NULL;
1493
1494     if (e->op == YASM_EXPR_IDENT) {
1495         if (e->terms[0].type == YASM_EXPR_SYM)
1496             return yasm_symrec_get_segment(e->terms[0].data.sym);
1497         return NULL;
1498     }
1499     if (e->op != YASM_EXPR_ADD && e->op != YASM_EXPR_SUB)
1500         return NULL;
1501
1502     for (i=0; i<e->numterms; i++) {
1503         if ((e->op == YASM_EXPR_ADD || !i) &&
1504                 e->terms[i].type == YASM_EXPR_EXPR) {
1505             if ((segment = yasm_expr_segment(e->terms[i].data.expn))) {
1506                 if (seen) {
1507                     /* either sum of idents (?!) or substract of idents */
1508                     return NULL;
1509                 }
1510                 seen = 1;
1511             }
1512         }
1513     }
1514     /* exactly one offset */
1515     return segment;
1516 }