2 * Copyright (C) 2009 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
20 #include "smatch_extra.h"
21 #include "smatch_slist.h"
23 ALLOCATOR(data_info
, "smatch extra data");
24 ALLOCATOR(data_range
, "data range");
25 __DO_ALLOCATOR(struct data_range
, sizeof(struct data_range
), __alignof__(struct data_range
),
26 "permanent ranges", perm_data_range
);
28 char *show_rl(struct range_list
*list
)
30 struct data_range
*tmp
;
36 FOR_EACH_PTR(list
, tmp
) {
38 strncat(full
, ",", 254 - strlen(full
));
39 if (sval_cmp(tmp
->min
, tmp
->max
) == 0) {
40 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
43 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
44 strncat(full
, "-", 254 - strlen(full
));
45 strncat(full
, sval_to_str(tmp
->max
), 254 - strlen(full
));
46 } END_FOR_EACH_PTR(tmp
);
47 return alloc_sname(full
);
50 static int sval_too_big(struct symbol
*type
, sval_t sval
)
52 if (type_bits(type
) == 64)
54 if (sval
.uvalue
> ((1ULL << type_bits(type
)) - 1))
59 static void add_range_t(struct symbol
*type
, struct range_list
**rl
, sval_t min
, sval_t max
)
61 /* If we're just adding a number, cast it and add it */
62 if (sval_cmp(min
, max
) == 0) {
63 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
67 /* If the range is within the type range then add it */
68 if (sval_fits(type
, min
) && sval_fits(type
, max
)) {
69 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
74 * If the range we are adding has more bits than the range type then
75 * add the whole range type. Eg:
76 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
77 * This isn't totally the right thing to do. We could be more granular.
79 if (sval_too_big(type
, min
) || sval_too_big(type
, max
)) {
80 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
84 /* Cast negative values to high positive values */
85 if (sval_is_negative(min
) && type_unsigned(type
)) {
86 if (sval_is_positive(max
)) {
87 if (sval_too_high(type
, max
)) {
88 add_range(rl
, sval_type_min(type
), sval_type_max(type
));
91 add_range(rl
, sval_type_val(type
, 0), sval_cast(type
, max
));
92 max
= sval_type_max(type
);
94 max
= sval_cast(type
, max
);
96 min
= sval_cast(type
, min
);
97 add_range(rl
, min
, max
);
100 /* Cast high positive numbers to negative */
101 if (sval_unsigned(max
) && sval_is_negative(sval_cast(type
, max
))) {
102 if (!sval_is_negative(sval_cast(type
, min
))) {
103 add_range(rl
, sval_cast(type
, min
), sval_type_max(type
));
104 min
= sval_type_min(type
);
106 min
= sval_cast(type
, min
);
108 max
= sval_cast(type
, max
);
109 add_range(rl
, min
, max
);
112 add_range(rl
, sval_cast(type
, min
), sval_cast(type
, max
));
116 static int str_to_comparison_arg_helper(const char *str
,
117 struct expression
*call
, int *comparison
,
118 struct expression
**arg
, char **endp
)
121 char *c
= (char *)str
;
130 *comparison
= SPECIAL_LTE
;
135 } else if (*c
== '=') {
138 *comparison
= SPECIAL_EQUAL
;
139 } else if (*c
== '>') {
142 *comparison
= SPECIAL_GTE
;
147 } else if (*c
== '!') {
150 *comparison
= SPECIAL_NOTEQUAL
;
159 param
= strtoll(c
, &c
, 10);
160 c
++; /* skip the ']' character */
166 *arg
= get_argument_from_call_expr(call
->args
, param
);
172 int str_to_comparison_arg(const char *str
, struct expression
*call
, int *comparison
, struct expression
**arg
)
181 return str_to_comparison_arg_helper(str
, call
, comparison
, arg
, NULL
);
184 static int get_val_from_key(int use_max
, struct symbol
*type
, char *c
, struct expression
*call
, char **endp
, sval_t
*sval
)
186 struct expression
*arg
;
191 ret
= sval_type_max(type
);
193 ret
= sval_type_min(type
);
195 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
)) {
200 if (use_max
&& get_implied_max(arg
, &tmp
)) {
202 if (comparison
== '<') {
204 ret
= sval_binop(ret
, '-', tmp
);
207 if (!use_max
&& get_implied_min(arg
, &tmp
)) {
209 if (comparison
== '>') {
211 ret
= sval_binop(ret
, '+', tmp
);
219 static sval_t
add_one(sval_t sval
)
225 static sval_t
sub_one(sval_t sval
)
231 void filter_by_comparison(struct range_list
**rl
, int comparison
, struct range_list
*right
)
233 struct range_list
*left_orig
= *rl
;
234 struct range_list
*right_orig
= right
;
235 struct range_list
*ret_rl
= *rl
;
236 struct symbol
*cast_type
;
239 cast_type
= rl_type(left_orig
);
240 if (sval_type_max(rl_type(left_orig
)).uvalue
< sval_type_max(rl_type(right_orig
)).uvalue
)
241 cast_type
= rl_type(right_orig
);
242 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
243 cast_type
= &int_ctype
;
245 min
= sval_type_min(cast_type
);
246 max
= sval_type_max(cast_type
);
247 left_orig
= cast_rl(cast_type
, left_orig
);
248 right_orig
= cast_rl(cast_type
, right_orig
);
250 switch (comparison
) {
252 case SPECIAL_UNSIGNED_LT
:
253 ret_rl
= remove_range(left_orig
, rl_max(right_orig
), max
);
256 case SPECIAL_UNSIGNED_LTE
:
257 if (!sval_is_max(rl_max(right_orig
)))
258 ret_rl
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
261 if (!sval_is_max(rl_max(right_orig
)))
262 ret_rl
= remove_range(ret_rl
, add_one(rl_max(right_orig
)), max
);
263 if (!sval_is_min(rl_min(right_orig
)))
264 ret_rl
= remove_range(ret_rl
, min
, sub_one(rl_min(right_orig
)));
267 case SPECIAL_UNSIGNED_GTE
:
268 if (!sval_is_min(rl_min(right_orig
)))
269 ret_rl
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
272 case SPECIAL_UNSIGNED_GT
:
273 ret_rl
= remove_range(left_orig
, min
, rl_min(right_orig
));
275 case SPECIAL_NOTEQUAL
:
276 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
277 ret_rl
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
280 sm_msg("internal error: unhandled comparison %s", show_special(comparison
));
284 *rl
= cast_rl(rl_type(*rl
), ret_rl
);
287 static struct range_list
*filter_by_comparison_call(char *c
, struct expression
*call
, char **endp
, struct range_list
*start_rl
)
289 struct expression
*arg
;
290 struct range_list
*right_orig
;
293 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
))
296 if (!get_implied_rl(arg
, &right_orig
))
299 if (rl_type(start_rl
) == &int_ctype
&&
300 sval_is_negative(rl_min(start_rl
)) &&
301 type_unsigned(rl_type(right_orig
)))
302 right_orig
= cast_rl(&int_ctype
, right_orig
);
304 filter_by_comparison(&start_rl
, comparison
, right_orig
);
308 static sval_t
parse_val(int use_max
, struct expression
*call
, struct symbol
*type
, char *c
, char **endp
)
313 if (!strncmp(start
, "max", 3)) {
314 ret
= sval_type_max(type
);
316 } else if (!strncmp(start
, "u64max", 6)) {
317 ret
= sval_type_val(type
, ULLONG_MAX
);
319 } else if (!strncmp(start
, "s64max", 6)) {
320 ret
= sval_type_val(type
, LLONG_MAX
);
322 } else if (!strncmp(start
, "u32max", 6)) {
323 ret
= sval_type_val(type
, UINT_MAX
);
325 } else if (!strncmp(start
, "s32max", 6)) {
326 ret
= sval_type_val(type
, INT_MAX
);
328 } else if (!strncmp(start
, "u16max", 6)) {
329 ret
= sval_type_val(type
, USHRT_MAX
);
331 } else if (!strncmp(start
, "s16max", 6)) {
332 ret
= sval_type_val(type
, SHRT_MAX
);
334 } else if (!strncmp(start
, "min", 3)) {
335 ret
= sval_type_min(type
);
337 } else if (!strncmp(start
, "s64min", 6)) {
338 ret
= sval_type_val(type
, LLONG_MIN
);
340 } else if (!strncmp(start
, "s32min", 6)) {
341 ret
= sval_type_val(type
, INT_MIN
);
343 } else if (!strncmp(start
, "s16min", 6)) {
344 ret
= sval_type_val(type
, SHRT_MIN
);
346 } else if (!strncmp(start
, "long_min", 8)) {
347 ret
= sval_type_val(type
, LONG_MIN
);
349 } else if (!strncmp(start
, "long_max", 8)) {
350 ret
= sval_type_val(type
, LONG_MAX
);
352 } else if (!strncmp(start
, "ulong_max", 9)) {
353 ret
= sval_type_val(type
, ULONG_MAX
);
355 } else if (!strncmp(start
, "ptr_max", 7)) {
356 ret
= sval_type_val(type
, valid_ptr_max
);
358 } else if (start
[0] == '[') {
359 /* this parses [==p0] comparisons */
360 get_val_from_key(1, type
, start
, call
, &c
, &ret
);
362 ret
= sval_type_val(type
, strtoll(start
, &c
, 10));
368 static char *jump_to_call_math(char *value
)
372 while (*c
&& *c
!= '[')
378 if (*c
== '<' || *c
== '=' || *c
== '>' || *c
== '!')
384 static void str_to_rl_helper(struct expression
*call
, struct symbol
*type
, char *str
, char **endp
, struct range_list
**rl
)
386 struct range_list
*rl_tmp
= NULL
;
390 min
= sval_type_min(type
);
391 max
= sval_type_max(type
);
393 while (*c
!= '\0' && *c
!= '[') {
396 min
= parse_val(0, call
, type
, c
, &c
);
400 if (*c
== '\0' || *c
== '[') {
401 add_range_t(type
, &rl_tmp
, min
, min
);
405 add_range_t(type
, &rl_tmp
, min
, min
);
410 sm_msg("debug XXX: trouble parsing %s c = %s", str
, c
);
416 max
= parse_val(1, call
, type
, c
, &c
);
417 add_range_t(type
, &rl_tmp
, min
, max
);
428 static void str_to_dinfo(struct expression
*call
, struct symbol
*type
, char *value
, struct data_info
*dinfo
)
430 struct range_list
*math_rl
;
433 struct range_list
*rl
= NULL
;
438 if (strcmp(value
, "empty") == 0)
441 if (strncmp(value
, "[==$", 4) == 0) {
442 struct expression
*arg
;
445 if (!str_to_comparison_arg(value
, call
, &comparison
, &arg
))
447 if (!get_implied_rl(arg
, &rl
))
452 str_to_rl_helper(call
, type
, value
, &c
, &rl
);
456 call_math
= jump_to_call_math(value
);
457 if (call_math
&& parse_call_math_rl(call
, call_math
, &math_rl
)) {
458 rl
= rl_intersection(rl
, math_rl
);
463 * For now if we already tried to handle the call math and couldn't
464 * figure it out then bail.
466 if (jump_to_call_math(c
) == c
+ 1)
469 rl
= filter_by_comparison_call(c
, call
, &c
, rl
);
472 rl
= cast_rl(type
, rl
);
473 dinfo
->value_ranges
= rl
;
476 void str_to_rl(struct symbol
*type
, char *value
, struct range_list
**rl
)
478 struct data_info dinfo
= {};
480 str_to_dinfo(NULL
, type
, value
, &dinfo
);
481 *rl
= dinfo
.value_ranges
;
484 void call_results_to_rl(struct expression
*expr
, struct symbol
*type
, char *value
, struct range_list
**rl
)
486 struct data_info dinfo
= {};
488 str_to_dinfo(strip_expr(expr
), type
, value
, &dinfo
);
489 *rl
= dinfo
.value_ranges
;
492 int is_whole_rl(struct range_list
*rl
)
494 struct data_range
*drange
;
496 if (ptr_list_empty(rl
))
498 drange
= first_ptr_list((struct ptr_list
*)rl
);
499 if (sval_is_min(drange
->min
) && sval_is_max(drange
->max
))
504 int is_whole_rl_non_zero(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_unsigned(drange
->min
) &&
512 drange
->min
.value
== 1 &&
513 sval_is_max(drange
->max
))
515 if (!sval_is_min(drange
->min
) || drange
->max
.value
!= -1)
517 drange
= last_ptr_list((struct ptr_list
*)rl
);
518 if (drange
->min
.value
!= 1 || !sval_is_max(drange
->max
))
523 sval_t
rl_min(struct range_list
*rl
)
525 struct data_range
*drange
;
528 ret
.type
= &llong_ctype
;
529 ret
.value
= LLONG_MIN
;
530 if (ptr_list_empty(rl
))
532 drange
= first_ptr_list((struct ptr_list
*)rl
);
536 sval_t
rl_max(struct range_list
*rl
)
538 struct data_range
*drange
;
541 ret
.type
= &llong_ctype
;
542 ret
.value
= LLONG_MAX
;
543 if (ptr_list_empty(rl
))
545 drange
= last_ptr_list((struct ptr_list
*)rl
);
549 int rl_to_sval(struct range_list
*rl
, sval_t
*sval
)
558 if (sval_cmp(min
, max
) != 0)
564 struct symbol
*rl_type(struct range_list
*rl
)
568 return rl_min(rl
).type
;
571 static struct data_range
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
573 struct data_range
*ret
;
576 ret
= __alloc_perm_data_range(0);
578 ret
= __alloc_data_range(0);
584 struct data_range
*alloc_range(sval_t min
, sval_t max
)
586 return alloc_range_helper_sval(min
, max
, 0);
589 struct data_range
*alloc_range_perm(sval_t min
, sval_t max
)
591 return alloc_range_helper_sval(min
, max
, 1);
594 struct range_list
*alloc_rl(sval_t min
, sval_t max
)
596 struct range_list
*rl
= NULL
;
598 if (sval_cmp(min
, max
) > 0)
599 return alloc_whole_rl(min
.type
);
601 add_range(&rl
, min
, max
);
605 struct range_list
*alloc_whole_rl(struct symbol
*type
)
607 if (!type
|| type_positive_bits(type
) < 0)
609 if (type
->type
== SYM_ARRAY
)
612 return alloc_rl(sval_type_min(type
), sval_type_max(type
));
615 void add_range(struct range_list
**list
, sval_t min
, sval_t max
)
617 struct data_range
*tmp
;
618 struct data_range
*new = NULL
;
621 if (sval_cmp(min
, max
) > 0) {
622 min
= sval_type_min(min
.type
);
623 max
= sval_type_max(min
.type
);
627 * FIXME: This has a problem merging a range_list like: min-0,3-max
628 * with a range like 1-2. You end up with min-2,3-max instead of
631 FOR_EACH_PTR(*list
, tmp
) {
633 /* Sometimes we overlap with more than one range
634 so we have to delete or modify the next range. */
635 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
636 /* join 2 ranges here */
638 DELETE_CURRENT_PTR(tmp
);
642 /* Doesn't overlap with the next one. */
643 if (sval_cmp(max
, tmp
->min
) < 0)
646 if (sval_cmp(max
, tmp
->max
) <= 0) {
647 /* Partially overlaps the next one. */
649 DELETE_CURRENT_PTR(tmp
);
652 /* Completely overlaps the next one. */
653 DELETE_CURRENT_PTR(tmp
);
654 /* there could be more ranges to delete */
658 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
659 /* join 2 ranges into a big range */
660 new = alloc_range(min
, tmp
->max
);
661 REPLACE_CURRENT_PTR(tmp
, new);
664 if (sval_cmp(max
, tmp
->min
) < 0) { /* new range entirely below */
665 new = alloc_range(min
, max
);
666 INSERT_CURRENT(new, tmp
);
669 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
670 if (sval_cmp(max
, tmp
->max
) < 0)
674 new = alloc_range(min
, max
);
675 REPLACE_CURRENT_PTR(tmp
, new);
680 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
682 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
684 new = alloc_range(min
, max
);
685 REPLACE_CURRENT_PTR(tmp
, new);
689 if (!sval_is_min(min
) && min
.value
- 1 == tmp
->max
.value
) {
690 /* join 2 ranges into a big range */
691 new = alloc_range(tmp
->min
, max
);
692 REPLACE_CURRENT_PTR(tmp
, new);
696 /* the new range is entirely above the existing ranges */
697 } END_FOR_EACH_PTR(tmp
);
700 new = alloc_range(min
, max
);
701 add_ptr_list(list
, new);
704 struct range_list
*clone_rl(struct range_list
*list
)
706 struct data_range
*tmp
;
707 struct range_list
*ret
= NULL
;
709 FOR_EACH_PTR(list
, tmp
) {
710 add_ptr_list(&ret
, tmp
);
711 } END_FOR_EACH_PTR(tmp
);
715 struct range_list
*clone_rl_permanent(struct range_list
*list
)
717 struct data_range
*tmp
;
718 struct data_range
*new;
719 struct range_list
*ret
= NULL
;
721 FOR_EACH_PTR(list
, tmp
) {
722 new = alloc_range_perm(tmp
->min
, tmp
->max
);
723 add_ptr_list(&ret
, new);
724 } END_FOR_EACH_PTR(tmp
);
728 struct range_list
*rl_union(struct range_list
*one
, struct range_list
*two
)
730 struct data_range
*tmp
;
731 struct range_list
*ret
= NULL
;
733 FOR_EACH_PTR(one
, tmp
) {
734 add_range(&ret
, tmp
->min
, tmp
->max
);
735 } END_FOR_EACH_PTR(tmp
);
736 FOR_EACH_PTR(two
, tmp
) {
737 add_range(&ret
, tmp
->min
, tmp
->max
);
738 } END_FOR_EACH_PTR(tmp
);
742 struct range_list
*remove_range(struct range_list
*list
, sval_t min
, sval_t max
)
744 struct data_range
*tmp
;
745 struct range_list
*ret
= NULL
;
750 min
= sval_cast(rl_type(list
), min
);
751 max
= sval_cast(rl_type(list
), max
);
752 if (sval_cmp(min
, max
) > 0) {
758 FOR_EACH_PTR(list
, tmp
) {
759 if (sval_cmp(tmp
->max
, min
) < 0) {
760 add_range(&ret
, tmp
->min
, tmp
->max
);
763 if (sval_cmp(tmp
->min
, max
) > 0) {
764 add_range(&ret
, tmp
->min
, tmp
->max
);
767 if (sval_cmp(tmp
->min
, min
) >= 0 && sval_cmp(tmp
->max
, max
) <= 0)
769 if (sval_cmp(tmp
->min
, min
) >= 0) {
771 add_range(&ret
, max
, tmp
->max
);
772 } else if (sval_cmp(tmp
->max
, max
) <= 0) {
774 add_range(&ret
, tmp
->min
, min
);
778 add_range(&ret
, tmp
->min
, min
);
779 add_range(&ret
, max
, tmp
->max
);
781 } END_FOR_EACH_PTR(tmp
);
785 int ranges_equiv(struct data_range
*one
, struct data_range
*two
)
791 if (sval_cmp(one
->min
, two
->min
) != 0)
793 if (sval_cmp(one
->max
, two
->max
) != 0)
798 int rl_equiv(struct range_list
*one
, struct range_list
*two
)
800 struct data_range
*one_range
;
801 struct data_range
*two_range
;
806 PREPARE_PTR_LIST(one
, one_range
);
807 PREPARE_PTR_LIST(two
, two_range
);
809 if (!one_range
&& !two_range
)
811 if (!ranges_equiv(one_range
, two_range
))
813 NEXT_PTR_LIST(one_range
);
814 NEXT_PTR_LIST(two_range
);
816 FINISH_PTR_LIST(two_range
);
817 FINISH_PTR_LIST(one_range
);
822 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
824 switch (comparison
) {
826 case SPECIAL_UNSIGNED_LT
:
827 if (sval_cmp(left
->min
, right
->max
) < 0)
830 case SPECIAL_UNSIGNED_LTE
:
832 if (sval_cmp(left
->min
, right
->max
) <= 0)
836 if (sval_cmp(left
->max
, right
->min
) < 0)
838 if (sval_cmp(left
->min
, right
->max
) > 0)
841 case SPECIAL_UNSIGNED_GTE
:
843 if (sval_cmp(left
->max
, right
->min
) >= 0)
847 case SPECIAL_UNSIGNED_GT
:
848 if (sval_cmp(left
->max
, right
->min
) > 0)
851 case SPECIAL_NOTEQUAL
:
852 if (sval_cmp(left
->min
, left
->max
) != 0)
854 if (sval_cmp(right
->min
, right
->max
) != 0)
856 if (sval_cmp(left
->min
, right
->min
) != 0)
860 sm_msg("unhandled comparison %d\n", comparison
);
866 int true_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
869 return true_comparison_range(var
, comparison
, val
);
871 return true_comparison_range(val
, comparison
, var
);
874 static int false_comparison_range_sval(struct data_range
*left
, int comparison
, struct data_range
*right
)
876 switch (comparison
) {
878 case SPECIAL_UNSIGNED_LT
:
879 if (sval_cmp(left
->max
, right
->min
) >= 0)
882 case SPECIAL_UNSIGNED_LTE
:
884 if (sval_cmp(left
->max
, right
->min
) > 0)
888 if (sval_cmp(left
->min
, left
->max
) != 0)
890 if (sval_cmp(right
->min
, right
->max
) != 0)
892 if (sval_cmp(left
->min
, right
->min
) != 0)
895 case SPECIAL_UNSIGNED_GTE
:
897 if (sval_cmp(left
->min
, right
->max
) < 0)
901 case SPECIAL_UNSIGNED_GT
:
902 if (sval_cmp(left
->min
, right
->max
) <= 0)
905 case SPECIAL_NOTEQUAL
:
906 if (sval_cmp(left
->max
, right
->min
) < 0)
908 if (sval_cmp(left
->min
, right
->max
) > 0)
912 sm_msg("unhandled comparison %d\n", comparison
);
918 int false_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
921 return false_comparison_range_sval(var
, comparison
, val
);
923 return false_comparison_range_sval(val
, comparison
, var
);
926 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
928 struct range_list
*rl_left
, *rl_right
;
929 struct data_range
*tmp_left
, *tmp_right
;
932 if (!get_implied_rl(left
, &rl_left
))
934 if (!get_implied_rl(right
, &rl_right
))
937 type
= rl_type(rl_left
);
938 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
939 type
= rl_type(rl_right
);
940 if (type_positive_bits(type
) < 31)
943 rl_left
= cast_rl(type
, rl_left
);
944 rl_right
= cast_rl(type
, rl_right
);
946 FOR_EACH_PTR(rl_left
, tmp_left
) {
947 FOR_EACH_PTR(rl_right
, tmp_right
) {
948 if (true_comparison_range(tmp_left
, comparison
, tmp_right
))
950 } END_FOR_EACH_PTR(tmp_right
);
951 } END_FOR_EACH_PTR(tmp_left
);
955 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
957 struct range_list
*rl_left
, *rl_right
;
958 struct data_range
*tmp_left
, *tmp_right
;
961 if (!get_implied_rl(left
, &rl_left
))
963 if (!get_implied_rl(right
, &rl_right
))
966 type
= rl_type(rl_left
);
967 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
968 type
= rl_type(rl_right
);
969 if (type_positive_bits(type
) < 31)
972 rl_left
= cast_rl(type
, rl_left
);
973 rl_right
= cast_rl(type
, rl_right
);
975 FOR_EACH_PTR(rl_left
, tmp_left
) {
976 FOR_EACH_PTR(rl_right
, tmp_right
) {
977 if (false_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
979 } END_FOR_EACH_PTR(tmp_right
);
980 } END_FOR_EACH_PTR(tmp_left
);
984 int possibly_true_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
986 struct data_range
*left_tmp
, *right_tmp
;
989 if (!left_ranges
|| !right_ranges
)
992 type
= rl_type(left_ranges
);
993 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
994 type
= rl_type(right_ranges
);
995 if (type_positive_bits(type
) < 31)
998 left_ranges
= cast_rl(type
, left_ranges
);
999 right_ranges
= cast_rl(type
, right_ranges
);
1001 FOR_EACH_PTR(left_ranges
, left_tmp
) {
1002 FOR_EACH_PTR(right_ranges
, right_tmp
) {
1003 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
1005 } END_FOR_EACH_PTR(right_tmp
);
1006 } END_FOR_EACH_PTR(left_tmp
);
1010 int possibly_false_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
1012 struct data_range
*left_tmp
, *right_tmp
;
1013 struct symbol
*type
;
1015 if (!left_ranges
|| !right_ranges
)
1018 type
= rl_type(left_ranges
);
1019 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
1020 type
= rl_type(right_ranges
);
1021 if (type_positive_bits(type
) < 31)
1024 left_ranges
= cast_rl(type
, left_ranges
);
1025 right_ranges
= cast_rl(type
, right_ranges
);
1027 FOR_EACH_PTR(left_ranges
, left_tmp
) {
1028 FOR_EACH_PTR(right_ranges
, right_tmp
) {
1029 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
1031 } END_FOR_EACH_PTR(right_tmp
);
1032 } END_FOR_EACH_PTR(left_tmp
);
1036 /* FIXME: the _rl here stands for right left so really it should be _lr */
1037 int possibly_true_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1040 return possibly_true_rl(a
, comparison
, b
);
1042 return possibly_true_rl(b
, comparison
, a
);
1045 int possibly_false_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1048 return possibly_false_rl(a
, comparison
, b
);
1050 return possibly_false_rl(b
, comparison
, a
);
1053 int rl_has_sval(struct range_list
*rl
, sval_t sval
)
1055 struct data_range
*tmp
;
1057 FOR_EACH_PTR(rl
, tmp
) {
1058 if (sval_cmp(tmp
->min
, sval
) <= 0 &&
1059 sval_cmp(tmp
->max
, sval
) >= 0)
1061 } END_FOR_EACH_PTR(tmp
);
1065 void tack_on(struct range_list
**list
, struct data_range
*drange
)
1067 add_ptr_list(list
, drange
);
1070 void push_rl(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
1072 add_ptr_list(rl_stack
, rl
);
1075 struct range_list
*pop_rl(struct range_list_stack
**rl_stack
)
1077 struct range_list
*rl
;
1079 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1080 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1084 struct range_list
*top_rl(struct range_list_stack
*rl_stack
)
1086 struct range_list
*rl
;
1088 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1092 void filter_top_rl(struct range_list_stack
**rl_stack
, struct range_list
*filter
)
1094 struct range_list
*rl
;
1096 rl
= pop_rl(rl_stack
);
1097 rl
= rl_filter(rl
, filter
);
1098 push_rl(rl_stack
, rl
);
1101 struct range_list
*rl_truncate_cast(struct symbol
*type
, struct range_list
*rl
)
1103 struct data_range
*tmp
;
1104 struct range_list
*ret
= NULL
;
1110 if (!type
|| type
== rl_type(rl
))
1113 FOR_EACH_PTR(rl
, tmp
) {
1116 if (type_bits(type
) < type_bits(rl_type(rl
))) {
1117 min
.uvalue
= tmp
->min
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1118 max
.uvalue
= tmp
->max
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1120 if (sval_cmp(min
, max
) > 0) {
1121 min
= sval_cast(type
, min
);
1122 max
= sval_cast(type
, max
);
1124 add_range_t(type
, &ret
, min
, max
);
1125 } END_FOR_EACH_PTR(tmp
);
1130 static int rl_is_sane(struct range_list
*rl
)
1132 struct data_range
*tmp
;
1133 struct symbol
*type
;
1136 FOR_EACH_PTR(rl
, tmp
) {
1137 if (!sval_fits(type
, tmp
->min
))
1139 if (!sval_fits(type
, tmp
->max
))
1141 if (sval_cmp(tmp
->min
, tmp
->max
) > 0)
1143 } END_FOR_EACH_PTR(tmp
);
1148 static int rl_type_consistent(struct range_list
*rl
)
1150 struct data_range
*tmp
;
1151 struct symbol
*type
;
1154 FOR_EACH_PTR(rl
, tmp
) {
1155 if (type
!= tmp
->min
.type
|| type
!= tmp
->max
.type
)
1157 } END_FOR_EACH_PTR(tmp
);
1161 static struct range_list
*cast_to_bool(struct range_list
*rl
)
1163 struct data_range
*tmp
;
1164 struct range_list
*ret
= NULL
;
1167 sval_t min
= { .type
= &bool_ctype
};
1168 sval_t max
= { .type
= &bool_ctype
};
1170 FOR_EACH_PTR(rl
, tmp
) {
1171 if (tmp
->min
.value
|| tmp
->max
.value
)
1173 if (sval_is_negative(tmp
->min
) &&
1174 sval_is_negative(tmp
->max
))
1176 if (tmp
->min
.value
== 0 ||
1177 tmp
->max
.value
== 0)
1179 if (sval_is_negative(tmp
->min
) &&
1182 } END_FOR_EACH_PTR(tmp
);
1189 add_range(&ret
, min
, max
);
1193 struct range_list
*cast_rl(struct symbol
*type
, struct range_list
*rl
)
1195 struct data_range
*tmp
;
1196 struct range_list
*ret
= NULL
;
1203 if (!rl_is_sane(rl
))
1204 return alloc_whole_rl(type
);
1205 if (type
== rl_type(rl
) && rl_type_consistent(rl
))
1208 if (type
== &bool_ctype
)
1209 return cast_to_bool(rl
);
1211 FOR_EACH_PTR(rl
, tmp
) {
1212 add_range_t(type
, &ret
, tmp
->min
, tmp
->max
);
1213 } END_FOR_EACH_PTR(tmp
);
1216 return alloc_whole_rl(type
);
1221 struct range_list
*rl_invert(struct range_list
*orig
)
1223 struct range_list
*ret
= NULL
;
1224 struct data_range
*tmp
;
1225 sval_t gap_min
, abs_max
, sval
;
1229 if (type_bits(rl_type(orig
)) < 0) /* void type mostly */
1232 gap_min
= sval_type_min(rl_min(orig
).type
);
1233 abs_max
= sval_type_max(rl_max(orig
).type
);
1235 FOR_EACH_PTR(orig
, tmp
) {
1236 if (sval_cmp(tmp
->min
, gap_min
) > 0) {
1237 sval
= sval_type_val(tmp
->min
.type
, tmp
->min
.value
- 1);
1238 add_range(&ret
, gap_min
, sval
);
1240 if (sval_cmp(tmp
->max
, abs_max
) == 0)
1242 gap_min
= sval_type_val(tmp
->max
.type
, tmp
->max
.value
+ 1);
1243 } END_FOR_EACH_PTR(tmp
);
1245 if (sval_cmp(gap_min
, abs_max
) <= 0)
1246 add_range(&ret
, gap_min
, abs_max
);
1251 struct range_list
*rl_filter(struct range_list
*rl
, struct range_list
*filter
)
1253 struct data_range
*tmp
;
1255 FOR_EACH_PTR(filter
, tmp
) {
1256 rl
= remove_range(rl
, tmp
->min
, tmp
->max
);
1257 } END_FOR_EACH_PTR(tmp
);
1262 struct range_list
*rl_intersection(struct range_list
*one
, struct range_list
*two
)
1264 struct range_list
*one_orig
;
1265 struct range_list
*two_orig
;
1266 struct range_list
*ret
;
1267 struct symbol
*ret_type
;
1268 struct symbol
*small_type
;
1269 struct symbol
*large_type
;
1279 ret_type
= rl_type(one
);
1280 small_type
= rl_type(one
);
1281 large_type
= rl_type(two
);
1283 if (type_bits(rl_type(two
)) < type_bits(small_type
)) {
1284 small_type
= rl_type(two
);
1285 large_type
= rl_type(one
);
1288 one
= cast_rl(large_type
, one
);
1289 two
= cast_rl(large_type
, two
);
1292 one
= rl_invert(one
);
1293 two
= rl_invert(two
);
1295 ret
= rl_filter(ret
, one
);
1296 ret
= rl_filter(ret
, two
);
1298 one
= cast_rl(small_type
, one_orig
);
1299 two
= cast_rl(small_type
, two_orig
);
1301 one
= rl_invert(one
);
1302 two
= rl_invert(two
);
1304 ret
= cast_rl(small_type
, ret
);
1305 ret
= rl_filter(ret
, one
);
1306 ret
= rl_filter(ret
, two
);
1308 return cast_rl(ret_type
, ret
);
1311 static struct range_list
*handle_mod_rl(struct range_list
*left
, struct range_list
*right
)
1316 max
= rl_max(right
);
1317 if (sval_is_max(max
))
1322 if (sval_is_negative(max
))
1324 if (sval_cmp(rl_max(left
), max
) < 0)
1328 return alloc_rl(zero
, max
);
1331 static struct range_list
*get_neg_rl(struct range_list
*rl
)
1333 struct data_range
*tmp
;
1334 struct data_range
*new;
1335 struct range_list
*ret
= NULL
;
1339 if (sval_is_positive(rl_min(rl
)))
1342 FOR_EACH_PTR(rl
, tmp
) {
1343 if (sval_is_positive(tmp
->min
))
1345 if (sval_is_positive(tmp
->max
)) {
1346 new = alloc_range(tmp
->min
, tmp
->max
);
1347 new->max
.value
= -1;
1348 add_range(&ret
, new->min
, new->max
);
1351 add_range(&ret
, tmp
->min
, tmp
->max
);
1352 } END_FOR_EACH_PTR(tmp
);
1357 static struct range_list
*get_pos_rl(struct range_list
*rl
)
1359 struct data_range
*tmp
;
1360 struct data_range
*new;
1361 struct range_list
*ret
= NULL
;
1365 if (sval_is_negative(rl_max(rl
)))
1368 FOR_EACH_PTR(rl
, tmp
) {
1369 if (sval_is_negative(tmp
->max
))
1371 if (sval_is_positive(tmp
->min
)) {
1372 add_range(&ret
, tmp
->min
, tmp
->max
);
1375 new = alloc_range(tmp
->min
, tmp
->max
);
1377 add_range(&ret
, new->min
, new->max
);
1378 } END_FOR_EACH_PTR(tmp
);
1383 static struct range_list
*divide_rl_helper(struct range_list
*left
, struct range_list
*right
)
1385 sval_t right_min
, right_max
;
1388 if (!left
|| !right
)
1391 /* let's assume we never divide by zero */
1392 right_min
= rl_min(right
);
1393 right_max
= rl_max(right
);
1394 if (right_min
.value
== 0 && right_max
.value
== 0)
1396 if (right_min
.value
== 0)
1397 right_min
.value
= 1;
1398 if (right_max
.value
== 0)
1399 right_max
.value
= -1;
1401 max
= sval_binop(rl_max(left
), '/', right_min
);
1402 min
= sval_binop(rl_min(left
), '/', right_max
);
1404 return alloc_rl(min
, max
);
1407 static struct range_list
*handle_divide_rl(struct range_list
*left
, struct range_list
*right
)
1409 struct range_list
*left_neg
, *left_pos
, *right_neg
, *right_pos
;
1410 struct range_list
*neg_neg
, *neg_pos
, *pos_neg
, *pos_pos
;
1411 struct range_list
*ret
;
1413 if (is_whole_rl(right
))
1416 left_neg
= get_neg_rl(left
);
1417 left_pos
= get_pos_rl(left
);
1418 right_neg
= get_neg_rl(right
);
1419 right_pos
= get_pos_rl(right
);
1421 neg_neg
= divide_rl_helper(left_neg
, right_neg
);
1422 neg_pos
= divide_rl_helper(left_neg
, right_pos
);
1423 pos_neg
= divide_rl_helper(left_pos
, right_neg
);
1424 pos_pos
= divide_rl_helper(left_pos
, right_pos
);
1426 ret
= rl_union(neg_neg
, neg_pos
);
1427 ret
= rl_union(ret
, pos_neg
);
1428 return rl_union(ret
, pos_pos
);
1431 static struct range_list
*handle_add_mult_rl(struct range_list
*left
, int op
, struct range_list
*right
)
1435 if (sval_binop_overflows(rl_min(left
), op
, rl_min(right
)))
1437 min
= sval_binop(rl_min(left
), op
, rl_min(right
));
1439 if (sval_binop_overflows(rl_max(left
), op
, rl_max(right
)))
1441 max
= sval_binop(rl_max(left
), op
, rl_max(right
));
1443 return alloc_rl(min
, max
);
1446 static unsigned long long rl_bits_always_set(struct range_list
*rl
)
1448 return sval_fls_mask(rl_min(rl
));
1451 static unsigned long long rl_bits_maybe_set(struct range_list
*rl
)
1453 return sval_fls_mask(rl_max(rl
));
1456 static struct range_list
*handle_OR_rl(struct range_list
*left
, struct range_list
*right
)
1458 unsigned long long left_min
, left_max
, right_min
, right_max
;
1462 if ((rl_to_sval(left
, &sval
) || rl_to_sval(right
, &sval
)) &&
1463 !sval_binop_overflows(rl_max(left
), '+', rl_max(right
)))
1464 return rl_binop(left
, '+', right
);
1466 left_min
= rl_bits_always_set(left
);
1467 left_max
= rl_bits_maybe_set(left
);
1468 right_min
= rl_bits_always_set(right
);
1469 right_max
= rl_bits_maybe_set(right
);
1471 min
.type
= max
.type
= &ullong_ctype
;
1472 min
.uvalue
= left_min
| right_min
;
1473 max
.uvalue
= left_max
| right_max
;
1475 return cast_rl(rl_type(left
), alloc_rl(min
, max
));
1478 static struct range_list
*handle_XOR_rl(struct range_list
*left
, struct range_list
*right
)
1480 unsigned long long left_set
, left_maybe
;
1481 unsigned long long right_set
, right_maybe
;
1484 left_set
= rl_bits_always_set(left
);
1485 left_maybe
= rl_bits_maybe_set(left
);
1487 right_set
= rl_bits_always_set(right
);
1488 right_maybe
= rl_bits_maybe_set(right
);
1490 zero
= max
= rl_min(left
);
1492 max
.uvalue
= fls_mask((left_maybe
| right_maybe
) ^ (left_set
& right_set
));
1494 return cast_rl(rl_type(left
), alloc_rl(zero
, max
));
1497 struct range_list
*rl_binop(struct range_list
*left
, int op
, struct range_list
*right
)
1499 struct symbol
*cast_type
;
1500 sval_t left_sval
, right_sval
;
1501 struct range_list
*ret
= NULL
;
1503 cast_type
= rl_type(left
);
1504 if (sval_type_max(rl_type(left
)).uvalue
< sval_type_max(rl_type(right
)).uvalue
)
1505 cast_type
= rl_type(right
);
1506 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
1507 cast_type
= &int_ctype
;
1509 left
= cast_rl(cast_type
, left
);
1510 right
= cast_rl(cast_type
, right
);
1512 if (!left
|| !right
)
1513 return alloc_whole_rl(cast_type
);
1515 if (rl_to_sval(left
, &left_sval
) && rl_to_sval(right
, &right_sval
)) {
1516 sval_t val
= sval_binop(left_sval
, op
, right_sval
);
1517 return alloc_rl(val
, val
);
1522 ret
= handle_mod_rl(left
, right
);
1525 ret
= handle_divide_rl(left
, right
);
1529 ret
= handle_add_mult_rl(left
, op
, right
);
1532 ret
= handle_OR_rl(left
, right
);
1535 ret
= handle_XOR_rl(left
, right
);
1538 /* FIXME: Do the rest as well */
1541 case SPECIAL_RIGHTSHIFT
:
1542 case SPECIAL_LEFTSHIFT
:
1547 ret
= alloc_whole_rl(cast_type
);
1551 void free_rl(struct range_list
**rlist
)
1553 __free_ptr_list((struct ptr_list
**)rlist
);
1556 static void free_single_dinfo(struct data_info
*dinfo
)
1558 free_rl(&dinfo
->value_ranges
);
1561 static void free_dinfos(struct allocation_blob
*blob
)
1563 unsigned int size
= sizeof(struct data_info
);
1564 unsigned int offset
= 0;
1566 while (offset
< blob
->offset
) {
1567 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
1572 void free_data_info_allocs(void)
1574 struct allocator_struct
*desc
= &data_info_allocator
;
1575 struct allocation_blob
*blob
= desc
->blobs
;
1578 desc
->allocations
= 0;
1579 desc
->total_bytes
= 0;
1580 desc
->useful_bytes
= 0;
1581 desc
->freelist
= NULL
;
1583 struct allocation_blob
*next
= blob
->next
;
1585 blob_free(blob
, desc
->chunking
);
1588 clear_data_range_alloc();
1591 void split_comparison_rl(struct range_list
*left_orig
, int op
, struct range_list
*right_orig
,
1592 struct range_list
**left_true_rl
, struct range_list
**left_false_rl
,
1593 struct range_list
**right_true_rl
, struct range_list
**right_false_rl
)
1595 struct range_list
*left_true
, *left_false
;
1596 struct range_list
*right_true
, *right_false
;
1599 min
= sval_type_min(rl_type(left_orig
));
1600 max
= sval_type_max(rl_type(left_orig
));
1602 left_true
= clone_rl(left_orig
);
1603 left_false
= clone_rl(left_orig
);
1604 right_true
= clone_rl(right_orig
);
1605 right_false
= clone_rl(right_orig
);
1609 case SPECIAL_UNSIGNED_LT
:
1610 left_true
= remove_range(left_orig
, rl_max(right_orig
), max
);
1611 if (!sval_is_min(rl_min(right_orig
))) {
1612 left_false
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1615 right_true
= remove_range(right_orig
, min
, rl_min(left_orig
));
1616 if (!sval_is_max(rl_max(left_orig
)))
1617 right_false
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1619 case SPECIAL_UNSIGNED_LTE
:
1621 if (!sval_is_max(rl_max(right_orig
)))
1622 left_true
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1623 left_false
= remove_range(left_orig
, min
, rl_min(right_orig
));
1625 if (!sval_is_min(rl_min(left_orig
)))
1626 right_true
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1627 right_false
= remove_range(right_orig
, rl_max(left_orig
), max
);
1629 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1630 left_false
= remove_range(left_false
, rl_min(left_orig
), rl_min(left_orig
));
1631 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1632 right_false
= remove_range(right_false
, rl_max(left_orig
), rl_max(left_orig
));
1635 if (!sval_is_max(rl_max(right_orig
))) {
1636 left_true
= remove_range(left_true
, add_one(rl_max(right_orig
)), max
);
1638 if (!sval_is_min(rl_min(right_orig
))) {
1639 left_true
= remove_range(left_true
, min
, sub_one(rl_min(right_orig
)));
1641 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1642 left_false
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1644 if (!sval_is_max(rl_max(left_orig
)))
1645 right_true
= remove_range(right_true
, add_one(rl_max(left_orig
)), max
);
1646 if (!sval_is_min(rl_min(left_orig
)))
1647 right_true
= remove_range(right_true
, min
, sub_one(rl_min(left_orig
)));
1648 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1649 right_false
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1651 case SPECIAL_UNSIGNED_GTE
:
1653 if (!sval_is_min(rl_min(right_orig
)))
1654 left_true
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1655 left_false
= remove_range(left_orig
, rl_max(right_orig
), max
);
1657 if (!sval_is_max(rl_max(left_orig
)))
1658 right_true
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1659 right_false
= remove_range(right_orig
, min
, rl_min(left_orig
));
1661 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1662 right_false
= remove_range(right_false
, rl_min(left_orig
), rl_min(left_orig
));
1663 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1664 left_false
= remove_range(left_false
, rl_max(left_orig
), rl_max(left_orig
));
1667 case SPECIAL_UNSIGNED_GT
:
1668 left_true
= remove_range(left_orig
, min
, rl_min(right_orig
));
1669 if (!sval_is_max(rl_max(right_orig
)))
1670 left_false
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1672 right_true
= remove_range(right_orig
, rl_max(left_orig
), max
);
1673 if (!sval_is_min(rl_min(left_orig
)))
1674 right_false
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1676 case SPECIAL_NOTEQUAL
:
1677 if (!sval_is_max(rl_max(right_orig
)))
1678 left_false
= remove_range(left_false
, add_one(rl_max(right_orig
)), max
);
1679 if (!sval_is_min(rl_min(right_orig
)))
1680 left_false
= remove_range(left_false
, min
, sub_one(rl_min(right_orig
)));
1681 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1682 left_true
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1684 if (!sval_is_max(rl_max(left_orig
)))
1685 right_false
= remove_range(right_false
, add_one(rl_max(left_orig
)), max
);
1686 if (!sval_is_min(rl_min(left_orig
)))
1687 right_false
= remove_range(right_false
, min
, sub_one(rl_min(left_orig
)));
1688 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1689 right_true
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1692 sm_msg("internal error: unhandled comparison %d", op
);
1697 *left_true_rl
= left_true
;
1698 *left_false_rl
= left_false
;
1700 if (right_true_rl
) {
1701 *right_true_rl
= right_true
;
1702 *right_false_rl
= right_false
;