1169689Skan/* Dead code elimination pass for the GNU compiler. 2169689Skan Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan Contributed by Ben Elliston <bje@redhat.com> 4169689Skan and Andrew MacLeod <amacleod@redhat.com> 5169689Skan Adapted to use control dependence by Steven Bosscher, SUSE Labs. 6169689Skan 7169689SkanThis file is part of GCC. 8169689Skan 9169689SkanGCC is free software; you can redistribute it and/or modify it 10169689Skanunder the terms of the GNU General Public License as published by the 11169689SkanFree Software Foundation; either version 2, or (at your option) any 12169689Skanlater version. 13169689Skan 14169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT 15169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 16169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17169689Skanfor more details. 18169689Skan 19169689SkanYou should have received a copy of the GNU General Public License 20169689Skanalong with GCC; see the file COPYING. If not, write to the Free 21169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 22169689Skan02110-1301, USA. */ 23169689Skan 24169689Skan/* Dead code elimination. 25169689Skan 26169689Skan References: 27169689Skan 28169689Skan Building an Optimizing Compiler, 29169689Skan Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. 30169689Skan 31169689Skan Advanced Compiler Design and Implementation, 32169689Skan Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10. 33169689Skan 34169689Skan Dead-code elimination is the removal of statements which have no 35169689Skan impact on the program's output. "Dead statements" have no impact 36169689Skan on the program's output, while "necessary statements" may have 37169689Skan impact on the output. 38169689Skan 39169689Skan The algorithm consists of three phases: 40169689Skan 1. Marking as necessary all statements known to be necessary, 41169689Skan e.g. most function calls, writing a value to memory, etc; 42169689Skan 2. Propagating necessary statements, e.g., the statements 43169689Skan giving values to operands in necessary statements; and 44169689Skan 3. Removing dead statements. */ 45169689Skan 46169689Skan#include "config.h" 47169689Skan#include "system.h" 48169689Skan#include "coretypes.h" 49169689Skan#include "tm.h" 50169689Skan#include "ggc.h" 51169689Skan 52169689Skan/* These RTL headers are needed for basic-block.h. */ 53169689Skan#include "rtl.h" 54169689Skan#include "tm_p.h" 55169689Skan#include "hard-reg-set.h" 56169689Skan#include "obstack.h" 57169689Skan#include "basic-block.h" 58169689Skan 59169689Skan#include "tree.h" 60169689Skan#include "diagnostic.h" 61169689Skan#include "tree-flow.h" 62169689Skan#include "tree-gimple.h" 63169689Skan#include "tree-dump.h" 64169689Skan#include "tree-pass.h" 65169689Skan#include "timevar.h" 66169689Skan#include "flags.h" 67169689Skan#include "cfgloop.h" 68169689Skan#include "tree-scalar-evolution.h" 69169689Skan 70169689Skanstatic struct stmt_stats 71169689Skan{ 72169689Skan int total; 73169689Skan int total_phis; 74169689Skan int removed; 75169689Skan int removed_phis; 76169689Skan} stats; 77169689Skan 78169689Skanstatic VEC(tree,heap) *worklist; 79169689Skan 80169689Skan/* Vector indicating an SSA name has already been processed and marked 81169689Skan as necessary. */ 82169689Skanstatic sbitmap processed; 83169689Skan 84169689Skan/* Vector indicating that last_stmt if a basic block has already been 85169689Skan marked as necessary. */ 86169689Skanstatic sbitmap last_stmt_necessary; 87169689Skan 88169689Skan/* Before we can determine whether a control branch is dead, we need to 89169689Skan compute which blocks are control dependent on which edges. 90169689Skan 91169689Skan We expect each block to be control dependent on very few edges so we 92169689Skan use a bitmap for each block recording its edges. An array holds the 93169689Skan bitmap. The Ith bit in the bitmap is set if that block is dependent 94169689Skan on the Ith edge. */ 95169689Skanstatic bitmap *control_dependence_map; 96169689Skan 97169689Skan/* Vector indicating that a basic block has already had all the edges 98169689Skan processed that it is control dependent on. */ 99169689Skanstatic sbitmap visited_control_parents; 100169689Skan 101169689Skan/* TRUE if this pass alters the CFG (by removing control statements). 102169689Skan FALSE otherwise. 103169689Skan 104169689Skan If this pass alters the CFG, then it will arrange for the dominators 105169689Skan to be recomputed. */ 106169689Skanstatic bool cfg_altered; 107169689Skan 108169689Skan/* Execute code that follows the macro for each edge (given number 109169689Skan EDGE_NUMBER within the CODE) for which the block with index N is 110169689Skan control dependent. */ 111169689Skan#define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \ 112169689Skan EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \ 113169689Skan (EDGE_NUMBER), (BI)) 114169689Skan 115169689Skan/* Local function prototypes. */ 116169689Skanstatic inline void set_control_dependence_map_bit (basic_block, int); 117169689Skanstatic inline void clear_control_dependence_bitmap (basic_block); 118169689Skanstatic void find_all_control_dependences (struct edge_list *); 119169689Skanstatic void find_control_dependence (struct edge_list *, int); 120169689Skanstatic inline basic_block find_pdom (basic_block); 121169689Skan 122169689Skanstatic inline void mark_stmt_necessary (tree, bool); 123169689Skanstatic inline void mark_operand_necessary (tree, bool); 124169689Skan 125169689Skanstatic void mark_stmt_if_obviously_necessary (tree, bool); 126169689Skanstatic void find_obviously_necessary_stmts (struct edge_list *); 127169689Skan 128169689Skanstatic void mark_control_dependent_edges_necessary (basic_block, struct edge_list *); 129169689Skanstatic void propagate_necessity (struct edge_list *); 130169689Skan 131169689Skanstatic void eliminate_unnecessary_stmts (void); 132169689Skanstatic void remove_dead_phis (basic_block); 133169689Skanstatic void remove_dead_stmt (block_stmt_iterator *, basic_block); 134169689Skan 135169689Skanstatic void print_stats (void); 136169689Skanstatic void tree_dce_init (bool); 137169689Skanstatic void tree_dce_done (bool); 138169689Skan 139169689Skan/* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */ 140169689Skanstatic inline void 141169689Skanset_control_dependence_map_bit (basic_block bb, int edge_index) 142169689Skan{ 143169689Skan if (bb == ENTRY_BLOCK_PTR) 144169689Skan return; 145169689Skan gcc_assert (bb != EXIT_BLOCK_PTR); 146169689Skan bitmap_set_bit (control_dependence_map[bb->index], edge_index); 147169689Skan} 148169689Skan 149169689Skan/* Clear all control dependences for block BB. */ 150169689Skanstatic inline void 151169689Skanclear_control_dependence_bitmap (basic_block bb) 152169689Skan{ 153169689Skan bitmap_clear (control_dependence_map[bb->index]); 154169689Skan} 155169689Skan 156169689Skan/* Record all blocks' control dependences on all edges in the edge 157169689Skan list EL, ala Morgan, Section 3.6. */ 158169689Skan 159169689Skanstatic void 160169689Skanfind_all_control_dependences (struct edge_list *el) 161169689Skan{ 162169689Skan int i; 163169689Skan 164169689Skan for (i = 0; i < NUM_EDGES (el); ++i) 165169689Skan find_control_dependence (el, i); 166169689Skan} 167169689Skan 168169689Skan/* Determine all blocks' control dependences on the given edge with edge_list 169169689Skan EL index EDGE_INDEX, ala Morgan, Section 3.6. */ 170169689Skan 171169689Skanstatic void 172169689Skanfind_control_dependence (struct edge_list *el, int edge_index) 173169689Skan{ 174169689Skan basic_block current_block; 175169689Skan basic_block ending_block; 176169689Skan 177169689Skan gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR); 178169689Skan 179169689Skan if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR) 180169689Skan ending_block = single_succ (ENTRY_BLOCK_PTR); 181169689Skan else 182169689Skan ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index)); 183169689Skan 184169689Skan for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index); 185169689Skan current_block != ending_block && current_block != EXIT_BLOCK_PTR; 186169689Skan current_block = find_pdom (current_block)) 187169689Skan { 188169689Skan edge e = INDEX_EDGE (el, edge_index); 189169689Skan 190169689Skan /* For abnormal edges, we don't make current_block control 191169689Skan dependent because instructions that throw are always necessary 192169689Skan anyway. */ 193169689Skan if (e->flags & EDGE_ABNORMAL) 194169689Skan continue; 195169689Skan 196169689Skan set_control_dependence_map_bit (current_block, edge_index); 197169689Skan } 198169689Skan} 199169689Skan 200169689Skan/* Find the immediate postdominator PDOM of the specified basic block BLOCK. 201169689Skan This function is necessary because some blocks have negative numbers. */ 202169689Skan 203169689Skanstatic inline basic_block 204169689Skanfind_pdom (basic_block block) 205169689Skan{ 206169689Skan gcc_assert (block != ENTRY_BLOCK_PTR); 207169689Skan 208169689Skan if (block == EXIT_BLOCK_PTR) 209169689Skan return EXIT_BLOCK_PTR; 210169689Skan else 211169689Skan { 212169689Skan basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block); 213169689Skan if (! bb) 214169689Skan return EXIT_BLOCK_PTR; 215169689Skan return bb; 216169689Skan } 217169689Skan} 218169689Skan 219169689Skan#define NECESSARY(stmt) stmt->common.asm_written_flag 220169689Skan 221169689Skan/* If STMT is not already marked necessary, mark it, and add it to the 222169689Skan worklist if ADD_TO_WORKLIST is true. */ 223169689Skanstatic inline void 224169689Skanmark_stmt_necessary (tree stmt, bool add_to_worklist) 225169689Skan{ 226169689Skan gcc_assert (stmt); 227169689Skan gcc_assert (!DECL_P (stmt)); 228169689Skan 229169689Skan if (NECESSARY (stmt)) 230169689Skan return; 231169689Skan 232169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 233169689Skan { 234169689Skan fprintf (dump_file, "Marking useful stmt: "); 235169689Skan print_generic_stmt (dump_file, stmt, TDF_SLIM); 236169689Skan fprintf (dump_file, "\n"); 237169689Skan } 238169689Skan 239169689Skan NECESSARY (stmt) = 1; 240169689Skan if (add_to_worklist) 241169689Skan VEC_safe_push (tree, heap, worklist, stmt); 242169689Skan} 243169689Skan 244169689Skan/* Mark the statement defining operand OP as necessary. PHIONLY is true 245169689Skan if we should only mark it necessary if it is a phi node. */ 246169689Skan 247169689Skanstatic inline void 248169689Skanmark_operand_necessary (tree op, bool phionly) 249169689Skan{ 250169689Skan tree stmt; 251169689Skan int ver; 252169689Skan 253169689Skan gcc_assert (op); 254169689Skan 255169689Skan ver = SSA_NAME_VERSION (op); 256169689Skan if (TEST_BIT (processed, ver)) 257169689Skan return; 258169689Skan SET_BIT (processed, ver); 259169689Skan 260169689Skan stmt = SSA_NAME_DEF_STMT (op); 261169689Skan gcc_assert (stmt); 262169689Skan 263169689Skan if (NECESSARY (stmt) 264169689Skan || IS_EMPTY_STMT (stmt) 265169689Skan || (phionly && TREE_CODE (stmt) != PHI_NODE)) 266169689Skan return; 267169689Skan 268169689Skan NECESSARY (stmt) = 1; 269169689Skan VEC_safe_push (tree, heap, worklist, stmt); 270169689Skan} 271169689Skan 272169689Skan 273169689Skan/* Mark STMT as necessary if it obviously is. Add it to the worklist if 274169689Skan it can make other statements necessary. 275169689Skan 276169689Skan If AGGRESSIVE is false, control statements are conservatively marked as 277169689Skan necessary. */ 278169689Skan 279169689Skanstatic void 280169689Skanmark_stmt_if_obviously_necessary (tree stmt, bool aggressive) 281169689Skan{ 282169689Skan stmt_ann_t ann; 283169689Skan tree op; 284169689Skan 285169689Skan /* With non-call exceptions, we have to assume that all statements could 286169689Skan throw. If a statement may throw, it is inherently necessary. */ 287169689Skan if (flag_non_call_exceptions 288169689Skan && tree_could_throw_p (stmt)) 289169689Skan { 290169689Skan mark_stmt_necessary (stmt, true); 291169689Skan return; 292169689Skan } 293169689Skan 294169689Skan /* Statements that are implicitly live. Most function calls, asm and return 295169689Skan statements are required. Labels and BIND_EXPR nodes are kept because 296169689Skan they are control flow, and we have no way of knowing whether they can be 297169689Skan removed. DCE can eliminate all the other statements in a block, and CFG 298169689Skan can then remove the block and labels. */ 299169689Skan switch (TREE_CODE (stmt)) 300169689Skan { 301169689Skan case BIND_EXPR: 302169689Skan case LABEL_EXPR: 303169689Skan case CASE_LABEL_EXPR: 304169689Skan mark_stmt_necessary (stmt, false); 305169689Skan return; 306169689Skan 307169689Skan case ASM_EXPR: 308169689Skan case RESX_EXPR: 309169689Skan case RETURN_EXPR: 310169689Skan mark_stmt_necessary (stmt, true); 311169689Skan return; 312169689Skan 313169689Skan case CALL_EXPR: 314169689Skan /* Most, but not all function calls are required. Function calls that 315169689Skan produce no result and have no side effects (i.e. const pure 316169689Skan functions) are unnecessary. */ 317169689Skan if (TREE_SIDE_EFFECTS (stmt)) 318169689Skan mark_stmt_necessary (stmt, true); 319169689Skan return; 320169689Skan 321169689Skan case MODIFY_EXPR: 322169689Skan op = get_call_expr_in (stmt); 323169689Skan if (op && TREE_SIDE_EFFECTS (op)) 324169689Skan { 325169689Skan mark_stmt_necessary (stmt, true); 326169689Skan return; 327169689Skan } 328169689Skan 329169689Skan /* These values are mildly magic bits of the EH runtime. We can't 330169689Skan see the entire lifetime of these values until landing pads are 331169689Skan generated. */ 332169689Skan if (TREE_CODE (TREE_OPERAND (stmt, 0)) == EXC_PTR_EXPR 333169689Skan || TREE_CODE (TREE_OPERAND (stmt, 0)) == FILTER_EXPR) 334169689Skan { 335169689Skan mark_stmt_necessary (stmt, true); 336169689Skan return; 337169689Skan } 338169689Skan break; 339169689Skan 340169689Skan case GOTO_EXPR: 341169689Skan gcc_assert (!simple_goto_p (stmt)); 342169689Skan mark_stmt_necessary (stmt, true); 343169689Skan return; 344169689Skan 345169689Skan case COND_EXPR: 346169689Skan gcc_assert (EDGE_COUNT (bb_for_stmt (stmt)->succs) == 2); 347169689Skan /* Fall through. */ 348169689Skan 349169689Skan case SWITCH_EXPR: 350169689Skan if (! aggressive) 351169689Skan mark_stmt_necessary (stmt, true); 352169689Skan break; 353169689Skan 354169689Skan default: 355169689Skan break; 356169689Skan } 357169689Skan 358169689Skan ann = stmt_ann (stmt); 359169689Skan 360169689Skan /* If the statement has volatile operands, it needs to be preserved. 361169689Skan Same for statements that can alter control flow in unpredictable 362169689Skan ways. */ 363169689Skan if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt)) 364169689Skan { 365169689Skan mark_stmt_necessary (stmt, true); 366169689Skan return; 367169689Skan } 368169689Skan 369169689Skan if (is_hidden_global_store (stmt)) 370169689Skan { 371169689Skan mark_stmt_necessary (stmt, true); 372169689Skan return; 373169689Skan } 374169689Skan 375169689Skan return; 376169689Skan} 377169689Skan 378169689Skan/* Find obviously necessary statements. These are things like most function 379169689Skan calls, and stores to file level variables. 380169689Skan 381169689Skan If EL is NULL, control statements are conservatively marked as 382169689Skan necessary. Otherwise it contains the list of edges used by control 383169689Skan dependence analysis. */ 384169689Skan 385169689Skanstatic void 386169689Skanfind_obviously_necessary_stmts (struct edge_list *el) 387169689Skan{ 388169689Skan basic_block bb; 389169689Skan block_stmt_iterator i; 390169689Skan edge e; 391169689Skan 392169689Skan FOR_EACH_BB (bb) 393169689Skan { 394169689Skan tree phi; 395169689Skan 396169689Skan /* Check any PHI nodes in the block. */ 397169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 398169689Skan { 399169689Skan NECESSARY (phi) = 0; 400169689Skan 401169689Skan /* PHIs for virtual variables do not directly affect code 402169689Skan generation and need not be considered inherently necessary 403169689Skan regardless of the bits set in their decl. 404169689Skan 405169689Skan Thus, we only need to mark PHIs for real variables which 406169689Skan need their result preserved as being inherently necessary. */ 407169689Skan if (is_gimple_reg (PHI_RESULT (phi)) 408169689Skan && is_global_var (SSA_NAME_VAR (PHI_RESULT (phi)))) 409169689Skan mark_stmt_necessary (phi, true); 410169689Skan } 411169689Skan 412169689Skan /* Check all statements in the block. */ 413169689Skan for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i)) 414169689Skan { 415169689Skan tree stmt = bsi_stmt (i); 416169689Skan NECESSARY (stmt) = 0; 417169689Skan mark_stmt_if_obviously_necessary (stmt, el != NULL); 418169689Skan } 419169689Skan } 420169689Skan 421169689Skan if (el) 422169689Skan { 423169689Skan /* Prevent the loops from being removed. We must keep the infinite loops, 424169689Skan and we currently do not have a means to recognize the finite ones. */ 425169689Skan FOR_EACH_BB (bb) 426169689Skan { 427169689Skan edge_iterator ei; 428169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 429169689Skan if (e->flags & EDGE_DFS_BACK) 430169689Skan mark_control_dependent_edges_necessary (e->dest, el); 431169689Skan } 432169689Skan } 433169689Skan} 434169689Skan 435169689Skan/* Make corresponding control dependent edges necessary. We only 436169689Skan have to do this once for each basic block, so we clear the bitmap 437169689Skan after we're done. */ 438169689Skanstatic void 439169689Skanmark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) 440169689Skan{ 441169689Skan bitmap_iterator bi; 442169689Skan unsigned edge_number; 443169689Skan 444169689Skan gcc_assert (bb != EXIT_BLOCK_PTR); 445169689Skan 446169689Skan if (bb == ENTRY_BLOCK_PTR) 447169689Skan return; 448169689Skan 449169689Skan EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number) 450169689Skan { 451169689Skan tree t; 452169689Skan basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); 453169689Skan 454169689Skan if (TEST_BIT (last_stmt_necessary, cd_bb->index)) 455169689Skan continue; 456169689Skan SET_BIT (last_stmt_necessary, cd_bb->index); 457169689Skan 458169689Skan t = last_stmt (cd_bb); 459169689Skan if (t && is_ctrl_stmt (t)) 460169689Skan mark_stmt_necessary (t, true); 461169689Skan } 462169689Skan} 463169689Skan 464169689Skan/* Propagate necessity using the operands of necessary statements. Process 465169689Skan the uses on each statement in the worklist, and add all feeding statements 466169689Skan which contribute to the calculation of this value to the worklist. 467169689Skan 468169689Skan In conservative mode, EL is NULL. */ 469169689Skan 470169689Skanstatic void 471169689Skanpropagate_necessity (struct edge_list *el) 472169689Skan{ 473169689Skan tree i; 474169689Skan bool aggressive = (el ? true : false); 475169689Skan 476169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 477169689Skan fprintf (dump_file, "\nProcessing worklist:\n"); 478169689Skan 479169689Skan while (VEC_length (tree, worklist) > 0) 480169689Skan { 481169689Skan /* Take `i' from worklist. */ 482169689Skan i = VEC_pop (tree, worklist); 483169689Skan 484169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 485169689Skan { 486169689Skan fprintf (dump_file, "processing: "); 487169689Skan print_generic_stmt (dump_file, i, TDF_SLIM); 488169689Skan fprintf (dump_file, "\n"); 489169689Skan } 490169689Skan 491169689Skan if (aggressive) 492169689Skan { 493169689Skan /* Mark the last statements of the basic blocks that the block 494169689Skan containing `i' is control dependent on, but only if we haven't 495169689Skan already done so. */ 496169689Skan basic_block bb = bb_for_stmt (i); 497169689Skan if (bb != ENTRY_BLOCK_PTR 498169689Skan && ! TEST_BIT (visited_control_parents, bb->index)) 499169689Skan { 500169689Skan SET_BIT (visited_control_parents, bb->index); 501169689Skan mark_control_dependent_edges_necessary (bb, el); 502169689Skan } 503169689Skan } 504169689Skan 505169689Skan if (TREE_CODE (i) == PHI_NODE) 506169689Skan { 507169689Skan /* PHI nodes are somewhat special in that each PHI alternative has 508169689Skan data and control dependencies. All the statements feeding the 509169689Skan PHI node's arguments are always necessary. In aggressive mode, 510169689Skan we also consider the control dependent edges leading to the 511169689Skan predecessor block associated with each PHI alternative as 512169689Skan necessary. */ 513169689Skan int k; 514169689Skan for (k = 0; k < PHI_NUM_ARGS (i); k++) 515169689Skan { 516169689Skan tree arg = PHI_ARG_DEF (i, k); 517169689Skan if (TREE_CODE (arg) == SSA_NAME) 518169689Skan mark_operand_necessary (arg, false); 519169689Skan } 520169689Skan 521169689Skan if (aggressive) 522169689Skan { 523169689Skan for (k = 0; k < PHI_NUM_ARGS (i); k++) 524169689Skan { 525169689Skan basic_block arg_bb = PHI_ARG_EDGE (i, k)->src; 526169689Skan if (arg_bb != ENTRY_BLOCK_PTR 527169689Skan && ! TEST_BIT (visited_control_parents, arg_bb->index)) 528169689Skan { 529169689Skan SET_BIT (visited_control_parents, arg_bb->index); 530169689Skan mark_control_dependent_edges_necessary (arg_bb, el); 531169689Skan } 532169689Skan } 533169689Skan } 534169689Skan } 535169689Skan else 536169689Skan { 537169689Skan /* Propagate through the operands. Examine all the USE, VUSE and 538169689Skan V_MAY_DEF operands in this statement. Mark all the statements 539169689Skan which feed this statement's uses as necessary. */ 540169689Skan ssa_op_iter iter; 541169689Skan tree use; 542169689Skan 543169689Skan /* The operands of V_MAY_DEF expressions are also needed as they 544169689Skan represent potential definitions that may reach this 545169689Skan statement (V_MAY_DEF operands allow us to follow def-def 546169689Skan links). */ 547169689Skan 548169689Skan FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES) 549169689Skan mark_operand_necessary (use, false); 550169689Skan } 551169689Skan } 552169689Skan} 553169689Skan 554169689Skan 555169689Skan/* Propagate necessity around virtual phi nodes used in kill operands. 556169689Skan The reason this isn't done during propagate_necessity is because we don't 557169689Skan want to keep phis around that are just there for must-defs, unless we 558169689Skan absolutely have to. After we've rewritten the reaching definitions to be 559169689Skan correct in the previous part of the fixup routine, we can simply propagate 560169689Skan around the information about which of these virtual phi nodes are really 561169689Skan used, and set the NECESSARY flag accordingly. 562169689Skan Note that we do the minimum here to ensure that we keep alive the phis that 563169689Skan are actually used in the corrected SSA form. In particular, some of these 564169689Skan phis may now have all of the same operand, and will be deleted by some 565169689Skan other pass. */ 566169689Skan 567169689Skanstatic void 568169689Skanmark_really_necessary_kill_operand_phis (void) 569169689Skan{ 570169689Skan basic_block bb; 571169689Skan int i; 572169689Skan 573169689Skan /* Seed the worklist with the new virtual phi arguments and virtual 574169689Skan uses */ 575169689Skan FOR_EACH_BB (bb) 576169689Skan { 577169689Skan block_stmt_iterator bsi; 578169689Skan tree phi; 579169689Skan 580169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 581169689Skan { 582169689Skan if (!is_gimple_reg (PHI_RESULT (phi)) && NECESSARY (phi)) 583169689Skan { 584169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 585169689Skan mark_operand_necessary (PHI_ARG_DEF (phi, i), true); 586169689Skan } 587169689Skan } 588169689Skan 589169689Skan for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 590169689Skan { 591169689Skan tree stmt = bsi_stmt (bsi); 592169689Skan 593169689Skan if (NECESSARY (stmt)) 594169689Skan { 595169689Skan use_operand_p use_p; 596169689Skan ssa_op_iter iter; 597169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 598169689Skan SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 599169689Skan { 600169689Skan tree use = USE_FROM_PTR (use_p); 601169689Skan mark_operand_necessary (use, true); 602169689Skan } 603169689Skan } 604169689Skan } 605169689Skan } 606169689Skan 607169689Skan /* Mark all virtual phis still in use as necessary, and all of their 608169689Skan arguments that are phis as necessary. */ 609169689Skan while (VEC_length (tree, worklist) > 0) 610169689Skan { 611169689Skan tree use = VEC_pop (tree, worklist); 612169689Skan 613169689Skan for (i = 0; i < PHI_NUM_ARGS (use); i++) 614169689Skan mark_operand_necessary (PHI_ARG_DEF (use, i), true); 615169689Skan } 616169689Skan} 617169689Skan 618169689Skan 619169689Skan 620169689Skan 621169689Skan/* Eliminate unnecessary statements. Any instruction not marked as necessary 622169689Skan contributes nothing to the program, and can be deleted. */ 623169689Skan 624169689Skanstatic void 625169689Skaneliminate_unnecessary_stmts (void) 626169689Skan{ 627169689Skan basic_block bb; 628169689Skan block_stmt_iterator i; 629169689Skan 630169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 631169689Skan fprintf (dump_file, "\nEliminating unnecessary statements:\n"); 632169689Skan 633169689Skan clear_special_calls (); 634169689Skan FOR_EACH_BB (bb) 635169689Skan { 636169689Skan /* Remove dead PHI nodes. */ 637169689Skan remove_dead_phis (bb); 638169689Skan } 639169689Skan 640169689Skan FOR_EACH_BB (bb) 641169689Skan { 642169689Skan /* Remove dead statements. */ 643169689Skan for (i = bsi_start (bb); ! bsi_end_p (i) ; ) 644169689Skan { 645169689Skan tree t = bsi_stmt (i); 646169689Skan 647169689Skan stats.total++; 648169689Skan 649169689Skan /* If `i' is not necessary then remove it. */ 650169689Skan if (! NECESSARY (t)) 651169689Skan remove_dead_stmt (&i, bb); 652169689Skan else 653169689Skan { 654169689Skan tree call = get_call_expr_in (t); 655169689Skan if (call) 656169689Skan notice_special_calls (call); 657169689Skan bsi_next (&i); 658169689Skan } 659169689Skan } 660169689Skan } 661169689Skan } 662169689Skan 663169689Skan/* Remove dead PHI nodes from block BB. */ 664169689Skan 665169689Skanstatic void 666169689Skanremove_dead_phis (basic_block bb) 667169689Skan{ 668169689Skan tree prev, phi; 669169689Skan 670169689Skan prev = NULL_TREE; 671169689Skan phi = phi_nodes (bb); 672169689Skan while (phi) 673169689Skan { 674169689Skan stats.total_phis++; 675169689Skan 676169689Skan if (! NECESSARY (phi)) 677169689Skan { 678169689Skan tree next = PHI_CHAIN (phi); 679169689Skan 680169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 681169689Skan { 682169689Skan fprintf (dump_file, "Deleting : "); 683169689Skan print_generic_stmt (dump_file, phi, TDF_SLIM); 684169689Skan fprintf (dump_file, "\n"); 685169689Skan } 686169689Skan 687169689Skan remove_phi_node (phi, prev); 688169689Skan stats.removed_phis++; 689169689Skan phi = next; 690169689Skan } 691169689Skan else 692169689Skan { 693169689Skan prev = phi; 694169689Skan phi = PHI_CHAIN (phi); 695169689Skan } 696169689Skan } 697169689Skan} 698169689Skan 699169689Skan/* Remove dead statement pointed to by iterator I. Receives the basic block BB 700169689Skan containing I so that we don't have to look it up. */ 701169689Skan 702169689Skanstatic void 703169689Skanremove_dead_stmt (block_stmt_iterator *i, basic_block bb) 704169689Skan{ 705169689Skan tree t = bsi_stmt (*i); 706169689Skan def_operand_p def_p; 707169689Skan 708169689Skan ssa_op_iter iter; 709169689Skan 710169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 711169689Skan { 712169689Skan fprintf (dump_file, "Deleting : "); 713169689Skan print_generic_stmt (dump_file, t, TDF_SLIM); 714169689Skan fprintf (dump_file, "\n"); 715169689Skan } 716169689Skan 717169689Skan stats.removed++; 718169689Skan 719169689Skan /* If we have determined that a conditional branch statement contributes 720169689Skan nothing to the program, then we not only remove it, but we also change 721169689Skan the flow graph so that the current block will simply fall-thru to its 722169689Skan immediate post-dominator. The blocks we are circumventing will be 723169689Skan removed by cleanup_tree_cfg if this change in the flow graph makes them 724169689Skan unreachable. */ 725169689Skan if (is_ctrl_stmt (t)) 726169689Skan { 727169689Skan basic_block post_dom_bb; 728169689Skan 729169689Skan /* The post dominance info has to be up-to-date. */ 730169689Skan gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK); 731169689Skan /* Get the immediate post dominator of bb. */ 732169689Skan post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); 733169689Skan 734169689Skan /* There are three particularly problematical cases. 735169689Skan 736169689Skan 1. Blocks that do not have an immediate post dominator. This 737169689Skan can happen with infinite loops. 738169689Skan 739169689Skan 2. Blocks that are only post dominated by the exit block. These 740169689Skan can also happen for infinite loops as we create fake edges 741169689Skan in the dominator tree. 742169689Skan 743169689Skan 3. If the post dominator has PHI nodes we may be able to compute 744169689Skan the right PHI args for them. 745169689Skan 746169689Skan 747169689Skan In each of these cases we must remove the control statement 748169689Skan as it may reference SSA_NAMEs which are going to be removed and 749169689Skan we remove all but one outgoing edge from the block. */ 750169689Skan if (! post_dom_bb 751169689Skan || post_dom_bb == EXIT_BLOCK_PTR 752169689Skan || phi_nodes (post_dom_bb)) 753169689Skan ; 754169689Skan else 755169689Skan { 756169689Skan /* Redirect the first edge out of BB to reach POST_DOM_BB. */ 757169689Skan redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb); 758169689Skan PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL; 759169689Skan } 760169689Skan EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; 761169689Skan EDGE_SUCC (bb, 0)->count = bb->count; 762169689Skan 763169689Skan /* The edge is no longer associated with a conditional, so it does 764169689Skan not have TRUE/FALSE flags. */ 765169689Skan EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 766169689Skan 767169689Skan /* The lone outgoing edge from BB will be a fallthru edge. */ 768169689Skan EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU; 769169689Skan 770169689Skan /* Remove the remaining the outgoing edges. */ 771169689Skan while (!single_succ_p (bb)) 772169689Skan { 773169689Skan /* FIXME. When we remove the edge, we modify the CFG, which 774169689Skan in turn modifies the dominator and post-dominator tree. 775169689Skan Is it safe to postpone recomputing the dominator and 776169689Skan post-dominator tree until the end of this pass given that 777169689Skan the post-dominators are used above? */ 778169689Skan cfg_altered = true; 779169689Skan remove_edge (EDGE_SUCC (bb, 1)); 780169689Skan } 781169689Skan } 782169689Skan 783169689Skan FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter, SSA_OP_VIRTUAL_DEFS) 784169689Skan { 785169689Skan tree def = DEF_FROM_PTR (def_p); 786169689Skan mark_sym_for_renaming (SSA_NAME_VAR (def)); 787169689Skan } 788169689Skan bsi_remove (i, true); 789169689Skan release_defs (t); 790169689Skan} 791169689Skan 792169689Skan/* Print out removed statement statistics. */ 793169689Skan 794169689Skanstatic void 795169689Skanprint_stats (void) 796169689Skan{ 797169689Skan if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS))) 798169689Skan { 799169689Skan float percg; 800169689Skan 801169689Skan percg = ((float) stats.removed / (float) stats.total) * 100; 802169689Skan fprintf (dump_file, "Removed %d of %d statements (%d%%)\n", 803169689Skan stats.removed, stats.total, (int) percg); 804169689Skan 805169689Skan if (stats.total_phis == 0) 806169689Skan percg = 0; 807169689Skan else 808169689Skan percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100; 809169689Skan 810169689Skan fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n", 811169689Skan stats.removed_phis, stats.total_phis, (int) percg); 812169689Skan } 813169689Skan} 814169689Skan 815169689Skan/* Initialization for this pass. Set up the used data structures. */ 816169689Skan 817169689Skanstatic void 818169689Skantree_dce_init (bool aggressive) 819169689Skan{ 820169689Skan memset ((void *) &stats, 0, sizeof (stats)); 821169689Skan 822169689Skan if (aggressive) 823169689Skan { 824169689Skan int i; 825169689Skan 826169689Skan control_dependence_map = XNEWVEC (bitmap, last_basic_block); 827169689Skan for (i = 0; i < last_basic_block; ++i) 828169689Skan control_dependence_map[i] = BITMAP_ALLOC (NULL); 829169689Skan 830169689Skan last_stmt_necessary = sbitmap_alloc (last_basic_block); 831169689Skan sbitmap_zero (last_stmt_necessary); 832169689Skan } 833169689Skan 834169689Skan processed = sbitmap_alloc (num_ssa_names + 1); 835169689Skan sbitmap_zero (processed); 836169689Skan 837169689Skan worklist = VEC_alloc (tree, heap, 64); 838169689Skan cfg_altered = false; 839169689Skan} 840169689Skan 841169689Skan/* Cleanup after this pass. */ 842169689Skan 843169689Skanstatic void 844169689Skantree_dce_done (bool aggressive) 845169689Skan{ 846169689Skan if (aggressive) 847169689Skan { 848169689Skan int i; 849169689Skan 850169689Skan for (i = 0; i < last_basic_block; ++i) 851169689Skan BITMAP_FREE (control_dependence_map[i]); 852169689Skan free (control_dependence_map); 853169689Skan 854169689Skan sbitmap_free (visited_control_parents); 855169689Skan sbitmap_free (last_stmt_necessary); 856169689Skan } 857169689Skan 858169689Skan sbitmap_free (processed); 859169689Skan 860169689Skan VEC_free (tree, heap, worklist); 861169689Skan} 862169689Skan 863169689Skan/* Main routine to eliminate dead code. 864169689Skan 865169689Skan AGGRESSIVE controls the aggressiveness of the algorithm. 866169689Skan In conservative mode, we ignore control dependence and simply declare 867169689Skan all but the most trivially dead branches necessary. This mode is fast. 868169689Skan In aggressive mode, control dependences are taken into account, which 869169689Skan results in more dead code elimination, but at the cost of some time. 870169689Skan 871169689Skan FIXME: Aggressive mode before PRE doesn't work currently because 872169689Skan the dominance info is not invalidated after DCE1. This is 873169689Skan not an issue right now because we only run aggressive DCE 874169689Skan as the last tree SSA pass, but keep this in mind when you 875169689Skan start experimenting with pass ordering. */ 876169689Skan 877169689Skanstatic void 878169689Skanperform_tree_ssa_dce (bool aggressive) 879169689Skan{ 880169689Skan struct edge_list *el = NULL; 881169689Skan 882169689Skan tree_dce_init (aggressive); 883169689Skan 884169689Skan if (aggressive) 885169689Skan { 886169689Skan /* Compute control dependence. */ 887169689Skan timevar_push (TV_CONTROL_DEPENDENCES); 888169689Skan calculate_dominance_info (CDI_POST_DOMINATORS); 889169689Skan el = create_edge_list (); 890169689Skan find_all_control_dependences (el); 891169689Skan timevar_pop (TV_CONTROL_DEPENDENCES); 892169689Skan 893169689Skan visited_control_parents = sbitmap_alloc (last_basic_block); 894169689Skan sbitmap_zero (visited_control_parents); 895169689Skan 896169689Skan mark_dfs_back_edges (); 897169689Skan } 898169689Skan 899169689Skan find_obviously_necessary_stmts (el); 900169689Skan 901169689Skan propagate_necessity (el); 902169689Skan 903169689Skan mark_really_necessary_kill_operand_phis (); 904169689Skan eliminate_unnecessary_stmts (); 905169689Skan 906169689Skan if (aggressive) 907169689Skan free_dominance_info (CDI_POST_DOMINATORS); 908169689Skan 909169689Skan /* If we removed paths in the CFG, then we need to update 910169689Skan dominators as well. I haven't investigated the possibility 911169689Skan of incrementally updating dominators. */ 912169689Skan if (cfg_altered) 913169689Skan free_dominance_info (CDI_DOMINATORS); 914169689Skan 915169689Skan /* Debugging dumps. */ 916169689Skan if (dump_file) 917169689Skan print_stats (); 918169689Skan 919169689Skan tree_dce_done (aggressive); 920169689Skan 921169689Skan free_edge_list (el); 922169689Skan} 923169689Skan 924169689Skan/* Pass entry points. */ 925169689Skanstatic unsigned int 926169689Skantree_ssa_dce (void) 927169689Skan{ 928169689Skan perform_tree_ssa_dce (/*aggressive=*/false); 929169689Skan return 0; 930169689Skan} 931169689Skan 932169689Skanstatic unsigned int 933169689Skantree_ssa_dce_loop (void) 934169689Skan{ 935169689Skan perform_tree_ssa_dce (/*aggressive=*/false); 936169689Skan free_numbers_of_iterations_estimates (current_loops); 937169689Skan scev_reset (); 938169689Skan return 0; 939169689Skan} 940169689Skan 941169689Skanstatic unsigned int 942169689Skantree_ssa_cd_dce (void) 943169689Skan{ 944169689Skan perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); 945169689Skan return 0; 946169689Skan} 947169689Skan 948169689Skanstatic bool 949169689Skangate_dce (void) 950169689Skan{ 951169689Skan return flag_tree_dce != 0; 952169689Skan} 953169689Skan 954169689Skanstruct tree_opt_pass pass_dce = 955169689Skan{ 956169689Skan "dce", /* name */ 957169689Skan gate_dce, /* gate */ 958169689Skan tree_ssa_dce, /* execute */ 959169689Skan NULL, /* sub */ 960169689Skan NULL, /* next */ 961169689Skan 0, /* static_pass_number */ 962169689Skan TV_TREE_DCE, /* tv_id */ 963169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 964169689Skan 0, /* properties_provided */ 965169689Skan 0, /* properties_destroyed */ 966169689Skan 0, /* todo_flags_start */ 967169689Skan TODO_dump_func 968169689Skan | TODO_update_ssa 969169689Skan | TODO_cleanup_cfg 970169689Skan | TODO_ggc_collect 971169689Skan | TODO_verify_ssa 972169689Skan | TODO_remove_unused_locals, /* todo_flags_finish */ 973169689Skan 0 /* letter */ 974169689Skan}; 975169689Skan 976169689Skanstruct tree_opt_pass pass_dce_loop = 977169689Skan{ 978169689Skan "dceloop", /* name */ 979169689Skan gate_dce, /* gate */ 980169689Skan tree_ssa_dce_loop, /* execute */ 981169689Skan NULL, /* sub */ 982169689Skan NULL, /* next */ 983169689Skan 0, /* static_pass_number */ 984169689Skan TV_TREE_DCE, /* tv_id */ 985169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 986169689Skan 0, /* properties_provided */ 987169689Skan 0, /* properties_destroyed */ 988169689Skan 0, /* todo_flags_start */ 989169689Skan TODO_dump_func 990169689Skan | TODO_update_ssa 991169689Skan | TODO_cleanup_cfg 992169689Skan | TODO_verify_ssa, /* todo_flags_finish */ 993169689Skan 0 /* letter */ 994169689Skan}; 995169689Skan 996169689Skanstruct tree_opt_pass pass_cd_dce = 997169689Skan{ 998169689Skan "cddce", /* name */ 999169689Skan gate_dce, /* gate */ 1000169689Skan tree_ssa_cd_dce, /* execute */ 1001169689Skan NULL, /* sub */ 1002169689Skan NULL, /* next */ 1003169689Skan 0, /* static_pass_number */ 1004169689Skan TV_TREE_CD_DCE, /* tv_id */ 1005169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1006169689Skan 0, /* properties_provided */ 1007169689Skan 0, /* properties_destroyed */ 1008169689Skan 0, /* todo_flags_start */ 1009169689Skan TODO_dump_func 1010169689Skan | TODO_update_ssa 1011169689Skan | TODO_cleanup_cfg 1012169689Skan | TODO_ggc_collect 1013169689Skan | TODO_verify_ssa 1014169689Skan | TODO_verify_flow, /* todo_flags_finish */ 1015169689Skan 0 /* letter */ 1016169689Skan}; 1017