tree-cfgcleanup.c revision 169689
1139825Simp/* CFG cleanup for trees. 277957Sbenno Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 377957Sbenno Free Software Foundation, Inc. 477957Sbenno 577957SbennoThis file is part of GCC. 677957Sbenno 777957SbennoGCC is free software; you can redistribute it and/or modify 877957Sbennoit under the terms of the GNU General Public License as published by 977957Sbennothe Free Software Foundation; either version 2, or (at your option) 1077957Sbennoany later version. 1177957Sbenno 1277957SbennoGCC is distributed in the hope that it will be useful, 1377957Sbennobut WITHOUT ANY WARRANTY; without even the implied warranty of 1477957SbennoMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1577957SbennoGNU General Public License for more details. 1677957Sbenno 1777957SbennoYou should have received a copy of the GNU General Public License 1877957Sbennoalong with GCC; see the file COPYING. If not, write to 1977957Sbennothe Free Software Foundation, 51 Franklin Street, Fifth Floor, 2077957SbennoBoston, MA 02110-1301, USA. */ 2177957Sbenno 2277957Sbenno#include "config.h" 2377957Sbenno#include "system.h" 2477957Sbenno#include "coretypes.h" 2577957Sbenno#include "tm.h" 2677957Sbenno#include "tree.h" 2777957Sbenno#include "rtl.h" 2877957Sbenno#include "tm_p.h" 2977957Sbenno#include "hard-reg-set.h" 3077957Sbenno#include "basic-block.h" 3177957Sbenno#include "output.h" 3277957Sbenno#include "toplev.h" 3377957Sbenno#include "flags.h" 34113038Sobrien#include "function.h" 35113038Sobrien#include "expr.h" 3677957Sbenno#include "ggc.h" 3777957Sbenno#include "langhooks.h" 3877957Sbenno#include "diagnostic.h" 3977957Sbenno#include "tree-flow.h" 4077957Sbenno#include "timevar.h" 4177957Sbenno#include "tree-dump.h" 4277957Sbenno#include "tree-pass.h" 4377957Sbenno#include "toplev.h" 4477957Sbenno#include "except.h" 4577957Sbenno#include "cfgloop.h" 4699665Sbenno#include "cfglayout.h" 4799665Sbenno#include "hashtab.h" 4877957Sbenno#include "tree-ssa-propagate.h" 4977957Sbenno#include "tree-scalar-evolution.h" 5090643Sbenno 5190643Sbenno/* Remove any fallthru edge from EV. Return true if an edge was removed. */ 5290643Sbenno 5390643Sbennostatic bool 54160714Smarcelremove_fallthru_edge (VEC(edge,gc) *ev) 55160714Smarcel{ 5677957Sbenno edge_iterator ei; 5799030Sbenno edge e; 5899665Sbenno 5977957Sbenno FOR_EACH_EDGE (e, ei, ev) 6077957Sbenno if ((e->flags & EDGE_FALLTHRU) != 0) 6177957Sbenno { 62123370Sgrehan remove_edge (e); 6377957Sbenno return true; 64151891Sgrehan } 65151891Sgrehan return false; 6690643Sbenno} 6777957Sbenno 6877957Sbenno/* Disconnect an unreachable block in the control expression starting 6977957Sbenno at block BB. */ 70151891Sgrehan 71151891Sgrehanstatic bool 72151891Sgrehancleanup_control_expr_graph (basic_block bb, block_stmt_iterator bsi) 73151891Sgrehan{ 74151891Sgrehan edge taken_edge; 75151891Sgrehan bool retval = false; 76151891Sgrehan tree expr = bsi_stmt (bsi), val; 77151891Sgrehan 78151891Sgrehan if (!single_succ_p (bb)) 79151891Sgrehan { 80151891Sgrehan edge e; 81151891Sgrehan edge_iterator ei; 82151891Sgrehan bool warned; 83151891Sgrehan 84151891Sgrehan fold_defer_overflow_warnings (); 85151891Sgrehan 86151891Sgrehan switch (TREE_CODE (expr)) 87151891Sgrehan { 88151891Sgrehan case COND_EXPR: 89151891Sgrehan val = fold (COND_EXPR_COND (expr)); 90151891Sgrehan break; 91151891Sgrehan 92151891Sgrehan case SWITCH_EXPR: 93151891Sgrehan val = fold (SWITCH_COND (expr)); 94151891Sgrehan if (TREE_CODE (val) != INTEGER_CST) 95151891Sgrehan { 96151891Sgrehan fold_undefer_and_ignore_overflow_warnings (); 97151891Sgrehan return false; 98151891Sgrehan } 99151891Sgrehan break; 100151891Sgrehan 101151891Sgrehan default: 102151891Sgrehan gcc_unreachable (); 103151891Sgrehan } 104151891Sgrehan 105151891Sgrehan taken_edge = find_taken_edge (bb, val); 106151891Sgrehan if (!taken_edge) 107123370Sgrehan { 108123370Sgrehan fold_undefer_and_ignore_overflow_warnings (); 109123370Sgrehan return false; 110123370Sgrehan } 111123370Sgrehan 112123370Sgrehan /* Remove all the edges except the one that is always executed. */ 113123370Sgrehan warned = false; 114123370Sgrehan for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 115123370Sgrehan { 116123370Sgrehan if (e != taken_edge) 117123370Sgrehan { 118123370Sgrehan if (!warned) 119123370Sgrehan { 120123370Sgrehan fold_undefer_overflow_warnings 121123370Sgrehan (true, expr, WARN_STRICT_OVERFLOW_CONDITIONAL); 122123370Sgrehan warned = true; 123123370Sgrehan } 124123370Sgrehan 125123370Sgrehan taken_edge->probability += e->probability; 126123370Sgrehan taken_edge->count += e->count; 127123370Sgrehan remove_edge (e); 128123370Sgrehan retval = true; 129123370Sgrehan } 13077957Sbenno else 13177957Sbenno ei_next (&ei); 13277957Sbenno } 13377957Sbenno if (!warned) 13477957Sbenno fold_undefer_and_ignore_overflow_warnings (); 13577957Sbenno if (taken_edge->probability > REG_BR_PROB_BASE) 13677957Sbenno taken_edge->probability = REG_BR_PROB_BASE; 13797346Sbenno } 13897346Sbenno else 13977957Sbenno taken_edge = single_succ_edge (bb); 14097346Sbenno 141123370Sgrehan bsi_remove (&bsi, true); 142123370Sgrehan taken_edge->flags = EDGE_FALLTHRU; 143123370Sgrehan 14477957Sbenno /* We removed some paths from the cfg. */ 14577957Sbenno free_dominance_info (CDI_DOMINATORS); 14677957Sbenno 14777957Sbenno return retval; 14877957Sbenno} 14997346Sbenno 15097346Sbenno/* A list of all the noreturn calls passed to modify_stmt. 15177957Sbenno cleanup_control_flow uses it to detect cases where a mid-block 15297346Sbenno indirect call has been turned into a noreturn call. When this 15397346Sbenno happens, all the instructions after the call are no longer 15477957Sbenno reachable and must be deleted as dead. */ 15577957Sbenno 15677957SbennoVEC(tree,gc) *modified_noreturn_calls; 15797346Sbenno 158123370Sgrehan/* Try to remove superfluous control structures. */ 159123370Sgrehan 160123370Sgrehanstatic bool 161123370Sgrehancleanup_control_flow (void) 162123370Sgrehan{ 163123370Sgrehan basic_block bb; 164123370Sgrehan block_stmt_iterator bsi; 165123370Sgrehan bool retval = false; 166123370Sgrehan tree stmt; 167123370Sgrehan 168123370Sgrehan /* Detect cases where a mid-block call is now known not to return. */ 169123370Sgrehan while (VEC_length (tree, modified_noreturn_calls)) 170123370Sgrehan { 171123370Sgrehan stmt = VEC_pop (tree, modified_noreturn_calls); 172123370Sgrehan bb = bb_for_stmt (stmt); 173123370Sgrehan if (bb != NULL && last_stmt (bb) != stmt && noreturn_call_p (stmt)) 174123370Sgrehan split_block (bb, stmt); 175123370Sgrehan } 176123370Sgrehan 177123370Sgrehan FOR_EACH_BB (bb) 178123370Sgrehan { 179123370Sgrehan bsi = bsi_last (bb); 180123370Sgrehan 181123370Sgrehan /* If the last statement of the block could throw and now cannot, 182123370Sgrehan we need to prune cfg. */ 183123370Sgrehan retval |= tree_purge_dead_eh_edges (bb); 184123370Sgrehan 185123370Sgrehan if (bsi_end_p (bsi)) 186123370Sgrehan continue; 187123370Sgrehan 188123370Sgrehan stmt = bsi_stmt (bsi); 189123370Sgrehan 190123370Sgrehan if (TREE_CODE (stmt) == COND_EXPR 191123370Sgrehan || TREE_CODE (stmt) == SWITCH_EXPR) 19277957Sbenno retval |= cleanup_control_expr_graph (bb, bsi); 19377957Sbenno /* If we had a computed goto which has a compile-time determinable 19477957Sbenno destination, then we can eliminate the goto. */ 19577957Sbenno else if (TREE_CODE (stmt) == GOTO_EXPR 19677957Sbenno && TREE_CODE (GOTO_DESTINATION (stmt)) == ADDR_EXPR 19777957Sbenno && (TREE_CODE (TREE_OPERAND (GOTO_DESTINATION (stmt), 0)) 19877957Sbenno == LABEL_DECL)) 19977957Sbenno { 20077957Sbenno edge e; 20177957Sbenno tree label; 20277957Sbenno edge_iterator ei; 20377957Sbenno basic_block target_block; 20477957Sbenno bool removed_edge = false; 20577957Sbenno 20690643Sbenno /* First look at all the outgoing edges. Delete any outgoing 20799030Sbenno edges which do not go to the right block. For the one 20877957Sbenno edge which goes to the right block, fix up its flags. */ 20990643Sbenno label = TREE_OPERAND (GOTO_DESTINATION (stmt), 0); 21090643Sbenno target_block = label_to_block (label); 21177957Sbenno for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 21277957Sbenno { 21377957Sbenno if (e->dest != target_block) 21477957Sbenno { 215151891Sgrehan removed_edge = true; 21677957Sbenno remove_edge (e); 21777957Sbenno } 218151891Sgrehan else 219151891Sgrehan { 22099030Sbenno /* Turn off the EDGE_ABNORMAL flag. */ 22199030Sbenno e->flags &= ~EDGE_ABNORMAL; 222133862Smarius 22399030Sbenno /* And set EDGE_FALLTHRU. */ 22499030Sbenno e->flags |= EDGE_FALLTHRU; 22599030Sbenno ei_next (&ei); 22699030Sbenno } 22799030Sbenno } 228103602Sgrehan 229103602Sgrehan /* If we removed one or more edges, then we will need to fix the 230103602Sgrehan dominators. It may be possible to incrementally update them. */ 231103602Sgrehan if (removed_edge) 232103602Sgrehan free_dominance_info (CDI_DOMINATORS); 233103602Sgrehan 23499030Sbenno /* Remove the GOTO_EXPR as it is not needed. The CFG has all the 23599030Sbenno relevant information we need. */ 23677957Sbenno bsi_remove (&bsi, true); 237151891Sgrehan retval = true; 238151891Sgrehan } 23999030Sbenno 24099030Sbenno /* Check for indirect calls that have been turned into 24199030Sbenno noreturn calls. */ 24299030Sbenno else if (noreturn_call_p (stmt) && remove_fallthru_edge (bb->succs)) 24399030Sbenno { 24499030Sbenno free_dominance_info (CDI_DOMINATORS); 24599030Sbenno retval = true; 24699030Sbenno } 24799030Sbenno } 24899030Sbenno return retval; 24999030Sbenno} 25099030Sbenno 251151891Sgrehan/* Return true if basic block BB does nothing except pass control 252151891Sgrehan flow to another block and that we can safely insert a label at 25377957Sbenno the start of the successor block. 25477957Sbenno 25577957Sbenno As a precondition, we require that BB be not equal to 25677957Sbenno ENTRY_BLOCK_PTR. */ 25777957Sbenno 25877957Sbennostatic bool 25977957Sbennotree_forwarder_block_p (basic_block bb, bool phi_wanted) 26077957Sbenno{ 26177957Sbenno block_stmt_iterator bsi; 26277957Sbenno edge_iterator ei; 263123353Sgallatin edge e, succ; 264123353Sgallatin basic_block dest; 265123353Sgallatin 266123353Sgallatin /* BB must have a single outgoing edge. */ 267123353Sgallatin if (single_succ_p (bb) != 1 268123353Sgallatin /* If PHI_WANTED is false, BB must not have any PHI nodes. 269123353Sgallatin Otherwise, BB must have PHI nodes. */ 270123353Sgallatin || (phi_nodes (bb) != NULL_TREE) != phi_wanted 271123353Sgallatin /* BB may not be a predecessor of EXIT_BLOCK_PTR. */ 272123353Sgallatin || single_succ (bb) == EXIT_BLOCK_PTR 273123353Sgallatin /* Nor should this be an infinite loop. */ 274123353Sgallatin || single_succ (bb) == bb 275123353Sgallatin /* BB may not have an abnormal outgoing edge. */ 276123353Sgallatin || (single_succ_edge (bb)->flags & EDGE_ABNORMAL)) 277123353Sgallatin return false; 278123353Sgallatin 279123353Sgallatin#if ENABLE_CHECKING 280123353Sgallatin gcc_assert (bb != ENTRY_BLOCK_PTR); 28199665Sbenno#endif 28299665Sbenno 28399665Sbenno /* Now walk through the statements backward. We can ignore labels, 28499665Sbenno anything else means this is not a forwarder block. */ 28599665Sbenno for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 28699665Sbenno { 28799665Sbenno tree stmt = bsi_stmt (bsi); 288133855Sssouhlal 289160714Smarcel switch (TREE_CODE (stmt)) 290160714Smarcel { 291160714Smarcel case LABEL_EXPR: 292160714Smarcel if (DECL_NONLOCAL (LABEL_EXPR_LABEL (stmt))) 293160714Smarcel return false; 294160714Smarcel break; 295160714Smarcel 296160714Smarcel default: 297133855Sssouhlal return false; 298160714Smarcel } 299160714Smarcel } 300160714Smarcel 301160714Smarcel if (find_edge (ENTRY_BLOCK_PTR, bb)) 302160714Smarcel return false; 303160714Smarcel 304160714Smarcel if (current_loops) 305160714Smarcel { 306133855Sssouhlal basic_block dest; 307133855Sssouhlal /* Protect loop latches, headers and preheaders. */ 308133855Sssouhlal if (bb->loop_father->header == bb) 309133855Sssouhlal return false; 310133855Sssouhlal dest = EDGE_SUCC (bb, 0)->dest; 311133855Sssouhlal 312133855Sssouhlal if (dest->loop_father->header == dest) 313133855Sssouhlal return false; 314133855Sssouhlal } 315133855Sssouhlal 316133855Sssouhlal /* If we have an EH edge leaving this block, make sure that the 317 destination of this block has only one predecessor. This ensures 318 that we don't get into the situation where we try to remove two 319 forwarders that go to the same basic block but are handlers for 320 different EH regions. */ 321 succ = single_succ_edge (bb); 322 dest = succ->dest; 323 FOR_EACH_EDGE (e, ei, bb->preds) 324 { 325 if (e->flags & EDGE_EH) 326 { 327 if (!single_pred_p (dest)) 328 return false; 329 } 330 } 331 332 return true; 333} 334 335/* Return true if BB has at least one abnormal incoming edge. */ 336 337static inline bool 338has_abnormal_incoming_edge_p (basic_block bb) 339{ 340 edge e; 341 edge_iterator ei; 342 343 FOR_EACH_EDGE (e, ei, bb->preds) 344 if (e->flags & EDGE_ABNORMAL) 345 return true; 346 347 return false; 348} 349 350/* If all the PHI nodes in DEST have alternatives for E1 and E2 and 351 those alternatives are equal in each of the PHI nodes, then return 352 true, else return false. */ 353 354static bool 355phi_alternatives_equal (basic_block dest, edge e1, edge e2) 356{ 357 int n1 = e1->dest_idx; 358 int n2 = e2->dest_idx; 359 tree phi; 360 361 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) 362 { 363 tree val1 = PHI_ARG_DEF (phi, n1); 364 tree val2 = PHI_ARG_DEF (phi, n2); 365 366 gcc_assert (val1 != NULL_TREE); 367 gcc_assert (val2 != NULL_TREE); 368 369 if (!operand_equal_for_phi_arg_p (val1, val2)) 370 return false; 371 } 372 373 return true; 374} 375 376/* Removes forwarder block BB. Returns false if this failed. If a new 377 forwarder block is created due to redirection of edges, it is 378 stored to worklist. */ 379 380static bool 381remove_forwarder_block (basic_block bb, basic_block **worklist) 382{ 383 edge succ = single_succ_edge (bb), e, s; 384 basic_block dest = succ->dest; 385 tree label; 386 tree phi; 387 edge_iterator ei; 388 block_stmt_iterator bsi, bsi_to; 389 bool seen_abnormal_edge = false; 390 391 /* We check for infinite loops already in tree_forwarder_block_p. 392 However it may happen that the infinite loop is created 393 afterwards due to removal of forwarders. */ 394 if (dest == bb) 395 return false; 396 397 /* If the destination block consists of a nonlocal label, do not merge 398 it. */ 399 label = first_stmt (dest); 400 if (label 401 && TREE_CODE (label) == LABEL_EXPR 402 && DECL_NONLOCAL (LABEL_EXPR_LABEL (label))) 403 return false; 404 405 /* If there is an abnormal edge to basic block BB, but not into 406 dest, problems might occur during removal of the phi node at out 407 of ssa due to overlapping live ranges of registers. 408 409 If there is an abnormal edge in DEST, the problems would occur 410 anyway since cleanup_dead_labels would then merge the labels for 411 two different eh regions, and rest of exception handling code 412 does not like it. 413 414 So if there is an abnormal edge to BB, proceed only if there is 415 no abnormal edge to DEST and there are no phi nodes in DEST. */ 416 if (has_abnormal_incoming_edge_p (bb)) 417 { 418 seen_abnormal_edge = true; 419 420 if (has_abnormal_incoming_edge_p (dest) 421 || phi_nodes (dest) != NULL_TREE) 422 return false; 423 } 424 425 /* If there are phi nodes in DEST, and some of the blocks that are 426 predecessors of BB are also predecessors of DEST, check that the 427 phi node arguments match. */ 428 if (phi_nodes (dest)) 429 { 430 FOR_EACH_EDGE (e, ei, bb->preds) 431 { 432 s = find_edge (e->src, dest); 433 if (!s) 434 continue; 435 436 if (!phi_alternatives_equal (dest, succ, s)) 437 return false; 438 } 439 } 440 441 /* Redirect the edges. */ 442 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 443 { 444 if (e->flags & EDGE_ABNORMAL) 445 { 446 /* If there is an abnormal edge, redirect it anyway, and 447 move the labels to the new block to make it legal. */ 448 s = redirect_edge_succ_nodup (e, dest); 449 } 450 else 451 s = redirect_edge_and_branch (e, dest); 452 453 if (s == e) 454 { 455 /* Create arguments for the phi nodes, since the edge was not 456 here before. */ 457 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) 458 add_phi_arg (phi, PHI_ARG_DEF (phi, succ->dest_idx), s); 459 } 460 else 461 { 462 /* The source basic block might become a forwarder. We know 463 that it was not a forwarder before, since it used to have 464 at least two outgoing edges, so we may just add it to 465 worklist. */ 466 if (tree_forwarder_block_p (s->src, false)) 467 *(*worklist)++ = s->src; 468 } 469 } 470 471 if (seen_abnormal_edge) 472 { 473 /* Move the labels to the new block, so that the redirection of 474 the abnormal edges works. */ 475 476 bsi_to = bsi_start (dest); 477 for (bsi = bsi_start (bb); !bsi_end_p (bsi); ) 478 { 479 label = bsi_stmt (bsi); 480 gcc_assert (TREE_CODE (label) == LABEL_EXPR); 481 bsi_remove (&bsi, false); 482 bsi_insert_before (&bsi_to, label, BSI_CONTINUE_LINKING); 483 } 484 } 485 486 /* Update the dominators. */ 487 if (dom_info_available_p (CDI_DOMINATORS)) 488 { 489 basic_block dom, dombb, domdest; 490 491 dombb = get_immediate_dominator (CDI_DOMINATORS, bb); 492 domdest = get_immediate_dominator (CDI_DOMINATORS, dest); 493 if (domdest == bb) 494 { 495 /* Shortcut to avoid calling (relatively expensive) 496 nearest_common_dominator unless necessary. */ 497 dom = dombb; 498 } 499 else 500 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb); 501 502 set_immediate_dominator (CDI_DOMINATORS, dest, dom); 503 } 504 505 /* And kill the forwarder block. */ 506 delete_basic_block (bb); 507 508 return true; 509} 510 511/* Removes forwarder blocks. */ 512 513static bool 514cleanup_forwarder_blocks (void) 515{ 516 basic_block bb; 517 bool changed = false; 518 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks); 519 basic_block *current = worklist; 520 521 FOR_EACH_BB (bb) 522 { 523 if (tree_forwarder_block_p (bb, false)) 524 *current++ = bb; 525 } 526 527 while (current != worklist) 528 { 529 bb = *--current; 530 changed |= remove_forwarder_block (bb, ¤t); 531 } 532 533 free (worklist); 534 return changed; 535} 536 537/* Do one round of CFG cleanup. */ 538 539static bool 540cleanup_tree_cfg_1 (void) 541{ 542 bool retval; 543 544 retval = cleanup_control_flow (); 545 retval |= delete_unreachable_blocks (); 546 547 /* Forwarder blocks can carry line number information which is 548 useful when debugging, so we only clean them up when 549 optimizing. */ 550 551 if (optimize > 0) 552 { 553 /* cleanup_forwarder_blocks can redirect edges out of 554 SWITCH_EXPRs, which can get expensive. So we want to enable 555 recording of edge to CASE_LABEL_EXPR mappings around the call 556 to cleanup_forwarder_blocks. */ 557 start_recording_case_labels (); 558 retval |= cleanup_forwarder_blocks (); 559 end_recording_case_labels (); 560 } 561 562 /* Merging the blocks may create new opportunities for folding 563 conditional branches (due to the elimination of single-valued PHI 564 nodes). */ 565 retval |= merge_seq_blocks (); 566 567 return retval; 568} 569 570 571/* Remove unreachable blocks and other miscellaneous clean up work. 572 Return true if the flowgraph was modified, false otherwise. */ 573 574bool 575cleanup_tree_cfg (void) 576{ 577 bool retval, changed; 578 579 timevar_push (TV_TREE_CLEANUP_CFG); 580 581 /* Iterate until there are no more cleanups left to do. If any 582 iteration changed the flowgraph, set CHANGED to true. */ 583 changed = false; 584 do 585 { 586 retval = cleanup_tree_cfg_1 (); 587 changed |= retval; 588 } 589 while (retval); 590 591 compact_blocks (); 592 593#ifdef ENABLE_CHECKING 594 verify_flow_info (); 595#endif 596 597 timevar_pop (TV_TREE_CLEANUP_CFG); 598 599 return changed; 600} 601 602/* Cleanup cfg and repair loop structures. */ 603 604void 605cleanup_tree_cfg_loop (void) 606{ 607 bool changed = cleanup_tree_cfg (); 608 609 if (changed) 610 { 611 bitmap changed_bbs = BITMAP_ALLOC (NULL); 612 fix_loop_structure (current_loops, changed_bbs); 613 calculate_dominance_info (CDI_DOMINATORS); 614 615 /* This usually does nothing. But sometimes parts of cfg that originally 616 were inside a loop get out of it due to edge removal (since they 617 become unreachable by back edges from latch). */ 618 rewrite_into_loop_closed_ssa (changed_bbs, TODO_update_ssa); 619 620 BITMAP_FREE (changed_bbs); 621 622#ifdef ENABLE_CHECKING 623 verify_loop_structure (current_loops); 624#endif 625 scev_reset (); 626 } 627} 628 629/* Merge the PHI nodes at BB into those at BB's sole successor. */ 630 631static void 632remove_forwarder_block_with_phi (basic_block bb) 633{ 634 edge succ = single_succ_edge (bb); 635 basic_block dest = succ->dest; 636 tree label; 637 basic_block dombb, domdest, dom; 638 639 /* We check for infinite loops already in tree_forwarder_block_p. 640 However it may happen that the infinite loop is created 641 afterwards due to removal of forwarders. */ 642 if (dest == bb) 643 return; 644 645 /* If the destination block consists of a nonlocal label, do not 646 merge it. */ 647 label = first_stmt (dest); 648 if (label 649 && TREE_CODE (label) == LABEL_EXPR 650 && DECL_NONLOCAL (LABEL_EXPR_LABEL (label))) 651 return; 652 653 /* Redirect each incoming edge to BB to DEST. */ 654 while (EDGE_COUNT (bb->preds) > 0) 655 { 656 edge e = EDGE_PRED (bb, 0), s; 657 tree phi; 658 659 s = find_edge (e->src, dest); 660 if (s) 661 { 662 /* We already have an edge S from E->src to DEST. If S and 663 E->dest's sole successor edge have the same PHI arguments 664 at DEST, redirect S to DEST. */ 665 if (phi_alternatives_equal (dest, s, succ)) 666 { 667 e = redirect_edge_and_branch (e, dest); 668 PENDING_STMT (e) = NULL_TREE; 669 continue; 670 } 671 672 /* PHI arguments are different. Create a forwarder block by 673 splitting E so that we can merge PHI arguments on E to 674 DEST. */ 675 e = single_succ_edge (split_edge (e)); 676 } 677 678 s = redirect_edge_and_branch (e, dest); 679 680 /* redirect_edge_and_branch must not create a new edge. */ 681 gcc_assert (s == e); 682 683 /* Add to the PHI nodes at DEST each PHI argument removed at the 684 destination of E. */ 685 for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi)) 686 { 687 tree def = PHI_ARG_DEF (phi, succ->dest_idx); 688 689 if (TREE_CODE (def) == SSA_NAME) 690 { 691 tree var; 692 693 /* If DEF is one of the results of PHI nodes removed during 694 redirection, replace it with the PHI argument that used 695 to be on E. */ 696 for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var)) 697 { 698 tree old_arg = TREE_PURPOSE (var); 699 tree new_arg = TREE_VALUE (var); 700 701 if (def == old_arg) 702 { 703 def = new_arg; 704 break; 705 } 706 } 707 } 708 709 add_phi_arg (phi, def, s); 710 } 711 712 PENDING_STMT (e) = NULL; 713 } 714 715 /* Update the dominators. */ 716 dombb = get_immediate_dominator (CDI_DOMINATORS, bb); 717 domdest = get_immediate_dominator (CDI_DOMINATORS, dest); 718 if (domdest == bb) 719 { 720 /* Shortcut to avoid calling (relatively expensive) 721 nearest_common_dominator unless necessary. */ 722 dom = dombb; 723 } 724 else 725 dom = nearest_common_dominator (CDI_DOMINATORS, domdest, dombb); 726 727 set_immediate_dominator (CDI_DOMINATORS, dest, dom); 728 729 /* Remove BB since all of BB's incoming edges have been redirected 730 to DEST. */ 731 delete_basic_block (bb); 732} 733 734/* This pass merges PHI nodes if one feeds into another. For example, 735 suppose we have the following: 736 737 goto <bb 9> (<L9>); 738 739<L8>:; 740 tem_17 = foo (); 741 742 # tem_6 = PHI <tem_17(8), tem_23(7)>; 743<L9>:; 744 745 # tem_3 = PHI <tem_6(9), tem_2(5)>; 746<L10>:; 747 748 Then we merge the first PHI node into the second one like so: 749 750 goto <bb 9> (<L10>); 751 752<L8>:; 753 tem_17 = foo (); 754 755 # tem_3 = PHI <tem_23(7), tem_2(5), tem_17(8)>; 756<L10>:; 757*/ 758 759static unsigned int 760merge_phi_nodes (void) 761{ 762 basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks); 763 basic_block *current = worklist; 764 basic_block bb; 765 766 calculate_dominance_info (CDI_DOMINATORS); 767 768 /* Find all PHI nodes that we may be able to merge. */ 769 FOR_EACH_BB (bb) 770 { 771 basic_block dest; 772 773 /* Look for a forwarder block with PHI nodes. */ 774 if (!tree_forwarder_block_p (bb, true)) 775 continue; 776 777 dest = single_succ (bb); 778 779 /* We have to feed into another basic block with PHI 780 nodes. */ 781 if (!phi_nodes (dest) 782 /* We don't want to deal with a basic block with 783 abnormal edges. */ 784 || has_abnormal_incoming_edge_p (bb)) 785 continue; 786 787 if (!dominated_by_p (CDI_DOMINATORS, dest, bb)) 788 { 789 /* If BB does not dominate DEST, then the PHI nodes at 790 DEST must be the only users of the results of the PHI 791 nodes at BB. */ 792 *current++ = bb; 793 } 794 else 795 { 796 tree phi; 797 unsigned int dest_idx = single_succ_edge (bb)->dest_idx; 798 799 /* BB dominates DEST. There may be many users of the PHI 800 nodes in BB. However, there is still a trivial case we 801 can handle. If the result of every PHI in BB is used 802 only by a PHI in DEST, then we can trivially merge the 803 PHI nodes from BB into DEST. */ 804 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 805 { 806 tree result = PHI_RESULT (phi); 807 use_operand_p imm_use; 808 tree use_stmt; 809 810 /* If the PHI's result is never used, then we can just 811 ignore it. */ 812 if (has_zero_uses (result)) 813 continue; 814 815 /* Get the single use of the result of this PHI node. */ 816 if (!single_imm_use (result, &imm_use, &use_stmt) 817 || TREE_CODE (use_stmt) != PHI_NODE 818 || bb_for_stmt (use_stmt) != dest 819 || PHI_ARG_DEF (use_stmt, dest_idx) != result) 820 break; 821 } 822 823 /* If the loop above iterated through all the PHI nodes 824 in BB, then we can merge the PHIs from BB into DEST. */ 825 if (!phi) 826 *current++ = bb; 827 } 828 } 829 830 /* Now let's drain WORKLIST. */ 831 while (current != worklist) 832 { 833 bb = *--current; 834 remove_forwarder_block_with_phi (bb); 835 } 836 837 free (worklist); 838 return 0; 839} 840 841static bool 842gate_merge_phi (void) 843{ 844 return 1; 845} 846 847struct tree_opt_pass pass_merge_phi = { 848 "mergephi", /* name */ 849 gate_merge_phi, /* gate */ 850 merge_phi_nodes, /* execute */ 851 NULL, /* sub */ 852 NULL, /* next */ 853 0, /* static_pass_number */ 854 TV_TREE_MERGE_PHI, /* tv_id */ 855 PROP_cfg | PROP_ssa, /* properties_required */ 856 0, /* properties_provided */ 857 0, /* properties_destroyed */ 858 0, /* todo_flags_start */ 859 TODO_dump_func | TODO_ggc_collect /* todo_flags_finish */ 860 | TODO_verify_ssa, 861 0 /* letter */ 862}; 863