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