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 smatch_state *alloc_extra_state_empty(void)
  34 {
  35         struct smatch_state *state;
  36         struct data_info *dinfo;
  37
  38         dinfo = __alloc_data_info(0);
  39         dinfo->type = DATA_RANGE;
  40         dinfo->value_ranges = NULL;
  41         state = __alloc_smatch_state(0);
  42         state->data = dinfo;
  43         return state;
  44 }
  45
  46 static struct smatch_state *alloc_extra_state_no_name(int val)
  47 {
  48         struct smatch_state *state;
  49
  50         state = __alloc_smatch_state(0);
  51         state->data = (void *)alloc_dinfo_range(val, val);
  52         return state;
  53 }
  54
  55 /* We do this because ->value_ranges is a list */
  56 struct smatch_state *extra_undefined(void)
  57 {
  58         struct data_info *dinfo;
  59         static struct smatch_state *ret;
  60         static struct symbol *prev_func;
  61
  62         if  (prev_func == cur_func)
  63                 return ret;
  64         prev_func = cur_func;
  65
  66         dinfo = alloc_dinfo_range(whole_range.min, whole_range.max);
  67         ret = __alloc_smatch_state(0);
  68         ret->name = "unknown";
  69         ret->data = dinfo;
  70         return ret;
  71 }
  72
  73 struct smatch_state *alloc_extra_state(long long val)
  74 {
  75         struct smatch_state *state;
  76
  77         state = alloc_extra_state_no_name(val);
  78         state->name = show_ranges(get_dinfo(state)->value_ranges);
  79         return state;
  80 }
  81
  82 struct smatch_state *alloc_extra_state_range(long long min, long long max)
  83 {
  84         struct smatch_state *state;
  85
  86         if (min == whole_range.min && max == whole_range.max)
  87                 return extra_undefined();
  88         state = __alloc_smatch_state(0);
  89         state->data = (void *)alloc_dinfo_range(min, max);
  90         state->name = show_ranges(get_dinfo(state)->value_ranges);
  91         return state;
  92 }
  93
  94 struct smatch_state *alloc_extra_state_range_list(struct range_list *rl)
  95 {
  96         struct smatch_state *state;
  97
  98         state = __alloc_smatch_state(0);
  99         state->data = (void *)alloc_dinfo_range_list(rl);
 100         state->name = show_ranges(get_dinfo(state)->value_ranges);
 101         return state;
 102 }
 103
 104 struct data_info *get_dinfo(struct smatch_state *state)
 105 {
 106         if (!state)
 107                 return NULL;
 108         return (struct data_info *)state->data;
 109
 110 }
 111
 112 struct smatch_state *filter_range(struct smatch_state *orig,
 113                                  long long filter_min, long long filter_max)
 114 {
 115         struct smatch_state *ret;
 116         struct data_info *orig_info;
 117         struct data_info *ret_info;
 118
 119         if (!orig)
 120                 orig = extra_undefined();
 121         orig_info = get_dinfo(orig);
 122         ret = alloc_extra_state_empty();
 123         ret_info = get_dinfo(ret);
 124         ret_info->value_ranges = remove_range(orig_info->value_ranges, filter_min, filter_max);
 125         ret->name = show_ranges(ret_info->value_ranges);
 126         return ret;
 127 }
 128
 129 struct smatch_state *add_filter(struct smatch_state *orig, long long num)
 130 {
 131         return filter_range(orig, num, num);
 132 }
 133
 134 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
 135                                        struct smatch_state *s1,
 136                                        struct smatch_state *s2)
 137 {
 138         struct data_info *info1 = get_dinfo(s1);
 139         struct data_info *info2 = get_dinfo(s2);
 140         struct data_info *ret_info;
 141         struct smatch_state *tmp;
 142         struct range_list *value_ranges;
 143
 144         value_ranges = range_list_union(info1->value_ranges, info2->value_ranges);
 145         tmp = alloc_extra_state_empty();
 146         ret_info = get_dinfo(tmp);
 147         ret_info->value_ranges = value_ranges;
 148         tmp->name = show_ranges(ret_info->value_ranges);
 149         return tmp;
 150 }
 151
 152 struct sm_state *__extra_pre_loop_hook_before(struct statement *iterator_pre_statement)
 153 {
 154         struct expression *expr;
 155         char *name;
 156         struct symbol *sym;
 157         struct sm_state *ret = NULL;
 158
 159         if (!iterator_pre_statement)
 160                 return NULL;
 161         if (iterator_pre_statement->type != STMT_EXPRESSION)
 162                 return NULL;
 163         expr = iterator_pre_statement->expression;
 164         if (expr->type != EXPR_ASSIGNMENT)
 165                 return NULL;
 166         name = get_variable_from_expr(expr->left, &sym);
 167         if (!name || !sym)
 168                 goto free;
 169         ret = get_sm_state(my_id, name, sym);
 170 free:
 171         free_string(name);
 172         return ret;
 173 }
 174
 175 int __iterator_unchanged(struct sm_state *sm, struct statement *iterator)
 176 {
 177         struct expression *iter_expr;
 178         char *name;
 179         struct symbol *sym;
 180         int ret = 0;
 181
 182         if (!iterator)
 183                 return 0;
 184         if (iterator->type != STMT_EXPRESSION)
 185                 return 0;
 186         iter_expr = iterator->expression;
 187         if (iter_expr->op != SPECIAL_INCREMENT && iter_expr->op != SPECIAL_DECREMENT)
 188                 return 0;
 189         name = get_variable_from_expr(iter_expr->unop, &sym);
 190         if (!name || !sym)
 191                 goto free;
 192         if (get_sm_state(my_id, name, sym) == sm)
 193                 ret = 1;
 194 free:
 195         free_string(name);
 196         return ret;
 197 }
 198
 199 void __extra_pre_loop_hook_after(struct sm_state *sm,
 200                                 struct statement *iterator,
 201                                 struct expression *condition)
 202 {
 203         struct expression *iter_expr;
 204         char *name;
 205         struct symbol *sym;
 206         long long value;
 207         int left = 0;
 208         struct smatch_state *state;
 209         struct data_info *dinfo;
 210         long long min, max;
 211
 212         iter_expr = iterator->expression;
 213
 214         if (condition->type != EXPR_COMPARE)
 215                 return;
 216         if (!get_value(condition->left, &value)) {
 217                 if (!get_value(condition->right, &value))
 218                         return;
 219                 left = 1;
 220         }
 221         if (left)
 222                 name = get_variable_from_expr(condition->left, &sym);
 223         else
 224                 name = get_variable_from_expr(condition->right, &sym);
 225         if (!name || !sym)
 226                 goto free;
 227         if (sym != sm->sym || strcmp(name, sm->name))
 228                 goto free;
 229         state = get_state(my_id, name, sym);
 230         dinfo = get_dinfo(state);
 231         min = get_dinfo_min(dinfo);
 232         max = get_dinfo_max(dinfo);
 233         if (iter_expr->op == SPECIAL_INCREMENT && min != whole_range.min && max == whole_range.max) {
 234                 set_state(my_id, name, sym, alloc_extra_state(min));
 235         } else if (min == whole_range.min && max != whole_range.max) {
 236                 set_state(my_id, name, sym, alloc_extra_state(max));
 237         }
 238 free:
 239         free_string(name);
 240         return;
 241 }
 242
 243 static struct smatch_state *unmatched_state(struct sm_state *sm)
 244 {
 245         return extra_undefined();
 246 }
 247
 248 static void match_function_call(struct expression *expr)
 249 {
 250         struct expression *tmp;
 251         struct symbol *sym;
 252         char *name;
 253         int i = 0;
 254
 255         FOR_EACH_PTR(expr->args, tmp) {
 256                 if (tmp->type == EXPR_PREOP && tmp->op == '&') {
 257                         name = get_variable_from_expr(tmp->unop, &sym);
 258                         if (name) {
 259                                 set_state(my_id, name, sym, extra_undefined());
 260                         }
 261                         free_string(name);
 262                 }
 263                 i++;
 264         } END_FOR_EACH_PTR(tmp);
 265 }
 266
 267 static void match_assign(struct expression *expr)
 268 {
 269         struct expression *left;
 270         struct expression *right;
 271         struct symbol *sym;
 272         char *name;
 273         long long value;
 274         int known;
 275         long long min = whole_range.min;
 276         long long max = whole_range.max;
 277         long long tmp;
 278         struct range_list *rl = NULL;
 279
 280         left = strip_expr(expr->left);
 281         name = get_variable_from_expr(left, &sym);
 282         if (!name)
 283                 return;
 284         right = strip_expr(expr->right);
 285         while (right->type == EXPR_ASSIGNMENT && right->op == '=')
 286                 right = strip_expr(right->left);
 287
 288         known = get_implied_range_list(right, &rl);
 289         if (expr->op == '=') {
 290                 if (known)
 291                         set_state(my_id, name, sym, alloc_extra_state_range_list(rl));
 292                 else
 293                         set_state(my_id, name, sym, extra_undefined());
 294                 goto free;
 295         }
 296
 297         known = get_implied_value(right, &value);
 298         if (expr->op == SPECIAL_ADD_ASSIGN) {
 299                 if (get_implied_min(left, &tmp)) {
 300                         if (known)
 301                                 min = tmp + value;
 302                         else
 303                                 min = tmp;
 304                 }
 305
 306         }
 307         if (expr->op == SPECIAL_SUB_ASSIGN) {
 308                 if (get_implied_max(left, &tmp)) {
 309                         if (known)
 310                                 max = tmp - value;
 311                         else
 312                                 max = tmp;
 313                 }
 314
 315         }
 316         set_state(my_id, name, sym, alloc_extra_state_range(min, max));
 317 free:
 318         free_string(name);
 319 }
 320
 321 static void unop_expr(struct expression *expr)
 322 {
 323         struct symbol *sym;
 324         char *name;
 325         long long min = whole_range.min;
 326         long long max = whole_range.max;
 327         long long val;
 328
 329         if (expr->op == '*')
 330                 return;
 331         if (expr->op == '(')
 332                 return;
 333         if (expr->op == '!')
 334                 return;
 335
 336         name = get_variable_from_expr(expr->unop, &sym);
 337         if (!name)
 338                 goto free;
 339         if (expr->op == SPECIAL_INCREMENT) {
 340                 if (get_implied_min(expr->unop, &val))
 341                         min = val + 1;
 342         }
 343         if (expr->op == SPECIAL_DECREMENT) {
 344                 if (get_implied_max(expr->unop, &val))
 345                         max = val - 1;
 346         }
 347         set_state(my_id, name, sym, alloc_extra_state_range(min, max));
 348 free:
 349         free_string(name);
 350 }
 351
 352 static void match_declarations(struct symbol *sym)
 353 {
 354         const char *name;
 355         long long val;
 356
 357         if (sym->ident) {
 358                 name = sym->ident->name;
 359                 if (sym->initializer) {
 360                         if (get_value(sym->initializer, &val))
 361                                 set_state(my_id, name, sym, alloc_extra_state(val));
 362                         else
 363                                 set_state(my_id, name, sym, extra_undefined());
 364                         scoped_state(my_id, name, sym);
 365                 } else {
 366                         set_state(my_id, name, sym, extra_undefined());
 367                         scoped_state(my_id, name, sym);
 368                 }
 369         }
 370 }
 371
 372 static void match_function_def(struct symbol *sym)
 373 {
 374         struct symbol *arg;
 375
 376         cur_func = sym;
 377         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 378                 if (!arg->ident) {
 379                         continue;
 380                 }
 381                 set_state(my_id, arg->ident->name, arg, extra_undefined());
 382         } END_FOR_EACH_PTR(arg);
 383 }
 384
 385 #define VAL_SINGLE 0
 386 #define VAL_MAX    1
 387 #define VAL_MIN    2
 388
 389 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 390 {
 391         struct smatch_state *state;
 392         struct symbol *sym;
 393         char *name;
 394
 395         if (get_value(expr, val))
 396                 return 1;
 397
 398         name = get_variable_from_expr(expr, &sym);
 399         if (!name)
 400                 return 0;
 401         state = get_state(my_id, name, sym);
 402         free_string(name);
 403         if (!state || !state->data)
 404                 return 0;
 405         if (what == VAL_SINGLE)
 406                 return get_single_value_from_range(get_dinfo(state), val);
 407         if (what == VAL_MAX) {
 408                 *val = get_dinfo_max(get_dinfo(state));
 409                 if (*val == whole_range.max) /* this means just guessing */
 410                         return 0;
 411                 return 1;
 412         }
 413         *val = get_dinfo_min(get_dinfo(state));
 414         if (*val == whole_range.min)
 415                 return 0;
 416         return 1;
 417 }
 418
 419 int get_implied_single_val(struct expression *expr, long long *val)
 420 {
 421         return get_implied_value_helper(expr, val, VAL_SINGLE);
 422 }
 423
 424 int get_implied_max(struct expression *expr, long long *val)
 425 {
 426         return get_implied_value_helper(expr, val, VAL_MAX);
 427 }
 428
 429 int get_implied_min(struct expression *expr, long long *val)
 430 {
 431         return get_implied_value_helper(expr, val, VAL_MIN);
 432 }
 433
 434 int get_implied_single_fuzzy_max(struct expression *expr, long long *max)
 435 {
 436         struct sm_state *sm;
 437         struct sm_state *tmp;
 438
 439         if (get_implied_max(expr, max))
 440                 return 1;
 441
 442         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 443         if (!sm)
 444                 return 0;
 445
 446         *max = whole_range.min;
 447         FOR_EACH_PTR(sm->possible, tmp) {
 448                 long long new_min;
 449
 450                 new_min = get_dinfo_min(get_dinfo(tmp->state));
 451                 if (new_min > *max)
 452                         *max = new_min;
 453         } END_FOR_EACH_PTR(tmp);
 454
 455         if (*max > whole_range.min)
 456                 return 1;
 457         return 0;
 458 }
 459
 460 int get_implied_single_fuzzy_min(struct expression *expr, long long *min)
 461 {
 462         struct sm_state *sm;
 463         struct sm_state *tmp;
 464
 465         if (get_implied_min(expr, min))
 466                 return 1;
 467
 468         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 469         if (!sm)
 470                 return 0;
 471
 472         *min = whole_range.max;
 473         FOR_EACH_PTR(sm->possible, tmp) {
 474                 long long new_max;
 475
 476                 new_max = get_dinfo_max(get_dinfo(tmp->state));
 477                 if (new_max < *min)
 478                         *min = new_max;
 479         } END_FOR_EACH_PTR(tmp);
 480
 481         if (*min < whole_range.max)
 482                 return 1;
 483         return 0;
 484 }
 485
 486 static int last_stmt_val(struct statement *stmt, long long *val)
 487 {
 488         struct expression *expr;
 489
 490         if (!stmt)
 491                 return 0;
 492
 493         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 494         if (stmt->type != STMT_EXPRESSION)
 495                 return 0;
 496         expr = stmt->expression;
 497         return get_value(expr, val);
 498 }
 499
 500 static void match_comparison(struct expression *expr)
 501 {
 502         long long fixed;
 503         char *name = NULL;
 504         struct symbol *sym;
 505         struct smatch_state *one_state;
 506         struct smatch_state *two_state;
 507         struct smatch_state *orig;
 508         int left = 0;
 509         int comparison = expr->op;
 510         struct expression *varies = expr->right;
 511
 512         if (!get_value(expr->left, &fixed)) {
 513                 if (!get_value(expr->right, &fixed))
 514                         return;
 515                 varies = expr->left;
 516                 left = 1;
 517         }
 518         if (varies->op == SPECIAL_INCREMENT || varies->op == SPECIAL_DECREMENT)
 519                 varies = varies->unop;
 520         if (varies->type == EXPR_CALL) {
 521                 function_comparison(comparison, varies, fixed, left);
 522                 return;
 523         }
 524
 525         name = get_variable_from_expr(varies, &sym);
 526         if (!name || !sym)
 527                 goto free;
 528
 529         orig = get_state(my_id, name, sym);
 530         if (!orig)
 531                 orig = extra_undefined();
 532
 533         switch (comparison) {
 534         case '<':
 535         case SPECIAL_UNSIGNED_LT:
 536                 one_state = filter_range(orig, whole_range.min, fixed - 1);
 537                 two_state = filter_range(orig, fixed, whole_range.max);
 538                 if (left)
 539                         set_true_false_states(my_id, name, sym, two_state, one_state);
 540                 else
 541                         set_true_false_states(my_id, name, sym, one_state, two_state);
 542                 return;
 543         case SPECIAL_UNSIGNED_LTE:
 544         case SPECIAL_LTE:
 545                 one_state = filter_range(orig, whole_range.min, fixed);
 546                 two_state = filter_range(orig, fixed + 1, whole_range.max);
 547                 if (left)
 548                         set_true_false_states(my_id, name, sym, two_state, one_state);
 549                 else
 550                         set_true_false_states(my_id, name, sym, one_state, two_state);
 551                 return;
 552         case SPECIAL_EQUAL:
 553                 // todo.  print a warning here for impossible conditions.
 554                 one_state = alloc_extra_state(fixed);
 555                 two_state = filter_range(orig, fixed, fixed);
 556                 set_true_false_states(my_id, name, sym, one_state, two_state);
 557                 return;
 558         case SPECIAL_UNSIGNED_GTE:
 559         case SPECIAL_GTE:
 560                 one_state = filter_range(orig, whole_range.min, fixed - 1);
 561                 two_state = filter_range(orig, fixed, whole_range.max);
 562                 if (left)
 563                         set_true_false_states(my_id, name, sym, one_state, two_state);
 564                 else
 565                         set_true_false_states(my_id, name, sym, two_state, one_state);
 566                 return;
 567         case '>':
 568         case SPECIAL_UNSIGNED_GT:
 569                 one_state = filter_range(orig, whole_range.min, fixed);
 570                 two_state = filter_range(orig, fixed + 1, whole_range.max);
 571                 if (left)
 572                         set_true_false_states(my_id, name, sym, one_state, two_state);
 573                 else
 574                         set_true_false_states(my_id, name, sym, two_state, one_state);
 575                 return;
 576         case SPECIAL_NOTEQUAL:
 577                 one_state = alloc_extra_state(fixed);
 578                 two_state = filter_range(orig, fixed, fixed);
 579                 set_true_false_states(my_id, name, sym, two_state, one_state);
 580                 return;
 581         default:
 582                 sm_msg("unhandled comparison %d\n", comparison);
 583                 return;
 584         }
 585         return;
 586 free:
 587         free_string(name);
 588 }
 589
 590 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
 591 void __extra_match_condition(struct expression *expr)
 592 {
 593         struct symbol *sym;
 594         char *name;
 595         struct smatch_state *pre_state;
 596         struct smatch_state *true_state;
 597         struct smatch_state *false_state;
 598
 599         expr = strip_expr(expr);
 600         switch (expr->type) {
 601         case EXPR_CALL:
 602                 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
 603                 return;
 604         case EXPR_PREOP:
 605         case EXPR_SYMBOL:
 606         case EXPR_DEREF:
 607                 name = get_variable_from_expr(expr, &sym);
 608                 if (!name)
 609                         return;
 610                 pre_state = get_state(my_id, name, sym);
 611                 true_state = add_filter(pre_state, 0);
 612                 false_state = alloc_extra_state(0);
 613                 set_true_false_states(my_id, name, sym, true_state, false_state);
 614                 free_string(name);
 615                 return;
 616         case EXPR_COMPARE:
 617                 match_comparison(expr);
 618                 return;
 619         case EXPR_ASSIGNMENT:
 620                 __extra_match_condition(expr->left);
 621                 return;
 622         }
 623 }
 624
 625 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
 626 int implied_not_equal(struct expression *expr, long long val)
 627 {
 628         char *name;
 629         struct symbol *sym;
 630         struct smatch_state *state;
 631         int ret = 0;
 632
 633         name = get_variable_from_expr(expr, &sym);
 634         if (!name || !sym)
 635                 goto exit;
 636         state = get_state(my_id, name, sym);
 637         if (!state || !state->data)
 638                 goto exit;
 639         ret = !possibly_false(SPECIAL_NOTEQUAL, get_dinfo(state), val, 1);
 640 exit:
 641         free_string(name);
 642         return ret;
 643 }
 644
 645 int known_condition_true(struct expression *expr)
 646 {
 647         long long tmp;
 648
 649         if (!expr)
 650                 return 0;
 651
 652         if (get_value(expr, &tmp) && tmp)
 653                 return 1;
 654
 655         expr = strip_expr(expr);
 656         switch (expr->type) {
 657         case EXPR_PREOP:
 658                 if (expr->op == '!') {
 659                         if (known_condition_false(expr->unop))
 660                                 return 1;
 661                         break;
 662                 }
 663                 break;
 664         default:
 665                 break;
 666         }
 667         return 0;
 668 }
 669
 670 int known_condition_false(struct expression *expr)
 671 {
 672         if (!expr)
 673                 return 0;
 674
 675         if (is_zero(expr))
 676                 return 1;
 677
 678         switch (expr->type) {
 679         case EXPR_PREOP:
 680                 if (expr->op == '!') {
 681                         if (known_condition_true(expr->unop))
 682                                 return 1;
 683                         break;
 684                 }
 685                 break;
 686         default:
 687                 break;
 688         }
 689         return 0;
 690 }
 691
 692 static int do_comparison_range(struct expression *expr)
 693 {
 694         struct symbol *sym;
 695         char *name;
 696         struct smatch_state *state;
 697         long long value;
 698         int left = 0;
 699         int poss_true, poss_false;
 700
 701         if (!get_value(expr->left, &value)) {
 702                 if (!get_value(expr->right, &value))
 703                         return 3;
 704                 left = 1;
 705         }
 706         if (left)
 707                 name = get_variable_from_expr(expr->left, &sym);
 708         else
 709                 name = get_variable_from_expr(expr->right, &sym);
 710         if (!name || !sym)
 711                 goto free;
 712         state = get_state(SMATCH_EXTRA, name, sym);
 713         if (!state)
 714                 goto free;
 715         poss_true = possibly_true(expr->op, get_dinfo(state), value, left);
 716         poss_false = possibly_false(expr->op, get_dinfo(state), value, left);
 717         if (!poss_true && !poss_false)
 718                 return 0;
 719         if (poss_true && !poss_false)
 720                 return 1;
 721         if (!poss_true && poss_false)
 722                 return 2;
 723         if (poss_true && poss_false)
 724                 return 3;
 725 free:
 726         free_string(name);
 727         return 3;
 728 }
 729
 730 int implied_condition_true(struct expression *expr)
 731 {
 732         struct statement *stmt;
 733         long long tmp;
 734         long long val;
 735
 736         if (!expr)
 737                 return 0;
 738
 739         if (get_value(expr, &tmp) && tmp)
 740                 return 1;
 741
 742         expr = strip_expr(expr);
 743         switch (expr->type) {
 744         case EXPR_COMPARE:
 745                 if (do_comparison_range(expr) == 1)
 746                         return 1;
 747                 break;
 748         case EXPR_PREOP:
 749                 if (expr->op == '!') {
 750                         if (implied_condition_false(expr->unop))
 751                                 return 1;
 752                         break;
 753                 }
 754                 stmt = get_block_thing(expr);
 755                 if (last_stmt_val(stmt, &val) && val == 1)
 756                         return 1;
 757                 break;
 758         default:
 759                 if (implied_not_equal(expr, 0) == 1)
 760                         return 1;
 761                 break;
 762         }
 763         return 0;
 764 }
 765
 766 int implied_condition_false(struct expression *expr)
 767 {
 768         struct statement *stmt;
 769         struct expression *tmp;
 770         long long val;
 771
 772         if (!expr)
 773                 return 0;
 774
 775         if (is_zero(expr))
 776                 return 1;
 777
 778         switch (expr->type) {
 779         case EXPR_COMPARE:
 780                 if (do_comparison_range(expr) == 2)
 781                         return 1;
 782         case EXPR_PREOP:
 783                 if (expr->op == '!') {
 784                         if (implied_condition_true(expr->unop))
 785                                 return 1;
 786                         break;
 787                 }
 788                 stmt = get_block_thing(expr);
 789                 if (last_stmt_val(stmt, &val) && val == 0)
 790                         return 1;
 791                 tmp = strip_expr(expr);
 792                 if (tmp != expr)
 793                         return implied_condition_false(tmp);
 794                 break;
 795         default:
 796                 if (get_implied_value(expr, &val) && val == 0)
 797                         return 1;
 798                 break;
 799         }
 800         return 0;
 801 }
 802
 803 int get_implied_range_list(struct expression *expr, struct range_list **rl)
 804 {
 805         long long val;
 806         struct smatch_state *state;
 807
 808         expr = strip_expr(expr);
 809
 810         state = get_state_expr(my_id, expr);
 811         if (state) {
 812                 *rl = clone_range_list(get_dinfo(state)->value_ranges);
 813                 return 1;
 814         }
 815
 816         if (get_implied_value(expr, &val)) {
 817                 *rl = NULL;
 818                 add_range(rl, val, val);
 819                 return 1;
 820         }
 821
 822         if (expr->type == EXPR_BINOP && expr->op == '%') {
 823                 if (!get_implied_value(expr->right, &val))
 824                         return 0;
 825                 *rl = NULL;
 826                 add_range(rl, 0, val - 1);
 827                 return 1;
 828         }
 829
 830         return 0;
 831 }
 832
 833 void register_smatch_extra(int id)
 834 {
 835         my_id = id;
 836         add_merge_hook(my_id, &merge_func);
 837         add_unmatched_state_hook(my_id, &unmatched_state);
 838         add_hook(&unop_expr, OP_HOOK);
 839         add_hook(&match_function_def, FUNC_DEF_HOOK);
 840         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 841         add_hook(&match_assign, ASSIGNMENT_HOOK);
 842         add_hook(&match_declarations, DECLARATION_HOOK);
 843 }