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