1/* Dead code elimination pass for the GNU compiler. 2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 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 3, 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 COPYING3. If not see 22<http://www.gnu.org/licenses/>. */ 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 "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 78#define STMT_NECESSARY GF_PLF_1 79 80static VEC(gimple,heap) *worklist; 81 82/* Vector indicating an SSA name has already been processed and marked 83 as necessary. */ 84static sbitmap processed; 85 86/* Vector indicating that last_stmt if a basic block has already been 87 marked as necessary. */ 88static sbitmap last_stmt_necessary; 89 90/* Vector indicating that BB contains statements that are live. */ 91static sbitmap bb_contains_live_stmts; 92 93/* Before we can determine whether a control branch is dead, we need to 94 compute which blocks are control dependent on which edges. 95 96 We expect each block to be control dependent on very few edges so we 97 use a bitmap for each block recording its edges. An array holds the 98 bitmap. The Ith bit in the bitmap is set if that block is dependent 99 on the Ith edge. */ 100static bitmap *control_dependence_map; 101 102/* Vector indicating that a basic block has already had all the edges 103 processed that it is control dependent on. */ 104static sbitmap visited_control_parents; 105 106/* TRUE if this pass alters the CFG (by removing control statements). 107 FALSE otherwise. 108 109 If this pass alters the CFG, then it will arrange for the dominators 110 to be recomputed. */ 111static bool cfg_altered; 112 113/* Execute code that follows the macro for each edge (given number 114 EDGE_NUMBER within the CODE) for which the block with index N is 115 control dependent. */ 116#define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \ 117 EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \ 118 (EDGE_NUMBER), (BI)) 119 120 121/* Indicate block BB is control dependent on an edge with index EDGE_INDEX. */ 122static inline void 123set_control_dependence_map_bit (basic_block bb, int edge_index) 124{ 125 if (bb == ENTRY_BLOCK_PTR) 126 return; 127 gcc_assert (bb != EXIT_BLOCK_PTR); 128 bitmap_set_bit (control_dependence_map[bb->index], edge_index); 129} 130 131/* Clear all control dependences for block BB. */ 132static inline void 133clear_control_dependence_bitmap (basic_block bb) 134{ 135 bitmap_clear (control_dependence_map[bb->index]); 136} 137 138 139/* Find the immediate postdominator PDOM of the specified basic block BLOCK. 140 This function is necessary because some blocks have negative numbers. */ 141 142static inline basic_block 143find_pdom (basic_block block) 144{ 145 gcc_assert (block != ENTRY_BLOCK_PTR); 146 147 if (block == EXIT_BLOCK_PTR) 148 return EXIT_BLOCK_PTR; 149 else 150 { 151 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block); 152 if (! bb) 153 return EXIT_BLOCK_PTR; 154 return bb; 155 } 156} 157 158 159/* Determine all blocks' control dependences on the given edge with edge_list 160 EL index EDGE_INDEX, ala Morgan, Section 3.6. */ 161 162static void 163find_control_dependence (struct edge_list *el, int edge_index) 164{ 165 basic_block current_block; 166 basic_block ending_block; 167 168 gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR); 169 170 if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR) 171 ending_block = single_succ (ENTRY_BLOCK_PTR); 172 else 173 ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index)); 174 175 for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index); 176 current_block != ending_block && current_block != EXIT_BLOCK_PTR; 177 current_block = find_pdom (current_block)) 178 { 179 edge e = INDEX_EDGE (el, edge_index); 180 181 /* For abnormal edges, we don't make current_block control 182 dependent because instructions that throw are always necessary 183 anyway. */ 184 if (e->flags & EDGE_ABNORMAL) 185 continue; 186 187 set_control_dependence_map_bit (current_block, edge_index); 188 } 189} 190 191 192/* Record all blocks' control dependences on all edges in the edge 193 list EL, ala Morgan, Section 3.6. */ 194 195static void 196find_all_control_dependences (struct edge_list *el) 197{ 198 int i; 199 200 for (i = 0; i < NUM_EDGES (el); ++i) 201 find_control_dependence (el, i); 202} 203 204/* If STMT is not already marked necessary, mark it, and add it to the 205 worklist if ADD_TO_WORKLIST is true. */ 206static inline void 207mark_stmt_necessary (gimple stmt, bool add_to_worklist) 208{ 209 gcc_assert (stmt); 210 211 if (gimple_plf (stmt, STMT_NECESSARY)) 212 return; 213 214 if (dump_file && (dump_flags & TDF_DETAILS)) 215 { 216 fprintf (dump_file, "Marking useful stmt: "); 217 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 218 fprintf (dump_file, "\n"); 219 } 220 221 gimple_set_plf (stmt, STMT_NECESSARY, true); 222 if (add_to_worklist) 223 VEC_safe_push (gimple, heap, worklist, stmt); 224 if (bb_contains_live_stmts && !is_gimple_debug (stmt)) 225 SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index); 226} 227 228 229/* Mark the statement defining operand OP as necessary. */ 230 231static inline void 232mark_operand_necessary (tree op) 233{ 234 gimple stmt; 235 int ver; 236 237 gcc_assert (op); 238 239 ver = SSA_NAME_VERSION (op); 240 if (TEST_BIT (processed, ver)) 241 { 242 stmt = SSA_NAME_DEF_STMT (op); 243 gcc_assert (gimple_nop_p (stmt) 244 || gimple_plf (stmt, STMT_NECESSARY)); 245 return; 246 } 247 SET_BIT (processed, ver); 248 249 stmt = SSA_NAME_DEF_STMT (op); 250 gcc_assert (stmt); 251 252 if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt)) 253 return; 254 255 if (dump_file && (dump_flags & TDF_DETAILS)) 256 { 257 fprintf (dump_file, "marking necessary through "); 258 print_generic_expr (dump_file, op, 0); 259 fprintf (dump_file, " stmt "); 260 print_gimple_stmt (dump_file, stmt, 0, 0); 261 } 262 263 gimple_set_plf (stmt, STMT_NECESSARY, true); 264 if (bb_contains_live_stmts) 265 SET_BIT (bb_contains_live_stmts, gimple_bb (stmt)->index); 266 VEC_safe_push (gimple, heap, worklist, stmt); 267} 268 269 270/* Mark STMT as necessary if it obviously is. Add it to the worklist if 271 it can make other statements necessary. 272 273 If AGGRESSIVE is false, control statements are conservatively marked as 274 necessary. */ 275 276static void 277mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive) 278{ 279 tree lhs = NULL_TREE; 280 /* With non-call exceptions, we have to assume that all statements could 281 throw. If a statement may throw, it is inherently necessary. */ 282 if (flag_non_call_exceptions 283 && stmt_could_throw_p (stmt)) 284 { 285 mark_stmt_necessary (stmt, true); 286 return; 287 } 288 289 /* Statements that are implicitly live. Most function calls, asm 290 and return statements are required. Labels and GIMPLE_BIND nodes 291 are kept because they are control flow, and we have no way of 292 knowing whether they can be removed. DCE can eliminate all the 293 other statements in a block, and CFG can then remove the block 294 and labels. */ 295 switch (gimple_code (stmt)) 296 { 297 case GIMPLE_PREDICT: 298 case GIMPLE_LABEL: 299 mark_stmt_necessary (stmt, false); 300 return; 301 302 case GIMPLE_ASM: 303 case GIMPLE_RESX: 304 case GIMPLE_RETURN: 305 mark_stmt_necessary (stmt, true); 306 return; 307 308 case GIMPLE_CALL: 309 /* Most, but not all function calls are required. Function calls that 310 produce no result and have no side effects (i.e. const pure 311 functions) are unnecessary. */ 312 if (gimple_has_side_effects (stmt)) 313 { 314 mark_stmt_necessary (stmt, true); 315 return; 316 } 317 if (!gimple_call_lhs (stmt)) 318 return; 319 lhs = gimple_call_lhs (stmt); 320 /* Fall through */ 321 322 case GIMPLE_ASSIGN: 323 if (!lhs) 324 lhs = gimple_assign_lhs (stmt); 325 break; 326 327 case GIMPLE_DEBUG: 328 /* Debug temps without a value are not useful. ??? If we could 329 easily locate the debug temp bind stmt for a use thereof, 330 would could refrain from marking all debug temps here, and 331 mark them only if they're used. */ 332 if (gimple_debug_bind_has_value_p (stmt) 333 || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL) 334 mark_stmt_necessary (stmt, false); 335 return; 336 337 case GIMPLE_GOTO: 338 gcc_assert (!simple_goto_p (stmt)); 339 mark_stmt_necessary (stmt, true); 340 return; 341 342 case GIMPLE_COND: 343 gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2); 344 /* Fall through. */ 345 346 case GIMPLE_SWITCH: 347 if (! aggressive) 348 mark_stmt_necessary (stmt, true); 349 break; 350 351 default: 352 break; 353 } 354 355 /* If the statement has volatile operands, it needs to be preserved. 356 Same for statements that can alter control flow in unpredictable 357 ways. */ 358 if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt)) 359 { 360 mark_stmt_necessary (stmt, true); 361 return; 362 } 363 364 if (is_hidden_global_store (stmt)) 365 { 366 mark_stmt_necessary (stmt, true); 367 return; 368 } 369 370 return; 371} 372 373 374/* Make corresponding control dependent edges necessary. We only 375 have to do this once for each basic block, so we clear the bitmap 376 after we're done. */ 377static void 378mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) 379{ 380 bitmap_iterator bi; 381 unsigned edge_number; 382 383 gcc_assert (bb != EXIT_BLOCK_PTR); 384 385 if (bb == ENTRY_BLOCK_PTR) 386 return; 387 388 EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number) 389 { 390 gimple stmt; 391 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); 392 393 if (TEST_BIT (last_stmt_necessary, cd_bb->index)) 394 continue; 395 SET_BIT (last_stmt_necessary, cd_bb->index); 396 SET_BIT (bb_contains_live_stmts, cd_bb->index); 397 398 stmt = last_stmt (cd_bb); 399 if (stmt && is_ctrl_stmt (stmt)) 400 mark_stmt_necessary (stmt, true); 401 } 402} 403 404 405/* Find obviously necessary statements. These are things like most function 406 calls, and stores to file level variables. 407 408 If EL is NULL, control statements are conservatively marked as 409 necessary. Otherwise it contains the list of edges used by control 410 dependence analysis. */ 411 412static void 413find_obviously_necessary_stmts (struct edge_list *el) 414{ 415 basic_block bb; 416 gimple_stmt_iterator gsi; 417 edge e; 418 gimple phi, stmt; 419 420 FOR_EACH_BB (bb) 421 { 422 /* PHI nodes are never inherently necessary. */ 423 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 424 { 425 phi = gsi_stmt (gsi); 426 gimple_set_plf (phi, STMT_NECESSARY, false); 427 } 428 429 /* Check all statements in the block. */ 430 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 431 { 432 stmt = gsi_stmt (gsi); 433 gimple_set_plf (stmt, STMT_NECESSARY, false); 434 mark_stmt_if_obviously_necessary (stmt, el != NULL); 435 } 436 } 437 438 /* Pure and const functions are finite and thus have no infinite loops in 439 them. */ 440 if ((TREE_READONLY (current_function_decl) 441 || DECL_PURE_P (current_function_decl)) 442 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)) 443 return; 444 445 /* Prevent the empty possibly infinite loops from being removed. */ 446 if (el) 447 { 448 loop_iterator li; 449 struct loop *loop; 450 scev_initialize (); 451 if (mark_irreducible_loops ()) 452 FOR_EACH_BB (bb) 453 { 454 edge_iterator ei; 455 FOR_EACH_EDGE (e, ei, bb->succs) 456 if ((e->flags & EDGE_DFS_BACK) 457 && (e->flags & EDGE_IRREDUCIBLE_LOOP)) 458 { 459 if (dump_file) 460 fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n", 461 e->src->index, e->dest->index); 462 mark_control_dependent_edges_necessary (e->dest, el); 463 } 464 } 465 466 FOR_EACH_LOOP (li, loop, 0) 467 if (!finite_loop_p (loop)) 468 { 469 if (dump_file) 470 fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num); 471 mark_control_dependent_edges_necessary (loop->latch, el); 472 } 473 scev_finalize (); 474 } 475} 476 477 478/* Return true if REF is based on an aliased base, otherwise false. */ 479 480static bool 481ref_may_be_aliased (tree ref) 482{ 483 while (handled_component_p (ref)) 484 ref = TREE_OPERAND (ref, 0); 485 return !(DECL_P (ref) 486 && !may_be_aliased (ref)); 487} 488 489static bitmap visited = NULL; 490static unsigned int longest_chain = 0; 491static unsigned int total_chain = 0; 492static unsigned int nr_walks = 0; 493static bool chain_ovfl = false; 494 495/* Worker for the walker that marks reaching definitions of REF, 496 which is based on a non-aliased decl, necessary. It returns 497 true whenever the defining statement of the current VDEF is 498 a kill for REF, as no dominating may-defs are necessary for REF 499 anymore. DATA points to the basic-block that contains the 500 stmt that refers to REF. */ 501 502static bool 503mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data) 504{ 505 gimple def_stmt = SSA_NAME_DEF_STMT (vdef); 506 507 /* All stmts we visit are necessary. */ 508 mark_operand_necessary (vdef); 509 510 /* If the stmt lhs kills ref, then we can stop walking. */ 511 if (gimple_has_lhs (def_stmt) 512 && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME) 513 { 514 tree base, lhs = gimple_get_lhs (def_stmt); 515 HOST_WIDE_INT size, offset, max_size; 516 ao_ref_base (ref); 517 base = get_ref_base_and_extent (lhs, &offset, &size, &max_size); 518 /* We can get MEM[symbol: sZ, index: D.8862_1] here, 519 so base == refd->base does not always hold. */ 520 if (base == ref->base) 521 { 522 /* For a must-alias check we need to be able to constrain 523 the accesses properly. */ 524 if (size != -1 && size == max_size 525 && ref->max_size != -1) 526 { 527 if (offset <= ref->offset 528 && offset + size >= ref->offset + ref->max_size) 529 return true; 530 } 531 /* Or they need to be exactly the same. */ 532 else if (ref->ref 533 /* Make sure there is no induction variable involved 534 in the references (gcc.c-torture/execute/pr42142.c). 535 The simplest way is to check if the kill dominates 536 the use. */ 537 && dominated_by_p (CDI_DOMINATORS, (basic_block) data, 538 gimple_bb (def_stmt)) 539 && operand_equal_p (ref->ref, lhs, 0)) 540 return true; 541 } 542 } 543 544 /* Otherwise keep walking. */ 545 return false; 546} 547 548static void 549mark_aliased_reaching_defs_necessary (gimple stmt, tree ref) 550{ 551 unsigned int chain; 552 ao_ref refd; 553 gcc_assert (!chain_ovfl); 554 ao_ref_init (&refd, ref); 555 chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt), 556 mark_aliased_reaching_defs_necessary_1, 557 gimple_bb (stmt), NULL); 558 if (chain > longest_chain) 559 longest_chain = chain; 560 total_chain += chain; 561 nr_walks++; 562} 563 564/* Worker for the walker that marks reaching definitions of REF, which 565 is not based on a non-aliased decl. For simplicity we need to end 566 up marking all may-defs necessary that are not based on a non-aliased 567 decl. The only job of this walker is to skip may-defs based on 568 a non-aliased decl. */ 569 570static bool 571mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED, 572 tree vdef, void *data ATTRIBUTE_UNUSED) 573{ 574 gimple def_stmt = SSA_NAME_DEF_STMT (vdef); 575 576 /* We have to skip already visited (and thus necessary) statements 577 to make the chaining work after we dropped back to simple mode. */ 578 if (chain_ovfl 579 && TEST_BIT (processed, SSA_NAME_VERSION (vdef))) 580 { 581 gcc_assert (gimple_nop_p (def_stmt) 582 || gimple_plf (def_stmt, STMT_NECESSARY)); 583 return false; 584 } 585 586 /* We want to skip stores to non-aliased variables. */ 587 if (!chain_ovfl 588 && gimple_assign_single_p (def_stmt)) 589 { 590 tree lhs = gimple_assign_lhs (def_stmt); 591 if (!ref_may_be_aliased (lhs)) 592 return false; 593 } 594 595 mark_operand_necessary (vdef); 596 597 return false; 598} 599 600static void 601mark_all_reaching_defs_necessary (gimple stmt) 602{ 603 walk_aliased_vdefs (NULL, gimple_vuse (stmt), 604 mark_all_reaching_defs_necessary_1, NULL, &visited); 605} 606 607/* Return true for PHI nodes with one or identical arguments 608 can be removed. */ 609static bool 610degenerate_phi_p (gimple phi) 611{ 612 unsigned int i; 613 tree op = gimple_phi_arg_def (phi, 0); 614 for (i = 1; i < gimple_phi_num_args (phi); i++) 615 if (gimple_phi_arg_def (phi, i) != op) 616 return false; 617 return true; 618} 619 620/* Propagate necessity using the operands of necessary statements. 621 Process the uses on each statement in the worklist, and add all 622 feeding statements which contribute to the calculation of this 623 value to the worklist. 624 625 In conservative mode, EL is NULL. */ 626 627static void 628propagate_necessity (struct edge_list *el) 629{ 630 gimple stmt; 631 bool aggressive = (el ? true : false); 632 633 if (dump_file && (dump_flags & TDF_DETAILS)) 634 fprintf (dump_file, "\nProcessing worklist:\n"); 635 636 while (VEC_length (gimple, worklist) > 0) 637 { 638 /* Take STMT from worklist. */ 639 stmt = VEC_pop (gimple, worklist); 640 641 if (dump_file && (dump_flags & TDF_DETAILS)) 642 { 643 fprintf (dump_file, "processing: "); 644 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 645 fprintf (dump_file, "\n"); 646 } 647 648 if (aggressive) 649 { 650 /* Mark the last statements of the basic blocks that the block 651 containing STMT is control dependent on, but only if we haven't 652 already done so. */ 653 basic_block bb = gimple_bb (stmt); 654 if (bb != ENTRY_BLOCK_PTR 655 && ! TEST_BIT (visited_control_parents, bb->index)) 656 { 657 SET_BIT (visited_control_parents, bb->index); 658 mark_control_dependent_edges_necessary (bb, el); 659 } 660 } 661 662 if (gimple_code (stmt) == GIMPLE_PHI 663 /* We do not process virtual PHI nodes nor do we track their 664 necessity. */ 665 && is_gimple_reg (gimple_phi_result (stmt))) 666 { 667 /* PHI nodes are somewhat special in that each PHI alternative has 668 data and control dependencies. All the statements feeding the 669 PHI node's arguments are always necessary. In aggressive mode, 670 we also consider the control dependent edges leading to the 671 predecessor block associated with each PHI alternative as 672 necessary. */ 673 size_t k; 674 675 for (k = 0; k < gimple_phi_num_args (stmt); k++) 676 { 677 tree arg = PHI_ARG_DEF (stmt, k); 678 if (TREE_CODE (arg) == SSA_NAME) 679 mark_operand_necessary (arg); 680 } 681 682 if (aggressive && !degenerate_phi_p (stmt)) 683 { 684 for (k = 0; k < gimple_phi_num_args (stmt); k++) 685 { 686 basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src; 687 if (arg_bb != ENTRY_BLOCK_PTR 688 && ! TEST_BIT (visited_control_parents, arg_bb->index)) 689 { 690 SET_BIT (visited_control_parents, arg_bb->index); 691 mark_control_dependent_edges_necessary (arg_bb, el); 692 } 693 } 694 } 695 } 696 else 697 { 698 /* Propagate through the operands. Examine all the USE, VUSE and 699 VDEF operands in this statement. Mark all the statements 700 which feed this statement's uses as necessary. */ 701 ssa_op_iter iter; 702 tree use; 703 704 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 705 mark_operand_necessary (use); 706 707 use = gimple_vuse (stmt); 708 if (!use) 709 continue; 710 711 /* If we dropped to simple mode make all immediately 712 reachable definitions necessary. */ 713 if (chain_ovfl) 714 { 715 mark_all_reaching_defs_necessary (stmt); 716 continue; 717 } 718 719 /* For statements that may load from memory (have a VUSE) we 720 have to mark all reaching (may-)definitions as necessary. 721 We partition this task into two cases: 722 1) explicit loads based on decls that are not aliased 723 2) implicit loads (like calls) and explicit loads not 724 based on decls that are not aliased (like indirect 725 references or loads from globals) 726 For 1) we mark all reaching may-defs as necessary, stopping 727 at dominating kills. For 2) we want to mark all dominating 728 references necessary, but non-aliased ones which we handle 729 in 1). By keeping a global visited bitmap for references 730 we walk for 2) we avoid quadratic behavior for those. */ 731 732 if (is_gimple_call (stmt)) 733 { 734 tree callee = gimple_call_fndecl (stmt); 735 unsigned i; 736 737 /* Calls to functions that are merely acting as barriers 738 or that only store to memory do not make any previous 739 stores necessary. */ 740 if (callee != NULL_TREE 741 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL 742 && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET 743 || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC 744 || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE)) 745 continue; 746 747 /* Calls implicitly load from memory, their arguments 748 in addition may explicitly perform memory loads. */ 749 mark_all_reaching_defs_necessary (stmt); 750 for (i = 0; i < gimple_call_num_args (stmt); ++i) 751 { 752 tree arg = gimple_call_arg (stmt, i); 753 if (TREE_CODE (arg) == SSA_NAME 754 || is_gimple_min_invariant (arg)) 755 continue; 756 if (!ref_may_be_aliased (arg)) 757 mark_aliased_reaching_defs_necessary (stmt, arg); 758 } 759 } 760 else if (gimple_assign_single_p (stmt)) 761 { 762 tree rhs; 763 bool rhs_aliased = false; 764 /* If this is a load mark things necessary. */ 765 rhs = gimple_assign_rhs1 (stmt); 766 if (TREE_CODE (rhs) != SSA_NAME 767 && !is_gimple_min_invariant (rhs)) 768 { 769 if (!ref_may_be_aliased (rhs)) 770 mark_aliased_reaching_defs_necessary (stmt, rhs); 771 else 772 rhs_aliased = true; 773 } 774 if (rhs_aliased) 775 mark_all_reaching_defs_necessary (stmt); 776 } 777 else if (gimple_code (stmt) == GIMPLE_RETURN) 778 { 779 tree rhs = gimple_return_retval (stmt); 780 /* A return statement may perform a load. */ 781 if (TREE_CODE (rhs) != SSA_NAME 782 && !is_gimple_min_invariant (rhs)) 783 { 784 if (!ref_may_be_aliased (rhs)) 785 mark_aliased_reaching_defs_necessary (stmt, rhs); 786 else 787 mark_all_reaching_defs_necessary (stmt); 788 } 789 } 790 else if (gimple_code (stmt) == GIMPLE_ASM) 791 { 792 unsigned i; 793 mark_all_reaching_defs_necessary (stmt); 794 /* Inputs may perform loads. */ 795 for (i = 0; i < gimple_asm_ninputs (stmt); ++i) 796 { 797 tree op = TREE_VALUE (gimple_asm_input_op (stmt, i)); 798 if (TREE_CODE (op) != SSA_NAME 799 && !is_gimple_min_invariant (op) 800 && !ref_may_be_aliased (op)) 801 mark_aliased_reaching_defs_necessary (stmt, op); 802 } 803 } 804 else 805 gcc_unreachable (); 806 807 /* If we over-used our alias oracle budget drop to simple 808 mode. The cost metric allows quadratic behavior 809 (number of uses times number of may-defs queries) up to 810 a constant maximal number of queries and after that falls back to 811 super-linear complexity. */ 812 if (/* Constant but quadratic for small functions. */ 813 total_chain > 128 * 128 814 /* Linear in the number of may-defs. */ 815 && total_chain > 32 * longest_chain 816 /* Linear in the number of uses. */ 817 && total_chain > nr_walks * 32) 818 { 819 chain_ovfl = true; 820 if (visited) 821 bitmap_clear (visited); 822 } 823 } 824 } 825} 826 827/* Replace all uses of result of PHI by underlying variable and mark it 828 for renaming. */ 829 830void 831mark_virtual_phi_result_for_renaming (gimple phi) 832{ 833 bool used = false; 834 imm_use_iterator iter; 835 use_operand_p use_p; 836 gimple stmt; 837 tree result_ssa, result_var; 838 839 if (dump_file && (dump_flags & TDF_DETAILS)) 840 { 841 fprintf (dump_file, "Marking result for renaming : "); 842 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 843 fprintf (dump_file, "\n"); 844 } 845 846 result_ssa = gimple_phi_result (phi); 847 result_var = SSA_NAME_VAR (result_ssa); 848 FOR_EACH_IMM_USE_STMT (stmt, iter, result_ssa) 849 { 850 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 851 SET_USE (use_p, result_var); 852 update_stmt (stmt); 853 used = true; 854 } 855 if (used) 856 mark_sym_for_renaming (result_var); 857} 858 859/* Remove dead PHI nodes from block BB. */ 860 861static bool 862remove_dead_phis (basic_block bb) 863{ 864 bool something_changed = false; 865 gimple_seq phis; 866 gimple phi; 867 gimple_stmt_iterator gsi; 868 phis = phi_nodes (bb); 869 870 for (gsi = gsi_start (phis); !gsi_end_p (gsi);) 871 { 872 stats.total_phis++; 873 phi = gsi_stmt (gsi); 874 875 /* We do not track necessity of virtual PHI nodes. Instead do 876 very simple dead PHI removal here. */ 877 if (!is_gimple_reg (gimple_phi_result (phi))) 878 { 879 /* Virtual PHI nodes with one or identical arguments 880 can be removed. */ 881 if (degenerate_phi_p (phi)) 882 { 883 tree vdef = gimple_phi_result (phi); 884 tree vuse = gimple_phi_arg_def (phi, 0); 885 886 use_operand_p use_p; 887 imm_use_iterator iter; 888 gimple use_stmt; 889 FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef) 890 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 891 SET_USE (use_p, vuse); 892 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef) 893 && TREE_CODE (vuse) == SSA_NAME) 894 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1; 895 } 896 else 897 gimple_set_plf (phi, STMT_NECESSARY, true); 898 } 899 900 if (!gimple_plf (phi, STMT_NECESSARY)) 901 { 902 something_changed = true; 903 if (dump_file && (dump_flags & TDF_DETAILS)) 904 { 905 fprintf (dump_file, "Deleting : "); 906 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 907 fprintf (dump_file, "\n"); 908 } 909 910 remove_phi_node (&gsi, true); 911 stats.removed_phis++; 912 continue; 913 } 914 915 gsi_next (&gsi); 916 } 917 return something_changed; 918} 919 920/* Forward edge E to respective POST_DOM_BB and update PHIs. */ 921 922static edge 923forward_edge_to_pdom (edge e, basic_block post_dom_bb) 924{ 925 gimple_stmt_iterator gsi; 926 edge e2 = NULL; 927 edge_iterator ei; 928 929 if (dump_file && (dump_flags & TDF_DETAILS)) 930 fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index, 931 e->dest->index, post_dom_bb->index); 932 933 e2 = redirect_edge_and_branch (e, post_dom_bb); 934 cfg_altered = true; 935 936 /* If edge was already around, no updating is neccesary. */ 937 if (e2 != e) 938 return e2; 939 940 if (!gimple_seq_empty_p (phi_nodes (post_dom_bb))) 941 { 942 /* We are sure that for every live PHI we are seeing control dependent BB. 943 This means that we can pick any edge to duplicate PHI args from. */ 944 FOR_EACH_EDGE (e2, ei, post_dom_bb->preds) 945 if (e2 != e) 946 break; 947 for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);) 948 { 949 gimple phi = gsi_stmt (gsi); 950 tree op; 951 source_location locus; 952 953 /* PHIs for virtuals have no control dependency relation on them. 954 We are lost here and must force renaming of the symbol. */ 955 if (!is_gimple_reg (gimple_phi_result (phi))) 956 { 957 mark_virtual_phi_result_for_renaming (phi); 958 remove_phi_node (&gsi, true); 959 continue; 960 } 961 962 /* Dead PHI do not imply control dependency. */ 963 if (!gimple_plf (phi, STMT_NECESSARY)) 964 { 965 gsi_next (&gsi); 966 continue; 967 } 968 969 op = gimple_phi_arg_def (phi, e2->dest_idx); 970 locus = gimple_phi_arg_location (phi, e2->dest_idx); 971 add_phi_arg (phi, op, e, locus); 972 /* The resulting PHI if not dead can only be degenerate. */ 973 gcc_assert (degenerate_phi_p (phi)); 974 gsi_next (&gsi); 975 } 976 } 977 return e; 978} 979 980/* Remove dead statement pointed to by iterator I. Receives the basic block BB 981 containing I so that we don't have to look it up. */ 982 983static void 984remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb) 985{ 986 gimple stmt = gsi_stmt (*i); 987 988 if (dump_file && (dump_flags & TDF_DETAILS)) 989 { 990 fprintf (dump_file, "Deleting : "); 991 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 992 fprintf (dump_file, "\n"); 993 } 994 995 stats.removed++; 996 997 /* If we have determined that a conditional branch statement contributes 998 nothing to the program, then we not only remove it, but we also change 999 the flow graph so that the current block will simply fall-thru to its 1000 immediate post-dominator. The blocks we are circumventing will be 1001 removed by cleanup_tree_cfg if this change in the flow graph makes them 1002 unreachable. */ 1003 if (is_ctrl_stmt (stmt)) 1004 { 1005 basic_block post_dom_bb; 1006 edge e, e2; 1007 edge_iterator ei; 1008 1009 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); 1010 1011 e = find_edge (bb, post_dom_bb); 1012 1013 /* If edge is already there, try to use it. This avoids need to update 1014 PHI nodes. Also watch for cases where post dominator does not exists 1015 or is exit block. These can happen for infinite loops as we create 1016 fake edges in the dominator tree. */ 1017 if (e) 1018 ; 1019 else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR) 1020 e = EDGE_SUCC (bb, 0); 1021 else 1022 e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb); 1023 gcc_assert (e); 1024 e->probability = REG_BR_PROB_BASE; 1025 e->count = bb->count; 1026 1027 /* The edge is no longer associated with a conditional, so it does 1028 not have TRUE/FALSE flags. */ 1029 e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 1030 1031 /* The lone outgoing edge from BB will be a fallthru edge. */ 1032 e->flags |= EDGE_FALLTHRU; 1033 1034 /* Remove the remaining outgoing edges. */ 1035 for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); ) 1036 if (e != e2) 1037 { 1038 cfg_altered = true; 1039 remove_edge (e2); 1040 } 1041 else 1042 ei_next (&ei); 1043 } 1044 1045 unlink_stmt_vdef (stmt); 1046 gsi_remove (i, true); 1047 release_defs (stmt); 1048} 1049 1050/* Eliminate unnecessary statements. Any instruction not marked as necessary 1051 contributes nothing to the program, and can be deleted. */ 1052 1053static bool 1054eliminate_unnecessary_stmts (void) 1055{ 1056 bool something_changed = false; 1057 basic_block bb; 1058 gimple_stmt_iterator gsi, psi; 1059 gimple stmt; 1060 tree call; 1061 VEC (basic_block, heap) *h; 1062 1063 if (dump_file && (dump_flags & TDF_DETAILS)) 1064 fprintf (dump_file, "\nEliminating unnecessary statements:\n"); 1065 1066 clear_special_calls (); 1067 1068 /* Walking basic blocks and statements in reverse order avoids 1069 releasing SSA names before any other DEFs that refer to them are 1070 released. This helps avoid loss of debug information, as we get 1071 a chance to propagate all RHSs of removed SSAs into debug uses, 1072 rather than only the latest ones. E.g., consider: 1073 1074 x_3 = y_1 + z_2; 1075 a_5 = x_3 - b_4; 1076 # DEBUG a => a_5 1077 1078 If we were to release x_3 before a_5, when we reached a_5 and 1079 tried to substitute it into the debug stmt, we'd see x_3 there, 1080 but x_3's DEF, type, etc would have already been disconnected. 1081 By going backwards, the debug stmt first changes to: 1082 1083 # DEBUG a => x_3 - b_4 1084 1085 and then to: 1086 1087 # DEBUG a => y_1 + z_2 - b_4 1088 1089 as desired. */ 1090 gcc_assert (dom_info_available_p (CDI_DOMINATORS)); 1091 h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR)); 1092 1093 while (VEC_length (basic_block, h)) 1094 { 1095 bb = VEC_pop (basic_block, h); 1096 1097 /* Remove dead statements. */ 1098 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi) 1099 { 1100 stmt = gsi_stmt (gsi); 1101 1102 psi = gsi; 1103 gsi_prev (&psi); 1104 1105 stats.total++; 1106 1107 /* If GSI is not necessary then remove it. */ 1108 if (!gimple_plf (stmt, STMT_NECESSARY)) 1109 { 1110 if (!is_gimple_debug (stmt)) 1111 something_changed = true; 1112 remove_dead_stmt (&gsi, bb); 1113 } 1114 else if (is_gimple_call (stmt)) 1115 { 1116 call = gimple_call_fndecl (stmt); 1117 if (call) 1118 { 1119 tree name; 1120 1121 /* When LHS of var = call (); is dead, simplify it into 1122 call (); saving one operand. */ 1123 name = gimple_call_lhs (stmt); 1124 if (name && TREE_CODE (name) == SSA_NAME 1125 && !TEST_BIT (processed, SSA_NAME_VERSION (name))) 1126 { 1127 something_changed = true; 1128 if (dump_file && (dump_flags & TDF_DETAILS)) 1129 { 1130 fprintf (dump_file, "Deleting LHS of call: "); 1131 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1132 fprintf (dump_file, "\n"); 1133 } 1134 1135 gimple_call_set_lhs (stmt, NULL_TREE); 1136 maybe_clean_or_replace_eh_stmt (stmt, stmt); 1137 update_stmt (stmt); 1138 release_ssa_name (name); 1139 } 1140 notice_special_calls (stmt); 1141 } 1142 } 1143 } 1144 } 1145 1146 VEC_free (basic_block, heap, h); 1147 1148 /* Since we don't track liveness of virtual PHI nodes, it is possible that we 1149 rendered some PHI nodes unreachable while they are still in use. 1150 Mark them for renaming. */ 1151 if (cfg_altered) 1152 { 1153 basic_block prev_bb; 1154 1155 find_unreachable_blocks (); 1156 1157 /* Delete all unreachable basic blocks in reverse dominator order. */ 1158 for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb) 1159 { 1160 prev_bb = bb->prev_bb; 1161 1162 if (!TEST_BIT (bb_contains_live_stmts, bb->index) 1163 || !(bb->flags & BB_REACHABLE)) 1164 { 1165 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1166 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi)))) 1167 { 1168 bool found = false; 1169 imm_use_iterator iter; 1170 1171 FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi))) 1172 { 1173 if (!(gimple_bb (stmt)->flags & BB_REACHABLE)) 1174 continue; 1175 if (gimple_code (stmt) == GIMPLE_PHI 1176 || gimple_plf (stmt, STMT_NECESSARY)) 1177 { 1178 found = true; 1179 BREAK_FROM_IMM_USE_STMT (iter); 1180 } 1181 } 1182 if (found) 1183 mark_virtual_phi_result_for_renaming (gsi_stmt (gsi)); 1184 } 1185 1186 if (!(bb->flags & BB_REACHABLE)) 1187 { 1188 /* Speed up the removal of blocks that don't 1189 dominate others. Walking backwards, this should 1190 be the common case. ??? Do we need to recompute 1191 dominators because of cfg_altered? */ 1192 if (!MAY_HAVE_DEBUG_STMTS 1193 || !first_dom_son (CDI_DOMINATORS, bb)) 1194 delete_basic_block (bb); 1195 else 1196 { 1197 h = get_all_dominated_blocks (CDI_DOMINATORS, bb); 1198 1199 while (VEC_length (basic_block, h)) 1200 { 1201 bb = VEC_pop (basic_block, h); 1202 prev_bb = bb->prev_bb; 1203 /* Rearrangements to the CFG may have failed 1204 to update the dominators tree, so that 1205 formerly-dominated blocks are now 1206 otherwise reachable. */ 1207 if (!!(bb->flags & BB_REACHABLE)) 1208 continue; 1209 delete_basic_block (bb); 1210 } 1211 1212 VEC_free (basic_block, heap, h); 1213 } 1214 } 1215 } 1216 } 1217 } 1218 FOR_EACH_BB (bb) 1219 { 1220 /* Remove dead PHI nodes. */ 1221 something_changed |= remove_dead_phis (bb); 1222 } 1223 1224 return something_changed; 1225} 1226 1227 1228/* Print out removed statement statistics. */ 1229 1230static void 1231print_stats (void) 1232{ 1233 float percg; 1234 1235 percg = ((float) stats.removed / (float) stats.total) * 100; 1236 fprintf (dump_file, "Removed %d of %d statements (%d%%)\n", 1237 stats.removed, stats.total, (int) percg); 1238 1239 if (stats.total_phis == 0) 1240 percg = 0; 1241 else 1242 percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100; 1243 1244 fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n", 1245 stats.removed_phis, stats.total_phis, (int) percg); 1246} 1247 1248/* Initialization for this pass. Set up the used data structures. */ 1249 1250static void 1251tree_dce_init (bool aggressive) 1252{ 1253 memset ((void *) &stats, 0, sizeof (stats)); 1254 1255 if (aggressive) 1256 { 1257 int i; 1258 1259 control_dependence_map = XNEWVEC (bitmap, last_basic_block); 1260 for (i = 0; i < last_basic_block; ++i) 1261 control_dependence_map[i] = BITMAP_ALLOC (NULL); 1262 1263 last_stmt_necessary = sbitmap_alloc (last_basic_block); 1264 sbitmap_zero (last_stmt_necessary); 1265 bb_contains_live_stmts = sbitmap_alloc (last_basic_block); 1266 sbitmap_zero (bb_contains_live_stmts); 1267 } 1268 1269 processed = sbitmap_alloc (num_ssa_names + 1); 1270 sbitmap_zero (processed); 1271 1272 worklist = VEC_alloc (gimple, heap, 64); 1273 cfg_altered = false; 1274} 1275 1276/* Cleanup after this pass. */ 1277 1278static void 1279tree_dce_done (bool aggressive) 1280{ 1281 if (aggressive) 1282 { 1283 int i; 1284 1285 for (i = 0; i < last_basic_block; ++i) 1286 BITMAP_FREE (control_dependence_map[i]); 1287 free (control_dependence_map); 1288 1289 sbitmap_free (visited_control_parents); 1290 sbitmap_free (last_stmt_necessary); 1291 sbitmap_free (bb_contains_live_stmts); 1292 bb_contains_live_stmts = NULL; 1293 } 1294 1295 sbitmap_free (processed); 1296 1297 VEC_free (gimple, heap, worklist); 1298} 1299 1300/* Main routine to eliminate dead code. 1301 1302 AGGRESSIVE controls the aggressiveness of the algorithm. 1303 In conservative mode, we ignore control dependence and simply declare 1304 all but the most trivially dead branches necessary. This mode is fast. 1305 In aggressive mode, control dependences are taken into account, which 1306 results in more dead code elimination, but at the cost of some time. 1307 1308 FIXME: Aggressive mode before PRE doesn't work currently because 1309 the dominance info is not invalidated after DCE1. This is 1310 not an issue right now because we only run aggressive DCE 1311 as the last tree SSA pass, but keep this in mind when you 1312 start experimenting with pass ordering. */ 1313 1314static unsigned int 1315perform_tree_ssa_dce (bool aggressive) 1316{ 1317 struct edge_list *el = NULL; 1318 bool something_changed = 0; 1319 1320 calculate_dominance_info (CDI_DOMINATORS); 1321 1322 /* Preheaders are needed for SCEV to work. 1323 Simple lateches and recorded exits improve chances that loop will 1324 proved to be finite in testcases such as in loop-15.c and loop-24.c */ 1325 if (aggressive) 1326 loop_optimizer_init (LOOPS_NORMAL 1327 | LOOPS_HAVE_RECORDED_EXITS); 1328 1329 tree_dce_init (aggressive); 1330 1331 if (aggressive) 1332 { 1333 /* Compute control dependence. */ 1334 timevar_push (TV_CONTROL_DEPENDENCES); 1335 calculate_dominance_info (CDI_POST_DOMINATORS); 1336 el = create_edge_list (); 1337 find_all_control_dependences (el); 1338 timevar_pop (TV_CONTROL_DEPENDENCES); 1339 1340 visited_control_parents = sbitmap_alloc (last_basic_block); 1341 sbitmap_zero (visited_control_parents); 1342 1343 mark_dfs_back_edges (); 1344 } 1345 1346 find_obviously_necessary_stmts (el); 1347 1348 if (aggressive) 1349 loop_optimizer_finalize (); 1350 1351 longest_chain = 0; 1352 total_chain = 0; 1353 nr_walks = 0; 1354 chain_ovfl = false; 1355 visited = BITMAP_ALLOC (NULL); 1356 propagate_necessity (el); 1357 BITMAP_FREE (visited); 1358 1359 something_changed |= eliminate_unnecessary_stmts (); 1360 something_changed |= cfg_altered; 1361 1362 /* We do not update postdominators, so free them unconditionally. */ 1363 free_dominance_info (CDI_POST_DOMINATORS); 1364 1365 /* If we removed paths in the CFG, then we need to update 1366 dominators as well. I haven't investigated the possibility 1367 of incrementally updating dominators. */ 1368 if (cfg_altered) 1369 free_dominance_info (CDI_DOMINATORS); 1370 1371 statistics_counter_event (cfun, "Statements deleted", stats.removed); 1372 statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis); 1373 1374 /* Debugging dumps. */ 1375 if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS))) 1376 print_stats (); 1377 1378 tree_dce_done (aggressive); 1379 1380 free_edge_list (el); 1381 1382 if (something_changed) 1383 return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect 1384 | TODO_remove_unused_locals); 1385 else 1386 return 0; 1387} 1388 1389/* Pass entry points. */ 1390static unsigned int 1391tree_ssa_dce (void) 1392{ 1393 return perform_tree_ssa_dce (/*aggressive=*/false); 1394} 1395 1396static unsigned int 1397tree_ssa_dce_loop (void) 1398{ 1399 unsigned int todo; 1400 todo = perform_tree_ssa_dce (/*aggressive=*/false); 1401 if (todo) 1402 { 1403 free_numbers_of_iterations_estimates (); 1404 scev_reset (); 1405 } 1406 return todo; 1407} 1408 1409static unsigned int 1410tree_ssa_cd_dce (void) 1411{ 1412 return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); 1413} 1414 1415static bool 1416gate_dce (void) 1417{ 1418 return flag_tree_dce != 0; 1419} 1420 1421struct gimple_opt_pass pass_dce = 1422{ 1423 { 1424 GIMPLE_PASS, 1425 "dce", /* name */ 1426 gate_dce, /* gate */ 1427 tree_ssa_dce, /* execute */ 1428 NULL, /* sub */ 1429 NULL, /* next */ 1430 0, /* static_pass_number */ 1431 TV_TREE_DCE, /* tv_id */ 1432 PROP_cfg | PROP_ssa, /* properties_required */ 1433 0, /* properties_provided */ 1434 0, /* properties_destroyed */ 1435 0, /* todo_flags_start */ 1436 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ 1437 } 1438}; 1439 1440struct gimple_opt_pass pass_dce_loop = 1441{ 1442 { 1443 GIMPLE_PASS, 1444 "dceloop", /* name */ 1445 gate_dce, /* gate */ 1446 tree_ssa_dce_loop, /* execute */ 1447 NULL, /* sub */ 1448 NULL, /* next */ 1449 0, /* static_pass_number */ 1450 TV_TREE_DCE, /* tv_id */ 1451 PROP_cfg | PROP_ssa, /* properties_required */ 1452 0, /* properties_provided */ 1453 0, /* properties_destroyed */ 1454 0, /* todo_flags_start */ 1455 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ 1456 } 1457}; 1458 1459struct gimple_opt_pass pass_cd_dce = 1460{ 1461 { 1462 GIMPLE_PASS, 1463 "cddce", /* name */ 1464 gate_dce, /* gate */ 1465 tree_ssa_cd_dce, /* execute */ 1466 NULL, /* sub */ 1467 NULL, /* next */ 1468 0, /* static_pass_number */ 1469 TV_TREE_CD_DCE, /* tv_id */ 1470 PROP_cfg | PROP_ssa, /* properties_required */ 1471 0, /* properties_provided */ 1472 0, /* properties_destroyed */ 1473 0, /* todo_flags_start */ 1474 TODO_dump_func | TODO_verify_ssa 1475 | TODO_verify_flow /* todo_flags_finish */ 1476 } 1477}; 1478