1 /* Const/Copy propagation originating from degenerate PHIs 2 Copyright (C) 2001-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 GCC is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "backend.h" 24 #include "cfghooks.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "ssa.h" 28 #include "fold-const.h" 29 #include "cfgloop.h" 30 #include "gimple-pretty-print.h" 31 #include "gimple-fold.h" 32 #include "tree-eh.h" 33 #include "gimple-iterator.h" 34 #include "tree-cfg.h" 35 #include "tree-pass.h" 36 #include "tree-ssa-propagate.h" 37 38 39 /* PHI-ONLY copy and constant propagation. This pass is meant to clean 40 up degenerate PHIs created by or exposed by jump threading. */ 41 42 /* Given a statement STMT, which is either a PHI node or an assignment, 43 remove it from the IL. */ 44 45 static void 46 remove_stmt_or_phi (gimple *stmt) 47 { 48 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 49 50 if (gimple_code (stmt) == GIMPLE_PHI) 51 remove_phi_node (&gsi, true); 52 else 53 { 54 gsi_remove (&gsi, true); 55 release_defs (stmt); 56 } 57 } 58 59 /* Given a statement STMT, which is either a PHI node or an assignment, 60 return the "rhs" of the node, in the case of a non-degenerate 61 phi, NULL is returned. */ 62 63 static tree 64 get_rhs_or_phi_arg (gimple *stmt) 65 { 66 if (gimple_code (stmt) == GIMPLE_PHI) 67 return degenerate_phi_result (as_a <gphi *> (stmt)); 68 else if (gimple_assign_single_p (stmt)) 69 return gimple_assign_rhs1 (stmt); 70 else 71 gcc_unreachable (); 72 } 73 74 75 /* Given a statement STMT, which is either a PHI node or an assignment, 76 return the "lhs" of the node. */ 77 78 static tree 79 get_lhs_or_phi_result (gimple *stmt) 80 { 81 if (gimple_code (stmt) == GIMPLE_PHI) 82 return gimple_phi_result (stmt); 83 else if (is_gimple_assign (stmt)) 84 return gimple_assign_lhs (stmt); 85 else 86 gcc_unreachable (); 87 } 88 89 /* Propagate RHS into all uses of LHS (when possible). 90 91 RHS and LHS are derived from STMT, which is passed in solely so 92 that we can remove it if propagation is successful. 93 94 When propagating into a PHI node or into a statement which turns 95 into a trivial copy or constant initialization, set the 96 appropriate bit in INTERESTING_NAMEs so that we will visit those 97 nodes as well in an effort to pick up secondary optimization 98 opportunities. 99 100 NEED_EH_CLEANUP tracks blocks that need their EH information 101 cleaned up after changing EH information on a statement. */ 102 103 static bool 104 propagate_rhs_into_lhs (gimple *stmt, tree lhs, tree rhs, 105 bitmap interesting_names, bitmap need_eh_cleanup) 106 { 107 bool cfg_altered = false; 108 109 /* First verify that propagation is valid. */ 110 if (may_propagate_copy (lhs, rhs)) 111 { 112 use_operand_p use_p; 113 imm_use_iterator iter; 114 gimple *use_stmt; 115 bool all = true; 116 117 /* Dump details. */ 118 if (dump_file && (dump_flags & TDF_DETAILS)) 119 { 120 fprintf (dump_file, " Replacing '"); 121 print_generic_expr (dump_file, lhs, dump_flags); 122 fprintf (dump_file, "' with %s '", 123 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable")); 124 print_generic_expr (dump_file, rhs, dump_flags); 125 fprintf (dump_file, "'\n"); 126 } 127 128 /* Walk over every use of LHS and try to replace the use with RHS. 129 At this point the only reason why such a propagation would not 130 be successful would be if the use occurs in an ASM_EXPR. */ 131 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) 132 { 133 /* Leave debug stmts alone. If we succeed in propagating 134 all non-debug uses, we'll drop the DEF, and propagation 135 into debug stmts will occur then. */ 136 if (gimple_debug_bind_p (use_stmt)) 137 continue; 138 139 /* It's not always safe to propagate into an ASM_EXPR. */ 140 if (gimple_code (use_stmt) == GIMPLE_ASM 141 && ! may_propagate_copy_into_asm (lhs)) 142 { 143 all = false; 144 continue; 145 } 146 147 /* It's not ok to propagate into the definition stmt of RHS. 148 <bb 9>: 149 # prephitmp.12_36 = PHI <g_67.1_6(9)> 150 g_67.1_6 = prephitmp.12_36; 151 goto <bb 9>; 152 While this is strictly all dead code we do not want to 153 deal with this here. */ 154 if (TREE_CODE (rhs) == SSA_NAME 155 && SSA_NAME_DEF_STMT (rhs) == use_stmt) 156 { 157 all = false; 158 continue; 159 } 160 161 /* Dump details. */ 162 if (dump_file && (dump_flags & TDF_DETAILS)) 163 { 164 fprintf (dump_file, " Original statement:"); 165 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); 166 } 167 168 /* Propagate the RHS into this use of the LHS. */ 169 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 170 propagate_value (use_p, rhs); 171 172 /* Special cases to avoid useless calls into the folding 173 routines, operand scanning, etc. 174 175 Propagation into a PHI may cause the PHI to become 176 a degenerate, so mark the PHI as interesting. No other 177 actions are necessary. */ 178 if (gimple_code (use_stmt) == GIMPLE_PHI) 179 { 180 tree result; 181 182 /* Dump details. */ 183 if (dump_file && (dump_flags & TDF_DETAILS)) 184 { 185 fprintf (dump_file, " Updated statement:"); 186 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); 187 } 188 189 result = get_lhs_or_phi_result (use_stmt); 190 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); 191 continue; 192 } 193 194 /* From this point onward we are propagating into a 195 real statement. Folding may (or may not) be possible, 196 we may expose new operands, expose dead EH edges, 197 etc. */ 198 /* NOTE tuples. In the tuples world, fold_stmt_inplace 199 cannot fold a call that simplifies to a constant, 200 because the GIMPLE_CALL must be replaced by a 201 GIMPLE_ASSIGN, and there is no way to effect such a 202 transformation in-place. We might want to consider 203 using the more general fold_stmt here. */ 204 { 205 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 206 fold_stmt_inplace (&gsi); 207 } 208 209 /* Sometimes propagation can expose new operands to the 210 renamer. */ 211 update_stmt (use_stmt); 212 213 /* Dump details. */ 214 if (dump_file && (dump_flags & TDF_DETAILS)) 215 { 216 fprintf (dump_file, " Updated statement:"); 217 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); 218 } 219 220 /* If we replaced a variable index with a constant, then 221 we would need to update the invariant flag for ADDR_EXPRs. */ 222 if (gimple_assign_single_p (use_stmt) 223 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR) 224 recompute_tree_invariant_for_addr_expr 225 (gimple_assign_rhs1 (use_stmt)); 226 227 /* If we cleaned up EH information from the statement, 228 mark its containing block as needing EH cleanups. */ 229 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt)) 230 { 231 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index); 232 if (dump_file && (dump_flags & TDF_DETAILS)) 233 fprintf (dump_file, " Flagged to clear EH edges.\n"); 234 } 235 236 /* Propagation may expose new trivial copy/constant propagation 237 opportunities. */ 238 if (gimple_assign_single_p (use_stmt) 239 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME 240 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME 241 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt)))) 242 { 243 tree result = get_lhs_or_phi_result (use_stmt); 244 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); 245 } 246 247 /* Propagation into these nodes may make certain edges in 248 the CFG unexecutable. We want to identify them as PHI nodes 249 at the destination of those unexecutable edges may become 250 degenerates. */ 251 else if (gimple_code (use_stmt) == GIMPLE_COND 252 || gimple_code (use_stmt) == GIMPLE_SWITCH 253 || gimple_code (use_stmt) == GIMPLE_GOTO) 254 { 255 tree val; 256 257 if (gimple_code (use_stmt) == GIMPLE_COND) 258 val = fold_binary_loc (gimple_location (use_stmt), 259 gimple_cond_code (use_stmt), 260 boolean_type_node, 261 gimple_cond_lhs (use_stmt), 262 gimple_cond_rhs (use_stmt)); 263 else if (gimple_code (use_stmt) == GIMPLE_SWITCH) 264 val = gimple_switch_index (as_a <gswitch *> (use_stmt)); 265 else 266 val = gimple_goto_dest (use_stmt); 267 268 if (val && is_gimple_min_invariant (val)) 269 { 270 basic_block bb = gimple_bb (use_stmt); 271 edge te = find_taken_edge (bb, val); 272 if (!te) 273 continue; 274 275 edge_iterator ei; 276 edge e; 277 gimple_stmt_iterator gsi; 278 gphi_iterator psi; 279 280 /* Remove all outgoing edges except TE. */ 281 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));) 282 { 283 if (e != te) 284 { 285 /* Mark all the PHI nodes at the destination of 286 the unexecutable edge as interesting. */ 287 for (psi = gsi_start_phis (e->dest); 288 !gsi_end_p (psi); 289 gsi_next (&psi)) 290 { 291 gphi *phi = psi.phi (); 292 293 tree result = gimple_phi_result (phi); 294 int version = SSA_NAME_VERSION (result); 295 296 bitmap_set_bit (interesting_names, version); 297 } 298 299 te->probability += e->probability; 300 301 remove_edge (e); 302 cfg_altered = true; 303 } 304 else 305 ei_next (&ei); 306 } 307 308 gsi = gsi_last_bb (gimple_bb (use_stmt)); 309 gsi_remove (&gsi, true); 310 311 /* And fixup the flags on the single remaining edge. */ 312 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 313 te->flags &= ~EDGE_ABNORMAL; 314 te->flags |= EDGE_FALLTHRU; 315 } 316 } 317 } 318 319 /* Ensure there is nothing else to do. */ 320 gcc_assert (!all || has_zero_uses (lhs)); 321 322 /* If we were able to propagate away all uses of LHS, then 323 we can remove STMT. */ 324 if (all) 325 remove_stmt_or_phi (stmt); 326 } 327 return cfg_altered; 328 } 329 330 /* STMT is either a PHI node (potentially a degenerate PHI node) or 331 a statement that is a trivial copy or constant initialization. 332 333 Attempt to eliminate STMT by propagating its RHS into all uses of 334 its LHS. This may in turn set new bits in INTERESTING_NAMES 335 for nodes we want to revisit later. 336 337 All exit paths should clear INTERESTING_NAMES for the result 338 of STMT. 339 340 NEED_EH_CLEANUP tracks blocks that need their EH information 341 cleaned up after changing EH information on a statement. It is 342 not set or queried here, but passed along to children. */ 343 344 static bool 345 eliminate_const_or_copy (gimple *stmt, bitmap interesting_names, 346 bitmap need_eh_cleanup) 347 { 348 tree lhs = get_lhs_or_phi_result (stmt); 349 tree rhs; 350 int version = SSA_NAME_VERSION (lhs); 351 bool cfg_altered = false; 352 353 /* If the LHS of this statement or PHI has no uses, then we can 354 just eliminate it. This can occur if, for example, the PHI 355 was created by block duplication due to threading and its only 356 use was in the conditional at the end of the block which was 357 deleted. */ 358 if (has_zero_uses (lhs)) 359 { 360 bitmap_clear_bit (interesting_names, version); 361 remove_stmt_or_phi (stmt); 362 return cfg_altered; 363 } 364 365 /* Get the RHS of the assignment or PHI node if the PHI is a 366 degenerate. */ 367 rhs = get_rhs_or_phi_arg (stmt); 368 if (!rhs) 369 { 370 bitmap_clear_bit (interesting_names, version); 371 return cfg_altered; 372 } 373 374 if (!virtual_operand_p (lhs)) 375 cfg_altered = propagate_rhs_into_lhs (stmt, lhs, rhs, 376 interesting_names, need_eh_cleanup); 377 else 378 { 379 gimple *use_stmt; 380 imm_use_iterator iter; 381 use_operand_p use_p; 382 /* For virtual operands we have to propagate into all uses as 383 otherwise we will create overlapping life-ranges. */ 384 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) 385 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 386 SET_USE (use_p, rhs); 387 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 388 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1; 389 remove_stmt_or_phi (stmt); 390 } 391 392 /* Note that STMT may well have been deleted by now, so do 393 not access it, instead use the saved version # to clear 394 T's entry in the worklist. */ 395 bitmap_clear_bit (interesting_names, version); 396 return cfg_altered; 397 } 398 399 /* The first phase in degenerate PHI elimination. 400 401 Eliminate the degenerate PHIs in BB, then recurse on the 402 dominator children of BB. 403 404 INTERESTING_NAMES tracks SSA_NAMEs that we may want to revisit 405 in the future. It is not set or queried here, but passed along 406 to children. 407 408 NEED_EH_CLEANUP tracks blocks that need their EH information 409 cleaned up after changing EH information on a statement. It is 410 not set or queried here, but passed along to children. */ 411 412 static bool 413 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names, 414 bitmap need_eh_cleanup) 415 { 416 gphi_iterator gsi; 417 basic_block son; 418 bool cfg_altered = false; 419 420 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);) 421 { 422 gphi *phi = gsi.phi (); 423 /* We might end up removing PHI so advance the iterator now. */ 424 gsi_next (&gsi); 425 cfg_altered |= eliminate_const_or_copy (phi, interesting_names, 426 need_eh_cleanup); 427 } 428 429 /* Recurse into the dominator children of BB. */ 430 for (son = first_dom_son (CDI_DOMINATORS, bb); 431 son; 432 son = next_dom_son (CDI_DOMINATORS, son)) 433 cfg_altered |= eliminate_degenerate_phis_1 (son, interesting_names, 434 need_eh_cleanup); 435 436 return cfg_altered; 437 } 438 439 440 /* A very simple pass to eliminate degenerate PHI nodes from the 441 IL. This is meant to be fast enough to be able to be run several 442 times in the optimization pipeline. 443 444 Certain optimizations, particularly those which duplicate blocks 445 or remove edges from the CFG can create or expose PHIs which are 446 trivial copies or constant initializations. 447 448 While we could pick up these optimizations in DOM or with the 449 combination of copy-prop and CCP, those solutions are far too 450 heavy-weight for our needs. 451 452 This implementation has two phases so that we can efficiently 453 eliminate the first order degenerate PHIs and second order 454 degenerate PHIs. 455 456 The first phase performs a dominator walk to identify and eliminate 457 the vast majority of the degenerate PHIs. When a degenerate PHI 458 is identified and eliminated any affected statements or PHIs 459 are put on a worklist. 460 461 The second phase eliminates degenerate PHIs and trivial copies 462 or constant initializations using the worklist. This is how we 463 pick up the secondary optimization opportunities with minimal 464 cost. */ 465 466 namespace { 467 468 const pass_data pass_data_phi_only_cprop = 469 { 470 GIMPLE_PASS, /* type */ 471 "phicprop", /* name */ 472 OPTGROUP_NONE, /* optinfo_flags */ 473 TV_TREE_PHI_CPROP, /* tv_id */ 474 ( PROP_cfg | PROP_ssa ), /* properties_required */ 475 0, /* properties_provided */ 476 0, /* properties_destroyed */ 477 0, /* todo_flags_start */ 478 ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */ 479 }; 480 481 class pass_phi_only_cprop : public gimple_opt_pass 482 { 483 public: 484 pass_phi_only_cprop (gcc::context *ctxt) 485 : gimple_opt_pass (pass_data_phi_only_cprop, ctxt) 486 {} 487 488 /* opt_pass methods: */ 489 opt_pass * clone () { return new pass_phi_only_cprop (m_ctxt); } 490 virtual bool gate (function *) { return flag_tree_dom != 0; } 491 virtual unsigned int execute (function *); 492 493 }; // class pass_phi_only_cprop 494 495 unsigned int 496 pass_phi_only_cprop::execute (function *fun) 497 { 498 bool cfg_altered = false; 499 500 /* Bitmap of blocks which need EH information updated. We can not 501 update it on-the-fly as doing so invalidates the dominator tree. */ 502 auto_bitmap need_eh_cleanup; 503 504 /* INTERESTING_NAMES is effectively our worklist, indexed by 505 SSA_NAME_VERSION. 506 507 A set bit indicates that the statement or PHI node which 508 defines the SSA_NAME should be (re)examined to determine if 509 it has become a degenerate PHI or trivial const/copy propagation 510 opportunity. 511 512 Experiments have show we generally get better compilation 513 time behavior with bitmaps rather than sbitmaps. */ 514 auto_bitmap interesting_names; 515 auto_bitmap interesting_names1; 516 517 calculate_dominance_info (CDI_DOMINATORS); 518 cfg_altered = false; 519 520 /* First phase. Eliminate degenerate PHIs via a dominator 521 walk of the CFG. 522 523 Experiments have indicated that we generally get better 524 compile-time behavior by visiting blocks in the first 525 phase in dominator order. Presumably this is because walking 526 in dominator order leaves fewer PHIs for later examination 527 by the worklist phase. */ 528 cfg_altered = eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (fun), 529 interesting_names, 530 need_eh_cleanup); 531 532 /* Second phase. Eliminate second order degenerate PHIs as well 533 as trivial copies or constant initializations identified by 534 the first phase or this phase. Basically we keep iterating 535 until our set of INTERESTING_NAMEs is empty. */ 536 while (!bitmap_empty_p (interesting_names)) 537 { 538 unsigned int i; 539 bitmap_iterator bi; 540 541 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap 542 changed during the loop. Copy it to another bitmap and 543 use that. */ 544 bitmap_copy (interesting_names1, interesting_names); 545 546 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi) 547 { 548 tree name = ssa_name (i); 549 550 /* Ignore SSA_NAMEs that have been released because 551 their defining statement was deleted (unreachable). */ 552 if (name) 553 cfg_altered 554 |= eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)), 555 interesting_names, need_eh_cleanup); 556 } 557 } 558 559 if (cfg_altered) 560 { 561 free_dominance_info (CDI_DOMINATORS); 562 /* If we changed the CFG schedule loops for fixup by cfgcleanup. */ 563 loops_state_set (LOOPS_NEED_FIXUP); 564 } 565 566 /* Propagation of const and copies may make some EH edges dead. Purge 567 such edges from the CFG as needed. */ 568 if (!bitmap_empty_p (need_eh_cleanup)) 569 gimple_purge_all_dead_eh_edges (need_eh_cleanup); 570 571 return 0; 572 } 573 574 } // anon namespace 575 576 gimple_opt_pass * 577 make_pass_phi_only_cprop (gcc::context *ctxt) 578 { 579 return new pass_phi_only_cprop (ctxt); 580 } 581