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