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