Mercurial > hg > CbC > CbC_gcc
comparison gcc/tree-ssa-dce.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 24 May 2010 12:47:05 +0900 |
parents | 77e2b8dfacca |
children | f6334be47118 |
comparison
equal
deleted
inserted
replaced
56:3c8a44c06a95 | 63:b7f97abdc517 |
---|---|
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, 2009 | 2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 |
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 |
45 | 45 |
46 #include "config.h" | 46 #include "config.h" |
47 #include "system.h" | 47 #include "system.h" |
48 #include "coretypes.h" | 48 #include "coretypes.h" |
49 #include "tm.h" | 49 #include "tm.h" |
50 #include "ggc.h" | |
51 | |
52 /* These RTL headers are needed for basic-block.h. */ | |
53 #include "rtl.h" | |
54 #include "tm_p.h" | |
55 #include "hard-reg-set.h" | |
56 #include "obstack.h" | |
57 #include "basic-block.h" | |
58 | 50 |
59 #include "tree.h" | 51 #include "tree.h" |
60 #include "diagnostic.h" | 52 #include "diagnostic.h" |
53 #include "tree-pretty-print.h" | |
54 #include "gimple-pretty-print.h" | |
55 #include "basic-block.h" | |
61 #include "tree-flow.h" | 56 #include "tree-flow.h" |
62 #include "gimple.h" | 57 #include "gimple.h" |
63 #include "tree-dump.h" | 58 #include "tree-dump.h" |
64 #include "tree-pass.h" | 59 #include "tree-pass.h" |
65 #include "timevar.h" | 60 #include "timevar.h" |
371 } | 366 } |
372 | 367 |
373 | 368 |
374 /* Make corresponding control dependent edges necessary. We only | 369 /* Make corresponding control dependent edges necessary. We only |
375 have to do this once for each basic block, so we clear the bitmap | 370 have to do this once for each basic block, so we clear the bitmap |
376 after we're done. */ | 371 after we're done. |
372 | |
373 When IGNORE_SELF it true, ignore BB from the list of control dependences. */ | |
377 static void | 374 static void |
378 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el) | 375 mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el, bool ignore_self) |
379 { | 376 { |
380 bitmap_iterator bi; | 377 bitmap_iterator bi; |
381 unsigned edge_number; | 378 unsigned edge_number; |
379 bool skipped = false; | |
382 | 380 |
383 gcc_assert (bb != EXIT_BLOCK_PTR); | 381 gcc_assert (bb != EXIT_BLOCK_PTR); |
384 | 382 |
385 if (bb == ENTRY_BLOCK_PTR) | 383 if (bb == ENTRY_BLOCK_PTR) |
386 return; | 384 return; |
387 | 385 |
388 EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number) | 386 EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number) |
389 { | 387 { |
390 gimple stmt; | 388 gimple stmt; |
391 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); | 389 basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number); |
390 | |
391 if (ignore_self && cd_bb == bb) | |
392 { | |
393 skipped = true; | |
394 continue; | |
395 } | |
392 | 396 |
393 if (TEST_BIT (last_stmt_necessary, cd_bb->index)) | 397 if (TEST_BIT (last_stmt_necessary, cd_bb->index)) |
394 continue; | 398 continue; |
395 SET_BIT (last_stmt_necessary, cd_bb->index); | 399 SET_BIT (last_stmt_necessary, cd_bb->index); |
396 SET_BIT (bb_contains_live_stmts, cd_bb->index); | 400 SET_BIT (bb_contains_live_stmts, cd_bb->index); |
397 | 401 |
398 stmt = last_stmt (cd_bb); | 402 stmt = last_stmt (cd_bb); |
399 if (stmt && is_ctrl_stmt (stmt)) | 403 if (stmt && is_ctrl_stmt (stmt)) |
400 mark_stmt_necessary (stmt, true); | 404 mark_stmt_necessary (stmt, true); |
401 } | 405 } |
406 if (!skipped) | |
407 SET_BIT (visited_control_parents, bb->index); | |
402 } | 408 } |
403 | 409 |
404 | 410 |
405 /* Find obviously necessary statements. These are things like most function | 411 /* Find obviously necessary statements. These are things like most function |
406 calls, and stores to file level variables. | 412 calls, and stores to file level variables. |
457 && (e->flags & EDGE_IRREDUCIBLE_LOOP)) | 463 && (e->flags & EDGE_IRREDUCIBLE_LOOP)) |
458 { | 464 { |
459 if (dump_file) | 465 if (dump_file) |
460 fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n", | 466 fprintf (dump_file, "Marking back edge of irreducible loop %i->%i\n", |
461 e->src->index, e->dest->index); | 467 e->src->index, e->dest->index); |
462 mark_control_dependent_edges_necessary (e->dest, el); | 468 mark_control_dependent_edges_necessary (e->dest, el, false); |
463 } | 469 } |
464 } | 470 } |
465 | 471 |
466 FOR_EACH_LOOP (li, loop, 0) | 472 FOR_EACH_LOOP (li, loop, 0) |
467 if (!finite_loop_p (loop)) | 473 if (!finite_loop_p (loop)) |
468 { | 474 { |
469 if (dump_file) | 475 if (dump_file) |
470 fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num); | 476 fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num); |
471 mark_control_dependent_edges_necessary (loop->latch, el); | 477 mark_control_dependent_edges_necessary (loop->latch, el, false); |
472 } | 478 } |
473 scev_finalize (); | 479 scev_finalize (); |
474 } | 480 } |
475 } | 481 } |
476 | 482 |
651 containing STMT is control dependent on, but only if we haven't | 657 containing STMT is control dependent on, but only if we haven't |
652 already done so. */ | 658 already done so. */ |
653 basic_block bb = gimple_bb (stmt); | 659 basic_block bb = gimple_bb (stmt); |
654 if (bb != ENTRY_BLOCK_PTR | 660 if (bb != ENTRY_BLOCK_PTR |
655 && ! TEST_BIT (visited_control_parents, bb->index)) | 661 && ! TEST_BIT (visited_control_parents, bb->index)) |
656 { | 662 mark_control_dependent_edges_necessary (bb, el, false); |
657 SET_BIT (visited_control_parents, bb->index); | |
658 mark_control_dependent_edges_necessary (bb, el); | |
659 } | |
660 } | 663 } |
661 | 664 |
662 if (gimple_code (stmt) == GIMPLE_PHI | 665 if (gimple_code (stmt) == GIMPLE_PHI |
663 /* We do not process virtual PHI nodes nor do we track their | 666 /* We do not process virtual PHI nodes nor do we track their |
664 necessity. */ | 667 necessity. */ |
677 tree arg = PHI_ARG_DEF (stmt, k); | 680 tree arg = PHI_ARG_DEF (stmt, k); |
678 if (TREE_CODE (arg) == SSA_NAME) | 681 if (TREE_CODE (arg) == SSA_NAME) |
679 mark_operand_necessary (arg); | 682 mark_operand_necessary (arg); |
680 } | 683 } |
681 | 684 |
685 /* For PHI operands it matters from where the control flow arrives | |
686 to the BB. Consider the following example: | |
687 | |
688 a=exp1; | |
689 b=exp2; | |
690 if (test) | |
691 ; | |
692 else | |
693 ; | |
694 c=PHI(a,b) | |
695 | |
696 We need to mark control dependence of the empty basic blocks, since they | |
697 contains computation of PHI operands. | |
698 | |
699 Doing so is too restrictive in the case the predecestor block is in | |
700 the loop. Consider: | |
701 | |
702 if (b) | |
703 { | |
704 int i; | |
705 for (i = 0; i<1000; ++i) | |
706 ; | |
707 j = 0; | |
708 } | |
709 return j; | |
710 | |
711 There is PHI for J in the BB containing return statement. | |
712 In this case the control dependence of predecestor block (that is | |
713 within the empty loop) also contains the block determining number | |
714 of iterations of the block that would prevent removing of empty | |
715 loop in this case. | |
716 | |
717 This scenario can be avoided by splitting critical edges. | |
718 To save the critical edge splitting pass we identify how the control | |
719 dependence would look like if the edge was split. | |
720 | |
721 Consider the modified CFG created from current CFG by splitting | |
722 edge B->C. In the postdominance tree of modified CFG, C' is | |
723 always child of C. There are two cases how chlids of C' can look | |
724 like: | |
725 | |
726 1) C' is leaf | |
727 | |
728 In this case the only basic block C' is control dependent on is B. | |
729 | |
730 2) C' has single child that is B | |
731 | |
732 In this case control dependence of C' is same as control | |
733 dependence of B in original CFG except for block B itself. | |
734 (since C' postdominate B in modified CFG) | |
735 | |
736 Now how to decide what case happens? There are two basic options: | |
737 | |
738 a) C postdominate B. Then C immediately postdominate B and | |
739 case 2 happens iff there is no other way from B to C except | |
740 the edge B->C. | |
741 | |
742 There is other way from B to C iff there is succesor of B that | |
743 is not postdominated by B. Testing this condition is somewhat | |
744 expensive, because we need to iterate all succesors of B. | |
745 We are safe to assume that this does not happen: we will mark B | |
746 as needed when processing the other path from B to C that is | |
747 conrol dependent on B and marking control dependencies of B | |
748 itself is harmless because they will be processed anyway after | |
749 processing control statement in B. | |
750 | |
751 b) C does not postdominate B. Always case 1 happens since there is | |
752 path from C to exit that does not go through B and thus also C'. */ | |
753 | |
682 if (aggressive && !degenerate_phi_p (stmt)) | 754 if (aggressive && !degenerate_phi_p (stmt)) |
683 { | 755 { |
684 for (k = 0; k < gimple_phi_num_args (stmt); k++) | 756 for (k = 0; k < gimple_phi_num_args (stmt); k++) |
685 { | 757 { |
686 basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src; | 758 basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src; |
687 if (arg_bb != ENTRY_BLOCK_PTR | 759 |
688 && ! TEST_BIT (visited_control_parents, arg_bb->index)) | 760 if (gimple_bb (stmt) |
761 != get_immediate_dominator (CDI_POST_DOMINATORS, arg_bb)) | |
689 { | 762 { |
690 SET_BIT (visited_control_parents, arg_bb->index); | 763 if (!TEST_BIT (last_stmt_necessary, arg_bb->index)) |
691 mark_control_dependent_edges_necessary (arg_bb, el); | 764 { |
765 gimple stmt2; | |
766 SET_BIT (last_stmt_necessary, arg_bb->index); | |
767 SET_BIT (bb_contains_live_stmts, arg_bb->index); | |
768 | |
769 stmt2 = last_stmt (arg_bb); | |
770 if (stmt2 && is_ctrl_stmt (stmt2)) | |
771 mark_stmt_necessary (stmt2, true); | |
772 } | |
692 } | 773 } |
774 else if (arg_bb != ENTRY_BLOCK_PTR | |
775 && ! TEST_BIT (visited_control_parents, arg_bb->index)) | |
776 mark_control_dependent_edges_necessary (arg_bb, el, true); | |
693 } | 777 } |
694 } | 778 } |
695 } | 779 } |
696 else | 780 else |
697 { | 781 { |
915 gsi_next (&gsi); | 999 gsi_next (&gsi); |
916 } | 1000 } |
917 return something_changed; | 1001 return something_changed; |
918 } | 1002 } |
919 | 1003 |
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. */ | 1004 /* Forward edge E to respective POST_DOM_BB and update PHIs. */ |
942 | 1005 |
943 static edge | 1006 static edge |
944 forward_edge_to_pdom (edge e, basic_block post_dom_bb) | 1007 forward_edge_to_pdom (edge e, basic_block post_dom_bb) |
945 { | 1008 { |
956 | 1019 |
957 /* If edge was already around, no updating is neccesary. */ | 1020 /* If edge was already around, no updating is neccesary. */ |
958 if (e2 != e) | 1021 if (e2 != e) |
959 return e2; | 1022 return e2; |
960 | 1023 |
961 if (phi_nodes (post_dom_bb)) | 1024 if (!gimple_seq_empty_p (phi_nodes (post_dom_bb))) |
962 { | 1025 { |
963 /* We are sure that for every live PHI we are seeing control dependent BB. | 1026 /* 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 | 1027 This means that we can pick any edge to duplicate PHI args from. */ |
965 to the PHI itself. */ | |
966 FOR_EACH_EDGE (e2, ei, post_dom_bb->preds) | 1028 FOR_EACH_EDGE (e2, ei, post_dom_bb->preds) |
967 if (e2 != e && dominated_by_p (CDI_POST_DOMINATORS, e->src, e2->src)) | 1029 if (e2 != e) |
968 break; | 1030 break; |
969 for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);) | 1031 for (gsi = gsi_start_phis (post_dom_bb); !gsi_end_p (gsi);) |
970 { | 1032 { |
971 gimple phi = gsi_stmt (gsi); | 1033 gimple phi = gsi_stmt (gsi); |
972 tree op; | 1034 tree op; |
973 source_location locus; | 1035 source_location locus; |
974 | 1036 |
975 /* Dead PHI do not imply control dependency. */ | 1037 /* PHIs for virtuals have no control dependency relation on them. |
976 if (!gimple_plf (phi, STMT_NECESSARY) | 1038 We are lost here and must force renaming of the symbol. */ |
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))) | 1039 if (!is_gimple_reg (gimple_phi_result (phi))) |
992 { | 1040 { |
993 mark_virtual_phi_result_for_renaming (phi); | 1041 mark_virtual_phi_result_for_renaming (phi); |
994 remove_phi_node (&gsi, true); | 1042 remove_phi_node (&gsi, true); |
995 continue; | 1043 continue; |
996 } | 1044 } |
997 if (!e2) | 1045 |
1046 /* Dead PHI do not imply control dependency. */ | |
1047 if (!gimple_plf (phi, STMT_NECESSARY)) | |
998 { | 1048 { |
999 op = gimple_phi_arg_def (phi, e->dest_idx == 0 ? 1 : 0); | 1049 gsi_next (&gsi); |
1000 locus = gimple_phi_arg_location (phi, e->dest_idx == 0 ? 1 : 0); | 1050 continue; |
1001 } | 1051 } |
1002 else | 1052 |
1003 { | 1053 op = gimple_phi_arg_def (phi, e2->dest_idx); |
1004 op = gimple_phi_arg_def (phi, e2->dest_idx); | 1054 locus = gimple_phi_arg_location (phi, e2->dest_idx); |
1005 locus = gimple_phi_arg_location (phi, e2->dest_idx); | |
1006 } | |
1007 add_phi_arg (phi, op, e, locus); | 1055 add_phi_arg (phi, op, e, locus); |
1008 gcc_assert (e2 || degenerate_phi_p (phi)); | 1056 /* The resulting PHI if not dead can only be degenerate. */ |
1057 gcc_assert (degenerate_phi_p (phi)); | |
1009 gsi_next (&gsi); | 1058 gsi_next (&gsi); |
1010 } | 1059 } |
1011 } | 1060 } |
1012 return e; | 1061 return e; |
1013 } | 1062 } |
1039 { | 1088 { |
1040 basic_block post_dom_bb; | 1089 basic_block post_dom_bb; |
1041 edge e, e2; | 1090 edge e, e2; |
1042 edge_iterator ei; | 1091 edge_iterator ei; |
1043 | 1092 |
1044 post_dom_bb = get_live_post_dom (bb); | 1093 post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb); |
1045 | 1094 |
1046 e = find_edge (bb, post_dom_bb); | 1095 e = find_edge (bb, post_dom_bb); |
1047 | 1096 |
1048 /* If edge is already there, try to use it. This avoids need to update | 1097 /* If edge is already there, try to use it. This avoids need to update |
1049 PHI nodes. Also watch for cases where post dominator does not exists | 1098 PHI nodes. Also watch for cases where post dominator does not exists |