1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
31 #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"
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
;
78 /* If we can thread this edge this field records the new target. */
79 edge redirection_target
;
83 /* Hash table with expressions made available during the renaming process.
84 When an assignment of the form X_i = EXPR is found, the statement is
85 stored in this table. If the same expression EXPR is later found on the
86 RHS of another statement, it is replaced with X_i (thus performing
87 global redundancy elimination). Similarly as we pass through conditionals
88 we record the conditional itself as having either a true or false value
90 static htab_t avail_exprs
;
92 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
93 expressions it enters into the hash table along with a marker entry
94 (null). When we finish processing the block, we pop off entries and
95 remove the expressions from the global hash table until we hit the
97 static VEC(tree_on_heap
) *avail_exprs_stack
;
99 /* Stack of trees used to restore the global currdefs to its original
100 state after completing optimization of a block and its dominator children.
102 An SSA_NAME indicates that the current definition of the underlying
103 variable should be set to the given SSA_NAME.
105 A _DECL node indicates that the underlying variable has no current
108 A NULL node is used to mark the last node associated with the
110 static VEC(tree_on_heap
) *block_defs_stack
;
112 /* Stack of statements we need to rescan during finalization for newly
115 Statement rescanning must occur after the current block's available
116 expressions are removed from AVAIL_EXPRS. Else we may change the
117 hash code for an expression and be unable to find/remove it from
119 static VEC(tree_on_heap
) *stmts_to_rescan
;
121 /* Structure for entries in the expression hash table.
123 This requires more memory for the hash table entries, but allows us
124 to avoid creating silly tree nodes and annotations for conditionals,
125 eliminates 2 global hash tables and two block local varrays.
127 It also allows us to reduce the number of hash table lookups we
128 have to perform in lookup_avail_expr and finally it allows us to
129 significantly reduce the number of calls into the hashing routine
134 /* The value (lhs) of this expression. */
137 /* The expression (rhs) we want to record. */
140 /* The annotation if this element corresponds to a statement. */
143 /* The hash value for RHS/ann. */
147 /* Stack of dest,src pairs that need to be restored during finalization.
149 A NULL entry is used to mark the end of pairs which need to be
150 restored during finalization of this block. */
151 static VEC(tree_on_heap
) *const_and_copies_stack
;
153 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
154 know their exact value. */
155 static bitmap nonzero_vars
;
157 /* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
158 when the current block is finalized.
160 A NULL entry is used to mark the end of names needing their
161 entry in NONZERO_VARS cleared during finalization of this block. */
162 static VEC(tree_on_heap
) *nonzero_vars_stack
;
164 /* Track whether or not we have changed the control flow graph. */
165 static bool cfg_altered
;
167 /* Bitmap of blocks that have had EH statements cleaned. We should
168 remove their dead edges eventually. */
169 static bitmap need_eh_cleanup
;
171 /* Statistics for dominator optimizations. */
175 long num_exprs_considered
;
179 static struct opt_stats_d opt_stats
;
181 /* Value range propagation record. Each time we encounter a conditional
182 of the form SSA_NAME COND CONST we create a new vrp_element to record
183 how the condition affects the possible values SSA_NAME may have.
185 Each record contains the condition tested (COND), and the range of
186 values the variable may legitimately have if COND is true. Note the
187 range of values may be a smaller range than COND specifies if we have
188 recorded other ranges for this variable. Each record also contains the
189 block in which the range was recorded for invalidation purposes.
191 Note that the current known range is computed lazily. This allows us
192 to avoid the overhead of computing ranges which are never queried.
194 When we encounter a conditional, we look for records which constrain
195 the SSA_NAME used in the condition. In some cases those records allow
196 us to determine the condition's result at compile time. In other cases
197 they may allow us to simplify the condition.
199 We also use value ranges to do things like transform signed div/mod
200 operations into unsigned div/mod or to simplify ABS_EXPRs.
202 Simple experiments have shown these optimizations to not be all that
203 useful on switch statements (much to my surprise). So switch statement
204 optimizations are not performed.
206 Note carefully we do not propagate information through each statement
207 in the block. i.e., if we know variable X has a value defined of
208 [0, 25] and we encounter Y = X + 1, we do not track a value range
209 for Y (which would be [1, 26] if we cared). Similarly we do not
210 constrain values as we encounter narrowing typecasts, etc. */
214 /* The highest and lowest values the variable in COND may contain when
215 COND is true. Note this may not necessarily be the same values
216 tested by COND if the same variable was used in earlier conditionals.
218 Note this is computed lazily and thus can be NULL indicating that
219 the values have not been computed yet. */
223 /* The actual conditional we recorded. This is needed since we compute
227 /* The basic block where this record was created. We use this to determine
228 when to remove records. */
232 /* A hash table holding value range records (VRP_ELEMENTs) for a given
233 SSA_NAME. We used to use a varray indexed by SSA_NAME_VERSION, but
234 that gets awful wasteful, particularly since the density objects
235 with useful information is very low. */
236 static htab_t vrp_data
;
238 /* An entry in the VRP_DATA hash table. We record the variable and a
239 varray of VRP_ELEMENT records associated with that variable. */
246 /* Array of variables which have their values constrained by operations
247 in this basic block. We use this during finalization to know
248 which variables need their VRP data updated. */
250 /* Stack of SSA_NAMEs which had their values constrained by operations
251 in this basic block. During finalization of this block we use this
252 list to determine which variables need their VRP data updated.
254 A NULL entry marks the end of the SSA_NAMEs associated with this block. */
255 static VEC(tree_on_heap
) *vrp_variables_stack
;
263 /* Local functions. */
264 static void optimize_stmt (struct dom_walk_data
*,
266 block_stmt_iterator
);
267 static tree
lookup_avail_expr (tree
, bool);
268 static hashval_t
vrp_hash (const void *);
269 static int vrp_eq (const void *, const void *);
270 static hashval_t
avail_expr_hash (const void *);
271 static hashval_t
real_avail_expr_hash (const void *);
272 static int avail_expr_eq (const void *, const void *);
273 static void htab_statistics (FILE *, htab_t
);
274 static void record_cond (tree
, tree
);
275 static void record_const_or_copy (tree
, tree
);
276 static void record_equality (tree
, tree
);
277 static tree
update_rhs_and_lookup_avail_expr (tree
, tree
, bool);
278 static tree
simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*,
280 static tree
simplify_cond_and_lookup_avail_expr (tree
, stmt_ann_t
, int);
281 static tree
simplify_switch_and_lookup_avail_expr (tree
, int);
282 static tree
find_equivalent_equality_comparison (tree
);
283 static void record_range (tree
, basic_block
);
284 static bool extract_range_from_cond (tree
, tree
*, tree
*, int *);
285 static void record_equivalences_from_phis (basic_block
);
286 static void record_equivalences_from_incoming_edge (basic_block
);
287 static bool eliminate_redundant_computations (struct dom_walk_data
*,
289 static void record_equivalences_from_stmt (tree
, int, stmt_ann_t
);
290 static void thread_across_edge (struct dom_walk_data
*, edge
);
291 static void dom_opt_finalize_block (struct dom_walk_data
*, basic_block
);
292 static void dom_opt_initialize_block (struct dom_walk_data
*, basic_block
);
293 static void propagate_to_outgoing_edges (struct dom_walk_data
*, basic_block
);
294 static void remove_local_expressions_from_table (void);
295 static void restore_vars_to_original_value (void);
296 static void restore_currdefs_to_original_value (void);
297 static void register_definitions_for_stmt (tree
);
298 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
299 static void restore_nonzero_vars_to_original_value (void);
300 static inline bool unsafe_associative_fp_binop (tree
);
302 /* Local version of fold that doesn't introduce cruft. */
309 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
310 may have been added by fold, and "useless" type conversions that might
311 now be apparent due to propagation. */
312 STRIP_USELESS_TYPE_CONVERSION (t
);
317 /* Allocate an EDGE_INFO for edge E and attach it to E.
318 Return the new EDGE_INFO structure. */
320 static struct edge_info
*
321 allocate_edge_info (edge e
)
323 struct edge_info
*edge_info
;
325 edge_info
= xcalloc (1, sizeof (struct edge_info
));
331 /* Free all EDGE_INFO structures associated with edges in the CFG.
332 If a particular edge can be threaded, copy the redirection
333 target from the EDGE_INFO structure into the edge's AUX field
334 as required by code to update the CFG and SSA graph for
338 free_all_edge_infos (void)
346 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
348 struct edge_info
*edge_info
= e
->aux
;
352 e
->aux
= edge_info
->redirection_target
;
353 if (edge_info
->cond_equivalences
)
354 free (edge_info
->cond_equivalences
);
361 /* Jump threading, redundancy elimination and const/copy propagation.
363 This pass may expose new symbols that need to be renamed into SSA. For
364 every new symbol exposed, its corresponding bit will be set in
368 tree_ssa_dominator_optimize (void)
370 struct dom_walk_data walk_data
;
372 struct loops loops_info
;
374 memset (&opt_stats
, 0, sizeof (opt_stats
));
376 for (i
= 0; i
< num_referenced_vars
; i
++)
377 var_ann (referenced_var (i
))->current_def
= NULL
;
379 /* Create our hash tables. */
380 avail_exprs
= htab_create (1024, real_avail_expr_hash
, avail_expr_eq
, free
);
381 vrp_data
= htab_create (ceil_log2 (num_ssa_names
), vrp_hash
, vrp_eq
, free
);
382 avail_exprs_stack
= VEC_alloc (tree_on_heap
, 20);
383 block_defs_stack
= VEC_alloc (tree_on_heap
, 20);
384 const_and_copies_stack
= VEC_alloc (tree_on_heap
, 20);
385 nonzero_vars_stack
= VEC_alloc (tree_on_heap
, 20);
386 vrp_variables_stack
= VEC_alloc (tree_on_heap
, 20);
387 stmts_to_rescan
= VEC_alloc (tree_on_heap
, 20);
388 nonzero_vars
= BITMAP_ALLOC (NULL
);
389 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
391 /* Setup callbacks for the generic dominator tree walker. */
392 walk_data
.walk_stmts_backward
= false;
393 walk_data
.dom_direction
= CDI_DOMINATORS
;
394 walk_data
.initialize_block_local_data
= NULL
;
395 walk_data
.before_dom_children_before_stmts
= dom_opt_initialize_block
;
396 walk_data
.before_dom_children_walk_stmts
= optimize_stmt
;
397 walk_data
.before_dom_children_after_stmts
= propagate_to_outgoing_edges
;
398 walk_data
.after_dom_children_before_stmts
= NULL
;
399 walk_data
.after_dom_children_walk_stmts
= NULL
;
400 walk_data
.after_dom_children_after_stmts
= dom_opt_finalize_block
;
401 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
402 When we attach more stuff we'll need to fill this out with a real
404 walk_data
.global_data
= NULL
;
405 walk_data
.block_local_data_size
= 0;
407 /* Now initialize the dominator walker. */
408 init_walk_dominator_tree (&walk_data
);
410 calculate_dominance_info (CDI_DOMINATORS
);
412 /* We need to know which edges exit loops so that we can
413 aggressively thread through loop headers to an exit
415 flow_loops_find (&loops_info
);
416 mark_loop_exit_edges (&loops_info
);
417 flow_loops_free (&loops_info
);
419 /* Clean up the CFG so that any forwarder blocks created by loop
420 canonicalization are removed. */
423 /* If we prove certain blocks are unreachable, then we want to
424 repeat the dominator optimization process as PHI nodes may
425 have turned into copies which allows better propagation of
426 values. So we repeat until we do not identify any new unreachable
430 /* Optimize the dominator tree. */
433 /* We need accurate information regarding back edges in the CFG
434 for jump threading. */
435 mark_dfs_back_edges ();
437 /* Recursively walk the dominator tree optimizing statements. */
438 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
440 /* If we exposed any new variables, go ahead and put them into
441 SSA form now, before we handle jump threading. This simplifies
442 interactions between rewriting of _DECL nodes into SSA form
443 and rewriting SSA_NAME nodes into SSA form after block
444 duplication and CFG manipulation. */
445 if (!bitmap_empty_p (vars_to_rename
))
447 rewrite_into_ssa (false);
448 bitmap_clear (vars_to_rename
);
451 free_all_edge_infos ();
453 /* Thread jumps, creating duplicate blocks as needed. */
454 cfg_altered
|= thread_through_all_blocks ();
456 /* Removal of statements may make some EH edges dead. Purge
457 such edges from the CFG as needed. */
458 if (!bitmap_empty_p (need_eh_cleanup
))
460 cfg_altered
|= tree_purge_all_dead_eh_edges (need_eh_cleanup
);
461 bitmap_zero (need_eh_cleanup
);
465 free_dominance_info (CDI_DOMINATORS
);
467 cfg_altered
|= cleanup_tree_cfg ();
469 if (rediscover_loops_after_threading
)
471 /* Rerun basic loop analysis to discover any newly
472 created loops and update the set of exit edges. */
473 rediscover_loops_after_threading
= false;
474 flow_loops_find (&loops_info
);
475 mark_loop_exit_edges (&loops_info
);
476 flow_loops_free (&loops_info
);
478 /* Remove any forwarder blocks inserted by loop
479 header canonicalization. */
483 calculate_dominance_info (CDI_DOMINATORS
);
485 rewrite_ssa_into_ssa ();
487 /* Reinitialize the various tables. */
488 bitmap_clear (nonzero_vars
);
489 htab_empty (avail_exprs
);
490 htab_empty (vrp_data
);
492 for (i
= 0; i
< num_referenced_vars
; i
++)
493 var_ann (referenced_var (i
))->current_def
= NULL
;
495 /* Finally, remove everything except invariants in SSA_NAME_VALUE.
497 This must be done before we iterate as we might have a
498 reference to an SSA_NAME which was removed by the call to
499 rewrite_ssa_into_ssa.
501 Long term we will be able to let everything in SSA_NAME_VALUE
502 persist. However, for now, we know this is the safe thing to do. */
503 for (i
= 0; i
< num_ssa_names
; i
++)
505 tree name
= ssa_name (i
);
511 value
= SSA_NAME_VALUE (name
);
512 if (value
&& !is_gimple_min_invariant (value
))
513 SSA_NAME_VALUE (name
) = NULL
;
516 while (optimize
> 1 && cfg_altered
);
518 /* Debugging dumps. */
519 if (dump_file
&& (dump_flags
& TDF_STATS
))
520 dump_dominator_optimization_stats (dump_file
);
522 /* We emptied the hash table earlier, now delete it completely. */
523 htab_delete (avail_exprs
);
524 htab_delete (vrp_data
);
526 /* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
527 CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
528 of the do-while loop above. */
530 /* And finalize the dominator walker. */
531 fini_walk_dominator_tree (&walk_data
);
533 /* Free nonzero_vars. */
534 BITMAP_FREE (nonzero_vars
);
535 BITMAP_FREE (need_eh_cleanup
);
537 VEC_free (tree_on_heap
, block_defs_stack
);
538 VEC_free (tree_on_heap
, avail_exprs_stack
);
539 VEC_free (tree_on_heap
, const_and_copies_stack
);
540 VEC_free (tree_on_heap
, nonzero_vars_stack
);
541 VEC_free (tree_on_heap
, vrp_variables_stack
);
542 VEC_free (tree_on_heap
, stmts_to_rescan
);
546 gate_dominator (void)
548 return flag_tree_dom
!= 0;
551 struct tree_opt_pass pass_dominator
=
554 gate_dominator
, /* gate */
555 tree_ssa_dominator_optimize
, /* execute */
558 0, /* static_pass_number */
559 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
560 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
561 0, /* properties_provided */
562 0, /* properties_destroyed */
563 0, /* todo_flags_start */
564 TODO_dump_func
| TODO_rename_vars
565 | TODO_verify_ssa
, /* todo_flags_finish */
570 /* We are exiting BB, see if the target block begins with a conditional
571 jump which has a known value when reached via BB. */
574 thread_across_edge (struct dom_walk_data
*walk_data
, edge e
)
576 block_stmt_iterator bsi
;
580 /* Each PHI creates a temporary equivalence, record them. */
581 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
583 tree src
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
584 tree dst
= PHI_RESULT (phi
);
586 /* If the desired argument is not the same as this PHI's result
587 and it is set by a PHI in this block, then we can not thread
588 through this block. */
590 && TREE_CODE (src
) == SSA_NAME
591 && TREE_CODE (SSA_NAME_DEF_STMT (src
)) == PHI_NODE
592 && bb_for_stmt (SSA_NAME_DEF_STMT (src
)) == e
->dest
)
595 record_const_or_copy (dst
, src
);
596 register_new_def (dst
, &block_defs_stack
);
599 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
601 tree lhs
, cached_lhs
;
603 stmt
= bsi_stmt (bsi
);
605 /* Ignore empty statements and labels. */
606 if (IS_EMPTY_STMT (stmt
) || TREE_CODE (stmt
) == LABEL_EXPR
)
609 /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
610 value, then stop our search here. Ideally when we stop a
611 search we stop on a COND_EXPR or SWITCH_EXPR. */
612 if (TREE_CODE (stmt
) != MODIFY_EXPR
613 || TREE_CODE (TREE_OPERAND (stmt
, 0)) != SSA_NAME
)
616 /* At this point we have a statement which assigns an RHS to an
617 SSA_VAR on the LHS. We want to prove that the RHS is already
618 available and that its value is held in the current definition
619 of the LHS -- meaning that this assignment is a NOP when
620 reached via edge E. */
621 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
)
622 cached_lhs
= TREE_OPERAND (stmt
, 1);
624 cached_lhs
= lookup_avail_expr (stmt
, false);
626 lhs
= TREE_OPERAND (stmt
, 0);
628 /* This can happen if we thread around to the start of a loop. */
629 if (lhs
== cached_lhs
)
632 /* If we did not find RHS in the hash table, then try again after
633 temporarily const/copy propagating the operands. */
636 /* Copy the operands. */
637 stmt_ann_t ann
= stmt_ann (stmt
);
638 use_optype uses
= USE_OPS (ann
);
639 vuse_optype vuses
= VUSE_OPS (ann
);
640 tree
*uses_copy
= xmalloc (NUM_USES (uses
) * sizeof (tree
));
641 tree
*vuses_copy
= xmalloc (NUM_VUSES (vuses
) * sizeof (tree
));
644 /* Make a copy of the uses into USES_COPY, then cprop into
646 for (i
= 0; i
< NUM_USES (uses
); i
++)
650 uses_copy
[i
] = USE_OP (uses
, i
);
651 if (TREE_CODE (USE_OP (uses
, i
)) == SSA_NAME
)
652 tmp
= SSA_NAME_VALUE (USE_OP (uses
, i
));
653 if (tmp
&& TREE_CODE (tmp
) != VALUE_HANDLE
)
654 SET_USE_OP (uses
, i
, tmp
);
657 /* Similarly for virtual uses. */
658 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
662 vuses_copy
[i
] = VUSE_OP (vuses
, i
);
663 if (TREE_CODE (VUSE_OP (vuses
, i
)) == SSA_NAME
)
664 tmp
= SSA_NAME_VALUE (VUSE_OP (vuses
, i
));
665 if (tmp
&& TREE_CODE (tmp
) != VALUE_HANDLE
)
666 SET_VUSE_OP (vuses
, i
, tmp
);
669 /* Try to lookup the new expression. */
670 cached_lhs
= lookup_avail_expr (stmt
, false);
672 /* Restore the statement's original uses/defs. */
673 for (i
= 0; i
< NUM_USES (uses
); i
++)
674 SET_USE_OP (uses
, i
, uses_copy
[i
]);
676 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
677 SET_VUSE_OP (vuses
, i
, vuses_copy
[i
]);
682 /* If we still did not find the expression in the hash table,
683 then we can not ignore this statement. */
688 /* If the expression in the hash table was not assigned to an
689 SSA_NAME, then we can not ignore this statement. */
690 if (TREE_CODE (cached_lhs
) != SSA_NAME
)
693 /* If we have different underlying variables, then we can not
694 ignore this statement. */
695 if (SSA_NAME_VAR (cached_lhs
) != SSA_NAME_VAR (lhs
))
698 /* If CACHED_LHS does not represent the current value of the underlying
699 variable in CACHED_LHS/LHS, then we can not ignore this statement. */
700 if (var_ann (SSA_NAME_VAR (lhs
))->current_def
!= cached_lhs
)
703 /* If we got here, then we can ignore this statement and continue
704 walking through the statements in the block looking for a threadable
707 We want to record an equivalence lhs = cache_lhs so that if
708 the result of this statement is used later we can copy propagate
710 record_const_or_copy (lhs
, cached_lhs
);
711 register_new_def (lhs
, &block_defs_stack
);
714 /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
715 arm will be taken. */
717 && (TREE_CODE (stmt
) == COND_EXPR
718 || TREE_CODE (stmt
) == SWITCH_EXPR
719 || TREE_CODE (stmt
) == GOTO_EXPR
))
721 tree cond
, cached_lhs
;
723 /* Now temporarily cprop the operands and try to find the resulting
724 expression in the hash tables. */
725 if (TREE_CODE (stmt
) == COND_EXPR
)
726 cond
= COND_EXPR_COND (stmt
);
727 else if (TREE_CODE (stmt
) == GOTO_EXPR
)
728 cond
= GOTO_DESTINATION (stmt
);
730 cond
= SWITCH_COND (stmt
);
732 if (COMPARISON_CLASS_P (cond
))
734 tree dummy_cond
, op0
, op1
;
735 enum tree_code cond_code
;
737 op0
= TREE_OPERAND (cond
, 0);
738 op1
= TREE_OPERAND (cond
, 1);
739 cond_code
= TREE_CODE (cond
);
741 /* Get the current value of both operands. */
742 if (TREE_CODE (op0
) == SSA_NAME
)
744 tree tmp
= SSA_NAME_VALUE (op0
);
745 if (tmp
&& TREE_CODE (tmp
) != VALUE_HANDLE
)
749 if (TREE_CODE (op1
) == SSA_NAME
)
751 tree tmp
= SSA_NAME_VALUE (op1
);
752 if (tmp
&& TREE_CODE (tmp
) != VALUE_HANDLE
)
756 /* Stuff the operator and operands into our dummy conditional
757 expression, creating the dummy conditional if necessary. */
758 dummy_cond
= walk_data
->global_data
;
761 dummy_cond
= build (cond_code
, boolean_type_node
, op0
, op1
);
762 dummy_cond
= build (COND_EXPR
, void_type_node
,
763 dummy_cond
, NULL
, NULL
);
764 walk_data
->global_data
= dummy_cond
;
768 TREE_SET_CODE (COND_EXPR_COND (dummy_cond
), cond_code
);
769 TREE_OPERAND (COND_EXPR_COND (dummy_cond
), 0) = op0
;
770 TREE_OPERAND (COND_EXPR_COND (dummy_cond
), 1) = op1
;
773 /* If the conditional folds to an invariant, then we are done,
774 otherwise look it up in the hash tables. */
775 cached_lhs
= local_fold (COND_EXPR_COND (dummy_cond
));
776 if (! is_gimple_min_invariant (cached_lhs
))
778 cached_lhs
= lookup_avail_expr (dummy_cond
, false);
779 if (!cached_lhs
|| ! is_gimple_min_invariant (cached_lhs
))
780 cached_lhs
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
785 /* We can have conditionals which just test the state of a
786 variable rather than use a relational operator. These are
787 simpler to handle. */
788 else if (TREE_CODE (cond
) == SSA_NAME
)
791 cached_lhs
= SSA_NAME_VALUE (cached_lhs
);
792 if (cached_lhs
&& ! is_gimple_min_invariant (cached_lhs
))
796 cached_lhs
= lookup_avail_expr (stmt
, false);
800 edge taken_edge
= find_taken_edge (e
->dest
, cached_lhs
);
801 basic_block dest
= (taken_edge
? taken_edge
->dest
: NULL
);
806 /* If we have a known destination for the conditional, then
807 we can perform this optimization, which saves at least one
808 conditional jump each time it applies since we get to
809 bypass the conditional at our original destination. */
812 struct edge_info
*edge_info
;
814 update_bb_profile_for_threading (e
->dest
, EDGE_FREQUENCY (e
),
815 e
->count
, taken_edge
);
819 edge_info
= allocate_edge_info (e
);
820 edge_info
->redirection_target
= taken_edge
;
821 bb_ann (e
->dest
)->incoming_edge_threaded
= true;
828 /* Initialize local stacks for this optimizer and record equivalences
829 upon entry to BB. Equivalences can come from the edge traversed to
830 reach BB or they may come from PHI nodes at the start of BB. */
833 dom_opt_initialize_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
837 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
839 /* Push a marker on the stacks of local information so that we know how
840 far to unwind when we finalize this block. */
841 VEC_safe_push (tree_on_heap
, avail_exprs_stack
, NULL_TREE
);
842 VEC_safe_push (tree_on_heap
, block_defs_stack
, NULL_TREE
);
843 VEC_safe_push (tree_on_heap
, const_and_copies_stack
, NULL_TREE
);
844 VEC_safe_push (tree_on_heap
, nonzero_vars_stack
, NULL_TREE
);
845 VEC_safe_push (tree_on_heap
, vrp_variables_stack
, NULL_TREE
);
847 record_equivalences_from_incoming_edge (bb
);
849 /* PHI nodes can create equivalences too. */
850 record_equivalences_from_phis (bb
);
853 /* Given an expression EXPR (a relational expression or a statement),
854 initialize the hash table element pointed by by ELEMENT. */
857 initialize_hash_element (tree expr
, tree lhs
, struct expr_hash_elt
*element
)
859 /* Hash table elements may be based on conditional expressions or statements.
861 For the former case, we have no annotation and we want to hash the
862 conditional expression. In the latter case we have an annotation and
863 we want to record the expression the statement evaluates. */
864 if (COMPARISON_CLASS_P (expr
) || TREE_CODE (expr
) == TRUTH_NOT_EXPR
)
869 else if (TREE_CODE (expr
) == COND_EXPR
)
871 element
->ann
= stmt_ann (expr
);
872 element
->rhs
= COND_EXPR_COND (expr
);
874 else if (TREE_CODE (expr
) == SWITCH_EXPR
)
876 element
->ann
= stmt_ann (expr
);
877 element
->rhs
= SWITCH_COND (expr
);
879 else if (TREE_CODE (expr
) == RETURN_EXPR
&& TREE_OPERAND (expr
, 0))
881 element
->ann
= stmt_ann (expr
);
882 element
->rhs
= TREE_OPERAND (TREE_OPERAND (expr
, 0), 1);
886 element
->ann
= stmt_ann (expr
);
887 element
->rhs
= TREE_OPERAND (expr
, 1);
891 element
->hash
= avail_expr_hash (element
);
894 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
895 LIMIT entries left in LOCALs. */
898 remove_local_expressions_from_table (void)
900 /* Remove all the expressions made available in this block. */
901 while (VEC_length (tree_on_heap
, avail_exprs_stack
) > 0)
903 struct expr_hash_elt element
;
904 tree expr
= VEC_pop (tree_on_heap
, avail_exprs_stack
);
906 if (expr
== NULL_TREE
)
909 initialize_hash_element (expr
, NULL
, &element
);
910 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
914 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
915 state, stopping when there are LIMIT entries left in LOCALs. */
918 restore_nonzero_vars_to_original_value (void)
920 while (VEC_length (tree_on_heap
, nonzero_vars_stack
) > 0)
922 tree name
= VEC_pop (tree_on_heap
, nonzero_vars_stack
);
927 bitmap_clear_bit (nonzero_vars
, SSA_NAME_VERSION (name
));
931 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
932 CONST_AND_COPIES to its original state, stopping when we hit a
936 restore_vars_to_original_value (void)
938 while (VEC_length (tree_on_heap
, const_and_copies_stack
) > 0)
940 tree prev_value
, dest
;
942 dest
= VEC_pop (tree_on_heap
, const_and_copies_stack
);
947 prev_value
= VEC_pop (tree_on_heap
, const_and_copies_stack
);
948 SSA_NAME_VALUE (dest
) = prev_value
;
952 /* Similar to restore_vars_to_original_value, except that it restores
953 CURRDEFS to its original value. */
955 restore_currdefs_to_original_value (void)
957 /* Restore CURRDEFS to its original state. */
958 while (VEC_length (tree_on_heap
, block_defs_stack
) > 0)
960 tree tmp
= VEC_pop (tree_on_heap
, block_defs_stack
);
963 if (tmp
== NULL_TREE
)
966 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
967 definition of its underlying variable. If we recorded anything
968 else, it must have been an _DECL node and its current reaching
969 definition must have been NULL. */
970 if (TREE_CODE (tmp
) == SSA_NAME
)
973 var
= SSA_NAME_VAR (saved_def
);
981 var_ann (var
)->current_def
= saved_def
;
985 /* We have finished processing the dominator children of BB, perform
986 any finalization actions in preparation for leaving this node in
987 the dominator tree. */
990 dom_opt_finalize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
994 /* If we are at a leaf node in the dominator tree, see if we can thread
995 the edge from BB through its successor.
997 Do this before we remove entries from our equivalence tables. */
998 if (EDGE_COUNT (bb
->succs
) == 1
999 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
1000 && (get_immediate_dominator (CDI_DOMINATORS
, EDGE_SUCC (bb
, 0)->dest
) != bb
1001 || phi_nodes (EDGE_SUCC (bb
, 0)->dest
)))
1004 thread_across_edge (walk_data
, EDGE_SUCC (bb
, 0));
1006 else if ((last
= last_stmt (bb
))
1007 && TREE_CODE (last
) == GOTO_EXPR
1008 && TREE_CODE (TREE_OPERAND (last
, 0)) == SSA_NAME
)
1013 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1015 thread_across_edge (walk_data
, e
);
1018 else if ((last
= last_stmt (bb
))
1019 && TREE_CODE (last
) == COND_EXPR
1020 && (COMPARISON_CLASS_P (COND_EXPR_COND (last
))
1021 || TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
)
1022 && EDGE_COUNT (bb
->succs
) == 2
1023 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
1024 && (EDGE_SUCC (bb
, 1)->flags
& EDGE_ABNORMAL
) == 0)
1026 edge true_edge
, false_edge
;
1028 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1030 /* If the THEN arm is the end of a dominator tree or has PHI nodes,
1031 then try to thread through its edge. */
1032 if (get_immediate_dominator (CDI_DOMINATORS
, true_edge
->dest
) != bb
1033 || phi_nodes (true_edge
->dest
))
1035 struct edge_info
*edge_info
;
1038 /* Push a marker onto the available expression stack so that we
1039 unwind any expressions related to the TRUE arm before processing
1040 the false arm below. */
1041 VEC_safe_push (tree_on_heap
, avail_exprs_stack
, NULL_TREE
);
1042 VEC_safe_push (tree_on_heap
, block_defs_stack
, NULL_TREE
);
1043 VEC_safe_push (tree_on_heap
, const_and_copies_stack
, NULL_TREE
);
1045 edge_info
= true_edge
->aux
;
1047 /* If we have info associated with this edge, record it into
1048 our equivalency tables. */
1051 tree
*cond_equivalences
= edge_info
->cond_equivalences
;
1052 tree lhs
= edge_info
->lhs
;
1053 tree rhs
= edge_info
->rhs
;
1055 /* If we have a simple NAME = VALUE equivalency record it.
1056 Until the jump threading selection code improves, only
1057 do this if both the name and value are SSA_NAMEs with
1058 the same underlying variable to avoid missing threading
1061 && TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
1062 && TREE_CODE (edge_info
->rhs
) == SSA_NAME
1063 && SSA_NAME_VAR (lhs
) == SSA_NAME_VAR (rhs
))
1064 record_const_or_copy (lhs
, rhs
);
1066 /* If we have 0 = COND or 1 = COND equivalences, record them
1067 into our expression hash tables. */
1068 if (cond_equivalences
)
1069 for (i
= 0; i
< edge_info
->max_cond_equivalences
; i
+= 2)
1071 tree expr
= cond_equivalences
[i
];
1072 tree value
= cond_equivalences
[i
+ 1];
1074 record_cond (expr
, value
);
1078 /* Now thread the edge. */
1079 thread_across_edge (walk_data
, true_edge
);
1081 /* And restore the various tables to their state before
1082 we threaded this edge. */
1083 remove_local_expressions_from_table ();
1084 restore_vars_to_original_value ();
1085 restore_currdefs_to_original_value ();
1088 /* Similarly for the ELSE arm. */
1089 if (get_immediate_dominator (CDI_DOMINATORS
, false_edge
->dest
) != bb
1090 || phi_nodes (false_edge
->dest
))
1092 struct edge_info
*edge_info
;
1095 edge_info
= false_edge
->aux
;
1097 /* If we have info associated with this edge, record it into
1098 our equivalency tables. */
1101 tree
*cond_equivalences
= edge_info
->cond_equivalences
;
1102 tree lhs
= edge_info
->lhs
;
1103 tree rhs
= edge_info
->rhs
;
1105 /* If we have a simple NAME = VALUE equivalency record it.
1106 Until the jump threading selection code improves, only
1107 do this if both the name and value are SSA_NAMEs with
1108 the same underlying variable to avoid missing threading
1111 && TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
)
1112 record_const_or_copy (lhs
, rhs
);
1114 /* If we have 0 = COND or 1 = COND equivalences, record them
1115 into our expression hash tables. */
1116 if (cond_equivalences
)
1117 for (i
= 0; i
< edge_info
->max_cond_equivalences
; i
+= 2)
1119 tree expr
= cond_equivalences
[i
];
1120 tree value
= cond_equivalences
[i
+ 1];
1122 record_cond (expr
, value
);
1126 thread_across_edge (walk_data
, false_edge
);
1128 /* No need to remove local expressions from our tables
1129 or restore vars to their original value as that will
1130 be done immediately below. */
1134 remove_local_expressions_from_table ();
1135 restore_nonzero_vars_to_original_value ();
1136 restore_vars_to_original_value ();
1137 restore_currdefs_to_original_value ();
1139 /* Remove VRP records associated with this basic block. They are no
1142 To be efficient, we note which variables have had their values
1143 constrained in this block. So walk over each variable in the
1144 VRP_VARIABLEs array. */
1145 while (VEC_length (tree_on_heap
, vrp_variables_stack
) > 0)
1147 tree var
= VEC_pop (tree_on_heap
, vrp_variables_stack
);
1148 struct vrp_hash_elt vrp_hash_elt
, *vrp_hash_elt_p
;
1151 /* Each variable has a stack of value range records. We want to
1152 invalidate those associated with our basic block. So we walk
1153 the array backwards popping off records associated with our
1154 block. Once we hit a record not associated with our block
1156 varray_type var_vrp_records
;
1161 vrp_hash_elt
.var
= var
;
1162 vrp_hash_elt
.records
= NULL
;
1164 slot
= htab_find_slot (vrp_data
, &vrp_hash_elt
, NO_INSERT
);
1166 vrp_hash_elt_p
= (struct vrp_hash_elt
*) *slot
;
1167 var_vrp_records
= vrp_hash_elt_p
->records
;
1169 while (VARRAY_ACTIVE_SIZE (var_vrp_records
) > 0)
1171 struct vrp_element
*element
1172 = (struct vrp_element
*)VARRAY_TOP_GENERIC_PTR (var_vrp_records
);
1174 if (element
->bb
!= bb
)
1177 VARRAY_POP (var_vrp_records
);
1181 /* If we queued any statements to rescan in this block, then
1182 go ahead and rescan them now. */
1183 while (VEC_length (tree_on_heap
, stmts_to_rescan
) > 0)
1185 tree stmt
= VEC_last (tree_on_heap
, stmts_to_rescan
);
1186 basic_block stmt_bb
= bb_for_stmt (stmt
);
1191 VEC_pop (tree_on_heap
, stmts_to_rescan
);
1192 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1196 /* PHI nodes can create equivalences too.
1198 Ignoring any alternatives which are the same as the result, if
1199 all the alternatives are equal, then the PHI node creates an
1202 Additionally, if all the PHI alternatives are known to have a nonzero
1203 value, then the result of this PHI is known to have a nonzero value,
1204 even if we do not know its exact value. */
1207 record_equivalences_from_phis (basic_block bb
)
1211 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1213 tree lhs
= PHI_RESULT (phi
);
1217 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1219 tree t
= PHI_ARG_DEF (phi
, i
);
1221 /* Ignore alternatives which are the same as our LHS. Since
1222 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1223 can simply compare pointers. */
1227 /* If we have not processed an alternative yet, then set
1228 RHS to this alternative. */
1231 /* If we have processed an alternative (stored in RHS), then
1232 see if it is equal to this one. If it isn't, then stop
1234 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
1238 /* If we had no interesting alternatives, then all the RHS alternatives
1239 must have been the same as LHS. */
1243 /* If we managed to iterate through each PHI alternative without
1244 breaking out of the loop, then we have a PHI which may create
1245 a useful equivalence. We do not need to record unwind data for
1246 this, since this is a true assignment and not an equivalence
1247 inferred from a comparison. All uses of this ssa name are dominated
1248 by this assignment, so unwinding just costs time and space. */
1249 if (i
== PHI_NUM_ARGS (phi
)
1250 && may_propagate_copy (lhs
, rhs
))
1251 SSA_NAME_VALUE (lhs
) = rhs
;
1253 /* Now see if we know anything about the nonzero property for the
1254 result of this PHI. */
1255 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1257 if (!PHI_ARG_NONZERO (phi
, i
))
1261 if (i
== PHI_NUM_ARGS (phi
))
1262 bitmap_set_bit (nonzero_vars
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1264 register_new_def (lhs
, &block_defs_stack
);
1268 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1269 return that edge. Otherwise return NULL. */
1271 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
1277 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1279 /* A loop back edge can be identified by the destination of
1280 the edge dominating the source of the edge. */
1281 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
1284 /* If we have already seen a non-loop edge, then we must have
1285 multiple incoming non-loop edges and thus we return NULL. */
1289 /* This is the first non-loop incoming edge we have found. Record
1297 /* Record any equivalences created by the incoming edge to BB. If BB
1298 has more than one incoming edge, then no equivalence is created. */
1301 record_equivalences_from_incoming_edge (basic_block bb
)
1305 struct edge_info
*edge_info
;
1307 /* If our parent block ended with a control statement, then we may be
1308 able to record some equivalences based on which outgoing edge from
1309 the parent was followed. */
1310 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1312 e
= single_incoming_edge_ignoring_loop_edges (bb
);
1314 /* If we had a single incoming edge from our parent block, then enter
1315 any data associated with the edge into our tables. */
1316 if (e
&& e
->src
== parent
)
1324 tree lhs
= edge_info
->lhs
;
1325 tree rhs
= edge_info
->rhs
;
1326 tree
*cond_equivalences
= edge_info
->cond_equivalences
;
1329 record_equality (lhs
, rhs
);
1331 if (cond_equivalences
)
1333 bool recorded_range
= false;
1334 for (i
= 0; i
< edge_info
->max_cond_equivalences
; i
+= 2)
1336 tree expr
= cond_equivalences
[i
];
1337 tree value
= cond_equivalences
[i
+ 1];
1339 record_cond (expr
, value
);
1341 /* For the first true equivalence, record range
1342 information. We only do this for the first
1343 true equivalence as it should dominate any
1344 later true equivalences. */
1345 if (! recorded_range
1346 && COMPARISON_CLASS_P (expr
)
1347 && value
== boolean_true_node
1348 && TREE_CONSTANT (TREE_OPERAND (expr
, 1)))
1350 record_range (expr
, bb
);
1351 recorded_range
= true;
1359 /* Dump SSA statistics on FILE. */
1362 dump_dominator_optimization_stats (FILE *file
)
1366 fprintf (file
, "Total number of statements: %6ld\n\n",
1367 opt_stats
.num_stmts
);
1368 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1369 opt_stats
.num_exprs_considered
);
1371 n_exprs
= opt_stats
.num_exprs_considered
;
1375 fprintf (file
, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
1376 opt_stats
.num_re
, PERCENT (opt_stats
.num_re
,
1379 fprintf (file
, "\nHash table statistics:\n");
1381 fprintf (file
, " avail_exprs: ");
1382 htab_statistics (file
, avail_exprs
);
1386 /* Dump SSA statistics on stderr. */
1389 debug_dominator_optimization_stats (void)
1391 dump_dominator_optimization_stats (stderr
);
1395 /* Dump statistics for the hash table HTAB. */
1398 htab_statistics (FILE *file
, htab_t htab
)
1400 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1401 (long) htab_size (htab
),
1402 (long) htab_elements (htab
),
1403 htab_collisions (htab
));
1406 /* Record the fact that VAR has a nonzero value, though we may not know
1407 its exact value. Note that if VAR is already known to have a nonzero
1408 value, then we do nothing. */
1411 record_var_is_nonzero (tree var
)
1413 int indx
= SSA_NAME_VERSION (var
);
1415 if (bitmap_bit_p (nonzero_vars
, indx
))
1418 /* Mark it in the global table. */
1419 bitmap_set_bit (nonzero_vars
, indx
);
1421 /* Record this SSA_NAME so that we can reset the global table
1422 when we leave this block. */
1423 VEC_safe_push (tree_on_heap
, nonzero_vars_stack
, var
);
1426 /* Enter a statement into the true/false expression hash table indicating
1427 that the condition COND has the value VALUE. */
1430 record_cond (tree cond
, tree value
)
1432 struct expr_hash_elt
*element
= xmalloc (sizeof (struct expr_hash_elt
));
1435 initialize_hash_element (cond
, value
, element
);
1437 slot
= htab_find_slot_with_hash (avail_exprs
, (void *)element
,
1438 element
->hash
, INSERT
);
1441 *slot
= (void *) element
;
1442 VEC_safe_push (tree_on_heap
, avail_exprs_stack
, cond
);
1448 /* Build a new conditional using NEW_CODE, OP0 and OP1 and store
1449 the new conditional into *p, then store a boolean_true_node
1453 build_and_record_new_cond (enum tree_code new_code
, tree op0
, tree op1
, tree
*p
)
1455 *p
= build2 (new_code
, boolean_type_node
, op0
, op1
);
1457 *p
= boolean_true_node
;
1460 /* Record that COND is true and INVERTED is false into the edge information
1461 structure. Also record that any conditions dominated by COND are true
1464 For example, if a < b is true, then a <= b must also be true. */
1467 record_conditions (struct edge_info
*edge_info
, tree cond
, tree inverted
)
1471 if (!COMPARISON_CLASS_P (cond
))
1474 op0
= TREE_OPERAND (cond
, 0);
1475 op1
= TREE_OPERAND (cond
, 1);
1477 switch (TREE_CODE (cond
))
1481 edge_info
->max_cond_equivalences
= 12;
1482 edge_info
->cond_equivalences
= xmalloc (12 * sizeof (tree
));
1483 build_and_record_new_cond ((TREE_CODE (cond
) == LT_EXPR
1484 ? LE_EXPR
: GE_EXPR
),
1485 op0
, op1
, &edge_info
->cond_equivalences
[4]);
1486 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1487 &edge_info
->cond_equivalences
[6]);
1488 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1489 &edge_info
->cond_equivalences
[8]);
1490 build_and_record_new_cond (LTGT_EXPR
, op0
, op1
,
1491 &edge_info
->cond_equivalences
[10]);
1496 edge_info
->max_cond_equivalences
= 6;
1497 edge_info
->cond_equivalences
= xmalloc (6 * sizeof (tree
));
1498 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1499 &edge_info
->cond_equivalences
[4]);
1503 edge_info
->max_cond_equivalences
= 10;
1504 edge_info
->cond_equivalences
= xmalloc (10 * sizeof (tree
));
1505 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1506 &edge_info
->cond_equivalences
[4]);
1507 build_and_record_new_cond (LE_EXPR
, op0
, op1
,
1508 &edge_info
->cond_equivalences
[6]);
1509 build_and_record_new_cond (GE_EXPR
, op0
, op1
,
1510 &edge_info
->cond_equivalences
[8]);
1513 case UNORDERED_EXPR
:
1514 edge_info
->max_cond_equivalences
= 16;
1515 edge_info
->cond_equivalences
= xmalloc (16 * sizeof (tree
));
1516 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1517 &edge_info
->cond_equivalences
[4]);
1518 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1519 &edge_info
->cond_equivalences
[6]);
1520 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1521 &edge_info
->cond_equivalences
[8]);
1522 build_and_record_new_cond (UNEQ_EXPR
, op0
, op1
,
1523 &edge_info
->cond_equivalences
[10]);
1524 build_and_record_new_cond (UNLT_EXPR
, op0
, op1
,
1525 &edge_info
->cond_equivalences
[12]);
1526 build_and_record_new_cond (UNGT_EXPR
, op0
, op1
,
1527 &edge_info
->cond_equivalences
[14]);
1532 edge_info
->max_cond_equivalences
= 8;
1533 edge_info
->cond_equivalences
= xmalloc (8 * sizeof (tree
));
1534 build_and_record_new_cond ((TREE_CODE (cond
) == UNLT_EXPR
1535 ? UNLE_EXPR
: UNGE_EXPR
),
1536 op0
, op1
, &edge_info
->cond_equivalences
[4]);
1537 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1538 &edge_info
->cond_equivalences
[6]);
1542 edge_info
->max_cond_equivalences
= 8;
1543 edge_info
->cond_equivalences
= xmalloc (8 * sizeof (tree
));
1544 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1545 &edge_info
->cond_equivalences
[4]);
1546 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1547 &edge_info
->cond_equivalences
[6]);
1551 edge_info
->max_cond_equivalences
= 8;
1552 edge_info
->cond_equivalences
= xmalloc (8 * sizeof (tree
));
1553 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1554 &edge_info
->cond_equivalences
[4]);
1555 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1556 &edge_info
->cond_equivalences
[6]);
1560 edge_info
->max_cond_equivalences
= 4;
1561 edge_info
->cond_equivalences
= xmalloc (4 * sizeof (tree
));
1565 /* Now store the original true and false conditions into the first
1567 edge_info
->cond_equivalences
[0] = cond
;
1568 edge_info
->cond_equivalences
[1] = boolean_true_node
;
1569 edge_info
->cond_equivalences
[2] = inverted
;
1570 edge_info
->cond_equivalences
[3] = boolean_false_node
;
1573 /* A helper function for record_const_or_copy and record_equality.
1574 Do the work of recording the value and undo info. */
1577 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
)
1579 SSA_NAME_VALUE (x
) = y
;
1581 VEC_safe_push (tree_on_heap
, const_and_copies_stack
, prev_x
);
1582 VEC_safe_push (tree_on_heap
, const_and_copies_stack
, x
);
1586 /* Return the loop depth of the basic block of the defining statement of X.
1587 This number should not be treated as absolutely correct because the loop
1588 information may not be completely up-to-date when dom runs. However, it
1589 will be relatively correct, and as more passes are taught to keep loop info
1590 up to date, the result will become more and more accurate. */
1593 loop_depth_of_name (tree x
)
1598 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1599 if (TREE_CODE (x
) != SSA_NAME
)
1602 /* Otherwise return the loop depth of the defining statement's bb.
1603 Note that there may not actually be a bb for this statement, if the
1604 ssa_name is live on entry. */
1605 defstmt
= SSA_NAME_DEF_STMT (x
);
1606 defbb
= bb_for_stmt (defstmt
);
1610 return defbb
->loop_depth
;
1614 /* Record that X is equal to Y in const_and_copies. Record undo
1615 information in the block-local vector. */
1618 record_const_or_copy (tree x
, tree y
)
1620 tree prev_x
= SSA_NAME_VALUE (x
);
1622 if (TREE_CODE (y
) == SSA_NAME
)
1624 tree tmp
= SSA_NAME_VALUE (y
);
1629 record_const_or_copy_1 (x
, y
, prev_x
);
1632 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1633 This constrains the cases in which we may treat this as assignment. */
1636 record_equality (tree x
, tree y
)
1638 tree prev_x
= NULL
, prev_y
= NULL
;
1640 if (TREE_CODE (x
) == SSA_NAME
)
1641 prev_x
= SSA_NAME_VALUE (x
);
1642 if (TREE_CODE (y
) == SSA_NAME
)
1643 prev_y
= SSA_NAME_VALUE (y
);
1645 /* If one of the previous values is invariant, or invariant in more loops
1646 (by depth), then use that.
1647 Otherwise it doesn't matter which value we choose, just so
1648 long as we canonicalize on one value. */
1649 if (TREE_INVARIANT (y
))
1651 else if (TREE_INVARIANT (x
) || (loop_depth_of_name (x
) <= loop_depth_of_name (y
)))
1652 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1653 else if (prev_x
&& TREE_INVARIANT (prev_x
))
1654 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1655 else if (prev_y
&& TREE_CODE (prev_y
) != VALUE_HANDLE
)
1658 /* After the swapping, we must have one SSA_NAME. */
1659 if (TREE_CODE (x
) != SSA_NAME
)
1662 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1663 variable compared against zero. If we're honoring signed zeros,
1664 then we cannot record this value unless we know that the value is
1666 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1667 && (TREE_CODE (y
) != REAL_CST
1668 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1671 record_const_or_copy_1 (x
, y
, prev_x
);
1674 /* Return true, if it is ok to do folding of an associative expression.
1675 EXP is the tree for the associative expression. */
1678 unsafe_associative_fp_binop (tree exp
)
1680 enum tree_code code
= TREE_CODE (exp
);
1681 return !(!flag_unsafe_math_optimizations
1682 && (code
== MULT_EXPR
|| code
== PLUS_EXPR
1683 || code
== MINUS_EXPR
)
1684 && FLOAT_TYPE_P (TREE_TYPE (exp
)));
1687 /* Returns true when STMT is a simple iv increment. It detects the
1688 following situation:
1690 i_1 = phi (..., i_2)
1691 i_2 = i_1 +/- ... */
1694 simple_iv_increment_p (tree stmt
)
1696 tree lhs
, rhs
, preinc
, phi
;
1699 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1702 lhs
= TREE_OPERAND (stmt
, 0);
1703 if (TREE_CODE (lhs
) != SSA_NAME
)
1706 rhs
= TREE_OPERAND (stmt
, 1);
1708 if (TREE_CODE (rhs
) != PLUS_EXPR
1709 && TREE_CODE (rhs
) != MINUS_EXPR
)
1712 preinc
= TREE_OPERAND (rhs
, 0);
1713 if (TREE_CODE (preinc
) != SSA_NAME
)
1716 phi
= SSA_NAME_DEF_STMT (preinc
);
1717 if (TREE_CODE (phi
) != PHI_NODE
)
1720 for (i
= 0; i
< (unsigned) PHI_NUM_ARGS (phi
); i
++)
1721 if (PHI_ARG_DEF (phi
, i
) == lhs
)
1727 /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
1728 hash tables. Try to simplify the RHS using whatever equivalences
1729 we may have recorded.
1731 If we are able to simplify the RHS, then lookup the simplified form in
1732 the hash table and return the result. Otherwise return NULL. */
1735 simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*walk_data
,
1736 tree stmt
, int insert
)
1738 tree rhs
= TREE_OPERAND (stmt
, 1);
1739 enum tree_code rhs_code
= TREE_CODE (rhs
);
1742 /* If we have lhs = ~x, look and see if we earlier had x = ~y.
1743 In which case we can change this statement to be lhs = y.
1744 Which can then be copy propagated.
1746 Similarly for negation. */
1747 if ((rhs_code
== BIT_NOT_EXPR
|| rhs_code
== NEGATE_EXPR
)
1748 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
1750 /* Get the definition statement for our RHS. */
1751 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1753 /* See if the RHS_DEF_STMT has the same form as our statement. */
1754 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
1755 && TREE_CODE (TREE_OPERAND (rhs_def_stmt
, 1)) == rhs_code
)
1757 tree rhs_def_operand
;
1759 rhs_def_operand
= TREE_OPERAND (TREE_OPERAND (rhs_def_stmt
, 1), 0);
1761 /* Verify that RHS_DEF_OPERAND is a suitable SSA variable. */
1762 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
1763 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
1764 result
= update_rhs_and_lookup_avail_expr (stmt
,
1770 /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
1771 If OP is associative, create and fold (y OP C2) OP C1 which
1772 should result in (y OP C3), use that as the RHS for the
1773 assignment. Add minus to this, as we handle it specially below. */
1774 if ((associative_tree_code (rhs_code
) || rhs_code
== MINUS_EXPR
)
1775 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
1776 && is_gimple_min_invariant (TREE_OPERAND (rhs
, 1)))
1778 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1780 /* If the statement defines an induction variable, do not propagate
1781 its value, so that we do not create overlapping life ranges. */
1782 if (simple_iv_increment_p (rhs_def_stmt
))
1783 goto dont_fold_assoc
;
1785 /* See if the RHS_DEF_STMT has the same form as our statement. */
1786 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
)
1788 tree rhs_def_rhs
= TREE_OPERAND (rhs_def_stmt
, 1);
1789 enum tree_code rhs_def_code
= TREE_CODE (rhs_def_rhs
);
1791 if ((rhs_code
== rhs_def_code
&& unsafe_associative_fp_binop (rhs
))
1792 || (rhs_code
== PLUS_EXPR
&& rhs_def_code
== MINUS_EXPR
)
1793 || (rhs_code
== MINUS_EXPR
&& rhs_def_code
== PLUS_EXPR
))
1795 tree def_stmt_op0
= TREE_OPERAND (rhs_def_rhs
, 0);
1796 tree def_stmt_op1
= TREE_OPERAND (rhs_def_rhs
, 1);
1798 if (TREE_CODE (def_stmt_op0
) == SSA_NAME
1799 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0
)
1800 && is_gimple_min_invariant (def_stmt_op1
))
1802 tree outer_const
= TREE_OPERAND (rhs
, 1);
1803 tree type
= TREE_TYPE (TREE_OPERAND (stmt
, 0));
1806 /* If we care about correct floating point results, then
1807 don't fold x + c1 - c2. Note that we need to take both
1808 the codes and the signs to figure this out. */
1809 if (FLOAT_TYPE_P (type
)
1810 && !flag_unsafe_math_optimizations
1811 && (rhs_def_code
== PLUS_EXPR
1812 || rhs_def_code
== MINUS_EXPR
))
1816 neg
^= (rhs_code
== MINUS_EXPR
);
1817 neg
^= (rhs_def_code
== MINUS_EXPR
);
1818 neg
^= real_isneg (TREE_REAL_CST_PTR (outer_const
));
1819 neg
^= real_isneg (TREE_REAL_CST_PTR (def_stmt_op1
));
1822 goto dont_fold_assoc
;
1825 /* Ho hum. So fold will only operate on the outermost
1826 thingy that we give it, so we have to build the new
1827 expression in two pieces. This requires that we handle
1828 combinations of plus and minus. */
1829 if (rhs_def_code
!= rhs_code
)
1831 if (rhs_def_code
== MINUS_EXPR
)
1832 t
= build (MINUS_EXPR
, type
, outer_const
, def_stmt_op1
);
1834 t
= build (MINUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1835 rhs_code
= PLUS_EXPR
;
1837 else if (rhs_def_code
== MINUS_EXPR
)
1838 t
= build (PLUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1840 t
= build (rhs_def_code
, type
, def_stmt_op1
, outer_const
);
1842 t
= build (rhs_code
, type
, def_stmt_op0
, t
);
1845 /* If the result is a suitable looking gimple expression,
1846 then use it instead of the original for STMT. */
1847 if (TREE_CODE (t
) == SSA_NAME
1848 || (UNARY_CLASS_P (t
)
1849 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
1850 || ((BINARY_CLASS_P (t
) || COMPARISON_CLASS_P (t
))
1851 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
1852 && is_gimple_val (TREE_OPERAND (t
, 1))))
1853 result
= update_rhs_and_lookup_avail_expr (stmt
, t
, insert
);
1860 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1861 and BIT_AND_EXPR respectively if the first operand is greater
1862 than zero and the second operand is an exact power of two. */
1863 if ((rhs_code
== TRUNC_DIV_EXPR
|| rhs_code
== TRUNC_MOD_EXPR
)
1864 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
1865 && integer_pow2p (TREE_OPERAND (rhs
, 1)))
1868 tree op
= TREE_OPERAND (rhs
, 0);
1870 if (TYPE_UNSIGNED (TREE_TYPE (op
)))
1872 val
= integer_one_node
;
1876 tree dummy_cond
= walk_data
->global_data
;
1880 dummy_cond
= build (GT_EXPR
, boolean_type_node
,
1881 op
, integer_zero_node
);
1882 dummy_cond
= build (COND_EXPR
, void_type_node
,
1883 dummy_cond
, NULL
, NULL
);
1884 walk_data
->global_data
= dummy_cond
;
1888 TREE_SET_CODE (COND_EXPR_COND (dummy_cond
), GT_EXPR
);
1889 TREE_OPERAND (COND_EXPR_COND (dummy_cond
), 0) = op
;
1890 TREE_OPERAND (COND_EXPR_COND (dummy_cond
), 1)
1891 = integer_zero_node
;
1893 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
, NULL
, false);
1896 if (val
&& integer_onep (val
))
1899 tree op0
= TREE_OPERAND (rhs
, 0);
1900 tree op1
= TREE_OPERAND (rhs
, 1);
1902 if (rhs_code
== TRUNC_DIV_EXPR
)
1903 t
= build (RSHIFT_EXPR
, TREE_TYPE (op0
), op0
,
1904 build_int_cst (NULL_TREE
, tree_log2 (op1
)));
1906 t
= build (BIT_AND_EXPR
, TREE_TYPE (op0
), op0
,
1907 local_fold (build (MINUS_EXPR
, TREE_TYPE (op1
),
1908 op1
, integer_one_node
)));
1910 result
= update_rhs_and_lookup_avail_expr (stmt
, t
, insert
);
1914 /* Transform ABS (X) into X or -X as appropriate. */
1915 if (rhs_code
== ABS_EXPR
1916 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
1919 tree op
= TREE_OPERAND (rhs
, 0);
1920 tree type
= TREE_TYPE (op
);
1922 if (TYPE_UNSIGNED (type
))
1924 val
= integer_zero_node
;
1928 tree dummy_cond
= walk_data
->global_data
;
1932 dummy_cond
= build (LE_EXPR
, boolean_type_node
,
1933 op
, integer_zero_node
);
1934 dummy_cond
= build (COND_EXPR
, void_type_node
,
1935 dummy_cond
, NULL
, NULL
);
1936 walk_data
->global_data
= dummy_cond
;
1940 TREE_SET_CODE (COND_EXPR_COND (dummy_cond
), LE_EXPR
);
1941 TREE_OPERAND (COND_EXPR_COND (dummy_cond
), 0) = op
;
1942 TREE_OPERAND (COND_EXPR_COND (dummy_cond
), 1)
1943 = build_int_cst (type
, 0);
1945 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
, NULL
, false);
1949 TREE_SET_CODE (COND_EXPR_COND (dummy_cond
), GE_EXPR
);
1950 TREE_OPERAND (COND_EXPR_COND (dummy_cond
), 0) = op
;
1951 TREE_OPERAND (COND_EXPR_COND (dummy_cond
), 1)
1952 = build_int_cst (type
, 0);
1954 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
1959 if (integer_zerop (val
))
1960 val
= integer_one_node
;
1961 else if (integer_onep (val
))
1962 val
= integer_zero_node
;
1968 && (integer_onep (val
) || integer_zerop (val
)))
1972 if (integer_onep (val
))
1973 t
= build1 (NEGATE_EXPR
, TREE_TYPE (op
), op
);
1977 result
= update_rhs_and_lookup_avail_expr (stmt
, t
, insert
);
1981 /* Optimize *"foo" into 'f'. This is done here rather than
1982 in fold to avoid problems with stuff like &*"foo". */
1983 if (TREE_CODE (rhs
) == INDIRECT_REF
|| TREE_CODE (rhs
) == ARRAY_REF
)
1985 tree t
= fold_read_from_constant_string (rhs
);
1988 result
= update_rhs_and_lookup_avail_expr (stmt
, t
, insert
);
1994 /* COND is a condition of the form:
1996 x == const or x != const
1998 Look back to x's defining statement and see if x is defined as
2002 If const is unchanged if we convert it to type, then we can build
2003 the equivalent expression:
2006 y == const or y != const
2008 Which may allow further optimizations.
2010 Return the equivalent comparison or NULL if no such equivalent comparison
2014 find_equivalent_equality_comparison (tree cond
)
2016 tree op0
= TREE_OPERAND (cond
, 0);
2017 tree op1
= TREE_OPERAND (cond
, 1);
2018 tree def_stmt
= SSA_NAME_DEF_STMT (op0
);
2020 /* OP0 might have been a parameter, so first make sure it
2021 was defined by a MODIFY_EXPR. */
2022 if (def_stmt
&& TREE_CODE (def_stmt
) == MODIFY_EXPR
)
2024 tree def_rhs
= TREE_OPERAND (def_stmt
, 1);
2026 /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
2027 if ((TREE_CODE (def_rhs
) == NOP_EXPR
2028 || TREE_CODE (def_rhs
) == CONVERT_EXPR
)
2029 && TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == SSA_NAME
)
2031 tree def_rhs_inner
= TREE_OPERAND (def_rhs
, 0);
2032 tree def_rhs_inner_type
= TREE_TYPE (def_rhs_inner
);
2035 if (TYPE_PRECISION (def_rhs_inner_type
)
2036 > TYPE_PRECISION (TREE_TYPE (def_rhs
)))
2039 /* What we want to prove is that if we convert OP1 to
2040 the type of the object inside the NOP_EXPR that the
2041 result is still equivalent to SRC.
2043 If that is true, the build and return new equivalent
2044 condition which uses the source of the typecast and the
2045 new constant (which has only changed its type). */
2046 new = build1 (TREE_CODE (def_rhs
), def_rhs_inner_type
, op1
);
2047 new = local_fold (new);
2048 if (is_gimple_val (new) && tree_int_cst_equal (new, op1
))
2049 return build (TREE_CODE (cond
), TREE_TYPE (cond
),
2050 def_rhs_inner
, new);
2056 /* STMT is a COND_EXPR for which we could not trivially determine its
2057 result. This routine attempts to find equivalent forms of the
2058 condition which we may be able to optimize better. It also
2059 uses simple value range propagation to optimize conditionals. */
2062 simplify_cond_and_lookup_avail_expr (tree stmt
,
2066 tree cond
= COND_EXPR_COND (stmt
);
2068 if (COMPARISON_CLASS_P (cond
))
2070 tree op0
= TREE_OPERAND (cond
, 0);
2071 tree op1
= TREE_OPERAND (cond
, 1);
2073 if (TREE_CODE (op0
) == SSA_NAME
&& is_gimple_min_invariant (op1
))
2076 tree low
, high
, cond_low
, cond_high
;
2077 int lowequal
, highequal
, swapped
, no_overlap
, subset
, cond_inverted
;
2078 varray_type vrp_records
;
2079 struct vrp_element
*element
;
2080 struct vrp_hash_elt vrp_hash_elt
, *vrp_hash_elt_p
;
2083 /* First see if we have test of an SSA_NAME against a constant
2084 where the SSA_NAME is defined by an earlier typecast which
2085 is irrelevant when performing tests against the given
2087 if (TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
2089 tree new_cond
= find_equivalent_equality_comparison (cond
);
2093 /* Update the statement to use the new equivalent
2095 COND_EXPR_COND (stmt
) = new_cond
;
2097 /* If this is not a real stmt, ann will be NULL and we
2098 avoid processing the operands. */
2102 /* Lookup the condition and return its known value if it
2104 new_cond
= lookup_avail_expr (stmt
, insert
);
2108 /* The operands have changed, so update op0 and op1. */
2109 op0
= TREE_OPERAND (cond
, 0);
2110 op1
= TREE_OPERAND (cond
, 1);
2114 /* Consult the value range records for this variable (if they exist)
2115 to see if we can eliminate or simplify this conditional.
2117 Note two tests are necessary to determine no records exist.
2118 First we have to see if the virtual array exists, if it
2119 exists, then we have to check its active size.
2121 Also note the vast majority of conditionals are not testing
2122 a variable which has had its range constrained by an earlier
2123 conditional. So this filter avoids a lot of unnecessary work. */
2124 vrp_hash_elt
.var
= op0
;
2125 vrp_hash_elt
.records
= NULL
;
2126 slot
= htab_find_slot (vrp_data
, &vrp_hash_elt
, NO_INSERT
);
2130 vrp_hash_elt_p
= (struct vrp_hash_elt
*) *slot
;
2131 vrp_records
= vrp_hash_elt_p
->records
;
2132 if (vrp_records
== NULL
)
2135 limit
= VARRAY_ACTIVE_SIZE (vrp_records
);
2137 /* If we have no value range records for this variable, or we are
2138 unable to extract a range for this condition, then there is
2141 || ! extract_range_from_cond (cond
, &cond_high
,
2142 &cond_low
, &cond_inverted
))
2145 /* We really want to avoid unnecessary computations of range
2146 info. So all ranges are computed lazily; this avoids a
2147 lot of unnecessary work. i.e., we record the conditional,
2148 but do not process how it constrains the variable's
2149 potential values until we know that processing the condition
2152 However, we do not want to have to walk a potentially long
2153 list of ranges, nor do we want to compute a variable's
2154 range more than once for a given path.
2156 Luckily, each time we encounter a conditional that can not
2157 be otherwise optimized we will end up here and we will
2158 compute the necessary range information for the variable
2159 used in this condition.
2161 Thus you can conclude that there will never be more than one
2162 conditional associated with a variable which has not been
2163 processed. So we never need to merge more than one new
2164 conditional into the current range.
2166 These properties also help us avoid unnecessary work. */
2168 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
, limit
- 1);
2170 if (element
->high
&& element
->low
)
2172 /* The last element has been processed, so there is no range
2173 merging to do, we can simply use the high/low values
2174 recorded in the last element. */
2176 high
= element
->high
;
2180 tree tmp_high
, tmp_low
;
2183 /* The last element has not been processed. Process it now.
2184 record_range should ensure for cond inverted is not set.
2185 This call can only fail if cond is x < min or x > max,
2186 which fold should have optimized into false.
2187 If that doesn't happen, just pretend all values are
2189 if (! extract_range_from_cond (element
->cond
, &tmp_high
,
2193 gcc_assert (dummy
== 0);
2195 /* If this is the only element, then no merging is necessary,
2196 the high/low values from extract_range_from_cond are all
2205 /* Get the high/low value from the previous element. */
2206 struct vrp_element
*prev
2207 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
,
2212 /* Merge in this element's range with the range from the
2215 The low value for the merged range is the maximum of
2216 the previous low value and the low value of this record.
2218 Similarly the high value for the merged range is the
2219 minimum of the previous high value and the high value of
2221 low
= (tree_int_cst_compare (low
, tmp_low
) == 1
2223 high
= (tree_int_cst_compare (high
, tmp_high
) == -1
2227 /* And record the computed range. */
2229 element
->high
= high
;
2233 /* After we have constrained this variable's potential values,
2234 we try to determine the result of the given conditional.
2236 To simplify later tests, first determine if the current
2237 low value is the same low value as the conditional.
2238 Similarly for the current high value and the high value
2239 for the conditional. */
2240 lowequal
= tree_int_cst_equal (low
, cond_low
);
2241 highequal
= tree_int_cst_equal (high
, cond_high
);
2243 if (lowequal
&& highequal
)
2244 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2246 /* To simplify the overlap/subset tests below we may want
2247 to swap the two ranges so that the larger of the two
2248 ranges occurs "first". */
2250 if (tree_int_cst_compare (low
, cond_low
) == 1
2252 && tree_int_cst_compare (cond_high
, high
) == 1))
2265 /* Now determine if there is no overlap in the ranges
2266 or if the second range is a subset of the first range. */
2267 no_overlap
= tree_int_cst_lt (high
, cond_low
);
2268 subset
= tree_int_cst_compare (cond_high
, high
) != 1;
2270 /* If there was no overlap in the ranges, then this conditional
2271 always has a false value (unless we had to invert this
2272 conditional, in which case it always has a true value). */
2274 return (cond_inverted
? boolean_true_node
: boolean_false_node
);
2276 /* If the current range is a subset of the condition's range,
2277 then this conditional always has a true value (unless we
2278 had to invert this conditional, in which case it always
2279 has a true value). */
2280 if (subset
&& swapped
)
2281 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2283 /* We were unable to determine the result of the conditional.
2284 However, we may be able to simplify the conditional. First
2285 merge the ranges in the same manner as range merging above. */
2286 low
= tree_int_cst_compare (low
, cond_low
) == 1 ? low
: cond_low
;
2287 high
= tree_int_cst_compare (high
, cond_high
) == -1 ? high
: cond_high
;
2289 /* If the range has converged to a single point, then turn this
2290 into an equality comparison. */
2291 if (TREE_CODE (cond
) != EQ_EXPR
2292 && TREE_CODE (cond
) != NE_EXPR
2293 && tree_int_cst_equal (low
, high
))
2295 TREE_SET_CODE (cond
, EQ_EXPR
);
2296 TREE_OPERAND (cond
, 1) = high
;
2303 /* STMT is a SWITCH_EXPR for which we could not trivially determine its
2304 result. This routine attempts to find equivalent forms of the
2305 condition which we may be able to optimize better. */
2308 simplify_switch_and_lookup_avail_expr (tree stmt
, int insert
)
2310 tree cond
= SWITCH_COND (stmt
);
2313 /* The optimization that we really care about is removing unnecessary
2314 casts. That will let us do much better in propagating the inferred
2315 constant at the switch target. */
2316 if (TREE_CODE (cond
) == SSA_NAME
)
2318 def
= SSA_NAME_DEF_STMT (cond
);
2319 if (TREE_CODE (def
) == MODIFY_EXPR
)
2321 def
= TREE_OPERAND (def
, 1);
2322 if (TREE_CODE (def
) == NOP_EXPR
)
2327 def
= TREE_OPERAND (def
, 0);
2329 #ifdef ENABLE_CHECKING
2330 /* ??? Why was Jeff testing this? We are gimple... */
2331 gcc_assert (is_gimple_val (def
));
2334 to
= TREE_TYPE (cond
);
2335 ti
= TREE_TYPE (def
);
2337 /* If we have an extension that preserves value, then we
2338 can copy the source value into the switch. */
2340 need_precision
= TYPE_PRECISION (ti
);
2342 if (TYPE_UNSIGNED (to
) && !TYPE_UNSIGNED (ti
))
2344 else if (!TYPE_UNSIGNED (to
) && TYPE_UNSIGNED (ti
))
2345 need_precision
+= 1;
2346 if (TYPE_PRECISION (to
) < need_precision
)
2351 SWITCH_COND (stmt
) = def
;
2354 return lookup_avail_expr (stmt
, insert
);
2364 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2365 known value for that SSA_NAME (or NULL if no value is known).
2367 NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
2368 even if we don't know their precise value.
2370 Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
2371 nodes of the successors of BB. */
2374 cprop_into_successor_phis (basic_block bb
, bitmap nonzero_vars
)
2379 /* This can get rather expensive if the implementation is naive in
2380 how it finds the phi alternative associated with a particular edge. */
2381 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2386 /* If this is an abnormal edge, then we do not want to copy propagate
2387 into the PHI alternative associated with this edge. */
2388 if (e
->flags
& EDGE_ABNORMAL
)
2391 phi
= phi_nodes (e
->dest
);
2396 for ( ; phi
; phi
= PHI_CHAIN (phi
))
2399 use_operand_p orig_p
;
2402 /* The alternative may be associated with a constant, so verify
2403 it is an SSA_NAME before doing anything with it. */
2404 orig_p
= PHI_ARG_DEF_PTR (phi
, indx
);
2405 orig
= USE_FROM_PTR (orig_p
);
2406 if (TREE_CODE (orig
) != SSA_NAME
)
2409 /* If the alternative is known to have a nonzero value, record
2410 that fact in the PHI node itself for future use. */
2411 if (bitmap_bit_p (nonzero_vars
, SSA_NAME_VERSION (orig
)))
2412 PHI_ARG_NONZERO (phi
, indx
) = true;
2414 /* If we have *ORIG_P in our constant/copy table, then replace
2415 ORIG_P with its value in our constant/copy table. */
2416 new = SSA_NAME_VALUE (orig
);
2418 && (TREE_CODE (new) == SSA_NAME
2419 || is_gimple_min_invariant (new))
2420 && may_propagate_copy (orig
, new))
2422 propagate_value (orig_p
, new);
2428 /* We have finished optimizing BB, record any information implied by
2429 taking a specific outgoing edge from BB. */
2432 record_edge_info (basic_block bb
)
2434 block_stmt_iterator bsi
= bsi_last (bb
);
2435 struct edge_info
*edge_info
;
2437 if (! bsi_end_p (bsi
))
2439 tree stmt
= bsi_stmt (bsi
);
2441 if (stmt
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
2443 tree cond
= SWITCH_COND (stmt
);
2445 if (TREE_CODE (cond
) == SSA_NAME
)
2447 tree labels
= SWITCH_LABELS (stmt
);
2448 int i
, n_labels
= TREE_VEC_LENGTH (labels
);
2449 tree
*info
= xcalloc (n_basic_blocks
, sizeof (tree
));
2453 for (i
= 0; i
< n_labels
; i
++)
2455 tree label
= TREE_VEC_ELT (labels
, i
);
2456 basic_block target_bb
= label_to_block (CASE_LABEL (label
));
2458 if (CASE_HIGH (label
)
2459 || !CASE_LOW (label
)
2460 || info
[target_bb
->index
])
2461 info
[target_bb
->index
] = error_mark_node
;
2463 info
[target_bb
->index
] = label
;
2466 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2468 basic_block target_bb
= e
->dest
;
2469 tree node
= info
[target_bb
->index
];
2471 if (node
!= NULL
&& node
!= error_mark_node
)
2473 tree x
= fold_convert (TREE_TYPE (cond
), CASE_LOW (node
));
2474 edge_info
= allocate_edge_info (e
);
2475 edge_info
->lhs
= cond
;
2483 /* A COND_EXPR may create equivalences too. */
2484 if (stmt
&& TREE_CODE (stmt
) == COND_EXPR
)
2486 tree cond
= COND_EXPR_COND (stmt
);
2490 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
2492 /* If the conditional is a single variable 'X', record 'X = 1'
2493 for the true edge and 'X = 0' on the false edge. */
2494 if (SSA_VAR_P (cond
))
2496 struct edge_info
*edge_info
;
2498 edge_info
= allocate_edge_info (true_edge
);
2499 edge_info
->lhs
= cond
;
2500 edge_info
->rhs
= constant_boolean_node (1, TREE_TYPE (cond
));
2502 edge_info
= allocate_edge_info (false_edge
);
2503 edge_info
->lhs
= cond
;
2504 edge_info
->rhs
= constant_boolean_node (0, TREE_TYPE (cond
));
2506 /* Equality tests may create one or two equivalences. */
2507 else if (COMPARISON_CLASS_P (cond
))
2509 tree op0
= TREE_OPERAND (cond
, 0);
2510 tree op1
= TREE_OPERAND (cond
, 1);
2512 /* Special case comparing booleans against a constant as we
2513 know the value of OP0 on both arms of the branch. i.e., we
2514 can record an equivalence for OP0 rather than COND. */
2515 if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
2516 && TREE_CODE (op0
) == SSA_NAME
2517 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
2518 && is_gimple_min_invariant (op1
))
2520 if (TREE_CODE (cond
) == EQ_EXPR
)
2522 edge_info
= allocate_edge_info (true_edge
);
2523 edge_info
->lhs
= op0
;
2524 edge_info
->rhs
= (integer_zerop (op1
)
2525 ? boolean_false_node
2526 : boolean_true_node
);
2528 edge_info
= allocate_edge_info (false_edge
);
2529 edge_info
->lhs
= op0
;
2530 edge_info
->rhs
= (integer_zerop (op1
)
2532 : boolean_false_node
);
2536 edge_info
= allocate_edge_info (true_edge
);
2537 edge_info
->lhs
= op0
;
2538 edge_info
->rhs
= (integer_zerop (op1
)
2540 : boolean_false_node
);
2542 edge_info
= allocate_edge_info (false_edge
);
2543 edge_info
->lhs
= op0
;
2544 edge_info
->rhs
= (integer_zerop (op1
)
2545 ? boolean_false_node
2546 : boolean_true_node
);
2550 else if (is_gimple_min_invariant (op0
)
2551 && (TREE_CODE (op1
) == SSA_NAME
2552 || is_gimple_min_invariant (op1
)))
2554 tree inverted
= invert_truthvalue (cond
);
2555 struct edge_info
*edge_info
;
2557 edge_info
= allocate_edge_info (true_edge
);
2558 record_conditions (edge_info
, cond
, inverted
);
2560 if (TREE_CODE (cond
) == EQ_EXPR
)
2562 edge_info
->lhs
= op1
;
2563 edge_info
->rhs
= op0
;
2566 edge_info
= allocate_edge_info (false_edge
);
2567 record_conditions (edge_info
, inverted
, cond
);
2569 if (TREE_CODE (cond
) == NE_EXPR
)
2571 edge_info
->lhs
= op1
;
2572 edge_info
->rhs
= op0
;
2576 else if (TREE_CODE (op0
) == SSA_NAME
2577 && (is_gimple_min_invariant (op1
)
2578 || TREE_CODE (op1
) == SSA_NAME
))
2580 tree inverted
= invert_truthvalue (cond
);
2581 struct edge_info
*edge_info
;
2583 edge_info
= allocate_edge_info (true_edge
);
2584 record_conditions (edge_info
, cond
, inverted
);
2586 if (TREE_CODE (cond
) == EQ_EXPR
)
2588 edge_info
->lhs
= op0
;
2589 edge_info
->rhs
= op1
;
2592 edge_info
= allocate_edge_info (false_edge
);
2593 record_conditions (edge_info
, inverted
, cond
);
2595 if (TREE_CODE (cond
) == NE_EXPR
)
2597 edge_info
->lhs
= op0
;
2598 edge_info
->rhs
= op1
;
2603 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
2608 /* Propagate information from BB to its outgoing edges.
2610 This can include equivalency information implied by control statements
2611 at the end of BB and const/copy propagation into PHIs in BB's
2612 successor blocks. */
2615 propagate_to_outgoing_edges (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
2619 record_edge_info (bb
);
2620 cprop_into_successor_phis (bb
, nonzero_vars
);
2623 /* Search for redundant computations in STMT. If any are found, then
2624 replace them with the variable holding the result of the computation.
2626 If safe, record this expression into the available expression hash
2630 eliminate_redundant_computations (struct dom_walk_data
*walk_data
,
2631 tree stmt
, stmt_ann_t ann
)
2633 v_may_def_optype v_may_defs
= V_MAY_DEF_OPS (ann
);
2634 tree
*expr_p
, def
= NULL_TREE
;
2637 bool retval
= false;
2639 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2640 def
= TREE_OPERAND (stmt
, 0);
2642 /* Certain expressions on the RHS can be optimized away, but can not
2643 themselves be entered into the hash tables. */
2644 if (ann
->makes_aliased_stores
2646 || TREE_CODE (def
) != SSA_NAME
2647 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
2648 || NUM_V_MAY_DEFS (v_may_defs
) != 0
2649 /* Do not record equivalences for increments of ivs. This would create
2650 overlapping live ranges for a very questionable gain. */
2651 || simple_iv_increment_p (stmt
))
2654 /* Check if the expression has been computed before. */
2655 cached_lhs
= lookup_avail_expr (stmt
, insert
);
2657 /* If this is an assignment and the RHS was not in the hash table,
2658 then try to simplify the RHS and lookup the new RHS in the
2660 if (! cached_lhs
&& TREE_CODE (stmt
) == MODIFY_EXPR
)
2661 cached_lhs
= simplify_rhs_and_lookup_avail_expr (walk_data
, stmt
, insert
);
2662 /* Similarly if this is a COND_EXPR and we did not find its
2663 expression in the hash table, simplify the condition and
2665 else if (! cached_lhs
&& TREE_CODE (stmt
) == COND_EXPR
)
2666 cached_lhs
= simplify_cond_and_lookup_avail_expr (stmt
, ann
, insert
);
2667 /* Similarly for a SWITCH_EXPR. */
2668 else if (!cached_lhs
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
2669 cached_lhs
= simplify_switch_and_lookup_avail_expr (stmt
, insert
);
2671 opt_stats
.num_exprs_considered
++;
2673 /* Get a pointer to the expression we are trying to optimize. */
2674 if (TREE_CODE (stmt
) == COND_EXPR
)
2675 expr_p
= &COND_EXPR_COND (stmt
);
2676 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2677 expr_p
= &SWITCH_COND (stmt
);
2678 else if (TREE_CODE (stmt
) == RETURN_EXPR
&& TREE_OPERAND (stmt
, 0))
2679 expr_p
= &TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
2681 expr_p
= &TREE_OPERAND (stmt
, 1);
2683 /* It is safe to ignore types here since we have already done
2684 type checking in the hashing and equality routines. In fact
2685 type checking here merely gets in the way of constant
2686 propagation. Also, make sure that it is safe to propagate
2687 CACHED_LHS into *EXPR_P. */
2689 && (TREE_CODE (cached_lhs
) != SSA_NAME
2690 || may_propagate_copy (*expr_p
, cached_lhs
)))
2692 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2694 fprintf (dump_file
, " Replaced redundant expr '");
2695 print_generic_expr (dump_file
, *expr_p
, dump_flags
);
2696 fprintf (dump_file
, "' with '");
2697 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
2698 fprintf (dump_file
, "'\n");
2703 #if defined ENABLE_CHECKING
2704 gcc_assert (TREE_CODE (cached_lhs
) == SSA_NAME
2705 || is_gimple_min_invariant (cached_lhs
));
2708 if (TREE_CODE (cached_lhs
) == ADDR_EXPR
2709 || (POINTER_TYPE_P (TREE_TYPE (*expr_p
))
2710 && is_gimple_min_invariant (cached_lhs
)))
2713 propagate_tree_value (expr_p
, cached_lhs
);
2719 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
2720 the available expressions table or the const_and_copies table.
2721 Detect and record those equivalences. */
2724 record_equivalences_from_stmt (tree stmt
,
2728 tree lhs
= TREE_OPERAND (stmt
, 0);
2729 enum tree_code lhs_code
= TREE_CODE (lhs
);
2732 if (lhs_code
== SSA_NAME
)
2734 tree rhs
= TREE_OPERAND (stmt
, 1);
2736 /* Strip away any useless type conversions. */
2737 STRIP_USELESS_TYPE_CONVERSION (rhs
);
2739 /* If the RHS of the assignment is a constant or another variable that
2740 may be propagated, register it in the CONST_AND_COPIES table. We
2741 do not need to record unwind data for this, since this is a true
2742 assignment and not an equivalence inferred from a comparison. All
2743 uses of this ssa name are dominated by this assignment, so unwinding
2744 just costs time and space. */
2746 && (TREE_CODE (rhs
) == SSA_NAME
2747 || is_gimple_min_invariant (rhs
)))
2748 SSA_NAME_VALUE (lhs
) = rhs
;
2750 /* alloca never returns zero and the address of a non-weak symbol
2751 is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
2752 stripped as they do not affect this equivalence. */
2753 while (TREE_CODE (rhs
) == NOP_EXPR
2754 || TREE_CODE (rhs
) == CONVERT_EXPR
)
2755 rhs
= TREE_OPERAND (rhs
, 0);
2757 if (alloca_call_p (rhs
)
2758 || (TREE_CODE (rhs
) == ADDR_EXPR
2759 && DECL_P (TREE_OPERAND (rhs
, 0))
2760 && ! DECL_WEAK (TREE_OPERAND (rhs
, 0))))
2761 record_var_is_nonzero (lhs
);
2763 /* IOR of any value with a nonzero value will result in a nonzero
2764 value. Even if we do not know the exact result recording that
2765 the result is nonzero is worth the effort. */
2766 if (TREE_CODE (rhs
) == BIT_IOR_EXPR
2767 && integer_nonzerop (TREE_OPERAND (rhs
, 1)))
2768 record_var_is_nonzero (lhs
);
2771 /* Look at both sides for pointer dereferences. If we find one, then
2772 the pointer must be nonnull and we can enter that equivalence into
2774 if (flag_delete_null_pointer_checks
)
2775 for (i
= 0; i
< 2; i
++)
2777 tree t
= TREE_OPERAND (stmt
, i
);
2779 /* Strip away any COMPONENT_REFs. */
2780 while (TREE_CODE (t
) == COMPONENT_REF
)
2781 t
= TREE_OPERAND (t
, 0);
2783 /* Now see if this is a pointer dereference. */
2784 if (INDIRECT_REF_P (t
))
2786 tree op
= TREE_OPERAND (t
, 0);
2788 /* If the pointer is a SSA variable, then enter new
2789 equivalences into the hash table. */
2790 while (TREE_CODE (op
) == SSA_NAME
)
2792 tree def
= SSA_NAME_DEF_STMT (op
);
2794 record_var_is_nonzero (op
);
2796 /* And walk up the USE-DEF chains noting other SSA_NAMEs
2797 which are known to have a nonzero value. */
2799 && TREE_CODE (def
) == MODIFY_EXPR
2800 && TREE_CODE (TREE_OPERAND (def
, 1)) == NOP_EXPR
)
2801 op
= TREE_OPERAND (TREE_OPERAND (def
, 1), 0);
2808 /* A memory store, even an aliased store, creates a useful
2809 equivalence. By exchanging the LHS and RHS, creating suitable
2810 vops and recording the result in the available expression table,
2811 we may be able to expose more redundant loads. */
2812 if (!ann
->has_volatile_ops
2813 && (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
2814 || is_gimple_min_invariant (TREE_OPERAND (stmt
, 1)))
2815 && !is_gimple_reg (lhs
))
2817 tree rhs
= TREE_OPERAND (stmt
, 1);
2820 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
2821 is a constant, we need to adjust the constant to fit into the
2822 type of the LHS. If the LHS is a bitfield and the RHS is not
2823 a constant, then we can not record any equivalences for this
2824 statement since we would need to represent the widening or
2825 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
2826 and should not be necessary if GCC represented bitfields
2828 if (lhs_code
== COMPONENT_REF
2829 && DECL_BIT_FIELD (TREE_OPERAND (lhs
, 1)))
2831 if (TREE_CONSTANT (rhs
))
2832 rhs
= widen_bitfield (rhs
, TREE_OPERAND (lhs
, 1), lhs
);
2836 /* If the value overflowed, then we can not use this equivalence. */
2837 if (rhs
&& ! is_gimple_min_invariant (rhs
))
2843 /* Build a new statement with the RHS and LHS exchanged. */
2844 new = build (MODIFY_EXPR
, TREE_TYPE (stmt
), rhs
, lhs
);
2846 create_ssa_artficial_load_stmt (&(ann
->operands
), new);
2848 /* Finally enter the statement into the available expression
2850 lookup_avail_expr (new, true);
2855 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2856 CONST_AND_COPIES. */
2859 cprop_operand (tree stmt
, use_operand_p op_p
)
2861 bool may_have_exposed_new_symbols
= false;
2863 tree op
= USE_FROM_PTR (op_p
);
2865 /* If the operand has a known constant value or it is known to be a
2866 copy of some other variable, use the value or copy stored in
2867 CONST_AND_COPIES. */
2868 val
= SSA_NAME_VALUE (op
);
2869 if (val
&& TREE_CODE (val
) != VALUE_HANDLE
)
2871 tree op_type
, val_type
;
2873 /* Do not change the base variable in the virtual operand
2874 tables. That would make it impossible to reconstruct
2875 the renamed virtual operand if we later modify this
2876 statement. Also only allow the new value to be an SSA_NAME
2877 for propagation into virtual operands. */
2878 if (!is_gimple_reg (op
)
2879 && (get_virtual_var (val
) != get_virtual_var (op
)
2880 || TREE_CODE (val
) != SSA_NAME
))
2883 /* Do not replace hard register operands in asm statements. */
2884 if (TREE_CODE (stmt
) == ASM_EXPR
2885 && !may_propagate_copy_into_asm (op
))
2888 /* Get the toplevel type of each operand. */
2889 op_type
= TREE_TYPE (op
);
2890 val_type
= TREE_TYPE (val
);
2892 /* While both types are pointers, get the type of the object
2894 while (POINTER_TYPE_P (op_type
) && POINTER_TYPE_P (val_type
))
2896 op_type
= TREE_TYPE (op_type
);
2897 val_type
= TREE_TYPE (val_type
);
2900 /* Make sure underlying types match before propagating a constant by
2901 converting the constant to the proper type. Note that convert may
2902 return a non-gimple expression, in which case we ignore this
2903 propagation opportunity. */
2904 if (TREE_CODE (val
) != SSA_NAME
)
2906 if (!lang_hooks
.types_compatible_p (op_type
, val_type
))
2908 val
= fold_convert (TREE_TYPE (op
), val
);
2909 if (!is_gimple_min_invariant (val
))
2914 /* Certain operands are not allowed to be copy propagated due
2915 to their interaction with exception handling and some GCC
2917 else if (!may_propagate_copy (op
, val
))
2920 /* Do not propagate copies if the propagated value is at a deeper loop
2921 depth than the propagatee. Otherwise, this may move loop variant
2922 variables outside of their loops and prevent coalescing
2923 opportunities. If the value was loop invariant, it will be hoisted
2924 by LICM and exposed for copy propagation. */
2925 if (loop_depth_of_name (val
) > loop_depth_of_name (op
))
2929 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2931 fprintf (dump_file
, " Replaced '");
2932 print_generic_expr (dump_file
, op
, dump_flags
);
2933 fprintf (dump_file
, "' with %s '",
2934 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
2935 print_generic_expr (dump_file
, val
, dump_flags
);
2936 fprintf (dump_file
, "'\n");
2939 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2940 that we may have exposed a new symbol for SSA renaming. */
2941 if (TREE_CODE (val
) == ADDR_EXPR
2942 || (POINTER_TYPE_P (TREE_TYPE (op
))
2943 && is_gimple_min_invariant (val
)))
2944 may_have_exposed_new_symbols
= true;
2946 propagate_value (op_p
, val
);
2948 /* And note that we modified this statement. This is now
2949 safe, even if we changed virtual operands since we will
2950 rescan the statement and rewrite its operands again. */
2953 return may_have_exposed_new_symbols
;
2956 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2957 known value for that SSA_NAME (or NULL if no value is known).
2959 Propagate values from CONST_AND_COPIES into the uses, vuses and
2960 v_may_def_ops of STMT. */
2963 cprop_into_stmt (tree stmt
)
2965 bool may_have_exposed_new_symbols
= false;
2970 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_ALL_USES
)
2972 if (TREE_CODE (USE_FROM_PTR (op_p
)) == SSA_NAME
)
2973 may_have_exposed_new_symbols
|= cprop_operand (stmt
, op_p
);
2976 if (may_have_exposed_new_symbols
)
2978 rhs
= get_rhs (stmt
);
2979 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
2980 recompute_tree_invarant_for_addr_expr (rhs
);
2983 return may_have_exposed_new_symbols
;
2987 /* Optimize the statement pointed by iterator SI.
2989 We try to perform some simplistic global redundancy elimination and
2990 constant propagation:
2992 1- To detect global redundancy, we keep track of expressions that have
2993 been computed in this block and its dominators. If we find that the
2994 same expression is computed more than once, we eliminate repeated
2995 computations by using the target of the first one.
2997 2- Constant values and copy assignments. This is used to do very
2998 simplistic constant and copy propagation. When a constant or copy
2999 assignment is found, we map the value on the RHS of the assignment to
3000 the variable in the LHS in the CONST_AND_COPIES table. */
3003 optimize_stmt (struct dom_walk_data
*walk_data
, basic_block bb
,
3004 block_stmt_iterator si
)
3008 bool may_optimize_p
;
3009 bool may_have_exposed_new_symbols
= false;
3011 stmt
= bsi_stmt (si
);
3013 get_stmt_operands (stmt
);
3014 ann
= stmt_ann (stmt
);
3015 opt_stats
.num_stmts
++;
3016 may_have_exposed_new_symbols
= false;
3018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3020 fprintf (dump_file
, "Optimizing statement ");
3021 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
3024 /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
3025 may_have_exposed_new_symbols
= cprop_into_stmt (stmt
);
3027 /* If the statement has been modified with constant replacements,
3028 fold its RHS before checking for redundant computations. */
3031 /* Try to fold the statement making sure that STMT is kept
3033 if (fold_stmt (bsi_stmt_ptr (si
)))
3035 stmt
= bsi_stmt (si
);
3036 ann
= stmt_ann (stmt
);
3038 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3040 fprintf (dump_file
, " Folded to: ");
3041 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
3045 /* Constant/copy propagation above may change the set of
3046 virtual operands associated with this statement. Folding
3047 may remove the need for some virtual operands.
3049 Indicate we will need to rescan and rewrite the statement. */
3050 may_have_exposed_new_symbols
= true;
3053 /* Check for redundant computations. Do this optimization only
3054 for assignments that have no volatile ops and conditionals. */
3055 may_optimize_p
= (!ann
->has_volatile_ops
3056 && ((TREE_CODE (stmt
) == RETURN_EXPR
3057 && TREE_OPERAND (stmt
, 0)
3058 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
3059 && ! (TREE_SIDE_EFFECTS
3060 (TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1))))
3061 || (TREE_CODE (stmt
) == MODIFY_EXPR
3062 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt
, 1)))
3063 || TREE_CODE (stmt
) == COND_EXPR
3064 || TREE_CODE (stmt
) == SWITCH_EXPR
));
3067 may_have_exposed_new_symbols
3068 |= eliminate_redundant_computations (walk_data
, stmt
, ann
);
3070 /* Record any additional equivalences created by this statement. */
3071 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
3072 record_equivalences_from_stmt (stmt
,
3076 register_definitions_for_stmt (stmt
);
3078 /* If STMT is a COND_EXPR and it was modified, then we may know
3079 where it goes. If that is the case, then mark the CFG as altered.
3081 This will cause us to later call remove_unreachable_blocks and
3082 cleanup_tree_cfg when it is safe to do so. It is not safe to
3083 clean things up here since removal of edges and such can trigger
3084 the removal of PHI nodes, which in turn can release SSA_NAMEs to
3087 That's all fine and good, except that once SSA_NAMEs are released
3088 to the manager, we must not call create_ssa_name until all references
3089 to released SSA_NAMEs have been eliminated.
3091 All references to the deleted SSA_NAMEs can not be eliminated until
3092 we remove unreachable blocks.
3094 We can not remove unreachable blocks until after we have completed
3095 any queued jump threading.
3097 We can not complete any queued jump threads until we have taken
3098 appropriate variables out of SSA form. Taking variables out of
3099 SSA form can call create_ssa_name and thus we lose.
3101 Ultimately I suspect we're going to need to change the interface
3102 into the SSA_NAME manager. */
3108 if (TREE_CODE (stmt
) == COND_EXPR
)
3109 val
= COND_EXPR_COND (stmt
);
3110 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
3111 val
= SWITCH_COND (stmt
);
3113 if (val
&& TREE_CODE (val
) == INTEGER_CST
&& find_taken_edge (bb
, val
))
3116 /* If we simplified a statement in such a way as to be shown that it
3117 cannot trap, update the eh information and the cfg to match. */
3118 if (maybe_clean_eh_stmt (stmt
))
3120 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
3121 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3122 fprintf (dump_file
, " Flagged to clear EH edges.\n");
3126 if (may_have_exposed_new_symbols
)
3127 VEC_safe_push (tree_on_heap
, stmts_to_rescan
, bsi_stmt (si
));
3130 /* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
3131 available expression hashtable, then return the LHS from the hash
3134 If INSERT is true, then we also update the available expression
3135 hash table to account for the changes made to STMT. */
3138 update_rhs_and_lookup_avail_expr (tree stmt
, tree new_rhs
, bool insert
)
3140 tree cached_lhs
= NULL
;
3142 /* Remove the old entry from the hash table. */
3145 struct expr_hash_elt element
;
3147 initialize_hash_element (stmt
, NULL
, &element
);
3148 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
3151 /* Now update the RHS of the assignment. */
3152 TREE_OPERAND (stmt
, 1) = new_rhs
;
3154 /* Now lookup the updated statement in the hash table. */
3155 cached_lhs
= lookup_avail_expr (stmt
, insert
);
3157 /* We have now called lookup_avail_expr twice with two different
3158 versions of this same statement, once in optimize_stmt, once here.
3160 We know the call in optimize_stmt did not find an existing entry
3161 in the hash table, so a new entry was created. At the same time
3162 this statement was pushed onto the AVAIL_EXPRS_STACK vector.
3164 If this call failed to find an existing entry on the hash table,
3165 then the new version of this statement was entered into the
3166 hash table. And this statement was pushed onto BLOCK_AVAIL_EXPR
3167 for the second time. So there are two copies on BLOCK_AVAIL_EXPRs
3169 If this call succeeded, we still have one copy of this statement
3170 on the BLOCK_AVAIL_EXPRs vector.
3172 For both cases, we need to pop the most recent entry off the
3173 BLOCK_AVAIL_EXPRs vector. For the case where we never found this
3174 statement in the hash tables, that will leave precisely one
3175 copy of this statement on BLOCK_AVAIL_EXPRs. For the case where
3176 we found a copy of this statement in the second hash table lookup
3177 we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs. */
3179 VEC_pop (tree_on_heap
, avail_exprs_stack
);
3181 /* And make sure we record the fact that we modified this
3188 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
3189 found, return its LHS. Otherwise insert STMT in the table and return
3192 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
3193 is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
3194 can be removed when we finish processing this block and its children.
3196 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
3197 contains no CALL_EXPR on its RHS and makes no volatile nor
3198 aliased references. */
3201 lookup_avail_expr (tree stmt
, bool insert
)
3206 struct expr_hash_elt
*element
= xmalloc (sizeof (struct expr_hash_elt
));
3208 lhs
= TREE_CODE (stmt
) == MODIFY_EXPR
? TREE_OPERAND (stmt
, 0) : NULL
;
3210 initialize_hash_element (stmt
, lhs
, element
);
3212 /* Don't bother remembering constant assignments and copy operations.
3213 Constants and copy operations are handled by the constant/copy propagator
3214 in optimize_stmt. */
3215 if (TREE_CODE (element
->rhs
) == SSA_NAME
3216 || is_gimple_min_invariant (element
->rhs
))
3222 /* If this is an equality test against zero, see if we have recorded a
3223 nonzero value for the variable in question. */
3224 if ((TREE_CODE (element
->rhs
) == EQ_EXPR
3225 || TREE_CODE (element
->rhs
) == NE_EXPR
)
3226 && TREE_CODE (TREE_OPERAND (element
->rhs
, 0)) == SSA_NAME
3227 && integer_zerop (TREE_OPERAND (element
->rhs
, 1)))
3229 int indx
= SSA_NAME_VERSION (TREE_OPERAND (element
->rhs
, 0));
3231 if (bitmap_bit_p (nonzero_vars
, indx
))
3233 tree t
= element
->rhs
;
3236 if (TREE_CODE (t
) == EQ_EXPR
)
3237 return boolean_false_node
;
3239 return boolean_true_node
;
3243 /* Finally try to find the expression in the main expression hash table. */
3244 slot
= htab_find_slot_with_hash (avail_exprs
, element
, element
->hash
,
3245 (insert
? INSERT
: NO_INSERT
));
3254 *slot
= (void *) element
;
3255 VEC_safe_push (tree_on_heap
, avail_exprs_stack
,
3256 stmt
? stmt
: element
->rhs
);
3260 /* Extract the LHS of the assignment so that it can be used as the current
3261 definition of another variable. */
3262 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
3264 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
3265 use the value from the const_and_copies table. */
3266 if (TREE_CODE (lhs
) == SSA_NAME
)
3268 temp
= SSA_NAME_VALUE (lhs
);
3269 if (temp
&& TREE_CODE (temp
) != VALUE_HANDLE
)
3277 /* Given a condition COND, record into HI_P, LO_P and INVERTED_P the
3278 range of values that result in the conditional having a true value.
3280 Return true if we are successful in extracting a range from COND and
3281 false if we are unsuccessful. */
3284 extract_range_from_cond (tree cond
, tree
*hi_p
, tree
*lo_p
, int *inverted_p
)
3286 tree op1
= TREE_OPERAND (cond
, 1);
3287 tree high
, low
, type
;
3290 type
= TREE_TYPE (op1
);
3292 /* Experiments have shown that it's rarely, if ever useful to
3293 record ranges for enumerations. Presumably this is due to
3294 the fact that they're rarely used directly. They are typically
3295 cast into an integer type and used that way. */
3296 if (TREE_CODE (type
) != INTEGER_TYPE
3297 /* We don't know how to deal with types with variable bounds. */
3298 || TREE_CODE (TYPE_MIN_VALUE (type
)) != INTEGER_CST
3299 || TREE_CODE (TYPE_MAX_VALUE (type
)) != INTEGER_CST
)
3302 switch (TREE_CODE (cond
))
3316 high
= TYPE_MAX_VALUE (type
);
3321 high
= TYPE_MAX_VALUE (type
);
3322 if (!tree_int_cst_lt (op1
, high
))
3324 low
= int_const_binop (PLUS_EXPR
, op1
, integer_one_node
, 1);
3330 low
= TYPE_MIN_VALUE (type
);
3335 low
= TYPE_MIN_VALUE (type
);
3336 if (!tree_int_cst_lt (low
, op1
))
3338 high
= int_const_binop (MINUS_EXPR
, op1
, integer_one_node
, 1);
3348 *inverted_p
= inverted
;
3352 /* Record a range created by COND for basic block BB. */
3355 record_range (tree cond
, basic_block bb
)
3357 enum tree_code code
= TREE_CODE (cond
);
3359 /* We explicitly ignore NE_EXPRs and all the unordered comparisons.
3360 They rarely allow for meaningful range optimizations and significantly
3361 complicate the implementation. */
3362 if ((code
== LT_EXPR
|| code
== LE_EXPR
|| code
== GT_EXPR
3363 || code
== GE_EXPR
|| code
== EQ_EXPR
)
3364 && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond
, 1))) == INTEGER_TYPE
)
3366 struct vrp_hash_elt
*vrp_hash_elt
;
3367 struct vrp_element
*element
;
3368 varray_type
*vrp_records_p
;
3372 vrp_hash_elt
= xmalloc (sizeof (struct vrp_hash_elt
));
3373 vrp_hash_elt
->var
= TREE_OPERAND (cond
, 0);
3374 vrp_hash_elt
->records
= NULL
;
3375 slot
= htab_find_slot (vrp_data
, vrp_hash_elt
, INSERT
);
3378 *slot
= (void *) vrp_hash_elt
;
3380 free (vrp_hash_elt
);
3382 vrp_hash_elt
= (struct vrp_hash_elt
*) *slot
;
3383 vrp_records_p
= &vrp_hash_elt
->records
;
3385 element
= ggc_alloc (sizeof (struct vrp_element
));
3386 element
->low
= NULL
;
3387 element
->high
= NULL
;
3388 element
->cond
= cond
;
3391 if (*vrp_records_p
== NULL
)
3392 VARRAY_GENERIC_PTR_INIT (*vrp_records_p
, 2, "vrp records");
3394 VARRAY_PUSH_GENERIC_PTR (*vrp_records_p
, element
);
3395 VEC_safe_push (tree_on_heap
, vrp_variables_stack
, TREE_OPERAND (cond
, 0));
3399 /* Hashing and equality functions for VRP_DATA.
3401 Since this hash table is addressed by SSA_NAMEs, we can hash on
3402 their version number and equality can be determined with a
3403 pointer comparison. */
3406 vrp_hash (const void *p
)
3408 tree var
= ((struct vrp_hash_elt
*)p
)->var
;
3410 return SSA_NAME_VERSION (var
);
3414 vrp_eq (const void *p1
, const void *p2
)
3416 tree var1
= ((struct vrp_hash_elt
*)p1
)->var
;
3417 tree var2
= ((struct vrp_hash_elt
*)p2
)->var
;
3419 return var1
== var2
;
3422 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
3423 MODIFY_EXPR statements. We compute a value number for expressions using
3424 the code of the expression and the SSA numbers of its operands. */
3427 avail_expr_hash (const void *p
)
3429 stmt_ann_t ann
= ((struct expr_hash_elt
*)p
)->ann
;
3430 tree rhs
= ((struct expr_hash_elt
*)p
)->rhs
;
3435 /* iterative_hash_expr knows how to deal with any expression and
3436 deals with commutative operators as well, so just use it instead
3437 of duplicating such complexities here. */
3438 val
= iterative_hash_expr (rhs
, val
);
3440 /* If the hash table entry is not associated with a statement, then we
3441 can just hash the expression and not worry about virtual operands
3446 /* Add the SSA version numbers of every vuse operand. This is important
3447 because compound variables like arrays are not renamed in the
3448 operands. Rather, the rename is done on the virtual variable
3449 representing all the elements of the array. */
3450 vuses
= VUSE_OPS (ann
);
3451 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
3452 val
= iterative_hash_expr (VUSE_OP (vuses
, i
), val
);
3458 real_avail_expr_hash (const void *p
)
3460 return ((const struct expr_hash_elt
*)p
)->hash
;
3464 avail_expr_eq (const void *p1
, const void *p2
)
3466 stmt_ann_t ann1
= ((struct expr_hash_elt
*)p1
)->ann
;
3467 tree rhs1
= ((struct expr_hash_elt
*)p1
)->rhs
;
3468 stmt_ann_t ann2
= ((struct expr_hash_elt
*)p2
)->ann
;
3469 tree rhs2
= ((struct expr_hash_elt
*)p2
)->rhs
;
3471 /* If they are the same physical expression, return true. */
3472 if (rhs1
== rhs2
&& ann1
== ann2
)
3475 /* If their codes are not equal, then quit now. */
3476 if (TREE_CODE (rhs1
) != TREE_CODE (rhs2
))
3479 /* In case of a collision, both RHS have to be identical and have the
3480 same VUSE operands. */
3481 if ((TREE_TYPE (rhs1
) == TREE_TYPE (rhs2
)
3482 || lang_hooks
.types_compatible_p (TREE_TYPE (rhs1
), TREE_TYPE (rhs2
)))
3483 && operand_equal_p (rhs1
, rhs2
, OEP_PURE_SAME
))
3485 vuse_optype ops1
= NULL
;
3486 vuse_optype ops2
= NULL
;
3487 size_t num_ops1
= 0;
3488 size_t num_ops2
= 0;
3493 ops1
= VUSE_OPS (ann1
);
3494 num_ops1
= NUM_VUSES (ops1
);
3499 ops2
= VUSE_OPS (ann2
);
3500 num_ops2
= NUM_VUSES (ops2
);
3503 /* If the number of virtual uses is different, then we consider
3505 if (num_ops1
!= num_ops2
)
3508 for (i
= 0; i
< num_ops1
; i
++)
3509 if (VUSE_OP (ops1
, i
) != VUSE_OP (ops2
, i
))
3512 gcc_assert (((struct expr_hash_elt
*)p1
)->hash
3513 == ((struct expr_hash_elt
*)p2
)->hash
);
3520 /* Given STMT and a pointer to the block local definitions BLOCK_DEFS_P,
3521 register register all objects set by this statement into BLOCK_DEFS_P
3525 register_definitions_for_stmt (tree stmt
)
3530 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
3533 /* FIXME: We shouldn't be registering new defs if the variable
3534 doesn't need to be renamed. */
3535 register_new_def (def
, &block_defs_stack
);