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 "langhooks.h"
45 /* This file implements optimizations on the dominator tree. */
47 /* Hash table with expressions made available during the renaming process.
48 When an assignment of the form X_i = EXPR is found, the statement is
49 stored in this table. If the same expression EXPR is later found on the
50 RHS of another statement, it is replaced with X_i (thus performing
51 global redundancy elimination). Similarly as we pass through conditionals
52 we record the conditional itself as having either a true or false value
54 static htab_t avail_exprs
;
56 /* Structure for entries in the expression hash table.
58 This requires more memory for the hash table entries, but allows us
59 to avoid creating silly tree nodes and annotations for conditionals,
60 eliminates 2 global hash tables and two block local varrays.
62 It also allows us to reduce the number of hash table lookups we
63 have to perform in lookup_avail_expr and finally it allows us to
64 significantly reduce the number of calls into the hashing routine
68 /* The value (lhs) of this expression. */
71 /* The expression (rhs) we want to record. */
74 /* The annotation if this element corresponds to a statement. */
77 /* The hash value for RHS/ann. */
81 /* Table of constant values and copies indexed by SSA name. When the
82 renaming pass finds an assignment of a constant (X_i = C) or a copy
83 assignment from another SSA variable (X_i = Y_j), it creates a mapping
84 between X_i and the RHS in this table. This mapping is used later on,
85 when renaming uses of X_i. If an assignment to X_i is found in this
86 table, instead of using X_i, we use the RHS of the statement stored in
87 this table (thus performing very simplistic copy and constant
89 static varray_type const_and_copies
;
91 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
92 know their exact value. */
93 static bitmap nonzero_vars
;
95 /* Track whether or not we have changed the control flow graph. */
96 static bool cfg_altered
;
98 /* Bitmap of blocks that have had EH statements cleaned. We should
99 remove their dead edges eventually. */
100 static bitmap need_eh_cleanup
;
102 /* Statistics for dominator optimizations. */
106 long num_exprs_considered
;
110 /* Value range propagation record. Each time we encounter a conditional
111 of the form SSA_NAME COND CONST we create a new vrp_element to record
112 how the condition affects the possible values SSA_NAME may have.
114 Each record contains the condition tested (COND), and the the range of
115 values the variable may legitimately have if COND is true. Note the
116 range of values may be a smaller range than COND specifies if we have
117 recorded other ranges for this variable. Each record also contains the
118 block in which the range was recorded for invalidation purposes.
120 Note that the current known range is computed lazily. This allows us
121 to avoid the overhead of computing ranges which are never queried.
123 When we encounter a conditional, we look for records which constrain
124 the SSA_NAME used in the condition. In some cases those records allow
125 us to determine the condition's result at compile time. In other cases
126 they may allow us to simplify the condition.
128 We also use value ranges to do things like transform signed div/mod
129 operations into unsigned div/mod or to simplify ABS_EXPRs.
131 Simple experiments have shown these optimizations to not be all that
132 useful on switch statements (much to my surprise). So switch statement
133 optimizations are not performed.
135 Note carefully we do not propagate information through each statement
136 in the block. ie, if we know variable X has a value defined of
137 [0, 25] and we encounter Y = X + 1, we do not track a value range
138 for Y (which would be [1, 26] if we cared). Similarly we do not
139 constrain values as we encounter narrowing typecasts, etc. */
143 /* The highest and lowest values the variable in COND may contain when
144 COND is true. Note this may not necessarily be the same values
145 tested by COND if the same variable was used in earlier conditionals.
147 Note this is computed lazily and thus can be NULL indicating that
148 the values have not been computed yet. */
152 /* The actual conditional we recorded. This is needed since we compute
156 /* The basic block where this record was created. We use this to determine
157 when to remove records. */
161 static struct opt_stats_d opt_stats
;
163 /* This virtual array holds pairs of edges which describe a scheduled
164 edge redirection from jump threading.
166 The first entry in each pair is the edge we are going to redirect.
168 The second entry in each pair is the edge leading to our final
169 destination block. By providing this as an edge rather than the
170 final target block itself we can correctly handle redirections
171 when the target block had PHIs which required edge insertions/splitting
172 to remove the PHIs. */
173 static GTY(()) varray_type redirection_edges
;
175 /* A virtual array holding value range records for the variable identified
176 by the index, SSA_VERSION. */
177 static varray_type vrp_data
;
179 /* Datastructure for block local data used during the dominator walk.
180 We maintain a stack of these as we recursively walk down the
183 struct dom_walk_block_data
185 /* Array of all the expressions entered into the global expression
186 hash table by this block. During finalization we use this array to
187 know what expressions to remove from the global expression hash
189 varray_type avail_exprs
;
191 /* Array of dest, src pairs that need to be restored during finalization
192 into the global const/copies table during finalization. */
193 varray_type const_and_copies
;
195 /* Similarly for the nonzero state of variables that needs to be
196 restored during finalization. */
197 varray_type nonzero_vars
;
199 /* Array of statements we need to rescan during finalization for newly
200 exposed variables. */
201 varray_type stmts_to_rescan
;
203 /* Array of variables which have their values constrained by operations
204 in this basic block. We use this during finalization to know
205 which variables need their VRP data updated. */
206 varray_type vrp_variables
;
208 /* Array of tree pairs used to restore the global currdefs to its
209 original state after completing optimization of a block and its
210 dominator children. */
211 varray_type block_defs
;
220 /* Local functions. */
221 static void optimize_stmt (struct dom_walk_data
*,
223 block_stmt_iterator
);
224 static inline tree
get_value_for (tree
, varray_type table
);
225 static inline void set_value_for (tree
, tree
, varray_type table
);
226 static tree
lookup_avail_expr (tree
, varray_type
*, bool);
227 static struct eq_expr_value
get_eq_expr_value (tree
, int, varray_type
*,
228 basic_block
, varray_type
*);
229 static hashval_t
avail_expr_hash (const void *);
230 static hashval_t
real_avail_expr_hash (const void *);
231 static int avail_expr_eq (const void *, const void *);
232 static void htab_statistics (FILE *, htab_t
);
233 static void record_cond (tree
, tree
, varray_type
*);
234 static void record_dominating_conditions (tree
, varray_type
*);
235 static void record_const_or_copy (tree
, tree
, varray_type
*);
236 static void record_equality (tree
, tree
, varray_type
*);
237 static tree
update_rhs_and_lookup_avail_expr (tree
, tree
, varray_type
*,
239 static tree
simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*,
240 tree
, stmt_ann_t
, int);
241 static tree
simplify_cond_and_lookup_avail_expr (tree
, varray_type
*,
243 static tree
simplify_switch_and_lookup_avail_expr (tree
, varray_type
*,
245 static tree
find_equivalent_equality_comparison (tree
);
246 static void record_range (tree
, basic_block
, varray_type
*);
247 static bool extract_range_from_cond (tree
, tree
*, tree
*, int *);
248 static void record_equivalences_from_phis (struct dom_walk_data
*, basic_block
);
249 static void record_equivalences_from_incoming_edge (struct dom_walk_data
*,
251 static bool eliminate_redundant_computations (struct dom_walk_data
*,
253 static void record_equivalences_from_stmt (tree
, varray_type
*, varray_type
*,
255 static void thread_across_edge (struct dom_walk_data
*, edge
);
256 static void dom_opt_finalize_block (struct dom_walk_data
*, basic_block
);
257 static void dom_opt_initialize_block_local_data (struct dom_walk_data
*,
259 static void dom_opt_initialize_block (struct dom_walk_data
*, basic_block
);
260 static void cprop_into_phis (struct dom_walk_data
*, basic_block
);
261 static void remove_local_expressions_from_table (varray_type locals
,
264 static void restore_vars_to_original_value (varray_type locals
,
267 static void restore_currdefs_to_original_value (varray_type locals
,
269 static void register_definitions_for_stmt (stmt_ann_t
, varray_type
*);
270 static void redirect_edges_and_update_ssa_graph (varray_type
);
271 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
273 /* Local version of fold that doesn't introduce cruft. */
280 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
281 may have been added by fold, and "useless" type conversions that might
282 now be apparent due to propagation. */
283 STRIP_USELESS_TYPE_CONVERSION (t
);
288 /* Return the value associated with variable VAR in TABLE. */
291 get_value_for (tree var
, varray_type table
)
293 return VARRAY_TREE (table
, SSA_NAME_VERSION (var
));
296 /* Associate VALUE to variable VAR in TABLE. */
299 set_value_for (tree var
, tree value
, varray_type table
)
301 VARRAY_TREE (table
, SSA_NAME_VERSION (var
)) = value
;
304 /* REDIRECTION_EDGES contains edge pairs where we want to revector the
305 destination of the first edge to the destination of the second edge.
307 These redirections may significantly change the SSA graph since we
308 allow redirection through blocks with PHI nodes and blocks with
309 real instructions in some cases.
311 This routine will perform the requested redirections and incrementally
312 update the SSA graph.
314 Note in some cases requested redirections may be ignored as they can
315 not be safely implemented. */
318 redirect_edges_and_update_ssa_graph (varray_type redirection_edges
)
323 size_t old_num_referenced_vars
= num_referenced_vars
;
324 bitmap virtuals_to_rename
= BITMAP_XMALLOC ();
326 /* First note any variables which we are going to have to take
327 out of SSA form as well as any virtuals which need updating. */
328 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
330 block_stmt_iterator bsi
;
335 e
= VARRAY_EDGE (redirection_edges
, i
);
336 tgt
= VARRAY_EDGE (redirection_edges
, i
+ 1)->dest
;
338 /* All variables referenced in PHI nodes we bypass must be
340 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
342 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
344 if (is_gimple_reg (PHI_RESULT (phi
)))
345 bitmap_set_bit (vars_to_rename
, var_ann (result
)->uid
);
347 bitmap_set_bit (virtuals_to_rename
, var_ann (result
)->uid
);
350 /* Any variables set by statements at the start of the block we
351 are bypassing must also be taken our of SSA form. */
352 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
356 v_may_def_optype v_may_defs
;
357 v_must_def_optype v_must_defs
;
358 tree stmt
= bsi_stmt (bsi
);
359 stmt_ann_t ann
= stmt_ann (stmt
);
361 if (TREE_CODE (stmt
) == COND_EXPR
)
364 get_stmt_operands (stmt
);
366 defs
= DEF_OPS (ann
);
367 for (j
= 0; j
< NUM_DEFS (defs
); j
++)
369 tree op
= SSA_NAME_VAR (DEF_OP (defs
, j
));
370 bitmap_set_bit (vars_to_rename
, var_ann (op
)->uid
);
373 v_may_defs
= STMT_V_MAY_DEF_OPS (stmt
);
374 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
376 tree op
= V_MAY_DEF_RESULT (v_may_defs
, j
);
377 bitmap_set_bit (vars_to_rename
, var_ann (op
)->uid
);
380 v_must_defs
= STMT_V_MUST_DEF_OPS (stmt
);
381 for (j
= 0; j
< NUM_V_MUST_DEFS (v_must_defs
); j
++)
383 tree op
= V_MUST_DEF_OP (v_must_defs
, j
);
384 bitmap_set_bit (vars_to_rename
, var_ann (op
)->uid
);
388 /* Finally, any variables in PHI nodes at our final destination
389 must also be taken our of SSA form. */
390 for (phi
= phi_nodes (tgt
); phi
; phi
= PHI_CHAIN (phi
))
392 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
394 if (is_gimple_reg (PHI_RESULT (phi
)))
395 bitmap_set_bit (vars_to_rename
, var_ann (result
)->uid
);
397 bitmap_set_bit (virtuals_to_rename
, var_ann (result
)->uid
);
401 /* Take those selected variables out of SSA form. This must be
402 done before we start redirecting edges. */
403 if (bitmap_first_set_bit (vars_to_rename
) >= 0)
404 rewrite_vars_out_of_ssa (vars_to_rename
);
406 /* The out of SSA translation above may split the edge from
407 E->src to E->dest. This could potentially cause us to lose
408 an assignment leading to invalid warnings about uninitialized
409 variables or incorrect code.
411 Luckily, we can detect this by looking at the last statement
412 in E->dest. If it is not a COND_EXPR or SWITCH_EXPR, then
413 the edge was split and instead of E, we want E->dest->succ. */
414 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
416 edge e
= VARRAY_EDGE (redirection_edges
, i
);
417 tree last
= last_stmt (e
->dest
);
420 && TREE_CODE (last
) != COND_EXPR
421 && TREE_CODE (last
) != SWITCH_EXPR
)
425 #ifdef ENABLE_CHECKING
426 /* There should only be a single successor if the
427 original edge was split. */
431 /* Replace the edge in REDIRECTION_EDGES for the
433 VARRAY_EDGE (redirection_edges
, i
) = e
;
437 /* If we created any new variables as part of the out-of-ssa
438 translation, then any jump threads must be invalidated if they
439 bypass a block in which we skipped instructions.
441 This is necessary as instructions which appeared to be NOPS
442 may be necessary after the out-of-ssa translation. */
443 if (num_referenced_vars
!= old_num_referenced_vars
)
445 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
447 block_stmt_iterator bsi
;
450 e
= VARRAY_EDGE (redirection_edges
, i
);
451 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
453 tree stmt
= bsi_stmt (bsi
);
455 if (IS_EMPTY_STMT (stmt
)
456 || TREE_CODE (stmt
) == LABEL_EXPR
)
459 if (TREE_CODE (stmt
) == COND_EXPR
)
462 /* Invalidate the jump thread. */
463 VARRAY_EDGE (redirection_edges
, i
) = NULL
;
464 VARRAY_EDGE (redirection_edges
, i
+ 1) = NULL
;
470 /* Now redirect the edges. */
471 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
476 e
= VARRAY_EDGE (redirection_edges
, i
);
480 tgt
= VARRAY_EDGE (redirection_edges
, i
+ 1)->dest
;
483 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
484 fprintf (dump_file
, " Threaded jump %d --> %d to %d\n",
485 e
->src
->index
, e
->dest
->index
, tgt
->index
);
489 e
= redirect_edge_and_branch (e
, tgt
);
490 PENDING_STMT (e
) = NULL_TREE
;
492 /* Updating the dominance information would be nontrivial. */
493 free_dominance_info (CDI_DOMINATORS
);
495 if ((dump_file
&& (dump_flags
& TDF_DETAILS
))
497 fprintf (dump_file
, " basic block %d created\n",
503 VARRAY_CLEAR (redirection_edges
);
505 for (i
= old_num_referenced_vars
; i
< num_referenced_vars
; i
++)
507 bitmap_set_bit (vars_to_rename
, i
);
508 var_ann (referenced_var (i
))->out_of_ssa_tag
= 0;
511 bitmap_a_or_b (vars_to_rename
, vars_to_rename
, virtuals_to_rename
);
513 /* We must remove any PHIs for virtual variables that we are going to
514 re-rename. Hopefully we'll be able to simply update these incrementally
520 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
522 tree result
= PHI_RESULT (phi
);
524 next
= PHI_CHAIN (phi
);
526 if (bitmap_bit_p (virtuals_to_rename
,
527 var_ann (SSA_NAME_VAR (result
))->uid
))
528 remove_phi_node (phi
, NULL
, bb
);
531 BITMAP_XFREE (virtuals_to_rename
);
534 /* Jump threading, redundancy elimination and const/copy propagation.
536 This pass may expose new symbols that need to be renamed into SSA. For
537 every new symbol exposed, its corresponding bit will be set in
541 tree_ssa_dominator_optimize (void)
544 struct dom_walk_data walk_data
;
547 for (i
= 0; i
< num_referenced_vars
; i
++)
548 var_ann (referenced_var (i
))->current_def
= NULL
;
550 /* Mark loop edges so we avoid threading across loop boundaries.
551 This may result in transforming natural loop into irreducible
553 mark_dfs_back_edges ();
555 /* Create our hash tables. */
556 avail_exprs
= htab_create (1024, real_avail_expr_hash
, avail_expr_eq
, free
);
557 VARRAY_TREE_INIT (const_and_copies
, num_ssa_names
, "const_and_copies");
558 nonzero_vars
= BITMAP_XMALLOC ();
559 VARRAY_EDGE_INIT (redirection_edges
, 20, "redirection_edges");
560 VARRAY_GENERIC_PTR_INIT (vrp_data
, num_ssa_names
, "vrp_data");
561 need_eh_cleanup
= BITMAP_XMALLOC ();
563 /* Setup callbacks for the generic dominator tree walker. */
564 walk_data
.walk_stmts_backward
= false;
565 walk_data
.dom_direction
= CDI_DOMINATORS
;
566 walk_data
.initialize_block_local_data
= dom_opt_initialize_block_local_data
;
567 walk_data
.before_dom_children_before_stmts
= dom_opt_initialize_block
;
568 walk_data
.before_dom_children_walk_stmts
= optimize_stmt
;
569 walk_data
.before_dom_children_after_stmts
= cprop_into_phis
;
570 walk_data
.after_dom_children_before_stmts
= NULL
;
571 walk_data
.after_dom_children_walk_stmts
= NULL
;
572 walk_data
.after_dom_children_after_stmts
= dom_opt_finalize_block
;
573 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
574 When we attach more stuff we'll need to fill this out with a real
576 walk_data
.global_data
= NULL
;
577 walk_data
.block_local_data_size
= sizeof (struct dom_walk_block_data
);
579 /* Now initialize the dominator walker. */
580 init_walk_dominator_tree (&walk_data
);
582 /* Reset block_forwardable in each block's annotation. We use that
583 attribute when threading through COND_EXPRs. */
585 bb_ann (bb
)->forwardable
= 1;
587 calculate_dominance_info (CDI_DOMINATORS
);
589 /* If we prove certain blocks are unreachable, then we want to
590 repeat the dominator optimization process as PHI nodes may
591 have turned into copies which allows better propagation of
592 values. So we repeat until we do not identify any new unreachable
596 /* Optimize the dominator tree. */
599 /* Recursively walk the dominator tree optimizing statements. */
600 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
602 /* Wipe the hash tables. */
604 if (VARRAY_ACTIVE_SIZE (redirection_edges
) > 0)
605 redirect_edges_and_update_ssa_graph (redirection_edges
);
607 if (bitmap_first_set_bit (need_eh_cleanup
) >= 0)
609 cfg_altered
= tree_purge_all_dead_eh_edges (need_eh_cleanup
);
610 bitmap_zero (need_eh_cleanup
);
613 /* We may have made some basic blocks unreachable, remove them. */
614 cfg_altered
|= delete_unreachable_blocks ();
616 /* If the CFG was altered, then recompute the dominator tree. This
617 is not strictly needed if we only removed unreachable blocks, but
618 may produce better results. If we threaded jumps, then rebuilding
619 the dominator tree is strictly necessary. Likewise with EH cleanup.
620 Free the dominance info first so that cleanup_tree_cfg doesn't try
624 free_dominance_info (CDI_DOMINATORS
);
626 calculate_dominance_info (CDI_DOMINATORS
);
629 /* If we are going to iterate (CFG_ALTERED is true), then we must
630 perform any queued renaming before the next iteration. */
632 && bitmap_first_set_bit (vars_to_rename
) >= 0)
634 rewrite_into_ssa (false);
635 bitmap_clear (vars_to_rename
);
637 /* The into SSA translation may have created new SSA_NAMES whic
638 affect the size of CONST_AND_COPIES and VRP_DATA. */
639 VARRAY_GROW (const_and_copies
, num_ssa_names
);
640 VARRAY_GROW (vrp_data
, num_ssa_names
);
643 /* Reinitialize the various tables. */
644 bitmap_clear (nonzero_vars
);
645 htab_empty (avail_exprs
);
646 VARRAY_CLEAR (const_and_copies
);
647 VARRAY_CLEAR (vrp_data
);
649 for (i
= 0; i
< num_referenced_vars
; i
++)
650 var_ann (referenced_var (i
))->current_def
= NULL
;
654 /* Remove any unreachable blocks left behind and linearize the CFG. */
657 /* Debugging dumps. */
658 if (dump_file
&& (dump_flags
& TDF_STATS
))
659 dump_dominator_optimization_stats (dump_file
);
661 /* We emptied the hash table earlier, now delete it completely. */
662 htab_delete (avail_exprs
);
664 /* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
665 CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
666 of the do-while loop above. */
668 /* And finalize the dominator walker. */
669 fini_walk_dominator_tree (&walk_data
);
671 /* Free nonzero_vars. */
672 BITMAP_XFREE (nonzero_vars
);
673 BITMAP_XFREE (need_eh_cleanup
);
677 gate_dominator (void)
679 return flag_tree_dom
!= 0;
682 struct tree_opt_pass pass_dominator
=
685 gate_dominator
, /* gate */
686 tree_ssa_dominator_optimize
, /* execute */
689 0, /* static_pass_number */
690 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
691 PROP_cfg
| PROP_ssa
, /* properties_required */
692 0, /* properties_provided */
693 0, /* properties_destroyed */
694 0, /* todo_flags_start */
695 TODO_dump_func
| TODO_rename_vars
696 | TODO_verify_ssa
/* todo_flags_finish */
700 /* We are exiting BB, see if the target block begins with a conditional
701 jump which has a known value when reached via BB. */
704 thread_across_edge (struct dom_walk_data
*walk_data
, edge e
)
706 struct dom_walk_block_data
*bd
707 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
708 block_stmt_iterator bsi
;
712 /* Each PHI creates a temporary equivalence, record them. */
713 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
715 tree src
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
716 tree dst
= PHI_RESULT (phi
);
717 record_const_or_copy (dst
, src
, &bd
->const_and_copies
);
718 register_new_def (dst
, &bd
->block_defs
);
721 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
723 tree lhs
, cached_lhs
;
725 stmt
= bsi_stmt (bsi
);
727 /* Ignore empty statements and labels. */
728 if (IS_EMPTY_STMT (stmt
) || TREE_CODE (stmt
) == LABEL_EXPR
)
731 /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
732 value, then stop our search here. Ideally when we stop a
733 search we stop on a COND_EXPR or SWITCH_EXPR. */
734 if (TREE_CODE (stmt
) != MODIFY_EXPR
735 || TREE_CODE (TREE_OPERAND (stmt
, 0)) != SSA_NAME
)
738 /* At this point we have a statement which assigns an RHS to an
739 SSA_VAR on the LHS. We want to prove that the RHS is already
740 available and that its value is held in the current definition
741 of the LHS -- meaning that this assignment is a NOP when
742 reached via edge E. */
743 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
)
744 cached_lhs
= TREE_OPERAND (stmt
, 1);
746 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
748 lhs
= TREE_OPERAND (stmt
, 0);
750 /* This can happen if we thread around to the start of a loop. */
751 if (lhs
== cached_lhs
)
754 /* If we did not find RHS in the hash table, then try again after
755 temporarily const/copy propagating the operands. */
758 /* Copy the operands. */
759 stmt_ann_t ann
= stmt_ann (stmt
);
760 use_optype uses
= USE_OPS (ann
);
761 vuse_optype vuses
= VUSE_OPS (ann
);
762 tree
*uses_copy
= xcalloc (NUM_USES (uses
), sizeof (tree
));
763 tree
*vuses_copy
= xcalloc (NUM_VUSES (vuses
), sizeof (tree
));
766 /* Make a copy of the uses into USES_COPY, then cprop into
768 for (i
= 0; i
< NUM_USES (uses
); i
++)
772 uses_copy
[i
] = USE_OP (uses
, i
);
773 if (TREE_CODE (USE_OP (uses
, i
)) == SSA_NAME
)
774 tmp
= get_value_for (USE_OP (uses
, i
), const_and_copies
);
776 SET_USE_OP (uses
, i
, tmp
);
779 /* Similarly for virtual uses. */
780 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
784 vuses_copy
[i
] = VUSE_OP (vuses
, i
);
785 if (TREE_CODE (VUSE_OP (vuses
, i
)) == SSA_NAME
)
786 tmp
= get_value_for (VUSE_OP (vuses
, i
), const_and_copies
);
788 SET_VUSE_OP (vuses
, i
, tmp
);
791 /* Try to lookup the new expression. */
792 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
794 /* Restore the statement's original uses/defs. */
795 for (i
= 0; i
< NUM_USES (uses
); i
++)
796 SET_USE_OP (uses
, i
, uses_copy
[i
]);
798 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
799 SET_VUSE_OP (vuses
, i
, vuses_copy
[i
]);
804 /* If we still did not find the expression in the hash table,
805 then we can not ignore this statement. */
810 /* If the expression in the hash table was not assigned to an
811 SSA_NAME, then we can not ignore this statement. */
812 if (TREE_CODE (cached_lhs
) != SSA_NAME
)
815 /* If we have different underlying variables, then we can not
816 ignore this statement. */
817 if (SSA_NAME_VAR (cached_lhs
) != SSA_NAME_VAR (lhs
))
820 /* If CACHED_LHS does not represent the current value of the undering
821 variable in CACHED_LHS/LHS, then we can not ignore this statement. */
822 if (var_ann (SSA_NAME_VAR (lhs
))->current_def
!= cached_lhs
)
825 /* If we got here, then we can ignore this statement and continue
826 walking through the statements in the block looking for a threadable
829 We want to record an equivalence lhs = cache_lhs so that if
830 the result of this statement is used later we can copy propagate
832 record_const_or_copy (lhs
, cached_lhs
, &bd
->const_and_copies
);
833 register_new_def (lhs
, &bd
->block_defs
);
836 /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
837 arm will be taken. */
839 && (TREE_CODE (stmt
) == COND_EXPR
840 || TREE_CODE (stmt
) == SWITCH_EXPR
))
842 tree cond
, cached_lhs
;
845 /* Do not forward entry edges into the loop. In the case loop
846 has multiple entry edges we may end up in constructing irreducible
848 ??? We may consider forwarding the edges in the case all incoming
849 edges forward to the same destination block. */
850 if (!e
->flags
& EDGE_DFS_BACK
)
852 for (e1
= e
->dest
->pred
; e
; e
= e
->pred_next
)
853 if (e1
->flags
& EDGE_DFS_BACK
)
859 /* Now temporarily cprop the operands and try to find the resulting
860 expression in the hash tables. */
861 if (TREE_CODE (stmt
) == COND_EXPR
)
862 cond
= COND_EXPR_COND (stmt
);
864 cond
= SWITCH_COND (stmt
);
866 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
868 tree dummy_cond
, op0
, op1
;
869 enum tree_code cond_code
;
871 op0
= TREE_OPERAND (cond
, 0);
872 op1
= TREE_OPERAND (cond
, 1);
873 cond_code
= TREE_CODE (cond
);
875 /* Get the current value of both operands. */
876 if (TREE_CODE (op0
) == SSA_NAME
)
878 tree tmp
= get_value_for (op0
, const_and_copies
);
883 if (TREE_CODE (op1
) == SSA_NAME
)
885 tree tmp
= get_value_for (op1
, const_and_copies
);
890 /* Stuff the operator and operands into our dummy conditional
891 expression, creating the dummy conditional if necessary. */
892 dummy_cond
= walk_data
->global_data
;
895 dummy_cond
= build (cond_code
, boolean_type_node
, op0
, op1
);
896 dummy_cond
= build (COND_EXPR
, void_type_node
,
897 dummy_cond
, NULL
, NULL
);
898 walk_data
->global_data
= dummy_cond
;
902 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), cond_code
);
903 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op0
;
904 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1) = op1
;
907 /* If the conditional folds to an invariant, then we are done,
908 otherwise look it up in the hash tables. */
909 cached_lhs
= local_fold (COND_EXPR_COND (dummy_cond
));
910 if (! is_gimple_min_invariant (cached_lhs
))
911 cached_lhs
= lookup_avail_expr (dummy_cond
, NULL
, false);
912 if (!cached_lhs
|| ! is_gimple_min_invariant (cached_lhs
))
914 stmt_ann_t ann
= get_stmt_ann (dummy_cond
);
915 cached_lhs
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
921 /* We can have conditionals which just test the state of a
922 variable rather than use a relational operator. These are
923 simpler to handle. */
924 else if (TREE_CODE (cond
) == SSA_NAME
)
927 cached_lhs
= get_value_for (cached_lhs
, const_and_copies
);
928 if (cached_lhs
&& ! is_gimple_min_invariant (cached_lhs
))
932 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
936 edge taken_edge
= find_taken_edge (e
->dest
, cached_lhs
);
937 basic_block dest
= (taken_edge
? taken_edge
->dest
: NULL
);
942 /* If we have a known destination for the conditional, then
943 we can perform this optimization, which saves at least one
944 conditional jump each time it applies since we get to
945 bypass the conditional at our original destination.
947 Note that we can either thread through a block with PHIs
948 or to a block with PHIs, but not both. At this time the
949 bookkeeping to keep the CFG & SSA up-to-date has proven
953 int saved_forwardable
= bb_ann (e
->src
)->forwardable
;
956 bb_ann (e
->src
)->forwardable
= 0;
957 tmp_edge
= tree_block_forwards_to (dest
);
958 taken_edge
= (tmp_edge
? tmp_edge
: taken_edge
);
959 bb_ann (e
->src
)->forwardable
= saved_forwardable
;
960 VARRAY_PUSH_EDGE (redirection_edges
, e
);
961 VARRAY_PUSH_EDGE (redirection_edges
, taken_edge
);
968 /* Initialize the local stacks.
970 AVAIL_EXPRS stores all the expressions made available in this block.
972 CONST_AND_COPIES stores var/value pairs to restore at the end of this
975 NONZERO_VARS stores the vars which have a nonzero value made in this
978 STMTS_TO_RESCAN is a list of statements we will rescan for operands.
980 VRP_VARIABLES is the list of variables which have had their values
981 constrained by an operation in this block.
983 These stacks are cleared in the finalization routine run for each
987 dom_opt_initialize_block_local_data (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
988 basic_block bb ATTRIBUTE_UNUSED
,
989 bool recycled ATTRIBUTE_UNUSED
)
991 #ifdef ENABLE_CHECKING
992 struct dom_walk_block_data
*bd
993 = (struct dom_walk_block_data
*)VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
995 /* We get cleared memory from the allocator, so if the memory is not
996 cleared, then we are re-using a previously allocated entry. In
997 that case, we can also re-use the underlying virtual arrays. Just
998 make sure we clear them before using them! */
1001 if (bd
->avail_exprs
&& VARRAY_ACTIVE_SIZE (bd
->avail_exprs
) > 0)
1003 if (bd
->const_and_copies
&& VARRAY_ACTIVE_SIZE (bd
->const_and_copies
) > 0)
1005 if (bd
->nonzero_vars
&& VARRAY_ACTIVE_SIZE (bd
->nonzero_vars
) > 0)
1007 if (bd
->stmts_to_rescan
&& VARRAY_ACTIVE_SIZE (bd
->stmts_to_rescan
) > 0)
1009 if (bd
->vrp_variables
&& VARRAY_ACTIVE_SIZE (bd
->vrp_variables
) > 0)
1011 if (bd
->block_defs
&& VARRAY_ACTIVE_SIZE (bd
->block_defs
) > 0)
1017 /* Initialize local stacks for this optimizer and record equivalences
1018 upon entry to BB. Equivalences can come from the edge traversed to
1019 reach BB or they may come from PHI nodes at the start of BB. */
1022 dom_opt_initialize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
1024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1025 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1027 record_equivalences_from_incoming_edge (walk_data
, bb
);
1029 /* PHI nodes can create equivalences too. */
1030 record_equivalences_from_phis (walk_data
, bb
);
1033 /* Given an expression EXPR (a relational expression or a statement),
1034 initialize the hash table element pointed by by ELEMENT. */
1037 initialize_hash_element (tree expr
, tree lhs
, struct expr_hash_elt
*element
)
1039 /* Hash table elements may be based on conditional expressions or statements.
1041 For the former case, we have no annotation and we want to hash the
1042 conditional expression. In the latter case we have an annotation and
1043 we want to record the expression the statement evaluates. */
1044 if (TREE_CODE_CLASS (TREE_CODE (expr
)) == '<'
1045 || TREE_CODE (expr
) == TRUTH_NOT_EXPR
)
1047 element
->ann
= NULL
;
1048 element
->rhs
= expr
;
1050 else if (TREE_CODE (expr
) == COND_EXPR
)
1052 element
->ann
= stmt_ann (expr
);
1053 element
->rhs
= COND_EXPR_COND (expr
);
1055 else if (TREE_CODE (expr
) == SWITCH_EXPR
)
1057 element
->ann
= stmt_ann (expr
);
1058 element
->rhs
= SWITCH_COND (expr
);
1060 else if (TREE_CODE (expr
) == RETURN_EXPR
&& TREE_OPERAND (expr
, 0))
1062 element
->ann
= stmt_ann (expr
);
1063 element
->rhs
= TREE_OPERAND (TREE_OPERAND (expr
, 0), 1);
1067 element
->ann
= stmt_ann (expr
);
1068 element
->rhs
= TREE_OPERAND (expr
, 1);
1072 element
->hash
= avail_expr_hash (element
);
1075 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
1076 LIMIT entries left in LOCALs. */
1079 remove_local_expressions_from_table (varray_type locals
,
1086 /* Remove all the expressions made available in this block. */
1087 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1089 struct expr_hash_elt element
;
1090 tree expr
= VARRAY_TOP_TREE (locals
);
1091 VARRAY_POP (locals
);
1093 initialize_hash_element (expr
, NULL
, &element
);
1094 htab_remove_elt_with_hash (table
, &element
, element
.hash
);
1098 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
1099 state, stopping when there are LIMIT entries left in LOCALs. */
1102 restore_nonzero_vars_to_original_value (varray_type locals
,
1109 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1111 tree name
= VARRAY_TOP_TREE (locals
);
1112 VARRAY_POP (locals
);
1113 bitmap_clear_bit (table
, SSA_NAME_VERSION (name
));
1117 /* Use the source/dest pairs in LOCALS to restore TABLE to its original
1118 state, stopping when there are LIMIT entries left in LOCALs. */
1121 restore_vars_to_original_value (varray_type locals
,
1128 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1130 tree prev_value
, dest
;
1132 prev_value
= VARRAY_TOP_TREE (locals
);
1133 VARRAY_POP (locals
);
1134 dest
= VARRAY_TOP_TREE (locals
);
1135 VARRAY_POP (locals
);
1137 set_value_for (dest
, prev_value
, table
);
1141 /* Similar to restore_vars_to_original_value, except that it restores
1142 CURRDEFS to its original value. */
1144 restore_currdefs_to_original_value (varray_type locals
, unsigned limit
)
1149 /* Restore CURRDEFS to its original state. */
1150 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1152 tree tmp
= VARRAY_TOP_TREE (locals
);
1153 tree saved_def
, var
;
1155 VARRAY_POP (locals
);
1157 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
1158 definition of its underlying variable. If we recorded anything
1159 else, it must have been an _DECL node and its current reaching
1160 definition must have been NULL. */
1161 if (TREE_CODE (tmp
) == SSA_NAME
)
1164 var
= SSA_NAME_VAR (saved_def
);
1172 var_ann (var
)->current_def
= saved_def
;
1176 /* We have finished processing the dominator children of BB, perform
1177 any finalization actions in preparation for leaving this node in
1178 the dominator tree. */
1181 dom_opt_finalize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
1183 struct dom_walk_block_data
*bd
1184 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1187 /* If we are at a leaf node in the dominator graph, see if we can thread
1188 the edge from BB through its successor.
1190 Do this before we remove entries from our equivalence tables. */
1192 && ! bb
->succ
->succ_next
1193 && (bb
->succ
->flags
& EDGE_ABNORMAL
) == 0
1194 && (get_immediate_dominator (CDI_DOMINATORS
, bb
->succ
->dest
) != bb
1195 || phi_nodes (bb
->succ
->dest
)))
1198 thread_across_edge (walk_data
, bb
->succ
);
1200 else if ((last
= last_stmt (bb
))
1201 && TREE_CODE (last
) == COND_EXPR
1202 && (TREE_CODE_CLASS (TREE_CODE (COND_EXPR_COND (last
))) == '<'
1203 || TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
)
1205 && (bb
->succ
->flags
& EDGE_ABNORMAL
) == 0
1206 && bb
->succ
->succ_next
1207 && (bb
->succ
->succ_next
->flags
& EDGE_ABNORMAL
) == 0
1208 && ! bb
->succ
->succ_next
->succ_next
)
1210 edge true_edge
, false_edge
;
1211 tree cond
, inverted
= NULL
;
1212 enum tree_code cond_code
;
1214 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1216 cond
= COND_EXPR_COND (last
);
1217 cond_code
= TREE_CODE (cond
);
1219 if (TREE_CODE_CLASS (cond_code
) == '<')
1220 inverted
= invert_truthvalue (cond
);
1222 /* If the THEN arm is the end of a dominator tree or has PHI nodes,
1223 then try to thread through its edge. */
1224 if (get_immediate_dominator (CDI_DOMINATORS
, true_edge
->dest
) != bb
1225 || phi_nodes (true_edge
->dest
))
1227 unsigned avail_expr_limit
;
1228 unsigned const_and_copies_limit
;
1229 unsigned currdefs_limit
;
1232 = bd
->avail_exprs
? VARRAY_ACTIVE_SIZE (bd
->avail_exprs
) : 0;
1233 const_and_copies_limit
1234 = bd
->const_and_copies
? VARRAY_ACTIVE_SIZE (bd
->const_and_copies
)
1237 = bd
->block_defs
? VARRAY_ACTIVE_SIZE (bd
->block_defs
) : 0;
1239 /* Record any equivalences created by following this edge. */
1240 if (TREE_CODE_CLASS (cond_code
) == '<')
1242 record_cond (cond
, boolean_true_node
, &bd
->avail_exprs
);
1243 record_dominating_conditions (cond
, &bd
->avail_exprs
);
1244 record_cond (inverted
, boolean_false_node
, &bd
->avail_exprs
);
1246 else if (cond_code
== SSA_NAME
)
1247 record_const_or_copy (cond
, boolean_true_node
,
1248 &bd
->const_and_copies
);
1250 /* Now thread the edge. */
1251 thread_across_edge (walk_data
, true_edge
);
1253 /* And restore the various tables to their state before
1254 we threaded this edge. */
1255 remove_local_expressions_from_table (bd
->avail_exprs
,
1258 restore_vars_to_original_value (bd
->const_and_copies
,
1259 const_and_copies_limit
,
1261 restore_currdefs_to_original_value (bd
->block_defs
, currdefs_limit
);
1264 /* Similarly for the ELSE arm. */
1265 if (get_immediate_dominator (CDI_DOMINATORS
, false_edge
->dest
) != bb
1266 || phi_nodes (false_edge
->dest
))
1268 /* Record any equivalences created by following this edge. */
1269 if (TREE_CODE_CLASS (cond_code
) == '<')
1271 record_cond (cond
, boolean_false_node
, &bd
->avail_exprs
);
1272 record_cond (inverted
, boolean_true_node
, &bd
->avail_exprs
);
1273 record_dominating_conditions (inverted
, &bd
->avail_exprs
);
1275 else if (cond_code
== SSA_NAME
)
1276 record_const_or_copy (cond
, boolean_false_node
,
1277 &bd
->const_and_copies
);
1279 thread_across_edge (walk_data
, false_edge
);
1281 /* No need to remove local expressions from our tables
1282 or restore vars to their original value as that will
1283 be done immediately below. */
1287 remove_local_expressions_from_table (bd
->avail_exprs
, 0, avail_exprs
);
1288 restore_nonzero_vars_to_original_value (bd
->nonzero_vars
, 0, nonzero_vars
);
1289 restore_vars_to_original_value (bd
->const_and_copies
, 0, const_and_copies
);
1290 restore_currdefs_to_original_value (bd
->block_defs
, 0);
1292 /* Remove VRP records associated with this basic block. They are no
1295 To be efficient, we note which variables have had their values
1296 constrained in this block. So walk over each variable in the
1297 VRP_VARIABLEs array. */
1298 while (bd
->vrp_variables
&& VARRAY_ACTIVE_SIZE (bd
->vrp_variables
) > 0)
1300 tree var
= VARRAY_TOP_TREE (bd
->vrp_variables
);
1302 /* Each variable has a stack of value range records. We want to
1303 invalidate those associated with our basic block. So we walk
1304 the array backwards popping off records associated with our
1305 block. Once we hit a record not associated with our block
1307 varray_type var_vrp_records
= VARRAY_GENERIC_PTR (vrp_data
,
1308 SSA_NAME_VERSION (var
));
1310 while (VARRAY_ACTIVE_SIZE (var_vrp_records
) > 0)
1312 struct vrp_element
*element
1313 = (struct vrp_element
*)VARRAY_TOP_GENERIC_PTR (var_vrp_records
);
1315 if (element
->bb
!= bb
)
1318 VARRAY_POP (var_vrp_records
);
1321 VARRAY_POP (bd
->vrp_variables
);
1324 /* Re-scan operands in all statements that may have had new symbols
1326 while (bd
->stmts_to_rescan
&& VARRAY_ACTIVE_SIZE (bd
->stmts_to_rescan
) > 0)
1328 tree stmt
= VARRAY_TOP_TREE (bd
->stmts_to_rescan
);
1329 VARRAY_POP (bd
->stmts_to_rescan
);
1330 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1334 /* PHI nodes can create equivalences too.
1336 Ignoring any alternatives which are the same as the result, if
1337 all the alternatives are equal, then the PHI node creates an
1340 Additionally, if all the PHI alternatives are known to have a nonzero
1341 value, then the result of this PHI is known to have a nonzero value,
1342 even if we do not know its exact value. */
1345 record_equivalences_from_phis (struct dom_walk_data
*walk_data
, basic_block bb
)
1347 struct dom_walk_block_data
*bd
1348 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1351 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1353 tree lhs
= PHI_RESULT (phi
);
1357 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1359 tree t
= PHI_ARG_DEF (phi
, i
);
1361 if (TREE_CODE (t
) == SSA_NAME
|| is_gimple_min_invariant (t
))
1363 /* Ignore alternatives which are the same as our LHS. */
1364 if (operand_equal_p (lhs
, t
, 0))
1367 /* If we have not processed an alternative yet, then set
1368 RHS to this alternative. */
1371 /* If we have processed an alternative (stored in RHS), then
1372 see if it is equal to this one. If it isn't, then stop
1374 else if (! operand_equal_p (rhs
, t
, 0))
1381 /* If we had no interesting alternatives, then all the RHS alternatives
1382 must have been the same as LHS. */
1386 /* If we managed to iterate through each PHI alternative without
1387 breaking out of the loop, then we have a PHI which may create
1388 a useful equivalence. We do not need to record unwind data for
1389 this, since this is a true assignment and not an equivalence
1390 inferred from a comparison. All uses of this ssa name are dominated
1391 by this assignment, so unwinding just costs time and space. */
1392 if (i
== PHI_NUM_ARGS (phi
)
1393 && may_propagate_copy (lhs
, rhs
))
1394 set_value_for (lhs
, rhs
, const_and_copies
);
1396 /* Now see if we know anything about the nonzero property for the
1397 result of this PHI. */
1398 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1400 if (!PHI_ARG_NONZERO (phi
, i
))
1404 if (i
== PHI_NUM_ARGS (phi
))
1405 bitmap_set_bit (nonzero_vars
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1407 register_new_def (lhs
, &bd
->block_defs
);
1411 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1412 return that edge. Otherwise return NULL. */
1414 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
1419 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
1421 /* A loop back edge can be identified by the destination of
1422 the edge dominating the source of the edge. */
1423 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
1426 /* If we have already seen a non-loop edge, then we must have
1427 multiple incoming non-loop edges and thus we return NULL. */
1431 /* This is the first non-loop incoming edge we have found. Record
1439 /* Record any equivalences created by the incoming edge to BB. If BB
1440 has more than one incoming edge, then no equivalence is created. */
1443 record_equivalences_from_incoming_edge (struct dom_walk_data
*walk_data
,
1448 struct eq_expr_value eq_expr_value
;
1449 tree parent_block_last_stmt
= NULL
;
1450 struct dom_walk_block_data
*bd
1451 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1453 /* If our parent block ended with a control statment, then we may be
1454 able to record some equivalences based on which outgoing edge from
1455 the parent was followed. */
1456 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1459 parent_block_last_stmt
= last_stmt (parent
);
1460 if (parent_block_last_stmt
&& !is_ctrl_stmt (parent_block_last_stmt
))
1461 parent_block_last_stmt
= NULL
;
1464 eq_expr_value
.src
= NULL
;
1465 eq_expr_value
.dst
= NULL
;
1467 /* If we have a single predecessor (ignoring loop backedges), then extract
1468 EDGE_FLAGS from the single incoming edge. Otherwise just return as
1469 there is nothing to do. */
1471 && parent_block_last_stmt
)
1473 edge e
= single_incoming_edge_ignoring_loop_edges (bb
);
1474 if (e
&& bb_for_stmt (parent_block_last_stmt
) == e
->src
)
1475 edge_flags
= e
->flags
;
1482 /* If our parent block ended in a COND_EXPR, add any equivalences
1483 created by the COND_EXPR to the hash table and initialize
1484 EQ_EXPR_VALUE appropriately.
1486 EQ_EXPR_VALUE is an assignment expression created when BB's immediate
1487 dominator ends in a COND_EXPR statement whose predicate is of the form
1488 'VAR == VALUE', where VALUE may be another variable or a constant.
1489 This is used to propagate VALUE on the THEN_CLAUSE of that
1490 conditional. This assignment is inserted in CONST_AND_COPIES so that
1491 the copy and constant propagator can find more propagation
1493 if (TREE_CODE (parent_block_last_stmt
) == COND_EXPR
1494 && (edge_flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1495 eq_expr_value
= get_eq_expr_value (parent_block_last_stmt
,
1496 (edge_flags
& EDGE_TRUE_VALUE
) != 0,
1499 &bd
->vrp_variables
);
1500 /* Similarly when the parent block ended in a SWITCH_EXPR.
1501 We can only know the value of the switch's condition if the dominator
1502 parent is also the only predecessor of this block. */
1503 else if (bb
->pred
->src
== parent
1504 && TREE_CODE (parent_block_last_stmt
) == SWITCH_EXPR
)
1506 tree switch_cond
= SWITCH_COND (parent_block_last_stmt
);
1508 /* If the switch's condition is an SSA variable, then we may
1509 know its value at each of the case labels. */
1510 if (TREE_CODE (switch_cond
) == SSA_NAME
)
1512 tree switch_vec
= SWITCH_LABELS (parent_block_last_stmt
);
1513 size_t i
, n
= TREE_VEC_LENGTH (switch_vec
);
1515 tree match_case
= NULL_TREE
;
1517 /* Search the case labels for those whose destination is
1518 the current basic block. */
1519 for (i
= 0; i
< n
; ++i
)
1521 tree elt
= TREE_VEC_ELT (switch_vec
, i
);
1522 if (label_to_block (CASE_LABEL (elt
)) == bb
)
1524 if (++case_count
> 1 || CASE_HIGH (elt
))
1530 /* If we encountered precisely one CASE_LABEL_EXPR and it
1531 was not the default case, or a case range, then we know
1532 the exact value of SWITCH_COND which caused us to get to
1533 this block. Record that equivalence in EQ_EXPR_VALUE. */
1536 && CASE_LOW (match_case
)
1537 && !CASE_HIGH (match_case
))
1539 eq_expr_value
.dst
= switch_cond
;
1540 eq_expr_value
.src
= CASE_LOW (match_case
);
1545 /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
1546 new value for VAR, so that occurrences of VAR can be replaced with
1547 VALUE while re-writing the THEN arm of a COND_EXPR. */
1548 if (eq_expr_value
.src
&& eq_expr_value
.dst
)
1549 record_equality (eq_expr_value
.dst
, eq_expr_value
.src
,
1550 &bd
->const_and_copies
);
1553 /* Dump SSA statistics on FILE. */
1556 dump_dominator_optimization_stats (FILE *file
)
1560 fprintf (file
, "Total number of statements: %6ld\n\n",
1561 opt_stats
.num_stmts
);
1562 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1563 opt_stats
.num_exprs_considered
);
1565 n_exprs
= opt_stats
.num_exprs_considered
;
1569 fprintf (file
, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
1570 opt_stats
.num_re
, PERCENT (opt_stats
.num_re
,
1573 fprintf (file
, "\nHash table statistics:\n");
1575 fprintf (file
, " avail_exprs: ");
1576 htab_statistics (file
, avail_exprs
);
1580 /* Dump SSA statistics on stderr. */
1583 debug_dominator_optimization_stats (void)
1585 dump_dominator_optimization_stats (stderr
);
1589 /* Dump statistics for the hash table HTAB. */
1592 htab_statistics (FILE *file
, htab_t htab
)
1594 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1595 (long) htab_size (htab
),
1596 (long) htab_elements (htab
),
1597 htab_collisions (htab
));
1600 /* Record the fact that VAR has a nonzero value, though we may not know
1601 its exact value. Note that if VAR is already known to have a nonzero
1602 value, then we do nothing. */
1605 record_var_is_nonzero (tree var
, varray_type
*block_nonzero_vars_p
)
1607 int indx
= SSA_NAME_VERSION (var
);
1609 if (bitmap_bit_p (nonzero_vars
, indx
))
1612 /* Mark it in the global table. */
1613 bitmap_set_bit (nonzero_vars
, indx
);
1615 /* Record this SSA_NAME so that we can reset the global table
1616 when we leave this block. */
1617 if (! *block_nonzero_vars_p
)
1618 VARRAY_TREE_INIT (*block_nonzero_vars_p
, 2, "block_nonzero_vars");
1619 VARRAY_PUSH_TREE (*block_nonzero_vars_p
, var
);
1622 /* Enter a statement into the true/false expression hash table indicating
1623 that the condition COND has the value VALUE. */
1626 record_cond (tree cond
, tree value
, varray_type
*block_avail_exprs_p
)
1628 struct expr_hash_elt
*element
= xmalloc (sizeof (struct expr_hash_elt
));
1631 initialize_hash_element (cond
, value
, element
);
1633 slot
= htab_find_slot_with_hash (avail_exprs
, (void *)element
,
1634 element
->hash
, true);
1637 *slot
= (void *) element
;
1638 if (! *block_avail_exprs_p
)
1639 VARRAY_TREE_INIT (*block_avail_exprs_p
, 20, "block_avail_exprs");
1640 VARRAY_PUSH_TREE (*block_avail_exprs_p
, cond
);
1646 /* COND is a condition which is known to be true. Record variants of
1647 COND which must also be true.
1649 For example, if a < b is true, then a <= b must also be true. */
1652 record_dominating_conditions (tree cond
, varray_type
*block_avail_exprs_p
)
1654 switch (TREE_CODE (cond
))
1657 record_cond (build2 (LE_EXPR
, boolean_type_node
,
1658 TREE_OPERAND (cond
, 0),
1659 TREE_OPERAND (cond
, 1)),
1661 block_avail_exprs_p
);
1662 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1663 TREE_OPERAND (cond
, 0),
1664 TREE_OPERAND (cond
, 1)),
1666 block_avail_exprs_p
);
1667 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1668 TREE_OPERAND (cond
, 0),
1669 TREE_OPERAND (cond
, 1)),
1671 block_avail_exprs_p
);
1672 record_cond (build2 (LTGT_EXPR
, boolean_type_node
,
1673 TREE_OPERAND (cond
, 0),
1674 TREE_OPERAND (cond
, 1)),
1676 block_avail_exprs_p
);
1680 record_cond (build2 (GE_EXPR
, boolean_type_node
,
1681 TREE_OPERAND (cond
, 0),
1682 TREE_OPERAND (cond
, 1)),
1684 block_avail_exprs_p
);
1685 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1686 TREE_OPERAND (cond
, 0),
1687 TREE_OPERAND (cond
, 1)),
1689 block_avail_exprs_p
);
1690 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1691 TREE_OPERAND (cond
, 0),
1692 TREE_OPERAND (cond
, 1)),
1694 block_avail_exprs_p
);
1695 record_cond (build2 (LTGT_EXPR
, boolean_type_node
,
1696 TREE_OPERAND (cond
, 0),
1697 TREE_OPERAND (cond
, 1)),
1699 block_avail_exprs_p
);
1704 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1705 TREE_OPERAND (cond
, 0),
1706 TREE_OPERAND (cond
, 1)),
1708 block_avail_exprs_p
);
1712 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1713 TREE_OPERAND (cond
, 0),
1714 TREE_OPERAND (cond
, 1)),
1716 block_avail_exprs_p
);
1717 record_cond (build2 (LE_EXPR
, boolean_type_node
,
1718 TREE_OPERAND (cond
, 0),
1719 TREE_OPERAND (cond
, 1)),
1721 block_avail_exprs_p
);
1722 record_cond (build2 (GE_EXPR
, boolean_type_node
,
1723 TREE_OPERAND (cond
, 0),
1724 TREE_OPERAND (cond
, 1)),
1726 block_avail_exprs_p
);
1729 case UNORDERED_EXPR
:
1730 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1731 TREE_OPERAND (cond
, 0),
1732 TREE_OPERAND (cond
, 1)),
1734 block_avail_exprs_p
);
1735 record_cond (build2 (UNLE_EXPR
, boolean_type_node
,
1736 TREE_OPERAND (cond
, 0),
1737 TREE_OPERAND (cond
, 1)),
1739 block_avail_exprs_p
);
1740 record_cond (build2 (UNGE_EXPR
, boolean_type_node
,
1741 TREE_OPERAND (cond
, 0),
1742 TREE_OPERAND (cond
, 1)),
1744 block_avail_exprs_p
);
1745 record_cond (build2 (UNEQ_EXPR
, boolean_type_node
,
1746 TREE_OPERAND (cond
, 0),
1747 TREE_OPERAND (cond
, 1)),
1749 block_avail_exprs_p
);
1750 record_cond (build2 (UNLT_EXPR
, boolean_type_node
,
1751 TREE_OPERAND (cond
, 0),
1752 TREE_OPERAND (cond
, 1)),
1754 block_avail_exprs_p
);
1755 record_cond (build2 (UNGT_EXPR
, boolean_type_node
,
1756 TREE_OPERAND (cond
, 0),
1757 TREE_OPERAND (cond
, 1)),
1759 block_avail_exprs_p
);
1763 record_cond (build2 (UNLE_EXPR
, boolean_type_node
,
1764 TREE_OPERAND (cond
, 0),
1765 TREE_OPERAND (cond
, 1)),
1767 block_avail_exprs_p
);
1768 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1769 TREE_OPERAND (cond
, 0),
1770 TREE_OPERAND (cond
, 1)),
1772 block_avail_exprs_p
);
1776 record_cond (build2 (UNGE_EXPR
, boolean_type_node
,
1777 TREE_OPERAND (cond
, 0),
1778 TREE_OPERAND (cond
, 1)),
1780 block_avail_exprs_p
);
1781 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1782 TREE_OPERAND (cond
, 0),
1783 TREE_OPERAND (cond
, 1)),
1785 block_avail_exprs_p
);
1789 record_cond (build2 (UNLE_EXPR
, boolean_type_node
,
1790 TREE_OPERAND (cond
, 0),
1791 TREE_OPERAND (cond
, 1)),
1793 block_avail_exprs_p
);
1794 record_cond (build2 (UNGE_EXPR
, boolean_type_node
,
1795 TREE_OPERAND (cond
, 0),
1796 TREE_OPERAND (cond
, 1)),
1798 block_avail_exprs_p
);
1802 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1803 TREE_OPERAND (cond
, 0),
1804 TREE_OPERAND (cond
, 1)),
1806 block_avail_exprs_p
);
1807 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1808 TREE_OPERAND (cond
, 0),
1809 TREE_OPERAND (cond
, 1)),
1811 block_avail_exprs_p
);
1818 /* A helper function for record_const_or_copy and record_equality.
1819 Do the work of recording the value and undo info. */
1822 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
,
1823 varray_type
*block_const_and_copies_p
)
1825 set_value_for (x
, y
, const_and_copies
);
1827 if (!*block_const_and_copies_p
)
1828 VARRAY_TREE_INIT (*block_const_and_copies_p
, 2, "block_const_and_copies");
1829 VARRAY_PUSH_TREE (*block_const_and_copies_p
, x
);
1830 VARRAY_PUSH_TREE (*block_const_and_copies_p
, prev_x
);
1833 /* Record that X is equal to Y in const_and_copies. Record undo
1834 information in the block-local varray. */
1837 record_const_or_copy (tree x
, tree y
, varray_type
*block_const_and_copies_p
)
1839 tree prev_x
= get_value_for (x
, const_and_copies
);
1841 if (TREE_CODE (y
) == SSA_NAME
)
1843 tree tmp
= get_value_for (y
, const_and_copies
);
1848 record_const_or_copy_1 (x
, y
, prev_x
, block_const_and_copies_p
);
1851 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1852 This constrains the cases in which we may treat this as assignment. */
1855 record_equality (tree x
, tree y
, varray_type
*block_const_and_copies_p
)
1857 tree prev_x
= NULL
, prev_y
= NULL
;
1859 if (TREE_CODE (x
) == SSA_NAME
)
1860 prev_x
= get_value_for (x
, const_and_copies
);
1861 if (TREE_CODE (y
) == SSA_NAME
)
1862 prev_y
= get_value_for (y
, const_and_copies
);
1864 /* If one of the previous values is invariant, then use that.
1865 Otherwise it doesn't matter which value we choose, just so
1866 long as we canonicalize on one value. */
1867 if (TREE_INVARIANT (y
))
1869 else if (TREE_INVARIANT (x
))
1870 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1871 else if (prev_x
&& TREE_INVARIANT (prev_x
))
1872 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1876 /* After the swapping, we must have one SSA_NAME. */
1877 if (TREE_CODE (x
) != SSA_NAME
)
1880 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1881 variable compared against zero. If we're honoring signed zeros,
1882 then we cannot record this value unless we know that the value is
1884 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1885 && (TREE_CODE (y
) != REAL_CST
1886 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1889 record_const_or_copy_1 (x
, y
, prev_x
, block_const_and_copies_p
);
1892 /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
1893 hash tables. Try to simplify the RHS using whatever equivalences
1894 we may have recorded.
1896 If we are able to simplify the RHS, then lookup the simplified form in
1897 the hash table and return the result. Otherwise return NULL. */
1900 simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*walk_data
,
1905 tree rhs
= TREE_OPERAND (stmt
, 1);
1906 enum tree_code rhs_code
= TREE_CODE (rhs
);
1908 struct dom_walk_block_data
*bd
1909 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1911 /* If we have lhs = ~x, look and see if we earlier had x = ~y.
1912 In which case we can change this statement to be lhs = y.
1913 Which can then be copy propagated.
1915 Similarly for negation. */
1916 if ((rhs_code
== BIT_NOT_EXPR
|| rhs_code
== NEGATE_EXPR
)
1917 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
1919 /* Get the definition statement for our RHS. */
1920 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1922 /* See if the RHS_DEF_STMT has the same form as our statement. */
1923 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
1924 && TREE_CODE (TREE_OPERAND (rhs_def_stmt
, 1)) == rhs_code
)
1926 tree rhs_def_operand
;
1928 rhs_def_operand
= TREE_OPERAND (TREE_OPERAND (rhs_def_stmt
, 1), 0);
1930 /* Verify that RHS_DEF_OPERAND is a suitable SSA variable. */
1931 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
1932 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
1933 result
= update_rhs_and_lookup_avail_expr (stmt
,
1941 /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
1942 If OP is associative, create and fold (y OP C2) OP C1 which
1943 should result in (y OP C3), use that as the RHS for the
1944 assignment. Add minus to this, as we handle it specially below. */
1945 if ((associative_tree_code (rhs_code
) || rhs_code
== MINUS_EXPR
)
1946 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
1947 && is_gimple_min_invariant (TREE_OPERAND (rhs
, 1)))
1949 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1951 /* See if the RHS_DEF_STMT has the same form as our statement. */
1952 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
)
1954 tree rhs_def_rhs
= TREE_OPERAND (rhs_def_stmt
, 1);
1955 enum tree_code rhs_def_code
= TREE_CODE (rhs_def_rhs
);
1957 if (rhs_code
== rhs_def_code
1958 || (rhs_code
== PLUS_EXPR
&& rhs_def_code
== MINUS_EXPR
)
1959 || (rhs_code
== MINUS_EXPR
&& rhs_def_code
== PLUS_EXPR
))
1961 tree def_stmt_op0
= TREE_OPERAND (rhs_def_rhs
, 0);
1962 tree def_stmt_op1
= TREE_OPERAND (rhs_def_rhs
, 1);
1964 if (TREE_CODE (def_stmt_op0
) == SSA_NAME
1965 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0
)
1966 && is_gimple_min_invariant (def_stmt_op1
))
1968 tree outer_const
= TREE_OPERAND (rhs
, 1);
1969 tree type
= TREE_TYPE (TREE_OPERAND (stmt
, 0));
1972 /* If we care about correct floating point results, then
1973 don't fold x + c1 - c2. Note that we need to take both
1974 the codes and the signs to figure this out. */
1975 if (FLOAT_TYPE_P (type
)
1976 && !flag_unsafe_math_optimizations
1977 && (rhs_def_code
== PLUS_EXPR
1978 || rhs_def_code
== MINUS_EXPR
))
1982 neg
^= (rhs_code
== MINUS_EXPR
);
1983 neg
^= (rhs_def_code
== MINUS_EXPR
);
1984 neg
^= real_isneg (TREE_REAL_CST_PTR (outer_const
));
1985 neg
^= real_isneg (TREE_REAL_CST_PTR (def_stmt_op1
));
1988 goto dont_fold_assoc
;
1991 /* Ho hum. So fold will only operate on the outermost
1992 thingy that we give it, so we have to build the new
1993 expression in two pieces. This requires that we handle
1994 combinations of plus and minus. */
1995 if (rhs_def_code
!= rhs_code
)
1997 if (rhs_def_code
== MINUS_EXPR
)
1998 t
= build (MINUS_EXPR
, type
, outer_const
, def_stmt_op1
);
2000 t
= build (MINUS_EXPR
, type
, def_stmt_op1
, outer_const
);
2001 rhs_code
= PLUS_EXPR
;
2003 else if (rhs_def_code
== MINUS_EXPR
)
2004 t
= build (PLUS_EXPR
, type
, def_stmt_op1
, outer_const
);
2006 t
= build (rhs_def_code
, type
, def_stmt_op1
, outer_const
);
2008 t
= build (rhs_code
, type
, def_stmt_op0
, t
);
2011 /* If the result is a suitable looking gimple expression,
2012 then use it instead of the original for STMT. */
2013 if (TREE_CODE (t
) == SSA_NAME
2014 || (TREE_CODE_CLASS (TREE_CODE (t
)) == '1'
2015 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
2016 || ((TREE_CODE_CLASS (TREE_CODE (t
)) == '2'
2017 || TREE_CODE_CLASS (TREE_CODE (t
)) == '<')
2018 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
2019 && is_gimple_val (TREE_OPERAND (t
, 1))))
2020 result
= update_rhs_and_lookup_avail_expr
2021 (stmt
, t
, &bd
->avail_exprs
, ann
, insert
);
2028 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
2029 and BIT_AND_EXPR respectively if the first operand is greater
2030 than zero and the second operand is an exact power of two. */
2031 if ((rhs_code
== TRUNC_DIV_EXPR
|| rhs_code
== TRUNC_MOD_EXPR
)
2032 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
2033 && integer_pow2p (TREE_OPERAND (rhs
, 1)))
2036 tree op
= TREE_OPERAND (rhs
, 0);
2038 if (TYPE_UNSIGNED (TREE_TYPE (op
)))
2040 val
= integer_one_node
;
2044 tree dummy_cond
= walk_data
->global_data
;
2048 dummy_cond
= build (GT_EXPR
, boolean_type_node
,
2049 op
, integer_zero_node
);
2050 dummy_cond
= build (COND_EXPR
, void_type_node
,
2051 dummy_cond
, NULL
, NULL
);
2052 walk_data
->global_data
= dummy_cond
;
2056 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), GT_EXPR
);
2057 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
2058 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
2059 = integer_zero_node
;
2061 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
2066 if (val
&& integer_onep (val
))
2069 tree op0
= TREE_OPERAND (rhs
, 0);
2070 tree op1
= TREE_OPERAND (rhs
, 1);
2072 if (rhs_code
== TRUNC_DIV_EXPR
)
2073 t
= build (RSHIFT_EXPR
, TREE_TYPE (op0
), op0
,
2074 build_int_2 (tree_log2 (op1
), 0));
2076 t
= build (BIT_AND_EXPR
, TREE_TYPE (op0
), op0
,
2077 local_fold (build (MINUS_EXPR
, TREE_TYPE (op1
),
2078 op1
, integer_one_node
)));
2080 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
2086 /* Transform ABS (X) into X or -X as appropriate. */
2087 if (rhs_code
== ABS_EXPR
2088 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
2091 tree op
= TREE_OPERAND (rhs
, 0);
2092 tree type
= TREE_TYPE (op
);
2094 if (TYPE_UNSIGNED (type
))
2096 val
= integer_zero_node
;
2100 tree dummy_cond
= walk_data
->global_data
;
2104 dummy_cond
= build (LE_EXPR
, boolean_type_node
,
2105 op
, integer_zero_node
);
2106 dummy_cond
= build (COND_EXPR
, void_type_node
,
2107 dummy_cond
, NULL
, NULL
);
2108 walk_data
->global_data
= dummy_cond
;
2112 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), LE_EXPR
);
2113 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
2114 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
2115 = fold_convert (type
, integer_zero_node
);
2117 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
2123 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), GE_EXPR
);
2124 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
2125 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
2126 = fold_convert (type
, integer_zero_node
);
2128 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
2134 if (integer_zerop (val
))
2135 val
= integer_one_node
;
2136 else if (integer_onep (val
))
2137 val
= integer_zero_node
;
2143 && (integer_onep (val
) || integer_zerop (val
)))
2147 if (integer_onep (val
))
2148 t
= build1 (NEGATE_EXPR
, TREE_TYPE (op
), op
);
2152 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
2158 /* Optimize *"foo" into 'f'. This is done here rather than
2159 in fold to avoid problems with stuff like &*"foo". */
2160 if (TREE_CODE (rhs
) == INDIRECT_REF
|| TREE_CODE (rhs
) == ARRAY_REF
)
2162 tree t
= fold_read_from_constant_string (rhs
);
2165 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
2173 /* COND is a condition of the form:
2175 x == const or x != const
2177 Look back to x's defining statement and see if x is defined as
2181 If const is unchanged if we convert it to type, then we can build
2182 the equivalent expression:
2185 y == const or y != const
2187 Which may allow further optimizations.
2189 Return the equivalent comparison or NULL if no such equivalent comparison
2193 find_equivalent_equality_comparison (tree cond
)
2195 tree op0
= TREE_OPERAND (cond
, 0);
2196 tree op1
= TREE_OPERAND (cond
, 1);
2197 tree def_stmt
= SSA_NAME_DEF_STMT (op0
);
2199 /* OP0 might have been a parameter, so first make sure it
2200 was defined by a MODIFY_EXPR. */
2201 if (def_stmt
&& TREE_CODE (def_stmt
) == MODIFY_EXPR
)
2203 tree def_rhs
= TREE_OPERAND (def_stmt
, 1);
2205 /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
2206 if ((TREE_CODE (def_rhs
) == NOP_EXPR
2207 || TREE_CODE (def_rhs
) == CONVERT_EXPR
)
2208 && TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == SSA_NAME
)
2210 tree def_rhs_inner
= TREE_OPERAND (def_rhs
, 0);
2211 tree def_rhs_inner_type
= TREE_TYPE (def_rhs_inner
);
2214 if (TYPE_PRECISION (def_rhs_inner_type
)
2215 > TYPE_PRECISION (TREE_TYPE (def_rhs
)))
2218 /* What we want to prove is that if we convert OP1 to
2219 the type of the object inside the NOP_EXPR that the
2220 result is still equivalent to SRC.
2222 If that is true, the build and return new equivalent
2223 condition which uses the source of the typecast and the
2224 new constant (which has only changed its type). */
2225 new = build1 (TREE_CODE (def_rhs
), def_rhs_inner_type
, op1
);
2226 new = local_fold (new);
2227 if (is_gimple_val (new) && tree_int_cst_equal (new, op1
))
2228 return build (TREE_CODE (cond
), TREE_TYPE (cond
),
2229 def_rhs_inner
, new);
2235 /* STMT is a COND_EXPR for which we could not trivially determine its
2236 result. This routine attempts to find equivalent forms of the
2237 condition which we may be able to optimize better. It also
2238 uses simple value range propagation to optimize conditionals. */
2241 simplify_cond_and_lookup_avail_expr (tree stmt
,
2242 varray_type
*block_avail_exprs_p
,
2246 tree cond
= COND_EXPR_COND (stmt
);
2248 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
2250 tree op0
= TREE_OPERAND (cond
, 0);
2251 tree op1
= TREE_OPERAND (cond
, 1);
2253 if (TREE_CODE (op0
) == SSA_NAME
&& is_gimple_min_invariant (op1
))
2256 tree low
, high
, cond_low
, cond_high
;
2257 int lowequal
, highequal
, swapped
, no_overlap
, subset
, cond_inverted
;
2258 varray_type vrp_records
;
2259 struct vrp_element
*element
;
2261 /* First see if we have test of an SSA_NAME against a constant
2262 where the SSA_NAME is defined by an earlier typecast which
2263 is irrelevant when performing tests against the given
2265 if (TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
2267 tree new_cond
= find_equivalent_equality_comparison (cond
);
2271 /* Update the statement to use the new equivalent
2273 COND_EXPR_COND (stmt
) = new_cond
;
2276 /* Lookup the condition and return its known value if it
2278 new_cond
= lookup_avail_expr (stmt
, block_avail_exprs_p
,
2283 /* The operands have changed, so update op0 and op1. */
2284 op0
= TREE_OPERAND (cond
, 0);
2285 op1
= TREE_OPERAND (cond
, 1);
2289 /* Consult the value range records for this variable (if they exist)
2290 to see if we can eliminate or simplify this conditional.
2292 Note two tests are necessary to determine no records exist.
2293 First we have to see if the virtual array exists, if it
2294 exists, then we have to check its active size.
2296 Also note the vast majority of conditionals are not testing
2297 a variable which has had its range constrained by an earlier
2298 conditional. So this filter avoids a lot of unnecessary work. */
2299 vrp_records
= VARRAY_GENERIC_PTR (vrp_data
, SSA_NAME_VERSION (op0
));
2300 if (vrp_records
== NULL
)
2303 limit
= VARRAY_ACTIVE_SIZE (vrp_records
);
2305 /* If we have no value range records for this variable, or we are
2306 unable to extract a range for this condition, then there is
2309 || ! extract_range_from_cond (cond
, &cond_high
,
2310 &cond_low
, &cond_inverted
))
2313 /* We really want to avoid unnecessary computations of range
2314 info. So all ranges are computed lazily; this avoids a
2315 lot of unnecessary work. ie, we record the conditional,
2316 but do not process how it constrains the variable's
2317 potential values until we know that processing the condition
2320 However, we do not want to have to walk a potentially long
2321 list of ranges, nor do we want to compute a variable's
2322 range more than once for a given path.
2324 Luckily, each time we encounter a conditional that can not
2325 be otherwise optimized we will end up here and we will
2326 compute the necessary range information for the variable
2327 used in this condition.
2329 Thus you can conclude that there will never be more than one
2330 conditional associated with a variable which has not been
2331 processed. So we never need to merge more than one new
2332 conditional into the current range.
2334 These properties also help us avoid unnecessary work. */
2336 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
, limit
- 1);
2338 if (element
->high
&& element
->low
)
2340 /* The last element has been processed, so there is no range
2341 merging to do, we can simply use the high/low values
2342 recorded in the last element. */
2344 high
= element
->high
;
2348 tree tmp_high
, tmp_low
;
2351 /* The last element has not been processed. Process it now. */
2352 extract_range_from_cond (element
->cond
, &tmp_high
,
2355 /* If this is the only element, then no merging is necessary,
2356 the high/low values from extract_range_from_cond are all
2365 /* Get the high/low value from the previous element. */
2366 struct vrp_element
*prev
2367 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
,
2372 /* Merge in this element's range with the range from the
2375 The low value for the merged range is the maximum of
2376 the previous low value and the low value of this record.
2378 Similarly the high value for the merged range is the
2379 minimum of the previous high value and the high value of
2381 low
= (tree_int_cst_compare (low
, tmp_low
) == 1
2383 high
= (tree_int_cst_compare (high
, tmp_high
) == -1
2387 /* And record the computed range. */
2389 element
->high
= high
;
2393 /* After we have constrained this variable's potential values,
2394 we try to determine the result of the given conditional.
2396 To simplify later tests, first determine if the current
2397 low value is the same low value as the conditional.
2398 Similarly for the current high value and the high value
2399 for the conditional. */
2400 lowequal
= tree_int_cst_equal (low
, cond_low
);
2401 highequal
= tree_int_cst_equal (high
, cond_high
);
2403 if (lowequal
&& highequal
)
2404 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2406 /* To simplify the overlap/subset tests below we may want
2407 to swap the two ranges so that the larger of the two
2408 ranges occurs "first". */
2410 if (tree_int_cst_compare (low
, cond_low
) == 1
2412 && tree_int_cst_compare (cond_high
, high
) == 1))
2425 /* Now determine if there is no overlap in the ranges
2426 or if the second range is a subset of the first range. */
2427 no_overlap
= tree_int_cst_lt (high
, cond_low
);
2428 subset
= tree_int_cst_compare (cond_high
, high
) != 1;
2430 /* If there was no overlap in the ranges, then this conditional
2431 always has a false value (unless we had to invert this
2432 conditional, in which case it always has a true value). */
2434 return (cond_inverted
? boolean_true_node
: boolean_false_node
);
2436 /* If the current range is a subset of the condition's range,
2437 then this conditional always has a true value (unless we
2438 had to invert this conditional, in which case it always
2439 has a true value). */
2440 if (subset
&& swapped
)
2441 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2443 /* We were unable to determine the result of the conditional.
2444 However, we may be able to simplify the conditional. First
2445 merge the ranges in the same manner as range merging above. */
2446 low
= tree_int_cst_compare (low
, cond_low
) == 1 ? low
: cond_low
;
2447 high
= tree_int_cst_compare (high
, cond_high
) == -1 ? high
: cond_high
;
2449 /* If the range has converged to a single point, then turn this
2450 into an equality comparison. */
2451 if (TREE_CODE (cond
) != EQ_EXPR
2452 && TREE_CODE (cond
) != NE_EXPR
2453 && tree_int_cst_equal (low
, high
))
2455 TREE_SET_CODE (cond
, EQ_EXPR
);
2456 TREE_OPERAND (cond
, 1) = high
;
2463 /* STMT is a SWITCH_EXPR for which we could not trivially determine its
2464 result. This routine attempts to find equivalent forms of the
2465 condition which we may be able to optimize better. */
2468 simplify_switch_and_lookup_avail_expr (tree stmt
,
2469 varray_type
*block_avail_exprs_p
,
2473 tree cond
= SWITCH_COND (stmt
);
2476 /* The optimization that we really care about is removing unnecessary
2477 casts. That will let us do much better in propagating the inferred
2478 constant at the switch target. */
2479 if (TREE_CODE (cond
) == SSA_NAME
)
2481 def
= SSA_NAME_DEF_STMT (cond
);
2482 if (TREE_CODE (def
) == MODIFY_EXPR
)
2484 def
= TREE_OPERAND (def
, 1);
2485 if (TREE_CODE (def
) == NOP_EXPR
)
2490 def
= TREE_OPERAND (def
, 0);
2492 #ifdef ENABLE_CHECKING
2493 /* ??? Why was Jeff testing this? We are gimple... */
2494 if (!is_gimple_val (def
))
2498 to
= TREE_TYPE (cond
);
2499 ti
= TREE_TYPE (def
);
2501 /* If we have an extension that preserves value, then we
2502 can copy the source value into the switch. */
2504 need_precision
= TYPE_PRECISION (ti
);
2506 if (TYPE_UNSIGNED (to
) && !TYPE_UNSIGNED (ti
))
2508 else if (!TYPE_UNSIGNED (to
) && TYPE_UNSIGNED (ti
))
2509 need_precision
+= 1;
2510 if (TYPE_PRECISION (to
) < need_precision
)
2515 SWITCH_COND (stmt
) = def
;
2518 return lookup_avail_expr (stmt
, block_avail_exprs_p
, insert
);
2528 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2529 known value for that SSA_NAME (or NULL if no value is known).
2531 NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
2532 even if we don't know their precise value.
2534 Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
2535 nodes of the successors of BB. */
2538 cprop_into_successor_phis (basic_block bb
,
2539 varray_type const_and_copies
,
2540 bitmap nonzero_vars
)
2544 /* This can get rather expensive if the implementation is naive in
2545 how it finds the phi alternative associated with a particular edge. */
2546 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
2552 /* If this is an abnormal edge, then we do not want to copy propagate
2553 into the PHI alternative associated with this edge. */
2554 if (e
->flags
& EDGE_ABNORMAL
)
2557 phi
= phi_nodes (e
->dest
);
2561 /* There is no guarantee that for any two PHI nodes in a block that
2562 the phi alternative associated with a particular edge will be
2563 at the same index in the phi alternative array.
2565 However, it is very likely they will be the same. So we keep
2566 track of the index of the alternative where we found the edge in
2567 the previous phi node and check that index first in the next
2568 phi node. If that hint fails, then we actually search all
2570 phi_num_args
= PHI_NUM_ARGS (phi
);
2571 hint
= phi_num_args
;
2572 for ( ; phi
; phi
= PHI_CHAIN (phi
))
2576 use_operand_p orig_p
;
2579 /* If the hint is valid (!= phi_num_args), see if it points
2580 us to the desired phi alternative. */
2581 if (hint
!= phi_num_args
&& PHI_ARG_EDGE (phi
, hint
) == e
)
2585 /* The hint was either invalid or did not point to the
2586 correct phi alternative. Search all the alternatives
2587 for the correct one. Update the hint. */
2588 for (i
= 0; i
< phi_num_args
; i
++)
2589 if (PHI_ARG_EDGE (phi
, i
) == e
)
2594 #ifdef ENABLE_CHECKING
2595 /* If we did not find the proper alternative, then something is
2597 if (hint
== phi_num_args
)
2601 /* The alternative may be associated with a constant, so verify
2602 it is an SSA_NAME before doing anything with it. */
2603 orig_p
= PHI_ARG_DEF_PTR (phi
, hint
);
2604 orig
= USE_FROM_PTR (orig_p
);
2605 if (TREE_CODE (orig
) != SSA_NAME
)
2608 /* If the alternative is known to have a nonzero value, record
2609 that fact in the PHI node itself for future use. */
2610 if (bitmap_bit_p (nonzero_vars
, SSA_NAME_VERSION (orig
)))
2611 PHI_ARG_NONZERO (phi
, hint
) = true;
2613 /* If we have *ORIG_P in our constant/copy table, then replace
2614 ORIG_P with its value in our constant/copy table. */
2615 new = VARRAY_TREE (const_and_copies
, SSA_NAME_VERSION (orig
));
2617 && (TREE_CODE (new) == SSA_NAME
2618 || is_gimple_min_invariant (new))
2619 && may_propagate_copy (orig
, new))
2621 propagate_value (orig_p
, new);
2628 /* Propagate known constants/copies into PHI nodes of BB's successor
2632 cprop_into_phis (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
2635 cprop_into_successor_phis (bb
, const_and_copies
, nonzero_vars
);
2638 /* Search for redundant computations in STMT. If any are found, then
2639 replace them with the variable holding the result of the computation.
2641 If safe, record this expression into the available expression hash
2645 eliminate_redundant_computations (struct dom_walk_data
*walk_data
,
2646 tree stmt
, stmt_ann_t ann
)
2648 v_may_def_optype v_may_defs
= V_MAY_DEF_OPS (ann
);
2649 tree
*expr_p
, def
= NULL_TREE
;
2652 bool retval
= false;
2653 struct dom_walk_block_data
*bd
2654 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
2656 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2657 def
= TREE_OPERAND (stmt
, 0);
2659 /* Certain expressions on the RHS can be optimized away, but can not
2660 themselves be entered into the hash tables. */
2661 if (ann
->makes_aliased_stores
2663 || TREE_CODE (def
) != SSA_NAME
2664 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
2665 || NUM_V_MAY_DEFS (v_may_defs
) != 0)
2668 /* Check if the expression has been computed before. */
2669 cached_lhs
= lookup_avail_expr (stmt
, &bd
->avail_exprs
, insert
);
2671 /* If this is an assignment and the RHS was not in the hash table,
2672 then try to simplify the RHS and lookup the new RHS in the
2674 if (! cached_lhs
&& TREE_CODE (stmt
) == MODIFY_EXPR
)
2675 cached_lhs
= simplify_rhs_and_lookup_avail_expr (walk_data
,
2679 /* Similarly if this is a COND_EXPR and we did not find its
2680 expression in the hash table, simplify the condition and
2682 else if (! cached_lhs
&& TREE_CODE (stmt
) == COND_EXPR
)
2683 cached_lhs
= simplify_cond_and_lookup_avail_expr (stmt
,
2687 /* Similarly for a SWITCH_EXPR. */
2688 else if (!cached_lhs
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
2689 cached_lhs
= simplify_switch_and_lookup_avail_expr (stmt
,
2694 opt_stats
.num_exprs_considered
++;
2696 /* Get a pointer to the expression we are trying to optimize. */
2697 if (TREE_CODE (stmt
) == COND_EXPR
)
2698 expr_p
= &COND_EXPR_COND (stmt
);
2699 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2700 expr_p
= &SWITCH_COND (stmt
);
2701 else if (TREE_CODE (stmt
) == RETURN_EXPR
&& TREE_OPERAND (stmt
, 0))
2702 expr_p
= &TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
2704 expr_p
= &TREE_OPERAND (stmt
, 1);
2706 /* It is safe to ignore types here since we have already done
2707 type checking in the hashing and equality routines. In fact
2708 type checking here merely gets in the way of constant
2709 propagation. Also, make sure that it is safe to propagate
2710 CACHED_LHS into *EXPR_P. */
2712 && (TREE_CODE (cached_lhs
) != SSA_NAME
2713 || may_propagate_copy (*expr_p
, cached_lhs
)))
2715 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2717 fprintf (dump_file
, " Replaced redundant expr '");
2718 print_generic_expr (dump_file
, *expr_p
, dump_flags
);
2719 fprintf (dump_file
, "' with '");
2720 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
2721 fprintf (dump_file
, "'\n");
2726 #if defined ENABLE_CHECKING
2727 if (TREE_CODE (cached_lhs
) != SSA_NAME
2728 && !is_gimple_min_invariant (cached_lhs
))
2732 if (TREE_CODE (cached_lhs
) == ADDR_EXPR
2733 || (POINTER_TYPE_P (TREE_TYPE (*expr_p
))
2734 && is_gimple_min_invariant (cached_lhs
)))
2737 propagate_tree_value (expr_p
, cached_lhs
);
2743 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
2744 the available expressions table or the const_and_copies table.
2745 Detect and record those equivalences. */
2748 record_equivalences_from_stmt (tree stmt
,
2749 varray_type
*block_avail_exprs_p
,
2750 varray_type
*block_nonzero_vars_p
,
2754 tree lhs
= TREE_OPERAND (stmt
, 0);
2755 enum tree_code lhs_code
= TREE_CODE (lhs
);
2758 if (lhs_code
== SSA_NAME
)
2760 tree rhs
= TREE_OPERAND (stmt
, 1);
2762 /* Strip away any useless type conversions. */
2763 STRIP_USELESS_TYPE_CONVERSION (rhs
);
2765 /* If the RHS of the assignment is a constant or another variable that
2766 may be propagated, register it in the CONST_AND_COPIES table. We
2767 do not need to record unwind data for this, since this is a true
2768 assignment and not an equivalence inferred from a comparison. All
2769 uses of this ssa name are dominated by this assignment, so unwinding
2770 just costs time and space. */
2772 && (TREE_CODE (rhs
) == SSA_NAME
2773 || is_gimple_min_invariant (rhs
)))
2774 set_value_for (lhs
, rhs
, const_and_copies
);
2776 /* alloca never returns zero and the address of a non-weak symbol
2777 is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
2778 stripped as they do not affect this equivalence. */
2779 while (TREE_CODE (rhs
) == NOP_EXPR
2780 || TREE_CODE (rhs
) == CONVERT_EXPR
)
2781 rhs
= TREE_OPERAND (rhs
, 0);
2783 if (alloca_call_p (rhs
)
2784 || (TREE_CODE (rhs
) == ADDR_EXPR
2785 && DECL_P (TREE_OPERAND (rhs
, 0))
2786 && ! DECL_WEAK (TREE_OPERAND (rhs
, 0))))
2787 record_var_is_nonzero (lhs
, block_nonzero_vars_p
);
2789 /* IOR of any value with a nonzero value will result in a nonzero
2790 value. Even if we do not know the exact result recording that
2791 the result is nonzero is worth the effort. */
2792 if (TREE_CODE (rhs
) == BIT_IOR_EXPR
2793 && integer_nonzerop (TREE_OPERAND (rhs
, 1)))
2794 record_var_is_nonzero (lhs
, block_nonzero_vars_p
);
2797 /* Look at both sides for pointer dereferences. If we find one, then
2798 the pointer must be nonnull and we can enter that equivalence into
2800 if (flag_delete_null_pointer_checks
)
2801 for (i
= 0; i
< 2; i
++)
2803 tree t
= TREE_OPERAND (stmt
, i
);
2805 /* Strip away any COMPONENT_REFs. */
2806 while (TREE_CODE (t
) == COMPONENT_REF
)
2807 t
= TREE_OPERAND (t
, 0);
2809 /* Now see if this is a pointer dereference. */
2810 if (TREE_CODE (t
) == INDIRECT_REF
)
2812 tree op
= TREE_OPERAND (t
, 0);
2814 /* If the pointer is a SSA variable, then enter new
2815 equivalences into the hash table. */
2816 while (TREE_CODE (op
) == SSA_NAME
)
2818 tree def
= SSA_NAME_DEF_STMT (op
);
2820 record_var_is_nonzero (op
, block_nonzero_vars_p
);
2822 /* And walk up the USE-DEF chains noting other SSA_NAMEs
2823 which are known to have a nonzero value. */
2825 && TREE_CODE (def
) == MODIFY_EXPR
2826 && TREE_CODE (TREE_OPERAND (def
, 1)) == NOP_EXPR
)
2827 op
= TREE_OPERAND (TREE_OPERAND (def
, 1), 0);
2834 /* A memory store, even an aliased store, creates a useful
2835 equivalence. By exchanging the LHS and RHS, creating suitable
2836 vops and recording the result in the available expression table,
2837 we may be able to expose more redundant loads. */
2838 if (!ann
->has_volatile_ops
2839 && (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
2840 || is_gimple_min_invariant (TREE_OPERAND (stmt
, 1)))
2841 && !is_gimple_reg (lhs
))
2843 tree rhs
= TREE_OPERAND (stmt
, 1);
2847 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
2848 is a constant, we need to adjust the constant to fit into the
2849 type of the LHS. If the LHS is a bitfield and the RHS is not
2850 a constant, then we can not record any equivalences for this
2851 statement since we would need to represent the widening or
2852 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
2853 and should not be necessary if GCC represented bitfields
2855 if (lhs_code
== COMPONENT_REF
2856 && DECL_BIT_FIELD (TREE_OPERAND (lhs
, 1)))
2858 if (TREE_CONSTANT (rhs
))
2859 rhs
= widen_bitfield (rhs
, TREE_OPERAND (lhs
, 1), lhs
);
2863 /* If the value overflowed, then we can not use this equivalence. */
2864 if (rhs
&& ! is_gimple_min_invariant (rhs
))
2870 v_may_def_optype v_may_defs
= V_MAY_DEF_OPS (ann
);
2871 v_must_def_optype v_must_defs
= V_MUST_DEF_OPS (ann
);
2873 /* Build a new statement with the RHS and LHS exchanged. */
2874 new = build (MODIFY_EXPR
, TREE_TYPE (stmt
), rhs
, lhs
);
2876 /* Get an annotation and set up the real operands. */
2878 get_stmt_operands (new);
2880 /* Clear out the virtual operands on the new statement, we are
2881 going to set them explicitly below. */
2883 remove_v_may_defs (new);
2884 remove_v_must_defs (new);
2886 start_ssa_stmt_operands (new);
2887 /* For each VDEF on the original statement, we want to create a
2888 VUSE of the V_MAY_DEF result or V_MUST_DEF op on the new
2890 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
2892 tree op
= V_MAY_DEF_RESULT (v_may_defs
, j
);
2896 for (j
= 0; j
< NUM_V_MUST_DEFS (v_must_defs
); j
++)
2898 tree op
= V_MUST_DEF_OP (v_must_defs
, j
);
2902 finalize_ssa_stmt_operands (new);
2904 /* Finally enter the statement into the available expression
2906 lookup_avail_expr (new, block_avail_exprs_p
, true);
2911 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2912 CONST_AND_COPIES. */
2915 cprop_operand (stmt_ann_t ann
, use_operand_p op_p
, varray_type const_and_copies
)
2917 bool may_have_exposed_new_symbols
= false;
2919 tree op
= USE_FROM_PTR (op_p
);
2921 /* If the operand has a known constant value or it is known to be a
2922 copy of some other variable, use the value or copy stored in
2923 CONST_AND_COPIES. */
2924 val
= VARRAY_TREE (const_and_copies
, SSA_NAME_VERSION (op
));
2927 tree op_type
, val_type
;
2929 /* Do not change the base variable in the virtual operand
2930 tables. That would make it impossible to reconstruct
2931 the renamed virtual operand if we later modify this
2932 statement. Also only allow the new value to be an SSA_NAME
2933 for propagation into virtual operands. */
2934 if (!is_gimple_reg (op
)
2935 && (get_virtual_var (val
) != get_virtual_var (op
)
2936 || TREE_CODE (val
) != SSA_NAME
))
2939 /* Get the toplevel type of each operand. */
2940 op_type
= TREE_TYPE (op
);
2941 val_type
= TREE_TYPE (val
);
2943 /* While both types are pointers, get the type of the object
2945 while (POINTER_TYPE_P (op_type
) && POINTER_TYPE_P (val_type
))
2947 op_type
= TREE_TYPE (op_type
);
2948 val_type
= TREE_TYPE (val_type
);
2951 /* Make sure underlying types match before propagating a constant by
2952 converting the constant to the proper type. Note that convert may
2953 return a non-gimple expression, in which case we ignore this
2954 propagation opportunity. */
2955 if (TREE_CODE (val
) != SSA_NAME
)
2957 if (!lang_hooks
.types_compatible_p (op_type
, val_type
))
2959 val
= fold_convert (TREE_TYPE (op
), val
);
2960 if (!is_gimple_min_invariant (val
))
2965 /* Certain operands are not allowed to be copy propagated due
2966 to their interaction with exception handling and some GCC
2968 else if (!may_propagate_copy (op
, val
))
2972 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2974 fprintf (dump_file
, " Replaced '");
2975 print_generic_expr (dump_file
, op
, dump_flags
);
2976 fprintf (dump_file
, "' with %s '",
2977 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
2978 print_generic_expr (dump_file
, val
, dump_flags
);
2979 fprintf (dump_file
, "'\n");
2982 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2983 that we may have exposed a new symbol for SSA renaming. */
2984 if (TREE_CODE (val
) == ADDR_EXPR
2985 || (POINTER_TYPE_P (TREE_TYPE (op
))
2986 && is_gimple_min_invariant (val
)))
2987 may_have_exposed_new_symbols
= true;
2989 propagate_value (op_p
, val
);
2991 /* And note that we modified this statement. This is now
2992 safe, even if we changed virtual operands since we will
2993 rescan the statement and rewrite its operands again. */
2996 return may_have_exposed_new_symbols
;
2999 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
3000 known value for that SSA_NAME (or NULL if no value is known).
3002 Propagate values from CONST_AND_COPIES into the uses, vuses and
3003 v_may_def_ops of STMT. */
3006 cprop_into_stmt (tree stmt
, varray_type const_and_copies
)
3008 bool may_have_exposed_new_symbols
= false;
3009 stmt_ann_t ann
= stmt_ann (stmt
);
3010 size_t i
, num_uses
, num_vuses
, num_v_may_defs
;
3012 v_may_def_optype v_may_defs
;
3015 uses
= USE_OPS (ann
);
3016 num_uses
= NUM_USES (uses
);
3017 for (i
= 0; i
< num_uses
; i
++)
3019 use_operand_p op_p
= USE_OP_PTR (uses
, i
);
3020 if (TREE_CODE (USE_FROM_PTR (op_p
)) == SSA_NAME
)
3021 may_have_exposed_new_symbols
3022 |= cprop_operand (ann
, op_p
, const_and_copies
);
3025 vuses
= VUSE_OPS (ann
);
3026 num_vuses
= NUM_VUSES (vuses
);
3027 for (i
= 0; i
< num_vuses
; i
++)
3029 use_operand_p op_p
= VUSE_OP_PTR (vuses
, i
);
3030 if (TREE_CODE (USE_FROM_PTR (op_p
)) == SSA_NAME
)
3031 may_have_exposed_new_symbols
3032 |= cprop_operand (ann
, op_p
, const_and_copies
);
3035 v_may_defs
= V_MAY_DEF_OPS (ann
);
3036 num_v_may_defs
= NUM_V_MAY_DEFS (v_may_defs
);
3037 for (i
= 0; i
< num_v_may_defs
; i
++)
3039 use_operand_p op_p
= V_MAY_DEF_OP_PTR (v_may_defs
, i
);
3040 if (TREE_CODE (USE_FROM_PTR (op_p
)) == SSA_NAME
)
3041 may_have_exposed_new_symbols
3042 |= cprop_operand (ann
, op_p
, const_and_copies
);
3044 return may_have_exposed_new_symbols
;
3048 /* Optimize the statement pointed by iterator SI.
3050 We try to perform some simplistic global redundancy elimination and
3051 constant propagation:
3053 1- To detect global redundancy, we keep track of expressions that have
3054 been computed in this block and its dominators. If we find that the
3055 same expression is computed more than once, we eliminate repeated
3056 computations by using the target of the first one.
3058 2- Constant values and copy assignments. This is used to do very
3059 simplistic constant and copy propagation. When a constant or copy
3060 assignment is found, we map the value on the RHS of the assignment to
3061 the variable in the LHS in the CONST_AND_COPIES table. */
3064 optimize_stmt (struct dom_walk_data
*walk_data
, basic_block bb
,
3065 block_stmt_iterator si
)
3069 bool may_optimize_p
;
3070 bool may_have_exposed_new_symbols
= false;
3071 struct dom_walk_block_data
*bd
3072 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
3074 stmt
= bsi_stmt (si
);
3076 get_stmt_operands (stmt
);
3077 ann
= stmt_ann (stmt
);
3078 opt_stats
.num_stmts
++;
3079 may_have_exposed_new_symbols
= false;
3081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3083 fprintf (dump_file
, "Optimizing statement ");
3084 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
3087 /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
3088 may_have_exposed_new_symbols
= cprop_into_stmt (stmt
, const_and_copies
);
3090 /* If the statement has been modified with constant replacements,
3091 fold its RHS before checking for redundant computations. */
3094 /* Try to fold the statement making sure that STMT is kept
3096 if (fold_stmt (bsi_stmt_ptr (si
)))
3098 stmt
= bsi_stmt (si
);
3099 ann
= stmt_ann (stmt
);
3101 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3103 fprintf (dump_file
, " Folded to: ");
3104 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
3108 /* Constant/copy propagation above may change the set of
3109 virtual operands associated with this statement. Folding
3110 may remove the need for some virtual operands.
3112 Indicate we will need to rescan and rewrite the statement. */
3113 may_have_exposed_new_symbols
= true;
3116 /* Check for redundant computations. Do this optimization only
3117 for assignments that have no volatile ops and conditionals. */
3118 may_optimize_p
= (!ann
->has_volatile_ops
3119 && ((TREE_CODE (stmt
) == RETURN_EXPR
3120 && TREE_OPERAND (stmt
, 0)
3121 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
3122 && ! (TREE_SIDE_EFFECTS
3123 (TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1))))
3124 || (TREE_CODE (stmt
) == MODIFY_EXPR
3125 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt
, 1)))
3126 || TREE_CODE (stmt
) == COND_EXPR
3127 || TREE_CODE (stmt
) == SWITCH_EXPR
));
3130 may_have_exposed_new_symbols
3131 |= eliminate_redundant_computations (walk_data
, stmt
, ann
);
3133 /* Record any additional equivalences created by this statement. */
3134 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
3135 record_equivalences_from_stmt (stmt
,
3141 register_definitions_for_stmt (ann
, &bd
->block_defs
);
3143 /* If STMT is a COND_EXPR and it was modified, then we may know
3144 where it goes. If that is the case, then mark the CFG as altered.
3146 This will cause us to later call remove_unreachable_blocks and
3147 cleanup_tree_cfg when it is safe to do so. It is not safe to
3148 clean things up here since removal of edges and such can trigger
3149 the removal of PHI nodes, which in turn can release SSA_NAMEs to
3152 That's all fine and good, except that once SSA_NAMEs are released
3153 to the manager, we must not call create_ssa_name until all references
3154 to released SSA_NAMEs have been eliminated.
3156 All references to the deleted SSA_NAMEs can not be eliminated until
3157 we remove unreachable blocks.
3159 We can not remove unreachable blocks until after we have completed
3160 any queued jump threading.
3162 We can not complete any queued jump threads until we have taken
3163 appropriate variables out of SSA form. Taking variables out of
3164 SSA form can call create_ssa_name and thus we lose.
3166 Ultimately I suspect we're going to need to change the interface
3167 into the SSA_NAME manager. */
3173 if (TREE_CODE (stmt
) == COND_EXPR
)
3174 val
= COND_EXPR_COND (stmt
);
3175 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
3176 val
= SWITCH_COND (stmt
);
3178 if (val
&& TREE_CODE (val
) == INTEGER_CST
&& find_taken_edge (bb
, val
))
3181 /* If we simplified a statement in such a way as to be shown that it
3182 cannot trap, update the eh information and the cfg to match. */
3183 if (maybe_clean_eh_stmt (stmt
))
3185 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
3186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3187 fprintf (dump_file
, " Flagged to clear EH edges.\n");
3191 if (may_have_exposed_new_symbols
)
3193 if (! bd
->stmts_to_rescan
)
3194 VARRAY_TREE_INIT (bd
->stmts_to_rescan
, 20, "stmts_to_rescan");
3195 VARRAY_PUSH_TREE (bd
->stmts_to_rescan
, bsi_stmt (si
));
3199 /* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
3200 available expression hashtable, then return the LHS from the hash
3203 If INSERT is true, then we also update the available expression
3204 hash table to account for the changes made to STMT. */
3207 update_rhs_and_lookup_avail_expr (tree stmt
, tree new_rhs
,
3208 varray_type
*block_avail_exprs_p
,
3212 tree cached_lhs
= NULL
;
3214 /* Remove the old entry from the hash table. */
3217 struct expr_hash_elt element
;
3219 initialize_hash_element (stmt
, NULL
, &element
);
3220 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
3223 /* Now update the RHS of the assignment. */
3224 TREE_OPERAND (stmt
, 1) = new_rhs
;
3226 /* Now lookup the updated statement in the hash table. */
3227 cached_lhs
= lookup_avail_expr (stmt
, block_avail_exprs_p
, insert
);
3229 /* We have now called lookup_avail_expr twice with two different
3230 versions of this same statement, once in optimize_stmt, once here.
3232 We know the call in optimize_stmt did not find an existing entry
3233 in the hash table, so a new entry was created. At the same time
3234 this statement was pushed onto the BLOCK_AVAIL_EXPRS varray.
3236 If this call failed to find an existing entry on the hash table,
3237 then the new version of this statement was entered into the
3238 hash table. And this statement was pushed onto BLOCK_AVAIL_EXPR
3239 for the second time. So there are two copies on BLOCK_AVAIL_EXPRs
3241 If this call succeeded, we still have one copy of this statement
3242 on the BLOCK_AVAIL_EXPRs varray.
3244 For both cases, we need to pop the most recent entry off the
3245 BLOCK_AVAIL_EXPRs varray. For the case where we never found this
3246 statement in the hash tables, that will leave precisely one
3247 copy of this statement on BLOCK_AVAIL_EXPRs. For the case where
3248 we found a copy of this statement in the second hash table lookup
3249 we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs. */
3251 VARRAY_POP (*block_avail_exprs_p
);
3253 /* And make sure we record the fact that we modified this
3260 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
3261 found, return its LHS. Otherwise insert STMT in the table and return
3264 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
3265 is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
3266 can be removed when we finish processing this block and its children.
3268 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
3269 contains no CALL_EXPR on its RHS and makes no volatile nor
3270 aliased references. */
3273 lookup_avail_expr (tree stmt
, varray_type
*block_avail_exprs_p
, bool insert
)
3278 struct expr_hash_elt
*element
= xcalloc (sizeof (struct expr_hash_elt
), 1);
3280 lhs
= TREE_CODE (stmt
) == MODIFY_EXPR
? TREE_OPERAND (stmt
, 0) : NULL
;
3282 initialize_hash_element (stmt
, lhs
, element
);
3284 /* Don't bother remembering constant assignments and copy operations.
3285 Constants and copy operations are handled by the constant/copy propagator
3286 in optimize_stmt. */
3287 if (TREE_CODE (element
->rhs
) == SSA_NAME
3288 || is_gimple_min_invariant (element
->rhs
))
3294 /* If this is an equality test against zero, see if we have recorded a
3295 nonzero value for the variable in question. */
3296 if ((TREE_CODE (element
->rhs
) == EQ_EXPR
3297 || TREE_CODE (element
->rhs
) == NE_EXPR
)
3298 && TREE_CODE (TREE_OPERAND (element
->rhs
, 0)) == SSA_NAME
3299 && integer_zerop (TREE_OPERAND (element
->rhs
, 1)))
3301 int indx
= SSA_NAME_VERSION (TREE_OPERAND (element
->rhs
, 0));
3303 if (bitmap_bit_p (nonzero_vars
, indx
))
3305 tree t
= element
->rhs
;
3308 if (TREE_CODE (t
) == EQ_EXPR
)
3309 return boolean_false_node
;
3311 return boolean_true_node
;
3315 /* Finally try to find the expression in the main expression hash table. */
3316 slot
= htab_find_slot_with_hash (avail_exprs
, element
, element
->hash
,
3317 (insert
? INSERT
: NO_INSERT
));
3326 *slot
= (void *) element
;
3327 if (! *block_avail_exprs_p
)
3328 VARRAY_TREE_INIT (*block_avail_exprs_p
, 20, "block_avail_exprs");
3329 VARRAY_PUSH_TREE (*block_avail_exprs_p
, stmt
? stmt
: element
->rhs
);
3333 /* Extract the LHS of the assignment so that it can be used as the current
3334 definition of another variable. */
3335 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
3337 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
3338 use the value from the const_and_copies table. */
3339 if (TREE_CODE (lhs
) == SSA_NAME
)
3341 temp
= get_value_for (lhs
, const_and_copies
);
3350 /* Given a condition COND, record into HI_P, LO_P and INVERTED_P the
3351 range of values that result in the conditional having a true value.
3353 Return true if we are successful in extracting a range from COND and
3354 false if we are unsuccessful. */
3357 extract_range_from_cond (tree cond
, tree
*hi_p
, tree
*lo_p
, int *inverted_p
)
3359 tree op1
= TREE_OPERAND (cond
, 1);
3360 tree high
, low
, type
;
3363 /* Experiments have shown that it's rarely, if ever useful to
3364 record ranges for enumerations. Presumably this is due to
3365 the fact that they're rarely used directly. They are typically
3366 cast into an integer type and used that way. */
3367 if (TREE_CODE (TREE_TYPE (op1
)) != INTEGER_TYPE
)
3370 type
= TREE_TYPE (op1
);
3372 switch (TREE_CODE (cond
))
3386 high
= TYPE_MAX_VALUE (type
);
3391 low
= int_const_binop (PLUS_EXPR
, op1
, integer_one_node
, 1);
3392 high
= TYPE_MAX_VALUE (type
);
3398 low
= TYPE_MIN_VALUE (type
);
3403 high
= int_const_binop (MINUS_EXPR
, op1
, integer_one_node
, 1);
3404 low
= TYPE_MIN_VALUE (type
);
3414 *inverted_p
= inverted
;
3418 /* Record a range created by COND for basic block BB. */
3421 record_range (tree cond
, basic_block bb
, varray_type
*vrp_variables_p
)
3423 /* We explicitly ignore NE_EXPRs. They rarely allow for meaningful
3424 range optimizations and significantly complicate the implementation. */
3425 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<'
3426 && TREE_CODE (cond
) != NE_EXPR
3427 && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond
, 1))) == INTEGER_TYPE
)
3429 struct vrp_element
*element
= ggc_alloc (sizeof (struct vrp_element
));
3430 int ssa_version
= SSA_NAME_VERSION (TREE_OPERAND (cond
, 0));
3432 varray_type
*vrp_records_p
3433 = (varray_type
*)&VARRAY_GENERIC_PTR (vrp_data
, ssa_version
);
3435 element
->low
= NULL
;
3436 element
->high
= NULL
;
3437 element
->cond
= cond
;
3440 if (*vrp_records_p
== NULL
)
3442 VARRAY_GENERIC_PTR_INIT (*vrp_records_p
, 2, "vrp records");
3443 VARRAY_GENERIC_PTR (vrp_data
, ssa_version
) = *vrp_records_p
;
3446 VARRAY_PUSH_GENERIC_PTR (*vrp_records_p
, element
);
3447 if (! *vrp_variables_p
)
3448 VARRAY_TREE_INIT (*vrp_variables_p
, 2, "vrp_variables");
3449 VARRAY_PUSH_TREE (*vrp_variables_p
, TREE_OPERAND (cond
, 0));
3453 /* Given a conditional statement IF_STMT, return the assignment 'X = Y'
3454 known to be true depending on which arm of IF_STMT is taken.
3456 Not all conditional statements will result in a useful assignment.
3457 Return NULL_TREE in that case.
3459 Also enter into the available expression table statements of
3466 This allows us to lookup the condition in a dominated block and
3467 get back a constant indicating if the condition is true. */
3469 static struct eq_expr_value
3470 get_eq_expr_value (tree if_stmt
,
3472 varray_type
*block_avail_exprs_p
,
3474 varray_type
*vrp_variables_p
)
3477 struct eq_expr_value retval
;
3479 cond
= COND_EXPR_COND (if_stmt
);
3483 /* If the conditional is a single variable 'X', return 'X = 1' for
3484 the true arm and 'X = 0' on the false arm. */
3485 if (TREE_CODE (cond
) == SSA_NAME
)
3488 retval
.src
= (true_arm
? integer_one_node
: integer_zero_node
);
3492 /* If we have a comparison expression, then record its result into
3493 the available expression table. */
3494 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
3496 tree op0
= TREE_OPERAND (cond
, 0);
3497 tree op1
= TREE_OPERAND (cond
, 1);
3499 /* Special case comparing booleans against a constant as we know
3500 the value of OP0 on both arms of the branch. ie, we can record
3501 an equivalence for OP0 rather than COND. */
3502 if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
3503 && TREE_CODE (op0
) == SSA_NAME
3504 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
3505 && is_gimple_min_invariant (op1
))
3507 if ((TREE_CODE (cond
) == EQ_EXPR
&& true_arm
)
3508 || (TREE_CODE (cond
) == NE_EXPR
&& ! true_arm
))
3514 if (integer_zerop (op1
))
3515 retval
.src
= boolean_true_node
;
3517 retval
.src
= boolean_false_node
;
3523 if (TREE_CODE (op0
) == SSA_NAME
3524 && (is_gimple_min_invariant (op1
) || TREE_CODE (op1
) == SSA_NAME
))
3526 tree inverted
= invert_truthvalue (cond
);
3528 /* When we find an available expression in the hash table, we replace
3529 the expression with the LHS of the statement in the hash table.
3531 So, we want to build statements such as "1 = <condition>" on the
3532 true arm and "0 = <condition>" on the false arm. That way if we
3533 find the expression in the table, we will replace it with its
3534 known constant value. Also insert inversions of the result and
3535 condition into the hash table. */
3538 record_cond (cond
, boolean_true_node
, block_avail_exprs_p
);
3539 record_dominating_conditions (cond
, block_avail_exprs_p
);
3540 record_cond (inverted
, boolean_false_node
, block_avail_exprs_p
);
3542 if (TREE_CONSTANT (op1
))
3543 record_range (cond
, bb
, vrp_variables_p
);
3545 /* If the conditional is of the form 'X == Y', return 'X = Y'
3546 for the true arm. */
3547 if (TREE_CODE (cond
) == EQ_EXPR
)
3557 record_cond (inverted
, boolean_true_node
, block_avail_exprs_p
);
3558 record_dominating_conditions (inverted
, block_avail_exprs_p
);
3559 record_cond (cond
, boolean_false_node
, block_avail_exprs_p
);
3561 if (TREE_CONSTANT (op1
))
3562 record_range (inverted
, bb
, vrp_variables_p
);
3564 /* If the conditional is of the form 'X != Y', return 'X = Y'
3565 for the false arm. */
3566 if (TREE_CODE (cond
) == NE_EXPR
)
3579 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
3580 MODIFY_EXPR statements. We compute a value number for expressions using
3581 the code of the expression and the SSA numbers of its operands. */
3584 avail_expr_hash (const void *p
)
3586 stmt_ann_t ann
= ((struct expr_hash_elt
*)p
)->ann
;
3587 tree rhs
= ((struct expr_hash_elt
*)p
)->rhs
;
3592 /* iterative_hash_expr knows how to deal with any expression and
3593 deals with commutative operators as well, so just use it instead
3594 of duplicating such complexities here. */
3595 val
= iterative_hash_expr (rhs
, val
);
3597 /* If the hash table entry is not associated with a statement, then we
3598 can just hash the expression and not worry about virtual operands
3603 /* Add the SSA version numbers of every vuse operand. This is important
3604 because compound variables like arrays are not renamed in the
3605 operands. Rather, the rename is done on the virtual variable
3606 representing all the elements of the array. */
3607 vuses
= VUSE_OPS (ann
);
3608 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
3609 val
= iterative_hash_expr (VUSE_OP (vuses
, i
), val
);
3615 real_avail_expr_hash (const void *p
)
3617 return ((const struct expr_hash_elt
*)p
)->hash
;
3621 avail_expr_eq (const void *p1
, const void *p2
)
3623 stmt_ann_t ann1
= ((struct expr_hash_elt
*)p1
)->ann
;
3624 tree rhs1
= ((struct expr_hash_elt
*)p1
)->rhs
;
3625 stmt_ann_t ann2
= ((struct expr_hash_elt
*)p2
)->ann
;
3626 tree rhs2
= ((struct expr_hash_elt
*)p2
)->rhs
;
3628 /* If they are the same physical expression, return true. */
3629 if (rhs1
== rhs2
&& ann1
== ann2
)
3632 /* If their codes are not equal, then quit now. */
3633 if (TREE_CODE (rhs1
) != TREE_CODE (rhs2
))
3636 /* In case of a collision, both RHS have to be identical and have the
3637 same VUSE operands. */
3638 if ((TREE_TYPE (rhs1
) == TREE_TYPE (rhs2
)
3639 || lang_hooks
.types_compatible_p (TREE_TYPE (rhs1
), TREE_TYPE (rhs2
)))
3640 && operand_equal_p (rhs1
, rhs2
, OEP_PURE_SAME
))
3642 vuse_optype ops1
= NULL
;
3643 vuse_optype ops2
= NULL
;
3644 size_t num_ops1
= 0;
3645 size_t num_ops2
= 0;
3650 ops1
= VUSE_OPS (ann1
);
3651 num_ops1
= NUM_VUSES (ops1
);
3656 ops2
= VUSE_OPS (ann2
);
3657 num_ops2
= NUM_VUSES (ops2
);
3660 /* If the number of virtual uses is different, then we consider
3662 if (num_ops1
!= num_ops2
)
3665 for (i
= 0; i
< num_ops1
; i
++)
3666 if (VUSE_OP (ops1
, i
) != VUSE_OP (ops2
, i
))
3669 #ifdef ENABLE_CHECKING
3670 if (((struct expr_hash_elt
*)p1
)->hash
3671 != ((struct expr_hash_elt
*)p2
)->hash
)
3680 /* Given STMT and a pointer to the block local definitions BLOCK_DEFS_P,
3681 register register all objects set by this statement into BLOCK_DEFS_P
3685 register_definitions_for_stmt (stmt_ann_t ann
, varray_type
*block_defs_p
)
3688 v_may_def_optype v_may_defs
;
3689 v_must_def_optype v_must_defs
;
3692 defs
= DEF_OPS (ann
);
3693 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
3695 tree def
= DEF_OP (defs
, i
);
3697 /* FIXME: We shouldn't be registering new defs if the variable
3698 doesn't need to be renamed. */
3699 register_new_def (def
, block_defs_p
);
3702 /* Register new virtual definitions made by the statement. */
3703 v_may_defs
= V_MAY_DEF_OPS (ann
);
3704 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
3706 /* FIXME: We shouldn't be registering new defs if the variable
3707 doesn't need to be renamed. */
3708 register_new_def (V_MAY_DEF_RESULT (v_may_defs
, i
), block_defs_p
);
3711 /* Register new virtual mustdefs made by the statement. */
3712 v_must_defs
= V_MUST_DEF_OPS (ann
);
3713 for (i
= 0; i
< NUM_V_MUST_DEFS (v_must_defs
); i
++)
3715 /* FIXME: We shouldn't be registering new defs if the variable
3716 doesn't need to be renamed. */
3717 register_new_def (V_MUST_DEF_OP (v_must_defs
, i
), block_defs_p
);