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