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