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
);
26 static long long cast_to_type(struct expression
*expr
, long long val
)
28 struct symbol
*type
= get_type(expr
);
33 switch (type
->bit_size
) {
35 if (type
->ctype
.modifiers
& MOD_UNSIGNED
)
36 val
= (long long)(unsigned char) val
;
38 val
= (long long)(char) val
;
41 if (type
->ctype
.modifiers
& MOD_UNSIGNED
)
42 val
= (long long)(unsigned short) val
;
44 val
= (long long)(short) val
;
47 if (type
->ctype
.modifiers
& MOD_UNSIGNED
)
48 val
= (long long)(unsigned int) val
;
50 val
= (long long)(int) val
;
56 static int opposite_implied(int implied
)
58 if (implied
== IMPLIED_MIN
)
60 if (implied
== IMPLIED_MAX
)
65 static int last_stmt_val(struct statement
*stmt
, long long *val
)
67 struct expression
*expr
;
72 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
73 if (stmt
->type
!= STMT_EXPRESSION
)
75 expr
= stmt
->expression
;
76 return get_value(expr
, val
);
79 static long long handle_expression_statement(struct expression
*expr
, int *undefined
, int implied
)
81 struct statement
*stmt
;
84 stmt
= get_expression_statement(expr
);
85 if (last_stmt_val(stmt
, &tmp
))
92 static long long handle_ampersand(int *undefined
, int implied
)
94 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
)
96 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
)
103 static long long handle_preop(struct expression
*expr
, int *undefined
, int implied
)
105 long long ret
= BOGUS
;
109 ret
= handle_ampersand(undefined
, implied
);
112 ret
= !_get_value(expr
->unop
, undefined
, implied
);
115 ret
= ~_get_value(expr
->unop
, undefined
, implied
);
116 ret
= cast_to_type(expr
->unop
, ret
);
119 ret
= -_get_value(expr
->unop
, undefined
, implied
);
122 ret
= _get_implied_value(expr
, undefined
, implied
);
125 ret
= handle_expression_statement(expr
, undefined
, implied
);
133 static long long handle_divide(struct expression
*expr
, int *undefined
, int implied
)
137 long long ret
= BOGUS
;
139 left
= _get_value(expr
->left
, undefined
, implied
);
140 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
150 static long long handle_subtract(struct expression
*expr
, int *undefined
, int implied
)
155 left
= _get_value(expr
->left
, undefined
, implied
);
156 right
= _get_value(expr
->right
, undefined
, opposite_implied(implied
));
161 static long long handle_binop(struct expression
*expr
, int *undefined
, int implied
)
165 long long ret
= BOGUS
;
167 if (expr
->type
!= EXPR_BINOP
) {
172 left
= _get_value(expr
->left
, undefined
, implied
);
173 right
= _get_value(expr
->right
, undefined
, implied
);
180 ret
= handle_divide(expr
, undefined
, implied
);
186 ret
= handle_subtract(expr
, undefined
, implied
);
200 case SPECIAL_RIGHTSHIFT
:
203 case SPECIAL_LEFTSHIFT
:
215 static int do_comparison(struct expression
*expr
)
217 struct range_list
*left_ranges
= NULL
;
218 struct range_list
*right_ranges
= NULL
;
219 int poss_true
, poss_false
;
221 get_implied_range_list(expr
->left
, &left_ranges
);
222 get_implied_range_list(expr
->right
, &right_ranges
);
224 poss_true
= possibly_true_range_lists(left_ranges
, expr
->op
, right_ranges
);
225 poss_false
= possibly_false_range_lists(left_ranges
, expr
->op
, right_ranges
);
227 free_range_list(&left_ranges
);
228 free_range_list(&right_ranges
);
230 if (!poss_true
&& !poss_false
)
232 if (poss_true
&& !poss_false
)
234 if (!poss_true
&& poss_false
)
239 static long long handle_comparison(struct expression
*expr
, int *undefined
, int implied
)
241 long long left
, right
;
244 if (get_value(expr
->left
, &left
) && get_value(expr
->right
, &right
)) {
245 struct data_range tmp_left
, tmp_right
;
249 tmp_right
.min
= right
;
250 tmp_right
.max
= right
;
251 return true_comparison_range(&tmp_left
, expr
->op
, &tmp_right
);
254 if (implied
== NOTIMPLIED
) {
259 res
= do_comparison(expr
);
265 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
)
267 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
)
274 static long long handle_logical(struct expression
*expr
, int *undefined
, int implied
)
276 long long left_val
, right_val
;
278 if ((implied
== NOTIMPLIED
&& get_value(expr
->left
, &left_val
) &&
279 get_value(expr
->right
, &right_val
)) ||
280 (implied
!= NOTIMPLIED
&& get_implied_value(expr
->left
, &left_val
) &&
281 get_implied_value(expr
->right
, &right_val
))) {
283 case SPECIAL_LOGICAL_OR
:
284 return left_val
|| right_val
;
285 case SPECIAL_LOGICAL_AND
:
286 return left_val
&& right_val
;
293 if (implied
== IMPLIED_MIN
|| implied
== FUZZYMIN
)
295 if (implied
== IMPLIED_MAX
|| implied
== FUZZYMAX
)
302 static long long handle_conditional(struct expression
*expr
, int *undefined
, int implied
)
304 if (known_condition_true(expr
->conditional
))
305 return _get_value(expr
->cond_true
, undefined
, implied
);
306 if (known_condition_false(expr
->conditional
))
307 return _get_value(expr
->cond_false
, undefined
, implied
);
309 if (implied
== NOTIMPLIED
) {
314 if (implied_condition_true(expr
->conditional
))
315 return _get_value(expr
->cond_true
, undefined
, implied
);
316 if (implied_condition_false(expr
->conditional
))
317 return _get_value(expr
->cond_false
, undefined
, implied
);
323 static int get_implied_value_helper(struct expression
*expr
, long long *val
, int what
)
325 struct smatch_state
*state
;
329 expr
= strip_expr(expr
);
331 if (get_value(expr
, val
))
334 name
= get_variable_from_expr(expr
, &sym
);
337 state
= get_state(SMATCH_EXTRA
, name
, sym
);
339 if (!state
|| !state
->data
)
342 return estate_get_single_value(state
, val
);
343 if (what
== IMPLIED_MAX
) {
344 *val
= estate_max(state
);
345 if (*val
== whole_range
.max
) /* this means just guessing */
349 *val
= estate_min(state
);
350 if (*val
== whole_range
.min
)
355 static int get_fuzzy_max_helper(struct expression
*expr
, long long *max
)
358 struct sm_state
*tmp
;
360 if (get_implied_max(expr
, max
))
363 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
367 *max
= whole_range
.min
;
368 FOR_EACH_PTR(sm
->possible
, tmp
) {
371 new_min
= estate_min(tmp
->state
);
374 } END_FOR_EACH_PTR(tmp
);
376 if (*max
> whole_range
.min
)
381 static int get_fuzzy_min_helper(struct expression
*expr
, long long *min
)
384 struct sm_state
*tmp
;
386 if (get_implied_min(expr
, min
))
389 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
393 *min
= whole_range
.max
;
394 FOR_EACH_PTR(sm
->possible
, tmp
) {
397 new_max
= estate_max(tmp
->state
);
400 } END_FOR_EACH_PTR(tmp
);
402 if (*min
< whole_range
.max
)
407 static long long _get_implied_value(struct expression
*expr
, int *undefined
, int implied
)
409 long long ret
= BOGUS
;
415 if (!get_implied_value_helper(expr
, &ret
, implied
))
419 if (!get_fuzzy_max_helper(expr
, &ret
))
423 if (!get_fuzzy_min_helper(expr
, &ret
))
432 static int get_const_value(struct expression
*expr
, long long *val
)
439 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
441 if (get_value(sym
->initializer
, val
))
446 static long long _get_value(struct expression
*expr
, int *undefined
, int implied
)
448 long long ret
= BOGUS
;
457 expr
= strip_parens(expr
);
459 switch (expr
->type
) {
462 ret
= cast_to_type(expr
, ret
);
465 ret
= handle_preop(expr
, undefined
, implied
);
468 ret
= _get_value(expr
->unop
, undefined
, implied
);
471 case EXPR_FORCE_CAST
:
472 case EXPR_IMPLIED_CAST
:
473 ret
= _get_value(expr
->cast_expression
, undefined
, implied
);
474 return cast_to_type(expr
, ret
);
476 ret
= handle_binop(expr
, undefined
, implied
);
479 ret
= handle_comparison(expr
, undefined
, implied
);
482 ret
= handle_logical(expr
, undefined
, implied
);
486 ret
= get_expression_value_nomod(expr
);
489 if (get_const_value(expr
, &ret
))
491 ret
= _get_implied_value(expr
, undefined
, implied
);
494 case EXPR_CONDITIONAL
:
495 ret
= handle_conditional(expr
, undefined
, implied
);
498 ret
= _get_implied_value(expr
, undefined
, implied
);
505 /* returns 1 if it can get a value literal or else returns 0 */
506 int get_value(struct expression
*expr
, long long *val
)
510 *val
= _get_value(expr
, &undefined
, NOTIMPLIED
);
516 int get_implied_value(struct expression
*expr
, long long *val
)
520 *val
= _get_value(expr
, &undefined
, IMPLIED
);
524 int get_implied_min(struct expression
*expr
, long long *val
)
528 *val
= _get_value(expr
, &undefined
, IMPLIED_MIN
);
532 int get_implied_max(struct expression
*expr
, long long *val
)
536 *val
= _get_value(expr
, &undefined
, IMPLIED_MAX
);
540 int get_fuzzy_min(struct expression
*expr
, long long *val
)
544 *val
= _get_value(expr
, &undefined
, FUZZYMIN
);
548 int get_fuzzy_max(struct expression
*expr
, long long *val
)
552 *val
= _get_value(expr
, &undefined
, FUZZYMAX
);
556 int get_absolute_min(struct expression
*expr
, long long *val
)
561 type
= get_type(expr
);
563 if (get_value(expr
, val
))
567 min
= type_min(type
);
568 if (!get_implied_min(expr
, val
) || *val
< min
)
573 int get_absolute_max(struct expression
*expr
, long long *val
)
578 type
= get_type(expr
);
580 if (get_value(expr
, val
))
584 max
= type_max(type
);
585 if (!get_implied_max(expr
, val
) || *val
> max
)
587 if (*val
< type_min(type
))
592 int known_condition_true(struct expression
*expr
)
599 if (get_value(expr
, &tmp
) && tmp
)
605 int known_condition_false(struct expression
*expr
)
613 if (expr
->type
== EXPR_CALL
) {
614 if (sym_name_is("__builtin_constant_p", expr
->fn
))
620 int implied_condition_true(struct expression
*expr
)
627 if (known_condition_true(expr
))
629 if (get_implied_value(expr
, &tmp
) && tmp
)
632 if (expr
->type
== EXPR_POSTOP
)
633 return implied_condition_true(expr
->unop
);
635 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
636 return implied_not_equal(expr
->unop
, 1);
637 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
638 return implied_not_equal(expr
->unop
, -1);
640 expr
= strip_expr(expr
);
641 switch (expr
->type
) {
643 if (do_comparison(expr
) == 1)
647 if (expr
->op
== '!') {
648 if (implied_condition_false(expr
->unop
))
654 if (implied_not_equal(expr
, 0) == 1)
661 int implied_condition_false(struct expression
*expr
)
663 struct expression
*tmp
;
669 if (known_condition_false(expr
))
672 switch (expr
->type
) {
674 if (do_comparison(expr
) == 2)
677 if (expr
->op
== '!') {
678 if (implied_condition_true(expr
->unop
))
682 tmp
= strip_expr(expr
);
684 return implied_condition_false(tmp
);
687 if (get_implied_value(expr
, &val
) && val
== 0)