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