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