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