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