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->type == EXPR_INITIALIZER) {
159 struct expression *cast = expr->cast_expression;
160 struct symbol *sym = expr->cast_type;
161 expr = dup_expression(expr);
162 expr->cast_expression = copy_expression(cast);
163 expr->cast_type = alloc_symbol(sym->pos, sym->type);
164 *expr->cast_type = *sym;
165 break;
166 }
167 case EXPR_FORCE_CAST:
168 case EXPR_IMPLIED_CAST:
169 case EXPR_SIZEOF:
170 case EXPR_PTRSIZEOF:
171 case EXPR_ALIGNOF: {
172 struct expression *cast = copy_expression(expr->cast_expression);
173 if (cast == expr->cast_expression)
174 break;
175 expr = dup_expression(expr);
176 expr->cast_expression = cast;
177 break;
178 }
179
180 /* Conditional expression */
181 case EXPR_SELECT:
182 case EXPR_CONDITIONAL: {
183 struct expression *cond = copy_expression(expr->conditional);
184 struct expression *valt = copy_expression(expr->cond_true);
185 struct expression *valf = copy_expression(expr->cond_false);
186 if (cond == expr->conditional && valt == expr->cond_true && valf == expr->cond_false)
187 break;
188 expr = dup_expression(expr);
189 expr->conditional = cond;
190 expr->cond_true = valt;
191 expr->cond_false = valf;
192 break;
193 }
194
195 /* Statement expression */
196 case EXPR_STATEMENT: {
197 struct statement *stmt = alloc_statement(expr->pos, STMT_COMPOUND);
198 copy_statement(expr->statement, stmt);
199 expr = dup_expression(expr);
200 expr->statement = stmt;
201 break;
202 }
203
204 /* Call expression */
205 case EXPR_CALL: {
206 struct expression *fn = copy_expression(expr->fn);
207 struct expression_list *list = expr->args;
208 struct expression *arg;
209
210 expr = dup_expression(expr);
211 expr->fn = fn;
212 expr->args = NULL;
213 FOR_EACH_PTR(list, arg) {
214 add_expression(&expr->args, copy_expression(arg));
215 } END_FOR_EACH_PTR(arg);
216 break;
217 }
218
219 /* Initializer list statement */
220 case EXPR_INITIALIZER: {
221 struct expression_list *list = expr->expr_list;
222 struct expression *entry;
223 expr = dup_expression(expr);
224 expr->expr_list = NULL;
225 FOR_EACH_PTR(list, entry) {
226 add_expression(&expr->expr_list, copy_expression(entry));
227 } END_FOR_EACH_PTR(entry);
228 break;
229 }
230
231 /* Label in inline function - hmm. */
232 case EXPR_LABEL: {
233 struct symbol *label_symbol = copy_symbol(expr->pos, expr->label_symbol);
234 expr = dup_expression(expr);
235 expr->label_symbol = label_symbol;
236 break;
237 }
238
239 case EXPR_INDEX: {
240 struct expression *sub_expr = copy_expression(expr->idx_expression);
241 expr = dup_expression(expr);
242 expr->idx_expression = sub_expr;
243 break;
244 }
245
246 case EXPR_IDENTIFIER: {
247 struct expression *sub_expr = copy_expression(expr->ident_expression);
248 expr = dup_expression(expr);
249 expr->ident_expression = sub_expr;
250 break;
251 }
252
253 /* Position in initializer.. */
254 case EXPR_POS: {
255 struct expression *val = copy_expression(expr->init_expr);
256 expr = dup_expression(expr);
257 expr->init_expr = val;
258 break;
259 }
260 case EXPR_OFFSETOF: {
261 struct expression *val = copy_expression(expr->down);
262 if (expr->op == '.') {
263 if (expr->down != val) {
264 expr = dup_expression(expr);
265 expr->down = val;
266 }
267 } else {
268 struct expression *idx = copy_expression(expr->index);
269 if (expr->down != val || expr->index != idx) {
270 expr = dup_expression(expr);
271 expr->down = val;
272 expr->index = idx;
273 }
274 }
275 break;
276 }
277 case EXPR_ASM_OPERAND: {
278 expr = dup_expression(expr);
279 expr->constraint = copy_expression(expr->constraint);
280 expr->expr = copy_expression(expr->expr);
281 break;
282 }
283 default:
284 warning(expr->pos, "trying to copy expression type %d", expr->type);
285 }
286 return expr;
287 }
288
289 static struct expression_list *copy_asm_constraints(struct expression_list *in)
290 {
291 struct expression_list *out = NULL;
292 struct expression *expr;
293
294 FOR_EACH_PTR(in, expr) {
295 add_expression(&out, copy_expression(expr));
296 } END_FOR_EACH_PTR(expr);
297 return out;
298 }
299
300 static void set_replace(struct symbol *old, struct symbol *new)
301 {
302 new->replace = old;
303 old->replace = new;
304 }
305
306 static void unset_replace(struct symbol *sym)
307 {
308 struct symbol *r = sym->replace;
309 if (!r) {
310 warning(sym->pos, "symbol '%s' not replaced?", show_ident(sym->ident));
311 return;
312 }
313 r->replace = NULL;
314 sym->replace = NULL;
315 }
316
317 static void unset_replace_list(struct symbol_list *list)
318 {
319 struct symbol *sym;
320 FOR_EACH_PTR(list, sym) {
321 unset_replace(sym);
322 } END_FOR_EACH_PTR(sym);
323 }
324
325 static struct statement *copy_one_statement(struct statement *stmt)
326 {
327 if (!stmt)
328 return NULL;
329 switch(stmt->type) {
330 case STMT_NONE:
331 break;
332 case STMT_DECLARATION: {
333 struct symbol *sym;
334 struct statement *newstmt = dup_statement(stmt);
335 newstmt->declaration = NULL;
336 FOR_EACH_PTR(stmt->declaration, sym) {
337 struct symbol *newsym = copy_symbol(stmt->pos, sym);
338 if (newsym != sym)
339 newsym->initializer = copy_expression(sym->initializer);
340 add_symbol(&newstmt->declaration, newsym);
341 } END_FOR_EACH_PTR(sym);
342 stmt = newstmt;
343 break;
344 }
345 case STMT_CONTEXT:
346 case STMT_EXPRESSION: {
347 struct expression *expr = copy_expression(stmt->expression);
348 if (expr == stmt->expression)
349 break;
350 stmt = dup_statement(stmt);
351 stmt->expression = expr;
352 break;
353 }
354 case STMT_RANGE: {
355 struct expression *expr = copy_expression(stmt->range_expression);
356 if (expr == stmt->expression)
357 break;
358 stmt = dup_statement(stmt);
359 stmt->range_expression = expr;
360 break;
361 }
362 case STMT_COMPOUND: {
363 struct statement *new = alloc_statement(stmt->pos, STMT_COMPOUND);
364 copy_statement(stmt, new);
365 stmt = new;
366 break;
367 }
368 case STMT_IF: {
369 struct expression *cond = stmt->if_conditional;
370 struct statement *valt = stmt->if_true;
371 struct statement *valf = stmt->if_false;
372
373 cond = copy_expression(cond);
374 valt = copy_one_statement(valt);
375 valf = copy_one_statement(valf);
376 if (stmt->if_conditional == cond &&
377 stmt->if_true == valt &&
378 stmt->if_false == valf)
379 break;
380 stmt = dup_statement(stmt);
381 stmt->if_conditional = cond;
382 stmt->if_true = valt;
383 stmt->if_false = valf;
384 break;
385 }
386 case STMT_RETURN: {
387 struct expression *retval = copy_expression(stmt->ret_value);
388 struct symbol *sym = copy_symbol(stmt->pos, stmt->ret_target);
389
390 stmt = dup_statement(stmt);
391 stmt->ret_value = retval;
392 stmt->ret_target = sym;
393 break;
394 }
395 case STMT_CASE: {
396 stmt = dup_statement(stmt);
397 stmt->case_label = copy_symbol(stmt->pos, stmt->case_label);
398 stmt->case_label->stmt = stmt;
399 stmt->case_expression = copy_expression(stmt->case_expression);
400 stmt->case_to = copy_expression(stmt->case_to);
401 stmt->case_statement = copy_one_statement(stmt->case_statement);
402 break;
403 }
404 case STMT_SWITCH: {
405 struct symbol *switch_break = copy_symbol(stmt->pos, stmt->switch_break);
406 struct symbol *switch_case = copy_symbol(stmt->pos, stmt->switch_case);
407 struct expression *expr = copy_expression(stmt->switch_expression);
408 struct statement *switch_stmt = copy_one_statement(stmt->switch_statement);
409
410 stmt = dup_statement(stmt);
411 switch_case->symbol_list = copy_symbol_list(switch_case->symbol_list);
412 stmt->switch_break = switch_break;
413 stmt->switch_case = switch_case;
414 stmt->switch_expression = expr;
415 stmt->switch_statement = switch_stmt;
416 break;
417 }
418 case STMT_ITERATOR: {
419 stmt = dup_statement(stmt);
420 stmt->iterator_break = copy_symbol(stmt->pos, stmt->iterator_break);
421 stmt->iterator_continue = copy_symbol(stmt->pos, stmt->iterator_continue);
422 stmt->iterator_syms = copy_symbol_list(stmt->iterator_syms);
423
424 stmt->iterator_pre_statement = copy_one_statement(stmt->iterator_pre_statement);
425 stmt->iterator_pre_condition = copy_expression(stmt->iterator_pre_condition);
426
427 stmt->iterator_statement = copy_one_statement(stmt->iterator_statement);
428
429 stmt->iterator_post_statement = copy_one_statement(stmt->iterator_post_statement);
430 stmt->iterator_post_condition = copy_expression(stmt->iterator_post_condition);
431 break;
432 }
433 case STMT_LABEL: {
434 stmt = dup_statement(stmt);
435 stmt->label_identifier = copy_symbol(stmt->pos, stmt->label_identifier);
436 stmt->label_statement = copy_one_statement(stmt->label_statement);
437 break;
438 }
439 case STMT_GOTO: {
440 stmt = dup_statement(stmt);
441 stmt->goto_label = copy_symbol(stmt->pos, stmt->goto_label);
442 stmt->goto_expression = copy_expression(stmt->goto_expression);
443 stmt->target_list = copy_symbol_list(stmt->target_list);
444 break;
445 }
446 case STMT_ASM: {
447 stmt = dup_statement(stmt);
448 stmt->asm_inputs = copy_asm_constraints(stmt->asm_inputs);
449 stmt->asm_outputs = copy_asm_constraints(stmt->asm_outputs);
450 /* no need to dup "clobbers", since they are all constant strings */
451 break;
452 }
453 default:
454 warning(stmt->pos, "trying to copy statement type %d", stmt->type);
455 break;
456 }
457 return stmt;
458 }
459
460 /*
461 * Copy a statement tree from 'src' to 'dst', where both
462 * source and destination are of type STMT_COMPOUND.
463 *
464 * We do this for the tree-level inliner.
465 *
466 * This doesn't do the symbol replacement right: it's not
467 * re-entrant.
468 */
469 static void copy_statement(struct statement *src, struct statement *dst)
470 {
471 struct statement *stmt;
472
473 FOR_EACH_PTR(src->stmts, stmt) {
474 add_statement(&dst->stmts, copy_one_statement(stmt));
475 } END_FOR_EACH_PTR(stmt);
476 dst->args = copy_one_statement(src->args);
477 dst->ret = copy_symbol(src->pos, src->ret);
478 dst->inline_fn = src->inline_fn;
479 }
480
481 static struct symbol *create_copy_symbol(struct symbol *orig)
482 {
483 struct symbol *sym = orig;
484 if (orig) {
485 sym = alloc_symbol(orig->pos, orig->type);
486 *sym = *orig;
487 sym->bb_target = NULL;
488 sym->pseudo = NULL;
489 set_replace(orig, sym);
490 orig = sym;
491 }
492 return orig;
493 }
494
495 static struct symbol_list *create_symbol_list(struct symbol_list *src)
496 {
497 struct symbol_list *dst = NULL;
498 struct symbol *sym;
499
500 FOR_EACH_PTR(src, sym) {
501 struct symbol *newsym = create_copy_symbol(sym);
502 add_symbol(&dst, newsym);
503 } END_FOR_EACH_PTR(sym);
504 return dst;
505 }
506
507 int inline_function(struct expression *expr, struct symbol *sym)
508 {
509 struct symbol_list * fn_symbol_list;
510 struct symbol *fn = sym->ctype.base_type;
511 struct expression_list *arg_list = expr->args;
512 struct statement *stmt = alloc_statement(expr->pos, STMT_COMPOUND);
513 struct symbol_list *name_list, *arg_decl;
514 struct symbol *name;
515 struct expression *arg;
516
517 if (!fn->inline_stmt) {
518 sparse_error(fn->pos, "marked inline, but without a definition");
519 return 0;
520 }
521 if (fn->expanding)
522 return 0;
523
524 fn->expanding = 1;
525
526 name_list = fn->arguments;
527
528 expr->type = EXPR_STATEMENT;
529 expr->statement = stmt;
530 expr->ctype = fn->ctype.base_type;
531
532 fn_symbol_list = create_symbol_list(sym->inline_symbol_list);
533
534 arg_decl = NULL;
535 PREPARE_PTR_LIST(name_list, name);
536 FOR_EACH_PTR(arg_list, arg) {
537 struct symbol *a = alloc_symbol(arg->pos, SYM_NODE);
538
539 a->ctype.base_type = arg->ctype;
540 if (name) {
541 *a = *name;
542 set_replace(name, a);
543 add_symbol(&fn_symbol_list, a);
544 }
545 a->initializer = arg;
546 add_symbol(&arg_decl, a);
547
548 NEXT_PTR_LIST(name);
549 } END_FOR_EACH_PTR(arg);
550 FINISH_PTR_LIST(name);
551
552 copy_statement(fn->inline_stmt, stmt);
553
554 if (arg_decl) {
555 struct statement *decl = alloc_statement(expr->pos, STMT_DECLARATION);
556 decl->declaration = arg_decl;
557 stmt->args = decl;
558 }
559 stmt->inline_fn = sym;
560
561 unset_replace_list(fn_symbol_list);
562
563 evaluate_statement(stmt);
564
565 fn->expanding = 0;
566 return 1;
567 }
568
569 void uninline(struct symbol *sym)
570 {
571 struct symbol *fn = sym->ctype.base_type;
572 struct symbol_list *arg_list = fn->arguments;
573 struct symbol *p;
574
575 sym->symbol_list = create_symbol_list(sym->inline_symbol_list);
576 FOR_EACH_PTR(arg_list, p) {
577 p->replace = p;
578 } END_FOR_EACH_PTR(p);
579 fn->stmt = alloc_statement(fn->pos, STMT_COMPOUND);
580 copy_statement(fn->inline_stmt, fn->stmt);
581 unset_replace_list(sym->symbol_list);
582 unset_replace_list(arg_list);
583 }