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