Mercurial > hg > CbC > CbC_gcc
comparison gcc/tree-ssa-dce.c @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 12 Feb 2010 23:39:51 +0900 |
parents | a06113de4d67 |
children | b7f97abdc517 |
comparison
equal
deleted
inserted
replaced
52:c156f1bd5cd9 | 55:77e2b8dfacca |
---|---|
1 /* Dead code elimination pass for the GNU compiler. | 1 /* Dead code elimination pass for the GNU compiler. |
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008 | 2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 |
3 Free Software Foundation, Inc. | 3 Free Software Foundation, Inc. |
4 Contributed by Ben Elliston <bje@redhat.com> | 4 Contributed by Ben Elliston <bje@redhat.com> |
5 and Andrew MacLeod <amacleod@redhat.com> | 5 and Andrew MacLeod <amacleod@redhat.com> |
6 Adapted to use control dependence by Steven Bosscher, SUSE Labs. | 6 Adapted to use control dependence by Steven Bosscher, SUSE Labs. |
7 | 7 |
8 This file is part of GCC. | 8 This file is part of GCC. |
9 | 9 |
10 GCC is free software; you can redistribute it and/or modify it | 10 GCC is free software; you can redistribute it and/or modify it |
11 under the terms of the GNU General Public License as published by the | 11 under the terms of the GNU General Public License as published by the |
12 Free Software Foundation; either version 3, or (at your option) any | 12 Free Software Foundation; either version 3, or (at your option) any |
13 later version. | 13 later version. |
14 | 14 |
15 GCC is distributed in the hope that it will be useful, but WITHOUT | 15 GCC is distributed in the hope that it will be useful, but WITHOUT |
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | 16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | 17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
18 for more details. | 18 for more details. |
19 | 19 |
20 You should have received a copy of the GNU General Public License | 20 You should have received a copy of the GNU General Public License |
21 along with GCC; see the file COPYING3. If not see | 21 along with GCC; see the file COPYING3. If not see |
22 <http://www.gnu.org/licenses/>. */ | 22 <http://www.gnu.org/licenses/>. */ |
23 | 23 |
24 /* Dead code elimination. | 24 /* Dead code elimination. |
85 | 85 |
86 /* Vector indicating that last_stmt if a basic block has already been | 86 /* Vector indicating that last_stmt if a basic block has already been |
87 marked as necessary. */ | 87 marked as necessary. */ |
88 static sbitmap last_stmt_necessary; | 88 static sbitmap last_stmt_necessary; |
89 | 89 |
90 /* Vector indicating that BB contains statements that are live. */ | |
91 static sbitmap bb_contains_live_stmts; | |
92 | |
90 /* Before we can determine whether a control branch is dead, we need to | 93 /* Before we can determine whether a control branch is dead, we need to |
91 compute which blocks are control dependent on which edges. | 94 compute which blocks are control dependent on which edges. |
92 | 95 |
93 We expect each block to be control dependent on very few edges so we | 96 We expect each block to be control dependent on very few edges so we |
94 use a bitmap for each block recording its edges. An array holds the | 97 use a bitmap for each block recording its edges. An array holds the |
216 } | 219 } |
217 | 220 |
218 gimple_set_plf (stmt, STMT_NECESSARY, true); | 221 gimple_set_plf (stmt, STMT_NECESSARY, true); |
219 if (add_to_worklist) | 222 if (add_to_worklist) |
220 VEC_safe_push (gimple, heap, worklist, stmt); | 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); | |
221 } | 226 } |
222 | 227 |
223 | 228 |
224 /* Mark the statement defining operand OP as necessary. */ | 229 /* Mark the statement defining operand OP as necessary. */ |
225 | 230 |
231 | 236 |
232 gcc_assert (op); | 237 gcc_assert (op); |
233 | 238 |
234 ver = SSA_NAME_VERSION (op); | 239 ver = SSA_NAME_VERSION (op); |
235 if (TEST_BIT (processed, ver)) | 240 if (TEST_BIT (processed, ver)) |
236 return; | 241 { |
242 stmt = SSA_NAME_DEF_STMT (op); | |
243 gcc_assert (gimple_nop_p (stmt) | |
244 || gimple_plf (stmt, STMT_NECESSARY)); | |
245 return; | |
246 } | |
237 SET_BIT (processed, ver); | 247 SET_BIT (processed, ver); |
238 | 248 |
239 stmt = SSA_NAME_DEF_STMT (op); | 249 stmt = SSA_NAME_DEF_STMT (op); |
240 gcc_assert (stmt); | 250 gcc_assert (stmt); |
241 | 251 |
242 if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt)) | 252 if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt)) |
243 return; | 253 return; |
244 | 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 | |
245 gimple_set_plf (stmt, STMT_NECESSARY, true); | 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); | |
246 VEC_safe_push (gimple, heap, worklist, stmt); | 266 VEC_safe_push (gimple, heap, worklist, stmt); |
247 } | 267 } |
248 | 268 |
249 | 269 |
250 /* Mark STMT as necessary if it obviously is. Add it to the worklist if | 270 /* Mark STMT as necessary if it obviously is. Add it to the worklist if |
280 return; | 300 return; |
281 | 301 |
282 case GIMPLE_ASM: | 302 case GIMPLE_ASM: |
283 case GIMPLE_RESX: | 303 case GIMPLE_RESX: |
284 case GIMPLE_RETURN: | 304 case GIMPLE_RETURN: |
285 case GIMPLE_CHANGE_DYNAMIC_TYPE: | |
286 mark_stmt_necessary (stmt, true); | 305 mark_stmt_necessary (stmt, true); |
287 return; | 306 return; |
288 | 307 |
289 case GIMPLE_CALL: | 308 case GIMPLE_CALL: |
290 /* Most, but not all function calls are required. Function calls that | 309 /* Most, but not all function calls are required. Function calls that |
301 /* Fall through */ | 320 /* Fall through */ |
302 | 321 |
303 case GIMPLE_ASSIGN: | 322 case GIMPLE_ASSIGN: |
304 if (!lhs) | 323 if (!lhs) |
305 lhs = gimple_assign_lhs (stmt); | 324 lhs = gimple_assign_lhs (stmt); |
306 /* These values are mildly magic bits of the EH runtime. We can't | |
307 see the entire lifetime of these values until landing pads are | |
308 generated. */ | |
309 if (TREE_CODE (lhs) == EXC_PTR_EXPR | |
310 || TREE_CODE (lhs) == FILTER_EXPR) | |
311 { | |
312 mark_stmt_necessary (stmt, true); | |
313 return; | |
314 } | |
315 break; | 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; | |
316 | 336 |
317 case GIMPLE_GOTO: | 337 case GIMPLE_GOTO: |
318 gcc_assert (!simple_goto_p (stmt)); | 338 gcc_assert (!simple_goto_p (stmt)); |
319 mark_stmt_necessary (stmt, true); | 339 mark_stmt_necessary (stmt, true); |
320 return; | 340 return; |
371 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); | 391 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); |
372 | 392 |
373 if (TEST_BIT (last_stmt_necessary, cd_bb->index)) | 393 if (TEST_BIT (last_stmt_necessary, cd_bb->index)) |
374 continue; | 394 continue; |
375 SET_BIT (last_stmt_necessary, cd_bb->index); | 395 SET_BIT (last_stmt_necessary, cd_bb->index); |
396 SET_BIT (bb_contains_live_stmts, cd_bb->index); | |
376 | 397 |
377 stmt = last_stmt (cd_bb); | 398 stmt = last_stmt (cd_bb); |
378 if (stmt && is_ctrl_stmt (stmt)) | 399 if (stmt && is_ctrl_stmt (stmt)) |
379 mark_stmt_necessary (stmt, true); | 400 mark_stmt_necessary (stmt, true); |
380 } | 401 } |
412 gimple_set_plf (stmt, STMT_NECESSARY, false); | 433 gimple_set_plf (stmt, STMT_NECESSARY, false); |
413 mark_stmt_if_obviously_necessary (stmt, el != NULL); | 434 mark_stmt_if_obviously_necessary (stmt, el != NULL); |
414 } | 435 } |
415 } | 436 } |
416 | 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. */ | |
417 if (el) | 446 if (el) |
418 { | 447 { |
419 /* Prevent the loops from being removed. We must keep the infinite loops, | 448 loop_iterator li; |
420 and we currently do not have a means to recognize the finite ones. */ | 449 struct loop *loop; |
421 FOR_EACH_BB (bb) | 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 | |
480 static bool | |
481 ref_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 | |
489 static bitmap visited = NULL; | |
490 static unsigned int longest_chain = 0; | |
491 static unsigned int total_chain = 0; | |
492 static unsigned int nr_walks = 0; | |
493 static 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 | |
502 static bool | |
503 mark_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) | |
422 { | 521 { |
423 edge_iterator ei; | 522 /* For a must-alias check we need to be able to constrain |
424 FOR_EACH_EDGE (e, ei, bb->succs) | 523 the accesses properly. */ |
425 if (e->flags & EDGE_DFS_BACK) | 524 if (size != -1 && size == max_size |
426 mark_control_dependent_edges_necessary (e->dest, el); | 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; | |
427 } | 541 } |
428 } | 542 } |
429 } | 543 |
430 | 544 /* Otherwise keep walking. */ |
545 return false; | |
546 } | |
547 | |
548 static void | |
549 mark_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 | |
570 static bool | |
571 mark_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 | |
600 static void | |
601 mark_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. */ | |
609 static bool | |
610 degenerate_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 } | |
431 | 619 |
432 /* Propagate necessity using the operands of necessary statements. | 620 /* Propagate necessity using the operands of necessary statements. |
433 Process the uses on each statement in the worklist, and add all | 621 Process the uses on each statement in the worklist, and add all |
434 feeding statements which contribute to the calculation of this | 622 feeding statements which contribute to the calculation of this |
435 value to the worklist. | 623 value to the worklist. |
436 | 624 |
437 In conservative mode, EL is NULL. */ | 625 In conservative mode, EL is NULL. */ |
438 | 626 |
439 static void | 627 static void |
440 propagate_necessity (struct edge_list *el) | 628 propagate_necessity (struct edge_list *el) |
441 { | 629 { |
442 gimple stmt; | 630 gimple stmt; |
443 bool aggressive = (el ? true : false); | 631 bool aggressive = (el ? true : false); |
444 | 632 |
445 if (dump_file && (dump_flags & TDF_DETAILS)) | 633 if (dump_file && (dump_flags & TDF_DETAILS)) |
446 fprintf (dump_file, "\nProcessing worklist:\n"); | 634 fprintf (dump_file, "\nProcessing worklist:\n"); |
447 | 635 |
448 while (VEC_length (gimple, worklist) > 0) | 636 while (VEC_length (gimple, worklist) > 0) |
469 SET_BIT (visited_control_parents, bb->index); | 657 SET_BIT (visited_control_parents, bb->index); |
470 mark_control_dependent_edges_necessary (bb, el); | 658 mark_control_dependent_edges_necessary (bb, el); |
471 } | 659 } |
472 } | 660 } |
473 | 661 |
474 if (gimple_code (stmt) == GIMPLE_PHI) | 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))) | |
475 { | 666 { |
476 /* PHI nodes are somewhat special in that each PHI alternative has | 667 /* PHI nodes are somewhat special in that each PHI alternative has |
477 data and control dependencies. All the statements feeding the | 668 data and control dependencies. All the statements feeding the |
478 PHI node's arguments are always necessary. In aggressive mode, | 669 PHI node's arguments are always necessary. In aggressive mode, |
479 we also consider the control dependent edges leading to the | 670 we also consider the control dependent edges leading to the |
486 tree arg = PHI_ARG_DEF (stmt, k); | 677 tree arg = PHI_ARG_DEF (stmt, k); |
487 if (TREE_CODE (arg) == SSA_NAME) | 678 if (TREE_CODE (arg) == SSA_NAME) |
488 mark_operand_necessary (arg); | 679 mark_operand_necessary (arg); |
489 } | 680 } |
490 | 681 |
491 if (aggressive) | 682 if (aggressive && !degenerate_phi_p (stmt)) |
492 { | 683 { |
493 for (k = 0; k < gimple_phi_num_args (stmt); k++) | 684 for (k = 0; k < gimple_phi_num_args (stmt); k++) |
494 { | 685 { |
495 basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src; | 686 basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src; |
496 if (arg_bb != ENTRY_BLOCK_PTR | 687 if (arg_bb != ENTRY_BLOCK_PTR |
503 } | 694 } |
504 } | 695 } |
505 else | 696 else |
506 { | 697 { |
507 /* Propagate through the operands. Examine all the USE, VUSE and | 698 /* Propagate through the operands. Examine all the USE, VUSE and |
508 VDEF operands in this statement. Mark all the statements | 699 VDEF operands in this statement. Mark all the statements |
509 which feed this statement's uses as necessary. The | 700 which feed this statement's uses as necessary. */ |
510 operands of VDEF expressions are also needed as they | |
511 represent potential definitions that may reach this | |
512 statement (VDEF operands allow us to follow def-def | |
513 links). */ | |
514 ssa_op_iter iter; | 701 ssa_op_iter iter; |
515 tree use; | 702 tree use; |
516 | 703 |
517 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES) | 704 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) |
518 mark_operand_necessary (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 } | |
519 } | 823 } |
520 } | 824 } |
521 } | 825 } |
522 | 826 |
827 /* Replace all uses of result of PHI by underlying variable and mark it | |
828 for renaming. */ | |
829 | |
830 void | |
831 mark_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 } | |
523 | 858 |
524 /* Remove dead PHI nodes from block BB. */ | 859 /* Remove dead PHI nodes from block BB. */ |
525 | 860 |
526 static bool | 861 static bool |
527 remove_dead_phis (basic_block bb) | 862 remove_dead_phis (basic_block bb) |
535 for (gsi = gsi_start (phis); !gsi_end_p (gsi);) | 870 for (gsi = gsi_start (phis); !gsi_end_p (gsi);) |
536 { | 871 { |
537 stats.total_phis++; | 872 stats.total_phis++; |
538 phi = gsi_stmt (gsi); | 873 phi = gsi_stmt (gsi); |
539 | 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 | |
540 if (!gimple_plf (phi, STMT_NECESSARY)) | 900 if (!gimple_plf (phi, STMT_NECESSARY)) |
541 { | 901 { |
542 something_changed = true; | 902 something_changed = true; |
543 if (dump_file && (dump_flags & TDF_DETAILS)) | 903 if (dump_file && (dump_flags & TDF_DETAILS)) |
544 { | 904 { |
547 fprintf (dump_file, "\n"); | 907 fprintf (dump_file, "\n"); |
548 } | 908 } |
549 | 909 |
550 remove_phi_node (&gsi, true); | 910 remove_phi_node (&gsi, true); |
551 stats.removed_phis++; | 911 stats.removed_phis++; |
912 continue; | |
552 } | 913 } |
553 else | 914 |
915 gsi_next (&gsi); | |
916 } | |
917 return something_changed; | |
918 } | |
919 | |
920 /* Find first live post dominator of BB. */ | |
921 | |
922 static basic_block | |
923 get_live_post_dom (basic_block bb) | |
924 { | |
925 basic_block post_dom_bb; | |
926 | |
927 | |
928 /* The post dominance info has to be up-to-date. */ | |
929 gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK); | |
930 | |
931 /* Get the immediate post dominator of bb. */ | |
932 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); | |
933 /* And look for first live one. */ | |
934 while (post_dom_bb != EXIT_BLOCK_PTR | |
935 && !TEST_BIT (bb_contains_live_stmts, post_dom_bb->index)) | |
936 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, post_dom_bb); | |
937 | |
938 return post_dom_bb; | |
939 } | |
940 | |
941 /* Forward edge E to respective POST_DOM_BB and update PHIs. */ | |
942 | |
943 static edge | |
944 forward_edge_to_pdom (edge e, basic_block post_dom_bb) | |
945 { | |
946 gimple_stmt_iterator gsi; | |
947 edge e2 = NULL; | |
948 edge_iterator ei; | |
949 | |
950 if (dump_file && (dump_flags & TDF_DETAILS)) | |
951 fprintf (dump_file, "Redirecting edge %i->%i to %i\n", e->src->index, | |
952 e->dest->index, post_dom_bb->index); | |
953 | |
954 e2 = redirect_edge_and_branch (e, post_dom_bb); | |
955 cfg_altered = true; | |
956 | |
957 /* If edge was already around, no updating is neccesary. */ | |
958 if (e2 != e) | |
959 return e2; | |
960 | |
961 if (phi_nodes (post_dom_bb)) | |
962 { | |
963 /* We are sure that for every live PHI we are seeing control dependent BB. | |
964 This means that we can look up the end of control dependent path leading | |
965 to the PHI itself. */ | |
966 FOR_EACH_EDGE (e2, ei, post_dom_bb->preds) | |
967 if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src)) | |
968 break; | |
969 for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);) | |
554 { | 970 { |
555 gsi_next (&gsi); | 971 gimple phi = gsi_stmt (gsi); |
972 tree op; | |
973 source_location locus; | |
974 | |
975 /* Dead PHI do not imply control dependency. */ | |
976 if (!gimple_plf (phi, STMT_NECESSARY) | |
977 && is_gimple_reg (gimple_phi_result (phi))) | |
978 { | |
979 gsi_next (&gsi); | |
980 continue; | |
981 } | |
982 if (gimple_phi_arg_def (phi, e->dest_idx)) | |
983 { | |
984 gsi_next (&gsi); | |
985 continue; | |
986 } | |
987 | |
988 /* We didn't find edge to update. This can happen for PHIs on virtuals | |
989 since there is no control dependency relation on them. We are lost | |
990 here and must force renaming of the symbol. */ | |
991 if (!is_gimple_reg (gimple_phi_result (phi))) | |
992 { | |
993 mark_virtual_phi_result_for_renaming (phi); | |
994 remove_phi_node (&gsi, true); | |
995 continue; | |
996 } | |
997 if (!e2) | |
998 { | |
999 op = gimple_phi_arg_def (phi, e->dest_idx == 0 ? 1 : 0); | |
1000 locus = gimple_phi_arg_location (phi, e->dest_idx == 0 ? 1 : 0); | |
1001 } | |
1002 else | |
1003 { | |
1004 op = gimple_phi_arg_def (phi, e2->dest_idx); | |
1005 locus = gimple_phi_arg_location (phi, e2->dest_idx); | |
1006 } | |
1007 add_phi_arg (phi, op, e, locus); | |
1008 gcc_assert (e2 || degenerate_phi_p (phi)); | |
1009 gsi_next (&gsi); | |
556 } | 1010 } |
557 } | 1011 } |
558 return something_changed; | 1012 return e; |
559 } | 1013 } |
560 | |
561 | 1014 |
562 /* Remove dead statement pointed to by iterator I. Receives the basic block BB | 1015 /* Remove dead statement pointed to by iterator I. Receives the basic block BB |
563 containing I so that we don't have to look it up. */ | 1016 containing I so that we don't have to look it up. */ |
564 | 1017 |
565 static void | 1018 static void |
583 removed by cleanup_tree_cfg if this change in the flow graph makes them | 1036 removed by cleanup_tree_cfg if this change in the flow graph makes them |
584 unreachable. */ | 1037 unreachable. */ |
585 if (is_ctrl_stmt (stmt)) | 1038 if (is_ctrl_stmt (stmt)) |
586 { | 1039 { |
587 basic_block post_dom_bb; | 1040 basic_block post_dom_bb; |
588 | 1041 edge e, e2; |
589 /* The post dominance info has to be up-to-date. */ | 1042 edge_iterator ei; |
590 gcc_assert (dom_info_state (CDI_POST_DOMINATORS) == DOM_OK); | 1043 |
591 /* Get the immediate post dominator of bb. */ | 1044 post_dom_bb = get_live_post_dom (bb); |
592 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); | 1045 |
593 | 1046 e = find_edge (bb, post_dom_bb); |
594 /* There are three particularly problematical cases. | 1047 |
595 | 1048 /* If edge is already there, try to use it. This avoids need to update |
596 1. Blocks that do not have an immediate post dominator. This | 1049 PHI nodes. Also watch for cases where post dominator does not exists |
597 can happen with infinite loops. | 1050 or is exit block. These can happen for infinite loops as we create |
598 | 1051 fake edges in the dominator tree. */ |
599 2. Blocks that are only post dominated by the exit block. These | 1052 if (e) |
600 can also happen for infinite loops as we create fake edges | 1053 ; |
601 in the dominator tree. | 1054 else if (! post_dom_bb || post_dom_bb == EXIT_BLOCK_PTR) |
602 | 1055 e = EDGE_SUCC (bb, 0); |
603 3. If the post dominator has PHI nodes we may be able to compute | |
604 the right PHI args for them. | |
605 | |
606 In each of these cases we must remove the control statement | |
607 as it may reference SSA_NAMEs which are going to be removed and | |
608 we remove all but one outgoing edge from the block. */ | |
609 if (! post_dom_bb | |
610 || post_dom_bb == EXIT_BLOCK_PTR | |
611 || phi_nodes (post_dom_bb)) | |
612 ; | |
613 else | 1056 else |
614 { | 1057 e = forward_edge_to_pdom (EDGE_SUCC (bb, 0), post_dom_bb); |
615 /* Redirect the first edge out of BB to reach POST_DOM_BB. */ | 1058 gcc_assert (e); |
616 redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb); | 1059 e->probability = REG_BR_PROB_BASE; |
617 PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL; | 1060 e->count = bb->count; |
618 | |
619 /* It is not sufficient to set cfg_altered below during edge | |
620 removal, in case BB has two successors and one of them | |
621 is POST_DOM_BB. */ | |
622 cfg_altered = true; | |
623 } | |
624 EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; | |
625 EDGE_SUCC (bb, 0)->count = bb->count; | |
626 | 1061 |
627 /* The edge is no longer associated with a conditional, so it does | 1062 /* The edge is no longer associated with a conditional, so it does |
628 not have TRUE/FALSE flags. */ | 1063 not have TRUE/FALSE flags. */ |
629 EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); | 1064 e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); |
630 | 1065 |
631 /* The lone outgoing edge from BB will be a fallthru edge. */ | 1066 /* The lone outgoing edge from BB will be a fallthru edge. */ |
632 EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU; | 1067 e->flags |= EDGE_FALLTHRU; |
633 | 1068 |
634 /* Remove the remaining the outgoing edges. */ | 1069 /* Remove the remaining outgoing edges. */ |
635 while (!single_succ_p (bb)) | 1070 for (ei = ei_start (bb->succs); (e2 = ei_safe_edge (ei)); ) |
636 { | 1071 if (e != e2) |
637 /* FIXME. When we remove the edge, we modify the CFG, which | 1072 { |
638 in turn modifies the dominator and post-dominator tree. | 1073 cfg_altered = true; |
639 Is it safe to postpone recomputing the dominator and | 1074 remove_edge (e2); |
640 post-dominator tree until the end of this pass given that | 1075 } |
641 the post-dominators are used above? */ | 1076 else |
642 cfg_altered = true; | 1077 ei_next (&ei); |
643 remove_edge (EDGE_SUCC (bb, 1)); | 1078 } |
644 } | 1079 |
645 } | 1080 unlink_stmt_vdef (stmt); |
646 | 1081 gsi_remove (i, true); |
647 gsi_remove (i, true); | 1082 release_defs (stmt); |
648 release_defs (stmt); | 1083 } |
649 } | |
650 | |
651 | 1084 |
652 /* Eliminate unnecessary statements. Any instruction not marked as necessary | 1085 /* Eliminate unnecessary statements. Any instruction not marked as necessary |
653 contributes nothing to the program, and can be deleted. */ | 1086 contributes nothing to the program, and can be deleted. */ |
654 | 1087 |
655 static bool | 1088 static bool |
656 eliminate_unnecessary_stmts (void) | 1089 eliminate_unnecessary_stmts (void) |
657 { | 1090 { |
658 bool something_changed = false; | 1091 bool something_changed = false; |
659 basic_block bb; | 1092 basic_block bb; |
660 gimple_stmt_iterator gsi; | 1093 gimple_stmt_iterator gsi, psi; |
661 gimple stmt; | 1094 gimple stmt; |
662 tree call; | 1095 tree call; |
1096 VEC (basic_block, heap) *h; | |
663 | 1097 |
664 if (dump_file && (dump_flags & TDF_DETAILS)) | 1098 if (dump_file && (dump_flags & TDF_DETAILS)) |
665 fprintf (dump_file, "\nEliminating unnecessary statements:\n"); | 1099 fprintf (dump_file, "\nEliminating unnecessary statements:\n"); |
666 | 1100 |
667 clear_special_calls (); | 1101 clear_special_calls (); |
668 FOR_EACH_BB (bb) | 1102 |
669 { | 1103 /* Walking basic blocks and statements in reverse order avoids |
670 /* Remove dead PHI nodes. */ | 1104 releasing SSA names before any other DEFs that refer to them are |
671 something_changed |= remove_dead_phis (bb); | 1105 released. This helps avoid loss of debug information, as we get |
672 } | 1106 a chance to propagate all RHSs of removed SSAs into debug uses, |
673 | 1107 rather than only the latest ones. E.g., consider: |
674 FOR_EACH_BB (bb) | 1108 |
675 { | 1109 x_3 = y_1 + z_2; |
1110 a_5 = x_3 - b_4; | |
1111 # DEBUG a => a_5 | |
1112 | |
1113 If we were to release x_3 before a_5, when we reached a_5 and | |
1114 tried to substitute it into the debug stmt, we'd see x_3 there, | |
1115 but x_3's DEF, type, etc would have already been disconnected. | |
1116 By going backwards, the debug stmt first changes to: | |
1117 | |
1118 # DEBUG a => x_3 - b_4 | |
1119 | |
1120 and then to: | |
1121 | |
1122 # DEBUG a => y_1 + z_2 - b_4 | |
1123 | |
1124 as desired. */ | |
1125 gcc_assert (dom_info_available_p (CDI_DOMINATORS)); | |
1126 h = get_all_dominated_blocks (CDI_DOMINATORS, single_succ (ENTRY_BLOCK_PTR)); | |
1127 | |
1128 while (VEC_length (basic_block, h)) | |
1129 { | |
1130 bb = VEC_pop (basic_block, h); | |
1131 | |
676 /* Remove dead statements. */ | 1132 /* Remove dead statements. */ |
677 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) | 1133 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi = psi) |
678 { | 1134 { |
679 stmt = gsi_stmt (gsi); | 1135 stmt = gsi_stmt (gsi); |
680 | 1136 |
1137 psi = gsi; | |
1138 gsi_prev (&psi); | |
1139 | |
681 stats.total++; | 1140 stats.total++; |
682 | 1141 |
683 /* If GSI is not necessary then remove it. */ | 1142 /* If GSI is not necessary then remove it. */ |
684 if (!gimple_plf (stmt, STMT_NECESSARY)) | 1143 if (!gimple_plf (stmt, STMT_NECESSARY)) |
685 { | 1144 { |
1145 if (!is_gimple_debug (stmt)) | |
1146 something_changed = true; | |
686 remove_dead_stmt (&gsi, bb); | 1147 remove_dead_stmt (&gsi, bb); |
687 something_changed = true; | |
688 } | 1148 } |
689 else if (is_gimple_call (stmt)) | 1149 else if (is_gimple_call (stmt)) |
690 { | 1150 { |
691 call = gimple_call_fndecl (stmt); | 1151 call = gimple_call_fndecl (stmt); |
692 if (call) | 1152 if (call) |
693 { | 1153 { |
694 tree name; | 1154 tree name; |
695 gimple g; | |
696 | 1155 |
697 /* When LHS of var = call (); is dead, simplify it into | 1156 /* When LHS of var = call (); is dead, simplify it into |
698 call (); saving one operand. */ | 1157 call (); saving one operand. */ |
699 name = gimple_call_lhs (stmt); | 1158 name = gimple_call_lhs (stmt); |
700 if (name && TREE_CODE (name) == SSA_NAME | 1159 if (name && TREE_CODE (name) == SSA_NAME |
705 { | 1164 { |
706 fprintf (dump_file, "Deleting LHS of call: "); | 1165 fprintf (dump_file, "Deleting LHS of call: "); |
707 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | 1166 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
708 fprintf (dump_file, "\n"); | 1167 fprintf (dump_file, "\n"); |
709 } | 1168 } |
710 | 1169 |
711 push_stmt_changes (gsi_stmt_ptr (&gsi)); | 1170 gimple_call_set_lhs (stmt, NULL_TREE); |
712 g = gimple_copy (stmt); | 1171 maybe_clean_or_replace_eh_stmt (stmt, stmt); |
713 gimple_call_set_lhs (g, NULL_TREE); | 1172 update_stmt (stmt); |
714 gsi_replace (&gsi, g, false); | |
715 maybe_clean_or_replace_eh_stmt (stmt, g); | |
716 mark_symbols_for_renaming (g); | |
717 pop_stmt_changes (gsi_stmt_ptr (&gsi)); | |
718 release_ssa_name (name); | 1173 release_ssa_name (name); |
719 } | 1174 } |
720 notice_special_calls (stmt); | 1175 notice_special_calls (stmt); |
721 } | 1176 } |
722 gsi_next (&gsi); | |
723 } | |
724 else | |
725 { | |
726 gsi_next (&gsi); | |
727 } | 1177 } |
728 } | 1178 } |
1179 } | |
1180 | |
1181 VEC_free (basic_block, heap, h); | |
1182 | |
1183 /* Since we don't track liveness of virtual PHI nodes, it is possible that we | |
1184 rendered some PHI nodes unreachable while they are still in use. | |
1185 Mark them for renaming. */ | |
1186 if (cfg_altered) | |
1187 { | |
1188 basic_block prev_bb; | |
1189 | |
1190 find_unreachable_blocks (); | |
1191 | |
1192 /* Delete all unreachable basic blocks in reverse dominator order. */ | |
1193 for (bb = EXIT_BLOCK_PTR->prev_bb; bb != ENTRY_BLOCK_PTR; bb = prev_bb) | |
1194 { | |
1195 prev_bb = bb->prev_bb; | |
1196 | |
1197 if (!TEST_BIT (bb_contains_live_stmts, bb->index) | |
1198 || !(bb->flags & BB_REACHABLE)) | |
1199 { | |
1200 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
1201 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi)))) | |
1202 { | |
1203 bool found = false; | |
1204 imm_use_iterator iter; | |
1205 | |
1206 FOR_EACH_IMM_USE_STMT (stmt, iter, gimple_phi_result (gsi_stmt (gsi))) | |
1207 { | |
1208 if (!(gimple_bb (stmt)->flags & BB_REACHABLE)) | |
1209 continue; | |
1210 if (gimple_code (stmt) == GIMPLE_PHI | |
1211 || gimple_plf (stmt, STMT_NECESSARY)) | |
1212 { | |
1213 found = true; | |
1214 BREAK_FROM_IMM_USE_STMT (iter); | |
1215 } | |
1216 } | |
1217 if (found) | |
1218 mark_virtual_phi_result_for_renaming (gsi_stmt (gsi)); | |
1219 } | |
1220 | |
1221 if (!(bb->flags & BB_REACHABLE)) | |
1222 { | |
1223 /* Speed up the removal of blocks that don't | |
1224 dominate others. Walking backwards, this should | |
1225 be the common case. ??? Do we need to recompute | |
1226 dominators because of cfg_altered? */ | |
1227 if (!MAY_HAVE_DEBUG_STMTS | |
1228 || !first_dom_son (CDI_DOMINATORS, bb)) | |
1229 delete_basic_block (bb); | |
1230 else | |
1231 { | |
1232 h = get_all_dominated_blocks (CDI_DOMINATORS, bb); | |
1233 | |
1234 while (VEC_length (basic_block, h)) | |
1235 { | |
1236 bb = VEC_pop (basic_block, h); | |
1237 prev_bb = bb->prev_bb; | |
1238 /* Rearrangements to the CFG may have failed | |
1239 to update the dominators tree, so that | |
1240 formerly-dominated blocks are now | |
1241 otherwise reachable. */ | |
1242 if (!!(bb->flags & BB_REACHABLE)) | |
1243 continue; | |
1244 delete_basic_block (bb); | |
1245 } | |
1246 | |
1247 VEC_free (basic_block, heap, h); | |
1248 } | |
1249 } | |
1250 } | |
1251 } | |
1252 } | |
1253 FOR_EACH_BB (bb) | |
1254 { | |
1255 /* Remove dead PHI nodes. */ | |
1256 something_changed |= remove_dead_phis (bb); | |
729 } | 1257 } |
730 | 1258 |
731 return something_changed; | 1259 return something_changed; |
732 } | 1260 } |
733 | 1261 |
767 for (i = 0; i < last_basic_block; ++i) | 1295 for (i = 0; i < last_basic_block; ++i) |
768 control_dependence_map[i] = BITMAP_ALLOC (NULL); | 1296 control_dependence_map[i] = BITMAP_ALLOC (NULL); |
769 | 1297 |
770 last_stmt_necessary = sbitmap_alloc (last_basic_block); | 1298 last_stmt_necessary = sbitmap_alloc (last_basic_block); |
771 sbitmap_zero (last_stmt_necessary); | 1299 sbitmap_zero (last_stmt_necessary); |
1300 bb_contains_live_stmts = sbitmap_alloc (last_basic_block); | |
1301 sbitmap_zero (bb_contains_live_stmts); | |
772 } | 1302 } |
773 | 1303 |
774 processed = sbitmap_alloc (num_ssa_names + 1); | 1304 processed = sbitmap_alloc (num_ssa_names + 1); |
775 sbitmap_zero (processed); | 1305 sbitmap_zero (processed); |
776 | 1306 |
791 BITMAP_FREE (control_dependence_map[i]); | 1321 BITMAP_FREE (control_dependence_map[i]); |
792 free (control_dependence_map); | 1322 free (control_dependence_map); |
793 | 1323 |
794 sbitmap_free (visited_control_parents); | 1324 sbitmap_free (visited_control_parents); |
795 sbitmap_free (last_stmt_necessary); | 1325 sbitmap_free (last_stmt_necessary); |
1326 sbitmap_free (bb_contains_live_stmts); | |
1327 bb_contains_live_stmts = NULL; | |
796 } | 1328 } |
797 | 1329 |
798 sbitmap_free (processed); | 1330 sbitmap_free (processed); |
799 | 1331 |
800 VEC_free (gimple, heap, worklist); | 1332 VEC_free (gimple, heap, worklist); |
817 static unsigned int | 1349 static unsigned int |
818 perform_tree_ssa_dce (bool aggressive) | 1350 perform_tree_ssa_dce (bool aggressive) |
819 { | 1351 { |
820 struct edge_list *el = NULL; | 1352 struct edge_list *el = NULL; |
821 bool something_changed = 0; | 1353 bool something_changed = 0; |
1354 | |
1355 /* Preheaders are needed for SCEV to work. | |
1356 Simple lateches and recorded exits improve chances that loop will | |
1357 proved to be finite in testcases such as in loop-15.c and loop-24.c */ | |
1358 if (aggressive) | |
1359 loop_optimizer_init (LOOPS_NORMAL | |
1360 | LOOPS_HAVE_RECORDED_EXITS); | |
822 | 1361 |
823 tree_dce_init (aggressive); | 1362 tree_dce_init (aggressive); |
824 | 1363 |
825 if (aggressive) | 1364 if (aggressive) |
826 { | 1365 { |
837 mark_dfs_back_edges (); | 1376 mark_dfs_back_edges (); |
838 } | 1377 } |
839 | 1378 |
840 find_obviously_necessary_stmts (el); | 1379 find_obviously_necessary_stmts (el); |
841 | 1380 |
1381 if (aggressive) | |
1382 loop_optimizer_finalize (); | |
1383 | |
1384 longest_chain = 0; | |
1385 total_chain = 0; | |
1386 nr_walks = 0; | |
1387 chain_ovfl = false; | |
1388 visited = BITMAP_ALLOC (NULL); | |
842 propagate_necessity (el); | 1389 propagate_necessity (el); |
1390 BITMAP_FREE (visited); | |
843 | 1391 |
844 something_changed |= eliminate_unnecessary_stmts (); | 1392 something_changed |= eliminate_unnecessary_stmts (); |
845 something_changed |= cfg_altered; | 1393 something_changed |= cfg_altered; |
846 | 1394 |
847 /* We do not update postdominators, so free them unconditionally. */ | 1395 /* We do not update postdominators, so free them unconditionally. */ |
863 tree_dce_done (aggressive); | 1411 tree_dce_done (aggressive); |
864 | 1412 |
865 free_edge_list (el); | 1413 free_edge_list (el); |
866 | 1414 |
867 if (something_changed) | 1415 if (something_changed) |
868 return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect | 1416 return (TODO_update_ssa | TODO_cleanup_cfg | TODO_ggc_collect |
869 | TODO_remove_unused_locals); | 1417 | TODO_remove_unused_locals); |
870 else | 1418 else |
871 return 0; | 1419 return 0; |
872 } | 1420 } |
873 | 1421 |