4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
12 #include "smatch_slist.h"
13 #include "smatch_extra.h"
15 static sval_t
_get_value(struct expression
*expr
, int *undefined
, int implied
);
16 static sval_t
_get_implied_value(struct expression
*expr
, int *undefined
, int implied
);
20 static sval_t zero
= {.type
= &int_ctype
, {.value
= 0} };
21 static sval_t one
= {.type
= &int_ctype
, {.value
= 1} };
22 static sval_t bogus
= {.type
= &int_ctype
, {.value
= BOGUS
} };
36 static int opposite_implied(int implied
)
38 if (implied
== IMPLIED_MIN
)
40 if (implied
== IMPLIED_MAX
)
42 if (implied
== FUZZY_MIN
)
44 if (implied
== FUZZY_MAX
)
46 if (implied
== ABSOLUTE_MIN
)
48 if (implied
== ABSOLUTE_MAX
)
50 if (implied
== HARD_MAX
) /* we don't have a hard min. */
56 static int last_stmt_sval(struct statement
*stmt
, sval_t
*sval
)
58 struct expression
*expr
;
63 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
64 if (stmt
->type
!= STMT_EXPRESSION
)
66 expr
= stmt
->expression
;
67 if (!get_value(expr
, sval
))
72 static sval_t
handle_expression_statement(struct expression
*expr
, int *undefined
, int implied
)
74 struct statement
*stmt
;
77 stmt
= get_expression_statement(expr
);
78 if (!last_stmt_sval(stmt
, &ret
)) {
86 static sval_t
handle_ampersand(int *undefined
, int implied
)
90 ret
.type
= &ptr_ctype
;
93 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
94 return valid_ptr_min_sval
;
95 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
96 return valid_ptr_max_sval
;
102 static sval_t
handle_negate(struct expression
*expr
, int *undefined
, int implied
)
106 ret
= sval_blank(expr
->unop
);
108 if (known_condition_true(expr
->unop
)) {
113 if (implied
== NOTIMPLIED
) {
118 if (implied_condition_true(expr
->unop
)) {
122 if (implied_condition_false(expr
->unop
)) {
126 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
) {
130 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
) {
138 static sval_t
handle_preop(struct expression
*expr
, int *undefined
, int implied
)
144 ret
= handle_ampersand(undefined
, implied
);
147 ret
= handle_negate(expr
, undefined
, implied
);
150 ret
= _get_value(expr
->unop
, undefined
, implied
);
151 ret
= sval_preop(ret
, '~');
152 ret
= sval_cast(get_type(expr
->unop
), ret
);
155 ret
= _get_value(expr
->unop
, undefined
, implied
);
156 ret
= sval_preop(ret
, '-');
159 ret
= _get_implied_value(expr
, undefined
, implied
);
162 ret
= handle_expression_statement(expr
, undefined
, implied
);
166 ret
= sval_blank(expr
);
168 ret
= sval_cast(get_type(expr
), ret
);
172 static sval_t
handle_divide(struct expression
*expr
, int *undefined
, int implied
)
176 left
= _get_value(expr
->left
, undefined
, implied
);
177 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
179 if (right
.value
== 0) {
184 return sval_binop(left
, '/', right
);
187 static sval_t
handle_subtract(struct expression
*expr
, int *undefined
, int implied
)
190 sval_t left
, right
, ret
;
191 int left_undefined
= 0;
192 int right_undefined
= 0;
193 int known_but_negative
= 0;
196 left
= _get_value(expr
->left
, &left_undefined
, implied
);
197 right
= _get_value(expr
->right
, &right_undefined
, opposite_implied(implied
));
199 if (!left_undefined
&& !right_undefined
) {
200 ret
= sval_binop(left
, '-', right
);
201 if (sval_is_negative(ret
))
202 known_but_negative
= 1;
204 return ret
; /* best case scenario */
207 comparison
= get_comparison(expr
->left
, expr
->right
);
211 type
= get_type(expr
);
213 switch (comparison
) {
215 case SPECIAL_UNSIGNED_GT
:
220 return sval_type_val(type
, 1);
224 return _get_value(expr
->left
, undefined
, implied
);
228 case SPECIAL_UNSIGNED_GTE
:
233 return sval_type_val(type
, 0);
237 return _get_value(expr
->left
, undefined
, implied
);
242 if (known_but_negative
)
250 static sval_t
handle_mod(struct expression
*expr
, int *undefined
, int implied
)
254 /* if we can't figure out the right side it's probably hopeless */
255 right
= _get_value(expr
->right
, undefined
, implied
);
256 if (*undefined
|| right
.value
== 0) {
264 left
= _get_value(expr
->left
, undefined
, implied
);
266 return sval_binop(left
, '%', right
);
272 return sval_type_val(get_type(expr
), 0);
277 right
= sval_cast(get_type(expr
), right
);
284 static sval_t
handle_binop(struct expression
*expr
, int *undefined
, int implied
)
288 sval_t ret
= {.type
= &int_ctype
, {.value
= 123456} };
293 return handle_mod(expr
, undefined
, implied
);
295 if (implied
== HARD_MAX
) {
299 left
= _get_value(expr
->left
, &local_undef
, implied
);
301 if (implied
== IMPLIED_MIN
|| implied
== ABSOLUTE_MIN
) {
302 ret
= sval_blank(expr
->left
);
306 if (implied
!= IMPLIED_MAX
&& implied
!= ABSOLUTE_MAX
)
308 if (!get_absolute_max(expr
->left
, &left
))
311 right
= _get_value(expr
->right
, undefined
, implied
);
314 return sval_binop(left
, '&', right
);
316 case SPECIAL_RIGHTSHIFT
:
317 if (implied
== HARD_MAX
) {
321 left
= _get_value(expr
->left
, &local_undef
, implied
);
323 if (implied
== IMPLIED_MIN
|| implied
== ABSOLUTE_MIN
) {
324 ret
= sval_blank(expr
->left
);
328 if (implied
!= IMPLIED_MAX
&& implied
!= ABSOLUTE_MAX
)
330 if (!get_absolute_max(expr
->left
, &left
))
333 right
= _get_value(expr
->right
, undefined
, implied
);
336 return sval_binop(left
, SPECIAL_RIGHTSHIFT
, right
);
338 return handle_subtract(expr
, undefined
, implied
);
341 left
= _get_value(expr
->left
, undefined
, implied
);
342 right
= _get_value(expr
->right
, undefined
, implied
);
347 type
= get_type(expr
);
348 left
= sval_cast(type
, left
);
349 right
= sval_cast(type
, right
);
354 if (sval_binop_overflows(left
, expr
->op
, right
))
355 return sval_type_max(get_type(expr
));
359 if (sval_binop_overflows(left
, expr
->op
, right
)) {
367 return handle_divide(expr
, undefined
, implied
);
369 if (right
.value
== 0) {
373 return sval_binop(left
, '%', right
);
376 ret
= sval_binop(left
, expr
->op
, right
);
381 static int do_comparison(struct expression
*expr
)
383 struct range_list
*left_ranges
= NULL
;
384 struct range_list
*right_ranges
= NULL
;
385 int poss_true
, poss_false
;
388 type
= get_type(expr
);
390 get_implied_rl(expr
->left
, &left_ranges
);
391 get_implied_rl(expr
->right
, &right_ranges
);
392 left_ranges
= cast_rl(type
, left_ranges
);
393 right_ranges
= cast_rl(type
, right_ranges
);
395 poss_true
= possibly_true_rl(left_ranges
, expr
->op
, right_ranges
);
396 poss_false
= possibly_false_rl(left_ranges
, expr
->op
, right_ranges
);
398 free_rl(&left_ranges
);
399 free_rl(&right_ranges
);
401 if (!poss_true
&& !poss_false
)
403 if (poss_true
&& !poss_false
)
405 if (!poss_true
&& poss_false
)
410 static sval_t
handle_comparison(struct expression
*expr
, int *undefined
, int implied
)
415 if (get_value(expr
->left
, &left
) && get_value(expr
->right
, &right
)) {
416 struct data_range tmp_left
, tmp_right
;
420 tmp_right
.min
= right
;
421 tmp_right
.max
= right
;
422 if (true_comparison_range(&tmp_left
, expr
->op
, &tmp_right
))
427 if (implied
== NOTIMPLIED
) {
432 res
= do_comparison(expr
);
438 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
440 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
447 static sval_t
handle_logical(struct expression
*expr
, int *undefined
, int implied
)
453 if (implied
== NOTIMPLIED
) {
454 if (get_value(expr
->left
, &left
))
456 if (get_value(expr
->right
, &right
))
459 if (get_implied_value(expr
->left
, &left
))
461 if (get_implied_value(expr
->right
, &right
))
466 case SPECIAL_LOGICAL_OR
:
467 if (left_known
&& left
.value
)
469 if (right_known
&& right
.value
)
471 if (left_known
&& right_known
)
474 case SPECIAL_LOGICAL_AND
:
475 if (left_known
&& right_known
) {
476 if (left
.value
&& right
.value
)
486 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
488 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
495 static sval_t
handle_conditional(struct expression
*expr
, int *undefined
, int implied
)
497 if (known_condition_true(expr
->conditional
))
498 return _get_value(expr
->cond_true
, undefined
, implied
);
499 if (known_condition_false(expr
->conditional
))
500 return _get_value(expr
->cond_false
, undefined
, implied
);
502 if (implied
== NOTIMPLIED
) {
507 if (implied_condition_true(expr
->conditional
))
508 return _get_value(expr
->cond_true
, undefined
, implied
);
509 if (implied_condition_false(expr
->conditional
))
510 return _get_value(expr
->cond_false
, undefined
, implied
);
516 static int get_local_value(struct expression
*expr
, sval_t
*sval
, int implied
)
525 return get_local_min_helper(expr
, sval
);
530 return get_local_max_helper(expr
, sval
);
535 static int get_implied_value_helper(struct expression
*expr
, sval_t
*sval
, int implied
)
537 struct smatch_state
*state
;
541 /* fixme: this should return the casted value */
543 expr
= strip_expr(expr
);
545 if (get_value(expr
, sval
))
548 name
= expr_to_var_sym(expr
, &sym
);
551 *sval
= sval_blank(expr
);
552 state
= get_state(SMATCH_EXTRA
, name
, sym
);
554 if (!state
|| !state
->data
)
555 return get_local_value(expr
, sval
, implied
);
556 if (implied
== IMPLIED
) {
557 if (estate_get_single_value(state
, sval
))
561 if (implied
== HARD_MAX
) {
562 if (estate_get_hard_max(state
, sval
))
566 if (implied
== IMPLIED_MAX
|| implied
== ABSOLUTE_MAX
) {
567 *sval
= estate_max(state
);
570 *sval
= estate_min(state
);
574 static int get_fuzzy_max_helper(struct expression
*expr
, sval_t
*max
)
577 struct sm_state
*tmp
;
580 if (get_hard_max(expr
, &sval
)) {
585 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
589 sval
= sval_type_min(estate_type(sm
->state
));
590 FOR_EACH_PTR(sm
->possible
, tmp
) {
593 new_min
= estate_min(tmp
->state
);
594 if (sval_cmp(new_min
, sval
) > 0)
596 } END_FOR_EACH_PTR(tmp
);
598 if (sval_is_min(sval
))
600 if (sval
.value
== sval_type_min(sval
.type
).value
+ 1) /* it's common to be on off */
603 *max
= sval_cast(get_type(expr
), sval
);
607 static int get_fuzzy_min_helper(struct expression
*expr
, sval_t
*min
)
610 struct sm_state
*tmp
;
613 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
617 if (!sval_is_min(estate_min(sm
->state
))) {
618 *min
= estate_min(sm
->state
);
622 sval
= sval_type_max(estate_type(sm
->state
));
623 FOR_EACH_PTR(sm
->possible
, tmp
) {
626 new_max
= estate_max(tmp
->state
);
627 if (sval_cmp(new_max
, sval
) < 0)
629 } END_FOR_EACH_PTR(tmp
);
631 if (sval_is_max(sval
))
633 *min
= sval_cast(get_type(expr
), sval
);
637 static sval_t
_get_implied_value(struct expression
*expr
, int *undefined
, int implied
)
641 ret
= sval_blank(expr
);
650 if (!get_implied_value_helper(expr
, &ret
, implied
))
654 if (!get_fuzzy_max_helper(expr
, &ret
))
658 if (!get_fuzzy_min_helper(expr
, &ret
))
667 static int get_const_value(struct expression
*expr
, sval_t
*sval
)
672 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
675 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
677 if (get_value(sym
->initializer
, &right
)) {
678 *sval
= sval_cast(get_type(expr
), right
);
684 static sval_t
handle_sizeof(struct expression
*expr
)
689 ret
= sval_blank(expr
);
690 sym
= expr
->cast_type
;
692 sym
= evaluate_expression(expr
->cast_expression
);
694 * Expressions of restricted types will possibly get
695 * promoted - check that here
697 if (is_restricted_type(sym
)) {
698 if (sym
->bit_size
< bits_in_int
)
700 } else if (is_fouled_type(sym
)) {
704 examine_symbol_type(sym
);
706 ret
.type
= size_t_ctype
;
707 if (sym
->bit_size
<= 0) /* sizeof(void) */ {
708 if (get_real_base_type(sym
) == &void_ctype
)
713 ret
.value
= bits_to_bytes(sym
->bit_size
);
718 static sval_t
handle_call(struct expression
*expr
, int *undefined
, int implied
)
720 struct range_list
*rl
;
722 if (!get_implied_rl(expr
, &rl
)) {
729 if (sval_cmp(rl_min(rl
), rl_max(rl
)) == 0)
748 static sval_t
_get_value(struct expression
*expr
, int *undefined
, int implied
)
759 expr
= strip_parens(expr
);
761 switch (expr
->type
) {
763 ret
= sval_from_val(expr
, expr
->value
);
766 ret
= handle_preop(expr
, undefined
, implied
);
769 ret
= _get_value(expr
->unop
, undefined
, implied
);
772 case EXPR_FORCE_CAST
:
773 case EXPR_IMPLIED_CAST
:
774 ret
= _get_value(expr
->cast_expression
, undefined
, implied
);
775 ret
= sval_cast(get_type(expr
), ret
);
778 ret
= handle_binop(expr
, undefined
, implied
);
781 ret
= handle_comparison(expr
, undefined
, implied
);
784 ret
= handle_logical(expr
, undefined
, implied
);
788 ret
= handle_sizeof(expr
);
791 if (get_const_value(expr
, &ret
)) {
794 ret
= _get_implied_value(expr
, undefined
, implied
);
797 case EXPR_CONDITIONAL
:
798 ret
= handle_conditional(expr
, undefined
, implied
);
801 ret
= handle_call(expr
, undefined
, implied
);
804 ret
= _get_implied_value(expr
, undefined
, implied
);
811 /* returns 1 if it can get a value literal or else returns 0 */
812 int get_value(struct expression
*expr
, sval_t
*sval
)
817 ret
= _get_value(expr
, &undefined
, NOTIMPLIED
);
824 int get_implied_value(struct expression
*expr
, sval_t
*sval
)
829 ret
= _get_value(expr
, &undefined
, IMPLIED
);
836 int get_implied_min(struct expression
*expr
, sval_t
*sval
)
841 ret
= _get_value(expr
, &undefined
, IMPLIED_MIN
);
848 int get_implied_max(struct expression
*expr
, sval_t
*sval
)
853 ret
= _get_value(expr
, &undefined
, IMPLIED_MAX
);
860 int get_implied_rl(struct expression
*expr
, struct range_list
**rl
)
863 struct smatch_state
*state
;
870 expr
= strip_parens(expr
);
874 state
= get_state_expr(SMATCH_EXTRA
, expr
);
876 *rl
= clone_rl(estate_rl(state
));
880 if (expr
->type
== EXPR_CALL
) {
881 if (get_implied_return(expr
, rl
))
883 *rl
= db_return_vals(expr
);
889 if (get_implied_value(expr
, &sval
)) {
890 add_range(rl
, sval
, sval
);
894 if (get_local_rl(expr
, rl
))
897 min_known
= get_implied_min(expr
, &min
);
898 max_known
= get_implied_max(expr
, &max
);
899 if (!min_known
&& !max_known
)
902 get_absolute_min(expr
, &min
);
904 get_absolute_max(expr
, &max
);
906 *rl
= alloc_rl(min
, max
);
910 int get_hard_max(struct expression
*expr
, sval_t
*sval
)
915 ret
= _get_value(expr
, &undefined
, HARD_MAX
);
922 int get_fuzzy_min(struct expression
*expr
, sval_t
*sval
)
927 ret
= _get_value(expr
, &undefined
, FUZZY_MIN
);
934 int get_fuzzy_max(struct expression
*expr
, sval_t
*sval
)
939 ret
= _get_value(expr
, &undefined
, FUZZY_MAX
);
942 if (ret
.uvalue
> INT_MAX
- 10000)
948 int get_absolute_min(struct expression
*expr
, sval_t
*sval
)
953 type
= get_type(expr
);
955 type
= &llong_ctype
; // FIXME: this is wrong but places assume get type can't fail.
956 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MIN
);
958 *sval
= sval_type_min(type
);
962 if (sval_cmp(*sval
, sval_type_min(type
)) < 0)
963 *sval
= sval_type_min(type
);
967 int get_absolute_max(struct expression
*expr
, sval_t
*sval
)
972 type
= get_type(expr
);
975 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MAX
);
977 *sval
= sval_type_max(type
);
981 if (sval_cmp(sval_type_max(type
), *sval
) < 0)
982 *sval
= sval_type_max(type
);
986 int known_condition_true(struct expression
*expr
)
993 if (get_value(expr
, &tmp
) && tmp
.value
)
999 int known_condition_false(struct expression
*expr
)
1007 if (expr
->type
== EXPR_CALL
) {
1008 if (sym_name_is("__builtin_constant_p", expr
->fn
))
1014 int implied_condition_true(struct expression
*expr
)
1021 if (known_condition_true(expr
))
1023 if (get_implied_value(expr
, &tmp
) && tmp
.value
)
1026 if (expr
->type
== EXPR_POSTOP
)
1027 return implied_condition_true(expr
->unop
);
1029 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
1030 return implied_not_equal(expr
->unop
, 1);
1031 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
1032 return implied_not_equal(expr
->unop
, -1);
1034 expr
= strip_expr(expr
);
1035 switch (expr
->type
) {
1037 if (do_comparison(expr
) == 1)
1041 if (expr
->op
== '!') {
1042 if (implied_condition_false(expr
->unop
))
1048 if (implied_not_equal(expr
, 0) == 1)
1055 int implied_condition_false(struct expression
*expr
)
1057 struct expression
*tmp
;
1063 if (known_condition_false(expr
))
1066 switch (expr
->type
) {
1068 if (do_comparison(expr
) == 2)
1071 if (expr
->op
== '!') {
1072 if (implied_condition_true(expr
->unop
))
1076 tmp
= strip_expr(expr
);
1078 return implied_condition_false(tmp
);
1081 if (get_implied_value(expr
, &sval
) && sval
.value
== 0)