kernel.return_fixes: add fls() and fls64()
[smatch.git] / smatch_ranges.c
blobc0d769978d51eee0aae0909c980f7c6f977eee43
1 /*
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
18 #include "parse.h"
19 #include "smatch.h"
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;
31 char full[256];
32 int i = 0;
34 full[0] = '\0';
35 full[255] = '\0';
36 FOR_EACH_PTR(list, tmp) {
37 if (i++)
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));
41 continue;
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))
54 return 0;
55 if (sval.uvalue <= ((1ULL << type_bits(type)) - 1))
56 return 0;
57 if (type_signed(sval.type)) {
58 if (sval.value < sval_type_min(type).value)
59 return 1;
60 if (sval.value > sval_type_max(type).value)
61 return 1;
62 return 0;
64 if (sval.uvalue > sval_type_max(type).uvalue)
65 return 1;
66 return 0;
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));
74 return;
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));
80 return;
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));
91 return;
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));
99 return;
101 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
102 max = sval_type_max(type);
103 } else {
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);
115 } else {
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));
123 return;
126 static int str_to_comparison_arg_helper(const char *str,
127 struct expression *call, int *comparison,
128 struct expression **arg, char **endp)
130 int param;
131 char *c = (char *)str;
133 if (*c != '[')
134 return 0;
135 c++;
137 if (*c == '<') {
138 c++;
139 if (*c == '=') {
140 *comparison = SPECIAL_LTE;
141 c++;
142 } else {
143 *comparison = '<';
145 } else if (*c == '=') {
146 c++;
147 c++;
148 *comparison = SPECIAL_EQUAL;
149 } else if (*c == '>') {
150 c++;
151 if (*c == '=') {
152 *comparison = SPECIAL_GTE;
153 c++;
154 } else {
155 *comparison = '>';
157 } else if (*c == '!') {
158 c++;
159 c++;
160 *comparison = SPECIAL_NOTEQUAL;
161 } else {
162 return 0;
165 if (*c != '$')
166 return 0;
167 c++;
169 param = strtoll(c, &c, 10);
170 c++; /* skip the ']' character */
171 if (endp)
172 *endp = (char *)c;
174 if (!call)
175 return 0;
176 *arg = get_argument_from_call_expr(call->args, param);
177 if (!*arg)
178 return 0;
179 return 1;
182 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
184 while (1) {
185 if (!*str)
186 return 0;
187 if (*str == '[')
188 break;
189 str++;
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;
197 int comparison;
198 sval_t ret, tmp;
200 if (use_max)
201 ret = sval_type_max(type);
202 else
203 ret = sval_type_min(type);
205 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
206 *sval = ret;
207 return 0;
210 if (use_max && get_implied_max(arg, &tmp)) {
211 ret = tmp;
212 if (comparison == '<') {
213 tmp.value = 1;
214 ret = sval_binop(ret, '-', tmp);
217 if (!use_max && get_implied_min(arg, &tmp)) {
218 ret = tmp;
219 if (comparison == '>') {
220 tmp.value = 1;
221 ret = sval_binop(ret, '+', tmp);
225 *sval = ret;
226 return 1;
229 static sval_t add_one(sval_t sval)
231 sval.value++;
232 return sval;
235 static sval_t sub_one(sval_t sval)
237 sval.value--;
238 return 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;
247 sval_t min, max;
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) {
261 case '<':
262 case SPECIAL_UNSIGNED_LT:
263 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
264 break;
265 case SPECIAL_LTE:
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);
269 break;
270 case SPECIAL_EQUAL:
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)));
275 break;
276 case SPECIAL_GTE:
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)));
280 break;
281 case '>':
282 case SPECIAL_UNSIGNED_GT:
283 ret_rl = remove_range(left_orig, min, rl_min(right_orig));
284 break;
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));
288 break;
289 default:
290 sm_msg("internal error: unhandled comparison %s", show_special(comparison));
291 return;
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;
301 int comparison;
303 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
304 return start_rl;
306 if (!get_implied_rl(arg, &right_orig))
307 return start_rl;
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);
315 return start_rl;
318 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
320 char *start = c;
321 sval_t ret;
323 if (!strncmp(start, "max", 3)) {
324 ret = sval_type_max(type);
325 c += 3;
326 } else if (!strncmp(start, "u64max", 6)) {
327 ret = sval_type_val(type, ULLONG_MAX);
328 c += 6;
329 } else if (!strncmp(start, "s64max", 6)) {
330 ret = sval_type_val(type, LLONG_MAX);
331 c += 6;
332 } else if (!strncmp(start, "u32max", 6)) {
333 ret = sval_type_val(type, UINT_MAX);
334 c += 6;
335 } else if (!strncmp(start, "s32max", 6)) {
336 ret = sval_type_val(type, INT_MAX);
337 c += 6;
338 } else if (!strncmp(start, "u16max", 6)) {
339 ret = sval_type_val(type, USHRT_MAX);
340 c += 6;
341 } else if (!strncmp(start, "s16max", 6)) {
342 ret = sval_type_val(type, SHRT_MAX);
343 c += 6;
344 } else if (!strncmp(start, "min", 3)) {
345 ret = sval_type_min(type);
346 c += 3;
347 } else if (!strncmp(start, "s64min", 6)) {
348 ret = sval_type_val(type, LLONG_MIN);
349 c += 6;
350 } else if (!strncmp(start, "s32min", 6)) {
351 ret = sval_type_val(type, INT_MIN);
352 c += 6;
353 } else if (!strncmp(start, "s16min", 6)) {
354 ret = sval_type_val(type, SHRT_MIN);
355 c += 6;
356 } else if (!strncmp(start, "long_min", 8)) {
357 ret = sval_type_val(type, LONG_MIN);
358 c += 8;
359 } else if (!strncmp(start, "long_max", 8)) {
360 ret = sval_type_val(type, LONG_MAX);
361 c += 8;
362 } else if (!strncmp(start, "ulong_max", 9)) {
363 ret = sval_type_val(type, ULONG_MAX);
364 c += 8;
365 } else if (!strncmp(start, "ptr_max", 7)) {
366 ret = sval_type_val(type, valid_ptr_max);
367 c += 8;
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));
373 } else {
374 ret = sval_type_val(type, strtoll(start, &c, 10));
376 *endp = c;
377 return ret;
380 static char *jump_to_call_math(char *value)
382 char *c = value;
384 while (*c && *c != '[')
385 c++;
387 if (!*c)
388 return NULL;
389 c++;
390 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
391 return NULL;
393 return 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;
399 sval_t min, max;
400 char *c;
402 min = sval_type_min(type);
403 max = sval_type_max(type);
404 c = str;
405 while (*c != '\0' && *c != '[') {
406 if (*c == '(')
407 c++;
408 min = parse_val(0, call, type, c, &c);
409 if (!sval_fits(type, min))
410 min = sval_type_min(type);
411 max = min;
412 if (*c == ')')
413 c++;
414 if (*c == '\0' || *c == '[') {
415 add_range_t(type, &rl_tmp, min, min);
416 break;
418 if (*c == ',') {
419 add_range_t(type, &rl_tmp, min, min);
420 c++;
421 continue;
423 if (*c != '-') {
424 sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
425 break;
427 c++;
428 if (*c == '(')
429 c++;
430 max = parse_val(1, call, type, c, &c);
431 if (!sval_fits(type, max))
432 max = sval_type_max(type);
433 add_range_t(type, &rl_tmp, min, max);
434 if (*c == ')')
435 c++;
436 if (*c == ',')
437 c++;
440 *rl = rl_tmp;
441 *endp = c;
444 static void str_to_dinfo(struct expression *call, struct symbol *type, char *value, struct data_info *dinfo)
446 struct range_list *math_rl;
447 char *call_math;
448 char *c;
449 struct range_list *rl = NULL;
451 if (!type)
452 type = &llong_ctype;
454 if (strcmp(value, "empty") == 0)
455 return;
457 if (strncmp(value, "[==$", 4) == 0) {
458 struct expression *arg;
459 int comparison;
461 if (!str_to_comparison_arg(value, call, &comparison, &arg))
462 return;
463 if (!get_implied_rl(arg, &rl))
464 return;
465 goto cast;
468 str_to_rl_helper(call, type, value, &c, &rl);
469 if (*c == '\0')
470 goto cast;
472 call_math = jump_to_call_math(value);
473 if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
474 rl = rl_intersection(rl, math_rl);
475 goto cast;
479 * For now if we already tried to handle the call math and couldn't
480 * figure it out then bail.
482 if (jump_to_call_math(c) == c + 1)
483 goto cast;
485 rl = filter_by_comparison_call(c, call, &c, rl);
487 cast:
488 rl = cast_rl(type, rl);
489 dinfo->value_ranges = rl;
492 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
494 struct data_info dinfo = {};
496 str_to_dinfo(NULL, type, value, &dinfo);
497 *rl = dinfo.value_ranges;
500 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
502 struct data_info dinfo = {};
504 str_to_dinfo(strip_expr(expr), type, value, &dinfo);
505 *rl = dinfo.value_ranges;
508 int is_whole_rl(struct range_list *rl)
510 struct data_range *drange;
512 if (ptr_list_empty(rl))
513 return 0;
514 drange = first_ptr_list((struct ptr_list *)rl);
515 if (sval_is_min(drange->min) && sval_is_max(drange->max))
516 return 1;
517 return 0;
520 int is_whole_rl_non_zero(struct range_list *rl)
522 struct data_range *drange;
524 if (ptr_list_empty(rl))
525 return 0;
526 drange = first_ptr_list((struct ptr_list *)rl);
527 if (sval_unsigned(drange->min) &&
528 drange->min.value == 1 &&
529 sval_is_max(drange->max))
530 return 1;
531 if (!sval_is_min(drange->min) || drange->max.value != -1)
532 return 0;
533 drange = last_ptr_list((struct ptr_list *)rl);
534 if (drange->min.value != 1 || !sval_is_max(drange->max))
535 return 0;
536 return 1;
539 sval_t rl_min(struct range_list *rl)
541 struct data_range *drange;
542 sval_t ret;
544 ret.type = &llong_ctype;
545 ret.value = LLONG_MIN;
546 if (ptr_list_empty(rl))
547 return ret;
548 drange = first_ptr_list((struct ptr_list *)rl);
549 return drange->min;
552 sval_t rl_max(struct range_list *rl)
554 struct data_range *drange;
555 sval_t ret;
557 ret.type = &llong_ctype;
558 ret.value = LLONG_MAX;
559 if (ptr_list_empty(rl))
560 return ret;
561 drange = last_ptr_list((struct ptr_list *)rl);
562 return drange->max;
565 int rl_to_sval(struct range_list *rl, sval_t *sval)
567 sval_t min, max;
569 if (!rl)
570 return 0;
572 min = rl_min(rl);
573 max = rl_max(rl);
574 if (sval_cmp(min, max) != 0)
575 return 0;
576 *sval = min;
577 return 1;
580 struct symbol *rl_type(struct range_list *rl)
582 if (!rl)
583 return NULL;
584 return rl_min(rl).type;
587 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
589 struct data_range *ret;
591 if (perm)
592 ret = __alloc_perm_data_range(0);
593 else
594 ret = __alloc_data_range(0);
595 ret->min = min;
596 ret->max = max;
597 return ret;
600 struct data_range *alloc_range(sval_t min, sval_t max)
602 return alloc_range_helper_sval(min, max, 0);
605 struct data_range *alloc_range_perm(sval_t min, sval_t max)
607 return alloc_range_helper_sval(min, max, 1);
610 struct range_list *alloc_rl(sval_t min, sval_t max)
612 struct range_list *rl = NULL;
614 if (sval_cmp(min, max) > 0)
615 return alloc_whole_rl(min.type);
617 add_range(&rl, min, max);
618 return rl;
621 struct range_list *alloc_whole_rl(struct symbol *type)
623 if (!type || type_positive_bits(type) < 0)
624 type = &llong_ctype;
625 if (type->type == SYM_ARRAY)
626 type = &ptr_ctype;
628 return alloc_rl(sval_type_min(type), sval_type_max(type));
631 void add_range(struct range_list **list, sval_t min, sval_t max)
633 struct data_range *tmp;
634 struct data_range *new = NULL;
635 int check_next = 0;
638 * There is at least on valid reason why the types might be confusing
639 * and that's when you have a void pointer and on some paths you treat
640 * it as a u8 pointer and on other paths you treat it as a u16 pointer.
641 * This case is hard to deal with.
643 * There are other cases where we probably should be more specific about
644 * the types than we are. For example, we end up merging a lot of ulong
645 * with pointers and I have not figured out why we do that.
647 * But this hack works for both cases, I think. We cast it to pointers
648 * or we use the bigger size.
651 if (*list && rl_type(*list) != min.type) {
652 if (rl_type(*list)->type == SYM_PTR) {
653 min = sval_cast(rl_type(*list), min);
654 max = sval_cast(rl_type(*list), max);
655 } else if (min.type->type == SYM_PTR) {
656 *list = cast_rl(min.type, *list);
657 } else if (type_bits(rl_type(*list)) >= type_bits(min.type)) {
658 min = sval_cast(rl_type(*list), min);
659 max = sval_cast(rl_type(*list), max);
660 } else {
661 *list = cast_rl(min.type, *list);
665 if (sval_cmp(min, max) > 0) {
666 min = sval_type_min(min.type);
667 max = sval_type_max(min.type);
671 * FIXME: This has a problem merging a range_list like: min-0,3-max
672 * with a range like 1-2. You end up with min-2,3-max instead of
673 * just min-max.
675 FOR_EACH_PTR(*list, tmp) {
676 if (check_next) {
677 /* Sometimes we overlap with more than one range
678 so we have to delete or modify the next range. */
679 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
680 /* join 2 ranges here */
681 new->max = tmp->max;
682 DELETE_CURRENT_PTR(tmp);
683 return;
686 /* Doesn't overlap with the next one. */
687 if (sval_cmp(max, tmp->min) < 0)
688 return;
690 if (sval_cmp(max, tmp->max) <= 0) {
691 /* Partially overlaps the next one. */
692 new->max = tmp->max;
693 DELETE_CURRENT_PTR(tmp);
694 return;
695 } else {
696 /* Completely overlaps the next one. */
697 DELETE_CURRENT_PTR(tmp);
698 /* there could be more ranges to delete */
699 continue;
702 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
703 /* join 2 ranges into a big range */
704 new = alloc_range(min, tmp->max);
705 REPLACE_CURRENT_PTR(tmp, new);
706 return;
708 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
709 new = alloc_range(min, max);
710 INSERT_CURRENT(new, tmp);
711 return;
713 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
714 if (sval_cmp(max, tmp->max) < 0)
715 max = tmp->max;
716 else
717 check_next = 1;
718 new = alloc_range(min, max);
719 REPLACE_CURRENT_PTR(tmp, new);
720 if (!check_next)
721 return;
722 continue;
724 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
725 return;
726 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
727 min = tmp->min;
728 new = alloc_range(min, max);
729 REPLACE_CURRENT_PTR(tmp, new);
730 check_next = 1;
731 continue;
733 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
734 /* join 2 ranges into a big range */
735 new = alloc_range(tmp->min, max);
736 REPLACE_CURRENT_PTR(tmp, new);
737 check_next = 1;
738 continue;
740 /* the new range is entirely above the existing ranges */
741 } END_FOR_EACH_PTR(tmp);
742 if (check_next)
743 return;
744 new = alloc_range(min, max);
745 add_ptr_list(list, new);
748 struct range_list *clone_rl(struct range_list *list)
750 struct data_range *tmp;
751 struct range_list *ret = NULL;
753 FOR_EACH_PTR(list, tmp) {
754 add_ptr_list(&ret, tmp);
755 } END_FOR_EACH_PTR(tmp);
756 return ret;
759 struct range_list *clone_rl_permanent(struct range_list *list)
761 struct data_range *tmp;
762 struct data_range *new;
763 struct range_list *ret = NULL;
765 FOR_EACH_PTR(list, tmp) {
766 new = alloc_range_perm(tmp->min, tmp->max);
767 add_ptr_list(&ret, new);
768 } END_FOR_EACH_PTR(tmp);
769 return ret;
772 struct range_list *rl_union(struct range_list *one, struct range_list *two)
774 struct data_range *tmp;
775 struct range_list *ret = NULL;
777 FOR_EACH_PTR(one, tmp) {
778 add_range(&ret, tmp->min, tmp->max);
779 } END_FOR_EACH_PTR(tmp);
780 FOR_EACH_PTR(two, tmp) {
781 add_range(&ret, tmp->min, tmp->max);
782 } END_FOR_EACH_PTR(tmp);
783 return ret;
786 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
788 struct data_range *tmp;
789 struct range_list *ret = NULL;
791 if (!list)
792 return NULL;
794 min = sval_cast(rl_type(list), min);
795 max = sval_cast(rl_type(list), max);
796 if (sval_cmp(min, max) > 0) {
797 sval_t tmp = min;
798 min = max;
799 max = tmp;
802 FOR_EACH_PTR(list, tmp) {
803 if (sval_cmp(tmp->max, min) < 0) {
804 add_range(&ret, tmp->min, tmp->max);
805 continue;
807 if (sval_cmp(tmp->min, max) > 0) {
808 add_range(&ret, tmp->min, tmp->max);
809 continue;
811 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
812 continue;
813 if (sval_cmp(tmp->min, min) >= 0) {
814 max.value++;
815 add_range(&ret, max, tmp->max);
816 } else if (sval_cmp(tmp->max, max) <= 0) {
817 min.value--;
818 add_range(&ret, tmp->min, min);
819 } else {
820 min.value--;
821 max.value++;
822 add_range(&ret, tmp->min, min);
823 add_range(&ret, max, tmp->max);
825 } END_FOR_EACH_PTR(tmp);
826 return ret;
829 int ranges_equiv(struct data_range *one, struct data_range *two)
831 if (!one && !two)
832 return 1;
833 if (!one || !two)
834 return 0;
835 if (sval_cmp(one->min, two->min) != 0)
836 return 0;
837 if (sval_cmp(one->max, two->max) != 0)
838 return 0;
839 return 1;
842 int rl_equiv(struct range_list *one, struct range_list *two)
844 struct data_range *one_range;
845 struct data_range *two_range;
847 if (one == two)
848 return 1;
850 PREPARE_PTR_LIST(one, one_range);
851 PREPARE_PTR_LIST(two, two_range);
852 for (;;) {
853 if (!one_range && !two_range)
854 return 1;
855 if (!ranges_equiv(one_range, two_range))
856 return 0;
857 NEXT_PTR_LIST(one_range);
858 NEXT_PTR_LIST(two_range);
860 FINISH_PTR_LIST(two_range);
861 FINISH_PTR_LIST(one_range);
863 return 1;
866 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
868 switch (comparison) {
869 case '<':
870 case SPECIAL_UNSIGNED_LT:
871 if (sval_cmp(left->min, right->max) < 0)
872 return 1;
873 return 0;
874 case SPECIAL_UNSIGNED_LTE:
875 case SPECIAL_LTE:
876 if (sval_cmp(left->min, right->max) <= 0)
877 return 1;
878 return 0;
879 case SPECIAL_EQUAL:
880 if (sval_cmp(left->max, right->min) < 0)
881 return 0;
882 if (sval_cmp(left->min, right->max) > 0)
883 return 0;
884 return 1;
885 case SPECIAL_UNSIGNED_GTE:
886 case SPECIAL_GTE:
887 if (sval_cmp(left->max, right->min) >= 0)
888 return 1;
889 return 0;
890 case '>':
891 case SPECIAL_UNSIGNED_GT:
892 if (sval_cmp(left->max, right->min) > 0)
893 return 1;
894 return 0;
895 case SPECIAL_NOTEQUAL:
896 if (sval_cmp(left->min, left->max) != 0)
897 return 1;
898 if (sval_cmp(right->min, right->max) != 0)
899 return 1;
900 if (sval_cmp(left->min, right->min) != 0)
901 return 1;
902 return 0;
903 default:
904 sm_msg("unhandled comparison %d\n", comparison);
905 return 0;
907 return 0;
910 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
912 if (left)
913 return true_comparison_range(var, comparison, val);
914 else
915 return true_comparison_range(val, comparison, var);
918 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
920 switch (comparison) {
921 case '<':
922 case SPECIAL_UNSIGNED_LT:
923 if (sval_cmp(left->max, right->min) >= 0)
924 return 1;
925 return 0;
926 case SPECIAL_UNSIGNED_LTE:
927 case SPECIAL_LTE:
928 if (sval_cmp(left->max, right->min) > 0)
929 return 1;
930 return 0;
931 case SPECIAL_EQUAL:
932 if (sval_cmp(left->min, left->max) != 0)
933 return 1;
934 if (sval_cmp(right->min, right->max) != 0)
935 return 1;
936 if (sval_cmp(left->min, right->min) != 0)
937 return 1;
938 return 0;
939 case SPECIAL_UNSIGNED_GTE:
940 case SPECIAL_GTE:
941 if (sval_cmp(left->min, right->max) < 0)
942 return 1;
943 return 0;
944 case '>':
945 case SPECIAL_UNSIGNED_GT:
946 if (sval_cmp(left->min, right->max) <= 0)
947 return 1;
948 return 0;
949 case SPECIAL_NOTEQUAL:
950 if (sval_cmp(left->max, right->min) < 0)
951 return 0;
952 if (sval_cmp(left->min, right->max) > 0)
953 return 0;
954 return 1;
955 default:
956 sm_msg("unhandled comparison %d\n", comparison);
957 return 0;
959 return 0;
962 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
964 if (left)
965 return false_comparison_range_sval(var, comparison, val);
966 else
967 return false_comparison_range_sval(val, comparison, var);
970 int possibly_true(struct expression *left, int comparison, struct expression *right)
972 struct range_list *rl_left, *rl_right;
973 struct data_range *tmp_left, *tmp_right;
974 struct symbol *type;
976 if (!get_implied_rl(left, &rl_left))
977 return 1;
978 if (!get_implied_rl(right, &rl_right))
979 return 1;
981 type = rl_type(rl_left);
982 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
983 type = rl_type(rl_right);
984 if (type_positive_bits(type) < 31)
985 type = &int_ctype;
987 rl_left = cast_rl(type, rl_left);
988 rl_right = cast_rl(type, rl_right);
990 FOR_EACH_PTR(rl_left, tmp_left) {
991 FOR_EACH_PTR(rl_right, tmp_right) {
992 if (true_comparison_range(tmp_left, comparison, tmp_right))
993 return 1;
994 } END_FOR_EACH_PTR(tmp_right);
995 } END_FOR_EACH_PTR(tmp_left);
996 return 0;
999 int possibly_false(struct expression *left, int comparison, struct expression *right)
1001 struct range_list *rl_left, *rl_right;
1002 struct data_range *tmp_left, *tmp_right;
1003 struct symbol *type;
1005 if (!get_implied_rl(left, &rl_left))
1006 return 1;
1007 if (!get_implied_rl(right, &rl_right))
1008 return 1;
1010 type = rl_type(rl_left);
1011 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1012 type = rl_type(rl_right);
1013 if (type_positive_bits(type) < 31)
1014 type = &int_ctype;
1016 rl_left = cast_rl(type, rl_left);
1017 rl_right = cast_rl(type, rl_right);
1019 FOR_EACH_PTR(rl_left, tmp_left) {
1020 FOR_EACH_PTR(rl_right, tmp_right) {
1021 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
1022 return 1;
1023 } END_FOR_EACH_PTR(tmp_right);
1024 } END_FOR_EACH_PTR(tmp_left);
1025 return 0;
1028 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1030 struct data_range *left_tmp, *right_tmp;
1031 struct symbol *type;
1033 if (!left_ranges || !right_ranges)
1034 return 1;
1036 type = rl_type(left_ranges);
1037 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1038 type = rl_type(right_ranges);
1039 if (type_positive_bits(type) < 31)
1040 type = &int_ctype;
1042 left_ranges = cast_rl(type, left_ranges);
1043 right_ranges = cast_rl(type, right_ranges);
1045 FOR_EACH_PTR(left_ranges, left_tmp) {
1046 FOR_EACH_PTR(right_ranges, right_tmp) {
1047 if (true_comparison_range(left_tmp, comparison, right_tmp))
1048 return 1;
1049 } END_FOR_EACH_PTR(right_tmp);
1050 } END_FOR_EACH_PTR(left_tmp);
1051 return 0;
1054 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1056 struct data_range *left_tmp, *right_tmp;
1057 struct symbol *type;
1059 if (!left_ranges || !right_ranges)
1060 return 1;
1062 type = rl_type(left_ranges);
1063 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1064 type = rl_type(right_ranges);
1065 if (type_positive_bits(type) < 31)
1066 type = &int_ctype;
1068 left_ranges = cast_rl(type, left_ranges);
1069 right_ranges = cast_rl(type, right_ranges);
1071 FOR_EACH_PTR(left_ranges, left_tmp) {
1072 FOR_EACH_PTR(right_ranges, right_tmp) {
1073 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
1074 return 1;
1075 } END_FOR_EACH_PTR(right_tmp);
1076 } END_FOR_EACH_PTR(left_tmp);
1077 return 0;
1080 /* FIXME: the _rl here stands for right left so really it should be _lr */
1081 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1083 if (left)
1084 return possibly_true_rl(a, comparison, b);
1085 else
1086 return possibly_true_rl(b, comparison, a);
1089 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1091 if (left)
1092 return possibly_false_rl(a, comparison, b);
1093 else
1094 return possibly_false_rl(b, comparison, a);
1097 int rl_has_sval(struct range_list *rl, sval_t sval)
1099 struct data_range *tmp;
1101 FOR_EACH_PTR(rl, tmp) {
1102 if (sval_cmp(tmp->min, sval) <= 0 &&
1103 sval_cmp(tmp->max, sval) >= 0)
1104 return 1;
1105 } END_FOR_EACH_PTR(tmp);
1106 return 0;
1109 void tack_on(struct range_list **list, struct data_range *drange)
1111 add_ptr_list(list, drange);
1114 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
1116 add_ptr_list(rl_stack, rl);
1119 struct range_list *pop_rl(struct range_list_stack **rl_stack)
1121 struct range_list *rl;
1123 rl = last_ptr_list((struct ptr_list *)*rl_stack);
1124 delete_ptr_list_last((struct ptr_list **)rl_stack);
1125 return rl;
1128 struct range_list *top_rl(struct range_list_stack *rl_stack)
1130 struct range_list *rl;
1132 rl = last_ptr_list((struct ptr_list *)rl_stack);
1133 return rl;
1136 void filter_top_rl(struct range_list_stack **rl_stack, struct range_list *filter)
1138 struct range_list *rl;
1140 rl = pop_rl(rl_stack);
1141 rl = rl_filter(rl, filter);
1142 push_rl(rl_stack, rl);
1145 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1147 struct data_range *tmp;
1148 struct range_list *ret = NULL;
1149 sval_t min, max;
1151 if (!rl)
1152 return NULL;
1154 if (!type || type == rl_type(rl))
1155 return rl;
1157 FOR_EACH_PTR(rl, tmp) {
1158 min = tmp->min;
1159 max = tmp->max;
1160 if (type_bits(type) < type_bits(rl_type(rl))) {
1161 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1162 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1164 if (sval_cmp(min, max) > 0) {
1165 min = sval_cast(type, min);
1166 max = sval_cast(type, max);
1168 add_range_t(type, &ret, min, max);
1169 } END_FOR_EACH_PTR(tmp);
1171 return ret;
1174 static int rl_is_sane(struct range_list *rl)
1176 struct data_range *tmp;
1177 struct symbol *type;
1179 type = rl_type(rl);
1180 FOR_EACH_PTR(rl, tmp) {
1181 if (!sval_fits(type, tmp->min))
1182 return 0;
1183 if (!sval_fits(type, tmp->max))
1184 return 0;
1185 if (sval_cmp(tmp->min, tmp->max) > 0)
1186 return 0;
1187 } END_FOR_EACH_PTR(tmp);
1189 return 1;
1192 static int rl_type_consistent(struct range_list *rl)
1194 struct data_range *tmp;
1195 struct symbol *type;
1197 type = rl_type(rl);
1198 FOR_EACH_PTR(rl, tmp) {
1199 if (type != tmp->min.type || type != tmp->max.type)
1200 return 0;
1201 } END_FOR_EACH_PTR(tmp);
1202 return 1;
1205 static struct range_list *cast_to_bool(struct range_list *rl)
1207 struct data_range *tmp;
1208 struct range_list *ret = NULL;
1209 int has_one = 0;
1210 int has_zero = 0;
1211 sval_t min = { .type = &bool_ctype };
1212 sval_t max = { .type = &bool_ctype };
1214 FOR_EACH_PTR(rl, tmp) {
1215 if (tmp->min.value || tmp->max.value)
1216 has_one = 1;
1217 if (sval_is_negative(tmp->min) &&
1218 sval_is_negative(tmp->max))
1219 continue;
1220 if (tmp->min.value == 0 ||
1221 tmp->max.value == 0)
1222 has_zero = 1;
1223 if (sval_is_negative(tmp->min) &&
1224 tmp->max.value > 0)
1225 has_zero = 1;
1226 } END_FOR_EACH_PTR(tmp);
1228 if (!has_zero)
1229 min.value = 1;
1230 if (has_one)
1231 max.value = 1;
1233 add_range(&ret, min, max);
1234 return ret;
1237 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1239 struct data_range *tmp;
1240 struct range_list *ret = NULL;
1242 if (!rl)
1243 return NULL;
1245 if (!type)
1246 return rl;
1247 if (!rl_is_sane(rl))
1248 return alloc_whole_rl(type);
1249 if (type == rl_type(rl) && rl_type_consistent(rl))
1250 return rl;
1252 if (type == &bool_ctype)
1253 return cast_to_bool(rl);
1255 FOR_EACH_PTR(rl, tmp) {
1256 add_range_t(type, &ret, tmp->min, tmp->max);
1257 } END_FOR_EACH_PTR(tmp);
1259 if (!ret)
1260 return alloc_whole_rl(type);
1262 return ret;
1265 struct range_list *rl_invert(struct range_list *orig)
1267 struct range_list *ret = NULL;
1268 struct data_range *tmp;
1269 sval_t gap_min, abs_max, sval;
1271 if (!orig)
1272 return NULL;
1273 if (type_bits(rl_type(orig)) < 0) /* void type mostly */
1274 return NULL;
1276 gap_min = sval_type_min(rl_min(orig).type);
1277 abs_max = sval_type_max(rl_max(orig).type);
1279 FOR_EACH_PTR(orig, tmp) {
1280 if (sval_cmp(tmp->min, gap_min) > 0) {
1281 sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
1282 add_range(&ret, gap_min, sval);
1284 if (sval_cmp(tmp->max, abs_max) == 0)
1285 return ret;
1286 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
1287 } END_FOR_EACH_PTR(tmp);
1289 if (sval_cmp(gap_min, abs_max) <= 0)
1290 add_range(&ret, gap_min, abs_max);
1292 return ret;
1295 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1297 struct data_range *tmp;
1299 FOR_EACH_PTR(filter, tmp) {
1300 rl = remove_range(rl, tmp->min, tmp->max);
1301 } END_FOR_EACH_PTR(tmp);
1303 return rl;
1306 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1308 struct range_list *one_orig;
1309 struct range_list *two_orig;
1310 struct range_list *ret;
1311 struct symbol *ret_type;
1312 struct symbol *small_type;
1313 struct symbol *large_type;
1315 if (!two)
1316 return NULL;
1317 if (!one)
1318 return NULL;
1320 one_orig = one;
1321 two_orig = two;
1323 ret_type = rl_type(one);
1324 small_type = rl_type(one);
1325 large_type = rl_type(two);
1327 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1328 small_type = rl_type(two);
1329 large_type = rl_type(one);
1332 one = cast_rl(large_type, one);
1333 two = cast_rl(large_type, two);
1335 ret = one;
1336 one = rl_invert(one);
1337 two = rl_invert(two);
1339 ret = rl_filter(ret, one);
1340 ret = rl_filter(ret, two);
1342 one = cast_rl(small_type, one_orig);
1343 two = cast_rl(small_type, two_orig);
1345 one = rl_invert(one);
1346 two = rl_invert(two);
1348 ret = cast_rl(small_type, ret);
1349 ret = rl_filter(ret, one);
1350 ret = rl_filter(ret, two);
1352 return cast_rl(ret_type, ret);
1355 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1357 sval_t zero;
1358 sval_t max;
1360 max = rl_max(right);
1361 if (sval_is_max(max))
1362 return left;
1363 if (max.value == 0)
1364 return NULL;
1365 max.value--;
1366 if (sval_is_negative(max))
1367 return NULL;
1368 if (sval_cmp(rl_max(left), max) < 0)
1369 return left;
1370 zero = max;
1371 zero.value = 0;
1372 return alloc_rl(zero, max);
1375 static struct range_list *get_neg_rl(struct range_list *rl)
1377 struct data_range *tmp;
1378 struct data_range *new;
1379 struct range_list *ret = NULL;
1381 if (!rl)
1382 return NULL;
1383 if (sval_is_positive(rl_min(rl)))
1384 return NULL;
1386 FOR_EACH_PTR(rl, tmp) {
1387 if (sval_is_positive(tmp->min))
1388 return ret;
1389 if (sval_is_positive(tmp->max)) {
1390 new = alloc_range(tmp->min, tmp->max);
1391 new->max.value = -1;
1392 add_range(&ret, new->min, new->max);
1393 return ret;
1395 add_range(&ret, tmp->min, tmp->max);
1396 } END_FOR_EACH_PTR(tmp);
1398 return ret;
1401 static struct range_list *get_pos_rl(struct range_list *rl)
1403 struct data_range *tmp;
1404 struct data_range *new;
1405 struct range_list *ret = NULL;
1407 if (!rl)
1408 return NULL;
1409 if (sval_is_negative(rl_max(rl)))
1410 return NULL;
1412 FOR_EACH_PTR(rl, tmp) {
1413 if (sval_is_negative(tmp->max))
1414 continue;
1415 if (sval_is_positive(tmp->min)) {
1416 add_range(&ret, tmp->min, tmp->max);
1417 continue;
1419 new = alloc_range(tmp->min, tmp->max);
1420 new->min.value = 0;
1421 add_range(&ret, new->min, new->max);
1422 } END_FOR_EACH_PTR(tmp);
1424 return ret;
1427 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1429 sval_t right_min, right_max;
1430 sval_t min, max;
1432 if (!left || !right)
1433 return NULL;
1435 /* let's assume we never divide by zero */
1436 right_min = rl_min(right);
1437 right_max = rl_max(right);
1438 if (right_min.value == 0 && right_max.value == 0)
1439 return NULL;
1440 if (right_min.value == 0)
1441 right_min.value = 1;
1442 if (right_max.value == 0)
1443 right_max.value = -1;
1445 max = sval_binop(rl_max(left), '/', right_min);
1446 min = sval_binop(rl_min(left), '/', right_max);
1448 return alloc_rl(min, max);
1451 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1453 struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1454 struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1455 struct range_list *ret;
1457 if (is_whole_rl(right))
1458 return NULL;
1460 left_neg = get_neg_rl(left);
1461 left_pos = get_pos_rl(left);
1462 right_neg = get_neg_rl(right);
1463 right_pos = get_pos_rl(right);
1465 neg_neg = divide_rl_helper(left_neg, right_neg);
1466 neg_pos = divide_rl_helper(left_neg, right_pos);
1467 pos_neg = divide_rl_helper(left_pos, right_neg);
1468 pos_pos = divide_rl_helper(left_pos, right_pos);
1470 ret = rl_union(neg_neg, neg_pos);
1471 ret = rl_union(ret, pos_neg);
1472 return rl_union(ret, pos_pos);
1475 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1477 sval_t min, max;
1479 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1480 return NULL;
1481 min = sval_binop(rl_min(left), op, rl_min(right));
1483 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1484 return NULL;
1485 max = sval_binop(rl_max(left), op, rl_max(right));
1487 return alloc_rl(min, max);
1490 static unsigned long long rl_bits_always_set(struct range_list *rl)
1492 return sval_fls_mask(rl_min(rl));
1495 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1497 return sval_fls_mask(rl_max(rl));
1500 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1502 unsigned long long left_min, left_max, right_min, right_max;
1503 sval_t min, max;
1504 sval_t sval;
1506 if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1507 !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1508 return rl_binop(left, '+', right);
1510 left_min = rl_bits_always_set(left);
1511 left_max = rl_bits_maybe_set(left);
1512 right_min = rl_bits_always_set(right);
1513 right_max = rl_bits_maybe_set(right);
1515 min.type = max.type = &ullong_ctype;
1516 min.uvalue = left_min | right_min;
1517 max.uvalue = left_max | right_max;
1519 return cast_rl(rl_type(left), alloc_rl(min, max));
1522 static struct range_list *handle_XOR_rl(struct range_list *left, struct range_list *right)
1524 unsigned long long left_set, left_maybe;
1525 unsigned long long right_set, right_maybe;
1526 sval_t zero, max;
1528 left_set = rl_bits_always_set(left);
1529 left_maybe = rl_bits_maybe_set(left);
1531 right_set = rl_bits_always_set(right);
1532 right_maybe = rl_bits_maybe_set(right);
1534 zero = max = rl_min(left);
1535 zero.uvalue = 0;
1536 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1538 return cast_rl(rl_type(left), alloc_rl(zero, max));
1541 static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
1543 unsigned long long left_set, left_maybe;
1544 unsigned long long right_set, right_maybe;
1545 sval_t zero, max;
1547 return NULL;
1549 left_set = rl_bits_always_set(left);
1550 left_maybe = rl_bits_maybe_set(left);
1552 right_set = rl_bits_always_set(right);
1553 right_maybe = rl_bits_maybe_set(right);
1555 zero = max = rl_min(left);
1556 zero.uvalue = 0;
1557 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1559 return cast_rl(rl_type(left), alloc_rl(zero, max));
1562 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1564 struct symbol *cast_type;
1565 sval_t left_sval, right_sval;
1566 struct range_list *ret = NULL;
1568 cast_type = rl_type(left);
1569 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1570 cast_type = rl_type(right);
1571 if (sval_type_max(cast_type).uvalue < INT_MAX)
1572 cast_type = &int_ctype;
1574 left = cast_rl(cast_type, left);
1575 right = cast_rl(cast_type, right);
1577 if (!left || !right)
1578 return alloc_whole_rl(cast_type);
1580 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
1581 sval_t val = sval_binop(left_sval, op, right_sval);
1582 return alloc_rl(val, val);
1585 switch (op) {
1586 case '%':
1587 ret = handle_mod_rl(left, right);
1588 break;
1589 case '/':
1590 ret = handle_divide_rl(left, right);
1591 break;
1592 case '*':
1593 case '+':
1594 ret = handle_add_mult_rl(left, op, right);
1595 break;
1596 case '|':
1597 ret = handle_OR_rl(left, right);
1598 break;
1599 case '^':
1600 ret = handle_XOR_rl(left, right);
1601 break;
1602 case '&':
1603 ret = handle_AND_rl(left, right);
1604 break;
1606 /* FIXME: Do the rest as well */
1607 case '-':
1608 case SPECIAL_RIGHTSHIFT:
1609 case SPECIAL_LEFTSHIFT:
1610 break;
1613 if (!ret)
1614 ret = alloc_whole_rl(cast_type);
1615 return ret;
1618 void free_rl(struct range_list **rlist)
1620 __free_ptr_list((struct ptr_list **)rlist);
1623 static void free_single_dinfo(struct data_info *dinfo)
1625 free_rl(&dinfo->value_ranges);
1628 static void free_dinfos(struct allocation_blob *blob)
1630 unsigned int size = sizeof(struct data_info);
1631 unsigned int offset = 0;
1633 while (offset < blob->offset) {
1634 free_single_dinfo((struct data_info *)(blob->data + offset));
1635 offset += size;
1639 void free_data_info_allocs(void)
1641 struct allocator_struct *desc = &data_info_allocator;
1642 struct allocation_blob *blob = desc->blobs;
1644 desc->blobs = NULL;
1645 desc->allocations = 0;
1646 desc->total_bytes = 0;
1647 desc->useful_bytes = 0;
1648 desc->freelist = NULL;
1649 while (blob) {
1650 struct allocation_blob *next = blob->next;
1651 free_dinfos(blob);
1652 blob_free(blob, desc->chunking);
1653 blob = next;
1655 clear_data_range_alloc();
1658 void split_comparison_rl(struct range_list *left_orig, int op, struct range_list *right_orig,
1659 struct range_list **left_true_rl, struct range_list **left_false_rl,
1660 struct range_list **right_true_rl, struct range_list **right_false_rl)
1662 struct range_list *left_true, *left_false;
1663 struct range_list *right_true, *right_false;
1664 sval_t min, max;
1666 min = sval_type_min(rl_type(left_orig));
1667 max = sval_type_max(rl_type(left_orig));
1669 left_true = clone_rl(left_orig);
1670 left_false = clone_rl(left_orig);
1671 right_true = clone_rl(right_orig);
1672 right_false = clone_rl(right_orig);
1674 switch (op) {
1675 case '<':
1676 case SPECIAL_UNSIGNED_LT:
1677 left_true = remove_range(left_orig, rl_max(right_orig), max);
1678 if (!sval_is_min(rl_min(right_orig))) {
1679 left_false = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
1682 right_true = remove_range(right_orig, min, rl_min(left_orig));
1683 if (!sval_is_max(rl_max(left_orig)))
1684 right_false = remove_range(right_orig, add_one(rl_max(left_orig)), max);
1685 break;
1686 case SPECIAL_UNSIGNED_LTE:
1687 case SPECIAL_LTE:
1688 if (!sval_is_max(rl_max(right_orig)))
1689 left_true = remove_range(left_orig, add_one(rl_max(right_orig)), max);
1690 left_false = remove_range(left_orig, min, rl_min(right_orig));
1692 if (!sval_is_min(rl_min(left_orig)))
1693 right_true = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
1694 right_false = remove_range(right_orig, rl_max(left_orig), max);
1696 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
1697 left_false = remove_range(left_false, rl_min(left_orig), rl_min(left_orig));
1698 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
1699 right_false = remove_range(right_false, rl_max(left_orig), rl_max(left_orig));
1700 break;
1701 case SPECIAL_EQUAL:
1702 if (!sval_is_max(rl_max(right_orig))) {
1703 left_true = remove_range(left_true, add_one(rl_max(right_orig)), max);
1705 if (!sval_is_min(rl_min(right_orig))) {
1706 left_true = remove_range(left_true, min, sub_one(rl_min(right_orig)));
1708 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
1709 left_false = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
1711 if (!sval_is_max(rl_max(left_orig)))
1712 right_true = remove_range(right_true, add_one(rl_max(left_orig)), max);
1713 if (!sval_is_min(rl_min(left_orig)))
1714 right_true = remove_range(right_true, min, sub_one(rl_min(left_orig)));
1715 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
1716 right_false = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
1717 break;
1718 case SPECIAL_UNSIGNED_GTE:
1719 case SPECIAL_GTE:
1720 if (!sval_is_min(rl_min(right_orig)))
1721 left_true = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
1722 left_false = remove_range(left_orig, rl_max(right_orig), max);
1724 if (!sval_is_max(rl_max(left_orig)))
1725 right_true = remove_range(right_orig, add_one(rl_max(left_orig)), max);
1726 right_false = remove_range(right_orig, min, rl_min(left_orig));
1728 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
1729 right_false = remove_range(right_false, rl_min(left_orig), rl_min(left_orig));
1730 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
1731 left_false = remove_range(left_false, rl_max(left_orig), rl_max(left_orig));
1732 break;
1733 case '>':
1734 case SPECIAL_UNSIGNED_GT:
1735 left_true = remove_range(left_orig, min, rl_min(right_orig));
1736 if (!sval_is_max(rl_max(right_orig)))
1737 left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
1739 right_true = remove_range(right_orig, rl_max(left_orig), max);
1740 if (!sval_is_min(rl_min(left_orig)))
1741 right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
1742 break;
1743 case SPECIAL_NOTEQUAL:
1744 if (!sval_is_max(rl_max(right_orig)))
1745 left_false = remove_range(left_false, add_one(rl_max(right_orig)), max);
1746 if (!sval_is_min(rl_min(right_orig)))
1747 left_false = remove_range(left_false, min, sub_one(rl_min(right_orig)));
1748 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
1749 left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
1751 if (!sval_is_max(rl_max(left_orig)))
1752 right_false = remove_range(right_false, add_one(rl_max(left_orig)), max);
1753 if (!sval_is_min(rl_min(left_orig)))
1754 right_false = remove_range(right_false, min, sub_one(rl_min(left_orig)));
1755 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
1756 right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
1757 break;
1758 default:
1759 sm_msg("internal error: unhandled comparison %d", op);
1760 return;
1763 if (left_true_rl) {
1764 *left_true_rl = left_true;
1765 *left_false_rl = left_false;
1767 if (right_true_rl) {
1768 *right_true_rl = right_true;
1769 *right_false_rl = right_false;