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