1169689Skan/* CFG cleanup for trees. 2169689Skan Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 3169689Skan Free Software Foundation, Inc. 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "tree.h" 27169689Skan#include "rtl.h" 28169689Skan#include "tm_p.h" 29169689Skan#include "hard-reg-set.h" 30169689Skan#include "basic-block.h" 31169689Skan#include "output.h" 32169689Skan#include "toplev.h" 33169689Skan#include "flags.h" 34169689Skan#include "function.h" 35169689Skan#include "expr.h" 36169689Skan#include "ggc.h" 37169689Skan#include "langhooks.h" 38169689Skan#include "diagnostic.h" 39169689Skan#include "tree-flow.h" 40169689Skan#include "timevar.h" 41169689Skan#include "tree-dump.h" 42169689Skan#include "tree-pass.h" 43169689Skan#include "toplev.h" 44169689Skan#include "except.h" 45169689Skan#include "cfgloop.h" 46169689Skan#include "cfglayout.h" 47169689Skan#include "hashtab.h" 48169689Skan#include "tree-ssa-propagate.h" 49169689Skan#include "tree-scalar-evolution.h" 50169689Skan 51169689Skan/* Remove any fallthru edge from EV. Return true if an edge was removed. */ 52169689Skan 53169689Skanstatic bool 54169689Skanremove_fallthru_edge (VEC(edge,gc) *ev) 55169689Skan{ 56169689Skan edge_iterator ei; 57169689Skan edge e; 58169689Skan 59169689Skan FOR_EACH_EDGE (e, ei, ev) 60169689Skan if ((e->flags & EDGE_FALLTHRU) != 0) 61169689Skan { 62169689Skan remove_edge (e); 63169689Skan return true; 64169689Skan } 65169689Skan return false; 66169689Skan} 67169689Skan 68169689Skan/* Disconnect an unreachable block in the control expression starting 69169689Skan at block BB. */ 70169689Skan 71169689Skanstatic bool 72169689Skancleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi) 73169689Skan{ 74169689Skan edge taken_edge; 75169689Skan bool retval = false; 76169689Skan tree expr = bsi_stmt (bsi), val; 77169689Skan 78169689Skan if (!single_succ_p (bb)) 79169689Skan { 80169689Skan edge e; 81169689Skan edge_iterator ei; 82169689Skan bool warned; 83169689Skan 84169689Skan fold_defer_overflow_warnings (); 85169689Skan 86169689Skan switch (TREE_CODE (expr)) 87169689Skan { 88169689Skan case COND_EXPR: 89169689Skan val = fold (COND_EXPR_COND (expr)); 90169689Skan break; 91169689Skan 92169689Skan case SWITCH_EXPR: 93169689Skan val = fold (SWITCH_COND (expr)); 94169689Skan if (TREE_CODE (val) != INTEGER_CST) 95169689Skan { 96169689Skan fold_undefer_and_ignore_overflow_warnings (); 97169689Skan return false; 98169689Skan } 99169689Skan break; 100169689Skan 101169689Skan default: 102169689Skan gcc_unreachable (); 103169689Skan } 104169689Skan 105169689Skan taken_edge = find_taken_edge (bb, val); 106169689Skan if (!taken_edge) 107169689Skan { 108169689Skan fold_undefer_and_ignore_overflow_warnings (); 109169689Skan return false; 110169689Skan } 111169689Skan 112169689Skan /* Remove all the edges except the one that is always executed. */ 113169689Skan warned = false; 114169689Skan for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 115169689Skan { 116169689Skan if (e != taken_edge) 117169689Skan { 118169689Skan if (!warned) 119169689Skan { 120169689Skan fold_undefer_overflow_warnings 121169689Skan (true, expr, WARN_STRICT_OVERFLOW_CONDITIONAL); 122169689Skan warned = true; 123169689Skan } 124169689Skan 125169689Skan taken_edge->probability += e->probability; 126169689Skan taken_edge->count += e->count; 127169689Skan remove_edge (e); 128169689Skan retval = true; 129169689Skan } 130169689Skan else 131169689Skan ei_next (&ei); 132169689Skan } 133169689Skan if (!warned) 134169689Skan fold_undefer_and_ignore_overflow_warnings (); 135169689Skan if (taken_edge->probability > REG_BR_PROB_BASE) 136169689Skan taken_edge->probability = REG_BR_PROB_BASE; 137169689Skan } 138169689Skan else 139169689Skan taken_edge = single_succ_edge (bb); 140169689Skan 141169689Skan bsi_remove (&bsi, true); 142169689Skan taken_edge->flags = EDGE_FALLTHRU; 143169689Skan 144169689Skan /* We removed some paths from the cfg. */ 145169689Skan free_dominance_info (CDI_DOMINATORS); 146169689Skan 147169689Skan return retval; 148169689Skan} 149169689Skan 150169689Skan/* A list of all the noreturn calls passed to modify_stmt. 151169689Skan cleanup_control_flow uses it to detect cases where a mid-block 152169689Skan indirect call has been turned into a noreturn call. When this 153169689Skan happens, all the instructions after the call are no longer 154169689Skan reachable and must be deleted as dead. */ 155169689Skan 156169689SkanVEC(tree,gc) *modified_noreturn_calls; 157169689Skan 158169689Skan/* Try to remove superfluous control structures. */ 159169689Skan 160169689Skanstatic bool 161169689Skancleanup_control_flow (void) 162169689Skan{ 163169689Skan basic_block bb; 164169689Skan block_stmt_iterator bsi; 165169689Skan bool retval = false; 166169689Skan tree stmt; 167169689Skan 168169689Skan /* Detect cases where a mid-block call is now known not to return. */ 169169689Skan while (VEC_length (tree, modified_noreturn_calls)) 170169689Skan { 171169689Skan stmt = VEC_pop (tree, modified_noreturn_calls); 172169689Skan bb = bb_for_stmt (stmt); 173169689Skan if (bb != NULL && last_stmt (bb) != stmt && noreturn_call_p (stmt)) 174169689Skan split_block (bb, stmt); 175169689Skan } 176169689Skan 177169689Skan FOR_EACH_BB (bb) 178169689Skan { 179169689Skan bsi = bsi_last (bb); 180169689Skan 181169689Skan /* If the last statement of the block could throw and now cannot, 182169689Skan we need to prune cfg. */ 183169689Skan retval |= tree_purge_dead_eh_edges (bb); 184169689Skan 185169689Skan if (bsi_end_p (bsi)) 186169689Skan continue; 187169689Skan 188169689Skan stmt = bsi_stmt (bsi); 189169689Skan 190169689Skan if (TREE_CODE (stmt) == COND_EXPR 191169689Skan || TREE_CODE (stmt) == SWITCH_EXPR) 192169689Skan retval |= cleanup_control_expr_graph (bb, bsi); 193169689Skan /* If we had a computed goto which has a compile-time determinable 194169689Skan destination, then we can eliminate the goto. */ 195169689Skan else if (TREE_CODE (stmt) == GOTO_EXPR 196169689Skan && TREE_CODE (GOTO_DESTINATION (stmt)) == ADDR_EXPR 197169689Skan && (TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt), 0)) 198169689Skan == LABEL_DECL)) 199169689Skan { 200169689Skan edge e; 201169689Skan tree label; 202169689Skan edge_iterator ei; 203169689Skan basic_block target_block; 204169689Skan bool removed_edge = false; 205169689Skan 206169689Skan /* First look at all the outgoing edges. Delete any outgoing 207169689Skan edges which do not go to the right block. For the one 208169689Skan edge which goes to the right block, fix up its flags. */ 209169689Skan label = TREE_OPERAND (GOTO_DESTINATION (stmt), 0); 210169689Skan target_block = label_to_block (label); 211169689Skan for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 212169689Skan { 213169689Skan if (e->dest != target_block) 214169689Skan { 215169689Skan removed_edge = true; 216169689Skan remove_edge (e); 217169689Skan } 218169689Skan else 219169689Skan { 220169689Skan /* Turn off the EDGE_ABNORMAL flag. */ 221169689Skan e->flags &= ~EDGE_ABNORMAL; 222169689Skan 223169689Skan /* And set EDGE_FALLTHRU. */ 224169689Skan e->flags |= EDGE_FALLTHRU; 225169689Skan ei_next (&ei); 226169689Skan } 227169689Skan } 228169689Skan 229169689Skan /* If we removed one or more edges, then we will need to fix the 230169689Skan dominators. It may be possible to incrementally update them. */ 231169689Skan if (removed_edge) 232169689Skan free_dominance_info (CDI_DOMINATORS); 233169689Skan 234169689Skan /* Remove the GOTO_EXPR as it is not needed. The CFG has all the 235169689Skan relevant information we need. */ 236169689Skan bsi_remove (&bsi, true); 237169689Skan retval = true; 238169689Skan } 239169689Skan 240169689Skan /* Check for indirect calls that have been turned into 241169689Skan noreturn calls. */ 242169689Skan else if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs)) 243169689Skan { 244169689Skan free_dominance_info (CDI_DOMINATORS); 245169689Skan retval = true; 246169689Skan } 247169689Skan } 248169689Skan return retval; 249169689Skan} 250169689Skan 251169689Skan/* Return true if basic block BB does nothing except pass control 252169689Skan flow to another block and that we can safely insert a label at 253169689Skan the start of the successor block. 254169689Skan 255169689Skan As a precondition, we require that BB be not equal to 256169689Skan ENTRY_BLOCK_PTR. */ 257169689Skan 258169689Skanstatic bool 259169689Skantree_forwarder_block_p (basic_block bb, bool phi_wanted) 260169689Skan{ 261169689Skan block_stmt_iterator bsi; 262169689Skan edge_iterator ei; 263169689Skan edge e, succ; 264169689Skan basic_block dest; 265169689Skan 266169689Skan /* BB must have a single outgoing edge. */ 267169689Skan if (single_succ_p (bb) != 1 268169689Skan /* If PHI_WANTED is false, BB must not have any PHI nodes. 269169689Skan Otherwise, BB must have PHI nodes. */ 270169689Skan || (phi_nodes (bb) != NULL_TREE) != phi_wanted 271169689Skan /* BB may not be a predecessor of EXIT_BLOCK_PTR. */ 272169689Skan || single_succ (bb) == EXIT_BLOCK_PTR 273169689Skan /* Nor should this be an infinite loop. */ 274169689Skan || single_succ (bb) == bb 275169689Skan /* BB may not have an abnormal outgoing edge. */ 276169689Skan || (single_succ_edge (bb)->flags & EDGE_ABNORMAL)) 277169689Skan return false; 278169689Skan 279169689Skan#if ENABLE_CHECKING 280169689Skan gcc_assert (bb != ENTRY_BLOCK_PTR); 281169689Skan#endif 282169689Skan 283169689Skan /* Now walk through the statements backward. We can ignore labels, 284169689Skan anything else means this is not a forwarder block. */ 285169689Skan for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 286169689Skan { 287169689Skan tree stmt = bsi_stmt (bsi); 288169689Skan 289169689Skan switch (TREE_CODE (stmt)) 290169689Skan { 291169689Skan case LABEL_EXPR: 292169689Skan if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))) 293169689Skan return false; 294169689Skan break; 295169689Skan 296169689Skan default: 297169689Skan return false; 298169689Skan } 299169689Skan } 300169689Skan 301169689Skan if (find_edge (ENTRY_BLOCK_PTR, bb)) 302169689Skan return false; 303169689Skan 304169689Skan if (current_loops) 305169689Skan { 306169689Skan basic_block dest; 307169689Skan /* Protect loop latches, headers and preheaders. */ 308169689Skan if (bb->loop_father->header == bb) 309169689Skan return false; 310169689Skan dest = EDGE_SUCC (bb, 0)->dest; 311169689Skan 312169689Skan if (dest->loop_father->header == dest) 313169689Skan return false; 314169689Skan } 315169689Skan 316169689Skan /* If we have an EH edge leaving this block, make sure that the 317169689Skan destination of this block has only one predecessor. This ensures 318169689Skan that we don't get into the situation where we try to remove two 319169689Skan forwarders that go to the same basic block but are handlers for 320169689Skan different EH regions. */ 321169689Skan succ = single_succ_edge (bb); 322169689Skan dest = succ->dest; 323169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 324169689Skan { 325169689Skan if (e->flags & EDGE_EH) 326169689Skan { 327169689Skan if (!single_pred_p (dest)) 328169689Skan return false; 329169689Skan } 330169689Skan } 331169689Skan 332169689Skan return true; 333169689Skan} 334169689Skan 335169689Skan/* Return true if BB has at least one abnormal incoming edge. */ 336169689Skan 337169689Skanstatic inline bool 338169689Skanhas_abnormal_incoming_edge_p (basic_block bb) 339169689Skan{ 340169689Skan edge e; 341169689Skan edge_iterator ei; 342169689Skan 343169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 344169689Skan if (e->flags & EDGE_ABNORMAL) 345169689Skan return true; 346169689Skan 347169689Skan return false; 348169689Skan} 349169689Skan 350169689Skan/* If all the PHI nodes in DEST have alternatives for E1 and E2 and 351169689Skan those alternatives are equal in each of the PHI nodes, then return 352169689Skan true, else return false. */ 353169689Skan 354169689Skanstatic bool 355169689Skanphi_alternatives_equal (basic_block dest, edge e1, edge e2) 356169689Skan{ 357169689Skan int n1 = e1->dest_idx; 358169689Skan int n2 = e2->dest_idx; 359169689Skan tree phi; 360169689Skan 361169689Skan for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) 362169689Skan { 363169689Skan tree val1 = PHI_ARG_DEF (phi, n1); 364169689Skan tree val2 = PHI_ARG_DEF (phi, n2); 365169689Skan 366169689Skan gcc_assert (val1 != NULL_TREE); 367169689Skan gcc_assert (val2 != NULL_TREE); 368169689Skan 369169689Skan if (!operand_equal_for_phi_arg_p (val1, val2)) 370169689Skan return false; 371169689Skan } 372169689Skan 373169689Skan return true; 374169689Skan} 375169689Skan 376169689Skan/* Removes forwarder block BB. Returns false if this failed. If a new 377169689Skan forwarder block is created due to redirection of edges, it is 378169689Skan stored to worklist. */ 379169689Skan 380169689Skanstatic bool 381169689Skanremove_forwarder_block (basic_block bb, basic_block **worklist) 382169689Skan{ 383169689Skan edge succ = single_succ_edge (bb), e, s; 384169689Skan basic_block dest = succ->dest; 385169689Skan tree label; 386169689Skan tree phi; 387169689Skan edge_iterator ei; 388169689Skan block_stmt_iterator bsi, bsi_to; 389169689Skan bool seen_abnormal_edge = false; 390169689Skan 391169689Skan /* We check for infinite loops already in tree_forwarder_block_p. 392169689Skan However it may happen that the infinite loop is created 393169689Skan afterwards due to removal of forwarders. */ 394169689Skan if (dest == bb) 395169689Skan return false; 396169689Skan 397169689Skan /* If the destination block consists of a nonlocal label, do not merge 398169689Skan it. */ 399169689Skan label = first_stmt (dest); 400169689Skan if (label 401169689Skan && TREE_CODE (label) == LABEL_EXPR 402169689Skan && DECL_NONLOCAL (LABEL_EXPR_LABEL (label))) 403169689Skan return false; 404169689Skan 405169689Skan /* If there is an abnormal edge to basic block BB, but not into 406169689Skan dest, problems might occur during removal of the phi node at out 407169689Skan of ssa due to overlapping live ranges of registers. 408169689Skan 409169689Skan If there is an abnormal edge in DEST, the problems would occur 410169689Skan anyway since cleanup_dead_labels would then merge the labels for 411169689Skan two different eh regions, and rest of exception handling code 412169689Skan does not like it. 413169689Skan 414169689Skan So if there is an abnormal edge to BB, proceed only if there is 415169689Skan no abnormal edge to DEST and there are no phi nodes in DEST. */ 416169689Skan if (has_abnormal_incoming_edge_p (bb)) 417169689Skan { 418169689Skan seen_abnormal_edge = true; 419169689Skan 420169689Skan if (has_abnormal_incoming_edge_p (dest) 421169689Skan || phi_nodes (dest) != NULL_TREE) 422169689Skan return false; 423169689Skan } 424169689Skan 425169689Skan /* If there are phi nodes in DEST, and some of the blocks that are 426169689Skan predecessors of BB are also predecessors of DEST, check that the 427169689Skan phi node arguments match. */ 428169689Skan if (phi_nodes (dest)) 429169689Skan { 430169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 431169689Skan { 432169689Skan s = find_edge (e->src, dest); 433169689Skan if (!s) 434169689Skan continue; 435169689Skan 436169689Skan if (!phi_alternatives_equal (dest, succ, s)) 437169689Skan return false; 438169689Skan } 439169689Skan } 440169689Skan 441169689Skan /* Redirect the edges. */ 442169689Skan for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 443169689Skan { 444169689Skan if (e->flags & EDGE_ABNORMAL) 445169689Skan { 446169689Skan /* If there is an abnormal edge, redirect it anyway, and 447169689Skan move the labels to the new block to make it legal. */ 448169689Skan s = redirect_edge_succ_nodup (e, dest); 449169689Skan } 450169689Skan else 451169689Skan s = redirect_edge_and_branch (e, dest); 452169689Skan 453169689Skan if (s == e) 454169689Skan { 455169689Skan /* Create arguments for the phi nodes, since the edge was not 456169689Skan here before. */ 457169689Skan for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) 458169689Skan add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s); 459169689Skan } 460169689Skan else 461169689Skan { 462169689Skan /* The source basic block might become a forwarder. We know 463169689Skan that it was not a forwarder before, since it used to have 464169689Skan at least two outgoing edges, so we may just add it to 465169689Skan worklist. */ 466169689Skan if (tree_forwarder_block_p (s->src, false)) 467169689Skan *(*worklist)++ = s->src; 468169689Skan } 469169689Skan } 470169689Skan 471169689Skan if (seen_abnormal_edge) 472169689Skan { 473169689Skan /* Move the labels to the new block, so that the redirection of 474169689Skan the abnormal edges works. */ 475169689Skan 476169689Skan bsi_to = bsi_start (dest); 477169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 478169689Skan { 479169689Skan label = bsi_stmt (bsi); 480169689Skan gcc_assert (TREE_CODE (label) == LABEL_EXPR); 481169689Skan bsi_remove (&bsi, false); 482169689Skan bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING); 483169689Skan } 484169689Skan } 485169689Skan 486169689Skan /* Update the dominators. */ 487169689Skan if (dom_info_available_p (CDI_DOMINATORS)) 488169689Skan { 489169689Skan basic_block dom, dombb, domdest; 490169689Skan 491169689Skan dombb = get_immediate_dominator (CDI_DOMINATORS, bb); 492169689Skan domdest = get_immediate_dominator (CDI_DOMINATORS, dest); 493169689Skan if (domdest == bb) 494169689Skan { 495169689Skan /* Shortcut to avoid calling (relatively expensive) 496169689Skan nearest_common_dominator unless necessary. */ 497169689Skan dom = dombb; 498169689Skan } 499169689Skan else 500169689Skan dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb); 501169689Skan 502169689Skan set_immediate_dominator (CDI_DOMINATORS, dest, dom); 503169689Skan } 504169689Skan 505169689Skan /* And kill the forwarder block. */ 506169689Skan delete_basic_block (bb); 507169689Skan 508169689Skan return true; 509169689Skan} 510169689Skan 511169689Skan/* Removes forwarder blocks. */ 512169689Skan 513169689Skanstatic bool 514169689Skancleanup_forwarder_blocks (void) 515169689Skan{ 516169689Skan basic_block bb; 517169689Skan bool changed = false; 518169689Skan basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks); 519169689Skan basic_block *current = worklist; 520169689Skan 521169689Skan FOR_EACH_BB (bb) 522169689Skan { 523169689Skan if (tree_forwarder_block_p (bb, false)) 524169689Skan *current++ = bb; 525169689Skan } 526169689Skan 527169689Skan while (current != worklist) 528169689Skan { 529169689Skan bb = *--current; 530169689Skan changed |= remove_forwarder_block (bb, ¤t); 531169689Skan } 532169689Skan 533169689Skan free (worklist); 534169689Skan return changed; 535169689Skan} 536169689Skan 537169689Skan/* Do one round of CFG cleanup. */ 538169689Skan 539169689Skanstatic bool 540169689Skancleanup_tree_cfg_1 (void) 541169689Skan{ 542169689Skan bool retval; 543169689Skan 544169689Skan retval = cleanup_control_flow (); 545169689Skan retval |= delete_unreachable_blocks (); 546169689Skan 547169689Skan /* Forwarder blocks can carry line number information which is 548169689Skan useful when debugging, so we only clean them up when 549169689Skan optimizing. */ 550169689Skan 551169689Skan if (optimize > 0) 552169689Skan { 553169689Skan /* cleanup_forwarder_blocks can redirect edges out of 554169689Skan SWITCH_EXPRs, which can get expensive. So we want to enable 555169689Skan recording of edge to CASE_LABEL_EXPR mappings around the call 556169689Skan to cleanup_forwarder_blocks. */ 557169689Skan start_recording_case_labels (); 558169689Skan retval |= cleanup_forwarder_blocks (); 559169689Skan end_recording_case_labels (); 560169689Skan } 561169689Skan 562169689Skan /* Merging the blocks may create new opportunities for folding 563169689Skan conditional branches (due to the elimination of single-valued PHI 564169689Skan nodes). */ 565169689Skan retval |= merge_seq_blocks (); 566169689Skan 567169689Skan return retval; 568169689Skan} 569169689Skan 570169689Skan 571169689Skan/* Remove unreachable blocks and other miscellaneous clean up work. 572169689Skan Return true if the flowgraph was modified, false otherwise. */ 573169689Skan 574169689Skanbool 575169689Skancleanup_tree_cfg (void) 576169689Skan{ 577169689Skan bool retval, changed; 578169689Skan 579169689Skan timevar_push (TV_TREE_CLEANUP_CFG); 580169689Skan 581169689Skan /* Iterate until there are no more cleanups left to do. If any 582169689Skan iteration changed the flowgraph, set CHANGED to true. */ 583169689Skan changed = false; 584169689Skan do 585169689Skan { 586169689Skan retval = cleanup_tree_cfg_1 (); 587169689Skan changed |= retval; 588169689Skan } 589169689Skan while (retval); 590169689Skan 591169689Skan compact_blocks (); 592169689Skan 593169689Skan#ifdef ENABLE_CHECKING 594169689Skan verify_flow_info (); 595169689Skan#endif 596169689Skan 597169689Skan timevar_pop (TV_TREE_CLEANUP_CFG); 598169689Skan 599169689Skan return changed; 600169689Skan} 601169689Skan 602169689Skan/* Cleanup cfg and repair loop structures. */ 603169689Skan 604169689Skanvoid 605169689Skancleanup_tree_cfg_loop (void) 606169689Skan{ 607169689Skan bool changed = cleanup_tree_cfg (); 608169689Skan 609169689Skan if (changed) 610169689Skan { 611169689Skan bitmap changed_bbs = BITMAP_ALLOC (NULL); 612169689Skan fix_loop_structure (current_loops, changed_bbs); 613169689Skan calculate_dominance_info (CDI_DOMINATORS); 614169689Skan 615169689Skan /* This usually does nothing. But sometimes parts of cfg that originally 616169689Skan were inside a loop get out of it due to edge removal (since they 617169689Skan become unreachable by back edges from latch). */ 618169689Skan rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa); 619169689Skan 620169689Skan BITMAP_FREE (changed_bbs); 621169689Skan 622169689Skan#ifdef ENABLE_CHECKING 623169689Skan verify_loop_structure (current_loops); 624169689Skan#endif 625169689Skan scev_reset (); 626169689Skan } 627169689Skan} 628169689Skan 629169689Skan/* Merge the PHI nodes at BB into those at BB's sole successor. */ 630169689Skan 631169689Skanstatic void 632169689Skanremove_forwarder_block_with_phi (basic_block bb) 633169689Skan{ 634169689Skan edge succ = single_succ_edge (bb); 635169689Skan basic_block dest = succ->dest; 636169689Skan tree label; 637169689Skan basic_block dombb, domdest, dom; 638169689Skan 639169689Skan /* We check for infinite loops already in tree_forwarder_block_p. 640169689Skan However it may happen that the infinite loop is created 641169689Skan afterwards due to removal of forwarders. */ 642169689Skan if (dest == bb) 643169689Skan return; 644169689Skan 645169689Skan /* If the destination block consists of a nonlocal label, do not 646169689Skan merge it. */ 647169689Skan label = first_stmt (dest); 648169689Skan if (label 649169689Skan && TREE_CODE (label) == LABEL_EXPR 650169689Skan && DECL_NONLOCAL (LABEL_EXPR_LABEL (label))) 651169689Skan return; 652169689Skan 653169689Skan /* Redirect each incoming edge to BB to DEST. */ 654169689Skan while (EDGE_COUNT (bb->preds) > 0) 655169689Skan { 656169689Skan edge e = EDGE_PRED (bb, 0), s; 657169689Skan tree phi; 658169689Skan 659169689Skan s = find_edge (e->src, dest); 660169689Skan if (s) 661169689Skan { 662169689Skan /* We already have an edge S from E->src to DEST. If S and 663169689Skan E->dest's sole successor edge have the same PHI arguments 664169689Skan at DEST, redirect S to DEST. */ 665169689Skan if (phi_alternatives_equal (dest, s, succ)) 666169689Skan { 667169689Skan e = redirect_edge_and_branch (e, dest); 668169689Skan PENDING_STMT (e) = NULL_TREE; 669169689Skan continue; 670169689Skan } 671169689Skan 672169689Skan /* PHI arguments are different. Create a forwarder block by 673169689Skan splitting E so that we can merge PHI arguments on E to 674169689Skan DEST. */ 675169689Skan e = single_succ_edge (split_edge (e)); 676169689Skan } 677169689Skan 678169689Skan s = redirect_edge_and_branch (e, dest); 679169689Skan 680169689Skan /* redirect_edge_and_branch must not create a new edge. */ 681169689Skan gcc_assert (s == e); 682169689Skan 683169689Skan /* Add to the PHI nodes at DEST each PHI argument removed at the 684169689Skan destination of E. */ 685169689Skan for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) 686169689Skan { 687169689Skan tree def = PHI_ARG_DEF (phi, succ->dest_idx); 688169689Skan 689169689Skan if (TREE_CODE (def) == SSA_NAME) 690169689Skan { 691169689Skan tree var; 692169689Skan 693169689Skan /* If DEF is one of the results of PHI nodes removed during 694169689Skan redirection, replace it with the PHI argument that used 695169689Skan to be on E. */ 696169689Skan for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var)) 697169689Skan { 698169689Skan tree old_arg = TREE_PURPOSE (var); 699169689Skan tree new_arg = TREE_VALUE (var); 700169689Skan 701169689Skan if (def == old_arg) 702169689Skan { 703169689Skan def = new_arg; 704169689Skan break; 705169689Skan } 706169689Skan } 707169689Skan } 708169689Skan 709169689Skan add_phi_arg (phi, def, s); 710169689Skan } 711169689Skan 712169689Skan PENDING_STMT (e) = NULL; 713169689Skan } 714169689Skan 715169689Skan /* Update the dominators. */ 716169689Skan dombb = get_immediate_dominator (CDI_DOMINATORS, bb); 717169689Skan domdest = get_immediate_dominator (CDI_DOMINATORS, dest); 718169689Skan if (domdest == bb) 719169689Skan { 720169689Skan /* Shortcut to avoid calling (relatively expensive) 721169689Skan nearest_common_dominator unless necessary. */ 722169689Skan dom = dombb; 723169689Skan } 724169689Skan else 725169689Skan dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb); 726169689Skan 727169689Skan set_immediate_dominator (CDI_DOMINATORS, dest, dom); 728169689Skan 729169689Skan /* Remove BB since all of BB's incoming edges have been redirected 730169689Skan to DEST. */ 731169689Skan delete_basic_block (bb); 732169689Skan} 733169689Skan 734169689Skan/* This pass merges PHI nodes if one feeds into another. For example, 735169689Skan suppose we have the following: 736169689Skan 737169689Skan goto <bb 9> (<L9>); 738169689Skan 739169689Skan<L8>:; 740169689Skan tem_17 = foo (); 741169689Skan 742169689Skan # tem_6 = PHI <tem_17(8), tem_23(7)>; 743169689Skan<L9>:; 744169689Skan 745169689Skan # tem_3 = PHI <tem_6(9), tem_2(5)>; 746169689Skan<L10>:; 747169689Skan 748169689Skan Then we merge the first PHI node into the second one like so: 749169689Skan 750169689Skan goto <bb 9> (<L10>); 751169689Skan 752169689Skan<L8>:; 753169689Skan tem_17 = foo (); 754169689Skan 755169689Skan # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>; 756169689Skan<L10>:; 757169689Skan*/ 758169689Skan 759169689Skanstatic unsigned int 760169689Skanmerge_phi_nodes (void) 761169689Skan{ 762169689Skan basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks); 763169689Skan basic_block *current = worklist; 764169689Skan basic_block bb; 765169689Skan 766169689Skan calculate_dominance_info (CDI_DOMINATORS); 767169689Skan 768169689Skan /* Find all PHI nodes that we may be able to merge. */ 769169689Skan FOR_EACH_BB (bb) 770169689Skan { 771169689Skan basic_block dest; 772169689Skan 773169689Skan /* Look for a forwarder block with PHI nodes. */ 774169689Skan if (!tree_forwarder_block_p (bb, true)) 775169689Skan continue; 776169689Skan 777169689Skan dest = single_succ (bb); 778169689Skan 779169689Skan /* We have to feed into another basic block with PHI 780169689Skan nodes. */ 781169689Skan if (!phi_nodes (dest) 782169689Skan /* We don't want to deal with a basic block with 783169689Skan abnormal edges. */ 784169689Skan || has_abnormal_incoming_edge_p (bb)) 785169689Skan continue; 786169689Skan 787169689Skan if (!dominated_by_p (CDI_DOMINATORS, dest, bb)) 788169689Skan { 789169689Skan /* If BB does not dominate DEST, then the PHI nodes at 790169689Skan DEST must be the only users of the results of the PHI 791169689Skan nodes at BB. */ 792169689Skan *current++ = bb; 793169689Skan } 794169689Skan else 795169689Skan { 796169689Skan tree phi; 797169689Skan unsigned int dest_idx = single_succ_edge (bb)->dest_idx; 798169689Skan 799169689Skan /* BB dominates DEST. There may be many users of the PHI 800169689Skan nodes in BB. However, there is still a trivial case we 801169689Skan can handle. If the result of every PHI in BB is used 802169689Skan only by a PHI in DEST, then we can trivially merge the 803169689Skan PHI nodes from BB into DEST. */ 804169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 805169689Skan { 806169689Skan tree result = PHI_RESULT (phi); 807169689Skan use_operand_p imm_use; 808169689Skan tree use_stmt; 809169689Skan 810169689Skan /* If the PHI's result is never used, then we can just 811169689Skan ignore it. */ 812169689Skan if (has_zero_uses (result)) 813169689Skan continue; 814169689Skan 815169689Skan /* Get the single use of the result of this PHI node. */ 816169689Skan if (!single_imm_use (result, &imm_use, &use_stmt) 817169689Skan || TREE_CODE (use_stmt) != PHI_NODE 818169689Skan || bb_for_stmt (use_stmt) != dest 819169689Skan || PHI_ARG_DEF (use_stmt, dest_idx) != result) 820169689Skan break; 821169689Skan } 822169689Skan 823169689Skan /* If the loop above iterated through all the PHI nodes 824169689Skan in BB, then we can merge the PHIs from BB into DEST. */ 825169689Skan if (!phi) 826169689Skan *current++ = bb; 827169689Skan } 828169689Skan } 829169689Skan 830169689Skan /* Now let's drain WORKLIST. */ 831169689Skan while (current != worklist) 832169689Skan { 833169689Skan bb = *--current; 834169689Skan remove_forwarder_block_with_phi (bb); 835169689Skan } 836169689Skan 837169689Skan free (worklist); 838169689Skan return 0; 839169689Skan} 840169689Skan 841169689Skanstatic bool 842169689Skangate_merge_phi (void) 843169689Skan{ 844169689Skan return 1; 845169689Skan} 846169689Skan 847169689Skanstruct tree_opt_pass pass_merge_phi = { 848169689Skan "mergephi", /* name */ 849169689Skan gate_merge_phi, /* gate */ 850169689Skan merge_phi_nodes, /* execute */ 851169689Skan NULL, /* sub */ 852169689Skan NULL, /* next */ 853169689Skan 0, /* static_pass_number */ 854169689Skan TV_TREE_MERGE_PHI, /* tv_id */ 855169689Skan PROP_cfg | PROP_ssa, /* properties_required */ 856169689Skan 0, /* properties_provided */ 857169689Skan 0, /* properties_destroyed */ 858169689Skan 0, /* todo_flags_start */ 859169689Skan TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */ 860169689Skan | TODO_verify_ssa, 861169689Skan 0 /* letter */ 862169689Skan}; 863