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