1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
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 3, 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 COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
31 #include "basic-block.h"
36 #include "diagnostic.h"
38 #include "tree-dump.h"
39 #include "tree-flow.h"
42 #include "tree-pass.h"
43 #include "tree-ssa-propagate.h"
44 #include "langhooks.h"
47 /* This file implements optimizations on the dominator tree. */
50 /* Structure for recording edge equivalences as well as any pending
51 edge redirections during the dominator optimizer.
53 Computing and storing the edge equivalences instead of creating
54 them on-demand can save significant amounts of time, particularly
55 for pathological cases involving switch statements.
57 These structures live for a single iteration of the dominator
58 optimizer in the edge's AUX field. At the end of an iteration we
59 free each of these structures and update the AUX field to point
60 to any requested redirection target (the code for updating the
61 CFG and SSA graph for edge redirection expects redirection edge
62 targets to be in the AUX field for each edge. */
66 /* If this edge creates a simple equivalence, the LHS and RHS of
67 the equivalence will be stored here. */
71 /* Traversing an edge may also indicate one or more particular conditions
72 are true or false. The number of recorded conditions can vary, but
73 can be determined by the condition's code. So we have an array
74 and its maximum index rather than use a varray. */
75 tree *cond_equivalences;
76 unsigned int max_cond_equivalences;
80 /* Hash table with expressions made available during the renaming process.
81 When an assignment of the form X_i = EXPR is found, the statement is
82 stored in this table. If the same expression EXPR is later found on the
83 RHS of another statement, it is replaced with X_i (thus performing
84 global redundancy elimination). Similarly as we pass through conditionals
85 we record the conditional itself as having either a true or false value
87 static htab_t avail_exprs;
89 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
90 expressions it enters into the hash table along with a marker entry
91 (null). When we finish processing the block, we pop off entries and
92 remove the expressions from the global hash table until we hit the
94 static VEC(tree,heap) *avail_exprs_stack;
96 /* Stack of statements we need to rescan during finalization for newly
99 Statement rescanning must occur after the current block's available
100 expressions are removed from AVAIL_EXPRS. Else we may change the
101 hash code for an expression and be unable to find/remove it from
103 typedef tree *tree_p;
105 DEF_VEC_ALLOC_P(tree_p,heap);
107 static VEC(tree_p,heap) *stmts_to_rescan;
109 /* Structure for entries in the expression hash table.
111 This requires more memory for the hash table entries, but allows us
112 to avoid creating silly tree nodes and annotations for conditionals,
113 eliminates 2 global hash tables and two block local varrays.
115 It also allows us to reduce the number of hash table lookups we
116 have to perform in lookup_avail_expr and finally it allows us to
117 significantly reduce the number of calls into the hashing routine
122 /* The value (lhs) of this expression. */
125 /* The expression (rhs) we want to record. */
128 /* The stmt pointer if this element corresponds to a statement. */
131 /* The hash value for RHS/ann. */
135 /* Stack of dest,src pairs that need to be restored during finalization.
137 A NULL entry is used to mark the end of pairs which need to be
138 restored during finalization of this block. */
139 static VEC(tree,heap) *const_and_copies_stack;
141 /* Track whether or not we have changed the control flow graph. */
142 static bool cfg_altered;
144 /* Bitmap of blocks that have had EH statements cleaned. We should
145 remove their dead edges eventually. */
146 static bitmap need_eh_cleanup;
148 /* Statistics for dominator optimizations. */
152 long num_exprs_considered;
158 static struct opt_stats_d opt_stats;
166 /* Local functions. */
167 static void optimize_stmt (struct dom_walk_data *,
169 block_stmt_iterator);
170 static tree lookup_avail_expr (tree, bool);
171 static hashval_t avail_expr_hash (const void *);
172 static hashval_t real_avail_expr_hash (const void *);
173 static int avail_expr_eq (const void *, const void *);
174 static void htab_statistics (FILE *, htab_t);
175 static void record_cond (tree, tree);
176 static void record_const_or_copy (tree, tree);
177 static void record_equality (tree, tree);
178 static void record_equivalences_from_phis (basic_block);
179 static void record_equivalences_from_incoming_edge (basic_block);
180 static bool eliminate_redundant_computations (tree);
181 static void record_equivalences_from_stmt (tree, int, stmt_ann_t);
182 static void dom_thread_across_edge (struct dom_walk_data *, edge);
183 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
184 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
185 static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
186 static void remove_local_expressions_from_table (void);
187 static void restore_vars_to_original_value (void);
188 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
191 /* Allocate an EDGE_INFO for edge E and attach it to E.
192 Return the new EDGE_INFO structure. */
194 static struct edge_info *
195 allocate_edge_info (edge e)
197 struct edge_info *edge_info;
199 edge_info = XCNEW (struct edge_info);
205 /* Free all EDGE_INFO structures associated with edges in the CFG.
206 If a particular edge can be threaded, copy the redirection
207 target from the EDGE_INFO structure into the edge's AUX field
208 as required by code to update the CFG and SSA graph for
212 free_all_edge_infos (void)
220 FOR_EACH_EDGE (e, ei, bb->preds)
222 struct edge_info *edge_info = (struct edge_info *) e->aux;
226 if (edge_info->cond_equivalences)
227 free (edge_info->cond_equivalences);
235 /* Jump threading, redundancy elimination and const/copy propagation.
237 This pass may expose new symbols that need to be renamed into SSA. For
238 every new symbol exposed, its corresponding bit will be set in
242 tree_ssa_dominator_optimize (void)
244 struct dom_walk_data walk_data;
247 memset (&opt_stats, 0, sizeof (opt_stats));
249 /* Create our hash tables. */
250 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
251 avail_exprs_stack = VEC_alloc (tree, heap, 20);
252 const_and_copies_stack = VEC_alloc (tree, heap, 20);
253 stmts_to_rescan = VEC_alloc (tree_p, heap, 20);
254 need_eh_cleanup = BITMAP_ALLOC (NULL);
256 /* Setup callbacks for the generic dominator tree walker. */
257 walk_data.walk_stmts_backward = false;
258 walk_data.dom_direction = CDI_DOMINATORS;
259 walk_data.initialize_block_local_data = NULL;
260 walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
261 walk_data.before_dom_children_walk_stmts = optimize_stmt;
262 walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
263 walk_data.after_dom_children_before_stmts = NULL;
264 walk_data.after_dom_children_walk_stmts = NULL;
265 walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
266 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
267 When we attach more stuff we'll need to fill this out with a real
269 walk_data.global_data = NULL;
270 walk_data.block_local_data_size = 0;
271 walk_data.interesting_blocks = NULL;
273 /* Now initialize the dominator walker. */
274 init_walk_dominator_tree (&walk_data);
276 calculate_dominance_info (CDI_DOMINATORS);
279 /* We need to know loop structures in order to avoid destroying them
280 in jump threading. Note that we still can e.g. thread through loop
281 headers to an exit edge, or through loop header to the loop body, assuming
282 that we update the loop info. */
283 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
285 /* We need accurate information regarding back edges in the CFG
286 for jump threading; this may include back edes that are not part of
288 mark_dfs_back_edges ();
290 /* Recursively walk the dominator tree optimizing statements. */
291 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
294 block_stmt_iterator bsi;
298 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
299 update_stmt_if_modified (bsi_stmt (bsi));
303 /* If we exposed any new variables, go ahead and put them into
304 SSA form now, before we handle jump threading. This simplifies
305 interactions between rewriting of _DECL nodes into SSA form
306 and rewriting SSA_NAME nodes into SSA form after block
307 duplication and CFG manipulation. */
308 update_ssa (TODO_update_ssa);
310 free_all_edge_infos ();
312 /* Thread jumps, creating duplicate blocks as needed. */
313 cfg_altered |= thread_through_all_blocks (first_pass_instance);
316 free_dominance_info (CDI_DOMINATORS);
318 /* Removal of statements may make some EH edges dead. Purge
319 such edges from the CFG as needed. */
320 if (!bitmap_empty_p (need_eh_cleanup))
325 /* Jump threading may have created forwarder blocks from blocks
326 needing EH cleanup; the new successor of these blocks, which
327 has inherited from the original block, needs the cleanup. */
328 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
330 basic_block bb = BASIC_BLOCK (i);
331 if (single_succ_p (bb) == 1
332 && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
334 bitmap_clear_bit (need_eh_cleanup, i);
335 bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index);
339 tree_purge_all_dead_eh_edges (need_eh_cleanup);
340 bitmap_zero (need_eh_cleanup);
343 /* Finally, remove everything except invariants in SSA_NAME_VALUE.
345 Long term we will be able to let everything in SSA_NAME_VALUE
346 persist. However, for now, we know this is the safe thing to do. */
347 for (i = 0; i < num_ssa_names; i++)
349 tree name = ssa_name (i);
355 value = SSA_NAME_VALUE (name);
356 if (value && !is_gimple_min_invariant (value))
357 SSA_NAME_VALUE (name) = NULL;
360 /* Debugging dumps. */
361 if (dump_file && (dump_flags & TDF_STATS))
362 dump_dominator_optimization_stats (dump_file);
364 loop_optimizer_finalize ();
366 /* Delete our main hashtable. */
367 htab_delete (avail_exprs);
369 /* And finalize the dominator walker. */
370 fini_walk_dominator_tree (&walk_data);
372 /* Free asserted bitmaps and stacks. */
373 BITMAP_FREE (need_eh_cleanup);
375 VEC_free (tree, heap, avail_exprs_stack);
376 VEC_free (tree, heap, const_and_copies_stack);
377 VEC_free (tree_p, heap, stmts_to_rescan);
382 gate_dominator (void)
384 return flag_tree_dom != 0;
387 struct gimple_opt_pass pass_dominator =
392 gate_dominator, /* gate */
393 tree_ssa_dominator_optimize, /* execute */
396 0, /* static_pass_number */
397 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
398 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
399 0, /* properties_provided */
400 0, /* properties_destroyed */
401 0, /* todo_flags_start */
405 | TODO_verify_ssa /* todo_flags_finish */
410 /* Given a stmt CONDSTMT containing a COND_EXPR, canonicalize the
411 COND_EXPR into a canonical form. */
414 canonicalize_comparison (tree condstmt)
416 tree cond = COND_EXPR_COND (condstmt);
419 enum tree_code code = TREE_CODE (cond);
421 if (!COMPARISON_CLASS_P (cond))
424 op0 = TREE_OPERAND (cond, 0);
425 op1 = TREE_OPERAND (cond, 1);
427 /* If it would be profitable to swap the operands, then do so to
428 canonicalize the statement, enabling better optimization.
430 By placing canonicalization of such expressions here we
431 transparently keep statements in canonical form, even
432 when the statement is modified. */
433 if (tree_swap_operands_p (op0, op1, false))
435 /* For relationals we need to swap the operands
436 and change the code. */
442 TREE_SET_CODE (cond, swap_tree_comparison (code));
443 swap_tree_operands (condstmt,
444 &TREE_OPERAND (cond, 0),
445 &TREE_OPERAND (cond, 1));
446 /* If one operand was in the operand cache, but the other is
447 not, because it is a constant, this is a case that the
448 internal updating code of swap_tree_operands can't handle
450 if (TREE_CODE_CLASS (TREE_CODE (op0))
451 != TREE_CODE_CLASS (TREE_CODE (op1)))
452 update_stmt (condstmt);
457 /* Initialize local stacks for this optimizer and record equivalences
458 upon entry to BB. Equivalences can come from the edge traversed to
459 reach BB or they may come from PHI nodes at the start of BB. */
462 dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
465 if (dump_file && (dump_flags & TDF_DETAILS))
466 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
468 /* Push a marker on the stacks of local information so that we know how
469 far to unwind when we finalize this block. */
470 VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
471 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
473 record_equivalences_from_incoming_edge (bb);
475 /* PHI nodes can create equivalences too. */
476 record_equivalences_from_phis (bb);
479 /* Given an expression EXPR (a relational expression or a statement),
480 initialize the hash table element pointed to by ELEMENT. */
483 initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
485 /* Hash table elements may be based on conditional expressions or statements.
487 For the former case, we have no annotation and we want to hash the
488 conditional expression. In the latter case we have an annotation and
489 we want to record the expression the statement evaluates. */
490 if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)
492 element->stmt = NULL;
495 else if (TREE_CODE (expr) == COND_EXPR)
497 element->stmt = expr;
498 element->rhs = COND_EXPR_COND (expr);
500 else if (TREE_CODE (expr) == SWITCH_EXPR)
502 element->stmt = expr;
503 element->rhs = SWITCH_COND (expr);
505 else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
507 element->stmt = expr;
508 element->rhs = GIMPLE_STMT_OPERAND (TREE_OPERAND (expr, 0), 1);
510 else if (TREE_CODE (expr) == GOTO_EXPR)
512 element->stmt = expr;
513 element->rhs = GOTO_DESTINATION (expr);
517 element->stmt = expr;
518 element->rhs = GENERIC_TREE_OPERAND (expr, 1);
522 element->hash = avail_expr_hash (element);
525 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
526 LIMIT entries left in LOCALs. */
529 remove_local_expressions_from_table (void)
531 /* Remove all the expressions made available in this block. */
532 while (VEC_length (tree, avail_exprs_stack) > 0)
534 struct expr_hash_elt element;
535 tree expr = VEC_pop (tree, avail_exprs_stack);
537 if (expr == NULL_TREE)
540 initialize_hash_element (expr, NULL, &element);
541 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
545 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
546 CONST_AND_COPIES to its original state, stopping when we hit a
550 restore_vars_to_original_value (void)
552 while (VEC_length (tree, const_and_copies_stack) > 0)
554 tree prev_value, dest;
556 dest = VEC_pop (tree, const_and_copies_stack);
561 prev_value = VEC_pop (tree, const_and_copies_stack);
562 SSA_NAME_VALUE (dest) = prev_value;
566 /* A trivial wrapper so that we can present the generic jump
567 threading code with a simple API for simplifying statements. */
569 simplify_stmt_for_jump_threading (tree stmt, tree within_stmt ATTRIBUTE_UNUSED)
571 return lookup_avail_expr (stmt, false);
574 /* Wrapper for common code to attempt to thread an edge. For example,
575 it handles lazily building the dummy condition and the bookkeeping
576 when jump threading is successful. */
579 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
581 /* If we don't already have a dummy condition, build it now. */
582 if (! walk_data->global_data)
584 tree dummy_cond = build2 (NE_EXPR, boolean_type_node,
585 integer_zero_node, integer_zero_node);
586 dummy_cond = build3 (COND_EXPR, void_type_node, dummy_cond, NULL, NULL);
587 walk_data->global_data = dummy_cond;
590 thread_across_edge ((tree) walk_data->global_data, e, false,
591 &const_and_copies_stack,
592 simplify_stmt_for_jump_threading);
595 /* We have finished processing the dominator children of BB, perform
596 any finalization actions in preparation for leaving this node in
597 the dominator tree. */
600 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
605 /* If we have an outgoing edge to a block with multiple incoming and
606 outgoing edges, then we may be able to thread the edge. ie, we
607 may be able to statically determine which of the outgoing edges
608 will be traversed when the incoming edge from BB is traversed. */
609 if (single_succ_p (bb)
610 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
611 && potentially_threadable_block (single_succ (bb)))
613 dom_thread_across_edge (walk_data, single_succ_edge (bb));
615 else if ((last = last_stmt (bb))
616 && TREE_CODE (last) == COND_EXPR
617 && (COMPARISON_CLASS_P (COND_EXPR_COND (last))
618 || TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
619 && EDGE_COUNT (bb->succs) == 2
620 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
621 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
623 edge true_edge, false_edge;
625 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
627 /* Only try to thread the edge if it reaches a target block with
628 more than one predecessor and more than one successor. */
629 if (potentially_threadable_block (true_edge->dest))
631 struct edge_info *edge_info;
634 /* Push a marker onto the available expression stack so that we
635 unwind any expressions related to the TRUE arm before processing
636 the false arm below. */
637 VEC_safe_push (tree, heap, avail_exprs_stack, NULL_TREE);
638 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
640 edge_info = (struct edge_info *) true_edge->aux;
642 /* If we have info associated with this edge, record it into
643 our equivalency tables. */
646 tree *cond_equivalences = edge_info->cond_equivalences;
647 tree lhs = edge_info->lhs;
648 tree rhs = edge_info->rhs;
650 /* If we have a simple NAME = VALUE equivalency record it. */
651 if (lhs && TREE_CODE (lhs) == SSA_NAME)
652 record_const_or_copy (lhs, rhs);
654 /* If we have 0 = COND or 1 = COND equivalences, record them
655 into our expression hash tables. */
656 if (cond_equivalences)
657 for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
659 tree expr = cond_equivalences[i];
660 tree value = cond_equivalences[i + 1];
662 record_cond (expr, value);
666 dom_thread_across_edge (walk_data, true_edge);
668 /* And restore the various tables to their state before
669 we threaded this edge. */
670 remove_local_expressions_from_table ();
673 /* Similarly for the ELSE arm. */
674 if (potentially_threadable_block (false_edge->dest))
676 struct edge_info *edge_info;
679 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
680 edge_info = (struct edge_info *) false_edge->aux;
682 /* If we have info associated with this edge, record it into
683 our equivalency tables. */
686 tree *cond_equivalences = edge_info->cond_equivalences;
687 tree lhs = edge_info->lhs;
688 tree rhs = edge_info->rhs;
690 /* If we have a simple NAME = VALUE equivalency record it. */
691 if (lhs && TREE_CODE (lhs) == SSA_NAME)
692 record_const_or_copy (lhs, rhs);
694 /* If we have 0 = COND or 1 = COND equivalences, record them
695 into our expression hash tables. */
696 if (cond_equivalences)
697 for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
699 tree expr = cond_equivalences[i];
700 tree value = cond_equivalences[i + 1];
702 record_cond (expr, value);
706 /* Now thread the edge. */
707 dom_thread_across_edge (walk_data, false_edge);
709 /* No need to remove local expressions from our tables
710 or restore vars to their original value as that will
711 be done immediately below. */
715 remove_local_expressions_from_table ();
716 restore_vars_to_original_value ();
718 /* If we queued any statements to rescan in this block, then
719 go ahead and rescan them now. */
720 while (VEC_length (tree_p, stmts_to_rescan) > 0)
722 tree *stmt_p = VEC_last (tree_p, stmts_to_rescan);
724 basic_block stmt_bb = bb_for_stmt (stmt);
729 VEC_pop (tree_p, stmts_to_rescan);
730 pop_stmt_changes (stmt_p);
734 /* PHI nodes can create equivalences too.
736 Ignoring any alternatives which are the same as the result, if
737 all the alternatives are equal, then the PHI node creates an
741 record_equivalences_from_phis (basic_block bb)
745 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
747 tree lhs = PHI_RESULT (phi);
751 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
753 tree t = PHI_ARG_DEF (phi, i);
755 /* Ignore alternatives which are the same as our LHS. Since
756 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
757 can simply compare pointers. */
761 /* If we have not processed an alternative yet, then set
762 RHS to this alternative. */
765 /* If we have processed an alternative (stored in RHS), then
766 see if it is equal to this one. If it isn't, then stop
768 else if (! operand_equal_for_phi_arg_p (rhs, t))
772 /* If we had no interesting alternatives, then all the RHS alternatives
773 must have been the same as LHS. */
777 /* If we managed to iterate through each PHI alternative without
778 breaking out of the loop, then we have a PHI which may create
779 a useful equivalence. We do not need to record unwind data for
780 this, since this is a true assignment and not an equivalence
781 inferred from a comparison. All uses of this ssa name are dominated
782 by this assignment, so unwinding just costs time and space. */
783 if (i == PHI_NUM_ARGS (phi)
784 && may_propagate_copy (lhs, rhs))
785 SSA_NAME_VALUE (lhs) = rhs;
789 /* Ignoring loop backedges, if BB has precisely one incoming edge then
790 return that edge. Otherwise return NULL. */
792 single_incoming_edge_ignoring_loop_edges (basic_block bb)
798 FOR_EACH_EDGE (e, ei, bb->preds)
800 /* A loop back edge can be identified by the destination of
801 the edge dominating the source of the edge. */
802 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
805 /* If we have already seen a non-loop edge, then we must have
806 multiple incoming non-loop edges and thus we return NULL. */
810 /* This is the first non-loop incoming edge we have found. Record
818 /* Record any equivalences created by the incoming edge to BB. If BB
819 has more than one incoming edge, then no equivalence is created. */
822 record_equivalences_from_incoming_edge (basic_block bb)
826 struct edge_info *edge_info;
828 /* If our parent block ended with a control statement, then we may be
829 able to record some equivalences based on which outgoing edge from
830 the parent was followed. */
831 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
833 e = single_incoming_edge_ignoring_loop_edges (bb);
835 /* If we had a single incoming edge from our parent block, then enter
836 any data associated with the edge into our tables. */
837 if (e && e->src == parent)
841 edge_info = (struct edge_info *) e->aux;
845 tree lhs = edge_info->lhs;
846 tree rhs = edge_info->rhs;
847 tree *cond_equivalences = edge_info->cond_equivalences;
850 record_equality (lhs, rhs);
852 if (cond_equivalences)
854 for (i = 0; i < edge_info->max_cond_equivalences; i += 2)
856 tree expr = cond_equivalences[i];
857 tree value = cond_equivalences[i + 1];
859 record_cond (expr, value);
866 /* Dump SSA statistics on FILE. */
869 dump_dominator_optimization_stats (FILE *file)
873 fprintf (file, "Total number of statements: %6ld\n\n",
874 opt_stats.num_stmts);
875 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
876 opt_stats.num_exprs_considered);
878 n_exprs = opt_stats.num_exprs_considered;
882 fprintf (file, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
883 opt_stats.num_re, PERCENT (opt_stats.num_re,
885 fprintf (file, " Constants propagated: %6ld\n",
886 opt_stats.num_const_prop);
887 fprintf (file, " Copies propagated: %6ld\n",
888 opt_stats.num_copy_prop);
890 fprintf (file, "\nHash table statistics:\n");
892 fprintf (file, " avail_exprs: ");
893 htab_statistics (file, avail_exprs);
897 /* Dump SSA statistics on stderr. */
900 debug_dominator_optimization_stats (void)
902 dump_dominator_optimization_stats (stderr);
906 /* Dump statistics for the hash table HTAB. */
909 htab_statistics (FILE *file, htab_t htab)
911 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
912 (long) htab_size (htab),
913 (long) htab_elements (htab),
914 htab_collisions (htab));
917 /* Enter a statement into the true/false expression hash table indicating
918 that the condition COND has the value VALUE. */
921 record_cond (tree cond, tree value)
923 struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
926 initialize_hash_element (cond, value, element);
928 slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
929 element->hash, INSERT);
932 *slot = (void *) element;
933 VEC_safe_push (tree, heap, avail_exprs_stack, cond);
939 /* Build a new conditional using NEW_CODE, OP0 and OP1 and store
940 the new conditional into *p, then store a boolean_true_node
944 build_and_record_new_cond (enum tree_code new_code, tree op0, tree op1, tree *p)
946 *p = build2 (new_code, boolean_type_node, op0, op1);
948 *p = boolean_true_node;
951 /* Record that COND is true and INVERTED is false into the edge information
952 structure. Also record that any conditions dominated by COND are true
955 For example, if a < b is true, then a <= b must also be true. */
958 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
962 if (!COMPARISON_CLASS_P (cond))
965 op0 = TREE_OPERAND (cond, 0);
966 op1 = TREE_OPERAND (cond, 1);
968 switch (TREE_CODE (cond))
972 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
974 edge_info->max_cond_equivalences = 12;
975 edge_info->cond_equivalences = XNEWVEC (tree, 12);
976 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
977 &edge_info->cond_equivalences[8]);
978 build_and_record_new_cond (LTGT_EXPR, op0, op1,
979 &edge_info->cond_equivalences[10]);
983 edge_info->max_cond_equivalences = 8;
984 edge_info->cond_equivalences = XNEWVEC (tree, 8);
987 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
988 ? LE_EXPR : GE_EXPR),
989 op0, op1, &edge_info->cond_equivalences[4]);
990 build_and_record_new_cond (NE_EXPR, op0, op1,
991 &edge_info->cond_equivalences[6]);
996 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
998 edge_info->max_cond_equivalences = 6;
999 edge_info->cond_equivalences = XNEWVEC (tree, 6);
1000 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1001 &edge_info->cond_equivalences[4]);
1005 edge_info->max_cond_equivalences = 4;
1006 edge_info->cond_equivalences = XNEWVEC (tree, 4);
1011 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1013 edge_info->max_cond_equivalences = 10;
1014 edge_info->cond_equivalences = XNEWVEC (tree, 10);
1015 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1016 &edge_info->cond_equivalences[8]);
1020 edge_info->max_cond_equivalences = 8;
1021 edge_info->cond_equivalences = XNEWVEC (tree, 8);
1023 build_and_record_new_cond (LE_EXPR, op0, op1,
1024 &edge_info->cond_equivalences[4]);
1025 build_and_record_new_cond (GE_EXPR, op0, op1,
1026 &edge_info->cond_equivalences[6]);
1029 case UNORDERED_EXPR:
1030 edge_info->max_cond_equivalences = 16;
1031 edge_info->cond_equivalences = XNEWVEC (tree, 16);
1032 build_and_record_new_cond (NE_EXPR, op0, op1,
1033 &edge_info->cond_equivalences[4]);
1034 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1035 &edge_info->cond_equivalences[6]);
1036 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1037 &edge_info->cond_equivalences[8]);
1038 build_and_record_new_cond (UNEQ_EXPR, op0, op1,
1039 &edge_info->cond_equivalences[10]);
1040 build_and_record_new_cond (UNLT_EXPR, op0, op1,
1041 &edge_info->cond_equivalences[12]);
1042 build_and_record_new_cond (UNGT_EXPR, op0, op1,
1043 &edge_info->cond_equivalences[14]);
1048 edge_info->max_cond_equivalences = 8;
1049 edge_info->cond_equivalences = XNEWVEC (tree, 8);
1050 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1051 ? UNLE_EXPR : UNGE_EXPR),
1052 op0, op1, &edge_info->cond_equivalences[4]);
1053 build_and_record_new_cond (NE_EXPR, op0, op1,
1054 &edge_info->cond_equivalences[6]);
1058 edge_info->max_cond_equivalences = 8;
1059 edge_info->cond_equivalences = XNEWVEC (tree, 8);
1060 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1061 &edge_info->cond_equivalences[4]);
1062 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1063 &edge_info->cond_equivalences[6]);
1067 edge_info->max_cond_equivalences = 8;
1068 edge_info->cond_equivalences = XNEWVEC (tree, 8);
1069 build_and_record_new_cond (NE_EXPR, op0, op1,
1070 &edge_info->cond_equivalences[4]);
1071 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1072 &edge_info->cond_equivalences[6]);
1076 edge_info->max_cond_equivalences = 4;
1077 edge_info->cond_equivalences = XNEWVEC (tree, 4);
1081 /* Now store the original true and false conditions into the first
1083 edge_info->cond_equivalences[0] = cond;
1084 edge_info->cond_equivalences[1] = boolean_true_node;
1085 edge_info->cond_equivalences[2] = inverted;
1086 edge_info->cond_equivalences[3] = boolean_false_node;
1089 /* A helper function for record_const_or_copy and record_equality.
1090 Do the work of recording the value and undo info. */
1093 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1095 SSA_NAME_VALUE (x) = y;
1097 VEC_reserve (tree, heap, const_and_copies_stack, 2);
1098 VEC_quick_push (tree, const_and_copies_stack, prev_x);
1099 VEC_quick_push (tree, const_and_copies_stack, x);
1103 /* Return the loop depth of the basic block of the defining statement of X.
1104 This number should not be treated as absolutely correct because the loop
1105 information may not be completely up-to-date when dom runs. However, it
1106 will be relatively correct, and as more passes are taught to keep loop info
1107 up to date, the result will become more and more accurate. */
1110 loop_depth_of_name (tree x)
1115 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1116 if (TREE_CODE (x) != SSA_NAME)
1119 /* Otherwise return the loop depth of the defining statement's bb.
1120 Note that there may not actually be a bb for this statement, if the
1121 ssa_name is live on entry. */
1122 defstmt = SSA_NAME_DEF_STMT (x);
1123 defbb = bb_for_stmt (defstmt);
1127 return defbb->loop_depth;
1131 /* Record that X is equal to Y in const_and_copies. Record undo
1132 information in the block-local vector. */
1135 record_const_or_copy (tree x, tree y)
1137 tree prev_x = SSA_NAME_VALUE (x);
1139 if (TREE_CODE (y) == SSA_NAME)
1141 tree tmp = SSA_NAME_VALUE (y);
1146 record_const_or_copy_1 (x, y, prev_x);
1149 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1150 This constrains the cases in which we may treat this as assignment. */
1153 record_equality (tree x, tree y)
1155 tree prev_x = NULL, prev_y = NULL;
1157 if (TREE_CODE (x) == SSA_NAME)
1158 prev_x = SSA_NAME_VALUE (x);
1159 if (TREE_CODE (y) == SSA_NAME)
1160 prev_y = SSA_NAME_VALUE (y);
1162 /* If one of the previous values is invariant, or invariant in more loops
1163 (by depth), then use that.
1164 Otherwise it doesn't matter which value we choose, just so
1165 long as we canonicalize on one value. */
1166 if (is_gimple_min_invariant (y))
1168 else if (is_gimple_min_invariant (x)
1169 || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
1170 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1171 else if (prev_x && is_gimple_min_invariant (prev_x))
1172 x = y, y = prev_x, prev_x = prev_y;
1173 else if (prev_y && TREE_CODE (prev_y) != VALUE_HANDLE)
1176 /* After the swapping, we must have one SSA_NAME. */
1177 if (TREE_CODE (x) != SSA_NAME)
1180 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1181 variable compared against zero. If we're honoring signed zeros,
1182 then we cannot record this value unless we know that the value is
1184 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1185 && (TREE_CODE (y) != REAL_CST
1186 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1189 record_const_or_copy_1 (x, y, prev_x);
1192 /* Returns true when STMT is a simple iv increment. It detects the
1193 following situation:
1195 i_1 = phi (..., i_2)
1196 i_2 = i_1 +/- ... */
1199 simple_iv_increment_p (tree stmt)
1201 tree lhs, rhs, preinc, phi;
1204 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1207 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1208 if (TREE_CODE (lhs) != SSA_NAME)
1211 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1213 if (TREE_CODE (rhs) != PLUS_EXPR
1214 && TREE_CODE (rhs) != MINUS_EXPR)
1217 preinc = TREE_OPERAND (rhs, 0);
1218 if (TREE_CODE (preinc) != SSA_NAME)
1221 phi = SSA_NAME_DEF_STMT (preinc);
1222 if (TREE_CODE (phi) != PHI_NODE)
1225 for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1226 if (PHI_ARG_DEF (phi, i) == lhs)
1232 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1233 known value for that SSA_NAME (or NULL if no value is known).
1235 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1236 successors of BB. */
1239 cprop_into_successor_phis (basic_block bb)
1244 FOR_EACH_EDGE (e, ei, bb->succs)
1249 /* If this is an abnormal edge, then we do not want to copy propagate
1250 into the PHI alternative associated with this edge. */
1251 if (e->flags & EDGE_ABNORMAL)
1254 phi = phi_nodes (e->dest);
1259 for ( ; phi; phi = PHI_CHAIN (phi))
1262 use_operand_p orig_p;
1265 /* The alternative may be associated with a constant, so verify
1266 it is an SSA_NAME before doing anything with it. */
1267 orig_p = PHI_ARG_DEF_PTR (phi, indx);
1268 orig_val = USE_FROM_PTR (orig_p);
1269 if (TREE_CODE (orig_val) != SSA_NAME)
1272 /* If we have *ORIG_P in our constant/copy table, then replace
1273 ORIG_P with its value in our constant/copy table. */
1274 new_val = SSA_NAME_VALUE (orig_val);
1276 && new_val != orig_val
1277 && (TREE_CODE (new_val) == SSA_NAME
1278 || is_gimple_min_invariant (new_val))
1279 && may_propagate_copy (orig_val, new_val))
1280 propagate_value (orig_p, new_val);
1285 /* We have finished optimizing BB, record any information implied by
1286 taking a specific outgoing edge from BB. */
1289 record_edge_info (basic_block bb)
1291 block_stmt_iterator bsi = bsi_last (bb);
1292 struct edge_info *edge_info;
1294 if (! bsi_end_p (bsi))
1296 tree stmt = bsi_stmt (bsi);
1298 if (stmt && TREE_CODE (stmt) == SWITCH_EXPR)
1300 tree cond = SWITCH_COND (stmt);
1302 if (TREE_CODE (cond) == SSA_NAME)
1304 tree labels = SWITCH_LABELS (stmt);
1305 int i, n_labels = TREE_VEC_LENGTH (labels);
1306 tree *info = XCNEWVEC (tree, last_basic_block);
1310 for (i = 0; i < n_labels; i++)
1312 tree label = TREE_VEC_ELT (labels, i);
1313 basic_block target_bb = label_to_block (CASE_LABEL (label));
1315 if (CASE_HIGH (label)
1316 || !CASE_LOW (label)
1317 || info[target_bb->index])
1318 info[target_bb->index] = error_mark_node;
1320 info[target_bb->index] = label;
1323 FOR_EACH_EDGE (e, ei, bb->succs)
1325 basic_block target_bb = e->dest;
1326 tree node = info[target_bb->index];
1328 if (node != NULL && node != error_mark_node)
1330 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
1331 edge_info = allocate_edge_info (e);
1332 edge_info->lhs = cond;
1340 /* A COND_EXPR may create equivalences too. */
1341 if (stmt && TREE_CODE (stmt) == COND_EXPR)
1343 tree cond = COND_EXPR_COND (stmt);
1347 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1349 /* If the conditional is a single variable 'X', record 'X = 1'
1350 for the true edge and 'X = 0' on the false edge. */
1351 if (SSA_VAR_P (cond))
1353 struct edge_info *edge_info;
1355 edge_info = allocate_edge_info (true_edge);
1356 edge_info->lhs = cond;
1357 edge_info->rhs = constant_boolean_node (1, TREE_TYPE (cond));
1359 edge_info = allocate_edge_info (false_edge);
1360 edge_info->lhs = cond;
1361 edge_info->rhs = constant_boolean_node (0, TREE_TYPE (cond));
1363 /* Equality tests may create one or two equivalences. */
1364 else if (COMPARISON_CLASS_P (cond))
1366 tree op0 = TREE_OPERAND (cond, 0);
1367 tree op1 = TREE_OPERAND (cond, 1);
1369 /* Special case comparing booleans against a constant as we
1370 know the value of OP0 on both arms of the branch. i.e., we
1371 can record an equivalence for OP0 rather than COND. */
1372 if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1373 && TREE_CODE (op0) == SSA_NAME
1374 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
1375 && is_gimple_min_invariant (op1))
1377 if (TREE_CODE (cond) == EQ_EXPR)
1379 edge_info = allocate_edge_info (true_edge);
1380 edge_info->lhs = op0;
1381 edge_info->rhs = (integer_zerop (op1)
1382 ? boolean_false_node
1383 : boolean_true_node);
1385 edge_info = allocate_edge_info (false_edge);
1386 edge_info->lhs = op0;
1387 edge_info->rhs = (integer_zerop (op1)
1389 : boolean_false_node);
1393 edge_info = allocate_edge_info (true_edge);
1394 edge_info->lhs = op0;
1395 edge_info->rhs = (integer_zerop (op1)
1397 : boolean_false_node);
1399 edge_info = allocate_edge_info (false_edge);
1400 edge_info->lhs = op0;
1401 edge_info->rhs = (integer_zerop (op1)
1402 ? boolean_false_node
1403 : boolean_true_node);
1407 else if (is_gimple_min_invariant (op0)
1408 && (TREE_CODE (op1) == SSA_NAME
1409 || is_gimple_min_invariant (op1)))
1411 tree inverted = invert_truthvalue (cond);
1412 struct edge_info *edge_info;
1414 edge_info = allocate_edge_info (true_edge);
1415 record_conditions (edge_info, cond, inverted);
1417 if (TREE_CODE (cond) == EQ_EXPR)
1419 edge_info->lhs = op1;
1420 edge_info->rhs = op0;
1423 edge_info = allocate_edge_info (false_edge);
1424 record_conditions (edge_info, inverted, cond);
1426 if (TREE_CODE (cond) == NE_EXPR)
1428 edge_info->lhs = op1;
1429 edge_info->rhs = op0;
1433 else if (TREE_CODE (op0) == SSA_NAME
1434 && (is_gimple_min_invariant (op1)
1435 || TREE_CODE (op1) == SSA_NAME))
1437 tree inverted = invert_truthvalue (cond);
1438 struct edge_info *edge_info;
1440 edge_info = allocate_edge_info (true_edge);
1441 record_conditions (edge_info, cond, inverted);
1443 if (TREE_CODE (cond) == EQ_EXPR)
1445 edge_info->lhs = op0;
1446 edge_info->rhs = op1;
1449 edge_info = allocate_edge_info (false_edge);
1450 record_conditions (edge_info, inverted, cond);
1452 if (TREE_CODE (cond) == NE_EXPR)
1454 edge_info->lhs = op0;
1455 edge_info->rhs = op1;
1460 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1465 /* Propagate information from BB to its outgoing edges.
1467 This can include equivalency information implied by control statements
1468 at the end of BB and const/copy propagation into PHIs in BB's
1469 successor blocks. */
1472 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1475 record_edge_info (bb);
1476 cprop_into_successor_phis (bb);
1479 /* Search for redundant computations in STMT. If any are found, then
1480 replace them with the variable holding the result of the computation.
1482 If safe, record this expression into the available expression hash
1486 eliminate_redundant_computations (tree stmt)
1488 tree *expr_p, def = NULL_TREE;
1491 bool retval = false;
1492 bool modify_expr_p = false;
1494 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1495 def = GIMPLE_STMT_OPERAND (stmt, 0);
1497 /* Certain expressions on the RHS can be optimized away, but can not
1498 themselves be entered into the hash tables. */
1500 || TREE_CODE (def) != SSA_NAME
1501 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1502 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF)
1503 /* Do not record equivalences for increments of ivs. This would create
1504 overlapping live ranges for a very questionable gain. */
1505 || simple_iv_increment_p (stmt))
1508 /* Check if the expression has been computed before. */
1509 cached_lhs = lookup_avail_expr (stmt, insert);
1511 opt_stats.num_exprs_considered++;
1513 /* Get a pointer to the expression we are trying to optimize. */
1514 if (TREE_CODE (stmt) == COND_EXPR)
1515 expr_p = &COND_EXPR_COND (stmt);
1516 else if (TREE_CODE (stmt) == SWITCH_EXPR)
1517 expr_p = &SWITCH_COND (stmt);
1518 else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
1520 expr_p = &GIMPLE_STMT_OPERAND (TREE_OPERAND (stmt, 0), 1);
1521 modify_expr_p = true;
1525 expr_p = &GENERIC_TREE_OPERAND (stmt, 1);
1526 modify_expr_p = true;
1529 /* It is safe to ignore types here since we have already done
1530 type checking in the hashing and equality routines. In fact
1531 type checking here merely gets in the way of constant
1532 propagation. Also, make sure that it is safe to propagate
1533 CACHED_LHS into *EXPR_P. */
1535 && ((TREE_CODE (cached_lhs) != SSA_NAME
1537 || useless_type_conversion_p (TREE_TYPE (*expr_p),
1538 TREE_TYPE (cached_lhs))))
1539 || may_propagate_copy (*expr_p, cached_lhs)))
1541 if (dump_file && (dump_flags & TDF_DETAILS))
1543 fprintf (dump_file, " Replaced redundant expr '");
1544 print_generic_expr (dump_file, *expr_p, dump_flags);
1545 fprintf (dump_file, "' with '");
1546 print_generic_expr (dump_file, cached_lhs, dump_flags);
1547 fprintf (dump_file, "'\n");
1552 #if defined ENABLE_CHECKING
1553 gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
1554 || is_gimple_min_invariant (cached_lhs));
1557 if (TREE_CODE (cached_lhs) == ADDR_EXPR
1558 || (POINTER_TYPE_P (TREE_TYPE (*expr_p))
1559 && is_gimple_min_invariant (cached_lhs)))
1563 && !useless_type_conversion_p (TREE_TYPE (*expr_p),
1564 TREE_TYPE (cached_lhs)))
1565 cached_lhs = fold_convert (TREE_TYPE (*expr_p), cached_lhs);
1567 propagate_tree_value (expr_p, cached_lhs);
1568 mark_stmt_modified (stmt);
1573 /* STMT, a GIMPLE_MODIFY_STMT, may create certain equivalences, in either
1574 the available expressions table or the const_and_copies table.
1575 Detect and record those equivalences. */
1578 record_equivalences_from_stmt (tree stmt, int may_optimize_p, stmt_ann_t ann)
1580 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1581 enum tree_code lhs_code = TREE_CODE (lhs);
1583 if (lhs_code == SSA_NAME)
1585 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1587 /* Strip away any useless type conversions. */
1588 STRIP_USELESS_TYPE_CONVERSION (rhs);
1590 /* If the RHS of the assignment is a constant or another variable that
1591 may be propagated, register it in the CONST_AND_COPIES table. We
1592 do not need to record unwind data for this, since this is a true
1593 assignment and not an equivalence inferred from a comparison. All
1594 uses of this ssa name are dominated by this assignment, so unwinding
1595 just costs time and space. */
1597 && (TREE_CODE (rhs) == SSA_NAME
1598 || is_gimple_min_invariant (rhs)))
1599 SSA_NAME_VALUE (lhs) = rhs;
1602 /* A memory store, even an aliased store, creates a useful
1603 equivalence. By exchanging the LHS and RHS, creating suitable
1604 vops and recording the result in the available expression table,
1605 we may be able to expose more redundant loads. */
1606 if (!ann->has_volatile_ops
1607 && stmt_references_memory_p (stmt)
1608 && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == SSA_NAME
1609 || is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt, 1)))
1610 && !is_gimple_reg (lhs))
1612 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1615 /* Build a new statement with the RHS and LHS exchanged. */
1616 new_stmt = build_gimple_modify_stmt (rhs, lhs);
1617 create_ssa_artificial_load_stmt (new_stmt, stmt, true);
1619 /* Finally enter the statement into the available expression
1621 lookup_avail_expr (new_stmt, true);
1625 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1626 CONST_AND_COPIES. */
1629 cprop_operand (tree stmt, use_operand_p op_p)
1631 bool may_have_exposed_new_symbols = false;
1633 tree op = USE_FROM_PTR (op_p);
1635 /* If the operand has a known constant value or it is known to be a
1636 copy of some other variable, use the value or copy stored in
1637 CONST_AND_COPIES. */
1638 val = SSA_NAME_VALUE (op);
1639 if (val && val != op && TREE_CODE (val) != VALUE_HANDLE)
1641 tree op_type, val_type;
1643 /* Do not change the base variable in the virtual operand
1644 tables. That would make it impossible to reconstruct
1645 the renamed virtual operand if we later modify this
1646 statement. Also only allow the new value to be an SSA_NAME
1647 for propagation into virtual operands. */
1648 if (!is_gimple_reg (op)
1649 && (TREE_CODE (val) != SSA_NAME
1650 || is_gimple_reg (val)
1651 || get_virtual_var (val) != get_virtual_var (op)))
1654 /* Do not replace hard register operands in asm statements. */
1655 if (TREE_CODE (stmt) == ASM_EXPR
1656 && !may_propagate_copy_into_asm (op))
1659 /* Get the toplevel type of each operand. */
1660 op_type = TREE_TYPE (op);
1661 val_type = TREE_TYPE (val);
1663 /* While both types are pointers, get the type of the object
1665 while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
1667 op_type = TREE_TYPE (op_type);
1668 val_type = TREE_TYPE (val_type);
1671 /* Make sure underlying types match before propagating a constant by
1672 converting the constant to the proper type. Note that convert may
1673 return a non-gimple expression, in which case we ignore this
1674 propagation opportunity. */
1675 if (TREE_CODE (val) != SSA_NAME)
1677 if (!useless_type_conversion_p (op_type, val_type))
1679 val = fold_convert (TREE_TYPE (op), val);
1680 if (!is_gimple_min_invariant (val))
1685 /* Certain operands are not allowed to be copy propagated due
1686 to their interaction with exception handling and some GCC
1688 else if (!may_propagate_copy (op, val))
1691 /* Do not propagate copies if the propagated value is at a deeper loop
1692 depth than the propagatee. Otherwise, this may move loop variant
1693 variables outside of their loops and prevent coalescing
1694 opportunities. If the value was loop invariant, it will be hoisted
1695 by LICM and exposed for copy propagation. */
1696 if (loop_depth_of_name (val) > loop_depth_of_name (op))
1700 if (dump_file && (dump_flags & TDF_DETAILS))
1702 fprintf (dump_file, " Replaced '");
1703 print_generic_expr (dump_file, op, dump_flags);
1704 fprintf (dump_file, "' with %s '",
1705 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
1706 print_generic_expr (dump_file, val, dump_flags);
1707 fprintf (dump_file, "'\n");
1710 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
1711 that we may have exposed a new symbol for SSA renaming. */
1712 if (TREE_CODE (val) == ADDR_EXPR
1713 || (POINTER_TYPE_P (TREE_TYPE (op))
1714 && is_gimple_min_invariant (val)))
1715 may_have_exposed_new_symbols = true;
1717 if (TREE_CODE (val) != SSA_NAME)
1718 opt_stats.num_const_prop++;
1720 opt_stats.num_copy_prop++;
1722 propagate_value (op_p, val);
1724 /* And note that we modified this statement. This is now
1725 safe, even if we changed virtual operands since we will
1726 rescan the statement and rewrite its operands again. */
1727 mark_stmt_modified (stmt);
1729 return may_have_exposed_new_symbols;
1732 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1733 known value for that SSA_NAME (or NULL if no value is known).
1735 Propagate values from CONST_AND_COPIES into the uses, vuses and
1736 vdef_ops of STMT. */
1739 cprop_into_stmt (tree stmt)
1741 bool may_have_exposed_new_symbols = false;
1745 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
1747 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
1748 may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
1751 return may_have_exposed_new_symbols;
1755 /* Optimize the statement pointed to by iterator SI.
1757 We try to perform some simplistic global redundancy elimination and
1758 constant propagation:
1760 1- To detect global redundancy, we keep track of expressions that have
1761 been computed in this block and its dominators. If we find that the
1762 same expression is computed more than once, we eliminate repeated
1763 computations by using the target of the first one.
1765 2- Constant values and copy assignments. This is used to do very
1766 simplistic constant and copy propagation. When a constant or copy
1767 assignment is found, we map the value on the RHS of the assignment to
1768 the variable in the LHS in the CONST_AND_COPIES table. */
1771 optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1772 basic_block bb, block_stmt_iterator si)
1775 tree stmt, old_stmt;
1776 bool may_optimize_p;
1777 bool may_have_exposed_new_symbols = false;
1779 old_stmt = stmt = bsi_stmt (si);
1781 if (TREE_CODE (stmt) == COND_EXPR)
1782 canonicalize_comparison (stmt);
1784 update_stmt_if_modified (stmt);
1785 ann = stmt_ann (stmt);
1786 opt_stats.num_stmts++;
1787 may_have_exposed_new_symbols = false;
1788 push_stmt_changes (bsi_stmt_ptr (si));
1790 if (dump_file && (dump_flags & TDF_DETAILS))
1792 fprintf (dump_file, "Optimizing statement ");
1793 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1796 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
1797 may_have_exposed_new_symbols = cprop_into_stmt (stmt);
1799 /* If the statement has been modified with constant replacements,
1800 fold its RHS before checking for redundant computations. */
1805 /* Try to fold the statement making sure that STMT is kept
1807 if (fold_stmt (bsi_stmt_ptr (si)))
1809 stmt = bsi_stmt (si);
1810 ann = stmt_ann (stmt);
1812 if (dump_file && (dump_flags & TDF_DETAILS))
1814 fprintf (dump_file, " Folded to: ");
1815 print_generic_stmt (dump_file, stmt, TDF_SLIM);
1819 rhs = get_rhs (stmt);
1820 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
1821 recompute_tree_invariant_for_addr_expr (rhs);
1823 /* Constant/copy propagation above may change the set of
1824 virtual operands associated with this statement. Folding
1825 may remove the need for some virtual operands.
1827 Indicate we will need to rescan and rewrite the statement. */
1828 may_have_exposed_new_symbols = true;
1831 /* Check for redundant computations. Do this optimization only
1832 for assignments that have no volatile ops and conditionals. */
1833 may_optimize_p = (!ann->has_volatile_ops
1834 && ((TREE_CODE (stmt) == RETURN_EXPR
1835 && TREE_OPERAND (stmt, 0)
1836 && TREE_CODE (TREE_OPERAND (stmt, 0))
1837 == GIMPLE_MODIFY_STMT
1838 && ! (TREE_SIDE_EFFECTS
1839 (GIMPLE_STMT_OPERAND
1840 (TREE_OPERAND (stmt, 0), 1))))
1841 || (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1842 && ! TREE_SIDE_EFFECTS (GIMPLE_STMT_OPERAND (stmt,
1844 || TREE_CODE (stmt) == COND_EXPR
1845 || TREE_CODE (stmt) == SWITCH_EXPR));
1848 may_have_exposed_new_symbols |= eliminate_redundant_computations (stmt);
1850 /* Record any additional equivalences created by this statement. */
1851 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1852 record_equivalences_from_stmt (stmt, may_optimize_p, ann);
1854 /* If STMT is a COND_EXPR and it was modified, then we may know
1855 where it goes. If that is the case, then mark the CFG as altered.
1857 This will cause us to later call remove_unreachable_blocks and
1858 cleanup_tree_cfg when it is safe to do so. It is not safe to
1859 clean things up here since removal of edges and such can trigger
1860 the removal of PHI nodes, which in turn can release SSA_NAMEs to
1863 That's all fine and good, except that once SSA_NAMEs are released
1864 to the manager, we must not call create_ssa_name until all references
1865 to released SSA_NAMEs have been eliminated.
1867 All references to the deleted SSA_NAMEs can not be eliminated until
1868 we remove unreachable blocks.
1870 We can not remove unreachable blocks until after we have completed
1871 any queued jump threading.
1873 We can not complete any queued jump threads until we have taken
1874 appropriate variables out of SSA form. Taking variables out of
1875 SSA form can call create_ssa_name and thus we lose.
1877 Ultimately I suspect we're going to need to change the interface
1878 into the SSA_NAME manager. */
1883 if (TREE_CODE (stmt) == COND_EXPR)
1884 val = COND_EXPR_COND (stmt);
1885 else if (TREE_CODE (stmt) == SWITCH_EXPR)
1886 val = SWITCH_COND (stmt);
1888 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
1891 /* If we simplified a statement in such a way as to be shown that it
1892 cannot trap, update the eh information and the cfg to match. */
1893 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
1895 bitmap_set_bit (need_eh_cleanup, bb->index);
1896 if (dump_file && (dump_flags & TDF_DETAILS))
1897 fprintf (dump_file, " Flagged to clear EH edges.\n");
1901 if (may_have_exposed_new_symbols)
1903 /* Queue the statement to be re-scanned after all the
1904 AVAIL_EXPRS have been processed. The change buffer stack for
1905 all the pushed statements will be processed when this queue
1907 VEC_safe_push (tree_p, heap, stmts_to_rescan, bsi_stmt_ptr (si));
1911 /* Otherwise, just discard the recently pushed change buffer. If
1912 not, the STMTS_TO_RESCAN queue will get out of synch with the
1913 change buffer stack. */
1914 discard_stmt_changes (bsi_stmt_ptr (si));
1918 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
1919 found, return its LHS. Otherwise insert STMT in the table and return
1922 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
1923 is also added to the stack pointed to by BLOCK_AVAIL_EXPRS_P, so that they
1924 can be removed when we finish processing this block and its children.
1926 NOTE: This function assumes that STMT is a GIMPLE_MODIFY_STMT node that
1927 contains no CALL_EXPR on its RHS and makes no volatile nor
1928 aliased references. */
1931 lookup_avail_expr (tree stmt, bool insert)
1936 struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
1938 lhs = TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1939 ? GIMPLE_STMT_OPERAND (stmt, 0) : NULL;
1941 initialize_hash_element (stmt, lhs, element);
1943 /* Don't bother remembering constant assignments and copy operations.
1944 Constants and copy operations are handled by the constant/copy propagator
1945 in optimize_stmt. */
1946 if (TREE_CODE (element->rhs) == SSA_NAME
1947 || is_gimple_min_invariant (element->rhs))
1953 /* Finally try to find the expression in the main expression hash table. */
1954 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
1955 (insert ? INSERT : NO_INSERT));
1964 *slot = (void *) element;
1965 VEC_safe_push (tree, heap, avail_exprs_stack,
1966 stmt ? stmt : element->rhs);
1970 /* Extract the LHS of the assignment so that it can be used as the current
1971 definition of another variable. */
1972 lhs = ((struct expr_hash_elt *)*slot)->lhs;
1974 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
1975 use the value from the const_and_copies table. */
1976 if (TREE_CODE (lhs) == SSA_NAME)
1978 temp = SSA_NAME_VALUE (lhs);
1979 if (temp && TREE_CODE (temp) != VALUE_HANDLE)
1987 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
1988 GIMPLE_MODIFY_STMT statements. We compute a value number for expressions
1989 using the code of the expression and the SSA numbers of its operands. */
1992 avail_expr_hash (const void *p)
1994 tree stmt = ((const struct expr_hash_elt *)p)->stmt;
1995 tree rhs = ((const struct expr_hash_elt *)p)->rhs;
2000 /* iterative_hash_expr knows how to deal with any expression and
2001 deals with commutative operators as well, so just use it instead
2002 of duplicating such complexities here. */
2003 val = iterative_hash_expr (rhs, val);
2005 /* If the hash table entry is not associated with a statement, then we
2006 can just hash the expression and not worry about virtual operands
2008 if (!stmt || !stmt_ann (stmt))
2011 /* Add the SSA version numbers of every vuse operand. This is important
2012 because compound variables like arrays are not renamed in the
2013 operands. Rather, the rename is done on the virtual variable
2014 representing all the elements of the array. */
2015 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
2016 val = iterative_hash_expr (vuse, val);
2022 real_avail_expr_hash (const void *p)
2024 return ((const struct expr_hash_elt *)p)->hash;
2028 avail_expr_eq (const void *p1, const void *p2)
2030 tree stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
2031 tree rhs1 = ((const struct expr_hash_elt *)p1)->rhs;
2032 tree stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
2033 tree rhs2 = ((const struct expr_hash_elt *)p2)->rhs;
2035 /* If they are the same physical expression, return true. */
2036 if (rhs1 == rhs2 && stmt1 == stmt2)
2039 /* If their codes are not equal, then quit now. */
2040 if (TREE_CODE (rhs1) != TREE_CODE (rhs2))
2043 /* In case of a collision, both RHS have to be identical and have the
2044 same VUSE operands. */
2045 if (types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2))
2046 && operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
2048 bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE);
2049 gcc_assert (!ret || ((const struct expr_hash_elt *)p1)->hash
2050 == ((const struct expr_hash_elt *)p2)->hash);
2057 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2058 up degenerate PHIs created by or exposed by jump threading. */
2060 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2064 degenerate_phi_result (tree phi)
2066 tree lhs = PHI_RESULT (phi);
2070 /* Ignoring arguments which are the same as LHS, if all the remaining
2071 arguments are the same, then the PHI is a degenerate and has the
2072 value of that common argument. */
2073 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2075 tree arg = PHI_ARG_DEF (phi, i);
2081 else if (!operand_equal_p (arg, val, 0))
2084 return (i == PHI_NUM_ARGS (phi) ? val : NULL);
2087 /* Given a tree node T, which is either a PHI_NODE or GIMPLE_MODIFY_STMT,
2088 remove it from the IL. */
2091 remove_stmt_or_phi (tree t)
2093 if (TREE_CODE (t) == PHI_NODE)
2094 remove_phi_node (t, NULL, true);
2097 block_stmt_iterator bsi = bsi_for_stmt (t);
2098 bsi_remove (&bsi, true);
2103 /* Given a tree node T, which is either a PHI_NODE or GIMPLE_MODIFY_STMT,
2104 return the "rhs" of the node, in the case of a non-degenerate
2105 PHI, NULL is returned. */
2108 get_rhs_or_phi_arg (tree t)
2110 if (TREE_CODE (t) == PHI_NODE)
2111 return degenerate_phi_result (t);
2112 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
2113 return GIMPLE_STMT_OPERAND (t, 1);
2118 /* Given a tree node T, which is either a PHI_NODE or a GIMPLE_MODIFY_STMT,
2119 return the "lhs" of the node. */
2122 get_lhs_or_phi_result (tree t)
2124 if (TREE_CODE (t) == PHI_NODE)
2125 return PHI_RESULT (t);
2126 else if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
2127 return GIMPLE_STMT_OPERAND (t, 0);
2131 /* Propagate RHS into all uses of LHS (when possible).
2133 RHS and LHS are derived from STMT, which is passed in solely so
2134 that we can remove it if propagation is successful.
2136 When propagating into a PHI node or into a statement which turns
2137 into a trivial copy or constant initialization, set the
2138 appropriate bit in INTERESTING_NAMEs so that we will visit those
2139 nodes as well in an effort to pick up secondary optimization
2143 propagate_rhs_into_lhs (tree stmt, tree lhs, tree rhs, bitmap interesting_names)
2145 /* First verify that propagation is valid and isn't going to move a
2146 loop variant variable outside its loop. */
2147 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
2148 && (TREE_CODE (rhs) != SSA_NAME
2149 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
2150 && may_propagate_copy (lhs, rhs)
2151 && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
2153 use_operand_p use_p;
2154 imm_use_iterator iter;
2159 if (dump_file && (dump_flags & TDF_DETAILS))
2161 fprintf (dump_file, " Replacing '");
2162 print_generic_expr (dump_file, lhs, dump_flags);
2163 fprintf (dump_file, "' with %s '",
2164 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
2165 print_generic_expr (dump_file, rhs, dump_flags);
2166 fprintf (dump_file, "'\n");
2169 /* Walk over every use of LHS and try to replace the use with RHS.
2170 At this point the only reason why such a propagation would not
2171 be successful would be if the use occurs in an ASM_EXPR. */
2172 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
2175 /* It's not always safe to propagate into an ASM_EXPR. */
2176 if (TREE_CODE (use_stmt) == ASM_EXPR
2177 && ! may_propagate_copy_into_asm (lhs))
2184 if (dump_file && (dump_flags & TDF_DETAILS))
2186 fprintf (dump_file, " Original statement:");
2187 print_generic_expr (dump_file, use_stmt, dump_flags);
2188 fprintf (dump_file, "\n");
2191 push_stmt_changes (&use_stmt);
2193 /* Propagate the RHS into this use of the LHS. */
2194 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2195 propagate_value (use_p, rhs);
2197 /* Special cases to avoid useless calls into the folding
2198 routines, operand scanning, etc.
2200 First, propagation into a PHI may cause the PHI to become
2201 a degenerate, so mark the PHI as interesting. No other
2202 actions are necessary.
2204 Second, if we're propagating a virtual operand and the
2205 propagation does not change the underlying _DECL node for
2206 the virtual operand, then no further actions are necessary. */
2207 if (TREE_CODE (use_stmt) == PHI_NODE
2208 || (! is_gimple_reg (lhs)
2209 && TREE_CODE (rhs) == SSA_NAME
2210 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
2213 if (dump_file && (dump_flags & TDF_DETAILS))
2215 fprintf (dump_file, " Updated statement:");
2216 print_generic_expr (dump_file, use_stmt, dump_flags);
2217 fprintf (dump_file, "\n");
2220 /* Propagation into a PHI may expose new degenerate PHIs,
2221 so mark the result of the PHI as interesting. */
2222 if (TREE_CODE (use_stmt) == PHI_NODE)
2224 tree result = get_lhs_or_phi_result (use_stmt);
2225 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2228 discard_stmt_changes (&use_stmt);
2232 /* From this point onward we are propagating into a
2233 real statement. Folding may (or may not) be possible,
2234 we may expose new operands, expose dead EH edges,
2236 fold_stmt_inplace (use_stmt);
2238 /* Sometimes propagation can expose new operands to the
2239 renamer. Note this will call update_stmt at the
2240 appropriate time. */
2241 pop_stmt_changes (&use_stmt);
2244 if (dump_file && (dump_flags & TDF_DETAILS))
2246 fprintf (dump_file, " Updated statement:");
2247 print_generic_expr (dump_file, use_stmt, dump_flags);
2248 fprintf (dump_file, "\n");
2251 /* If we replaced a variable index with a constant, then
2252 we would need to update the invariant flag for ADDR_EXPRs. */
2253 if (TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
2254 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == ADDR_EXPR)
2255 recompute_tree_invariant_for_addr_expr
2256 (GIMPLE_STMT_OPERAND (use_stmt, 1));
2258 /* If we cleaned up EH information from the statement,
2259 mark its containing block as needing EH cleanups. */
2260 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
2262 bitmap_set_bit (need_eh_cleanup, bb_for_stmt (use_stmt)->index);
2263 if (dump_file && (dump_flags & TDF_DETAILS))
2264 fprintf (dump_file, " Flagged to clear EH edges.\n");
2267 /* Propagation may expose new trivial copy/constant propagation
2269 if (TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
2270 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 0)) == SSA_NAME
2271 && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt, 1)) == SSA_NAME
2272 || is_gimple_min_invariant (GIMPLE_STMT_OPERAND (use_stmt,
2275 tree result = get_lhs_or_phi_result (use_stmt);
2276 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2279 /* Propagation into these nodes may make certain edges in
2280 the CFG unexecutable. We want to identify them as PHI nodes
2281 at the destination of those unexecutable edges may become
2283 else if (TREE_CODE (use_stmt) == COND_EXPR
2284 || TREE_CODE (use_stmt) == SWITCH_EXPR
2285 || TREE_CODE (use_stmt) == GOTO_EXPR)
2289 if (TREE_CODE (use_stmt) == COND_EXPR)
2290 val = COND_EXPR_COND (use_stmt);
2291 else if (TREE_CODE (use_stmt) == SWITCH_EXPR)
2292 val = SWITCH_COND (use_stmt);
2294 val = GOTO_DESTINATION (use_stmt);
2296 if (is_gimple_min_invariant (val))
2298 basic_block bb = bb_for_stmt (use_stmt);
2299 edge te = find_taken_edge (bb, val);
2302 block_stmt_iterator bsi;
2304 /* Remove all outgoing edges except TE. */
2305 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
2311 /* Mark all the PHI nodes at the destination of
2312 the unexecutable edge as interesting. */
2313 for (phi = phi_nodes (e->dest);
2315 phi = PHI_CHAIN (phi))
2317 tree result = PHI_RESULT (phi);
2318 int version = SSA_NAME_VERSION (result);
2320 bitmap_set_bit (interesting_names, version);
2323 te->probability += e->probability;
2325 te->count += e->count;
2333 bsi = bsi_last (bb_for_stmt (use_stmt));
2334 bsi_remove (&bsi, true);
2336 /* And fixup the flags on the single remaining edge. */
2337 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
2338 te->flags &= ~EDGE_ABNORMAL;
2339 te->flags |= EDGE_FALLTHRU;
2340 if (te->probability > REG_BR_PROB_BASE)
2341 te->probability = REG_BR_PROB_BASE;
2346 /* Ensure there is nothing else to do. */
2347 gcc_assert (!all || has_zero_uses (lhs));
2349 /* If we were able to propagate away all uses of LHS, then
2350 we can remove STMT. */
2352 remove_stmt_or_phi (stmt);
2356 /* T is either a PHI node (potentially a degenerate PHI node) or
2357 a statement that is a trivial copy or constant initialization.
2359 Attempt to eliminate T by propagating its RHS into all uses of
2360 its LHS. This may in turn set new bits in INTERESTING_NAMES
2361 for nodes we want to revisit later.
2363 All exit paths should clear INTERESTING_NAMES for the result
2367 eliminate_const_or_copy (tree t, bitmap interesting_names)
2369 tree lhs = get_lhs_or_phi_result (t);
2371 int version = SSA_NAME_VERSION (lhs);
2373 /* If the LHS of this statement or PHI has no uses, then we can
2374 just eliminate it. This can occur if, for example, the PHI
2375 was created by block duplication due to threading and its only
2376 use was in the conditional at the end of the block which was
2378 if (has_zero_uses (lhs))
2380 bitmap_clear_bit (interesting_names, version);
2381 remove_stmt_or_phi (t);
2385 /* Get the RHS of the assignment or PHI node if the PHI is a
2387 rhs = get_rhs_or_phi_arg (t);
2390 bitmap_clear_bit (interesting_names, version);
2394 propagate_rhs_into_lhs (t, lhs, rhs, interesting_names);
2396 /* Note that T may well have been deleted by now, so do
2397 not access it, instead use the saved version # to clear
2398 T's entry in the worklist. */
2399 bitmap_clear_bit (interesting_names, version);
2402 /* The first phase in degenerate PHI elimination.
2404 Eliminate the degenerate PHIs in BB, then recurse on the
2405 dominator children of BB. */
2408 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names)
2413 for (phi = phi_nodes (bb); phi; phi = next)
2415 next = PHI_CHAIN (phi);
2416 eliminate_const_or_copy (phi, interesting_names);
2419 /* Recurse into the dominator children of BB. */
2420 for (son = first_dom_son (CDI_DOMINATORS, bb);
2422 son = next_dom_son (CDI_DOMINATORS, son))
2423 eliminate_degenerate_phis_1 (son, interesting_names);
2427 /* A very simple pass to eliminate degenerate PHI nodes from the
2428 IL. This is meant to be fast enough to be able to be run several
2429 times in the optimization pipeline.
2431 Certain optimizations, particularly those which duplicate blocks
2432 or remove edges from the CFG can create or expose PHIs which are
2433 trivial copies or constant initializations.
2435 While we could pick up these optimizations in DOM or with the
2436 combination of copy-prop and CCP, those solutions are far too
2437 heavy-weight for our needs.
2439 This implementation has two phases so that we can efficiently
2440 eliminate the first order degenerate PHIs and second order
2443 The first phase performs a dominator walk to identify and eliminate
2444 the vast majority of the degenerate PHIs. When a degenerate PHI
2445 is identified and eliminated any affected statements or PHIs
2446 are put on a worklist.
2448 The second phase eliminates degenerate PHIs and trivial copies
2449 or constant initializations using the worklist. This is how we
2450 pick up the secondary optimization opportunities with minimal
2454 eliminate_degenerate_phis (void)
2456 bitmap interesting_names;
2457 bitmap interesting_names1;
2459 /* Bitmap of blocks which need EH information updated. We can not
2460 update it on-the-fly as doing so invalidates the dominator tree. */
2461 need_eh_cleanup = BITMAP_ALLOC (NULL);
2463 /* INTERESTING_NAMES is effectively our worklist, indexed by
2466 A set bit indicates that the statement or PHI node which
2467 defines the SSA_NAME should be (re)examined to determine if
2468 it has become a degenerate PHI or trivial const/copy propagation
2471 Experiments have show we generally get better compilation
2472 time behavior with bitmaps rather than sbitmaps. */
2473 interesting_names = BITMAP_ALLOC (NULL);
2474 interesting_names1 = BITMAP_ALLOC (NULL);
2476 calculate_dominance_info (CDI_DOMINATORS);
2477 cfg_altered = false;
2479 /* First phase. Eliminate degenerate PHIs via a dominator
2482 Experiments have indicated that we generally get better
2483 compile-time behavior by visiting blocks in the first
2484 phase in dominator order. Presumably this is because walking
2485 in dominator order leaves fewer PHIs for later examination
2486 by the worklist phase. */
2487 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
2489 /* Second phase. Eliminate second order degenerate PHIs as well
2490 as trivial copies or constant initializations identified by
2491 the first phase or this phase. Basically we keep iterating
2492 until our set of INTERESTING_NAMEs is empty. */
2493 while (!bitmap_empty_p (interesting_names))
2498 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2499 changed during the loop. Copy it to another bitmap and
2501 bitmap_copy (interesting_names1, interesting_names);
2503 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
2505 tree name = ssa_name (i);
2507 /* Ignore SSA_NAMEs that have been released because
2508 their defining statement was deleted (unreachable). */
2510 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
2516 free_dominance_info (CDI_DOMINATORS);
2518 /* Propagation of const and copies may make some EH edges dead. Purge
2519 such edges from the CFG as needed. */
2520 if (!bitmap_empty_p (need_eh_cleanup))
2522 tree_purge_all_dead_eh_edges (need_eh_cleanup);
2523 BITMAP_FREE (need_eh_cleanup);
2526 BITMAP_FREE (interesting_names);
2527 BITMAP_FREE (interesting_names1);
2531 struct gimple_opt_pass pass_phi_only_cprop =
2535 "phicprop", /* name */
2536 gate_dominator, /* gate */
2537 eliminate_degenerate_phis, /* execute */
2540 0, /* static_pass_number */
2541 TV_TREE_PHI_CPROP, /* tv_id */
2542 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2543 0, /* properties_provided */
2544 0, /* properties_destroyed */
2545 0, /* todo_flags_start */
2551 | TODO_update_ssa /* todo_flags_finish */