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
);
27 __DECLARE_ALLOCATOR(struct ptr_list
, rl_ptrlist
);
29 char *show_rl(struct range_list
*list
)
31 struct data_range
*tmp
;
36 full
[sizeof(full
) - 1] = '\0';
37 FOR_EACH_PTR(list
, tmp
) {
39 strncat(full
, ",", 254 - strlen(full
));
40 if (sval_cmp(tmp
->min
, tmp
->max
) == 0) {
41 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
44 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
45 strncat(full
, "-", 254 - strlen(full
));
46 strncat(full
, sval_to_str(tmp
->max
), 254 - strlen(full
));
47 } END_FOR_EACH_PTR(tmp
);
48 if (strlen(full
) == sizeof(full
) - 1)
49 full
[sizeof(full
) - 2] = '+';
50 return alloc_sname(full
);
53 void free_all_rl(void)
55 clear_rl_ptrlist_alloc();
58 static int sval_too_big(struct symbol
*type
, sval_t sval
)
60 if (type_bits(type
) >= 32 &&
61 type_bits(sval
.type
) <= type_bits(type
))
63 if (sval
.uvalue
<= ((1ULL << type_bits(type
)) - 1))
65 if (type_signed(sval
.type
)) {
66 if (type_unsigned(type
)) {
67 unsigned long long neg
= ~sval
.uvalue
;
68 if (neg
<= sval_type_max(type
).uvalue
)
71 if (sval
.value
< sval_type_min(type
).value
)
73 if (sval
.value
> sval_type_max(type
).value
)
77 if (sval
.uvalue
> sval_type_max(type
).uvalue
)
82 static void add_range_t(struct symbol
*type
, struct range_list
**rl
, sval_t min
, sval_t max
)
84 /* If we're just adding a number, cast it and add it */
85 if (sval_cmp(min
, max
) == 0) {
86 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
90 /* If the range is within the type range then add it */
91 if (sval_fits(type
, min
) && sval_fits(type
, max
)) {
92 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
97 * If the range we are adding has more bits than the range type then
98 * add the whole range type. Eg:
99 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
100 * This isn't totally the right thing to do. We could be more granular.
102 if (sval_too_big(type
, min
) || sval_too_big(type
, max
)) {
103 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
107 /* Cast negative values to high positive values */
108 if (sval_is_negative(min
) && type_unsigned(type
)) {
109 if (sval_is_positive(max
)) {
110 if (sval_too_high(type
, max
)) {
111 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
114 add_range(rl
, sval_type_val(type
, 0), sval_cast(type
, max
));
115 max
= sval_type_max(type
);
117 max
= sval_cast(type
, max
);
119 min
= sval_cast(type
, min
);
120 add_range(rl
, min
, max
);
123 /* Cast high positive numbers to negative */
124 if (sval_unsigned(max
) && sval_is_negative(sval_cast(type
, max
))) {
125 if (!sval_is_negative(sval_cast(type
, min
))) {
126 add_range(rl
, sval_cast(type
, min
), sval_type_max(type
));
127 min
= sval_type_min(type
);
129 min
= sval_cast(type
, min
);
131 max
= sval_cast(type
, max
);
132 add_range(rl
, min
, max
);
135 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
139 static int str_to_comparison_arg_helper(const char *str
,
140 struct expression
*call
, int *comparison
,
141 struct expression
**arg
, char **endp
)
144 char *c
= (char *)str
;
153 *comparison
= SPECIAL_LTE
;
158 } else if (*c
== '=') {
161 *comparison
= SPECIAL_EQUAL
;
162 } else if (*c
== '>') {
165 *comparison
= SPECIAL_GTE
;
170 } else if (*c
== '!') {
173 *comparison
= SPECIAL_NOTEQUAL
;
182 param
= strtoll(c
, &c
, 10);
184 c
++; /* skip the ']' character */
190 *arg
= get_argument_from_call_expr(call
->args
, param
);
193 if (*c
== '-' && *(c
+ 1) == '>') {
197 n
= snprintf(buf
, sizeof(buf
), "$%s", c
);
198 if (n
>= sizeof(buf
))
200 if (buf
[n
- 1] == ']')
202 *arg
= gen_expression_from_key(*arg
, buf
);
203 while (*c
&& *c
!= ']')
209 int str_to_comparison_arg(const char *str
, struct expression
*call
, int *comparison
, struct expression
**arg
)
218 return str_to_comparison_arg_helper(str
, call
, comparison
, arg
, NULL
);
221 static int get_val_from_key(int use_max
, struct symbol
*type
, char *c
, struct expression
*call
, char **endp
, sval_t
*sval
)
223 struct expression
*arg
;
228 ret
= sval_type_max(type
);
230 ret
= sval_type_min(type
);
232 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
)) {
237 if (use_max
&& get_implied_max(arg
, &tmp
)) {
239 if (comparison
== '<') {
241 ret
= sval_binop(ret
, '-', tmp
);
244 if (!use_max
&& get_implied_min(arg
, &tmp
)) {
246 if (comparison
== '>') {
248 ret
= sval_binop(ret
, '+', tmp
);
256 static sval_t
add_one(sval_t sval
)
262 static sval_t
sub_one(sval_t sval
)
268 void filter_by_comparison(struct range_list
**rl
, int comparison
, struct range_list
*right
)
270 struct range_list
*left_orig
= *rl
;
271 struct range_list
*right_orig
= right
;
272 struct range_list
*ret_rl
= *rl
;
273 struct symbol
*cast_type
;
276 cast_type
= rl_type(left_orig
);
277 if (sval_type_max(rl_type(left_orig
)).uvalue
< sval_type_max(rl_type(right_orig
)).uvalue
)
278 cast_type
= rl_type(right_orig
);
279 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
280 cast_type
= &int_ctype
;
282 min
= sval_type_min(cast_type
);
283 max
= sval_type_max(cast_type
);
284 left_orig
= cast_rl(cast_type
, left_orig
);
285 right_orig
= cast_rl(cast_type
, right_orig
);
287 switch (comparison
) {
289 case SPECIAL_UNSIGNED_LT
:
290 ret_rl
= remove_range(left_orig
, rl_max(right_orig
), max
);
293 case SPECIAL_UNSIGNED_LTE
:
294 if (!sval_is_max(rl_max(right_orig
)))
295 ret_rl
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
298 if (!sval_is_max(rl_max(right_orig
)))
299 ret_rl
= remove_range(ret_rl
, add_one(rl_max(right_orig
)), max
);
300 if (!sval_is_min(rl_min(right_orig
)))
301 ret_rl
= remove_range(ret_rl
, min
, sub_one(rl_min(right_orig
)));
304 case SPECIAL_UNSIGNED_GTE
:
305 if (!sval_is_min(rl_min(right_orig
)))
306 ret_rl
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
309 case SPECIAL_UNSIGNED_GT
:
310 ret_rl
= remove_range(left_orig
, min
, rl_min(right_orig
));
312 case SPECIAL_NOTEQUAL
:
313 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
314 ret_rl
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
317 sm_msg("internal error: unhandled comparison %s", show_special(comparison
));
321 *rl
= cast_rl(rl_type(*rl
), ret_rl
);
324 static struct range_list
*filter_by_comparison_call(char *c
, struct expression
*call
, char **endp
, struct range_list
*start_rl
)
327 struct expression
*arg
;
328 struct range_list
*casted_start
, *right_orig
;
331 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
))
334 if (!get_implied_rl(arg
, &right_orig
))
338 if (type_positive_bits(rl_type(start_rl
)) > type_positive_bits(type
))
339 type
= rl_type(start_rl
);
340 if (type_positive_bits(rl_type(right_orig
)) > type_positive_bits(type
))
341 type
= rl_type(right_orig
);
343 casted_start
= cast_rl(type
, start_rl
);
344 right_orig
= cast_rl(type
, right_orig
);
346 filter_by_comparison(&casted_start
, comparison
, right_orig
);
347 return cast_rl(rl_type(start_rl
), casted_start
);
350 static sval_t
parse_val(int use_max
, struct expression
*call
, struct symbol
*type
, char *c
, char **endp
)
355 if (!strncmp(start
, "max", 3)) {
356 ret
= sval_type_max(type
);
358 } else if (!strncmp(start
, "u64max", 6)) {
359 ret
= sval_type_val(type
, ULLONG_MAX
);
361 } else if (!strncmp(start
, "s64max", 6)) {
362 ret
= sval_type_val(type
, LLONG_MAX
);
364 } else if (!strncmp(start
, "u32max", 6)) {
365 ret
= sval_type_val(type
, UINT_MAX
);
367 } else if (!strncmp(start
, "s32max", 6)) {
368 ret
= sval_type_val(type
, INT_MAX
);
370 } else if (!strncmp(start
, "u16max", 6)) {
371 ret
= sval_type_val(type
, USHRT_MAX
);
373 } else if (!strncmp(start
, "s16max", 6)) {
374 ret
= sval_type_val(type
, SHRT_MAX
);
376 } else if (!strncmp(start
, "min", 3)) {
377 ret
= sval_type_min(type
);
379 } else if (!strncmp(start
, "s64min", 6)) {
380 ret
= sval_type_val(type
, LLONG_MIN
);
382 } else if (!strncmp(start
, "s32min", 6)) {
383 ret
= sval_type_val(type
, INT_MIN
);
385 } else if (!strncmp(start
, "s16min", 6)) {
386 ret
= sval_type_val(type
, SHRT_MIN
);
388 } else if (!strncmp(start
, "long_min", 8)) {
389 ret
= sval_type_val(type
, LONG_MIN
);
391 } else if (!strncmp(start
, "long_max", 8)) {
392 ret
= sval_type_val(type
, LONG_MAX
);
394 } else if (!strncmp(start
, "ulong_max", 9)) {
395 ret
= sval_type_val(type
, ULONG_MAX
);
397 } else if (!strncmp(start
, "ptr_max", 7)) {
398 ret
= sval_type_val(type
, valid_ptr_max
);
400 } else if (start
[0] == '[') {
401 /* this parses [==p0] comparisons */
402 get_val_from_key(1, type
, start
, call
, &c
, &ret
);
403 } else if (type_positive_bits(type
) == 64) {
404 ret
= sval_type_val(type
, strtoull(start
, &c
, 10));
406 ret
= sval_type_val(type
, strtoll(start
, &c
, 10));
412 static char *jump_to_call_math(char *value
)
416 while (*c
&& *c
!= '[')
422 if (*c
== '<' || *c
== '=' || *c
== '>' || *c
== '!')
428 static void str_to_rl_helper(struct expression
*call
, struct symbol
*type
, char *str
, char **endp
, struct range_list
**rl
)
430 struct range_list
*rl_tmp
= NULL
;
434 min
= sval_type_min(type
);
435 max
= sval_type_max(type
);
437 while (*c
!= '\0' && *c
!= '[') {
439 if (sval_cmp(min
, sval_type_min(type
)) != 0)
441 max
= sval_type_max(type
);
442 add_range_t(type
, &rl_tmp
, min
, max
);
447 min
= parse_val(0, call
, type
, c
, &c
);
448 if (!sval_fits(type
, min
))
449 min
= sval_type_min(type
);
453 if (*c
== '\0' || *c
== '[') {
454 add_range_t(type
, &rl_tmp
, min
, min
);
458 add_range_t(type
, &rl_tmp
, min
, min
);
463 min
= sval_type_max(type
);
467 sm_msg("debug XXX: trouble parsing %s c = %s", str
, c
);
473 max
= parse_val(1, call
, type
, c
, &c
);
474 if (!sval_fits(type
, max
))
475 max
= sval_type_max(type
);
477 max
= sval_type_max(type
);
480 add_range_t(type
, &rl_tmp
, min
, max
);
491 static void str_to_dinfo(struct expression
*call
, struct symbol
*type
, char *value
, struct data_info
*dinfo
)
493 struct range_list
*math_rl
;
496 struct range_list
*rl
= NULL
;
501 if (strcmp(value
, "empty") == 0)
504 if (strncmp(value
, "[==$", 4) == 0) {
505 struct expression
*arg
;
508 if (!str_to_comparison_arg(value
, call
, &comparison
, &arg
))
510 if (!get_implied_rl(arg
, &rl
))
515 str_to_rl_helper(call
, type
, value
, &c
, &rl
);
519 call_math
= jump_to_call_math(value
);
520 if (call_math
&& parse_call_math_rl(call
, call_math
, &math_rl
)) {
521 rl
= rl_intersection(rl
, math_rl
);
526 * For now if we already tried to handle the call math and couldn't
527 * figure it out then bail.
529 if (jump_to_call_math(c
) == c
+ 1)
532 rl
= filter_by_comparison_call(c
, call
, &c
, rl
);
535 rl
= cast_rl(type
, rl
);
536 dinfo
->value_ranges
= rl
;
539 void str_to_rl(struct symbol
*type
, char *value
, struct range_list
**rl
)
541 struct data_info dinfo
= {};
543 str_to_dinfo(NULL
, type
, value
, &dinfo
);
544 *rl
= dinfo
.value_ranges
;
547 void call_results_to_rl(struct expression
*expr
, struct symbol
*type
, char *value
, struct range_list
**rl
)
549 struct data_info dinfo
= {};
551 str_to_dinfo(strip_expr(expr
), type
, value
, &dinfo
);
552 *rl
= dinfo
.value_ranges
;
555 int is_whole_rl(struct range_list
*rl
)
557 struct data_range
*drange
;
559 if (ptr_list_empty(rl
))
561 drange
= first_ptr_list((struct ptr_list
*)rl
);
562 if (sval_is_min(drange
->min
) && sval_is_max(drange
->max
))
567 int is_whole_rl_non_zero(struct range_list
*rl
)
569 struct data_range
*drange
;
571 if (ptr_list_empty(rl
))
573 drange
= first_ptr_list((struct ptr_list
*)rl
);
574 if (sval_unsigned(drange
->min
) &&
575 drange
->min
.value
== 1 &&
576 sval_is_max(drange
->max
))
578 if (!sval_is_min(drange
->min
) || drange
->max
.value
!= -1)
580 drange
= last_ptr_list((struct ptr_list
*)rl
);
581 if (drange
->min
.value
!= 1 || !sval_is_max(drange
->max
))
586 sval_t
rl_min(struct range_list
*rl
)
588 struct data_range
*drange
;
591 ret
.type
= &llong_ctype
;
592 ret
.value
= LLONG_MIN
;
593 if (ptr_list_empty(rl
))
595 drange
= first_ptr_list((struct ptr_list
*)rl
);
599 sval_t
rl_max(struct range_list
*rl
)
601 struct data_range
*drange
;
604 ret
.type
= &llong_ctype
;
605 ret
.value
= LLONG_MAX
;
606 if (ptr_list_empty(rl
))
608 drange
= last_ptr_list((struct ptr_list
*)rl
);
612 int rl_to_sval(struct range_list
*rl
, sval_t
*sval
)
621 if (sval_cmp(min
, max
) != 0)
627 struct symbol
*rl_type(struct range_list
*rl
)
631 return rl_min(rl
).type
;
634 static struct data_range
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
636 struct data_range
*ret
;
639 ret
= __alloc_perm_data_range(0);
641 ret
= __alloc_data_range(0);
647 struct data_range
*alloc_range(sval_t min
, sval_t max
)
649 return alloc_range_helper_sval(min
, max
, 0);
652 struct data_range
*alloc_range_perm(sval_t min
, sval_t max
)
654 return alloc_range_helper_sval(min
, max
, 1);
657 struct range_list
*alloc_rl(sval_t min
, sval_t max
)
659 struct range_list
*rl
= NULL
;
661 if (sval_cmp(min
, max
) > 0)
662 return alloc_whole_rl(min
.type
);
664 add_range(&rl
, min
, max
);
668 struct range_list
*alloc_whole_rl(struct symbol
*type
)
670 if (!type
|| type_positive_bits(type
) < 0)
672 if (type
->type
== SYM_ARRAY
)
675 return alloc_rl(sval_type_min(type
), sval_type_max(type
));
678 extern int rl_ptrlist_hack
;
679 void add_range(struct range_list
**list
, sval_t min
, sval_t max
)
681 struct data_range
*tmp
;
682 struct data_range
*new = NULL
;
686 * There is at least on valid reason why the types might be confusing
687 * and that's when you have a void pointer and on some paths you treat
688 * it as a u8 pointer and on other paths you treat it as a u16 pointer.
689 * This case is hard to deal with.
691 * There are other cases where we probably should be more specific about
692 * the types than we are. For example, we end up merging a lot of ulong
693 * with pointers and I have not figured out why we do that.
695 * But this hack works for both cases, I think. We cast it to pointers
696 * or we use the bigger size.
699 if (*list
&& rl_type(*list
) != min
.type
) {
700 if (rl_type(*list
)->type
== SYM_PTR
) {
701 min
= sval_cast(rl_type(*list
), min
);
702 max
= sval_cast(rl_type(*list
), max
);
703 } else if (min
.type
->type
== SYM_PTR
) {
704 *list
= cast_rl(min
.type
, *list
);
705 } else if (type_bits(rl_type(*list
)) >= type_bits(min
.type
)) {
706 min
= sval_cast(rl_type(*list
), min
);
707 max
= sval_cast(rl_type(*list
), max
);
709 *list
= cast_rl(min
.type
, *list
);
713 if (sval_cmp(min
, max
) > 0) {
714 min
= sval_type_min(min
.type
);
715 max
= sval_type_max(min
.type
);
719 * FIXME: This has a problem merging a range_list like: min-0,3-max
720 * with a range like 1-2. You end up with min-2,3-max instead of
723 FOR_EACH_PTR(*list
, tmp
) {
725 /* Sometimes we overlap with more than one range
726 so we have to delete or modify the next range. */
727 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
728 /* join 2 ranges here */
730 DELETE_CURRENT_PTR(tmp
);
734 /* Doesn't overlap with the next one. */
735 if (sval_cmp(max
, tmp
->min
) < 0)
738 if (sval_cmp(max
, tmp
->max
) <= 0) {
739 /* Partially overlaps the next one. */
741 DELETE_CURRENT_PTR(tmp
);
744 /* Completely overlaps the next one. */
745 DELETE_CURRENT_PTR(tmp
);
746 /* there could be more ranges to delete */
750 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
751 /* join 2 ranges into a big range */
752 new = alloc_range(min
, tmp
->max
);
753 REPLACE_CURRENT_PTR(tmp
, new);
756 if (sval_cmp(max
, tmp
->min
) < 0) { /* new range entirely below */
757 new = alloc_range(min
, max
);
758 INSERT_CURRENT(new, tmp
);
761 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
762 if (sval_cmp(max
, tmp
->max
) < 0)
766 new = alloc_range(min
, max
);
767 REPLACE_CURRENT_PTR(tmp
, new);
772 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
774 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
776 new = alloc_range(min
, max
);
777 REPLACE_CURRENT_PTR(tmp
, new);
781 if (!sval_is_min(min
) && min
.value
- 1 == tmp
->max
.value
) {
782 /* join 2 ranges into a big range */
783 new = alloc_range(tmp
->min
, max
);
784 REPLACE_CURRENT_PTR(tmp
, new);
788 /* the new range is entirely above the existing ranges */
789 } END_FOR_EACH_PTR(tmp
);
792 new = alloc_range(min
, max
);
795 add_ptr_list(list
, new);
799 struct range_list
*clone_rl(struct range_list
*list
)
801 struct data_range
*tmp
;
802 struct range_list
*ret
= NULL
;
804 FOR_EACH_PTR(list
, tmp
) {
805 add_ptr_list(&ret
, tmp
);
806 } END_FOR_EACH_PTR(tmp
);
810 struct range_list
*clone_rl_permanent(struct range_list
*list
)
812 struct data_range
*tmp
;
813 struct data_range
*new;
814 struct range_list
*ret
= NULL
;
816 FOR_EACH_PTR(list
, tmp
) {
817 new = alloc_range_perm(tmp
->min
, tmp
->max
);
818 add_ptr_list(&ret
, new);
819 } END_FOR_EACH_PTR(tmp
);
823 struct range_list
*rl_union(struct range_list
*one
, struct range_list
*two
)
825 struct data_range
*tmp
;
826 struct range_list
*ret
= NULL
;
828 FOR_EACH_PTR(one
, tmp
) {
829 add_range(&ret
, tmp
->min
, tmp
->max
);
830 } END_FOR_EACH_PTR(tmp
);
831 FOR_EACH_PTR(two
, tmp
) {
832 add_range(&ret
, tmp
->min
, tmp
->max
);
833 } END_FOR_EACH_PTR(tmp
);
837 struct range_list
*remove_range(struct range_list
*list
, sval_t min
, sval_t max
)
839 struct data_range
*tmp
;
840 struct range_list
*ret
= NULL
;
845 min
= sval_cast(rl_type(list
), min
);
846 max
= sval_cast(rl_type(list
), max
);
847 if (sval_cmp(min
, max
) > 0) {
853 FOR_EACH_PTR(list
, tmp
) {
854 if (sval_cmp(tmp
->max
, min
) < 0) {
855 add_range(&ret
, tmp
->min
, tmp
->max
);
858 if (sval_cmp(tmp
->min
, max
) > 0) {
859 add_range(&ret
, tmp
->min
, tmp
->max
);
862 if (sval_cmp(tmp
->min
, min
) >= 0 && sval_cmp(tmp
->max
, max
) <= 0)
864 if (sval_cmp(tmp
->min
, min
) >= 0) {
866 add_range(&ret
, max
, tmp
->max
);
867 } else if (sval_cmp(tmp
->max
, max
) <= 0) {
869 add_range(&ret
, tmp
->min
, min
);
873 add_range(&ret
, tmp
->min
, min
);
874 add_range(&ret
, max
, tmp
->max
);
876 } END_FOR_EACH_PTR(tmp
);
880 int ranges_equiv(struct data_range
*one
, struct data_range
*two
)
886 if (sval_cmp(one
->min
, two
->min
) != 0)
888 if (sval_cmp(one
->max
, two
->max
) != 0)
893 int rl_equiv(struct range_list
*one
, struct range_list
*two
)
895 struct data_range
*one_range
;
896 struct data_range
*two_range
;
901 PREPARE_PTR_LIST(one
, one_range
);
902 PREPARE_PTR_LIST(two
, two_range
);
904 if (!one_range
&& !two_range
)
906 if (!ranges_equiv(one_range
, two_range
))
908 NEXT_PTR_LIST(one_range
);
909 NEXT_PTR_LIST(two_range
);
911 FINISH_PTR_LIST(two_range
);
912 FINISH_PTR_LIST(one_range
);
917 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
919 switch (comparison
) {
921 case SPECIAL_UNSIGNED_LT
:
922 if (sval_cmp(left
->min
, right
->max
) < 0)
925 case SPECIAL_UNSIGNED_LTE
:
927 if (sval_cmp(left
->min
, right
->max
) <= 0)
931 if (sval_cmp(left
->max
, right
->min
) < 0)
933 if (sval_cmp(left
->min
, right
->max
) > 0)
936 case SPECIAL_UNSIGNED_GTE
:
938 if (sval_cmp(left
->max
, right
->min
) >= 0)
942 case SPECIAL_UNSIGNED_GT
:
943 if (sval_cmp(left
->max
, right
->min
) > 0)
946 case SPECIAL_NOTEQUAL
:
947 if (sval_cmp(left
->min
, left
->max
) != 0)
949 if (sval_cmp(right
->min
, right
->max
) != 0)
951 if (sval_cmp(left
->min
, right
->min
) != 0)
955 sm_msg("unhandled comparison %d\n", comparison
);
961 int true_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
964 return true_comparison_range(var
, comparison
, val
);
966 return true_comparison_range(val
, comparison
, var
);
969 static int false_comparison_range_sval(struct data_range
*left
, int comparison
, struct data_range
*right
)
971 switch (comparison
) {
973 case SPECIAL_UNSIGNED_LT
:
974 if (sval_cmp(left
->max
, right
->min
) >= 0)
977 case SPECIAL_UNSIGNED_LTE
:
979 if (sval_cmp(left
->max
, right
->min
) > 0)
983 if (sval_cmp(left
->min
, left
->max
) != 0)
985 if (sval_cmp(right
->min
, right
->max
) != 0)
987 if (sval_cmp(left
->min
, right
->min
) != 0)
990 case SPECIAL_UNSIGNED_GTE
:
992 if (sval_cmp(left
->min
, right
->max
) < 0)
996 case SPECIAL_UNSIGNED_GT
:
997 if (sval_cmp(left
->min
, right
->max
) <= 0)
1000 case SPECIAL_NOTEQUAL
:
1001 if (sval_cmp(left
->max
, right
->min
) < 0)
1003 if (sval_cmp(left
->min
, right
->max
) > 0)
1007 sm_msg("unhandled comparison %d\n", comparison
);
1013 int false_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
1016 return false_comparison_range_sval(var
, comparison
, val
);
1018 return false_comparison_range_sval(val
, comparison
, var
);
1021 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
1023 struct range_list
*rl_left
, *rl_right
;
1024 struct data_range
*tmp_left
, *tmp_right
;
1025 struct symbol
*type
;
1027 if (!get_implied_rl(left
, &rl_left
))
1029 if (!get_implied_rl(right
, &rl_right
))
1032 type
= rl_type(rl_left
);
1033 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
1034 type
= rl_type(rl_right
);
1035 if (type_positive_bits(type
) < 31)
1038 rl_left
= cast_rl(type
, rl_left
);
1039 rl_right
= cast_rl(type
, rl_right
);
1041 FOR_EACH_PTR(rl_left
, tmp_left
) {
1042 FOR_EACH_PTR(rl_right
, tmp_right
) {
1043 if (true_comparison_range(tmp_left
, comparison
, tmp_right
))
1045 } END_FOR_EACH_PTR(tmp_right
);
1046 } END_FOR_EACH_PTR(tmp_left
);
1050 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
1052 struct range_list
*rl_left
, *rl_right
;
1053 struct data_range
*tmp_left
, *tmp_right
;
1054 struct symbol
*type
;
1056 if (!get_implied_rl(left
, &rl_left
))
1058 if (!get_implied_rl(right
, &rl_right
))
1061 type
= rl_type(rl_left
);
1062 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
1063 type
= rl_type(rl_right
);
1064 if (type_positive_bits(type
) < 31)
1067 rl_left
= cast_rl(type
, rl_left
);
1068 rl_right
= cast_rl(type
, rl_right
);
1070 FOR_EACH_PTR(rl_left
, tmp_left
) {
1071 FOR_EACH_PTR(rl_right
, tmp_right
) {
1072 if (false_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
1074 } END_FOR_EACH_PTR(tmp_right
);
1075 } END_FOR_EACH_PTR(tmp_left
);
1079 int possibly_true_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
1081 struct data_range
*left_tmp
, *right_tmp
;
1082 struct symbol
*type
;
1084 if (!left_ranges
|| !right_ranges
)
1087 type
= rl_type(left_ranges
);
1088 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
1089 type
= rl_type(right_ranges
);
1090 if (type_positive_bits(type
) < 31)
1093 left_ranges
= cast_rl(type
, left_ranges
);
1094 right_ranges
= cast_rl(type
, right_ranges
);
1096 FOR_EACH_PTR(left_ranges
, left_tmp
) {
1097 FOR_EACH_PTR(right_ranges
, right_tmp
) {
1098 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
1100 } END_FOR_EACH_PTR(right_tmp
);
1101 } END_FOR_EACH_PTR(left_tmp
);
1105 int possibly_false_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
1107 struct data_range
*left_tmp
, *right_tmp
;
1108 struct symbol
*type
;
1110 if (!left_ranges
|| !right_ranges
)
1113 type
= rl_type(left_ranges
);
1114 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
1115 type
= rl_type(right_ranges
);
1116 if (type_positive_bits(type
) < 31)
1119 left_ranges
= cast_rl(type
, left_ranges
);
1120 right_ranges
= cast_rl(type
, right_ranges
);
1122 FOR_EACH_PTR(left_ranges
, left_tmp
) {
1123 FOR_EACH_PTR(right_ranges
, right_tmp
) {
1124 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
1126 } END_FOR_EACH_PTR(right_tmp
);
1127 } END_FOR_EACH_PTR(left_tmp
);
1131 /* FIXME: the _rl here stands for right left so really it should be _lr */
1132 int possibly_true_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1135 return possibly_true_rl(a
, comparison
, b
);
1137 return possibly_true_rl(b
, comparison
, a
);
1140 int possibly_false_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1143 return possibly_false_rl(a
, comparison
, b
);
1145 return possibly_false_rl(b
, comparison
, a
);
1148 int rl_has_sval(struct range_list
*rl
, sval_t sval
)
1150 struct data_range
*tmp
;
1152 FOR_EACH_PTR(rl
, tmp
) {
1153 if (sval_cmp(tmp
->min
, sval
) <= 0 &&
1154 sval_cmp(tmp
->max
, sval
) >= 0)
1156 } END_FOR_EACH_PTR(tmp
);
1160 void tack_on(struct range_list
**list
, struct data_range
*drange
)
1162 add_ptr_list(list
, drange
);
1165 void push_rl(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
1167 add_ptr_list(rl_stack
, rl
);
1170 struct range_list
*pop_rl(struct range_list_stack
**rl_stack
)
1172 struct range_list
*rl
;
1174 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1175 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1179 struct range_list
*top_rl(struct range_list_stack
*rl_stack
)
1181 struct range_list
*rl
;
1183 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1187 void filter_top_rl(struct range_list_stack
**rl_stack
, struct range_list
*filter
)
1189 struct range_list
*rl
;
1191 rl
= pop_rl(rl_stack
);
1192 rl
= rl_filter(rl
, filter
);
1193 push_rl(rl_stack
, rl
);
1196 struct range_list
*rl_truncate_cast(struct symbol
*type
, struct range_list
*rl
)
1198 struct data_range
*tmp
;
1199 struct range_list
*ret
= NULL
;
1205 if (!type
|| type
== rl_type(rl
))
1208 FOR_EACH_PTR(rl
, tmp
) {
1211 if (type_bits(type
) < type_bits(rl_type(rl
))) {
1212 min
.uvalue
= tmp
->min
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1213 max
.uvalue
= tmp
->max
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1215 if (sval_cmp(min
, max
) > 0) {
1216 min
= sval_cast(type
, min
);
1217 max
= sval_cast(type
, max
);
1219 add_range_t(type
, &ret
, min
, max
);
1220 } END_FOR_EACH_PTR(tmp
);
1225 static int rl_is_sane(struct range_list
*rl
)
1227 struct data_range
*tmp
;
1228 struct symbol
*type
;
1231 FOR_EACH_PTR(rl
, tmp
) {
1232 if (!sval_fits(type
, tmp
->min
))
1234 if (!sval_fits(type
, tmp
->max
))
1236 if (sval_cmp(tmp
->min
, tmp
->max
) > 0)
1238 } END_FOR_EACH_PTR(tmp
);
1243 static int rl_type_consistent(struct range_list
*rl
)
1245 struct data_range
*tmp
;
1246 struct symbol
*type
;
1249 FOR_EACH_PTR(rl
, tmp
) {
1250 if (type
!= tmp
->min
.type
|| type
!= tmp
->max
.type
)
1252 } END_FOR_EACH_PTR(tmp
);
1256 static struct range_list
*cast_to_bool(struct range_list
*rl
)
1258 struct data_range
*tmp
;
1259 struct range_list
*ret
= NULL
;
1262 sval_t min
= { .type
= &bool_ctype
};
1263 sval_t max
= { .type
= &bool_ctype
};
1265 FOR_EACH_PTR(rl
, tmp
) {
1266 if (tmp
->min
.value
|| tmp
->max
.value
)
1268 if (sval_is_negative(tmp
->min
) &&
1269 sval_is_negative(tmp
->max
))
1271 if (tmp
->min
.value
== 0 ||
1272 tmp
->max
.value
== 0)
1274 if (sval_is_negative(tmp
->min
) &&
1277 } END_FOR_EACH_PTR(tmp
);
1284 add_range(&ret
, min
, max
);
1288 struct range_list
*cast_rl(struct symbol
*type
, struct range_list
*rl
)
1290 struct data_range
*tmp
;
1291 struct range_list
*ret
= NULL
;
1298 if (!rl_is_sane(rl
))
1299 return alloc_whole_rl(type
);
1300 if (type
== rl_type(rl
) && rl_type_consistent(rl
))
1303 if (type
== &bool_ctype
)
1304 return cast_to_bool(rl
);
1306 FOR_EACH_PTR(rl
, tmp
) {
1307 add_range_t(type
, &ret
, tmp
->min
, tmp
->max
);
1308 } END_FOR_EACH_PTR(tmp
);
1311 return alloc_whole_rl(type
);
1316 struct range_list
*rl_invert(struct range_list
*orig
)
1318 struct range_list
*ret
= NULL
;
1319 struct data_range
*tmp
;
1320 sval_t gap_min
, abs_max
, sval
;
1324 if (type_bits(rl_type(orig
)) < 0) /* void type mostly */
1327 gap_min
= sval_type_min(rl_min(orig
).type
);
1328 abs_max
= sval_type_max(rl_max(orig
).type
);
1330 FOR_EACH_PTR(orig
, tmp
) {
1331 if (sval_cmp(tmp
->min
, gap_min
) > 0) {
1332 sval
= sval_type_val(tmp
->min
.type
, tmp
->min
.value
- 1);
1333 add_range(&ret
, gap_min
, sval
);
1335 if (sval_cmp(tmp
->max
, abs_max
) == 0)
1337 gap_min
= sval_type_val(tmp
->max
.type
, tmp
->max
.value
+ 1);
1338 } END_FOR_EACH_PTR(tmp
);
1340 if (sval_cmp(gap_min
, abs_max
) <= 0)
1341 add_range(&ret
, gap_min
, abs_max
);
1346 struct range_list
*rl_filter(struct range_list
*rl
, struct range_list
*filter
)
1348 struct data_range
*tmp
;
1350 FOR_EACH_PTR(filter
, tmp
) {
1351 rl
= remove_range(rl
, tmp
->min
, tmp
->max
);
1352 } END_FOR_EACH_PTR(tmp
);
1357 struct range_list
*rl_intersection(struct range_list
*one
, struct range_list
*two
)
1359 struct range_list
*one_orig
;
1360 struct range_list
*two_orig
;
1361 struct range_list
*ret
;
1362 struct symbol
*ret_type
;
1363 struct symbol
*small_type
;
1364 struct symbol
*large_type
;
1374 ret_type
= rl_type(one
);
1375 small_type
= rl_type(one
);
1376 large_type
= rl_type(two
);
1378 if (type_bits(rl_type(two
)) < type_bits(small_type
)) {
1379 small_type
= rl_type(two
);
1380 large_type
= rl_type(one
);
1383 one
= cast_rl(large_type
, one
);
1384 two
= cast_rl(large_type
, two
);
1387 one
= rl_invert(one
);
1388 two
= rl_invert(two
);
1390 ret
= rl_filter(ret
, one
);
1391 ret
= rl_filter(ret
, two
);
1393 one
= cast_rl(small_type
, one_orig
);
1394 two
= cast_rl(small_type
, two_orig
);
1396 one
= rl_invert(one
);
1397 two
= rl_invert(two
);
1399 ret
= cast_rl(small_type
, ret
);
1400 ret
= rl_filter(ret
, one
);
1401 ret
= rl_filter(ret
, two
);
1403 return cast_rl(ret_type
, ret
);
1406 static struct range_list
*handle_mod_rl(struct range_list
*left
, struct range_list
*right
)
1411 max
= rl_max(right
);
1412 if (sval_is_max(max
))
1417 if (sval_is_negative(max
))
1419 if (sval_cmp(rl_max(left
), max
) < 0)
1423 return alloc_rl(zero
, max
);
1426 static struct range_list
*get_neg_rl(struct range_list
*rl
)
1428 struct data_range
*tmp
;
1429 struct data_range
*new;
1430 struct range_list
*ret
= NULL
;
1434 if (sval_is_positive(rl_min(rl
)))
1437 FOR_EACH_PTR(rl
, tmp
) {
1438 if (sval_is_positive(tmp
->min
))
1440 if (sval_is_positive(tmp
->max
)) {
1441 new = alloc_range(tmp
->min
, tmp
->max
);
1442 new->max
.value
= -1;
1443 add_range(&ret
, new->min
, new->max
);
1446 add_range(&ret
, tmp
->min
, tmp
->max
);
1447 } END_FOR_EACH_PTR(tmp
);
1452 static struct range_list
*get_pos_rl(struct range_list
*rl
)
1454 struct data_range
*tmp
;
1455 struct data_range
*new;
1456 struct range_list
*ret
= NULL
;
1460 if (sval_is_negative(rl_max(rl
)))
1463 FOR_EACH_PTR(rl
, tmp
) {
1464 if (sval_is_negative(tmp
->max
))
1466 if (sval_is_positive(tmp
->min
)) {
1467 add_range(&ret
, tmp
->min
, tmp
->max
);
1470 new = alloc_range(tmp
->min
, tmp
->max
);
1472 add_range(&ret
, new->min
, new->max
);
1473 } END_FOR_EACH_PTR(tmp
);
1478 static struct range_list
*divide_rl_helper(struct range_list
*left
, struct range_list
*right
)
1480 sval_t right_min
, right_max
;
1483 if (!left
|| !right
)
1486 /* let's assume we never divide by zero */
1487 right_min
= rl_min(right
);
1488 right_max
= rl_max(right
);
1489 if (right_min
.value
== 0 && right_max
.value
== 0)
1491 if (right_min
.value
== 0)
1492 right_min
.value
= 1;
1493 if (right_max
.value
== 0)
1494 right_max
.value
= -1;
1496 max
= sval_binop(rl_max(left
), '/', right_min
);
1497 min
= sval_binop(rl_min(left
), '/', right_max
);
1499 return alloc_rl(min
, max
);
1502 static struct range_list
*handle_divide_rl(struct range_list
*left
, struct range_list
*right
)
1504 struct range_list
*left_neg
, *left_pos
, *right_neg
, *right_pos
;
1505 struct range_list
*neg_neg
, *neg_pos
, *pos_neg
, *pos_pos
;
1506 struct range_list
*ret
;
1508 if (is_whole_rl(right
))
1511 left_neg
= get_neg_rl(left
);
1512 left_pos
= get_pos_rl(left
);
1513 right_neg
= get_neg_rl(right
);
1514 right_pos
= get_pos_rl(right
);
1516 neg_neg
= divide_rl_helper(left_neg
, right_neg
);
1517 neg_pos
= divide_rl_helper(left_neg
, right_pos
);
1518 pos_neg
= divide_rl_helper(left_pos
, right_neg
);
1519 pos_pos
= divide_rl_helper(left_pos
, right_pos
);
1521 ret
= rl_union(neg_neg
, neg_pos
);
1522 ret
= rl_union(ret
, pos_neg
);
1523 return rl_union(ret
, pos_pos
);
1526 static struct range_list
*handle_add_mult_rl(struct range_list
*left
, int op
, struct range_list
*right
)
1530 if (sval_binop_overflows(rl_min(left
), op
, rl_min(right
)))
1532 min
= sval_binop(rl_min(left
), op
, rl_min(right
));
1534 if (sval_binop_overflows(rl_max(left
), op
, rl_max(right
)))
1536 max
= sval_binop(rl_max(left
), op
, rl_max(right
));
1538 return alloc_rl(min
, max
);
1541 static struct range_list
*handle_sub_rl(struct range_list
*left_orig
, struct range_list
*right_orig
)
1543 struct range_list
*left_rl
, *right_rl
;
1544 struct symbol
*type
;
1546 sval_t min_ll
, max_ll
, res_ll
;
1549 /* TODO: These things should totally be using dranges where possible */
1551 if (!left_orig
|| !right_orig
)
1555 if (type_positive_bits(rl_type(left_orig
)) > type_positive_bits(type
))
1556 type
= rl_type(left_orig
);
1557 if (type_positive_bits(rl_type(right_orig
)) > type_positive_bits(type
))
1558 type
= rl_type(right_orig
);
1560 left_rl
= cast_rl(type
, left_orig
);
1561 right_rl
= cast_rl(type
, right_orig
);
1563 max
= rl_max(left_rl
);
1564 min
= sval_type_min(type
);
1566 min_ll
= rl_min(left_rl
);
1567 min_ll
.type
= &llong_ctype
;
1568 max_ll
= rl_max(right_rl
);
1569 max_ll
.type
= &llong_ctype
;
1571 res_ll
.value
= min_ll
.value
- max_ll
.value
;
1573 if (!sval_binop_overflows(rl_min(left_rl
), '-', rl_max(right_rl
))) {
1574 tmp
= sval_binop(rl_min(left_rl
), '-', rl_max(right_rl
));
1575 if (sval_cmp(tmp
, min
) > 0)
1577 } else if (type_positive_bits(type
) < 63 &&
1578 !sval_binop_overflows(min_ll
, '-', max_ll
) &&
1579 (min
.value
!= 0 && sval_cmp(res_ll
, min
) >= 0)) {
1580 struct range_list
*left_casted
, *right_casted
, *result
;
1582 left_casted
= cast_rl(&llong_ctype
, left_orig
);
1583 right_casted
= cast_rl(&llong_ctype
, right_orig
);
1584 result
= handle_sub_rl(left_casted
, right_casted
);
1585 return cast_rl(type
, result
);
1588 if (!sval_is_max(rl_max(left_rl
))) {
1589 tmp
= sval_binop(rl_max(left_rl
), '-', rl_min(right_rl
));
1590 if (sval_cmp(tmp
, max
) < 0)
1594 if (sval_is_min(min
) && sval_is_max(max
))
1597 return alloc_rl(min
, max
);
1600 static unsigned long long rl_bits_always_set(struct range_list
*rl
)
1602 return sval_fls_mask(rl_min(rl
));
1605 static unsigned long long rl_bits_maybe_set(struct range_list
*rl
)
1607 return sval_fls_mask(rl_max(rl
));
1610 static struct range_list
*handle_OR_rl(struct range_list
*left
, struct range_list
*right
)
1612 unsigned long long left_min
, left_max
, right_min
, right_max
;
1616 if ((rl_to_sval(left
, &sval
) || rl_to_sval(right
, &sval
)) &&
1617 !sval_binop_overflows(rl_max(left
), '+', rl_max(right
)))
1618 return rl_binop(left
, '+', right
);
1620 left_min
= rl_bits_always_set(left
);
1621 left_max
= rl_bits_maybe_set(left
);
1622 right_min
= rl_bits_always_set(right
);
1623 right_max
= rl_bits_maybe_set(right
);
1625 min
.type
= max
.type
= &ullong_ctype
;
1626 min
.uvalue
= left_min
| right_min
;
1627 max
.uvalue
= left_max
| right_max
;
1629 return cast_rl(rl_type(left
), alloc_rl(min
, max
));
1632 static struct range_list
*handle_XOR_rl(struct range_list
*left
, struct range_list
*right
)
1634 unsigned long long left_set
, left_maybe
;
1635 unsigned long long right_set
, right_maybe
;
1638 left_set
= rl_bits_always_set(left
);
1639 left_maybe
= rl_bits_maybe_set(left
);
1641 right_set
= rl_bits_always_set(right
);
1642 right_maybe
= rl_bits_maybe_set(right
);
1644 zero
= max
= rl_min(left
);
1646 max
.uvalue
= fls_mask((left_maybe
| right_maybe
) ^ (left_set
& right_set
));
1648 return cast_rl(rl_type(left
), alloc_rl(zero
, max
));
1651 static struct range_list
*handle_AND_rl(struct range_list
*left
, struct range_list
*right
)
1653 unsigned long long left_set
, left_maybe
;
1654 unsigned long long right_set
, right_maybe
;
1659 left_set
= rl_bits_always_set(left
);
1660 left_maybe
= rl_bits_maybe_set(left
);
1662 right_set
= rl_bits_always_set(right
);
1663 right_maybe
= rl_bits_maybe_set(right
);
1665 zero
= max
= rl_min(left
);
1667 max
.uvalue
= fls_mask((left_maybe
| right_maybe
) ^ (left_set
& right_set
));
1669 return cast_rl(rl_type(left
), alloc_rl(zero
, max
));
1672 struct range_list
*rl_binop(struct range_list
*left
, int op
, struct range_list
*right
)
1674 struct symbol
*cast_type
;
1675 sval_t left_sval
, right_sval
;
1676 struct range_list
*ret
= NULL
;
1678 cast_type
= rl_type(left
);
1679 if (sval_type_max(rl_type(left
)).uvalue
< sval_type_max(rl_type(right
)).uvalue
)
1680 cast_type
= rl_type(right
);
1681 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
1682 cast_type
= &int_ctype
;
1684 left
= cast_rl(cast_type
, left
);
1685 right
= cast_rl(cast_type
, right
);
1687 if (!left
&& !right
)
1690 if (rl_to_sval(left
, &left_sval
) && rl_to_sval(right
, &right_sval
)) {
1691 sval_t val
= sval_binop(left_sval
, op
, right_sval
);
1692 return alloc_rl(val
, val
);
1697 ret
= handle_mod_rl(left
, right
);
1700 ret
= handle_divide_rl(left
, right
);
1704 ret
= handle_add_mult_rl(left
, op
, right
);
1707 ret
= handle_OR_rl(left
, right
);
1710 ret
= handle_XOR_rl(left
, right
);
1713 ret
= handle_AND_rl(left
, right
);
1716 ret
= handle_sub_rl(left
, right
);
1718 /* FIXME: Do the rest as well */
1719 case SPECIAL_RIGHTSHIFT
:
1720 case SPECIAL_LEFTSHIFT
:
1727 void free_data_info_allocs(void)
1729 struct allocator_struct
*desc
= &data_info_allocator
;
1730 struct allocation_blob
*blob
= desc
->blobs
;
1736 desc
->allocations
= 0;
1737 desc
->total_bytes
= 0;
1738 desc
->useful_bytes
= 0;
1739 desc
->freelist
= NULL
;
1741 struct allocation_blob
*next
= blob
->next
;
1742 blob_free(blob
, desc
->chunking
);
1745 clear_data_range_alloc();
1748 void split_comparison_rl(struct range_list
*left_orig
, int op
, struct range_list
*right_orig
,
1749 struct range_list
**left_true_rl
, struct range_list
**left_false_rl
,
1750 struct range_list
**right_true_rl
, struct range_list
**right_false_rl
)
1752 struct range_list
*left_true
, *left_false
;
1753 struct range_list
*right_true
, *right_false
;
1756 min
= sval_type_min(rl_type(left_orig
));
1757 max
= sval_type_max(rl_type(left_orig
));
1759 left_true
= clone_rl(left_orig
);
1760 left_false
= clone_rl(left_orig
);
1761 right_true
= clone_rl(right_orig
);
1762 right_false
= clone_rl(right_orig
);
1766 case SPECIAL_UNSIGNED_LT
:
1767 left_true
= remove_range(left_orig
, rl_max(right_orig
), max
);
1768 if (!sval_is_min(rl_min(right_orig
))) {
1769 left_false
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1772 right_true
= remove_range(right_orig
, min
, rl_min(left_orig
));
1773 if (!sval_is_max(rl_max(left_orig
)))
1774 right_false
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1776 case SPECIAL_UNSIGNED_LTE
:
1778 if (!sval_is_max(rl_max(right_orig
)))
1779 left_true
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1780 left_false
= remove_range(left_orig
, min
, rl_min(right_orig
));
1782 if (!sval_is_min(rl_min(left_orig
)))
1783 right_true
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1784 right_false
= remove_range(right_orig
, rl_max(left_orig
), max
);
1786 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1787 left_false
= remove_range(left_false
, rl_min(left_orig
), rl_min(left_orig
));
1788 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1789 right_false
= remove_range(right_false
, rl_max(left_orig
), rl_max(left_orig
));
1792 left_true
= rl_intersection(left_orig
, right_orig
);
1793 right_true
= clone_rl(left_true
);
1795 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1796 left_false
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1797 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1798 right_false
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1800 case SPECIAL_UNSIGNED_GTE
:
1802 if (!sval_is_min(rl_min(right_orig
)))
1803 left_true
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1804 left_false
= remove_range(left_orig
, rl_max(right_orig
), max
);
1806 if (!sval_is_max(rl_max(left_orig
)))
1807 right_true
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1808 right_false
= remove_range(right_orig
, min
, rl_min(left_orig
));
1810 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1811 right_false
= remove_range(right_false
, rl_min(left_orig
), rl_min(left_orig
));
1812 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1813 left_false
= remove_range(left_false
, rl_max(left_orig
), rl_max(left_orig
));
1816 case SPECIAL_UNSIGNED_GT
:
1817 left_true
= remove_range(left_orig
, min
, rl_min(right_orig
));
1818 if (!sval_is_max(rl_max(right_orig
)))
1819 left_false
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1821 right_true
= remove_range(right_orig
, rl_max(left_orig
), max
);
1822 if (!sval_is_min(rl_min(left_orig
)))
1823 right_false
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1825 case SPECIAL_NOTEQUAL
:
1826 left_false
= rl_intersection(left_orig
, right_orig
);
1827 right_false
= clone_rl(left_false
);
1829 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1830 left_true
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1831 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1832 right_true
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1835 sm_msg("internal error: unhandled comparison %d", op
);
1840 *left_true_rl
= left_true
;
1841 *left_false_rl
= left_false
;
1843 if (right_true_rl
) {
1844 *right_true_rl
= right_true
;
1845 *right_false_rl
= right_false
;