2 * Copyright (C) 2009 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_extra.h"
21 #include "smatch_slist.h"
23 ALLOCATOR(data_info
, "smatch extra data");
24 ALLOCATOR(data_range
, "data range");
25 __DO_ALLOCATOR(struct data_range
, sizeof(struct data_range
), __alignof__(struct data_range
),
26 "permanent ranges", perm_data_range
);
28 char *show_rl(struct range_list
*list
)
30 struct data_range
*tmp
;
36 FOR_EACH_PTR(list
, tmp
) {
38 strncat(full
, ",", 254 - strlen(full
));
39 if (sval_cmp(tmp
->min
, tmp
->max
) == 0) {
40 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
43 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
44 strncat(full
, "-", 254 - strlen(full
));
45 strncat(full
, sval_to_str(tmp
->max
), 254 - strlen(full
));
46 } END_FOR_EACH_PTR(tmp
);
47 return alloc_sname(full
);
50 static int sval_too_big(struct symbol
*type
, sval_t sval
)
52 if (type_bits(type
) == 64)
54 if (sval
.uvalue
> ((1ULL << type_bits(type
)) - 1))
59 static void add_range_t(struct symbol
*type
, struct range_list
**rl
, sval_t min
, sval_t max
)
61 /* If we're just adding a number, cast it and add it */
62 if (sval_cmp(min
, max
) == 0) {
63 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
67 /* If the range is within the type range then add it */
68 if (sval_fits(type
, min
) && sval_fits(type
, max
)) {
69 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
74 * If the range we are adding has more bits than the range type then
75 * add the whole range type. Eg:
76 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
77 * This isn't totally the right thing to do. We could be more granular.
79 if (sval_too_big(type
, min
) || sval_too_big(type
, max
)) {
80 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
84 /* Cast negative values to high positive values */
85 if (sval_is_negative(min
) && type_unsigned(type
)) {
86 if (sval_is_positive(max
)) {
87 if (sval_too_high(type
, max
)) {
88 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
91 add_range(rl
, sval_type_val(type
, 0), sval_cast(type
, max
));
92 max
= sval_type_max(type
);
94 max
= sval_cast(type
, max
);
96 min
= sval_cast(type
, min
);
97 add_range(rl
, min
, max
);
100 /* Cast high positive numbers to negative */
101 if (sval_unsigned(max
) && sval_is_negative(sval_cast(type
, max
))) {
102 if (!sval_is_negative(sval_cast(type
, min
))) {
103 add_range(rl
, sval_cast(type
, min
), sval_type_max(type
));
104 min
= sval_type_min(type
);
106 min
= sval_cast(type
, min
);
108 max
= sval_cast(type
, max
);
109 add_range(rl
, min
, max
);
112 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
116 static int str_to_comparison_arg_helper(const char *str
,
117 struct expression
*call
, int *comparison
,
118 struct expression
**arg
, char **endp
)
121 char *c
= (char *)str
;
130 *comparison
= SPECIAL_LTE
;
135 } else if (*c
== '=') {
138 *comparison
= SPECIAL_EQUAL
;
139 } else if (*c
== '>') {
142 *comparison
= SPECIAL_GTE
;
147 } else if (*c
== '!') {
150 *comparison
= SPECIAL_NOTEQUAL
;
159 param
= strtoll(c
, &c
, 10);
160 c
++; /* skip the ']' character */
166 *arg
= get_argument_from_call_expr(call
->args
, param
);
172 int str_to_comparison_arg(const char *str
, struct expression
*call
, int *comparison
, struct expression
**arg
)
181 return str_to_comparison_arg_helper(str
, call
, comparison
, arg
, NULL
);
184 static int get_val_from_key(int use_max
, struct symbol
*type
, char *c
, struct expression
*call
, char **endp
, sval_t
*sval
)
186 struct expression
*arg
;
191 ret
= sval_type_max(type
);
193 ret
= sval_type_min(type
);
195 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
)) {
200 if (use_max
&& get_implied_max(arg
, &tmp
)) {
202 if (comparison
== '<') {
204 ret
= sval_binop(ret
, '-', tmp
);
207 if (!use_max
&& get_implied_min(arg
, &tmp
)) {
209 if (comparison
== '>') {
211 ret
= sval_binop(ret
, '+', tmp
);
219 static sval_t
add_one(sval_t sval
)
225 static sval_t
sub_one(sval_t sval
)
231 void filter_by_comparison(struct range_list
**rl
, int comparison
, struct range_list
*right
)
233 struct range_list
*left_orig
= *rl
;
234 struct range_list
*right_orig
= right
;
235 struct range_list
*ret_rl
= *rl
;
236 struct symbol
*cast_type
;
239 cast_type
= rl_type(left_orig
);
240 if (sval_type_max(rl_type(left_orig
)).uvalue
< sval_type_max(rl_type(right_orig
)).uvalue
)
241 cast_type
= rl_type(right_orig
);
242 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
243 cast_type
= &int_ctype
;
245 min
= sval_type_min(cast_type
);
246 max
= sval_type_max(cast_type
);
247 left_orig
= cast_rl(cast_type
, left_orig
);
248 right_orig
= cast_rl(cast_type
, right_orig
);
250 switch (comparison
) {
252 case SPECIAL_UNSIGNED_LT
:
253 ret_rl
= remove_range(left_orig
, rl_max(right_orig
), max
);
256 case SPECIAL_UNSIGNED_LTE
:
257 if (!sval_is_max(rl_max(right_orig
)))
258 ret_rl
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
261 if (!sval_is_max(rl_max(right_orig
)))
262 ret_rl
= remove_range(ret_rl
, add_one(rl_max(right_orig
)), max
);
263 if (!sval_is_min(rl_min(right_orig
)))
264 ret_rl
= remove_range(ret_rl
, min
, sub_one(rl_min(right_orig
)));
267 case SPECIAL_UNSIGNED_GTE
:
268 if (!sval_is_min(rl_min(right_orig
)))
269 ret_rl
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
272 case SPECIAL_UNSIGNED_GT
:
273 ret_rl
= remove_range(left_orig
, min
, rl_min(right_orig
));
275 case SPECIAL_NOTEQUAL
:
276 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
277 ret_rl
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
280 sm_msg("internal error: unhandled comparison %s", show_special(comparison
));
284 *rl
= cast_rl(rl_type(*rl
), ret_rl
);
287 static struct range_list
*filter_by_comparison_call(char *c
, struct expression
*call
, char **endp
, struct range_list
*start_rl
)
289 struct expression
*arg
;
290 struct range_list
*right_orig
;
293 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
))
296 if (!get_implied_rl(arg
, &right_orig
))
299 filter_by_comparison(&start_rl
, comparison
, right_orig
);
303 static sval_t
parse_val(int use_max
, struct expression
*call
, struct symbol
*type
, char *c
, char **endp
)
308 if (!strncmp(start
, "max", 3)) {
309 ret
= sval_type_max(type
);
311 } else if (!strncmp(start
, "u64max", 6)) {
312 ret
= sval_type_val(type
, ULLONG_MAX
);
314 } else if (!strncmp(start
, "s64max", 6)) {
315 ret
= sval_type_val(type
, LLONG_MAX
);
317 } else if (!strncmp(start
, "u32max", 6)) {
318 ret
= sval_type_val(type
, UINT_MAX
);
320 } else if (!strncmp(start
, "s32max", 6)) {
321 ret
= sval_type_val(type
, INT_MAX
);
323 } else if (!strncmp(start
, "u16max", 6)) {
324 ret
= sval_type_val(type
, USHRT_MAX
);
326 } else if (!strncmp(start
, "s16max", 6)) {
327 ret
= sval_type_val(type
, SHRT_MAX
);
329 } else if (!strncmp(start
, "min", 3)) {
330 ret
= sval_type_min(type
);
332 } else if (!strncmp(start
, "s64min", 6)) {
333 ret
= sval_type_val(type
, LLONG_MIN
);
335 } else if (!strncmp(start
, "s32min", 6)) {
336 ret
= sval_type_val(type
, INT_MIN
);
338 } else if (!strncmp(start
, "s16min", 6)) {
339 ret
= sval_type_val(type
, SHRT_MIN
);
341 } else if (!strncmp(start
, "long_min", 8)) {
342 ret
= sval_type_val(type
, LONG_MIN
);
344 } else if (!strncmp(start
, "long_max", 8)) {
345 ret
= sval_type_val(type
, LONG_MAX
);
347 } else if (!strncmp(start
, "ulong_max", 9)) {
348 ret
= sval_type_val(type
, ULONG_MAX
);
350 } else if (!strncmp(start
, "ptr_max", 7)) {
351 ret
= sval_type_val(type
, valid_ptr_max
);
353 } else if (start
[0] == '[') {
354 /* this parses [==p0] comparisons */
355 get_val_from_key(1, type
, start
, call
, &c
, &ret
);
357 ret
= sval_type_val(type
, strtoll(start
, &c
, 10));
363 static char *jump_to_call_math(char *value
)
367 while (*c
&& *c
!= '[')
373 if (*c
== '<' || *c
== '=' || *c
== '>' || *c
== '!')
379 static void str_to_rl_helper(struct expression
*call
, struct symbol
*type
, char *str
, char **endp
, struct range_list
**rl
)
381 struct range_list
*rl_tmp
= NULL
;
385 min
= sval_type_min(type
);
386 max
= sval_type_max(type
);
388 while (*c
!= '\0' && *c
!= '[') {
391 min
= parse_val(0, call
, type
, c
, &c
);
395 if (*c
== '\0' || *c
== '[') {
396 add_range_t(type
, &rl_tmp
, min
, min
);
400 add_range_t(type
, &rl_tmp
, min
, min
);
405 sm_msg("debug XXX: trouble parsing %s c = %s", str
, c
);
411 max
= parse_val(1, call
, type
, c
, &c
);
412 add_range_t(type
, &rl_tmp
, min
, max
);
423 static void str_to_dinfo(struct expression
*call
, struct symbol
*type
, char *value
, struct data_info
*dinfo
)
425 struct range_list
*math_rl
;
428 struct range_list
*rl
= NULL
;
433 if (strcmp(value
, "empty") == 0)
436 if (strncmp(value
, "[==$", 4) == 0) {
437 struct expression
*arg
;
440 if (!str_to_comparison_arg(value
, call
, &comparison
, &arg
))
442 if (!get_implied_rl(arg
, &rl
))
447 str_to_rl_helper(call
, type
, value
, &c
, &rl
);
451 call_math
= jump_to_call_math(value
);
452 if (call_math
&& parse_call_math_rl(call
, call_math
, &math_rl
)) {
453 rl
= rl_intersection(rl
, math_rl
);
458 * For now if we already tried to handle the call math and couldn't
459 * figure it out then bail.
461 if (jump_to_call_math(c
) == c
+ 1)
464 rl
= filter_by_comparison_call(c
, call
, &c
, rl
);
467 rl
= cast_rl(type
, rl
);
468 dinfo
->value_ranges
= rl
;
471 void str_to_rl(struct symbol
*type
, char *value
, struct range_list
**rl
)
473 struct data_info dinfo
= {};
475 str_to_dinfo(NULL
, type
, value
, &dinfo
);
476 *rl
= dinfo
.value_ranges
;
479 void call_results_to_rl(struct expression
*expr
, struct symbol
*type
, char *value
, struct range_list
**rl
)
481 struct data_info dinfo
= {};
483 str_to_dinfo(strip_expr(expr
), type
, value
, &dinfo
);
484 *rl
= dinfo
.value_ranges
;
487 int is_whole_rl(struct range_list
*rl
)
489 struct data_range
*drange
;
491 if (ptr_list_empty(rl
))
493 drange
= first_ptr_list((struct ptr_list
*)rl
);
494 if (sval_is_min(drange
->min
) && sval_is_max(drange
->max
))
499 int is_whole_rl_non_zero(struct range_list
*rl
)
501 struct data_range
*drange
;
503 if (ptr_list_empty(rl
))
505 drange
= first_ptr_list((struct ptr_list
*)rl
);
506 if (sval_unsigned(drange
->min
) &&
507 drange
->min
.value
== 1 &&
508 sval_is_max(drange
->max
))
510 if (!sval_is_min(drange
->min
) || drange
->max
.value
!= -1)
512 drange
= last_ptr_list((struct ptr_list
*)rl
);
513 if (drange
->min
.value
!= 1 || !sval_is_max(drange
->max
))
518 sval_t
rl_min(struct range_list
*rl
)
520 struct data_range
*drange
;
523 ret
.type
= &llong_ctype
;
524 ret
.value
= LLONG_MIN
;
525 if (ptr_list_empty(rl
))
527 drange
= first_ptr_list((struct ptr_list
*)rl
);
531 sval_t
rl_max(struct range_list
*rl
)
533 struct data_range
*drange
;
536 ret
.type
= &llong_ctype
;
537 ret
.value
= LLONG_MAX
;
538 if (ptr_list_empty(rl
))
540 drange
= last_ptr_list((struct ptr_list
*)rl
);
544 int rl_to_sval(struct range_list
*rl
, sval_t
*sval
)
553 if (sval_cmp(min
, max
) != 0)
559 struct symbol
*rl_type(struct range_list
*rl
)
563 return rl_min(rl
).type
;
566 static struct data_range
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
568 struct data_range
*ret
;
571 ret
= __alloc_perm_data_range(0);
573 ret
= __alloc_data_range(0);
579 struct data_range
*alloc_range(sval_t min
, sval_t max
)
581 return alloc_range_helper_sval(min
, max
, 0);
584 struct data_range
*alloc_range_perm(sval_t min
, sval_t max
)
586 return alloc_range_helper_sval(min
, max
, 1);
589 struct range_list
*alloc_rl(sval_t min
, sval_t max
)
591 struct range_list
*rl
= NULL
;
593 if (sval_cmp(min
, max
) > 0)
594 return alloc_whole_rl(min
.type
);
596 add_range(&rl
, min
, max
);
600 struct range_list
*alloc_whole_rl(struct symbol
*type
)
602 if (!type
|| type_positive_bits(type
) < 0)
604 if (type
->type
== SYM_ARRAY
)
607 return alloc_rl(sval_type_min(type
), sval_type_max(type
));
610 void add_range(struct range_list
**list
, sval_t min
, sval_t max
)
612 struct data_range
*tmp
= NULL
;
613 struct data_range
*new = NULL
;
616 if (sval_cmp(min
, max
) > 0) {
617 min
= sval_type_min(min
.type
);
618 max
= sval_type_max(min
.type
);
622 * FIXME: This has a problem merging a range_list like: min-0,3-max
623 * with a range like 1-2. You end up with min-2,3-max instead of
626 FOR_EACH_PTR(*list
, tmp
) {
628 /* Sometimes we overlap with more than one range
629 so we have to delete or modify the next range. */
630 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
631 /* join 2 ranges here */
633 DELETE_CURRENT_PTR(tmp
);
637 /* Doesn't overlap with the next one. */
638 if (sval_cmp(max
, tmp
->min
) < 0)
641 if (sval_cmp(max
, tmp
->max
) <= 0) {
642 /* Partially overlaps the next one. */
644 DELETE_CURRENT_PTR(tmp
);
647 /* Completely overlaps the next one. */
648 DELETE_CURRENT_PTR(tmp
);
649 /* there could be more ranges to delete */
653 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
654 /* join 2 ranges into a big range */
655 new = alloc_range(min
, tmp
->max
);
656 REPLACE_CURRENT_PTR(tmp
, new);
659 if (sval_cmp(max
, tmp
->min
) < 0) { /* new range entirely below */
660 new = alloc_range(min
, max
);
661 INSERT_CURRENT(new, tmp
);
664 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
665 if (sval_cmp(max
, tmp
->max
) < 0)
669 new = alloc_range(min
, max
);
670 REPLACE_CURRENT_PTR(tmp
, new);
675 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
677 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
679 new = alloc_range(min
, max
);
680 REPLACE_CURRENT_PTR(tmp
, new);
684 if (!sval_is_min(min
) && min
.value
- 1 == tmp
->max
.value
) {
685 /* join 2 ranges into a big range */
686 new = alloc_range(tmp
->min
, max
);
687 REPLACE_CURRENT_PTR(tmp
, new);
691 /* the new range is entirely above the existing ranges */
692 } END_FOR_EACH_PTR(tmp
);
695 new = alloc_range(min
, max
);
696 add_ptr_list(list
, new);
699 struct range_list
*clone_rl(struct range_list
*list
)
701 struct data_range
*tmp
;
702 struct range_list
*ret
= NULL
;
704 FOR_EACH_PTR(list
, tmp
) {
705 add_ptr_list(&ret
, tmp
);
706 } END_FOR_EACH_PTR(tmp
);
710 struct range_list
*clone_rl_permanent(struct range_list
*list
)
712 struct data_range
*tmp
;
713 struct data_range
*new;
714 struct range_list
*ret
= NULL
;
716 FOR_EACH_PTR(list
, tmp
) {
717 new = alloc_range_perm(tmp
->min
, tmp
->max
);
718 add_ptr_list(&ret
, new);
719 } END_FOR_EACH_PTR(tmp
);
723 struct range_list
*rl_union(struct range_list
*one
, struct range_list
*two
)
725 struct data_range
*tmp
;
726 struct range_list
*ret
= NULL
;
728 FOR_EACH_PTR(one
, tmp
) {
729 add_range(&ret
, tmp
->min
, tmp
->max
);
730 } END_FOR_EACH_PTR(tmp
);
731 FOR_EACH_PTR(two
, tmp
) {
732 add_range(&ret
, tmp
->min
, tmp
->max
);
733 } END_FOR_EACH_PTR(tmp
);
737 struct range_list
*remove_range(struct range_list
*list
, sval_t min
, sval_t max
)
739 struct data_range
*tmp
;
740 struct range_list
*ret
= NULL
;
742 FOR_EACH_PTR(list
, tmp
) {
743 if (sval_cmp(tmp
->max
, min
) < 0) {
744 add_range(&ret
, tmp
->min
, tmp
->max
);
747 if (sval_cmp(tmp
->min
, max
) > 0) {
748 add_range(&ret
, tmp
->min
, tmp
->max
);
751 if (sval_cmp(tmp
->min
, min
) >= 0 && sval_cmp(tmp
->max
, max
) <= 0)
753 if (sval_cmp(tmp
->min
, min
) >= 0) {
755 add_range(&ret
, max
, tmp
->max
);
756 } else if (sval_cmp(tmp
->max
, max
) <= 0) {
758 add_range(&ret
, tmp
->min
, min
);
762 add_range(&ret
, tmp
->min
, min
);
763 add_range(&ret
, max
, tmp
->max
);
765 } END_FOR_EACH_PTR(tmp
);
769 int ranges_equiv(struct data_range
*one
, struct data_range
*two
)
775 if (sval_cmp(one
->min
, two
->min
) != 0)
777 if (sval_cmp(one
->max
, two
->max
) != 0)
782 int rl_equiv(struct range_list
*one
, struct range_list
*two
)
784 struct data_range
*one_range
;
785 struct data_range
*two_range
;
790 PREPARE_PTR_LIST(one
, one_range
);
791 PREPARE_PTR_LIST(two
, two_range
);
793 if (!one_range
&& !two_range
)
795 if (!ranges_equiv(one_range
, two_range
))
797 NEXT_PTR_LIST(one_range
);
798 NEXT_PTR_LIST(two_range
);
800 FINISH_PTR_LIST(two_range
);
801 FINISH_PTR_LIST(one_range
);
806 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
808 switch (comparison
) {
810 case SPECIAL_UNSIGNED_LT
:
811 if (sval_cmp(left
->min
, right
->max
) < 0)
814 case SPECIAL_UNSIGNED_LTE
:
816 if (sval_cmp(left
->min
, right
->max
) <= 0)
820 if (sval_cmp(left
->max
, right
->min
) < 0)
822 if (sval_cmp(left
->min
, right
->max
) > 0)
825 case SPECIAL_UNSIGNED_GTE
:
827 if (sval_cmp(left
->max
, right
->min
) >= 0)
831 case SPECIAL_UNSIGNED_GT
:
832 if (sval_cmp(left
->max
, right
->min
) > 0)
835 case SPECIAL_NOTEQUAL
:
836 if (sval_cmp(left
->min
, left
->max
) != 0)
838 if (sval_cmp(right
->min
, right
->max
) != 0)
840 if (sval_cmp(left
->min
, right
->min
) != 0)
844 sm_msg("unhandled comparison %d\n", comparison
);
850 int true_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
853 return true_comparison_range(var
, comparison
, val
);
855 return true_comparison_range(val
, comparison
, var
);
858 static int false_comparison_range_sval(struct data_range
*left
, int comparison
, struct data_range
*right
)
860 switch (comparison
) {
862 case SPECIAL_UNSIGNED_LT
:
863 if (sval_cmp(left
->max
, right
->min
) >= 0)
866 case SPECIAL_UNSIGNED_LTE
:
868 if (sval_cmp(left
->max
, right
->min
) > 0)
872 if (sval_cmp(left
->min
, left
->max
) != 0)
874 if (sval_cmp(right
->min
, right
->max
) != 0)
876 if (sval_cmp(left
->min
, right
->min
) != 0)
879 case SPECIAL_UNSIGNED_GTE
:
881 if (sval_cmp(left
->min
, right
->max
) < 0)
885 case SPECIAL_UNSIGNED_GT
:
886 if (sval_cmp(left
->min
, right
->max
) <= 0)
889 case SPECIAL_NOTEQUAL
:
890 if (sval_cmp(left
->max
, right
->min
) < 0)
892 if (sval_cmp(left
->min
, right
->max
) > 0)
896 sm_msg("unhandled comparison %d\n", comparison
);
902 int false_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
905 return false_comparison_range_sval(var
, comparison
, val
);
907 return false_comparison_range_sval(val
, comparison
, var
);
910 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
912 struct range_list
*rl_left
, *rl_right
;
913 struct data_range
*tmp_left
, *tmp_right
;
916 if (!get_implied_rl(left
, &rl_left
))
918 if (!get_implied_rl(right
, &rl_right
))
921 type
= rl_type(rl_left
);
922 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
923 type
= rl_type(rl_right
);
924 if (type_positive_bits(type
) < 31)
927 rl_left
= cast_rl(type
, rl_left
);
928 rl_right
= cast_rl(type
, rl_right
);
930 FOR_EACH_PTR(rl_left
, tmp_left
) {
931 FOR_EACH_PTR(rl_right
, tmp_right
) {
932 if (true_comparison_range(tmp_left
, comparison
, tmp_right
))
934 } END_FOR_EACH_PTR(tmp_right
);
935 } END_FOR_EACH_PTR(tmp_left
);
939 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
941 struct range_list
*rl_left
, *rl_right
;
942 struct data_range
*tmp_left
, *tmp_right
;
945 if (!get_implied_rl(left
, &rl_left
))
947 if (!get_implied_rl(right
, &rl_right
))
950 type
= rl_type(rl_left
);
951 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
952 type
= rl_type(rl_right
);
953 if (type_positive_bits(type
) < 31)
956 rl_left
= cast_rl(type
, rl_left
);
957 rl_right
= cast_rl(type
, rl_right
);
959 FOR_EACH_PTR(rl_left
, tmp_left
) {
960 FOR_EACH_PTR(rl_right
, tmp_right
) {
961 if (false_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
963 } END_FOR_EACH_PTR(tmp_right
);
964 } END_FOR_EACH_PTR(tmp_left
);
968 int possibly_true_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
970 struct data_range
*left_tmp
, *right_tmp
;
973 if (!left_ranges
|| !right_ranges
)
976 type
= rl_type(left_ranges
);
977 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
978 type
= rl_type(right_ranges
);
979 if (type_positive_bits(type
) < 31)
982 left_ranges
= cast_rl(type
, left_ranges
);
983 right_ranges
= cast_rl(type
, right_ranges
);
985 FOR_EACH_PTR(left_ranges
, left_tmp
) {
986 FOR_EACH_PTR(right_ranges
, right_tmp
) {
987 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
989 } END_FOR_EACH_PTR(right_tmp
);
990 } END_FOR_EACH_PTR(left_tmp
);
994 int possibly_false_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
996 struct data_range
*left_tmp
, *right_tmp
;
999 if (!left_ranges
|| !right_ranges
)
1002 type
= rl_type(left_ranges
);
1003 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
1004 type
= rl_type(right_ranges
);
1005 if (type_positive_bits(type
) < 31)
1008 left_ranges
= cast_rl(type
, left_ranges
);
1009 right_ranges
= cast_rl(type
, right_ranges
);
1011 FOR_EACH_PTR(left_ranges
, left_tmp
) {
1012 FOR_EACH_PTR(right_ranges
, right_tmp
) {
1013 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
1015 } END_FOR_EACH_PTR(right_tmp
);
1016 } END_FOR_EACH_PTR(left_tmp
);
1020 /* FIXME: the _rl here stands for right left so really it should be _lr */
1021 int possibly_true_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1024 return possibly_true_rl(a
, comparison
, b
);
1026 return possibly_true_rl(b
, comparison
, a
);
1029 int possibly_false_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1032 return possibly_false_rl(a
, comparison
, b
);
1034 return possibly_false_rl(b
, comparison
, a
);
1037 int rl_has_sval(struct range_list
*rl
, sval_t sval
)
1039 struct data_range
*tmp
;
1041 FOR_EACH_PTR(rl
, tmp
) {
1042 if (sval_cmp(tmp
->min
, sval
) <= 0 &&
1043 sval_cmp(tmp
->max
, sval
) >= 0)
1045 } END_FOR_EACH_PTR(tmp
);
1049 void tack_on(struct range_list
**list
, struct data_range
*drange
)
1051 add_ptr_list(list
, drange
);
1054 void push_rl(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
1056 add_ptr_list(rl_stack
, rl
);
1059 struct range_list
*pop_rl(struct range_list_stack
**rl_stack
)
1061 struct range_list
*rl
;
1063 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1064 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1068 struct range_list
*top_rl(struct range_list_stack
*rl_stack
)
1070 struct range_list
*rl
;
1072 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1076 void filter_top_rl(struct range_list_stack
**rl_stack
, sval_t start
, sval_t end
)
1078 struct range_list
*rl
;
1080 rl
= pop_rl(rl_stack
);
1081 rl
= remove_range(rl
, start
, end
);
1082 push_rl(rl_stack
, rl
);
1085 struct range_list
*rl_truncate_cast(struct symbol
*type
, struct range_list
*rl
)
1087 struct data_range
*tmp
;
1088 struct range_list
*ret
= NULL
;
1094 if (!type
|| type
== rl_type(rl
))
1097 FOR_EACH_PTR(rl
, tmp
) {
1100 if (type_bits(type
) < type_bits(rl_type(rl
))) {
1101 min
.uvalue
= tmp
->min
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1102 max
.uvalue
= tmp
->max
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1104 if (sval_cmp(min
, max
) > 0) {
1105 min
= sval_cast(type
, min
);
1106 max
= sval_cast(type
, max
);
1108 add_range_t(type
, &ret
, min
, max
);
1109 } END_FOR_EACH_PTR(tmp
);
1114 static int rl_is_sane(struct range_list
*rl
)
1116 struct data_range
*tmp
;
1117 struct symbol
*type
;
1120 FOR_EACH_PTR(rl
, tmp
) {
1121 if (!sval_fits(type
, tmp
->min
))
1123 if (!sval_fits(type
, tmp
->max
))
1125 if (sval_cmp(tmp
->min
, tmp
->max
) > 0)
1127 } END_FOR_EACH_PTR(tmp
);
1132 static int rl_type_consistent(struct range_list
*rl
)
1134 struct data_range
*tmp
;
1135 struct symbol
*type
;
1138 FOR_EACH_PTR(rl
, tmp
) {
1139 if (type
!= tmp
->min
.type
|| type
!= tmp
->max
.type
)
1141 } END_FOR_EACH_PTR(tmp
);
1145 struct range_list
*cast_rl(struct symbol
*type
, struct range_list
*rl
)
1147 struct data_range
*tmp
;
1148 struct range_list
*ret
= NULL
;
1155 if (!rl_is_sane(rl
))
1156 return alloc_whole_rl(type
);
1157 if (type
== rl_type(rl
) && rl_type_consistent(rl
))
1160 FOR_EACH_PTR(rl
, tmp
) {
1161 add_range_t(type
, &ret
, tmp
->min
, tmp
->max
);
1162 } END_FOR_EACH_PTR(tmp
);
1165 return alloc_whole_rl(type
);
1170 struct range_list
*rl_invert(struct range_list
*orig
)
1172 struct range_list
*ret
= NULL
;
1173 struct data_range
*tmp
;
1174 sval_t gap_min
, abs_max
, sval
;
1179 gap_min
= sval_type_min(rl_min(orig
).type
);
1180 abs_max
= sval_type_max(rl_max(orig
).type
);
1182 FOR_EACH_PTR(orig
, tmp
) {
1183 if (sval_cmp(tmp
->min
, gap_min
) > 0) {
1184 sval
= sval_type_val(tmp
->min
.type
, tmp
->min
.value
- 1);
1185 add_range(&ret
, gap_min
, sval
);
1187 gap_min
= sval_type_val(tmp
->max
.type
, tmp
->max
.value
+ 1);
1188 if (sval_cmp(tmp
->max
, abs_max
) == 0)
1190 } END_FOR_EACH_PTR(tmp
);
1192 if (sval_cmp(gap_min
, abs_max
) < 0)
1193 add_range(&ret
, gap_min
, abs_max
);
1198 struct range_list
*rl_filter(struct range_list
*rl
, struct range_list
*filter
)
1200 struct data_range
*tmp
;
1202 FOR_EACH_PTR(filter
, tmp
) {
1203 rl
= remove_range(rl
, tmp
->min
, tmp
->max
);
1204 } END_FOR_EACH_PTR(tmp
);
1209 struct range_list
*rl_intersection(struct range_list
*one
, struct range_list
*two
)
1211 struct range_list
*one_orig
;
1212 struct range_list
*two_orig
;
1213 struct range_list
*ret
;
1214 struct symbol
*ret_type
;
1215 struct symbol
*small_type
;
1216 struct symbol
*large_type
;
1226 ret_type
= rl_type(one
);
1227 small_type
= rl_type(one
);
1228 large_type
= rl_type(two
);
1230 if (type_bits(rl_type(two
)) < type_bits(small_type
)) {
1231 small_type
= rl_type(two
);
1232 large_type
= rl_type(one
);
1235 one
= cast_rl(large_type
, one
);
1236 two
= cast_rl(large_type
, two
);
1239 one
= rl_invert(one
);
1240 two
= rl_invert(two
);
1242 ret
= rl_filter(ret
, one
);
1243 ret
= rl_filter(ret
, two
);
1245 one
= cast_rl(small_type
, one_orig
);
1246 two
= cast_rl(small_type
, two_orig
);
1248 one
= rl_invert(one
);
1249 two
= rl_invert(two
);
1251 ret
= cast_rl(small_type
, ret
);
1252 ret
= rl_filter(ret
, one
);
1253 ret
= rl_filter(ret
, two
);
1255 return cast_rl(ret_type
, ret
);
1258 static struct range_list
*handle_mod_rl(struct range_list
*left
, struct range_list
*right
)
1263 max
= rl_max(right
);
1264 if (sval_is_max(max
))
1269 if (sval_is_negative(max
))
1271 if (sval_cmp(rl_max(left
), max
) < 0)
1275 return alloc_rl(zero
, max
);
1278 static struct range_list
*get_neg_rl(struct range_list
*rl
)
1280 struct data_range
*tmp
;
1281 struct data_range
*new;
1282 struct range_list
*ret
= NULL
;
1286 if (sval_is_positive(rl_min(rl
)))
1289 FOR_EACH_PTR(rl
, tmp
) {
1290 if (sval_is_positive(tmp
->min
))
1292 if (sval_is_positive(tmp
->max
)) {
1293 new = alloc_range(tmp
->min
, tmp
->max
);
1294 new->max
.value
= -1;
1295 add_range(&ret
, new->min
, new->max
);
1298 add_range(&ret
, tmp
->min
, tmp
->max
);
1299 } END_FOR_EACH_PTR(tmp
);
1304 static struct range_list
*get_pos_rl(struct range_list
*rl
)
1306 struct data_range
*tmp
;
1307 struct data_range
*new;
1308 struct range_list
*ret
= NULL
;
1312 if (sval_is_negative(rl_max(rl
)))
1315 FOR_EACH_PTR(rl
, tmp
) {
1316 if (sval_is_negative(tmp
->max
))
1318 if (sval_is_positive(tmp
->min
)) {
1319 add_range(&ret
, tmp
->min
, tmp
->max
);
1322 new = alloc_range(tmp
->min
, tmp
->max
);
1324 add_range(&ret
, new->min
, new->max
);
1325 } END_FOR_EACH_PTR(tmp
);
1330 static struct range_list
*divide_rl_helper(struct range_list
*left
, struct range_list
*right
)
1332 sval_t right_min
, right_max
;
1335 if (!left
|| !right
)
1338 /* let's assume we never divide by zero */
1339 right_min
= rl_min(right
);
1340 right_max
= rl_max(right
);
1341 if (right_min
.value
== 0 && right_max
.value
== 0)
1343 if (right_min
.value
== 0)
1344 right_min
.value
= 1;
1345 if (right_max
.value
== 0)
1346 right_max
.value
= -1;
1348 max
= sval_binop(rl_max(left
), '/', right_min
);
1349 min
= sval_binop(rl_min(left
), '/', right_max
);
1351 return alloc_rl(min
, max
);
1354 static struct range_list
*handle_divide_rl(struct range_list
*left
, struct range_list
*right
)
1356 struct range_list
*left_neg
, *left_pos
, *right_neg
, *right_pos
;
1357 struct range_list
*neg_neg
, *neg_pos
, *pos_neg
, *pos_pos
;
1358 struct range_list
*ret
;
1360 if (is_whole_rl(right
))
1363 left_neg
= get_neg_rl(left
);
1364 left_pos
= get_pos_rl(left
);
1365 right_neg
= get_neg_rl(right
);
1366 right_pos
= get_pos_rl(right
);
1368 neg_neg
= divide_rl_helper(left_neg
, right_neg
);
1369 neg_pos
= divide_rl_helper(left_neg
, right_pos
);
1370 pos_neg
= divide_rl_helper(left_pos
, right_neg
);
1371 pos_pos
= divide_rl_helper(left_pos
, right_pos
);
1373 ret
= rl_union(neg_neg
, neg_pos
);
1374 ret
= rl_union(ret
, pos_neg
);
1375 return rl_union(ret
, pos_pos
);
1378 static struct range_list
*handle_add_mult_rl(struct range_list
*left
, int op
, struct range_list
*right
)
1382 if (sval_binop_overflows(rl_min(left
), op
, rl_min(right
)))
1384 min
= sval_binop(rl_min(left
), op
, rl_min(right
));
1386 if (sval_binop_overflows(rl_max(left
), op
, rl_max(right
)))
1388 max
= sval_binop(rl_max(left
), op
, rl_max(right
));
1390 return alloc_rl(min
, max
);
1393 static unsigned long long rl_bits_always_set(struct range_list
*rl
)
1395 return sval_fls_mask(rl_min(rl
));
1398 static unsigned long long rl_bits_maybe_set(struct range_list
*rl
)
1400 return sval_fls_mask(rl_max(rl
));
1403 static struct range_list
*handle_OR_rl(struct range_list
*left
, struct range_list
*right
)
1405 unsigned long long left_min
, left_max
, right_min
, right_max
;
1409 if ((rl_to_sval(left
, &sval
) || rl_to_sval(right
, &sval
)) &&
1410 !sval_binop_overflows(rl_max(left
), '+', rl_max(right
)))
1411 return rl_binop(left
, '+', right
);
1413 left_min
= rl_bits_always_set(left
);
1414 left_max
= rl_bits_maybe_set(left
);
1415 right_min
= rl_bits_always_set(right
);
1416 right_max
= rl_bits_maybe_set(right
);
1418 min
.type
= max
.type
= &ullong_ctype
;
1419 min
.uvalue
= left_min
| right_min
;
1420 max
.uvalue
= left_max
| right_max
;
1422 return cast_rl(rl_type(left
), alloc_rl(min
, max
));
1425 static struct range_list
*handle_XOR_rl(struct range_list
*left
, struct range_list
*right
)
1427 unsigned long long left_set
, left_maybe
;
1428 unsigned long long right_set
, right_maybe
;
1431 left_set
= rl_bits_always_set(left
);
1432 left_maybe
= rl_bits_maybe_set(left
);
1434 right_set
= rl_bits_always_set(right
);
1435 right_maybe
= rl_bits_maybe_set(right
);
1437 zero
= max
= rl_min(left
);
1439 max
.uvalue
= fls_mask((left_maybe
| right_maybe
) ^ (left_set
& right_set
));
1441 return cast_rl(rl_type(left
), alloc_rl(zero
, max
));
1444 struct range_list
*rl_binop(struct range_list
*left
, int op
, struct range_list
*right
)
1446 struct symbol
*cast_type
;
1447 sval_t left_sval
, right_sval
;
1448 struct range_list
*ret
= NULL
;
1450 cast_type
= rl_type(left
);
1451 if (sval_type_max(rl_type(left
)).uvalue
< sval_type_max(rl_type(right
)).uvalue
)
1452 cast_type
= rl_type(right
);
1453 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
1454 cast_type
= &int_ctype
;
1456 left
= cast_rl(cast_type
, left
);
1457 right
= cast_rl(cast_type
, right
);
1459 if (!left
|| !right
)
1460 return alloc_whole_rl(cast_type
);
1462 if (rl_to_sval(left
, &left_sval
) && rl_to_sval(right
, &right_sval
)) {
1463 sval_t val
= sval_binop(left_sval
, op
, right_sval
);
1464 return alloc_rl(val
, val
);
1469 ret
= handle_mod_rl(left
, right
);
1472 ret
= handle_divide_rl(left
, right
);
1476 ret
= handle_add_mult_rl(left
, op
, right
);
1479 ret
= handle_OR_rl(left
, right
);
1482 ret
= handle_XOR_rl(left
, right
);
1485 /* FIXME: Do the rest as well */
1488 case SPECIAL_RIGHTSHIFT
:
1489 case SPECIAL_LEFTSHIFT
:
1494 ret
= alloc_whole_rl(cast_type
);
1498 void free_rl(struct range_list
**rlist
)
1500 __free_ptr_list((struct ptr_list
**)rlist
);
1503 static void free_single_dinfo(struct data_info
*dinfo
)
1505 free_rl(&dinfo
->value_ranges
);
1508 static void free_dinfos(struct allocation_blob
*blob
)
1510 unsigned int size
= sizeof(struct data_info
);
1511 unsigned int offset
= 0;
1513 while (offset
< blob
->offset
) {
1514 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
1519 void free_data_info_allocs(void)
1521 struct allocator_struct
*desc
= &data_info_allocator
;
1522 struct allocation_blob
*blob
= desc
->blobs
;
1525 desc
->allocations
= 0;
1526 desc
->total_bytes
= 0;
1527 desc
->useful_bytes
= 0;
1528 desc
->freelist
= NULL
;
1530 struct allocation_blob
*next
= blob
->next
;
1532 blob_free(blob
, desc
->chunking
);
1535 clear_data_range_alloc();