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