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