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