?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
implied: use a time based timeout instead of counting ->nr_children
[smatch.git] / smatch_ranges.c
blobd83e2209a81b30f50a9f44837f8ff26afb32e597
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[512];
32 int i = 0;
33
34 full[0] = '\0';
35 full[sizeof(full) - 1] = '\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 if (strlen(full) == sizeof(full) - 1)
48 full[sizeof(full) - 2] = '+';
49 return alloc_sname(full);
50 }
51
52 static int sval_too_big(struct symbol *type, sval_t sval)
53 {
54 if (type_bits(type) >= 32 &&
55 type_bits(sval.type) <= type_bits(type))
56 return 0;
57 if (sval.uvalue <= ((1ULL << type_bits(type)) - 1))
58 return 0;
59 if (type_signed(sval.type)) {
60 if (type_unsigned(type)) {
61 unsigned long long neg = ~sval.uvalue;
62 if (neg <= sval_type_max(type).uvalue)
63 return 0;
64 }
65 if (sval.value < sval_type_min(type).value)
66 return 1;
67 if (sval.value > sval_type_max(type).value)
68 return 1;
69 return 0;
70 }
71 if (sval.uvalue > sval_type_max(type).uvalue)
72 return 1;
73 return 0;
74 }
75
76 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
77 {
78 /* If we're just adding a number, cast it and add it */
79 if (sval_cmp(min, max) == 0) {
80 add_range(rl, sval_cast(type, min), sval_cast(type, max));
81 return;
82 }
83
84 /* If the range is within the type range then add it */
85 if (sval_fits(type, min) && sval_fits(type, max)) {
86 add_range(rl, sval_cast(type, min), sval_cast(type, max));
87 return;
88 }
89
90 /*
91 * If the range we are adding has more bits than the range type then
92 * add the whole range type. Eg:
93 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
94 * This isn't totally the right thing to do. We could be more granular.
95 */
96 if (sval_too_big(type, min) || sval_too_big(type, max)) {
97 add_range(rl, sval_type_min(type), sval_type_max(type));
98 return;
99 }
100
101 /* Cast negative values to high positive values */
102 if (sval_is_negative(min) && type_unsigned(type)) {
103 if (sval_is_positive(max)) {
104 if (sval_too_high(type, max)) {
105 add_range(rl, sval_type_min(type), sval_type_max(type));
106 return;
107 }
108 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
109 max = sval_type_max(type);
110 } else {
111 max = sval_cast(type, max);
112 }
113 min = sval_cast(type, min);
114 add_range(rl, min, max);
115 }
116
117 /* Cast high positive numbers to negative */
118 if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
119 if (!sval_is_negative(sval_cast(type, min))) {
120 add_range(rl, sval_cast(type, min), sval_type_max(type));
121 min = sval_type_min(type);
122 } else {
123 min = sval_cast(type, min);
124 }
125 max = sval_cast(type, max);
126 add_range(rl, min, max);
127 }
128
129 add_range(rl, sval_cast(type, min), sval_cast(type, max));
130 return;
131 }
132
133 static int str_to_comparison_arg_helper(const char *str,
134 struct expression *call, int *comparison,
135 struct expression **arg, char **endp)
136 {
137 int param;
138 char *c = (char *)str;
139
140 if (*c != '[')
141 return 0;
142 c++;
143
144 if (*c == '<') {
145 c++;
146 if (*c == '=') {
147 *comparison = SPECIAL_LTE;
148 c++;
149 } else {
150 *comparison = '<';
151 }
152 } else if (*c == '=') {
153 c++;
154 c++;
155 *comparison = SPECIAL_EQUAL;
156 } else if (*c == '>') {
157 c++;
158 if (*c == '=') {
159 *comparison = SPECIAL_GTE;
160 c++;
161 } else {
162 *comparison = '>';
163 }
164 } else if (*c == '!') {
165 c++;
166 c++;
167 *comparison = SPECIAL_NOTEQUAL;
168 } else {
169 return 0;
170 }
171
172 if (*c != '$')
173 return 0;
174 c++;
175
176 param = strtoll(c, &c, 10);
177 c++; /* skip the ']' character */
178 if (endp)
179 *endp = (char *)c;
180
181 if (!call)
182 return 0;
183 *arg = get_argument_from_call_expr(call->args, param);
184 if (!*arg)
185 return 0;
186 return 1;
187 }
188
189 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
190 {
191 while (1) {
192 if (!*str)
193 return 0;
194 if (*str == '[')
195 break;
196 str++;
197 }
198 return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
199 }
200
201 static int get_val_from_key(int use_max, struct symbol *type, char *c, struct expression *call, char **endp, sval_t *sval)
202 {
203 struct expression *arg;
204 int comparison;
205 sval_t ret, tmp;
206
207 if (use_max)
208 ret = sval_type_max(type);
209 else
210 ret = sval_type_min(type);
211
212 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
213 *sval = ret;
214 return 0;
215 }
216
217 if (use_max && get_implied_max(arg, &tmp)) {
218 ret = tmp;
219 if (comparison == '<') {
220 tmp.value = 1;
221 ret = sval_binop(ret, '-', tmp);
222 }
223 }
224 if (!use_max && get_implied_min(arg, &tmp)) {
225 ret = tmp;
226 if (comparison == '>') {
227 tmp.value = 1;
228 ret = sval_binop(ret, '+', tmp);
229 }
230 }
231
232 *sval = ret;
233 return 1;
234 }
235
236 static sval_t add_one(sval_t sval)
237 {
238 sval.value++;
239 return sval;
240 }
241
242 static sval_t sub_one(sval_t sval)
243 {
244 sval.value--;
245 return sval;
246 }
247
248 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
249 {
250 struct range_list *left_orig = *rl;
251 struct range_list *right_orig = right;
252 struct range_list *ret_rl = *rl;
253 struct symbol *cast_type;
254 sval_t min, max;
255
256 cast_type = rl_type(left_orig);
257 if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
258 cast_type = rl_type(right_orig);
259 if (sval_type_max(cast_type).uvalue < INT_MAX)
260 cast_type = &int_ctype;
261
262 min = sval_type_min(cast_type);
263 max = sval_type_max(cast_type);
264 left_orig = cast_rl(cast_type, left_orig);
265 right_orig = cast_rl(cast_type, right_orig);
266
267 switch (comparison) {
268 case '<':
269 case SPECIAL_UNSIGNED_LT:
270 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
271 break;
272 case SPECIAL_LTE:
273 case SPECIAL_UNSIGNED_LTE:
274 if (!sval_is_max(rl_max(right_orig)))
275 ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
276 break;
277 case SPECIAL_EQUAL:
278 if (!sval_is_max(rl_max(right_orig)))
279 ret_rl = remove_range(ret_rl, add_one(rl_max(right_orig)), max);
280 if (!sval_is_min(rl_min(right_orig)))
281 ret_rl = remove_range(ret_rl, min, sub_one(rl_min(right_orig)));
282 break;
283 case SPECIAL_GTE:
284 case SPECIAL_UNSIGNED_GTE:
285 if (!sval_is_min(rl_min(right_orig)))
286 ret_rl = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
287 break;
288 case '>':
289 case SPECIAL_UNSIGNED_GT:
290 ret_rl = remove_range(left_orig, min, rl_min(right_orig));
291 break;
292 case SPECIAL_NOTEQUAL:
293 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
294 ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
295 break;
296 default:
297 sm_msg("internal error: unhandled comparison %s", show_special(comparison));
298 return;
299 }
300
301 *rl = cast_rl(rl_type(*rl), ret_rl);
302 }
303
304 static struct range_list *filter_by_comparison_call(char *c, struct expression *call, char **endp, struct range_list *start_rl)
305 {
306 struct symbol *type;
307 struct expression *arg;
308 struct range_list *casted_start, *right_orig;
309 int comparison;
310
311 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
312 return start_rl;
313
314 if (!get_implied_rl(arg, &right_orig))
315 return start_rl;
316
317 type = &int_ctype;
318 if (type_positive_bits(rl_type(start_rl)) > type_positive_bits(type))
319 type = rl_type(start_rl);
320 if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
321 type = rl_type(right_orig);
322
323 casted_start = cast_rl(type, start_rl);
324 right_orig = cast_rl(type, right_orig);
325
326 filter_by_comparison(&casted_start, comparison, right_orig);
327 return cast_rl(rl_type(start_rl), casted_start);
328 }
329
330 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
331 {
332 char *start = c;
333 sval_t ret;
334
335 if (!strncmp(start, "max", 3)) {
336 ret = sval_type_max(type);
337 c += 3;
338 } else if (!strncmp(start, "u64max", 6)) {
339 ret = sval_type_val(type, ULLONG_MAX);
340 c += 6;
341 } else if (!strncmp(start, "s64max", 6)) {
342 ret = sval_type_val(type, LLONG_MAX);
343 c += 6;
344 } else if (!strncmp(start, "u32max", 6)) {
345 ret = sval_type_val(type, UINT_MAX);
346 c += 6;
347 } else if (!strncmp(start, "s32max", 6)) {
348 ret = sval_type_val(type, INT_MAX);
349 c += 6;
350 } else if (!strncmp(start, "u16max", 6)) {
351 ret = sval_type_val(type, USHRT_MAX);
352 c += 6;
353 } else if (!strncmp(start, "s16max", 6)) {
354 ret = sval_type_val(type, SHRT_MAX);
355 c += 6;
356 } else if (!strncmp(start, "min", 3)) {
357 ret = sval_type_min(type);
358 c += 3;
359 } else if (!strncmp(start, "s64min", 6)) {
360 ret = sval_type_val(type, LLONG_MIN);
361 c += 6;
362 } else if (!strncmp(start, "s32min", 6)) {
363 ret = sval_type_val(type, INT_MIN);
364 c += 6;
365 } else if (!strncmp(start, "s16min", 6)) {
366 ret = sval_type_val(type, SHRT_MIN);
367 c += 6;
368 } else if (!strncmp(start, "long_min", 8)) {
369 ret = sval_type_val(type, LONG_MIN);
370 c += 8;
371 } else if (!strncmp(start, "long_max", 8)) {
372 ret = sval_type_val(type, LONG_MAX);
373 c += 8;
374 } else if (!strncmp(start, "ulong_max", 9)) {
375 ret = sval_type_val(type, ULONG_MAX);
376 c += 8;
377 } else if (!strncmp(start, "ptr_max", 7)) {
378 ret = sval_type_val(type, valid_ptr_max);
379 c += 8;
380 } else if (start[0] == '[') {
381 /* this parses [==p0] comparisons */
382 get_val_from_key(1, type, start, call, &c, &ret);
383 } else if (type_positive_bits(type) == 64) {
384 ret = sval_type_val(type, strtoull(start, &c, 10));
385 } else {
386 ret = sval_type_val(type, strtoll(start, &c, 10));
387 }
388 *endp = c;
389 return ret;
390 }
391
392 static char *jump_to_call_math(char *value)
393 {
394 char *c = value;
395
396 while (*c && *c != '[')
397 c++;
398
399 if (!*c)
400 return NULL;
401 c++;
402 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
403 return NULL;
404
405 return c;
406 }
407
408 static void str_to_rl_helper(struct expression *call, struct symbol *type, char *str, char **endp, struct range_list **rl)
409 {
410 struct range_list *rl_tmp = NULL;
411 sval_t min, max;
412 char *c;
413
414 min = sval_type_min(type);
415 max = sval_type_max(type);
416 c = str;
417 while (*c != '\0' && *c != '[') {
418 if (*c == '+') {
419 if (sval_cmp(min, sval_type_min(type)) != 0)
420 min = max;
421 max = sval_type_max(type);
422 add_range_t(type, &rl_tmp, min, max);
423 break;
424 }
425 if (*c == '(')
426 c++;
427 min = parse_val(0, call, type, c, &c);
428 if (!sval_fits(type, min))
429 min = sval_type_min(type);
430 max = min;
431 if (*c == ')')
432 c++;
433 if (*c == '\0' || *c == '[') {
434 add_range_t(type, &rl_tmp, min, min);
435 break;
436 }
437 if (*c == ',') {
438 add_range_t(type, &rl_tmp, min, min);
439 c++;
440 continue;
441 }
442 if (*c == '+') {
443 min = sval_type_max(type);
444 c++;
445 }
446 if (*c != '-') {
447 sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
448 break;
449 }
450 c++;
451 if (*c == '(')
452 c++;
453 max = parse_val(1, call, type, c, &c);
454 if (!sval_fits(type, max))
455 max = sval_type_max(type);
456 if (*c == '+') {
457 max = sval_type_max(type);
458 c++;
459 }
460 add_range_t(type, &rl_tmp, min, max);
461 if (*c == ')')
462 c++;
463 if (*c == ',')
464 c++;
465 }
466
467 *rl = rl_tmp;
468 *endp = c;
469 }
470
471 static void str_to_dinfo(struct expression *call, struct symbol *type, char *value, struct data_info *dinfo)
472 {
473 struct range_list *math_rl;
474 char *call_math;
475 char *c;
476 struct range_list *rl = NULL;
477
478 if (!type)
479 type = &llong_ctype;
480
481 if (strcmp(value, "empty") == 0)
482 return;
483
484 if (strncmp(value, "[==$", 4) == 0) {
485 struct expression *arg;
486 int comparison;
487
488 if (!str_to_comparison_arg(value, call, &comparison, &arg))
489 return;
490 if (!get_implied_rl(arg, &rl))
491 return;
492 goto cast;
493 }
494
495 str_to_rl_helper(call, type, value, &c, &rl);
496 if (*c == '\0')
497 goto cast;
498
499 call_math = jump_to_call_math(value);
500 if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
501 rl = rl_intersection(rl, math_rl);
502 goto cast;
503 }
504
505 /*
506 * For now if we already tried to handle the call math and couldn't
507 * figure it out then bail.
508 */
509 if (jump_to_call_math(c) == c + 1)
510 goto cast;
511
512 rl = filter_by_comparison_call(c, call, &c, rl);
513
514 cast:
515 rl = cast_rl(type, rl);
516 dinfo->value_ranges = rl;
517 }
518
519 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
520 {
521 struct data_info dinfo = {};
522
523 str_to_dinfo(NULL, type, value, &dinfo);
524 *rl = dinfo.value_ranges;
525 }
526
527 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
528 {
529 struct data_info dinfo = {};
530
531 str_to_dinfo(strip_expr(expr), type, value, &dinfo);
532 *rl = dinfo.value_ranges;
533 }
534
535 int is_whole_rl(struct range_list *rl)
536 {
537 struct data_range *drange;
538
539 if (ptr_list_empty(rl))
540 return 0;
541 drange = first_ptr_list((struct ptr_list *)rl);
542 if (sval_is_min(drange->min) && sval_is_max(drange->max))
543 return 1;
544 return 0;
545 }
546
547 int is_whole_rl_non_zero(struct range_list *rl)
548 {
549 struct data_range *drange;
550
551 if (ptr_list_empty(rl))
552 return 0;
553 drange = first_ptr_list((struct ptr_list *)rl);
554 if (sval_unsigned(drange->min) &&
555 drange->min.value == 1 &&
556 sval_is_max(drange->max))
557 return 1;
558 if (!sval_is_min(drange->min) || drange->max.value != -1)
559 return 0;
560 drange = last_ptr_list((struct ptr_list *)rl);
561 if (drange->min.value != 1 || !sval_is_max(drange->max))
562 return 0;
563 return 1;
564 }
565
566 sval_t rl_min(struct range_list *rl)
567 {
568 struct data_range *drange;
569 sval_t ret;
570
571 ret.type = &llong_ctype;
572 ret.value = LLONG_MIN;
573 if (ptr_list_empty(rl))
574 return ret;
575 drange = first_ptr_list((struct ptr_list *)rl);
576 return drange->min;
577 }
578
579 sval_t rl_max(struct range_list *rl)
580 {
581 struct data_range *drange;
582 sval_t ret;
583
584 ret.type = &llong_ctype;
585 ret.value = LLONG_MAX;
586 if (ptr_list_empty(rl))
587 return ret;
588 drange = last_ptr_list((struct ptr_list *)rl);
589 return drange->max;
590 }
591
592 int rl_to_sval(struct range_list *rl, sval_t *sval)
593 {
594 sval_t min, max;
595
596 if (!rl)
597 return 0;
598
599 min = rl_min(rl);
600 max = rl_max(rl);
601 if (sval_cmp(min, max) != 0)
602 return 0;
603 *sval = min;
604 return 1;
605 }
606
607 struct symbol *rl_type(struct range_list *rl)
608 {
609 if (!rl)
610 return NULL;
611 return rl_min(rl).type;
612 }
613
614 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
615 {
616 struct data_range *ret;
617
618 if (perm)
619 ret = __alloc_perm_data_range(0);
620 else
621 ret = __alloc_data_range(0);
622 ret->min = min;
623 ret->max = max;
624 return ret;
625 }
626
627 struct data_range *alloc_range(sval_t min, sval_t max)
628 {
629 return alloc_range_helper_sval(min, max, 0);
630 }
631
632 struct data_range *alloc_range_perm(sval_t min, sval_t max)
633 {
634 return alloc_range_helper_sval(min, max, 1);
635 }
636
637 struct range_list *alloc_rl(sval_t min, sval_t max)
638 {
639 struct range_list *rl = NULL;
640
641 if (sval_cmp(min, max) > 0)
642 return alloc_whole_rl(min.type);
643
644 add_range(&rl, min, max);
645 return rl;
646 }
647
648 struct range_list *alloc_whole_rl(struct symbol *type)
649 {
650 if (!type || type_positive_bits(type) < 0)
651 type = &llong_ctype;
652 if (type->type == SYM_ARRAY)
653 type = &ptr_ctype;
654
655 return alloc_rl(sval_type_min(type), sval_type_max(type));
656 }
657
658 void add_range(struct range_list **list, sval_t min, sval_t max)
659 {
660 struct data_range *tmp;
661 struct data_range *new = NULL;
662 int check_next = 0;
663
664 /*
665 * There is at least on valid reason why the types might be confusing
666 * and that's when you have a void pointer and on some paths you treat
667 * it as a u8 pointer and on other paths you treat it as a u16 pointer.
668 * This case is hard to deal with.
669 *
670 * There are other cases where we probably should be more specific about
671 * the types than we are. For example, we end up merging a lot of ulong
672 * with pointers and I have not figured out why we do that.
673 *
674 * But this hack works for both cases, I think. We cast it to pointers
675 * or we use the bigger size.
676 *
677 */
678 if (*list && rl_type(*list) != min.type) {
679 if (rl_type(*list)->type == SYM_PTR) {
680 min = sval_cast(rl_type(*list), min);
681 max = sval_cast(rl_type(*list), max);
682 } else if (min.type->type == SYM_PTR) {
683 *list = cast_rl(min.type, *list);
684 } else if (type_bits(rl_type(*list)) >= type_bits(min.type)) {
685 min = sval_cast(rl_type(*list), min);
686 max = sval_cast(rl_type(*list), max);
687 } else {
688 *list = cast_rl(min.type, *list);
689 }
690 }
691
692 if (sval_cmp(min, max) > 0) {
693 min = sval_type_min(min.type);
694 max = sval_type_max(min.type);
695 }
696
697 /*
698 * FIXME: This has a problem merging a range_list like: min-0,3-max
699 * with a range like 1-2. You end up with min-2,3-max instead of
700 * just min-max.
701 */
702 FOR_EACH_PTR(*list, tmp) {
703 if (check_next) {
704 /* Sometimes we overlap with more than one range
705 so we have to delete or modify the next range. */
706 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
707 /* join 2 ranges here */
708 new->max = tmp->max;
709 DELETE_CURRENT_PTR(tmp);
710 return;
711 }
712
713 /* Doesn't overlap with the next one. */
714 if (sval_cmp(max, tmp->min) < 0)
715 return;
716
717 if (sval_cmp(max, tmp->max) <= 0) {
718 /* Partially overlaps the next one. */
719 new->max = tmp->max;
720 DELETE_CURRENT_PTR(tmp);
721 return;
722 } else {
723 /* Completely overlaps the next one. */
724 DELETE_CURRENT_PTR(tmp);
725 /* there could be more ranges to delete */
726 continue;
727 }
728 }
729 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
730 /* join 2 ranges into a big range */
731 new = alloc_range(min, tmp->max);
732 REPLACE_CURRENT_PTR(tmp, new);
733 return;
734 }
735 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
736 new = alloc_range(min, max);
737 INSERT_CURRENT(new, tmp);
738 return;
739 }
740 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
741 if (sval_cmp(max, tmp->max) < 0)
742 max = tmp->max;
743 else
744 check_next = 1;
745 new = alloc_range(min, max);
746 REPLACE_CURRENT_PTR(tmp, new);
747 if (!check_next)
748 return;
749 continue;
750 }
751 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
752 return;
753 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
754 min = tmp->min;
755 new = alloc_range(min, max);
756 REPLACE_CURRENT_PTR(tmp, new);
757 check_next = 1;
758 continue;
759 }
760 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
761 /* join 2 ranges into a big range */
762 new = alloc_range(tmp->min, max);
763 REPLACE_CURRENT_PTR(tmp, new);
764 check_next = 1;
765 continue;
766 }
767 /* the new range is entirely above the existing ranges */
768 } END_FOR_EACH_PTR(tmp);
769 if (check_next)
770 return;
771 new = alloc_range(min, max);
772 add_ptr_list(list, new);
773 }
774
775 struct range_list *clone_rl(struct range_list *list)
776 {
777 struct data_range *tmp;
778 struct range_list *ret = NULL;
779
780 FOR_EACH_PTR(list, tmp) {
781 add_ptr_list(&ret, tmp);
782 } END_FOR_EACH_PTR(tmp);
783 return ret;
784 }
785
786 struct range_list *clone_rl_permanent(struct range_list *list)
787 {
788 struct data_range *tmp;
789 struct data_range *new;
790 struct range_list *ret = NULL;
791
792 FOR_EACH_PTR(list, tmp) {
793 new = alloc_range_perm(tmp->min, tmp->max);
794 add_ptr_list(&ret, new);
795 } END_FOR_EACH_PTR(tmp);
796 return ret;
797 }
798
799 struct range_list *rl_union(struct range_list *one, struct range_list *two)
800 {
801 struct data_range *tmp;
802 struct range_list *ret = NULL;
803
804 FOR_EACH_PTR(one, tmp) {
805 add_range(&ret, tmp->min, tmp->max);
806 } END_FOR_EACH_PTR(tmp);
807 FOR_EACH_PTR(two, tmp) {
808 add_range(&ret, tmp->min, tmp->max);
809 } END_FOR_EACH_PTR(tmp);
810 return ret;
811 }
812
813 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
814 {
815 struct data_range *tmp;
816 struct range_list *ret = NULL;
817
818 if (!list)
819 return NULL;
820
821 min = sval_cast(rl_type(list), min);
822 max = sval_cast(rl_type(list), max);
823 if (sval_cmp(min, max) > 0) {
824 sval_t tmp = min;
825 min = max;
826 max = tmp;
827 }
828
829 FOR_EACH_PTR(list, tmp) {
830 if (sval_cmp(tmp->max, min) < 0) {
831 add_range(&ret, tmp->min, tmp->max);
832 continue;
833 }
834 if (sval_cmp(tmp->min, max) > 0) {
835 add_range(&ret, tmp->min, tmp->max);
836 continue;
837 }
838 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
839 continue;
840 if (sval_cmp(tmp->min, min) >= 0) {
841 max.value++;
842 add_range(&ret, max, tmp->max);
843 } else if (sval_cmp(tmp->max, max) <= 0) {
844 min.value--;
845 add_range(&ret, tmp->min, min);
846 } else {
847 min.value--;
848 max.value++;
849 add_range(&ret, tmp->min, min);
850 add_range(&ret, max, tmp->max);
851 }
852 } END_FOR_EACH_PTR(tmp);
853 return ret;
854 }
855
856 int ranges_equiv(struct data_range *one, struct data_range *two)
857 {
858 if (!one && !two)
859 return 1;
860 if (!one || !two)
861 return 0;
862 if (sval_cmp(one->min, two->min) != 0)
863 return 0;
864 if (sval_cmp(one->max, two->max) != 0)
865 return 0;
866 return 1;
867 }
868
869 int rl_equiv(struct range_list *one, struct range_list *two)
870 {
871 struct data_range *one_range;
872 struct data_range *two_range;
873
874 if (one == two)
875 return 1;
876
877 PREPARE_PTR_LIST(one, one_range);
878 PREPARE_PTR_LIST(two, two_range);
879 for (;;) {
880 if (!one_range && !two_range)
881 return 1;
882 if (!ranges_equiv(one_range, two_range))
883 return 0;
884 NEXT_PTR_LIST(one_range);
885 NEXT_PTR_LIST(two_range);
886 }
887 FINISH_PTR_LIST(two_range);
888 FINISH_PTR_LIST(one_range);
889
890 return 1;
891 }
892
893 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
894 {
895 switch (comparison) {
896 case '<':
897 case SPECIAL_UNSIGNED_LT:
898 if (sval_cmp(left->min, right->max) < 0)
899 return 1;
900 return 0;
901 case SPECIAL_UNSIGNED_LTE:
902 case SPECIAL_LTE:
903 if (sval_cmp(left->min, right->max) <= 0)
904 return 1;
905 return 0;
906 case SPECIAL_EQUAL:
907 if (sval_cmp(left->max, right->min) < 0)
908 return 0;
909 if (sval_cmp(left->min, right->max) > 0)
910 return 0;
911 return 1;
912 case SPECIAL_UNSIGNED_GTE:
913 case SPECIAL_GTE:
914 if (sval_cmp(left->max, right->min) >= 0)
915 return 1;
916 return 0;
917 case '>':
918 case SPECIAL_UNSIGNED_GT:
919 if (sval_cmp(left->max, right->min) > 0)
920 return 1;
921 return 0;
922 case SPECIAL_NOTEQUAL:
923 if (sval_cmp(left->min, left->max) != 0)
924 return 1;
925 if (sval_cmp(right->min, right->max) != 0)
926 return 1;
927 if (sval_cmp(left->min, right->min) != 0)
928 return 1;
929 return 0;
930 default:
931 sm_msg("unhandled comparison %d\n", comparison);
932 return 0;
933 }
934 return 0;
935 }
936
937 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
938 {
939 if (left)
940 return true_comparison_range(var, comparison, val);
941 else
942 return true_comparison_range(val, comparison, var);
943 }
944
945 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
946 {
947 switch (comparison) {
948 case '<':
949 case SPECIAL_UNSIGNED_LT:
950 if (sval_cmp(left->max, right->min) >= 0)
951 return 1;
952 return 0;
953 case SPECIAL_UNSIGNED_LTE:
954 case SPECIAL_LTE:
955 if (sval_cmp(left->max, right->min) > 0)
956 return 1;
957 return 0;
958 case SPECIAL_EQUAL:
959 if (sval_cmp(left->min, left->max) != 0)
960 return 1;
961 if (sval_cmp(right->min, right->max) != 0)
962 return 1;
963 if (sval_cmp(left->min, right->min) != 0)
964 return 1;
965 return 0;
966 case SPECIAL_UNSIGNED_GTE:
967 case SPECIAL_GTE:
968 if (sval_cmp(left->min, right->max) < 0)
969 return 1;
970 return 0;
971 case '>':
972 case SPECIAL_UNSIGNED_GT:
973 if (sval_cmp(left->min, right->max) <= 0)
974 return 1;
975 return 0;
976 case SPECIAL_NOTEQUAL:
977 if (sval_cmp(left->max, right->min) < 0)
978 return 0;
979 if (sval_cmp(left->min, right->max) > 0)
980 return 0;
981 return 1;
982 default:
983 sm_msg("unhandled comparison %d\n", comparison);
984 return 0;
985 }
986 return 0;
987 }
988
989 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
990 {
991 if (left)
992 return false_comparison_range_sval(var, comparison, val);
993 else
994 return false_comparison_range_sval(val, comparison, var);
995 }
996
997 int possibly_true(struct expression *left, int comparison, struct expression *right)
998 {
999 struct range_list *rl_left, *rl_right;
1000 struct data_range *tmp_left, *tmp_right;
1001 struct symbol *type;
1002
1003 if (!get_implied_rl(left, &rl_left))
1004 return 1;
1005 if (!get_implied_rl(right, &rl_right))
1006 return 1;
1007
1008 type = rl_type(rl_left);
1009 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1010 type = rl_type(rl_right);
1011 if (type_positive_bits(type) < 31)
1012 type = &int_ctype;
1013
1014 rl_left = cast_rl(type, rl_left);
1015 rl_right = cast_rl(type, rl_right);
1016
1017 FOR_EACH_PTR(rl_left, tmp_left) {
1018 FOR_EACH_PTR(rl_right, tmp_right) {
1019 if (true_comparison_range(tmp_left, comparison, tmp_right))
1020 return 1;
1021 } END_FOR_EACH_PTR(tmp_right);
1022 } END_FOR_EACH_PTR(tmp_left);
1023 return 0;
1024 }
1025
1026 int possibly_false(struct expression *left, int comparison, struct expression *right)
1027 {
1028 struct range_list *rl_left, *rl_right;
1029 struct data_range *tmp_left, *tmp_right;
1030 struct symbol *type;
1031
1032 if (!get_implied_rl(left, &rl_left))
1033 return 1;
1034 if (!get_implied_rl(right, &rl_right))
1035 return 1;
1036
1037 type = rl_type(rl_left);
1038 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1039 type = rl_type(rl_right);
1040 if (type_positive_bits(type) < 31)
1041 type = &int_ctype;
1042
1043 rl_left = cast_rl(type, rl_left);
1044 rl_right = cast_rl(type, rl_right);
1045
1046 FOR_EACH_PTR(rl_left, tmp_left) {
1047 FOR_EACH_PTR(rl_right, tmp_right) {
1048 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
1049 return 1;
1050 } END_FOR_EACH_PTR(tmp_right);
1051 } END_FOR_EACH_PTR(tmp_left);
1052 return 0;
1053 }
1054
1055 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1056 {
1057 struct data_range *left_tmp, *right_tmp;
1058 struct symbol *type;
1059
1060 if (!left_ranges || !right_ranges)
1061 return 1;
1062
1063 type = rl_type(left_ranges);
1064 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1065 type = rl_type(right_ranges);
1066 if (type_positive_bits(type) < 31)
1067 type = &int_ctype;
1068
1069 left_ranges = cast_rl(type, left_ranges);
1070 right_ranges = cast_rl(type, right_ranges);
1071
1072 FOR_EACH_PTR(left_ranges, left_tmp) {
1073 FOR_EACH_PTR(right_ranges, right_tmp) {
1074 if (true_comparison_range(left_tmp, comparison, right_tmp))
1075 return 1;
1076 } END_FOR_EACH_PTR(right_tmp);
1077 } END_FOR_EACH_PTR(left_tmp);
1078 return 0;
1079 }
1080
1081 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1082 {
1083 struct data_range *left_tmp, *right_tmp;
1084 struct symbol *type;
1085
1086 if (!left_ranges || !right_ranges)
1087 return 1;
1088
1089 type = rl_type(left_ranges);
1090 if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1091 type = rl_type(right_ranges);
1092 if (type_positive_bits(type) < 31)
1093 type = &int_ctype;
1094
1095 left_ranges = cast_rl(type, left_ranges);
1096 right_ranges = cast_rl(type, right_ranges);
1097
1098 FOR_EACH_PTR(left_ranges, left_tmp) {
1099 FOR_EACH_PTR(right_ranges, right_tmp) {
1100 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
1101 return 1;
1102 } END_FOR_EACH_PTR(right_tmp);
1103 } END_FOR_EACH_PTR(left_tmp);
1104 return 0;
1105 }
1106
1107 /* FIXME: the _rl here stands for right left so really it should be _lr */
1108 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1109 {
1110 if (left)
1111 return possibly_true_rl(a, comparison, b);
1112 else
1113 return possibly_true_rl(b, comparison, a);
1114 }
1115
1116 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1117 {
1118 if (left)
1119 return possibly_false_rl(a, comparison, b);
1120 else
1121 return possibly_false_rl(b, comparison, a);
1122 }
1123
1124 int rl_has_sval(struct range_list *rl, sval_t sval)
1125 {
1126 struct data_range *tmp;
1127
1128 FOR_EACH_PTR(rl, tmp) {
1129 if (sval_cmp(tmp->min, sval) <= 0 &&
1130 sval_cmp(tmp->max, sval) >= 0)
1131 return 1;
1132 } END_FOR_EACH_PTR(tmp);
1133 return 0;
1134 }
1135
1136 void tack_on(struct range_list **list, struct data_range *drange)
1137 {
1138 add_ptr_list(list, drange);
1139 }
1140
1141 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
1142 {
1143 add_ptr_list(rl_stack, rl);
1144 }
1145
1146 struct range_list *pop_rl(struct range_list_stack **rl_stack)
1147 {
1148 struct range_list *rl;
1149
1150 rl = last_ptr_list((struct ptr_list *)*rl_stack);
1151 delete_ptr_list_last((struct ptr_list **)rl_stack);
1152 return rl;
1153 }
1154
1155 struct range_list *top_rl(struct range_list_stack *rl_stack)
1156 {
1157 struct range_list *rl;
1158
1159 rl = last_ptr_list((struct ptr_list *)rl_stack);
1160 return rl;
1161 }
1162
1163 void filter_top_rl(struct range_list_stack **rl_stack, struct range_list *filter)
1164 {
1165 struct range_list *rl;
1166
1167 rl = pop_rl(rl_stack);
1168 rl = rl_filter(rl, filter);
1169 push_rl(rl_stack, rl);
1170 }
1171
1172 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1173 {
1174 struct data_range *tmp;
1175 struct range_list *ret = NULL;
1176 sval_t min, max;
1177
1178 if (!rl)
1179 return NULL;
1180
1181 if (!type || type == rl_type(rl))
1182 return rl;
1183
1184 FOR_EACH_PTR(rl, tmp) {
1185 min = tmp->min;
1186 max = tmp->max;
1187 if (type_bits(type) < type_bits(rl_type(rl))) {
1188 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1189 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1190 }
1191 if (sval_cmp(min, max) > 0) {
1192 min = sval_cast(type, min);
1193 max = sval_cast(type, max);
1194 }
1195 add_range_t(type, &ret, min, max);
1196 } END_FOR_EACH_PTR(tmp);
1197
1198 return ret;
1199 }
1200
1201 static int rl_is_sane(struct range_list *rl)
1202 {
1203 struct data_range *tmp;
1204 struct symbol *type;
1205
1206 type = rl_type(rl);
1207 FOR_EACH_PTR(rl, tmp) {
1208 if (!sval_fits(type, tmp->min))
1209 return 0;
1210 if (!sval_fits(type, tmp->max))
1211 return 0;
1212 if (sval_cmp(tmp->min, tmp->max) > 0)
1213 return 0;
1214 } END_FOR_EACH_PTR(tmp);
1215
1216 return 1;
1217 }
1218
1219 static int rl_type_consistent(struct range_list *rl)
1220 {
1221 struct data_range *tmp;
1222 struct symbol *type;
1223
1224 type = rl_type(rl);
1225 FOR_EACH_PTR(rl, tmp) {
1226 if (type != tmp->min.type || type != tmp->max.type)
1227 return 0;
1228 } END_FOR_EACH_PTR(tmp);
1229 return 1;
1230 }
1231
1232 static struct range_list *cast_to_bool(struct range_list *rl)
1233 {
1234 struct data_range *tmp;
1235 struct range_list *ret = NULL;
1236 int has_one = 0;
1237 int has_zero = 0;
1238 sval_t min = { .type = &bool_ctype };
1239 sval_t max = { .type = &bool_ctype };
1240
1241 FOR_EACH_PTR(rl, tmp) {
1242 if (tmp->min.value || tmp->max.value)
1243 has_one = 1;
1244 if (sval_is_negative(tmp->min) &&
1245 sval_is_negative(tmp->max))
1246 continue;
1247 if (tmp->min.value == 0 ||
1248 tmp->max.value == 0)
1249 has_zero = 1;
1250 if (sval_is_negative(tmp->min) &&
1251 tmp->max.value > 0)
1252 has_zero = 1;
1253 } END_FOR_EACH_PTR(tmp);
1254
1255 if (!has_zero)
1256 min.value = 1;
1257 if (has_one)
1258 max.value = 1;
1259
1260 add_range(&ret, min, max);
1261 return ret;
1262 }
1263
1264 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1265 {
1266 struct data_range *tmp;
1267 struct range_list *ret = NULL;
1268
1269 if (!rl)
1270 return NULL;
1271
1272 if (!type)
1273 return rl;
1274 if (!rl_is_sane(rl))
1275 return alloc_whole_rl(type);
1276 if (type == rl_type(rl) && rl_type_consistent(rl))
1277 return rl;
1278
1279 if (type == &bool_ctype)
1280 return cast_to_bool(rl);
1281
1282 FOR_EACH_PTR(rl, tmp) {
1283 add_range_t(type, &ret, tmp->min, tmp->max);
1284 } END_FOR_EACH_PTR(tmp);
1285
1286 if (!ret)
1287 return alloc_whole_rl(type);
1288
1289 return ret;
1290 }
1291
1292 struct range_list *rl_invert(struct range_list *orig)
1293 {
1294 struct range_list *ret = NULL;
1295 struct data_range *tmp;
1296 sval_t gap_min, abs_max, sval;
1297
1298 if (!orig)
1299 return NULL;
1300 if (type_bits(rl_type(orig)) < 0) /* void type mostly */
1301 return NULL;
1302
1303 gap_min = sval_type_min(rl_min(orig).type);
1304 abs_max = sval_type_max(rl_max(orig).type);
1305
1306 FOR_EACH_PTR(orig, tmp) {
1307 if (sval_cmp(tmp->min, gap_min) > 0) {
1308 sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
1309 add_range(&ret, gap_min, sval);
1310 }
1311 if (sval_cmp(tmp->max, abs_max) == 0)
1312 return ret;
1313 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
1314 } END_FOR_EACH_PTR(tmp);
1315
1316 if (sval_cmp(gap_min, abs_max) <= 0)
1317 add_range(&ret, gap_min, abs_max);
1318
1319 return ret;
1320 }
1321
1322 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1323 {
1324 struct data_range *tmp;
1325
1326 FOR_EACH_PTR(filter, tmp) {
1327 rl = remove_range(rl, tmp->min, tmp->max);
1328 } END_FOR_EACH_PTR(tmp);
1329
1330 return rl;
1331 }
1332
1333 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1334 {
1335 struct range_list *one_orig;
1336 struct range_list *two_orig;
1337 struct range_list *ret;
1338 struct symbol *ret_type;
1339 struct symbol *small_type;
1340 struct symbol *large_type;
1341
1342 if (!two)
1343 return NULL;
1344 if (!one)
1345 return NULL;
1346
1347 one_orig = one;
1348 two_orig = two;
1349
1350 ret_type = rl_type(one);
1351 small_type = rl_type(one);
1352 large_type = rl_type(two);
1353
1354 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1355 small_type = rl_type(two);
1356 large_type = rl_type(one);
1357 }
1358
1359 one = cast_rl(large_type, one);
1360 two = cast_rl(large_type, two);
1361
1362 ret = one;
1363 one = rl_invert(one);
1364 two = rl_invert(two);
1365
1366 ret = rl_filter(ret, one);
1367 ret = rl_filter(ret, two);
1368
1369 one = cast_rl(small_type, one_orig);
1370 two = cast_rl(small_type, two_orig);
1371
1372 one = rl_invert(one);
1373 two = rl_invert(two);
1374
1375 ret = cast_rl(small_type, ret);
1376 ret = rl_filter(ret, one);
1377 ret = rl_filter(ret, two);
1378
1379 return cast_rl(ret_type, ret);
1380 }
1381
1382 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1383 {
1384 sval_t zero;
1385 sval_t max;
1386
1387 max = rl_max(right);
1388 if (sval_is_max(max))
1389 return left;
1390 if (max.value == 0)
1391 return NULL;
1392 max.value--;
1393 if (sval_is_negative(max))
1394 return NULL;
1395 if (sval_cmp(rl_max(left), max) < 0)
1396 return left;
1397 zero = max;
1398 zero.value = 0;
1399 return alloc_rl(zero, max);
1400 }
1401
1402 static struct range_list *get_neg_rl(struct range_list *rl)
1403 {
1404 struct data_range *tmp;
1405 struct data_range *new;
1406 struct range_list *ret = NULL;
1407
1408 if (!rl)
1409 return NULL;
1410 if (sval_is_positive(rl_min(rl)))
1411 return NULL;
1412
1413 FOR_EACH_PTR(rl, tmp) {
1414 if (sval_is_positive(tmp->min))
1415 return ret;
1416 if (sval_is_positive(tmp->max)) {
1417 new = alloc_range(tmp->min, tmp->max);
1418 new->max.value = -1;
1419 add_range(&ret, new->min, new->max);
1420 return ret;
1421 }
1422 add_range(&ret, tmp->min, tmp->max);
1423 } END_FOR_EACH_PTR(tmp);
1424
1425 return ret;
1426 }
1427
1428 static struct range_list *get_pos_rl(struct range_list *rl)
1429 {
1430 struct data_range *tmp;
1431 struct data_range *new;
1432 struct range_list *ret = NULL;
1433
1434 if (!rl)
1435 return NULL;
1436 if (sval_is_negative(rl_max(rl)))
1437 return NULL;
1438
1439 FOR_EACH_PTR(rl, tmp) {
1440 if (sval_is_negative(tmp->max))
1441 continue;
1442 if (sval_is_positive(tmp->min)) {
1443 add_range(&ret, tmp->min, tmp->max);
1444 continue;
1445 }
1446 new = alloc_range(tmp->min, tmp->max);
1447 new->min.value = 0;
1448 add_range(&ret, new->min, new->max);
1449 } END_FOR_EACH_PTR(tmp);
1450
1451 return ret;
1452 }
1453
1454 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1455 {
1456 sval_t right_min, right_max;
1457 sval_t min, max;
1458
1459 if (!left || !right)
1460 return NULL;
1461
1462 /* let's assume we never divide by zero */
1463 right_min = rl_min(right);
1464 right_max = rl_max(right);
1465 if (right_min.value == 0 && right_max.value == 0)
1466 return NULL;
1467 if (right_min.value == 0)
1468 right_min.value = 1;
1469 if (right_max.value == 0)
1470 right_max.value = -1;
1471
1472 max = sval_binop(rl_max(left), '/', right_min);
1473 min = sval_binop(rl_min(left), '/', right_max);
1474
1475 return alloc_rl(min, max);
1476 }
1477
1478 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1479 {
1480 struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1481 struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1482 struct range_list *ret;
1483
1484 if (is_whole_rl(right))
1485 return NULL;
1486
1487 left_neg = get_neg_rl(left);
1488 left_pos = get_pos_rl(left);
1489 right_neg = get_neg_rl(right);
1490 right_pos = get_pos_rl(right);
1491
1492 neg_neg = divide_rl_helper(left_neg, right_neg);
1493 neg_pos = divide_rl_helper(left_neg, right_pos);
1494 pos_neg = divide_rl_helper(left_pos, right_neg);
1495 pos_pos = divide_rl_helper(left_pos, right_pos);
1496
1497 ret = rl_union(neg_neg, neg_pos);
1498 ret = rl_union(ret, pos_neg);
1499 return rl_union(ret, pos_pos);
1500 }
1501
1502 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1503 {
1504 sval_t min, max;
1505
1506 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1507 return NULL;
1508 min = sval_binop(rl_min(left), op, rl_min(right));
1509
1510 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1511 return NULL;
1512 max = sval_binop(rl_max(left), op, rl_max(right));
1513
1514 return alloc_rl(min, max);
1515 }
1516
1517 static struct range_list *handle_sub_rl(struct range_list *left_orig, struct range_list *right_orig)
1518 {
1519 struct range_list *left_rl, *right_rl;
1520 struct symbol *type;
1521 sval_t min, max;
1522 sval_t min_ll, max_ll, res_ll;
1523 sval_t tmp;
1524
1525 /* TODO: These things should totally be using dranges where possible */
1526
1527 if (!left_orig || !right_orig)
1528 return NULL;
1529
1530 type = &int_ctype;
1531 if (type_positive_bits(rl_type(left_orig)) > type_positive_bits(type))
1532 type = rl_type(left_orig);
1533 if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
1534 type = rl_type(right_orig);
1535
1536 left_rl = cast_rl(type, left_orig);
1537 right_rl = cast_rl(type, right_orig);
1538
1539 max = rl_max(left_rl);
1540 min = sval_type_min(type);
1541
1542 min_ll = rl_min(left_rl);
1543 min_ll.type = &llong_ctype;
1544 max_ll = rl_max(right_rl);
1545 max_ll.type = &llong_ctype;
1546 res_ll = min_ll;
1547 res_ll.value = min_ll.value - max_ll.value;
1548
1549 if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
1550 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
1551 if (sval_cmp(tmp, min) > 0)
1552 min = tmp;
1553 } else if (type_positive_bits(type) < 63 &&
1554 !sval_binop_overflows(min_ll, '-', max_ll) &&
1555 (min.value != 0 && sval_cmp(res_ll, min) >= 0)) {
1556 struct range_list *left_casted, *right_casted, *result;
1557
1558 left_casted = cast_rl(&llong_ctype, left_orig);
1559 right_casted = cast_rl(&llong_ctype, right_orig);
1560 result = handle_sub_rl(left_casted, right_casted);
1561 return cast_rl(type, result);
1562 }
1563
1564 if (!sval_is_max(rl_max(left_rl))) {
1565 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
1566 if (sval_cmp(tmp, max) < 0)
1567 max = tmp;
1568 }
1569
1570 if (sval_is_min(min) && sval_is_max(max))
1571 return NULL;
1572
1573 return alloc_rl(min, max);
1574 }
1575
1576 static unsigned long long rl_bits_always_set(struct range_list *rl)
1577 {
1578 return sval_fls_mask(rl_min(rl));
1579 }
1580
1581 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1582 {
1583 return sval_fls_mask(rl_max(rl));
1584 }
1585
1586 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1587 {
1588 unsigned long long left_min, left_max, right_min, right_max;
1589 sval_t min, max;
1590 sval_t sval;
1591
1592 if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1593 !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1594 return rl_binop(left, '+', right);
1595
1596 left_min = rl_bits_always_set(left);
1597 left_max = rl_bits_maybe_set(left);
1598 right_min = rl_bits_always_set(right);
1599 right_max = rl_bits_maybe_set(right);
1600
1601 min.type = max.type = &ullong_ctype;
1602 min.uvalue = left_min | right_min;
1603 max.uvalue = left_max | right_max;
1604
1605 return cast_rl(rl_type(left), alloc_rl(min, max));
1606 }
1607
1608 static struct range_list *handle_XOR_rl(struct range_list *left, struct range_list *right)
1609 {
1610 unsigned long long left_set, left_maybe;
1611 unsigned long long right_set, right_maybe;
1612 sval_t zero, max;
1613
1614 left_set = rl_bits_always_set(left);
1615 left_maybe = rl_bits_maybe_set(left);
1616
1617 right_set = rl_bits_always_set(right);
1618 right_maybe = rl_bits_maybe_set(right);
1619
1620 zero = max = rl_min(left);
1621 zero.uvalue = 0;
1622 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1623
1624 return cast_rl(rl_type(left), alloc_rl(zero, max));
1625 }
1626
1627 static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
1628 {
1629 unsigned long long left_set, left_maybe;
1630 unsigned long long right_set, right_maybe;
1631 sval_t zero, max;
1632
1633 return NULL;
1634
1635 left_set = rl_bits_always_set(left);
1636 left_maybe = rl_bits_maybe_set(left);
1637
1638 right_set = rl_bits_always_set(right);
1639 right_maybe = rl_bits_maybe_set(right);
1640
1641 zero = max = rl_min(left);
1642 zero.uvalue = 0;
1643 max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1644
1645 return cast_rl(rl_type(left), alloc_rl(zero, max));
1646 }
1647
1648 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1649 {
1650 struct symbol *cast_type;
1651 sval_t left_sval, right_sval;
1652 struct range_list *ret = NULL;
1653
1654 cast_type = rl_type(left);
1655 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1656 cast_type = rl_type(right);
1657 if (sval_type_max(cast_type).uvalue < INT_MAX)
1658 cast_type = &int_ctype;
1659
1660 left = cast_rl(cast_type, left);
1661 right = cast_rl(cast_type, right);
1662
1663 if (!left && !right)
1664 return NULL;
1665
1666 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
1667 sval_t val = sval_binop(left_sval, op, right_sval);
1668 return alloc_rl(val, val);
1669 }
1670
1671 switch (op) {
1672 case '%':
1673 ret = handle_mod_rl(left, right);
1674 break;
1675 case '/':
1676 ret = handle_divide_rl(left, right);
1677 break;
1678 case '*':
1679 case '+':
1680 ret = handle_add_mult_rl(left, op, right);
1681 break;
1682 case '|':
1683 ret = handle_OR_rl(left, right);
1684 break;
1685 case '^':
1686 ret = handle_XOR_rl(left, right);
1687 break;
1688 case '&':
1689 ret = handle_AND_rl(left, right);
1690 break;
1691 case '-':
1692 ret = handle_sub_rl(left, right);
1693 break;
1694 /* FIXME: Do the rest as well */
1695 case SPECIAL_RIGHTSHIFT:
1696 case SPECIAL_LEFTSHIFT:
1697 break;
1698 }
1699
1700 return ret;
1701 }
1702
1703 void free_rl(struct range_list **rlist)
1704 {
1705 __free_ptr_list((struct ptr_list **)rlist);
1706 }
1707
1708 static void free_single_dinfo(struct data_info *dinfo)
1709 {
1710 free_rl(&dinfo->value_ranges);
1711 }
1712
1713 static void free_dinfos(struct allocation_blob *blob)
1714 {
1715 unsigned int size = sizeof(struct data_info);
1716 unsigned int offset = 0;
1717
1718 while (offset < blob->offset) {
1719 free_single_dinfo((struct data_info *)(blob->data + offset));
1720 offset += size;
1721 }
1722 }
1723
1724 void free_data_info_allocs(void)
1725 {
1726 struct allocator_struct *desc = &data_info_allocator;
1727 struct allocation_blob *blob = desc->blobs;
1728
1729 desc->blobs = NULL;
1730 desc->allocations = 0;
1731 desc->total_bytes = 0;
1732 desc->useful_bytes = 0;
1733 desc->freelist = NULL;
1734 while (blob) {
1735 struct allocation_blob *next = blob->next;
1736 free_dinfos(blob);
1737 blob_free(blob, desc->chunking);
1738 blob = next;
1739 }
1740 clear_data_range_alloc();
1741 }
1742
1743 void split_comparison_rl(struct range_list *left_orig, int op, struct range_list *right_orig,
1744 struct range_list **left_true_rl, struct range_list **left_false_rl,
1745 struct range_list **right_true_rl, struct range_list **right_false_rl)
1746 {
1747 struct range_list *left_true, *left_false;
1748 struct range_list *right_true, *right_false;
1749 sval_t min, max;
1750
1751 min = sval_type_min(rl_type(left_orig));
1752 max = sval_type_max(rl_type(left_orig));
1753
1754 left_true = clone_rl(left_orig);
1755 left_false = clone_rl(left_orig);
1756 right_true = clone_rl(right_orig);
1757 right_false = clone_rl(right_orig);
1758
1759 switch (op) {
1760 case '<':
1761 case SPECIAL_UNSIGNED_LT:
1762 left_true = remove_range(left_orig, rl_max(right_orig), max);
1763 if (!sval_is_min(rl_min(right_orig))) {
1764 left_false = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
1765 }
1766
1767 right_true = remove_range(right_orig, min, rl_min(left_orig));
1768 if (!sval_is_max(rl_max(left_orig)))
1769 right_false = remove_range(right_orig, add_one(rl_max(left_orig)), max);
1770 break;
1771 case SPECIAL_UNSIGNED_LTE:
1772 case SPECIAL_LTE:
1773 if (!sval_is_max(rl_max(right_orig)))
1774 left_true = remove_range(left_orig, add_one(rl_max(right_orig)), max);
1775 left_false = remove_range(left_orig, min, rl_min(right_orig));
1776
1777 if (!sval_is_min(rl_min(left_orig)))
1778 right_true = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
1779 right_false = remove_range(right_orig, rl_max(left_orig), max);
1780
1781 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
1782 left_false = remove_range(left_false, rl_min(left_orig), rl_min(left_orig));
1783 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
1784 right_false = remove_range(right_false, rl_max(left_orig), rl_max(left_orig));
1785 break;
1786 case SPECIAL_EQUAL:
1787 if (!sval_is_max(rl_max(right_orig))) {
1788 left_true = remove_range(left_true, add_one(rl_max(right_orig)), max);
1789 }
1790 if (!sval_is_min(rl_min(right_orig))) {
1791 left_true = remove_range(left_true, min, sub_one(rl_min(right_orig)));
1792 }
1793 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
1794 left_false = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
1795
1796 if (!sval_is_max(rl_max(left_orig)))
1797 right_true = remove_range(right_true, add_one(rl_max(left_orig)), max);
1798 if (!sval_is_min(rl_min(left_orig)))
1799 right_true = remove_range(right_true, min, sub_one(rl_min(left_orig)));
1800 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
1801 right_false = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
1802 break;
1803 case SPECIAL_UNSIGNED_GTE:
1804 case SPECIAL_GTE:
1805 if (!sval_is_min(rl_min(right_orig)))
1806 left_true = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
1807 left_false = remove_range(left_orig, rl_max(right_orig), max);
1808
1809 if (!sval_is_max(rl_max(left_orig)))
1810 right_true = remove_range(right_orig, add_one(rl_max(left_orig)), max);
1811 right_false = remove_range(right_orig, min, rl_min(left_orig));
1812
1813 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
1814 right_false = remove_range(right_false, rl_min(left_orig), rl_min(left_orig));
1815 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
1816 left_false = remove_range(left_false, rl_max(left_orig), rl_max(left_orig));
1817 break;
1818 case '>':
1819 case SPECIAL_UNSIGNED_GT:
1820 left_true = remove_range(left_orig, min, rl_min(right_orig));
1821 if (!sval_is_max(rl_max(right_orig)))
1822 left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
1823
1824 right_true = remove_range(right_orig, rl_max(left_orig), max);
1825 if (!sval_is_min(rl_min(left_orig)))
1826 right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
1827 break;
1828 case SPECIAL_NOTEQUAL:
1829 if (!sval_is_max(rl_max(right_orig)))
1830 left_false = remove_range(left_false, add_one(rl_max(right_orig)), max);
1831 if (!sval_is_min(rl_min(right_orig)))
1832 left_false = remove_range(left_false, min, sub_one(rl_min(right_orig)));
1833 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
1834 left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
1835
1836 if (!sval_is_max(rl_max(left_orig)))
1837 right_false = remove_range(right_false, add_one(rl_max(left_orig)), max);
1838 if (!sval_is_min(rl_min(left_orig)))
1839 right_false = remove_range(right_false, min, sub_one(rl_min(left_orig)));
1840 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
1841 right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
1842 break;
1843 default:
1844 sm_msg("internal error: unhandled comparison %d", op);
1845 return;
1846 }
1847
1848 if (left_true_rl) {
1849 *left_true_rl = left_true;
1850 *left_false_rl = left_false;
1851 }
1852 if (right_true_rl) {
1853 *right_true_rl = right_true;
1854 *right_false_rl = right_false;
1855 }
1856 }
Static analysis for C