1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to
20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA. */
25 #include "coretypes.h"
32 #include "basic-block.h"
37 #include "diagnostic.h"
39 #include "tree-dump.h"
40 #include "tree-flow.h"
43 #include "tree-pass.h"
44 #include "tree-ssa-propagate.h"
45 #include "langhooks.h"
48 /* This file implements optimizations on the dominator tree. */
51 /* Structure for recording edge equivalences as well as any pending
52 edge redirections during the dominator optimizer.
54 Computing and storing the edge equivalences instead of creating
55 them on-demand can save significant amounts of time, particularly
56 for pathological cases involving switch statements.
58 These structures live for a single iteration of the dominator
59 optimizer in the edge's AUX field. At the end of an iteration we
60 free each of these structures and update the AUX field to point
61 to any requested redirection target (the code for updating the
62 CFG and SSA graph for edge redirection expects redirection edge
63 targets to be in the AUX field for each edge. */
67 /* If this edge creates a simple equivalence, the LHS and RHS of
68 the equivalence will be stored here. */
72 /* Traversing an edge may also indicate one or more particular conditions
73 are true or false. The number of recorded conditions can vary, but
74 can be determined by the condition's code. So we have an array
75 and its maximum index rather than use a varray. */
76 tree *cond_equivalences;
77 unsigned int max_cond_equivalences;
81 /* Hash table with expressions made available during the renaming process.
82 When an assignment of the form X_i = EXPR is found, the statement is
83 stored in this table. If the same expression EXPR is later found on the
84 RHS of another statement, it is replaced with X_i (thus performing
85 global redundancy elimination). Similarly as we pass through conditionals
86 we record the conditional itself as having either a true or false value
88 static htab_t avail_exprs;
90 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
91 expressions it enters into the hash table along with a marker entry
92 (null). When we finish processing the block, we pop off entries and
93 remove the expressions from the global hash table until we hit the
95 static VEC(tree,heap) *avail_exprs_stack;
97 /* Stack of statements we need to rescan during finalization for newly
100 Statement rescanning must occur after the current block's available
101 expressions are removed from AVAIL_EXPRS. Else we may change the
102 hash code for an expression and be unable to find/remove it from
104 static VEC(tree,heap) *stmts_to_rescan;
106 /* Structure for entries in the expression hash table.
108 This requires more memory for the hash table entries, but allows us
109 to avoid creating silly tree nodes and annotations for conditionals,
110 eliminates 2 global hash tables and two block local varrays.
112 It also allows us to reduce the number of hash table lookups we
113 have to perform in lookup_avail_expr and finally it allows us to
114 significantly reduce the number of calls into the hashing routine
119 /* The value (lhs) of this expression. */
122 /* The expression (rhs) we want to record. */
125 /* The stmt pointer if this element corresponds to a statement. */
128 /* The hash value for RHS/ann. */
132 /* Stack of dest,src pairs that need to be restored during finalization.
134 A NULL entry is used to mark the end of pairs which need to be
135 restored during finalization of this block. */
136 static VEC(tree,heap) *const_and_copies_stack;
138 /* Track whether or not we have changed the control flow graph. */
139 static bool cfg_altered;
141 /* Bitmap of blocks that have had EH statements cleaned. We should
142 remove their dead edges eventually. */
143 static bitmap need_eh_cleanup;
145 /* Statistics for dominator optimizations. */
149 long num_exprs_considered;
155 static struct opt_stats_d opt_stats;
163 /* Local functions. */
164 static void optimize_stmt (struct dom_walk_data *,
166 block_stmt_iterator);
167 static tree lookup_avail_expr (tree, bool);
168 static hashval_t avail_expr_hash (const void *);
169 static hashval_t real_avail_expr_hash (const void *);
170 static int avail_expr_eq (const void *, const void *);
171 static void htab_statistics (FILE *, htab_t);
172 static void record_cond (tree, tree);
173 static void record_const_or_copy (tree, tree);
174 static void record_equality (tree, tree);
175 static void record_equivalences_from_phis (basic_block);
176 static void record_equivalences_from_incoming_edge (basic_block);
177 static bool eliminate_redundant_computations (tree);
178 static void record_equivalences_from_stmt (tree, int, stmt_ann_t);
179 static void dom_thread_across_edge (struct dom_walk_data *, edge);
180 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
181 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
182 static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
183 static void remove_local_expressions_from_table (void);
184 static void restore_vars_to_original_value (void);
185 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
188 /* Allocate an EDGE_INFO for edge E and attach it to E.
189 Return the new EDGE_INFO structure. */
191 static struct edge_info *
192 allocate_edge_info (edge e)
194 struct edge_info *edge_info;
196 edge_info = XCNEW (struct edge_info);
202 /* Free all EDGE_INFO structures associated with edges in the CFG.
203 If a particular edge can be threaded, copy the redirection
204 target from the EDGE_INFO structure into the edge's AUX field
205 as required by code to update the CFG and SSA graph for
209 free_all_edge_infos (void)
217 FOR_EACH_EDGE (e, ei, bb->preds)
219 struct edge_info *edge_info = (struct edge_info *) e->aux;
223 if (edge_info->cond_equivalences)
224 free (edge_info->cond_equivalences);
232 /* Jump threading, redundancy elimination and const/copy propagation.
234 This pass may expose new symbols that need to be renamed into SSA. For
235 every new symbol exposed, its corresponding bit will be set in
239 tree_ssa_dominator_optimize (void)
241 struct dom_walk_data walk_data;
243 struct loops loops_info;
245 memset (&opt_stats, 0, sizeof (opt_stats));
247 /* Create our hash tables. */
248 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
249 avail_exprs_stack = VEC_alloc (tree, heap, 20);
250 const_and_copies_stack = VEC_alloc (tree, heap, 20);
251 stmts_to_rescan = VEC_alloc (tree, heap, 20);
252 need_eh_cleanup = BITMAP_ALLOC (NULL);
254 /* Setup callbacks for the generic dominator tree walker. */
255 walk_data.walk_stmts_backward = false;
256 walk_data.dom_direction = CDI_DOMINATORS;
257 walk_data.initialize_block_local_data = NULL;
258 walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
259 walk_data.before_dom_children_walk_stmts = optimize_stmt;
260 walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
261 walk_data.after_dom_children_before_stmts = NULL;
262 walk_data.after_dom_children_walk_stmts = NULL;
263 walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
264 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
265 When we attach more stuff we'll need to fill this out with a real
267 walk_data.global_data = NULL;
268 walk_data.block_local_data_size = 0;
269 walk_data.interesting_blocks = NULL;
271 /* Now initialize the dominator walker. */
272 init_walk_dominator_tree (&walk_data);
274 calculate_dominance_info (CDI_DOMINATORS);
276 /* We need to know which edges exit loops so that we can
277 aggressively thread through loop headers to an exit
279 flow_loops_find (&loops_info);
280 mark_loop_exit_edges (&loops_info);
281 flow_loops_free (&loops_info);
283 /* Clean up the CFG so that any forwarder blocks created by loop
284 canonicalization are removed. */
286 calculate_dominance_info (CDI_DOMINATORS);
288 /* We need accurate information regarding back edges in the CFG
289 for jump threading. */
290 mark_dfs_back_edges ();
292 /* Recursively walk the dominator tree optimizing statements. */
293 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
296 block_stmt_iterator bsi;
300 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
301 update_stmt_if_modified (bsi_stmt (bsi));
305 /* If we exposed any new variables, go ahead and put them into
306 SSA form now, before we handle jump threading. This simplifies
307 interactions between rewriting of _DECL nodes into SSA form
308 and rewriting SSA_NAME nodes into SSA form after block
309 duplication and CFG manipulation. */
310 update_ssa (TODO_update_ssa);
312 free_all_edge_infos ();
314 /* Thread jumps, creating duplicate blocks as needed. */
315 cfg_altered |= thread_through_all_blocks ();
317 /* Removal of statements may make some EH edges dead. Purge
318 such edges from the CFG as needed. */
319 if (!bitmap_empty_p (need_eh_cleanup))
321 cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
322 bitmap_zero (need_eh_cleanup);
326 free_dominance_info (CDI_DOMINATORS);
328 /* Finally, remove everything except invariants in SSA_NAME_VALUE.
330 Long term we will be able to let everything in SSA_NAME_VALUE
331 persist. However, for now, we know this is the safe thing to do. */
332 for (i = 0; i < num_ssa_names; i++)
334 tree name = ssa_name (i);
340 value = SSA_NAME_VALUE (name);
341 if (value && !is_gimple_min_invariant (value))
342 SSA_NAME_VALUE (name) = NULL;
345 /* Debugging dumps. */
346 if (dump_file && (dump_flags & TDF_STATS))
347 dump_dominator_optimization_stats (dump_file);
349 /* Delete our main hashtable. */
350 htab_delete (avail_exprs);
352 /* And finalize the dominator walker. */
353 fini_walk_dominator_tree (&walk_data);
355 /* Free asserted bitmaps and stacks. */
356 BITMAP_FREE (need_eh_cleanup);
358 VEC_free (tree, heap, avail_exprs_stack);
359 VEC_free (tree, heap, const_and_copies_stack);
360 VEC_free (tree, heap, stmts_to_rescan);
364 gate_dominator (void)
366 return flag_tree_dom != 0;
369 struct tree_opt_pass pass_dominator =
372 gate_dominator, /* gate */
373 tree_ssa_dominator_optimize, /* execute */
376 0, /* static_pass_number */
377 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
378 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
379 0, /* properties_provided */
380 PROP_smt_usage, /* properties_destroyed */
381 0, /* todo_flags_start */
386 | TODO_update_smt_usage, /* todo_flags_finish */
391 /* Given a stmt CONDSTMT containing a COND_EXPR, canonicalize the
392 COND_EXPR into a canonical form. */
395 canonicalize_comparison (tree condstmt)
397 tree cond = COND_EXPR_COND (condstmt);
400 enum tree_code code = TREE_CODE (cond);
402 if (!COMPARISON_CLASS_P (cond))
405 op0 = TREE_OPERAND (cond, 0);
406 op1 = TREE_OPERAND (cond, 1);
408 /* If it would be profitable to swap the operands, then do so to
409 canonicalize the statement, enabling better optimization.
411 By placing canonicalization of such expressions here we
412 transparently keep statements in canonical form, even
413 when the statement is modified. */
414 if (tree_swap_operands_p (op0, op1, false))
416 /* For relationals we need to swap the operands
417 and change the code. */
423 TREE_SET_CODE (cond, swap_tree_comparison (code));
424 swap_tree_operands (condstmt,
425 &TREE_OPERAND (cond, 0),
426 &TREE_OPERAND (cond, 1));
427 /* If one operand was in the operand cache, but the other is
428 not, because it is a constant, this is a case that the
429 internal updating code of swap_tree_operands can't handle
431 if (TREE_CODE_CLASS (TREE_CODE (op0))
432 != TREE_CODE_CLASS (TREE_CODE (op1)))
433 update_stmt (condstmt);
438 /* Initialize local stacks for this optimizer and record equivalences
439 upon entry to BB. Equivalences can come from the edge traversed to
440 reach BB or they may come from PHI nodes at the start of BB. */
443 dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
446 if (dump_file && (dump_flags & TDF_DETAILS))
447 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
449 /* Push a marker on the stacks of local information so that we know how
450 far to unwind when we finalize this block. */
451 VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
452 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
454 record_equivalences_from_incoming_edge (bb);
456 /* PHI nodes can create equivalences too. */
457 record_equivalences_from_phis (bb);
460 /* Given an expression EXPR (a relational expression or a statement),
461 initialize the hash table element pointed to by ELEMENT. */
464 initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
466 /* Hash table elements may be based on conditional expressions or statements.
468 For the former case, we have no annotation and we want to hash the
469 conditional expression. In the latter case we have an annotation and
470 we want to record the expression the statement evaluates. */
471 if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)
473 element->stmt = NULL;
476 else if (TREE_CODE (expr) == COND_EXPR)
478 element->stmt = expr;
479 element->rhs = COND_EXPR_COND (expr);
481 else if (TREE_CODE (expr) == SWITCH_EXPR)
483 element->stmt = expr;
484 element->rhs = SWITCH_COND (expr);
486 else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
488 element->stmt = expr;
489 element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);
491 else if (TREE_CODE (expr) == GOTO_EXPR)
493 element->stmt = expr;
494 element->rhs = GOTO_DESTINATION (expr);
498 element->stmt = expr;
499 element->rhs = TREE_OPERAND (expr, 1);
503 element->hash = avail_expr_hash (element);
506 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
507 LIMIT entries left in LOCALs. */
510 remove_local_expressions_from_table (void)
512 /* Remove all the expressions made available in this block. */
513 while (VEC_length (tree, avail_exprs_stack) > 0)
515 struct expr_hash_elt element;
516 tree expr = VEC_pop (tree, avail_exprs_stack);
518 if (expr == NULL_TREE)
521 initialize_hash_element (expr, NULL, &element);
522 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
526 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
527 CONST_AND_COPIES to its original state, stopping when we hit a
531 restore_vars_to_original_value (void)
533 while (VEC_length (tree, const_and_copies_stack) > 0)
535 tree prev_value, dest;
537 dest = VEC_pop (tree, const_and_copies_stack);
542 prev_value = VEC_pop (tree, const_and_copies_stack);
543 SSA_NAME_VALUE (dest) = prev_value;
547 /* A trivial wrapper so that we can present the generic jump
548 threading code with a simple API for simplifying statements. */
550 simplify_stmt_for_jump_threading (tree stmt)
552 return lookup_avail_expr (stmt, false);
555 /* Wrapper for common code to attempt to thread an edge. For example,
556 it handles lazily building the dummy condition and the bookkeeping
557 when jump threading is successful. */
560 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
562 /* If we don't already have a dummy condition, build it now. */
563 if (! walk_data->global_data)
565 tree dummy_cond = build2 (NE_EXPR, boolean_type_node,
566 integer_zero_node, integer_zero_node);
567 dummy_cond = build3 (COND_EXPR, void_type_node, dummy_cond, NULL, NULL);
568 walk_data->global_data = dummy_cond;
571 thread_across_edge (walk_data->global_data, e, false,
572 &const_and_copies_stack,
573 simplify_stmt_for_jump_threading);
576 /* We have finished processing the dominator children of BB, perform
577 any finalization actions in preparation for leaving this node in
578 the dominator tree. */
581 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
586 /* If we have an outgoing edge to a block with multiple incoming and
587 outgoing edges, then we may be able to thread the edge. ie, we
588 may be able to statically determine which of the outgoing edges
589 will be traversed when the incoming edge from BB is traversed. */
590 if (single_succ_p (bb)
591 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
592 && potentially_threadable_block (single_succ (bb)))
594 dom_thread_across_edge (walk_data, single_succ_edge (bb));
596 else if ((last = last_stmt (bb))
597 && TREE_CODE (last) == COND_EXPR
598 && (COMPARISON_CLASS_P (COND_EXPR_COND (last))
599 || TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
600 && EDGE_COUNT (bb->succs) == 2
601 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
602 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
604 edge true_edge, false_edge;
606 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
608 /* Only try to thread the edge if it reaches a target block with
609 more than one predecessor and more than one successor. */
610 if (potentially_threadable_block (true_edge->dest))
612 struct edge_info *edge_info;
615 /* Push a marker onto the available expression stack so that we
616 unwind any expressions related to the TRUE arm before processing
617 the false arm below. */
618 VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
619 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
621 edge_info = (struct edge_info *) true_edge->aux;
623 /* If we have info associated with this edge, record it into
624 our equivalency tables. */
627 tree *cond_equivalences = edge_info->cond_equivalences;
628 tree lhs = edge_info->lhs;
629 tree rhs = edge_info->rhs;
631 /* If we have a simple NAME = VALUE equivalency record it. */
632 if (lhs && TREE_CODE (lhs) == SSA_NAME)
633 record_const_or_copy (lhs, rhs);
635 /* If we have 0 = COND or 1 = COND equivalences, record them
636 into our expression hash tables. */
637 if (cond_equivalences)
638 for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
640 tree expr = cond_equivalences[i];
641 tree value = cond_equivalences[i + 1];
643 record_cond (expr, value);
647 dom_thread_across_edge (walk_data, true_edge);
649 /* And restore the various tables to their state before
650 we threaded this edge. */
651 remove_local_expressions_from_table ();
654 /* Similarly for the ELSE arm. */
655 if (potentially_threadable_block (false_edge->dest))
657 struct edge_info *edge_info;
660 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
661 edge_info = (struct edge_info *) false_edge->aux;
663 /* If we have info associated with this edge, record it into
664 our equivalency tables. */
667 tree *cond_equivalences = edge_info->cond_equivalences;
668 tree lhs = edge_info->lhs;
669 tree rhs = edge_info->rhs;
671 /* If we have a simple NAME = VALUE equivalency record it. */
672 if (lhs && TREE_CODE (lhs) == SSA_NAME)
673 record_const_or_copy (lhs, rhs);
675 /* If we have 0 = COND or 1 = COND equivalences, record them
676 into our expression hash tables. */
677 if (cond_equivalences)
678 for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
680 tree expr = cond_equivalences[i];
681 tree value = cond_equivalences[i + 1];
683 record_cond (expr, value);
687 /* Now thread the edge. */
688 dom_thread_across_edge (walk_data, false_edge);
690 /* No need to remove local expressions from our tables
691 or restore vars to their original value as that will
692 be done immediately below. */
696 remove_local_expressions_from_table ();
697 restore_vars_to_original_value ();
699 /* If we queued any statements to rescan in this block, then
700 go ahead and rescan them now. */
701 while (VEC_length (tree, stmts_to_rescan) > 0)
703 tree stmt = VEC_last (tree, stmts_to_rescan);
704 basic_block stmt_bb = bb_for_stmt (stmt);
709 VEC_pop (tree, stmts_to_rescan);
710 mark_new_vars_to_rename (stmt);
714 /* PHI nodes can create equivalences too.
716 Ignoring any alternatives which are the same as the result, if
717 all the alternatives are equal, then the PHI node creates an
721 record_equivalences_from_phis (basic_block bb)
725 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
727 tree lhs = PHI_RESULT (phi);
731 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
733 tree t = PHI_ARG_DEF (phi, i);
735 /* Ignore alternatives which are the same as our LHS. Since
736 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
737 can simply compare pointers. */
741 /* If we have not processed an alternative yet, then set
742 RHS to this alternative. */
745 /* If we have processed an alternative (stored in RHS), then
746 see if it is equal to this one. If it isn't, then stop
748 else if (! operand_equal_for_phi_arg_p (rhs, t))
752 /* If we had no interesting alternatives, then all the RHS alternatives
753 must have been the same as LHS. */
757 /* If we managed to iterate through each PHI alternative without
758 breaking out of the loop, then we have a PHI which may create
759 a useful equivalence. We do not need to record unwind data for
760 this, since this is a true assignment and not an equivalence
761 inferred from a comparison. All uses of this ssa name are dominated
762 by this assignment, so unwinding just costs time and space. */
763 if (i == PHI_NUM_ARGS (phi)
764 && may_propagate_copy (lhs, rhs))
765 SSA_NAME_VALUE (lhs) = rhs;
769 /* Ignoring loop backedges, if BB has precisely one incoming edge then
770 return that edge. Otherwise return NULL. */
772 single_incoming_edge_ignoring_loop_edges (basic_block bb)
778 FOR_EACH_EDGE (e, ei, bb->preds)
780 /* A loop back edge can be identified by the destination of
781 the edge dominating the source of the edge. */
782 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
785 /* If we have already seen a non-loop edge, then we must have
786 multiple incoming non-loop edges and thus we return NULL. */
790 /* This is the first non-loop incoming edge we have found. Record
798 /* Record any equivalences created by the incoming edge to BB. If BB
799 has more than one incoming edge, then no equivalence is created. */
802 record_equivalences_from_incoming_edge (basic_block bb)
806 struct edge_info *edge_info;
808 /* If our parent block ended with a control statement, then we may be
809 able to record some equivalences based on which outgoing edge from
810 the parent was followed. */
811 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
813 e = single_incoming_edge_ignoring_loop_edges (bb);
815 /* If we had a single incoming edge from our parent block, then enter
816 any data associated with the edge into our tables. */
817 if (e && e->src == parent)
821 edge_info = (struct edge_info *) e->aux;
825 tree lhs = edge_info->lhs;
826 tree rhs = edge_info->rhs;
827 tree *cond_equivalences = edge_info->cond_equivalences;
830 record_equality (lhs, rhs);
832 if (cond_equivalences)
834 for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
836 tree expr = cond_equivalences[i];
837 tree value = cond_equivalences[i + 1];
839 record_cond (expr, value);
846 /* Dump SSA statistics on FILE. */
849 dump_dominator_optimization_stats (FILE *file)
853 fprintf (file, "Total number of statements: %6ld\n\n",
854 opt_stats.num_stmts);
855 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
856 opt_stats.num_exprs_considered);
858 n_exprs = opt_stats.num_exprs_considered;
862 fprintf (file, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
863 opt_stats.num_re, PERCENT (opt_stats.num_re,
865 fprintf (file, " Constants propagated: %6ld\n",
866 opt_stats.num_const_prop);
867 fprintf (file, " Copies propagated: %6ld\n",
868 opt_stats.num_copy_prop);
870 fprintf (file, "\nHash table statistics:\n");
872 fprintf (file, " avail_exprs: ");
873 htab_statistics (file, avail_exprs);
877 /* Dump SSA statistics on stderr. */
880 debug_dominator_optimization_stats (void)
882 dump_dominator_optimization_stats (stderr);
886 /* Dump statistics for the hash table HTAB. */
889 htab_statistics (FILE *file, htab_t htab)
891 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
892 (long) htab_size (htab),
893 (long) htab_elements (htab),
894 htab_collisions (htab));
897 /* Enter a statement into the true/false expression hash table indicating
898 that the condition COND has the value VALUE. */
901 record_cond (tree cond, tree value)
903 struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
906 initialize_hash_element (cond, value, element);
908 slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
909 element->hash, INSERT);
912 *slot = (void *) element;
913 VEC_safe_push (tree, heap, avail_exprs_stack, cond);
919 /* Build a new conditional using NEW_CODE, OP0 and OP1 and store
920 the new conditional into *p, then store a boolean_true_node
924 build_and_record_new_cond (enum tree_code new_code, tree op0, tree op1, tree *p)
926 *p = build2 (new_code, boolean_type_node, op0, op1);
928 *p = boolean_true_node;
931 /* Record that COND is true and INVERTED is false into the edge information
932 structure. Also record that any conditions dominated by COND are true
935 For example, if a < b is true, then a <= b must also be true. */
938 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
942 if (!COMPARISON_CLASS_P (cond))
945 op0 = TREE_OPERAND (cond, 0);
946 op1 = TREE_OPERAND (cond, 1);
948 switch (TREE_CODE (cond))
952 edge_info->max_cond_equivalences = 12;
953 edge_info->cond_equivalences = XNEWVEC (tree, 12);
954 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
955 ? LE_EXPR : GE_EXPR),
956 op0, op1, &edge_info->cond_equivalences[4]);
957 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
958 &edge_info->cond_equivalences[6]);
959 build_and_record_new_cond (NE_EXPR, op0, op1,
960 &edge_info->cond_equivalences[8]);
961 build_and_record_new_cond (LTGT_EXPR, op0, op1,
962 &edge_info->cond_equivalences[10]);
967 edge_info->max_cond_equivalences = 6;
968 edge_info->cond_equivalences = XNEWVEC (tree, 6);
969 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
970 &edge_info->cond_equivalences[4]);
974 edge_info->max_cond_equivalences = 10;
975 edge_info->cond_equivalences = XNEWVEC (tree, 10);
976 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
977 &edge_info->cond_equivalences[4]);
978 build_and_record_new_cond (LE_EXPR, op0, op1,
979 &edge_info->cond_equivalences[6]);
980 build_and_record_new_cond (GE_EXPR, op0, op1,
981 &edge_info->cond_equivalences[8]);
985 edge_info->max_cond_equivalences = 16;
986 edge_info->cond_equivalences = XNEWVEC (tree, 16);
987 build_and_record_new_cond (NE_EXPR, op0, op1,
988 &edge_info->cond_equivalences[4]);
989 build_and_record_new_cond (UNLE_EXPR, op0, op1,
990 &edge_info->cond_equivalences[6]);
991 build_and_record_new_cond (UNGE_EXPR, op0, op1,
992 &edge_info->cond_equivalences[8]);
993 build_and_record_new_cond (UNEQ_EXPR, op0, op1,
994 &edge_info->cond_equivalences[10]);
995 build_and_record_new_cond (UNLT_EXPR, op0, op1,
996 &edge_info->cond_equivalences[12]);
997 build_and_record_new_cond (UNGT_EXPR, op0, op1,
998 &edge_info->cond_equivalences[14]);
1003 edge_info->max_cond_equivalences = 8;
1004 edge_info->cond_equivalences = XNEWVEC (tree, 8);
1005 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1006 ? UNLE_EXPR : UNGE_EXPR),
1007 op0, op1, &edge_info->cond_equivalences[4]);
1008 build_and_record_new_cond (NE_EXPR, op0, op1,
1009 &edge_info->cond_equivalences[6]);
1013 edge_info->max_cond_equivalences = 8;
1014 edge_info->cond_equivalences = XNEWVEC (tree, 8);
1015 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1016 &edge_info->cond_equivalences[4]);
1017 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1018 &edge_info->cond_equivalences[6]);
1022 edge_info->max_cond_equivalences = 8;
1023 edge_info->cond_equivalences = XNEWVEC (tree, 8);
1024 build_and_record_new_cond (NE_EXPR, op0, op1,
1025 &edge_info->cond_equivalences[4]);
1026 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1027 &edge_info->cond_equivalences[6]);
1031 edge_info->max_cond_equivalences = 4;
1032 edge_info->cond_equivalences = XNEWVEC (tree, 4);
1036 /* Now store the original true and false conditions into the first
1038 edge_info->cond_equivalences[0] = cond;
1039 edge_info->cond_equivalences[1] = boolean_true_node;
1040 edge_info->cond_equivalences[2] = inverted;
1041 edge_info->cond_equivalences[3] = boolean_false_node;
1044 /* A helper function for record_const_or_copy and record_equality.
1045 Do the work of recording the value and undo info. */
1048 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1050 SSA_NAME_VALUE (x) = y;
1052 VEC_reserve (tree, heap, const_and_copies_stack, 2);
1053 VEC_quick_push (tree, const_and_copies_stack, prev_x);
1054 VEC_quick_push (tree, const_and_copies_stack, x);
1058 /* Return the loop depth of the basic block of the defining statement of X.
1059 This number should not be treated as absolutely correct because the loop
1060 information may not be completely up-to-date when dom runs. However, it
1061 will be relatively correct, and as more passes are taught to keep loop info
1062 up to date, the result will become more and more accurate. */
1065 loop_depth_of_name (tree x)
1070 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1071 if (TREE_CODE (x) != SSA_NAME)
1074 /* Otherwise return the loop depth of the defining statement's bb.
1075 Note that there may not actually be a bb for this statement, if the
1076 ssa_name is live on entry. */
1077 defstmt = SSA_NAME_DEF_STMT (x);
1078 defbb = bb_for_stmt (defstmt);
1082 return defbb->loop_depth;
1086 /* Record that X is equal to Y in const_and_copies. Record undo
1087 information in the block-local vector. */
1090 record_const_or_copy (tree x, tree y)
1092 tree prev_x = SSA_NAME_VALUE (x);
1094 if (TREE_CODE (y) == SSA_NAME)
1096 tree tmp = SSA_NAME_VALUE (y);
1101 record_const_or_copy_1 (x, y, prev_x);
1104 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1105 This constrains the cases in which we may treat this as assignment. */
1108 record_equality (tree x, tree y)
1110 tree prev_x = NULL, prev_y = NULL;
1112 if (TREE_CODE (x) == SSA_NAME)
1113 prev_x = SSA_NAME_VALUE (x);
1114 if (TREE_CODE (y) == SSA_NAME)
1115 prev_y = SSA_NAME_VALUE (y);
1117 /* If one of the previous values is invariant, or invariant in more loops
1118 (by depth), then use that.
1119 Otherwise it doesn't matter which value we choose, just so
1120 long as we canonicalize on one value. */
1121 if (TREE_INVARIANT (y))
1123 else if (TREE_INVARIANT (x) || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
1124 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1125 else if (prev_x && TREE_INVARIANT (prev_x))
1126 x = y, y = prev_x, prev_x = prev_y;
1127 else if (prev_y && TREE_CODE (prev_y) != VALUE_HANDLE)
1130 /* After the swapping, we must have one SSA_NAME. */
1131 if (TREE_CODE (x) != SSA_NAME)
1134 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1135 variable compared against zero. If we're honoring signed zeros,
1136 then we cannot record this value unless we know that the value is
1138 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1139 && (TREE_CODE (y) != REAL_CST
1140 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1143 record_const_or_copy_1 (x, y, prev_x);
1146 /* Returns true when STMT is a simple iv increment. It detects the
1147 following situation:
1149 i_1 = phi (..., i_2)
1150 i_2 = i_1 +/- ... */
1153 simple_iv_increment_p (tree stmt)
1155 tree lhs, rhs, preinc, phi;
1158 if (TREE_CODE (stmt) != MODIFY_EXPR)
1161 lhs = TREE_OPERAND (stmt, 0);
1162 if (TREE_CODE (lhs) != SSA_NAME)
1165 rhs = TREE_OPERAND (stmt, 1);
1167 if (TREE_CODE (rhs) != PLUS_EXPR
1168 && TREE_CODE (rhs) != MINUS_EXPR)
1171 preinc = TREE_OPERAND (rhs, 0);
1172 if (TREE_CODE (preinc) != SSA_NAME)
1175 phi = SSA_NAME_DEF_STMT (preinc);
1176 if (TREE_CODE (phi) != PHI_NODE)
1179 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1180 if (PHI_ARG_DEF (phi, i) == lhs)
1186 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1187 known value for that SSA_NAME (or NULL if no value is known).
1189 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1190 successors of BB. */
1193 cprop_into_successor_phis (basic_block bb)
1198 FOR_EACH_EDGE (e, ei, bb->succs)
1203 /* If this is an abnormal edge, then we do not want to copy propagate
1204 into the PHI alternative associated with this edge. */
1205 if (e->flags & EDGE_ABNORMAL)
1208 phi = phi_nodes (e->dest);
1213 for ( ; phi; phi = PHI_CHAIN (phi))
1216 use_operand_p orig_p;
1219 /* The alternative may be associated with a constant, so verify
1220 it is an SSA_NAME before doing anything with it. */
1221 orig_p = PHI_ARG_DEF_PTR (phi, indx);
1222 orig = USE_FROM_PTR (orig_p);
1223 if (TREE_CODE (orig) != SSA_NAME)
1226 /* If we have *ORIG_P in our constant/copy table, then replace
1227 ORIG_P with its value in our constant/copy table. */
1228 new = SSA_NAME_VALUE (orig);
1231 && (TREE_CODE (new) == SSA_NAME
1232 || is_gimple_min_invariant (new))
1233 && may_propagate_copy (orig, new))
1234 propagate_value (orig_p, new);
1239 /* We have finished optimizing BB, record any information implied by
1240 taking a specific outgoing edge from BB. */
1243 record_edge_info (basic_block bb)
1245 block_stmt_iterator bsi = bsi_last (bb);
1246 struct edge_info *edge_info;
1248 if (! bsi_end_p (bsi))
1250 tree stmt = bsi_stmt (bsi);
1252 if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1254 tree cond = SWITCH_COND (stmt);
1256 if (TREE_CODE (cond) == SSA_NAME)
1258 tree labels = SWITCH_LABELS (stmt);
1259 int i, n_labels = TREE_VEC_LENGTH (labels);
1260 tree *info = XCNEWVEC (tree, last_basic_block);
1264 for (i = 0; i < n_labels; i++)
1266 tree label = TREE_VEC_ELT (labels, i);
1267 basic_block target_bb = label_to_block (CASE_LABEL (label));
1269 if (CASE_HIGH (label)
1270 || !CASE_LOW (label)
1271 || info[target_bb->index])
1272 info[target_bb->index] = error_mark_node;
1274 info[target_bb->index] = label;
1277 FOR_EACH_EDGE (e, ei, bb->succs)
1279 basic_block target_bb = e->dest;
1280 tree node = info[target_bb->index];
1282 if (node != NULL && node != error_mark_node)
1284 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
1285 edge_info = allocate_edge_info (e);
1286 edge_info->lhs = cond;
1294 /* A COND_EXPR may create equivalences too. */
1295 if (stmt && TREE_CODE (stmt) == COND_EXPR)
1297 tree cond = COND_EXPR_COND (stmt);
1301 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1303 /* If the conditional is a single variable 'X', record 'X = 1'
1304 for the true edge and 'X = 0' on the false edge. */
1305 if (SSA_VAR_P (cond))
1307 struct edge_info *edge_info;
1309 edge_info = allocate_edge_info (true_edge);
1310 edge_info->lhs = cond;
1311 edge_info->rhs = constant_boolean_node (1, TREE_TYPE (cond));
1313 edge_info = allocate_edge_info (false_edge);
1314 edge_info->lhs = cond;
1315 edge_info->rhs = constant_boolean_node (0, TREE_TYPE (cond));
1317 /* Equality tests may create one or two equivalences. */
1318 else if (COMPARISON_CLASS_P (cond))
1320 tree op0 = TREE_OPERAND (cond, 0);
1321 tree op1 = TREE_OPERAND (cond, 1);
1323 /* Special case comparing booleans against a constant as we
1324 know the value of OP0 on both arms of the branch. i.e., we
1325 can record an equivalence for OP0 rather than COND. */
1326 if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1327 && TREE_CODE (op0) == SSA_NAME
1328 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
1329 && is_gimple_min_invariant (op1))
1331 if (TREE_CODE (cond) == EQ_EXPR)
1333 edge_info = allocate_edge_info (true_edge);
1334 edge_info->lhs = op0;
1335 edge_info->rhs = (integer_zerop (op1)
1336 ? boolean_false_node
1337 : boolean_true_node);
1339 edge_info = allocate_edge_info (false_edge);
1340 edge_info->lhs = op0;
1341 edge_info->rhs = (integer_zerop (op1)
1343 : boolean_false_node);
1347 edge_info = allocate_edge_info (true_edge);
1348 edge_info->lhs = op0;
1349 edge_info->rhs = (integer_zerop (op1)
1351 : boolean_false_node);
1353 edge_info = allocate_edge_info (false_edge);
1354 edge_info->lhs = op0;
1355 edge_info->rhs = (integer_zerop (op1)
1356 ? boolean_false_node
1357 : boolean_true_node);
1361 else if (is_gimple_min_invariant (op0)
1362 && (TREE_CODE (op1) == SSA_NAME
1363 || is_gimple_min_invariant (op1)))
1365 tree inverted = invert_truthvalue (cond);
1366 struct edge_info *edge_info;
1368 edge_info = allocate_edge_info (true_edge);
1369 record_conditions (edge_info, cond, inverted);
1371 if (TREE_CODE (cond) == EQ_EXPR)
1373 edge_info->lhs = op1;
1374 edge_info->rhs = op0;
1377 edge_info = allocate_edge_info (false_edge);
1378 record_conditions (edge_info, inverted, cond);
1380 if (TREE_CODE (cond) == NE_EXPR)
1382 edge_info->lhs = op1;
1383 edge_info->rhs = op0;
1387 else if (TREE_CODE (op0) == SSA_NAME
1388 && (is_gimple_min_invariant (op1)
1389 || TREE_CODE (op1) == SSA_NAME))
1391 tree inverted = invert_truthvalue (cond);
1392 struct edge_info *edge_info;
1394 edge_info = allocate_edge_info (true_edge);
1395 record_conditions (edge_info, cond, inverted);
1397 if (TREE_CODE (cond) == EQ_EXPR)
1399 edge_info->lhs = op0;
1400 edge_info->rhs = op1;
1403 edge_info = allocate_edge_info (false_edge);
1404 record_conditions (edge_info, inverted, cond);
1406 if (TREE_CODE (cond) == NE_EXPR)
1408 edge_info->lhs = op0;
1409 edge_info->rhs = op1;
1414 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1419 /* Propagate information from BB to its outgoing edges.
1421 This can include equivalency information implied by control statements
1422 at the end of BB and const/copy propagation into PHIs in BB's
1423 successor blocks. */
1426 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1429 record_edge_info (bb);
1430 cprop_into_successor_phis (bb);
1433 /* Search for redundant computations in STMT. If any are found, then
1434 replace them with the variable holding the result of the computation.
1436 If safe, record this expression into the available expression hash
1440 eliminate_redundant_computations (tree stmt)
1442 tree *expr_p, def = NULL_TREE;
1445 bool retval = false;
1446 bool modify_expr_p = false;
1448 if (TREE_CODE (stmt) == MODIFY_EXPR)
1449 def = TREE_OPERAND (stmt, 0);
1451 /* Certain expressions on the RHS can be optimized away, but can not
1452 themselves be entered into the hash tables. */
1454 || TREE_CODE (def) != SSA_NAME
1455 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1456 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF)
1457 /* Do not record equivalences for increments of ivs. This would create
1458 overlapping live ranges for a very questionable gain. */
1459 || simple_iv_increment_p (stmt))
1462 /* Check if the expression has been computed before. */
1463 cached_lhs = lookup_avail_expr (stmt, insert);
1465 opt_stats.num_exprs_considered++;
1467 /* Get a pointer to the expression we are trying to optimize. */
1468 if (TREE_CODE (stmt) == COND_EXPR)
1469 expr_p = &COND_EXPR_COND (stmt);
1470 else if (TREE_CODE (stmt) == SWITCH_EXPR)
1471 expr_p = &SWITCH_COND (stmt);
1472 else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
1474 expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
1475 modify_expr_p = true;
1479 expr_p = &TREE_OPERAND (stmt, 1);
1480 modify_expr_p = true;
1483 /* It is safe to ignore types here since we have already done
1484 type checking in the hashing and equality routines. In fact
1485 type checking here merely gets in the way of constant
1486 propagation. Also, make sure that it is safe to propagate
1487 CACHED_LHS into *EXPR_P. */
1489 && ((TREE_CODE (cached_lhs) != SSA_NAME
1491 || tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
1492 TREE_TYPE (cached_lhs))))
1493 || may_propagate_copy (*expr_p, cached_lhs)))
1495 if (dump_file && (dump_flags & TDF_DETAILS))
1497 fprintf (dump_file, " Replaced redundant expr '");
1498 print_generic_expr (dump_file, *expr_p, dump_flags);
1499 fprintf (dump_file, "' with '");
1500 print_generic_expr (dump_file, cached_lhs, dump_flags);
1501 fprintf (dump_file, "'\n");
1506 #if defined ENABLE_CHECKING
1507 gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
1508 || is_gimple_min_invariant (cached_lhs));
1511 if (TREE_CODE (cached_lhs) == ADDR_EXPR
1512 || (POINTER_TYPE_P (TREE_TYPE (*expr_p))
1513 && is_gimple_min_invariant (cached_lhs)))
1517 && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p),
1518 TREE_TYPE (cached_lhs)))
1519 cached_lhs = fold_convert (TREE_TYPE (*expr_p), cached_lhs);
1521 propagate_tree_value (expr_p, cached_lhs);
1522 mark_stmt_modified (stmt);
1527 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
1528 the available expressions table or the const_and_copies table.
1529 Detect and record those equivalences. */
1532 record_equivalences_from_stmt (tree stmt,
1536 tree lhs = TREE_OPERAND (stmt, 0);
1537 enum tree_code lhs_code = TREE_CODE (lhs);
1539 if (lhs_code == SSA_NAME)
1541 tree rhs = TREE_OPERAND (stmt, 1);
1543 /* Strip away any useless type conversions. */
1544 STRIP_USELESS_TYPE_CONVERSION (rhs);
1546 /* If the RHS of the assignment is a constant or another variable that
1547 may be propagated, register it in the CONST_AND_COPIES table. We
1548 do not need to record unwind data for this, since this is a true
1549 assignment and not an equivalence inferred from a comparison. All
1550 uses of this ssa name are dominated by this assignment, so unwinding
1551 just costs time and space. */
1553 && (TREE_CODE (rhs) == SSA_NAME
1554 || is_gimple_min_invariant (rhs)))
1555 SSA_NAME_VALUE (lhs) = rhs;
1558 /* A memory store, even an aliased store, creates a useful
1559 equivalence. By exchanging the LHS and RHS, creating suitable
1560 vops and recording the result in the available expression table,
1561 we may be able to expose more redundant loads. */
1562 if (!ann->has_volatile_ops
1563 && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
1564 || is_gimple_min_invariant (TREE_OPERAND (stmt, 1)))
1565 && !is_gimple_reg (lhs))
1567 tree rhs = TREE_OPERAND (stmt, 1);
1570 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
1571 is a constant, we need to adjust the constant to fit into the
1572 type of the LHS. If the LHS is a bitfield and the RHS is not
1573 a constant, then we can not record any equivalences for this
1574 statement since we would need to represent the widening or
1575 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
1576 and should not be necessary if GCC represented bitfields
1578 if (lhs_code == COMPONENT_REF
1579 && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
1581 if (TREE_CONSTANT (rhs))
1582 rhs = widen_bitfield (rhs, TREE_OPERAND (lhs, 1), lhs);
1586 /* If the value overflowed, then we can not use this equivalence. */
1587 if (rhs && ! is_gimple_min_invariant (rhs))
1593 /* Build a new statement with the RHS and LHS exchanged. */
1594 new = build2 (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
1596 create_ssa_artficial_load_stmt (new, stmt);
1598 /* Finally enter the statement into the available expression
1600 lookup_avail_expr (new, true);
1605 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1606 CONST_AND_COPIES. */
1609 cprop_operand (tree stmt, use_operand_p op_p)
1611 bool may_have_exposed_new_symbols = false;
1613 tree op = USE_FROM_PTR (op_p);
1615 /* If the operand has a known constant value or it is known to be a
1616 copy of some other variable, use the value or copy stored in
1617 CONST_AND_COPIES. */
1618 val = SSA_NAME_VALUE (op);
1619 if (val && val != op && TREE_CODE (val) != VALUE_HANDLE)
1621 tree op_type, val_type;
1623 /* Do not change the base variable in the virtual operand
1624 tables. That would make it impossible to reconstruct
1625 the renamed virtual operand if we later modify this
1626 statement. Also only allow the new value to be an SSA_NAME
1627 for propagation into virtual operands. */
1628 if (!is_gimple_reg (op)
1629 && (TREE_CODE (val) != SSA_NAME
1630 || is_gimple_reg (val)
1631 || get_virtual_var (val) != get_virtual_var (op)))
1634 /* Do not replace hard register operands in asm statements. */
1635 if (TREE_CODE (stmt) == ASM_EXPR
1636 && !may_propagate_copy_into_asm (op))
1639 /* Get the toplevel type of each operand. */
1640 op_type = TREE_TYPE (op);
1641 val_type = TREE_TYPE (val);
1643 /* While both types are pointers, get the type of the object
1645 while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
1647 op_type = TREE_TYPE (op_type);
1648 val_type = TREE_TYPE (val_type);
1651 /* Make sure underlying types match before propagating a constant by
1652 converting the constant to the proper type. Note that convert may
1653 return a non-gimple expression, in which case we ignore this
1654 propagation opportunity. */
1655 if (TREE_CODE (val) != SSA_NAME)
1657 if (!lang_hooks.types_compatible_p (op_type, val_type))
1659 val = fold_convert (TREE_TYPE (op), val);
1660 if (!is_gimple_min_invariant (val))
1665 /* Certain operands are not allowed to be copy propagated due
1666 to their interaction with exception handling and some GCC
1668 else if (!may_propagate_copy (op, val))
1671 /* Do not propagate copies if the propagated value is at a deeper loop
1672 depth than the propagatee. Otherwise, this may move loop variant
1673 variables outside of their loops and prevent coalescing
1674 opportunities. If the value was loop invariant, it will be hoisted
1675 by LICM and exposed for copy propagation. */
1676 if (loop_depth_of_name (val) > loop_depth_of_name (op))
1680 if (dump_file && (dump_flags & TDF_DETAILS))
1682 fprintf (dump_file, " Replaced '");
1683 print_generic_expr (dump_file, op, dump_flags);
1684 fprintf (dump_file, "' with %s '",
1685 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
1686 print_generic_expr (dump_file, val, dump_flags);
1687 fprintf (dump_file, "'\n");
1690 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
1691 that we may have exposed a new symbol for SSA renaming. */
1692 if (TREE_CODE (val) == ADDR_EXPR
1693 || (POINTER_TYPE_P (TREE_TYPE (op))
1694 && is_gimple_min_invariant (val)))
1695 may_have_exposed_new_symbols = true;
1697 if (TREE_CODE (val) != SSA_NAME)
1698 opt_stats.num_const_prop++;
1700 opt_stats.num_copy_prop++;
1702 propagate_value (op_p, val);
1704 /* And note that we modified this statement. This is now
1705 safe, even if we changed virtual operands since we will
1706 rescan the statement and rewrite its operands again. */
1707 mark_stmt_modified (stmt);
1709 return may_have_exposed_new_symbols;
1712 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1713 known value for that SSA_NAME (or NULL if no value is known).
1715 Propagate values from CONST_AND_COPIES into the uses, vuses and
1716 v_may_def_ops of STMT. */
1719 cprop_into_stmt (tree stmt)
1721 bool may_have_exposed_new_symbols = false;
1725 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
1727 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
1728 may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
1731 return may_have_exposed_new_symbols;
1735 /* Optimize the statement pointed to by iterator SI.
1737 We try to perform some simplistic global redundancy elimination and
1738 constant propagation:
1740 1- To detect global redundancy, we keep track of expressions that have
1741 been computed in this block and its dominators. If we find that the
1742 same expression is computed more than once, we eliminate repeated
1743 computations by using the target of the first one.
1745 2- Constant values and copy assignments. This is used to do very
1746 simplistic constant and copy propagation. When a constant or copy
1747 assignment is found, we map the value on the RHS of the assignment to
1748 the variable in the LHS in the CONST_AND_COPIES table. */
1751 optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1752 basic_block bb, block_stmt_iterator si)
1755 tree stmt, old_stmt;
1756 bool may_optimize_p;
1757 bool may_have_exposed_new_symbols = false;
1759 old_stmt = stmt = bsi_stmt (si);
1761 if (TREE_CODE (stmt) == COND_EXPR)
1762 canonicalize_comparison (stmt);
1764 update_stmt_if_modified (stmt);
1765 ann = stmt_ann (stmt);
1766 opt_stats.num_stmts++;
1767 may_have_exposed_new_symbols = false;
1769 if (dump_file && (dump_flags & TDF_DETAILS))
1771 fprintf (dump_file, "Optimizing statement ");
1772 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1775 /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
1776 may_have_exposed_new_symbols = cprop_into_stmt (stmt);
1778 /* If the statement has been modified with constant replacements,
1779 fold its RHS before checking for redundant computations. */
1784 /* Try to fold the statement making sure that STMT is kept
1786 if (fold_stmt (bsi_stmt_ptr (si)))
1788 stmt = bsi_stmt (si);
1789 ann = stmt_ann (stmt);
1791 if (dump_file && (dump_flags & TDF_DETAILS))
1793 fprintf (dump_file, " Folded to: ");
1794 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1798 rhs = get_rhs (stmt);
1799 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
1800 recompute_tree_invariant_for_addr_expr (rhs);
1802 /* Constant/copy propagation above may change the set of
1803 virtual operands associated with this statement. Folding
1804 may remove the need for some virtual operands.
1806 Indicate we will need to rescan and rewrite the statement. */
1807 may_have_exposed_new_symbols = true;
1810 /* Check for redundant computations. Do this optimization only
1811 for assignments that have no volatile ops and conditionals. */
1812 may_optimize_p = (!ann->has_volatile_ops
1813 && ((TREE_CODE (stmt) == RETURN_EXPR
1814 && TREE_OPERAND (stmt, 0)
1815 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR
1816 && ! (TREE_SIDE_EFFECTS
1817 (TREE_OPERAND (TREE_OPERAND (stmt, 0), 1))))
1818 || (TREE_CODE (stmt) == MODIFY_EXPR
1819 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1)))
1820 || TREE_CODE (stmt) == COND_EXPR
1821 || TREE_CODE (stmt) == SWITCH_EXPR));
1824 may_have_exposed_new_symbols |= eliminate_redundant_computations (stmt);
1826 /* Record any additional equivalences created by this statement. */
1827 if (TREE_CODE (stmt) == MODIFY_EXPR)
1828 record_equivalences_from_stmt (stmt,
1832 /* If STMT is a COND_EXPR and it was modified, then we may know
1833 where it goes. If that is the case, then mark the CFG as altered.
1835 This will cause us to later call remove_unreachable_blocks and
1836 cleanup_tree_cfg when it is safe to do so. It is not safe to
1837 clean things up here since removal of edges and such can trigger
1838 the removal of PHI nodes, which in turn can release SSA_NAMEs to
1841 That's all fine and good, except that once SSA_NAMEs are released
1842 to the manager, we must not call create_ssa_name until all references
1843 to released SSA_NAMEs have been eliminated.
1845 All references to the deleted SSA_NAMEs can not be eliminated until
1846 we remove unreachable blocks.
1848 We can not remove unreachable blocks until after we have completed
1849 any queued jump threading.
1851 We can not complete any queued jump threads until we have taken
1852 appropriate variables out of SSA form. Taking variables out of
1853 SSA form can call create_ssa_name and thus we lose.
1855 Ultimately I suspect we're going to need to change the interface
1856 into the SSA_NAME manager. */
1862 if (TREE_CODE (stmt) == COND_EXPR)
1863 val = COND_EXPR_COND (stmt);
1864 else if (TREE_CODE (stmt) == SWITCH_EXPR)
1865 val = SWITCH_COND (stmt);
1867 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
1870 /* If we simplified a statement in such a way as to be shown that it
1871 cannot trap, update the eh information and the cfg to match. */
1872 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
1874 bitmap_set_bit (need_eh_cleanup, bb->index);
1875 if (dump_file && (dump_flags & TDF_DETAILS))
1876 fprintf (dump_file, " Flagged to clear EH edges.\n");
1880 if (may_have_exposed_new_symbols)
1881 VEC_safe_push (tree, heap, stmts_to_rescan, bsi_stmt (si));
1884 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
1885 found, return its LHS. Otherwise insert STMT in the table and return
1888 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
1889 is also added to the stack pointed to by BLOCK_AVAIL_EXPRS_P, so that they
1890 can be removed when we finish processing this block and its children.
1892 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
1893 contains no CALL_EXPR on its RHS and makes no volatile nor
1894 aliased references. */
1897 lookup_avail_expr (tree stmt, bool insert)
1902 struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
1904 lhs = TREE_CODE (stmt) == MODIFY_EXPR ? TREE_OPERAND (stmt, 0) : NULL;
1906 initialize_hash_element (stmt, lhs, element);
1908 /* Don't bother remembering constant assignments and copy operations.
1909 Constants and copy operations are handled by the constant/copy propagator
1910 in optimize_stmt. */
1911 if (TREE_CODE (element->rhs) == SSA_NAME
1912 || is_gimple_min_invariant (element->rhs))
1918 /* Finally try to find the expression in the main expression hash table. */
1919 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
1920 (insert ? INSERT : NO_INSERT));
1929 *slot = (void *) element;
1930 VEC_safe_push (tree, heap, avail_exprs_stack,
1931 stmt ? stmt : element->rhs);
1935 /* Extract the LHS of the assignment so that it can be used as the current
1936 definition of another variable. */
1937 lhs = ((struct expr_hash_elt *)*slot)->lhs;
1939 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
1940 use the value from the const_and_copies table. */
1941 if (TREE_CODE (lhs) == SSA_NAME)
1943 temp = SSA_NAME_VALUE (lhs);
1944 if (temp && TREE_CODE (temp) != VALUE_HANDLE)
1952 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
1953 MODIFY_EXPR statements. We compute a value number for expressions using
1954 the code of the expression and the SSA numbers of its operands. */
1957 avail_expr_hash (const void *p)
1959 tree stmt = ((struct expr_hash_elt *)p)->stmt;
1960 tree rhs = ((struct expr_hash_elt *)p)->rhs;
1965 /* iterative_hash_expr knows how to deal with any expression and
1966 deals with commutative operators as well, so just use it instead
1967 of duplicating such complexities here. */
1968 val = iterative_hash_expr (rhs, val);
1970 /* If the hash table entry is not associated with a statement, then we
1971 can just hash the expression and not worry about virtual operands
1973 if (!stmt || !stmt_ann (stmt))
1976 /* Add the SSA version numbers of every vuse operand. This is important
1977 because compound variables like arrays are not renamed in the
1978 operands. Rather, the rename is done on the virtual variable
1979 representing all the elements of the array. */
1980 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
1981 val = iterative_hash_expr (vuse, val);
1987 real_avail_expr_hash (const void *p)
1989 return ((const struct expr_hash_elt *)p)->hash;
1993 avail_expr_eq (const void *p1, const void *p2)
1995 tree stmt1 = ((struct expr_hash_elt *)p1)->stmt;
1996 tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;
1997 tree stmt2 = ((struct expr_hash_elt *)p2)->stmt;
1998 tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
2000 /* If they are the same physical expression, return true. */
2001 if (rhs1 == rhs2 && stmt1 == stmt2)
2004 /* If their codes are not equal, then quit now. */
2005 if (TREE_CODE (rhs1) != TREE_CODE (rhs2))
2008 /* In case of a collision, both RHS have to be identical and have the
2009 same VUSE operands. */
2010 if ((TREE_TYPE (rhs1) == TREE_TYPE (rhs2)
2011 || lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2)))
2012 && operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
2014 bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE);
2015 gcc_assert (!ret || ((struct expr_hash_elt *)p1)->hash
2016 == ((struct expr_hash_elt *)p2)->hash);