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