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