inline.c

   1 /*
   2  * Sparse - a semantic source parser.
   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
  26 #include <stdlib.h>
  27 #include <stdio.h>
  28
  29 #include "lib.h"
  30 #include "allocate.h"
  31 #include "token.h"
  32 #include "parse.h"
  33 #include "symbol.h"
  34 #include "expression.h"
  35
  36 static struct expression * dup_expression(struct expression *expr)
  37 {
  38         struct expression *dup = alloc_expression(expr->pos, expr->type);
  39         *dup = *expr;
  40         return dup;
  41 }
  42
  43 static struct statement * dup_statement(struct statement *stmt)
  44 {
  45         struct statement *dup = alloc_statement(stmt->pos, stmt->type);
  46         *dup = *stmt;
  47         return dup;
  48 }
  49
  50 static struct symbol *copy_symbol(struct position pos, struct symbol *sym)
  51 {
  52         if (!sym)
  53                 return sym;
  54         if (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN | MOD_TOPLEVEL | MOD_INLINE))
  55                 return sym;
  56         if (!sym->replace) {
  57                 warning(pos, "unreplaced symbol '%s'", show_ident(sym->ident));
  58                 return sym;
  59         }
  60         return sym->replace;
  61 }
  62
  63 static struct symbol_list *copy_symbol_list(struct symbol_list *src)
  64 {
  65         struct symbol_list *dst = NULL;
  66         struct symbol *sym;
  67
  68         FOR_EACH_PTR(src, sym) {
  69                 struct symbol *newsym = copy_symbol(sym->pos, sym);
  70                 add_symbol(&dst, newsym);
  71         } END_FOR_EACH_PTR(sym);
  72         return dst;
  73 }
  74
  75 static struct expression * copy_expression(struct expression *expr)
  76 {
  77         if (!expr)
  78                 return NULL;
  79
  80         switch (expr->type) {
  81         /*
  82          * EXPR_SYMBOL is the interesting case, we may need to replace the
  83          * symbol to the new copy.
  84          */
  85         case EXPR_SYMBOL: {
  86                 struct symbol *sym = copy_symbol(expr->pos, expr->symbol);
  87                 if (sym == expr->symbol)
  88                         break;
  89                 expr = dup_expression(expr);
  90                 expr->symbol = sym;
  91                 break;
  92         }
  93
  94         /* Atomics, never change, just return the expression directly */
  95         case EXPR_VALUE:
  96         case EXPR_STRING:
  97         case EXPR_FVALUE:
  98         case EXPR_TYPE:
  99                 break;
 100
 101         /* Unops: check if the subexpression is unique */
 102         case EXPR_PREOP:
 103         case EXPR_POSTOP: {
 104                 struct expression *unop = copy_expression(expr->unop);
 105                 if (expr->unop == unop)
 106                         break;
 107                 expr = dup_expression(expr);
 108                 expr->unop = unop;
 109                 break;
 110         }
 111
 112         case EXPR_SLICE: {
 113                 struct expression *base = copy_expression(expr->base);
 114                 expr = dup_expression(expr);
 115                 expr->base = base;
 116                 break;
 117         }
 118
 119         /* Binops: copy left/right expressions */
 120         case EXPR_BINOP:
 121         case EXPR_COMMA:
 122         case EXPR_COMPARE:
 123         case EXPR_LOGICAL: {
 124                 struct expression *left = copy_expression(expr->left);
 125                 struct expression *right = copy_expression(expr->right);
 126                 if (left == expr->left && right == expr->right)
 127                         break;
 128                 expr = dup_expression(expr);
 129                 expr->left = left;
 130                 expr->right = right;
 131                 break;
 132         }
 133
 134         case EXPR_ASSIGNMENT: {
 135                 struct expression *left = copy_expression(expr->left);
 136                 struct expression *right = copy_expression(expr->right);
 137                 if (expr->op == '=' && left == expr->left && right == expr->right)
 138                         break;
 139                 expr = dup_expression(expr);
 140                 expr->left = left;
 141                 expr->right = right;
 142                 break;
 143         }
 144
 145         /* Dereference */
 146         case EXPR_DEREF: {
 147                 struct expression *deref = copy_expression(expr->deref);
 148                 expr = dup_expression(expr);
 149                 expr->deref = deref;
 150                 break;
 151         }
 152
 153         /* Cast/sizeof/__alignof__ */
 154         case EXPR_CAST:
 155                 if (expr->cast_expression->type == EXPR_INITIALIZER) {
 156                         struct expression *cast = expr->cast_expression;
 157                         struct symbol *sym = expr->cast_type;
 158                         expr = dup_expression(expr);
 159                         expr->cast_expression = copy_expression(cast);
 160                         expr->cast_type = alloc_symbol(sym->pos, sym->type);
 161                         *expr->cast_type = *sym;
 162                         break;
 163                 }
 164         case EXPR_FORCE_CAST:
 165         case EXPR_IMPLIED_CAST:
 166         case EXPR_SIZEOF:
 167         case EXPR_PTRSIZEOF:
 168         case EXPR_ALIGNOF: {
 169                 struct expression *cast = copy_expression(expr->cast_expression);
 170                 if (cast == expr->cast_expression)
 171                         break;
 172                 expr = dup_expression(expr);
 173                 expr->cast_expression = cast;
 174                 break;
 175         }
 176
 177         /* Conditional expression */
 178         case EXPR_SELECT:
 179         case EXPR_CONDITIONAL: {
 180                 struct expression *cond = copy_expression(expr->conditional);
 181                 struct expression *true = copy_expression(expr->cond_true);
 182                 struct expression *false = copy_expression(expr->cond_false);
 183                 if (cond == expr->conditional && true == expr->cond_true && false == expr->cond_false)
 184                         break;
 185                 expr = dup_expression(expr);
 186                 expr->conditional = cond;
 187                 expr->cond_true = true;
 188                 expr->cond_false = false;
 189                 break;
 190         }
 191
 192         /* Statement expression */
 193         case EXPR_STATEMENT: {
 194                 struct statement *stmt = alloc_statement(expr->pos, STMT_COMPOUND);
 195                 copy_statement(expr->statement, stmt);
 196                 expr = dup_expression(expr);
 197                 expr->statement = stmt;
 198                 break;
 199         }
 200
 201         /* Call expression */
 202         case EXPR_CALL: {
 203                 struct expression *fn = copy_expression(expr->fn);
 204                 struct expression_list *list = expr->args;
 205                 struct expression *arg;
 206
 207                 expr = dup_expression(expr);
 208                 expr->fn = fn;
 209                 expr->args = NULL;
 210                 FOR_EACH_PTR(list, arg) {
 211                         add_expression(&expr->args, copy_expression(arg));
 212                 } END_FOR_EACH_PTR(arg);
 213                 break;
 214         }
 215
 216         /* Initializer list statement */
 217         case EXPR_INITIALIZER: {
 218                 struct expression_list *list = expr->expr_list;
 219                 struct expression *entry;
 220                 expr = dup_expression(expr);
 221                 expr->expr_list = NULL;
 222                 FOR_EACH_PTR(list, entry) {
 223                         add_expression(&expr->expr_list, copy_expression(entry));
 224                 } END_FOR_EACH_PTR(entry);
 225                 break;
 226         }
 227
 228         /* Label in inline function - hmm. */
 229         case EXPR_LABEL: {
 230                 struct symbol *label_symbol = copy_symbol(expr->pos, expr->label_symbol);
 231                 expr = dup_expression(expr);
 232                 expr->label_symbol = label_symbol;
 233                 break;
 234         }
 235
 236         case EXPR_INDEX: {
 237                 struct expression *sub_expr = copy_expression(expr->idx_expression);
 238                 expr = dup_expression(expr);
 239                 expr->idx_expression = sub_expr;
 240                 break;
 241         }
 242
 243         case EXPR_IDENTIFIER: {
 244                 struct expression *sub_expr = copy_expression(expr->ident_expression);
 245                 expr = dup_expression(expr);
 246                 expr->ident_expression = sub_expr;
 247                 break;
 248         }
 249
 250         /* Position in initializer.. */
 251         case EXPR_POS: {
 252                 struct expression *val = copy_expression(expr->init_expr);
 253                 expr = dup_expression(expr);
 254                 expr->init_expr = val;
 255                 break;
 256         }
 257         case EXPR_OFFSETOF: {
 258                 struct expression *val = copy_expression(expr->down);
 259                 if (expr->op == '.') {
 260                         if (expr->down != val) {
 261                                 expr = dup_expression(expr);
 262                                 expr->down = val;
 263                         }
 264                 } else {
 265                         struct expression *idx = copy_expression(expr->index);
 266                         if (expr->down != val || expr->index != idx) {
 267                                 expr = dup_expression(expr);
 268                                 expr->down = val;
 269                                 expr->index = idx;
 270                         }
 271                 }
 272                 break;
 273         }
 274         default:
 275                 warning(expr->pos, "trying to copy expression type %d", expr->type);
 276         }
 277         return expr;
 278 }
 279
 280 static struct expression_list *copy_asm_constraints(struct expression_list *in)
 281 {
 282         struct expression_list *out = NULL;
 283         struct expression *expr;
 284         int state = 0;
 285
 286         FOR_EACH_PTR(in, expr) {
 287                 switch (state) {
 288                 case 0: /* identifier */
 289                 case 1: /* constraint */
 290                         state++;
 291                         add_expression(&out, expr);
 292                         continue;
 293                 case 2: /* expression */
 294                         state = 0;
 295                         add_expression(&out, copy_expression(expr));
 296                         continue;
 297                 }
 298         } END_FOR_EACH_PTR(expr);
 299         return out;
 300 }
 301
 302 static void set_replace(struct symbol *old, struct symbol *new)
 303 {
 304         new->replace = old;
 305         old->replace = new;
 306 }
 307
 308 static void unset_replace(struct symbol *sym)
 309 {
 310         struct symbol *r = sym->replace;
 311         if (!r) {
 312                 warning(sym->pos, "symbol '%s' not replaced?", show_ident(sym->ident));
 313                 return;
 314         }
 315         r->replace = NULL;
 316         sym->replace = NULL;
 317 }
 318
 319 static void unset_replace_list(struct symbol_list *list)
 320 {
 321         struct symbol *sym;
 322         FOR_EACH_PTR(list, sym) {
 323                 unset_replace(sym);
 324         } END_FOR_EACH_PTR(sym);
 325 }
 326
 327 static struct statement *copy_one_statement(struct statement *stmt)
 328 {
 329         if (!stmt)
 330                 return NULL;
 331         switch(stmt->type) {
 332         case STMT_NONE:
 333                 break;
 334         case STMT_DECLARATION: {
 335                 struct symbol *sym;
 336                 struct statement *newstmt = dup_statement(stmt);
 337                 newstmt->declaration = NULL;
 338                 FOR_EACH_PTR(stmt->declaration, sym) {
 339                         struct symbol *newsym = copy_symbol(stmt->pos, sym);
 340                         if (newsym != sym)
 341                                 newsym->initializer = copy_expression(sym->initializer);
 342                         add_symbol(&newstmt->declaration, newsym);
 343                 } END_FOR_EACH_PTR(sym);
 344                 stmt = newstmt;
 345                 break;
 346         }
 347         case STMT_CONTEXT:
 348         case STMT_EXPRESSION: {
 349                 struct expression *expr = copy_expression(stmt->expression);
 350                 if (expr == stmt->expression)
 351                         break;
 352                 stmt = dup_statement(stmt);
 353                 stmt->expression = expr;
 354                 break;
 355         }
 356         case STMT_RANGE: {
 357                 struct expression *expr = copy_expression(stmt->range_expression);
 358                 if (expr == stmt->expression)
 359                         break;
 360                 stmt = dup_statement(stmt);
 361                 stmt->range_expression = expr;
 362                 break;
 363         }
 364         case STMT_COMPOUND: {
 365                 struct statement *new = alloc_statement(stmt->pos, STMT_COMPOUND);
 366                 copy_statement(stmt, new);
 367                 stmt = new;
 368                 break;
 369         }
 370         case STMT_IF: {
 371                 struct expression *cond = stmt->if_conditional;
 372                 struct statement *true = stmt->if_true;
 373                 struct statement *false = stmt->if_false;
 374
 375                 cond = copy_expression(cond);
 376                 true = copy_one_statement(true);
 377                 false = copy_one_statement(false);
 378                 if (stmt->if_conditional == cond &&
 379                     stmt->if_true == true &&
 380                     stmt->if_false == false)
 381                         break;
 382                 stmt = dup_statement(stmt);
 383                 stmt->if_conditional = cond;
 384                 stmt->if_true = true;
 385                 stmt->if_false = false;
 386                 break;
 387         }
 388         case STMT_RETURN: {
 389                 struct expression *retval = copy_expression(stmt->ret_value);
 390                 struct symbol *sym = copy_symbol(stmt->pos, stmt->ret_target);
 391
 392                 stmt = dup_statement(stmt);
 393                 stmt->ret_value = retval;
 394                 stmt->ret_target = sym;
 395                 break;
 396         }
 397         case STMT_CASE: {
 398                 stmt = dup_statement(stmt);
 399                 stmt->case_label = copy_symbol(stmt->pos, stmt->case_label);
 400                 stmt->case_label->stmt = stmt;
 401                 stmt->case_expression = copy_expression(stmt->case_expression);
 402                 stmt->case_to = copy_expression(stmt->case_to);
 403                 stmt->case_statement = copy_one_statement(stmt->case_statement);
 404                 break;
 405         }
 406         case STMT_SWITCH: {
 407                 struct symbol *switch_break = copy_symbol(stmt->pos, stmt->switch_break);
 408                 struct symbol *switch_case = copy_symbol(stmt->pos, stmt->switch_case);
 409                 struct expression *expr = copy_expression(stmt->switch_expression);
 410                 struct statement *switch_stmt = copy_one_statement(stmt->switch_statement);
 411
 412                 stmt = dup_statement(stmt);
 413                 switch_case->symbol_list = copy_symbol_list(switch_case->symbol_list);
 414                 stmt->switch_break = switch_break;
 415                 stmt->switch_case = switch_case;
 416                 stmt->switch_expression = expr;
 417                 stmt->switch_statement = switch_stmt;
 418                 break;
 419         }
 420         case STMT_ITERATOR: {
 421                 stmt = dup_statement(stmt);
 422                 stmt->iterator_break = copy_symbol(stmt->pos, stmt->iterator_break);
 423                 stmt->iterator_continue = copy_symbol(stmt->pos, stmt->iterator_continue);
 424                 stmt->iterator_syms = copy_symbol_list(stmt->iterator_syms);
 425
 426                 stmt->iterator_pre_statement = copy_one_statement(stmt->iterator_pre_statement);
 427                 stmt->iterator_pre_condition = copy_expression(stmt->iterator_pre_condition);
 428
 429                 stmt->iterator_statement = copy_one_statement(stmt->iterator_statement);
 430
 431                 stmt->iterator_post_statement = copy_one_statement(stmt->iterator_post_statement);
 432                 stmt->iterator_post_condition = copy_expression(stmt->iterator_post_condition);
 433                 break;
 434         }
 435         case STMT_LABEL: {
 436                 stmt = dup_statement(stmt);
 437                 stmt->label_identifier = copy_symbol(stmt->pos, stmt->label_identifier);
 438                 stmt->label_statement = copy_one_statement(stmt->label_statement);
 439                 break;
 440         }
 441         case STMT_GOTO: {
 442                 stmt = dup_statement(stmt);
 443                 stmt->goto_label = copy_symbol(stmt->pos, stmt->goto_label);
 444                 stmt->goto_expression = copy_expression(stmt->goto_expression);
 445                 stmt->target_list = copy_symbol_list(stmt->target_list);
 446                 break;
 447         }
 448         case STMT_ASM: {
 449                 stmt = dup_statement(stmt);
 450                 stmt->asm_inputs = copy_asm_constraints(stmt->asm_inputs);
 451                 stmt->asm_outputs = copy_asm_constraints(stmt->asm_outputs);
 452                 /* no need to dup "clobbers", since they are all constant strings */
 453                 break;
 454         }
 455         default:
 456                 warning(stmt->pos, "trying to copy statement type %d", stmt->type);
 457                 break;
 458         }
 459         return stmt;
 460 }
 461
 462 /*
 463  * Copy a statement tree from 'src' to 'dst', where both
 464  * source and destination are of type STMT_COMPOUND.
 465  *
 466  * We do this for the tree-level inliner.
 467  *
 468  * This doesn't do the symbol replacement right: it's not
 469  * re-entrant.
 470  */
 471 void copy_statement(struct statement *src, struct statement *dst)
 472 {
 473         struct statement *stmt;
 474
 475         FOR_EACH_PTR(src->stmts, stmt) {
 476                 add_statement(&dst->stmts, copy_one_statement(stmt));
 477         } END_FOR_EACH_PTR(stmt);
 478         dst->args = copy_one_statement(src->args);
 479         dst->ret = copy_symbol(src->pos, src->ret);
 480         dst->inline_fn = src->inline_fn;
 481 }
 482
 483 static struct symbol *create_copy_symbol(struct symbol *orig)
 484 {
 485         struct symbol *sym = orig;
 486         if (orig) {
 487                 sym = alloc_symbol(orig->pos, orig->type);
 488                 *sym = *orig;
 489                 sym->bb_target = NULL;
 490                 sym->pseudo = NULL;
 491                 set_replace(orig, sym);
 492                 orig = sym;
 493         }
 494         return orig;
 495 }
 496
 497 static struct symbol_list *create_symbol_list(struct symbol_list *src)
 498 {
 499         struct symbol_list *dst = NULL;
 500         struct symbol *sym;
 501
 502         FOR_EACH_PTR(src, sym) {
 503                 struct symbol *newsym = create_copy_symbol(sym);
 504                 add_symbol(&dst, newsym);
 505         } END_FOR_EACH_PTR(sym);
 506         return dst;
 507 }
 508
 509 int inline_function(struct expression *expr, struct symbol *sym)
 510 {
 511         struct symbol_list * fn_symbol_list;
 512         struct symbol *fn = sym->ctype.base_type;
 513         struct expression_list *arg_list = expr->args;
 514         struct statement *stmt = alloc_statement(expr->pos, STMT_COMPOUND);
 515         struct symbol_list *name_list, *arg_decl;
 516         struct symbol *name;
 517         struct expression *arg;
 518
 519         if (!fn->inline_stmt) {
 520                 sparse_error(fn->pos, "marked inline, but without a definition");
 521                 return 0;
 522         }
 523         if (fn->expanding)
 524                 return 0;
 525
 526         fn->expanding = 1;
 527
 528         name_list = fn->arguments;
 529
 530         expr->type = EXPR_STATEMENT;
 531         expr->statement = stmt;
 532         expr->ctype = fn->ctype.base_type;
 533
 534         fn_symbol_list = create_symbol_list(sym->inline_symbol_list);
 535
 536         arg_decl = NULL;
 537         PREPARE_PTR_LIST(name_list, name);
 538         FOR_EACH_PTR(arg_list, arg) {
 539                 struct symbol *a = alloc_symbol(arg->pos, SYM_NODE);
 540
 541                 a->ctype.base_type = arg->ctype;
 542                 if (name) {
 543                         *a = *name;
 544                         set_replace(name, a);
 545                         add_symbol(&fn_symbol_list, a);
 546                 }
 547                 a->initializer = arg;
 548                 add_symbol(&arg_decl, a);
 549
 550                 NEXT_PTR_LIST(name);
 551         } END_FOR_EACH_PTR(arg);
 552         FINISH_PTR_LIST(name);
 553
 554         copy_statement(fn->inline_stmt, stmt);
 555
 556         if (arg_decl) {
 557                 struct statement *decl = alloc_statement(expr->pos, STMT_DECLARATION);
 558                 decl->declaration = arg_decl;
 559                 stmt->args = decl;
 560         }
 561         stmt->inline_fn = sym;
 562
 563         unset_replace_list(fn_symbol_list);
 564
 565         evaluate_statement(stmt);
 566
 567         fn->expanding = 0;
 568         return 1;
 569 }
 570
 571 void uninline(struct symbol *sym)
 572 {
 573         struct symbol *fn = sym->ctype.base_type;
 574         struct symbol_list *arg_list = fn->arguments;
 575         struct symbol *p;
 576
 577         sym->symbol_list = create_symbol_list(sym->inline_symbol_list);
 578         FOR_EACH_PTR(arg_list, p) {
 579                 p->replace = p;
 580         } END_FOR_EACH_PTR(p);
 581         fn->stmt = alloc_statement(fn->pos, STMT_COMPOUND);
 582         copy_statement(fn->inline_stmt, fn->stmt);
 583         unset_replace_list(sym->symbol_list);
 584         unset_replace_list(arg_list);
 585 }