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