?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
avl: make get_stree_id() return -1 if the stree pointer is NULL
[smatch.git] / smatch_ranges.c
blob4e30a8048653bd520c9ac038d779a556c3da939b
1 /*
2 * Copyright (C) 2009 Dan Carpenter.
3 *
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.
8 *
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.
13 *
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
16 */
17
18 #include "parse.h"
19 #include "smatch.h"
20 #include "smatch_extra.h"
21 #include "smatch_slist.h"
22
23 ALLOCATOR(data_info, "smatch extra data");
24 ALLOCATOR(data_range, "data range");
25 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
26 "permanent ranges", perm_data_range);
27
28 char *show_rl(struct range_list *list)
29 {
30 struct data_range *tmp;
31 char full[256];
32 int i = 0;
33
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;
42 }
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);
48 }
49
50 static int sval_too_big(struct symbol *type, sval_t sval)
51 {
52 if (type_bits(type) == 64)
53 return 0;
54 if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
55 return 1;
56 return 0;
57 }
58
59 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
60 {
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));
64 return;
65 }
66
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));
70 return;
71 }
72
73 /*
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.
78 */
79 if (sval_too_big(type, min) || sval_too_big(type, max)) {
80 add_range(rl, sval_type_min(type), sval_type_max(type));
81 return;
82 }
83
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));
89 return;
90 }
91 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
92 max = sval_type_max(type);
93 } else {
94 max = sval_cast(type, max);
95 }
96 min = sval_cast(type, min);
97 add_range(rl, min, max);
98 }
99
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);
105 } else {
106 min = sval_cast(type, min);
107 }
108 max = sval_cast(type, max);
109 add_range(rl, min, max);
110 }
111
112 add_range(rl, sval_cast(type, min), sval_cast(type, max));
113 return;
114 }
115
116 static int str_to_comparison_arg_helper(const char *str,
117 struct expression *call, int *comparison,
118 struct expression **arg, char **endp)
119 {
120 int param;
121 char *c = (char *)str;
122
123 if (*c != '[')
124 return 0;
125 c++;
126
127 if (*c == '<') {
128 c++;
129 if (*c == '=') {
130 *comparison = SPECIAL_LTE;
131 c++;
132 } else {
133 *comparison = '<';
134 }
135 } else if (*c == '=') {
136 c++;
137 c++;
138 *comparison = SPECIAL_EQUAL;
139 } else if (*c == '>') {
140 c++;
141 if (*c == '=') {
142 *comparison = SPECIAL_GTE;
143 c++;
144 } else {
145 *comparison = '>';
146 }
147 } else if (*c == '!') {
148 c++;
149 c++;
150 *comparison = SPECIAL_NOTEQUAL;
151 } else {
152 return 0;
153 }
154
155 if (*c != '$')
156 return 0;
157 c++;
158
159 param = strtoll(c, &c, 10);
160 c++; /* skip the ']' character */
161 if (endp)
162 *endp = (char *)c;
163
164 if (!call)
165 return 0;
166 *arg = get_argument_from_call_expr(call->args, param);
167 if (!*arg)
168 return 0;
169 return 1;
170 }
171
172 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
173 {
174 while (1) {
175 if (!*str)
176 return 0;
177 if (*str == '[')
178 break;
179 str++;
180 }
181 return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
182 }
183
184 static int get_val_from_key(int use_max, struct symbol *type, char *c, struct expression *call, char **endp, sval_t *sval)
185 {
186 struct expression *arg;
187 int comparison;
188 sval_t ret, tmp;
189
190 if (use_max)
191 ret = sval_type_max(type);
192 else
193 ret = sval_type_min(type);
194
195 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
196 *sval = ret;
197 return 0;
198 }
199
200 if (use_max && get_implied_max(arg, &tmp)) {
201 ret = tmp;
202 if (comparison == '<') {
203 tmp.value = 1;
204 ret = sval_binop(ret, '-', tmp);
205 }
206 }
207 if (!use_max && get_implied_min(arg, &tmp)) {
208 ret = tmp;
209 if (comparison == '>') {
210 tmp.value = 1;
211 ret = sval_binop(ret, '+', tmp);
212 }
213 }
214
215 *sval = ret;
216 return 1;
217 }
218
219 static sval_t add_one(sval_t sval)
220 {
221 sval.value++;
222 return sval;
223 }
224
225 static sval_t sub_one(sval_t sval)
226 {
227 sval.value--;
228 return sval;
229 }
230
231 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
232 {
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;
237 sval_t min, max;
238
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;
244
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);
249
250 switch (comparison) {
251 case '<':
252 case SPECIAL_UNSIGNED_LT:
253 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
254 break;
255 case SPECIAL_LTE:
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);
259 break;
260 case SPECIAL_EQUAL:
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)));
265 break;
266 case SPECIAL_GTE:
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)));
270 break;
271 case '>':
272 case SPECIAL_UNSIGNED_GT:
273 ret_rl = remove_range(left_orig, min, rl_min(right_orig));
274 break;
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));
278 break;
279 default:
280 sm_msg("internal error: unhandled comparison %s", show_special(comparison));
281 return;
282 }
283
284 *rl = cast_rl(rl_type(*rl), ret_rl);
285 }
286
287 static struct range_list *filter_by_comparison_call(char *c, struct expression *call, char **endp, struct range_list *start_rl)
288 {
289 struct expression *arg;
290 struct range_list *right_orig;
291 int comparison;
292
293 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
294 return NULL;
295
296 if (!get_implied_rl(arg, &right_orig))
297 return NULL;
298
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);
303
304 filter_by_comparison(&start_rl, comparison, right_orig);
305 return start_rl;
306 }
307
308 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
309 {
310 char *start = c;
311 sval_t ret;
312
313 if (!strncmp(start, "max", 3)) {
314 ret = sval_type_max(type);
315 c += 3;
316 } else if (!strncmp(start, "u64max", 6)) {
317 ret = sval_type_val(type, ULLONG_MAX);
318 c += 6;
319 } else if (!strncmp(start, "s64max", 6)) {
320 ret = sval_type_val(type, LLONG_MAX);
321 c += 6;
322 } else if (!strncmp(start, "u32max", 6)) {
323 ret = sval_type_val(type, UINT_MAX);
324 c += 6;
325 } else if (!strncmp(start, "s32max", 6)) {
326 ret = sval_type_val(type, INT_MAX);
327 c += 6;
328 } else if (!strncmp(start, "u16max", 6)) {
329 ret = sval_type_val(type, USHRT_MAX);
330 c += 6;
331 } else if (!strncmp(start, "s16max", 6)) {
332 ret = sval_type_val(type, SHRT_MAX);
333 c += 6;
334 } else if (!strncmp(start, "min", 3)) {
335 ret = sval_type_min(type);
336 c += 3;
337 } else if (!strncmp(start, "s64min", 6)) {
338 ret = sval_type_val(type, LLONG_MIN);
339 c += 6;
340 } else if (!strncmp(start, "s32min", 6)) {
341 ret = sval_type_val(type, INT_MIN);
342 c += 6;
343 } else if (!strncmp(start, "s16min", 6)) {
344 ret = sval_type_val(type, SHRT_MIN);
345 c += 6;
346 } else if (!strncmp(start, "long_min", 8)) {
347 ret = sval_type_val(type, LONG_MIN);
348 c += 8;
349 } else if (!strncmp(start, "long_max", 8)) {
350 ret = sval_type_val(type, LONG_MAX);
351 c += 8;
352 } else if (!strncmp(start, "ulong_max", 9)) {
353 ret = sval_type_val(type, ULONG_MAX);
354 c += 8;
355 } else if (!strncmp(start, "ptr_max", 7)) {
356 ret = sval_type_val(type, valid_ptr_max);
357 c += 8;
358 } else if (start[0] == '[') {
359 /* this parses [==p0] comparisons */
360 get_val_from_key(1, type, start, call, &c, &ret);
361 } else {
362 ret = sval_type_val(type, strtoll(start, &c, 10));
363 }
364 *endp = c;
365 return ret;
366 }
367
368 static char *jump_to_call_math(char *value)
369 {
370 char *c = value;
371
372 while (*c && *c != '[')
373 c++;
374
375 if (!*c)
376 return NULL;
377 c++;
378 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
379 return NULL;
380
381 return c;
382 }
383
384 static void str_to_rl_helper(struct expression *call, struct symbol *type, char *str, char **endp, struct range_list **rl)
385 {
386 struct range_list *rl_tmp = NULL;
387 sval_t min, max;
388 char *c;
389
390 min = sval_type_min(type);
391 max = sval_type_max(type);
392 c = str;
393 while (*c != '\0' && *c != '[') {
394 if (*c == '(')
395 c++;
396 min = parse_val(0, call, type, c, &c);
397 max = min;
398 if (*c == ')')
399 c++;
400 if (*c == '\0' || *c == '[') {
401 add_range_t(type, &rl_tmp, min, min);
402 break;
403 }
404 if (*c == ',') {
405 add_range_t(type, &rl_tmp, min, min);
406 c++;
407 continue;
408 }
409 if (*c != '-') {
410 sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
411 break;
412 }
413 c++;
414 if (*c == '(')
415 c++;
416 max = parse_val(1, call, type, c, &c);
417 add_range_t(type, &rl_tmp, min, max);
418 if (*c == ')')
419 c++;
420 if (*c == ',')
421 c++;
422 }
423
424 *rl = rl_tmp;
425 *endp = c;
426 }
427
428 static void str_to_dinfo(struct expression *call, struct symbol *type, char *value, struct data_info *dinfo)
429 {
430 struct range_list *math_rl;
431 char *call_math;
432 char *c;
433 struct range_list *rl = NULL;
434
435 if (!type)
436 type = &llong_ctype;
437
438 if (strcmp(value, "empty") == 0)
439 return;
440
441 if (strncmp(value, "[==$", 4) == 0) {
442 struct expression *arg;
443 int comparison;
444
445 if (!str_to_comparison_arg(value, call, &comparison, &arg))
446 return;
447 if (!get_implied_rl(arg, &rl))
448 return;
449 goto cast;
450 }
451
452 str_to_rl_helper(call, type, value, &c, &rl);
453 if (*c == '\0')
454 goto cast;
455
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);
459 goto cast;
460 }
461
462 /*
463 * For now if we already tried to handle the call math and couldn't
464 * figure it out then bail.
465 */
466 if (jump_to_call_math(c) == c + 1)
467 goto cast;
468
469 rl = filter_by_comparison_call(c, call, &c, rl);
470
471 cast:
472 rl = cast_rl(type, rl);
473 dinfo->value_ranges = rl;
474 }
475
476 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
477 {
478 struct data_info dinfo = {};
479
480 str_to_dinfo(NULL, type, value, &dinfo);
481 *rl = dinfo.value_ranges;
482 }
483
484 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
485 {
486 struct data_info dinfo = {};
487
488 str_to_dinfo(strip_expr(expr), type, value, &dinfo);
489 *rl = dinfo.value_ranges;
490 }
491
492 int is_whole_rl(struct range_list *rl)
493 {
494 struct data_range *drange;
495
496 if (ptr_list_empty(rl))
497 return 0;
498 drange = first_ptr_list((struct ptr_list *)rl);
499 if (sval_is_min(drange->min) && sval_is_max(drange->max))
500 return 1;
501 return 0;
502 }
503
504 int is_whole_rl_non_zero(struct range_list *rl)
505 {
506 struct data_range *drange;
507
508 if (ptr_list_empty(rl))
509 return 0;
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))
514 return 1;
515 if (!sval_is_min(drange->min) || drange->max.value != -1)
516 return 0;
517 drange = last_ptr_list((struct ptr_list *)rl);
518 if (drange->min.value != 1 || !sval_is_max(drange->max))
519 return 0;
520 return 1;
521 }
522
523 sval_t rl_min(struct range_list *rl)
524 {
525 struct data_range *drange;
526 sval_t ret;
527
528 ret.type = &llong_ctype;
529 ret.value = LLONG_MIN;
530 if (ptr_list_empty(rl))
531 return ret;
532 drange = first_ptr_list((struct ptr_list *)rl);
533 return drange->min;
534 }
535
536 sval_t rl_max(struct range_list *rl)
537 {
538 struct data_range *drange;
539 sval_t ret;
540
541 ret.type = &llong_ctype;
542 ret.value = LLONG_MAX;
543 if (ptr_list_empty(rl))
544 return ret;
545 drange = last_ptr_list((struct ptr_list *)rl);
546 return drange->max;
547 }
548
549 int rl_to_sval(struct range_list *rl, sval_t *sval)
550 {
551 sval_t min, max;
552
553 if (!rl)
554 return 0;
555
556 min = rl_min(rl);
557 max = rl_max(rl);
558 if (sval_cmp(min, max) != 0)
559 return 0;
560 *sval = min;
561 return 1;
562 }
563
564 struct symbol *rl_type(struct range_list *rl)
565 {
566 if (!rl)
567 return NULL;
568 return rl_min(rl).type;
569 }
570
571 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
572 {
573 struct data_range *ret;
574
575 if (perm)
576 ret = __alloc_perm_data_range(0);
577 else
578 ret = __alloc_data_range(0);
579 ret->min = min;
580 ret->max = max;
581 return ret;
582 }
583
584 struct data_range *alloc_range(sval_t min, sval_t max)
585 {
586 return alloc_range_helper_sval(min, max, 0);
587 }
588
589 struct data_range *alloc_range_perm(sval_t min, sval_t max)
590 {
591 return alloc_range_helper_sval(min, max, 1);
592 }
593
594 struct range_list *alloc_rl(sval_t min, sval_t max)
595 {
596 struct range_list *rl = NULL;
597
598 if (sval_cmp(min, max) > 0)
599 return alloc_whole_rl(min.type);
600
601 add_range(&rl, min, max);
602 return rl;
603 }
604
605 struct range_list *alloc_whole_rl(struct symbol *type)
606 {
607 if (!type || type_positive_bits(type) < 0)
608 type = &llong_ctype;
609 if (type->type == SYM_ARRAY)
610 type = &ptr_ctype;
611
612 return alloc_rl(sval_type_min(type), sval_type_max(type));
613 }
614
615 void add_range(struct range_list **list, sval_t min, sval_t max)
616 {
617 struct data_range *tmp;
618 struct data_range *new = NULL;
619 int check_next = 0;
620
621 if (sval_cmp(min, max) > 0) {
622 min = sval_type_min(min.type);
623 max = sval_type_max(min.type);
624 }
625
626 /*
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
629 * just min-max.
630 */
631 FOR_EACH_PTR(*list, tmp) {
632 if (check_next) {
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 */
637 new->max = tmp->max;
638 DELETE_CURRENT_PTR(tmp);
639 return;
640 }
641
642 /* Doesn't overlap with the next one. */
643 if (sval_cmp(max, tmp->min) < 0)
644 return;
645
646 if (sval_cmp(max, tmp->max) <= 0) {
647 /* Partially overlaps the next one. */
648 new->max = tmp->max;
649 DELETE_CURRENT_PTR(tmp);
650 return;
651 } else {
652 /* Completely overlaps the next one. */
653 DELETE_CURRENT_PTR(tmp);
654 /* there could be more ranges to delete */
655 continue;
656 }
657 }
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);
662 return;
663 }
664 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
665 new = alloc_range(min, max);
666 INSERT_CURRENT(new, tmp);
667 return;
668 }
669 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
670 if (sval_cmp(max, tmp->max) < 0)
671 max = tmp->max;
672 else
673 check_next = 1;
674 new = alloc_range(min, max);
675 REPLACE_CURRENT_PTR(tmp, new);
676 if (!check_next)
677 return;
678 continue;
679 }
680 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
681 return;
682 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
683 min = tmp->min;
684 new = alloc_range(min, max);
685 REPLACE_CURRENT_PTR(tmp, new);
686 check_next = 1;
687 continue;
688 }
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);
693 check_next = 1;
694 continue;
695 }
696 /* the new range is entirely above the existing ranges */
697 } END_FOR_EACH_PTR(tmp);
698 if (check_next)
699 return;
700 new = alloc_range(min, max);
701 add_ptr_list(list, new);
702 }
703
704 struct range_list *clone_rl(struct range_list *list)
705 {
706 struct data_range *tmp;
707 struct range_list *ret = NULL;
708
709 FOR_EACH_PTR(list, tmp) {
710 add_ptr_list(&ret, tmp);
711 } END_FOR_EACH_PTR(tmp);
712 return ret;
713 }
714
715 struct range_list *clone_rl_permanent(struct range_list *list)
716 {
717 struct data_range *tmp;
718 struct data_range *new;
719 struct range_list *ret = NULL;
720
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);
725 return ret;
726 }
727
728 struct range_list *rl_union(struct range_list *one, struct range_list *two)
729 {
730 struct data_range *tmp;
731 struct range_list *ret = NULL;
732
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);
739 return ret;
740 }
741
742 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
743 {
744 struct data_range *tmp;
745 struct range_list *ret = NULL;
746
747 if (!list)
748 return NULL;
749
750 min = sval_cast(rl_type(list), min);
751 max = sval_cast(rl_type(list), max);
752 if (sval_cmp(min, max) > 0) {
753 sval_t tmp = min;
754 min = max;
755 max = tmp;
756 }
757
758 FOR_EACH_PTR(list, tmp) {
759 if (sval_cmp(tmp->max, min) < 0) {
760 add_range(&ret, tmp->min, tmp->max);
761 continue;
762 }
763 if (sval_cmp(tmp->min, max) > 0) {
764 add_range(&ret, tmp->min, tmp->max);
765 continue;
766 }
767 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
768 continue;
769 if (sval_cmp(tmp->min, min) >= 0) {
770 max.value++;
771 add_range(&ret, max, tmp->max);
772 } else if (sval_cmp(tmp->max, max) <= 0) {
773 min.value--;
774 add_range(&ret, tmp->min, min);
775 } else {
776 min.value--;
777 max.value++;
778 add_range(&ret, tmp->min, min);
779 add_range(&ret, max, tmp->max);
780 }
781 } END_FOR_EACH_PTR(tmp);
782 return ret;
783 }
784
785 int ranges_equiv(struct data_range *one, struct data_range *two)
786 {
787 if (!one && !two)
788 return 1;
789 if (!one || !two)
790 return 0;
791 if (sval_cmp(one->min, two->min) != 0)
792 return 0;
793 if (sval_cmp(one->max, two->max) != 0)
794 return 0;
795 return 1;
796 }
797
798 int rl_equiv(struct range_list *one, struct range_list *two)
799 {
800 struct data_range *one_range;
801 struct data_range *two_range;
802
803 if (one == two)
804 return 1;
805
806 PREPARE_PTR_LIST(one, one_range);
807 PREPARE_PTR_LIST(two, two_range);
808 for (;;) {
809 if (!one_range && !two_range)
810 return 1;
811 if (!ranges_equiv(one_range, two_range))
812 return 0;
813 NEXT_PTR_LIST(one_range);
814 NEXT_PTR_LIST(two_range);
815 }
816 FINISH_PTR_LIST(two_range);
817 FINISH_PTR_LIST(one_range);
818
819 return 1;
820 }
821
822 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
823 {
824 switch (comparison) {
825 case '<':
826 case SPECIAL_UNSIGNED_LT:
827 if (sval_cmp(left->min, right->max) < 0)
828 return 1;
829 return 0;
830 case SPECIAL_UNSIGNED_LTE:
831 case SPECIAL_LTE:
832 if (sval_cmp(left->min, right->max) <= 0)
833 return 1;
834 return 0;
835 case SPECIAL_EQUAL:
836 if (sval_cmp(left->max, right->min) < 0)
837 return 0;
838 if (sval_cmp(left->min, right->max) > 0)
839 return 0;
840 return 1;
841 case SPECIAL_UNSIGNED_GTE:
842 case SPECIAL_GTE:
843 if (sval_cmp(left->max, right->min) >= 0)
844 return 1;
845 return 0;
846 case '>':
847 case SPECIAL_UNSIGNED_GT:
848 if (sval_cmp(left->max, right->min) > 0)
849 return 1;
850 return 0;
851 case SPECIAL_NOTEQUAL:
852 if (sval_cmp(left->min, left->max) != 0)
853 return 1;
854 if (sval_cmp(right->min, right->max) != 0)
855 return 1;
856 if (sval_cmp(left->min, right->min) != 0)
857 return 1;
858 return 0;
859 default:
860 sm_msg("unhandled comparison %d\n", comparison);
861 return 0;
862 }
863 return 0;
864 }
865
866 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
867 {
868 if (left)
869 return true_comparison_range(var, comparison, val);
870 else
871 return true_comparison_range(val, comparison, var);
872 }
873
874 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
875 {
876 switch (comparison) {
877 case '<':
878 case SPECIAL_UNSIGNED_LT:
879 if (sval_cmp(left->max, right->min) >= 0)
880 return 1;
881 return 0;
882 case SPECIAL_UNSIGNED_LTE:
883 case SPECIAL_LTE:
884 if (sval_cmp(left->max, right->min) > 0)
885 return 1;
886 return 0;
887 case SPECIAL_EQUAL:
888 if (sval_cmp(left->min, left->max) != 0)
889 return 1;
890 if (sval_cmp(right->min, right->max) != 0)
891 return 1;
892 if (sval_cmp(left->min, right->min) != 0)
893 return 1;
894 return 0;
895 case SPECIAL_UNSIGNED_GTE:
896 case SPECIAL_GTE:
897 if (sval_cmp(left->min, right->max) < 0)
898 return 1;
899 return 0;
900 case '>':
901 case SPECIAL_UNSIGNED_GT:
902 if (sval_cmp(left->min, right->max) <= 0)
903 return 1;
904 return 0;
905 case SPECIAL_NOTEQUAL:
906 if (sval_cmp(left->max, right->min) < 0)
907 return 0;
908 if (sval_cmp(left->min, right->max) > 0)
909 return 0;
910 return 1;
911 default:
912 sm_msg("unhandled comparison %d\n", comparison);
913 return 0;
914 }
915 return 0;
916 }
917
918 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
919 {
920 if (left)
921 return false_comparison_range_sval(var, comparison, val);
922 else
923 return false_comparison_range_sval(val, comparison, var);
924 }
925
926 int possibly_true(struct expression *left, int comparison, struct expression *right)
927 {
928 struct range_list *rl_left, *rl_right;
929 struct data_range *tmp_left, *tmp_right;
930 struct symbol *type;
931
932 if (!get_implied_rl(left, &rl_left))
933 return 1;
934 if (!get_implied_rl(right, &rl_right))
935 return 1;
936
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)
941 type = &int_ctype;
942
943 rl_left = cast_rl(type, rl_left);
944 rl_right = cast_rl(type, rl_right);
945
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))
949 return 1;
950 } END_FOR_EACH_PTR(tmp_right);
951 } END_FOR_EACH_PTR(tmp_left);
952 return 0;
953 }
954
955 int possibly_false(struct expression *left, int comparison, struct expression *right)
956 {
957 struct range_list *rl_left, *rl_right;
958 struct data_range *tmp_left, *tmp_right;
959 struct symbol *type;
960
961 if (!get_implied_rl(left, &rl_left))
962 return 1;
963 if (!get_implied_rl(right, &rl_right))
964 return 1;
965
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)
970 type = &int_ctype;
971
972 rl_left = cast_rl(type, rl_left);
973 rl_right = cast_rl(type, rl_right);
974
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))
978 return 1;
979 } END_FOR_EACH_PTR(tmp_right);
980 } END_FOR_EACH_PTR(tmp_left);
981 return 0;
982 }
983
984 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
985 {
986 struct data_range *left_tmp, *right_tmp;
987 struct symbol *type;
988
989 if (!left_ranges || !right_ranges)
990 return 1;
991
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)
996 type = &int_ctype;
997
998 left_ranges = cast_rl(type, left_ranges);
999 right_ranges = cast_rl(type, right_ranges);
1000
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))
1004 return 1;
1005 } END_FOR_EACH_PTR(right_tmp);
1006 } END_FOR_EACH_PTR(left_tmp);
1007 return 0;
1008 }
1009
1010 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1011 {
1012 struct data_range *left_tmp, *right_tmp;
1013 struct symbol *type;
1014
1015 if (!left_ranges || !right_ranges)
1016 return 1;
1017
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)
1022 type = &int_ctype;
1023
1024 left_ranges = cast_rl(type, left_ranges);
1025 right_ranges = cast_rl(type, right_ranges);
1026
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))
1030 return 1;
1031 } END_FOR_EACH_PTR(right_tmp);
1032 } END_FOR_EACH_PTR(left_tmp);
1033 return 0;
1034 }
1035
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)
1038 {
1039 if (left)
1040 return possibly_true_rl(a, comparison, b);
1041 else
1042 return possibly_true_rl(b, comparison, a);
1043 }
1044
1045 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1046 {
1047 if (left)
1048 return possibly_false_rl(a, comparison, b);
1049 else
1050 return possibly_false_rl(b, comparison, a);
1051 }
1052
1053 int rl_has_sval(struct range_list *rl, sval_t sval)
1054 {
1055 struct data_range *tmp;
1056
1057 FOR_EACH_PTR(rl, tmp) {
1058 if (sval_cmp(tmp->min, sval) <= 0 &&
1059 sval_cmp(tmp->max, sval) >= 0)
1060 return 1;
1061 } END_FOR_EACH_PTR(tmp);
1062 return 0;
1063 }
1064
1065 void tack_on(struct range_list **list, struct data_range *drange)
1066 {
1067 add_ptr_list(list, drange);
1068 }
1069
1070 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
1071 {
1072 add_ptr_list(rl_stack, rl);
1073 }
1074
1075 struct range_list *pop_rl(struct range_list_stack **rl_stack)
1076 {
1077 struct range_list *rl;
1078
1079 rl = last_ptr_list((struct ptr_list *)*rl_stack);
1080 delete_ptr_list_last((struct ptr_list **)rl_stack);
1081 return rl;
1082 }
1083
1084 struct range_list *top_rl(struct range_list_stack *rl_stack)
1085 {
1086 struct range_list *rl;
1087
1088 rl = last_ptr_list((struct ptr_list *)rl_stack);
1089 return rl;
1090 }
1091
1092 void filter_top_rl(struct range_list_stack **rl_stack, struct range_list *filter)
1093 {
1094 struct range_list *rl;
1095
1096 rl = pop_rl(rl_stack);
1097 rl = rl_filter(rl, filter);
1098 push_rl(rl_stack, rl);
1099 }
1100
1101 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1102 {
1103 struct data_range *tmp;
1104 struct range_list *ret = NULL;
1105 sval_t min, max;
1106
1107 if (!rl)
1108 return NULL;
1109
1110 if (!type || type == rl_type(rl))
1111 return rl;
1112
1113 FOR_EACH_PTR(rl, tmp) {
1114 min = tmp->min;
1115 max = tmp->max;
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);
1119 }
1120 if (sval_cmp(min, max) > 0) {
1121 min = sval_cast(type, min);
1122 max = sval_cast(type, max);
1123 }
1124 add_range_t(type, &ret, min, max);
1125 } END_FOR_EACH_PTR(tmp);
1126
1127 return ret;
1128 }
1129
1130 static int rl_is_sane(struct range_list *rl)
1131 {
1132 struct data_range *tmp;
1133 struct symbol *type;
1134
1135 type = rl_type(rl);
1136 FOR_EACH_PTR(rl, tmp) {
1137 if (!sval_fits(type, tmp->min))
1138 return 0;
1139 if (!sval_fits(type, tmp->max))
1140 return 0;
1141 if (sval_cmp(tmp->min, tmp->max) > 0)
1142 return 0;
1143 } END_FOR_EACH_PTR(tmp);
1144
1145 return 1;
1146 }
1147
1148 static int rl_type_consistent(struct range_list *rl)
1149 {
1150 struct data_range *tmp;
1151 struct symbol *type;
1152
1153 type = rl_type(rl);
1154 FOR_EACH_PTR(rl, tmp) {
1155 if (type != tmp->min.type || type != tmp->max.type)
1156 return 0;
1157 } END_FOR_EACH_PTR(tmp);
1158 return 1;
1159 }
1160
1161 static struct range_list *cast_to_bool(struct range_list *rl)
1162 {
1163 struct data_range *tmp;
1164 struct range_list *ret = NULL;
1165 int has_one = 0;
1166 int has_zero = 0;
1167 sval_t min = { .type = &bool_ctype };
1168 sval_t max = { .type = &bool_ctype };
1169
1170 FOR_EACH_PTR(rl, tmp) {
1171 if (tmp->min.value || tmp->max.value)
1172 has_one = 1;
1173 if (sval_is_negative(tmp->min) &&
1174 sval_is_negative(tmp->max))
1175 continue;
1176 if (tmp->min.value == 0 ||
1177 tmp->max.value == 0)
1178 has_zero = 1;
1179 if (sval_is_negative(tmp->min) &&
1180 tmp->max.value > 0)
1181 has_zero = 1;
1182 } END_FOR_EACH_PTR(tmp);
1183
1184 if (!has_zero)
1185 min.value = 1;
1186 if (has_one)
1187 max.value = 1;
1188
1189 add_range(&ret, min, max);
1190 return ret;
1191 }
1192
1193 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1194 {
1195 struct data_range *tmp;
1196 struct range_list *ret = NULL;
1197
1198 if (!rl)
1199 return NULL;
1200
1201 if (!type)
1202 return rl;
1203 if (!rl_is_sane(rl))
1204 return alloc_whole_rl(type);
1205 if (type == rl_type(rl) && rl_type_consistent(rl))
1206 return rl;
1207
1208 if (type == &bool_ctype)
1209 return cast_to_bool(rl);
1210
1211 FOR_EACH_PTR(rl, tmp) {
1212 add_range_t(type, &ret, tmp->min, tmp->max);
1213 } END_FOR_EACH_PTR(tmp);
1214
1215 if (!ret)
1216 return alloc_whole_rl(type);
1217
1218 return ret;
1219 }
1220
1221 struct range_list *rl_invert(struct range_list *orig)
1222 {
1223 struct range_list *ret = NULL;
1224 struct data_range *tmp;
1225 sval_t gap_min, abs_max, sval;
1226
1227 if (!orig)
1228 return NULL;
1229 if (type_bits(rl_type(orig)) < 0) /* void type mostly */
1230 return NULL;
1231
1232 gap_min = sval_type_min(rl_min(orig).type);
1233 abs_max = sval_type_max(rl_max(orig).type);
1234
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);
1239 }
1240 if (sval_cmp(tmp->max, abs_max) == 0)
1241 return ret;
1242 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
1243 } END_FOR_EACH_PTR(tmp);
1244
1245 if (sval_cmp(gap_min, abs_max) <= 0)
1246 add_range(&ret, gap_min, abs_max);
1247
1248 return ret;
1249 }
1250
1251 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1252 {
1253 struct data_range *tmp;
1254
1255 FOR_EACH_PTR(filter, tmp) {
1256 rl = remove_range(rl, tmp->min, tmp->max);
1257 } END_FOR_EACH_PTR(tmp);
1258
1259 return rl;
1260 }
1261
1262 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1263 {
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;
1270
1271 if (!two)
1272 return NULL;
1273 if (!one)
1274 return NULL;
1275
1276 one_orig = one;
1277 two_orig = two;
1278
1279 ret_type = rl_type(one);
1280 small_type = rl_type(one);
1281 large_type = rl_type(two);
1282
1283 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1284 small_type = rl_type(two);
1285 large_type = rl_type(one);
1286 }
1287
1288 one = cast_rl(large_type, one);
1289 two = cast_rl(large_type, two);
1290
1291 ret = one;
1292 one = rl_invert(one);
1293 two = rl_invert(two);
1294
1295 ret = rl_filter(ret, one);
1296 ret = rl_filter(ret, two);
1297
1298 one = cast_rl(small_type, one_orig);
1299 two = cast_rl(small_type, two_orig);
1300
1301 one = rl_invert(one);
1302 two = rl_invert(two);
1303
1304 ret = cast_rl(small_type, ret);
1305 ret = rl_filter(ret, one);
1306 ret = rl_filter(ret, two);
1307
1308 return cast_rl(ret_type, ret);
1309 }
1310
1311 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1312 {
1313 sval_t zero;
1314 sval_t max;
1315
1316 max = rl_max(right);
1317 if (sval_is_max(max))
1318 return left;
1319 if (max.value == 0)
1320 return NULL;
1321 max.value--;
1322 if (sval_is_negative(max))
1323 return NULL;
1324 if (sval_cmp(rl_max(left), max) < 0)
1325 return left;
1326 zero = max;
1327 zero.value = 0;
1328 return alloc_rl(zero, max);
1329 }
1330
1331 static struct range_list *get_neg_rl(struct range_list *rl)
1332 {
1333 struct data_range *tmp;
1334 struct data_range *new;
1335 struct range_list *ret = NULL;
1336
1337 if (!rl)
1338 return NULL;
1339 if (sval_is_positive(rl_min(rl)))
1340 return NULL;
1341
1342 FOR_EACH_PTR(rl, tmp) {
1343 if (sval_is_positive(tmp->min))
1344 return ret;
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);
1349 return ret;
1350 }
1351 add_range(&ret, tmp->min, tmp->max);
1352 } END_FOR_EACH_PTR(tmp);
1353
1354 return ret;
1355 }
1356
1357 static struct range_list *get_pos_rl(struct range_list *rl)
1358 {
1359 struct data_range *tmp;
1360 struct data_range *new;
1361 struct range_list *ret = NULL;
1362
1363 if (!rl)
1364 return NULL;
1365 if (sval_is_negative(rl_max(rl)))
1366 return NULL;
1367
1368 FOR_EACH_PTR(rl, tmp) {
1369 if (sval_is_negative(tmp->max))
1370 continue;
1371 if (sval_is_positive(tmp->min)) {
1372 add_range(&ret, tmp->min, tmp->max);
1373 continue;
1374 }
1375 new = alloc_range(tmp->min, tmp->max);
1376 new->min.value = 0;
1377 add_range(&ret, new->min, new->max);
1378 } END_FOR_EACH_PTR(tmp);
1379
1380 return ret;
1381 }
1382
1383 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1384 {
1385 sval_t right_min, right_max;
1386 sval_t min, max;
1387
1388 if (!left || !right)
1389 return NULL;
1390
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)
1395 return NULL;
1396 if (right_min.value == 0)
1397 right_min.value = 1;
1398 if (right_max.value == 0)
1399 right_max.value = -1;
1400
1401 max = sval_binop(rl_max(left), '/', right_min);
1402 min = sval_binop(rl_min(left), '/', right_max);
1403
1404 return alloc_rl(min, max);
1405 }
1406
1407 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1408 {
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;
1412
1413 if (is_whole_rl(right))
1414 return NULL;
1415
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);
1420
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);
1425
1426 ret = rl_union(neg_neg, neg_pos);
1427 ret = rl_union(ret, pos_neg);
1428 return rl_union(ret, pos_pos);
1429 }
1430
1431 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1432 {
1433 sval_t min, max;
1434
1435 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1436 return NULL;
1437 min = sval_binop(rl_min(left), op, rl_min(right));
1438
1439 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1440 return NULL;
1441 max = sval_binop(rl_max(left), op, rl_max(right));
1442
1443 return alloc_rl(min, max);
1444 }
1445
1446 static unsigned long long rl_bits_always_set(struct range_list *rl)
1447 {
1448 return sval_fls_mask(rl_min(rl));
1449 }
1450
1451 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1452 {
1453 return sval_fls_mask(rl_max(rl));
1454 }
1455
1456 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1457 {
1458 unsigned long long left_min, left_max, right_min, right_max;
1459 sval_t min, max;
1460 sval_t sval;
1461
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);
1465
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);
1470
1471 min.type = max.type = &ullong_ctype;
1472 min.uvalue = left_min | right_min;
1473 max.uvalue = left_max | right_max;
1474
1475 return cast_rl(rl_type(left), alloc_rl(min, max));
1476 }
1477
1478 static struct range_list *handle_XOR_rl(struct range_list *left, struct range_list *right)
1479 {
1480 unsigned long long left_set, left_maybe;
1481 unsigned long long right_set, right_maybe;
1482 sval_t zero, max;
1483
1484 left_set = rl_bits_always_set(left);
1485 left_maybe = rl_bits_maybe_set(left);
1486
1487 right_set = rl_bits_always_set(right);
1488 right_maybe = rl_bits_maybe_set(right);
1489
1490 zero = max = rl_min(left);
1491 zero.uvalue = 0;
1492 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1493
1494 return cast_rl(rl_type(left), alloc_rl(zero, max));
1495 }
1496
1497 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1498 {
1499 struct symbol *cast_type;
1500 sval_t left_sval, right_sval;
1501 struct range_list *ret = NULL;
1502
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;
1508
1509 left = cast_rl(cast_type, left);
1510 right = cast_rl(cast_type, right);
1511
1512 if (!left || !right)
1513 return alloc_whole_rl(cast_type);
1514
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);
1518 }
1519
1520 switch (op) {
1521 case '%':
1522 ret = handle_mod_rl(left, right);
1523 break;
1524 case '/':
1525 ret = handle_divide_rl(left, right);
1526 break;
1527 case '*':
1528 case '+':
1529 ret = handle_add_mult_rl(left, op, right);
1530 break;
1531 case '|':
1532 ret = handle_OR_rl(left, right);
1533 break;
1534 case '^':
1535 ret = handle_XOR_rl(left, right);
1536 break;
1537
1538 /* FIXME: Do the rest as well */
1539 case '-':
1540 case '&':
1541 case SPECIAL_RIGHTSHIFT:
1542 case SPECIAL_LEFTSHIFT:
1543 break;
1544 }
1545
1546 if (!ret)
1547 ret = alloc_whole_rl(cast_type);
1548 return ret;
1549 }
1550
1551 void free_rl(struct range_list **rlist)
1552 {
1553 __free_ptr_list((struct ptr_list **)rlist);
1554 }
1555
1556 static void free_single_dinfo(struct data_info *dinfo)
1557 {
1558 free_rl(&dinfo->value_ranges);
1559 }
1560
1561 static void free_dinfos(struct allocation_blob *blob)
1562 {
1563 unsigned int size = sizeof(struct data_info);
1564 unsigned int offset = 0;
1565
1566 while (offset < blob->offset) {
1567 free_single_dinfo((struct data_info *)(blob->data + offset));
1568 offset += size;
1569 }
1570 }
1571
1572 void free_data_info_allocs(void)
1573 {
1574 struct allocator_struct *desc = &data_info_allocator;
1575 struct allocation_blob *blob = desc->blobs;
1576
1577 desc->blobs = NULL;
1578 desc->allocations = 0;
1579 desc->total_bytes = 0;
1580 desc->useful_bytes = 0;
1581 desc->freelist = NULL;
1582 while (blob) {
1583 struct allocation_blob *next = blob->next;
1584 free_dinfos(blob);
1585 blob_free(blob, desc->chunking);
1586 blob = next;
1587 }
1588 clear_data_range_alloc();
1589 }
1590
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)
1594 {
1595 struct range_list *left_true, *left_false;
1596 struct range_list *right_true, *right_false;
1597 sval_t min, max;
1598
1599 min = sval_type_min(rl_type(left_orig));
1600 max = sval_type_max(rl_type(left_orig));
1601
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);
1606
1607 switch (op) {
1608 case '<':
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)));
1613 }
1614
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);
1618 break;
1619 case SPECIAL_UNSIGNED_LTE:
1620 case SPECIAL_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));
1624
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);
1628
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));
1633 break;
1634 case SPECIAL_EQUAL:
1635 if (!sval_is_max(rl_max(right_orig))) {
1636 left_true = remove_range(left_true, add_one(rl_max(right_orig)), max);
1637 }
1638 if (!sval_is_min(rl_min(right_orig))) {
1639 left_true = remove_range(left_true, min, sub_one(rl_min(right_orig)));
1640 }
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));
1643
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));
1650 break;
1651 case SPECIAL_UNSIGNED_GTE:
1652 case SPECIAL_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);
1656
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));
1660
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));
1665 break;
1666 case '>':
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);
1671
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)));
1675 break;
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));
1683
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));
1690 break;
1691 default:
1692 sm_msg("internal error: unhandled comparison %d", op);
1693 return;
1694 }
1695
1696 if (left_true_rl) {
1697 *left_true_rl = left_true;
1698 *left_false_rl = left_false;
1699 }
1700 if (right_true_rl) {
1701 *right_true_rl = right_true;
1702 *right_false_rl = right_false;
1703 }
1704 }
Static analysis for C