1/* Predicate aware uninitialized variable warning. 2 Copyright (C) 2001-2015 Free Software Foundation, Inc. 3 Contributed by Xinliang David Li <davidxl@google.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along 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 "hash-set.h" 26#include "machmode.h" 27#include "vec.h" 28#include "double-int.h" 29#include "input.h" 30#include "alias.h" 31#include "symtab.h" 32#include "wide-int.h" 33#include "inchash.h" 34#include "tree.h" 35#include "fold-const.h" 36#include "flags.h" 37#include "tm_p.h" 38#include "predict.h" 39#include "hard-reg-set.h" 40#include "input.h" 41#include "function.h" 42#include "dominance.h" 43#include "cfg.h" 44#include "basic-block.h" 45#include "gimple-pretty-print.h" 46#include "bitmap.h" 47#include "tree-ssa-alias.h" 48#include "internal-fn.h" 49#include "gimple-expr.h" 50#include "is-a.h" 51#include "gimple.h" 52#include "gimple-iterator.h" 53#include "gimple-ssa.h" 54#include "tree-phinodes.h" 55#include "ssa-iterators.h" 56#include "tree-ssa.h" 57#include "tree-inline.h" 58#include "tree-pass.h" 59#include "diagnostic-core.h" 60#include "params.h" 61#include "tree-cfg.h" 62 63/* This implements the pass that does predicate aware warning on uses of 64 possibly uninitialized variables. The pass first collects the set of 65 possibly uninitialized SSA names. For each such name, it walks through 66 all its immediate uses. For each immediate use, it rebuilds the condition 67 expression (the predicate) that guards the use. The predicate is then 68 examined to see if the variable is always defined under that same condition. 69 This is done either by pruning the unrealizable paths that lead to the 70 default definitions or by checking if the predicate set that guards the 71 defining paths is a superset of the use predicate. */ 72 73 74/* Pointer set of potentially undefined ssa names, i.e., 75 ssa names that are defined by phi with operands that 76 are not defined or potentially undefined. */ 77static hash_set<tree> *possibly_undefined_names = 0; 78 79/* Bit mask handling macros. */ 80#define MASK_SET_BIT(mask, pos) mask |= (1 << pos) 81#define MASK_TEST_BIT(mask, pos) (mask & (1 << pos)) 82#define MASK_EMPTY(mask) (mask == 0) 83 84/* Returns the first bit position (starting from LSB) 85 in mask that is non zero. Returns -1 if the mask is empty. */ 86static int 87get_mask_first_set_bit (unsigned mask) 88{ 89 int pos = 0; 90 if (mask == 0) 91 return -1; 92 93 while ((mask & (1 << pos)) == 0) 94 pos++; 95 96 return pos; 97} 98#define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask) 99 100/* Return true if T, an SSA_NAME, has an undefined value. */ 101static bool 102has_undefined_value_p (tree t) 103{ 104 return (ssa_undefined_value_p (t) 105 || (possibly_undefined_names 106 && possibly_undefined_names->contains (t))); 107} 108 109 110 111/* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING 112 is set on SSA_NAME_VAR. */ 113 114static inline bool 115uninit_undefined_value_p (tree t) { 116 if (!has_undefined_value_p (t)) 117 return false; 118 if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t))) 119 return false; 120 return true; 121} 122 123/* Emit warnings for uninitialized variables. This is done in two passes. 124 125 The first pass notices real uses of SSA names with undefined values. 126 Such uses are unconditionally uninitialized, and we can be certain that 127 such a use is a mistake. This pass is run before most optimizations, 128 so that we catch as many as we can. 129 130 The second pass follows PHI nodes to find uses that are potentially 131 uninitialized. In this case we can't necessarily prove that the use 132 is really uninitialized. This pass is run after most optimizations, 133 so that we thread as many jumps and possible, and delete as much dead 134 code as possible, in order to reduce false positives. We also look 135 again for plain uninitialized variables, since optimization may have 136 changed conditionally uninitialized to unconditionally uninitialized. */ 137 138/* Emit a warning for EXPR based on variable VAR at the point in the 139 program T, an SSA_NAME, is used being uninitialized. The exact 140 warning text is in MSGID and DATA is the gimple stmt with info about 141 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX 142 gives which argument of the phi node to take the location from. WC 143 is the warning code. */ 144 145static void 146warn_uninit (enum opt_code wc, tree t, tree expr, tree var, 147 const char *gmsgid, void *data, location_t phiarg_loc) 148{ 149 gimple context = (gimple) data; 150 location_t location, cfun_loc; 151 expanded_location xloc, floc; 152 153 /* Ignore COMPLEX_EXPR as initializing only a part of a complex 154 turns in a COMPLEX_EXPR with the not initialized part being 155 set to its previous (undefined) value. */ 156 if (is_gimple_assign (context) 157 && gimple_assign_rhs_code (context) == COMPLEX_EXPR) 158 return; 159 if (!has_undefined_value_p (t)) 160 return; 161 162 /* TREE_NO_WARNING either means we already warned, or the front end 163 wishes to suppress the warning. */ 164 if ((context 165 && (gimple_no_warning_p (context) 166 || (gimple_assign_single_p (context) 167 && TREE_NO_WARNING (gimple_assign_rhs1 (context))))) 168 || TREE_NO_WARNING (expr)) 169 return; 170 171 if (context != NULL && gimple_has_location (context)) 172 location = gimple_location (context); 173 else if (phiarg_loc != UNKNOWN_LOCATION) 174 location = phiarg_loc; 175 else 176 location = DECL_SOURCE_LOCATION (var); 177 location = linemap_resolve_location (line_table, location, 178 LRK_SPELLING_LOCATION, 179 NULL); 180 cfun_loc = DECL_SOURCE_LOCATION (cfun->decl); 181 xloc = expand_location (location); 182 floc = expand_location (cfun_loc); 183 if (warning_at (location, wc, gmsgid, expr)) 184 { 185 TREE_NO_WARNING (expr) = 1; 186 187 if (location == DECL_SOURCE_LOCATION (var)) 188 return; 189 if (xloc.file != floc.file 190 || linemap_location_before_p (line_table, 191 location, cfun_loc) 192 || linemap_location_before_p (line_table, 193 cfun->function_end_locus, 194 location)) 195 inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var); 196 } 197} 198 199static unsigned int 200warn_uninitialized_vars (bool warn_possibly_uninitialized) 201{ 202 gimple_stmt_iterator gsi; 203 basic_block bb; 204 205 FOR_EACH_BB_FN (bb, cfun) 206 { 207 bool always_executed = dominated_by_p (CDI_POST_DOMINATORS, 208 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)), bb); 209 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 210 { 211 gimple stmt = gsi_stmt (gsi); 212 use_operand_p use_p; 213 ssa_op_iter op_iter; 214 tree use; 215 216 if (is_gimple_debug (stmt)) 217 continue; 218 219 /* We only do data flow with SSA_NAMEs, so that's all we 220 can warn about. */ 221 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE) 222 { 223 use = USE_FROM_PTR (use_p); 224 if (always_executed) 225 warn_uninit (OPT_Wuninitialized, use, 226 SSA_NAME_VAR (use), SSA_NAME_VAR (use), 227 "%qD is used uninitialized in this function", 228 stmt, UNKNOWN_LOCATION); 229 else if (warn_possibly_uninitialized) 230 warn_uninit (OPT_Wmaybe_uninitialized, use, 231 SSA_NAME_VAR (use), SSA_NAME_VAR (use), 232 "%qD may be used uninitialized in this function", 233 stmt, UNKNOWN_LOCATION); 234 } 235 236 /* For memory the only cheap thing we can do is see if we 237 have a use of the default def of the virtual operand. 238 ??? Not so cheap would be to use the alias oracle via 239 walk_aliased_vdefs, if we don't find any aliasing vdef 240 warn as is-used-uninitialized, if we don't find an aliasing 241 vdef that kills our use (stmt_kills_ref_p), warn as 242 may-be-used-uninitialized. But this walk is quadratic and 243 so must be limited which means we would miss warning 244 opportunities. */ 245 use = gimple_vuse (stmt); 246 if (use 247 && gimple_assign_single_p (stmt) 248 && !gimple_vdef (stmt) 249 && SSA_NAME_IS_DEFAULT_DEF (use)) 250 { 251 tree rhs = gimple_assign_rhs1 (stmt); 252 tree base = get_base_address (rhs); 253 254 /* Do not warn if it can be initialized outside this function. */ 255 if (TREE_CODE (base) != VAR_DECL 256 || DECL_HARD_REGISTER (base) 257 || is_global_var (base)) 258 continue; 259 260 if (always_executed) 261 warn_uninit (OPT_Wuninitialized, use, 262 gimple_assign_rhs1 (stmt), base, 263 "%qE is used uninitialized in this function", 264 stmt, UNKNOWN_LOCATION); 265 else if (warn_possibly_uninitialized) 266 warn_uninit (OPT_Wmaybe_uninitialized, use, 267 gimple_assign_rhs1 (stmt), base, 268 "%qE may be used uninitialized in this function", 269 stmt, UNKNOWN_LOCATION); 270 } 271 } 272 } 273 274 return 0; 275} 276 277/* Checks if the operand OPND of PHI is defined by 278 another phi with one operand defined by this PHI, 279 but the rest operands are all defined. If yes, 280 returns true to skip this this operand as being 281 redundant. Can be enhanced to be more general. */ 282 283static bool 284can_skip_redundant_opnd (tree opnd, gimple phi) 285{ 286 gimple op_def; 287 tree phi_def; 288 int i, n; 289 290 phi_def = gimple_phi_result (phi); 291 op_def = SSA_NAME_DEF_STMT (opnd); 292 if (gimple_code (op_def) != GIMPLE_PHI) 293 return false; 294 n = gimple_phi_num_args (op_def); 295 for (i = 0; i < n; ++i) 296 { 297 tree op = gimple_phi_arg_def (op_def, i); 298 if (TREE_CODE (op) != SSA_NAME) 299 continue; 300 if (op != phi_def && uninit_undefined_value_p (op)) 301 return false; 302 } 303 304 return true; 305} 306 307/* Returns a bit mask holding the positions of arguments in PHI 308 that have empty (or possibly empty) definitions. */ 309 310static unsigned 311compute_uninit_opnds_pos (gphi *phi) 312{ 313 size_t i, n; 314 unsigned uninit_opnds = 0; 315 316 n = gimple_phi_num_args (phi); 317 /* Bail out for phi with too many args. */ 318 if (n > 32) 319 return 0; 320 321 for (i = 0; i < n; ++i) 322 { 323 tree op = gimple_phi_arg_def (phi, i); 324 if (TREE_CODE (op) == SSA_NAME 325 && uninit_undefined_value_p (op) 326 && !can_skip_redundant_opnd (op, phi)) 327 { 328 if (cfun->has_nonlocal_label || cfun->calls_setjmp) 329 { 330 /* Ignore SSA_NAMEs that appear on abnormal edges 331 somewhere. */ 332 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op)) 333 continue; 334 } 335 MASK_SET_BIT (uninit_opnds, i); 336 } 337 } 338 return uninit_opnds; 339} 340 341/* Find the immediate postdominator PDOM of the specified 342 basic block BLOCK. */ 343 344static inline basic_block 345find_pdom (basic_block block) 346{ 347 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun)) 348 return EXIT_BLOCK_PTR_FOR_FN (cfun); 349 else 350 { 351 basic_block bb 352 = get_immediate_dominator (CDI_POST_DOMINATORS, block); 353 if (! bb) 354 return EXIT_BLOCK_PTR_FOR_FN (cfun); 355 return bb; 356 } 357} 358 359/* Find the immediate DOM of the specified 360 basic block BLOCK. */ 361 362static inline basic_block 363find_dom (basic_block block) 364{ 365 if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 366 return ENTRY_BLOCK_PTR_FOR_FN (cfun); 367 else 368 { 369 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block); 370 if (! bb) 371 return ENTRY_BLOCK_PTR_FOR_FN (cfun); 372 return bb; 373 } 374} 375 376/* Returns true if BB1 is postdominating BB2 and BB1 is 377 not a loop exit bb. The loop exit bb check is simple and does 378 not cover all cases. */ 379 380static bool 381is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2) 382{ 383 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1)) 384 return false; 385 386 if (single_pred_p (bb1) && !single_succ_p (bb2)) 387 return false; 388 389 return true; 390} 391 392/* Find the closest postdominator of a specified BB, which is control 393 equivalent to BB. */ 394 395static inline basic_block 396find_control_equiv_block (basic_block bb) 397{ 398 basic_block pdom; 399 400 pdom = find_pdom (bb); 401 402 /* Skip the postdominating bb that is also loop exit. */ 403 if (!is_non_loop_exit_postdominating (pdom, bb)) 404 return NULL; 405 406 if (dominated_by_p (CDI_DOMINATORS, pdom, bb)) 407 return pdom; 408 409 return NULL; 410} 411 412#define MAX_NUM_CHAINS 8 413#define MAX_CHAIN_LEN 5 414#define MAX_POSTDOM_CHECK 8 415#define MAX_SWITCH_CASES 40 416 417/* Computes the control dependence chains (paths of edges) 418 for DEP_BB up to the dominating basic block BB (the head node of a 419 chain should be dominated by it). CD_CHAINS is pointer to an 420 array holding the result chains. CUR_CD_CHAIN is the current 421 chain being computed. *NUM_CHAINS is total number of chains. The 422 function returns true if the information is successfully computed, 423 return false if there is no control dependence or not computed. */ 424 425static bool 426compute_control_dep_chain (basic_block bb, basic_block dep_bb, 427 vec<edge> *cd_chains, 428 size_t *num_chains, 429 vec<edge> *cur_cd_chain, 430 int *num_calls) 431{ 432 edge_iterator ei; 433 edge e; 434 size_t i; 435 bool found_cd_chain = false; 436 size_t cur_chain_len = 0; 437 438 if (EDGE_COUNT (bb->succs) < 2) 439 return false; 440 441 if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS)) 442 return false; 443 ++*num_calls; 444 445 /* Could use a set instead. */ 446 cur_chain_len = cur_cd_chain->length (); 447 if (cur_chain_len > MAX_CHAIN_LEN) 448 return false; 449 450 for (i = 0; i < cur_chain_len; i++) 451 { 452 edge e = (*cur_cd_chain)[i]; 453 /* Cycle detected. */ 454 if (e->src == bb) 455 return false; 456 } 457 458 FOR_EACH_EDGE (e, ei, bb->succs) 459 { 460 basic_block cd_bb; 461 int post_dom_check = 0; 462 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL)) 463 continue; 464 465 cd_bb = e->dest; 466 cur_cd_chain->safe_push (e); 467 while (!is_non_loop_exit_postdominating (cd_bb, bb)) 468 { 469 if (cd_bb == dep_bb) 470 { 471 /* Found a direct control dependence. */ 472 if (*num_chains < MAX_NUM_CHAINS) 473 { 474 cd_chains[*num_chains] = cur_cd_chain->copy (); 475 (*num_chains)++; 476 } 477 found_cd_chain = true; 478 /* Check path from next edge. */ 479 break; 480 } 481 482 /* Now check if DEP_BB is indirectly control dependent on BB. */ 483 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains, 484 num_chains, cur_cd_chain, num_calls)) 485 { 486 found_cd_chain = true; 487 break; 488 } 489 490 cd_bb = find_pdom (cd_bb); 491 post_dom_check++; 492 if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || post_dom_check > 493 MAX_POSTDOM_CHECK) 494 break; 495 } 496 cur_cd_chain->pop (); 497 gcc_assert (cur_cd_chain->length () == cur_chain_len); 498 } 499 gcc_assert (cur_cd_chain->length () == cur_chain_len); 500 501 return found_cd_chain; 502} 503 504/* The type to represent a simple predicate */ 505 506typedef struct use_def_pred_info 507{ 508 tree pred_lhs; 509 tree pred_rhs; 510 enum tree_code cond_code; 511 bool invert; 512} pred_info; 513 514/* The type to represent a sequence of predicates grouped 515 with .AND. operation. */ 516 517typedef vec<pred_info, va_heap, vl_ptr> pred_chain; 518 519/* The type to represent a sequence of pred_chains grouped 520 with .OR. operation. */ 521 522typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union; 523 524/* Converts the chains of control dependence edges into a set of 525 predicates. A control dependence chain is represented by a vector 526 edges. DEP_CHAINS points to an array of dependence chains. 527 NUM_CHAINS is the size of the chain array. One edge in a dependence 528 chain is mapped to predicate expression represented by pred_info 529 type. One dependence chain is converted to a composite predicate that 530 is the result of AND operation of pred_info mapped to each edge. 531 A composite predicate is presented by a vector of pred_info. On 532 return, *PREDS points to the resulting array of composite predicates. 533 *NUM_PREDS is the number of composite predictes. */ 534 535static bool 536convert_control_dep_chain_into_preds (vec<edge> *dep_chains, 537 size_t num_chains, 538 pred_chain_union *preds) 539{ 540 bool has_valid_pred = false; 541 size_t i, j; 542 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS) 543 return false; 544 545 /* Now convert the control dep chain into a set 546 of predicates. */ 547 preds->reserve (num_chains); 548 549 for (i = 0; i < num_chains; i++) 550 { 551 vec<edge> one_cd_chain = dep_chains[i]; 552 553 has_valid_pred = false; 554 pred_chain t_chain = vNULL; 555 for (j = 0; j < one_cd_chain.length (); j++) 556 { 557 gimple cond_stmt; 558 gimple_stmt_iterator gsi; 559 basic_block guard_bb; 560 pred_info one_pred; 561 edge e; 562 563 e = one_cd_chain[j]; 564 guard_bb = e->src; 565 gsi = gsi_last_bb (guard_bb); 566 if (gsi_end_p (gsi)) 567 { 568 has_valid_pred = false; 569 break; 570 } 571 cond_stmt = gsi_stmt (gsi); 572 if (is_gimple_call (cond_stmt) 573 && EDGE_COUNT (e->src->succs) >= 2) 574 { 575 /* Ignore EH edge. Can add assertion 576 on the other edge's flag. */ 577 continue; 578 } 579 /* Skip if there is essentially one succesor. */ 580 if (EDGE_COUNT (e->src->succs) == 2) 581 { 582 edge e1; 583 edge_iterator ei1; 584 bool skip = false; 585 586 FOR_EACH_EDGE (e1, ei1, e->src->succs) 587 { 588 if (EDGE_COUNT (e1->dest->succs) == 0) 589 { 590 skip = true; 591 break; 592 } 593 } 594 if (skip) 595 continue; 596 } 597 if (gimple_code (cond_stmt) == GIMPLE_COND) 598 { 599 one_pred.pred_lhs = gimple_cond_lhs (cond_stmt); 600 one_pred.pred_rhs = gimple_cond_rhs (cond_stmt); 601 one_pred.cond_code = gimple_cond_code (cond_stmt); 602 one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE); 603 t_chain.safe_push (one_pred); 604 has_valid_pred = true; 605 } 606 else if (gswitch *gs = dyn_cast <gswitch *> (cond_stmt)) 607 { 608 /* Avoid quadratic behavior. */ 609 if (gimple_switch_num_labels (gs) > MAX_SWITCH_CASES) 610 { 611 has_valid_pred = false; 612 break; 613 } 614 /* Find the case label. */ 615 tree l = NULL_TREE; 616 unsigned idx; 617 for (idx = 0; idx < gimple_switch_num_labels (gs); ++idx) 618 { 619 tree tl = gimple_switch_label (gs, idx); 620 if (e->dest == label_to_block (CASE_LABEL (tl))) 621 { 622 if (!l) 623 l = tl; 624 else 625 { 626 l = NULL_TREE; 627 break; 628 } 629 } 630 } 631 /* If more than one label reaches this block or the case 632 label doesn't have a single value (like the default one) 633 fail. */ 634 if (!l 635 || !CASE_LOW (l) 636 || (CASE_HIGH (l) && !operand_equal_p (CASE_LOW (l), 637 CASE_HIGH (l), 0))) 638 { 639 has_valid_pred = false; 640 break; 641 } 642 one_pred.pred_lhs = gimple_switch_index (gs); 643 one_pred.pred_rhs = CASE_LOW (l); 644 one_pred.cond_code = EQ_EXPR; 645 one_pred.invert = false; 646 t_chain.safe_push (one_pred); 647 has_valid_pred = true; 648 } 649 else 650 { 651 has_valid_pred = false; 652 break; 653 } 654 } 655 656 if (!has_valid_pred) 657 break; 658 else 659 preds->safe_push (t_chain); 660 } 661 return has_valid_pred; 662} 663 664/* Computes all control dependence chains for USE_BB. The control 665 dependence chains are then converted to an array of composite 666 predicates pointed to by PREDS. PHI_BB is the basic block of 667 the phi whose result is used in USE_BB. */ 668 669static bool 670find_predicates (pred_chain_union *preds, 671 basic_block phi_bb, 672 basic_block use_bb) 673{ 674 size_t num_chains = 0, i; 675 int num_calls = 0; 676 vec<edge> dep_chains[MAX_NUM_CHAINS]; 677 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain; 678 bool has_valid_pred = false; 679 basic_block cd_root = 0; 680 681 /* First find the closest bb that is control equivalent to PHI_BB 682 that also dominates USE_BB. */ 683 cd_root = phi_bb; 684 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root)) 685 { 686 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root); 687 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb)) 688 cd_root = ctrl_eq_bb; 689 else 690 break; 691 } 692 693 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains, 694 &cur_chain, &num_calls); 695 696 has_valid_pred 697 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds); 698 for (i = 0; i < num_chains; i++) 699 dep_chains[i].release (); 700 return has_valid_pred; 701} 702 703/* Computes the set of incoming edges of PHI that have non empty 704 definitions of a phi chain. The collection will be done 705 recursively on operands that are defined by phis. CD_ROOT 706 is the control dependence root. *EDGES holds the result, and 707 VISITED_PHIS is a pointer set for detecting cycles. */ 708 709static void 710collect_phi_def_edges (gphi *phi, basic_block cd_root, 711 vec<edge> *edges, 712 hash_set<gimple> *visited_phis) 713{ 714 size_t i, n; 715 edge opnd_edge; 716 tree opnd; 717 718 if (visited_phis->add (phi)) 719 return; 720 721 n = gimple_phi_num_args (phi); 722 for (i = 0; i < n; i++) 723 { 724 opnd_edge = gimple_phi_arg_edge (phi, i); 725 opnd = gimple_phi_arg_def (phi, i); 726 727 if (TREE_CODE (opnd) != SSA_NAME) 728 { 729 if (dump_file && (dump_flags & TDF_DETAILS)) 730 { 731 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i); 732 print_gimple_stmt (dump_file, phi, 0, 0); 733 } 734 edges->safe_push (opnd_edge); 735 } 736 else 737 { 738 gimple def = SSA_NAME_DEF_STMT (opnd); 739 740 if (gimple_code (def) == GIMPLE_PHI 741 && dominated_by_p (CDI_DOMINATORS, 742 gimple_bb (def), cd_root)) 743 collect_phi_def_edges (as_a <gphi *> (def), cd_root, edges, 744 visited_phis); 745 else if (!uninit_undefined_value_p (opnd)) 746 { 747 if (dump_file && (dump_flags & TDF_DETAILS)) 748 { 749 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i); 750 print_gimple_stmt (dump_file, phi, 0, 0); 751 } 752 edges->safe_push (opnd_edge); 753 } 754 } 755 } 756} 757 758/* For each use edge of PHI, computes all control dependence chains. 759 The control dependence chains are then converted to an array of 760 composite predicates pointed to by PREDS. */ 761 762static bool 763find_def_preds (pred_chain_union *preds, gphi *phi) 764{ 765 size_t num_chains = 0, i, n; 766 vec<edge> dep_chains[MAX_NUM_CHAINS]; 767 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain; 768 vec<edge> def_edges = vNULL; 769 bool has_valid_pred = false; 770 basic_block phi_bb, cd_root = 0; 771 772 phi_bb = gimple_bb (phi); 773 /* First find the closest dominating bb to be 774 the control dependence root */ 775 cd_root = find_dom (phi_bb); 776 if (!cd_root) 777 return false; 778 779 hash_set<gimple> visited_phis; 780 collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis); 781 782 n = def_edges.length (); 783 if (n == 0) 784 return false; 785 786 for (i = 0; i < n; i++) 787 { 788 size_t prev_nc, j; 789 int num_calls = 0; 790 edge opnd_edge; 791 792 opnd_edge = def_edges[i]; 793 prev_nc = num_chains; 794 compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains, 795 &num_chains, &cur_chain, &num_calls); 796 797 /* Now update the newly added chains with 798 the phi operand edge: */ 799 if (EDGE_COUNT (opnd_edge->src->succs) > 1) 800 { 801 if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS) 802 dep_chains[num_chains++] = vNULL; 803 for (j = prev_nc; j < num_chains; j++) 804 dep_chains[j].safe_push (opnd_edge); 805 } 806 } 807 808 has_valid_pred 809 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds); 810 for (i = 0; i < num_chains; i++) 811 dep_chains[i].release (); 812 return has_valid_pred; 813} 814 815/* Dumps the predicates (PREDS) for USESTMT. */ 816 817static void 818dump_predicates (gimple usestmt, pred_chain_union preds, 819 const char* msg) 820{ 821 size_t i, j; 822 pred_chain one_pred_chain = vNULL; 823 fprintf (dump_file, "%s", msg); 824 print_gimple_stmt (dump_file, usestmt, 0, 0); 825 fprintf (dump_file, "is guarded by :\n\n"); 826 size_t num_preds = preds.length (); 827 /* Do some dumping here: */ 828 for (i = 0; i < num_preds; i++) 829 { 830 size_t np; 831 832 one_pred_chain = preds[i]; 833 np = one_pred_chain.length (); 834 835 for (j = 0; j < np; j++) 836 { 837 pred_info one_pred = one_pred_chain[j]; 838 if (one_pred.invert) 839 fprintf (dump_file, " (.NOT.) "); 840 print_generic_expr (dump_file, one_pred.pred_lhs, 0); 841 fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code)); 842 print_generic_expr (dump_file, one_pred.pred_rhs, 0); 843 if (j < np - 1) 844 fprintf (dump_file, " (.AND.) "); 845 else 846 fprintf (dump_file, "\n"); 847 } 848 if (i < num_preds - 1) 849 fprintf (dump_file, "(.OR.)\n"); 850 else 851 fprintf (dump_file, "\n\n"); 852 } 853} 854 855/* Destroys the predicate set *PREDS. */ 856 857static void 858destroy_predicate_vecs (pred_chain_union preds) 859{ 860 size_t i; 861 862 size_t n = preds.length (); 863 for (i = 0; i < n; i++) 864 preds[i].release (); 865 preds.release (); 866} 867 868 869/* Computes the 'normalized' conditional code with operand 870 swapping and condition inversion. */ 871 872static enum tree_code 873get_cmp_code (enum tree_code orig_cmp_code, 874 bool swap_cond, bool invert) 875{ 876 enum tree_code tc = orig_cmp_code; 877 878 if (swap_cond) 879 tc = swap_tree_comparison (orig_cmp_code); 880 if (invert) 881 tc = invert_tree_comparison (tc, false); 882 883 switch (tc) 884 { 885 case LT_EXPR: 886 case LE_EXPR: 887 case GT_EXPR: 888 case GE_EXPR: 889 case EQ_EXPR: 890 case NE_EXPR: 891 break; 892 default: 893 return ERROR_MARK; 894 } 895 return tc; 896} 897 898/* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e. 899 all values in the range satisfies (x CMPC BOUNDARY) == true. */ 900 901static bool 902is_value_included_in (tree val, tree boundary, enum tree_code cmpc) 903{ 904 bool inverted = false; 905 bool is_unsigned; 906 bool result; 907 908 /* Only handle integer constant here. */ 909 if (TREE_CODE (val) != INTEGER_CST 910 || TREE_CODE (boundary) != INTEGER_CST) 911 return true; 912 913 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val)); 914 915 if (cmpc == GE_EXPR || cmpc == GT_EXPR 916 || cmpc == NE_EXPR) 917 { 918 cmpc = invert_tree_comparison (cmpc, false); 919 inverted = true; 920 } 921 922 if (is_unsigned) 923 { 924 if (cmpc == EQ_EXPR) 925 result = tree_int_cst_equal (val, boundary); 926 else if (cmpc == LT_EXPR) 927 result = tree_int_cst_lt (val, boundary); 928 else 929 { 930 gcc_assert (cmpc == LE_EXPR); 931 result = tree_int_cst_le (val, boundary); 932 } 933 } 934 else 935 { 936 if (cmpc == EQ_EXPR) 937 result = tree_int_cst_equal (val, boundary); 938 else if (cmpc == LT_EXPR) 939 result = tree_int_cst_lt (val, boundary); 940 else 941 { 942 gcc_assert (cmpc == LE_EXPR); 943 result = (tree_int_cst_equal (val, boundary) 944 || tree_int_cst_lt (val, boundary)); 945 } 946 } 947 948 if (inverted) 949 result ^= 1; 950 951 return result; 952} 953 954/* Returns true if PRED is common among all the predicate 955 chains (PREDS) (and therefore can be factored out). 956 NUM_PRED_CHAIN is the size of array PREDS. */ 957 958static bool 959find_matching_predicate_in_rest_chains (pred_info pred, 960 pred_chain_union preds, 961 size_t num_pred_chains) 962{ 963 size_t i, j, n; 964 965 /* Trival case. */ 966 if (num_pred_chains == 1) 967 return true; 968 969 for (i = 1; i < num_pred_chains; i++) 970 { 971 bool found = false; 972 pred_chain one_chain = preds[i]; 973 n = one_chain.length (); 974 for (j = 0; j < n; j++) 975 { 976 pred_info pred2 = one_chain[j]; 977 /* Can relax the condition comparison to not 978 use address comparison. However, the most common 979 case is that multiple control dependent paths share 980 a common path prefix, so address comparison should 981 be ok. */ 982 983 if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0) 984 && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0) 985 && pred2.invert == pred.invert) 986 { 987 found = true; 988 break; 989 } 990 } 991 if (!found) 992 return false; 993 } 994 return true; 995} 996 997/* Forward declaration. */ 998static bool 999is_use_properly_guarded (gimple use_stmt, 1000 basic_block use_bb, 1001 gphi *phi, 1002 unsigned uninit_opnds, 1003 hash_set<gphi *> *visited_phis); 1004 1005/* Returns true if all uninitialized opnds are pruned. Returns false 1006 otherwise. PHI is the phi node with uninitialized operands, 1007 UNINIT_OPNDS is the bitmap of the uninitialize operand positions, 1008 FLAG_DEF is the statement defining the flag guarding the use of the 1009 PHI output, BOUNDARY_CST is the const value used in the predicate 1010 associated with the flag, CMP_CODE is the comparison code used in 1011 the predicate, VISITED_PHIS is the pointer set of phis visited, and 1012 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions 1013 that are also phis. 1014 1015 Example scenario: 1016 1017 BB1: 1018 flag_1 = phi <0, 1> // (1) 1019 var_1 = phi <undef, some_val> 1020 1021 1022 BB2: 1023 flag_2 = phi <0, flag_1, flag_1> // (2) 1024 var_2 = phi <undef, var_1, var_1> 1025 if (flag_2 == 1) 1026 goto BB3; 1027 1028 BB3: 1029 use of var_2 // (3) 1030 1031 Because some flag arg in (1) is not constant, if we do not look into the 1032 flag phis recursively, it is conservatively treated as unknown and var_1 1033 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized 1034 a false warning will be emitted. Checking recursively into (1), the compiler can 1035 find out that only some_val (which is defined) can flow into (3) which is OK. 1036 1037*/ 1038 1039static bool 1040prune_uninit_phi_opnds_in_unrealizable_paths (gphi *phi, 1041 unsigned uninit_opnds, 1042 gphi *flag_def, 1043 tree boundary_cst, 1044 enum tree_code cmp_code, 1045 hash_set<gphi *> *visited_phis, 1046 bitmap *visited_flag_phis) 1047{ 1048 unsigned i; 1049 1050 for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++) 1051 { 1052 tree flag_arg; 1053 1054 if (!MASK_TEST_BIT (uninit_opnds, i)) 1055 continue; 1056 1057 flag_arg = gimple_phi_arg_def (flag_def, i); 1058 if (!is_gimple_constant (flag_arg)) 1059 { 1060 gphi *flag_arg_def, *phi_arg_def; 1061 tree phi_arg; 1062 unsigned uninit_opnds_arg_phi; 1063 1064 if (TREE_CODE (flag_arg) != SSA_NAME) 1065 return false; 1066 flag_arg_def = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (flag_arg)); 1067 if (!flag_arg_def) 1068 return false; 1069 1070 phi_arg = gimple_phi_arg_def (phi, i); 1071 if (TREE_CODE (phi_arg) != SSA_NAME) 1072 return false; 1073 1074 phi_arg_def = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (phi_arg)); 1075 if (!phi_arg_def) 1076 return false; 1077 1078 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def)) 1079 return false; 1080 1081 if (!*visited_flag_phis) 1082 *visited_flag_phis = BITMAP_ALLOC (NULL); 1083 1084 if (bitmap_bit_p (*visited_flag_phis, 1085 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)))) 1086 return false; 1087 1088 bitmap_set_bit (*visited_flag_phis, 1089 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))); 1090 1091 /* Now recursively prune the uninitialized phi args. */ 1092 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def); 1093 if (!prune_uninit_phi_opnds_in_unrealizable_paths 1094 (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def, 1095 boundary_cst, cmp_code, visited_phis, visited_flag_phis)) 1096 return false; 1097 1098 bitmap_clear_bit (*visited_flag_phis, 1099 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))); 1100 continue; 1101 } 1102 1103 /* Now check if the constant is in the guarded range. */ 1104 if (is_value_included_in (flag_arg, boundary_cst, cmp_code)) 1105 { 1106 tree opnd; 1107 gimple opnd_def; 1108 1109 /* Now that we know that this undefined edge is not 1110 pruned. If the operand is defined by another phi, 1111 we can further prune the incoming edges of that 1112 phi by checking the predicates of this operands. */ 1113 1114 opnd = gimple_phi_arg_def (phi, i); 1115 opnd_def = SSA_NAME_DEF_STMT (opnd); 1116 if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def)) 1117 { 1118 edge opnd_edge; 1119 unsigned uninit_opnds2 1120 = compute_uninit_opnds_pos (opnd_def_phi); 1121 if (!MASK_EMPTY (uninit_opnds2)) 1122 { 1123 opnd_edge = gimple_phi_arg_edge (phi, i); 1124 if (!is_use_properly_guarded (phi, 1125 opnd_edge->src, 1126 opnd_def_phi, 1127 uninit_opnds2, 1128 visited_phis)) 1129 return false; 1130 } 1131 } 1132 else 1133 return false; 1134 } 1135 } 1136 1137 return true; 1138} 1139 1140/* A helper function that determines if the predicate set 1141 of the use is not overlapping with that of the uninit paths. 1142 The most common senario of guarded use is in Example 1: 1143 Example 1: 1144 if (some_cond) 1145 { 1146 x = ...; 1147 flag = true; 1148 } 1149 1150 ... some code ... 1151 1152 if (flag) 1153 use (x); 1154 1155 The real world examples are usually more complicated, but similar 1156 and usually result from inlining: 1157 1158 bool init_func (int * x) 1159 { 1160 if (some_cond) 1161 return false; 1162 *x = .. 1163 return true; 1164 } 1165 1166 void foo(..) 1167 { 1168 int x; 1169 1170 if (!init_func(&x)) 1171 return; 1172 1173 .. some_code ... 1174 use (x); 1175 } 1176 1177 Another possible use scenario is in the following trivial example: 1178 1179 Example 2: 1180 if (n > 0) 1181 x = 1; 1182 ... 1183 if (n > 0) 1184 { 1185 if (m < 2) 1186 .. = x; 1187 } 1188 1189 Predicate analysis needs to compute the composite predicate: 1190 1191 1) 'x' use predicate: (n > 0) .AND. (m < 2) 1192 2) 'x' default value (non-def) predicate: .NOT. (n > 0) 1193 (the predicate chain for phi operand defs can be computed 1194 starting from a bb that is control equivalent to the phi's 1195 bb and is dominating the operand def.) 1196 1197 and check overlapping: 1198 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0)) 1199 <==> false 1200 1201 This implementation provides framework that can handle 1202 scenarios. (Note that many simple cases are handled properly 1203 without the predicate analysis -- this is due to jump threading 1204 transformation which eliminates the merge point thus makes 1205 path sensitive analysis unnecessary.) 1206 1207 NUM_PREDS is the number is the number predicate chains, PREDS is 1208 the array of chains, PHI is the phi node whose incoming (undefined) 1209 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding 1210 uninit operand positions. VISITED_PHIS is the pointer set of phi 1211 stmts being checked. */ 1212 1213 1214static bool 1215use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds, 1216 gphi *phi, unsigned uninit_opnds, 1217 hash_set<gphi *> *visited_phis) 1218{ 1219 unsigned int i, n; 1220 gimple flag_def = 0; 1221 tree boundary_cst = 0; 1222 enum tree_code cmp_code; 1223 bool swap_cond = false; 1224 bool invert = false; 1225 pred_chain the_pred_chain = vNULL; 1226 bitmap visited_flag_phis = NULL; 1227 bool all_pruned = false; 1228 size_t num_preds = preds.length (); 1229 1230 gcc_assert (num_preds > 0); 1231 /* Find within the common prefix of multiple predicate chains 1232 a predicate that is a comparison of a flag variable against 1233 a constant. */ 1234 the_pred_chain = preds[0]; 1235 n = the_pred_chain.length (); 1236 for (i = 0; i < n; i++) 1237 { 1238 tree cond_lhs, cond_rhs, flag = 0; 1239 1240 pred_info the_pred = the_pred_chain[i]; 1241 1242 invert = the_pred.invert; 1243 cond_lhs = the_pred.pred_lhs; 1244 cond_rhs = the_pred.pred_rhs; 1245 cmp_code = the_pred.cond_code; 1246 1247 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME 1248 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs)) 1249 { 1250 boundary_cst = cond_rhs; 1251 flag = cond_lhs; 1252 } 1253 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME 1254 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs)) 1255 { 1256 boundary_cst = cond_lhs; 1257 flag = cond_rhs; 1258 swap_cond = true; 1259 } 1260 1261 if (!flag) 1262 continue; 1263 1264 flag_def = SSA_NAME_DEF_STMT (flag); 1265 1266 if (!flag_def) 1267 continue; 1268 1269 if ((gimple_code (flag_def) == GIMPLE_PHI) 1270 && (gimple_bb (flag_def) == gimple_bb (phi)) 1271 && find_matching_predicate_in_rest_chains (the_pred, preds, 1272 num_preds)) 1273 break; 1274 1275 flag_def = 0; 1276 } 1277 1278 if (!flag_def) 1279 return false; 1280 1281 /* Now check all the uninit incoming edge has a constant flag value 1282 that is in conflict with the use guard/predicate. */ 1283 cmp_code = get_cmp_code (cmp_code, swap_cond, invert); 1284 1285 if (cmp_code == ERROR_MARK) 1286 return false; 1287 1288 all_pruned = prune_uninit_phi_opnds_in_unrealizable_paths (phi, 1289 uninit_opnds, 1290 as_a <gphi *> (flag_def), 1291 boundary_cst, 1292 cmp_code, 1293 visited_phis, 1294 &visited_flag_phis); 1295 1296 if (visited_flag_phis) 1297 BITMAP_FREE (visited_flag_phis); 1298 1299 return all_pruned; 1300} 1301 1302/* The helper function returns true if two predicates X1 and X2 1303 are equivalent. It assumes the expressions have already 1304 properly re-associated. */ 1305 1306static inline bool 1307pred_equal_p (pred_info x1, pred_info x2) 1308{ 1309 enum tree_code c1, c2; 1310 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0) 1311 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0)) 1312 return false; 1313 1314 c1 = x1.cond_code; 1315 if (x1.invert != x2.invert 1316 && TREE_CODE_CLASS (x2.cond_code) == tcc_comparison) 1317 c2 = invert_tree_comparison (x2.cond_code, false); 1318 else 1319 c2 = x2.cond_code; 1320 1321 return c1 == c2; 1322} 1323 1324/* Returns true if the predication is testing !=. */ 1325 1326static inline bool 1327is_neq_relop_p (pred_info pred) 1328{ 1329 1330 return (pred.cond_code == NE_EXPR && !pred.invert) 1331 || (pred.cond_code == EQ_EXPR && pred.invert); 1332} 1333 1334/* Returns true if pred is of the form X != 0. */ 1335 1336static inline bool 1337is_neq_zero_form_p (pred_info pred) 1338{ 1339 if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs) 1340 || TREE_CODE (pred.pred_lhs) != SSA_NAME) 1341 return false; 1342 return true; 1343} 1344 1345/* The helper function returns true if two predicates X1 1346 is equivalent to X2 != 0. */ 1347 1348static inline bool 1349pred_expr_equal_p (pred_info x1, tree x2) 1350{ 1351 if (!is_neq_zero_form_p (x1)) 1352 return false; 1353 1354 return operand_equal_p (x1.pred_lhs, x2, 0); 1355} 1356 1357/* Returns true of the domain of single predicate expression 1358 EXPR1 is a subset of that of EXPR2. Returns false if it 1359 can not be proved. */ 1360 1361static bool 1362is_pred_expr_subset_of (pred_info expr1, pred_info expr2) 1363{ 1364 enum tree_code code1, code2; 1365 1366 if (pred_equal_p (expr1, expr2)) 1367 return true; 1368 1369 if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST) 1370 || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST)) 1371 return false; 1372 1373 if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0)) 1374 return false; 1375 1376 code1 = expr1.cond_code; 1377 if (expr1.invert) 1378 code1 = invert_tree_comparison (code1, false); 1379 code2 = expr2.cond_code; 1380 if (expr2.invert) 1381 code2 = invert_tree_comparison (code2, false); 1382 1383 if ((code1 == EQ_EXPR || code1 == BIT_AND_EXPR) 1384 && code2 == BIT_AND_EXPR) 1385 return wi::eq_p (expr1.pred_rhs, 1386 wi::bit_and (expr1.pred_rhs, expr2.pred_rhs)); 1387 1388 if (code1 != code2 && code2 != NE_EXPR) 1389 return false; 1390 1391 if (is_value_included_in (expr1.pred_rhs, expr2.pred_rhs, code2)) 1392 return true; 1393 1394 return false; 1395} 1396 1397/* Returns true if the domain of PRED1 is a subset 1398 of that of PRED2. Returns false if it can not be proved so. */ 1399 1400static bool 1401is_pred_chain_subset_of (pred_chain pred1, 1402 pred_chain pred2) 1403{ 1404 size_t np1, np2, i1, i2; 1405 1406 np1 = pred1.length (); 1407 np2 = pred2.length (); 1408 1409 for (i2 = 0; i2 < np2; i2++) 1410 { 1411 bool found = false; 1412 pred_info info2 = pred2[i2]; 1413 for (i1 = 0; i1 < np1; i1++) 1414 { 1415 pred_info info1 = pred1[i1]; 1416 if (is_pred_expr_subset_of (info1, info2)) 1417 { 1418 found = true; 1419 break; 1420 } 1421 } 1422 if (!found) 1423 return false; 1424 } 1425 return true; 1426} 1427 1428/* Returns true if the domain defined by 1429 one pred chain ONE_PRED is a subset of the domain 1430 of *PREDS. It returns false if ONE_PRED's domain is 1431 not a subset of any of the sub-domains of PREDS 1432 (corresponding to each individual chains in it), even 1433 though it may be still be a subset of whole domain 1434 of PREDS which is the union (ORed) of all its subdomains. 1435 In other words, the result is conservative. */ 1436 1437static bool 1438is_included_in (pred_chain one_pred, pred_chain_union preds) 1439{ 1440 size_t i; 1441 size_t n = preds.length (); 1442 1443 for (i = 0; i < n; i++) 1444 { 1445 if (is_pred_chain_subset_of (one_pred, preds[i])) 1446 return true; 1447 } 1448 1449 return false; 1450} 1451 1452/* Compares two predicate sets PREDS1 and PREDS2 and returns 1453 true if the domain defined by PREDS1 is a superset 1454 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and 1455 PREDS2 respectively. The implementation chooses not to build 1456 generic trees (and relying on the folding capability of the 1457 compiler), but instead performs brute force comparison of 1458 individual predicate chains (won't be a compile time problem 1459 as the chains are pretty short). When the function returns 1460 false, it does not necessarily mean *PREDS1 is not a superset 1461 of *PREDS2, but mean it may not be so since the analysis can 1462 not prove it. In such cases, false warnings may still be 1463 emitted. */ 1464 1465static bool 1466is_superset_of (pred_chain_union preds1, pred_chain_union preds2) 1467{ 1468 size_t i, n2; 1469 pred_chain one_pred_chain = vNULL; 1470 1471 n2 = preds2.length (); 1472 1473 for (i = 0; i < n2; i++) 1474 { 1475 one_pred_chain = preds2[i]; 1476 if (!is_included_in (one_pred_chain, preds1)) 1477 return false; 1478 } 1479 1480 return true; 1481} 1482 1483/* Returns true if TC is AND or OR. */ 1484 1485static inline bool 1486is_and_or_or_p (enum tree_code tc, tree type) 1487{ 1488 return (tc == BIT_IOR_EXPR 1489 || (tc == BIT_AND_EXPR 1490 && (type == 0 || TREE_CODE (type) == BOOLEAN_TYPE))); 1491} 1492 1493/* Returns true if X1 is the negate of X2. */ 1494 1495static inline bool 1496pred_neg_p (pred_info x1, pred_info x2) 1497{ 1498 enum tree_code c1, c2; 1499 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0) 1500 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0)) 1501 return false; 1502 1503 c1 = x1.cond_code; 1504 if (x1.invert == x2.invert) 1505 c2 = invert_tree_comparison (x2.cond_code, false); 1506 else 1507 c2 = x2.cond_code; 1508 1509 return c1 == c2; 1510} 1511 1512/* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0); 1513 2) (X AND Y) OR (!X AND Y) is equivalent to Y; 1514 3) X OR (!X AND Y) is equivalent to (X OR Y); 1515 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to 1516 (x != 0 AND y != 0) 1517 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to 1518 (X AND Y) OR Z 1519 1520 PREDS is the predicate chains, and N is the number of chains. */ 1521 1522/* Helper function to implement rule 1 above. ONE_CHAIN is 1523 the AND predication to be simplified. */ 1524 1525static void 1526simplify_pred (pred_chain *one_chain) 1527{ 1528 size_t i, j, n; 1529 bool simplified = false; 1530 pred_chain s_chain = vNULL; 1531 1532 n = one_chain->length (); 1533 1534 for (i = 0; i < n; i++) 1535 { 1536 pred_info *a_pred = &(*one_chain)[i]; 1537 1538 if (!a_pred->pred_lhs) 1539 continue; 1540 if (!is_neq_zero_form_p (*a_pred)) 1541 continue; 1542 1543 gimple def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs); 1544 if (gimple_code (def_stmt) != GIMPLE_ASSIGN) 1545 continue; 1546 if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR) 1547 { 1548 for (j = 0; j < n; j++) 1549 { 1550 pred_info *b_pred = &(*one_chain)[j]; 1551 1552 if (!b_pred->pred_lhs) 1553 continue; 1554 if (!is_neq_zero_form_p (*b_pred)) 1555 continue; 1556 1557 if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt)) 1558 || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt))) 1559 { 1560 /* Mark a_pred for removal. */ 1561 a_pred->pred_lhs = NULL; 1562 a_pred->pred_rhs = NULL; 1563 simplified = true; 1564 break; 1565 } 1566 } 1567 } 1568 } 1569 1570 if (!simplified) 1571 return; 1572 1573 for (i = 0; i < n; i++) 1574 { 1575 pred_info *a_pred = &(*one_chain)[i]; 1576 if (!a_pred->pred_lhs) 1577 continue; 1578 s_chain.safe_push (*a_pred); 1579 } 1580 1581 one_chain->release (); 1582 *one_chain = s_chain; 1583} 1584 1585/* The helper function implements the rule 2 for the 1586 OR predicate PREDS. 1587 1588 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */ 1589 1590static bool 1591simplify_preds_2 (pred_chain_union *preds) 1592{ 1593 size_t i, j, n; 1594 bool simplified = false; 1595 pred_chain_union s_preds = vNULL; 1596 1597 /* (X AND Y) OR (!X AND Y) is equivalent to Y. 1598 (X AND Y) OR (X AND !Y) is equivalent to X. */ 1599 1600 n = preds->length (); 1601 for (i = 0; i < n; i++) 1602 { 1603 pred_info x, y; 1604 pred_chain *a_chain = &(*preds)[i]; 1605 1606 if (a_chain->length () != 2) 1607 continue; 1608 1609 x = (*a_chain)[0]; 1610 y = (*a_chain)[1]; 1611 1612 for (j = 0; j < n; j++) 1613 { 1614 pred_chain *b_chain; 1615 pred_info x2, y2; 1616 1617 if (j == i) 1618 continue; 1619 1620 b_chain = &(*preds)[j]; 1621 if (b_chain->length () != 2) 1622 continue; 1623 1624 x2 = (*b_chain)[0]; 1625 y2 = (*b_chain)[1]; 1626 1627 if (pred_equal_p (x, x2) && pred_neg_p (y, y2)) 1628 { 1629 /* Kill a_chain. */ 1630 a_chain->release (); 1631 b_chain->release (); 1632 b_chain->safe_push (x); 1633 simplified = true; 1634 break; 1635 } 1636 if (pred_neg_p (x, x2) && pred_equal_p (y, y2)) 1637 { 1638 /* Kill a_chain. */ 1639 a_chain->release (); 1640 b_chain->release (); 1641 b_chain->safe_push (y); 1642 simplified = true; 1643 break; 1644 } 1645 } 1646 } 1647 /* Now clean up the chain. */ 1648 if (simplified) 1649 { 1650 for (i = 0; i < n; i++) 1651 { 1652 if ((*preds)[i].is_empty ()) 1653 continue; 1654 s_preds.safe_push ((*preds)[i]); 1655 } 1656 preds->release (); 1657 (*preds) = s_preds; 1658 s_preds = vNULL; 1659 } 1660 1661 return simplified; 1662} 1663 1664/* The helper function implements the rule 2 for the 1665 OR predicate PREDS. 1666 1667 3) x OR (!x AND y) is equivalent to x OR y. */ 1668 1669static bool 1670simplify_preds_3 (pred_chain_union *preds) 1671{ 1672 size_t i, j, n; 1673 bool simplified = false; 1674 1675 /* Now iteratively simplify X OR (!X AND Z ..) 1676 into X OR (Z ...). */ 1677 1678 n = preds->length (); 1679 if (n < 2) 1680 return false; 1681 1682 for (i = 0; i < n; i++) 1683 { 1684 pred_info x; 1685 pred_chain *a_chain = &(*preds)[i]; 1686 1687 if (a_chain->length () != 1) 1688 continue; 1689 1690 x = (*a_chain)[0]; 1691 1692 for (j = 0; j < n; j++) 1693 { 1694 pred_chain *b_chain; 1695 pred_info x2; 1696 size_t k; 1697 1698 if (j == i) 1699 continue; 1700 1701 b_chain = &(*preds)[j]; 1702 if (b_chain->length () < 2) 1703 continue; 1704 1705 for (k = 0; k < b_chain->length (); k++) 1706 { 1707 x2 = (*b_chain)[k]; 1708 if (pred_neg_p (x, x2)) 1709 { 1710 b_chain->unordered_remove (k); 1711 simplified = true; 1712 break; 1713 } 1714 } 1715 } 1716 } 1717 return simplified; 1718} 1719 1720/* The helper function implements the rule 4 for the 1721 OR predicate PREDS. 1722 1723 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to 1724 (x != 0 ANd y != 0). */ 1725 1726static bool 1727simplify_preds_4 (pred_chain_union *preds) 1728{ 1729 size_t i, j, n; 1730 bool simplified = false; 1731 pred_chain_union s_preds = vNULL; 1732 gimple def_stmt; 1733 1734 n = preds->length (); 1735 for (i = 0; i < n; i++) 1736 { 1737 pred_info z; 1738 pred_chain *a_chain = &(*preds)[i]; 1739 1740 if (a_chain->length () != 1) 1741 continue; 1742 1743 z = (*a_chain)[0]; 1744 1745 if (!is_neq_zero_form_p (z)) 1746 continue; 1747 1748 def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs); 1749 if (gimple_code (def_stmt) != GIMPLE_ASSIGN) 1750 continue; 1751 1752 if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR) 1753 continue; 1754 1755 for (j = 0; j < n; j++) 1756 { 1757 pred_chain *b_chain; 1758 pred_info x2, y2; 1759 1760 if (j == i) 1761 continue; 1762 1763 b_chain = &(*preds)[j]; 1764 if (b_chain->length () != 2) 1765 continue; 1766 1767 x2 = (*b_chain)[0]; 1768 y2 = (*b_chain)[1]; 1769 if (!is_neq_zero_form_p (x2) 1770 || !is_neq_zero_form_p (y2)) 1771 continue; 1772 1773 if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt)) 1774 && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt))) 1775 || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt)) 1776 && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt)))) 1777 { 1778 /* Kill a_chain. */ 1779 a_chain->release (); 1780 simplified = true; 1781 break; 1782 } 1783 } 1784 } 1785 /* Now clean up the chain. */ 1786 if (simplified) 1787 { 1788 for (i = 0; i < n; i++) 1789 { 1790 if ((*preds)[i].is_empty ()) 1791 continue; 1792 s_preds.safe_push ((*preds)[i]); 1793 } 1794 preds->release (); 1795 (*preds) = s_preds; 1796 s_preds = vNULL; 1797 } 1798 1799 return simplified; 1800} 1801 1802 1803/* This function simplifies predicates in PREDS. */ 1804 1805static void 1806simplify_preds (pred_chain_union *preds, gimple use_or_def, bool is_use) 1807{ 1808 size_t i, n; 1809 bool changed = false; 1810 1811 if (dump_file && dump_flags & TDF_DETAILS) 1812 { 1813 fprintf (dump_file, "[BEFORE SIMPLICATION -- "); 1814 dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n"); 1815 } 1816 1817 for (i = 0; i < preds->length (); i++) 1818 simplify_pred (&(*preds)[i]); 1819 1820 n = preds->length (); 1821 if (n < 2) 1822 return; 1823 1824 do 1825 { 1826 changed = false; 1827 if (simplify_preds_2 (preds)) 1828 changed = true; 1829 1830 /* Now iteratively simplify X OR (!X AND Z ..) 1831 into X OR (Z ...). */ 1832 if (simplify_preds_3 (preds)) 1833 changed = true; 1834 1835 if (simplify_preds_4 (preds)) 1836 changed = true; 1837 1838 } while (changed); 1839 1840 return; 1841} 1842 1843/* This is a helper function which attempts to normalize predicate chains 1844 by following UD chains. It basically builds up a big tree of either IOR 1845 operations or AND operations, and convert the IOR tree into a 1846 pred_chain_union or BIT_AND tree into a pred_chain. 1847 Example: 1848 1849 _3 = _2 RELOP1 _1; 1850 _6 = _5 RELOP2 _4; 1851 _9 = _8 RELOP3 _7; 1852 _10 = _3 | _6; 1853 _12 = _9 | _0; 1854 _t = _10 | _12; 1855 1856 then _t != 0 will be normalized into a pred_chain_union 1857 1858 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0) 1859 1860 Similarly given, 1861 1862 _3 = _2 RELOP1 _1; 1863 _6 = _5 RELOP2 _4; 1864 _9 = _8 RELOP3 _7; 1865 _10 = _3 & _6; 1866 _12 = _9 & _0; 1867 1868 then _t != 0 will be normalized into a pred_chain: 1869 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0) 1870 1871 */ 1872 1873/* This is a helper function that stores a PRED into NORM_PREDS. */ 1874 1875inline static void 1876push_pred (pred_chain_union *norm_preds, pred_info pred) 1877{ 1878 pred_chain pred_chain = vNULL; 1879 pred_chain.safe_push (pred); 1880 norm_preds->safe_push (pred_chain); 1881} 1882 1883/* A helper function that creates a predicate of the form 1884 OP != 0 and push it WORK_LIST. */ 1885 1886inline static void 1887push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list, 1888 hash_set<tree> *mark_set) 1889{ 1890 if (mark_set->contains (op)) 1891 return; 1892 mark_set->add (op); 1893 1894 pred_info arg_pred; 1895 arg_pred.pred_lhs = op; 1896 arg_pred.pred_rhs = integer_zero_node; 1897 arg_pred.cond_code = NE_EXPR; 1898 arg_pred.invert = false; 1899 work_list->safe_push (arg_pred); 1900} 1901 1902/* A helper that generates a pred_info from a gimple assignment 1903 CMP_ASSIGN with comparison rhs. */ 1904 1905static pred_info 1906get_pred_info_from_cmp (gimple cmp_assign) 1907{ 1908 pred_info n_pred; 1909 n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign); 1910 n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign); 1911 n_pred.cond_code = gimple_assign_rhs_code (cmp_assign); 1912 n_pred.invert = false; 1913 return n_pred; 1914} 1915 1916/* Returns true if the PHI is a degenerated phi with 1917 all args with the same value (relop). In that case, *PRED 1918 will be updated to that value. */ 1919 1920static bool 1921is_degenerated_phi (gimple phi, pred_info *pred_p) 1922{ 1923 int i, n; 1924 tree op0; 1925 gimple def0; 1926 pred_info pred0; 1927 1928 n = gimple_phi_num_args (phi); 1929 op0 = gimple_phi_arg_def (phi, 0); 1930 1931 if (TREE_CODE (op0) != SSA_NAME) 1932 return false; 1933 1934 def0 = SSA_NAME_DEF_STMT (op0); 1935 if (gimple_code (def0) != GIMPLE_ASSIGN) 1936 return false; 1937 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) 1938 != tcc_comparison) 1939 return false; 1940 pred0 = get_pred_info_from_cmp (def0); 1941 1942 for (i = 1; i < n; ++i) 1943 { 1944 gimple def; 1945 pred_info pred; 1946 tree op = gimple_phi_arg_def (phi, i); 1947 1948 if (TREE_CODE (op) != SSA_NAME) 1949 return false; 1950 1951 def = SSA_NAME_DEF_STMT (op); 1952 if (gimple_code (def) != GIMPLE_ASSIGN) 1953 return false; 1954 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) 1955 != tcc_comparison) 1956 return false; 1957 pred = get_pred_info_from_cmp (def); 1958 if (!pred_equal_p (pred, pred0)) 1959 return false; 1960 } 1961 1962 *pred_p = pred0; 1963 return true; 1964} 1965 1966/* Normalize one predicate PRED 1967 1) if PRED can no longer be normlized, put it into NORM_PREDS. 1968 2) otherwise if PRED is of the form x != 0, follow x's definition 1969 and put normalized predicates into WORK_LIST. */ 1970 1971static void 1972normalize_one_pred_1 (pred_chain_union *norm_preds, 1973 pred_chain *norm_chain, 1974 pred_info pred, 1975 enum tree_code and_or_code, 1976 vec<pred_info, va_heap, vl_ptr> *work_list, 1977 hash_set<tree> *mark_set) 1978{ 1979 if (!is_neq_zero_form_p (pred)) 1980 { 1981 if (and_or_code == BIT_IOR_EXPR) 1982 push_pred (norm_preds, pred); 1983 else 1984 norm_chain->safe_push (pred); 1985 return; 1986 } 1987 1988 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs); 1989 1990 if (gimple_code (def_stmt) == GIMPLE_PHI 1991 && is_degenerated_phi (def_stmt, &pred)) 1992 work_list->safe_push (pred); 1993 else if (gimple_code (def_stmt) == GIMPLE_PHI 1994 && and_or_code == BIT_IOR_EXPR) 1995 { 1996 int i, n; 1997 n = gimple_phi_num_args (def_stmt); 1998 1999 /* If we see non zero constant, we should punt. The predicate 2000 * should be one guarding the phi edge. */ 2001 for (i = 0; i < n; ++i) 2002 { 2003 tree op = gimple_phi_arg_def (def_stmt, i); 2004 if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op)) 2005 { 2006 push_pred (norm_preds, pred); 2007 return; 2008 } 2009 } 2010 2011 for (i = 0; i < n; ++i) 2012 { 2013 tree op = gimple_phi_arg_def (def_stmt, i); 2014 if (integer_zerop (op)) 2015 continue; 2016 2017 push_to_worklist (op, work_list, mark_set); 2018 } 2019 } 2020 else if (gimple_code (def_stmt) != GIMPLE_ASSIGN) 2021 { 2022 if (and_or_code == BIT_IOR_EXPR) 2023 push_pred (norm_preds, pred); 2024 else 2025 norm_chain->safe_push (pred); 2026 } 2027 else if (gimple_assign_rhs_code (def_stmt) == and_or_code) 2028 { 2029 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */ 2030 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt))) 2031 { 2032 /* But treat x & 3 as condition. */ 2033 if (and_or_code == BIT_AND_EXPR) 2034 { 2035 pred_info n_pred; 2036 n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt); 2037 n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt); 2038 n_pred.cond_code = and_or_code; 2039 n_pred.invert = false; 2040 norm_chain->safe_push (n_pred); 2041 } 2042 } 2043 else 2044 { 2045 push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set); 2046 push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set); 2047 } 2048 } 2049 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) 2050 == tcc_comparison) 2051 { 2052 pred_info n_pred = get_pred_info_from_cmp (def_stmt); 2053 if (and_or_code == BIT_IOR_EXPR) 2054 push_pred (norm_preds, n_pred); 2055 else 2056 norm_chain->safe_push (n_pred); 2057 } 2058 else 2059 { 2060 if (and_or_code == BIT_IOR_EXPR) 2061 push_pred (norm_preds, pred); 2062 else 2063 norm_chain->safe_push (pred); 2064 } 2065} 2066 2067/* Normalize PRED and store the normalized predicates into NORM_PREDS. */ 2068 2069static void 2070normalize_one_pred (pred_chain_union *norm_preds, 2071 pred_info pred) 2072{ 2073 vec<pred_info, va_heap, vl_ptr> work_list = vNULL; 2074 enum tree_code and_or_code = ERROR_MARK; 2075 pred_chain norm_chain = vNULL; 2076 2077 if (!is_neq_zero_form_p (pred)) 2078 { 2079 push_pred (norm_preds, pred); 2080 return; 2081 } 2082 2083 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs); 2084 if (gimple_code (def_stmt) == GIMPLE_ASSIGN) 2085 and_or_code = gimple_assign_rhs_code (def_stmt); 2086 if (and_or_code != BIT_IOR_EXPR 2087 && and_or_code != BIT_AND_EXPR) 2088 { 2089 if (TREE_CODE_CLASS (and_or_code) 2090 == tcc_comparison) 2091 { 2092 pred_info n_pred = get_pred_info_from_cmp (def_stmt); 2093 push_pred (norm_preds, n_pred); 2094 } 2095 else 2096 push_pred (norm_preds, pred); 2097 return; 2098 } 2099 2100 work_list.safe_push (pred); 2101 hash_set<tree> mark_set; 2102 2103 while (!work_list.is_empty ()) 2104 { 2105 pred_info a_pred = work_list.pop (); 2106 normalize_one_pred_1 (norm_preds, &norm_chain, a_pred, 2107 and_or_code, &work_list, &mark_set); 2108 } 2109 if (and_or_code == BIT_AND_EXPR) 2110 norm_preds->safe_push (norm_chain); 2111 2112 work_list.release (); 2113} 2114 2115static void 2116normalize_one_pred_chain (pred_chain_union *norm_preds, 2117 pred_chain one_chain) 2118{ 2119 vec<pred_info, va_heap, vl_ptr> work_list = vNULL; 2120 hash_set<tree> mark_set; 2121 pred_chain norm_chain = vNULL; 2122 size_t i; 2123 2124 for (i = 0; i < one_chain.length (); i++) 2125 { 2126 work_list.safe_push (one_chain[i]); 2127 mark_set.add (one_chain[i].pred_lhs); 2128 } 2129 2130 while (!work_list.is_empty ()) 2131 { 2132 pred_info a_pred = work_list.pop (); 2133 normalize_one_pred_1 (0, &norm_chain, a_pred, 2134 BIT_AND_EXPR, &work_list, &mark_set); 2135 } 2136 2137 norm_preds->safe_push (norm_chain); 2138 work_list.release (); 2139} 2140 2141/* Normalize predicate chains PREDS and returns the normalized one. */ 2142 2143static pred_chain_union 2144normalize_preds (pred_chain_union preds, gimple use_or_def, bool is_use) 2145{ 2146 pred_chain_union norm_preds = vNULL; 2147 size_t n = preds.length (); 2148 size_t i; 2149 2150 if (dump_file && dump_flags & TDF_DETAILS) 2151 { 2152 fprintf (dump_file, "[BEFORE NORMALIZATION --"); 2153 dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n"); 2154 } 2155 2156 for (i = 0; i < n; i++) 2157 { 2158 if (preds[i].length () != 1) 2159 normalize_one_pred_chain (&norm_preds, preds[i]); 2160 else 2161 { 2162 normalize_one_pred (&norm_preds, preds[i][0]); 2163 preds[i].release (); 2164 } 2165 } 2166 2167 if (dump_file) 2168 { 2169 fprintf (dump_file, "[AFTER NORMALIZATION -- "); 2170 dump_predicates (use_or_def, norm_preds, is_use ? "[USE]:\n" : "[DEF]:\n"); 2171 } 2172 2173 preds.release (); 2174 return norm_preds; 2175} 2176 2177 2178/* Computes the predicates that guard the use and checks 2179 if the incoming paths that have empty (or possibly 2180 empty) definition can be pruned/filtered. The function returns 2181 true if it can be determined that the use of PHI's def in 2182 USE_STMT is guarded with a predicate set not overlapping with 2183 predicate sets of all runtime paths that do not have a definition. 2184 Returns false if it is not or it can not be determined. USE_BB is 2185 the bb of the use (for phi operand use, the bb is not the bb of 2186 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS 2187 is a bit vector. If an operand of PHI is uninitialized, the 2188 corresponding bit in the vector is 1. VISIED_PHIS is a pointer 2189 set of phis being visted. */ 2190 2191static bool 2192is_use_properly_guarded (gimple use_stmt, 2193 basic_block use_bb, 2194 gphi *phi, 2195 unsigned uninit_opnds, 2196 hash_set<gphi *> *visited_phis) 2197{ 2198 basic_block phi_bb; 2199 pred_chain_union preds = vNULL; 2200 pred_chain_union def_preds = vNULL; 2201 bool has_valid_preds = false; 2202 bool is_properly_guarded = false; 2203 2204 if (visited_phis->add (phi)) 2205 return false; 2206 2207 phi_bb = gimple_bb (phi); 2208 2209 if (is_non_loop_exit_postdominating (use_bb, phi_bb)) 2210 return false; 2211 2212 has_valid_preds = find_predicates (&preds, phi_bb, use_bb); 2213 2214 if (!has_valid_preds) 2215 { 2216 destroy_predicate_vecs (preds); 2217 return false; 2218 } 2219 2220 /* Try to prune the dead incoming phi edges. */ 2221 is_properly_guarded 2222 = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds, 2223 visited_phis); 2224 2225 if (is_properly_guarded) 2226 { 2227 destroy_predicate_vecs (preds); 2228 return true; 2229 } 2230 2231 has_valid_preds = find_def_preds (&def_preds, phi); 2232 2233 if (!has_valid_preds) 2234 { 2235 destroy_predicate_vecs (preds); 2236 destroy_predicate_vecs (def_preds); 2237 return false; 2238 } 2239 2240 simplify_preds (&preds, use_stmt, true); 2241 preds = normalize_preds (preds, use_stmt, true); 2242 2243 simplify_preds (&def_preds, phi, false); 2244 def_preds = normalize_preds (def_preds, phi, false); 2245 2246 is_properly_guarded = is_superset_of (def_preds, preds); 2247 2248 destroy_predicate_vecs (preds); 2249 destroy_predicate_vecs (def_preds); 2250 return is_properly_guarded; 2251} 2252 2253/* Searches through all uses of a potentially 2254 uninitialized variable defined by PHI and returns a use 2255 statement if the use is not properly guarded. It returns 2256 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector 2257 holding the position(s) of uninit PHI operands. WORKLIST 2258 is the vector of candidate phis that may be updated by this 2259 function. ADDED_TO_WORKLIST is the pointer set tracking 2260 if the new phi is already in the worklist. */ 2261 2262static gimple 2263find_uninit_use (gphi *phi, unsigned uninit_opnds, 2264 vec<gphi *> *worklist, 2265 hash_set<gphi *> *added_to_worklist) 2266{ 2267 tree phi_result; 2268 use_operand_p use_p; 2269 gimple use_stmt; 2270 imm_use_iterator iter; 2271 2272 phi_result = gimple_phi_result (phi); 2273 2274 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result) 2275 { 2276 basic_block use_bb; 2277 2278 use_stmt = USE_STMT (use_p); 2279 if (is_gimple_debug (use_stmt)) 2280 continue; 2281 2282 if (gphi *use_phi = dyn_cast <gphi *> (use_stmt)) 2283 use_bb = gimple_phi_arg_edge (use_phi, 2284 PHI_ARG_INDEX_FROM_USE (use_p))->src; 2285 else 2286 use_bb = gimple_bb (use_stmt); 2287 2288 hash_set<gphi *> visited_phis; 2289 if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds, 2290 &visited_phis)) 2291 continue; 2292 2293 if (dump_file && (dump_flags & TDF_DETAILS)) 2294 { 2295 fprintf (dump_file, "[CHECK]: Found unguarded use: "); 2296 print_gimple_stmt (dump_file, use_stmt, 0, 0); 2297 } 2298 /* Found one real use, return. */ 2299 if (gimple_code (use_stmt) != GIMPLE_PHI) 2300 return use_stmt; 2301 2302 /* Found a phi use that is not guarded, 2303 add the phi to the worklist. */ 2304 if (!added_to_worklist->add (as_a <gphi *> (use_stmt))) 2305 { 2306 if (dump_file && (dump_flags & TDF_DETAILS)) 2307 { 2308 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: "); 2309 print_gimple_stmt (dump_file, use_stmt, 0, 0); 2310 } 2311 2312 worklist->safe_push (as_a <gphi *> (use_stmt)); 2313 possibly_undefined_names->add (phi_result); 2314 } 2315 } 2316 2317 return NULL; 2318} 2319 2320/* Look for inputs to PHI that are SSA_NAMEs that have empty definitions 2321 and gives warning if there exists a runtime path from the entry to a 2322 use of the PHI def that does not contain a definition. In other words, 2323 the warning is on the real use. The more dead paths that can be pruned 2324 by the compiler, the fewer false positives the warning is. WORKLIST 2325 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is 2326 a pointer set tracking if the new phi is added to the worklist or not. */ 2327 2328static void 2329warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist, 2330 hash_set<gphi *> *added_to_worklist) 2331{ 2332 unsigned uninit_opnds; 2333 gimple uninit_use_stmt = 0; 2334 tree uninit_op; 2335 int phiarg_index; 2336 location_t loc; 2337 2338 /* Don't look at virtual operands. */ 2339 if (virtual_operand_p (gimple_phi_result (phi))) 2340 return; 2341 2342 uninit_opnds = compute_uninit_opnds_pos (phi); 2343 2344 if (MASK_EMPTY (uninit_opnds)) 2345 return; 2346 2347 if (dump_file && (dump_flags & TDF_DETAILS)) 2348 { 2349 fprintf (dump_file, "[CHECK]: examining phi: "); 2350 print_gimple_stmt (dump_file, phi, 0, 0); 2351 } 2352 2353 /* Now check if we have any use of the value without proper guard. */ 2354 uninit_use_stmt = find_uninit_use (phi, uninit_opnds, 2355 worklist, added_to_worklist); 2356 2357 /* All uses are properly guarded. */ 2358 if (!uninit_use_stmt) 2359 return; 2360 2361 phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds); 2362 uninit_op = gimple_phi_arg_def (phi, phiarg_index); 2363 if (SSA_NAME_VAR (uninit_op) == NULL_TREE) 2364 return; 2365 if (gimple_phi_arg_has_location (phi, phiarg_index)) 2366 loc = gimple_phi_arg_location (phi, phiarg_index); 2367 else 2368 loc = UNKNOWN_LOCATION; 2369 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op), 2370 SSA_NAME_VAR (uninit_op), 2371 "%qD may be used uninitialized in this function", 2372 uninit_use_stmt, loc); 2373 2374} 2375 2376static bool 2377gate_warn_uninitialized (void) 2378{ 2379 return warn_uninitialized || warn_maybe_uninitialized; 2380} 2381 2382namespace { 2383 2384const pass_data pass_data_late_warn_uninitialized = 2385{ 2386 GIMPLE_PASS, /* type */ 2387 "uninit", /* name */ 2388 OPTGROUP_NONE, /* optinfo_flags */ 2389 TV_NONE, /* tv_id */ 2390 PROP_ssa, /* properties_required */ 2391 0, /* properties_provided */ 2392 0, /* properties_destroyed */ 2393 0, /* todo_flags_start */ 2394 0, /* todo_flags_finish */ 2395}; 2396 2397class pass_late_warn_uninitialized : public gimple_opt_pass 2398{ 2399public: 2400 pass_late_warn_uninitialized (gcc::context *ctxt) 2401 : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt) 2402 {} 2403 2404 /* opt_pass methods: */ 2405 opt_pass * clone () { return new pass_late_warn_uninitialized (m_ctxt); } 2406 virtual bool gate (function *) { return gate_warn_uninitialized (); } 2407 virtual unsigned int execute (function *); 2408 2409}; // class pass_late_warn_uninitialized 2410 2411unsigned int 2412pass_late_warn_uninitialized::execute (function *fun) 2413{ 2414 basic_block bb; 2415 gphi_iterator gsi; 2416 vec<gphi *> worklist = vNULL; 2417 2418 calculate_dominance_info (CDI_DOMINATORS); 2419 calculate_dominance_info (CDI_POST_DOMINATORS); 2420 /* Re-do the plain uninitialized variable check, as optimization may have 2421 straightened control flow. Do this first so that we don't accidentally 2422 get a "may be" warning when we'd have seen an "is" warning later. */ 2423 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1); 2424 2425 timevar_push (TV_TREE_UNINIT); 2426 2427 possibly_undefined_names = new hash_set<tree>; 2428 hash_set<gphi *> added_to_worklist; 2429 2430 /* Initialize worklist */ 2431 FOR_EACH_BB_FN (bb, fun) 2432 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2433 { 2434 gphi *phi = gsi.phi (); 2435 size_t n, i; 2436 2437 n = gimple_phi_num_args (phi); 2438 2439 /* Don't look at virtual operands. */ 2440 if (virtual_operand_p (gimple_phi_result (phi))) 2441 continue; 2442 2443 for (i = 0; i < n; ++i) 2444 { 2445 tree op = gimple_phi_arg_def (phi, i); 2446 if (TREE_CODE (op) == SSA_NAME 2447 && uninit_undefined_value_p (op)) 2448 { 2449 worklist.safe_push (phi); 2450 added_to_worklist.add (phi); 2451 if (dump_file && (dump_flags & TDF_DETAILS)) 2452 { 2453 fprintf (dump_file, "[WORKLIST]: add to initial list: "); 2454 print_gimple_stmt (dump_file, phi, 0, 0); 2455 } 2456 break; 2457 } 2458 } 2459 } 2460 2461 while (worklist.length () != 0) 2462 { 2463 gphi *cur_phi = 0; 2464 cur_phi = worklist.pop (); 2465 warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist); 2466 } 2467 2468 worklist.release (); 2469 delete possibly_undefined_names; 2470 possibly_undefined_names = NULL; 2471 free_dominance_info (CDI_POST_DOMINATORS); 2472 timevar_pop (TV_TREE_UNINIT); 2473 return 0; 2474} 2475 2476} // anon namespace 2477 2478gimple_opt_pass * 2479make_pass_late_warn_uninitialized (gcc::context *ctxt) 2480{ 2481 return new pass_late_warn_uninitialized (ctxt); 2482} 2483 2484 2485static unsigned int 2486execute_early_warn_uninitialized (void) 2487{ 2488 /* Currently, this pass runs always but 2489 execute_late_warn_uninitialized only runs with optimization. With 2490 optimization we want to warn about possible uninitialized as late 2491 as possible, thus don't do it here. However, without 2492 optimization we need to warn here about "may be uninitialized". */ 2493 calculate_dominance_info (CDI_POST_DOMINATORS); 2494 2495 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize); 2496 2497 /* Post-dominator information can not be reliably updated. Free it 2498 after the use. */ 2499 2500 free_dominance_info (CDI_POST_DOMINATORS); 2501 return 0; 2502} 2503 2504 2505namespace { 2506 2507const pass_data pass_data_early_warn_uninitialized = 2508{ 2509 GIMPLE_PASS, /* type */ 2510 "*early_warn_uninitialized", /* name */ 2511 OPTGROUP_NONE, /* optinfo_flags */ 2512 TV_TREE_UNINIT, /* tv_id */ 2513 PROP_ssa, /* properties_required */ 2514 0, /* properties_provided */ 2515 0, /* properties_destroyed */ 2516 0, /* todo_flags_start */ 2517 0, /* todo_flags_finish */ 2518}; 2519 2520class pass_early_warn_uninitialized : public gimple_opt_pass 2521{ 2522public: 2523 pass_early_warn_uninitialized (gcc::context *ctxt) 2524 : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt) 2525 {} 2526 2527 /* opt_pass methods: */ 2528 virtual bool gate (function *) { return gate_warn_uninitialized (); } 2529 virtual unsigned int execute (function *) 2530 { 2531 return execute_early_warn_uninitialized (); 2532 } 2533 2534}; // class pass_early_warn_uninitialized 2535 2536} // anon namespace 2537 2538gimple_opt_pass * 2539make_pass_early_warn_uninitialized (gcc::context *ctxt) 2540{ 2541 return new pass_early_warn_uninitialized (ctxt); 2542} 2543