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 str_to_comparison_arg_helper(const char *str
,
51 struct expression
*call
, int *comparison
,
52 struct expression
**arg
, char **endp
)
55 char *c
= (char *)str
;
64 *comparison
= SPECIAL_LTE
;
69 } else if (*c
== '=') {
72 *comparison
= SPECIAL_EQUAL
;
73 } else if (*c
== '>') {
76 *comparison
= SPECIAL_GTE
;
81 } else if (*c
== '!') {
84 *comparison
= SPECIAL_NOTEQUAL
;
93 param
= strtoll(c
, &c
, 10);
94 c
++; /* skip the ']' character */
100 *arg
= get_argument_from_call_expr(call
->args
, param
);
106 int str_to_comparison_arg(const char *str
, struct expression
*call
, int *comparison
, struct expression
**arg
)
115 return str_to_comparison_arg_helper(str
, call
, comparison
, arg
, NULL
);
118 static int get_val_from_key(int use_max
, struct symbol
*type
, char *c
, struct expression
*call
, char **endp
, sval_t
*sval
)
120 struct expression
*arg
;
125 ret
= sval_type_max(type
);
127 ret
= sval_type_min(type
);
129 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
)) {
134 if (use_max
&& get_implied_max(arg
, &tmp
)) {
136 if (comparison
== '<') {
138 ret
= sval_binop(ret
, '-', tmp
);
141 if (!use_max
&& get_implied_min(arg
, &tmp
)) {
143 if (comparison
== '>') {
145 ret
= sval_binop(ret
, '+', tmp
);
153 static sval_t
add_one(sval_t sval
)
159 static sval_t
sub_one(sval_t sval
)
165 void filter_by_comparison(struct range_list
**rl
, int comparison
, struct range_list
*right
)
167 struct range_list
*left_orig
= *rl
;
168 struct range_list
*right_orig
= right
;
169 struct range_list
*ret_rl
= *rl
;
170 struct symbol
*cast_type
;
173 cast_type
= rl_type(left_orig
);
174 if (sval_type_max(rl_type(left_orig
)).uvalue
< sval_type_max(rl_type(right_orig
)).uvalue
)
175 cast_type
= rl_type(right_orig
);
176 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
177 cast_type
= &int_ctype
;
179 min
= sval_type_min(cast_type
);
180 max
= sval_type_max(cast_type
);
181 left_orig
= cast_rl(cast_type
, left_orig
);
182 right_orig
= cast_rl(cast_type
, right_orig
);
184 switch (comparison
) {
186 case SPECIAL_UNSIGNED_LT
:
187 ret_rl
= remove_range(left_orig
, rl_max(right_orig
), max
);
190 case SPECIAL_UNSIGNED_LTE
:
191 if (!sval_is_max(rl_max(right_orig
)))
192 ret_rl
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
195 if (!sval_is_max(rl_max(right_orig
)))
196 ret_rl
= remove_range(ret_rl
, add_one(rl_max(right_orig
)), max
);
197 if (!sval_is_min(rl_min(right_orig
)))
198 ret_rl
= remove_range(ret_rl
, min
, sub_one(rl_min(right_orig
)));
201 case SPECIAL_UNSIGNED_GTE
:
202 if (!sval_is_min(rl_min(right_orig
)))
203 ret_rl
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
206 case SPECIAL_UNSIGNED_GT
:
207 ret_rl
= remove_range(left_orig
, min
, rl_min(right_orig
));
209 case SPECIAL_NOTEQUAL
:
210 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
211 ret_rl
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
214 sm_msg("internal error: unhandled comparison %s", show_special(comparison
));
218 *rl
= cast_rl(rl_type(*rl
), ret_rl
);
221 static struct range_list
*filter_by_comparison_call(char *c
, struct expression
*call
, char **endp
, struct range_list
*start_rl
)
223 struct expression
*arg
;
224 struct range_list
*right_orig
;
227 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
))
230 if (!get_implied_rl(arg
, &right_orig
))
233 filter_by_comparison(&start_rl
, comparison
, right_orig
);
237 static sval_t
parse_val(int use_max
, struct expression
*call
, struct symbol
*type
, char *c
, char **endp
)
242 if (!strncmp(start
, "max", 3)) {
243 ret
= sval_type_max(type
);
245 } else if (!strncmp(start
, "u64max", 6)) {
246 ret
= sval_type_val(type
, ULLONG_MAX
);
248 } else if (!strncmp(start
, "s64max", 6)) {
249 ret
= sval_type_val(type
, LLONG_MAX
);
251 } else if (!strncmp(start
, "u32max", 6)) {
252 ret
= sval_type_val(type
, UINT_MAX
);
254 } else if (!strncmp(start
, "s32max", 6)) {
255 ret
= sval_type_val(type
, INT_MAX
);
257 } else if (!strncmp(start
, "u16max", 6)) {
258 ret
= sval_type_val(type
, USHRT_MAX
);
260 } else if (!strncmp(start
, "s16max", 6)) {
261 ret
= sval_type_val(type
, SHRT_MAX
);
263 } else if (!strncmp(start
, "min", 3)) {
264 ret
= sval_type_min(type
);
266 } else if (!strncmp(start
, "s64min", 6)) {
267 ret
= sval_type_val(type
, LLONG_MIN
);
269 } else if (!strncmp(start
, "s32min", 6)) {
270 ret
= sval_type_val(type
, INT_MIN
);
272 } else if (!strncmp(start
, "s16min", 6)) {
273 ret
= sval_type_val(type
, SHRT_MIN
);
275 } else if (!strncmp(start
, "long_min", 8)) {
276 ret
= sval_type_val(type
, LONG_MIN
);
278 } else if (!strncmp(start
, "long_max", 8)) {
279 ret
= sval_type_val(type
, LONG_MAX
);
281 } else if (!strncmp(start
, "ulong_max", 9)) {
282 ret
= sval_type_val(type
, ULONG_MAX
);
284 } else if (!strncmp(start
, "ptr_max", 7)) {
285 ret
= sval_type_val(type
, valid_ptr_max
);
287 } else if (start
[0] == '[') {
288 /* this parses [==p0] comparisons */
289 get_val_from_key(1, type
, start
, call
, &c
, &ret
);
291 ret
= sval_type_val(type
, strtoll(start
, &c
, 10));
297 static char *jump_to_call_math(char *value
)
301 while (*c
&& *c
!= '[')
307 if (*c
== '<' || *c
== '=' || *c
== '>' || *c
== '!')
313 static void str_to_rl_helper(struct expression
*call
, struct symbol
*type
, char *value
, struct range_list
**rl
)
315 struct range_list
*math_rl
;
324 if (strcmp(value
, "empty") == 0)
327 if (strncmp(value
, "[==$", 4) == 0) {
328 struct expression
*arg
;
331 if (!str_to_comparison_arg(value
, call
, &comparison
, &arg
))
333 if (!get_implied_rl(arg
, rl
))
338 min
= sval_type_min(type
);
339 max
= sval_type_max(type
);
341 while (*c
!= '\0' && *c
!= '[') {
344 min
= parse_val(0, call
, type
, c
, &c
);
348 if (*c
== '\0' || *c
== '[') {
349 add_range(rl
, min
, min
);
353 add_range(rl
, min
, min
);
358 sm_msg("debug XXX: trouble parsing %s c = %s", value
, c
);
364 max
= parse_val(1, call
, type
, c
, &c
);
365 add_range(rl
, min
, max
);
375 call_math
= jump_to_call_math(value
);
376 if (call_math
&& parse_call_math_rl(call
, call_math
, &math_rl
)) {
377 *rl
= rl_intersection(*rl
, math_rl
);
382 * For now if we already tried to handle the call math and couldn't
383 * figure it out then bail.
385 if (jump_to_call_math(c
) == c
+ 1)
388 *rl
= filter_by_comparison_call(c
, call
, &c
, *rl
);
391 *rl
= cast_rl(type
, *rl
);
394 void str_to_rl(struct symbol
*type
, char *value
, struct range_list
**rl
)
396 return str_to_rl_helper(NULL
, type
, value
, rl
);
399 void call_results_to_rl(struct expression
*expr
, struct symbol
*type
, char *value
, struct range_list
**rl
)
401 return str_to_rl_helper(strip_expr(expr
), type
, value
, rl
);
404 int is_whole_rl(struct range_list
*rl
)
406 struct data_range
*drange
;
408 if (ptr_list_empty(rl
))
410 drange
= first_ptr_list((struct ptr_list
*)rl
);
411 if (sval_is_min(drange
->min
) && sval_is_max(drange
->max
))
416 sval_t
rl_min(struct range_list
*rl
)
418 struct data_range
*drange
;
421 ret
.type
= &llong_ctype
;
422 ret
.value
= LLONG_MIN
;
423 if (ptr_list_empty(rl
))
425 drange
= first_ptr_list((struct ptr_list
*)rl
);
429 sval_t
rl_max(struct range_list
*rl
)
431 struct data_range
*drange
;
434 ret
.type
= &llong_ctype
;
435 ret
.value
= LLONG_MAX
;
436 if (ptr_list_empty(rl
))
438 drange
= last_ptr_list((struct ptr_list
*)rl
);
442 int rl_to_sval(struct range_list
*rl
, sval_t
*sval
)
451 if (sval_cmp(min
, max
) != 0)
457 struct symbol
*rl_type(struct range_list
*rl
)
461 return rl_min(rl
).type
;
464 static struct data_range
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
466 struct data_range
*ret
;
469 ret
= __alloc_perm_data_range(0);
471 ret
= __alloc_data_range(0);
477 struct data_range
*alloc_range(sval_t min
, sval_t max
)
479 return alloc_range_helper_sval(min
, max
, 0);
482 struct data_range
*alloc_range_perm(sval_t min
, sval_t max
)
484 return alloc_range_helper_sval(min
, max
, 1);
487 struct range_list
*alloc_rl(sval_t min
, sval_t max
)
489 struct range_list
*rl
= NULL
;
491 if (sval_cmp(min
, max
) > 0)
492 return alloc_whole_rl(min
.type
);
494 add_range(&rl
, min
, max
);
498 struct range_list
*alloc_whole_rl(struct symbol
*type
)
500 if (!type
|| type_positive_bits(type
) < 0)
502 if (type
->type
== SYM_ARRAY
)
505 return alloc_rl(sval_type_min(type
), sval_type_max(type
));
508 void add_range(struct range_list
**list
, sval_t min
, sval_t max
)
510 struct data_range
*tmp
= NULL
;
511 struct data_range
*new = NULL
;
515 * FIXME: This has a problem merging a range_list like: min-0,3-max
516 * with a range like 1-2. You end up with min-2,3-max instead of
519 FOR_EACH_PTR(*list
, tmp
) {
521 /* Sometimes we overlap with more than one range
522 so we have to delete or modify the next range. */
523 if (max
.value
+ 1 == tmp
->min
.value
) {
524 /* join 2 ranges here */
526 DELETE_CURRENT_PTR(tmp
);
530 /* Doesn't overlap with the next one. */
531 if (sval_cmp(max
, tmp
->min
) < 0)
533 /* Partially overlaps with the next one. */
534 if (sval_cmp(max
, tmp
->max
) < 0) {
535 tmp
->min
.value
= max
.value
+ 1;
538 /* Completely overlaps with the next one. */
539 if (sval_cmp(max
, tmp
->max
) >= 0) {
540 DELETE_CURRENT_PTR(tmp
);
541 /* there could be more ranges to delete */
545 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
546 /* join 2 ranges into a big range */
547 new = alloc_range(min
, tmp
->max
);
548 REPLACE_CURRENT_PTR(tmp
, new);
551 if (sval_cmp(max
, tmp
->min
) < 0) { /* new range entirely below */
552 new = alloc_range(min
, max
);
553 INSERT_CURRENT(new, tmp
);
556 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
557 if (sval_cmp(max
, tmp
->max
) < 0)
561 new = alloc_range(min
, max
);
562 REPLACE_CURRENT_PTR(tmp
, new);
567 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
569 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
571 new = alloc_range(min
, max
);
572 REPLACE_CURRENT_PTR(tmp
, new);
576 if (!sval_is_min(min
) && min
.value
- 1 == tmp
->max
.value
) {
577 /* join 2 ranges into a big range */
578 new = alloc_range(tmp
->min
, max
);
579 REPLACE_CURRENT_PTR(tmp
, new);
583 /* the new range is entirely above the existing ranges */
584 } END_FOR_EACH_PTR(tmp
);
587 new = alloc_range(min
, max
);
588 add_ptr_list(list
, new);
591 struct range_list
*clone_rl(struct range_list
*list
)
593 struct data_range
*tmp
;
594 struct range_list
*ret
= NULL
;
596 FOR_EACH_PTR(list
, tmp
) {
597 add_ptr_list(&ret
, tmp
);
598 } END_FOR_EACH_PTR(tmp
);
602 struct range_list
*clone_rl_permanent(struct range_list
*list
)
604 struct data_range
*tmp
;
605 struct data_range
*new;
606 struct range_list
*ret
= NULL
;
608 FOR_EACH_PTR(list
, tmp
) {
609 new = alloc_range_perm(tmp
->min
, tmp
->max
);
610 add_ptr_list(&ret
, new);
611 } END_FOR_EACH_PTR(tmp
);
615 struct range_list
*rl_union(struct range_list
*one
, struct range_list
*two
)
617 struct data_range
*tmp
;
618 struct range_list
*ret
= NULL
;
620 FOR_EACH_PTR(one
, tmp
) {
621 add_range(&ret
, tmp
->min
, tmp
->max
);
622 } END_FOR_EACH_PTR(tmp
);
623 FOR_EACH_PTR(two
, tmp
) {
624 add_range(&ret
, tmp
->min
, tmp
->max
);
625 } END_FOR_EACH_PTR(tmp
);
629 struct range_list
*remove_range(struct range_list
*list
, sval_t min
, sval_t max
)
631 struct data_range
*tmp
;
632 struct range_list
*ret
= NULL
;
634 FOR_EACH_PTR(list
, tmp
) {
635 if (sval_cmp(tmp
->max
, min
) < 0) {
636 add_range(&ret
, tmp
->min
, tmp
->max
);
639 if (sval_cmp(tmp
->min
, max
) > 0) {
640 add_range(&ret
, tmp
->min
, tmp
->max
);
643 if (sval_cmp(tmp
->min
, min
) >= 0 && sval_cmp(tmp
->max
, max
) <= 0)
645 if (sval_cmp(tmp
->min
, min
) >= 0) {
647 add_range(&ret
, max
, tmp
->max
);
648 } else if (sval_cmp(tmp
->max
, max
) <= 0) {
650 add_range(&ret
, tmp
->min
, min
);
654 add_range(&ret
, tmp
->min
, min
);
655 add_range(&ret
, max
, tmp
->max
);
657 } END_FOR_EACH_PTR(tmp
);
661 int ranges_equiv(struct data_range
*one
, struct data_range
*two
)
667 if (sval_cmp(one
->min
, two
->min
) != 0)
669 if (sval_cmp(one
->max
, two
->max
) != 0)
674 int rl_equiv(struct range_list
*one
, struct range_list
*two
)
676 struct data_range
*one_range
;
677 struct data_range
*two_range
;
682 PREPARE_PTR_LIST(one
, one_range
);
683 PREPARE_PTR_LIST(two
, two_range
);
685 if (!one_range
&& !two_range
)
687 if (!ranges_equiv(one_range
, two_range
))
689 NEXT_PTR_LIST(one_range
);
690 NEXT_PTR_LIST(two_range
);
692 FINISH_PTR_LIST(two_range
);
693 FINISH_PTR_LIST(one_range
);
698 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
700 switch (comparison
) {
702 case SPECIAL_UNSIGNED_LT
:
703 if (sval_cmp(left
->min
, right
->max
) < 0)
706 case SPECIAL_UNSIGNED_LTE
:
708 if (sval_cmp(left
->min
, right
->max
) <= 0)
712 if (sval_cmp(left
->max
, right
->min
) < 0)
714 if (sval_cmp(left
->min
, right
->max
) > 0)
717 case SPECIAL_UNSIGNED_GTE
:
719 if (sval_cmp(left
->max
, right
->min
) >= 0)
723 case SPECIAL_UNSIGNED_GT
:
724 if (sval_cmp(left
->max
, right
->min
) > 0)
727 case SPECIAL_NOTEQUAL
:
728 if (sval_cmp(left
->min
, left
->max
) != 0)
730 if (sval_cmp(right
->min
, right
->max
) != 0)
732 if (sval_cmp(left
->min
, right
->min
) != 0)
736 sm_msg("unhandled comparison %d\n", comparison
);
742 int true_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
745 return true_comparison_range(var
, comparison
, val
);
747 return true_comparison_range(val
, comparison
, var
);
750 static int false_comparison_range_sval(struct data_range
*left
, int comparison
, struct data_range
*right
)
752 switch (comparison
) {
754 case SPECIAL_UNSIGNED_LT
:
755 if (sval_cmp(left
->max
, right
->min
) >= 0)
758 case SPECIAL_UNSIGNED_LTE
:
760 if (sval_cmp(left
->max
, right
->min
) > 0)
764 if (sval_cmp(left
->min
, left
->max
) != 0)
766 if (sval_cmp(right
->min
, right
->max
) != 0)
768 if (sval_cmp(left
->min
, right
->min
) != 0)
771 case SPECIAL_UNSIGNED_GTE
:
773 if (sval_cmp(left
->min
, right
->max
) < 0)
777 case SPECIAL_UNSIGNED_GT
:
778 if (sval_cmp(left
->min
, right
->max
) <= 0)
781 case SPECIAL_NOTEQUAL
:
782 if (sval_cmp(left
->max
, right
->min
) < 0)
784 if (sval_cmp(left
->min
, right
->max
) > 0)
788 sm_msg("unhandled comparison %d\n", comparison
);
794 int false_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
797 return false_comparison_range_sval(var
, comparison
, val
);
799 return false_comparison_range_sval(val
, comparison
, var
);
802 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
804 struct range_list
*rl_left
, *rl_right
;
805 struct data_range
*tmp_left
, *tmp_right
;
808 if (!get_implied_rl(left
, &rl_left
))
810 if (!get_implied_rl(right
, &rl_right
))
813 type
= rl_type(rl_left
);
814 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
815 type
= rl_type(rl_right
);
816 if (type_positive_bits(type
) < 31)
819 rl_left
= cast_rl(type
, rl_left
);
820 rl_right
= cast_rl(type
, rl_right
);
822 FOR_EACH_PTR(rl_left
, tmp_left
) {
823 FOR_EACH_PTR(rl_right
, tmp_right
) {
824 if (true_comparison_range(tmp_left
, comparison
, tmp_right
))
826 } END_FOR_EACH_PTR(tmp_right
);
827 } END_FOR_EACH_PTR(tmp_left
);
831 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
833 struct range_list
*rl_left
, *rl_right
;
834 struct data_range
*tmp_left
, *tmp_right
;
837 if (!get_implied_rl(left
, &rl_left
))
839 if (!get_implied_rl(right
, &rl_right
))
842 type
= rl_type(rl_left
);
843 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
844 type
= rl_type(rl_right
);
845 if (type_positive_bits(type
) < 31)
848 rl_left
= cast_rl(type
, rl_left
);
849 rl_right
= cast_rl(type
, rl_right
);
851 FOR_EACH_PTR(rl_left
, tmp_left
) {
852 FOR_EACH_PTR(rl_right
, tmp_right
) {
853 if (false_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
855 } END_FOR_EACH_PTR(tmp_right
);
856 } END_FOR_EACH_PTR(tmp_left
);
860 int possibly_true_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
862 struct data_range
*left_tmp
, *right_tmp
;
864 if (!left_ranges
|| !right_ranges
)
867 FOR_EACH_PTR(left_ranges
, left_tmp
) {
868 FOR_EACH_PTR(right_ranges
, right_tmp
) {
869 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
871 } END_FOR_EACH_PTR(right_tmp
);
872 } END_FOR_EACH_PTR(left_tmp
);
876 int possibly_false_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
878 struct data_range
*left_tmp
, *right_tmp
;
880 if (!left_ranges
|| !right_ranges
)
883 FOR_EACH_PTR(left_ranges
, left_tmp
) {
884 FOR_EACH_PTR(right_ranges
, right_tmp
) {
885 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
887 } END_FOR_EACH_PTR(right_tmp
);
888 } END_FOR_EACH_PTR(left_tmp
);
892 /* FIXME: the _rl here stands for right left so really it should be _lr */
893 int possibly_true_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
896 return possibly_true_rl(a
, comparison
, b
);
898 return possibly_true_rl(b
, comparison
, a
);
901 int possibly_false_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
904 return possibly_false_rl(a
, comparison
, b
);
906 return possibly_false_rl(b
, comparison
, a
);
909 int rl_has_sval(struct range_list
*rl
, sval_t sval
)
911 struct data_range
*tmp
;
913 FOR_EACH_PTR(rl
, tmp
) {
914 if (sval_cmp(tmp
->min
, sval
) <= 0 &&
915 sval_cmp(tmp
->max
, sval
) >= 0)
917 } END_FOR_EACH_PTR(tmp
);
921 void tack_on(struct range_list
**list
, struct data_range
*drange
)
923 add_ptr_list(list
, drange
);
926 void push_rl(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
928 add_ptr_list(rl_stack
, rl
);
931 struct range_list
*pop_rl(struct range_list_stack
**rl_stack
)
933 struct range_list
*rl
;
935 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
936 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
940 struct range_list
*top_rl(struct range_list_stack
*rl_stack
)
942 struct range_list
*rl
;
944 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
948 void filter_top_rl(struct range_list_stack
**rl_stack
, sval_t sval
)
950 struct range_list
*rl
;
952 rl
= pop_rl(rl_stack
);
953 rl
= remove_range(rl
, sval
, sval
);
954 push_rl(rl_stack
, rl
);
957 static int sval_too_big(struct symbol
*type
, sval_t sval
)
959 if (type_bits(type
) == 64)
961 if (sval
.uvalue
> ((1ULL << type_bits(type
)) - 1))
966 static void add_range_t(struct symbol
*type
, struct range_list
**rl
, sval_t min
, sval_t max
)
968 /* If we're just adding a number, cast it and add it */
969 if (sval_cmp(min
, max
) == 0) {
970 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
974 /* If the range is within the type range then add it */
975 if (sval_fits(type
, min
) && sval_fits(type
, max
)) {
976 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
981 * If the range we are adding has more bits than the range type then
982 * add the whole range type. Eg:
983 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
984 * This isn't totally the right thing to do. We could be more granular.
986 if (sval_too_big(type
, min
) || sval_too_big(type
, max
)) {
987 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
991 /* Cast negative values to high positive values */
992 if (sval_is_negative(min
) && type_unsigned(type
)) {
993 if (sval_is_positive(max
)) {
994 if (sval_too_high(type
, max
)) {
995 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
998 add_range(rl
, sval_type_val(type
, 0), sval_cast(type
, max
));
999 max
= sval_type_max(type
);
1001 max
= sval_cast(type
, max
);
1003 min
= sval_cast(type
, min
);
1004 add_range(rl
, min
, max
);
1007 /* Cast high positive numbers to negative */
1008 if (sval_unsigned(max
) && sval_is_negative(sval_cast(type
, max
))) {
1009 if (!sval_is_negative(sval_cast(type
, min
))) {
1010 add_range(rl
, sval_cast(type
, min
), sval_type_max(type
));
1011 min
= sval_type_min(type
);
1013 min
= sval_cast(type
, min
);
1015 max
= sval_cast(type
, max
);
1016 add_range(rl
, min
, max
);
1019 add_range(rl
, min
, max
);
1023 struct range_list
*rl_truncate_cast(struct symbol
*type
, struct range_list
*rl
)
1025 struct data_range
*tmp
;
1026 struct range_list
*ret
= NULL
;
1032 if (!type
|| type
== rl_type(rl
))
1035 FOR_EACH_PTR(rl
, tmp
) {
1038 if (type_bits(type
) < type_bits(rl_type(rl
))) {
1039 min
.uvalue
= tmp
->min
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1040 max
.uvalue
= tmp
->max
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1042 if (sval_cmp(min
, max
) > 0) {
1043 min
= sval_cast(type
, min
);
1044 max
= sval_cast(type
, max
);
1046 add_range_t(type
, &ret
, min
, max
);
1047 } END_FOR_EACH_PTR(tmp
);
1052 static int rl_is_sane(struct range_list
*rl
)
1054 struct data_range
*tmp
;
1055 struct symbol
*type
;
1058 FOR_EACH_PTR(rl
, tmp
) {
1059 if (!sval_fits(type
, tmp
->min
))
1061 if (!sval_fits(type
, tmp
->max
))
1063 if (sval_cmp(tmp
->min
, tmp
->max
) > 0)
1065 } END_FOR_EACH_PTR(tmp
);
1070 static int rl_type_consistent(struct range_list
*rl
)
1072 struct data_range
*tmp
;
1073 struct symbol
*type
;
1076 FOR_EACH_PTR(rl
, tmp
) {
1077 if (type
!= tmp
->min
.type
|| type
!= tmp
->max
.type
)
1079 } END_FOR_EACH_PTR(tmp
);
1083 struct range_list
*cast_rl(struct symbol
*type
, struct range_list
*rl
)
1085 struct data_range
*tmp
;
1086 struct range_list
*ret
= NULL
;
1093 if (!rl_is_sane(rl
))
1094 return alloc_whole_rl(type
);
1095 if (type
== rl_type(rl
) && rl_type_consistent(rl
))
1098 FOR_EACH_PTR(rl
, tmp
) {
1099 add_range_t(type
, &ret
, tmp
->min
, tmp
->max
);
1100 } END_FOR_EACH_PTR(tmp
);
1103 return alloc_whole_rl(type
);
1108 struct range_list
*rl_invert(struct range_list
*orig
)
1110 struct range_list
*ret
= NULL
;
1111 struct data_range
*tmp
;
1112 sval_t gap_min
, abs_max
, sval
;
1117 gap_min
= sval_type_min(rl_min(orig
).type
);
1118 abs_max
= sval_type_max(rl_max(orig
).type
);
1120 FOR_EACH_PTR(orig
, tmp
) {
1121 if (sval_cmp(tmp
->min
, gap_min
) > 0) {
1122 sval
= sval_type_val(tmp
->min
.type
, tmp
->min
.value
- 1);
1123 add_range(&ret
, gap_min
, sval
);
1125 gap_min
= sval_type_val(tmp
->max
.type
, tmp
->max
.value
+ 1);
1126 if (sval_cmp(tmp
->max
, abs_max
) == 0)
1128 } END_FOR_EACH_PTR(tmp
);
1130 if (sval_cmp(gap_min
, abs_max
) < 0)
1131 add_range(&ret
, gap_min
, abs_max
);
1136 struct range_list
*rl_filter(struct range_list
*rl
, struct range_list
*filter
)
1138 struct data_range
*tmp
;
1140 FOR_EACH_PTR(filter
, tmp
) {
1141 rl
= remove_range(rl
, tmp
->min
, tmp
->max
);
1142 } END_FOR_EACH_PTR(tmp
);
1147 struct range_list
*rl_intersection(struct range_list
*one
, struct range_list
*two
)
1149 struct range_list
*one_orig
;
1150 struct range_list
*two_orig
;
1151 struct range_list
*ret
;
1152 struct symbol
*ret_type
;
1153 struct symbol
*small_type
;
1154 struct symbol
*large_type
;
1164 ret_type
= rl_type(one
);
1165 small_type
= rl_type(one
);
1166 large_type
= rl_type(two
);
1168 if (type_bits(rl_type(two
)) < type_bits(small_type
)) {
1169 small_type
= rl_type(two
);
1170 large_type
= rl_type(one
);
1173 one
= cast_rl(large_type
, one
);
1174 two
= cast_rl(large_type
, two
);
1177 one
= rl_invert(one
);
1178 two
= rl_invert(two
);
1180 ret
= rl_filter(ret
, one
);
1181 ret
= rl_filter(ret
, two
);
1183 one
= cast_rl(small_type
, one_orig
);
1184 two
= cast_rl(small_type
, two_orig
);
1186 one
= rl_invert(one
);
1187 two
= rl_invert(two
);
1189 ret
= cast_rl(small_type
, ret
);
1190 ret
= rl_filter(ret
, one
);
1191 ret
= rl_filter(ret
, two
);
1193 return cast_rl(ret_type
, ret
);
1196 static struct range_list
*handle_mod_rl(struct range_list
*left
, struct range_list
*right
)
1201 max
= rl_max(right
);
1202 if (sval_is_max(max
))
1207 if (sval_is_negative(max
))
1209 if (sval_cmp(rl_max(left
), max
) < 0)
1213 return alloc_rl(zero
, max
);
1216 static struct range_list
*handle_divide_rl(struct range_list
*left
, struct range_list
*right
)
1220 if (sval_is_max(rl_max(left
)))
1222 if (sval_is_max(rl_max(right
)))
1225 if (sval_is_negative(rl_min(left
)))
1227 if (sval_cmp_val(rl_min(right
), 0) <= 0)
1230 max
= sval_binop(rl_max(left
), '/', rl_min(right
));
1231 min
= sval_binop(rl_min(left
), '/', rl_max(right
));
1233 return alloc_rl(min
, max
);
1236 static struct range_list
*handle_add_mult_rl(struct range_list
*left
, int op
, struct range_list
*right
)
1240 if (sval_binop_overflows(rl_min(left
), op
, rl_min(right
)))
1242 min
= sval_binop(rl_min(left
), op
, rl_min(right
));
1244 if (sval_binop_overflows(rl_max(left
), op
, rl_max(right
)))
1246 max
= sval_binop(rl_max(left
), op
, rl_max(right
));
1248 return alloc_rl(min
, max
);
1251 static unsigned long long sval_fls_mask(sval_t sval
)
1253 unsigned long long uvalue
= sval
.uvalue
;
1254 unsigned long long high_bit
= 0;
1264 return ((unsigned long long)-1) >> (64 - high_bit
);
1267 static unsigned long long rl_bits_always_set(struct range_list
*rl
)
1269 return sval_fls_mask(rl_min(rl
));
1272 static unsigned long long rl_bits_maybe_set(struct range_list
*rl
)
1274 return sval_fls_mask(rl_max(rl
));
1277 static struct range_list
*handle_OR_rl(struct range_list
*left
, struct range_list
*right
)
1279 unsigned long long left_min
, left_max
, right_min
, right_max
;
1283 if ((rl_to_sval(left
, &sval
) || rl_to_sval(right
, &sval
)) &&
1284 !sval_binop_overflows(rl_max(left
), '+', rl_max(right
)))
1285 return rl_binop(left
, '+', right
);
1287 left_min
= rl_bits_always_set(left
);
1288 left_max
= rl_bits_maybe_set(left
);
1289 right_min
= rl_bits_always_set(right
);
1290 right_max
= rl_bits_maybe_set(right
);
1292 min
.type
= max
.type
= &ullong_ctype
;
1293 min
.uvalue
= left_min
| right_min
;
1294 max
.uvalue
= left_max
| right_max
;
1296 return cast_rl(rl_type(left
), alloc_rl(min
, max
));
1299 struct range_list
*rl_binop(struct range_list
*left
, int op
, struct range_list
*right
)
1301 struct symbol
*cast_type
;
1302 sval_t left_sval
, right_sval
;
1303 struct range_list
*ret
= NULL
;
1305 cast_type
= rl_type(left
);
1306 if (sval_type_max(rl_type(left
)).uvalue
< sval_type_max(rl_type(right
)).uvalue
)
1307 cast_type
= rl_type(right
);
1308 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
1309 cast_type
= &int_ctype
;
1311 left
= cast_rl(cast_type
, left
);
1312 right
= cast_rl(cast_type
, right
);
1314 if (!left
|| !right
)
1315 return alloc_whole_rl(cast_type
);
1317 if (rl_to_sval(left
, &left_sval
) && rl_to_sval(right
, &right_sval
)) {
1318 sval_t val
= sval_binop(left_sval
, op
, right_sval
);
1319 return alloc_rl(val
, val
);
1324 ret
= handle_mod_rl(left
, right
);
1327 ret
= handle_divide_rl(left
, right
);
1331 ret
= handle_add_mult_rl(left
, op
, right
);
1334 ret
= handle_OR_rl(left
, right
);
1337 /* FIXME: Do the rest as well */
1340 case SPECIAL_RIGHTSHIFT
:
1341 case SPECIAL_LEFTSHIFT
:
1347 ret
= alloc_whole_rl(cast_type
);
1351 void free_rl(struct range_list
**rlist
)
1353 __free_ptr_list((struct ptr_list
**)rlist
);
1356 static void free_single_dinfo(struct data_info
*dinfo
)
1358 free_rl(&dinfo
->value_ranges
);
1361 static void free_dinfos(struct allocation_blob
*blob
)
1363 unsigned int size
= sizeof(struct data_info
);
1364 unsigned int offset
= 0;
1366 while (offset
< blob
->offset
) {
1367 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
1372 void free_data_info_allocs(void)
1374 struct allocator_struct
*desc
= &data_info_allocator
;
1375 struct allocation_blob
*blob
= desc
->blobs
;
1378 desc
->allocations
= 0;
1379 desc
->total_bytes
= 0;
1380 desc
->useful_bytes
= 0;
1381 desc
->freelist
= NULL
;
1383 struct allocation_blob
*next
= blob
->next
;
1385 blob_free(blob
, desc
->chunking
);
1388 clear_data_range_alloc();