1 /* Dead code elimination pass for the GNU compiler. 2 Copyright (C) 2002-2017 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 7 This file is part of GCC. 8 9 GCC is free software; you can redistribute it and/or modify it 10 under the terms of the GNU General Public License as published by the 11 Free Software Foundation; either version 3, or (at your option) any 12 later version. 13 14 GCC is distributed in the hope that it will be useful, but WITHOUT 15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17 for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with GCC; see the file COPYING3. If not see 21 <http://www.gnu.org/licenses/>. */ 22 23 /* Dead code elimination. 24 25 References: 26 27 Building an Optimizing Compiler, 28 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. 29 30 Advanced Compiler Design and Implementation, 31 Steven Muchnick, Morgan Kaufmann, 1997, Section 18.10. 32 33 Dead-code elimination is the removal of statements which have no 34 impact on the program's output. "Dead statements" have no impact 35 on the program's output, while "necessary statements" may have 36 impact on the output. 37 38 The algorithm consists of three phases: 39 1. Marking as necessary all statements known to be necessary, 40 e.g. most function calls, writing a value to memory, etc; 41 2. Propagating necessary statements, e.g., the statements 42 giving values to operands in necessary statements; and 43 3. Removing dead statements. */ 44 45 #include "config.h" 46 #include "system.h" 47 #include "coretypes.h" 48 #include "backend.h" 49 #include "rtl.h" 50 #include "tree.h" 51 #include "gimple.h" 52 #include "cfghooks.h" 53 #include "tree-pass.h" 54 #include "ssa.h" 55 #include "gimple-pretty-print.h" 56 #include "fold-const.h" 57 #include "calls.h" 58 #include "cfganal.h" 59 #include "tree-eh.h" 60 #include "gimplify.h" 61 #include "gimple-iterator.h" 62 #include "tree-cfg.h" 63 #include "tree-ssa-loop-niter.h" 64 #include "tree-into-ssa.h" 65 #include "tree-dfa.h" 66 #include "cfgloop.h" 67 #include "tree-scalar-evolution.h" 68 #include "tree-chkp.h" 69 #include "tree-ssa-propagate.h" 70 #include "gimple-fold.h" 71 72 static struct stmt_stats 73 { 74 int total; 75 int total_phis; 76 int removed; 77 int removed_phis; 78 } stats; 79 80 #define STMT_NECESSARY GF_PLF_1 81 82 static vec<gimple *> worklist; 83 84 /* Vector indicating an SSA name has already been processed and marked 85 as necessary. */ 86 static sbitmap processed; 87 88 /* Vector indicating that the last statement of a basic block has already 89 been marked as necessary. */ 90 static sbitmap last_stmt_necessary; 91 92 /* Vector indicating that BB contains statements that are live. */ 93 static sbitmap bb_contains_live_stmts; 94 95 /* Before we can determine whether a control branch is dead, we need to 96 compute which blocks are control dependent on which edges. 97 98 We expect each block to be control dependent on very few edges so we 99 use a bitmap for each block recording its edges. An array holds the 100 bitmap. The Ith bit in the bitmap is set if that block is dependent 101 on the Ith edge. */ 102 static control_dependences *cd; 103 104 /* Vector indicating that a basic block has already had all the edges 105 processed that it is control dependent on. */ 106 static sbitmap visited_control_parents; 107 108 /* TRUE if this pass alters the CFG (by removing control statements). 109 FALSE otherwise. 110 111 If this pass alters the CFG, then it will arrange for the dominators 112 to be recomputed. */ 113 static bool cfg_altered; 114 115 /* When non-NULL holds map from basic block index into the postorder. */ 116 static int *bb_postorder; 117 118 119 /* If STMT is not already marked necessary, mark it, and add it to the 120 worklist if ADD_TO_WORKLIST is true. */ 121 122 static inline void 123 mark_stmt_necessary (gimple *stmt, bool add_to_worklist) 124 { 125 gcc_assert (stmt); 126 127 if (gimple_plf (stmt, STMT_NECESSARY)) 128 return; 129 130 if (dump_file && (dump_flags & TDF_DETAILS)) 131 { 132 fprintf (dump_file, "Marking useful stmt: "); 133 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 134 fprintf (dump_file, "\n"); 135 } 136 137 gimple_set_plf (stmt, STMT_NECESSARY, true); 138 if (add_to_worklist) 139 worklist.safe_push (stmt); 140 if (add_to_worklist && bb_contains_live_stmts && !is_gimple_debug (stmt)) 141 bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index); 142 } 143 144 145 /* Mark the statement defining operand OP as necessary. */ 146 147 static inline void 148 mark_operand_necessary (tree op) 149 { 150 gimple *stmt; 151 int ver; 152 153 gcc_assert (op); 154 155 ver = SSA_NAME_VERSION (op); 156 if (bitmap_bit_p (processed, ver)) 157 { 158 stmt = SSA_NAME_DEF_STMT (op); 159 gcc_assert (gimple_nop_p (stmt) 160 || gimple_plf (stmt, STMT_NECESSARY)); 161 return; 162 } 163 bitmap_set_bit (processed, ver); 164 165 stmt = SSA_NAME_DEF_STMT (op); 166 gcc_assert (stmt); 167 168 if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt)) 169 return; 170 171 if (dump_file && (dump_flags & TDF_DETAILS)) 172 { 173 fprintf (dump_file, "marking necessary through "); 174 print_generic_expr (dump_file, op, 0); 175 fprintf (dump_file, " stmt "); 176 print_gimple_stmt (dump_file, stmt, 0, 0); 177 } 178 179 gimple_set_plf (stmt, STMT_NECESSARY, true); 180 if (bb_contains_live_stmts) 181 bitmap_set_bit (bb_contains_live_stmts, gimple_bb (stmt)->index); 182 worklist.safe_push (stmt); 183 } 184 185 186 /* Mark STMT as necessary if it obviously is. Add it to the worklist if 187 it can make other statements necessary. 188 189 If AGGRESSIVE is false, control statements are conservatively marked as 190 necessary. */ 191 192 static void 193 mark_stmt_if_obviously_necessary (gimple *stmt, bool aggressive) 194 { 195 /* With non-call exceptions, we have to assume that all statements could 196 throw. If a statement could throw, it can be deemed necessary. */ 197 if (cfun->can_throw_non_call_exceptions 198 && !cfun->can_delete_dead_exceptions 199 && stmt_could_throw_p (stmt)) 200 { 201 mark_stmt_necessary (stmt, true); 202 return; 203 } 204 205 /* Statements that are implicitly live. Most function calls, asm 206 and return statements are required. Labels and GIMPLE_BIND nodes 207 are kept because they are control flow, and we have no way of 208 knowing whether they can be removed. DCE can eliminate all the 209 other statements in a block, and CFG can then remove the block 210 and labels. */ 211 switch (gimple_code (stmt)) 212 { 213 case GIMPLE_PREDICT: 214 case GIMPLE_LABEL: 215 mark_stmt_necessary (stmt, false); 216 return; 217 218 case GIMPLE_ASM: 219 case GIMPLE_RESX: 220 case GIMPLE_RETURN: 221 mark_stmt_necessary (stmt, true); 222 return; 223 224 case GIMPLE_CALL: 225 { 226 tree callee = gimple_call_fndecl (stmt); 227 if (callee != NULL_TREE 228 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) 229 switch (DECL_FUNCTION_CODE (callee)) 230 { 231 case BUILT_IN_MALLOC: 232 case BUILT_IN_ALIGNED_ALLOC: 233 case BUILT_IN_CALLOC: 234 case BUILT_IN_ALLOCA: 235 case BUILT_IN_ALLOCA_WITH_ALIGN: 236 return; 237 238 default:; 239 } 240 /* Most, but not all function calls are required. Function calls that 241 produce no result and have no side effects (i.e. const pure 242 functions) are unnecessary. */ 243 if (gimple_has_side_effects (stmt)) 244 { 245 mark_stmt_necessary (stmt, true); 246 return; 247 } 248 if (!gimple_call_lhs (stmt)) 249 return; 250 break; 251 } 252 253 case GIMPLE_DEBUG: 254 /* Debug temps without a value are not useful. ??? If we could 255 easily locate the debug temp bind stmt for a use thereof, 256 would could refrain from marking all debug temps here, and 257 mark them only if they're used. */ 258 if (!gimple_debug_bind_p (stmt) 259 || gimple_debug_bind_has_value_p (stmt) 260 || TREE_CODE (gimple_debug_bind_get_var (stmt)) != DEBUG_EXPR_DECL) 261 mark_stmt_necessary (stmt, false); 262 return; 263 264 case GIMPLE_GOTO: 265 gcc_assert (!simple_goto_p (stmt)); 266 mark_stmt_necessary (stmt, true); 267 return; 268 269 case GIMPLE_COND: 270 gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2); 271 /* Fall through. */ 272 273 case GIMPLE_SWITCH: 274 if (! aggressive) 275 mark_stmt_necessary (stmt, true); 276 break; 277 278 case GIMPLE_ASSIGN: 279 if (gimple_clobber_p (stmt)) 280 return; 281 break; 282 283 default: 284 break; 285 } 286 287 /* If the statement has volatile operands, it needs to be preserved. 288 Same for statements that can alter control flow in unpredictable 289 ways. */ 290 if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt)) 291 { 292 mark_stmt_necessary (stmt, true); 293 return; 294 } 295 296 if (stmt_may_clobber_global_p (stmt)) 297 { 298 mark_stmt_necessary (stmt, true); 299 return; 300 } 301 302 return; 303 } 304 305 306 /* Mark the last statement of BB as necessary. */ 307 308 static void 309 mark_last_stmt_necessary (basic_block bb) 310 { 311 gimple *stmt = last_stmt (bb); 312 313 bitmap_set_bit (last_stmt_necessary, bb->index); 314 bitmap_set_bit (bb_contains_live_stmts, bb->index); 315 316 /* We actually mark the statement only if it is a control statement. */ 317 if (stmt && is_ctrl_stmt (stmt)) 318 mark_stmt_necessary (stmt, true); 319 } 320 321 322 /* Mark control dependent edges of BB as necessary. We have to do this only 323 once for each basic block so we set the appropriate bit after we're done. 324 325 When IGNORE_SELF is true, ignore BB in the list of control dependences. */ 326 327 static void 328 mark_control_dependent_edges_necessary (basic_block bb, bool ignore_self) 329 { 330 bitmap_iterator bi; 331 unsigned edge_number; 332 bool skipped = false; 333 334 gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); 335 336 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)) 337 return; 338 339 EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index), 340 0, edge_number, bi) 341 { 342 basic_block cd_bb = cd->get_edge_src (edge_number); 343 344 if (ignore_self && cd_bb == bb) 345 { 346 skipped = true; 347 continue; 348 } 349 350 if (!bitmap_bit_p (last_stmt_necessary, cd_bb->index)) 351 mark_last_stmt_necessary (cd_bb); 352 } 353 354 if (!skipped) 355 bitmap_set_bit (visited_control_parents, bb->index); 356 } 357 358 359 /* Find obviously necessary statements. These are things like most function 360 calls, and stores to file level variables. 361 362 If EL is NULL, control statements are conservatively marked as 363 necessary. Otherwise it contains the list of edges used by control 364 dependence analysis. */ 365 366 static void 367 find_obviously_necessary_stmts (bool aggressive) 368 { 369 basic_block bb; 370 gimple_stmt_iterator gsi; 371 edge e; 372 gimple *phi, *stmt; 373 int flags; 374 375 FOR_EACH_BB_FN (bb, cfun) 376 { 377 /* PHI nodes are never inherently necessary. */ 378 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 379 { 380 phi = gsi_stmt (gsi); 381 gimple_set_plf (phi, STMT_NECESSARY, false); 382 } 383 384 /* Check all statements in the block. */ 385 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 386 { 387 stmt = gsi_stmt (gsi); 388 gimple_set_plf (stmt, STMT_NECESSARY, false); 389 mark_stmt_if_obviously_necessary (stmt, aggressive); 390 } 391 } 392 393 /* Pure and const functions are finite and thus have no infinite loops in 394 them. */ 395 flags = flags_from_decl_or_type (current_function_decl); 396 if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE)) 397 return; 398 399 /* Prevent the empty possibly infinite loops from being removed. */ 400 if (aggressive) 401 { 402 struct loop *loop; 403 if (mark_irreducible_loops ()) 404 FOR_EACH_BB_FN (bb, cfun) 405 { 406 edge_iterator ei; 407 FOR_EACH_EDGE (e, ei, bb->succs) 408 if ((e->flags & EDGE_DFS_BACK) 409 && (e->flags & EDGE_IRREDUCIBLE_LOOP)) 410 { 411 if (dump_file) 412 fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n", 413 e->src->index, e->dest->index); 414 mark_control_dependent_edges_necessary (e->dest, false); 415 } 416 } 417 418 FOR_EACH_LOOP (loop, 0) 419 if (!finite_loop_p (loop)) 420 { 421 if (dump_file) 422 fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num); 423 mark_control_dependent_edges_necessary (loop->latch, false); 424 } 425 } 426 } 427 428 429 /* Return true if REF is based on an aliased base, otherwise false. */ 430 431 static bool 432 ref_may_be_aliased (tree ref) 433 { 434 gcc_assert (TREE_CODE (ref) != WITH_SIZE_EXPR); 435 while (handled_component_p (ref)) 436 ref = TREE_OPERAND (ref, 0); 437 if (TREE_CODE (ref) == MEM_REF 438 && TREE_CODE (TREE_OPERAND (ref, 0)) == ADDR_EXPR) 439 ref = TREE_OPERAND (TREE_OPERAND (ref, 0), 0); 440 return !(DECL_P (ref) 441 && !may_be_aliased (ref)); 442 } 443 444 static bitmap visited = NULL; 445 static unsigned int longest_chain = 0; 446 static unsigned int total_chain = 0; 447 static unsigned int nr_walks = 0; 448 static bool chain_ovfl = false; 449 450 /* Worker for the walker that marks reaching definitions of REF, 451 which is based on a non-aliased decl, necessary. It returns 452 true whenever the defining statement of the current VDEF is 453 a kill for REF, as no dominating may-defs are necessary for REF 454 anymore. DATA points to the basic-block that contains the 455 stmt that refers to REF. */ 456 457 static bool 458 mark_aliased_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data) 459 { 460 gimple *def_stmt = SSA_NAME_DEF_STMT (vdef); 461 462 /* All stmts we visit are necessary. */ 463 if (! gimple_clobber_p (def_stmt)) 464 mark_operand_necessary (vdef); 465 466 /* If the stmt lhs kills ref, then we can stop walking. */ 467 if (gimple_has_lhs (def_stmt) 468 && TREE_CODE (gimple_get_lhs (def_stmt)) != SSA_NAME 469 /* The assignment is not necessarily carried out if it can throw 470 and we can catch it in the current function where we could inspect 471 the previous value. 472 ??? We only need to care about the RHS throwing. For aggregate 473 assignments or similar calls and non-call exceptions the LHS 474 might throw as well. */ 475 && !stmt_can_throw_internal (def_stmt)) 476 { 477 tree base, lhs = gimple_get_lhs (def_stmt); 478 HOST_WIDE_INT size, offset, max_size; 479 bool reverse; 480 ao_ref_base (ref); 481 base 482 = get_ref_base_and_extent (lhs, &offset, &size, &max_size, &reverse); 483 /* We can get MEM[symbol: sZ, index: D.8862_1] here, 484 so base == refd->base does not always hold. */ 485 if (base == ref->base) 486 { 487 /* For a must-alias check we need to be able to constrain 488 the accesses properly. */ 489 if (size != -1 && size == max_size 490 && ref->max_size != -1) 491 { 492 if (offset <= ref->offset 493 && offset + size >= ref->offset + ref->max_size) 494 return true; 495 } 496 /* Or they need to be exactly the same. */ 497 else if (ref->ref 498 /* Make sure there is no induction variable involved 499 in the references (gcc.c-torture/execute/pr42142.c). 500 The simplest way is to check if the kill dominates 501 the use. */ 502 /* But when both are in the same block we cannot 503 easily tell whether we came from a backedge 504 unless we decide to compute stmt UIDs 505 (see PR58246). */ 506 && (basic_block) data != gimple_bb (def_stmt) 507 && dominated_by_p (CDI_DOMINATORS, (basic_block) data, 508 gimple_bb (def_stmt)) 509 && operand_equal_p (ref->ref, lhs, 0)) 510 return true; 511 } 512 } 513 514 /* Otherwise keep walking. */ 515 return false; 516 } 517 518 static void 519 mark_aliased_reaching_defs_necessary (gimple *stmt, tree ref) 520 { 521 unsigned int chain; 522 ao_ref refd; 523 gcc_assert (!chain_ovfl); 524 ao_ref_init (&refd, ref); 525 chain = walk_aliased_vdefs (&refd, gimple_vuse (stmt), 526 mark_aliased_reaching_defs_necessary_1, 527 gimple_bb (stmt), NULL); 528 if (chain > longest_chain) 529 longest_chain = chain; 530 total_chain += chain; 531 nr_walks++; 532 } 533 534 /* Worker for the walker that marks reaching definitions of REF, which 535 is not based on a non-aliased decl. For simplicity we need to end 536 up marking all may-defs necessary that are not based on a non-aliased 537 decl. The only job of this walker is to skip may-defs based on 538 a non-aliased decl. */ 539 540 static bool 541 mark_all_reaching_defs_necessary_1 (ao_ref *ref ATTRIBUTE_UNUSED, 542 tree vdef, void *data ATTRIBUTE_UNUSED) 543 { 544 gimple *def_stmt = SSA_NAME_DEF_STMT (vdef); 545 546 /* We have to skip already visited (and thus necessary) statements 547 to make the chaining work after we dropped back to simple mode. */ 548 if (chain_ovfl 549 && bitmap_bit_p (processed, SSA_NAME_VERSION (vdef))) 550 { 551 gcc_assert (gimple_nop_p (def_stmt) 552 || gimple_plf (def_stmt, STMT_NECESSARY)); 553 return false; 554 } 555 556 /* We want to skip stores to non-aliased variables. */ 557 if (!chain_ovfl 558 && gimple_assign_single_p (def_stmt)) 559 { 560 tree lhs = gimple_assign_lhs (def_stmt); 561 if (!ref_may_be_aliased (lhs)) 562 return false; 563 } 564 565 /* We want to skip statments that do not constitute stores but have 566 a virtual definition. */ 567 if (is_gimple_call (def_stmt)) 568 { 569 tree callee = gimple_call_fndecl (def_stmt); 570 if (callee != NULL_TREE 571 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL) 572 switch (DECL_FUNCTION_CODE (callee)) 573 { 574 case BUILT_IN_MALLOC: 575 case BUILT_IN_ALIGNED_ALLOC: 576 case BUILT_IN_CALLOC: 577 case BUILT_IN_ALLOCA: 578 case BUILT_IN_ALLOCA_WITH_ALIGN: 579 case BUILT_IN_FREE: 580 return false; 581 582 default:; 583 } 584 } 585 586 if (! gimple_clobber_p (def_stmt)) 587 mark_operand_necessary (vdef); 588 589 return false; 590 } 591 592 static void 593 mark_all_reaching_defs_necessary (gimple *stmt) 594 { 595 walk_aliased_vdefs (NULL, gimple_vuse (stmt), 596 mark_all_reaching_defs_necessary_1, NULL, &visited); 597 } 598 599 /* Return true for PHI nodes with one or identical arguments 600 can be removed. */ 601 static bool 602 degenerate_phi_p (gimple *phi) 603 { 604 unsigned int i; 605 tree op = gimple_phi_arg_def (phi, 0); 606 for (i = 1; i < gimple_phi_num_args (phi); i++) 607 if (gimple_phi_arg_def (phi, i) != op) 608 return false; 609 return true; 610 } 611 612 /* Propagate necessity using the operands of necessary statements. 613 Process the uses on each statement in the worklist, and add all 614 feeding statements which contribute to the calculation of this 615 value to the worklist. 616 617 In conservative mode, EL is NULL. */ 618 619 static void 620 propagate_necessity (bool aggressive) 621 { 622 gimple *stmt; 623 624 if (dump_file && (dump_flags & TDF_DETAILS)) 625 fprintf (dump_file, "\nProcessing worklist:\n"); 626 627 while (worklist.length () > 0) 628 { 629 /* Take STMT from worklist. */ 630 stmt = worklist.pop (); 631 632 if (dump_file && (dump_flags & TDF_DETAILS)) 633 { 634 fprintf (dump_file, "processing: "); 635 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 636 fprintf (dump_file, "\n"); 637 } 638 639 if (aggressive) 640 { 641 /* Mark the last statement of the basic blocks on which the block 642 containing STMT is control dependent, but only if we haven't 643 already done so. */ 644 basic_block bb = gimple_bb (stmt); 645 if (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) 646 && !bitmap_bit_p (visited_control_parents, bb->index)) 647 mark_control_dependent_edges_necessary (bb, false); 648 } 649 650 if (gimple_code (stmt) == GIMPLE_PHI 651 /* We do not process virtual PHI nodes nor do we track their 652 necessity. */ 653 && !virtual_operand_p (gimple_phi_result (stmt))) 654 { 655 /* PHI nodes are somewhat special in that each PHI alternative has 656 data and control dependencies. All the statements feeding the 657 PHI node's arguments are always necessary. In aggressive mode, 658 we also consider the control dependent edges leading to the 659 predecessor block associated with each PHI alternative as 660 necessary. */ 661 gphi *phi = as_a <gphi *> (stmt); 662 size_t k; 663 664 for (k = 0; k < gimple_phi_num_args (stmt); k++) 665 { 666 tree arg = PHI_ARG_DEF (stmt, k); 667 if (TREE_CODE (arg) == SSA_NAME) 668 mark_operand_necessary (arg); 669 } 670 671 /* For PHI operands it matters from where the control flow arrives 672 to the BB. Consider the following example: 673 674 a=exp1; 675 b=exp2; 676 if (test) 677 ; 678 else 679 ; 680 c=PHI(a,b) 681 682 We need to mark control dependence of the empty basic blocks, since they 683 contains computation of PHI operands. 684 685 Doing so is too restrictive in the case the predecestor block is in 686 the loop. Consider: 687 688 if (b) 689 { 690 int i; 691 for (i = 0; i<1000; ++i) 692 ; 693 j = 0; 694 } 695 return j; 696 697 There is PHI for J in the BB containing return statement. 698 In this case the control dependence of predecestor block (that is 699 within the empty loop) also contains the block determining number 700 of iterations of the block that would prevent removing of empty 701 loop in this case. 702 703 This scenario can be avoided by splitting critical edges. 704 To save the critical edge splitting pass we identify how the control 705 dependence would look like if the edge was split. 706 707 Consider the modified CFG created from current CFG by splitting 708 edge B->C. In the postdominance tree of modified CFG, C' is 709 always child of C. There are two cases how chlids of C' can look 710 like: 711 712 1) C' is leaf 713 714 In this case the only basic block C' is control dependent on is B. 715 716 2) C' has single child that is B 717 718 In this case control dependence of C' is same as control 719 dependence of B in original CFG except for block B itself. 720 (since C' postdominate B in modified CFG) 721 722 Now how to decide what case happens? There are two basic options: 723 724 a) C postdominate B. Then C immediately postdominate B and 725 case 2 happens iff there is no other way from B to C except 726 the edge B->C. 727 728 There is other way from B to C iff there is succesor of B that 729 is not postdominated by B. Testing this condition is somewhat 730 expensive, because we need to iterate all succesors of B. 731 We are safe to assume that this does not happen: we will mark B 732 as needed when processing the other path from B to C that is 733 conrol dependent on B and marking control dependencies of B 734 itself is harmless because they will be processed anyway after 735 processing control statement in B. 736 737 b) C does not postdominate B. Always case 1 happens since there is 738 path from C to exit that does not go through B and thus also C'. */ 739 740 if (aggressive && !degenerate_phi_p (stmt)) 741 { 742 for (k = 0; k < gimple_phi_num_args (stmt); k++) 743 { 744 basic_block arg_bb = gimple_phi_arg_edge (phi, k)->src; 745 746 if (gimple_bb (stmt) 747 != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb)) 748 { 749 if (!bitmap_bit_p (last_stmt_necessary, arg_bb->index)) 750 mark_last_stmt_necessary (arg_bb); 751 } 752 else if (arg_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) 753 && !bitmap_bit_p (visited_control_parents, 754 arg_bb->index)) 755 mark_control_dependent_edges_necessary (arg_bb, true); 756 } 757 } 758 } 759 else 760 { 761 /* Propagate through the operands. Examine all the USE, VUSE and 762 VDEF operands in this statement. Mark all the statements 763 which feed this statement's uses as necessary. */ 764 ssa_op_iter iter; 765 tree use; 766 767 /* If this is a call to free which is directly fed by an 768 allocation function do not mark that necessary through 769 processing the argument. */ 770 if (gimple_call_builtin_p (stmt, BUILT_IN_FREE)) 771 { 772 tree ptr = gimple_call_arg (stmt, 0); 773 gimple *def_stmt; 774 tree def_callee; 775 /* If the pointer we free is defined by an allocation 776 function do not add the call to the worklist. */ 777 if (TREE_CODE (ptr) == SSA_NAME 778 && is_gimple_call (def_stmt = SSA_NAME_DEF_STMT (ptr)) 779 && (def_callee = gimple_call_fndecl (def_stmt)) 780 && DECL_BUILT_IN_CLASS (def_callee) == BUILT_IN_NORMAL 781 && (DECL_FUNCTION_CODE (def_callee) == BUILT_IN_ALIGNED_ALLOC 782 || DECL_FUNCTION_CODE (def_callee) == BUILT_IN_MALLOC 783 || DECL_FUNCTION_CODE (def_callee) == BUILT_IN_CALLOC)) 784 { 785 gimple *bounds_def_stmt; 786 tree bounds; 787 788 /* For instrumented calls we should also check used 789 bounds are returned by the same allocation call. */ 790 if (!gimple_call_with_bounds_p (stmt) 791 || ((bounds = gimple_call_arg (stmt, 1)) 792 && TREE_CODE (bounds) == SSA_NAME 793 && (bounds_def_stmt = SSA_NAME_DEF_STMT (bounds)) 794 && chkp_gimple_call_builtin_p (bounds_def_stmt, 795 BUILT_IN_CHKP_BNDRET) 796 && gimple_call_arg (bounds_def_stmt, 0) == ptr)) 797 continue; 798 } 799 } 800 801 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 802 mark_operand_necessary (use); 803 804 use = gimple_vuse (stmt); 805 if (!use) 806 continue; 807 808 /* If we dropped to simple mode make all immediately 809 reachable definitions necessary. */ 810 if (chain_ovfl) 811 { 812 mark_all_reaching_defs_necessary (stmt); 813 continue; 814 } 815 816 /* For statements that may load from memory (have a VUSE) we 817 have to mark all reaching (may-)definitions as necessary. 818 We partition this task into two cases: 819 1) explicit loads based on decls that are not aliased 820 2) implicit loads (like calls) and explicit loads not 821 based on decls that are not aliased (like indirect 822 references or loads from globals) 823 For 1) we mark all reaching may-defs as necessary, stopping 824 at dominating kills. For 2) we want to mark all dominating 825 references necessary, but non-aliased ones which we handle 826 in 1). By keeping a global visited bitmap for references 827 we walk for 2) we avoid quadratic behavior for those. */ 828 829 if (is_gimple_call (stmt)) 830 { 831 tree callee = gimple_call_fndecl (stmt); 832 unsigned i; 833 834 /* Calls to functions that are merely acting as barriers 835 or that only store to memory do not make any previous 836 stores necessary. */ 837 if (callee != NULL_TREE 838 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL 839 && (DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET 840 || DECL_FUNCTION_CODE (callee) == BUILT_IN_MEMSET_CHK 841 || DECL_FUNCTION_CODE (callee) == BUILT_IN_MALLOC 842 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALIGNED_ALLOC 843 || DECL_FUNCTION_CODE (callee) == BUILT_IN_CALLOC 844 || DECL_FUNCTION_CODE (callee) == BUILT_IN_FREE 845 || DECL_FUNCTION_CODE (callee) == BUILT_IN_VA_END 846 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA 847 || (DECL_FUNCTION_CODE (callee) 848 == BUILT_IN_ALLOCA_WITH_ALIGN) 849 || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE 850 || DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE 851 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ASSUME_ALIGNED)) 852 continue; 853 854 /* Calls implicitly load from memory, their arguments 855 in addition may explicitly perform memory loads. */ 856 mark_all_reaching_defs_necessary (stmt); 857 for (i = 0; i < gimple_call_num_args (stmt); ++i) 858 { 859 tree arg = gimple_call_arg (stmt, i); 860 if (TREE_CODE (arg) == SSA_NAME 861 || is_gimple_min_invariant (arg)) 862 continue; 863 if (TREE_CODE (arg) == WITH_SIZE_EXPR) 864 arg = TREE_OPERAND (arg, 0); 865 if (!ref_may_be_aliased (arg)) 866 mark_aliased_reaching_defs_necessary (stmt, arg); 867 } 868 } 869 else if (gimple_assign_single_p (stmt)) 870 { 871 tree rhs; 872 /* If this is a load mark things necessary. */ 873 rhs = gimple_assign_rhs1 (stmt); 874 if (TREE_CODE (rhs) != SSA_NAME 875 && !is_gimple_min_invariant (rhs) 876 && TREE_CODE (rhs) != CONSTRUCTOR) 877 { 878 if (!ref_may_be_aliased (rhs)) 879 mark_aliased_reaching_defs_necessary (stmt, rhs); 880 else 881 mark_all_reaching_defs_necessary (stmt); 882 } 883 } 884 else if (greturn *return_stmt = dyn_cast <greturn *> (stmt)) 885 { 886 tree rhs = gimple_return_retval (return_stmt); 887 /* A return statement may perform a load. */ 888 if (rhs 889 && TREE_CODE (rhs) != SSA_NAME 890 && !is_gimple_min_invariant (rhs) 891 && TREE_CODE (rhs) != CONSTRUCTOR) 892 { 893 if (!ref_may_be_aliased (rhs)) 894 mark_aliased_reaching_defs_necessary (stmt, rhs); 895 else 896 mark_all_reaching_defs_necessary (stmt); 897 } 898 } 899 else if (gasm *asm_stmt = dyn_cast <gasm *> (stmt)) 900 { 901 unsigned i; 902 mark_all_reaching_defs_necessary (stmt); 903 /* Inputs may perform loads. */ 904 for (i = 0; i < gimple_asm_ninputs (asm_stmt); ++i) 905 { 906 tree op = TREE_VALUE (gimple_asm_input_op (asm_stmt, i)); 907 if (TREE_CODE (op) != SSA_NAME 908 && !is_gimple_min_invariant (op) 909 && TREE_CODE (op) != CONSTRUCTOR 910 && !ref_may_be_aliased (op)) 911 mark_aliased_reaching_defs_necessary (stmt, op); 912 } 913 } 914 else if (gimple_code (stmt) == GIMPLE_TRANSACTION) 915 { 916 /* The beginning of a transaction is a memory barrier. */ 917 /* ??? If we were really cool, we'd only be a barrier 918 for the memories touched within the transaction. */ 919 mark_all_reaching_defs_necessary (stmt); 920 } 921 else 922 gcc_unreachable (); 923 924 /* If we over-used our alias oracle budget drop to simple 925 mode. The cost metric allows quadratic behavior 926 (number of uses times number of may-defs queries) up to 927 a constant maximal number of queries and after that falls back to 928 super-linear complexity. */ 929 if (/* Constant but quadratic for small functions. */ 930 total_chain > 128 * 128 931 /* Linear in the number of may-defs. */ 932 && total_chain > 32 * longest_chain 933 /* Linear in the number of uses. */ 934 && total_chain > nr_walks * 32) 935 { 936 chain_ovfl = true; 937 if (visited) 938 bitmap_clear (visited); 939 } 940 } 941 } 942 } 943 944 /* Remove dead PHI nodes from block BB. */ 945 946 static bool 947 remove_dead_phis (basic_block bb) 948 { 949 bool something_changed = false; 950 gphi *phi; 951 gphi_iterator gsi; 952 953 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);) 954 { 955 stats.total_phis++; 956 phi = gsi.phi (); 957 958 /* We do not track necessity of virtual PHI nodes. Instead do 959 very simple dead PHI removal here. */ 960 if (virtual_operand_p (gimple_phi_result (phi))) 961 { 962 /* Virtual PHI nodes with one or identical arguments 963 can be removed. */ 964 if (degenerate_phi_p (phi)) 965 { 966 tree vdef = gimple_phi_result (phi); 967 tree vuse = gimple_phi_arg_def (phi, 0); 968 969 use_operand_p use_p; 970 imm_use_iterator iter; 971 gimple *use_stmt; 972 FOR_EACH_IMM_USE_STMT (use_stmt, iter, vdef) 973 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 974 SET_USE (use_p, vuse); 975 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vdef) 976 && TREE_CODE (vuse) == SSA_NAME) 977 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (vuse) = 1; 978 } 979 else 980 gimple_set_plf (phi, STMT_NECESSARY, true); 981 } 982 983 if (!gimple_plf (phi, STMT_NECESSARY)) 984 { 985 something_changed = true; 986 if (dump_file && (dump_flags & TDF_DETAILS)) 987 { 988 fprintf (dump_file, "Deleting : "); 989 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 990 fprintf (dump_file, "\n"); 991 } 992 993 remove_phi_node (&gsi, true); 994 stats.removed_phis++; 995 continue; 996 } 997 998 gsi_next (&gsi); 999 } 1000 return something_changed; 1001 } 1002 1003 1004 /* Remove dead statement pointed to by iterator I. Receives the basic block BB 1005 containing I so that we don't have to look it up. */ 1006 1007 static void 1008 remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb) 1009 { 1010 gimple *stmt = gsi_stmt (*i); 1011 1012 if (dump_file && (dump_flags & TDF_DETAILS)) 1013 { 1014 fprintf (dump_file, "Deleting : "); 1015 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1016 fprintf (dump_file, "\n"); 1017 } 1018 1019 stats.removed++; 1020 1021 /* If we have determined that a conditional branch statement contributes 1022 nothing to the program, then we not only remove it, but we need to update 1023 the CFG. We can chose any of edges out of BB as long as we are sure to not 1024 close infinite loops. This is done by always choosing the edge closer to 1025 exit in inverted_post_order_compute order. */ 1026 if (is_ctrl_stmt (stmt)) 1027 { 1028 edge_iterator ei; 1029 edge e = NULL, e2; 1030 1031 /* See if there is only one non-abnormal edge. */ 1032 if (single_succ_p (bb)) 1033 e = single_succ_edge (bb); 1034 /* Otherwise chose one that is closer to bb with live statement in it. 1035 To be able to chose one, we compute inverted post order starting from 1036 all BBs with live statements. */ 1037 if (!e) 1038 { 1039 if (!bb_postorder) 1040 { 1041 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); 1042 int postorder_num 1043 = inverted_post_order_compute (postorder, 1044 &bb_contains_live_stmts); 1045 bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); 1046 for (int i = 0; i < postorder_num; ++i) 1047 bb_postorder[postorder[i]] = i; 1048 free (postorder); 1049 } 1050 FOR_EACH_EDGE (e2, ei, bb->succs) 1051 if (!e || e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) 1052 || bb_postorder [e->dest->index] 1053 < bb_postorder [e2->dest->index]) 1054 e = e2; 1055 } 1056 gcc_assert (e); 1057 e->probability = REG_BR_PROB_BASE; 1058 e->count = bb->count; 1059 1060 /* The edge is no longer associated with a conditional, so it does 1061 not have TRUE/FALSE flags. 1062 We are also safe to drop EH/ABNORMAL flags and turn them into 1063 normal control flow, because we know that all the destinations (including 1064 those odd edges) are equivalent for program execution. */ 1065 e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_EH | EDGE_ABNORMAL); 1066 1067 /* The lone outgoing edge from BB will be a fallthru edge. */ 1068 e->flags |= EDGE_FALLTHRU; 1069 1070 /* Remove the remaining outgoing edges. */ 1071 for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); ) 1072 if (e != e2) 1073 { 1074 cfg_altered = true; 1075 /* If we made a BB unconditionally exit a loop or removed 1076 an entry into an irreducible region, then this transform 1077 alters the set of BBs in the loop. Schedule a fixup. */ 1078 if (loop_exit_edge_p (bb->loop_father, e) 1079 || (e2->dest->flags & BB_IRREDUCIBLE_LOOP)) 1080 loops_state_set (LOOPS_NEED_FIXUP); 1081 remove_edge (e2); 1082 } 1083 else 1084 ei_next (&ei); 1085 } 1086 1087 /* If this is a store into a variable that is being optimized away, 1088 add a debug bind stmt if possible. */ 1089 if (MAY_HAVE_DEBUG_STMTS 1090 && gimple_assign_single_p (stmt) 1091 && is_gimple_val (gimple_assign_rhs1 (stmt))) 1092 { 1093 tree lhs = gimple_assign_lhs (stmt); 1094 if ((VAR_P (lhs) || TREE_CODE (lhs) == PARM_DECL) 1095 && !DECL_IGNORED_P (lhs) 1096 && is_gimple_reg_type (TREE_TYPE (lhs)) 1097 && !is_global_var (lhs) 1098 && !DECL_HAS_VALUE_EXPR_P (lhs)) 1099 { 1100 tree rhs = gimple_assign_rhs1 (stmt); 1101 gdebug *note 1102 = gimple_build_debug_bind (lhs, unshare_expr (rhs), stmt); 1103 gsi_insert_after (i, note, GSI_SAME_STMT); 1104 } 1105 } 1106 1107 unlink_stmt_vdef (stmt); 1108 gsi_remove (i, true); 1109 release_defs (stmt); 1110 } 1111 1112 /* Helper for maybe_optimize_arith_overflow. Find in *TP if there are any 1113 uses of data (SSA_NAME) other than REALPART_EXPR referencing it. */ 1114 1115 static tree 1116 find_non_realpart_uses (tree *tp, int *walk_subtrees, void *data) 1117 { 1118 if (TYPE_P (*tp) || TREE_CODE (*tp) == REALPART_EXPR) 1119 *walk_subtrees = 0; 1120 if (*tp == (tree) data) 1121 return *tp; 1122 return NULL_TREE; 1123 } 1124 1125 /* If the IMAGPART_EXPR of the {ADD,SUB,MUL}_OVERFLOW result is never used, 1126 but REALPART_EXPR is, optimize the {ADD,SUB,MUL}_OVERFLOW internal calls 1127 into plain unsigned {PLUS,MINUS,MULT}_EXPR, and if needed reset debug 1128 uses. */ 1129 1130 static void 1131 maybe_optimize_arith_overflow (gimple_stmt_iterator *gsi, 1132 enum tree_code subcode) 1133 { 1134 gimple *stmt = gsi_stmt (*gsi); 1135 tree lhs = gimple_call_lhs (stmt); 1136 1137 if (lhs == NULL || TREE_CODE (lhs) != SSA_NAME) 1138 return; 1139 1140 imm_use_iterator imm_iter; 1141 use_operand_p use_p; 1142 bool has_debug_uses = false; 1143 bool has_realpart_uses = false; 1144 bool has_other_uses = false; 1145 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs) 1146 { 1147 gimple *use_stmt = USE_STMT (use_p); 1148 if (is_gimple_debug (use_stmt)) 1149 has_debug_uses = true; 1150 else if (is_gimple_assign (use_stmt) 1151 && gimple_assign_rhs_code (use_stmt) == REALPART_EXPR 1152 && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == lhs) 1153 has_realpart_uses = true; 1154 else 1155 { 1156 has_other_uses = true; 1157 break; 1158 } 1159 } 1160 1161 if (!has_realpart_uses || has_other_uses) 1162 return; 1163 1164 tree arg0 = gimple_call_arg (stmt, 0); 1165 tree arg1 = gimple_call_arg (stmt, 1); 1166 location_t loc = gimple_location (stmt); 1167 tree type = TREE_TYPE (TREE_TYPE (lhs)); 1168 tree utype = type; 1169 if (!TYPE_UNSIGNED (type)) 1170 utype = build_nonstandard_integer_type (TYPE_PRECISION (type), 1); 1171 tree result = fold_build2_loc (loc, subcode, utype, 1172 fold_convert_loc (loc, utype, arg0), 1173 fold_convert_loc (loc, utype, arg1)); 1174 result = fold_convert_loc (loc, type, result); 1175 1176 if (has_debug_uses) 1177 { 1178 gimple *use_stmt; 1179 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, lhs) 1180 { 1181 if (!gimple_debug_bind_p (use_stmt)) 1182 continue; 1183 tree v = gimple_debug_bind_get_value (use_stmt); 1184 if (walk_tree (&v, find_non_realpart_uses, lhs, NULL)) 1185 { 1186 gimple_debug_bind_reset_value (use_stmt); 1187 update_stmt (use_stmt); 1188 } 1189 } 1190 } 1191 1192 if (TREE_CODE (result) == INTEGER_CST && TREE_OVERFLOW (result)) 1193 result = drop_tree_overflow (result); 1194 tree overflow = build_zero_cst (type); 1195 tree ctype = build_complex_type (type); 1196 if (TREE_CODE (result) == INTEGER_CST) 1197 result = build_complex (ctype, result, overflow); 1198 else 1199 result = build2_loc (gimple_location (stmt), COMPLEX_EXPR, 1200 ctype, result, overflow); 1201 1202 if (dump_file && (dump_flags & TDF_DETAILS)) 1203 { 1204 fprintf (dump_file, "Transforming call: "); 1205 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1206 fprintf (dump_file, "because the overflow result is never used into: "); 1207 print_generic_stmt (dump_file, result, TDF_SLIM); 1208 fprintf (dump_file, "\n"); 1209 } 1210 1211 if (!update_call_from_tree (gsi, result)) 1212 gimplify_and_update_call_from_tree (gsi, result); 1213 } 1214 1215 /* Eliminate unnecessary statements. Any instruction not marked as necessary 1216 contributes nothing to the program, and can be deleted. */ 1217 1218 static bool 1219 eliminate_unnecessary_stmts (void) 1220 { 1221 bool something_changed = false; 1222 basic_block bb; 1223 gimple_stmt_iterator gsi, psi; 1224 gimple *stmt; 1225 tree call; 1226 vec<basic_block> h; 1227 1228 if (dump_file && (dump_flags & TDF_DETAILS)) 1229 fprintf (dump_file, "\nEliminating unnecessary statements:\n"); 1230 1231 clear_special_calls (); 1232 1233 /* Walking basic blocks and statements in reverse order avoids 1234 releasing SSA names before any other DEFs that refer to them are 1235 released. This helps avoid loss of debug information, as we get 1236 a chance to propagate all RHSs of removed SSAs into debug uses, 1237 rather than only the latest ones. E.g., consider: 1238 1239 x_3 = y_1 + z_2; 1240 a_5 = x_3 - b_4; 1241 # DEBUG a => a_5 1242 1243 If we were to release x_3 before a_5, when we reached a_5 and 1244 tried to substitute it into the debug stmt, we'd see x_3 there, 1245 but x_3's DEF, type, etc would have already been disconnected. 1246 By going backwards, the debug stmt first changes to: 1247 1248 # DEBUG a => x_3 - b_4 1249 1250 and then to: 1251 1252 # DEBUG a => y_1 + z_2 - b_4 1253 1254 as desired. */ 1255 gcc_assert (dom_info_available_p (CDI_DOMINATORS)); 1256 h = get_all_dominated_blocks (CDI_DOMINATORS, 1257 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))); 1258 1259 while (h.length ()) 1260 { 1261 bb = h.pop (); 1262 1263 /* Remove dead statements. */ 1264 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi) 1265 { 1266 stmt = gsi_stmt (gsi); 1267 1268 psi = gsi; 1269 gsi_prev (&psi); 1270 1271 stats.total++; 1272 1273 /* We can mark a call to free as not necessary if the 1274 defining statement of its argument is not necessary 1275 (and thus is getting removed). */ 1276 if (gimple_plf (stmt, STMT_NECESSARY) 1277 && gimple_call_builtin_p (stmt, BUILT_IN_FREE)) 1278 { 1279 tree ptr = gimple_call_arg (stmt, 0); 1280 if (TREE_CODE (ptr) == SSA_NAME) 1281 { 1282 gimple *def_stmt = SSA_NAME_DEF_STMT (ptr); 1283 if (!gimple_nop_p (def_stmt) 1284 && !gimple_plf (def_stmt, STMT_NECESSARY)) 1285 gimple_set_plf (stmt, STMT_NECESSARY, false); 1286 } 1287 /* We did not propagate necessity for free calls fed 1288 by allocation function to allow unnecessary 1289 alloc-free sequence elimination. For instrumented 1290 calls it also means we did not mark bounds producer 1291 as necessary and it is time to do it in case free 1292 call is not removed. */ 1293 if (gimple_call_with_bounds_p (stmt)) 1294 { 1295 gimple *bounds_def_stmt; 1296 tree bounds = gimple_call_arg (stmt, 1); 1297 gcc_assert (TREE_CODE (bounds) == SSA_NAME); 1298 bounds_def_stmt = SSA_NAME_DEF_STMT (bounds); 1299 if (bounds_def_stmt 1300 && !gimple_plf (bounds_def_stmt, STMT_NECESSARY)) 1301 gimple_set_plf (bounds_def_stmt, STMT_NECESSARY, 1302 gimple_plf (stmt, STMT_NECESSARY)); 1303 } 1304 } 1305 1306 /* If GSI is not necessary then remove it. */ 1307 if (!gimple_plf (stmt, STMT_NECESSARY)) 1308 { 1309 /* Keep clobbers that we can keep live live. */ 1310 if (gimple_clobber_p (stmt)) 1311 { 1312 ssa_op_iter iter; 1313 use_operand_p use_p; 1314 bool dead = false; 1315 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) 1316 { 1317 tree name = USE_FROM_PTR (use_p); 1318 if (!SSA_NAME_IS_DEFAULT_DEF (name) 1319 && !bitmap_bit_p (processed, SSA_NAME_VERSION (name))) 1320 { 1321 dead = true; 1322 break; 1323 } 1324 } 1325 if (!dead) 1326 continue; 1327 } 1328 if (!is_gimple_debug (stmt)) 1329 something_changed = true; 1330 remove_dead_stmt (&gsi, bb); 1331 } 1332 else if (is_gimple_call (stmt)) 1333 { 1334 tree name = gimple_call_lhs (stmt); 1335 1336 notice_special_calls (as_a <gcall *> (stmt)); 1337 1338 /* When LHS of var = call (); is dead, simplify it into 1339 call (); saving one operand. */ 1340 if (name 1341 && TREE_CODE (name) == SSA_NAME 1342 && !bitmap_bit_p (processed, SSA_NAME_VERSION (name)) 1343 /* Avoid doing so for allocation calls which we 1344 did not mark as necessary, it will confuse the 1345 special logic we apply to malloc/free pair removal. */ 1346 && (!(call = gimple_call_fndecl (stmt)) 1347 || DECL_BUILT_IN_CLASS (call) != BUILT_IN_NORMAL 1348 || (DECL_FUNCTION_CODE (call) != BUILT_IN_ALIGNED_ALLOC 1349 && DECL_FUNCTION_CODE (call) != BUILT_IN_MALLOC 1350 && DECL_FUNCTION_CODE (call) != BUILT_IN_CALLOC 1351 && DECL_FUNCTION_CODE (call) != BUILT_IN_ALLOCA 1352 && (DECL_FUNCTION_CODE (call) 1353 != BUILT_IN_ALLOCA_WITH_ALIGN))) 1354 /* Avoid doing so for bndret calls for the same reason. */ 1355 && !chkp_gimple_call_builtin_p (stmt, BUILT_IN_CHKP_BNDRET)) 1356 { 1357 something_changed = true; 1358 if (dump_file && (dump_flags & TDF_DETAILS)) 1359 { 1360 fprintf (dump_file, "Deleting LHS of call: "); 1361 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 1362 fprintf (dump_file, "\n"); 1363 } 1364 1365 gimple_call_set_lhs (stmt, NULL_TREE); 1366 maybe_clean_or_replace_eh_stmt (stmt, stmt); 1367 update_stmt (stmt); 1368 release_ssa_name (name); 1369 1370 /* GOMP_SIMD_LANE or ASAN_POISON without lhs is not 1371 needed. */ 1372 if (gimple_call_internal_p (stmt)) 1373 switch (gimple_call_internal_fn (stmt)) 1374 { 1375 case IFN_GOMP_SIMD_LANE: 1376 case IFN_ASAN_POISON: 1377 remove_dead_stmt (&gsi, bb); 1378 break; 1379 default: 1380 break; 1381 } 1382 } 1383 else if (gimple_call_internal_p (stmt)) 1384 switch (gimple_call_internal_fn (stmt)) 1385 { 1386 case IFN_ADD_OVERFLOW: 1387 maybe_optimize_arith_overflow (&gsi, PLUS_EXPR); 1388 break; 1389 case IFN_SUB_OVERFLOW: 1390 maybe_optimize_arith_overflow (&gsi, MINUS_EXPR); 1391 break; 1392 case IFN_MUL_OVERFLOW: 1393 maybe_optimize_arith_overflow (&gsi, MULT_EXPR); 1394 break; 1395 default: 1396 break; 1397 } 1398 } 1399 } 1400 } 1401 1402 h.release (); 1403 1404 /* Since we don't track liveness of virtual PHI nodes, it is possible that we 1405 rendered some PHI nodes unreachable while they are still in use. 1406 Mark them for renaming. */ 1407 if (cfg_altered) 1408 { 1409 basic_block prev_bb; 1410 1411 find_unreachable_blocks (); 1412 1413 /* Delete all unreachable basic blocks in reverse dominator order. */ 1414 for (bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb; 1415 bb != ENTRY_BLOCK_PTR_FOR_FN (cfun); bb = prev_bb) 1416 { 1417 prev_bb = bb->prev_bb; 1418 1419 if (!bitmap_bit_p (bb_contains_live_stmts, bb->index) 1420 || !(bb->flags & BB_REACHABLE)) 1421 { 1422 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 1423 gsi_next (&gsi)) 1424 if (virtual_operand_p (gimple_phi_result (gsi.phi ()))) 1425 { 1426 bool found = false; 1427 imm_use_iterator iter; 1428 1429 FOR_EACH_IMM_USE_STMT (stmt, iter, 1430 gimple_phi_result (gsi.phi ())) 1431 { 1432 if (!(gimple_bb (stmt)->flags & BB_REACHABLE)) 1433 continue; 1434 if (gimple_code (stmt) == GIMPLE_PHI 1435 || gimple_plf (stmt, STMT_NECESSARY)) 1436 { 1437 found = true; 1438 BREAK_FROM_IMM_USE_STMT (iter); 1439 } 1440 } 1441 if (found) 1442 mark_virtual_phi_result_for_renaming (gsi.phi ()); 1443 } 1444 1445 if (!(bb->flags & BB_REACHABLE)) 1446 { 1447 /* Speed up the removal of blocks that don't 1448 dominate others. Walking backwards, this should 1449 be the common case. ??? Do we need to recompute 1450 dominators because of cfg_altered? */ 1451 if (!MAY_HAVE_DEBUG_STMTS 1452 || !first_dom_son (CDI_DOMINATORS, bb)) 1453 delete_basic_block (bb); 1454 else 1455 { 1456 h = get_all_dominated_blocks (CDI_DOMINATORS, bb); 1457 1458 while (h.length ()) 1459 { 1460 bb = h.pop (); 1461 prev_bb = bb->prev_bb; 1462 /* Rearrangements to the CFG may have failed 1463 to update the dominators tree, so that 1464 formerly-dominated blocks are now 1465 otherwise reachable. */ 1466 if (!!(bb->flags & BB_REACHABLE)) 1467 continue; 1468 delete_basic_block (bb); 1469 } 1470 1471 h.release (); 1472 } 1473 } 1474 } 1475 } 1476 } 1477 FOR_EACH_BB_FN (bb, cfun) 1478 { 1479 /* Remove dead PHI nodes. */ 1480 something_changed |= remove_dead_phis (bb); 1481 } 1482 1483 if (bb_postorder) 1484 free (bb_postorder); 1485 bb_postorder = NULL; 1486 1487 return something_changed; 1488 } 1489 1490 1491 /* Print out removed statement statistics. */ 1492 1493 static void 1494 print_stats (void) 1495 { 1496 float percg; 1497 1498 percg = ((float) stats.removed / (float) stats.total) * 100; 1499 fprintf (dump_file, "Removed %d of %d statements (%d%%)\n", 1500 stats.removed, stats.total, (int) percg); 1501 1502 if (stats.total_phis == 0) 1503 percg = 0; 1504 else 1505 percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100; 1506 1507 fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n", 1508 stats.removed_phis, stats.total_phis, (int) percg); 1509 } 1510 1511 /* Initialization for this pass. Set up the used data structures. */ 1512 1513 static void 1514 tree_dce_init (bool aggressive) 1515 { 1516 memset ((void *) &stats, 0, sizeof (stats)); 1517 1518 if (aggressive) 1519 { 1520 last_stmt_necessary = sbitmap_alloc (last_basic_block_for_fn (cfun)); 1521 bitmap_clear (last_stmt_necessary); 1522 bb_contains_live_stmts = sbitmap_alloc (last_basic_block_for_fn (cfun)); 1523 bitmap_clear (bb_contains_live_stmts); 1524 } 1525 1526 processed = sbitmap_alloc (num_ssa_names + 1); 1527 bitmap_clear (processed); 1528 1529 worklist.create (64); 1530 cfg_altered = false; 1531 } 1532 1533 /* Cleanup after this pass. */ 1534 1535 static void 1536 tree_dce_done (bool aggressive) 1537 { 1538 if (aggressive) 1539 { 1540 delete cd; 1541 sbitmap_free (visited_control_parents); 1542 sbitmap_free (last_stmt_necessary); 1543 sbitmap_free (bb_contains_live_stmts); 1544 bb_contains_live_stmts = NULL; 1545 } 1546 1547 sbitmap_free (processed); 1548 1549 worklist.release (); 1550 } 1551 1552 /* Main routine to eliminate dead code. 1553 1554 AGGRESSIVE controls the aggressiveness of the algorithm. 1555 In conservative mode, we ignore control dependence and simply declare 1556 all but the most trivially dead branches necessary. This mode is fast. 1557 In aggressive mode, control dependences are taken into account, which 1558 results in more dead code elimination, but at the cost of some time. 1559 1560 FIXME: Aggressive mode before PRE doesn't work currently because 1561 the dominance info is not invalidated after DCE1. This is 1562 not an issue right now because we only run aggressive DCE 1563 as the last tree SSA pass, but keep this in mind when you 1564 start experimenting with pass ordering. */ 1565 1566 static unsigned int 1567 perform_tree_ssa_dce (bool aggressive) 1568 { 1569 bool something_changed = 0; 1570 1571 calculate_dominance_info (CDI_DOMINATORS); 1572 1573 /* Preheaders are needed for SCEV to work. 1574 Simple lateches and recorded exits improve chances that loop will 1575 proved to be finite in testcases such as in loop-15.c and loop-24.c */ 1576 bool in_loop_pipeline = scev_initialized_p (); 1577 if (aggressive && ! in_loop_pipeline) 1578 { 1579 scev_initialize (); 1580 loop_optimizer_init (LOOPS_NORMAL 1581 | LOOPS_HAVE_RECORDED_EXITS); 1582 } 1583 1584 tree_dce_init (aggressive); 1585 1586 if (aggressive) 1587 { 1588 /* Compute control dependence. */ 1589 calculate_dominance_info (CDI_POST_DOMINATORS); 1590 cd = new control_dependences (); 1591 1592 visited_control_parents = 1593 sbitmap_alloc (last_basic_block_for_fn (cfun)); 1594 bitmap_clear (visited_control_parents); 1595 1596 mark_dfs_back_edges (); 1597 } 1598 1599 find_obviously_necessary_stmts (aggressive); 1600 1601 if (aggressive && ! in_loop_pipeline) 1602 { 1603 loop_optimizer_finalize (); 1604 scev_finalize (); 1605 } 1606 1607 longest_chain = 0; 1608 total_chain = 0; 1609 nr_walks = 0; 1610 chain_ovfl = false; 1611 visited = BITMAP_ALLOC (NULL); 1612 propagate_necessity (aggressive); 1613 BITMAP_FREE (visited); 1614 1615 something_changed |= eliminate_unnecessary_stmts (); 1616 something_changed |= cfg_altered; 1617 1618 /* We do not update postdominators, so free them unconditionally. */ 1619 free_dominance_info (CDI_POST_DOMINATORS); 1620 1621 /* If we removed paths in the CFG, then we need to update 1622 dominators as well. I haven't investigated the possibility 1623 of incrementally updating dominators. */ 1624 if (cfg_altered) 1625 free_dominance_info (CDI_DOMINATORS); 1626 1627 statistics_counter_event (cfun, "Statements deleted", stats.removed); 1628 statistics_counter_event (cfun, "PHI nodes deleted", stats.removed_phis); 1629 1630 /* Debugging dumps. */ 1631 if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS))) 1632 print_stats (); 1633 1634 tree_dce_done (aggressive); 1635 1636 if (something_changed) 1637 { 1638 free_numbers_of_iterations_estimates (cfun); 1639 if (in_loop_pipeline) 1640 scev_reset (); 1641 return TODO_update_ssa | TODO_cleanup_cfg; 1642 } 1643 return 0; 1644 } 1645 1646 /* Pass entry points. */ 1647 static unsigned int 1648 tree_ssa_dce (void) 1649 { 1650 return perform_tree_ssa_dce (/*aggressive=*/false); 1651 } 1652 1653 static unsigned int 1654 tree_ssa_cd_dce (void) 1655 { 1656 return perform_tree_ssa_dce (/*aggressive=*/optimize >= 2); 1657 } 1658 1659 namespace { 1660 1661 const pass_data pass_data_dce = 1662 { 1663 GIMPLE_PASS, /* type */ 1664 "dce", /* name */ 1665 OPTGROUP_NONE, /* optinfo_flags */ 1666 TV_TREE_DCE, /* tv_id */ 1667 ( PROP_cfg | PROP_ssa ), /* properties_required */ 1668 0, /* properties_provided */ 1669 0, /* properties_destroyed */ 1670 0, /* todo_flags_start */ 1671 0, /* todo_flags_finish */ 1672 }; 1673 1674 class pass_dce : public gimple_opt_pass 1675 { 1676 public: 1677 pass_dce (gcc::context *ctxt) 1678 : gimple_opt_pass (pass_data_dce, ctxt) 1679 {} 1680 1681 /* opt_pass methods: */ 1682 opt_pass * clone () { return new pass_dce (m_ctxt); } 1683 virtual bool gate (function *) { return flag_tree_dce != 0; } 1684 virtual unsigned int execute (function *) { return tree_ssa_dce (); } 1685 1686 }; // class pass_dce 1687 1688 } // anon namespace 1689 1690 gimple_opt_pass * 1691 make_pass_dce (gcc::context *ctxt) 1692 { 1693 return new pass_dce (ctxt); 1694 } 1695 1696 namespace { 1697 1698 const pass_data pass_data_cd_dce = 1699 { 1700 GIMPLE_PASS, /* type */ 1701 "cddce", /* name */ 1702 OPTGROUP_NONE, /* optinfo_flags */ 1703 TV_TREE_CD_DCE, /* tv_id */ 1704 ( PROP_cfg | PROP_ssa ), /* properties_required */ 1705 0, /* properties_provided */ 1706 0, /* properties_destroyed */ 1707 0, /* todo_flags_start */ 1708 0, /* todo_flags_finish */ 1709 }; 1710 1711 class pass_cd_dce : public gimple_opt_pass 1712 { 1713 public: 1714 pass_cd_dce (gcc::context *ctxt) 1715 : gimple_opt_pass (pass_data_cd_dce, ctxt) 1716 {} 1717 1718 /* opt_pass methods: */ 1719 opt_pass * clone () { return new pass_cd_dce (m_ctxt); } 1720 virtual bool gate (function *) { return flag_tree_dce != 0; } 1721 virtual unsigned int execute (function *) { return tree_ssa_cd_dce (); } 1722 1723 }; // class pass_cd_dce 1724 1725 } // anon namespace 1726 1727 gimple_opt_pass * 1728 make_pass_cd_dce (gcc::context *ctxt) 1729 { 1730 return new pass_cd_dce (ctxt); 1731 } 1732