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