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