1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
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 edges 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 statistics_counter_event (cfun
, "Redundant expressions eliminated",
362 statistics_counter_event (cfun
, "Constants propagated",
363 opt_stats
.num_const_prop
);
364 statistics_counter_event (cfun
, "Copies propagated",
365 opt_stats
.num_copy_prop
);
367 /* Debugging dumps. */
368 if (dump_file
&& (dump_flags
& TDF_STATS
))
369 dump_dominator_optimization_stats (dump_file
);
371 loop_optimizer_finalize ();
373 /* Delete our main hashtable. */
374 htab_delete (avail_exprs
);
376 /* And finalize the dominator walker. */
377 fini_walk_dominator_tree (&walk_data
);
379 /* Free asserted bitmaps and stacks. */
380 BITMAP_FREE (need_eh_cleanup
);
382 VEC_free (tree
, heap
, avail_exprs_stack
);
383 VEC_free (tree
, heap
, const_and_copies_stack
);
384 VEC_free (tree_p
, heap
, stmts_to_rescan
);
389 gate_dominator (void)
391 return flag_tree_dom
!= 0;
394 struct gimple_opt_pass pass_dominator
=
399 gate_dominator
, /* gate */
400 tree_ssa_dominator_optimize
, /* execute */
403 0, /* static_pass_number */
404 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
405 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
406 0, /* properties_provided */
407 0, /* properties_destroyed */
408 0, /* todo_flags_start */
412 | TODO_verify_ssa
/* todo_flags_finish */
417 /* Given a stmt CONDSTMT containing a COND_EXPR, canonicalize the
418 COND_EXPR into a canonical form. */
421 canonicalize_comparison (tree condstmt
)
423 tree cond
= COND_EXPR_COND (condstmt
);
426 enum tree_code code
= TREE_CODE (cond
);
428 if (!COMPARISON_CLASS_P (cond
))
431 op0
= TREE_OPERAND (cond
, 0);
432 op1
= TREE_OPERAND (cond
, 1);
434 /* If it would be profitable to swap the operands, then do so to
435 canonicalize the statement, enabling better optimization.
437 By placing canonicalization of such expressions here we
438 transparently keep statements in canonical form, even
439 when the statement is modified. */
440 if (tree_swap_operands_p (op0
, op1
, false))
442 /* For relationals we need to swap the operands
443 and change the code. */
449 TREE_SET_CODE (cond
, swap_tree_comparison (code
));
450 swap_tree_operands (condstmt
,
451 &TREE_OPERAND (cond
, 0),
452 &TREE_OPERAND (cond
, 1));
453 /* If one operand was in the operand cache, but the other is
454 not, because it is a constant, this is a case that the
455 internal updating code of swap_tree_operands can't handle
457 if (TREE_CODE_CLASS (TREE_CODE (op0
))
458 != TREE_CODE_CLASS (TREE_CODE (op1
)))
459 update_stmt (condstmt
);
464 /* Initialize local stacks for this optimizer and record equivalences
465 upon entry to BB. Equivalences can come from the edge traversed to
466 reach BB or they may come from PHI nodes at the start of BB. */
469 dom_opt_initialize_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
472 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
473 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
475 /* Push a marker on the stacks of local information so that we know how
476 far to unwind when we finalize this block. */
477 VEC_safe_push (tree
, heap
, avail_exprs_stack
, NULL_TREE
);
478 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
480 record_equivalences_from_incoming_edge (bb
);
482 /* PHI nodes can create equivalences too. */
483 record_equivalences_from_phis (bb
);
486 /* Given an expression EXPR (a relational expression or a statement),
487 initialize the hash table element pointed to by ELEMENT. */
490 initialize_hash_element (tree expr
, tree lhs
, struct expr_hash_elt
*element
)
492 /* Hash table elements may be based on conditional expressions or statements.
494 For the former case, we have no annotation and we want to hash the
495 conditional expression. In the latter case we have an annotation and
496 we want to record the expression the statement evaluates. */
497 if (COMPARISON_CLASS_P (expr
) || TREE_CODE (expr
) == TRUTH_NOT_EXPR
)
499 element
->stmt
= NULL
;
502 else if (TREE_CODE (expr
) == COND_EXPR
)
504 element
->stmt
= expr
;
505 element
->rhs
= COND_EXPR_COND (expr
);
507 else if (TREE_CODE (expr
) == SWITCH_EXPR
)
509 element
->stmt
= expr
;
510 element
->rhs
= SWITCH_COND (expr
);
512 else if (TREE_CODE (expr
) == RETURN_EXPR
&& TREE_OPERAND (expr
, 0))
514 element
->stmt
= expr
;
515 element
->rhs
= GIMPLE_STMT_OPERAND (TREE_OPERAND (expr
, 0), 1);
517 else if (TREE_CODE (expr
) == GOTO_EXPR
)
519 element
->stmt
= expr
;
520 element
->rhs
= GOTO_DESTINATION (expr
);
524 element
->stmt
= expr
;
525 element
->rhs
= GENERIC_TREE_OPERAND (expr
, 1);
529 element
->hash
= avail_expr_hash (element
);
532 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
533 LIMIT entries left in LOCALs. */
536 remove_local_expressions_from_table (void)
538 /* Remove all the expressions made available in this block. */
539 while (VEC_length (tree
, avail_exprs_stack
) > 0)
541 struct expr_hash_elt element
;
542 tree expr
= VEC_pop (tree
, avail_exprs_stack
);
544 if (expr
== NULL_TREE
)
547 initialize_hash_element (expr
, NULL
, &element
);
548 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
552 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
553 CONST_AND_COPIES to its original state, stopping when we hit a
557 restore_vars_to_original_value (void)
559 while (VEC_length (tree
, const_and_copies_stack
) > 0)
561 tree prev_value
, dest
;
563 dest
= VEC_pop (tree
, const_and_copies_stack
);
568 prev_value
= VEC_pop (tree
, const_and_copies_stack
);
569 SSA_NAME_VALUE (dest
) = prev_value
;
573 /* A trivial wrapper so that we can present the generic jump
574 threading code with a simple API for simplifying statements. */
576 simplify_stmt_for_jump_threading (tree stmt
, tree within_stmt ATTRIBUTE_UNUSED
)
578 return lookup_avail_expr (stmt
, false);
581 /* Wrapper for common code to attempt to thread an edge. For example,
582 it handles lazily building the dummy condition and the bookkeeping
583 when jump threading is successful. */
586 dom_thread_across_edge (struct dom_walk_data
*walk_data
, edge e
)
588 /* If we don't already have a dummy condition, build it now. */
589 if (! walk_data
->global_data
)
591 tree dummy_cond
= build2 (NE_EXPR
, boolean_type_node
,
592 integer_zero_node
, integer_zero_node
);
593 dummy_cond
= build3 (COND_EXPR
, void_type_node
, dummy_cond
, NULL
, NULL
);
594 walk_data
->global_data
= dummy_cond
;
597 thread_across_edge ((tree
) walk_data
->global_data
, e
, false,
598 &const_and_copies_stack
,
599 simplify_stmt_for_jump_threading
);
602 /* We have finished processing the dominator children of BB, perform
603 any finalization actions in preparation for leaving this node in
604 the dominator tree. */
607 dom_opt_finalize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
612 /* If we have an outgoing edge to a block with multiple incoming and
613 outgoing edges, then we may be able to thread the edge, i.e., we
614 may be able to statically determine which of the outgoing edges
615 will be traversed when the incoming edge from BB is traversed. */
616 if (single_succ_p (bb
)
617 && (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
) == 0
618 && potentially_threadable_block (single_succ (bb
)))
620 dom_thread_across_edge (walk_data
, single_succ_edge (bb
));
622 else if ((last
= last_stmt (bb
))
623 && TREE_CODE (last
) == COND_EXPR
624 && (COMPARISON_CLASS_P (COND_EXPR_COND (last
))
625 || TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
)
626 && EDGE_COUNT (bb
->succs
) == 2
627 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
628 && (EDGE_SUCC (bb
, 1)->flags
& EDGE_ABNORMAL
) == 0)
630 edge true_edge
, false_edge
;
632 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
634 /* Only try to thread the edge if it reaches a target block with
635 more than one predecessor and more than one successor. */
636 if (potentially_threadable_block (true_edge
->dest
))
638 struct edge_info
*edge_info
;
641 /* Push a marker onto the available expression stack so that we
642 unwind any expressions related to the TRUE arm before processing
643 the false arm below. */
644 VEC_safe_push (tree
, heap
, avail_exprs_stack
, NULL_TREE
);
645 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
647 edge_info
= (struct edge_info
*) true_edge
->aux
;
649 /* If we have info associated with this edge, record it into
650 our equivalency tables. */
653 tree
*cond_equivalences
= edge_info
->cond_equivalences
;
654 tree lhs
= edge_info
->lhs
;
655 tree rhs
= edge_info
->rhs
;
657 /* If we have a simple NAME = VALUE equivalency record it. */
658 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
659 record_const_or_copy (lhs
, rhs
);
661 /* If we have 0 = COND or 1 = COND equivalences, record them
662 into our expression hash tables. */
663 if (cond_equivalences
)
664 for (i
= 0; i
< edge_info
->max_cond_equivalences
; i
+= 2)
666 tree expr
= cond_equivalences
[i
];
667 tree value
= cond_equivalences
[i
+ 1];
669 record_cond (expr
, value
);
673 dom_thread_across_edge (walk_data
, true_edge
);
675 /* And restore the various tables to their state before
676 we threaded this edge. */
677 remove_local_expressions_from_table ();
680 /* Similarly for the ELSE arm. */
681 if (potentially_threadable_block (false_edge
->dest
))
683 struct edge_info
*edge_info
;
686 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
687 edge_info
= (struct edge_info
*) false_edge
->aux
;
689 /* If we have info associated with this edge, record it into
690 our equivalency tables. */
693 tree
*cond_equivalences
= edge_info
->cond_equivalences
;
694 tree lhs
= edge_info
->lhs
;
695 tree rhs
= edge_info
->rhs
;
697 /* If we have a simple NAME = VALUE equivalency record it. */
698 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
699 record_const_or_copy (lhs
, rhs
);
701 /* If we have 0 = COND or 1 = COND equivalences, record them
702 into our expression hash tables. */
703 if (cond_equivalences
)
704 for (i
= 0; i
< edge_info
->max_cond_equivalences
; i
+= 2)
706 tree expr
= cond_equivalences
[i
];
707 tree value
= cond_equivalences
[i
+ 1];
709 record_cond (expr
, value
);
713 /* Now thread the edge. */
714 dom_thread_across_edge (walk_data
, false_edge
);
716 /* No need to remove local expressions from our tables
717 or restore vars to their original value as that will
718 be done immediately below. */
722 remove_local_expressions_from_table ();
723 restore_vars_to_original_value ();
725 /* If we queued any statements to rescan in this block, then
726 go ahead and rescan them now. */
727 while (VEC_length (tree_p
, stmts_to_rescan
) > 0)
729 tree
*stmt_p
= VEC_last (tree_p
, stmts_to_rescan
);
731 basic_block stmt_bb
= bb_for_stmt (stmt
);
736 VEC_pop (tree_p
, stmts_to_rescan
);
737 pop_stmt_changes (stmt_p
);
741 /* PHI nodes can create equivalences too.
743 Ignoring any alternatives which are the same as the result, if
744 all the alternatives are equal, then the PHI node creates an
748 record_equivalences_from_phis (basic_block bb
)
752 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
754 tree lhs
= PHI_RESULT (phi
);
758 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
760 tree t
= PHI_ARG_DEF (phi
, i
);
762 /* Ignore alternatives which are the same as our LHS. Since
763 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
764 can simply compare pointers. */
768 /* If we have not processed an alternative yet, then set
769 RHS to this alternative. */
772 /* If we have processed an alternative (stored in RHS), then
773 see if it is equal to this one. If it isn't, then stop
775 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
779 /* If we had no interesting alternatives, then all the RHS alternatives
780 must have been the same as LHS. */
784 /* If we managed to iterate through each PHI alternative without
785 breaking out of the loop, then we have a PHI which may create
786 a useful equivalence. We do not need to record unwind data for
787 this, since this is a true assignment and not an equivalence
788 inferred from a comparison. All uses of this ssa name are dominated
789 by this assignment, so unwinding just costs time and space. */
790 if (i
== PHI_NUM_ARGS (phi
)
791 && may_propagate_copy (lhs
, rhs
))
792 SSA_NAME_VALUE (lhs
) = rhs
;
796 /* Ignoring loop backedges, if BB has precisely one incoming edge then
797 return that edge. Otherwise return NULL. */
799 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
805 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
807 /* A loop back edge can be identified by the destination of
808 the edge dominating the source of the edge. */
809 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
812 /* If we have already seen a non-loop edge, then we must have
813 multiple incoming non-loop edges and thus we return NULL. */
817 /* This is the first non-loop incoming edge we have found. Record
825 /* Record any equivalences created by the incoming edge to BB. If BB
826 has more than one incoming edge, then no equivalence is created. */
829 record_equivalences_from_incoming_edge (basic_block bb
)
833 struct edge_info
*edge_info
;
835 /* If our parent block ended with a control statement, then we may be
836 able to record some equivalences based on which outgoing edge from
837 the parent was followed. */
838 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
840 e
= single_incoming_edge_ignoring_loop_edges (bb
);
842 /* If we had a single incoming edge from our parent block, then enter
843 any data associated with the edge into our tables. */
844 if (e
&& e
->src
== parent
)
848 edge_info
= (struct edge_info
*) e
->aux
;
852 tree lhs
= edge_info
->lhs
;
853 tree rhs
= edge_info
->rhs
;
854 tree
*cond_equivalences
= edge_info
->cond_equivalences
;
857 record_equality (lhs
, rhs
);
859 if (cond_equivalences
)
861 for (i
= 0; i
< edge_info
->max_cond_equivalences
; i
+= 2)
863 tree expr
= cond_equivalences
[i
];
864 tree value
= cond_equivalences
[i
+ 1];
866 record_cond (expr
, value
);
873 /* Dump SSA statistics on FILE. */
876 dump_dominator_optimization_stats (FILE *file
)
878 fprintf (file
, "Total number of statements: %6ld\n\n",
879 opt_stats
.num_stmts
);
880 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
881 opt_stats
.num_exprs_considered
);
883 fprintf (file
, "\nHash table statistics:\n");
885 fprintf (file
, " avail_exprs: ");
886 htab_statistics (file
, avail_exprs
);
890 /* Dump SSA statistics on stderr. */
893 debug_dominator_optimization_stats (void)
895 dump_dominator_optimization_stats (stderr
);
899 /* Dump statistics for the hash table HTAB. */
902 htab_statistics (FILE *file
, htab_t htab
)
904 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
905 (long) htab_size (htab
),
906 (long) htab_elements (htab
),
907 htab_collisions (htab
));
910 /* Enter a statement into the true/false expression hash table indicating
911 that the condition COND has the value VALUE. */
914 record_cond (tree cond
, tree value
)
916 struct expr_hash_elt
*element
= XCNEW (struct expr_hash_elt
);
919 initialize_hash_element (cond
, value
, element
);
921 slot
= htab_find_slot_with_hash (avail_exprs
, (void *)element
,
922 element
->hash
, INSERT
);
925 *slot
= (void *) element
;
926 VEC_safe_push (tree
, heap
, avail_exprs_stack
, cond
);
932 /* Build a new conditional using NEW_CODE, OP0 and OP1 and store
933 the new conditional into *p, then store a boolean_true_node
937 build_and_record_new_cond (enum tree_code new_code
, tree op0
, tree op1
, tree
*p
)
939 *p
= build2 (new_code
, boolean_type_node
, op0
, op1
);
941 *p
= boolean_true_node
;
944 /* Record that COND is true and INVERTED is false into the edge information
945 structure. Also record that any conditions dominated by COND are true
948 For example, if a < b is true, then a <= b must also be true. */
951 record_conditions (struct edge_info
*edge_info
, tree cond
, tree inverted
)
955 if (!COMPARISON_CLASS_P (cond
))
958 op0
= TREE_OPERAND (cond
, 0);
959 op1
= TREE_OPERAND (cond
, 1);
961 switch (TREE_CODE (cond
))
965 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
967 edge_info
->max_cond_equivalences
= 12;
968 edge_info
->cond_equivalences
= XNEWVEC (tree
, 12);
969 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
970 &edge_info
->cond_equivalences
[8]);
971 build_and_record_new_cond (LTGT_EXPR
, op0
, op1
,
972 &edge_info
->cond_equivalences
[10]);
976 edge_info
->max_cond_equivalences
= 8;
977 edge_info
->cond_equivalences
= XNEWVEC (tree
, 8);
980 build_and_record_new_cond ((TREE_CODE (cond
) == LT_EXPR
981 ? LE_EXPR
: GE_EXPR
),
982 op0
, op1
, &edge_info
->cond_equivalences
[4]);
983 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
984 &edge_info
->cond_equivalences
[6]);
989 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
991 edge_info
->max_cond_equivalences
= 6;
992 edge_info
->cond_equivalences
= XNEWVEC (tree
, 6);
993 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
994 &edge_info
->cond_equivalences
[4]);
998 edge_info
->max_cond_equivalences
= 4;
999 edge_info
->cond_equivalences
= XNEWVEC (tree
, 4);
1004 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1006 edge_info
->max_cond_equivalences
= 10;
1007 edge_info
->cond_equivalences
= XNEWVEC (tree
, 10);
1008 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1009 &edge_info
->cond_equivalences
[8]);
1013 edge_info
->max_cond_equivalences
= 8;
1014 edge_info
->cond_equivalences
= XNEWVEC (tree
, 8);
1016 build_and_record_new_cond (LE_EXPR
, op0
, op1
,
1017 &edge_info
->cond_equivalences
[4]);
1018 build_and_record_new_cond (GE_EXPR
, op0
, op1
,
1019 &edge_info
->cond_equivalences
[6]);
1022 case UNORDERED_EXPR
:
1023 edge_info
->max_cond_equivalences
= 16;
1024 edge_info
->cond_equivalences
= XNEWVEC (tree
, 16);
1025 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1026 &edge_info
->cond_equivalences
[4]);
1027 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1028 &edge_info
->cond_equivalences
[6]);
1029 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1030 &edge_info
->cond_equivalences
[8]);
1031 build_and_record_new_cond (UNEQ_EXPR
, op0
, op1
,
1032 &edge_info
->cond_equivalences
[10]);
1033 build_and_record_new_cond (UNLT_EXPR
, op0
, op1
,
1034 &edge_info
->cond_equivalences
[12]);
1035 build_and_record_new_cond (UNGT_EXPR
, op0
, op1
,
1036 &edge_info
->cond_equivalences
[14]);
1041 edge_info
->max_cond_equivalences
= 8;
1042 edge_info
->cond_equivalences
= XNEWVEC (tree
, 8);
1043 build_and_record_new_cond ((TREE_CODE (cond
) == UNLT_EXPR
1044 ? UNLE_EXPR
: UNGE_EXPR
),
1045 op0
, op1
, &edge_info
->cond_equivalences
[4]);
1046 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1047 &edge_info
->cond_equivalences
[6]);
1051 edge_info
->max_cond_equivalences
= 8;
1052 edge_info
->cond_equivalences
= XNEWVEC (tree
, 8);
1053 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1054 &edge_info
->cond_equivalences
[4]);
1055 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1056 &edge_info
->cond_equivalences
[6]);
1060 edge_info
->max_cond_equivalences
= 8;
1061 edge_info
->cond_equivalences
= XNEWVEC (tree
, 8);
1062 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1063 &edge_info
->cond_equivalences
[4]);
1064 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1065 &edge_info
->cond_equivalences
[6]);
1069 edge_info
->max_cond_equivalences
= 4;
1070 edge_info
->cond_equivalences
= XNEWVEC (tree
, 4);
1074 /* Now store the original true and false conditions into the first
1076 edge_info
->cond_equivalences
[0] = cond
;
1077 edge_info
->cond_equivalences
[1] = boolean_true_node
;
1078 edge_info
->cond_equivalences
[2] = inverted
;
1079 edge_info
->cond_equivalences
[3] = boolean_false_node
;
1082 /* A helper function for record_const_or_copy and record_equality.
1083 Do the work of recording the value and undo info. */
1086 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
)
1088 SSA_NAME_VALUE (x
) = y
;
1090 VEC_reserve (tree
, heap
, const_and_copies_stack
, 2);
1091 VEC_quick_push (tree
, const_and_copies_stack
, prev_x
);
1092 VEC_quick_push (tree
, const_and_copies_stack
, x
);
1096 /* Return the loop depth of the basic block of the defining statement of X.
1097 This number should not be treated as absolutely correct because the loop
1098 information may not be completely up-to-date when dom runs. However, it
1099 will be relatively correct, and as more passes are taught to keep loop info
1100 up to date, the result will become more and more accurate. */
1103 loop_depth_of_name (tree x
)
1108 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1109 if (TREE_CODE (x
) != SSA_NAME
)
1112 /* Otherwise return the loop depth of the defining statement's bb.
1113 Note that there may not actually be a bb for this statement, if the
1114 ssa_name is live on entry. */
1115 defstmt
= SSA_NAME_DEF_STMT (x
);
1116 defbb
= bb_for_stmt (defstmt
);
1120 return defbb
->loop_depth
;
1124 /* Record that X is equal to Y in const_and_copies. Record undo
1125 information in the block-local vector. */
1128 record_const_or_copy (tree x
, tree y
)
1130 tree prev_x
= SSA_NAME_VALUE (x
);
1132 if (TREE_CODE (y
) == SSA_NAME
)
1134 tree tmp
= SSA_NAME_VALUE (y
);
1139 record_const_or_copy_1 (x
, y
, prev_x
);
1142 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1143 This constrains the cases in which we may treat this as assignment. */
1146 record_equality (tree x
, tree y
)
1148 tree prev_x
= NULL
, prev_y
= NULL
;
1150 if (TREE_CODE (x
) == SSA_NAME
)
1151 prev_x
= SSA_NAME_VALUE (x
);
1152 if (TREE_CODE (y
) == SSA_NAME
)
1153 prev_y
= SSA_NAME_VALUE (y
);
1155 /* If one of the previous values is invariant, or invariant in more loops
1156 (by depth), then use that.
1157 Otherwise it doesn't matter which value we choose, just so
1158 long as we canonicalize on one value. */
1159 if (is_gimple_min_invariant (y
))
1161 else if (is_gimple_min_invariant (x
)
1162 || (loop_depth_of_name (x
) <= loop_depth_of_name (y
)))
1163 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1164 else if (prev_x
&& is_gimple_min_invariant (prev_x
))
1165 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1169 /* After the swapping, we must have one SSA_NAME. */
1170 if (TREE_CODE (x
) != SSA_NAME
)
1173 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1174 variable compared against zero. If we're honoring signed zeros,
1175 then we cannot record this value unless we know that the value is
1177 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1178 && (TREE_CODE (y
) != REAL_CST
1179 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1182 record_const_or_copy_1 (x
, y
, prev_x
);
1185 /* Returns true when STMT is a simple iv increment. It detects the
1186 following situation:
1188 i_1 = phi (..., i_2)
1189 i_2 = i_1 +/- ... */
1192 simple_iv_increment_p (tree stmt
)
1194 tree lhs
, rhs
, preinc
, phi
;
1197 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
1200 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1201 if (TREE_CODE (lhs
) != SSA_NAME
)
1204 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1206 if (TREE_CODE (rhs
) != PLUS_EXPR
1207 && TREE_CODE (rhs
) != MINUS_EXPR
)
1210 preinc
= TREE_OPERAND (rhs
, 0);
1211 if (TREE_CODE (preinc
) != SSA_NAME
)
1214 phi
= SSA_NAME_DEF_STMT (preinc
);
1215 if (TREE_CODE (phi
) != PHI_NODE
)
1218 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1219 if (PHI_ARG_DEF (phi
, i
) == lhs
)
1225 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1226 known value for that SSA_NAME (or NULL if no value is known).
1228 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1229 successors of BB. */
1232 cprop_into_successor_phis (basic_block bb
)
1237 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1242 /* If this is an abnormal edge, then we do not want to copy propagate
1243 into the PHI alternative associated with this edge. */
1244 if (e
->flags
& EDGE_ABNORMAL
)
1247 phi
= phi_nodes (e
->dest
);
1252 for ( ; phi
; phi
= PHI_CHAIN (phi
))
1255 use_operand_p orig_p
;
1258 /* The alternative may be associated with a constant, so verify
1259 it is an SSA_NAME before doing anything with it. */
1260 orig_p
= PHI_ARG_DEF_PTR (phi
, indx
);
1261 orig_val
= USE_FROM_PTR (orig_p
);
1262 if (TREE_CODE (orig_val
) != SSA_NAME
)
1265 /* If we have *ORIG_P in our constant/copy table, then replace
1266 ORIG_P with its value in our constant/copy table. */
1267 new_val
= SSA_NAME_VALUE (orig_val
);
1269 && new_val
!= orig_val
1270 && (TREE_CODE (new_val
) == SSA_NAME
1271 || is_gimple_min_invariant (new_val
))
1272 && may_propagate_copy (orig_val
, new_val
))
1273 propagate_value (orig_p
, new_val
);
1278 /* We have finished optimizing BB, record any information implied by
1279 taking a specific outgoing edge from BB. */
1282 record_edge_info (basic_block bb
)
1284 block_stmt_iterator bsi
= bsi_last (bb
);
1285 struct edge_info
*edge_info
;
1287 if (! bsi_end_p (bsi
))
1289 tree stmt
= bsi_stmt (bsi
);
1291 if (stmt
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
1293 tree cond
= SWITCH_COND (stmt
);
1295 if (TREE_CODE (cond
) == SSA_NAME
)
1297 tree labels
= SWITCH_LABELS (stmt
);
1298 int i
, n_labels
= TREE_VEC_LENGTH (labels
);
1299 tree
*info
= XCNEWVEC (tree
, last_basic_block
);
1303 for (i
= 0; i
< n_labels
; i
++)
1305 tree label
= TREE_VEC_ELT (labels
, i
);
1306 basic_block target_bb
= label_to_block (CASE_LABEL (label
));
1308 if (CASE_HIGH (label
)
1309 || !CASE_LOW (label
)
1310 || info
[target_bb
->index
])
1311 info
[target_bb
->index
] = error_mark_node
;
1313 info
[target_bb
->index
] = label
;
1316 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1318 basic_block target_bb
= e
->dest
;
1319 tree node
= info
[target_bb
->index
];
1321 if (node
!= NULL
&& node
!= error_mark_node
)
1323 tree x
= fold_convert (TREE_TYPE (cond
), CASE_LOW (node
));
1324 edge_info
= allocate_edge_info (e
);
1325 edge_info
->lhs
= cond
;
1333 /* A COND_EXPR may create equivalences too. */
1334 if (stmt
&& TREE_CODE (stmt
) == COND_EXPR
)
1336 tree cond
= COND_EXPR_COND (stmt
);
1340 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1342 /* If the conditional is a single variable 'X', record 'X = 1'
1343 for the true edge and 'X = 0' on the false edge. */
1344 if (SSA_VAR_P (cond
))
1346 struct edge_info
*edge_info
;
1348 edge_info
= allocate_edge_info (true_edge
);
1349 edge_info
->lhs
= cond
;
1350 edge_info
->rhs
= constant_boolean_node (1, TREE_TYPE (cond
));
1352 edge_info
= allocate_edge_info (false_edge
);
1353 edge_info
->lhs
= cond
;
1354 edge_info
->rhs
= constant_boolean_node (0, TREE_TYPE (cond
));
1356 /* Equality tests may create one or two equivalences. */
1357 else if (COMPARISON_CLASS_P (cond
))
1359 tree op0
= TREE_OPERAND (cond
, 0);
1360 tree op1
= TREE_OPERAND (cond
, 1);
1362 /* Special case comparing booleans against a constant as we
1363 know the value of OP0 on both arms of the branch, i.e., we
1364 can record an equivalence for OP0 rather than COND. */
1365 if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
1366 && TREE_CODE (op0
) == SSA_NAME
1367 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
1368 && is_gimple_min_invariant (op1
))
1370 if (TREE_CODE (cond
) == EQ_EXPR
)
1372 edge_info
= allocate_edge_info (true_edge
);
1373 edge_info
->lhs
= op0
;
1374 edge_info
->rhs
= (integer_zerop (op1
)
1375 ? boolean_false_node
1376 : boolean_true_node
);
1378 edge_info
= allocate_edge_info (false_edge
);
1379 edge_info
->lhs
= op0
;
1380 edge_info
->rhs
= (integer_zerop (op1
)
1382 : boolean_false_node
);
1386 edge_info
= allocate_edge_info (true_edge
);
1387 edge_info
->lhs
= op0
;
1388 edge_info
->rhs
= (integer_zerop (op1
)
1390 : boolean_false_node
);
1392 edge_info
= allocate_edge_info (false_edge
);
1393 edge_info
->lhs
= op0
;
1394 edge_info
->rhs
= (integer_zerop (op1
)
1395 ? boolean_false_node
1396 : boolean_true_node
);
1400 else if (is_gimple_min_invariant (op0
)
1401 && (TREE_CODE (op1
) == SSA_NAME
1402 || is_gimple_min_invariant (op1
)))
1404 tree inverted
= invert_truthvalue (cond
);
1405 struct edge_info
*edge_info
;
1407 edge_info
= allocate_edge_info (true_edge
);
1408 record_conditions (edge_info
, cond
, inverted
);
1410 if (TREE_CODE (cond
) == EQ_EXPR
)
1412 edge_info
->lhs
= op1
;
1413 edge_info
->rhs
= op0
;
1416 edge_info
= allocate_edge_info (false_edge
);
1417 record_conditions (edge_info
, inverted
, cond
);
1419 if (TREE_CODE (cond
) == NE_EXPR
)
1421 edge_info
->lhs
= op1
;
1422 edge_info
->rhs
= op0
;
1426 else if (TREE_CODE (op0
) == SSA_NAME
1427 && (is_gimple_min_invariant (op1
)
1428 || TREE_CODE (op1
) == SSA_NAME
))
1430 tree inverted
= invert_truthvalue (cond
);
1431 struct edge_info
*edge_info
;
1433 edge_info
= allocate_edge_info (true_edge
);
1434 record_conditions (edge_info
, cond
, inverted
);
1436 if (TREE_CODE (cond
) == EQ_EXPR
)
1438 edge_info
->lhs
= op0
;
1439 edge_info
->rhs
= op1
;
1442 edge_info
= allocate_edge_info (false_edge
);
1443 record_conditions (edge_info
, inverted
, cond
);
1445 if (TREE_CODE (cond
) == NE_EXPR
)
1447 edge_info
->lhs
= op0
;
1448 edge_info
->rhs
= op1
;
1453 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1458 /* Propagate information from BB to its outgoing edges.
1460 This can include equivalency information implied by control statements
1461 at the end of BB and const/copy propagation into PHIs in BB's
1462 successor blocks. */
1465 propagate_to_outgoing_edges (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1468 record_edge_info (bb
);
1469 cprop_into_successor_phis (bb
);
1472 /* Search for redundant computations in STMT. If any are found, then
1473 replace them with the variable holding the result of the computation.
1475 If safe, record this expression into the available expression hash
1479 eliminate_redundant_computations (tree stmt
)
1481 tree
*expr_p
, def
= NULL_TREE
;
1484 bool retval
= false;
1485 bool modify_expr_p
= false;
1487 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1488 def
= GIMPLE_STMT_OPERAND (stmt
, 0);
1490 /* Certain expressions on the RHS can be optimized away, but can not
1491 themselves be entered into the hash tables. */
1493 || TREE_CODE (def
) != SSA_NAME
1494 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
1495 || !ZERO_SSA_OPERANDS (stmt
, SSA_OP_VDEF
)
1496 /* Do not record equivalences for increments of ivs. This would create
1497 overlapping live ranges for a very questionable gain. */
1498 || simple_iv_increment_p (stmt
))
1501 /* Check if the expression has been computed before. */
1502 cached_lhs
= lookup_avail_expr (stmt
, insert
);
1504 opt_stats
.num_exprs_considered
++;
1506 /* Get a pointer to the expression we are trying to optimize. */
1507 if (TREE_CODE (stmt
) == COND_EXPR
)
1508 expr_p
= &COND_EXPR_COND (stmt
);
1509 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
1510 expr_p
= &SWITCH_COND (stmt
);
1511 else if (TREE_CODE (stmt
) == RETURN_EXPR
&& TREE_OPERAND (stmt
, 0))
1513 expr_p
= &GIMPLE_STMT_OPERAND (TREE_OPERAND (stmt
, 0), 1);
1514 modify_expr_p
= true;
1518 expr_p
= &GENERIC_TREE_OPERAND (stmt
, 1);
1519 modify_expr_p
= true;
1522 /* It is safe to ignore types here since we have already done
1523 type checking in the hashing and equality routines. In fact
1524 type checking here merely gets in the way of constant
1525 propagation. Also, make sure that it is safe to propagate
1526 CACHED_LHS into *EXPR_P. */
1528 && ((TREE_CODE (cached_lhs
) != SSA_NAME
1530 || useless_type_conversion_p (TREE_TYPE (*expr_p
),
1531 TREE_TYPE (cached_lhs
))))
1532 || may_propagate_copy (*expr_p
, cached_lhs
)))
1534 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1536 fprintf (dump_file
, " Replaced redundant expr '");
1537 print_generic_expr (dump_file
, *expr_p
, dump_flags
);
1538 fprintf (dump_file
, "' with '");
1539 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
1540 fprintf (dump_file
, "'\n");
1545 #if defined ENABLE_CHECKING
1546 gcc_assert (TREE_CODE (cached_lhs
) == SSA_NAME
1547 || is_gimple_min_invariant (cached_lhs
));
1550 if (TREE_CODE (cached_lhs
) == ADDR_EXPR
1551 || (POINTER_TYPE_P (TREE_TYPE (*expr_p
))
1552 && is_gimple_min_invariant (cached_lhs
)))
1556 && !useless_type_conversion_p (TREE_TYPE (*expr_p
),
1557 TREE_TYPE (cached_lhs
)))
1558 cached_lhs
= fold_convert (TREE_TYPE (*expr_p
), cached_lhs
);
1560 propagate_tree_value (expr_p
, cached_lhs
);
1561 mark_stmt_modified (stmt
);
1566 /* STMT, a GIMPLE_MODIFY_STMT, may create certain equivalences, in either
1567 the available expressions table or the const_and_copies table.
1568 Detect and record those equivalences. */
1571 record_equivalences_from_stmt (tree stmt
, int may_optimize_p
, stmt_ann_t ann
)
1573 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1574 enum tree_code lhs_code
= TREE_CODE (lhs
);
1576 if (lhs_code
== SSA_NAME
)
1578 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1580 /* Strip away any useless type conversions. */
1581 STRIP_USELESS_TYPE_CONVERSION (rhs
);
1583 /* If the RHS of the assignment is a constant or another variable that
1584 may be propagated, register it in the CONST_AND_COPIES table. We
1585 do not need to record unwind data for this, since this is a true
1586 assignment and not an equivalence inferred from a comparison. All
1587 uses of this ssa name are dominated by this assignment, so unwinding
1588 just costs time and space. */
1590 && (TREE_CODE (rhs
) == SSA_NAME
1591 || is_gimple_min_invariant (rhs
)))
1592 SSA_NAME_VALUE (lhs
) = rhs
;
1595 /* A memory store, even an aliased store, creates a useful
1596 equivalence. By exchanging the LHS and RHS, creating suitable
1597 vops and recording the result in the available expression table,
1598 we may be able to expose more redundant loads. */
1599 if (!ann
->has_volatile_ops
1600 && stmt_references_memory_p (stmt
)
1601 && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == SSA_NAME
1602 || is_gimple_min_invariant (GIMPLE_STMT_OPERAND (stmt
, 1)))
1603 && !is_gimple_reg (lhs
))
1605 tree rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1608 /* Build a new statement with the RHS and LHS exchanged. */
1609 new_stmt
= build_gimple_modify_stmt (rhs
, lhs
);
1610 create_ssa_artificial_load_stmt (new_stmt
, stmt
, true);
1612 /* Finally enter the statement into the available expression
1614 lookup_avail_expr (new_stmt
, true);
1618 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1619 CONST_AND_COPIES. */
1622 cprop_operand (tree stmt
, use_operand_p op_p
)
1624 bool may_have_exposed_new_symbols
= false;
1626 tree op
= USE_FROM_PTR (op_p
);
1628 /* If the operand has a known constant value or it is known to be a
1629 copy of some other variable, use the value or copy stored in
1630 CONST_AND_COPIES. */
1631 val
= SSA_NAME_VALUE (op
);
1632 if (val
&& val
!= op
)
1634 tree op_type
, val_type
;
1636 /* Do not change the base variable in the virtual operand
1637 tables. That would make it impossible to reconstruct
1638 the renamed virtual operand if we later modify this
1639 statement. Also only allow the new value to be an SSA_NAME
1640 for propagation into virtual operands. */
1641 if (!is_gimple_reg (op
)
1642 && (TREE_CODE (val
) != SSA_NAME
1643 || is_gimple_reg (val
)
1644 || get_virtual_var (val
) != get_virtual_var (op
)))
1647 /* Do not replace hard register operands in asm statements. */
1648 if (TREE_CODE (stmt
) == ASM_EXPR
1649 && !may_propagate_copy_into_asm (op
))
1652 /* Get the toplevel type of each operand. */
1653 op_type
= TREE_TYPE (op
);
1654 val_type
= TREE_TYPE (val
);
1656 /* While both types are pointers, get the type of the object
1658 while (POINTER_TYPE_P (op_type
) && POINTER_TYPE_P (val_type
))
1660 op_type
= TREE_TYPE (op_type
);
1661 val_type
= TREE_TYPE (val_type
);
1664 /* Make sure underlying types match before propagating a constant by
1665 converting the constant to the proper type. Note that convert may
1666 return a non-gimple expression, in which case we ignore this
1667 propagation opportunity. */
1668 if (TREE_CODE (val
) != SSA_NAME
)
1670 if (!useless_type_conversion_p (op_type
, val_type
))
1672 val
= fold_convert (TREE_TYPE (op
), val
);
1673 if (!is_gimple_min_invariant (val
))
1678 /* Certain operands are not allowed to be copy propagated due
1679 to their interaction with exception handling and some GCC
1681 else if (!may_propagate_copy (op
, val
))
1684 /* Do not propagate copies if the propagated value is at a deeper loop
1685 depth than the propagatee. Otherwise, this may move loop variant
1686 variables outside of their loops and prevent coalescing
1687 opportunities. If the value was loop invariant, it will be hoisted
1688 by LICM and exposed for copy propagation. */
1689 if (loop_depth_of_name (val
) > loop_depth_of_name (op
))
1693 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1695 fprintf (dump_file
, " Replaced '");
1696 print_generic_expr (dump_file
, op
, dump_flags
);
1697 fprintf (dump_file
, "' with %s '",
1698 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
1699 print_generic_expr (dump_file
, val
, dump_flags
);
1700 fprintf (dump_file
, "'\n");
1703 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
1704 that we may have exposed a new symbol for SSA renaming. */
1705 if (TREE_CODE (val
) == ADDR_EXPR
1706 || (POINTER_TYPE_P (TREE_TYPE (op
))
1707 && is_gimple_min_invariant (val
)))
1708 may_have_exposed_new_symbols
= true;
1710 if (TREE_CODE (val
) != SSA_NAME
)
1711 opt_stats
.num_const_prop
++;
1713 opt_stats
.num_copy_prop
++;
1715 propagate_value (op_p
, val
);
1717 /* And note that we modified this statement. This is now
1718 safe, even if we changed virtual operands since we will
1719 rescan the statement and rewrite its operands again. */
1720 mark_stmt_modified (stmt
);
1722 return may_have_exposed_new_symbols
;
1725 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1726 known value for that SSA_NAME (or NULL if no value is known).
1728 Propagate values from CONST_AND_COPIES into the uses, vuses and
1729 vdef_ops of STMT. */
1732 cprop_into_stmt (tree stmt
)
1734 bool may_have_exposed_new_symbols
= false;
1738 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1740 if (TREE_CODE (USE_FROM_PTR (op_p
)) == SSA_NAME
)
1741 may_have_exposed_new_symbols
|= cprop_operand (stmt
, op_p
);
1744 return may_have_exposed_new_symbols
;
1748 /* Optimize the statement pointed to by iterator SI.
1750 We try to perform some simplistic global redundancy elimination and
1751 constant propagation:
1753 1- To detect global redundancy, we keep track of expressions that have
1754 been computed in this block and its dominators. If we find that the
1755 same expression is computed more than once, we eliminate repeated
1756 computations by using the target of the first one.
1758 2- Constant values and copy assignments. This is used to do very
1759 simplistic constant and copy propagation. When a constant or copy
1760 assignment is found, we map the value on the RHS of the assignment to
1761 the variable in the LHS in the CONST_AND_COPIES table. */
1764 optimize_stmt (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1765 basic_block bb
, block_stmt_iterator si
)
1768 tree stmt
, old_stmt
;
1769 bool may_optimize_p
;
1770 bool may_have_exposed_new_symbols
= false;
1772 old_stmt
= stmt
= bsi_stmt (si
);
1774 if (TREE_CODE (stmt
) == COND_EXPR
)
1775 canonicalize_comparison (stmt
);
1777 update_stmt_if_modified (stmt
);
1778 ann
= stmt_ann (stmt
);
1779 opt_stats
.num_stmts
++;
1780 may_have_exposed_new_symbols
= false;
1781 push_stmt_changes (bsi_stmt_ptr (si
));
1783 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1785 fprintf (dump_file
, "Optimizing statement ");
1786 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1789 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
1790 may_have_exposed_new_symbols
= cprop_into_stmt (stmt
);
1792 /* If the statement has been modified with constant replacements,
1793 fold its RHS before checking for redundant computations. */
1798 /* Try to fold the statement making sure that STMT is kept
1800 if (fold_stmt (bsi_stmt_ptr (si
)))
1802 stmt
= bsi_stmt (si
);
1803 ann
= stmt_ann (stmt
);
1805 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1807 fprintf (dump_file
, " Folded to: ");
1808 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1812 rhs
= get_rhs (stmt
);
1813 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
1814 recompute_tree_invariant_for_addr_expr (rhs
);
1816 /* Constant/copy propagation above may change the set of
1817 virtual operands associated with this statement. Folding
1818 may remove the need for some virtual operands.
1820 Indicate we will need to rescan and rewrite the statement. */
1821 may_have_exposed_new_symbols
= true;
1824 /* Check for redundant computations. Do this optimization only
1825 for assignments that have no volatile ops and conditionals. */
1826 may_optimize_p
= (!ann
->has_volatile_ops
1827 && ((TREE_CODE (stmt
) == RETURN_EXPR
1828 && TREE_OPERAND (stmt
, 0)
1829 && TREE_CODE (TREE_OPERAND (stmt
, 0))
1830 == GIMPLE_MODIFY_STMT
1831 && ! (TREE_SIDE_EFFECTS
1832 (GIMPLE_STMT_OPERAND
1833 (TREE_OPERAND (stmt
, 0), 1))))
1834 || (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1835 && ! TREE_SIDE_EFFECTS (GIMPLE_STMT_OPERAND (stmt
,
1837 || TREE_CODE (stmt
) == COND_EXPR
1838 || TREE_CODE (stmt
) == SWITCH_EXPR
));
1841 may_have_exposed_new_symbols
|= eliminate_redundant_computations (stmt
);
1843 /* Record any additional equivalences created by this statement. */
1844 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1845 record_equivalences_from_stmt (stmt
, may_optimize_p
, ann
);
1847 /* If STMT is a COND_EXPR and it was modified, then we may know
1848 where it goes. If that is the case, then mark the CFG as altered.
1850 This will cause us to later call remove_unreachable_blocks and
1851 cleanup_tree_cfg when it is safe to do so. It is not safe to
1852 clean things up here since removal of edges and such can trigger
1853 the removal of PHI nodes, which in turn can release SSA_NAMEs to
1856 That's all fine and good, except that once SSA_NAMEs are released
1857 to the manager, we must not call create_ssa_name until all references
1858 to released SSA_NAMEs have been eliminated.
1860 All references to the deleted SSA_NAMEs can not be eliminated until
1861 we remove unreachable blocks.
1863 We can not remove unreachable blocks until after we have completed
1864 any queued jump threading.
1866 We can not complete any queued jump threads until we have taken
1867 appropriate variables out of SSA form. Taking variables out of
1868 SSA form can call create_ssa_name and thus we lose.
1870 Ultimately I suspect we're going to need to change the interface
1871 into the SSA_NAME manager. */
1876 if (TREE_CODE (stmt
) == COND_EXPR
)
1877 val
= COND_EXPR_COND (stmt
);
1878 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
1879 val
= SWITCH_COND (stmt
);
1881 if (val
&& TREE_CODE (val
) == INTEGER_CST
&& find_taken_edge (bb
, val
))
1884 /* If we simplified a statement in such a way as to be shown that it
1885 cannot trap, update the eh information and the cfg to match. */
1886 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
1888 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
1889 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1890 fprintf (dump_file
, " Flagged to clear EH edges.\n");
1894 if (may_have_exposed_new_symbols
)
1896 /* Queue the statement to be re-scanned after all the
1897 AVAIL_EXPRS have been processed. The change buffer stack for
1898 all the pushed statements will be processed when this queue
1900 VEC_safe_push (tree_p
, heap
, stmts_to_rescan
, bsi_stmt_ptr (si
));
1904 /* Otherwise, just discard the recently pushed change buffer. If
1905 not, the STMTS_TO_RESCAN queue will get out of synch with the
1906 change buffer stack. */
1907 discard_stmt_changes (bsi_stmt_ptr (si
));
1911 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
1912 found, return its LHS. Otherwise insert STMT in the table and return
1915 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
1916 is also added to the stack pointed to by BLOCK_AVAIL_EXPRS_P, so that they
1917 can be removed when we finish processing this block and its children.
1919 NOTE: This function assumes that STMT is a GIMPLE_MODIFY_STMT node that
1920 contains no CALL_EXPR on its RHS and makes no volatile nor
1921 aliased references. */
1924 lookup_avail_expr (tree stmt
, bool insert
)
1929 struct expr_hash_elt
*element
= XNEW (struct expr_hash_elt
);
1931 lhs
= TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1932 ? GIMPLE_STMT_OPERAND (stmt
, 0) : NULL
;
1934 initialize_hash_element (stmt
, lhs
, element
);
1936 /* Don't bother remembering constant assignments and copy operations.
1937 Constants and copy operations are handled by the constant/copy propagator
1938 in optimize_stmt. */
1939 if (TREE_CODE (element
->rhs
) == SSA_NAME
1940 || is_gimple_min_invariant (element
->rhs
))
1946 /* Finally try to find the expression in the main expression hash table. */
1947 slot
= htab_find_slot_with_hash (avail_exprs
, element
, element
->hash
,
1948 (insert
? INSERT
: NO_INSERT
));
1957 *slot
= (void *) element
;
1958 VEC_safe_push (tree
, heap
, avail_exprs_stack
,
1959 stmt
? stmt
: element
->rhs
);
1963 /* Extract the LHS of the assignment so that it can be used as the current
1964 definition of another variable. */
1965 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
1967 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
1968 use the value from the const_and_copies table. */
1969 if (TREE_CODE (lhs
) == SSA_NAME
)
1971 temp
= SSA_NAME_VALUE (lhs
);
1980 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
1981 GIMPLE_MODIFY_STMT statements. We compute a value number for expressions
1982 using the code of the expression and the SSA numbers of its operands. */
1985 avail_expr_hash (const void *p
)
1987 tree stmt
= ((const struct expr_hash_elt
*)p
)->stmt
;
1988 tree rhs
= ((const struct expr_hash_elt
*)p
)->rhs
;
1993 /* iterative_hash_expr knows how to deal with any expression and
1994 deals with commutative operators as well, so just use it instead
1995 of duplicating such complexities here. */
1996 val
= iterative_hash_expr (rhs
, val
);
1998 /* If the hash table entry is not associated with a statement, then we
1999 can just hash the expression and not worry about virtual operands
2001 if (!stmt
|| !stmt_ann (stmt
))
2004 /* Add the SSA version numbers of every vuse operand. This is important
2005 because compound variables like arrays are not renamed in the
2006 operands. Rather, the rename is done on the virtual variable
2007 representing all the elements of the array. */
2008 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VUSE
)
2009 val
= iterative_hash_expr (vuse
, val
);
2015 real_avail_expr_hash (const void *p
)
2017 return ((const struct expr_hash_elt
*)p
)->hash
;
2021 avail_expr_eq (const void *p1
, const void *p2
)
2023 tree stmt1
= ((const struct expr_hash_elt
*)p1
)->stmt
;
2024 tree rhs1
= ((const struct expr_hash_elt
*)p1
)->rhs
;
2025 tree stmt2
= ((const struct expr_hash_elt
*)p2
)->stmt
;
2026 tree rhs2
= ((const struct expr_hash_elt
*)p2
)->rhs
;
2028 /* If they are the same physical expression, return true. */
2029 if (rhs1
== rhs2
&& stmt1
== stmt2
)
2032 /* If their codes are not equal, then quit now. */
2033 if (TREE_CODE (rhs1
) != TREE_CODE (rhs2
))
2036 /* In case of a collision, both RHS have to be identical and have the
2037 same VUSE operands. */
2038 if (types_compatible_p (TREE_TYPE (rhs1
), TREE_TYPE (rhs2
))
2039 && operand_equal_p (rhs1
, rhs2
, OEP_PURE_SAME
))
2041 bool ret
= compare_ssa_operands_equal (stmt1
, stmt2
, SSA_OP_VUSE
);
2042 gcc_assert (!ret
|| ((const struct expr_hash_elt
*)p1
)->hash
2043 == ((const struct expr_hash_elt
*)p2
)->hash
);
2050 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2051 up degenerate PHIs created by or exposed by jump threading. */
2053 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2057 degenerate_phi_result (tree phi
)
2059 tree lhs
= PHI_RESULT (phi
);
2063 /* Ignoring arguments which are the same as LHS, if all the remaining
2064 arguments are the same, then the PHI is a degenerate and has the
2065 value of that common argument. */
2066 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
2068 tree arg
= PHI_ARG_DEF (phi
, i
);
2074 else if (!operand_equal_p (arg
, val
, 0))
2077 return (i
== PHI_NUM_ARGS (phi
) ? val
: NULL
);
2080 /* Given a tree node T, which is either a PHI_NODE or GIMPLE_MODIFY_STMT,
2081 remove it from the IL. */
2084 remove_stmt_or_phi (tree t
)
2086 if (TREE_CODE (t
) == PHI_NODE
)
2087 remove_phi_node (t
, NULL
, true);
2090 block_stmt_iterator bsi
= bsi_for_stmt (t
);
2091 bsi_remove (&bsi
, true);
2096 /* Given a tree node T, which is either a PHI_NODE or GIMPLE_MODIFY_STMT,
2097 return the "rhs" of the node, in the case of a non-degenerate
2098 PHI, NULL is returned. */
2101 get_rhs_or_phi_arg (tree t
)
2103 if (TREE_CODE (t
) == PHI_NODE
)
2104 return degenerate_phi_result (t
);
2105 else if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
2106 return GIMPLE_STMT_OPERAND (t
, 1);
2111 /* Given a tree node T, which is either a PHI_NODE or a GIMPLE_MODIFY_STMT,
2112 return the "lhs" of the node. */
2115 get_lhs_or_phi_result (tree t
)
2117 if (TREE_CODE (t
) == PHI_NODE
)
2118 return PHI_RESULT (t
);
2119 else if (TREE_CODE (t
) == GIMPLE_MODIFY_STMT
)
2120 return GIMPLE_STMT_OPERAND (t
, 0);
2124 /* Propagate RHS into all uses of LHS (when possible).
2126 RHS and LHS are derived from STMT, which is passed in solely so
2127 that we can remove it if propagation is successful.
2129 When propagating into a PHI node or into a statement which turns
2130 into a trivial copy or constant initialization, set the
2131 appropriate bit in INTERESTING_NAMEs so that we will visit those
2132 nodes as well in an effort to pick up secondary optimization
2136 propagate_rhs_into_lhs (tree stmt
, tree lhs
, tree rhs
, bitmap interesting_names
)
2138 /* First verify that propagation is valid and isn't going to move a
2139 loop variant variable outside its loop. */
2140 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
)
2141 && (TREE_CODE (rhs
) != SSA_NAME
2142 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
2143 && may_propagate_copy (lhs
, rhs
)
2144 && loop_depth_of_name (lhs
) >= loop_depth_of_name (rhs
))
2146 use_operand_p use_p
;
2147 imm_use_iterator iter
;
2152 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2154 fprintf (dump_file
, " Replacing '");
2155 print_generic_expr (dump_file
, lhs
, dump_flags
);
2156 fprintf (dump_file
, "' with %s '",
2157 (TREE_CODE (rhs
) != SSA_NAME
? "constant" : "variable"));
2158 print_generic_expr (dump_file
, rhs
, dump_flags
);
2159 fprintf (dump_file
, "'\n");
2162 /* Walk over every use of LHS and try to replace the use with RHS.
2163 At this point the only reason why such a propagation would not
2164 be successful would be if the use occurs in an ASM_EXPR. */
2165 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
2168 /* It's not always safe to propagate into an ASM_EXPR. */
2169 if (TREE_CODE (use_stmt
) == ASM_EXPR
2170 && ! may_propagate_copy_into_asm (lhs
))
2177 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2179 fprintf (dump_file
, " Original statement:");
2180 print_generic_expr (dump_file
, use_stmt
, dump_flags
);
2181 fprintf (dump_file
, "\n");
2184 push_stmt_changes (&use_stmt
);
2186 /* Propagate the RHS into this use of the LHS. */
2187 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2188 propagate_value (use_p
, rhs
);
2190 /* Special cases to avoid useless calls into the folding
2191 routines, operand scanning, etc.
2193 First, propagation into a PHI may cause the PHI to become
2194 a degenerate, so mark the PHI as interesting. No other
2195 actions are necessary.
2197 Second, if we're propagating a virtual operand and the
2198 propagation does not change the underlying _DECL node for
2199 the virtual operand, then no further actions are necessary. */
2200 if (TREE_CODE (use_stmt
) == PHI_NODE
2201 || (! is_gimple_reg (lhs
)
2202 && TREE_CODE (rhs
) == SSA_NAME
2203 && SSA_NAME_VAR (lhs
) == SSA_NAME_VAR (rhs
)))
2206 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2208 fprintf (dump_file
, " Updated statement:");
2209 print_generic_expr (dump_file
, use_stmt
, dump_flags
);
2210 fprintf (dump_file
, "\n");
2213 /* Propagation into a PHI may expose new degenerate PHIs,
2214 so mark the result of the PHI as interesting. */
2215 if (TREE_CODE (use_stmt
) == PHI_NODE
)
2217 tree result
= get_lhs_or_phi_result (use_stmt
);
2218 bitmap_set_bit (interesting_names
, SSA_NAME_VERSION (result
));
2221 discard_stmt_changes (&use_stmt
);
2225 /* From this point onward we are propagating into a
2226 real statement. Folding may (or may not) be possible,
2227 we may expose new operands, expose dead EH edges,
2229 fold_stmt_inplace (use_stmt
);
2231 /* Sometimes propagation can expose new operands to the
2232 renamer. Note this will call update_stmt at the
2233 appropriate time. */
2234 pop_stmt_changes (&use_stmt
);
2237 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2239 fprintf (dump_file
, " Updated statement:");
2240 print_generic_expr (dump_file
, use_stmt
, dump_flags
);
2241 fprintf (dump_file
, "\n");
2244 /* If we replaced a variable index with a constant, then
2245 we would need to update the invariant flag for ADDR_EXPRs. */
2246 if (TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
2247 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == ADDR_EXPR
)
2248 recompute_tree_invariant_for_addr_expr
2249 (GIMPLE_STMT_OPERAND (use_stmt
, 1));
2251 /* If we cleaned up EH information from the statement,
2252 mark its containing block as needing EH cleanups. */
2253 if (maybe_clean_or_replace_eh_stmt (use_stmt
, use_stmt
))
2255 bitmap_set_bit (need_eh_cleanup
, bb_for_stmt (use_stmt
)->index
);
2256 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2257 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2260 /* Propagation may expose new trivial copy/constant propagation
2262 if (TREE_CODE (use_stmt
) == GIMPLE_MODIFY_STMT
2263 && TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 0)) == SSA_NAME
2264 && (TREE_CODE (GIMPLE_STMT_OPERAND (use_stmt
, 1)) == SSA_NAME
2265 || is_gimple_min_invariant (GIMPLE_STMT_OPERAND (use_stmt
,
2268 tree result
= get_lhs_or_phi_result (use_stmt
);
2269 bitmap_set_bit (interesting_names
, SSA_NAME_VERSION (result
));
2272 /* Propagation into these nodes may make certain edges in
2273 the CFG unexecutable. We want to identify them as PHI nodes
2274 at the destination of those unexecutable edges may become
2276 else if (TREE_CODE (use_stmt
) == COND_EXPR
2277 || TREE_CODE (use_stmt
) == SWITCH_EXPR
2278 || TREE_CODE (use_stmt
) == GOTO_EXPR
)
2282 if (TREE_CODE (use_stmt
) == COND_EXPR
)
2283 val
= COND_EXPR_COND (use_stmt
);
2284 else if (TREE_CODE (use_stmt
) == SWITCH_EXPR
)
2285 val
= SWITCH_COND (use_stmt
);
2287 val
= GOTO_DESTINATION (use_stmt
);
2289 if (is_gimple_min_invariant (val
))
2291 basic_block bb
= bb_for_stmt (use_stmt
);
2292 edge te
= find_taken_edge (bb
, val
);
2295 block_stmt_iterator bsi
;
2297 /* Remove all outgoing edges except TE. */
2298 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
));)
2304 /* Mark all the PHI nodes at the destination of
2305 the unexecutable edge as interesting. */
2306 for (phi
= phi_nodes (e
->dest
);
2308 phi
= PHI_CHAIN (phi
))
2310 tree result
= PHI_RESULT (phi
);
2311 int version
= SSA_NAME_VERSION (result
);
2313 bitmap_set_bit (interesting_names
, version
);
2316 te
->probability
+= e
->probability
;
2318 te
->count
+= e
->count
;
2326 bsi
= bsi_last (bb_for_stmt (use_stmt
));
2327 bsi_remove (&bsi
, true);
2329 /* And fixup the flags on the single remaining edge. */
2330 te
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
2331 te
->flags
&= ~EDGE_ABNORMAL
;
2332 te
->flags
|= EDGE_FALLTHRU
;
2333 if (te
->probability
> REG_BR_PROB_BASE
)
2334 te
->probability
= REG_BR_PROB_BASE
;
2339 /* Ensure there is nothing else to do. */
2340 gcc_assert (!all
|| has_zero_uses (lhs
));
2342 /* If we were able to propagate away all uses of LHS, then
2343 we can remove STMT. */
2345 remove_stmt_or_phi (stmt
);
2349 /* T is either a PHI node (potentially a degenerate PHI node) or
2350 a statement that is a trivial copy or constant initialization.
2352 Attempt to eliminate T by propagating its RHS into all uses of
2353 its LHS. This may in turn set new bits in INTERESTING_NAMES
2354 for nodes we want to revisit later.
2356 All exit paths should clear INTERESTING_NAMES for the result
2360 eliminate_const_or_copy (tree t
, bitmap interesting_names
)
2362 tree lhs
= get_lhs_or_phi_result (t
);
2364 int version
= SSA_NAME_VERSION (lhs
);
2366 /* If the LHS of this statement or PHI has no uses, then we can
2367 just eliminate it. This can occur if, for example, the PHI
2368 was created by block duplication due to threading and its only
2369 use was in the conditional at the end of the block which was
2371 if (has_zero_uses (lhs
))
2373 bitmap_clear_bit (interesting_names
, version
);
2374 remove_stmt_or_phi (t
);
2378 /* Get the RHS of the assignment or PHI node if the PHI is a
2380 rhs
= get_rhs_or_phi_arg (t
);
2383 bitmap_clear_bit (interesting_names
, version
);
2387 propagate_rhs_into_lhs (t
, lhs
, rhs
, interesting_names
);
2389 /* Note that T may well have been deleted by now, so do
2390 not access it, instead use the saved version # to clear
2391 T's entry in the worklist. */
2392 bitmap_clear_bit (interesting_names
, version
);
2395 /* The first phase in degenerate PHI elimination.
2397 Eliminate the degenerate PHIs in BB, then recurse on the
2398 dominator children of BB. */
2401 eliminate_degenerate_phis_1 (basic_block bb
, bitmap interesting_names
)
2406 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
2408 next
= PHI_CHAIN (phi
);
2409 eliminate_const_or_copy (phi
, interesting_names
);
2412 /* Recurse into the dominator children of BB. */
2413 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2415 son
= next_dom_son (CDI_DOMINATORS
, son
))
2416 eliminate_degenerate_phis_1 (son
, interesting_names
);
2420 /* A very simple pass to eliminate degenerate PHI nodes from the
2421 IL. This is meant to be fast enough to be able to be run several
2422 times in the optimization pipeline.
2424 Certain optimizations, particularly those which duplicate blocks
2425 or remove edges from the CFG can create or expose PHIs which are
2426 trivial copies or constant initializations.
2428 While we could pick up these optimizations in DOM or with the
2429 combination of copy-prop and CCP, those solutions are far too
2430 heavy-weight for our needs.
2432 This implementation has two phases so that we can efficiently
2433 eliminate the first order degenerate PHIs and second order
2436 The first phase performs a dominator walk to identify and eliminate
2437 the vast majority of the degenerate PHIs. When a degenerate PHI
2438 is identified and eliminated any affected statements or PHIs
2439 are put on a worklist.
2441 The second phase eliminates degenerate PHIs and trivial copies
2442 or constant initializations using the worklist. This is how we
2443 pick up the secondary optimization opportunities with minimal
2447 eliminate_degenerate_phis (void)
2449 bitmap interesting_names
;
2450 bitmap interesting_names1
;
2452 /* Bitmap of blocks which need EH information updated. We can not
2453 update it on-the-fly as doing so invalidates the dominator tree. */
2454 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
2456 /* INTERESTING_NAMES is effectively our worklist, indexed by
2459 A set bit indicates that the statement or PHI node which
2460 defines the SSA_NAME should be (re)examined to determine if
2461 it has become a degenerate PHI or trivial const/copy propagation
2464 Experiments have show we generally get better compilation
2465 time behavior with bitmaps rather than sbitmaps. */
2466 interesting_names
= BITMAP_ALLOC (NULL
);
2467 interesting_names1
= BITMAP_ALLOC (NULL
);
2469 calculate_dominance_info (CDI_DOMINATORS
);
2470 cfg_altered
= false;
2472 /* First phase. Eliminate degenerate PHIs via a dominator
2475 Experiments have indicated that we generally get better
2476 compile-time behavior by visiting blocks in the first
2477 phase in dominator order. Presumably this is because walking
2478 in dominator order leaves fewer PHIs for later examination
2479 by the worklist phase. */
2480 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR
, interesting_names
);
2482 /* Second phase. Eliminate second order degenerate PHIs as well
2483 as trivial copies or constant initializations identified by
2484 the first phase or this phase. Basically we keep iterating
2485 until our set of INTERESTING_NAMEs is empty. */
2486 while (!bitmap_empty_p (interesting_names
))
2491 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2492 changed during the loop. Copy it to another bitmap and
2494 bitmap_copy (interesting_names1
, interesting_names
);
2496 EXECUTE_IF_SET_IN_BITMAP (interesting_names1
, 0, i
, bi
)
2498 tree name
= ssa_name (i
);
2500 /* Ignore SSA_NAMEs that have been released because
2501 their defining statement was deleted (unreachable). */
2503 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i
)),
2509 free_dominance_info (CDI_DOMINATORS
);
2511 /* Propagation of const and copies may make some EH edges dead. Purge
2512 such edges from the CFG as needed. */
2513 if (!bitmap_empty_p (need_eh_cleanup
))
2515 tree_purge_all_dead_eh_edges (need_eh_cleanup
);
2516 BITMAP_FREE (need_eh_cleanup
);
2519 BITMAP_FREE (interesting_names
);
2520 BITMAP_FREE (interesting_names1
);
2524 struct gimple_opt_pass pass_phi_only_cprop
=
2528 "phicprop", /* name */
2529 gate_dominator
, /* gate */
2530 eliminate_degenerate_phis
, /* execute */
2533 0, /* static_pass_number */
2534 TV_TREE_PHI_CPROP
, /* tv_id */
2535 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
2536 0, /* properties_provided */
2537 0, /* properties_destroyed */
2538 0, /* todo_flags_start */
2544 | TODO_update_ssa
/* todo_flags_finish */