1 /*
   2  * sparse/expand.c
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *               2003-2004 Linus Torvalds
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  * expand constant expressions.
  26  */
  27 #include <stdlib.h>
  28 #include <stdarg.h>
  29 #include <stddef.h>
  30 #include <stdio.h>
  31 #include <string.h>
  32 #include <ctype.h>
  33 #include <unistd.h>
  34 #include <fcntl.h>
  35 #include <limits.h>
  36 
  37 #include "lib.h"
  38 #include "allocate.h"
  39 #include "parse.h"
  40 #include "token.h"
  41 #include "symbol.h"
  42 #include "target.h"
  43 #include "expression.h"
  44 #include "expand.h"
  45 
  46 
  47 static int expand_expression(struct expression *);
  48 static int expand_statement(struct statement *);
  49 static int conservative;
  50 
  51 static int expand_symbol_expression(struct expression *expr)
  52 {
  53         struct symbol *sym = expr->symbol;
  54 
  55         if (sym == &zero_int) {
  56                 if (Wundef)
  57                         warning(expr->pos, "undefined preprocessor identifier '%s'", show_ident(expr->symbol_name));
  58                 expr->type = EXPR_VALUE;
  59                 expr->value = 0;
  60                 expr->taint = 0;
  61                 return 0;
  62         }
  63         /* The cost of a symbol expression is lower for on-stack symbols */
  64         return (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN)) ? 2 : 1;
  65 }
  66 
  67 static long long get_longlong(struct expression *expr)
  68 {
  69         int no_expand = expr->ctype->ctype.modifiers & MOD_UNSIGNED;
  70         long long mask = 1ULL << (expr->ctype->bit_size - 1);
  71         long long value = expr->value;
  72         long long ormask, andmask;
  73 
  74         if (!(value & mask))
  75                 no_expand = 1;
  76         andmask = mask | (mask-1);
  77         ormask = ~andmask;
  78         if (no_expand)
  79                 ormask = 0;
  80         return (value & andmask) | ormask;
  81 }
  82 
  83 void cast_value(struct expression *expr, struct symbol *newtype,
  84                 struct expression *old, struct symbol *oldtype)
  85 {
  86         int old_size = oldtype->bit_size;
  87         int new_size = newtype->bit_size;
  88         long long value, mask, signmask;
  89         long long oldmask, oldsignmask, dropped;
  90 
  91         if (is_float_type(newtype) || is_float_type(oldtype))
  92                 goto Float;
  93 
  94         // For pointers and integers, we can just move the value around
  95         expr->type = EXPR_VALUE;
  96         expr->taint = old->taint;
  97         if (old_size == new_size) {
  98                 expr->value = old->value;
  99                 return;
 100         }
 101 
 102         // expand it to the full "long long" value
 103         value = get_longlong(old);
 104 
 105 Int:
 106         // _Bool requires a zero test rather than truncation.
 107         if (is_bool_type(newtype)) {
 108                 expr->value = !!value;
 109                 if (!conservative && value != 0 && value != 1)
 110                         warning(old->pos, "odd constant _Bool cast (%llx becomes 1)", value);
 111                 return;
 112         }
 113 
 114         // Truncate it to the new size
 115         signmask = 1ULL << (new_size-1);
 116         mask = signmask | (signmask-1);
 117         expr->value = value & mask;
 118 
 119         // Stop here unless checking for truncation
 120         if (!Wcast_truncate || conservative)
 121                 return;
 122         
 123         // Check if we dropped any bits..
 124         oldsignmask = 1ULL << (old_size-1);
 125         oldmask = oldsignmask | (oldsignmask-1);
 126         dropped = oldmask & ~mask;
 127 
 128         // OK if the bits were (and still are) purely sign bits
 129         if (value & dropped) {
 130                 if (!(value & oldsignmask) || !(value & signmask) || (value & dropped) != dropped)
 131                         warning(old->pos, "cast truncates bits from constant value (%llx becomes %llx)",
 132                                 value & oldmask,
 133                                 value & mask);
 134         }
 135         return;
 136 
 137 Float:
 138         if (!is_float_type(newtype)) {
 139                 value = (long long)old->fvalue;
 140                 expr->type = EXPR_VALUE;
 141                 expr->taint = 0;
 142                 goto Int;
 143         }
 144 
 145         if (!is_float_type(oldtype))
 146                 expr->fvalue = (long double)get_longlong(old);
 147         else
 148                 expr->fvalue = old->fvalue;
 149 
 150         if (!(newtype->ctype.modifiers & MOD_LONGLONG) && \
 151             !(newtype->ctype.modifiers & MOD_LONGLONGLONG)) {
 152                 if ((newtype->ctype.modifiers & MOD_LONG))
 153                         expr->fvalue = (double)expr->fvalue;
 154                 else
 155                         expr->fvalue = (float)expr->fvalue;
 156         }
 157         expr->type = EXPR_FVALUE;
 158 }
 159 
 160 static int check_shift_count(struct expression *expr, struct symbol *ctype, unsigned int count)
 161 {
 162         warning(expr->pos, "shift too big (%u) for type %s", count, show_typename(ctype));
 163         count &= ctype->bit_size-1;
 164         return count;
 165 }
 166 
 167 /*
 168  * CAREFUL! We need to get the size and sign of the
 169  * result right!
 170  */
 171 #define CONVERT(op,s)   (((op)<<1)+(s))
 172 #define SIGNED(op)      CONVERT(op, 1)
 173 #define UNSIGNED(op)    CONVERT(op, 0)
 174 static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
 175 {
 176         struct expression *left = expr->left, *right = expr->right;
 177         unsigned long long v, l, r, mask;
 178         signed long long sl, sr;
 179         int is_signed;
 180 
 181         if (right->type != EXPR_VALUE)
 182                 return 0;
 183         r = right->value;
 184         if (expr->op == SPECIAL_LEFTSHIFT || expr->op == SPECIAL_RIGHTSHIFT) {
 185                 if (r >= ctype->bit_size) {
 186                         if (conservative)
 187                                 return 0;
 188                         r = check_shift_count(expr, ctype, r);
 189                         right->value = r;
 190                 }
 191         }
 192         if (left->type != EXPR_VALUE)
 193                 return 0;
 194         l = left->value; r = right->value;
 195         is_signed = !(ctype->ctype.modifiers & MOD_UNSIGNED);
 196         mask = 1ULL << (ctype->bit_size-1);
 197         sl = l; sr = r;
 198         if (is_signed && (sl & mask))
 199                 sl |= ~(mask-1);
 200         if (is_signed && (sr & mask))
 201                 sr |= ~(mask-1);
 202         
 203         switch (CONVERT(expr->op,is_signed)) {
 204         case SIGNED('+'):
 205         case UNSIGNED('+'):
 206                 v = l + r;
 207                 break;
 208 
 209         case SIGNED('-'):
 210         case UNSIGNED('-'):
 211                 v = l - r;
 212                 break;
 213 
 214         case SIGNED('&'):
 215         case UNSIGNED('&'):
 216                 v = l & r;
 217                 break;
 218 
 219         case SIGNED('|'):
 220         case UNSIGNED('|'):
 221                 v = l | r;
 222                 break;
 223 
 224         case SIGNED('^'):
 225         case UNSIGNED('^'):
 226                 v = l ^ r;
 227                 break;
 228 
 229         case SIGNED('*'):
 230                 v = sl * sr;
 231                 break;
 232 
 233         case UNSIGNED('*'):
 234                 v = l * r;
 235                 break;
 236 
 237         case SIGNED('/'):
 238                 if (!r)
 239                         goto Div;
 240                 if (l == mask && sr == -1)
 241                         goto Overflow;
 242                 v = sl / sr;
 243                 break;
 244 
 245         case UNSIGNED('/'):
 246                 if (!r) goto Div;
 247                 v = l / r; 
 248                 break;
 249 
 250         case SIGNED('%'):
 251                 if (!r)
 252                         goto Div;
 253                 if (l == mask && sr == -1)
 254                         goto Overflow;
 255                 v = sl % sr;
 256                 break;
 257 
 258         case UNSIGNED('%'):
 259                 if (!r) goto Div;
 260                 v = l % r;
 261                 break;
 262 
 263         case SIGNED(SPECIAL_LEFTSHIFT):
 264         case UNSIGNED(SPECIAL_LEFTSHIFT):
 265                 v = l << r;
 266                 break; 
 267 
 268         case SIGNED(SPECIAL_RIGHTSHIFT):
 269                 v = sl >> r;
 270                 break;
 271 
 272         case UNSIGNED(SPECIAL_RIGHTSHIFT):
 273                 v = l >> r;
 274                 break;
 275 
 276         default:
 277                 return 0;
 278         }
 279         mask = mask | (mask-1);
 280         expr->value = v & mask;
 281         expr->type = EXPR_VALUE;
 282         expr->taint = left->taint | right->taint;
 283         return 1;
 284 Div:
 285         if (!conservative)
 286                 warning(expr->pos, "division by zero");
 287         return 0;
 288 Overflow:
 289         if (!conservative)
 290                 warning(expr->pos, "constant integer operation overflow");
 291         return 0;
 292 }
 293 
 294 static int simplify_cmp_binop(struct expression *expr, struct symbol *ctype)
 295 {
 296         struct expression *left = expr->left, *right = expr->right;
 297         unsigned long long l, r, mask;
 298         signed long long sl, sr;
 299 
 300         if (left->type != EXPR_VALUE || right->type != EXPR_VALUE)
 301                 return 0;
 302         l = left->value; r = right->value;
 303         mask = 1ULL << (ctype->bit_size-1);
 304         sl = l; sr = r;
 305         if (sl & mask)
 306                 sl |= ~(mask-1);
 307         if (sr & mask)
 308                 sr |= ~(mask-1);
 309         switch (expr->op) {
 310         case '<':            expr->value = sl < sr; break;
 311         case '>':            expr->value = sl > sr; break;
 312         case SPECIAL_LTE:       expr->value = sl <= sr; break;
 313         case SPECIAL_GTE:       expr->value = sl >= sr; break;
 314         case SPECIAL_EQUAL:     expr->value = l == r; break;
 315         case SPECIAL_NOTEQUAL:  expr->value = l != r; break;
 316         case SPECIAL_UNSIGNED_LT:expr->value = l < r; break;
 317         case SPECIAL_UNSIGNED_GT:expr->value = l > r; break;
 318         case SPECIAL_UNSIGNED_LTE:expr->value = l <= r; break;
 319         case SPECIAL_UNSIGNED_GTE:expr->value = l >= r; break;
 320         }
 321         expr->type = EXPR_VALUE;
 322         expr->taint = left->taint | right->taint;
 323         return 1;
 324 }
 325 
 326 static int simplify_float_binop(struct expression *expr)
 327 {
 328         struct expression *left = expr->left, *right = expr->right;
 329         unsigned long mod = expr->ctype->ctype.modifiers;
 330         long double l, r, res;
 331 
 332         if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE)
 333                 return 0;
 334 
 335         l = left->fvalue;
 336         r = right->fvalue;
 337 
 338         if (mod & MOD_LONGLONG) {
 339                 switch (expr->op) {
 340                 case '+':       res = l + r; break;
 341                 case '-':       res = l - r; break;
 342                 case '*':       res = l * r; break;
 343                 case '/':       if (!r) goto Div;
 344                                 res = l / r; break;
 345                 default: return 0;
 346                 }
 347         } else if (mod & MOD_LONG) {
 348                 switch (expr->op) {
 349                 case '+':       res = (double) l + (double) r; break;
 350                 case '-':       res = (double) l - (double) r; break;
 351                 case '*':       res = (double) l * (double) r; break;
 352                 case '/':       if (!r) goto Div;
 353                                 res = (double) l / (double) r; break;
 354                 default: return 0;
 355                 }
 356         } else {
 357                 switch (expr->op) {
 358                 case '+':       res = (float)l + (float)r; break;
 359                 case '-':       res = (float)l - (float)r; break;
 360                 case '*':       res = (float)l * (float)r; break;
 361                 case '/':       if (!r) goto Div;
 362                                 res = (float)l / (float)r; break;
 363                 default: return 0;
 364                 }
 365         }
 366         expr->type = EXPR_FVALUE;
 367         expr->fvalue = res;
 368         return 1;
 369 Div:
 370         if (!conservative)
 371                 warning(expr->pos, "division by zero");
 372         return 0;
 373 }
 374 
 375 static int simplify_float_cmp(struct expression *expr, struct symbol *ctype)
 376 {
 377         struct expression *left = expr->left, *right = expr->right;
 378         long double l, r;
 379 
 380         if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE)
 381                 return 0;
 382 
 383         l = left->fvalue;
 384         r = right->fvalue;
 385         switch (expr->op) {
 386         case '<':            expr->value = l < r; break;
 387         case '>':            expr->value = l > r; break;
 388         case SPECIAL_LTE:       expr->value = l <= r; break;
 389         case SPECIAL_GTE:       expr->value = l >= r; break;
 390         case SPECIAL_EQUAL:     expr->value = l == r; break;
 391         case SPECIAL_NOTEQUAL:  expr->value = l != r; break;
 392         }
 393         expr->type = EXPR_VALUE;
 394         expr->taint = 0;
 395         return 1;
 396 }
 397 
 398 static int expand_binop(struct expression *expr)
 399 {
 400         int cost;
 401 
 402         cost = expand_expression(expr->left);
 403         cost += expand_expression(expr->right);
 404         if (simplify_int_binop(expr, expr->ctype))
 405                 return 0;
 406         if (simplify_float_binop(expr))
 407                 return 0;
 408         return cost + 1;
 409 }
 410 
 411 static int expand_logical(struct expression *expr)
 412 {
 413         struct expression *left = expr->left;
 414         struct expression *right;
 415         int cost, rcost;
 416 
 417         /* Do immediate short-circuiting ... */
 418         cost = expand_expression(left);
 419         if (left->type == EXPR_VALUE) {
 420                 if (expr->op == SPECIAL_LOGICAL_AND) {
 421                         if (!left->value) {
 422                                 expr->type = EXPR_VALUE;
 423                                 expr->value = 0;
 424                                 expr->taint = left->taint;
 425                                 return 0;
 426                         }
 427                 } else {
 428                         if (left->value) {
 429                                 expr->type = EXPR_VALUE;
 430                                 expr->value = 1;
 431                                 expr->taint = left->taint;
 432                                 return 0;
 433                         }
 434                 }
 435         }
 436 
 437         right = expr->right;
 438         rcost = expand_expression(right);
 439         if (left->type == EXPR_VALUE && right->type == EXPR_VALUE) {
 440                 /*
 441                  * We know the left value doesn't matter, since
 442                  * otherwise we would have short-circuited it..
 443                  */
 444                 expr->type = EXPR_VALUE;
 445                 expr->value = right->value != 0;
 446                 expr->taint = left->taint | right->taint;
 447                 return 0;
 448         }
 449 
 450         /*
 451          * If the right side is safe and cheaper than a branch,
 452          * just avoid the branch and turn it into a regular binop
 453          * style SAFELOGICAL.
 454          */
 455         if (rcost < BRANCH_COST) {
 456                 expr->type = EXPR_BINOP;
 457                 rcost -= BRANCH_COST - 1;
 458         }
 459 
 460         return cost + BRANCH_COST + rcost;
 461 }
 462 
 463 static int expand_comma(struct expression *expr)
 464 {
 465         int cost;
 466 
 467         cost = expand_expression(expr->left);
 468         cost += expand_expression(expr->right);
 469         if (expr->left->type == EXPR_VALUE || expr->left->type == EXPR_FVALUE) {
 470                 unsigned flags = expr->flags;
 471                 unsigned taint;
 472                 taint = expr->left->type == EXPR_VALUE ? expr->left->taint : 0;
 473                 *expr = *expr->right;
 474                 expr->flags = flags;
 475                 if (expr->type == EXPR_VALUE)
 476                         expr->taint |= Taint_comma | taint;
 477         }
 478         return cost;
 479 }
 480 
 481 #define MOD_IGN (MOD_VOLATILE | MOD_CONST)
 482 
 483 static int compare_types(int op, struct symbol *left, struct symbol *right)
 484 {
 485         struct ctype c1 = {.base_type = left};
 486         struct ctype c2 = {.base_type = right};
 487         switch (op) {
 488         case SPECIAL_EQUAL:
 489                 return !type_difference(&c1, &c2, MOD_IGN, MOD_IGN);
 490         case SPECIAL_NOTEQUAL:
 491                 return type_difference(&c1, &c2, MOD_IGN, MOD_IGN) != NULL;
 492         case '<':
 493                 return left->bit_size < right->bit_size;
 494         case '>':
 495                 return left->bit_size > right->bit_size;
 496         case SPECIAL_LTE:
 497                 return left->bit_size <= right->bit_size;
 498         case SPECIAL_GTE:
 499                 return left->bit_size >= right->bit_size;
 500         }
 501         return 0;
 502 }
 503 
 504 static int expand_compare(struct expression *expr)
 505 {
 506         struct expression *left = expr->left, *right = expr->right;
 507         int cost;
 508 
 509         cost = expand_expression(left);
 510         cost += expand_expression(right);
 511 
 512         if (left && right) {
 513                 /* Type comparison? */
 514                 if (left->type == EXPR_TYPE && right->type == EXPR_TYPE) {
 515                         int op = expr->op;
 516                         expr->type = EXPR_VALUE;
 517                         expr->value = compare_types(op, left->symbol, right->symbol);
 518                         expr->taint = 0;
 519                         return 0;
 520                 }
 521                 if (simplify_cmp_binop(expr, left->ctype))
 522                         return 0;
 523                 if (simplify_float_cmp(expr, left->ctype))
 524                         return 0;
 525         }
 526         return cost + 1;
 527 }
 528 
 529 static int expand_conditional(struct expression *expr)
 530 {
 531         struct expression *cond = expr->conditional;
 532         struct expression *true = expr->cond_true;
 533         struct expression *false = expr->cond_false;
 534         int cost, cond_cost;
 535 
 536         cond_cost = expand_expression(cond);
 537         if (cond->type == EXPR_VALUE) {
 538                 unsigned flags = expr->flags;
 539                 if (!cond->value)
 540                         true = false;
 541                 if (!true)
 542                         true = cond;
 543                 cost = expand_expression(true);
 544                 *expr = *true;
 545                 expr->flags = flags;
 546                 if (expr->type == EXPR_VALUE)
 547                         expr->taint |= cond->taint;
 548                 return cost;
 549         }
 550 
 551         cost = expand_expression(true);
 552         cost += expand_expression(false);
 553 
 554         if (cost < SELECT_COST) {
 555                 expr->type = EXPR_SELECT;
 556                 cost -= BRANCH_COST - 1;
 557         }
 558 
 559         return cost + cond_cost + BRANCH_COST;
 560 }
 561                 
 562 static int expand_assignment(struct expression *expr)
 563 {
 564         expand_expression(expr->left);
 565         expand_expression(expr->right);
 566         return SIDE_EFFECTS;
 567 }
 568 
 569 static int expand_addressof(struct expression *expr)
 570 {
 571         return expand_expression(expr->unop);
 572 }
 573 
 574 /*
 575  * Look up a trustable initializer value at the requested offset.
 576  *
 577  * Return NULL if no such value can be found or statically trusted.
 578  *
 579  * FIXME!! We should check that the size is right!
 580  */
 581 static struct expression *constant_symbol_value(struct symbol *sym, int offset)
 582 {
 583         struct expression *value;
 584 
 585         if (sym->ctype.modifiers & (MOD_ASSIGNED | MOD_ADDRESSABLE))
 586                 return NULL;
 587         value = sym->initializer;
 588         if (!value)
 589                 return NULL;
 590         if (value->type == EXPR_INITIALIZER) {
 591                 struct expression *entry;
 592                 FOR_EACH_PTR(value->expr_list, entry) {
 593                         if (entry->type != EXPR_POS) {
 594                                 if (offset)
 595                                         continue;
 596                                 return entry;
 597                         }
 598                         if (entry->init_offset < offset)
 599                                 continue;
 600                         if (entry->init_offset > offset)
 601                                 return NULL;
 602                         return entry->init_expr;
 603                 } END_FOR_EACH_PTR(entry);
 604                 return NULL;
 605         }
 606         return value;
 607 }
 608 
 609 static int expand_dereference(struct expression *expr)
 610 {
 611         struct expression *unop = expr->unop;
 612         unsigned int offset;
 613 
 614         expand_expression(unop);
 615 
 616         /*
 617          * NOTE! We get a bogus warning right now for some special
 618          * cases: apparently I've screwed up the optimization of
 619          * a zero-offset dereference, and the ctype is wrong.
 620          *
 621          * Leave the warning in anyway, since this is also a good
 622          * test for me to get the type evaluation right..
 623          */
 624         if (expr->ctype->ctype.modifiers & MOD_NODEREF)
 625                 warning(unop->pos, "dereference of noderef expression");
 626 
 627         /*
 628          * Is it "symbol" or "symbol + offset"?
 629          */
 630         offset = 0;
 631         if (unop->type == EXPR_BINOP && unop->op == '+') {
 632                 struct expression *right = unop->right;
 633                 if (right->type == EXPR_VALUE) {
 634                         offset = right->value;
 635                         unop = unop->left;
 636                 }
 637         }
 638 
 639         if (unop->type == EXPR_SYMBOL) {
 640                 struct symbol *sym = unop->symbol;
 641                 struct expression *value = constant_symbol_value(sym, offset);
 642 
 643                 /* Const symbol with a constant initializer? */
 644                 if (value) {
 645                         /* FIXME! We should check that the size is right! */
 646                         if (value->type == EXPR_VALUE) {
 647                                 expr->type = EXPR_VALUE;
 648                                 expr->value = value->value;
 649                                 expr->taint = 0;
 650                                 return 0;
 651                         } else if (value->type == EXPR_FVALUE) {
 652                                 expr->type = EXPR_FVALUE;
 653                                 expr->fvalue = value->fvalue;
 654                                 return 0;
 655                         }
 656                 }
 657 
 658                 /* Direct symbol dereference? Cheap and safe */
 659                 return (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN)) ? 2 : 1;
 660         }
 661 
 662         return UNSAFE;
 663 }
 664 
 665 static int simplify_preop(struct expression *expr)
 666 {
 667         struct expression *op = expr->unop;
 668         unsigned long long v, mask;
 669 
 670         if (op->type != EXPR_VALUE)
 671                 return 0;
 672 
 673         mask = 1ULL << (expr->ctype->bit_size-1);
 674         v = op->value;
 675         switch (expr->op) {
 676         case '+': break;
 677         case '-':
 678                 if (v == mask && !(expr->ctype->ctype.modifiers & MOD_UNSIGNED))
 679                         goto Overflow;
 680                 v = -v;
 681                 break;
 682         case '!': v = !v; break;
 683         case '~': v = ~v; break;
 684         default: return 0;
 685         }
 686         mask = mask | (mask-1);
 687         expr->value = v & mask;
 688         expr->type = EXPR_VALUE;
 689         expr->taint = op->taint;
 690         return 1;
 691 
 692 Overflow:
 693         if (!conservative)
 694                 warning(expr->pos, "constant integer operation overflow");
 695         return 0;
 696 }
 697 
 698 static int simplify_float_preop(struct expression *expr)
 699 {
 700         struct expression *op = expr->unop;
 701         long double v;
 702 
 703         if (op->type != EXPR_FVALUE)
 704                 return 0;
 705         v = op->fvalue;
 706         switch (expr->op) {
 707         case '+': break;
 708         case '-': v = -v; break;
 709         default: return 0;
 710         }
 711         expr->fvalue = v;
 712         expr->type = EXPR_FVALUE;
 713         return 1;
 714 }
 715 
 716 /*
 717  * Unary post-ops: x++ and x--
 718  */
 719 static int expand_postop(struct expression *expr)
 720 {
 721         expand_expression(expr->unop);
 722         return SIDE_EFFECTS;
 723 }
 724 
 725 static int expand_preop(struct expression *expr)
 726 {
 727         int cost;
 728 
 729         switch (expr->op) {
 730         case '*':
 731                 return expand_dereference(expr);
 732 
 733         case '&':
 734                 return expand_addressof(expr);
 735 
 736         case SPECIAL_INCREMENT:
 737         case SPECIAL_DECREMENT:
 738                 /*
 739                  * From a type evaluation standpoint the preops are
 740                  * the same as the postops
 741                  */
 742                 return expand_postop(expr);
 743 
 744         default:
 745                 break;
 746         }
 747         cost = expand_expression(expr->unop);
 748 
 749         if (simplify_preop(expr))
 750                 return 0;
 751         if (simplify_float_preop(expr))
 752                 return 0;
 753         return cost + 1;
 754 }
 755 
 756 static int expand_arguments(struct expression_list *head)
 757 {
 758         int cost = 0;
 759         struct expression *expr;
 760 
 761         FOR_EACH_PTR (head, expr) {
 762                 cost += expand_expression(expr);
 763         } END_FOR_EACH_PTR(expr);
 764         return cost;
 765 }
 766 
 767 static int expand_cast(struct expression *expr)
 768 {
 769         int cost;
 770         struct expression *target = expr->cast_expression;
 771 
 772         cost = expand_expression(target);
 773 
 774         /* Simplify normal integer casts.. */
 775         if (target->type == EXPR_VALUE || target->type == EXPR_FVALUE) {
 776                 cast_value(expr, expr->ctype, target, target->ctype);
 777                 return 0;
 778         }
 779         return cost + 1;
 780 }
 781 
 782 /*
 783  * expand a call expression with a symbol. This
 784  * should expand builtins.
 785  */
 786 static int expand_symbol_call(struct expression *expr, int cost)
 787 {
 788         struct expression *fn = expr->fn;
 789         struct symbol *ctype = fn->ctype;
 790 
 791         if (fn->type != EXPR_PREOP)
 792                 return SIDE_EFFECTS;
 793 
 794         if (ctype->op && ctype->op->expand)
 795                 return ctype->op->expand(expr, cost);
 796 
 797         if (ctype->ctype.modifiers & MOD_PURE)
 798                 return cost + 1;
 799 
 800         return SIDE_EFFECTS;
 801 }
 802 
 803 static int expand_call(struct expression *expr)
 804 {
 805         int cost;
 806         struct symbol *sym;
 807         struct expression *fn = expr->fn;
 808 
 809         cost = expand_arguments(expr->args);
 810         sym = fn->ctype;
 811         if (!sym) {
 812                 expression_error(expr, "function has no type");
 813                 return SIDE_EFFECTS;
 814         }
 815         if (sym->type == SYM_NODE)
 816                 return expand_symbol_call(expr, cost);
 817 
 818         return SIDE_EFFECTS;
 819 }
 820 
 821 static int expand_expression_list(struct expression_list *list)
 822 {
 823         int cost = 0;
 824         struct expression *expr;
 825 
 826         FOR_EACH_PTR(list, expr) {
 827                 cost += expand_expression(expr);
 828         } END_FOR_EACH_PTR(expr);
 829         return cost;
 830 }
 831 
 832 /* 
 833  * We can simplify nested position expressions if
 834  * this is a simple (single) positional expression.
 835  */
 836 static int expand_pos_expression(struct expression *expr)
 837 {
 838         struct expression *nested = expr->init_expr;
 839         unsigned long offset = expr->init_offset;
 840         int nr = expr->init_nr;
 841 
 842         if (nr == 1) {
 843                 switch (nested->type) {
 844                 case EXPR_POS:
 845                         offset += nested->init_offset;
 846                         *expr = *nested;
 847                         expr->init_offset = offset;
 848                         nested = expr;
 849                         break;
 850 
 851                 case EXPR_INITIALIZER: {
 852                         struct expression *reuse = nested, *entry;
 853                         *expr = *nested;
 854                         FOR_EACH_PTR(expr->expr_list, entry) {
 855                                 if (entry->type == EXPR_POS) {
 856                                         entry->init_offset += offset;
 857                                 } else {
 858                                         if (!reuse) {
 859                                                 /*
 860                                                  * This happens rarely, but it can happen
 861                                                  * with bitfields that are all at offset
 862                                                  * zero..
 863                                                  */
 864                                                 reuse = alloc_expression(entry->pos, EXPR_POS);
 865                                         }
 866                                         reuse->type = EXPR_POS;
 867                                         reuse->ctype = entry->ctype;
 868                                         reuse->init_offset = offset;
 869                                         reuse->init_nr = 1;
 870                                         reuse->init_expr = entry;
 871                                         REPLACE_CURRENT_PTR(entry, reuse);
 872                                         reuse = NULL;
 873                                 }
 874                         } END_FOR_EACH_PTR(entry);
 875                         nested = expr;
 876                         break;
 877                 }
 878 
 879                 default:
 880                         break;
 881                 }
 882         }
 883         return expand_expression(nested);
 884 }
 885 
 886 static unsigned long bit_offset(const struct expression *expr)
 887 {
 888         unsigned long offset = 0;
 889         while (expr->type == EXPR_POS) {
 890                 offset += bytes_to_bits(expr->init_offset);
 891                 expr = expr->init_expr;
 892         }
 893         if (expr && expr->ctype)
 894                 offset += expr->ctype->bit_offset;
 895         return offset;
 896 }
 897 
 898 static unsigned long bit_range(const struct expression *expr)
 899 {
 900         unsigned long range = 0;
 901         unsigned long size = 0;
 902         while (expr->type == EXPR_POS) {
 903                 unsigned long nr = expr->init_nr;
 904                 size = expr->ctype->bit_size;
 905                 range += (nr - 1) * size;
 906                 expr = expr->init_expr;
 907         }
 908         range += size;
 909         return range;
 910 }
 911 
 912 static int compare_expressions(const void *_a, const void *_b)
 913 {
 914         const struct expression *a = _a;
 915         const struct expression *b = _b;
 916         unsigned long a_pos = bit_offset(a);
 917         unsigned long b_pos = bit_offset(b);
 918 
 919         return (a_pos < b_pos) ? -1 : (a_pos == b_pos) ? 0 : 1;
 920 }
 921 
 922 static void sort_expression_list(struct expression_list **list)
 923 {
 924         sort_list((struct ptr_list **)list, compare_expressions);
 925 }
 926 
 927 static void verify_nonoverlapping(struct expression_list **list, struct expression *expr)
 928 {
 929         struct expression *a = NULL;
 930         unsigned long max = 0;
 931         unsigned long whole = expr->ctype->bit_size;
 932         struct expression *b;
 933 
 934         if (!Woverride_init)
 935                 return;
 936 
 937         FOR_EACH_PTR(*list, b) {
 938                 unsigned long off, end;
 939                 if (!b->ctype || !b->ctype->bit_size)
 940                         continue;
 941                 off = bit_offset(b);
 942                 if (a && off < max) {
 943                         warning(a->pos, "Initializer entry defined twice");
 944                         info(b->pos, "  also defined here");
 945                         if (!Woverride_init_all)
 946                                 return;
 947                 }
 948                 end = off + bit_range(b);
 949                 if (!a && !Woverride_init_whole_range) {
 950                         // If first entry is the whole range, do not let
 951                         // any warning about it (this allow to initialize
 952                         // an array with some default value and then override
 953                         // some specific entries).
 954                         if (off == 0 && end == whole)
 955                                 continue;
 956                 }
 957                 if (end > max) {
 958                         max = end;
 959                         a = b;
 960                 }
 961         } END_FOR_EACH_PTR(b);
 962 }
 963 
 964 static int expand_expression(struct expression *expr)
 965 {
 966         if (!expr)
 967                 return 0;
 968         if (!expr->ctype || expr->ctype == &bad_ctype)
 969                 return UNSAFE;
 970 
 971         switch (expr->type) {
 972         case EXPR_VALUE:
 973         case EXPR_FVALUE:
 974         case EXPR_STRING:
 975                 return 0;
 976         case EXPR_TYPE:
 977         case EXPR_SYMBOL:
 978                 return expand_symbol_expression(expr);
 979         case EXPR_BINOP:
 980                 return expand_binop(expr);
 981 
 982         case EXPR_LOGICAL:
 983                 return expand_logical(expr);
 984 
 985         case EXPR_COMMA:
 986                 return expand_comma(expr);
 987 
 988         case EXPR_COMPARE:
 989                 return expand_compare(expr);
 990 
 991         case EXPR_ASSIGNMENT:
 992                 return expand_assignment(expr);
 993 
 994         case EXPR_PREOP:
 995                 return expand_preop(expr);
 996 
 997         case EXPR_POSTOP:
 998                 return expand_postop(expr);
 999 
1000         case EXPR_CAST:
1001         case EXPR_FORCE_CAST:
1002         case EXPR_IMPLIED_CAST:
1003                 return expand_cast(expr);
1004 
1005         case EXPR_CALL:
1006                 return expand_call(expr);
1007 
1008         case EXPR_DEREF:
1009                 warning(expr->pos, "we should not have an EXPR_DEREF left at expansion time");
1010                 return UNSAFE;
1011 
1012         case EXPR_SELECT:
1013         case EXPR_CONDITIONAL:
1014                 return expand_conditional(expr);
1015 
1016         case EXPR_STATEMENT: {
1017                 struct statement *stmt = expr->statement;
1018                 int cost = expand_statement(stmt);
1019 
1020                 if (stmt->type == STMT_EXPRESSION && stmt->expression)
1021                         *expr = *stmt->expression;
1022                 return cost;
1023         }
1024 
1025         case EXPR_LABEL:
1026                 return 0;
1027 
1028         case EXPR_INITIALIZER:
1029                 sort_expression_list(&expr->expr_list);
1030                 verify_nonoverlapping(&expr->expr_list, expr);
1031                 return expand_expression_list(expr->expr_list);
1032 
1033         case EXPR_IDENTIFIER:
1034                 return UNSAFE;
1035 
1036         case EXPR_INDEX:
1037                 return UNSAFE;
1038 
1039         case EXPR_SLICE:
1040                 return expand_expression(expr->base) + 1;
1041 
1042         case EXPR_POS:
1043                 return expand_pos_expression(expr);
1044 
1045         case EXPR_SIZEOF:
1046         case EXPR_PTRSIZEOF:
1047         case EXPR_ALIGNOF:
1048         case EXPR_OFFSETOF:
1049                 expression_error(expr, "internal front-end error: sizeof in expansion?");
1050                 return UNSAFE;
1051         }
1052         return SIDE_EFFECTS;
1053 }
1054 
1055 static void expand_const_expression(struct expression *expr, const char *where)
1056 {
1057         if (expr) {
1058                 expand_expression(expr);
1059                 if (expr->type != EXPR_VALUE)
1060                         expression_error(expr, "Expected constant expression in %s", where);
1061         }
1062 }
1063 
1064 int expand_symbol(struct symbol *sym)
1065 {
1066         int retval;
1067         struct symbol *base_type;
1068 
1069         if (!sym)
1070                 return 0;
1071         base_type = sym->ctype.base_type;
1072         if (!base_type)
1073                 return 0;
1074 
1075         retval = expand_expression(sym->initializer);
1076         /* expand the body of the symbol */
1077         if (base_type->type == SYM_FN) {
1078                 if (base_type->stmt)
1079                         expand_statement(base_type->stmt);
1080         }
1081         return retval;
1082 }
1083 
1084 static void expand_return_expression(struct statement *stmt)
1085 {
1086         expand_expression(stmt->expression);
1087 }
1088 
1089 static int expand_if_statement(struct statement *stmt)
1090 {
1091         struct expression *expr = stmt->if_conditional;
1092 
1093         if (!expr || !expr->ctype || expr->ctype == &bad_ctype)
1094                 return UNSAFE;
1095 
1096         expand_expression(expr);
1097 
1098 /* This is only valid if nobody jumps into the "dead" side */
1099 #if 0
1100         /* Simplify constant conditionals without even evaluating the false side */
1101         if (expr->type == EXPR_VALUE) {
1102                 struct statement *simple;
1103                 simple = expr->value ? stmt->if_true : stmt->if_false;
1104 
1105                 /* Nothing? */
1106                 if (!simple) {
1107                         stmt->type = STMT_NONE;
1108                         return 0;
1109                 }
1110                 expand_statement(simple);
1111                 *stmt = *simple;
1112                 return SIDE_EFFECTS;
1113         }
1114 #endif
1115         expand_statement(stmt->if_true);
1116         expand_statement(stmt->if_false);
1117         return SIDE_EFFECTS;
1118 }
1119 
1120 /*
1121  * Expanding a compound statement is really just
1122  * about adding up the costs of each individual
1123  * statement.
1124  *
1125  * We also collapse a simple compound statement:
1126  * this would trigger for simple inline functions,
1127  * except we would have to check the "return"
1128  * symbol usage. Next time.
1129  */
1130 static int expand_compound(struct statement *stmt)
1131 {
1132         struct statement *s, *last;
1133         int cost, statements;
1134 
1135         if (stmt->ret)
1136                 expand_symbol(stmt->ret);
1137 
1138         last = stmt->args;
1139         cost = expand_statement(last);
1140         statements = last != NULL;
1141         FOR_EACH_PTR(stmt->stmts, s) {
1142                 statements++;
1143                 last = s;
1144                 cost += expand_statement(s);
1145         } END_FOR_EACH_PTR(s);
1146 
1147         if (statements == 1 && !stmt->ret)
1148                 *stmt = *last;
1149 
1150         return cost;
1151 }
1152 
1153 static int expand_statement(struct statement *stmt)
1154 {
1155         if (!stmt)
1156                 return 0;
1157 
1158         switch (stmt->type) {
1159         case STMT_DECLARATION: {
1160                 struct symbol *sym;
1161                 FOR_EACH_PTR(stmt->declaration, sym) {
1162                         expand_symbol(sym);
1163                 } END_FOR_EACH_PTR(sym);
1164                 return SIDE_EFFECTS;
1165         }
1166 
1167         case STMT_RETURN:
1168                 expand_return_expression(stmt);
1169                 return SIDE_EFFECTS;
1170 
1171         case STMT_EXPRESSION:
1172                 return expand_expression(stmt->expression);
1173 
1174         case STMT_COMPOUND:
1175                 return expand_compound(stmt);
1176 
1177         case STMT_IF:
1178                 return expand_if_statement(stmt);
1179 
1180         case STMT_ITERATOR:
1181                 expand_expression(stmt->iterator_pre_condition);
1182                 expand_expression(stmt->iterator_post_condition);
1183                 expand_statement(stmt->iterator_pre_statement);
1184                 expand_statement(stmt->iterator_statement);
1185                 expand_statement(stmt->iterator_post_statement);
1186                 return SIDE_EFFECTS;
1187 
1188         case STMT_SWITCH:
1189                 expand_expression(stmt->switch_expression);
1190                 expand_statement(stmt->switch_statement);
1191                 return SIDE_EFFECTS;
1192 
1193         case STMT_CASE:
1194                 expand_const_expression(stmt->case_expression, "case statement");
1195                 expand_const_expression(stmt->case_to, "case statement");
1196                 expand_statement(stmt->case_statement);
1197                 return SIDE_EFFECTS;
1198 
1199         case STMT_LABEL:
1200                 expand_statement(stmt->label_statement);
1201                 return SIDE_EFFECTS;
1202 
1203         case STMT_GOTO:
1204                 expand_expression(stmt->goto_expression);
1205                 return SIDE_EFFECTS;
1206 
1207         case STMT_NONE:
1208                 break;
1209         case STMT_ASM:
1210                 /* FIXME! Do the asm parameter evaluation! */
1211                 break;
1212         case STMT_CONTEXT:
1213                 expand_expression(stmt->expression);
1214                 break;
1215         case STMT_RANGE:
1216                 expand_expression(stmt->range_expression);
1217                 expand_expression(stmt->range_low);
1218                 expand_expression(stmt->range_high);
1219                 break;
1220         }
1221         return SIDE_EFFECTS;
1222 }
1223 
1224 static inline int bad_integer_constant_expression(struct expression *expr)
1225 {
1226         if (!(expr->flags & CEF_ICE))
1227                 return 1;
1228         if (expr->taint & Taint_comma)
1229                 return 1;
1230         return 0;
1231 }
1232 
1233 static long long __get_expression_value(struct expression *expr, int strict)
1234 {
1235         long long value, mask;
1236         struct symbol *ctype;
1237 
1238         if (!expr)
1239                 return 0;
1240         ctype = evaluate_expression(expr);
1241         if (!ctype) {
1242                 expression_error(expr, "bad constant expression type");
1243                 return 0;
1244         }
1245         expand_expression(expr);
1246         if (expr->type != EXPR_VALUE) {
1247                 if (strict != 2)
1248                         expression_error(expr, "bad constant expression");
1249                 return 0;
1250         }
1251         if ((strict == 1) && bad_integer_constant_expression(expr)) {
1252                 expression_error(expr, "bad integer constant expression");
1253                 return 0;
1254         }
1255 
1256         value = expr->value;
1257         mask = 1ULL << (ctype->bit_size-1);
1258 
1259         if (value & mask) {
1260                 while (ctype->type != SYM_BASETYPE)
1261                         ctype = ctype->ctype.base_type;
1262                 if (!(ctype->ctype.modifiers & MOD_UNSIGNED))
1263                         value = value | mask | ~(mask-1);
1264         }
1265         return value;
1266 }
1267 
1268 long long get_expression_value(struct expression *expr)
1269 {
1270         return __get_expression_value(expr, 0);
1271 }
1272 
1273 long long const_expression_value(struct expression *expr)
1274 {
1275         return __get_expression_value(expr, 1);
1276 }
1277 
1278 long long get_expression_value_silent(struct expression *expr)
1279 {
1280 
1281         return __get_expression_value(expr, 2);
1282 }
1283 
1284 int expr_truth_value(struct expression *expr)
1285 {
1286         const int saved = conservative;
1287         struct symbol *ctype;
1288 
1289         if (!expr)
1290                 return 0;
1291 
1292         ctype = evaluate_expression(expr);
1293         if (!ctype)
1294                 return -1;
1295 
1296         conservative = 1;
1297         expand_expression(expr);
1298         conservative = saved;
1299 
1300 redo:
1301         switch (expr->type) {
1302         case EXPR_COMMA:
1303                 expr = expr->right;
1304                 goto redo;
1305         case EXPR_VALUE:
1306                 return expr->value != 0;
1307         case EXPR_FVALUE:
1308                 return expr->fvalue != 0;
1309         default:
1310                 return -1;
1311         }
1312 }
1313 
1314 int is_zero_constant(struct expression *expr)
1315 {
1316         const int saved = conservative;
1317         conservative = 1;
1318         expand_expression(expr);
1319         conservative = saved;
1320         return expr->type == EXPR_VALUE && !expr->value;
1321 }