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