12166 resync smatch to 0.6.1-rc1-il-3

   1 /*
   2  * Copyright (C) 2008 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  *
  17  * Copyright 2019 Joyent, Inc.
  18  */
  19 
  20 /*
  21  * Imagine we have this code:
  22  * foo = 1;
  23  * if (bar)
  24  *         foo = 99;
  25  * else
  26  *         frob();
  27  *                   //  <-- point #1
  28  * if (foo == 99)    //  <-- point #2
  29  *         bar->baz; //  <-- point #3
  30  *
  31  *
  32  * At point #3 bar is non null and can be dereferenced.
  33  *
  34  * It's smatch_implied.c which sets bar to non null at point #2.
  35  *
  36  * At point #1 merge_slist() stores the list of states from both
  37  * the true and false paths.  On the true path foo == 99 and on
  38  * the false path foo == 1.  merge_slist() sets their pool
  39  * list to show the other states which were there when foo == 99.
  40  *
  41  * When it comes to the if (foo == 99) the smatch implied hook
  42  * looks for all the pools where foo was not 99.  It makes a list
  43  * of those.
  44  *
  45  * Then for bar (and all the other states) it says, ok bar is a
  46  * merged state that came from these previous states.  We'll
  47  * chop out all the states where it came from a pool where
  48  * foo != 99 and merge it all back together.
  49  *
  50  * That is the implied state of bar.
  51  *
  52  * merge_slist() sets up ->pool.  An sm_state only has one ->pool and
  53  *    that is the pool where it was first set.  The my pool gets set when
  54  *    code paths merge.  States that have been set since the last merge do
  55  *    not have a ->pool.
  56  * merge_sm_state() sets ->left and ->right.  (These are the states which were
  57  *    merged to form the current state.)
  58  * a pool:  a pool is an slist that has been merged with another slist.
  59  */
  60 
  61 #include <time.h>
  62 #include "smatch.h"
  63 #include "smatch_slist.h"
  64 #include "smatch_extra.h"
  65 
  66 char *implied_debug_msg;
  67 
  68 bool implications_off;
  69 
  70 #define implied_debug 0
  71 #define DIMPLIED(msg...) do { if (implied_debug) printf(msg); } while (0)
  72 
  73 bool debug_implied(void)
  74 {
  75         return implied_debug;
  76 }
  77 
  78 /*
  79  * tmp_range_list():
  80  * It messes things up to free range list allocations.  This helper fuction
  81  * lets us reuse memory instead of doing new allocations.
  82  */
  83 static struct range_list *tmp_range_list(struct symbol *type, long long num)
  84 {
  85         static struct range_list *my_list = NULL;
  86         static struct data_range *my_range;
  87 
  88         __free_ptr_list((struct ptr_list **)&my_list);
  89         my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
  90         add_ptr_list(&my_list, my_range);
  91         return my_list;
  92 }
  93 
  94 static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
  95 {
  96         if (!implied_debug && !option_debug)
  97                 return;
  98 
  99         if (istrue && isfalse) {
 100                 printf("%s: %d: does not exist.\n", show_sm(sm), sm->line);
 101         } else if (istrue) {
 102                 printf("'%s = %s' from %d is true. %s[stree %d]\n", sm->name, show_state(sm->state),
 103                         sm->line, sm->merged ? "[merged]" : "[leaf]",
 104                         get_stree_id(sm->pool));
 105         } else if (isfalse) {
 106                 printf("'%s = %s' from %d is false. %s[stree %d]\n", sm->name, show_state(sm->state),
 107                         sm->line,
 108                         sm->merged ? "[merged]" : "[leaf]",
 109                         get_stree_id(sm->pool));
 110         } else {
 111                 printf("'%s = %s' from %d could be true or false. %s[stree %d]\n", sm->name,
 112                         show_state(sm->state), sm->line,
 113                         sm->merged ? "[merged]" : "[leaf]",
 114                         get_stree_id(sm->pool));
 115         }
 116 }
 117 
 118 static int create_fake_history(struct sm_state *sm, int comparison, struct range_list *rl)
 119 {
 120         struct range_list *orig_rl;
 121         struct range_list *true_rl, *false_rl;
 122         struct stree *true_stree, *false_stree;
 123         struct sm_state *true_sm, *false_sm;
 124         sval_t sval;
 125 
 126         if (is_merged(sm) || sm->left || sm->right)
 127                 return 0;
 128         if (!rl_to_sval(rl, &sval))
 129                 return 0;
 130         if (!estate_rl(sm->state))
 131                 return 0;
 132 
 133         orig_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
 134         split_comparison_rl(orig_rl, comparison, rl, &true_rl, &false_rl, NULL, NULL);
 135 
 136         true_rl = rl_truncate_cast(estate_type(sm->state), true_rl);
 137         false_rl = rl_truncate_cast(estate_type(sm->state), false_rl);
 138         if (is_whole_rl(true_rl) || is_whole_rl(false_rl) ||
 139             !true_rl || !false_rl ||
 140             rl_equiv(orig_rl, true_rl) || rl_equiv(orig_rl, false_rl) ||
 141             rl_equiv(estate_rl(sm->state), true_rl) || rl_equiv(estate_rl(sm->state), false_rl))
 142                 return 0;
 143 
 144         if (rl_intersection(true_rl, false_rl)) {
 145                 sm_perror("parsing (%s (%s) %s %s)",
 146                         sm->name, sm->state->name, show_special(comparison), show_rl(rl));
 147                 sm_msg("true_rl = %s false_rl = %s intersection = %s",
 148                        show_rl(true_rl), show_rl(false_rl), show_rl(rl_intersection(true_rl, false_rl)));



 149                 return 0;
 150         }
 151 
 152         if (implied_debug)
 153                 sm_msg("fake_history: %s vs %s.  %s %s %s. --> T: %s F: %s",
 154                        sm->name, show_rl(rl), sm->state->name, show_special(comparison), show_rl(rl),
 155                        show_rl(true_rl), show_rl(false_rl));
 156 
 157         true_sm = clone_sm(sm);
 158         false_sm = clone_sm(sm);
 159 
 160         true_sm->state = clone_partial_estate(sm->state, true_rl);
 161         free_slist(&true_sm->possible);
 162         add_possible_sm(true_sm, true_sm);
 163         false_sm->state = clone_partial_estate(sm->state, false_rl);
 164         free_slist(&false_sm->possible);
 165         add_possible_sm(false_sm, false_sm);
 166 
 167         true_stree = clone_stree(sm->pool);
 168         false_stree = clone_stree(sm->pool);
 169 
 170         overwrite_sm_state_stree(&true_stree, true_sm);
 171         overwrite_sm_state_stree(&false_stree, false_sm);
 172 
 173         true_sm->pool = true_stree;
 174         false_sm->pool = false_stree;
 175 
 176         sm->merged = 1;
 177         sm->left = true_sm;
 178         sm->right = false_sm;
 179 
 180         return 1;
 181 }
 182 
 183 /*
 184  * add_pool() adds a slist to *pools. If the slist has already been
 185  * added earlier then it doesn't get added a second time.
 186  */
 187 void add_pool(struct state_list **pools, struct sm_state *new)
 188 {
 189         struct sm_state *tmp;
 190 
 191         FOR_EACH_PTR(*pools, tmp) {
 192                 if (tmp->pool < new->pool)
 193                         continue;
 194                 else if (tmp->pool == new->pool) {
 195                         return;
 196                 } else {
 197                         INSERT_CURRENT(new, tmp);
 198                         return;
 199                 }
 200         } END_FOR_EACH_PTR(tmp);
 201         add_ptr_list(pools, new);
 202 }
 203 
 204 static int pool_in_pools(struct stree *pool,
 205                          const struct state_list *slist)
 206 {
 207         struct sm_state *tmp;
 208 
 209         FOR_EACH_PTR(slist, tmp) {
 210                 if (!tmp->pool)
 211                         continue;
 212                 if (tmp->pool == pool)
 213                         return 1;
 214         } END_FOR_EACH_PTR(tmp);
 215         return 0;
 216 }
 217 
 218 static int remove_pool(struct state_list **pools, struct stree *remove)
 219 {
 220         struct sm_state *tmp;
 221         int ret = 0;
 222 
 223         FOR_EACH_PTR(*pools, tmp) {
 224                 if (tmp->pool == remove) {
 225                         DELETE_CURRENT_PTR(tmp);
 226                         ret = 1;
 227                 }
 228         } END_FOR_EACH_PTR(tmp);
 229 
 230         return ret;
 231 }
 232 
 233 /*
 234  * If 'foo' == 99 add it that pool to the true pools.  If it's false, add it to
 235  * the false pools.  If we're not sure, then we don't add it to either.
 236  */
 237 static void do_compare(struct sm_state *sm, int comparison, struct range_list *rl,
 238                         struct state_list **true_stack,
 239                         struct state_list **maybe_stack,
 240                         struct state_list **false_stack,
 241                         int *mixed, struct sm_state *gate_sm)
 242 {
 243         int istrue;
 244         int isfalse;
 245         struct range_list *var_rl;
 246 
 247         if (!sm->pool)
 248                 return;
 249 
 250         var_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
 251 
 252         istrue = !possibly_false_rl(var_rl, comparison, rl);
 253         isfalse = !possibly_true_rl(var_rl, comparison, rl);
 254 
 255         print_debug_tf(sm, istrue, isfalse);
 256 
 257         /* give up if we have borrowed implications (smatch_equiv.c) */
 258         if (sm->sym != gate_sm->sym ||
 259             strcmp(sm->name, gate_sm->name) != 0) {
 260                 if (mixed)
 261                         *mixed = 1;
 262         }
 263 
 264         if (mixed && !*mixed && !is_merged(sm) && !istrue && !isfalse) {
 265                 if (!create_fake_history(sm, comparison, rl))
 266                         *mixed = 1;
 267         }
 268 
 269         if (istrue)
 270                 add_pool(true_stack, sm);
 271         else if (isfalse)
 272                 add_pool(false_stack, sm);
 273         else
 274                 add_pool(maybe_stack, sm);
 275 }
 276 
 277 static int is_checked(struct state_list *checked, struct sm_state *sm)
 278 {
 279         struct sm_state *tmp;
 280 
 281         FOR_EACH_PTR(checked, tmp) {
 282                 if (tmp == sm)
 283                         return 1;
 284         } END_FOR_EACH_PTR(tmp);
 285         return 0;
 286 }
 287 
 288 /*
 289  * separate_pools():
 290  * Example code:  if (foo == 99) {
 291  *
 292  * Say 'foo' is a merged state that has many possible values.  It is the combination
 293  * of merges.  separate_pools() iterates through the pools recursively and calls
 294  * do_compare() for each time 'foo' was set.
 295  */
 296 static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
 297                         struct state_list **true_stack,
 298                         struct state_list **maybe_stack,
 299                         struct state_list **false_stack,
 300                         struct state_list **checked, int *mixed, struct sm_state *gate_sm,
 301                         struct timeval *start_time)
 302 {
 303         int free_checked = 0;
 304         struct state_list *checked_states = NULL;
 305         struct timeval now, diff;
 306 
 307         if (!sm)
 308                 return;
 309 
 310         gettimeofday(&now, NULL);
 311         timersub(&now, start_time, &diff);
 312         if (diff.tv_sec >= 1) {
 313                 if (implied_debug) {
 314                         sm_msg("debug: %s: implications taking too long.  (%s %s %s)",
 315                                __func__, sm->state->name, show_special(comparison), show_rl(rl));
 316                 }
 317                 if (mixed)
 318                         *mixed = 1;
 319         }
 320 
 321         if (checked == NULL) {
 322                 checked = &checked_states;
 323                 free_checked = 1;
 324         }
 325         if (is_checked(*checked, sm))
 326                 return;
 327         add_ptr_list(checked, sm);
 328 
 329         do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
 330 
 331         __separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
 332         __separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
 333         if (free_checked)
 334                 free_slist(checked);
 335 }
 336 
 337 static void separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
 338                         struct state_list **true_stack,
 339                         struct state_list **false_stack,
 340                         struct state_list **checked, int *mixed)
 341 {
 342         struct state_list *maybe_stack = NULL;
 343         struct sm_state *tmp;
 344         struct timeval start_time;
 345 
 346 
 347         gettimeofday(&start_time, NULL);
 348         __separate_pools(sm, comparison, rl, true_stack, &maybe_stack, false_stack, checked, mixed, sm, &start_time);
 349 
 350         if (implied_debug) {
 351                 struct sm_state *sm;
 352 
 353                 FOR_EACH_PTR(*true_stack, sm) {
 354                         sm_msg("TRUE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
 355                 } END_FOR_EACH_PTR(sm);
 356 
 357                 FOR_EACH_PTR(maybe_stack, sm) {
 358                         sm_msg("MAYBE %s %s[stree %d]",
 359                                show_sm(sm), sm->merged ? "(merged) ": "", get_stree_id(sm->pool));
 360                 } END_FOR_EACH_PTR(sm);
 361 
 362                 FOR_EACH_PTR(*false_stack, sm) {
 363                         sm_msg("FALSE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
 364                 } END_FOR_EACH_PTR(sm);
 365         }
 366         /* if it's a maybe then remove it */
 367         FOR_EACH_PTR(maybe_stack, tmp) {
 368                 remove_pool(false_stack, tmp->pool);
 369                 remove_pool(true_stack, tmp->pool);
 370         } END_FOR_EACH_PTR(tmp);
 371 
 372         /* if it's both true and false remove it from both */
 373         FOR_EACH_PTR(*true_stack, tmp) {
 374                 if (remove_pool(false_stack, tmp->pool))
 375                         DELETE_CURRENT_PTR(tmp);
 376         } END_FOR_EACH_PTR(tmp);
 377 }
 378 
 379 static int sm_in_keep_leafs(struct sm_state *sm, const struct state_list *keep_gates)
 380 {
 381         struct sm_state *tmp, *old;
 382 
 383         FOR_EACH_PTR(keep_gates, tmp) {
 384                 if (is_merged(tmp))
 385                         continue;
 386                 old = get_sm_state_stree(tmp->pool, sm->owner, sm->name, sm->sym);
 387                 if (!old)
 388                         continue;
 389                 if (old == sm)
 390                         return 1;
 391         } END_FOR_EACH_PTR(tmp);
 392         return 0;
 393 }
 394 
 395 static int going_too_slow(void)
 396 {
 397         static void *printed;
 398 
 399         if (out_of_memory()) {
 400                 implications_off = true;
 401                 return 1;
 402         }
 403 
 404         if (!option_timeout || time_parsing_function() < option_timeout) {
 405                 implications_off = false;
 406                 return 0;
 407         }
 408 
 409         if (!__inline_fn && printed != cur_func_sym) {
 410                 if (!is_skipped_function())
 411                         sm_perror("turning off implications after %d seconds", option_timeout);
 412                 printed = cur_func_sym;
 413         }
 414         implications_off = true;
 415         return 1;
 416 }
 417 
 418 static char *sm_state_info(struct sm_state *sm)
 419 {
 420         static char buf[512];
 421         int n = 0;
 422 
 423         n += snprintf(buf + n, sizeof(buf) - n, "[stree %d line %d] ",
 424                       get_stree_id(sm->pool),  sm->line);
 425         if (n >= sizeof(buf))
 426                 return buf;
 427         n += snprintf(buf + n, sizeof(buf) - n, "%s ", show_sm(sm));
 428         if (n >= sizeof(buf))
 429                 return buf;
 430         n += snprintf(buf + n, sizeof(buf) - n, "left = %s [stree %d] ",
 431                       sm->left ? sm->left->state->name : "<none>",
 432                       sm->left ? get_stree_id(sm->left->pool) : -1);
 433         if (n >= sizeof(buf))
 434                 return buf;
 435         n += snprintf(buf + n, sizeof(buf) - n, "right = %s [stree %d]",
 436                       sm->right ? sm->right->state->name : "<none>",
 437                       sm->right ? get_stree_id(sm->right->pool) : -1);
 438         return buf;
 439 }
 440 
 441 /*
 442  * NOTE: If a state is in both the keep stack and the remove stack then that is
 443  * a bug.  Only add states which are definitely true or definitely false.  If
 444  * you have a leaf state that could be both true and false, then create a fake
 445  * split history where one side is true and one side is false.  Otherwise, if
 446  * you can't do that, then don't add it to either list.
 447  */
 448 #define RECURSE_LIMIT 300
 449 struct sm_state *filter_pools(struct sm_state *sm,
 450                               const struct state_list *remove_stack,
 451                               const struct state_list *keep_stack,
 452                               int *modified, int *recurse_cnt,
 453                               struct timeval *start, int *skip, int *bail)
 454 {
 455         struct sm_state *ret = NULL;
 456         struct sm_state *left;
 457         struct sm_state *right;
 458         int removed = 0;
 459         struct timeval now, diff;
 460 
 461         if (!sm)
 462                 return NULL;
 463         if (*bail)
 464                 return NULL;
 465         gettimeofday(&now, NULL);
 466         timersub(&now, start, &diff);
 467         if (diff.tv_sec >= 3) {
 468                 DIMPLIED("%s: implications taking too long: %s\n", __func__, sm_state_info(sm));
 469                 *bail = 1;
 470                 return NULL;
 471         }
 472         if ((*recurse_cnt)++ > RECURSE_LIMIT) {
 473                 DIMPLIED("%s: recursed too far:  %s\n", __func__, sm_state_info(sm));
 474                 *skip = 1;
 475                 return NULL;
 476         }
 477 
 478         if (pool_in_pools(sm->pool, remove_stack)) {
 479                 DIMPLIED("%s: remove: %s\n", __func__, sm_state_info(sm));
 480                 *modified = 1;
 481                 return NULL;
 482         }
 483 
 484         if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack) || sm_in_keep_leafs(sm, keep_stack)) {
 485                 DIMPLIED("%s: keep %s (%s, %s, %s): %s\n", __func__, sm->state->name,
 486                         is_merged(sm) ? "merged" : "not merged",
 487                         pool_in_pools(sm->pool, keep_stack) ? "not in keep pools" : "in keep pools",
 488                         sm_in_keep_leafs(sm, keep_stack) ? "reachable keep leaf" : "no keep leaf",
 489                         sm_state_info(sm));
 490                 return sm;
 491         }
 492 
 493         left = filter_pools(sm->left, remove_stack, keep_stack, &removed, recurse_cnt, start, skip, bail);
 494         right = filter_pools(sm->right, remove_stack, keep_stack, &removed, recurse_cnt, start, skip, bail);
 495         if (*bail || *skip)
 496                 return NULL;
 497         if (!removed) {
 498                 DIMPLIED("%s: kept all: %s\n", __func__, sm_state_info(sm));
 499                 return sm;
 500         }
 501         *modified = 1;
 502         if (!left && !right) {
 503                 DIMPLIED("%s: removed all: %s\n", __func__, sm_state_info(sm));
 504                 return NULL;
 505         }
 506 
 507         if (!left) {
 508                 ret = clone_sm(right);
 509                 ret->merged = 1;
 510                 ret->right = right;
 511                 ret->left = NULL;
 512         } else if (!right) {
 513                 ret = clone_sm(left);
 514                 ret->merged = 1;
 515                 ret->left = left;
 516                 ret->right = NULL;
 517         } else {
 518                 if (left->sym != sm->sym || strcmp(left->name, sm->name) != 0) {
 519                         left = clone_sm(left);
 520                         left->sym = sm->sym;
 521                         left->name = sm->name;
 522                 }
 523                 if (right->sym != sm->sym || strcmp(right->name, sm->name) != 0) {
 524                         right = clone_sm(right);
 525                         right->sym = sm->sym;
 526                         right->name = sm->name;
 527                 }
 528                 ret = merge_sm_states(left, right);
 529         }
 530 
 531         ret->pool = sm->pool;
 532 
 533         DIMPLIED("%s: partial: %s\n", __func__, sm_state_info(sm));
 534         return ret;
 535 }
 536 
 537 static struct stree *filter_stack(struct sm_state *gate_sm,
 538                                        struct stree *pre_stree,
 539                                        const struct state_list *remove_stack,
 540                                        const struct state_list *keep_stack)
 541 {
 542         struct stree *ret = NULL;
 543         struct sm_state *tmp;
 544         struct sm_state *filtered_sm;
 545         int modified;
 546         int recurse_cnt;
 547         struct timeval start;
 548         int skip;
 549         int bail = 0;
 550 
 551         if (!remove_stack)
 552                 return NULL;
 553 
 554         gettimeofday(&start, NULL);
 555         FOR_EACH_SM(pre_stree, tmp) {
 556                 if (!tmp->merged || sm_in_keep_leafs(tmp, keep_stack))
 557                         continue;
 558                 modified = 0;
 559                 recurse_cnt = 0;
 560                 skip = 0;
 561                 filtered_sm = filter_pools(tmp, remove_stack, keep_stack, &modified, &recurse_cnt, &start, &skip, &bail);
 562                 if (going_too_slow())
 563                         return NULL;
 564                 if (bail)
 565                         return ret;  /* Return the implications we figured out before time ran out. */
 566 
 567 
 568                 if (skip || !filtered_sm || !modified)
 569                         continue;
 570                 /* the assignments here are for borrowed implications */
 571                 filtered_sm->name = tmp->name;
 572                 filtered_sm->sym = tmp->sym;
 573                 avl_insert(&ret, filtered_sm);
 574         } END_FOR_EACH_SM(tmp);
 575         return ret;
 576 }
 577 
 578 static void separate_and_filter(struct sm_state *sm, int comparison, struct range_list *rl,
 579                 struct stree *pre_stree,
 580                 struct stree **true_states,
 581                 struct stree **false_states,
 582                 int *mixed)
 583 {
 584         struct state_list *true_stack = NULL;
 585         struct state_list *false_stack = NULL;
 586         struct timeval time_before;
 587         struct timeval time_after;
 588         int sec;
 589 
 590         gettimeofday(&time_before, NULL);
 591 
 592         DIMPLIED("checking implications: (%s (%s) %s %s)\n",
 593                  sm->name, sm->state->name, show_special(comparison), show_rl(rl));
 594 
 595         if (!is_merged(sm)) {
 596                 DIMPLIED("%d '%s' from line %d is not merged.\n", get_lineno(), sm->name, sm->line);
 597                 return;
 598         }
 599 
 600         separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
 601 
 602         DIMPLIED("filtering true stack.\n");
 603         *true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
 604         DIMPLIED("filtering false stack.\n");
 605         *false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
 606         free_slist(&true_stack);
 607         free_slist(&false_stack);
 608 
 609         gettimeofday(&time_after, NULL);
 610         sec = time_after.tv_sec - time_before.tv_sec;
 611         if (option_timeout && sec > option_timeout) {
 612                 sm_perror("Function too hairy.  Ignoring implications after %d seconds.", sec);
 613         }
 614 }
 615 
 616 static struct expression *get_last_expr(struct statement *stmt)
 617 {
 618         struct statement *last;
 619 
 620         last = last_ptr_list((struct ptr_list *)stmt->stmts);
 621         if (last->type == STMT_EXPRESSION)
 622                 return last->expression;
 623 
 624         if (last->type == STMT_LABEL) {
 625                 if (last->label_statement &&
 626                     last->label_statement->type == STMT_EXPRESSION)
 627                         return last->label_statement->expression;
 628         }
 629 
 630         return NULL;
 631 }
 632 
 633 static struct expression *get_left_most_expr(struct expression *expr)
 634 {
 635         struct statement *compound;
 636 
 637         compound = get_expression_statement(expr);
 638         if (compound)
 639                 return get_last_expr(compound);
 640 
 641         expr = strip_parens(expr);
 642         if (expr->type == EXPR_ASSIGNMENT)
 643                 return get_left_most_expr(expr->left);
 644         return expr;
 645 }
 646 
 647 static int is_merged_expr(struct expression  *expr)
 648 {
 649         struct sm_state *sm;
 650         sval_t dummy;
 651 
 652         if (get_value(expr, &dummy))
 653                 return 0;
 654         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 655         if (!sm)
 656                 return 0;
 657         if (is_merged(sm))
 658                 return 1;
 659         return 0;
 660 }
 661 
 662 static void delete_gate_sm_equiv(struct stree **stree, const char *name, struct symbol *sym)
 663 {
 664         struct smatch_state *state;
 665         struct relation *rel;
 666 
 667         state = get_state(SMATCH_EXTRA, name, sym);
 668         if (!state)
 669                 return;
 670         FOR_EACH_PTR(estate_related(state), rel) {
 671                 delete_state_stree(stree, SMATCH_EXTRA, rel->name, rel->sym);
 672         } END_FOR_EACH_PTR(rel);
 673 }
 674 
 675 static void delete_gate_sm(struct stree **stree, const char *name, struct symbol *sym)
 676 {
 677         delete_state_stree(stree, SMATCH_EXTRA, name, sym);
 678 }
 679 
 680 static int handle_comparison(struct expression *expr,
 681                               struct stree **implied_true,
 682                               struct stree **implied_false)
 683 {
 684         struct sm_state *sm = NULL;
 685         struct range_list *rl = NULL;
 686         struct expression *left;
 687         struct expression *right;
 688         struct symbol *type;
 689         int comparison = expr->op;
 690         int mixed = 0;
 691 
 692         left = get_left_most_expr(expr->left);
 693         right = get_left_most_expr(expr->right);
 694 
 695         if (is_merged_expr(left)) {
 696                 sm = get_sm_state_expr(SMATCH_EXTRA, left);
 697                 get_implied_rl(right, &rl);
 698         } else if (is_merged_expr(right)) {
 699                 sm = get_sm_state_expr(SMATCH_EXTRA, right);
 700                 get_implied_rl(left, &rl);
 701                 comparison = flip_comparison(comparison);
 702         }
 703 
 704         if (!rl || !sm)
 705                 return 0;
 706 
 707         type = get_type(expr);
 708         if (!type)
 709                 return 0;
 710         if (type_positive_bits(rl_type(rl)) > type_positive_bits(type))
 711                 type = rl_type(rl);
 712         if (type_positive_bits(type) < 31)
 713                 type = &int_ctype;
 714         rl = cast_rl(type, rl);
 715 
 716         separate_and_filter(sm, comparison, rl, __get_cur_stree(), implied_true, implied_false, &mixed);
 717 
 718         delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
 719         delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
 720         if (mixed) {
 721                 delete_gate_sm(implied_true, sm->name, sm->sym);
 722                 delete_gate_sm(implied_false, sm->name, sm->sym);
 723         }
 724 
 725         return 1;
 726 }
 727 
 728 static int handle_zero_comparison(struct expression *expr,
 729                                 struct stree **implied_true,
 730                                 struct stree **implied_false)
 731 {
 732         struct symbol *sym;
 733         char *name;
 734         struct sm_state *sm;
 735         int mixed = 0;
 736         int ret = 0;
 737 
 738         if (expr->type == EXPR_POSTOP)
 739                 expr = strip_expr(expr->unop);
 740 
 741         if (expr->type == EXPR_ASSIGNMENT) {
 742                 /* most of the time ->pools will be empty here because we
 743                    just set the state, but if have assigned a conditional
 744                    function there are implications. */
 745                 expr = expr->left;
 746         }
 747 
 748         name = expr_to_var_sym(expr, &sym);
 749         if (!name || !sym)
 750                 goto free;
 751         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 752         if (!sm)
 753                 goto free;
 754 
 755         separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(estate_type(sm->state), 0), __get_cur_stree(), implied_true, implied_false, &mixed);
 756         delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
 757         delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
 758         if (mixed) {
 759                 delete_gate_sm(implied_true, sm->name, sm->sym);
 760                 delete_gate_sm(implied_false, sm->name, sm->sym);
 761         }
 762 
 763         ret = 1;
 764 free:
 765         free_string(name);
 766         return ret;
 767 }
 768 
 769 static int handled_by_comparison_hook(struct expression *expr,
 770                                    struct stree **implied_true,
 771                                    struct stree **implied_false)
 772 {
 773         struct state_list *true_stack = NULL;
 774         struct state_list *false_stack = NULL;
 775         struct stree *pre_stree;
 776         struct sm_state *sm;
 777 
 778         sm = comparison_implication_hook(expr, &true_stack, &false_stack);
 779         if (!sm)
 780                 return 0;
 781 
 782         pre_stree = clone_stree(__get_cur_stree());
 783 
 784         *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
 785         *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
 786 
 787         free_stree(&pre_stree);
 788         free_slist(&true_stack);
 789         free_slist(&false_stack);
 790 
 791         return 1;
 792 }
 793 
 794 static int handled_by_extra_states(struct expression *expr,
 795                                    struct stree **implied_true,
 796                                    struct stree **implied_false)
 797 {
 798         sval_t sval;
 799 
 800         /* If the expression is known then it has no implications.  */
 801         if (get_implied_value(expr, &sval))
 802                 return true;
 803 
 804         if (expr->type == EXPR_COMPARE)
 805                 return handle_comparison(expr, implied_true, implied_false);
 806         else
 807                 return handle_zero_comparison(expr, implied_true, implied_false);
 808 }
 809 

























 810 static int handled_by_stored_conditions(struct expression *expr,
 811                                         struct stree **implied_true,
 812                                         struct stree **implied_false)
 813 {
 814         struct state_list *true_stack = NULL;
 815         struct state_list *false_stack = NULL;
 816         struct stree *pre_stree;
 817         struct sm_state *sm;
 818 
 819         sm = stored_condition_implication_hook(expr, &true_stack, &false_stack);
 820         if (!sm)
 821                 return 0;
 822 
 823         pre_stree = clone_stree(__get_cur_stree());
 824 
 825         *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
 826         *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
 827 
 828         free_stree(&pre_stree);
 829         free_slist(&true_stack);
 830         free_slist(&false_stack);
 831 
 832         return 1;
 833 }
 834 
 835 static struct stree *saved_implied_true;
 836 static struct stree *saved_implied_false;
 837 static struct stree *extra_saved_implied_true;
 838 static struct stree *extra_saved_implied_false;
 839 
 840 static void separate_extra_states(struct stree **implied_true,
 841                                   struct stree **implied_false)

 842 {
 843         struct sm_state *sm;
 844 
 845         /* We process extra states later to preserve the implications. */
 846         FOR_EACH_SM(*implied_true, sm) {
 847                 if (sm->owner == SMATCH_EXTRA)
 848                         overwrite_sm_state_stree(&extra_saved_implied_true, sm);
 849         } END_FOR_EACH_SM(sm);
 850         FOR_EACH_SM(extra_saved_implied_true, sm) {
 851                 delete_state_stree(implied_true, sm->owner, sm->name, sm->sym);
 852         } END_FOR_EACH_SM(sm);
 853 
 854         FOR_EACH_SM(*implied_false, sm) {
 855                 if (sm->owner == SMATCH_EXTRA)
 856                         overwrite_sm_state_stree(&extra_saved_implied_false, sm);
 857         } END_FOR_EACH_SM(sm);
 858         FOR_EACH_SM(extra_saved_implied_false, sm) {
 859                 delete_state_stree(implied_false, sm->owner, sm->name, sm->sym);
 860         } END_FOR_EACH_SM(sm);
 861 }
 862 
 863 static void get_tf_states(struct expression *expr,
 864                           struct stree **implied_true,
 865                           struct stree **implied_false)
 866 {
 867         if (handled_by_comparison_hook(expr, implied_true, implied_false))
 868                 return;
 869 





 870         if (handled_by_extra_states(expr, implied_true, implied_false)) {
 871                 separate_extra_states(implied_true, implied_false);
 872                 return;
 873         }
 874 
 875         if (handled_by_stored_conditions(expr, implied_true, implied_false))
 876                 return;
 877 }
 878 
 879 static void save_implications_hook(struct expression *expr)
 880 {
 881         if (going_too_slow())
 882                 return;
 883         get_tf_states(expr, &saved_implied_true, &saved_implied_false);
 884 }
 885 
 886 static void set_implied_states(struct expression *expr)
 887 {
 888         struct sm_state *sm;
 889 
 890         if (implied_debug &&
 891             (expr || saved_implied_true || saved_implied_false)) {
 892                 char *name;
 893 
 894                 name = expr_to_str(expr);
 895                 printf("These are the implied states for the true path: (%s)\n", name);
 896                 __print_stree(saved_implied_true);
 897                 printf("These are the implied states for the false path: (%s)\n", name);
 898                 __print_stree(saved_implied_false);
 899                 free_string(name);
 900         }
 901 
 902         FOR_EACH_SM(saved_implied_true, sm) {
 903                 __set_true_false_sm(sm, NULL);
 904         } END_FOR_EACH_SM(sm);
 905         free_stree(&saved_implied_true);
 906 
 907         FOR_EACH_SM(saved_implied_false, sm) {
 908                 __set_true_false_sm(NULL, sm);
 909         } END_FOR_EACH_SM(sm);
 910         free_stree(&saved_implied_false);
 911 }
 912 
 913 static void set_extra_implied_states(struct expression *expr)
 914 {
 915         saved_implied_true = extra_saved_implied_true;
 916         saved_implied_false = extra_saved_implied_false;
 917         extra_saved_implied_true = NULL;
 918         extra_saved_implied_false = NULL;
 919         set_implied_states(NULL);
 920 }
 921 
 922 void param_limit_implications(struct expression *expr, int param, char *key, char *value)
 923 {
 924         struct expression *arg;
 925         struct symbol *compare_type;
 926         char *name;
 927         struct symbol *sym;
 928         struct sm_state *sm;
 929         struct sm_state *tmp;
 930         struct stree *implied_true = NULL;
 931         struct stree *implied_false = NULL;
 932         struct range_list *orig, *limit;
 933 
 934         if (time_parsing_function() > 40)
 935                 return;
 936 
 937         while (expr->type == EXPR_ASSIGNMENT)
 938                 expr = strip_expr(expr->right);
 939         if (expr->type != EXPR_CALL)
 940                 return;
 941 
 942         arg = get_argument_from_call_expr(expr->args, param);
 943         if (!arg)
 944                 return;
 945 
 946         arg = strip_parens(arg);
 947         while (arg->type == EXPR_ASSIGNMENT && arg->op == '=')
 948                 arg = strip_parens(arg->left);
 949 
 950         name = get_variable_from_key(arg, key, &sym);
 951         if (!name || !sym)
 952                 goto free;
 953 
 954         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 955         if (!sm || !sm->merged)
 956                 goto free;
 957 
 958         if (strcmp(key, "$") == 0)
 959                 compare_type = get_arg_type(expr->fn, param);
 960         else
 961                 compare_type = get_member_type_from_key(arg, key);
 962 
 963         orig = estate_rl(sm->state);
 964         orig = cast_rl(compare_type, orig);
 965 
 966         call_results_to_rl(expr, compare_type, value, &limit);
 967 
 968         separate_and_filter(sm, SPECIAL_EQUAL, limit, __get_cur_stree(), &implied_true, &implied_false, NULL);
 969 
 970         FOR_EACH_SM(implied_true, tmp) {
 971                 __set_sm_fake_stree(tmp);
 972         } END_FOR_EACH_SM(tmp);
 973 
 974         free_stree(&implied_true);
 975         free_stree(&implied_false);
 976 free:
 977         free_string(name);
 978 }
 979 
 980 struct stree *__implied_case_stree(struct expression *switch_expr,
 981                                    struct range_list *rl,
 982                                    struct range_list_stack **remaining_cases,
 983                                    struct stree **raw_stree)
 984 {
 985         char *name;
 986         struct symbol *sym;
 987         struct var_sym_list *vsl;
 988         struct sm_state *sm;
 989         struct stree *true_states = NULL;
 990         struct stree *false_states = NULL;
 991         struct stree *extra_states;
 992         struct stree *ret = clone_stree(*raw_stree);
 993 
 994         name = expr_to_chunk_sym_vsl(switch_expr, &sym, &vsl);
 995 
 996         if (rl)
 997                 filter_top_rl(remaining_cases, rl);
 998         else
 999                 rl = clone_rl(top_rl(*remaining_cases));
1000 
1001         if (name) {
1002                 sm = get_sm_state_stree(*raw_stree, SMATCH_EXTRA, name, sym);
1003                 if (sm)
1004                         separate_and_filter(sm, SPECIAL_EQUAL, rl, *raw_stree, &true_states, &false_states, NULL);
1005         }
1006 
1007         __push_fake_cur_stree();
1008         __unnullify_path();
1009         if (name)
1010                 set_extra_nomod_vsl(name, sym, vsl, NULL, alloc_estate_rl(rl));
1011         __pass_case_to_client(switch_expr, rl);
1012         extra_states = __pop_fake_cur_stree();
1013         overwrite_stree(extra_states, &true_states);
1014         overwrite_stree(true_states, &ret);
1015         free_stree(&extra_states);
1016         free_stree(&true_states);
1017         free_stree(&false_states);
1018 
1019         free_string(name);
1020         return ret;
1021 }
1022 
1023 static void match_end_func(struct symbol *sym)
1024 {
1025         if (__inline_fn)
1026                 return;
1027         implied_debug_msg = NULL;
1028 }
1029 
1030 static void get_tf_stacks_from_pool(struct sm_state *gate_sm,
1031                                     struct sm_state *pool_sm,
1032                                     struct state_list **true_stack,
1033                                     struct state_list **false_stack)
1034 {
1035         struct sm_state *tmp;
1036         int possibly_true = 0;
1037 
1038         if (!gate_sm)
1039                 return;
1040 
1041         if (strcmp(gate_sm->state->name, pool_sm->state->name) == 0) {
1042                 add_ptr_list(true_stack, pool_sm);
1043                 return;
1044         }
1045 
1046         FOR_EACH_PTR(gate_sm->possible, tmp) {
1047                 if (strcmp(tmp->state->name, pool_sm->state->name) == 0) {
1048                         possibly_true = 1;
1049                         break;
1050                 }
1051         } END_FOR_EACH_PTR(tmp);
1052 
1053         if (!possibly_true) {
1054                 add_ptr_list(false_stack, gate_sm);
1055                 return;
1056         }
1057 
1058         get_tf_stacks_from_pool(gate_sm->left, pool_sm, true_stack, false_stack);
1059         get_tf_stacks_from_pool(gate_sm->right, pool_sm, true_stack, false_stack);
1060 }
1061 
1062 /*
1063  * The situation is we have a SMATCH_EXTRA state and we want to break it into
1064  * each of the ->possible states and find the implications of each.  The caller
1065  * has to use __push_fake_cur_stree() to preserve the correct states so they
1066  * can be restored later.
1067  */
1068 void overwrite_states_using_pool(struct sm_state *gate_sm, struct sm_state *pool_sm)
1069 {
1070         struct state_list *true_stack = NULL;
1071         struct state_list *false_stack = NULL;
1072         struct stree *pre_stree;
1073         struct stree *implied_true;
1074         struct sm_state *tmp;
1075 
1076         if (!pool_sm->pool)
1077                 return;
1078 
1079         get_tf_stacks_from_pool(gate_sm, pool_sm, &true_stack, &false_stack);
1080 
1081         pre_stree = clone_stree(__get_cur_stree());
1082 
1083         implied_true = filter_stack(gate_sm, pre_stree, false_stack, true_stack);
1084 
1085         free_stree(&pre_stree);
1086         free_slist(&true_stack);
1087         free_slist(&false_stack);
1088 
1089         FOR_EACH_SM(implied_true, tmp) {
1090                 set_state(tmp->owner, tmp->name, tmp->sym, tmp->state);
1091         } END_FOR_EACH_SM(tmp);
1092 
1093         free_stree(&implied_true);
1094 }
1095 
1096 int assume(struct expression *expr)
1097 {
1098         int orig_final_pass = final_pass;
1099 
1100         in_fake_env++;
1101         final_pass = 0;
1102         __push_fake_cur_stree();
1103         __split_whole_condition(expr);
1104         final_pass = orig_final_pass;
1105         in_fake_env--;
1106 
1107         return 1;
1108 }
1109 
1110 void end_assume(void)
1111 {
1112         __discard_false_states();
1113         __free_fake_cur_stree();
1114 }
1115 
1116 int impossible_assumption(struct expression *left, int op, sval_t sval)
1117 {
1118         struct expression *value;
1119         struct expression *comparison;
1120         int ret;
1121 
1122         value = value_expr(sval.value);
1123         comparison = compare_expression(left, op, value);
1124 
1125         if (!assume(comparison))
1126                 return 0;
1127         ret = is_impossible_path();
1128         end_assume();
1129 
1130         return ret;
1131 }
1132 
1133 void __extra_match_condition(struct expression *expr);
1134 void __comparison_match_condition(struct expression *expr);
1135 void __stored_condition(struct expression *expr);
1136 void register_implications(int id)
1137 {
1138         add_hook(&save_implications_hook, CONDITION_HOOK);
1139         add_hook(&set_implied_states, CONDITION_HOOK);
1140         add_hook(&__extra_match_condition, CONDITION_HOOK);
1141         add_hook(&set_extra_implied_states, CONDITION_HOOK);
1142         add_hook(&__comparison_match_condition, CONDITION_HOOK);

1143         add_hook(&__stored_condition, CONDITION_HOOK);
1144         add_hook(&match_end_func, END_FUNC_HOOK);
1145 }
--- EOF ---