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