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");
  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         if (unop->type == EXPR_SYMBOL) {
 256                 struct symbol *sym = unop->symbol;
 257
 258                 if (sym->ctype.modifiers & MOD_NODEREF)
 259                         warn(expr->pos, "dereference of '%s'", show_ident(sym->ident));
 260
 261                 /* Const symbol with a constant initializer? */
 262                 if (!(sym->ctype.modifiers & (MOD_ASSIGNED | MOD_ADDRESSABLE))) {
 263                         struct expression *value = sym->initializer;
 264                         if (value) {
 265                                 if (value->type == EXPR_VALUE) {
 266                                         expr->type = EXPR_VALUE;
 267                                         expr->value = value->value;
 268                                 }
 269                         }
 270                 }
 271         }
 272 }
 273
 274 static void simplify_preop(struct expression *expr)
 275 {
 276         struct expression *op = expr->unop;
 277         unsigned long long v, mask;
 278
 279         if (op->type != EXPR_VALUE)
 280                 return;
 281         v = op->value;
 282         switch (expr->op) {
 283         case '+': break;
 284         case '-': v = -v; break;
 285         case '!': v = !v; break;
 286         case '~': v = ~v; break;
 287         default: return;
 288         }
 289         mask = 1ULL << (expr->ctype->bit_size-1);
 290         mask = mask | (mask-1);
 291         expr->value = v & mask;
 292         expr->type = EXPR_VALUE;
 293 }
 294
 295 /*
 296  * Unary post-ops: x++ and x--
 297  */
 298 static void expand_postop(struct expression *expr)
 299 {
 300 }
 301
 302 static void expand_preop(struct expression *expr)
 303 {
 304         switch (expr->op) {
 305         case '*':
 306                 expand_dereference(expr);
 307                 return;
 308
 309         case '&':
 310                 expand_addressof(expr);
 311                 return;
 312
 313         case SPECIAL_INCREMENT:
 314         case SPECIAL_DECREMENT:
 315                 /*
 316                  * From a type evaluation standpoint the pre-ops are
 317                  * the same as the postops
 318                  */
 319                 expand_postop(expr);
 320                 return;
 321
 322         default:
 323                 break;
 324         }
 325         simplify_preop(expr);
 326 }
 327
 328 static void expand_arguments(struct expression_list *head)
 329 {
 330         struct expression *expr;
 331
 332         FOR_EACH_PTR (head, expr) {
 333                 expand_expression(expr);
 334         } END_FOR_EACH_PTR;
 335 }
 336
 337 static void expand_cast(struct expression *expr)
 338 {
 339         struct expression *target = expr->cast_expression;
 340
 341         expand_expression(target);
 342
 343         /* Simplify normal integer casts.. */
 344         if (target->type == EXPR_VALUE)
 345                 cast_value(expr, expr->ctype, target, target->ctype);
 346 }
 347
 348 /*
 349  * expand a call expression with a symbol. This
 350  * should expand inline functions, and expand
 351  * builtins.
 352  */
 353 static void expand_symbol_call(struct expression *expr)
 354 {
 355         struct expression *fn = expr->fn;
 356         struct symbol *ctype = fn->ctype;
 357
 358         if (fn->type != EXPR_PREOP)
 359                 return;
 360
 361         if (ctype->op && ctype->op->expand) {
 362                 ctype->op->expand(expr);
 363                 return;
 364         }
 365 }
 366
 367 static void expand_call(struct expression *expr)
 368 {
 369         struct symbol *sym;
 370         struct expression *fn = expr->fn;
 371
 372         sym = fn->ctype;
 373         expand_arguments(expr->args);
 374         if (sym->type == SYM_NODE)
 375                 expand_symbol_call(expr);
 376 }
 377
 378 static void expand_expression_list(struct expression_list *list)
 379 {
 380         struct expression *expr;
 381
 382         FOR_EACH_PTR(list, expr) {
 383                 expand_expression(expr);
 384         } END_FOR_EACH_PTR;
 385 }
 386
 387 static void expand_expression(struct expression *expr)
 388 {
 389         if (!expr)
 390                 return;
 391         if (!expr->ctype)
 392                 return;
 393
 394         switch (expr->type) {
 395         case EXPR_VALUE:
 396                 return;
 397         case EXPR_STRING:
 398                 return;
 399         case EXPR_TYPE:
 400         case EXPR_SYMBOL:
 401                 expand_symbol_expression(expr);
 402                 return;
 403         case EXPR_BINOP:
 404                 expand_expression(expr->left);
 405                 expand_expression(expr->right);
 406                 expand_binop(expr);
 407                 return;
 408
 409         case EXPR_LOGICAL:
 410                 expand_logical(expr);
 411                 return;
 412
 413         case EXPR_COMMA:
 414                 expand_expression(expr->left);
 415                 expand_expression(expr->right);
 416                 expand_comma(expr);
 417                 return;
 418
 419         case EXPR_COMPARE:
 420                 expand_expression(expr->left);
 421                 expand_expression(expr->right);
 422                 expand_compare(expr);
 423                 return;
 424
 425         case EXPR_ASSIGNMENT:
 426                 expand_expression(expr->left);
 427                 expand_expression(expr->right);
 428                 expand_assignment(expr);
 429                 return;
 430
 431         case EXPR_PREOP:
 432                 expand_expression(expr->unop);
 433                 expand_preop(expr);
 434                 return;
 435
 436         case EXPR_POSTOP:
 437                 expand_expression(expr->unop);
 438                 expand_postop(expr);
 439                 return;
 440
 441         case EXPR_CAST:
 442                 expand_cast(expr);
 443                 return;
 444
 445         case EXPR_CALL:
 446                 expand_call(expr);
 447                 return;
 448
 449         case EXPR_DEREF:
 450                 return;
 451
 452         case EXPR_BITFIELD:
 453                 expand_expression(expr->address);
 454                 return;
 455
 456         case EXPR_CONDITIONAL:
 457                 expand_expression(expr->conditional);
 458                 expand_expression(expr->cond_false);
 459                 expand_expression(expr->cond_true);
 460                 expand_conditional(expr);
 461                 return;
 462
 463         case EXPR_STATEMENT:
 464                 expand_statement(expr->statement);
 465                 return;
 466
 467         case EXPR_LABEL:
 468                 return;
 469
 470         case EXPR_INITIALIZER:
 471                 expand_expression_list(expr->expr_list);
 472                 return;
 473
 474         case EXPR_IDENTIFIER:
 475                 return;
 476
 477         case EXPR_INDEX:
 478                 return;
 479
 480         case EXPR_POS:
 481                 expand_expression(expr->init_expr);
 482                 return;
 483
 484         case EXPR_SIZEOF:
 485                 warn(expr->pos, "internal front-end error: sizeof in expansion?");
 486                 return;
 487         }
 488         return;
 489 }
 490
 491 static void expand_const_expression(struct expression *expr, const char *where)
 492 {
 493         if (expr) {
 494                 expand_expression(expr);
 495                 if (expr->type != EXPR_VALUE)
 496                         warn(expr->pos, "Expected constant expression in %s", where);
 497         }
 498 }
 499
 500 void expand_symbol(struct symbol *sym)
 501 {
 502         struct symbol *base_type;
 503
 504         if (!sym)
 505                 return;
 506         base_type = sym->ctype.base_type;
 507         if (!base_type)
 508                 return;
 509
 510         expand_expression(sym->initializer);
 511         /* expand the body of the symbol */
 512         if (base_type->type == SYM_FN) {
 513                 if (base_type->stmt)
 514                         expand_statement(base_type->stmt);
 515         }
 516 }
 517
 518 static void expand_return_expression(struct statement *stmt)
 519 {
 520         expand_expression(stmt->expression);
 521 }
 522
 523 static void expand_if_statement(struct statement *stmt)
 524 {
 525         struct expression *expr = stmt->if_conditional;
 526
 527         if (!expr || !expr->ctype)
 528                 return;
 529
 530         expand_expression(expr);
 531
 532 /* This is only valid if nobody jumps into the "dead" side */
 533 #if 0
 534         /* Simplify constant conditionals without even evaluating the false side */
 535         if (expr->type == EXPR_VALUE) {
 536                 struct statement *simple;
 537                 simple = expr->value ? stmt->if_true : stmt->if_false;
 538
 539                 /* Nothing? */
 540                 if (!simple) {
 541                         stmt->type = STMT_NONE;
 542                         return;
 543                 }
 544                 expand_statement(simple);
 545                 *stmt = *simple;
 546                 return;
 547         }
 548 #endif
 549         expand_statement(stmt->if_true);
 550         expand_statement(stmt->if_false);
 551 }
 552
 553 static void expand_statement(struct statement *stmt)
 554 {
 555         if (!stmt)
 556                 return;
 557
 558         switch (stmt->type) {
 559         case STMT_RETURN:
 560                 expand_return_expression(stmt);
 561                 return;
 562
 563         case STMT_EXPRESSION:
 564                 expand_expression(stmt->expression);
 565                 return;
 566
 567         case STMT_COMPOUND: {
 568                 struct symbol *sym;
 569                 struct statement *s;
 570
 571                 FOR_EACH_PTR(stmt->syms, sym) {
 572                         expand_symbol(sym);
 573                 } END_FOR_EACH_PTR;
 574                 expand_symbol(stmt->ret);
 575
 576                 FOR_EACH_PTR(stmt->stmts, s) {
 577                         expand_statement(s);
 578                 } END_FOR_EACH_PTR;
 579                 return;
 580         }
 581
 582         case STMT_IF:
 583                 expand_if_statement(stmt);
 584                 return;
 585
 586         case STMT_ITERATOR:
 587                 expand_expression(stmt->iterator_pre_condition);
 588                 expand_expression(stmt->iterator_post_condition);
 589                 expand_statement(stmt->iterator_pre_statement);
 590                 expand_statement(stmt->iterator_statement);
 591                 expand_statement(stmt->iterator_post_statement);
 592                 return;
 593
 594         case STMT_SWITCH:
 595                 expand_expression(stmt->switch_expression);
 596                 expand_statement(stmt->switch_statement);
 597                 return;
 598
 599         case STMT_CASE:
 600                 expand_const_expression(stmt->case_expression, "case statement");
 601                 expand_const_expression(stmt->case_to, "case statement");
 602                 expand_statement(stmt->case_statement);
 603                 return;
 604
 605         case STMT_LABEL:
 606                 expand_statement(stmt->label_statement);
 607                 return;
 608
 609         case STMT_GOTO:
 610                 expand_expression(stmt->goto_expression);
 611                 return;
 612
 613         case STMT_NONE:
 614                 break;
 615         case STMT_ASM:
 616                 /* FIXME! Do the asm parameter evaluation! */
 617                 break;
 618         }
 619 }
 620
 621 long long get_expression_value(struct expression *expr)
 622 {
 623         long long value, mask;
 624         struct symbol *ctype;
 625
 626         if (!expr)
 627                 return 0;
 628         ctype = evaluate_expression(expr);
 629         if (!ctype) {
 630                 warn(expr->pos, "bad constant expression type");
 631                 return 0;
 632         }
 633         expand_expression(expr);
 634         if (expr->type != EXPR_VALUE) {
 635                 warn(expr->pos, "bad constant expression");
 636                 return 0;
 637         }
 638
 639         value = expr->value;
 640         mask = 1ULL << (ctype->bit_size-1);
 641
 642         if (value & mask) {
 643                 while (ctype->type != SYM_BASETYPE)
 644                         ctype = ctype->ctype.base_type;
 645                 if (!(ctype->ctype.modifiers & MOD_UNSIGNED))
 646                         value = value | mask | ~(mask-1);
 647         }
 648         return value;
 649 }