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 }