4 * Copyright (C) 2003 Transmeta Corp.
7 * Licensed under the Open Software License version 1.1
9 * expand constant expressions.
26 #include "expression.h"
28 /* Random cost numbers */
29 #define SIDE_EFFECTS 10000 /* The expression has side effects */
30 #define UNSAFE 100 /* The expression may be "infinitely costly" due to exceptions */
31 #define SELECT_COST 20 /* Cut-off for turning a conditional into a select */
32 #define BRANCH_COST 10 /* Cost of a conditional branch */
34 static int expand_expression(struct expression
*);
35 static int expand_statement(struct statement
*);
37 static int expand_symbol_expression(struct expression
*expr
)
39 struct symbol
*sym
= expr
->symbol
;
40 /* The cost of a symbol expression is lower for on-stack symbols */
41 return (sym
->ctype
.modifiers
& (MOD_STATIC
| MOD_EXTERN
)) ? 2 : 1;
44 static long long get_longlong(struct expression
*expr
)
46 int no_expand
= expr
->ctype
->ctype
.modifiers
& MOD_UNSIGNED
;
47 long long mask
= 1ULL << (expr
->ctype
->bit_size
- 1);
48 long long value
= expr
->value
;
49 long long ormask
, andmask
;
53 andmask
= mask
| (mask
-1);
57 return (value
& andmask
) | ormask
;
60 void cast_value(struct expression
*expr
, struct symbol
*newtype
,
61 struct expression
*old
, struct symbol
*oldtype
)
63 int old_size
= oldtype
->bit_size
;
64 int new_size
= newtype
->bit_size
;
65 long long value
, mask
;
67 if (newtype
->ctype
.base_type
== &fp_type
||
68 oldtype
->ctype
.base_type
== &fp_type
)
71 // For pointers and integers, we can just move the value around
72 expr
->type
= EXPR_VALUE
;
73 if (old_size
== new_size
) {
74 expr
->value
= old
->value
;
78 // expand it to the full "long long" value
79 value
= get_longlong(old
);
82 // Truncate it to the new size
83 mask
= 1ULL << (new_size
-1);
84 mask
= mask
| (mask
-1);
85 expr
->value
= value
& mask
;
89 if (newtype
->ctype
.base_type
!= &fp_type
) {
90 value
= (long long)old
->fvalue
;
91 expr
->type
= EXPR_VALUE
;
95 if (oldtype
->ctype
.base_type
!= &fp_type
)
96 expr
->fvalue
= (long double)get_longlong(old
);
98 expr
->fvalue
= old
->value
;
100 if (!(newtype
->ctype
.modifiers
& MOD_LONGLONG
)) {
101 if ((newtype
->ctype
.modifiers
& MOD_LONG
))
102 expr
->fvalue
= (double)expr
->fvalue
;
104 expr
->fvalue
= (float)expr
->fvalue
;
106 expr
->type
= EXPR_FVALUE
;
109 static int check_shift_count(struct expression
*expr
, struct symbol
*ctype
, unsigned int count
)
111 if (count
>= ctype
->bit_size
) {
112 warning(expr
->pos
, "shift too big (%u) for type %s", count
, show_typename(ctype
));
113 count
&= ctype
->bit_size
-1;
119 * CAREFUL! We need to get the size and sign of the
122 #define CONVERT(op,s) (((op)<<1)+(s))
123 #define SIGNED(op) CONVERT(op, 1)
124 #define UNSIGNED(op) CONVERT(op, 0)
125 static int simplify_int_binop(struct expression
*expr
, struct symbol
*ctype
)
127 struct expression
*left
= expr
->left
, *right
= expr
->right
;
128 unsigned long long v
, l
, r
, mask
;
129 signed long long sl
, sr
;
132 if (right
->type
!= EXPR_VALUE
)
135 if (expr
->op
== SPECIAL_LEFTSHIFT
|| expr
->op
== SPECIAL_RIGHTSHIFT
) {
136 r
= check_shift_count(expr
, ctype
, r
);
139 if (left
->type
!= EXPR_VALUE
)
141 l
= left
->value
; r
= right
->value
;
142 is_signed
= !(ctype
->ctype
.modifiers
& MOD_UNSIGNED
);
143 mask
= 1ULL << (ctype
->bit_size
-1);
145 if (is_signed
&& (sl
& mask
))
147 if (is_signed
&& (sr
& mask
))
150 switch (CONVERT(expr
->op
,is_signed
)) {
187 if (l
== mask
&& sr
== -1)
208 case SIGNED(SPECIAL_LEFTSHIFT
):
209 case UNSIGNED(SPECIAL_LEFTSHIFT
):
213 case SIGNED(SPECIAL_RIGHTSHIFT
):
217 case UNSIGNED(SPECIAL_RIGHTSHIFT
):
224 mask
= mask
| (mask
-1);
225 expr
->value
= v
& mask
;
226 expr
->type
= EXPR_VALUE
;
229 warning(expr
->pos
, "division by zero");
232 warning(expr
->pos
, "constant integer operation overflow");
236 static int simplify_cmp_binop(struct expression
*expr
, struct symbol
*ctype
)
238 struct expression
*left
= expr
->left
, *right
= expr
->right
;
239 unsigned long long l
, r
, mask
;
240 signed long long sl
, sr
;
242 if (left
->type
!= EXPR_VALUE
|| right
->type
!= EXPR_VALUE
)
244 l
= left
->value
; r
= right
->value
;
245 mask
= 1ULL << (ctype
->bit_size
-1);
252 case '<': expr
->value
= sl
< sr
; break;
253 case '>': expr
->value
= sl
> sr
; break;
254 case SPECIAL_LTE
: expr
->value
= sl
<= sr
; break;
255 case SPECIAL_GTE
: expr
->value
= sl
>= sr
; break;
256 case SPECIAL_EQUAL
: expr
->value
= l
== r
; break;
257 case SPECIAL_NOTEQUAL
: expr
->value
= l
!= r
; break;
258 case SPECIAL_UNSIGNED_LT
:expr
->value
= l
< r
; break;
259 case SPECIAL_UNSIGNED_GT
:expr
->value
= l
> r
; break;
260 case SPECIAL_UNSIGNED_LTE
:expr
->value
= l
<= r
; break;
261 case SPECIAL_UNSIGNED_GTE
:expr
->value
= l
>= r
; break;
263 expr
->type
= EXPR_VALUE
;
267 static int simplify_float_binop(struct expression
*expr
)
269 struct expression
*left
= expr
->left
, *right
= expr
->right
;
270 unsigned long mod
= expr
->ctype
->ctype
.modifiers
;
271 long double l
, r
, res
;
273 if (left
->type
!= EXPR_FVALUE
|| right
->type
!= EXPR_FVALUE
)
279 if (mod
& MOD_LONGLONG
) {
281 case '+': res
= l
+ r
; break;
282 case '-': res
= l
- r
; break;
283 case '*': res
= l
* r
; break;
284 case '/': if (!r
) goto Div
;
288 } else if (mod
& MOD_LONG
) {
290 case '+': res
= (double) l
+ (double) r
; break;
291 case '-': res
= (double) l
- (double) r
; break;
292 case '*': res
= (double) l
* (double) r
; break;
293 case '/': if (!r
) goto Div
;
294 res
= (double) l
/ (double) r
; break;
299 case '+': res
= (float)l
+ (float)r
; break;
300 case '-': res
= (float)l
- (float)r
; break;
301 case '*': res
= (float)l
* (float)r
; break;
302 case '/': if (!r
) goto Div
;
303 res
= (float)l
/ (float)r
; break;
307 expr
->type
= EXPR_FVALUE
;
311 warning(expr
->pos
, "division by zero");
315 static int simplify_float_cmp(struct expression
*expr
, struct symbol
*ctype
)
317 struct expression
*left
= expr
->left
, *right
= expr
->right
;
320 if (left
->type
!= EXPR_FVALUE
|| right
->type
!= EXPR_FVALUE
)
326 case '<': expr
->value
= l
< r
; break;
327 case '>': expr
->value
= l
> r
; break;
328 case SPECIAL_LTE
: expr
->value
= l
<= r
; break;
329 case SPECIAL_GTE
: expr
->value
= l
>= r
; break;
330 case SPECIAL_EQUAL
: expr
->value
= l
== r
; break;
331 case SPECIAL_NOTEQUAL
: expr
->value
= l
!= r
; break;
333 expr
->type
= EXPR_VALUE
;
337 static int expand_binop(struct expression
*expr
)
341 cost
= expand_expression(expr
->left
);
342 cost
+= expand_expression(expr
->right
);
343 if (simplify_int_binop(expr
, expr
->ctype
))
345 if (simplify_float_binop(expr
))
350 static int expand_logical(struct expression
*expr
)
352 struct expression
*left
= expr
->left
;
353 struct expression
*right
;
356 /* Do immediate short-circuiting ... */
357 cost
= expand_expression(left
);
358 if (left
->type
== EXPR_VALUE
) {
359 if (expr
->op
== SPECIAL_LOGICAL_AND
) {
361 expr
->type
= EXPR_VALUE
;
367 expr
->type
= EXPR_VALUE
;
375 rcost
= expand_expression(right
);
376 if (left
->type
== EXPR_VALUE
&& right
->type
== EXPR_VALUE
) {
378 * We know the left value doesn't matter, since
379 * otherwise we would have short-circuited it..
381 expr
->type
= EXPR_VALUE
;
382 expr
->value
= right
->value
!= 0;
387 * If the right side is safe and cheaper than a branch,
388 * just avoid the branch and turn it into a regular binop
391 if (rcost
< BRANCH_COST
) {
392 expr
->type
= EXPR_BINOP
;
393 rcost
-= BRANCH_COST
- 1;
396 return cost
+ BRANCH_COST
+ rcost
;
399 static int expand_comma(struct expression
*expr
)
403 cost
= expand_expression(expr
->left
);
404 cost
+= expand_expression(expr
->right
);
405 if (expr
->left
->type
== EXPR_VALUE
|| expr
->left
->type
== EXPR_FVALUE
)
406 *expr
= *expr
->right
;
410 #define MOD_IGN (MOD_VOLATILE | MOD_CONST)
412 static int compare_types(int op
, struct symbol
*left
, struct symbol
*right
)
416 return !type_difference(left
, right
, MOD_IGN
, MOD_IGN
);
417 case SPECIAL_NOTEQUAL
:
418 return type_difference(left
, right
, MOD_IGN
, MOD_IGN
) != NULL
;
420 return left
->bit_size
< right
->bit_size
;
422 return left
->bit_size
> right
->bit_size
;
424 return left
->bit_size
<= right
->bit_size
;
426 return left
->bit_size
>= right
->bit_size
;
431 static int expand_compare(struct expression
*expr
)
433 struct expression
*left
= expr
->left
, *right
= expr
->right
;
436 cost
= expand_expression(left
);
437 cost
+= expand_expression(right
);
439 /* Type comparison? */
440 if (left
&& right
&& left
->type
== EXPR_TYPE
&& right
->type
== EXPR_TYPE
) {
442 expr
->type
= EXPR_VALUE
;
443 expr
->value
= compare_types(op
, left
->symbol
, right
->symbol
);
446 if (simplify_cmp_binop(expr
, left
->ctype
))
448 if (simplify_float_cmp(expr
, left
->ctype
))
453 static int expand_conditional(struct expression
*expr
)
455 struct expression
*cond
= expr
->conditional
;
456 struct expression
*true = expr
->cond_true
;
457 struct expression
*false = expr
->cond_false
;
460 cond_cost
= expand_expression(cond
);
461 if (cond
->type
== EXPR_VALUE
) {
462 true = true ? : cond
;
466 return expand_expression(expr
);
469 cost
= expand_expression(true);
470 cost
+= expand_expression(false);
472 if (cost
< SELECT_COST
) {
473 expr
->type
= EXPR_SELECT
;
474 cost
-= BRANCH_COST
- 1;
477 return cost
+ cond_cost
+ BRANCH_COST
;
480 static int expand_assignment(struct expression
*expr
)
482 expand_expression(expr
->left
);
483 expand_expression(expr
->right
);
487 static int expand_addressof(struct expression
*expr
)
489 return expand_expression(expr
->unop
);
492 static int expand_dereference(struct expression
*expr
)
494 struct expression
*unop
= expr
->unop
;
496 expand_expression(unop
);
499 * NOTE! We get a bogus warning right now for some special
500 * cases: apparently I've screwed up the optimization of
501 * a zero-offset derefence, and the ctype is wrong.
503 * Leave the warning in anyway, since this is also a good
504 * test for me to get the type evaluation right..
506 if (expr
->ctype
->ctype
.modifiers
& MOD_NODEREF
)
507 warning(unop
->pos
, "dereference of noderef expression");
509 if (unop
->type
== EXPR_SYMBOL
) {
510 struct symbol
*sym
= unop
->symbol
;
512 /* Const symbol with a constant initializer? */
513 if (!(sym
->ctype
.modifiers
& (MOD_ASSIGNED
| MOD_ADDRESSABLE
))) {
514 struct expression
*value
= sym
->initializer
;
516 if (value
->type
== EXPR_VALUE
) {
517 expr
->type
= EXPR_VALUE
;
518 expr
->value
= value
->value
;
520 } else if (value
->type
== EXPR_FVALUE
) {
521 expr
->type
= EXPR_FVALUE
;
522 expr
->fvalue
= value
->fvalue
;
528 /* Direct symbol dereference? Cheap and safe */
529 return (sym
->ctype
.modifiers
& (MOD_STATIC
| MOD_EXTERN
)) ? 2 : 1;
534 static int simplify_preop(struct expression
*expr
)
536 struct expression
*op
= expr
->unop
;
537 unsigned long long v
, mask
;
539 if (op
->type
!= EXPR_VALUE
)
542 mask
= 1ULL << (expr
->ctype
->bit_size
-1);
547 if (v
== mask
&& !(expr
->ctype
->ctype
.modifiers
& MOD_UNSIGNED
))
551 case '!': v
= !v
; break;
552 case '~': v
= ~v
; break;
555 mask
= mask
| (mask
-1);
556 expr
->value
= v
& mask
;
557 expr
->type
= EXPR_VALUE
;
561 warning(expr
->pos
, "constant integer operation overflow");
565 static int simplify_float_preop(struct expression
*expr
)
567 struct expression
*op
= expr
->unop
;
570 if (op
->type
!= EXPR_FVALUE
)
575 case '-': v
= -v
; break;
579 expr
->type
= EXPR_FVALUE
;
584 * Unary post-ops: x++ and x--
586 static int expand_postop(struct expression
*expr
)
588 expand_expression(expr
->unop
);
592 static int expand_preop(struct expression
*expr
)
598 return expand_dereference(expr
);
601 return expand_addressof(expr
);
603 case SPECIAL_INCREMENT
:
604 case SPECIAL_DECREMENT
:
606 * From a type evaluation standpoint the pre-ops are
607 * the same as the postops
609 return expand_postop(expr
);
614 cost
= expand_expression(expr
->unop
);
616 if (simplify_preop(expr
))
618 if (simplify_float_preop(expr
))
623 static int expand_arguments(struct expression_list
*head
)
626 struct expression
*expr
;
628 FOR_EACH_PTR (head
, expr
) {
629 cost
+= expand_expression(expr
);
630 } END_FOR_EACH_PTR(expr
);
634 static int expand_cast(struct expression
*expr
)
637 struct expression
*target
= expr
->cast_expression
;
639 cost
= expand_expression(target
);
641 /* Simplify normal integer casts.. */
642 if (target
->type
== EXPR_VALUE
|| target
->type
== EXPR_FVALUE
) {
643 cast_value(expr
, expr
->ctype
, target
, target
->ctype
);
650 * expand a call expression with a symbol. This
651 * should expand builtins.
653 static int expand_symbol_call(struct expression
*expr
)
655 struct expression
*fn
= expr
->fn
;
656 struct symbol
*ctype
= fn
->ctype
;
658 if (fn
->type
!= EXPR_PREOP
)
661 if (ctype
->op
&& ctype
->op
->expand
)
662 return ctype
->op
->expand(expr
);
667 static int expand_call(struct expression
*expr
)
671 struct expression
*fn
= expr
->fn
;
673 cost
= expand_arguments(expr
->args
);
676 error(expr
->pos
, "function has no type");
679 if (sym
->type
== SYM_NODE
)
680 return expand_symbol_call(expr
);
685 static int expand_expression_list(struct expression_list
*list
)
688 struct expression
*expr
;
690 FOR_EACH_PTR(list
, expr
) {
691 cost
+= expand_expression(expr
);
692 } END_FOR_EACH_PTR(expr
);
697 * We can simplify nested position expressions if
698 * this is a simple (single) positional expression.
700 static int expand_pos_expression(struct expression
*expr
)
702 struct expression
*nested
= expr
->init_expr
;
703 unsigned long offset
= expr
->init_offset
;
704 int nr
= expr
->init_nr
;
707 switch (nested
->type
) {
709 offset
+= nested
->init_offset
;
711 expr
->init_offset
= offset
;
715 case EXPR_INITIALIZER
: {
716 struct expression
*reuse
= nested
, *entry
;
718 FOR_EACH_PTR(expr
->expr_list
, entry
) {
719 if (entry
->type
== EXPR_POS
) {
720 entry
->init_offset
+= offset
;
723 error(entry
->pos
, "multiple initializers at offset zero");
726 reuse
->type
= EXPR_POS
;
727 reuse
->ctype
= entry
->ctype
;
728 reuse
->init_offset
= offset
;
730 reuse
->init_expr
= entry
;
731 REPLACE_CURRENT_PTR(entry
, reuse
);
734 } END_FOR_EACH_PTR(entry
);
743 return expand_expression(nested
);
746 static int compare_expressions(const void *_a
, const void *_b
)
748 const struct expression
*a
= _a
;
749 const struct expression
*b
= _b
;
752 r
= (b
->type
!= EXPR_POS
) - (a
->type
!= EXPR_POS
);
755 if (a
->init_offset
< b
->init_offset
)
757 if (a
->init_offset
> b
->init_offset
)
759 /* Check bitfield offset.. */
763 if (a
->ctype
&& b
->ctype
) {
764 if (a
->ctype
->bit_offset
< b
->ctype
->bit_offset
)
772 static void sort_expression_list(struct expression_list
**list
)
774 sort_list((struct ptr_list
**)list
, compare_expressions
);
777 static int expand_expression(struct expression
*expr
)
784 switch (expr
->type
) {
791 return expand_symbol_expression(expr
);
793 return expand_binop(expr
);
796 return expand_logical(expr
);
799 return expand_comma(expr
);
802 return expand_compare(expr
);
804 case EXPR_ASSIGNMENT
:
805 return expand_assignment(expr
);
808 return expand_preop(expr
);
811 return expand_postop(expr
);
814 return expand_cast(expr
);
817 return expand_call(expr
);
820 warning(expr
->pos
, "we should not have an EXPR_DEREF left at expansion time");
824 return expand_expression(expr
->address
);
827 case EXPR_CONDITIONAL
:
828 return expand_conditional(expr
);
831 return expand_statement(expr
->statement
);
836 case EXPR_INITIALIZER
:
837 sort_expression_list(&expr
->expr_list
);
838 return expand_expression_list(expr
->expr_list
);
840 case EXPR_IDENTIFIER
:
847 return expand_expression(expr
->base
) + 1;
850 return expand_pos_expression(expr
);
854 warning(expr
->pos
, "internal front-end error: sizeof in expansion?");
860 static void expand_const_expression(struct expression
*expr
, const char *where
)
863 expand_expression(expr
);
864 if (expr
->type
!= EXPR_VALUE
)
865 warning(expr
->pos
, "Expected constant expression in %s", where
);
869 void expand_symbol(struct symbol
*sym
)
871 struct symbol
*base_type
;
875 base_type
= sym
->ctype
.base_type
;
879 expand_expression(sym
->initializer
);
880 /* expand the body of the symbol */
881 if (base_type
->type
== SYM_FN
) {
883 expand_statement(base_type
->stmt
);
887 static void expand_return_expression(struct statement
*stmt
)
889 expand_expression(stmt
->expression
);
892 static int expand_if_statement(struct statement
*stmt
)
894 struct expression
*expr
= stmt
->if_conditional
;
896 if (!expr
|| !expr
->ctype
)
899 expand_expression(expr
);
901 /* This is only valid if nobody jumps into the "dead" side */
903 /* Simplify constant conditionals without even evaluating the false side */
904 if (expr
->type
== EXPR_VALUE
) {
905 struct statement
*simple
;
906 simple
= expr
->value
? stmt
->if_true
: stmt
->if_false
;
910 stmt
->type
= STMT_NONE
;
913 expand_statement(simple
);
918 expand_statement(stmt
->if_true
);
919 expand_statement(stmt
->if_false
);
923 static int expand_statement(struct statement
*stmt
)
928 switch (stmt
->type
) {
930 expand_return_expression(stmt
);
933 case STMT_EXPRESSION
:
934 return expand_expression(stmt
->expression
);
936 case STMT_COMPOUND
: {
941 FOR_EACH_PTR(stmt
->syms
, sym
) {
943 } END_FOR_EACH_PTR(sym
);
944 expand_symbol(stmt
->ret
);
947 FOR_EACH_PTR(stmt
->stmts
, s
) {
948 cost
+= expand_statement(s
);
949 } END_FOR_EACH_PTR(s
);
954 return expand_if_statement(stmt
);
957 expand_expression(stmt
->iterator_pre_condition
);
958 expand_expression(stmt
->iterator_post_condition
);
959 expand_statement(stmt
->iterator_pre_statement
);
960 expand_statement(stmt
->iterator_statement
);
961 expand_statement(stmt
->iterator_post_statement
);
965 expand_expression(stmt
->switch_expression
);
966 expand_statement(stmt
->switch_statement
);
970 expand_const_expression(stmt
->case_expression
, "case statement");
971 expand_const_expression(stmt
->case_to
, "case statement");
972 expand_statement(stmt
->case_statement
);
976 expand_statement(stmt
->label_statement
);
980 expand_expression(stmt
->goto_expression
);
986 /* FIXME! Do the asm parameter evaluation! */
992 long long get_expression_value(struct expression
*expr
)
994 long long value
, mask
;
995 struct symbol
*ctype
;
999 ctype
= evaluate_expression(expr
);
1001 warning(expr
->pos
, "bad constant expression type");
1004 expand_expression(expr
);
1005 if (expr
->type
!= EXPR_VALUE
) {
1006 warning(expr
->pos
, "bad constant expression");
1010 value
= expr
->value
;
1011 mask
= 1ULL << (ctype
->bit_size
-1);
1014 while (ctype
->type
!= SYM_BASETYPE
)
1015 ctype
= ctype
->ctype
.base_type
;
1016 if (!(ctype
->ctype
.modifiers
& MOD_UNSIGNED
))
1017 value
= value
| mask
| ~(mask
-1);