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