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 }