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_const_or_copy (tree
, tree
, varray_type
*);
230 static void record_equality (tree
, tree
, varray_type
*);
231 static tree
update_rhs_and_lookup_avail_expr (tree
, tree
, varray_type
*,
233 static tree
simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*,
234 tree
, stmt_ann_t
, int);
235 static tree
simplify_cond_and_lookup_avail_expr (tree
, varray_type
*,
237 static tree
simplify_switch_and_lookup_avail_expr (tree
, varray_type
*,
239 static tree
find_equivalent_equality_comparison (tree
);
240 static void record_range (tree
, basic_block
, varray_type
*);
241 static bool extract_range_from_cond (tree
, tree
*, tree
*, int *);
242 static void record_equivalences_from_phis (struct dom_walk_data
*, basic_block
);
243 static void record_equivalences_from_incoming_edge (struct dom_walk_data
*,
245 static bool eliminate_redundant_computations (struct dom_walk_data
*,
247 static void record_equivalences_from_stmt (tree
, varray_type
*, varray_type
*,
249 static void thread_across_edge (struct dom_walk_data
*, edge
);
250 static void dom_opt_finalize_block (struct dom_walk_data
*, basic_block
);
251 static void dom_opt_initialize_block_local_data (struct dom_walk_data
*,
253 static void dom_opt_initialize_block (struct dom_walk_data
*, basic_block
);
254 static void cprop_into_phis (struct dom_walk_data
*, basic_block
);
255 static void remove_local_expressions_from_table (varray_type locals
,
258 static void restore_vars_to_original_value (varray_type locals
,
261 static void restore_currdefs_to_original_value (varray_type locals
,
263 static void register_definitions_for_stmt (stmt_ann_t
, varray_type
*);
264 static void redirect_edges_and_update_ssa_graph (varray_type
);
266 /* Local version of fold that doesn't introduce cruft. */
273 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
274 may have been added by fold, and "useless" type conversions that might
275 now be apparent due to propagation. */
276 STRIP_MAIN_TYPE_NOPS (t
);
277 STRIP_USELESS_TYPE_CONVERSION (t
);
282 /* Return the value associated with variable VAR in TABLE. */
285 get_value_for (tree var
, varray_type table
)
287 return VARRAY_TREE (table
, SSA_NAME_VERSION (var
));
290 /* Associate VALUE to variable VAR in TABLE. */
293 set_value_for (tree var
, tree value
, varray_type table
)
295 VARRAY_TREE (table
, SSA_NAME_VERSION (var
)) = value
;
298 /* REDIRECTION_EDGES contains edge pairs where we want to revector the
299 destination of the first edge to the destination of the second edge.
301 These redirections may significantly change the SSA graph since we
302 allow redirection through blocks with PHI nodes and blocks with
303 real instructions in some cases.
305 This routine will perform the requested redirections and incrementally
306 update the SSA graph.
308 Note in some cases requested redirections may be ignored as they can
309 not be safely implemented. */
312 redirect_edges_and_update_ssa_graph (varray_type redirection_edges
)
317 size_t old_num_referenced_vars
= num_referenced_vars
;
318 bitmap virtuals_to_rename
= BITMAP_XMALLOC ();
320 /* First note any variables which we are going to have to take
321 out of SSA form as well as any virtuals which need updating. */
322 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
324 block_stmt_iterator bsi
;
329 e
= VARRAY_EDGE (redirection_edges
, i
);
330 tgt
= VARRAY_EDGE (redirection_edges
, i
+ 1)->dest
;
332 /* All variables referenced in PHI nodes we bypass must be
334 for (phi
= phi_nodes (e
->dest
); phi
; phi
= TREE_CHAIN (phi
))
336 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
338 if (is_gimple_reg (PHI_RESULT (phi
)))
339 bitmap_set_bit (vars_to_rename
, var_ann (result
)->uid
);
341 bitmap_set_bit (virtuals_to_rename
, var_ann (result
)->uid
);
344 /* Any variables set by statements at the start of the block we
345 are bypassing must also be taken our of SSA form. */
346 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
351 tree stmt
= bsi_stmt (bsi
);
352 stmt_ann_t ann
= stmt_ann (stmt
);
354 if (TREE_CODE (stmt
) == COND_EXPR
)
357 get_stmt_operands (stmt
);
359 defs
= DEF_OPS (ann
);
360 for (j
= 0; j
< NUM_DEFS (defs
); j
++)
362 tree op
= SSA_NAME_VAR (DEF_OP (defs
, j
));
363 bitmap_set_bit (vars_to_rename
, var_ann (op
)->uid
);
366 vdefs
= VDEF_OPS (ann
);
367 for (j
= 0; j
< NUM_VDEFS (vdefs
); j
++)
369 tree op
= VDEF_RESULT (vdefs
, j
);
370 bitmap_set_bit (virtuals_to_rename
, var_ann (op
)->uid
);
374 /* Finally, any variables in PHI nodes at our final destination
375 must also be taken our of SSA form. */
376 for (phi
= phi_nodes (tgt
); phi
; phi
= TREE_CHAIN (phi
))
378 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
380 if (is_gimple_reg (PHI_RESULT (phi
)))
381 bitmap_set_bit (vars_to_rename
, var_ann (result
)->uid
);
383 bitmap_set_bit (virtuals_to_rename
, var_ann (result
)->uid
);
387 /* Take those selected variables out of SSA form. This must be
388 done before we start redirecting edges. */
389 if (bitmap_first_set_bit (vars_to_rename
) >= 0)
390 rewrite_vars_out_of_ssa (vars_to_rename
);
392 /* The out of SSA translation above may split the edge from
393 E->src to E->dest. This could potentially cause us to lose
394 an assignment leading to invalid warnings about uninitialized
395 variables or incorrect code.
397 Luckily, we can detect this by looking at the last statement
398 in E->dest. If it is not a COND_EXPR or SWITCH_EXPR, then
399 the edge was split and instead of E, we want E->dest->succ. */
400 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
402 edge e
= VARRAY_EDGE (redirection_edges
, i
);
403 tree last
= last_stmt (e
->dest
);
406 && TREE_CODE (last
) != COND_EXPR
407 && TREE_CODE (last
) != SWITCH_EXPR
)
411 #ifdef ENABLE_CHECKING
412 /* There should only be a single successor if the
413 original edge was split. */
417 /* Replace the edge in REDIRECTION_EDGES for the
419 VARRAY_EDGE (redirection_edges
, i
) = e
;
423 /* If we created any new variables as part of the out-of-ssa
424 translation, then any jump threads must be invalidated if they
425 bypass a block in which we skipped instructions.
427 This is necessary as instructions which appeared to be NOPS
428 may be necessary after the out-of-ssa translation. */
429 if (num_referenced_vars
!= old_num_referenced_vars
)
431 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
433 block_stmt_iterator bsi
;
436 e
= VARRAY_EDGE (redirection_edges
, i
);
437 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
439 tree stmt
= bsi_stmt (bsi
);
441 if (IS_EMPTY_STMT (stmt
)
442 || TREE_CODE (stmt
) == LABEL_EXPR
)
445 if (TREE_CODE (stmt
) == COND_EXPR
)
448 /* Invalidate the jump thread. */
449 VARRAY_EDGE (redirection_edges
, i
) = NULL
;
450 VARRAY_EDGE (redirection_edges
, i
+ 1) = NULL
;
456 /* Now redirect the edges. */
457 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
462 e
= VARRAY_EDGE (redirection_edges
, i
);
466 tgt
= VARRAY_EDGE (redirection_edges
, i
+ 1)->dest
;
469 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
470 fprintf (dump_file
, " Threaded jump %d --> %d to %d\n",
471 e
->src
->index
, e
->dest
->index
, tgt
->index
);
475 e
= redirect_edge_and_branch (e
, tgt
);
476 PENDING_STMT (e
) = NULL_TREE
;
478 /* Updating the dominance information would be nontrivial. */
479 free_dominance_info (CDI_DOMINATORS
);
481 if ((dump_file
&& (dump_flags
& TDF_DETAILS
))
483 fprintf (dump_file
, " basic block %d created\n",
489 VARRAY_CLEAR (redirection_edges
);
491 for (i
= old_num_referenced_vars
; i
< num_referenced_vars
; i
++)
493 bitmap_set_bit (vars_to_rename
, i
);
494 var_ann (referenced_var (i
))->out_of_ssa_tag
= 0;
497 bitmap_a_or_b (vars_to_rename
, vars_to_rename
, virtuals_to_rename
);
499 /* We must remove any PHIs for virtual variables that we are going to
500 re-rename. Hopefully we'll be able to simply update these incrementally
506 for (phi
= phi_nodes (bb
); phi
; phi
= next
)
508 tree result
= PHI_RESULT (phi
);
510 next
= TREE_CHAIN (phi
);
512 if (bitmap_bit_p (virtuals_to_rename
,
513 var_ann (SSA_NAME_VAR (result
))->uid
))
514 remove_phi_node (phi
, NULL
, bb
);
517 BITMAP_XFREE (virtuals_to_rename
);
520 /* Jump threading, redundancy elimination and const/copy propagation.
522 Optimize function FNDECL based on a walk through the dominator tree.
524 This pass may expose new symbols that need to be renamed into SSA. For
525 every new symbol exposed, its corresponding bit will be set in
528 PHASE indicates which dump file from the DUMP_FILES array to use when
529 dumping debugging information. */
532 tree_ssa_dominator_optimize (void)
535 struct dom_walk_data walk_data
;
538 for (i
= 0; i
< num_referenced_vars
; i
++)
539 var_ann (referenced_var (i
))->current_def
= NULL
;
541 /* Mark loop edges so we avoid threading across loop boundaries.
542 This may result in transforming natural loop into irreducible
544 mark_dfs_back_edges ();
546 /* Create our hash tables. */
547 avail_exprs
= htab_create (1024, avail_expr_hash
, avail_expr_eq
, free
);
548 VARRAY_TREE_INIT (const_and_copies
, highest_ssa_version
, "const_and_copies");
549 nonzero_vars
= BITMAP_XMALLOC ();
550 VARRAY_EDGE_INIT (redirection_edges
, 20, "redirection_edges");
551 VARRAY_GENERIC_PTR_INIT (vrp_data
, highest_ssa_version
, "vrp_data");
553 /* Setup callbacks for the generic dominator tree walker. */
554 walk_data
.walk_stmts_backward
= false;
555 walk_data
.dom_direction
= CDI_DOMINATORS
;
556 walk_data
.initialize_block_local_data
= dom_opt_initialize_block_local_data
;
557 walk_data
.before_dom_children_before_stmts
= dom_opt_initialize_block
;
558 walk_data
.before_dom_children_walk_stmts
= optimize_stmt
;
559 walk_data
.before_dom_children_after_stmts
= cprop_into_phis
;
560 walk_data
.after_dom_children_before_stmts
= NULL
;
561 walk_data
.after_dom_children_walk_stmts
= NULL
;
562 walk_data
.after_dom_children_after_stmts
= dom_opt_finalize_block
;
563 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
564 When we attach more stuff we'll need to fill this out with a real
566 walk_data
.global_data
= NULL
;
567 walk_data
.block_local_data_size
= sizeof (struct dom_walk_block_data
);
569 /* Now initialize the dominator walker. */
570 init_walk_dominator_tree (&walk_data
);
572 /* Reset block_forwardable in each block's annotation. We use that
573 attribute when threading through COND_EXPRs. */
575 bb_ann (bb
)->forwardable
= 1;
577 calculate_dominance_info (CDI_DOMINATORS
);
579 /* If we prove certain blocks are unreachable, then we want to
580 repeat the dominator optimization process as PHI nodes may
581 have turned into copies which allows better propagation of
582 values. So we repeat until we do not identify any new unreachable
586 /* Optimize the dominator tree. */
589 /* Recursively walk the dominator tree optimizing statements. */
590 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
592 /* Wipe the hash tables. */
594 if (VARRAY_ACTIVE_SIZE (redirection_edges
) > 0)
595 redirect_edges_and_update_ssa_graph (redirection_edges
);
597 /* We may have made some basic blocks unreachable, remove them. */
598 cfg_altered
|= delete_unreachable_blocks ();
600 /* If the CFG was altered, then recompute the dominator tree. This
601 is not strictly needed if we only removed unreachable blocks, but
602 may produce better results. If we threaded jumps, then rebuilding
603 the dominator tree is strictly necessary. */
607 calculate_dominance_info (CDI_DOMINATORS
);
610 /* If we are going to iterate (CFG_ALTERED is true), then we must
611 perform any queued renaming before the next iteration. */
613 && bitmap_first_set_bit (vars_to_rename
) >= 0)
616 bitmap_clear (vars_to_rename
);
618 /* The into SSA translation may have created new SSA_NAMES whic
619 affect the size of CONST_AND_COPIES and VRP_DATA. */
620 VARRAY_GROW (const_and_copies
, highest_ssa_version
);
621 VARRAY_GROW (vrp_data
, highest_ssa_version
);
624 /* Reinitialize the various tables. */
625 bitmap_clear (nonzero_vars
);
626 htab_empty (avail_exprs
);
627 VARRAY_CLEAR (const_and_copies
);
628 VARRAY_CLEAR (vrp_data
);
630 for (i
= 0; i
< num_referenced_vars
; i
++)
631 var_ann (referenced_var (i
))->current_def
= NULL
;
635 /* Remove any unreachable blocks left behind and linearize the CFG. */
638 /* Debugging dumps. */
639 if (dump_file
&& (dump_flags
& TDF_STATS
))
640 dump_dominator_optimization_stats (dump_file
);
642 /* We emptyed the hash table earlier, now delete it completely. */
643 htab_delete (avail_exprs
);
645 /* It is not nocessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
646 CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
647 of the do-while loop above. */
649 /* And finalize the dominator walker. */
650 fini_walk_dominator_tree (&walk_data
);
652 /* Free nonzero_vars. */
653 BITMAP_XFREE (nonzero_vars
);
657 gate_dominator (void)
659 return flag_tree_dom
!= 0;
662 struct tree_opt_pass pass_dominator
=
665 gate_dominator
, /* gate */
666 tree_ssa_dominator_optimize
, /* execute */
669 0, /* static_pass_number */
670 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
671 PROP_cfg
| PROP_ssa
, /* properties_required */
672 0, /* properties_provided */
673 0, /* properties_destroyed */
674 0, /* todo_flags_start */
675 TODO_dump_func
| TODO_rename_vars
676 | TODO_verify_ssa
/* todo_flags_finish */
680 /* We are exiting BB, see if the target block begins with a conditional
681 jump which has a known value when reached via BB. */
684 thread_across_edge (struct dom_walk_data
*walk_data
, edge e
)
686 struct dom_walk_block_data
*bd
687 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
688 block_stmt_iterator bsi
;
692 /* Each PHI creates a temporary equivalence, record them. */
693 for (phi
= phi_nodes (e
->dest
); phi
; phi
= TREE_CHAIN (phi
))
695 tree src
= PHI_ARG_DEF (phi
, phi_arg_from_edge (phi
, e
));
696 tree dst
= PHI_RESULT (phi
);
697 record_const_or_copy (dst
, src
, &bd
->const_and_copies
);
698 register_new_def (dst
, &bd
->block_defs
);
701 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
703 tree lhs
, cached_lhs
;
705 stmt
= bsi_stmt (bsi
);
707 /* Ignore empty statements and labels. */
708 if (IS_EMPTY_STMT (stmt
) || TREE_CODE (stmt
) == LABEL_EXPR
)
711 /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
712 value, then stop our search here. Ideally when we stop a
713 search we stop on a COND_EXPR or SWITCH_EXPR. */
714 if (TREE_CODE (stmt
) != MODIFY_EXPR
715 || TREE_CODE (TREE_OPERAND (stmt
, 0)) != SSA_NAME
)
718 /* At this point we have a statement which assigns an RHS to an
719 SSA_VAR on the LHS. We want to prove that the RHS is already
720 available and that its value is held in the current definition
721 of the LHS -- meaning that this assignment is a NOP when
722 reached via edge E. */
723 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
)
724 cached_lhs
= TREE_OPERAND (stmt
, 1);
726 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
728 lhs
= TREE_OPERAND (stmt
, 0);
730 /* This can happen if we thread around to the start of a loop. */
731 if (lhs
== cached_lhs
)
734 /* If we did not find RHS in the hash table, then try again after
735 temporarily const/copy propagating the operands. */
738 /* Copy the operands. */
739 stmt_ann_t ann
= stmt_ann (stmt
);
740 use_optype uses
= USE_OPS (ann
);
741 vuse_optype vuses
= VUSE_OPS (ann
);
742 tree
*uses_copy
= xcalloc (NUM_USES (uses
), sizeof (tree
));
743 tree
*vuses_copy
= xcalloc (NUM_VUSES (vuses
), sizeof (tree
));
746 /* Make a copy of the uses into USES_COPY, then cprop into
748 for (i
= 0; i
< NUM_USES (uses
); i
++)
752 uses_copy
[i
] = USE_OP (uses
, i
);
753 if (TREE_CODE (USE_OP (uses
, i
)) == SSA_NAME
)
754 tmp
= get_value_for (USE_OP (uses
, i
), const_and_copies
);
756 *USE_OP_PTR (uses
, i
) = tmp
;
759 /* Similarly for virtual uses. */
760 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
764 vuses_copy
[i
] = VUSE_OP (vuses
, i
);
765 if (TREE_CODE (VUSE_OP (vuses
, i
)) == SSA_NAME
)
766 tmp
= get_value_for (VUSE_OP (vuses
, i
), const_and_copies
);
768 VUSE_OP (vuses
, i
) = tmp
;
771 /* Try to lookup the new expression. */
772 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
774 /* Restore the statement's original uses/defs. */
775 for (i
= 0; i
< NUM_USES (uses
); i
++)
776 *USE_OP_PTR (uses
, i
) = uses_copy
[i
];
778 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
779 VUSE_OP (vuses
, i
) = vuses_copy
[i
];
784 /* If we still did not find the expression in the hash table,
785 then we can not ignore this statement. */
790 /* If the expression in the hash table was not assigned to an
791 SSA_NAME, then we can not ignore this statement. */
792 if (TREE_CODE (cached_lhs
) != SSA_NAME
)
795 /* If we have different underlying variables, then we can not
796 ignore this statement. */
797 if (SSA_NAME_VAR (cached_lhs
) != SSA_NAME_VAR (lhs
))
800 /* If CACHED_LHS does not represent the current value of the undering
801 variable in CACHED_LHS/LHS, then we can not ignore this statement. */
802 if (var_ann (SSA_NAME_VAR (lhs
))->current_def
!= cached_lhs
)
805 /* If we got here, then we can ignore this statement and continue
806 walking through the statements in the block looking for a threadable
809 We want to record an equivalence lhs = cache_lhs so that if
810 the result of this statement is used later we can copy propagate
812 record_const_or_copy (lhs
, cached_lhs
, &bd
->const_and_copies
);
813 register_new_def (lhs
, &bd
->block_defs
);
816 /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
817 arm will be taken. */
819 && (TREE_CODE (stmt
) == COND_EXPR
820 || TREE_CODE (stmt
) == SWITCH_EXPR
))
822 tree cond
, cached_lhs
;
825 /* Do not forward entry edges into the loop. In the case loop
826 has multiple entry edges we may end up in constructing irreducible
828 ??? We may consider forwarding the edges in the case all incoming
829 edges forward to the same destination block. */
830 if (!e
->flags
& EDGE_DFS_BACK
)
832 for (e1
= e
->dest
->pred
; e
; e
= e
->pred_next
)
833 if (e1
->flags
& EDGE_DFS_BACK
)
839 /* Now temporarily cprop the operands and try to find the resulting
840 expression in the hash tables. */
841 if (TREE_CODE (stmt
) == COND_EXPR
)
842 cond
= COND_EXPR_COND (stmt
);
844 cond
= SWITCH_COND (stmt
);
846 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
848 tree dummy_cond
, op0
, op1
;
849 enum tree_code cond_code
;
851 op0
= TREE_OPERAND (cond
, 0);
852 op1
= TREE_OPERAND (cond
, 1);
853 cond_code
= TREE_CODE (cond
);
855 /* Get the current value of both operands. */
856 if (TREE_CODE (op0
) == SSA_NAME
)
858 tree tmp
= get_value_for (op0
, const_and_copies
);
863 if (TREE_CODE (op1
) == SSA_NAME
)
865 tree tmp
= get_value_for (op1
, const_and_copies
);
870 /* Stuff the operator and operands into our dummy conditional
871 expression, creating the dummy conditional if necessary. */
872 dummy_cond
= walk_data
->global_data
;
875 dummy_cond
= build (cond_code
, boolean_type_node
, op0
, op1
);
876 dummy_cond
= build (COND_EXPR
, void_type_node
,
877 dummy_cond
, NULL
, NULL
);
878 walk_data
->global_data
= dummy_cond
;
882 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), cond_code
);
883 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op0
;
884 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1) = op1
;
887 /* If the conditional folds to an invariant, then we are done,
888 otherwise look it up in the hash tables. */
889 cached_lhs
= local_fold (COND_EXPR_COND (dummy_cond
));
890 if (! is_gimple_min_invariant (cached_lhs
))
891 cached_lhs
= lookup_avail_expr (dummy_cond
, NULL
, false);
892 if (!cached_lhs
|| ! is_gimple_min_invariant (cached_lhs
))
894 stmt_ann_t ann
= get_stmt_ann (dummy_cond
);
895 cached_lhs
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
901 /* We can have conditionals which just test the state of a
902 variable rather than use a relational operator. These are
903 simpler to handle. */
904 else if (TREE_CODE (cond
) == SSA_NAME
)
907 cached_lhs
= get_value_for (cached_lhs
, const_and_copies
);
908 if (cached_lhs
&& ! is_gimple_min_invariant (cached_lhs
))
912 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
916 edge taken_edge
= find_taken_edge (e
->dest
, cached_lhs
);
917 basic_block dest
= (taken_edge
? taken_edge
->dest
: NULL
);
922 /* If we have a known destination for the conditional, then
923 we can perform this optimization, which saves at least one
924 conditional jump each time it applies since we get to
925 bypass the conditional at our original destination.
927 Note that we can either thread through a block with PHIs
928 or to a block with PHIs, but not both. At this time the
929 bookkeeping to keep the CFG & SSA up-to-date has proven
933 int saved_forwardable
= bb_ann (e
->src
)->forwardable
;
936 bb_ann (e
->src
)->forwardable
= 0;
937 tmp_edge
= tree_block_forwards_to (dest
);
938 taken_edge
= (tmp_edge
? tmp_edge
: taken_edge
);
939 bb_ann (e
->src
)->forwardable
= saved_forwardable
;
940 VARRAY_PUSH_EDGE (redirection_edges
, e
);
941 VARRAY_PUSH_EDGE (redirection_edges
, taken_edge
);
948 /* Initialize the local stacks.
950 AVAIL_EXPRS stores all the expressions made available in this block.
952 CONST_AND_COPIES stores var/value pairs to restore at the end of this
955 NONZERO_VARS stores the vars which have a nonzero value made in this
958 STMTS_TO_RESCAN is a list of statements we will rescan for operands.
960 VRP_VARIABLES is the list of variables which have had their values
961 constrained by an operation in this block.
963 These stacks are cleared in the finalization routine run for each
967 dom_opt_initialize_block_local_data (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
968 basic_block bb ATTRIBUTE_UNUSED
,
969 bool recycled ATTRIBUTE_UNUSED
)
971 #ifdef ENABLE_CHECKING
972 struct dom_walk_block_data
*bd
973 = (struct dom_walk_block_data
*)VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
975 /* We get cleared memory from the allocator, so if the memory is not
976 cleared, then we are re-using a previously allocated entry. In
977 that case, we can also re-use the underlying virtual arrays. Just
978 make sure we clear them before using them! */
981 if (bd
->avail_exprs
&& VARRAY_ACTIVE_SIZE (bd
->avail_exprs
) > 0)
983 if (bd
->const_and_copies
&& VARRAY_ACTIVE_SIZE (bd
->const_and_copies
) > 0)
985 if (bd
->nonzero_vars
&& VARRAY_ACTIVE_SIZE (bd
->nonzero_vars
) > 0)
987 if (bd
->stmts_to_rescan
&& VARRAY_ACTIVE_SIZE (bd
->stmts_to_rescan
) > 0)
989 if (bd
->vrp_variables
&& VARRAY_ACTIVE_SIZE (bd
->vrp_variables
) > 0)
991 if (bd
->block_defs
&& VARRAY_ACTIVE_SIZE (bd
->block_defs
) > 0)
997 /* Initialize local stacks for this optimizer and record equivalences
998 upon entry to BB. Equivalences can come from the edge traversed to
999 reach BB or they may come from PHI nodes at the start of BB. */
1002 dom_opt_initialize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
1004 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1005 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1007 record_equivalences_from_incoming_edge (walk_data
, bb
);
1009 /* PHI nodes can create equivalences too. */
1010 record_equivalences_from_phis (walk_data
, bb
);
1013 /* Given an expression EXPR (a relational expression or a statement),
1014 initialize the hash table element pointed by by ELEMENT. */
1017 initialize_hash_element (tree expr
, tree lhs
, struct expr_hash_elt
*element
)
1019 /* Hash table elements may be based on conditional expressions or statements.
1021 For the former case, we have no annotation and we want to hash the
1022 conditional expression. In the latter case we have an annotation and
1023 we want to record the expression the statement evaluates. */
1024 if (TREE_CODE_CLASS (TREE_CODE (expr
)) == '<'
1025 || TREE_CODE (expr
) == TRUTH_NOT_EXPR
)
1027 element
->ann
= NULL
;
1028 element
->rhs
= expr
;
1030 else if (TREE_CODE (expr
) == COND_EXPR
)
1032 element
->ann
= stmt_ann (expr
);
1033 element
->rhs
= COND_EXPR_COND (expr
);
1035 else if (TREE_CODE (expr
) == SWITCH_EXPR
)
1037 element
->ann
= stmt_ann (expr
);
1038 element
->rhs
= SWITCH_COND (expr
);
1040 else if (TREE_CODE (expr
) == RETURN_EXPR
&& TREE_OPERAND (expr
, 0))
1042 element
->ann
= stmt_ann (expr
);
1043 element
->rhs
= TREE_OPERAND (TREE_OPERAND (expr
, 0), 1);
1047 element
->ann
= stmt_ann (expr
);
1048 element
->rhs
= TREE_OPERAND (expr
, 1);
1052 element
->hash
= avail_expr_hash (element
);
1055 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
1056 LIMIT entries left in LOCALs. */
1059 remove_local_expressions_from_table (varray_type locals
,
1066 /* Remove all the expressions made available in this block. */
1067 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1069 struct expr_hash_elt element
;
1070 tree expr
= VARRAY_TOP_TREE (locals
);
1071 VARRAY_POP (locals
);
1073 initialize_hash_element (expr
, NULL
, &element
);
1074 htab_remove_elt_with_hash (table
, &element
, element
.hash
);
1078 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
1079 state, stopping when there are LIMIT entires left in LOCALs. */
1082 restore_nonzero_vars_to_original_value (varray_type locals
,
1089 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1091 tree name
= VARRAY_TOP_TREE (locals
);
1092 VARRAY_POP (locals
);
1093 bitmap_clear_bit (table
, SSA_NAME_VERSION (name
));
1097 /* Use the source/dest pairs in LOCALS to restore TABLE to its original
1098 state, stopping when there are LIMIT entires left in LOCALs. */
1101 restore_vars_to_original_value (varray_type locals
,
1108 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1110 tree prev_value
, dest
;
1112 prev_value
= VARRAY_TOP_TREE (locals
);
1113 VARRAY_POP (locals
);
1114 dest
= VARRAY_TOP_TREE (locals
);
1115 VARRAY_POP (locals
);
1117 set_value_for (dest
, prev_value
, table
);
1121 /* Similar to restore_vars_to_original_value, except that it restores
1122 CURRDEFS to its original value. */
1124 restore_currdefs_to_original_value (varray_type locals
, unsigned limit
)
1129 /* Restore CURRDEFS to its original state. */
1130 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1132 tree tmp
= VARRAY_TOP_TREE (locals
);
1133 tree saved_def
, var
;
1135 VARRAY_POP (locals
);
1137 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
1138 definition of its underlying variable. If we recorded anything
1139 else, it must have been an _DECL node and its current reaching
1140 definition must have been NULL. */
1141 if (TREE_CODE (tmp
) == SSA_NAME
)
1144 var
= SSA_NAME_VAR (saved_def
);
1152 var_ann (var
)->current_def
= saved_def
;
1156 /* We have finished processing the dominator children of BB, perform
1157 any finalization actions in preparation for leaving this node in
1158 the dominator tree. */
1161 dom_opt_finalize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
1163 struct dom_walk_block_data
*bd
1164 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1167 /* If we are at a leaf node in the dominator graph, see if we can thread
1168 the edge from BB through its successor.
1170 Do this before we remove entries from our equivalence tables. */
1172 && ! bb
->succ
->succ_next
1173 && (bb
->succ
->flags
& EDGE_ABNORMAL
) == 0
1174 && (get_immediate_dominator (CDI_DOMINATORS
, bb
->succ
->dest
) != bb
1175 || phi_nodes (bb
->succ
->dest
)))
1178 thread_across_edge (walk_data
, bb
->succ
);
1180 else if ((last
= last_stmt (bb
))
1181 && TREE_CODE (last
) == COND_EXPR
1182 && (TREE_CODE_CLASS (TREE_CODE (COND_EXPR_COND (last
))) == '<'
1183 || TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
)
1185 && (bb
->succ
->flags
& EDGE_ABNORMAL
) == 0
1186 && bb
->succ
->succ_next
1187 && (bb
->succ
->succ_next
->flags
& EDGE_ABNORMAL
) == 0
1188 && ! bb
->succ
->succ_next
->succ_next
)
1190 edge true_edge
, false_edge
;
1191 tree cond
, inverted
= NULL
;
1192 enum tree_code cond_code
;
1194 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1196 cond
= COND_EXPR_COND (last
);
1197 cond_code
= TREE_CODE (cond
);
1199 if (TREE_CODE_CLASS (cond_code
) == '<')
1200 inverted
= invert_truthvalue (cond
);
1202 /* If the THEN arm is the end of a dominator tree or has PHI nodes,
1203 then try to thread through its edge. */
1204 if (get_immediate_dominator (CDI_DOMINATORS
, true_edge
->dest
) != bb
1205 || phi_nodes (true_edge
->dest
))
1207 unsigned avail_expr_limit
;
1208 unsigned const_and_copies_limit
;
1209 unsigned currdefs_limit
;
1212 = bd
->avail_exprs
? VARRAY_ACTIVE_SIZE (bd
->avail_exprs
) : 0;
1213 const_and_copies_limit
1214 = bd
->const_and_copies
? VARRAY_ACTIVE_SIZE (bd
->const_and_copies
)
1217 = bd
->block_defs
? VARRAY_ACTIVE_SIZE (bd
->block_defs
) : 0;
1219 /* Record any equivalences created by following this edge. */
1220 if (TREE_CODE_CLASS (cond_code
) == '<')
1222 record_cond (cond
, boolean_true_node
, &bd
->avail_exprs
);
1223 record_cond (inverted
, boolean_false_node
, &bd
->avail_exprs
);
1225 else if (cond_code
== SSA_NAME
)
1226 record_const_or_copy (cond
, boolean_true_node
,
1227 &bd
->const_and_copies
);
1229 /* Now thread the edge. */
1230 thread_across_edge (walk_data
, true_edge
);
1232 /* And restore the various tables to their state before
1233 we threaded this edge. */
1234 remove_local_expressions_from_table (bd
->avail_exprs
,
1237 restore_vars_to_original_value (bd
->const_and_copies
,
1238 const_and_copies_limit
,
1240 restore_currdefs_to_original_value (bd
->block_defs
, currdefs_limit
);
1243 /* Similarly for the ELSE arm. */
1244 if (get_immediate_dominator (CDI_DOMINATORS
, false_edge
->dest
) != bb
1245 || phi_nodes (false_edge
->dest
))
1247 /* Record any equivalences created by following this edge. */
1248 if (TREE_CODE_CLASS (cond_code
) == '<')
1250 record_cond (cond
, boolean_false_node
, &bd
->avail_exprs
);
1251 record_cond (inverted
, boolean_true_node
, &bd
->avail_exprs
);
1253 else if (cond_code
== SSA_NAME
)
1254 record_const_or_copy (cond
, boolean_false_node
,
1255 &bd
->const_and_copies
);
1257 thread_across_edge (walk_data
, false_edge
);
1259 /* No need to remove local expressions from our tables
1260 or restore vars to their original value as that will
1261 be done immediately below. */
1265 remove_local_expressions_from_table (bd
->avail_exprs
, 0, avail_exprs
);
1266 restore_nonzero_vars_to_original_value (bd
->nonzero_vars
, 0, nonzero_vars
);
1267 restore_vars_to_original_value (bd
->const_and_copies
, 0, const_and_copies
);
1268 restore_currdefs_to_original_value (bd
->block_defs
, 0);
1270 /* Remove VRP records associated with this basic block. They are no
1273 To be efficient, we note which variables have had their values
1274 constrained in this block. So walk over each variable in the
1275 VRP_VARIABLEs array. */
1276 while (bd
->vrp_variables
&& VARRAY_ACTIVE_SIZE (bd
->vrp_variables
) > 0)
1278 tree var
= VARRAY_TOP_TREE (bd
->vrp_variables
);
1280 /* Each variable has a stack of value range records. We want to
1281 invalidate those associated with our basic block. So we walk
1282 the array backwards popping off records associated with our
1283 block. Once we hit a record not associated with our block
1285 varray_type var_vrp_records
= VARRAY_GENERIC_PTR (vrp_data
,
1286 SSA_NAME_VERSION (var
));
1288 while (VARRAY_ACTIVE_SIZE (var_vrp_records
) > 0)
1290 struct vrp_element
*element
1291 = (struct vrp_element
*)VARRAY_TOP_GENERIC_PTR (var_vrp_records
);
1293 if (element
->bb
!= bb
)
1296 VARRAY_POP (var_vrp_records
);
1299 VARRAY_POP (bd
->vrp_variables
);
1302 /* Re-scan operands in all statements that may have had new symbols
1304 while (bd
->stmts_to_rescan
&& VARRAY_ACTIVE_SIZE (bd
->stmts_to_rescan
) > 0)
1306 tree stmt
= VARRAY_TOP_TREE (bd
->stmts_to_rescan
);
1307 VARRAY_POP (bd
->stmts_to_rescan
);
1308 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1312 /* PHI nodes can create equivalences too.
1314 Ignoring any alternatives which are the same as the result, if
1315 all the alternatives are equal, then the PHI node creates an
1318 Additionally, if all the PHI alternatives are known to have a nonzero
1319 value, then the result of this PHI is known to have a nonzero value,
1320 even if we do not know its exact value. */
1323 record_equivalences_from_phis (struct dom_walk_data
*walk_data
, basic_block bb
)
1325 struct dom_walk_block_data
*bd
1326 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1329 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1331 tree lhs
= PHI_RESULT (phi
);
1335 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1337 tree t
= PHI_ARG_DEF (phi
, i
);
1339 if (TREE_CODE (t
) == SSA_NAME
|| is_gimple_min_invariant (t
))
1341 /* Ignore alternatives which are the same as our LHS. */
1342 if (operand_equal_p (lhs
, t
, 0))
1345 /* If we have not processed an alternative yet, then set
1346 RHS to this alternative. */
1349 /* If we have processed an alternative (stored in RHS), then
1350 see if it is equal to this one. If it isn't, then stop
1352 else if (! operand_equal_p (rhs
, t
, 0))
1359 /* If we had no interesting alternatives, then all the RHS alternatives
1360 must have been the same as LHS. */
1364 /* If we managed to iterate through each PHI alternative without
1365 breaking out of the loop, then we have a PHI which may create
1366 a useful equivalence. We do not need to record unwind data for
1367 this, since this is a true assignment and not an equivalence
1368 infered from a comparison. All uses of this ssa name are dominated
1369 by this assignment, so unwinding just costs time and space. */
1370 if (i
== PHI_NUM_ARGS (phi
)
1371 && may_propagate_copy (lhs
, rhs
))
1372 set_value_for (lhs
, rhs
, const_and_copies
);
1374 /* Now see if we know anything about the nonzero property for the
1375 result of this PHI. */
1376 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1378 if (!PHI_ARG_NONZERO (phi
, i
))
1382 if (i
== PHI_NUM_ARGS (phi
))
1383 bitmap_set_bit (nonzero_vars
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1385 register_new_def (lhs
, &bd
->block_defs
);
1389 /* Record any equivalences created by the incoming edge to BB. If BB
1390 has more than one incoming edge, then no equivalence is created. */
1393 record_equivalences_from_incoming_edge (struct dom_walk_data
*walk_data
,
1398 struct eq_expr_value eq_expr_value
;
1399 tree parent_block_last_stmt
= NULL
;
1400 struct dom_walk_block_data
*bd
1401 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1403 /* If our parent block ended with a control statment, then we may be
1404 able to record some equivalences based on which outgoing edge from
1405 the parent was followed. */
1406 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1409 parent_block_last_stmt
= last_stmt (parent
);
1410 if (parent_block_last_stmt
&& !is_ctrl_stmt (parent_block_last_stmt
))
1411 parent_block_last_stmt
= NULL
;
1414 eq_expr_value
.src
= NULL
;
1415 eq_expr_value
.dst
= NULL
;
1417 /* If we have a single predecessor, then extract EDGE_FLAGS from
1418 our single incoming edge. Otherwise clear EDGE_FLAGS and
1419 PARENT_BLOCK_LAST_STMT since they're not needed. */
1421 && ! bb
->pred
->pred_next
1422 && parent_block_last_stmt
1423 && bb_for_stmt (parent_block_last_stmt
) == bb
->pred
->src
)
1425 edge_flags
= bb
->pred
->flags
;
1430 parent_block_last_stmt
= NULL
;
1433 /* If our parent block ended in a COND_EXPR, add any equivalences
1434 created by the COND_EXPR to the hash table and initialize
1435 EQ_EXPR_VALUE appropriately.
1437 EQ_EXPR_VALUE is an assignment expression created when BB's immediate
1438 dominator ends in a COND_EXPR statement whose predicate is of the form
1439 'VAR == VALUE', where VALUE may be another variable or a constant.
1440 This is used to propagate VALUE on the THEN_CLAUSE of that
1441 conditional. This assignment is inserted in CONST_AND_COPIES so that
1442 the copy and constant propagator can find more propagation
1444 if (parent_block_last_stmt
1445 && bb
->pred
->pred_next
== NULL
1446 && TREE_CODE (parent_block_last_stmt
) == COND_EXPR
1447 && (edge_flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1448 eq_expr_value
= get_eq_expr_value (parent_block_last_stmt
,
1449 (edge_flags
& EDGE_TRUE_VALUE
) != 0,
1452 &bd
->vrp_variables
);
1453 /* Similarly when the parent block ended in a SWITCH_EXPR. */
1454 else if (parent_block_last_stmt
1455 && bb
->pred
->pred_next
== NULL
1456 && TREE_CODE (parent_block_last_stmt
) == SWITCH_EXPR
)
1458 tree switch_cond
= SWITCH_COND (parent_block_last_stmt
);
1460 /* If the switch's condition is an SSA variable, then we may
1461 know its value at each of the case labels. */
1462 if (TREE_CODE (switch_cond
) == SSA_NAME
)
1464 tree switch_vec
= SWITCH_LABELS (parent_block_last_stmt
);
1465 size_t i
, n
= TREE_VEC_LENGTH (switch_vec
);
1467 tree match_case
= NULL_TREE
;
1469 /* Search the case labels for those whose destination is
1470 the current basic block. */
1471 for (i
= 0; i
< n
; ++i
)
1473 tree elt
= TREE_VEC_ELT (switch_vec
, i
);
1474 if (label_to_block (CASE_LABEL (elt
)) == bb
)
1476 if (++case_count
> 1)
1482 /* If we encountered precisely one CASE_LABEL_EXPR and it
1483 was not the default case, or a case range, then we know
1484 the exact value of SWITCH_COND which caused us to get to
1485 this block. Record that equivalence in EQ_EXPR_VALUE. */
1487 && CASE_LOW (match_case
)
1488 && !CASE_HIGH (match_case
))
1490 eq_expr_value
.dst
= switch_cond
;
1491 eq_expr_value
.src
= CASE_LOW (match_case
);
1496 /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
1497 new value for VAR, so that occurrences of VAR can be replaced with
1498 VALUE while re-writing the THEN arm of a COND_EXPR. */
1499 if (eq_expr_value
.src
&& eq_expr_value
.dst
)
1500 record_equality (eq_expr_value
.dst
, eq_expr_value
.src
,
1501 &bd
->const_and_copies
);
1504 /* Dump SSA statistics on FILE. */
1507 dump_dominator_optimization_stats (FILE *file
)
1511 fprintf (file
, "Total number of statements: %6ld\n\n",
1512 opt_stats
.num_stmts
);
1513 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1514 opt_stats
.num_exprs_considered
);
1516 n_exprs
= opt_stats
.num_exprs_considered
;
1520 fprintf (file
, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
1521 opt_stats
.num_re
, PERCENT (opt_stats
.num_re
,
1524 fprintf (file
, "\nHash table statistics:\n");
1526 fprintf (file
, " avail_exprs: ");
1527 htab_statistics (file
, avail_exprs
);
1531 /* Dump SSA statistics on stderr. */
1534 debug_dominator_optimization_stats (void)
1536 dump_dominator_optimization_stats (stderr
);
1540 /* Dump statistics for the hash table HTAB. */
1543 htab_statistics (FILE *file
, htab_t htab
)
1545 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1546 (long) htab_size (htab
),
1547 (long) htab_elements (htab
),
1548 htab_collisions (htab
));
1551 /* Record the fact that VAR has a nonzero value, though we may not know
1552 its exact value. Note that if VAR is already known to have a nonzero
1553 value, then we do nothing. */
1556 record_var_is_nonzero (tree var
, varray_type
*block_nonzero_vars_p
)
1558 int indx
= SSA_NAME_VERSION (var
);
1560 if (bitmap_bit_p (nonzero_vars
, indx
))
1563 /* Mark it in the global table. */
1564 bitmap_set_bit (nonzero_vars
, indx
);
1566 /* Record this SSA_NAME so that we can reset the global table
1567 when we leave this block. */
1568 if (! *block_nonzero_vars_p
)
1569 VARRAY_TREE_INIT (*block_nonzero_vars_p
, 2, "block_nonzero_vars");
1570 VARRAY_PUSH_TREE (*block_nonzero_vars_p
, var
);
1573 /* Enter a statement into the true/false expression hash table indicating
1574 that the condition COND has the value VALUE. */
1577 record_cond (tree cond
, tree value
, varray_type
*block_avail_exprs_p
)
1579 struct expr_hash_elt
*element
= xmalloc (sizeof (struct expr_hash_elt
));
1582 initialize_hash_element (cond
, value
, element
);
1584 slot
= htab_find_slot_with_hash (avail_exprs
, (void *)element
,
1585 element
->hash
, true);
1588 *slot
= (void *) element
;
1589 if (! *block_avail_exprs_p
)
1590 VARRAY_TREE_INIT (*block_avail_exprs_p
, 20, "block_avail_exprs");
1591 VARRAY_PUSH_TREE (*block_avail_exprs_p
, cond
);
1597 /* A helper function for record_const_or_copy and record_equality.
1598 Do the work of recording the value and undo info. */
1601 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
,
1602 varray_type
*block_const_and_copies_p
)
1604 set_value_for (x
, y
, const_and_copies
);
1606 if (!*block_const_and_copies_p
)
1607 VARRAY_TREE_INIT (*block_const_and_copies_p
, 2, "block_const_and_copies");
1608 VARRAY_PUSH_TREE (*block_const_and_copies_p
, x
);
1609 VARRAY_PUSH_TREE (*block_const_and_copies_p
, prev_x
);
1612 /* Record that X is equal to Y in const_and_copies. Record undo
1613 information in the block-local varray. */
1616 record_const_or_copy (tree x
, tree y
, varray_type
*block_const_and_copies_p
)
1618 tree prev_x
= get_value_for (x
, const_and_copies
);
1620 if (TREE_CODE (y
) == SSA_NAME
)
1622 tree tmp
= get_value_for (y
, const_and_copies
);
1627 record_const_or_copy_1 (x
, y
, prev_x
, block_const_and_copies_p
);
1630 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1631 This constrains the cases in which we may treat this as assignment. */
1634 record_equality (tree x
, tree y
, varray_type
*block_const_and_copies_p
)
1636 tree prev_x
= NULL
, prev_y
= NULL
;
1638 if (TREE_CODE (x
) == SSA_NAME
)
1639 prev_x
= get_value_for (x
, const_and_copies
);
1640 if (TREE_CODE (y
) == SSA_NAME
)
1641 prev_y
= get_value_for (y
, const_and_copies
);
1643 /* If one of the previous values is invariant, then use that.
1644 Otherwise it doesn't matter which value we choose, just so
1645 long as we canonicalize on one value. */
1646 if (TREE_INVARIANT (y
))
1648 else if (TREE_INVARIANT (x
))
1649 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1650 else if (prev_x
&& TREE_INVARIANT (prev_x
))
1651 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1655 /* After the swapping, we must have one SSA_NAME. */
1656 if (TREE_CODE (x
) != SSA_NAME
)
1659 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1660 variable compared against zero. If we're honoring signed zeros,
1661 then we cannot record this value unless we know that the value is
1663 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1664 && (TREE_CODE (y
) != REAL_CST
1665 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1668 record_const_or_copy_1 (x
, y
, prev_x
, block_const_and_copies_p
);
1671 /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
1672 hash tables. Try to simplify the RHS using whatever equivalences
1673 we may have recorded.
1675 If we are able to simplify the RHS, then lookup the simplified form in
1676 the hash table and return the result. Otherwise return NULL. */
1679 simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*walk_data
,
1684 tree rhs
= TREE_OPERAND (stmt
, 1);
1685 enum tree_code rhs_code
= TREE_CODE (rhs
);
1687 struct dom_walk_block_data
*bd
1688 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1690 /* If we have lhs = ~x, look and see if we earlier had x = ~y.
1691 In which case we can change this statement to be lhs = y.
1692 Which can then be copy propagated.
1694 Similarly for negation. */
1695 if ((rhs_code
== BIT_NOT_EXPR
|| rhs_code
== NEGATE_EXPR
)
1696 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
1698 /* Get the definition statement for our RHS. */
1699 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1701 /* See if the RHS_DEF_STMT has the same form as our statement. */
1702 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
1703 && TREE_CODE (TREE_OPERAND (rhs_def_stmt
, 1)) == rhs_code
)
1705 tree rhs_def_operand
;
1707 rhs_def_operand
= TREE_OPERAND (TREE_OPERAND (rhs_def_stmt
, 1), 0);
1709 /* Verify that RHS_DEF_OPERAND is a suitable SSA variable. */
1710 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
1711 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
1712 result
= update_rhs_and_lookup_avail_expr (stmt
,
1720 /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
1721 If OP is associative, create and fold (y OP C2) OP C1 which
1722 should result in (y OP C3), use that as the RHS for the
1723 assignment. Add minus to this, as we handle it specially below. */
1724 if ((associative_tree_code (rhs_code
) || rhs_code
== MINUS_EXPR
)
1725 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
1726 && is_gimple_min_invariant (TREE_OPERAND (rhs
, 1)))
1728 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1730 /* See if the RHS_DEF_STMT has the same form as our statement. */
1731 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
)
1733 tree rhs_def_rhs
= TREE_OPERAND (rhs_def_stmt
, 1);
1734 enum tree_code rhs_def_code
= TREE_CODE (rhs_def_rhs
);
1736 if (rhs_code
== rhs_def_code
1737 || (rhs_code
== PLUS_EXPR
&& rhs_def_code
== MINUS_EXPR
)
1738 || (rhs_code
== MINUS_EXPR
&& rhs_def_code
== PLUS_EXPR
))
1740 tree def_stmt_op0
= TREE_OPERAND (rhs_def_rhs
, 0);
1741 tree def_stmt_op1
= TREE_OPERAND (rhs_def_rhs
, 1);
1743 if (TREE_CODE (def_stmt_op0
) == SSA_NAME
1744 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0
)
1745 && is_gimple_min_invariant (def_stmt_op1
))
1747 tree outer_const
= TREE_OPERAND (rhs
, 1);
1748 tree type
= TREE_TYPE (TREE_OPERAND (stmt
, 0));
1751 /* Ho hum. So fold will only operate on the outermost
1752 thingy that we give it, so we have to build the new
1753 expression in two pieces. This requires that we handle
1754 combinations of plus and minus. */
1755 if (rhs_def_code
!= rhs_code
)
1757 if (rhs_def_code
== MINUS_EXPR
)
1758 t
= build (MINUS_EXPR
, type
, outer_const
, def_stmt_op1
);
1760 t
= build (MINUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1761 rhs_code
= PLUS_EXPR
;
1763 else if (rhs_def_code
== MINUS_EXPR
)
1764 t
= build (PLUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1766 t
= build (rhs_def_code
, type
, def_stmt_op1
, outer_const
);
1768 t
= build (rhs_code
, type
, def_stmt_op0
, t
);
1771 /* If the result is a suitable looking gimple expression,
1772 then use it instead of the original for STMT. */
1773 if (TREE_CODE (t
) == SSA_NAME
1774 || (TREE_CODE_CLASS (TREE_CODE (t
)) == '1'
1775 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
1776 || ((TREE_CODE_CLASS (TREE_CODE (t
)) == '2'
1777 || TREE_CODE_CLASS (TREE_CODE (t
)) == '<')
1778 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
1779 && is_gimple_val (TREE_OPERAND (t
, 1))))
1780 result
= update_rhs_and_lookup_avail_expr
1781 (stmt
, t
, &bd
->avail_exprs
, ann
, insert
);
1787 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1788 and BIT_AND_EXPR respectively if the first operand is greater
1789 than zero and the second operand is an exact power of two. */
1790 if ((rhs_code
== TRUNC_DIV_EXPR
|| rhs_code
== TRUNC_MOD_EXPR
)
1791 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
1792 && integer_pow2p (TREE_OPERAND (rhs
, 1)))
1795 tree op
= TREE_OPERAND (rhs
, 0);
1797 if (TYPE_UNSIGNED (TREE_TYPE (op
)))
1799 val
= integer_one_node
;
1803 tree dummy_cond
= walk_data
->global_data
;
1807 dummy_cond
= build (GT_EXPR
, boolean_type_node
,
1808 op
, integer_zero_node
);
1809 dummy_cond
= build (COND_EXPR
, void_type_node
,
1810 dummy_cond
, NULL
, NULL
);
1811 walk_data
->global_data
= dummy_cond
;
1815 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), GT_EXPR
);
1816 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
1817 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
1818 = integer_zero_node
;
1820 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
1825 if (val
&& integer_onep (val
))
1828 tree op0
= TREE_OPERAND (rhs
, 0);
1829 tree op1
= TREE_OPERAND (rhs
, 1);
1831 if (rhs_code
== TRUNC_DIV_EXPR
)
1832 t
= build (RSHIFT_EXPR
, TREE_TYPE (op0
), op0
,
1833 build_int_2 (tree_log2 (op1
), 0));
1835 t
= build (BIT_AND_EXPR
, TREE_TYPE (op0
), op0
,
1836 local_fold (build (MINUS_EXPR
, TREE_TYPE (op1
),
1837 op1
, integer_one_node
)));
1839 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
1845 /* Transform ABS (X) into X or -X as appropriate. */
1846 if (rhs_code
== ABS_EXPR
1847 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
1850 tree op
= TREE_OPERAND (rhs
, 0);
1851 tree type
= TREE_TYPE (op
);
1853 if (TYPE_UNSIGNED (type
))
1855 val
= integer_zero_node
;
1859 tree dummy_cond
= walk_data
->global_data
;
1863 dummy_cond
= build (LE_EXPR
, boolean_type_node
,
1864 op
, integer_zero_node
);
1865 dummy_cond
= build (COND_EXPR
, void_type_node
,
1866 dummy_cond
, NULL
, NULL
);
1867 walk_data
->global_data
= dummy_cond
;
1871 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), LE_EXPR
);
1872 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
1873 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
1874 = convert (type
, integer_zero_node
);
1876 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
1882 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), GE_EXPR
);
1883 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
1884 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
1885 = convert (type
, integer_zero_node
);
1887 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
1893 if (integer_zerop (val
))
1894 val
= integer_one_node
;
1895 else if (integer_onep (val
))
1896 val
= integer_zero_node
;
1902 && (integer_onep (val
) || integer_zerop (val
)))
1906 if (integer_onep (val
))
1907 t
= build1 (NEGATE_EXPR
, TREE_TYPE (op
), op
);
1911 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
1917 /* Optimize *"foo" into 'f'. This is done here rather than
1918 in fold to avoid problems with stuff like &*"foo". */
1919 if (TREE_CODE (rhs
) == INDIRECT_REF
|| TREE_CODE (rhs
) == ARRAY_REF
)
1921 tree t
= fold_read_from_constant_string (rhs
);
1924 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
1932 /* COND is a condition of the form:
1934 x == const or x != const
1936 Look back to x's defining statement and see if x is defined as
1940 If const is unchanged if we convert it to type, then we can build
1941 the equivalent expression:
1944 y == const or y != const
1946 Which may allow further optimizations.
1948 Return the equivalent comparison or NULL if no such equivalent comparison
1952 find_equivalent_equality_comparison (tree cond
)
1954 tree op0
= TREE_OPERAND (cond
, 0);
1955 tree op1
= TREE_OPERAND (cond
, 1);
1956 tree def_stmt
= SSA_NAME_DEF_STMT (op0
);
1958 /* OP0 might have been a parameter, so first make sure it
1959 was defined by a MODIFY_EXPR. */
1960 if (def_stmt
&& TREE_CODE (def_stmt
) == MODIFY_EXPR
)
1962 tree def_rhs
= TREE_OPERAND (def_stmt
, 1);
1964 /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
1965 if ((TREE_CODE (def_rhs
) == NOP_EXPR
1966 || TREE_CODE (def_rhs
) == CONVERT_EXPR
)
1967 && TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == SSA_NAME
)
1969 tree def_rhs_inner
= TREE_OPERAND (def_rhs
, 0);
1970 tree def_rhs_inner_type
= TREE_TYPE (def_rhs_inner
);
1973 if (TYPE_PRECISION (def_rhs_inner_type
)
1974 > TYPE_PRECISION (TREE_TYPE (def_rhs
)))
1977 /* What we want to prove is that if we convert OP1 to
1978 the type of the object inside the NOP_EXPR that the
1979 result is still equivalent to SRC.
1981 If that is true, the build and return new equivalent
1982 condition which uses the source of the typecast and the
1983 new constant (which has only changed its type). */
1984 new = build1 (TREE_CODE (def_rhs
), def_rhs_inner_type
, op1
);
1985 new = local_fold (new);
1986 if (is_gimple_val (new) && tree_int_cst_equal (new, op1
))
1987 return build (TREE_CODE (cond
), TREE_TYPE (cond
),
1988 def_rhs_inner
, new);
1994 /* STMT is a COND_EXPR for which we could not trivially determine its
1995 result. This routine attempts to find equivalent forms of the
1996 condition which we may be able to optimize better. It also
1997 uses simple value range propagation to optimize conditionals. */
2000 simplify_cond_and_lookup_avail_expr (tree stmt
,
2001 varray_type
*block_avail_exprs_p
,
2005 tree cond
= COND_EXPR_COND (stmt
);
2007 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
2009 tree op0
= TREE_OPERAND (cond
, 0);
2010 tree op1
= TREE_OPERAND (cond
, 1);
2012 if (TREE_CODE (op0
) == SSA_NAME
&& is_gimple_min_invariant (op1
))
2015 tree low
, high
, cond_low
, cond_high
;
2016 int lowequal
, highequal
, swapped
, no_overlap
, subset
, cond_inverted
;
2017 varray_type vrp_records
;
2018 struct vrp_element
*element
;
2020 /* First see if we have test of an SSA_NAME against a constant
2021 where the SSA_NAME is defined by an earlier typecast which
2022 is irrelevant when performing tests against the given
2024 if (TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
2026 tree new_cond
= find_equivalent_equality_comparison (cond
);
2030 /* Update the statement to use the new equivalent
2032 COND_EXPR_COND (stmt
) = new_cond
;
2035 /* Lookup the condition and return its known value if it
2037 new_cond
= lookup_avail_expr (stmt
, block_avail_exprs_p
,
2042 /* The operands have changed, so update op0 and op1. */
2043 op0
= TREE_OPERAND (cond
, 0);
2044 op1
= TREE_OPERAND (cond
, 1);
2048 /* Consult the value range records for this variable (if they exist)
2049 to see if we can eliminate or simplify this conditional.
2051 Note two tests are necessary to determine no records exist.
2052 First we have to see if the virtual array exists, if it
2053 exists, then we have to check its active size.
2055 Also note the vast majority of conditionals are not testing
2056 a variable which has had its range constrained by an earlier
2057 conditional. So this filter avoids a lot of unnecessary work. */
2058 vrp_records
= VARRAY_GENERIC_PTR (vrp_data
, SSA_NAME_VERSION (op0
));
2059 if (vrp_records
== NULL
)
2062 limit
= VARRAY_ACTIVE_SIZE (vrp_records
);
2064 /* If we have no value range records for this variable, or we are
2065 unable to extract a range for this condition, then there is
2068 || ! extract_range_from_cond (cond
, &cond_high
,
2069 &cond_low
, &cond_inverted
))
2072 /* We really want to avoid unnecessary computations of range
2073 info. So all ranges are computed lazily; this avoids a
2074 lot of unnecessary work. ie, we record the conditional,
2075 but do not process how it constrains the variable's
2076 potential values until we know that processing the condition
2079 However, we do not want to have to walk a potentially long
2080 list of ranges, nor do we want to compute a variable's
2081 range more than once for a given path.
2083 Luckily, each time we encounter a conditional that can not
2084 be otherwise optimized we will end up here and we will
2085 compute the necessary range information for the variable
2086 used in this condition.
2088 Thus you can conclude that there will never be more than one
2089 conditional associated with a variable which has not been
2090 processed. So we never need to merge more than one new
2091 conditional into the current range.
2093 These properties also help us avoid unnecessary work. */
2095 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
, limit
- 1);
2097 if (element
->high
&& element
->low
)
2099 /* The last element has been processed, so there is no range
2100 merging to do, we can simply use the high/low values
2101 recorded in the last element. */
2103 high
= element
->high
;
2107 tree tmp_high
, tmp_low
;
2110 /* The last element has not been processed. Process it now. */
2111 extract_range_from_cond (element
->cond
, &tmp_high
,
2114 /* If this is the only element, then no merging is necessary,
2115 the high/low values from extract_range_from_cond are all
2124 /* Get the high/low value from the previous element. */
2125 struct vrp_element
*prev
2126 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
,
2131 /* Merge in this element's range with the range from the
2134 The low value for the merged range is the maximum of
2135 the previous low value and the low value of this record.
2137 Similarly the high value for the merged range is the
2138 minimum of the previous high value and the high value of
2140 low
= (tree_int_cst_compare (low
, tmp_low
) == 1
2142 high
= (tree_int_cst_compare (high
, tmp_high
) == -1
2146 /* And record the computed range. */
2148 element
->high
= high
;
2152 /* After we have constrained this variable's potential values,
2153 we try to determine the result of the given conditional.
2155 To simplify later tests, first determine if the current
2156 low value is the same low value as the conditional.
2157 Similarly for the current high value and the high value
2158 for the conditional. */
2159 lowequal
= tree_int_cst_equal (low
, cond_low
);
2160 highequal
= tree_int_cst_equal (high
, cond_high
);
2162 if (lowequal
&& highequal
)
2163 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2165 /* To simplify the overlap/subset tests below we may want
2166 to swap the two ranges so that the larger of the two
2167 ranges occurs "first". */
2169 if (tree_int_cst_compare (low
, cond_low
) == 1
2171 && tree_int_cst_compare (cond_high
, high
) == 1))
2184 /* Now determine if there is no overlap in the ranges
2185 or if the second range is a subset of the first range. */
2186 no_overlap
= tree_int_cst_lt (high
, cond_low
);
2187 subset
= tree_int_cst_compare (cond_high
, high
) != 1;
2189 /* If there was no overlap in the ranges, then this conditional
2190 always has a false value (unless we had to invert this
2191 conditional, in which case it always has a true value). */
2193 return (cond_inverted
? boolean_true_node
: boolean_false_node
);
2195 /* If the current range is a subset of the condition's range,
2196 then this conditional always has a true value (unless we
2197 had to invert this conditional, in which case it always
2198 has a true value). */
2199 if (subset
&& swapped
)
2200 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2202 /* We were unable to determine the result of the conditional.
2203 However, we may be able to simplify the conditional. First
2204 merge the ranges in the same manner as range merging above. */
2205 low
= tree_int_cst_compare (low
, cond_low
) == 1 ? low
: cond_low
;
2206 high
= tree_int_cst_compare (high
, cond_high
) == -1 ? high
: cond_high
;
2208 /* If the range has converged to a single point, then turn this
2209 into an equality comparison. */
2210 if (TREE_CODE (cond
) != EQ_EXPR
2211 && TREE_CODE (cond
) != NE_EXPR
2212 && tree_int_cst_equal (low
, high
))
2214 TREE_SET_CODE (cond
, EQ_EXPR
);
2215 TREE_OPERAND (cond
, 1) = high
;
2222 /* STMT is a SWITCH_EXPR for which we could not trivially determine its
2223 result. This routine attempts to find equivalent forms of the
2224 condition which we may be able to optimize better. */
2227 simplify_switch_and_lookup_avail_expr (tree stmt
,
2228 varray_type
*block_avail_exprs_p
,
2232 tree cond
= SWITCH_COND (stmt
);
2235 /* The optimization that we really care about is removing unnecessary
2236 casts. That will let us do much better in propagating the inferred
2237 constant at the switch target. */
2238 if (TREE_CODE (cond
) == SSA_NAME
)
2240 def
= SSA_NAME_DEF_STMT (cond
);
2241 if (TREE_CODE (def
) == MODIFY_EXPR
)
2243 def
= TREE_OPERAND (def
, 1);
2244 if (TREE_CODE (def
) == NOP_EXPR
)
2246 def
= TREE_OPERAND (def
, 0);
2247 to
= TREE_TYPE (cond
);
2248 ti
= TREE_TYPE (def
);
2250 /* If we have an extension that preserves sign, then we
2251 can copy the source value into the switch. */
2252 if (TYPE_UNSIGNED (to
) == TYPE_UNSIGNED (ti
)
2253 && TYPE_PRECISION (to
) >= TYPE_PRECISION (ti
)
2254 && is_gimple_val (def
))
2256 SWITCH_COND (stmt
) = def
;
2259 return lookup_avail_expr (stmt
, block_avail_exprs_p
, insert
);
2268 /* Propagate known constants/copies into PHI nodes of BB's successor
2272 cprop_into_phis (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
2275 cprop_into_successor_phis (bb
, const_and_copies
, nonzero_vars
);
2278 /* Search for redundant computations in STMT. If any are found, then
2279 replace them with the variable holding the result of the computation.
2281 If safe, record this expression into the available expression hash
2285 eliminate_redundant_computations (struct dom_walk_data
*walk_data
,
2286 tree stmt
, stmt_ann_t ann
)
2288 vdef_optype vdefs
= VDEF_OPS (ann
);
2289 tree
*expr_p
, def
= NULL_TREE
;
2292 bool retval
= false;
2293 struct dom_walk_block_data
*bd
2294 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
2296 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2297 def
= TREE_OPERAND (stmt
, 0);
2299 /* Certain expressions on the RHS can be optimized away, but can not
2300 themselves be entered into the hash tables. */
2301 if (ann
->makes_aliased_stores
2303 || TREE_CODE (def
) != SSA_NAME
2304 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
2305 || NUM_VDEFS (vdefs
) != 0)
2308 /* Check if the expression has been computed before. */
2309 cached_lhs
= lookup_avail_expr (stmt
, &bd
->avail_exprs
, insert
);
2311 /* If this is an assignment and the RHS was not in the hash table,
2312 then try to simplify the RHS and lookup the new RHS in the
2314 if (! cached_lhs
&& TREE_CODE (stmt
) == MODIFY_EXPR
)
2315 cached_lhs
= simplify_rhs_and_lookup_avail_expr (walk_data
,
2319 /* Similarly if this is a COND_EXPR and we did not find its
2320 expression in the hash table, simplify the condition and
2322 else if (! cached_lhs
&& TREE_CODE (stmt
) == COND_EXPR
)
2323 cached_lhs
= simplify_cond_and_lookup_avail_expr (stmt
,
2327 /* Similarly for a SWITCH_EXPR. */
2328 else if (!cached_lhs
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
2329 cached_lhs
= simplify_switch_and_lookup_avail_expr (stmt
,
2334 opt_stats
.num_exprs_considered
++;
2336 /* Get a pointer to the expression we are trying to optimize. */
2337 if (TREE_CODE (stmt
) == COND_EXPR
)
2338 expr_p
= &COND_EXPR_COND (stmt
);
2339 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2340 expr_p
= &SWITCH_COND (stmt
);
2341 else if (TREE_CODE (stmt
) == RETURN_EXPR
&& TREE_OPERAND (stmt
, 0))
2342 expr_p
= &TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
2344 expr_p
= &TREE_OPERAND (stmt
, 1);
2346 /* It is safe to ignore types here since we have already done
2347 type checking in the hashing and equality routines. In fact
2348 type checking here merely gets in the way of constant
2349 propagation. Also, make sure that it is safe to propagate
2350 CACHED_LHS into *EXPR_P. */
2352 && (TREE_CODE (cached_lhs
) != SSA_NAME
2353 || may_propagate_copy (cached_lhs
, *expr_p
)))
2355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2357 fprintf (dump_file
, " Replaced redundant expr '");
2358 print_generic_expr (dump_file
, *expr_p
, dump_flags
);
2359 fprintf (dump_file
, "' with '");
2360 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
2361 fprintf (dump_file
, "'\n");
2366 #if defined ENABLE_CHECKING
2367 if (TREE_CODE (cached_lhs
) != SSA_NAME
2368 && !is_gimple_min_invariant (cached_lhs
))
2372 if (TREE_CODE (cached_lhs
) == ADDR_EXPR
2373 || (POINTER_TYPE_P (TREE_TYPE (*expr_p
))
2374 && is_gimple_min_invariant (cached_lhs
)))
2377 propagate_value (expr_p
, cached_lhs
);
2383 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
2384 the available expressions table or the const_and_copies table.
2385 Detect and record those equivalences. */
2388 record_equivalences_from_stmt (tree stmt
,
2389 varray_type
*block_avail_exprs_p
,
2390 varray_type
*block_nonzero_vars_p
,
2394 tree lhs
= TREE_OPERAND (stmt
, 0);
2395 enum tree_code lhs_code
= TREE_CODE (lhs
);
2398 if (lhs_code
== SSA_NAME
)
2400 tree rhs
= TREE_OPERAND (stmt
, 1);
2402 /* Strip away any useless type conversions. */
2403 STRIP_USELESS_TYPE_CONVERSION (rhs
);
2405 /* If the RHS of the assignment is a constant or another variable that
2406 may be propagated, register it in the CONST_AND_COPIES table. We
2407 do not need to record unwind data for this, since this is a true
2408 assignment and not an equivalence infered from a comparison. All
2409 uses of this ssa name are dominated by this assignment, so unwinding
2410 just costs time and space. */
2412 && (TREE_CODE (rhs
) == SSA_NAME
2413 || is_gimple_min_invariant (rhs
)))
2414 set_value_for (lhs
, rhs
, const_and_copies
);
2416 /* alloca never returns zero and the address of a non-weak symbol
2417 is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
2418 stripped as they do not affect this equivalence. */
2419 while (TREE_CODE (rhs
) == NOP_EXPR
2420 || TREE_CODE (rhs
) == CONVERT_EXPR
)
2421 rhs
= TREE_OPERAND (rhs
, 0);
2423 if (alloca_call_p (rhs
)
2424 || (TREE_CODE (rhs
) == ADDR_EXPR
2425 && DECL_P (TREE_OPERAND (rhs
, 0))
2426 && ! DECL_WEAK (TREE_OPERAND (rhs
, 0))))
2427 record_var_is_nonzero (lhs
, block_nonzero_vars_p
);
2429 /* IOR of any value with a nonzero value will result in a nonzero
2430 value. Even if we do not know the exact result recording that
2431 the result is nonzero is worth the effort. */
2432 if (TREE_CODE (rhs
) == BIT_IOR_EXPR
2433 && integer_nonzerop (TREE_OPERAND (rhs
, 1)))
2434 record_var_is_nonzero (lhs
, block_nonzero_vars_p
);
2437 /* Look at both sides for pointer dereferences. If we find one, then
2438 the pointer must be nonnull and we can enter that equivalence into
2440 if (flag_delete_null_pointer_checks
)
2441 for (i
= 0; i
< 2; i
++)
2443 tree t
= TREE_OPERAND (stmt
, i
);
2445 /* Strip away any COMPONENT_REFs. */
2446 while (TREE_CODE (t
) == COMPONENT_REF
)
2447 t
= TREE_OPERAND (t
, 0);
2449 /* Now see if this is a pointer dereference. */
2450 if (TREE_CODE (t
) == INDIRECT_REF
)
2452 tree op
= TREE_OPERAND (t
, 0);
2454 /* If the pointer is a SSA variable, then enter new
2455 equivalences into the hash table. */
2456 while (TREE_CODE (op
) == SSA_NAME
)
2458 tree def
= SSA_NAME_DEF_STMT (op
);
2460 record_var_is_nonzero (op
, block_nonzero_vars_p
);
2462 /* And walk up the USE-DEF chains noting other SSA_NAMEs
2463 which are known to have a nonzero value. */
2465 && TREE_CODE (def
) == MODIFY_EXPR
2466 && TREE_CODE (TREE_OPERAND (def
, 1)) == NOP_EXPR
)
2467 op
= TREE_OPERAND (TREE_OPERAND (def
, 1), 0);
2474 /* A memory store, even an aliased store, creates a useful
2475 equivalence. By exchanging the LHS and RHS, creating suitable
2476 vops and recording the result in the available expression table,
2477 we may be able to expose more redundant loads. */
2478 if (!ann
->has_volatile_ops
2479 && (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
2480 || is_gimple_min_invariant (TREE_OPERAND (stmt
, 1)))
2481 && !is_gimple_reg (lhs
))
2483 tree rhs
= TREE_OPERAND (stmt
, 1);
2487 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
2488 is a constant, we need to adjust the constant to fit into the
2489 type of the LHS. If the LHS is a bitfield and the RHS is not
2490 a constant, then we can not record any equivalences for this
2491 statement since we would need to represent the widening or
2492 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
2493 and should not be necessary if GCC represented bitfields
2495 if (lhs_code
== COMPONENT_REF
2496 && DECL_BIT_FIELD (TREE_OPERAND (lhs
, 1)))
2498 if (TREE_CONSTANT (rhs
))
2499 rhs
= widen_bitfield (rhs
, TREE_OPERAND (lhs
, 1), lhs
);
2503 /* If the value overflowed, then we can not use this equivalence. */
2504 if (rhs
&& ! is_gimple_min_invariant (rhs
))
2510 vdef_optype vdefs
= VDEF_OPS (ann
);
2512 /* Build a new statement with the RHS and LHS exchanged. */
2513 new = build (MODIFY_EXPR
, TREE_TYPE (stmt
), rhs
, lhs
);
2515 /* Get an annotation and set up the real operands. */
2517 get_stmt_operands (new);
2519 /* Clear out the virtual operands on the new statement, we are
2520 going to set them explicitly below. */
2524 start_ssa_stmt_operands (new);
2525 /* For each VDEF on the original statement, we want to create a
2526 VUSE of the VDEF result on the new statement. */
2527 for (j
= 0; j
< NUM_VDEFS (vdefs
); j
++)
2529 tree op
= VDEF_RESULT (vdefs
, j
);
2533 finalize_ssa_stmt_operands (new);
2535 /* Finally enter the statement into the available expression
2537 lookup_avail_expr (new, block_avail_exprs_p
, true);
2542 /* Optimize the statement pointed by iterator SI.
2544 We try to perform some simplistic global redundancy elimination and
2545 constant propagation:
2547 1- To detect global redundancy, we keep track of expressions that have
2548 been computed in this block and its dominators. If we find that the
2549 same expression is computed more than once, we eliminate repeated
2550 computations by using the target of the first one.
2552 2- Constant values and copy assignments. This is used to do very
2553 simplistic constant and copy propagation. When a constant or copy
2554 assignment is found, we map the value on the RHS of the assignment to
2555 the variable in the LHS in the CONST_AND_COPIES table. */
2558 optimize_stmt (struct dom_walk_data
*walk_data
,
2559 basic_block bb ATTRIBUTE_UNUSED
,
2560 block_stmt_iterator si
)
2565 bool may_optimize_p
;
2566 bool may_have_exposed_new_symbols
= false;
2567 struct dom_walk_block_data
*bd
2568 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
2570 stmt
= bsi_stmt (si
);
2572 get_stmt_operands (stmt
);
2573 ann
= stmt_ann (stmt
);
2574 vdefs
= VDEF_OPS (ann
);
2575 opt_stats
.num_stmts
++;
2576 may_have_exposed_new_symbols
= false;
2578 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2580 fprintf (dump_file
, "Optimizing statement ");
2581 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
2584 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2585 may_have_exposed_new_symbols
= cprop_into_stmt (stmt
, const_and_copies
);
2587 /* If the statement has been modified with constant replacements,
2588 fold its RHS before checking for redundant computations. */
2591 /* Try to fold the statement making sure that STMT is kept
2593 if (fold_stmt (bsi_stmt_ptr (si
)))
2595 stmt
= bsi_stmt (si
);
2596 ann
= stmt_ann (stmt
);
2598 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2600 fprintf (dump_file
, " Folded to: ");
2601 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
2605 /* Constant/copy propagation above may change the set of
2606 virtual operands associated with this statement. Folding
2607 may remove the need for some virtual operands.
2609 Indicate we will need to rescan and rewrite the statement. */
2610 may_have_exposed_new_symbols
= true;
2613 /* Check for redundant computations. Do this optimization only
2614 for assignments that have no volatile ops and conditionals. */
2615 may_optimize_p
= (!ann
->has_volatile_ops
2616 && ((TREE_CODE (stmt
) == RETURN_EXPR
2617 && TREE_OPERAND (stmt
, 0)
2618 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
2619 && ! (TREE_SIDE_EFFECTS
2620 (TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1))))
2621 || (TREE_CODE (stmt
) == MODIFY_EXPR
2622 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt
, 1)))
2623 || TREE_CODE (stmt
) == COND_EXPR
2624 || TREE_CODE (stmt
) == SWITCH_EXPR
));
2627 may_have_exposed_new_symbols
2628 |= eliminate_redundant_computations (walk_data
, stmt
, ann
);
2630 /* Record any additional equivalences created by this statement. */
2631 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2632 record_equivalences_from_stmt (stmt
,
2638 register_definitions_for_stmt (ann
, &bd
->block_defs
);
2640 /* If STMT is a COND_EXPR and it was modified, then we may know
2641 where it goes. If that is the case, then mark the CFG as altered.
2643 This will cause us to later call remove_unreachable_blocks and
2644 cleanup_tree_cfg when it is safe to do so. It is not safe to
2645 clean things up here since removal of edges and such can trigger
2646 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2649 That's all fine and good, except that once SSA_NAMEs are released
2650 to the manager, we must not call create_ssa_name until all references
2651 to released SSA_NAMEs have been eliminated.
2653 All references to the deleted SSA_NAMEs can not be eliminated until
2654 we remove unreachable blocks.
2656 We can not remove unreachable blocks until after we have completed
2657 any queued jump threading.
2659 We can not complete any queued jump threads until we have taken
2660 appropriate variables out of SSA form. Taking variables out of
2661 SSA form can call create_ssa_name and thus we lose.
2663 Ultimately I suspect we're going to need to change the interface
2664 into the SSA_NAME manager. */
2670 if (TREE_CODE (stmt
) == COND_EXPR
)
2671 val
= COND_EXPR_COND (stmt
);
2672 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2673 val
= SWITCH_COND (stmt
);
2675 if (val
&& TREE_CODE (val
) == INTEGER_CST
2676 && find_taken_edge (bb_for_stmt (stmt
), val
))
2680 if (may_have_exposed_new_symbols
)
2682 if (! bd
->stmts_to_rescan
)
2683 VARRAY_TREE_INIT (bd
->stmts_to_rescan
, 20, "stmts_to_rescan");
2684 VARRAY_PUSH_TREE (bd
->stmts_to_rescan
, bsi_stmt (si
));
2688 /* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
2689 available expression hashtable, then return the LHS from the hash
2692 If INSERT is true, then we also update the available expression
2693 hash table to account for the changes made to STMT. */
2696 update_rhs_and_lookup_avail_expr (tree stmt
, tree new_rhs
,
2697 varray_type
*block_avail_exprs_p
,
2701 tree cached_lhs
= NULL
;
2703 /* Remove the old entry from the hash table. */
2706 struct expr_hash_elt element
;
2708 initialize_hash_element (stmt
, NULL
, &element
);
2709 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
2712 /* Now update the RHS of the assignment. */
2713 TREE_OPERAND (stmt
, 1) = new_rhs
;
2715 /* Now lookup the updated statement in the hash table. */
2716 cached_lhs
= lookup_avail_expr (stmt
, block_avail_exprs_p
, insert
);
2718 /* We have now called lookup_avail_expr twice with two different
2719 versions of this same statement, once in optimize_stmt, once here.
2721 We know the call in optimize_stmt did not find an existing entry
2722 in the hash table, so a new entry was created. At the same time
2723 this statement was pushed onto the BLOCK_AVAIL_EXPRS varray.
2725 If this call failed to find an existing entry on the hash table,
2726 then the new version of this statement was entered into the
2727 hash table. And this statement was pushed onto BLOCK_AVAIL_EXPR
2728 for the second time. So there are two copies on BLOCK_AVAIL_EXPRs
2730 If this call succeeded, we still have one copy of this statement
2731 on the BLOCK_AVAIL_EXPRs varray.
2733 For both cases, we need to pop the most recent entry off the
2734 BLOCK_AVAIL_EXPRs varray. For the case where we never found this
2735 statement in the hash tables, that will leave precisely one
2736 copy of this statement on BLOCK_AVAIL_EXPRs. For the case where
2737 we found a copy of this statement in the second hash table lookup
2738 we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs. */
2740 VARRAY_POP (*block_avail_exprs_p
);
2742 /* And make sure we record the fact that we modified this
2749 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
2750 found, return its LHS. Otherwise insert STMT in the table and return
2753 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
2754 is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
2755 can be removed when we finish processing this block and its children.
2757 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
2758 contains no CALL_EXPR on its RHS and makes no volatile nor
2759 aliased references. */
2762 lookup_avail_expr (tree stmt
, varray_type
*block_avail_exprs_p
, bool insert
)
2767 struct expr_hash_elt
*element
= xcalloc (sizeof (struct expr_hash_elt
), 1);
2769 lhs
= TREE_CODE (stmt
) == MODIFY_EXPR
? TREE_OPERAND (stmt
, 0) : NULL
;
2771 initialize_hash_element (stmt
, lhs
, element
);
2773 /* Don't bother remembering constant assignments and copy operations.
2774 Constants and copy operations are handled by the constant/copy propagator
2775 in optimize_stmt. */
2776 if (TREE_CODE (element
->rhs
) == SSA_NAME
2777 || is_gimple_min_invariant (element
->rhs
))
2783 /* If this is an equality test against zero, see if we have recorded a
2784 nonzero value for the variable in question. */
2785 if ((TREE_CODE (element
->rhs
) == EQ_EXPR
2786 || TREE_CODE (element
->rhs
) == NE_EXPR
)
2787 && TREE_CODE (TREE_OPERAND (element
->rhs
, 0)) == SSA_NAME
2788 && integer_zerop (TREE_OPERAND (element
->rhs
, 1)))
2790 int indx
= SSA_NAME_VERSION (TREE_OPERAND (element
->rhs
, 0));
2792 if (bitmap_bit_p (nonzero_vars
, indx
))
2794 tree t
= element
->rhs
;
2797 if (TREE_CODE (t
) == EQ_EXPR
)
2798 return boolean_false_node
;
2800 return boolean_true_node
;
2804 /* Finally try to find the expression in the main expression hash table. */
2805 slot
= htab_find_slot_with_hash (avail_exprs
, element
, element
->hash
,
2806 (insert
? INSERT
: NO_INSERT
));
2815 *slot
= (void *) element
;
2816 if (! *block_avail_exprs_p
)
2817 VARRAY_TREE_INIT (*block_avail_exprs_p
, 20, "block_avail_exprs");
2818 VARRAY_PUSH_TREE (*block_avail_exprs_p
, stmt
? stmt
: element
->rhs
);
2822 /* Extract the LHS of the assignment so that it can be used as the current
2823 definition of another variable. */
2824 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
2826 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2827 use the value from the const_and_copies table. */
2828 if (TREE_CODE (lhs
) == SSA_NAME
)
2830 temp
= get_value_for (lhs
, const_and_copies
);
2839 /* Given a condition COND, record into HI_P, LO_P and INVERTED_P the
2840 range of values that result in the conditional having a true value.
2842 Return true if we are successful in extracting a range from COND and
2843 false if we are unsuccessful. */
2846 extract_range_from_cond (tree cond
, tree
*hi_p
, tree
*lo_p
, int *inverted_p
)
2848 tree op1
= TREE_OPERAND (cond
, 1);
2849 tree high
, low
, type
;
2852 /* Experiments have shown that it's rarely, if ever useful to
2853 record ranges for enumerations. Presumably this is due to
2854 the fact that they're rarely used directly. They are typically
2855 cast into an integer type and used that way. */
2856 if (TREE_CODE (TREE_TYPE (op1
)) != INTEGER_TYPE
)
2859 type
= TREE_TYPE (op1
);
2861 switch (TREE_CODE (cond
))
2875 high
= TYPE_MAX_VALUE (type
);
2880 low
= int_const_binop (PLUS_EXPR
, op1
, integer_one_node
, 1);
2881 high
= TYPE_MAX_VALUE (type
);
2887 low
= TYPE_MIN_VALUE (type
);
2892 high
= int_const_binop (MINUS_EXPR
, op1
, integer_one_node
, 1);
2893 low
= TYPE_MIN_VALUE (type
);
2903 *inverted_p
= inverted
;
2907 /* Record a range created by COND for basic block BB. */
2910 record_range (tree cond
, basic_block bb
, varray_type
*vrp_variables_p
)
2912 /* We explicitly ignore NE_EXPRs. They rarely allow for meaningful
2913 range optimizations and significantly complicate the implementation. */
2914 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<'
2915 && TREE_CODE (cond
) != NE_EXPR
2916 && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond
, 1))) == INTEGER_TYPE
)
2918 struct vrp_element
*element
= ggc_alloc (sizeof (struct vrp_element
));
2919 int ssa_version
= SSA_NAME_VERSION (TREE_OPERAND (cond
, 0));
2921 varray_type
*vrp_records_p
2922 = (varray_type
*)&VARRAY_GENERIC_PTR (vrp_data
, ssa_version
);
2924 element
->low
= NULL
;
2925 element
->high
= NULL
;
2926 element
->cond
= cond
;
2929 if (*vrp_records_p
== NULL
)
2931 VARRAY_GENERIC_PTR_INIT (*vrp_records_p
, 2, "vrp records");
2932 VARRAY_GENERIC_PTR (vrp_data
, ssa_version
) = *vrp_records_p
;
2935 VARRAY_PUSH_GENERIC_PTR (*vrp_records_p
, element
);
2936 if (! *vrp_variables_p
)
2937 VARRAY_TREE_INIT (*vrp_variables_p
, 2, "vrp_variables");
2938 VARRAY_PUSH_TREE (*vrp_variables_p
, TREE_OPERAND (cond
, 0));
2942 /* Given a conditional statement IF_STMT, return the assignment 'X = Y'
2943 known to be true depending on which arm of IF_STMT is taken.
2945 Not all conditional statements will result in a useful assignment.
2946 Return NULL_TREE in that case.
2948 Also enter into the available expression table statements of
2955 This allows us to lookup the condition in a dominated block and
2956 get back a constant indicating if the condition is true. */
2958 static struct eq_expr_value
2959 get_eq_expr_value (tree if_stmt
,
2961 varray_type
*block_avail_exprs_p
,
2963 varray_type
*vrp_variables_p
)
2966 struct eq_expr_value retval
;
2968 cond
= COND_EXPR_COND (if_stmt
);
2972 /* If the conditional is a single variable 'X', return 'X = 1' for
2973 the true arm and 'X = 0' on the false arm. */
2974 if (TREE_CODE (cond
) == SSA_NAME
)
2977 retval
.src
= (true_arm
? integer_one_node
: integer_zero_node
);
2981 /* If we have a comparison expression, then record its result into
2982 the available expression table. */
2983 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
2985 tree op0
= TREE_OPERAND (cond
, 0);
2986 tree op1
= TREE_OPERAND (cond
, 1);
2988 /* Special case comparing booleans against a constant as we know
2989 the value of OP0 on both arms of the branch. ie, we can record
2990 an equivalence for OP0 rather than COND. */
2991 if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
2992 && TREE_CODE (op0
) == SSA_NAME
2993 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
2994 && is_gimple_min_invariant (op1
))
2996 if ((TREE_CODE (cond
) == EQ_EXPR
&& true_arm
)
2997 || (TREE_CODE (cond
) == NE_EXPR
&& ! true_arm
))
3003 if (integer_zerop (op1
))
3004 retval
.src
= boolean_true_node
;
3006 retval
.src
= boolean_false_node
;
3012 if (TREE_CODE (op0
) == SSA_NAME
3013 && (is_gimple_min_invariant (op1
) || TREE_CODE (op1
) == SSA_NAME
))
3015 tree inverted
= invert_truthvalue (cond
);
3017 /* When we find an available expression in the hash table, we replace
3018 the expression with the LHS of the statement in the hash table.
3020 So, we want to build statements such as "1 = <condition>" on the
3021 true arm and "0 = <condition>" on the false arm. That way if we
3022 find the expression in the table, we will replace it with its
3023 known constant value. Also insert inversions of the result and
3024 condition into the hash table. */
3027 record_cond (cond
, boolean_true_node
, block_avail_exprs_p
);
3028 record_cond (inverted
, boolean_false_node
, block_avail_exprs_p
);
3030 if (TREE_CONSTANT (op1
))
3031 record_range (cond
, bb
, vrp_variables_p
);
3033 /* If the conditional is of the form 'X == Y', return 'X = Y'
3034 for the true arm. */
3035 if (TREE_CODE (cond
) == EQ_EXPR
)
3045 record_cond (inverted
, boolean_true_node
, block_avail_exprs_p
);
3046 record_cond (cond
, boolean_false_node
, block_avail_exprs_p
);
3048 if (TREE_CONSTANT (op1
))
3049 record_range (inverted
, bb
, vrp_variables_p
);
3051 /* If the conditional is of the form 'X != Y', return 'X = Y'
3052 for the false arm. */
3053 if (TREE_CODE (cond
) == NE_EXPR
)
3066 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
3067 MODIFY_EXPR statements. We compute a value number for expressions using
3068 the code of the expression and the SSA numbers of its operands. */
3071 avail_expr_hash (const void *p
)
3073 stmt_ann_t ann
= ((struct expr_hash_elt
*)p
)->ann
;
3074 tree rhs
= ((struct expr_hash_elt
*)p
)->rhs
;
3079 /* iterative_hash_expr knows how to deal with any expression and
3080 deals with commutative operators as well, so just use it instead
3081 of duplicating such complexities here. */
3082 val
= iterative_hash_expr (rhs
, val
);
3084 /* If the hash table entry is not associated with a statement, then we
3085 can just hash the expression and not worry about virtual operands
3090 /* Add the SSA version numbers of every vuse operand. This is important
3091 because compound variables like arrays are not renamed in the
3092 operands. Rather, the rename is done on the virtual variable
3093 representing all the elements of the array. */
3094 vuses
= VUSE_OPS (ann
);
3095 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
3096 val
= iterative_hash_expr (VUSE_OP (vuses
, i
), val
);
3103 avail_expr_eq (const void *p1
, const void *p2
)
3105 stmt_ann_t ann1
= ((struct expr_hash_elt
*)p1
)->ann
;
3106 tree rhs1
= ((struct expr_hash_elt
*)p1
)->rhs
;
3107 stmt_ann_t ann2
= ((struct expr_hash_elt
*)p2
)->ann
;
3108 tree rhs2
= ((struct expr_hash_elt
*)p2
)->rhs
;
3110 /* If they are the same physical expression, return true. */
3111 if (rhs1
== rhs2
&& ann1
== ann2
)
3114 /* If their codes are not equal, then quit now. */
3115 if (TREE_CODE (rhs1
) != TREE_CODE (rhs2
))
3118 /* In case of a collision, both RHS have to be identical and have the
3119 same VUSE operands. */
3120 if ((TREE_TYPE (rhs1
) == TREE_TYPE (rhs2
)
3121 || lang_hooks
.types_compatible_p (TREE_TYPE (rhs1
), TREE_TYPE (rhs2
)))
3122 && operand_equal_p (rhs1
, rhs2
, OEP_PURE_SAME
))
3124 vuse_optype ops1
= NULL
;
3125 vuse_optype ops2
= NULL
;
3126 size_t num_ops1
= 0;
3127 size_t num_ops2
= 0;
3132 ops1
= VUSE_OPS (ann1
);
3133 num_ops1
= NUM_VUSES (ops1
);
3138 ops2
= VUSE_OPS (ann2
);
3139 num_ops2
= NUM_VUSES (ops2
);
3142 /* If the number of virtual uses is different, then we consider
3144 if (num_ops1
!= num_ops2
)
3147 for (i
= 0; i
< num_ops1
; i
++)
3148 if (VUSE_OP (ops1
, i
) != VUSE_OP (ops2
, i
))
3151 #ifdef ENABLE_CHECKING
3152 if (((struct expr_hash_elt
*)p1
)->hash
3153 != ((struct expr_hash_elt
*)p2
)->hash
)
3162 /* Given STMT and a pointer to the block local defintions BLOCK_DEFS_P,
3163 register register all objects set by this statement into BLOCK_DEFS_P
3167 register_definitions_for_stmt (stmt_ann_t ann
, varray_type
*block_defs_p
)
3173 defs
= DEF_OPS (ann
);
3174 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
3176 tree def
= DEF_OP (defs
, i
);
3178 /* FIXME: We shouldn't be registering new defs if the variable
3179 doesn't need to be renamed. */
3180 register_new_def (def
, block_defs_p
);
3183 /* Register new virtual definitions made by the statement. */
3184 vdefs
= VDEF_OPS (ann
);
3185 for (i
= 0; i
< NUM_VDEFS (vdefs
); i
++)
3187 /* FIXME: We shouldn't be registering new defs if the variable
3188 doesn't need to be renamed. */
3189 register_new_def (VDEF_RESULT (vdefs
, i
), block_defs_p
);