1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to
20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA. */
25 #include "coretypes.h"
32 #include "basic-block.h"
37 #include "diagnostic.h"
39 #include "tree-dump.h"
40 #include "tree-flow.h"
43 #include "tree-pass.h"
44 #include "tree-ssa-propagate.h"
45 #include "langhooks.h"
48 /* This file implements optimizations on the dominator tree. */
51 /* Structure for recording edge equivalences as well as any pending
52 edge redirections during the dominator optimizer.
54 Computing and storing the edge equivalences instead of creating
55 them on-demand can save significant amounts of time, particularly
56 for pathological cases involving switch statements.
58 These structures live for a single iteration of the dominator
59 optimizer in the edge's AUX field. At the end of an iteration we
60 free each of these structures and update the AUX field to point
61 to any requested redirection target (the code for updating the
62 CFG and SSA graph for edge redirection expects redirection edge
63 targets to be in the AUX field for each edge. */
67 /* If this edge creates a simple equivalence, the LHS and RHS of
68 the equivalence will be stored here. */
72 /* Traversing an edge may also indicate one or more particular conditions
73 are true or false. The number of recorded conditions can vary, but
74 can be determined by the condition's code. So we have an array
75 and its maximum index rather than use a varray. */
76 tree
*cond_equivalences
;
77 unsigned int max_cond_equivalences
;
81 /* Hash table with expressions made available during the renaming process.
82 When an assignment of the form X_i = EXPR is found, the statement is
83 stored in this table. If the same expression EXPR is later found on the
84 RHS of another statement, it is replaced with X_i (thus performing
85 global redundancy elimination). Similarly as we pass through conditionals
86 we record the conditional itself as having either a true or false value
88 static htab_t avail_exprs
;
90 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
91 expressions it enters into the hash table along with a marker entry
92 (null). When we finish processing the block, we pop off entries and
93 remove the expressions from the global hash table until we hit the
95 static VEC(tree
,heap
) *avail_exprs_stack
;
97 /* Stack of statements we need to rescan during finalization for newly
100 Statement rescanning must occur after the current block's available
101 expressions are removed from AVAIL_EXPRS. Else we may change the
102 hash code for an expression and be unable to find/remove it from
104 static VEC(tree
,heap
) *stmts_to_rescan
;
106 /* Structure for entries in the expression hash table.
108 This requires more memory for the hash table entries, but allows us
109 to avoid creating silly tree nodes and annotations for conditionals,
110 eliminates 2 global hash tables and two block local varrays.
112 It also allows us to reduce the number of hash table lookups we
113 have to perform in lookup_avail_expr and finally it allows us to
114 significantly reduce the number of calls into the hashing routine
119 /* The value (lhs) of this expression. */
122 /* The expression (rhs) we want to record. */
125 /* The stmt pointer if this element corresponds to a statement. */
128 /* The hash value for RHS/ann. */
132 /* Stack of dest,src pairs that need to be restored during finalization.
134 A NULL entry is used to mark the end of pairs which need to be
135 restored during finalization of this block. */
136 static VEC(tree
,heap
) *const_and_copies_stack
;
138 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
139 know their exact value. */
140 static bitmap nonzero_vars
;
142 /* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
143 when the current block is finalized.
145 A NULL entry is used to mark the end of names needing their
146 entry in NONZERO_VARS cleared during finalization of this block. */
147 static VEC(tree
,heap
) *nonzero_vars_stack
;
149 /* Track whether or not we have changed the control flow graph. */
150 static bool cfg_altered
;
152 /* Bitmap of blocks that have had EH statements cleaned. We should
153 remove their dead edges eventually. */
154 static bitmap need_eh_cleanup
;
156 /* Statistics for dominator optimizations. */
160 long num_exprs_considered
;
166 static struct opt_stats_d opt_stats
;
174 /* Local functions. */
175 static void optimize_stmt (struct dom_walk_data
*,
177 block_stmt_iterator
);
178 static tree
lookup_avail_expr (tree
, bool);
179 static hashval_t
avail_expr_hash (const void *);
180 static hashval_t
real_avail_expr_hash (const void *);
181 static int avail_expr_eq (const void *, const void *);
182 static void htab_statistics (FILE *, htab_t
);
183 static void record_cond (tree
, tree
);
184 static void record_const_or_copy (tree
, tree
);
185 static void record_equality (tree
, tree
);
186 static void record_equivalences_from_phis (basic_block
);
187 static void record_equivalences_from_incoming_edge (basic_block
);
188 static bool eliminate_redundant_computations (tree
);
189 static void record_equivalences_from_stmt (tree
, int, stmt_ann_t
);
190 static void dom_thread_across_edge (struct dom_walk_data
*, edge
);
191 static void dom_opt_finalize_block (struct dom_walk_data
*, basic_block
);
192 static void dom_opt_initialize_block (struct dom_walk_data
*, basic_block
);
193 static void propagate_to_outgoing_edges (struct dom_walk_data
*, basic_block
);
194 static void remove_local_expressions_from_table (void);
195 static void restore_vars_to_original_value (void);
196 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
197 static void restore_nonzero_vars_to_original_value (void);
198 static inline bool unsafe_associative_fp_binop (tree
);
201 /* Allocate an EDGE_INFO for edge E and attach it to E.
202 Return the new EDGE_INFO structure. */
204 static struct edge_info
*
205 allocate_edge_info (edge e
)
207 struct edge_info
*edge_info
;
209 edge_info
= XCNEW (struct edge_info
);
215 /* Free all EDGE_INFO structures associated with edges in the CFG.
216 If a particular edge can be threaded, copy the redirection
217 target from the EDGE_INFO structure into the edge's AUX field
218 as required by code to update the CFG and SSA graph for
222 free_all_edge_infos (void)
230 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
232 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
236 if (edge_info
->cond_equivalences
)
237 free (edge_info
->cond_equivalences
);
245 /* Jump threading, redundancy elimination and const/copy propagation.
247 This pass may expose new symbols that need to be renamed into SSA. For
248 every new symbol exposed, its corresponding bit will be set in
252 tree_ssa_dominator_optimize (void)
254 struct dom_walk_data walk_data
;
256 struct loops loops_info
;
258 memset (&opt_stats
, 0, sizeof (opt_stats
));
260 /* Create our hash tables. */
261 avail_exprs
= htab_create (1024, real_avail_expr_hash
, avail_expr_eq
, free
);
262 avail_exprs_stack
= VEC_alloc (tree
, heap
, 20);
263 const_and_copies_stack
= VEC_alloc (tree
, heap
, 20);
264 nonzero_vars_stack
= VEC_alloc (tree
, heap
, 20);
265 stmts_to_rescan
= VEC_alloc (tree
, heap
, 20);
266 nonzero_vars
= BITMAP_ALLOC (NULL
);
267 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
269 /* Setup callbacks for the generic dominator tree walker. */
270 walk_data
.walk_stmts_backward
= false;
271 walk_data
.dom_direction
= CDI_DOMINATORS
;
272 walk_data
.initialize_block_local_data
= NULL
;
273 walk_data
.before_dom_children_before_stmts
= dom_opt_initialize_block
;
274 walk_data
.before_dom_children_walk_stmts
= optimize_stmt
;
275 walk_data
.before_dom_children_after_stmts
= propagate_to_outgoing_edges
;
276 walk_data
.after_dom_children_before_stmts
= NULL
;
277 walk_data
.after_dom_children_walk_stmts
= NULL
;
278 walk_data
.after_dom_children_after_stmts
= dom_opt_finalize_block
;
279 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
280 When we attach more stuff we'll need to fill this out with a real
282 walk_data
.global_data
= NULL
;
283 walk_data
.block_local_data_size
= 0;
284 walk_data
.interesting_blocks
= NULL
;
286 /* Now initialize the dominator walker. */
287 init_walk_dominator_tree (&walk_data
);
289 calculate_dominance_info (CDI_DOMINATORS
);
291 /* We need to know which edges exit loops so that we can
292 aggressively thread through loop headers to an exit
294 flow_loops_find (&loops_info
);
295 mark_loop_exit_edges (&loops_info
);
296 flow_loops_free (&loops_info
);
298 /* Clean up the CFG so that any forwarder blocks created by loop
299 canonicalization are removed. */
301 calculate_dominance_info (CDI_DOMINATORS
);
303 /* We need accurate information regarding back edges in the CFG
304 for jump threading. */
305 mark_dfs_back_edges ();
307 /* Recursively walk the dominator tree optimizing statements. */
308 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
311 block_stmt_iterator bsi
;
315 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
316 update_stmt_if_modified (bsi_stmt (bsi
));
320 /* If we exposed any new variables, go ahead and put them into
321 SSA form now, before we handle jump threading. This simplifies
322 interactions between rewriting of _DECL nodes into SSA form
323 and rewriting SSA_NAME nodes into SSA form after block
324 duplication and CFG manipulation. */
325 update_ssa (TODO_update_ssa
);
327 free_all_edge_infos ();
329 /* Thread jumps, creating duplicate blocks as needed. */
330 cfg_altered
|= thread_through_all_blocks ();
332 /* Removal of statements may make some EH edges dead. Purge
333 such edges from the CFG as needed. */
334 if (!bitmap_empty_p (need_eh_cleanup
))
336 cfg_altered
|= tree_purge_all_dead_eh_edges (need_eh_cleanup
);
337 bitmap_zero (need_eh_cleanup
);
341 free_dominance_info (CDI_DOMINATORS
);
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 /* Delete our main hashtable. */
365 htab_delete (avail_exprs
);
367 /* And finalize the dominator walker. */
368 fini_walk_dominator_tree (&walk_data
);
370 /* Free nonzero_vars. */
371 BITMAP_FREE (nonzero_vars
);
372 BITMAP_FREE (need_eh_cleanup
);
374 VEC_free (tree
, heap
, avail_exprs_stack
);
375 VEC_free (tree
, heap
, const_and_copies_stack
);
376 VEC_free (tree
, heap
, nonzero_vars_stack
);
377 VEC_free (tree
, heap
, stmts_to_rescan
);
381 gate_dominator (void)
383 return flag_tree_dom
!= 0;
386 struct tree_opt_pass pass_dominator
=
389 gate_dominator
, /* gate */
390 tree_ssa_dominator_optimize
, /* execute */
393 0, /* static_pass_number */
394 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
395 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
396 0, /* properties_provided */
397 0, /* properties_destroyed */
398 0, /* todo_flags_start */
402 | TODO_verify_ssa
, /* todo_flags_finish */
407 /* Given a stmt CONDSTMT containing a COND_EXPR, canonicalize the
408 COND_EXPR into a canonical form. */
411 canonicalize_comparison (tree condstmt
)
413 tree cond
= COND_EXPR_COND (condstmt
);
416 enum tree_code code
= TREE_CODE (cond
);
418 if (!COMPARISON_CLASS_P (cond
))
421 op0
= TREE_OPERAND (cond
, 0);
422 op1
= TREE_OPERAND (cond
, 1);
424 /* If it would be profitable to swap the operands, then do so to
425 canonicalize the statement, enabling better optimization.
427 By placing canonicalization of such expressions here we
428 transparently keep statements in canonical form, even
429 when the statement is modified. */
430 if (tree_swap_operands_p (op0
, op1
, false))
432 /* For relationals we need to swap the operands
433 and change the code. */
439 TREE_SET_CODE (cond
, swap_tree_comparison (code
));
440 swap_tree_operands (condstmt
,
441 &TREE_OPERAND (cond
, 0),
442 &TREE_OPERAND (cond
, 1));
443 /* If one operand was in the operand cache, but the other is
444 not, because it is a constant, this is a case that the
445 internal updating code of swap_tree_operands can't handle
447 if (TREE_CODE_CLASS (TREE_CODE (op0
))
448 != TREE_CODE_CLASS (TREE_CODE (op1
)))
449 update_stmt (condstmt
);
454 /* Initialize local stacks for this optimizer and record equivalences
455 upon entry to BB. Equivalences can come from the edge traversed to
456 reach BB or they may come from PHI nodes at the start of BB. */
459 dom_opt_initialize_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
463 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
465 /* Push a marker on the stacks of local information so that we know how
466 far to unwind when we finalize this block. */
467 VEC_safe_push (tree
, heap
, avail_exprs_stack
, NULL_TREE
);
468 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
469 VEC_safe_push (tree
, heap
, nonzero_vars_stack
, NULL_TREE
);
471 record_equivalences_from_incoming_edge (bb
);
473 /* PHI nodes can create equivalences too. */
474 record_equivalences_from_phis (bb
);
477 /* Given an expression EXPR (a relational expression or a statement),
478 initialize the hash table element pointed to by ELEMENT. */
481 initialize_hash_element (tree expr
, tree lhs
, struct expr_hash_elt
*element
)
483 /* Hash table elements may be based on conditional expressions or statements.
485 For the former case, we have no annotation and we want to hash the
486 conditional expression. In the latter case we have an annotation and
487 we want to record the expression the statement evaluates. */
488 if (COMPARISON_CLASS_P (expr
) || TREE_CODE (expr
) == TRUTH_NOT_EXPR
)
490 element
->stmt
= NULL
;
493 else if (TREE_CODE (expr
) == COND_EXPR
)
495 element
->stmt
= expr
;
496 element
->rhs
= COND_EXPR_COND (expr
);
498 else if (TREE_CODE (expr
) == SWITCH_EXPR
)
500 element
->stmt
= expr
;
501 element
->rhs
= SWITCH_COND (expr
);
503 else if (TREE_CODE (expr
) == RETURN_EXPR
&& TREE_OPERAND (expr
, 0))
505 element
->stmt
= expr
;
506 element
->rhs
= TREE_OPERAND (TREE_OPERAND (expr
, 0), 1);
508 else if (TREE_CODE (expr
) == GOTO_EXPR
)
510 element
->stmt
= expr
;
511 element
->rhs
= GOTO_DESTINATION (expr
);
515 element
->stmt
= expr
;
516 element
->rhs
= TREE_OPERAND (expr
, 1);
520 element
->hash
= avail_expr_hash (element
);
523 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
524 LIMIT entries left in LOCALs. */
527 remove_local_expressions_from_table (void)
529 /* Remove all the expressions made available in this block. */
530 while (VEC_length (tree
, avail_exprs_stack
) > 0)
532 struct expr_hash_elt element
;
533 tree expr
= VEC_pop (tree
, avail_exprs_stack
);
535 if (expr
== NULL_TREE
)
538 initialize_hash_element (expr
, NULL
, &element
);
539 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
543 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
544 state, stopping when there are LIMIT entries left in LOCALs. */
547 restore_nonzero_vars_to_original_value (void)
549 while (VEC_length (tree
, nonzero_vars_stack
) > 0)
551 tree name
= VEC_pop (tree
, nonzero_vars_stack
);
556 bitmap_clear_bit (nonzero_vars
, SSA_NAME_VERSION (name
));
560 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
561 CONST_AND_COPIES to its original state, stopping when we hit a
565 restore_vars_to_original_value (void)
567 while (VEC_length (tree
, const_and_copies_stack
) > 0)
569 tree prev_value
, dest
;
571 dest
= VEC_pop (tree
, const_and_copies_stack
);
576 prev_value
= VEC_pop (tree
, const_and_copies_stack
);
577 SSA_NAME_VALUE (dest
) = prev_value
;
581 /* A trivial wrapper so that we can present the generic jump
582 threading code with a simple API for simplifying statements. */
584 simplify_stmt_for_jump_threading (tree stmt
)
586 return lookup_avail_expr (stmt
, false);
589 /* Wrapper for common code to attempt to thread an edge. For example,
590 it handles lazily building the dummy condition and the bookkeeping
591 when jump threading is successful. */
594 dom_thread_across_edge (struct dom_walk_data
*walk_data
, edge e
)
596 /* If we don't already have a dummy condition, build it now. */
597 if (! walk_data
->global_data
)
599 tree dummy_cond
= build2 (NE_EXPR
, boolean_type_node
,
600 integer_zero_node
, integer_zero_node
);
601 dummy_cond
= build3 (COND_EXPR
, void_type_node
, dummy_cond
, NULL
, NULL
);
602 walk_data
->global_data
= dummy_cond
;
605 thread_across_edge (walk_data
->global_data
, e
, false,
606 &const_and_copies_stack
,
607 simplify_stmt_for_jump_threading
);
610 /* We have finished processing the dominator children of BB, perform
611 any finalization actions in preparation for leaving this node in
612 the dominator tree. */
615 dom_opt_finalize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
620 /* If we have an outgoing edge to a block with multiple incoming and
621 outgoing edges, then we may be able to thread the edge. ie, we
622 may be able to statically determine which of the outgoing edges
623 will be traversed when the incoming edge from BB is traversed. */
624 if (single_succ_p (bb
)
625 && (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
) == 0
626 && potentially_threadable_block (single_succ (bb
)))
628 dom_thread_across_edge (walk_data
, single_succ_edge (bb
));
630 else if ((last
= last_stmt (bb
))
631 && TREE_CODE (last
) == COND_EXPR
632 && (COMPARISON_CLASS_P (COND_EXPR_COND (last
))
633 || TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
)
634 && EDGE_COUNT (bb
->succs
) == 2
635 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
636 && (EDGE_SUCC (bb
, 1)->flags
& EDGE_ABNORMAL
) == 0)
638 edge true_edge
, false_edge
;
640 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
642 /* Only try to thread the edge if it reaches a target block with
643 more than one predecessor and more than one successor. */
644 if (potentially_threadable_block (true_edge
->dest
))
646 struct edge_info
*edge_info
;
649 /* Push a marker onto the available expression stack so that we
650 unwind any expressions related to the TRUE arm before processing
651 the false arm below. */
652 VEC_safe_push (tree
, heap
, avail_exprs_stack
, NULL_TREE
);
653 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
655 edge_info
= (struct edge_info
*) true_edge
->aux
;
657 /* If we have info associated with this edge, record it into
658 our equivalency tables. */
661 tree
*cond_equivalences
= edge_info
->cond_equivalences
;
662 tree lhs
= edge_info
->lhs
;
663 tree rhs
= edge_info
->rhs
;
665 /* If we have a simple NAME = VALUE equivalency record it. */
666 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
667 record_const_or_copy (lhs
, rhs
);
669 /* If we have 0 = COND or 1 = COND equivalences, record them
670 into our expression hash tables. */
671 if (cond_equivalences
)
672 for (i
= 0; i
< edge_info
->max_cond_equivalences
; i
+= 2)
674 tree expr
= cond_equivalences
[i
];
675 tree value
= cond_equivalences
[i
+ 1];
677 record_cond (expr
, value
);
681 dom_thread_across_edge (walk_data
, true_edge
);
683 /* And restore the various tables to their state before
684 we threaded this edge. */
685 remove_local_expressions_from_table ();
688 /* Similarly for the ELSE arm. */
689 if (potentially_threadable_block (false_edge
->dest
))
691 struct edge_info
*edge_info
;
694 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
695 edge_info
= (struct edge_info
*) false_edge
->aux
;
697 /* If we have info associated with this edge, record it into
698 our equivalency tables. */
701 tree
*cond_equivalences
= edge_info
->cond_equivalences
;
702 tree lhs
= edge_info
->lhs
;
703 tree rhs
= edge_info
->rhs
;
705 /* If we have a simple NAME = VALUE equivalency record it. */
706 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
707 record_const_or_copy (lhs
, rhs
);
709 /* If we have 0 = COND or 1 = COND equivalences, record them
710 into our expression hash tables. */
711 if (cond_equivalences
)
712 for (i
= 0; i
< edge_info
->max_cond_equivalences
; i
+= 2)
714 tree expr
= cond_equivalences
[i
];
715 tree value
= cond_equivalences
[i
+ 1];
717 record_cond (expr
, value
);
721 /* Now thread the edge. */
722 dom_thread_across_edge (walk_data
, false_edge
);
724 /* No need to remove local expressions from our tables
725 or restore vars to their original value as that will
726 be done immediately below. */
730 remove_local_expressions_from_table ();
731 restore_nonzero_vars_to_original_value ();
732 restore_vars_to_original_value ();
734 /* If we queued any statements to rescan in this block, then
735 go ahead and rescan them now. */
736 while (VEC_length (tree
, stmts_to_rescan
) > 0)
738 tree stmt
= VEC_last (tree
, stmts_to_rescan
);
739 basic_block stmt_bb
= bb_for_stmt (stmt
);
744 VEC_pop (tree
, stmts_to_rescan
);
745 mark_new_vars_to_rename (stmt
);
749 /* PHI nodes can create equivalences too.
751 Ignoring any alternatives which are the same as the result, if
752 all the alternatives are equal, then the PHI node creates an
755 Additionally, if all the PHI alternatives are known to have a nonzero
756 value, then the result of this PHI is known to have a nonzero value,
757 even if we do not know its exact value. */
760 record_equivalences_from_phis (basic_block bb
)
764 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
766 tree lhs
= PHI_RESULT (phi
);
770 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
772 tree t
= PHI_ARG_DEF (phi
, i
);
774 /* Ignore alternatives which are the same as our LHS. Since
775 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
776 can simply compare pointers. */
780 /* If we have not processed an alternative yet, then set
781 RHS to this alternative. */
784 /* If we have processed an alternative (stored in RHS), then
785 see if it is equal to this one. If it isn't, then stop
787 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
791 /* If we had no interesting alternatives, then all the RHS alternatives
792 must have been the same as LHS. */
796 /* If we managed to iterate through each PHI alternative without
797 breaking out of the loop, then we have a PHI which may create
798 a useful equivalence. We do not need to record unwind data for
799 this, since this is a true assignment and not an equivalence
800 inferred from a comparison. All uses of this ssa name are dominated
801 by this assignment, so unwinding just costs time and space. */
802 if (i
== PHI_NUM_ARGS (phi
)
803 && may_propagate_copy (lhs
, rhs
))
804 SSA_NAME_VALUE (lhs
) = rhs
;
806 /* Now see if we know anything about the nonzero property for the
807 result of this PHI. */
808 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
810 if (!PHI_ARG_NONZERO (phi
, i
))
814 if (i
== PHI_NUM_ARGS (phi
))
815 bitmap_set_bit (nonzero_vars
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
819 /* Ignoring loop backedges, if BB has precisely one incoming edge then
820 return that edge. Otherwise return NULL. */
822 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
828 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
830 /* A loop back edge can be identified by the destination of
831 the edge dominating the source of the edge. */
832 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
835 /* If we have already seen a non-loop edge, then we must have
836 multiple incoming non-loop edges and thus we return NULL. */
840 /* This is the first non-loop incoming edge we have found. Record
848 /* Record any equivalences created by the incoming edge to BB. If BB
849 has more than one incoming edge, then no equivalence is created. */
852 record_equivalences_from_incoming_edge (basic_block bb
)
856 struct edge_info
*edge_info
;
858 /* If our parent block ended with a control statement, then we may be
859 able to record some equivalences based on which outgoing edge from
860 the parent was followed. */
861 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
863 e
= single_incoming_edge_ignoring_loop_edges (bb
);
865 /* If we had a single incoming edge from our parent block, then enter
866 any data associated with the edge into our tables. */
867 if (e
&& e
->src
== parent
)
871 edge_info
= (struct edge_info
*) e
->aux
;
875 tree lhs
= edge_info
->lhs
;
876 tree rhs
= edge_info
->rhs
;
877 tree
*cond_equivalences
= edge_info
->cond_equivalences
;
880 record_equality (lhs
, rhs
);
882 if (cond_equivalences
)
884 for (i
= 0; i
< edge_info
->max_cond_equivalences
; i
+= 2)
886 tree expr
= cond_equivalences
[i
];
887 tree value
= cond_equivalences
[i
+ 1];
889 record_cond (expr
, value
);
896 /* Dump SSA statistics on FILE. */
899 dump_dominator_optimization_stats (FILE *file
)
903 fprintf (file
, "Total number of statements: %6ld\n\n",
904 opt_stats
.num_stmts
);
905 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
906 opt_stats
.num_exprs_considered
);
908 n_exprs
= opt_stats
.num_exprs_considered
;
912 fprintf (file
, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
913 opt_stats
.num_re
, PERCENT (opt_stats
.num_re
,
915 fprintf (file
, " Constants propagated: %6ld\n",
916 opt_stats
.num_const_prop
);
917 fprintf (file
, " Copies propagated: %6ld\n",
918 opt_stats
.num_copy_prop
);
920 fprintf (file
, "\nHash table statistics:\n");
922 fprintf (file
, " avail_exprs: ");
923 htab_statistics (file
, avail_exprs
);
927 /* Dump SSA statistics on stderr. */
930 debug_dominator_optimization_stats (void)
932 dump_dominator_optimization_stats (stderr
);
936 /* Dump statistics for the hash table HTAB. */
939 htab_statistics (FILE *file
, htab_t htab
)
941 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
942 (long) htab_size (htab
),
943 (long) htab_elements (htab
),
944 htab_collisions (htab
));
947 /* Record the fact that VAR has a nonzero value, though we may not know
948 its exact value. Note that if VAR is already known to have a nonzero
949 value, then we do nothing. */
952 record_var_is_nonzero (tree var
)
954 int indx
= SSA_NAME_VERSION (var
);
956 if (bitmap_bit_p (nonzero_vars
, indx
))
959 /* Mark it in the global table. */
960 bitmap_set_bit (nonzero_vars
, indx
);
962 /* Record this SSA_NAME so that we can reset the global table
963 when we leave this block. */
964 VEC_safe_push (tree
, heap
, nonzero_vars_stack
, var
);
967 /* Enter a statement into the true/false expression hash table indicating
968 that the condition COND has the value VALUE. */
971 record_cond (tree cond
, tree value
)
973 struct expr_hash_elt
*element
= XCNEW (struct expr_hash_elt
);
976 initialize_hash_element (cond
, value
, element
);
978 slot
= htab_find_slot_with_hash (avail_exprs
, (void *)element
,
979 element
->hash
, INSERT
);
982 *slot
= (void *) element
;
983 VEC_safe_push (tree
, heap
, avail_exprs_stack
, cond
);
989 /* Build a new conditional using NEW_CODE, OP0 and OP1 and store
990 the new conditional into *p, then store a boolean_true_node
994 build_and_record_new_cond (enum tree_code new_code
, tree op0
, tree op1
, tree
*p
)
996 *p
= build2 (new_code
, boolean_type_node
, op0
, op1
);
998 *p
= boolean_true_node
;
1001 /* Record that COND is true and INVERTED is false into the edge information
1002 structure. Also record that any conditions dominated by COND are true
1005 For example, if a < b is true, then a <= b must also be true. */
1008 record_conditions (struct edge_info
*edge_info
, tree cond
, tree inverted
)
1012 if (!COMPARISON_CLASS_P (cond
))
1015 op0
= TREE_OPERAND (cond
, 0);
1016 op1
= TREE_OPERAND (cond
, 1);
1018 switch (TREE_CODE (cond
))
1022 edge_info
->max_cond_equivalences
= 12;
1023 edge_info
->cond_equivalences
= XNEWVEC (tree
, 12);
1024 build_and_record_new_cond ((TREE_CODE (cond
) == LT_EXPR
1025 ? LE_EXPR
: GE_EXPR
),
1026 op0
, op1
, &edge_info
->cond_equivalences
[4]);
1027 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1028 &edge_info
->cond_equivalences
[6]);
1029 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1030 &edge_info
->cond_equivalences
[8]);
1031 build_and_record_new_cond (LTGT_EXPR
, op0
, op1
,
1032 &edge_info
->cond_equivalences
[10]);
1037 edge_info
->max_cond_equivalences
= 6;
1038 edge_info
->cond_equivalences
= XNEWVEC (tree
, 6);
1039 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1040 &edge_info
->cond_equivalences
[4]);
1044 edge_info
->max_cond_equivalences
= 10;
1045 edge_info
->cond_equivalences
= XNEWVEC (tree
, 10);
1046 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1047 &edge_info
->cond_equivalences
[4]);
1048 build_and_record_new_cond (LE_EXPR
, op0
, op1
,
1049 &edge_info
->cond_equivalences
[6]);
1050 build_and_record_new_cond (GE_EXPR
, op0
, op1
,
1051 &edge_info
->cond_equivalences
[8]);
1054 case UNORDERED_EXPR
:
1055 edge_info
->max_cond_equivalences
= 16;
1056 edge_info
->cond_equivalences
= XNEWVEC (tree
, 16);
1057 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1058 &edge_info
->cond_equivalences
[4]);
1059 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1060 &edge_info
->cond_equivalences
[6]);
1061 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1062 &edge_info
->cond_equivalences
[8]);
1063 build_and_record_new_cond (UNEQ_EXPR
, op0
, op1
,
1064 &edge_info
->cond_equivalences
[10]);
1065 build_and_record_new_cond (UNLT_EXPR
, op0
, op1
,
1066 &edge_info
->cond_equivalences
[12]);
1067 build_and_record_new_cond (UNGT_EXPR
, op0
, op1
,
1068 &edge_info
->cond_equivalences
[14]);
1073 edge_info
->max_cond_equivalences
= 8;
1074 edge_info
->cond_equivalences
= XNEWVEC (tree
, 8);
1075 build_and_record_new_cond ((TREE_CODE (cond
) == UNLT_EXPR
1076 ? UNLE_EXPR
: UNGE_EXPR
),
1077 op0
, op1
, &edge_info
->cond_equivalences
[4]);
1078 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1079 &edge_info
->cond_equivalences
[6]);
1083 edge_info
->max_cond_equivalences
= 8;
1084 edge_info
->cond_equivalences
= XNEWVEC (tree
, 8);
1085 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1086 &edge_info
->cond_equivalences
[4]);
1087 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1088 &edge_info
->cond_equivalences
[6]);
1092 edge_info
->max_cond_equivalences
= 8;
1093 edge_info
->cond_equivalences
= XNEWVEC (tree
, 8);
1094 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1095 &edge_info
->cond_equivalences
[4]);
1096 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1097 &edge_info
->cond_equivalences
[6]);
1101 edge_info
->max_cond_equivalences
= 4;
1102 edge_info
->cond_equivalences
= XNEWVEC (tree
, 4);
1106 /* Now store the original true and false conditions into the first
1108 edge_info
->cond_equivalences
[0] = cond
;
1109 edge_info
->cond_equivalences
[1] = boolean_true_node
;
1110 edge_info
->cond_equivalences
[2] = inverted
;
1111 edge_info
->cond_equivalences
[3] = boolean_false_node
;
1114 /* A helper function for record_const_or_copy and record_equality.
1115 Do the work of recording the value and undo info. */
1118 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
)
1120 SSA_NAME_VALUE (x
) = y
;
1122 VEC_reserve (tree
, heap
, const_and_copies_stack
, 2);
1123 VEC_quick_push (tree
, const_and_copies_stack
, prev_x
);
1124 VEC_quick_push (tree
, const_and_copies_stack
, x
);
1128 /* Return the loop depth of the basic block of the defining statement of X.
1129 This number should not be treated as absolutely correct because the loop
1130 information may not be completely up-to-date when dom runs. However, it
1131 will be relatively correct, and as more passes are taught to keep loop info
1132 up to date, the result will become more and more accurate. */
1135 loop_depth_of_name (tree x
)
1140 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1141 if (TREE_CODE (x
) != SSA_NAME
)
1144 /* Otherwise return the loop depth of the defining statement's bb.
1145 Note that there may not actually be a bb for this statement, if the
1146 ssa_name is live on entry. */
1147 defstmt
= SSA_NAME_DEF_STMT (x
);
1148 defbb
= bb_for_stmt (defstmt
);
1152 return defbb
->loop_depth
;
1156 /* Record that X is equal to Y in const_and_copies. Record undo
1157 information in the block-local vector. */
1160 record_const_or_copy (tree x
, tree y
)
1162 tree prev_x
= SSA_NAME_VALUE (x
);
1164 if (TREE_CODE (y
) == SSA_NAME
)
1166 tree tmp
= SSA_NAME_VALUE (y
);
1171 record_const_or_copy_1 (x
, y
, prev_x
);
1174 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1175 This constrains the cases in which we may treat this as assignment. */
1178 record_equality (tree x
, tree y
)
1180 tree prev_x
= NULL
, prev_y
= NULL
;
1182 if (TREE_CODE (x
) == SSA_NAME
)
1183 prev_x
= SSA_NAME_VALUE (x
);
1184 if (TREE_CODE (y
) == SSA_NAME
)
1185 prev_y
= SSA_NAME_VALUE (y
);
1187 /* If one of the previous values is invariant, or invariant in more loops
1188 (by depth), then use that.
1189 Otherwise it doesn't matter which value we choose, just so
1190 long as we canonicalize on one value. */
1191 if (TREE_INVARIANT (y
))
1193 else if (TREE_INVARIANT (x
) || (loop_depth_of_name (x
) <= loop_depth_of_name (y
)))
1194 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1195 else if (prev_x
&& TREE_INVARIANT (prev_x
))
1196 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1197 else if (prev_y
&& TREE_CODE (prev_y
) != VALUE_HANDLE
)
1200 /* After the swapping, we must have one SSA_NAME. */
1201 if (TREE_CODE (x
) != SSA_NAME
)
1204 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1205 variable compared against zero. If we're honoring signed zeros,
1206 then we cannot record this value unless we know that the value is
1208 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1209 && (TREE_CODE (y
) != REAL_CST
1210 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1213 record_const_or_copy_1 (x
, y
, prev_x
);
1216 /* Return true, if it is ok to do folding of an associative expression.
1217 EXP is the tree for the associative expression. */
1220 unsafe_associative_fp_binop (tree exp
)
1222 enum tree_code code
= TREE_CODE (exp
);
1223 return !(!flag_unsafe_math_optimizations
1224 && (code
== MULT_EXPR
|| code
== PLUS_EXPR
1225 || code
== MINUS_EXPR
)
1226 && FLOAT_TYPE_P (TREE_TYPE (exp
)));
1229 /* Returns true when STMT is a simple iv increment. It detects the
1230 following situation:
1232 i_1 = phi (..., i_2)
1233 i_2 = i_1 +/- ... */
1236 simple_iv_increment_p (tree stmt
)
1238 tree lhs
, rhs
, preinc
, phi
;
1241 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1244 lhs
= TREE_OPERAND (stmt
, 0);
1245 if (TREE_CODE (lhs
) != SSA_NAME
)
1248 rhs
= TREE_OPERAND (stmt
, 1);
1250 if (TREE_CODE (rhs
) != PLUS_EXPR
1251 && TREE_CODE (rhs
) != MINUS_EXPR
)
1254 preinc
= TREE_OPERAND (rhs
, 0);
1255 if (TREE_CODE (preinc
) != SSA_NAME
)
1258 phi
= SSA_NAME_DEF_STMT (preinc
);
1259 if (TREE_CODE (phi
) != PHI_NODE
)
1262 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1263 if (PHI_ARG_DEF (phi
, i
) == lhs
)
1269 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1270 known value for that SSA_NAME (or NULL if no value is known).
1272 NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
1273 even if we don't know their precise value.
1275 Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
1276 nodes of the successors of BB. */
1279 cprop_into_successor_phis (basic_block bb
, bitmap nonzero_vars
)
1284 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1289 /* If this is an abnormal edge, then we do not want to copy propagate
1290 into the PHI alternative associated with this edge. */
1291 if (e
->flags
& EDGE_ABNORMAL
)
1294 phi
= phi_nodes (e
->dest
);
1299 for ( ; phi
; phi
= PHI_CHAIN (phi
))
1302 use_operand_p orig_p
;
1305 /* The alternative may be associated with a constant, so verify
1306 it is an SSA_NAME before doing anything with it. */
1307 orig_p
= PHI_ARG_DEF_PTR (phi
, indx
);
1308 orig
= USE_FROM_PTR (orig_p
);
1309 if (TREE_CODE (orig
) != SSA_NAME
)
1312 /* If the alternative is known to have a nonzero value, record
1313 that fact in the PHI node itself for future use. */
1314 if (bitmap_bit_p (nonzero_vars
, SSA_NAME_VERSION (orig
)))
1315 PHI_ARG_NONZERO (phi
, indx
) = true;
1317 /* If we have *ORIG_P in our constant/copy table, then replace
1318 ORIG_P with its value in our constant/copy table. */
1319 new = SSA_NAME_VALUE (orig
);
1322 && (TREE_CODE (new) == SSA_NAME
1323 || is_gimple_min_invariant (new))
1324 && may_propagate_copy (orig
, new))
1325 propagate_value (orig_p
, new);
1330 /* We have finished optimizing BB, record any information implied by
1331 taking a specific outgoing edge from BB. */
1334 record_edge_info (basic_block bb
)
1336 block_stmt_iterator bsi
= bsi_last (bb
);
1337 struct edge_info
*edge_info
;
1339 if (! bsi_end_p (bsi
))
1341 tree stmt
= bsi_stmt (bsi
);
1343 if (stmt
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
1345 tree cond
= SWITCH_COND (stmt
);
1347 if (TREE_CODE (cond
) == SSA_NAME
)
1349 tree labels
= SWITCH_LABELS (stmt
);
1350 int i
, n_labels
= TREE_VEC_LENGTH (labels
);
1351 tree
*info
= XCNEWVEC (tree
, last_basic_block
);
1355 for (i
= 0; i
< n_labels
; i
++)
1357 tree label
= TREE_VEC_ELT (labels
, i
);
1358 basic_block target_bb
= label_to_block (CASE_LABEL (label
));
1360 if (CASE_HIGH (label
)
1361 || !CASE_LOW (label
)
1362 || info
[target_bb
->index
])
1363 info
[target_bb
->index
] = error_mark_node
;
1365 info
[target_bb
->index
] = label
;
1368 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1370 basic_block target_bb
= e
->dest
;
1371 tree node
= info
[target_bb
->index
];
1373 if (node
!= NULL
&& node
!= error_mark_node
)
1375 tree x
= fold_convert (TREE_TYPE (cond
), CASE_LOW (node
));
1376 edge_info
= allocate_edge_info (e
);
1377 edge_info
->lhs
= cond
;
1385 /* A COND_EXPR may create equivalences too. */
1386 if (stmt
&& TREE_CODE (stmt
) == COND_EXPR
)
1388 tree cond
= COND_EXPR_COND (stmt
);
1392 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1394 /* If the conditional is a single variable 'X', record 'X = 1'
1395 for the true edge and 'X = 0' on the false edge. */
1396 if (SSA_VAR_P (cond
))
1398 struct edge_info
*edge_info
;
1400 edge_info
= allocate_edge_info (true_edge
);
1401 edge_info
->lhs
= cond
;
1402 edge_info
->rhs
= constant_boolean_node (1, TREE_TYPE (cond
));
1404 edge_info
= allocate_edge_info (false_edge
);
1405 edge_info
->lhs
= cond
;
1406 edge_info
->rhs
= constant_boolean_node (0, TREE_TYPE (cond
));
1408 /* Equality tests may create one or two equivalences. */
1409 else if (COMPARISON_CLASS_P (cond
))
1411 tree op0
= TREE_OPERAND (cond
, 0);
1412 tree op1
= TREE_OPERAND (cond
, 1);
1414 /* Special case comparing booleans against a constant as we
1415 know the value of OP0 on both arms of the branch. i.e., we
1416 can record an equivalence for OP0 rather than COND. */
1417 if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
1418 && TREE_CODE (op0
) == SSA_NAME
1419 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
1420 && is_gimple_min_invariant (op1
))
1422 if (TREE_CODE (cond
) == EQ_EXPR
)
1424 edge_info
= allocate_edge_info (true_edge
);
1425 edge_info
->lhs
= op0
;
1426 edge_info
->rhs
= (integer_zerop (op1
)
1427 ? boolean_false_node
1428 : boolean_true_node
);
1430 edge_info
= allocate_edge_info (false_edge
);
1431 edge_info
->lhs
= op0
;
1432 edge_info
->rhs
= (integer_zerop (op1
)
1434 : boolean_false_node
);
1438 edge_info
= allocate_edge_info (true_edge
);
1439 edge_info
->lhs
= op0
;
1440 edge_info
->rhs
= (integer_zerop (op1
)
1442 : boolean_false_node
);
1444 edge_info
= allocate_edge_info (false_edge
);
1445 edge_info
->lhs
= op0
;
1446 edge_info
->rhs
= (integer_zerop (op1
)
1447 ? boolean_false_node
1448 : boolean_true_node
);
1452 else if (is_gimple_min_invariant (op0
)
1453 && (TREE_CODE (op1
) == SSA_NAME
1454 || is_gimple_min_invariant (op1
)))
1456 tree inverted
= invert_truthvalue (cond
);
1457 struct edge_info
*edge_info
;
1459 edge_info
= allocate_edge_info (true_edge
);
1460 record_conditions (edge_info
, cond
, inverted
);
1462 if (TREE_CODE (cond
) == EQ_EXPR
)
1464 edge_info
->lhs
= op1
;
1465 edge_info
->rhs
= op0
;
1468 edge_info
= allocate_edge_info (false_edge
);
1469 record_conditions (edge_info
, inverted
, cond
);
1471 if (TREE_CODE (cond
) == NE_EXPR
)
1473 edge_info
->lhs
= op1
;
1474 edge_info
->rhs
= op0
;
1478 else if (TREE_CODE (op0
) == SSA_NAME
1479 && (is_gimple_min_invariant (op1
)
1480 || TREE_CODE (op1
) == SSA_NAME
))
1482 tree inverted
= invert_truthvalue (cond
);
1483 struct edge_info
*edge_info
;
1485 edge_info
= allocate_edge_info (true_edge
);
1486 record_conditions (edge_info
, cond
, inverted
);
1488 if (TREE_CODE (cond
) == EQ_EXPR
)
1490 edge_info
->lhs
= op0
;
1491 edge_info
->rhs
= op1
;
1494 edge_info
= allocate_edge_info (false_edge
);
1495 record_conditions (edge_info
, inverted
, cond
);
1497 if (TREE_CODE (cond
) == NE_EXPR
)
1499 edge_info
->lhs
= op0
;
1500 edge_info
->rhs
= op1
;
1505 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1510 /* Propagate information from BB to its outgoing edges.
1512 This can include equivalency information implied by control statements
1513 at the end of BB and const/copy propagation into PHIs in BB's
1514 successor blocks. */
1517 propagate_to_outgoing_edges (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1520 record_edge_info (bb
);
1521 cprop_into_successor_phis (bb
, nonzero_vars
);
1524 /* Search for redundant computations in STMT. If any are found, then
1525 replace them with the variable holding the result of the computation.
1527 If safe, record this expression into the available expression hash
1531 eliminate_redundant_computations (tree stmt
)
1533 tree
*expr_p
, def
= NULL_TREE
;
1536 bool retval
= false;
1537 bool modify_expr_p
= false;
1539 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1540 def
= TREE_OPERAND (stmt
, 0);
1542 /* Certain expressions on the RHS can be optimized away, but can not
1543 themselves be entered into the hash tables. */
1545 || TREE_CODE (def
) != SSA_NAME
1546 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
1547 || !ZERO_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
)
1548 /* Do not record equivalences for increments of ivs. This would create
1549 overlapping live ranges for a very questionable gain. */
1550 || simple_iv_increment_p (stmt
))
1553 /* Check if the expression has been computed before. */
1554 cached_lhs
= lookup_avail_expr (stmt
, insert
);
1556 opt_stats
.num_exprs_considered
++;
1558 /* Get a pointer to the expression we are trying to optimize. */
1559 if (TREE_CODE (stmt
) == COND_EXPR
)
1560 expr_p
= &COND_EXPR_COND (stmt
);
1561 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
1562 expr_p
= &SWITCH_COND (stmt
);
1563 else if (TREE_CODE (stmt
) == RETURN_EXPR
&& TREE_OPERAND (stmt
, 0))
1565 expr_p
= &TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
1566 modify_expr_p
= true;
1570 expr_p
= &TREE_OPERAND (stmt
, 1);
1571 modify_expr_p
= true;
1574 /* It is safe to ignore types here since we have already done
1575 type checking in the hashing and equality routines. In fact
1576 type checking here merely gets in the way of constant
1577 propagation. Also, make sure that it is safe to propagate
1578 CACHED_LHS into *EXPR_P. */
1580 && ((TREE_CODE (cached_lhs
) != SSA_NAME
1582 || tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p
),
1583 TREE_TYPE (cached_lhs
))))
1584 || may_propagate_copy (*expr_p
, cached_lhs
)))
1586 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1588 fprintf (dump_file
, " Replaced redundant expr '");
1589 print_generic_expr (dump_file
, *expr_p
, dump_flags
);
1590 fprintf (dump_file
, "' with '");
1591 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
1592 fprintf (dump_file
, "'\n");
1597 #if defined ENABLE_CHECKING
1598 gcc_assert (TREE_CODE (cached_lhs
) == SSA_NAME
1599 || is_gimple_min_invariant (cached_lhs
));
1602 if (TREE_CODE (cached_lhs
) == ADDR_EXPR
1603 || (POINTER_TYPE_P (TREE_TYPE (*expr_p
))
1604 && is_gimple_min_invariant (cached_lhs
)))
1608 && !tree_ssa_useless_type_conversion_1 (TREE_TYPE (*expr_p
),
1609 TREE_TYPE (cached_lhs
)))
1610 cached_lhs
= fold_convert (TREE_TYPE (*expr_p
), cached_lhs
);
1612 propagate_tree_value (expr_p
, cached_lhs
);
1613 mark_stmt_modified (stmt
);
1618 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
1619 the available expressions table or the const_and_copies table.
1620 Detect and record those equivalences. */
1623 record_equivalences_from_stmt (tree stmt
,
1627 tree lhs
= TREE_OPERAND (stmt
, 0);
1628 enum tree_code lhs_code
= TREE_CODE (lhs
);
1631 if (lhs_code
== SSA_NAME
)
1633 tree rhs
= TREE_OPERAND (stmt
, 1);
1635 /* Strip away any useless type conversions. */
1636 STRIP_USELESS_TYPE_CONVERSION (rhs
);
1638 /* If the RHS of the assignment is a constant or another variable that
1639 may be propagated, register it in the CONST_AND_COPIES table. We
1640 do not need to record unwind data for this, since this is a true
1641 assignment and not an equivalence inferred from a comparison. All
1642 uses of this ssa name are dominated by this assignment, so unwinding
1643 just costs time and space. */
1645 && (TREE_CODE (rhs
) == SSA_NAME
1646 || is_gimple_min_invariant (rhs
)))
1647 SSA_NAME_VALUE (lhs
) = rhs
;
1649 if (tree_expr_nonzero_p (rhs
))
1650 record_var_is_nonzero (lhs
);
1653 /* Look at both sides for pointer dereferences. If we find one, then
1654 the pointer must be nonnull and we can enter that equivalence into
1656 if (flag_delete_null_pointer_checks
)
1657 for (i
= 0; i
< 2; i
++)
1659 tree t
= TREE_OPERAND (stmt
, i
);
1661 /* Strip away any COMPONENT_REFs. */
1662 while (TREE_CODE (t
) == COMPONENT_REF
)
1663 t
= TREE_OPERAND (t
, 0);
1665 /* Now see if this is a pointer dereference. */
1666 if (INDIRECT_REF_P (t
))
1668 tree op
= TREE_OPERAND (t
, 0);
1670 /* If the pointer is a SSA variable, then enter new
1671 equivalences into the hash table. */
1672 while (TREE_CODE (op
) == SSA_NAME
)
1674 tree def
= SSA_NAME_DEF_STMT (op
);
1676 record_var_is_nonzero (op
);
1678 /* And walk up the USE-DEF chains noting other SSA_NAMEs
1679 which are known to have a nonzero value. */
1681 && TREE_CODE (def
) == MODIFY_EXPR
1682 && TREE_CODE (TREE_OPERAND (def
, 1)) == NOP_EXPR
)
1683 op
= TREE_OPERAND (TREE_OPERAND (def
, 1), 0);
1690 /* A memory store, even an aliased store, creates a useful
1691 equivalence. By exchanging the LHS and RHS, creating suitable
1692 vops and recording the result in the available expression table,
1693 we may be able to expose more redundant loads. */
1694 if (!ann
->has_volatile_ops
1695 && (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
1696 || is_gimple_min_invariant (TREE_OPERAND (stmt
, 1)))
1697 && !is_gimple_reg (lhs
))
1699 tree rhs
= TREE_OPERAND (stmt
, 1);
1702 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
1703 is a constant, we need to adjust the constant to fit into the
1704 type of the LHS. If the LHS is a bitfield and the RHS is not
1705 a constant, then we can not record any equivalences for this
1706 statement since we would need to represent the widening or
1707 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
1708 and should not be necessary if GCC represented bitfields
1710 if (lhs_code
== COMPONENT_REF
1711 && DECL_BIT_FIELD (TREE_OPERAND (lhs
, 1)))
1713 if (TREE_CONSTANT (rhs
))
1714 rhs
= widen_bitfield (rhs
, TREE_OPERAND (lhs
, 1), lhs
);
1718 /* If the value overflowed, then we can not use this equivalence. */
1719 if (rhs
&& ! is_gimple_min_invariant (rhs
))
1725 /* Build a new statement with the RHS and LHS exchanged. */
1726 new = build2 (MODIFY_EXPR
, TREE_TYPE (stmt
), rhs
, lhs
);
1728 create_ssa_artficial_load_stmt (new, stmt
);
1730 /* Finally enter the statement into the available expression
1732 lookup_avail_expr (new, true);
1737 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1738 CONST_AND_COPIES. */
1741 cprop_operand (tree stmt
, use_operand_p op_p
)
1743 bool may_have_exposed_new_symbols
= false;
1745 tree op
= USE_FROM_PTR (op_p
);
1747 /* If the operand has a known constant value or it is known to be a
1748 copy of some other variable, use the value or copy stored in
1749 CONST_AND_COPIES. */
1750 val
= SSA_NAME_VALUE (op
);
1751 if (val
&& val
!= op
&& TREE_CODE (val
) != VALUE_HANDLE
)
1753 tree op_type
, val_type
;
1755 /* Do not change the base variable in the virtual operand
1756 tables. That would make it impossible to reconstruct
1757 the renamed virtual operand if we later modify this
1758 statement. Also only allow the new value to be an SSA_NAME
1759 for propagation into virtual operands. */
1760 if (!is_gimple_reg (op
)
1761 && (TREE_CODE (val
) != SSA_NAME
1762 || is_gimple_reg (val
)
1763 || get_virtual_var (val
) != get_virtual_var (op
)))
1766 /* Do not replace hard register operands in asm statements. */
1767 if (TREE_CODE (stmt
) == ASM_EXPR
1768 && !may_propagate_copy_into_asm (op
))
1771 /* Get the toplevel type of each operand. */
1772 op_type
= TREE_TYPE (op
);
1773 val_type
= TREE_TYPE (val
);
1775 /* While both types are pointers, get the type of the object
1777 while (POINTER_TYPE_P (op_type
) && POINTER_TYPE_P (val_type
))
1779 op_type
= TREE_TYPE (op_type
);
1780 val_type
= TREE_TYPE (val_type
);
1783 /* Make sure underlying types match before propagating a constant by
1784 converting the constant to the proper type. Note that convert may
1785 return a non-gimple expression, in which case we ignore this
1786 propagation opportunity. */
1787 if (TREE_CODE (val
) != SSA_NAME
)
1789 if (!lang_hooks
.types_compatible_p (op_type
, val_type
))
1791 val
= fold_convert (TREE_TYPE (op
), val
);
1792 if (!is_gimple_min_invariant (val
))
1797 /* Certain operands are not allowed to be copy propagated due
1798 to their interaction with exception handling and some GCC
1800 else if (!may_propagate_copy (op
, val
))
1803 /* Do not propagate copies if the propagated value is at a deeper loop
1804 depth than the propagatee. Otherwise, this may move loop variant
1805 variables outside of their loops and prevent coalescing
1806 opportunities. If the value was loop invariant, it will be hoisted
1807 by LICM and exposed for copy propagation. */
1808 if (loop_depth_of_name (val
) > loop_depth_of_name (op
))
1812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1814 fprintf (dump_file
, " Replaced '");
1815 print_generic_expr (dump_file
, op
, dump_flags
);
1816 fprintf (dump_file
, "' with %s '",
1817 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
1818 print_generic_expr (dump_file
, val
, dump_flags
);
1819 fprintf (dump_file
, "'\n");
1822 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
1823 that we may have exposed a new symbol for SSA renaming. */
1824 if (TREE_CODE (val
) == ADDR_EXPR
1825 || (POINTER_TYPE_P (TREE_TYPE (op
))
1826 && is_gimple_min_invariant (val
)))
1827 may_have_exposed_new_symbols
= true;
1829 if (TREE_CODE (val
) != SSA_NAME
)
1830 opt_stats
.num_const_prop
++;
1832 opt_stats
.num_copy_prop
++;
1834 propagate_value (op_p
, val
);
1836 /* And note that we modified this statement. This is now
1837 safe, even if we changed virtual operands since we will
1838 rescan the statement and rewrite its operands again. */
1839 mark_stmt_modified (stmt
);
1841 return may_have_exposed_new_symbols
;
1844 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1845 known value for that SSA_NAME (or NULL if no value is known).
1847 Propagate values from CONST_AND_COPIES into the uses, vuses and
1848 v_may_def_ops of STMT. */
1851 cprop_into_stmt (tree stmt
)
1853 bool may_have_exposed_new_symbols
= false;
1857 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_ALL_USES
)
1859 if (TREE_CODE (USE_FROM_PTR (op_p
)) == SSA_NAME
)
1860 may_have_exposed_new_symbols
|= cprop_operand (stmt
, op_p
);
1863 return may_have_exposed_new_symbols
;
1867 /* Optimize the statement pointed to by iterator SI.
1869 We try to perform some simplistic global redundancy elimination and
1870 constant propagation:
1872 1- To detect global redundancy, we keep track of expressions that have
1873 been computed in this block and its dominators. If we find that the
1874 same expression is computed more than once, we eliminate repeated
1875 computations by using the target of the first one.
1877 2- Constant values and copy assignments. This is used to do very
1878 simplistic constant and copy propagation. When a constant or copy
1879 assignment is found, we map the value on the RHS of the assignment to
1880 the variable in the LHS in the CONST_AND_COPIES table. */
1883 optimize_stmt (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1884 basic_block bb
, block_stmt_iterator si
)
1887 tree stmt
, old_stmt
;
1888 bool may_optimize_p
;
1889 bool may_have_exposed_new_symbols
= false;
1891 old_stmt
= stmt
= bsi_stmt (si
);
1893 if (TREE_CODE (stmt
) == COND_EXPR
)
1894 canonicalize_comparison (stmt
);
1896 update_stmt_if_modified (stmt
);
1897 ann
= stmt_ann (stmt
);
1898 opt_stats
.num_stmts
++;
1899 may_have_exposed_new_symbols
= false;
1901 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1903 fprintf (dump_file
, "Optimizing statement ");
1904 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1907 /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
1908 may_have_exposed_new_symbols
= cprop_into_stmt (stmt
);
1910 /* If the statement has been modified with constant replacements,
1911 fold its RHS before checking for redundant computations. */
1916 /* Try to fold the statement making sure that STMT is kept
1918 if (fold_stmt (bsi_stmt_ptr (si
)))
1920 stmt
= bsi_stmt (si
);
1921 ann
= stmt_ann (stmt
);
1923 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1925 fprintf (dump_file
, " Folded to: ");
1926 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
1930 rhs
= get_rhs (stmt
);
1931 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
1932 recompute_tree_invariant_for_addr_expr (rhs
);
1934 /* Constant/copy propagation above may change the set of
1935 virtual operands associated with this statement. Folding
1936 may remove the need for some virtual operands.
1938 Indicate we will need to rescan and rewrite the statement. */
1939 may_have_exposed_new_symbols
= true;
1942 /* Check for redundant computations. Do this optimization only
1943 for assignments that have no volatile ops and conditionals. */
1944 may_optimize_p
= (!ann
->has_volatile_ops
1945 && ((TREE_CODE (stmt
) == RETURN_EXPR
1946 && TREE_OPERAND (stmt
, 0)
1947 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
1948 && ! (TREE_SIDE_EFFECTS
1949 (TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1))))
1950 || (TREE_CODE (stmt
) == MODIFY_EXPR
1951 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt
, 1)))
1952 || TREE_CODE (stmt
) == COND_EXPR
1953 || TREE_CODE (stmt
) == SWITCH_EXPR
));
1956 may_have_exposed_new_symbols
|= eliminate_redundant_computations (stmt
);
1958 /* Record any additional equivalences created by this statement. */
1959 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
1960 record_equivalences_from_stmt (stmt
,
1964 /* If STMT is a COND_EXPR and it was modified, then we may know
1965 where it goes. If that is the case, then mark the CFG as altered.
1967 This will cause us to later call remove_unreachable_blocks and
1968 cleanup_tree_cfg when it is safe to do so. It is not safe to
1969 clean things up here since removal of edges and such can trigger
1970 the removal of PHI nodes, which in turn can release SSA_NAMEs to
1973 That's all fine and good, except that once SSA_NAMEs are released
1974 to the manager, we must not call create_ssa_name until all references
1975 to released SSA_NAMEs have been eliminated.
1977 All references to the deleted SSA_NAMEs can not be eliminated until
1978 we remove unreachable blocks.
1980 We can not remove unreachable blocks until after we have completed
1981 any queued jump threading.
1983 We can not complete any queued jump threads until we have taken
1984 appropriate variables out of SSA form. Taking variables out of
1985 SSA form can call create_ssa_name and thus we lose.
1987 Ultimately I suspect we're going to need to change the interface
1988 into the SSA_NAME manager. */
1994 if (TREE_CODE (stmt
) == COND_EXPR
)
1995 val
= COND_EXPR_COND (stmt
);
1996 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
1997 val
= SWITCH_COND (stmt
);
1999 if (val
&& TREE_CODE (val
) == INTEGER_CST
&& find_taken_edge (bb
, val
))
2002 /* If we simplified a statement in such a way as to be shown that it
2003 cannot trap, update the eh information and the cfg to match. */
2004 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
2006 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2008 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2012 if (may_have_exposed_new_symbols
)
2013 VEC_safe_push (tree
, heap
, stmts_to_rescan
, bsi_stmt (si
));
2016 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
2017 found, return its LHS. Otherwise insert STMT in the table and return
2020 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
2021 is also added to the stack pointed to by BLOCK_AVAIL_EXPRS_P, so that they
2022 can be removed when we finish processing this block and its children.
2024 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
2025 contains no CALL_EXPR on its RHS and makes no volatile nor
2026 aliased references. */
2029 lookup_avail_expr (tree stmt
, bool insert
)
2034 struct expr_hash_elt
*element
= XNEW (struct expr_hash_elt
);
2036 lhs
= TREE_CODE (stmt
) == MODIFY_EXPR
? TREE_OPERAND (stmt
, 0) : NULL
;
2038 initialize_hash_element (stmt
, lhs
, element
);
2040 /* Don't bother remembering constant assignments and copy operations.
2041 Constants and copy operations are handled by the constant/copy propagator
2042 in optimize_stmt. */
2043 if (TREE_CODE (element
->rhs
) == SSA_NAME
2044 || is_gimple_min_invariant (element
->rhs
))
2050 /* If this is an equality test against zero, see if we have recorded a
2051 nonzero value for the variable in question. */
2052 if ((TREE_CODE (element
->rhs
) == EQ_EXPR
2053 || TREE_CODE (element
->rhs
) == NE_EXPR
)
2054 && TREE_CODE (TREE_OPERAND (element
->rhs
, 0)) == SSA_NAME
2055 && integer_zerop (TREE_OPERAND (element
->rhs
, 1)))
2057 int indx
= SSA_NAME_VERSION (TREE_OPERAND (element
->rhs
, 0));
2059 if (bitmap_bit_p (nonzero_vars
, indx
))
2061 tree t
= element
->rhs
;
2063 return constant_boolean_node (TREE_CODE (t
) != EQ_EXPR
,
2068 /* Finally try to find the expression in the main expression hash table. */
2069 slot
= htab_find_slot_with_hash (avail_exprs
, element
, element
->hash
,
2070 (insert
? INSERT
: NO_INSERT
));
2079 *slot
= (void *) element
;
2080 VEC_safe_push (tree
, heap
, avail_exprs_stack
,
2081 stmt
? stmt
: element
->rhs
);
2085 /* Extract the LHS of the assignment so that it can be used as the current
2086 definition of another variable. */
2087 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
2089 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2090 use the value from the const_and_copies table. */
2091 if (TREE_CODE (lhs
) == SSA_NAME
)
2093 temp
= SSA_NAME_VALUE (lhs
);
2094 if (temp
&& TREE_CODE (temp
) != VALUE_HANDLE
)
2102 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
2103 MODIFY_EXPR statements. We compute a value number for expressions using
2104 the code of the expression and the SSA numbers of its operands. */
2107 avail_expr_hash (const void *p
)
2109 tree stmt
= ((struct expr_hash_elt
*)p
)->stmt
;
2110 tree rhs
= ((struct expr_hash_elt
*)p
)->rhs
;
2115 /* iterative_hash_expr knows how to deal with any expression and
2116 deals with commutative operators as well, so just use it instead
2117 of duplicating such complexities here. */
2118 val
= iterative_hash_expr (rhs
, val
);
2120 /* If the hash table entry is not associated with a statement, then we
2121 can just hash the expression and not worry about virtual operands
2123 if (!stmt
|| !stmt_ann (stmt
))
2126 /* Add the SSA version numbers of every vuse operand. This is important
2127 because compound variables like arrays are not renamed in the
2128 operands. Rather, the rename is done on the virtual variable
2129 representing all the elements of the array. */
2130 FOR_EACH_SSA_TREE_OPERAND (vuse
, stmt
, iter
, SSA_OP_VUSE
)
2131 val
= iterative_hash_expr (vuse
, val
);
2137 real_avail_expr_hash (const void *p
)
2139 return ((const struct expr_hash_elt
*)p
)->hash
;
2143 avail_expr_eq (const void *p1
, const void *p2
)
2145 tree stmt1
= ((struct expr_hash_elt
*)p1
)->stmt
;
2146 tree rhs1
= ((struct expr_hash_elt
*)p1
)->rhs
;
2147 tree stmt2
= ((struct expr_hash_elt
*)p2
)->stmt
;
2148 tree rhs2
= ((struct expr_hash_elt
*)p2
)->rhs
;
2150 /* If they are the same physical expression, return true. */
2151 if (rhs1
== rhs2
&& stmt1
== stmt2
)
2154 /* If their codes are not equal, then quit now. */
2155 if (TREE_CODE (rhs1
) != TREE_CODE (rhs2
))
2158 /* In case of a collision, both RHS have to be identical and have the
2159 same VUSE operands. */
2160 if ((TREE_TYPE (rhs1
) == TREE_TYPE (rhs2
)
2161 || lang_hooks
.types_compatible_p (TREE_TYPE (rhs1
), TREE_TYPE (rhs2
)))
2162 && operand_equal_p (rhs1
, rhs2
, OEP_PURE_SAME
))
2164 bool ret
= compare_ssa_operands_equal (stmt1
, stmt2
, SSA_OP_VUSE
);
2165 gcc_assert (!ret
|| ((struct expr_hash_elt
*)p1
)->hash
2166 == ((struct expr_hash_elt
*)p2
)->hash
);