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