xref: /illumos-gate/usr/src/tools/smatch/src/inline.c (revision c85f09cc)
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_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 
copy_asm_constraints(struct expression_list * in)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 
set_replace(struct symbol * old,struct symbol * new)300 static void set_replace(struct symbol *old, struct symbol *new)
301 {
302 	new->replace = old;
303 	old->replace = new;
304 }
305 
unset_replace(struct symbol * sym)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 
unset_replace_list(struct symbol_list * list)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 
copy_one_statement(struct statement * stmt)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  */
copy_statement(struct statement * src,struct statement * dst)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 
create_copy_symbol(struct symbol * orig)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 
create_symbol_list(struct symbol_list * src)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 
inline_function(struct expression * expr,struct symbol * sym)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 
uninline(struct symbol * sym)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 }
584