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