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 /* Statistics for dominator optimizations. */
102 long num_exprs_considered
;
106 /* Value range propagation record. Each time we encounter a conditional
107 of the form SSA_NAME COND CONST we create a new vrp_element to record
108 how the condition affects the possible values SSA_NAME may have.
110 Each record contains the condition tested (COND), and the the range of
111 values the variable may legitimately have if COND is true. Note the
112 range of values may be a smaller range than COND specifies if we have
113 recorded other ranges for this variable. Each record also contains the
114 block in which the range was recorded for invalidation purposes.
116 Note that the current known range is computed lazily. This allows us
117 to avoid the overhead of computing ranges which are never queried.
119 When we encounter a conditional, we look for records which constrain
120 the SSA_NAME used in the condition. In some cases those records allow
121 us to determine the condition's result at compile time. In other cases
122 they may allow us to simplify the condition.
124 We also use value ranges to do things like transform signed div/mod
125 operations into unsigned div/mod or to simplify ABS_EXPRs.
127 Simple experiments have shown these optimizations to not be all that
128 useful on switch statements (much to my surprise). So switch statement
129 optimizations are not performed.
131 Note carefully we do not propagate information through each statement
132 in the block. ie, if we know variable X has a value defined of
133 [0, 25] and we encounter Y = X + 1, we do not track a value range
134 for Y (which would be [1, 26] if we cared). Similarly we do not
135 constrain values as we encounter narrowing typecasts, etc. */
139 /* The highest and lowest values the variable in COND may contain when
140 COND is true. Note this may not necessarily be the same values
141 tested by COND if the same variable was used in earlier conditionals.
143 Note this is computed lazily and thus can be NULL indicating that
144 the values have not been computed yet. */
148 /* The actual conditional we recorded. This is needed since we compute
152 /* The basic block where this record was created. We use this to determine
153 when to remove records. */
157 static struct opt_stats_d opt_stats
;
159 /* This virtual array holds pairs of edges which describe a scheduled
160 edge redirection from jump threading.
162 The first entry in each pair is the edge we are going to redirect.
164 The second entry in each pair is the edge leading to our final
165 destination block. By providing this as an edge rather than the
166 final target block itself we can correctly handle redirections
167 when the target block had PHIs which required edge insertions/splitting
168 to remove the PHIs. */
169 static GTY(()) varray_type redirection_edges
;
171 /* A virtual array holding value range records for the variable identified
172 by the index, SSA_VERSION. */
173 static varray_type vrp_data
;
175 /* Datastructure for block local data used during the dominator walk.
176 We maintain a stack of these as we recursively walk down the
179 struct dom_walk_block_data
181 /* Array of all the expressions entered into the global expression
182 hash table by this block. During finalization we use this array to
183 know what expressions to remove from the global expression hash
185 varray_type avail_exprs
;
187 /* Array of dest, src pairs that need to be restored during finalization
188 into the global const/copies table during finalization. */
189 varray_type const_and_copies
;
191 /* Similarly for the nonzero state of variables that needs to be
192 restored during finalization. */
193 varray_type nonzero_vars
;
195 /* Array of statements we need to rescan during finalization for newly
196 exposed variables. */
197 varray_type stmts_to_rescan
;
199 /* Array of variables which have their values constrained by operations
200 in this basic block. We use this during finalization to know
201 which variables need their VRP data updated. */
202 varray_type vrp_variables
;
204 /* Array of tree pairs used to restore the global currdefs to its
205 original state after completing optimization of a block and its
206 dominator children. */
207 varray_type block_defs
;
216 /* Local functions. */
217 static void optimize_stmt (struct dom_walk_data
*,
219 block_stmt_iterator
);
220 static inline tree
get_value_for (tree
, varray_type table
);
221 static inline void set_value_for (tree
, tree
, varray_type table
);
222 static tree
lookup_avail_expr (tree
, varray_type
*, bool);
223 static struct eq_expr_value
get_eq_expr_value (tree
, int, varray_type
*,
224 basic_block
, varray_type
*);
225 static hashval_t
avail_expr_hash (const void *);
226 static int avail_expr_eq (const void *, const void *);
227 static void htab_statistics (FILE *, htab_t
);
228 static void record_cond (tree
, tree
, varray_type
*);
229 static void record_dominating_conditions (tree
, varray_type
*);
230 static void record_const_or_copy (tree
, tree
, varray_type
*);
231 static void record_equality (tree
, tree
, varray_type
*);
232 static tree
update_rhs_and_lookup_avail_expr (tree
, tree
, varray_type
*,
234 static tree
simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*,
235 tree
, stmt_ann_t
, int);
236 static tree
simplify_cond_and_lookup_avail_expr (tree
, varray_type
*,
238 static tree
simplify_switch_and_lookup_avail_expr (tree
, varray_type
*,
240 static tree
find_equivalent_equality_comparison (tree
);
241 static void record_range (tree
, basic_block
, varray_type
*);
242 static bool extract_range_from_cond (tree
, tree
*, tree
*, int *);
243 static void record_equivalences_from_phis (struct dom_walk_data
*, basic_block
);
244 static void record_equivalences_from_incoming_edge (struct dom_walk_data
*,
246 static bool eliminate_redundant_computations (struct dom_walk_data
*,
248 static void record_equivalences_from_stmt (tree
, varray_type
*, varray_type
*,
250 static void thread_across_edge (struct dom_walk_data
*, edge
);
251 static void dom_opt_finalize_block (struct dom_walk_data
*, basic_block
);
252 static void dom_opt_initialize_block_local_data (struct dom_walk_data
*,
254 static void dom_opt_initialize_block (struct dom_walk_data
*, basic_block
);
255 static void cprop_into_phis (struct dom_walk_data
*, basic_block
);
256 static void remove_local_expressions_from_table (varray_type locals
,
259 static void restore_vars_to_original_value (varray_type locals
,
262 static void restore_currdefs_to_original_value (varray_type locals
,
264 static void register_definitions_for_stmt (stmt_ann_t
, varray_type
*);
265 static void redirect_edges_and_update_ssa_graph (varray_type
);
267 /* Local version of fold that doesn't introduce cruft. */
274 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
275 may have been added by fold, and "useless" type conversions that might
276 now be apparent due to propagation. */
277 STRIP_MAIN_TYPE_NOPS (t
);
278 STRIP_USELESS_TYPE_CONVERSION (t
);
283 /* Return the value associated with variable VAR in TABLE. */
286 get_value_for (tree var
, varray_type table
)
288 return VARRAY_TREE (table
, SSA_NAME_VERSION (var
));
291 /* Associate VALUE to variable VAR in TABLE. */
294 set_value_for (tree var
, tree value
, varray_type table
)
296 VARRAY_TREE (table
, SSA_NAME_VERSION (var
)) = value
;
299 /* REDIRECTION_EDGES contains edge pairs where we want to revector the
300 destination of the first edge to the destination of the second edge.
302 These redirections may significantly change the SSA graph since we
303 allow redirection through blocks with PHI nodes and blocks with
304 real instructions in some cases.
306 This routine will perform the requested redirections and incrementally
307 update the SSA graph.
309 Note in some cases requested redirections may be ignored as they can
310 not be safely implemented. */
313 redirect_edges_and_update_ssa_graph (varray_type redirection_edges
)
318 size_t old_num_referenced_vars
= num_referenced_vars
;
319 bitmap virtuals_to_rename
= BITMAP_XMALLOC ();
321 /* First note any variables which we are going to have to take
322 out of SSA form as well as any virtuals which need updating. */
323 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
325 block_stmt_iterator bsi
;
330 e
= VARRAY_EDGE (redirection_edges
, i
);
331 tgt
= VARRAY_EDGE (redirection_edges
, i
+ 1)->dest
;
333 /* All variables referenced in PHI nodes we bypass must be
335 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
337 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
339 if (is_gimple_reg (PHI_RESULT (phi
)))
340 bitmap_set_bit (vars_to_rename
, var_ann (result
)->uid
);
342 bitmap_set_bit (virtuals_to_rename
, var_ann (result
)->uid
);
345 /* Any variables set by statements at the start of the block we
346 are bypassing must also be taken our of SSA form. */
347 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
351 v_may_def_optype v_may_defs
;
352 v_must_def_optype v_must_defs
;
353 tree stmt
= bsi_stmt (bsi
);
354 stmt_ann_t ann
= stmt_ann (stmt
);
356 if (TREE_CODE (stmt
) == COND_EXPR
)
359 get_stmt_operands (stmt
);
361 defs
= DEF_OPS (ann
);
362 for (j
= 0; j
< NUM_DEFS (defs
); j
++)
364 tree op
= SSA_NAME_VAR (DEF_OP (defs
, j
));
365 bitmap_set_bit (vars_to_rename
, var_ann (op
)->uid
);
368 v_may_defs
= STMT_V_MAY_DEF_OPS (stmt
);
369 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
371 tree op
= V_MAY_DEF_RESULT (v_may_defs
, j
);
372 bitmap_set_bit (vars_to_rename
, var_ann (op
)->uid
);
375 v_must_defs
= STMT_V_MUST_DEF_OPS (stmt
);
376 for (j
= 0; j
< NUM_V_MUST_DEFS (v_must_defs
); j
++)
378 tree op
= V_MUST_DEF_OP (v_must_defs
, j
);
379 bitmap_set_bit (vars_to_rename
, var_ann (op
)->uid
);
383 /* Finally, any variables in PHI nodes at our final destination
384 must also be taken our of SSA form. */
385 for (phi
= phi_nodes (tgt
); phi
; phi
= PHI_CHAIN (phi
))
387 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
389 if (is_gimple_reg (PHI_RESULT (phi
)))
390 bitmap_set_bit (vars_to_rename
, var_ann (result
)->uid
);
392 bitmap_set_bit (virtuals_to_rename
, var_ann (result
)->uid
);
396 /* Take those selected variables out of SSA form. This must be
397 done before we start redirecting edges. */
398 if (bitmap_first_set_bit (vars_to_rename
) >= 0)
399 rewrite_vars_out_of_ssa (vars_to_rename
);
401 /* The out of SSA translation above may split the edge from
402 E->src to E->dest. This could potentially cause us to lose
403 an assignment leading to invalid warnings about uninitialized
404 variables or incorrect code.
406 Luckily, we can detect this by looking at the last statement
407 in E->dest. If it is not a COND_EXPR or SWITCH_EXPR, then
408 the edge was split and instead of E, we want E->dest->succ. */
409 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
411 edge e
= VARRAY_EDGE (redirection_edges
, i
);
412 tree last
= last_stmt (e
->dest
);
415 && TREE_CODE (last
) != COND_EXPR
416 && TREE_CODE (last
) != SWITCH_EXPR
)
420 #ifdef ENABLE_CHECKING
421 /* There should only be a single successor if the
422 original edge was split. */
426 /* Replace the edge in REDIRECTION_EDGES for the
428 VARRAY_EDGE (redirection_edges
, i
) = e
;
432 /* If we created any new variables as part of the out-of-ssa
433 translation, then any jump threads must be invalidated if they
434 bypass a block in which we skipped instructions.
436 This is necessary as instructions which appeared to be NOPS
437 may be necessary after the out-of-ssa translation. */
438 if (num_referenced_vars
!= old_num_referenced_vars
)
440 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
442 block_stmt_iterator bsi
;
445 e
= VARRAY_EDGE (redirection_edges
, i
);
446 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
448 tree stmt
= bsi_stmt (bsi
);
450 if (IS_EMPTY_STMT (stmt
)
451 || TREE_CODE (stmt
) == LABEL_EXPR
)
454 if (TREE_CODE (stmt
) == COND_EXPR
)
457 /* Invalidate the jump thread. */
458 VARRAY_EDGE (redirection_edges
, i
) = NULL
;
459 VARRAY_EDGE (redirection_edges
, i
+ 1) = NULL
;
465 /* Now redirect the edges. */
466 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
471 e
= VARRAY_EDGE (redirection_edges
, i
);
475 tgt
= VARRAY_EDGE (redirection_edges
, i
+ 1)->dest
;
478 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
479 fprintf (dump_file
, " Threaded jump %d --> %d to %d\n",
480 e
->src
->index
, e
->dest
->index
, tgt
->index
);
484 e
= redirect_edge_and_branch (e
, tgt
);
485 PENDING_STMT (e
) = NULL_TREE
;
487 /* Updating the dominance information would be nontrivial. */
488 free_dominance_info (CDI_DOMINATORS
);
490 if ((dump_file
&& (dump_flags
& TDF_DETAILS
))
492 fprintf (dump_file
, " basic block %d created\n",
498 VARRAY_CLEAR (redirection_edges
);
500 for (i
= old_num_referenced_vars
; i
< num_referenced_vars
; i
++)
502 bitmap_set_bit (vars_to_rename
, i
);
503 var_ann (referenced_var (i
))->out_of_ssa_tag
= 0;
506 bitmap_a_or_b (vars_to_rename
, vars_to_rename
, virtuals_to_rename
);
508 /* We must remove any PHIs for virtual variables that we are going to
509 re-rename. Hopefully we'll be able to simply update these incrementally
515 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
517 tree result
= PHI_RESULT (phi
);
519 next
= PHI_CHAIN (phi
);
521 if (bitmap_bit_p (virtuals_to_rename
,
522 var_ann (SSA_NAME_VAR (result
))->uid
))
523 remove_phi_node (phi
, NULL
, bb
);
526 BITMAP_XFREE (virtuals_to_rename
);
529 /* Jump threading, redundancy elimination and const/copy propagation.
531 Optimize function FNDECL based on a walk through the dominator tree.
533 This pass may expose new symbols that need to be renamed into SSA. For
534 every new symbol exposed, its corresponding bit will be set in
537 PHASE indicates which dump file from the DUMP_FILES array to use when
538 dumping debugging information. */
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, 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");
562 /* Setup callbacks for the generic dominator tree walker. */
563 walk_data
.walk_stmts_backward
= false;
564 walk_data
.dom_direction
= CDI_DOMINATORS
;
565 walk_data
.initialize_block_local_data
= dom_opt_initialize_block_local_data
;
566 walk_data
.before_dom_children_before_stmts
= dom_opt_initialize_block
;
567 walk_data
.before_dom_children_walk_stmts
= optimize_stmt
;
568 walk_data
.before_dom_children_after_stmts
= cprop_into_phis
;
569 walk_data
.after_dom_children_before_stmts
= NULL
;
570 walk_data
.after_dom_children_walk_stmts
= NULL
;
571 walk_data
.after_dom_children_after_stmts
= dom_opt_finalize_block
;
572 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
573 When we attach more stuff we'll need to fill this out with a real
575 walk_data
.global_data
= NULL
;
576 walk_data
.block_local_data_size
= sizeof (struct dom_walk_block_data
);
578 /* Now initialize the dominator walker. */
579 init_walk_dominator_tree (&walk_data
);
581 /* Reset block_forwardable in each block's annotation. We use that
582 attribute when threading through COND_EXPRs. */
584 bb_ann (bb
)->forwardable
= 1;
586 calculate_dominance_info (CDI_DOMINATORS
);
588 /* If we prove certain blocks are unreachable, then we want to
589 repeat the dominator optimization process as PHI nodes may
590 have turned into copies which allows better propagation of
591 values. So we repeat until we do not identify any new unreachable
595 /* Optimize the dominator tree. */
598 /* Recursively walk the dominator tree optimizing statements. */
599 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
601 /* Wipe the hash tables. */
603 if (VARRAY_ACTIVE_SIZE (redirection_edges
) > 0)
604 redirect_edges_and_update_ssa_graph (redirection_edges
);
606 /* We may have made some basic blocks unreachable, remove them. */
607 cfg_altered
|= delete_unreachable_blocks ();
609 /* If the CFG was altered, then recompute the dominator tree. This
610 is not strictly needed if we only removed unreachable blocks, but
611 may produce better results. If we threaded jumps, then rebuilding
612 the dominator tree is strictly necessary. */
616 calculate_dominance_info (CDI_DOMINATORS
);
619 /* If we are going to iterate (CFG_ALTERED is true), then we must
620 perform any queued renaming before the next iteration. */
622 && bitmap_first_set_bit (vars_to_rename
) >= 0)
625 bitmap_clear (vars_to_rename
);
627 /* The into SSA translation may have created new SSA_NAMES whic
628 affect the size of CONST_AND_COPIES and VRP_DATA. */
629 VARRAY_GROW (const_and_copies
, num_ssa_names
);
630 VARRAY_GROW (vrp_data
, num_ssa_names
);
633 /* Reinitialize the various tables. */
634 bitmap_clear (nonzero_vars
);
635 htab_empty (avail_exprs
);
636 VARRAY_CLEAR (const_and_copies
);
637 VARRAY_CLEAR (vrp_data
);
639 for (i
= 0; i
< num_referenced_vars
; i
++)
640 var_ann (referenced_var (i
))->current_def
= NULL
;
644 /* Remove any unreachable blocks left behind and linearize the CFG. */
647 /* Debugging dumps. */
648 if (dump_file
&& (dump_flags
& TDF_STATS
))
649 dump_dominator_optimization_stats (dump_file
);
651 /* We emptyed the hash table earlier, now delete it completely. */
652 htab_delete (avail_exprs
);
654 /* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
655 CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
656 of the do-while loop above. */
658 /* And finalize the dominator walker. */
659 fini_walk_dominator_tree (&walk_data
);
661 /* Free nonzero_vars. */
662 BITMAP_XFREE (nonzero_vars
);
666 gate_dominator (void)
668 return flag_tree_dom
!= 0;
671 struct tree_opt_pass pass_dominator
=
674 gate_dominator
, /* gate */
675 tree_ssa_dominator_optimize
, /* execute */
678 0, /* static_pass_number */
679 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
680 PROP_cfg
| PROP_ssa
, /* properties_required */
681 0, /* properties_provided */
682 0, /* properties_destroyed */
683 0, /* todo_flags_start */
684 TODO_dump_func
| TODO_rename_vars
685 | TODO_verify_ssa
/* todo_flags_finish */
689 /* We are exiting BB, see if the target block begins with a conditional
690 jump which has a known value when reached via BB. */
693 thread_across_edge (struct dom_walk_data
*walk_data
, edge e
)
695 struct dom_walk_block_data
*bd
696 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
697 block_stmt_iterator bsi
;
701 /* Each PHI creates a temporary equivalence, record them. */
702 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
704 tree src
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
705 tree dst
= PHI_RESULT (phi
);
706 record_const_or_copy (dst
, src
, &bd
->const_and_copies
);
707 register_new_def (dst
, &bd
->block_defs
);
710 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
712 tree lhs
, cached_lhs
;
714 stmt
= bsi_stmt (bsi
);
716 /* Ignore empty statements and labels. */
717 if (IS_EMPTY_STMT (stmt
) || TREE_CODE (stmt
) == LABEL_EXPR
)
720 /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
721 value, then stop our search here. Ideally when we stop a
722 search we stop on a COND_EXPR or SWITCH_EXPR. */
723 if (TREE_CODE (stmt
) != MODIFY_EXPR
724 || TREE_CODE (TREE_OPERAND (stmt
, 0)) != SSA_NAME
)
727 /* At this point we have a statement which assigns an RHS to an
728 SSA_VAR on the LHS. We want to prove that the RHS is already
729 available and that its value is held in the current definition
730 of the LHS -- meaning that this assignment is a NOP when
731 reached via edge E. */
732 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
)
733 cached_lhs
= TREE_OPERAND (stmt
, 1);
735 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
737 lhs
= TREE_OPERAND (stmt
, 0);
739 /* This can happen if we thread around to the start of a loop. */
740 if (lhs
== cached_lhs
)
743 /* If we did not find RHS in the hash table, then try again after
744 temporarily const/copy propagating the operands. */
747 /* Copy the operands. */
748 stmt_ann_t ann
= stmt_ann (stmt
);
749 use_optype uses
= USE_OPS (ann
);
750 vuse_optype vuses
= VUSE_OPS (ann
);
751 tree
*uses_copy
= xcalloc (NUM_USES (uses
), sizeof (tree
));
752 tree
*vuses_copy
= xcalloc (NUM_VUSES (vuses
), sizeof (tree
));
755 /* Make a copy of the uses into USES_COPY, then cprop into
757 for (i
= 0; i
< NUM_USES (uses
); i
++)
761 uses_copy
[i
] = USE_OP (uses
, i
);
762 if (TREE_CODE (USE_OP (uses
, i
)) == SSA_NAME
)
763 tmp
= get_value_for (USE_OP (uses
, i
), const_and_copies
);
765 SET_USE_OP (uses
, i
, tmp
);
768 /* Similarly for virtual uses. */
769 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
773 vuses_copy
[i
] = VUSE_OP (vuses
, i
);
774 if (TREE_CODE (VUSE_OP (vuses
, i
)) == SSA_NAME
)
775 tmp
= get_value_for (VUSE_OP (vuses
, i
), const_and_copies
);
777 SET_VUSE_OP (vuses
, i
, tmp
);
780 /* Try to lookup the new expression. */
781 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
783 /* Restore the statement's original uses/defs. */
784 for (i
= 0; i
< NUM_USES (uses
); i
++)
785 SET_USE_OP (uses
, i
, uses_copy
[i
]);
787 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
788 SET_VUSE_OP (vuses
, i
, vuses_copy
[i
]);
793 /* If we still did not find the expression in the hash table,
794 then we can not ignore this statement. */
799 /* If the expression in the hash table was not assigned to an
800 SSA_NAME, then we can not ignore this statement. */
801 if (TREE_CODE (cached_lhs
) != SSA_NAME
)
804 /* If we have different underlying variables, then we can not
805 ignore this statement. */
806 if (SSA_NAME_VAR (cached_lhs
) != SSA_NAME_VAR (lhs
))
809 /* If CACHED_LHS does not represent the current value of the undering
810 variable in CACHED_LHS/LHS, then we can not ignore this statement. */
811 if (var_ann (SSA_NAME_VAR (lhs
))->current_def
!= cached_lhs
)
814 /* If we got here, then we can ignore this statement and continue
815 walking through the statements in the block looking for a threadable
818 We want to record an equivalence lhs = cache_lhs so that if
819 the result of this statement is used later we can copy propagate
821 record_const_or_copy (lhs
, cached_lhs
, &bd
->const_and_copies
);
822 register_new_def (lhs
, &bd
->block_defs
);
825 /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
826 arm will be taken. */
828 && (TREE_CODE (stmt
) == COND_EXPR
829 || TREE_CODE (stmt
) == SWITCH_EXPR
))
831 tree cond
, cached_lhs
;
834 /* Do not forward entry edges into the loop. In the case loop
835 has multiple entry edges we may end up in constructing irreducible
837 ??? We may consider forwarding the edges in the case all incoming
838 edges forward to the same destination block. */
839 if (!e
->flags
& EDGE_DFS_BACK
)
841 for (e1
= e
->dest
->pred
; e
; e
= e
->pred_next
)
842 if (e1
->flags
& EDGE_DFS_BACK
)
848 /* Now temporarily cprop the operands and try to find the resulting
849 expression in the hash tables. */
850 if (TREE_CODE (stmt
) == COND_EXPR
)
851 cond
= COND_EXPR_COND (stmt
);
853 cond
= SWITCH_COND (stmt
);
855 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
857 tree dummy_cond
, op0
, op1
;
858 enum tree_code cond_code
;
860 op0
= TREE_OPERAND (cond
, 0);
861 op1
= TREE_OPERAND (cond
, 1);
862 cond_code
= TREE_CODE (cond
);
864 /* Get the current value of both operands. */
865 if (TREE_CODE (op0
) == SSA_NAME
)
867 tree tmp
= get_value_for (op0
, const_and_copies
);
872 if (TREE_CODE (op1
) == SSA_NAME
)
874 tree tmp
= get_value_for (op1
, const_and_copies
);
879 /* Stuff the operator and operands into our dummy conditional
880 expression, creating the dummy conditional if necessary. */
881 dummy_cond
= walk_data
->global_data
;
884 dummy_cond
= build (cond_code
, boolean_type_node
, op0
, op1
);
885 dummy_cond
= build (COND_EXPR
, void_type_node
,
886 dummy_cond
, NULL
, NULL
);
887 walk_data
->global_data
= dummy_cond
;
891 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), cond_code
);
892 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op0
;
893 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1) = op1
;
896 /* If the conditional folds to an invariant, then we are done,
897 otherwise look it up in the hash tables. */
898 cached_lhs
= local_fold (COND_EXPR_COND (dummy_cond
));
899 if (! is_gimple_min_invariant (cached_lhs
))
900 cached_lhs
= lookup_avail_expr (dummy_cond
, NULL
, false);
901 if (!cached_lhs
|| ! is_gimple_min_invariant (cached_lhs
))
903 stmt_ann_t ann
= get_stmt_ann (dummy_cond
);
904 cached_lhs
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
910 /* We can have conditionals which just test the state of a
911 variable rather than use a relational operator. These are
912 simpler to handle. */
913 else if (TREE_CODE (cond
) == SSA_NAME
)
916 cached_lhs
= get_value_for (cached_lhs
, const_and_copies
);
917 if (cached_lhs
&& ! is_gimple_min_invariant (cached_lhs
))
921 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
925 edge taken_edge
= find_taken_edge (e
->dest
, cached_lhs
);
926 basic_block dest
= (taken_edge
? taken_edge
->dest
: NULL
);
931 /* If we have a known destination for the conditional, then
932 we can perform this optimization, which saves at least one
933 conditional jump each time it applies since we get to
934 bypass the conditional at our original destination.
936 Note that we can either thread through a block with PHIs
937 or to a block with PHIs, but not both. At this time the
938 bookkeeping to keep the CFG & SSA up-to-date has proven
942 int saved_forwardable
= bb_ann (e
->src
)->forwardable
;
945 bb_ann (e
->src
)->forwardable
= 0;
946 tmp_edge
= tree_block_forwards_to (dest
);
947 taken_edge
= (tmp_edge
? tmp_edge
: taken_edge
);
948 bb_ann (e
->src
)->forwardable
= saved_forwardable
;
949 VARRAY_PUSH_EDGE (redirection_edges
, e
);
950 VARRAY_PUSH_EDGE (redirection_edges
, taken_edge
);
957 /* Initialize the local stacks.
959 AVAIL_EXPRS stores all the expressions made available in this block.
961 CONST_AND_COPIES stores var/value pairs to restore at the end of this
964 NONZERO_VARS stores the vars which have a nonzero value made in this
967 STMTS_TO_RESCAN is a list of statements we will rescan for operands.
969 VRP_VARIABLES is the list of variables which have had their values
970 constrained by an operation in this block.
972 These stacks are cleared in the finalization routine run for each
976 dom_opt_initialize_block_local_data (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
977 basic_block bb ATTRIBUTE_UNUSED
,
978 bool recycled ATTRIBUTE_UNUSED
)
980 #ifdef ENABLE_CHECKING
981 struct dom_walk_block_data
*bd
982 = (struct dom_walk_block_data
*)VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
984 /* We get cleared memory from the allocator, so if the memory is not
985 cleared, then we are re-using a previously allocated entry. In
986 that case, we can also re-use the underlying virtual arrays. Just
987 make sure we clear them before using them! */
990 if (bd
->avail_exprs
&& VARRAY_ACTIVE_SIZE (bd
->avail_exprs
) > 0)
992 if (bd
->const_and_copies
&& VARRAY_ACTIVE_SIZE (bd
->const_and_copies
) > 0)
994 if (bd
->nonzero_vars
&& VARRAY_ACTIVE_SIZE (bd
->nonzero_vars
) > 0)
996 if (bd
->stmts_to_rescan
&& VARRAY_ACTIVE_SIZE (bd
->stmts_to_rescan
) > 0)
998 if (bd
->vrp_variables
&& VARRAY_ACTIVE_SIZE (bd
->vrp_variables
) > 0)
1000 if (bd
->block_defs
&& VARRAY_ACTIVE_SIZE (bd
->block_defs
) > 0)
1006 /* Initialize local stacks for this optimizer and record equivalences
1007 upon entry to BB. Equivalences can come from the edge traversed to
1008 reach BB or they may come from PHI nodes at the start of BB. */
1011 dom_opt_initialize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
1013 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1014 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1016 record_equivalences_from_incoming_edge (walk_data
, bb
);
1018 /* PHI nodes can create equivalences too. */
1019 record_equivalences_from_phis (walk_data
, bb
);
1022 /* Given an expression EXPR (a relational expression or a statement),
1023 initialize the hash table element pointed by by ELEMENT. */
1026 initialize_hash_element (tree expr
, tree lhs
, struct expr_hash_elt
*element
)
1028 /* Hash table elements may be based on conditional expressions or statements.
1030 For the former case, we have no annotation and we want to hash the
1031 conditional expression. In the latter case we have an annotation and
1032 we want to record the expression the statement evaluates. */
1033 if (TREE_CODE_CLASS (TREE_CODE (expr
)) == '<'
1034 || TREE_CODE (expr
) == TRUTH_NOT_EXPR
)
1036 element
->ann
= NULL
;
1037 element
->rhs
= expr
;
1039 else if (TREE_CODE (expr
) == COND_EXPR
)
1041 element
->ann
= stmt_ann (expr
);
1042 element
->rhs
= COND_EXPR_COND (expr
);
1044 else if (TREE_CODE (expr
) == SWITCH_EXPR
)
1046 element
->ann
= stmt_ann (expr
);
1047 element
->rhs
= SWITCH_COND (expr
);
1049 else if (TREE_CODE (expr
) == RETURN_EXPR
&& TREE_OPERAND (expr
, 0))
1051 element
->ann
= stmt_ann (expr
);
1052 element
->rhs
= TREE_OPERAND (TREE_OPERAND (expr
, 0), 1);
1056 element
->ann
= stmt_ann (expr
);
1057 element
->rhs
= TREE_OPERAND (expr
, 1);
1061 element
->hash
= avail_expr_hash (element
);
1064 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
1065 LIMIT entries left in LOCALs. */
1068 remove_local_expressions_from_table (varray_type locals
,
1075 /* Remove all the expressions made available in this block. */
1076 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1078 struct expr_hash_elt element
;
1079 tree expr
= VARRAY_TOP_TREE (locals
);
1080 VARRAY_POP (locals
);
1082 initialize_hash_element (expr
, NULL
, &element
);
1083 htab_remove_elt_with_hash (table
, &element
, element
.hash
);
1087 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
1088 state, stopping when there are LIMIT entries left in LOCALs. */
1091 restore_nonzero_vars_to_original_value (varray_type locals
,
1098 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1100 tree name
= VARRAY_TOP_TREE (locals
);
1101 VARRAY_POP (locals
);
1102 bitmap_clear_bit (table
, SSA_NAME_VERSION (name
));
1106 /* Use the source/dest pairs in LOCALS to restore TABLE to its original
1107 state, stopping when there are LIMIT entries left in LOCALs. */
1110 restore_vars_to_original_value (varray_type locals
,
1117 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1119 tree prev_value
, dest
;
1121 prev_value
= VARRAY_TOP_TREE (locals
);
1122 VARRAY_POP (locals
);
1123 dest
= VARRAY_TOP_TREE (locals
);
1124 VARRAY_POP (locals
);
1126 set_value_for (dest
, prev_value
, table
);
1130 /* Similar to restore_vars_to_original_value, except that it restores
1131 CURRDEFS to its original value. */
1133 restore_currdefs_to_original_value (varray_type locals
, unsigned limit
)
1138 /* Restore CURRDEFS to its original state. */
1139 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1141 tree tmp
= VARRAY_TOP_TREE (locals
);
1142 tree saved_def
, var
;
1144 VARRAY_POP (locals
);
1146 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
1147 definition of its underlying variable. If we recorded anything
1148 else, it must have been an _DECL node and its current reaching
1149 definition must have been NULL. */
1150 if (TREE_CODE (tmp
) == SSA_NAME
)
1153 var
= SSA_NAME_VAR (saved_def
);
1161 var_ann (var
)->current_def
= saved_def
;
1165 /* We have finished processing the dominator children of BB, perform
1166 any finalization actions in preparation for leaving this node in
1167 the dominator tree. */
1170 dom_opt_finalize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
1172 struct dom_walk_block_data
*bd
1173 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1176 /* If we are at a leaf node in the dominator graph, see if we can thread
1177 the edge from BB through its successor.
1179 Do this before we remove entries from our equivalence tables. */
1181 && ! bb
->succ
->succ_next
1182 && (bb
->succ
->flags
& EDGE_ABNORMAL
) == 0
1183 && (get_immediate_dominator (CDI_DOMINATORS
, bb
->succ
->dest
) != bb
1184 || phi_nodes (bb
->succ
->dest
)))
1187 thread_across_edge (walk_data
, bb
->succ
);
1189 else if ((last
= last_stmt (bb
))
1190 && TREE_CODE (last
) == COND_EXPR
1191 && (TREE_CODE_CLASS (TREE_CODE (COND_EXPR_COND (last
))) == '<'
1192 || TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
)
1194 && (bb
->succ
->flags
& EDGE_ABNORMAL
) == 0
1195 && bb
->succ
->succ_next
1196 && (bb
->succ
->succ_next
->flags
& EDGE_ABNORMAL
) == 0
1197 && ! bb
->succ
->succ_next
->succ_next
)
1199 edge true_edge
, false_edge
;
1200 tree cond
, inverted
= NULL
;
1201 enum tree_code cond_code
;
1203 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1205 cond
= COND_EXPR_COND (last
);
1206 cond_code
= TREE_CODE (cond
);
1208 if (TREE_CODE_CLASS (cond_code
) == '<')
1209 inverted
= invert_truthvalue (cond
);
1211 /* If the THEN arm is the end of a dominator tree or has PHI nodes,
1212 then try to thread through its edge. */
1213 if (get_immediate_dominator (CDI_DOMINATORS
, true_edge
->dest
) != bb
1214 || phi_nodes (true_edge
->dest
))
1216 unsigned avail_expr_limit
;
1217 unsigned const_and_copies_limit
;
1218 unsigned currdefs_limit
;
1221 = bd
->avail_exprs
? VARRAY_ACTIVE_SIZE (bd
->avail_exprs
) : 0;
1222 const_and_copies_limit
1223 = bd
->const_and_copies
? VARRAY_ACTIVE_SIZE (bd
->const_and_copies
)
1226 = bd
->block_defs
? VARRAY_ACTIVE_SIZE (bd
->block_defs
) : 0;
1228 /* Record any equivalences created by following this edge. */
1229 if (TREE_CODE_CLASS (cond_code
) == '<')
1231 record_cond (cond
, boolean_true_node
, &bd
->avail_exprs
);
1232 record_dominating_conditions (cond
, &bd
->avail_exprs
);
1233 record_cond (inverted
, boolean_false_node
, &bd
->avail_exprs
);
1235 else if (cond_code
== SSA_NAME
)
1236 record_const_or_copy (cond
, boolean_true_node
,
1237 &bd
->const_and_copies
);
1239 /* Now thread the edge. */
1240 thread_across_edge (walk_data
, true_edge
);
1242 /* And restore the various tables to their state before
1243 we threaded this edge. */
1244 remove_local_expressions_from_table (bd
->avail_exprs
,
1247 restore_vars_to_original_value (bd
->const_and_copies
,
1248 const_and_copies_limit
,
1250 restore_currdefs_to_original_value (bd
->block_defs
, currdefs_limit
);
1253 /* Similarly for the ELSE arm. */
1254 if (get_immediate_dominator (CDI_DOMINATORS
, false_edge
->dest
) != bb
1255 || phi_nodes (false_edge
->dest
))
1257 /* Record any equivalences created by following this edge. */
1258 if (TREE_CODE_CLASS (cond_code
) == '<')
1260 record_cond (cond
, boolean_false_node
, &bd
->avail_exprs
);
1261 record_cond (inverted
, boolean_true_node
, &bd
->avail_exprs
);
1262 record_dominating_conditions (inverted
, &bd
->avail_exprs
);
1264 else if (cond_code
== SSA_NAME
)
1265 record_const_or_copy (cond
, boolean_false_node
,
1266 &bd
->const_and_copies
);
1268 thread_across_edge (walk_data
, false_edge
);
1270 /* No need to remove local expressions from our tables
1271 or restore vars to their original value as that will
1272 be done immediately below. */
1276 remove_local_expressions_from_table (bd
->avail_exprs
, 0, avail_exprs
);
1277 restore_nonzero_vars_to_original_value (bd
->nonzero_vars
, 0, nonzero_vars
);
1278 restore_vars_to_original_value (bd
->const_and_copies
, 0, const_and_copies
);
1279 restore_currdefs_to_original_value (bd
->block_defs
, 0);
1281 /* Remove VRP records associated with this basic block. They are no
1284 To be efficient, we note which variables have had their values
1285 constrained in this block. So walk over each variable in the
1286 VRP_VARIABLEs array. */
1287 while (bd
->vrp_variables
&& VARRAY_ACTIVE_SIZE (bd
->vrp_variables
) > 0)
1289 tree var
= VARRAY_TOP_TREE (bd
->vrp_variables
);
1291 /* Each variable has a stack of value range records. We want to
1292 invalidate those associated with our basic block. So we walk
1293 the array backwards popping off records associated with our
1294 block. Once we hit a record not associated with our block
1296 varray_type var_vrp_records
= VARRAY_GENERIC_PTR (vrp_data
,
1297 SSA_NAME_VERSION (var
));
1299 while (VARRAY_ACTIVE_SIZE (var_vrp_records
) > 0)
1301 struct vrp_element
*element
1302 = (struct vrp_element
*)VARRAY_TOP_GENERIC_PTR (var_vrp_records
);
1304 if (element
->bb
!= bb
)
1307 VARRAY_POP (var_vrp_records
);
1310 VARRAY_POP (bd
->vrp_variables
);
1313 /* Re-scan operands in all statements that may have had new symbols
1315 while (bd
->stmts_to_rescan
&& VARRAY_ACTIVE_SIZE (bd
->stmts_to_rescan
) > 0)
1317 tree stmt
= VARRAY_TOP_TREE (bd
->stmts_to_rescan
);
1318 VARRAY_POP (bd
->stmts_to_rescan
);
1319 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1323 /* PHI nodes can create equivalences too.
1325 Ignoring any alternatives which are the same as the result, if
1326 all the alternatives are equal, then the PHI node creates an
1329 Additionally, if all the PHI alternatives are known to have a nonzero
1330 value, then the result of this PHI is known to have a nonzero value,
1331 even if we do not know its exact value. */
1334 record_equivalences_from_phis (struct dom_walk_data
*walk_data
, basic_block bb
)
1336 struct dom_walk_block_data
*bd
1337 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1340 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1342 tree lhs
= PHI_RESULT (phi
);
1346 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1348 tree t
= PHI_ARG_DEF (phi
, i
);
1350 if (TREE_CODE (t
) == SSA_NAME
|| is_gimple_min_invariant (t
))
1352 /* Ignore alternatives which are the same as our LHS. */
1353 if (operand_equal_p (lhs
, t
, 0))
1356 /* If we have not processed an alternative yet, then set
1357 RHS to this alternative. */
1360 /* If we have processed an alternative (stored in RHS), then
1361 see if it is equal to this one. If it isn't, then stop
1363 else if (! operand_equal_p (rhs
, t
, 0))
1370 /* If we had no interesting alternatives, then all the RHS alternatives
1371 must have been the same as LHS. */
1375 /* If we managed to iterate through each PHI alternative without
1376 breaking out of the loop, then we have a PHI which may create
1377 a useful equivalence. We do not need to record unwind data for
1378 this, since this is a true assignment and not an equivalence
1379 inferred from a comparison. All uses of this ssa name are dominated
1380 by this assignment, so unwinding just costs time and space. */
1381 if (i
== PHI_NUM_ARGS (phi
)
1382 && may_propagate_copy (lhs
, rhs
))
1383 set_value_for (lhs
, rhs
, const_and_copies
);
1385 /* Now see if we know anything about the nonzero property for the
1386 result of this PHI. */
1387 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1389 if (!PHI_ARG_NONZERO (phi
, i
))
1393 if (i
== PHI_NUM_ARGS (phi
))
1394 bitmap_set_bit (nonzero_vars
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1396 register_new_def (lhs
, &bd
->block_defs
);
1400 /* Record any equivalences created by the incoming edge to BB. If BB
1401 has more than one incoming edge, then no equivalence is created. */
1404 record_equivalences_from_incoming_edge (struct dom_walk_data
*walk_data
,
1409 struct eq_expr_value eq_expr_value
;
1410 tree parent_block_last_stmt
= NULL
;
1411 struct dom_walk_block_data
*bd
1412 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1414 /* If our parent block ended with a control statment, then we may be
1415 able to record some equivalences based on which outgoing edge from
1416 the parent was followed. */
1417 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1420 parent_block_last_stmt
= last_stmt (parent
);
1421 if (parent_block_last_stmt
&& !is_ctrl_stmt (parent_block_last_stmt
))
1422 parent_block_last_stmt
= NULL
;
1425 eq_expr_value
.src
= NULL
;
1426 eq_expr_value
.dst
= NULL
;
1428 /* If we have a single predecessor, then extract EDGE_FLAGS from
1429 our single incoming edge. Otherwise clear EDGE_FLAGS and
1430 PARENT_BLOCK_LAST_STMT since they're not needed. */
1432 && ! bb
->pred
->pred_next
1433 && parent_block_last_stmt
1434 && bb_for_stmt (parent_block_last_stmt
) == bb
->pred
->src
)
1436 edge_flags
= bb
->pred
->flags
;
1441 parent_block_last_stmt
= NULL
;
1444 /* If our parent block ended in a COND_EXPR, add any equivalences
1445 created by the COND_EXPR to the hash table and initialize
1446 EQ_EXPR_VALUE appropriately.
1448 EQ_EXPR_VALUE is an assignment expression created when BB's immediate
1449 dominator ends in a COND_EXPR statement whose predicate is of the form
1450 'VAR == VALUE', where VALUE may be another variable or a constant.
1451 This is used to propagate VALUE on the THEN_CLAUSE of that
1452 conditional. This assignment is inserted in CONST_AND_COPIES so that
1453 the copy and constant propagator can find more propagation
1455 if (parent_block_last_stmt
1456 && bb
->pred
->pred_next
== NULL
1457 && TREE_CODE (parent_block_last_stmt
) == COND_EXPR
1458 && (edge_flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1459 eq_expr_value
= get_eq_expr_value (parent_block_last_stmt
,
1460 (edge_flags
& EDGE_TRUE_VALUE
) != 0,
1463 &bd
->vrp_variables
);
1464 /* Similarly when the parent block ended in a SWITCH_EXPR.
1465 We can only know the value of the switch's condition if the dominator
1466 parent is also the only predecessor of this block. */
1467 else if (parent_block_last_stmt
1468 && bb
->pred
->pred_next
== NULL
1469 && bb
->pred
->src
== parent
1470 && TREE_CODE (parent_block_last_stmt
) == SWITCH_EXPR
)
1472 tree switch_cond
= SWITCH_COND (parent_block_last_stmt
);
1474 /* If the switch's condition is an SSA variable, then we may
1475 know its value at each of the case labels. */
1476 if (TREE_CODE (switch_cond
) == SSA_NAME
)
1478 tree switch_vec
= SWITCH_LABELS (parent_block_last_stmt
);
1479 size_t i
, n
= TREE_VEC_LENGTH (switch_vec
);
1481 tree match_case
= NULL_TREE
;
1483 /* Search the case labels for those whose destination is
1484 the current basic block. */
1485 for (i
= 0; i
< n
; ++i
)
1487 tree elt
= TREE_VEC_ELT (switch_vec
, i
);
1488 if (label_to_block (CASE_LABEL (elt
)) == bb
)
1490 if (++case_count
> 1 || CASE_HIGH (elt
))
1496 /* If we encountered precisely one CASE_LABEL_EXPR and it
1497 was not the default case, or a case range, then we know
1498 the exact value of SWITCH_COND which caused us to get to
1499 this block. Record that equivalence in EQ_EXPR_VALUE. */
1502 && CASE_LOW (match_case
)
1503 && !CASE_HIGH (match_case
))
1505 eq_expr_value
.dst
= switch_cond
;
1506 eq_expr_value
.src
= CASE_LOW (match_case
);
1511 /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
1512 new value for VAR, so that occurrences of VAR can be replaced with
1513 VALUE while re-writing the THEN arm of a COND_EXPR. */
1514 if (eq_expr_value
.src
&& eq_expr_value
.dst
)
1515 record_equality (eq_expr_value
.dst
, eq_expr_value
.src
,
1516 &bd
->const_and_copies
);
1519 /* Dump SSA statistics on FILE. */
1522 dump_dominator_optimization_stats (FILE *file
)
1526 fprintf (file
, "Total number of statements: %6ld\n\n",
1527 opt_stats
.num_stmts
);
1528 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1529 opt_stats
.num_exprs_considered
);
1531 n_exprs
= opt_stats
.num_exprs_considered
;
1535 fprintf (file
, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
1536 opt_stats
.num_re
, PERCENT (opt_stats
.num_re
,
1539 fprintf (file
, "\nHash table statistics:\n");
1541 fprintf (file
, " avail_exprs: ");
1542 htab_statistics (file
, avail_exprs
);
1546 /* Dump SSA statistics on stderr. */
1549 debug_dominator_optimization_stats (void)
1551 dump_dominator_optimization_stats (stderr
);
1555 /* Dump statistics for the hash table HTAB. */
1558 htab_statistics (FILE *file
, htab_t htab
)
1560 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1561 (long) htab_size (htab
),
1562 (long) htab_elements (htab
),
1563 htab_collisions (htab
));
1566 /* Record the fact that VAR has a nonzero value, though we may not know
1567 its exact value. Note that if VAR is already known to have a nonzero
1568 value, then we do nothing. */
1571 record_var_is_nonzero (tree var
, varray_type
*block_nonzero_vars_p
)
1573 int indx
= SSA_NAME_VERSION (var
);
1575 if (bitmap_bit_p (nonzero_vars
, indx
))
1578 /* Mark it in the global table. */
1579 bitmap_set_bit (nonzero_vars
, indx
);
1581 /* Record this SSA_NAME so that we can reset the global table
1582 when we leave this block. */
1583 if (! *block_nonzero_vars_p
)
1584 VARRAY_TREE_INIT (*block_nonzero_vars_p
, 2, "block_nonzero_vars");
1585 VARRAY_PUSH_TREE (*block_nonzero_vars_p
, var
);
1588 /* Enter a statement into the true/false expression hash table indicating
1589 that the condition COND has the value VALUE. */
1592 record_cond (tree cond
, tree value
, varray_type
*block_avail_exprs_p
)
1594 struct expr_hash_elt
*element
= xmalloc (sizeof (struct expr_hash_elt
));
1597 initialize_hash_element (cond
, value
, element
);
1599 slot
= htab_find_slot_with_hash (avail_exprs
, (void *)element
,
1600 element
->hash
, true);
1603 *slot
= (void *) element
;
1604 if (! *block_avail_exprs_p
)
1605 VARRAY_TREE_INIT (*block_avail_exprs_p
, 20, "block_avail_exprs");
1606 VARRAY_PUSH_TREE (*block_avail_exprs_p
, cond
);
1612 /* COND is a condition which is known to be true. Record variants of
1613 COND which must also be true.
1615 For example, if a < b is true, then a <= b must also be true. */
1618 record_dominating_conditions (tree cond
, varray_type
*block_avail_exprs_p
)
1620 switch (TREE_CODE (cond
))
1623 record_cond (build2 (LE_EXPR
, boolean_type_node
,
1624 TREE_OPERAND (cond
, 0),
1625 TREE_OPERAND (cond
, 1)),
1627 block_avail_exprs_p
);
1628 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1629 TREE_OPERAND (cond
, 0),
1630 TREE_OPERAND (cond
, 1)),
1632 block_avail_exprs_p
);
1633 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1634 TREE_OPERAND (cond
, 0),
1635 TREE_OPERAND (cond
, 1)),
1637 block_avail_exprs_p
);
1638 record_cond (build2 (LTGT_EXPR
, boolean_type_node
,
1639 TREE_OPERAND (cond
, 0),
1640 TREE_OPERAND (cond
, 1)),
1642 block_avail_exprs_p
);
1646 record_cond (build2 (GE_EXPR
, boolean_type_node
,
1647 TREE_OPERAND (cond
, 0),
1648 TREE_OPERAND (cond
, 1)),
1650 block_avail_exprs_p
);
1651 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1652 TREE_OPERAND (cond
, 0),
1653 TREE_OPERAND (cond
, 1)),
1655 block_avail_exprs_p
);
1656 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1657 TREE_OPERAND (cond
, 0),
1658 TREE_OPERAND (cond
, 1)),
1660 block_avail_exprs_p
);
1661 record_cond (build2 (LTGT_EXPR
, boolean_type_node
,
1662 TREE_OPERAND (cond
, 0),
1663 TREE_OPERAND (cond
, 1)),
1665 block_avail_exprs_p
);
1670 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1671 TREE_OPERAND (cond
, 0),
1672 TREE_OPERAND (cond
, 1)),
1674 block_avail_exprs_p
);
1678 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1679 TREE_OPERAND (cond
, 0),
1680 TREE_OPERAND (cond
, 1)),
1682 block_avail_exprs_p
);
1683 record_cond (build2 (LE_EXPR
, boolean_type_node
,
1684 TREE_OPERAND (cond
, 0),
1685 TREE_OPERAND (cond
, 1)),
1687 block_avail_exprs_p
);
1688 record_cond (build2 (GE_EXPR
, boolean_type_node
,
1689 TREE_OPERAND (cond
, 0),
1690 TREE_OPERAND (cond
, 1)),
1692 block_avail_exprs_p
);
1695 case UNORDERED_EXPR
:
1696 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1697 TREE_OPERAND (cond
, 0),
1698 TREE_OPERAND (cond
, 1)),
1700 block_avail_exprs_p
);
1701 record_cond (build2 (UNLE_EXPR
, boolean_type_node
,
1702 TREE_OPERAND (cond
, 0),
1703 TREE_OPERAND (cond
, 1)),
1705 block_avail_exprs_p
);
1706 record_cond (build2 (UNGE_EXPR
, boolean_type_node
,
1707 TREE_OPERAND (cond
, 0),
1708 TREE_OPERAND (cond
, 1)),
1710 block_avail_exprs_p
);
1711 record_cond (build2 (UNEQ_EXPR
, boolean_type_node
,
1712 TREE_OPERAND (cond
, 0),
1713 TREE_OPERAND (cond
, 1)),
1715 block_avail_exprs_p
);
1716 record_cond (build2 (UNLT_EXPR
, boolean_type_node
,
1717 TREE_OPERAND (cond
, 0),
1718 TREE_OPERAND (cond
, 1)),
1720 block_avail_exprs_p
);
1721 record_cond (build2 (UNGT_EXPR
, boolean_type_node
,
1722 TREE_OPERAND (cond
, 0),
1723 TREE_OPERAND (cond
, 1)),
1725 block_avail_exprs_p
);
1729 record_cond (build2 (UNLE_EXPR
, boolean_type_node
,
1730 TREE_OPERAND (cond
, 0),
1731 TREE_OPERAND (cond
, 1)),
1733 block_avail_exprs_p
);
1734 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1735 TREE_OPERAND (cond
, 0),
1736 TREE_OPERAND (cond
, 1)),
1738 block_avail_exprs_p
);
1742 record_cond (build2 (UNGE_EXPR
, boolean_type_node
,
1743 TREE_OPERAND (cond
, 0),
1744 TREE_OPERAND (cond
, 1)),
1746 block_avail_exprs_p
);
1747 record_cond (build2 (NE_EXPR
, boolean_type_node
,
1748 TREE_OPERAND (cond
, 0),
1749 TREE_OPERAND (cond
, 1)),
1751 block_avail_exprs_p
);
1755 record_cond (build2 (UNLE_EXPR
, boolean_type_node
,
1756 TREE_OPERAND (cond
, 0),
1757 TREE_OPERAND (cond
, 1)),
1759 block_avail_exprs_p
);
1760 record_cond (build2 (UNGE_EXPR
, boolean_type_node
,
1761 TREE_OPERAND (cond
, 0),
1762 TREE_OPERAND (cond
, 1)),
1764 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
);
1773 record_cond (build2 (ORDERED_EXPR
, boolean_type_node
,
1774 TREE_OPERAND (cond
, 0),
1775 TREE_OPERAND (cond
, 1)),
1777 block_avail_exprs_p
);
1784 /* A helper function for record_const_or_copy and record_equality.
1785 Do the work of recording the value and undo info. */
1788 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
,
1789 varray_type
*block_const_and_copies_p
)
1791 set_value_for (x
, y
, const_and_copies
);
1793 if (!*block_const_and_copies_p
)
1794 VARRAY_TREE_INIT (*block_const_and_copies_p
, 2, "block_const_and_copies");
1795 VARRAY_PUSH_TREE (*block_const_and_copies_p
, x
);
1796 VARRAY_PUSH_TREE (*block_const_and_copies_p
, prev_x
);
1799 /* Record that X is equal to Y in const_and_copies. Record undo
1800 information in the block-local varray. */
1803 record_const_or_copy (tree x
, tree y
, varray_type
*block_const_and_copies_p
)
1805 tree prev_x
= get_value_for (x
, const_and_copies
);
1807 if (TREE_CODE (y
) == SSA_NAME
)
1809 tree tmp
= get_value_for (y
, const_and_copies
);
1814 record_const_or_copy_1 (x
, y
, prev_x
, block_const_and_copies_p
);
1817 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1818 This constrains the cases in which we may treat this as assignment. */
1821 record_equality (tree x
, tree y
, varray_type
*block_const_and_copies_p
)
1823 tree prev_x
= NULL
, prev_y
= NULL
;
1825 if (TREE_CODE (x
) == SSA_NAME
)
1826 prev_x
= get_value_for (x
, const_and_copies
);
1827 if (TREE_CODE (y
) == SSA_NAME
)
1828 prev_y
= get_value_for (y
, const_and_copies
);
1830 /* If one of the previous values is invariant, then use that.
1831 Otherwise it doesn't matter which value we choose, just so
1832 long as we canonicalize on one value. */
1833 if (TREE_INVARIANT (y
))
1835 else if (TREE_INVARIANT (x
))
1836 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1837 else if (prev_x
&& TREE_INVARIANT (prev_x
))
1838 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1842 /* After the swapping, we must have one SSA_NAME. */
1843 if (TREE_CODE (x
) != SSA_NAME
)
1846 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1847 variable compared against zero. If we're honoring signed zeros,
1848 then we cannot record this value unless we know that the value is
1850 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1851 && (TREE_CODE (y
) != REAL_CST
1852 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1855 record_const_or_copy_1 (x
, y
, prev_x
, block_const_and_copies_p
);
1858 /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
1859 hash tables. Try to simplify the RHS using whatever equivalences
1860 we may have recorded.
1862 If we are able to simplify the RHS, then lookup the simplified form in
1863 the hash table and return the result. Otherwise return NULL. */
1866 simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*walk_data
,
1871 tree rhs
= TREE_OPERAND (stmt
, 1);
1872 enum tree_code rhs_code
= TREE_CODE (rhs
);
1874 struct dom_walk_block_data
*bd
1875 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1877 /* If we have lhs = ~x, look and see if we earlier had x = ~y.
1878 In which case we can change this statement to be lhs = y.
1879 Which can then be copy propagated.
1881 Similarly for negation. */
1882 if ((rhs_code
== BIT_NOT_EXPR
|| rhs_code
== NEGATE_EXPR
)
1883 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
1885 /* Get the definition statement for our RHS. */
1886 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1888 /* See if the RHS_DEF_STMT has the same form as our statement. */
1889 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
1890 && TREE_CODE (TREE_OPERAND (rhs_def_stmt
, 1)) == rhs_code
)
1892 tree rhs_def_operand
;
1894 rhs_def_operand
= TREE_OPERAND (TREE_OPERAND (rhs_def_stmt
, 1), 0);
1896 /* Verify that RHS_DEF_OPERAND is a suitable SSA variable. */
1897 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
1898 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
1899 result
= update_rhs_and_lookup_avail_expr (stmt
,
1907 /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
1908 If OP is associative, create and fold (y OP C2) OP C1 which
1909 should result in (y OP C3), use that as the RHS for the
1910 assignment. Add minus to this, as we handle it specially below. */
1911 if ((associative_tree_code (rhs_code
) || rhs_code
== MINUS_EXPR
)
1912 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
1913 && is_gimple_min_invariant (TREE_OPERAND (rhs
, 1)))
1915 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1917 /* See if the RHS_DEF_STMT has the same form as our statement. */
1918 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
)
1920 tree rhs_def_rhs
= TREE_OPERAND (rhs_def_stmt
, 1);
1921 enum tree_code rhs_def_code
= TREE_CODE (rhs_def_rhs
);
1923 if (rhs_code
== rhs_def_code
1924 || (rhs_code
== PLUS_EXPR
&& rhs_def_code
== MINUS_EXPR
)
1925 || (rhs_code
== MINUS_EXPR
&& rhs_def_code
== PLUS_EXPR
))
1927 tree def_stmt_op0
= TREE_OPERAND (rhs_def_rhs
, 0);
1928 tree def_stmt_op1
= TREE_OPERAND (rhs_def_rhs
, 1);
1930 if (TREE_CODE (def_stmt_op0
) == SSA_NAME
1931 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0
)
1932 && is_gimple_min_invariant (def_stmt_op1
))
1934 tree outer_const
= TREE_OPERAND (rhs
, 1);
1935 tree type
= TREE_TYPE (TREE_OPERAND (stmt
, 0));
1938 /* Ho hum. So fold will only operate on the outermost
1939 thingy that we give it, so we have to build the new
1940 expression in two pieces. This requires that we handle
1941 combinations of plus and minus. */
1942 if (rhs_def_code
!= rhs_code
)
1944 if (rhs_def_code
== MINUS_EXPR
)
1945 t
= build (MINUS_EXPR
, type
, outer_const
, def_stmt_op1
);
1947 t
= build (MINUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1948 rhs_code
= PLUS_EXPR
;
1950 else if (rhs_def_code
== MINUS_EXPR
)
1951 t
= build (PLUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1953 t
= build (rhs_def_code
, type
, def_stmt_op1
, outer_const
);
1955 t
= build (rhs_code
, type
, def_stmt_op0
, t
);
1958 /* If the result is a suitable looking gimple expression,
1959 then use it instead of the original for STMT. */
1960 if (TREE_CODE (t
) == SSA_NAME
1961 || (TREE_CODE_CLASS (TREE_CODE (t
)) == '1'
1962 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
1963 || ((TREE_CODE_CLASS (TREE_CODE (t
)) == '2'
1964 || TREE_CODE_CLASS (TREE_CODE (t
)) == '<')
1965 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
1966 && is_gimple_val (TREE_OPERAND (t
, 1))))
1967 result
= update_rhs_and_lookup_avail_expr
1968 (stmt
, t
, &bd
->avail_exprs
, ann
, insert
);
1974 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1975 and BIT_AND_EXPR respectively if the first operand is greater
1976 than zero and the second operand is an exact power of two. */
1977 if ((rhs_code
== TRUNC_DIV_EXPR
|| rhs_code
== TRUNC_MOD_EXPR
)
1978 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
1979 && integer_pow2p (TREE_OPERAND (rhs
, 1)))
1982 tree op
= TREE_OPERAND (rhs
, 0);
1984 if (TYPE_UNSIGNED (TREE_TYPE (op
)))
1986 val
= integer_one_node
;
1990 tree dummy_cond
= walk_data
->global_data
;
1994 dummy_cond
= build (GT_EXPR
, boolean_type_node
,
1995 op
, integer_zero_node
);
1996 dummy_cond
= build (COND_EXPR
, void_type_node
,
1997 dummy_cond
, NULL
, NULL
);
1998 walk_data
->global_data
= dummy_cond
;
2002 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), GT_EXPR
);
2003 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
2004 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
2005 = integer_zero_node
;
2007 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
2012 if (val
&& integer_onep (val
))
2015 tree op0
= TREE_OPERAND (rhs
, 0);
2016 tree op1
= TREE_OPERAND (rhs
, 1);
2018 if (rhs_code
== TRUNC_DIV_EXPR
)
2019 t
= build (RSHIFT_EXPR
, TREE_TYPE (op0
), op0
,
2020 build_int_2 (tree_log2 (op1
), 0));
2022 t
= build (BIT_AND_EXPR
, TREE_TYPE (op0
), op0
,
2023 local_fold (build (MINUS_EXPR
, TREE_TYPE (op1
),
2024 op1
, integer_one_node
)));
2026 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
2032 /* Transform ABS (X) into X or -X as appropriate. */
2033 if (rhs_code
== ABS_EXPR
2034 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
2037 tree op
= TREE_OPERAND (rhs
, 0);
2038 tree type
= TREE_TYPE (op
);
2040 if (TYPE_UNSIGNED (type
))
2042 val
= integer_zero_node
;
2046 tree dummy_cond
= walk_data
->global_data
;
2050 dummy_cond
= build (LE_EXPR
, boolean_type_node
,
2051 op
, integer_zero_node
);
2052 dummy_cond
= build (COND_EXPR
, void_type_node
,
2053 dummy_cond
, NULL
, NULL
);
2054 walk_data
->global_data
= dummy_cond
;
2058 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), LE_EXPR
);
2059 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
2060 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
2061 = fold_convert (type
, integer_zero_node
);
2063 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
2069 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), GE_EXPR
);
2070 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
2071 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
2072 = fold_convert (type
, integer_zero_node
);
2074 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
2080 if (integer_zerop (val
))
2081 val
= integer_one_node
;
2082 else if (integer_onep (val
))
2083 val
= integer_zero_node
;
2089 && (integer_onep (val
) || integer_zerop (val
)))
2093 if (integer_onep (val
))
2094 t
= build1 (NEGATE_EXPR
, TREE_TYPE (op
), op
);
2098 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
2104 /* Optimize *"foo" into 'f'. This is done here rather than
2105 in fold to avoid problems with stuff like &*"foo". */
2106 if (TREE_CODE (rhs
) == INDIRECT_REF
|| TREE_CODE (rhs
) == ARRAY_REF
)
2108 tree t
= fold_read_from_constant_string (rhs
);
2111 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
2119 /* COND is a condition of the form:
2121 x == const or x != const
2123 Look back to x's defining statement and see if x is defined as
2127 If const is unchanged if we convert it to type, then we can build
2128 the equivalent expression:
2131 y == const or y != const
2133 Which may allow further optimizations.
2135 Return the equivalent comparison or NULL if no such equivalent comparison
2139 find_equivalent_equality_comparison (tree cond
)
2141 tree op0
= TREE_OPERAND (cond
, 0);
2142 tree op1
= TREE_OPERAND (cond
, 1);
2143 tree def_stmt
= SSA_NAME_DEF_STMT (op0
);
2145 /* OP0 might have been a parameter, so first make sure it
2146 was defined by a MODIFY_EXPR. */
2147 if (def_stmt
&& TREE_CODE (def_stmt
) == MODIFY_EXPR
)
2149 tree def_rhs
= TREE_OPERAND (def_stmt
, 1);
2151 /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
2152 if ((TREE_CODE (def_rhs
) == NOP_EXPR
2153 || TREE_CODE (def_rhs
) == CONVERT_EXPR
)
2154 && TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == SSA_NAME
)
2156 tree def_rhs_inner
= TREE_OPERAND (def_rhs
, 0);
2157 tree def_rhs_inner_type
= TREE_TYPE (def_rhs_inner
);
2160 if (TYPE_PRECISION (def_rhs_inner_type
)
2161 > TYPE_PRECISION (TREE_TYPE (def_rhs
)))
2164 /* What we want to prove is that if we convert OP1 to
2165 the type of the object inside the NOP_EXPR that the
2166 result is still equivalent to SRC.
2168 If that is true, the build and return new equivalent
2169 condition which uses the source of the typecast and the
2170 new constant (which has only changed its type). */
2171 new = build1 (TREE_CODE (def_rhs
), def_rhs_inner_type
, op1
);
2172 new = local_fold (new);
2173 if (is_gimple_val (new) && tree_int_cst_equal (new, op1
))
2174 return build (TREE_CODE (cond
), TREE_TYPE (cond
),
2175 def_rhs_inner
, new);
2181 /* STMT is a COND_EXPR for which we could not trivially determine its
2182 result. This routine attempts to find equivalent forms of the
2183 condition which we may be able to optimize better. It also
2184 uses simple value range propagation to optimize conditionals. */
2187 simplify_cond_and_lookup_avail_expr (tree stmt
,
2188 varray_type
*block_avail_exprs_p
,
2192 tree cond
= COND_EXPR_COND (stmt
);
2194 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
2196 tree op0
= TREE_OPERAND (cond
, 0);
2197 tree op1
= TREE_OPERAND (cond
, 1);
2199 if (TREE_CODE (op0
) == SSA_NAME
&& is_gimple_min_invariant (op1
))
2202 tree low
, high
, cond_low
, cond_high
;
2203 int lowequal
, highequal
, swapped
, no_overlap
, subset
, cond_inverted
;
2204 varray_type vrp_records
;
2205 struct vrp_element
*element
;
2207 /* First see if we have test of an SSA_NAME against a constant
2208 where the SSA_NAME is defined by an earlier typecast which
2209 is irrelevant when performing tests against the given
2211 if (TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
2213 tree new_cond
= find_equivalent_equality_comparison (cond
);
2217 /* Update the statement to use the new equivalent
2219 COND_EXPR_COND (stmt
) = new_cond
;
2222 /* Lookup the condition and return its known value if it
2224 new_cond
= lookup_avail_expr (stmt
, block_avail_exprs_p
,
2229 /* The operands have changed, so update op0 and op1. */
2230 op0
= TREE_OPERAND (cond
, 0);
2231 op1
= TREE_OPERAND (cond
, 1);
2235 /* Consult the value range records for this variable (if they exist)
2236 to see if we can eliminate or simplify this conditional.
2238 Note two tests are necessary to determine no records exist.
2239 First we have to see if the virtual array exists, if it
2240 exists, then we have to check its active size.
2242 Also note the vast majority of conditionals are not testing
2243 a variable which has had its range constrained by an earlier
2244 conditional. So this filter avoids a lot of unnecessary work. */
2245 vrp_records
= VARRAY_GENERIC_PTR (vrp_data
, SSA_NAME_VERSION (op0
));
2246 if (vrp_records
== NULL
)
2249 limit
= VARRAY_ACTIVE_SIZE (vrp_records
);
2251 /* If we have no value range records for this variable, or we are
2252 unable to extract a range for this condition, then there is
2255 || ! extract_range_from_cond (cond
, &cond_high
,
2256 &cond_low
, &cond_inverted
))
2259 /* We really want to avoid unnecessary computations of range
2260 info. So all ranges are computed lazily; this avoids a
2261 lot of unnecessary work. ie, we record the conditional,
2262 but do not process how it constrains the variable's
2263 potential values until we know that processing the condition
2266 However, we do not want to have to walk a potentially long
2267 list of ranges, nor do we want to compute a variable's
2268 range more than once for a given path.
2270 Luckily, each time we encounter a conditional that can not
2271 be otherwise optimized we will end up here and we will
2272 compute the necessary range information for the variable
2273 used in this condition.
2275 Thus you can conclude that there will never be more than one
2276 conditional associated with a variable which has not been
2277 processed. So we never need to merge more than one new
2278 conditional into the current range.
2280 These properties also help us avoid unnecessary work. */
2282 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
, limit
- 1);
2284 if (element
->high
&& element
->low
)
2286 /* The last element has been processed, so there is no range
2287 merging to do, we can simply use the high/low values
2288 recorded in the last element. */
2290 high
= element
->high
;
2294 tree tmp_high
, tmp_low
;
2297 /* The last element has not been processed. Process it now. */
2298 extract_range_from_cond (element
->cond
, &tmp_high
,
2301 /* If this is the only element, then no merging is necessary,
2302 the high/low values from extract_range_from_cond are all
2311 /* Get the high/low value from the previous element. */
2312 struct vrp_element
*prev
2313 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
,
2318 /* Merge in this element's range with the range from the
2321 The low value for the merged range is the maximum of
2322 the previous low value and the low value of this record.
2324 Similarly the high value for the merged range is the
2325 minimum of the previous high value and the high value of
2327 low
= (tree_int_cst_compare (low
, tmp_low
) == 1
2329 high
= (tree_int_cst_compare (high
, tmp_high
) == -1
2333 /* And record the computed range. */
2335 element
->high
= high
;
2339 /* After we have constrained this variable's potential values,
2340 we try to determine the result of the given conditional.
2342 To simplify later tests, first determine if the current
2343 low value is the same low value as the conditional.
2344 Similarly for the current high value and the high value
2345 for the conditional. */
2346 lowequal
= tree_int_cst_equal (low
, cond_low
);
2347 highequal
= tree_int_cst_equal (high
, cond_high
);
2349 if (lowequal
&& highequal
)
2350 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2352 /* To simplify the overlap/subset tests below we may want
2353 to swap the two ranges so that the larger of the two
2354 ranges occurs "first". */
2356 if (tree_int_cst_compare (low
, cond_low
) == 1
2358 && tree_int_cst_compare (cond_high
, high
) == 1))
2371 /* Now determine if there is no overlap in the ranges
2372 or if the second range is a subset of the first range. */
2373 no_overlap
= tree_int_cst_lt (high
, cond_low
);
2374 subset
= tree_int_cst_compare (cond_high
, high
) != 1;
2376 /* If there was no overlap in the ranges, then this conditional
2377 always has a false value (unless we had to invert this
2378 conditional, in which case it always has a true value). */
2380 return (cond_inverted
? boolean_true_node
: boolean_false_node
);
2382 /* If the current range is a subset of the condition's range,
2383 then this conditional always has a true value (unless we
2384 had to invert this conditional, in which case it always
2385 has a true value). */
2386 if (subset
&& swapped
)
2387 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2389 /* We were unable to determine the result of the conditional.
2390 However, we may be able to simplify the conditional. First
2391 merge the ranges in the same manner as range merging above. */
2392 low
= tree_int_cst_compare (low
, cond_low
) == 1 ? low
: cond_low
;
2393 high
= tree_int_cst_compare (high
, cond_high
) == -1 ? high
: cond_high
;
2395 /* If the range has converged to a single point, then turn this
2396 into an equality comparison. */
2397 if (TREE_CODE (cond
) != EQ_EXPR
2398 && TREE_CODE (cond
) != NE_EXPR
2399 && tree_int_cst_equal (low
, high
))
2401 TREE_SET_CODE (cond
, EQ_EXPR
);
2402 TREE_OPERAND (cond
, 1) = high
;
2409 /* STMT is a SWITCH_EXPR for which we could not trivially determine its
2410 result. This routine attempts to find equivalent forms of the
2411 condition which we may be able to optimize better. */
2414 simplify_switch_and_lookup_avail_expr (tree stmt
,
2415 varray_type
*block_avail_exprs_p
,
2419 tree cond
= SWITCH_COND (stmt
);
2422 /* The optimization that we really care about is removing unnecessary
2423 casts. That will let us do much better in propagating the inferred
2424 constant at the switch target. */
2425 if (TREE_CODE (cond
) == SSA_NAME
)
2427 def
= SSA_NAME_DEF_STMT (cond
);
2428 if (TREE_CODE (def
) == MODIFY_EXPR
)
2430 def
= TREE_OPERAND (def
, 1);
2431 if (TREE_CODE (def
) == NOP_EXPR
)
2433 def
= TREE_OPERAND (def
, 0);
2434 to
= TREE_TYPE (cond
);
2435 ti
= TREE_TYPE (def
);
2437 /* If we have an extension that preserves sign, then we
2438 can copy the source value into the switch. */
2439 if (TYPE_UNSIGNED (to
) == TYPE_UNSIGNED (ti
)
2440 && TYPE_PRECISION (to
) >= TYPE_PRECISION (ti
)
2441 && is_gimple_val (def
))
2443 SWITCH_COND (stmt
) = def
;
2446 return lookup_avail_expr (stmt
, block_avail_exprs_p
, insert
);
2455 /* Propagate known constants/copies into PHI nodes of BB's successor
2459 cprop_into_phis (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
2462 cprop_into_successor_phis (bb
, const_and_copies
, nonzero_vars
);
2465 /* Search for redundant computations in STMT. If any are found, then
2466 replace them with the variable holding the result of the computation.
2468 If safe, record this expression into the available expression hash
2472 eliminate_redundant_computations (struct dom_walk_data
*walk_data
,
2473 tree stmt
, stmt_ann_t ann
)
2475 v_may_def_optype v_may_defs
= V_MAY_DEF_OPS (ann
);
2476 tree
*expr_p
, def
= NULL_TREE
;
2479 bool retval
= false;
2480 struct dom_walk_block_data
*bd
2481 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
2483 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2484 def
= TREE_OPERAND (stmt
, 0);
2486 /* Certain expressions on the RHS can be optimized away, but can not
2487 themselves be entered into the hash tables. */
2488 if (ann
->makes_aliased_stores
2490 || TREE_CODE (def
) != SSA_NAME
2491 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
2492 || NUM_V_MAY_DEFS (v_may_defs
) != 0)
2495 /* Check if the expression has been computed before. */
2496 cached_lhs
= lookup_avail_expr (stmt
, &bd
->avail_exprs
, insert
);
2498 /* If this is an assignment and the RHS was not in the hash table,
2499 then try to simplify the RHS and lookup the new RHS in the
2501 if (! cached_lhs
&& TREE_CODE (stmt
) == MODIFY_EXPR
)
2502 cached_lhs
= simplify_rhs_and_lookup_avail_expr (walk_data
,
2506 /* Similarly if this is a COND_EXPR and we did not find its
2507 expression in the hash table, simplify the condition and
2509 else if (! cached_lhs
&& TREE_CODE (stmt
) == COND_EXPR
)
2510 cached_lhs
= simplify_cond_and_lookup_avail_expr (stmt
,
2514 /* Similarly for a SWITCH_EXPR. */
2515 else if (!cached_lhs
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
2516 cached_lhs
= simplify_switch_and_lookup_avail_expr (stmt
,
2521 opt_stats
.num_exprs_considered
++;
2523 /* Get a pointer to the expression we are trying to optimize. */
2524 if (TREE_CODE (stmt
) == COND_EXPR
)
2525 expr_p
= &COND_EXPR_COND (stmt
);
2526 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2527 expr_p
= &SWITCH_COND (stmt
);
2528 else if (TREE_CODE (stmt
) == RETURN_EXPR
&& TREE_OPERAND (stmt
, 0))
2529 expr_p
= &TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
2531 expr_p
= &TREE_OPERAND (stmt
, 1);
2533 /* It is safe to ignore types here since we have already done
2534 type checking in the hashing and equality routines. In fact
2535 type checking here merely gets in the way of constant
2536 propagation. Also, make sure that it is safe to propagate
2537 CACHED_LHS into *EXPR_P. */
2539 && (TREE_CODE (cached_lhs
) != SSA_NAME
2540 || may_propagate_copy (cached_lhs
, *expr_p
)))
2542 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2544 fprintf (dump_file
, " Replaced redundant expr '");
2545 print_generic_expr (dump_file
, *expr_p
, dump_flags
);
2546 fprintf (dump_file
, "' with '");
2547 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
2548 fprintf (dump_file
, "'\n");
2553 #if defined ENABLE_CHECKING
2554 if (TREE_CODE (cached_lhs
) != SSA_NAME
2555 && !is_gimple_min_invariant (cached_lhs
))
2559 if (TREE_CODE (cached_lhs
) == ADDR_EXPR
2560 || (POINTER_TYPE_P (TREE_TYPE (*expr_p
))
2561 && is_gimple_min_invariant (cached_lhs
)))
2564 propagate_tree_value (expr_p
, cached_lhs
);
2570 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
2571 the available expressions table or the const_and_copies table.
2572 Detect and record those equivalences. */
2575 record_equivalences_from_stmt (tree stmt
,
2576 varray_type
*block_avail_exprs_p
,
2577 varray_type
*block_nonzero_vars_p
,
2581 tree lhs
= TREE_OPERAND (stmt
, 0);
2582 enum tree_code lhs_code
= TREE_CODE (lhs
);
2585 if (lhs_code
== SSA_NAME
)
2587 tree rhs
= TREE_OPERAND (stmt
, 1);
2589 /* Strip away any useless type conversions. */
2590 STRIP_USELESS_TYPE_CONVERSION (rhs
);
2592 /* If the RHS of the assignment is a constant or another variable that
2593 may be propagated, register it in the CONST_AND_COPIES table. We
2594 do not need to record unwind data for this, since this is a true
2595 assignment and not an equivalence inferred from a comparison. All
2596 uses of this ssa name are dominated by this assignment, so unwinding
2597 just costs time and space. */
2599 && (TREE_CODE (rhs
) == SSA_NAME
2600 || is_gimple_min_invariant (rhs
)))
2601 set_value_for (lhs
, rhs
, const_and_copies
);
2603 /* alloca never returns zero and the address of a non-weak symbol
2604 is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
2605 stripped as they do not affect this equivalence. */
2606 while (TREE_CODE (rhs
) == NOP_EXPR
2607 || TREE_CODE (rhs
) == CONVERT_EXPR
)
2608 rhs
= TREE_OPERAND (rhs
, 0);
2610 if (alloca_call_p (rhs
)
2611 || (TREE_CODE (rhs
) == ADDR_EXPR
2612 && DECL_P (TREE_OPERAND (rhs
, 0))
2613 && ! DECL_WEAK (TREE_OPERAND (rhs
, 0))))
2614 record_var_is_nonzero (lhs
, block_nonzero_vars_p
);
2616 /* IOR of any value with a nonzero value will result in a nonzero
2617 value. Even if we do not know the exact result recording that
2618 the result is nonzero is worth the effort. */
2619 if (TREE_CODE (rhs
) == BIT_IOR_EXPR
2620 && integer_nonzerop (TREE_OPERAND (rhs
, 1)))
2621 record_var_is_nonzero (lhs
, block_nonzero_vars_p
);
2624 /* Look at both sides for pointer dereferences. If we find one, then
2625 the pointer must be nonnull and we can enter that equivalence into
2627 if (flag_delete_null_pointer_checks
)
2628 for (i
= 0; i
< 2; i
++)
2630 tree t
= TREE_OPERAND (stmt
, i
);
2632 /* Strip away any COMPONENT_REFs. */
2633 while (TREE_CODE (t
) == COMPONENT_REF
)
2634 t
= TREE_OPERAND (t
, 0);
2636 /* Now see if this is a pointer dereference. */
2637 if (TREE_CODE (t
) == INDIRECT_REF
)
2639 tree op
= TREE_OPERAND (t
, 0);
2641 /* If the pointer is a SSA variable, then enter new
2642 equivalences into the hash table. */
2643 while (TREE_CODE (op
) == SSA_NAME
)
2645 tree def
= SSA_NAME_DEF_STMT (op
);
2647 record_var_is_nonzero (op
, block_nonzero_vars_p
);
2649 /* And walk up the USE-DEF chains noting other SSA_NAMEs
2650 which are known to have a nonzero value. */
2652 && TREE_CODE (def
) == MODIFY_EXPR
2653 && TREE_CODE (TREE_OPERAND (def
, 1)) == NOP_EXPR
)
2654 op
= TREE_OPERAND (TREE_OPERAND (def
, 1), 0);
2661 /* A memory store, even an aliased store, creates a useful
2662 equivalence. By exchanging the LHS and RHS, creating suitable
2663 vops and recording the result in the available expression table,
2664 we may be able to expose more redundant loads. */
2665 if (!ann
->has_volatile_ops
2666 && (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
2667 || is_gimple_min_invariant (TREE_OPERAND (stmt
, 1)))
2668 && !is_gimple_reg (lhs
))
2670 tree rhs
= TREE_OPERAND (stmt
, 1);
2674 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
2675 is a constant, we need to adjust the constant to fit into the
2676 type of the LHS. If the LHS is a bitfield and the RHS is not
2677 a constant, then we can not record any equivalences for this
2678 statement since we would need to represent the widening or
2679 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
2680 and should not be necessary if GCC represented bitfields
2682 if (lhs_code
== COMPONENT_REF
2683 && DECL_BIT_FIELD (TREE_OPERAND (lhs
, 1)))
2685 if (TREE_CONSTANT (rhs
))
2686 rhs
= widen_bitfield (rhs
, TREE_OPERAND (lhs
, 1), lhs
);
2690 /* If the value overflowed, then we can not use this equivalence. */
2691 if (rhs
&& ! is_gimple_min_invariant (rhs
))
2697 v_may_def_optype v_may_defs
= V_MAY_DEF_OPS (ann
);
2698 v_must_def_optype v_must_defs
= V_MUST_DEF_OPS (ann
);
2700 /* Build a new statement with the RHS and LHS exchanged. */
2701 new = build (MODIFY_EXPR
, TREE_TYPE (stmt
), rhs
, lhs
);
2703 /* Get an annotation and set up the real operands. */
2705 get_stmt_operands (new);
2707 /* Clear out the virtual operands on the new statement, we are
2708 going to set them explicitly below. */
2710 remove_v_may_defs (new);
2711 remove_v_must_defs (new);
2713 start_ssa_stmt_operands (new);
2714 /* For each VDEF on the original statement, we want to create a
2715 VUSE of the V_MAY_DEF result or V_MUST_DEF op on the new
2717 for (j
= 0; j
< NUM_V_MAY_DEFS (v_may_defs
); j
++)
2719 tree op
= V_MAY_DEF_RESULT (v_may_defs
, j
);
2723 for (j
= 0; j
< NUM_V_MUST_DEFS (v_must_defs
); j
++)
2725 tree op
= V_MUST_DEF_OP (v_must_defs
, j
);
2729 finalize_ssa_stmt_operands (new);
2731 /* Finally enter the statement into the available expression
2733 lookup_avail_expr (new, block_avail_exprs_p
, true);
2738 /* Optimize the statement pointed by iterator SI.
2740 We try to perform some simplistic global redundancy elimination and
2741 constant propagation:
2743 1- To detect global redundancy, we keep track of expressions that have
2744 been computed in this block and its dominators. If we find that the
2745 same expression is computed more than once, we eliminate repeated
2746 computations by using the target of the first one.
2748 2- Constant values and copy assignments. This is used to do very
2749 simplistic constant and copy propagation. When a constant or copy
2750 assignment is found, we map the value on the RHS of the assignment to
2751 the variable in the LHS in the CONST_AND_COPIES table. */
2754 optimize_stmt (struct dom_walk_data
*walk_data
,
2755 basic_block bb ATTRIBUTE_UNUSED
,
2756 block_stmt_iterator si
)
2760 bool may_optimize_p
;
2761 bool may_have_exposed_new_symbols
= false;
2762 struct dom_walk_block_data
*bd
2763 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
2765 stmt
= bsi_stmt (si
);
2767 get_stmt_operands (stmt
);
2768 ann
= stmt_ann (stmt
);
2769 opt_stats
.num_stmts
++;
2770 may_have_exposed_new_symbols
= false;
2772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2774 fprintf (dump_file
, "Optimizing statement ");
2775 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
2778 /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
2779 may_have_exposed_new_symbols
= cprop_into_stmt (stmt
, const_and_copies
);
2781 /* If the statement has been modified with constant replacements,
2782 fold its RHS before checking for redundant computations. */
2785 /* Try to fold the statement making sure that STMT is kept
2787 if (fold_stmt (bsi_stmt_ptr (si
)))
2789 stmt
= bsi_stmt (si
);
2790 ann
= stmt_ann (stmt
);
2792 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2794 fprintf (dump_file
, " Folded to: ");
2795 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
2799 /* Constant/copy propagation above may change the set of
2800 virtual operands associated with this statement. Folding
2801 may remove the need for some virtual operands.
2803 Indicate we will need to rescan and rewrite the statement. */
2804 may_have_exposed_new_symbols
= true;
2807 /* Check for redundant computations. Do this optimization only
2808 for assignments that have no volatile ops and conditionals. */
2809 may_optimize_p
= (!ann
->has_volatile_ops
2810 && ((TREE_CODE (stmt
) == RETURN_EXPR
2811 && TREE_OPERAND (stmt
, 0)
2812 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
2813 && ! (TREE_SIDE_EFFECTS
2814 (TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1))))
2815 || (TREE_CODE (stmt
) == MODIFY_EXPR
2816 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt
, 1)))
2817 || TREE_CODE (stmt
) == COND_EXPR
2818 || TREE_CODE (stmt
) == SWITCH_EXPR
));
2821 may_have_exposed_new_symbols
2822 |= eliminate_redundant_computations (walk_data
, stmt
, ann
);
2824 /* Record any additional equivalences created by this statement. */
2825 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2826 record_equivalences_from_stmt (stmt
,
2832 register_definitions_for_stmt (ann
, &bd
->block_defs
);
2834 /* If STMT is a COND_EXPR and it was modified, then we may know
2835 where it goes. If that is the case, then mark the CFG as altered.
2837 This will cause us to later call remove_unreachable_blocks and
2838 cleanup_tree_cfg when it is safe to do so. It is not safe to
2839 clean things up here since removal of edges and such can trigger
2840 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2843 That's all fine and good, except that once SSA_NAMEs are released
2844 to the manager, we must not call create_ssa_name until all references
2845 to released SSA_NAMEs have been eliminated.
2847 All references to the deleted SSA_NAMEs can not be eliminated until
2848 we remove unreachable blocks.
2850 We can not remove unreachable blocks until after we have completed
2851 any queued jump threading.
2853 We can not complete any queued jump threads until we have taken
2854 appropriate variables out of SSA form. Taking variables out of
2855 SSA form can call create_ssa_name and thus we lose.
2857 Ultimately I suspect we're going to need to change the interface
2858 into the SSA_NAME manager. */
2864 if (TREE_CODE (stmt
) == COND_EXPR
)
2865 val
= COND_EXPR_COND (stmt
);
2866 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2867 val
= SWITCH_COND (stmt
);
2869 if (val
&& TREE_CODE (val
) == INTEGER_CST
2870 && find_taken_edge (bb_for_stmt (stmt
), val
))
2874 if (may_have_exposed_new_symbols
)
2876 if (! bd
->stmts_to_rescan
)
2877 VARRAY_TREE_INIT (bd
->stmts_to_rescan
, 20, "stmts_to_rescan");
2878 VARRAY_PUSH_TREE (bd
->stmts_to_rescan
, bsi_stmt (si
));
2882 /* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
2883 available expression hashtable, then return the LHS from the hash
2886 If INSERT is true, then we also update the available expression
2887 hash table to account for the changes made to STMT. */
2890 update_rhs_and_lookup_avail_expr (tree stmt
, tree new_rhs
,
2891 varray_type
*block_avail_exprs_p
,
2895 tree cached_lhs
= NULL
;
2897 /* Remove the old entry from the hash table. */
2900 struct expr_hash_elt element
;
2902 initialize_hash_element (stmt
, NULL
, &element
);
2903 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
2906 /* Now update the RHS of the assignment. */
2907 TREE_OPERAND (stmt
, 1) = new_rhs
;
2909 /* Now lookup the updated statement in the hash table. */
2910 cached_lhs
= lookup_avail_expr (stmt
, block_avail_exprs_p
, insert
);
2912 /* We have now called lookup_avail_expr twice with two different
2913 versions of this same statement, once in optimize_stmt, once here.
2915 We know the call in optimize_stmt did not find an existing entry
2916 in the hash table, so a new entry was created. At the same time
2917 this statement was pushed onto the BLOCK_AVAIL_EXPRS varray.
2919 If this call failed to find an existing entry on the hash table,
2920 then the new version of this statement was entered into the
2921 hash table. And this statement was pushed onto BLOCK_AVAIL_EXPR
2922 for the second time. So there are two copies on BLOCK_AVAIL_EXPRs
2924 If this call succeeded, we still have one copy of this statement
2925 on the BLOCK_AVAIL_EXPRs varray.
2927 For both cases, we need to pop the most recent entry off the
2928 BLOCK_AVAIL_EXPRs varray. For the case where we never found this
2929 statement in the hash tables, that will leave precisely one
2930 copy of this statement on BLOCK_AVAIL_EXPRs. For the case where
2931 we found a copy of this statement in the second hash table lookup
2932 we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs. */
2934 VARRAY_POP (*block_avail_exprs_p
);
2936 /* And make sure we record the fact that we modified this
2943 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
2944 found, return its LHS. Otherwise insert STMT in the table and return
2947 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
2948 is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
2949 can be removed when we finish processing this block and its children.
2951 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
2952 contains no CALL_EXPR on its RHS and makes no volatile nor
2953 aliased references. */
2956 lookup_avail_expr (tree stmt
, varray_type
*block_avail_exprs_p
, bool insert
)
2961 struct expr_hash_elt
*element
= xcalloc (sizeof (struct expr_hash_elt
), 1);
2963 lhs
= TREE_CODE (stmt
) == MODIFY_EXPR
? TREE_OPERAND (stmt
, 0) : NULL
;
2965 initialize_hash_element (stmt
, lhs
, element
);
2967 /* Don't bother remembering constant assignments and copy operations.
2968 Constants and copy operations are handled by the constant/copy propagator
2969 in optimize_stmt. */
2970 if (TREE_CODE (element
->rhs
) == SSA_NAME
2971 || is_gimple_min_invariant (element
->rhs
))
2977 /* If this is an equality test against zero, see if we have recorded a
2978 nonzero value for the variable in question. */
2979 if ((TREE_CODE (element
->rhs
) == EQ_EXPR
2980 || TREE_CODE (element
->rhs
) == NE_EXPR
)
2981 && TREE_CODE (TREE_OPERAND (element
->rhs
, 0)) == SSA_NAME
2982 && integer_zerop (TREE_OPERAND (element
->rhs
, 1)))
2984 int indx
= SSA_NAME_VERSION (TREE_OPERAND (element
->rhs
, 0));
2986 if (bitmap_bit_p (nonzero_vars
, indx
))
2988 tree t
= element
->rhs
;
2991 if (TREE_CODE (t
) == EQ_EXPR
)
2992 return boolean_false_node
;
2994 return boolean_true_node
;
2998 /* Finally try to find the expression in the main expression hash table. */
2999 slot
= htab_find_slot_with_hash (avail_exprs
, element
, element
->hash
,
3000 (insert
? INSERT
: NO_INSERT
));
3009 *slot
= (void *) element
;
3010 if (! *block_avail_exprs_p
)
3011 VARRAY_TREE_INIT (*block_avail_exprs_p
, 20, "block_avail_exprs");
3012 VARRAY_PUSH_TREE (*block_avail_exprs_p
, stmt
? stmt
: element
->rhs
);
3016 /* Extract the LHS of the assignment so that it can be used as the current
3017 definition of another variable. */
3018 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
3020 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
3021 use the value from the const_and_copies table. */
3022 if (TREE_CODE (lhs
) == SSA_NAME
)
3024 temp
= get_value_for (lhs
, const_and_copies
);
3033 /* Given a condition COND, record into HI_P, LO_P and INVERTED_P the
3034 range of values that result in the conditional having a true value.
3036 Return true if we are successful in extracting a range from COND and
3037 false if we are unsuccessful. */
3040 extract_range_from_cond (tree cond
, tree
*hi_p
, tree
*lo_p
, int *inverted_p
)
3042 tree op1
= TREE_OPERAND (cond
, 1);
3043 tree high
, low
, type
;
3046 /* Experiments have shown that it's rarely, if ever useful to
3047 record ranges for enumerations. Presumably this is due to
3048 the fact that they're rarely used directly. They are typically
3049 cast into an integer type and used that way. */
3050 if (TREE_CODE (TREE_TYPE (op1
)) != INTEGER_TYPE
)
3053 type
= TREE_TYPE (op1
);
3055 switch (TREE_CODE (cond
))
3069 high
= TYPE_MAX_VALUE (type
);
3074 low
= int_const_binop (PLUS_EXPR
, op1
, integer_one_node
, 1);
3075 high
= TYPE_MAX_VALUE (type
);
3081 low
= TYPE_MIN_VALUE (type
);
3086 high
= int_const_binop (MINUS_EXPR
, op1
, integer_one_node
, 1);
3087 low
= TYPE_MIN_VALUE (type
);
3097 *inverted_p
= inverted
;
3101 /* Record a range created by COND for basic block BB. */
3104 record_range (tree cond
, basic_block bb
, varray_type
*vrp_variables_p
)
3106 /* We explicitly ignore NE_EXPRs. They rarely allow for meaningful
3107 range optimizations and significantly complicate the implementation. */
3108 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<'
3109 && TREE_CODE (cond
) != NE_EXPR
3110 && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond
, 1))) == INTEGER_TYPE
)
3112 struct vrp_element
*element
= ggc_alloc (sizeof (struct vrp_element
));
3113 int ssa_version
= SSA_NAME_VERSION (TREE_OPERAND (cond
, 0));
3115 varray_type
*vrp_records_p
3116 = (varray_type
*)&VARRAY_GENERIC_PTR (vrp_data
, ssa_version
);
3118 element
->low
= NULL
;
3119 element
->high
= NULL
;
3120 element
->cond
= cond
;
3123 if (*vrp_records_p
== NULL
)
3125 VARRAY_GENERIC_PTR_INIT (*vrp_records_p
, 2, "vrp records");
3126 VARRAY_GENERIC_PTR (vrp_data
, ssa_version
) = *vrp_records_p
;
3129 VARRAY_PUSH_GENERIC_PTR (*vrp_records_p
, element
);
3130 if (! *vrp_variables_p
)
3131 VARRAY_TREE_INIT (*vrp_variables_p
, 2, "vrp_variables");
3132 VARRAY_PUSH_TREE (*vrp_variables_p
, TREE_OPERAND (cond
, 0));
3136 /* Given a conditional statement IF_STMT, return the assignment 'X = Y'
3137 known to be true depending on which arm of IF_STMT is taken.
3139 Not all conditional statements will result in a useful assignment.
3140 Return NULL_TREE in that case.
3142 Also enter into the available expression table statements of
3149 This allows us to lookup the condition in a dominated block and
3150 get back a constant indicating if the condition is true. */
3152 static struct eq_expr_value
3153 get_eq_expr_value (tree if_stmt
,
3155 varray_type
*block_avail_exprs_p
,
3157 varray_type
*vrp_variables_p
)
3160 struct eq_expr_value retval
;
3162 cond
= COND_EXPR_COND (if_stmt
);
3166 /* If the conditional is a single variable 'X', return 'X = 1' for
3167 the true arm and 'X = 0' on the false arm. */
3168 if (TREE_CODE (cond
) == SSA_NAME
)
3171 retval
.src
= (true_arm
? integer_one_node
: integer_zero_node
);
3175 /* If we have a comparison expression, then record its result into
3176 the available expression table. */
3177 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
3179 tree op0
= TREE_OPERAND (cond
, 0);
3180 tree op1
= TREE_OPERAND (cond
, 1);
3182 /* Special case comparing booleans against a constant as we know
3183 the value of OP0 on both arms of the branch. ie, we can record
3184 an equivalence for OP0 rather than COND. */
3185 if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
3186 && TREE_CODE (op0
) == SSA_NAME
3187 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
3188 && is_gimple_min_invariant (op1
))
3190 if ((TREE_CODE (cond
) == EQ_EXPR
&& true_arm
)
3191 || (TREE_CODE (cond
) == NE_EXPR
&& ! true_arm
))
3197 if (integer_zerop (op1
))
3198 retval
.src
= boolean_true_node
;
3200 retval
.src
= boolean_false_node
;
3206 if (TREE_CODE (op0
) == SSA_NAME
3207 && (is_gimple_min_invariant (op1
) || TREE_CODE (op1
) == SSA_NAME
))
3209 tree inverted
= invert_truthvalue (cond
);
3211 /* When we find an available expression in the hash table, we replace
3212 the expression with the LHS of the statement in the hash table.
3214 So, we want to build statements such as "1 = <condition>" on the
3215 true arm and "0 = <condition>" on the false arm. That way if we
3216 find the expression in the table, we will replace it with its
3217 known constant value. Also insert inversions of the result and
3218 condition into the hash table. */
3221 record_cond (cond
, boolean_true_node
, block_avail_exprs_p
);
3222 record_dominating_conditions (cond
, block_avail_exprs_p
);
3223 record_cond (inverted
, boolean_false_node
, block_avail_exprs_p
);
3225 if (TREE_CONSTANT (op1
))
3226 record_range (cond
, bb
, vrp_variables_p
);
3228 /* If the conditional is of the form 'X == Y', return 'X = Y'
3229 for the true arm. */
3230 if (TREE_CODE (cond
) == EQ_EXPR
)
3240 record_cond (inverted
, boolean_true_node
, block_avail_exprs_p
);
3241 record_dominating_conditions (inverted
, block_avail_exprs_p
);
3242 record_cond (cond
, boolean_false_node
, block_avail_exprs_p
);
3244 if (TREE_CONSTANT (op1
))
3245 record_range (inverted
, bb
, vrp_variables_p
);
3247 /* If the conditional is of the form 'X != Y', return 'X = Y'
3248 for the false arm. */
3249 if (TREE_CODE (cond
) == NE_EXPR
)
3262 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
3263 MODIFY_EXPR statements. We compute a value number for expressions using
3264 the code of the expression and the SSA numbers of its operands. */
3267 avail_expr_hash (const void *p
)
3269 stmt_ann_t ann
= ((struct expr_hash_elt
*)p
)->ann
;
3270 tree rhs
= ((struct expr_hash_elt
*)p
)->rhs
;
3275 /* iterative_hash_expr knows how to deal with any expression and
3276 deals with commutative operators as well, so just use it instead
3277 of duplicating such complexities here. */
3278 val
= iterative_hash_expr (rhs
, val
);
3280 /* If the hash table entry is not associated with a statement, then we
3281 can just hash the expression and not worry about virtual operands
3286 /* Add the SSA version numbers of every vuse operand. This is important
3287 because compound variables like arrays are not renamed in the
3288 operands. Rather, the rename is done on the virtual variable
3289 representing all the elements of the array. */
3290 vuses
= VUSE_OPS (ann
);
3291 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
3292 val
= iterative_hash_expr (VUSE_OP (vuses
, i
), val
);
3299 avail_expr_eq (const void *p1
, const void *p2
)
3301 stmt_ann_t ann1
= ((struct expr_hash_elt
*)p1
)->ann
;
3302 tree rhs1
= ((struct expr_hash_elt
*)p1
)->rhs
;
3303 stmt_ann_t ann2
= ((struct expr_hash_elt
*)p2
)->ann
;
3304 tree rhs2
= ((struct expr_hash_elt
*)p2
)->rhs
;
3306 /* If they are the same physical expression, return true. */
3307 if (rhs1
== rhs2
&& ann1
== ann2
)
3310 /* If their codes are not equal, then quit now. */
3311 if (TREE_CODE (rhs1
) != TREE_CODE (rhs2
))
3314 /* In case of a collision, both RHS have to be identical and have the
3315 same VUSE operands. */
3316 if ((TREE_TYPE (rhs1
) == TREE_TYPE (rhs2
)
3317 || lang_hooks
.types_compatible_p (TREE_TYPE (rhs1
), TREE_TYPE (rhs2
)))
3318 && operand_equal_p (rhs1
, rhs2
, OEP_PURE_SAME
))
3320 vuse_optype ops1
= NULL
;
3321 vuse_optype ops2
= NULL
;
3322 size_t num_ops1
= 0;
3323 size_t num_ops2
= 0;
3328 ops1
= VUSE_OPS (ann1
);
3329 num_ops1
= NUM_VUSES (ops1
);
3334 ops2
= VUSE_OPS (ann2
);
3335 num_ops2
= NUM_VUSES (ops2
);
3338 /* If the number of virtual uses is different, then we consider
3340 if (num_ops1
!= num_ops2
)
3343 for (i
= 0; i
< num_ops1
; i
++)
3344 if (VUSE_OP (ops1
, i
) != VUSE_OP (ops2
, i
))
3347 #ifdef ENABLE_CHECKING
3348 if (((struct expr_hash_elt
*)p1
)->hash
3349 != ((struct expr_hash_elt
*)p2
)->hash
)
3358 /* Given STMT and a pointer to the block local defintions BLOCK_DEFS_P,
3359 register register all objects set by this statement into BLOCK_DEFS_P
3363 register_definitions_for_stmt (stmt_ann_t ann
, varray_type
*block_defs_p
)
3366 v_may_def_optype v_may_defs
;
3367 v_must_def_optype v_must_defs
;
3370 defs
= DEF_OPS (ann
);
3371 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
3373 tree def
= DEF_OP (defs
, i
);
3375 /* FIXME: We shouldn't be registering new defs if the variable
3376 doesn't need to be renamed. */
3377 register_new_def (def
, block_defs_p
);
3380 /* Register new virtual definitions made by the statement. */
3381 v_may_defs
= V_MAY_DEF_OPS (ann
);
3382 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
3384 /* FIXME: We shouldn't be registering new defs if the variable
3385 doesn't need to be renamed. */
3386 register_new_def (V_MAY_DEF_RESULT (v_may_defs
, i
), block_defs_p
);
3389 /* Register new virtual mustdefs made by the statement. */
3390 v_must_defs
= V_MUST_DEF_OPS (ann
);
3391 for (i
= 0; i
< NUM_V_MUST_DEFS (v_must_defs
); i
++)
3393 /* FIXME: We shouldn't be registering new defs if the variable
3394 doesn't need to be renamed. */
3395 register_new_def (V_MUST_DEF_OP (v_must_defs
, i
), block_defs_p
);