?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[PATCH] clean up usual_conversions(), kill evaluate_shift()
[smatch.git] / expand.c
bloba46f1c248fa72e274da2786dcdecf604aa769dfe
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 if (left && right) {
467 /* Type comparison? */
468 if (left->type == EXPR_TYPE && right->type == EXPR_TYPE) {
469 int op = expr->op;
470 expr->type = EXPR_VALUE;
471 expr->value = compare_types(op, left->symbol, right->symbol);
472 return 0;
473 }
474 if (simplify_cmp_binop(expr, left->ctype))
475 return 0;
476 if (simplify_float_cmp(expr, left->ctype))
477 return 0;
478 }
479 return cost + 1;
480 }
481
482 static int expand_conditional(struct expression *expr)
483 {
484 struct expression *cond = expr->conditional;
485 struct expression *true = expr->cond_true;
486 struct expression *false = expr->cond_false;
487 int cost, cond_cost;
488
489 cond_cost = expand_expression(cond);
490 if (cond->type == EXPR_VALUE) {
491 if (!cond->value)
492 true = false;
493 if (!true)
494 true = cond;
495 *expr = *true;
496 return expand_expression(expr);
497 }
498
499 cost = expand_expression(true);
500 cost += expand_expression(false);
501
502 if (cost < SELECT_COST) {
503 expr->type = EXPR_SELECT;
504 cost -= BRANCH_COST - 1;
505 }
506
507 return cost + cond_cost + BRANCH_COST;
508 }
509
510 static int expand_assignment(struct expression *expr)
511 {
512 expand_expression(expr->left);
513 expand_expression(expr->right);
514 return SIDE_EFFECTS;
515 }
516
517 static int expand_addressof(struct expression *expr)
518 {
519 return expand_expression(expr->unop);
520 }
521
522 /*
523 * Look up a trustable initializer value at the requested offset.
524 *
525 * Return NULL if no such value can be found or statically trusted.
526 *
527 * FIXME!! We should check that the size is right!
528 */
529 static struct expression *constant_symbol_value(struct symbol *sym, int offset)
530 {
531 struct expression *value;
532
533 if (sym->ctype.modifiers & (MOD_ASSIGNED | MOD_ADDRESSABLE))
534 return NULL;
535 value = sym->initializer;
536 if (!value)
537 return NULL;
538 if (value->type == EXPR_INITIALIZER) {
539 struct expression *entry;
540 FOR_EACH_PTR(value->expr_list, entry) {
541 if (entry->type != EXPR_POS) {
542 if (offset)
543 continue;
544 return entry;
545 }
546 if (entry->init_offset < offset)
547 continue;
548 if (entry->init_offset > offset)
549 return NULL;
550 return entry->init_expr;
551 } END_FOR_EACH_PTR(entry);
552 return NULL;
553 }
554 return value;
555 }
556
557 static int expand_dereference(struct expression *expr)
558 {
559 struct expression *unop = expr->unop;
560 unsigned int offset;
561
562 expand_expression(unop);
563
564 /*
565 * NOTE! We get a bogus warning right now for some special
566 * cases: apparently I've screwed up the optimization of
567 * a zero-offset dereference, and the ctype is wrong.
568 *
569 * Leave the warning in anyway, since this is also a good
570 * test for me to get the type evaluation right..
571 */
572 if (expr->ctype->ctype.modifiers & MOD_NODEREF)
573 warning(unop->pos, "dereference of noderef expression");
574
575 /*
576 * Is it "symbol" or "symbol + offset"?
577 */
578 offset = 0;
579 if (unop->type == EXPR_BINOP && unop->op == '+') {
580 struct expression *right = unop->right;
581 if (right->type == EXPR_VALUE) {
582 offset = right->value;
583 unop = unop->left;
584 }
585 }
586
587 if (unop->type == EXPR_SYMBOL) {
588 struct symbol *sym = unop->symbol;
589 struct expression *value = constant_symbol_value(sym, offset);
590
591 /* Const symbol with a constant initializer? */
592 if (value) {
593 /* FIXME! We should check that the size is right! */
594 if (value->type == EXPR_VALUE) {
595 expr->type = EXPR_VALUE;
596 expr->value = value->value;
597 return 0;
598 } else if (value->type == EXPR_FVALUE) {
599 expr->type = EXPR_FVALUE;
600 expr->fvalue = value->fvalue;
601 return 0;
602 }
603 }
604
605 /* Direct symbol dereference? Cheap and safe */
606 return (sym->ctype.modifiers & (MOD_STATIC | MOD_EXTERN)) ? 2 : 1;
607 }
608
609 return UNSAFE;
610 }
611
612 static int simplify_preop(struct expression *expr)
613 {
614 struct expression *op = expr->unop;
615 unsigned long long v, mask;
616
617 if (op->type != EXPR_VALUE)
618 return 0;
619
620 mask = 1ULL << (expr->ctype->bit_size-1);
621 v = op->value;
622 switch (expr->op) {
623 case '+': break;
624 case '-':
625 if (v == mask && !(expr->ctype->ctype.modifiers & MOD_UNSIGNED))
626 goto Overflow;
627 v = -v;
628 break;
629 case '!': v = !v; break;
630 case '~': v = ~v; break;
631 default: return 0;
632 }
633 mask = mask | (mask-1);
634 expr->value = v & mask;
635 expr->type = EXPR_VALUE;
636 return 1;
637
638 Overflow:
639 warning(expr->pos, "constant integer operation overflow");
640 return 0;
641 }
642
643 static int simplify_float_preop(struct expression *expr)
644 {
645 struct expression *op = expr->unop;
646 long double v;
647
648 if (op->type != EXPR_FVALUE)
649 return 0;
650 v = op->fvalue;
651 switch (expr->op) {
652 case '+': break;
653 case '-': v = -v; break;
654 default: return 0;
655 }
656 expr->fvalue = v;
657 expr->type = EXPR_FVALUE;
658 return 1;
659 }
660
661 /*
662 * Unary post-ops: x++ and x--
663 */
664 static int expand_postop(struct expression *expr)
665 {
666 expand_expression(expr->unop);
667 return SIDE_EFFECTS;
668 }
669
670 static int expand_preop(struct expression *expr)
671 {
672 int cost;
673
674 switch (expr->op) {
675 case '*':
676 return expand_dereference(expr);
677
678 case '&':
679 return expand_addressof(expr);
680
681 case SPECIAL_INCREMENT:
682 case SPECIAL_DECREMENT:
683 /*
684 * From a type evaluation standpoint the preops are
685 * the same as the postops
686 */
687 return expand_postop(expr);
688
689 default:
690 break;
691 }
692 cost = expand_expression(expr->unop);
693
694 if (simplify_preop(expr))
695 return 0;
696 if (simplify_float_preop(expr))
697 return 0;
698 return cost + 1;
699 }
700
701 static int expand_arguments(struct expression_list *head)
702 {
703 int cost = 0;
704 struct expression *expr;
705
706 FOR_EACH_PTR (head, expr) {
707 cost += expand_expression(expr);
708 } END_FOR_EACH_PTR(expr);
709 return cost;
710 }
711
712 static int expand_cast(struct expression *expr)
713 {
714 int cost;
715 struct expression *target = expr->cast_expression;
716
717 cost = expand_expression(target);
718
719 /* Simplify normal integer casts.. */
720 if (target->type == EXPR_VALUE || target->type == EXPR_FVALUE) {
721 cast_value(expr, expr->ctype, target, target->ctype);
722 return 0;
723 }
724 return cost + 1;
725 }
726
727 /* The arguments are constant if the cost of all of them is zero */
728 int expand_constant_p(struct expression *expr, int cost)
729 {
730 expr->type = EXPR_VALUE;
731 expr->value = !cost;
732 return 0;
733 }
734
735 /* The arguments are safe, if their cost is less than SIDE_EFFECTS */
736 int expand_safe_p(struct expression *expr, int cost)
737 {
738 expr->type = EXPR_VALUE;
739 expr->value = (cost < SIDE_EFFECTS);
740 return 0;
741 }
742
743 /*
744 * expand a call expression with a symbol. This
745 * should expand builtins.
746 */
747 static int expand_symbol_call(struct expression *expr, int cost)
748 {
749 struct expression *fn = expr->fn;
750 struct symbol *ctype = fn->ctype;
751
752 if (fn->type != EXPR_PREOP)
753 return SIDE_EFFECTS;
754
755 if (ctype->op && ctype->op->expand)
756 return ctype->op->expand(expr, cost);
757
758 return SIDE_EFFECTS;
759 }
760
761 static int expand_call(struct expression *expr)
762 {
763 int cost;
764 struct symbol *sym;
765 struct expression *fn = expr->fn;
766
767 cost = expand_arguments(expr->args);
768 sym = fn->ctype;
769 if (!sym) {
770 expression_error(expr, "function has no type");
771 return SIDE_EFFECTS;
772 }
773 if (sym->type == SYM_NODE)
774 return expand_symbol_call(expr, cost);
775
776 return SIDE_EFFECTS;
777 }
778
779 static int expand_expression_list(struct expression_list *list)
780 {
781 int cost = 0;
782 struct expression *expr;
783
784 FOR_EACH_PTR(list, expr) {
785 cost += expand_expression(expr);
786 } END_FOR_EACH_PTR(expr);
787 return cost;
788 }
789
790 /*
791 * We can simplify nested position expressions if
792 * this is a simple (single) positional expression.
793 */
794 static int expand_pos_expression(struct expression *expr)
795 {
796 struct expression *nested = expr->init_expr;
797 unsigned long offset = expr->init_offset;
798 int nr = expr->init_nr;
799
800 if (nr == 1) {
801 switch (nested->type) {
802 case EXPR_POS:
803 offset += nested->init_offset;
804 *expr = *nested;
805 expr->init_offset = offset;
806 nested = expr;
807 break;
808
809 case EXPR_INITIALIZER: {
810 struct expression *reuse = nested, *entry;
811 *expr = *nested;
812 FOR_EACH_PTR(expr->expr_list, entry) {
813 if (entry->type == EXPR_POS) {
814 entry->init_offset += offset;
815 } else {
816 if (!reuse) {
817 /*
818 * This happens rarely, but it can happen
819 * with bitfields that are all at offset
820 * zero..
821 */
822 reuse = alloc_expression(entry->pos, EXPR_POS);
823 }
824 reuse->type = EXPR_POS;
825 reuse->ctype = entry->ctype;
826 reuse->init_offset = offset;
827 reuse->init_nr = 1;
828 reuse->init_expr = entry;
829 REPLACE_CURRENT_PTR(entry, reuse);
830 reuse = NULL;
831 }
832 } END_FOR_EACH_PTR(entry);
833 nested = expr;
834 break;
835 }
836
837 default:
838 break;
839 }
840 }
841 return expand_expression(nested);
842 }
843
844 static unsigned long bit_offset(const struct expression *expr)
845 {
846 unsigned long offset = 0;
847 while (expr->type == EXPR_POS) {
848 offset += expr->init_offset << 3;
849 expr = expr->init_expr;
850 }
851 if (expr && expr->ctype)
852 offset += expr->ctype->bit_offset;
853 return offset;
854 }
855
856 static int compare_expressions(const void *_a, const void *_b)
857 {
858 const struct expression *a = _a;
859 const struct expression *b = _b;
860 unsigned long a_pos = bit_offset(a);
861 unsigned long b_pos = bit_offset(b);
862
863 return (a_pos < b_pos) ? -1 : (a_pos == b_pos) ? 0 : 1;
864 }
865
866 static void sort_expression_list(struct expression_list **list)
867 {
868 sort_list((struct ptr_list **)list, compare_expressions);
869 }
870
871 static void verify_nonoverlapping(struct expression_list **list)
872 {
873 struct expression *a = NULL;
874 struct expression *b;
875
876 FOR_EACH_PTR(*list, b) {
877 if (!b->ctype || !b->ctype->bit_size)
878 continue;
879 if (a && bit_offset(a) == bit_offset(b)) {
880 sparse_error(a->pos, "Initializer entry defined twice");
881 info(b->pos, " also defined here");
882 return;
883 }
884 a = b;
885 } END_FOR_EACH_PTR(b);
886 }
887
888 static int expand_expression(struct expression *expr)
889 {
890 if (!expr)
891 return 0;
892 if (!expr->ctype || expr->ctype == &bad_ctype)
893 return UNSAFE;
894
895 switch (expr->type) {
896 case EXPR_VALUE:
897 case EXPR_FVALUE:
898 case EXPR_STRING:
899 return 0;
900 case EXPR_TYPE:
901 case EXPR_SYMBOL:
902 return expand_symbol_expression(expr);
903 case EXPR_BINOP:
904 return expand_binop(expr);
905
906 case EXPR_LOGICAL:
907 return expand_logical(expr);
908
909 case EXPR_COMMA:
910 return expand_comma(expr);
911
912 case EXPR_COMPARE:
913 return expand_compare(expr);
914
915 case EXPR_ASSIGNMENT:
916 return expand_assignment(expr);
917
918 case EXPR_PREOP:
919 return expand_preop(expr);
920
921 case EXPR_POSTOP:
922 return expand_postop(expr);
923
924 case EXPR_CAST:
925 case EXPR_IMPLIED_CAST:
926 return expand_cast(expr);
927
928 case EXPR_CALL:
929 return expand_call(expr);
930
931 case EXPR_DEREF:
932 warning(expr->pos, "we should not have an EXPR_DEREF left at expansion time");
933 return UNSAFE;
934
935 case EXPR_SELECT:
936 case EXPR_CONDITIONAL:
937 return expand_conditional(expr);
938
939 case EXPR_STATEMENT: {
940 struct statement *stmt = expr->statement;
941 int cost = expand_statement(stmt);
942
943 if (stmt->type == STMT_EXPRESSION && stmt->expression)
944 *expr = *stmt->expression;
945 return cost;
946 }
947
948 case EXPR_LABEL:
949 return 0;
950
951 case EXPR_INITIALIZER:
952 sort_expression_list(&expr->expr_list);
953 verify_nonoverlapping(&expr->expr_list);
954 return expand_expression_list(expr->expr_list);
955
956 case EXPR_IDENTIFIER:
957 return UNSAFE;
958
959 case EXPR_INDEX:
960 return UNSAFE;
961
962 case EXPR_SLICE:
963 return expand_expression(expr->base) + 1;
964
965 case EXPR_POS:
966 return expand_pos_expression(expr);
967
968 case EXPR_SIZEOF:
969 case EXPR_PTRSIZEOF:
970 case EXPR_ALIGNOF:
971 expression_error(expr, "internal front-end error: sizeof in expansion?");
972 return UNSAFE;
973 }
974 return SIDE_EFFECTS;
975 }
976
977 static void expand_const_expression(struct expression *expr, const char *where)
978 {
979 if (expr) {
980 expand_expression(expr);
981 if (expr->type != EXPR_VALUE)
982 expression_error(expr, "Expected constant expression in %s", where);
983 }
984 }
985
986 int expand_symbol(struct symbol *sym)
987 {
988 int retval;
989 struct symbol *base_type;
990
991 if (!sym)
992 return 0;
993 base_type = sym->ctype.base_type;
994 if (!base_type)
995 return 0;
996
997 retval = expand_expression(sym->initializer);
998 /* expand the body of the symbol */
999 if (base_type->type == SYM_FN) {
1000 if (base_type->stmt)
1001 expand_statement(base_type->stmt);
1002 }
1003 return retval;
1004 }
1005
1006 static void expand_return_expression(struct statement *stmt)
1007 {
1008 expand_expression(stmt->expression);
1009 }
1010
1011 static int expand_if_statement(struct statement *stmt)
1012 {
1013 struct expression *expr = stmt->if_conditional;
1014
1015 if (!expr || !expr->ctype || expr->ctype == &bad_ctype)
1016 return UNSAFE;
1017
1018 expand_expression(expr);
1019
1020 /* This is only valid if nobody jumps into the "dead" side */
1021 #if 0
1022 /* Simplify constant conditionals without even evaluating the false side */
1023 if (expr->type == EXPR_VALUE) {
1024 struct statement *simple;
1025 simple = expr->value ? stmt->if_true : stmt->if_false;
1026
1027 /* Nothing? */
1028 if (!simple) {
1029 stmt->type = STMT_NONE;
1030 return 0;
1031 }
1032 expand_statement(simple);
1033 *stmt = *simple;
1034 return SIDE_EFFECTS;
1035 }
1036 #endif
1037 expand_statement(stmt->if_true);
1038 expand_statement(stmt->if_false);
1039 return SIDE_EFFECTS;
1040 }
1041
1042 /*
1043 * Expanding a compound statement is really just
1044 * about adding up the costs of each individual
1045 * statement.
1046 *
1047 * We also collapse a simple compound statement:
1048 * this would trigger for simple inline functions,
1049 * except we would have to check the "return"
1050 * symbol usage. Next time.
1051 */
1052 static int expand_compound(struct statement *stmt)
1053 {
1054 struct statement *s, *last;
1055 int cost, statements;
1056
1057 if (stmt->ret)
1058 expand_symbol(stmt->ret);
1059
1060 last = stmt->args;
1061 cost = expand_statement(last);
1062 statements = last != NULL;
1063 FOR_EACH_PTR(stmt->stmts, s) {
1064 statements++;
1065 last = s;
1066 cost += expand_statement(s);
1067 } END_FOR_EACH_PTR(s);
1068
1069 if (statements == 1 && !stmt->ret)
1070 *stmt = *last;
1071
1072 return cost;
1073 }
1074
1075 static int expand_statement(struct statement *stmt)
1076 {
1077 if (!stmt)
1078 return 0;
1079
1080 switch (stmt->type) {
1081 case STMT_DECLARATION: {
1082 struct symbol *sym;
1083 FOR_EACH_PTR(stmt->declaration, sym) {
1084 expand_symbol(sym);
1085 } END_FOR_EACH_PTR(sym);
1086 return SIDE_EFFECTS;
1087 }
1088
1089 case STMT_RETURN:
1090 expand_return_expression(stmt);
1091 return SIDE_EFFECTS;
1092
1093 case STMT_EXPRESSION:
1094 return expand_expression(stmt->expression);
1095
1096 case STMT_COMPOUND:
1097 return expand_compound(stmt);
1098
1099 case STMT_IF:
1100 return expand_if_statement(stmt);
1101
1102 case STMT_ITERATOR:
1103 expand_expression(stmt->iterator_pre_condition);
1104 expand_expression(stmt->iterator_post_condition);
1105 expand_statement(stmt->iterator_pre_statement);
1106 expand_statement(stmt->iterator_statement);
1107 expand_statement(stmt->iterator_post_statement);
1108 return SIDE_EFFECTS;
1109
1110 case STMT_SWITCH:
1111 expand_expression(stmt->switch_expression);
1112 expand_statement(stmt->switch_statement);
1113 return SIDE_EFFECTS;
1114
1115 case STMT_CASE:
1116 expand_const_expression(stmt->case_expression, "case statement");
1117 expand_const_expression(stmt->case_to, "case statement");
1118 expand_statement(stmt->case_statement);
1119 return SIDE_EFFECTS;
1120
1121 case STMT_LABEL:
1122 expand_statement(stmt->label_statement);
1123 return SIDE_EFFECTS;
1124
1125 case STMT_GOTO:
1126 expand_expression(stmt->goto_expression);
1127 return SIDE_EFFECTS;
1128
1129 case STMT_NONE:
1130 break;
1131 case STMT_ASM:
1132 /* FIXME! Do the asm parameter evaluation! */
1133 break;
1134 case STMT_CONTEXT:
1135 expand_expression(stmt->expression);
1136 break;
1137 case STMT_RANGE:
1138 expand_expression(stmt->range_expression);
1139 expand_expression(stmt->range_low);
1140 expand_expression(stmt->range_high);
1141 break;
1142 }
1143 return SIDE_EFFECTS;
1144 }
1145
1146 long long get_expression_value(struct expression *expr)
1147 {
1148 long long value, mask;
1149 struct symbol *ctype;
1150
1151 if (!expr)
1152 return 0;
1153 ctype = evaluate_expression(expr);
1154 if (!ctype) {
1155 expression_error(expr, "bad constant expression type");
1156 return 0;
1157 }
1158 expand_expression(expr);
1159 if (expr->type != EXPR_VALUE) {
1160 expression_error(expr, "bad constant expression");
1161 return 0;
1162 }
1163
1164 value = expr->value;
1165 mask = 1ULL << (ctype->bit_size-1);
1166
1167 if (value & mask) {
1168 while (ctype->type != SYM_BASETYPE)
1169 ctype = ctype->ctype.base_type;
1170 if (!(ctype->ctype.modifiers & MOD_UNSIGNED))
1171 value = value | mask | ~(mask-1);
1172 }
1173 return value;
1174 }
Static analysis for C