expand.c

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