Simplify testing for "is it a string?" by just checking
[smatch.git] / expand.c
blob35f0b203ec14e0b6448121a0b9c2994727b421f3
1 /*
2 * sparse/expand.c
4 * Copyright (C) 2003 Transmeta Corp.
5 * 2003 Linus Torvalds
7 * Licensed under the Open Software License version 1.1
9 * expand constant expressions.
11 #include <stdlib.h>
12 #include <stdarg.h>
13 #include <stddef.h>
14 #include <stdio.h>
15 #include <string.h>
16 #include <ctype.h>
17 #include <unistd.h>
18 #include <fcntl.h>
19 #include <limits.h>
21 #include "lib.h"
22 #include "parse.h"
23 #include "token.h"
24 #include "symbol.h"
25 #include "target.h"
26 #include "expression.h"
28 static void expand_expression(struct expression *);
29 static void expand_statement(struct statement *);
31 static void expand_symbol_expression(struct expression *expr)
33 struct symbol *sym = expr->symbol;
36 * The preprocessor can cause unknown symbols to be generated
38 if (!sym) {
39 warn(expr->pos, "undefined preprocessor identifier '%s'", show_ident(expr->symbol_name));
40 expr->type = EXPR_VALUE;
41 expr->value = 0;
42 return;
46 static long long get_longlong(struct expression *expr)
48 int no_expand = expr->ctype->ctype.modifiers & MOD_UNSIGNED;
49 long long mask = 1ULL << (expr->ctype->bit_size - 1);
50 long long value = expr->value;
51 long long ormask, andmask;
53 if (!(value & mask))
54 no_expand = 1;
55 andmask = mask | (mask-1);
56 ormask = ~andmask;
57 if (no_expand)
58 ormask = 0;
59 return (value & andmask) | ormask;
62 void cast_value(struct expression *expr, struct symbol *newtype,
63 struct expression *old, struct symbol *oldtype)
65 int old_size = oldtype->bit_size;
66 int new_size = newtype->bit_size;
67 long long value, mask;
69 if (newtype->ctype.base_type == &fp_type ||
70 oldtype->ctype.base_type == &fp_type)
71 goto Float;
73 // For pointers and integers, we can just move the value around
74 expr->type = EXPR_VALUE;
75 if (old_size == new_size) {
76 expr->value = old->value;
77 return;
80 // expand it to the full "long long" value
81 value = get_longlong(old);
83 Int:
84 // Truncate it to the new size
85 mask = 1ULL << (new_size-1);
86 mask = mask | (mask-1);
87 expr->value = value & mask;
88 return;
90 Float:
91 if (newtype->ctype.base_type != &fp_type) {
92 value = (long long)old->fvalue;
93 expr->type = EXPR_VALUE;
94 goto Int;
97 if (oldtype->ctype.base_type != &fp_type)
98 expr->fvalue = (long double)get_longlong(old);
99 else
100 expr->fvalue = old->value;
102 if (!(newtype->ctype.modifiers & MOD_LONGLONG)) {
103 if ((newtype->ctype.modifiers & MOD_LONG))
104 expr->fvalue = (double)expr->fvalue;
105 else
106 expr->fvalue = (float)expr->fvalue;
108 expr->type = EXPR_FVALUE;
111 static int check_shift_count(struct expression *expr, struct symbol *ctype, unsigned int count)
113 if (count >= ctype->bit_size) {
114 warn(expr->pos, "shift too big for type (%x)", ctype->ctype.modifiers);
115 count &= ctype->bit_size-1;
117 return count;
121 * CAREFUL! We need to get the size and sign of the
122 * result right!
124 #define CONVERT(op,s) (((op)<<1)+(s))
125 #define SIGNED(op) CONVERT(op, 1)
126 #define UNSIGNED(op) CONVERT(op, 0)
127 static int simplify_int_binop(struct expression *expr, struct symbol *ctype)
129 struct expression *left = expr->left, *right = expr->right;
130 unsigned long long v, l, r, mask;
131 signed long long sl, sr;
132 int is_signed, shift;
134 if (left->type != EXPR_VALUE || right->type != EXPR_VALUE)
135 return 0;
136 l = left->value; r = right->value;
137 is_signed = !(ctype->ctype.modifiers & MOD_UNSIGNED);
138 mask = 1ULL << (ctype->bit_size-1);
139 sl = l; sr = r;
140 if (is_signed && (sl & mask))
141 sl |= ~(mask-1);
142 if (is_signed && (sr & mask))
143 sr |= ~(mask-1);
145 switch (CONVERT(expr->op,is_signed)) {
146 case SIGNED('+'):
147 case UNSIGNED('+'):
148 v = l + r;
149 break;
151 case SIGNED('-'):
152 case UNSIGNED('-'):
153 v = l - r;
154 break;
156 case SIGNED('&'):
157 case UNSIGNED('&'):
158 v = l & r;
159 break;
161 case SIGNED('|'):
162 case UNSIGNED('|'):
163 v = l | r;
164 break;
166 case SIGNED('^'):
167 case UNSIGNED('^'):
168 v = l ^ r;
169 break;
171 case SIGNED('*'):
172 v = sl * sr;
173 break;
175 case UNSIGNED('*'):
176 v = l * r;
177 break;
179 case SIGNED('/'):
180 if (!r)
181 goto Div;
182 if (l == mask && sr == -1)
183 goto Overflow;
184 v = sl / sr;
185 break;
187 case UNSIGNED('/'):
188 if (!r) goto Div;
189 v = l / r;
190 break;
192 case SIGNED('%'):
193 if (!r)
194 goto Div;
195 v = sl % sr;
196 break;
198 case UNSIGNED('%'):
199 if (!r) goto Div;
200 v = l % r;
201 break;
203 case SIGNED(SPECIAL_LEFTSHIFT):
204 case UNSIGNED(SPECIAL_LEFTSHIFT):
205 shift = check_shift_count(expr, ctype, r);
206 v = l << shift;
207 break;
209 case SIGNED(SPECIAL_RIGHTSHIFT):
210 shift = check_shift_count(expr, ctype, r);
211 v = sl >> shift;
212 break;
214 case UNSIGNED(SPECIAL_RIGHTSHIFT):
215 shift = check_shift_count(expr, ctype, r);
216 v = l >> shift;
217 break;
219 default:
220 return 0;
222 mask = mask | (mask-1);
223 expr->value = v & mask;
224 expr->type = EXPR_VALUE;
225 return 1;
226 Div:
227 warn(expr->pos, "division by zero");
228 return 0;
229 Overflow:
230 warn(expr->pos, "constant integer operation overflow");
231 return 0;
234 static int simplify_cmp_binop(struct expression *expr, struct symbol *ctype)
236 struct expression *left = expr->left, *right = expr->right;
237 unsigned long long l, r, mask;
238 signed long long sl, sr;
240 if (left->type != EXPR_VALUE || right->type != EXPR_VALUE)
241 return 0;
242 l = left->value; r = right->value;
243 mask = 1ULL << (ctype->bit_size-1);
244 sl = l; sr = r;
245 if (sl & mask)
246 sl |= ~(mask-1);
247 if (sr & mask)
248 sr |= ~(mask-1);
249 switch (expr->op) {
250 case '<': expr->value = sl < sr; break;
251 case '>': expr->value = sl > sr; break;
252 case SPECIAL_LTE: expr->value = sl <= sr; break;
253 case SPECIAL_GTE: expr->value = sl >= sr; break;
254 case SPECIAL_EQUAL: expr->value = l == r; break;
255 case SPECIAL_NOTEQUAL: expr->value = l != r; break;
256 case SPECIAL_UNSIGNED_LT:expr->value = l < r; break;
257 case SPECIAL_UNSIGNED_GT:expr->value = l > r; break;
258 case SPECIAL_UNSIGNED_LTE:expr->value = l <= r; break;
259 case SPECIAL_UNSIGNED_GTE:expr->value = l >= r; break;
261 expr->type = EXPR_VALUE;
262 return 1;
265 static int simplify_float_binop(struct expression *expr)
267 struct expression *left = expr->left, *right = expr->right;
268 unsigned long mod = expr->ctype->ctype.modifiers;
269 long double l = left->fvalue;
270 long double r = right->fvalue;
271 long double res;
273 if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE)
274 return 0;
275 if (mod & MOD_LONGLONG) {
276 switch (expr->op) {
277 case '+': res = l + r; break;
278 case '-': res = l - r; break;
279 case '*': res = l * r; break;
280 case '/': if (!r) goto Div;
281 res = l / r; break;
282 default: return 0;
284 } else if (mod & MOD_LONG) {
285 switch (expr->op) {
286 case '+': res = (double) l + (double) r; break;
287 case '-': res = (double) l - (double) r; break;
288 case '*': res = (double) l * (double) r; break;
289 case '/': if (!r) goto Div;
290 res = (double) l / (double) r; break;
291 default: return 0;
293 } else {
294 switch (expr->op) {
295 case '+': res = (float)l + (float)r; break;
296 case '-': res = (float)l - (float)r; break;
297 case '*': res = (float)l * (float)r; break;
298 case '/': if (!r) goto Div;
299 res = (float)l / (float)r; break;
300 default: return 0;
303 expr->type = EXPR_FVALUE;
304 expr->fvalue = res;
305 return 1;
306 Div:
307 warn(expr->pos, "division by zero");
308 return 0;
311 static int simplify_float_cmp(struct expression *expr, struct symbol *ctype)
313 struct expression *left = expr->left, *right = expr->right;
314 long double l, r;
316 if (left->type != EXPR_FVALUE || right->type != EXPR_FVALUE)
317 return 0;
319 l = left->fvalue;
320 r = right->fvalue;
321 switch (expr->op) {
322 case '<': expr->value = l < r; break;
323 case '>': expr->value = l > r; break;
324 case SPECIAL_LTE: expr->value = l <= r; break;
325 case SPECIAL_GTE: expr->value = l >= r; break;
326 case SPECIAL_EQUAL: expr->value = l == r; break;
327 case SPECIAL_NOTEQUAL: expr->value = l != r; break;
329 expr->type = EXPR_VALUE;
330 return 1;
333 static void expand_binop(struct expression *expr)
335 if (simplify_int_binop(expr, expr->ctype))
336 return;
337 simplify_float_binop(expr);
340 static void expand_logical(struct expression *expr)
342 struct expression *left = expr->left;
343 struct expression *right;
345 /* Do immediate short-circuiting ... */
346 expand_expression(left);
347 if (left->type == EXPR_VALUE) {
348 if (expr->op == SPECIAL_LOGICAL_AND) {
349 if (!left->value) {
350 expr->type = EXPR_VALUE;
351 expr->value = 0;
352 return;
354 } else {
355 if (left->value) {
356 expr->type = EXPR_VALUE;
357 expr->value = 1;
358 return;
363 right = expr->right;
364 expand_expression(right);
365 if (left->type == EXPR_VALUE && right->type == EXPR_VALUE) {
367 * We know the left value doesn't matter, since
368 * otherwise we would have short-circuited it..
370 expr->type = EXPR_VALUE;
371 expr->value = right->value != 0;
375 static void expand_comma(struct expression *expr)
377 if (expr->left->type == EXPR_VALUE || expr->left->type == EXPR_FVALUE)
378 *expr = *expr->right;
381 #define MOD_IGN (MOD_VOLATILE | MOD_CONST)
383 static int compare_types(int op, struct symbol *left, struct symbol *right)
385 switch (op) {
386 case SPECIAL_EQUAL:
387 return !type_difference(left, right, MOD_IGN, MOD_IGN);
388 case SPECIAL_NOTEQUAL:
389 return type_difference(left, right, MOD_IGN, MOD_IGN) != NULL;
390 case '<':
391 return left->bit_size < right->bit_size;
392 case '>':
393 return left->bit_size > right->bit_size;
394 case SPECIAL_LTE:
395 return left->bit_size <= right->bit_size;
396 case SPECIAL_GTE:
397 return left->bit_size >= right->bit_size;
399 return 0;
402 static void expand_compare(struct expression *expr)
404 struct expression *left = expr->left, *right = expr->right;
406 /* Type comparison? */
407 if (left && right && left->type == EXPR_TYPE && right->type == EXPR_TYPE) {
408 int op = expr->op;
409 expr->type = EXPR_VALUE;
410 expr->value = compare_types(op, left->symbol, right->symbol);
411 return;
413 if (simplify_cmp_binop(expr, left->ctype))
414 return;
415 simplify_float_cmp(expr, left->ctype);
418 static void expand_conditional(struct expression *expr)
420 struct expression *cond = expr->conditional;
422 if (cond->type == EXPR_VALUE) {
423 struct expression *true, *false;
425 true = expr->cond_true ? : cond;
426 false = expr->cond_false;
428 if (!cond->value)
429 true = false;
430 *expr = *true;
434 static void expand_assignment(struct expression *expr)
438 static void expand_addressof(struct expression *expr)
442 static void expand_dereference(struct expression *expr)
444 struct expression *unop = expr->unop;
447 * NOTE! We get a bogus warning right now for some special
448 * cases: apparently I've screwed up the optimization of
449 * a zero-offset derefence, and the ctype is wrong.
451 * Leave the warning in anyway, since this is also a good
452 * test for me to get the type evaluation right..
454 if (expr->ctype->ctype.modifiers & MOD_NODEREF)
455 warn(unop->pos, "dereference of noderef expression");
457 if (unop->type == EXPR_SYMBOL) {
458 struct symbol *sym = unop->symbol;
460 /* Const symbol with a constant initializer? */
461 if (!(sym->ctype.modifiers & (MOD_ASSIGNED | MOD_ADDRESSABLE))) {
462 struct expression *value = sym->initializer;
463 if (value) {
464 if (value->type == EXPR_VALUE) {
465 expr->type = EXPR_VALUE;
466 expr->value = value->value;
467 } else if (value->type == EXPR_FVALUE) {
468 expr->type = EXPR_FVALUE;
469 expr->fvalue = value->fvalue;
476 static int simplify_preop(struct expression *expr)
478 struct expression *op = expr->unop;
479 unsigned long long v, mask;
481 if (op->type != EXPR_VALUE)
482 return 0;
483 v = op->value;
484 switch (expr->op) {
485 case '+': break;
486 case '-': v = -v; break;
487 case '!': v = !v; break;
488 case '~': v = ~v; break;
489 default: return 0;
491 mask = 1ULL << (expr->ctype->bit_size-1);
492 mask = mask | (mask-1);
493 expr->value = v & mask;
494 expr->type = EXPR_VALUE;
495 return 1;
498 static int simplify_float_preop(struct expression *expr)
500 struct expression *op = expr->unop;
501 long double v;
503 if (op->type != EXPR_FVALUE)
504 return 0;
505 v = op->fvalue;
506 switch (expr->op) {
507 case '+': break;
508 case '-': v = -v; break;
509 default: return 0;
511 expr->fvalue = v;
512 expr->type = EXPR_FVALUE;
513 return 1;
517 * Unary post-ops: x++ and x--
519 static void expand_postop(struct expression *expr)
523 static void expand_preop(struct expression *expr)
525 switch (expr->op) {
526 case '*':
527 expand_dereference(expr);
528 return;
530 case '&':
531 expand_addressof(expr);
532 return;
534 case SPECIAL_INCREMENT:
535 case SPECIAL_DECREMENT:
537 * From a type evaluation standpoint the pre-ops are
538 * the same as the postops
540 expand_postop(expr);
541 return;
543 default:
544 break;
546 if (simplify_preop(expr))
547 return;
548 simplify_float_preop(expr);
551 static void expand_arguments(struct expression_list *head)
553 struct expression *expr;
555 FOR_EACH_PTR (head, expr) {
556 expand_expression(expr);
557 } END_FOR_EACH_PTR;
560 static void expand_cast(struct expression *expr)
562 struct expression *target = expr->cast_expression;
564 expand_expression(target);
566 /* Simplify normal integer casts.. */
567 if (target->type == EXPR_VALUE || target->type == EXPR_FVALUE)
568 cast_value(expr, expr->ctype, target, target->ctype);
572 * expand a call expression with a symbol. This
573 * should expand inline functions, and expand
574 * builtins.
576 static void expand_symbol_call(struct expression *expr)
578 struct expression *fn = expr->fn;
579 struct symbol *ctype = fn->ctype;
581 if (fn->type != EXPR_PREOP)
582 return;
584 if (ctype->op && ctype->op->expand) {
585 ctype->op->expand(expr);
586 return;
590 static void expand_call(struct expression *expr)
592 struct symbol *sym;
593 struct expression *fn = expr->fn;
595 sym = fn->ctype;
596 expand_arguments(expr->args);
597 if (sym->type == SYM_NODE)
598 expand_symbol_call(expr);
601 static void expand_expression_list(struct expression_list *list)
603 struct expression *expr;
605 FOR_EACH_PTR(list, expr) {
606 expand_expression(expr);
607 } END_FOR_EACH_PTR;
610 static void expand_expression(struct expression *expr)
612 if (!expr)
613 return;
614 if (!expr->ctype)
615 return;
617 switch (expr->type) {
618 case EXPR_VALUE:
619 case EXPR_FVALUE:
620 case EXPR_STRING:
621 return;
622 case EXPR_TYPE:
623 case EXPR_SYMBOL:
624 expand_symbol_expression(expr);
625 return;
626 case EXPR_BINOP:
627 expand_expression(expr->left);
628 expand_expression(expr->right);
629 expand_binop(expr);
630 return;
632 case EXPR_LOGICAL:
633 expand_logical(expr);
634 return;
636 case EXPR_COMMA:
637 expand_expression(expr->left);
638 expand_expression(expr->right);
639 expand_comma(expr);
640 return;
642 case EXPR_COMPARE:
643 expand_expression(expr->left);
644 expand_expression(expr->right);
645 expand_compare(expr);
646 return;
648 case EXPR_ASSIGNMENT:
649 expand_expression(expr->left);
650 expand_expression(expr->right);
651 expand_assignment(expr);
652 return;
654 case EXPR_PREOP:
655 expand_expression(expr->unop);
656 expand_preop(expr);
657 return;
659 case EXPR_POSTOP:
660 expand_expression(expr->unop);
661 expand_postop(expr);
662 return;
664 case EXPR_CAST:
665 expand_cast(expr);
666 return;
668 case EXPR_CALL:
669 expand_call(expr);
670 return;
672 case EXPR_DEREF:
673 return;
675 case EXPR_BITFIELD:
676 expand_expression(expr->address);
677 return;
679 case EXPR_CONDITIONAL:
680 expand_expression(expr->conditional);
681 expand_expression(expr->cond_false);
682 expand_expression(expr->cond_true);
683 expand_conditional(expr);
684 return;
686 case EXPR_STATEMENT:
687 expand_statement(expr->statement);
688 return;
690 case EXPR_LABEL:
691 return;
693 case EXPR_INITIALIZER:
694 expand_expression_list(expr->expr_list);
695 return;
697 case EXPR_IDENTIFIER:
698 return;
700 case EXPR_INDEX:
701 return;
703 case EXPR_POS:
704 expand_expression(expr->init_expr);
705 return;
707 case EXPR_SIZEOF:
708 case EXPR_ALIGNOF:
709 warn(expr->pos, "internal front-end error: sizeof in expansion?");
710 return;
712 return;
715 static void expand_const_expression(struct expression *expr, const char *where)
717 if (expr) {
718 expand_expression(expr);
719 if (expr->type != EXPR_VALUE)
720 warn(expr->pos, "Expected constant expression in %s", where);
724 void expand_symbol(struct symbol *sym)
726 struct symbol *base_type;
728 if (!sym)
729 return;
730 base_type = sym->ctype.base_type;
731 if (!base_type)
732 return;
734 expand_expression(sym->initializer);
735 /* expand the body of the symbol */
736 if (base_type->type == SYM_FN) {
737 if (base_type->stmt)
738 expand_statement(base_type->stmt);
742 static void expand_return_expression(struct statement *stmt)
744 expand_expression(stmt->expression);
747 static void expand_if_statement(struct statement *stmt)
749 struct expression *expr = stmt->if_conditional;
751 if (!expr || !expr->ctype)
752 return;
754 expand_expression(expr);
756 /* This is only valid if nobody jumps into the "dead" side */
757 #if 0
758 /* Simplify constant conditionals without even evaluating the false side */
759 if (expr->type == EXPR_VALUE) {
760 struct statement *simple;
761 simple = expr->value ? stmt->if_true : stmt->if_false;
763 /* Nothing? */
764 if (!simple) {
765 stmt->type = STMT_NONE;
766 return;
768 expand_statement(simple);
769 *stmt = *simple;
770 return;
772 #endif
773 expand_statement(stmt->if_true);
774 expand_statement(stmt->if_false);
777 static void expand_statement(struct statement *stmt)
779 if (!stmt)
780 return;
782 switch (stmt->type) {
783 case STMT_RETURN:
784 expand_return_expression(stmt);
785 return;
787 case STMT_EXPRESSION:
788 expand_expression(stmt->expression);
789 return;
791 case STMT_COMPOUND: {
792 struct symbol *sym;
793 struct statement *s;
795 FOR_EACH_PTR(stmt->syms, sym) {
796 expand_symbol(sym);
797 } END_FOR_EACH_PTR;
798 expand_symbol(stmt->ret);
800 FOR_EACH_PTR(stmt->stmts, s) {
801 expand_statement(s);
802 } END_FOR_EACH_PTR;
803 return;
806 case STMT_IF:
807 expand_if_statement(stmt);
808 return;
810 case STMT_ITERATOR:
811 expand_expression(stmt->iterator_pre_condition);
812 expand_expression(stmt->iterator_post_condition);
813 expand_statement(stmt->iterator_pre_statement);
814 expand_statement(stmt->iterator_statement);
815 expand_statement(stmt->iterator_post_statement);
816 return;
818 case STMT_SWITCH:
819 expand_expression(stmt->switch_expression);
820 expand_statement(stmt->switch_statement);
821 return;
823 case STMT_CASE:
824 expand_const_expression(stmt->case_expression, "case statement");
825 expand_const_expression(stmt->case_to, "case statement");
826 expand_statement(stmt->case_statement);
827 return;
829 case STMT_LABEL:
830 expand_statement(stmt->label_statement);
831 return;
833 case STMT_GOTO:
834 expand_expression(stmt->goto_expression);
835 return;
837 case STMT_NONE:
838 break;
839 case STMT_ASM:
840 /* FIXME! Do the asm parameter evaluation! */
841 break;
845 long long get_expression_value(struct expression *expr)
847 long long value, mask;
848 struct symbol *ctype;
850 if (!expr)
851 return 0;
852 ctype = evaluate_expression(expr);
853 if (!ctype) {
854 warn(expr->pos, "bad constant expression type");
855 return 0;
857 expand_expression(expr);
858 if (expr->type != EXPR_VALUE) {
859 warn(expr->pos, "bad constant expression");
860 return 0;
863 value = expr->value;
864 mask = 1ULL << (ctype->bit_size-1);
866 if (value & mask) {
867 while (ctype->type != SYM_BASETYPE)
868 ctype = ctype->ctype.base_type;
869 if (!(ctype->ctype.modifiers & MOD_UNSIGNED))
870 value = value | mask | ~(mask-1);
872 return value;