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