4 * Copyright (C) 2010 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 #include "smatch_slist.h"
12 #include "smatch_extra.h"
14 static sval_t
_get_value(struct expression
*expr
, int *undefined
, int implied
);
15 static sval_t
_get_implied_value(struct expression
*expr
, int *undefined
, int implied
);
19 static sval_t zero
= {.type
= &int_ctype
, .value
= 0};
20 static sval_t one
= {.type
= &int_ctype
, .value
= 1};
21 static sval_t bogus
= {.type
= &int_ctype
, .value
= BOGUS
};
35 static int opposite_implied(int implied
)
37 if (implied
== IMPLIED_MIN
)
39 if (implied
== IMPLIED_MAX
)
41 if (implied
== FUZZY_MIN
)
43 if (implied
== FUZZY_MAX
)
45 if (implied
== ABSOLUTE_MIN
)
47 if (implied
== ABSOLUTE_MAX
)
53 static int last_stmt_sval(struct statement
*stmt
, sval_t
*sval
)
55 struct expression
*expr
;
60 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
61 if (stmt
->type
!= STMT_EXPRESSION
)
63 expr
= stmt
->expression
;
64 if (!get_value(expr
, sval
))
69 static sval_t
handle_expression_statement(struct expression
*expr
, int *undefined
, int implied
)
71 struct statement
*stmt
;
74 stmt
= get_expression_statement(expr
);
75 if (!last_stmt_sval(stmt
, &ret
)) {
83 static sval_t
handle_ampersand(int *undefined
, int implied
)
87 ret
.type
= &ptr_ctype
;
90 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
91 return valid_ptr_min_sval
;
92 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
93 return valid_ptr_max_sval
;
99 static sval_t
handle_negate(struct expression
*expr
, int *undefined
, int implied
)
103 ret
= sval_blank(expr
->unop
);
105 if (known_condition_true(expr
->unop
)) {
110 if (implied
== NOTIMPLIED
) {
115 if (implied_condition_true(expr
->unop
)) {
119 if (implied_condition_false(expr
->unop
)) {
123 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
) {
127 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
) {
135 static sval_t
handle_preop(struct expression
*expr
, int *undefined
, int implied
)
141 ret
= handle_ampersand(undefined
, implied
);
144 ret
= handle_negate(expr
, undefined
, implied
);
147 ret
= _get_value(expr
->unop
, undefined
, implied
);
148 ret
= sval_preop(ret
, '~');
149 ret
= sval_cast(get_type(expr
->unop
), ret
);
152 ret
= _get_value(expr
->unop
, undefined
, implied
);
153 ret
= sval_preop(ret
, '-');
156 ret
= _get_implied_value(expr
, undefined
, implied
);
159 ret
= handle_expression_statement(expr
, undefined
, implied
);
163 ret
= sval_blank(expr
);
165 ret
= sval_cast(get_type(expr
), ret
);
169 static sval_t
handle_divide(struct expression
*expr
, int *undefined
, int implied
)
173 left
= _get_value(expr
->left
, undefined
, implied
);
174 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
176 if (right
.value
== 0) {
181 return sval_binop(left
, '/', right
);
184 static sval_t
handle_subtract(struct expression
*expr
, int *undefined
, int implied
)
187 sval_t left
, right
, ret
;
188 int left_undefined
= 0;
189 int right_undefined
= 0;
190 int known_but_negative
= 0;
193 left
= _get_value(expr
->left
, &left_undefined
, implied
);
194 right
= _get_value(expr
->right
, &right_undefined
, opposite_implied(implied
));
196 if (!left_undefined
&& !right_undefined
) {
197 ret
= sval_binop(left
, '-', right
);
198 if (sval_is_negative(ret
))
199 known_but_negative
= 1;
201 return ret
; /* best case scenario */
204 comparison
= get_comparison(expr
->left
, expr
->right
);
208 type
= get_type(expr
);
210 switch (comparison
) {
212 case SPECIAL_UNSIGNED_GT
:
217 return sval_type_val(type
, 1);
221 return _get_value(expr
->left
, undefined
, implied
);
225 case SPECIAL_UNSIGNED_GTE
:
230 return sval_type_val(type
, 0);
234 return _get_value(expr
->left
, undefined
, implied
);
239 if (known_but_negative
)
247 static sval_t
handle_mod(struct expression
*expr
, int *undefined
, int implied
)
251 /* if we can't figure out the right side it's probably hopeless */
252 right
= _get_value(expr
->right
, undefined
, implied
);
253 if (*undefined
|| right
.value
== 0)
256 left
= _get_value(expr
->left
, undefined
, implied
);
258 return sval_binop(left
, '%', right
);
268 return sval_type_val(get_type(expr
->left
), 0);
273 right
= sval_cast(get_type(expr
), right
);
280 static sval_t
handle_binop(struct expression
*expr
, int *undefined
, int implied
)
284 sval_t ret
= {.type
= &int_ctype
, .value
= 123456};
289 return handle_mod(expr
, undefined
, implied
);
291 left
= _get_value(expr
->left
, &local_undef
, implied
);
293 if (implied
== IMPLIED_MIN
|| implied
== ABSOLUTE_MIN
) {
294 ret
= sval_blank(expr
->left
);
298 if (implied
!= IMPLIED_MAX
&& implied
!= ABSOLUTE_MAX
)
300 if (!get_absolute_max(expr
->left
, &left
))
303 right
= _get_value(expr
->right
, undefined
, implied
);
306 return sval_binop(left
, '&', right
);
308 case SPECIAL_RIGHTSHIFT
:
309 left
= _get_value(expr
->left
, &local_undef
, implied
);
311 if (implied
== IMPLIED_MIN
|| implied
== ABSOLUTE_MIN
) {
312 ret
= sval_blank(expr
->left
);
316 if (implied
!= IMPLIED_MAX
&& implied
!= ABSOLUTE_MAX
)
318 if (!get_absolute_max(expr
->left
, &left
))
321 right
= _get_value(expr
->right
, undefined
, implied
);
324 return sval_binop(left
, SPECIAL_RIGHTSHIFT
, right
);
326 return handle_subtract(expr
, undefined
, implied
);
329 left
= _get_value(expr
->left
, undefined
, implied
);
330 right
= _get_value(expr
->right
, undefined
, implied
);
335 type
= get_type(expr
);
336 left
= sval_cast(type
, left
);
337 right
= sval_cast(type
, right
);
342 if (sval_binop_overflows(left
, expr
->op
, right
))
343 return sval_type_max(get_type(expr
));
347 if (sval_binop_overflows(left
, expr
->op
, right
)) {
355 return handle_divide(expr
, undefined
, implied
);
357 if (right
.value
== 0) {
361 return sval_binop(left
, '%', right
);
364 ret
= sval_binop(left
, expr
->op
, right
);
369 static int do_comparison(struct expression
*expr
)
371 struct range_list
*left_ranges
= NULL
;
372 struct range_list
*right_ranges
= NULL
;
373 int poss_true
, poss_false
;
375 get_implied_rl(expr
->left
, &left_ranges
);
376 get_implied_rl(expr
->right
, &right_ranges
);
378 poss_true
= possibly_true_rl(left_ranges
, expr
->op
, right_ranges
);
379 poss_false
= possibly_false_rl(left_ranges
, expr
->op
, right_ranges
);
381 free_rl(&left_ranges
);
382 free_rl(&right_ranges
);
384 if (!poss_true
&& !poss_false
)
386 if (poss_true
&& !poss_false
)
388 if (!poss_true
&& poss_false
)
393 static sval_t
handle_comparison(struct expression
*expr
, int *undefined
, int implied
)
398 if (get_value(expr
->left
, &left
) && get_value(expr
->right
, &right
)) {
399 struct data_range tmp_left
, tmp_right
;
403 tmp_right
.min
= right
;
404 tmp_right
.max
= right
;
405 if (true_comparison_range(&tmp_left
, expr
->op
, &tmp_right
))
410 if (implied
== NOTIMPLIED
) {
415 res
= do_comparison(expr
);
421 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
423 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
430 static sval_t
handle_logical(struct expression
*expr
, int *undefined
, int implied
)
436 if (implied
== NOTIMPLIED
) {
437 if (get_value(expr
->left
, &left
))
439 if (get_value(expr
->right
, &right
))
442 if (get_implied_value(expr
->left
, &left
))
444 if (get_implied_value(expr
->right
, &right
))
449 case SPECIAL_LOGICAL_OR
:
450 if (left_known
&& left
.value
)
452 if (right_known
&& right
.value
)
454 if (left_known
&& right_known
)
457 case SPECIAL_LOGICAL_AND
:
458 if (left_known
&& right_known
) {
459 if (left
.value
&& right
.value
)
469 if (implied
== IMPLIED_MIN
|| implied
== FUZZY_MIN
|| implied
== ABSOLUTE_MIN
)
471 if (implied
== IMPLIED_MAX
|| implied
== FUZZY_MAX
|| implied
== ABSOLUTE_MAX
)
478 static sval_t
handle_conditional(struct expression
*expr
, int *undefined
, int implied
)
480 if (known_condition_true(expr
->conditional
))
481 return _get_value(expr
->cond_true
, undefined
, implied
);
482 if (known_condition_false(expr
->conditional
))
483 return _get_value(expr
->cond_false
, undefined
, implied
);
485 if (implied
== NOTIMPLIED
) {
490 if (implied_condition_true(expr
->conditional
))
491 return _get_value(expr
->cond_true
, undefined
, implied
);
492 if (implied_condition_false(expr
->conditional
))
493 return _get_value(expr
->cond_false
, undefined
, implied
);
499 static int get_implied_value_helper(struct expression
*expr
, sval_t
*sval
, int implied
)
501 struct smatch_state
*state
;
505 /* fixme: this should return the casted value */
507 expr
= strip_expr(expr
);
509 if (get_value(expr
, sval
))
512 name
= expr_to_var_sym(expr
, &sym
);
515 *sval
= sval_blank(expr
);
516 state
= get_state(SMATCH_EXTRA
, name
, sym
);
518 if (!state
|| !state
->data
)
520 if (implied
== IMPLIED
) {
521 if (estate_get_single_value(state
, sval
))
525 if (implied
== HARD_MAX
) {
526 if (estate_get_hard_max(state
, sval
))
530 if (implied
== IMPLIED_MAX
) {
531 *sval
= estate_max(state
);
532 if (sval_is_max(*sval
)) /* this means just guessing. fixme. not really */
536 *sval
= estate_min(state
);
537 if (sval_is_min(*sval
)) /* fixme */
542 static int get_fuzzy_max_helper(struct expression
*expr
, sval_t
*max
)
545 struct sm_state
*tmp
;
548 if (get_hard_max(expr
, &sval
)) {
553 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
557 sval
= sval_type_min(estate_type(sm
->state
));
558 FOR_EACH_PTR(sm
->possible
, tmp
) {
561 new_min
= estate_min(tmp
->state
);
562 if (sval_cmp(new_min
, sval
) > 0)
564 } END_FOR_EACH_PTR(tmp
);
566 if (sval_is_min(sval
))
568 if (sval
.value
== sval_type_min(sval
.type
).value
+ 1) /* it's common to be on off */
571 *max
= sval_cast(get_type(expr
), sval
);
575 static int get_fuzzy_min_helper(struct expression
*expr
, sval_t
*min
)
578 struct sm_state
*tmp
;
581 if (get_implied_min(expr
, min
))
584 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
588 sval
= sval_type_max(estate_type(sm
->state
));
589 FOR_EACH_PTR(sm
->possible
, tmp
) {
592 new_max
= estate_max(tmp
->state
);
593 if (sval_cmp(new_max
, sval
) < 0)
595 } END_FOR_EACH_PTR(tmp
);
597 if (sval_is_max(sval
))
599 *min
= sval_cast(get_type(expr
), sval
);
603 static sval_t
_get_implied_value(struct expression
*expr
, int *undefined
, int implied
)
607 ret
= sval_blank(expr
);
614 if (!get_implied_value_helper(expr
, &ret
, implied
))
618 if (!get_absolute_min_helper(expr
, &ret
))
622 if (!get_absolute_max_helper(expr
, &ret
))
626 if (!get_fuzzy_max_helper(expr
, &ret
))
630 if (!get_fuzzy_min_helper(expr
, &ret
))
639 static int get_const_value(struct expression
*expr
, sval_t
*sval
)
644 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
647 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
649 if (get_value(sym
->initializer
, &right
)) {
650 *sval
= sval_cast(get_type(expr
), right
);
656 static sval_t
_get_value(struct expression
*expr
, int *undefined
, int implied
)
667 expr
= strip_parens(expr
);
669 switch (expr
->type
) {
671 ret
= sval_from_val(expr
, expr
->value
);
674 ret
= handle_preop(expr
, undefined
, implied
);
677 ret
= _get_value(expr
->unop
, undefined
, implied
);
680 case EXPR_FORCE_CAST
:
681 case EXPR_IMPLIED_CAST
:
682 ret
= _get_value(expr
->cast_expression
, undefined
, implied
);
683 ret
= sval_cast(get_type(expr
), ret
);
686 ret
= handle_binop(expr
, undefined
, implied
);
689 ret
= handle_comparison(expr
, undefined
, implied
);
692 ret
= handle_logical(expr
, undefined
, implied
);
696 ret
= sval_blank(expr
);
697 ret
.value
= get_expression_value_nomod(expr
);
700 if (get_const_value(expr
, &ret
)) {
703 ret
= _get_implied_value(expr
, undefined
, implied
);
706 case EXPR_CONDITIONAL
:
707 ret
= handle_conditional(expr
, undefined
, implied
);
710 ret
= _get_implied_value(expr
, undefined
, implied
);
717 /* returns 1 if it can get a value literal or else returns 0 */
718 int get_value(struct expression
*expr
, sval_t
*sval
)
723 ret
= _get_value(expr
, &undefined
, NOTIMPLIED
);
730 int get_implied_value(struct expression
*expr
, sval_t
*sval
)
735 ret
= _get_value(expr
, &undefined
, IMPLIED
);
742 int get_implied_min(struct expression
*expr
, sval_t
*sval
)
747 ret
= _get_value(expr
, &undefined
, IMPLIED_MIN
);
754 int get_implied_max(struct expression
*expr
, sval_t
*sval
)
759 ret
= _get_value(expr
, &undefined
, IMPLIED_MAX
);
766 int get_implied_rl(struct expression
*expr
, struct range_list
**rl
)
769 struct smatch_state
*state
;
776 expr
= strip_parens(expr
);
780 state
= get_state_expr(SMATCH_EXTRA
, expr
);
782 *rl
= clone_rl(estate_rl(state
));
786 if (expr
->type
== EXPR_CALL
) {
787 if (get_implied_return(expr
, rl
))
789 *rl
= db_return_vals(expr
);
795 if (get_implied_value(expr
, &sval
)) {
796 add_range(rl
, sval
, sval
);
800 min_known
= get_implied_min(expr
, &min
);
801 max_known
= get_implied_max(expr
, &max
);
802 if (!min_known
&& !max_known
)
805 get_absolute_min(expr
, &min
);
807 get_absolute_max(expr
, &max
);
809 *rl
= alloc_rl(min
, max
);
813 int get_hard_max(struct expression
*expr
, sval_t
*sval
)
818 ret
= _get_value(expr
, &undefined
, HARD_MAX
);
825 int get_fuzzy_min(struct expression
*expr
, sval_t
*sval
)
830 ret
= _get_value(expr
, &undefined
, FUZZY_MIN
);
837 int get_fuzzy_max(struct expression
*expr
, sval_t
*sval
)
842 ret
= _get_value(expr
, &undefined
, FUZZY_MAX
);
849 int get_absolute_min(struct expression
*expr
, sval_t
*sval
)
854 type
= get_type(expr
);
856 type
= &llong_ctype
; // FIXME: this is wrong but places assume get type can't fail.
857 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MIN
);
859 *sval
= sval_type_min(type
);
863 if (sval_cmp(*sval
, sval_type_min(type
)) < 0)
864 *sval
= sval_type_min(type
);
868 int get_absolute_max(struct expression
*expr
, sval_t
*sval
)
873 type
= get_type(expr
);
876 *sval
= _get_value(expr
, &undefined
, ABSOLUTE_MAX
);
878 *sval
= sval_type_max(type
);
882 if (sval_cmp(sval_type_max(type
), *sval
) < 0)
883 *sval
= sval_type_max(type
);
887 int known_condition_true(struct expression
*expr
)
894 if (get_value(expr
, &tmp
) && tmp
.value
)
900 int known_condition_false(struct expression
*expr
)
908 if (expr
->type
== EXPR_CALL
) {
909 if (sym_name_is("__builtin_constant_p", expr
->fn
))
915 int implied_condition_true(struct expression
*expr
)
922 if (known_condition_true(expr
))
924 if (get_implied_value(expr
, &tmp
) && tmp
.value
)
927 if (expr
->type
== EXPR_POSTOP
)
928 return implied_condition_true(expr
->unop
);
930 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
931 return implied_not_equal(expr
->unop
, 1);
932 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
933 return implied_not_equal(expr
->unop
, -1);
935 expr
= strip_expr(expr
);
936 switch (expr
->type
) {
938 if (do_comparison(expr
) == 1)
942 if (expr
->op
== '!') {
943 if (implied_condition_false(expr
->unop
))
949 if (implied_not_equal(expr
, 0) == 1)
956 int implied_condition_false(struct expression
*expr
)
958 struct expression
*tmp
;
964 if (known_condition_false(expr
))
967 switch (expr
->type
) {
969 if (do_comparison(expr
) == 2)
972 if (expr
->op
== '!') {
973 if (implied_condition_true(expr
->unop
))
977 tmp
= strip_expr(expr
);
979 return implied_condition_false(tmp
);
982 if (get_implied_value(expr
, &sval
) && sval
.value
== 0)