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