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 } 586