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;
623 memset (&opt_stats, 0, sizeof (opt_stats));
625 /* Create our hash tables. */
626 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt);
627 avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20);
628 const_and_copies_stack = VEC_alloc (tree, heap, 20);
629 stmts_to_rescan = VEC_alloc (gimple_p, heap, 20);
630 need_eh_cleanup = BITMAP_ALLOC (NULL);
632 /* Setup callbacks for the generic dominator tree walker. */
633 walk_data.walk_stmts_backward = false;
634 walk_data.dom_direction = CDI_DOMINATORS;
635 walk_data.initialize_block_local_data = NULL;
636 walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
637 walk_data.before_dom_children_walk_stmts = optimize_stmt;
638 walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges;
639 walk_data.after_dom_children_before_stmts = NULL;
640 walk_data.after_dom_children_walk_stmts = NULL;
641 walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
642 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
643 When we attach more stuff we'll need to fill this out with a real
645 walk_data.global_data = NULL;
646 walk_data.block_local_data_size = 0;
647 walk_data.interesting_blocks = NULL;
649 /* Now initialize the dominator walker. */
650 init_walk_dominator_tree (&walk_data);
652 calculate_dominance_info (CDI_DOMINATORS);
655 /* We need to know loop structures in order to avoid destroying them
656 in jump threading. Note that we still can e.g. thread through loop
657 headers to an exit edge, or through loop header to the loop body, assuming
658 that we update the loop info. */
659 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
661 /* Initialize the value-handle array. */
662 threadedge_initialize_values ();
664 /* We need accurate information regarding back edges in the CFG
665 for jump threading; this may include back edges that are not part of
667 mark_dfs_back_edges ();
669 /* Recursively walk the dominator tree optimizing statements. */
670 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
673 gimple_stmt_iterator gsi;
676 {for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
677 update_stmt_if_modified (gsi_stmt (gsi));
681 /* If we exposed any new variables, go ahead and put them into
682 SSA form now, before we handle jump threading. This simplifies
683 interactions between rewriting of _DECL nodes into SSA form
684 and rewriting SSA_NAME nodes into SSA form after block
685 duplication and CFG manipulation. */
686 update_ssa (TODO_update_ssa);
688 free_all_edge_infos ();
690 /* Thread jumps, creating duplicate blocks as needed. */
691 cfg_altered |= thread_through_all_blocks (first_pass_instance);
694 free_dominance_info (CDI_DOMINATORS);
696 /* Removal of statements may make some EH edges dead. Purge
697 such edges from the CFG as needed. */
698 if (!bitmap_empty_p (need_eh_cleanup))
703 /* Jump threading may have created forwarder blocks from blocks
704 needing EH cleanup; the new successor of these blocks, which
705 has inherited from the original block, needs the cleanup. */
706 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
708 basic_block bb = BASIC_BLOCK (i);
709 if (single_succ_p (bb) == 1
710 && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
712 bitmap_clear_bit (need_eh_cleanup, i);
713 bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index);
717 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
718 bitmap_zero (need_eh_cleanup);
721 statistics_counter_event (cfun, "Redundant expressions eliminated",
723 statistics_counter_event (cfun, "Constants propagated",
724 opt_stats.num_const_prop);
725 statistics_counter_event (cfun, "Copies propagated",
726 opt_stats.num_copy_prop);
728 /* Debugging dumps. */
729 if (dump_file && (dump_flags & TDF_STATS))
730 dump_dominator_optimization_stats (dump_file);
732 loop_optimizer_finalize ();
734 /* Delete our main hashtable. */
735 htab_delete (avail_exprs);
737 /* And finalize the dominator walker. */
738 fini_walk_dominator_tree (&walk_data);
740 /* Free asserted bitmaps and stacks. */
741 BITMAP_FREE (need_eh_cleanup);
743 VEC_free (expr_hash_elt_t, heap, avail_exprs_stack);
744 VEC_free (tree, heap, const_and_copies_stack);
745 VEC_free (gimple_p, heap, stmts_to_rescan);
747 /* Free the value-handle array. */
748 threadedge_finalize_values ();
749 ssa_name_values = NULL;
755 gate_dominator (void)
757 return flag_tree_dom != 0;
760 struct gimple_opt_pass pass_dominator =
765 gate_dominator, /* gate */
766 tree_ssa_dominator_optimize, /* execute */
769 0, /* static_pass_number */
770 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
771 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
772 0, /* properties_provided */
773 0, /* properties_destroyed */
774 0, /* todo_flags_start */
778 | TODO_verify_ssa /* todo_flags_finish */
783 /* Given a conditional statement CONDSTMT, convert the
784 condition to a canonical form. */
787 canonicalize_comparison (gimple condstmt)
793 gcc_assert (gimple_code (condstmt) == GIMPLE_COND);
795 op0 = gimple_cond_lhs (condstmt);
796 op1 = gimple_cond_rhs (condstmt);
798 code = gimple_cond_code (condstmt);
800 /* If it would be profitable to swap the operands, then do so to
801 canonicalize the statement, enabling better optimization.
803 By placing canonicalization of such expressions here we
804 transparently keep statements in canonical form, even
805 when the statement is modified. */
806 if (tree_swap_operands_p (op0, op1, false))
808 /* For relationals we need to swap the operands
809 and change the code. */
815 code = swap_tree_comparison (code);
817 gimple_cond_set_code (condstmt, code);
818 gimple_cond_set_lhs (condstmt, op1);
819 gimple_cond_set_rhs (condstmt, op0);
821 update_stmt (condstmt);
826 /* Initialize local stacks for this optimizer and record equivalences
827 upon entry to BB. Equivalences can come from the edge traversed to
828 reach BB or they may come from PHI nodes at the start of BB. */
831 dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
834 if (dump_file && (dump_flags & TDF_DETAILS))
835 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
837 /* Push a marker on the stacks of local information so that we know how
838 far to unwind when we finalize this block. */
839 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
840 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
842 record_equivalences_from_incoming_edge (bb);
844 /* PHI nodes can create equivalences too. */
845 record_equivalences_from_phis (bb);
848 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
849 LIMIT entries left in LOCALs. */
852 remove_local_expressions_from_table (void)
854 /* Remove all the expressions made available in this block. */
855 while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0)
857 struct expr_hash_elt element;
858 expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack);
865 /* This must precede the actual removal from the hash table,
866 as ELEMENT and the table entry may share a call argument
867 vector which will be freed during removal. */
868 if (dump_file && (dump_flags & TDF_DETAILS))
870 fprintf (dump_file, "<<<< ");
871 print_expr_hash_elt (dump_file, &element);
874 htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
878 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
879 CONST_AND_COPIES to its original state, stopping when we hit a
883 restore_vars_to_original_value (void)
885 while (VEC_length (tree, const_and_copies_stack) > 0)
887 tree prev_value, dest;
889 dest = VEC_pop (tree, const_and_copies_stack);
894 if (dump_file && (dump_flags & TDF_DETAILS))
896 fprintf (dump_file, "<<<< COPY ");
897 print_generic_expr (dump_file, dest, 0);
898 fprintf (dump_file, " = ");
899 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0);
900 fprintf (dump_file, "\n");
903 prev_value = VEC_pop (tree, const_and_copies_stack);
904 set_ssa_name_value (dest, prev_value);
908 /* A trivial wrapper so that we can present the generic jump
909 threading code with a simple API for simplifying statements. */
911 simplify_stmt_for_jump_threading (gimple stmt,
912 gimple within_stmt ATTRIBUTE_UNUSED)
914 return lookup_avail_expr (stmt, false);
917 /* Wrapper for common code to attempt to thread an edge. For example,
918 it handles lazily building the dummy condition and the bookkeeping
919 when jump threading is successful. */
922 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
924 if (! walk_data->global_data)
927 gimple_build_cond (NE_EXPR,
928 integer_zero_node, integer_zero_node,
930 walk_data->global_data = dummy_cond;
933 thread_across_edge ((gimple) walk_data->global_data, e, false,
934 &const_and_copies_stack,
935 simplify_stmt_for_jump_threading);
938 /* We have finished processing the dominator children of BB, perform
939 any finalization actions in preparation for leaving this node in
940 the dominator tree. */
943 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
947 /* If we have an outgoing edge to a block with multiple incoming and
948 outgoing edges, then we may be able to thread the edge, i.e., we
949 may be able to statically determine which of the outgoing edges
950 will be traversed when the incoming edge from BB is traversed. */
951 if (single_succ_p (bb)
952 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
953 && potentially_threadable_block (single_succ (bb)))
955 dom_thread_across_edge (walk_data, single_succ_edge (bb));
957 else if ((last = last_stmt (bb))
958 && gimple_code (last) == GIMPLE_COND
959 && EDGE_COUNT (bb->succs) == 2
960 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
961 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
963 edge true_edge, false_edge;
965 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
967 /* Only try to thread the edge if it reaches a target block with
968 more than one predecessor and more than one successor. */
969 if (potentially_threadable_block (true_edge->dest))
971 struct edge_info *edge_info;
974 /* Push a marker onto the available expression stack so that we
975 unwind any expressions related to the TRUE arm before processing
976 the false arm below. */
977 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
978 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
980 edge_info = (struct edge_info *) true_edge->aux;
982 /* If we have info associated with this edge, record it into
983 our equivalence tables. */
986 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
987 tree lhs = edge_info->lhs;
988 tree rhs = edge_info->rhs;
990 /* If we have a simple NAME = VALUE equivalence, record it. */
991 if (lhs && TREE_CODE (lhs) == SSA_NAME)
992 record_const_or_copy (lhs, rhs);
994 /* If we have 0 = COND or 1 = COND equivalences, record them
995 into our expression hash tables. */
996 if (cond_equivalences)
997 for (i = 0; i < edge_info->max_cond_equivalences; i++)
998 record_cond (&cond_equivalences[i]);
1001 dom_thread_across_edge (walk_data, true_edge);
1003 /* And restore the various tables to their state before
1004 we threaded this edge. */
1005 remove_local_expressions_from_table ();
1008 /* Similarly for the ELSE arm. */
1009 if (potentially_threadable_block (false_edge->dest))
1011 struct edge_info *edge_info;
1014 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1015 edge_info = (struct edge_info *) false_edge->aux;
1017 /* If we have info associated with this edge, record it into
1018 our equivalence tables. */
1021 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1022 tree lhs = edge_info->lhs;
1023 tree rhs = edge_info->rhs;
1025 /* If we have a simple NAME = VALUE equivalence, record it. */
1026 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1027 record_const_or_copy (lhs, rhs);
1029 /* If we have 0 = COND or 1 = COND equivalences, record them
1030 into our expression hash tables. */
1031 if (cond_equivalences)
1032 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1033 record_cond (&cond_equivalences[i]);
1036 /* Now thread the edge. */
1037 dom_thread_across_edge (walk_data, false_edge);
1039 /* No need to remove local expressions from our tables
1040 or restore vars to their original value as that will
1041 be done immediately below. */
1045 remove_local_expressions_from_table ();
1046 restore_vars_to_original_value ();
1048 /* If we queued any statements to rescan in this block, then
1049 go ahead and rescan them now. */
1050 while (VEC_length (gimple_p, stmts_to_rescan) > 0)
1052 gimple *stmt_p = VEC_last (gimple_p, stmts_to_rescan);
1053 gimple stmt = *stmt_p;
1054 basic_block stmt_bb = gimple_bb (stmt);
1059 VEC_pop (gimple_p, stmts_to_rescan);
1060 pop_stmt_changes (stmt_p);
1064 /* PHI nodes can create equivalences too.
1066 Ignoring any alternatives which are the same as the result, if
1067 all the alternatives are equal, then the PHI node creates an
1071 record_equivalences_from_phis (basic_block bb)
1073 gimple_stmt_iterator gsi;
1075 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1077 gimple phi = gsi_stmt (gsi);
1079 tree lhs = gimple_phi_result (phi);
1083 for (i = 0; i < gimple_phi_num_args (phi); i++)
1085 tree t = gimple_phi_arg_def (phi, i);
1087 /* Ignore alternatives which are the same as our LHS. Since
1088 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1089 can simply compare pointers. */
1093 /* If we have not processed an alternative yet, then set
1094 RHS to this alternative. */
1097 /* If we have processed an alternative (stored in RHS), then
1098 see if it is equal to this one. If it isn't, then stop
1100 else if (! operand_equal_for_phi_arg_p (rhs, t))
1104 /* If we had no interesting alternatives, then all the RHS alternatives
1105 must have been the same as LHS. */
1109 /* If we managed to iterate through each PHI alternative without
1110 breaking out of the loop, then we have a PHI which may create
1111 a useful equivalence. We do not need to record unwind data for
1112 this, since this is a true assignment and not an equivalence
1113 inferred from a comparison. All uses of this ssa name are dominated
1114 by this assignment, so unwinding just costs time and space. */
1115 if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs))
1116 set_ssa_name_value (lhs, rhs);
1120 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1121 return that edge. Otherwise return NULL. */
1123 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1129 FOR_EACH_EDGE (e, ei, bb->preds)
1131 /* A loop back edge can be identified by the destination of
1132 the edge dominating the source of the edge. */
1133 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1136 /* If we have already seen a non-loop edge, then we must have
1137 multiple incoming non-loop edges and thus we return NULL. */
1141 /* This is the first non-loop incoming edge we have found. Record
1149 /* Record any equivalences created by the incoming edge to BB. If BB
1150 has more than one incoming edge, then no equivalence is created. */
1153 record_equivalences_from_incoming_edge (basic_block bb)
1157 struct edge_info *edge_info;
1159 /* If our parent block ended with a control statement, then we may be
1160 able to record some equivalences based on which outgoing edge from
1161 the parent was followed. */
1162 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1164 e = single_incoming_edge_ignoring_loop_edges (bb);
1166 /* If we had a single incoming edge from our parent block, then enter
1167 any data associated with the edge into our tables. */
1168 if (e && e->src == parent)
1172 edge_info = (struct edge_info *) e->aux;
1176 tree lhs = edge_info->lhs;
1177 tree rhs = edge_info->rhs;
1178 struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences;
1181 record_equality (lhs, rhs);
1183 if (cond_equivalences)
1184 for (i = 0; i < edge_info->max_cond_equivalences; i++)
1185 record_cond (&cond_equivalences[i]);
1190 /* Dump SSA statistics on FILE. */
1193 dump_dominator_optimization_stats (FILE *file)
1195 fprintf (file, "Total number of statements: %6ld\n\n",
1196 opt_stats.num_stmts);
1197 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1198 opt_stats.num_exprs_considered);
1200 fprintf (file, "\nHash table statistics:\n");
1202 fprintf (file, " avail_exprs: ");
1203 htab_statistics (file, avail_exprs);
1207 /* Dump SSA statistics on stderr. */
1210 debug_dominator_optimization_stats (void)
1212 dump_dominator_optimization_stats (stderr);
1216 /* Dump statistics for the hash table HTAB. */
1219 htab_statistics (FILE *file, htab_t htab)
1221 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1222 (long) htab_size (htab),
1223 (long) htab_elements (htab),
1224 htab_collisions (htab));
1228 /* Enter condition equivalence into the expression hash table.
1229 This indicates that a conditional expression has a known
1233 record_cond (struct cond_equivalence *p)
1235 struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
1238 initialize_hash_element_from_expr (&p->cond, p->value, element);
1240 slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
1241 element->hash, INSERT);
1244 *slot = (void *) element;
1246 if (dump_file && (dump_flags & TDF_DETAILS))
1248 fprintf (dump_file, "1>>> ");
1249 print_expr_hash_elt (dump_file, element);
1252 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
1258 /* Build a cond_equivalence record indicating that the comparison
1259 CODE holds between operands OP0 and OP1. */
1262 build_and_record_new_cond (enum tree_code code,
1264 struct cond_equivalence *p)
1266 struct hashable_expr *cond = &p->cond;
1268 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
1270 cond->type = boolean_type_node;
1271 cond->kind = EXPR_BINARY;
1272 cond->ops.binary.op = code;
1273 cond->ops.binary.opnd0 = op0;
1274 cond->ops.binary.opnd1 = op1;
1276 p->value = boolean_true_node;
1279 /* Record that COND is true and INVERTED is false into the edge information
1280 structure. Also record that any conditions dominated by COND are true
1283 For example, if a < b is true, then a <= b must also be true. */
1286 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
1290 if (!COMPARISON_CLASS_P (cond))
1293 op0 = TREE_OPERAND (cond, 0);
1294 op1 = TREE_OPERAND (cond, 1);
1296 switch (TREE_CODE (cond))
1300 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1302 edge_info->max_cond_equivalences = 6;
1303 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 6);
1304 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1305 &edge_info->cond_equivalences[4]);
1306 build_and_record_new_cond (LTGT_EXPR, op0, op1,
1307 &edge_info->cond_equivalences[5]);
1311 edge_info->max_cond_equivalences = 4;
1312 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1315 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
1316 ? LE_EXPR : GE_EXPR),
1317 op0, op1, &edge_info->cond_equivalences[2]);
1318 build_and_record_new_cond (NE_EXPR, op0, op1,
1319 &edge_info->cond_equivalences[3]);
1324 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1326 edge_info->max_cond_equivalences = 3;
1327 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 3);
1328 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1329 &edge_info->cond_equivalences[2]);
1333 edge_info->max_cond_equivalences = 2;
1334 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1339 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1341 edge_info->max_cond_equivalences = 5;
1342 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 5);
1343 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1344 &edge_info->cond_equivalences[4]);
1348 edge_info->max_cond_equivalences = 4;
1349 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1351 build_and_record_new_cond (LE_EXPR, op0, op1,
1352 &edge_info->cond_equivalences[2]);
1353 build_and_record_new_cond (GE_EXPR, op0, op1,
1354 &edge_info->cond_equivalences[3]);
1357 case UNORDERED_EXPR:
1358 edge_info->max_cond_equivalences = 8;
1359 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 8);
1360 build_and_record_new_cond (NE_EXPR, op0, op1,
1361 &edge_info->cond_equivalences[2]);
1362 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1363 &edge_info->cond_equivalences[3]);
1364 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1365 &edge_info->cond_equivalences[4]);
1366 build_and_record_new_cond (UNEQ_EXPR, op0, op1,
1367 &edge_info->cond_equivalences[5]);
1368 build_and_record_new_cond (UNLT_EXPR, op0, op1,
1369 &edge_info->cond_equivalences[6]);
1370 build_and_record_new_cond (UNGT_EXPR, op0, op1,
1371 &edge_info->cond_equivalences[7]);
1376 edge_info->max_cond_equivalences = 4;
1377 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1378 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1379 ? UNLE_EXPR : UNGE_EXPR),
1380 op0, op1, &edge_info->cond_equivalences[2]);
1381 build_and_record_new_cond (NE_EXPR, op0, op1,
1382 &edge_info->cond_equivalences[3]);
1386 edge_info->max_cond_equivalences = 4;
1387 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1388 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1389 &edge_info->cond_equivalences[2]);
1390 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1391 &edge_info->cond_equivalences[3]);
1395 edge_info->max_cond_equivalences = 4;
1396 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 4);
1397 build_and_record_new_cond (NE_EXPR, op0, op1,
1398 &edge_info->cond_equivalences[2]);
1399 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1400 &edge_info->cond_equivalences[3]);
1404 edge_info->max_cond_equivalences = 2;
1405 edge_info->cond_equivalences = XNEWVEC (struct cond_equivalence, 2);
1409 /* Now store the original true and false conditions into the first
1411 initialize_expr_from_cond (cond, &edge_info->cond_equivalences[0].cond);
1412 edge_info->cond_equivalences[0].value = boolean_true_node;
1414 /* It is possible for INVERTED to be the negation of a comparison,
1415 and not a valid RHS or GIMPLE_COND condition. This happens because
1416 invert_truthvalue may return such an expression when asked to invert
1417 a floating-point comparison. These comparisons are not assumed to
1418 obey the trichotomy law. */
1419 initialize_expr_from_cond (inverted, &edge_info->cond_equivalences[1].cond);
1420 edge_info->cond_equivalences[1].value = boolean_false_node;
1423 /* A helper function for record_const_or_copy and record_equality.
1424 Do the work of recording the value and undo info. */
1427 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1429 set_ssa_name_value (x, y);
1431 if (dump_file && (dump_flags & TDF_DETAILS))
1433 fprintf (dump_file, "0>>> COPY ");
1434 print_generic_expr (dump_file, x, 0);
1435 fprintf (dump_file, " = ");
1436 print_generic_expr (dump_file, y, 0);
1437 fprintf (dump_file, "\n");
1440 VEC_reserve (tree, heap, const_and_copies_stack, 2);
1441 VEC_quick_push (tree, const_and_copies_stack, prev_x);
1442 VEC_quick_push (tree, const_and_copies_stack, x);
1445 /* Return the loop depth of the basic block of the defining statement of X.
1446 This number should not be treated as absolutely correct because the loop
1447 information may not be completely up-to-date when dom runs. However, it
1448 will be relatively correct, and as more passes are taught to keep loop info
1449 up to date, the result will become more and more accurate. */
1452 loop_depth_of_name (tree x)
1457 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1458 if (TREE_CODE (x) != SSA_NAME)
1461 /* Otherwise return the loop depth of the defining statement's bb.
1462 Note that there may not actually be a bb for this statement, if the
1463 ssa_name is live on entry. */
1464 defstmt = SSA_NAME_DEF_STMT (x);
1465 defbb = gimple_bb (defstmt);
1469 return defbb->loop_depth;
1472 /* Record that X is equal to Y in const_and_copies. Record undo
1473 information in the block-local vector. */
1476 record_const_or_copy (tree x, tree y)
1478 tree prev_x = SSA_NAME_VALUE (x);
1480 gcc_assert (TREE_CODE (x) == SSA_NAME);
1482 if (TREE_CODE (y) == SSA_NAME)
1484 tree tmp = SSA_NAME_VALUE (y);
1489 record_const_or_copy_1 (x, y, prev_x);
1492 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1493 This constrains the cases in which we may treat this as assignment. */
1496 record_equality (tree x, tree y)
1498 tree prev_x = NULL, prev_y = NULL;
1500 if (TREE_CODE (x) == SSA_NAME)
1501 prev_x = SSA_NAME_VALUE (x);
1502 if (TREE_CODE (y) == SSA_NAME)
1503 prev_y = SSA_NAME_VALUE (y);
1505 /* If one of the previous values is invariant, or invariant in more loops
1506 (by depth), then use that.
1507 Otherwise it doesn't matter which value we choose, just so
1508 long as we canonicalize on one value. */
1509 if (is_gimple_min_invariant (y))
1511 else if (is_gimple_min_invariant (x)
1512 || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
1513 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1514 else if (prev_x && is_gimple_min_invariant (prev_x))
1515 x = y, y = prev_x, prev_x = prev_y;
1519 /* After the swapping, we must have one SSA_NAME. */
1520 if (TREE_CODE (x) != SSA_NAME)
1523 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1524 variable compared against zero. If we're honoring signed zeros,
1525 then we cannot record this value unless we know that the value is
1527 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1528 && (TREE_CODE (y) != REAL_CST
1529 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1532 record_const_or_copy_1 (x, y, prev_x);
1535 /* Returns true when STMT is a simple iv increment. It detects the
1536 following situation:
1538 i_1 = phi (..., i_2)
1539 i_2 = i_1 +/- ... */
1542 simple_iv_increment_p (gimple stmt)
1548 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1551 lhs = gimple_assign_lhs (stmt);
1552 if (TREE_CODE (lhs) != SSA_NAME)
1555 if (gimple_assign_rhs_code (stmt) != PLUS_EXPR
1556 && gimple_assign_rhs_code (stmt) != MINUS_EXPR)
1559 preinc = gimple_assign_rhs1 (stmt);
1561 if (TREE_CODE (preinc) != SSA_NAME)
1564 phi = SSA_NAME_DEF_STMT (preinc);
1565 if (gimple_code (phi) != GIMPLE_PHI)
1568 for (i = 0; i < gimple_phi_num_args (phi); i++)
1569 if (gimple_phi_arg_def (phi, i) == lhs)
1575 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1576 known value for that SSA_NAME (or NULL if no value is known).
1578 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1579 successors of BB. */
1582 cprop_into_successor_phis (basic_block bb)
1587 FOR_EACH_EDGE (e, ei, bb->succs)
1590 gimple_stmt_iterator gsi;
1592 /* If this is an abnormal edge, then we do not want to copy propagate
1593 into the PHI alternative associated with this edge. */
1594 if (e->flags & EDGE_ABNORMAL)
1597 gsi = gsi_start_phis (e->dest);
1598 if (gsi_end_p (gsi))
1602 for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1605 use_operand_p orig_p;
1607 gimple phi = gsi_stmt (gsi);
1609 /* The alternative may be associated with a constant, so verify
1610 it is an SSA_NAME before doing anything with it. */
1611 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1612 orig_val = get_use_from_ptr (orig_p);
1613 if (TREE_CODE (orig_val) != SSA_NAME)
1616 /* If we have *ORIG_P in our constant/copy table, then replace
1617 ORIG_P with its value in our constant/copy table. */
1618 new_val = SSA_NAME_VALUE (orig_val);
1620 && new_val != orig_val
1621 && (TREE_CODE (new_val) == SSA_NAME
1622 || is_gimple_min_invariant (new_val))
1623 && may_propagate_copy (orig_val, new_val))
1624 propagate_value (orig_p, new_val);
1629 /* We have finished optimizing BB, record any information implied by
1630 taking a specific outgoing edge from BB. */
1633 record_edge_info (basic_block bb)
1635 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1636 struct edge_info *edge_info;
1638 if (! gsi_end_p (gsi))
1640 gimple stmt = gsi_stmt (gsi);
1642 if (gimple_code (stmt) == GIMPLE_SWITCH)
1644 tree index = gimple_switch_index (stmt);
1646 if (TREE_CODE (index) == SSA_NAME)
1649 int n_labels = gimple_switch_num_labels (stmt);
1650 tree *info = XCNEWVEC (tree, last_basic_block);
1654 for (i = 0; i < n_labels; i++)
1656 tree label = gimple_switch_label (stmt, i);
1657 basic_block target_bb = label_to_block (CASE_LABEL (label));
1658 if (CASE_HIGH (label)
1659 || !CASE_LOW (label)
1660 || info[target_bb->index])
1661 info[target_bb->index] = error_mark_node;
1663 info[target_bb->index] = label;
1666 FOR_EACH_EDGE (e, ei, bb->succs)
1668 basic_block target_bb = e->dest;
1669 tree label = info[target_bb->index];
1671 if (label != NULL && label != error_mark_node)
1673 tree x = fold_convert (TREE_TYPE (index), CASE_LOW (label));
1674 edge_info = allocate_edge_info (e);
1675 edge_info->lhs = index;
1683 /* A COND_EXPR may create equivalences too. */
1684 if (gimple_code (stmt) == GIMPLE_COND)
1689 tree op0 = gimple_cond_lhs (stmt);
1690 tree op1 = gimple_cond_rhs (stmt);
1691 enum tree_code code = gimple_cond_code (stmt);
1693 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1695 /* Special case comparing booleans against a constant as we
1696 know the value of OP0 on both arms of the branch. i.e., we
1697 can record an equivalence for OP0 rather than COND. */
1698 if ((code == EQ_EXPR || code == NE_EXPR)
1699 && TREE_CODE (op0) == SSA_NAME
1700 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
1701 && is_gimple_min_invariant (op1))
1703 if (code == EQ_EXPR)
1705 edge_info = allocate_edge_info (true_edge);
1706 edge_info->lhs = op0;
1707 edge_info->rhs = (integer_zerop (op1)
1708 ? boolean_false_node
1709 : boolean_true_node);
1711 edge_info = allocate_edge_info (false_edge);
1712 edge_info->lhs = op0;
1713 edge_info->rhs = (integer_zerop (op1)
1715 : boolean_false_node);
1719 edge_info = allocate_edge_info (true_edge);
1720 edge_info->lhs = op0;
1721 edge_info->rhs = (integer_zerop (op1)
1723 : boolean_false_node);
1725 edge_info = allocate_edge_info (false_edge);
1726 edge_info->lhs = op0;
1727 edge_info->rhs = (integer_zerop (op1)
1728 ? boolean_false_node
1729 : boolean_true_node);
1732 else if (is_gimple_min_invariant (op0)
1733 && (TREE_CODE (op1) == SSA_NAME
1734 || is_gimple_min_invariant (op1)))
1736 tree cond = build2 (code, boolean_type_node, op0, op1);
1737 tree inverted = invert_truthvalue (cond);
1738 struct edge_info *edge_info;
1740 edge_info = allocate_edge_info (true_edge);
1741 record_conditions (edge_info, cond, inverted);
1743 if (code == EQ_EXPR)
1745 edge_info->lhs = op1;
1746 edge_info->rhs = op0;
1749 edge_info = allocate_edge_info (false_edge);
1750 record_conditions (edge_info, inverted, cond);
1752 if (code == NE_EXPR)
1754 edge_info->lhs = op1;
1755 edge_info->rhs = op0;
1759 else if (TREE_CODE (op0) == SSA_NAME
1760 && (is_gimple_min_invariant (op1)
1761 || TREE_CODE (op1) == SSA_NAME))
1763 tree cond = build2 (code, boolean_type_node, op0, op1);
1764 tree inverted = invert_truthvalue (cond);
1765 struct edge_info *edge_info;
1767 edge_info = allocate_edge_info (true_edge);
1768 record_conditions (edge_info, cond, inverted);
1770 if (code == EQ_EXPR)
1772 edge_info->lhs = op0;
1773 edge_info->rhs = op1;
1776 edge_info = allocate_edge_info (false_edge);
1777 record_conditions (edge_info, inverted, cond);
1779 if (TREE_CODE (cond) == NE_EXPR)
1781 edge_info->lhs = op0;
1782 edge_info->rhs = op1;
1787 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1791 /* Propagate information from BB to its outgoing edges.
1793 This can include equivalence information implied by control statements
1794 at the end of BB and const/copy propagation into PHIs in BB's
1795 successor blocks. */
1798 propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1801 record_edge_info (bb);
1802 cprop_into_successor_phis (bb);
1805 /* Search for redundant computations in STMT. If any are found, then
1806 replace them with the variable holding the result of the computation.
1808 If safe, record this expression into the available expression hash
1812 eliminate_redundant_computations (gimple_stmt_iterator* gsi)
1817 bool retval = false;
1818 bool assigns_var_p = false;
1820 gimple stmt = gsi_stmt (*gsi);
1822 tree def = gimple_get_lhs (stmt);
1824 /* Certain expressions on the RHS can be optimized away, but can not
1825 themselves be entered into the hash tables. */
1827 || TREE_CODE (def) != SSA_NAME
1828 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1829 || gimple_vdef (stmt)
1830 /* Do not record equivalences for increments of ivs. This would create
1831 overlapping live ranges for a very questionable gain. */
1832 || simple_iv_increment_p (stmt))
1835 /* Check if the expression has been computed before. */
1836 cached_lhs = lookup_avail_expr (stmt, insert);
1838 opt_stats.num_exprs_considered++;
1840 /* Get the type of the expression we are trying to optimize. */
1841 if (is_gimple_assign (stmt))
1843 expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1844 assigns_var_p = true;
1846 else if (gimple_code (stmt) == GIMPLE_COND)
1847 expr_type = boolean_type_node;
1848 else if (is_gimple_call (stmt))
1850 gcc_assert (gimple_call_lhs (stmt));
1851 expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1852 assigns_var_p = true;
1854 else if (gimple_code (stmt) == GIMPLE_SWITCH)
1855 expr_type = TREE_TYPE (gimple_switch_index (stmt));
1862 /* It is safe to ignore types here since we have already done
1863 type checking in the hashing and equality routines. In fact
1864 type checking here merely gets in the way of constant
1865 propagation. Also, make sure that it is safe to propagate
1866 CACHED_LHS into the expression in STMT. */
1867 if ((TREE_CODE (cached_lhs) != SSA_NAME
1869 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1870 || may_propagate_copy_into_stmt (stmt, cached_lhs))
1872 #if defined ENABLE_CHECKING
1873 gcc_assert (TREE_CODE (cached_lhs) == SSA_NAME
1874 || is_gimple_min_invariant (cached_lhs));
1877 if (dump_file && (dump_flags & TDF_DETAILS))
1879 fprintf (dump_file, " Replaced redundant expr '");
1880 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1881 fprintf (dump_file, "' with '");
1882 print_generic_expr (dump_file, cached_lhs, dump_flags);
1883 fprintf (dump_file, "'\n");
1888 if (TREE_CODE (cached_lhs) == ADDR_EXPR
1889 || (POINTER_TYPE_P (expr_type)
1890 && is_gimple_min_invariant (cached_lhs)))
1894 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1895 cached_lhs = fold_convert (expr_type, cached_lhs);
1897 propagate_tree_value_into_stmt (gsi, cached_lhs);
1899 /* Since it is always necessary to mark the result as modified,
1900 perhaps we should move this into propagate_tree_value_into_stmt
1902 gimple_set_modified (gsi_stmt (*gsi), true);
1907 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1908 the available expressions table or the const_and_copies table.
1909 Detect and record those equivalences. */
1910 /* We handle only very simple copy equivalences here. The heavy
1911 lifing is done by eliminate_redundant_computations. */
1914 record_equivalences_from_stmt (gimple stmt, int may_optimize_p)
1917 enum tree_code lhs_code;
1919 gcc_assert (is_gimple_assign (stmt));
1921 lhs = gimple_assign_lhs (stmt);
1922 lhs_code = TREE_CODE (lhs);
1924 if (lhs_code == SSA_NAME
1925 && gimple_assign_single_p (stmt))
1927 tree rhs = gimple_assign_rhs1 (stmt);
1929 /* If the RHS of the assignment is a constant or another variable that
1930 may be propagated, register it in the CONST_AND_COPIES table. We
1931 do not need to record unwind data for this, since this is a true
1932 assignment and not an equivalence inferred from a comparison. All
1933 uses of this ssa name are dominated by this assignment, so unwinding
1934 just costs time and space. */
1936 && (TREE_CODE (rhs) == SSA_NAME
1937 || is_gimple_min_invariant (rhs)))
1939 if (dump_file && (dump_flags & TDF_DETAILS))
1941 fprintf (dump_file, "==== ASGN ");
1942 print_generic_expr (dump_file, lhs, 0);
1943 fprintf (dump_file, " = ");
1944 print_generic_expr (dump_file, rhs, 0);
1945 fprintf (dump_file, "\n");
1948 set_ssa_name_value (lhs, rhs);
1952 /* A memory store, even an aliased store, creates a useful
1953 equivalence. By exchanging the LHS and RHS, creating suitable
1954 vops and recording the result in the available expression table,
1955 we may be able to expose more redundant loads. */
1956 if (!gimple_has_volatile_ops (stmt)
1957 && gimple_references_memory_p (stmt)
1958 && gimple_assign_single_p (stmt)
1959 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1960 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1961 && !is_gimple_reg (lhs))
1963 tree rhs = gimple_assign_rhs1 (stmt);
1966 /* Build a new statement with the RHS and LHS exchanged. */
1967 if (TREE_CODE (rhs) == SSA_NAME)
1969 /* NOTE tuples. The call to gimple_build_assign below replaced
1970 a call to build_gimple_modify_stmt, which did not set the
1971 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1972 may cause an SSA validation failure, as the LHS may be a
1973 default-initialized name and should have no definition. I'm
1974 a bit dubious of this, as the artificial statement that we
1975 generate here may in fact be ill-formed, but it is simply
1976 used as an internal device in this pass, and never becomes
1978 gimple defstmt = SSA_NAME_DEF_STMT (rhs);
1979 new_stmt = gimple_build_assign (rhs, lhs);
1980 SSA_NAME_DEF_STMT (rhs) = defstmt;
1983 new_stmt = gimple_build_assign (rhs, lhs);
1985 gimple_set_vuse (new_stmt, gimple_vdef (stmt));
1987 /* Finally enter the statement into the available expression
1989 lookup_avail_expr (new_stmt, true);
1993 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1994 CONST_AND_COPIES. */
1997 cprop_operand (gimple stmt, use_operand_p op_p)
1999 bool may_have_exposed_new_symbols = false;
2001 tree op = USE_FROM_PTR (op_p);
2003 /* If the operand has a known constant value or it is known to be a
2004 copy of some other variable, use the value or copy stored in
2005 CONST_AND_COPIES. */
2006 val = SSA_NAME_VALUE (op);
2007 if (val && val != op)
2009 /* Do not change the base variable in the virtual operand
2010 tables. That would make it impossible to reconstruct
2011 the renamed virtual operand if we later modify this
2012 statement. Also only allow the new value to be an SSA_NAME
2013 for propagation into virtual operands. */
2014 if (!is_gimple_reg (op)
2015 && (TREE_CODE (val) != SSA_NAME
2016 || is_gimple_reg (val)
2017 || get_virtual_var (val) != get_virtual_var (op)))
2020 /* Do not replace hard register operands in asm statements. */
2021 if (gimple_code (stmt) == GIMPLE_ASM
2022 && !may_propagate_copy_into_asm (op))
2025 /* Certain operands are not allowed to be copy propagated due
2026 to their interaction with exception handling and some GCC
2028 if (!may_propagate_copy (op, val))
2031 /* Do not propagate addresses that point to volatiles into memory
2032 stmts without volatile operands. */
2033 if (POINTER_TYPE_P (TREE_TYPE (val))
2034 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val)))
2035 && gimple_has_mem_ops (stmt)
2036 && !gimple_has_volatile_ops (stmt))
2039 /* Do not propagate copies if the propagated value is at a deeper loop
2040 depth than the propagatee. Otherwise, this may move loop variant
2041 variables outside of their loops and prevent coalescing
2042 opportunities. If the value was loop invariant, it will be hoisted
2043 by LICM and exposed for copy propagation. */
2044 if (loop_depth_of_name (val) > loop_depth_of_name (op))
2048 if (dump_file && (dump_flags & TDF_DETAILS))
2050 fprintf (dump_file, " Replaced '");
2051 print_generic_expr (dump_file, op, dump_flags);
2052 fprintf (dump_file, "' with %s '",
2053 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2054 print_generic_expr (dump_file, val, dump_flags);
2055 fprintf (dump_file, "'\n");
2058 /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2059 that we may have exposed a new symbol for SSA renaming. */
2060 if (TREE_CODE (val) == ADDR_EXPR
2061 || (POINTER_TYPE_P (TREE_TYPE (op))
2062 && is_gimple_min_invariant (val)))
2063 may_have_exposed_new_symbols = true;
2065 if (TREE_CODE (val) != SSA_NAME)
2066 opt_stats.num_const_prop++;
2068 opt_stats.num_copy_prop++;
2070 propagate_value (op_p, val);
2072 /* And note that we modified this statement. This is now
2073 safe, even if we changed virtual operands since we will
2074 rescan the statement and rewrite its operands again. */
2075 gimple_set_modified (stmt, true);
2077 return may_have_exposed_new_symbols;
2080 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2081 known value for that SSA_NAME (or NULL if no value is known).
2083 Propagate values from CONST_AND_COPIES into the uses, vuses and
2084 vdef_ops of STMT. */
2087 cprop_into_stmt (gimple stmt)
2089 bool may_have_exposed_new_symbols = false;
2093 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
2095 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
2096 may_have_exposed_new_symbols |= cprop_operand (stmt, op_p);
2099 return may_have_exposed_new_symbols;
2102 /* Optimize the statement pointed to by iterator SI.
2104 We try to perform some simplistic global redundancy elimination and
2105 constant propagation:
2107 1- To detect global redundancy, we keep track of expressions that have
2108 been computed in this block and its dominators. If we find that the
2109 same expression is computed more than once, we eliminate repeated
2110 computations by using the target of the first one.
2112 2- Constant values and copy assignments. This is used to do very
2113 simplistic constant and copy propagation. When a constant or copy
2114 assignment is found, we map the value on the RHS of the assignment to
2115 the variable in the LHS in the CONST_AND_COPIES table. */
2118 optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2119 basic_block bb, gimple_stmt_iterator si)
2121 gimple stmt, old_stmt;
2122 bool may_optimize_p;
2123 bool may_have_exposed_new_symbols;
2124 bool modified_p = false;
2126 old_stmt = stmt = gsi_stmt (si);
2128 if (gimple_code (stmt) == GIMPLE_COND)
2129 canonicalize_comparison (stmt);
2131 update_stmt_if_modified (stmt);
2132 opt_stats.num_stmts++;
2133 push_stmt_changes (gsi_stmt_ptr (&si));
2135 if (dump_file && (dump_flags & TDF_DETAILS))
2137 fprintf (dump_file, "Optimizing statement ");
2138 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2141 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2142 may_have_exposed_new_symbols = cprop_into_stmt (stmt);
2144 /* If the statement has been modified with constant replacements,
2145 fold its RHS before checking for redundant computations. */
2146 if (gimple_modified_p (stmt))
2150 /* Try to fold the statement making sure that STMT is kept
2152 if (fold_stmt (&si))
2154 stmt = gsi_stmt (si);
2156 if (dump_file && (dump_flags & TDF_DETAILS))
2158 fprintf (dump_file, " Folded to: ");
2159 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2163 /* We only need to consider cases that can yield a gimple operand. */
2164 if (gimple_assign_single_p (stmt))
2165 rhs = gimple_assign_rhs1 (stmt);
2166 else if (gimple_code (stmt) == GIMPLE_GOTO)
2167 rhs = gimple_goto_dest (stmt);
2168 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2169 /* This should never be an ADDR_EXPR. */
2170 rhs = gimple_switch_index (stmt);
2172 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
2173 recompute_tree_invariant_for_addr_expr (rhs);
2175 /* Constant/copy propagation above may change the set of
2176 virtual operands associated with this statement. Folding
2177 may remove the need for some virtual operands.
2179 Indicate we will need to rescan and rewrite the statement. */
2180 may_have_exposed_new_symbols = true;
2181 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2182 even if fold_stmt updated the stmt already and thus cleared
2183 gimple_modified_p flag on it. */
2187 /* Check for redundant computations. Do this optimization only
2188 for assignments that have no volatile ops and conditionals. */
2189 may_optimize_p = (!gimple_has_volatile_ops (stmt)
2190 && ((is_gimple_assign (stmt)
2191 && !gimple_rhs_has_side_effects (stmt))
2192 || (is_gimple_call (stmt)
2193 && gimple_call_lhs (stmt) != NULL_TREE
2194 && !gimple_rhs_has_side_effects (stmt))
2195 || gimple_code (stmt) == GIMPLE_COND
2196 || gimple_code (stmt) == GIMPLE_SWITCH));
2200 may_have_exposed_new_symbols |= eliminate_redundant_computations (&si);
2201 stmt = gsi_stmt (si);
2204 /* Record any additional equivalences created by this statement. */
2205 if (is_gimple_assign (stmt))
2206 record_equivalences_from_stmt (stmt, may_optimize_p);
2208 /* If STMT is a COND_EXPR and it was modified, then we may know
2209 where it goes. If that is the case, then mark the CFG as altered.
2211 This will cause us to later call remove_unreachable_blocks and
2212 cleanup_tree_cfg when it is safe to do so. It is not safe to
2213 clean things up here since removal of edges and such can trigger
2214 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2217 That's all fine and good, except that once SSA_NAMEs are released
2218 to the manager, we must not call create_ssa_name until all references
2219 to released SSA_NAMEs have been eliminated.
2221 All references to the deleted SSA_NAMEs can not be eliminated until
2222 we remove unreachable blocks.
2224 We can not remove unreachable blocks until after we have completed
2225 any queued jump threading.
2227 We can not complete any queued jump threads until we have taken
2228 appropriate variables out of SSA form. Taking variables out of
2229 SSA form can call create_ssa_name and thus we lose.
2231 Ultimately I suspect we're going to need to change the interface
2232 into the SSA_NAME manager. */
2233 if (gimple_modified_p (stmt) || modified_p)
2237 if (gimple_code (stmt) == GIMPLE_COND)
2238 val = fold_binary (gimple_cond_code (stmt), boolean_type_node,
2239 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
2240 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2241 val = gimple_switch_index (stmt);
2243 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
2246 /* If we simplified a statement in such a way as to be shown that it
2247 cannot trap, update the eh information and the cfg to match. */
2248 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
2250 bitmap_set_bit (need_eh_cleanup, bb->index);
2251 if (dump_file && (dump_flags & TDF_DETAILS))
2252 fprintf (dump_file, " Flagged to clear EH edges.\n");
2256 if (may_have_exposed_new_symbols)
2258 /* Queue the statement to be re-scanned after all the
2259 AVAIL_EXPRS have been processed. The change buffer stack for
2260 all the pushed statements will be processed when this queue
2262 VEC_safe_push (gimple_p, heap, stmts_to_rescan, gsi_stmt_ptr (&si));
2266 /* Otherwise, just discard the recently pushed change buffer. If
2267 not, the STMTS_TO_RESCAN queue will get out of synch with the
2268 change buffer stack. */
2269 discard_stmt_changes (gsi_stmt_ptr (&si));
2273 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
2274 If found, return its LHS. Otherwise insert STMT in the table and
2277 Also, when an expression is first inserted in the table, it is also
2278 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
2279 we finish processing this block and its children. */
2282 lookup_avail_expr (gimple stmt, bool insert)
2287 struct expr_hash_elt *element = XNEW (struct expr_hash_elt);
2289 /* Get LHS of assignment or call, else NULL_TREE. */
2290 lhs = gimple_get_lhs (stmt);
2292 initialize_hash_element (stmt, lhs, element);
2294 if (dump_file && (dump_flags & TDF_DETAILS))
2296 fprintf (dump_file, "LKUP ");
2297 print_expr_hash_elt (dump_file, element);
2300 /* Don't bother remembering constant assignments and copy operations.
2301 Constants and copy operations are handled by the constant/copy propagator
2302 in optimize_stmt. */
2303 if (element->expr.kind == EXPR_SINGLE
2304 && (TREE_CODE (element->expr.ops.single.rhs) == SSA_NAME
2305 || is_gimple_min_invariant (element->expr.ops.single.rhs)))
2311 /* Finally try to find the expression in the main expression hash table. */
2312 slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
2313 (insert ? INSERT : NO_INSERT));
2322 *slot = (void *) element;
2324 if (dump_file && (dump_flags & TDF_DETAILS))
2326 fprintf (dump_file, "2>>> ");
2327 print_expr_hash_elt (dump_file, element);
2330 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
2334 /* Extract the LHS of the assignment so that it can be used as the current
2335 definition of another variable. */
2336 lhs = ((struct expr_hash_elt *)*slot)->lhs;
2338 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2339 use the value from the const_and_copies table. */
2340 if (TREE_CODE (lhs) == SSA_NAME)
2342 temp = SSA_NAME_VALUE (lhs);
2349 if (dump_file && (dump_flags & TDF_DETAILS))
2351 fprintf (dump_file, "FIND: ");
2352 print_generic_expr (dump_file, lhs, 0);
2353 fprintf (dump_file, "\n");
2359 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number
2360 for expressions using the code of the expression and the SSA numbers of
2364 avail_expr_hash (const void *p)
2366 gimple stmt = ((const struct expr_hash_elt *)p)->stmt;
2367 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr;
2371 val = iterative_hash_hashable_expr (expr, val);
2373 /* If the hash table entry is not associated with a statement, then we
2374 can just hash the expression and not worry about virtual operands
2379 /* Add the SSA version numbers of the vuse operand. This is important
2380 because compound variables like arrays are not renamed in the
2381 operands. Rather, the rename is done on the virtual variable
2382 representing all the elements of the array. */
2383 if ((vuse = gimple_vuse (stmt)))
2384 val = iterative_hash_expr (vuse, val);
2390 real_avail_expr_hash (const void *p)
2392 return ((const struct expr_hash_elt *)p)->hash;
2396 avail_expr_eq (const void *p1, const void *p2)
2398 gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
2399 const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr;
2400 const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp;
2401 gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
2402 const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr;
2403 const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp;
2405 /* This case should apply only when removing entries from the table. */
2406 if (stamp1 == stamp2)
2410 We add stmts to a hash table and them modify them. To detect the case
2411 that we modify a stmt and then search for it, we assume that the hash
2412 is always modified by that change.
2413 We have to fully check why this doesn't happen on trunk or rewrite
2414 this in a more reliable (and easier to understand) way. */
2415 if (((const struct expr_hash_elt *)p1)->hash
2416 != ((const struct expr_hash_elt *)p2)->hash)
2419 /* In case of a collision, both RHS have to be identical and have the
2420 same VUSE operands. */
2421 if (hashable_expr_equal_p (expr1, expr2)
2422 && types_compatible_p (expr1->type, expr2->type))
2424 /* Note that STMT1 and/or STMT2 may be NULL. */
2425 return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE)
2426 == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE));
2432 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2433 up degenerate PHIs created by or exposed by jump threading. */
2435 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2439 degenerate_phi_result (gimple phi)
2441 tree lhs = gimple_phi_result (phi);
2445 /* Ignoring arguments which are the same as LHS, if all the remaining
2446 arguments are the same, then the PHI is a degenerate and has the
2447 value of that common argument. */
2448 for (i = 0; i < gimple_phi_num_args (phi); i++)
2450 tree arg = gimple_phi_arg_def (phi, i);
2456 else if (!operand_equal_p (arg, val, 0))
2459 return (i == gimple_phi_num_args (phi) ? val : NULL);
2462 /* Given a statement STMT, which is either a PHI node or an assignment,
2463 remove it from the IL. */
2466 remove_stmt_or_phi (gimple stmt)
2468 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
2470 if (gimple_code (stmt) == GIMPLE_PHI)
2471 remove_phi_node (&gsi, true);
2474 gsi_remove (&gsi, true);
2475 release_defs (stmt);
2479 /* Given a statement STMT, which is either a PHI node or an assignment,
2480 return the "rhs" of the node, in the case of a non-degenerate
2481 phi, NULL is returned. */
2484 get_rhs_or_phi_arg (gimple stmt)
2486 if (gimple_code (stmt) == GIMPLE_PHI)
2487 return degenerate_phi_result (stmt);
2488 else if (gimple_assign_single_p (stmt))
2489 return gimple_assign_rhs1 (stmt);
2495 /* Given a statement STMT, which is either a PHI node or an assignment,
2496 return the "lhs" of the node. */
2499 get_lhs_or_phi_result (gimple stmt)
2501 if (gimple_code (stmt) == GIMPLE_PHI)
2502 return gimple_phi_result (stmt);
2503 else if (is_gimple_assign (stmt))
2504 return gimple_assign_lhs (stmt);
2509 /* Propagate RHS into all uses of LHS (when possible).
2511 RHS and LHS are derived from STMT, which is passed in solely so
2512 that we can remove it if propagation is successful.
2514 When propagating into a PHI node or into a statement which turns
2515 into a trivial copy or constant initialization, set the
2516 appropriate bit in INTERESTING_NAMEs so that we will visit those
2517 nodes as well in an effort to pick up secondary optimization
2521 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
2523 /* First verify that propagation is valid and isn't going to move a
2524 loop variant variable outside its loop. */
2525 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
2526 && (TREE_CODE (rhs) != SSA_NAME
2527 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
2528 && may_propagate_copy (lhs, rhs)
2529 && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
2531 use_operand_p use_p;
2532 imm_use_iterator iter;
2537 if (dump_file && (dump_flags & TDF_DETAILS))
2539 fprintf (dump_file, " Replacing '");
2540 print_generic_expr (dump_file, lhs, dump_flags);
2541 fprintf (dump_file, "' with %s '",
2542 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
2543 print_generic_expr (dump_file, rhs, dump_flags);
2544 fprintf (dump_file, "'\n");
2547 /* Walk over every use of LHS and try to replace the use with RHS.
2548 At this point the only reason why such a propagation would not
2549 be successful would be if the use occurs in an ASM_EXPR. */
2550 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
2553 /* It's not always safe to propagate into an ASM_EXPR. */
2554 if (gimple_code (use_stmt) == GIMPLE_ASM
2555 && ! may_propagate_copy_into_asm (lhs))
2562 if (dump_file && (dump_flags & TDF_DETAILS))
2564 fprintf (dump_file, " Original statement:");
2565 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2568 push_stmt_changes (&use_stmt);
2570 /* Propagate the RHS into this use of the LHS. */
2571 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2572 propagate_value (use_p, rhs);
2574 /* Special cases to avoid useless calls into the folding
2575 routines, operand scanning, etc.
2577 First, propagation into a PHI may cause the PHI to become
2578 a degenerate, so mark the PHI as interesting. No other
2579 actions are necessary.
2581 Second, if we're propagating a virtual operand and the
2582 propagation does not change the underlying _DECL node for
2583 the virtual operand, then no further actions are necessary. */
2584 if (gimple_code (use_stmt) == GIMPLE_PHI
2585 || (! is_gimple_reg (lhs)
2586 && TREE_CODE (rhs) == SSA_NAME
2587 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
2590 if (dump_file && (dump_flags & TDF_DETAILS))
2592 fprintf (dump_file, " Updated statement:");
2593 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2596 /* Propagation into a PHI may expose new degenerate PHIs,
2597 so mark the result of the PHI as interesting. */
2598 if (gimple_code (use_stmt) == GIMPLE_PHI)
2600 tree result = get_lhs_or_phi_result (use_stmt);
2601 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2604 discard_stmt_changes (&use_stmt);
2608 /* From this point onward we are propagating into a
2609 real statement. Folding may (or may not) be possible,
2610 we may expose new operands, expose dead EH edges,
2612 /* NOTE tuples. In the tuples world, fold_stmt_inplace
2613 cannot fold a call that simplifies to a constant,
2614 because the GIMPLE_CALL must be replaced by a
2615 GIMPLE_ASSIGN, and there is no way to effect such a
2616 transformation in-place. We might want to consider
2617 using the more general fold_stmt here. */
2618 fold_stmt_inplace (use_stmt);
2620 /* Sometimes propagation can expose new operands to the
2621 renamer. Note this will call update_stmt at the
2622 appropriate time. */
2623 pop_stmt_changes (&use_stmt);
2626 if (dump_file && (dump_flags & TDF_DETAILS))
2628 fprintf (dump_file, " Updated statement:");
2629 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2632 /* If we replaced a variable index with a constant, then
2633 we would need to update the invariant flag for ADDR_EXPRs. */
2634 if (gimple_assign_single_p (use_stmt)
2635 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
2636 recompute_tree_invariant_for_addr_expr
2637 (gimple_assign_rhs1 (use_stmt));
2639 /* If we cleaned up EH information from the statement,
2640 mark its containing block as needing EH cleanups. */
2641 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
2643 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
2644 if (dump_file && (dump_flags & TDF_DETAILS))
2645 fprintf (dump_file, " Flagged to clear EH edges.\n");
2648 /* Propagation may expose new trivial copy/constant propagation
2650 if (gimple_assign_single_p (use_stmt)
2651 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
2652 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
2653 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
2655 tree result = get_lhs_or_phi_result (use_stmt);
2656 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2659 /* Propagation into these nodes may make certain edges in
2660 the CFG unexecutable. We want to identify them as PHI nodes
2661 at the destination of those unexecutable edges may become
2663 else if (gimple_code (use_stmt) == GIMPLE_COND
2664 || gimple_code (use_stmt) == GIMPLE_SWITCH
2665 || gimple_code (use_stmt) == GIMPLE_GOTO)
2669 if (gimple_code (use_stmt) == GIMPLE_COND)
2670 val = fold_binary (gimple_cond_code (use_stmt),
2672 gimple_cond_lhs (use_stmt),
2673 gimple_cond_rhs (use_stmt));
2674 else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
2675 val = gimple_switch_index (use_stmt);
2677 val = gimple_goto_dest (use_stmt);
2679 if (val && is_gimple_min_invariant (val))
2681 basic_block bb = gimple_bb (use_stmt);
2682 edge te = find_taken_edge (bb, val);
2685 gimple_stmt_iterator gsi, psi;
2687 /* Remove all outgoing edges except TE. */
2688 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
2692 /* Mark all the PHI nodes at the destination of
2693 the unexecutable edge as interesting. */
2694 for (psi = gsi_start_phis (e->dest);
2698 gimple phi = gsi_stmt (psi);
2700 tree result = gimple_phi_result (phi);
2701 int version = SSA_NAME_VERSION (result);
2703 bitmap_set_bit (interesting_names, version);
2706 te->probability += e->probability;
2708 te->count += e->count;
2716 gsi = gsi_last_bb (gimple_bb (use_stmt));
2717 gsi_remove (&gsi, true);
2719 /* And fixup the flags on the single remaining edge. */
2720 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
2721 te->flags &= ~EDGE_ABNORMAL;
2722 te->flags |= EDGE_FALLTHRU;
2723 if (te->probability > REG_BR_PROB_BASE)
2724 te->probability = REG_BR_PROB_BASE;
2729 /* Ensure there is nothing else to do. */
2730 gcc_assert (!all || has_zero_uses (lhs));
2732 /* If we were able to propagate away all uses of LHS, then
2733 we can remove STMT. */
2735 remove_stmt_or_phi (stmt);
2739 /* STMT is either a PHI node (potentially a degenerate PHI node) or
2740 a statement that is a trivial copy or constant initialization.
2742 Attempt to eliminate T by propagating its RHS into all uses of
2743 its LHS. This may in turn set new bits in INTERESTING_NAMES
2744 for nodes we want to revisit later.
2746 All exit paths should clear INTERESTING_NAMES for the result
2750 eliminate_const_or_copy (gimple stmt, bitmap interesting_names)
2752 tree lhs = get_lhs_or_phi_result (stmt);
2754 int version = SSA_NAME_VERSION (lhs);
2756 /* If the LHS of this statement or PHI has no uses, then we can
2757 just eliminate it. This can occur if, for example, the PHI
2758 was created by block duplication due to threading and its only
2759 use was in the conditional at the end of the block which was
2761 if (has_zero_uses (lhs))
2763 bitmap_clear_bit (interesting_names, version);
2764 remove_stmt_or_phi (stmt);
2768 /* Get the RHS of the assignment or PHI node if the PHI is a
2770 rhs = get_rhs_or_phi_arg (stmt);
2773 bitmap_clear_bit (interesting_names, version);
2777 propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
2779 /* Note that STMT may well have been deleted by now, so do
2780 not access it, instead use the saved version # to clear
2781 T's entry in the worklist. */
2782 bitmap_clear_bit (interesting_names, version);
2785 /* The first phase in degenerate PHI elimination.
2787 Eliminate the degenerate PHIs in BB, then recurse on the
2788 dominator children of BB. */
2791 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names)
2793 gimple_stmt_iterator gsi;
2796 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2798 gimple phi = gsi_stmt (gsi);
2800 eliminate_const_or_copy (phi, interesting_names);
2803 /* Recurse into the dominator children of BB. */
2804 for (son = first_dom_son (CDI_DOMINATORS, bb);
2806 son = next_dom_son (CDI_DOMINATORS, son))
2807 eliminate_degenerate_phis_1 (son, interesting_names);
2811 /* A very simple pass to eliminate degenerate PHI nodes from the
2812 IL. This is meant to be fast enough to be able to be run several
2813 times in the optimization pipeline.
2815 Certain optimizations, particularly those which duplicate blocks
2816 or remove edges from the CFG can create or expose PHIs which are
2817 trivial copies or constant initializations.
2819 While we could pick up these optimizations in DOM or with the
2820 combination of copy-prop and CCP, those solutions are far too
2821 heavy-weight for our needs.
2823 This implementation has two phases so that we can efficiently
2824 eliminate the first order degenerate PHIs and second order
2827 The first phase performs a dominator walk to identify and eliminate
2828 the vast majority of the degenerate PHIs. When a degenerate PHI
2829 is identified and eliminated any affected statements or PHIs
2830 are put on a worklist.
2832 The second phase eliminates degenerate PHIs and trivial copies
2833 or constant initializations using the worklist. This is how we
2834 pick up the secondary optimization opportunities with minimal
2838 eliminate_degenerate_phis (void)
2840 bitmap interesting_names;
2841 bitmap interesting_names1;
2843 /* Bitmap of blocks which need EH information updated. We can not
2844 update it on-the-fly as doing so invalidates the dominator tree. */
2845 need_eh_cleanup = BITMAP_ALLOC (NULL);
2847 /* INTERESTING_NAMES is effectively our worklist, indexed by
2850 A set bit indicates that the statement or PHI node which
2851 defines the SSA_NAME should be (re)examined to determine if
2852 it has become a degenerate PHI or trivial const/copy propagation
2855 Experiments have show we generally get better compilation
2856 time behavior with bitmaps rather than sbitmaps. */
2857 interesting_names = BITMAP_ALLOC (NULL);
2858 interesting_names1 = BITMAP_ALLOC (NULL);
2860 calculate_dominance_info (CDI_DOMINATORS);
2861 cfg_altered = false;
2863 /* First phase. Eliminate degenerate PHIs via a dominator
2866 Experiments have indicated that we generally get better
2867 compile-time behavior by visiting blocks in the first
2868 phase in dominator order. Presumably this is because walking
2869 in dominator order leaves fewer PHIs for later examination
2870 by the worklist phase. */
2871 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
2873 /* Second phase. Eliminate second order degenerate PHIs as well
2874 as trivial copies or constant initializations identified by
2875 the first phase or this phase. Basically we keep iterating
2876 until our set of INTERESTING_NAMEs is empty. */
2877 while (!bitmap_empty_p (interesting_names))
2882 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2883 changed during the loop. Copy it to another bitmap and
2885 bitmap_copy (interesting_names1, interesting_names);
2887 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
2889 tree name = ssa_name (i);
2891 /* Ignore SSA_NAMEs that have been released because
2892 their defining statement was deleted (unreachable). */
2894 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
2900 free_dominance_info (CDI_DOMINATORS);
2902 /* Propagation of const and copies may make some EH edges dead. Purge
2903 such edges from the CFG as needed. */
2904 if (!bitmap_empty_p (need_eh_cleanup))
2906 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
2907 BITMAP_FREE (need_eh_cleanup);
2910 BITMAP_FREE (interesting_names);
2911 BITMAP_FREE (interesting_names1);
2915 struct gimple_opt_pass pass_phi_only_cprop =
2919 "phicprop", /* name */
2920 gate_dominator, /* gate */
2921 eliminate_degenerate_phis, /* execute */
2924 0, /* static_pass_number */
2925 TV_TREE_PHI_CPROP, /* tv_id */
2926 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
2927 0, /* properties_provided */
2928 0, /* properties_destroyed */
2929 0, /* todo_flags_start */
2935 | TODO_update_ssa /* todo_flags_finish */