1/* Dead code elimination pass for the GNU compiler. 2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Ben Elliston <bje@redhat.com> 4 and Andrew MacLeod <amacleod@redhat.com> 5 Adapted to use control dependence by Steven Bosscher, SUSE Labs. 6 7This file is part of GCC. 8 9GCC is free software; you can redistribute it and/or modify it 10under the terms of the GNU General Public License as published by the 11Free Software Foundation; either version 2, or (at your option) any 12later version. 13 14GCC is distributed in the hope that it will be useful, but WITHOUT 15ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17for more details. 18 19You should have received a copy of the GNU General Public License 20along with GCC; see the file COPYING. If not, write to the Free 21Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2202110-1301, USA. */ 23 24/* Dead code elimination. 25 26 References: 27 28 Building an Optimizing Compiler, 29 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. 30 31 Advanced Compiler Design and Implementation, 32 Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10. 33 34 Dead-code elimination is the removal of statements which have no 35 impact on the program's output. "Dead statements" have no impact 36 on the program's output, while "necessary statements" may have 37 impact on the output. 38 39 The algorithm consists of three phases: 40 1. Marking as necessary all statements known to be necessary, 41 e.g. most function calls, writing a value to memory, etc; 42 2. Propagating necessary statements, e.g., the statements 43 giving values to operands in necessary statements; and 44 3. Removing dead statements. */ 45 46#include "config.h" 47#include "system.h" 48#include "coretypes.h" 49#include "tm.h" 50#include "ggc.h" 51 52/* These RTL headers are needed for basic-block.h. */ 53#include "rtl.h" 54#include "tm_p.h" 55#include "hard-reg-set.h" 56#include "obstack.h" 57#include "basic-block.h" 58 59#include "tree.h" 60#include "diagnostic.h" 61#include "tree-flow.h" 62#include "tree-gimple.h" 63#include "tree-dump.h" 64#include "tree-pass.h" 65#include "timevar.h" 66#include "flags.h" 67#include "cfgloop.h" 68#include "tree-scalar-evolution.h" 69 70static struct stmt_stats 71{ 72 int total; 73 int total_phis; 74 int removed; 75 int removed_phis; 76} stats; 77 78static VEC(tree,heap) *worklist; 79 80/* Vector indicating an SSA name has already been processed and marked 81 as necessary. */ 82static sbitmap processed; 83 84/* Vector indicating that last_stmt if a basic block has already been 85 marked as necessary. */ 86static sbitmap last_stmt_necessary; 87 88/* Before we can determine whether a control branch is dead, we need to 89 compute which blocks are control dependent on which edges. 90 91 We expect each block to be control dependent on very few edges so we 92 use a bitmap for each block recording its edges. An array holds the 93 bitmap. The Ith bit in the bitmap is set if that block is dependent 94 on the Ith edge. */ 95static bitmap *control_dependence_map; 96 97/* Vector indicating that a basic block has already had all the edges 98 processed that it is control dependent on. */ 99static sbitmap visited_control_parents; 100 101/* TRUE if this pass alters the CFG (by removing control statements). 102 FALSE otherwise. 103 104 If this pass alters the CFG, then it will arrange for the dominators 105 to be recomputed. */ 106static bool cfg_altered; 107 108/* Execute CODE for each edge (given number EDGE_NUMBER within the CODE) 109 for which the block with index N is control dependent. */ 110#define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE) \ 111 { \ 112 bitmap_iterator bi; \ 113 \ 114 EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[N], 0, EDGE_NUMBER, bi) \ 115 { \ 116 CODE; \ 117 } \ 118 } 119 120/* Local function prototypes. */ 121static inline void set_control_dependence_map_bit (basic_block, int); 122static inline void clear_control_dependence_bitmap (basic_block); 123static void find_all_control_dependences (struct edge_list *); 124static void find_control_dependence (struct edge_list *, int); 125static inline basic_block find_pdom (basic_block); 126 127static inline void mark_stmt_necessary (tree, bool); 128static inline void mark_operand_necessary (tree, bool); 129 130static void mark_stmt_if_obviously_necessary (tree, bool); 131static void find_obviously_necessary_stmts (struct edge_list *); 132 133static void mark_control_dependent_edges_necessary (basic_block, struct edge_list *); 134static void propagate_necessity (struct edge_list *); 135 136static void eliminate_unnecessary_stmts (void); 137static void remove_dead_phis (basic_block); 138static void remove_dead_stmt (block_stmt_iterator *, basic_block); 139 140static void print_stats (void); 141static void tree_dce_init (bool); 142static void tree_dce_done (bool); 143 144/* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */ 145static inline void 146set_control_dependence_map_bit (basic_block bb, int edge_index) 147{ 148 if (bb == ENTRY_BLOCK_PTR) 149 return; 150 gcc_assert (bb != EXIT_BLOCK_PTR); 151 bitmap_set_bit (control_dependence_map[bb->index], edge_index); 152} 153 154/* Clear all control dependences for block BB. */ 155static inline 156void clear_control_dependence_bitmap (basic_block bb) 157{ 158 bitmap_clear (control_dependence_map[bb->index]); 159} 160 161/* Record all blocks' control dependences on all edges in the edge 162 list EL, ala Morgan, Section 3.6. */ 163 164static void 165find_all_control_dependences (struct edge_list *el) 166{ 167 int i; 168 169 for (i = 0; i < NUM_EDGES (el); ++i) 170 find_control_dependence (el, i); 171} 172 173/* Determine all blocks' control dependences on the given edge with edge_list 174 EL index EDGE_INDEX, ala Morgan, Section 3.6. */ 175 176static void 177find_control_dependence (struct edge_list *el, int edge_index) 178{ 179 basic_block current_block; 180 basic_block ending_block; 181 182 gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR); 183 184 if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR) 185 ending_block = ENTRY_BLOCK_PTR->next_bb; 186 else 187 ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index)); 188 189 for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index); 190 current_block != ending_block && current_block != EXIT_BLOCK_PTR; 191 current_block = find_pdom (current_block)) 192 { 193 edge e = INDEX_EDGE (el, edge_index); 194 195 /* For abnormal edges, we don't make current_block control 196 dependent because instructions that throw are always necessary 197 anyway. */ 198 if (e->flags & EDGE_ABNORMAL) 199 continue; 200 201 set_control_dependence_map_bit (current_block, edge_index); 202 } 203} 204 205/* Find the immediate postdominator PDOM of the specified basic block BLOCK. 206 This function is necessary because some blocks have negative numbers. */ 207 208static inline basic_block 209find_pdom (basic_block block) 210{ 211 gcc_assert (block != ENTRY_BLOCK_PTR); 212 213 if (block == EXIT_BLOCK_PTR) 214 return EXIT_BLOCK_PTR; 215 else 216 { 217 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block); 218 if (! bb) 219 return EXIT_BLOCK_PTR; 220 return bb; 221 } 222} 223 224#define NECESSARY(stmt) stmt->common.asm_written_flag 225 226/* If STMT is not already marked necessary, mark it, and add it to the 227 worklist if ADD_TO_WORKLIST is true. */ 228static inline void 229mark_stmt_necessary (tree stmt, bool add_to_worklist) 230{ 231 gcc_assert (stmt); 232 gcc_assert (!DECL_P (stmt)); 233 234 if (NECESSARY (stmt)) 235 return; 236 237 if (dump_file && (dump_flags & TDF_DETAILS)) 238 { 239 fprintf (dump_file, "Marking useful stmt: "); 240 print_generic_stmt (dump_file, stmt, TDF_SLIM); 241 fprintf (dump_file, "\n"); 242 } 243 244 NECESSARY (stmt) = 1; 245 if (add_to_worklist) 246 VEC_safe_push (tree, heap, worklist, stmt); 247} 248 249/* Mark the statement defining operand OP as necessary. PHIONLY is true 250 if we should only mark it necessary if it is a phi node. */ 251 252static inline void 253mark_operand_necessary (tree op, bool phionly) 254{ 255 tree stmt; 256 int ver; 257 258 gcc_assert (op); 259 260 ver = SSA_NAME_VERSION (op); 261 if (TEST_BIT (processed, ver)) 262 return; 263 SET_BIT (processed, ver); 264 265 stmt = SSA_NAME_DEF_STMT (op); 266 gcc_assert (stmt); 267 268 if (NECESSARY (stmt) 269 || IS_EMPTY_STMT (stmt) 270 || (phionly && TREE_CODE (stmt) != PHI_NODE)) 271 return; 272 273 NECESSARY (stmt) = 1; 274 VEC_safe_push (tree, heap, worklist, stmt); 275} 276 277 278/* Mark STMT as necessary if it obviously is. Add it to the worklist if 279 it can make other statements necessary. 280 281 If AGGRESSIVE is false, control statements are conservatively marked as 282 necessary. */ 283 284static void 285mark_stmt_if_obviously_necessary (tree stmt, bool aggressive) 286{ 287 stmt_ann_t ann; 288 tree op, def; 289 ssa_op_iter iter; 290 291 /* With non-call exceptions, we have to assume that all statements could 292 throw. If a statement may throw, it is inherently necessary. */ 293 if (flag_non_call_exceptions 294 && tree_could_throw_p (stmt)) 295 { 296 mark_stmt_necessary (stmt, true); 297 return; 298 } 299 300 /* Statements that are implicitly live. Most function calls, asm and return 301 statements are required. Labels and BIND_EXPR nodes are kept because 302 they are control flow, and we have no way of knowing whether they can be 303 removed. DCE can eliminate all the other statements in a block, and CFG 304 can then remove the block and labels. */ 305 switch (TREE_CODE (stmt)) 306 { 307 case BIND_EXPR: 308 case LABEL_EXPR: 309 case CASE_LABEL_EXPR: 310 mark_stmt_necessary (stmt, false); 311 return; 312 313 case ASM_EXPR: 314 case RESX_EXPR: 315 case RETURN_EXPR: 316 mark_stmt_necessary (stmt, true); 317 return; 318 319 case CALL_EXPR: 320 /* Most, but not all function calls are required. Function calls that 321 produce no result and have no side effects (i.e. const pure 322 functions) are unnecessary. */ 323 if (TREE_SIDE_EFFECTS (stmt)) 324 mark_stmt_necessary (stmt, true); 325 return; 326 327 case MODIFY_EXPR: 328 op = get_call_expr_in (stmt); 329 if (op && TREE_SIDE_EFFECTS (op)) 330 { 331 mark_stmt_necessary (stmt, true); 332 return; 333 } 334 335 /* These values are mildly magic bits of the EH runtime. We can't 336 see the entire lifetime of these values until landing pads are 337 generated. */ 338 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == EXC_PTR_EXPR 339 || TREE_CODE (TREE_OPERAND (stmt, 0)) == FILTER_EXPR) 340 { 341 mark_stmt_necessary (stmt, true); 342 return; 343 } 344 break; 345 346 case GOTO_EXPR: 347 gcc_assert (!simple_goto_p (stmt)); 348 mark_stmt_necessary (stmt, true); 349 return; 350 351 case COND_EXPR: 352 gcc_assert (EDGE_COUNT (bb_for_stmt (stmt)->succs) == 2); 353 /* Fall through. */ 354 355 case SWITCH_EXPR: 356 if (! aggressive) 357 mark_stmt_necessary (stmt, true); 358 break; 359 360 default: 361 break; 362 } 363 364 ann = stmt_ann (stmt); 365 366 /* If the statement has volatile operands, it needs to be preserved. 367 Same for statements that can alter control flow in unpredictable 368 ways. */ 369 if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt)) 370 { 371 mark_stmt_necessary (stmt, true); 372 return; 373 } 374 375 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 376 { 377 if (is_global_var (SSA_NAME_VAR (def))) 378 { 379 mark_stmt_necessary (stmt, true); 380 return; 381 } 382 } 383 if (is_hidden_global_store (stmt)) 384 { 385 mark_stmt_necessary (stmt, true); 386 return; 387 } 388 389 return; 390} 391 392/* Find obviously necessary statements. These are things like most function 393 calls, and stores to file level variables. 394 395 If EL is NULL, control statements are conservatively marked as 396 necessary. Otherwise it contains the list of edges used by control 397 dependence analysis. */ 398 399static void 400find_obviously_necessary_stmts (struct edge_list *el) 401{ 402 basic_block bb; 403 block_stmt_iterator i; 404 edge e; 405 406 FOR_EACH_BB (bb) 407 { 408 tree phi; 409 410 /* Check any PHI nodes in the block. */ 411 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 412 { 413 NECESSARY (phi) = 0; 414 415 /* PHIs for virtual variables do not directly affect code 416 generation and need not be considered inherently necessary 417 regardless of the bits set in their decl. 418 419 Thus, we only need to mark PHIs for real variables which 420 need their result preserved as being inherently necessary. */ 421 if (is_gimple_reg (PHI_RESULT (phi)) 422 && is_global_var (SSA_NAME_VAR (PHI_RESULT (phi)))) 423 mark_stmt_necessary (phi, true); 424 } 425 426 /* Check all statements in the block. */ 427 for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i)) 428 { 429 tree stmt = bsi_stmt (i); 430 NECESSARY (stmt) = 0; 431 mark_stmt_if_obviously_necessary (stmt, el != NULL); 432 } 433 } 434 435 if (el) 436 { 437 /* Prevent the loops from being removed. We must keep the infinite loops, 438 and we currently do not have a means to recognize the finite ones. */ 439 FOR_EACH_BB (bb) 440 { 441 edge_iterator ei; 442 FOR_EACH_EDGE (e, ei, bb->succs) 443 if (e->flags & EDGE_DFS_BACK) 444 mark_control_dependent_edges_necessary (e->dest, el); 445 } 446 } 447} 448 449/* Make corresponding control dependent edges necessary. We only 450 have to do this once for each basic block, so we clear the bitmap 451 after we're done. */ 452static void 453mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) 454{ 455 unsigned edge_number; 456 457 gcc_assert (bb != EXIT_BLOCK_PTR); 458 459 if (bb == ENTRY_BLOCK_PTR) 460 return; 461 462 EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number, 463 { 464 tree t; 465 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); 466 467 if (TEST_BIT (last_stmt_necessary, cd_bb->index)) 468 continue; 469 SET_BIT (last_stmt_necessary, cd_bb->index); 470 471 t = last_stmt (cd_bb); 472 if (t && is_ctrl_stmt (t)) 473 mark_stmt_necessary (t, true); 474 }); 475} 476 477/* Propagate necessity using the operands of necessary statements. Process 478 the uses on each statement in the worklist, and add all feeding statements 479 which contribute to the calculation of this value to the worklist. 480 481 In conservative mode, EL is NULL. */ 482 483static void 484propagate_necessity (struct edge_list *el) 485{ 486 tree i; 487 bool aggressive = (el ? true : false); 488 489 if (dump_file && (dump_flags & TDF_DETAILS)) 490 fprintf (dump_file, "\nProcessing worklist:\n"); 491 492 while (VEC_length (tree, worklist) > 0) 493 { 494 /* Take `i' from worklist. */ 495 i = VEC_pop (tree, worklist); 496 497 if (dump_file && (dump_flags & TDF_DETAILS)) 498 { 499 fprintf (dump_file, "processing: "); 500 print_generic_stmt (dump_file, i, TDF_SLIM); 501 fprintf (dump_file, "\n"); 502 } 503 504 if (aggressive) 505 { 506 /* Mark the last statements of the basic blocks that the block 507 containing `i' is control dependent on, but only if we haven't 508 already done so. */ 509 basic_block bb = bb_for_stmt (i); 510 if (bb != ENTRY_BLOCK_PTR 511 && ! TEST_BIT (visited_control_parents, bb->index)) 512 { 513 SET_BIT (visited_control_parents, bb->index); 514 mark_control_dependent_edges_necessary (bb, el); 515 } 516 } 517 518 if (TREE_CODE (i) == PHI_NODE) 519 { 520 /* PHI nodes are somewhat special in that each PHI alternative has 521 data and control dependencies. All the statements feeding the 522 PHI node's arguments are always necessary. In aggressive mode, 523 we also consider the control dependent edges leading to the 524 predecessor block associated with each PHI alternative as 525 necessary. */ 526 int k; 527 for (k = 0; k < PHI_NUM_ARGS (i); k++) 528 { 529 tree arg = PHI_ARG_DEF (i, k); 530 if (TREE_CODE (arg) == SSA_NAME) 531 mark_operand_necessary (arg, false); 532 } 533 534 if (aggressive) 535 { 536 for (k = 0; k < PHI_NUM_ARGS (i); k++) 537 { 538 basic_block arg_bb = PHI_ARG_EDGE (i, k)->src; 539 if (arg_bb != ENTRY_BLOCK_PTR 540 && ! TEST_BIT (visited_control_parents, arg_bb->index)) 541 { 542 SET_BIT (visited_control_parents, arg_bb->index); 543 mark_control_dependent_edges_necessary (arg_bb, el); 544 } 545 } 546 } 547 } 548 else 549 { 550 /* Propagate through the operands. Examine all the USE, VUSE and 551 V_MAY_DEF operands in this statement. Mark all the statements 552 which feed this statement's uses as necessary. */ 553 ssa_op_iter iter; 554 tree use; 555 556 /* The operands of V_MAY_DEF expressions are also needed as they 557 represent potential definitions that may reach this 558 statement (V_MAY_DEF operands allow us to follow def-def 559 links). */ 560 561 FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES) 562 mark_operand_necessary (use, false); 563 } 564 } 565} 566 567 568/* Propagate necessity around virtual phi nodes used in kill operands. 569 The reason this isn't done during propagate_necessity is because we don't 570 want to keep phis around that are just there for must-defs, unless we 571 absolutely have to. After we've rewritten the reaching definitions to be 572 correct in the previous part of the fixup routine, we can simply propagate 573 around the information about which of these virtual phi nodes are really 574 used, and set the NECESSARY flag accordingly. 575 Note that we do the minimum here to ensure that we keep alive the phis that 576 are actually used in the corrected SSA form. In particular, some of these 577 phis may now have all of the same operand, and will be deleted by some 578 other pass. */ 579 580static void 581mark_really_necessary_kill_operand_phis (void) 582{ 583 basic_block bb; 584 int i; 585 586 /* Seed the worklist with the new virtual phi arguments and virtual 587 uses */ 588 FOR_EACH_BB (bb) 589 { 590 block_stmt_iterator bsi; 591 tree phi; 592 593 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 594 { 595 if (!is_gimple_reg (PHI_RESULT (phi)) && NECESSARY (phi)) 596 { 597 for (i = 0; i < PHI_NUM_ARGS (phi); i++) 598 mark_operand_necessary (PHI_ARG_DEF (phi, i), true); 599 } 600 } 601 602 for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi)) 603 { 604 tree stmt = bsi_stmt (bsi); 605 606 if (NECESSARY (stmt)) 607 { 608 use_operand_p use_p; 609 ssa_op_iter iter; 610 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 611 SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS) 612 { 613 tree use = USE_FROM_PTR (use_p); 614 mark_operand_necessary (use, true); 615 } 616 } 617 } 618 } 619 620 /* Mark all virtual phis still in use as necessary, and all of their 621 arguments that are phis as necessary. */ 622 while (VEC_length (tree, worklist) > 0) 623 { 624 tree use = VEC_pop (tree, worklist); 625 626 for (i = 0; i < PHI_NUM_ARGS (use); i++) 627 mark_operand_necessary (PHI_ARG_DEF (use, i), true); 628 } 629} 630 631 632 633 634/* Eliminate unnecessary statements. Any instruction not marked as necessary 635 contributes nothing to the program, and can be deleted. */ 636 637static void 638eliminate_unnecessary_stmts (void) 639{ 640 basic_block bb; 641 block_stmt_iterator i; 642 643 if (dump_file && (dump_flags & TDF_DETAILS)) 644 fprintf (dump_file, "\nEliminating unnecessary statements:\n"); 645 646 clear_special_calls (); 647 FOR_EACH_BB (bb) 648 { 649 /* Remove dead PHI nodes. */ 650 remove_dead_phis (bb); 651 } 652 653 FOR_EACH_BB (bb) 654 { 655 /* Remove dead statements. */ 656 for (i = bsi_start (bb); ! bsi_end_p (i) ; ) 657 { 658 tree t = bsi_stmt (i); 659 660 stats.total++; 661 662 /* If `i' is not necessary then remove it. */ 663 if (! NECESSARY (t)) 664 remove_dead_stmt (&i, bb); 665 else 666 { 667 tree call = get_call_expr_in (t); 668 if (call) 669 notice_special_calls (call); 670 bsi_next (&i); 671 } 672 } 673 } 674 } 675 676/* Remove dead PHI nodes from block BB. */ 677 678static void 679remove_dead_phis (basic_block bb) 680{ 681 tree prev, phi; 682 683 prev = NULL_TREE; 684 phi = phi_nodes (bb); 685 while (phi) 686 { 687 stats.total_phis++; 688 689 if (! NECESSARY (phi)) 690 { 691 tree next = PHI_CHAIN (phi); 692 693 if (dump_file && (dump_flags & TDF_DETAILS)) 694 { 695 fprintf (dump_file, "Deleting : "); 696 print_generic_stmt (dump_file, phi, TDF_SLIM); 697 fprintf (dump_file, "\n"); 698 } 699 700 remove_phi_node (phi, prev); 701 stats.removed_phis++; 702 phi = next; 703 } 704 else 705 { 706 prev = phi; 707 phi = PHI_CHAIN (phi); 708 } 709 } 710} 711 712/* Remove dead statement pointed to by iterator I. Receives the basic block BB 713 containing I so that we don't have to look it up. */ 714 715static void 716remove_dead_stmt (block_stmt_iterator *i, basic_block bb) 717{ 718 tree t = bsi_stmt (*i); 719 def_operand_p def_p; 720 721 ssa_op_iter iter; 722 723 if (dump_file && (dump_flags & TDF_DETAILS)) 724 { 725 fprintf (dump_file, "Deleting : "); 726 print_generic_stmt (dump_file, t, TDF_SLIM); 727 fprintf (dump_file, "\n"); 728 } 729 730 stats.removed++; 731 732 /* If we have determined that a conditional branch statement contributes 733 nothing to the program, then we not only remove it, but we also change 734 the flow graph so that the current block will simply fall-thru to its 735 immediate post-dominator. The blocks we are circumventing will be 736 removed by cleaup_tree_cfg if this change in the flow graph makes them 737 unreachable. */ 738 if (is_ctrl_stmt (t)) 739 { 740 basic_block post_dom_bb; 741 742 /* The post dominance info has to be up-to-date. */ 743 gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK); 744 /* Get the immediate post dominator of bb. */ 745 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); 746 /* Some blocks don't have an immediate post dominator. This can happen 747 for example with infinite loops. Removing an infinite loop is an 748 inappropriate transformation anyway... */ 749 if (! post_dom_bb) 750 { 751 bsi_next (i); 752 return; 753 } 754 755 /* If the post dominator block has PHI nodes, we might be unable 756 to compute the right PHI args for them. Since the control 757 statement is unnecessary, all edges can be regarded as 758 equivalent, but we have to get rid of the condition, since it 759 might reference a variable that was determined to be 760 unnecessary and thus removed. */ 761 if (phi_nodes (post_dom_bb)) 762 post_dom_bb = EDGE_SUCC (bb, 0)->dest; 763 else 764 { 765 /* Redirect the first edge out of BB to reach POST_DOM_BB. */ 766 redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb); 767 PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL; 768 } 769 EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; 770 EDGE_SUCC (bb, 0)->count = bb->count; 771 772 /* The edge is no longer associated with a conditional, so it does 773 not have TRUE/FALSE flags. */ 774 EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 775 776 /* If the edge reaches any block other than the exit, then it is a 777 fallthru edge; if it reaches the exit, then it is not a fallthru 778 edge. */ 779 if (post_dom_bb != EXIT_BLOCK_PTR) 780 EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU; 781 else 782 EDGE_SUCC (bb, 0)->flags &= ~EDGE_FALLTHRU; 783 784 /* Remove the remaining the outgoing edges. */ 785 while (!single_succ_p (bb)) 786 { 787 /* FIXME. When we remove the edge, we modify the CFG, which 788 in turn modifies the dominator and post-dominator tree. 789 Is it safe to postpone recomputing the dominator and 790 post-dominator tree until the end of this pass given that 791 the post-dominators are used above? */ 792 cfg_altered = true; 793 remove_edge (EDGE_SUCC (bb, 1)); 794 } 795 } 796 797 FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter, SSA_OP_VIRTUAL_DEFS) 798 { 799 tree def = DEF_FROM_PTR (def_p); 800 mark_sym_for_renaming (SSA_NAME_VAR (def)); 801 } 802 bsi_remove (i); 803 release_defs (t); 804} 805 806/* Print out removed statement statistics. */ 807 808static void 809print_stats (void) 810{ 811 if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS))) 812 { 813 float percg; 814 815 percg = ((float) stats.removed / (float) stats.total) * 100; 816 fprintf (dump_file, "Removed %d of %d statements (%d%%)\n", 817 stats.removed, stats.total, (int) percg); 818 819 if (stats.total_phis == 0) 820 percg = 0; 821 else 822 percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100; 823 824 fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n", 825 stats.removed_phis, stats.total_phis, (int) percg); 826 } 827} 828 829/* Initialization for this pass. Set up the used data structures. */ 830 831static void 832tree_dce_init (bool aggressive) 833{ 834 memset ((void *) &stats, 0, sizeof (stats)); 835 836 if (aggressive) 837 { 838 int i; 839 840 control_dependence_map 841 = xmalloc (last_basic_block * sizeof (bitmap)); 842 for (i = 0; i < last_basic_block; ++i) 843 control_dependence_map[i] = BITMAP_ALLOC (NULL); 844 845 last_stmt_necessary = sbitmap_alloc (last_basic_block); 846 sbitmap_zero (last_stmt_necessary); 847 } 848 849 processed = sbitmap_alloc (num_ssa_names + 1); 850 sbitmap_zero (processed); 851 852 worklist = VEC_alloc (tree, heap, 64); 853 cfg_altered = false; 854} 855 856/* Cleanup after this pass. */ 857 858static void 859tree_dce_done (bool aggressive) 860{ 861 if (aggressive) 862 { 863 int i; 864 865 for (i = 0; i < last_basic_block; ++i) 866 BITMAP_FREE (control_dependence_map[i]); 867 free (control_dependence_map); 868 869 sbitmap_free (visited_control_parents); 870 sbitmap_free (last_stmt_necessary); 871 } 872 873 sbitmap_free (processed); 874 875 VEC_free (tree, heap, worklist); 876} 877 878/* Main routine to eliminate dead code. 879 880 AGGRESSIVE controls the aggressiveness of the algorithm. 881 In conservative mode, we ignore control dependence and simply declare 882 all but the most trivially dead branches necessary. This mode is fast. 883 In aggressive mode, control dependences are taken into account, which 884 results in more dead code elimination, but at the cost of some time. 885 886 FIXME: Aggressive mode before PRE doesn't work currently because 887 the dominance info is not invalidated after DCE1. This is 888 not an issue right now because we only run aggressive DCE 889 as the last tree SSA pass, but keep this in mind when you 890 start experimenting with pass ordering. */ 891 892static void 893perform_tree_ssa_dce (bool aggressive) 894{ 895 struct edge_list *el = NULL; 896 897 tree_dce_init (aggressive); 898 899 if (aggressive) 900 { 901 /* Compute control dependence. */ 902 timevar_push (TV_CONTROL_DEPENDENCES); 903 calculate_dominance_info (CDI_POST_DOMINATORS); 904 el = create_edge_list (); 905 find_all_control_dependences (el); 906 timevar_pop (TV_CONTROL_DEPENDENCES); 907 908 visited_control_parents = sbitmap_alloc (last_basic_block); 909 sbitmap_zero (visited_control_parents); 910 911 mark_dfs_back_edges (); 912 } 913 914 find_obviously_necessary_stmts (el); 915 916 propagate_necessity (el); 917 918 mark_really_necessary_kill_operand_phis (); 919 eliminate_unnecessary_stmts (); 920 921 if (aggressive) 922 free_dominance_info (CDI_POST_DOMINATORS); 923 924 /* If we removed paths in the CFG, then we need to update 925 dominators as well. I haven't investigated the possibility 926 of incrementally updating dominators. */ 927 if (cfg_altered) 928 free_dominance_info (CDI_DOMINATORS); 929 930 /* Debugging dumps. */ 931 if (dump_file) 932 print_stats (); 933 934 tree_dce_done (aggressive); 935 936 free_edge_list (el); 937} 938 939/* Pass entry points. */ 940static void 941tree_ssa_dce (void) 942{ 943 perform_tree_ssa_dce (/*aggressive=*/false); 944} 945 946static void 947tree_ssa_dce_loop (void) 948{ 949 perform_tree_ssa_dce (/*aggressive=*/false); 950 free_numbers_of_iterations_estimates (current_loops); 951 scev_reset (); 952} 953 954static void 955tree_ssa_cd_dce (void) 956{ 957 perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); 958} 959 960static bool 961gate_dce (void) 962{ 963 return flag_tree_dce != 0; 964} 965 966struct tree_opt_pass pass_dce = 967{ 968 "dce", /* name */ 969 gate_dce, /* gate */ 970 tree_ssa_dce, /* execute */ 971 NULL, /* sub */ 972 NULL, /* next */ 973 0, /* static_pass_number */ 974 TV_TREE_DCE, /* tv_id */ 975 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 976 0, /* properties_provided */ 977 0, /* properties_destroyed */ 978 0, /* todo_flags_start */ 979 TODO_dump_func 980 | TODO_update_ssa 981 | TODO_cleanup_cfg 982 | TODO_ggc_collect 983 | TODO_verify_ssa, /* todo_flags_finish */ 984 0 /* letter */ 985}; 986 987struct tree_opt_pass pass_dce_loop = 988{ 989 "dceloop", /* name */ 990 gate_dce, /* gate */ 991 tree_ssa_dce_loop, /* execute */ 992 NULL, /* sub */ 993 NULL, /* next */ 994 0, /* static_pass_number */ 995 TV_TREE_DCE, /* tv_id */ 996 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 997 0, /* properties_provided */ 998 0, /* properties_destroyed */ 999 0, /* todo_flags_start */ 1000 TODO_dump_func 1001 | TODO_update_ssa 1002 | TODO_cleanup_cfg 1003 | TODO_verify_ssa, /* todo_flags_finish */ 1004 0 /* letter */ 1005}; 1006 1007struct tree_opt_pass pass_cd_dce = 1008{ 1009 "cddce", /* name */ 1010 gate_dce, /* gate */ 1011 tree_ssa_cd_dce, /* execute */ 1012 NULL, /* sub */ 1013 NULL, /* next */ 1014 0, /* static_pass_number */ 1015 TV_TREE_CD_DCE, /* tv_id */ 1016 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 1017 0, /* properties_provided */ 1018 0, /* properties_destroyed */ 1019 0, /* todo_flags_start */ 1020 TODO_dump_func 1021 | TODO_update_ssa 1022 | TODO_cleanup_cfg 1023 | TODO_ggc_collect 1024 | TODO_verify_ssa 1025 | TODO_verify_flow, /* todo_flags_finish */ 1026 0 /* letter */ 1027}; 1028