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 static struct range_list
*zero_perm
;
38 zero_perm
= clone_rl_permanent(alloc_rl(zero
, zero
));
42 struct range_list
*rl_one(void)
44 static struct range_list
*one_perm
;
47 one_perm
= clone_rl_permanent(alloc_rl(one
, one
));
61 static struct range_list
*last_stmt_rl(struct statement
*stmt
, int implied
, int *recurse_cnt
)
63 struct expression
*expr
;
68 stmt
= last_ptr_list((struct ptr_list
*)stmt
->stmts
);
69 if (stmt
->type
== STMT_LABEL
) {
70 if (stmt
->label_statement
&&
71 stmt
->label_statement
->type
== STMT_EXPRESSION
)
72 expr
= stmt
->label_statement
->expression
;
75 } else if (stmt
->type
== STMT_EXPRESSION
) {
76 expr
= stmt
->expression
;
80 return _get_rl(expr
, implied
, recurse_cnt
);
83 static struct range_list
*handle_expression_statement_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
85 return last_stmt_rl(get_expression_statement(expr
), implied
, recurse_cnt
);
88 static struct range_list
*handle_ampersand_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
90 struct range_list
*rl
;
93 if (implied
== RL_EXACT
|| implied
== RL_HARD
)
95 if (get_mtag_sval(expr
, &sval
))
96 return alloc_rl(sval
, sval
);
97 if (get_address_rl(expr
, &rl
))
99 return alloc_rl(valid_ptr_min_sval
, valid_ptr_max_sval
);
102 static struct range_list
*handle_negate_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
104 if (known_condition_true(expr
->unop
))
106 if (known_condition_false(expr
->unop
))
109 if (implied
== RL_EXACT
)
112 if (implied_condition_true(expr
->unop
))
114 if (implied_condition_false(expr
->unop
))
116 return alloc_rl(zero
, one
);
119 static struct range_list
*handle_bitwise_negate(struct expression
*expr
, int implied
, int *recurse_cnt
)
121 struct range_list
*rl
;
124 rl
= _get_rl(expr
->unop
, implied
, recurse_cnt
);
125 if (!rl_to_sval(rl
, &sval
))
127 sval
= sval_preop(sval
, '~');
128 sval_cast(get_type(expr
->unop
), sval
);
129 return alloc_rl(sval
, sval
);
132 static struct range_list
*handle_minus_preop(struct expression
*expr
, int implied
, int *recurse_cnt
)
134 struct range_list
*rl
;
137 rl
= _get_rl(expr
->unop
, implied
, recurse_cnt
);
138 min
= sval_preop(rl_max(rl
), '-');
139 max
= sval_preop(rl_min(rl
), '-');
140 return alloc_rl(min
, max
);
143 static struct range_list
*handle_preop_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
147 return handle_ampersand_rl(expr
, implied
, recurse_cnt
);
149 return handle_negate_rl(expr
, implied
, recurse_cnt
);
151 return handle_bitwise_negate(expr
, implied
, recurse_cnt
);
153 return handle_minus_preop(expr
, implied
, recurse_cnt
);
155 return handle_variable(expr
, implied
, recurse_cnt
);
157 return handle_expression_statement_rl(expr
, implied
, recurse_cnt
);
163 static struct range_list
*handle_divide_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
165 struct range_list
*left_rl
, *right_rl
;
168 type
= get_type(expr
);
170 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
171 left_rl
= cast_rl(type
, left_rl
);
172 right_rl
= _get_rl(expr
->right
, implied
, recurse_cnt
);
173 right_rl
= cast_rl(type
, right_rl
);
175 if (!left_rl
|| !right_rl
)
178 if (implied
!= RL_REAL_ABSOLUTE
) {
179 if (is_whole_rl(left_rl
) || is_whole_rl(right_rl
))
183 return rl_binop(left_rl
, '/', right_rl
);
186 static int handle_offset_subtraction(struct expression
*expr
)
188 struct expression
*left
, *right
;
189 struct symbol
*left_sym
, *right_sym
;
191 int left_offset
, right_offset
;
193 type
= get_type(expr
);
194 if (!type
|| type
->type
!= SYM_PTR
)
196 type
= get_real_base_type(type
);
197 if (!type
|| (type_bits(type
) != 8 && (type
!= &void_ctype
)))
200 left
= strip_expr(expr
->left
);
201 right
= strip_expr(expr
->right
);
203 if (left
->type
!= EXPR_PREOP
|| left
->op
!= '&')
205 left
= strip_expr(left
->unop
);
207 left_sym
= expr_to_sym(left
);
208 right_sym
= expr_to_sym(right
);
209 if (!left_sym
|| left_sym
!= right_sym
)
212 left_offset
= get_member_offset_from_deref(left
);
213 if (right
->type
== EXPR_SYMBOL
)
216 if (right
->type
!= EXPR_PREOP
|| right
->op
!= '&')
218 right
= strip_expr(right
->unop
);
219 right_offset
= get_member_offset_from_deref(right
);
221 if (left_offset
< 0 || right_offset
< 0)
224 return left_offset
- right_offset
;
227 static struct range_list
*handle_subtract_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
230 struct range_list
*left_orig
, *right_orig
;
231 struct range_list
*left_rl
, *right_rl
;
232 sval_t max
, min
, tmp
;
236 type
= get_type(expr
);
238 offset
= handle_offset_subtraction(expr
);
243 return alloc_rl(tmp
, tmp
);
246 comparison
= get_comparison(expr
->left
, expr
->right
);
248 left_orig
= _get_rl(expr
->left
, implied
, recurse_cnt
);
249 left_rl
= cast_rl(type
, left_orig
);
250 right_orig
= _get_rl(expr
->right
, implied
, recurse_cnt
);
251 right_rl
= cast_rl(type
, right_orig
);
253 if ((!left_rl
|| !right_rl
) &&
254 (implied
== RL_EXACT
|| implied
== RL_HARD
|| implied
== RL_FUZZY
))
258 left_rl
= alloc_whole_rl(type
);
260 right_rl
= alloc_whole_rl(type
);
262 /* negative values complicate everything fix this later */
263 if (sval_is_negative(rl_min(right_rl
)))
265 max
= rl_max(left_rl
);
266 min
= sval_type_min(type
);
268 switch (comparison
) {
270 case SPECIAL_UNSIGNED_GT
:
271 min
= sval_type_val(type
, 1);
272 max
= rl_max(left_rl
);
275 case SPECIAL_UNSIGNED_GTE
:
276 min
= sval_type_val(type
, 0);
277 max
= rl_max(left_rl
);
280 min
= sval_type_val(type
, 0);
281 max
= sval_type_val(type
, 0);
284 case SPECIAL_UNSIGNED_LT
:
285 max
= sval_type_val(type
, -1);
288 case SPECIAL_UNSIGNED_LTE
:
289 max
= sval_type_val(type
, 0);
292 if (!left_orig
|| !right_orig
)
294 return rl_binop(left_rl
, '-', right_rl
);
297 if (!sval_binop_overflows(rl_min(left_rl
), '-', rl_max(right_rl
))) {
298 tmp
= sval_binop(rl_min(left_rl
), '-', rl_max(right_rl
));
299 if (sval_cmp(tmp
, min
) > 0)
303 if (!sval_is_max(rl_max(left_rl
))) {
304 tmp
= sval_binop(rl_max(left_rl
), '-', rl_min(right_rl
));
305 if (sval_cmp(tmp
, max
) < 0)
309 if (sval_is_min(min
) && sval_is_max(max
))
312 return cast_rl(type
, alloc_rl(min
, max
));
315 static struct range_list
*handle_mod_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
317 struct range_list
*rl
;
318 sval_t left
, right
, sval
;
320 if (implied
== RL_EXACT
) {
321 if (!get_implied_value(expr
->right
, &right
))
323 if (!get_implied_value(expr
->left
, &left
))
325 sval
= sval_binop(left
, '%', right
);
326 return alloc_rl(sval
, sval
);
328 /* if we can't figure out the right side it's probably hopeless */
329 if (!get_implied_value_internal(expr
->right
, &right
, recurse_cnt
))
332 right
= sval_cast(get_type(expr
), right
);
335 rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
336 if (rl
&& rl_max(rl
).uvalue
< right
.uvalue
)
337 right
.uvalue
= rl_max(rl
).uvalue
;
339 return alloc_rl(sval_cast(right
.type
, zero
), right
);
342 static sval_t
sval_lowest_set_bit(sval_t sval
)
347 for (i
= 0; i
< 64; i
++) {
348 if (sval
.uvalue
& 1ULL << i
) {
351 sval
.uvalue
&= ~(1ULL << i
);
357 static struct range_list
*handle_bitwise_AND(struct expression
*expr
, int implied
, int *recurse_cnt
)
360 struct range_list
*left_rl
, *right_rl
;
364 if (implied
!= RL_IMPLIED
&& implied
!= RL_ABSOLUTE
&& implied
!= RL_REAL_ABSOLUTE
)
367 type
= get_type(expr
);
369 if (get_implied_value_internal(expr
->left
, &known
, recurse_cnt
)) {
372 min
= sval_lowest_set_bit(known
);
373 left_rl
= alloc_rl(min
, known
);
374 left_rl
= cast_rl(type
, left_rl
);
375 add_range(&left_rl
, sval_type_val(type
, 0), sval_type_val(type
, 0));
377 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
379 left_rl
= cast_rl(type
, left_rl
);
380 left_rl
= alloc_rl(sval_type_val(type
, 0), rl_max(left_rl
));
382 if (implied
== RL_HARD
)
384 left_rl
= alloc_whole_rl(type
);
388 new_recurse
= *recurse_cnt
;
389 if (*recurse_cnt
>= 200)
390 new_recurse
= 100; /* Let's try super hard to get the mask */
391 if (get_implied_value_internal(expr
->right
, &known
, &new_recurse
)) {
392 sval_t min
, left_max
, mod
;
394 *recurse_cnt
= new_recurse
;
396 min
= sval_lowest_set_bit(known
);
397 right_rl
= alloc_rl(min
, known
);
398 right_rl
= cast_rl(type
, right_rl
);
399 add_range(&right_rl
, sval_type_val(type
, 0), sval_type_val(type
, 0));
401 if (min
.value
!= 0) {
402 left_max
= rl_max(left_rl
);
403 mod
= sval_binop(left_max
, '%', min
);
405 left_max
= sval_binop(left_max
, '-', mod
);
407 if (left_max
.value
> 0 && sval_cmp(left_max
, rl_max(left_rl
)) < 0)
408 left_rl
= remove_range(left_rl
, left_max
, rl_max(left_rl
));
412 right_rl
= _get_rl(expr
->right
, implied
, recurse_cnt
);
414 right_rl
= cast_rl(type
, right_rl
);
415 right_rl
= alloc_rl(sval_type_val(type
, 0), rl_max(right_rl
));
417 if (implied
== RL_HARD
)
419 right_rl
= alloc_whole_rl(type
);
423 return rl_intersection(left_rl
, right_rl
);
426 static struct range_list
*use_rl_binop(struct expression
*expr
, int implied
, int *recurse_cnt
)
429 struct range_list
*left_rl
, *right_rl
;
431 if (implied
!= RL_IMPLIED
&& implied
!= RL_ABSOLUTE
&& implied
!= RL_REAL_ABSOLUTE
)
434 type
= get_type(expr
);
436 get_absolute_rl_internal(expr
->left
, &left_rl
, recurse_cnt
);
437 get_absolute_rl_internal(expr
->right
, &right_rl
, recurse_cnt
);
438 left_rl
= cast_rl(type
, left_rl
);
439 right_rl
= cast_rl(type
, right_rl
);
440 if (!left_rl
|| !right_rl
)
443 return rl_binop(left_rl
, expr
->op
, right_rl
);
446 static struct range_list
*handle_right_shift(struct expression
*expr
, int implied
, int *recurse_cnt
)
448 struct range_list
*left_rl
;
452 if (implied
== RL_EXACT
|| implied
== RL_HARD
)
455 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
457 max
= rl_max(left_rl
);
458 min
= rl_min(left_rl
);
460 if (implied
== RL_FUZZY
)
462 max
= sval_type_max(get_type(expr
->left
));
463 min
= sval_type_val(get_type(expr
->left
), 0);
466 if (get_implied_value_internal(expr
->right
, &right
, recurse_cnt
)) {
467 min
= sval_binop(min
, SPECIAL_RIGHTSHIFT
, right
);
468 max
= sval_binop(max
, SPECIAL_RIGHTSHIFT
, right
);
469 } else if (!sval_is_negative(min
)) {
471 max
= sval_type_max(max
.type
);
476 return alloc_rl(min
, max
);
479 static struct range_list
*handle_left_shift(struct expression
*expr
, int implied
, int *recurse_cnt
)
481 struct range_list
*left_rl
, *res
;
486 if (implied
== RL_EXACT
|| implied
== RL_HARD
)
488 /* this is hopeless without the right side */
489 if (!get_implied_value_internal(expr
->right
, &right
, recurse_cnt
))
491 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
493 max
= rl_max(left_rl
);
494 min
= rl_min(left_rl
);
495 if (min
.value
== 0) {
500 if (implied
== RL_FUZZY
)
502 max
= sval_type_max(get_type(expr
->left
));
503 min
= sval_type_val(get_type(expr
->left
), 1);
507 max
= sval_binop(max
, SPECIAL_LEFTSHIFT
, right
);
508 min
= sval_binop(min
, SPECIAL_LEFTSHIFT
, right
);
509 res
= alloc_rl(min
, max
);
511 res
= rl_union(res
, rl_zero());
515 static struct range_list
*handle_known_binop(struct expression
*expr
)
519 if (!get_value(expr
->left
, &left
))
521 if (!get_value(expr
->right
, &right
))
523 left
= sval_binop(left
, expr
->op
, right
);
524 return alloc_rl(left
, left
);
527 static int has_actual_ranges(struct range_list
*rl
)
529 struct data_range
*tmp
;
531 FOR_EACH_PTR(rl
, tmp
) {
532 if (sval_cmp(tmp
->min
, tmp
->max
) != 0)
534 } END_FOR_EACH_PTR(tmp
);
538 static struct range_list
*handle_implied_binop(struct range_list
*left_rl
, int op
, struct range_list
*right_rl
)
540 struct range_list
*res_rl
;
541 struct data_range
*left_drange
, *right_drange
;
544 if (!left_rl
|| !right_rl
)
546 if (has_actual_ranges(left_rl
))
548 if (has_actual_ranges(right_rl
))
551 if (ptr_list_size((struct ptr_list
*)left_rl
) * ptr_list_size((struct ptr_list
*)right_rl
) > 20)
556 FOR_EACH_PTR(left_rl
, left_drange
) {
557 FOR_EACH_PTR(right_rl
, right_drange
) {
558 if ((op
== '%' || op
== '/') &&
559 right_drange
->min
.value
== 0)
561 res
= sval_binop(left_drange
->min
, op
, right_drange
->min
);
562 add_range(&res_rl
, res
, res
);
563 } END_FOR_EACH_PTR(right_drange
);
564 } END_FOR_EACH_PTR(left_drange
);
569 static struct range_list
*handle_binop_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
571 struct smatch_state
*state
;
573 struct range_list
*left_rl
, *right_rl
, *rl
;
576 rl
= handle_known_binop(expr
);
579 if (implied
== RL_EXACT
)
582 if (custom_handle_variable
) {
583 rl
= custom_handle_variable(expr
);
588 state
= get_extra_state(expr
);
589 if (state
&& !is_whole_rl(estate_rl(state
))) {
590 if (implied
!= RL_HARD
|| estate_has_hard_max(state
))
591 return clone_rl(estate_rl(state
));
594 type
= get_type(expr
);
595 left_rl
= _get_rl(expr
->left
, implied
, recurse_cnt
);
596 left_rl
= cast_rl(type
, left_rl
);
597 right_rl
= _get_rl(expr
->right
, implied
, recurse_cnt
);
598 right_rl
= cast_rl(type
, right_rl
);
600 if (!left_rl
&& !right_rl
)
603 rl
= handle_implied_binop(left_rl
, expr
->op
, right_rl
);
609 return handle_mod_rl(expr
, implied
, recurse_cnt
);
611 return handle_bitwise_AND(expr
, implied
, recurse_cnt
);
614 return use_rl_binop(expr
, implied
, recurse_cnt
);
615 case SPECIAL_RIGHTSHIFT
:
616 return handle_right_shift(expr
, implied
, recurse_cnt
);
617 case SPECIAL_LEFTSHIFT
:
618 return handle_left_shift(expr
, implied
, recurse_cnt
);
620 return handle_subtract_rl(expr
, implied
, recurse_cnt
);
622 return handle_divide_rl(expr
, implied
, recurse_cnt
);
625 if (!left_rl
|| !right_rl
)
628 if (sval_binop_overflows(rl_min(left_rl
), expr
->op
, rl_min(right_rl
)))
630 if (sval_binop_overflows(rl_max(left_rl
), expr
->op
, rl_max(right_rl
)))
633 min
= sval_binop(rl_min(left_rl
), expr
->op
, rl_min(right_rl
));
634 max
= sval_binop(rl_max(left_rl
), expr
->op
, rl_max(right_rl
));
636 return alloc_rl(min
, max
);
639 static int do_comparison(struct expression
*expr
)
641 struct range_list
*left_ranges
= NULL
;
642 struct range_list
*right_ranges
= NULL
;
643 int poss_true
, poss_false
;
646 type
= get_type(expr
);
647 get_absolute_rl(expr
->left
, &left_ranges
);
648 get_absolute_rl(expr
->right
, &right_ranges
);
650 left_ranges
= cast_rl(type
, left_ranges
);
651 right_ranges
= cast_rl(type
, right_ranges
);
653 poss_true
= possibly_true_rl(left_ranges
, expr
->op
, right_ranges
);
654 poss_false
= possibly_false_rl(left_ranges
, expr
->op
, right_ranges
);
656 if (!poss_true
&& !poss_false
)
658 if (poss_true
&& !poss_false
)
660 if (!poss_true
&& poss_false
)
665 static struct range_list
*handle_comparison_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
670 if (expr
->op
== SPECIAL_EQUAL
&& expr
->left
->type
== EXPR_TYPE
) {
671 struct symbol
*left
, *right
;
673 left
= get_real_base_type(expr
->left
->symbol
);
674 right
= get_real_base_type(expr
->left
->symbol
);
680 if (get_value(expr
->left
, &left
) && get_value(expr
->right
, &right
)) {
681 struct data_range tmp_left
, tmp_right
;
685 tmp_right
.min
= right
;
686 tmp_right
.max
= right
;
687 if (true_comparison_range(&tmp_left
, expr
->op
, &tmp_right
))
692 if (implied
== RL_EXACT
)
695 res
= do_comparison(expr
);
701 return alloc_rl(zero
, one
);
704 static struct range_list
*handle_logical_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
710 if (implied
== RL_EXACT
) {
711 if (get_value(expr
->left
, &left
))
713 if (get_value(expr
->right
, &right
))
716 if (get_implied_value_internal(expr
->left
, &left
, recurse_cnt
))
718 if (get_implied_value_internal(expr
->right
, &right
, recurse_cnt
))
723 case SPECIAL_LOGICAL_OR
:
724 if (left_known
&& left
.value
)
726 if (right_known
&& right
.value
)
728 if (left_known
&& right_known
)
731 case SPECIAL_LOGICAL_AND
:
732 if (left_known
&& right_known
) {
733 if (left
.value
&& right
.value
)
742 if (implied
== RL_EXACT
)
745 return alloc_rl(zero
, one
);
748 static struct range_list
*handle_conditional_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
750 struct range_list
*true_rl
, *false_rl
;
752 int final_pass_orig
= final_pass
;
754 if (known_condition_true(expr
->conditional
))
755 return _get_rl(expr
->cond_true
, implied
, recurse_cnt
);
756 if (known_condition_false(expr
->conditional
))
757 return _get_rl(expr
->cond_false
, implied
, recurse_cnt
);
759 if (implied
== RL_EXACT
)
762 if (implied_condition_true(expr
->conditional
))
763 return _get_rl(expr
->cond_true
, implied
, recurse_cnt
);
764 if (implied_condition_false(expr
->conditional
))
765 return _get_rl(expr
->cond_false
, implied
, recurse_cnt
);
768 /* this becomes a problem with deeply nested conditional statements */
772 type
= get_type(expr
);
774 __push_fake_cur_stree();
776 __split_whole_condition(expr
->conditional
);
777 true_rl
= _get_rl(expr
->cond_true
, implied
, recurse_cnt
);
778 __push_true_states();
779 __use_false_states();
780 false_rl
= _get_rl(expr
->cond_false
, implied
, recurse_cnt
);
781 __merge_true_states();
782 __free_fake_cur_stree();
783 final_pass
= final_pass_orig
;
785 if (!true_rl
|| !false_rl
)
787 true_rl
= cast_rl(type
, true_rl
);
788 false_rl
= cast_rl(type
, false_rl
);
790 return rl_union(true_rl
, false_rl
);
793 static int get_fuzzy_max_helper(struct expression
*expr
, sval_t
*max
)
795 struct smatch_state
*state
;
798 if (get_hard_max(expr
, &sval
)) {
803 state
= get_extra_state(expr
);
804 if (!state
|| !estate_has_fuzzy_max(state
))
806 *max
= sval_cast(get_type(expr
), estate_get_fuzzy_max(state
));
810 static int get_fuzzy_min_helper(struct expression
*expr
, sval_t
*min
)
812 struct smatch_state
*state
;
815 state
= get_extra_state(expr
);
816 if (!state
|| !estate_rl(state
))
819 sval
= estate_min(state
);
820 if (sval_is_negative(sval
) && sval_is_min(sval
))
823 if (sval_is_max(sval
))
826 *min
= sval_cast(get_type(expr
), sval
);
830 int get_const_value(struct expression
*expr
, sval_t
*sval
)
835 if (expr
->type
!= EXPR_SYMBOL
|| !expr
->symbol
)
838 if (!(sym
->ctype
.modifiers
& MOD_CONST
))
840 if (get_value(sym
->initializer
, &right
)) {
841 *sval
= sval_cast(get_type(expr
), right
);
847 struct range_list
*var_to_absolute_rl(struct expression
*expr
)
849 struct smatch_state
*state
;
850 struct range_list
*rl
;
852 state
= get_extra_state(expr
);
853 if (!state
|| is_whole_rl(estate_rl(state
))) {
854 state
= get_real_absolute_state(expr
);
855 if (state
&& state
->data
&& !estate_is_whole(state
))
856 return clone_rl(estate_rl(state
));
857 if (get_local_rl(expr
, &rl
) && !is_whole_rl(rl
))
859 if (get_mtag_rl(expr
, &rl
))
861 if (get_db_type_rl(expr
, &rl
) && !is_whole_rl(rl
))
863 return alloc_whole_rl(get_type(expr
));
865 /* err on the side of saying things are possible */
866 if (!estate_rl(state
))
867 return alloc_whole_rl(get_type(expr
));
868 return clone_rl(estate_rl(state
));
871 static struct range_list
*handle_variable(struct expression
*expr
, int implied
, int *recurse_cnt
)
873 struct smatch_state
*state
;
874 struct range_list
*rl
;
875 sval_t sval
, min
, max
;
878 if (get_const_value(expr
, &sval
))
879 return alloc_rl(sval
, sval
);
881 if (custom_handle_variable
) {
882 rl
= custom_handle_variable(expr
);
884 return var_to_absolute_rl(expr
);
888 if (implied
== RL_EXACT
)
891 if (get_mtag_sval(expr
, &sval
))
892 return alloc_rl(sval
, sval
);
894 type
= get_type(expr
);
895 if (type
&& type
->type
== SYM_FN
)
896 return alloc_rl(fn_ptr_min
, fn_ptr_max
);
902 state
= get_extra_state(expr
);
903 if (!state
|| !state
->data
) {
904 if (implied
== RL_HARD
)
906 if (get_local_rl(expr
, &rl
))
908 if (get_mtag_rl(expr
, &rl
))
910 if (get_db_type_rl(expr
, &rl
))
912 if (is_array(expr
) && get_array_rl(expr
, &rl
))
916 if (implied
== RL_HARD
&& !estate_has_hard_max(state
))
918 return clone_rl(estate_rl(state
));
919 case RL_REAL_ABSOLUTE
: {
920 struct smatch_state
*abs_state
;
922 state
= get_extra_state(expr
);
923 abs_state
= get_real_absolute_state(expr
);
925 if (estate_rl(state
) && estate_rl(abs_state
)) {
926 return clone_rl(rl_intersection(estate_rl(state
),
927 estate_rl(abs_state
)));
928 } else if (estate_rl(state
)) {
929 return clone_rl(estate_rl(state
));
930 } else if (estate_is_empty(state
)) {
932 * FIXME: we don't handle empty extra states correctly.
934 * The real abs rl is supposed to be filtered by the
935 * extra state if there is one. We don't bother keeping
936 * the abs state in sync all the time because we know it
937 * will be filtered later.
939 * It's not totally obvious to me how they should be
940 * handled. Perhaps we should take the whole rl and
941 * filter by the imaginary states. Perhaps we should
942 * just go with the empty state.
944 * Anyway what we currently do is return NULL here and
945 * that gets translated into the whole range in
946 * get_real_absolute_rl().
950 } else if (estate_rl(abs_state
)) {
951 return clone_rl(estate_rl(abs_state
));
954 if (get_local_rl(expr
, &rl
))
956 if (get_mtag_rl(expr
, &rl
))
958 if (get_db_type_rl(expr
, &rl
))
960 if (is_array(expr
) && get_array_rl(expr
, &rl
))
965 if (!get_fuzzy_min_helper(expr
, &min
))
966 min
= sval_type_min(get_type(expr
));
967 if (!get_fuzzy_max_helper(expr
, &max
))
969 /* fuzzy ranges are often inverted */
970 if (sval_cmp(min
, max
) > 0) {
975 return alloc_rl(min
, max
);
980 static sval_t
handle_sizeof(struct expression
*expr
)
985 ret
= sval_blank(expr
);
986 sym
= expr
->cast_type
;
988 sym
= evaluate_expression(expr
->cast_expression
);
990 __silence_warnings_for_stmt
= true;
995 * Expressions of restricted types will possibly get
996 * promoted - check that here. I'm not sure how this works,
997 * the problem is that sizeof(le16) shouldn't be promoted and
998 * the original code did that... Let's if zero this out and
1002 if (is_restricted_type(sym
)) {
1003 if (type_bits(sym
) < bits_in_int
)
1007 if (is_fouled_type(sym
))
1010 examine_symbol_type(sym
);
1012 ret
.type
= size_t_ctype
;
1013 if (type_bits(sym
) <= 0) /* sizeof(void) */ {
1014 if (get_real_base_type(sym
) == &void_ctype
)
1019 ret
.value
= type_bytes(sym
);
1024 static struct range_list
*handle_strlen(struct expression
*expr
, int implied
, int *recurse_cnt
)
1026 struct range_list
*rl
;
1027 struct expression
*arg
, *tmp
;
1029 sval_t ret
= { .type
= &ulong_ctype
};
1031 if (implied
== RL_EXACT
)
1034 arg
= get_argument_from_call_expr(expr
->args
, 0);
1037 if (arg
->type
== EXPR_STRING
) {
1038 ret
.value
= arg
->string
->length
- 1;
1039 return alloc_rl(ret
, ret
);
1041 if (get_implied_value(arg
, &tag
) &&
1042 (tmp
= fake_string_from_mtag(tag
.uvalue
))) {
1043 ret
.value
= tmp
->string
->length
- 1;
1044 return alloc_rl(ret
, ret
);
1047 if (implied
== RL_HARD
|| implied
== RL_FUZZY
)
1050 if (get_implied_return(expr
, &rl
))
1056 static struct range_list
*handle_builtin_constant_p(struct expression
*expr
, int implied
, int *recurse_cnt
)
1058 struct expression
*arg
;
1059 struct range_list
*rl
;
1062 arg
= get_argument_from_call_expr(expr
->args
, 0);
1063 rl
= _get_rl(arg
, RL_EXACT
, recurse_cnt
);
1064 if (rl_to_sval(rl
, &sval
))
1069 static struct range_list
*handle__builtin_choose_expr(struct expression
*expr
, int implied
, int *recurse_cnt
)
1071 struct expression
*const_expr
, *expr1
, *expr2
;
1074 const_expr
= get_argument_from_call_expr(expr
->args
, 0);
1075 expr1
= get_argument_from_call_expr(expr
->args
, 1);
1076 expr2
= get_argument_from_call_expr(expr
->args
, 2);
1078 if (!get_value(const_expr
, &sval
) || !expr1
|| !expr2
)
1081 return _get_rl(expr1
, implied
, recurse_cnt
);
1082 return _get_rl(expr2
, implied
, recurse_cnt
);
1085 static struct range_list
*handle_call_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
1087 struct range_list
*rl
;
1089 if (sym_name_is("__builtin_constant_p", expr
->fn
))
1090 return handle_builtin_constant_p(expr
, implied
, recurse_cnt
);
1092 if (sym_name_is("__builtin_choose_expr", expr
->fn
))
1093 return handle__builtin_choose_expr(expr
, implied
, recurse_cnt
);
1095 if (sym_name_is("__builtin_expect", expr
->fn
) ||
1096 sym_name_is("__builtin_bswap16", expr
->fn
) ||
1097 sym_name_is("__builtin_bswap32", expr
->fn
) ||
1098 sym_name_is("__builtin_bswap64", expr
->fn
)) {
1099 struct expression
*arg
;
1101 arg
= get_argument_from_call_expr(expr
->args
, 0);
1102 return _get_rl(arg
, implied
, recurse_cnt
);
1105 if (sym_name_is("strlen", expr
->fn
))
1106 return handle_strlen(expr
, implied
, recurse_cnt
);
1108 if (implied
== RL_EXACT
|| implied
== RL_HARD
|| implied
== RL_FUZZY
)
1111 if (custom_handle_variable
) {
1112 rl
= custom_handle_variable(expr
);
1117 if (get_implied_return(expr
, &rl
))
1119 return db_return_vals(expr
);
1122 static struct range_list
*handle_cast(struct expression
*expr
, int implied
, int *recurse_cnt
)
1124 struct range_list
*rl
;
1125 struct symbol
*type
;
1127 type
= get_type(expr
);
1128 rl
= _get_rl(expr
->cast_expression
, implied
, recurse_cnt
);
1130 return cast_rl(type
, rl
);
1131 if (implied
== RL_ABSOLUTE
|| implied
== RL_REAL_ABSOLUTE
)
1132 return alloc_whole_rl(type
);
1133 if (implied
== RL_IMPLIED
&& type
&&
1134 type_bits(type
) > 0 && type_bits(type
) < 32)
1135 return alloc_whole_rl(type
);
1139 static struct range_list
*_get_rl(struct expression
*expr
, int implied
, int *recurse_cnt
)
1141 struct range_list
*rl
;
1142 struct symbol
*type
;
1145 type
= get_type(expr
);
1146 expr
= strip_parens(expr
);
1150 if (++(*recurse_cnt
) >= 200)
1153 switch(expr
->type
) {
1155 case EXPR_FORCE_CAST
:
1156 case EXPR_IMPLIED_CAST
:
1157 rl
= handle_cast(expr
, implied
, recurse_cnt
);
1161 expr
= strip_expr(expr
);
1165 switch (expr
->type
) {
1167 sval
= sval_from_val(expr
, expr
->value
);
1168 rl
= alloc_rl(sval
, sval
);
1171 rl
= handle_preop_rl(expr
, implied
, recurse_cnt
);
1174 rl
= _get_rl(expr
->unop
, implied
, recurse_cnt
);
1177 rl
= handle_binop_rl(expr
, implied
, recurse_cnt
);
1180 rl
= handle_comparison_rl(expr
, implied
, recurse_cnt
);
1183 rl
= handle_logical_rl(expr
, implied
, recurse_cnt
);
1185 case EXPR_PTRSIZEOF
:
1187 sval
= handle_sizeof(expr
);
1188 rl
= alloc_rl(sval
, sval
);
1191 case EXPR_CONDITIONAL
:
1192 rl
= handle_conditional_rl(expr
, implied
, recurse_cnt
);
1195 rl
= handle_call_rl(expr
, implied
, recurse_cnt
);
1199 if (get_mtag_sval(expr
, &sval
))
1200 rl
= alloc_rl(sval
, sval
);
1203 rl
= handle_variable(expr
, implied
, recurse_cnt
);
1209 if (type
&& (implied
== RL_ABSOLUTE
|| implied
== RL_REAL_ABSOLUTE
))
1210 return alloc_whole_rl(type
);
1215 struct expression
*expr
;
1216 struct range_list
*rl
;
1217 } cached_results
[24];
1218 static int cache_idx
;
1220 void clear_math_cache(void)
1222 memset(cached_results
, 0, sizeof(cached_results
));
1225 /* returns 1 if it can get a value literal or else returns 0 */
1226 int get_value(struct expression
*expr
, sval_t
*sval
)
1228 struct range_list
*(*orig_custom_fn
)(struct expression
*expr
);
1229 struct range_list
*rl
;
1230 int recurse_cnt
= 0;
1235 * This only handles RL_EXACT because other expr statements can be
1236 * different at different points. Like the list iterator, for example.
1238 for (i
= 0; i
< ARRAY_SIZE(cached_results
); i
++) {
1239 if (expr
== cached_results
[i
].expr
)
1240 return rl_to_sval(cached_results
[i
].rl
, sval
);
1243 orig_custom_fn
= custom_handle_variable
;
1244 custom_handle_variable
= NULL
;
1245 rl
= _get_rl(expr
, RL_EXACT
, &recurse_cnt
);
1246 if (!rl_to_sval(rl
, &tmp
))
1248 custom_handle_variable
= orig_custom_fn
;
1250 cached_results
[cache_idx
].expr
= expr
;
1251 cached_results
[cache_idx
].rl
= rl
;
1252 cache_idx
= (cache_idx
+ 1) % ARRAY_SIZE(cached_results
);
1261 static int get_implied_value_internal(struct expression
*expr
, sval_t
*sval
, int *recurse_cnt
)
1263 struct range_list
*rl
;
1265 rl
= _get_rl(expr
, RL_IMPLIED
, recurse_cnt
);
1266 if (!rl_to_sval(rl
, sval
))
1271 int get_implied_value(struct expression
*expr
, sval_t
*sval
)
1273 struct range_list
*rl
;
1274 int recurse_cnt
= 0;
1276 rl
= _get_rl(expr
, RL_IMPLIED
, &recurse_cnt
);
1277 if (!rl_to_sval(rl
, sval
))
1282 int get_implied_min(struct expression
*expr
, sval_t
*sval
)
1284 struct range_list
*rl
;
1285 int recurse_cnt
= 0;
1287 rl
= _get_rl(expr
, RL_IMPLIED
, &recurse_cnt
);
1294 int get_implied_max(struct expression
*expr
, sval_t
*sval
)
1296 struct range_list
*rl
;
1297 int recurse_cnt
= 0;
1299 rl
= _get_rl(expr
, RL_IMPLIED
, &recurse_cnt
);
1306 int get_implied_rl(struct expression
*expr
, struct range_list
**rl
)
1308 int recurse_cnt
= 0;
1310 *rl
= _get_rl(expr
, RL_IMPLIED
, &recurse_cnt
);
1316 static int get_absolute_rl_internal(struct expression
*expr
, struct range_list
**rl
, int *recurse_cnt
)
1318 *rl
= _get_rl(expr
, RL_ABSOLUTE
, recurse_cnt
);
1320 *rl
= alloc_whole_rl(get_type(expr
));
1324 int get_absolute_rl(struct expression
*expr
, struct range_list
**rl
)
1326 int recurse_cnt
= 0;
1328 *rl
= _get_rl(expr
, RL_ABSOLUTE
, &recurse_cnt
);
1330 *rl
= alloc_whole_rl(get_type(expr
));
1334 int get_real_absolute_rl(struct expression
*expr
, struct range_list
**rl
)
1336 int recurse_cnt
= 0;
1338 *rl
= _get_rl(expr
, RL_REAL_ABSOLUTE
, &recurse_cnt
);
1340 *rl
= alloc_whole_rl(get_type(expr
));
1344 int custom_get_absolute_rl(struct expression
*expr
,
1345 struct range_list
*(*fn
)(struct expression
*expr
),
1346 struct range_list
**rl
)
1348 int recurse_cnt
= 0;
1351 custom_handle_variable
= fn
;
1352 *rl
= _get_rl(expr
, RL_REAL_ABSOLUTE
, &recurse_cnt
);
1353 custom_handle_variable
= NULL
;
1357 int get_implied_rl_var_sym(const char *var
, struct symbol
*sym
, struct range_list
**rl
)
1359 struct smatch_state
*state
;
1361 state
= get_state(SMATCH_EXTRA
, var
, sym
);
1362 *rl
= estate_rl(state
);
1368 int get_hard_max(struct expression
*expr
, sval_t
*sval
)
1370 struct range_list
*rl
;
1371 int recurse_cnt
= 0;
1373 rl
= _get_rl(expr
, RL_HARD
, &recurse_cnt
);
1380 int get_fuzzy_min(struct expression
*expr
, sval_t
*sval
)
1382 struct range_list
*rl
;
1384 int recurse_cnt
= 0;
1386 rl
= _get_rl(expr
, RL_FUZZY
, &recurse_cnt
);
1390 if (sval_is_negative(tmp
) && sval_is_min(tmp
))
1396 int get_fuzzy_max(struct expression
*expr
, sval_t
*sval
)
1398 struct range_list
*rl
;
1400 int recurse_cnt
= 0;
1402 rl
= _get_rl(expr
, RL_FUZZY
, &recurse_cnt
);
1406 if (max
.uvalue
> INT_MAX
- 10000)
1412 int get_absolute_min(struct expression
*expr
, sval_t
*sval
)
1414 struct range_list
*rl
;
1415 struct symbol
*type
;
1416 int recurse_cnt
= 0;
1418 type
= get_type(expr
);
1420 type
= &llong_ctype
; // FIXME: this is wrong but places assume get type can't fail.
1421 rl
= _get_rl(expr
, RL_REAL_ABSOLUTE
, &recurse_cnt
);
1425 *sval
= sval_type_min(type
);
1427 if (sval_cmp(*sval
, sval_type_min(type
)) < 0)
1428 *sval
= sval_type_min(type
);
1432 int get_absolute_max(struct expression
*expr
, sval_t
*sval
)
1434 struct range_list
*rl
;
1435 struct symbol
*type
;
1436 int recurse_cnt
= 0;
1438 type
= get_type(expr
);
1440 type
= &llong_ctype
;
1441 rl
= _get_rl(expr
, RL_REAL_ABSOLUTE
, &recurse_cnt
);
1445 *sval
= sval_type_max(type
);
1447 if (sval_cmp(sval_type_max(type
), *sval
) < 0)
1448 *sval
= sval_type_max(type
);
1452 int known_condition_true(struct expression
*expr
)
1459 if (get_value(expr
, &tmp
) && tmp
.value
)
1465 int known_condition_false(struct expression
*expr
)
1476 int implied_condition_true(struct expression
*expr
)
1483 if (known_condition_true(expr
))
1485 if (get_implied_value(expr
, &tmp
) && tmp
.value
)
1488 if (expr
->type
== EXPR_POSTOP
)
1489 return implied_condition_true(expr
->unop
);
1491 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_DECREMENT
)
1492 return implied_not_equal(expr
->unop
, 1);
1493 if (expr
->type
== EXPR_PREOP
&& expr
->op
== SPECIAL_INCREMENT
)
1494 return implied_not_equal(expr
->unop
, -1);
1496 expr
= strip_expr(expr
);
1497 switch (expr
->type
) {
1499 if (do_comparison(expr
) == 1)
1503 if (expr
->op
== '!') {
1504 if (implied_condition_false(expr
->unop
))
1510 if (implied_not_equal(expr
, 0) == 1)
1517 int implied_condition_false(struct expression
*expr
)
1519 struct expression
*tmp
;
1525 if (known_condition_false(expr
))
1528 switch (expr
->type
) {
1530 if (do_comparison(expr
) == 2)
1533 if (expr
->op
== '!') {
1534 if (implied_condition_true(expr
->unop
))
1538 tmp
= strip_expr(expr
);
1540 return implied_condition_false(tmp
);
1543 if (get_implied_value(expr
, &sval
) && sval
.value
== 0)
1550 int can_integer_overflow(struct symbol
*type
, struct expression
*expr
)
1553 sval_t lmax
, rmax
, res
;
1558 expr
= strip_expr(expr
);
1560 if (expr
->type
== EXPR_ASSIGNMENT
) {
1562 case SPECIAL_MUL_ASSIGN
:
1565 case SPECIAL_ADD_ASSIGN
:
1568 case SPECIAL_SHL_ASSIGN
:
1569 op
= SPECIAL_LEFTSHIFT
;
1574 } else if (expr
->type
== EXPR_BINOP
) {
1575 if (expr
->op
!= '*' && expr
->op
!= '+' && expr
->op
!= SPECIAL_LEFTSHIFT
)
1582 get_absolute_max(expr
->left
, &lmax
);
1583 get_absolute_max(expr
->right
, &rmax
);
1585 if (sval_binop_overflows(lmax
, op
, rmax
))
1588 res
= sval_binop(lmax
, op
, rmax
);
1589 if (sval_cmp(res
, sval_type_max(type
)) > 0)