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
) >= 32 &&
53 type_bits(sval
.type
) <= type_bits(type
))
55 if (sval
.uvalue
<= ((1ULL << type_bits(type
)) - 1))
57 if (type_signed(sval
.type
)) {
58 if (sval
.value
< sval_type_min(type
).value
)
60 if (sval
.value
> sval_type_max(type
).value
)
64 if (sval
.uvalue
> sval_type_max(type
).uvalue
)
69 static void add_range_t(struct symbol
*type
, struct range_list
**rl
, sval_t min
, sval_t max
)
71 /* If we're just adding a number, cast it and add it */
72 if (sval_cmp(min
, max
) == 0) {
73 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
77 /* If the range is within the type range then add it */
78 if (sval_fits(type
, min
) && sval_fits(type
, max
)) {
79 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
84 * If the range we are adding has more bits than the range type then
85 * add the whole range type. Eg:
86 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
87 * This isn't totally the right thing to do. We could be more granular.
89 if (sval_too_big(type
, min
) || sval_too_big(type
, max
)) {
90 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
94 /* Cast negative values to high positive values */
95 if (sval_is_negative(min
) && type_unsigned(type
)) {
96 if (sval_is_positive(max
)) {
97 if (sval_too_high(type
, max
)) {
98 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
101 add_range(rl
, sval_type_val(type
, 0), sval_cast(type
, max
));
102 max
= sval_type_max(type
);
104 max
= sval_cast(type
, max
);
106 min
= sval_cast(type
, min
);
107 add_range(rl
, min
, max
);
110 /* Cast high positive numbers to negative */
111 if (sval_unsigned(max
) && sval_is_negative(sval_cast(type
, max
))) {
112 if (!sval_is_negative(sval_cast(type
, min
))) {
113 add_range(rl
, sval_cast(type
, min
), sval_type_max(type
));
114 min
= sval_type_min(type
);
116 min
= sval_cast(type
, min
);
118 max
= sval_cast(type
, max
);
119 add_range(rl
, min
, max
);
122 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
126 static int str_to_comparison_arg_helper(const char *str
,
127 struct expression
*call
, int *comparison
,
128 struct expression
**arg
, char **endp
)
131 char *c
= (char *)str
;
140 *comparison
= SPECIAL_LTE
;
145 } else if (*c
== '=') {
148 *comparison
= SPECIAL_EQUAL
;
149 } else if (*c
== '>') {
152 *comparison
= SPECIAL_GTE
;
157 } else if (*c
== '!') {
160 *comparison
= SPECIAL_NOTEQUAL
;
169 param
= strtoll(c
, &c
, 10);
170 c
++; /* skip the ']' character */
176 *arg
= get_argument_from_call_expr(call
->args
, param
);
182 int str_to_comparison_arg(const char *str
, struct expression
*call
, int *comparison
, struct expression
**arg
)
191 return str_to_comparison_arg_helper(str
, call
, comparison
, arg
, NULL
);
194 static int get_val_from_key(int use_max
, struct symbol
*type
, char *c
, struct expression
*call
, char **endp
, sval_t
*sval
)
196 struct expression
*arg
;
201 ret
= sval_type_max(type
);
203 ret
= sval_type_min(type
);
205 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
)) {
210 if (use_max
&& get_implied_max(arg
, &tmp
)) {
212 if (comparison
== '<') {
214 ret
= sval_binop(ret
, '-', tmp
);
217 if (!use_max
&& get_implied_min(arg
, &tmp
)) {
219 if (comparison
== '>') {
221 ret
= sval_binop(ret
, '+', tmp
);
229 static sval_t
add_one(sval_t sval
)
235 static sval_t
sub_one(sval_t sval
)
241 void filter_by_comparison(struct range_list
**rl
, int comparison
, struct range_list
*right
)
243 struct range_list
*left_orig
= *rl
;
244 struct range_list
*right_orig
= right
;
245 struct range_list
*ret_rl
= *rl
;
246 struct symbol
*cast_type
;
249 cast_type
= rl_type(left_orig
);
250 if (sval_type_max(rl_type(left_orig
)).uvalue
< sval_type_max(rl_type(right_orig
)).uvalue
)
251 cast_type
= rl_type(right_orig
);
252 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
253 cast_type
= &int_ctype
;
255 min
= sval_type_min(cast_type
);
256 max
= sval_type_max(cast_type
);
257 left_orig
= cast_rl(cast_type
, left_orig
);
258 right_orig
= cast_rl(cast_type
, right_orig
);
260 switch (comparison
) {
262 case SPECIAL_UNSIGNED_LT
:
263 ret_rl
= remove_range(left_orig
, rl_max(right_orig
), max
);
266 case SPECIAL_UNSIGNED_LTE
:
267 if (!sval_is_max(rl_max(right_orig
)))
268 ret_rl
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
271 if (!sval_is_max(rl_max(right_orig
)))
272 ret_rl
= remove_range(ret_rl
, add_one(rl_max(right_orig
)), max
);
273 if (!sval_is_min(rl_min(right_orig
)))
274 ret_rl
= remove_range(ret_rl
, min
, sub_one(rl_min(right_orig
)));
277 case SPECIAL_UNSIGNED_GTE
:
278 if (!sval_is_min(rl_min(right_orig
)))
279 ret_rl
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
282 case SPECIAL_UNSIGNED_GT
:
283 ret_rl
= remove_range(left_orig
, min
, rl_min(right_orig
));
285 case SPECIAL_NOTEQUAL
:
286 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
287 ret_rl
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
290 sm_msg("internal error: unhandled comparison %s", show_special(comparison
));
294 *rl
= cast_rl(rl_type(*rl
), ret_rl
);
297 static struct range_list
*filter_by_comparison_call(char *c
, struct expression
*call
, char **endp
, struct range_list
*start_rl
)
299 struct expression
*arg
;
300 struct range_list
*right_orig
;
303 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
))
306 if (!get_implied_rl(arg
, &right_orig
))
309 if (rl_type(start_rl
) == &int_ctype
&&
310 sval_is_negative(rl_min(start_rl
)) &&
311 type_unsigned(rl_type(right_orig
)))
312 right_orig
= cast_rl(&int_ctype
, right_orig
);
314 filter_by_comparison(&start_rl
, comparison
, right_orig
);
318 static sval_t
parse_val(int use_max
, struct expression
*call
, struct symbol
*type
, char *c
, char **endp
)
323 if (!strncmp(start
, "max", 3)) {
324 ret
= sval_type_max(type
);
326 } else if (!strncmp(start
, "u64max", 6)) {
327 ret
= sval_type_val(type
, ULLONG_MAX
);
329 } else if (!strncmp(start
, "s64max", 6)) {
330 ret
= sval_type_val(type
, LLONG_MAX
);
332 } else if (!strncmp(start
, "u32max", 6)) {
333 ret
= sval_type_val(type
, UINT_MAX
);
335 } else if (!strncmp(start
, "s32max", 6)) {
336 ret
= sval_type_val(type
, INT_MAX
);
338 } else if (!strncmp(start
, "u16max", 6)) {
339 ret
= sval_type_val(type
, USHRT_MAX
);
341 } else if (!strncmp(start
, "s16max", 6)) {
342 ret
= sval_type_val(type
, SHRT_MAX
);
344 } else if (!strncmp(start
, "min", 3)) {
345 ret
= sval_type_min(type
);
347 } else if (!strncmp(start
, "s64min", 6)) {
348 ret
= sval_type_val(type
, LLONG_MIN
);
350 } else if (!strncmp(start
, "s32min", 6)) {
351 ret
= sval_type_val(type
, INT_MIN
);
353 } else if (!strncmp(start
, "s16min", 6)) {
354 ret
= sval_type_val(type
, SHRT_MIN
);
356 } else if (!strncmp(start
, "long_min", 8)) {
357 ret
= sval_type_val(type
, LONG_MIN
);
359 } else if (!strncmp(start
, "long_max", 8)) {
360 ret
= sval_type_val(type
, LONG_MAX
);
362 } else if (!strncmp(start
, "ulong_max", 9)) {
363 ret
= sval_type_val(type
, ULONG_MAX
);
365 } else if (!strncmp(start
, "ptr_max", 7)) {
366 ret
= sval_type_val(type
, valid_ptr_max
);
368 } else if (start
[0] == '[') {
369 /* this parses [==p0] comparisons */
370 get_val_from_key(1, type
, start
, call
, &c
, &ret
);
371 } else if (type_positive_bits(type
) == 64) {
372 ret
= sval_type_val(type
, strtoull(start
, &c
, 10));
374 ret
= sval_type_val(type
, strtoll(start
, &c
, 10));
380 static char *jump_to_call_math(char *value
)
384 while (*c
&& *c
!= '[')
390 if (*c
== '<' || *c
== '=' || *c
== '>' || *c
== '!')
396 static void str_to_rl_helper(struct expression
*call
, struct symbol
*type
, char *str
, char **endp
, struct range_list
**rl
)
398 struct range_list
*rl_tmp
= NULL
;
402 min
= sval_type_min(type
);
403 max
= sval_type_max(type
);
405 while (*c
!= '\0' && *c
!= '[') {
408 min
= parse_val(0, call
, type
, c
, &c
);
412 if (*c
== '\0' || *c
== '[') {
413 add_range_t(type
, &rl_tmp
, min
, min
);
417 add_range_t(type
, &rl_tmp
, min
, min
);
422 sm_msg("debug XXX: trouble parsing %s c = %s", str
, c
);
428 max
= parse_val(1, call
, type
, c
, &c
);
429 add_range_t(type
, &rl_tmp
, min
, max
);
440 static void str_to_dinfo(struct expression
*call
, struct symbol
*type
, char *value
, struct data_info
*dinfo
)
442 struct range_list
*math_rl
;
445 struct range_list
*rl
= NULL
;
450 if (strcmp(value
, "empty") == 0)
453 if (strncmp(value
, "[==$", 4) == 0) {
454 struct expression
*arg
;
457 if (!str_to_comparison_arg(value
, call
, &comparison
, &arg
))
459 if (!get_implied_rl(arg
, &rl
))
464 str_to_rl_helper(call
, type
, value
, &c
, &rl
);
468 call_math
= jump_to_call_math(value
);
469 if (call_math
&& parse_call_math_rl(call
, call_math
, &math_rl
)) {
470 rl
= rl_intersection(rl
, math_rl
);
475 * For now if we already tried to handle the call math and couldn't
476 * figure it out then bail.
478 if (jump_to_call_math(c
) == c
+ 1)
481 rl
= filter_by_comparison_call(c
, call
, &c
, rl
);
484 rl
= cast_rl(type
, rl
);
485 dinfo
->value_ranges
= rl
;
488 void str_to_rl(struct symbol
*type
, char *value
, struct range_list
**rl
)
490 struct data_info dinfo
= {};
492 str_to_dinfo(NULL
, type
, value
, &dinfo
);
493 *rl
= dinfo
.value_ranges
;
496 void call_results_to_rl(struct expression
*expr
, struct symbol
*type
, char *value
, struct range_list
**rl
)
498 struct data_info dinfo
= {};
500 str_to_dinfo(strip_expr(expr
), type
, value
, &dinfo
);
501 *rl
= dinfo
.value_ranges
;
504 int is_whole_rl(struct range_list
*rl
)
506 struct data_range
*drange
;
508 if (ptr_list_empty(rl
))
510 drange
= first_ptr_list((struct ptr_list
*)rl
);
511 if (sval_is_min(drange
->min
) && sval_is_max(drange
->max
))
516 int is_whole_rl_non_zero(struct range_list
*rl
)
518 struct data_range
*drange
;
520 if (ptr_list_empty(rl
))
522 drange
= first_ptr_list((struct ptr_list
*)rl
);
523 if (sval_unsigned(drange
->min
) &&
524 drange
->min
.value
== 1 &&
525 sval_is_max(drange
->max
))
527 if (!sval_is_min(drange
->min
) || drange
->max
.value
!= -1)
529 drange
= last_ptr_list((struct ptr_list
*)rl
);
530 if (drange
->min
.value
!= 1 || !sval_is_max(drange
->max
))
535 sval_t
rl_min(struct range_list
*rl
)
537 struct data_range
*drange
;
540 ret
.type
= &llong_ctype
;
541 ret
.value
= LLONG_MIN
;
542 if (ptr_list_empty(rl
))
544 drange
= first_ptr_list((struct ptr_list
*)rl
);
548 sval_t
rl_max(struct range_list
*rl
)
550 struct data_range
*drange
;
553 ret
.type
= &llong_ctype
;
554 ret
.value
= LLONG_MAX
;
555 if (ptr_list_empty(rl
))
557 drange
= last_ptr_list((struct ptr_list
*)rl
);
561 int rl_to_sval(struct range_list
*rl
, sval_t
*sval
)
570 if (sval_cmp(min
, max
) != 0)
576 struct symbol
*rl_type(struct range_list
*rl
)
580 return rl_min(rl
).type
;
583 static struct data_range
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
585 struct data_range
*ret
;
588 ret
= __alloc_perm_data_range(0);
590 ret
= __alloc_data_range(0);
596 struct data_range
*alloc_range(sval_t min
, sval_t max
)
598 return alloc_range_helper_sval(min
, max
, 0);
601 struct data_range
*alloc_range_perm(sval_t min
, sval_t max
)
603 return alloc_range_helper_sval(min
, max
, 1);
606 struct range_list
*alloc_rl(sval_t min
, sval_t max
)
608 struct range_list
*rl
= NULL
;
610 if (sval_cmp(min
, max
) > 0)
611 return alloc_whole_rl(min
.type
);
613 add_range(&rl
, min
, max
);
617 struct range_list
*alloc_whole_rl(struct symbol
*type
)
619 if (!type
|| type_positive_bits(type
) < 0)
621 if (type
->type
== SYM_ARRAY
)
624 return alloc_rl(sval_type_min(type
), sval_type_max(type
));
627 void add_range(struct range_list
**list
, sval_t min
, sval_t max
)
629 struct data_range
*tmp
;
630 struct data_range
*new = NULL
;
634 * There is at least on valid reason why the types might be confusing
635 * and that's when you have a void pointer and on some paths you treat
636 * it as a u8 pointer and on other paths you treat it as a u16 pointer.
637 * This case is hard to deal with.
639 * There are other cases where we probably should be more specific about
640 * the types than we are. For example, we end up merging a lot of ulong
641 * with pointers and I have not figured out why we do that.
643 * But this hack works for both cases, I think. We cast it to pointers
644 * or we use the bigger size.
647 if (*list
&& rl_type(*list
) != min
.type
) {
648 if (rl_type(*list
)->type
== SYM_PTR
) {
649 min
= sval_cast(rl_type(*list
), min
);
650 max
= sval_cast(rl_type(*list
), max
);
651 } else if (min
.type
->type
== SYM_PTR
) {
652 *list
= cast_rl(min
.type
, *list
);
653 } else if (type_bits(rl_type(*list
)) >= type_bits(min
.type
)) {
654 min
= sval_cast(rl_type(*list
), min
);
655 max
= sval_cast(rl_type(*list
), max
);
657 *list
= cast_rl(min
.type
, *list
);
661 if (sval_cmp(min
, max
) > 0) {
662 min
= sval_type_min(min
.type
);
663 max
= sval_type_max(min
.type
);
667 * FIXME: This has a problem merging a range_list like: min-0,3-max
668 * with a range like 1-2. You end up with min-2,3-max instead of
671 FOR_EACH_PTR(*list
, tmp
) {
673 /* Sometimes we overlap with more than one range
674 so we have to delete or modify the next range. */
675 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
676 /* join 2 ranges here */
678 DELETE_CURRENT_PTR(tmp
);
682 /* Doesn't overlap with the next one. */
683 if (sval_cmp(max
, tmp
->min
) < 0)
686 if (sval_cmp(max
, tmp
->max
) <= 0) {
687 /* Partially overlaps the next one. */
689 DELETE_CURRENT_PTR(tmp
);
692 /* Completely overlaps the next one. */
693 DELETE_CURRENT_PTR(tmp
);
694 /* there could be more ranges to delete */
698 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
699 /* join 2 ranges into a big range */
700 new = alloc_range(min
, tmp
->max
);
701 REPLACE_CURRENT_PTR(tmp
, new);
704 if (sval_cmp(max
, tmp
->min
) < 0) { /* new range entirely below */
705 new = alloc_range(min
, max
);
706 INSERT_CURRENT(new, tmp
);
709 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
710 if (sval_cmp(max
, tmp
->max
) < 0)
714 new = alloc_range(min
, max
);
715 REPLACE_CURRENT_PTR(tmp
, new);
720 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
722 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
724 new = alloc_range(min
, max
);
725 REPLACE_CURRENT_PTR(tmp
, new);
729 if (!sval_is_min(min
) && min
.value
- 1 == tmp
->max
.value
) {
730 /* join 2 ranges into a big range */
731 new = alloc_range(tmp
->min
, max
);
732 REPLACE_CURRENT_PTR(tmp
, new);
736 /* the new range is entirely above the existing ranges */
737 } END_FOR_EACH_PTR(tmp
);
740 new = alloc_range(min
, max
);
741 add_ptr_list(list
, new);
744 struct range_list
*clone_rl(struct range_list
*list
)
746 struct data_range
*tmp
;
747 struct range_list
*ret
= NULL
;
749 FOR_EACH_PTR(list
, tmp
) {
750 add_ptr_list(&ret
, tmp
);
751 } END_FOR_EACH_PTR(tmp
);
755 struct range_list
*clone_rl_permanent(struct range_list
*list
)
757 struct data_range
*tmp
;
758 struct data_range
*new;
759 struct range_list
*ret
= NULL
;
761 FOR_EACH_PTR(list
, tmp
) {
762 new = alloc_range_perm(tmp
->min
, tmp
->max
);
763 add_ptr_list(&ret
, new);
764 } END_FOR_EACH_PTR(tmp
);
768 struct range_list
*rl_union(struct range_list
*one
, struct range_list
*two
)
770 struct data_range
*tmp
;
771 struct range_list
*ret
= NULL
;
773 FOR_EACH_PTR(one
, tmp
) {
774 add_range(&ret
, tmp
->min
, tmp
->max
);
775 } END_FOR_EACH_PTR(tmp
);
776 FOR_EACH_PTR(two
, tmp
) {
777 add_range(&ret
, tmp
->min
, tmp
->max
);
778 } END_FOR_EACH_PTR(tmp
);
782 struct range_list
*remove_range(struct range_list
*list
, sval_t min
, sval_t max
)
784 struct data_range
*tmp
;
785 struct range_list
*ret
= NULL
;
790 min
= sval_cast(rl_type(list
), min
);
791 max
= sval_cast(rl_type(list
), max
);
792 if (sval_cmp(min
, max
) > 0) {
798 FOR_EACH_PTR(list
, tmp
) {
799 if (sval_cmp(tmp
->max
, min
) < 0) {
800 add_range(&ret
, tmp
->min
, tmp
->max
);
803 if (sval_cmp(tmp
->min
, max
) > 0) {
804 add_range(&ret
, tmp
->min
, tmp
->max
);
807 if (sval_cmp(tmp
->min
, min
) >= 0 && sval_cmp(tmp
->max
, max
) <= 0)
809 if (sval_cmp(tmp
->min
, min
) >= 0) {
811 add_range(&ret
, max
, tmp
->max
);
812 } else if (sval_cmp(tmp
->max
, max
) <= 0) {
814 add_range(&ret
, tmp
->min
, min
);
818 add_range(&ret
, tmp
->min
, min
);
819 add_range(&ret
, max
, tmp
->max
);
821 } END_FOR_EACH_PTR(tmp
);
825 int ranges_equiv(struct data_range
*one
, struct data_range
*two
)
831 if (sval_cmp(one
->min
, two
->min
) != 0)
833 if (sval_cmp(one
->max
, two
->max
) != 0)
838 int rl_equiv(struct range_list
*one
, struct range_list
*two
)
840 struct data_range
*one_range
;
841 struct data_range
*two_range
;
846 PREPARE_PTR_LIST(one
, one_range
);
847 PREPARE_PTR_LIST(two
, two_range
);
849 if (!one_range
&& !two_range
)
851 if (!ranges_equiv(one_range
, two_range
))
853 NEXT_PTR_LIST(one_range
);
854 NEXT_PTR_LIST(two_range
);
856 FINISH_PTR_LIST(two_range
);
857 FINISH_PTR_LIST(one_range
);
862 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
864 switch (comparison
) {
866 case SPECIAL_UNSIGNED_LT
:
867 if (sval_cmp(left
->min
, right
->max
) < 0)
870 case SPECIAL_UNSIGNED_LTE
:
872 if (sval_cmp(left
->min
, right
->max
) <= 0)
876 if (sval_cmp(left
->max
, right
->min
) < 0)
878 if (sval_cmp(left
->min
, right
->max
) > 0)
881 case SPECIAL_UNSIGNED_GTE
:
883 if (sval_cmp(left
->max
, right
->min
) >= 0)
887 case SPECIAL_UNSIGNED_GT
:
888 if (sval_cmp(left
->max
, right
->min
) > 0)
891 case SPECIAL_NOTEQUAL
:
892 if (sval_cmp(left
->min
, left
->max
) != 0)
894 if (sval_cmp(right
->min
, right
->max
) != 0)
896 if (sval_cmp(left
->min
, right
->min
) != 0)
900 sm_msg("unhandled comparison %d\n", comparison
);
906 int true_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
909 return true_comparison_range(var
, comparison
, val
);
911 return true_comparison_range(val
, comparison
, var
);
914 static int false_comparison_range_sval(struct data_range
*left
, int comparison
, struct data_range
*right
)
916 switch (comparison
) {
918 case SPECIAL_UNSIGNED_LT
:
919 if (sval_cmp(left
->max
, right
->min
) >= 0)
922 case SPECIAL_UNSIGNED_LTE
:
924 if (sval_cmp(left
->max
, right
->min
) > 0)
928 if (sval_cmp(left
->min
, left
->max
) != 0)
930 if (sval_cmp(right
->min
, right
->max
) != 0)
932 if (sval_cmp(left
->min
, right
->min
) != 0)
935 case SPECIAL_UNSIGNED_GTE
:
937 if (sval_cmp(left
->min
, right
->max
) < 0)
941 case SPECIAL_UNSIGNED_GT
:
942 if (sval_cmp(left
->min
, right
->max
) <= 0)
945 case SPECIAL_NOTEQUAL
:
946 if (sval_cmp(left
->max
, right
->min
) < 0)
948 if (sval_cmp(left
->min
, right
->max
) > 0)
952 sm_msg("unhandled comparison %d\n", comparison
);
958 int false_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
961 return false_comparison_range_sval(var
, comparison
, val
);
963 return false_comparison_range_sval(val
, comparison
, var
);
966 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
968 struct range_list
*rl_left
, *rl_right
;
969 struct data_range
*tmp_left
, *tmp_right
;
972 if (!get_implied_rl(left
, &rl_left
))
974 if (!get_implied_rl(right
, &rl_right
))
977 type
= rl_type(rl_left
);
978 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
979 type
= rl_type(rl_right
);
980 if (type_positive_bits(type
) < 31)
983 rl_left
= cast_rl(type
, rl_left
);
984 rl_right
= cast_rl(type
, rl_right
);
986 FOR_EACH_PTR(rl_left
, tmp_left
) {
987 FOR_EACH_PTR(rl_right
, tmp_right
) {
988 if (true_comparison_range(tmp_left
, comparison
, tmp_right
))
990 } END_FOR_EACH_PTR(tmp_right
);
991 } END_FOR_EACH_PTR(tmp_left
);
995 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
997 struct range_list
*rl_left
, *rl_right
;
998 struct data_range
*tmp_left
, *tmp_right
;
1001 if (!get_implied_rl(left
, &rl_left
))
1003 if (!get_implied_rl(right
, &rl_right
))
1006 type
= rl_type(rl_left
);
1007 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
1008 type
= rl_type(rl_right
);
1009 if (type_positive_bits(type
) < 31)
1012 rl_left
= cast_rl(type
, rl_left
);
1013 rl_right
= cast_rl(type
, rl_right
);
1015 FOR_EACH_PTR(rl_left
, tmp_left
) {
1016 FOR_EACH_PTR(rl_right
, tmp_right
) {
1017 if (false_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
1019 } END_FOR_EACH_PTR(tmp_right
);
1020 } END_FOR_EACH_PTR(tmp_left
);
1024 int possibly_true_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
1026 struct data_range
*left_tmp
, *right_tmp
;
1027 struct symbol
*type
;
1029 if (!left_ranges
|| !right_ranges
)
1032 type
= rl_type(left_ranges
);
1033 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
1034 type
= rl_type(right_ranges
);
1035 if (type_positive_bits(type
) < 31)
1038 left_ranges
= cast_rl(type
, left_ranges
);
1039 right_ranges
= cast_rl(type
, right_ranges
);
1041 FOR_EACH_PTR(left_ranges
, left_tmp
) {
1042 FOR_EACH_PTR(right_ranges
, right_tmp
) {
1043 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
1045 } END_FOR_EACH_PTR(right_tmp
);
1046 } END_FOR_EACH_PTR(left_tmp
);
1050 int possibly_false_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
1052 struct data_range
*left_tmp
, *right_tmp
;
1053 struct symbol
*type
;
1055 if (!left_ranges
|| !right_ranges
)
1058 type
= rl_type(left_ranges
);
1059 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
1060 type
= rl_type(right_ranges
);
1061 if (type_positive_bits(type
) < 31)
1064 left_ranges
= cast_rl(type
, left_ranges
);
1065 right_ranges
= cast_rl(type
, right_ranges
);
1067 FOR_EACH_PTR(left_ranges
, left_tmp
) {
1068 FOR_EACH_PTR(right_ranges
, right_tmp
) {
1069 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
1071 } END_FOR_EACH_PTR(right_tmp
);
1072 } END_FOR_EACH_PTR(left_tmp
);
1076 /* FIXME: the _rl here stands for right left so really it should be _lr */
1077 int possibly_true_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1080 return possibly_true_rl(a
, comparison
, b
);
1082 return possibly_true_rl(b
, comparison
, a
);
1085 int possibly_false_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1088 return possibly_false_rl(a
, comparison
, b
);
1090 return possibly_false_rl(b
, comparison
, a
);
1093 int rl_has_sval(struct range_list
*rl
, sval_t sval
)
1095 struct data_range
*tmp
;
1097 FOR_EACH_PTR(rl
, tmp
) {
1098 if (sval_cmp(tmp
->min
, sval
) <= 0 &&
1099 sval_cmp(tmp
->max
, sval
) >= 0)
1101 } END_FOR_EACH_PTR(tmp
);
1105 void tack_on(struct range_list
**list
, struct data_range
*drange
)
1107 add_ptr_list(list
, drange
);
1110 void push_rl(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
1112 add_ptr_list(rl_stack
, rl
);
1115 struct range_list
*pop_rl(struct range_list_stack
**rl_stack
)
1117 struct range_list
*rl
;
1119 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1120 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1124 struct range_list
*top_rl(struct range_list_stack
*rl_stack
)
1126 struct range_list
*rl
;
1128 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1132 void filter_top_rl(struct range_list_stack
**rl_stack
, struct range_list
*filter
)
1134 struct range_list
*rl
;
1136 rl
= pop_rl(rl_stack
);
1137 rl
= rl_filter(rl
, filter
);
1138 push_rl(rl_stack
, rl
);
1141 struct range_list
*rl_truncate_cast(struct symbol
*type
, struct range_list
*rl
)
1143 struct data_range
*tmp
;
1144 struct range_list
*ret
= NULL
;
1150 if (!type
|| type
== rl_type(rl
))
1153 FOR_EACH_PTR(rl
, tmp
) {
1156 if (type_bits(type
) < type_bits(rl_type(rl
))) {
1157 min
.uvalue
= tmp
->min
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1158 max
.uvalue
= tmp
->max
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1160 if (sval_cmp(min
, max
) > 0) {
1161 min
= sval_cast(type
, min
);
1162 max
= sval_cast(type
, max
);
1164 add_range_t(type
, &ret
, min
, max
);
1165 } END_FOR_EACH_PTR(tmp
);
1170 static int rl_is_sane(struct range_list
*rl
)
1172 struct data_range
*tmp
;
1173 struct symbol
*type
;
1176 FOR_EACH_PTR(rl
, tmp
) {
1177 if (!sval_fits(type
, tmp
->min
))
1179 if (!sval_fits(type
, tmp
->max
))
1181 if (sval_cmp(tmp
->min
, tmp
->max
) > 0)
1183 } END_FOR_EACH_PTR(tmp
);
1188 static int rl_type_consistent(struct range_list
*rl
)
1190 struct data_range
*tmp
;
1191 struct symbol
*type
;
1194 FOR_EACH_PTR(rl
, tmp
) {
1195 if (type
!= tmp
->min
.type
|| type
!= tmp
->max
.type
)
1197 } END_FOR_EACH_PTR(tmp
);
1201 static struct range_list
*cast_to_bool(struct range_list
*rl
)
1203 struct data_range
*tmp
;
1204 struct range_list
*ret
= NULL
;
1207 sval_t min
= { .type
= &bool_ctype
};
1208 sval_t max
= { .type
= &bool_ctype
};
1210 FOR_EACH_PTR(rl
, tmp
) {
1211 if (tmp
->min
.value
|| tmp
->max
.value
)
1213 if (sval_is_negative(tmp
->min
) &&
1214 sval_is_negative(tmp
->max
))
1216 if (tmp
->min
.value
== 0 ||
1217 tmp
->max
.value
== 0)
1219 if (sval_is_negative(tmp
->min
) &&
1222 } END_FOR_EACH_PTR(tmp
);
1229 add_range(&ret
, min
, max
);
1233 struct range_list
*cast_rl(struct symbol
*type
, struct range_list
*rl
)
1235 struct data_range
*tmp
;
1236 struct range_list
*ret
= NULL
;
1243 if (!rl_is_sane(rl
))
1244 return alloc_whole_rl(type
);
1245 if (type
== rl_type(rl
) && rl_type_consistent(rl
))
1248 if (type
== &bool_ctype
)
1249 return cast_to_bool(rl
);
1251 FOR_EACH_PTR(rl
, tmp
) {
1252 add_range_t(type
, &ret
, tmp
->min
, tmp
->max
);
1253 } END_FOR_EACH_PTR(tmp
);
1256 return alloc_whole_rl(type
);
1261 struct range_list
*rl_invert(struct range_list
*orig
)
1263 struct range_list
*ret
= NULL
;
1264 struct data_range
*tmp
;
1265 sval_t gap_min
, abs_max
, sval
;
1269 if (type_bits(rl_type(orig
)) < 0) /* void type mostly */
1272 gap_min
= sval_type_min(rl_min(orig
).type
);
1273 abs_max
= sval_type_max(rl_max(orig
).type
);
1275 FOR_EACH_PTR(orig
, tmp
) {
1276 if (sval_cmp(tmp
->min
, gap_min
) > 0) {
1277 sval
= sval_type_val(tmp
->min
.type
, tmp
->min
.value
- 1);
1278 add_range(&ret
, gap_min
, sval
);
1280 if (sval_cmp(tmp
->max
, abs_max
) == 0)
1282 gap_min
= sval_type_val(tmp
->max
.type
, tmp
->max
.value
+ 1);
1283 } END_FOR_EACH_PTR(tmp
);
1285 if (sval_cmp(gap_min
, abs_max
) <= 0)
1286 add_range(&ret
, gap_min
, abs_max
);
1291 struct range_list
*rl_filter(struct range_list
*rl
, struct range_list
*filter
)
1293 struct data_range
*tmp
;
1295 FOR_EACH_PTR(filter
, tmp
) {
1296 rl
= remove_range(rl
, tmp
->min
, tmp
->max
);
1297 } END_FOR_EACH_PTR(tmp
);
1302 struct range_list
*rl_intersection(struct range_list
*one
, struct range_list
*two
)
1304 struct range_list
*one_orig
;
1305 struct range_list
*two_orig
;
1306 struct range_list
*ret
;
1307 struct symbol
*ret_type
;
1308 struct symbol
*small_type
;
1309 struct symbol
*large_type
;
1319 ret_type
= rl_type(one
);
1320 small_type
= rl_type(one
);
1321 large_type
= rl_type(two
);
1323 if (type_bits(rl_type(two
)) < type_bits(small_type
)) {
1324 small_type
= rl_type(two
);
1325 large_type
= rl_type(one
);
1328 one
= cast_rl(large_type
, one
);
1329 two
= cast_rl(large_type
, two
);
1332 one
= rl_invert(one
);
1333 two
= rl_invert(two
);
1335 ret
= rl_filter(ret
, one
);
1336 ret
= rl_filter(ret
, two
);
1338 one
= cast_rl(small_type
, one_orig
);
1339 two
= cast_rl(small_type
, two_orig
);
1341 one
= rl_invert(one
);
1342 two
= rl_invert(two
);
1344 ret
= cast_rl(small_type
, ret
);
1345 ret
= rl_filter(ret
, one
);
1346 ret
= rl_filter(ret
, two
);
1348 return cast_rl(ret_type
, ret
);
1351 static struct range_list
*handle_mod_rl(struct range_list
*left
, struct range_list
*right
)
1356 max
= rl_max(right
);
1357 if (sval_is_max(max
))
1362 if (sval_is_negative(max
))
1364 if (sval_cmp(rl_max(left
), max
) < 0)
1368 return alloc_rl(zero
, max
);
1371 static struct range_list
*get_neg_rl(struct range_list
*rl
)
1373 struct data_range
*tmp
;
1374 struct data_range
*new;
1375 struct range_list
*ret
= NULL
;
1379 if (sval_is_positive(rl_min(rl
)))
1382 FOR_EACH_PTR(rl
, tmp
) {
1383 if (sval_is_positive(tmp
->min
))
1385 if (sval_is_positive(tmp
->max
)) {
1386 new = alloc_range(tmp
->min
, tmp
->max
);
1387 new->max
.value
= -1;
1388 add_range(&ret
, new->min
, new->max
);
1391 add_range(&ret
, tmp
->min
, tmp
->max
);
1392 } END_FOR_EACH_PTR(tmp
);
1397 static struct range_list
*get_pos_rl(struct range_list
*rl
)
1399 struct data_range
*tmp
;
1400 struct data_range
*new;
1401 struct range_list
*ret
= NULL
;
1405 if (sval_is_negative(rl_max(rl
)))
1408 FOR_EACH_PTR(rl
, tmp
) {
1409 if (sval_is_negative(tmp
->max
))
1411 if (sval_is_positive(tmp
->min
)) {
1412 add_range(&ret
, tmp
->min
, tmp
->max
);
1415 new = alloc_range(tmp
->min
, tmp
->max
);
1417 add_range(&ret
, new->min
, new->max
);
1418 } END_FOR_EACH_PTR(tmp
);
1423 static struct range_list
*divide_rl_helper(struct range_list
*left
, struct range_list
*right
)
1425 sval_t right_min
, right_max
;
1428 if (!left
|| !right
)
1431 /* let's assume we never divide by zero */
1432 right_min
= rl_min(right
);
1433 right_max
= rl_max(right
);
1434 if (right_min
.value
== 0 && right_max
.value
== 0)
1436 if (right_min
.value
== 0)
1437 right_min
.value
= 1;
1438 if (right_max
.value
== 0)
1439 right_max
.value
= -1;
1441 max
= sval_binop(rl_max(left
), '/', right_min
);
1442 min
= sval_binop(rl_min(left
), '/', right_max
);
1444 return alloc_rl(min
, max
);
1447 static struct range_list
*handle_divide_rl(struct range_list
*left
, struct range_list
*right
)
1449 struct range_list
*left_neg
, *left_pos
, *right_neg
, *right_pos
;
1450 struct range_list
*neg_neg
, *neg_pos
, *pos_neg
, *pos_pos
;
1451 struct range_list
*ret
;
1453 if (is_whole_rl(right
))
1456 left_neg
= get_neg_rl(left
);
1457 left_pos
= get_pos_rl(left
);
1458 right_neg
= get_neg_rl(right
);
1459 right_pos
= get_pos_rl(right
);
1461 neg_neg
= divide_rl_helper(left_neg
, right_neg
);
1462 neg_pos
= divide_rl_helper(left_neg
, right_pos
);
1463 pos_neg
= divide_rl_helper(left_pos
, right_neg
);
1464 pos_pos
= divide_rl_helper(left_pos
, right_pos
);
1466 ret
= rl_union(neg_neg
, neg_pos
);
1467 ret
= rl_union(ret
, pos_neg
);
1468 return rl_union(ret
, pos_pos
);
1471 static struct range_list
*handle_add_mult_rl(struct range_list
*left
, int op
, struct range_list
*right
)
1475 if (sval_binop_overflows(rl_min(left
), op
, rl_min(right
)))
1477 min
= sval_binop(rl_min(left
), op
, rl_min(right
));
1479 if (sval_binop_overflows(rl_max(left
), op
, rl_max(right
)))
1481 max
= sval_binop(rl_max(left
), op
, rl_max(right
));
1483 return alloc_rl(min
, max
);
1486 static unsigned long long rl_bits_always_set(struct range_list
*rl
)
1488 return sval_fls_mask(rl_min(rl
));
1491 static unsigned long long rl_bits_maybe_set(struct range_list
*rl
)
1493 return sval_fls_mask(rl_max(rl
));
1496 static struct range_list
*handle_OR_rl(struct range_list
*left
, struct range_list
*right
)
1498 unsigned long long left_min
, left_max
, right_min
, right_max
;
1502 if ((rl_to_sval(left
, &sval
) || rl_to_sval(right
, &sval
)) &&
1503 !sval_binop_overflows(rl_max(left
), '+', rl_max(right
)))
1504 return rl_binop(left
, '+', right
);
1506 left_min
= rl_bits_always_set(left
);
1507 left_max
= rl_bits_maybe_set(left
);
1508 right_min
= rl_bits_always_set(right
);
1509 right_max
= rl_bits_maybe_set(right
);
1511 min
.type
= max
.type
= &ullong_ctype
;
1512 min
.uvalue
= left_min
| right_min
;
1513 max
.uvalue
= left_max
| right_max
;
1515 return cast_rl(rl_type(left
), alloc_rl(min
, max
));
1518 static struct range_list
*handle_XOR_rl(struct range_list
*left
, struct range_list
*right
)
1520 unsigned long long left_set
, left_maybe
;
1521 unsigned long long right_set
, right_maybe
;
1524 left_set
= rl_bits_always_set(left
);
1525 left_maybe
= rl_bits_maybe_set(left
);
1527 right_set
= rl_bits_always_set(right
);
1528 right_maybe
= rl_bits_maybe_set(right
);
1530 zero
= max
= rl_min(left
);
1532 max
.uvalue
= fls_mask((left_maybe
| right_maybe
) ^ (left_set
& right_set
));
1534 return cast_rl(rl_type(left
), alloc_rl(zero
, max
));
1537 static struct range_list
*handle_AND_rl(struct range_list
*left
, struct range_list
*right
)
1539 unsigned long long left_set
, left_maybe
;
1540 unsigned long long right_set
, right_maybe
;
1545 left_set
= rl_bits_always_set(left
);
1546 left_maybe
= rl_bits_maybe_set(left
);
1548 right_set
= rl_bits_always_set(right
);
1549 right_maybe
= rl_bits_maybe_set(right
);
1551 zero
= max
= rl_min(left
);
1553 max
.uvalue
= fls_mask((left_maybe
| right_maybe
) ^ (left_set
& right_set
));
1555 return cast_rl(rl_type(left
), alloc_rl(zero
, max
));
1558 struct range_list
*rl_binop(struct range_list
*left
, int op
, struct range_list
*right
)
1560 struct symbol
*cast_type
;
1561 sval_t left_sval
, right_sval
;
1562 struct range_list
*ret
= NULL
;
1564 cast_type
= rl_type(left
);
1565 if (sval_type_max(rl_type(left
)).uvalue
< sval_type_max(rl_type(right
)).uvalue
)
1566 cast_type
= rl_type(right
);
1567 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
1568 cast_type
= &int_ctype
;
1570 left
= cast_rl(cast_type
, left
);
1571 right
= cast_rl(cast_type
, right
);
1573 if (!left
|| !right
)
1574 return alloc_whole_rl(cast_type
);
1576 if (rl_to_sval(left
, &left_sval
) && rl_to_sval(right
, &right_sval
)) {
1577 sval_t val
= sval_binop(left_sval
, op
, right_sval
);
1578 return alloc_rl(val
, val
);
1583 ret
= handle_mod_rl(left
, right
);
1586 ret
= handle_divide_rl(left
, right
);
1590 ret
= handle_add_mult_rl(left
, op
, right
);
1593 ret
= handle_OR_rl(left
, right
);
1596 ret
= handle_XOR_rl(left
, right
);
1599 ret
= handle_AND_rl(left
, right
);
1602 /* FIXME: Do the rest as well */
1604 case SPECIAL_RIGHTSHIFT
:
1605 case SPECIAL_LEFTSHIFT
:
1610 ret
= alloc_whole_rl(cast_type
);
1614 void free_rl(struct range_list
**rlist
)
1616 __free_ptr_list((struct ptr_list
**)rlist
);
1619 static void free_single_dinfo(struct data_info
*dinfo
)
1621 free_rl(&dinfo
->value_ranges
);
1624 static void free_dinfos(struct allocation_blob
*blob
)
1626 unsigned int size
= sizeof(struct data_info
);
1627 unsigned int offset
= 0;
1629 while (offset
< blob
->offset
) {
1630 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
1635 void free_data_info_allocs(void)
1637 struct allocator_struct
*desc
= &data_info_allocator
;
1638 struct allocation_blob
*blob
= desc
->blobs
;
1641 desc
->allocations
= 0;
1642 desc
->total_bytes
= 0;
1643 desc
->useful_bytes
= 0;
1644 desc
->freelist
= NULL
;
1646 struct allocation_blob
*next
= blob
->next
;
1648 blob_free(blob
, desc
->chunking
);
1651 clear_data_range_alloc();
1654 void split_comparison_rl(struct range_list
*left_orig
, int op
, struct range_list
*right_orig
,
1655 struct range_list
**left_true_rl
, struct range_list
**left_false_rl
,
1656 struct range_list
**right_true_rl
, struct range_list
**right_false_rl
)
1658 struct range_list
*left_true
, *left_false
;
1659 struct range_list
*right_true
, *right_false
;
1662 min
= sval_type_min(rl_type(left_orig
));
1663 max
= sval_type_max(rl_type(left_orig
));
1665 left_true
= clone_rl(left_orig
);
1666 left_false
= clone_rl(left_orig
);
1667 right_true
= clone_rl(right_orig
);
1668 right_false
= clone_rl(right_orig
);
1672 case SPECIAL_UNSIGNED_LT
:
1673 left_true
= remove_range(left_orig
, rl_max(right_orig
), max
);
1674 if (!sval_is_min(rl_min(right_orig
))) {
1675 left_false
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1678 right_true
= remove_range(right_orig
, min
, rl_min(left_orig
));
1679 if (!sval_is_max(rl_max(left_orig
)))
1680 right_false
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1682 case SPECIAL_UNSIGNED_LTE
:
1684 if (!sval_is_max(rl_max(right_orig
)))
1685 left_true
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1686 left_false
= remove_range(left_orig
, min
, rl_min(right_orig
));
1688 if (!sval_is_min(rl_min(left_orig
)))
1689 right_true
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1690 right_false
= remove_range(right_orig
, rl_max(left_orig
), max
);
1692 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1693 left_false
= remove_range(left_false
, rl_min(left_orig
), rl_min(left_orig
));
1694 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1695 right_false
= remove_range(right_false
, rl_max(left_orig
), rl_max(left_orig
));
1698 if (!sval_is_max(rl_max(right_orig
))) {
1699 left_true
= remove_range(left_true
, add_one(rl_max(right_orig
)), max
);
1701 if (!sval_is_min(rl_min(right_orig
))) {
1702 left_true
= remove_range(left_true
, min
, sub_one(rl_min(right_orig
)));
1704 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1705 left_false
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1707 if (!sval_is_max(rl_max(left_orig
)))
1708 right_true
= remove_range(right_true
, add_one(rl_max(left_orig
)), max
);
1709 if (!sval_is_min(rl_min(left_orig
)))
1710 right_true
= remove_range(right_true
, min
, sub_one(rl_min(left_orig
)));
1711 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1712 right_false
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1714 case SPECIAL_UNSIGNED_GTE
:
1716 if (!sval_is_min(rl_min(right_orig
)))
1717 left_true
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1718 left_false
= remove_range(left_orig
, rl_max(right_orig
), max
);
1720 if (!sval_is_max(rl_max(left_orig
)))
1721 right_true
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1722 right_false
= remove_range(right_orig
, min
, rl_min(left_orig
));
1724 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1725 right_false
= remove_range(right_false
, rl_min(left_orig
), rl_min(left_orig
));
1726 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1727 left_false
= remove_range(left_false
, rl_max(left_orig
), rl_max(left_orig
));
1730 case SPECIAL_UNSIGNED_GT
:
1731 left_true
= remove_range(left_orig
, min
, rl_min(right_orig
));
1732 if (!sval_is_max(rl_max(right_orig
)))
1733 left_false
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1735 right_true
= remove_range(right_orig
, rl_max(left_orig
), max
);
1736 if (!sval_is_min(rl_min(left_orig
)))
1737 right_false
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1739 case SPECIAL_NOTEQUAL
:
1740 if (!sval_is_max(rl_max(right_orig
)))
1741 left_false
= remove_range(left_false
, add_one(rl_max(right_orig
)), max
);
1742 if (!sval_is_min(rl_min(right_orig
)))
1743 left_false
= remove_range(left_false
, min
, sub_one(rl_min(right_orig
)));
1744 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1745 left_true
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1747 if (!sval_is_max(rl_max(left_orig
)))
1748 right_false
= remove_range(right_false
, add_one(rl_max(left_orig
)), max
);
1749 if (!sval_is_min(rl_min(left_orig
)))
1750 right_false
= remove_range(right_false
, min
, sub_one(rl_min(left_orig
)));
1751 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1752 right_true
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1755 sm_msg("internal error: unhandled comparison %d", op
);
1760 *left_true_rl
= left_true
;
1761 *left_false_rl
= left_false
;
1763 if (right_true_rl
) {
1764 *right_true_rl
= right_true
;
1765 *right_false_rl
= right_false
;