1/* CFG cleanup for trees. 2 Copyright (C) 2001-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 3, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 "tm.h" 24#include "hash-set.h" 25#include "machmode.h" 26#include "vec.h" 27#include "double-int.h" 28#include "input.h" 29#include "alias.h" 30#include "symtab.h" 31#include "wide-int.h" 32#include "inchash.h" 33#include "tree.h" 34#include "fold-const.h" 35#include "tm_p.h" 36#include "predict.h" 37#include "hard-reg-set.h" 38#include "function.h" 39#include "dominance.h" 40#include "cfg.h" 41#include "cfganal.h" 42#include "cfgcleanup.h" 43#include "basic-block.h" 44#include "diagnostic-core.h" 45#include "flags.h" 46#include "langhooks.h" 47#include "tree-ssa-alias.h" 48#include "internal-fn.h" 49#include "tree-eh.h" 50#include "gimple-expr.h" 51#include "is-a.h" 52#include "gimple.h" 53#include "gimplify.h" 54#include "gimple-iterator.h" 55#include "gimple-ssa.h" 56#include "tree-cfg.h" 57#include "tree-phinodes.h" 58#include "ssa-iterators.h" 59#include "stringpool.h" 60#include "tree-ssanames.h" 61#include "tree-ssa-loop-manip.h" 62#include "hashtab.h" 63#include "rtl.h" 64#include "statistics.h" 65#include "real.h" 66#include "fixed-value.h" 67#include "insn-config.h" 68#include "expmed.h" 69#include "dojump.h" 70#include "explow.h" 71#include "calls.h" 72#include "emit-rtl.h" 73#include "varasm.h" 74#include "stmt.h" 75#include "expr.h" 76#include "tree-dfa.h" 77#include "tree-ssa.h" 78#include "tree-pass.h" 79#include "except.h" 80#include "cfgloop.h" 81#include "tree-ssa-propagate.h" 82#include "tree-scalar-evolution.h" 83 84/* The set of blocks in that at least one of the following changes happened: 85 -- the statement at the end of the block was changed 86 -- the block was newly created 87 -- the set of the predecessors of the block changed 88 -- the set of the successors of the block changed 89 ??? Maybe we could track these changes separately, since they determine 90 what cleanups it makes sense to try on the block. */ 91bitmap cfgcleanup_altered_bbs; 92 93/* Remove any fallthru edge from EV. Return true if an edge was removed. */ 94 95static bool 96remove_fallthru_edge (vec<edge, va_gc> *ev) 97{ 98 edge_iterator ei; 99 edge e; 100 101 FOR_EACH_EDGE (e, ei, ev) 102 if ((e->flags & EDGE_FALLTHRU) != 0) 103 { 104 if (e->flags & EDGE_COMPLEX) 105 e->flags &= ~EDGE_FALLTHRU; 106 else 107 remove_edge_and_dominated_blocks (e); 108 return true; 109 } 110 return false; 111} 112 113 114/* Disconnect an unreachable block in the control expression starting 115 at block BB. */ 116 117static bool 118cleanup_control_expr_graph (basic_block bb, gimple_stmt_iterator gsi) 119{ 120 edge taken_edge; 121 bool retval = false; 122 gimple stmt = gsi_stmt (gsi); 123 tree val; 124 125 if (!single_succ_p (bb)) 126 { 127 edge e; 128 edge_iterator ei; 129 bool warned; 130 location_t loc; 131 132 fold_defer_overflow_warnings (); 133 loc = gimple_location (stmt); 134 switch (gimple_code (stmt)) 135 { 136 case GIMPLE_COND: 137 val = fold_binary_loc (loc, gimple_cond_code (stmt), 138 boolean_type_node, 139 gimple_cond_lhs (stmt), 140 gimple_cond_rhs (stmt)); 141 break; 142 143 case GIMPLE_SWITCH: 144 val = gimple_switch_index (as_a <gswitch *> (stmt)); 145 break; 146 147 default: 148 val = NULL_TREE; 149 } 150 taken_edge = find_taken_edge (bb, val); 151 if (!taken_edge) 152 { 153 fold_undefer_and_ignore_overflow_warnings (); 154 return false; 155 } 156 157 /* Remove all the edges except the one that is always executed. */ 158 warned = false; 159 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 160 { 161 if (e != taken_edge) 162 { 163 if (!warned) 164 { 165 fold_undefer_overflow_warnings 166 (true, stmt, WARN_STRICT_OVERFLOW_CONDITIONAL); 167 warned = true; 168 } 169 170 taken_edge->probability += e->probability; 171 taken_edge->count += e->count; 172 remove_edge_and_dominated_blocks (e); 173 retval = true; 174 } 175 else 176 ei_next (&ei); 177 } 178 if (!warned) 179 fold_undefer_and_ignore_overflow_warnings (); 180 if (taken_edge->probability > REG_BR_PROB_BASE) 181 taken_edge->probability = REG_BR_PROB_BASE; 182 } 183 else 184 taken_edge = single_succ_edge (bb); 185 186 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index); 187 gsi_remove (&gsi, true); 188 taken_edge->flags = EDGE_FALLTHRU; 189 190 return retval; 191} 192 193/* Cleanup the GF_CALL_CTRL_ALTERING flag according to 194 to updated gimple_call_flags. */ 195 196static void 197cleanup_call_ctrl_altering_flag (gimple bb_end) 198{ 199 if (!is_gimple_call (bb_end) 200 || !gimple_call_ctrl_altering_p (bb_end)) 201 return; 202 203 int flags = gimple_call_flags (bb_end); 204 if (((flags & (ECF_CONST | ECF_PURE)) 205 && !(flags & ECF_LOOPING_CONST_OR_PURE)) 206 || (flags & ECF_LEAF)) 207 gimple_call_set_ctrl_altering (bb_end, false); 208} 209 210/* Try to remove superfluous control structures in basic block BB. Returns 211 true if anything changes. */ 212 213static bool 214cleanup_control_flow_bb (basic_block bb) 215{ 216 gimple_stmt_iterator gsi; 217 bool retval = false; 218 gimple stmt; 219 220 /* If the last statement of the block could throw and now cannot, 221 we need to prune cfg. */ 222 retval |= gimple_purge_dead_eh_edges (bb); 223 224 gsi = gsi_last_bb (bb); 225 if (gsi_end_p (gsi)) 226 return retval; 227 228 stmt = gsi_stmt (gsi); 229 230 /* Try to cleanup ctrl altering flag for call which ends bb. */ 231 cleanup_call_ctrl_altering_flag (stmt); 232 233 if (gimple_code (stmt) == GIMPLE_COND 234 || gimple_code (stmt) == GIMPLE_SWITCH) 235 retval |= cleanup_control_expr_graph (bb, gsi); 236 else if (gimple_code (stmt) == GIMPLE_GOTO 237 && TREE_CODE (gimple_goto_dest (stmt)) == ADDR_EXPR 238 && (TREE_CODE (TREE_OPERAND (gimple_goto_dest (stmt), 0)) 239 == LABEL_DECL)) 240 { 241 /* If we had a computed goto which has a compile-time determinable 242 destination, then we can eliminate the goto. */ 243 edge e; 244 tree label; 245 edge_iterator ei; 246 basic_block target_block; 247 248 /* First look at all the outgoing edges. Delete any outgoing 249 edges which do not go to the right block. For the one 250 edge which goes to the right block, fix up its flags. */ 251 label = TREE_OPERAND (gimple_goto_dest (stmt), 0); 252 target_block = label_to_block (label); 253 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 254 { 255 if (e->dest != target_block) 256 remove_edge_and_dominated_blocks (e); 257 else 258 { 259 /* Turn off the EDGE_ABNORMAL flag. */ 260 e->flags &= ~EDGE_ABNORMAL; 261 262 /* And set EDGE_FALLTHRU. */ 263 e->flags |= EDGE_FALLTHRU; 264 ei_next (&ei); 265 } 266 } 267 268 bitmap_set_bit (cfgcleanup_altered_bbs, bb->index); 269 bitmap_set_bit (cfgcleanup_altered_bbs, target_block->index); 270 271 /* Remove the GOTO_EXPR as it is not needed. The CFG has all the 272 relevant information we need. */ 273 gsi_remove (&gsi, true); 274 retval = true; 275 } 276 277 /* Check for indirect calls that have been turned into 278 noreturn calls. */ 279 else if (is_gimple_call (stmt) 280 && gimple_call_noreturn_p (stmt) 281 && remove_fallthru_edge (bb->succs)) 282 retval = true; 283 284 return retval; 285} 286 287/* Return true if basic block BB does nothing except pass control 288 flow to another block and that we can safely insert a label at 289 the start of the successor block. 290 291 As a precondition, we require that BB be not equal to 292 the entry block. */ 293 294static bool 295tree_forwarder_block_p (basic_block bb, bool phi_wanted) 296{ 297 gimple_stmt_iterator gsi; 298 location_t locus; 299 300 /* BB must have a single outgoing edge. */ 301 if (single_succ_p (bb) != 1 302 /* If PHI_WANTED is false, BB must not have any PHI nodes. 303 Otherwise, BB must have PHI nodes. */ 304 || gimple_seq_empty_p (phi_nodes (bb)) == phi_wanted 305 /* BB may not be a predecessor of the exit block. */ 306 || single_succ (bb) == EXIT_BLOCK_PTR_FOR_FN (cfun) 307 /* Nor should this be an infinite loop. */ 308 || single_succ (bb) == bb 309 /* BB may not have an abnormal outgoing edge. */ 310 || (single_succ_edge (bb)->flags & EDGE_ABNORMAL)) 311 return false; 312 313 gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)); 314 315 locus = single_succ_edge (bb)->goto_locus; 316 317 /* There should not be an edge coming from entry, or an EH edge. */ 318 { 319 edge_iterator ei; 320 edge e; 321 322 FOR_EACH_EDGE (e, ei, bb->preds) 323 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || (e->flags & EDGE_EH)) 324 return false; 325 /* If goto_locus of any of the edges differs, prevent removing 326 the forwarder block for -O0. */ 327 else if (optimize == 0 && e->goto_locus != locus) 328 return false; 329 } 330 331 /* Now walk through the statements backward. We can ignore labels, 332 anything else means this is not a forwarder block. */ 333 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) 334 { 335 gimple stmt = gsi_stmt (gsi); 336 337 switch (gimple_code (stmt)) 338 { 339 case GIMPLE_LABEL: 340 if (DECL_NONLOCAL (gimple_label_label (as_a <glabel *> (stmt)))) 341 return false; 342 if (optimize == 0 && gimple_location (stmt) != locus) 343 return false; 344 break; 345 346 /* ??? For now, hope there's a corresponding debug 347 assignment at the destination. */ 348 case GIMPLE_DEBUG: 349 break; 350 351 default: 352 return false; 353 } 354 } 355 356 if (current_loops) 357 { 358 basic_block dest; 359 /* Protect loop headers. */ 360 if (bb->loop_father->header == bb) 361 return false; 362 363 dest = EDGE_SUCC (bb, 0)->dest; 364 /* Protect loop preheaders and latches if requested. */ 365 if (dest->loop_father->header == dest) 366 { 367 if (bb->loop_father == dest->loop_father) 368 { 369 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES)) 370 return false; 371 /* If bb doesn't have a single predecessor we'd make this 372 loop have multiple latches. Don't do that if that 373 would in turn require disambiguating them. */ 374 return (single_pred_p (bb) 375 || loops_state_satisfies_p 376 (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)); 377 } 378 else if (bb->loop_father == loop_outer (dest->loop_father)) 379 return !loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS); 380 /* Always preserve other edges into loop headers that are 381 not simple latches or preheaders. */ 382 return false; 383 } 384 } 385 386 return true; 387} 388 389/* If all the PHI nodes in DEST have alternatives for E1 and E2 and 390 those alternatives are equal in each of the PHI nodes, then return 391 true, else return false. */ 392 393static bool 394phi_alternatives_equal (basic_block dest, edge e1, edge e2) 395{ 396 int n1 = e1->dest_idx; 397 int n2 = e2->dest_idx; 398 gphi_iterator gsi; 399 400 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi)) 401 { 402 gphi *phi = gsi.phi (); 403 tree val1 = gimple_phi_arg_def (phi, n1); 404 tree val2 = gimple_phi_arg_def (phi, n2); 405 406 gcc_assert (val1 != NULL_TREE); 407 gcc_assert (val2 != NULL_TREE); 408 409 if (!operand_equal_for_phi_arg_p (val1, val2)) 410 return false; 411 } 412 413 return true; 414} 415 416/* Removes forwarder block BB. Returns false if this failed. */ 417 418static bool 419remove_forwarder_block (basic_block bb) 420{ 421 edge succ = single_succ_edge (bb), e, s; 422 basic_block dest = succ->dest; 423 gimple label; 424 edge_iterator ei; 425 gimple_stmt_iterator gsi, gsi_to; 426 bool can_move_debug_stmts; 427 428 /* We check for infinite loops already in tree_forwarder_block_p. 429 However it may happen that the infinite loop is created 430 afterwards due to removal of forwarders. */ 431 if (dest == bb) 432 return false; 433 434 /* If the destination block consists of a nonlocal label or is a 435 EH landing pad, do not merge it. */ 436 label = first_stmt (dest); 437 if (label) 438 if (glabel *label_stmt = dyn_cast <glabel *> (label)) 439 if (DECL_NONLOCAL (gimple_label_label (label_stmt)) 440 || EH_LANDING_PAD_NR (gimple_label_label (label_stmt)) != 0) 441 return false; 442 443 /* If there is an abnormal edge to basic block BB, but not into 444 dest, problems might occur during removal of the phi node at out 445 of ssa due to overlapping live ranges of registers. 446 447 If there is an abnormal edge in DEST, the problems would occur 448 anyway since cleanup_dead_labels would then merge the labels for 449 two different eh regions, and rest of exception handling code 450 does not like it. 451 452 So if there is an abnormal edge to BB, proceed only if there is 453 no abnormal edge to DEST and there are no phi nodes in DEST. */ 454 if (bb_has_abnormal_pred (bb) 455 && (bb_has_abnormal_pred (dest) 456 || !gimple_seq_empty_p (phi_nodes (dest)))) 457 return false; 458 459 /* If there are phi nodes in DEST, and some of the blocks that are 460 predecessors of BB are also predecessors of DEST, check that the 461 phi node arguments match. */ 462 if (!gimple_seq_empty_p (phi_nodes (dest))) 463 { 464 FOR_EACH_EDGE (e, ei, bb->preds) 465 { 466 s = find_edge (e->src, dest); 467 if (!s) 468 continue; 469 470 if (!phi_alternatives_equal (dest, succ, s)) 471 return false; 472 } 473 } 474 475 can_move_debug_stmts = MAY_HAVE_DEBUG_STMTS && single_pred_p (dest); 476 477 basic_block pred = NULL; 478 if (single_pred_p (bb)) 479 pred = single_pred (bb); 480 481 /* Redirect the edges. */ 482 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 483 { 484 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index); 485 486 if (e->flags & EDGE_ABNORMAL) 487 { 488 /* If there is an abnormal edge, redirect it anyway, and 489 move the labels to the new block to make it legal. */ 490 s = redirect_edge_succ_nodup (e, dest); 491 } 492 else 493 s = redirect_edge_and_branch (e, dest); 494 495 if (s == e) 496 { 497 /* Create arguments for the phi nodes, since the edge was not 498 here before. */ 499 for (gphi_iterator psi = gsi_start_phis (dest); 500 !gsi_end_p (psi); 501 gsi_next (&psi)) 502 { 503 gphi *phi = psi.phi (); 504 source_location l = gimple_phi_arg_location_from_edge (phi, succ); 505 tree def = gimple_phi_arg_def (phi, succ->dest_idx); 506 add_phi_arg (phi, unshare_expr (def), s, l); 507 } 508 } 509 } 510 511 /* Move nonlocal labels and computed goto targets as well as user 512 defined labels and labels with an EH landing pad number to the 513 new block, so that the redirection of the abnormal edges works, 514 jump targets end up in a sane place and debug information for 515 labels is retained. */ 516 gsi_to = gsi_start_bb (dest); 517 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); ) 518 { 519 tree decl; 520 label = gsi_stmt (gsi); 521 if (is_gimple_debug (label)) 522 break; 523 decl = gimple_label_label (as_a <glabel *> (label)); 524 if (EH_LANDING_PAD_NR (decl) != 0 525 || DECL_NONLOCAL (decl) 526 || FORCED_LABEL (decl) 527 || !DECL_ARTIFICIAL (decl)) 528 { 529 gsi_remove (&gsi, false); 530 gsi_insert_before (&gsi_to, label, GSI_SAME_STMT); 531 } 532 else 533 gsi_next (&gsi); 534 } 535 536 /* Move debug statements if the destination has a single predecessor. */ 537 if (can_move_debug_stmts) 538 { 539 gsi_to = gsi_after_labels (dest); 540 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); ) 541 { 542 gimple debug = gsi_stmt (gsi); 543 if (!is_gimple_debug (debug)) 544 break; 545 gsi_remove (&gsi, false); 546 gsi_insert_before (&gsi_to, debug, GSI_SAME_STMT); 547 } 548 } 549 550 bitmap_set_bit (cfgcleanup_altered_bbs, dest->index); 551 552 /* Update the dominators. */ 553 if (dom_info_available_p (CDI_DOMINATORS)) 554 { 555 basic_block dom, dombb, domdest; 556 557 dombb = get_immediate_dominator (CDI_DOMINATORS, bb); 558 domdest = get_immediate_dominator (CDI_DOMINATORS, dest); 559 if (domdest == bb) 560 { 561 /* Shortcut to avoid calling (relatively expensive) 562 nearest_common_dominator unless necessary. */ 563 dom = dombb; 564 } 565 else 566 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb); 567 568 set_immediate_dominator (CDI_DOMINATORS, dest, dom); 569 } 570 571 /* Adjust latch infomation of BB's parent loop as otherwise 572 the cfg hook has a hard time not to kill the loop. */ 573 if (current_loops && bb->loop_father->latch == bb) 574 bb->loop_father->latch = pred; 575 576 /* And kill the forwarder block. */ 577 delete_basic_block (bb); 578 579 return true; 580} 581 582/* STMT is a call that has been discovered noreturn. Split the 583 block to prepare fixing up the CFG and remove LHS. 584 Return true if cleanup-cfg needs to run. */ 585 586bool 587fixup_noreturn_call (gimple stmt) 588{ 589 basic_block bb = gimple_bb (stmt); 590 bool changed = false; 591 592 if (gimple_call_builtin_p (stmt, BUILT_IN_RETURN)) 593 return false; 594 595 /* First split basic block if stmt is not last. */ 596 if (stmt != gsi_stmt (gsi_last_bb (bb))) 597 { 598 if (stmt == gsi_stmt (gsi_last_nondebug_bb (bb))) 599 { 600 /* Don't split if there are only debug stmts 601 after stmt, that can result in -fcompare-debug 602 failures. Remove the debug stmts instead, 603 they should be all unreachable anyway. */ 604 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 605 for (gsi_next (&gsi); !gsi_end_p (gsi); ) 606 gsi_remove (&gsi, true); 607 } 608 else 609 { 610 split_block (bb, stmt); 611 changed = true; 612 } 613 } 614 615 /* If there is an LHS, remove it. */ 616 tree lhs = gimple_call_lhs (stmt); 617 if (lhs) 618 { 619 gimple_call_set_lhs (stmt, NULL_TREE); 620 621 /* We need to fix up the SSA name to avoid checking errors. */ 622 if (TREE_CODE (lhs) == SSA_NAME) 623 { 624 tree new_var = create_tmp_reg (TREE_TYPE (lhs)); 625 SET_SSA_NAME_VAR_OR_IDENTIFIER (lhs, new_var); 626 SSA_NAME_DEF_STMT (lhs) = gimple_build_nop (); 627 set_ssa_default_def (cfun, new_var, lhs); 628 } 629 630 update_stmt (stmt); 631 } 632 633 /* Mark the call as altering control flow. */ 634 if (!gimple_call_ctrl_altering_p (stmt)) 635 { 636 gimple_call_set_ctrl_altering (stmt, true); 637 changed = true; 638 } 639 640 return changed; 641} 642 643 644/* Tries to cleanup cfg in basic block BB. Returns true if anything 645 changes. */ 646 647static bool 648cleanup_tree_cfg_bb (basic_block bb) 649{ 650 bool retval = cleanup_control_flow_bb (bb); 651 652 if (tree_forwarder_block_p (bb, false) 653 && remove_forwarder_block (bb)) 654 return true; 655 656 /* Merging the blocks may create new opportunities for folding 657 conditional branches (due to the elimination of single-valued PHI 658 nodes). */ 659 if (single_succ_p (bb) 660 && can_merge_blocks_p (bb, single_succ (bb))) 661 { 662 /* If there is a merge opportunity with the predecessor 663 do nothing now but wait until we process the predecessor. 664 This happens when we visit BBs in a non-optimal order and 665 avoids quadratic behavior with adjusting stmts BB pointer. */ 666 if (single_pred_p (bb) 667 && can_merge_blocks_p (single_pred (bb), bb)) 668 ; 669 else 670 { 671 merge_blocks (bb, single_succ (bb)); 672 return true; 673 } 674 } 675 676 return retval; 677} 678 679/* Iterate the cfg cleanups, while anything changes. */ 680 681static bool 682cleanup_tree_cfg_1 (void) 683{ 684 bool retval = false; 685 basic_block bb; 686 unsigned i, n; 687 688 /* Prepare the worklists of altered blocks. */ 689 cfgcleanup_altered_bbs = BITMAP_ALLOC (NULL); 690 691 /* During forwarder block cleanup, we may redirect edges out of 692 SWITCH_EXPRs, which can get expensive. So we want to enable 693 recording of edge to CASE_LABEL_EXPR. */ 694 start_recording_case_labels (); 695 696 /* Start by iterating over all basic blocks. We cannot use FOR_EACH_BB_FN, 697 since the basic blocks may get removed. */ 698 n = last_basic_block_for_fn (cfun); 699 for (i = NUM_FIXED_BLOCKS; i < n; i++) 700 { 701 bb = BASIC_BLOCK_FOR_FN (cfun, i); 702 if (bb) 703 retval |= cleanup_tree_cfg_bb (bb); 704 } 705 706 /* Now process the altered blocks, as long as any are available. */ 707 while (!bitmap_empty_p (cfgcleanup_altered_bbs)) 708 { 709 i = bitmap_first_set_bit (cfgcleanup_altered_bbs); 710 bitmap_clear_bit (cfgcleanup_altered_bbs, i); 711 if (i < NUM_FIXED_BLOCKS) 712 continue; 713 714 bb = BASIC_BLOCK_FOR_FN (cfun, i); 715 if (!bb) 716 continue; 717 718 retval |= cleanup_tree_cfg_bb (bb); 719 } 720 721 end_recording_case_labels (); 722 BITMAP_FREE (cfgcleanup_altered_bbs); 723 return retval; 724} 725 726 727/* Remove unreachable blocks and other miscellaneous clean up work. 728 Return true if the flowgraph was modified, false otherwise. */ 729 730static bool 731cleanup_tree_cfg_noloop (void) 732{ 733 bool changed; 734 735 timevar_push (TV_TREE_CLEANUP_CFG); 736 737 /* Iterate until there are no more cleanups left to do. If any 738 iteration changed the flowgraph, set CHANGED to true. 739 740 If dominance information is available, there cannot be any unreachable 741 blocks. */ 742 if (!dom_info_available_p (CDI_DOMINATORS)) 743 { 744 changed = delete_unreachable_blocks (); 745 calculate_dominance_info (CDI_DOMINATORS); 746 } 747 else 748 { 749#ifdef ENABLE_CHECKING 750 verify_dominators (CDI_DOMINATORS); 751#endif 752 changed = false; 753 } 754 755 changed |= cleanup_tree_cfg_1 (); 756 757 gcc_assert (dom_info_available_p (CDI_DOMINATORS)); 758 compact_blocks (); 759 760#ifdef ENABLE_CHECKING 761 verify_flow_info (); 762#endif 763 764 timevar_pop (TV_TREE_CLEANUP_CFG); 765 766 if (changed && current_loops) 767 loops_state_set (LOOPS_NEED_FIXUP); 768 769 return changed; 770} 771 772/* Repairs loop structures. */ 773 774static void 775repair_loop_structures (void) 776{ 777 bitmap changed_bbs; 778 unsigned n_new_loops; 779 780 calculate_dominance_info (CDI_DOMINATORS); 781 782 timevar_push (TV_REPAIR_LOOPS); 783 changed_bbs = BITMAP_ALLOC (NULL); 784 n_new_loops = fix_loop_structure (changed_bbs); 785 786 /* This usually does nothing. But sometimes parts of cfg that originally 787 were inside a loop get out of it due to edge removal (since they 788 become unreachable by back edges from latch). Also a former 789 irreducible loop can become reducible - in this case force a full 790 rewrite into loop-closed SSA form. */ 791 if (loops_state_satisfies_p (LOOP_CLOSED_SSA)) 792 rewrite_into_loop_closed_ssa (n_new_loops ? NULL : changed_bbs, 793 TODO_update_ssa); 794 795 BITMAP_FREE (changed_bbs); 796 797#ifdef ENABLE_CHECKING 798 verify_loop_structure (); 799#endif 800 scev_reset (); 801 802 timevar_pop (TV_REPAIR_LOOPS); 803} 804 805/* Cleanup cfg and repair loop structures. */ 806 807bool 808cleanup_tree_cfg (void) 809{ 810 bool changed = cleanup_tree_cfg_noloop (); 811 812 if (current_loops != NULL 813 && loops_state_satisfies_p (LOOPS_NEED_FIXUP)) 814 repair_loop_structures (); 815 816 return changed; 817} 818 819/* Tries to merge the PHI nodes at BB into those at BB's sole successor. 820 Returns true if successful. */ 821 822static bool 823remove_forwarder_block_with_phi (basic_block bb) 824{ 825 edge succ = single_succ_edge (bb); 826 basic_block dest = succ->dest; 827 gimple label; 828 basic_block dombb, domdest, dom; 829 830 /* We check for infinite loops already in tree_forwarder_block_p. 831 However it may happen that the infinite loop is created 832 afterwards due to removal of forwarders. */ 833 if (dest == bb) 834 return false; 835 836 /* If the destination block consists of a nonlocal label, do not 837 merge it. */ 838 label = first_stmt (dest); 839 if (label) 840 if (glabel *label_stmt = dyn_cast <glabel *> (label)) 841 if (DECL_NONLOCAL (gimple_label_label (label_stmt))) 842 return false; 843 844 /* Record BB's single pred in case we need to update the father 845 loop's latch information later. */ 846 basic_block pred = NULL; 847 if (single_pred_p (bb)) 848 pred = single_pred (bb); 849 850 /* Redirect each incoming edge to BB to DEST. */ 851 while (EDGE_COUNT (bb->preds) > 0) 852 { 853 edge e = EDGE_PRED (bb, 0), s; 854 gphi_iterator gsi; 855 856 s = find_edge (e->src, dest); 857 if (s) 858 { 859 /* We already have an edge S from E->src to DEST. If S and 860 E->dest's sole successor edge have the same PHI arguments 861 at DEST, redirect S to DEST. */ 862 if (phi_alternatives_equal (dest, s, succ)) 863 { 864 e = redirect_edge_and_branch (e, dest); 865 redirect_edge_var_map_clear (e); 866 continue; 867 } 868 869 /* PHI arguments are different. Create a forwarder block by 870 splitting E so that we can merge PHI arguments on E to 871 DEST. */ 872 e = single_succ_edge (split_edge (e)); 873 } 874 875 s = redirect_edge_and_branch (e, dest); 876 877 /* redirect_edge_and_branch must not create a new edge. */ 878 gcc_assert (s == e); 879 880 /* Add to the PHI nodes at DEST each PHI argument removed at the 881 destination of E. */ 882 for (gsi = gsi_start_phis (dest); 883 !gsi_end_p (gsi); 884 gsi_next (&gsi)) 885 { 886 gphi *phi = gsi.phi (); 887 tree def = gimple_phi_arg_def (phi, succ->dest_idx); 888 source_location locus = gimple_phi_arg_location_from_edge (phi, succ); 889 890 if (TREE_CODE (def) == SSA_NAME) 891 { 892 /* If DEF is one of the results of PHI nodes removed during 893 redirection, replace it with the PHI argument that used 894 to be on E. */ 895 vec<edge_var_map> *head = redirect_edge_var_map_vector (e); 896 size_t length = head ? head->length () : 0; 897 for (size_t i = 0; i < length; i++) 898 { 899 edge_var_map *vm = &(*head)[i]; 900 tree old_arg = redirect_edge_var_map_result (vm); 901 tree new_arg = redirect_edge_var_map_def (vm); 902 903 if (def == old_arg) 904 { 905 def = new_arg; 906 locus = redirect_edge_var_map_location (vm); 907 break; 908 } 909 } 910 } 911 912 add_phi_arg (phi, def, s, locus); 913 } 914 915 redirect_edge_var_map_clear (e); 916 } 917 918 /* Update the dominators. */ 919 dombb = get_immediate_dominator (CDI_DOMINATORS, bb); 920 domdest = get_immediate_dominator (CDI_DOMINATORS, dest); 921 if (domdest == bb) 922 { 923 /* Shortcut to avoid calling (relatively expensive) 924 nearest_common_dominator unless necessary. */ 925 dom = dombb; 926 } 927 else 928 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb); 929 930 set_immediate_dominator (CDI_DOMINATORS, dest, dom); 931 932 /* Adjust latch infomation of BB's parent loop as otherwise 933 the cfg hook has a hard time not to kill the loop. */ 934 if (current_loops && bb->loop_father->latch == bb) 935 bb->loop_father->latch = pred; 936 937 /* Remove BB since all of BB's incoming edges have been redirected 938 to DEST. */ 939 delete_basic_block (bb); 940 941 return true; 942} 943 944/* This pass merges PHI nodes if one feeds into another. For example, 945 suppose we have the following: 946 947 goto <bb 9> (<L9>); 948 949<L8>:; 950 tem_17 = foo (); 951 952 # tem_6 = PHI <tem_17(8), tem_23(7)>; 953<L9>:; 954 955 # tem_3 = PHI <tem_6(9), tem_2(5)>; 956<L10>:; 957 958 Then we merge the first PHI node into the second one like so: 959 960 goto <bb 9> (<L10>); 961 962<L8>:; 963 tem_17 = foo (); 964 965 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>; 966<L10>:; 967*/ 968 969namespace { 970 971const pass_data pass_data_merge_phi = 972{ 973 GIMPLE_PASS, /* type */ 974 "mergephi", /* name */ 975 OPTGROUP_NONE, /* optinfo_flags */ 976 TV_TREE_MERGE_PHI, /* tv_id */ 977 ( PROP_cfg | PROP_ssa ), /* properties_required */ 978 0, /* properties_provided */ 979 0, /* properties_destroyed */ 980 0, /* todo_flags_start */ 981 0, /* todo_flags_finish */ 982}; 983 984class pass_merge_phi : public gimple_opt_pass 985{ 986public: 987 pass_merge_phi (gcc::context *ctxt) 988 : gimple_opt_pass (pass_data_merge_phi, ctxt) 989 {} 990 991 /* opt_pass methods: */ 992 opt_pass * clone () { return new pass_merge_phi (m_ctxt); } 993 virtual unsigned int execute (function *); 994 995}; // class pass_merge_phi 996 997unsigned int 998pass_merge_phi::execute (function *fun) 999{ 1000 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun)); 1001 basic_block *current = worklist; 1002 basic_block bb; 1003 1004 calculate_dominance_info (CDI_DOMINATORS); 1005 1006 /* Find all PHI nodes that we may be able to merge. */ 1007 FOR_EACH_BB_FN (bb, fun) 1008 { 1009 basic_block dest; 1010 1011 /* Look for a forwarder block with PHI nodes. */ 1012 if (!tree_forwarder_block_p (bb, true)) 1013 continue; 1014 1015 dest = single_succ (bb); 1016 1017 /* We have to feed into another basic block with PHI 1018 nodes. */ 1019 if (gimple_seq_empty_p (phi_nodes (dest)) 1020 /* We don't want to deal with a basic block with 1021 abnormal edges. */ 1022 || bb_has_abnormal_pred (bb)) 1023 continue; 1024 1025 if (!dominated_by_p (CDI_DOMINATORS, dest, bb)) 1026 { 1027 /* If BB does not dominate DEST, then the PHI nodes at 1028 DEST must be the only users of the results of the PHI 1029 nodes at BB. */ 1030 *current++ = bb; 1031 } 1032 else 1033 { 1034 gphi_iterator gsi; 1035 unsigned int dest_idx = single_succ_edge (bb)->dest_idx; 1036 1037 /* BB dominates DEST. There may be many users of the PHI 1038 nodes in BB. However, there is still a trivial case we 1039 can handle. If the result of every PHI in BB is used 1040 only by a PHI in DEST, then we can trivially merge the 1041 PHI nodes from BB into DEST. */ 1042 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 1043 gsi_next (&gsi)) 1044 { 1045 gphi *phi = gsi.phi (); 1046 tree result = gimple_phi_result (phi); 1047 use_operand_p imm_use; 1048 gimple use_stmt; 1049 1050 /* If the PHI's result is never used, then we can just 1051 ignore it. */ 1052 if (has_zero_uses (result)) 1053 continue; 1054 1055 /* Get the single use of the result of this PHI node. */ 1056 if (!single_imm_use (result, &imm_use, &use_stmt) 1057 || gimple_code (use_stmt) != GIMPLE_PHI 1058 || gimple_bb (use_stmt) != dest 1059 || gimple_phi_arg_def (use_stmt, dest_idx) != result) 1060 break; 1061 } 1062 1063 /* If the loop above iterated through all the PHI nodes 1064 in BB, then we can merge the PHIs from BB into DEST. */ 1065 if (gsi_end_p (gsi)) 1066 *current++ = bb; 1067 } 1068 } 1069 1070 /* Now let's drain WORKLIST. */ 1071 bool changed = false; 1072 while (current != worklist) 1073 { 1074 bb = *--current; 1075 changed |= remove_forwarder_block_with_phi (bb); 1076 } 1077 free (worklist); 1078 1079 /* Removing forwarder blocks can cause formerly irreducible loops 1080 to become reducible if we merged two entry blocks. */ 1081 if (changed 1082 && current_loops) 1083 loops_state_set (LOOPS_NEED_FIXUP); 1084 1085 return 0; 1086} 1087 1088} // anon namespace 1089 1090gimple_opt_pass * 1091make_pass_merge_phi (gcc::context *ctxt) 1092{ 1093 return new pass_merge_phi (ctxt); 1094} 1095 1096/* Pass: cleanup the CFG just before expanding trees to RTL. 1097 This is just a round of label cleanups and case node grouping 1098 because after the tree optimizers have run such cleanups may 1099 be necessary. */ 1100 1101static unsigned int 1102execute_cleanup_cfg_post_optimizing (void) 1103{ 1104 unsigned int todo = execute_fixup_cfg (); 1105 if (cleanup_tree_cfg ()) 1106 { 1107 todo &= ~TODO_cleanup_cfg; 1108 todo |= TODO_update_ssa; 1109 } 1110 maybe_remove_unreachable_handlers (); 1111 cleanup_dead_labels (); 1112 group_case_labels (); 1113 if ((flag_compare_debug_opt || flag_compare_debug) 1114 && flag_dump_final_insns) 1115 { 1116 FILE *final_output = fopen (flag_dump_final_insns, "a"); 1117 1118 if (!final_output) 1119 { 1120 error ("could not open final insn dump file %qs: %m", 1121 flag_dump_final_insns); 1122 flag_dump_final_insns = NULL; 1123 } 1124 else 1125 { 1126 int save_unnumbered = flag_dump_unnumbered; 1127 int save_noaddr = flag_dump_noaddr; 1128 1129 flag_dump_noaddr = flag_dump_unnumbered = 1; 1130 fprintf (final_output, "\n"); 1131 dump_enumerated_decls (final_output, dump_flags | TDF_NOUID); 1132 flag_dump_noaddr = save_noaddr; 1133 flag_dump_unnumbered = save_unnumbered; 1134 if (fclose (final_output)) 1135 { 1136 error ("could not close final insn dump file %qs: %m", 1137 flag_dump_final_insns); 1138 flag_dump_final_insns = NULL; 1139 } 1140 } 1141 } 1142 return todo; 1143} 1144 1145namespace { 1146 1147const pass_data pass_data_cleanup_cfg_post_optimizing = 1148{ 1149 GIMPLE_PASS, /* type */ 1150 "optimized", /* name */ 1151 OPTGROUP_NONE, /* optinfo_flags */ 1152 TV_TREE_CLEANUP_CFG, /* tv_id */ 1153 PROP_cfg, /* properties_required */ 1154 0, /* properties_provided */ 1155 0, /* properties_destroyed */ 1156 0, /* todo_flags_start */ 1157 TODO_remove_unused_locals, /* todo_flags_finish */ 1158}; 1159 1160class pass_cleanup_cfg_post_optimizing : public gimple_opt_pass 1161{ 1162public: 1163 pass_cleanup_cfg_post_optimizing (gcc::context *ctxt) 1164 : gimple_opt_pass (pass_data_cleanup_cfg_post_optimizing, ctxt) 1165 {} 1166 1167 /* opt_pass methods: */ 1168 virtual unsigned int execute (function *) 1169 { 1170 return execute_cleanup_cfg_post_optimizing (); 1171 } 1172 1173}; // class pass_cleanup_cfg_post_optimizing 1174 1175} // anon namespace 1176 1177gimple_opt_pass * 1178make_pass_cleanup_cfg_post_optimizing (gcc::context *ctxt) 1179{ 1180 return new pass_cleanup_cfg_post_optimizing (ctxt); 1181} 1182 1183 1184