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