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