smatch_comparison.c

   1 /*
   2  * smatch/smatch_comparison.c
   3  *
   4  * Copyright (C) 2012 Oracle.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * The point here is to store the relationships between two variables.
  12  * Ie:  y > x.
  13  * To do that we create a state with the two variables in alphabetical order:
  14  * ->name = "x vs y" and the state would be "<".  On the false path the state
  15  * would be ">=".
  16  *
  17  * Part of the trick of it is that if x or y is modified then we need to reset
  18  * the state.  We need to keep a list of all the states which depend on x and
  19  * all the states which depend on y.  The link_id code handles this.
  20  *
  21  */
  22
  23 #include "smatch.h"
  24 #include "smatch_extra.h"
  25 #include "smatch_slist.h"
  26
  27 static int compare_id;
  28 static int link_id;
  29
  30 struct compare_data {
  31         const char *var1;
  32         struct var_sym_list *vsl1;
  33         int comparison;
  34         const char *var2;
  35         struct var_sym_list *vsl2;
  36 };
  37 ALLOCATOR(compare_data, "compare data");
  38
  39 int chunk_vsl_eq(const char *a, struct var_sym_list *a_vsl, const char *b, struct var_sym_list *b_vsl)
  40 {
  41         if (strcmp(a, b) == 0)
  42                 return 1;
  43         return 0;
  44 }
  45
  46 static struct symbol *first_sym(struct var_sym_list *vsl)
  47 {
  48         struct var_sym *vs;
  49
  50         if (!vsl)
  51                 return NULL;
  52         vs = first_ptr_list((struct ptr_list *)vsl);
  53         return vs->sym;
  54 }
  55
  56 static struct smatch_state *alloc_compare_state(
  57                 const char *var1, struct var_sym_list *vsl1,
  58                 int comparison,
  59                 const char *var2, struct var_sym_list *vsl2)
  60 {
  61         struct smatch_state *state;
  62         struct compare_data *data;
  63
  64         state = __alloc_smatch_state(0);
  65         state->name = alloc_sname(show_special(comparison));
  66         data = __alloc_compare_data(0);
  67         data->var1 = alloc_sname(var1);
  68         data->vsl1 = clone_var_sym_list(vsl1);
  69         data->comparison = comparison;
  70         data->var2 = alloc_sname(var2);
  71         data->vsl2 = clone_var_sym_list(vsl2);
  72         state->data = data;
  73         return state;
  74 }
  75
  76 static int state_to_comparison(struct smatch_state *state)
  77 {
  78         if (!state || !state->data)
  79                 return 0;
  80         return ((struct compare_data *)state->data)->comparison;
  81 }
  82
  83 /*
  84  * flip_op() reverses the op left and right.  So "x >= y" becomes "y <= x".
  85  */
  86 static int flip_op(int op)
  87 {
  88         switch (op) {
  89         case 0:
  90                 return 0;
  91         case '<':
  92                 return '>';
  93         case SPECIAL_UNSIGNED_LT:
  94                 return SPECIAL_UNSIGNED_GT;
  95         case SPECIAL_LTE:
  96                 return SPECIAL_GTE;
  97         case SPECIAL_UNSIGNED_LTE:
  98                 return SPECIAL_UNSIGNED_GTE;
  99         case SPECIAL_EQUAL:
 100                 return SPECIAL_EQUAL;
 101         case SPECIAL_NOTEQUAL:
 102                 return SPECIAL_NOTEQUAL;
 103         case SPECIAL_GTE:
 104                 return SPECIAL_LTE;
 105         case SPECIAL_UNSIGNED_GTE:
 106                 return SPECIAL_UNSIGNED_LTE;
 107         case '>':
 108                 return '<';
 109         case SPECIAL_UNSIGNED_GT:
 110                 return SPECIAL_UNSIGNED_LT;
 111         default:
 112                 sm_msg("internal smatch bug.  unhandled comparison %d", op);
 113                 return op;
 114         }
 115 }
 116
 117 static int falsify_op(int op)
 118 {
 119         switch (op) {
 120         case 0:
 121                 return 0;
 122         case '<':
 123                 return SPECIAL_GTE;
 124         case SPECIAL_UNSIGNED_LT:
 125                 return SPECIAL_UNSIGNED_GTE;
 126         case SPECIAL_LTE:
 127                 return '>';
 128         case SPECIAL_UNSIGNED_LTE:
 129                 return SPECIAL_UNSIGNED_GT;
 130         case SPECIAL_EQUAL:
 131                 return SPECIAL_NOTEQUAL;
 132         case SPECIAL_NOTEQUAL:
 133                 return SPECIAL_EQUAL;
 134         case SPECIAL_GTE:
 135                 return '<';
 136         case SPECIAL_UNSIGNED_GTE:
 137                 return SPECIAL_UNSIGNED_LT;
 138         case '>':
 139                 return SPECIAL_LTE;
 140         case SPECIAL_UNSIGNED_GT:
 141                 return SPECIAL_UNSIGNED_LTE;
 142         default:
 143                 sm_msg("internal smatch bug.  unhandled comparison %d", op);
 144                 return op;
 145         }
 146 }
 147
 148 static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl)
 149 {
 150         sval_t left_min, left_max, right_min, right_max;
 151
 152         if (!left_rl || !right_rl)
 153                 return 0;
 154
 155         left_min = rl_min(left_rl);
 156         left_max = rl_max(left_rl);
 157         right_min = rl_min(right_rl);
 158         right_max = rl_max(right_rl);
 159
 160         if (left_min.value == left_max.value &&
 161             right_min.value == right_max.value &&
 162             left_min.value == right_min.value)
 163                 return SPECIAL_EQUAL;
 164
 165         if (sval_cmp(left_max, right_min) < 0)
 166                 return '<';
 167         if (sval_cmp(left_max, right_min) == 0)
 168                 return SPECIAL_LTE;
 169         if (sval_cmp(left_min, right_max) > 0)
 170                 return '>';
 171         if (sval_cmp(left_min, right_max) == 0)
 172                 return SPECIAL_GTE;
 173
 174         return 0;
 175 }
 176
 177 static struct range_list *get_orig_rl(struct var_sym_list *vsl)
 178 {
 179         struct symbol *sym;
 180         struct smatch_state *state;
 181
 182         if (!vsl)
 183                 return NULL;
 184         sym = first_sym(vsl);
 185         if (!sym || !sym->ident)
 186                 return NULL;
 187         state = get_orig_estate(sym->ident->name, sym);
 188         return estate_rl(state);
 189 }
 190
 191 static struct smatch_state *unmatched_comparison(struct sm_state *sm)
 192 {
 193         struct compare_data *data = sm->state->data;
 194         struct range_list *left_rl, *right_rl;
 195         int op;
 196
 197         if (!data)
 198                 return &undefined;
 199
 200         if (strstr(data->var1, " orig"))
 201                 left_rl = get_orig_rl(data->vsl1);
 202         else if (!get_implied_rl_var_sym(data->var1, first_sym(data->vsl1), &left_rl))
 203                 return &undefined;
 204         if (strstr(data->var2, " orig"))
 205                 right_rl = get_orig_rl(data->vsl2);
 206         else if (!get_implied_rl_var_sym(data->var2, first_sym(data->vsl2), &right_rl))
 207                 return &undefined;
 208
 209
 210         op = rl_comparison(left_rl, right_rl);
 211         if (op)
 212                 return alloc_compare_state(data->var1, data->vsl1, op, data->var2, data->vsl2);
 213
 214         return &undefined;
 215 }
 216
 217 /* remove_unsigned_from_comparison() is obviously a hack. */
 218 static int remove_unsigned_from_comparison(int op)
 219 {
 220         switch (op) {
 221         case SPECIAL_UNSIGNED_LT:
 222                 return '<';
 223         case SPECIAL_UNSIGNED_LTE:
 224                 return SPECIAL_LTE;
 225         case SPECIAL_UNSIGNED_GTE:
 226                 return SPECIAL_GTE;
 227         case SPECIAL_UNSIGNED_GT:
 228                 return '>';
 229         default:
 230                 return op;
 231         }
 232 }
 233
 234 /*
 235  * This is for when you merge states "a < b" and "a == b", the result is that
 236  * we can say for sure, "a <= b" after the merge.
 237  */
 238 static int merge_comparisons(int one, int two)
 239 {
 240         int LT, EQ, GT;
 241
 242         one = remove_unsigned_from_comparison(one);
 243         two = remove_unsigned_from_comparison(two);
 244
 245         LT = EQ = GT = 0;
 246
 247         switch (one) {
 248         case '<':
 249                 LT = 1;
 250                 break;
 251         case SPECIAL_LTE:
 252                 LT = 1;
 253                 EQ = 1;
 254                 break;
 255         case SPECIAL_EQUAL:
 256                 EQ = 1;
 257                 break;
 258         case SPECIAL_GTE:
 259                 GT = 1;
 260                 EQ = 1;
 261                 break;
 262         case '>':
 263                 GT = 1;
 264         }
 265
 266         switch (two) {
 267         case '<':
 268                 LT = 1;
 269                 break;
 270         case SPECIAL_LTE:
 271                 LT = 1;
 272                 EQ = 1;
 273                 break;
 274         case SPECIAL_EQUAL:
 275                 EQ = 1;
 276                 break;
 277         case SPECIAL_GTE:
 278                 GT = 1;
 279                 EQ = 1;
 280                 break;
 281         case '>':
 282                 GT = 1;
 283         }
 284
 285         if (LT && EQ && GT)
 286                 return 0;
 287         if (LT && EQ)
 288                 return SPECIAL_LTE;
 289         if (LT && GT)
 290                 return SPECIAL_NOTEQUAL;
 291         if (LT)
 292                 return '<';
 293         if (EQ && GT)
 294                 return SPECIAL_GTE;
 295         if (GT)
 296                 return '>';
 297         return 0;
 298 }
 299
 300 /*
 301  * This is for if you have "a < b" and "b <= c".  Or in other words,
 302  * "a < b <= c".  You would call this like get_combined_comparison('<', '<=').
 303  * The return comparison would be '<'.
 304  *
 305  * This function is different from merge_comparisons(), for example:
 306  * merge_comparison('<', '==') returns '<='
 307  * get_combined_comparison('<', '==') returns '<'
 308  */
 309 static int combine_comparisons(int left_compare, int right_compare)
 310 {
 311         int LT, EQ, GT;
 312
 313         left_compare = remove_unsigned_from_comparison(left_compare);
 314         right_compare = remove_unsigned_from_comparison(right_compare);
 315
 316         LT = EQ = GT = 0;
 317
 318         switch (left_compare) {
 319         case '<':
 320                 LT++;
 321                 break;
 322         case SPECIAL_LTE:
 323                 LT++;
 324                 EQ++;
 325                 break;
 326         case SPECIAL_EQUAL:
 327                 return right_compare;
 328         case SPECIAL_GTE:
 329                 GT++;
 330                 EQ++;
 331                 break;
 332         case '>':
 333                 GT++;
 334         }
 335
 336         switch (right_compare) {
 337         case '<':
 338                 LT++;
 339                 break;
 340         case SPECIAL_LTE:
 341                 LT++;
 342                 EQ++;
 343                 break;
 344         case SPECIAL_EQUAL:
 345                 return left_compare;
 346         case SPECIAL_GTE:
 347                 GT++;
 348                 EQ++;
 349                 break;
 350         case '>':
 351                 GT++;
 352         }
 353
 354         if (LT == 2) {
 355                 if (EQ == 2)
 356                         return SPECIAL_LTE;
 357                 return '<';
 358         }
 359
 360         if (GT == 2) {
 361                 if (EQ == 2)
 362                         return SPECIAL_GTE;
 363                 return '>';
 364         }
 365         return 0;
 366 }
 367
 368 static struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2)
 369 {
 370         struct compare_data *data = s1->data;
 371         int op;
 372
 373         op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2));
 374         if (op)
 375                 return alloc_compare_state(data->var1, data->vsl1, op, data->var2, data->vsl2);
 376         return &undefined;
 377 }
 378
 379 struct smatch_state *alloc_link_state(struct string_list *links)
 380 {
 381         struct smatch_state *state;
 382         static char buf[256];
 383         char *tmp;
 384         int i;
 385
 386         state = __alloc_smatch_state(0);
 387
 388         i = 0;
 389         FOR_EACH_PTR(links, tmp) {
 390                 if (!i++) {
 391                         snprintf(buf, sizeof(buf), "%s", tmp);
 392                 } else {
 393                         append(buf, ", ", sizeof(buf));
 394                         append(buf, tmp, sizeof(buf));
 395                 }
 396         } END_FOR_EACH_PTR(tmp);
 397
 398         state->name = alloc_sname(buf);
 399         state->data = links;
 400         return state;
 401 }
 402
 403 static void save_start_states(struct statement *stmt)
 404 {
 405         struct symbol *param;
 406         char orig[64];
 407         char state_name[128];
 408         struct smatch_state *state;
 409         struct string_list *links;
 410         char *link;
 411
 412         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
 413                 struct var_sym_list *vsl1 = NULL;
 414                 struct var_sym_list *vsl2 = NULL;
 415
 416                 if (!param->ident)
 417                         continue;
 418                 snprintf(orig, sizeof(orig), "%s orig", param->ident->name);
 419                 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig);
 420                 add_var_sym(&vsl1, param->ident->name, param);
 421                 add_var_sym(&vsl2, orig, param);
 422                 state = alloc_compare_state(param->ident->name, vsl1, SPECIAL_EQUAL, alloc_sname(orig), vsl2);
 423                 set_state(compare_id, state_name, NULL, state);
 424
 425                 link = alloc_sname(state_name);
 426                 links = NULL;
 427                 insert_string(&links, link);
 428                 state = alloc_link_state(links);
 429                 set_state(link_id, param->ident->name, param, state);
 430         } END_FOR_EACH_PTR(param);
 431 }
 432
 433 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
 434 {
 435         struct smatch_state *ret;
 436         struct string_list *links;
 437
 438         links = combine_string_lists(s1->data, s2->data);
 439         ret = alloc_link_state(links);
 440         return ret;
 441 }
 442
 443 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
 444 {
 445         struct smatch_state *old_state, *new_state;
 446         struct string_list *links;
 447         char *new;
 448
 449         old_state = get_state(link_id, var, sym);
 450         if (old_state)
 451                 links = clone_str_list(old_state->data);
 452         else
 453                 links = NULL;
 454
 455         new = alloc_sname(link);
 456         insert_string(&links, new);
 457
 458         new_state = alloc_link_state(links);
 459         set_state(link_id, var, sym, new_state);
 460 }
 461
 462 static void match_inc(struct sm_state *sm)
 463 {
 464         struct string_list *links;
 465         struct smatch_state *state;
 466         char *tmp;
 467
 468         links = sm->state->data;
 469
 470         FOR_EACH_PTR(links, tmp) {
 471                 state = get_state(compare_id, tmp, NULL);
 472
 473                 switch (state_to_comparison(state)) {
 474                 case SPECIAL_EQUAL:
 475                 case SPECIAL_GTE:
 476                 case SPECIAL_UNSIGNED_GTE:
 477                 case '>':
 478                 case SPECIAL_UNSIGNED_GT: {
 479                         struct compare_data *data = state->data;
 480                         struct smatch_state *new;
 481
 482                         new = alloc_compare_state(data->var1, data->vsl1, '>', data->var2, data->vsl2);
 483                         set_state(compare_id, tmp, NULL, new);
 484                         break;
 485                         }
 486                 default:
 487                         set_state(compare_id, tmp, NULL, &undefined);
 488                 }
 489         } END_FOR_EACH_PTR(tmp);
 490 }
 491
 492 static void match_dec(struct sm_state *sm)
 493 {
 494         struct string_list *links;
 495         struct smatch_state *state;
 496         char *tmp;
 497
 498         links = sm->state->data;
 499
 500         FOR_EACH_PTR(links, tmp) {
 501                 state = get_state(compare_id, tmp, NULL);
 502
 503                 switch (state_to_comparison(state)) {
 504                 case SPECIAL_EQUAL:
 505                 case SPECIAL_LTE:
 506                 case SPECIAL_UNSIGNED_LTE:
 507                 case '<':
 508                 case SPECIAL_UNSIGNED_LT: {
 509                         struct compare_data *data = state->data;
 510                         struct smatch_state *new;
 511
 512                         new = alloc_compare_state(data->var1, data->vsl1, '<', data->var2, data->vsl2);
 513                         set_state(compare_id, tmp, NULL, new);
 514                         break;
 515                         }
 516                 default:
 517                         set_state(compare_id, tmp, NULL, &undefined);
 518                 }
 519         } END_FOR_EACH_PTR(tmp);
 520 }
 521
 522 static int match_inc_dec(struct sm_state *sm, struct expression *mod_expr)
 523 {
 524         if (!mod_expr)
 525                 return 0;
 526         if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP)
 527                 return 0;
 528
 529         if (mod_expr->op == SPECIAL_INCREMENT) {
 530                 match_inc(sm);
 531                 return 1;
 532         }
 533         if (mod_expr->op == SPECIAL_DECREMENT) {
 534                 match_dec(sm);
 535                 return 1;
 536         }
 537         return 0;
 538 }
 539
 540 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
 541 {
 542         struct string_list *links;
 543         char *tmp;
 544
 545         if (match_inc_dec(sm, mod_expr))
 546                 return;
 547
 548         links = sm->state->data;
 549
 550         FOR_EACH_PTR(links, tmp) {
 551                 set_state(compare_id, tmp, NULL, &undefined);
 552         } END_FOR_EACH_PTR(tmp);
 553         set_state(link_id, sm->name, sm->sym, &undefined);
 554 }
 555
 556 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym)
 557 {
 558         char *name, *left_name, *right_name;
 559         struct symbol *tmp;
 560         char buf[128];
 561
 562         expr = strip_expr(expr);
 563         if (!expr)
 564                 return NULL;
 565         if (sym)
 566                 *sym = NULL;
 567
 568         name = expr_to_var_sym(expr, &tmp);
 569         if (name && tmp) {
 570                 if (sym)
 571                         *sym = tmp;
 572                 return name;
 573         }
 574         if (name)
 575                 free_string(name);
 576
 577         if (expr->type != EXPR_BINOP)
 578                 return NULL;
 579         if (expr->op != '-' && expr->op != '+')
 580                 return NULL;
 581
 582         left_name = expr_to_var(expr->left);
 583         if (!left_name)
 584                 return NULL;
 585         right_name = expr_to_var(expr->right);
 586         if (!right_name) {
 587                 free_string(left_name);
 588                 return NULL;
 589         }
 590         snprintf(buf, sizeof(buf), "%s %s %s", left_name, show_special(expr->op), right_name);
 591         free_string(left_name);
 592         free_string(right_name);
 593         return alloc_string(buf);
 594 }
 595
 596 static char *chunk_to_var(struct expression *expr)
 597 {
 598         return chunk_to_var_sym(expr, NULL);
 599 }
 600
 601 static void save_link(struct expression *expr, char *link)
 602 {
 603         char *var;
 604         struct symbol *sym;
 605
 606         expr = strip_expr(expr);
 607         if (expr->type == EXPR_BINOP) {
 608                 save_link(expr->left, link);
 609                 save_link(expr->right, link);
 610                 return;
 611         }
 612
 613         var = expr_to_var_sym(expr, &sym);
 614         if (!var || !sym)
 615                 goto done;
 616
 617         save_link_var_sym(var, sym, link);
 618 done:
 619         free_string(var);
 620 }
 621
 622 static void update_tf_links(struct state_list *pre_slist,
 623                             const char *left_var, struct var_sym_list *left_vsl,
 624                             int left_comparison,
 625                             const char *mid_var, struct var_sym_list *mid_vsl,
 626                             struct string_list *links)
 627 {
 628         struct smatch_state *state;
 629         struct smatch_state *true_state, *false_state;
 630         struct compare_data *data;
 631         const char *right_var;
 632         struct var_sym_list *right_vsl;
 633         int right_comparison;
 634         int true_comparison;
 635         int false_comparison;
 636         char *tmp;
 637         char state_name[256];
 638         struct var_sym *vs;
 639
 640         FOR_EACH_PTR(links, tmp) {
 641                 state = get_state_slist(pre_slist, compare_id, tmp, NULL);
 642                 if (!state || !state->data)
 643                         continue;
 644                 data = state->data;
 645                 right_comparison = data->comparison;
 646                 right_var = data->var2;
 647                 right_vsl = data->vsl2;
 648                 if (chunk_vsl_eq(mid_var, mid_vsl, right_var, right_vsl)) {
 649                         right_var = data->var1;
 650                         right_vsl = data->vsl1;
 651                         right_comparison = flip_op(right_comparison);
 652                 }
 653                 true_comparison = combine_comparisons(left_comparison, right_comparison);
 654                 false_comparison = combine_comparisons(falsify_op(left_comparison), right_comparison);
 655
 656                 if (strcmp(left_var, right_var) > 0) {
 657                         const char *tmp_var = left_var;
 658                         struct var_sym_list *tmp_vsl = left_vsl;
 659
 660                         left_var = right_var;
 661                         left_vsl = right_vsl;
 662                         right_var = tmp_var;
 663                         right_vsl = tmp_vsl;
 664                         true_comparison = flip_op(true_comparison);
 665                         false_comparison = flip_op(false_comparison);
 666                 }
 667
 668                 if (!true_comparison && !false_comparison)
 669                         continue;
 670
 671                 if (true_comparison)
 672                         true_state = alloc_compare_state(left_var, left_vsl, true_comparison, right_var, right_vsl);
 673                 else
 674                         true_state = NULL;
 675                 if (false_comparison)
 676                         false_state = alloc_compare_state(left_var, left_vsl, false_comparison, right_var, right_vsl);
 677                 else
 678                         false_state = NULL;
 679
 680                 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var);
 681                 set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
 682                 FOR_EACH_PTR(left_vsl, vs) {
 683                         save_link_var_sym(vs->var, vs->sym, state_name);
 684                 } END_FOR_EACH_PTR(vs);
 685                 FOR_EACH_PTR(right_vsl, vs) {
 686                         save_link_var_sym(vs->var, vs->sym, state_name);
 687                 } END_FOR_EACH_PTR(vs);
 688
 689         } END_FOR_EACH_PTR(tmp);
 690 }
 691
 692 static void update_tf_data(struct state_list *pre_slist,
 693                 const char *left_name, struct symbol *left_sym,
 694                 const char *right_name, struct symbol *right_sym,
 695                 struct compare_data *tdata)
 696 {
 697         struct smatch_state *state;
 698
 699         state = get_state_slist(pre_slist, link_id, tdata->var2, first_sym(tdata->vsl2));
 700         if (state)
 701                 update_tf_links(pre_slist, tdata->var1, tdata->vsl1, tdata->comparison, tdata->var2, tdata->vsl2, state->data);
 702
 703         state = get_state_slist(pre_slist, link_id, tdata->var1, first_sym(tdata->vsl1));
 704         if (state)
 705                 update_tf_links(pre_slist, tdata->var2, tdata->vsl2, flip_op(tdata->comparison), tdata->var1, tdata->vsl1, state->data);
 706 }
 707
 708 static void match_compare(struct expression *expr)
 709 {
 710         char *left = NULL;
 711         char *right = NULL;
 712         struct symbol *left_sym, *right_sym;
 713         struct var_sym_list *left_vsl, *right_vsl;
 714         int op, false_op;
 715         struct smatch_state *true_state, *false_state;
 716         char state_name[256];
 717         struct state_list *pre_slist;
 718
 719         if (expr->type != EXPR_COMPARE)
 720                 return;
 721         left = chunk_to_var_sym(expr->left, &left_sym);
 722         if (!left)
 723                 goto free;
 724         left_vsl = expr_to_vsl(expr->left);
 725         right = chunk_to_var_sym(expr->right, &right_sym);
 726         if (!right)
 727                 goto free;
 728         right_vsl = expr_to_vsl(expr->right);
 729
 730         if (strcmp(left, right) > 0) {
 731                 struct symbol *tmp_sym = left_sym;
 732                 char *tmp_name = left;
 733                 struct var_sym_list *tmp_vsl = left_vsl;
 734
 735                 left = right;
 736                 left_sym = right_sym;
 737                 left_vsl = right_vsl;
 738                 right = tmp_name;
 739                 right_sym = tmp_sym;
 740                 right_vsl = tmp_vsl;
 741                 op = flip_op(expr->op);
 742         } else {
 743                 op = expr->op;
 744         }
 745         false_op = falsify_op(op);
 746         snprintf(state_name, sizeof(state_name), "%s vs %s", left, right);
 747         true_state = alloc_compare_state(left, left_vsl, op, right, right_vsl);
 748         false_state = alloc_compare_state(left, left_vsl, false_op, right, right_vsl);
 749
 750         pre_slist = clone_slist(__get_cur_slist());
 751         update_tf_data(pre_slist, left, left_sym, right, right_sym, true_state->data);
 752         free_slist(&pre_slist);
 753
 754         set_true_false_states(compare_id, state_name, NULL, true_state, false_state);
 755         save_link(expr->left, state_name);
 756         save_link(expr->right, state_name);
 757 free:
 758         free_string(left);
 759         free_string(right);
 760 }
 761
 762 static void add_comparison_var_sym(const char *left_name,
 763                 struct var_sym_list *left_vsl,
 764                 int comparison,
 765                 const char *right_name, struct var_sym_list *right_vsl)
 766 {
 767         struct smatch_state *state;
 768         struct var_sym *vs;
 769         char state_name[256];
 770
 771         if (strcmp(left_name, right_name) > 0) {
 772                 const char *tmp_name = left_name;
 773                 struct var_sym_list *tmp_vsl = left_vsl;
 774
 775                 left_name = right_name;
 776                 left_vsl = right_vsl;
 777                 right_name = tmp_name;
 778                 right_vsl = tmp_vsl;
 779                 comparison = flip_op(comparison);
 780         }
 781         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
 782         state = alloc_compare_state(left_name, left_vsl, comparison, right_name, right_vsl);
 783
 784         set_state(compare_id, state_name, NULL, state);
 785
 786         FOR_EACH_PTR(left_vsl, vs) {
 787                 save_link_var_sym(vs->var, vs->sym, state_name);
 788         } END_FOR_EACH_PTR(vs);
 789         FOR_EACH_PTR(right_vsl, vs) {
 790                 save_link_var_sym(vs->var, vs->sym, state_name);
 791         } END_FOR_EACH_PTR(vs);
 792 }
 793
 794 static void add_comparison(struct expression *left, int comparison, struct expression *right)
 795 {
 796         char *left_name = NULL;
 797         char *right_name = NULL;
 798         struct symbol *left_sym, *right_sym;
 799         struct var_sym_list *left_vsl, *right_vsl;
 800         struct smatch_state *state;
 801         char state_name[256];
 802
 803         left_name = chunk_to_var_sym(left, &left_sym);
 804         if (!left_name)
 805                 goto free;
 806         left_vsl = expr_to_vsl(left);
 807         right_name = chunk_to_var_sym(right, &right_sym);
 808         if (!right_name)
 809                 goto free;
 810         right_vsl = expr_to_vsl(right);
 811
 812         if (strcmp(left_name, right_name) > 0) {
 813                 struct symbol *tmp_sym = left_sym;
 814                 char *tmp_name = left_name;
 815                 struct var_sym_list *tmp_vsl = left_vsl;
 816
 817                 left_name = right_name;
 818                 left_sym = right_sym;
 819                 left_vsl = right_vsl;
 820                 right_name = tmp_name;
 821                 right_sym = tmp_sym;
 822                 right_vsl = tmp_vsl;
 823                 comparison = flip_op(comparison);
 824         }
 825         snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name);
 826         state = alloc_compare_state(left_name, left_vsl, comparison, right_name, right_vsl);
 827
 828         set_state(compare_id, state_name, NULL, state);
 829         save_link(left, state_name);
 830         save_link(right, state_name);
 831
 832 free:
 833         free_string(left_name);
 834         free_string(right_name);
 835 }
 836
 837 static void match_assign_add(struct expression *expr)
 838 {
 839         struct expression *right;
 840         struct expression *r_left, *r_right;
 841         sval_t left_tmp, right_tmp;
 842
 843         right = strip_expr(expr->right);
 844         r_left = strip_expr(right->left);
 845         r_right = strip_expr(right->right);
 846
 847         get_absolute_min(r_left, &left_tmp);
 848         get_absolute_min(r_right, &right_tmp);
 849
 850         if (left_tmp.value > 0)
 851                 add_comparison(expr->left, '>', r_right);
 852         else if (left_tmp.value == 0)
 853                 add_comparison(expr->left, SPECIAL_GTE, r_right);
 854
 855         if (right_tmp.value > 0)
 856                 add_comparison(expr->left, '>', r_left);
 857         else if (right_tmp.value == 0)
 858                 add_comparison(expr->left, SPECIAL_GTE, r_left);
 859 }
 860
 861 static void match_assign_sub(struct expression *expr)
 862 {
 863         struct expression *right;
 864         struct expression *r_left, *r_right;
 865         int comparison;
 866         sval_t min;
 867
 868         right = strip_expr(expr->right);
 869         r_left = strip_expr(right->left);
 870         r_right = strip_expr(right->right);
 871
 872         if (get_absolute_min(r_right, &min) && sval_is_negative(min))
 873                 return;
 874
 875         comparison = get_comparison(r_left, r_right);
 876
 877         switch (comparison) {
 878         case '>':
 879         case SPECIAL_GTE:
 880                 if (implied_not_equal(r_right, 0))
 881                         add_comparison(expr->left, '>', r_left);
 882                 else
 883                         add_comparison(expr->left, SPECIAL_GTE, r_left);
 884                 return;
 885         }
 886 }
 887
 888 static void match_assign_divide(struct expression *expr)
 889 {
 890         struct expression *right;
 891         struct expression *r_left, *r_right;
 892         sval_t min;
 893
 894         right = strip_expr(expr->right);
 895         r_left = strip_expr(right->left);
 896         r_right = strip_expr(right->right);
 897         if (!get_implied_min(r_right, &min) || min.value <= 1)
 898                 return;
 899
 900         add_comparison(expr->left, '<', r_left);
 901 }
 902
 903 static void match_binop_assign(struct expression *expr)
 904 {
 905         struct expression *right;
 906
 907         right = strip_expr(expr->right);
 908         if (right->op == '+')
 909                 match_assign_add(expr);
 910         if (right->op == '-')
 911                 match_assign_sub(expr);
 912         if (right->op == '/')
 913                 match_assign_divide(expr);
 914 }
 915
 916 static void copy_comparisons(struct expression *left, struct expression *right)
 917 {
 918         struct string_list *links;
 919         struct smatch_state *state;
 920         struct compare_data *data;
 921         struct symbol *left_sym, *right_sym;
 922         char *left_var = NULL;
 923         char *right_var = NULL;
 924         struct var_sym_list *left_vsl;
 925         const char *var;
 926         struct var_sym_list *vsl;
 927         int comparison;
 928         char *tmp;
 929
 930         left_var = chunk_to_var_sym(left, &left_sym);
 931         if (!left_var)
 932                 goto done;
 933         left_vsl = expr_to_vsl(left);
 934         right_var = chunk_to_var_sym(right, &right_sym);
 935         if (!right_var)
 936                 goto done;
 937
 938         state = get_state(link_id, right_var, right_sym);
 939         if (!state)
 940                 return;
 941         links = state->data;
 942
 943         FOR_EACH_PTR(links, tmp) {
 944                 state = get_state(compare_id, tmp, NULL);
 945                 if (!state || !state->data)
 946                         continue;
 947                 data = state->data;
 948                 comparison = data->comparison;
 949                 var = data->var2;
 950                 vsl = data->vsl2;
 951                 if (chunk_vsl_eq(var, vsl, right_var, NULL)) {
 952                         var = data->var1;
 953                         vsl = data->vsl1;
 954                         comparison = flip_op(comparison);
 955                 }
 956                 add_comparison_var_sym(left_var, left_vsl, comparison, var, vsl);
 957         } END_FOR_EACH_PTR(tmp);
 958
 959 done:
 960         free_string(right_var);
 961 }
 962
 963 static void match_assign(struct expression *expr)
 964 {
 965         struct expression *right;
 966
 967         if (expr->op != '=')
 968                 return;
 969
 970         copy_comparisons(expr->left, expr->right);
 971         add_comparison(expr->left, SPECIAL_EQUAL, expr->right);
 972
 973         right = strip_expr(expr->right);
 974         if (right->type == EXPR_BINOP)
 975                 match_binop_assign(expr);
 976 }
 977
 978 static int get_comparison_strings(char *one, char *two)
 979 {
 980         char buf[256];
 981         struct smatch_state *state;
 982         int invert = 0;
 983         int ret = 0;
 984
 985         if (strcmp(one, two) > 0) {
 986                 char *tmp = one;
 987
 988                 one = two;
 989                 two = tmp;
 990                 invert = 1;
 991         }
 992
 993         snprintf(buf, sizeof(buf), "%s vs %s", one, two);
 994         state = get_state(compare_id, buf, NULL);
 995         if (state)
 996                 ret = state_to_comparison(state);
 997
 998         if (invert)
 999                 ret = flip_op(ret);
1000
1001         return ret;
1002 }
1003
1004 int get_comparison(struct expression *a, struct expression *b)
1005 {
1006         char *one = NULL;
1007         char *two = NULL;
1008         int ret = 0;
1009
1010         one = chunk_to_var(a);
1011         if (!one)
1012                 goto free;
1013         two = chunk_to_var(b);
1014         if (!two)
1015                 goto free;
1016
1017         ret = get_comparison_strings(one, two);
1018 free:
1019         free_string(one);
1020         free_string(two);
1021         return ret;
1022 }
1023
1024 static void update_links_from_call(struct expression *left,
1025                                    int left_compare,
1026                                    struct expression *right)
1027 {
1028         struct string_list *links;
1029         struct smatch_state *state;
1030         struct compare_data *data;
1031         struct symbol *left_sym, *right_sym;
1032         char *left_var = NULL;
1033         char *right_var = NULL;
1034         struct var_sym_list *left_vsl;
1035         const char *var;
1036         struct var_sym_list *vsl;
1037         int comparison;
1038         char *tmp;
1039
1040         left_var = chunk_to_var_sym(left, &left_sym);
1041         if (!left_var)
1042                 goto done;
1043         left_vsl = expr_to_vsl(left);
1044         right_var = chunk_to_var_sym(right, &right_sym);
1045         if (!right_var)
1046                 goto done;
1047
1048         state = get_state(link_id, right_var, right_sym);
1049         if (!state)
1050                 return;
1051         links = state->data;
1052
1053         FOR_EACH_PTR(links, tmp) {
1054                 state = get_state(compare_id, tmp, NULL);
1055                 if (!state || !state->data)
1056                         continue;
1057                 data = state->data;
1058                 comparison = data->comparison;
1059                 var = data->var2;
1060                 vsl = data->vsl2;
1061                 if (chunk_vsl_eq(var, vsl, right_var, NULL)) {
1062                         var = data->var1;
1063                         vsl = data->vsl1;
1064                         comparison = flip_op(comparison);
1065                 }
1066                 comparison = combine_comparisons(left_compare, comparison);
1067                 if (!comparison)
1068                         continue;
1069                 add_comparison_var_sym(left_var, left_vsl, comparison, var, vsl);
1070         } END_FOR_EACH_PTR(tmp);
1071
1072 done:
1073         free_string(right_var);
1074 }
1075
1076 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range)
1077 {
1078         struct expression *arg;
1079         int comparison;
1080         const char *c = range;
1081
1082         if (!str_to_comparison_arg(c, call, &comparison, &arg))
1083                 return;
1084         update_links_from_call(expr, comparison, arg);
1085         add_comparison(expr, comparison, arg);
1086 }
1087
1088 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with)
1089 {
1090         struct symbol *param;
1091         char *var = NULL;
1092         char buf[256];
1093         char *ret_str = NULL;
1094         int compare;
1095         int i;
1096
1097         var = chunk_to_var(expr);
1098         if (!var)
1099                 goto free;
1100
1101         i = -1;
1102         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) {
1103                 i++;
1104                 if (!param->ident)
1105                         continue;
1106                 snprintf(buf, sizeof(buf), "%s orig", param->ident->name);
1107                 compare = get_comparison_strings(var, buf);
1108                 if (!compare)
1109                         continue;
1110                 if (show_special(compare)[0] != starts_with)
1111                         continue;
1112                 snprintf(buf, sizeof(buf), "[%sp%d]", show_special(compare), i);
1113                 ret_str = alloc_sname(buf);
1114                 break;
1115         } END_FOR_EACH_PTR(param);
1116
1117 free:
1118         free_string(var);
1119         return ret_str;
1120 }
1121
1122 char *expr_equal_to_param(struct expression *expr)
1123 {
1124         return range_comparison_to_param_helper(expr, '=');
1125 }
1126
1127 char *expr_lte_to_param(struct expression *expr)
1128 {
1129         return range_comparison_to_param_helper(expr, '<');
1130 }
1131
1132 static void free_data(struct symbol *sym)
1133 {
1134         if (__inline_fn)
1135                 return;
1136         clear_compare_data_alloc();
1137 }
1138
1139 void register_comparison(int id)
1140 {
1141         compare_id = id;
1142         add_hook(&match_compare, CONDITION_HOOK);
1143         add_hook(&match_assign, ASSIGNMENT_HOOK);
1144         add_hook(&save_start_states, AFTER_DEF_HOOK);
1145         add_unmatched_state_hook(compare_id, unmatched_comparison);
1146         add_merge_hook(compare_id, &merge_compare_states);
1147         add_hook(&free_data, AFTER_FUNC_HOOK);
1148 }
1149
1150 void register_comparison_links(int id)
1151 {
1152         link_id = id;
1153         add_merge_hook(link_id, &merge_links);
1154         add_modification_hook(link_id, &match_modify);
1155 }