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