1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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"
29 #include "basic-block.h"
33 #include "tree-pretty-print.h"
34 #include "gimple-pretty-print.h"
36 #include "tree-dump.h"
37 #include "tree-flow.h"
39 #include "tree-pass.h"
40 #include "tree-ssa-propagate.h"
41 #include "langhooks.h"
44 /* This file implements optimizations on the dominator tree. */
46 /* Representation of a "naked" right-hand-side expression, to be used
47 in recording available expressions in the expression hash table. */
63 struct { tree rhs; } single;
64 struct { enum tree_code op; tree opnd; } unary;
65 struct { enum tree_code op; tree opnd0, opnd1; } binary;
66 struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary;
67 struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call;
71 /* Structure for recording known values of a conditional expression
72 at the exits from its block. */
74 typedef struct cond_equivalence_s
76 struct hashable_expr cond;
80 DEF_VEC_O(cond_equivalence);
81 DEF_VEC_ALLOC_O(cond_equivalence,heap);
83 /* Structure for recording edge equivalences as well as any pending
84 edge redirections during the dominator optimizer.
86 Computing and storing the edge equivalences instead of creating
87 them on-demand can save significant amounts of time, particularly
88 for pathological cases involving switch statements.
90 These structures live for a single iteration of the dominator
91 optimizer in the edge's AUX field. At the end of an iteration we
92 free each of these structures and update the AUX field to point
93 to any requested redirection target (the code for updating the
94 CFG and SSA graph for edge redirection expects redirection edge
95 targets to be in the AUX field for each edge. */
99 /* If this edge creates a simple equivalence, the LHS and RHS of
100 the equivalence will be stored here. */
104 /* Traversing an edge may also indicate one or more particular conditions
105 are true or false. */
106 VEC(cond_equivalence, heap) *cond_equivalences;
109 /* Hash table with expressions made available during the renaming process.
110 When an assignment of the form X_i = EXPR is found, the statement is
111 stored in this table. If the same expression EXPR is later found on the
112 RHS of another statement, it is replaced with X_i (thus performing
113 global redundancy elimination). Similarly as we pass through conditionals
114 we record the conditional itself as having either a true or false value
116 static htab_t avail_exprs;
118 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
119 expressions it enters into the hash table along with a marker entry
120 (null). When we finish processing the block, we pop off entries and
121 remove the expressions from the global hash table until we hit the
123 typedef struct expr_hash_elt * expr_hash_elt_t;
124 DEF_VEC_P(expr_hash_elt_t);
125 DEF_VEC_ALLOC_P(expr_hash_elt_t,heap);
127 static VEC(expr_hash_elt_t,heap) *avail_exprs_stack;
129 /* Structure for entries in the expression hash table. */
133 /* The value (lhs) of this expression. */
136 /* The expression (rhs) we want to record. */
137 struct hashable_expr expr;
139 /* The stmt pointer if this element corresponds to a statement. */
142 /* The hash value for RHS. */
145 /* A unique stamp, typically the address of the hash
146 element itself, used in removing entries from the table. */
147 struct expr_hash_elt *stamp;
150 /* Stack of dest,src pairs that need to be restored during finalization.
152 A NULL entry is used to mark the end of pairs which need to be
153 restored during finalization of this block. */
154 static VEC(tree,heap) *const_and_copies_stack;
156 /* Track whether or not we have changed the control flow graph. */
157 static bool cfg_altered;
159 /* Bitmap of blocks that have had EH statements cleaned. We should
160 remove their dead edges eventually. */
161 static bitmap need_eh_cleanup;
163 /* Statistics for dominator optimizations. */
167 long num_exprs_considered;
173 static struct opt_stats_d opt_stats;
175 /* Local functions. */
176 static void optimize_stmt (basic_block, gimple_stmt_iterator);
177 static tree lookup_avail_expr (gimple, bool);
178 static hashval_t avail_expr_hash (const void *);
179 static hashval_t real_avail_expr_hash (const void *);
180 static int avail_expr_eq (const void *, const void *);
181 static void htab_statistics (FILE *, htab_t);
182 static void record_cond (cond_equivalence *);
183 static void record_const_or_copy (tree, tree);
184 static void record_equality (tree, tree);
185 static void record_equivalences_from_phis (basic_block);
186 static void record_equivalences_from_incoming_edge (basic_block);
187 static void eliminate_redundant_computations (gimple_stmt_iterator *);
188 static void record_equivalences_from_stmt (gimple, int);
189 static void dom_thread_across_edge (struct dom_walk_data *, edge);
190 static void dom_opt_leave_block (struct dom_walk_data *, basic_block);
191 static void dom_opt_enter_block (struct dom_walk_data *, basic_block);
192 static void remove_local_expressions_from_table (void);
193 static void restore_vars_to_original_value (void);
194 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
197 /* Given a statement STMT, initialize the hash table element pointed to
201 initialize_hash_element (gimple stmt, tree lhs,
202 struct expr_hash_elt *element)
204 enum gimple_code code = gimple_code (stmt);
205 struct hashable_expr *expr = &element->expr;
207 if (code == GIMPLE_ASSIGN)
209 enum tree_code subcode = gimple_assign_rhs_code (stmt);
211 switch (get_gimple_rhs_class (subcode))
213 case GIMPLE_SINGLE_RHS:
214 expr->kind = EXPR_SINGLE;
215 expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt));
216 expr->ops.single.rhs = gimple_assign_rhs1 (stmt);
218 case GIMPLE_UNARY_RHS:
219 expr->kind = EXPR_UNARY;
220 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
221 expr->ops.unary.op = subcode;
222 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt);
224 case GIMPLE_BINARY_RHS:
225 expr->kind = EXPR_BINARY;
226 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
227 expr->ops.binary.op = subcode;
228 expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
229 expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
231 case GIMPLE_TERNARY_RHS:
232 expr->kind = EXPR_TERNARY;
233 expr->type = TREE_TYPE (gimple_assign_lhs (stmt));
234 expr->ops.ternary.op = subcode;
235 expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt);
236 expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt);
237 expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt);
243 else if (code == GIMPLE_COND)
245 expr->type = boolean_type_node;
246 expr->kind = EXPR_BINARY;
247 expr->ops.binary.op = gimple_cond_code (stmt);
248 expr->ops.binary.opnd0 = gimple_cond_lhs (stmt);
249 expr->ops.binary.opnd1 = gimple_cond_rhs (stmt);
251 else if (code == GIMPLE_CALL)
253 size_t nargs = gimple_call_num_args (stmt);
256 gcc_assert (gimple_call_lhs (stmt));
258 expr->type = TREE_TYPE (gimple_call_lhs (stmt));
259 expr->kind = EXPR_CALL;
260 expr->ops.call.fn_from = stmt;
262 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
263 expr->ops.call.pure = true;
265 expr->ops.call.pure = false;
267 expr->ops.call.nargs = nargs;
268 expr->ops.call.args = (tree *) xcalloc (nargs, sizeof (tree));
269 for (i = 0; i < nargs; i++)
270 expr->ops.call.args[i] = gimple_call_arg (stmt, i);
272 else if (code == GIMPLE_SWITCH)
274 expr->type = TREE_TYPE (gimple_switch_index (stmt));
275 expr->kind = EXPR_SINGLE;
276 expr->ops.single.rhs = gimple_switch_index (stmt);
278 else if (code == GIMPLE_GOTO)
280 expr->type = TREE_TYPE (gimple_goto_dest (stmt));
281 expr->kind = EXPR_SINGLE;
282 expr->ops.single.rhs = gimple_goto_dest (stmt);
288 element->stmt = stmt;
289 element->hash = avail_expr_hash (element);
290 element->stamp = element;
293 /* Given a conditional expression COND as a tree, initialize
294 a hashable_expr expression EXPR. The conditional must be a
295 comparison or logical negation. A constant or a variable is
299 initialize_expr_from_cond (tree cond, struct hashable_expr *expr)
301 expr->type = boolean_type_node;
303 if (COMPARISON_CLASS_P (cond))
305 expr->kind = EXPR_BINARY;
306 expr->ops.binary.op = TREE_CODE (cond);
307 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0);
308 expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1);
310 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
312 expr->kind = EXPR_UNARY;
313 expr->ops.unary.op = TRUTH_NOT_EXPR;
314 expr->ops.unary.opnd = TREE_OPERAND (cond, 0);
320 /* Given a hashable_expr expression EXPR and an LHS,
321 initialize the hash table element pointed to by ELEMENT. */
324 initialize_hash_element_from_expr (struct hashable_expr *expr,
326 struct expr_hash_elt *element)
328 element->expr = *expr;
330 element->stmt = NULL;
331 element->hash = avail_expr_hash (element);
332 element->stamp = element;
335 /* Compare two hashable_expr structures for equivalence.
336 They are considered equivalent when the the expressions
337 they denote must necessarily be equal. The logic is intended
338 to follow that of operand_equal_p in fold-const.c */
341 hashable_expr_equal_p (const struct hashable_expr *expr0,
342 const struct hashable_expr *expr1)
344 tree type0 = expr0->type;
345 tree type1 = expr1->type;
347 /* If either type is NULL, there is nothing to check. */
348 if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE))
351 /* If both types don't have the same signedness, precision, and mode,
352 then we can't consider them equal. */
354 && (TREE_CODE (type0) == ERROR_MARK
355 || TREE_CODE (type1) == ERROR_MARK
356 || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1)
357 || TYPE_PRECISION (type0) != TYPE_PRECISION (type1)
358 || TYPE_MODE (type0) != TYPE_MODE (type1)))
361 if (expr0->kind != expr1->kind)
367 return operand_equal_p (expr0->ops.single.rhs,
368 expr1->ops.single.rhs, 0);
371 if (expr0->ops.unary.op != expr1->ops.unary.op)
374 if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op)
375 || expr0->ops.unary.op == NON_LVALUE_EXPR)
376 && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type))
379 return operand_equal_p (expr0->ops.unary.opnd,
380 expr1->ops.unary.opnd, 0);
383 if (expr0->ops.binary.op != expr1->ops.binary.op)
386 if (operand_equal_p (expr0->ops.binary.opnd0,
387 expr1->ops.binary.opnd0, 0)
388 && operand_equal_p (expr0->ops.binary.opnd1,
389 expr1->ops.binary.opnd1, 0))
392 /* For commutative ops, allow the other order. */
393 return (commutative_tree_code (expr0->ops.binary.op)
394 && operand_equal_p (expr0->ops.binary.opnd0,
395 expr1->ops.binary.opnd1, 0)
396 && operand_equal_p (expr0->ops.binary.opnd1,
397 expr1->ops.binary.opnd0, 0));
400 if (expr0->ops.ternary.op != expr1->ops.ternary.op
401 || !operand_equal_p (expr0->ops.ternary.opnd2,
402 expr1->ops.ternary.opnd2, 0))
405 if (operand_equal_p (expr0->ops.ternary.opnd0,
406 expr1->ops.ternary.opnd0, 0)
407 && operand_equal_p (expr0->ops.ternary.opnd1,
408 expr1->ops.ternary.opnd1, 0))
411 /* For commutative ops, allow the other order. */
412 return (commutative_ternary_tree_code (expr0->ops.ternary.op)
413 && operand_equal_p (expr0->ops.ternary.opnd0,
414 expr1->ops.ternary.opnd1, 0)
415 && operand_equal_p (expr0->ops.ternary.opnd1,
416 expr1->ops.ternary.opnd0, 0));
422 /* If the calls are to different functions, then they
423 clearly cannot be equal. */
424 if (!gimple_call_same_target_p (expr0->ops.call.fn_from,
425 expr1->ops.call.fn_from))
428 if (! expr0->ops.call.pure)
431 if (expr0->ops.call.nargs != expr1->ops.call.nargs)
434 for (i = 0; i < expr0->ops.call.nargs; i++)
435 if (! operand_equal_p (expr0->ops.call.args[i],
436 expr1->ops.call.args[i], 0))
447 /* Compute a hash value for a hashable_expr value EXPR and a
448 previously accumulated hash value VAL. If two hashable_expr
449 values compare equal with hashable_expr_equal_p, they must
450 hash to the same value, given an identical value of VAL.
451 The logic is intended to follow iterative_hash_expr in tree.c. */
454 iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val)
459 val = iterative_hash_expr (expr->ops.single.rhs, val);
463 val = iterative_hash_object (expr->ops.unary.op, val);
465 /* Make sure to include signedness in the hash computation.
466 Don't hash the type, that can lead to having nodes which
467 compare equal according to operand_equal_p, but which
468 have different hash codes. */
469 if (CONVERT_EXPR_CODE_P (expr->ops.unary.op)
470 || expr->ops.unary.op == NON_LVALUE_EXPR)
471 val += TYPE_UNSIGNED (expr->type);
473 val = iterative_hash_expr (expr->ops.unary.opnd, val);
477 val = iterative_hash_object (expr->ops.binary.op, val);
478 if (commutative_tree_code (expr->ops.binary.op))
479 val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0,
480 expr->ops.binary.opnd1, val);
483 val = iterative_hash_expr (expr->ops.binary.opnd0, val);
484 val = iterative_hash_expr (expr->ops.binary.opnd1, val);
489 val = iterative_hash_object (expr->ops.ternary.op, val);
490 if (commutative_ternary_tree_code (expr->ops.ternary.op))
491 val = iterative_hash_exprs_commutative (expr->ops.ternary.opnd0,
492 expr->ops.ternary.opnd1, val);
495 val = iterative_hash_expr (expr->ops.ternary.opnd0, val);
496 val = iterative_hash_expr (expr->ops.ternary.opnd1, val);
498 val = iterative_hash_expr (expr->ops.ternary.opnd2, val);
504 enum tree_code code = CALL_EXPR;
507 val = iterative_hash_object (code, val);
508 fn_from = expr->ops.call.fn_from;
509 if (gimple_call_internal_p (fn_from))
510 val = iterative_hash_hashval_t
511 ((hashval_t) gimple_call_internal_fn (fn_from), val);
513 val = iterative_hash_expr (gimple_call_fn (fn_from), val);
514 for (i = 0; i < expr->ops.call.nargs; i++)
515 val = iterative_hash_expr (expr->ops.call.args[i], val);
526 /* Print a diagnostic dump of an expression hash table entry. */
529 print_expr_hash_elt (FILE * stream, const struct expr_hash_elt *element)
532 fprintf (stream, "STMT ");
534 fprintf (stream, "COND ");
538 print_generic_expr (stream, element->lhs, 0);
539 fprintf (stream, " = ");
542 switch (element->expr.kind)
545 print_generic_expr (stream, element->expr.ops.single.rhs, 0);
549 fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]);
550 print_generic_expr (stream, element->expr.ops.unary.opnd, 0);
554 print_generic_expr (stream, element->expr.ops.binary.opnd0, 0);
555 fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]);
556 print_generic_expr (stream, element->expr.ops.binary.opnd1, 0);
560 fprintf (stream, " %s <", tree_code_name[element->expr.ops.ternary.op]);
561 print_generic_expr (stream, element->expr.ops.ternary.opnd0, 0);
562 fputs (", ", stream);
563 print_generic_expr (stream, element->expr.ops.ternary.opnd1, 0);
564 fputs (", ", stream);
565 print_generic_expr (stream, element->expr.ops.ternary.opnd2, 0);
572 size_t nargs = element->expr.ops.call.nargs;
575 fn_from = element->expr.ops.call.fn_from;
576 if (gimple_call_internal_p (fn_from))
577 fputs (internal_fn_name (gimple_call_internal_fn (fn_from)),
580 print_generic_expr (stream, gimple_call_fn (fn_from), 0);
581 fprintf (stream, " (");
582 for (i = 0; i < nargs; i++)
584 print_generic_expr (stream, element->expr.ops.call.args[i], 0);
586 fprintf (stream, ", ");
588 fprintf (stream, ")");
592 fprintf (stream, "\n");
596 fprintf (stream, " ");
597 print_gimple_stmt (stream, element->stmt, 0, 0);
601 /* Delete an expr_hash_elt and reclaim its storage. */
604 free_expr_hash_elt (void *elt)
606 struct expr_hash_elt *element = ((struct expr_hash_elt *)elt);
608 if (element->expr.kind == EXPR_CALL)
609 free (element->expr.ops.call.args);
614 /* Allocate an EDGE_INFO for edge E and attach it to E.
615 Return the new EDGE_INFO structure. */
617 static struct edge_info *
618 allocate_edge_info (edge e)
620 struct edge_info *edge_info;
622 edge_info = XCNEW (struct edge_info);
628 /* Free all EDGE_INFO structures associated with edges in the CFG.
629 If a particular edge can be threaded, copy the redirection
630 target from the EDGE_INFO structure into the edge's AUX field
631 as required by code to update the CFG and SSA graph for
635 free_all_edge_infos (void)
643 FOR_EACH_EDGE (e, ei, bb->preds)
645 struct edge_info *edge_info = (struct edge_info *) e->aux;
649 if (edge_info->cond_equivalences)
650 VEC_free (cond_equivalence, heap, edge_info->cond_equivalences);
658 /* Jump threading, redundancy elimination and const/copy propagation.
660 This pass may expose new symbols that need to be renamed into SSA. For
661 every new symbol exposed, its corresponding bit will be set in
665 tree_ssa_dominator_optimize (void)
667 struct dom_walk_data walk_data;
669 memset (&opt_stats, 0, sizeof (opt_stats));
671 /* Create our hash tables. */
672 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt);
673 avail_exprs_stack = VEC_alloc (expr_hash_elt_t, heap, 20);
674 const_and_copies_stack = VEC_alloc (tree, heap, 20);
675 need_eh_cleanup = BITMAP_ALLOC (NULL);
677 /* Setup callbacks for the generic dominator tree walker. */
678 walk_data.dom_direction = CDI_DOMINATORS;
679 walk_data.initialize_block_local_data = NULL;
680 walk_data.before_dom_children = dom_opt_enter_block;
681 walk_data.after_dom_children = dom_opt_leave_block;
682 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
683 When we attach more stuff we'll need to fill this out with a real
685 walk_data.global_data = NULL;
686 walk_data.block_local_data_size = 0;
688 /* Now initialize the dominator walker. */
689 init_walk_dominator_tree (&walk_data);
691 calculate_dominance_info (CDI_DOMINATORS);
694 /* We need to know loop structures in order to avoid destroying them
695 in jump threading. Note that we still can e.g. thread through loop
696 headers to an exit edge, or through loop header to the loop body, assuming
697 that we update the loop info. */
698 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES);
700 /* Initialize the value-handle array. */
701 threadedge_initialize_values ();
703 /* We need accurate information regarding back edges in the CFG
704 for jump threading; this may include back edges that are not part of
706 mark_dfs_back_edges ();
708 /* Recursively walk the dominator tree optimizing statements. */
709 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
712 gimple_stmt_iterator gsi;
716 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
717 update_stmt_if_modified (gsi_stmt (gsi));
721 /* If we exposed any new variables, go ahead and put them into
722 SSA form now, before we handle jump threading. This simplifies
723 interactions between rewriting of _DECL nodes into SSA form
724 and rewriting SSA_NAME nodes into SSA form after block
725 duplication and CFG manipulation. */
726 update_ssa (TODO_update_ssa);
728 free_all_edge_infos ();
730 /* Thread jumps, creating duplicate blocks as needed. */
731 cfg_altered |= thread_through_all_blocks (first_pass_instance);
734 free_dominance_info (CDI_DOMINATORS);
736 /* Removal of statements may make some EH edges dead. Purge
737 such edges from the CFG as needed. */
738 if (!bitmap_empty_p (need_eh_cleanup))
743 /* Jump threading may have created forwarder blocks from blocks
744 needing EH cleanup; the new successor of these blocks, which
745 has inherited from the original block, needs the cleanup. */
746 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi)
748 basic_block bb = BASIC_BLOCK (i);
750 && single_succ_p (bb)
751 && (single_succ_edge (bb)->flags & EDGE_EH) == 0)
753 bitmap_clear_bit (need_eh_cleanup, i);
754 bitmap_set_bit (need_eh_cleanup, single_succ (bb)->index);
758 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
759 bitmap_zero (need_eh_cleanup);
762 statistics_counter_event (cfun, "Redundant expressions eliminated",
764 statistics_counter_event (cfun, "Constants propagated",
765 opt_stats.num_const_prop);
766 statistics_counter_event (cfun, "Copies propagated",
767 opt_stats.num_copy_prop);
769 /* Debugging dumps. */
770 if (dump_file && (dump_flags & TDF_STATS))
771 dump_dominator_optimization_stats (dump_file);
773 loop_optimizer_finalize ();
775 /* Delete our main hashtable. */
776 htab_delete (avail_exprs);
778 /* And finalize the dominator walker. */
779 fini_walk_dominator_tree (&walk_data);
781 /* Free asserted bitmaps and stacks. */
782 BITMAP_FREE (need_eh_cleanup);
784 VEC_free (expr_hash_elt_t, heap, avail_exprs_stack);
785 VEC_free (tree, heap, const_and_copies_stack);
787 /* Free the value-handle array. */
788 threadedge_finalize_values ();
789 ssa_name_values = NULL;
795 gate_dominator (void)
797 return flag_tree_dom != 0;
800 struct gimple_opt_pass pass_dominator =
805 gate_dominator, /* gate */
806 tree_ssa_dominator_optimize, /* execute */
809 0, /* static_pass_number */
810 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */
811 PROP_cfg | PROP_ssa, /* properties_required */
812 0, /* properties_provided */
813 0, /* properties_destroyed */
814 0, /* todo_flags_start */
818 | TODO_verify_flow /* todo_flags_finish */
823 /* Given a conditional statement CONDSTMT, convert the
824 condition to a canonical form. */
827 canonicalize_comparison (gimple condstmt)
833 gcc_assert (gimple_code (condstmt) == GIMPLE_COND);
835 op0 = gimple_cond_lhs (condstmt);
836 op1 = gimple_cond_rhs (condstmt);
838 code = gimple_cond_code (condstmt);
840 /* If it would be profitable to swap the operands, then do so to
841 canonicalize the statement, enabling better optimization.
843 By placing canonicalization of such expressions here we
844 transparently keep statements in canonical form, even
845 when the statement is modified. */
846 if (tree_swap_operands_p (op0, op1, false))
848 /* For relationals we need to swap the operands
849 and change the code. */
855 code = swap_tree_comparison (code);
857 gimple_cond_set_code (condstmt, code);
858 gimple_cond_set_lhs (condstmt, op1);
859 gimple_cond_set_rhs (condstmt, op0);
861 update_stmt (condstmt);
866 /* Initialize local stacks for this optimizer and record equivalences
867 upon entry to BB. Equivalences can come from the edge traversed to
868 reach BB or they may come from PHI nodes at the start of BB. */
870 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
871 LIMIT entries left in LOCALs. */
874 remove_local_expressions_from_table (void)
876 /* Remove all the expressions made available in this block. */
877 while (VEC_length (expr_hash_elt_t, avail_exprs_stack) > 0)
879 expr_hash_elt_t victim = VEC_pop (expr_hash_elt_t, avail_exprs_stack);
885 /* This must precede the actual removal from the hash table,
886 as ELEMENT and the table entry may share a call argument
887 vector which will be freed during removal. */
888 if (dump_file && (dump_flags & TDF_DETAILS))
890 fprintf (dump_file, "<<<< ");
891 print_expr_hash_elt (dump_file, victim);
894 slot = htab_find_slot_with_hash (avail_exprs,
895 victim, victim->hash, NO_INSERT);
896 gcc_assert (slot && *slot == (void *) victim);
897 htab_clear_slot (avail_exprs, slot);
901 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
902 CONST_AND_COPIES to its original state, stopping when we hit a
906 restore_vars_to_original_value (void)
908 while (VEC_length (tree, const_and_copies_stack) > 0)
910 tree prev_value, dest;
912 dest = VEC_pop (tree, const_and_copies_stack);
917 if (dump_file && (dump_flags & TDF_DETAILS))
919 fprintf (dump_file, "<<<< COPY ");
920 print_generic_expr (dump_file, dest, 0);
921 fprintf (dump_file, " = ");
922 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0);
923 fprintf (dump_file, "\n");
926 prev_value = VEC_pop (tree, const_and_copies_stack);
927 set_ssa_name_value (dest, prev_value);
931 /* A trivial wrapper so that we can present the generic jump
932 threading code with a simple API for simplifying statements. */
934 simplify_stmt_for_jump_threading (gimple stmt,
935 gimple within_stmt ATTRIBUTE_UNUSED)
937 return lookup_avail_expr (stmt, false);
940 /* Wrapper for common code to attempt to thread an edge. For example,
941 it handles lazily building the dummy condition and the bookkeeping
942 when jump threading is successful. */
945 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e)
947 if (! walk_data->global_data)
950 gimple_build_cond (NE_EXPR,
951 integer_zero_node, integer_zero_node,
953 walk_data->global_data = dummy_cond;
956 thread_across_edge ((gimple) walk_data->global_data, e, false,
957 &const_and_copies_stack,
958 simplify_stmt_for_jump_threading);
961 /* PHI nodes can create equivalences too.
963 Ignoring any alternatives which are the same as the result, if
964 all the alternatives are equal, then the PHI node creates an
968 record_equivalences_from_phis (basic_block bb)
970 gimple_stmt_iterator gsi;
972 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
974 gimple phi = gsi_stmt (gsi);
976 tree lhs = gimple_phi_result (phi);
980 for (i = 0; i < gimple_phi_num_args (phi); i++)
982 tree t = gimple_phi_arg_def (phi, i);
984 /* Ignore alternatives which are the same as our LHS. Since
985 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
986 can simply compare pointers. */
990 /* If we have not processed an alternative yet, then set
991 RHS to this alternative. */
994 /* If we have processed an alternative (stored in RHS), then
995 see if it is equal to this one. If it isn't, then stop
997 else if (! operand_equal_for_phi_arg_p (rhs, t))
1001 /* If we had no interesting alternatives, then all the RHS alternatives
1002 must have been the same as LHS. */
1006 /* If we managed to iterate through each PHI alternative without
1007 breaking out of the loop, then we have a PHI which may create
1008 a useful equivalence. We do not need to record unwind data for
1009 this, since this is a true assignment and not an equivalence
1010 inferred from a comparison. All uses of this ssa name are dominated
1011 by this assignment, so unwinding just costs time and space. */
1012 if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs))
1013 set_ssa_name_value (lhs, rhs);
1017 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1018 return that edge. Otherwise return NULL. */
1020 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1026 FOR_EACH_EDGE (e, ei, bb->preds)
1028 /* A loop back edge can be identified by the destination of
1029 the edge dominating the source of the edge. */
1030 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1033 /* If we have already seen a non-loop edge, then we must have
1034 multiple incoming non-loop edges and thus we return NULL. */
1038 /* This is the first non-loop incoming edge we have found. Record
1046 /* Record any equivalences created by the incoming edge to BB. If BB
1047 has more than one incoming edge, then no equivalence is created. */
1050 record_equivalences_from_incoming_edge (basic_block bb)
1054 struct edge_info *edge_info;
1056 /* If our parent block ended with a control statement, then we may be
1057 able to record some equivalences based on which outgoing edge from
1058 the parent was followed. */
1059 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1061 e = single_incoming_edge_ignoring_loop_edges (bb);
1063 /* If we had a single incoming edge from our parent block, then enter
1064 any data associated with the edge into our tables. */
1065 if (e && e->src == parent)
1069 edge_info = (struct edge_info *) e->aux;
1073 tree lhs = edge_info->lhs;
1074 tree rhs = edge_info->rhs;
1075 cond_equivalence *eq;
1078 record_equality (lhs, rhs);
1080 for (i = 0; VEC_iterate (cond_equivalence,
1081 edge_info->cond_equivalences, i, eq); ++i)
1087 /* Dump SSA statistics on FILE. */
1090 dump_dominator_optimization_stats (FILE *file)
1092 fprintf (file, "Total number of statements: %6ld\n\n",
1093 opt_stats.num_stmts);
1094 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1095 opt_stats.num_exprs_considered);
1097 fprintf (file, "\nHash table statistics:\n");
1099 fprintf (file, " avail_exprs: ");
1100 htab_statistics (file, avail_exprs);
1104 /* Dump SSA statistics on stderr. */
1107 debug_dominator_optimization_stats (void)
1109 dump_dominator_optimization_stats (stderr);
1113 /* Dump statistics for the hash table HTAB. */
1116 htab_statistics (FILE *file, htab_t htab)
1118 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1119 (long) htab_size (htab),
1120 (long) htab_elements (htab),
1121 htab_collisions (htab));
1125 /* Enter condition equivalence into the expression hash table.
1126 This indicates that a conditional expression has a known
1130 record_cond (cond_equivalence *p)
1132 struct expr_hash_elt *element = XCNEW (struct expr_hash_elt);
1135 initialize_hash_element_from_expr (&p->cond, p->value, element);
1137 slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
1138 element->hash, INSERT);
1141 *slot = (void *) element;
1143 if (dump_file && (dump_flags & TDF_DETAILS))
1145 fprintf (dump_file, "1>>> ");
1146 print_expr_hash_elt (dump_file, element);
1149 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element);
1155 /* Build a cond_equivalence record indicating that the comparison
1156 CODE holds between operands OP0 and OP1 and push it to **P. */
1159 build_and_record_new_cond (enum tree_code code,
1161 VEC(cond_equivalence, heap) **p)
1164 struct hashable_expr *cond = &c.cond;
1166 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
1168 cond->type = boolean_type_node;
1169 cond->kind = EXPR_BINARY;
1170 cond->ops.binary.op = code;
1171 cond->ops.binary.opnd0 = op0;
1172 cond->ops.binary.opnd1 = op1;
1174 c.value = boolean_true_node;
1175 VEC_safe_push (cond_equivalence, heap, *p, &c);
1178 /* Record that COND is true and INVERTED is false into the edge information
1179 structure. Also record that any conditions dominated by COND are true
1182 For example, if a < b is true, then a <= b must also be true. */
1185 record_conditions (struct edge_info *edge_info, tree cond, tree inverted)
1190 if (!COMPARISON_CLASS_P (cond))
1193 op0 = TREE_OPERAND (cond, 0);
1194 op1 = TREE_OPERAND (cond, 1);
1196 switch (TREE_CODE (cond))
1200 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1202 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1203 &edge_info->cond_equivalences);
1204 build_and_record_new_cond (LTGT_EXPR, op0, op1,
1205 &edge_info->cond_equivalences);
1208 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR
1209 ? LE_EXPR : GE_EXPR),
1210 op0, op1, &edge_info->cond_equivalences);
1211 build_and_record_new_cond (NE_EXPR, op0, op1,
1212 &edge_info->cond_equivalences);
1217 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1219 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1220 &edge_info->cond_equivalences);
1225 if (FLOAT_TYPE_P (TREE_TYPE (op0)))
1227 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1228 &edge_info->cond_equivalences);
1230 build_and_record_new_cond (LE_EXPR, op0, op1,
1231 &edge_info->cond_equivalences);
1232 build_and_record_new_cond (GE_EXPR, op0, op1,
1233 &edge_info->cond_equivalences);
1236 case UNORDERED_EXPR:
1237 build_and_record_new_cond (NE_EXPR, op0, op1,
1238 &edge_info->cond_equivalences);
1239 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1240 &edge_info->cond_equivalences);
1241 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1242 &edge_info->cond_equivalences);
1243 build_and_record_new_cond (UNEQ_EXPR, op0, op1,
1244 &edge_info->cond_equivalences);
1245 build_and_record_new_cond (UNLT_EXPR, op0, op1,
1246 &edge_info->cond_equivalences);
1247 build_and_record_new_cond (UNGT_EXPR, op0, op1,
1248 &edge_info->cond_equivalences);
1253 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR
1254 ? UNLE_EXPR : UNGE_EXPR),
1255 op0, op1, &edge_info->cond_equivalences);
1256 build_and_record_new_cond (NE_EXPR, op0, op1,
1257 &edge_info->cond_equivalences);
1261 build_and_record_new_cond (UNLE_EXPR, op0, op1,
1262 &edge_info->cond_equivalences);
1263 build_and_record_new_cond (UNGE_EXPR, op0, op1,
1264 &edge_info->cond_equivalences);
1268 build_and_record_new_cond (NE_EXPR, op0, op1,
1269 &edge_info->cond_equivalences);
1270 build_and_record_new_cond (ORDERED_EXPR, op0, op1,
1271 &edge_info->cond_equivalences);
1278 /* Now store the original true and false conditions into the first
1280 initialize_expr_from_cond (cond, &c.cond);
1281 c.value = boolean_true_node;
1282 VEC_safe_push (cond_equivalence, heap, edge_info->cond_equivalences, &c);
1284 /* It is possible for INVERTED to be the negation of a comparison,
1285 and not a valid RHS or GIMPLE_COND condition. This happens because
1286 invert_truthvalue may return such an expression when asked to invert
1287 a floating-point comparison. These comparisons are not assumed to
1288 obey the trichotomy law. */
1289 initialize_expr_from_cond (inverted, &c.cond);
1290 c.value = boolean_false_node;
1291 VEC_safe_push (cond_equivalence, heap, edge_info->cond_equivalences, &c);
1294 /* A helper function for record_const_or_copy and record_equality.
1295 Do the work of recording the value and undo info. */
1298 record_const_or_copy_1 (tree x, tree y, tree prev_x)
1300 set_ssa_name_value (x, y);
1302 if (dump_file && (dump_flags & TDF_DETAILS))
1304 fprintf (dump_file, "0>>> COPY ");
1305 print_generic_expr (dump_file, x, 0);
1306 fprintf (dump_file, " = ");
1307 print_generic_expr (dump_file, y, 0);
1308 fprintf (dump_file, "\n");
1311 VEC_reserve (tree, heap, const_and_copies_stack, 2);
1312 VEC_quick_push (tree, const_and_copies_stack, prev_x);
1313 VEC_quick_push (tree, const_and_copies_stack, x);
1316 /* Return the loop depth of the basic block of the defining statement of X.
1317 This number should not be treated as absolutely correct because the loop
1318 information may not be completely up-to-date when dom runs. However, it
1319 will be relatively correct, and as more passes are taught to keep loop info
1320 up to date, the result will become more and more accurate. */
1323 loop_depth_of_name (tree x)
1328 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1329 if (TREE_CODE (x) != SSA_NAME)
1332 /* Otherwise return the loop depth of the defining statement's bb.
1333 Note that there may not actually be a bb for this statement, if the
1334 ssa_name is live on entry. */
1335 defstmt = SSA_NAME_DEF_STMT (x);
1336 defbb = gimple_bb (defstmt);
1340 return defbb->loop_depth;
1343 /* Record that X is equal to Y in const_and_copies. Record undo
1344 information in the block-local vector. */
1347 record_const_or_copy (tree x, tree y)
1349 tree prev_x = SSA_NAME_VALUE (x);
1351 gcc_assert (TREE_CODE (x) == SSA_NAME);
1353 if (TREE_CODE (y) == SSA_NAME)
1355 tree tmp = SSA_NAME_VALUE (y);
1360 record_const_or_copy_1 (x, y, prev_x);
1363 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1364 This constrains the cases in which we may treat this as assignment. */
1367 record_equality (tree x, tree y)
1369 tree prev_x = NULL, prev_y = NULL;
1371 if (TREE_CODE (x) == SSA_NAME)
1372 prev_x = SSA_NAME_VALUE (x);
1373 if (TREE_CODE (y) == SSA_NAME)
1374 prev_y = SSA_NAME_VALUE (y);
1376 /* If one of the previous values is invariant, or invariant in more loops
1377 (by depth), then use that.
1378 Otherwise it doesn't matter which value we choose, just so
1379 long as we canonicalize on one value. */
1380 if (is_gimple_min_invariant (y))
1382 else if (is_gimple_min_invariant (x)
1383 || (loop_depth_of_name (x) <= loop_depth_of_name (y)))
1384 prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1385 else if (prev_x && is_gimple_min_invariant (prev_x))
1386 x = y, y = prev_x, prev_x = prev_y;
1390 /* After the swapping, we must have one SSA_NAME. */
1391 if (TREE_CODE (x) != SSA_NAME)
1394 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1395 variable compared against zero. If we're honoring signed zeros,
1396 then we cannot record this value unless we know that the value is
1398 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1399 && (TREE_CODE (y) != REAL_CST
1400 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1403 record_const_or_copy_1 (x, y, prev_x);
1406 /* Returns true when STMT is a simple iv increment. It detects the
1407 following situation:
1409 i_1 = phi (..., i_2)
1410 i_2 = i_1 +/- ... */
1413 simple_iv_increment_p (gimple stmt)
1415 enum tree_code code;
1420 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1423 lhs = gimple_assign_lhs (stmt);
1424 if (TREE_CODE (lhs) != SSA_NAME)
1427 code = gimple_assign_rhs_code (stmt);
1428 if (code != PLUS_EXPR
1429 && code != MINUS_EXPR
1430 && code != POINTER_PLUS_EXPR)
1433 preinc = gimple_assign_rhs1 (stmt);
1434 if (TREE_CODE (preinc) != SSA_NAME)
1437 phi = SSA_NAME_DEF_STMT (preinc);
1438 if (gimple_code (phi) != GIMPLE_PHI)
1441 for (i = 0; i < gimple_phi_num_args (phi); i++)
1442 if (gimple_phi_arg_def (phi, i) == lhs)
1448 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1449 known value for that SSA_NAME (or NULL if no value is known).
1451 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1452 successors of BB. */
1455 cprop_into_successor_phis (basic_block bb)
1460 FOR_EACH_EDGE (e, ei, bb->succs)
1463 gimple_stmt_iterator gsi;
1465 /* If this is an abnormal edge, then we do not want to copy propagate
1466 into the PHI alternative associated with this edge. */
1467 if (e->flags & EDGE_ABNORMAL)
1470 gsi = gsi_start_phis (e->dest);
1471 if (gsi_end_p (gsi))
1475 for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1478 use_operand_p orig_p;
1480 gimple phi = gsi_stmt (gsi);
1482 /* The alternative may be associated with a constant, so verify
1483 it is an SSA_NAME before doing anything with it. */
1484 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1485 orig_val = get_use_from_ptr (orig_p);
1486 if (TREE_CODE (orig_val) != SSA_NAME)
1489 /* If we have *ORIG_P in our constant/copy table, then replace
1490 ORIG_P with its value in our constant/copy table. */
1491 new_val = SSA_NAME_VALUE (orig_val);
1493 && new_val != orig_val
1494 && (TREE_CODE (new_val) == SSA_NAME
1495 || is_gimple_min_invariant (new_val))
1496 && may_propagate_copy (orig_val, new_val))
1497 propagate_value (orig_p, new_val);
1502 /* We have finished optimizing BB, record any information implied by
1503 taking a specific outgoing edge from BB. */
1506 record_edge_info (basic_block bb)
1508 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1509 struct edge_info *edge_info;
1511 if (! gsi_end_p (gsi))
1513 gimple stmt = gsi_stmt (gsi);
1514 location_t loc = gimple_location (stmt);
1516 if (gimple_code (stmt) == GIMPLE_SWITCH)
1518 tree index = gimple_switch_index (stmt);
1520 if (TREE_CODE (index) == SSA_NAME)
1523 int n_labels = gimple_switch_num_labels (stmt);
1524 tree *info = XCNEWVEC (tree, last_basic_block);
1528 for (i = 0; i < n_labels; i++)
1530 tree label = gimple_switch_label (stmt, i);
1531 basic_block target_bb = label_to_block (CASE_LABEL (label));
1532 if (CASE_HIGH (label)
1533 || !CASE_LOW (label)
1534 || info[target_bb->index])
1535 info[target_bb->index] = error_mark_node;
1537 info[target_bb->index] = label;
1540 FOR_EACH_EDGE (e, ei, bb->succs)
1542 basic_block target_bb = e->dest;
1543 tree label = info[target_bb->index];
1545 if (label != NULL && label != error_mark_node)
1547 tree x = fold_convert_loc (loc, TREE_TYPE (index),
1549 edge_info = allocate_edge_info (e);
1550 edge_info->lhs = index;
1558 /* A COND_EXPR may create equivalences too. */
1559 if (gimple_code (stmt) == GIMPLE_COND)
1564 tree op0 = gimple_cond_lhs (stmt);
1565 tree op1 = gimple_cond_rhs (stmt);
1566 enum tree_code code = gimple_cond_code (stmt);
1568 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1570 /* Special case comparing booleans against a constant as we
1571 know the value of OP0 on both arms of the branch. i.e., we
1572 can record an equivalence for OP0 rather than COND. */
1573 if ((code == EQ_EXPR || code == NE_EXPR)
1574 && TREE_CODE (op0) == SSA_NAME
1575 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
1576 && is_gimple_min_invariant (op1))
1578 if (code == EQ_EXPR)
1580 edge_info = allocate_edge_info (true_edge);
1581 edge_info->lhs = op0;
1582 edge_info->rhs = (integer_zerop (op1)
1583 ? boolean_false_node
1584 : boolean_true_node);
1586 edge_info = allocate_edge_info (false_edge);
1587 edge_info->lhs = op0;
1588 edge_info->rhs = (integer_zerop (op1)
1590 : boolean_false_node);
1594 edge_info = allocate_edge_info (true_edge);
1595 edge_info->lhs = op0;
1596 edge_info->rhs = (integer_zerop (op1)
1598 : boolean_false_node);
1600 edge_info = allocate_edge_info (false_edge);
1601 edge_info->lhs = op0;
1602 edge_info->rhs = (integer_zerop (op1)
1603 ? boolean_false_node
1604 : boolean_true_node);
1607 else if (is_gimple_min_invariant (op0)
1608 && (TREE_CODE (op1) == SSA_NAME
1609 || is_gimple_min_invariant (op1)))
1611 tree cond = build2 (code, boolean_type_node, op0, op1);
1612 tree inverted = invert_truthvalue_loc (loc, cond);
1613 struct edge_info *edge_info;
1615 edge_info = allocate_edge_info (true_edge);
1616 record_conditions (edge_info, cond, inverted);
1618 if (code == EQ_EXPR)
1620 edge_info->lhs = op1;
1621 edge_info->rhs = op0;
1624 edge_info = allocate_edge_info (false_edge);
1625 record_conditions (edge_info, inverted, cond);
1627 if (TREE_CODE (inverted) == EQ_EXPR)
1629 edge_info->lhs = op1;
1630 edge_info->rhs = op0;
1634 else if (TREE_CODE (op0) == SSA_NAME
1635 && (is_gimple_min_invariant (op1)
1636 || TREE_CODE (op1) == SSA_NAME))
1638 tree cond = build2 (code, boolean_type_node, op0, op1);
1639 tree inverted = invert_truthvalue_loc (loc, cond);
1640 struct edge_info *edge_info;
1642 edge_info = allocate_edge_info (true_edge);
1643 record_conditions (edge_info, cond, inverted);
1645 if (code == EQ_EXPR)
1647 edge_info->lhs = op0;
1648 edge_info->rhs = op1;
1651 edge_info = allocate_edge_info (false_edge);
1652 record_conditions (edge_info, inverted, cond);
1654 if (TREE_CODE (inverted) == EQ_EXPR)
1656 edge_info->lhs = op0;
1657 edge_info->rhs = op1;
1662 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1667 dom_opt_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1670 gimple_stmt_iterator gsi;
1672 if (dump_file && (dump_flags & TDF_DETAILS))
1673 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
1675 /* Push a marker on the stacks of local information so that we know how
1676 far to unwind when we finalize this block. */
1677 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
1678 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1680 record_equivalences_from_incoming_edge (bb);
1682 /* PHI nodes can create equivalences too. */
1683 record_equivalences_from_phis (bb);
1685 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1686 optimize_stmt (bb, gsi);
1688 /* Now prepare to process dominated blocks. */
1689 record_edge_info (bb);
1690 cprop_into_successor_phis (bb);
1693 /* We have finished processing the dominator children of BB, perform
1694 any finalization actions in preparation for leaving this node in
1695 the dominator tree. */
1698 dom_opt_leave_block (struct dom_walk_data *walk_data, basic_block bb)
1702 /* If we have an outgoing edge to a block with multiple incoming and
1703 outgoing edges, then we may be able to thread the edge, i.e., we
1704 may be able to statically determine which of the outgoing edges
1705 will be traversed when the incoming edge from BB is traversed. */
1706 if (single_succ_p (bb)
1707 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
1708 && potentially_threadable_block (single_succ (bb)))
1710 dom_thread_across_edge (walk_data, single_succ_edge (bb));
1712 else if ((last = last_stmt (bb))
1713 && gimple_code (last) == GIMPLE_COND
1714 && EDGE_COUNT (bb->succs) == 2
1715 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
1716 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
1718 edge true_edge, false_edge;
1720 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1722 /* Only try to thread the edge if it reaches a target block with
1723 more than one predecessor and more than one successor. */
1724 if (potentially_threadable_block (true_edge->dest))
1726 struct edge_info *edge_info;
1729 /* Push a marker onto the available expression stack so that we
1730 unwind any expressions related to the TRUE arm before processing
1731 the false arm below. */
1732 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
1733 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1735 edge_info = (struct edge_info *) true_edge->aux;
1737 /* If we have info associated with this edge, record it into
1738 our equivalence tables. */
1741 cond_equivalence *eq;
1742 tree lhs = edge_info->lhs;
1743 tree rhs = edge_info->rhs;
1745 /* If we have a simple NAME = VALUE equivalence, record it. */
1746 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1747 record_const_or_copy (lhs, rhs);
1749 /* If we have 0 = COND or 1 = COND equivalences, record them
1750 into our expression hash tables. */
1751 for (i = 0; VEC_iterate (cond_equivalence,
1752 edge_info->cond_equivalences, i, eq); ++i)
1756 dom_thread_across_edge (walk_data, true_edge);
1758 /* And restore the various tables to their state before
1759 we threaded this edge. */
1760 remove_local_expressions_from_table ();
1763 /* Similarly for the ELSE arm. */
1764 if (potentially_threadable_block (false_edge->dest))
1766 struct edge_info *edge_info;
1769 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1770 edge_info = (struct edge_info *) false_edge->aux;
1772 /* If we have info associated with this edge, record it into
1773 our equivalence tables. */
1776 cond_equivalence *eq;
1777 tree lhs = edge_info->lhs;
1778 tree rhs = edge_info->rhs;
1780 /* If we have a simple NAME = VALUE equivalence, record it. */
1781 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1782 record_const_or_copy (lhs, rhs);
1784 /* If we have 0 = COND or 1 = COND equivalences, record them
1785 into our expression hash tables. */
1786 for (i = 0; VEC_iterate (cond_equivalence,
1787 edge_info->cond_equivalences, i, eq); ++i)
1791 /* Now thread the edge. */
1792 dom_thread_across_edge (walk_data, false_edge);
1794 /* No need to remove local expressions from our tables
1795 or restore vars to their original value as that will
1796 be done immediately below. */
1800 remove_local_expressions_from_table ();
1801 restore_vars_to_original_value ();
1804 /* Search for redundant computations in STMT. If any are found, then
1805 replace them with the variable holding the result of the computation.
1807 If safe, record this expression into the available expression hash
1811 eliminate_redundant_computations (gimple_stmt_iterator* gsi)
1816 bool assigns_var_p = false;
1818 gimple stmt = gsi_stmt (*gsi);
1820 tree def = gimple_get_lhs (stmt);
1822 /* Certain expressions on the RHS can be optimized away, but can not
1823 themselves be entered into the hash tables. */
1825 || TREE_CODE (def) != SSA_NAME
1826 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1827 || gimple_vdef (stmt)
1828 /* Do not record equivalences for increments of ivs. This would create
1829 overlapping live ranges for a very questionable gain. */
1830 || simple_iv_increment_p (stmt))
1833 /* Check if the expression has been computed before. */
1834 cached_lhs = lookup_avail_expr (stmt, insert);
1836 opt_stats.num_exprs_considered++;
1838 /* Get the type of the expression we are trying to optimize. */
1839 if (is_gimple_assign (stmt))
1841 expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1842 assigns_var_p = true;
1844 else if (gimple_code (stmt) == GIMPLE_COND)
1845 expr_type = boolean_type_node;
1846 else if (is_gimple_call (stmt))
1848 gcc_assert (gimple_call_lhs (stmt));
1849 expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1850 assigns_var_p = true;
1852 else if (gimple_code (stmt) == GIMPLE_SWITCH)
1853 expr_type = TREE_TYPE (gimple_switch_index (stmt));
1860 /* It is safe to ignore types here since we have already done
1861 type checking in the hashing and equality routines. In fact
1862 type checking here merely gets in the way of constant
1863 propagation. Also, make sure that it is safe to propagate
1864 CACHED_LHS into the expression in STMT. */
1865 if ((TREE_CODE (cached_lhs) != SSA_NAME
1867 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1868 || may_propagate_copy_into_stmt (stmt, cached_lhs))
1870 gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME
1871 || is_gimple_min_invariant (cached_lhs));
1873 if (dump_file && (dump_flags & TDF_DETAILS))
1875 fprintf (dump_file, " Replaced redundant expr '");
1876 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1877 fprintf (dump_file, "' with '");
1878 print_generic_expr (dump_file, cached_lhs, dump_flags);
1879 fprintf (dump_file, "'\n");
1885 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1886 cached_lhs = fold_convert (expr_type, cached_lhs);
1888 propagate_tree_value_into_stmt (gsi, cached_lhs);
1890 /* Since it is always necessary to mark the result as modified,
1891 perhaps we should move this into propagate_tree_value_into_stmt
1893 gimple_set_modified (gsi_stmt (*gsi), true);
1897 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1898 the available expressions table or the const_and_copies table.
1899 Detect and record those equivalences. */
1900 /* We handle only very simple copy equivalences here. The heavy
1901 lifing is done by eliminate_redundant_computations. */
1904 record_equivalences_from_stmt (gimple stmt, int may_optimize_p)
1907 enum tree_code lhs_code;
1909 gcc_assert (is_gimple_assign (stmt));
1911 lhs = gimple_assign_lhs (stmt);
1912 lhs_code = TREE_CODE (lhs);
1914 if (lhs_code == SSA_NAME
1915 && gimple_assign_single_p (stmt))
1917 tree rhs = gimple_assign_rhs1 (stmt);
1919 /* If the RHS of the assignment is a constant or another variable that
1920 may be propagated, register it in the CONST_AND_COPIES table. We
1921 do not need to record unwind data for this, since this is a true
1922 assignment and not an equivalence inferred from a comparison. All
1923 uses of this ssa name are dominated by this assignment, so unwinding
1924 just costs time and space. */
1926 && (TREE_CODE (rhs) == SSA_NAME
1927 || is_gimple_min_invariant (rhs)))
1929 if (dump_file && (dump_flags & TDF_DETAILS))
1931 fprintf (dump_file, "==== ASGN ");
1932 print_generic_expr (dump_file, lhs, 0);
1933 fprintf (dump_file, " = ");
1934 print_generic_expr (dump_file, rhs, 0);
1935 fprintf (dump_file, "\n");
1938 set_ssa_name_value (lhs, rhs);
1942 /* A memory store, even an aliased store, creates a useful
1943 equivalence. By exchanging the LHS and RHS, creating suitable
1944 vops and recording the result in the available expression table,
1945 we may be able to expose more redundant loads. */
1946 if (!gimple_has_volatile_ops (stmt)
1947 && gimple_references_memory_p (stmt)
1948 && gimple_assign_single_p (stmt)
1949 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1950 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1951 && !is_gimple_reg (lhs))
1953 tree rhs = gimple_assign_rhs1 (stmt);
1956 /* Build a new statement with the RHS and LHS exchanged. */
1957 if (TREE_CODE (rhs) == SSA_NAME)
1959 /* NOTE tuples. The call to gimple_build_assign below replaced
1960 a call to build_gimple_modify_stmt, which did not set the
1961 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1962 may cause an SSA validation failure, as the LHS may be a
1963 default-initialized name and should have no definition. I'm
1964 a bit dubious of this, as the artificial statement that we
1965 generate here may in fact be ill-formed, but it is simply
1966 used as an internal device in this pass, and never becomes
1968 gimple defstmt = SSA_NAME_DEF_STMT (rhs);
1969 new_stmt = gimple_build_assign (rhs, lhs);
1970 SSA_NAME_DEF_STMT (rhs) = defstmt;
1973 new_stmt = gimple_build_assign (rhs, lhs);
1975 gimple_set_vuse (new_stmt, gimple_vdef (stmt));
1977 /* Finally enter the statement into the available expression
1979 lookup_avail_expr (new_stmt, true);
1983 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1984 CONST_AND_COPIES. */
1987 cprop_operand (gimple stmt, use_operand_p op_p)
1990 tree op = USE_FROM_PTR (op_p);
1992 /* If the operand has a known constant value or it is known to be a
1993 copy of some other variable, use the value or copy stored in
1994 CONST_AND_COPIES. */
1995 val = SSA_NAME_VALUE (op);
1996 if (val && val != op)
1998 /* Do not change the base variable in the virtual operand
1999 tables. That would make it impossible to reconstruct
2000 the renamed virtual operand if we later modify this
2001 statement. Also only allow the new value to be an SSA_NAME
2002 for propagation into virtual operands. */
2003 if (!is_gimple_reg (op)
2004 && (TREE_CODE (val) != SSA_NAME
2005 || is_gimple_reg (val)
2006 || get_virtual_var (val) != get_virtual_var (op)))
2009 /* Do not replace hard register operands in asm statements. */
2010 if (gimple_code (stmt) == GIMPLE_ASM
2011 && !may_propagate_copy_into_asm (op))
2014 /* Certain operands are not allowed to be copy propagated due
2015 to their interaction with exception handling and some GCC
2017 if (!may_propagate_copy (op, val))
2020 /* Do not propagate addresses that point to volatiles into memory
2021 stmts without volatile operands. */
2022 if (POINTER_TYPE_P (TREE_TYPE (val))
2023 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val)))
2024 && gimple_has_mem_ops (stmt)
2025 && !gimple_has_volatile_ops (stmt))
2028 /* Do not propagate copies if the propagated value is at a deeper loop
2029 depth than the propagatee. Otherwise, this may move loop variant
2030 variables outside of their loops and prevent coalescing
2031 opportunities. If the value was loop invariant, it will be hoisted
2032 by LICM and exposed for copy propagation. */
2033 if (loop_depth_of_name (val) > loop_depth_of_name (op))
2036 /* Do not propagate copies into simple IV increment statements.
2037 See PR23821 for how this can disturb IV analysis. */
2038 if (TREE_CODE (val) != INTEGER_CST
2039 && simple_iv_increment_p (stmt))
2043 if (dump_file && (dump_flags & TDF_DETAILS))
2045 fprintf (dump_file, " Replaced '");
2046 print_generic_expr (dump_file, op, dump_flags);
2047 fprintf (dump_file, "' with %s '",
2048 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2049 print_generic_expr (dump_file, val, dump_flags);
2050 fprintf (dump_file, "'\n");
2053 if (TREE_CODE (val) != SSA_NAME)
2054 opt_stats.num_const_prop++;
2056 opt_stats.num_copy_prop++;
2058 propagate_value (op_p, val);
2060 /* And note that we modified this statement. This is now
2061 safe, even if we changed virtual operands since we will
2062 rescan the statement and rewrite its operands again. */
2063 gimple_set_modified (stmt, true);
2067 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2068 known value for that SSA_NAME (or NULL if no value is known).
2070 Propagate values from CONST_AND_COPIES into the uses, vuses and
2071 vdef_ops of STMT. */
2074 cprop_into_stmt (gimple stmt)
2079 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
2081 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
2082 cprop_operand (stmt, op_p);
2086 /* Optimize the statement pointed to by iterator SI.
2088 We try to perform some simplistic global redundancy elimination and
2089 constant propagation:
2091 1- To detect global redundancy, we keep track of expressions that have
2092 been computed in this block and its dominators. If we find that the
2093 same expression is computed more than once, we eliminate repeated
2094 computations by using the target of the first one.
2096 2- Constant values and copy assignments. This is used to do very
2097 simplistic constant and copy propagation. When a constant or copy
2098 assignment is found, we map the value on the RHS of the assignment to
2099 the variable in the LHS in the CONST_AND_COPIES table. */
2102 optimize_stmt (basic_block bb, gimple_stmt_iterator si)
2104 gimple stmt, old_stmt;
2105 bool may_optimize_p;
2106 bool modified_p = false;
2108 old_stmt = stmt = gsi_stmt (si);
2110 if (gimple_code (stmt) == GIMPLE_COND)
2111 canonicalize_comparison (stmt);
2113 update_stmt_if_modified (stmt);
2114 opt_stats.num_stmts++;
2116 if (dump_file && (dump_flags & TDF_DETAILS))
2118 fprintf (dump_file, "Optimizing statement ");
2119 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2122 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2123 cprop_into_stmt (stmt);
2125 /* If the statement has been modified with constant replacements,
2126 fold its RHS before checking for redundant computations. */
2127 if (gimple_modified_p (stmt))
2131 /* Try to fold the statement making sure that STMT is kept
2133 if (fold_stmt (&si))
2135 stmt = gsi_stmt (si);
2136 gimple_set_modified (stmt, true);
2138 if (dump_file && (dump_flags & TDF_DETAILS))
2140 fprintf (dump_file, " Folded to: ");
2141 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2145 /* We only need to consider cases that can yield a gimple operand. */
2146 if (gimple_assign_single_p (stmt))
2147 rhs = gimple_assign_rhs1 (stmt);
2148 else if (gimple_code (stmt) == GIMPLE_GOTO)
2149 rhs = gimple_goto_dest (stmt);
2150 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2151 /* This should never be an ADDR_EXPR. */
2152 rhs = gimple_switch_index (stmt);
2154 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
2155 recompute_tree_invariant_for_addr_expr (rhs);
2157 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2158 even if fold_stmt updated the stmt already and thus cleared
2159 gimple_modified_p flag on it. */
2163 /* Check for redundant computations. Do this optimization only
2164 for assignments that have no volatile ops and conditionals. */
2165 may_optimize_p = (!gimple_has_volatile_ops (stmt)
2166 && ((is_gimple_assign (stmt)
2167 && !gimple_rhs_has_side_effects (stmt))
2168 || (is_gimple_call (stmt)
2169 && gimple_call_lhs (stmt) != NULL_TREE
2170 && !gimple_rhs_has_side_effects (stmt))
2171 || gimple_code (stmt) == GIMPLE_COND
2172 || gimple_code (stmt) == GIMPLE_SWITCH));
2176 if (gimple_code (stmt) == GIMPLE_CALL)
2178 /* Resolve __builtin_constant_p. If it hasn't been
2179 folded to integer_one_node by now, it's fairly
2180 certain that the value simply isn't constant. */
2181 tree callee = gimple_call_fndecl (stmt);
2183 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
2184 && DECL_FUNCTION_CODE (callee) == BUILT_IN_CONSTANT_P)
2186 propagate_tree_value_into_stmt (&si, integer_zero_node);
2187 stmt = gsi_stmt (si);
2191 update_stmt_if_modified (stmt);
2192 eliminate_redundant_computations (&si);
2193 stmt = gsi_stmt (si);
2195 /* Perform simple redundant store elimination. */
2196 if (gimple_assign_single_p (stmt)
2197 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2199 tree lhs = gimple_assign_lhs (stmt);
2200 tree rhs = gimple_assign_rhs1 (stmt);
2203 if (TREE_CODE (rhs) == SSA_NAME)
2205 tree tem = SSA_NAME_VALUE (rhs);
2209 /* Build a new statement with the RHS and LHS exchanged. */
2210 if (TREE_CODE (rhs) == SSA_NAME)
2212 gimple defstmt = SSA_NAME_DEF_STMT (rhs);
2213 new_stmt = gimple_build_assign (rhs, lhs);
2214 SSA_NAME_DEF_STMT (rhs) = defstmt;
2217 new_stmt = gimple_build_assign (rhs, lhs);
2218 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
2219 cached_lhs = lookup_avail_expr (new_stmt, false);
2221 && rhs == cached_lhs)
2223 basic_block bb = gimple_bb (stmt);
2224 int lp_nr = lookup_stmt_eh_lp (stmt);
2225 unlink_stmt_vdef (stmt);
2226 gsi_remove (&si, true);
2229 bitmap_set_bit (need_eh_cleanup, bb->index);
2230 if (dump_file && (dump_flags & TDF_DETAILS))
2231 fprintf (dump_file, " Flagged to clear EH edges.\n");
2238 /* Record any additional equivalences created by this statement. */
2239 if (is_gimple_assign (stmt))
2240 record_equivalences_from_stmt (stmt, may_optimize_p);
2242 /* If STMT is a COND_EXPR and it was modified, then we may know
2243 where it goes. If that is the case, then mark the CFG as altered.
2245 This will cause us to later call remove_unreachable_blocks and
2246 cleanup_tree_cfg when it is safe to do so. It is not safe to
2247 clean things up here since removal of edges and such can trigger
2248 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2251 That's all fine and good, except that once SSA_NAMEs are released
2252 to the manager, we must not call create_ssa_name until all references
2253 to released SSA_NAMEs have been eliminated.
2255 All references to the deleted SSA_NAMEs can not be eliminated until
2256 we remove unreachable blocks.
2258 We can not remove unreachable blocks until after we have completed
2259 any queued jump threading.
2261 We can not complete any queued jump threads until we have taken
2262 appropriate variables out of SSA form. Taking variables out of
2263 SSA form can call create_ssa_name and thus we lose.
2265 Ultimately I suspect we're going to need to change the interface
2266 into the SSA_NAME manager. */
2267 if (gimple_modified_p (stmt) || modified_p)
2271 update_stmt_if_modified (stmt);
2273 if (gimple_code (stmt) == GIMPLE_COND)
2274 val = fold_binary_loc (gimple_location (stmt),
2275 gimple_cond_code (stmt), boolean_type_node,
2276 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
2277 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2278 val = gimple_switch_index (stmt);
2280 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
2283 /* If we simplified a statement in such a way as to be shown that it
2284 cannot trap, update the eh information and the cfg to match. */
2285 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
2287 bitmap_set_bit (need_eh_cleanup, bb->index);
2288 if (dump_file && (dump_flags & TDF_DETAILS))
2289 fprintf (dump_file, " Flagged to clear EH edges.\n");
2294 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
2295 If found, return its LHS. Otherwise insert STMT in the table and
2298 Also, when an expression is first inserted in the table, it is also
2299 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
2300 we finish processing this block and its children. */
2303 lookup_avail_expr (gimple stmt, bool insert)
2308 struct expr_hash_elt element;
2310 /* Get LHS of assignment or call, else NULL_TREE. */
2311 lhs = gimple_get_lhs (stmt);
2313 initialize_hash_element (stmt, lhs, &element);
2315 if (dump_file && (dump_flags & TDF_DETAILS))
2317 fprintf (dump_file, "LKUP ");
2318 print_expr_hash_elt (dump_file, &element);
2321 /* Don't bother remembering constant assignments and copy operations.
2322 Constants and copy operations are handled by the constant/copy propagator
2323 in optimize_stmt. */
2324 if (element.expr.kind == EXPR_SINGLE
2325 && (TREE_CODE (element.expr.ops.single.rhs) == SSA_NAME
2326 || is_gimple_min_invariant (element.expr.ops.single.rhs)))
2329 /* Finally try to find the expression in the main expression hash table. */
2330 slot = htab_find_slot_with_hash (avail_exprs, &element, element.hash,
2331 (insert ? INSERT : NO_INSERT));
2337 struct expr_hash_elt *element2 = XNEW (struct expr_hash_elt);
2338 *element2 = element;
2339 element2->stamp = element2;
2340 *slot = (void *) element2;
2342 if (dump_file && (dump_flags & TDF_DETAILS))
2344 fprintf (dump_file, "2>>> ");
2345 print_expr_hash_elt (dump_file, element2);
2348 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element2);
2352 /* Extract the LHS of the assignment so that it can be used as the current
2353 definition of another variable. */
2354 lhs = ((struct expr_hash_elt *)*slot)->lhs;
2356 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2357 use the value from the const_and_copies table. */
2358 if (TREE_CODE (lhs) == SSA_NAME)
2360 temp = SSA_NAME_VALUE (lhs);
2365 if (dump_file && (dump_flags & TDF_DETAILS))
2367 fprintf (dump_file, "FIND: ");
2368 print_generic_expr (dump_file, lhs, 0);
2369 fprintf (dump_file, "\n");
2375 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number
2376 for expressions using the code of the expression and the SSA numbers of
2380 avail_expr_hash (const void *p)
2382 gimple stmt = ((const struct expr_hash_elt *)p)->stmt;
2383 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr;
2387 val = iterative_hash_hashable_expr (expr, val);
2389 /* If the hash table entry is not associated with a statement, then we
2390 can just hash the expression and not worry about virtual operands
2395 /* Add the SSA version numbers of the vuse operand. This is important
2396 because compound variables like arrays are not renamed in the
2397 operands. Rather, the rename is done on the virtual variable
2398 representing all the elements of the array. */
2399 if ((vuse = gimple_vuse (stmt)))
2400 val = iterative_hash_expr (vuse, val);
2406 real_avail_expr_hash (const void *p)
2408 return ((const struct expr_hash_elt *)p)->hash;
2412 avail_expr_eq (const void *p1, const void *p2)
2414 gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
2415 const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr;
2416 const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp;
2417 gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
2418 const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr;
2419 const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp;
2421 /* This case should apply only when removing entries from the table. */
2422 if (stamp1 == stamp2)
2426 We add stmts to a hash table and them modify them. To detect the case
2427 that we modify a stmt and then search for it, we assume that the hash
2428 is always modified by that change.
2429 We have to fully check why this doesn't happen on trunk or rewrite
2430 this in a more reliable (and easier to understand) way. */
2431 if (((const struct expr_hash_elt *)p1)->hash
2432 != ((const struct expr_hash_elt *)p2)->hash)
2435 /* In case of a collision, both RHS have to be identical and have the
2436 same VUSE operands. */
2437 if (hashable_expr_equal_p (expr1, expr2)
2438 && types_compatible_p (expr1->type, expr2->type))
2440 /* Note that STMT1 and/or STMT2 may be NULL. */
2441 return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE)
2442 == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE));
2448 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2449 up degenerate PHIs created by or exposed by jump threading. */
2451 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2455 degenerate_phi_result (gimple phi)
2457 tree lhs = gimple_phi_result (phi);
2461 /* Ignoring arguments which are the same as LHS, if all the remaining
2462 arguments are the same, then the PHI is a degenerate and has the
2463 value of that common argument. */
2464 for (i = 0; i < gimple_phi_num_args (phi); i++)
2466 tree arg = gimple_phi_arg_def (phi, i);
2474 else if (arg == val)
2476 /* We bring in some of operand_equal_p not only to speed things
2477 up, but also to avoid crashing when dereferencing the type of
2478 a released SSA name. */
2479 else if (TREE_CODE (val) != TREE_CODE (arg)
2480 || TREE_CODE (val) == SSA_NAME
2481 || !operand_equal_p (arg, val, 0))
2484 return (i == gimple_phi_num_args (phi) ? val : NULL);
2487 /* Given a statement STMT, which is either a PHI node or an assignment,
2488 remove it from the IL. */
2491 remove_stmt_or_phi (gimple stmt)
2493 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
2495 if (gimple_code (stmt) == GIMPLE_PHI)
2496 remove_phi_node (&gsi, true);
2499 gsi_remove (&gsi, true);
2500 release_defs (stmt);
2504 /* Given a statement STMT, which is either a PHI node or an assignment,
2505 return the "rhs" of the node, in the case of a non-degenerate
2506 phi, NULL is returned. */
2509 get_rhs_or_phi_arg (gimple stmt)
2511 if (gimple_code (stmt) == GIMPLE_PHI)
2512 return degenerate_phi_result (stmt);
2513 else if (gimple_assign_single_p (stmt))
2514 return gimple_assign_rhs1 (stmt);
2520 /* Given a statement STMT, which is either a PHI node or an assignment,
2521 return the "lhs" of the node. */
2524 get_lhs_or_phi_result (gimple stmt)
2526 if (gimple_code (stmt) == GIMPLE_PHI)
2527 return gimple_phi_result (stmt);
2528 else if (is_gimple_assign (stmt))
2529 return gimple_assign_lhs (stmt);
2534 /* Propagate RHS into all uses of LHS (when possible).
2536 RHS and LHS are derived from STMT, which is passed in solely so
2537 that we can remove it if propagation is successful.
2539 When propagating into a PHI node or into a statement which turns
2540 into a trivial copy or constant initialization, set the
2541 appropriate bit in INTERESTING_NAMEs so that we will visit those
2542 nodes as well in an effort to pick up secondary optimization
2546 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
2548 /* First verify that propagation is valid and isn't going to move a
2549 loop variant variable outside its loop. */
2550 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
2551 && (TREE_CODE (rhs) != SSA_NAME
2552 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
2553 && may_propagate_copy (lhs, rhs)
2554 && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
2556 use_operand_p use_p;
2557 imm_use_iterator iter;
2562 if (dump_file && (dump_flags & TDF_DETAILS))
2564 fprintf (dump_file, " Replacing '");
2565 print_generic_expr (dump_file, lhs, dump_flags);
2566 fprintf (dump_file, "' with %s '",
2567 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
2568 print_generic_expr (dump_file, rhs, dump_flags);
2569 fprintf (dump_file, "'\n");
2572 /* Walk over every use of LHS and try to replace the use with RHS.
2573 At this point the only reason why such a propagation would not
2574 be successful would be if the use occurs in an ASM_EXPR. */
2575 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
2577 /* Leave debug stmts alone. If we succeed in propagating
2578 all non-debug uses, we'll drop the DEF, and propagation
2579 into debug stmts will occur then. */
2580 if (gimple_debug_bind_p (use_stmt))
2583 /* It's not always safe to propagate into an ASM_EXPR. */
2584 if (gimple_code (use_stmt) == GIMPLE_ASM
2585 && ! may_propagate_copy_into_asm (lhs))
2591 /* It's not ok to propagate into the definition stmt of RHS.
2593 # prephitmp.12_36 = PHI <g_67.1_6(9)>
2594 g_67.1_6 = prephitmp.12_36;
2596 While this is strictly all dead code we do not want to
2597 deal with this here. */
2598 if (TREE_CODE (rhs) == SSA_NAME
2599 && SSA_NAME_DEF_STMT (rhs) == use_stmt)
2606 if (dump_file && (dump_flags & TDF_DETAILS))
2608 fprintf (dump_file, " Original statement:");
2609 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2612 /* Propagate the RHS into this use of the LHS. */
2613 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2614 propagate_value (use_p, rhs);
2616 /* Special cases to avoid useless calls into the folding
2617 routines, operand scanning, etc.
2619 First, propagation into a PHI may cause the PHI to become
2620 a degenerate, so mark the PHI as interesting. No other
2621 actions are necessary.
2623 Second, if we're propagating a virtual operand and the
2624 propagation does not change the underlying _DECL node for
2625 the virtual operand, then no further actions are necessary. */
2626 if (gimple_code (use_stmt) == GIMPLE_PHI
2627 || (! is_gimple_reg (lhs)
2628 && TREE_CODE (rhs) == SSA_NAME
2629 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
2632 if (dump_file && (dump_flags & TDF_DETAILS))
2634 fprintf (dump_file, " Updated statement:");
2635 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2638 /* Propagation into a PHI may expose new degenerate PHIs,
2639 so mark the result of the PHI as interesting. */
2640 if (gimple_code (use_stmt) == GIMPLE_PHI)
2642 tree result = get_lhs_or_phi_result (use_stmt);
2643 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2649 /* From this point onward we are propagating into a
2650 real statement. Folding may (or may not) be possible,
2651 we may expose new operands, expose dead EH edges,
2653 /* NOTE tuples. In the tuples world, fold_stmt_inplace
2654 cannot fold a call that simplifies to a constant,
2655 because the GIMPLE_CALL must be replaced by a
2656 GIMPLE_ASSIGN, and there is no way to effect such a
2657 transformation in-place. We might want to consider
2658 using the more general fold_stmt here. */
2660 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
2661 fold_stmt_inplace (&gsi);
2664 /* Sometimes propagation can expose new operands to the
2666 update_stmt (use_stmt);
2669 if (dump_file && (dump_flags & TDF_DETAILS))
2671 fprintf (dump_file, " Updated statement:");
2672 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2675 /* If we replaced a variable index with a constant, then
2676 we would need to update the invariant flag for ADDR_EXPRs. */
2677 if (gimple_assign_single_p (use_stmt)
2678 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
2679 recompute_tree_invariant_for_addr_expr
2680 (gimple_assign_rhs1 (use_stmt));
2682 /* If we cleaned up EH information from the statement,
2683 mark its containing block as needing EH cleanups. */
2684 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
2686 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
2687 if (dump_file && (dump_flags & TDF_DETAILS))
2688 fprintf (dump_file, " Flagged to clear EH edges.\n");
2691 /* Propagation may expose new trivial copy/constant propagation
2693 if (gimple_assign_single_p (use_stmt)
2694 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
2695 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
2696 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
2698 tree result = get_lhs_or_phi_result (use_stmt);
2699 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2702 /* Propagation into these nodes may make certain edges in
2703 the CFG unexecutable. We want to identify them as PHI nodes
2704 at the destination of those unexecutable edges may become
2706 else if (gimple_code (use_stmt) == GIMPLE_COND
2707 || gimple_code (use_stmt) == GIMPLE_SWITCH
2708 || gimple_code (use_stmt) == GIMPLE_GOTO)
2712 if (gimple_code (use_stmt) == GIMPLE_COND)
2713 val = fold_binary_loc (gimple_location (use_stmt),
2714 gimple_cond_code (use_stmt),
2716 gimple_cond_lhs (use_stmt),
2717 gimple_cond_rhs (use_stmt));
2718 else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
2719 val = gimple_switch_index (use_stmt);
2721 val = gimple_goto_dest (use_stmt);
2723 if (val && is_gimple_min_invariant (val))
2725 basic_block bb = gimple_bb (use_stmt);
2726 edge te = find_taken_edge (bb, val);
2729 gimple_stmt_iterator gsi, psi;
2731 /* Remove all outgoing edges except TE. */
2732 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
2736 /* Mark all the PHI nodes at the destination of
2737 the unexecutable edge as interesting. */
2738 for (psi = gsi_start_phis (e->dest);
2742 gimple phi = gsi_stmt (psi);
2744 tree result = gimple_phi_result (phi);
2745 int version = SSA_NAME_VERSION (result);
2747 bitmap_set_bit (interesting_names, version);
2750 te->probability += e->probability;
2752 te->count += e->count;
2760 gsi = gsi_last_bb (gimple_bb (use_stmt));
2761 gsi_remove (&gsi, true);
2763 /* And fixup the flags on the single remaining edge. */
2764 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
2765 te->flags &= ~EDGE_ABNORMAL;
2766 te->flags |= EDGE_FALLTHRU;
2767 if (te->probability > REG_BR_PROB_BASE)
2768 te->probability = REG_BR_PROB_BASE;
2773 /* Ensure there is nothing else to do. */
2774 gcc_assert (!all || has_zero_uses (lhs));
2776 /* If we were able to propagate away all uses of LHS, then
2777 we can remove STMT. */
2779 remove_stmt_or_phi (stmt);
2783 /* STMT is either a PHI node (potentially a degenerate PHI node) or
2784 a statement that is a trivial copy or constant initialization.
2786 Attempt to eliminate T by propagating its RHS into all uses of
2787 its LHS. This may in turn set new bits in INTERESTING_NAMES
2788 for nodes we want to revisit later.
2790 All exit paths should clear INTERESTING_NAMES for the result
2794 eliminate_const_or_copy (gimple stmt, bitmap interesting_names)
2796 tree lhs = get_lhs_or_phi_result (stmt);
2798 int version = SSA_NAME_VERSION (lhs);
2800 /* If the LHS of this statement or PHI has no uses, then we can
2801 just eliminate it. This can occur if, for example, the PHI
2802 was created by block duplication due to threading and its only
2803 use was in the conditional at the end of the block which was
2805 if (has_zero_uses (lhs))
2807 bitmap_clear_bit (interesting_names, version);
2808 remove_stmt_or_phi (stmt);
2812 /* Get the RHS of the assignment or PHI node if the PHI is a
2814 rhs = get_rhs_or_phi_arg (stmt);
2817 bitmap_clear_bit (interesting_names, version);
2821 propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
2823 /* Note that STMT may well have been deleted by now, so do
2824 not access it, instead use the saved version # to clear
2825 T's entry in the worklist. */
2826 bitmap_clear_bit (interesting_names, version);
2829 /* The first phase in degenerate PHI elimination.
2831 Eliminate the degenerate PHIs in BB, then recurse on the
2832 dominator children of BB. */
2835 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names)
2837 gimple_stmt_iterator gsi;
2840 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2842 gimple phi = gsi_stmt (gsi);
2844 eliminate_const_or_copy (phi, interesting_names);
2847 /* Recurse into the dominator children of BB. */
2848 for (son = first_dom_son (CDI_DOMINATORS, bb);
2850 son = next_dom_son (CDI_DOMINATORS, son))
2851 eliminate_degenerate_phis_1 (son, interesting_names);
2855 /* A very simple pass to eliminate degenerate PHI nodes from the
2856 IL. This is meant to be fast enough to be able to be run several
2857 times in the optimization pipeline.
2859 Certain optimizations, particularly those which duplicate blocks
2860 or remove edges from the CFG can create or expose PHIs which are
2861 trivial copies or constant initializations.
2863 While we could pick up these optimizations in DOM or with the
2864 combination of copy-prop and CCP, those solutions are far too
2865 heavy-weight for our needs.
2867 This implementation has two phases so that we can efficiently
2868 eliminate the first order degenerate PHIs and second order
2871 The first phase performs a dominator walk to identify and eliminate
2872 the vast majority of the degenerate PHIs. When a degenerate PHI
2873 is identified and eliminated any affected statements or PHIs
2874 are put on a worklist.
2876 The second phase eliminates degenerate PHIs and trivial copies
2877 or constant initializations using the worklist. This is how we
2878 pick up the secondary optimization opportunities with minimal
2882 eliminate_degenerate_phis (void)
2884 bitmap interesting_names;
2885 bitmap interesting_names1;
2887 /* Bitmap of blocks which need EH information updated. We can not
2888 update it on-the-fly as doing so invalidates the dominator tree. */
2889 need_eh_cleanup = BITMAP_ALLOC (NULL);
2891 /* INTERESTING_NAMES is effectively our worklist, indexed by
2894 A set bit indicates that the statement or PHI node which
2895 defines the SSA_NAME should be (re)examined to determine if
2896 it has become a degenerate PHI or trivial const/copy propagation
2899 Experiments have show we generally get better compilation
2900 time behavior with bitmaps rather than sbitmaps. */
2901 interesting_names = BITMAP_ALLOC (NULL);
2902 interesting_names1 = BITMAP_ALLOC (NULL);
2904 calculate_dominance_info (CDI_DOMINATORS);
2905 cfg_altered = false;
2907 /* First phase. Eliminate degenerate PHIs via a dominator
2910 Experiments have indicated that we generally get better
2911 compile-time behavior by visiting blocks in the first
2912 phase in dominator order. Presumably this is because walking
2913 in dominator order leaves fewer PHIs for later examination
2914 by the worklist phase. */
2915 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
2917 /* Second phase. Eliminate second order degenerate PHIs as well
2918 as trivial copies or constant initializations identified by
2919 the first phase or this phase. Basically we keep iterating
2920 until our set of INTERESTING_NAMEs is empty. */
2921 while (!bitmap_empty_p (interesting_names))
2926 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2927 changed during the loop. Copy it to another bitmap and
2929 bitmap_copy (interesting_names1, interesting_names);
2931 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
2933 tree name = ssa_name (i);
2935 /* Ignore SSA_NAMEs that have been released because
2936 their defining statement was deleted (unreachable). */
2938 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
2944 free_dominance_info (CDI_DOMINATORS);
2946 /* Propagation of const and copies may make some EH edges dead. Purge
2947 such edges from the CFG as needed. */
2948 if (!bitmap_empty_p (need_eh_cleanup))
2950 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
2951 BITMAP_FREE (need_eh_cleanup);
2954 BITMAP_FREE (interesting_names);
2955 BITMAP_FREE (interesting_names1);
2959 struct gimple_opt_pass pass_phi_only_cprop =
2963 "phicprop", /* name */
2964 gate_dominator, /* gate */
2965 eliminate_degenerate_phis, /* execute */
2968 0, /* static_pass_number */
2969 TV_TREE_PHI_CPROP, /* tv_id */
2970 PROP_cfg | PROP_ssa, /* properties_required */
2971 0, /* properties_provided */
2972 0, /* properties_destroyed */
2973 0, /* todo_flags_start */
2978 | TODO_update_ssa /* todo_flags_finish */