xref: /illumos-gate/usr/src/tools/smatch/src/expand.c (revision c85f09cc92abd00c84e58ec9f0f5d942906cb713)
1 /*
2  * sparse/expand.c
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  * expand constant expressions.
26  */
27 #include <stdlib.h>
28 #include <stdarg.h>
29 #include <stddef.h>
30 #include <stdio.h>
31 #include <string.h>
32 #include <ctype.h>
33 #include <unistd.h>
34 #include <fcntl.h>
35 #include <limits.h>
36 
37 #include "lib.h"
38 #include "allocate.h"
39 #include "parse.h"
40 #include "token.h"
41 #include "symbol.h"
42 #include "target.h"
43 #include "expression.h"
44 #include "evaluate.h"
45 #include "expand.h"
46 
47 
48 static int expand_expression(struct expression *);
49 static int expand_statement(struct statement *);
50 
51 // If set, don't issue a warning on divide-by-0, invalid shift, ...
52 // and don't mark the expression as erroneous but leave it as-is.
53 // This allows testing some characteristics of the expression
54 // without creating any side-effects (e.g.: is_zero_constant()).
55 static int conservative;
56 
expand_symbol_expression(struct expression * expr)57 static int expand_symbol_expression(struct expression *expr)
58 {
59 	struct symbol *sym = expr->symbol;
60 
61 	if (sym == &zero_int) {
62 		if (Wundef)
63 			warning(expr->pos, "undefined preprocessor identifier '%s'", show_ident(expr->symbol_name));
64 		expr->type = EXPR_VALUE;
65 		expr->value = 0;
66 		expr->taint = 0;
67 		return 0;
68 	}
69 	/* The cost of a symbol expression is lower for on-stack symbols */
70 	return (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN)) ? 2 : 1;
71 }
72 
get_longlong(struct expression * expr)73 static long long get_longlong(struct expression *expr)
74 {
75 	int no_expand = expr->ctype->ctype.modifiers & MOD_UNSIGNED;
76 	long long mask = 1ULL << (expr->ctype->bit_size - 1);
77 	long long value = expr->value;
78 	long long ormask, andmask;
79 
80 	if (!(value & mask))
81 		no_expand = 1;
82 	andmask = mask | (mask-1);
83 	ormask = ~andmask;
84 	if (no_expand)
85 		ormask = 0;
86 	return (value & andmask) | ormask;
87 }
88 
cast_value(struct expression * expr,struct symbol * newtype,struct expression * old,struct symbol * oldtype)89 void cast_value(struct expression *expr, struct symbol *newtype,
90 		struct expression *old, struct symbol *oldtype)
91 {
92 	int old_size = oldtype->bit_size;
93 	int new_size = newtype->bit_size;
94 	long long value, mask, signmask;
95 	long long oldmask, oldsignmask, dropped;
96 
97 	if (is_float_type(newtype) || is_float_type(oldtype))
98 		goto Float;
99 
100 	// For pointers and integers, we can just move the value around
101 	expr->type = EXPR_VALUE;
102 	expr->taint = old->taint;
103 	if (old_size == new_size) {
104 		expr->value = old->value;
105 		return;
106 	}
107 
108 	// expand it to the full "long long" value
109 	value = get_longlong(old);
110 
111 Int:
112 	// _Bool requires a zero test rather than truncation.
113 	if (is_bool_type(newtype)) {
114 		expr->value = !!value;
115 		if (!conservative && value != 0 && value != 1)
116 			warning(old->pos, "odd constant _Bool cast (%llx becomes 1)", value);
117 		return;
118 	}
119 
120 	// Truncate it to the new size
121 	signmask = 1ULL << (new_size-1);
122 	mask = signmask | (signmask-1);
123 	expr->value = value & mask;
124 
125 	// Stop here unless checking for truncation
126 	if (!Wcast_truncate || conservative)
127 		return;
128 
129 	// Check if we dropped any bits..
130 	oldsignmask = 1ULL << (old_size-1);
131 	oldmask = oldsignmask | (oldsignmask-1);
132 	dropped = oldmask & ~mask;
133 
134 	// OK if the bits were (and still are) purely sign bits
135 	if (value & dropped) {
136 		if (!(value & oldsignmask) || !(value & signmask) || (value & dropped) != dropped)
137 			warning(old->pos, "cast truncates bits from constant value (%llx becomes %llx)",
138 				value & oldmask,
139 				value & mask);
140 	}
141 	return;
142 
143 Float:
144 	if (!is_float_type(newtype)) {
145 		value = (long long)old->fvalue;
146 		expr->type = EXPR_VALUE;
147 		expr->taint = 0;
148 		goto Int;
149 	}
150 
151 	if (!is_float_type(oldtype))
152 		expr->fvalue = (long double)get_longlong(old);
153 	else
154 		expr->fvalue = old->fvalue;
155 
156 	if (!(newtype->ctype.modifiers & MOD_LONGLONG) && \
157 	    !(newtype->ctype.modifiers & MOD_LONGLONGLONG)) {
158 		if ((newtype->ctype.modifiers & MOD_LONG))
159 			expr->fvalue = (double)expr->fvalue;
160 		else
161 			expr->fvalue = (float)expr->fvalue;
162 	}
163 	expr->type = EXPR_FVALUE;
164 }
165 
warn_shift_count(struct expression * expr,struct symbol * ctype,long long count)166 static void warn_shift_count(struct expression *expr, struct symbol *ctype, long long count)
167 {
168 	if (count < 0) {
169 		if (!Wshift_count_negative)
170 			return;
171 		warning(expr->pos, "shift count is negative (%lld)", count);
172 		return;
173 	}
174 	if (ctype->type == SYM_NODE)
175 		ctype = ctype->ctype.base_type;
176 
177 	if (!Wshift_count_overflow)
178 		return;
179 	warning(expr->pos, "shift too big (%llu) for type %s", count, show_typename(ctype));
180 }
181 
182 /* Return true if constant shift size is valid */
check_shift_count(struct expression * expr,struct expression * right)183 static bool check_shift_count(struct expression *expr, struct expression *right)
184 {
185 	struct symbol *ctype = expr->ctype;
186 	long long count = get_longlong(right);
187 
188 	if (count >= 0 && count < ctype->bit_size)
189 		return true;
190 	if (!conservative)
191 		warn_shift_count(expr, ctype, count);
192 	return false;
193 }
194 
195 /*
196  * CAREFUL! We need to get the size and sign of the
197  * result right!
198  */
199 #define CONVERT(op,s)	(((op)<<1)+(s))
200 #define SIGNED(op)	CONVERT(op, 1)
201 #define UNSIGNED(op)	CONVERT(op, 0)
simplify_int_binop(struct expression * expr,struct symbol * ctype)202 static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
203 {
204 	struct expression *left = expr->left, *right = expr->right;
205 	unsigned long long v, l, r, mask;
206 	signed long long sl, sr;
207 	int is_signed;
208 
209 	if (right->type != EXPR_VALUE)
210 		return 0;
211 	r = right->value;
212 	if (expr->op == SPECIAL_LEFTSHIFT || expr->op == SPECIAL_RIGHTSHIFT) {
213 		if (!check_shift_count(expr, right))
214 			return 0;
215 	}
216 	if (left->type != EXPR_VALUE)
217 		return 0;
218 	l = left->value; r = right->value;
219 	is_signed = !(ctype->ctype.modifiers & MOD_UNSIGNED);
220 	mask = 1ULL << (ctype->bit_size-1);
221 	sl = l; sr = r;
222 	if (is_signed && (sl & mask))
223 		sl |= ~(mask-1);
224 	if (is_signed && (sr & mask))
225 		sr |= ~(mask-1);
226 
227 	switch (CONVERT(expr->op,is_signed)) {
228 	case SIGNED('+'):
229 	case UNSIGNED('+'):
230 		v = l + r;
231 		break;
232 
233 	case SIGNED('-'):
234 	case UNSIGNED('-'):
235 		v = l - r;
236 		break;
237 
238 	case SIGNED('&'):
239 	case UNSIGNED('&'):
240 		v = l & r;
241 		break;
242 
243 	case SIGNED('|'):
244 	case UNSIGNED('|'):
245 		v = l | r;
246 		break;
247 
248 	case SIGNED('^'):
249 	case UNSIGNED('^'):
250 		v = l ^ r;
251 		break;
252 
253 	case SIGNED('*'):
254 		v = sl * sr;
255 		break;
256 
257 	case UNSIGNED('*'):
258 		v = l * r;
259 		break;
260 
261 	case SIGNED('/'):
262 		if (!r)
263 			goto Div;
264 		if (l == mask && sr == -1)
265 			goto Overflow;
266 		v = sl / sr;
267 		break;
268 
269 	case UNSIGNED('/'):
270 		if (!r) goto Div;
271 		v = l / r;
272 		break;
273 
274 	case SIGNED('%'):
275 		if (!r)
276 			goto Div;
277 		if (l == mask && sr == -1)
278 			goto Overflow;
279 		v = sl % sr;
280 		break;
281 
282 	case UNSIGNED('%'):
283 		if (!r) goto Div;
284 		v = l % r;
285 		break;
286 
287 	case SIGNED(SPECIAL_LEFTSHIFT):
288 	case UNSIGNED(SPECIAL_LEFTSHIFT):
289 		v = l << r;
290 		break;
291 
292 	case SIGNED(SPECIAL_RIGHTSHIFT):
293 		v = sl >> r;
294 		break;
295 
296 	case UNSIGNED(SPECIAL_RIGHTSHIFT):
297 		v = l >> r;
298 		break;
299 
300 	default:
301 		return 0;
302 	}
303 	mask = mask | (mask-1);
304 	expr->value = v & mask;
305 	expr->type = EXPR_VALUE;
306 	expr->taint = left->taint | right->taint;
307 	return 1;
308 Div:
309 	if (!conservative)
310 		warning(expr->pos, "division by zero");
311 	return 0;
312 Overflow:
313 	if (!conservative)
314 		warning(expr->pos, "constant integer operation overflow");
315 	return 0;
316 }
317 
simplify_cmp_binop(struct expression * expr,struct symbol * ctype)318 static int simplify_cmp_binop(struct expression *expr, struct symbol *ctype)
319 {
320 	struct expression *left = expr->left, *right = expr->right;
321 	unsigned long long l, r, mask;
322 	signed long long sl, sr;
323 
324 	if (left->type != EXPR_VALUE || right->type != EXPR_VALUE)
325 		return 0;
326 	l = left->value; r = right->value;
327 	mask = 1ULL << (ctype->bit_size-1);
328 	sl = l; sr = r;
329 	if (sl & mask)
330 		sl |= ~(mask-1);
331 	if (sr & mask)
332 		sr |= ~(mask-1);
333 	switch (expr->op) {
334 	case '<':		expr->value = sl < sr; break;
335 	case '>':		expr->value = sl > sr; break;
336 	case SPECIAL_LTE:	expr->value = sl <= sr; break;
337 	case SPECIAL_GTE:	expr->value = sl >= sr; break;
338 	case SPECIAL_EQUAL:	expr->value = l == r; break;
339 	case SPECIAL_NOTEQUAL:	expr->value = l != r; break;
340 	case SPECIAL_UNSIGNED_LT:expr->value = l < r; break;
341 	case SPECIAL_UNSIGNED_GT:expr->value = l > r; break;
342 	case SPECIAL_UNSIGNED_LTE:expr->value = l <= r; break;
343 	case SPECIAL_UNSIGNED_GTE:expr->value = l >= r; break;
344 	}
345 	expr->type = EXPR_VALUE;
346 	expr->taint = left->taint | right->taint;
347 	return 1;
348 }
349 
simplify_float_binop(struct expression * expr)350 static int simplify_float_binop(struct expression *expr)
351 {
352 	struct expression *left = expr->left, *right = expr->right;
353 	unsigned long mod = expr->ctype->ctype.modifiers;
354 	long double l, r, res;
355 
356 	if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE)
357 		return 0;
358 
359 	l = left->fvalue;
360 	r = right->fvalue;
361 
362 	if (mod & MOD_LONGLONG) {
363 		switch (expr->op) {
364 		case '+':	res = l + r; break;
365 		case '-':	res = l - r; break;
366 		case '*':	res = l * r; break;
367 		case '/':	if (!r) goto Div;
368 				res = l / r; break;
369 		default: return 0;
370 		}
371 	} else if (mod & MOD_LONG) {
372 		switch (expr->op) {
373 		case '+':	res = (double) l + (double) r; break;
374 		case '-':	res = (double) l - (double) r; break;
375 		case '*':	res = (double) l * (double) r; break;
376 		case '/':	if (!r) goto Div;
377 				res = (double) l / (double) r; break;
378 		default: return 0;
379 		}
380 	} else {
381 		switch (expr->op) {
382 		case '+':	res = (float)l + (float)r; break;
383 		case '-':	res = (float)l - (float)r; break;
384 		case '*':	res = (float)l * (float)r; break;
385 		case '/':	if (!r) goto Div;
386 				res = (float)l / (float)r; break;
387 		default: return 0;
388 		}
389 	}
390 	expr->type = EXPR_FVALUE;
391 	expr->fvalue = res;
392 	return 1;
393 Div:
394 	if (!conservative)
395 		warning(expr->pos, "division by zero");
396 	return 0;
397 }
398 
simplify_float_cmp(struct expression * expr,struct symbol * ctype)399 static int simplify_float_cmp(struct expression *expr, struct symbol *ctype)
400 {
401 	struct expression *left = expr->left, *right = expr->right;
402 	long double l, r;
403 
404 	if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE)
405 		return 0;
406 
407 	l = left->fvalue;
408 	r = right->fvalue;
409 	switch (expr->op) {
410 	case '<':		expr->value = l < r; break;
411 	case '>':		expr->value = l > r; break;
412 	case SPECIAL_LTE:	expr->value = l <= r; break;
413 	case SPECIAL_GTE:	expr->value = l >= r; break;
414 	case SPECIAL_EQUAL:	expr->value = l == r; break;
415 	case SPECIAL_NOTEQUAL:	expr->value = l != r; break;
416 	}
417 	expr->type = EXPR_VALUE;
418 	expr->taint = 0;
419 	return 1;
420 }
421 
expand_binop(struct expression * expr)422 static int expand_binop(struct expression *expr)
423 {
424 	int cost;
425 
426 	cost = expand_expression(expr->left);
427 	cost += expand_expression(expr->right);
428 	if (simplify_int_binop(expr, expr->ctype))
429 		return 0;
430 	if (simplify_float_binop(expr))
431 		return 0;
432 	return cost + 1;
433 }
434 
expand_logical(struct expression * expr)435 static int expand_logical(struct expression *expr)
436 {
437 	struct expression *left = expr->left;
438 	struct expression *right;
439 	int cost, rcost;
440 
441 	/* Do immediate short-circuiting ... */
442 	cost = expand_expression(left);
443 	if (left->type == EXPR_VALUE) {
444 		if (expr->op == SPECIAL_LOGICAL_AND) {
445 			if (!left->value) {
446 				expr->type = EXPR_VALUE;
447 				expr->value = 0;
448 				expr->taint = left->taint;
449 				return 0;
450 			}
451 		} else {
452 			if (left->value) {
453 				expr->type = EXPR_VALUE;
454 				expr->value = 1;
455 				expr->taint = left->taint;
456 				return 0;
457 			}
458 		}
459 	}
460 
461 	right = expr->right;
462 	rcost = expand_expression(right);
463 	if (left->type == EXPR_VALUE && right->type == EXPR_VALUE) {
464 		/*
465 		 * We know the left value doesn't matter, since
466 		 * otherwise we would have short-circuited it..
467 		 */
468 		expr->type = EXPR_VALUE;
469 		expr->value = right->value != 0;
470 		expr->taint = left->taint | right->taint;
471 		return 0;
472 	}
473 
474 	/*
475 	 * If the right side is safe and cheaper than a branch,
476 	 * just avoid the branch and turn it into a regular binop
477 	 * style SAFELOGICAL.
478 	 */
479 	if (rcost < BRANCH_COST) {
480 		expr->type = EXPR_BINOP;
481 		rcost -= BRANCH_COST - 1;
482 	}
483 
484 	return cost + BRANCH_COST + rcost;
485 }
486 
expand_comma(struct expression * expr)487 static int expand_comma(struct expression *expr)
488 {
489 	int cost;
490 
491 	cost = expand_expression(expr->left);
492 	cost += expand_expression(expr->right);
493 	if (expr->left->type == EXPR_VALUE || expr->left->type == EXPR_FVALUE) {
494 		unsigned flags = expr->flags;
495 		unsigned taint;
496 		taint = expr->left->type == EXPR_VALUE ? expr->left->taint : 0;
497 		*expr = *expr->right;
498 		expr->flags = flags;
499 		if (expr->type == EXPR_VALUE)
500 			expr->taint |= Taint_comma | taint;
501 	}
502 	return cost;
503 }
504 
505 #define MOD_IGN (MOD_QUALIFIER)
506 
compare_types(int op,struct symbol * left,struct symbol * right)507 static int compare_types(int op, struct symbol *left, struct symbol *right)
508 {
509 	struct ctype c1 = {.base_type = left};
510 	struct ctype c2 = {.base_type = right};
511 	switch (op) {
512 	case SPECIAL_EQUAL:
513 		return !type_difference(&c1, &c2, MOD_IGN, MOD_IGN);
514 	case SPECIAL_NOTEQUAL:
515 		return type_difference(&c1, &c2, MOD_IGN, MOD_IGN) != NULL;
516 	case '<':
517 		return left->bit_size < right->bit_size;
518 	case '>':
519 		return left->bit_size > right->bit_size;
520 	case SPECIAL_LTE:
521 		return left->bit_size <= right->bit_size;
522 	case SPECIAL_GTE:
523 		return left->bit_size >= right->bit_size;
524 	}
525 	return 0;
526 }
527 
expand_compare(struct expression * expr)528 static int expand_compare(struct expression *expr)
529 {
530 	struct expression *left = expr->left, *right = expr->right;
531 	int cost;
532 
533 	cost = expand_expression(left);
534 	cost += expand_expression(right);
535 
536 	if (left && right) {
537 		/* Type comparison? */
538 		if (left->type == EXPR_TYPE && right->type == EXPR_TYPE) {
539 			int op = expr->op;
540 			expr->type = EXPR_VALUE;
541 			expr->value = compare_types(op, left->symbol, right->symbol);
542 			expr->taint = 0;
543 			return 0;
544 		}
545 		if (simplify_cmp_binop(expr, left->ctype))
546 			return 0;
547 		if (simplify_float_cmp(expr, left->ctype))
548 			return 0;
549 	}
550 	return cost + 1;
551 }
552 
expand_conditional(struct expression * expr)553 static int expand_conditional(struct expression *expr)
554 {
555 	struct expression *cond = expr->conditional;
556 	struct expression *valt = expr->cond_true;
557 	struct expression *valf = expr->cond_false;
558 	int cost, cond_cost;
559 
560 	cond_cost = expand_expression(cond);
561 	if (cond->type == EXPR_VALUE) {
562 		unsigned flags = expr->flags;
563 		if (!cond->value)
564 			valt = valf;
565 		if (!valt)
566 			valt = cond;
567 		cost = expand_expression(valt);
568 		*expr = *valt;
569 		expr->flags = flags;
570 		if (expr->type == EXPR_VALUE)
571 			expr->taint |= cond->taint;
572 		return cost;
573 	}
574 
575 	cost = expand_expression(valt);
576 	cost += expand_expression(valf);
577 
578 	if (cost < SELECT_COST) {
579 		expr->type = EXPR_SELECT;
580 		cost -= BRANCH_COST - 1;
581 	}
582 
583 	return cost + cond_cost + BRANCH_COST;
584 }
585 
check_assignment(struct expression * expr)586 static void check_assignment(struct expression *expr)
587 {
588 	struct expression *right;
589 
590 	switch (expr->op) {
591 	case SPECIAL_SHL_ASSIGN:
592 	case SPECIAL_SHR_ASSIGN:
593 		right = expr->right;
594 		if (right->type != EXPR_VALUE)
595 			break;
596 		check_shift_count(expr, right);
597 		break;
598 	}
599 	return;
600 }
601 
expand_assignment(struct expression * expr)602 static int expand_assignment(struct expression *expr)
603 {
604 	expand_expression(expr->left);
605 	expand_expression(expr->right);
606 
607 	if (!conservative)
608 		check_assignment(expr);
609 	return SIDE_EFFECTS;
610 }
611 
expand_addressof(struct expression * expr)612 static int expand_addressof(struct expression *expr)
613 {
614 	return expand_expression(expr->unop);
615 }
616 
617 /*
618  * Look up a trustable initializer value at the requested offset.
619  *
620  * Return NULL if no such value can be found or statically trusted.
621  *
622  * FIXME!! We should check that the size is right!
623  */
constant_symbol_value(struct symbol * sym,int offset)624 static struct expression *constant_symbol_value(struct symbol *sym, int offset)
625 {
626 	struct expression *value;
627 
628 	if (sym->ctype.modifiers & MOD_ACCESS)
629 		return NULL;
630 	value = sym->initializer;
631 	if (!value)
632 		return NULL;
633 	if (value->type == EXPR_INITIALIZER) {
634 		struct expression *entry;
635 		FOR_EACH_PTR(value->expr_list, entry) {
636 			if (entry->type != EXPR_POS) {
637 				if (offset)
638 					continue;
639 				return entry;
640 			}
641 			if (entry->init_offset < offset)
642 				continue;
643 			if (entry->init_offset > offset)
644 				return NULL;
645 			return entry->init_expr;
646 		} END_FOR_EACH_PTR(entry);
647 		return NULL;
648 	}
649 	return value;
650 }
651 
expand_dereference(struct expression * expr)652 static int expand_dereference(struct expression *expr)
653 {
654 	struct expression *unop = expr->unop;
655 	unsigned int offset;
656 
657 	expand_expression(unop);
658 
659 	/*
660 	 * NOTE! We get a bogus warning right now for some special
661 	 * cases: apparently I've screwed up the optimization of
662 	 * a zero-offset dereference, and the ctype is wrong.
663 	 *
664 	 * Leave the warning in anyway, since this is also a good
665 	 * test for me to get the type evaluation right..
666 	 */
667 	if (expr->ctype->ctype.modifiers & MOD_NODEREF)
668 		warning(unop->pos, "dereference of noderef expression");
669 
670 	/*
671 	 * Is it "symbol" or "symbol + offset"?
672 	 */
673 	offset = 0;
674 	if (unop->type == EXPR_BINOP && unop->op == '+') {
675 		struct expression *right = unop->right;
676 		if (right->type == EXPR_VALUE) {
677 			offset = right->value;
678 			unop = unop->left;
679 		}
680 	}
681 
682 	if (unop->type == EXPR_SYMBOL) {
683 		struct symbol *sym = unop->symbol;
684 		struct expression *value = constant_symbol_value(sym, offset);
685 
686 		/* Const symbol with a constant initializer? */
687 		if (value) {
688 			/* FIXME! We should check that the size is right! */
689 			if (value->type == EXPR_VALUE) {
690 				if (is_bitfield_type(value->ctype))
691 					return UNSAFE;
692 				expr->type = EXPR_VALUE;
693 				expr->value = value->value;
694 				expr->taint = 0;
695 				return 0;
696 			} else if (value->type == EXPR_FVALUE) {
697 				expr->type = EXPR_FVALUE;
698 				expr->fvalue = value->fvalue;
699 				return 0;
700 			}
701 		}
702 
703 		/* Direct symbol dereference? Cheap and safe */
704 		return (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN)) ? 2 : 1;
705 	}
706 
707 	return UNSAFE;
708 }
709 
simplify_preop(struct expression * expr)710 static int simplify_preop(struct expression *expr)
711 {
712 	struct expression *op = expr->unop;
713 	unsigned long long v, mask;
714 
715 	if (op->type != EXPR_VALUE)
716 		return 0;
717 
718 	mask = 1ULL << (expr->ctype->bit_size-1);
719 	v = op->value;
720 	switch (expr->op) {
721 	case '+': break;
722 	case '-':
723 		if (v == mask && !(expr->ctype->ctype.modifiers & MOD_UNSIGNED))
724 			goto Overflow;
725 		v = -v;
726 		break;
727 	case '!': v = !v; break;
728 	case '~': v = ~v; break;
729 	default: return 0;
730 	}
731 	mask = mask | (mask-1);
732 	expr->value = v & mask;
733 	expr->type = EXPR_VALUE;
734 	expr->taint = op->taint;
735 	return 1;
736 
737 Overflow:
738 	if (!conservative)
739 		warning(expr->pos, "constant integer operation overflow");
740 	return 0;
741 }
742 
simplify_float_preop(struct expression * expr)743 static int simplify_float_preop(struct expression *expr)
744 {
745 	struct expression *op = expr->unop;
746 	long double v;
747 
748 	if (op->type != EXPR_FVALUE)
749 		return 0;
750 	v = op->fvalue;
751 	switch (expr->op) {
752 	case '+': break;
753 	case '-': v = -v; break;
754 	default: return 0;
755 	}
756 	expr->fvalue = v;
757 	expr->type = EXPR_FVALUE;
758 	return 1;
759 }
760 
761 /*
762  * Unary post-ops: x++ and x--
763  */
expand_postop(struct expression * expr)764 static int expand_postop(struct expression *expr)
765 {
766 	expand_expression(expr->unop);
767 	return SIDE_EFFECTS;
768 }
769 
expand_preop(struct expression * expr)770 static int expand_preop(struct expression *expr)
771 {
772 	int cost;
773 
774 	switch (expr->op) {
775 	case '*':
776 		return expand_dereference(expr);
777 
778 	case '&':
779 		return expand_addressof(expr);
780 
781 	case SPECIAL_INCREMENT:
782 	case SPECIAL_DECREMENT:
783 		/*
784 		 * From a type evaluation standpoint the preops are
785 		 * the same as the postops
786 		 */
787 		return expand_postop(expr);
788 
789 	default:
790 		break;
791 	}
792 	cost = expand_expression(expr->unop);
793 
794 	if (simplify_preop(expr))
795 		return 0;
796 	if (simplify_float_preop(expr))
797 		return 0;
798 	return cost + 1;
799 }
800 
expand_arguments(struct expression_list * head)801 static int expand_arguments(struct expression_list *head)
802 {
803 	int cost = 0;
804 	struct expression *expr;
805 
806 	FOR_EACH_PTR (head, expr) {
807 		cost += expand_expression(expr);
808 	} END_FOR_EACH_PTR(expr);
809 	return cost;
810 }
811 
expand_cast(struct expression * expr)812 static int expand_cast(struct expression *expr)
813 {
814 	int cost;
815 	struct expression *target = expr->cast_expression;
816 
817 	cost = expand_expression(target);
818 
819 	/* Simplify normal integer casts.. */
820 	if (target->type == EXPR_VALUE || target->type == EXPR_FVALUE) {
821 		cast_value(expr, expr->ctype, target, target->ctype);
822 		return 0;
823 	}
824 	return cost + 1;
825 }
826 
827 /*
828  * expand a call expression with a symbol. This
829  * should expand builtins.
830  */
expand_symbol_call(struct expression * expr,int cost)831 static int expand_symbol_call(struct expression *expr, int cost)
832 {
833 	struct expression *fn = expr->fn;
834 	struct symbol *ctype = fn->ctype;
835 
836 	expand_expression(fn);
837 
838 	if (fn->type != EXPR_PREOP)
839 		return SIDE_EFFECTS;
840 
841 	if (ctype->op && ctype->op->expand)
842 		return ctype->op->expand(expr, cost);
843 
844 	if (ctype->ctype.modifiers & MOD_PURE)
845 		return cost + 1;
846 
847 	return SIDE_EFFECTS;
848 }
849 
expand_call(struct expression * expr)850 static int expand_call(struct expression *expr)
851 {
852 	int cost;
853 	struct symbol *sym;
854 	struct expression *fn = expr->fn;
855 
856 	cost = expand_arguments(expr->args);
857 	sym = fn->ctype;
858 	if (!sym) {
859 		expression_error(expr, "function has no type");
860 		return SIDE_EFFECTS;
861 	}
862 	if (sym->type == SYM_NODE)
863 		return expand_symbol_call(expr, cost);
864 
865 	return SIDE_EFFECTS;
866 }
867 
expand_expression_list(struct expression_list * list)868 static int expand_expression_list(struct expression_list *list)
869 {
870 	int cost = 0;
871 	struct expression *expr;
872 
873 	FOR_EACH_PTR(list, expr) {
874 		cost += expand_expression(expr);
875 	} END_FOR_EACH_PTR(expr);
876 	return cost;
877 }
878 
879 /*
880  * We can simplify nested position expressions if
881  * this is a simple (single) positional expression.
882  */
expand_pos_expression(struct expression * expr)883 static int expand_pos_expression(struct expression *expr)
884 {
885 	struct expression *nested = expr->init_expr;
886 	unsigned long offset = expr->init_offset;
887 	int nr = expr->init_nr;
888 
889 	if (nr == 1) {
890 		switch (nested->type) {
891 		case EXPR_POS:
892 			offset += nested->init_offset;
893 			*expr = *nested;
894 			expr->init_offset = offset;
895 			nested = expr;
896 			break;
897 
898 		case EXPR_INITIALIZER: {
899 			struct expression *reuse = nested, *entry;
900 			*expr = *nested;
901 			FOR_EACH_PTR(expr->expr_list, entry) {
902 				if (entry->type == EXPR_POS) {
903 					entry->init_offset += offset;
904 				} else {
905 					if (!reuse) {
906 						/*
907 						 * This happens rarely, but it can happen
908 						 * with bitfields that are all at offset
909 						 * zero..
910 						 */
911 						reuse = alloc_expression(entry->pos, EXPR_POS);
912 					}
913 					reuse->type = EXPR_POS;
914 					reuse->ctype = entry->ctype;
915 					reuse->init_offset = offset;
916 					reuse->init_nr = 1;
917 					reuse->init_expr = entry;
918 					REPLACE_CURRENT_PTR(entry, reuse);
919 					reuse = NULL;
920 				}
921 			} END_FOR_EACH_PTR(entry);
922 			nested = expr;
923 			break;
924 		}
925 
926 		default:
927 			break;
928 		}
929 	}
930 	return expand_expression(nested);
931 }
932 
bit_offset(const struct expression * expr)933 static unsigned long bit_offset(const struct expression *expr)
934 {
935 	unsigned long offset = 0;
936 	while (expr->type == EXPR_POS) {
937 		offset += bytes_to_bits(expr->init_offset);
938 		expr = expr->init_expr;
939 	}
940 	if (expr && expr->ctype)
941 		offset += expr->ctype->bit_offset;
942 	return offset;
943 }
944 
bit_range(const struct expression * expr)945 static unsigned long bit_range(const struct expression *expr)
946 {
947 	unsigned long range = 0;
948 	unsigned long size = 0;
949 	while (expr->type == EXPR_POS) {
950 		unsigned long nr = expr->init_nr;
951 		size = expr->ctype->bit_size;
952 		range += (nr - 1) * size;
953 		expr = expr->init_expr;
954 	}
955 	range += size;
956 	return range;
957 }
958 
compare_expressions(const void * _a,const void * _b)959 static int compare_expressions(const void *_a, const void *_b)
960 {
961 	const struct expression *a = _a;
962 	const struct expression *b = _b;
963 	unsigned long a_pos = bit_offset(a);
964 	unsigned long b_pos = bit_offset(b);
965 
966 	return (a_pos < b_pos) ? -1 : (a_pos == b_pos) ? 0 : 1;
967 }
968 
sort_expression_list(struct expression_list ** list)969 static void sort_expression_list(struct expression_list **list)
970 {
971 	sort_list((struct ptr_list **)list, compare_expressions);
972 }
973 
verify_nonoverlapping(struct expression_list ** list,struct expression * expr)974 static void verify_nonoverlapping(struct expression_list **list, struct expression *expr)
975 {
976 	struct expression *a = NULL;
977 	unsigned long max = 0;
978 	unsigned long whole = expr->ctype->bit_size;
979 	struct expression *b;
980 
981 	if (!Woverride_init)
982 		return;
983 
984 	FOR_EACH_PTR(*list, b) {
985 		unsigned long off, end;
986 		if (!b->ctype || !b->ctype->bit_size)
987 			continue;
988 		off = bit_offset(b);
989 		if (a && off < max) {
990 			warning(a->pos, "Initializer entry defined twice");
991 			info(b->pos, "  also defined here");
992 			if (!Woverride_init_all)
993 				return;
994 		}
995 		end = off + bit_range(b);
996 		if (!a && !Woverride_init_whole_range) {
997 			// If first entry is the whole range, do not let
998 			// any warning about it (this allow to initialize
999 			// an array with some default value and then override
1000 			// some specific entries).
1001 			if (off == 0 && end == whole)
1002 				continue;
1003 		}
1004 		if (end > max) {
1005 			max = end;
1006 			a = b;
1007 		}
1008 	} END_FOR_EACH_PTR(b);
1009 }
1010 
expand_expression(struct expression * expr)1011 static int expand_expression(struct expression *expr)
1012 {
1013 	if (!expr)
1014 		return 0;
1015 	if (!expr->ctype || expr->ctype == &bad_ctype)
1016 		return UNSAFE;
1017 
1018 	switch (expr->type) {
1019 	case EXPR_VALUE:
1020 	case EXPR_FVALUE:
1021 	case EXPR_STRING:
1022 		return 0;
1023 	case EXPR_TYPE:
1024 	case EXPR_SYMBOL:
1025 		return expand_symbol_expression(expr);
1026 	case EXPR_BINOP:
1027 		return expand_binop(expr);
1028 
1029 	case EXPR_LOGICAL:
1030 		return expand_logical(expr);
1031 
1032 	case EXPR_COMMA:
1033 		return expand_comma(expr);
1034 
1035 	case EXPR_COMPARE:
1036 		return expand_compare(expr);
1037 
1038 	case EXPR_ASSIGNMENT:
1039 		return expand_assignment(expr);
1040 
1041 	case EXPR_PREOP:
1042 		return expand_preop(expr);
1043 
1044 	case EXPR_POSTOP:
1045 		return expand_postop(expr);
1046 
1047 	case EXPR_CAST:
1048 	case EXPR_FORCE_CAST:
1049 	case EXPR_IMPLIED_CAST:
1050 		return expand_cast(expr);
1051 
1052 	case EXPR_CALL:
1053 		return expand_call(expr);
1054 
1055 	case EXPR_DEREF:
1056 		warning(expr->pos, "we should not have an EXPR_DEREF left at expansion time");
1057 		return UNSAFE;
1058 
1059 	case EXPR_SELECT:
1060 	case EXPR_CONDITIONAL:
1061 		return expand_conditional(expr);
1062 
1063 	case EXPR_STATEMENT: {
1064 		struct statement *stmt = expr->statement;
1065 		int cost = expand_statement(stmt);
1066 
1067 		if (stmt->type == STMT_EXPRESSION && stmt->expression)
1068 			*expr = *stmt->expression;
1069 		return cost;
1070 	}
1071 
1072 	case EXPR_LABEL:
1073 		return 0;
1074 
1075 	case EXPR_INITIALIZER:
1076 		sort_expression_list(&expr->expr_list);
1077 		verify_nonoverlapping(&expr->expr_list, expr);
1078 		return expand_expression_list(expr->expr_list);
1079 
1080 	case EXPR_IDENTIFIER:
1081 		return UNSAFE;
1082 
1083 	case EXPR_INDEX:
1084 		return UNSAFE;
1085 
1086 	case EXPR_SLICE:
1087 		return expand_expression(expr->base) + 1;
1088 
1089 	case EXPR_POS:
1090 		return expand_pos_expression(expr);
1091 
1092 	case EXPR_SIZEOF:
1093 	case EXPR_PTRSIZEOF:
1094 	case EXPR_ALIGNOF:
1095 	case EXPR_OFFSETOF:
1096 		expression_error(expr, "internal front-end error: sizeof in expansion?");
1097 		return UNSAFE;
1098 	case EXPR_ASM_OPERAND:
1099 		expression_error(expr, "internal front-end error: ASM_OPERAND in expansion?");
1100 		return UNSAFE;
1101 	}
1102 	return SIDE_EFFECTS;
1103 }
1104 
expand_const_expression(struct expression * expr,const char * where)1105 static void expand_const_expression(struct expression *expr, const char *where)
1106 {
1107 	if (expr) {
1108 		expand_expression(expr);
1109 		if (expr->type != EXPR_VALUE)
1110 			expression_error(expr, "Expected constant expression in %s", where);
1111 	}
1112 }
1113 
expand_symbol(struct symbol * sym)1114 int expand_symbol(struct symbol *sym)
1115 {
1116 	int retval;
1117 	struct symbol *base_type;
1118 
1119 	if (!sym)
1120 		return 0;
1121 	base_type = sym->ctype.base_type;
1122 	if (!base_type)
1123 		return 0;
1124 
1125 	retval = expand_expression(sym->initializer);
1126 	/* expand the body of the symbol */
1127 	if (base_type->type == SYM_FN) {
1128 		if (base_type->stmt)
1129 			expand_statement(base_type->stmt);
1130 	}
1131 	return retval;
1132 }
1133 
expand_return_expression(struct statement * stmt)1134 static void expand_return_expression(struct statement *stmt)
1135 {
1136 	expand_expression(stmt->expression);
1137 }
1138 
expand_if_statement(struct statement * stmt)1139 static int expand_if_statement(struct statement *stmt)
1140 {
1141 	struct expression *expr = stmt->if_conditional;
1142 
1143 	if (!expr || !expr->ctype || expr->ctype == &bad_ctype)
1144 		return UNSAFE;
1145 
1146 	expand_expression(expr);
1147 
1148 /* This is only valid if nobody jumps into the "dead" side */
1149 #if 0
1150 	/* Simplify constant conditionals without even evaluating the false side */
1151 	if (expr->type == EXPR_VALUE) {
1152 		struct statement *simple;
1153 		simple = expr->value ? stmt->if_true : stmt->if_false;
1154 
1155 		/* Nothing? */
1156 		if (!simple) {
1157 			stmt->type = STMT_NONE;
1158 			return 0;
1159 		}
1160 		expand_statement(simple);
1161 		*stmt = *simple;
1162 		return SIDE_EFFECTS;
1163 	}
1164 #endif
1165 	expand_statement(stmt->if_true);
1166 	expand_statement(stmt->if_false);
1167 	return SIDE_EFFECTS;
1168 }
1169 
1170 /*
1171  * Expanding a compound statement is really just
1172  * about adding up the costs of each individual
1173  * statement.
1174  *
1175  * We also collapse a simple compound statement:
1176  * this would trigger for simple inline functions,
1177  * except we would have to check the "return"
1178  * symbol usage. Next time.
1179  */
expand_compound(struct statement * stmt)1180 static int expand_compound(struct statement *stmt)
1181 {
1182 	struct statement *s, *last;
1183 	int cost, statements;
1184 
1185 	if (stmt->ret)
1186 		expand_symbol(stmt->ret);
1187 
1188 	last = stmt->args;
1189 	cost = expand_statement(last);
1190 	statements = last != NULL;
1191 	FOR_EACH_PTR(stmt->stmts, s) {
1192 		statements++;
1193 		last = s;
1194 		cost += expand_statement(s);
1195 	} END_FOR_EACH_PTR(s);
1196 
1197 	if (statements == 1 && !stmt->ret)
1198 		*stmt = *last;
1199 
1200 	return cost;
1201 }
1202 
expand_statement(struct statement * stmt)1203 static int expand_statement(struct statement *stmt)
1204 {
1205 	if (!stmt)
1206 		return 0;
1207 
1208 	switch (stmt->type) {
1209 	case STMT_DECLARATION: {
1210 		struct symbol *sym;
1211 		FOR_EACH_PTR(stmt->declaration, sym) {
1212 			expand_symbol(sym);
1213 		} END_FOR_EACH_PTR(sym);
1214 		return SIDE_EFFECTS;
1215 	}
1216 
1217 	case STMT_RETURN:
1218 		expand_return_expression(stmt);
1219 		return SIDE_EFFECTS;
1220 
1221 	case STMT_EXPRESSION:
1222 		return expand_expression(stmt->expression);
1223 
1224 	case STMT_COMPOUND:
1225 		return expand_compound(stmt);
1226 
1227 	case STMT_IF:
1228 		return expand_if_statement(stmt);
1229 
1230 	case STMT_ITERATOR:
1231 		expand_expression(stmt->iterator_pre_condition);
1232 		expand_expression(stmt->iterator_post_condition);
1233 		expand_statement(stmt->iterator_pre_statement);
1234 		expand_statement(stmt->iterator_statement);
1235 		expand_statement(stmt->iterator_post_statement);
1236 		return SIDE_EFFECTS;
1237 
1238 	case STMT_SWITCH:
1239 		expand_expression(stmt->switch_expression);
1240 		expand_statement(stmt->switch_statement);
1241 		return SIDE_EFFECTS;
1242 
1243 	case STMT_CASE:
1244 		expand_const_expression(stmt->case_expression, "case statement");
1245 		expand_const_expression(stmt->case_to, "case statement");
1246 		expand_statement(stmt->case_statement);
1247 		return SIDE_EFFECTS;
1248 
1249 	case STMT_LABEL:
1250 		expand_statement(stmt->label_statement);
1251 		return SIDE_EFFECTS;
1252 
1253 	case STMT_GOTO:
1254 		expand_expression(stmt->goto_expression);
1255 		return SIDE_EFFECTS;
1256 
1257 	case STMT_NONE:
1258 		break;
1259 	case STMT_ASM:
1260 		/* FIXME! Do the asm parameter evaluation! */
1261 		break;
1262 	case STMT_CONTEXT:
1263 		expand_expression(stmt->expression);
1264 		break;
1265 	case STMT_RANGE:
1266 		expand_expression(stmt->range_expression);
1267 		expand_expression(stmt->range_low);
1268 		expand_expression(stmt->range_high);
1269 		break;
1270 	}
1271 	return SIDE_EFFECTS;
1272 }
1273 
bad_integer_constant_expression(struct expression * expr)1274 static inline int bad_integer_constant_expression(struct expression *expr)
1275 {
1276 	if (!(expr->flags & CEF_ICE))
1277 		return 1;
1278 	if (expr->taint & Taint_comma)
1279 		return 1;
1280 	return 0;
1281 }
1282 
__get_expression_value(struct expression * expr,int strict)1283 static long long __get_expression_value(struct expression *expr, int strict)
1284 {
1285 	long long value, mask;
1286 	struct symbol *ctype;
1287 
1288 	if (!expr)
1289 		return 0;
1290 	ctype = evaluate_expression(expr);
1291 	if (!ctype) {
1292 		expression_error(expr, "bad constant expression type");
1293 		return 0;
1294 	}
1295 	expand_expression(expr);
1296 	if (expr->type != EXPR_VALUE) {
1297 		if (strict != 2)
1298 			expression_error(expr, "bad constant expression");
1299 		return 0;
1300 	}
1301 #if 0	// This complains about "1 ? 1 :__bits_per()" which the kernel use
1302 	if ((strict == 1) && bad_integer_constant_expression(expr)) {
1303 		expression_error(expr, "bad integer constant expression");
1304 		return 0;
1305 	}
1306 #endif
1307 
1308 	value = expr->value;
1309 	mask = 1ULL << (ctype->bit_size-1);
1310 
1311 	if (value & mask) {
1312 		while (ctype->type != SYM_BASETYPE)
1313 			ctype = ctype->ctype.base_type;
1314 		if (!(ctype->ctype.modifiers & MOD_UNSIGNED))
1315 			value = value | mask | ~(mask-1);
1316 	}
1317 	return value;
1318 }
1319 
get_expression_value(struct expression * expr)1320 long long get_expression_value(struct expression *expr)
1321 {
1322 	return __get_expression_value(expr, 0);
1323 }
1324 
const_expression_value(struct expression * expr)1325 long long const_expression_value(struct expression *expr)
1326 {
1327 	return __get_expression_value(expr, 1);
1328 }
1329 
get_expression_value_silent(struct expression * expr)1330 long long get_expression_value_silent(struct expression *expr)
1331 {
1332 
1333 	return __get_expression_value(expr, 2);
1334 }
1335 
expr_truth_value(struct expression * expr)1336 int expr_truth_value(struct expression *expr)
1337 {
1338 	const int saved = conservative;
1339 	struct symbol *ctype;
1340 
1341 	if (!expr)
1342 		return 0;
1343 
1344 	ctype = evaluate_expression(expr);
1345 	if (!ctype)
1346 		return -1;
1347 
1348 	conservative = 1;
1349 	expand_expression(expr);
1350 	conservative = saved;
1351 
1352 redo:
1353 	switch (expr->type) {
1354 	case EXPR_COMMA:
1355 		expr = expr->right;
1356 		goto redo;
1357 	case EXPR_VALUE:
1358 		return expr->value != 0;
1359 	case EXPR_FVALUE:
1360 		return expr->fvalue != 0;
1361 	default:
1362 		return -1;
1363 	}
1364 }
1365 
is_zero_constant(struct expression * expr)1366 int is_zero_constant(struct expression *expr)
1367 {
1368 	const int saved = conservative;
1369 	conservative = 1;
1370 	expand_expression(expr);
1371 	conservative = saved;
1372 	return expr->type == EXPR_VALUE && !expr->value;
1373 }
1374