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 static VEC(gimple_p,heap) *stmts_to_rescan;
139 /* Structure for entries in the expression hash table. */
143 /* The value (lhs) of this expression. */
146 /* The expression (rhs) we want to record. */
147 struct hashable_expr expr;
149 /* The stmt pointer if this element corresponds to a statement. */
152 /* The hash value for RHS. */
155 /* A unique stamp, typically the address of the hash
156 element itself, used in removing entries from the table. */
157 struct expr_hash_elt *stamp;
160 /* Stack of dest,src pairs that need to be restored during finalization.
162 A NULL entry is used to mark the end of pairs which need to be
163 restored during finalization of this block. */
164 static VEC(tree,heap) *const_and_copies_stack;
166 /* Track whether or not we have changed the control flow graph. */
167 static bool cfg_altered;
169 /* Bitmap of blocks that have had EH statements cleaned. We should
170 remove their dead edges eventually. */
171 static bitmap need_eh_cleanup;
173 /* Statistics for dominator optimizations. */
177 long num_exprs_considered;
183 static struct opt_stats_d opt_stats;
185 /* Local functions. */
186 static void optimize_stmt (struct dom_walk_data *,
188 gimple_stmt_iterator);
189 static tree lookup_avail_expr (gimple, bool);
190 static hashval_t avail_expr_hash (const void *);
191 static hashval_t real_avail_expr_hash (const void *);
192 static int avail_expr_eq (const void *, const void *);
193 static void htab_statistics (FILE *, htab_t);
194 static void record_cond (struct cond_equivalence *);
195 static void record_const_or_copy (tree, tree);
196 static void record_equality (tree, tree);
197 static void record_equivalences_from_phis (basic_block);
198 static void record_equivalences_from_incoming_edge (basic_block);
199 static bool eliminate_redundant_computations (gimple_stmt_iterator *);
200 static void record_equivalences_from_stmt (gimple, int);
201 static void dom_thread_across_edge (struct dom_walk_data *, edge);
202 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
203 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
204 static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block);
205 static void remove_local_expressions_from_table (void);
206 static void restore_vars_to_original_value (void);
207 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
210 /* Given a statement STMT, initialize the hash table element pointed to
214 initialize_hash_element (gimple stmt, tree lhs,
215 struct expr_hash_elt *element)
217 enum gimple_code code = gimple_code (stmt);
218 struct hashable_expr *expr = &element->expr;
220 if (code == GIMPLE_ASSIGN)
222 enum tree_code subcode = gimple_assign_rhs_code (stmt);
224 expr->type = NULL_TREE;
226 switch (get_gimple_rhs_class (subcode))
228 case GIMPLE_SINGLE_RHS:
229 expr->kind = EXPR_SINGLE;
230 expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
232 case GIMPLE_UNARY_RHS:
233 expr->kind = EXPR_UNARY;
234 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
235 expr->ops.unary.op = subcode;
236 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
238 case GIMPLE_BINARY_RHS:
239 expr->kind = EXPR_BINARY;
240 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
241 expr->ops.binary.op = subcode;
242 expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
243 expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
249 else if (code == GIMPLE_COND)
251 expr->type = boolean_type_node;
252 expr->kind = EXPR_BINARY;
253 expr->ops.binary.op = gimple_cond_code (stmt);
254 expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
255 expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
257 else if (code == GIMPLE_CALL)
259 size_t nargs = gimple_call_num_args (stmt);
262 gcc_assert (gimple_call_lhs (stmt));
264 expr->type = TREE_TYPE (gimple_call_lhs (stmt));
265 expr->kind = EXPR_CALL;
266 expr->ops.call.fn = gimple_call_fn (stmt);
268 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
269 expr->ops.call.pure = true;
271 expr->ops.call.pure = false;
273 expr->ops.call.nargs = nargs;
274 expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree));
275 for (i = 0; i < nargs; i++)
276 expr->ops.call.args[i] = gimple_call_arg (stmt, i);
278 else if (code == GIMPLE_SWITCH)
280 expr->type = TREE_TYPE (gimple_switch_index (stmt));
281 expr->kind = EXPR_SINGLE;
282 expr->ops.single.rhs = gimple_switch_index (stmt);
284 else if (code == GIMPLE_GOTO)
286 expr->type = TREE_TYPE (gimple_goto_dest (stmt));
287 expr->kind = EXPR_SINGLE;
288 expr->ops.single.rhs = gimple_goto_dest (stmt);
294 element->stmt = stmt;
295 element->hash = avail_expr_hash (element);
296 element->stamp = element;
299 /* Given a conditional expression COND as a tree, initialize
300 a hashable_expr expression EXPR. The conditional must be a
301 comparison or logical negation. A constant or a variable is
305 initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
307 expr->type = boolean_type_node;
309 if (COMPARISON_CLASS_P (cond))
311 expr->kind = EXPR_BINARY;
312 expr->ops.binary.op = TREE_CODE (cond);
313 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
314 expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
316 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
318 expr->kind = EXPR_UNARY;
319 expr->ops.unary.op = TRUTH_NOT_EXPR;
320 expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
326 /* Given a hashable_expr expression EXPR and an LHS,
327 initialize the hash table element pointed to by ELEMENT. */
330 initialize_hash_element_from_expr (struct hashable_expr *expr,
332 struct expr_hash_elt *element)
334 element->expr = *expr;
336 element->stmt = NULL;
337 element->hash = avail_expr_hash (element);
338 element->stamp = element;
341 /* Compare two hashable_expr structures for equivalence.
342 They are considered equivalent when the the expressions
343 they denote must necessarily be equal. The logic is intended
344 to follow that of operand_equal_p in fold-const.c */
347 hashable_expr_equal_p (const struct hashable_expr *expr0,
348 const struct hashable_expr *expr1)
350 tree type0 = expr0->type;
351 tree type1 = expr1->type;
353 /* If either type is NULL, there is nothing to check. */
354 if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
357 /* If both types don't have the same signedness, precision, and mode,
358 then we can't consider them equal. */
360 && (TREE_CODE (type0) == ERROR_MARK
361 || TREE_CODE (type1) == ERROR_MARK
362 || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
363 || TYPE_PRECISION (type0) != TYPE_PRECISION (type1)
364 || TYPE_MODE (type0) != TYPE_MODE (type1)))
367 if (expr0->kind != expr1->kind)
373 return operand_equal_p (expr0->ops.single.rhs,
374 expr1->ops.single.rhs, 0);
377 if (expr0->ops.unary.op != expr1->ops.unary.op)
380 if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
381 || expr0->ops.unary.op == NON_LVALUE_EXPR)
382 && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
385 return operand_equal_p (expr0->ops.unary.opnd,
386 expr1->ops.unary.opnd, 0);
390 if (expr0->ops.binary.op != expr1->ops.binary.op)
393 if (operand_equal_p (expr0->ops.binary.opnd0,
394 expr1->ops.binary.opnd0, 0)
395 && operand_equal_p (expr0->ops.binary.opnd1,
396 expr1->ops.binary.opnd1, 0))
399 /* For commutative ops, allow the other order. */
400 return (commutative_tree_code (expr0->ops.binary.op)
401 && operand_equal_p (expr0->ops.binary.opnd0,
402 expr1->ops.binary.opnd1, 0)
403 && operand_equal_p (expr0->ops.binary.opnd1,
404 expr1->ops.binary.opnd0, 0));
411 /* If the calls are to different functions, then they
412 clearly cannot be equal. */
413 if (! operand_equal_p (expr0->ops.call.fn,
414 expr1->ops.call.fn, 0))
417 if (! expr0->ops.call.pure)
420 if (expr0->ops.call.nargs != expr1->ops.call.nargs)
423 for (i = 0; i < expr0->ops.call.nargs; i++)
424 if (! operand_equal_p (expr0->ops.call.args[i],
425 expr1->ops.call.args[i], 0))
436 /* Compute a hash value for a hashable_expr value EXPR and a
437 previously accumulated hash value VAL. If two hashable_expr
438 values compare equal with hashable_expr_equal_p, they must
439 hash to the same value, given an identical value of VAL.
440 The logic is intended to follow iterative_hash_expr in tree.c. */
443 iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val)
448 val = iterative_hash_expr (expr->ops.single.rhs, val);
452 val = iterative_hash_object (expr->ops.unary.op, val);
454 /* Make sure to include signedness in the hash computation.
455 Don't hash the type, that can lead to having nodes which
456 compare equal according to operand_equal_p, but which
457 have different hash codes. */
458 if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
459 || expr->ops.unary.op == NON_LVALUE_EXPR)
460 val += TYPE_UNSIGNED (expr->type);
462 val = iterative_hash_expr (expr->ops.unary.opnd, val);
466 val = iterative_hash_object (expr->ops.binary.op, val);
467 if (commutative_tree_code (expr->ops.binary.op))
468 val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
469 expr->ops.binary.opnd1, val);
472 val = iterative_hash_expr (expr->ops.binary.opnd0, val);
473 val = iterative_hash_expr (expr->ops.binary.opnd1, val);
480 enum tree_code code = CALL_EXPR;
482 val = iterative_hash_object (code, val);
483 val = iterative_hash_expr (expr->ops.call.fn, val);
484 for (i = 0; i < expr->ops.call.nargs; i++)
485 val = iterative_hash_expr (expr->ops.call.args[i], val);
496 /* Print a diagnostic dump of an expression hash table entry. */
499 print_expr_hash_elt (FILE * stream, const struct expr_hash_elt *element)
502 fprintf (stream, "STMT ");
504 fprintf (stream, "COND ");
508 print_generic_expr (stream, element->lhs, 0);
509 fprintf (stream, " = ");
512 switch (element->expr.kind)
515 print_generic_expr (stream, element->expr.ops.single.rhs, 0);
519 fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]);
520 print_generic_expr (stream, element->expr.ops.unary.opnd, 0);
524 print_generic_expr (stream, element->expr.ops.binary.opnd0, 0);
525 fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]);
526 print_generic_expr (stream, element->expr.ops.binary.opnd1, 0);
532 size_t nargs = element->expr.ops.call.nargs;
534 print_generic_expr (stream, element->expr.ops.call.fn, 0);
535 fprintf (stream, " (");
536 for (i = 0; i < nargs; i++)
538 print_generic_expr (stream, element->expr.ops.call.args[i], 0);
540 fprintf (stream, ", ");
542 fprintf (stream, ")");
546 fprintf (stream, "\n");
550 fprintf (stream, " ");
551 print_gimple_stmt (stream, element->stmt, 0, 0);
555 /* Delete an expr_hash_elt and reclaim its storage. */
558 free_expr_hash_elt (void *elt)
560 struct expr_hash_elt *element = ((struct expr_hash_elt *)elt);
562 if (element->expr.kind == EXPR_CALL)
563 free (element->expr.ops.call.args);
568 /* Allocate an EDGE_INFO for edge E and attach it to E.
569 Return the new EDGE_INFO structure. */
571 static struct edge_info *
572 allocate_edge_info (edge e)
574 struct edge_info *edge_info;
576 edge_info = XCNEW (struct edge_info);
582 /* Free all EDGE_INFO structures associated with edges in the CFG.
583 If a particular edge can be threaded, copy the redirection
584 target from the EDGE_INFO structure into the edge's AUX field
585 as required by code to update the CFG and SSA graph for
589 free_all_edge_infos (void)
597 FOR_EACH_EDGE (e, ei, bb->preds)
599 struct edge_info *edge_info = (struct edge_info *) e->aux;
603 if (edge_info->cond_equivalences)
604 free (edge_info->cond_equivalences);
612 /* Jump threading, redundancy elimination and const/copy propagation.
614 This pass may expose new symbols that need to be renamed into SSA. For
615 every new symbol exposed, its corresponding bit will be set in
619 tree_ssa_dominator_optimize (void)
621 struct dom_walk_data walk_data;
624 memset (&opt_stats, 0, sizeof (opt_stats));
626 /* Create our hash tables. */
627 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt);
628 avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20);
629 const_and_copies_stack = VEC_alloc (tree, heap, 20);
630 stmts_to_rescan = VEC_alloc (gimple_p, heap, 20);
631 need_eh_cleanup = BITMAP_ALLOC (NULL);
633 /* Setup callbacks for the generic dominator tree walker. */
634 walk_data.walk_stmts_backward = false;
635 walk_data.dom_direction = CDI_DOMINATORS;
636 walk_data.initialize_block_local_data = NULL;
637 walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
638 walk_data.before_dom_children_walk_stmts = optimize_stmt;
639 walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
640 walk_data.after_dom_children_before_stmts = NULL;
641 walk_data.after_dom_children_walk_stmts = NULL;
642 walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
643 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
644 When we attach more stuff we'll need to fill this out with a real
646 walk_data.global_data = NULL;
647 walk_data.block_local_data_size = 0;
648 walk_data.interesting_blocks = NULL;
650 /* Now initialize the dominator walker. */
651 init_walk_dominator_tree (&walk_data);
653 calculate_dominance_info (CDI_DOMINATORS);
656 /* We need to know loop structures in order to avoid destroying them
657 in jump threading. Note that we still can e.g. thread through loop
658 headers to an exit edge, or through loop header to the loop body, assuming
659 that we update the loop info. */
660 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
662 /* We need accurate information regarding back edges in the CFG
663 for jump threading; this may include back edges that are not part of
665 mark_dfs_back_edges ();
667 /* Recursively walk the dominator tree optimizing statements. */
668 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
671 gimple_stmt_iterator gsi;
674 {for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
675 update_stmt_if_modified (gsi_stmt (gsi));
679 /* If we exposed any new variables, go ahead and put them into
680 SSA form now, before we handle jump threading. This simplifies
681 interactions between rewriting of _DECL nodes into SSA form
682 and rewriting SSA_NAME nodes into SSA form after block
683 duplication and CFG manipulation. */
684 update_ssa (TODO_update_ssa);
686 free_all_edge_infos ();
688 /* Thread jumps, creating duplicate blocks as needed. */
689 cfg_altered |= thread_through_all_blocks (first_pass_instance);
692 free_dominance_info (CDI_DOMINATORS);
694 /* Removal of statements may make some EH edges dead. Purge
695 such edges from the CFG as needed. */
696 if (!bitmap_empty_p (need_eh_cleanup))
701 /* Jump threading may have created forwarder blocks from blocks
702 needing EH cleanup; the new successor of these blocks, which
703 has inherited from the original block, needs the cleanup. */
704 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
706 basic_block bb = BASIC_BLOCK (i);
707 if (single_succ_p (bb) == 1
708 && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
710 bitmap_clear_bit (need_eh_cleanup, i);
711 bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index);
715 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
716 bitmap_zero (need_eh_cleanup);
719 /* Finally, remove everything except invariants in SSA_NAME_VALUE.
721 Long term we will be able to let everything in SSA_NAME_VALUE
722 persist. However, for now, we know this is the safe thing to do. */
723 for (i = 0; i < num_ssa_names; i++)
725 tree name = ssa_name (i);
731 value = SSA_NAME_VALUE (name);
732 if (value && !is_gimple_min_invariant (value))
733 SSA_NAME_VALUE (name) = NULL;
736 statistics_counter_event (cfun, "Redundant expressions eliminated",
738 statistics_counter_event (cfun, "Constants propagated",
739 opt_stats.num_const_prop);
740 statistics_counter_event (cfun, "Copies propagated",
741 opt_stats.num_copy_prop);
743 /* Debugging dumps. */
744 if (dump_file && (dump_flags & TDF_STATS))
745 dump_dominator_optimization_stats (dump_file);
747 loop_optimizer_finalize ();
749 /* Delete our main hashtable. */
750 htab_delete (avail_exprs);
752 /* And finalize the dominator walker. */
753 fini_walk_dominator_tree (&walk_data);
755 /* Free asserted bitmaps and stacks. */
756 BITMAP_FREE (need_eh_cleanup);
758 VEC_free (expr_hash_elt_t, heap, avail_exprs_stack);
759 VEC_free (tree, heap, const_and_copies_stack);
760 VEC_free (gimple_p, heap, stmts_to_rescan);
766 gate_dominator (void)
768 return flag_tree_dom != 0;
771 struct gimple_opt_pass pass_dominator =
776 gate_dominator, /* gate */
777 tree_ssa_dominator_optimize, /* execute */
780 0, /* static_pass_number */
781 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
782 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
783 0, /* properties_provided */
784 0, /* properties_destroyed */
785 0, /* todo_flags_start */
789 | TODO_verify_ssa /* todo_flags_finish */
794 /* Given a conditional statement CONDSTMT, convert the
795 condition to a canonical form. */
798 canonicalize_comparison (gimple condstmt)
804 gcc_assert (gimple_code (condstmt) == GIMPLE_COND);
806 op0 = gimple_cond_lhs (condstmt);
807 op1 = gimple_cond_rhs (condstmt);
809 code = gimple_cond_code (condstmt);
811 /* If it would be profitable to swap the operands, then do so to
812 canonicalize the statement, enabling better optimization.
814 By placing canonicalization of such expressions here we
815 transparently keep statements in canonical form, even
816 when the statement is modified. */
817 if (tree_swap_operands_p (op0, op1, false))
819 /* For relationals we need to swap the operands
820 and change the code. */
826 code = swap_tree_comparison (code);
828 gimple_cond_set_code (condstmt, code);
829 gimple_cond_set_lhs (condstmt, op1);
830 gimple_cond_set_rhs (condstmt, op0);
832 update_stmt (condstmt);
837 /* Initialize local stacks for this optimizer and record equivalences
838 upon entry to BB. Equivalences can come from the edge traversed to
839 reach BB or they may come from PHI nodes at the start of BB. */
842 dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
845 if (dump_file && (dump_flags & TDF_DETAILS))
846 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
848 /* Push a marker on the stacks of local information so that we know how
849 far to unwind when we finalize this block. */
850 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
851 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
853 record_equivalences_from_incoming_edge (bb);
855 /* PHI nodes can create equivalences too. */
856 record_equivalences_from_phis (bb);
859 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
860 LIMIT entries left in LOCALs. */
863 remove_local_expressions_from_table (void)
865 /* Remove all the expressions made available in this block. */
866 while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0)
868 struct expr_hash_elt element;
869 expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack);
876 /* This must precede the actual removal from the hash table,
877 as ELEMENT and the table entry may share a call argument
878 vector which will be freed during removal. */
879 if (dump_file && (dump_flags & TDF_DETAILS))
881 fprintf (dump_file, "<<<< ");
882 print_expr_hash_elt (dump_file, &element);
885 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
889 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
890 CONST_AND_COPIES to its original state, stopping when we hit a
894 restore_vars_to_original_value (void)
896 while (VEC_length (tree, const_and_copies_stack) > 0)
898 tree prev_value, dest;
900 dest = VEC_pop (tree, const_and_copies_stack);
905 if (dump_file && (dump_flags & TDF_DETAILS))
907 fprintf (dump_file, "<<<< COPY ");
908 print_generic_expr (dump_file, dest, 0);
909 fprintf (dump_file, " = ");
910 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0);
911 fprintf (dump_file, "\n");
914 prev_value = VEC_pop (tree, const_and_copies_stack);
915 SSA_NAME_VALUE (dest) = prev_value;
919 /* A trivial wrapper so that we can present the generic jump
920 threading code with a simple API for simplifying statements. */
922 simplify_stmt_for_jump_threading (gimple stmt,
923 gimple within_stmt ATTRIBUTE_UNUSED)
925 return lookup_avail_expr (stmt, false);
928 /* Wrapper for common code to attempt to thread an edge. For example,
929 it handles lazily building the dummy condition and the bookkeeping
930 when jump threading is successful. */
933 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
935 if (! walk_data->global_data)
938 gimple_build_cond (NE_EXPR,
939 integer_zero_node, integer_zero_node,
941 walk_data->global_data = dummy_cond;
944 thread_across_edge ((gimple) walk_data->global_data, e, false,
945 &const_and_copies_stack,
946 simplify_stmt_for_jump_threading);
949 /* We have finished processing the dominator children of BB, perform
950 any finalization actions in preparation for leaving this node in
951 the dominator tree. */
954 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
958 /* If we have an outgoing edge to a block with multiple incoming and
959 outgoing edges, then we may be able to thread the edge, i.e., we
960 may be able to statically determine which of the outgoing edges
961 will be traversed when the incoming edge from BB is traversed. */
962 if (single_succ_p (bb)
963 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
964 && potentially_threadable_block (single_succ (bb)))
966 dom_thread_across_edge (walk_data, single_succ_edge (bb));
968 else if ((last = last_stmt (bb))
969 && gimple_code (last) == GIMPLE_COND
970 && EDGE_COUNT (bb->succs) == 2
971 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
972 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
974 edge true_edge, false_edge;
976 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
978 /* Only try to thread the edge if it reaches a target block with
979 more than one predecessor and more than one successor. */
980 if (potentially_threadable_block (true_edge->dest))
982 struct edge_info *edge_info;
985 /* Push a marker onto the available expression stack so that we
986 unwind any expressions related to the TRUE arm before processing
987 the false arm below. */
988 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
989 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
991 edge_info = (struct edge_info *) true_edge->aux;
993 /* If we have info associated with this edge, record it into
994 our equivalence tables. */
997 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
998 tree lhs = edge_info->lhs;
999 tree rhs = edge_info->rhs;
1001 /* If we have a simple NAME = VALUE equivalence, record it. */
1002 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1003 record_const_or_copy (lhs, rhs);
1005 /* If we have 0 = COND or 1 = COND equivalences, record them
1006 into our expression hash tables. */
1007 if (cond_equivalences)
1008 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1009 record_cond (&cond_equivalences[i]);
1012 dom_thread_across_edge (walk_data, true_edge);
1014 /* And restore the various tables to their state before
1015 we threaded this edge. */
1016 remove_local_expressions_from_table ();
1019 /* Similarly for the ELSE arm. */
1020 if (potentially_threadable_block (false_edge->dest))
1022 struct edge_info *edge_info;
1025 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1026 edge_info = (struct edge_info *) false_edge->aux;
1028 /* If we have info associated with this edge, record it into
1029 our equivalence tables. */
1032 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1033 tree lhs = edge_info->lhs;
1034 tree rhs = edge_info->rhs;
1036 /* If we have a simple NAME = VALUE equivalence, record it. */
1037 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1038 record_const_or_copy (lhs, rhs);
1040 /* If we have 0 = COND or 1 = COND equivalences, record them
1041 into our expression hash tables. */
1042 if (cond_equivalences)
1043 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1044 record_cond (&cond_equivalences[i]);
1047 /* Now thread the edge. */
1048 dom_thread_across_edge (walk_data, false_edge);
1050 /* No need to remove local expressions from our tables
1051 or restore vars to their original value as that will
1052 be done immediately below. */
1056 remove_local_expressions_from_table ();
1057 restore_vars_to_original_value ();
1059 /* If we queued any statements to rescan in this block, then
1060 go ahead and rescan them now. */
1061 while (VEC_length (gimple_p, stmts_to_rescan) > 0)
1063 gimple *stmt_p = VEC_last (gimple_p, stmts_to_rescan);
1064 gimple stmt = *stmt_p;
1065 basic_block stmt_bb = gimple_bb (stmt);
1070 VEC_pop (gimple_p, stmts_to_rescan);
1071 pop_stmt_changes (stmt_p);
1075 /* PHI nodes can create equivalences too.
1077 Ignoring any alternatives which are the same as the result, if
1078 all the alternatives are equal, then the PHI node creates an
1082 record_equivalences_from_phis (basic_block bb)
1084 gimple_stmt_iterator gsi;
1086 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1088 gimple phi = gsi_stmt (gsi);
1090 tree lhs = gimple_phi_result (phi);
1094 for (i = 0; i < gimple_phi_num_args (phi); i++)
1096 tree t = gimple_phi_arg_def (phi, i);
1098 /* Ignore alternatives which are the same as our LHS. Since
1099 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1100 can simply compare pointers. */
1104 /* If we have not processed an alternative yet, then set
1105 RHS to this alternative. */
1108 /* If we have processed an alternative (stored in RHS), then
1109 see if it is equal to this one. If it isn't, then stop
1111 else if (! operand_equal_for_phi_arg_p (rhs, t))
1115 /* If we had no interesting alternatives, then all the RHS alternatives
1116 must have been the same as LHS. */
1120 /* If we managed to iterate through each PHI alternative without
1121 breaking out of the loop, then we have a PHI which may create
1122 a useful equivalence. We do not need to record unwind data for
1123 this, since this is a true assignment and not an equivalence
1124 inferred from a comparison. All uses of this ssa name are dominated
1125 by this assignment, so unwinding just costs time and space. */
1126 if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs))
1127 SSA_NAME_VALUE (lhs) = rhs;
1131 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1132 return that edge. Otherwise return NULL. */
1134 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1140 FOR_EACH_EDGE (e, ei, bb->preds)
1142 /* A loop back edge can be identified by the destination of
1143 the edge dominating the source of the edge. */
1144 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1147 /* If we have already seen a non-loop edge, then we must have
1148 multiple incoming non-loop edges and thus we return NULL. */
1152 /* This is the first non-loop incoming edge we have found. Record
1160 /* Record any equivalences created by the incoming edge to BB. If BB
1161 has more than one incoming edge, then no equivalence is created. */
1164 record_equivalences_from_incoming_edge (basic_block bb)
1168 struct edge_info *edge_info;
1170 /* If our parent block ended with a control statement, then we may be
1171 able to record some equivalences based on which outgoing edge from
1172 the parent was followed. */
1173 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1175 e = single_incoming_edge_ignoring_loop_edges (bb);
1177 /* If we had a single incoming edge from our parent block, then enter
1178 any data associated with the edge into our tables. */
1179 if (e && e->src == parent)
1183 edge_info = (struct edge_info *) e->aux;
1187 tree lhs = edge_info->lhs;
1188 tree rhs = edge_info->rhs;
1189 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1192 record_equality (lhs, rhs);
1194 if (cond_equivalences)
1195 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1196 record_cond (&cond_equivalences[i]);
1201 /* Dump SSA statistics on FILE. */
1204 dump_dominator_optimization_stats (FILE *file)
1206 fprintf (file, "Total number of statements: %6ld\n\n",
1207 opt_stats.num_stmts);
1208 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1209 opt_stats.num_exprs_considered);
1211 fprintf (file, "\nHash table statistics:\n");
1213 fprintf (file, " avail_exprs: ");
1214 htab_statistics (file, avail_exprs);
1218 /* Dump SSA statistics on stderr. */
1221 debug_dominator_optimization_stats (void)
1223 dump_dominator_optimization_stats (stderr);
1227 /* Dump statistics for the hash table HTAB. */
1230 htab_statistics (FILE *file, htab_t htab)
1232 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1233 (long) htab_size (htab),
1234 (long) htab_elements (htab),
1235 htab_collisions (htab));
1239 /* Enter condition equivalence into the expression hash table.
1240 This indicates that a conditional expression has a known
1244 record_cond (struct cond_equivalence *p)
1246 struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
1249 initialize_hash_element_from_expr (&p->cond, p->value, element);
1251 slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
1252 element->hash, INSERT);
1255 *slot = (void *) element;
1257 if (dump_file && (dump_flags & TDF_DETAILS))
1259 fprintf (dump_file, "1>>> ");
1260 print_expr_hash_elt (dump_file, element);
1263 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
1269 /* Build a cond_equivalence record indicating that the comparison
1270 CODE holds between operands OP0 and OP1. */
1273 build_and_record_new_cond (enum tree_code code,
1275 struct cond_equivalence *p)
1277 struct hashable_expr *cond = &p->cond;
1279 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
1281 cond->type = boolean_type_node;
1282 cond->kind = EXPR_BINARY;
1283 cond->ops.binary.op = code;
1284 cond->ops.binary.opnd0 = op0;
1285 cond->ops.binary.opnd1 = op1;
1287 p->value = boolean_true_node;
1290 /* Record that COND is true and INVERTED is false into the edge information
1291 structure. Also record that any conditions dominated by COND are true
1294 For example, if a < b is true, then a <= b must also be true. */
1297 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
1301 if (!COMPARISON_CLASS_P (cond))
1304 op0 = TREE_OPERAND (cond, 0);
1305 op1 = TREE_OPERAND (cond, 1);
1307 switch (TREE_CODE (cond))
1311 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1313 edge_info->max_cond_equivalences = 6;
1314 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 6);
1315 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1316 &edge_info->cond_equivalences[4]);
1317 build_and_record_new_cond (LTGT_EXPR, op0, op1,
1318 &edge_info->cond_equivalences[5]);
1322 edge_info->max_cond_equivalences = 4;
1323 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1326 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
1327 ? LE_EXPR : GE_EXPR),
1328 op0, op1, &edge_info->cond_equivalences[2]);
1329 build_and_record_new_cond (NE_EXPR, op0, op1,
1330 &edge_info->cond_equivalences[3]);
1335 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1337 edge_info->max_cond_equivalences = 3;
1338 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 3);
1339 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1340 &edge_info->cond_equivalences[2]);
1344 edge_info->max_cond_equivalences = 2;
1345 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1350 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1352 edge_info->max_cond_equivalences = 5;
1353 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 5);
1354 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1355 &edge_info->cond_equivalences[4]);
1359 edge_info->max_cond_equivalences = 4;
1360 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1362 build_and_record_new_cond (LE_EXPR, op0, op1,
1363 &edge_info->cond_equivalences[2]);
1364 build_and_record_new_cond (GE_EXPR, op0, op1,
1365 &edge_info->cond_equivalences[3]);
1368 case UNORDERED_EXPR:
1369 edge_info->max_cond_equivalences = 8;
1370 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 8);
1371 build_and_record_new_cond (NE_EXPR, op0, op1,
1372 &edge_info->cond_equivalences[2]);
1373 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1374 &edge_info->cond_equivalences[3]);
1375 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1376 &edge_info->cond_equivalences[4]);
1377 build_and_record_new_cond (UNEQ_EXPR, op0, op1,
1378 &edge_info->cond_equivalences[5]);
1379 build_and_record_new_cond (UNLT_EXPR, op0, op1,
1380 &edge_info->cond_equivalences[6]);
1381 build_and_record_new_cond (UNGT_EXPR, op0, op1,
1382 &edge_info->cond_equivalences[7]);
1387 edge_info->max_cond_equivalences = 4;
1388 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1389 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1390 ? UNLE_EXPR : UNGE_EXPR),
1391 op0, op1, &edge_info->cond_equivalences[2]);
1392 build_and_record_new_cond (NE_EXPR, op0, op1,
1393 &edge_info->cond_equivalences[3]);
1397 edge_info->max_cond_equivalences = 4;
1398 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1399 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1400 &edge_info->cond_equivalences[2]);
1401 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1402 &edge_info->cond_equivalences[3]);
1406 edge_info->max_cond_equivalences = 4;
1407 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1408 build_and_record_new_cond (NE_EXPR, op0, op1,
1409 &edge_info->cond_equivalences[2]);
1410 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1411 &edge_info->cond_equivalences[3]);
1415 edge_info->max_cond_equivalences = 2;
1416 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1420 /* Now store the original true and false conditions into the first
1422 initialize_expr_from_cond (cond, &edge_info->cond_equivalences[0].cond);
1423 edge_info->cond_equivalences[0].value = boolean_true_node;
1425 /* It is possible for INVERTED to be the negation of a comparison,
1426 and not a valid RHS or GIMPLE_COND condition. This happens because
1427 invert_truthvalue may return such an expression when asked to invert
1428 a floating-point comparison. These comparisons are not assumed to
1429 obey the trichotomy law. */
1430 initialize_expr_from_cond (inverted, &edge_info->cond_equivalences[1].cond);
1431 edge_info->cond_equivalences[1].value = boolean_false_node;
1434 /* A helper function for record_const_or_copy and record_equality.
1435 Do the work of recording the value and undo info. */
1438 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1440 SSA_NAME_VALUE (x) = y;
1442 if (dump_file && (dump_flags & TDF_DETAILS))
1444 fprintf (dump_file, "0>>> COPY ");
1445 print_generic_expr (dump_file, x, 0);
1446 fprintf (dump_file, " = ");
1447 print_generic_expr (dump_file, y, 0);
1448 fprintf (dump_file, "\n");
1451 VEC_reserve (tree, heap, const_and_copies_stack, 2);
1452 VEC_quick_push (tree, const_and_copies_stack, prev_x);
1453 VEC_quick_push (tree, const_and_copies_stack, x);
1456 /* Return the loop depth of the basic block of the defining statement of X.
1457 This number should not be treated as absolutely correct because the loop
1458 information may not be completely up-to-date when dom runs. However, it
1459 will be relatively correct, and as more passes are taught to keep loop info
1460 up to date, the result will become more and more accurate. */
1463 loop_depth_of_name (tree x)
1468 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1469 if (TREE_CODE (x) != SSA_NAME)
1472 /* Otherwise return the loop depth of the defining statement's bb.
1473 Note that there may not actually be a bb for this statement, if the
1474 ssa_name is live on entry. */
1475 defstmt = SSA_NAME_DEF_STMT (x);
1476 defbb = gimple_bb (defstmt);
1480 return defbb->loop_depth;
1483 /* Record that X is equal to Y in const_and_copies. Record undo
1484 information in the block-local vector. */
1487 record_const_or_copy (tree x, tree y)
1489 tree prev_x = SSA_NAME_VALUE (x);
1491 gcc_assert (TREE_CODE (x) == SSA_NAME);
1493 if (TREE_CODE (y) == SSA_NAME)
1495 tree tmp = SSA_NAME_VALUE (y);
1500 record_const_or_copy_1 (x, y, prev_x);
1503 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1504 This constrains the cases in which we may treat this as assignment. */
1507 record_equality (tree x, tree y)
1509 tree prev_x = NULL, prev_y = NULL;
1511 if (TREE_CODE (x) == SSA_NAME)
1512 prev_x = SSA_NAME_VALUE (x);
1513 if (TREE_CODE (y) == SSA_NAME)
1514 prev_y = SSA_NAME_VALUE (y);
1516 /* If one of the previous values is invariant, or invariant in more loops
1517 (by depth), 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 (is_gimple_min_invariant (y))
1522 else if (is_gimple_min_invariant (x)
1523 || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
1524 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1525 else if (prev_x && is_gimple_min_invariant (prev_x))
1526 x = y, y = prev_x, prev_x = prev_y;
1530 /* After the swapping, we must have one SSA_NAME. */
1531 if (TREE_CODE (x) != SSA_NAME)
1534 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1535 variable compared against zero. If we're honoring signed zeros,
1536 then we cannot record this value unless we know that the value is
1538 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1539 && (TREE_CODE (y) != REAL_CST
1540 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1543 record_const_or_copy_1 (x, y, prev_x);
1546 /* Returns true when STMT is a simple iv increment. It detects the
1547 following situation:
1549 i_1 = phi (..., i_2)
1550 i_2 = i_1 +/- ... */
1553 simple_iv_increment_p (gimple stmt)
1559 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1562 lhs = gimple_assign_lhs (stmt);
1563 if (TREE_CODE (lhs) != SSA_NAME)
1566 if (gimple_assign_rhs_code (stmt) != PLUS_EXPR
1567 && gimple_assign_rhs_code (stmt) != MINUS_EXPR)
1570 preinc = gimple_assign_rhs1 (stmt);
1572 if (TREE_CODE (preinc) != SSA_NAME)
1575 phi = SSA_NAME_DEF_STMT (preinc);
1576 if (gimple_code (phi) != GIMPLE_PHI)
1579 for (i = 0; i < gimple_phi_num_args (phi); i++)
1580 if (gimple_phi_arg_def (phi, i) == lhs)
1586 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1587 known value for that SSA_NAME (or NULL if no value is known).
1589 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1590 successors of BB. */
1593 cprop_into_successor_phis (basic_block bb)
1598 FOR_EACH_EDGE (e, ei, bb->succs)
1601 gimple_stmt_iterator gsi;
1603 /* If this is an abnormal edge, then we do not want to copy propagate
1604 into the PHI alternative associated with this edge. */
1605 if (e->flags & EDGE_ABNORMAL)
1608 gsi = gsi_start_phis (e->dest);
1609 if (gsi_end_p (gsi))
1613 for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1616 use_operand_p orig_p;
1618 gimple phi = gsi_stmt (gsi);
1620 /* The alternative may be associated with a constant, so verify
1621 it is an SSA_NAME before doing anything with it. */
1622 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1623 orig_val = get_use_from_ptr (orig_p);
1624 if (TREE_CODE (orig_val) != SSA_NAME)
1627 /* If we have *ORIG_P in our constant/copy table, then replace
1628 ORIG_P with its value in our constant/copy table. */
1629 new_val = SSA_NAME_VALUE (orig_val);
1631 && new_val != orig_val
1632 && (TREE_CODE (new_val) == SSA_NAME
1633 || is_gimple_min_invariant (new_val))
1634 && may_propagate_copy (orig_val, new_val))
1635 propagate_value (orig_p, new_val);
1640 /* We have finished optimizing BB, record any information implied by
1641 taking a specific outgoing edge from BB. */
1644 record_edge_info (basic_block bb)
1646 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1647 struct edge_info *edge_info;
1649 if (! gsi_end_p (gsi))
1651 gimple stmt = gsi_stmt (gsi);
1653 if (gimple_code (stmt) == GIMPLE_SWITCH)
1655 tree index = gimple_switch_index (stmt);
1657 if (TREE_CODE (index) == SSA_NAME)
1660 int n_labels = gimple_switch_num_labels (stmt);
1661 tree *info = XCNEWVEC (tree, last_basic_block);
1665 for (i = 0; i < n_labels; i++)
1667 tree label = gimple_switch_label (stmt, i);
1668 basic_block target_bb = label_to_block (CASE_LABEL (label));
1669 if (CASE_HIGH (label)
1670 || !CASE_LOW (label)
1671 || info[target_bb->index])
1672 info[target_bb->index] = error_mark_node;
1674 info[target_bb->index] = label;
1677 FOR_EACH_EDGE (e, ei, bb->succs)
1679 basic_block target_bb = e->dest;
1680 tree label = info[target_bb->index];
1682 if (label != NULL && label != error_mark_node)
1684 tree x = fold_convert (TREE_TYPE (index), CASE_LOW (label));
1685 edge_info = allocate_edge_info (e);
1686 edge_info->lhs = index;
1694 /* A COND_EXPR may create equivalences too. */
1695 if (gimple_code (stmt) == GIMPLE_COND)
1700 tree op0 = gimple_cond_lhs (stmt);
1701 tree op1 = gimple_cond_rhs (stmt);
1702 enum tree_code code = gimple_cond_code (stmt);
1704 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1706 /* Special case comparing booleans against a constant as we
1707 know the value of OP0 on both arms of the branch. i.e., we
1708 can record an equivalence for OP0 rather than COND. */
1709 if ((code == EQ_EXPR || code == NE_EXPR)
1710 && TREE_CODE (op0) == SSA_NAME
1711 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
1712 && is_gimple_min_invariant (op1))
1714 if (code == EQ_EXPR)
1716 edge_info = allocate_edge_info (true_edge);
1717 edge_info->lhs = op0;
1718 edge_info->rhs = (integer_zerop (op1)
1719 ? boolean_false_node
1720 : boolean_true_node);
1722 edge_info = allocate_edge_info (false_edge);
1723 edge_info->lhs = op0;
1724 edge_info->rhs = (integer_zerop (op1)
1726 : boolean_false_node);
1730 edge_info = allocate_edge_info (true_edge);
1731 edge_info->lhs = op0;
1732 edge_info->rhs = (integer_zerop (op1)
1734 : boolean_false_node);
1736 edge_info = allocate_edge_info (false_edge);
1737 edge_info->lhs = op0;
1738 edge_info->rhs = (integer_zerop (op1)
1739 ? boolean_false_node
1740 : boolean_true_node);
1743 else if (is_gimple_min_invariant (op0)
1744 && (TREE_CODE (op1) == SSA_NAME
1745 || is_gimple_min_invariant (op1)))
1747 tree cond = build2 (code, boolean_type_node, op0, op1);
1748 tree inverted = invert_truthvalue (cond);
1749 struct edge_info *edge_info;
1751 edge_info = allocate_edge_info (true_edge);
1752 record_conditions (edge_info, cond, inverted);
1754 if (code == EQ_EXPR)
1756 edge_info->lhs = op1;
1757 edge_info->rhs = op0;
1760 edge_info = allocate_edge_info (false_edge);
1761 record_conditions (edge_info, inverted, cond);
1763 if (code == NE_EXPR)
1765 edge_info->lhs = op1;
1766 edge_info->rhs = op0;
1770 else if (TREE_CODE (op0) == SSA_NAME
1771 && (is_gimple_min_invariant (op1)
1772 || TREE_CODE (op1) == SSA_NAME))
1774 tree cond = build2 (code, boolean_type_node, op0, op1);
1775 tree inverted = invert_truthvalue (cond);
1776 struct edge_info *edge_info;
1778 edge_info = allocate_edge_info (true_edge);
1779 record_conditions (edge_info, cond, inverted);
1781 if (code == EQ_EXPR)
1783 edge_info->lhs = op0;
1784 edge_info->rhs = op1;
1787 edge_info = allocate_edge_info (false_edge);
1788 record_conditions (edge_info, inverted, cond);
1790 if (TREE_CODE (cond) == NE_EXPR)
1792 edge_info->lhs = op0;
1793 edge_info->rhs = op1;
1798 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1802 /* Propagate information from BB to its outgoing edges.
1804 This can include equivalence information implied by control statements
1805 at the end of BB and const/copy propagation into PHIs in BB's
1806 successor blocks. */
1809 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1812 record_edge_info (bb);
1813 cprop_into_successor_phis (bb);
1816 /* Search for redundant computations in STMT. If any are found, then
1817 replace them with the variable holding the result of the computation.
1819 If safe, record this expression into the available expression hash
1823 eliminate_redundant_computations (gimple_stmt_iterator* gsi)
1828 bool retval = false;
1829 bool assigns_var_p = false;
1831 gimple stmt = gsi_stmt (*gsi);
1833 tree def = gimple_get_lhs (stmt);
1835 /* Certain expressions on the RHS can be optimized away, but can not
1836 themselves be entered into the hash tables. */
1838 || TREE_CODE (def) != SSA_NAME
1839 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1840 || gimple_vdef (stmt)
1841 /* Do not record equivalences for increments of ivs. This would create
1842 overlapping live ranges for a very questionable gain. */
1843 || simple_iv_increment_p (stmt))
1846 /* Check if the expression has been computed before. */
1847 cached_lhs = lookup_avail_expr (stmt, insert);
1849 opt_stats.num_exprs_considered++;
1851 /* Get the type of the expression we are trying to optimize. */
1852 if (is_gimple_assign (stmt))
1854 expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1855 assigns_var_p = true;
1857 else if (gimple_code (stmt) == GIMPLE_COND)
1858 expr_type = boolean_type_node;
1859 else if (is_gimple_call (stmt))
1861 gcc_assert (gimple_call_lhs (stmt));
1862 expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1863 assigns_var_p = true;
1865 else if (gimple_code (stmt) == GIMPLE_SWITCH)
1866 expr_type = TREE_TYPE (gimple_switch_index (stmt));
1873 /* It is safe to ignore types here since we have already done
1874 type checking in the hashing and equality routines. In fact
1875 type checking here merely gets in the way of constant
1876 propagation. Also, make sure that it is safe to propagate
1877 CACHED_LHS into the expression in STMT. */
1878 if ((TREE_CODE (cached_lhs) != SSA_NAME
1880 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1881 || may_propagate_copy_into_stmt (stmt, cached_lhs))
1883 #if defined ENABLE_CHECKING
1884 gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
1885 || is_gimple_min_invariant (cached_lhs));
1888 if (dump_file && (dump_flags & TDF_DETAILS))
1890 fprintf (dump_file, " Replaced redundant expr '");
1891 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1892 fprintf (dump_file, "' with '");
1893 print_generic_expr (dump_file, cached_lhs, dump_flags);
1894 fprintf (dump_file, "'\n");
1899 if (TREE_CODE (cached_lhs) == ADDR_EXPR
1900 || (POINTER_TYPE_P (expr_type)
1901 && is_gimple_min_invariant (cached_lhs)))
1905 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1906 cached_lhs = fold_convert (expr_type, cached_lhs);
1908 propagate_tree_value_into_stmt (gsi, cached_lhs);
1910 /* Since it is always necessary to mark the result as modified,
1911 perhaps we should move this into propagate_tree_value_into_stmt
1913 gimple_set_modified (gsi_stmt (*gsi), true);
1918 /* Return true if statement GS is an assignment that peforms a useless
1919 type conversion. It is is intended to be a tuples analog of function
1920 tree_ssa_useless_type_conversion. */
1923 gimple_assign_unary_useless_conversion_p (gimple gs)
1925 if (is_gimple_assign (gs)
1926 && (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs))
1927 || gimple_assign_rhs_code (gs) == VIEW_CONVERT_EXPR
1928 || gimple_assign_rhs_code (gs) == NON_LVALUE_EXPR))
1930 tree lhs_type = TREE_TYPE (gimple_assign_lhs (gs));
1931 tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (gs));
1932 return useless_type_conversion_p (lhs_type, rhs_type);
1938 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1939 the available expressions table or the const_and_copies table.
1940 Detect and record those equivalences. */
1941 /* We handle only very simple copy equivalences here. The heavy
1942 lifing is done by eliminate_redundant_computations. */
1945 record_equivalences_from_stmt (gimple stmt, int may_optimize_p)
1948 enum tree_code lhs_code;
1950 gcc_assert (is_gimple_assign (stmt));
1952 lhs = gimple_assign_lhs (stmt);
1953 lhs_code = TREE_CODE (lhs);
1955 if (lhs_code == SSA_NAME
1956 && (gimple_assign_single_p (stmt)
1957 || gimple_assign_unary_useless_conversion_p (stmt)))
1959 tree rhs = gimple_assign_rhs1 (stmt);
1961 /* Strip away any useless type conversions. */
1962 STRIP_USELESS_TYPE_CONVERSION (rhs);
1964 /* If the RHS of the assignment is a constant or another variable that
1965 may be propagated, register it in the CONST_AND_COPIES table. We
1966 do not need to record unwind data for this, since this is a true
1967 assignment and not an equivalence inferred from a comparison. All
1968 uses of this ssa name are dominated by this assignment, so unwinding
1969 just costs time and space. */
1971 && (TREE_CODE (rhs) == SSA_NAME
1972 || is_gimple_min_invariant (rhs)))
1974 if (dump_file && (dump_flags & TDF_DETAILS))
1976 fprintf (dump_file, "==== ASGN ");
1977 print_generic_expr (dump_file, lhs, 0);
1978 fprintf (dump_file, " = ");
1979 print_generic_expr (dump_file, rhs, 0);
1980 fprintf (dump_file, "\n");
1983 SSA_NAME_VALUE (lhs) = rhs;
1987 /* A memory store, even an aliased store, creates a useful
1988 equivalence. By exchanging the LHS and RHS, creating suitable
1989 vops and recording the result in the available expression table,
1990 we may be able to expose more redundant loads. */
1991 if (!gimple_has_volatile_ops (stmt)
1992 && gimple_references_memory_p (stmt)
1993 && gimple_assign_single_p (stmt)
1994 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1995 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1996 && !is_gimple_reg (lhs))
1998 tree rhs = gimple_assign_rhs1 (stmt);
2001 /* Build a new statement with the RHS and LHS exchanged. */
2002 if (TREE_CODE (rhs) == SSA_NAME)
2004 /* NOTE tuples. The call to gimple_build_assign below replaced
2005 a call to build_gimple_modify_stmt, which did not set the
2006 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
2007 may cause an SSA validation failure, as the LHS may be a
2008 default-initialized name and should have no definition. I'm
2009 a bit dubious of this, as the artificial statement that we
2010 generate here may in fact be ill-formed, but it is simply
2011 used as an internal device in this pass, and never becomes
2013 gimple defstmt = SSA_NAME_DEF_STMT (rhs);
2014 new_stmt = gimple_build_assign (rhs, lhs);
2015 SSA_NAME_DEF_STMT (rhs) = defstmt;
2018 new_stmt = gimple_build_assign (rhs, lhs);
2020 gimple_set_vuse (new_stmt, gimple_vdef (stmt));
2022 /* Finally enter the statement into the available expression
2024 lookup_avail_expr (new_stmt, true);
2028 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2029 CONST_AND_COPIES. */
2032 cprop_operand (gimple stmt, use_operand_p op_p)
2034 bool may_have_exposed_new_symbols = false;
2036 tree op = USE_FROM_PTR (op_p);
2038 /* If the operand has a known constant value or it is known to be a
2039 copy of some other variable, use the value or copy stored in
2040 CONST_AND_COPIES. */
2041 val = SSA_NAME_VALUE (op);
2042 if (val && val != op)
2044 /* Do not change the base variable in the virtual operand
2045 tables. That would make it impossible to reconstruct
2046 the renamed virtual operand if we later modify this
2047 statement. Also only allow the new value to be an SSA_NAME
2048 for propagation into virtual operands. */
2049 if (!is_gimple_reg (op)
2050 && (TREE_CODE (val) != SSA_NAME
2051 || is_gimple_reg (val)
2052 || get_virtual_var (val) != get_virtual_var (op)))
2055 /* Do not replace hard register operands in asm statements. */
2056 if (gimple_code (stmt) == GIMPLE_ASM
2057 && !may_propagate_copy_into_asm (op))
2060 /* Certain operands are not allowed to be copy propagated due
2061 to their interaction with exception handling and some GCC
2063 if (!may_propagate_copy (op, val))
2066 /* Do not propagate addresses that point to volatiles into memory
2067 stmts without volatile operands. */
2068 if (POINTER_TYPE_P (TREE_TYPE (val))
2069 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val)))
2070 && gimple_has_mem_ops (stmt)
2071 && !gimple_has_volatile_ops (stmt))
2074 /* Do not propagate copies if the propagated value is at a deeper loop
2075 depth than the propagatee. Otherwise, this may move loop variant
2076 variables outside of their loops and prevent coalescing
2077 opportunities. If the value was loop invariant, it will be hoisted
2078 by LICM and exposed for copy propagation. */
2079 if (loop_depth_of_name (val) > loop_depth_of_name (op))
2083 if (dump_file && (dump_flags & TDF_DETAILS))
2085 fprintf (dump_file, " Replaced '");
2086 print_generic_expr (dump_file, op, dump_flags);
2087 fprintf (dump_file, "' with %s '",
2088 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2089 print_generic_expr (dump_file, val, dump_flags);
2090 fprintf (dump_file, "'\n");
2093 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2094 that we may have exposed a new symbol for SSA renaming. */
2095 if (TREE_CODE (val) == ADDR_EXPR
2096 || (POINTER_TYPE_P (TREE_TYPE (op))
2097 && is_gimple_min_invariant (val)))
2098 may_have_exposed_new_symbols = true;
2100 if (TREE_CODE (val) != SSA_NAME)
2101 opt_stats.num_const_prop++;
2103 opt_stats.num_copy_prop++;
2105 propagate_value (op_p, val);
2107 /* And note that we modified this statement. This is now
2108 safe, even if we changed virtual operands since we will
2109 rescan the statement and rewrite its operands again. */
2110 gimple_set_modified (stmt, true);
2112 return may_have_exposed_new_symbols;
2115 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2116 known value for that SSA_NAME (or NULL if no value is known).
2118 Propagate values from CONST_AND_COPIES into the uses, vuses and
2119 vdef_ops of STMT. */
2122 cprop_into_stmt (gimple stmt)
2124 bool may_have_exposed_new_symbols = false;
2128 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
2130 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
2131 may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
2134 return may_have_exposed_new_symbols;
2137 /* Optimize the statement pointed to by iterator SI.
2139 We try to perform some simplistic global redundancy elimination and
2140 constant propagation:
2142 1- To detect global redundancy, we keep track of expressions that have
2143 been computed in this block and its dominators. If we find that the
2144 same expression is computed more than once, we eliminate repeated
2145 computations by using the target of the first one.
2147 2- Constant values and copy assignments. This is used to do very
2148 simplistic constant and copy propagation. When a constant or copy
2149 assignment is found, we map the value on the RHS of the assignment to
2150 the variable in the LHS in the CONST_AND_COPIES table. */
2153 optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2154 basic_block bb, gimple_stmt_iterator si)
2156 gimple stmt, old_stmt;
2157 bool may_optimize_p;
2158 bool may_have_exposed_new_symbols;
2159 bool modified_p = false;
2161 old_stmt = stmt = gsi_stmt (si);
2163 if (gimple_code (stmt) == GIMPLE_COND)
2164 canonicalize_comparison (stmt);
2166 update_stmt_if_modified (stmt);
2167 opt_stats.num_stmts++;
2168 push_stmt_changes (gsi_stmt_ptr (&si));
2170 if (dump_file && (dump_flags & TDF_DETAILS))
2172 fprintf (dump_file, "Optimizing statement ");
2173 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2176 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2177 may_have_exposed_new_symbols = cprop_into_stmt (stmt);
2179 /* If the statement has been modified with constant replacements,
2180 fold its RHS before checking for redundant computations. */
2181 if (gimple_modified_p (stmt))
2185 /* Try to fold the statement making sure that STMT is kept
2187 if (fold_stmt (&si))
2189 stmt = gsi_stmt (si);
2191 if (dump_file && (dump_flags & TDF_DETAILS))
2193 fprintf (dump_file, " Folded to: ");
2194 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2198 /* We only need to consider cases that can yield a gimple operand. */
2199 if (gimple_assign_single_p (stmt))
2200 rhs = gimple_assign_rhs1 (stmt);
2201 else if (gimple_code (stmt) == GIMPLE_GOTO)
2202 rhs = gimple_goto_dest (stmt);
2203 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2204 /* This should never be an ADDR_EXPR. */
2205 rhs = gimple_switch_index (stmt);
2207 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
2208 recompute_tree_invariant_for_addr_expr (rhs);
2210 /* Constant/copy propagation above may change the set of
2211 virtual operands associated with this statement. Folding
2212 may remove the need for some virtual operands.
2214 Indicate we will need to rescan and rewrite the statement. */
2215 may_have_exposed_new_symbols = true;
2216 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2217 even if fold_stmt updated the stmt already and thus cleared
2218 gimple_modified_p flag on it. */
2222 /* Check for redundant computations. Do this optimization only
2223 for assignments that have no volatile ops and conditionals. */
2224 may_optimize_p = (!gimple_has_volatile_ops (stmt)
2225 && ((is_gimple_assign (stmt)
2226 && !gimple_rhs_has_side_effects (stmt))
2227 || (is_gimple_call (stmt)
2228 && gimple_call_lhs (stmt) != NULL_TREE
2229 && !gimple_rhs_has_side_effects (stmt))
2230 || gimple_code (stmt) == GIMPLE_COND
2231 || gimple_code (stmt) == GIMPLE_SWITCH));
2235 may_have_exposed_new_symbols |= eliminate_redundant_computations (&si);
2236 stmt = gsi_stmt (si);
2239 /* Record any additional equivalences created by this statement. */
2240 if (is_gimple_assign (stmt))
2241 record_equivalences_from_stmt (stmt, may_optimize_p);
2243 /* If STMT is a COND_EXPR and it was modified, then we may know
2244 where it goes. If that is the case, then mark the CFG as altered.
2246 This will cause us to later call remove_unreachable_blocks and
2247 cleanup_tree_cfg when it is safe to do so. It is not safe to
2248 clean things up here since removal of edges and such can trigger
2249 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2252 That's all fine and good, except that once SSA_NAMEs are released
2253 to the manager, we must not call create_ssa_name until all references
2254 to released SSA_NAMEs have been eliminated.
2256 All references to the deleted SSA_NAMEs can not be eliminated until
2257 we remove unreachable blocks.
2259 We can not remove unreachable blocks until after we have completed
2260 any queued jump threading.
2262 We can not complete any queued jump threads until we have taken
2263 appropriate variables out of SSA form. Taking variables out of
2264 SSA form can call create_ssa_name and thus we lose.
2266 Ultimately I suspect we're going to need to change the interface
2267 into the SSA_NAME manager. */
2268 if (gimple_modified_p (stmt) || modified_p)
2272 if (gimple_code (stmt) == GIMPLE_COND)
2273 val = fold_binary (gimple_cond_code (stmt), boolean_type_node,
2274 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
2275 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2276 val = gimple_switch_index (stmt);
2278 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
2281 /* If we simplified a statement in such a way as to be shown that it
2282 cannot trap, update the eh information and the cfg to match. */
2283 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
2285 bitmap_set_bit (need_eh_cleanup, bb->index);
2286 if (dump_file && (dump_flags & TDF_DETAILS))
2287 fprintf (dump_file, " Flagged to clear EH edges.\n");
2291 if (may_have_exposed_new_symbols)
2293 /* Queue the statement to be re-scanned after all the
2294 AVAIL_EXPRS have been processed. The change buffer stack for
2295 all the pushed statements will be processed when this queue
2297 VEC_safe_push (gimple_p, heap, stmts_to_rescan, gsi_stmt_ptr (&si));
2301 /* Otherwise, just discard the recently pushed change buffer. If
2302 not, the STMTS_TO_RESCAN queue will get out of synch with the
2303 change buffer stack. */
2304 discard_stmt_changes (gsi_stmt_ptr (&si));
2308 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
2309 If found, return its LHS. Otherwise insert STMT in the table and
2312 Also, when an expression is first inserted in the table, it is also
2313 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
2314 we finish processing this block and its children. */
2317 lookup_avail_expr (gimple stmt, bool insert)
2322 struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
2324 /* Get LHS of assignment or call, else NULL_TREE. */
2325 lhs = gimple_get_lhs (stmt);
2327 initialize_hash_element (stmt, lhs, element);
2329 if (dump_file && (dump_flags & TDF_DETAILS))
2331 fprintf (dump_file, "LKUP ");
2332 print_expr_hash_elt (dump_file, element);
2335 /* Don't bother remembering constant assignments and copy operations.
2336 Constants and copy operations are handled by the constant/copy propagator
2337 in optimize_stmt. */
2338 if (element->expr.kind == EXPR_SINGLE
2339 && (TREE_CODE (element->expr.ops.single.rhs) == SSA_NAME
2340 || is_gimple_min_invariant (element->expr.ops.single.rhs)))
2346 /* Finally try to find the expression in the main expression hash table. */
2347 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
2348 (insert ? INSERT : NO_INSERT));
2357 *slot = (void *) element;
2359 if (dump_file && (dump_flags & TDF_DETAILS))
2361 fprintf (dump_file, "2>>> ");
2362 print_expr_hash_elt (dump_file, element);
2365 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
2369 /* Extract the LHS of the assignment so that it can be used as the current
2370 definition of another variable. */
2371 lhs = ((struct expr_hash_elt *)*slot)->lhs;
2373 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2374 use the value from the const_and_copies table. */
2375 if (TREE_CODE (lhs) == SSA_NAME)
2377 temp = SSA_NAME_VALUE (lhs);
2384 if (dump_file && (dump_flags & TDF_DETAILS))
2386 fprintf (dump_file, "FIND: ");
2387 print_generic_expr (dump_file, lhs, 0);
2388 fprintf (dump_file, "\n");
2394 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number
2395 for expressions using the code of the expression and the SSA numbers of
2399 avail_expr_hash (const void *p)
2401 gimple stmt = ((const struct expr_hash_elt *)p)->stmt;
2402 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr;
2406 val = iterative_hash_hashable_expr (expr, val);
2408 /* If the hash table entry is not associated with a statement, then we
2409 can just hash the expression and not worry about virtual operands
2414 /* Add the SSA version numbers of the vuse operand. This is important
2415 because compound variables like arrays are not renamed in the
2416 operands. Rather, the rename is done on the virtual variable
2417 representing all the elements of the array. */
2418 if ((vuse = gimple_vuse (stmt)))
2419 val = iterative_hash_expr (vuse, val);
2425 real_avail_expr_hash (const void *p)
2427 return ((const struct expr_hash_elt *)p)->hash;
2431 avail_expr_eq (const void *p1, const void *p2)
2433 gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
2434 const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr;
2435 const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp;
2436 gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
2437 const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr;
2438 const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp;
2440 /* This case should apply only when removing entries from the table. */
2441 if (stamp1 == stamp2)
2445 We add stmts to a hash table and them modify them. To detect the case
2446 that we modify a stmt and then search for it, we assume that the hash
2447 is always modified by that change.
2448 We have to fully check why this doesn't happen on trunk or rewrite
2449 this in a more reliable (and easier to understand) way. */
2450 if (((const struct expr_hash_elt *)p1)->hash
2451 != ((const struct expr_hash_elt *)p2)->hash)
2454 /* In case of a collision, both RHS have to be identical and have the
2455 same VUSE operands. */
2456 if (hashable_expr_equal_p (expr1, expr2)
2457 && types_compatible_p (expr1->type, expr2->type))
2459 /* Note that STMT1 and/or STMT2 may be NULL. */
2460 return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE)
2461 == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE));
2467 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2468 up degenerate PHIs created by or exposed by jump threading. */
2470 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2474 degenerate_phi_result (gimple phi)
2476 tree lhs = gimple_phi_result (phi);
2480 /* Ignoring arguments which are the same as LHS, if all the remaining
2481 arguments are the same, then the PHI is a degenerate and has the
2482 value of that common argument. */
2483 for (i = 0; i < gimple_phi_num_args (phi); i++)
2485 tree arg = gimple_phi_arg_def (phi, i);
2491 else if (!operand_equal_p (arg, val, 0))
2494 return (i == gimple_phi_num_args (phi) ? val : NULL);
2497 /* Given a statement STMT, which is either a PHI node or an assignment,
2498 remove it from the IL. */
2501 remove_stmt_or_phi (gimple stmt)
2503 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
2505 if (gimple_code (stmt) == GIMPLE_PHI)
2506 remove_phi_node (&gsi, true);
2509 gsi_remove (&gsi, true);
2510 release_defs (stmt);
2514 /* Given a statement STMT, which is either a PHI node or an assignment,
2515 return the "rhs" of the node, in the case of a non-degenerate
2516 phi, NULL is returned. */
2519 get_rhs_or_phi_arg (gimple stmt)
2521 if (gimple_code (stmt) == GIMPLE_PHI)
2522 return degenerate_phi_result (stmt);
2523 else if (gimple_assign_single_p (stmt))
2524 return gimple_assign_rhs1 (stmt);
2530 /* Given a statement STMT, which is either a PHI node or an assignment,
2531 return the "lhs" of the node. */
2534 get_lhs_or_phi_result (gimple stmt)
2536 if (gimple_code (stmt) == GIMPLE_PHI)
2537 return gimple_phi_result (stmt);
2538 else if (is_gimple_assign (stmt))
2539 return gimple_assign_lhs (stmt);
2544 /* Propagate RHS into all uses of LHS (when possible).
2546 RHS and LHS are derived from STMT, which is passed in solely so
2547 that we can remove it if propagation is successful.
2549 When propagating into a PHI node or into a statement which turns
2550 into a trivial copy or constant initialization, set the
2551 appropriate bit in INTERESTING_NAMEs so that we will visit those
2552 nodes as well in an effort to pick up secondary optimization
2556 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
2558 /* First verify that propagation is valid and isn't going to move a
2559 loop variant variable outside its loop. */
2560 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
2561 && (TREE_CODE (rhs) != SSA_NAME
2562 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
2563 && may_propagate_copy (lhs, rhs)
2564 && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
2566 use_operand_p use_p;
2567 imm_use_iterator iter;
2572 if (dump_file && (dump_flags & TDF_DETAILS))
2574 fprintf (dump_file, " Replacing '");
2575 print_generic_expr (dump_file, lhs, dump_flags);
2576 fprintf (dump_file, "' with %s '",
2577 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
2578 print_generic_expr (dump_file, rhs, dump_flags);
2579 fprintf (dump_file, "'\n");
2582 /* Walk over every use of LHS and try to replace the use with RHS.
2583 At this point the only reason why such a propagation would not
2584 be successful would be if the use occurs in an ASM_EXPR. */
2585 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
2588 /* It's not always safe to propagate into an ASM_EXPR. */
2589 if (gimple_code (use_stmt) == GIMPLE_ASM
2590 && ! may_propagate_copy_into_asm (lhs))
2597 if (dump_file && (dump_flags & TDF_DETAILS))
2599 fprintf (dump_file, " Original statement:");
2600 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2603 push_stmt_changes (&use_stmt);
2605 /* Propagate the RHS into this use of the LHS. */
2606 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2607 propagate_value (use_p, rhs);
2609 /* Special cases to avoid useless calls into the folding
2610 routines, operand scanning, etc.
2612 First, propagation into a PHI may cause the PHI to become
2613 a degenerate, so mark the PHI as interesting. No other
2614 actions are necessary.
2616 Second, if we're propagating a virtual operand and the
2617 propagation does not change the underlying _DECL node for
2618 the virtual operand, then no further actions are necessary. */
2619 if (gimple_code (use_stmt) == GIMPLE_PHI
2620 || (! is_gimple_reg (lhs)
2621 && TREE_CODE (rhs) == SSA_NAME
2622 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
2625 if (dump_file && (dump_flags & TDF_DETAILS))
2627 fprintf (dump_file, " Updated statement:");
2628 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2631 /* Propagation into a PHI may expose new degenerate PHIs,
2632 so mark the result of the PHI as interesting. */
2633 if (gimple_code (use_stmt) == GIMPLE_PHI)
2635 tree result = get_lhs_or_phi_result (use_stmt);
2636 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2639 discard_stmt_changes (&use_stmt);
2643 /* From this point onward we are propagating into a
2644 real statement. Folding may (or may not) be possible,
2645 we may expose new operands, expose dead EH edges,
2647 /* NOTE tuples. In the tuples world, fold_stmt_inplace
2648 cannot fold a call that simplifies to a constant,
2649 because the GIMPLE_CALL must be replaced by a
2650 GIMPLE_ASSIGN, and there is no way to effect such a
2651 transformation in-place. We might want to consider
2652 using the more general fold_stmt here. */
2653 fold_stmt_inplace (use_stmt);
2655 /* Sometimes propagation can expose new operands to the
2656 renamer. Note this will call update_stmt at the
2657 appropriate time. */
2658 pop_stmt_changes (&use_stmt);
2661 if (dump_file && (dump_flags & TDF_DETAILS))
2663 fprintf (dump_file, " Updated statement:");
2664 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2667 /* If we replaced a variable index with a constant, then
2668 we would need to update the invariant flag for ADDR_EXPRs. */
2669 if (gimple_assign_single_p (use_stmt)
2670 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
2671 recompute_tree_invariant_for_addr_expr
2672 (gimple_assign_rhs1 (use_stmt));
2674 /* If we cleaned up EH information from the statement,
2675 mark its containing block as needing EH cleanups. */
2676 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
2678 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
2679 if (dump_file && (dump_flags & TDF_DETAILS))
2680 fprintf (dump_file, " Flagged to clear EH edges.\n");
2683 /* Propagation may expose new trivial copy/constant propagation
2685 if (gimple_assign_single_p (use_stmt)
2686 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
2687 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
2688 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
2690 tree result = get_lhs_or_phi_result (use_stmt);
2691 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2694 /* Propagation into these nodes may make certain edges in
2695 the CFG unexecutable. We want to identify them as PHI nodes
2696 at the destination of those unexecutable edges may become
2698 else if (gimple_code (use_stmt) == GIMPLE_COND
2699 || gimple_code (use_stmt) == GIMPLE_SWITCH
2700 || gimple_code (use_stmt) == GIMPLE_GOTO)
2704 if (gimple_code (use_stmt) == GIMPLE_COND)
2705 val = fold_binary (gimple_cond_code (use_stmt),
2707 gimple_cond_lhs (use_stmt),
2708 gimple_cond_rhs (use_stmt));
2709 else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
2710 val = gimple_switch_index (use_stmt);
2712 val = gimple_goto_dest (use_stmt);
2714 if (val && is_gimple_min_invariant (val))
2716 basic_block bb = gimple_bb (use_stmt);
2717 edge te = find_taken_edge (bb, val);
2720 gimple_stmt_iterator gsi, psi;
2722 /* Remove all outgoing edges except TE. */
2723 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
2727 /* Mark all the PHI nodes at the destination of
2728 the unexecutable edge as interesting. */
2729 for (psi = gsi_start_phis (e->dest);
2733 gimple phi = gsi_stmt (psi);
2735 tree result = gimple_phi_result (phi);
2736 int version = SSA_NAME_VERSION (result);
2738 bitmap_set_bit (interesting_names, version);
2741 te->probability += e->probability;
2743 te->count += e->count;
2751 gsi = gsi_last_bb (gimple_bb (use_stmt));
2752 gsi_remove (&gsi, true);
2754 /* And fixup the flags on the single remaining edge. */
2755 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
2756 te->flags &= ~EDGE_ABNORMAL;
2757 te->flags |= EDGE_FALLTHRU;
2758 if (te->probability > REG_BR_PROB_BASE)
2759 te->probability = REG_BR_PROB_BASE;
2764 /* Ensure there is nothing else to do. */
2765 gcc_assert (!all || has_zero_uses (lhs));
2767 /* If we were able to propagate away all uses of LHS, then
2768 we can remove STMT. */
2770 remove_stmt_or_phi (stmt);
2774 /* STMT is either a PHI node (potentially a degenerate PHI node) or
2775 a statement that is a trivial copy or constant initialization.
2777 Attempt to eliminate T by propagating its RHS into all uses of
2778 its LHS. This may in turn set new bits in INTERESTING_NAMES
2779 for nodes we want to revisit later.
2781 All exit paths should clear INTERESTING_NAMES for the result
2785 eliminate_const_or_copy (gimple stmt, bitmap interesting_names)
2787 tree lhs = get_lhs_or_phi_result (stmt);
2789 int version = SSA_NAME_VERSION (lhs);
2791 /* If the LHS of this statement or PHI has no uses, then we can
2792 just eliminate it. This can occur if, for example, the PHI
2793 was created by block duplication due to threading and its only
2794 use was in the conditional at the end of the block which was
2796 if (has_zero_uses (lhs))
2798 bitmap_clear_bit (interesting_names, version);
2799 remove_stmt_or_phi (stmt);
2803 /* Get the RHS of the assignment or PHI node if the PHI is a
2805 rhs = get_rhs_or_phi_arg (stmt);
2808 bitmap_clear_bit (interesting_names, version);
2812 propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
2814 /* Note that STMT may well have been deleted by now, so do
2815 not access it, instead use the saved version # to clear
2816 T's entry in the worklist. */
2817 bitmap_clear_bit (interesting_names, version);
2820 /* The first phase in degenerate PHI elimination.
2822 Eliminate the degenerate PHIs in BB, then recurse on the
2823 dominator children of BB. */
2826 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names)
2828 gimple_stmt_iterator gsi;
2831 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2833 gimple phi = gsi_stmt (gsi);
2835 eliminate_const_or_copy (phi, interesting_names);
2838 /* Recurse into the dominator children of BB. */
2839 for (son = first_dom_son (CDI_DOMINATORS, bb);
2841 son = next_dom_son (CDI_DOMINATORS, son))
2842 eliminate_degenerate_phis_1 (son, interesting_names);
2846 /* A very simple pass to eliminate degenerate PHI nodes from the
2847 IL. This is meant to be fast enough to be able to be run several
2848 times in the optimization pipeline.
2850 Certain optimizations, particularly those which duplicate blocks
2851 or remove edges from the CFG can create or expose PHIs which are
2852 trivial copies or constant initializations.
2854 While we could pick up these optimizations in DOM or with the
2855 combination of copy-prop and CCP, those solutions are far too
2856 heavy-weight for our needs.
2858 This implementation has two phases so that we can efficiently
2859 eliminate the first order degenerate PHIs and second order
2862 The first phase performs a dominator walk to identify and eliminate
2863 the vast majority of the degenerate PHIs. When a degenerate PHI
2864 is identified and eliminated any affected statements or PHIs
2865 are put on a worklist.
2867 The second phase eliminates degenerate PHIs and trivial copies
2868 or constant initializations using the worklist. This is how we
2869 pick up the secondary optimization opportunities with minimal
2873 eliminate_degenerate_phis (void)
2875 bitmap interesting_names;
2876 bitmap interesting_names1;
2878 /* Bitmap of blocks which need EH information updated. We can not
2879 update it on-the-fly as doing so invalidates the dominator tree. */
2880 need_eh_cleanup = BITMAP_ALLOC (NULL);
2882 /* INTERESTING_NAMES is effectively our worklist, indexed by
2885 A set bit indicates that the statement or PHI node which
2886 defines the SSA_NAME should be (re)examined to determine if
2887 it has become a degenerate PHI or trivial const/copy propagation
2890 Experiments have show we generally get better compilation
2891 time behavior with bitmaps rather than sbitmaps. */
2892 interesting_names = BITMAP_ALLOC (NULL);
2893 interesting_names1 = BITMAP_ALLOC (NULL);
2895 calculate_dominance_info (CDI_DOMINATORS);
2896 cfg_altered = false;
2898 /* First phase. Eliminate degenerate PHIs via a dominator
2901 Experiments have indicated that we generally get better
2902 compile-time behavior by visiting blocks in the first
2903 phase in dominator order. Presumably this is because walking
2904 in dominator order leaves fewer PHIs for later examination
2905 by the worklist phase. */
2906 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
2908 /* Second phase. Eliminate second order degenerate PHIs as well
2909 as trivial copies or constant initializations identified by
2910 the first phase or this phase. Basically we keep iterating
2911 until our set of INTERESTING_NAMEs is empty. */
2912 while (!bitmap_empty_p (interesting_names))
2917 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2918 changed during the loop. Copy it to another bitmap and
2920 bitmap_copy (interesting_names1, interesting_names);
2922 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
2924 tree name = ssa_name (i);
2926 /* Ignore SSA_NAMEs that have been released because
2927 their defining statement was deleted (unreachable). */
2929 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
2935 free_dominance_info (CDI_DOMINATORS);
2937 /* Propagation of const and copies may make some EH edges dead. Purge
2938 such edges from the CFG as needed. */
2939 if (!bitmap_empty_p (need_eh_cleanup))
2941 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
2942 BITMAP_FREE (need_eh_cleanup);
2945 BITMAP_FREE (interesting_names);
2946 BITMAP_FREE (interesting_names1);
2950 struct gimple_opt_pass pass_phi_only_cprop =
2954 "phicprop", /* name */
2955 gate_dominator, /* gate */
2956 eliminate_degenerate_phis, /* execute */
2959 0, /* static_pass_number */
2960 TV_TREE_PHI_CPROP, /* tv_id */
2961 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2962 0, /* properties_provided */
2963 0, /* properties_destroyed */
2964 0, /* todo_flags_start */
2970 | TODO_update_ssa /* todo_flags_finish */