1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
31 #include "basic-block.h"
36 #include "diagnostic.h"
38 #include "tree-dump.h"
39 #include "tree-flow.h"
42 #include "tree-pass.h"
43 #include "tree-ssa-propagate.h"
44 #include "langhooks.h"
46 /* This file implements optimizations on the dominator tree. */
48 /* Hash table with expressions made available during the renaming process.
49 When an assignment of the form X_i = EXPR is found, the statement is
50 stored in this table. If the same expression EXPR is later found on the
51 RHS of another statement, it is replaced with X_i (thus performing
52 global redundancy elimination). Similarly as we pass through conditionals
53 we record the conditional itself as having either a true or false value
55 static htab_t avail_exprs;
57 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
58 expressions it enters into the hash table along with a marker entry
59 (null). When we finish processing the block, we pop off entries and
60 remove the expressions from the global hash table until we hit the
62 static varray_type avail_exprs_stack;
64 /* Stack of trees used to restore the global currdefs to its original
65 state after completing optimization of a block and its dominator children.
67 An SSA_NAME indicates that the current definition of the underlying
68 variable should be set to the given SSA_NAME.
70 A _DECL node indicates that the underlying variable has no current
73 A NULL node is used to mark the last node associated with the
75 varray_type block_defs_stack;
77 /* Stack of statements we need to rescan during finalization for newly
80 Statement rescanning must occur after the current block's available
81 expressions are removed from AVAIL_EXPRS. Else we may change the
82 hash code for an expression and be unable to find/remove it from
84 varray_type stmts_to_rescan;
86 /* Structure for entries in the expression hash table.
88 This requires more memory for the hash table entries, but allows us
89 to avoid creating silly tree nodes and annotations for conditionals,
90 eliminates 2 global hash tables and two block local varrays.
92 It also allows us to reduce the number of hash table lookups we
93 have to perform in lookup_avail_expr and finally it allows us to
94 significantly reduce the number of calls into the hashing routine
99 /* The value (lhs) of this expression. */
102 /* The expression (rhs) we want to record. */
105 /* The annotation if this element corresponds to a statement. */
108 /* The hash value for RHS/ann. */
112 /* Table of constant values and copies indexed by SSA name. When the
113 renaming pass finds an assignment of a constant (X_i = C) or a copy
114 assignment from another SSA variable (X_i = Y_j), it creates a mapping
115 between X_i and the RHS in this table. This mapping is used later on,
116 when renaming uses of X_i. If an assignment to X_i is found in this
117 table, instead of using X_i, we use the RHS of the statement stored in
118 this table (thus performing very simplistic copy and constant
120 static varray_type const_and_copies;
122 /* Stack of dest,src pairs that need to be restored during finalization.
124 A NULL entry is used to mark the end of pairs which need to be
125 restored during finalization of this block. */
126 static varray_type const_and_copies_stack;
128 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
129 know their exact value. */
130 static bitmap nonzero_vars;
132 /* Stack of SSA_NAMEs which need their NONZERO_VARS property cleared
133 when the current block is finalized.
135 A NULL entry is used to mark the end of names needing their
136 entry in NONZERO_VARS cleared during finalization of this block. */
137 static varray_type nonzero_vars_stack;
139 /* Track whether or not we have changed the control flow graph. */
140 static bool cfg_altered;
142 /* Bitmap of blocks that have had EH statements cleaned. We should
143 remove their dead edges eventually. */
144 static bitmap need_eh_cleanup;
146 /* Statistics for dominator optimizations. */
150 long num_exprs_considered;
154 /* Value range propagation record. Each time we encounter a conditional
155 of the form SSA_NAME COND CONST we create a new vrp_element to record
156 how the condition affects the possible values SSA_NAME may have.
158 Each record contains the condition tested (COND), and the the range of
159 values the variable may legitimately have if COND is true. Note the
160 range of values may be a smaller range than COND specifies if we have
161 recorded other ranges for this variable. Each record also contains the
162 block in which the range was recorded for invalidation purposes.
164 Note that the current known range is computed lazily. This allows us
165 to avoid the overhead of computing ranges which are never queried.
167 When we encounter a conditional, we look for records which constrain
168 the SSA_NAME used in the condition. In some cases those records allow
169 us to determine the condition's result at compile time. In other cases
170 they may allow us to simplify the condition.
172 We also use value ranges to do things like transform signed div/mod
173 operations into unsigned div/mod or to simplify ABS_EXPRs.
175 Simple experiments have shown these optimizations to not be all that
176 useful on switch statements (much to my surprise). So switch statement
177 optimizations are not performed.
179 Note carefully we do not propagate information through each statement
180 in the block. i.e., if we know variable X has a value defined of
181 [0, 25] and we encounter Y = X + 1, we do not track a value range
182 for Y (which would be [1, 26] if we cared). Similarly we do not
183 constrain values as we encounter narrowing typecasts, etc. */
187 /* The highest and lowest values the variable in COND may contain when
188 COND is true. Note this may not necessarily be the same values
189 tested by COND if the same variable was used in earlier conditionals.
191 Note this is computed lazily and thus can be NULL indicating that
192 the values have not been computed yet. */
196 /* The actual conditional we recorded. This is needed since we compute
200 /* The basic block where this record was created. We use this to determine
201 when to remove records. */
205 static struct opt_stats_d opt_stats;
207 /* A virtual array holding value range records for the variable identified
208 by the index, SSA_VERSION. */
209 static varray_type vrp_data;
211 /* Array of variables which have their values constrained by operations
212 in this basic block. We use this during finalization to know
213 which variables need their VRP data updated. */
215 /* Stack of SSA_NAMEs which had their values constrainted by operations
216 in this basic block. During finalization of this block we use this
217 list to determine which variables need their VRP data updated.
219 A NULL entry marks the end of the SSA_NAMEs associated with this block. */
220 static varray_type vrp_variables_stack;
228 /* Local functions. */
229 static void optimize_stmt (struct dom_walk_data *,
231 block_stmt_iterator);
232 static inline tree get_value_for (tree, varray_type table);
233 static inline void set_value_for (tree, tree, varray_type table);
234 static tree lookup_avail_expr (tree, bool);
235 static struct eq_expr_value get_eq_expr_value (tree, int, basic_block);
236 static hashval_t avail_expr_hash (const void *);
237 static hashval_t real_avail_expr_hash (const void *);
238 static int avail_expr_eq (const void *, const void *);
239 static void htab_statistics (FILE *, htab_t);
240 static void record_cond (tree, tree);
241 static void record_dominating_conditions (tree);
242 static void record_const_or_copy (tree, tree);
243 static void record_equality (tree, tree);
244 static tree update_rhs_and_lookup_avail_expr (tree, tree, bool);
245 static tree simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *,
247 static tree simplify_cond_and_lookup_avail_expr (tree, stmt_ann_t, int);
248 static tree simplify_switch_and_lookup_avail_expr (tree, int);
249 static tree find_equivalent_equality_comparison (tree);
250 static void record_range (tree, basic_block);
251 static bool extract_range_from_cond (tree, tree *, tree *, int *);
252 static void record_equivalences_from_phis (struct dom_walk_data *, basic_block);
253 static void record_equivalences_from_incoming_edge (struct dom_walk_data *,
255 static bool eliminate_redundant_computations (struct dom_walk_data *,
257 static void record_equivalences_from_stmt (tree, int, stmt_ann_t);
258 static void thread_across_edge (struct dom_walk_data *, edge);
259 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
260 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
261 static void cprop_into_phis (struct dom_walk_data *, basic_block);
262 static void remove_local_expressions_from_table (void);
263 static void restore_vars_to_original_value (void);
264 static void restore_currdefs_to_original_value (void);
265 static void register_definitions_for_stmt (tree);
266 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
267 static void restore_nonzero_vars_to_original_value (void);
269 /* Local version of fold that doesn't introduce cruft. */
276 /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that
277 may have been added by fold, and "useless" type conversions that might
278 now be apparent due to propagation. */
279 STRIP_USELESS_TYPE_CONVERSION (t);
284 /* Return the value associated with variable VAR in TABLE. */
287 get_value_for (tree var, varray_type table)
289 return VARRAY_TREE (table, SSA_NAME_VERSION (var));
292 /* Associate VALUE to variable VAR in TABLE. */
295 set_value_for (tree var, tree value, varray_type table)
297 VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
300 /* Jump threading, redundancy elimination and const/copy propagation.
302 This pass may expose new symbols that need to be renamed into SSA. For
303 every new symbol exposed, its corresponding bit will be set in
307 tree_ssa_dominator_optimize (void)
309 struct dom_walk_data walk_data;
312 for (i = 0; i < num_referenced_vars; i++)
313 var_ann (referenced_var (i))->current_def = NULL;
315 /* Mark loop edges so we avoid threading across loop boundaries.
316 This may result in transforming natural loop into irreducible
318 mark_dfs_back_edges ();
320 /* Create our hash tables. */
321 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
322 VARRAY_TREE_INIT (avail_exprs_stack, 20, "Available expression stack");
323 VARRAY_TREE_INIT (block_defs_stack, 20, "Block DEFS stack");
324 VARRAY_TREE_INIT (const_and_copies, num_ssa_names, "const_and_copies");
325 VARRAY_TREE_INIT (const_and_copies_stack, 20, "Block const_and_copies stack");
326 VARRAY_TREE_INIT (nonzero_vars_stack, 20, "Block nonzero_vars stack");
327 VARRAY_TREE_INIT (vrp_variables_stack, 20, "Block vrp_variables stack");
328 nonzero_vars = BITMAP_XMALLOC ();
329 VARRAY_GENERIC_PTR_INIT (vrp_data, num_ssa_names, "vrp_data");
330 need_eh_cleanup = BITMAP_XMALLOC ();
331 VARRAY_TREE_INIT (stmts_to_rescan, 20, "Statements to rescan");
333 /* Setup callbacks for the generic dominator tree walker. */
334 walk_data.walk_stmts_backward = false;
335 walk_data.dom_direction = CDI_DOMINATORS;
336 walk_data.initialize_block_local_data = NULL;
337 walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
338 walk_data.before_dom_children_walk_stmts = optimize_stmt;
339 walk_data.before_dom_children_after_stmts = cprop_into_phis;
340 walk_data.after_dom_children_before_stmts = NULL;
341 walk_data.after_dom_children_walk_stmts = NULL;
342 walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
343 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
344 When we attach more stuff we'll need to fill this out with a real
346 walk_data.global_data = NULL;
347 walk_data.block_local_data_size = 0;
349 /* Now initialize the dominator walker. */
350 init_walk_dominator_tree (&walk_data);
352 calculate_dominance_info (CDI_DOMINATORS);
354 /* If we prove certain blocks are unreachable, then we want to
355 repeat the dominator optimization process as PHI nodes may
356 have turned into copies which allows better propagation of
357 values. So we repeat until we do not identify any new unreachable
361 /* Optimize the dominator tree. */
364 /* Recursively walk the dominator tree optimizing statements. */
365 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
367 /* If we exposed any new variables, go ahead and put them into
368 SSA form now, before we handle jump threading. This simplifies
369 interactions between rewriting of _DECL nodes into SSA form
370 and rewriting SSA_NAME nodes into SSA form after block
371 duplication and CFG manipulation. */
372 if (bitmap_first_set_bit (vars_to_rename) >= 0)
374 rewrite_into_ssa (false);
375 bitmap_clear (vars_to_rename);
378 /* Thread jumps, creating duplicate blocks as needed. */
379 cfg_altered = thread_through_all_blocks ();
381 /* Removal of statements may make some EH edges dead. Purge
382 such edges from the CFG as needed. */
383 if (bitmap_first_set_bit (need_eh_cleanup) >= 0)
385 cfg_altered |= tree_purge_all_dead_eh_edges (need_eh_cleanup);
386 bitmap_zero (need_eh_cleanup);
389 free_dominance_info (CDI_DOMINATORS);
390 cfg_altered = cleanup_tree_cfg ();
391 calculate_dominance_info (CDI_DOMINATORS);
393 rewrite_ssa_into_ssa ();
395 if (VARRAY_ACTIVE_SIZE (const_and_copies) <= num_ssa_names)
397 VARRAY_GROW (const_and_copies, num_ssa_names);
398 VARRAY_GROW (vrp_data, num_ssa_names);
401 /* Reinitialize the various tables. */
402 bitmap_clear (nonzero_vars);
403 htab_empty (avail_exprs);
404 VARRAY_CLEAR (const_and_copies);
405 VARRAY_CLEAR (vrp_data);
407 for (i = 0; i < num_referenced_vars; i++)
408 var_ann (referenced_var (i))->current_def = NULL;
412 /* Debugging dumps. */
413 if (dump_file && (dump_flags & TDF_STATS))
414 dump_dominator_optimization_stats (dump_file);
416 /* We emptied the hash table earlier, now delete it completely. */
417 htab_delete (avail_exprs);
419 /* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
420 CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
421 of the do-while loop above. */
423 /* And finalize the dominator walker. */
424 fini_walk_dominator_tree (&walk_data);
426 /* Free nonzero_vars. */
427 BITMAP_XFREE (nonzero_vars);
428 BITMAP_XFREE (need_eh_cleanup);
432 gate_dominator (void)
434 return flag_tree_dom != 0;
437 struct tree_opt_pass pass_dominator =
440 gate_dominator, /* gate */
441 tree_ssa_dominator_optimize, /* execute */
444 0, /* static_pass_number */
445 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
446 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
447 0, /* properties_provided */
448 0, /* properties_destroyed */
449 0, /* todo_flags_start */
450 TODO_dump_func | TODO_rename_vars
451 | TODO_verify_ssa, /* todo_flags_finish */
456 /* We are exiting BB, see if the target block begins with a conditional
457 jump which has a known value when reached via BB. */
460 thread_across_edge (struct dom_walk_data *walk_data, edge e)
462 block_stmt_iterator bsi;
466 /* Each PHI creates a temporary equivalence, record them. */
467 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
469 tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
470 tree dst = PHI_RESULT (phi);
471 record_const_or_copy (dst, src);
472 register_new_def (dst, &block_defs_stack);
475 for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
477 tree lhs, cached_lhs;
479 stmt = bsi_stmt (bsi);
481 /* Ignore empty statements and labels. */
482 if (IS_EMPTY_STMT (stmt) || TREE_CODE (stmt) == LABEL_EXPR)
485 /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
486 value, then stop our search here. Ideally when we stop a
487 search we stop on a COND_EXPR or SWITCH_EXPR. */
488 if (TREE_CODE (stmt) != MODIFY_EXPR
489 || TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
492 /* At this point we have a statement which assigns an RHS to an
493 SSA_VAR on the LHS. We want to prove that the RHS is already
494 available and that its value is held in the current definition
495 of the LHS -- meaning that this assignment is a NOP when
496 reached via edge E. */
497 if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
498 cached_lhs = TREE_OPERAND (stmt, 1);
500 cached_lhs = lookup_avail_expr (stmt, false);
502 lhs = TREE_OPERAND (stmt, 0);
504 /* This can happen if we thread around to the start of a loop. */
505 if (lhs == cached_lhs)
508 /* If we did not find RHS in the hash table, then try again after
509 temporarily const/copy propagating the operands. */
512 /* Copy the operands. */
513 stmt_ann_t ann = stmt_ann (stmt);
514 use_optype uses = USE_OPS (ann);
515 vuse_optype vuses = VUSE_OPS (ann);
516 tree *uses_copy = xcalloc (NUM_USES (uses), sizeof (tree));
517 tree *vuses_copy = xcalloc (NUM_VUSES (vuses), sizeof (tree));
520 /* Make a copy of the uses into USES_COPY, then cprop into
522 for (i = 0; i < NUM_USES (uses); i++)
526 uses_copy[i] = USE_OP (uses, i);
527 if (TREE_CODE (USE_OP (uses, i)) == SSA_NAME)
528 tmp = get_value_for (USE_OP (uses, i), const_and_copies);
530 SET_USE_OP (uses, i, tmp);
533 /* Similarly for virtual uses. */
534 for (i = 0; i < NUM_VUSES (vuses); i++)
538 vuses_copy[i] = VUSE_OP (vuses, i);
539 if (TREE_CODE (VUSE_OP (vuses, i)) == SSA_NAME)
540 tmp = get_value_for (VUSE_OP (vuses, i), const_and_copies);
542 SET_VUSE_OP (vuses, i, tmp);
545 /* Try to lookup the new expression. */
546 cached_lhs = lookup_avail_expr (stmt, false);
548 /* Restore the statement's original uses/defs. */
549 for (i = 0; i < NUM_USES (uses); i++)
550 SET_USE_OP (uses, i, uses_copy[i]);
552 for (i = 0; i < NUM_VUSES (vuses); i++)
553 SET_VUSE_OP (vuses, i, vuses_copy[i]);
558 /* If we still did not find the expression in the hash table,
559 then we can not ignore this statement. */
564 /* If the expression in the hash table was not assigned to an
565 SSA_NAME, then we can not ignore this statement. */
566 if (TREE_CODE (cached_lhs) != SSA_NAME)
569 /* If we have different underlying variables, then we can not
570 ignore this statement. */
571 if (SSA_NAME_VAR (cached_lhs) != SSA_NAME_VAR (lhs))
574 /* If CACHED_LHS does not represent the current value of the undering
575 variable in CACHED_LHS/LHS, then we can not ignore this statement. */
576 if (var_ann (SSA_NAME_VAR (lhs))->current_def != cached_lhs)
579 /* If we got here, then we can ignore this statement and continue
580 walking through the statements in the block looking for a threadable
583 We want to record an equivalence lhs = cache_lhs so that if
584 the result of this statement is used later we can copy propagate
586 record_const_or_copy (lhs, cached_lhs);
587 register_new_def (lhs, &block_defs_stack);
590 /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
591 arm will be taken. */
593 && (TREE_CODE (stmt) == COND_EXPR
594 || TREE_CODE (stmt) == SWITCH_EXPR))
596 tree cond, cached_lhs;
599 /* Do not forward entry edges into the loop. In the case loop
600 has multiple entry edges we may end up in constructing irreducible
602 ??? We may consider forwarding the edges in the case all incoming
603 edges forward to the same destination block. */
604 if (!e->flags & EDGE_DFS_BACK)
606 for (e1 = e->dest->pred; e; e = e->pred_next)
607 if (e1->flags & EDGE_DFS_BACK)
613 /* Now temporarily cprop the operands and try to find the resulting
614 expression in the hash tables. */
615 if (TREE_CODE (stmt) == COND_EXPR)
616 cond = COND_EXPR_COND (stmt);
618 cond = SWITCH_COND (stmt);
620 if (COMPARISON_CLASS_P (cond))
622 tree dummy_cond, op0, op1;
623 enum tree_code cond_code;
625 op0 = TREE_OPERAND (cond, 0);
626 op1 = TREE_OPERAND (cond, 1);
627 cond_code = TREE_CODE (cond);
629 /* Get the current value of both operands. */
630 if (TREE_CODE (op0) == SSA_NAME)
632 tree tmp = get_value_for (op0, const_and_copies);
637 if (TREE_CODE (op1) == SSA_NAME)
639 tree tmp = get_value_for (op1, const_and_copies);
644 /* Stuff the operator and operands into our dummy conditional
645 expression, creating the dummy conditional if necessary. */
646 dummy_cond = walk_data->global_data;
649 dummy_cond = build (cond_code, boolean_type_node, op0, op1);
650 dummy_cond = build (COND_EXPR, void_type_node,
651 dummy_cond, NULL, NULL);
652 walk_data->global_data = dummy_cond;
656 TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), cond_code);
657 TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op0;
658 TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1) = op1;
661 /* If the conditional folds to an invariant, then we are done,
662 otherwise look it up in the hash tables. */
663 cached_lhs = local_fold (COND_EXPR_COND (dummy_cond));
664 if (! is_gimple_min_invariant (cached_lhs))
665 cached_lhs = lookup_avail_expr (dummy_cond, false);
666 if (!cached_lhs || ! is_gimple_min_invariant (cached_lhs))
668 cached_lhs = simplify_cond_and_lookup_avail_expr (dummy_cond,
673 /* We can have conditionals which just test the state of a
674 variable rather than use a relational operator. These are
675 simpler to handle. */
676 else if (TREE_CODE (cond) == SSA_NAME)
679 cached_lhs = get_value_for (cached_lhs, const_and_copies);
680 if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
684 cached_lhs = lookup_avail_expr (stmt, false);
688 edge taken_edge = find_taken_edge (e->dest, cached_lhs);
689 basic_block dest = (taken_edge ? taken_edge->dest : NULL);
694 /* If we have a known destination for the conditional, then
695 we can perform this optimization, which saves at least one
696 conditional jump each time it applies since we get to
697 bypass the conditional at our original destination. */
701 bb_ann (e->dest)->incoming_edge_threaded = true;
708 /* Initialize local stacks for this optimizer and record equivalences
709 upon entry to BB. Equivalences can come from the edge traversed to
710 reach BB or they may come from PHI nodes at the start of BB. */
713 dom_opt_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
715 if (dump_file && (dump_flags & TDF_DETAILS))
716 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
718 /* Push a marker on the stacks of local information so that we know how
719 far to unwind when we finalize this block. */
720 VARRAY_PUSH_TREE (avail_exprs_stack, NULL_TREE);
721 VARRAY_PUSH_TREE (block_defs_stack, NULL_TREE);
722 VARRAY_PUSH_TREE (const_and_copies_stack, NULL_TREE);
723 VARRAY_PUSH_TREE (nonzero_vars_stack, NULL_TREE);
724 VARRAY_PUSH_TREE (vrp_variables_stack, NULL_TREE);
726 record_equivalences_from_incoming_edge (walk_data, bb);
728 /* PHI nodes can create equivalences too. */
729 record_equivalences_from_phis (walk_data, bb);
732 /* Given an expression EXPR (a relational expression or a statement),
733 initialize the hash table element pointed by by ELEMENT. */
736 initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
738 /* Hash table elements may be based on conditional expressions or statements.
740 For the former case, we have no annotation and we want to hash the
741 conditional expression. In the latter case we have an annotation and
742 we want to record the expression the statement evaluates. */
743 if (COMPARISON_CLASS_P (expr) || TREE_CODE (expr) == TRUTH_NOT_EXPR)
748 else if (TREE_CODE (expr) == COND_EXPR)
750 element->ann = stmt_ann (expr);
751 element->rhs = COND_EXPR_COND (expr);
753 else if (TREE_CODE (expr) == SWITCH_EXPR)
755 element->ann = stmt_ann (expr);
756 element->rhs = SWITCH_COND (expr);
758 else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
760 element->ann = stmt_ann (expr);
761 element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);
765 element->ann = stmt_ann (expr);
766 element->rhs = TREE_OPERAND (expr, 1);
770 element->hash = avail_expr_hash (element);
773 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
774 LIMIT entries left in LOCALs. */
777 remove_local_expressions_from_table (void)
779 /* Remove all the expressions made available in this block. */
780 while (VARRAY_ACTIVE_SIZE (avail_exprs_stack) > 0)
782 struct expr_hash_elt element;
783 tree expr = VARRAY_TOP_TREE (avail_exprs_stack);
784 VARRAY_POP (avail_exprs_stack);
786 if (expr == NULL_TREE)
789 initialize_hash_element (expr, NULL, &element);
790 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
794 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
795 state, stopping when there are LIMIT entries left in LOCALs. */
798 restore_nonzero_vars_to_original_value ()
800 while (VARRAY_ACTIVE_SIZE (nonzero_vars_stack) > 0)
802 tree name = VARRAY_TOP_TREE (nonzero_vars_stack);
803 VARRAY_POP (nonzero_vars_stack);
808 bitmap_clear_bit (nonzero_vars, SSA_NAME_VERSION (name));
812 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
813 CONST_AND_COPIES to its original state, stopping when we hit a
817 restore_vars_to_original_value (void)
819 while (VARRAY_ACTIVE_SIZE (const_and_copies_stack) > 0)
821 tree prev_value, dest;
823 dest = VARRAY_TOP_TREE (const_and_copies_stack);
824 VARRAY_POP (const_and_copies_stack);
829 prev_value = VARRAY_TOP_TREE (const_and_copies_stack);
830 VARRAY_POP (const_and_copies_stack);
832 set_value_for (dest, prev_value, const_and_copies);
836 /* Similar to restore_vars_to_original_value, except that it restores
837 CURRDEFS to its original value. */
839 restore_currdefs_to_original_value (void)
841 /* Restore CURRDEFS to its original state. */
842 while (VARRAY_ACTIVE_SIZE (block_defs_stack) > 0)
844 tree tmp = VARRAY_TOP_TREE (block_defs_stack);
847 VARRAY_POP (block_defs_stack);
849 if (tmp == NULL_TREE)
852 /* If we recorded an SSA_NAME, then make the SSA_NAME the current
853 definition of its underlying variable. If we recorded anything
854 else, it must have been an _DECL node and its current reaching
855 definition must have been NULL. */
856 if (TREE_CODE (tmp) == SSA_NAME)
859 var = SSA_NAME_VAR (saved_def);
867 var_ann (var)->current_def = saved_def;
871 /* We have finished processing the dominator children of BB, perform
872 any finalization actions in preparation for leaving this node in
873 the dominator tree. */
876 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
880 /* If we are at a leaf node in the dominator graph, see if we can thread
881 the edge from BB through its successor.
883 Do this before we remove entries from our equivalence tables. */
885 && ! bb->succ->succ_next
886 && (bb->succ->flags & EDGE_ABNORMAL) == 0
887 && (get_immediate_dominator (CDI_DOMINATORS, bb->succ->dest) != bb
888 || phi_nodes (bb->succ->dest)))
891 thread_across_edge (walk_data, bb->succ);
893 else if ((last = last_stmt (bb))
894 && TREE_CODE (last) == COND_EXPR
895 && (COMPARISON_CLASS_P (COND_EXPR_COND (last))
896 || TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
898 && (bb->succ->flags & EDGE_ABNORMAL) == 0
899 && bb->succ->succ_next
900 && (bb->succ->succ_next->flags & EDGE_ABNORMAL) == 0
901 && ! bb->succ->succ_next->succ_next)
903 edge true_edge, false_edge;
904 tree cond, inverted = NULL;
905 enum tree_code cond_code;
907 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
909 cond = COND_EXPR_COND (last);
910 cond_code = TREE_CODE (cond);
912 if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
913 inverted = invert_truthvalue (cond);
915 /* If the THEN arm is the end of a dominator tree or has PHI nodes,
916 then try to thread through its edge. */
917 if (get_immediate_dominator (CDI_DOMINATORS, true_edge->dest) != bb
918 || phi_nodes (true_edge->dest))
920 /* Push a marker onto the available expression stack so that we
921 unwind any expressions related to the TRUE arm before processing
922 the false arm below. */
923 VARRAY_PUSH_TREE (avail_exprs_stack, NULL_TREE);
924 VARRAY_PUSH_TREE (block_defs_stack, NULL_TREE);
925 VARRAY_PUSH_TREE (const_and_copies_stack, NULL_TREE);
927 /* Record any equivalences created by following this edge. */
928 if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
930 record_cond (cond, boolean_true_node);
931 record_dominating_conditions (cond);
932 record_cond (inverted, boolean_false_node);
934 else if (cond_code == SSA_NAME)
935 record_const_or_copy (cond, boolean_true_node);
937 /* Now thread the edge. */
938 thread_across_edge (walk_data, true_edge);
940 /* And restore the various tables to their state before
941 we threaded this edge. */
942 remove_local_expressions_from_table ();
943 restore_vars_to_original_value ();
944 restore_currdefs_to_original_value ();
947 /* Similarly for the ELSE arm. */
948 if (get_immediate_dominator (CDI_DOMINATORS, false_edge->dest) != bb
949 || phi_nodes (false_edge->dest))
951 /* Record any equivalences created by following this edge. */
952 if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
954 record_cond (cond, boolean_false_node);
955 record_cond (inverted, boolean_true_node);
956 record_dominating_conditions (inverted);
958 else if (cond_code == SSA_NAME)
959 record_const_or_copy (cond, boolean_false_node);
961 thread_across_edge (walk_data, false_edge);
963 /* No need to remove local expressions from our tables
964 or restore vars to their original value as that will
965 be done immediately below. */
969 remove_local_expressions_from_table ();
970 restore_nonzero_vars_to_original_value ();
971 restore_vars_to_original_value ();
972 restore_currdefs_to_original_value ();
974 /* Remove VRP records associated with this basic block. They are no
977 To be efficient, we note which variables have had their values
978 constrained in this block. So walk over each variable in the
979 VRP_VARIABLEs array. */
980 while (VARRAY_ACTIVE_SIZE (vrp_variables_stack) > 0)
982 tree var = VARRAY_TOP_TREE (vrp_variables_stack);
984 /* Each variable has a stack of value range records. We want to
985 invalidate those associated with our basic block. So we walk
986 the array backwards popping off records associated with our
987 block. Once we hit a record not associated with our block
989 varray_type var_vrp_records;
991 VARRAY_POP (vrp_variables_stack);
996 var_vrp_records = VARRAY_GENERIC_PTR (vrp_data, SSA_NAME_VERSION (var));
997 while (VARRAY_ACTIVE_SIZE (var_vrp_records) > 0)
999 struct vrp_element *element
1000 = (struct vrp_element *)VARRAY_TOP_GENERIC_PTR (var_vrp_records);
1002 if (element->bb != bb)
1005 VARRAY_POP (var_vrp_records);
1010 /* If we queued any statements to rescan in this block, then
1011 go ahead and rescan them now. */
1012 while (VARRAY_ACTIVE_SIZE (stmts_to_rescan) > 0)
1014 tree stmt = VARRAY_TOP_TREE (stmts_to_rescan);
1015 basic_block stmt_bb = bb_for_stmt (stmt);
1020 VARRAY_POP (stmts_to_rescan);
1021 mark_new_vars_to_rename (stmt, vars_to_rename);
1025 /* PHI nodes can create equivalences too.
1027 Ignoring any alternatives which are the same as the result, if
1028 all the alternatives are equal, then the PHI node creates an
1031 Additionally, if all the PHI alternatives are known to have a nonzero
1032 value, then the result of this PHI is known to have a nonzero value,
1033 even if we do not know its exact value. */
1036 record_equivalences_from_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1041 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1043 tree lhs = PHI_RESULT (phi);
1047 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1049 tree t = PHI_ARG_DEF (phi, i);
1051 if (TREE_CODE (t) == SSA_NAME || is_gimple_min_invariant (t))
1053 /* Ignore alternatives which are the same as our LHS. */
1054 if (operand_equal_p (lhs, t, 0))
1057 /* If we have not processed an alternative yet, then set
1058 RHS to this alternative. */
1061 /* If we have processed an alternative (stored in RHS), then
1062 see if it is equal to this one. If it isn't, then stop
1064 else if (! operand_equal_p (rhs, t, 0))
1071 /* If we had no interesting alternatives, then all the RHS alternatives
1072 must have been the same as LHS. */
1076 /* If we managed to iterate through each PHI alternative without
1077 breaking out of the loop, then we have a PHI which may create
1078 a useful equivalence. We do not need to record unwind data for
1079 this, since this is a true assignment and not an equivalence
1080 inferred from a comparison. All uses of this ssa name are dominated
1081 by this assignment, so unwinding just costs time and space. */
1082 if (i == PHI_NUM_ARGS (phi)
1083 && may_propagate_copy (lhs, rhs))
1084 set_value_for (lhs, rhs, const_and_copies);
1086 /* Now see if we know anything about the nonzero property for the
1087 result of this PHI. */
1088 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1090 if (!PHI_ARG_NONZERO (phi, i))
1094 if (i == PHI_NUM_ARGS (phi))
1095 bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
1097 register_new_def (lhs, &block_defs_stack);
1101 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1102 return that edge. Otherwise return NULL. */
1104 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1109 for (e = bb->pred; e; e = e->pred_next)
1111 /* A loop back edge can be identified by the destination of
1112 the edge dominating the source of the edge. */
1113 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1116 /* If we have already seen a non-loop edge, then we must have
1117 multiple incoming non-loop edges and thus we return NULL. */
1121 /* This is the first non-loop incoming edge we have found. Record
1129 /* Record any equivalences created by the incoming edge to BB. If BB
1130 has more than one incoming edge, then no equivalence is created. */
1133 record_equivalences_from_incoming_edge (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1138 struct eq_expr_value eq_expr_value;
1139 tree parent_block_last_stmt = NULL;
1141 /* If our parent block ended with a control statment, then we may be
1142 able to record some equivalences based on which outgoing edge from
1143 the parent was followed. */
1144 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1147 parent_block_last_stmt = last_stmt (parent);
1148 if (parent_block_last_stmt && !is_ctrl_stmt (parent_block_last_stmt))
1149 parent_block_last_stmt = NULL;
1152 eq_expr_value.src = NULL;
1153 eq_expr_value.dst = NULL;
1155 /* If we have a single predecessor (ignoring loop backedges), then extract
1156 EDGE_FLAGS from the single incoming edge. Otherwise just return as
1157 there is nothing to do. */
1159 && parent_block_last_stmt)
1161 edge e = single_incoming_edge_ignoring_loop_edges (bb);
1162 if (e && bb_for_stmt (parent_block_last_stmt) == e->src)
1163 edge_flags = e->flags;
1170 /* If our parent block ended in a COND_EXPR, add any equivalences
1171 created by the COND_EXPR to the hash table and initialize
1172 EQ_EXPR_VALUE appropriately.
1174 EQ_EXPR_VALUE is an assignment expression created when BB's immediate
1175 dominator ends in a COND_EXPR statement whose predicate is of the form
1176 'VAR == VALUE', where VALUE may be another variable or a constant.
1177 This is used to propagate VALUE on the THEN_CLAUSE of that
1178 conditional. This assignment is inserted in CONST_AND_COPIES so that
1179 the copy and constant propagator can find more propagation
1181 if (TREE_CODE (parent_block_last_stmt) == COND_EXPR
1182 && (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1183 eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
1184 (edge_flags & EDGE_TRUE_VALUE) != 0,
1186 /* Similarly when the parent block ended in a SWITCH_EXPR.
1187 We can only know the value of the switch's condition if the dominator
1188 parent is also the only predecessor of this block. */
1189 else if (bb->pred->src == parent
1190 && TREE_CODE (parent_block_last_stmt) == SWITCH_EXPR)
1192 tree switch_cond = SWITCH_COND (parent_block_last_stmt);
1194 /* If the switch's condition is an SSA variable, then we may
1195 know its value at each of the case labels. */
1196 if (TREE_CODE (switch_cond) == SSA_NAME)
1198 tree switch_vec = SWITCH_LABELS (parent_block_last_stmt);
1199 size_t i, n = TREE_VEC_LENGTH (switch_vec);
1201 tree match_case = NULL_TREE;
1203 /* Search the case labels for those whose destination is
1204 the current basic block. */
1205 for (i = 0; i < n; ++i)
1207 tree elt = TREE_VEC_ELT (switch_vec, i);
1208 if (label_to_block (CASE_LABEL (elt)) == bb)
1210 if (++case_count > 1 || CASE_HIGH (elt))
1216 /* If we encountered precisely one CASE_LABEL_EXPR and it
1217 was not the default case, or a case range, then we know
1218 the exact value of SWITCH_COND which caused us to get to
1219 this block. Record that equivalence in EQ_EXPR_VALUE. */
1222 && CASE_LOW (match_case)
1223 && !CASE_HIGH (match_case))
1225 eq_expr_value.dst = switch_cond;
1226 eq_expr_value.src = fold_convert (TREE_TYPE (switch_cond),
1227 CASE_LOW (match_case));
1232 /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
1233 new value for VAR, so that occurrences of VAR can be replaced with
1234 VALUE while re-writing the THEN arm of a COND_EXPR. */
1235 if (eq_expr_value.src && eq_expr_value.dst)
1236 record_equality (eq_expr_value.dst, eq_expr_value.src);
1239 /* Dump SSA statistics on FILE. */
1242 dump_dominator_optimization_stats (FILE *file)
1246 fprintf (file, "Total number of statements: %6ld\n\n",
1247 opt_stats.num_stmts);
1248 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1249 opt_stats.num_exprs_considered);
1251 n_exprs = opt_stats.num_exprs_considered;
1255 fprintf (file, " Redundant expressions eliminated: %6ld (%.0f%%)\n",
1256 opt_stats.num_re, PERCENT (opt_stats.num_re,
1259 fprintf (file, "\nHash table statistics:\n");
1261 fprintf (file, " avail_exprs: ");
1262 htab_statistics (file, avail_exprs);
1266 /* Dump SSA statistics on stderr. */
1269 debug_dominator_optimization_stats (void)
1271 dump_dominator_optimization_stats (stderr);
1275 /* Dump statistics for the hash table HTAB. */
1278 htab_statistics (FILE *file, htab_t htab)
1280 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1281 (long) htab_size (htab),
1282 (long) htab_elements (htab),
1283 htab_collisions (htab));
1286 /* Record the fact that VAR has a nonzero value, though we may not know
1287 its exact value. Note that if VAR is already known to have a nonzero
1288 value, then we do nothing. */
1291 record_var_is_nonzero (tree var)
1293 int indx = SSA_NAME_VERSION (var);
1295 if (bitmap_bit_p (nonzero_vars, indx))
1298 /* Mark it in the global table. */
1299 bitmap_set_bit (nonzero_vars, indx);
1301 /* Record this SSA_NAME so that we can reset the global table
1302 when we leave this block. */
1303 VARRAY_PUSH_TREE (nonzero_vars_stack, var);
1306 /* Enter a statement into the true/false expression hash table indicating
1307 that the condition COND has the value VALUE. */
1310 record_cond (tree cond, tree value)
1312 struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
1315 initialize_hash_element (cond, value, element);
1317 slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
1318 element->hash, true);
1321 *slot = (void *) element;
1322 VARRAY_PUSH_TREE (avail_exprs_stack, cond);
1328 /* COND is a condition which is known to be true. Record variants of
1329 COND which must also be true.
1331 For example, if a < b is true, then a <= b must also be true. */
1334 record_dominating_conditions (tree cond)
1336 switch (TREE_CODE (cond))
1339 record_cond (build2 (LE_EXPR, boolean_type_node,
1340 TREE_OPERAND (cond, 0),
1341 TREE_OPERAND (cond, 1)),
1343 record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1344 TREE_OPERAND (cond, 0),
1345 TREE_OPERAND (cond, 1)),
1347 record_cond (build2 (NE_EXPR, boolean_type_node,
1348 TREE_OPERAND (cond, 0),
1349 TREE_OPERAND (cond, 1)),
1351 record_cond (build2 (LTGT_EXPR, boolean_type_node,
1352 TREE_OPERAND (cond, 0),
1353 TREE_OPERAND (cond, 1)),
1358 record_cond (build2 (GE_EXPR, boolean_type_node,
1359 TREE_OPERAND (cond, 0),
1360 TREE_OPERAND (cond, 1)),
1362 record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1363 TREE_OPERAND (cond, 0),
1364 TREE_OPERAND (cond, 1)),
1366 record_cond (build2 (NE_EXPR, boolean_type_node,
1367 TREE_OPERAND (cond, 0),
1368 TREE_OPERAND (cond, 1)),
1370 record_cond (build2 (LTGT_EXPR, boolean_type_node,
1371 TREE_OPERAND (cond, 0),
1372 TREE_OPERAND (cond, 1)),
1378 record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1379 TREE_OPERAND (cond, 0),
1380 TREE_OPERAND (cond, 1)),
1385 record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1386 TREE_OPERAND (cond, 0),
1387 TREE_OPERAND (cond, 1)),
1389 record_cond (build2 (LE_EXPR, boolean_type_node,
1390 TREE_OPERAND (cond, 0),
1391 TREE_OPERAND (cond, 1)),
1393 record_cond (build2 (GE_EXPR, boolean_type_node,
1394 TREE_OPERAND (cond, 0),
1395 TREE_OPERAND (cond, 1)),
1399 case UNORDERED_EXPR:
1400 record_cond (build2 (NE_EXPR, boolean_type_node,
1401 TREE_OPERAND (cond, 0),
1402 TREE_OPERAND (cond, 1)),
1404 record_cond (build2 (UNLE_EXPR, boolean_type_node,
1405 TREE_OPERAND (cond, 0),
1406 TREE_OPERAND (cond, 1)),
1408 record_cond (build2 (UNGE_EXPR, boolean_type_node,
1409 TREE_OPERAND (cond, 0),
1410 TREE_OPERAND (cond, 1)),
1412 record_cond (build2 (UNEQ_EXPR, boolean_type_node,
1413 TREE_OPERAND (cond, 0),
1414 TREE_OPERAND (cond, 1)),
1416 record_cond (build2 (UNLT_EXPR, boolean_type_node,
1417 TREE_OPERAND (cond, 0),
1418 TREE_OPERAND (cond, 1)),
1420 record_cond (build2 (UNGT_EXPR, boolean_type_node,
1421 TREE_OPERAND (cond, 0),
1422 TREE_OPERAND (cond, 1)),
1427 record_cond (build2 (UNLE_EXPR, boolean_type_node,
1428 TREE_OPERAND (cond, 0),
1429 TREE_OPERAND (cond, 1)),
1431 record_cond (build2 (NE_EXPR, boolean_type_node,
1432 TREE_OPERAND (cond, 0),
1433 TREE_OPERAND (cond, 1)),
1438 record_cond (build2 (UNGE_EXPR, boolean_type_node,
1439 TREE_OPERAND (cond, 0),
1440 TREE_OPERAND (cond, 1)),
1442 record_cond (build2 (NE_EXPR, boolean_type_node,
1443 TREE_OPERAND (cond, 0),
1444 TREE_OPERAND (cond, 1)),
1449 record_cond (build2 (UNLE_EXPR, boolean_type_node,
1450 TREE_OPERAND (cond, 0),
1451 TREE_OPERAND (cond, 1)),
1453 record_cond (build2 (UNGE_EXPR, boolean_type_node,
1454 TREE_OPERAND (cond, 0),
1455 TREE_OPERAND (cond, 1)),
1460 record_cond (build2 (NE_EXPR, boolean_type_node,
1461 TREE_OPERAND (cond, 0),
1462 TREE_OPERAND (cond, 1)),
1464 record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1465 TREE_OPERAND (cond, 0),
1466 TREE_OPERAND (cond, 1)),
1474 /* A helper function for record_const_or_copy and record_equality.
1475 Do the work of recording the value and undo info. */
1478 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1480 set_value_for (x, y, const_and_copies);
1482 VARRAY_PUSH_TREE (const_and_copies_stack, prev_x);
1483 VARRAY_PUSH_TREE (const_and_copies_stack, x);
1486 /* Record that X is equal to Y in const_and_copies. Record undo
1487 information in the block-local varray. */
1490 record_const_or_copy (tree x, tree y)
1492 tree prev_x = get_value_for (x, const_and_copies);
1494 if (TREE_CODE (y) == SSA_NAME)
1496 tree tmp = get_value_for (y, const_and_copies);
1501 record_const_or_copy_1 (x, y, prev_x);
1504 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1505 This constrains the cases in which we may treat this as assignment. */
1508 record_equality (tree x, tree y)
1510 tree prev_x = NULL, prev_y = NULL;
1512 if (TREE_CODE (x) == SSA_NAME)
1513 prev_x = get_value_for (x, const_and_copies);
1514 if (TREE_CODE (y) == SSA_NAME)
1515 prev_y = get_value_for (y, const_and_copies);
1517 /* If one of the previous values is invariant, then use that.
1518 Otherwise it doesn't matter which value we choose, just so
1519 long as we canonicalize on one value. */
1520 if (TREE_INVARIANT (y))
1522 else if (TREE_INVARIANT (x))
1523 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1524 else if (prev_x && TREE_INVARIANT (prev_x))
1525 x = y, y = prev_x, prev_x = prev_y;
1529 /* After the swapping, we must have one SSA_NAME. */
1530 if (TREE_CODE (x) != SSA_NAME)
1533 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1534 variable compared against zero. If we're honoring signed zeros,
1535 then we cannot record this value unless we know that the value is
1537 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1538 && (TREE_CODE (y) != REAL_CST
1539 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1542 record_const_or_copy_1 (x, y, prev_x);
1545 /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
1546 hash tables. Try to simplify the RHS using whatever equivalences
1547 we may have recorded.
1549 If we are able to simplify the RHS, then lookup the simplified form in
1550 the hash table and return the result. Otherwise return NULL. */
1553 simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
1554 tree stmt, int insert)
1556 tree rhs = TREE_OPERAND (stmt, 1);
1557 enum tree_code rhs_code = TREE_CODE (rhs);
1560 /* If we have lhs = ~x, look and see if we earlier had x = ~y.
1561 In which case we can change this statement to be lhs = y.
1562 Which can then be copy propagated.
1564 Similarly for negation. */
1565 if ((rhs_code == BIT_NOT_EXPR || rhs_code == NEGATE_EXPR)
1566 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
1568 /* Get the definition statement for our RHS. */
1569 tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
1571 /* See if the RHS_DEF_STMT has the same form as our statement. */
1572 if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR
1573 && TREE_CODE (TREE_OPERAND (rhs_def_stmt, 1)) == rhs_code)
1575 tree rhs_def_operand;
1577 rhs_def_operand = TREE_OPERAND (TREE_OPERAND (rhs_def_stmt, 1), 0);
1579 /* Verify that RHS_DEF_OPERAND is a suitable SSA variable. */
1580 if (TREE_CODE (rhs_def_operand) == SSA_NAME
1581 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1582 result = update_rhs_and_lookup_avail_expr (stmt,
1588 /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
1589 If OP is associative, create and fold (y OP C2) OP C1 which
1590 should result in (y OP C3), use that as the RHS for the
1591 assignment. Add minus to this, as we handle it specially below. */
1592 if ((associative_tree_code (rhs_code) || rhs_code == MINUS_EXPR)
1593 && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
1594 && is_gimple_min_invariant (TREE_OPERAND (rhs, 1)))
1596 tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
1598 /* See if the RHS_DEF_STMT has the same form as our statement. */
1599 if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR)
1601 tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
1602 enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
1604 if (rhs_code == rhs_def_code
1605 || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
1606 || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
1608 tree def_stmt_op0 = TREE_OPERAND (rhs_def_rhs, 0);
1609 tree def_stmt_op1 = TREE_OPERAND (rhs_def_rhs, 1);
1611 if (TREE_CODE (def_stmt_op0) == SSA_NAME
1612 && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0)
1613 && is_gimple_min_invariant (def_stmt_op1))
1615 tree outer_const = TREE_OPERAND (rhs, 1);
1616 tree type = TREE_TYPE (TREE_OPERAND (stmt, 0));
1619 /* If we care about correct floating point results, then
1620 don't fold x + c1 - c2. Note that we need to take both
1621 the codes and the signs to figure this out. */
1622 if (FLOAT_TYPE_P (type)
1623 && !flag_unsafe_math_optimizations
1624 && (rhs_def_code == PLUS_EXPR
1625 || rhs_def_code == MINUS_EXPR))
1629 neg ^= (rhs_code == MINUS_EXPR);
1630 neg ^= (rhs_def_code == MINUS_EXPR);
1631 neg ^= real_isneg (TREE_REAL_CST_PTR (outer_const));
1632 neg ^= real_isneg (TREE_REAL_CST_PTR (def_stmt_op1));
1635 goto dont_fold_assoc;
1638 /* Ho hum. So fold will only operate on the outermost
1639 thingy that we give it, so we have to build the new
1640 expression in two pieces. This requires that we handle
1641 combinations of plus and minus. */
1642 if (rhs_def_code != rhs_code)
1644 if (rhs_def_code == MINUS_EXPR)
1645 t = build (MINUS_EXPR, type, outer_const, def_stmt_op1);
1647 t = build (MINUS_EXPR, type, def_stmt_op1, outer_const);
1648 rhs_code = PLUS_EXPR;
1650 else if (rhs_def_code == MINUS_EXPR)
1651 t = build (PLUS_EXPR, type, def_stmt_op1, outer_const);
1653 t = build (rhs_def_code, type, def_stmt_op1, outer_const);
1655 t = build (rhs_code, type, def_stmt_op0, t);
1658 /* If the result is a suitable looking gimple expression,
1659 then use it instead of the original for STMT. */
1660 if (TREE_CODE (t) == SSA_NAME
1661 || (UNARY_CLASS_P (t)
1662 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1663 || ((BINARY_CLASS_P (t) || COMPARISON_CLASS_P (t))
1664 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
1665 && is_gimple_val (TREE_OPERAND (t, 1))))
1666 result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
1673 /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1674 and BIT_AND_EXPR respectively if the first operand is greater
1675 than zero and the second operand is an exact power of two. */
1676 if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
1677 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
1678 && integer_pow2p (TREE_OPERAND (rhs, 1)))
1681 tree op = TREE_OPERAND (rhs, 0);
1683 if (TYPE_UNSIGNED (TREE_TYPE (op)))
1685 val = integer_one_node;
1689 tree dummy_cond = walk_data->global_data;
1693 dummy_cond = build (GT_EXPR, boolean_type_node,
1694 op, integer_zero_node);
1695 dummy_cond = build (COND_EXPR, void_type_node,
1696 dummy_cond, NULL, NULL);
1697 walk_data->global_data = dummy_cond;
1701 TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), GT_EXPR);
1702 TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
1703 TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
1704 = integer_zero_node;
1706 val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
1709 if (val && integer_onep (val))
1712 tree op0 = TREE_OPERAND (rhs, 0);
1713 tree op1 = TREE_OPERAND (rhs, 1);
1715 if (rhs_code == TRUNC_DIV_EXPR)
1716 t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0,
1717 build_int_cst (NULL_TREE, tree_log2 (op1)));
1719 t = build (BIT_AND_EXPR, TREE_TYPE (op0), op0,
1720 local_fold (build (MINUS_EXPR, TREE_TYPE (op1),
1721 op1, integer_one_node)));
1723 result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
1727 /* Transform ABS (X) into X or -X as appropriate. */
1728 if (rhs_code == ABS_EXPR
1729 && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
1732 tree op = TREE_OPERAND (rhs, 0);
1733 tree type = TREE_TYPE (op);
1735 if (TYPE_UNSIGNED (type))
1737 val = integer_zero_node;
1741 tree dummy_cond = walk_data->global_data;
1745 dummy_cond = build (LE_EXPR, boolean_type_node,
1746 op, integer_zero_node);
1747 dummy_cond = build (COND_EXPR, void_type_node,
1748 dummy_cond, NULL, NULL);
1749 walk_data->global_data = dummy_cond;
1753 TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), LE_EXPR);
1754 TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
1755 TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
1756 = build_int_cst (type, 0);
1758 val = simplify_cond_and_lookup_avail_expr (dummy_cond, NULL, false);
1762 TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), GE_EXPR);
1763 TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
1764 TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
1765 = build_int_cst (type, 0);
1767 val = simplify_cond_and_lookup_avail_expr (dummy_cond,
1772 if (integer_zerop (val))
1773 val = integer_one_node;
1774 else if (integer_onep (val))
1775 val = integer_zero_node;
1781 && (integer_onep (val) || integer_zerop (val)))
1785 if (integer_onep (val))
1786 t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
1790 result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
1794 /* Optimize *"foo" into 'f'. This is done here rather than
1795 in fold to avoid problems with stuff like &*"foo". */
1796 if (TREE_CODE (rhs) == INDIRECT_REF || TREE_CODE (rhs) == ARRAY_REF)
1798 tree t = fold_read_from_constant_string (rhs);
1801 result = update_rhs_and_lookup_avail_expr (stmt, t, insert);
1807 /* COND is a condition of the form:
1809 x == const or x != const
1811 Look back to x's defining statement and see if x is defined as
1815 If const is unchanged if we convert it to type, then we can build
1816 the equivalent expression:
1819 y == const or y != const
1821 Which may allow further optimizations.
1823 Return the equivalent comparison or NULL if no such equivalent comparison
1827 find_equivalent_equality_comparison (tree cond)
1829 tree op0 = TREE_OPERAND (cond, 0);
1830 tree op1 = TREE_OPERAND (cond, 1);
1831 tree def_stmt = SSA_NAME_DEF_STMT (op0);
1833 /* OP0 might have been a parameter, so first make sure it
1834 was defined by a MODIFY_EXPR. */
1835 if (def_stmt && TREE_CODE (def_stmt) == MODIFY_EXPR)
1837 tree def_rhs = TREE_OPERAND (def_stmt, 1);
1839 /* Now make sure the RHS of the MODIFY_EXPR is a typecast. */
1840 if ((TREE_CODE (def_rhs) == NOP_EXPR
1841 || TREE_CODE (def_rhs) == CONVERT_EXPR)
1842 && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME)
1844 tree def_rhs_inner = TREE_OPERAND (def_rhs, 0);
1845 tree def_rhs_inner_type = TREE_TYPE (def_rhs_inner);
1848 if (TYPE_PRECISION (def_rhs_inner_type)
1849 > TYPE_PRECISION (TREE_TYPE (def_rhs)))
1852 /* What we want to prove is that if we convert OP1 to
1853 the type of the object inside the NOP_EXPR that the
1854 result is still equivalent to SRC.
1856 If that is true, the build and return new equivalent
1857 condition which uses the source of the typecast and the
1858 new constant (which has only changed its type). */
1859 new = build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1);
1860 new = local_fold (new);
1861 if (is_gimple_val (new) && tree_int_cst_equal (new, op1))
1862 return build (TREE_CODE (cond), TREE_TYPE (cond),
1863 def_rhs_inner, new);
1869 /* STMT is a COND_EXPR for which we could not trivially determine its
1870 result. This routine attempts to find equivalent forms of the
1871 condition which we may be able to optimize better. It also
1872 uses simple value range propagation to optimize conditionals. */
1875 simplify_cond_and_lookup_avail_expr (tree stmt,
1879 tree cond = COND_EXPR_COND (stmt);
1881 if (COMPARISON_CLASS_P (cond))
1883 tree op0 = TREE_OPERAND (cond, 0);
1884 tree op1 = TREE_OPERAND (cond, 1);
1886 if (TREE_CODE (op0) == SSA_NAME && is_gimple_min_invariant (op1))
1889 tree low, high, cond_low, cond_high;
1890 int lowequal, highequal, swapped, no_overlap, subset, cond_inverted;
1891 varray_type vrp_records;
1892 struct vrp_element *element;
1894 /* First see if we have test of an SSA_NAME against a constant
1895 where the SSA_NAME is defined by an earlier typecast which
1896 is irrelevant when performing tests against the given
1898 if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
1900 tree new_cond = find_equivalent_equality_comparison (cond);
1904 /* Update the statement to use the new equivalent
1906 COND_EXPR_COND (stmt) = new_cond;
1908 /* If this is not a real stmt, ann will be NULL and we
1909 avoid processing the operands. */
1913 /* Lookup the condition and return its known value if it
1915 new_cond = lookup_avail_expr (stmt, insert);
1919 /* The operands have changed, so update op0 and op1. */
1920 op0 = TREE_OPERAND (cond, 0);
1921 op1 = TREE_OPERAND (cond, 1);
1925 /* Consult the value range records for this variable (if they exist)
1926 to see if we can eliminate or simplify this conditional.
1928 Note two tests are necessary to determine no records exist.
1929 First we have to see if the virtual array exists, if it
1930 exists, then we have to check its active size.
1932 Also note the vast majority of conditionals are not testing
1933 a variable which has had its range constrained by an earlier
1934 conditional. So this filter avoids a lot of unnecessary work. */
1935 vrp_records = VARRAY_GENERIC_PTR (vrp_data, SSA_NAME_VERSION (op0));
1936 if (vrp_records == NULL)
1939 limit = VARRAY_ACTIVE_SIZE (vrp_records);
1941 /* If we have no value range records for this variable, or we are
1942 unable to extract a range for this condition, then there is
1945 || ! extract_range_from_cond (cond, &cond_high,
1946 &cond_low, &cond_inverted))
1949 /* We really want to avoid unnecessary computations of range
1950 info. So all ranges are computed lazily; this avoids a
1951 lot of unnecessary work. i.e., we record the conditional,
1952 but do not process how it constrains the variable's
1953 potential values until we know that processing the condition
1956 However, we do not want to have to walk a potentially long
1957 list of ranges, nor do we want to compute a variable's
1958 range more than once for a given path.
1960 Luckily, each time we encounter a conditional that can not
1961 be otherwise optimized we will end up here and we will
1962 compute the necessary range information for the variable
1963 used in this condition.
1965 Thus you can conclude that there will never be more than one
1966 conditional associated with a variable which has not been
1967 processed. So we never need to merge more than one new
1968 conditional into the current range.
1970 These properties also help us avoid unnecessary work. */
1972 = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records, limit - 1);
1974 if (element->high && element->low)
1976 /* The last element has been processed, so there is no range
1977 merging to do, we can simply use the high/low values
1978 recorded in the last element. */
1980 high = element->high;
1984 tree tmp_high, tmp_low;
1987 /* The last element has not been processed. Process it now. */
1988 extract_range_from_cond (element->cond, &tmp_high,
1991 /* If this is the only element, then no merging is necessary,
1992 the high/low values from extract_range_from_cond are all
2001 /* Get the high/low value from the previous element. */
2002 struct vrp_element *prev
2003 = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records,
2008 /* Merge in this element's range with the range from the
2011 The low value for the merged range is the maximum of
2012 the previous low value and the low value of this record.
2014 Similarly the high value for the merged range is the
2015 minimum of the previous high value and the high value of
2017 low = (tree_int_cst_compare (low, tmp_low) == 1
2019 high = (tree_int_cst_compare (high, tmp_high) == -1
2023 /* And record the computed range. */
2025 element->high = high;
2029 /* After we have constrained this variable's potential values,
2030 we try to determine the result of the given conditional.
2032 To simplify later tests, first determine if the current
2033 low value is the same low value as the conditional.
2034 Similarly for the current high value and the high value
2035 for the conditional. */
2036 lowequal = tree_int_cst_equal (low, cond_low);
2037 highequal = tree_int_cst_equal (high, cond_high);
2039 if (lowequal && highequal)
2040 return (cond_inverted ? boolean_false_node : boolean_true_node);
2042 /* To simplify the overlap/subset tests below we may want
2043 to swap the two ranges so that the larger of the two
2044 ranges occurs "first". */
2046 if (tree_int_cst_compare (low, cond_low) == 1
2048 && tree_int_cst_compare (cond_high, high) == 1))
2061 /* Now determine if there is no overlap in the ranges
2062 or if the second range is a subset of the first range. */
2063 no_overlap = tree_int_cst_lt (high, cond_low);
2064 subset = tree_int_cst_compare (cond_high, high) != 1;
2066 /* If there was no overlap in the ranges, then this conditional
2067 always has a false value (unless we had to invert this
2068 conditional, in which case it always has a true value). */
2070 return (cond_inverted ? boolean_true_node : boolean_false_node);
2072 /* If the current range is a subset of the condition's range,
2073 then this conditional always has a true value (unless we
2074 had to invert this conditional, in which case it always
2075 has a true value). */
2076 if (subset && swapped)
2077 return (cond_inverted ? boolean_false_node : boolean_true_node);
2079 /* We were unable to determine the result of the conditional.
2080 However, we may be able to simplify the conditional. First
2081 merge the ranges in the same manner as range merging above. */
2082 low = tree_int_cst_compare (low, cond_low) == 1 ? low : cond_low;
2083 high = tree_int_cst_compare (high, cond_high) == -1 ? high : cond_high;
2085 /* If the range has converged to a single point, then turn this
2086 into an equality comparison. */
2087 if (TREE_CODE (cond) != EQ_EXPR
2088 && TREE_CODE (cond) != NE_EXPR
2089 && tree_int_cst_equal (low, high))
2091 TREE_SET_CODE (cond, EQ_EXPR);
2092 TREE_OPERAND (cond, 1) = high;
2099 /* STMT is a SWITCH_EXPR for which we could not trivially determine its
2100 result. This routine attempts to find equivalent forms of the
2101 condition which we may be able to optimize better. */
2104 simplify_switch_and_lookup_avail_expr (tree stmt, int insert)
2106 tree cond = SWITCH_COND (stmt);
2109 /* The optimization that we really care about is removing unnecessary
2110 casts. That will let us do much better in propagating the inferred
2111 constant at the switch target. */
2112 if (TREE_CODE (cond) == SSA_NAME)
2114 def = SSA_NAME_DEF_STMT (cond);
2115 if (TREE_CODE (def) == MODIFY_EXPR)
2117 def = TREE_OPERAND (def, 1);
2118 if (TREE_CODE (def) == NOP_EXPR)
2123 def = TREE_OPERAND (def, 0);
2125 #ifdef ENABLE_CHECKING
2126 /* ??? Why was Jeff testing this? We are gimple... */
2127 gcc_assert (is_gimple_val (def));
2130 to = TREE_TYPE (cond);
2131 ti = TREE_TYPE (def);
2133 /* If we have an extension that preserves value, then we
2134 can copy the source value into the switch. */
2136 need_precision = TYPE_PRECISION (ti);
2138 if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
2140 else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
2141 need_precision += 1;
2142 if (TYPE_PRECISION (to) < need_precision)
2147 SWITCH_COND (stmt) = def;
2150 return lookup_avail_expr (stmt, insert);
2160 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2161 known value for that SSA_NAME (or NULL if no value is known).
2163 NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
2164 even if we don't know their precise value.
2166 Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
2167 nodes of the successors of BB. */
2170 cprop_into_successor_phis (basic_block bb,
2171 varray_type const_and_copies,
2172 bitmap nonzero_vars)
2176 /* This can get rather expensive if the implementation is naive in
2177 how it finds the phi alternative associated with a particular edge. */
2178 for (e = bb->succ; e; e = e->succ_next)
2184 /* If this is an abnormal edge, then we do not want to copy propagate
2185 into the PHI alternative associated with this edge. */
2186 if (e->flags & EDGE_ABNORMAL)
2189 phi = phi_nodes (e->dest);
2193 /* There is no guarantee that for any two PHI nodes in a block that
2194 the phi alternative associated with a particular edge will be
2195 at the same index in the phi alternative array.
2197 However, it is very likely they will be the same. So we keep
2198 track of the index of the alternative where we found the edge in
2199 the previous phi node and check that index first in the next
2200 phi node. If that hint fails, then we actually search all
2202 phi_num_args = PHI_NUM_ARGS (phi);
2203 hint = phi_num_args;
2204 for ( ; phi; phi = PHI_CHAIN (phi))
2208 use_operand_p orig_p;
2211 /* If the hint is valid (!= phi_num_args), see if it points
2212 us to the desired phi alternative. */
2213 if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
2217 /* The hint was either invalid or did not point to the
2218 correct phi alternative. Search all the alternatives
2219 for the correct one. Update the hint. */
2220 for (i = 0; i < phi_num_args; i++)
2221 if (PHI_ARG_EDGE (phi, i) == e)
2226 /* If we did not find the proper alternative, then something is
2228 gcc_assert (hint != phi_num_args);
2230 /* The alternative may be associated with a constant, so verify
2231 it is an SSA_NAME before doing anything with it. */
2232 orig_p = PHI_ARG_DEF_PTR (phi, hint);
2233 orig = USE_FROM_PTR (orig_p);
2234 if (TREE_CODE (orig) != SSA_NAME)
2237 /* If the alternative is known to have a nonzero value, record
2238 that fact in the PHI node itself for future use. */
2239 if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
2240 PHI_ARG_NONZERO (phi, hint) = true;
2242 /* If we have *ORIG_P in our constant/copy table, then replace
2243 ORIG_P with its value in our constant/copy table. */
2244 new = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (orig));
2246 && (TREE_CODE (new) == SSA_NAME
2247 || is_gimple_min_invariant (new))
2248 && may_propagate_copy (orig, new))
2250 propagate_value (orig_p, new);
2257 /* Propagate known constants/copies into PHI nodes of BB's successor
2261 cprop_into_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2264 cprop_into_successor_phis (bb, const_and_copies, nonzero_vars);
2267 /* Search for redundant computations in STMT. If any are found, then
2268 replace them with the variable holding the result of the computation.
2270 If safe, record this expression into the available expression hash
2274 eliminate_redundant_computations (struct dom_walk_data *walk_data,
2275 tree stmt, stmt_ann_t ann)
2277 v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);
2278 tree *expr_p, def = NULL_TREE;
2281 bool retval = false;
2283 if (TREE_CODE (stmt) == MODIFY_EXPR)
2284 def = TREE_OPERAND (stmt, 0);
2286 /* Certain expressions on the RHS can be optimized away, but can not
2287 themselves be entered into the hash tables. */
2288 if (ann->makes_aliased_stores
2290 || TREE_CODE (def) != SSA_NAME
2291 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
2292 || NUM_V_MAY_DEFS (v_may_defs) != 0)
2295 /* Check if the expression has been computed before. */
2296 cached_lhs = lookup_avail_expr (stmt, insert);
2298 /* If this is an assignment and the RHS was not in the hash table,
2299 then try to simplify the RHS and lookup the new RHS in the
2301 if (! cached_lhs && TREE_CODE (stmt) == MODIFY_EXPR)
2302 cached_lhs = simplify_rhs_and_lookup_avail_expr (walk_data, stmt, insert);
2303 /* Similarly if this is a COND_EXPR and we did not find its
2304 expression in the hash table, simplify the condition and
2306 else if (! cached_lhs && TREE_CODE (stmt) == COND_EXPR)
2307 cached_lhs = simplify_cond_and_lookup_avail_expr (stmt, ann, insert);
2308 /* Similarly for a SWITCH_EXPR. */
2309 else if (!cached_lhs && TREE_CODE (stmt) == SWITCH_EXPR)
2310 cached_lhs = simplify_switch_and_lookup_avail_expr (stmt, insert);
2312 opt_stats.num_exprs_considered++;
2314 /* Get a pointer to the expression we are trying to optimize. */
2315 if (TREE_CODE (stmt) == COND_EXPR)
2316 expr_p = &COND_EXPR_COND (stmt);
2317 else if (TREE_CODE (stmt) == SWITCH_EXPR)
2318 expr_p = &SWITCH_COND (stmt);
2319 else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
2320 expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
2322 expr_p = &TREE_OPERAND (stmt, 1);
2324 /* It is safe to ignore types here since we have already done
2325 type checking in the hashing and equality routines. In fact
2326 type checking here merely gets in the way of constant
2327 propagation. Also, make sure that it is safe to propagate
2328 CACHED_LHS into *EXPR_P. */
2330 && (TREE_CODE (cached_lhs) != SSA_NAME
2331 || may_propagate_copy (*expr_p, cached_lhs)))
2333 if (dump_file && (dump_flags & TDF_DETAILS))
2335 fprintf (dump_file, " Replaced redundant expr '");
2336 print_generic_expr (dump_file, *expr_p, dump_flags);
2337 fprintf (dump_file, "' with '");
2338 print_generic_expr (dump_file, cached_lhs, dump_flags);
2339 fprintf (dump_file, "'\n");
2344 #if defined ENABLE_CHECKING
2345 gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
2346 || is_gimple_min_invariant (cached_lhs));
2349 if (TREE_CODE (cached_lhs) == ADDR_EXPR
2350 || (POINTER_TYPE_P (TREE_TYPE (*expr_p))
2351 && is_gimple_min_invariant (cached_lhs)))
2354 propagate_tree_value (expr_p, cached_lhs);
2360 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
2361 the available expressions table or the const_and_copies table.
2362 Detect and record those equivalences. */
2365 record_equivalences_from_stmt (tree stmt,
2369 tree lhs = TREE_OPERAND (stmt, 0);
2370 enum tree_code lhs_code = TREE_CODE (lhs);
2373 if (lhs_code == SSA_NAME)
2375 tree rhs = TREE_OPERAND (stmt, 1);
2377 /* Strip away any useless type conversions. */
2378 STRIP_USELESS_TYPE_CONVERSION (rhs);
2380 /* If the RHS of the assignment is a constant or another variable that
2381 may be propagated, register it in the CONST_AND_COPIES table. We
2382 do not need to record unwind data for this, since this is a true
2383 assignment and not an equivalence inferred from a comparison. All
2384 uses of this ssa name are dominated by this assignment, so unwinding
2385 just costs time and space. */
2387 && (TREE_CODE (rhs) == SSA_NAME
2388 || is_gimple_min_invariant (rhs)))
2389 set_value_for (lhs, rhs, const_and_copies);
2391 /* alloca never returns zero and the address of a non-weak symbol
2392 is never zero. NOP_EXPRs and CONVERT_EXPRs can be completely
2393 stripped as they do not affect this equivalence. */
2394 while (TREE_CODE (rhs) == NOP_EXPR
2395 || TREE_CODE (rhs) == CONVERT_EXPR)
2396 rhs = TREE_OPERAND (rhs, 0);
2398 if (alloca_call_p (rhs)
2399 || (TREE_CODE (rhs) == ADDR_EXPR
2400 && DECL_P (TREE_OPERAND (rhs, 0))
2401 && ! DECL_WEAK (TREE_OPERAND (rhs, 0))))
2402 record_var_is_nonzero (lhs);
2404 /* IOR of any value with a nonzero value will result in a nonzero
2405 value. Even if we do not know the exact result recording that
2406 the result is nonzero is worth the effort. */
2407 if (TREE_CODE (rhs) == BIT_IOR_EXPR
2408 && integer_nonzerop (TREE_OPERAND (rhs, 1)))
2409 record_var_is_nonzero (lhs);
2412 /* Look at both sides for pointer dereferences. If we find one, then
2413 the pointer must be nonnull and we can enter that equivalence into
2415 if (flag_delete_null_pointer_checks)
2416 for (i = 0; i < 2; i++)
2418 tree t = TREE_OPERAND (stmt, i);
2420 /* Strip away any COMPONENT_REFs. */
2421 while (TREE_CODE (t) == COMPONENT_REF)
2422 t = TREE_OPERAND (t, 0);
2424 /* Now see if this is a pointer dereference. */
2425 if (TREE_CODE (t) == INDIRECT_REF)
2427 tree op = TREE_OPERAND (t, 0);
2429 /* If the pointer is a SSA variable, then enter new
2430 equivalences into the hash table. */
2431 while (TREE_CODE (op) == SSA_NAME)
2433 tree def = SSA_NAME_DEF_STMT (op);
2435 record_var_is_nonzero (op);
2437 /* And walk up the USE-DEF chains noting other SSA_NAMEs
2438 which are known to have a nonzero value. */
2440 && TREE_CODE (def) == MODIFY_EXPR
2441 && TREE_CODE (TREE_OPERAND (def, 1)) == NOP_EXPR)
2442 op = TREE_OPERAND (TREE_OPERAND (def, 1), 0);
2449 /* A memory store, even an aliased store, creates a useful
2450 equivalence. By exchanging the LHS and RHS, creating suitable
2451 vops and recording the result in the available expression table,
2452 we may be able to expose more redundant loads. */
2453 if (!ann->has_volatile_ops
2454 && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
2455 || is_gimple_min_invariant (TREE_OPERAND (stmt, 1)))
2456 && !is_gimple_reg (lhs))
2458 tree rhs = TREE_OPERAND (stmt, 1);
2461 /* FIXME: If the LHS of the assignment is a bitfield and the RHS
2462 is a constant, we need to adjust the constant to fit into the
2463 type of the LHS. If the LHS is a bitfield and the RHS is not
2464 a constant, then we can not record any equivalences for this
2465 statement since we would need to represent the widening or
2466 narrowing of RHS. This fixes gcc.c-torture/execute/921016-1.c
2467 and should not be necessary if GCC represented bitfields
2469 if (lhs_code == COMPONENT_REF
2470 && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
2472 if (TREE_CONSTANT (rhs))
2473 rhs = widen_bitfield (rhs, TREE_OPERAND (lhs, 1), lhs);
2477 /* If the value overflowed, then we can not use this equivalence. */
2478 if (rhs && ! is_gimple_min_invariant (rhs))
2484 /* Build a new statement with the RHS and LHS exchanged. */
2485 new = build (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
2487 create_ssa_artficial_load_stmt (&(ann->operands), new);
2489 /* Finally enter the statement into the available expression
2491 lookup_avail_expr (new, true);
2496 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2497 CONST_AND_COPIES. */
2500 cprop_operand (tree stmt, use_operand_p op_p, varray_type const_and_copies)
2502 bool may_have_exposed_new_symbols = false;
2504 tree op = USE_FROM_PTR (op_p);
2506 /* If the operand has a known constant value or it is known to be a
2507 copy of some other variable, use the value or copy stored in
2508 CONST_AND_COPIES. */
2509 val = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (op));
2512 tree op_type, val_type;
2514 /* Do not change the base variable in the virtual operand
2515 tables. That would make it impossible to reconstruct
2516 the renamed virtual operand if we later modify this
2517 statement. Also only allow the new value to be an SSA_NAME
2518 for propagation into virtual operands. */
2519 if (!is_gimple_reg (op)
2520 && (get_virtual_var (val) != get_virtual_var (op)
2521 || TREE_CODE (val) != SSA_NAME))
2524 /* Get the toplevel type of each operand. */
2525 op_type = TREE_TYPE (op);
2526 val_type = TREE_TYPE (val);
2528 /* While both types are pointers, get the type of the object
2530 while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
2532 op_type = TREE_TYPE (op_type);
2533 val_type = TREE_TYPE (val_type);
2536 /* Make sure underlying types match before propagating a constant by
2537 converting the constant to the proper type. Note that convert may
2538 return a non-gimple expression, in which case we ignore this
2539 propagation opportunity. */
2540 if (TREE_CODE (val) != SSA_NAME)
2542 if (!lang_hooks.types_compatible_p (op_type, val_type))
2544 val = fold_convert (TREE_TYPE (op), val);
2545 if (!is_gimple_min_invariant (val))
2550 /* Certain operands are not allowed to be copy propagated due
2551 to their interaction with exception handling and some GCC
2553 else if (!may_propagate_copy (op, val))
2557 if (dump_file && (dump_flags & TDF_DETAILS))
2559 fprintf (dump_file, " Replaced '");
2560 print_generic_expr (dump_file, op, dump_flags);
2561 fprintf (dump_file, "' with %s '",
2562 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2563 print_generic_expr (dump_file, val, dump_flags);
2564 fprintf (dump_file, "'\n");
2567 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2568 that we may have exposed a new symbol for SSA renaming. */
2569 if (TREE_CODE (val) == ADDR_EXPR
2570 || (POINTER_TYPE_P (TREE_TYPE (op))
2571 && is_gimple_min_invariant (val)))
2572 may_have_exposed_new_symbols = true;
2574 propagate_value (op_p, val);
2576 /* And note that we modified this statement. This is now
2577 safe, even if we changed virtual operands since we will
2578 rescan the statement and rewrite its operands again. */
2581 return may_have_exposed_new_symbols;
2584 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2585 known value for that SSA_NAME (or NULL if no value is known).
2587 Propagate values from CONST_AND_COPIES into the uses, vuses and
2588 v_may_def_ops of STMT. */
2591 cprop_into_stmt (tree stmt, varray_type const_and_copies)
2593 bool may_have_exposed_new_symbols = false;
2598 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
2600 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
2601 may_have_exposed_new_symbols
2602 |= cprop_operand (stmt, op_p, const_and_copies);
2605 if (may_have_exposed_new_symbols)
2607 rhs = get_rhs (stmt);
2608 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
2609 recompute_tree_invarant_for_addr_expr (rhs);
2612 return may_have_exposed_new_symbols;
2616 /* Optimize the statement pointed by iterator SI.
2618 We try to perform some simplistic global redundancy elimination and
2619 constant propagation:
2621 1- To detect global redundancy, we keep track of expressions that have
2622 been computed in this block and its dominators. If we find that the
2623 same expression is computed more than once, we eliminate repeated
2624 computations by using the target of the first one.
2626 2- Constant values and copy assignments. This is used to do very
2627 simplistic constant and copy propagation. When a constant or copy
2628 assignment is found, we map the value on the RHS of the assignment to
2629 the variable in the LHS in the CONST_AND_COPIES table. */
2632 optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
2633 block_stmt_iterator si)
2637 bool may_optimize_p;
2638 bool may_have_exposed_new_symbols = false;
2640 stmt = bsi_stmt (si);
2642 get_stmt_operands (stmt);
2643 ann = stmt_ann (stmt);
2644 opt_stats.num_stmts++;
2645 may_have_exposed_new_symbols = false;
2647 if (dump_file && (dump_flags & TDF_DETAILS))
2649 fprintf (dump_file, "Optimizing statement ");
2650 print_generic_stmt (dump_file, stmt, TDF_SLIM);
2653 /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs. */
2654 may_have_exposed_new_symbols = cprop_into_stmt (stmt, const_and_copies);
2656 /* If the statement has been modified with constant replacements,
2657 fold its RHS before checking for redundant computations. */
2660 /* Try to fold the statement making sure that STMT is kept
2662 if (fold_stmt (bsi_stmt_ptr (si)))
2664 stmt = bsi_stmt (si);
2665 ann = stmt_ann (stmt);
2667 if (dump_file && (dump_flags & TDF_DETAILS))
2669 fprintf (dump_file, " Folded to: ");
2670 print_generic_stmt (dump_file, stmt, TDF_SLIM);
2674 /* Constant/copy propagation above may change the set of
2675 virtual operands associated with this statement. Folding
2676 may remove the need for some virtual operands.
2678 Indicate we will need to rescan and rewrite the statement. */
2679 may_have_exposed_new_symbols = true;
2682 /* Check for redundant computations. Do this optimization only
2683 for assignments that have no volatile ops and conditionals. */
2684 may_optimize_p = (!ann->has_volatile_ops
2685 && ((TREE_CODE (stmt) == RETURN_EXPR
2686 && TREE_OPERAND (stmt, 0)
2687 && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR
2688 && ! (TREE_SIDE_EFFECTS
2689 (TREE_OPERAND (TREE_OPERAND (stmt, 0), 1))))
2690 || (TREE_CODE (stmt) == MODIFY_EXPR
2691 && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1)))
2692 || TREE_CODE (stmt) == COND_EXPR
2693 || TREE_CODE (stmt) == SWITCH_EXPR));
2696 may_have_exposed_new_symbols
2697 |= eliminate_redundant_computations (walk_data, stmt, ann);
2699 /* Record any additional equivalences created by this statement. */
2700 if (TREE_CODE (stmt) == MODIFY_EXPR)
2701 record_equivalences_from_stmt (stmt,
2705 register_definitions_for_stmt (stmt);
2707 /* If STMT is a COND_EXPR and it was modified, then we may know
2708 where it goes. If that is the case, then mark the CFG as altered.
2710 This will cause us to later call remove_unreachable_blocks and
2711 cleanup_tree_cfg when it is safe to do so. It is not safe to
2712 clean things up here since removal of edges and such can trigger
2713 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2716 That's all fine and good, except that once SSA_NAMEs are released
2717 to the manager, we must not call create_ssa_name until all references
2718 to released SSA_NAMEs have been eliminated.
2720 All references to the deleted SSA_NAMEs can not be eliminated until
2721 we remove unreachable blocks.
2723 We can not remove unreachable blocks until after we have completed
2724 any queued jump threading.
2726 We can not complete any queued jump threads until we have taken
2727 appropriate variables out of SSA form. Taking variables out of
2728 SSA form can call create_ssa_name and thus we lose.
2730 Ultimately I suspect we're going to need to change the interface
2731 into the SSA_NAME manager. */
2737 if (TREE_CODE (stmt) == COND_EXPR)
2738 val = COND_EXPR_COND (stmt);
2739 else if (TREE_CODE (stmt) == SWITCH_EXPR)
2740 val = SWITCH_COND (stmt);
2742 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
2745 /* If we simplified a statement in such a way as to be shown that it
2746 cannot trap, update the eh information and the cfg to match. */
2747 if (maybe_clean_eh_stmt (stmt))
2749 bitmap_set_bit (need_eh_cleanup, bb->index);
2750 if (dump_file && (dump_flags & TDF_DETAILS))
2751 fprintf (dump_file, " Flagged to clear EH edges.\n");
2755 if (may_have_exposed_new_symbols)
2756 VARRAY_PUSH_TREE (stmts_to_rescan, bsi_stmt (si));
2759 /* Replace the RHS of STMT with NEW_RHS. If RHS can be found in the
2760 available expression hashtable, then return the LHS from the hash
2763 If INSERT is true, then we also update the available expression
2764 hash table to account for the changes made to STMT. */
2767 update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs, bool insert)
2769 tree cached_lhs = NULL;
2771 /* Remove the old entry from the hash table. */
2774 struct expr_hash_elt element;
2776 initialize_hash_element (stmt, NULL, &element);
2777 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
2780 /* Now update the RHS of the assignment. */
2781 TREE_OPERAND (stmt, 1) = new_rhs;
2783 /* Now lookup the updated statement in the hash table. */
2784 cached_lhs = lookup_avail_expr (stmt, insert);
2786 /* We have now called lookup_avail_expr twice with two different
2787 versions of this same statement, once in optimize_stmt, once here.
2789 We know the call in optimize_stmt did not find an existing entry
2790 in the hash table, so a new entry was created. At the same time
2791 this statement was pushed onto the BLOCK_AVAIL_EXPRS varray.
2793 If this call failed to find an existing entry on the hash table,
2794 then the new version of this statement was entered into the
2795 hash table. And this statement was pushed onto BLOCK_AVAIL_EXPR
2796 for the second time. So there are two copies on BLOCK_AVAIL_EXPRs
2798 If this call succeeded, we still have one copy of this statement
2799 on the BLOCK_AVAIL_EXPRs varray.
2801 For both cases, we need to pop the most recent entry off the
2802 BLOCK_AVAIL_EXPRs varray. For the case where we never found this
2803 statement in the hash tables, that will leave precisely one
2804 copy of this statement on BLOCK_AVAIL_EXPRs. For the case where
2805 we found a copy of this statement in the second hash table lookup
2806 we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs. */
2808 VARRAY_POP (avail_exprs_stack);
2810 /* And make sure we record the fact that we modified this
2817 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. If
2818 found, return its LHS. Otherwise insert STMT in the table and return
2821 Also, when an expression is first inserted in the AVAIL_EXPRS table, it
2822 is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
2823 can be removed when we finish processing this block and its children.
2825 NOTE: This function assumes that STMT is a MODIFY_EXPR node that
2826 contains no CALL_EXPR on its RHS and makes no volatile nor
2827 aliased references. */
2830 lookup_avail_expr (tree stmt, bool insert)
2835 struct expr_hash_elt *element = xcalloc (sizeof (struct expr_hash_elt), 1);
2837 lhs = TREE_CODE (stmt) == MODIFY_EXPR ? TREE_OPERAND (stmt, 0) : NULL;
2839 initialize_hash_element (stmt, lhs, element);
2841 /* Don't bother remembering constant assignments and copy operations.
2842 Constants and copy operations are handled by the constant/copy propagator
2843 in optimize_stmt. */
2844 if (TREE_CODE (element->rhs) == SSA_NAME
2845 || is_gimple_min_invariant (element->rhs))
2851 /* If this is an equality test against zero, see if we have recorded a
2852 nonzero value for the variable in question. */
2853 if ((TREE_CODE (element->rhs) == EQ_EXPR
2854 || TREE_CODE (element->rhs) == NE_EXPR)
2855 && TREE_CODE (TREE_OPERAND (element->rhs, 0)) == SSA_NAME
2856 && integer_zerop (TREE_OPERAND (element->rhs, 1)))
2858 int indx = SSA_NAME_VERSION (TREE_OPERAND (element->rhs, 0));
2860 if (bitmap_bit_p (nonzero_vars, indx))
2862 tree t = element->rhs;
2865 if (TREE_CODE (t) == EQ_EXPR)
2866 return boolean_false_node;
2868 return boolean_true_node;
2872 /* Finally try to find the expression in the main expression hash table. */
2873 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
2874 (insert ? INSERT : NO_INSERT));
2883 *slot = (void *) element;
2884 VARRAY_PUSH_TREE (avail_exprs_stack, stmt ? stmt : element->rhs);
2888 /* Extract the LHS of the assignment so that it can be used as the current
2889 definition of another variable. */
2890 lhs = ((struct expr_hash_elt *)*slot)->lhs;
2892 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2893 use the value from the const_and_copies table. */
2894 if (TREE_CODE (lhs) == SSA_NAME)
2896 temp = get_value_for (lhs, const_and_copies);
2905 /* Given a condition COND, record into HI_P, LO_P and INVERTED_P the
2906 range of values that result in the conditional having a true value.
2908 Return true if we are successful in extracting a range from COND and
2909 false if we are unsuccessful. */
2912 extract_range_from_cond (tree cond, tree *hi_p, tree *lo_p, int *inverted_p)
2914 tree op1 = TREE_OPERAND (cond, 1);
2915 tree high, low, type;
2918 /* Experiments have shown that it's rarely, if ever useful to
2919 record ranges for enumerations. Presumably this is due to
2920 the fact that they're rarely used directly. They are typically
2921 cast into an integer type and used that way. */
2922 if (TREE_CODE (TREE_TYPE (op1)) != INTEGER_TYPE)
2925 type = TREE_TYPE (op1);
2927 switch (TREE_CODE (cond))
2941 high = TYPE_MAX_VALUE (type);
2946 low = int_const_binop (PLUS_EXPR, op1, integer_one_node, 1);
2947 high = TYPE_MAX_VALUE (type);
2953 low = TYPE_MIN_VALUE (type);
2958 high = int_const_binop (MINUS_EXPR, op1, integer_one_node, 1);
2959 low = TYPE_MIN_VALUE (type);
2969 *inverted_p = inverted;
2973 /* Record a range created by COND for basic block BB. */
2976 record_range (tree cond, basic_block bb)
2978 /* We explicitly ignore NE_EXPRs. They rarely allow for meaningful
2979 range optimizations and significantly complicate the implementation. */
2980 if (COMPARISON_CLASS_P (cond)
2981 && TREE_CODE (cond) != NE_EXPR
2982 && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond, 1))) == INTEGER_TYPE)
2984 struct vrp_element *element = ggc_alloc (sizeof (struct vrp_element));
2985 int ssa_version = SSA_NAME_VERSION (TREE_OPERAND (cond, 0));
2987 varray_type *vrp_records_p
2988 = (varray_type *)&VARRAY_GENERIC_PTR (vrp_data, ssa_version);
2990 element->low = NULL;
2991 element->high = NULL;
2992 element->cond = cond;
2995 if (*vrp_records_p == NULL)
2997 VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records");
2998 VARRAY_GENERIC_PTR (vrp_data, ssa_version) = *vrp_records_p;
3001 VARRAY_PUSH_GENERIC_PTR (*vrp_records_p, element);
3002 VARRAY_PUSH_TREE (vrp_variables_stack, TREE_OPERAND (cond, 0));
3006 /* Given a conditional statement IF_STMT, return the assignment 'X = Y'
3007 known to be true depending on which arm of IF_STMT is taken.
3009 Not all conditional statements will result in a useful assignment.
3010 Return NULL_TREE in that case.
3012 Also enter into the available expression table statements of
3019 This allows us to lookup the condition in a dominated block and
3020 get back a constant indicating if the condition is true. */
3022 static struct eq_expr_value
3023 get_eq_expr_value (tree if_stmt,
3028 struct eq_expr_value retval;
3030 cond = COND_EXPR_COND (if_stmt);
3034 /* If the conditional is a single variable 'X', return 'X = 1' for
3035 the true arm and 'X = 0' on the false arm. */
3036 if (TREE_CODE (cond) == SSA_NAME)
3039 retval.src = constant_boolean_node (true_arm, TREE_TYPE (cond));
3043 /* If we have a comparison expression, then record its result into
3044 the available expression table. */
3045 if (COMPARISON_CLASS_P (cond))
3047 tree op0 = TREE_OPERAND (cond, 0);
3048 tree op1 = TREE_OPERAND (cond, 1);
3050 /* Special case comparing booleans against a constant as we know
3051 the value of OP0 on both arms of the branch. i.e., we can record
3052 an equivalence for OP0 rather than COND. */
3053 if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
3054 && TREE_CODE (op0) == SSA_NAME
3055 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
3056 && is_gimple_min_invariant (op1))
3058 if ((TREE_CODE (cond) == EQ_EXPR && true_arm)
3059 || (TREE_CODE (cond) == NE_EXPR && ! true_arm))
3065 if (integer_zerop (op1))
3066 retval.src = boolean_true_node;
3068 retval.src = boolean_false_node;
3074 if (TREE_CODE (op0) == SSA_NAME
3075 && (is_gimple_min_invariant (op1) || TREE_CODE (op1) == SSA_NAME))
3077 tree inverted = invert_truthvalue (cond);
3079 /* When we find an available expression in the hash table, we replace
3080 the expression with the LHS of the statement in the hash table.
3082 So, we want to build statements such as "1 = <condition>" on the
3083 true arm and "0 = <condition>" on the false arm. That way if we
3084 find the expression in the table, we will replace it with its
3085 known constant value. Also insert inversions of the result and
3086 condition into the hash table. */
3089 record_cond (cond, boolean_true_node);
3090 record_dominating_conditions (cond);
3091 record_cond (inverted, boolean_false_node);
3093 if (TREE_CONSTANT (op1))
3094 record_range (cond, bb);
3096 /* If the conditional is of the form 'X == Y', return 'X = Y'
3097 for the true arm. */
3098 if (TREE_CODE (cond) == EQ_EXPR)
3108 record_cond (inverted, boolean_true_node);
3109 record_dominating_conditions (inverted);
3110 record_cond (cond, boolean_false_node);
3112 if (TREE_CONSTANT (op1))
3113 record_range (inverted, bb);
3115 /* If the conditional is of the form 'X != Y', return 'X = Y'
3116 for the false arm. */
3117 if (TREE_CODE (cond) == NE_EXPR)
3130 /* Hashing and equality functions for AVAIL_EXPRS. The table stores
3131 MODIFY_EXPR statements. We compute a value number for expressions using
3132 the code of the expression and the SSA numbers of its operands. */
3135 avail_expr_hash (const void *p)
3137 stmt_ann_t ann = ((struct expr_hash_elt *)p)->ann;
3138 tree rhs = ((struct expr_hash_elt *)p)->rhs;
3143 /* iterative_hash_expr knows how to deal with any expression and
3144 deals with commutative operators as well, so just use it instead
3145 of duplicating such complexities here. */
3146 val = iterative_hash_expr (rhs, val);
3148 /* If the hash table entry is not associated with a statement, then we
3149 can just hash the expression and not worry about virtual operands
3154 /* Add the SSA version numbers of every vuse operand. This is important
3155 because compound variables like arrays are not renamed in the
3156 operands. Rather, the rename is done on the virtual variable
3157 representing all the elements of the array. */
3158 vuses = VUSE_OPS (ann);
3159 for (i = 0; i < NUM_VUSES (vuses); i++)
3160 val = iterative_hash_expr (VUSE_OP (vuses, i), val);
3166 real_avail_expr_hash (const void *p)
3168 return ((const struct expr_hash_elt *)p)->hash;
3172 avail_expr_eq (const void *p1, const void *p2)
3174 stmt_ann_t ann1 = ((struct expr_hash_elt *)p1)->ann;
3175 tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;
3176 stmt_ann_t ann2 = ((struct expr_hash_elt *)p2)->ann;
3177 tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
3179 /* If they are the same physical expression, return true. */
3180 if (rhs1 == rhs2 && ann1 == ann2)
3183 /* If their codes are not equal, then quit now. */
3184 if (TREE_CODE (rhs1) != TREE_CODE (rhs2))
3187 /* In case of a collision, both RHS have to be identical and have the
3188 same VUSE operands. */
3189 if ((TREE_TYPE (rhs1) == TREE_TYPE (rhs2)
3190 || lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2)))
3191 && operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
3193 vuse_optype ops1 = NULL;
3194 vuse_optype ops2 = NULL;
3195 size_t num_ops1 = 0;
3196 size_t num_ops2 = 0;
3201 ops1 = VUSE_OPS (ann1);
3202 num_ops1 = NUM_VUSES (ops1);
3207 ops2 = VUSE_OPS (ann2);
3208 num_ops2 = NUM_VUSES (ops2);
3211 /* If the number of virtual uses is different, then we consider
3213 if (num_ops1 != num_ops2)
3216 for (i = 0; i < num_ops1; i++)
3217 if (VUSE_OP (ops1, i) != VUSE_OP (ops2, i))
3220 gcc_assert (((struct expr_hash_elt *)p1)->hash
3221 == ((struct expr_hash_elt *)p2)->hash);
3228 /* Given STMT and a pointer to the block local definitions BLOCK_DEFS_P,
3229 register register all objects set by this statement into BLOCK_DEFS_P
3233 register_definitions_for_stmt (tree stmt)
3238 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
3241 /* FIXME: We shouldn't be registering new defs if the variable
3242 doesn't need to be renamed. */
3243 register_new_def (def, &block_defs_stack);