1 /* Predicate aware uninitialized variable warning. 2 Copyright (C) 2001-2013 Free Software Foundation, Inc. 3 Contributed by Xinliang David Li <davidxl@google.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "flags.h" 27 #include "tm_p.h" 28 #include "basic-block.h" 29 #include "function.h" 30 #include "gimple-pretty-print.h" 31 #include "bitmap.h" 32 #include "pointer-set.h" 33 #include "tree-flow.h" 34 #include "gimple.h" 35 #include "tree-inline.h" 36 #include "hashtab.h" 37 #include "tree-pass.h" 38 #include "diagnostic-core.h" 39 #include "params.h" 40 41 /* This implements the pass that does predicate aware warning on uses of 42 possibly uninitialized variables. The pass first collects the set of 43 possibly uninitialized SSA names. For each such name, it walks through 44 all its immediate uses. For each immediate use, it rebuilds the condition 45 expression (the predicate) that guards the use. The predicate is then 46 examined to see if the variable is always defined under that same condition. 47 This is done either by pruning the unrealizable paths that lead to the 48 default definitions or by checking if the predicate set that guards the 49 defining paths is a superset of the use predicate. */ 50 51 52 /* Pointer set of potentially undefined ssa names, i.e., 53 ssa names that are defined by phi with operands that 54 are not defined or potentially undefined. */ 55 static struct pointer_set_t *possibly_undefined_names = 0; 56 57 /* Bit mask handling macros. */ 58 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos) 59 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos)) 60 #define MASK_EMPTY(mask) (mask == 0) 61 62 /* Returns the first bit position (starting from LSB) 63 in mask that is non zero. Returns -1 if the mask is empty. */ 64 static int 65 get_mask_first_set_bit (unsigned mask) 66 { 67 int pos = 0; 68 if (mask == 0) 69 return -1; 70 71 while ((mask & (1 << pos)) == 0) 72 pos++; 73 74 return pos; 75 } 76 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask) 77 78 79 /* Return true if T, an SSA_NAME, has an undefined value. */ 80 81 bool 82 ssa_undefined_value_p (tree t) 83 { 84 tree var = SSA_NAME_VAR (t); 85 86 if (!var) 87 ; 88 /* Parameters get their initial value from the function entry. */ 89 else if (TREE_CODE (var) == PARM_DECL) 90 return false; 91 /* When returning by reference the return address is actually a hidden 92 parameter. */ 93 else if (TREE_CODE (var) == RESULT_DECL && DECL_BY_REFERENCE (var)) 94 return false; 95 /* Hard register variables get their initial value from the ether. */ 96 else if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var)) 97 return false; 98 99 /* The value is undefined iff its definition statement is empty. */ 100 return (gimple_nop_p (SSA_NAME_DEF_STMT (t)) 101 || (possibly_undefined_names 102 && pointer_set_contains (possibly_undefined_names, t))); 103 } 104 105 /* Like ssa_undefined_value_p, but don't return true if TREE_NO_WARNING 106 is set on SSA_NAME_VAR. */ 107 108 static inline bool 109 uninit_undefined_value_p (tree t) 110 { 111 if (!ssa_undefined_value_p (t)) 112 return false; 113 if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t))) 114 return false; 115 return true; 116 } 117 118 /* Checks if the operand OPND of PHI is defined by 119 another phi with one operand defined by this PHI, 120 but the rest operands are all defined. If yes, 121 returns true to skip this this operand as being 122 redundant. Can be enhanced to be more general. */ 123 124 static bool 125 can_skip_redundant_opnd (tree opnd, gimple phi) 126 { 127 gimple op_def; 128 tree phi_def; 129 int i, n; 130 131 phi_def = gimple_phi_result (phi); 132 op_def = SSA_NAME_DEF_STMT (opnd); 133 if (gimple_code (op_def) != GIMPLE_PHI) 134 return false; 135 n = gimple_phi_num_args (op_def); 136 for (i = 0; i < n; ++i) 137 { 138 tree op = gimple_phi_arg_def (op_def, i); 139 if (TREE_CODE (op) != SSA_NAME) 140 continue; 141 if (op != phi_def && uninit_undefined_value_p (op)) 142 return false; 143 } 144 145 return true; 146 } 147 148 /* Returns a bit mask holding the positions of arguments in PHI 149 that have empty (or possibly empty) definitions. */ 150 151 static unsigned 152 compute_uninit_opnds_pos (gimple phi) 153 { 154 size_t i, n; 155 unsigned uninit_opnds = 0; 156 157 n = gimple_phi_num_args (phi); 158 /* Bail out for phi with too many args. */ 159 if (n > 32) 160 return 0; 161 162 for (i = 0; i < n; ++i) 163 { 164 tree op = gimple_phi_arg_def (phi, i); 165 if (TREE_CODE (op) == SSA_NAME 166 && uninit_undefined_value_p (op) 167 && !can_skip_redundant_opnd (op, phi)) 168 MASK_SET_BIT (uninit_opnds, i); 169 } 170 return uninit_opnds; 171 } 172 173 /* Find the immediate postdominator PDOM of the specified 174 basic block BLOCK. */ 175 176 static inline basic_block 177 find_pdom (basic_block block) 178 { 179 if (block == EXIT_BLOCK_PTR) 180 return EXIT_BLOCK_PTR; 181 else 182 { 183 basic_block bb 184 = get_immediate_dominator (CDI_POST_DOMINATORS, block); 185 if (! bb) 186 return EXIT_BLOCK_PTR; 187 return bb; 188 } 189 } 190 191 /* Find the immediate DOM of the specified 192 basic block BLOCK. */ 193 194 static inline basic_block 195 find_dom (basic_block block) 196 { 197 if (block == ENTRY_BLOCK_PTR) 198 return ENTRY_BLOCK_PTR; 199 else 200 { 201 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block); 202 if (! bb) 203 return ENTRY_BLOCK_PTR; 204 return bb; 205 } 206 } 207 208 /* Returns true if BB1 is postdominating BB2 and BB1 is 209 not a loop exit bb. The loop exit bb check is simple and does 210 not cover all cases. */ 211 212 static bool 213 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2) 214 { 215 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1)) 216 return false; 217 218 if (single_pred_p (bb1) && !single_succ_p (bb2)) 219 return false; 220 221 return true; 222 } 223 224 /* Find the closest postdominator of a specified BB, which is control 225 equivalent to BB. */ 226 227 static inline basic_block 228 find_control_equiv_block (basic_block bb) 229 { 230 basic_block pdom; 231 232 pdom = find_pdom (bb); 233 234 /* Skip the postdominating bb that is also loop exit. */ 235 if (!is_non_loop_exit_postdominating (pdom, bb)) 236 return NULL; 237 238 if (dominated_by_p (CDI_DOMINATORS, pdom, bb)) 239 return pdom; 240 241 return NULL; 242 } 243 244 #define MAX_NUM_CHAINS 8 245 #define MAX_CHAIN_LEN 5 246 #define MAX_POSTDOM_CHECK 8 247 248 /* Computes the control dependence chains (paths of edges) 249 for DEP_BB up to the dominating basic block BB (the head node of a 250 chain should be dominated by it). CD_CHAINS is pointer to an 251 array holding the result chains. CUR_CD_CHAIN is the current 252 chain being computed. *NUM_CHAINS is total number of chains. The 253 function returns true if the information is successfully computed, 254 return false if there is no control dependence or not computed. */ 255 256 static bool 257 compute_control_dep_chain (basic_block bb, basic_block dep_bb, 258 vec<edge> *cd_chains, 259 size_t *num_chains, 260 vec<edge> *cur_cd_chain, 261 int *num_calls) 262 { 263 edge_iterator ei; 264 edge e; 265 size_t i; 266 bool found_cd_chain = false; 267 size_t cur_chain_len = 0; 268 269 if (EDGE_COUNT (bb->succs) < 2) 270 return false; 271 272 if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS)) 273 return false; 274 ++*num_calls; 275 276 /* Could use a set instead. */ 277 cur_chain_len = cur_cd_chain->length (); 278 if (cur_chain_len > MAX_CHAIN_LEN) 279 return false; 280 281 for (i = 0; i < cur_chain_len; i++) 282 { 283 edge e = (*cur_cd_chain)[i]; 284 /* cycle detected. */ 285 if (e->src == bb) 286 return false; 287 } 288 289 FOR_EACH_EDGE (e, ei, bb->succs) 290 { 291 basic_block cd_bb; 292 int post_dom_check = 0; 293 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL)) 294 continue; 295 296 cd_bb = e->dest; 297 cur_cd_chain->safe_push (e); 298 while (!is_non_loop_exit_postdominating (cd_bb, bb)) 299 { 300 if (cd_bb == dep_bb) 301 { 302 /* Found a direct control dependence. */ 303 if (*num_chains < MAX_NUM_CHAINS) 304 { 305 cd_chains[*num_chains] = cur_cd_chain->copy (); 306 (*num_chains)++; 307 } 308 found_cd_chain = true; 309 /* check path from next edge. */ 310 break; 311 } 312 313 /* Now check if DEP_BB is indirectly control dependent on BB. */ 314 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains, 315 num_chains, cur_cd_chain, num_calls)) 316 { 317 found_cd_chain = true; 318 break; 319 } 320 321 cd_bb = find_pdom (cd_bb); 322 post_dom_check++; 323 if (cd_bb == EXIT_BLOCK_PTR || post_dom_check > MAX_POSTDOM_CHECK) 324 break; 325 } 326 cur_cd_chain->pop (); 327 gcc_assert (cur_cd_chain->length () == cur_chain_len); 328 } 329 gcc_assert (cur_cd_chain->length () == cur_chain_len); 330 331 return found_cd_chain; 332 } 333 334 typedef struct use_pred_info 335 { 336 gimple cond; 337 bool invert; 338 } *use_pred_info_t; 339 340 341 342 /* Converts the chains of control dependence edges into a set of 343 predicates. A control dependence chain is represented by a vector 344 edges. DEP_CHAINS points to an array of dependence chains. 345 NUM_CHAINS is the size of the chain array. One edge in a dependence 346 chain is mapped to predicate expression represented by use_pred_info_t 347 type. One dependence chain is converted to a composite predicate that 348 is the result of AND operation of use_pred_info_t mapped to each edge. 349 A composite predicate is presented by a vector of use_pred_info_t. On 350 return, *PREDS points to the resulting array of composite predicates. 351 *NUM_PREDS is the number of composite predictes. */ 352 353 static bool 354 convert_control_dep_chain_into_preds (vec<edge> *dep_chains, 355 size_t num_chains, 356 vec<use_pred_info_t> **preds, 357 size_t *num_preds) 358 { 359 bool has_valid_pred = false; 360 size_t i, j; 361 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS) 362 return false; 363 364 /* Now convert the control dep chain into a set 365 of predicates. */ 366 typedef vec<use_pred_info_t> vec_use_pred_info_t_heap; 367 *preds = XCNEWVEC (vec_use_pred_info_t_heap, num_chains); 368 *num_preds = num_chains; 369 370 for (i = 0; i < num_chains; i++) 371 { 372 vec<edge> one_cd_chain = dep_chains[i]; 373 374 has_valid_pred = false; 375 for (j = 0; j < one_cd_chain.length (); j++) 376 { 377 gimple cond_stmt; 378 gimple_stmt_iterator gsi; 379 basic_block guard_bb; 380 use_pred_info_t one_pred; 381 edge e; 382 383 e = one_cd_chain[j]; 384 guard_bb = e->src; 385 gsi = gsi_last_bb (guard_bb); 386 if (gsi_end_p (gsi)) 387 { 388 has_valid_pred = false; 389 break; 390 } 391 cond_stmt = gsi_stmt (gsi); 392 if (gimple_code (cond_stmt) == GIMPLE_CALL 393 && EDGE_COUNT (e->src->succs) >= 2) 394 { 395 /* Ignore EH edge. Can add assertion 396 on the other edge's flag. */ 397 continue; 398 } 399 /* Skip if there is essentially one succesor. */ 400 if (EDGE_COUNT (e->src->succs) == 2) 401 { 402 edge e1; 403 edge_iterator ei1; 404 bool skip = false; 405 406 FOR_EACH_EDGE (e1, ei1, e->src->succs) 407 { 408 if (EDGE_COUNT (e1->dest->succs) == 0) 409 { 410 skip = true; 411 break; 412 } 413 } 414 if (skip) 415 continue; 416 } 417 if (gimple_code (cond_stmt) != GIMPLE_COND) 418 { 419 has_valid_pred = false; 420 break; 421 } 422 one_pred = XNEW (struct use_pred_info); 423 one_pred->cond = cond_stmt; 424 one_pred->invert = !!(e->flags & EDGE_FALSE_VALUE); 425 (*preds)[i].safe_push (one_pred); 426 has_valid_pred = true; 427 } 428 429 if (!has_valid_pred) 430 break; 431 } 432 return has_valid_pred; 433 } 434 435 /* Computes all control dependence chains for USE_BB. The control 436 dependence chains are then converted to an array of composite 437 predicates pointed to by PREDS. PHI_BB is the basic block of 438 the phi whose result is used in USE_BB. */ 439 440 static bool 441 find_predicates (vec<use_pred_info_t> **preds, 442 size_t *num_preds, 443 basic_block phi_bb, 444 basic_block use_bb) 445 { 446 size_t num_chains = 0, i; 447 int num_calls = 0; 448 vec<edge> dep_chains[MAX_NUM_CHAINS]; 449 vec<edge> cur_chain = vNULL; 450 bool has_valid_pred = false; 451 basic_block cd_root = 0; 452 453 /* First find the closest bb that is control equivalent to PHI_BB 454 that also dominates USE_BB. */ 455 cd_root = phi_bb; 456 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root)) 457 { 458 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root); 459 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb)) 460 cd_root = ctrl_eq_bb; 461 else 462 break; 463 } 464 465 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains, 466 &cur_chain, &num_calls); 467 468 has_valid_pred 469 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds, 470 num_preds); 471 /* Free individual chain */ 472 cur_chain.release (); 473 for (i = 0; i < num_chains; i++) 474 dep_chains[i].release (); 475 return has_valid_pred; 476 } 477 478 /* Computes the set of incoming edges of PHI that have non empty 479 definitions of a phi chain. The collection will be done 480 recursively on operands that are defined by phis. CD_ROOT 481 is the control dependence root. *EDGES holds the result, and 482 VISITED_PHIS is a pointer set for detecting cycles. */ 483 484 static void 485 collect_phi_def_edges (gimple phi, basic_block cd_root, 486 vec<edge> *edges, 487 struct pointer_set_t *visited_phis) 488 { 489 size_t i, n; 490 edge opnd_edge; 491 tree opnd; 492 493 if (pointer_set_insert (visited_phis, phi)) 494 return; 495 496 n = gimple_phi_num_args (phi); 497 for (i = 0; i < n; i++) 498 { 499 opnd_edge = gimple_phi_arg_edge (phi, i); 500 opnd = gimple_phi_arg_def (phi, i); 501 502 if (TREE_CODE (opnd) != SSA_NAME) 503 { 504 if (dump_file && (dump_flags & TDF_DETAILS)) 505 { 506 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i); 507 print_gimple_stmt (dump_file, phi, 0, 0); 508 } 509 edges->safe_push (opnd_edge); 510 } 511 else 512 { 513 gimple def = SSA_NAME_DEF_STMT (opnd); 514 515 if (gimple_code (def) == GIMPLE_PHI 516 && dominated_by_p (CDI_DOMINATORS, 517 gimple_bb (def), cd_root)) 518 collect_phi_def_edges (def, cd_root, edges, 519 visited_phis); 520 else if (!uninit_undefined_value_p (opnd)) 521 { 522 if (dump_file && (dump_flags & TDF_DETAILS)) 523 { 524 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i); 525 print_gimple_stmt (dump_file, phi, 0, 0); 526 } 527 edges->safe_push (opnd_edge); 528 } 529 } 530 } 531 } 532 533 /* For each use edge of PHI, computes all control dependence chains. 534 The control dependence chains are then converted to an array of 535 composite predicates pointed to by PREDS. */ 536 537 static bool 538 find_def_preds (vec<use_pred_info_t> **preds, 539 size_t *num_preds, gimple phi) 540 { 541 size_t num_chains = 0, i, n; 542 vec<edge> dep_chains[MAX_NUM_CHAINS]; 543 vec<edge> cur_chain = vNULL; 544 vec<edge> def_edges = vNULL; 545 bool has_valid_pred = false; 546 basic_block phi_bb, cd_root = 0; 547 struct pointer_set_t *visited_phis; 548 549 phi_bb = gimple_bb (phi); 550 /* First find the closest dominating bb to be 551 the control dependence root */ 552 cd_root = find_dom (phi_bb); 553 if (!cd_root) 554 return false; 555 556 visited_phis = pointer_set_create (); 557 collect_phi_def_edges (phi, cd_root, &def_edges, visited_phis); 558 pointer_set_destroy (visited_phis); 559 560 n = def_edges.length (); 561 if (n == 0) 562 return false; 563 564 for (i = 0; i < n; i++) 565 { 566 size_t prev_nc, j; 567 int num_calls = 0; 568 edge opnd_edge; 569 570 opnd_edge = def_edges[i]; 571 prev_nc = num_chains; 572 compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains, 573 &num_chains, &cur_chain, &num_calls); 574 575 /* Now update the newly added chains with 576 the phi operand edge: */ 577 if (EDGE_COUNT (opnd_edge->src->succs) > 1) 578 { 579 if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS) 580 dep_chains[num_chains++] = vNULL; 581 for (j = prev_nc; j < num_chains; j++) 582 dep_chains[j].safe_push (opnd_edge); 583 } 584 } 585 586 /* Free individual chain */ 587 cur_chain.release (); 588 589 has_valid_pred 590 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds, 591 num_preds); 592 for (i = 0; i < num_chains; i++) 593 dep_chains[i].release (); 594 return has_valid_pred; 595 } 596 597 /* Dumps the predicates (PREDS) for USESTMT. */ 598 599 static void 600 dump_predicates (gimple usestmt, size_t num_preds, 601 vec<use_pred_info_t> *preds, 602 const char* msg) 603 { 604 size_t i, j; 605 vec<use_pred_info_t> one_pred_chain; 606 fprintf (dump_file, msg); 607 print_gimple_stmt (dump_file, usestmt, 0, 0); 608 fprintf (dump_file, "is guarded by :\n"); 609 /* do some dumping here: */ 610 for (i = 0; i < num_preds; i++) 611 { 612 size_t np; 613 614 one_pred_chain = preds[i]; 615 np = one_pred_chain.length (); 616 617 for (j = 0; j < np; j++) 618 { 619 use_pred_info_t one_pred 620 = one_pred_chain[j]; 621 if (one_pred->invert) 622 fprintf (dump_file, " (.NOT.) "); 623 print_gimple_stmt (dump_file, one_pred->cond, 0, 0); 624 if (j < np - 1) 625 fprintf (dump_file, "(.AND.)\n"); 626 } 627 if (i < num_preds - 1) 628 fprintf (dump_file, "(.OR.)\n"); 629 } 630 } 631 632 /* Destroys the predicate set *PREDS. */ 633 634 static void 635 destroy_predicate_vecs (size_t n, 636 vec<use_pred_info_t> * preds) 637 { 638 size_t i, j; 639 for (i = 0; i < n; i++) 640 { 641 for (j = 0; j < preds[i].length (); j++) 642 free (preds[i][j]); 643 preds[i].release (); 644 } 645 free (preds); 646 } 647 648 649 /* Computes the 'normalized' conditional code with operand 650 swapping and condition inversion. */ 651 652 static enum tree_code 653 get_cmp_code (enum tree_code orig_cmp_code, 654 bool swap_cond, bool invert) 655 { 656 enum tree_code tc = orig_cmp_code; 657 658 if (swap_cond) 659 tc = swap_tree_comparison (orig_cmp_code); 660 if (invert) 661 tc = invert_tree_comparison (tc, false); 662 663 switch (tc) 664 { 665 case LT_EXPR: 666 case LE_EXPR: 667 case GT_EXPR: 668 case GE_EXPR: 669 case EQ_EXPR: 670 case NE_EXPR: 671 break; 672 default: 673 return ERROR_MARK; 674 } 675 return tc; 676 } 677 678 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e. 679 all values in the range satisfies (x CMPC BOUNDARY) == true. */ 680 681 static bool 682 is_value_included_in (tree val, tree boundary, enum tree_code cmpc) 683 { 684 bool inverted = false; 685 bool is_unsigned; 686 bool result; 687 688 /* Only handle integer constant here. */ 689 if (TREE_CODE (val) != INTEGER_CST 690 || TREE_CODE (boundary) != INTEGER_CST) 691 return true; 692 693 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val)); 694 695 if (cmpc == GE_EXPR || cmpc == GT_EXPR 696 || cmpc == NE_EXPR) 697 { 698 cmpc = invert_tree_comparison (cmpc, false); 699 inverted = true; 700 } 701 702 if (is_unsigned) 703 { 704 if (cmpc == EQ_EXPR) 705 result = tree_int_cst_equal (val, boundary); 706 else if (cmpc == LT_EXPR) 707 result = INT_CST_LT_UNSIGNED (val, boundary); 708 else 709 { 710 gcc_assert (cmpc == LE_EXPR); 711 result = (tree_int_cst_equal (val, boundary) 712 || INT_CST_LT_UNSIGNED (val, boundary)); 713 } 714 } 715 else 716 { 717 if (cmpc == EQ_EXPR) 718 result = tree_int_cst_equal (val, boundary); 719 else if (cmpc == LT_EXPR) 720 result = INT_CST_LT (val, boundary); 721 else 722 { 723 gcc_assert (cmpc == LE_EXPR); 724 result = (tree_int_cst_equal (val, boundary) 725 || INT_CST_LT (val, boundary)); 726 } 727 } 728 729 if (inverted) 730 result ^= 1; 731 732 return result; 733 } 734 735 /* Returns true if PRED is common among all the predicate 736 chains (PREDS) (and therefore can be factored out). 737 NUM_PRED_CHAIN is the size of array PREDS. */ 738 739 static bool 740 find_matching_predicate_in_rest_chains (use_pred_info_t pred, 741 vec<use_pred_info_t> *preds, 742 size_t num_pred_chains) 743 { 744 size_t i, j, n; 745 746 /* trival case */ 747 if (num_pred_chains == 1) 748 return true; 749 750 for (i = 1; i < num_pred_chains; i++) 751 { 752 bool found = false; 753 vec<use_pred_info_t> one_chain = preds[i]; 754 n = one_chain.length (); 755 for (j = 0; j < n; j++) 756 { 757 use_pred_info_t pred2 758 = one_chain[j]; 759 /* can relax the condition comparison to not 760 use address comparison. However, the most common 761 case is that multiple control dependent paths share 762 a common path prefix, so address comparison should 763 be ok. */ 764 765 if (pred2->cond == pred->cond 766 && pred2->invert == pred->invert) 767 { 768 found = true; 769 break; 770 } 771 } 772 if (!found) 773 return false; 774 } 775 return true; 776 } 777 778 /* Forward declaration. */ 779 static bool 780 is_use_properly_guarded (gimple use_stmt, 781 basic_block use_bb, 782 gimple phi, 783 unsigned uninit_opnds, 784 struct pointer_set_t *visited_phis); 785 786 /* Returns true if all uninitialized opnds are pruned. Returns false 787 otherwise. PHI is the phi node with uninitialized operands, 788 UNINIT_OPNDS is the bitmap of the uninitialize operand positions, 789 FLAG_DEF is the statement defining the flag guarding the use of the 790 PHI output, BOUNDARY_CST is the const value used in the predicate 791 associated with the flag, CMP_CODE is the comparison code used in 792 the predicate, VISITED_PHIS is the pointer set of phis visited, and 793 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions 794 that are also phis. 795 796 Example scenario: 797 798 BB1: 799 flag_1 = phi <0, 1> // (1) 800 var_1 = phi <undef, some_val> 801 802 803 BB2: 804 flag_2 = phi <0, flag_1, flag_1> // (2) 805 var_2 = phi <undef, var_1, var_1> 806 if (flag_2 == 1) 807 goto BB3; 808 809 BB3: 810 use of var_2 // (3) 811 812 Because some flag arg in (1) is not constant, if we do not look into the 813 flag phis recursively, it is conservatively treated as unknown and var_1 814 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized 815 a false warning will be emitted. Checking recursively into (1), the compiler can 816 find out that only some_val (which is defined) can flow into (3) which is OK. 817 818 */ 819 820 static bool 821 prune_uninit_phi_opnds_in_unrealizable_paths ( 822 gimple phi, unsigned uninit_opnds, 823 gimple flag_def, tree boundary_cst, 824 enum tree_code cmp_code, 825 struct pointer_set_t *visited_phis, 826 bitmap *visited_flag_phis) 827 { 828 unsigned i; 829 830 for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++) 831 { 832 tree flag_arg; 833 834 if (!MASK_TEST_BIT (uninit_opnds, i)) 835 continue; 836 837 flag_arg = gimple_phi_arg_def (flag_def, i); 838 if (!is_gimple_constant (flag_arg)) 839 { 840 gimple flag_arg_def, phi_arg_def; 841 tree phi_arg; 842 unsigned uninit_opnds_arg_phi; 843 844 if (TREE_CODE (flag_arg) != SSA_NAME) 845 return false; 846 flag_arg_def = SSA_NAME_DEF_STMT (flag_arg); 847 if (gimple_code (flag_arg_def) != GIMPLE_PHI) 848 return false; 849 850 phi_arg = gimple_phi_arg_def (phi, i); 851 if (TREE_CODE (phi_arg) != SSA_NAME) 852 return false; 853 854 phi_arg_def = SSA_NAME_DEF_STMT (phi_arg); 855 if (gimple_code (phi_arg_def) != GIMPLE_PHI) 856 return false; 857 858 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def)) 859 return false; 860 861 if (!*visited_flag_phis) 862 *visited_flag_phis = BITMAP_ALLOC (NULL); 863 864 if (bitmap_bit_p (*visited_flag_phis, 865 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)))) 866 return false; 867 868 bitmap_set_bit (*visited_flag_phis, 869 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))); 870 871 /* Now recursively prune the uninitialized phi args. */ 872 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def); 873 if (!prune_uninit_phi_opnds_in_unrealizable_paths ( 874 phi_arg_def, uninit_opnds_arg_phi, 875 flag_arg_def, boundary_cst, cmp_code, 876 visited_phis, visited_flag_phis)) 877 return false; 878 879 bitmap_clear_bit (*visited_flag_phis, 880 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))); 881 continue; 882 } 883 884 /* Now check if the constant is in the guarded range. */ 885 if (is_value_included_in (flag_arg, boundary_cst, cmp_code)) 886 { 887 tree opnd; 888 gimple opnd_def; 889 890 /* Now that we know that this undefined edge is not 891 pruned. If the operand is defined by another phi, 892 we can further prune the incoming edges of that 893 phi by checking the predicates of this operands. */ 894 895 opnd = gimple_phi_arg_def (phi, i); 896 opnd_def = SSA_NAME_DEF_STMT (opnd); 897 if (gimple_code (opnd_def) == GIMPLE_PHI) 898 { 899 edge opnd_edge; 900 unsigned uninit_opnds2 901 = compute_uninit_opnds_pos (opnd_def); 902 gcc_assert (!MASK_EMPTY (uninit_opnds2)); 903 opnd_edge = gimple_phi_arg_edge (phi, i); 904 if (!is_use_properly_guarded (phi, 905 opnd_edge->src, 906 opnd_def, 907 uninit_opnds2, 908 visited_phis)) 909 return false; 910 } 911 else 912 return false; 913 } 914 } 915 916 return true; 917 } 918 919 /* A helper function that determines if the predicate set 920 of the use is not overlapping with that of the uninit paths. 921 The most common senario of guarded use is in Example 1: 922 Example 1: 923 if (some_cond) 924 { 925 x = ...; 926 flag = true; 927 } 928 929 ... some code ... 930 931 if (flag) 932 use (x); 933 934 The real world examples are usually more complicated, but similar 935 and usually result from inlining: 936 937 bool init_func (int * x) 938 { 939 if (some_cond) 940 return false; 941 *x = .. 942 return true; 943 } 944 945 void foo(..) 946 { 947 int x; 948 949 if (!init_func(&x)) 950 return; 951 952 .. some_code ... 953 use (x); 954 } 955 956 Another possible use scenario is in the following trivial example: 957 958 Example 2: 959 if (n > 0) 960 x = 1; 961 ... 962 if (n > 0) 963 { 964 if (m < 2) 965 .. = x; 966 } 967 968 Predicate analysis needs to compute the composite predicate: 969 970 1) 'x' use predicate: (n > 0) .AND. (m < 2) 971 2) 'x' default value (non-def) predicate: .NOT. (n > 0) 972 (the predicate chain for phi operand defs can be computed 973 starting from a bb that is control equivalent to the phi's 974 bb and is dominating the operand def.) 975 976 and check overlapping: 977 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0)) 978 <==> false 979 980 This implementation provides framework that can handle 981 scenarios. (Note that many simple cases are handled properly 982 without the predicate analysis -- this is due to jump threading 983 transformation which eliminates the merge point thus makes 984 path sensitive analysis unnecessary.) 985 986 NUM_PREDS is the number is the number predicate chains, PREDS is 987 the array of chains, PHI is the phi node whose incoming (undefined) 988 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding 989 uninit operand positions. VISITED_PHIS is the pointer set of phi 990 stmts being checked. */ 991 992 993 static bool 994 use_pred_not_overlap_with_undef_path_pred ( 995 size_t num_preds, 996 vec<use_pred_info_t> *preds, 997 gimple phi, unsigned uninit_opnds, 998 struct pointer_set_t *visited_phis) 999 { 1000 unsigned int i, n; 1001 gimple flag_def = 0; 1002 tree boundary_cst = 0; 1003 enum tree_code cmp_code; 1004 bool swap_cond = false; 1005 bool invert = false; 1006 vec<use_pred_info_t> the_pred_chain; 1007 bitmap visited_flag_phis = NULL; 1008 bool all_pruned = false; 1009 1010 gcc_assert (num_preds > 0); 1011 /* Find within the common prefix of multiple predicate chains 1012 a predicate that is a comparison of a flag variable against 1013 a constant. */ 1014 the_pred_chain = preds[0]; 1015 n = the_pred_chain.length (); 1016 for (i = 0; i < n; i++) 1017 { 1018 gimple cond; 1019 tree cond_lhs, cond_rhs, flag = 0; 1020 1021 use_pred_info_t the_pred 1022 = the_pred_chain[i]; 1023 1024 cond = the_pred->cond; 1025 invert = the_pred->invert; 1026 cond_lhs = gimple_cond_lhs (cond); 1027 cond_rhs = gimple_cond_rhs (cond); 1028 cmp_code = gimple_cond_code (cond); 1029 1030 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME 1031 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs)) 1032 { 1033 boundary_cst = cond_rhs; 1034 flag = cond_lhs; 1035 } 1036 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME 1037 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs)) 1038 { 1039 boundary_cst = cond_lhs; 1040 flag = cond_rhs; 1041 swap_cond = true; 1042 } 1043 1044 if (!flag) 1045 continue; 1046 1047 flag_def = SSA_NAME_DEF_STMT (flag); 1048 1049 if (!flag_def) 1050 continue; 1051 1052 if ((gimple_code (flag_def) == GIMPLE_PHI) 1053 && (gimple_bb (flag_def) == gimple_bb (phi)) 1054 && find_matching_predicate_in_rest_chains ( 1055 the_pred, preds, num_preds)) 1056 break; 1057 1058 flag_def = 0; 1059 } 1060 1061 if (!flag_def) 1062 return false; 1063 1064 /* Now check all the uninit incoming edge has a constant flag value 1065 that is in conflict with the use guard/predicate. */ 1066 cmp_code = get_cmp_code (cmp_code, swap_cond, invert); 1067 1068 if (cmp_code == ERROR_MARK) 1069 return false; 1070 1071 all_pruned = prune_uninit_phi_opnds_in_unrealizable_paths (phi, 1072 uninit_opnds, 1073 flag_def, 1074 boundary_cst, 1075 cmp_code, 1076 visited_phis, 1077 &visited_flag_phis); 1078 1079 if (visited_flag_phis) 1080 BITMAP_FREE (visited_flag_phis); 1081 1082 return all_pruned; 1083 } 1084 1085 /* Returns true if TC is AND or OR */ 1086 1087 static inline bool 1088 is_and_or_or (enum tree_code tc, tree typ) 1089 { 1090 return (tc == BIT_IOR_EXPR 1091 || (tc == BIT_AND_EXPR 1092 && (typ == 0 || TREE_CODE (typ) == BOOLEAN_TYPE))); 1093 } 1094 1095 typedef struct norm_cond 1096 { 1097 vec<gimple> conds; 1098 enum tree_code cond_code; 1099 bool invert; 1100 } *norm_cond_t; 1101 1102 1103 /* Normalizes gimple condition COND. The normalization follows 1104 UD chains to form larger condition expression trees. NORM_COND 1105 holds the normalized result. COND_CODE is the logical opcode 1106 (AND or OR) of the normalized tree. */ 1107 1108 static void 1109 normalize_cond_1 (gimple cond, 1110 norm_cond_t norm_cond, 1111 enum tree_code cond_code) 1112 { 1113 enum gimple_code gc; 1114 enum tree_code cur_cond_code; 1115 tree rhs1, rhs2; 1116 1117 gc = gimple_code (cond); 1118 if (gc != GIMPLE_ASSIGN) 1119 { 1120 norm_cond->conds.safe_push (cond); 1121 return; 1122 } 1123 1124 cur_cond_code = gimple_assign_rhs_code (cond); 1125 rhs1 = gimple_assign_rhs1 (cond); 1126 rhs2 = gimple_assign_rhs2 (cond); 1127 if (cur_cond_code == NE_EXPR) 1128 { 1129 if (integer_zerop (rhs2) 1130 && (TREE_CODE (rhs1) == SSA_NAME)) 1131 normalize_cond_1 ( 1132 SSA_NAME_DEF_STMT (rhs1), 1133 norm_cond, cond_code); 1134 else if (integer_zerop (rhs1) 1135 && (TREE_CODE (rhs2) == SSA_NAME)) 1136 normalize_cond_1 ( 1137 SSA_NAME_DEF_STMT (rhs2), 1138 norm_cond, cond_code); 1139 else 1140 norm_cond->conds.safe_push (cond); 1141 1142 return; 1143 } 1144 1145 if (is_and_or_or (cur_cond_code, TREE_TYPE (rhs1)) 1146 && (cond_code == cur_cond_code || cond_code == ERROR_MARK) 1147 && (TREE_CODE (rhs1) == SSA_NAME && TREE_CODE (rhs2) == SSA_NAME)) 1148 { 1149 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs1), 1150 norm_cond, cur_cond_code); 1151 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs2), 1152 norm_cond, cur_cond_code); 1153 norm_cond->cond_code = cur_cond_code; 1154 } 1155 else 1156 norm_cond->conds.safe_push (cond); 1157 } 1158 1159 /* See normalize_cond_1 for details. INVERT is a flag to indicate 1160 if COND needs to be inverted or not. */ 1161 1162 static void 1163 normalize_cond (gimple cond, norm_cond_t norm_cond, bool invert) 1164 { 1165 enum tree_code cond_code; 1166 1167 norm_cond->cond_code = ERROR_MARK; 1168 norm_cond->invert = false; 1169 norm_cond->conds.create (0); 1170 gcc_assert (gimple_code (cond) == GIMPLE_COND); 1171 cond_code = gimple_cond_code (cond); 1172 if (invert) 1173 cond_code = invert_tree_comparison (cond_code, false); 1174 1175 if (cond_code == NE_EXPR) 1176 { 1177 if (integer_zerop (gimple_cond_rhs (cond)) 1178 && (TREE_CODE (gimple_cond_lhs (cond)) == SSA_NAME)) 1179 normalize_cond_1 ( 1180 SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)), 1181 norm_cond, ERROR_MARK); 1182 else if (integer_zerop (gimple_cond_lhs (cond)) 1183 && (TREE_CODE (gimple_cond_rhs (cond)) == SSA_NAME)) 1184 normalize_cond_1 ( 1185 SSA_NAME_DEF_STMT (gimple_cond_rhs (cond)), 1186 norm_cond, ERROR_MARK); 1187 else 1188 { 1189 norm_cond->conds.safe_push (cond); 1190 norm_cond->invert = invert; 1191 } 1192 } 1193 else 1194 { 1195 norm_cond->conds.safe_push (cond); 1196 norm_cond->invert = invert; 1197 } 1198 1199 gcc_assert (norm_cond->conds.length () == 1 1200 || is_and_or_or (norm_cond->cond_code, NULL)); 1201 } 1202 1203 /* Returns true if the domain for condition COND1 is a subset of 1204 COND2. REVERSE is a flag. when it is true the function checks 1205 if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags 1206 to indicate if COND1 and COND2 need to be inverted or not. */ 1207 1208 static bool 1209 is_gcond_subset_of (gimple cond1, bool invert1, 1210 gimple cond2, bool invert2, 1211 bool reverse) 1212 { 1213 enum gimple_code gc1, gc2; 1214 enum tree_code cond1_code, cond2_code; 1215 gimple tmp; 1216 tree cond1_lhs, cond1_rhs, cond2_lhs, cond2_rhs; 1217 1218 /* Take the short cut. */ 1219 if (cond1 == cond2) 1220 return true; 1221 1222 if (reverse) 1223 { 1224 tmp = cond1; 1225 cond1 = cond2; 1226 cond2 = tmp; 1227 } 1228 1229 gc1 = gimple_code (cond1); 1230 gc2 = gimple_code (cond2); 1231 1232 if ((gc1 != GIMPLE_ASSIGN && gc1 != GIMPLE_COND) 1233 || (gc2 != GIMPLE_ASSIGN && gc2 != GIMPLE_COND)) 1234 return cond1 == cond2; 1235 1236 cond1_code = ((gc1 == GIMPLE_ASSIGN) 1237 ? gimple_assign_rhs_code (cond1) 1238 : gimple_cond_code (cond1)); 1239 1240 cond2_code = ((gc2 == GIMPLE_ASSIGN) 1241 ? gimple_assign_rhs_code (cond2) 1242 : gimple_cond_code (cond2)); 1243 1244 if (TREE_CODE_CLASS (cond1_code) != tcc_comparison 1245 || TREE_CODE_CLASS (cond2_code) != tcc_comparison) 1246 return false; 1247 1248 if (invert1) 1249 cond1_code = invert_tree_comparison (cond1_code, false); 1250 if (invert2) 1251 cond2_code = invert_tree_comparison (cond2_code, false); 1252 1253 cond1_lhs = ((gc1 == GIMPLE_ASSIGN) 1254 ? gimple_assign_rhs1 (cond1) 1255 : gimple_cond_lhs (cond1)); 1256 cond1_rhs = ((gc1 == GIMPLE_ASSIGN) 1257 ? gimple_assign_rhs2 (cond1) 1258 : gimple_cond_rhs (cond1)); 1259 cond2_lhs = ((gc2 == GIMPLE_ASSIGN) 1260 ? gimple_assign_rhs1 (cond2) 1261 : gimple_cond_lhs (cond2)); 1262 cond2_rhs = ((gc2 == GIMPLE_ASSIGN) 1263 ? gimple_assign_rhs2 (cond2) 1264 : gimple_cond_rhs (cond2)); 1265 1266 /* Assuming const operands have been swapped to the 1267 rhs at this point of the analysis. */ 1268 1269 if (cond1_lhs != cond2_lhs) 1270 return false; 1271 1272 if (!is_gimple_constant (cond1_rhs) 1273 || TREE_CODE (cond1_rhs) != INTEGER_CST) 1274 return (cond1_rhs == cond2_rhs); 1275 1276 if (!is_gimple_constant (cond2_rhs) 1277 || TREE_CODE (cond2_rhs) != INTEGER_CST) 1278 return (cond1_rhs == cond2_rhs); 1279 1280 if (cond1_code == EQ_EXPR) 1281 return is_value_included_in (cond1_rhs, 1282 cond2_rhs, cond2_code); 1283 if (cond1_code == NE_EXPR || cond2_code == EQ_EXPR) 1284 return ((cond2_code == cond1_code) 1285 && tree_int_cst_equal (cond1_rhs, cond2_rhs)); 1286 1287 if (((cond1_code == GE_EXPR || cond1_code == GT_EXPR) 1288 && (cond2_code == LE_EXPR || cond2_code == LT_EXPR)) 1289 || ((cond1_code == LE_EXPR || cond1_code == LT_EXPR) 1290 && (cond2_code == GE_EXPR || cond2_code == GT_EXPR))) 1291 return false; 1292 1293 if (cond1_code != GE_EXPR && cond1_code != GT_EXPR 1294 && cond1_code != LE_EXPR && cond1_code != LT_EXPR) 1295 return false; 1296 1297 if (cond1_code == GT_EXPR) 1298 { 1299 cond1_code = GE_EXPR; 1300 cond1_rhs = fold_binary (PLUS_EXPR, TREE_TYPE (cond1_rhs), 1301 cond1_rhs, 1302 fold_convert (TREE_TYPE (cond1_rhs), 1303 integer_one_node)); 1304 } 1305 else if (cond1_code == LT_EXPR) 1306 { 1307 cond1_code = LE_EXPR; 1308 cond1_rhs = fold_binary (MINUS_EXPR, TREE_TYPE (cond1_rhs), 1309 cond1_rhs, 1310 fold_convert (TREE_TYPE (cond1_rhs), 1311 integer_one_node)); 1312 } 1313 1314 if (!cond1_rhs) 1315 return false; 1316 1317 gcc_assert (cond1_code == GE_EXPR || cond1_code == LE_EXPR); 1318 1319 if (cond2_code == GE_EXPR || cond2_code == GT_EXPR || 1320 cond2_code == LE_EXPR || cond2_code == LT_EXPR) 1321 return is_value_included_in (cond1_rhs, 1322 cond2_rhs, cond2_code); 1323 else if (cond2_code == NE_EXPR) 1324 return 1325 (is_value_included_in (cond1_rhs, 1326 cond2_rhs, cond2_code) 1327 && !is_value_included_in (cond2_rhs, 1328 cond1_rhs, cond1_code)); 1329 return false; 1330 } 1331 1332 /* Returns true if the domain of the condition expression 1333 in COND is a subset of any of the sub-conditions 1334 of the normalized condtion NORM_COND. INVERT is a flag 1335 to indicate of the COND needs to be inverted. 1336 REVERSE is a flag. When it is true, the check is reversed -- 1337 it returns true if COND is a superset of any of the subconditions 1338 of NORM_COND. */ 1339 1340 static bool 1341 is_subset_of_any (gimple cond, bool invert, 1342 norm_cond_t norm_cond, bool reverse) 1343 { 1344 size_t i; 1345 size_t len = norm_cond->conds.length (); 1346 1347 for (i = 0; i < len; i++) 1348 { 1349 if (is_gcond_subset_of (cond, invert, 1350 norm_cond->conds[i], 1351 false, reverse)) 1352 return true; 1353 } 1354 return false; 1355 } 1356 1357 /* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR 1358 expressions (formed by following UD chains not control 1359 dependence chains). The function returns true of domain 1360 of and expression NORM_COND1 is a subset of NORM_COND2's. 1361 The implementation is conservative, and it returns false if 1362 it the inclusion relationship may not hold. */ 1363 1364 static bool 1365 is_or_set_subset_of (norm_cond_t norm_cond1, 1366 norm_cond_t norm_cond2) 1367 { 1368 size_t i; 1369 size_t len = norm_cond1->conds.length (); 1370 1371 for (i = 0; i < len; i++) 1372 { 1373 if (!is_subset_of_any (norm_cond1->conds[i], 1374 false, norm_cond2, false)) 1375 return false; 1376 } 1377 return true; 1378 } 1379 1380 /* NORM_COND1 and NORM_COND2 are normalized logical AND 1381 expressions (formed by following UD chains not control 1382 dependence chains). The function returns true of domain 1383 of and expression NORM_COND1 is a subset of NORM_COND2's. */ 1384 1385 static bool 1386 is_and_set_subset_of (norm_cond_t norm_cond1, 1387 norm_cond_t norm_cond2) 1388 { 1389 size_t i; 1390 size_t len = norm_cond2->conds.length (); 1391 1392 for (i = 0; i < len; i++) 1393 { 1394 if (!is_subset_of_any (norm_cond2->conds[i], 1395 false, norm_cond1, true)) 1396 return false; 1397 } 1398 return true; 1399 } 1400 1401 /* Returns true of the domain if NORM_COND1 is a subset 1402 of that of NORM_COND2. Returns false if it can not be 1403 proved to be so. */ 1404 1405 static bool 1406 is_norm_cond_subset_of (norm_cond_t norm_cond1, 1407 norm_cond_t norm_cond2) 1408 { 1409 size_t i; 1410 enum tree_code code1, code2; 1411 1412 code1 = norm_cond1->cond_code; 1413 code2 = norm_cond2->cond_code; 1414 1415 if (code1 == BIT_AND_EXPR) 1416 { 1417 /* Both conditions are AND expressions. */ 1418 if (code2 == BIT_AND_EXPR) 1419 return is_and_set_subset_of (norm_cond1, norm_cond2); 1420 /* NORM_COND1 is an AND expression, and NORM_COND2 is an OR 1421 expression. In this case, returns true if any subexpression 1422 of NORM_COND1 is a subset of any subexpression of NORM_COND2. */ 1423 else if (code2 == BIT_IOR_EXPR) 1424 { 1425 size_t len1; 1426 len1 = norm_cond1->conds.length (); 1427 for (i = 0; i < len1; i++) 1428 { 1429 gimple cond1 = norm_cond1->conds[i]; 1430 if (is_subset_of_any (cond1, false, norm_cond2, false)) 1431 return true; 1432 } 1433 return false; 1434 } 1435 else 1436 { 1437 gcc_assert (code2 == ERROR_MARK); 1438 gcc_assert (norm_cond2->conds.length () == 1); 1439 return is_subset_of_any (norm_cond2->conds[0], 1440 norm_cond2->invert, norm_cond1, true); 1441 } 1442 } 1443 /* NORM_COND1 is an OR expression */ 1444 else if (code1 == BIT_IOR_EXPR) 1445 { 1446 if (code2 != code1) 1447 return false; 1448 1449 return is_or_set_subset_of (norm_cond1, norm_cond2); 1450 } 1451 else 1452 { 1453 gcc_assert (code1 == ERROR_MARK); 1454 gcc_assert (norm_cond1->conds.length () == 1); 1455 /* Conservatively returns false if NORM_COND1 is non-decomposible 1456 and NORM_COND2 is an AND expression. */ 1457 if (code2 == BIT_AND_EXPR) 1458 return false; 1459 1460 if (code2 == BIT_IOR_EXPR) 1461 return is_subset_of_any (norm_cond1->conds[0], 1462 norm_cond1->invert, norm_cond2, false); 1463 1464 gcc_assert (code2 == ERROR_MARK); 1465 gcc_assert (norm_cond2->conds.length () == 1); 1466 return is_gcond_subset_of (norm_cond1->conds[0], 1467 norm_cond1->invert, 1468 norm_cond2->conds[0], 1469 norm_cond2->invert, false); 1470 } 1471 } 1472 1473 /* Returns true of the domain of single predicate expression 1474 EXPR1 is a subset of that of EXPR2. Returns false if it 1475 can not be proved. */ 1476 1477 static bool 1478 is_pred_expr_subset_of (use_pred_info_t expr1, 1479 use_pred_info_t expr2) 1480 { 1481 gimple cond1, cond2; 1482 enum tree_code code1, code2; 1483 struct norm_cond norm_cond1, norm_cond2; 1484 bool is_subset = false; 1485 1486 cond1 = expr1->cond; 1487 cond2 = expr2->cond; 1488 code1 = gimple_cond_code (cond1); 1489 code2 = gimple_cond_code (cond2); 1490 1491 if (expr1->invert) 1492 code1 = invert_tree_comparison (code1, false); 1493 if (expr2->invert) 1494 code2 = invert_tree_comparison (code2, false); 1495 1496 /* Fast path -- match exactly */ 1497 if ((gimple_cond_lhs (cond1) == gimple_cond_lhs (cond2)) 1498 && (gimple_cond_rhs (cond1) == gimple_cond_rhs (cond2)) 1499 && (code1 == code2)) 1500 return true; 1501 1502 /* Normalize conditions. To keep NE_EXPR, do not invert 1503 with both need inversion. */ 1504 normalize_cond (cond1, &norm_cond1, (expr1->invert)); 1505 normalize_cond (cond2, &norm_cond2, (expr2->invert)); 1506 1507 is_subset = is_norm_cond_subset_of (&norm_cond1, &norm_cond2); 1508 1509 /* Free memory */ 1510 norm_cond1.conds.release (); 1511 norm_cond2.conds.release (); 1512 return is_subset ; 1513 } 1514 1515 /* Returns true if the domain of PRED1 is a subset 1516 of that of PRED2. Returns false if it can not be proved so. */ 1517 1518 static bool 1519 is_pred_chain_subset_of (vec<use_pred_info_t> pred1, 1520 vec<use_pred_info_t> pred2) 1521 { 1522 size_t np1, np2, i1, i2; 1523 1524 np1 = pred1.length (); 1525 np2 = pred2.length (); 1526 1527 for (i2 = 0; i2 < np2; i2++) 1528 { 1529 bool found = false; 1530 use_pred_info_t info2 1531 = pred2[i2]; 1532 for (i1 = 0; i1 < np1; i1++) 1533 { 1534 use_pred_info_t info1 1535 = pred1[i1]; 1536 if (is_pred_expr_subset_of (info1, info2)) 1537 { 1538 found = true; 1539 break; 1540 } 1541 } 1542 if (!found) 1543 return false; 1544 } 1545 return true; 1546 } 1547 1548 /* Returns true if the domain defined by 1549 one pred chain ONE_PRED is a subset of the domain 1550 of *PREDS. It returns false if ONE_PRED's domain is 1551 not a subset of any of the sub-domains of PREDS ( 1552 corresponding to each individual chains in it), even 1553 though it may be still be a subset of whole domain 1554 of PREDS which is the union (ORed) of all its subdomains. 1555 In other words, the result is conservative. */ 1556 1557 static bool 1558 is_included_in (vec<use_pred_info_t> one_pred, 1559 vec<use_pred_info_t> *preds, 1560 size_t n) 1561 { 1562 size_t i; 1563 1564 for (i = 0; i < n; i++) 1565 { 1566 if (is_pred_chain_subset_of (one_pred, preds[i])) 1567 return true; 1568 } 1569 1570 return false; 1571 } 1572 1573 /* compares two predicate sets PREDS1 and PREDS2 and returns 1574 true if the domain defined by PREDS1 is a superset 1575 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and 1576 PREDS2 respectively. The implementation chooses not to build 1577 generic trees (and relying on the folding capability of the 1578 compiler), but instead performs brute force comparison of 1579 individual predicate chains (won't be a compile time problem 1580 as the chains are pretty short). When the function returns 1581 false, it does not necessarily mean *PREDS1 is not a superset 1582 of *PREDS2, but mean it may not be so since the analysis can 1583 not prove it. In such cases, false warnings may still be 1584 emitted. */ 1585 1586 static bool 1587 is_superset_of (vec<use_pred_info_t> *preds1, 1588 size_t n1, 1589 vec<use_pred_info_t> *preds2, 1590 size_t n2) 1591 { 1592 size_t i; 1593 vec<use_pred_info_t> one_pred_chain; 1594 1595 for (i = 0; i < n2; i++) 1596 { 1597 one_pred_chain = preds2[i]; 1598 if (!is_included_in (one_pred_chain, preds1, n1)) 1599 return false; 1600 } 1601 1602 return true; 1603 } 1604 1605 /* Comparison function used by qsort. It is used to 1606 sort predicate chains to allow predicate 1607 simplification. */ 1608 1609 static int 1610 pred_chain_length_cmp (const void *p1, const void *p2) 1611 { 1612 use_pred_info_t i1, i2; 1613 vec<use_pred_info_t> const *chain1 1614 = (vec<use_pred_info_t> const *)p1; 1615 vec<use_pred_info_t> const *chain2 1616 = (vec<use_pred_info_t> const *)p2; 1617 1618 if (chain1->length () != chain2->length ()) 1619 return (chain1->length () - chain2->length ()); 1620 1621 i1 = (*chain1)[0]; 1622 i2 = (*chain2)[0]; 1623 1624 /* Allow predicates with similar prefix come together. */ 1625 if (!i1->invert && i2->invert) 1626 return -1; 1627 else if (i1->invert && !i2->invert) 1628 return 1; 1629 1630 return gimple_uid (i1->cond) - gimple_uid (i2->cond); 1631 } 1632 1633 /* x OR (!x AND y) is equivalent to x OR y. 1634 This function normalizes x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) 1635 into x1 OR x2 OR x3. PREDS is the predicate chains, and N is 1636 the number of chains. Returns true if normalization happens. */ 1637 1638 static bool 1639 normalize_preds (vec<use_pred_info_t> *preds, size_t *n) 1640 { 1641 size_t i, j, ll; 1642 vec<use_pred_info_t> pred_chain; 1643 vec<use_pred_info_t> x = vNULL; 1644 use_pred_info_t xj = 0, nxj = 0; 1645 1646 if (*n < 2) 1647 return false; 1648 1649 /* First sort the chains in ascending order of lengths. */ 1650 qsort (preds, *n, sizeof (void *), pred_chain_length_cmp); 1651 pred_chain = preds[0]; 1652 ll = pred_chain.length (); 1653 if (ll != 1) 1654 { 1655 if (ll == 2) 1656 { 1657 use_pred_info_t xx, yy, xx2, nyy; 1658 vec<use_pred_info_t> pred_chain2 = preds[1]; 1659 if (pred_chain2.length () != 2) 1660 return false; 1661 1662 /* See if simplification x AND y OR x AND !y is possible. */ 1663 xx = pred_chain[0]; 1664 yy = pred_chain[1]; 1665 xx2 = pred_chain2[0]; 1666 nyy = pred_chain2[1]; 1667 if (gimple_cond_lhs (xx->cond) != gimple_cond_lhs (xx2->cond) 1668 || gimple_cond_rhs (xx->cond) != gimple_cond_rhs (xx2->cond) 1669 || gimple_cond_code (xx->cond) != gimple_cond_code (xx2->cond) 1670 || (xx->invert != xx2->invert)) 1671 return false; 1672 if (gimple_cond_lhs (yy->cond) != gimple_cond_lhs (nyy->cond) 1673 || gimple_cond_rhs (yy->cond) != gimple_cond_rhs (nyy->cond) 1674 || gimple_cond_code (yy->cond) != gimple_cond_code (nyy->cond) 1675 || (yy->invert == nyy->invert)) 1676 return false; 1677 1678 /* Now merge the first two chains. */ 1679 free (yy); 1680 free (nyy); 1681 free (xx2); 1682 pred_chain.release (); 1683 pred_chain2.release (); 1684 pred_chain.safe_push (xx); 1685 preds[0] = pred_chain; 1686 for (i = 1; i < *n - 1; i++) 1687 preds[i] = preds[i + 1]; 1688 1689 preds[*n - 1].create (0); 1690 *n = *n - 1; 1691 } 1692 else 1693 return false; 1694 } 1695 1696 x.safe_push (pred_chain[0]); 1697 1698 /* The loop extracts x1, x2, x3, etc from chains 1699 x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) OR ... */ 1700 for (i = 1; i < *n; i++) 1701 { 1702 pred_chain = preds[i]; 1703 if (pred_chain.length () != i + 1) 1704 return false; 1705 1706 for (j = 0; j < i; j++) 1707 { 1708 xj = x[j]; 1709 nxj = pred_chain[j]; 1710 1711 /* Check if nxj is !xj */ 1712 if (gimple_cond_lhs (xj->cond) != gimple_cond_lhs (nxj->cond) 1713 || gimple_cond_rhs (xj->cond) != gimple_cond_rhs (nxj->cond) 1714 || gimple_cond_code (xj->cond) != gimple_cond_code (nxj->cond) 1715 || (xj->invert == nxj->invert)) 1716 return false; 1717 } 1718 1719 x.safe_push (pred_chain[i]); 1720 } 1721 1722 /* Now normalize the pred chains using the extraced x1, x2, x3 etc. */ 1723 for (j = 0; j < *n; j++) 1724 { 1725 use_pred_info_t t; 1726 xj = x[j]; 1727 1728 t = XNEW (struct use_pred_info); 1729 *t = *xj; 1730 1731 x[j] = t; 1732 } 1733 1734 for (i = 0; i < *n; i++) 1735 { 1736 pred_chain = preds[i]; 1737 for (j = 0; j < pred_chain.length (); j++) 1738 free (pred_chain[j]); 1739 pred_chain.release (); 1740 /* A new chain. */ 1741 pred_chain.safe_push (x[i]); 1742 preds[i] = pred_chain; 1743 } 1744 return true; 1745 } 1746 1747 1748 1749 /* Computes the predicates that guard the use and checks 1750 if the incoming paths that have empty (or possibly 1751 empty) definition can be pruned/filtered. The function returns 1752 true if it can be determined that the use of PHI's def in 1753 USE_STMT is guarded with a predicate set not overlapping with 1754 predicate sets of all runtime paths that do not have a definition. 1755 Returns false if it is not or it can not be determined. USE_BB is 1756 the bb of the use (for phi operand use, the bb is not the bb of 1757 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS 1758 is a bit vector. If an operand of PHI is uninitialized, the 1759 corresponding bit in the vector is 1. VISIED_PHIS is a pointer 1760 set of phis being visted. */ 1761 1762 static bool 1763 is_use_properly_guarded (gimple use_stmt, 1764 basic_block use_bb, 1765 gimple phi, 1766 unsigned uninit_opnds, 1767 struct pointer_set_t *visited_phis) 1768 { 1769 basic_block phi_bb; 1770 vec<use_pred_info_t> *preds = 0; 1771 vec<use_pred_info_t> *def_preds = 0; 1772 size_t num_preds = 0, num_def_preds = 0; 1773 bool has_valid_preds = false; 1774 bool is_properly_guarded = false; 1775 1776 if (pointer_set_insert (visited_phis, phi)) 1777 return false; 1778 1779 phi_bb = gimple_bb (phi); 1780 1781 if (is_non_loop_exit_postdominating (use_bb, phi_bb)) 1782 return false; 1783 1784 has_valid_preds = find_predicates (&preds, &num_preds, 1785 phi_bb, use_bb); 1786 1787 if (!has_valid_preds) 1788 { 1789 destroy_predicate_vecs (num_preds, preds); 1790 return false; 1791 } 1792 1793 if (dump_file) 1794 dump_predicates (use_stmt, num_preds, preds, 1795 "\nUse in stmt "); 1796 1797 has_valid_preds = find_def_preds (&def_preds, 1798 &num_def_preds, phi); 1799 1800 if (has_valid_preds) 1801 { 1802 bool normed; 1803 if (dump_file) 1804 dump_predicates (phi, num_def_preds, def_preds, 1805 "Operand defs of phi "); 1806 1807 normed = normalize_preds (def_preds, &num_def_preds); 1808 if (normed && dump_file) 1809 { 1810 fprintf (dump_file, "\nNormalized to\n"); 1811 dump_predicates (phi, num_def_preds, def_preds, 1812 "Operand defs of phi "); 1813 } 1814 is_properly_guarded = 1815 is_superset_of (def_preds, num_def_preds, 1816 preds, num_preds); 1817 } 1818 1819 /* further prune the dead incoming phi edges. */ 1820 if (!is_properly_guarded) 1821 is_properly_guarded 1822 = use_pred_not_overlap_with_undef_path_pred ( 1823 num_preds, preds, phi, uninit_opnds, visited_phis); 1824 1825 destroy_predicate_vecs (num_preds, preds); 1826 destroy_predicate_vecs (num_def_preds, def_preds); 1827 return is_properly_guarded; 1828 } 1829 1830 /* Searches through all uses of a potentially 1831 uninitialized variable defined by PHI and returns a use 1832 statement if the use is not properly guarded. It returns 1833 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector 1834 holding the position(s) of uninit PHI operands. WORKLIST 1835 is the vector of candidate phis that may be updated by this 1836 function. ADDED_TO_WORKLIST is the pointer set tracking 1837 if the new phi is already in the worklist. */ 1838 1839 static gimple 1840 find_uninit_use (gimple phi, unsigned uninit_opnds, 1841 vec<gimple> *worklist, 1842 struct pointer_set_t *added_to_worklist) 1843 { 1844 tree phi_result; 1845 use_operand_p use_p; 1846 gimple use_stmt; 1847 imm_use_iterator iter; 1848 1849 phi_result = gimple_phi_result (phi); 1850 1851 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result) 1852 { 1853 struct pointer_set_t *visited_phis; 1854 basic_block use_bb; 1855 1856 use_stmt = USE_STMT (use_p); 1857 if (is_gimple_debug (use_stmt)) 1858 continue; 1859 1860 visited_phis = pointer_set_create (); 1861 1862 if (gimple_code (use_stmt) == GIMPLE_PHI) 1863 use_bb = gimple_phi_arg_edge (use_stmt, 1864 PHI_ARG_INDEX_FROM_USE (use_p))->src; 1865 else 1866 use_bb = gimple_bb (use_stmt); 1867 1868 if (is_use_properly_guarded (use_stmt, 1869 use_bb, 1870 phi, 1871 uninit_opnds, 1872 visited_phis)) 1873 { 1874 pointer_set_destroy (visited_phis); 1875 continue; 1876 } 1877 pointer_set_destroy (visited_phis); 1878 1879 if (dump_file && (dump_flags & TDF_DETAILS)) 1880 { 1881 fprintf (dump_file, "[CHECK]: Found unguarded use: "); 1882 print_gimple_stmt (dump_file, use_stmt, 0, 0); 1883 } 1884 /* Found one real use, return. */ 1885 if (gimple_code (use_stmt) != GIMPLE_PHI) 1886 return use_stmt; 1887 1888 /* Found a phi use that is not guarded, 1889 add the phi to the worklist. */ 1890 if (!pointer_set_insert (added_to_worklist, 1891 use_stmt)) 1892 { 1893 if (dump_file && (dump_flags & TDF_DETAILS)) 1894 { 1895 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: "); 1896 print_gimple_stmt (dump_file, use_stmt, 0, 0); 1897 } 1898 1899 worklist->safe_push (use_stmt); 1900 pointer_set_insert (possibly_undefined_names, phi_result); 1901 } 1902 } 1903 1904 return NULL; 1905 } 1906 1907 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions 1908 and gives warning if there exists a runtime path from the entry to a 1909 use of the PHI def that does not contain a definition. In other words, 1910 the warning is on the real use. The more dead paths that can be pruned 1911 by the compiler, the fewer false positives the warning is. WORKLIST 1912 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is 1913 a pointer set tracking if the new phi is added to the worklist or not. */ 1914 1915 static void 1916 warn_uninitialized_phi (gimple phi, vec<gimple> *worklist, 1917 struct pointer_set_t *added_to_worklist) 1918 { 1919 unsigned uninit_opnds; 1920 gimple uninit_use_stmt = 0; 1921 tree uninit_op; 1922 1923 /* Don't look at virtual operands. */ 1924 if (virtual_operand_p (gimple_phi_result (phi))) 1925 return; 1926 1927 uninit_opnds = compute_uninit_opnds_pos (phi); 1928 1929 if (MASK_EMPTY (uninit_opnds)) 1930 return; 1931 1932 if (dump_file && (dump_flags & TDF_DETAILS)) 1933 { 1934 fprintf (dump_file, "[CHECK]: examining phi: "); 1935 print_gimple_stmt (dump_file, phi, 0, 0); 1936 } 1937 1938 /* Now check if we have any use of the value without proper guard. */ 1939 uninit_use_stmt = find_uninit_use (phi, uninit_opnds, 1940 worklist, added_to_worklist); 1941 1942 /* All uses are properly guarded. */ 1943 if (!uninit_use_stmt) 1944 return; 1945 1946 uninit_op = gimple_phi_arg_def (phi, MASK_FIRST_SET_BIT (uninit_opnds)); 1947 if (SSA_NAME_VAR (uninit_op) == NULL_TREE) 1948 return; 1949 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op), 1950 SSA_NAME_VAR (uninit_op), 1951 "%qD may be used uninitialized in this function", 1952 uninit_use_stmt); 1953 1954 } 1955 1956 1957 /* Entry point to the late uninitialized warning pass. */ 1958 1959 static unsigned int 1960 execute_late_warn_uninitialized (void) 1961 { 1962 basic_block bb; 1963 gimple_stmt_iterator gsi; 1964 vec<gimple> worklist = vNULL; 1965 struct pointer_set_t *added_to_worklist; 1966 1967 calculate_dominance_info (CDI_DOMINATORS); 1968 calculate_dominance_info (CDI_POST_DOMINATORS); 1969 /* Re-do the plain uninitialized variable check, as optimization may have 1970 straightened control flow. Do this first so that we don't accidentally 1971 get a "may be" warning when we'd have seen an "is" warning later. */ 1972 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1); 1973 1974 timevar_push (TV_TREE_UNINIT); 1975 1976 possibly_undefined_names = pointer_set_create (); 1977 added_to_worklist = pointer_set_create (); 1978 1979 /* Initialize worklist */ 1980 FOR_EACH_BB (bb) 1981 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1982 { 1983 gimple phi = gsi_stmt (gsi); 1984 size_t n, i; 1985 1986 n = gimple_phi_num_args (phi); 1987 1988 /* Don't look at virtual operands. */ 1989 if (virtual_operand_p (gimple_phi_result (phi))) 1990 continue; 1991 1992 for (i = 0; i < n; ++i) 1993 { 1994 tree op = gimple_phi_arg_def (phi, i); 1995 if (TREE_CODE (op) == SSA_NAME 1996 && uninit_undefined_value_p (op)) 1997 { 1998 worklist.safe_push (phi); 1999 pointer_set_insert (added_to_worklist, phi); 2000 if (dump_file && (dump_flags & TDF_DETAILS)) 2001 { 2002 fprintf (dump_file, "[WORKLIST]: add to initial list: "); 2003 print_gimple_stmt (dump_file, phi, 0, 0); 2004 } 2005 break; 2006 } 2007 } 2008 } 2009 2010 while (worklist.length () != 0) 2011 { 2012 gimple cur_phi = 0; 2013 cur_phi = worklist.pop (); 2014 warn_uninitialized_phi (cur_phi, &worklist, added_to_worklist); 2015 } 2016 2017 worklist.release (); 2018 pointer_set_destroy (added_to_worklist); 2019 pointer_set_destroy (possibly_undefined_names); 2020 possibly_undefined_names = NULL; 2021 free_dominance_info (CDI_POST_DOMINATORS); 2022 timevar_pop (TV_TREE_UNINIT); 2023 return 0; 2024 } 2025 2026 static bool 2027 gate_warn_uninitialized (void) 2028 { 2029 return warn_uninitialized != 0; 2030 } 2031 2032 struct gimple_opt_pass pass_late_warn_uninitialized = 2033 { 2034 { 2035 GIMPLE_PASS, 2036 "uninit", /* name */ 2037 OPTGROUP_NONE, /* optinfo_flags */ 2038 gate_warn_uninitialized, /* gate */ 2039 execute_late_warn_uninitialized, /* execute */ 2040 NULL, /* sub */ 2041 NULL, /* next */ 2042 0, /* static_pass_number */ 2043 TV_NONE, /* tv_id */ 2044 PROP_ssa, /* properties_required */ 2045 0, /* properties_provided */ 2046 0, /* properties_destroyed */ 2047 0, /* todo_flags_start */ 2048 0 /* todo_flags_finish */ 2049 } 2050 }; 2051