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