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