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