1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004 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"
36 #include "diagnostic.h"
38 #include "tree-dump.h"
39 #include "tree-flow.h"
42 #include "tree-pass.h"
43 #include "tree-ssa-propagate.h"
44 #include "langhooks.h"
46 /* This file implements optimizations on the dominator tree. */
48 /* Hash table with expressions made available during the renaming process.
49 When an assignment of the form X_i = EXPR is found, the statement is
50 stored in this table. If the same expression EXPR is later found on the
51 RHS of another statement, it is replaced with X_i (thus performing
52 global redundancy elimination). Similarly as we pass through conditionals
53 we record the conditional itself as having either a true or false value
55 static htab_t avail_exprs
;
57 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
58 expressions it enters into the hash table along with a marker entry
59 (null). When we finish processing the block, we pop off entries and
60 remove the expressions from the global hash table until we hit the
62 static varray_type avail_exprs_stack
;
64 /* Stack of trees used to restore the global currdefs to its original
65 state after completing optimization of a block and its dominator children.
67 An SSA_NAME indicates that the current definition of the underlying
68 variable should be set to the given SSA_NAME.
70 A _DECL node indicates that the underlying variable has no current
73 A NULL node is used to mark the last node associated with the
75 varray_type block_defs_stack
;
77 /* Stack of statements we need to rescan during finalization for newly
80 Statement rescanning must occur after the current block's available
81 expressions are removed from AVAIL_EXPRS. Else we may change the
82 hash code for an expression and be unable to find/remove it from
84 varray_type stmts_to_rescan
;
86 /* Structure for entries in the expression hash table.
88 This requires more memory for the hash table entries, but allows us
89 to avoid creating silly tree nodes and annotations for conditionals,
90 eliminates 2 global hash tables and two block local varrays.
92 It also allows us to reduce the number of hash table lookups we
93 have to perform in lookup_avail_expr and finally it allows us to
94 significantly reduce the number of calls into the hashing routine
99 /* The value (lhs) of this expression. */
102 /* The expression (rhs) we want to record. */
105 /* The annotation if this element corresponds to a statement. */
108 /* The hash value for RHS/ann. */
112 /* Stack of dest,src pairs that need to be restored during finalization.
114 A NULL entry is used to mark the end of pairs which need to be
115 restored during finalization of this block. */
116 static varray_type const_and_copies_stack
;
118 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
119 know their exact value. */
120 static bitmap nonzero_vars
;
122 /* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
123 when the current block is finalized.
125 A NULL entry is used to mark the end of names needing their
126 entry in NONZERO_VARS cleared during finalization of this block. */
127 static varray_type nonzero_vars_stack
;
129 /* Track whether or not we have changed the control flow graph. */
130 static bool cfg_altered
;
132 /* Bitmap of blocks that have had EH statements cleaned. We should
133 remove their dead edges eventually. */
134 static bitmap need_eh_cleanup
;
136 /* Statistics for dominator optimizations. */
140 long num_exprs_considered
;
144 static struct opt_stats_d opt_stats
;
146 /* Value range propagation record. Each time we encounter a conditional
147 of the form SSA_NAME COND CONST we create a new vrp_element to record
148 how the condition affects the possible values SSA_NAME may have.
150 Each record contains the condition tested (COND), and the the range of
151 values the variable may legitimately have if COND is true. Note the
152 range of values may be a smaller range than COND specifies if we have
153 recorded other ranges for this variable. Each record also contains the
154 block in which the range was recorded for invalidation purposes.
156 Note that the current known range is computed lazily. This allows us
157 to avoid the overhead of computing ranges which are never queried.
159 When we encounter a conditional, we look for records which constrain
160 the SSA_NAME used in the condition. In some cases those records allow
161 us to determine the condition's result at compile time. In other cases
162 they may allow us to simplify the condition.
164 We also use value ranges to do things like transform signed div/mod
165 operations into unsigned div/mod or to simplify ABS_EXPRs.
167 Simple experiments have shown these optimizations to not be all that
168 useful on switch statements (much to my surprise). So switch statement
169 optimizations are not performed.
171 Note carefully we do not propagate information through each statement
172 in the block. i.e., if we know variable X has a value defined of
173 [0, 25] and we encounter Y = X + 1, we do not track a value range
174 for Y (which would be [1, 26] if we cared). Similarly we do not
175 constrain values as we encounter narrowing typecasts, etc. */
179 /* The highest and lowest values the variable in COND may contain when
180 COND is true. Note this may not necessarily be the same values
181 tested by COND if the same variable was used in earlier conditionals.
183 Note this is computed lazily and thus can be NULL indicating that
184 the values have not been computed yet. */
188 /* The actual conditional we recorded. This is needed since we compute
192 /* The basic block where this record was created. We use this to determine
193 when to remove records. */
197 /* A hash table holding value range records (VRP_ELEMENTs) for a given
198 SSA_NAME. We used to use a varray indexed by SSA_NAME_VERSION, but
199 that gets awful wasteful, particularly since the density objects
200 with useful information is very low. */
201 static htab_t vrp_data
;
203 /* An entry in the VRP_DATA hash table. We record the variable and a
204 varray of VRP_ELEMENT records associated with that variable. */
212 /* Array of variables which have their values constrained by operations
213 in this basic block. We use this during finalization to know
214 which variables need their VRP data updated. */
216 /* Stack of SSA_NAMEs which had their values constrainted by operations
217 in this basic block. During finalization of this block we use this
218 list to determine which variables need their VRP data updated.
220 A NULL entry marks the end of the SSA_NAMEs associated with this block. */
221 static varray_type vrp_variables_stack
;
229 /* Local functions. */
230 static void optimize_stmt (struct dom_walk_data
*,
232 block_stmt_iterator
);
233 static tree
lookup_avail_expr (tree
, bool);
234 static struct eq_expr_value
get_eq_expr_value (tree
, int, basic_block
);
235 static hashval_t
vrp_hash (const void *);
236 static int vrp_eq (const void *, const void *);
237 static hashval_t
avail_expr_hash (const void *);
238 static hashval_t
real_avail_expr_hash (const void *);
239 static int avail_expr_eq (const void *, const void *);
240 static void htab_statistics (FILE *, htab_t
);
241 static void record_cond (tree
, tree
);
242 static void record_dominating_conditions (tree
);
243 static void record_const_or_copy (tree
, tree
);
244 static void record_equality (tree
, tree
);
245 static tree
update_rhs_and_lookup_avail_expr (tree
, tree
, bool);
246 static tree
simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*,
248 static tree
simplify_cond_and_lookup_avail_expr (tree
, stmt_ann_t
, int);
249 static tree
simplify_switch_and_lookup_avail_expr (tree
, int);
250 static tree
find_equivalent_equality_comparison (tree
);
251 static void record_range (tree
, basic_block
);
252 static bool extract_range_from_cond (tree
, tree
*, tree
*, int *);
253 static void record_equivalences_from_phis (struct dom_walk_data
*, basic_block
);
254 static void record_equivalences_from_incoming_edge (struct dom_walk_data
*,
256 static bool eliminate_redundant_computations (struct dom_walk_data
*,
258 static void record_equivalences_from_stmt (tree
, int, stmt_ann_t
);
259 static void thread_across_edge (struct dom_walk_data
*, edge
);
260 static void dom_opt_finalize_block (struct dom_walk_data
*, basic_block
);
261 static void dom_opt_initialize_block (struct dom_walk_data
*, basic_block
);
262 static void cprop_into_phis (struct dom_walk_data
*, basic_block
);
263 static void remove_local_expressions_from_table (void);
264 static void restore_vars_to_original_value (void);
265 static void restore_currdefs_to_original_value (void);
266 static void register_definitions_for_stmt (tree
);
267 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
268 static void restore_nonzero_vars_to_original_value (void);
270 /* Local version of fold that doesn't introduce cruft. */
277 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
278 may have been added by fold, and "useless" type conversions that might
279 now be apparent due to propagation. */
280 STRIP_USELESS_TYPE_CONVERSION (t
);
285 /* Jump threading, redundancy elimination and const/copy propagation.
287 This pass may expose new symbols that need to be renamed into SSA. For
288 every new symbol exposed, its corresponding bit will be set in
292 tree_ssa_dominator_optimize (void)
294 struct dom_walk_data walk_data
;
297 for (i
= 0; i
< num_referenced_vars
; i
++)
298 var_ann (referenced_var (i
))->current_def
= NULL
;
300 /* Mark loop edges so we avoid threading across loop boundaries.
301 This may result in transforming natural loop into irreducible
303 mark_dfs_back_edges ();
305 /* Create our hash tables. */
306 avail_exprs
= htab_create (1024, real_avail_expr_hash
, avail_expr_eq
, free
);
307 vrp_data
= htab_create (ceil_log2 (num_ssa_names
), vrp_hash
, vrp_eq
, free
);
308 VARRAY_TREE_INIT (avail_exprs_stack
, 20, "Available expression stack");
309 VARRAY_TREE_INIT (block_defs_stack
, 20, "Block DEFS stack");
310 VARRAY_TREE_INIT (const_and_copies_stack
, 20, "Block const_and_copies stack");
311 VARRAY_TREE_INIT (nonzero_vars_stack
, 20, "Block nonzero_vars stack");
312 VARRAY_TREE_INIT (vrp_variables_stack
, 20, "Block vrp_variables stack");
313 VARRAY_TREE_INIT (stmts_to_rescan
, 20, "Statements to rescan");
314 nonzero_vars
= BITMAP_XMALLOC ();
315 need_eh_cleanup
= BITMAP_XMALLOC ();
317 /* Setup callbacks for the generic dominator tree walker. */
318 walk_data
.walk_stmts_backward
= false;
319 walk_data
.dom_direction
= CDI_DOMINATORS
;
320 walk_data
.initialize_block_local_data
= NULL
;
321 walk_data
.before_dom_children_before_stmts
= dom_opt_initialize_block
;
322 walk_data
.before_dom_children_walk_stmts
= optimize_stmt
;
323 walk_data
.before_dom_children_after_stmts
= cprop_into_phis
;
324 walk_data
.after_dom_children_before_stmts
= NULL
;
325 walk_data
.after_dom_children_walk_stmts
= NULL
;
326 walk_data
.after_dom_children_after_stmts
= dom_opt_finalize_block
;
327 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
328 When we attach more stuff we'll need to fill this out with a real
330 walk_data
.global_data
= NULL
;
331 walk_data
.block_local_data_size
= 0;
333 /* Now initialize the dominator walker. */
334 init_walk_dominator_tree (&walk_data
);
336 calculate_dominance_info (CDI_DOMINATORS
);
338 /* If we prove certain blocks are unreachable, then we want to
339 repeat the dominator optimization process as PHI nodes may
340 have turned into copies which allows better propagation of
341 values. So we repeat until we do not identify any new unreachable
345 /* Optimize the dominator tree. */
348 /* Recursively walk the dominator tree optimizing statements. */
349 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
351 /* If we exposed any new variables, go ahead and put them into
352 SSA form now, before we handle jump threading. This simplifies
353 interactions between rewriting of _DECL nodes into SSA form
354 and rewriting SSA_NAME nodes into SSA form after block
355 duplication and CFG manipulation. */
356 if (bitmap_first_set_bit (vars_to_rename
) >= 0)
358 rewrite_into_ssa (false);
359 bitmap_clear (vars_to_rename
);
362 /* Thread jumps, creating duplicate blocks as needed. */
363 cfg_altered
= thread_through_all_blocks ();
365 /* Removal of statements may make some EH edges dead. Purge
366 such edges from the CFG as needed. */
367 if (bitmap_first_set_bit (need_eh_cleanup
) >= 0)
369 cfg_altered
|= tree_purge_all_dead_eh_edges (need_eh_cleanup
);
370 bitmap_zero (need_eh_cleanup
);
373 free_dominance_info (CDI_DOMINATORS
);
374 cfg_altered
= cleanup_tree_cfg ();
375 calculate_dominance_info (CDI_DOMINATORS
);
377 rewrite_ssa_into_ssa ();
379 /* Reinitialize the various tables. */
380 bitmap_clear (nonzero_vars
);
381 htab_empty (avail_exprs
);
382 htab_empty (vrp_data
);
384 for (i
= 0; i
< num_referenced_vars
; i
++)
385 var_ann (referenced_var (i
))->current_def
= NULL
;
389 /* Debugging dumps. */
390 if (dump_file
&& (dump_flags
& TDF_STATS
))
391 dump_dominator_optimization_stats (dump_file
);
393 /* We emptied the hash table earlier, now delete it completely. */
394 htab_delete (avail_exprs
);
395 htab_delete (vrp_data
);
397 /* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
398 CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
399 of the do-while loop above. */
401 /* And finalize the dominator walker. */
402 fini_walk_dominator_tree (&walk_data
);
404 /* Free nonzero_vars. */
405 BITMAP_XFREE (nonzero_vars
);
406 BITMAP_XFREE (need_eh_cleanup
);
408 /* Finally, remove everything except invariants in SSA_NAME_VALUE.
410 Long term we will be able to let everything in SSA_NAME_VALUE
411 persist. However, for now, we know this is the safe thing to
413 for (i
= 0; i
< num_ssa_names
; i
++)
415 tree name
= ssa_name (i
);
421 value
= SSA_NAME_VALUE (name
);
422 if (value
&& !is_gimple_min_invariant (value
))
423 SSA_NAME_VALUE (name
) = NULL
;
428 gate_dominator (void)
430 return flag_tree_dom
!= 0;
433 struct tree_opt_pass pass_dominator
=
436 gate_dominator
, /* gate */
437 tree_ssa_dominator_optimize
, /* execute */
440 0, /* static_pass_number */
441 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
442 PROP_cfg
| PROP_ssa
| PROP_alias
, /* properties_required */
443 0, /* properties_provided */
444 0, /* properties_destroyed */
445 0, /* todo_flags_start */
446 TODO_dump_func
| TODO_rename_vars
447 | TODO_verify_ssa
, /* todo_flags_finish */
452 /* We are exiting BB, see if the target block begins with a conditional
453 jump which has a known value when reached via BB. */
456 thread_across_edge (struct dom_walk_data
*walk_data
, edge e
)
458 block_stmt_iterator bsi
;
462 /* Each PHI creates a temporary equivalence, record them. */
463 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
465 tree src
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
466 tree dst
= PHI_RESULT (phi
);
467 record_const_or_copy (dst
, src
);
468 register_new_def (dst
, &block_defs_stack
);
471 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
473 tree lhs
, cached_lhs
;
475 stmt
= bsi_stmt (bsi
);
477 /* Ignore empty statements and labels. */
478 if (IS_EMPTY_STMT (stmt
) || TREE_CODE (stmt
) == LABEL_EXPR
)
481 /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
482 value, then stop our search here. Ideally when we stop a
483 search we stop on a COND_EXPR or SWITCH_EXPR. */
484 if (TREE_CODE (stmt
) != MODIFY_EXPR
485 || TREE_CODE (TREE_OPERAND (stmt
, 0)) != SSA_NAME
)
488 /* At this point we have a statement which assigns an RHS to an
489 SSA_VAR on the LHS. We want to prove that the RHS is already
490 available and that its value is held in the current definition
491 of the LHS -- meaning that this assignment is a NOP when
492 reached via edge E. */
493 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
)
494 cached_lhs
= TREE_OPERAND (stmt
, 1);
496 cached_lhs
= lookup_avail_expr (stmt
, false);
498 lhs
= TREE_OPERAND (stmt
, 0);
500 /* This can happen if we thread around to the start of a loop. */
501 if (lhs
== cached_lhs
)
504 /* If we did not find RHS in the hash table, then try again after
505 temporarily const/copy propagating the operands. */
508 /* Copy the operands. */
509 stmt_ann_t ann
= stmt_ann (stmt
);
510 use_optype uses
= USE_OPS (ann
);
511 vuse_optype vuses
= VUSE_OPS (ann
);
512 tree
*uses_copy
= xcalloc (NUM_USES (uses
), sizeof (tree
));
513 tree
*vuses_copy
= xcalloc (NUM_VUSES (vuses
), sizeof (tree
));
516 /* Make a copy of the uses into USES_COPY, then cprop into
518 for (i
= 0; i
< NUM_USES (uses
); i
++)
522 uses_copy
[i
] = USE_OP (uses
, i
);
523 if (TREE_CODE (USE_OP (uses
, i
)) == SSA_NAME
)
524 tmp
= SSA_NAME_VALUE (USE_OP (uses
, i
));
525 if (tmp
&& TREE_CODE (tmp
) != VALUE_HANDLE
)
526 SET_USE_OP (uses
, i
, tmp
);
529 /* Similarly for virtual uses. */
530 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
534 vuses_copy
[i
] = VUSE_OP (vuses
, i
);
535 if (TREE_CODE (VUSE_OP (vuses
, i
)) == SSA_NAME
)
536 tmp
= SSA_NAME_VALUE (VUSE_OP (vuses
, i
));
537 if (tmp
&& TREE_CODE (tmp
) != VALUE_HANDLE
)
538 SET_VUSE_OP (vuses
, i
, tmp
);
541 /* Try to lookup the new expression. */
542 cached_lhs
= lookup_avail_expr (stmt
, false);
544 /* Restore the statement's original uses/defs. */
545 for (i
= 0; i
< NUM_USES (uses
); i
++)
546 SET_USE_OP (uses
, i
, uses_copy
[i
]);
548 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
549 SET_VUSE_OP (vuses
, i
, vuses_copy
[i
]);
554 /* If we still did not find the expression in the hash table,
555 then we can not ignore this statement. */
560 /* If the expression in the hash table was not assigned to an
561 SSA_NAME, then we can not ignore this statement. */
562 if (TREE_CODE (cached_lhs
) != SSA_NAME
)
565 /* If we have different underlying variables, then we can not
566 ignore this statement. */
567 if (SSA_NAME_VAR (cached_lhs
) != SSA_NAME_VAR (lhs
))
570 /* If CACHED_LHS does not represent the current value of the undering
571 variable in CACHED_LHS/LHS, then we can not ignore this statement. */
572 if (var_ann (SSA_NAME_VAR (lhs
))->current_def
!= cached_lhs
)
575 /* If we got here, then we can ignore this statement and continue
576 walking through the statements in the block looking for a threadable
579 We want to record an equivalence lhs = cache_lhs so that if
580 the result of this statement is used later we can copy propagate
582 record_const_or_copy (lhs
, cached_lhs
);
583 register_new_def (lhs
, &block_defs_stack
);
586 /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
587 arm will be taken. */
589 && (TREE_CODE (stmt
) == COND_EXPR
590 || TREE_CODE (stmt
) == SWITCH_EXPR
))
592 tree cond
, cached_lhs
;
596 /* Do not forward entry edges into the loop. In the case loop
597 has multiple entry edges we may end up in constructing irreducible
599 ??? We may consider forwarding the edges in the case all incoming
600 edges forward to the same destination block. */
601 if (!e
->flags
& EDGE_DFS_BACK
)
603 FOR_EACH_EDGE (e1
, ei
, e
->dest
->preds
)
604 if (e1
->flags
& EDGE_DFS_BACK
)
610 /* Now temporarily cprop the operands and try to find the resulting
611 expression in the hash tables. */
612 if (TREE_CODE (stmt
) == COND_EXPR
)
613 cond
= COND_EXPR_COND (stmt
);
615 cond
= SWITCH_COND (stmt
);
617 if (COMPARISON_CLASS_P (cond
))
619 tree dummy_cond
, op0
, op1
;
620 enum tree_code cond_code
;
622 op0
= TREE_OPERAND (cond
, 0);
623 op1
= TREE_OPERAND (cond
, 1);
624 cond_code
= TREE_CODE (cond
);
626 /* Get the current value of both operands. */
627 if (TREE_CODE (op0
) == SSA_NAME
)
629 tree tmp
= SSA_NAME_VALUE (op0
);
630 if (tmp
&& TREE_CODE (tmp
) != VALUE_HANDLE
)
634 if (TREE_CODE (op1
) == SSA_NAME
)
636 tree tmp
= SSA_NAME_VALUE (op1
);
637 if (tmp
&& TREE_CODE (tmp
) != VALUE_HANDLE
)
641 /* Stuff the operator and operands into our dummy conditional
642 expression, creating the dummy conditional if necessary. */
643 dummy_cond
= walk_data
->global_data
;
646 dummy_cond
= build (cond_code
, boolean_type_node
, op0
, op1
);
647 dummy_cond
= build (COND_EXPR
, void_type_node
,
648 dummy_cond
, NULL
, NULL
);
649 walk_data
->global_data
= dummy_cond
;
653 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), cond_code
);
654 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op0
;
655 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1) = op1
;
658 /* If the conditional folds to an invariant, then we are done,
659 otherwise look it up in the hash tables. */
660 cached_lhs
= local_fold (COND_EXPR_COND (dummy_cond
));
661 if (! is_gimple_min_invariant (cached_lhs
))
662 cached_lhs
= lookup_avail_expr (dummy_cond
, false);
663 if (!cached_lhs
|| ! is_gimple_min_invariant (cached_lhs
))
665 cached_lhs
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
670 /* We can have conditionals which just test the state of a
671 variable rather than use a relational operator. These are
672 simpler to handle. */
673 else if (TREE_CODE (cond
) == SSA_NAME
)
676 cached_lhs
= SSA_NAME_VALUE (cached_lhs
);
677 if (cached_lhs
&& ! is_gimple_min_invariant (cached_lhs
))
681 cached_lhs
= lookup_avail_expr (stmt
, false);
685 edge taken_edge
= find_taken_edge (e
->dest
, cached_lhs
);
686 basic_block dest
= (taken_edge
? taken_edge
->dest
: NULL
);
691 /* If we have a known destination for the conditional, then
692 we can perform this optimization, which saves at least one
693 conditional jump each time it applies since we get to
694 bypass the conditional at our original destination. */
697 update_bb_profile_for_threading (e
->dest
, EDGE_FREQUENCY (e
),
698 e
->count
, taken_edge
);
700 bb_ann (e
->dest
)->incoming_edge_threaded
= true;
707 /* Initialize local stacks for this optimizer and record equivalences
708 upon entry to BB. Equivalences can come from the edge traversed to
709 reach BB or they may come from PHI nodes at the start of BB. */
712 dom_opt_initialize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
715 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
717 /* Push a marker on the stacks of local information so that we know how
718 far to unwind when we finalize this block. */
719 VARRAY_PUSH_TREE (avail_exprs_stack
, NULL_TREE
);
720 VARRAY_PUSH_TREE (block_defs_stack
, NULL_TREE
);
721 VARRAY_PUSH_TREE (const_and_copies_stack
, NULL_TREE
);
722 VARRAY_PUSH_TREE (nonzero_vars_stack
, NULL_TREE
);
723 VARRAY_PUSH_TREE (vrp_variables_stack
, NULL_TREE
);
725 record_equivalences_from_incoming_edge (walk_data
, bb
);
727 /* PHI nodes can create equivalences too. */
728 record_equivalences_from_phis (walk_data
, bb
);
731 /* Given an expression EXPR (a relational expression or a statement),
732 initialize the hash table element pointed by by ELEMENT. */
735 initialize_hash_element (tree expr
, tree lhs
, struct expr_hash_elt
*element
)
737 /* Hash table elements may be based on conditional expressions or statements.
739 For the former case, we have no annotation and we want to hash the
740 conditional expression. In the latter case we have an annotation and
741 we want to record the expression the statement evaluates. */
742 if (COMPARISON_CLASS_P (expr
) || TREE_CODE (expr
) == TRUTH_NOT_EXPR
)
747 else if (TREE_CODE (expr
) == COND_EXPR
)
749 element
->ann
= stmt_ann (expr
);
750 element
->rhs
= COND_EXPR_COND (expr
);
752 else if (TREE_CODE (expr
) == SWITCH_EXPR
)
754 element
->ann
= stmt_ann (expr
);
755 element
->rhs
= SWITCH_COND (expr
);
757 else if (TREE_CODE (expr
) == RETURN_EXPR
&& TREE_OPERAND (expr
, 0))
759 element
->ann
= stmt_ann (expr
);
760 element
->rhs
= TREE_OPERAND (TREE_OPERAND (expr
, 0), 1);
764 element
->ann
= stmt_ann (expr
);
765 element
->rhs
= TREE_OPERAND (expr
, 1);
769 element
->hash
= avail_expr_hash (element
);
772 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
773 LIMIT entries left in LOCALs. */
776 remove_local_expressions_from_table (void)
778 /* Remove all the expressions made available in this block. */
779 while (VARRAY_ACTIVE_SIZE (avail_exprs_stack
) > 0)
781 struct expr_hash_elt element
;
782 tree expr
= VARRAY_TOP_TREE (avail_exprs_stack
);
783 VARRAY_POP (avail_exprs_stack
);
785 if (expr
== NULL_TREE
)
788 initialize_hash_element (expr
, NULL
, &element
);
789 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
793 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
794 state, stopping when there are LIMIT entries left in LOCALs. */
797 restore_nonzero_vars_to_original_value (void)
799 while (VARRAY_ACTIVE_SIZE (nonzero_vars_stack
) > 0)
801 tree name
= VARRAY_TOP_TREE (nonzero_vars_stack
);
802 VARRAY_POP (nonzero_vars_stack
);
807 bitmap_clear_bit (nonzero_vars
, SSA_NAME_VERSION (name
));
811 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
812 CONST_AND_COPIES to its original state, stopping when we hit a
816 restore_vars_to_original_value (void)
818 while (VARRAY_ACTIVE_SIZE (const_and_copies_stack
) > 0)
820 tree prev_value
, dest
;
822 dest
= VARRAY_TOP_TREE (const_and_copies_stack
);
823 VARRAY_POP (const_and_copies_stack
);
828 prev_value
= VARRAY_TOP_TREE (const_and_copies_stack
);
829 VARRAY_POP (const_and_copies_stack
);
831 SSA_NAME_VALUE (dest
) = prev_value
;
835 /* Similar to restore_vars_to_original_value, except that it restores
836 CURRDEFS to its original value. */
838 restore_currdefs_to_original_value (void)
840 /* Restore CURRDEFS to its original state. */
841 while (VARRAY_ACTIVE_SIZE (block_defs_stack
) > 0)
843 tree tmp
= VARRAY_TOP_TREE (block_defs_stack
);
846 VARRAY_POP (block_defs_stack
);
848 if (tmp
== NULL_TREE
)
851 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
852 definition of its underlying variable. If we recorded anything
853 else, it must have been an _DECL node and its current reaching
854 definition must have been NULL. */
855 if (TREE_CODE (tmp
) == SSA_NAME
)
858 var
= SSA_NAME_VAR (saved_def
);
866 var_ann (var
)->current_def
= saved_def
;
870 /* We have finished processing the dominator children of BB, perform
871 any finalization actions in preparation for leaving this node in
872 the dominator tree. */
875 dom_opt_finalize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
879 /* If we are at a leaf node in the dominator graph, see if we can thread
880 the edge from BB through its successor.
882 Do this before we remove entries from our equivalence tables. */
883 if (EDGE_COUNT (bb
->succs
) == 1
884 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
885 && (get_immediate_dominator (CDI_DOMINATORS
, EDGE_SUCC (bb
, 0)->dest
) != bb
886 || phi_nodes (EDGE_SUCC (bb
, 0)->dest
)))
889 thread_across_edge (walk_data
, EDGE_SUCC (bb
, 0));
891 else if ((last
= last_stmt (bb
))
892 && TREE_CODE (last
) == COND_EXPR
893 && (COMPARISON_CLASS_P (COND_EXPR_COND (last
))
894 || TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
)
895 && EDGE_COUNT (bb
->succs
) == 2
896 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
897 && (EDGE_SUCC (bb
, 1)->flags
& EDGE_ABNORMAL
) == 0)
899 edge true_edge
, false_edge
;
900 tree cond
, inverted
= NULL
;
901 enum tree_code cond_code
;
903 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
905 cond
= COND_EXPR_COND (last
);
906 cond_code
= TREE_CODE (cond
);
908 if (TREE_CODE_CLASS (cond_code
) == tcc_comparison
)
909 inverted
= invert_truthvalue (cond
);
911 /* If the THEN arm is the end of a dominator tree or has PHI nodes,
912 then try to thread through its edge. */
913 if (get_immediate_dominator (CDI_DOMINATORS
, true_edge
->dest
) != bb
914 || phi_nodes (true_edge
->dest
))
916 /* Push a marker onto the available expression stack so that we
917 unwind any expressions related to the TRUE arm before processing
918 the false arm below. */
919 VARRAY_PUSH_TREE (avail_exprs_stack
, NULL_TREE
);
920 VARRAY_PUSH_TREE (block_defs_stack
, NULL_TREE
);
921 VARRAY_PUSH_TREE (const_and_copies_stack
, NULL_TREE
);
923 /* Record any equivalences created by following this edge. */
924 if (TREE_CODE_CLASS (cond_code
) == tcc_comparison
)
926 record_cond (cond
, boolean_true_node
);
927 record_dominating_conditions (cond
);
928 record_cond (inverted
, boolean_false_node
);
930 else if (cond_code
== SSA_NAME
)
931 record_const_or_copy (cond
, boolean_true_node
);
933 /* Now thread the edge. */
934 thread_across_edge (walk_data
, true_edge
);
936 /* And restore the various tables to their state before
937 we threaded this edge. */
938 remove_local_expressions_from_table ();
939 restore_vars_to_original_value ();
940 restore_currdefs_to_original_value ();
943 /* Similarly for the ELSE arm. */
944 if (get_immediate_dominator (CDI_DOMINATORS
, false_edge
->dest
) != bb
945 || phi_nodes (false_edge
->dest
))
947 /* Record any equivalences created by following this edge. */
948 if (TREE_CODE_CLASS (cond_code
) == tcc_comparison
)
950 record_cond (cond
, boolean_false_node
);
951 record_cond (inverted
, boolean_true_node
);
952 record_dominating_conditions (inverted
);
954 else if (cond_code
== SSA_NAME
)
955 record_const_or_copy (cond
, boolean_false_node
);
957 thread_across_edge (walk_data
, false_edge
);
959 /* No need to remove local expressions from our tables
960 or restore vars to their original value as that will
961 be done immediately below. */
965 remove_local_expressions_from_table ();
966 restore_nonzero_vars_to_original_value ();
967 restore_vars_to_original_value ();
968 restore_currdefs_to_original_value ();
970 /* Remove VRP records associated with this basic block. They are no
973 To be efficient, we note which variables have had their values
974 constrained in this block. So walk over each variable in the
975 VRP_VARIABLEs array. */
976 while (VARRAY_ACTIVE_SIZE (vrp_variables_stack
) > 0)
978 tree var
= VARRAY_TOP_TREE (vrp_variables_stack
);
979 struct vrp_hash_elt vrp_hash_elt
, *vrp_hash_elt_p
;
982 /* Each variable has a stack of value range records. We want to
983 invalidate those associated with our basic block. So we walk
984 the array backwards popping off records associated with our
985 block. Once we hit a record not associated with our block
987 varray_type var_vrp_records
;
989 VARRAY_POP (vrp_variables_stack
);
994 vrp_hash_elt
.var
= var
;
995 vrp_hash_elt
.records
= NULL
;
997 slot
= htab_find_slot (vrp_data
, &vrp_hash_elt
, NO_INSERT
);
999 vrp_hash_elt_p
= (struct vrp_hash_elt
*) *slot
;
1000 var_vrp_records
= vrp_hash_elt_p
->records
;
1002 while (VARRAY_ACTIVE_SIZE (var_vrp_records
) > 0)
1004 struct vrp_element
*element
1005 = (struct vrp_element
*)VARRAY_TOP_GENERIC_PTR (var_vrp_records
);
1007 if (element
->bb
!= bb
)
1010 VARRAY_POP (var_vrp_records
);
1014 /* If we queued any statements to rescan in this block, then
1015 go ahead and rescan them now. */
1016 while (VARRAY_ACTIVE_SIZE (stmts_to_rescan
) > 0)
1018 tree stmt
= VARRAY_TOP_TREE (stmts_to_rescan
);
1019 basic_block stmt_bb
= bb_for_stmt (stmt
);
1024 VARRAY_POP (stmts_to_rescan
);
1025 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1029 /* PHI nodes can create equivalences too.
1031 Ignoring any alternatives which are the same as the result, if
1032 all the alternatives are equal, then the PHI node creates an
1035 Additionally, if all the PHI alternatives are known to have a nonzero
1036 value, then the result of this PHI is known to have a nonzero value,
1037 even if we do not know its exact value. */
1040 record_equivalences_from_phis (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1045 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1047 tree lhs
= PHI_RESULT (phi
);
1051 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1053 tree t
= PHI_ARG_DEF (phi
, i
);
1055 if (TREE_CODE (t
) == SSA_NAME
|| is_gimple_min_invariant (t
))
1057 /* Ignore alternatives which are the same as our LHS. */
1058 if (operand_equal_p (lhs
, t
, 0))
1061 /* If we have not processed an alternative yet, then set
1062 RHS to this alternative. */
1065 /* If we have processed an alternative (stored in RHS), then
1066 see if it is equal to this one. If it isn't, then stop
1068 else if (! operand_equal_p (rhs
, t
, 0))
1075 /* If we had no interesting alternatives, then all the RHS alternatives
1076 must have been the same as LHS. */
1080 /* If we managed to iterate through each PHI alternative without
1081 breaking out of the loop, then we have a PHI which may create
1082 a useful equivalence. We do not need to record unwind data for
1083 this, since this is a true assignment and not an equivalence
1084 inferred from a comparison. All uses of this ssa name are dominated
1085 by this assignment, so unwinding just costs time and space. */
1086 if (i
== PHI_NUM_ARGS (phi
)
1087 && may_propagate_copy (lhs
, rhs
))
1088 SSA_NAME_VALUE (lhs
) = rhs
;
1090 /* Now see if we know anything about the nonzero property for the
1091 result of this PHI. */
1092 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1094 if (!PHI_ARG_NONZERO (phi
, i
))
1098 if (i
== PHI_NUM_ARGS (phi
))
1099 bitmap_set_bit (nonzero_vars
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1101 register_new_def (lhs
, &block_defs_stack
);
1105 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1106 return that edge. Otherwise return NULL. */
1108 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
1114 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1116 /* A loop back edge can be identified by the destination of
1117 the edge dominating the source of the edge. */
1118 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
1121 /* If we have already seen a non-loop edge, then we must have
1122 multiple incoming non-loop edges and thus we return NULL. */
1126 /* This is the first non-loop incoming edge we have found. Record
1134 /* Record any equivalences created by the incoming edge to BB. If BB
1135 has more than one incoming edge, then no equivalence is created. */
1138 record_equivalences_from_incoming_edge (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1143 struct eq_expr_value eq_expr_value
;
1144 tree parent_block_last_stmt
= NULL
;
1146 /* If our parent block ended with a control statment, then we may be
1147 able to record some equivalences based on which outgoing edge from
1148 the parent was followed. */
1149 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1152 parent_block_last_stmt
= last_stmt (parent
);
1153 if (parent_block_last_stmt
&& !is_ctrl_stmt (parent_block_last_stmt
))
1154 parent_block_last_stmt
= NULL
;
1157 eq_expr_value
.src
= NULL
;
1158 eq_expr_value
.dst
= NULL
;
1160 /* If we have a single predecessor (ignoring loop backedges), then extract
1161 EDGE_FLAGS from the single incoming edge. Otherwise just return as
1162 there is nothing to do. */
1163 if (EDGE_COUNT (bb
->preds
) >= 1
1164 && parent_block_last_stmt
)
1166 edge e
= single_incoming_edge_ignoring_loop_edges (bb
);
1167 if (e
&& bb_for_stmt (parent_block_last_stmt
) == e
->src
)
1168 edge_flags
= e
->flags
;
1175 /* If our parent block ended in a COND_EXPR, add any equivalences
1176 created by the COND_EXPR to the hash table and initialize
1177 EQ_EXPR_VALUE appropriately.
1179 EQ_EXPR_VALUE is an assignment expression created when BB's immediate
1180 dominator ends in a COND_EXPR statement whose predicate is of the form
1181 'VAR == VALUE', where VALUE may be another variable or a constant.
1182 This is used to propagate VALUE on the THEN_CLAUSE of that
1183 conditional. This assignment is inserted in CONST_AND_COPIES so that
1184 the copy and constant propagator can find more propagation
1186 if (TREE_CODE (parent_block_last_stmt
) == COND_EXPR
1187 && (edge_flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1188 eq_expr_value
= get_eq_expr_value (parent_block_last_stmt
,
1189 (edge_flags
& EDGE_TRUE_VALUE
) != 0,
1191 /* Similarly when the parent block ended in a SWITCH_EXPR.
1192 We can only know the value of the switch's condition if the dominator
1193 parent is also the only predecessor of this block. */
1194 else if (EDGE_PRED (bb
, 0)->src
== parent
1195 && TREE_CODE (parent_block_last_stmt
) == SWITCH_EXPR
)
1197 tree switch_cond
= SWITCH_COND (parent_block_last_stmt
);
1199 /* If the switch's condition is an SSA variable, then we may
1200 know its value at each of the case labels. */
1201 if (TREE_CODE (switch_cond
) == SSA_NAME
)
1203 tree switch_vec
= SWITCH_LABELS (parent_block_last_stmt
);
1204 size_t i
, n
= TREE_VEC_LENGTH (switch_vec
);
1206 tree match_case
= NULL_TREE
;
1208 /* Search the case labels for those whose destination is
1209 the current basic block. */
1210 for (i
= 0; i
< n
; ++i
)
1212 tree elt
= TREE_VEC_ELT (switch_vec
, i
);
1213 if (label_to_block (CASE_LABEL (elt
)) == bb
)
1215 if (++case_count
> 1 || CASE_HIGH (elt
))
1221 /* If we encountered precisely one CASE_LABEL_EXPR and it
1222 was not the default case, or a case range, then we know
1223 the exact value of SWITCH_COND which caused us to get to
1224 this block. Record that equivalence in EQ_EXPR_VALUE. */
1227 && CASE_LOW (match_case
)
1228 && !CASE_HIGH (match_case
))
1230 eq_expr_value
.dst
= switch_cond
;
1231 eq_expr_value
.src
= fold_convert (TREE_TYPE (switch_cond
),
1232 CASE_LOW (match_case
));
1237 /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
1238 new value for VAR, so that occurrences of VAR can be replaced with
1239 VALUE while re-writing the THEN arm of a COND_EXPR. */
1240 if (eq_expr_value
.src
&& eq_expr_value
.dst
)
1241 record_equality (eq_expr_value
.dst
, eq_expr_value
.src
);
1244 /* Dump SSA statistics on FILE. */
1247 dump_dominator_optimization_stats (FILE *file
)
1251 fprintf (file
, "Total number of statements: %6ld\n\n",
1252 opt_stats
.num_stmts
);
1253 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1254 opt_stats
.num_exprs_considered
);
1256 n_exprs
= opt_stats
.num_exprs_considered
;
1260 fprintf (file
, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
1261 opt_stats
.num_re
, PERCENT (opt_stats
.num_re
,
1264 fprintf (file
, "\nHash table statistics:\n");
1266 fprintf (file
, " avail_exprs: ");
1267 htab_statistics (file
, avail_exprs
);
1271 /* Dump SSA statistics on stderr. */
1274 debug_dominator_optimization_stats (void)
1276 dump_dominator_optimization_stats (stderr
);
1280 /* Dump statistics for the hash table HTAB. */
1283 htab_statistics (FILE *file
, htab_t htab
)
1285 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1286 (long) htab_size (htab
),
1287 (long) htab_elements (htab
),
1288 htab_collisions (htab
));
1291 /* Record the fact that VAR has a nonzero value, though we may not know
1292 its exact value. Note that if VAR is already known to have a nonzero
1293 value, then we do nothing. */
1296 record_var_is_nonzero (tree var
)
1298 int indx
= SSA_NAME_VERSION (var
);
1300 if (bitmap_bit_p (nonzero_vars
, indx
))
1303 /* Mark it in the global table. */
1304 bitmap_set_bit (nonzero_vars
, indx
);
1306 /* Record this SSA_NAME so that we can reset the global table
1307 when we leave this block. */
1308 VARRAY_PUSH_TREE (nonzero_vars_stack
, var
);
1311 /* Enter a statement into the true/false expression hash table indicating
1312 that the condition COND has the value VALUE. */
1315 record_cond (tree cond
, tree value
)
1317 struct expr_hash_elt
*element
= xmalloc (sizeof (struct expr_hash_elt
));
1320 initialize_hash_element (cond
, value
, element
);
1322 slot
= htab_find_slot_with_hash (avail_exprs
, (void *)element
,
1323 element
->hash
, true);
1326 *slot
= (void *) element
;
1327 VARRAY_PUSH_TREE (avail_exprs_stack
, cond
);
1333 /* COND is a condition which is known to be true. Record variants of
1334 COND which must also be true.
1336 For example, if a < b is true, then a <= b must also be true. */
1339 record_dominating_conditions (tree cond
)
1341 switch (TREE_CODE (cond
))
1344 record_cond (build2 (LE_EXPR
, boolean_type_node
,
1345 TREE_OPERAND (cond
, 0),
1346 TREE_OPERAND (cond
, 1)),
1348 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1349 TREE_OPERAND (cond
, 0),
1350 TREE_OPERAND (cond
, 1)),
1352 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1353 TREE_OPERAND (cond
, 0),
1354 TREE_OPERAND (cond
, 1)),
1356 record_cond (build2 (LTGT_EXPR
, boolean_type_node
,
1357 TREE_OPERAND (cond
, 0),
1358 TREE_OPERAND (cond
, 1)),
1363 record_cond (build2 (GE_EXPR
, boolean_type_node
,
1364 TREE_OPERAND (cond
, 0),
1365 TREE_OPERAND (cond
, 1)),
1367 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1368 TREE_OPERAND (cond
, 0),
1369 TREE_OPERAND (cond
, 1)),
1371 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1372 TREE_OPERAND (cond
, 0),
1373 TREE_OPERAND (cond
, 1)),
1375 record_cond (build2 (LTGT_EXPR
, boolean_type_node
,
1376 TREE_OPERAND (cond
, 0),
1377 TREE_OPERAND (cond
, 1)),
1383 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1384 TREE_OPERAND (cond
, 0),
1385 TREE_OPERAND (cond
, 1)),
1390 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1391 TREE_OPERAND (cond
, 0),
1392 TREE_OPERAND (cond
, 1)),
1394 record_cond (build2 (LE_EXPR
, boolean_type_node
,
1395 TREE_OPERAND (cond
, 0),
1396 TREE_OPERAND (cond
, 1)),
1398 record_cond (build2 (GE_EXPR
, boolean_type_node
,
1399 TREE_OPERAND (cond
, 0),
1400 TREE_OPERAND (cond
, 1)),
1404 case UNORDERED_EXPR
:
1405 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1406 TREE_OPERAND (cond
, 0),
1407 TREE_OPERAND (cond
, 1)),
1409 record_cond (build2 (UNLE_EXPR
, boolean_type_node
,
1410 TREE_OPERAND (cond
, 0),
1411 TREE_OPERAND (cond
, 1)),
1413 record_cond (build2 (UNGE_EXPR
, boolean_type_node
,
1414 TREE_OPERAND (cond
, 0),
1415 TREE_OPERAND (cond
, 1)),
1417 record_cond (build2 (UNEQ_EXPR
, boolean_type_node
,
1418 TREE_OPERAND (cond
, 0),
1419 TREE_OPERAND (cond
, 1)),
1421 record_cond (build2 (UNLT_EXPR
, boolean_type_node
,
1422 TREE_OPERAND (cond
, 0),
1423 TREE_OPERAND (cond
, 1)),
1425 record_cond (build2 (UNGT_EXPR
, boolean_type_node
,
1426 TREE_OPERAND (cond
, 0),
1427 TREE_OPERAND (cond
, 1)),
1432 record_cond (build2 (UNLE_EXPR
, boolean_type_node
,
1433 TREE_OPERAND (cond
, 0),
1434 TREE_OPERAND (cond
, 1)),
1436 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1437 TREE_OPERAND (cond
, 0),
1438 TREE_OPERAND (cond
, 1)),
1443 record_cond (build2 (UNGE_EXPR
, boolean_type_node
,
1444 TREE_OPERAND (cond
, 0),
1445 TREE_OPERAND (cond
, 1)),
1447 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1448 TREE_OPERAND (cond
, 0),
1449 TREE_OPERAND (cond
, 1)),
1454 record_cond (build2 (UNLE_EXPR
, boolean_type_node
,
1455 TREE_OPERAND (cond
, 0),
1456 TREE_OPERAND (cond
, 1)),
1458 record_cond (build2 (UNGE_EXPR
, boolean_type_node
,
1459 TREE_OPERAND (cond
, 0),
1460 TREE_OPERAND (cond
, 1)),
1465 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1466 TREE_OPERAND (cond
, 0),
1467 TREE_OPERAND (cond
, 1)),
1469 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1470 TREE_OPERAND (cond
, 0),
1471 TREE_OPERAND (cond
, 1)),
1479 /* A helper function for record_const_or_copy and record_equality.
1480 Do the work of recording the value and undo info. */
1483 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
)
1485 SSA_NAME_VALUE (x
) = y
;
1487 VARRAY_PUSH_TREE (const_and_copies_stack
, prev_x
);
1488 VARRAY_PUSH_TREE (const_and_copies_stack
, x
);
1491 /* Record that X is equal to Y in const_and_copies. Record undo
1492 information in the block-local varray. */
1495 record_const_or_copy (tree x
, tree y
)
1497 tree prev_x
= SSA_NAME_VALUE (x
);
1499 if (TREE_CODE (y
) == SSA_NAME
)
1501 tree tmp
= SSA_NAME_VALUE (y
);
1506 record_const_or_copy_1 (x
, y
, prev_x
);
1509 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1510 This constrains the cases in which we may treat this as assignment. */
1513 record_equality (tree x
, tree y
)
1515 tree prev_x
= NULL
, prev_y
= NULL
;
1517 if (TREE_CODE (x
) == SSA_NAME
)
1518 prev_x
= SSA_NAME_VALUE (x
);
1519 if (TREE_CODE (y
) == SSA_NAME
)
1520 prev_y
= SSA_NAME_VALUE (y
);
1522 /* If one of the previous values is invariant, then use that.
1523 Otherwise it doesn't matter which value we choose, just so
1524 long as we canonicalize on one value. */
1525 if (TREE_INVARIANT (y
))
1527 else if (TREE_INVARIANT (x
))
1528 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1529 else if (prev_x
&& TREE_INVARIANT (prev_x
))
1530 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1531 else if (prev_y
&& TREE_CODE (prev_y
) != VALUE_HANDLE
)
1534 /* After the swapping, we must have one SSA_NAME. */
1535 if (TREE_CODE (x
) != SSA_NAME
)
1538 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1539 variable compared against zero. If we're honoring signed zeros,
1540 then we cannot record this value unless we know that the value is
1542 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1543 && (TREE_CODE (y
) != REAL_CST
1544 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1547 record_const_or_copy_1 (x
, y
, prev_x
);
1550 /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
1551 hash tables. Try to simplify the RHS using whatever equivalences
1552 we may have recorded.
1554 If we are able to simplify the RHS, then lookup the simplified form in
1555 the hash table and return the result. Otherwise return NULL. */
1558 simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*walk_data
,
1559 tree stmt
, int insert
)
1561 tree rhs
= TREE_OPERAND (stmt
, 1);
1562 enum tree_code rhs_code
= TREE_CODE (rhs
);
1565 /* If we have lhs = ~x, look and see if we earlier had x = ~y.
1566 In which case we can change this statement to be lhs = y.
1567 Which can then be copy propagated.
1569 Similarly for negation. */
1570 if ((rhs_code
== BIT_NOT_EXPR
|| rhs_code
== NEGATE_EXPR
)
1571 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
1573 /* Get the definition statement for our RHS. */
1574 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1576 /* See if the RHS_DEF_STMT has the same form as our statement. */
1577 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
1578 && TREE_CODE (TREE_OPERAND (rhs_def_stmt
, 1)) == rhs_code
)
1580 tree rhs_def_operand
;
1582 rhs_def_operand
= TREE_OPERAND (TREE_OPERAND (rhs_def_stmt
, 1), 0);
1584 /* Verify that RHS_DEF_OPERAND is a suitable SSA variable. */
1585 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
1586 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
1587 result
= update_rhs_and_lookup_avail_expr (stmt
,
1593 /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
1594 If OP is associative, create and fold (y OP C2) OP C1 which
1595 should result in (y OP C3), use that as the RHS for the
1596 assignment. Add minus to this, as we handle it specially below. */
1597 if ((associative_tree_code (rhs_code
) || rhs_code
== MINUS_EXPR
)
1598 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
1599 && is_gimple_min_invariant (TREE_OPERAND (rhs
, 1)))
1601 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1603 /* See if the RHS_DEF_STMT has the same form as our statement. */
1604 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
)
1606 tree rhs_def_rhs
= TREE_OPERAND (rhs_def_stmt
, 1);
1607 enum tree_code rhs_def_code
= TREE_CODE (rhs_def_rhs
);
1609 if (rhs_code
== rhs_def_code
1610 || (rhs_code
== PLUS_EXPR
&& rhs_def_code
== MINUS_EXPR
)
1611 || (rhs_code
== MINUS_EXPR
&& rhs_def_code
== PLUS_EXPR
))
1613 tree def_stmt_op0
= TREE_OPERAND (rhs_def_rhs
, 0);
1614 tree def_stmt_op1
= TREE_OPERAND (rhs_def_rhs
, 1);
1616 if (TREE_CODE (def_stmt_op0
) == SSA_NAME
1617 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0
)
1618 && is_gimple_min_invariant (def_stmt_op1
))
1620 tree outer_const
= TREE_OPERAND (rhs
, 1);
1621 tree type
= TREE_TYPE (TREE_OPERAND (stmt
, 0));
1624 /* If we care about correct floating point results, then
1625 don't fold x + c1 - c2. Note that we need to take both
1626 the codes and the signs to figure this out. */
1627 if (FLOAT_TYPE_P (type
)
1628 && !flag_unsafe_math_optimizations
1629 && (rhs_def_code
== PLUS_EXPR
1630 || rhs_def_code
== MINUS_EXPR
))
1634 neg
^= (rhs_code
== MINUS_EXPR
);
1635 neg
^= (rhs_def_code
== MINUS_EXPR
);
1636 neg
^= real_isneg (TREE_REAL_CST_PTR (outer_const
));
1637 neg
^= real_isneg (TREE_REAL_CST_PTR (def_stmt_op1
));
1640 goto dont_fold_assoc
;
1643 /* Ho hum. So fold will only operate on the outermost
1644 thingy that we give it, so we have to build the new
1645 expression in two pieces. This requires that we handle
1646 combinations of plus and minus. */
1647 if (rhs_def_code
!= rhs_code
)
1649 if (rhs_def_code
== MINUS_EXPR
)
1650 t
= build (MINUS_EXPR
, type
, outer_const
, def_stmt_op1
);
1652 t
= build (MINUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1653 rhs_code
= PLUS_EXPR
;
1655 else if (rhs_def_code
== MINUS_EXPR
)
1656 t
= build (PLUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1658 t
= build (rhs_def_code
, type
, def_stmt_op1
, outer_const
);
1660 t
= build (rhs_code
, type
, def_stmt_op0
, t
);
1663 /* If the result is a suitable looking gimple expression,
1664 then use it instead of the original for STMT. */
1665 if (TREE_CODE (t
) == SSA_NAME
1666 || (UNARY_CLASS_P (t
)
1667 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
1668 || ((BINARY_CLASS_P (t
) || COMPARISON_CLASS_P (t
))
1669 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
1670 && is_gimple_val (TREE_OPERAND (t
, 1))))
1671 result
= update_rhs_and_lookup_avail_expr (stmt
, t
, insert
);
1678 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1679 and BIT_AND_EXPR respectively if the first operand is greater
1680 than zero and the second operand is an exact power of two. */
1681 if ((rhs_code
== TRUNC_DIV_EXPR
|| rhs_code
== TRUNC_MOD_EXPR
)
1682 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
1683 && integer_pow2p (TREE_OPERAND (rhs
, 1)))
1686 tree op
= TREE_OPERAND (rhs
, 0);
1688 if (TYPE_UNSIGNED (TREE_TYPE (op
)))
1690 val
= integer_one_node
;
1694 tree dummy_cond
= walk_data
->global_data
;
1698 dummy_cond
= build (GT_EXPR
, boolean_type_node
,
1699 op
, integer_zero_node
);
1700 dummy_cond
= build (COND_EXPR
, void_type_node
,
1701 dummy_cond
, NULL
, NULL
);
1702 walk_data
->global_data
= dummy_cond
;
1706 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), GT_EXPR
);
1707 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
1708 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
1709 = integer_zero_node
;
1711 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
, NULL
, false);
1714 if (val
&& integer_onep (val
))
1717 tree op0
= TREE_OPERAND (rhs
, 0);
1718 tree op1
= TREE_OPERAND (rhs
, 1);
1720 if (rhs_code
== TRUNC_DIV_EXPR
)
1721 t
= build (RSHIFT_EXPR
, TREE_TYPE (op0
), op0
,
1722 build_int_cst (NULL_TREE
, tree_log2 (op1
)));
1724 t
= build (BIT_AND_EXPR
, TREE_TYPE (op0
), op0
,
1725 local_fold (build (MINUS_EXPR
, TREE_TYPE (op1
),
1726 op1
, integer_one_node
)));
1728 result
= update_rhs_and_lookup_avail_expr (stmt
, t
, insert
);
1732 /* Transform ABS (X) into X or -X as appropriate. */
1733 if (rhs_code
== ABS_EXPR
1734 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
1737 tree op
= TREE_OPERAND (rhs
, 0);
1738 tree type
= TREE_TYPE (op
);
1740 if (TYPE_UNSIGNED (type
))
1742 val
= integer_zero_node
;
1746 tree dummy_cond
= walk_data
->global_data
;
1750 dummy_cond
= build (LE_EXPR
, boolean_type_node
,
1751 op
, integer_zero_node
);
1752 dummy_cond
= build (COND_EXPR
, void_type_node
,
1753 dummy_cond
, NULL
, NULL
);
1754 walk_data
->global_data
= dummy_cond
;
1758 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), LE_EXPR
);
1759 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
1760 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
1761 = build_int_cst (type
, 0);
1763 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
, NULL
, false);
1767 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), GE_EXPR
);
1768 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
1769 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
1770 = build_int_cst (type
, 0);
1772 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
1777 if (integer_zerop (val
))
1778 val
= integer_one_node
;
1779 else if (integer_onep (val
))
1780 val
= integer_zero_node
;
1786 && (integer_onep (val
) || integer_zerop (val
)))
1790 if (integer_onep (val
))
1791 t
= build1 (NEGATE_EXPR
, TREE_TYPE (op
), op
);
1795 result
= update_rhs_and_lookup_avail_expr (stmt
, t
, insert
);
1799 /* Optimize *"foo" into 'f'. This is done here rather than
1800 in fold to avoid problems with stuff like &*"foo". */
1801 if (TREE_CODE (rhs
) == INDIRECT_REF
|| TREE_CODE (rhs
) == ARRAY_REF
)
1803 tree t
= fold_read_from_constant_string (rhs
);
1806 result
= update_rhs_and_lookup_avail_expr (stmt
, t
, insert
);
1812 /* COND is a condition of the form:
1814 x == const or x != const
1816 Look back to x's defining statement and see if x is defined as
1820 If const is unchanged if we convert it to type, then we can build
1821 the equivalent expression:
1824 y == const or y != const
1826 Which may allow further optimizations.
1828 Return the equivalent comparison or NULL if no such equivalent comparison
1832 find_equivalent_equality_comparison (tree cond
)
1834 tree op0
= TREE_OPERAND (cond
, 0);
1835 tree op1
= TREE_OPERAND (cond
, 1);
1836 tree def_stmt
= SSA_NAME_DEF_STMT (op0
);
1838 /* OP0 might have been a parameter, so first make sure it
1839 was defined by a MODIFY_EXPR. */
1840 if (def_stmt
&& TREE_CODE (def_stmt
) == MODIFY_EXPR
)
1842 tree def_rhs
= TREE_OPERAND (def_stmt
, 1);
1844 /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
1845 if ((TREE_CODE (def_rhs
) == NOP_EXPR
1846 || TREE_CODE (def_rhs
) == CONVERT_EXPR
)
1847 && TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == SSA_NAME
)
1849 tree def_rhs_inner
= TREE_OPERAND (def_rhs
, 0);
1850 tree def_rhs_inner_type
= TREE_TYPE (def_rhs_inner
);
1853 if (TYPE_PRECISION (def_rhs_inner_type
)
1854 > TYPE_PRECISION (TREE_TYPE (def_rhs
)))
1857 /* What we want to prove is that if we convert OP1 to
1858 the type of the object inside the NOP_EXPR that the
1859 result is still equivalent to SRC.
1861 If that is true, the build and return new equivalent
1862 condition which uses the source of the typecast and the
1863 new constant (which has only changed its type). */
1864 new = build1 (TREE_CODE (def_rhs
), def_rhs_inner_type
, op1
);
1865 new = local_fold (new);
1866 if (is_gimple_val (new) && tree_int_cst_equal (new, op1
))
1867 return build (TREE_CODE (cond
), TREE_TYPE (cond
),
1868 def_rhs_inner
, new);
1874 /* STMT is a COND_EXPR for which we could not trivially determine its
1875 result. This routine attempts to find equivalent forms of the
1876 condition which we may be able to optimize better. It also
1877 uses simple value range propagation to optimize conditionals. */
1880 simplify_cond_and_lookup_avail_expr (tree stmt
,
1884 tree cond
= COND_EXPR_COND (stmt
);
1886 if (COMPARISON_CLASS_P (cond
))
1888 tree op0
= TREE_OPERAND (cond
, 0);
1889 tree op1
= TREE_OPERAND (cond
, 1);
1891 if (TREE_CODE (op0
) == SSA_NAME
&& is_gimple_min_invariant (op1
))
1894 tree low
, high
, cond_low
, cond_high
;
1895 int lowequal
, highequal
, swapped
, no_overlap
, subset
, cond_inverted
;
1896 varray_type vrp_records
;
1897 struct vrp_element
*element
;
1898 struct vrp_hash_elt vrp_hash_elt
, *vrp_hash_elt_p
;
1901 /* First see if we have test of an SSA_NAME against a constant
1902 where the SSA_NAME is defined by an earlier typecast which
1903 is irrelevant when performing tests against the given
1905 if (TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
1907 tree new_cond
= find_equivalent_equality_comparison (cond
);
1911 /* Update the statement to use the new equivalent
1913 COND_EXPR_COND (stmt
) = new_cond
;
1915 /* If this is not a real stmt, ann will be NULL and we
1916 avoid processing the operands. */
1920 /* Lookup the condition and return its known value if it
1922 new_cond
= lookup_avail_expr (stmt
, insert
);
1926 /* The operands have changed, so update op0 and op1. */
1927 op0
= TREE_OPERAND (cond
, 0);
1928 op1
= TREE_OPERAND (cond
, 1);
1932 /* Consult the value range records for this variable (if they exist)
1933 to see if we can eliminate or simplify this conditional.
1935 Note two tests are necessary to determine no records exist.
1936 First we have to see if the virtual array exists, if it
1937 exists, then we have to check its active size.
1939 Also note the vast majority of conditionals are not testing
1940 a variable which has had its range constrained by an earlier
1941 conditional. So this filter avoids a lot of unnecessary work. */
1942 vrp_hash_elt
.var
= op0
;
1943 vrp_hash_elt
.records
= NULL
;
1944 slot
= htab_find_slot (vrp_data
, &vrp_hash_elt
, NO_INSERT
);
1948 vrp_hash_elt_p
= (struct vrp_hash_elt
*) *slot
;
1949 vrp_records
= vrp_hash_elt_p
->records
;
1950 if (vrp_records
== NULL
)
1953 limit
= VARRAY_ACTIVE_SIZE (vrp_records
);
1955 /* If we have no value range records for this variable, or we are
1956 unable to extract a range for this condition, then there is
1959 || ! extract_range_from_cond (cond
, &cond_high
,
1960 &cond_low
, &cond_inverted
))
1963 /* We really want to avoid unnecessary computations of range
1964 info. So all ranges are computed lazily; this avoids a
1965 lot of unnecessary work. i.e., we record the conditional,
1966 but do not process how it constrains the variable's
1967 potential values until we know that processing the condition
1970 However, we do not want to have to walk a potentially long
1971 list of ranges, nor do we want to compute a variable's
1972 range more than once for a given path.
1974 Luckily, each time we encounter a conditional that can not
1975 be otherwise optimized we will end up here and we will
1976 compute the necessary range information for the variable
1977 used in this condition.
1979 Thus you can conclude that there will never be more than one
1980 conditional associated with a variable which has not been
1981 processed. So we never need to merge more than one new
1982 conditional into the current range.
1984 These properties also help us avoid unnecessary work. */
1986 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
, limit
- 1);
1988 if (element
->high
&& element
->low
)
1990 /* The last element has been processed, so there is no range
1991 merging to do, we can simply use the high/low values
1992 recorded in the last element. */
1994 high
= element
->high
;
1998 tree tmp_high
, tmp_low
;
2001 /* The last element has not been processed. Process it now. */
2002 extract_range_from_cond (element
->cond
, &tmp_high
,
2005 /* If this is the only element, then no merging is necessary,
2006 the high/low values from extract_range_from_cond are all
2015 /* Get the high/low value from the previous element. */
2016 struct vrp_element
*prev
2017 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
,
2022 /* Merge in this element's range with the range from the
2025 The low value for the merged range is the maximum of
2026 the previous low value and the low value of this record.
2028 Similarly the high value for the merged range is the
2029 minimum of the previous high value and the high value of
2031 low
= (tree_int_cst_compare (low
, tmp_low
) == 1
2033 high
= (tree_int_cst_compare (high
, tmp_high
) == -1
2037 /* And record the computed range. */
2039 element
->high
= high
;
2043 /* After we have constrained this variable's potential values,
2044 we try to determine the result of the given conditional.
2046 To simplify later tests, first determine if the current
2047 low value is the same low value as the conditional.
2048 Similarly for the current high value and the high value
2049 for the conditional. */
2050 lowequal
= tree_int_cst_equal (low
, cond_low
);
2051 highequal
= tree_int_cst_equal (high
, cond_high
);
2053 if (lowequal
&& highequal
)
2054 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2056 /* To simplify the overlap/subset tests below we may want
2057 to swap the two ranges so that the larger of the two
2058 ranges occurs "first". */
2060 if (tree_int_cst_compare (low
, cond_low
) == 1
2062 && tree_int_cst_compare (cond_high
, high
) == 1))
2075 /* Now determine if there is no overlap in the ranges
2076 or if the second range is a subset of the first range. */
2077 no_overlap
= tree_int_cst_lt (high
, cond_low
);
2078 subset
= tree_int_cst_compare (cond_high
, high
) != 1;
2080 /* If there was no overlap in the ranges, then this conditional
2081 always has a false value (unless we had to invert this
2082 conditional, in which case it always has a true value). */
2084 return (cond_inverted
? boolean_true_node
: boolean_false_node
);
2086 /* If the current range is a subset of the condition's range,
2087 then this conditional always has a true value (unless we
2088 had to invert this conditional, in which case it always
2089 has a true value). */
2090 if (subset
&& swapped
)
2091 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2093 /* We were unable to determine the result of the conditional.
2094 However, we may be able to simplify the conditional. First
2095 merge the ranges in the same manner as range merging above. */
2096 low
= tree_int_cst_compare (low
, cond_low
) == 1 ? low
: cond_low
;
2097 high
= tree_int_cst_compare (high
, cond_high
) == -1 ? high
: cond_high
;
2099 /* If the range has converged to a single point, then turn this
2100 into an equality comparison. */
2101 if (TREE_CODE (cond
) != EQ_EXPR
2102 && TREE_CODE (cond
) != NE_EXPR
2103 && tree_int_cst_equal (low
, high
))
2105 TREE_SET_CODE (cond
, EQ_EXPR
);
2106 TREE_OPERAND (cond
, 1) = high
;
2113 /* STMT is a SWITCH_EXPR for which we could not trivially determine its
2114 result. This routine attempts to find equivalent forms of the
2115 condition which we may be able to optimize better. */
2118 simplify_switch_and_lookup_avail_expr (tree stmt
, int insert
)
2120 tree cond
= SWITCH_COND (stmt
);
2123 /* The optimization that we really care about is removing unnecessary
2124 casts. That will let us do much better in propagating the inferred
2125 constant at the switch target. */
2126 if (TREE_CODE (cond
) == SSA_NAME
)
2128 def
= SSA_NAME_DEF_STMT (cond
);
2129 if (TREE_CODE (def
) == MODIFY_EXPR
)
2131 def
= TREE_OPERAND (def
, 1);
2132 if (TREE_CODE (def
) == NOP_EXPR
)
2137 def
= TREE_OPERAND (def
, 0);
2139 #ifdef ENABLE_CHECKING
2140 /* ??? Why was Jeff testing this? We are gimple... */
2141 gcc_assert (is_gimple_val (def
));
2144 to
= TREE_TYPE (cond
);
2145 ti
= TREE_TYPE (def
);
2147 /* If we have an extension that preserves value, then we
2148 can copy the source value into the switch. */
2150 need_precision
= TYPE_PRECISION (ti
);
2152 if (TYPE_UNSIGNED (to
) && !TYPE_UNSIGNED (ti
))
2154 else if (!TYPE_UNSIGNED (to
) && TYPE_UNSIGNED (ti
))
2155 need_precision
+= 1;
2156 if (TYPE_PRECISION (to
) < need_precision
)
2161 SWITCH_COND (stmt
) = def
;
2164 return lookup_avail_expr (stmt
, insert
);
2174 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2175 known value for that SSA_NAME (or NULL if no value is known).
2177 NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
2178 even if we don't know their precise value.
2180 Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
2181 nodes of the successors of BB. */
2184 cprop_into_successor_phis (basic_block bb
, bitmap nonzero_vars
)
2189 /* This can get rather expensive if the implementation is naive in
2190 how it finds the phi alternative associated with a particular edge. */
2191 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2197 /* If this is an abnormal edge, then we do not want to copy propagate
2198 into the PHI alternative associated with this edge. */
2199 if (e
->flags
& EDGE_ABNORMAL
)
2202 phi
= phi_nodes (e
->dest
);
2206 /* There is no guarantee that for any two PHI nodes in a block that
2207 the phi alternative associated with a particular edge will be
2208 at the same index in the phi alternative array.
2210 However, it is very likely they will be the same. So we keep
2211 track of the index of the alternative where we found the edge in
2212 the previous phi node and check that index first in the next
2213 phi node. If that hint fails, then we actually search all
2215 phi_num_args
= PHI_NUM_ARGS (phi
);
2216 hint
= phi_num_args
;
2217 for ( ; phi
; phi
= PHI_CHAIN (phi
))
2221 use_operand_p orig_p
;
2224 /* If the hint is valid (!= phi_num_args), see if it points
2225 us to the desired phi alternative. */
2226 if (hint
!= phi_num_args
&& PHI_ARG_EDGE (phi
, hint
) == e
)
2230 /* The hint was either invalid or did not point to the
2231 correct phi alternative. Search all the alternatives
2232 for the correct one. Update the hint. */
2233 for (i
= 0; i
< phi_num_args
; i
++)
2234 if (PHI_ARG_EDGE (phi
, i
) == e
)
2239 /* If we did not find the proper alternative, then something is
2241 gcc_assert (hint
!= phi_num_args
);
2243 /* The alternative may be associated with a constant, so verify
2244 it is an SSA_NAME before doing anything with it. */
2245 orig_p
= PHI_ARG_DEF_PTR (phi
, hint
);
2246 orig
= USE_FROM_PTR (orig_p
);
2247 if (TREE_CODE (orig
) != SSA_NAME
)
2250 /* If the alternative is known to have a nonzero value, record
2251 that fact in the PHI node itself for future use. */
2252 if (bitmap_bit_p (nonzero_vars
, SSA_NAME_VERSION (orig
)))
2253 PHI_ARG_NONZERO (phi
, hint
) = true;
2255 /* If we have *ORIG_P in our constant/copy table, then replace
2256 ORIG_P with its value in our constant/copy table. */
2257 new = SSA_NAME_VALUE (orig
);
2259 && (TREE_CODE (new) == SSA_NAME
2260 || is_gimple_min_invariant (new))
2261 && may_propagate_copy (orig
, new))
2263 propagate_value (orig_p
, new);
2270 /* Propagate known constants/copies into PHI nodes of BB's successor
2274 cprop_into_phis (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
2277 cprop_into_successor_phis (bb
, nonzero_vars
);
2280 /* Search for redundant computations in STMT. If any are found, then
2281 replace them with the variable holding the result of the computation.
2283 If safe, record this expression into the available expression hash
2287 eliminate_redundant_computations (struct dom_walk_data
*walk_data
,
2288 tree stmt
, stmt_ann_t ann
)
2290 v_may_def_optype v_may_defs
= V_MAY_DEF_OPS (ann
);
2291 tree
*expr_p
, def
= NULL_TREE
;
2294 bool retval
= false;
2296 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2297 def
= TREE_OPERAND (stmt
, 0);
2299 /* Certain expressions on the RHS can be optimized away, but can not
2300 themselves be entered into the hash tables. */
2301 if (ann
->makes_aliased_stores
2303 || TREE_CODE (def
) != SSA_NAME
2304 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
2305 || NUM_V_MAY_DEFS (v_may_defs
) != 0)
2308 /* Check if the expression has been computed before. */
2309 cached_lhs
= lookup_avail_expr (stmt
, insert
);
2311 /* If this is an assignment and the RHS was not in the hash table,
2312 then try to simplify the RHS and lookup the new RHS in the
2314 if (! cached_lhs
&& TREE_CODE (stmt
) == MODIFY_EXPR
)
2315 cached_lhs
= simplify_rhs_and_lookup_avail_expr (walk_data
, stmt
, insert
);
2316 /* Similarly if this is a COND_EXPR and we did not find its
2317 expression in the hash table, simplify the condition and
2319 else if (! cached_lhs
&& TREE_CODE (stmt
) == COND_EXPR
)
2320 cached_lhs
= simplify_cond_and_lookup_avail_expr (stmt
, ann
, insert
);
2321 /* Similarly for a SWITCH_EXPR. */
2322 else if (!cached_lhs
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
2323 cached_lhs
= simplify_switch_and_lookup_avail_expr (stmt
, insert
);
2325 opt_stats
.num_exprs_considered
++;
2327 /* Get a pointer to the expression we are trying to optimize. */
2328 if (TREE_CODE (stmt
) == COND_EXPR
)
2329 expr_p
= &COND_EXPR_COND (stmt
);
2330 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2331 expr_p
= &SWITCH_COND (stmt
);
2332 else if (TREE_CODE (stmt
) == RETURN_EXPR
&& TREE_OPERAND (stmt
, 0))
2333 expr_p
= &TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
2335 expr_p
= &TREE_OPERAND (stmt
, 1);
2337 /* It is safe to ignore types here since we have already done
2338 type checking in the hashing and equality routines. In fact
2339 type checking here merely gets in the way of constant
2340 propagation. Also, make sure that it is safe to propagate
2341 CACHED_LHS into *EXPR_P. */
2343 && (TREE_CODE (cached_lhs
) != SSA_NAME
2344 || may_propagate_copy (*expr_p
, cached_lhs
)))
2346 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2348 fprintf (dump_file
, " Replaced redundant expr '");
2349 print_generic_expr (dump_file
, *expr_p
, dump_flags
);
2350 fprintf (dump_file
, "' with '");
2351 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
2352 fprintf (dump_file
, "'\n");
2357 #if defined ENABLE_CHECKING
2358 gcc_assert (TREE_CODE (cached_lhs
) == SSA_NAME
2359 || is_gimple_min_invariant (cached_lhs
));
2362 if (TREE_CODE (cached_lhs
) == ADDR_EXPR
2363 || (POINTER_TYPE_P (TREE_TYPE (*expr_p
))
2364 && is_gimple_min_invariant (cached_lhs
)))
2367 propagate_tree_value (expr_p
, cached_lhs
);
2373 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
2374 the available expressions table or the const_and_copies table.
2375 Detect and record those equivalences. */
2378 record_equivalences_from_stmt (tree stmt
,
2382 tree lhs
= TREE_OPERAND (stmt
, 0);
2383 enum tree_code lhs_code
= TREE_CODE (lhs
);
2386 if (lhs_code
== SSA_NAME
)
2388 tree rhs
= TREE_OPERAND (stmt
, 1);
2390 /* Strip away any useless type conversions. */
2391 STRIP_USELESS_TYPE_CONVERSION (rhs
);
2393 /* If the RHS of the assignment is a constant or another variable that
2394 may be propagated, register it in the CONST_AND_COPIES table. We
2395 do not need to record unwind data for this, since this is a true
2396 assignment and not an equivalence inferred from a comparison. All
2397 uses of this ssa name are dominated by this assignment, so unwinding
2398 just costs time and space. */
2400 && (TREE_CODE (rhs
) == SSA_NAME
2401 || is_gimple_min_invariant (rhs
)))
2402 SSA_NAME_VALUE (lhs
) = rhs
;
2404 /* alloca never returns zero and the address of a non-weak symbol
2405 is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
2406 stripped as they do not affect this equivalence. */
2407 while (TREE_CODE (rhs
) == NOP_EXPR
2408 || TREE_CODE (rhs
) == CONVERT_EXPR
)
2409 rhs
= TREE_OPERAND (rhs
, 0);
2411 if (alloca_call_p (rhs
)
2412 || (TREE_CODE (rhs
) == ADDR_EXPR
2413 && DECL_P (TREE_OPERAND (rhs
, 0))
2414 && ! DECL_WEAK (TREE_OPERAND (rhs
, 0))))
2415 record_var_is_nonzero (lhs
);
2417 /* IOR of any value with a nonzero value will result in a nonzero
2418 value. Even if we do not know the exact result recording that
2419 the result is nonzero is worth the effort. */
2420 if (TREE_CODE (rhs
) == BIT_IOR_EXPR
2421 && integer_nonzerop (TREE_OPERAND (rhs
, 1)))
2422 record_var_is_nonzero (lhs
);
2425 /* Look at both sides for pointer dereferences. If we find one, then
2426 the pointer must be nonnull and we can enter that equivalence into
2428 if (flag_delete_null_pointer_checks
)
2429 for (i
= 0; i
< 2; i
++)
2431 tree t
= TREE_OPERAND (stmt
, i
);
2433 /* Strip away any COMPONENT_REFs. */
2434 while (TREE_CODE (t
) == COMPONENT_REF
)
2435 t
= TREE_OPERAND (t
, 0);
2437 /* Now see if this is a pointer dereference. */
2438 if (TREE_CODE (t
) == INDIRECT_REF
2439 || TREE_CODE (t
) == ALIGN_INDIRECT_REF
2440 || TREE_CODE (t
) == MISALIGNED_INDIRECT_REF
)
2442 tree op
= TREE_OPERAND (t
, 0);
2444 /* If the pointer is a SSA variable, then enter new
2445 equivalences into the hash table. */
2446 while (TREE_CODE (op
) == SSA_NAME
)
2448 tree def
= SSA_NAME_DEF_STMT (op
);
2450 record_var_is_nonzero (op
);
2452 /* And walk up the USE-DEF chains noting other SSA_NAMEs
2453 which are known to have a nonzero value. */
2455 && TREE_CODE (def
) == MODIFY_EXPR
2456 && TREE_CODE (TREE_OPERAND (def
, 1)) == NOP_EXPR
)
2457 op
= TREE_OPERAND (TREE_OPERAND (def
, 1), 0);
2464 /* A memory store, even an aliased store, creates a useful
2465 equivalence. By exchanging the LHS and RHS, creating suitable
2466 vops and recording the result in the available expression table,
2467 we may be able to expose more redundant loads. */
2468 if (!ann
->has_volatile_ops
2469 && (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
2470 || is_gimple_min_invariant (TREE_OPERAND (stmt
, 1)))
2471 && !is_gimple_reg (lhs
))
2473 tree rhs
= TREE_OPERAND (stmt
, 1);
2476 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
2477 is a constant, we need to adjust the constant to fit into the
2478 type of the LHS. If the LHS is a bitfield and the RHS is not
2479 a constant, then we can not record any equivalences for this
2480 statement since we would need to represent the widening or
2481 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
2482 and should not be necessary if GCC represented bitfields
2484 if (lhs_code
== COMPONENT_REF
2485 && DECL_BIT_FIELD (TREE_OPERAND (lhs
, 1)))
2487 if (TREE_CONSTANT (rhs
))
2488 rhs
= widen_bitfield (rhs
, TREE_OPERAND (lhs
, 1), lhs
);
2492 /* If the value overflowed, then we can not use this equivalence. */
2493 if (rhs
&& ! is_gimple_min_invariant (rhs
))
2499 /* Build a new statement with the RHS and LHS exchanged. */
2500 new = build (MODIFY_EXPR
, TREE_TYPE (stmt
), rhs
, lhs
);
2502 create_ssa_artficial_load_stmt (&(ann
->operands
), new);
2504 /* Finally enter the statement into the available expression
2506 lookup_avail_expr (new, true);
2511 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2512 CONST_AND_COPIES. */
2515 cprop_operand (tree stmt
, use_operand_p op_p
)
2517 bool may_have_exposed_new_symbols
= false;
2519 tree op
= USE_FROM_PTR (op_p
);
2521 /* If the operand has a known constant value or it is known to be a
2522 copy of some other variable, use the value or copy stored in
2523 CONST_AND_COPIES. */
2524 val
= SSA_NAME_VALUE (op
);
2525 if (val
&& TREE_CODE (val
) != VALUE_HANDLE
)
2527 tree op_type
, val_type
;
2529 /* Do not change the base variable in the virtual operand
2530 tables. That would make it impossible to reconstruct
2531 the renamed virtual operand if we later modify this
2532 statement. Also only allow the new value to be an SSA_NAME
2533 for propagation into virtual operands. */
2534 if (!is_gimple_reg (op
)
2535 && (get_virtual_var (val
) != get_virtual_var (op
)
2536 || TREE_CODE (val
) != SSA_NAME
))
2539 /* Get the toplevel type of each operand. */
2540 op_type
= TREE_TYPE (op
);
2541 val_type
= TREE_TYPE (val
);
2543 /* While both types are pointers, get the type of the object
2545 while (POINTER_TYPE_P (op_type
) && POINTER_TYPE_P (val_type
))
2547 op_type
= TREE_TYPE (op_type
);
2548 val_type
= TREE_TYPE (val_type
);
2551 /* Make sure underlying types match before propagating a constant by
2552 converting the constant to the proper type. Note that convert may
2553 return a non-gimple expression, in which case we ignore this
2554 propagation opportunity. */
2555 if (TREE_CODE (val
) != SSA_NAME
)
2557 if (!lang_hooks
.types_compatible_p (op_type
, val_type
))
2559 val
= fold_convert (TREE_TYPE (op
), val
);
2560 if (!is_gimple_min_invariant (val
))
2565 /* Certain operands are not allowed to be copy propagated due
2566 to their interaction with exception handling and some GCC
2568 else if (!may_propagate_copy (op
, val
))
2572 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2574 fprintf (dump_file
, " Replaced '");
2575 print_generic_expr (dump_file
, op
, dump_flags
);
2576 fprintf (dump_file
, "' with %s '",
2577 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
2578 print_generic_expr (dump_file
, val
, dump_flags
);
2579 fprintf (dump_file
, "'\n");
2582 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2583 that we may have exposed a new symbol for SSA renaming. */
2584 if (TREE_CODE (val
) == ADDR_EXPR
2585 || (POINTER_TYPE_P (TREE_TYPE (op
))
2586 && is_gimple_min_invariant (val
)))
2587 may_have_exposed_new_symbols
= true;
2589 propagate_value (op_p
, val
);
2591 /* And note that we modified this statement. This is now
2592 safe, even if we changed virtual operands since we will
2593 rescan the statement and rewrite its operands again. */
2596 return may_have_exposed_new_symbols
;
2599 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2600 known value for that SSA_NAME (or NULL if no value is known).
2602 Propagate values from CONST_AND_COPIES into the uses, vuses and
2603 v_may_def_ops of STMT. */
2606 cprop_into_stmt (tree stmt
)
2608 bool may_have_exposed_new_symbols
= false;
2613 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_ALL_USES
)
2615 if (TREE_CODE (USE_FROM_PTR (op_p
)) == SSA_NAME
)
2616 may_have_exposed_new_symbols
|= cprop_operand (stmt
, op_p
);
2619 if (may_have_exposed_new_symbols
)
2621 rhs
= get_rhs (stmt
);
2622 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
2623 recompute_tree_invarant_for_addr_expr (rhs
);
2626 return may_have_exposed_new_symbols
;
2630 /* Optimize the statement pointed by iterator SI.
2632 We try to perform some simplistic global redundancy elimination and
2633 constant propagation:
2635 1- To detect global redundancy, we keep track of expressions that have
2636 been computed in this block and its dominators. If we find that the
2637 same expression is computed more than once, we eliminate repeated
2638 computations by using the target of the first one.
2640 2- Constant values and copy assignments. This is used to do very
2641 simplistic constant and copy propagation. When a constant or copy
2642 assignment is found, we map the value on the RHS of the assignment to
2643 the variable in the LHS in the CONST_AND_COPIES table. */
2646 optimize_stmt (struct dom_walk_data
*walk_data
, basic_block bb
,
2647 block_stmt_iterator si
)
2651 bool may_optimize_p
;
2652 bool may_have_exposed_new_symbols
= false;
2654 stmt
= bsi_stmt (si
);
2656 get_stmt_operands (stmt
);
2657 ann
= stmt_ann (stmt
);
2658 opt_stats
.num_stmts
++;
2659 may_have_exposed_new_symbols
= false;
2661 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2663 fprintf (dump_file
, "Optimizing statement ");
2664 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
2667 /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
2668 may_have_exposed_new_symbols
= cprop_into_stmt (stmt
);
2670 /* If the statement has been modified with constant replacements,
2671 fold its RHS before checking for redundant computations. */
2674 /* Try to fold the statement making sure that STMT is kept
2676 if (fold_stmt (bsi_stmt_ptr (si
)))
2678 stmt
= bsi_stmt (si
);
2679 ann
= stmt_ann (stmt
);
2681 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2683 fprintf (dump_file
, " Folded to: ");
2684 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
2688 /* Constant/copy propagation above may change the set of
2689 virtual operands associated with this statement. Folding
2690 may remove the need for some virtual operands.
2692 Indicate we will need to rescan and rewrite the statement. */
2693 may_have_exposed_new_symbols
= true;
2696 /* Check for redundant computations. Do this optimization only
2697 for assignments that have no volatile ops and conditionals. */
2698 may_optimize_p
= (!ann
->has_volatile_ops
2699 && ((TREE_CODE (stmt
) == RETURN_EXPR
2700 && TREE_OPERAND (stmt
, 0)
2701 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
2702 && ! (TREE_SIDE_EFFECTS
2703 (TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1))))
2704 || (TREE_CODE (stmt
) == MODIFY_EXPR
2705 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt
, 1)))
2706 || TREE_CODE (stmt
) == COND_EXPR
2707 || TREE_CODE (stmt
) == SWITCH_EXPR
));
2710 may_have_exposed_new_symbols
2711 |= eliminate_redundant_computations (walk_data
, stmt
, ann
);
2713 /* Record any additional equivalences created by this statement. */
2714 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2715 record_equivalences_from_stmt (stmt
,
2719 register_definitions_for_stmt (stmt
);
2721 /* If STMT is a COND_EXPR and it was modified, then we may know
2722 where it goes. If that is the case, then mark the CFG as altered.
2724 This will cause us to later call remove_unreachable_blocks and
2725 cleanup_tree_cfg when it is safe to do so. It is not safe to
2726 clean things up here since removal of edges and such can trigger
2727 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2730 That's all fine and good, except that once SSA_NAMEs are released
2731 to the manager, we must not call create_ssa_name until all references
2732 to released SSA_NAMEs have been eliminated.
2734 All references to the deleted SSA_NAMEs can not be eliminated until
2735 we remove unreachable blocks.
2737 We can not remove unreachable blocks until after we have completed
2738 any queued jump threading.
2740 We can not complete any queued jump threads until we have taken
2741 appropriate variables out of SSA form. Taking variables out of
2742 SSA form can call create_ssa_name and thus we lose.
2744 Ultimately I suspect we're going to need to change the interface
2745 into the SSA_NAME manager. */
2751 if (TREE_CODE (stmt
) == COND_EXPR
)
2752 val
= COND_EXPR_COND (stmt
);
2753 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2754 val
= SWITCH_COND (stmt
);
2756 if (val
&& TREE_CODE (val
) == INTEGER_CST
&& find_taken_edge (bb
, val
))
2759 /* If we simplified a statement in such a way as to be shown that it
2760 cannot trap, update the eh information and the cfg to match. */
2761 if (maybe_clean_eh_stmt (stmt
))
2763 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2764 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2765 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2769 if (may_have_exposed_new_symbols
)
2770 VARRAY_PUSH_TREE (stmts_to_rescan
, bsi_stmt (si
));
2773 /* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
2774 available expression hashtable, then return the LHS from the hash
2777 If INSERT is true, then we also update the available expression
2778 hash table to account for the changes made to STMT. */
2781 update_rhs_and_lookup_avail_expr (tree stmt
, tree new_rhs
, bool insert
)
2783 tree cached_lhs
= NULL
;
2785 /* Remove the old entry from the hash table. */
2788 struct expr_hash_elt element
;
2790 initialize_hash_element (stmt
, NULL
, &element
);
2791 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
2794 /* Now update the RHS of the assignment. */
2795 TREE_OPERAND (stmt
, 1) = new_rhs
;
2797 /* Now lookup the updated statement in the hash table. */
2798 cached_lhs
= lookup_avail_expr (stmt
, insert
);
2800 /* We have now called lookup_avail_expr twice with two different
2801 versions of this same statement, once in optimize_stmt, once here.
2803 We know the call in optimize_stmt did not find an existing entry
2804 in the hash table, so a new entry was created. At the same time
2805 this statement was pushed onto the BLOCK_AVAIL_EXPRS varray.
2807 If this call failed to find an existing entry on the hash table,
2808 then the new version of this statement was entered into the
2809 hash table. And this statement was pushed onto BLOCK_AVAIL_EXPR
2810 for the second time. So there are two copies on BLOCK_AVAIL_EXPRs
2812 If this call succeeded, we still have one copy of this statement
2813 on the BLOCK_AVAIL_EXPRs varray.
2815 For both cases, we need to pop the most recent entry off the
2816 BLOCK_AVAIL_EXPRs varray. For the case where we never found this
2817 statement in the hash tables, that will leave precisely one
2818 copy of this statement on BLOCK_AVAIL_EXPRs. For the case where
2819 we found a copy of this statement in the second hash table lookup
2820 we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs. */
2822 VARRAY_POP (avail_exprs_stack
);
2824 /* And make sure we record the fact that we modified this
2831 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
2832 found, return its LHS. Otherwise insert STMT in the table and return
2835 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
2836 is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
2837 can be removed when we finish processing this block and its children.
2839 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
2840 contains no CALL_EXPR on its RHS and makes no volatile nor
2841 aliased references. */
2844 lookup_avail_expr (tree stmt
, bool insert
)
2849 struct expr_hash_elt
*element
= xcalloc (sizeof (struct expr_hash_elt
), 1);
2851 lhs
= TREE_CODE (stmt
) == MODIFY_EXPR
? TREE_OPERAND (stmt
, 0) : NULL
;
2853 initialize_hash_element (stmt
, lhs
, element
);
2855 /* Don't bother remembering constant assignments and copy operations.
2856 Constants and copy operations are handled by the constant/copy propagator
2857 in optimize_stmt. */
2858 if (TREE_CODE (element
->rhs
) == SSA_NAME
2859 || is_gimple_min_invariant (element
->rhs
))
2865 /* If this is an equality test against zero, see if we have recorded a
2866 nonzero value for the variable in question. */
2867 if ((TREE_CODE (element
->rhs
) == EQ_EXPR
2868 || TREE_CODE (element
->rhs
) == NE_EXPR
)
2869 && TREE_CODE (TREE_OPERAND (element
->rhs
, 0)) == SSA_NAME
2870 && integer_zerop (TREE_OPERAND (element
->rhs
, 1)))
2872 int indx
= SSA_NAME_VERSION (TREE_OPERAND (element
->rhs
, 0));
2874 if (bitmap_bit_p (nonzero_vars
, indx
))
2876 tree t
= element
->rhs
;
2879 if (TREE_CODE (t
) == EQ_EXPR
)
2880 return boolean_false_node
;
2882 return boolean_true_node
;
2886 /* Finally try to find the expression in the main expression hash table. */
2887 slot
= htab_find_slot_with_hash (avail_exprs
, element
, element
->hash
,
2888 (insert
? INSERT
: NO_INSERT
));
2897 *slot
= (void *) element
;
2898 VARRAY_PUSH_TREE (avail_exprs_stack
, stmt
? stmt
: element
->rhs
);
2902 /* Extract the LHS of the assignment so that it can be used as the current
2903 definition of another variable. */
2904 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
2906 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2907 use the value from the const_and_copies table. */
2908 if (TREE_CODE (lhs
) == SSA_NAME
)
2910 temp
= SSA_NAME_VALUE (lhs
);
2911 if (temp
&& TREE_CODE (temp
) != VALUE_HANDLE
)
2919 /* Given a condition COND, record into HI_P, LO_P and INVERTED_P the
2920 range of values that result in the conditional having a true value.
2922 Return true if we are successful in extracting a range from COND and
2923 false if we are unsuccessful. */
2926 extract_range_from_cond (tree cond
, tree
*hi_p
, tree
*lo_p
, int *inverted_p
)
2928 tree op1
= TREE_OPERAND (cond
, 1);
2929 tree high
, low
, type
;
2932 /* Experiments have shown that it's rarely, if ever useful to
2933 record ranges for enumerations. Presumably this is due to
2934 the fact that they're rarely used directly. They are typically
2935 cast into an integer type and used that way. */
2936 if (TREE_CODE (TREE_TYPE (op1
)) != INTEGER_TYPE
)
2939 type
= TREE_TYPE (op1
);
2941 switch (TREE_CODE (cond
))
2955 high
= TYPE_MAX_VALUE (type
);
2960 low
= int_const_binop (PLUS_EXPR
, op1
, integer_one_node
, 1);
2961 high
= TYPE_MAX_VALUE (type
);
2967 low
= TYPE_MIN_VALUE (type
);
2972 high
= int_const_binop (MINUS_EXPR
, op1
, integer_one_node
, 1);
2973 low
= TYPE_MIN_VALUE (type
);
2983 *inverted_p
= inverted
;
2987 /* Record a range created by COND for basic block BB. */
2990 record_range (tree cond
, basic_block bb
)
2992 /* We explicitly ignore NE_EXPRs. They rarely allow for meaningful
2993 range optimizations and significantly complicate the implementation. */
2994 if (COMPARISON_CLASS_P (cond
)
2995 && TREE_CODE (cond
) != NE_EXPR
2996 && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond
, 1))) == INTEGER_TYPE
)
2998 struct vrp_hash_elt
*vrp_hash_elt
;
2999 struct vrp_element
*element
;
3000 varray_type
*vrp_records_p
;
3004 vrp_hash_elt
= xmalloc (sizeof (struct vrp_hash_elt
));
3005 vrp_hash_elt
->var
= TREE_OPERAND (cond
, 0);
3006 vrp_hash_elt
->records
= NULL
;
3007 slot
= htab_find_slot (vrp_data
, vrp_hash_elt
, INSERT
);
3010 *slot
= (void *) vrp_hash_elt
;
3012 vrp_hash_elt
= (struct vrp_hash_elt
*) *slot
;
3013 vrp_records_p
= &vrp_hash_elt
->records
;
3015 element
= ggc_alloc (sizeof (struct vrp_element
));
3016 element
->low
= NULL
;
3017 element
->high
= NULL
;
3018 element
->cond
= cond
;
3021 if (*vrp_records_p
== NULL
)
3022 VARRAY_GENERIC_PTR_INIT (*vrp_records_p
, 2, "vrp records");
3024 VARRAY_PUSH_GENERIC_PTR (*vrp_records_p
, element
);
3025 VARRAY_PUSH_TREE (vrp_variables_stack
, TREE_OPERAND (cond
, 0));
3029 /* Given a conditional statement IF_STMT, return the assignment 'X = Y'
3030 known to be true depending on which arm of IF_STMT is taken.
3032 Not all conditional statements will result in a useful assignment.
3033 Return NULL_TREE in that case.
3035 Also enter into the available expression table statements of
3042 This allows us to lookup the condition in a dominated block and
3043 get back a constant indicating if the condition is true. */
3045 static struct eq_expr_value
3046 get_eq_expr_value (tree if_stmt
,
3051 struct eq_expr_value retval
;
3053 cond
= COND_EXPR_COND (if_stmt
);
3057 /* If the conditional is a single variable 'X', return 'X = 1' for
3058 the true arm and 'X = 0' on the false arm. */
3059 if (TREE_CODE (cond
) == SSA_NAME
)
3062 retval
.src
= constant_boolean_node (true_arm
, TREE_TYPE (cond
));
3066 /* If we have a comparison expression, then record its result into
3067 the available expression table. */
3068 if (COMPARISON_CLASS_P (cond
))
3070 tree op0
= TREE_OPERAND (cond
, 0);
3071 tree op1
= TREE_OPERAND (cond
, 1);
3073 /* Special case comparing booleans against a constant as we know
3074 the value of OP0 on both arms of the branch. i.e., we can record
3075 an equivalence for OP0 rather than COND. */
3076 if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
3077 && TREE_CODE (op0
) == SSA_NAME
3078 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
3079 && is_gimple_min_invariant (op1
))
3081 if ((TREE_CODE (cond
) == EQ_EXPR
&& true_arm
)
3082 || (TREE_CODE (cond
) == NE_EXPR
&& ! true_arm
))
3088 if (integer_zerop (op1
))
3089 retval
.src
= boolean_true_node
;
3091 retval
.src
= boolean_false_node
;
3097 if (TREE_CODE (op0
) == SSA_NAME
3098 && (is_gimple_min_invariant (op1
) || TREE_CODE (op1
) == SSA_NAME
))
3100 tree inverted
= invert_truthvalue (cond
);
3102 /* When we find an available expression in the hash table, we replace
3103 the expression with the LHS of the statement in the hash table.
3105 So, we want to build statements such as "1 = <condition>" on the
3106 true arm and "0 = <condition>" on the false arm. That way if we
3107 find the expression in the table, we will replace it with its
3108 known constant value. Also insert inversions of the result and
3109 condition into the hash table. */
3112 record_cond (cond
, boolean_true_node
);
3113 record_dominating_conditions (cond
);
3114 record_cond (inverted
, boolean_false_node
);
3116 if (TREE_CONSTANT (op1
))
3117 record_range (cond
, bb
);
3119 /* If the conditional is of the form 'X == Y', return 'X = Y'
3120 for the true arm. */
3121 if (TREE_CODE (cond
) == EQ_EXPR
)
3131 record_cond (inverted
, boolean_true_node
);
3132 record_dominating_conditions (inverted
);
3133 record_cond (cond
, boolean_false_node
);
3135 if (TREE_CONSTANT (op1
))
3136 record_range (inverted
, bb
);
3138 /* If the conditional is of the form 'X != Y', return 'X = Y'
3139 for the false arm. */
3140 if (TREE_CODE (cond
) == NE_EXPR
)
3153 /* Hashing and equality functions for VRP_DATA.
3155 Since this hash table is addressed by SSA_NAMEs, we can hash on
3156 their version number and equality can be determined with a
3157 pointer comparison. */
3160 vrp_hash (const void *p
)
3162 tree var
= ((struct vrp_hash_elt
*)p
)->var
;
3164 return SSA_NAME_VERSION (var
);
3168 vrp_eq (const void *p1
, const void *p2
)
3170 tree var1
= ((struct vrp_hash_elt
*)p1
)->var
;
3171 tree var2
= ((struct vrp_hash_elt
*)p2
)->var
;
3173 return var1
== var2
;
3176 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
3177 MODIFY_EXPR statements. We compute a value number for expressions using
3178 the code of the expression and the SSA numbers of its operands. */
3181 avail_expr_hash (const void *p
)
3183 stmt_ann_t ann
= ((struct expr_hash_elt
*)p
)->ann
;
3184 tree rhs
= ((struct expr_hash_elt
*)p
)->rhs
;
3189 /* iterative_hash_expr knows how to deal with any expression and
3190 deals with commutative operators as well, so just use it instead
3191 of duplicating such complexities here. */
3192 val
= iterative_hash_expr (rhs
, val
);
3194 /* If the hash table entry is not associated with a statement, then we
3195 can just hash the expression and not worry about virtual operands
3200 /* Add the SSA version numbers of every vuse operand. This is important
3201 because compound variables like arrays are not renamed in the
3202 operands. Rather, the rename is done on the virtual variable
3203 representing all the elements of the array. */
3204 vuses
= VUSE_OPS (ann
);
3205 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
3206 val
= iterative_hash_expr (VUSE_OP (vuses
, i
), val
);
3212 real_avail_expr_hash (const void *p
)
3214 return ((const struct expr_hash_elt
*)p
)->hash
;
3218 avail_expr_eq (const void *p1
, const void *p2
)
3220 stmt_ann_t ann1
= ((struct expr_hash_elt
*)p1
)->ann
;
3221 tree rhs1
= ((struct expr_hash_elt
*)p1
)->rhs
;
3222 stmt_ann_t ann2
= ((struct expr_hash_elt
*)p2
)->ann
;
3223 tree rhs2
= ((struct expr_hash_elt
*)p2
)->rhs
;
3225 /* If they are the same physical expression, return true. */
3226 if (rhs1
== rhs2
&& ann1
== ann2
)
3229 /* If their codes are not equal, then quit now. */
3230 if (TREE_CODE (rhs1
) != TREE_CODE (rhs2
))
3233 /* In case of a collision, both RHS have to be identical and have the
3234 same VUSE operands. */
3235 if ((TREE_TYPE (rhs1
) == TREE_TYPE (rhs2
)
3236 || lang_hooks
.types_compatible_p (TREE_TYPE (rhs1
), TREE_TYPE (rhs2
)))
3237 && operand_equal_p (rhs1
, rhs2
, OEP_PURE_SAME
))
3239 vuse_optype ops1
= NULL
;
3240 vuse_optype ops2
= NULL
;
3241 size_t num_ops1
= 0;
3242 size_t num_ops2
= 0;
3247 ops1
= VUSE_OPS (ann1
);
3248 num_ops1
= NUM_VUSES (ops1
);
3253 ops2
= VUSE_OPS (ann2
);
3254 num_ops2
= NUM_VUSES (ops2
);
3257 /* If the number of virtual uses is different, then we consider
3259 if (num_ops1
!= num_ops2
)
3262 for (i
= 0; i
< num_ops1
; i
++)
3263 if (VUSE_OP (ops1
, i
) != VUSE_OP (ops2
, i
))
3266 gcc_assert (((struct expr_hash_elt
*)p1
)->hash
3267 == ((struct expr_hash_elt
*)p2
)->hash
);
3274 /* Given STMT and a pointer to the block local definitions BLOCK_DEFS_P,
3275 register register all objects set by this statement into BLOCK_DEFS_P
3279 register_definitions_for_stmt (tree stmt
)
3284 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
3287 /* FIXME: We shouldn't be registering new defs if the variable
3288 doesn't need to be renamed. */
3289 register_new_def (def
, &block_defs_stack
);