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