expand.c

   1 /*
   2  * sparse/expand.c
   3  *
   4  * Copyright (C) 2003 Transmeta Corp.
   5  *               2003 Linus Torvalds
   6  *
   7  *  Licensed under the Open Software License version 1.1
   8  *
   9  * expand constant expressions.
  10  */
  11 #include <stdlib.h>
  12 #include <stdarg.h>
  13 #include <stddef.h>
  14 #include <stdio.h>
  15 #include <string.h>
  16 #include <ctype.h>
  17 #include <unistd.h>
  18 #include <fcntl.h>
  19 #include <limits.h>
  20
  21 #include "lib.h"
  22 #include "parse.h"
  23 #include "token.h"
  24 #include "symbol.h"
  25 #include "target.h"
  26 #include "expression.h"
  27
  28 static void expand_expression(struct expression *);
  29 static void expand_statement(struct statement *);
  30
  31 static void expand_symbol_expression(struct expression *expr)
  32 {
  33         struct symbol *sym = expr->symbol;
  34
  35         /*
  36          * The preprocessor can cause unknown symbols to be generated
  37          */
  38         if (!sym) {
  39                 warn(expr->pos, "undefined preprocessor identifier '%s'", show_ident(expr->symbol_name));
  40                 expr->type = EXPR_VALUE;
  41                 expr->value = 0;
  42                 return;
  43         }
  44 }
  45
  46 void cast_value(struct expression *expr, struct symbol *newtype,
  47                 struct expression *old, struct symbol *oldtype)
  48 {
  49         int old_size = oldtype->bit_size;
  50         int new_size = newtype->bit_size;
  51         long long value, mask, ormask, andmask;
  52         int is_signed;
  53
  54         // FIXME! We don't handle FP casts of constant values yet
  55         if (newtype->ctype.base_type == &fp_type)
  56                 return;
  57         if (oldtype->ctype.base_type == &fp_type)
  58                 return;
  59
  60         // For pointers and integers, we can just move the value around
  61         expr->type = EXPR_VALUE;
  62         if (old_size == new_size) {
  63                 expr->value = old->value;
  64                 return;
  65         }
  66
  67         // expand it to the full "long long" value
  68         is_signed = !(oldtype->ctype.modifiers & MOD_UNSIGNED);
  69         mask = 1ULL << (old_size-1);
  70         value = old->value;
  71         if (!(value & mask))
  72                 is_signed = 0;
  73         andmask = mask | (mask-1);
  74         ormask = ~andmask;
  75         if (!is_signed)
  76                 ormask = 0;
  77         value = (value & andmask) | ormask;
  78
  79         // Truncate it to the new size
  80         mask = 1ULL << (new_size-1);
  81         mask = mask | (mask-1);
  82         expr->value = value & mask;
  83 }
  84
  85 static int check_shift_count(struct expression *expr, struct symbol *ctype, unsigned int count)
  86 {
  87         if (count >= ctype->bit_size) {
  88                 warn(expr->pos, "shift too big for type (%x)", ctype->ctype.modifiers);
  89                 count &= ctype->bit_size-1;
  90         }
  91         return count;
  92 }
  93
  94 /*
  95  * CAREFUL! We need to get the size and sign of the
  96  * result right!
  97  */
  98 static void simplify_int_binop(struct expression *expr, struct symbol *ctype)
  99 {
 100         struct expression *left = expr->left, *right = expr->right;
 101         unsigned long long v, l, r, mask;
 102         signed long long s, sl, sr;
 103         int is_signed, shift;
 104
 105         if (left->type != EXPR_VALUE || right->type != EXPR_VALUE)
 106                 return;
 107         l = left->value; r = right->value;
 108         is_signed = !(ctype->ctype.modifiers & MOD_UNSIGNED);
 109         mask = 1ULL << (ctype->bit_size-1);
 110         sl = l; sr = r;
 111         if (is_signed && (sl & mask))
 112                 sl |= ~(mask-1);
 113         if (is_signed && (sr & mask))
 114                 sr |= ~(mask-1);
 115
 116         switch (expr->op) {
 117         case '+':               v = l + r; s = v; break;
 118         case '-':               v = l - r; s = v; break;
 119         case '&':               v = l & r; s = v; break;
 120         case '|':               v = l | r; s = v; break;
 121         case '^':               v = l ^ r; s = v; break;
 122         case '*':               v = l * r; s = sl * sr; break;
 123         case '/':               if (!r) return; v = l / r; s = sl / sr; break;
 124         case '%':               if (!r) return; v = l % r; s = sl % sr; break;
 125         case SPECIAL_LEFTSHIFT: shift = check_shift_count(expr, ctype, r); v = l << shift; s = v; break;
 126         case SPECIAL_RIGHTSHIFT:shift = check_shift_count(expr, ctype, r); v = l >> shift; s = sl >> shift; break;
 127         case '<':               v = l < r; s = sl < sr; break;
 128         case '>':               v = l > r; s = sl > sr; break;
 129         case SPECIAL_LTE:       v = l <= r; s = sl <= sr; break;
 130         case SPECIAL_GTE:       v = l >= r; s = sl >= sr; break;
 131         case SPECIAL_EQUAL:     v = l == r; s = v; break;
 132         case SPECIAL_NOTEQUAL:  v = l != r; s = v; break;
 133         default: return;
 134         }
 135         if (is_signed)
 136                 v = s;
 137         mask = mask | (mask-1);
 138         expr->value = v & mask;
 139         expr->type = EXPR_VALUE;
 140 }
 141
 142 static void expand_int_binop(struct expression *expr)
 143 {
 144         simplify_int_binop(expr, expr->ctype);
 145 }
 146
 147 static void expand_logical(struct expression *expr)
 148 {
 149         struct expression *left = expr->left;
 150         struct expression *right;
 151
 152         /* Do immediate short-circuiting ... */
 153         expand_expression(left);
 154         if (left->type == EXPR_VALUE) {
 155                 if (expr->op == SPECIAL_LOGICAL_AND) {
 156                         if (!left->value) {
 157                                 expr->type = EXPR_VALUE;
 158                                 expr->value = 0;
 159                                 return;
 160                         }
 161                 } else {
 162                         if (left->value) {
 163                                 expr->type = EXPR_VALUE;
 164                                 expr->value = 1;
 165                                 return;
 166                         }
 167                 }
 168         }
 169
 170         right = expr->right;
 171         expand_expression(right);
 172         if (left->type == EXPR_VALUE && right->type == EXPR_VALUE) {
 173                 /*
 174                  * We know the left value doesn't matter, since
 175                  * otherwise we would have short-circuited it..
 176                  */
 177                 expr->type = EXPR_VALUE;
 178                 expr->value = right->value;
 179         }
 180 }
 181
 182 static void expand_binop(struct expression *expr)
 183 {
 184         expand_int_binop(expr);
 185 }
 186
 187 static void expand_comma(struct expression *expr)
 188 {
 189         if (expr->left->type == EXPR_VALUE)
 190                 *expr = *expr->right;
 191 }
 192
 193 #define MOD_IGN (MOD_VOLATILE | MOD_CONST)
 194
 195 static int compare_types(int op, struct symbol *left, struct symbol *right)
 196 {
 197         switch (op) {
 198         case SPECIAL_EQUAL:
 199                 return !type_difference(left, right, MOD_IGN, MOD_IGN);
 200         case SPECIAL_NOTEQUAL:
 201                 return type_difference(left, right, MOD_IGN, MOD_IGN) != NULL;
 202         case '<':
 203                 return left->bit_size < right->bit_size;
 204         case '>':
 205                 return left->bit_size > right->bit_size;
 206         case SPECIAL_LTE:
 207                 return left->bit_size <= right->bit_size;
 208         case SPECIAL_GTE:
 209                 return left->bit_size >= right->bit_size;
 210         }
 211         return 0;
 212 }
 213
 214 static void expand_compare(struct expression *expr)
 215 {
 216         struct expression *left = expr->left, *right = expr->right;
 217
 218         /* Type comparison? */
 219         if (left && right && left->type == EXPR_TYPE && right->type == EXPR_TYPE) {
 220                 int op = expr->op;
 221                 expr->type = EXPR_VALUE;
 222                 expr->value = compare_types(op, left->symbol, right->symbol);
 223                 return;
 224         }
 225         simplify_int_binop(expr, expr->ctype);
 226 }
 227
 228 static void expand_conditional(struct expression *expr)
 229 {
 230         struct expression *cond = expr->conditional;
 231
 232         if (cond->type == EXPR_VALUE) {
 233                 struct expression *true, *false;
 234
 235                 true = expr->cond_true ? : cond;
 236                 false = expr->cond_false;
 237
 238                 if (!cond->value)
 239                         true = false;
 240                 *expr = *true;
 241         }
 242 }
 243
 244 static void expand_assignment(struct expression *expr)
 245 {
 246 }
 247
 248 static void expand_addressof(struct expression *expr)
 249 {
 250 }
 251
 252 static void expand_dereference(struct expression *expr)
 253 {
 254         struct expression *unop = expr->unop;
 255
 256         /*
 257          * NOTE! We get a bogus warning right now for some special
 258          * cases: apparently I've screwed up the optimization of
 259          * a zero-offset derefence, and the ctype is wrong.
 260          *
 261          * Leave the warning in anyway, since this is also a good
 262          * test for me to get the type evaluation right..
 263          */
 264         if (expr->ctype->ctype.modifiers & MOD_NODEREF)
 265                 warn(unop->pos, "dereference of noderef expression");
 266
 267         if (unop->type == EXPR_SYMBOL) {
 268                 struct symbol *sym = unop->symbol;
 269
 270                 /* Const symbol with a constant initializer? */
 271                 if (!(sym->ctype.modifiers & (MOD_ASSIGNED | MOD_ADDRESSABLE))) {
 272                         struct expression *value = sym->initializer;
 273                         if (value) {
 274                                 if (value->type == EXPR_VALUE) {
 275                                         expr->type = EXPR_VALUE;
 276                                         expr->value = value->value;
 277                                 }
 278                         }
 279                 }
 280         }
 281 }
 282
 283 static void simplify_preop(struct expression *expr)
 284 {
 285         struct expression *op = expr->unop;
 286         unsigned long long v, mask;
 287
 288         if (op->type != EXPR_VALUE)
 289                 return;
 290         v = op->value;
 291         switch (expr->op) {
 292         case '+': break;
 293         case '-': v = -v; break;
 294         case '!': v = !v; break;
 295         case '~': v = ~v; break;
 296         default: return;
 297         }
 298         mask = 1ULL << (expr->ctype->bit_size-1);
 299         mask = mask | (mask-1);
 300         expr->value = v & mask;
 301         expr->type = EXPR_VALUE;
 302 }
 303
 304 /*
 305  * Unary post-ops: x++ and x--
 306  */
 307 static void expand_postop(struct expression *expr)
 308 {
 309 }
 310
 311 static void expand_preop(struct expression *expr)
 312 {
 313         switch (expr->op) {
 314         case '*':
 315                 expand_dereference(expr);
 316                 return;
 317
 318         case '&':
 319                 expand_addressof(expr);
 320                 return;
 321
 322         case SPECIAL_INCREMENT:
 323         case SPECIAL_DECREMENT:
 324                 /*
 325                  * From a type evaluation standpoint the pre-ops are
 326                  * the same as the postops
 327                  */
 328                 expand_postop(expr);
 329                 return;
 330
 331         default:
 332                 break;
 333         }
 334         simplify_preop(expr);
 335 }
 336
 337 static void expand_arguments(struct expression_list *head)
 338 {
 339         struct expression *expr;
 340
 341         FOR_EACH_PTR (head, expr) {
 342                 expand_expression(expr);
 343         } END_FOR_EACH_PTR;
 344 }
 345
 346 static void expand_cast(struct expression *expr)
 347 {
 348         struct expression *target = expr->cast_expression;
 349
 350         expand_expression(target);
 351
 352         /* Simplify normal integer casts.. */
 353         if (target->type == EXPR_VALUE)
 354                 cast_value(expr, expr->ctype, target, target->ctype);
 355 }
 356
 357 /*
 358  * expand a call expression with a symbol. This
 359  * should expand inline functions, and expand
 360  * builtins.
 361  */
 362 static void expand_symbol_call(struct expression *expr)
 363 {
 364         struct expression *fn = expr->fn;
 365         struct symbol *ctype = fn->ctype;
 366
 367         if (fn->type != EXPR_PREOP)
 368                 return;
 369
 370         if (ctype->op && ctype->op->expand) {
 371                 ctype->op->expand(expr);
 372                 return;
 373         }
 374 }
 375
 376 static void expand_call(struct expression *expr)
 377 {
 378         struct symbol *sym;
 379         struct expression *fn = expr->fn;
 380
 381         sym = fn->ctype;
 382         expand_arguments(expr->args);
 383         if (sym->type == SYM_NODE)
 384                 expand_symbol_call(expr);
 385 }
 386
 387 static void expand_expression_list(struct expression_list *list)
 388 {
 389         struct expression *expr;
 390
 391         FOR_EACH_PTR(list, expr) {
 392                 expand_expression(expr);
 393         } END_FOR_EACH_PTR;
 394 }
 395
 396 static void expand_expression(struct expression *expr)
 397 {
 398         if (!expr)
 399                 return;
 400         if (!expr->ctype)
 401                 return;
 402
 403         switch (expr->type) {
 404         case EXPR_VALUE:
 405                 return;
 406         case EXPR_STRING:
 407                 return;
 408         case EXPR_TYPE:
 409         case EXPR_SYMBOL:
 410                 expand_symbol_expression(expr);
 411                 return;
 412         case EXPR_BINOP:
 413                 expand_expression(expr->left);
 414                 expand_expression(expr->right);
 415                 expand_binop(expr);
 416                 return;
 417
 418         case EXPR_LOGICAL:
 419                 expand_logical(expr);
 420                 return;
 421
 422         case EXPR_COMMA:
 423                 expand_expression(expr->left);
 424                 expand_expression(expr->right);
 425                 expand_comma(expr);
 426                 return;
 427
 428         case EXPR_COMPARE:
 429                 expand_expression(expr->left);
 430                 expand_expression(expr->right);
 431                 expand_compare(expr);
 432                 return;
 433
 434         case EXPR_ASSIGNMENT:
 435                 expand_expression(expr->left);
 436                 expand_expression(expr->right);
 437                 expand_assignment(expr);
 438                 return;
 439
 440         case EXPR_PREOP:
 441                 expand_expression(expr->unop);
 442                 expand_preop(expr);
 443                 return;
 444
 445         case EXPR_POSTOP:
 446                 expand_expression(expr->unop);
 447                 expand_postop(expr);
 448                 return;
 449
 450         case EXPR_CAST:
 451                 expand_cast(expr);
 452                 return;
 453
 454         case EXPR_CALL:
 455                 expand_call(expr);
 456                 return;
 457
 458         case EXPR_DEREF:
 459                 return;
 460
 461         case EXPR_BITFIELD:
 462                 expand_expression(expr->address);
 463                 return;
 464
 465         case EXPR_CONDITIONAL:
 466                 expand_expression(expr->conditional);
 467                 expand_expression(expr->cond_false);
 468                 expand_expression(expr->cond_true);
 469                 expand_conditional(expr);
 470                 return;
 471
 472         case EXPR_STATEMENT:
 473                 expand_statement(expr->statement);
 474                 return;
 475
 476         case EXPR_LABEL:
 477                 return;
 478
 479         case EXPR_INITIALIZER:
 480                 expand_expression_list(expr->expr_list);
 481                 return;
 482
 483         case EXPR_IDENTIFIER:
 484                 return;
 485
 486         case EXPR_INDEX:
 487                 return;
 488
 489         case EXPR_POS:
 490                 expand_expression(expr->init_expr);
 491                 return;
 492
 493         case EXPR_SIZEOF:
 494                 warn(expr->pos, "internal front-end error: sizeof in expansion?");
 495                 return;
 496         }
 497         return;
 498 }
 499
 500 static void expand_const_expression(struct expression *expr, const char *where)
 501 {
 502         if (expr) {
 503                 expand_expression(expr);
 504                 if (expr->type != EXPR_VALUE)
 505                         warn(expr->pos, "Expected constant expression in %s", where);
 506         }
 507 }
 508
 509 void expand_symbol(struct symbol *sym)
 510 {
 511         struct symbol *base_type;
 512
 513         if (!sym)
 514                 return;
 515         base_type = sym->ctype.base_type;
 516         if (!base_type)
 517                 return;
 518
 519         expand_expression(sym->initializer);
 520         /* expand the body of the symbol */
 521         if (base_type->type == SYM_FN) {
 522                 if (base_type->stmt)
 523                         expand_statement(base_type->stmt);
 524         }
 525 }
 526
 527 static void expand_return_expression(struct statement *stmt)
 528 {
 529         expand_expression(stmt->expression);
 530 }
 531
 532 static void expand_if_statement(struct statement *stmt)
 533 {
 534         struct expression *expr = stmt->if_conditional;
 535
 536         if (!expr || !expr->ctype)
 537                 return;
 538
 539         expand_expression(expr);
 540
 541 /* This is only valid if nobody jumps into the "dead" side */
 542 #if 0
 543         /* Simplify constant conditionals without even evaluating the false side */
 544         if (expr->type == EXPR_VALUE) {
 545                 struct statement *simple;
 546                 simple = expr->value ? stmt->if_true : stmt->if_false;
 547
 548                 /* Nothing? */
 549                 if (!simple) {
 550                         stmt->type = STMT_NONE;
 551                         return;
 552                 }
 553                 expand_statement(simple);
 554                 *stmt = *simple;
 555                 return;
 556         }
 557 #endif
 558         expand_statement(stmt->if_true);
 559         expand_statement(stmt->if_false);
 560 }
 561
 562 static void expand_statement(struct statement *stmt)
 563 {
 564         if (!stmt)
 565                 return;
 566
 567         switch (stmt->type) {
 568         case STMT_RETURN:
 569                 expand_return_expression(stmt);
 570                 return;
 571
 572         case STMT_EXPRESSION:
 573                 expand_expression(stmt->expression);
 574                 return;
 575
 576         case STMT_COMPOUND: {
 577                 struct symbol *sym;
 578                 struct statement *s;
 579
 580                 FOR_EACH_PTR(stmt->syms, sym) {
 581                         expand_symbol(sym);
 582                 } END_FOR_EACH_PTR;
 583                 expand_symbol(stmt->ret);
 584
 585                 FOR_EACH_PTR(stmt->stmts, s) {
 586                         expand_statement(s);
 587                 } END_FOR_EACH_PTR;
 588                 return;
 589         }
 590
 591         case STMT_IF:
 592                 expand_if_statement(stmt);
 593                 return;
 594
 595         case STMT_ITERATOR:
 596                 expand_expression(stmt->iterator_pre_condition);
 597                 expand_expression(stmt->iterator_post_condition);
 598                 expand_statement(stmt->iterator_pre_statement);
 599                 expand_statement(stmt->iterator_statement);
 600                 expand_statement(stmt->iterator_post_statement);
 601                 return;
 602
 603         case STMT_SWITCH:
 604                 expand_expression(stmt->switch_expression);
 605                 expand_statement(stmt->switch_statement);
 606                 return;
 607
 608         case STMT_CASE:
 609                 expand_const_expression(stmt->case_expression, "case statement");
 610                 expand_const_expression(stmt->case_to, "case statement");
 611                 expand_statement(stmt->case_statement);
 612                 return;
 613
 614         case STMT_LABEL:
 615                 expand_statement(stmt->label_statement);
 616                 return;
 617
 618         case STMT_GOTO:
 619                 expand_expression(stmt->goto_expression);
 620                 return;
 621
 622         case STMT_NONE:
 623                 break;
 624         case STMT_ASM:
 625                 /* FIXME! Do the asm parameter evaluation! */
 626                 break;
 627         }
 628 }
 629
 630 long long get_expression_value(struct expression *expr)
 631 {
 632         long long value, mask;
 633         struct symbol *ctype;
 634
 635         if (!expr)
 636                 return 0;
 637         ctype = evaluate_expression(expr);
 638         if (!ctype) {
 639                 warn(expr->pos, "bad constant expression type");
 640                 return 0;
 641         }
 642         expand_expression(expr);
 643         if (expr->type != EXPR_VALUE) {
 644                 warn(expr->pos, "bad constant expression");
 645                 return 0;
 646         }
 647
 648         value = expr->value;
 649         mask = 1ULL << (ctype->bit_size-1);
 650
 651         if (value & mask) {
 652                 while (ctype->type != SYM_BASETYPE)
 653                         ctype = ctype->ctype.base_type;
 654                 if (!(ctype->ctype.modifiers & MOD_UNSIGNED))
 655                         value = value | mask | ~(mask-1);
 656         }
 657         return value;
 658 }