Mercurial > hg > CbC > CbC_gcc
comparison gcc/tree-ssa-dom.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 | 3bfb6c00c1e0 |
children | b7f97abdc517 |
comparison
equal
deleted
inserted
replaced
52:c156f1bd5cd9 | 55:77e2b8dfacca |
---|---|
1 /* SSA Dominator optimizations for trees | 1 /* SSA Dominator optimizations for trees |
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 | 2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 |
3 Free Software Foundation, Inc. | 3 Free Software Foundation, Inc. |
4 Contributed by Diego Novillo <dnovillo@redhat.com> | 4 Contributed by Diego Novillo <dnovillo@redhat.com> |
5 | 5 |
6 This file is part of GCC. | 6 This file is part of GCC. |
7 | 7 |
81 /* Structure for recording edge equivalences as well as any pending | 81 /* Structure for recording edge equivalences as well as any pending |
82 edge redirections during the dominator optimizer. | 82 edge redirections during the dominator optimizer. |
83 | 83 |
84 Computing and storing the edge equivalences instead of creating | 84 Computing and storing the edge equivalences instead of creating |
85 them on-demand can save significant amounts of time, particularly | 85 them on-demand can save significant amounts of time, particularly |
86 for pathological cases involving switch statements. | 86 for pathological cases involving switch statements. |
87 | 87 |
88 These structures live for a single iteration of the dominator | 88 These structures live for a single iteration of the dominator |
89 optimizer in the edge's AUX field. At the end of an iteration we | 89 optimizer in the edge's AUX field. At the end of an iteration we |
90 free each of these structures and update the AUX field to point | 90 free each of these structures and update the AUX field to point |
91 to any requested redirection target (the code for updating the | 91 to any requested redirection target (the code for updating the |
125 DEF_VEC_P(expr_hash_elt_t); | 125 DEF_VEC_P(expr_hash_elt_t); |
126 DEF_VEC_ALLOC_P(expr_hash_elt_t,heap); | 126 DEF_VEC_ALLOC_P(expr_hash_elt_t,heap); |
127 | 127 |
128 static VEC(expr_hash_elt_t,heap) *avail_exprs_stack; | 128 static VEC(expr_hash_elt_t,heap) *avail_exprs_stack; |
129 | 129 |
130 /* Stack of statements we need to rescan during finalization for newly | |
131 exposed variables. | |
132 | |
133 Statement rescanning must occur after the current block's available | |
134 expressions are removed from AVAIL_EXPRS. Else we may change the | |
135 hash code for an expression and be unable to find/remove it from | |
136 AVAIL_EXPRS. */ | |
137 typedef gimple *gimple_p; | |
138 DEF_VEC_P(gimple_p); | |
139 DEF_VEC_ALLOC_P(gimple_p,heap); | |
140 | |
141 static VEC(gimple_p,heap) *stmts_to_rescan; | |
142 | |
143 /* Structure for entries in the expression hash table. */ | 130 /* Structure for entries in the expression hash table. */ |
144 | 131 |
145 struct expr_hash_elt | 132 struct expr_hash_elt |
146 { | 133 { |
147 /* The value (lhs) of this expression. */ | 134 /* The value (lhs) of this expression. */ |
185 }; | 172 }; |
186 | 173 |
187 static struct opt_stats_d opt_stats; | 174 static struct opt_stats_d opt_stats; |
188 | 175 |
189 /* Local functions. */ | 176 /* Local functions. */ |
190 static void optimize_stmt (struct dom_walk_data *, | 177 static void optimize_stmt (basic_block, gimple_stmt_iterator); |
191 basic_block, | |
192 gimple_stmt_iterator); | |
193 static tree lookup_avail_expr (gimple, bool); | 178 static tree lookup_avail_expr (gimple, bool); |
194 static hashval_t avail_expr_hash (const void *); | 179 static hashval_t avail_expr_hash (const void *); |
195 static hashval_t real_avail_expr_hash (const void *); | 180 static hashval_t real_avail_expr_hash (const void *); |
196 static int avail_expr_eq (const void *, const void *); | 181 static int avail_expr_eq (const void *, const void *); |
197 static void htab_statistics (FILE *, htab_t); | 182 static void htab_statistics (FILE *, htab_t); |
198 static void record_cond (struct cond_equivalence *); | 183 static void record_cond (struct cond_equivalence *); |
199 static void record_const_or_copy (tree, tree); | 184 static void record_const_or_copy (tree, tree); |
200 static void record_equality (tree, tree); | 185 static void record_equality (tree, tree); |
201 static void record_equivalences_from_phis (basic_block); | 186 static void record_equivalences_from_phis (basic_block); |
202 static void record_equivalences_from_incoming_edge (basic_block); | 187 static void record_equivalences_from_incoming_edge (basic_block); |
203 static bool eliminate_redundant_computations (gimple_stmt_iterator *); | 188 static void eliminate_redundant_computations (gimple_stmt_iterator *); |
204 static void record_equivalences_from_stmt (gimple, int); | 189 static void record_equivalences_from_stmt (gimple, int); |
205 static void dom_thread_across_edge (struct dom_walk_data *, edge); | 190 static void dom_thread_across_edge (struct dom_walk_data *, edge); |
206 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block); | 191 static void dom_opt_leave_block (struct dom_walk_data *, basic_block); |
207 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block); | 192 static void dom_opt_enter_block (struct dom_walk_data *, basic_block); |
208 static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block); | |
209 static void remove_local_expressions_from_table (void); | 193 static void remove_local_expressions_from_table (void); |
210 static void restore_vars_to_original_value (void); | 194 static void restore_vars_to_original_value (void); |
211 static edge single_incoming_edge_ignoring_loop_edges (basic_block); | 195 static edge single_incoming_edge_ignoring_loop_edges (basic_block); |
212 | 196 |
213 | 197 |
224 if (code == GIMPLE_ASSIGN) | 208 if (code == GIMPLE_ASSIGN) |
225 { | 209 { |
226 enum tree_code subcode = gimple_assign_rhs_code (stmt); | 210 enum tree_code subcode = gimple_assign_rhs_code (stmt); |
227 | 211 |
228 expr->type = NULL_TREE; | 212 expr->type = NULL_TREE; |
229 | 213 |
230 switch (get_gimple_rhs_class (subcode)) | 214 switch (get_gimple_rhs_class (subcode)) |
231 { | 215 { |
232 case GIMPLE_SINGLE_RHS: | 216 case GIMPLE_SINGLE_RHS: |
233 expr->kind = EXPR_SINGLE; | 217 expr->kind = EXPR_SINGLE; |
234 expr->ops.single.rhs = gimple_assign_rhs1 (stmt); | 218 expr->ops.single.rhs = gimple_assign_rhs1 (stmt); |
269 expr->kind = EXPR_CALL; | 253 expr->kind = EXPR_CALL; |
270 expr->ops.call.fn = gimple_call_fn (stmt); | 254 expr->ops.call.fn = gimple_call_fn (stmt); |
271 | 255 |
272 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)) | 256 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)) |
273 expr->ops.call.pure = true; | 257 expr->ops.call.pure = true; |
274 else | 258 else |
275 expr->ops.call.pure = false; | 259 expr->ops.call.pure = false; |
276 | 260 |
277 expr->ops.call.nargs = nargs; | 261 expr->ops.call.nargs = nargs; |
278 expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree)); | 262 expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree)); |
279 for (i = 0; i < nargs; i++) | 263 for (i = 0; i < nargs; i++) |
307 | 291 |
308 static void | 292 static void |
309 initialize_expr_from_cond (tree cond, struct hashable_expr *expr) | 293 initialize_expr_from_cond (tree cond, struct hashable_expr *expr) |
310 { | 294 { |
311 expr->type = boolean_type_node; | 295 expr->type = boolean_type_node; |
312 | 296 |
313 if (COMPARISON_CLASS_P (cond)) | 297 if (COMPARISON_CLASS_P (cond)) |
314 { | 298 { |
315 expr->kind = EXPR_BINARY; | 299 expr->kind = EXPR_BINARY; |
316 expr->ops.binary.op = TREE_CODE (cond); | 300 expr->ops.binary.op = TREE_CODE (cond); |
317 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0); | 301 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0); |
429 expr1->ops.call.args[i], 0)) | 413 expr1->ops.call.args[i], 0)) |
430 return false; | 414 return false; |
431 | 415 |
432 return true; | 416 return true; |
433 } | 417 } |
434 | 418 |
435 default: | 419 default: |
436 gcc_unreachable (); | 420 gcc_unreachable (); |
437 } | 421 } |
438 } | 422 } |
439 | 423 |
487 val = iterative_hash_expr (expr->ops.call.fn, val); | 471 val = iterative_hash_expr (expr->ops.call.fn, val); |
488 for (i = 0; i < expr->ops.call.nargs; i++) | 472 for (i = 0; i < expr->ops.call.nargs; i++) |
489 val = iterative_hash_expr (expr->ops.call.args[i], val); | 473 val = iterative_hash_expr (expr->ops.call.args[i], val); |
490 } | 474 } |
491 break; | 475 break; |
492 | 476 |
493 default: | 477 default: |
494 gcc_unreachable (); | 478 gcc_unreachable (); |
495 } | 479 } |
496 | 480 |
497 return val; | 481 return val; |
510 if (element->lhs) | 494 if (element->lhs) |
511 { | 495 { |
512 print_generic_expr (stream, element->lhs, 0); | 496 print_generic_expr (stream, element->lhs, 0); |
513 fprintf (stream, " = "); | 497 fprintf (stream, " = "); |
514 } | 498 } |
515 | 499 |
516 switch (element->expr.kind) | 500 switch (element->expr.kind) |
517 { | 501 { |
518 case EXPR_SINGLE: | 502 case EXPR_SINGLE: |
519 print_generic_expr (stream, element->expr.ops.single.rhs, 0); | 503 print_generic_expr (stream, element->expr.ops.single.rhs, 0); |
520 break; | 504 break; |
611 } | 595 } |
612 } | 596 } |
613 } | 597 } |
614 } | 598 } |
615 | 599 |
616 /* Jump threading, redundancy elimination and const/copy propagation. | 600 /* Jump threading, redundancy elimination and const/copy propagation. |
617 | 601 |
618 This pass may expose new symbols that need to be renamed into SSA. For | 602 This pass may expose new symbols that need to be renamed into SSA. For |
619 every new symbol exposed, its corresponding bit will be set in | 603 every new symbol exposed, its corresponding bit will be set in |
620 VARS_TO_RENAME. */ | 604 VARS_TO_RENAME. */ |
621 | 605 |
622 static unsigned int | 606 static unsigned int |
623 tree_ssa_dominator_optimize (void) | 607 tree_ssa_dominator_optimize (void) |
624 { | 608 { |
625 struct dom_walk_data walk_data; | 609 struct dom_walk_data walk_data; |
626 unsigned int i; | |
627 | 610 |
628 memset (&opt_stats, 0, sizeof (opt_stats)); | 611 memset (&opt_stats, 0, sizeof (opt_stats)); |
629 | 612 |
630 /* Create our hash tables. */ | 613 /* Create our hash tables. */ |
631 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt); | 614 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt); |
632 avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20); | 615 avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20); |
633 const_and_copies_stack = VEC_alloc (tree, heap, 20); | 616 const_and_copies_stack = VEC_alloc (tree, heap, 20); |
634 stmts_to_rescan = VEC_alloc (gimple_p, heap, 20); | |
635 need_eh_cleanup = BITMAP_ALLOC (NULL); | 617 need_eh_cleanup = BITMAP_ALLOC (NULL); |
636 | 618 |
637 /* Setup callbacks for the generic dominator tree walker. */ | 619 /* Setup callbacks for the generic dominator tree walker. */ |
638 walk_data.walk_stmts_backward = false; | |
639 walk_data.dom_direction = CDI_DOMINATORS; | 620 walk_data.dom_direction = CDI_DOMINATORS; |
640 walk_data.initialize_block_local_data = NULL; | 621 walk_data.initialize_block_local_data = NULL; |
641 walk_data.before_dom_children_before_stmts = dom_opt_initialize_block; | 622 walk_data.before_dom_children = dom_opt_enter_block; |
642 walk_data.before_dom_children_walk_stmts = optimize_stmt; | 623 walk_data.after_dom_children = dom_opt_leave_block; |
643 walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges; | |
644 walk_data.after_dom_children_before_stmts = NULL; | |
645 walk_data.after_dom_children_walk_stmts = NULL; | |
646 walk_data.after_dom_children_after_stmts = dom_opt_finalize_block; | |
647 /* Right now we only attach a dummy COND_EXPR to the global data pointer. | 624 /* Right now we only attach a dummy COND_EXPR to the global data pointer. |
648 When we attach more stuff we'll need to fill this out with a real | 625 When we attach more stuff we'll need to fill this out with a real |
649 structure. */ | 626 structure. */ |
650 walk_data.global_data = NULL; | 627 walk_data.global_data = NULL; |
651 walk_data.block_local_data_size = 0; | 628 walk_data.block_local_data_size = 0; |
652 walk_data.interesting_blocks = NULL; | |
653 | 629 |
654 /* Now initialize the dominator walker. */ | 630 /* Now initialize the dominator walker. */ |
655 init_walk_dominator_tree (&walk_data); | 631 init_walk_dominator_tree (&walk_data); |
656 | 632 |
657 calculate_dominance_info (CDI_DOMINATORS); | 633 calculate_dominance_info (CDI_DOMINATORS); |
661 in jump threading. Note that we still can e.g. thread through loop | 637 in jump threading. Note that we still can e.g. thread through loop |
662 headers to an exit edge, or through loop header to the loop body, assuming | 638 headers to an exit edge, or through loop header to the loop body, assuming |
663 that we update the loop info. */ | 639 that we update the loop info. */ |
664 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES); | 640 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES); |
665 | 641 |
642 /* Initialize the value-handle array. */ | |
643 threadedge_initialize_values (); | |
644 | |
666 /* We need accurate information regarding back edges in the CFG | 645 /* We need accurate information regarding back edges in the CFG |
667 for jump threading; this may include back edges that are not part of | 646 for jump threading; this may include back edges that are not part of |
668 a single loop. */ | 647 a single loop. */ |
669 mark_dfs_back_edges (); | 648 mark_dfs_back_edges (); |
670 | 649 |
671 /* Recursively walk the dominator tree optimizing statements. */ | 650 /* Recursively walk the dominator tree optimizing statements. */ |
672 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); | 651 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); |
673 | 652 |
674 { | 653 { |
675 gimple_stmt_iterator gsi; | 654 gimple_stmt_iterator gsi; |
718 | 697 |
719 gimple_purge_all_dead_eh_edges (need_eh_cleanup); | 698 gimple_purge_all_dead_eh_edges (need_eh_cleanup); |
720 bitmap_zero (need_eh_cleanup); | 699 bitmap_zero (need_eh_cleanup); |
721 } | 700 } |
722 | 701 |
723 /* Finally, remove everything except invariants in SSA_NAME_VALUE. | |
724 | |
725 Long term we will be able to let everything in SSA_NAME_VALUE | |
726 persist. However, for now, we know this is the safe thing to do. */ | |
727 for (i = 0; i < num_ssa_names; i++) | |
728 { | |
729 tree name = ssa_name (i); | |
730 tree value; | |
731 | |
732 if (!name) | |
733 continue; | |
734 | |
735 value = SSA_NAME_VALUE (name); | |
736 if (value && !is_gimple_min_invariant (value)) | |
737 SSA_NAME_VALUE (name) = NULL; | |
738 } | |
739 | |
740 statistics_counter_event (cfun, "Redundant expressions eliminated", | 702 statistics_counter_event (cfun, "Redundant expressions eliminated", |
741 opt_stats.num_re); | 703 opt_stats.num_re); |
742 statistics_counter_event (cfun, "Constants propagated", | 704 statistics_counter_event (cfun, "Constants propagated", |
743 opt_stats.num_const_prop); | 705 opt_stats.num_const_prop); |
744 statistics_counter_event (cfun, "Copies propagated", | 706 statistics_counter_event (cfun, "Copies propagated", |
756 /* And finalize the dominator walker. */ | 718 /* And finalize the dominator walker. */ |
757 fini_walk_dominator_tree (&walk_data); | 719 fini_walk_dominator_tree (&walk_data); |
758 | 720 |
759 /* Free asserted bitmaps and stacks. */ | 721 /* Free asserted bitmaps and stacks. */ |
760 BITMAP_FREE (need_eh_cleanup); | 722 BITMAP_FREE (need_eh_cleanup); |
761 | 723 |
762 VEC_free (expr_hash_elt_t, heap, avail_exprs_stack); | 724 VEC_free (expr_hash_elt_t, heap, avail_exprs_stack); |
763 VEC_free (tree, heap, const_and_copies_stack); | 725 VEC_free (tree, heap, const_and_copies_stack); |
764 VEC_free (gimple_p, heap, stmts_to_rescan); | 726 |
765 | 727 /* Free the value-handle array. */ |
728 threadedge_finalize_values (); | |
729 ssa_name_values = NULL; | |
730 | |
766 return 0; | 731 return 0; |
767 } | 732 } |
768 | 733 |
769 static bool | 734 static bool |
770 gate_dominator (void) | 735 gate_dominator (void) |
771 { | 736 { |
772 return flag_tree_dom != 0; | 737 return flag_tree_dom != 0; |
773 } | 738 } |
774 | 739 |
775 struct gimple_opt_pass pass_dominator = | 740 struct gimple_opt_pass pass_dominator = |
776 { | 741 { |
777 { | 742 { |
778 GIMPLE_PASS, | 743 GIMPLE_PASS, |
779 "dom", /* name */ | 744 "dom", /* name */ |
780 gate_dominator, /* gate */ | 745 gate_dominator, /* gate */ |
781 tree_ssa_dominator_optimize, /* execute */ | 746 tree_ssa_dominator_optimize, /* execute */ |
782 NULL, /* sub */ | 747 NULL, /* sub */ |
783 NULL, /* next */ | 748 NULL, /* next */ |
784 0, /* static_pass_number */ | 749 0, /* static_pass_number */ |
785 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */ | 750 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */ |
786 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ | 751 PROP_cfg | PROP_ssa, /* properties_required */ |
787 0, /* properties_provided */ | 752 0, /* properties_provided */ |
788 0, /* properties_destroyed */ | 753 0, /* properties_destroyed */ |
789 0, /* todo_flags_start */ | 754 0, /* todo_flags_start */ |
790 TODO_dump_func | 755 TODO_dump_func |
791 | TODO_update_ssa | 756 | TODO_update_ssa |
840 | 805 |
841 /* Initialize local stacks for this optimizer and record equivalences | 806 /* Initialize local stacks for this optimizer and record equivalences |
842 upon entry to BB. Equivalences can come from the edge traversed to | 807 upon entry to BB. Equivalences can come from the edge traversed to |
843 reach BB or they may come from PHI nodes at the start of BB. */ | 808 reach BB or they may come from PHI nodes at the start of BB. */ |
844 | 809 |
845 static void | |
846 dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, | |
847 basic_block bb) | |
848 { | |
849 if (dump_file && (dump_flags & TDF_DETAILS)) | |
850 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); | |
851 | |
852 /* Push a marker on the stacks of local information so that we know how | |
853 far to unwind when we finalize this block. */ | |
854 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); | |
855 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
856 | |
857 record_equivalences_from_incoming_edge (bb); | |
858 | |
859 /* PHI nodes can create equivalences too. */ | |
860 record_equivalences_from_phis (bb); | |
861 } | |
862 | |
863 /* Remove all the expressions in LOCALS from TABLE, stopping when there are | 810 /* Remove all the expressions in LOCALS from TABLE, stopping when there are |
864 LIMIT entries left in LOCALs. */ | 811 LIMIT entries left in LOCALs. */ |
865 | 812 |
866 static void | 813 static void |
867 remove_local_expressions_from_table (void) | 814 remove_local_expressions_from_table (void) |
868 { | 815 { |
869 /* Remove all the expressions made available in this block. */ | 816 /* Remove all the expressions made available in this block. */ |
870 while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0) | 817 while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0) |
871 { | 818 { |
872 struct expr_hash_elt element; | |
873 expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack); | 819 expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack); |
820 void **slot; | |
874 | 821 |
875 if (victim == NULL) | 822 if (victim == NULL) |
876 break; | 823 break; |
877 | |
878 element = *victim; | |
879 | 824 |
880 /* This must precede the actual removal from the hash table, | 825 /* This must precede the actual removal from the hash table, |
881 as ELEMENT and the table entry may share a call argument | 826 as ELEMENT and the table entry may share a call argument |
882 vector which will be freed during removal. */ | 827 vector which will be freed during removal. */ |
883 if (dump_file && (dump_flags & TDF_DETAILS)) | 828 if (dump_file && (dump_flags & TDF_DETAILS)) |
884 { | 829 { |
885 fprintf (dump_file, "<<<< "); | 830 fprintf (dump_file, "<<<< "); |
886 print_expr_hash_elt (dump_file, &element); | 831 print_expr_hash_elt (dump_file, victim); |
887 } | 832 } |
888 | 833 |
889 htab_remove_elt_with_hash (avail_exprs, &element, element.hash); | 834 slot = htab_find_slot_with_hash (avail_exprs, |
835 victim, victim->hash, NO_INSERT); | |
836 gcc_assert (slot && *slot == (void *) victim); | |
837 htab_clear_slot (avail_exprs, slot); | |
890 } | 838 } |
891 } | 839 } |
892 | 840 |
893 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore | 841 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore |
894 CONST_AND_COPIES to its original state, stopping when we hit a | 842 CONST_AND_COPIES to its original state, stopping when we hit a |
914 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0); | 862 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0); |
915 fprintf (dump_file, "\n"); | 863 fprintf (dump_file, "\n"); |
916 } | 864 } |
917 | 865 |
918 prev_value = VEC_pop (tree, const_and_copies_stack); | 866 prev_value = VEC_pop (tree, const_and_copies_stack); |
919 SSA_NAME_VALUE (dest) = prev_value; | 867 set_ssa_name_value (dest, prev_value); |
920 } | 868 } |
921 } | 869 } |
922 | 870 |
923 /* A trivial wrapper so that we can present the generic jump | 871 /* A trivial wrapper so that we can present the generic jump |
924 threading code with a simple API for simplifying statements. */ | 872 threading code with a simple API for simplifying statements. */ |
948 thread_across_edge ((gimple) walk_data->global_data, e, false, | 896 thread_across_edge ((gimple) walk_data->global_data, e, false, |
949 &const_and_copies_stack, | 897 &const_and_copies_stack, |
950 simplify_stmt_for_jump_threading); | 898 simplify_stmt_for_jump_threading); |
951 } | 899 } |
952 | 900 |
953 /* We have finished processing the dominator children of BB, perform | |
954 any finalization actions in preparation for leaving this node in | |
955 the dominator tree. */ | |
956 | |
957 static void | |
958 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb) | |
959 { | |
960 gimple last; | |
961 | |
962 /* If we have an outgoing edge to a block with multiple incoming and | |
963 outgoing edges, then we may be able to thread the edge, i.e., we | |
964 may be able to statically determine which of the outgoing edges | |
965 will be traversed when the incoming edge from BB is traversed. */ | |
966 if (single_succ_p (bb) | |
967 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0 | |
968 && potentially_threadable_block (single_succ (bb))) | |
969 { | |
970 dom_thread_across_edge (walk_data, single_succ_edge (bb)); | |
971 } | |
972 else if ((last = last_stmt (bb)) | |
973 && gimple_code (last) == GIMPLE_COND | |
974 && EDGE_COUNT (bb->succs) == 2 | |
975 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0 | |
976 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0) | |
977 { | |
978 edge true_edge, false_edge; | |
979 | |
980 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
981 | |
982 /* Only try to thread the edge if it reaches a target block with | |
983 more than one predecessor and more than one successor. */ | |
984 if (potentially_threadable_block (true_edge->dest)) | |
985 { | |
986 struct edge_info *edge_info; | |
987 unsigned int i; | |
988 | |
989 /* Push a marker onto the available expression stack so that we | |
990 unwind any expressions related to the TRUE arm before processing | |
991 the false arm below. */ | |
992 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); | |
993 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
994 | |
995 edge_info = (struct edge_info *) true_edge->aux; | |
996 | |
997 /* If we have info associated with this edge, record it into | |
998 our equivalence tables. */ | |
999 if (edge_info) | |
1000 { | |
1001 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; | |
1002 tree lhs = edge_info->lhs; | |
1003 tree rhs = edge_info->rhs; | |
1004 | |
1005 /* If we have a simple NAME = VALUE equivalence, record it. */ | |
1006 if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
1007 record_const_or_copy (lhs, rhs); | |
1008 | |
1009 /* If we have 0 = COND or 1 = COND equivalences, record them | |
1010 into our expression hash tables. */ | |
1011 if (cond_equivalences) | |
1012 for (i = 0; i < edge_info->max_cond_equivalences; i++) | |
1013 record_cond (&cond_equivalences[i]); | |
1014 } | |
1015 | |
1016 dom_thread_across_edge (walk_data, true_edge); | |
1017 | |
1018 /* And restore the various tables to their state before | |
1019 we threaded this edge. */ | |
1020 remove_local_expressions_from_table (); | |
1021 } | |
1022 | |
1023 /* Similarly for the ELSE arm. */ | |
1024 if (potentially_threadable_block (false_edge->dest)) | |
1025 { | |
1026 struct edge_info *edge_info; | |
1027 unsigned int i; | |
1028 | |
1029 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
1030 edge_info = (struct edge_info *) false_edge->aux; | |
1031 | |
1032 /* If we have info associated with this edge, record it into | |
1033 our equivalence tables. */ | |
1034 if (edge_info) | |
1035 { | |
1036 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; | |
1037 tree lhs = edge_info->lhs; | |
1038 tree rhs = edge_info->rhs; | |
1039 | |
1040 /* If we have a simple NAME = VALUE equivalence, record it. */ | |
1041 if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
1042 record_const_or_copy (lhs, rhs); | |
1043 | |
1044 /* If we have 0 = COND or 1 = COND equivalences, record them | |
1045 into our expression hash tables. */ | |
1046 if (cond_equivalences) | |
1047 for (i = 0; i < edge_info->max_cond_equivalences; i++) | |
1048 record_cond (&cond_equivalences[i]); | |
1049 } | |
1050 | |
1051 /* Now thread the edge. */ | |
1052 dom_thread_across_edge (walk_data, false_edge); | |
1053 | |
1054 /* No need to remove local expressions from our tables | |
1055 or restore vars to their original value as that will | |
1056 be done immediately below. */ | |
1057 } | |
1058 } | |
1059 | |
1060 remove_local_expressions_from_table (); | |
1061 restore_vars_to_original_value (); | |
1062 | |
1063 /* If we queued any statements to rescan in this block, then | |
1064 go ahead and rescan them now. */ | |
1065 while (VEC_length (gimple_p, stmts_to_rescan) > 0) | |
1066 { | |
1067 gimple *stmt_p = VEC_last (gimple_p, stmts_to_rescan); | |
1068 gimple stmt = *stmt_p; | |
1069 basic_block stmt_bb = gimple_bb (stmt); | |
1070 | |
1071 if (stmt_bb != bb) | |
1072 break; | |
1073 | |
1074 VEC_pop (gimple_p, stmts_to_rescan); | |
1075 pop_stmt_changes (stmt_p); | |
1076 } | |
1077 } | |
1078 | |
1079 /* PHI nodes can create equivalences too. | 901 /* PHI nodes can create equivalences too. |
1080 | 902 |
1081 Ignoring any alternatives which are the same as the result, if | 903 Ignoring any alternatives which are the same as the result, if |
1082 all the alternatives are equal, then the PHI node creates an | 904 all the alternatives are equal, then the PHI node creates an |
1083 equivalence. */ | 905 equivalence. */ |
1084 | 906 |
1085 static void | 907 static void |
1086 record_equivalences_from_phis (basic_block bb) | 908 record_equivalences_from_phis (basic_block bb) |
1087 { | 909 { |
1088 gimple_stmt_iterator gsi; | 910 gimple_stmt_iterator gsi; |
1089 | 911 |
1090 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | 912 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
1091 { | 913 { |
1092 gimple phi = gsi_stmt (gsi); | 914 gimple phi = gsi_stmt (gsi); |
1093 | 915 |
1094 tree lhs = gimple_phi_result (phi); | 916 tree lhs = gimple_phi_result (phi); |
1126 a useful equivalence. We do not need to record unwind data for | 948 a useful equivalence. We do not need to record unwind data for |
1127 this, since this is a true assignment and not an equivalence | 949 this, since this is a true assignment and not an equivalence |
1128 inferred from a comparison. All uses of this ssa name are dominated | 950 inferred from a comparison. All uses of this ssa name are dominated |
1129 by this assignment, so unwinding just costs time and space. */ | 951 by this assignment, so unwinding just costs time and space. */ |
1130 if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs)) | 952 if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs)) |
1131 SSA_NAME_VALUE (lhs) = rhs; | 953 set_ssa_name_value (lhs, rhs); |
1132 } | 954 } |
1133 } | 955 } |
1134 | 956 |
1135 /* Ignoring loop backedges, if BB has precisely one incoming edge then | 957 /* Ignoring loop backedges, if BB has precisely one incoming edge then |
1136 return that edge. Otherwise return NULL. */ | 958 return that edge. Otherwise return NULL. */ |
1270 free (element); | 1092 free (element); |
1271 } | 1093 } |
1272 | 1094 |
1273 /* Build a cond_equivalence record indicating that the comparison | 1095 /* Build a cond_equivalence record indicating that the comparison |
1274 CODE holds between operands OP0 and OP1. */ | 1096 CODE holds between operands OP0 and OP1. */ |
1275 | 1097 |
1276 static void | 1098 static void |
1277 build_and_record_new_cond (enum tree_code code, | 1099 build_and_record_new_cond (enum tree_code code, |
1278 tree op0, tree op1, | 1100 tree op0, tree op1, |
1279 struct cond_equivalence *p) | 1101 struct cond_equivalence *p) |
1280 { | 1102 { |
1439 Do the work of recording the value and undo info. */ | 1261 Do the work of recording the value and undo info. */ |
1440 | 1262 |
1441 static void | 1263 static void |
1442 record_const_or_copy_1 (tree x, tree y, tree prev_x) | 1264 record_const_or_copy_1 (tree x, tree y, tree prev_x) |
1443 { | 1265 { |
1444 SSA_NAME_VALUE (x) = y; | 1266 set_ssa_name_value (x, y); |
1445 | 1267 |
1446 if (dump_file && (dump_flags & TDF_DETAILS)) | 1268 if (dump_file && (dump_flags & TDF_DETAILS)) |
1447 { | 1269 { |
1448 fprintf (dump_file, "0>>> COPY "); | 1270 fprintf (dump_file, "0>>> COPY "); |
1449 print_generic_expr (dump_file, x, 0); | 1271 print_generic_expr (dump_file, x, 0); |
1547 record_const_or_copy_1 (x, y, prev_x); | 1369 record_const_or_copy_1 (x, y, prev_x); |
1548 } | 1370 } |
1549 | 1371 |
1550 /* Returns true when STMT is a simple iv increment. It detects the | 1372 /* Returns true when STMT is a simple iv increment. It detects the |
1551 following situation: | 1373 following situation: |
1552 | 1374 |
1553 i_1 = phi (..., i_2) | 1375 i_1 = phi (..., i_2) |
1554 i_2 = i_1 +/- ... */ | 1376 i_2 = i_1 +/- ... */ |
1555 | 1377 |
1556 static bool | 1378 static bool |
1557 simple_iv_increment_p (gimple stmt) | 1379 simple_iv_increment_p (gimple stmt) |
1586 | 1408 |
1587 return false; | 1409 return false; |
1588 } | 1410 } |
1589 | 1411 |
1590 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current | 1412 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current |
1591 known value for that SSA_NAME (or NULL if no value is known). | 1413 known value for that SSA_NAME (or NULL if no value is known). |
1592 | 1414 |
1593 Propagate values from CONST_AND_COPIES into the PHI nodes of the | 1415 Propagate values from CONST_AND_COPIES into the PHI nodes of the |
1594 successors of BB. */ | 1416 successors of BB. */ |
1595 | 1417 |
1596 static void | 1418 static void |
1651 struct edge_info *edge_info; | 1473 struct edge_info *edge_info; |
1652 | 1474 |
1653 if (! gsi_end_p (gsi)) | 1475 if (! gsi_end_p (gsi)) |
1654 { | 1476 { |
1655 gimple stmt = gsi_stmt (gsi); | 1477 gimple stmt = gsi_stmt (gsi); |
1478 location_t loc = gimple_location (stmt); | |
1656 | 1479 |
1657 if (gimple_code (stmt) == GIMPLE_SWITCH) | 1480 if (gimple_code (stmt) == GIMPLE_SWITCH) |
1658 { | 1481 { |
1659 tree index = gimple_switch_index (stmt); | 1482 tree index = gimple_switch_index (stmt); |
1660 | 1483 |
1683 basic_block target_bb = e->dest; | 1506 basic_block target_bb = e->dest; |
1684 tree label = info[target_bb->index]; | 1507 tree label = info[target_bb->index]; |
1685 | 1508 |
1686 if (label != NULL && label != error_mark_node) | 1509 if (label != NULL && label != error_mark_node) |
1687 { | 1510 { |
1688 tree x = fold_convert (TREE_TYPE (index), CASE_LOW (label)); | 1511 tree x = fold_convert_loc (loc, TREE_TYPE (index), |
1512 CASE_LOW (label)); | |
1689 edge_info = allocate_edge_info (e); | 1513 edge_info = allocate_edge_info (e); |
1690 edge_info->lhs = index; | 1514 edge_info->lhs = index; |
1691 edge_info->rhs = x; | 1515 edge_info->rhs = x; |
1692 } | 1516 } |
1693 } | 1517 } |
1747 else if (is_gimple_min_invariant (op0) | 1571 else if (is_gimple_min_invariant (op0) |
1748 && (TREE_CODE (op1) == SSA_NAME | 1572 && (TREE_CODE (op1) == SSA_NAME |
1749 || is_gimple_min_invariant (op1))) | 1573 || is_gimple_min_invariant (op1))) |
1750 { | 1574 { |
1751 tree cond = build2 (code, boolean_type_node, op0, op1); | 1575 tree cond = build2 (code, boolean_type_node, op0, op1); |
1752 tree inverted = invert_truthvalue (cond); | 1576 tree inverted = invert_truthvalue_loc (loc, cond); |
1753 struct edge_info *edge_info; | 1577 struct edge_info *edge_info; |
1754 | 1578 |
1755 edge_info = allocate_edge_info (true_edge); | 1579 edge_info = allocate_edge_info (true_edge); |
1756 record_conditions (edge_info, cond, inverted); | 1580 record_conditions (edge_info, cond, inverted); |
1757 | 1581 |
1774 else if (TREE_CODE (op0) == SSA_NAME | 1598 else if (TREE_CODE (op0) == SSA_NAME |
1775 && (is_gimple_min_invariant (op1) | 1599 && (is_gimple_min_invariant (op1) |
1776 || TREE_CODE (op1) == SSA_NAME)) | 1600 || TREE_CODE (op1) == SSA_NAME)) |
1777 { | 1601 { |
1778 tree cond = build2 (code, boolean_type_node, op0, op1); | 1602 tree cond = build2 (code, boolean_type_node, op0, op1); |
1779 tree inverted = invert_truthvalue (cond); | 1603 tree inverted = invert_truthvalue_loc (loc, cond); |
1780 struct edge_info *edge_info; | 1604 struct edge_info *edge_info; |
1781 | 1605 |
1782 edge_info = allocate_edge_info (true_edge); | 1606 edge_info = allocate_edge_info (true_edge); |
1783 record_conditions (edge_info, cond, inverted); | 1607 record_conditions (edge_info, cond, inverted); |
1784 | 1608 |
1801 | 1625 |
1802 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ | 1626 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ |
1803 } | 1627 } |
1804 } | 1628 } |
1805 | 1629 |
1806 /* Propagate information from BB to its outgoing edges. | 1630 static void |
1807 | 1631 dom_opt_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, |
1808 This can include equivalence information implied by control statements | 1632 basic_block bb) |
1809 at the end of BB and const/copy propagation into PHIs in BB's | 1633 { |
1810 successor blocks. */ | 1634 gimple_stmt_iterator gsi; |
1811 | 1635 |
1812 static void | 1636 if (dump_file && (dump_flags & TDF_DETAILS)) |
1813 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, | 1637 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); |
1814 basic_block bb) | 1638 |
1815 { | 1639 /* Push a marker on the stacks of local information so that we know how |
1640 far to unwind when we finalize this block. */ | |
1641 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); | |
1642 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
1643 | |
1644 record_equivalences_from_incoming_edge (bb); | |
1645 | |
1646 /* PHI nodes can create equivalences too. */ | |
1647 record_equivalences_from_phis (bb); | |
1648 | |
1649 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
1650 optimize_stmt (bb, gsi); | |
1651 | |
1652 /* Now prepare to process dominated blocks. */ | |
1816 record_edge_info (bb); | 1653 record_edge_info (bb); |
1817 cprop_into_successor_phis (bb); | 1654 cprop_into_successor_phis (bb); |
1818 } | 1655 } |
1819 | 1656 |
1657 /* We have finished processing the dominator children of BB, perform | |
1658 any finalization actions in preparation for leaving this node in | |
1659 the dominator tree. */ | |
1660 | |
1661 static void | |
1662 dom_opt_leave_block (struct dom_walk_data *walk_data, basic_block bb) | |
1663 { | |
1664 gimple last; | |
1665 | |
1666 /* If we have an outgoing edge to a block with multiple incoming and | |
1667 outgoing edges, then we may be able to thread the edge, i.e., we | |
1668 may be able to statically determine which of the outgoing edges | |
1669 will be traversed when the incoming edge from BB is traversed. */ | |
1670 if (single_succ_p (bb) | |
1671 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0 | |
1672 && potentially_threadable_block (single_succ (bb))) | |
1673 { | |
1674 dom_thread_across_edge (walk_data, single_succ_edge (bb)); | |
1675 } | |
1676 else if ((last = last_stmt (bb)) | |
1677 && gimple_code (last) == GIMPLE_COND | |
1678 && EDGE_COUNT (bb->succs) == 2 | |
1679 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0 | |
1680 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0) | |
1681 { | |
1682 edge true_edge, false_edge; | |
1683 | |
1684 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); | |
1685 | |
1686 /* Only try to thread the edge if it reaches a target block with | |
1687 more than one predecessor and more than one successor. */ | |
1688 if (potentially_threadable_block (true_edge->dest)) | |
1689 { | |
1690 struct edge_info *edge_info; | |
1691 unsigned int i; | |
1692 | |
1693 /* Push a marker onto the available expression stack so that we | |
1694 unwind any expressions related to the TRUE arm before processing | |
1695 the false arm below. */ | |
1696 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); | |
1697 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
1698 | |
1699 edge_info = (struct edge_info *) true_edge->aux; | |
1700 | |
1701 /* If we have info associated with this edge, record it into | |
1702 our equivalence tables. */ | |
1703 if (edge_info) | |
1704 { | |
1705 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; | |
1706 tree lhs = edge_info->lhs; | |
1707 tree rhs = edge_info->rhs; | |
1708 | |
1709 /* If we have a simple NAME = VALUE equivalence, record it. */ | |
1710 if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
1711 record_const_or_copy (lhs, rhs); | |
1712 | |
1713 /* If we have 0 = COND or 1 = COND equivalences, record them | |
1714 into our expression hash tables. */ | |
1715 if (cond_equivalences) | |
1716 for (i = 0; i < edge_info->max_cond_equivalences; i++) | |
1717 record_cond (&cond_equivalences[i]); | |
1718 } | |
1719 | |
1720 dom_thread_across_edge (walk_data, true_edge); | |
1721 | |
1722 /* And restore the various tables to their state before | |
1723 we threaded this edge. */ | |
1724 remove_local_expressions_from_table (); | |
1725 } | |
1726 | |
1727 /* Similarly for the ELSE arm. */ | |
1728 if (potentially_threadable_block (false_edge->dest)) | |
1729 { | |
1730 struct edge_info *edge_info; | |
1731 unsigned int i; | |
1732 | |
1733 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); | |
1734 edge_info = (struct edge_info *) false_edge->aux; | |
1735 | |
1736 /* If we have info associated with this edge, record it into | |
1737 our equivalence tables. */ | |
1738 if (edge_info) | |
1739 { | |
1740 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; | |
1741 tree lhs = edge_info->lhs; | |
1742 tree rhs = edge_info->rhs; | |
1743 | |
1744 /* If we have a simple NAME = VALUE equivalence, record it. */ | |
1745 if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
1746 record_const_or_copy (lhs, rhs); | |
1747 | |
1748 /* If we have 0 = COND or 1 = COND equivalences, record them | |
1749 into our expression hash tables. */ | |
1750 if (cond_equivalences) | |
1751 for (i = 0; i < edge_info->max_cond_equivalences; i++) | |
1752 record_cond (&cond_equivalences[i]); | |
1753 } | |
1754 | |
1755 /* Now thread the edge. */ | |
1756 dom_thread_across_edge (walk_data, false_edge); | |
1757 | |
1758 /* No need to remove local expressions from our tables | |
1759 or restore vars to their original value as that will | |
1760 be done immediately below. */ | |
1761 } | |
1762 } | |
1763 | |
1764 remove_local_expressions_from_table (); | |
1765 restore_vars_to_original_value (); | |
1766 } | |
1767 | |
1820 /* Search for redundant computations in STMT. If any are found, then | 1768 /* Search for redundant computations in STMT. If any are found, then |
1821 replace them with the variable holding the result of the computation. | 1769 replace them with the variable holding the result of the computation. |
1822 | 1770 |
1823 If safe, record this expression into the available expression hash | 1771 If safe, record this expression into the available expression hash |
1824 table. */ | 1772 table. */ |
1825 | 1773 |
1826 static bool | 1774 static void |
1827 eliminate_redundant_computations (gimple_stmt_iterator* gsi) | 1775 eliminate_redundant_computations (gimple_stmt_iterator* gsi) |
1828 { | 1776 { |
1829 tree expr_type; | 1777 tree expr_type; |
1830 tree cached_lhs; | 1778 tree cached_lhs; |
1831 bool insert = true; | 1779 bool insert = true; |
1832 bool retval = false; | |
1833 bool assigns_var_p = false; | 1780 bool assigns_var_p = false; |
1834 | 1781 |
1835 gimple stmt = gsi_stmt (*gsi); | 1782 gimple stmt = gsi_stmt (*gsi); |
1836 | 1783 |
1837 tree def = gimple_get_lhs (stmt); | 1784 tree def = gimple_get_lhs (stmt); |
1839 /* Certain expressions on the RHS can be optimized away, but can not | 1786 /* Certain expressions on the RHS can be optimized away, but can not |
1840 themselves be entered into the hash tables. */ | 1787 themselves be entered into the hash tables. */ |
1841 if (! def | 1788 if (! def |
1842 || TREE_CODE (def) != SSA_NAME | 1789 || TREE_CODE (def) != SSA_NAME |
1843 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) | 1790 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) |
1844 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF) | 1791 || gimple_vdef (stmt) |
1845 /* Do not record equivalences for increments of ivs. This would create | 1792 /* Do not record equivalences for increments of ivs. This would create |
1846 overlapping live ranges for a very questionable gain. */ | 1793 overlapping live ranges for a very questionable gain. */ |
1847 || simple_iv_increment_p (stmt)) | 1794 || simple_iv_increment_p (stmt)) |
1848 insert = false; | 1795 insert = false; |
1849 | 1796 |
1870 expr_type = TREE_TYPE (gimple_switch_index (stmt)); | 1817 expr_type = TREE_TYPE (gimple_switch_index (stmt)); |
1871 else | 1818 else |
1872 gcc_unreachable (); | 1819 gcc_unreachable (); |
1873 | 1820 |
1874 if (!cached_lhs) | 1821 if (!cached_lhs) |
1875 return false; | 1822 return; |
1876 | 1823 |
1877 /* It is safe to ignore types here since we have already done | 1824 /* It is safe to ignore types here since we have already done |
1878 type checking in the hashing and equality routines. In fact | 1825 type checking in the hashing and equality routines. In fact |
1879 type checking here merely gets in the way of constant | 1826 type checking here merely gets in the way of constant |
1880 propagation. Also, make sure that it is safe to propagate | 1827 propagation. Also, make sure that it is safe to propagate |
1898 fprintf (dump_file, "'\n"); | 1845 fprintf (dump_file, "'\n"); |
1899 } | 1846 } |
1900 | 1847 |
1901 opt_stats.num_re++; | 1848 opt_stats.num_re++; |
1902 | 1849 |
1903 if (TREE_CODE (cached_lhs) == ADDR_EXPR | |
1904 || (POINTER_TYPE_P (expr_type) | |
1905 && is_gimple_min_invariant (cached_lhs))) | |
1906 retval = true; | |
1907 | |
1908 if (assigns_var_p | 1850 if (assigns_var_p |
1909 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))) | 1851 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))) |
1910 cached_lhs = fold_convert (expr_type, cached_lhs); | 1852 cached_lhs = fold_convert (expr_type, cached_lhs); |
1911 | 1853 |
1912 propagate_tree_value_into_stmt (gsi, cached_lhs); | 1854 propagate_tree_value_into_stmt (gsi, cached_lhs); |
1914 /* Since it is always necessary to mark the result as modified, | 1856 /* Since it is always necessary to mark the result as modified, |
1915 perhaps we should move this into propagate_tree_value_into_stmt | 1857 perhaps we should move this into propagate_tree_value_into_stmt |
1916 itself. */ | 1858 itself. */ |
1917 gimple_set_modified (gsi_stmt (*gsi), true); | 1859 gimple_set_modified (gsi_stmt (*gsi), true); |
1918 } | 1860 } |
1919 return retval; | |
1920 } | |
1921 | |
1922 /* Return true if statement GS is an assignment that peforms a useless | |
1923 type conversion. It is is intended to be a tuples analog of function | |
1924 tree_ssa_useless_type_conversion. */ | |
1925 | |
1926 static bool | |
1927 gimple_assign_unary_useless_conversion_p (gimple gs) | |
1928 { | |
1929 if (is_gimple_assign (gs) | |
1930 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs)) | |
1931 || gimple_assign_rhs_code (gs) == VIEW_CONVERT_EXPR | |
1932 || gimple_assign_rhs_code (gs) == NON_LVALUE_EXPR)) | |
1933 { | |
1934 tree lhs_type = TREE_TYPE (gimple_assign_lhs (gs)); | |
1935 tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (gs)); | |
1936 return useless_type_conversion_p (lhs_type, rhs_type); | |
1937 } | |
1938 | |
1939 return false; | |
1940 } | 1861 } |
1941 | 1862 |
1942 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either | 1863 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either |
1943 the available expressions table or the const_and_copies table. | 1864 the available expressions table or the const_and_copies table. |
1944 Detect and record those equivalences. */ | 1865 Detect and record those equivalences. */ |
1955 | 1876 |
1956 lhs = gimple_assign_lhs (stmt); | 1877 lhs = gimple_assign_lhs (stmt); |
1957 lhs_code = TREE_CODE (lhs); | 1878 lhs_code = TREE_CODE (lhs); |
1958 | 1879 |
1959 if (lhs_code == SSA_NAME | 1880 if (lhs_code == SSA_NAME |
1960 && (gimple_assign_single_p (stmt) | 1881 && gimple_assign_single_p (stmt)) |
1961 || gimple_assign_unary_useless_conversion_p (stmt))) | |
1962 { | 1882 { |
1963 tree rhs = gimple_assign_rhs1 (stmt); | 1883 tree rhs = gimple_assign_rhs1 (stmt); |
1964 | |
1965 /* Strip away any useless type conversions. */ | |
1966 STRIP_USELESS_TYPE_CONVERSION (rhs); | |
1967 | 1884 |
1968 /* If the RHS of the assignment is a constant or another variable that | 1885 /* If the RHS of the assignment is a constant or another variable that |
1969 may be propagated, register it in the CONST_AND_COPIES table. We | 1886 may be propagated, register it in the CONST_AND_COPIES table. We |
1970 do not need to record unwind data for this, since this is a true | 1887 do not need to record unwind data for this, since this is a true |
1971 assignment and not an equivalence inferred from a comparison. All | 1888 assignment and not an equivalence inferred from a comparison. All |
1982 fprintf (dump_file, " = "); | 1899 fprintf (dump_file, " = "); |
1983 print_generic_expr (dump_file, rhs, 0); | 1900 print_generic_expr (dump_file, rhs, 0); |
1984 fprintf (dump_file, "\n"); | 1901 fprintf (dump_file, "\n"); |
1985 } | 1902 } |
1986 | 1903 |
1987 SSA_NAME_VALUE (lhs) = rhs; | 1904 set_ssa_name_value (lhs, rhs); |
1988 } | 1905 } |
1989 } | 1906 } |
1990 | 1907 |
1991 /* A memory store, even an aliased store, creates a useful | 1908 /* A memory store, even an aliased store, creates a useful |
1992 equivalence. By exchanging the LHS and RHS, creating suitable | 1909 equivalence. By exchanging the LHS and RHS, creating suitable |
2019 SSA_NAME_DEF_STMT (rhs) = defstmt; | 1936 SSA_NAME_DEF_STMT (rhs) = defstmt; |
2020 } | 1937 } |
2021 else | 1938 else |
2022 new_stmt = gimple_build_assign (rhs, lhs); | 1939 new_stmt = gimple_build_assign (rhs, lhs); |
2023 | 1940 |
2024 create_ssa_artificial_load_stmt (new_stmt, stmt, true); | 1941 gimple_set_vuse (new_stmt, gimple_vdef (stmt)); |
2025 | 1942 |
2026 /* Finally enter the statement into the available expression | 1943 /* Finally enter the statement into the available expression |
2027 table. */ | 1944 table. */ |
2028 lookup_avail_expr (new_stmt, true); | 1945 lookup_avail_expr (new_stmt, true); |
2029 } | 1946 } |
2030 } | 1947 } |
2031 | 1948 |
2032 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from | 1949 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from |
2033 CONST_AND_COPIES. */ | 1950 CONST_AND_COPIES. */ |
2034 | 1951 |
2035 static bool | 1952 static void |
2036 cprop_operand (gimple stmt, use_operand_p op_p) | 1953 cprop_operand (gimple stmt, use_operand_p op_p) |
2037 { | 1954 { |
2038 bool may_have_exposed_new_symbols = false; | |
2039 tree val; | 1955 tree val; |
2040 tree op = USE_FROM_PTR (op_p); | 1956 tree op = USE_FROM_PTR (op_p); |
2041 | 1957 |
2042 /* If the operand has a known constant value or it is known to be a | 1958 /* If the operand has a known constant value or it is known to be a |
2043 copy of some other variable, use the value or copy stored in | 1959 copy of some other variable, use the value or copy stored in |
2052 for propagation into virtual operands. */ | 1968 for propagation into virtual operands. */ |
2053 if (!is_gimple_reg (op) | 1969 if (!is_gimple_reg (op) |
2054 && (TREE_CODE (val) != SSA_NAME | 1970 && (TREE_CODE (val) != SSA_NAME |
2055 || is_gimple_reg (val) | 1971 || is_gimple_reg (val) |
2056 || get_virtual_var (val) != get_virtual_var (op))) | 1972 || get_virtual_var (val) != get_virtual_var (op))) |
2057 return false; | 1973 return; |
2058 | 1974 |
2059 /* Do not replace hard register operands in asm statements. */ | 1975 /* Do not replace hard register operands in asm statements. */ |
2060 if (gimple_code (stmt) == GIMPLE_ASM | 1976 if (gimple_code (stmt) == GIMPLE_ASM |
2061 && !may_propagate_copy_into_asm (op)) | 1977 && !may_propagate_copy_into_asm (op)) |
2062 return false; | 1978 return; |
2063 | 1979 |
2064 /* Certain operands are not allowed to be copy propagated due | 1980 /* Certain operands are not allowed to be copy propagated due |
2065 to their interaction with exception handling and some GCC | 1981 to their interaction with exception handling and some GCC |
2066 extensions. */ | 1982 extensions. */ |
2067 if (!may_propagate_copy (op, val)) | 1983 if (!may_propagate_copy (op, val)) |
2068 return false; | 1984 return; |
2069 | 1985 |
2070 /* Do not propagate addresses that point to volatiles into memory | 1986 /* Do not propagate addresses that point to volatiles into memory |
2071 stmts without volatile operands. */ | 1987 stmts without volatile operands. */ |
2072 if (POINTER_TYPE_P (TREE_TYPE (val)) | 1988 if (POINTER_TYPE_P (TREE_TYPE (val)) |
2073 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val))) | 1989 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val))) |
2074 && gimple_has_mem_ops (stmt) | 1990 && gimple_has_mem_ops (stmt) |
2075 && !gimple_has_volatile_ops (stmt)) | 1991 && !gimple_has_volatile_ops (stmt)) |
2076 return false; | 1992 return; |
2077 | 1993 |
2078 /* Do not propagate copies if the propagated value is at a deeper loop | 1994 /* Do not propagate copies if the propagated value is at a deeper loop |
2079 depth than the propagatee. Otherwise, this may move loop variant | 1995 depth than the propagatee. Otherwise, this may move loop variant |
2080 variables outside of their loops and prevent coalescing | 1996 variables outside of their loops and prevent coalescing |
2081 opportunities. If the value was loop invariant, it will be hoisted | 1997 opportunities. If the value was loop invariant, it will be hoisted |
2082 by LICM and exposed for copy propagation. */ | 1998 by LICM and exposed for copy propagation. */ |
2083 if (loop_depth_of_name (val) > loop_depth_of_name (op)) | 1999 if (loop_depth_of_name (val) > loop_depth_of_name (op)) |
2084 return false; | 2000 return; |
2001 | |
2002 /* Do not propagate copies into simple IV increment statements. | |
2003 See PR23821 for how this can disturb IV analysis. */ | |
2004 if (TREE_CODE (val) != INTEGER_CST | |
2005 && simple_iv_increment_p (stmt)) | |
2006 return; | |
2085 | 2007 |
2086 /* Dump details. */ | 2008 /* Dump details. */ |
2087 if (dump_file && (dump_flags & TDF_DETAILS)) | 2009 if (dump_file && (dump_flags & TDF_DETAILS)) |
2088 { | 2010 { |
2089 fprintf (dump_file, " Replaced '"); | 2011 fprintf (dump_file, " Replaced '"); |
2092 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable")); | 2014 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable")); |
2093 print_generic_expr (dump_file, val, dump_flags); | 2015 print_generic_expr (dump_file, val, dump_flags); |
2094 fprintf (dump_file, "'\n"); | 2016 fprintf (dump_file, "'\n"); |
2095 } | 2017 } |
2096 | 2018 |
2097 /* If VAL is an ADDR_EXPR or a constant of pointer type, note | |
2098 that we may have exposed a new symbol for SSA renaming. */ | |
2099 if (TREE_CODE (val) == ADDR_EXPR | |
2100 || (POINTER_TYPE_P (TREE_TYPE (op)) | |
2101 && is_gimple_min_invariant (val))) | |
2102 may_have_exposed_new_symbols = true; | |
2103 | |
2104 if (TREE_CODE (val) != SSA_NAME) | 2019 if (TREE_CODE (val) != SSA_NAME) |
2105 opt_stats.num_const_prop++; | 2020 opt_stats.num_const_prop++; |
2106 else | 2021 else |
2107 opt_stats.num_copy_prop++; | 2022 opt_stats.num_copy_prop++; |
2108 | 2023 |
2111 /* And note that we modified this statement. This is now | 2026 /* And note that we modified this statement. This is now |
2112 safe, even if we changed virtual operands since we will | 2027 safe, even if we changed virtual operands since we will |
2113 rescan the statement and rewrite its operands again. */ | 2028 rescan the statement and rewrite its operands again. */ |
2114 gimple_set_modified (stmt, true); | 2029 gimple_set_modified (stmt, true); |
2115 } | 2030 } |
2116 return may_have_exposed_new_symbols; | |
2117 } | 2031 } |
2118 | 2032 |
2119 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current | 2033 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current |
2120 known value for that SSA_NAME (or NULL if no value is known). | 2034 known value for that SSA_NAME (or NULL if no value is known). |
2121 | 2035 |
2122 Propagate values from CONST_AND_COPIES into the uses, vuses and | 2036 Propagate values from CONST_AND_COPIES into the uses, vuses and |
2123 vdef_ops of STMT. */ | 2037 vdef_ops of STMT. */ |
2124 | 2038 |
2125 static bool | 2039 static void |
2126 cprop_into_stmt (gimple stmt) | 2040 cprop_into_stmt (gimple stmt) |
2127 { | 2041 { |
2128 bool may_have_exposed_new_symbols = false; | |
2129 use_operand_p op_p; | 2042 use_operand_p op_p; |
2130 ssa_op_iter iter; | 2043 ssa_op_iter iter; |
2131 | 2044 |
2132 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES) | 2045 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES) |
2133 { | 2046 { |
2134 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME) | 2047 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME) |
2135 may_have_exposed_new_symbols |= cprop_operand (stmt, op_p); | 2048 cprop_operand (stmt, op_p); |
2136 } | 2049 } |
2137 | |
2138 return may_have_exposed_new_symbols; | |
2139 } | 2050 } |
2140 | 2051 |
2141 /* Optimize the statement pointed to by iterator SI. | 2052 /* Optimize the statement pointed to by iterator SI. |
2142 | 2053 |
2143 We try to perform some simplistic global redundancy elimination and | 2054 We try to perform some simplistic global redundancy elimination and |
2144 constant propagation: | 2055 constant propagation: |
2145 | 2056 |
2146 1- To detect global redundancy, we keep track of expressions that have | 2057 1- To detect global redundancy, we keep track of expressions that have |
2147 been computed in this block and its dominators. If we find that the | 2058 been computed in this block and its dominators. If we find that the |
2152 simplistic constant and copy propagation. When a constant or copy | 2063 simplistic constant and copy propagation. When a constant or copy |
2153 assignment is found, we map the value on the RHS of the assignment to | 2064 assignment is found, we map the value on the RHS of the assignment to |
2154 the variable in the LHS in the CONST_AND_COPIES table. */ | 2065 the variable in the LHS in the CONST_AND_COPIES table. */ |
2155 | 2066 |
2156 static void | 2067 static void |
2157 optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, | 2068 optimize_stmt (basic_block bb, gimple_stmt_iterator si) |
2158 basic_block bb, gimple_stmt_iterator si) | |
2159 { | 2069 { |
2160 gimple stmt, old_stmt; | 2070 gimple stmt, old_stmt; |
2161 bool may_optimize_p; | 2071 bool may_optimize_p; |
2162 bool may_have_exposed_new_symbols; | |
2163 bool modified_p = false; | 2072 bool modified_p = false; |
2164 | 2073 |
2165 old_stmt = stmt = gsi_stmt (si); | 2074 old_stmt = stmt = gsi_stmt (si); |
2166 | 2075 |
2167 if (gimple_code (stmt) == GIMPLE_COND) | 2076 if (gimple_code (stmt) == GIMPLE_COND) |
2168 canonicalize_comparison (stmt); | 2077 canonicalize_comparison (stmt); |
2169 | 2078 |
2170 update_stmt_if_modified (stmt); | 2079 update_stmt_if_modified (stmt); |
2171 opt_stats.num_stmts++; | 2080 opt_stats.num_stmts++; |
2172 push_stmt_changes (gsi_stmt_ptr (&si)); | |
2173 | 2081 |
2174 if (dump_file && (dump_flags & TDF_DETAILS)) | 2082 if (dump_file && (dump_flags & TDF_DETAILS)) |
2175 { | 2083 { |
2176 fprintf (dump_file, "Optimizing statement "); | 2084 fprintf (dump_file, "Optimizing statement "); |
2177 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | 2085 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
2178 } | 2086 } |
2179 | 2087 |
2180 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */ | 2088 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */ |
2181 may_have_exposed_new_symbols = cprop_into_stmt (stmt); | 2089 cprop_into_stmt (stmt); |
2182 | 2090 |
2183 /* If the statement has been modified with constant replacements, | 2091 /* If the statement has been modified with constant replacements, |
2184 fold its RHS before checking for redundant computations. */ | 2092 fold its RHS before checking for redundant computations. */ |
2185 if (gimple_modified_p (stmt)) | 2093 if (gimple_modified_p (stmt)) |
2186 { | 2094 { |
2189 /* Try to fold the statement making sure that STMT is kept | 2097 /* Try to fold the statement making sure that STMT is kept |
2190 up to date. */ | 2098 up to date. */ |
2191 if (fold_stmt (&si)) | 2099 if (fold_stmt (&si)) |
2192 { | 2100 { |
2193 stmt = gsi_stmt (si); | 2101 stmt = gsi_stmt (si); |
2102 gimple_set_modified (stmt, true); | |
2194 | 2103 |
2195 if (dump_file && (dump_flags & TDF_DETAILS)) | 2104 if (dump_file && (dump_flags & TDF_DETAILS)) |
2196 { | 2105 { |
2197 fprintf (dump_file, " Folded to: "); | 2106 fprintf (dump_file, " Folded to: "); |
2198 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | 2107 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
2209 rhs = gimple_switch_index (stmt); | 2118 rhs = gimple_switch_index (stmt); |
2210 | 2119 |
2211 if (rhs && TREE_CODE (rhs) == ADDR_EXPR) | 2120 if (rhs && TREE_CODE (rhs) == ADDR_EXPR) |
2212 recompute_tree_invariant_for_addr_expr (rhs); | 2121 recompute_tree_invariant_for_addr_expr (rhs); |
2213 | 2122 |
2214 /* Constant/copy propagation above may change the set of | |
2215 virtual operands associated with this statement. Folding | |
2216 may remove the need for some virtual operands. | |
2217 | |
2218 Indicate we will need to rescan and rewrite the statement. */ | |
2219 may_have_exposed_new_symbols = true; | |
2220 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called, | 2123 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called, |
2221 even if fold_stmt updated the stmt already and thus cleared | 2124 even if fold_stmt updated the stmt already and thus cleared |
2222 gimple_modified_p flag on it. */ | 2125 gimple_modified_p flag on it. */ |
2223 modified_p = true; | 2126 modified_p = true; |
2224 } | 2127 } |
2234 || gimple_code (stmt) == GIMPLE_COND | 2137 || gimple_code (stmt) == GIMPLE_COND |
2235 || gimple_code (stmt) == GIMPLE_SWITCH)); | 2138 || gimple_code (stmt) == GIMPLE_SWITCH)); |
2236 | 2139 |
2237 if (may_optimize_p) | 2140 if (may_optimize_p) |
2238 { | 2141 { |
2239 may_have_exposed_new_symbols |= eliminate_redundant_computations (&si); | 2142 if (gimple_code (stmt) == GIMPLE_CALL) |
2143 { | |
2144 /* Resolve __builtin_constant_p. If it hasn't been | |
2145 folded to integer_one_node by now, it's fairly | |
2146 certain that the value simply isn't constant. */ | |
2147 tree callee = gimple_call_fndecl (stmt); | |
2148 if (callee | |
2149 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL | |
2150 && DECL_FUNCTION_CODE (callee) == BUILT_IN_CONSTANT_P) | |
2151 { | |
2152 propagate_tree_value_into_stmt (&si, integer_zero_node); | |
2153 stmt = gsi_stmt (si); | |
2154 } | |
2155 } | |
2156 | |
2157 update_stmt_if_modified (stmt); | |
2158 eliminate_redundant_computations (&si); | |
2240 stmt = gsi_stmt (si); | 2159 stmt = gsi_stmt (si); |
2241 } | 2160 } |
2242 | 2161 |
2243 /* Record any additional equivalences created by this statement. */ | 2162 /* Record any additional equivalences created by this statement. */ |
2244 if (is_gimple_assign (stmt)) | 2163 if (is_gimple_assign (stmt)) |
2246 | 2165 |
2247 /* If STMT is a COND_EXPR and it was modified, then we may know | 2166 /* If STMT is a COND_EXPR and it was modified, then we may know |
2248 where it goes. If that is the case, then mark the CFG as altered. | 2167 where it goes. If that is the case, then mark the CFG as altered. |
2249 | 2168 |
2250 This will cause us to later call remove_unreachable_blocks and | 2169 This will cause us to later call remove_unreachable_blocks and |
2251 cleanup_tree_cfg when it is safe to do so. It is not safe to | 2170 cleanup_tree_cfg when it is safe to do so. It is not safe to |
2252 clean things up here since removal of edges and such can trigger | 2171 clean things up here since removal of edges and such can trigger |
2253 the removal of PHI nodes, which in turn can release SSA_NAMEs to | 2172 the removal of PHI nodes, which in turn can release SSA_NAMEs to |
2254 the manager. | 2173 the manager. |
2255 | 2174 |
2256 That's all fine and good, except that once SSA_NAMEs are released | 2175 That's all fine and good, except that once SSA_NAMEs are released |
2271 into the SSA_NAME manager. */ | 2190 into the SSA_NAME manager. */ |
2272 if (gimple_modified_p (stmt) || modified_p) | 2191 if (gimple_modified_p (stmt) || modified_p) |
2273 { | 2192 { |
2274 tree val = NULL; | 2193 tree val = NULL; |
2275 | 2194 |
2195 update_stmt_if_modified (stmt); | |
2196 | |
2276 if (gimple_code (stmt) == GIMPLE_COND) | 2197 if (gimple_code (stmt) == GIMPLE_COND) |
2277 val = fold_binary (gimple_cond_code (stmt), boolean_type_node, | 2198 val = fold_binary_loc (gimple_location (stmt), |
2199 gimple_cond_code (stmt), boolean_type_node, | |
2278 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); | 2200 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); |
2279 else if (gimple_code (stmt) == GIMPLE_SWITCH) | 2201 else if (gimple_code (stmt) == GIMPLE_SWITCH) |
2280 val = gimple_switch_index (stmt); | 2202 val = gimple_switch_index (stmt); |
2281 | 2203 |
2282 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val)) | 2204 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val)) |
2289 bitmap_set_bit (need_eh_cleanup, bb->index); | 2211 bitmap_set_bit (need_eh_cleanup, bb->index); |
2290 if (dump_file && (dump_flags & TDF_DETAILS)) | 2212 if (dump_file && (dump_flags & TDF_DETAILS)) |
2291 fprintf (dump_file, " Flagged to clear EH edges.\n"); | 2213 fprintf (dump_file, " Flagged to clear EH edges.\n"); |
2292 } | 2214 } |
2293 } | 2215 } |
2294 | |
2295 if (may_have_exposed_new_symbols) | |
2296 { | |
2297 /* Queue the statement to be re-scanned after all the | |
2298 AVAIL_EXPRS have been processed. The change buffer stack for | |
2299 all the pushed statements will be processed when this queue | |
2300 is emptied. */ | |
2301 VEC_safe_push (gimple_p, heap, stmts_to_rescan, gsi_stmt_ptr (&si)); | |
2302 } | |
2303 else | |
2304 { | |
2305 /* Otherwise, just discard the recently pushed change buffer. If | |
2306 not, the STMTS_TO_RESCAN queue will get out of synch with the | |
2307 change buffer stack. */ | |
2308 discard_stmt_changes (gsi_stmt_ptr (&si)); | |
2309 } | |
2310 } | 2216 } |
2311 | 2217 |
2312 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. | 2218 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. |
2313 If found, return its LHS. Otherwise insert STMT in the table and | 2219 If found, return its LHS. Otherwise insert STMT in the table and |
2314 return NULL_TREE. | 2220 return NULL_TREE. |
2351 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash, | 2257 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash, |
2352 (insert ? INSERT : NO_INSERT)); | 2258 (insert ? INSERT : NO_INSERT)); |
2353 if (slot == NULL) | 2259 if (slot == NULL) |
2354 { | 2260 { |
2355 free (element); | 2261 free (element); |
2356 return NULL_TREE; | 2262 return NULL_TREE; |
2357 } | 2263 } |
2358 | 2264 |
2359 if (*slot == NULL) | 2265 if (*slot == NULL) |
2360 { | 2266 { |
2361 *slot = (void *) element; | 2267 *slot = (void *) element; |
2403 avail_expr_hash (const void *p) | 2309 avail_expr_hash (const void *p) |
2404 { | 2310 { |
2405 gimple stmt = ((const struct expr_hash_elt *)p)->stmt; | 2311 gimple stmt = ((const struct expr_hash_elt *)p)->stmt; |
2406 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr; | 2312 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr; |
2407 tree vuse; | 2313 tree vuse; |
2408 ssa_op_iter iter; | |
2409 hashval_t val = 0; | 2314 hashval_t val = 0; |
2410 | 2315 |
2411 val = iterative_hash_hashable_expr (expr, val); | 2316 val = iterative_hash_hashable_expr (expr, val); |
2412 | 2317 |
2413 /* If the hash table entry is not associated with a statement, then we | 2318 /* If the hash table entry is not associated with a statement, then we |
2414 can just hash the expression and not worry about virtual operands | 2319 can just hash the expression and not worry about virtual operands |
2415 and such. */ | 2320 and such. */ |
2416 if (!stmt) | 2321 if (!stmt) |
2417 return val; | 2322 return val; |
2418 | 2323 |
2419 /* Add the SSA version numbers of every vuse operand. This is important | 2324 /* Add the SSA version numbers of the vuse operand. This is important |
2420 because compound variables like arrays are not renamed in the | 2325 because compound variables like arrays are not renamed in the |
2421 operands. Rather, the rename is done on the virtual variable | 2326 operands. Rather, the rename is done on the virtual variable |
2422 representing all the elements of the array. */ | 2327 representing all the elements of the array. */ |
2423 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE) | 2328 if ((vuse = gimple_vuse (stmt))) |
2424 val = iterative_hash_expr (vuse, val); | 2329 val = iterative_hash_expr (vuse, val); |
2425 | 2330 |
2426 return val; | 2331 return val; |
2427 } | 2332 } |
2428 | 2333 |
2460 same VUSE operands. */ | 2365 same VUSE operands. */ |
2461 if (hashable_expr_equal_p (expr1, expr2) | 2366 if (hashable_expr_equal_p (expr1, expr2) |
2462 && types_compatible_p (expr1->type, expr2->type)) | 2367 && types_compatible_p (expr1->type, expr2->type)) |
2463 { | 2368 { |
2464 /* Note that STMT1 and/or STMT2 may be NULL. */ | 2369 /* Note that STMT1 and/or STMT2 may be NULL. */ |
2465 bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE); | 2370 return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE) |
2466 return ret; | 2371 == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE)); |
2467 } | 2372 } |
2468 | 2373 |
2469 return false; | 2374 return false; |
2470 } | 2375 } |
2471 | 2376 |
2473 up degenerate PHIs created by or exposed by jump threading. */ | 2378 up degenerate PHIs created by or exposed by jump threading. */ |
2474 | 2379 |
2475 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return | 2380 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return |
2476 NULL. */ | 2381 NULL. */ |
2477 | 2382 |
2478 static tree | 2383 tree |
2479 degenerate_phi_result (gimple phi) | 2384 degenerate_phi_result (gimple phi) |
2480 { | 2385 { |
2481 tree lhs = gimple_phi_result (phi); | 2386 tree lhs = gimple_phi_result (phi); |
2482 tree val = NULL; | 2387 tree val = NULL; |
2483 size_t i; | 2388 size_t i; |
2493 continue; | 2398 continue; |
2494 else if (!arg) | 2399 else if (!arg) |
2495 break; | 2400 break; |
2496 else if (!val) | 2401 else if (!val) |
2497 val = arg; | 2402 val = arg; |
2498 else if (!operand_equal_p (arg, val, 0)) | 2403 else if (arg == val) |
2404 continue; | |
2405 /* We bring in some of operand_equal_p not only to speed things | |
2406 up, but also to avoid crashing when dereferencing the type of | |
2407 a released SSA name. */ | |
2408 else if (TREE_CODE (val) != TREE_CODE (arg) | |
2409 || TREE_CODE (val) == SSA_NAME | |
2410 || !operand_equal_p (arg, val, 0)) | |
2499 break; | 2411 break; |
2500 } | 2412 } |
2501 return (i == gimple_phi_num_args (phi) ? val : NULL); | 2413 return (i == gimple_phi_num_args (phi) ? val : NULL); |
2502 } | 2414 } |
2503 | 2415 |
2557 into a trivial copy or constant initialization, set the | 2469 into a trivial copy or constant initialization, set the |
2558 appropriate bit in INTERESTING_NAMEs so that we will visit those | 2470 appropriate bit in INTERESTING_NAMEs so that we will visit those |
2559 nodes as well in an effort to pick up secondary optimization | 2471 nodes as well in an effort to pick up secondary optimization |
2560 opportunities. */ | 2472 opportunities. */ |
2561 | 2473 |
2562 static void | 2474 static void |
2563 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names) | 2475 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names) |
2564 { | 2476 { |
2565 /* First verify that propagation is valid and isn't going to move a | 2477 /* First verify that propagation is valid and isn't going to move a |
2566 loop variant variable outside its loop. */ | 2478 loop variant variable outside its loop. */ |
2567 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) | 2479 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) |
2584 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable")); | 2496 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable")); |
2585 print_generic_expr (dump_file, rhs, dump_flags); | 2497 print_generic_expr (dump_file, rhs, dump_flags); |
2586 fprintf (dump_file, "'\n"); | 2498 fprintf (dump_file, "'\n"); |
2587 } | 2499 } |
2588 | 2500 |
2589 /* Walk over every use of LHS and try to replace the use with RHS. | 2501 /* Walk over every use of LHS and try to replace the use with RHS. |
2590 At this point the only reason why such a propagation would not | 2502 At this point the only reason why such a propagation would not |
2591 be successful would be if the use occurs in an ASM_EXPR. */ | 2503 be successful would be if the use occurs in an ASM_EXPR. */ |
2592 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) | 2504 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) |
2593 { | 2505 { |
2594 | 2506 /* Leave debug stmts alone. If we succeed in propagating |
2507 all non-debug uses, we'll drop the DEF, and propagation | |
2508 into debug stmts will occur then. */ | |
2509 if (gimple_debug_bind_p (use_stmt)) | |
2510 continue; | |
2511 | |
2595 /* It's not always safe to propagate into an ASM_EXPR. */ | 2512 /* It's not always safe to propagate into an ASM_EXPR. */ |
2596 if (gimple_code (use_stmt) == GIMPLE_ASM | 2513 if (gimple_code (use_stmt) == GIMPLE_ASM |
2597 && ! may_propagate_copy_into_asm (lhs)) | 2514 && ! may_propagate_copy_into_asm (lhs)) |
2598 { | 2515 { |
2599 all = false; | 2516 all = false; |
2604 if (dump_file && (dump_flags & TDF_DETAILS)) | 2521 if (dump_file && (dump_flags & TDF_DETAILS)) |
2605 { | 2522 { |
2606 fprintf (dump_file, " Original statement:"); | 2523 fprintf (dump_file, " Original statement:"); |
2607 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); | 2524 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); |
2608 } | 2525 } |
2609 | |
2610 push_stmt_changes (&use_stmt); | |
2611 | 2526 |
2612 /* Propagate the RHS into this use of the LHS. */ | 2527 /* Propagate the RHS into this use of the LHS. */ |
2613 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) | 2528 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) |
2614 propagate_value (use_p, rhs); | 2529 propagate_value (use_p, rhs); |
2615 | 2530 |
2641 { | 2556 { |
2642 tree result = get_lhs_or_phi_result (use_stmt); | 2557 tree result = get_lhs_or_phi_result (use_stmt); |
2643 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); | 2558 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); |
2644 } | 2559 } |
2645 | 2560 |
2646 discard_stmt_changes (&use_stmt); | |
2647 continue; | 2561 continue; |
2648 } | 2562 } |
2649 | 2563 |
2650 /* From this point onward we are propagating into a | 2564 /* From this point onward we are propagating into a |
2651 real statement. Folding may (or may not) be possible, | 2565 real statement. Folding may (or may not) be possible, |
2652 we may expose new operands, expose dead EH edges, | 2566 we may expose new operands, expose dead EH edges, |
2653 etc. */ | 2567 etc. */ |
2654 /* NOTE tuples. In the tuples world, fold_stmt_inplace | 2568 /* NOTE tuples. In the tuples world, fold_stmt_inplace |
2655 cannot fold a call that simplifies to a constant, | 2569 cannot fold a call that simplifies to a constant, |
2658 transformation in-place. We might want to consider | 2572 transformation in-place. We might want to consider |
2659 using the more general fold_stmt here. */ | 2573 using the more general fold_stmt here. */ |
2660 fold_stmt_inplace (use_stmt); | 2574 fold_stmt_inplace (use_stmt); |
2661 | 2575 |
2662 /* Sometimes propagation can expose new operands to the | 2576 /* Sometimes propagation can expose new operands to the |
2663 renamer. Note this will call update_stmt at the | 2577 renamer. */ |
2664 appropriate time. */ | 2578 update_stmt (use_stmt); |
2665 pop_stmt_changes (&use_stmt); | |
2666 | 2579 |
2667 /* Dump details. */ | 2580 /* Dump details. */ |
2668 if (dump_file && (dump_flags & TDF_DETAILS)) | 2581 if (dump_file && (dump_flags & TDF_DETAILS)) |
2669 { | 2582 { |
2670 fprintf (dump_file, " Updated statement:"); | 2583 fprintf (dump_file, " Updated statement:"); |
2707 || gimple_code (use_stmt) == GIMPLE_GOTO) | 2620 || gimple_code (use_stmt) == GIMPLE_GOTO) |
2708 { | 2621 { |
2709 tree val; | 2622 tree val; |
2710 | 2623 |
2711 if (gimple_code (use_stmt) == GIMPLE_COND) | 2624 if (gimple_code (use_stmt) == GIMPLE_COND) |
2712 val = fold_binary (gimple_cond_code (use_stmt), | 2625 val = fold_binary_loc (gimple_location (use_stmt), |
2626 gimple_cond_code (use_stmt), | |
2713 boolean_type_node, | 2627 boolean_type_node, |
2714 gimple_cond_lhs (use_stmt), | 2628 gimple_cond_lhs (use_stmt), |
2715 gimple_cond_rhs (use_stmt)); | 2629 gimple_cond_rhs (use_stmt)); |
2716 else if (gimple_code (use_stmt) == GIMPLE_SWITCH) | 2630 else if (gimple_code (use_stmt) == GIMPLE_SWITCH) |
2717 val = gimple_switch_index (use_stmt); | 2631 val = gimple_switch_index (use_stmt); |
2766 te->probability = REG_BR_PROB_BASE; | 2680 te->probability = REG_BR_PROB_BASE; |
2767 } | 2681 } |
2768 } | 2682 } |
2769 } | 2683 } |
2770 | 2684 |
2771 /* Ensure there is nothing else to do. */ | 2685 /* Ensure there is nothing else to do. */ |
2772 gcc_assert (!all || has_zero_uses (lhs)); | 2686 gcc_assert (!all || has_zero_uses (lhs)); |
2773 | 2687 |
2774 /* If we were able to propagate away all uses of LHS, then | 2688 /* If we were able to propagate away all uses of LHS, then |
2775 we can remove STMT. */ | 2689 we can remove STMT. */ |
2776 if (all) | 2690 if (all) |
2890 SSA_NAME_VERSION. | 2804 SSA_NAME_VERSION. |
2891 | 2805 |
2892 A set bit indicates that the statement or PHI node which | 2806 A set bit indicates that the statement or PHI node which |
2893 defines the SSA_NAME should be (re)examined to determine if | 2807 defines the SSA_NAME should be (re)examined to determine if |
2894 it has become a degenerate PHI or trivial const/copy propagation | 2808 it has become a degenerate PHI or trivial const/copy propagation |
2895 opportunity. | 2809 opportunity. |
2896 | 2810 |
2897 Experiments have show we generally get better compilation | 2811 Experiments have show we generally get better compilation |
2898 time behavior with bitmaps rather than sbitmaps. */ | 2812 time behavior with bitmaps rather than sbitmaps. */ |
2899 interesting_names = BITMAP_ALLOC (NULL); | 2813 interesting_names = BITMAP_ALLOC (NULL); |
2900 interesting_names1 = BITMAP_ALLOC (NULL); | 2814 interesting_names1 = BITMAP_ALLOC (NULL); |
2963 eliminate_degenerate_phis, /* execute */ | 2877 eliminate_degenerate_phis, /* execute */ |
2964 NULL, /* sub */ | 2878 NULL, /* sub */ |
2965 NULL, /* next */ | 2879 NULL, /* next */ |
2966 0, /* static_pass_number */ | 2880 0, /* static_pass_number */ |
2967 TV_TREE_PHI_CPROP, /* tv_id */ | 2881 TV_TREE_PHI_CPROP, /* tv_id */ |
2968 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ | 2882 PROP_cfg | PROP_ssa, /* properties_required */ |
2969 0, /* properties_provided */ | 2883 0, /* properties_provided */ |
2970 0, /* properties_destroyed */ | 2884 0, /* properties_destroyed */ |
2971 0, /* todo_flags_start */ | 2885 0, /* todo_flags_start */ |
2972 TODO_cleanup_cfg | 2886 TODO_cleanup_cfg |
2973 | TODO_dump_func | 2887 | TODO_dump_func |
2974 | TODO_ggc_collect | 2888 | TODO_ggc_collect |
2975 | TODO_verify_ssa | 2889 | TODO_verify_ssa |
2976 | TODO_verify_stmts | 2890 | TODO_verify_stmts |
2977 | TODO_update_ssa /* todo_flags_finish */ | 2891 | TODO_update_ssa /* todo_flags_finish */ |
2978 } | 2892 } |