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
)
300 struct expression
*arg
;
301 struct range_list
*casted_start
, *right_orig
;
304 if (!str_to_comparison_arg_helper(c
, call
, &comparison
, &arg
, endp
))
307 if (!get_implied_rl(arg
, &right_orig
))
311 if (type_positive_bits(rl_type(start_rl
)) > type_positive_bits(type
))
312 type
= rl_type(start_rl
);
313 if (type_positive_bits(rl_type(right_orig
)) > type_positive_bits(type
))
314 type
= rl_type(right_orig
);
316 casted_start
= cast_rl(type
, start_rl
);
317 right_orig
= cast_rl(type
, right_orig
);
319 filter_by_comparison(&casted_start
, comparison
, right_orig
);
320 return cast_rl(rl_type(start_rl
), casted_start
);
323 static sval_t
parse_val(int use_max
, struct expression
*call
, struct symbol
*type
, char *c
, char **endp
)
328 if (!strncmp(start
, "max", 3)) {
329 ret
= sval_type_max(type
);
331 } else if (!strncmp(start
, "u64max", 6)) {
332 ret
= sval_type_val(type
, ULLONG_MAX
);
334 } else if (!strncmp(start
, "s64max", 6)) {
335 ret
= sval_type_val(type
, LLONG_MAX
);
337 } else if (!strncmp(start
, "u32max", 6)) {
338 ret
= sval_type_val(type
, UINT_MAX
);
340 } else if (!strncmp(start
, "s32max", 6)) {
341 ret
= sval_type_val(type
, INT_MAX
);
343 } else if (!strncmp(start
, "u16max", 6)) {
344 ret
= sval_type_val(type
, USHRT_MAX
);
346 } else if (!strncmp(start
, "s16max", 6)) {
347 ret
= sval_type_val(type
, SHRT_MAX
);
349 } else if (!strncmp(start
, "min", 3)) {
350 ret
= sval_type_min(type
);
352 } else if (!strncmp(start
, "s64min", 6)) {
353 ret
= sval_type_val(type
, LLONG_MIN
);
355 } else if (!strncmp(start
, "s32min", 6)) {
356 ret
= sval_type_val(type
, INT_MIN
);
358 } else if (!strncmp(start
, "s16min", 6)) {
359 ret
= sval_type_val(type
, SHRT_MIN
);
361 } else if (!strncmp(start
, "long_min", 8)) {
362 ret
= sval_type_val(type
, LONG_MIN
);
364 } else if (!strncmp(start
, "long_max", 8)) {
365 ret
= sval_type_val(type
, LONG_MAX
);
367 } else if (!strncmp(start
, "ulong_max", 9)) {
368 ret
= sval_type_val(type
, ULONG_MAX
);
370 } else if (!strncmp(start
, "ptr_max", 7)) {
371 ret
= sval_type_val(type
, valid_ptr_max
);
373 } else if (start
[0] == '[') {
374 /* this parses [==p0] comparisons */
375 get_val_from_key(1, type
, start
, call
, &c
, &ret
);
376 } else if (type_positive_bits(type
) == 64) {
377 ret
= sval_type_val(type
, strtoull(start
, &c
, 10));
379 ret
= sval_type_val(type
, strtoll(start
, &c
, 10));
385 static char *jump_to_call_math(char *value
)
389 while (*c
&& *c
!= '[')
395 if (*c
== '<' || *c
== '=' || *c
== '>' || *c
== '!')
401 static void str_to_rl_helper(struct expression
*call
, struct symbol
*type
, char *str
, char **endp
, struct range_list
**rl
)
403 struct range_list
*rl_tmp
= NULL
;
407 min
= sval_type_min(type
);
408 max
= sval_type_max(type
);
410 while (*c
!= '\0' && *c
!= '[') {
413 min
= parse_val(0, call
, type
, c
, &c
);
414 if (!sval_fits(type
, min
))
415 min
= sval_type_min(type
);
419 if (*c
== '\0' || *c
== '[') {
420 add_range_t(type
, &rl_tmp
, min
, min
);
424 add_range_t(type
, &rl_tmp
, min
, min
);
429 sm_msg("debug XXX: trouble parsing %s c = %s", str
, c
);
435 max
= parse_val(1, call
, type
, c
, &c
);
436 if (!sval_fits(type
, max
))
437 max
= sval_type_max(type
);
438 add_range_t(type
, &rl_tmp
, min
, max
);
449 static void str_to_dinfo(struct expression
*call
, struct symbol
*type
, char *value
, struct data_info
*dinfo
)
451 struct range_list
*math_rl
;
454 struct range_list
*rl
= NULL
;
459 if (strcmp(value
, "empty") == 0)
462 if (strncmp(value
, "[==$", 4) == 0) {
463 struct expression
*arg
;
466 if (!str_to_comparison_arg(value
, call
, &comparison
, &arg
))
468 if (!get_implied_rl(arg
, &rl
))
473 str_to_rl_helper(call
, type
, value
, &c
, &rl
);
477 call_math
= jump_to_call_math(value
);
478 if (call_math
&& parse_call_math_rl(call
, call_math
, &math_rl
)) {
479 rl
= rl_intersection(rl
, math_rl
);
484 * For now if we already tried to handle the call math and couldn't
485 * figure it out then bail.
487 if (jump_to_call_math(c
) == c
+ 1)
490 rl
= filter_by_comparison_call(c
, call
, &c
, rl
);
493 rl
= cast_rl(type
, rl
);
494 dinfo
->value_ranges
= rl
;
497 void str_to_rl(struct symbol
*type
, char *value
, struct range_list
**rl
)
499 struct data_info dinfo
= {};
501 str_to_dinfo(NULL
, type
, value
, &dinfo
);
502 *rl
= dinfo
.value_ranges
;
505 void call_results_to_rl(struct expression
*expr
, struct symbol
*type
, char *value
, struct range_list
**rl
)
507 struct data_info dinfo
= {};
509 str_to_dinfo(strip_expr(expr
), type
, value
, &dinfo
);
510 *rl
= dinfo
.value_ranges
;
513 int is_whole_rl(struct range_list
*rl
)
515 struct data_range
*drange
;
517 if (ptr_list_empty(rl
))
519 drange
= first_ptr_list((struct ptr_list
*)rl
);
520 if (sval_is_min(drange
->min
) && sval_is_max(drange
->max
))
525 int is_whole_rl_non_zero(struct range_list
*rl
)
527 struct data_range
*drange
;
529 if (ptr_list_empty(rl
))
531 drange
= first_ptr_list((struct ptr_list
*)rl
);
532 if (sval_unsigned(drange
->min
) &&
533 drange
->min
.value
== 1 &&
534 sval_is_max(drange
->max
))
536 if (!sval_is_min(drange
->min
) || drange
->max
.value
!= -1)
538 drange
= last_ptr_list((struct ptr_list
*)rl
);
539 if (drange
->min
.value
!= 1 || !sval_is_max(drange
->max
))
544 sval_t
rl_min(struct range_list
*rl
)
546 struct data_range
*drange
;
549 ret
.type
= &llong_ctype
;
550 ret
.value
= LLONG_MIN
;
551 if (ptr_list_empty(rl
))
553 drange
= first_ptr_list((struct ptr_list
*)rl
);
557 sval_t
rl_max(struct range_list
*rl
)
559 struct data_range
*drange
;
562 ret
.type
= &llong_ctype
;
563 ret
.value
= LLONG_MAX
;
564 if (ptr_list_empty(rl
))
566 drange
= last_ptr_list((struct ptr_list
*)rl
);
570 int rl_to_sval(struct range_list
*rl
, sval_t
*sval
)
579 if (sval_cmp(min
, max
) != 0)
585 struct symbol
*rl_type(struct range_list
*rl
)
589 return rl_min(rl
).type
;
592 static struct data_range
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
594 struct data_range
*ret
;
597 ret
= __alloc_perm_data_range(0);
599 ret
= __alloc_data_range(0);
605 struct data_range
*alloc_range(sval_t min
, sval_t max
)
607 return alloc_range_helper_sval(min
, max
, 0);
610 struct data_range
*alloc_range_perm(sval_t min
, sval_t max
)
612 return alloc_range_helper_sval(min
, max
, 1);
615 struct range_list
*alloc_rl(sval_t min
, sval_t max
)
617 struct range_list
*rl
= NULL
;
619 if (sval_cmp(min
, max
) > 0)
620 return alloc_whole_rl(min
.type
);
622 add_range(&rl
, min
, max
);
626 struct range_list
*alloc_whole_rl(struct symbol
*type
)
628 if (!type
|| type_positive_bits(type
) < 0)
630 if (type
->type
== SYM_ARRAY
)
633 return alloc_rl(sval_type_min(type
), sval_type_max(type
));
636 void add_range(struct range_list
**list
, sval_t min
, sval_t max
)
638 struct data_range
*tmp
;
639 struct data_range
*new = NULL
;
643 * There is at least on valid reason why the types might be confusing
644 * and that's when you have a void pointer and on some paths you treat
645 * it as a u8 pointer and on other paths you treat it as a u16 pointer.
646 * This case is hard to deal with.
648 * There are other cases where we probably should be more specific about
649 * the types than we are. For example, we end up merging a lot of ulong
650 * with pointers and I have not figured out why we do that.
652 * But this hack works for both cases, I think. We cast it to pointers
653 * or we use the bigger size.
656 if (*list
&& rl_type(*list
) != min
.type
) {
657 if (rl_type(*list
)->type
== SYM_PTR
) {
658 min
= sval_cast(rl_type(*list
), min
);
659 max
= sval_cast(rl_type(*list
), max
);
660 } else if (min
.type
->type
== SYM_PTR
) {
661 *list
= cast_rl(min
.type
, *list
);
662 } else if (type_bits(rl_type(*list
)) >= type_bits(min
.type
)) {
663 min
= sval_cast(rl_type(*list
), min
);
664 max
= sval_cast(rl_type(*list
), max
);
666 *list
= cast_rl(min
.type
, *list
);
670 if (sval_cmp(min
, max
) > 0) {
671 min
= sval_type_min(min
.type
);
672 max
= sval_type_max(min
.type
);
676 * FIXME: This has a problem merging a range_list like: min-0,3-max
677 * with a range like 1-2. You end up with min-2,3-max instead of
680 FOR_EACH_PTR(*list
, tmp
) {
682 /* Sometimes we overlap with more than one range
683 so we have to delete or modify the next range. */
684 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
685 /* join 2 ranges here */
687 DELETE_CURRENT_PTR(tmp
);
691 /* Doesn't overlap with the next one. */
692 if (sval_cmp(max
, tmp
->min
) < 0)
695 if (sval_cmp(max
, tmp
->max
) <= 0) {
696 /* Partially overlaps the next one. */
698 DELETE_CURRENT_PTR(tmp
);
701 /* Completely overlaps the next one. */
702 DELETE_CURRENT_PTR(tmp
);
703 /* there could be more ranges to delete */
707 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
708 /* join 2 ranges into a big range */
709 new = alloc_range(min
, tmp
->max
);
710 REPLACE_CURRENT_PTR(tmp
, new);
713 if (sval_cmp(max
, tmp
->min
) < 0) { /* new range entirely below */
714 new = alloc_range(min
, max
);
715 INSERT_CURRENT(new, tmp
);
718 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
719 if (sval_cmp(max
, tmp
->max
) < 0)
723 new = alloc_range(min
, max
);
724 REPLACE_CURRENT_PTR(tmp
, new);
729 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
731 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
733 new = alloc_range(min
, max
);
734 REPLACE_CURRENT_PTR(tmp
, new);
738 if (!sval_is_min(min
) && min
.value
- 1 == tmp
->max
.value
) {
739 /* join 2 ranges into a big range */
740 new = alloc_range(tmp
->min
, max
);
741 REPLACE_CURRENT_PTR(tmp
, new);
745 /* the new range is entirely above the existing ranges */
746 } END_FOR_EACH_PTR(tmp
);
749 new = alloc_range(min
, max
);
750 add_ptr_list(list
, new);
753 struct range_list
*clone_rl(struct range_list
*list
)
755 struct data_range
*tmp
;
756 struct range_list
*ret
= NULL
;
758 FOR_EACH_PTR(list
, tmp
) {
759 add_ptr_list(&ret
, tmp
);
760 } END_FOR_EACH_PTR(tmp
);
764 struct range_list
*clone_rl_permanent(struct range_list
*list
)
766 struct data_range
*tmp
;
767 struct data_range
*new;
768 struct range_list
*ret
= NULL
;
770 FOR_EACH_PTR(list
, tmp
) {
771 new = alloc_range_perm(tmp
->min
, tmp
->max
);
772 add_ptr_list(&ret
, new);
773 } END_FOR_EACH_PTR(tmp
);
777 struct range_list
*rl_union(struct range_list
*one
, struct range_list
*two
)
779 struct data_range
*tmp
;
780 struct range_list
*ret
= NULL
;
782 FOR_EACH_PTR(one
, tmp
) {
783 add_range(&ret
, tmp
->min
, tmp
->max
);
784 } END_FOR_EACH_PTR(tmp
);
785 FOR_EACH_PTR(two
, tmp
) {
786 add_range(&ret
, tmp
->min
, tmp
->max
);
787 } END_FOR_EACH_PTR(tmp
);
791 struct range_list
*remove_range(struct range_list
*list
, sval_t min
, sval_t max
)
793 struct data_range
*tmp
;
794 struct range_list
*ret
= NULL
;
799 min
= sval_cast(rl_type(list
), min
);
800 max
= sval_cast(rl_type(list
), max
);
801 if (sval_cmp(min
, max
) > 0) {
807 FOR_EACH_PTR(list
, tmp
) {
808 if (sval_cmp(tmp
->max
, min
) < 0) {
809 add_range(&ret
, tmp
->min
, tmp
->max
);
812 if (sval_cmp(tmp
->min
, max
) > 0) {
813 add_range(&ret
, tmp
->min
, tmp
->max
);
816 if (sval_cmp(tmp
->min
, min
) >= 0 && sval_cmp(tmp
->max
, max
) <= 0)
818 if (sval_cmp(tmp
->min
, min
) >= 0) {
820 add_range(&ret
, max
, tmp
->max
);
821 } else if (sval_cmp(tmp
->max
, max
) <= 0) {
823 add_range(&ret
, tmp
->min
, min
);
827 add_range(&ret
, tmp
->min
, min
);
828 add_range(&ret
, max
, tmp
->max
);
830 } END_FOR_EACH_PTR(tmp
);
834 int ranges_equiv(struct data_range
*one
, struct data_range
*two
)
840 if (sval_cmp(one
->min
, two
->min
) != 0)
842 if (sval_cmp(one
->max
, two
->max
) != 0)
847 int rl_equiv(struct range_list
*one
, struct range_list
*two
)
849 struct data_range
*one_range
;
850 struct data_range
*two_range
;
855 PREPARE_PTR_LIST(one
, one_range
);
856 PREPARE_PTR_LIST(two
, two_range
);
858 if (!one_range
&& !two_range
)
860 if (!ranges_equiv(one_range
, two_range
))
862 NEXT_PTR_LIST(one_range
);
863 NEXT_PTR_LIST(two_range
);
865 FINISH_PTR_LIST(two_range
);
866 FINISH_PTR_LIST(one_range
);
871 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
873 switch (comparison
) {
875 case SPECIAL_UNSIGNED_LT
:
876 if (sval_cmp(left
->min
, right
->max
) < 0)
879 case SPECIAL_UNSIGNED_LTE
:
881 if (sval_cmp(left
->min
, right
->max
) <= 0)
885 if (sval_cmp(left
->max
, right
->min
) < 0)
887 if (sval_cmp(left
->min
, right
->max
) > 0)
890 case SPECIAL_UNSIGNED_GTE
:
892 if (sval_cmp(left
->max
, right
->min
) >= 0)
896 case SPECIAL_UNSIGNED_GT
:
897 if (sval_cmp(left
->max
, right
->min
) > 0)
900 case SPECIAL_NOTEQUAL
:
901 if (sval_cmp(left
->min
, left
->max
) != 0)
903 if (sval_cmp(right
->min
, right
->max
) != 0)
905 if (sval_cmp(left
->min
, right
->min
) != 0)
909 sm_msg("unhandled comparison %d\n", comparison
);
915 int true_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
918 return true_comparison_range(var
, comparison
, val
);
920 return true_comparison_range(val
, comparison
, var
);
923 static int false_comparison_range_sval(struct data_range
*left
, int comparison
, struct data_range
*right
)
925 switch (comparison
) {
927 case SPECIAL_UNSIGNED_LT
:
928 if (sval_cmp(left
->max
, right
->min
) >= 0)
931 case SPECIAL_UNSIGNED_LTE
:
933 if (sval_cmp(left
->max
, right
->min
) > 0)
937 if (sval_cmp(left
->min
, left
->max
) != 0)
939 if (sval_cmp(right
->min
, right
->max
) != 0)
941 if (sval_cmp(left
->min
, right
->min
) != 0)
944 case SPECIAL_UNSIGNED_GTE
:
946 if (sval_cmp(left
->min
, right
->max
) < 0)
950 case SPECIAL_UNSIGNED_GT
:
951 if (sval_cmp(left
->min
, right
->max
) <= 0)
954 case SPECIAL_NOTEQUAL
:
955 if (sval_cmp(left
->max
, right
->min
) < 0)
957 if (sval_cmp(left
->min
, right
->max
) > 0)
961 sm_msg("unhandled comparison %d\n", comparison
);
967 int false_comparison_range_LR(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
970 return false_comparison_range_sval(var
, comparison
, val
);
972 return false_comparison_range_sval(val
, comparison
, var
);
975 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
977 struct range_list
*rl_left
, *rl_right
;
978 struct data_range
*tmp_left
, *tmp_right
;
981 if (!get_implied_rl(left
, &rl_left
))
983 if (!get_implied_rl(right
, &rl_right
))
986 type
= rl_type(rl_left
);
987 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
988 type
= rl_type(rl_right
);
989 if (type_positive_bits(type
) < 31)
992 rl_left
= cast_rl(type
, rl_left
);
993 rl_right
= cast_rl(type
, rl_right
);
995 FOR_EACH_PTR(rl_left
, tmp_left
) {
996 FOR_EACH_PTR(rl_right
, tmp_right
) {
997 if (true_comparison_range(tmp_left
, comparison
, tmp_right
))
999 } END_FOR_EACH_PTR(tmp_right
);
1000 } END_FOR_EACH_PTR(tmp_left
);
1004 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
1006 struct range_list
*rl_left
, *rl_right
;
1007 struct data_range
*tmp_left
, *tmp_right
;
1008 struct symbol
*type
;
1010 if (!get_implied_rl(left
, &rl_left
))
1012 if (!get_implied_rl(right
, &rl_right
))
1015 type
= rl_type(rl_left
);
1016 if (type_positive_bits(type
) < type_positive_bits(rl_type(rl_right
)))
1017 type
= rl_type(rl_right
);
1018 if (type_positive_bits(type
) < 31)
1021 rl_left
= cast_rl(type
, rl_left
);
1022 rl_right
= cast_rl(type
, rl_right
);
1024 FOR_EACH_PTR(rl_left
, tmp_left
) {
1025 FOR_EACH_PTR(rl_right
, tmp_right
) {
1026 if (false_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
1028 } END_FOR_EACH_PTR(tmp_right
);
1029 } END_FOR_EACH_PTR(tmp_left
);
1033 int possibly_true_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
1035 struct data_range
*left_tmp
, *right_tmp
;
1036 struct symbol
*type
;
1038 if (!left_ranges
|| !right_ranges
)
1041 type
= rl_type(left_ranges
);
1042 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
1043 type
= rl_type(right_ranges
);
1044 if (type_positive_bits(type
) < 31)
1047 left_ranges
= cast_rl(type
, left_ranges
);
1048 right_ranges
= cast_rl(type
, right_ranges
);
1050 FOR_EACH_PTR(left_ranges
, left_tmp
) {
1051 FOR_EACH_PTR(right_ranges
, right_tmp
) {
1052 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
1054 } END_FOR_EACH_PTR(right_tmp
);
1055 } END_FOR_EACH_PTR(left_tmp
);
1059 int possibly_false_rl(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
1061 struct data_range
*left_tmp
, *right_tmp
;
1062 struct symbol
*type
;
1064 if (!left_ranges
|| !right_ranges
)
1067 type
= rl_type(left_ranges
);
1068 if (type_positive_bits(type
) < type_positive_bits(rl_type(right_ranges
)))
1069 type
= rl_type(right_ranges
);
1070 if (type_positive_bits(type
) < 31)
1073 left_ranges
= cast_rl(type
, left_ranges
);
1074 right_ranges
= cast_rl(type
, right_ranges
);
1076 FOR_EACH_PTR(left_ranges
, left_tmp
) {
1077 FOR_EACH_PTR(right_ranges
, right_tmp
) {
1078 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
1080 } END_FOR_EACH_PTR(right_tmp
);
1081 } END_FOR_EACH_PTR(left_tmp
);
1085 /* FIXME: the _rl here stands for right left so really it should be _lr */
1086 int possibly_true_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1089 return possibly_true_rl(a
, comparison
, b
);
1091 return possibly_true_rl(b
, comparison
, a
);
1094 int possibly_false_rl_LR(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
1097 return possibly_false_rl(a
, comparison
, b
);
1099 return possibly_false_rl(b
, comparison
, a
);
1102 int rl_has_sval(struct range_list
*rl
, sval_t sval
)
1104 struct data_range
*tmp
;
1106 FOR_EACH_PTR(rl
, tmp
) {
1107 if (sval_cmp(tmp
->min
, sval
) <= 0 &&
1108 sval_cmp(tmp
->max
, sval
) >= 0)
1110 } END_FOR_EACH_PTR(tmp
);
1114 void tack_on(struct range_list
**list
, struct data_range
*drange
)
1116 add_ptr_list(list
, drange
);
1119 void push_rl(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
1121 add_ptr_list(rl_stack
, rl
);
1124 struct range_list
*pop_rl(struct range_list_stack
**rl_stack
)
1126 struct range_list
*rl
;
1128 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
1129 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
1133 struct range_list
*top_rl(struct range_list_stack
*rl_stack
)
1135 struct range_list
*rl
;
1137 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
1141 void filter_top_rl(struct range_list_stack
**rl_stack
, struct range_list
*filter
)
1143 struct range_list
*rl
;
1145 rl
= pop_rl(rl_stack
);
1146 rl
= rl_filter(rl
, filter
);
1147 push_rl(rl_stack
, rl
);
1150 struct range_list
*rl_truncate_cast(struct symbol
*type
, struct range_list
*rl
)
1152 struct data_range
*tmp
;
1153 struct range_list
*ret
= NULL
;
1159 if (!type
|| type
== rl_type(rl
))
1162 FOR_EACH_PTR(rl
, tmp
) {
1165 if (type_bits(type
) < type_bits(rl_type(rl
))) {
1166 min
.uvalue
= tmp
->min
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1167 max
.uvalue
= tmp
->max
.uvalue
& ((1ULL << type_bits(type
)) - 1);
1169 if (sval_cmp(min
, max
) > 0) {
1170 min
= sval_cast(type
, min
);
1171 max
= sval_cast(type
, max
);
1173 add_range_t(type
, &ret
, min
, max
);
1174 } END_FOR_EACH_PTR(tmp
);
1179 static int rl_is_sane(struct range_list
*rl
)
1181 struct data_range
*tmp
;
1182 struct symbol
*type
;
1185 FOR_EACH_PTR(rl
, tmp
) {
1186 if (!sval_fits(type
, tmp
->min
))
1188 if (!sval_fits(type
, tmp
->max
))
1190 if (sval_cmp(tmp
->min
, tmp
->max
) > 0)
1192 } END_FOR_EACH_PTR(tmp
);
1197 static int rl_type_consistent(struct range_list
*rl
)
1199 struct data_range
*tmp
;
1200 struct symbol
*type
;
1203 FOR_EACH_PTR(rl
, tmp
) {
1204 if (type
!= tmp
->min
.type
|| type
!= tmp
->max
.type
)
1206 } END_FOR_EACH_PTR(tmp
);
1210 static struct range_list
*cast_to_bool(struct range_list
*rl
)
1212 struct data_range
*tmp
;
1213 struct range_list
*ret
= NULL
;
1216 sval_t min
= { .type
= &bool_ctype
};
1217 sval_t max
= { .type
= &bool_ctype
};
1219 FOR_EACH_PTR(rl
, tmp
) {
1220 if (tmp
->min
.value
|| tmp
->max
.value
)
1222 if (sval_is_negative(tmp
->min
) &&
1223 sval_is_negative(tmp
->max
))
1225 if (tmp
->min
.value
== 0 ||
1226 tmp
->max
.value
== 0)
1228 if (sval_is_negative(tmp
->min
) &&
1231 } END_FOR_EACH_PTR(tmp
);
1238 add_range(&ret
, min
, max
);
1242 struct range_list
*cast_rl(struct symbol
*type
, struct range_list
*rl
)
1244 struct data_range
*tmp
;
1245 struct range_list
*ret
= NULL
;
1252 if (!rl_is_sane(rl
))
1253 return alloc_whole_rl(type
);
1254 if (type
== rl_type(rl
) && rl_type_consistent(rl
))
1257 if (type
== &bool_ctype
)
1258 return cast_to_bool(rl
);
1260 FOR_EACH_PTR(rl
, tmp
) {
1261 add_range_t(type
, &ret
, tmp
->min
, tmp
->max
);
1262 } END_FOR_EACH_PTR(tmp
);
1265 return alloc_whole_rl(type
);
1270 struct range_list
*rl_invert(struct range_list
*orig
)
1272 struct range_list
*ret
= NULL
;
1273 struct data_range
*tmp
;
1274 sval_t gap_min
, abs_max
, sval
;
1278 if (type_bits(rl_type(orig
)) < 0) /* void type mostly */
1281 gap_min
= sval_type_min(rl_min(orig
).type
);
1282 abs_max
= sval_type_max(rl_max(orig
).type
);
1284 FOR_EACH_PTR(orig
, tmp
) {
1285 if (sval_cmp(tmp
->min
, gap_min
) > 0) {
1286 sval
= sval_type_val(tmp
->min
.type
, tmp
->min
.value
- 1);
1287 add_range(&ret
, gap_min
, sval
);
1289 if (sval_cmp(tmp
->max
, abs_max
) == 0)
1291 gap_min
= sval_type_val(tmp
->max
.type
, tmp
->max
.value
+ 1);
1292 } END_FOR_EACH_PTR(tmp
);
1294 if (sval_cmp(gap_min
, abs_max
) <= 0)
1295 add_range(&ret
, gap_min
, abs_max
);
1300 struct range_list
*rl_filter(struct range_list
*rl
, struct range_list
*filter
)
1302 struct data_range
*tmp
;
1304 FOR_EACH_PTR(filter
, tmp
) {
1305 rl
= remove_range(rl
, tmp
->min
, tmp
->max
);
1306 } END_FOR_EACH_PTR(tmp
);
1311 struct range_list
*rl_intersection(struct range_list
*one
, struct range_list
*two
)
1313 struct range_list
*one_orig
;
1314 struct range_list
*two_orig
;
1315 struct range_list
*ret
;
1316 struct symbol
*ret_type
;
1317 struct symbol
*small_type
;
1318 struct symbol
*large_type
;
1328 ret_type
= rl_type(one
);
1329 small_type
= rl_type(one
);
1330 large_type
= rl_type(two
);
1332 if (type_bits(rl_type(two
)) < type_bits(small_type
)) {
1333 small_type
= rl_type(two
);
1334 large_type
= rl_type(one
);
1337 one
= cast_rl(large_type
, one
);
1338 two
= cast_rl(large_type
, two
);
1341 one
= rl_invert(one
);
1342 two
= rl_invert(two
);
1344 ret
= rl_filter(ret
, one
);
1345 ret
= rl_filter(ret
, two
);
1347 one
= cast_rl(small_type
, one_orig
);
1348 two
= cast_rl(small_type
, two_orig
);
1350 one
= rl_invert(one
);
1351 two
= rl_invert(two
);
1353 ret
= cast_rl(small_type
, ret
);
1354 ret
= rl_filter(ret
, one
);
1355 ret
= rl_filter(ret
, two
);
1357 return cast_rl(ret_type
, ret
);
1360 static struct range_list
*handle_mod_rl(struct range_list
*left
, struct range_list
*right
)
1365 max
= rl_max(right
);
1366 if (sval_is_max(max
))
1371 if (sval_is_negative(max
))
1373 if (sval_cmp(rl_max(left
), max
) < 0)
1377 return alloc_rl(zero
, max
);
1380 static struct range_list
*get_neg_rl(struct range_list
*rl
)
1382 struct data_range
*tmp
;
1383 struct data_range
*new;
1384 struct range_list
*ret
= NULL
;
1388 if (sval_is_positive(rl_min(rl
)))
1391 FOR_EACH_PTR(rl
, tmp
) {
1392 if (sval_is_positive(tmp
->min
))
1394 if (sval_is_positive(tmp
->max
)) {
1395 new = alloc_range(tmp
->min
, tmp
->max
);
1396 new->max
.value
= -1;
1397 add_range(&ret
, new->min
, new->max
);
1400 add_range(&ret
, tmp
->min
, tmp
->max
);
1401 } END_FOR_EACH_PTR(tmp
);
1406 static struct range_list
*get_pos_rl(struct range_list
*rl
)
1408 struct data_range
*tmp
;
1409 struct data_range
*new;
1410 struct range_list
*ret
= NULL
;
1414 if (sval_is_negative(rl_max(rl
)))
1417 FOR_EACH_PTR(rl
, tmp
) {
1418 if (sval_is_negative(tmp
->max
))
1420 if (sval_is_positive(tmp
->min
)) {
1421 add_range(&ret
, tmp
->min
, tmp
->max
);
1424 new = alloc_range(tmp
->min
, tmp
->max
);
1426 add_range(&ret
, new->min
, new->max
);
1427 } END_FOR_EACH_PTR(tmp
);
1432 static struct range_list
*divide_rl_helper(struct range_list
*left
, struct range_list
*right
)
1434 sval_t right_min
, right_max
;
1437 if (!left
|| !right
)
1440 /* let's assume we never divide by zero */
1441 right_min
= rl_min(right
);
1442 right_max
= rl_max(right
);
1443 if (right_min
.value
== 0 && right_max
.value
== 0)
1445 if (right_min
.value
== 0)
1446 right_min
.value
= 1;
1447 if (right_max
.value
== 0)
1448 right_max
.value
= -1;
1450 max
= sval_binop(rl_max(left
), '/', right_min
);
1451 min
= sval_binop(rl_min(left
), '/', right_max
);
1453 return alloc_rl(min
, max
);
1456 static struct range_list
*handle_divide_rl(struct range_list
*left
, struct range_list
*right
)
1458 struct range_list
*left_neg
, *left_pos
, *right_neg
, *right_pos
;
1459 struct range_list
*neg_neg
, *neg_pos
, *pos_neg
, *pos_pos
;
1460 struct range_list
*ret
;
1462 if (is_whole_rl(right
))
1465 left_neg
= get_neg_rl(left
);
1466 left_pos
= get_pos_rl(left
);
1467 right_neg
= get_neg_rl(right
);
1468 right_pos
= get_pos_rl(right
);
1470 neg_neg
= divide_rl_helper(left_neg
, right_neg
);
1471 neg_pos
= divide_rl_helper(left_neg
, right_pos
);
1472 pos_neg
= divide_rl_helper(left_pos
, right_neg
);
1473 pos_pos
= divide_rl_helper(left_pos
, right_pos
);
1475 ret
= rl_union(neg_neg
, neg_pos
);
1476 ret
= rl_union(ret
, pos_neg
);
1477 return rl_union(ret
, pos_pos
);
1480 static struct range_list
*handle_add_mult_rl(struct range_list
*left
, int op
, struct range_list
*right
)
1484 if (sval_binop_overflows(rl_min(left
), op
, rl_min(right
)))
1486 min
= sval_binop(rl_min(left
), op
, rl_min(right
));
1488 if (sval_binop_overflows(rl_max(left
), op
, rl_max(right
)))
1490 max
= sval_binop(rl_max(left
), op
, rl_max(right
));
1492 return alloc_rl(min
, max
);
1495 static unsigned long long rl_bits_always_set(struct range_list
*rl
)
1497 return sval_fls_mask(rl_min(rl
));
1500 static unsigned long long rl_bits_maybe_set(struct range_list
*rl
)
1502 return sval_fls_mask(rl_max(rl
));
1505 static struct range_list
*handle_OR_rl(struct range_list
*left
, struct range_list
*right
)
1507 unsigned long long left_min
, left_max
, right_min
, right_max
;
1511 if ((rl_to_sval(left
, &sval
) || rl_to_sval(right
, &sval
)) &&
1512 !sval_binop_overflows(rl_max(left
), '+', rl_max(right
)))
1513 return rl_binop(left
, '+', right
);
1515 left_min
= rl_bits_always_set(left
);
1516 left_max
= rl_bits_maybe_set(left
);
1517 right_min
= rl_bits_always_set(right
);
1518 right_max
= rl_bits_maybe_set(right
);
1520 min
.type
= max
.type
= &ullong_ctype
;
1521 min
.uvalue
= left_min
| right_min
;
1522 max
.uvalue
= left_max
| right_max
;
1524 return cast_rl(rl_type(left
), alloc_rl(min
, max
));
1527 static struct range_list
*handle_XOR_rl(struct range_list
*left
, struct range_list
*right
)
1529 unsigned long long left_set
, left_maybe
;
1530 unsigned long long right_set
, right_maybe
;
1533 left_set
= rl_bits_always_set(left
);
1534 left_maybe
= rl_bits_maybe_set(left
);
1536 right_set
= rl_bits_always_set(right
);
1537 right_maybe
= rl_bits_maybe_set(right
);
1539 zero
= max
= rl_min(left
);
1541 max
.uvalue
= fls_mask((left_maybe
| right_maybe
) ^ (left_set
& right_set
));
1543 return cast_rl(rl_type(left
), alloc_rl(zero
, max
));
1546 static struct range_list
*handle_AND_rl(struct range_list
*left
, struct range_list
*right
)
1548 unsigned long long left_set
, left_maybe
;
1549 unsigned long long right_set
, right_maybe
;
1554 left_set
= rl_bits_always_set(left
);
1555 left_maybe
= rl_bits_maybe_set(left
);
1557 right_set
= rl_bits_always_set(right
);
1558 right_maybe
= rl_bits_maybe_set(right
);
1560 zero
= max
= rl_min(left
);
1562 max
.uvalue
= fls_mask((left_maybe
| right_maybe
) ^ (left_set
& right_set
));
1564 return cast_rl(rl_type(left
), alloc_rl(zero
, max
));
1567 struct range_list
*rl_binop(struct range_list
*left
, int op
, struct range_list
*right
)
1569 struct symbol
*cast_type
;
1570 sval_t left_sval
, right_sval
;
1571 struct range_list
*ret
= NULL
;
1573 cast_type
= rl_type(left
);
1574 if (sval_type_max(rl_type(left
)).uvalue
< sval_type_max(rl_type(right
)).uvalue
)
1575 cast_type
= rl_type(right
);
1576 if (sval_type_max(cast_type
).uvalue
< INT_MAX
)
1577 cast_type
= &int_ctype
;
1579 left
= cast_rl(cast_type
, left
);
1580 right
= cast_rl(cast_type
, right
);
1582 if (!left
|| !right
)
1583 return alloc_whole_rl(cast_type
);
1585 if (rl_to_sval(left
, &left_sval
) && rl_to_sval(right
, &right_sval
)) {
1586 sval_t val
= sval_binop(left_sval
, op
, right_sval
);
1587 return alloc_rl(val
, val
);
1592 ret
= handle_mod_rl(left
, right
);
1595 ret
= handle_divide_rl(left
, right
);
1599 ret
= handle_add_mult_rl(left
, op
, right
);
1602 ret
= handle_OR_rl(left
, right
);
1605 ret
= handle_XOR_rl(left
, right
);
1608 ret
= handle_AND_rl(left
, right
);
1611 /* FIXME: Do the rest as well */
1613 case SPECIAL_RIGHTSHIFT
:
1614 case SPECIAL_LEFTSHIFT
:
1619 ret
= alloc_whole_rl(cast_type
);
1623 void free_rl(struct range_list
**rlist
)
1625 __free_ptr_list((struct ptr_list
**)rlist
);
1628 static void free_single_dinfo(struct data_info
*dinfo
)
1630 free_rl(&dinfo
->value_ranges
);
1633 static void free_dinfos(struct allocation_blob
*blob
)
1635 unsigned int size
= sizeof(struct data_info
);
1636 unsigned int offset
= 0;
1638 while (offset
< blob
->offset
) {
1639 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
1644 void free_data_info_allocs(void)
1646 struct allocator_struct
*desc
= &data_info_allocator
;
1647 struct allocation_blob
*blob
= desc
->blobs
;
1650 desc
->allocations
= 0;
1651 desc
->total_bytes
= 0;
1652 desc
->useful_bytes
= 0;
1653 desc
->freelist
= NULL
;
1655 struct allocation_blob
*next
= blob
->next
;
1657 blob_free(blob
, desc
->chunking
);
1660 clear_data_range_alloc();
1663 void split_comparison_rl(struct range_list
*left_orig
, int op
, struct range_list
*right_orig
,
1664 struct range_list
**left_true_rl
, struct range_list
**left_false_rl
,
1665 struct range_list
**right_true_rl
, struct range_list
**right_false_rl
)
1667 struct range_list
*left_true
, *left_false
;
1668 struct range_list
*right_true
, *right_false
;
1671 min
= sval_type_min(rl_type(left_orig
));
1672 max
= sval_type_max(rl_type(left_orig
));
1674 left_true
= clone_rl(left_orig
);
1675 left_false
= clone_rl(left_orig
);
1676 right_true
= clone_rl(right_orig
);
1677 right_false
= clone_rl(right_orig
);
1681 case SPECIAL_UNSIGNED_LT
:
1682 left_true
= remove_range(left_orig
, rl_max(right_orig
), max
);
1683 if (!sval_is_min(rl_min(right_orig
))) {
1684 left_false
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1687 right_true
= remove_range(right_orig
, min
, rl_min(left_orig
));
1688 if (!sval_is_max(rl_max(left_orig
)))
1689 right_false
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1691 case SPECIAL_UNSIGNED_LTE
:
1693 if (!sval_is_max(rl_max(right_orig
)))
1694 left_true
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1695 left_false
= remove_range(left_orig
, min
, rl_min(right_orig
));
1697 if (!sval_is_min(rl_min(left_orig
)))
1698 right_true
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1699 right_false
= remove_range(right_orig
, rl_max(left_orig
), max
);
1701 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1702 left_false
= remove_range(left_false
, rl_min(left_orig
), rl_min(left_orig
));
1703 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1704 right_false
= remove_range(right_false
, rl_max(left_orig
), rl_max(left_orig
));
1707 if (!sval_is_max(rl_max(right_orig
))) {
1708 left_true
= remove_range(left_true
, add_one(rl_max(right_orig
)), max
);
1710 if (!sval_is_min(rl_min(right_orig
))) {
1711 left_true
= remove_range(left_true
, min
, sub_one(rl_min(right_orig
)));
1713 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1714 left_false
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1716 if (!sval_is_max(rl_max(left_orig
)))
1717 right_true
= remove_range(right_true
, add_one(rl_max(left_orig
)), max
);
1718 if (!sval_is_min(rl_min(left_orig
)))
1719 right_true
= remove_range(right_true
, min
, sub_one(rl_min(left_orig
)));
1720 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1721 right_false
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1723 case SPECIAL_UNSIGNED_GTE
:
1725 if (!sval_is_min(rl_min(right_orig
)))
1726 left_true
= remove_range(left_orig
, min
, sub_one(rl_min(right_orig
)));
1727 left_false
= remove_range(left_orig
, rl_max(right_orig
), max
);
1729 if (!sval_is_max(rl_max(left_orig
)))
1730 right_true
= remove_range(right_orig
, add_one(rl_max(left_orig
)), max
);
1731 right_false
= remove_range(right_orig
, min
, rl_min(left_orig
));
1733 if (sval_cmp(rl_min(left_orig
), rl_min(right_orig
)) == 0)
1734 right_false
= remove_range(right_false
, rl_min(left_orig
), rl_min(left_orig
));
1735 if (sval_cmp(rl_max(left_orig
), rl_max(right_orig
)) == 0)
1736 left_false
= remove_range(left_false
, rl_max(left_orig
), rl_max(left_orig
));
1739 case SPECIAL_UNSIGNED_GT
:
1740 left_true
= remove_range(left_orig
, min
, rl_min(right_orig
));
1741 if (!sval_is_max(rl_max(right_orig
)))
1742 left_false
= remove_range(left_orig
, add_one(rl_max(right_orig
)), max
);
1744 right_true
= remove_range(right_orig
, rl_max(left_orig
), max
);
1745 if (!sval_is_min(rl_min(left_orig
)))
1746 right_false
= remove_range(right_orig
, min
, sub_one(rl_min(left_orig
)));
1748 case SPECIAL_NOTEQUAL
:
1749 if (!sval_is_max(rl_max(right_orig
)))
1750 left_false
= remove_range(left_false
, add_one(rl_max(right_orig
)), max
);
1751 if (!sval_is_min(rl_min(right_orig
)))
1752 left_false
= remove_range(left_false
, min
, sub_one(rl_min(right_orig
)));
1753 if (sval_cmp(rl_min(right_orig
), rl_max(right_orig
)) == 0)
1754 left_true
= remove_range(left_orig
, rl_min(right_orig
), rl_min(right_orig
));
1756 if (!sval_is_max(rl_max(left_orig
)))
1757 right_false
= remove_range(right_false
, add_one(rl_max(left_orig
)), max
);
1758 if (!sval_is_min(rl_min(left_orig
)))
1759 right_false
= remove_range(right_false
, min
, sub_one(rl_min(left_orig
)));
1760 if (sval_cmp(rl_min(left_orig
), rl_max(left_orig
)) == 0)
1761 right_true
= remove_range(right_orig
, rl_min(left_orig
), rl_min(left_orig
));
1764 sm_msg("internal error: unhandled comparison %d", op
);
1769 *left_true_rl
= left_true
;
1770 *left_false_rl
= left_false
;
1772 if (right_true_rl
) {
1773 *right_true_rl
= right_true
;
1774 *right_false_rl
= right_false
;