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