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