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 expr->type = NULL_TREE;
230 switch (get_gimple_rhs_class (subcode))
232 case GIMPLE_SINGLE_RHS:
233 expr->kind = EXPR_SINGLE;
234 expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
236 case GIMPLE_UNARY_RHS:
237 expr->kind = EXPR_UNARY;
238 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
239 expr->ops.unary.op = subcode;
240 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
242 case GIMPLE_BINARY_RHS:
243 expr->kind = EXPR_BINARY;
244 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
245 expr->ops.binary.op = subcode;
246 expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
247 expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
253 else if (code == GIMPLE_COND)
255 expr->type = boolean_type_node;
256 expr->kind = EXPR_BINARY;
257 expr->ops.binary.op = gimple_cond_code (stmt);
258 expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
259 expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
261 else if (code == GIMPLE_CALL)
263 size_t nargs = gimple_call_num_args (stmt);
266 gcc_assert (gimple_call_lhs (stmt));
268 expr->type = TREE_TYPE (gimple_call_lhs (stmt));
269 expr->kind = EXPR_CALL;
270 expr->ops.call.fn = gimple_call_fn (stmt);
272 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
273 expr->ops.call.pure = true;
275 expr->ops.call.pure = false;
277 expr->ops.call.nargs = nargs;
278 expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree));
279 for (i = 0; i < nargs; i++)
280 expr->ops.call.args[i] = gimple_call_arg (stmt, i);
282 else if (code == GIMPLE_SWITCH)
284 expr->type = TREE_TYPE (gimple_switch_index (stmt));
285 expr->kind = EXPR_SINGLE;
286 expr->ops.single.rhs = gimple_switch_index (stmt);
288 else if (code == GIMPLE_GOTO)
290 expr->type = TREE_TYPE (gimple_goto_dest (stmt));
291 expr->kind = EXPR_SINGLE;
292 expr->ops.single.rhs = gimple_goto_dest (stmt);
298 element->stmt = stmt;
299 element->hash = avail_expr_hash (element);
300 element->stamp = element;
303 /* Given a conditional expression COND as a tree, initialize
304 a hashable_expr expression EXPR. The conditional must be a
305 comparison or logical negation. A constant or a variable is
309 initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
311 expr->type = boolean_type_node;
313 if (COMPARISON_CLASS_P (cond))
315 expr->kind = EXPR_BINARY;
316 expr->ops.binary.op = TREE_CODE (cond);
317 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
318 expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
320 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
322 expr->kind = EXPR_UNARY;
323 expr->ops.unary.op = TRUTH_NOT_EXPR;
324 expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
330 /* Given a hashable_expr expression EXPR and an LHS,
331 initialize the hash table element pointed to by ELEMENT. */
334 initialize_hash_element_from_expr (struct hashable_expr *expr,
336 struct expr_hash_elt *element)
338 element->expr = *expr;
340 element->stmt = NULL;
341 element->hash = avail_expr_hash (element);
342 element->stamp = element;
345 /* Compare two hashable_expr structures for equivalence.
346 They are considered equivalent when the the expressions
347 they denote must necessarily be equal. The logic is intended
348 to follow that of operand_equal_p in fold-const.c */
351 hashable_expr_equal_p (const struct hashable_expr *expr0,
352 const struct hashable_expr *expr1)
354 tree type0 = expr0->type;
355 tree type1 = expr1->type;
357 /* If either type is NULL, there is nothing to check. */
358 if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
361 /* If both types don't have the same signedness, precision, and mode,
362 then we can't consider them equal. */
364 && (TREE_CODE (type0) == ERROR_MARK
365 || TREE_CODE (type1) == ERROR_MARK
366 || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
367 || TYPE_PRECISION (type0) != TYPE_PRECISION (type1)
368 || TYPE_MODE (type0) != TYPE_MODE (type1)))
371 if (expr0->kind != expr1->kind)
377 return operand_equal_p (expr0->ops.single.rhs,
378 expr1->ops.single.rhs, 0);
381 if (expr0->ops.unary.op != expr1->ops.unary.op)
384 if ((expr0->ops.unary.op == NOP_EXPR
385 || expr0->ops.unary.op == CONVERT_EXPR
386 || expr0->ops.unary.op == NON_LVALUE_EXPR)
387 && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
390 return operand_equal_p (expr0->ops.unary.opnd,
391 expr1->ops.unary.opnd, 0);
395 if (expr0->ops.binary.op != expr1->ops.binary.op)
398 if (operand_equal_p (expr0->ops.binary.opnd0,
399 expr1->ops.binary.opnd0, 0)
400 && operand_equal_p (expr0->ops.binary.opnd1,
401 expr1->ops.binary.opnd1, 0))
404 /* For commutative ops, allow the other order. */
405 return (commutative_tree_code (expr0->ops.binary.op)
406 && operand_equal_p (expr0->ops.binary.opnd0,
407 expr1->ops.binary.opnd1, 0)
408 && operand_equal_p (expr0->ops.binary.opnd1,
409 expr1->ops.binary.opnd0, 0));
416 /* If the calls are to different functions, then they
417 clearly cannot be equal. */
418 if (! operand_equal_p (expr0->ops.call.fn,
419 expr1->ops.call.fn, 0))
422 if (! expr0->ops.call.pure)
425 if (expr0->ops.call.nargs != expr1->ops.call.nargs)
428 for (i = 0; i < expr0->ops.call.nargs; i++)
429 if (! operand_equal_p (expr0->ops.call.args[i],
430 expr1->ops.call.args[i], 0))
441 /* Compute a hash value for a hashable_expr value EXPR and a
442 previously accumulated hash value VAL. If two hashable_expr
443 values compare equal with hashable_expr_equal_p, they must
444 hash to the same value, given an identical value of VAL.
445 The logic is intended to follow iterative_hash_expr in tree.c. */
448 iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val)
453 val = iterative_hash_expr (expr->ops.single.rhs, val);
457 val = iterative_hash_object (expr->ops.unary.op, val);
459 /* Make sure to include signedness in the hash computation.
460 Don't hash the type, that can lead to having nodes which
461 compare equal according to operand_equal_p, but which
462 have different hash codes. */
463 if (expr->ops.unary.op == NOP_EXPR
464 || expr->ops.unary.op == CONVERT_EXPR
465 || expr->ops.unary.op == NON_LVALUE_EXPR)
466 val += TYPE_UNSIGNED (expr->type);
468 val = iterative_hash_expr (expr->ops.unary.opnd, val);
472 val = iterative_hash_object (expr->ops.binary.op, val);
473 if (commutative_tree_code (expr->ops.binary.op))
474 val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
475 expr->ops.binary.opnd1, val);
478 val = iterative_hash_expr (expr->ops.binary.opnd0, val);
479 val = iterative_hash_expr (expr->ops.binary.opnd1, val);
486 enum tree_code code = CALL_EXPR;
488 val = iterative_hash_object (code, val);
489 val = iterative_hash_expr (expr->ops.call.fn, val);
490 for (i = 0; i < expr->ops.call.nargs; i++)
491 val = iterative_hash_expr (expr->ops.call.args[i], val);
502 /* Print a diagnostic dump of an expression hash table entry. */
505 print_expr_hash_elt (FILE * stream, const struct expr_hash_elt *element)
508 fprintf (stream, "STMT ");
510 fprintf (stream, "COND ");
514 print_generic_expr (stream, element->lhs, 0);
515 fprintf (stream, " = ");
518 switch (element->expr.kind)
521 print_generic_expr (stream, element->expr.ops.single.rhs, 0);
525 fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]);
526 print_generic_expr (stream, element->expr.ops.unary.opnd, 0);
530 print_generic_expr (stream, element->expr.ops.binary.opnd0, 0);
531 fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]);
532 print_generic_expr (stream, element->expr.ops.binary.opnd1, 0);
538 size_t nargs = element->expr.ops.call.nargs;
540 print_generic_expr (stream, element->expr.ops.call.fn, 0);
541 fprintf (stream, " (");
542 for (i = 0; i < nargs; i++)
544 print_generic_expr (stream, element->expr.ops.call.args[i], 0);
546 fprintf (stream, ", ");
548 fprintf (stream, ")");
552 fprintf (stream, "\n");
556 fprintf (stream, " ");
557 print_gimple_stmt (stream, element->stmt, 0, 0);
561 /* Delete an expr_hash_elt and reclaim its storage. */
564 free_expr_hash_elt (void *elt)
566 struct expr_hash_elt *element = ((struct expr_hash_elt *)elt);
568 if (element->expr.kind == EXPR_CALL)
569 free (element->expr.ops.call.args);
574 /* Allocate an EDGE_INFO for edge E and attach it to E.
575 Return the new EDGE_INFO structure. */
577 static struct edge_info *
578 allocate_edge_info (edge e)
580 struct edge_info *edge_info;
582 edge_info = XCNEW (struct edge_info);
588 /* Free all EDGE_INFO structures associated with edges in the CFG.
589 If a particular edge can be threaded, copy the redirection
590 target from the EDGE_INFO structure into the edge's AUX field
591 as required by code to update the CFG and SSA graph for
595 free_all_edge_infos (void)
603 FOR_EACH_EDGE (e, ei, bb->preds)
605 struct edge_info *edge_info = (struct edge_info *) e->aux;
609 if (edge_info->cond_equivalences)
610 free (edge_info->cond_equivalences);
618 /* Jump threading, redundancy elimination and const/copy propagation.
620 This pass may expose new symbols that need to be renamed into SSA. For
621 every new symbol exposed, its corresponding bit will be set in
625 tree_ssa_dominator_optimize (void)
627 struct dom_walk_data walk_data;
630 memset (&opt_stats, 0, sizeof (opt_stats));
632 /* Create our hash tables. */
633 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt);
634 avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20);
635 const_and_copies_stack = VEC_alloc (tree, heap, 20);
636 stmts_to_rescan = VEC_alloc (gimple_p, heap, 20);
637 need_eh_cleanup = BITMAP_ALLOC (NULL);
639 /* Setup callbacks for the generic dominator tree walker. */
640 walk_data.walk_stmts_backward = false;
641 walk_data.dom_direction = CDI_DOMINATORS;
642 walk_data.initialize_block_local_data = NULL;
643 walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
644 walk_data.before_dom_children_walk_stmts = optimize_stmt;
645 walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
646 walk_data.after_dom_children_before_stmts = NULL;
647 walk_data.after_dom_children_walk_stmts = NULL;
648 walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
649 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
650 When we attach more stuff we'll need to fill this out with a real
652 walk_data.global_data = NULL;
653 walk_data.block_local_data_size = 0;
654 walk_data.interesting_blocks = NULL;
656 /* Now initialize the dominator walker. */
657 init_walk_dominator_tree (&walk_data);
659 calculate_dominance_info (CDI_DOMINATORS);
662 /* We need to know loop structures in order to avoid destroying them
663 in jump threading. Note that we still can e.g. thread through loop
664 headers to an exit edge, or through loop header to the loop body, assuming
665 that we update the loop info. */
666 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
668 /* We need accurate information regarding back edges in the CFG
669 for jump threading; this may include back edges that are not part of
671 mark_dfs_back_edges ();
673 /* Recursively walk the dominator tree optimizing statements. */
674 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
677 gimple_stmt_iterator gsi;
680 {for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
681 update_stmt_if_modified (gsi_stmt (gsi));
685 /* If we exposed any new variables, go ahead and put them into
686 SSA form now, before we handle jump threading. This simplifies
687 interactions between rewriting of _DECL nodes into SSA form
688 and rewriting SSA_NAME nodes into SSA form after block
689 duplication and CFG manipulation. */
690 update_ssa (TODO_update_ssa);
692 free_all_edge_infos ();
694 /* Thread jumps, creating duplicate blocks as needed. */
695 cfg_altered |= thread_through_all_blocks (first_pass_instance);
698 free_dominance_info (CDI_DOMINATORS);
700 /* Removal of statements may make some EH edges dead. Purge
701 such edges from the CFG as needed. */
702 if (!bitmap_empty_p (need_eh_cleanup))
707 /* Jump threading may have created forwarder blocks from blocks
708 needing EH cleanup; the new successor of these blocks, which
709 has inherited from the original block, needs the cleanup. */
710 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
712 basic_block bb = BASIC_BLOCK (i);
713 if (single_succ_p (bb) == 1
714 && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
716 bitmap_clear_bit (need_eh_cleanup, i);
717 bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index);
721 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
722 bitmap_zero (need_eh_cleanup);
725 /* Finally, remove everything except invariants in SSA_NAME_VALUE.
727 Long term we will be able to let everything in SSA_NAME_VALUE
728 persist. However, for now, we know this is the safe thing to do. */
729 for (i = 0; i < num_ssa_names; i++)
731 tree name = ssa_name (i);
737 value = SSA_NAME_VALUE (name);
738 if (value && !is_gimple_min_invariant (value))
739 SSA_NAME_VALUE (name) = NULL;
742 statistics_counter_event (cfun, "Redundant expressions eliminated",
744 statistics_counter_event (cfun, "Constants propagated",
745 opt_stats.num_const_prop);
746 statistics_counter_event (cfun, "Copies propagated",
747 opt_stats.num_copy_prop);
749 /* Debugging dumps. */
750 if (dump_file && (dump_flags & TDF_STATS))
751 dump_dominator_optimization_stats (dump_file);
753 loop_optimizer_finalize ();
755 /* Delete our main hashtable. */
756 htab_delete (avail_exprs);
758 /* And finalize the dominator walker. */
759 fini_walk_dominator_tree (&walk_data);
761 /* Free asserted bitmaps and stacks. */
762 BITMAP_FREE (need_eh_cleanup);
764 VEC_free (expr_hash_elt_t, heap, avail_exprs_stack);
765 VEC_free (tree, heap, const_and_copies_stack);
766 VEC_free (gimple_p, heap, stmts_to_rescan);
772 gate_dominator (void)
774 return flag_tree_dom != 0;
777 struct gimple_opt_pass pass_dominator =
782 gate_dominator, /* gate */
783 tree_ssa_dominator_optimize, /* execute */
786 0, /* static_pass_number */
787 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
788 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
789 0, /* properties_provided */
790 0, /* properties_destroyed */
791 0, /* todo_flags_start */
795 | TODO_verify_ssa /* todo_flags_finish */
800 /* Given a conditional statement CONDSTMT, convert the
801 condition to a canonical form. */
804 canonicalize_comparison (gimple condstmt)
810 gcc_assert (gimple_code (condstmt) == GIMPLE_COND);
812 op0 = gimple_cond_lhs (condstmt);
813 op1 = gimple_cond_rhs (condstmt);
815 code = gimple_cond_code (condstmt);
817 /* If it would be profitable to swap the operands, then do so to
818 canonicalize the statement, enabling better optimization.
820 By placing canonicalization of such expressions here we
821 transparently keep statements in canonical form, even
822 when the statement is modified. */
823 if (tree_swap_operands_p (op0, op1, false))
825 /* For relationals we need to swap the operands
826 and change the code. */
832 code = swap_tree_comparison (code);
834 gimple_cond_set_code (condstmt, code);
835 gimple_cond_set_lhs (condstmt, op1);
836 gimple_cond_set_rhs (condstmt, op0);
838 update_stmt (condstmt);
843 /* Initialize local stacks for this optimizer and record equivalences
844 upon entry to BB. Equivalences can come from the edge traversed to
845 reach BB or they may come from PHI nodes at the start of BB. */
848 dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
851 if (dump_file && (dump_flags & TDF_DETAILS))
852 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
854 /* Push a marker on the stacks of local information so that we know how
855 far to unwind when we finalize this block. */
856 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
857 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
859 record_equivalences_from_incoming_edge (bb);
861 /* PHI nodes can create equivalences too. */
862 record_equivalences_from_phis (bb);
865 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
866 LIMIT entries left in LOCALs. */
869 remove_local_expressions_from_table (void)
871 /* Remove all the expressions made available in this block. */
872 while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0)
874 struct expr_hash_elt element;
875 expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack);
882 /* This must precede the actual removal from the hash table,
883 as ELEMENT and the table entry may share a call argument
884 vector which will be freed during removal. */
885 if (dump_file && (dump_flags & TDF_DETAILS))
887 fprintf (dump_file, "<<<< ");
888 print_expr_hash_elt (dump_file, &element);
891 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
895 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
896 CONST_AND_COPIES to its original state, stopping when we hit a
900 restore_vars_to_original_value (void)
902 while (VEC_length (tree, const_and_copies_stack) > 0)
904 tree prev_value, dest;
906 dest = VEC_pop (tree, const_and_copies_stack);
911 if (dump_file && (dump_flags & TDF_DETAILS))
913 fprintf (dump_file, "<<<< COPY ");
914 print_generic_expr (dump_file, dest, 0);
915 fprintf (dump_file, " = ");
916 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0);
917 fprintf (dump_file, "\n");
920 prev_value = VEC_pop (tree, const_and_copies_stack);
921 SSA_NAME_VALUE (dest) = prev_value;
925 /* A trivial wrapper so that we can present the generic jump
926 threading code with a simple API for simplifying statements. */
928 simplify_stmt_for_jump_threading (gimple stmt,
929 gimple within_stmt ATTRIBUTE_UNUSED)
931 return lookup_avail_expr (stmt, false);
934 /* Wrapper for common code to attempt to thread an edge. For example,
935 it handles lazily building the dummy condition and the bookkeeping
936 when jump threading is successful. */
939 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
941 if (! walk_data->global_data)
944 gimple_build_cond (NE_EXPR,
945 integer_zero_node, integer_zero_node,
947 walk_data->global_data = dummy_cond;
950 thread_across_edge ((gimple) walk_data->global_data, e, false,
951 &const_and_copies_stack,
952 simplify_stmt_for_jump_threading);
955 /* We have finished processing the dominator children of BB, perform
956 any finalization actions in preparation for leaving this node in
957 the dominator tree. */
960 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
964 /* If we have an outgoing edge to a block with multiple incoming and
965 outgoing edges, then we may be able to thread the edge, i.e., we
966 may be able to statically determine which of the outgoing edges
967 will be traversed when the incoming edge from BB is traversed. */
968 if (single_succ_p (bb)
969 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
970 && potentially_threadable_block (single_succ (bb)))
972 dom_thread_across_edge (walk_data, single_succ_edge (bb));
974 else if ((last = last_stmt (bb))
975 && gimple_code (last) == GIMPLE_COND
976 && EDGE_COUNT (bb->succs) == 2
977 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
978 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
980 edge true_edge, false_edge;
982 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
984 /* Only try to thread the edge if it reaches a target block with
985 more than one predecessor and more than one successor. */
986 if (potentially_threadable_block (true_edge->dest))
988 struct edge_info *edge_info;
991 /* Push a marker onto the available expression stack so that we
992 unwind any expressions related to the TRUE arm before processing
993 the false arm below. */
994 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
995 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
997 edge_info = (struct edge_info *) true_edge->aux;
999 /* If we have info associated with this edge, record it into
1000 our equivalence tables. */
1003 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1004 tree lhs = edge_info->lhs;
1005 tree rhs = edge_info->rhs;
1007 /* If we have a simple NAME = VALUE equivalence, record it. */
1008 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1009 record_const_or_copy (lhs, rhs);
1011 /* If we have 0 = COND or 1 = COND equivalences, record them
1012 into our expression hash tables. */
1013 if (cond_equivalences)
1014 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1015 record_cond (&cond_equivalences[i]);
1018 dom_thread_across_edge (walk_data, true_edge);
1020 /* And restore the various tables to their state before
1021 we threaded this edge. */
1022 remove_local_expressions_from_table ();
1025 /* Similarly for the ELSE arm. */
1026 if (potentially_threadable_block (false_edge->dest))
1028 struct edge_info *edge_info;
1031 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1032 edge_info = (struct edge_info *) false_edge->aux;
1034 /* If we have info associated with this edge, record it into
1035 our equivalence tables. */
1038 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1039 tree lhs = edge_info->lhs;
1040 tree rhs = edge_info->rhs;
1042 /* If we have a simple NAME = VALUE equivalence, record it. */
1043 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1044 record_const_or_copy (lhs, rhs);
1046 /* If we have 0 = COND or 1 = COND equivalences, record them
1047 into our expression hash tables. */
1048 if (cond_equivalences)
1049 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1050 record_cond (&cond_equivalences[i]);
1053 /* Now thread the edge. */
1054 dom_thread_across_edge (walk_data, false_edge);
1056 /* No need to remove local expressions from our tables
1057 or restore vars to their original value as that will
1058 be done immediately below. */
1062 remove_local_expressions_from_table ();
1063 restore_vars_to_original_value ();
1065 /* If we queued any statements to rescan in this block, then
1066 go ahead and rescan them now. */
1067 while (VEC_length (gimple_p, stmts_to_rescan) > 0)
1069 gimple *stmt_p = VEC_last (gimple_p, stmts_to_rescan);
1070 gimple stmt = *stmt_p;
1071 basic_block stmt_bb = gimple_bb (stmt);
1076 VEC_pop (gimple_p, stmts_to_rescan);
1077 pop_stmt_changes (stmt_p);
1081 /* PHI nodes can create equivalences too.
1083 Ignoring any alternatives which are the same as the result, if
1084 all the alternatives are equal, then the PHI node creates an
1088 record_equivalences_from_phis (basic_block bb)
1090 gimple_stmt_iterator gsi;
1092 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1094 gimple phi = gsi_stmt (gsi);
1096 tree lhs = gimple_phi_result (phi);
1100 for (i = 0; i < gimple_phi_num_args (phi); i++)
1102 tree t = gimple_phi_arg_def (phi, i);
1104 /* Ignore alternatives which are the same as our LHS. Since
1105 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1106 can simply compare pointers. */
1110 /* If we have not processed an alternative yet, then set
1111 RHS to this alternative. */
1114 /* If we have processed an alternative (stored in RHS), then
1115 see if it is equal to this one. If it isn't, then stop
1117 else if (! operand_equal_for_phi_arg_p (rhs, t))
1121 /* If we had no interesting alternatives, then all the RHS alternatives
1122 must have been the same as LHS. */
1126 /* If we managed to iterate through each PHI alternative without
1127 breaking out of the loop, then we have a PHI which may create
1128 a useful equivalence. We do not need to record unwind data for
1129 this, since this is a true assignment and not an equivalence
1130 inferred from a comparison. All uses of this ssa name are dominated
1131 by this assignment, so unwinding just costs time and space. */
1132 if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs))
1133 SSA_NAME_VALUE (lhs) = rhs;
1137 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1138 return that edge. Otherwise return NULL. */
1140 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1146 FOR_EACH_EDGE (e, ei, bb->preds)
1148 /* A loop back edge can be identified by the destination of
1149 the edge dominating the source of the edge. */
1150 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1153 /* If we have already seen a non-loop edge, then we must have
1154 multiple incoming non-loop edges and thus we return NULL. */
1158 /* This is the first non-loop incoming edge we have found. Record
1166 /* Record any equivalences created by the incoming edge to BB. If BB
1167 has more than one incoming edge, then no equivalence is created. */
1170 record_equivalences_from_incoming_edge (basic_block bb)
1174 struct edge_info *edge_info;
1176 /* If our parent block ended with a control statement, then we may be
1177 able to record some equivalences based on which outgoing edge from
1178 the parent was followed. */
1179 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1181 e = single_incoming_edge_ignoring_loop_edges (bb);
1183 /* If we had a single incoming edge from our parent block, then enter
1184 any data associated with the edge into our tables. */
1185 if (e && e->src == parent)
1189 edge_info = (struct edge_info *) e->aux;
1193 tree lhs = edge_info->lhs;
1194 tree rhs = edge_info->rhs;
1195 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1198 record_equality (lhs, rhs);
1200 if (cond_equivalences)
1201 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1202 record_cond (&cond_equivalences[i]);
1207 /* Dump SSA statistics on FILE. */
1210 dump_dominator_optimization_stats (FILE *file)
1212 fprintf (file, "Total number of statements: %6ld\n\n",
1213 opt_stats.num_stmts);
1214 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1215 opt_stats.num_exprs_considered);
1217 fprintf (file, "\nHash table statistics:\n");
1219 fprintf (file, " avail_exprs: ");
1220 htab_statistics (file, avail_exprs);
1224 /* Dump SSA statistics on stderr. */
1227 debug_dominator_optimization_stats (void)
1229 dump_dominator_optimization_stats (stderr);
1233 /* Dump statistics for the hash table HTAB. */
1236 htab_statistics (FILE *file, htab_t htab)
1238 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1239 (long) htab_size (htab),
1240 (long) htab_elements (htab),
1241 htab_collisions (htab));
1245 /* Enter condition equivalence into the expression hash table.
1246 This indicates that a conditional expression has a known
1250 record_cond (struct cond_equivalence *p)
1252 struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
1255 initialize_hash_element_from_expr (&p->cond, p->value, element);
1257 slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
1258 element->hash, INSERT);
1261 *slot = (void *) element;
1263 if (dump_file && (dump_flags & TDF_DETAILS))
1265 fprintf (dump_file, "1>>> ");
1266 print_expr_hash_elt (dump_file, element);
1269 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
1275 /* Build a cond_equivalence record indicating that the comparison
1276 CODE holds between operands OP0 and OP1. */
1279 build_and_record_new_cond (enum tree_code code,
1281 struct cond_equivalence *p)
1283 struct hashable_expr *cond = &p->cond;
1285 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
1287 cond->type = boolean_type_node;
1288 cond->kind = EXPR_BINARY;
1289 cond->ops.binary.op = code;
1290 cond->ops.binary.opnd0 = op0;
1291 cond->ops.binary.opnd1 = op1;
1293 p->value = boolean_true_node;
1296 /* Record that COND is true and INVERTED is false into the edge information
1297 structure. Also record that any conditions dominated by COND are true
1300 For example, if a < b is true, then a <= b must also be true. */
1303 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
1307 if (!COMPARISON_CLASS_P (cond))
1310 op0 = TREE_OPERAND (cond, 0);
1311 op1 = TREE_OPERAND (cond, 1);
1313 switch (TREE_CODE (cond))
1317 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1319 edge_info->max_cond_equivalences = 6;
1320 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 6);
1321 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1322 &edge_info->cond_equivalences[4]);
1323 build_and_record_new_cond (LTGT_EXPR, op0, op1,
1324 &edge_info->cond_equivalences[5]);
1328 edge_info->max_cond_equivalences = 4;
1329 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1332 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
1333 ? LE_EXPR : GE_EXPR),
1334 op0, op1, &edge_info->cond_equivalences[2]);
1335 build_and_record_new_cond (NE_EXPR, op0, op1,
1336 &edge_info->cond_equivalences[3]);
1341 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1343 edge_info->max_cond_equivalences = 3;
1344 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 3);
1345 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1346 &edge_info->cond_equivalences[2]);
1350 edge_info->max_cond_equivalences = 2;
1351 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1356 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1358 edge_info->max_cond_equivalences = 5;
1359 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 5);
1360 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1361 &edge_info->cond_equivalences[4]);
1365 edge_info->max_cond_equivalences = 4;
1366 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1368 build_and_record_new_cond (LE_EXPR, op0, op1,
1369 &edge_info->cond_equivalences[2]);
1370 build_and_record_new_cond (GE_EXPR, op0, op1,
1371 &edge_info->cond_equivalences[3]);
1374 case UNORDERED_EXPR:
1375 edge_info->max_cond_equivalences = 8;
1376 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 8);
1377 build_and_record_new_cond (NE_EXPR, op0, op1,
1378 &edge_info->cond_equivalences[2]);
1379 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1380 &edge_info->cond_equivalences[3]);
1381 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1382 &edge_info->cond_equivalences[4]);
1383 build_and_record_new_cond (UNEQ_EXPR, op0, op1,
1384 &edge_info->cond_equivalences[5]);
1385 build_and_record_new_cond (UNLT_EXPR, op0, op1,
1386 &edge_info->cond_equivalences[6]);
1387 build_and_record_new_cond (UNGT_EXPR, op0, op1,
1388 &edge_info->cond_equivalences[7]);
1393 edge_info->max_cond_equivalences = 4;
1394 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1395 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1396 ? UNLE_EXPR : UNGE_EXPR),
1397 op0, op1, &edge_info->cond_equivalences[2]);
1398 build_and_record_new_cond (NE_EXPR, op0, op1,
1399 &edge_info->cond_equivalences[3]);
1403 edge_info->max_cond_equivalences = 4;
1404 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1405 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1406 &edge_info->cond_equivalences[2]);
1407 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1408 &edge_info->cond_equivalences[3]);
1412 edge_info->max_cond_equivalences = 4;
1413 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1414 build_and_record_new_cond (NE_EXPR, op0, op1,
1415 &edge_info->cond_equivalences[2]);
1416 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1417 &edge_info->cond_equivalences[3]);
1421 edge_info->max_cond_equivalences = 2;
1422 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1426 /* Now store the original true and false conditions into the first
1428 initialize_expr_from_cond (cond, &edge_info->cond_equivalences[0].cond);
1429 edge_info->cond_equivalences[0].value = boolean_true_node;
1431 /* It is possible for INVERTED to be the negation of a comparison,
1432 and not a valid RHS or GIMPLE_COND condition. This happens because
1433 invert_truthvalue may return such an expression when asked to invert
1434 a floating-point comparison. These comparisons are not assumed to
1435 obey the trichotomy law. */
1436 initialize_expr_from_cond (inverted, &edge_info->cond_equivalences[1].cond);
1437 edge_info->cond_equivalences[1].value = boolean_false_node;
1440 /* A helper function for record_const_or_copy and record_equality.
1441 Do the work of recording the value and undo info. */
1444 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1446 SSA_NAME_VALUE (x) = y;
1448 if (dump_file && (dump_flags & TDF_DETAILS))
1450 fprintf (dump_file, "0>>> COPY ");
1451 print_generic_expr (dump_file, x, 0);
1452 fprintf (dump_file, " = ");
1453 print_generic_expr (dump_file, y, 0);
1454 fprintf (dump_file, "\n");
1457 VEC_reserve (tree, heap, const_and_copies_stack, 2);
1458 VEC_quick_push (tree, const_and_copies_stack, prev_x);
1459 VEC_quick_push (tree, const_and_copies_stack, x);
1462 /* Return the loop depth of the basic block of the defining statement of X.
1463 This number should not be treated as absolutely correct because the loop
1464 information may not be completely up-to-date when dom runs. However, it
1465 will be relatively correct, and as more passes are taught to keep loop info
1466 up to date, the result will become more and more accurate. */
1469 loop_depth_of_name (tree x)
1474 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1475 if (TREE_CODE (x) != SSA_NAME)
1478 /* Otherwise return the loop depth of the defining statement's bb.
1479 Note that there may not actually be a bb for this statement, if the
1480 ssa_name is live on entry. */
1481 defstmt = SSA_NAME_DEF_STMT (x);
1482 defbb = gimple_bb (defstmt);
1486 return defbb->loop_depth;
1489 /* Record that X is equal to Y in const_and_copies. Record undo
1490 information in the block-local vector. */
1493 record_const_or_copy (tree x, tree y)
1495 tree prev_x = SSA_NAME_VALUE (x);
1497 gcc_assert (TREE_CODE (x) == SSA_NAME);
1499 if (TREE_CODE (y) == SSA_NAME)
1501 tree tmp = SSA_NAME_VALUE (y);
1506 record_const_or_copy_1 (x, y, prev_x);
1509 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1510 This constrains the cases in which we may treat this as assignment. */
1513 record_equality (tree x, tree y)
1515 tree prev_x = NULL, prev_y = NULL;
1517 if (TREE_CODE (x) == SSA_NAME)
1518 prev_x = SSA_NAME_VALUE (x);
1519 if (TREE_CODE (y) == SSA_NAME)
1520 prev_y = SSA_NAME_VALUE (y);
1522 /* If one of the previous values is invariant, or invariant in more loops
1523 (by depth), then use that.
1524 Otherwise it doesn't matter which value we choose, just so
1525 long as we canonicalize on one value. */
1526 if (is_gimple_min_invariant (y))
1528 else if (is_gimple_min_invariant (x)
1529 || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
1530 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1531 else if (prev_x && is_gimple_min_invariant (prev_x))
1532 x = y, y = prev_x, prev_x = prev_y;
1536 /* After the swapping, we must have one SSA_NAME. */
1537 if (TREE_CODE (x) != SSA_NAME)
1540 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1541 variable compared against zero. If we're honoring signed zeros,
1542 then we cannot record this value unless we know that the value is
1544 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1545 && (TREE_CODE (y) != REAL_CST
1546 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1549 record_const_or_copy_1 (x, y, prev_x);
1552 /* Returns true when STMT is a simple iv increment. It detects the
1553 following situation:
1555 i_1 = phi (..., i_2)
1556 i_2 = i_1 +/- ... */
1559 simple_iv_increment_p (gimple stmt)
1565 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1568 lhs = gimple_assign_lhs (stmt);
1569 if (TREE_CODE (lhs) != SSA_NAME)
1572 if (gimple_assign_rhs_code (stmt) != PLUS_EXPR
1573 && gimple_assign_rhs_code (stmt) != MINUS_EXPR)
1576 preinc = gimple_assign_rhs1 (stmt);
1578 if (TREE_CODE (preinc) != SSA_NAME)
1581 phi = SSA_NAME_DEF_STMT (preinc);
1582 if (gimple_code (phi) != GIMPLE_PHI)
1585 for (i = 0; i < gimple_phi_num_args (phi); i++)
1586 if (gimple_phi_arg_def (phi, i) == lhs)
1592 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1593 known value for that SSA_NAME (or NULL if no value is known).
1595 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1596 successors of BB. */
1599 cprop_into_successor_phis (basic_block bb)
1604 FOR_EACH_EDGE (e, ei, bb->succs)
1607 gimple_stmt_iterator gsi;
1609 /* If this is an abnormal edge, then we do not want to copy propagate
1610 into the PHI alternative associated with this edge. */
1611 if (e->flags & EDGE_ABNORMAL)
1614 gsi = gsi_start_phis (e->dest);
1615 if (gsi_end_p (gsi))
1619 for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1622 use_operand_p orig_p;
1624 gimple phi = gsi_stmt (gsi);
1626 /* The alternative may be associated with a constant, so verify
1627 it is an SSA_NAME before doing anything with it. */
1628 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1629 orig_val = get_use_from_ptr (orig_p);
1630 if (TREE_CODE (orig_val) != SSA_NAME)
1633 /* If we have *ORIG_P in our constant/copy table, then replace
1634 ORIG_P with its value in our constant/copy table. */
1635 new_val = SSA_NAME_VALUE (orig_val);
1637 && new_val != orig_val
1638 && (TREE_CODE (new_val) == SSA_NAME
1639 || is_gimple_min_invariant (new_val))
1640 && may_propagate_copy (orig_val, new_val))
1641 propagate_value (orig_p, new_val);
1646 /* We have finished optimizing BB, record any information implied by
1647 taking a specific outgoing edge from BB. */
1650 record_edge_info (basic_block bb)
1652 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1653 struct edge_info *edge_info;
1655 if (! gsi_end_p (gsi))
1657 gimple stmt = gsi_stmt (gsi);
1659 if (gimple_code (stmt) == GIMPLE_SWITCH)
1661 tree index = gimple_switch_index (stmt);
1663 if (TREE_CODE (index) == SSA_NAME)
1666 int n_labels = gimple_switch_num_labels (stmt);
1667 tree *info = XCNEWVEC (tree, last_basic_block);
1671 for (i = 0; i < n_labels; i++)
1673 tree label = gimple_switch_label (stmt, i);
1674 basic_block target_bb = label_to_block (CASE_LABEL (label));
1675 if (CASE_HIGH (label)
1676 || !CASE_LOW (label)
1677 || info[target_bb->index])
1678 info[target_bb->index] = error_mark_node;
1680 info[target_bb->index] = label;
1683 FOR_EACH_EDGE (e, ei, bb->succs)
1685 basic_block target_bb = e->dest;
1686 tree label = info[target_bb->index];
1688 if (label != NULL && label != error_mark_node)
1690 tree x = fold_convert (TREE_TYPE (index), CASE_LOW (label));
1691 edge_info = allocate_edge_info (e);
1692 edge_info->lhs = index;
1700 /* A COND_EXPR may create equivalences too. */
1701 if (gimple_code (stmt) == GIMPLE_COND)
1706 tree op0 = gimple_cond_lhs (stmt);
1707 tree op1 = gimple_cond_rhs (stmt);
1708 enum tree_code code = gimple_cond_code (stmt);
1710 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1712 /* Special case comparing booleans against a constant as we
1713 know the value of OP0 on both arms of the branch. i.e., we
1714 can record an equivalence for OP0 rather than COND. */
1715 if ((code == EQ_EXPR || code == NE_EXPR)
1716 && TREE_CODE (op0) == SSA_NAME
1717 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
1718 && is_gimple_min_invariant (op1))
1720 if (code == EQ_EXPR)
1722 edge_info = allocate_edge_info (true_edge);
1723 edge_info->lhs = op0;
1724 edge_info->rhs = (integer_zerop (op1)
1725 ? boolean_false_node
1726 : boolean_true_node);
1728 edge_info = allocate_edge_info (false_edge);
1729 edge_info->lhs = op0;
1730 edge_info->rhs = (integer_zerop (op1)
1732 : boolean_false_node);
1736 edge_info = allocate_edge_info (true_edge);
1737 edge_info->lhs = op0;
1738 edge_info->rhs = (integer_zerop (op1)
1740 : boolean_false_node);
1742 edge_info = allocate_edge_info (false_edge);
1743 edge_info->lhs = op0;
1744 edge_info->rhs = (integer_zerop (op1)
1745 ? boolean_false_node
1746 : boolean_true_node);
1749 else if (is_gimple_min_invariant (op0)
1750 && (TREE_CODE (op1) == SSA_NAME
1751 || is_gimple_min_invariant (op1)))
1753 tree cond = build2 (code, boolean_type_node, op0, op1);
1754 tree inverted = invert_truthvalue (cond);
1755 struct edge_info *edge_info;
1757 edge_info = allocate_edge_info (true_edge);
1758 record_conditions (edge_info, cond, inverted);
1760 if (code == EQ_EXPR)
1762 edge_info->lhs = op1;
1763 edge_info->rhs = op0;
1766 edge_info = allocate_edge_info (false_edge);
1767 record_conditions (edge_info, inverted, cond);
1769 if (code == NE_EXPR)
1771 edge_info->lhs = op1;
1772 edge_info->rhs = op0;
1776 else if (TREE_CODE (op0) == SSA_NAME
1777 && (is_gimple_min_invariant (op1)
1778 || TREE_CODE (op1) == SSA_NAME))
1780 tree cond = build2 (code, boolean_type_node, op0, op1);
1781 tree inverted = invert_truthvalue (cond);
1782 struct edge_info *edge_info;
1784 edge_info = allocate_edge_info (true_edge);
1785 record_conditions (edge_info, cond, inverted);
1787 if (code == EQ_EXPR)
1789 edge_info->lhs = op0;
1790 edge_info->rhs = op1;
1793 edge_info = allocate_edge_info (false_edge);
1794 record_conditions (edge_info, inverted, cond);
1796 if (TREE_CODE (cond) == NE_EXPR)
1798 edge_info->lhs = op0;
1799 edge_info->rhs = op1;
1804 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1808 /* Propagate information from BB to its outgoing edges.
1810 This can include equivalence information implied by control statements
1811 at the end of BB and const/copy propagation into PHIs in BB's
1812 successor blocks. */
1815 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1818 record_edge_info (bb);
1819 cprop_into_successor_phis (bb);
1822 /* Search for redundant computations in STMT. If any are found, then
1823 replace them with the variable holding the result of the computation.
1825 If safe, record this expression into the available expression hash
1829 eliminate_redundant_computations (gimple_stmt_iterator* gsi)
1834 bool retval = false;
1835 bool assigns_var_p = false;
1837 gimple stmt = gsi_stmt (*gsi);
1839 tree def = gimple_get_lhs (stmt);
1841 /* Certain expressions on the RHS can be optimized away, but can not
1842 themselves be entered into the hash tables. */
1844 || TREE_CODE (def) != SSA_NAME
1845 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1846 || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF)
1847 /* Do not record equivalences for increments of ivs. This would create
1848 overlapping live ranges for a very questionable gain. */
1849 || simple_iv_increment_p (stmt))
1852 /* Check if the expression has been computed before. */
1853 cached_lhs = lookup_avail_expr (stmt, insert);
1855 opt_stats.num_exprs_considered++;
1857 /* Get the type of the expression we are trying to optimize. */
1858 if (is_gimple_assign (stmt))
1860 expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1861 assigns_var_p = true;
1863 else if (gimple_code (stmt) == GIMPLE_COND)
1864 expr_type = boolean_type_node;
1865 else if (is_gimple_call (stmt))
1867 gcc_assert (gimple_call_lhs (stmt));
1868 expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1869 assigns_var_p = true;
1871 else if (gimple_code (stmt) == GIMPLE_SWITCH)
1872 expr_type = TREE_TYPE (gimple_switch_index (stmt));
1879 /* It is safe to ignore types here since we have already done
1880 type checking in the hashing and equality routines. In fact
1881 type checking here merely gets in the way of constant
1882 propagation. Also, make sure that it is safe to propagate
1883 CACHED_LHS into the expression in STMT. */
1884 if ((TREE_CODE (cached_lhs) != SSA_NAME
1886 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1887 || may_propagate_copy_into_stmt (stmt, cached_lhs))
1889 #if defined ENABLE_CHECKING
1890 gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
1891 || is_gimple_min_invariant (cached_lhs));
1894 if (dump_file && (dump_flags & TDF_DETAILS))
1896 fprintf (dump_file, " Replaced redundant expr '");
1897 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1898 fprintf (dump_file, "' with '");
1899 print_generic_expr (dump_file, cached_lhs, dump_flags);
1900 fprintf (dump_file, "'\n");
1905 if (TREE_CODE (cached_lhs) == ADDR_EXPR
1906 || (POINTER_TYPE_P (expr_type)
1907 && is_gimple_min_invariant (cached_lhs)))
1911 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1912 cached_lhs = fold_convert (expr_type, cached_lhs);
1914 propagate_tree_value_into_stmt (gsi, cached_lhs);
1916 /* Since it is always necessary to mark the result as modified,
1917 perhaps we should move this into propagate_tree_value_into_stmt
1919 gimple_set_modified (gsi_stmt (*gsi), true);
1924 /* Return true if statement GS is an assignment that peforms a useless
1925 type conversion. It is is intended to be a tuples analog of function
1926 tree_ssa_useless_type_conversion. */
1929 gimple_assign_unary_useless_conversion_p (gimple gs)
1931 if (is_gimple_assign (gs)
1932 && (gimple_assign_rhs_code (gs) == NOP_EXPR
1933 || gimple_assign_rhs_code (gs) == CONVERT_EXPR
1934 || gimple_assign_rhs_code (gs) == VIEW_CONVERT_EXPR
1935 || gimple_assign_rhs_code (gs) == NON_LVALUE_EXPR))
1937 tree lhs_type = TREE_TYPE (gimple_assign_lhs (gs));
1938 tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (gs));
1939 return useless_type_conversion_p (lhs_type, rhs_type);
1945 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1946 the available expressions table or the const_and_copies table.
1947 Detect and record those equivalences. */
1948 /* We handle only very simple copy equivalences here. The heavy
1949 lifing is done by eliminate_redundant_computations. */
1952 record_equivalences_from_stmt (gimple stmt, int may_optimize_p)
1955 enum tree_code lhs_code;
1957 gcc_assert (is_gimple_assign (stmt));
1959 lhs = gimple_assign_lhs (stmt);
1960 lhs_code = TREE_CODE (lhs);
1962 if (lhs_code == SSA_NAME
1963 && (gimple_assign_single_p (stmt)
1964 || gimple_assign_unary_useless_conversion_p (stmt)))
1966 tree rhs = gimple_assign_rhs1 (stmt);
1968 /* Strip away any useless type conversions. */
1969 STRIP_USELESS_TYPE_CONVERSION (rhs);
1971 /* If the RHS of the assignment is a constant or another variable that
1972 may be propagated, register it in the CONST_AND_COPIES table. We
1973 do not need to record unwind data for this, since this is a true
1974 assignment and not an equivalence inferred from a comparison. All
1975 uses of this ssa name are dominated by this assignment, so unwinding
1976 just costs time and space. */
1978 && (TREE_CODE (rhs) == SSA_NAME
1979 || is_gimple_min_invariant (rhs)))
1981 if (dump_file && (dump_flags & TDF_DETAILS))
1983 fprintf (dump_file, "==== ASGN ");
1984 print_generic_expr (dump_file, lhs, 0);
1985 fprintf (dump_file, " = ");
1986 print_generic_expr (dump_file, rhs, 0);
1987 fprintf (dump_file, "\n");
1990 SSA_NAME_VALUE (lhs) = rhs;
1994 /* A memory store, even an aliased store, creates a useful
1995 equivalence. By exchanging the LHS and RHS, creating suitable
1996 vops and recording the result in the available expression table,
1997 we may be able to expose more redundant loads. */
1998 if (!gimple_has_volatile_ops (stmt)
1999 && gimple_references_memory_p (stmt)
2000 && gimple_assign_single_p (stmt)
2001 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
2002 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
2003 && !is_gimple_reg (lhs))
2005 tree rhs = gimple_assign_rhs1 (stmt);
2008 /* Build a new statement with the RHS and LHS exchanged. */
2009 if (TREE_CODE (rhs) == SSA_NAME)
2011 /* NOTE tuples. The call to gimple_build_assign below replaced
2012 a call to build_gimple_modify_stmt, which did not set the
2013 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
2014 may cause an SSA validation failure, as the LHS may be a
2015 default-initialized name and should have no definition. I'm
2016 a bit dubious of this, as the artificial statement that we
2017 generate here may in fact be ill-formed, but it is simply
2018 used as an internal device in this pass, and never becomes
2020 gimple defstmt = SSA_NAME_DEF_STMT (rhs);
2021 new_stmt = gimple_build_assign (rhs, lhs);
2022 SSA_NAME_DEF_STMT (rhs) = defstmt;
2025 new_stmt = gimple_build_assign (rhs, lhs);
2027 create_ssa_artificial_load_stmt (new_stmt, stmt, true);
2029 /* Finally enter the statement into the available expression
2031 lookup_avail_expr (new_stmt, true);
2035 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2036 CONST_AND_COPIES. */
2039 cprop_operand (gimple stmt, use_operand_p op_p)
2041 bool may_have_exposed_new_symbols = false;
2043 tree op = USE_FROM_PTR (op_p);
2045 /* If the operand has a known constant value or it is known to be a
2046 copy of some other variable, use the value or copy stored in
2047 CONST_AND_COPIES. */
2048 val = SSA_NAME_VALUE (op);
2049 if (val && val != op)
2051 tree op_type, val_type;
2053 /* Do not change the base variable in the virtual operand
2054 tables. That would make it impossible to reconstruct
2055 the renamed virtual operand if we later modify this
2056 statement. Also only allow the new value to be an SSA_NAME
2057 for propagation into virtual operands. */
2058 if (!is_gimple_reg (op)
2059 && (TREE_CODE (val) != SSA_NAME
2060 || is_gimple_reg (val)
2061 || get_virtual_var (val) != get_virtual_var (op)))
2064 /* Do not replace hard register operands in asm statements. */
2065 if (gimple_code (stmt) == GIMPLE_ASM
2066 && !may_propagate_copy_into_asm (op))
2069 /* Get the toplevel type of each operand. */
2070 op_type = TREE_TYPE (op);
2071 val_type = TREE_TYPE (val);
2073 /* While both types are pointers, get the type of the object
2075 while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
2077 op_type = TREE_TYPE (op_type);
2078 val_type = TREE_TYPE (val_type);
2081 /* Make sure underlying types match before propagating a constant by
2082 converting the constant to the proper type. Note that convert may
2083 return a non-gimple expression, in which case we ignore this
2084 propagation opportunity. */
2085 if (TREE_CODE (val) != SSA_NAME)
2087 if (!useless_type_conversion_p (op_type, val_type))
2089 val = fold_convert (TREE_TYPE (op), val);
2090 if (!is_gimple_min_invariant (val))
2095 /* Certain operands are not allowed to be copy propagated due
2096 to their interaction with exception handling and some GCC
2098 else if (!may_propagate_copy (op, val))
2101 /* Do not propagate copies if the propagated value is at a deeper loop
2102 depth than the propagatee. Otherwise, this may move loop variant
2103 variables outside of their loops and prevent coalescing
2104 opportunities. If the value was loop invariant, it will be hoisted
2105 by LICM and exposed for copy propagation. */
2106 if (loop_depth_of_name (val) > loop_depth_of_name (op))
2110 if (dump_file && (dump_flags & TDF_DETAILS))
2112 fprintf (dump_file, " Replaced '");
2113 print_generic_expr (dump_file, op, dump_flags);
2114 fprintf (dump_file, "' with %s '",
2115 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2116 print_generic_expr (dump_file, val, dump_flags);
2117 fprintf (dump_file, "'\n");
2120 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2121 that we may have exposed a new symbol for SSA renaming. */
2122 if (TREE_CODE (val) == ADDR_EXPR
2123 || (POINTER_TYPE_P (TREE_TYPE (op))
2124 && is_gimple_min_invariant (val)))
2125 may_have_exposed_new_symbols = true;
2127 if (TREE_CODE (val) != SSA_NAME)
2128 opt_stats.num_const_prop++;
2130 opt_stats.num_copy_prop++;
2132 propagate_value (op_p, val);
2134 /* And note that we modified this statement. This is now
2135 safe, even if we changed virtual operands since we will
2136 rescan the statement and rewrite its operands again. */
2137 gimple_set_modified (stmt, true);
2139 return may_have_exposed_new_symbols;
2142 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2143 known value for that SSA_NAME (or NULL if no value is known).
2145 Propagate values from CONST_AND_COPIES into the uses, vuses and
2146 vdef_ops of STMT. */
2149 cprop_into_stmt (gimple stmt)
2151 bool may_have_exposed_new_symbols = false;
2155 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
2157 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
2158 may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
2161 return may_have_exposed_new_symbols;
2164 /* Optimize the statement pointed to by iterator SI.
2166 We try to perform some simplistic global redundancy elimination and
2167 constant propagation:
2169 1- To detect global redundancy, we keep track of expressions that have
2170 been computed in this block and its dominators. If we find that the
2171 same expression is computed more than once, we eliminate repeated
2172 computations by using the target of the first one.
2174 2- Constant values and copy assignments. This is used to do very
2175 simplistic constant and copy propagation. When a constant or copy
2176 assignment is found, we map the value on the RHS of the assignment to
2177 the variable in the LHS in the CONST_AND_COPIES table. */
2180 optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2181 basic_block bb, gimple_stmt_iterator si)
2183 gimple stmt, old_stmt;
2184 bool may_optimize_p;
2185 bool may_have_exposed_new_symbols = false;
2187 old_stmt = stmt = gsi_stmt (si);
2189 if (gimple_code (stmt) == GIMPLE_COND)
2190 canonicalize_comparison (stmt);
2192 update_stmt_if_modified (stmt);
2193 opt_stats.num_stmts++;
2194 may_have_exposed_new_symbols = false;
2195 push_stmt_changes (gsi_stmt_ptr (&si));
2197 if (dump_file && (dump_flags & TDF_DETAILS))
2199 fprintf (dump_file, "Optimizing statement ");
2200 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2203 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2204 may_have_exposed_new_symbols = cprop_into_stmt (stmt);
2206 /* If the statement has been modified with constant replacements,
2207 fold its RHS before checking for redundant computations. */
2208 if (gimple_modified_p (stmt))
2212 /* Try to fold the statement making sure that STMT is kept
2214 if (fold_stmt (&si))
2216 stmt = gsi_stmt (si);
2218 if (dump_file && (dump_flags & TDF_DETAILS))
2220 fprintf (dump_file, " Folded to: ");
2221 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2225 /* We only need to consider cases that can yield a gimple operand. */
2226 if (gimple_assign_single_p (stmt))
2227 rhs = gimple_assign_rhs1 (stmt);
2228 else if (gimple_code (stmt) == GIMPLE_GOTO)
2229 rhs = gimple_goto_dest (stmt);
2230 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2231 /* This should never be an ADDR_EXPR. */
2232 rhs = gimple_switch_index (stmt);
2234 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
2235 recompute_tree_invariant_for_addr_expr (rhs);
2237 /* Constant/copy propagation above may change the set of
2238 virtual operands associated with this statement. Folding
2239 may remove the need for some virtual operands.
2241 Indicate we will need to rescan and rewrite the statement. */
2242 may_have_exposed_new_symbols = true;
2245 /* Check for redundant computations. Do this optimization only
2246 for assignments that have no volatile ops and conditionals. */
2247 may_optimize_p = (!gimple_has_volatile_ops (stmt)
2248 && ((is_gimple_assign (stmt)
2249 && !gimple_rhs_has_side_effects (stmt))
2250 || (is_gimple_call (stmt)
2251 && gimple_call_lhs (stmt) != NULL_TREE
2252 && !gimple_rhs_has_side_effects (stmt))
2253 || gimple_code (stmt) == GIMPLE_COND
2254 || gimple_code (stmt) == GIMPLE_SWITCH));
2258 may_have_exposed_new_symbols |= eliminate_redundant_computations (&si);
2259 stmt = gsi_stmt (si);
2262 /* Record any additional equivalences created by this statement. */
2263 if (is_gimple_assign (stmt))
2264 record_equivalences_from_stmt (stmt, may_optimize_p);
2266 /* If STMT is a COND_EXPR and it was modified, then we may know
2267 where it goes. If that is the case, then mark the CFG as altered.
2269 This will cause us to later call remove_unreachable_blocks and
2270 cleanup_tree_cfg when it is safe to do so. It is not safe to
2271 clean things up here since removal of edges and such can trigger
2272 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2275 That's all fine and good, except that once SSA_NAMEs are released
2276 to the manager, we must not call create_ssa_name until all references
2277 to released SSA_NAMEs have been eliminated.
2279 All references to the deleted SSA_NAMEs can not be eliminated until
2280 we remove unreachable blocks.
2282 We can not remove unreachable blocks until after we have completed
2283 any queued jump threading.
2285 We can not complete any queued jump threads until we have taken
2286 appropriate variables out of SSA form. Taking variables out of
2287 SSA form can call create_ssa_name and thus we lose.
2289 Ultimately I suspect we're going to need to change the interface
2290 into the SSA_NAME manager. */
2291 if (gimple_modified_p (stmt))
2295 if (gimple_code (stmt) == GIMPLE_COND)
2296 val = fold_binary (gimple_cond_code (stmt), boolean_type_node,
2297 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
2298 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2299 val = gimple_switch_index (stmt);
2301 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
2304 /* If we simplified a statement in such a way as to be shown that it
2305 cannot trap, update the eh information and the cfg to match. */
2306 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
2308 bitmap_set_bit (need_eh_cleanup, bb->index);
2309 if (dump_file && (dump_flags & TDF_DETAILS))
2310 fprintf (dump_file, " Flagged to clear EH edges.\n");
2314 if (may_have_exposed_new_symbols)
2316 /* Queue the statement to be re-scanned after all the
2317 AVAIL_EXPRS have been processed. The change buffer stack for
2318 all the pushed statements will be processed when this queue
2320 VEC_safe_push (gimple_p, heap, stmts_to_rescan, gsi_stmt_ptr (&si));
2324 /* Otherwise, just discard the recently pushed change buffer. If
2325 not, the STMTS_TO_RESCAN queue will get out of synch with the
2326 change buffer stack. */
2327 discard_stmt_changes (gsi_stmt_ptr (&si));
2331 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
2332 If found, return its LHS. Otherwise insert STMT in the table and
2335 Also, when an expression is first inserted in the table, it is also
2336 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
2337 we finish processing this block and its children. */
2340 lookup_avail_expr (gimple stmt, bool insert)
2345 struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
2347 /* Get LHS of assignment or call, else NULL_TREE. */
2348 lhs = gimple_get_lhs (stmt);
2350 initialize_hash_element (stmt, lhs, element);
2352 if (dump_file && (dump_flags & TDF_DETAILS))
2354 fprintf (dump_file, "LKUP ");
2355 print_expr_hash_elt (dump_file, element);
2358 /* Don't bother remembering constant assignments and copy operations.
2359 Constants and copy operations are handled by the constant/copy propagator
2360 in optimize_stmt. */
2361 if (element->expr.kind == EXPR_SINGLE
2362 && (TREE_CODE (element->expr.ops.single.rhs) == SSA_NAME
2363 || is_gimple_min_invariant (element->expr.ops.single.rhs)))
2369 /* Finally try to find the expression in the main expression hash table. */
2370 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
2371 (insert ? INSERT : NO_INSERT));
2380 *slot = (void *) element;
2382 if (dump_file && (dump_flags & TDF_DETAILS))
2384 fprintf (dump_file, "2>>> ");
2385 print_expr_hash_elt (dump_file, element);
2388 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
2392 /* Extract the LHS of the assignment so that it can be used as the current
2393 definition of another variable. */
2394 lhs = ((struct expr_hash_elt *)*slot)->lhs;
2396 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2397 use the value from the const_and_copies table. */
2398 if (TREE_CODE (lhs) == SSA_NAME)
2400 temp = SSA_NAME_VALUE (lhs);
2407 if (dump_file && (dump_flags & TDF_DETAILS))
2409 fprintf (dump_file, "FIND: ");
2410 print_generic_expr (dump_file, lhs, 0);
2411 fprintf (dump_file, "\n");
2417 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number
2418 for expressions using the code of the expression and the SSA numbers of
2422 avail_expr_hash (const void *p)
2424 gimple stmt = ((const struct expr_hash_elt *)p)->stmt;
2425 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr;
2430 val = iterative_hash_hashable_expr (expr, val);
2432 /* If the hash table entry is not associated with a statement, then we
2433 can just hash the expression and not worry about virtual operands
2438 /* Add the SSA version numbers of every vuse operand. This is important
2439 because compound variables like arrays are not renamed in the
2440 operands. Rather, the rename is done on the virtual variable
2441 representing all the elements of the array. */
2442 FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
2443 val = iterative_hash_expr (vuse, val);
2449 real_avail_expr_hash (const void *p)
2451 return ((const struct expr_hash_elt *)p)->hash;
2455 avail_expr_eq (const void *p1, const void *p2)
2457 gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
2458 const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr;
2459 const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp;
2460 gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
2461 const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr;
2462 const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp;
2464 /* This case should apply only when removing entries from the table. */
2465 if (stamp1 == stamp2)
2469 We add stmts to a hash table and them modify them. To detect the case
2470 that we modify a stmt and then search for it, we assume that the hash
2471 is always modified by that change.
2472 We have to fully check why this doesn't happen on trunk or rewrite
2473 this in a more reliable (and easier to understand) way. */
2474 if (((const struct expr_hash_elt *)p1)->hash
2475 != ((const struct expr_hash_elt *)p2)->hash)
2478 /* In case of a collision, both RHS have to be identical and have the
2479 same VUSE operands. */
2480 if (hashable_expr_equal_p (expr1, expr2)
2481 && types_compatible_p (expr1->type, expr2->type))
2483 /* Note that STMT1 and/or STMT2 may be NULL. */
2484 bool ret = compare_ssa_operands_equal (stmt1, stmt2, SSA_OP_VUSE);
2491 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2492 up degenerate PHIs created by or exposed by jump threading. */
2494 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2498 degenerate_phi_result (gimple phi)
2500 tree lhs = gimple_phi_result (phi);
2504 /* Ignoring arguments which are the same as LHS, if all the remaining
2505 arguments are the same, then the PHI is a degenerate and has the
2506 value of that common argument. */
2507 for (i = 0; i < gimple_phi_num_args (phi); i++)
2509 tree arg = gimple_phi_arg_def (phi, i);
2515 else if (!operand_equal_p (arg, val, 0))
2518 return (i == gimple_phi_num_args (phi) ? val : NULL);
2521 /* Given a statement STMT, which is either a PHI node or an assignment,
2522 remove it from the IL. */
2525 remove_stmt_or_phi (gimple stmt)
2527 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
2529 if (gimple_code (stmt) == GIMPLE_PHI)
2530 remove_phi_node (&gsi, true);
2533 gsi_remove (&gsi, true);
2534 release_defs (stmt);
2538 /* Given a statement STMT, which is either a PHI node or an assignment,
2539 return the "rhs" of the node, in the case of a non-degenerate
2540 phi, NULL is returned. */
2543 get_rhs_or_phi_arg (gimple stmt)
2545 if (gimple_code (stmt) == GIMPLE_PHI)
2546 return degenerate_phi_result (stmt);
2547 else if (gimple_assign_single_p (stmt))
2548 return gimple_assign_rhs1 (stmt);
2554 /* Given a statement STMT, which is either a PHI node or an assignment,
2555 return the "lhs" of the node. */
2558 get_lhs_or_phi_result (gimple stmt)
2560 if (gimple_code (stmt) == GIMPLE_PHI)
2561 return gimple_phi_result (stmt);
2562 else if (is_gimple_assign (stmt))
2563 return gimple_assign_lhs (stmt);
2568 /* Propagate RHS into all uses of LHS (when possible).
2570 RHS and LHS are derived from STMT, which is passed in solely so
2571 that we can remove it if propagation is successful.
2573 When propagating into a PHI node or into a statement which turns
2574 into a trivial copy or constant initialization, set the
2575 appropriate bit in INTERESTING_NAMEs so that we will visit those
2576 nodes as well in an effort to pick up secondary optimization
2580 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
2582 /* First verify that propagation is valid and isn't going to move a
2583 loop variant variable outside its loop. */
2584 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
2585 && (TREE_CODE (rhs) != SSA_NAME
2586 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
2587 && may_propagate_copy (lhs, rhs)
2588 && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
2590 use_operand_p use_p;
2591 imm_use_iterator iter;
2596 if (dump_file && (dump_flags & TDF_DETAILS))
2598 fprintf (dump_file, " Replacing '");
2599 print_generic_expr (dump_file, lhs, dump_flags);
2600 fprintf (dump_file, "' with %s '",
2601 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
2602 print_generic_expr (dump_file, rhs, dump_flags);
2603 fprintf (dump_file, "'\n");
2606 /* Walk over every use of LHS and try to replace the use with RHS.
2607 At this point the only reason why such a propagation would not
2608 be successful would be if the use occurs in an ASM_EXPR. */
2609 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
2612 /* It's not always safe to propagate into an ASM_EXPR. */
2613 if (gimple_code (use_stmt) == GIMPLE_ASM
2614 && ! may_propagate_copy_into_asm (lhs))
2621 if (dump_file && (dump_flags & TDF_DETAILS))
2623 fprintf (dump_file, " Original statement:");
2624 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2627 push_stmt_changes (&use_stmt);
2629 /* Propagate the RHS into this use of the LHS. */
2630 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2631 propagate_value (use_p, rhs);
2633 /* Special cases to avoid useless calls into the folding
2634 routines, operand scanning, etc.
2636 First, propagation into a PHI may cause the PHI to become
2637 a degenerate, so mark the PHI as interesting. No other
2638 actions are necessary.
2640 Second, if we're propagating a virtual operand and the
2641 propagation does not change the underlying _DECL node for
2642 the virtual operand, then no further actions are necessary. */
2643 if (gimple_code (use_stmt) == GIMPLE_PHI
2644 || (! is_gimple_reg (lhs)
2645 && TREE_CODE (rhs) == SSA_NAME
2646 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
2649 if (dump_file && (dump_flags & TDF_DETAILS))
2651 fprintf (dump_file, " Updated statement:");
2652 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2655 /* Propagation into a PHI may expose new degenerate PHIs,
2656 so mark the result of the PHI as interesting. */
2657 if (gimple_code (use_stmt) == GIMPLE_PHI)
2659 tree result = get_lhs_or_phi_result (use_stmt);
2660 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2663 discard_stmt_changes (&use_stmt);
2667 /* From this point onward we are propagating into a
2668 real statement. Folding may (or may not) be possible,
2669 we may expose new operands, expose dead EH edges,
2671 /* NOTE tuples. In the tuples world, fold_stmt_inplace
2672 cannot fold a call that simplifies to a constant,
2673 because the GIMPLE_CALL must be replaced by a
2674 GIMPLE_ASSIGN, and there is no way to effect such a
2675 transformation in-place. We might want to consider
2676 using the more general fold_stmt here. */
2677 fold_stmt_inplace (use_stmt);
2679 /* Sometimes propagation can expose new operands to the
2680 renamer. Note this will call update_stmt at the
2681 appropriate time. */
2682 pop_stmt_changes (&use_stmt);
2685 if (dump_file && (dump_flags & TDF_DETAILS))
2687 fprintf (dump_file, " Updated statement:");
2688 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2691 /* If we replaced a variable index with a constant, then
2692 we would need to update the invariant flag for ADDR_EXPRs. */
2693 if (gimple_assign_single_p (use_stmt)
2694 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
2695 recompute_tree_invariant_for_addr_expr
2696 (gimple_assign_rhs1 (use_stmt));
2698 /* If we cleaned up EH information from the statement,
2699 mark its containing block as needing EH cleanups. */
2700 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
2702 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
2703 if (dump_file && (dump_flags & TDF_DETAILS))
2704 fprintf (dump_file, " Flagged to clear EH edges.\n");
2707 /* Propagation may expose new trivial copy/constant propagation
2709 if (gimple_assign_single_p (use_stmt)
2710 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
2711 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
2712 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
2714 tree result = get_lhs_or_phi_result (use_stmt);
2715 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2718 /* Propagation into these nodes may make certain edges in
2719 the CFG unexecutable. We want to identify them as PHI nodes
2720 at the destination of those unexecutable edges may become
2722 else if (gimple_code (use_stmt) == GIMPLE_COND
2723 || gimple_code (use_stmt) == GIMPLE_SWITCH
2724 || gimple_code (use_stmt) == GIMPLE_GOTO)
2728 if (gimple_code (use_stmt) == GIMPLE_COND)
2729 val = fold_binary (gimple_cond_code (use_stmt),
2731 gimple_cond_lhs (use_stmt),
2732 gimple_cond_rhs (use_stmt));
2733 else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
2734 val = gimple_switch_index (use_stmt);
2736 val = gimple_goto_dest (use_stmt);
2738 if (val && is_gimple_min_invariant (val))
2740 basic_block bb = gimple_bb (use_stmt);
2741 edge te = find_taken_edge (bb, val);
2744 gimple_stmt_iterator gsi, psi;
2746 /* Remove all outgoing edges except TE. */
2747 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
2751 /* Mark all the PHI nodes at the destination of
2752 the unexecutable edge as interesting. */
2753 for (psi = gsi_start_phis (e->dest);
2757 gimple phi = gsi_stmt (psi);
2759 tree result = gimple_phi_result (phi);
2760 int version = SSA_NAME_VERSION (result);
2762 bitmap_set_bit (interesting_names, version);
2765 te->probability += e->probability;
2767 te->count += e->count;
2775 gsi = gsi_last_bb (gimple_bb (use_stmt));
2776 gsi_remove (&gsi, true);
2778 /* And fixup the flags on the single remaining edge. */
2779 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
2780 te->flags &= ~EDGE_ABNORMAL;
2781 te->flags |= EDGE_FALLTHRU;
2782 if (te->probability > REG_BR_PROB_BASE)
2783 te->probability = REG_BR_PROB_BASE;
2788 /* Ensure there is nothing else to do. */
2789 gcc_assert (!all || has_zero_uses (lhs));
2791 /* If we were able to propagate away all uses of LHS, then
2792 we can remove STMT. */
2794 remove_stmt_or_phi (stmt);
2798 /* STMT is either a PHI node (potentially a degenerate PHI node) or
2799 a statement that is a trivial copy or constant initialization.
2801 Attempt to eliminate T by propagating its RHS into all uses of
2802 its LHS. This may in turn set new bits in INTERESTING_NAMES
2803 for nodes we want to revisit later.
2805 All exit paths should clear INTERESTING_NAMES for the result
2809 eliminate_const_or_copy (gimple stmt, bitmap interesting_names)
2811 tree lhs = get_lhs_or_phi_result (stmt);
2813 int version = SSA_NAME_VERSION (lhs);
2815 /* If the LHS of this statement or PHI has no uses, then we can
2816 just eliminate it. This can occur if, for example, the PHI
2817 was created by block duplication due to threading and its only
2818 use was in the conditional at the end of the block which was
2820 if (has_zero_uses (lhs))
2822 bitmap_clear_bit (interesting_names, version);
2823 remove_stmt_or_phi (stmt);
2827 /* Get the RHS of the assignment or PHI node if the PHI is a
2829 rhs = get_rhs_or_phi_arg (stmt);
2832 bitmap_clear_bit (interesting_names, version);
2836 propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
2838 /* Note that STMT may well have been deleted by now, so do
2839 not access it, instead use the saved version # to clear
2840 T's entry in the worklist. */
2841 bitmap_clear_bit (interesting_names, version);
2844 /* The first phase in degenerate PHI elimination.
2846 Eliminate the degenerate PHIs in BB, then recurse on the
2847 dominator children of BB. */
2850 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names)
2852 gimple_stmt_iterator gsi;
2855 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2857 gimple phi = gsi_stmt (gsi);
2859 eliminate_const_or_copy (phi, interesting_names);
2862 /* Recurse into the dominator children of BB. */
2863 for (son = first_dom_son (CDI_DOMINATORS, bb);
2865 son = next_dom_son (CDI_DOMINATORS, son))
2866 eliminate_degenerate_phis_1 (son, interesting_names);
2870 /* A very simple pass to eliminate degenerate PHI nodes from the
2871 IL. This is meant to be fast enough to be able to be run several
2872 times in the optimization pipeline.
2874 Certain optimizations, particularly those which duplicate blocks
2875 or remove edges from the CFG can create or expose PHIs which are
2876 trivial copies or constant initializations.
2878 While we could pick up these optimizations in DOM or with the
2879 combination of copy-prop and CCP, those solutions are far too
2880 heavy-weight for our needs.
2882 This implementation has two phases so that we can efficiently
2883 eliminate the first order degenerate PHIs and second order
2886 The first phase performs a dominator walk to identify and eliminate
2887 the vast majority of the degenerate PHIs. When a degenerate PHI
2888 is identified and eliminated any affected statements or PHIs
2889 are put on a worklist.
2891 The second phase eliminates degenerate PHIs and trivial copies
2892 or constant initializations using the worklist. This is how we
2893 pick up the secondary optimization opportunities with minimal
2897 eliminate_degenerate_phis (void)
2899 bitmap interesting_names;
2900 bitmap interesting_names1;
2902 /* Bitmap of blocks which need EH information updated. We can not
2903 update it on-the-fly as doing so invalidates the dominator tree. */
2904 need_eh_cleanup = BITMAP_ALLOC (NULL);
2906 /* INTERESTING_NAMES is effectively our worklist, indexed by
2909 A set bit indicates that the statement or PHI node which
2910 defines the SSA_NAME should be (re)examined to determine if
2911 it has become a degenerate PHI or trivial const/copy propagation
2914 Experiments have show we generally get better compilation
2915 time behavior with bitmaps rather than sbitmaps. */
2916 interesting_names = BITMAP_ALLOC (NULL);
2917 interesting_names1 = BITMAP_ALLOC (NULL);
2919 calculate_dominance_info (CDI_DOMINATORS);
2920 cfg_altered = false;
2922 /* First phase. Eliminate degenerate PHIs via a dominator
2925 Experiments have indicated that we generally get better
2926 compile-time behavior by visiting blocks in the first
2927 phase in dominator order. Presumably this is because walking
2928 in dominator order leaves fewer PHIs for later examination
2929 by the worklist phase. */
2930 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
2932 /* Second phase. Eliminate second order degenerate PHIs as well
2933 as trivial copies or constant initializations identified by
2934 the first phase or this phase. Basically we keep iterating
2935 until our set of INTERESTING_NAMEs is empty. */
2936 while (!bitmap_empty_p (interesting_names))
2941 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2942 changed during the loop. Copy it to another bitmap and
2944 bitmap_copy (interesting_names1, interesting_names);
2946 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
2948 tree name = ssa_name (i);
2950 /* Ignore SSA_NAMEs that have been released because
2951 their defining statement was deleted (unreachable). */
2953 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
2959 free_dominance_info (CDI_DOMINATORS);
2961 /* Propagation of const and copies may make some EH edges dead. Purge
2962 such edges from the CFG as needed. */
2963 if (!bitmap_empty_p (need_eh_cleanup))
2965 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
2966 BITMAP_FREE (need_eh_cleanup);
2969 BITMAP_FREE (interesting_names);
2970 BITMAP_FREE (interesting_names1);
2974 struct gimple_opt_pass pass_phi_only_cprop =
2978 "phicprop", /* name */
2979 gate_dominator, /* gate */
2980 eliminate_degenerate_phis, /* execute */
2983 0, /* static_pass_number */
2984 TV_TREE_PHI_CPROP, /* tv_id */
2985 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2986 0, /* properties_provided */
2987 0, /* properties_destroyed */
2988 0, /* todo_flags_start */
2994 | TODO_update_ssa /* todo_flags_finish */