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 long long _get_implied_value(struct expression
*expr
, int *undefined
, int implied
);
15 static long long _get_value(struct expression
*expr
, int *undefined
, int implied
);
25 #define ABSOLUTE_MIN 6
26 #define ABSOLUTE_MAX 7
28 static long long cast_to_type(struct expression
*expr
, long long val
)
30 struct symbol
*type
= get_type(expr
);
35 switch (type
->bit_size
) {
37 if (type
->ctype
.modifiers
& MOD_UNSIGNED
)
38 val
= (long long)(unsigned char) val
;
40 val
= (long long)(char) val
;
43 if (type
->ctype
.modifiers
& MOD_UNSIGNED
)
44 val
= (long long)(unsigned short) val
;
46 val
= (long long)(short) val
;
49 if (type
->ctype
.modifiers
& MOD_UNSIGNED
)
50 val
= (long long)(unsigned int) val
;
52 val
= (long long)(int) val
;
58 static int opposite_implied(int implied
)
60 if (implied
== IMPLIED_MIN
)
62 if (implied
== IMPLIED_MAX
)
64 if (implied
== ABSOLUTE_MIN
)
66 if (implied
== ABSOLUTE_MAX
)
71 static int last_stmt_val(struct statement
*stmt
, long long *val
)
73 struct expression
*expr
;
78 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
79 if (stmt
->type
!= STMT_EXPRESSION
)
81 expr
= stmt
->expression
;
82 return get_value(expr
, val
);
85 static long long handle_expression_statement(struct expression
*expr
, int *undefined
, int implied
)
87 struct statement
*stmt
;
90 stmt
= get_expression_statement(expr
);
91 if (last_stmt_val(stmt
, &tmp
))
98 static long long handle_ampersand(int *undefined
, int implied
)
100 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
|| implied
== ABSOLUTE_MIN
)
101 return valid_ptr_min
;
102 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
|| implied
== ABSOLUTE_MAX
)
103 return valid_ptr_max
;
109 static long long handle_preop(struct expression
*expr
, int *undefined
, int implied
)
111 long long ret
= BOGUS
;
115 ret
= handle_ampersand(undefined
, implied
);
118 ret
= !_get_value(expr
->unop
, undefined
, implied
);
121 ret
= ~_get_value(expr
->unop
, undefined
, implied
);
122 ret
= cast_to_type(expr
->unop
, ret
);
125 ret
= -_get_value(expr
->unop
, undefined
, implied
);
128 ret
= _get_implied_value(expr
, undefined
, implied
);
131 ret
= handle_expression_statement(expr
, undefined
, implied
);
139 static long long handle_divide(struct expression
*expr
, int *undefined
, int implied
)
143 long long ret
= BOGUS
;
145 left
= _get_value(expr
->left
, undefined
, implied
);
146 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
156 static long long handle_subtract(struct expression
*expr
, int *undefined
, int implied
)
161 left
= _get_value(expr
->left
, undefined
, implied
);
162 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
167 static long long handle_binop(struct expression
*expr
, int *undefined
, int implied
)
171 long long ret
= BOGUS
;
175 sm_msg("handle_binop %s", show_special(expr
->op
));
179 left
= _get_value(expr
->left
, &local_undef
, implied
);
181 if (implied
== ABSOLUTE_MIN
)
183 if (implied
!= ABSOLUTE_MAX
)
185 if (!get_absolute_max(expr
->left
, &left
))
188 right
= _get_value(expr
->right
, undefined
, implied
);
196 left
= _get_value(expr
->left
, &local_undef
, implied
);
198 if (implied
== ABSOLUTE_MIN
)
200 if (implied
!= ABSOLUTE_MAX
)
202 if (!get_absolute_max(expr
->left
, &left
))
205 right
= _get_value(expr
->right
, undefined
, implied
);
207 case SPECIAL_RIGHTSHIFT
:
208 left
= _get_value(expr
->left
, &local_undef
, implied
);
210 if (implied
== ABSOLUTE_MIN
)
212 if (implied
!= ABSOLUTE_MAX
)
214 if (!get_absolute_max(expr
->left
, &left
))
217 right
= _get_value(expr
->right
, undefined
, implied
);
218 return left
>> right
;
221 left
= _get_value(expr
->left
, undefined
, implied
);
222 right
= _get_value(expr
->right
, undefined
, implied
);
229 ret
= handle_divide(expr
, undefined
, implied
);
235 ret
= handle_subtract(expr
, undefined
, implied
);
249 case SPECIAL_RIGHTSHIFT
:
252 case SPECIAL_LEFTSHIFT
:
264 static int do_comparison(struct expression
*expr
)
266 struct range_list
*left_ranges
= NULL
;
267 struct range_list
*right_ranges
= NULL
;
268 int poss_true
, poss_false
;
270 get_implied_range_list(expr
->left
, &left_ranges
);
271 get_implied_range_list(expr
->right
, &right_ranges
);
273 poss_true
= possibly_true_range_lists(left_ranges
, expr
->op
, right_ranges
);
274 poss_false
= possibly_false_range_lists(left_ranges
, expr
->op
, right_ranges
);
276 free_range_list(&left_ranges
);
277 free_range_list(&right_ranges
);
279 if (!poss_true
&& !poss_false
)
281 if (poss_true
&& !poss_false
)
283 if (!poss_true
&& poss_false
)
288 static long long handle_comparison(struct expression
*expr
, int *undefined
, int implied
)
290 long long left
, right
;
293 if (get_value(expr
->left
, &left
) && get_value(expr
->right
, &right
)) {
294 struct data_range tmp_left
, tmp_right
;
298 tmp_right
.min
= right
;
299 tmp_right
.max
= right
;
300 return true_comparison_range(&tmp_left
, expr
->op
, &tmp_right
);
303 if (implied
== NOTIMPLIED
) {
308 res
= do_comparison(expr
);
314 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
|| implied
== ABSOLUTE_MIN
)
316 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
|| implied
== ABSOLUTE_MAX
)
323 static long long handle_logical(struct expression
*expr
, int *undefined
, int implied
)
325 long long left_val
, right_val
;
327 if ((implied
== NOTIMPLIED
&& get_value(expr
->left
, &left_val
) &&
328 get_value(expr
->right
, &right_val
)) ||
329 (implied
!= NOTIMPLIED
&& get_implied_value(expr
->left
, &left_val
) &&
330 get_implied_value(expr
->right
, &right_val
))) {
332 case SPECIAL_LOGICAL_OR
:
333 return left_val
|| right_val
;
334 case SPECIAL_LOGICAL_AND
:
335 return left_val
&& right_val
;
342 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
|| implied
== ABSOLUTE_MIN
)
344 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
|| implied
== ABSOLUTE_MAX
)
351 static long long handle_conditional(struct expression
*expr
, int *undefined
, int implied
)
353 if (known_condition_true(expr
->conditional
))
354 return _get_value(expr
->cond_true
, undefined
, implied
);
355 if (known_condition_false(expr
->conditional
))
356 return _get_value(expr
->cond_false
, undefined
, implied
);
358 if (implied
== NOTIMPLIED
) {
363 if (implied_condition_true(expr
->conditional
))
364 return _get_value(expr
->cond_true
, undefined
, implied
);
365 if (implied_condition_false(expr
->conditional
))
366 return _get_value(expr
->cond_false
, undefined
, implied
);
372 static int get_implied_value_helper(struct expression
*expr
, long long *val
, int what
)
374 struct smatch_state
*state
;
378 expr
= strip_expr(expr
);
380 if (get_value(expr
, val
))
383 name
= get_variable_from_expr(expr
, &sym
);
386 state
= get_state(SMATCH_EXTRA
, name
, sym
);
388 if (!state
|| !state
->data
)
391 return estate_get_single_value(state
, val
);
392 if (what
== IMPLIED_MAX
|| what
== ABSOLUTE_MAX
) {
393 *val
= estate_max(state
);
394 if (*val
== whole_range
.max
) /* this means just guessing */
398 *val
= estate_min(state
);
399 if (*val
== whole_range
.min
)
404 static int get_fuzzy_max_helper(struct expression
*expr
, long long *max
)
407 struct sm_state
*tmp
;
409 if (get_implied_max(expr
, max
))
412 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
416 *max
= whole_range
.min
;
417 FOR_EACH_PTR(sm
->possible
, tmp
) {
420 new_min
= estate_min(tmp
->state
);
423 } END_FOR_EACH_PTR(tmp
);
425 if (*max
> whole_range
.min
)
430 static int get_fuzzy_min_helper(struct expression
*expr
, long long *min
)
433 struct sm_state
*tmp
;
435 if (get_implied_min(expr
, min
))
438 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
442 *min
= whole_range
.max
;
443 FOR_EACH_PTR(sm
->possible
, tmp
) {
446 new_max
= estate_max(tmp
->state
);
449 } END_FOR_EACH_PTR(tmp
);
451 if (*min
< whole_range
.max
)
456 static long long _get_implied_value(struct expression
*expr
, int *undefined
, int implied
)
458 long long ret
= BOGUS
;
464 if (!get_implied_value_helper(expr
, &ret
, implied
))
469 struct smatch_state
*state
;
470 struct data_range
*range
;
472 if (get_implied_value_helper(expr
, &ret
, implied
))
475 state
= get_state_expr(absolute_id
, expr
);
476 if (!state
|| !state
->data
) {
481 if (implied
== ABSOLUTE_MAX
)
488 if (!get_fuzzy_max_helper(expr
, &ret
))
492 if (!get_fuzzy_min_helper(expr
, &ret
))
501 static int get_const_value(struct expression
*expr
, long long *val
)
508 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
510 if (get_value(sym
->initializer
, val
))
515 static long long _get_value(struct expression
*expr
, int *undefined
, int implied
)
517 long long ret
= BOGUS
;
526 expr
= strip_parens(expr
);
528 switch (expr
->type
) {
531 ret
= cast_to_type(expr
, ret
);
534 ret
= handle_preop(expr
, undefined
, implied
);
537 ret
= _get_value(expr
->unop
, undefined
, implied
);
540 case EXPR_FORCE_CAST
:
541 case EXPR_IMPLIED_CAST
:
542 ret
= _get_value(expr
->cast_expression
, undefined
, implied
);
543 return cast_to_type(expr
, ret
);
545 ret
= handle_binop(expr
, undefined
, implied
);
548 ret
= handle_comparison(expr
, undefined
, implied
);
551 ret
= handle_logical(expr
, undefined
, implied
);
555 ret
= get_expression_value_nomod(expr
);
558 if (get_const_value(expr
, &ret
))
560 ret
= _get_implied_value(expr
, undefined
, implied
);
563 case EXPR_CONDITIONAL
:
564 ret
= handle_conditional(expr
, undefined
, implied
);
567 ret
= _get_implied_value(expr
, undefined
, implied
);
574 /* returns 1 if it can get a value literal or else returns 0 */
575 int get_value(struct expression
*expr
, long long *val
)
579 *val
= _get_value(expr
, &undefined
, NOTIMPLIED
);
585 int get_implied_value(struct expression
*expr
, long long *val
)
589 *val
= _get_value(expr
, &undefined
, IMPLIED
);
593 int get_implied_min(struct expression
*expr
, long long *val
)
597 *val
= _get_value(expr
, &undefined
, IMPLIED_MIN
);
601 int get_implied_max(struct expression
*expr
, long long *val
)
605 *val
= _get_value(expr
, &undefined
, IMPLIED_MAX
);
609 int get_fuzzy_min(struct expression
*expr
, long long *val
)
613 *val
= _get_value(expr
, &undefined
, FUZZYMIN
);
617 int get_fuzzy_max(struct expression
*expr
, long long *val
)
621 *val
= _get_value(expr
, &undefined
, FUZZYMAX
);
625 int get_absolute_min(struct expression
*expr
, long long *val
)
630 type
= get_type(expr
);
631 *val
= _get_value(expr
, &undefined
, ABSOLUTE_MIN
);
633 *val
= type_min(type
);
637 if (type_min(type
) > *val
)
638 *val
= type_min(type
);
642 int get_absolute_max(struct expression
*expr
, long long *val
)
647 type
= get_type(expr
);
648 *val
= _get_value(expr
, &undefined
, ABSOLUTE_MAX
);
650 *val
= type_max(type
);
654 if (type_max(type
) < *val
)
655 *val
= type_max(type
);
659 int known_condition_true(struct expression
*expr
)
666 if (get_value(expr
, &tmp
) && tmp
)
672 int known_condition_false(struct expression
*expr
)
680 if (expr
->type
== EXPR_CALL
) {
681 if (sym_name_is("__builtin_constant_p", expr
->fn
))
687 int implied_condition_true(struct expression
*expr
)
694 if (known_condition_true(expr
))
696 if (get_implied_value(expr
, &tmp
) && tmp
)
699 if (expr
->type
== EXPR_POSTOP
)
700 return implied_condition_true(expr
->unop
);
702 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
703 return implied_not_equal(expr
->unop
, 1);
704 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
705 return implied_not_equal(expr
->unop
, -1);
707 expr
= strip_expr(expr
);
708 switch (expr
->type
) {
710 if (do_comparison(expr
) == 1)
714 if (expr
->op
== '!') {
715 if (implied_condition_false(expr
->unop
))
721 if (implied_not_equal(expr
, 0) == 1)
728 int implied_condition_false(struct expression
*expr
)
730 struct expression
*tmp
;
736 if (known_condition_false(expr
))
739 switch (expr
->type
) {
741 if (do_comparison(expr
) == 2)
744 if (expr
->op
== '!') {
745 if (implied_condition_true(expr
->unop
))
749 tmp
= strip_expr(expr
);
751 return implied_condition_false(tmp
);
754 if (get_implied_value(expr
, &val
) && val
== 0)