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"
44 #include "langhooks.h"
46 /* This file implements optimizations on the dominator tree. */
48 /* Hash table with expressions made available during the renaming process.
49 When an assignment of the form X_i = EXPR is found, the statement is
50 stored in this table. If the same expression EXPR is later found on the
51 RHS of another statement, it is replaced with X_i (thus performing
52 global redundancy elimination). Similarly as we pass through conditionals
53 we record the conditional itself as having either a true or false value
55 static htab_t avail_exprs
;
57 /* Structure for entries in the expression hash table.
59 This requires more memory for the hash table entries, but allows us
60 to avoid creating silly tree nodes and annotations for conditionals,
61 eliminates 2 global hash tables and two block local varrays.
63 It also allows us to reduce the number of hash table lookups we
64 have to perform in lookup_avail_expr and finally it allows us to
65 significantly reduce the number of calls into the hashing routine
69 /* The value (lhs) of this expression. */
72 /* The expression (rhs) we want to record. */
75 /* The annotation if this element corresponds to a statement. */
78 /* The hash value for RHS/ann. */
82 /* Table of constant values and copies indexed by SSA name. When the
83 renaming pass finds an assignment of a constant (X_i = C) or a copy
84 assignment from another SSA variable (X_i = Y_j), it creates a mapping
85 between X_i and the RHS in this table. This mapping is used later on,
86 when renaming uses of X_i. If an assignment to X_i is found in this
87 table, instead of using X_i, we use the RHS of the statement stored in
88 this table (thus performing very simplistic copy and constant
90 static varray_type const_and_copies
;
92 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
93 know their exact value. */
94 static bitmap nonzero_vars
;
96 /* Track whether or not we have changed the control flow graph. */
97 static bool cfg_altered
;
99 /* Statistics for dominator optimizations. */
103 long num_exprs_considered
;
107 /* Value range propagation record. Each time we encounter a conditional
108 of the form SSA_NAME COND CONST we create a new vrp_element to record
109 how the condition affects the possible values SSA_NAME may have.
111 Each record contains the condition tested (COND), and the the range of
112 values the variable may legitimately have if COND is true. Note the
113 range of values may be a smaller range than COND specifies if we have
114 recorded other ranges for this variable. Each record also contains the
115 block in which the range was recorded for invalidation purposes.
117 Note that the current known range is computed lazily. This allows us
118 to avoid the overhead of computing ranges which are never queried.
120 When we encounter a conditional, we look for records which constrain
121 the SSA_NAME used in the condition. In some cases those records allow
122 us to determine the condition's result at compile time. In other cases
123 they may allow us to simplify the condition.
125 We also use value ranges to do things like transform signed div/mod
126 operations into unsigned div/mod or to simplify ABS_EXPRs.
128 Simple experiments have shown these optimizations to not be all that
129 useful on switch statements (much to my surprise). So switch statement
130 optimizations are not performed.
132 Note carefully we do not propagate information through each statement
133 in the block. ie, if we know variable X has a value defined of
134 [0, 25] and we encounter Y = X + 1, we do not track a value range
135 for Y (which would be [1, 26] if we cared). Similarly we do not
136 constrain values as we encounter narrowing typecasts, etc. */
140 /* The highest and lowest values the variable in COND may contain when
141 COND is true. Note this may not necessarily be the same values
142 tested by COND if the same variable was used in earlier conditionals.
144 Note this is computed lazily and thus can be NULL indicating that
145 the values have not been computed yet. */
149 /* The actual conditional we recorded. This is needed since we compute
153 /* The basic block where this record was created. We use this to determine
154 when to remove records. */
158 static struct opt_stats_d opt_stats
;
160 /* This virtual array holds pairs of edges which describe a scheduled
161 edge redirection from jump threading.
163 The first entry in each pair is the edge we are going to redirect.
165 The second entry in each pair is the edge leading to our final
166 destination block. By providing this as an edge rather than the
167 final target block itself we can correctly handle redirections
168 when the target block had PHIs which required edge insertions/splitting
169 to remove the PHIs. */
170 static GTY(()) varray_type redirection_edges
;
172 /* A virtual array holding value range records for the variable identified
173 by the index, SSA_VERSION. */
174 static varray_type vrp_data
;
176 /* Datastructure for block local data used during the dominator walk.
177 We maintain a stack of these as we recursively walk down the
180 struct dom_walk_block_data
182 /* Array of all the expressions entered into the global expression
183 hash table by this block. During finalization we use this array to
184 know what expressions to remove from the global expression hash
186 varray_type avail_exprs
;
188 /* Array of dest, src pairs that need to be restored during finalization
189 into the global const/copies table during finalization. */
190 varray_type const_and_copies
;
192 /* Similarly for the nonzero state of variables that needs to be
193 restored during finalization. */
194 varray_type nonzero_vars
;
196 /* Array of statements we need to rescan during finalization for newly
197 exposed variables. */
198 varray_type stmts_to_rescan
;
200 /* Array of variables which have their values constrained by operations
201 in this basic block. We use this during finalization to know
202 which variables need their VRP data updated. */
203 varray_type vrp_variables
;
205 /* Array of tree pairs used to restore the global currdefs to its
206 original state after completing optimization of a block and its
207 dominator children. */
208 varray_type block_defs
;
217 /* Local functions. */
218 static void optimize_stmt (struct dom_walk_data
*,
220 block_stmt_iterator
);
221 static inline tree
get_value_for (tree
, varray_type table
);
222 static inline void set_value_for (tree
, tree
, varray_type table
);
223 static tree
lookup_avail_expr (tree
, varray_type
*, bool);
224 static struct eq_expr_value
get_eq_expr_value (tree
, int, varray_type
*,
225 basic_block
, varray_type
*);
226 static hashval_t
avail_expr_hash (const void *);
227 static int avail_expr_eq (const void *, const void *);
228 static void htab_statistics (FILE *, htab_t
);
229 static void record_cond (tree
, tree
, varray_type
*);
230 static void record_const_or_copy (tree
, tree
, varray_type
*);
231 static void record_equality (tree
, tree
, varray_type
*);
232 static tree
update_rhs_and_lookup_avail_expr (tree
, tree
, varray_type
*,
234 static tree
simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*,
235 tree
, stmt_ann_t
, int);
236 static tree
simplify_cond_and_lookup_avail_expr (tree
, varray_type
*,
238 static tree
simplify_switch_and_lookup_avail_expr (tree
, varray_type
*,
240 static tree
find_equivalent_equality_comparison (tree
);
241 static void record_range (tree
, basic_block
, varray_type
*);
242 static bool extract_range_from_cond (tree
, tree
*, tree
*, int *);
243 static void record_equivalences_from_phis (struct dom_walk_data
*, basic_block
);
244 static void record_equivalences_from_incoming_edge (struct dom_walk_data
*,
246 static bool eliminate_redundant_computations (struct dom_walk_data
*,
248 static void record_equivalences_from_stmt (tree
, varray_type
*, varray_type
*,
250 static void thread_across_edge (struct dom_walk_data
*, edge
);
251 static void dom_opt_finalize_block (struct dom_walk_data
*, basic_block
);
252 static void dom_opt_initialize_block_local_data (struct dom_walk_data
*,
254 static void dom_opt_initialize_block (struct dom_walk_data
*, basic_block
);
255 static void cprop_into_phis (struct dom_walk_data
*, basic_block
);
256 static void remove_local_expressions_from_table (varray_type locals
,
259 static void restore_vars_to_original_value (varray_type locals
,
262 static void restore_currdefs_to_original_value (varray_type locals
,
264 static void register_definitions_for_stmt (stmt_ann_t
, varray_type
*);
265 static void redirect_edges_and_update_ssa_graph (varray_type
);
267 /* Local version of fold that doesn't introduce cruft. */
274 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
275 may have been added by fold, and "useless" type conversions that might
276 now be apparent due to propagation. */
277 STRIP_MAIN_TYPE_NOPS (t
);
278 STRIP_USELESS_TYPE_CONVERSION (t
);
283 /* Return the value associated with variable VAR in TABLE. */
286 get_value_for (tree var
, varray_type table
)
288 return VARRAY_TREE (table
, SSA_NAME_VERSION (var
));
291 /* Associate VALUE to variable VAR in TABLE. */
294 set_value_for (tree var
, tree value
, varray_type table
)
296 VARRAY_TREE (table
, SSA_NAME_VERSION (var
)) = value
;
299 /* REDIRECTION_EDGES contains edge pairs where we want to revector the
300 destination of the first edge to the destination of the second edge.
302 These redirections may significantly change the SSA graph since we
303 allow redirection through blocks with PHI nodes and blocks with
304 real instructions in some cases.
306 This routine will perform the requested redirections and incrementally
307 update the SSA graph.
309 Note in some cases requested redirections may be ignored as they can
310 not be safely implemented. */
313 redirect_edges_and_update_ssa_graph (varray_type redirection_edges
)
317 size_t old_num_referenced_vars
= num_referenced_vars
;
319 /* First note any variables which we are going to have to take
321 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
323 block_stmt_iterator bsi
;
328 e
= VARRAY_EDGE (redirection_edges
, i
);
329 tgt
= VARRAY_EDGE (redirection_edges
, i
+ 1)->dest
;
331 /* All variables referenced in PHI nodes we bypass must be
333 for (phi
= phi_nodes (e
->dest
); phi
; phi
= TREE_CHAIN (phi
))
335 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
336 bitmap_set_bit (vars_to_rename
, var_ann (result
)->uid
);
339 /* Any variables set by statements at the start of the block we
340 are bypassing must also be taken our of SSA form. */
341 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
346 tree stmt
= bsi_stmt (bsi
);
347 stmt_ann_t ann
= stmt_ann (stmt
);
349 if (TREE_CODE (stmt
) == COND_EXPR
)
352 get_stmt_operands (stmt
);
354 defs
= DEF_OPS (ann
);
355 for (j
= 0; j
< NUM_DEFS (defs
); j
++)
357 tree op
= SSA_NAME_VAR (DEF_OP (defs
, j
));
358 bitmap_set_bit (vars_to_rename
, var_ann (op
)->uid
);
361 vdefs
= VDEF_OPS (ann
);
362 for (j
= 0; j
< NUM_VDEFS (vdefs
); j
++)
364 tree op
= VDEF_RESULT (vdefs
, j
);
365 bitmap_set_bit (vars_to_rename
, var_ann (op
)->uid
);
369 /* Finally, any variables in PHI nodes at our final destination
370 must also be taken our of SSA form. */
371 for (phi
= phi_nodes (tgt
); phi
; phi
= TREE_CHAIN (phi
))
373 tree result
= SSA_NAME_VAR (PHI_RESULT (phi
));
376 bitmap_set_bit (vars_to_rename
, var_ann (result
)->uid
);
378 for (j
= 0; j
< PHI_NUM_ARGS (phi
); j
++)
380 tree arg
= PHI_ARG_DEF (phi
, j
);
382 if (TREE_CODE (arg
) != SSA_NAME
)
385 arg
= SSA_NAME_VAR (arg
);
386 bitmap_set_bit (vars_to_rename
, var_ann (arg
)->uid
);
391 /* Take those selected variables out of SSA form. This must be
392 done before we start redirecting edges. */
393 if (bitmap_first_set_bit (vars_to_rename
) >= 0)
394 rewrite_vars_out_of_ssa (vars_to_rename
);
396 /* The out of SSA translation above may split the edge from
397 E->src to E->dest. This could potentially cause us to lose
398 an assignment leading to invalid warnings about uninitialized
399 variables or incorrect code.
401 Luckily, we can detect this by looking at the last statement
402 in E->dest. If it is not a COND_EXPR or SWITCH_EXPR, then
403 the edge was split and instead of E, we want E->dest->succ. */
404 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
406 edge e
= VARRAY_EDGE (redirection_edges
, i
);
407 tree last
= last_stmt (e
->dest
);
410 && TREE_CODE (last
) != COND_EXPR
411 && TREE_CODE (last
) != SWITCH_EXPR
)
415 #ifdef ENABLE_CHECKING
416 /* There should only be a single successor if the
417 original edge was split. */
421 /* Replace the edge in REDIRECTION_EDGES for the
423 VARRAY_EDGE (redirection_edges
, i
) = e
;
427 /* If we created any new variables as part of the out-of-ssa
428 translation, then any jump threads must be invalidated if they
429 bypass a block in which we skipped instructions.
431 This is necessary as instructions which appeared to be NOPS
432 may be necessary after the out-of-ssa translation. */
433 if (num_referenced_vars
!= old_num_referenced_vars
)
435 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
437 block_stmt_iterator bsi
;
440 e
= VARRAY_EDGE (redirection_edges
, i
);
441 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
443 tree stmt
= bsi_stmt (bsi
);
445 if (IS_EMPTY_STMT (stmt
)
446 || TREE_CODE (stmt
) == LABEL_EXPR
)
449 if (TREE_CODE (stmt
) == COND_EXPR
)
452 /* Invalidate the jump thread. */
453 VARRAY_EDGE (redirection_edges
, i
) = NULL
;
454 VARRAY_EDGE (redirection_edges
, i
+ 1) = NULL
;
460 /* Now redirect the edges. */
461 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (redirection_edges
); i
+= 2)
466 e
= VARRAY_EDGE (redirection_edges
, i
);
470 tgt
= VARRAY_EDGE (redirection_edges
, i
+ 1)->dest
;
473 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
474 fprintf (dump_file
, " Threaded jump %d --> %d to %d\n",
475 e
->src
->index
, e
->dest
->index
, tgt
->index
);
479 e
= redirect_edge_and_branch (e
, tgt
);
480 PENDING_STMT (e
) = NULL_TREE
;
482 /* Updating the dominance information would be nontrivial. */
483 free_dominance_info (CDI_DOMINATORS
);
485 if ((dump_file
&& (dump_flags
& TDF_DETAILS
))
487 fprintf (dump_file
, " basic block %d created\n",
493 VARRAY_CLEAR (redirection_edges
);
495 for (i
= old_num_referenced_vars
; i
< num_referenced_vars
; i
++)
497 bitmap_set_bit (vars_to_rename
, i
);
498 var_ann (referenced_var (i
))->out_of_ssa_tag
= 0;
502 /* Jump threading, redundancy elimination and const/copy propagation.
504 Optimize function FNDECL based on a walk through the dominator tree.
506 This pass may expose new symbols that need to be renamed into SSA. For
507 every new symbol exposed, its corresponding bit will be set in
510 PHASE indicates which dump file from the DUMP_FILES array to use when
511 dumping debugging information. */
514 tree_ssa_dominator_optimize (void)
517 struct dom_walk_data walk_data
;
520 for (i
= 0; i
< num_referenced_vars
; i
++)
521 var_ann (referenced_var (i
))->current_def
= NULL
;
523 /* Mark loop edges so we avoid threading across loop boundaries.
524 This may result in transforming natural loop into irreducible
526 mark_dfs_back_edges ();
528 /* Create our hash tables. */
529 avail_exprs
= htab_create (1024, avail_expr_hash
, avail_expr_eq
, free
);
530 VARRAY_TREE_INIT (const_and_copies
, highest_ssa_version
, "const_and_copies");
531 nonzero_vars
= BITMAP_XMALLOC ();
532 VARRAY_EDGE_INIT (redirection_edges
, 20, "redirection_edges");
533 VARRAY_GENERIC_PTR_INIT (vrp_data
, highest_ssa_version
, "vrp_data");
535 /* Setup callbacks for the generic dominator tree walker. */
536 walk_data
.walk_stmts_backward
= false;
537 walk_data
.dom_direction
= CDI_DOMINATORS
;
538 walk_data
.initialize_block_local_data
= dom_opt_initialize_block_local_data
;
539 walk_data
.before_dom_children_before_stmts
= dom_opt_initialize_block
;
540 walk_data
.before_dom_children_walk_stmts
= optimize_stmt
;
541 walk_data
.before_dom_children_after_stmts
= cprop_into_phis
;
542 walk_data
.after_dom_children_before_stmts
= NULL
;
543 walk_data
.after_dom_children_walk_stmts
= NULL
;
544 walk_data
.after_dom_children_after_stmts
= dom_opt_finalize_block
;
545 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
546 When we attach more stuff we'll need to fill this out with a real
548 walk_data
.global_data
= NULL
;
549 walk_data
.block_local_data_size
= sizeof (struct dom_walk_block_data
);
551 /* Now initialize the dominator walker. */
552 init_walk_dominator_tree (&walk_data
);
554 /* Reset block_forwardable in each block's annotation. We use that
555 attribute when threading through COND_EXPRs. */
557 bb_ann (bb
)->forwardable
= 1;
559 calculate_dominance_info (CDI_DOMINATORS
);
561 /* If we prove certain blocks are unreachable, then we want to
562 repeat the dominator optimization process as PHI nodes may
563 have turned into copies which allows better propagation of
564 values. So we repeat until we do not identify any new unreachable
568 /* Optimize the dominator tree. */
571 /* Recursively walk the dominator tree optimizing statements. */
572 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
574 /* Wipe the hash tables. */
576 if (VARRAY_ACTIVE_SIZE (redirection_edges
) > 0)
577 redirect_edges_and_update_ssa_graph (redirection_edges
);
579 /* We may have made some basic blocks unreachable, remove them. */
580 cfg_altered
|= delete_unreachable_blocks ();
582 /* If the CFG was altered, then recompute the dominator tree. This
583 is not strictly needed if we only removed unreachable blocks, but
584 may produce better results. If we threaded jumps, then rebuilding
585 the dominator tree is strictly necessary. */
589 calculate_dominance_info (CDI_DOMINATORS
);
592 /* If we are going to iterate (CFG_ALTERED is true), then we must
593 perform any queued renaming before the next iteration. */
595 && bitmap_first_set_bit (vars_to_rename
) >= 0)
598 bitmap_clear (vars_to_rename
);
600 /* The into SSA translation may have created new SSA_NAMES whic
601 affect the size of CONST_AND_COPIES and VRP_DATA. */
602 VARRAY_GROW (const_and_copies
, highest_ssa_version
);
603 VARRAY_GROW (vrp_data
, highest_ssa_version
);
606 /* Reinitialize the various tables. */
607 bitmap_clear (nonzero_vars
);
608 htab_empty (avail_exprs
);
609 VARRAY_CLEAR (const_and_copies
);
610 VARRAY_CLEAR (vrp_data
);
612 for (i
= 0; i
< num_referenced_vars
; i
++)
613 var_ann (referenced_var (i
))->current_def
= NULL
;
617 /* Remove any unreachable blocks left behind and linearize the CFG. */
620 /* Debugging dumps. */
621 if (dump_file
&& (dump_flags
& TDF_STATS
))
622 dump_dominator_optimization_stats (dump_file
);
624 /* We emptyed the hash table earlier, now delete it completely. */
625 htab_delete (avail_exprs
);
627 /* It is not nocessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
628 CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
629 of the do-while loop above. */
631 /* And finalize the dominator walker. */
632 fini_walk_dominator_tree (&walk_data
);
636 gate_dominator (void)
638 return flag_tree_dom
!= 0;
641 struct tree_opt_pass pass_dominator
=
644 gate_dominator
, /* gate */
645 tree_ssa_dominator_optimize
, /* execute */
648 0, /* static_pass_number */
649 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
650 PROP_cfg
| PROP_ssa
, /* properties_required */
651 0, /* properties_provided */
652 0, /* properties_destroyed */
653 0, /* todo_flags_start */
654 TODO_dump_func
| TODO_rename_vars
655 | TODO_verify_ssa
/* todo_flags_finish */
659 /* We are exiting BB, see if the target block begins with a conditional
660 jump which has a known value when reached via BB. */
663 thread_across_edge (struct dom_walk_data
*walk_data
, edge e
)
665 struct dom_walk_block_data
*bd
666 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
667 block_stmt_iterator bsi
;
671 /* Each PHI creates a temporary equivalence, record them. */
672 for (phi
= phi_nodes (e
->dest
); phi
; phi
= TREE_CHAIN (phi
))
674 tree src
= PHI_ARG_DEF (phi
, phi_arg_from_edge (phi
, e
));
675 tree dst
= PHI_RESULT (phi
);
676 record_const_or_copy (dst
, src
, &bd
->const_and_copies
);
677 register_new_def (dst
, &bd
->block_defs
);
680 for (bsi
= bsi_start (e
->dest
); ! bsi_end_p (bsi
); bsi_next (&bsi
))
682 tree lhs
, cached_lhs
;
684 stmt
= bsi_stmt (bsi
);
686 /* Ignore empty statements and labels. */
687 if (IS_EMPTY_STMT (stmt
) || TREE_CODE (stmt
) == LABEL_EXPR
)
690 /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
691 value, then stop our search here. Ideally when we stop a
692 search we stop on a COND_EXPR or SWITCH_EXPR. */
693 if (TREE_CODE (stmt
) != MODIFY_EXPR
694 || TREE_CODE (TREE_OPERAND (stmt
, 0)) != SSA_NAME
)
697 /* At this point we have a statement which assigns an RHS to an
698 SSA_VAR on the LHS. We want to prove that the RHS is already
699 available and that its value is held in the current definition
700 of the LHS -- meaning that this assignment is a NOP when
701 reached via edge E. */
702 if (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
)
703 cached_lhs
= TREE_OPERAND (stmt
, 1);
705 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
707 lhs
= TREE_OPERAND (stmt
, 0);
709 /* This can happen if we thread around to the start of a loop. */
710 if (lhs
== cached_lhs
)
713 /* If we did not find RHS in the hash table, then try again after
714 temporarily const/copy propagating the operands. */
717 /* Copy the operands. */
718 stmt_ann_t ann
= stmt_ann (stmt
);
719 use_optype uses
= USE_OPS (ann
);
720 vuse_optype vuses
= VUSE_OPS (ann
);
721 tree
*uses_copy
= xcalloc (NUM_USES (uses
), sizeof (tree
));
722 tree
*vuses_copy
= xcalloc (NUM_VUSES (vuses
), sizeof (tree
));
725 /* Make a copy of the uses into USES_COPY, then cprop into
727 for (i
= 0; i
< NUM_USES (uses
); i
++)
731 uses_copy
[i
] = USE_OP (uses
, i
);
732 if (TREE_CODE (USE_OP (uses
, i
)) == SSA_NAME
)
733 tmp
= get_value_for (USE_OP (uses
, i
), const_and_copies
);
735 *USE_OP_PTR (uses
, i
) = tmp
;
738 /* Similarly for virtual uses. */
739 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
743 vuses_copy
[i
] = VUSE_OP (vuses
, i
);
744 if (TREE_CODE (VUSE_OP (vuses
, i
)) == SSA_NAME
)
745 tmp
= get_value_for (VUSE_OP (vuses
, i
), const_and_copies
);
747 VUSE_OP (vuses
, i
) = tmp
;
750 /* Try to lookup the new expression. */
751 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
753 /* Restore the statement's original uses/defs. */
754 for (i
= 0; i
< NUM_USES (uses
); i
++)
755 *USE_OP_PTR (uses
, i
) = uses_copy
[i
];
757 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
758 VUSE_OP (vuses
, i
) = vuses_copy
[i
];
763 /* If we still did not find the expression in the hash table,
764 then we can not ignore this statement. */
769 /* If the expression in the hash table was not assigned to an
770 SSA_NAME, then we can not ignore this statement. */
771 if (TREE_CODE (cached_lhs
) != SSA_NAME
)
774 /* If we have different underlying variables, then we can not
775 ignore this statement. */
776 if (SSA_NAME_VAR (cached_lhs
) != SSA_NAME_VAR (lhs
))
779 /* If CACHED_LHS does not represent the current value of the undering
780 variable in CACHED_LHS/LHS, then we can not ignore this statement. */
781 if (var_ann (SSA_NAME_VAR (lhs
))->current_def
!= cached_lhs
)
784 /* If we got here, then we can ignore this statement and continue
785 walking through the statements in the block looking for a threadable
788 We want to record an equivalence lhs = cache_lhs so that if
789 the result of this statement is used later we can copy propagate
791 record_const_or_copy (lhs
, cached_lhs
, &bd
->const_and_copies
);
792 register_new_def (lhs
, &bd
->block_defs
);
795 /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
796 arm will be taken. */
798 && (TREE_CODE (stmt
) == COND_EXPR
799 || TREE_CODE (stmt
) == SWITCH_EXPR
))
801 tree cond
, cached_lhs
;
804 /* Do not forward entry edges into the loop. In the case loop
805 has multiple entry edges we may end up in constructing irreducible
807 ??? We may consider forwarding the edges in the case all incoming
808 edges forward to the same destination block. */
809 if (!e
->flags
& EDGE_DFS_BACK
)
811 for (e1
= e
->dest
->pred
; e
; e
= e
->pred_next
)
812 if (e1
->flags
& EDGE_DFS_BACK
)
818 /* Now temporarily cprop the operands and try to find the resulting
819 expression in the hash tables. */
820 if (TREE_CODE (stmt
) == COND_EXPR
)
821 cond
= COND_EXPR_COND (stmt
);
823 cond
= SWITCH_COND (stmt
);
825 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
827 tree dummy_cond
, op0
, op1
;
828 enum tree_code cond_code
;
830 op0
= TREE_OPERAND (cond
, 0);
831 op1
= TREE_OPERAND (cond
, 1);
832 cond_code
= TREE_CODE (cond
);
834 /* Get the current value of both operands. */
835 if (TREE_CODE (op0
) == SSA_NAME
)
837 tree tmp
= get_value_for (op0
, const_and_copies
);
842 if (TREE_CODE (op1
) == SSA_NAME
)
844 tree tmp
= get_value_for (op1
, const_and_copies
);
849 /* Stuff the operator and operands into our dummy conditional
850 expression, creating the dummy conditional if necessary. */
851 dummy_cond
= walk_data
->global_data
;
854 dummy_cond
= build (cond_code
, boolean_type_node
, op0
, op1
);
855 dummy_cond
= build (COND_EXPR
, void_type_node
,
856 dummy_cond
, NULL
, NULL
);
857 walk_data
->global_data
= dummy_cond
;
861 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), cond_code
);
862 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op0
;
863 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1) = op1
;
866 /* If the conditional folds to an invariant, then we are done,
867 otherwise look it up in the hash tables. */
868 cached_lhs
= local_fold (COND_EXPR_COND (dummy_cond
));
869 if (! is_gimple_min_invariant (cached_lhs
))
870 cached_lhs
= lookup_avail_expr (dummy_cond
, NULL
, false);
871 if (!cached_lhs
|| ! is_gimple_min_invariant (cached_lhs
))
873 stmt_ann_t ann
= get_stmt_ann (dummy_cond
);
874 cached_lhs
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
880 /* We can have conditionals which just test the state of a
881 variable rather than use a relational operator. These are
882 simpler to handle. */
883 else if (TREE_CODE (cond
) == SSA_NAME
)
886 cached_lhs
= get_value_for (cached_lhs
, const_and_copies
);
887 if (cached_lhs
&& ! is_gimple_min_invariant (cached_lhs
))
891 cached_lhs
= lookup_avail_expr (stmt
, NULL
, false);
895 edge taken_edge
= find_taken_edge (e
->dest
, cached_lhs
);
896 basic_block dest
= (taken_edge
? taken_edge
->dest
: NULL
);
901 /* If we have a known destination for the conditional, then
902 we can perform this optimization, which saves at least one
903 conditional jump each time it applies since we get to
904 bypass the conditional at our original destination.
906 Note that we can either thread through a block with PHIs
907 or to a block with PHIs, but not both. At this time the
908 bookkeeping to keep the CFG & SSA up-to-date has proven
912 int saved_forwardable
= bb_ann (e
->src
)->forwardable
;
915 bb_ann (e
->src
)->forwardable
= 0;
916 tmp_edge
= tree_block_forwards_to (dest
);
917 taken_edge
= (tmp_edge
? tmp_edge
: taken_edge
);
918 bb_ann (e
->src
)->forwardable
= saved_forwardable
;
919 VARRAY_PUSH_EDGE (redirection_edges
, e
);
920 VARRAY_PUSH_EDGE (redirection_edges
, taken_edge
);
927 /* Initialize the local stacks.
929 AVAIL_EXPRS stores all the expressions made available in this block.
931 CONST_AND_COPIES stores var/value pairs to restore at the end of this
934 NONZERO_VARS stores the vars which have a nonzero value made in this
937 STMTS_TO_RESCAN is a list of statements we will rescan for operands.
939 VRP_VARIABLES is the list of variables which have had their values
940 constrained by an operation in this block.
942 These stacks are cleared in the finalization routine run for each
946 dom_opt_initialize_block_local_data (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
947 basic_block bb ATTRIBUTE_UNUSED
,
948 bool recycled ATTRIBUTE_UNUSED
)
950 #ifdef ENABLE_CHECKING
951 struct dom_walk_block_data
*bd
952 = (struct dom_walk_block_data
*)VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
954 /* We get cleared memory from the allocator, so if the memory is not
955 cleared, then we are re-using a previously allocated entry. In
956 that case, we can also re-use the underlying virtual arrays. Just
957 make sure we clear them before using them! */
960 if (bd
->avail_exprs
&& VARRAY_ACTIVE_SIZE (bd
->avail_exprs
) > 0)
962 if (bd
->const_and_copies
&& VARRAY_ACTIVE_SIZE (bd
->const_and_copies
) > 0)
964 if (bd
->nonzero_vars
&& VARRAY_ACTIVE_SIZE (bd
->nonzero_vars
) > 0)
966 if (bd
->stmts_to_rescan
&& VARRAY_ACTIVE_SIZE (bd
->stmts_to_rescan
) > 0)
968 if (bd
->vrp_variables
&& VARRAY_ACTIVE_SIZE (bd
->vrp_variables
) > 0)
970 if (bd
->block_defs
&& VARRAY_ACTIVE_SIZE (bd
->block_defs
) > 0)
976 /* Initialize local stacks for this optimizer and record equivalences
977 upon entry to BB. Equivalences can come from the edge traversed to
978 reach BB or they may come from PHI nodes at the start of BB. */
981 dom_opt_initialize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
983 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
984 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
986 record_equivalences_from_incoming_edge (walk_data
, bb
);
988 /* PHI nodes can create equivalences too. */
989 record_equivalences_from_phis (walk_data
, bb
);
992 /* Given an expression EXPR (a relational expression or a statement),
993 initialize the hash table element pointed by by ELEMENT. */
996 initialize_hash_element (tree expr
, tree lhs
, struct expr_hash_elt
*element
)
998 /* Hash table elements may be based on conditional expressions or statements.
1000 For the former case, we have no annotation and we want to hash the
1001 conditional expression. In the latter case we have an annotation and
1002 we want to record the expression the statement evaluates. */
1003 if (TREE_CODE_CLASS (TREE_CODE (expr
)) == '<'
1004 || TREE_CODE (expr
) == TRUTH_NOT_EXPR
)
1006 element
->ann
= NULL
;
1007 element
->rhs
= expr
;
1009 else if (TREE_CODE (expr
) == COND_EXPR
)
1011 element
->ann
= stmt_ann (expr
);
1012 element
->rhs
= COND_EXPR_COND (expr
);
1014 else if (TREE_CODE (expr
) == SWITCH_EXPR
)
1016 element
->ann
= stmt_ann (expr
);
1017 element
->rhs
= SWITCH_COND (expr
);
1019 else if (TREE_CODE (expr
) == RETURN_EXPR
&& TREE_OPERAND (expr
, 0))
1021 element
->ann
= stmt_ann (expr
);
1022 element
->rhs
= TREE_OPERAND (TREE_OPERAND (expr
, 0), 1);
1026 element
->ann
= stmt_ann (expr
);
1027 element
->rhs
= TREE_OPERAND (expr
, 1);
1031 element
->hash
= avail_expr_hash (element
);
1034 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
1035 LIMIT entries left in LOCALs. */
1038 remove_local_expressions_from_table (varray_type locals
,
1045 /* Remove all the expressions made available in this block. */
1046 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1048 struct expr_hash_elt element
;
1049 tree expr
= VARRAY_TOP_TREE (locals
);
1050 VARRAY_POP (locals
);
1052 initialize_hash_element (expr
, NULL
, &element
);
1053 htab_remove_elt_with_hash (table
, &element
, element
.hash
);
1057 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
1058 state, stopping when there are LIMIT entires left in LOCALs. */
1061 restore_nonzero_vars_to_original_value (varray_type locals
,
1068 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1070 tree name
= VARRAY_TOP_TREE (locals
);
1071 VARRAY_POP (locals
);
1072 bitmap_clear_bit (table
, SSA_NAME_VERSION (name
));
1076 /* Use the source/dest pairs in LOCALS to restore TABLE to its original
1077 state, stopping when there are LIMIT entires left in LOCALs. */
1080 restore_vars_to_original_value (varray_type locals
,
1087 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1089 tree prev_value
, dest
;
1091 prev_value
= VARRAY_TOP_TREE (locals
);
1092 VARRAY_POP (locals
);
1093 dest
= VARRAY_TOP_TREE (locals
);
1094 VARRAY_POP (locals
);
1096 set_value_for (dest
, prev_value
, table
);
1100 /* Similar to restore_vars_to_original_value, except that it restores
1101 CURRDEFS to its original value. */
1103 restore_currdefs_to_original_value (varray_type locals
, unsigned limit
)
1108 /* Restore CURRDEFS to its original state. */
1109 while (VARRAY_ACTIVE_SIZE (locals
) > limit
)
1111 tree tmp
= VARRAY_TOP_TREE (locals
);
1112 tree saved_def
, var
;
1114 VARRAY_POP (locals
);
1116 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
1117 definition of its underlying variable. If we recorded anything
1118 else, it must have been an _DECL node and its current reaching
1119 definition must have been NULL. */
1120 if (TREE_CODE (tmp
) == SSA_NAME
)
1123 var
= SSA_NAME_VAR (saved_def
);
1131 var_ann (var
)->current_def
= saved_def
;
1135 /* We have finished processing the dominator children of BB, perform
1136 any finalization actions in preparation for leaving this node in
1137 the dominator tree. */
1140 dom_opt_finalize_block (struct dom_walk_data
*walk_data
, basic_block bb
)
1142 struct dom_walk_block_data
*bd
1143 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1146 /* If we are at a leaf node in the dominator graph, see if we can thread
1147 the edge from BB through its successor.
1149 Do this before we remove entries from our equivalence tables. */
1151 && ! bb
->succ
->succ_next
1152 && (bb
->succ
->flags
& EDGE_ABNORMAL
) == 0
1153 && (get_immediate_dominator (CDI_DOMINATORS
, bb
->succ
->dest
) != bb
1154 || phi_nodes (bb
->succ
->dest
)))
1157 thread_across_edge (walk_data
, bb
->succ
);
1159 else if ((last
= last_stmt (bb
))
1160 && TREE_CODE (last
) == COND_EXPR
1161 && (TREE_CODE_CLASS (TREE_CODE (COND_EXPR_COND (last
))) == '<'
1162 || TREE_CODE (COND_EXPR_COND (last
)) == SSA_NAME
)
1164 && (bb
->succ
->flags
& EDGE_ABNORMAL
) == 0
1165 && bb
->succ
->succ_next
1166 && (bb
->succ
->succ_next
->flags
& EDGE_ABNORMAL
) == 0
1167 && ! bb
->succ
->succ_next
->succ_next
)
1169 edge true_edge
, false_edge
;
1170 tree cond
, inverted
= NULL
;
1171 enum tree_code cond_code
;
1173 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1175 cond
= COND_EXPR_COND (last
);
1176 cond_code
= TREE_CODE (cond
);
1178 if (TREE_CODE_CLASS (cond_code
) == '<')
1179 inverted
= invert_truthvalue (cond
);
1181 /* If the THEN arm is the end of a dominator tree or has PHI nodes,
1182 then try to thread through its edge. */
1183 if (get_immediate_dominator (CDI_DOMINATORS
, true_edge
->dest
) != bb
1184 || phi_nodes (true_edge
->dest
))
1186 unsigned avail_expr_limit
;
1187 unsigned const_and_copies_limit
;
1188 unsigned currdefs_limit
;
1191 = bd
->avail_exprs
? VARRAY_ACTIVE_SIZE (bd
->avail_exprs
) : 0;
1192 const_and_copies_limit
1193 = bd
->const_and_copies
? VARRAY_ACTIVE_SIZE (bd
->const_and_copies
)
1196 = bd
->block_defs
? VARRAY_ACTIVE_SIZE (bd
->block_defs
) : 0;
1198 /* Record any equivalences created by following this edge. */
1199 if (TREE_CODE_CLASS (cond_code
) == '<')
1201 record_cond (cond
, boolean_true_node
, &bd
->avail_exprs
);
1202 record_cond (inverted
, boolean_false_node
, &bd
->avail_exprs
);
1204 else if (cond_code
== SSA_NAME
)
1205 record_const_or_copy (cond
, boolean_true_node
,
1206 &bd
->const_and_copies
);
1208 /* Now thread the edge. */
1209 thread_across_edge (walk_data
, true_edge
);
1211 /* And restore the various tables to their state before
1212 we threaded this edge. */
1213 remove_local_expressions_from_table (bd
->avail_exprs
,
1216 restore_vars_to_original_value (bd
->const_and_copies
,
1217 const_and_copies_limit
,
1219 restore_currdefs_to_original_value (bd
->block_defs
, currdefs_limit
);
1222 /* Similarly for the ELSE arm. */
1223 if (get_immediate_dominator (CDI_DOMINATORS
, false_edge
->dest
) != bb
1224 || phi_nodes (false_edge
->dest
))
1226 /* Record any equivalences created by following this edge. */
1227 if (TREE_CODE_CLASS (cond_code
) == '<')
1229 record_cond (cond
, boolean_false_node
, &bd
->avail_exprs
);
1230 record_cond (inverted
, boolean_true_node
, &bd
->avail_exprs
);
1232 else if (cond_code
== SSA_NAME
)
1233 record_const_or_copy (cond
, boolean_false_node
,
1234 &bd
->const_and_copies
);
1236 thread_across_edge (walk_data
, false_edge
);
1238 /* No need to remove local expressions from our tables
1239 or restore vars to their original value as that will
1240 be done immediately below. */
1244 remove_local_expressions_from_table (bd
->avail_exprs
, 0, avail_exprs
);
1245 restore_nonzero_vars_to_original_value (bd
->nonzero_vars
, 0, nonzero_vars
);
1246 restore_vars_to_original_value (bd
->const_and_copies
, 0, const_and_copies
);
1247 restore_currdefs_to_original_value (bd
->block_defs
, 0);
1249 /* Remove VRP records associated with this basic block. They are no
1252 To be efficient, we note which variables have had their values
1253 constrained in this block. So walk over each variable in the
1254 VRP_VARIABLEs array. */
1255 while (bd
->vrp_variables
&& VARRAY_ACTIVE_SIZE (bd
->vrp_variables
) > 0)
1257 tree var
= VARRAY_TOP_TREE (bd
->vrp_variables
);
1259 /* Each variable has a stack of value range records. We want to
1260 invalidate those associated with our basic block. So we walk
1261 the array backwards popping off records associated with our
1262 block. Once we hit a record not associated with our block
1264 varray_type var_vrp_records
= VARRAY_GENERIC_PTR (vrp_data
,
1265 SSA_NAME_VERSION (var
));
1267 while (VARRAY_ACTIVE_SIZE (var_vrp_records
) > 0)
1269 struct vrp_element
*element
1270 = (struct vrp_element
*)VARRAY_TOP_GENERIC_PTR (var_vrp_records
);
1272 if (element
->bb
!= bb
)
1275 VARRAY_POP (var_vrp_records
);
1278 VARRAY_POP (bd
->vrp_variables
);
1281 /* Re-scan operands in all statements that may have had new symbols
1283 while (bd
->stmts_to_rescan
&& VARRAY_ACTIVE_SIZE (bd
->stmts_to_rescan
) > 0)
1285 tree stmt
= VARRAY_TOP_TREE (bd
->stmts_to_rescan
);
1286 VARRAY_POP (bd
->stmts_to_rescan
);
1287 mark_new_vars_to_rename (stmt
, vars_to_rename
);
1291 /* PHI nodes can create equivalences too.
1293 Ignoring any alternatives which are the same as the result, if
1294 all the alternatives are equal, then the PHI node creates an
1297 record_equivalences_from_phis (struct dom_walk_data
*walk_data
, basic_block bb
)
1299 struct dom_walk_block_data
*bd
1300 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1303 for (phi
= phi_nodes (bb
); phi
; phi
= TREE_CHAIN (phi
))
1305 tree lhs
= PHI_RESULT (phi
);
1309 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
1311 tree t
= PHI_ARG_DEF (phi
, i
);
1313 if (TREE_CODE (t
) == SSA_NAME
|| is_gimple_min_invariant (t
))
1315 /* Ignore alternatives which are the same as our LHS. */
1316 if (operand_equal_p (lhs
, t
, 0))
1319 /* If we have not processed an alternative yet, then set
1320 RHS to this alternative. */
1323 /* If we have processed an alternative (stored in RHS), then
1324 see if it is equal to this one. If it isn't, then stop
1326 else if (! operand_equal_p (rhs
, t
, 0))
1333 /* If we had no interesting alternatives, then all the RHS alternatives
1334 must have been the same as LHS. */
1338 /* If we managed to iterate through each PHI alternative without
1339 breaking out of the loop, then we have a PHI which may create
1340 a useful equivalence. We do not need to record unwind data for
1341 this, since this is a true assignment and not an equivalence
1342 infered from a comparison. All uses of this ssa name are dominated
1343 by this assignment, so unwinding just costs time and space. */
1344 if (i
== PHI_NUM_ARGS (phi
)
1345 && may_propagate_copy (lhs
, rhs
))
1346 set_value_for (lhs
, rhs
, const_and_copies
);
1348 register_new_def (lhs
, &bd
->block_defs
);
1352 /* Record any equivalences created by the incoming edge to BB. If BB
1353 has more than one incoming edge, then no equivalence is created. */
1356 record_equivalences_from_incoming_edge (struct dom_walk_data
*walk_data
,
1361 struct eq_expr_value eq_expr_value
;
1362 tree parent_block_last_stmt
= NULL
;
1363 struct dom_walk_block_data
*bd
1364 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1366 /* If our parent block ended with a control statment, then we may be
1367 able to record some equivalences based on which outgoing edge from
1368 the parent was followed. */
1369 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1372 parent_block_last_stmt
= last_stmt (parent
);
1373 if (parent_block_last_stmt
&& !is_ctrl_stmt (parent_block_last_stmt
))
1374 parent_block_last_stmt
= NULL
;
1377 eq_expr_value
.src
= NULL
;
1378 eq_expr_value
.dst
= NULL
;
1380 /* If we have a single predecessor, then extract EDGE_FLAGS from
1381 our single incoming edge. Otherwise clear EDGE_FLAGS and
1382 PARENT_BLOCK_LAST_STMT since they're not needed. */
1384 && ! bb
->pred
->pred_next
1385 && parent_block_last_stmt
1386 && bb_for_stmt (parent_block_last_stmt
) == bb
->pred
->src
)
1388 edge_flags
= bb
->pred
->flags
;
1393 parent_block_last_stmt
= NULL
;
1396 /* If our parent block ended in a COND_EXPR, add any equivalences
1397 created by the COND_EXPR to the hash table and initialize
1398 EQ_EXPR_VALUE appropriately.
1400 EQ_EXPR_VALUE is an assignment expression created when BB's immediate
1401 dominator ends in a COND_EXPR statement whose predicate is of the form
1402 'VAR == VALUE', where VALUE may be another variable or a constant.
1403 This is used to propagate VALUE on the THEN_CLAUSE of that
1404 conditional. This assignment is inserted in CONST_AND_COPIES so that
1405 the copy and constant propagator can find more propagation
1407 if (parent_block_last_stmt
1408 && bb
->pred
->pred_next
== NULL
1409 && TREE_CODE (parent_block_last_stmt
) == COND_EXPR
1410 && (edge_flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1411 eq_expr_value
= get_eq_expr_value (parent_block_last_stmt
,
1412 (edge_flags
& EDGE_TRUE_VALUE
) != 0,
1415 &bd
->vrp_variables
);
1416 /* Similarly when the parent block ended in a SWITCH_EXPR. */
1417 else if (parent_block_last_stmt
1418 && bb
->pred
->pred_next
== NULL
1419 && TREE_CODE (parent_block_last_stmt
) == SWITCH_EXPR
)
1421 tree switch_cond
= SWITCH_COND (parent_block_last_stmt
);
1423 /* If the switch's condition is an SSA variable, then we may
1424 know its value at each of the case labels. */
1425 if (TREE_CODE (switch_cond
) == SSA_NAME
)
1427 tree switch_vec
= SWITCH_LABELS (parent_block_last_stmt
);
1428 size_t i
, n
= TREE_VEC_LENGTH (switch_vec
);
1430 tree match_case
= NULL_TREE
;
1432 /* Search the case labels for those whose destination is
1433 the current basic block. */
1434 for (i
= 0; i
< n
; ++i
)
1436 tree elt
= TREE_VEC_ELT (switch_vec
, i
);
1437 if (label_to_block (CASE_LABEL (elt
)) == bb
)
1439 if (++case_count
> 1)
1445 /* If we encountered precisely one CASE_LABEL_EXPR and it
1446 was not the default case, or a case range, then we know
1447 the exact value of SWITCH_COND which caused us to get to
1448 this block. Record that equivalence in EQ_EXPR_VALUE. */
1450 && CASE_LOW (match_case
)
1451 && !CASE_HIGH (match_case
))
1453 eq_expr_value
.dst
= switch_cond
;
1454 eq_expr_value
.src
= CASE_LOW (match_case
);
1459 /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
1460 new value for VAR, so that occurrences of VAR can be replaced with
1461 VALUE while re-writing the THEN arm of a COND_EXPR. */
1462 if (eq_expr_value
.src
&& eq_expr_value
.dst
)
1463 record_equality (eq_expr_value
.dst
, eq_expr_value
.src
,
1464 &bd
->const_and_copies
);
1467 /* Dump SSA statistics on FILE. */
1470 dump_dominator_optimization_stats (FILE *file
)
1474 fprintf (file
, "Total number of statements: %6ld\n\n",
1475 opt_stats
.num_stmts
);
1476 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1477 opt_stats
.num_exprs_considered
);
1479 n_exprs
= opt_stats
.num_exprs_considered
;
1483 fprintf (file
, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
1484 opt_stats
.num_re
, PERCENT (opt_stats
.num_re
,
1487 fprintf (file
, "\nHash table statistics:\n");
1489 fprintf (file
, " avail_exprs: ");
1490 htab_statistics (file
, avail_exprs
);
1494 /* Dump SSA statistics on stderr. */
1497 debug_dominator_optimization_stats (void)
1499 dump_dominator_optimization_stats (stderr
);
1503 /* Dump statistics for the hash table HTAB. */
1506 htab_statistics (FILE *file
, htab_t htab
)
1508 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1509 (long) htab_size (htab
),
1510 (long) htab_elements (htab
),
1511 htab_collisions (htab
));
1514 /* Record the fact that VAR has a nonzero value, though we may not know
1515 its exact value. Note that if VAR is already known to have a nonzero
1516 value, then we do nothing. */
1519 record_var_is_nonzero (tree var
, varray_type
*block_nonzero_vars_p
)
1521 int indx
= SSA_NAME_VERSION (var
);
1523 if (bitmap_bit_p (nonzero_vars
, indx
))
1526 /* Mark it in the global table. */
1527 bitmap_set_bit (nonzero_vars
, indx
);
1529 /* Record this SSA_NAME so that we can reset the global table
1530 when we leave this block. */
1531 if (! *block_nonzero_vars_p
)
1532 VARRAY_TREE_INIT (*block_nonzero_vars_p
, 2, "block_nonzero_vars");
1533 VARRAY_PUSH_TREE (*block_nonzero_vars_p
, var
);
1536 /* Enter a statement into the true/false expression hash table indicating
1537 that the condition COND has the value VALUE. */
1540 record_cond (tree cond
, tree value
, varray_type
*block_avail_exprs_p
)
1542 struct expr_hash_elt
*element
= xmalloc (sizeof (struct expr_hash_elt
));
1545 initialize_hash_element (cond
, value
, element
);
1547 slot
= htab_find_slot_with_hash (avail_exprs
, (void *)element
,
1548 element
->hash
, true);
1551 *slot
= (void *) element
;
1552 if (! *block_avail_exprs_p
)
1553 VARRAY_TREE_INIT (*block_avail_exprs_p
, 20, "block_avail_exprs");
1554 VARRAY_PUSH_TREE (*block_avail_exprs_p
, cond
);
1560 /* A helper function for record_const_or_copy and record_equality.
1561 Do the work of recording the value and undo info. */
1564 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
,
1565 varray_type
*block_const_and_copies_p
)
1567 set_value_for (x
, y
, const_and_copies
);
1569 if (!*block_const_and_copies_p
)
1570 VARRAY_TREE_INIT (*block_const_and_copies_p
, 2, "block_const_and_copies");
1571 VARRAY_PUSH_TREE (*block_const_and_copies_p
, x
);
1572 VARRAY_PUSH_TREE (*block_const_and_copies_p
, prev_x
);
1575 /* Record that X is equal to Y in const_and_copies. Record undo
1576 information in the block-local varray. */
1579 record_const_or_copy (tree x
, tree y
, varray_type
*block_const_and_copies_p
)
1581 tree prev_x
= get_value_for (x
, const_and_copies
);
1583 if (TREE_CODE (y
) == SSA_NAME
)
1585 tree tmp
= get_value_for (y
, const_and_copies
);
1590 record_const_or_copy_1 (x
, y
, prev_x
, block_const_and_copies_p
);
1593 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1594 This constrains the cases in which we may treat this as assignment. */
1597 record_equality (tree x
, tree y
, varray_type
*block_const_and_copies_p
)
1599 tree prev_x
= NULL
, prev_y
= NULL
;
1601 if (TREE_CODE (x
) == SSA_NAME
)
1602 prev_x
= get_value_for (x
, const_and_copies
);
1603 if (TREE_CODE (y
) == SSA_NAME
)
1604 prev_y
= get_value_for (y
, const_and_copies
);
1606 /* If one of the previous values is invariant, then use that.
1607 Otherwise it doesn't matter which value we choose, just so
1608 long as we canonicalize on one value. */
1609 if (TREE_INVARIANT (y
))
1611 else if (TREE_INVARIANT (x
))
1612 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1613 else if (prev_x
&& TREE_INVARIANT (prev_x
))
1614 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1618 /* After the swapping, we must have one SSA_NAME. */
1619 if (TREE_CODE (x
) != SSA_NAME
)
1622 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1623 variable compared against zero. If we're honoring signed zeros,
1624 then we cannot record this value unless we know that the value is
1626 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1627 && (TREE_CODE (y
) != REAL_CST
1628 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1631 record_const_or_copy_1 (x
, y
, prev_x
, block_const_and_copies_p
);
1634 /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
1635 hash tables. Try to simplify the RHS using whatever equivalences
1636 we may have recorded.
1638 If we are able to simplify the RHS, then lookup the simplified form in
1639 the hash table and return the result. Otherwise return NULL. */
1642 simplify_rhs_and_lookup_avail_expr (struct dom_walk_data
*walk_data
,
1647 tree rhs
= TREE_OPERAND (stmt
, 1);
1648 enum tree_code rhs_code
= TREE_CODE (rhs
);
1650 struct dom_walk_block_data
*bd
1651 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
1653 /* If we have lhs = ~x, look and see if we earlier had x = ~y.
1654 In which case we can change this statement to be lhs = y.
1655 Which can then be copy propagated.
1657 Similarly for negation. */
1658 if ((rhs_code
== BIT_NOT_EXPR
|| rhs_code
== NEGATE_EXPR
)
1659 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
)
1661 /* Get the definition statement for our RHS. */
1662 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1664 /* See if the RHS_DEF_STMT has the same form as our statement. */
1665 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
1666 && TREE_CODE (TREE_OPERAND (rhs_def_stmt
, 1)) == rhs_code
)
1668 tree rhs_def_operand
;
1670 rhs_def_operand
= TREE_OPERAND (TREE_OPERAND (rhs_def_stmt
, 1), 0);
1672 /* Verify that RHS_DEF_OPERAND is a suitable SSA variable. */
1673 if (TREE_CODE (rhs_def_operand
) == SSA_NAME
1674 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand
))
1675 result
= update_rhs_and_lookup_avail_expr (stmt
,
1683 /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
1684 If OP is associative, create and fold (y OP C2) OP C1 which
1685 should result in (y OP C3), use that as the RHS for the
1686 assignment. Add minus to this, as we handle it specially below. */
1687 if ((associative_tree_code (rhs_code
) || rhs_code
== MINUS_EXPR
)
1688 && TREE_CODE (TREE_OPERAND (rhs
, 0)) == SSA_NAME
1689 && is_gimple_min_invariant (TREE_OPERAND (rhs
, 1)))
1691 tree rhs_def_stmt
= SSA_NAME_DEF_STMT (TREE_OPERAND (rhs
, 0));
1693 /* See if the RHS_DEF_STMT has the same form as our statement. */
1694 if (TREE_CODE (rhs_def_stmt
) == MODIFY_EXPR
)
1696 tree rhs_def_rhs
= TREE_OPERAND (rhs_def_stmt
, 1);
1697 enum tree_code rhs_def_code
= TREE_CODE (rhs_def_rhs
);
1699 if (rhs_code
== rhs_def_code
1700 || (rhs_code
== PLUS_EXPR
&& rhs_def_code
== MINUS_EXPR
)
1701 || (rhs_code
== MINUS_EXPR
&& rhs_def_code
== PLUS_EXPR
))
1703 tree def_stmt_op0
= TREE_OPERAND (rhs_def_rhs
, 0);
1704 tree def_stmt_op1
= TREE_OPERAND (rhs_def_rhs
, 1);
1706 if (TREE_CODE (def_stmt_op0
) == SSA_NAME
1707 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0
)
1708 && is_gimple_min_invariant (def_stmt_op1
))
1710 tree outer_const
= TREE_OPERAND (rhs
, 1);
1711 tree type
= TREE_TYPE (TREE_OPERAND (stmt
, 0));
1714 /* Ho hum. So fold will only operate on the outermost
1715 thingy that we give it, so we have to build the new
1716 expression in two pieces. This requires that we handle
1717 combinations of plus and minus. */
1718 if (rhs_def_code
!= rhs_code
)
1720 if (rhs_def_code
== MINUS_EXPR
)
1721 t
= build (MINUS_EXPR
, type
, outer_const
, def_stmt_op1
);
1723 t
= build (MINUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1724 rhs_code
= PLUS_EXPR
;
1726 else if (rhs_def_code
== MINUS_EXPR
)
1727 t
= build (PLUS_EXPR
, type
, def_stmt_op1
, outer_const
);
1729 t
= build (rhs_def_code
, type
, def_stmt_op1
, outer_const
);
1731 t
= build (rhs_code
, type
, def_stmt_op0
, t
);
1734 /* If the result is a suitable looking gimple expression,
1735 then use it instead of the original for STMT. */
1736 if (TREE_CODE (t
) == SSA_NAME
1737 || (TREE_CODE_CLASS (TREE_CODE (t
)) == '1'
1738 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
)
1739 || ((TREE_CODE_CLASS (TREE_CODE (t
)) == '2'
1740 || TREE_CODE_CLASS (TREE_CODE (t
)) == '<')
1741 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
1742 && is_gimple_val (TREE_OPERAND (t
, 1))))
1743 result
= update_rhs_and_lookup_avail_expr
1744 (stmt
, t
, &bd
->avail_exprs
, ann
, insert
);
1750 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1751 and BIT_AND_EXPR respectively if the first operand is greater
1752 than zero and the second operand is an exact power of two. */
1753 if ((rhs_code
== TRUNC_DIV_EXPR
|| rhs_code
== TRUNC_MOD_EXPR
)
1754 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0)))
1755 && integer_pow2p (TREE_OPERAND (rhs
, 1)))
1758 tree op
= TREE_OPERAND (rhs
, 0);
1760 if (TYPE_UNSIGNED (TREE_TYPE (op
)))
1762 val
= integer_one_node
;
1766 tree dummy_cond
= walk_data
->global_data
;
1770 dummy_cond
= build (GT_EXPR
, boolean_type_node
,
1771 op
, integer_zero_node
);
1772 dummy_cond
= build (COND_EXPR
, void_type_node
,
1773 dummy_cond
, NULL
, NULL
);
1774 walk_data
->global_data
= dummy_cond
;
1778 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), GT_EXPR
);
1779 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
1780 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
1781 = integer_zero_node
;
1783 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
1788 if (val
&& integer_onep (val
))
1791 tree op0
= TREE_OPERAND (rhs
, 0);
1792 tree op1
= TREE_OPERAND (rhs
, 1);
1794 if (rhs_code
== TRUNC_DIV_EXPR
)
1795 t
= build (RSHIFT_EXPR
, TREE_TYPE (op0
), op0
,
1796 build_int_2 (tree_log2 (op1
), 0));
1798 t
= build (BIT_AND_EXPR
, TREE_TYPE (op0
), op0
,
1799 local_fold (build (MINUS_EXPR
, TREE_TYPE (op1
),
1800 op1
, integer_one_node
)));
1802 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
1808 /* Transform ABS (X) into X or -X as appropriate. */
1809 if (rhs_code
== ABS_EXPR
1810 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs
, 0))))
1813 tree op
= TREE_OPERAND (rhs
, 0);
1814 tree type
= TREE_TYPE (op
);
1816 if (TYPE_UNSIGNED (type
))
1818 val
= integer_zero_node
;
1822 tree dummy_cond
= walk_data
->global_data
;
1826 dummy_cond
= build (LT_EXPR
, boolean_type_node
,
1827 op
, integer_zero_node
);
1828 dummy_cond
= build (COND_EXPR
, void_type_node
,
1829 dummy_cond
, NULL
, NULL
);
1830 walk_data
->global_data
= dummy_cond
;
1834 TREE_SET_CODE (TREE_OPERAND (dummy_cond
, 0), LT_EXPR
);
1835 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 0) = op
;
1836 TREE_OPERAND (TREE_OPERAND (dummy_cond
, 0), 1)
1837 = convert (type
, integer_zero_node
);
1839 val
= simplify_cond_and_lookup_avail_expr (dummy_cond
,
1845 && (integer_onep (val
) || integer_zerop (val
)))
1849 if (integer_onep (val
))
1850 t
= build1 (NEGATE_EXPR
, TREE_TYPE (op
), op
);
1854 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
1860 /* Optimize *"foo" into 'f'. This is done here rather than
1861 in fold to avoid problems with stuff like &*"foo". */
1862 if (TREE_CODE (rhs
) == INDIRECT_REF
|| TREE_CODE (rhs
) == ARRAY_REF
)
1864 tree t
= fold_read_from_constant_string (rhs
);
1867 result
= update_rhs_and_lookup_avail_expr (stmt
, t
,
1875 /* COND is a condition of the form:
1877 x == const or x != const
1879 Look back to x's defining statement and see if x is defined as
1883 If const is unchanged if we convert it to type, then we can build
1884 the equivalent expression:
1887 y == const or y != const
1889 Which may allow further optimizations.
1891 Return the equivalent comparison or NULL if no such equivalent comparison
1895 find_equivalent_equality_comparison (tree cond
)
1897 tree op0
= TREE_OPERAND (cond
, 0);
1898 tree op1
= TREE_OPERAND (cond
, 1);
1899 tree def_stmt
= SSA_NAME_DEF_STMT (op0
);
1901 /* OP0 might have been a parameter, so first make sure it
1902 was defined by a MODIFY_EXPR. */
1903 if (def_stmt
&& TREE_CODE (def_stmt
) == MODIFY_EXPR
)
1905 tree def_rhs
= TREE_OPERAND (def_stmt
, 1);
1907 /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
1908 if ((TREE_CODE (def_rhs
) == NOP_EXPR
1909 || TREE_CODE (def_rhs
) == CONVERT_EXPR
)
1910 && TREE_CODE (TREE_OPERAND (def_rhs
, 0)) == SSA_NAME
)
1912 tree def_rhs_inner
= TREE_OPERAND (def_rhs
, 0);
1913 tree def_rhs_inner_type
= TREE_TYPE (def_rhs_inner
);
1916 if (TYPE_PRECISION (def_rhs_inner_type
)
1917 > TYPE_PRECISION (TREE_TYPE (def_rhs
)))
1920 /* What we want to prove is that if we convert OP1 to
1921 the type of the object inside the NOP_EXPR that the
1922 result is still equivalent to SRC.
1924 If that is true, the build and return new equivalent
1925 condition which uses the source of the typecast and the
1926 new constant (which has only changed its type). */
1927 new = build1 (TREE_CODE (def_rhs
), def_rhs_inner_type
, op1
);
1928 new = local_fold (new);
1929 if (is_gimple_val (new) && tree_int_cst_equal (new, op1
))
1930 return build (TREE_CODE (cond
), TREE_TYPE (cond
),
1931 def_rhs_inner
, new);
1937 /* STMT is a COND_EXPR for which we could not trivially determine its
1938 result. This routine attempts to find equivalent forms of the
1939 condition which we may be able to optimize better. It also
1940 uses simple value range propagation to optimize conditionals. */
1943 simplify_cond_and_lookup_avail_expr (tree stmt
,
1944 varray_type
*block_avail_exprs_p
,
1948 tree cond
= COND_EXPR_COND (stmt
);
1950 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
1952 tree op0
= TREE_OPERAND (cond
, 0);
1953 tree op1
= TREE_OPERAND (cond
, 1);
1955 if (TREE_CODE (op0
) == SSA_NAME
&& is_gimple_min_invariant (op1
))
1958 tree low
, high
, cond_low
, cond_high
;
1959 int lowequal
, highequal
, swapped
, no_overlap
, subset
, cond_inverted
;
1960 varray_type vrp_records
;
1961 struct vrp_element
*element
;
1963 /* First see if we have test of an SSA_NAME against a constant
1964 where the SSA_NAME is defined by an earlier typecast which
1965 is irrelevant when performing tests against the given
1967 if (TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
1969 tree new_cond
= find_equivalent_equality_comparison (cond
);
1973 /* Update the statement to use the new equivalent
1975 COND_EXPR_COND (stmt
) = new_cond
;
1978 /* Lookup the condition and return its known value if it
1980 new_cond
= lookup_avail_expr (stmt
, block_avail_exprs_p
,
1985 /* The operands have changed, so update op0 and op1. */
1986 op0
= TREE_OPERAND (cond
, 0);
1987 op1
= TREE_OPERAND (cond
, 1);
1991 /* Consult the value range records for this variable (if they exist)
1992 to see if we can eliminate or simplify this conditional.
1994 Note two tests are necessary to determine no records exist.
1995 First we have to see if the virtual array exists, if it
1996 exists, then we have to check its active size.
1998 Also note the vast majority of conditionals are not testing
1999 a variable which has had its range constrained by an earlier
2000 conditional. So this filter avoids a lot of unnecessary work. */
2001 vrp_records
= VARRAY_GENERIC_PTR (vrp_data
, SSA_NAME_VERSION (op0
));
2002 if (vrp_records
== NULL
)
2005 limit
= VARRAY_ACTIVE_SIZE (vrp_records
);
2007 /* If we have no value range records for this variable, or we are
2008 unable to extract a range for this condition, then there is
2011 || ! extract_range_from_cond (cond
, &cond_high
,
2012 &cond_low
, &cond_inverted
))
2015 /* We really want to avoid unnecessary computations of range
2016 info. So all ranges are computed lazily; this avoids a
2017 lot of unnecessary work. ie, we record the conditional,
2018 but do not process how it constrains the variable's
2019 potential values until we know that processing the condition
2022 However, we do not want to have to walk a potentially long
2023 list of ranges, nor do we want to compute a variable's
2024 range more than once for a given path.
2026 Luckily, each time we encounter a conditional that can not
2027 be otherwise optimized we will end up here and we will
2028 compute the necessary range information for the variable
2029 used in this condition.
2031 Thus you can conclude that there will never be more than one
2032 conditional associated with a variable which has not been
2033 processed. So we never need to merge more than one new
2034 conditional into the current range.
2036 These properties also help us avoid unnecessary work. */
2038 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
, limit
- 1);
2040 if (element
->high
&& element
->low
)
2042 /* The last element has been processed, so there is no range
2043 merging to do, we can simply use the high/low values
2044 recorded in the last element. */
2046 high
= element
->high
;
2050 tree tmp_high
, tmp_low
;
2053 /* The last element has not been processed. Process it now. */
2054 extract_range_from_cond (element
->cond
, &tmp_high
,
2057 /* If this is the only element, then no merging is necessary,
2058 the high/low values from extract_range_from_cond are all
2067 /* Get the high/low value from the previous element. */
2068 struct vrp_element
*prev
2069 = (struct vrp_element
*)VARRAY_GENERIC_PTR (vrp_records
,
2074 /* Merge in this element's range with the range from the
2077 The low value for the merged range is the maximum of
2078 the previous low value and the low value of this record.
2080 Similarly the high value for the merged range is the
2081 minimum of the previous high value and the high value of
2083 low
= (tree_int_cst_compare (low
, tmp_low
) == 1
2085 high
= (tree_int_cst_compare (high
, tmp_high
) == -1
2089 /* And record the computed range. */
2091 element
->high
= high
;
2095 /* After we have constrained this variable's potential values,
2096 we try to determine the result of the given conditional.
2098 To simplify later tests, first determine if the current
2099 low value is the same low value as the conditional.
2100 Similarly for the current high value and the high value
2101 for the conditional. */
2102 lowequal
= tree_int_cst_equal (low
, cond_low
);
2103 highequal
= tree_int_cst_equal (high
, cond_high
);
2105 if (lowequal
&& highequal
)
2106 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2108 /* To simplify the overlap/subset tests below we may want
2109 to swap the two ranges so that the larger of the two
2110 ranges occurs "first". */
2112 if (tree_int_cst_compare (low
, cond_low
) == 1
2114 && tree_int_cst_compare (cond_high
, high
) == 1))
2127 /* Now determine if there is no overlap in the ranges
2128 or if the second range is a subset of the first range. */
2129 no_overlap
= tree_int_cst_lt (high
, cond_low
);
2130 subset
= tree_int_cst_compare (cond_high
, high
) != 1;
2132 /* If there was no overlap in the ranges, then this conditional
2133 always has a false value (unless we had to invert this
2134 conditional, in which case it always has a true value). */
2136 return (cond_inverted
? boolean_true_node
: boolean_false_node
);
2138 /* If the current range is a subset of the condition's range,
2139 then this conditional always has a true value (unless we
2140 had to invert this conditional, in which case it always
2141 has a true value). */
2142 if (subset
&& swapped
)
2143 return (cond_inverted
? boolean_false_node
: boolean_true_node
);
2145 /* We were unable to determine the result of the conditional.
2146 However, we may be able to simplify the conditional. First
2147 merge the ranges in the same manner as range merging above. */
2148 low
= tree_int_cst_compare (low
, cond_low
) == 1 ? low
: cond_low
;
2149 high
= tree_int_cst_compare (high
, cond_high
) == -1 ? high
: cond_high
;
2151 /* If the range has converged to a single point, then turn this
2152 into an equality comparison. */
2153 if (TREE_CODE (cond
) != EQ_EXPR
2154 && TREE_CODE (cond
) != NE_EXPR
2155 && tree_int_cst_equal (low
, high
))
2157 TREE_SET_CODE (cond
, EQ_EXPR
);
2158 TREE_OPERAND (cond
, 1) = high
;
2165 /* STMT is a SWITCH_EXPR for which we could not trivially determine its
2166 result. This routine attempts to find equivalent forms of the
2167 condition which we may be able to optimize better. */
2170 simplify_switch_and_lookup_avail_expr (tree stmt
,
2171 varray_type
*block_avail_exprs_p
,
2175 tree cond
= SWITCH_COND (stmt
);
2178 /* The optimization that we really care about is removing unnecessary
2179 casts. That will let us do much better in propagating the inferred
2180 constant at the switch target. */
2181 if (TREE_CODE (cond
) == SSA_NAME
)
2183 def
= SSA_NAME_DEF_STMT (cond
);
2184 if (TREE_CODE (def
) == MODIFY_EXPR
)
2186 def
= TREE_OPERAND (def
, 1);
2187 if (TREE_CODE (def
) == NOP_EXPR
)
2189 def
= TREE_OPERAND (def
, 0);
2190 to
= TREE_TYPE (cond
);
2191 ti
= TREE_TYPE (def
);
2193 /* If we have an extension that preserves sign, then we
2194 can copy the source value into the switch. */
2195 if (TYPE_UNSIGNED (to
) == TYPE_UNSIGNED (ti
)
2196 && TYPE_PRECISION (to
) >= TYPE_PRECISION (ti
)
2197 && is_gimple_val (def
))
2199 SWITCH_COND (stmt
) = def
;
2202 return lookup_avail_expr (stmt
, block_avail_exprs_p
, insert
);
2211 /* Propagate known constants/copies into PHI nodes of BB's successor
2215 cprop_into_phis (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
2218 cprop_into_successor_phis (bb
, const_and_copies
);
2221 /* Search for redundant computations in STMT. If any are found, then
2222 replace them with the variable holding the result of the computation.
2224 If safe, record this expression into the available expression hash
2228 eliminate_redundant_computations (struct dom_walk_data
*walk_data
,
2229 tree stmt
, stmt_ann_t ann
)
2231 vdef_optype vdefs
= VDEF_OPS (ann
);
2232 tree
*expr_p
, def
= NULL_TREE
;
2235 bool retval
= false;
2236 struct dom_walk_block_data
*bd
2237 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
2239 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2240 def
= TREE_OPERAND (stmt
, 0);
2242 /* Certain expressions on the RHS can be optimized away, but can not
2243 themselves be entered into the hash tables. */
2244 if (ann
->makes_aliased_stores
2246 || TREE_CODE (def
) != SSA_NAME
2247 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
2248 || NUM_VDEFS (vdefs
) != 0)
2251 /* Check if the expression has been computed before. */
2252 cached_lhs
= lookup_avail_expr (stmt
, &bd
->avail_exprs
, insert
);
2254 /* If this is an assignment and the RHS was not in the hash table,
2255 then try to simplify the RHS and lookup the new RHS in the
2257 if (! cached_lhs
&& TREE_CODE (stmt
) == MODIFY_EXPR
)
2258 cached_lhs
= simplify_rhs_and_lookup_avail_expr (walk_data
,
2262 /* Similarly if this is a COND_EXPR and we did not find its
2263 expression in the hash table, simplify the condition and
2265 else if (! cached_lhs
&& TREE_CODE (stmt
) == COND_EXPR
)
2266 cached_lhs
= simplify_cond_and_lookup_avail_expr (stmt
,
2270 /* Similarly for a SWITCH_EXPR. */
2271 else if (!cached_lhs
&& TREE_CODE (stmt
) == SWITCH_EXPR
)
2272 cached_lhs
= simplify_switch_and_lookup_avail_expr (stmt
,
2277 opt_stats
.num_exprs_considered
++;
2279 /* Get a pointer to the expression we are trying to optimize. */
2280 if (TREE_CODE (stmt
) == COND_EXPR
)
2281 expr_p
= &COND_EXPR_COND (stmt
);
2282 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2283 expr_p
= &SWITCH_COND (stmt
);
2284 else if (TREE_CODE (stmt
) == RETURN_EXPR
&& TREE_OPERAND (stmt
, 0))
2285 expr_p
= &TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1);
2287 expr_p
= &TREE_OPERAND (stmt
, 1);
2289 /* It is safe to ignore types here since we have already done
2290 type checking in the hashing and equality routines. In fact
2291 type checking here merely gets in the way of constant
2292 propagation. Also, make sure that it is safe to propagate
2293 CACHED_LHS into *EXPR_P. */
2295 && (TREE_CODE (cached_lhs
) != SSA_NAME
2296 || may_propagate_copy (cached_lhs
, *expr_p
)))
2298 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2300 fprintf (dump_file
, " Replaced redundant expr '");
2301 print_generic_expr (dump_file
, *expr_p
, dump_flags
);
2302 fprintf (dump_file
, "' with '");
2303 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
2304 fprintf (dump_file
, "'\n");
2309 #if defined ENABLE_CHECKING
2310 if (TREE_CODE (cached_lhs
) != SSA_NAME
2311 && !is_gimple_min_invariant (cached_lhs
))
2315 if (TREE_CODE (cached_lhs
) == ADDR_EXPR
2316 || (POINTER_TYPE_P (TREE_TYPE (*expr_p
))
2317 && is_gimple_min_invariant (cached_lhs
)))
2320 propagate_value (expr_p
, cached_lhs
);
2326 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
2327 the available expressions table or the const_and_copies table.
2328 Detect and record those equivalences. */
2331 record_equivalences_from_stmt (tree stmt
,
2332 varray_type
*block_avail_exprs_p
,
2333 varray_type
*block_nonzero_vars_p
,
2337 tree lhs
= TREE_OPERAND (stmt
, 0);
2338 enum tree_code lhs_code
= TREE_CODE (lhs
);
2341 if (lhs_code
== SSA_NAME
)
2343 tree rhs
= TREE_OPERAND (stmt
, 1);
2345 /* Strip away any useless type conversions. */
2346 STRIP_USELESS_TYPE_CONVERSION (rhs
);
2348 /* If the RHS of the assignment is a constant or another variable that
2349 may be propagated, register it in the CONST_AND_COPIES table. We
2350 do not need to record unwind data for this, since this is a true
2351 assignment and not an equivalence infered from a comparison. All
2352 uses of this ssa name are dominated by this assignment, so unwinding
2353 just costs time and space. */
2355 && (TREE_CODE (rhs
) == SSA_NAME
2356 || is_gimple_min_invariant (rhs
)))
2357 set_value_for (lhs
, rhs
, const_and_copies
);
2359 /* alloca never returns zero and the address of a non-weak symbol
2360 is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
2361 stripped as they do not affect this equivalence. */
2362 while (TREE_CODE (rhs
) == NOP_EXPR
2363 || TREE_CODE (rhs
) == CONVERT_EXPR
)
2364 rhs
= TREE_OPERAND (rhs
, 0);
2366 if (alloca_call_p (rhs
)
2367 || (TREE_CODE (rhs
) == ADDR_EXPR
2368 && DECL_P (TREE_OPERAND (rhs
, 0))
2369 && ! DECL_WEAK (TREE_OPERAND (rhs
, 0))))
2370 record_var_is_nonzero (lhs
, block_nonzero_vars_p
);
2372 /* IOR of any value with a nonzero value will result in a nonzero
2373 value. Even if we do not know the exact result recording that
2374 the result is nonzero is worth the effort. */
2375 if (TREE_CODE (rhs
) == BIT_IOR_EXPR
2376 && integer_nonzerop (TREE_OPERAND (rhs
, 1)))
2377 record_var_is_nonzero (lhs
, block_nonzero_vars_p
);
2380 /* Look at both sides for pointer dereferences. If we find one, then
2381 the pointer must be nonnull and we can enter that equivalence into
2383 for (i
= 0; i
< 2; i
++)
2385 tree t
= TREE_OPERAND (stmt
, i
);
2387 /* Strip away any COMPONENT_REFs. */
2388 while (TREE_CODE (t
) == COMPONENT_REF
)
2389 t
= TREE_OPERAND (t
, 0);
2391 /* Now see if this is a pointer dereference. */
2392 if (TREE_CODE (t
) == INDIRECT_REF
)
2394 tree op
= TREE_OPERAND (t
, 0);
2396 /* If the pointer is a SSA variable, then enter new
2397 equivalences into the hash table. */
2398 if (TREE_CODE (op
) == SSA_NAME
)
2399 record_var_is_nonzero (op
, block_nonzero_vars_p
);
2403 /* A memory store, even an aliased store, creates a useful
2404 equivalence. By exchanging the LHS and RHS, creating suitable
2405 vops and recording the result in the available expression table,
2406 we may be able to expose more redundant loads. */
2407 if (!ann
->has_volatile_ops
2408 && (TREE_CODE (TREE_OPERAND (stmt
, 1)) == SSA_NAME
2409 || is_gimple_min_invariant (TREE_OPERAND (stmt
, 1)))
2410 && !is_gimple_reg (lhs
))
2412 tree rhs
= TREE_OPERAND (stmt
, 1);
2416 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
2417 is a constant, we need to adjust the constant to fit into the
2418 type of the LHS. If the LHS is a bitfield and the RHS is not
2419 a constant, then we can not record any equivalences for this
2420 statement since we would need to represent the widening or
2421 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
2422 and should not be necessary if GCC represented bitfields
2424 if (lhs_code
== COMPONENT_REF
2425 && DECL_BIT_FIELD (TREE_OPERAND (lhs
, 1)))
2427 if (TREE_CONSTANT (rhs
))
2428 rhs
= widen_bitfield (rhs
, TREE_OPERAND (lhs
, 1), lhs
);
2432 /* If the value overflowed, then we can not use this equivalence. */
2433 if (rhs
&& ! is_gimple_min_invariant (rhs
))
2439 vdef_optype vdefs
= VDEF_OPS (ann
);
2441 /* Build a new statement with the RHS and LHS exchanged. */
2442 new = build (MODIFY_EXPR
, TREE_TYPE (stmt
), rhs
, lhs
);
2444 /* Get an annotation and set up the real operands. */
2446 get_stmt_operands (new);
2448 /* Clear out the virtual operands on the new statement, we are
2449 going to set them explicitly below. */
2453 start_ssa_stmt_operands (new);
2454 /* For each VDEF on the original statement, we want to create a
2455 VUSE of the VDEF result on the new statement. */
2456 for (j
= 0; j
< NUM_VDEFS (vdefs
); j
++)
2458 tree op
= VDEF_RESULT (vdefs
, j
);
2462 finalize_ssa_stmt_operands (new);
2464 /* Finally enter the statement into the available expression
2466 lookup_avail_expr (new, block_avail_exprs_p
, true);
2471 /* Optimize the statement pointed by iterator SI.
2473 We try to perform some simplistic global redundancy elimination and
2474 constant propagation:
2476 1- To detect global redundancy, we keep track of expressions that have
2477 been computed in this block and its dominators. If we find that the
2478 same expression is computed more than once, we eliminate repeated
2479 computations by using the target of the first one.
2481 2- Constant values and copy assignments. This is used to do very
2482 simplistic constant and copy propagation. When a constant or copy
2483 assignment is found, we map the value on the RHS of the assignment to
2484 the variable in the LHS in the CONST_AND_COPIES table. */
2487 optimize_stmt (struct dom_walk_data
*walk_data
,
2488 basic_block bb ATTRIBUTE_UNUSED
,
2489 block_stmt_iterator si
)
2494 bool may_optimize_p
;
2495 bool may_have_exposed_new_symbols
= false;
2496 struct dom_walk_block_data
*bd
2497 = VARRAY_TOP_GENERIC_PTR (walk_data
->block_data_stack
);
2499 stmt
= bsi_stmt (si
);
2501 get_stmt_operands (stmt
);
2502 ann
= stmt_ann (stmt
);
2503 vdefs
= VDEF_OPS (ann
);
2504 opt_stats
.num_stmts
++;
2505 may_have_exposed_new_symbols
= false;
2507 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2509 fprintf (dump_file
, "Optimizing statement ");
2510 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
2513 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2514 may_have_exposed_new_symbols
= cprop_into_stmt (stmt
, const_and_copies
);
2516 /* If the statement has been modified with constant replacements,
2517 fold its RHS before checking for redundant computations. */
2520 /* Try to fold the statement making sure that STMT is kept
2522 if (fold_stmt (bsi_stmt_ptr (si
)))
2524 stmt
= bsi_stmt (si
);
2525 ann
= stmt_ann (stmt
);
2527 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2529 fprintf (dump_file
, " Folded to: ");
2530 print_generic_stmt (dump_file
, stmt
, TDF_SLIM
);
2534 /* Constant/copy propagation above may change the set of
2535 virtual operands associated with this statement. Folding
2536 may remove the need for some virtual operands.
2538 Indicate we will need to rescan and rewrite the statement. */
2539 may_have_exposed_new_symbols
= true;
2542 /* Check for redundant computations. Do this optimization only
2543 for assignments that have no volatile ops and conditionals. */
2544 may_optimize_p
= (!ann
->has_volatile_ops
2545 && ((TREE_CODE (stmt
) == RETURN_EXPR
2546 && TREE_OPERAND (stmt
, 0)
2547 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
2548 && ! (TREE_SIDE_EFFECTS
2549 (TREE_OPERAND (TREE_OPERAND (stmt
, 0), 1))))
2550 || (TREE_CODE (stmt
) == MODIFY_EXPR
2551 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt
, 1)))
2552 || TREE_CODE (stmt
) == COND_EXPR
2553 || TREE_CODE (stmt
) == SWITCH_EXPR
));
2556 may_have_exposed_new_symbols
2557 |= eliminate_redundant_computations (walk_data
, stmt
, ann
);
2559 /* Record any additional equivalences created by this statement. */
2560 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2561 record_equivalences_from_stmt (stmt
,
2567 register_definitions_for_stmt (ann
, &bd
->block_defs
);
2569 /* If STMT is a COND_EXPR and it was modified, then we may know
2570 where it goes. If that is the case, then mark the CFG as altered.
2572 This will cause us to later call remove_unreachable_blocks and
2573 cleanup_tree_cfg when it is safe to do so. It is not safe to
2574 clean things up here since removal of edges and such can trigger
2575 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2578 That's all fine and good, except that once SSA_NAMEs are released
2579 to the manager, we must not call create_ssa_name until all references
2580 to released SSA_NAMEs have been eliminated.
2582 All references to the deleted SSA_NAMEs can not be eliminated until
2583 we remove unreachable blocks.
2585 We can not remove unreachable blocks until after we have completed
2586 any queued jump threading.
2588 We can not complete any queued jump threads until we have taken
2589 appropriate variables out of SSA form. Taking variables out of
2590 SSA form can call create_ssa_name and thus we lose.
2592 Ultimately I suspect we're going to need to change the interface
2593 into the SSA_NAME manager. */
2599 if (TREE_CODE (stmt
) == COND_EXPR
)
2600 val
= COND_EXPR_COND (stmt
);
2601 else if (TREE_CODE (stmt
) == SWITCH_EXPR
)
2602 val
= SWITCH_COND (stmt
);
2604 if (val
&& TREE_CODE (val
) == INTEGER_CST
2605 && find_taken_edge (bb_for_stmt (stmt
), val
))
2609 if (may_have_exposed_new_symbols
)
2611 if (! bd
->stmts_to_rescan
)
2612 VARRAY_TREE_INIT (bd
->stmts_to_rescan
, 20, "stmts_to_rescan");
2613 VARRAY_PUSH_TREE (bd
->stmts_to_rescan
, bsi_stmt (si
));
2617 /* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
2618 available expression hashtable, then return the LHS from the hash
2621 If INSERT is true, then we also update the available expression
2622 hash table to account for the changes made to STMT. */
2625 update_rhs_and_lookup_avail_expr (tree stmt
, tree new_rhs
,
2626 varray_type
*block_avail_exprs_p
,
2630 tree cached_lhs
= NULL
;
2632 /* Remove the old entry from the hash table. */
2635 struct expr_hash_elt element
;
2637 initialize_hash_element (stmt
, NULL
, &element
);
2638 htab_remove_elt_with_hash (avail_exprs
, &element
, element
.hash
);
2641 /* Now update the RHS of the assignment. */
2642 TREE_OPERAND (stmt
, 1) = new_rhs
;
2644 /* Now lookup the updated statement in the hash table. */
2645 cached_lhs
= lookup_avail_expr (stmt
, block_avail_exprs_p
, insert
);
2647 /* We have now called lookup_avail_expr twice with two different
2648 versions of this same statement, once in optimize_stmt, once here.
2650 We know the call in optimize_stmt did not find an existing entry
2651 in the hash table, so a new entry was created. At the same time
2652 this statement was pushed onto the BLOCK_AVAIL_EXPRS varray.
2654 If this call failed to find an existing entry on the hash table,
2655 then the new version of this statement was entered into the
2656 hash table. And this statement was pushed onto BLOCK_AVAIL_EXPR
2657 for the second time. So there are two copies on BLOCK_AVAIL_EXPRs
2659 If this call succeeded, we still have one copy of this statement
2660 on the BLOCK_AVAIL_EXPRs varray.
2662 For both cases, we need to pop the most recent entry off the
2663 BLOCK_AVAIL_EXPRs varray. For the case where we never found this
2664 statement in the hash tables, that will leave precisely one
2665 copy of this statement on BLOCK_AVAIL_EXPRs. For the case where
2666 we found a copy of this statement in the second hash table lookup
2667 we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs. */
2669 VARRAY_POP (*block_avail_exprs_p
);
2671 /* And make sure we record the fact that we modified this
2678 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
2679 found, return its LHS. Otherwise insert STMT in the table and return
2682 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
2683 is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
2684 can be removed when we finish processing this block and its children.
2686 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
2687 contains no CALL_EXPR on its RHS and makes no volatile nor
2688 aliased references. */
2691 lookup_avail_expr (tree stmt
, varray_type
*block_avail_exprs_p
, bool insert
)
2696 struct expr_hash_elt
*element
= xcalloc (sizeof (struct expr_hash_elt
), 1);
2698 lhs
= TREE_CODE (stmt
) == MODIFY_EXPR
? TREE_OPERAND (stmt
, 0) : NULL
;
2700 initialize_hash_element (stmt
, lhs
, element
);
2702 /* Don't bother remembering constant assignments and copy operations.
2703 Constants and copy operations are handled by the constant/copy propagator
2704 in optimize_stmt. */
2705 if (TREE_CODE (element
->rhs
) == SSA_NAME
2706 || is_gimple_min_invariant (element
->rhs
))
2712 /* If this is an equality test against zero, see if we have recorded a
2713 nonzero value for the variable in question. */
2714 if ((TREE_CODE (element
->rhs
) == EQ_EXPR
2715 || TREE_CODE (element
->rhs
) == NE_EXPR
)
2716 && TREE_CODE (TREE_OPERAND (element
->rhs
, 0)) == SSA_NAME
2717 && integer_zerop (TREE_OPERAND (element
->rhs
, 1)))
2719 int indx
= SSA_NAME_VERSION (TREE_OPERAND (element
->rhs
, 0));
2721 if (bitmap_bit_p (nonzero_vars
, indx
))
2723 tree t
= element
->rhs
;
2726 if (TREE_CODE (t
) == EQ_EXPR
)
2727 return boolean_false_node
;
2729 return boolean_true_node
;
2733 /* Finally try to find the expression in the main expression hash table. */
2734 slot
= htab_find_slot_with_hash (avail_exprs
, element
, element
->hash
,
2735 (insert
? INSERT
: NO_INSERT
));
2744 *slot
= (void *) element
;
2745 if (! *block_avail_exprs_p
)
2746 VARRAY_TREE_INIT (*block_avail_exprs_p
, 20, "block_avail_exprs");
2747 VARRAY_PUSH_TREE (*block_avail_exprs_p
, stmt
? stmt
: element
->rhs
);
2751 /* Extract the LHS of the assignment so that it can be used as the current
2752 definition of another variable. */
2753 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
2755 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2756 use the value from the const_and_copies table. */
2757 if (TREE_CODE (lhs
) == SSA_NAME
)
2759 temp
= get_value_for (lhs
, const_and_copies
);
2768 /* Given a condition COND, record into HI_P, LO_P and INVERTED_P the
2769 range of values that result in the conditional having a true value.
2771 Return true if we are successful in extracting a range from COND and
2772 false if we are unsuccessful. */
2775 extract_range_from_cond (tree cond
, tree
*hi_p
, tree
*lo_p
, int *inverted_p
)
2777 tree op1
= TREE_OPERAND (cond
, 1);
2778 tree high
, low
, type
;
2781 /* Experiments have shown that it's rarely, if ever useful to
2782 record ranges for enumerations. Presumably this is due to
2783 the fact that they're rarely used directly. They are typically
2784 cast into an integer type and used that way. */
2785 if (TREE_CODE (TREE_TYPE (op1
)) != INTEGER_TYPE
)
2788 type
= TREE_TYPE (op1
);
2790 switch (TREE_CODE (cond
))
2804 high
= TYPE_MAX_VALUE (type
);
2809 low
= int_const_binop (PLUS_EXPR
, op1
, integer_one_node
, 1);
2810 high
= TYPE_MAX_VALUE (type
);
2816 low
= TYPE_MIN_VALUE (type
);
2821 high
= int_const_binop (MINUS_EXPR
, op1
, integer_one_node
, 1);
2822 low
= TYPE_MIN_VALUE (type
);
2832 *inverted_p
= inverted
;
2836 /* Record a range created by COND for basic block BB. */
2839 record_range (tree cond
, basic_block bb
, varray_type
*vrp_variables_p
)
2841 /* We explicitly ignore NE_EXPRs. They rarely allow for meaningful
2842 range optimizations and significantly complicate the implementation. */
2843 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<'
2844 && TREE_CODE (cond
) != NE_EXPR
2845 && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond
, 1))) == INTEGER_TYPE
)
2847 struct vrp_element
*element
= ggc_alloc (sizeof (struct vrp_element
));
2848 int ssa_version
= SSA_NAME_VERSION (TREE_OPERAND (cond
, 0));
2850 varray_type
*vrp_records_p
2851 = (varray_type
*)&VARRAY_GENERIC_PTR (vrp_data
, ssa_version
);
2853 element
->low
= NULL
;
2854 element
->high
= NULL
;
2855 element
->cond
= cond
;
2858 if (*vrp_records_p
== NULL
)
2860 VARRAY_GENERIC_PTR_INIT (*vrp_records_p
, 2, "vrp records");
2861 VARRAY_GENERIC_PTR (vrp_data
, ssa_version
) = *vrp_records_p
;
2864 VARRAY_PUSH_GENERIC_PTR (*vrp_records_p
, element
);
2865 if (! *vrp_variables_p
)
2866 VARRAY_TREE_INIT (*vrp_variables_p
, 2, "vrp_variables");
2867 VARRAY_PUSH_TREE (*vrp_variables_p
, TREE_OPERAND (cond
, 0));
2871 /* Given a conditional statement IF_STMT, return the assignment 'X = Y'
2872 known to be true depending on which arm of IF_STMT is taken.
2874 Not all conditional statements will result in a useful assignment.
2875 Return NULL_TREE in that case.
2877 Also enter into the available expression table statements of
2884 This allows us to lookup the condition in a dominated block and
2885 get back a constant indicating if the condition is true. */
2887 static struct eq_expr_value
2888 get_eq_expr_value (tree if_stmt
,
2890 varray_type
*block_avail_exprs_p
,
2892 varray_type
*vrp_variables_p
)
2895 struct eq_expr_value retval
;
2897 cond
= COND_EXPR_COND (if_stmt
);
2901 /* If the conditional is a single variable 'X', return 'X = 1' for
2902 the true arm and 'X = 0' on the false arm. */
2903 if (TREE_CODE (cond
) == SSA_NAME
)
2906 retval
.src
= (true_arm
? integer_one_node
: integer_zero_node
);
2910 /* If we have a comparison expression, then record its result into
2911 the available expression table. */
2912 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == '<')
2914 tree op0
= TREE_OPERAND (cond
, 0);
2915 tree op1
= TREE_OPERAND (cond
, 1);
2917 /* Special case comparing booleans against a constant as we know
2918 the value of OP0 on both arms of the branch. ie, we can record
2919 an equivalence for OP0 rather than COND. */
2920 if ((TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
2921 && TREE_CODE (op0
) == SSA_NAME
2922 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
2923 && is_gimple_min_invariant (op1
))
2925 if ((TREE_CODE (cond
) == EQ_EXPR
&& true_arm
)
2926 || (TREE_CODE (cond
) == NE_EXPR
&& ! true_arm
))
2932 if (integer_zerop (op1
))
2933 retval
.src
= boolean_true_node
;
2935 retval
.src
= boolean_false_node
;
2941 if (TREE_CODE (op0
) == SSA_NAME
2942 && (is_gimple_min_invariant (op1
) || TREE_CODE (op1
) == SSA_NAME
))
2944 tree inverted
= invert_truthvalue (cond
);
2946 /* When we find an available expression in the hash table, we replace
2947 the expression with the LHS of the statement in the hash table.
2949 So, we want to build statements such as "1 = <condition>" on the
2950 true arm and "0 = <condition>" on the false arm. That way if we
2951 find the expression in the table, we will replace it with its
2952 known constant value. Also insert inversions of the result and
2953 condition into the hash table. */
2956 record_cond (cond
, boolean_true_node
, block_avail_exprs_p
);
2957 record_cond (inverted
, boolean_false_node
, block_avail_exprs_p
);
2959 if (TREE_CONSTANT (op1
))
2960 record_range (cond
, bb
, vrp_variables_p
);
2962 /* If the conditional is of the form 'X == Y', return 'X = Y'
2963 for the true arm. */
2964 if (TREE_CODE (cond
) == EQ_EXPR
)
2974 record_cond (inverted
, boolean_true_node
, block_avail_exprs_p
);
2975 record_cond (cond
, boolean_false_node
, block_avail_exprs_p
);
2977 if (TREE_CONSTANT (op1
))
2978 record_range (inverted
, bb
, vrp_variables_p
);
2980 /* If the conditional is of the form 'X != Y', return 'X = Y'
2981 for the false arm. */
2982 if (TREE_CODE (cond
) == NE_EXPR
)
2995 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
2996 MODIFY_EXPR statements. We compute a value number for expressions using
2997 the code of the expression and the SSA numbers of its operands. */
3000 avail_expr_hash (const void *p
)
3002 stmt_ann_t ann
= ((struct expr_hash_elt
*)p
)->ann
;
3003 tree rhs
= ((struct expr_hash_elt
*)p
)->rhs
;
3008 /* iterative_hash_expr knows how to deal with any expression and
3009 deals with commutative operators as well, so just use it instead
3010 of duplicating such complexities here. */
3011 val
= iterative_hash_expr (rhs
, val
);
3013 /* If the hash table entry is not associated with a statement, then we
3014 can just hash the expression and not worry about virtual operands
3019 /* Add the SSA version numbers of every vuse operand. This is important
3020 because compound variables like arrays are not renamed in the
3021 operands. Rather, the rename is done on the virtual variable
3022 representing all the elements of the array. */
3023 vuses
= VUSE_OPS (ann
);
3024 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
3025 val
= iterative_hash_expr (VUSE_OP (vuses
, i
), val
);
3032 avail_expr_eq (const void *p1
, const void *p2
)
3034 stmt_ann_t ann1
= ((struct expr_hash_elt
*)p1
)->ann
;
3035 tree rhs1
= ((struct expr_hash_elt
*)p1
)->rhs
;
3036 stmt_ann_t ann2
= ((struct expr_hash_elt
*)p2
)->ann
;
3037 tree rhs2
= ((struct expr_hash_elt
*)p2
)->rhs
;
3039 /* If they are the same physical expression, return true. */
3040 if (rhs1
== rhs2
&& ann1
== ann2
)
3043 /* If their codes are not equal, then quit now. */
3044 if (TREE_CODE (rhs1
) != TREE_CODE (rhs2
))
3047 /* In case of a collision, both RHS have to be identical and have the
3048 same VUSE operands. */
3049 if ((TREE_TYPE (rhs1
) == TREE_TYPE (rhs2
)
3050 || lang_hooks
.types_compatible_p (TREE_TYPE (rhs1
), TREE_TYPE (rhs2
)))
3051 && operand_equal_p (rhs1
, rhs2
, OEP_PURE_SAME
))
3053 vuse_optype ops1
= NULL
;
3054 vuse_optype ops2
= NULL
;
3055 size_t num_ops1
= 0;
3056 size_t num_ops2
= 0;
3061 ops1
= VUSE_OPS (ann1
);
3062 num_ops1
= NUM_VUSES (ops1
);
3067 ops2
= VUSE_OPS (ann2
);
3068 num_ops2
= NUM_VUSES (ops2
);
3071 /* If the number of virtual uses is different, then we consider
3073 if (num_ops1
!= num_ops2
)
3076 for (i
= 0; i
< num_ops1
; i
++)
3077 if (VUSE_OP (ops1
, i
) != VUSE_OP (ops2
, i
))
3080 #ifdef ENABLE_CHECKING
3081 if (((struct expr_hash_elt
*)p1
)->hash
3082 != ((struct expr_hash_elt
*)p2
)->hash
)
3091 /* Given STMT and a pointer to the block local defintions BLOCK_DEFS_P,
3092 register register all objects set by this statement into BLOCK_DEFS_P
3096 register_definitions_for_stmt (stmt_ann_t ann
, varray_type
*block_defs_p
)
3102 defs
= DEF_OPS (ann
);
3103 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
3105 tree def
= DEF_OP (defs
, i
);
3107 /* FIXME: We shouldn't be registering new defs if the variable
3108 doesn't need to be renamed. */
3109 register_new_def (def
, block_defs_p
);
3112 /* Register new virtual definitions made by the statement. */
3113 vdefs
= VDEF_OPS (ann
);
3114 for (i
= 0; i
< NUM_VDEFS (vdefs
); i
++)
3116 /* FIXME: We shouldn't be registering new defs if the variable
3117 doesn't need to be renamed. */
3118 register_new_def (VDEF_RESULT (vdefs
, i
), block_defs_p
);