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 
  18 /*
  19  * Imagine we have this code:
  20  * foo = 1;
  21  * if (bar)
  22  *         foo = 99;
  23  * else
  24  *         frob();
  25  *                   //  <-- point #1
  26  * if (foo == 99)    //  <-- point #2
  27  *         bar->baz; //  <-- point #3
  28  *
  29  *
  30  * At point #3 bar is non null and can be dereferenced.
  31  *
  32  * It's smatch_implied.c which sets bar to non null at point #2.
  33  *
  34  * At point #1 merge_slist() stores the list of states from both
  35  * the true and false paths.  On the true path foo == 99 and on
  36  * the false path foo == 1.  merge_slist() sets their pool
  37  * list to show the other states which were there when foo == 99.
  38  *
  39  * When it comes to the if (foo == 99) the smatch implied hook
  40  * looks for all the pools where foo was not 99.  It makes a list
  41  * of those.
  42  *
  43  * Then for bar (and all the other states) it says, ok bar is a
  44  * merged state that came from these previous states.  We'll
  45  * chop out all the states where it came from a pool where
  46  * foo != 99 and merge it all back together.
  47  *
  48  * That is the implied state of bar.
  49  *
  50  * merge_slist() sets up ->pool.  An sm_state only has one ->pool and
  51  *    that is the pool where it was first set.  The my pool gets set when
  52  *    code paths merge.  States that have been set since the last merge do
  53  *    not have a ->pool.
  54  * merge_sm_state() sets ->left and ->right.  (These are the states which were
  55  *    merged to form the current state.)
  56  * a pool:  a pool is an slist that has been merged with another slist.
  57  */
  58 
  59 #include <sys/time.h>
  60 #include <time.h>
  61 #include "smatch.h"
  62 #include "smatch_slist.h"
  63 #include "smatch_extra.h"
  64 
  65 char *implied_debug_msg;
  66 #define DIMPLIED(msg...) do { if (option_debug_implied || option_debug) printf(msg); } while (0)
  67 
  68 int option_debug_implied = 0;
  69 
  70 /*
  71  * tmp_range_list():
  72  * It messes things up to free range list allocations.  This helper fuction
  73  * lets us reuse memory instead of doing new allocations.
  74  */
  75 static struct range_list *tmp_range_list(struct symbol *type, long long num)
  76 {
  77         static struct range_list *my_list = NULL;
  78         static struct data_range *my_range;
  79 
  80         __free_ptr_list((struct ptr_list **)&my_list);
  81         my_range = alloc_range(ll_to_sval(num), ll_to_sval(num));
  82         add_ptr_list(&my_list, my_range);
  83         return my_list;
  84 }
  85 
  86 static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
  87 {
  88         if (!option_debug_implied && !option_debug)
  89                 return;
  90 
  91         if (istrue && isfalse) {
  92                 printf("%s: %d: does not exist.\n", show_sm(sm), sm->line);
  93         } else if (istrue) {
  94                 printf("'%s = %s' from %d is true. %s[stree %d]\n", sm->name, show_state(sm->state),
  95                         sm->line, sm->merged ? "[merged]" : "[leaf]",
  96                         get_stree_id(sm->pool));
  97         } else if (isfalse) {
  98                 printf("'%s = %s' from %d is false. %s[stree %d]\n", sm->name, show_state(sm->state),
  99                         sm->line,
 100                         sm->merged ? "[merged]" : "[leaf]",
 101                         get_stree_id(sm->pool));
 102         } else {
 103                 printf("'%s = %s' from %d could be true or false. %s[stree %d]\n", sm->name,
 104                         show_state(sm->state), sm->line,
 105                         sm->merged ? "[merged]" : "[leaf]",
 106                         get_stree_id(sm->pool));
 107         }
 108 }
 109 
 110 static int create_fake_history(struct sm_state *sm, int comparison, struct range_list *rl)
 111 {
 112         struct range_list *orig_rl;
 113         struct range_list *true_rl, *false_rl;
 114         struct stree *true_stree, *false_stree;
 115         struct sm_state *true_sm, *false_sm;
 116         sval_t sval;
 117 
 118         if (is_merged(sm) || sm->left || sm->right)
 119                 return 0;
 120         if (!rl_to_sval(rl, &sval))
 121                 return 0;
 122         if (!estate_rl(sm->state))
 123                 return 0;
 124 
 125         orig_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
 126         split_comparison_rl(orig_rl, comparison, rl, &true_rl, &false_rl, NULL, NULL);
 127 
 128         true_rl = rl_truncate_cast(estate_type(sm->state), true_rl);
 129         false_rl = rl_truncate_cast(estate_type(sm->state), false_rl);
 130         if (is_whole_rl(true_rl) || is_whole_rl(false_rl) ||
 131             !true_rl || !false_rl ||
 132             rl_equiv(orig_rl, true_rl) || rl_equiv(orig_rl, false_rl) ||
 133             rl_equiv(estate_rl(sm->state), true_rl) || rl_equiv(estate_rl(sm->state), false_rl))
 134                 return 0;
 135 
 136         if (rl_intersection(true_rl, false_rl)) {
 137                 sm_perror("parsing (%s (%s) %s %s)",
 138                         sm->name, sm->state->name, show_special(comparison), show_rl(rl));
 139                 sm_msg("true_rl = %s false_rl = %s intersection = %s",
 140                        show_rl(true_rl), show_rl(false_rl), show_rl(rl_intersection(true_rl, false_rl)));
 141                 return 0;
 142         }
 143 
 144         if (option_debug)
 145                 sm_info("fake_history: %s vs %s.  %s %s %s. --> T: %s F: %s",
 146                        sm->name, show_rl(rl), sm->state->name, show_special(comparison), show_rl(rl),
 147                        show_rl(true_rl), show_rl(false_rl));
 148 
 149         true_sm = clone_sm(sm);
 150         false_sm = clone_sm(sm);
 151 
 152         true_sm->state = alloc_estate_rl(cast_rl(estate_type(sm->state), true_rl));
 153         free_slist(&true_sm->possible);
 154         add_possible_sm(true_sm, true_sm);
 155         false_sm->state = alloc_estate_rl(cast_rl(estate_type(sm->state), false_rl));
 156         free_slist(&false_sm->possible);
 157         add_possible_sm(false_sm, false_sm);
 158 
 159         true_stree = clone_stree(sm->pool);
 160         false_stree = clone_stree(sm->pool);
 161 
 162         overwrite_sm_state_stree(&true_stree, true_sm);
 163         overwrite_sm_state_stree(&false_stree, false_sm);
 164 
 165         true_sm->pool = true_stree;
 166         false_sm->pool = false_stree;
 167 
 168         sm->merged = 1;
 169         sm->left = true_sm;
 170         sm->right = false_sm;
 171 
 172         return 1;
 173 }
 174 
 175 /*
 176  * add_pool() adds a slist to *pools. If the slist has already been
 177  * added earlier then it doesn't get added a second time.
 178  */
 179 void add_pool(struct state_list **pools, struct sm_state *new)
 180 {
 181         struct sm_state *tmp;
 182 
 183         FOR_EACH_PTR(*pools, tmp) {
 184                 if (tmp->pool < new->pool)
 185                         continue;
 186                 else if (tmp->pool == new->pool) {
 187                         return;
 188                 } else {
 189                         INSERT_CURRENT(new, tmp);
 190                         return;
 191                 }
 192         } END_FOR_EACH_PTR(tmp);
 193         add_ptr_list(pools, new);
 194 }
 195 
 196 static int pool_in_pools(struct stree *pool,
 197                          const struct state_list *slist)
 198 {
 199         struct sm_state *tmp;
 200 
 201         FOR_EACH_PTR(slist, tmp) {
 202                 if (!tmp->pool)
 203                         continue;
 204                 if (tmp->pool == pool)
 205                         return 1;
 206         } END_FOR_EACH_PTR(tmp);
 207         return 0;
 208 }
 209 
 210 static int remove_pool(struct state_list **pools, struct stree *remove)
 211 {
 212         struct sm_state *tmp;
 213         int ret = 0;
 214 
 215         FOR_EACH_PTR(*pools, tmp) {
 216                 if (tmp->pool == remove) {
 217                         DELETE_CURRENT_PTR(tmp);
 218                         ret = 1;
 219                 }
 220         } END_FOR_EACH_PTR(tmp);
 221 
 222         return ret;
 223 }
 224 
 225 /*
 226  * If 'foo' == 99 add it that pool to the true pools.  If it's false, add it to
 227  * the false pools.  If we're not sure, then we don't add it to either.
 228  */
 229 static void do_compare(struct sm_state *sm, int comparison, struct range_list *rl,
 230                         struct state_list **true_stack,
 231                         struct state_list **maybe_stack,
 232                         struct state_list **false_stack,
 233                         int *mixed, struct sm_state *gate_sm)
 234 {
 235         int istrue;
 236         int isfalse;
 237         struct range_list *var_rl;
 238 
 239         if (!sm->pool)
 240                 return;
 241 
 242         var_rl = cast_rl(rl_type(rl), estate_rl(sm->state));
 243 
 244         istrue = !possibly_false_rl(var_rl, comparison, rl);
 245         isfalse = !possibly_true_rl(var_rl, comparison, rl);
 246 
 247         print_debug_tf(sm, istrue, isfalse);
 248 
 249         /* give up if we have borrowed implications (smatch_equiv.c) */
 250         if (sm->sym != gate_sm->sym ||
 251             strcmp(sm->name, gate_sm->name) != 0) {
 252                 if (mixed)
 253                         *mixed = 1;
 254         }
 255 
 256         if (mixed && !*mixed && !is_merged(sm) && !istrue && !isfalse) {
 257                 if (!create_fake_history(sm, comparison, rl))
 258                         *mixed = 1;
 259         }
 260 
 261         if (istrue)
 262                 add_pool(true_stack, sm);
 263         else if (isfalse)
 264                 add_pool(false_stack, sm);
 265         else
 266                 add_pool(maybe_stack, sm);
 267 
 268 }
 269 
 270 static int is_checked(struct state_list *checked, struct sm_state *sm)
 271 {
 272         struct sm_state *tmp;
 273 
 274         FOR_EACH_PTR(checked, tmp) {
 275                 if (tmp == sm)
 276                         return 1;
 277         } END_FOR_EACH_PTR(tmp);
 278         return 0;
 279 }
 280 
 281 /*
 282  * separate_pools():
 283  * Example code:  if (foo == 99) {
 284  *
 285  * Say 'foo' is a merged state that has many possible values.  It is the combination
 286  * of merges.  separate_pools() iterates through the pools recursively and calls
 287  * do_compare() for each time 'foo' was set.
 288  */
 289 static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
 290                         struct state_list **true_stack,
 291                         struct state_list **maybe_stack,
 292                         struct state_list **false_stack,
 293                         struct state_list **checked, int *mixed, struct sm_state *gate_sm)
 294 {
 295         int free_checked = 0;
 296         struct state_list *checked_states = NULL;
 297 
 298         if (!sm)
 299                 return;
 300 
 301         /*
 302          * If it looks like this is going to take too long as-is, then don't
 303          * create even more fake history.
 304          */
 305         if (mixed && sm->nr_children > 100)
 306                 *mixed = 1;
 307 
 308         /*
 309            Sometimes the implications are just too big to deal with
 310            so we bail.  Theoretically, bailing out here can cause more false
 311            positives but won't hide actual bugs.
 312         */
 313         if (sm->nr_children > 4000) {
 314                 if (option_debug || option_debug_implied) {
 315                         static char buf[1028];
 316                         snprintf(buf, sizeof(buf), "debug: %s: nr_children over 4000 (%d). (%s %s)",
 317                                  __func__, sm->nr_children, sm->name, show_state(sm->state));
 318                         implied_debug_msg = buf;
 319                 }
 320                 return;
 321         }
 322 
 323         if (checked == NULL) {
 324                 checked = &checked_states;
 325                 free_checked = 1;
 326         }
 327         if (is_checked(*checked, sm))
 328                 return;
 329         add_ptr_list(checked, sm);
 330 
 331         do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
 332 
 333         __separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm);
 334         __separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm);
 335         if (free_checked)
 336                 free_slist(checked);
 337 }
 338 
 339 static void separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
 340                         struct state_list **true_stack,
 341                         struct state_list **false_stack,
 342                         struct state_list **checked, int *mixed)
 343 {
 344         struct state_list *maybe_stack = NULL;
 345         struct sm_state *tmp;
 346 
 347         __separate_pools(sm, comparison, rl, true_stack, &maybe_stack, false_stack, checked, mixed, sm);
 348 
 349         if (option_debug) {
 350                 struct sm_state *sm;
 351 
 352                 FOR_EACH_PTR(*true_stack, sm) {
 353                         sm_msg("TRUE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
 354                 } END_FOR_EACH_PTR(sm);
 355 
 356                 FOR_EACH_PTR(maybe_stack, sm) {
 357                         sm_msg("MAYBE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
 358                 } END_FOR_EACH_PTR(sm);
 359 
 360                 FOR_EACH_PTR(*false_stack, sm) {
 361                         sm_msg("FALSE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
 362                 } END_FOR_EACH_PTR(sm);
 363         }
 364         /* if it's a maybe then remove it */
 365         FOR_EACH_PTR(maybe_stack, tmp) {
 366                 remove_pool(false_stack, tmp->pool);
 367                 remove_pool(true_stack, tmp->pool);
 368         } END_FOR_EACH_PTR(tmp);
 369 
 370         /* if it's both true and false remove it from both */
 371         FOR_EACH_PTR(*true_stack, tmp) {
 372                 if (remove_pool(false_stack, tmp->pool))
 373                         DELETE_CURRENT_PTR(tmp);
 374         } END_FOR_EACH_PTR(tmp);
 375 }
 376 
 377 static int sm_in_keep_leafs(struct sm_state *sm, const struct state_list *keep_gates)
 378 {
 379         struct sm_state *tmp, *old;
 380 
 381         FOR_EACH_PTR(keep_gates, tmp) {
 382                 if (is_merged(tmp))
 383                         continue;
 384                 old = get_sm_state_stree(tmp->pool, sm->owner, sm->name, sm->sym);
 385                 if (!old)
 386                         continue;
 387                 if (old == sm)
 388                         return 1;
 389         } END_FOR_EACH_PTR(tmp);
 390         return 0;
 391 }
 392 
 393 static int taking_too_long(void)
 394 {
 395         static void *printed;
 396 
 397         if (out_of_memory())
 398                 return 1;
 399 
 400         if (time_parsing_function() < 60)
 401                 return 0;
 402 
 403         if (!__inline_fn && printed != cur_func_sym) {
 404                 if (!is_skipped_function())
 405                         sm_perror("turning off implications after 60 seconds");
 406                 printed = cur_func_sym;
 407         }
 408         return 1;
 409 }
 410 
 411 /*
 412  * NOTE: If a state is in both the keep stack and the remove stack then that is
 413  * a bug.  Only add states which are definitely true or definitely false.  If
 414  * you have a leaf state that could be both true and false, then create a fake
 415  * split history where one side is true and one side is false.  Otherwise, if
 416  * you can't do that, then don't add it to either list.
 417  */
 418 struct sm_state *filter_pools(struct sm_state *sm,
 419                               const struct state_list *remove_stack,
 420                               const struct state_list *keep_stack,
 421                               int *modified, int *recurse_cnt,
 422                               struct timeval *start)
 423 {
 424         struct sm_state *ret = NULL;
 425         struct sm_state *left;
 426         struct sm_state *right;
 427         int removed = 0;
 428         struct timeval now;
 429 
 430         if (!sm)
 431                 return NULL;
 432         if (sm->skip_implications)
 433                 return sm;
 434         if (taking_too_long())
 435                 return sm;
 436 
 437         gettimeofday(&now, NULL);
 438         if ((*recurse_cnt)++ > 1000 || now.tv_sec - start->tv_sec > 5) {
 439                 if (local_debug || option_debug_implied) {
 440                         static char buf[1028];
 441                         snprintf(buf, sizeof(buf), "debug: %s: nr_children over 4000 (%d). (%s %s)",
 442                                  __func__, sm->nr_children, sm->name, show_state(sm->state));
 443                         implied_debug_msg = buf;
 444                 }
 445                 sm->skip_implications = 1;
 446                 return sm;
 447         }
 448 
 449         if (pool_in_pools(sm->pool, remove_stack)) {
 450                 DIMPLIED("removed [stree %d] %s from %d\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
 451                 *modified = 1;
 452                 return NULL;
 453         }
 454 
 455         if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack) || sm_in_keep_leafs(sm, keep_stack)) {
 456                 DIMPLIED("kept [stree %d] %s from %d. %s. %s. %s.\n", get_stree_id(sm->pool), show_sm(sm), sm->line,
 457                         is_merged(sm) ? "merged" : "not merged",
 458                         pool_in_pools(sm->pool, keep_stack) ? "not in keep pools" : "in keep pools",
 459                         sm_in_keep_leafs(sm, keep_stack) ? "reachable keep leaf" : "no keep leaf");
 460                 return sm;
 461         }
 462 
 463         DIMPLIED("checking [stree %d] %s from %d (%d) left = %s [stree %d] right = %s [stree %d]\n",
 464                  get_stree_id(sm->pool),
 465                  show_sm(sm), sm->line, sm->nr_children,
 466                  sm->left ? sm->left->state->name : "<none>", sm->left ? get_stree_id(sm->left->pool) : -1,
 467                  sm->right ? sm->right->state->name : "<none>", sm->right ? get_stree_id(sm->right->pool) : -1);
 468         left = filter_pools(sm->left, remove_stack, keep_stack, &removed, recurse_cnt, start);
 469         right = filter_pools(sm->right, remove_stack, keep_stack, &removed, recurse_cnt, start);
 470         if (!removed) {
 471                 DIMPLIED("kept [stree %d] %s from %d\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
 472                 return sm;
 473         }
 474         *modified = 1;
 475         if (!left && !right) {
 476                 DIMPLIED("removed [stree %d] %s from %d <none>\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
 477                 return NULL;
 478         }
 479 
 480         if (!left) {
 481                 ret = clone_sm(right);
 482                 ret->merged = 1;
 483                 ret->right = right;
 484                 ret->left = NULL;
 485         } else if (!right) {
 486                 ret = clone_sm(left);
 487                 ret->merged = 1;
 488                 ret->left = left;
 489                 ret->right = NULL;
 490         } else {
 491                 if (left->sym != sm->sym || strcmp(left->name, sm->name) != 0) {
 492                         left = clone_sm(left);
 493                         left->sym = sm->sym;
 494                         left->name = sm->name;
 495                 }
 496                 if (right->sym != sm->sym || strcmp(right->name, sm->name) != 0) {
 497                         right = clone_sm(right);
 498                         right->sym = sm->sym;
 499                         right->name = sm->name;
 500                 }
 501                 ret = merge_sm_states(left, right);
 502         }
 503 
 504         ret->pool = sm->pool;
 505 
 506         DIMPLIED("partial %s => ", show_sm(sm));
 507         DIMPLIED("%s from %d [stree %d]\n", show_sm(ret), sm->line, get_stree_id(sm->pool));
 508         return ret;
 509 }
 510 
 511 static struct stree *filter_stack(struct sm_state *gate_sm,
 512                                        struct stree *pre_stree,
 513                                        const struct state_list *remove_stack,
 514                                        const struct state_list *keep_stack)
 515 {
 516         struct stree *ret = NULL;
 517         struct sm_state *tmp;
 518         struct sm_state *filtered_sm;
 519         int modified;
 520         int recurse_cnt;
 521         struct timeval start;
 522 
 523         if (!remove_stack)
 524                 return NULL;
 525 
 526         if (taking_too_long())
 527                 return NULL;
 528 
 529         FOR_EACH_SM(pre_stree, tmp) {
 530                 if (option_debug)
 531                         sm_msg("%s: %s", __func__, show_sm(tmp));
 532                 if (!tmp->merged)
 533                         continue;
 534                 if (sm_in_keep_leafs(tmp, keep_stack))
 535                         continue;
 536                 modified = 0;
 537                 recurse_cnt = 0;
 538                 gettimeofday(&start, NULL);
 539                 filtered_sm = filter_pools(tmp, remove_stack, keep_stack, &modified, &recurse_cnt, &start);
 540                 if (!filtered_sm || !modified)
 541                         continue;
 542                 /* the assignments here are for borrowed implications */
 543                 filtered_sm->name = tmp->name;
 544                 filtered_sm->sym = tmp->sym;
 545                 avl_insert(&ret, filtered_sm);
 546                 if (out_of_memory() || taking_too_long())
 547                         return NULL;
 548 
 549         } END_FOR_EACH_SM(tmp);
 550         return ret;
 551 }
 552 
 553 static void separate_and_filter(struct sm_state *sm, int comparison, struct range_list *rl,
 554                 struct stree *pre_stree,
 555                 struct stree **true_states,
 556                 struct stree **false_states,
 557                 int *mixed)
 558 {
 559         struct state_list *true_stack = NULL;
 560         struct state_list *false_stack = NULL;
 561         struct timeval time_before;
 562         struct timeval time_after;
 563         int sec;
 564 
 565         gettimeofday(&time_before, NULL);
 566 
 567         if (!is_merged(sm)) {
 568                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm->name);
 569                 return;
 570         }
 571 
 572         if (option_debug_implied || option_debug) {
 573                 sm_msg("checking implications: (%s %s %s)",
 574                        sm->name, show_special(comparison), show_rl(rl));
 575         }
 576 
 577         separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
 578 
 579         DIMPLIED("filtering true stack.\n");
 580         *true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
 581         DIMPLIED("filtering false stack.\n");
 582         *false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
 583         free_slist(&true_stack);
 584         free_slist(&false_stack);
 585         if (option_debug_implied || option_debug) {
 586                 printf("These are the implied states for the true path: (%s %s %s)\n",
 587                        sm->name, show_special(comparison), show_rl(rl));
 588                 __print_stree(*true_states);
 589                 printf("These are the implied states for the false path: (%s %s %s)\n",
 590                        sm->name, show_special(comparison), show_rl(rl));
 591                 __print_stree(*false_states);
 592         }
 593 
 594         gettimeofday(&time_after, NULL);
 595         sec = time_after.tv_sec - time_before.tv_sec;
 596         if (sec > 20) {
 597                 sm->nr_children = 4000;
 598                 sm_perror("Function too hairy.  Ignoring implications after %d seconds.", sec);
 599         }
 600 }
 601 
 602 static struct expression *get_last_expr(struct statement *stmt)
 603 {
 604         struct statement *last;
 605 
 606         last = last_ptr_list((struct ptr_list *)stmt->stmts);
 607         if (last->type == STMT_EXPRESSION)
 608                 return last->expression;
 609 
 610         if (last->type == STMT_LABEL) {
 611                 if (last->label_statement &&
 612                     last->label_statement->type == STMT_EXPRESSION)
 613                         return last->label_statement->expression;
 614         }
 615 
 616         return NULL;
 617 }
 618 
 619 static struct expression *get_left_most_expr(struct expression *expr)
 620 {
 621         struct statement *compound;
 622 
 623         compound = get_expression_statement(expr);
 624         if (compound)
 625                 return get_last_expr(compound);
 626 
 627         expr = strip_parens(expr);
 628         if (expr->type == EXPR_ASSIGNMENT)
 629                 return get_left_most_expr(expr->left);
 630         return expr;
 631 }
 632 
 633 static int is_merged_expr(struct expression  *expr)
 634 {
 635         struct sm_state *sm;
 636         sval_t dummy;
 637 
 638         if (get_value(expr, &dummy))
 639                 return 0;
 640         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 641         if (!sm)
 642                 return 0;
 643         if (is_merged(sm))
 644                 return 1;
 645         return 0;
 646 }
 647 
 648 static void delete_gate_sm_equiv(struct stree **stree, const char *name, struct symbol *sym)
 649 {
 650         struct smatch_state *state;
 651         struct relation *rel;
 652 
 653         state = get_state(SMATCH_EXTRA, name, sym);
 654         if (!state)
 655                 return;
 656         FOR_EACH_PTR(estate_related(state), rel) {
 657                 delete_state_stree(stree, SMATCH_EXTRA, rel->name, rel->sym);
 658         } END_FOR_EACH_PTR(rel);
 659 }
 660 
 661 static void delete_gate_sm(struct stree **stree, const char *name, struct symbol *sym)
 662 {
 663         delete_state_stree(stree, SMATCH_EXTRA, name, sym);
 664 }
 665 
 666 static int handle_comparison(struct expression *expr,
 667                               struct stree **implied_true,
 668                               struct stree **implied_false)
 669 {
 670         struct sm_state *sm = NULL;
 671         struct range_list *rl = NULL;
 672         struct expression *left;
 673         struct expression *right;
 674         struct symbol *type;
 675         int comparison = expr->op;
 676         int mixed = 0;
 677 
 678         left = get_left_most_expr(expr->left);
 679         right = get_left_most_expr(expr->right);
 680 
 681         if (is_merged_expr(left)) {
 682                 sm = get_sm_state_expr(SMATCH_EXTRA, left);
 683                 get_implied_rl(right, &rl);
 684         } else if (is_merged_expr(right)) {
 685                 sm = get_sm_state_expr(SMATCH_EXTRA, right);
 686                 get_implied_rl(left, &rl);
 687                 comparison = flip_comparison(comparison);
 688         }
 689 
 690         if (!rl || !sm)
 691                 return 0;
 692 
 693         type = get_type(expr);
 694         if (!type)
 695                 return 0;
 696         if (type_positive_bits(rl_type(rl)) > type_positive_bits(type))
 697                 type = rl_type(rl);
 698         if (type_positive_bits(type) < 31)
 699                 type = &int_ctype;
 700         rl = cast_rl(type, rl);
 701 
 702         separate_and_filter(sm, comparison, rl, __get_cur_stree(), implied_true, implied_false, &mixed);
 703 
 704         delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
 705         delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
 706         if (mixed) {
 707                 delete_gate_sm(implied_true, sm->name, sm->sym);
 708                 delete_gate_sm(implied_false, sm->name, sm->sym);
 709         }
 710 
 711         return 1;
 712 }
 713 
 714 static int handle_zero_comparison(struct expression *expr,
 715                                 struct stree **implied_true,
 716                                 struct stree **implied_false)
 717 {
 718         struct symbol *sym;
 719         char *name;
 720         struct sm_state *sm;
 721         int mixed = 0;
 722         int ret = 0;
 723 
 724         if (expr->type == EXPR_POSTOP)
 725                 expr = strip_expr(expr->unop);
 726 
 727         if (expr->type == EXPR_ASSIGNMENT) {
 728                 /* most of the time ->pools will be empty here because we
 729                    just set the state, but if have assigned a conditional
 730                    function there are implications. */
 731                 expr = expr->left;
 732         }
 733 
 734         name = expr_to_var_sym(expr, &sym);
 735         if (!name || !sym)
 736                 goto free;
 737         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 738         if (!sm)
 739                 goto free;
 740 
 741         separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(estate_type(sm->state), 0), __get_cur_stree(), implied_true, implied_false, &mixed);
 742         delete_gate_sm_equiv(implied_true, sm->name, sm->sym);
 743         delete_gate_sm_equiv(implied_false, sm->name, sm->sym);
 744         if (mixed) {
 745                 delete_gate_sm(implied_true, sm->name, sm->sym);
 746                 delete_gate_sm(implied_false, sm->name, sm->sym);
 747         }
 748 
 749         ret = 1;
 750 free:
 751         free_string(name);
 752         return ret;
 753 }
 754 
 755 static int handled_by_comparison_hook(struct expression *expr,
 756                                    struct stree **implied_true,
 757                                    struct stree **implied_false)
 758 {
 759         struct state_list *true_stack = NULL;
 760         struct state_list *false_stack = NULL;
 761         struct stree *pre_stree;
 762         struct sm_state *sm;
 763 
 764         sm = comparison_implication_hook(expr, &true_stack, &false_stack);
 765         if (!sm)
 766                 return 0;
 767 
 768         pre_stree = clone_stree(__get_cur_stree());
 769 
 770         *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
 771         *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
 772 
 773         free_stree(&pre_stree);
 774         free_slist(&true_stack);
 775         free_slist(&false_stack);
 776 
 777         return 1;
 778 }
 779 
 780 static int handled_by_extra_states(struct expression *expr,
 781                                    struct stree **implied_true,
 782                                    struct stree **implied_false)
 783 {
 784         if (expr->type == EXPR_COMPARE)
 785                 return handle_comparison(expr, implied_true, implied_false);
 786         else
 787                 return handle_zero_comparison(expr, implied_true, implied_false);
 788 }
 789 
 790 static int handled_by_stored_conditions(struct expression *expr,
 791                                         struct stree **implied_true,
 792                                         struct stree **implied_false)
 793 {
 794         struct state_list *true_stack = NULL;
 795         struct state_list *false_stack = NULL;
 796         struct stree *pre_stree;
 797         struct sm_state *sm;
 798 
 799         sm = stored_condition_implication_hook(expr, &true_stack, &false_stack);
 800         if (!sm)
 801                 return 0;
 802 
 803         pre_stree = clone_stree(__get_cur_stree());
 804 
 805         *implied_true = filter_stack(sm, pre_stree, false_stack, true_stack);
 806         *implied_false = filter_stack(sm, pre_stree, true_stack, false_stack);
 807 
 808         free_stree(&pre_stree);
 809         free_slist(&true_stack);
 810         free_slist(&false_stack);
 811 
 812         return 1;
 813 }
 814 
 815 static int found_implications;
 816 static struct stree *saved_implied_true;
 817 static struct stree *saved_implied_false;
 818 static struct stree *extra_saved_implied_true;
 819 static struct stree *extra_saved_implied_false;
 820 
 821 static void separate_extra_states(struct stree **implied_true,
 822                                   struct stree **implied_false)
 823 {
 824         struct sm_state *sm;
 825 
 826         /* We process extra states later to preserve the implications. */
 827         FOR_EACH_SM(*implied_true, sm) {
 828                 if (sm->owner == SMATCH_EXTRA)
 829                         overwrite_sm_state_stree(&extra_saved_implied_true, sm);
 830         } END_FOR_EACH_SM(sm);
 831         FOR_EACH_SM(extra_saved_implied_true, sm) {
 832                 delete_state_stree(implied_true, sm->owner, sm->name, sm->sym);
 833         } END_FOR_EACH_SM(sm);
 834 
 835         FOR_EACH_SM(*implied_false, sm) {
 836                 if (sm->owner == SMATCH_EXTRA)
 837                         overwrite_sm_state_stree(&extra_saved_implied_false, sm);
 838         } END_FOR_EACH_SM(sm);
 839         FOR_EACH_SM(extra_saved_implied_false, sm) {
 840                 delete_state_stree(implied_false, sm->owner, sm->name, sm->sym);
 841         } END_FOR_EACH_SM(sm);
 842 }
 843 
 844 static void get_tf_states(struct expression *expr,
 845                           struct stree **implied_true,
 846                           struct stree **implied_false)
 847 {
 848         if (handled_by_comparison_hook(expr, implied_true, implied_false))
 849                 goto found;
 850 
 851         if (handled_by_extra_states(expr, implied_true, implied_false)) {
 852                 separate_extra_states(implied_true, implied_false);
 853                 goto found;
 854         }
 855 
 856         if (handled_by_stored_conditions(expr, implied_true, implied_false))
 857                 goto found;
 858 
 859         return;
 860 found:
 861         found_implications = 1;
 862 }
 863 
 864 static void save_implications_hook(struct expression *expr)
 865 {
 866         if (taking_too_long())
 867                 return;
 868         get_tf_states(expr, &saved_implied_true, &saved_implied_false);
 869 }
 870 
 871 static void set_implied_states(struct expression *expr)
 872 {
 873         struct sm_state *sm;
 874 
 875         FOR_EACH_SM(saved_implied_true, sm) {
 876                 __set_true_false_sm(sm, NULL);
 877         } END_FOR_EACH_SM(sm);
 878         free_stree(&saved_implied_true);
 879 
 880         FOR_EACH_SM(saved_implied_false, sm) {
 881                 __set_true_false_sm(NULL, sm);
 882         } END_FOR_EACH_SM(sm);
 883         free_stree(&saved_implied_false);
 884 }
 885 
 886 static void set_extra_implied_states(struct expression *expr)
 887 {
 888         saved_implied_true = extra_saved_implied_true;
 889         saved_implied_false = extra_saved_implied_false;
 890         extra_saved_implied_true = NULL;
 891         extra_saved_implied_false = NULL;
 892         set_implied_states(NULL);
 893 }
 894 
 895 void param_limit_implications(struct expression *expr, int param, char *key, char *value)
 896 {
 897         struct expression *arg;
 898         struct symbol *compare_type;
 899         char *name;
 900         struct symbol *sym;
 901         struct sm_state *sm;
 902         struct sm_state *tmp;
 903         struct stree *implied_true = NULL;
 904         struct stree *implied_false = NULL;
 905         struct range_list *orig, *limit;
 906 
 907         while (expr->type == EXPR_ASSIGNMENT)
 908                 expr = strip_expr(expr->right);
 909         if (expr->type != EXPR_CALL)
 910                 return;
 911 
 912         arg = get_argument_from_call_expr(expr->args, param);
 913         if (!arg)
 914                 return;
 915 
 916         arg = strip_parens(arg);
 917         while (arg->type == EXPR_ASSIGNMENT && arg->op == '=')
 918                 arg = strip_parens(arg->left);
 919 
 920         name = get_variable_from_key(arg, key, &sym);
 921         if (!name || !sym)
 922                 goto free;
 923 
 924         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 925         if (!sm || !sm->merged)
 926                 goto free;
 927 
 928         if (strcmp(key, "$") == 0)
 929                 compare_type = get_arg_type(expr->fn, param);
 930         else
 931                 compare_type = get_member_type_from_key(arg, key);
 932 
 933         orig = estate_rl(sm->state);
 934         orig = cast_rl(compare_type, orig);
 935 
 936         call_results_to_rl(expr, compare_type, value, &limit);
 937 
 938         separate_and_filter(sm, SPECIAL_EQUAL, limit, __get_cur_stree(), &implied_true, &implied_false, NULL);
 939 
 940         FOR_EACH_SM(implied_true, tmp) {
 941                 __set_sm_fake_stree(tmp);
 942         } END_FOR_EACH_SM(tmp);
 943 
 944         free_stree(&implied_true);
 945         free_stree(&implied_false);
 946 free:
 947         free_string(name);
 948 }
 949 
 950 struct stree *__implied_case_stree(struct expression *switch_expr,
 951                                    struct range_list *rl,
 952                                    struct range_list_stack **remaining_cases,
 953                                    struct stree **raw_stree)
 954 {
 955         char *name;
 956         struct symbol *sym;
 957         struct var_sym_list *vsl;
 958         struct sm_state *sm;
 959         struct stree *true_states = NULL;
 960         struct stree *false_states = NULL;
 961         struct stree *extra_states;
 962         struct stree *ret = clone_stree(*raw_stree);
 963 
 964         name = expr_to_chunk_sym_vsl(switch_expr, &sym, &vsl);
 965 
 966         if (rl)
 967                 filter_top_rl(remaining_cases, rl);
 968         else
 969                 rl = clone_rl(top_rl(*remaining_cases));
 970 
 971         if (name) {
 972                 sm = get_sm_state_stree(*raw_stree, SMATCH_EXTRA, name, sym);
 973                 if (sm)
 974                         separate_and_filter(sm, SPECIAL_EQUAL, rl, *raw_stree, &true_states, &false_states, NULL);
 975         }
 976 
 977         __push_fake_cur_stree();
 978         __unnullify_path();
 979         if (name)
 980                 set_extra_nomod_vsl(name, sym, vsl, NULL, alloc_estate_rl(rl));
 981         __pass_case_to_client(switch_expr, rl);
 982         extra_states = __pop_fake_cur_stree();
 983         overwrite_stree(extra_states, &true_states);
 984         overwrite_stree(true_states, &ret);
 985         free_stree(&extra_states);
 986         free_stree(&true_states);
 987         free_stree(&false_states);
 988 
 989         free_string(name);
 990         return ret;
 991 }
 992 
 993 static void match_end_func(struct symbol *sym)
 994 {
 995         if (__inline_fn)
 996                 return;
 997         implied_debug_msg = NULL;
 998 }
 999 
1000 static void get_tf_stacks_from_pool(struct sm_state *gate_sm,
1001                                     struct sm_state *pool_sm,
1002                                     struct state_list **true_stack,
1003                                     struct state_list **false_stack)
1004 {
1005         struct sm_state *tmp;
1006         int possibly_true = 0;
1007 
1008         if (!gate_sm)
1009                 return;
1010 
1011         if (strcmp(gate_sm->state->name, pool_sm->state->name) == 0) {
1012                 add_ptr_list(true_stack, pool_sm);
1013                 return;
1014         }
1015 
1016         FOR_EACH_PTR(gate_sm->possible, tmp) {
1017                 if (strcmp(tmp->state->name, pool_sm->state->name) == 0) {
1018                         possibly_true = 1;
1019                         break;
1020                 }
1021         } END_FOR_EACH_PTR(tmp);
1022 
1023         if (!possibly_true) {
1024                 add_ptr_list(false_stack, gate_sm);
1025                 return;
1026         }
1027 
1028         get_tf_stacks_from_pool(gate_sm->left, pool_sm, true_stack, false_stack);
1029         get_tf_stacks_from_pool(gate_sm->right, pool_sm, true_stack, false_stack);
1030 }
1031 
1032 /*
1033  * The situation is we have a SMATCH_EXTRA state and we want to break it into
1034  * each of the ->possible states and find the implications of each.  The caller
1035  * has to use __push_fake_cur_stree() to preserve the correct states so they
1036  * can be restored later.
1037  */
1038 void overwrite_states_using_pool(struct sm_state *gate_sm, struct sm_state *pool_sm)
1039 {
1040         struct state_list *true_stack = NULL;
1041         struct state_list *false_stack = NULL;
1042         struct stree *pre_stree;
1043         struct stree *implied_true;
1044         struct sm_state *tmp;
1045 
1046         if (!pool_sm->pool)
1047                 return;
1048 
1049         get_tf_stacks_from_pool(gate_sm, pool_sm, &true_stack, &false_stack);
1050 
1051         pre_stree = clone_stree(__get_cur_stree());
1052 
1053         implied_true = filter_stack(gate_sm, pre_stree, false_stack, true_stack);
1054 
1055         free_stree(&pre_stree);
1056         free_slist(&true_stack);
1057         free_slist(&false_stack);
1058 
1059         FOR_EACH_SM(implied_true, tmp) {
1060                 set_state(tmp->owner, tmp->name, tmp->sym, tmp->state);
1061         } END_FOR_EACH_SM(tmp);
1062 
1063         free_stree(&implied_true);
1064 }
1065 
1066 int assume(struct expression *expr)
1067 {
1068         int orig_final_pass = final_pass;
1069 
1070         in_fake_env++;
1071         final_pass = 0;
1072         __push_fake_cur_stree();
1073         found_implications = 0;
1074         __split_whole_condition(expr);
1075         final_pass = orig_final_pass;
1076         in_fake_env--;
1077 
1078         return 1;
1079 }
1080 
1081 void end_assume(void)
1082 {
1083         __discard_false_states();
1084         __free_fake_cur_stree();
1085 }
1086 
1087 int impossible_assumption(struct expression *left, int op, sval_t sval)
1088 {
1089         struct expression *value;
1090         struct expression *comparison;
1091         int ret;
1092 
1093         value = value_expr(sval.value);
1094         comparison = compare_expression(left, op, value);
1095 
1096         if (!assume(comparison))
1097                 return 0;
1098         ret = is_impossible_path();
1099         end_assume();
1100 
1101         return ret;
1102 }
1103 
1104 void __extra_match_condition(struct expression *expr);
1105 void __comparison_match_condition(struct expression *expr);
1106 void __stored_condition(struct expression *expr);
1107 void register_implications(int id)
1108 {
1109         add_hook(&save_implications_hook, CONDITION_HOOK);
1110         add_hook(&set_implied_states, CONDITION_HOOK);
1111         add_hook(&__extra_match_condition, CONDITION_HOOK);
1112         add_hook(&set_extra_implied_states, CONDITION_HOOK);
1113         add_hook(&__comparison_match_condition, CONDITION_HOOK);
1114         add_hook(&__stored_condition, CONDITION_HOOK);
1115         add_hook(&match_end_func, END_FUNC_HOOK);
1116 }