1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
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"
47 /* This file implements optimizations on the dominator tree. */
49 /* Representation of a "naked" right-hand-side expression, to be used
50 in recording available expressions in the expression hash table. */
65 struct { tree rhs; } single;
66 struct { enum tree_code op; tree opnd; } unary;
67 struct { enum tree_code op; tree opnd0; tree opnd1; } binary;
68 struct { tree fn; bool pure; size_t nargs; tree *args; } call;
72 /* Structure for recording known values of a conditional expression
73 at the exits from its block. */
75 struct cond_equivalence
77 struct hashable_expr cond;
81 /* Structure for recording edge equivalences as well as any pending
82 edge redirections during the dominator optimizer.
84 Computing and storing the edge equivalences instead of creating
85 them on-demand can save significant amounts of time, particularly
86 for pathological cases involving switch statements.
88 These structures live for a single iteration of the dominator
89 optimizer in the edge's AUX field. At the end of an iteration we
90 free each of these structures and update the AUX field to point
91 to any requested redirection target (the code for updating the
92 CFG and SSA graph for edge redirection expects redirection edge
93 targets to be in the AUX field for each edge. */
97 /* If this edge creates a simple equivalence, the LHS and RHS of
98 the equivalence will be stored here. */
102 /* Traversing an edge may also indicate one or more particular conditions
103 are true or false. The number of recorded conditions can vary, but
104 can be determined by the condition's code. So we have an array
105 and its maximum index rather than use a varray. */
106 struct cond_equivalence *cond_equivalences;
107 unsigned int max_cond_equivalences;
110 /* Hash table with expressions made available during the renaming process.
111 When an assignment of the form X_i = EXPR is found, the statement is
112 stored in this table. If the same expression EXPR is later found on the
113 RHS of another statement, it is replaced with X_i (thus performing
114 global redundancy elimination). Similarly as we pass through conditionals
115 we record the conditional itself as having either a true or false value
117 static htab_t avail_exprs;
119 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
120 expressions it enters into the hash table along with a marker entry
121 (null). When we finish processing the block, we pop off entries and
122 remove the expressions from the global hash table until we hit the
124 typedef struct expr_hash_elt * expr_hash_elt_t;
125 DEF_VEC_P(expr_hash_elt_t);
126 DEF_VEC_ALLOC_P(expr_hash_elt_t,heap);
128 static VEC(expr_hash_elt_t,heap) *avail_exprs_stack;
130 /* Stack of statements we need to rescan during finalization for newly
133 Statement rescanning must occur after the current block's available
134 expressions are removed from AVAIL_EXPRS. Else we may change the
135 hash code for an expression and be unable to find/remove it from
137 typedef gimple *gimple_p;
139 DEF_VEC_ALLOC_P(gimple_p,heap);
141 static VEC(gimple_p,heap) *stmts_to_rescan;
143 /* Structure for entries in the expression hash table. */
147 /* The value (lhs) of this expression. */
150 /* The expression (rhs) we want to record. */
151 struct hashable_expr expr;
153 /* The stmt pointer if this element corresponds to a statement. */
156 /* The hash value for RHS. */
159 /* A unique stamp, typically the address of the hash
160 element itself, used in removing entries from the table. */
161 struct expr_hash_elt *stamp;
164 /* Stack of dest,src pairs that need to be restored during finalization.
166 A NULL entry is used to mark the end of pairs which need to be
167 restored during finalization of this block. */
168 static VEC(tree,heap) *const_and_copies_stack;
170 /* Track whether or not we have changed the control flow graph. */
171 static bool cfg_altered;
173 /* Bitmap of blocks that have had EH statements cleaned. We should
174 remove their dead edges eventually. */
175 static bitmap need_eh_cleanup;
177 /* Statistics for dominator optimizations. */
181 long num_exprs_considered;
187 static struct opt_stats_d opt_stats;
189 /* Local functions. */
190 static void optimize_stmt (struct dom_walk_data *,
192 gimple_stmt_iterator);
193 static tree lookup_avail_expr (gimple, bool);
194 static hashval_t avail_expr_hash (const void *);
195 static hashval_t real_avail_expr_hash (const void *);
196 static int avail_expr_eq (const void *, const void *);
197 static void htab_statistics (FILE *, htab_t);
198 static void record_cond (struct cond_equivalence *);
199 static void record_const_or_copy (tree, tree);
200 static void record_equality (tree, tree);
201 static void record_equivalences_from_phis (basic_block);
202 static void record_equivalences_from_incoming_edge (basic_block);
203 static bool eliminate_redundant_computations (gimple_stmt_iterator *);
204 static void record_equivalences_from_stmt (gimple, int);
205 static void dom_thread_across_edge (struct dom_walk_data *, edge);
206 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
207 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
208 static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
209 static void remove_local_expressions_from_table (void);
210 static void restore_vars_to_original_value (void);
211 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
214 /* Given a statement STMT, initialize the hash table element pointed to
218 initialize_hash_element (gimple stmt, tree lhs,
219 struct expr_hash_elt *element)
221 enum gimple_code code = gimple_code (stmt);
222 struct hashable_expr *expr = &element->expr;
224 if (code == GIMPLE_ASSIGN)
226 enum tree_code subcode = gimple_assign_rhs_code (stmt);
228 switch (get_gimple_rhs_class (subcode))
230 case GIMPLE_SINGLE_RHS:
231 expr->kind = EXPR_SINGLE;
232 expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt));
233 expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
235 case GIMPLE_UNARY_RHS:
236 expr->kind = EXPR_UNARY;
237 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
238 expr->ops.unary.op = subcode;
239 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
241 case GIMPLE_BINARY_RHS:
242 expr->kind = EXPR_BINARY;
243 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
244 expr->ops.binary.op = subcode;
245 expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
246 expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
252 else if (code == GIMPLE_COND)
254 expr->type = boolean_type_node;
255 expr->kind = EXPR_BINARY;
256 expr->ops.binary.op = gimple_cond_code (stmt);
257 expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
258 expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
260 else if (code == GIMPLE_CALL)
262 size_t nargs = gimple_call_num_args (stmt);
265 gcc_assert (gimple_call_lhs (stmt));
267 expr->type = TREE_TYPE (gimple_call_lhs (stmt));
268 expr->kind = EXPR_CALL;
269 expr->ops.call.fn = gimple_call_fn (stmt);
271 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
272 expr->ops.call.pure = true;
274 expr->ops.call.pure = false;
276 expr->ops.call.nargs = nargs;
277 expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree));
278 for (i = 0; i < nargs; i++)
279 expr->ops.call.args[i] = gimple_call_arg (stmt, i);
281 else if (code == GIMPLE_SWITCH)
283 expr->type = TREE_TYPE (gimple_switch_index (stmt));
284 expr->kind = EXPR_SINGLE;
285 expr->ops.single.rhs = gimple_switch_index (stmt);
287 else if (code == GIMPLE_GOTO)
289 expr->type = TREE_TYPE (gimple_goto_dest (stmt));
290 expr->kind = EXPR_SINGLE;
291 expr->ops.single.rhs = gimple_goto_dest (stmt);
297 element->stmt = stmt;
298 element->hash = avail_expr_hash (element);
299 element->stamp = element;
302 /* Given a conditional expression COND as a tree, initialize
303 a hashable_expr expression EXPR. The conditional must be a
304 comparison or logical negation. A constant or a variable is
308 initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
310 expr->type = boolean_type_node;
312 if (COMPARISON_CLASS_P (cond))
314 expr->kind = EXPR_BINARY;
315 expr->ops.binary.op = TREE_CODE (cond);
316 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
317 expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
319 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
321 expr->kind = EXPR_UNARY;
322 expr->ops.unary.op = TRUTH_NOT_EXPR;
323 expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
329 /* Given a hashable_expr expression EXPR and an LHS,
330 initialize the hash table element pointed to by ELEMENT. */
333 initialize_hash_element_from_expr (struct hashable_expr *expr,
335 struct expr_hash_elt *element)
337 element->expr = *expr;
339 element->stmt = NULL;
340 element->hash = avail_expr_hash (element);
341 element->stamp = element;
344 /* Compare two hashable_expr structures for equivalence.
345 They are considered equivalent when the the expressions
346 they denote must necessarily be equal. The logic is intended
347 to follow that of operand_equal_p in fold-const.c */
350 hashable_expr_equal_p (const struct hashable_expr *expr0,
351 const struct hashable_expr *expr1)
353 tree type0 = expr0->type;
354 tree type1 = expr1->type;
356 /* If either type is NULL, there is nothing to check. */
357 if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
360 /* If both types don't have the same signedness, precision, and mode,
361 then we can't consider them equal. */
363 && (TREE_CODE (type0) == ERROR_MARK
364 || TREE_CODE (type1) == ERROR_MARK
365 || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
366 || TYPE_PRECISION (type0) != TYPE_PRECISION (type1)
367 || TYPE_MODE (type0) != TYPE_MODE (type1)))
370 if (expr0->kind != expr1->kind)
376 return operand_equal_p (expr0->ops.single.rhs,
377 expr1->ops.single.rhs, 0);
380 if (expr0->ops.unary.op != expr1->ops.unary.op)
383 if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
384 || expr0->ops.unary.op == NON_LVALUE_EXPR)
385 && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
388 return operand_equal_p (expr0->ops.unary.opnd,
389 expr1->ops.unary.opnd, 0);
393 if (expr0->ops.binary.op != expr1->ops.binary.op)
396 if (operand_equal_p (expr0->ops.binary.opnd0,
397 expr1->ops.binary.opnd0, 0)
398 && operand_equal_p (expr0->ops.binary.opnd1,
399 expr1->ops.binary.opnd1, 0))
402 /* For commutative ops, allow the other order. */
403 return (commutative_tree_code (expr0->ops.binary.op)
404 && operand_equal_p (expr0->ops.binary.opnd0,
405 expr1->ops.binary.opnd1, 0)
406 && operand_equal_p (expr0->ops.binary.opnd1,
407 expr1->ops.binary.opnd0, 0));
414 /* If the calls are to different functions, then they
415 clearly cannot be equal. */
416 if (! operand_equal_p (expr0->ops.call.fn,
417 expr1->ops.call.fn, 0))
420 if (! expr0->ops.call.pure)
423 if (expr0->ops.call.nargs != expr1->ops.call.nargs)
426 for (i = 0; i < expr0->ops.call.nargs; i++)
427 if (! operand_equal_p (expr0->ops.call.args[i],
428 expr1->ops.call.args[i], 0))
439 /* Compute a hash value for a hashable_expr value EXPR and a
440 previously accumulated hash value VAL. If two hashable_expr
441 values compare equal with hashable_expr_equal_p, they must
442 hash to the same value, given an identical value of VAL.
443 The logic is intended to follow iterative_hash_expr in tree.c. */
446 iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val)
451 val = iterative_hash_expr (expr->ops.single.rhs, val);
455 val = iterative_hash_object (expr->ops.unary.op, val);
457 /* Make sure to include signedness in the hash computation.
458 Don't hash the type, that can lead to having nodes which
459 compare equal according to operand_equal_p, but which
460 have different hash codes. */
461 if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
462 || expr->ops.unary.op == NON_LVALUE_EXPR)
463 val += TYPE_UNSIGNED (expr->type);
465 val = iterative_hash_expr (expr->ops.unary.opnd, val);
469 val = iterative_hash_object (expr->ops.binary.op, val);
470 if (commutative_tree_code (expr->ops.binary.op))
471 val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
472 expr->ops.binary.opnd1, val);
475 val = iterative_hash_expr (expr->ops.binary.opnd0, val);
476 val = iterative_hash_expr (expr->ops.binary.opnd1, val);
483 enum tree_code code = CALL_EXPR;
485 val = iterative_hash_object (code, val);
486 val = iterative_hash_expr (expr->ops.call.fn, val);
487 for (i = 0; i < expr->ops.call.nargs; i++)
488 val = iterative_hash_expr (expr->ops.call.args[i], val);
499 /* Print a diagnostic dump of an expression hash table entry. */
502 print_expr_hash_elt (FILE * stream, const struct expr_hash_elt *element)
505 fprintf (stream, "STMT ");
507 fprintf (stream, "COND ");
511 print_generic_expr (stream, element->lhs, 0);
512 fprintf (stream, " = ");
515 switch (element->expr.kind)
518 print_generic_expr (stream, element->expr.ops.single.rhs, 0);
522 fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]);
523 print_generic_expr (stream, element->expr.ops.unary.opnd, 0);
527 print_generic_expr (stream, element->expr.ops.binary.opnd0, 0);
528 fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]);
529 print_generic_expr (stream, element->expr.ops.binary.opnd1, 0);
535 size_t nargs = element->expr.ops.call.nargs;
537 print_generic_expr (stream, element->expr.ops.call.fn, 0);
538 fprintf (stream, " (");
539 for (i = 0; i < nargs; i++)
541 print_generic_expr (stream, element->expr.ops.call.args[i], 0);
543 fprintf (stream, ", ");
545 fprintf (stream, ")");
549 fprintf (stream, "\n");
553 fprintf (stream, " ");
554 print_gimple_stmt (stream, element->stmt, 0, 0);
558 /* Delete an expr_hash_elt and reclaim its storage. */
561 free_expr_hash_elt (void *elt)
563 struct expr_hash_elt *element = ((struct expr_hash_elt *)elt);
565 if (element->expr.kind == EXPR_CALL)
566 free (element->expr.ops.call.args);
571 /* Allocate an EDGE_INFO for edge E and attach it to E.
572 Return the new EDGE_INFO structure. */
574 static struct edge_info *
575 allocate_edge_info (edge e)
577 struct edge_info *edge_info;
579 edge_info = XCNEW (struct edge_info);
585 /* Free all EDGE_INFO structures associated with edges in the CFG.
586 If a particular edge can be threaded, copy the redirection
587 target from the EDGE_INFO structure into the edge's AUX field
588 as required by code to update the CFG and SSA graph for
592 free_all_edge_infos (void)
600 FOR_EACH_EDGE (e, ei, bb->preds)
602 struct edge_info *edge_info = (struct edge_info *) e->aux;
606 if (edge_info->cond_equivalences)
607 free (edge_info->cond_equivalences);
615 /* Jump threading, redundancy elimination and const/copy propagation.
617 This pass may expose new symbols that need to be renamed into SSA. For
618 every new symbol exposed, its corresponding bit will be set in
622 tree_ssa_dominator_optimize (void)
624 struct dom_walk_data walk_data;
627 memset (&opt_stats, 0, sizeof (opt_stats));
629 /* Create our hash tables. */
630 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt);
631 avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20);
632 const_and_copies_stack = VEC_alloc (tree, heap, 20);
633 stmts_to_rescan = VEC_alloc (gimple_p, heap, 20);
634 need_eh_cleanup = BITMAP_ALLOC (NULL);
636 /* Setup callbacks for the generic dominator tree walker. */
637 walk_data.walk_stmts_backward = false;
638 walk_data.dom_direction = CDI_DOMINATORS;
639 walk_data.initialize_block_local_data = NULL;
640 walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
641 walk_data.before_dom_children_walk_stmts = optimize_stmt;
642 walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
643 walk_data.after_dom_children_before_stmts = NULL;
644 walk_data.after_dom_children_walk_stmts = NULL;
645 walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
646 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
647 When we attach more stuff we'll need to fill this out with a real
649 walk_data.global_data = NULL;
650 walk_data.block_local_data_size = 0;
651 walk_data.interesting_blocks = NULL;
653 /* Now initialize the dominator walker. */
654 init_walk_dominator_tree (&walk_data);
656 calculate_dominance_info (CDI_DOMINATORS);
659 /* We need to know loop structures in order to avoid destroying them
660 in jump threading. Note that we still can e.g. thread through loop
661 headers to an exit edge, or through loop header to the loop body, assuming
662 that we update the loop info. */
663 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
665 /* We need accurate information regarding back edges in the CFG
666 for jump threading; this may include back edges that are not part of
668 mark_dfs_back_edges ();
670 /* Recursively walk the dominator tree optimizing statements. */
671 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
674 gimple_stmt_iterator gsi;
677 {for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
678 update_stmt_if_modified (gsi_stmt (gsi));
682 /* If we exposed any new variables, go ahead and put them into
683 SSA form now, before we handle jump threading. This simplifies
684 interactions between rewriting of _DECL nodes into SSA form
685 and rewriting SSA_NAME nodes into SSA form after block
686 duplication and CFG manipulation. */
687 update_ssa (TODO_update_ssa);
689 free_all_edge_infos ();
691 /* Thread jumps, creating duplicate blocks as needed. */
692 cfg_altered |= thread_through_all_blocks (first_pass_instance);
695 free_dominance_info (CDI_DOMINATORS);
697 /* Removal of statements may make some EH edges dead. Purge
698 such edges from the CFG as needed. */
699 if (!bitmap_empty_p (need_eh_cleanup))
704 /* Jump threading may have created forwarder blocks from blocks
705 needing EH cleanup; the new successor of these blocks, which
706 has inherited from the original block, needs the cleanup. */
707 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
709 basic_block bb = BASIC_BLOCK (i);
710 if (single_succ_p (bb) == 1
711 && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
713 bitmap_clear_bit (need_eh_cleanup, i);
714 bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index);
718 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
719 bitmap_zero (need_eh_cleanup);
722 /* Finally, remove everything except invariants in SSA_NAME_VALUE.
724 Long term we will be able to let everything in SSA_NAME_VALUE
725 persist. However, for now, we know this is the safe thing to do. */
726 for (i = 0; i < num_ssa_names; i++)
728 tree name = ssa_name (i);
734 value = SSA_NAME_VALUE (name);
735 if (value && !is_gimple_min_invariant (value))
736 SSA_NAME_VALUE (name) = NULL;
739 statistics_counter_event (cfun, "Redundant expressions eliminated",
741 statistics_counter_event (cfun, "Constants propagated",
742 opt_stats.num_const_prop);
743 statistics_counter_event (cfun, "Copies propagated",
744 opt_stats.num_copy_prop);
746 /* Debugging dumps. */
747 if (dump_file && (dump_flags & TDF_STATS))
748 dump_dominator_optimization_stats (dump_file);
750 loop_optimizer_finalize ();
752 /* Delete our main hashtable. */
753 htab_delete (avail_exprs);
755 /* And finalize the dominator walker. */
756 fini_walk_dominator_tree (&walk_data);
758 /* Free asserted bitmaps and stacks. */
759 BITMAP_FREE (need_eh_cleanup);
761 VEC_free (expr_hash_elt_t, heap, avail_exprs_stack);
762 VEC_free (tree, heap, const_and_copies_stack);
763 VEC_free (gimple_p, heap, stmts_to_rescan);
769 gate_dominator (void)
771 return flag_tree_dom != 0;
774 struct gimple_opt_pass pass_dominator =
779 gate_dominator, /* gate */
780 tree_ssa_dominator_optimize, /* execute */
783 0, /* static_pass_number */
784 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
785 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
786 0, /* properties_provided */
787 0, /* properties_destroyed */
788 0, /* todo_flags_start */
792 | TODO_verify_ssa /* todo_flags_finish */
797 /* Given a conditional statement CONDSTMT, convert the
798 condition to a canonical form. */
801 canonicalize_comparison (gimple condstmt)
807 gcc_assert (gimple_code (condstmt) == GIMPLE_COND);
809 op0 = gimple_cond_lhs (condstmt);
810 op1 = gimple_cond_rhs (condstmt);
812 code = gimple_cond_code (condstmt);
814 /* If it would be profitable to swap the operands, then do so to
815 canonicalize the statement, enabling better optimization.
817 By placing canonicalization of such expressions here we
818 transparently keep statements in canonical form, even
819 when the statement is modified. */
820 if (tree_swap_operands_p (op0, op1, false))
822 /* For relationals we need to swap the operands
823 and change the code. */
829 code = swap_tree_comparison (code);
831 gimple_cond_set_code (condstmt, code);
832 gimple_cond_set_lhs (condstmt, op1);
833 gimple_cond_set_rhs (condstmt, op0);
835 update_stmt (condstmt);
840 /* Initialize local stacks for this optimizer and record equivalences
841 upon entry to BB. Equivalences can come from the edge traversed to
842 reach BB or they may come from PHI nodes at the start of BB. */
845 dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
848 if (dump_file && (dump_flags & TDF_DETAILS))
849 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
851 /* Push a marker on the stacks of local information so that we know how
852 far to unwind when we finalize this block. */
853 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
854 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
856 record_equivalences_from_incoming_edge (bb);
858 /* PHI nodes can create equivalences too. */
859 record_equivalences_from_phis (bb);
862 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
863 LIMIT entries left in LOCALs. */
866 remove_local_expressions_from_table (void)
868 /* Remove all the expressions made available in this block. */
869 while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0)
871 struct expr_hash_elt element;
872 expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack);
879 /* This must precede the actual removal from the hash table,
880 as ELEMENT and the table entry may share a call argument
881 vector which will be freed during removal. */
882 if (dump_file && (dump_flags & TDF_DETAILS))
884 fprintf (dump_file, "<<<< ");
885 print_expr_hash_elt (dump_file, &element);
888 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
892 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
893 CONST_AND_COPIES to its original state, stopping when we hit a
897 restore_vars_to_original_value (void)
899 while (VEC_length (tree, const_and_copies_stack) > 0)
901 tree prev_value, dest;
903 dest = VEC_pop (tree, const_and_copies_stack);
908 if (dump_file && (dump_flags & TDF_DETAILS))
910 fprintf (dump_file, "<<<< COPY ");
911 print_generic_expr (dump_file, dest, 0);
912 fprintf (dump_file, " = ");
913 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0);
914 fprintf (dump_file, "\n");
917 prev_value = VEC_pop (tree, const_and_copies_stack);
918 SSA_NAME_VALUE (dest) = prev_value;
922 /* A trivial wrapper so that we can present the generic jump
923 threading code with a simple API for simplifying statements. */
925 simplify_stmt_for_jump_threading (gimple stmt,
926 gimple within_stmt ATTRIBUTE_UNUSED)
928 return lookup_avail_expr (stmt, false);
931 /* Wrapper for common code to attempt to thread an edge. For example,
932 it handles lazily building the dummy condition and the bookkeeping
933 when jump threading is successful. */
936 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
938 if (! walk_data->global_data)
941 gimple_build_cond (NE_EXPR,
942 integer_zero_node, integer_zero_node,
944 walk_data->global_data = dummy_cond;
947 thread_across_edge ((gimple) walk_data->global_data, e, false,
948 &const_and_copies_stack,
949 simplify_stmt_for_jump_threading);
952 /* We have finished processing the dominator children of BB, perform
953 any finalization actions in preparation for leaving this node in
954 the dominator tree. */
957 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
961 /* If we have an outgoing edge to a block with multiple incoming and
962 outgoing edges, then we may be able to thread the edge, i.e., we
963 may be able to statically determine which of the outgoing edges
964 will be traversed when the incoming edge from BB is traversed. */
965 if (single_succ_p (bb)
966 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
967 && potentially_threadable_block (single_succ (bb)))
969 dom_thread_across_edge (walk_data, single_succ_edge (bb));
971 else if ((last = last_stmt (bb))
972 && gimple_code (last) == GIMPLE_COND
973 && EDGE_COUNT (bb->succs) == 2
974 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
975 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
977 edge true_edge, false_edge;
979 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
981 /* Only try to thread the edge if it reaches a target block with
982 more than one predecessor and more than one successor. */
983 if (potentially_threadable_block (true_edge->dest))
985 struct edge_info *edge_info;
988 /* Push a marker onto the available expression stack so that we
989 unwind any expressions related to the TRUE arm before processing
990 the false arm below. */
991 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
992 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
994 edge_info = (struct edge_info *) true_edge->aux;
996 /* If we have info associated with this edge, record it into
997 our equivalence tables. */
1000 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1001 tree lhs = edge_info->lhs;
1002 tree rhs = edge_info->rhs;
1004 /* If we have a simple NAME = VALUE equivalence, record it. */
1005 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1006 record_const_or_copy (lhs, rhs);
1008 /* If we have 0 = COND or 1 = COND equivalences, record them
1009 into our expression hash tables. */
1010 if (cond_equivalences)
1011 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1012 record_cond (&cond_equivalences[i]);
1015 dom_thread_across_edge (walk_data, true_edge);
1017 /* And restore the various tables to their state before
1018 we threaded this edge. */
1019 remove_local_expressions_from_table ();
1022 /* Similarly for the ELSE arm. */
1023 if (potentially_threadable_block (false_edge->dest))
1025 struct edge_info *edge_info;
1028 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1029 edge_info = (struct edge_info *) false_edge->aux;
1031 /* If we have info associated with this edge, record it into
1032 our equivalence tables. */
1035 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1036 tree lhs = edge_info->lhs;
1037 tree rhs = edge_info->rhs;
1039 /* If we have a simple NAME = VALUE equivalence, record it. */
1040 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1041 record_const_or_copy (lhs, rhs);
1043 /* If we have 0 = COND or 1 = COND equivalences, record them
1044 into our expression hash tables. */
1045 if (cond_equivalences)
1046 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1047 record_cond (&cond_equivalences[i]);
1050 /* Now thread the edge. */
1051 dom_thread_across_edge (walk_data, false_edge);
1053 /* No need to remove local expressions from our tables
1054 or restore vars to their original value as that will
1055 be done immediately below. */
1059 remove_local_expressions_from_table ();
1060 restore_vars_to_original_value ();
1062 /* If we queued any statements to rescan in this block, then
1063 go ahead and rescan them now. */
1064 while (VEC_length (gimple_p, stmts_to_rescan) > 0)
1066 gimple *stmt_p = VEC_last (gimple_p, stmts_to_rescan);
1067 gimple stmt = *stmt_p;
1068 basic_block stmt_bb = gimple_bb (stmt);
1073 VEC_pop (gimple_p, stmts_to_rescan);
1074 pop_stmt_changes (stmt_p);
1078 /* PHI nodes can create equivalences too.
1080 Ignoring any alternatives which are the same as the result, if
1081 all the alternatives are equal, then the PHI node creates an
1085 record_equivalences_from_phis (basic_block bb)
1087 gimple_stmt_iterator gsi;
1089 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1091 gimple phi = gsi_stmt (gsi);
1093 tree lhs = gimple_phi_result (phi);
1097 for (i = 0; i < gimple_phi_num_args (phi); i++)
1099 tree t = gimple_phi_arg_def (phi, i);
1101 /* Ignore alternatives which are the same as our LHS. Since
1102 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1103 can simply compare pointers. */
1107 /* If we have not processed an alternative yet, then set
1108 RHS to this alternative. */
1111 /* If we have processed an alternative (stored in RHS), then
1112 see if it is equal to this one. If it isn't, then stop
1114 else if (! operand_equal_for_phi_arg_p (rhs, t))
1118 /* If we had no interesting alternatives, then all the RHS alternatives
1119 must have been the same as LHS. */
1123 /* If we managed to iterate through each PHI alternative without
1124 breaking out of the loop, then we have a PHI which may create
1125 a useful equivalence. We do not need to record unwind data for
1126 this, since this is a true assignment and not an equivalence
1127 inferred from a comparison. All uses of this ssa name are dominated
1128 by this assignment, so unwinding just costs time and space. */
1129 if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs))
1130 SSA_NAME_VALUE (lhs) = rhs;
1134 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1135 return that edge. Otherwise return NULL. */
1137 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1143 FOR_EACH_EDGE (e, ei, bb->preds)
1145 /* A loop back edge can be identified by the destination of
1146 the edge dominating the source of the edge. */
1147 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1150 /* If we have already seen a non-loop edge, then we must have
1151 multiple incoming non-loop edges and thus we return NULL. */
1155 /* This is the first non-loop incoming edge we have found. Record
1163 /* Record any equivalences created by the incoming edge to BB. If BB
1164 has more than one incoming edge, then no equivalence is created. */
1167 record_equivalences_from_incoming_edge (basic_block bb)
1171 struct edge_info *edge_info;
1173 /* If our parent block ended with a control statement, then we may be
1174 able to record some equivalences based on which outgoing edge from
1175 the parent was followed. */
1176 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1178 e = single_incoming_edge_ignoring_loop_edges (bb);
1180 /* If we had a single incoming edge from our parent block, then enter
1181 any data associated with the edge into our tables. */
1182 if (e && e->src == parent)
1186 edge_info = (struct edge_info *) e->aux;
1190 tree lhs = edge_info->lhs;
1191 tree rhs = edge_info->rhs;
1192 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1195 record_equality (lhs, rhs);
1197 if (cond_equivalences)
1198 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1199 record_cond (&cond_equivalences[i]);
1204 /* Dump SSA statistics on FILE. */
1207 dump_dominator_optimization_stats (FILE *file)
1209 fprintf (file, "Total number of statements: %6ld\n\n",
1210 opt_stats.num_stmts);
1211 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1212 opt_stats.num_exprs_considered);
1214 fprintf (file, "\nHash table statistics:\n");
1216 fprintf (file, " avail_exprs: ");
1217 htab_statistics (file, avail_exprs);
1221 /* Dump SSA statistics on stderr. */
1224 debug_dominator_optimization_stats (void)
1226 dump_dominator_optimization_stats (stderr);
1230 /* Dump statistics for the hash table HTAB. */
1233 htab_statistics (FILE *file, htab_t htab)
1235 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1236 (long) htab_size (htab),
1237 (long) htab_elements (htab),
1238 htab_collisions (htab));
1242 /* Enter condition equivalence into the expression hash table.
1243 This indicates that a conditional expression has a known
1247 record_cond (struct cond_equivalence *p)
1249 struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
1252 initialize_hash_element_from_expr (&p->cond, p->value, element);
1254 slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
1255 element->hash, INSERT);
1258 *slot = (void *) element;
1260 if (dump_file && (dump_flags & TDF_DETAILS))
1262 fprintf (dump_file, "1>>> ");
1263 print_expr_hash_elt (dump_file, element);
1266 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
1272 /* Build a cond_equivalence record indicating that the comparison
1273 CODE holds between operands OP0 and OP1. */
1276 build_and_record_new_cond (enum tree_code code,
1278 struct cond_equivalence *p)
1280 struct hashable_expr *cond = &p->cond;
1282 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
1284 cond->type = boolean_type_node;
1285 cond->kind = EXPR_BINARY;
1286 cond->ops.binary.op = code;
1287 cond->ops.binary.opnd0 = op0;
1288 cond->ops.binary.opnd1 = op1;
1290 p->value = boolean_true_node;
1293 /* Record that COND is true and INVERTED is false into the edge information
1294 structure. Also record that any conditions dominated by COND are true
1297 For example, if a < b is true, then a <= b must also be true. */
1300 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
1304 if (!COMPARISON_CLASS_P (cond))
1307 op0 = TREE_OPERAND (cond, 0);
1308 op1 = TREE_OPERAND (cond, 1);
1310 switch (TREE_CODE (cond))
1314 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1316 edge_info->max_cond_equivalences = 6;
1317 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 6);
1318 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1319 &edge_info->cond_equivalences[4]);
1320 build_and_record_new_cond (LTGT_EXPR, op0, op1,
1321 &edge_info->cond_equivalences[5]);
1325 edge_info->max_cond_equivalences = 4;
1326 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1329 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
1330 ? LE_EXPR : GE_EXPR),
1331 op0, op1, &edge_info->cond_equivalences[2]);
1332 build_and_record_new_cond (NE_EXPR, op0, op1,
1333 &edge_info->cond_equivalences[3]);
1338 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1340 edge_info->max_cond_equivalences = 3;
1341 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 3);
1342 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1343 &edge_info->cond_equivalences[2]);
1347 edge_info->max_cond_equivalences = 2;
1348 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1353 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1355 edge_info->max_cond_equivalences = 5;
1356 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 5);
1357 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1358 &edge_info->cond_equivalences[4]);
1362 edge_info->max_cond_equivalences = 4;
1363 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1365 build_and_record_new_cond (LE_EXPR, op0, op1,
1366 &edge_info->cond_equivalences[2]);
1367 build_and_record_new_cond (GE_EXPR, op0, op1,
1368 &edge_info->cond_equivalences[3]);
1371 case UNORDERED_EXPR:
1372 edge_info->max_cond_equivalences = 8;
1373 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 8);
1374 build_and_record_new_cond (NE_EXPR, op0, op1,
1375 &edge_info->cond_equivalences[2]);
1376 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1377 &edge_info->cond_equivalences[3]);
1378 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1379 &edge_info->cond_equivalences[4]);
1380 build_and_record_new_cond (UNEQ_EXPR, op0, op1,
1381 &edge_info->cond_equivalences[5]);
1382 build_and_record_new_cond (UNLT_EXPR, op0, op1,
1383 &edge_info->cond_equivalences[6]);
1384 build_and_record_new_cond (UNGT_EXPR, op0, op1,
1385 &edge_info->cond_equivalences[7]);
1390 edge_info->max_cond_equivalences = 4;
1391 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1392 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1393 ? UNLE_EXPR : UNGE_EXPR),
1394 op0, op1, &edge_info->cond_equivalences[2]);
1395 build_and_record_new_cond (NE_EXPR, op0, op1,
1396 &edge_info->cond_equivalences[3]);
1400 edge_info->max_cond_equivalences = 4;
1401 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1402 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1403 &edge_info->cond_equivalences[2]);
1404 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1405 &edge_info->cond_equivalences[3]);
1409 edge_info->max_cond_equivalences = 4;
1410 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1411 build_and_record_new_cond (NE_EXPR, op0, op1,
1412 &edge_info->cond_equivalences[2]);
1413 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1414 &edge_info->cond_equivalences[3]);
1418 edge_info->max_cond_equivalences = 2;
1419 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1423 /* Now store the original true and false conditions into the first
1425 initialize_expr_from_cond (cond, &edge_info->cond_equivalences[0].cond);
1426 edge_info->cond_equivalences[0].value = boolean_true_node;
1428 /* It is possible for INVERTED to be the negation of a comparison,
1429 and not a valid RHS or GIMPLE_COND condition. This happens because
1430 invert_truthvalue may return such an expression when asked to invert
1431 a floating-point comparison. These comparisons are not assumed to
1432 obey the trichotomy law. */
1433 initialize_expr_from_cond (inverted, &edge_info->cond_equivalences[1].cond);
1434 edge_info->cond_equivalences[1].value = boolean_false_node;
1437 /* A helper function for record_const_or_copy and record_equality.
1438 Do the work of recording the value and undo info. */
1441 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1443 SSA_NAME_VALUE (x) = y;
1445 if (dump_file && (dump_flags & TDF_DETAILS))
1447 fprintf (dump_file, "0>>> COPY ");
1448 print_generic_expr (dump_file, x, 0);
1449 fprintf (dump_file, " = ");
1450 print_generic_expr (dump_file, y, 0);
1451 fprintf (dump_file, "\n");
1454 VEC_reserve (tree, heap, const_and_copies_stack, 2);
1455 VEC_quick_push (tree, const_and_copies_stack, prev_x);
1456 VEC_quick_push (tree, const_and_copies_stack, x);
1459 /* Return the loop depth of the basic block of the defining statement of X.
1460 This number should not be treated as absolutely correct because the loop
1461 information may not be completely up-to-date when dom runs. However, it
1462 will be relatively correct, and as more passes are taught to keep loop info
1463 up to date, the result will become more and more accurate. */
1466 loop_depth_of_name (tree x)
1471 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1472 if (TREE_CODE (x) != SSA_NAME)
1475 /* Otherwise return the loop depth of the defining statement's bb.
1476 Note that there may not actually be a bb for this statement, if the
1477 ssa_name is live on entry. */
1478 defstmt = SSA_NAME_DEF_STMT (x);
1479 defbb = gimple_bb (defstmt);
1483 return defbb->loop_depth;
1486 /* Record that X is equal to Y in const_and_copies. Record undo
1487 information in the block-local vector. */
1490 record_const_or_copy (tree x, tree y)
1492 tree prev_x = SSA_NAME_VALUE (x);
1494 gcc_assert (TREE_CODE (x) == SSA_NAME);
1496 if (TREE_CODE (y) == SSA_NAME)
1498 tree tmp = SSA_NAME_VALUE (y);
1503 record_const_or_copy_1 (x, y, prev_x);
1506 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1507 This constrains the cases in which we may treat this as assignment. */
1510 record_equality (tree x, tree y)
1512 tree prev_x = NULL, prev_y = NULL;
1514 if (TREE_CODE (x) == SSA_NAME)
1515 prev_x = SSA_NAME_VALUE (x);
1516 if (TREE_CODE (y) == SSA_NAME)
1517 prev_y = SSA_NAME_VALUE (y);
1519 /* If one of the previous values is invariant, or invariant in more loops
1520 (by depth), then use that.
1521 Otherwise it doesn't matter which value we choose, just so
1522 long as we canonicalize on one value. */
1523 if (is_gimple_min_invariant (y))
1525 else if (is_gimple_min_invariant (x)
1526 || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
1527 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1528 else if (prev_x && is_gimple_min_invariant (prev_x))
1529 x = y, y = prev_x, prev_x = prev_y;
1533 /* After the swapping, we must have one SSA_NAME. */
1534 if (TREE_CODE (x) != SSA_NAME)
1537 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1538 variable compared against zero. If we're honoring signed zeros,
1539 then we cannot record this value unless we know that the value is
1541 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1542 && (TREE_CODE (y) != REAL_CST
1543 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1546 record_const_or_copy_1 (x, y, prev_x);
1549 /* Returns true when STMT is a simple iv increment. It detects the
1550 following situation:
1552 i_1 = phi (..., i_2)
1553 i_2 = i_1 +/- ... */
1556 simple_iv_increment_p (gimple stmt)
1562 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1565 lhs = gimple_assign_lhs (stmt);
1566 if (TREE_CODE (lhs) != SSA_NAME)
1569 if (gimple_assign_rhs_code (stmt) != PLUS_EXPR
1570 && gimple_assign_rhs_code (stmt) != MINUS_EXPR)
1573 preinc = gimple_assign_rhs1 (stmt);
1575 if (TREE_CODE (preinc) != SSA_NAME)
1578 phi = SSA_NAME_DEF_STMT (preinc);
1579 if (gimple_code (phi) != GIMPLE_PHI)
1582 for (i = 0; i < gimple_phi_num_args (phi); i++)
1583 if (gimple_phi_arg_def (phi, i) == lhs)
1589 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1590 known value for that SSA_NAME (or NULL if no value is known).
1592 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1593 successors of BB. */
1596 cprop_into_successor_phis (basic_block bb)
1601 FOR_EACH_EDGE (e, ei, bb->succs)
1604 gimple_stmt_iterator gsi;
1606 /* If this is an abnormal edge, then we do not want to copy propagate
1607 into the PHI alternative associated with this edge. */
1608 if (e->flags & EDGE_ABNORMAL)
1611 gsi = gsi_start_phis (e->dest);
1612 if (gsi_end_p (gsi))
1616 for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1619 use_operand_p orig_p;
1621 gimple phi = gsi_stmt (gsi);
1623 /* The alternative may be associated with a constant, so verify
1624 it is an SSA_NAME before doing anything with it. */
1625 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1626 orig_val = get_use_from_ptr (orig_p);
1627 if (TREE_CODE (orig_val) != SSA_NAME)
1630 /* If we have *ORIG_P in our constant/copy table, then replace
1631 ORIG_P with its value in our constant/copy table. */
1632 new_val = SSA_NAME_VALUE (orig_val);
1634 && new_val != orig_val
1635 && (TREE_CODE (new_val) == SSA_NAME
1636 || is_gimple_min_invariant (new_val))
1637 && may_propagate_copy (orig_val, new_val))
1638 propagate_value (orig_p, new_val);
1643 /* We have finished optimizing BB, record any information implied by
1644 taking a specific outgoing edge from BB. */
1647 record_edge_info (basic_block bb)
1649 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1650 struct edge_info *edge_info;
1652 if (! gsi_end_p (gsi))
1654 gimple stmt = gsi_stmt (gsi);
1656 if (gimple_code (stmt) == GIMPLE_SWITCH)
1658 tree index = gimple_switch_index (stmt);
1660 if (TREE_CODE (index) == SSA_NAME)
1663 int n_labels = gimple_switch_num_labels (stmt);
1664 tree *info = XCNEWVEC (tree, last_basic_block);
1668 for (i = 0; i < n_labels; i++)
1670 tree label = gimple_switch_label (stmt, i);
1671 basic_block target_bb = label_to_block (CASE_LABEL (label));
1672 if (CASE_HIGH (label)
1673 || !CASE_LOW (label)
1674 || info[target_bb->index])
1675 info[target_bb->index] = error_mark_node;
1677 info[target_bb->index] = label;
1680 FOR_EACH_EDGE (e, ei, bb->succs)
1682 basic_block target_bb = e->dest;
1683 tree label = info[target_bb->index];
1685 if (label != NULL && label != error_mark_node)
1687 tree x = fold_convert (TREE_TYPE (index), CASE_LOW (label));
1688 edge_info = allocate_edge_info (e);
1689 edge_info->lhs = index;
1697 /* A COND_EXPR may create equivalences too. */
1698 if (gimple_code (stmt) == GIMPLE_COND)
1703 tree op0 = gimple_cond_lhs (stmt);
1704 tree op1 = gimple_cond_rhs (stmt);
1705 enum tree_code code = gimple_cond_code (stmt);
1707 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1709 /* Special case comparing booleans against a constant as we
1710 know the value of OP0 on both arms of the branch. i.e., we
1711 can record an equivalence for OP0 rather than COND. */
1712 if ((code == EQ_EXPR || code == NE_EXPR)
1713 && TREE_CODE (op0) == SSA_NAME
1714 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
1715 && is_gimple_min_invariant (op1))
1717 if (code == EQ_EXPR)
1719 edge_info = allocate_edge_info (true_edge);
1720 edge_info->lhs = op0;
1721 edge_info->rhs = (integer_zerop (op1)
1722 ? boolean_false_node
1723 : boolean_true_node);
1725 edge_info = allocate_edge_info (false_edge);
1726 edge_info->lhs = op0;
1727 edge_info->rhs = (integer_zerop (op1)
1729 : boolean_false_node);
1733 edge_info = allocate_edge_info (true_edge);
1734 edge_info->lhs = op0;
1735 edge_info->rhs = (integer_zerop (op1)
1737 : boolean_false_node);
1739 edge_info = allocate_edge_info (false_edge);
1740 edge_info->lhs = op0;
1741 edge_info->rhs = (integer_zerop (op1)
1742 ? boolean_false_node
1743 : boolean_true_node);
1746 else if (is_gimple_min_invariant (op0)
1747 && (TREE_CODE (op1) == SSA_NAME
1748 || is_gimple_min_invariant (op1)))
1750 tree cond = build2 (code, boolean_type_node, op0, op1);
1751 tree inverted = invert_truthvalue (cond);
1752 struct edge_info *edge_info;
1754 edge_info = allocate_edge_info (true_edge);
1755 record_conditions (edge_info, cond, inverted);
1757 if (code == EQ_EXPR)
1759 edge_info->lhs = op1;
1760 edge_info->rhs = op0;
1763 edge_info = allocate_edge_info (false_edge);
1764 record_conditions (edge_info, inverted, cond);
1766 if (TREE_CODE (inverted) == EQ_EXPR)
1768 edge_info->lhs = op1;
1769 edge_info->rhs = op0;
1773 else if (TREE_CODE (op0) == SSA_NAME
1774 && (is_gimple_min_invariant (op1)
1775 || TREE_CODE (op1) == SSA_NAME))
1777 tree cond = build2 (code, boolean_type_node, op0, op1);
1778 tree inverted = invert_truthvalue (cond);
1779 struct edge_info *edge_info;
1781 edge_info = allocate_edge_info (true_edge);
1782 record_conditions (edge_info, cond, inverted);
1784 if (code == EQ_EXPR)
1786 edge_info->lhs = op0;
1787 edge_info->rhs = op1;
1790 edge_info = allocate_edge_info (false_edge);
1791 record_conditions (edge_info, inverted, cond);
1793 if (TREE_CODE (inverted) == EQ_EXPR)
1795 edge_info->lhs = op0;
1796 edge_info->rhs = op1;
1801 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1805 /* Propagate information from BB to its outgoing edges.
1807 This can include equivalence information implied by control statements
1808 at the end of BB and const/copy propagation into PHIs in BB's
1809 successor blocks. */
1812 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1815 record_edge_info (bb);
1816 cprop_into_successor_phis (bb);
1819 /* Search for redundant computations in STMT. If any are found, then
1820 replace them with the variable holding the result of the computation.
1822 If safe, record this expression into the available expression hash
1826 eliminate_redundant_computations (gimple_stmt_iterator* gsi)
1831 bool retval = false;
1832 bool assigns_var_p = false;
1834 gimple stmt = gsi_stmt (*gsi);
1836 tree def = gimple_get_lhs (stmt);
1838 /* Certain expressions on the RHS can be optimized away, but can not
1839 themselves be entered into the hash tables. */
1841 || TREE_CODE (def) != SSA_NAME
1842 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1843 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF)
1844 /* Do not record equivalences for increments of ivs. This would create
1845 overlapping live ranges for a very questionable gain. */
1846 || simple_iv_increment_p (stmt))
1849 /* Check if the expression has been computed before. */
1850 cached_lhs = lookup_avail_expr (stmt, insert);
1852 opt_stats.num_exprs_considered++;
1854 /* Get the type of the expression we are trying to optimize. */
1855 if (is_gimple_assign (stmt))
1857 expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1858 assigns_var_p = true;
1860 else if (gimple_code (stmt) == GIMPLE_COND)
1861 expr_type = boolean_type_node;
1862 else if (is_gimple_call (stmt))
1864 gcc_assert (gimple_call_lhs (stmt));
1865 expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1866 assigns_var_p = true;
1868 else if (gimple_code (stmt) == GIMPLE_SWITCH)
1869 expr_type = TREE_TYPE (gimple_switch_index (stmt));
1876 /* It is safe to ignore types here since we have already done
1877 type checking in the hashing and equality routines. In fact
1878 type checking here merely gets in the way of constant
1879 propagation. Also, make sure that it is safe to propagate
1880 CACHED_LHS into the expression in STMT. */
1881 if ((TREE_CODE (cached_lhs) != SSA_NAME
1883 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1884 || may_propagate_copy_into_stmt (stmt, cached_lhs))
1886 #if defined ENABLE_CHECKING
1887 gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
1888 || is_gimple_min_invariant (cached_lhs));
1891 if (dump_file && (dump_flags & TDF_DETAILS))
1893 fprintf (dump_file, " Replaced redundant expr '");
1894 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1895 fprintf (dump_file, "' with '");
1896 print_generic_expr (dump_file, cached_lhs, dump_flags);
1897 fprintf (dump_file, "'\n");
1902 if (TREE_CODE (cached_lhs) == ADDR_EXPR
1903 || (POINTER_TYPE_P (expr_type)
1904 && is_gimple_min_invariant (cached_lhs)))
1908 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1909 cached_lhs = fold_convert (expr_type, cached_lhs);
1911 propagate_tree_value_into_stmt (gsi, cached_lhs);
1913 /* Since it is always necessary to mark the result as modified,
1914 perhaps we should move this into propagate_tree_value_into_stmt
1916 gimple_set_modified (gsi_stmt (*gsi), true);
1921 /* Return true if statement GS is an assignment that peforms a useless
1922 type conversion. It is is intended to be a tuples analog of function
1923 tree_ssa_useless_type_conversion. */
1926 gimple_assign_unary_useless_conversion_p (gimple gs)
1928 if (is_gimple_assign (gs)
1929 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs))
1930 || gimple_assign_rhs_code (gs) == VIEW_CONVERT_EXPR
1931 || gimple_assign_rhs_code (gs) == NON_LVALUE_EXPR))
1933 tree lhs_type = TREE_TYPE (gimple_assign_lhs (gs));
1934 tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (gs));
1935 return useless_type_conversion_p (lhs_type, rhs_type);
1941 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1942 the available expressions table or the const_and_copies table.
1943 Detect and record those equivalences. */
1944 /* We handle only very simple copy equivalences here. The heavy
1945 lifing is done by eliminate_redundant_computations. */
1948 record_equivalences_from_stmt (gimple stmt, int may_optimize_p)
1951 enum tree_code lhs_code;
1953 gcc_assert (is_gimple_assign (stmt));
1955 lhs = gimple_assign_lhs (stmt);
1956 lhs_code = TREE_CODE (lhs);
1958 if (lhs_code == SSA_NAME
1959 && (gimple_assign_single_p (stmt)
1960 || gimple_assign_unary_useless_conversion_p (stmt)))
1962 tree rhs = gimple_assign_rhs1 (stmt);
1964 /* Strip away any useless type conversions. */
1965 STRIP_USELESS_TYPE_CONVERSION (rhs);
1967 /* If the RHS of the assignment is a constant or another variable that
1968 may be propagated, register it in the CONST_AND_COPIES table. We
1969 do not need to record unwind data for this, since this is a true
1970 assignment and not an equivalence inferred from a comparison. All
1971 uses of this ssa name are dominated by this assignment, so unwinding
1972 just costs time and space. */
1974 && (TREE_CODE (rhs) == SSA_NAME
1975 || is_gimple_min_invariant (rhs)))
1977 if (dump_file && (dump_flags & TDF_DETAILS))
1979 fprintf (dump_file, "==== ASGN ");
1980 print_generic_expr (dump_file, lhs, 0);
1981 fprintf (dump_file, " = ");
1982 print_generic_expr (dump_file, rhs, 0);
1983 fprintf (dump_file, "\n");
1986 SSA_NAME_VALUE (lhs) = rhs;
1990 /* A memory store, even an aliased store, creates a useful
1991 equivalence. By exchanging the LHS and RHS, creating suitable
1992 vops and recording the result in the available expression table,
1993 we may be able to expose more redundant loads. */
1994 if (!gimple_has_volatile_ops (stmt)
1995 && gimple_references_memory_p (stmt)
1996 && gimple_assign_single_p (stmt)
1997 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1998 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1999 && !is_gimple_reg (lhs))
2001 tree rhs = gimple_assign_rhs1 (stmt);
2004 /* Build a new statement with the RHS and LHS exchanged. */
2005 if (TREE_CODE (rhs) == SSA_NAME)
2007 /* NOTE tuples. The call to gimple_build_assign below replaced
2008 a call to build_gimple_modify_stmt, which did not set the
2009 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
2010 may cause an SSA validation failure, as the LHS may be a
2011 default-initialized name and should have no definition. I'm
2012 a bit dubious of this, as the artificial statement that we
2013 generate here may in fact be ill-formed, but it is simply
2014 used as an internal device in this pass, and never becomes
2016 gimple defstmt = SSA_NAME_DEF_STMT (rhs);
2017 new_stmt = gimple_build_assign (rhs, lhs);
2018 SSA_NAME_DEF_STMT (rhs) = defstmt;
2021 new_stmt = gimple_build_assign (rhs, lhs);
2023 create_ssa_artificial_load_stmt (new_stmt, stmt, true);
2025 /* Finally enter the statement into the available expression
2027 lookup_avail_expr (new_stmt, true);
2031 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2032 CONST_AND_COPIES. */
2035 cprop_operand (gimple stmt, use_operand_p op_p)
2037 bool may_have_exposed_new_symbols = false;
2039 tree op = USE_FROM_PTR (op_p);
2041 /* If the operand has a known constant value or it is known to be a
2042 copy of some other variable, use the value or copy stored in
2043 CONST_AND_COPIES. */
2044 val = SSA_NAME_VALUE (op);
2045 if (val && val != op)
2047 /* Do not change the base variable in the virtual operand
2048 tables. That would make it impossible to reconstruct
2049 the renamed virtual operand if we later modify this
2050 statement. Also only allow the new value to be an SSA_NAME
2051 for propagation into virtual operands. */
2052 if (!is_gimple_reg (op)
2053 && (TREE_CODE (val) != SSA_NAME
2054 || is_gimple_reg (val)
2055 || get_virtual_var (val) != get_virtual_var (op)))
2058 /* Do not replace hard register operands in asm statements. */
2059 if (gimple_code (stmt) == GIMPLE_ASM
2060 && !may_propagate_copy_into_asm (op))
2063 /* Certain operands are not allowed to be copy propagated due
2064 to their interaction with exception handling and some GCC
2066 if (!may_propagate_copy (op, val))
2069 /* Do not propagate addresses that point to volatiles into memory
2070 stmts without volatile operands. */
2071 if (POINTER_TYPE_P (TREE_TYPE (val))
2072 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val)))
2073 && gimple_has_mem_ops (stmt)
2074 && !gimple_has_volatile_ops (stmt))
2077 /* Do not propagate copies if the propagated value is at a deeper loop
2078 depth than the propagatee. Otherwise, this may move loop variant
2079 variables outside of their loops and prevent coalescing
2080 opportunities. If the value was loop invariant, it will be hoisted
2081 by LICM and exposed for copy propagation. */
2082 if (loop_depth_of_name (val) > loop_depth_of_name (op))
2086 if (dump_file && (dump_flags & TDF_DETAILS))
2088 fprintf (dump_file, " Replaced '");
2089 print_generic_expr (dump_file, op, dump_flags);
2090 fprintf (dump_file, "' with %s '",
2091 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2092 print_generic_expr (dump_file, val, dump_flags);
2093 fprintf (dump_file, "'\n");
2096 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2097 that we may have exposed a new symbol for SSA renaming. */
2098 if (TREE_CODE (val) == ADDR_EXPR
2099 || (POINTER_TYPE_P (TREE_TYPE (op))
2100 && is_gimple_min_invariant (val)))
2101 may_have_exposed_new_symbols = true;
2103 if (TREE_CODE (val) != SSA_NAME)
2104 opt_stats.num_const_prop++;
2106 opt_stats.num_copy_prop++;
2108 propagate_value (op_p, val);
2110 /* And note that we modified this statement. This is now
2111 safe, even if we changed virtual operands since we will
2112 rescan the statement and rewrite its operands again. */
2113 gimple_set_modified (stmt, true);
2115 return may_have_exposed_new_symbols;
2118 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2119 known value for that SSA_NAME (or NULL if no value is known).
2121 Propagate values from CONST_AND_COPIES into the uses, vuses and
2122 vdef_ops of STMT. */
2125 cprop_into_stmt (gimple stmt)
2127 bool may_have_exposed_new_symbols = false;
2131 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
2133 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
2134 may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
2137 return may_have_exposed_new_symbols;
2140 /* Optimize the statement pointed to by iterator SI.
2142 We try to perform some simplistic global redundancy elimination and
2143 constant propagation:
2145 1- To detect global redundancy, we keep track of expressions that have
2146 been computed in this block and its dominators. If we find that the
2147 same expression is computed more than once, we eliminate repeated
2148 computations by using the target of the first one.
2150 2- Constant values and copy assignments. This is used to do very
2151 simplistic constant and copy propagation. When a constant or copy
2152 assignment is found, we map the value on the RHS of the assignment to
2153 the variable in the LHS in the CONST_AND_COPIES table. */
2156 optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2157 basic_block bb, gimple_stmt_iterator si)
2159 gimple stmt, old_stmt;
2160 bool may_optimize_p;
2161 bool may_have_exposed_new_symbols;
2162 bool modified_p = false;
2164 old_stmt = stmt = gsi_stmt (si);
2166 if (gimple_code (stmt) == GIMPLE_COND)
2167 canonicalize_comparison (stmt);
2169 update_stmt_if_modified (stmt);
2170 opt_stats.num_stmts++;
2171 push_stmt_changes (gsi_stmt_ptr (&si));
2173 if (dump_file && (dump_flags & TDF_DETAILS))
2175 fprintf (dump_file, "Optimizing statement ");
2176 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2179 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2180 may_have_exposed_new_symbols = cprop_into_stmt (stmt);
2182 /* If the statement has been modified with constant replacements,
2183 fold its RHS before checking for redundant computations. */
2184 if (gimple_modified_p (stmt))
2188 /* Try to fold the statement making sure that STMT is kept
2190 if (fold_stmt (&si))
2192 stmt = gsi_stmt (si);
2194 if (dump_file && (dump_flags & TDF_DETAILS))
2196 fprintf (dump_file, " Folded to: ");
2197 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2201 /* We only need to consider cases that can yield a gimple operand. */
2202 if (gimple_assign_single_p (stmt))
2203 rhs = gimple_assign_rhs1 (stmt);
2204 else if (gimple_code (stmt) == GIMPLE_GOTO)
2205 rhs = gimple_goto_dest (stmt);
2206 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2207 /* This should never be an ADDR_EXPR. */
2208 rhs = gimple_switch_index (stmt);
2210 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
2211 recompute_tree_invariant_for_addr_expr (rhs);
2213 /* Constant/copy propagation above may change the set of
2214 virtual operands associated with this statement. Folding
2215 may remove the need for some virtual operands.
2217 Indicate we will need to rescan and rewrite the statement. */
2218 may_have_exposed_new_symbols = true;
2219 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2220 even if fold_stmt updated the stmt already and thus cleared
2221 gimple_modified_p flag on it. */
2225 /* Check for redundant computations. Do this optimization only
2226 for assignments that have no volatile ops and conditionals. */
2227 may_optimize_p = (!gimple_has_volatile_ops (stmt)
2228 && ((is_gimple_assign (stmt)
2229 && !gimple_rhs_has_side_effects (stmt))
2230 || (is_gimple_call (stmt)
2231 && gimple_call_lhs (stmt) != NULL_TREE
2232 && !gimple_rhs_has_side_effects (stmt))
2233 || gimple_code (stmt) == GIMPLE_COND
2234 || gimple_code (stmt) == GIMPLE_SWITCH));
2238 may_have_exposed_new_symbols |= eliminate_redundant_computations (&si);
2239 stmt = gsi_stmt (si);
2242 /* Record any additional equivalences created by this statement. */
2243 if (is_gimple_assign (stmt))
2244 record_equivalences_from_stmt (stmt, may_optimize_p);
2246 /* If STMT is a COND_EXPR and it was modified, then we may know
2247 where it goes. If that is the case, then mark the CFG as altered.
2249 This will cause us to later call remove_unreachable_blocks and
2250 cleanup_tree_cfg when it is safe to do so. It is not safe to
2251 clean things up here since removal of edges and such can trigger
2252 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2255 That's all fine and good, except that once SSA_NAMEs are released
2256 to the manager, we must not call create_ssa_name until all references
2257 to released SSA_NAMEs have been eliminated.
2259 All references to the deleted SSA_NAMEs can not be eliminated until
2260 we remove unreachable blocks.
2262 We can not remove unreachable blocks until after we have completed
2263 any queued jump threading.
2265 We can not complete any queued jump threads until we have taken
2266 appropriate variables out of SSA form. Taking variables out of
2267 SSA form can call create_ssa_name and thus we lose.
2269 Ultimately I suspect we're going to need to change the interface
2270 into the SSA_NAME manager. */
2271 if (gimple_modified_p (stmt) || modified_p)
2275 if (gimple_code (stmt) == GIMPLE_COND)
2276 val = fold_binary (gimple_cond_code (stmt), boolean_type_node,
2277 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
2278 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2279 val = gimple_switch_index (stmt);
2281 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
2284 /* If we simplified a statement in such a way as to be shown that it
2285 cannot trap, update the eh information and the cfg to match. */
2286 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
2288 bitmap_set_bit (need_eh_cleanup, bb->index);
2289 if (dump_file && (dump_flags & TDF_DETAILS))
2290 fprintf (dump_file, " Flagged to clear EH edges.\n");
2294 if (may_have_exposed_new_symbols)
2296 /* Queue the statement to be re-scanned after all the
2297 AVAIL_EXPRS have been processed. The change buffer stack for
2298 all the pushed statements will be processed when this queue
2300 VEC_safe_push (gimple_p, heap, stmts_to_rescan, gsi_stmt_ptr (&si));
2304 /* Otherwise, just discard the recently pushed change buffer. If
2305 not, the STMTS_TO_RESCAN queue will get out of synch with the
2306 change buffer stack. */
2307 discard_stmt_changes (gsi_stmt_ptr (&si));
2311 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
2312 If found, return its LHS. Otherwise insert STMT in the table and
2315 Also, when an expression is first inserted in the table, it is also
2316 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
2317 we finish processing this block and its children. */
2320 lookup_avail_expr (gimple stmt, bool insert)
2325 struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
2327 /* Get LHS of assignment or call, else NULL_TREE. */
2328 lhs = gimple_get_lhs (stmt);
2330 initialize_hash_element (stmt, lhs, element);
2332 if (dump_file && (dump_flags & TDF_DETAILS))
2334 fprintf (dump_file, "LKUP ");
2335 print_expr_hash_elt (dump_file, element);
2338 /* Don't bother remembering constant assignments and copy operations.
2339 Constants and copy operations are handled by the constant/copy propagator
2340 in optimize_stmt. */
2341 if (element->expr.kind == EXPR_SINGLE
2342 && (TREE_CODE (element->expr.ops.single.rhs) == SSA_NAME
2343 || is_gimple_min_invariant (element->expr.ops.single.rhs)))
2349 /* Finally try to find the expression in the main expression hash table. */
2350 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
2351 (insert ? INSERT : NO_INSERT));
2360 *slot = (void *) element;
2362 if (dump_file && (dump_flags & TDF_DETAILS))
2364 fprintf (dump_file, "2>>> ");
2365 print_expr_hash_elt (dump_file, element);
2368 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
2372 /* Extract the LHS of the assignment so that it can be used as the current
2373 definition of another variable. */
2374 lhs = ((struct expr_hash_elt *)*slot)->lhs;
2376 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2377 use the value from the const_and_copies table. */
2378 if (TREE_CODE (lhs) == SSA_NAME)
2380 temp = SSA_NAME_VALUE (lhs);
2387 if (dump_file && (dump_flags & TDF_DETAILS))
2389 fprintf (dump_file, "FIND: ");
2390 print_generic_expr (dump_file, lhs, 0);
2391 fprintf (dump_file, "\n");
2397 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number
2398 for expressions using the code of the expression and the SSA numbers of
2402 avail_expr_hash (const void *p)
2404 gimple stmt = ((const struct expr_hash_elt *)p)->stmt;
2405 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr;
2410 val = iterative_hash_hashable_expr (expr, val);
2412 /* If the hash table entry is not associated with a statement, then we
2413 can just hash the expression and not worry about virtual operands
2418 /* Add the SSA version numbers of every vuse operand. This is important
2419 because compound variables like arrays are not renamed in the
2420 operands. Rather, the rename is done on the virtual variable
2421 representing all the elements of the array. */
2422 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
2423 val = iterative_hash_expr (vuse, val);
2429 real_avail_expr_hash (const void *p)
2431 return ((const struct expr_hash_elt *)p)->hash;
2435 avail_expr_eq (const void *p1, const void *p2)
2437 gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
2438 const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr;
2439 const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp;
2440 gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
2441 const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr;
2442 const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp;
2444 /* This case should apply only when removing entries from the table. */
2445 if (stamp1 == stamp2)
2449 We add stmts to a hash table and them modify them. To detect the case
2450 that we modify a stmt and then search for it, we assume that the hash
2451 is always modified by that change.
2452 We have to fully check why this doesn't happen on trunk or rewrite
2453 this in a more reliable (and easier to understand) way. */
2454 if (((const struct expr_hash_elt *)p1)->hash
2455 != ((const struct expr_hash_elt *)p2)->hash)
2458 /* In case of a collision, both RHS have to be identical and have the
2459 same VUSE operands. */
2460 if (hashable_expr_equal_p (expr1, expr2)
2461 && types_compatible_p (expr1->type, expr2->type))
2463 /* Note that STMT1 and/or STMT2 may be NULL. */
2464 bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE);
2471 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2472 up degenerate PHIs created by or exposed by jump threading. */
2474 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2478 degenerate_phi_result (gimple phi)
2480 tree lhs = gimple_phi_result (phi);
2484 /* Ignoring arguments which are the same as LHS, if all the remaining
2485 arguments are the same, then the PHI is a degenerate and has the
2486 value of that common argument. */
2487 for (i = 0; i < gimple_phi_num_args (phi); i++)
2489 tree arg = gimple_phi_arg_def (phi, i);
2497 else if (!operand_equal_p (arg, val, 0))
2500 return (i == gimple_phi_num_args (phi) ? val : NULL);
2503 /* Given a statement STMT, which is either a PHI node or an assignment,
2504 remove it from the IL. */
2507 remove_stmt_or_phi (gimple stmt)
2509 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
2511 if (gimple_code (stmt) == GIMPLE_PHI)
2512 remove_phi_node (&gsi, true);
2515 gsi_remove (&gsi, true);
2516 release_defs (stmt);
2520 /* Given a statement STMT, which is either a PHI node or an assignment,
2521 return the "rhs" of the node, in the case of a non-degenerate
2522 phi, NULL is returned. */
2525 get_rhs_or_phi_arg (gimple stmt)
2527 if (gimple_code (stmt) == GIMPLE_PHI)
2528 return degenerate_phi_result (stmt);
2529 else if (gimple_assign_single_p (stmt))
2530 return gimple_assign_rhs1 (stmt);
2536 /* Given a statement STMT, which is either a PHI node or an assignment,
2537 return the "lhs" of the node. */
2540 get_lhs_or_phi_result (gimple stmt)
2542 if (gimple_code (stmt) == GIMPLE_PHI)
2543 return gimple_phi_result (stmt);
2544 else if (is_gimple_assign (stmt))
2545 return gimple_assign_lhs (stmt);
2550 /* Propagate RHS into all uses of LHS (when possible).
2552 RHS and LHS are derived from STMT, which is passed in solely so
2553 that we can remove it if propagation is successful.
2555 When propagating into a PHI node or into a statement which turns
2556 into a trivial copy or constant initialization, set the
2557 appropriate bit in INTERESTING_NAMEs so that we will visit those
2558 nodes as well in an effort to pick up secondary optimization
2562 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
2564 /* First verify that propagation is valid and isn't going to move a
2565 loop variant variable outside its loop. */
2566 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
2567 && (TREE_CODE (rhs) != SSA_NAME
2568 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
2569 && may_propagate_copy (lhs, rhs)
2570 && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
2572 use_operand_p use_p;
2573 imm_use_iterator iter;
2578 if (dump_file && (dump_flags & TDF_DETAILS))
2580 fprintf (dump_file, " Replacing '");
2581 print_generic_expr (dump_file, lhs, dump_flags);
2582 fprintf (dump_file, "' with %s '",
2583 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
2584 print_generic_expr (dump_file, rhs, dump_flags);
2585 fprintf (dump_file, "'\n");
2588 /* Walk over every use of LHS and try to replace the use with RHS.
2589 At this point the only reason why such a propagation would not
2590 be successful would be if the use occurs in an ASM_EXPR. */
2591 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
2594 /* It's not always safe to propagate into an ASM_EXPR. */
2595 if (gimple_code (use_stmt) == GIMPLE_ASM
2596 && ! may_propagate_copy_into_asm (lhs))
2602 /* It's not ok to propagate into the definition stmt of RHS.
2604 # prephitmp.12_36 = PHI <g_67.1_6(9)>
2605 g_67.1_6 = prephitmp.12_36;
2607 While this is strictly all dead code we do not want to
2608 deal with this here. */
2609 if (TREE_CODE (rhs) == SSA_NAME
2610 && SSA_NAME_DEF_STMT (rhs) == use_stmt)
2617 if (dump_file && (dump_flags & TDF_DETAILS))
2619 fprintf (dump_file, " Original statement:");
2620 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2623 push_stmt_changes (&use_stmt);
2625 /* Propagate the RHS into this use of the LHS. */
2626 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2627 propagate_value (use_p, rhs);
2629 /* Special cases to avoid useless calls into the folding
2630 routines, operand scanning, etc.
2632 First, propagation into a PHI may cause the PHI to become
2633 a degenerate, so mark the PHI as interesting. No other
2634 actions are necessary.
2636 Second, if we're propagating a virtual operand and the
2637 propagation does not change the underlying _DECL node for
2638 the virtual operand, then no further actions are necessary. */
2639 if (gimple_code (use_stmt) == GIMPLE_PHI
2640 || (! is_gimple_reg (lhs)
2641 && TREE_CODE (rhs) == SSA_NAME
2642 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
2645 if (dump_file && (dump_flags & TDF_DETAILS))
2647 fprintf (dump_file, " Updated statement:");
2648 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2651 /* Propagation into a PHI may expose new degenerate PHIs,
2652 so mark the result of the PHI as interesting. */
2653 if (gimple_code (use_stmt) == GIMPLE_PHI)
2655 tree result = get_lhs_or_phi_result (use_stmt);
2656 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2659 discard_stmt_changes (&use_stmt);
2663 /* From this point onward we are propagating into a
2664 real statement. Folding may (or may not) be possible,
2665 we may expose new operands, expose dead EH edges,
2667 /* NOTE tuples. In the tuples world, fold_stmt_inplace
2668 cannot fold a call that simplifies to a constant,
2669 because the GIMPLE_CALL must be replaced by a
2670 GIMPLE_ASSIGN, and there is no way to effect such a
2671 transformation in-place. We might want to consider
2672 using the more general fold_stmt here. */
2673 fold_stmt_inplace (use_stmt);
2675 /* Sometimes propagation can expose new operands to the
2676 renamer. Note this will call update_stmt at the
2677 appropriate time. */
2678 pop_stmt_changes (&use_stmt);
2681 if (dump_file && (dump_flags & TDF_DETAILS))
2683 fprintf (dump_file, " Updated statement:");
2684 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2687 /* If we replaced a variable index with a constant, then
2688 we would need to update the invariant flag for ADDR_EXPRs. */
2689 if (gimple_assign_single_p (use_stmt)
2690 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
2691 recompute_tree_invariant_for_addr_expr
2692 (gimple_assign_rhs1 (use_stmt));
2694 /* If we cleaned up EH information from the statement,
2695 mark its containing block as needing EH cleanups. */
2696 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
2698 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
2699 if (dump_file && (dump_flags & TDF_DETAILS))
2700 fprintf (dump_file, " Flagged to clear EH edges.\n");
2703 /* Propagation may expose new trivial copy/constant propagation
2705 if (gimple_assign_single_p (use_stmt)
2706 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
2707 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
2708 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
2710 tree result = get_lhs_or_phi_result (use_stmt);
2711 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2714 /* Propagation into these nodes may make certain edges in
2715 the CFG unexecutable. We want to identify them as PHI nodes
2716 at the destination of those unexecutable edges may become
2718 else if (gimple_code (use_stmt) == GIMPLE_COND
2719 || gimple_code (use_stmt) == GIMPLE_SWITCH
2720 || gimple_code (use_stmt) == GIMPLE_GOTO)
2724 if (gimple_code (use_stmt) == GIMPLE_COND)
2725 val = fold_binary (gimple_cond_code (use_stmt),
2727 gimple_cond_lhs (use_stmt),
2728 gimple_cond_rhs (use_stmt));
2729 else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
2730 val = gimple_switch_index (use_stmt);
2732 val = gimple_goto_dest (use_stmt);
2734 if (val && is_gimple_min_invariant (val))
2736 basic_block bb = gimple_bb (use_stmt);
2737 edge te = find_taken_edge (bb, val);
2740 gimple_stmt_iterator gsi, psi;
2742 /* Remove all outgoing edges except TE. */
2743 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
2747 /* Mark all the PHI nodes at the destination of
2748 the unexecutable edge as interesting. */
2749 for (psi = gsi_start_phis (e->dest);
2753 gimple phi = gsi_stmt (psi);
2755 tree result = gimple_phi_result (phi);
2756 int version = SSA_NAME_VERSION (result);
2758 bitmap_set_bit (interesting_names, version);
2761 te->probability += e->probability;
2763 te->count += e->count;
2771 gsi = gsi_last_bb (gimple_bb (use_stmt));
2772 gsi_remove (&gsi, true);
2774 /* And fixup the flags on the single remaining edge. */
2775 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
2776 te->flags &= ~EDGE_ABNORMAL;
2777 te->flags |= EDGE_FALLTHRU;
2778 if (te->probability > REG_BR_PROB_BASE)
2779 te->probability = REG_BR_PROB_BASE;
2784 /* Ensure there is nothing else to do. */
2785 gcc_assert (!all || has_zero_uses (lhs));
2787 /* If we were able to propagate away all uses of LHS, then
2788 we can remove STMT. */
2790 remove_stmt_or_phi (stmt);
2794 /* STMT is either a PHI node (potentially a degenerate PHI node) or
2795 a statement that is a trivial copy or constant initialization.
2797 Attempt to eliminate T by propagating its RHS into all uses of
2798 its LHS. This may in turn set new bits in INTERESTING_NAMES
2799 for nodes we want to revisit later.
2801 All exit paths should clear INTERESTING_NAMES for the result
2805 eliminate_const_or_copy (gimple stmt, bitmap interesting_names)
2807 tree lhs = get_lhs_or_phi_result (stmt);
2809 int version = SSA_NAME_VERSION (lhs);
2811 /* If the LHS of this statement or PHI has no uses, then we can
2812 just eliminate it. This can occur if, for example, the PHI
2813 was created by block duplication due to threading and its only
2814 use was in the conditional at the end of the block which was
2816 if (has_zero_uses (lhs))
2818 bitmap_clear_bit (interesting_names, version);
2819 remove_stmt_or_phi (stmt);
2823 /* Get the RHS of the assignment or PHI node if the PHI is a
2825 rhs = get_rhs_or_phi_arg (stmt);
2828 bitmap_clear_bit (interesting_names, version);
2832 propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
2834 /* Note that STMT may well have been deleted by now, so do
2835 not access it, instead use the saved version # to clear
2836 T's entry in the worklist. */
2837 bitmap_clear_bit (interesting_names, version);
2840 /* The first phase in degenerate PHI elimination.
2842 Eliminate the degenerate PHIs in BB, then recurse on the
2843 dominator children of BB. */
2846 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names)
2848 gimple_stmt_iterator gsi;
2851 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2853 gimple phi = gsi_stmt (gsi);
2855 eliminate_const_or_copy (phi, interesting_names);
2858 /* Recurse into the dominator children of BB. */
2859 for (son = first_dom_son (CDI_DOMINATORS, bb);
2861 son = next_dom_son (CDI_DOMINATORS, son))
2862 eliminate_degenerate_phis_1 (son, interesting_names);
2866 /* A very simple pass to eliminate degenerate PHI nodes from the
2867 IL. This is meant to be fast enough to be able to be run several
2868 times in the optimization pipeline.
2870 Certain optimizations, particularly those which duplicate blocks
2871 or remove edges from the CFG can create or expose PHIs which are
2872 trivial copies or constant initializations.
2874 While we could pick up these optimizations in DOM or with the
2875 combination of copy-prop and CCP, those solutions are far too
2876 heavy-weight for our needs.
2878 This implementation has two phases so that we can efficiently
2879 eliminate the first order degenerate PHIs and second order
2882 The first phase performs a dominator walk to identify and eliminate
2883 the vast majority of the degenerate PHIs. When a degenerate PHI
2884 is identified and eliminated any affected statements or PHIs
2885 are put on a worklist.
2887 The second phase eliminates degenerate PHIs and trivial copies
2888 or constant initializations using the worklist. This is how we
2889 pick up the secondary optimization opportunities with minimal
2893 eliminate_degenerate_phis (void)
2895 bitmap interesting_names;
2896 bitmap interesting_names1;
2898 /* Bitmap of blocks which need EH information updated. We can not
2899 update it on-the-fly as doing so invalidates the dominator tree. */
2900 need_eh_cleanup = BITMAP_ALLOC (NULL);
2902 /* INTERESTING_NAMES is effectively our worklist, indexed by
2905 A set bit indicates that the statement or PHI node which
2906 defines the SSA_NAME should be (re)examined to determine if
2907 it has become a degenerate PHI or trivial const/copy propagation
2910 Experiments have show we generally get better compilation
2911 time behavior with bitmaps rather than sbitmaps. */
2912 interesting_names = BITMAP_ALLOC (NULL);
2913 interesting_names1 = BITMAP_ALLOC (NULL);
2915 calculate_dominance_info (CDI_DOMINATORS);
2916 cfg_altered = false;
2918 /* First phase. Eliminate degenerate PHIs via a dominator
2921 Experiments have indicated that we generally get better
2922 compile-time behavior by visiting blocks in the first
2923 phase in dominator order. Presumably this is because walking
2924 in dominator order leaves fewer PHIs for later examination
2925 by the worklist phase. */
2926 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
2928 /* Second phase. Eliminate second order degenerate PHIs as well
2929 as trivial copies or constant initializations identified by
2930 the first phase or this phase. Basically we keep iterating
2931 until our set of INTERESTING_NAMEs is empty. */
2932 while (!bitmap_empty_p (interesting_names))
2937 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2938 changed during the loop. Copy it to another bitmap and
2940 bitmap_copy (interesting_names1, interesting_names);
2942 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
2944 tree name = ssa_name (i);
2946 /* Ignore SSA_NAMEs that have been released because
2947 their defining statement was deleted (unreachable). */
2949 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
2955 free_dominance_info (CDI_DOMINATORS);
2957 /* Propagation of const and copies may make some EH edges dead. Purge
2958 such edges from the CFG as needed. */
2959 if (!bitmap_empty_p (need_eh_cleanup))
2961 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
2962 BITMAP_FREE (need_eh_cleanup);
2965 BITMAP_FREE (interesting_names);
2966 BITMAP_FREE (interesting_names1);
2970 struct gimple_opt_pass pass_phi_only_cprop =
2974 "phicprop", /* name */
2975 gate_dominator, /* gate */
2976 eliminate_degenerate_phis, /* execute */
2979 0, /* static_pass_number */
2980 TV_TREE_PHI_CPROP, /* tv_id */
2981 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2982 0, /* properties_provided */
2983 0, /* properties_destroyed */
2984 0, /* todo_flags_start */
2990 | TODO_update_ssa /* todo_flags_finish */