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