smatch_extra.c

   1 /*
   2  * sparse/smatch_extra.c
   3  *
   4  * Copyright (C) 2008 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * smatch_extra.c is supposed to track the value of every variable.
  12  */
  13
  14 #include <stdlib.h>
  15 #ifndef __USE_ISOC99
  16 #define __USE_ISOC99
  17 #endif
  18 #include <limits.h>
  19 #include "parse.h"
  20 #include "smatch.h"
  21 #include "smatch_slist.h"
  22 #include "smatch_extra.h"
  23
  24 static int my_id;
  25
  26 static struct symbol *cur_func;
  27
  28 struct data_range whole_range = {
  29         .min = LLONG_MIN,
  30         .max = LLONG_MAX,
  31 };
  32
  33 static struct data_info *alloc_dinfo(void)
  34 {
  35         struct data_info *ret;
  36
  37         ret = __alloc_data_info(0);
  38         ret->equiv = NULL;
  39         ret->type = DATA_RANGE;
  40         ret->value_ranges = NULL;
  41         return ret;
  42 }
  43
  44 static struct data_info *alloc_dinfo_range(long long min, long long max)
  45 {
  46         struct data_info *ret;
  47
  48         ret = alloc_dinfo();
  49         add_range(&ret->value_ranges, min, max);
  50         return ret;
  51 }
  52
  53 static struct data_info *alloc_dinfo_range_list(struct range_list *rl)
  54 {
  55         struct data_info *ret;
  56
  57         ret = alloc_dinfo();
  58         ret->value_ranges = rl;
  59         return ret;
  60 }
  61
  62 static struct data_info *clone_dinfo(struct data_info *dinfo)
  63 {
  64         struct data_info *ret;
  65
  66         ret = alloc_dinfo();
  67         ret->equiv = clone_tracker_list(dinfo->equiv);
  68         ret->value_ranges = clone_range_list(dinfo->value_ranges);
  69         return ret;
  70 }
  71
  72 static struct smatch_state *clone_extra_state(struct smatch_state *state)
  73 {
  74         struct smatch_state *ret;
  75
  76         ret = __alloc_smatch_state(0);
  77         ret->name = state->name;
  78         ret->data = clone_dinfo(get_dinfo(state));
  79         return ret;
  80 }
  81
  82 static struct smatch_state *alloc_extra_state_empty(void)
  83 {
  84         struct smatch_state *state;
  85         struct data_info *dinfo;
  86
  87         dinfo = alloc_dinfo();
  88         state = __alloc_smatch_state(0);
  89         state->data = dinfo;
  90         state->name = "";
  91         return state;
  92 }
  93
  94 static struct smatch_state *alloc_extra_state_no_name(int val)
  95 {
  96         struct smatch_state *state;
  97
  98         state = __alloc_smatch_state(0);
  99         state->data = (void *)alloc_dinfo_range(val, val);
 100         return state;
 101 }
 102
 103 /* We do this because ->value_ranges is a list */
 104 struct smatch_state *extra_undefined(void)
 105 {
 106         struct data_info *dinfo;
 107         static struct smatch_state *ret;
 108         static struct symbol *prev_func;
 109
 110         if  (prev_func == cur_func)
 111                 return ret;
 112         prev_func = cur_func;
 113
 114         dinfo = alloc_dinfo_range(whole_range.min, whole_range.max);
 115         ret = __alloc_smatch_state(0);
 116         ret->name = "unknown";
 117         ret->data = dinfo;
 118         return ret;
 119 }
 120
 121 struct smatch_state *alloc_extra_state(long long val)
 122 {
 123         struct smatch_state *state;
 124
 125         state = alloc_extra_state_no_name(val);
 126         state->name = show_ranges(get_dinfo(state)->value_ranges);
 127         return state;
 128 }
 129
 130 struct smatch_state *alloc_extra_state_range(long long min, long long max)
 131 {
 132         struct smatch_state *state;
 133
 134         if (min == whole_range.min && max == whole_range.max)
 135                 return extra_undefined();
 136         state = __alloc_smatch_state(0);
 137         state->data = (void *)alloc_dinfo_range(min, max);
 138         state->name = show_ranges(get_dinfo(state)->value_ranges);
 139         return state;
 140 }
 141
 142 struct smatch_state *alloc_extra_state_range_list(struct range_list *rl)
 143 {
 144         struct smatch_state *state;
 145
 146         state = __alloc_smatch_state(0);
 147         state->data = (void *)alloc_dinfo_range_list(rl);
 148         state->name = show_ranges(get_dinfo(state)->value_ranges);
 149         return state;
 150 }
 151
 152 static void add_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 153 {
 154         struct data_info *dinfo;
 155
 156         dinfo = get_dinfo(state);
 157         add_tracker(&dinfo->equiv, SMATCH_EXTRA, name, sym);
 158 }
 159
 160 static void del_equiv(struct smatch_state *state, const char *name, struct symbol *sym)
 161 {
 162         struct data_info *dinfo;
 163
 164         dinfo = get_dinfo(state);
 165         del_tracker(&dinfo->equiv, SMATCH_EXTRA, name, sym);
 166 }
 167
 168 static void remove_from_equiv(const char *name, struct symbol *sym)
 169 {
 170         struct sm_state *orig_sm;
 171         struct tracker *tracker;
 172         struct smatch_state *state;
 173         struct tracker_list *to_update;
 174
 175         orig_sm = get_sm_state(SMATCH_EXTRA, name, sym);
 176         if (!orig_sm || !get_dinfo(orig_sm->state)->equiv)
 177                 return;
 178
 179         state = clone_extra_state(orig_sm->state);
 180         del_equiv(state, name, sym);
 181         to_update = get_dinfo(state)->equiv;
 182         if (ptr_list_size((struct ptr_list *)get_dinfo(state)->equiv) == 1)
 183                 get_dinfo(state)->equiv = NULL;
 184
 185         FOR_EACH_PTR(to_update, tracker) {
 186                 struct sm_state *new_sm;
 187
 188                 new_sm = clone_sm(orig_sm);
 189                 new_sm->name = tracker->name;
 190                 new_sm->sym = tracker->sym;
 191                 new_sm->state = state;
 192                 __set_sm(new_sm);
 193         } END_FOR_EACH_PTR(tracker);
 194 }
 195
 196 static void remove_from_equiv_expr(struct expression *expr)
 197 {
 198         char *name;
 199         struct symbol *sym;
 200
 201         name = get_variable_from_expr(expr, &sym);
 202         if (!name || !sym)
 203                 goto free;
 204         remove_from_equiv(name, sym);
 205 free:
 206         free_string(name);
 207 }
 208
 209 struct sm_state *set_extra_mod(const char *name, struct symbol *sym, struct smatch_state *state)
 210 {
 211         remove_from_equiv(name, sym);
 212         return set_state(SMATCH_EXTRA, name, sym, state);
 213 }
 214
 215 struct sm_state *set_extra_expr_mod(struct expression *expr, struct smatch_state *state)
 216 {
 217         remove_from_equiv_expr(expr);
 218         return set_state_expr(SMATCH_EXTRA, expr, state);
 219 }
 220
 221 void set_extra_true_false(const char *name, struct symbol *sym,
 222                         struct smatch_state *true_state,
 223                         struct smatch_state *false_state)
 224 {
 225         struct tracker *tracker;
 226         struct smatch_state *orig_state;
 227
 228         orig_state = get_state(SMATCH_EXTRA, name, sym);
 229
 230         if (!orig_state || !get_dinfo(orig_state)->equiv) {
 231                 set_true_false_states(SMATCH_EXTRA, name, sym, true_state, false_state);
 232                 return;
 233         }
 234
 235         FOR_EACH_PTR(get_dinfo(orig_state)->equiv, tracker) {
 236                 set_true_false_states(tracker->owner, tracker->name, tracker->sym,
 237                                 true_state, false_state);
 238                 if (true_state)
 239                         add_equiv(true_state, tracker->name, tracker->sym);
 240                 if (false_state)
 241                         add_equiv(false_state, tracker->name, tracker->sym);
 242         } END_FOR_EACH_PTR(tracker);
 243 }
 244
 245 struct data_info *get_dinfo(struct smatch_state *state)
 246 {
 247         if (!state)
 248                 return NULL;
 249         return (struct data_info *)state->data;
 250
 251 }
 252
 253 struct smatch_state *filter_range(struct smatch_state *orig,
 254                                  long long filter_min, long long filter_max)
 255 {
 256         struct smatch_state *ret;
 257         struct data_info *orig_info;
 258         struct data_info *ret_info;
 259
 260         if (!orig)
 261                 orig = extra_undefined();
 262         orig_info = get_dinfo(orig);
 263         ret = alloc_extra_state_empty();
 264         ret_info = get_dinfo(ret);
 265         ret_info->value_ranges = remove_range(orig_info->value_ranges, filter_min, filter_max);
 266         ret->name = show_ranges(ret_info->value_ranges);
 267         return ret;
 268 }
 269
 270 struct smatch_state *add_filter(struct smatch_state *orig, long long num)
 271 {
 272         return filter_range(orig, num, num);
 273 }
 274
 275 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
 276                                        struct smatch_state *s1,
 277                                        struct smatch_state *s2)
 278 {
 279         struct data_info *info1 = get_dinfo(s1);
 280         struct data_info *info2 = get_dinfo(s2);
 281         struct data_info *ret_info;
 282         struct smatch_state *tmp;
 283         struct range_list *value_ranges;
 284         struct tracker *tracker;
 285
 286         value_ranges = range_list_union(info1->value_ranges, info2->value_ranges);
 287         tmp = alloc_extra_state_empty();
 288         ret_info = get_dinfo(tmp);
 289         ret_info->value_ranges = value_ranges;
 290         tmp->name = show_ranges(ret_info->value_ranges);
 291         FOR_EACH_PTR(info1->equiv, tracker) {
 292                 if (in_tracker_list(info2->equiv, tracker->owner, tracker->name, tracker->sym))
 293                         add_equiv(tmp, tracker->name, tracker->sym);
 294         } END_FOR_EACH_PTR(tracker);
 295         return tmp;
 296 }
 297
 298 static struct sm_state *handle_canonical_while_count_down(struct statement *loop)
 299 {
 300         struct expression *iter_var;
 301         struct expression *condition;
 302         struct sm_state *sm;
 303         long long start;
 304
 305         condition = strip_expr(loop->iterator_pre_condition);
 306         if (!condition)
 307                 return NULL;
 308         if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
 309                 return NULL;
 310         if (condition->op != SPECIAL_DECREMENT)
 311                 return NULL;
 312
 313         iter_var = condition->unop;
 314         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 315         if (!sm)
 316                 return NULL;
 317         if (get_dinfo_min(get_dinfo(sm->state)) < 0)
 318                 return NULL;
 319         start = get_dinfo_max(get_dinfo(sm->state));
 320         if  (start <= 0)
 321                 return NULL;
 322         if (start != whole_range.max)
 323                 start--;
 324
 325         if (condition->type == EXPR_PREOP)
 326                 set_extra_expr_mod(iter_var, alloc_extra_state_range(1, start));
 327         if (condition->type == EXPR_POSTOP)
 328                 set_extra_expr_mod(iter_var, alloc_extra_state_range(0, start));
 329         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 330 }
 331
 332 static struct sm_state *handle_canonical_for_loops(struct statement *loop)
 333 {
 334         struct expression *iter_expr;
 335         struct expression *iter_var;
 336         struct expression *condition;
 337         struct sm_state *sm;
 338         long long start;
 339         long long end;
 340
 341         if (!loop->iterator_post_statement)
 342                 return NULL;
 343         if (loop->iterator_post_statement->type != STMT_EXPRESSION)
 344                 return NULL;
 345         iter_expr = loop->iterator_post_statement->expression;
 346         if (!loop->iterator_pre_condition)
 347                 return NULL;
 348         if (loop->iterator_pre_condition->type != EXPR_COMPARE)
 349                 return NULL;
 350         condition = loop->iterator_pre_condition;
 351
 352
 353         if (iter_expr->op != SPECIAL_INCREMENT)
 354                 return NULL;
 355         iter_var = iter_expr->unop;
 356         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 357         if (!sm)
 358                 return NULL;
 359         if (!get_single_value_from_dinfo(get_dinfo(sm->state), &start))
 360                 return NULL;
 361         if (!get_implied_value(condition->right, &end))
 362                 end = whole_range.max;
 363         if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
 364                 return NULL;
 365
 366         switch (condition->op) {
 367         case SPECIAL_NOTEQUAL:
 368         case '<':
 369                 if (end != whole_range.max)
 370                         end--;
 371                 break;
 372         case SPECIAL_LTE:
 373                 break;
 374         default:
 375                 return NULL;
 376         }
 377         if (end < start)
 378                 return NULL;
 379         set_extra_expr_mod(iter_var, alloc_extra_state_range(start, end));
 380         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 381 }
 382
 383 struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct state_list **slist)
 384 {
 385         struct sm_state *ret;
 386
 387         __push_fake_cur_slist();;
 388         if (!loop->iterator_post_statement)
 389                 ret = handle_canonical_while_count_down(loop);
 390         else
 391                 ret = handle_canonical_for_loops(loop);
 392         *slist = __pop_fake_cur_slist();
 393         return ret;
 394 }
 395
 396 int __iterator_unchanged(struct sm_state *sm)
 397 {
 398         if (!sm)
 399                 return 0;
 400         if (get_sm_state(my_id, sm->name, sm->sym) == sm)
 401                 return 1;
 402         return 0;
 403 }
 404
 405 static void while_count_down_after(struct sm_state *sm, struct expression *condition)
 406 {
 407         long long after_value;
 408
 409         /* paranoid checking.  prolly not needed */
 410         condition = strip_expr(condition);
 411         if (!condition)
 412                 return;
 413         if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
 414                 return;
 415         if (condition->op != SPECIAL_DECREMENT)
 416                 return;
 417         after_value = get_dinfo_min(get_dinfo(sm->state));
 418         after_value--;
 419         set_extra_mod(sm->name, sm->sym, alloc_extra_state(after_value));
 420 }
 421
 422 void __extra_pre_loop_hook_after(struct sm_state *sm,
 423                                 struct statement *iterator,
 424                                 struct expression *condition)
 425 {
 426         struct expression *iter_expr;
 427         char *name;
 428         struct symbol *sym;
 429         long long value;
 430         int left = 0;
 431         struct smatch_state *state;
 432         struct data_info *dinfo;
 433         long long min, max;
 434
 435         if (!iterator) {
 436                 while_count_down_after(sm, condition);
 437                 return;
 438         }
 439
 440         iter_expr = iterator->expression;
 441
 442         if (condition->type != EXPR_COMPARE)
 443                 return;
 444         if (!get_value(condition->left, &value)) {
 445                 if (!get_value(condition->right, &value))
 446                         return;
 447                 left = 1;
 448         }
 449         if (left)
 450                 name = get_variable_from_expr(condition->left, &sym);
 451         else
 452                 name = get_variable_from_expr(condition->right, &sym);
 453         if (!name || !sym)
 454                 goto free;
 455         if (sym != sm->sym || strcmp(name, sm->name))
 456                 goto free;
 457         state = get_state(my_id, name, sym);
 458         dinfo = get_dinfo(state);
 459         min = get_dinfo_min(dinfo);
 460         max = get_dinfo_max(dinfo);
 461         if (iter_expr->op == SPECIAL_INCREMENT && min != whole_range.min && max == whole_range.max) {
 462                 set_extra_mod(name, sym, alloc_extra_state(min));
 463         } else if (min == whole_range.min && max != whole_range.max) {
 464                 set_extra_mod(name, sym, alloc_extra_state(max));
 465         }
 466 free:
 467         free_string(name);
 468         return;
 469 }
 470
 471 static struct smatch_state *unmatched_state(struct sm_state *sm)
 472 {
 473         return extra_undefined();
 474 }
 475
 476 static void match_function_call(struct expression *expr)
 477 {
 478         struct expression *tmp;
 479         struct symbol *sym;
 480         char *name;
 481         int i = 0;
 482
 483         FOR_EACH_PTR(expr->args, tmp) {
 484                 if (tmp->type == EXPR_PREOP && tmp->op == '&') {
 485                         name = get_variable_from_expr(tmp->unop, &sym);
 486                         if (name) {
 487                                 set_extra_mod(name, sym, extra_undefined());
 488                         }
 489                         free_string(name);
 490                 }
 491                 i++;
 492         } END_FOR_EACH_PTR(tmp);
 493 }
 494
 495 static void set_equiv(struct sm_state *right_sm, struct expression *left)
 496 {
 497         struct smatch_state *state;
 498         struct data_info *dinfo;
 499         struct tracker *tracker;
 500         char *name;
 501         struct symbol *sym;
 502
 503         name = get_variable_from_expr(left, &sym);
 504         if (!name || !sym)
 505                 goto free;
 506
 507         state = clone_extra_state(right_sm->state);
 508
 509         dinfo = get_dinfo(state);
 510         if (!dinfo->equiv)
 511                 add_equiv(state, right_sm->name, right_sm->sym);
 512         add_equiv(state, name, sym);
 513
 514         FOR_EACH_PTR(dinfo->equiv, tracker) {
 515                 struct sm_state *new_sm;
 516
 517                 new_sm = clone_sm(right_sm);
 518                 new_sm->name = tracker->name;
 519                 new_sm->sym = tracker->sym;
 520                 new_sm->state = state;
 521                 __set_sm(new_sm);
 522         } END_FOR_EACH_PTR(tracker);
 523 free:
 524         free_string(name);
 525 }
 526
 527 static void match_assign(struct expression *expr)
 528 {
 529         struct expression *left;
 530         struct expression *right;
 531         struct sm_state *right_sm;
 532         struct symbol *sym;
 533         char *name;
 534         long long value;
 535         int known;
 536         long long min = whole_range.min;
 537         long long max = whole_range.max;
 538         long long tmp;
 539         struct range_list *rl = NULL;
 540
 541         left = strip_expr(expr->left);
 542         name = get_variable_from_expr(left, &sym);
 543         if (!name)
 544                 return;
 545         right = strip_expr(expr->right);
 546         while (right->type == EXPR_ASSIGNMENT && right->op == '=')
 547                 right = strip_expr(right->left);
 548
 549         right_sm = get_sm_state_expr(SMATCH_EXTRA, right);
 550         if (expr->op == '=' && right_sm) {
 551                 set_equiv(right_sm, left);
 552                 goto free;
 553         }
 554
 555         known = get_implied_range_list(right, &rl);
 556         if (expr->op == '=') {
 557                 if (known)
 558                         set_extra_mod(name, sym, alloc_extra_state_range_list(rl));
 559                 else
 560                         set_extra_mod(name, sym, extra_undefined());
 561                 goto free;
 562         }
 563
 564         known = get_implied_value(right, &value);
 565         if (expr->op == SPECIAL_ADD_ASSIGN) {
 566                 if (get_implied_min(left, &tmp)) {
 567                         if (known)
 568                                 min = tmp + value;
 569                         else
 570                                 min = tmp;
 571                 }
 572
 573         }
 574         if (expr->op == SPECIAL_SUB_ASSIGN) {
 575                 if (get_implied_max(left, &tmp)) {
 576                         if (known)
 577                                 max = tmp - value;
 578                         else
 579                                 max = tmp;
 580                 }
 581
 582         }
 583         set_extra_mod(name, sym, alloc_extra_state_range(min, max));
 584 free:
 585         free_string(name);
 586 }
 587
 588 static void unop_expr(struct expression *expr)
 589 {
 590         struct symbol *sym;
 591         char *name;
 592         long long min = whole_range.min;
 593         long long max = whole_range.max;
 594         long long val;
 595
 596         if (expr->op == '*')
 597                 return;
 598         if (expr->op == '(')
 599                 return;
 600         if (expr->op == '!')
 601                 return;
 602
 603         name = get_variable_from_expr(expr->unop, &sym);
 604         if (!name)
 605                 goto free;
 606         if (expr->op == SPECIAL_INCREMENT) {
 607                 if (get_implied_min(expr->unop, &val))
 608                         min = val + 1;
 609         }
 610         if (expr->op == SPECIAL_DECREMENT) {
 611                 if (get_implied_max(expr->unop, &val))
 612                         max = val - 1;
 613         }
 614         set_extra_mod(name, sym, alloc_extra_state_range(min, max));
 615 free:
 616         free_string(name);
 617 }
 618
 619 static void delete_state_tracker(struct tracker *t)
 620 {
 621         remove_from_equiv(t->name, t->sym);
 622         delete_state(t->owner, t->name, t->sym);
 623 }
 624
 625 static void scoped_state_extra(const char *name, struct symbol *sym)
 626 {
 627         struct tracker *t;
 628
 629         t = alloc_tracker(SMATCH_EXTRA, name, sym);
 630         add_scope_hook((scope_hook *)&delete_state_tracker, t);
 631 }
 632
 633 static void match_declarations(struct symbol *sym)
 634 {
 635         const char *name;
 636
 637         if (sym->ident) {
 638                 name = sym->ident->name;
 639                 if (!sym->initializer) {
 640                         set_state(SMATCH_EXTRA, name, sym, extra_undefined());
 641                         scoped_state_extra(name, sym);
 642                 }
 643         }
 644 }
 645
 646 static void match_function_def(struct symbol *sym)
 647 {
 648         struct symbol *arg;
 649
 650         cur_func = sym;
 651         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 652                 if (!arg->ident) {
 653                         continue;
 654                 }
 655                 set_state(my_id, arg->ident->name, arg, extra_undefined());
 656         } END_FOR_EACH_PTR(arg);
 657 }
 658
 659 static int last_stmt_val(struct statement *stmt, long long *val)
 660 {
 661         struct expression *expr;
 662
 663         if (!stmt)
 664                 return 0;
 665
 666         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 667         if (stmt->type != STMT_EXPRESSION)
 668                 return 0;
 669         expr = stmt->expression;
 670         return get_value(expr, val);
 671 }
 672
 673 static void match_comparison(struct expression *expr)
 674 {
 675         long long fixed;
 676         char *name = NULL;
 677         struct symbol *sym;
 678         struct smatch_state *true_state;
 679         struct smatch_state *false_state;
 680         struct smatch_state *orig;
 681         int left = 0;
 682         int comparison = expr->op;
 683         struct expression *varies = expr->right;
 684
 685         if (!get_value(expr->left, &fixed)) {
 686                 if (!get_value(expr->right, &fixed))
 687                         return;
 688                 varies = strip_expr(expr->left);
 689                 left = 1;
 690         }
 691         if (varies->op == SPECIAL_INCREMENT || varies->op == SPECIAL_DECREMENT)
 692                 varies = varies->unop;
 693         if (varies->type == EXPR_CALL) {
 694                 function_comparison(comparison, varies, fixed, left);
 695                 return;
 696         }
 697
 698         name = get_variable_from_expr(varies, &sym);
 699         if (!name || !sym)
 700                 goto free;
 701
 702         orig = get_state(my_id, name, sym);
 703         if (!orig)
 704                 orig = extra_undefined();
 705
 706         switch (comparison) {
 707         case '<':
 708         case SPECIAL_UNSIGNED_LT:
 709                 if (left) {
 710                         true_state = filter_range(orig, fixed, whole_range.max);
 711                         false_state = filter_range(orig, whole_range.min, fixed - 1);
 712                 } else {
 713                         true_state = filter_range(orig, whole_range.min, fixed);
 714                         false_state = filter_range(orig, fixed + 1, whole_range.max);
 715                 }
 716                 break;
 717         case SPECIAL_UNSIGNED_LTE:
 718         case SPECIAL_LTE:
 719                 if (left) {
 720                         true_state = filter_range(orig, fixed + 1, whole_range.max);
 721                         false_state = filter_range(orig, whole_range.min, fixed);
 722                 } else {
 723                         true_state = filter_range(orig, whole_range.min, fixed - 1);
 724                         false_state = filter_range(orig, fixed, whole_range.max);
 725                 }
 726                 break;
 727         case SPECIAL_EQUAL:
 728                 if (possibly_true(SPECIAL_EQUAL, get_dinfo(orig), fixed, fixed))
 729                         true_state = alloc_extra_state(fixed);
 730                 else
 731                         true_state = alloc_extra_state_empty();
 732                 false_state = filter_range(orig, fixed, fixed);
 733                 break;
 734         case SPECIAL_UNSIGNED_GTE:
 735         case SPECIAL_GTE:
 736                 if (left) {
 737                         true_state = filter_range(orig, whole_range.min, fixed - 1);
 738                         false_state = filter_range(orig, fixed, whole_range.max);
 739                 } else {
 740                         true_state = filter_range(orig, fixed + 1, whole_range.max);
 741                         false_state = filter_range(orig, whole_range.min, fixed);
 742                 }
 743                 break;
 744         case '>':
 745         case SPECIAL_UNSIGNED_GT:
 746                 if (left) {
 747                         true_state = filter_range(orig, whole_range.min, fixed);
 748                         false_state = filter_range(orig, fixed + 1, whole_range.max);
 749                 } else {
 750                         true_state = filter_range(orig, fixed, whole_range.max);
 751                         false_state = filter_range(orig, whole_range.min, fixed - 1);
 752                 }
 753                 break;
 754         case SPECIAL_NOTEQUAL:
 755                 true_state = filter_range(orig, fixed, fixed);
 756                 if (possibly_true(SPECIAL_EQUAL, get_dinfo(orig), fixed, fixed))
 757                         false_state = alloc_extra_state(fixed);
 758                 else
 759                         false_state = alloc_extra_state_empty();
 760                 break;
 761         default:
 762                 sm_msg("unhandled comparison %d\n", comparison);
 763                 goto free;
 764         }
 765         set_extra_true_false(name, sym, true_state, false_state);
 766 free:
 767         free_string(name);
 768 }
 769
 770 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
 771 void __extra_match_condition(struct expression *expr)
 772 {
 773         struct symbol *sym;
 774         char *name;
 775         struct smatch_state *pre_state;
 776         struct smatch_state *true_state;
 777         struct smatch_state *false_state;
 778
 779         expr = strip_expr(expr);
 780         switch (expr->type) {
 781         case EXPR_CALL:
 782                 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
 783                 return;
 784         case EXPR_PREOP:
 785         case EXPR_SYMBOL:
 786         case EXPR_DEREF:
 787                 name = get_variable_from_expr(expr, &sym);
 788                 if (!name)
 789                         return;
 790                 pre_state = get_state(my_id, name, sym);
 791                 true_state = add_filter(pre_state, 0);
 792                 if (possibly_true(SPECIAL_EQUAL, get_dinfo(pre_state), 0, 0))
 793                         false_state = alloc_extra_state(0);
 794                 else
 795                         false_state = alloc_extra_state_empty();
 796                 set_extra_true_false(name, sym, true_state, false_state);
 797                 free_string(name);
 798                 return;
 799         case EXPR_COMPARE:
 800                 match_comparison(expr);
 801                 return;
 802         case EXPR_ASSIGNMENT:
 803                 __extra_match_condition(expr->left);
 804                 return;
 805         }
 806 }
 807
 808 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
 809 int implied_not_equal(struct expression *expr, long long val)
 810 {
 811         char *name;
 812         struct symbol *sym;
 813         struct smatch_state *state;
 814         int ret = 0;
 815
 816         name = get_variable_from_expr(expr, &sym);
 817         if (!name || !sym)
 818                 goto exit;
 819         state = get_state(my_id, name, sym);
 820         if (!state || !state->data)
 821                 goto exit;
 822         ret = !possibly_false(SPECIAL_NOTEQUAL, get_dinfo(state), val, 1);
 823 exit:
 824         free_string(name);
 825         return ret;
 826 }
 827
 828 int known_condition_true(struct expression *expr)
 829 {
 830         long long tmp;
 831
 832         if (!expr)
 833                 return 0;
 834
 835         if (get_value(expr, &tmp) && tmp)
 836                 return 1;
 837
 838         expr = strip_expr(expr);
 839         switch (expr->type) {
 840         case EXPR_PREOP:
 841                 if (expr->op == '!') {
 842                         if (known_condition_false(expr->unop))
 843                                 return 1;
 844                         break;
 845                 }
 846                 break;
 847         default:
 848                 break;
 849         }
 850         return 0;
 851 }
 852
 853 int known_condition_false(struct expression *expr)
 854 {
 855         if (!expr)
 856                 return 0;
 857
 858         if (is_zero(expr))
 859                 return 1;
 860
 861         switch (expr->type) {
 862         case EXPR_PREOP:
 863                 if (expr->op == '!') {
 864                         if (known_condition_true(expr->unop))
 865                                 return 1;
 866                         break;
 867                 }
 868                 break;
 869         default:
 870                 break;
 871         }
 872         return 0;
 873 }
 874
 875 static int do_comparison_range(struct expression *expr)
 876 {
 877         struct symbol *sym;
 878         char *name;
 879         struct smatch_state *state;
 880         long long value;
 881         int left = 0;
 882         int poss_true, poss_false;
 883
 884         if (!get_value(expr->left, &value)) {
 885                 if (!get_value(expr->right, &value))
 886                         return 3;
 887                 left = 1;
 888         }
 889         if (left)
 890                 name = get_variable_from_expr(expr->left, &sym);
 891         else
 892                 name = get_variable_from_expr(expr->right, &sym);
 893         if (!name || !sym)
 894                 goto free;
 895         state = get_state(SMATCH_EXTRA, name, sym);
 896         if (!state)
 897                 goto free;
 898         poss_true = possibly_true(expr->op, get_dinfo(state), value, left);
 899         poss_false = possibly_false(expr->op, get_dinfo(state), value, left);
 900         if (!poss_true && !poss_false)
 901                 return 0;
 902         if (poss_true && !poss_false)
 903                 return 1;
 904         if (!poss_true && poss_false)
 905                 return 2;
 906         if (poss_true && poss_false)
 907                 return 3;
 908 free:
 909         free_string(name);
 910         return 3;
 911 }
 912
 913 int implied_condition_true(struct expression *expr)
 914 {
 915         struct statement *stmt;
 916         long long tmp;
 917         long long val;
 918
 919         if (!expr)
 920                 return 0;
 921
 922         if (get_implied_value(expr, &tmp) && tmp)
 923                 return 1;
 924
 925         if (expr->type == EXPR_POSTOP)
 926                 return implied_condition_true(expr->unop);
 927
 928         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
 929                 return implied_not_equal(expr->unop, 1);
 930         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
 931                 return implied_not_equal(expr->unop, -1);
 932
 933         expr = strip_expr(expr);
 934         switch (expr->type) {
 935         case EXPR_COMPARE:
 936                 if (do_comparison_range(expr) == 1)
 937                         return 1;
 938                 break;
 939         case EXPR_PREOP:
 940                 if (expr->op == '!') {
 941                         if (implied_condition_false(expr->unop))
 942                                 return 1;
 943                         break;
 944                 }
 945                 stmt = get_block_thing(expr);
 946                 if (last_stmt_val(stmt, &val) && val == 1)
 947                         return 1;
 948                 break;
 949         default:
 950                 if (implied_not_equal(expr, 0) == 1)
 951                         return 1;
 952                 break;
 953         }
 954         return 0;
 955 }
 956
 957 int implied_condition_false(struct expression *expr)
 958 {
 959         struct statement *stmt;
 960         struct expression *tmp;
 961         long long val;
 962
 963         if (!expr)
 964                 return 0;
 965
 966         if (is_zero(expr))
 967                 return 1;
 968
 969         switch (expr->type) {
 970         case EXPR_COMPARE:
 971                 if (do_comparison_range(expr) == 2)
 972                         return 1;
 973         case EXPR_PREOP:
 974                 if (expr->op == '!') {
 975                         if (implied_condition_true(expr->unop))
 976                                 return 1;
 977                         break;
 978                 }
 979                 stmt = get_block_thing(expr);
 980                 if (last_stmt_val(stmt, &val) && val == 0)
 981                         return 1;
 982                 tmp = strip_expr(expr);
 983                 if (tmp != expr)
 984                         return implied_condition_false(tmp);
 985                 break;
 986         default:
 987                 if (get_implied_value(expr, &val) && val == 0)
 988                         return 1;
 989                 break;
 990         }
 991         return 0;
 992 }
 993
 994 int get_implied_range_list(struct expression *expr, struct range_list **rl)
 995 {
 996         long long val;
 997         struct smatch_state *state;
 998
 999         expr = strip_expr(expr);
1000
1001         state = get_state_expr(my_id, expr);
1002         if (state) {
1003                 *rl = clone_range_list(get_dinfo(state)->value_ranges);
1004                 return 1;
1005         }
1006
1007         if (get_implied_value(expr, &val)) {
1008                 *rl = NULL;
1009                 add_range(rl, val, val);
1010                 return 1;
1011         }
1012
1013         if (expr->type == EXPR_BINOP && expr->op == '%') {
1014                 if (!get_implied_value(expr->right, &val))
1015                         return 0;
1016                 *rl = NULL;
1017                 add_range(rl, 0, val - 1);
1018                 return 1;
1019         }
1020
1021         return 0;
1022 }
1023
1024 int is_whole_range(struct smatch_state *state)
1025 {
1026         struct data_info *dinfo;
1027         struct data_range *drange;
1028
1029         if (!state)
1030                 return 0;
1031         dinfo = get_dinfo(state);
1032         drange = first_ptr_list((struct ptr_list *)dinfo->value_ranges);
1033         if (drange->min == whole_range.min && drange->max == whole_range.max)
1034                 return 1;
1035         return 0;
1036 }
1037
1038 void register_smatch_extra(int id)
1039 {
1040         my_id = id;
1041         add_merge_hook(my_id, &merge_func);
1042         add_unmatched_state_hook(my_id, &unmatched_state);
1043         add_hook(&unop_expr, OP_HOOK);
1044         add_hook(&match_function_def, FUNC_DEF_HOOK);
1045         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
1046         add_hook(&match_assign, ASSIGNMENT_HOOK);
1047         add_hook(&match_declarations, DECLARATION_HOOK);
1048 }