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