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