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
dup_expression(struct expression * expr)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
dup_statement(struct statement * stmt)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
copy_symbol(struct position pos,struct symbol * sym)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
copy_symbol_list(struct symbol_list * src)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
copy_expression(struct expression * expr)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_GENERIC:
278 expr = dup_expression(expr);
279 expr->control = copy_expression(expr->control);
280 if (!evaluate_expression(expr))
281 return NULL;
282 expr = copy_expression(expr);
283 break;
284
285 default:
286 warning(expr->pos, "trying to copy expression type %d", expr->type);
287 }
288 return expr;
289 }
290
copy_asm_operands(struct asm_operand_list * in)291 static struct asm_operand_list *copy_asm_operands(struct asm_operand_list *in)
292 {
293 struct asm_operand_list *out = NULL;
294 struct asm_operand *old;
295
296 FOR_EACH_PTR(in, old) {
297 struct asm_operand *new = __alloc_asm_operand(0);
298 new->name = old->name;
299 new->constraint = copy_expression(old->constraint);
300 new->expr = copy_expression(old->expr);
301 add_ptr_list(&out, new);
302 } END_FOR_EACH_PTR(old);
303 return out;
304 }
305
set_replace(struct symbol * old,struct symbol * new)306 static void set_replace(struct symbol *old, struct symbol *new)
307 {
308 new->replace = old;
309 old->replace = new;
310 }
311
unset_replace(struct symbol * sym)312 static void unset_replace(struct symbol *sym)
313 {
314 struct symbol *r = sym->replace;
315 if (!r) {
316 warning(sym->pos, "symbol '%s' not replaced?", show_ident(sym->ident));
317 return;
318 }
319 r->replace = NULL;
320 sym->replace = NULL;
321 }
322
unset_replace_list(struct symbol_list * list)323 static void unset_replace_list(struct symbol_list *list)
324 {
325 struct symbol *sym;
326 FOR_EACH_PTR(list, sym) {
327 unset_replace(sym);
328 } END_FOR_EACH_PTR(sym);
329 }
330
copy_one_statement(struct statement * stmt)331 static struct statement *copy_one_statement(struct statement *stmt)
332 {
333 if (!stmt)
334 return NULL;
335 switch(stmt->type) {
336 case STMT_NONE:
337 break;
338 case STMT_DECLARATION: {
339 struct symbol *sym;
340 struct statement *newstmt = dup_statement(stmt);
341 newstmt->declaration = NULL;
342 FOR_EACH_PTR(stmt->declaration, sym) {
343 struct symbol *newsym = copy_symbol(stmt->pos, sym);
344 if (newsym != sym)
345 newsym->initializer = copy_expression(sym->initializer);
346 add_symbol(&newstmt->declaration, newsym);
347 } END_FOR_EACH_PTR(sym);
348 stmt = newstmt;
349 break;
350 }
351 case STMT_CONTEXT:
352 case STMT_EXPRESSION: {
353 struct expression *expr = copy_expression(stmt->expression);
354 if (expr == stmt->expression)
355 break;
356 stmt = dup_statement(stmt);
357 stmt->expression = expr;
358 break;
359 }
360 case STMT_RANGE: {
361 struct expression *expr = copy_expression(stmt->range_expression);
362 if (expr == stmt->expression)
363 break;
364 stmt = dup_statement(stmt);
365 stmt->range_expression = expr;
366 break;
367 }
368 case STMT_COMPOUND: {
369 struct statement *new = alloc_statement(stmt->pos, STMT_COMPOUND);
370 copy_statement(stmt, new);
371 stmt = new;
372 break;
373 }
374 case STMT_IF: {
375 struct expression *cond = stmt->if_conditional;
376 struct statement *valt = stmt->if_true;
377 struct statement *valf = stmt->if_false;
378
379 cond = copy_expression(cond);
380 valt = copy_one_statement(valt);
381 valf = copy_one_statement(valf);
382 if (stmt->if_conditional == cond &&
383 stmt->if_true == valt &&
384 stmt->if_false == valf)
385 break;
386 stmt = dup_statement(stmt);
387 stmt->if_conditional = cond;
388 stmt->if_true = valt;
389 stmt->if_false = valf;
390 break;
391 }
392 case STMT_RETURN: {
393 struct expression *retval = copy_expression(stmt->ret_value);
394 struct symbol *sym = copy_symbol(stmt->pos, stmt->ret_target);
395
396 stmt = dup_statement(stmt);
397 stmt->ret_value = retval;
398 stmt->ret_target = sym;
399 break;
400 }
401 case STMT_CASE: {
402 stmt = dup_statement(stmt);
403 stmt->case_label = copy_symbol(stmt->pos, stmt->case_label);
404 stmt->case_label->stmt = stmt;
405 stmt->case_expression = copy_expression(stmt->case_expression);
406 stmt->case_to = copy_expression(stmt->case_to);
407 stmt->case_statement = copy_one_statement(stmt->case_statement);
408 break;
409 }
410 case STMT_SWITCH: {
411 struct symbol *switch_break = copy_symbol(stmt->pos, stmt->switch_break);
412 struct symbol *switch_case = copy_symbol(stmt->pos, stmt->switch_case);
413 struct expression *expr = copy_expression(stmt->switch_expression);
414 struct statement *switch_stmt = copy_one_statement(stmt->switch_statement);
415
416 stmt = dup_statement(stmt);
417 switch_case->symbol_list = copy_symbol_list(switch_case->symbol_list);
418 stmt->switch_break = switch_break;
419 stmt->switch_case = switch_case;
420 stmt->switch_expression = expr;
421 stmt->switch_statement = switch_stmt;
422 break;
423 }
424 case STMT_ITERATOR: {
425 stmt = dup_statement(stmt);
426 stmt->iterator_break = copy_symbol(stmt->pos, stmt->iterator_break);
427 stmt->iterator_continue = copy_symbol(stmt->pos, stmt->iterator_continue);
428 stmt->iterator_syms = copy_symbol_list(stmt->iterator_syms);
429
430 stmt->iterator_pre_statement = copy_one_statement(stmt->iterator_pre_statement);
431 stmt->iterator_pre_condition = copy_expression(stmt->iterator_pre_condition);
432
433 stmt->iterator_statement = copy_one_statement(stmt->iterator_statement);
434
435 stmt->iterator_post_statement = copy_one_statement(stmt->iterator_post_statement);
436 stmt->iterator_post_condition = copy_expression(stmt->iterator_post_condition);
437 break;
438 }
439 case STMT_LABEL: {
440 stmt = dup_statement(stmt);
441 stmt->label_identifier = copy_symbol(stmt->pos, stmt->label_identifier);
442 stmt->label_statement = copy_one_statement(stmt->label_statement);
443 break;
444 }
445 case STMT_GOTO: {
446 stmt = dup_statement(stmt);
447 stmt->goto_label = copy_symbol(stmt->pos, stmt->goto_label);
448 stmt->goto_expression = copy_expression(stmt->goto_expression);
449 stmt->target_list = copy_symbol_list(stmt->target_list);
450 break;
451 }
452 case STMT_ASM: {
453 stmt = dup_statement(stmt);
454 stmt->asm_inputs = copy_asm_operands(stmt->asm_inputs);
455 stmt->asm_outputs = copy_asm_operands(stmt->asm_outputs);
456 /* no need to dup "clobbers", since they are all constant strings */
457 break;
458 }
459 default:
460 warning(stmt->pos, "trying to copy statement type %d", stmt->type);
461 break;
462 }
463 return stmt;
464 }
465
466 /*
467 * Copy a statement tree from 'src' to 'dst', where both
468 * source and destination are of type STMT_COMPOUND.
469 *
470 * We do this for the tree-level inliner.
471 *
472 * This doesn't do the symbol replacement right: it's not
473 * re-entrant.
474 */
copy_statement(struct statement * src,struct statement * dst)475 static void copy_statement(struct statement *src, struct statement *dst)
476 {
477 struct statement *stmt;
478
479 FOR_EACH_PTR(src->stmts, stmt) {
480 add_statement(&dst->stmts, copy_one_statement(stmt));
481 } END_FOR_EACH_PTR(stmt);
482 dst->args = copy_one_statement(src->args);
483 dst->ret = copy_symbol(src->pos, src->ret);
484 dst->inline_fn = src->inline_fn;
485 }
486
create_copy_symbol(struct symbol * orig)487 static struct symbol *create_copy_symbol(struct symbol *orig)
488 {
489 struct symbol *sym = orig;
490 if (orig) {
491 sym = alloc_symbol(orig->pos, orig->type);
492 *sym = *orig;
493 sym->bb_target = NULL;
494 sym->pseudo = NULL;
495 set_replace(orig, sym);
496 orig = sym;
497 }
498 return orig;
499 }
500
create_symbol_list(struct symbol_list * src)501 static struct symbol_list *create_symbol_list(struct symbol_list *src)
502 {
503 struct symbol_list *dst = NULL;
504 struct symbol *sym;
505
506 FOR_EACH_PTR(src, sym) {
507 struct symbol *newsym = create_copy_symbol(sym);
508 add_symbol(&dst, newsym);
509 } END_FOR_EACH_PTR(sym);
510 return dst;
511 }
512
inline_function(struct expression * expr,struct symbol * sym)513 int inline_function(struct expression *expr, struct symbol *sym)
514 {
515 struct symbol_list * fn_symbol_list;
516 struct symbol *fn = sym->ctype.base_type;
517 struct expression_list *arg_list = expr->args;
518 struct statement *stmt = alloc_statement(expr->pos, STMT_COMPOUND);
519 struct symbol_list *name_list, *arg_decl;
520 struct symbol *name;
521 struct expression *arg;
522
523 if (!fn->inline_stmt) {
524 sparse_error(fn->pos, "marked inline, but without a definition");
525 return 0;
526 }
527 if (fn->expanding)
528 return 0;
529
530 name_list = fn->arguments;
531
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(name_list, name);
540 FOR_EACH_PTR(arg_list, arg) {
541 struct symbol *a = alloc_symbol(arg->pos, SYM_NODE);
542
543 a->ctype.base_type = arg->ctype;
544 if (name) {
545 *a = *name;
546 set_replace(name, a);
547 add_symbol(&fn_symbol_list, a);
548 }
549 a->initializer = arg;
550 add_symbol(&arg_decl, a);
551
552 NEXT_PTR_LIST(name);
553 } END_FOR_EACH_PTR(arg);
554 FINISH_PTR_LIST(name);
555
556 copy_statement(fn->inline_stmt, stmt);
557
558 if (arg_decl) {
559 struct statement *decl = alloc_statement(expr->pos, STMT_DECLARATION);
560 decl->declaration = arg_decl;
561 stmt->args = decl;
562 }
563 stmt->inline_fn = sym;
564
565 unset_replace_list(fn_symbol_list);
566
567 return 1;
568 }
569
uninline(struct symbol * sym)570 void uninline(struct symbol *sym)
571 {
572 struct symbol *fn = sym->ctype.base_type;
573 struct symbol_list *arg_list = fn->arguments;
574 struct symbol *p;
575
576 sym->symbol_list = create_symbol_list(sym->inline_symbol_list);
577 FOR_EACH_PTR(arg_list, p) {
578 p->replace = p;
579 } END_FOR_EACH_PTR(p);
580 fn->stmt = alloc_statement(fn->pos, STMT_COMPOUND);
581 copy_statement(fn->inline_stmt, fn->stmt);
582 unset_replace_list(sym->symbol_list);
583 unset_replace_list(arg_list);
584 }
585