2 * Copyright (C) 2010 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
20 #include "smatch_slist.h"
21 #include "smatch_extra.h"
23 static struct range_list
*_get_rl(struct expression
*expr
, int implied
, int *recurse_cnt
);
24 static struct range_list
*handle_variable(struct expression
*expr
, int implied
, int *recurse_cnt
);
25 static struct range_list
*(*custom_handle_variable
)(struct expression
*expr
);
27 static int get_implied_value_internal(struct expression
*expr
, sval_t
*sval
, int *recurse_cnt
);
28 static int get_absolute_rl_internal(struct expression
*expr
, struct range_list
**rl
, int *recurse_cnt
);
30 static sval_t zero
= {.type
= &int_ctype
, {.value
= 0} };
31 static sval_t one
= {.type
= &int_ctype
, {.value
= 1} };
33 struct range_list
*rl_zero(void)
35 return alloc_rl(zero
, zero
);
38 struct range_list
*rl_one(void)
40 return alloc_rl(one
, one
);
52 static struct range_list
*last_stmt_rl(struct statement
*stmt
, int implied
, int *recurse_cnt
)
54 struct expression
*expr
;
59 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
60 if (stmt
->type
== STMT_LABEL
) {
61 if (stmt
->label_statement
&&
62 stmt
->label_statement
->type
== STMT_EXPRESSION
)
63 expr
= stmt
->label_statement
->expression
;
66 } else if (stmt
->type
== STMT_EXPRESSION
) {
67 expr
= stmt
->expression
;
71 return _get_rl(expr
, implied
, recurse_cnt
);
74 static struct range_list
*handle_expression_statement_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
76 return last_stmt_rl(get_expression_statement(expr
), implied
, recurse_cnt
);
79 static struct range_list
*handle_ampersand_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
81 struct range_list
*rl
;
83 if (implied
== RL_EXACT
|| implied
== RL_HARD
)
85 if (get_address_rl(expr
, &rl
))
87 return alloc_rl(valid_ptr_min_sval
, valid_ptr_max_sval
);
90 static struct range_list
*handle_negate_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
92 if (known_condition_true(expr
->unop
))
94 if (known_condition_false(expr
->unop
))
97 if (implied
== RL_EXACT
)
100 if (implied_condition_true(expr
->unop
))
102 if (implied_condition_false(expr
->unop
))
104 return alloc_rl(zero
, one
);
107 static struct range_list
*handle_bitwise_negate(struct expression
*expr
, int implied
, int *recurse_cnt
)
109 struct range_list
*rl
;
112 rl
= _get_rl(expr
->unop
, implied
, recurse_cnt
);
113 if (!rl_to_sval(rl
, &sval
))
115 sval
= sval_preop(sval
, '~');
116 sval_cast(get_type(expr
->unop
), sval
);
117 return alloc_rl(sval
, sval
);
120 static struct range_list
*handle_minus_preop(struct expression
*expr
, int implied
, int *recurse_cnt
)
122 struct range_list
*rl
;
125 rl
= _get_rl(expr
->unop
, implied
, recurse_cnt
);
126 min
= sval_preop(rl_max(rl
), '-');
127 max
= sval_preop(rl_min(rl
), '-');
128 return alloc_rl(min
, max
);
131 static struct range_list
*handle_preop_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
135 return handle_ampersand_rl(expr
, implied
, recurse_cnt
);
137 return handle_negate_rl(expr
, implied
, recurse_cnt
);
139 return handle_bitwise_negate(expr
, implied
, recurse_cnt
);
141 return handle_minus_preop(expr
, implied
, recurse_cnt
);
143 return handle_variable(expr
, implied
, recurse_cnt
);
145 return handle_expression_statement_rl(expr
, implied
, recurse_cnt
);
151 static struct range_list
*handle_divide_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
153 struct range_list
*left_rl
, *right_rl
;
156 type
= get_type(expr
);
158 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
159 left_rl
= cast_rl(type
, left_rl
);
160 right_rl
= _get_rl(expr
->right
, implied
, recurse_cnt
);
161 right_rl
= cast_rl(type
, right_rl
);
163 if (!left_rl
|| !right_rl
)
166 if (implied
!= RL_REAL_ABSOLUTE
) {
167 if (is_whole_rl(left_rl
) || is_whole_rl(right_rl
))
171 return rl_binop(left_rl
, '/', right_rl
);
174 static int handle_offset_subtraction(struct expression
*expr
)
176 struct expression
*left
, *right
;
177 struct symbol
*left_sym
, *right_sym
;
179 int left_offset
, right_offset
;
181 type
= get_type(expr
);
182 if (!type
|| type
->type
!= SYM_PTR
)
184 type
= get_real_base_type(type
);
185 if (!type
|| (type_bits(type
) != 8 && (type
!= &void_ctype
)))
188 left
= strip_expr(expr
->left
);
189 right
= strip_expr(expr
->right
);
191 if (left
->type
!= EXPR_PREOP
|| left
->op
!= '&')
193 left
= strip_expr(left
->unop
);
195 left_sym
= expr_to_sym(left
);
196 right_sym
= expr_to_sym(right
);
197 if (!left_sym
|| left_sym
!= right_sym
)
200 left_offset
= get_member_offset_from_deref(left
);
201 if (right
->type
== EXPR_SYMBOL
)
204 if (right
->type
!= EXPR_PREOP
|| right
->op
!= '&')
206 right
= strip_expr(right
->unop
);
207 right_offset
= get_member_offset_from_deref(right
);
209 if (left_offset
< 0 || right_offset
< 0)
212 return left_offset
- right_offset
;
215 static struct range_list
*handle_subtract_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
218 struct range_list
*left_orig
, *right_orig
;
219 struct range_list
*left_rl
, *right_rl
;
220 sval_t max
, min
, tmp
;
224 type
= get_type(expr
);
226 offset
= handle_offset_subtraction(expr
);
231 return alloc_rl(tmp
, tmp
);
234 comparison
= get_comparison(expr
->left
, expr
->right
);
236 left_orig
= _get_rl(expr
->left
, implied
, recurse_cnt
);
237 left_rl
= cast_rl(type
, left_orig
);
238 right_orig
= _get_rl(expr
->right
, implied
, recurse_cnt
);
239 right_rl
= cast_rl(type
, right_orig
);
241 if ((!left_rl
|| !right_rl
) &&
242 (implied
== RL_EXACT
|| implied
== RL_HARD
|| implied
== RL_FUZZY
))
246 left_rl
= alloc_whole_rl(type
);
248 right_rl
= alloc_whole_rl(type
);
250 /* negative values complicate everything fix this later */
251 if (sval_is_negative(rl_min(right_rl
)))
253 max
= rl_max(left_rl
);
254 min
= sval_type_min(type
);
256 switch (comparison
) {
258 case SPECIAL_UNSIGNED_GT
:
259 min
= sval_type_val(type
, 1);
260 max
= rl_max(left_rl
);
263 case SPECIAL_UNSIGNED_GTE
:
264 min
= sval_type_val(type
, 0);
265 max
= rl_max(left_rl
);
268 min
= sval_type_val(type
, 0);
269 max
= sval_type_val(type
, 0);
272 case SPECIAL_UNSIGNED_LT
:
273 max
= sval_type_val(type
, -1);
276 case SPECIAL_UNSIGNED_LTE
:
277 max
= sval_type_val(type
, 0);
280 if (!left_orig
|| !right_orig
)
282 return rl_binop(left_rl
, '-', right_rl
);
285 if (!sval_binop_overflows(rl_min(left_rl
), '-', rl_max(right_rl
))) {
286 tmp
= sval_binop(rl_min(left_rl
), '-', rl_max(right_rl
));
287 if (sval_cmp(tmp
, min
) > 0)
291 if (!sval_is_max(rl_max(left_rl
))) {
292 tmp
= sval_binop(rl_max(left_rl
), '-', rl_min(right_rl
));
293 if (sval_cmp(tmp
, max
) < 0)
297 if (sval_is_min(min
) && sval_is_max(max
))
300 return cast_rl(type
, alloc_rl(min
, max
));
303 static struct range_list
*handle_mod_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
305 struct range_list
*rl
;
306 sval_t left
, right
, sval
;
308 if (implied
== RL_EXACT
) {
309 if (!get_implied_value(expr
->right
, &right
))
311 if (!get_implied_value(expr
->left
, &left
))
313 sval
= sval_binop(left
, '%', right
);
314 return alloc_rl(sval
, sval
);
316 /* if we can't figure out the right side it's probably hopeless */
317 if (!get_implied_value_internal(expr
->right
, &right
, recurse_cnt
))
320 right
= sval_cast(get_type(expr
), right
);
323 rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
324 if (rl
&& rl_max(rl
).uvalue
< right
.uvalue
)
325 right
.uvalue
= rl_max(rl
).uvalue
;
327 return alloc_rl(sval_cast(right
.type
, zero
), right
);
330 static sval_t
sval_lowest_set_bit(sval_t sval
)
335 for (i
= 0; i
< 64; i
++) {
336 if (sval
.uvalue
& 1ULL << i
) {
339 sval
.uvalue
&= ~(1ULL << i
);
345 static struct range_list
*handle_bitwise_AND(struct expression
*expr
, int implied
, int *recurse_cnt
)
348 struct range_list
*left_rl
, *right_rl
;
352 if (implied
!= RL_IMPLIED
&& implied
!= RL_ABSOLUTE
&& implied
!= RL_REAL_ABSOLUTE
)
355 type
= get_type(expr
);
357 if (get_implied_value_internal(expr
->left
, &known
, recurse_cnt
)) {
360 min
= sval_lowest_set_bit(known
);
361 left_rl
= alloc_rl(min
, known
);
362 left_rl
= cast_rl(type
, left_rl
);
363 add_range(&left_rl
, sval_type_val(type
, 0), sval_type_val(type
, 0));
365 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
367 left_rl
= cast_rl(type
, left_rl
);
368 left_rl
= alloc_rl(sval_type_val(type
, 0), rl_max(left_rl
));
370 if (implied
== RL_HARD
)
372 left_rl
= alloc_whole_rl(type
);
376 new_recurse
= *recurse_cnt
;
377 if (*recurse_cnt
>= 200)
378 new_recurse
= 100; /* Let's try super hard to get the mask */
379 if (get_implied_value_internal(expr
->right
, &known
, &new_recurse
)) {
380 sval_t min
, left_max
, mod
;
382 *recurse_cnt
= new_recurse
;
384 min
= sval_lowest_set_bit(known
);
385 right_rl
= alloc_rl(min
, known
);
386 right_rl
= cast_rl(type
, right_rl
);
387 add_range(&right_rl
, sval_type_val(type
, 0), sval_type_val(type
, 0));
389 if (min
.value
!= 0) {
390 left_max
= rl_max(left_rl
);
391 mod
= sval_binop(left_max
, '%', min
);
393 left_max
= sval_binop(left_max
, '-', mod
);
395 if (left_max
.value
> 0 && sval_cmp(left_max
, rl_max(left_rl
)) < 0)
396 left_rl
= remove_range(left_rl
, left_max
, rl_max(left_rl
));
400 right_rl
= _get_rl(expr
->right
, implied
, recurse_cnt
);
402 right_rl
= cast_rl(type
, right_rl
);
403 right_rl
= alloc_rl(sval_type_val(type
, 0), rl_max(right_rl
));
405 if (implied
== RL_HARD
)
407 right_rl
= alloc_whole_rl(type
);
411 return rl_intersection(left_rl
, right_rl
);
414 static struct range_list
*use_rl_binop(struct expression
*expr
, int implied
, int *recurse_cnt
)
417 struct range_list
*left_rl
, *right_rl
;
419 if (implied
!= RL_IMPLIED
&& implied
!= RL_ABSOLUTE
&& implied
!= RL_REAL_ABSOLUTE
)
422 type
= get_type(expr
);
424 get_absolute_rl_internal(expr
->left
, &left_rl
, recurse_cnt
);
425 get_absolute_rl_internal(expr
->right
, &right_rl
, recurse_cnt
);
426 left_rl
= cast_rl(type
, left_rl
);
427 right_rl
= cast_rl(type
, right_rl
);
428 if (!left_rl
|| !right_rl
)
431 return rl_binop(left_rl
, expr
->op
, right_rl
);
434 static struct range_list
*handle_right_shift(struct expression
*expr
, int implied
, int *recurse_cnt
)
436 struct range_list
*left_rl
;
440 if (implied
== RL_EXACT
|| implied
== RL_HARD
)
443 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
445 max
= rl_max(left_rl
);
446 min
= rl_min(left_rl
);
448 if (implied
== RL_FUZZY
)
450 max
= sval_type_max(get_type(expr
->left
));
451 min
= sval_type_val(get_type(expr
->left
), 0);
454 if (get_implied_value_internal(expr
->right
, &right
, recurse_cnt
)) {
455 min
= sval_binop(min
, SPECIAL_RIGHTSHIFT
, right
);
456 max
= sval_binop(max
, SPECIAL_RIGHTSHIFT
, right
);
457 } else if (!sval_is_negative(min
)) {
459 max
= sval_type_max(max
.type
);
464 return alloc_rl(min
, max
);
467 static struct range_list
*handle_left_shift(struct expression
*expr
, int implied
, int *recurse_cnt
)
469 struct range_list
*left_rl
, *res
;
474 if (implied
== RL_EXACT
|| implied
== RL_HARD
)
476 /* this is hopeless without the right side */
477 if (!get_implied_value_internal(expr
->right
, &right
, recurse_cnt
))
479 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
481 max
= rl_max(left_rl
);
482 min
= rl_min(left_rl
);
483 if (min
.value
== 0) {
488 if (implied
== RL_FUZZY
)
490 max
= sval_type_max(get_type(expr
->left
));
491 min
= sval_type_val(get_type(expr
->left
), 1);
495 max
= sval_binop(max
, SPECIAL_LEFTSHIFT
, right
);
496 min
= sval_binop(min
, SPECIAL_LEFTSHIFT
, right
);
497 res
= alloc_rl(min
, max
);
499 res
= rl_union(res
, rl_zero());
503 static struct range_list
*handle_known_binop(struct expression
*expr
)
507 if (!get_value(expr
->left
, &left
))
509 if (!get_value(expr
->right
, &right
))
511 left
= sval_binop(left
, expr
->op
, right
);
512 return alloc_rl(left
, left
);
515 static int has_actual_ranges(struct range_list
*rl
)
517 struct data_range
*tmp
;
519 FOR_EACH_PTR(rl
, tmp
) {
520 if (sval_cmp(tmp
->min
, tmp
->max
) != 0)
522 } END_FOR_EACH_PTR(tmp
);
526 static struct range_list
*handle_implied_binop(struct range_list
*left_rl
, int op
, struct range_list
*right_rl
)
528 struct range_list
*res_rl
;
529 struct data_range
*left_drange
, *right_drange
;
532 if (!left_rl
|| !right_rl
)
534 if (has_actual_ranges(left_rl
))
536 if (has_actual_ranges(right_rl
))
539 if (ptr_list_size((struct ptr_list
*)left_rl
) * ptr_list_size((struct ptr_list
*)right_rl
) > 20)
544 FOR_EACH_PTR(left_rl
, left_drange
) {
545 FOR_EACH_PTR(right_rl
, right_drange
) {
546 if ((op
== '%' || op
== '/') &&
547 right_drange
->min
.value
== 0)
549 res
= sval_binop(left_drange
->min
, op
, right_drange
->min
);
550 add_range(&res_rl
, res
, res
);
551 } END_FOR_EACH_PTR(right_drange
);
552 } END_FOR_EACH_PTR(left_drange
);
557 static struct range_list
*handle_binop_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
559 struct smatch_state
*state
;
561 struct range_list
*left_rl
, *right_rl
, *rl
;
564 rl
= handle_known_binop(expr
);
567 if (implied
== RL_EXACT
)
570 if (custom_handle_variable
) {
571 rl
= custom_handle_variable(expr
);
576 state
= get_extra_state(expr
);
577 if (state
&& !is_whole_rl(estate_rl(state
))) {
578 if (implied
!= RL_HARD
|| estate_has_hard_max(state
))
579 return clone_rl(estate_rl(state
));
582 type
= get_type(expr
);
583 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
584 left_rl
= cast_rl(type
, left_rl
);
585 right_rl
= _get_rl(expr
->right
, implied
, recurse_cnt
);
586 right_rl
= cast_rl(type
, right_rl
);
588 if (!left_rl
&& !right_rl
)
591 rl
= handle_implied_binop(left_rl
, expr
->op
, right_rl
);
597 return handle_mod_rl(expr
, implied
, recurse_cnt
);
599 return handle_bitwise_AND(expr
, implied
, recurse_cnt
);
602 return use_rl_binop(expr
, implied
, recurse_cnt
);
603 case SPECIAL_RIGHTSHIFT
:
604 return handle_right_shift(expr
, implied
, recurse_cnt
);
605 case SPECIAL_LEFTSHIFT
:
606 return handle_left_shift(expr
, implied
, recurse_cnt
);
608 return handle_subtract_rl(expr
, implied
, recurse_cnt
);
610 return handle_divide_rl(expr
, implied
, recurse_cnt
);
613 if (!left_rl
|| !right_rl
)
616 if (sval_binop_overflows(rl_min(left_rl
), expr
->op
, rl_min(right_rl
)))
618 if (sval_binop_overflows(rl_max(left_rl
), expr
->op
, rl_max(right_rl
)))
621 min
= sval_binop(rl_min(left_rl
), expr
->op
, rl_min(right_rl
));
622 max
= sval_binop(rl_max(left_rl
), expr
->op
, rl_max(right_rl
));
624 return alloc_rl(min
, max
);
627 static int do_comparison(struct expression
*expr
)
629 struct range_list
*left_ranges
= NULL
;
630 struct range_list
*right_ranges
= NULL
;
631 int poss_true
, poss_false
;
634 type
= get_type(expr
);
635 get_absolute_rl(expr
->left
, &left_ranges
);
636 get_absolute_rl(expr
->right
, &right_ranges
);
638 left_ranges
= cast_rl(type
, left_ranges
);
639 right_ranges
= cast_rl(type
, right_ranges
);
641 poss_true
= possibly_true_rl(left_ranges
, expr
->op
, right_ranges
);
642 poss_false
= possibly_false_rl(left_ranges
, expr
->op
, right_ranges
);
644 free_rl(&left_ranges
);
645 free_rl(&right_ranges
);
647 if (!poss_true
&& !poss_false
)
649 if (poss_true
&& !poss_false
)
651 if (!poss_true
&& poss_false
)
656 static struct range_list
*handle_comparison_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
661 if (expr
->op
== SPECIAL_EQUAL
&& expr
->left
->type
== EXPR_TYPE
) {
662 struct symbol
*left
, *right
;
664 left
= get_real_base_type(expr
->left
->symbol
);
665 right
= get_real_base_type(expr
->left
->symbol
);
671 if (get_value(expr
->left
, &left
) && get_value(expr
->right
, &right
)) {
672 struct data_range tmp_left
, tmp_right
;
676 tmp_right
.min
= right
;
677 tmp_right
.max
= right
;
678 if (true_comparison_range(&tmp_left
, expr
->op
, &tmp_right
))
683 if (implied
== RL_EXACT
)
686 res
= do_comparison(expr
);
692 return alloc_rl(zero
, one
);
695 static struct range_list
*handle_logical_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
701 if (implied
== RL_EXACT
) {
702 if (get_value(expr
->left
, &left
))
704 if (get_value(expr
->right
, &right
))
707 if (get_implied_value_internal(expr
->left
, &left
, recurse_cnt
))
709 if (get_implied_value_internal(expr
->right
, &right
, recurse_cnt
))
714 case SPECIAL_LOGICAL_OR
:
715 if (left_known
&& left
.value
)
717 if (right_known
&& right
.value
)
719 if (left_known
&& right_known
)
722 case SPECIAL_LOGICAL_AND
:
723 if (left_known
&& right_known
) {
724 if (left
.value
&& right
.value
)
733 if (implied
== RL_EXACT
)
736 return alloc_rl(zero
, one
);
739 static struct range_list
*handle_conditional_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
741 struct range_list
*true_rl
, *false_rl
;
743 int final_pass_orig
= final_pass
;
745 if (known_condition_true(expr
->conditional
))
746 return _get_rl(expr
->cond_true
, implied
, recurse_cnt
);
747 if (known_condition_false(expr
->conditional
))
748 return _get_rl(expr
->cond_false
, implied
, recurse_cnt
);
750 if (implied
== RL_EXACT
)
753 if (implied_condition_true(expr
->conditional
))
754 return _get_rl(expr
->cond_true
, implied
, recurse_cnt
);
755 if (implied_condition_false(expr
->conditional
))
756 return _get_rl(expr
->cond_false
, implied
, recurse_cnt
);
759 /* this becomes a problem with deeply nested conditional statements */
763 type
= get_type(expr
);
765 __push_fake_cur_stree();
767 __split_whole_condition(expr
->conditional
);
768 true_rl
= _get_rl(expr
->cond_true
, implied
, recurse_cnt
);
769 __push_true_states();
770 __use_false_states();
771 false_rl
= _get_rl(expr
->cond_false
, implied
, recurse_cnt
);
772 __merge_true_states();
773 __free_fake_cur_stree();
774 final_pass
= final_pass_orig
;
776 if (!true_rl
|| !false_rl
)
778 true_rl
= cast_rl(type
, true_rl
);
779 false_rl
= cast_rl(type
, false_rl
);
781 return rl_union(true_rl
, false_rl
);
784 static int get_fuzzy_max_helper(struct expression
*expr
, sval_t
*max
)
786 struct smatch_state
*state
;
789 if (get_hard_max(expr
, &sval
)) {
794 state
= get_extra_state(expr
);
795 if (!state
|| !estate_has_fuzzy_max(state
))
797 *max
= sval_cast(get_type(expr
), estate_get_fuzzy_max(state
));
801 static int get_fuzzy_min_helper(struct expression
*expr
, sval_t
*min
)
803 struct smatch_state
*state
;
806 state
= get_extra_state(expr
);
807 if (!state
|| !estate_rl(state
))
810 sval
= estate_min(state
);
811 if (sval_is_negative(sval
) && sval_is_min(sval
))
814 if (sval_is_max(sval
))
817 *min
= sval_cast(get_type(expr
), sval
);
821 int get_const_value(struct expression
*expr
, sval_t
*sval
)
826 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
829 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
831 if (get_value(sym
->initializer
, &right
)) {
832 *sval
= sval_cast(get_type(expr
), right
);
838 struct range_list
*var_to_absolute_rl(struct expression
*expr
)
840 struct smatch_state
*state
;
841 struct range_list
*rl
;
843 state
= get_extra_state(expr
);
844 if (!state
|| is_whole_rl(estate_rl(state
))) {
845 state
= get_real_absolute_state(expr
);
846 if (state
&& state
->data
&& !estate_is_whole(state
))
847 return clone_rl(estate_rl(state
));
848 if (get_local_rl(expr
, &rl
) && !is_whole_rl(rl
))
850 if (get_db_type_rl(expr
, &rl
) && !is_whole_rl(rl
))
852 return alloc_whole_rl(get_type(expr
));
854 /* err on the side of saying things are possible */
855 if (!estate_rl(state
))
856 return alloc_whole_rl(get_type(expr
));
857 return clone_rl(estate_rl(state
));
860 static struct range_list
*handle_variable(struct expression
*expr
, int implied
, int *recurse_cnt
)
862 struct smatch_state
*state
;
863 struct range_list
*rl
;
864 sval_t sval
, min
, max
;
867 if (get_const_value(expr
, &sval
))
868 return alloc_rl(sval
, sval
);
870 if (custom_handle_variable
) {
871 rl
= custom_handle_variable(expr
);
873 return var_to_absolute_rl(expr
);
877 if (implied
== RL_EXACT
)
880 type
= get_type(expr
);
881 if (type
&& type
->type
== SYM_FN
)
882 return alloc_rl(fn_ptr_min
, fn_ptr_max
);
888 state
= get_extra_state(expr
);
889 if (!state
|| !state
->data
) {
890 if (implied
== RL_HARD
)
892 if (get_local_rl(expr
, &rl
))
894 if (get_db_type_rl(expr
, &rl
))
898 if (implied
== RL_HARD
&& !estate_has_hard_max(state
))
900 return clone_rl(estate_rl(state
));
901 case RL_REAL_ABSOLUTE
: {
902 struct smatch_state
*abs_state
;
904 state
= get_extra_state(expr
);
905 abs_state
= get_real_absolute_state(expr
);
907 if (estate_rl(state
) && estate_rl(abs_state
)) {
908 return clone_rl(rl_intersection(estate_rl(state
),
909 estate_rl(abs_state
)));
910 } else if (estate_rl(state
)) {
911 return clone_rl(estate_rl(state
));
912 } else if (estate_is_empty(state
)) {
914 * FIXME: we don't handle empty extra states correctly.
916 * The real abs rl is supposed to be filtered by the
917 * extra state if there is one. We don't bother keeping
918 * the abs state in sync all the time because we know it
919 * will be filtered later.
921 * It's not totally obvious to me how they should be
922 * handled. Perhaps we should take the whole rl and
923 * filter by the imaginary states. Perhaps we should
924 * just go with the empty state.
926 * Anyway what we currently do is return NULL here and
927 * that gets translated into the whole range in
928 * get_real_absolute_rl().
932 } else if (estate_rl(abs_state
)) {
933 return clone_rl(estate_rl(abs_state
));
936 if (get_local_rl(expr
, &rl
))
938 if (get_db_type_rl(expr
, &rl
))
943 if (!get_fuzzy_min_helper(expr
, &min
))
944 min
= sval_type_min(get_type(expr
));
945 if (!get_fuzzy_max_helper(expr
, &max
))
947 /* fuzzy ranges are often inverted */
948 if (sval_cmp(min
, max
) > 0) {
953 return alloc_rl(min
, max
);
958 static sval_t
handle_sizeof(struct expression
*expr
)
963 ret
= sval_blank(expr
);
964 sym
= expr
->cast_type
;
966 sym
= evaluate_expression(expr
->cast_expression
);
968 __silence_warnings_for_stmt
= true;
973 * Expressions of restricted types will possibly get
974 * promoted - check that here. I'm not sure how this works,
975 * the problem is that sizeof(le16) shouldn't be promoted and
976 * the original code did that... Let's if zero this out and
980 if (is_restricted_type(sym
)) {
981 if (type_bits(sym
) < bits_in_int
)
985 if (is_fouled_type(sym
))
988 examine_symbol_type(sym
);
990 ret
.type
= size_t_ctype
;
991 if (type_bits(sym
) <= 0) /* sizeof(void) */ {
992 if (get_real_base_type(sym
) == &void_ctype
)
997 ret
.value
= type_bytes(sym
);
1002 static struct range_list
*handle_strlen(struct expression
*expr
, int implied
, int *recurse_cnt
)
1004 struct range_list
*rl
;
1005 struct expression
*arg
;
1006 sval_t sval
= { .type
= &ulong_ctype
};
1008 if (implied
== RL_EXACT
)
1011 arg
= get_argument_from_call_expr(expr
->args
, 0);
1014 if (arg
->type
== EXPR_STRING
) {
1015 sval
.value
= arg
->string
->length
- 1;
1016 return alloc_rl(sval
, sval
);
1019 if (implied
== RL_HARD
|| implied
== RL_FUZZY
)
1022 if (get_implied_return(expr
, &rl
))
1028 static struct range_list
*handle_call_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
1030 struct range_list
*rl
;
1032 if (sym_name_is("__builtin_expect", expr
->fn
) ||
1033 sym_name_is("__builtin_bswap16", expr
->fn
) ||
1034 sym_name_is("__builtin_bswap32", expr
->fn
) ||
1035 sym_name_is("__builtin_bswap64", expr
->fn
)) {
1036 struct expression
*arg
;
1038 arg
= get_argument_from_call_expr(expr
->args
, 0);
1039 return _get_rl(arg
, implied
, recurse_cnt
);
1042 if (sym_name_is("strlen", expr
->fn
))
1043 return handle_strlen(expr
, implied
, recurse_cnt
);
1045 if (implied
== RL_EXACT
|| implied
== RL_HARD
|| implied
== RL_FUZZY
)
1048 if (custom_handle_variable
) {
1049 rl
= custom_handle_variable(expr
);
1054 if (get_implied_return(expr
, &rl
))
1056 return db_return_vals(expr
);
1059 static struct range_list
*handle_cast(struct expression
*expr
, int implied
, int *recurse_cnt
)
1061 struct range_list
*rl
;
1062 struct symbol
*type
;
1064 type
= get_type(expr
);
1065 rl
= _get_rl(expr
->cast_expression
, implied
, recurse_cnt
);
1067 return cast_rl(type
, rl
);
1068 if (implied
== RL_ABSOLUTE
|| implied
== RL_REAL_ABSOLUTE
)
1069 return alloc_whole_rl(type
);
1070 if (implied
== RL_IMPLIED
&& type
&&
1071 type_bits(type
) > 0 && type_bits(type
) < 32)
1072 return alloc_whole_rl(type
);
1076 static struct range_list
*_get_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
1078 struct range_list
*rl
;
1079 struct symbol
*type
;
1082 type
= get_type(expr
);
1083 expr
= strip_parens(expr
);
1087 if (++(*recurse_cnt
) >= 200)
1090 switch(expr
->type
) {
1092 case EXPR_FORCE_CAST
:
1093 case EXPR_IMPLIED_CAST
:
1094 rl
= handle_cast(expr
, implied
, recurse_cnt
);
1098 expr
= strip_expr(expr
);
1102 switch (expr
->type
) {
1104 sval
= sval_from_val(expr
, expr
->value
);
1105 rl
= alloc_rl(sval
, sval
);
1108 rl
= handle_preop_rl(expr
, implied
, recurse_cnt
);
1111 rl
= _get_rl(expr
->unop
, implied
, recurse_cnt
);
1114 rl
= handle_binop_rl(expr
, implied
, recurse_cnt
);
1117 rl
= handle_comparison_rl(expr
, implied
, recurse_cnt
);
1120 rl
= handle_logical_rl(expr
, implied
, recurse_cnt
);
1122 case EXPR_PTRSIZEOF
:
1124 sval
= handle_sizeof(expr
);
1125 rl
= alloc_rl(sval
, sval
);
1128 case EXPR_CONDITIONAL
:
1129 rl
= handle_conditional_rl(expr
, implied
, recurse_cnt
);
1132 rl
= handle_call_rl(expr
, implied
, recurse_cnt
);
1135 rl
= handle_variable(expr
, implied
, recurse_cnt
);
1141 if (type
&& (implied
== RL_ABSOLUTE
|| implied
== RL_REAL_ABSOLUTE
))
1142 return alloc_whole_rl(type
);
1146 /* returns 1 if it can get a value literal or else returns 0 */
1147 int get_value(struct expression
*expr
, sval_t
*sval
)
1149 struct range_list
*rl
;
1150 int recurse_cnt
= 0;
1152 rl
= _get_rl(expr
, RL_EXACT
, &recurse_cnt
);
1153 if (!rl_to_sval(rl
, sval
))
1158 static int get_implied_value_internal(struct expression
*expr
, sval_t
*sval
, int *recurse_cnt
)
1160 struct range_list
*rl
;
1162 rl
= _get_rl(expr
, RL_IMPLIED
, recurse_cnt
);
1163 if (!rl_to_sval(rl
, sval
))
1168 int get_implied_value(struct expression
*expr
, sval_t
*sval
)
1170 struct range_list
*rl
;
1171 int recurse_cnt
= 0;
1173 rl
= _get_rl(expr
, RL_IMPLIED
, &recurse_cnt
);
1174 if (!rl_to_sval(rl
, sval
))
1179 int get_implied_min(struct expression
*expr
, sval_t
*sval
)
1181 struct range_list
*rl
;
1182 int recurse_cnt
= 0;
1184 rl
= _get_rl(expr
, RL_IMPLIED
, &recurse_cnt
);
1191 int get_implied_max(struct expression
*expr
, sval_t
*sval
)
1193 struct range_list
*rl
;
1194 int recurse_cnt
= 0;
1196 rl
= _get_rl(expr
, RL_IMPLIED
, &recurse_cnt
);
1203 int get_implied_rl(struct expression
*expr
, struct range_list
**rl
)
1205 int recurse_cnt
= 0;
1207 *rl
= _get_rl(expr
, RL_IMPLIED
, &recurse_cnt
);
1213 static int get_absolute_rl_internal(struct expression
*expr
, struct range_list
**rl
, int *recurse_cnt
)
1215 *rl
= _get_rl(expr
, RL_ABSOLUTE
, recurse_cnt
);
1217 *rl
= alloc_whole_rl(get_type(expr
));
1221 int get_absolute_rl(struct expression
*expr
, struct range_list
**rl
)
1223 int recurse_cnt
= 0;
1225 *rl
= _get_rl(expr
, RL_ABSOLUTE
, &recurse_cnt
);
1227 *rl
= alloc_whole_rl(get_type(expr
));
1231 int get_real_absolute_rl(struct expression
*expr
, struct range_list
**rl
)
1233 int recurse_cnt
= 0;
1235 *rl
= _get_rl(expr
, RL_REAL_ABSOLUTE
, &recurse_cnt
);
1237 *rl
= alloc_whole_rl(get_type(expr
));
1241 int custom_get_absolute_rl(struct expression
*expr
,
1242 struct range_list
*(*fn
)(struct expression
*expr
),
1243 struct range_list
**rl
)
1245 int recurse_cnt
= 0;
1248 custom_handle_variable
= fn
;
1249 *rl
= _get_rl(expr
, RL_REAL_ABSOLUTE
, &recurse_cnt
);
1250 custom_handle_variable
= NULL
;
1254 int get_implied_rl_var_sym(const char *var
, struct symbol
*sym
, struct range_list
**rl
)
1256 struct smatch_state
*state
;
1258 state
= get_state(SMATCH_EXTRA
, var
, sym
);
1259 *rl
= estate_rl(state
);
1265 int get_hard_max(struct expression
*expr
, sval_t
*sval
)
1267 struct range_list
*rl
;
1268 int recurse_cnt
= 0;
1270 rl
= _get_rl(expr
, RL_HARD
, &recurse_cnt
);
1277 int get_fuzzy_min(struct expression
*expr
, sval_t
*sval
)
1279 struct range_list
*rl
;
1281 int recurse_cnt
= 0;
1283 rl
= _get_rl(expr
, RL_FUZZY
, &recurse_cnt
);
1287 if (sval_is_negative(tmp
) && sval_is_min(tmp
))
1293 int get_fuzzy_max(struct expression
*expr
, sval_t
*sval
)
1295 struct range_list
*rl
;
1297 int recurse_cnt
= 0;
1299 rl
= _get_rl(expr
, RL_FUZZY
, &recurse_cnt
);
1303 if (max
.uvalue
> INT_MAX
- 10000)
1309 int get_absolute_min(struct expression
*expr
, sval_t
*sval
)
1311 struct range_list
*rl
;
1312 struct symbol
*type
;
1313 int recurse_cnt
= 0;
1315 type
= get_type(expr
);
1317 type
= &llong_ctype
; // FIXME: this is wrong but places assume get type can't fail.
1318 rl
= _get_rl(expr
, RL_REAL_ABSOLUTE
, &recurse_cnt
);
1322 *sval
= sval_type_min(type
);
1324 if (sval_cmp(*sval
, sval_type_min(type
)) < 0)
1325 *sval
= sval_type_min(type
);
1329 int get_absolute_max(struct expression
*expr
, sval_t
*sval
)
1331 struct range_list
*rl
;
1332 struct symbol
*type
;
1333 int recurse_cnt
= 0;
1335 type
= get_type(expr
);
1337 type
= &llong_ctype
;
1338 rl
= _get_rl(expr
, RL_REAL_ABSOLUTE
, &recurse_cnt
);
1342 *sval
= sval_type_max(type
);
1344 if (sval_cmp(sval_type_max(type
), *sval
) < 0)
1345 *sval
= sval_type_max(type
);
1349 int known_condition_true(struct expression
*expr
)
1356 if (get_value(expr
, &tmp
) && tmp
.value
)
1362 int known_condition_false(struct expression
*expr
)
1370 if (expr
->type
== EXPR_CALL
) {
1371 if (sym_name_is("__builtin_constant_p", expr
->fn
))
1377 int implied_condition_true(struct expression
*expr
)
1384 if (known_condition_true(expr
))
1386 if (get_implied_value(expr
, &tmp
) && tmp
.value
)
1389 if (expr
->type
== EXPR_POSTOP
)
1390 return implied_condition_true(expr
->unop
);
1392 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
1393 return implied_not_equal(expr
->unop
, 1);
1394 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
1395 return implied_not_equal(expr
->unop
, -1);
1397 expr
= strip_expr(expr
);
1398 switch (expr
->type
) {
1400 if (do_comparison(expr
) == 1)
1404 if (expr
->op
== '!') {
1405 if (implied_condition_false(expr
->unop
))
1411 if (implied_not_equal(expr
, 0) == 1)
1418 int implied_condition_false(struct expression
*expr
)
1420 struct expression
*tmp
;
1426 if (known_condition_false(expr
))
1429 switch (expr
->type
) {
1431 if (do_comparison(expr
) == 2)
1434 if (expr
->op
== '!') {
1435 if (implied_condition_true(expr
->unop
))
1439 tmp
= strip_expr(expr
);
1441 return implied_condition_false(tmp
);
1444 if (get_implied_value(expr
, &sval
) && sval
.value
== 0)
1451 int can_integer_overflow(struct symbol
*type
, struct expression
*expr
)
1454 sval_t lmax
, rmax
, res
;
1459 expr
= strip_expr(expr
);
1461 if (expr
->type
== EXPR_ASSIGNMENT
) {
1463 case SPECIAL_MUL_ASSIGN
:
1466 case SPECIAL_ADD_ASSIGN
:
1469 case SPECIAL_SHL_ASSIGN
:
1470 op
= SPECIAL_LEFTSHIFT
;
1475 } else if (expr
->type
== EXPR_BINOP
) {
1476 if (expr
->op
!= '*' && expr
->op
!= '+' && expr
->op
!= SPECIAL_LEFTSHIFT
)
1483 get_absolute_max(expr
->left
, &lmax
);
1484 get_absolute_max(expr
->right
, &rmax
);
1486 if (sval_binop_overflows(lmax
, op
, rmax
))
1489 res
= sval_binop(lmax
, op
, rmax
);
1490 if (sval_cmp(res
, sval_type_max(type
)) > 0)