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)
1419 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1422 lhs = gimple_assign_lhs (stmt);
1423 if (TREE_CODE (lhs) != SSA_NAME)
1426 if (gimple_assign_rhs_code (stmt) != PLUS_EXPR
1427 && gimple_assign_rhs_code (stmt) != MINUS_EXPR)
1430 preinc = gimple_assign_rhs1 (stmt);
1432 if (TREE_CODE (preinc) != SSA_NAME)
1435 phi = SSA_NAME_DEF_STMT (preinc);
1436 if (gimple_code (phi) != GIMPLE_PHI)
1439 for (i = 0; i < gimple_phi_num_args (phi); i++)
1440 if (gimple_phi_arg_def (phi, i) == lhs)
1446 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1447 known value for that SSA_NAME (or NULL if no value is known).
1449 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1450 successors of BB. */
1453 cprop_into_successor_phis (basic_block bb)
1458 FOR_EACH_EDGE (e, ei, bb->succs)
1461 gimple_stmt_iterator gsi;
1463 /* If this is an abnormal edge, then we do not want to copy propagate
1464 into the PHI alternative associated with this edge. */
1465 if (e->flags & EDGE_ABNORMAL)
1468 gsi = gsi_start_phis (e->dest);
1469 if (gsi_end_p (gsi))
1473 for ( ; !gsi_end_p (gsi); gsi_next (&gsi))
1476 use_operand_p orig_p;
1478 gimple phi = gsi_stmt (gsi);
1480 /* The alternative may be associated with a constant, so verify
1481 it is an SSA_NAME before doing anything with it. */
1482 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx);
1483 orig_val = get_use_from_ptr (orig_p);
1484 if (TREE_CODE (orig_val) != SSA_NAME)
1487 /* If we have *ORIG_P in our constant/copy table, then replace
1488 ORIG_P with its value in our constant/copy table. */
1489 new_val = SSA_NAME_VALUE (orig_val);
1491 && new_val != orig_val
1492 && (TREE_CODE (new_val) == SSA_NAME
1493 || is_gimple_min_invariant (new_val))
1494 && may_propagate_copy (orig_val, new_val))
1495 propagate_value (orig_p, new_val);
1500 /* We have finished optimizing BB, record any information implied by
1501 taking a specific outgoing edge from BB. */
1504 record_edge_info (basic_block bb)
1506 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1507 struct edge_info *edge_info;
1509 if (! gsi_end_p (gsi))
1511 gimple stmt = gsi_stmt (gsi);
1512 location_t loc = gimple_location (stmt);
1514 if (gimple_code (stmt) == GIMPLE_SWITCH)
1516 tree index = gimple_switch_index (stmt);
1518 if (TREE_CODE (index) == SSA_NAME)
1521 int n_labels = gimple_switch_num_labels (stmt);
1522 tree *info = XCNEWVEC (tree, last_basic_block);
1526 for (i = 0; i < n_labels; i++)
1528 tree label = gimple_switch_label (stmt, i);
1529 basic_block target_bb = label_to_block (CASE_LABEL (label));
1530 if (CASE_HIGH (label)
1531 || !CASE_LOW (label)
1532 || info[target_bb->index])
1533 info[target_bb->index] = error_mark_node;
1535 info[target_bb->index] = label;
1538 FOR_EACH_EDGE (e, ei, bb->succs)
1540 basic_block target_bb = e->dest;
1541 tree label = info[target_bb->index];
1543 if (label != NULL && label != error_mark_node)
1545 tree x = fold_convert_loc (loc, TREE_TYPE (index),
1547 edge_info = allocate_edge_info (e);
1548 edge_info->lhs = index;
1556 /* A COND_EXPR may create equivalences too. */
1557 if (gimple_code (stmt) == GIMPLE_COND)
1562 tree op0 = gimple_cond_lhs (stmt);
1563 tree op1 = gimple_cond_rhs (stmt);
1564 enum tree_code code = gimple_cond_code (stmt);
1566 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1568 /* Special case comparing booleans against a constant as we
1569 know the value of OP0 on both arms of the branch. i.e., we
1570 can record an equivalence for OP0 rather than COND. */
1571 if ((code == EQ_EXPR || code == NE_EXPR)
1572 && TREE_CODE (op0) == SSA_NAME
1573 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
1574 && is_gimple_min_invariant (op1))
1576 if (code == EQ_EXPR)
1578 edge_info = allocate_edge_info (true_edge);
1579 edge_info->lhs = op0;
1580 edge_info->rhs = (integer_zerop (op1)
1581 ? boolean_false_node
1582 : boolean_true_node);
1584 edge_info = allocate_edge_info (false_edge);
1585 edge_info->lhs = op0;
1586 edge_info->rhs = (integer_zerop (op1)
1588 : boolean_false_node);
1592 edge_info = allocate_edge_info (true_edge);
1593 edge_info->lhs = op0;
1594 edge_info->rhs = (integer_zerop (op1)
1596 : boolean_false_node);
1598 edge_info = allocate_edge_info (false_edge);
1599 edge_info->lhs = op0;
1600 edge_info->rhs = (integer_zerop (op1)
1601 ? boolean_false_node
1602 : boolean_true_node);
1605 else if (is_gimple_min_invariant (op0)
1606 && (TREE_CODE (op1) == SSA_NAME
1607 || is_gimple_min_invariant (op1)))
1609 tree cond = build2 (code, boolean_type_node, op0, op1);
1610 tree inverted = invert_truthvalue_loc (loc, cond);
1611 struct edge_info *edge_info;
1613 edge_info = allocate_edge_info (true_edge);
1614 record_conditions (edge_info, cond, inverted);
1616 if (code == EQ_EXPR)
1618 edge_info->lhs = op1;
1619 edge_info->rhs = op0;
1622 edge_info = allocate_edge_info (false_edge);
1623 record_conditions (edge_info, inverted, cond);
1625 if (TREE_CODE (inverted) == EQ_EXPR)
1627 edge_info->lhs = op1;
1628 edge_info->rhs = op0;
1632 else if (TREE_CODE (op0) == SSA_NAME
1633 && (is_gimple_min_invariant (op1)
1634 || TREE_CODE (op1) == SSA_NAME))
1636 tree cond = build2 (code, boolean_type_node, op0, op1);
1637 tree inverted = invert_truthvalue_loc (loc, cond);
1638 struct edge_info *edge_info;
1640 edge_info = allocate_edge_info (true_edge);
1641 record_conditions (edge_info, cond, inverted);
1643 if (code == EQ_EXPR)
1645 edge_info->lhs = op0;
1646 edge_info->rhs = op1;
1649 edge_info = allocate_edge_info (false_edge);
1650 record_conditions (edge_info, inverted, cond);
1652 if (TREE_CODE (inverted) == EQ_EXPR)
1654 edge_info->lhs = op0;
1655 edge_info->rhs = op1;
1660 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1665 dom_opt_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1668 gimple_stmt_iterator gsi;
1670 if (dump_file && (dump_flags & TDF_DETAILS))
1671 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
1673 /* Push a marker on the stacks of local information so that we know how
1674 far to unwind when we finalize this block. */
1675 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
1676 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1678 record_equivalences_from_incoming_edge (bb);
1680 /* PHI nodes can create equivalences too. */
1681 record_equivalences_from_phis (bb);
1683 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1684 optimize_stmt (bb, gsi);
1686 /* Now prepare to process dominated blocks. */
1687 record_edge_info (bb);
1688 cprop_into_successor_phis (bb);
1691 /* We have finished processing the dominator children of BB, perform
1692 any finalization actions in preparation for leaving this node in
1693 the dominator tree. */
1696 dom_opt_leave_block (struct dom_walk_data *walk_data, basic_block bb)
1700 /* If we have an outgoing edge to a block with multiple incoming and
1701 outgoing edges, then we may be able to thread the edge, i.e., we
1702 may be able to statically determine which of the outgoing edges
1703 will be traversed when the incoming edge from BB is traversed. */
1704 if (single_succ_p (bb)
1705 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0
1706 && potentially_threadable_block (single_succ (bb)))
1708 dom_thread_across_edge (walk_data, single_succ_edge (bb));
1710 else if ((last = last_stmt (bb))
1711 && gimple_code (last) == GIMPLE_COND
1712 && EDGE_COUNT (bb->succs) == 2
1713 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
1714 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
1716 edge true_edge, false_edge;
1718 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1720 /* Only try to thread the edge if it reaches a target block with
1721 more than one predecessor and more than one successor. */
1722 if (potentially_threadable_block (true_edge->dest))
1724 struct edge_info *edge_info;
1727 /* Push a marker onto the available expression stack so that we
1728 unwind any expressions related to the TRUE arm before processing
1729 the false arm below. */
1730 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL);
1731 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1733 edge_info = (struct edge_info *) true_edge->aux;
1735 /* If we have info associated with this edge, record it into
1736 our equivalence tables. */
1739 cond_equivalence *eq;
1740 tree lhs = edge_info->lhs;
1741 tree rhs = edge_info->rhs;
1743 /* If we have a simple NAME = VALUE equivalence, record it. */
1744 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1745 record_const_or_copy (lhs, rhs);
1747 /* If we have 0 = COND or 1 = COND equivalences, record them
1748 into our expression hash tables. */
1749 for (i = 0; VEC_iterate (cond_equivalence,
1750 edge_info->cond_equivalences, i, eq); ++i)
1754 dom_thread_across_edge (walk_data, true_edge);
1756 /* And restore the various tables to their state before
1757 we threaded this edge. */
1758 remove_local_expressions_from_table ();
1761 /* Similarly for the ELSE arm. */
1762 if (potentially_threadable_block (false_edge->dest))
1764 struct edge_info *edge_info;
1767 VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE);
1768 edge_info = (struct edge_info *) false_edge->aux;
1770 /* If we have info associated with this edge, record it into
1771 our equivalence tables. */
1774 cond_equivalence *eq;
1775 tree lhs = edge_info->lhs;
1776 tree rhs = edge_info->rhs;
1778 /* If we have a simple NAME = VALUE equivalence, record it. */
1779 if (lhs && TREE_CODE (lhs) == SSA_NAME)
1780 record_const_or_copy (lhs, rhs);
1782 /* If we have 0 = COND or 1 = COND equivalences, record them
1783 into our expression hash tables. */
1784 for (i = 0; VEC_iterate (cond_equivalence,
1785 edge_info->cond_equivalences, i, eq); ++i)
1789 /* Now thread the edge. */
1790 dom_thread_across_edge (walk_data, false_edge);
1792 /* No need to remove local expressions from our tables
1793 or restore vars to their original value as that will
1794 be done immediately below. */
1798 remove_local_expressions_from_table ();
1799 restore_vars_to_original_value ();
1802 /* Search for redundant computations in STMT. If any are found, then
1803 replace them with the variable holding the result of the computation.
1805 If safe, record this expression into the available expression hash
1809 eliminate_redundant_computations (gimple_stmt_iterator* gsi)
1814 bool assigns_var_p = false;
1816 gimple stmt = gsi_stmt (*gsi);
1818 tree def = gimple_get_lhs (stmt);
1820 /* Certain expressions on the RHS can be optimized away, but can not
1821 themselves be entered into the hash tables. */
1823 || TREE_CODE (def) != SSA_NAME
1824 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
1825 || gimple_vdef (stmt)
1826 /* Do not record equivalences for increments of ivs. This would create
1827 overlapping live ranges for a very questionable gain. */
1828 || simple_iv_increment_p (stmt))
1831 /* Check if the expression has been computed before. */
1832 cached_lhs = lookup_avail_expr (stmt, insert);
1834 opt_stats.num_exprs_considered++;
1836 /* Get the type of the expression we are trying to optimize. */
1837 if (is_gimple_assign (stmt))
1839 expr_type = TREE_TYPE (gimple_assign_lhs (stmt));
1840 assigns_var_p = true;
1842 else if (gimple_code (stmt) == GIMPLE_COND)
1843 expr_type = boolean_type_node;
1844 else if (is_gimple_call (stmt))
1846 gcc_assert (gimple_call_lhs (stmt));
1847 expr_type = TREE_TYPE (gimple_call_lhs (stmt));
1848 assigns_var_p = true;
1850 else if (gimple_code (stmt) == GIMPLE_SWITCH)
1851 expr_type = TREE_TYPE (gimple_switch_index (stmt));
1858 /* It is safe to ignore types here since we have already done
1859 type checking in the hashing and equality routines. In fact
1860 type checking here merely gets in the way of constant
1861 propagation. Also, make sure that it is safe to propagate
1862 CACHED_LHS into the expression in STMT. */
1863 if ((TREE_CODE (cached_lhs) != SSA_NAME
1865 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))))
1866 || may_propagate_copy_into_stmt (stmt, cached_lhs))
1868 gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME
1869 || is_gimple_min_invariant (cached_lhs));
1871 if (dump_file && (dump_flags & TDF_DETAILS))
1873 fprintf (dump_file, " Replaced redundant expr '");
1874 print_gimple_expr (dump_file, stmt, 0, dump_flags);
1875 fprintf (dump_file, "' with '");
1876 print_generic_expr (dump_file, cached_lhs, dump_flags);
1877 fprintf (dump_file, "'\n");
1883 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))
1884 cached_lhs = fold_convert (expr_type, cached_lhs);
1886 propagate_tree_value_into_stmt (gsi, cached_lhs);
1888 /* Since it is always necessary to mark the result as modified,
1889 perhaps we should move this into propagate_tree_value_into_stmt
1891 gimple_set_modified (gsi_stmt (*gsi), true);
1895 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1896 the available expressions table or the const_and_copies table.
1897 Detect and record those equivalences. */
1898 /* We handle only very simple copy equivalences here. The heavy
1899 lifing is done by eliminate_redundant_computations. */
1902 record_equivalences_from_stmt (gimple stmt, int may_optimize_p)
1905 enum tree_code lhs_code;
1907 gcc_assert (is_gimple_assign (stmt));
1909 lhs = gimple_assign_lhs (stmt);
1910 lhs_code = TREE_CODE (lhs);
1912 if (lhs_code == SSA_NAME
1913 && gimple_assign_single_p (stmt))
1915 tree rhs = gimple_assign_rhs1 (stmt);
1917 /* If the RHS of the assignment is a constant or another variable that
1918 may be propagated, register it in the CONST_AND_COPIES table. We
1919 do not need to record unwind data for this, since this is a true
1920 assignment and not an equivalence inferred from a comparison. All
1921 uses of this ssa name are dominated by this assignment, so unwinding
1922 just costs time and space. */
1924 && (TREE_CODE (rhs) == SSA_NAME
1925 || is_gimple_min_invariant (rhs)))
1927 if (dump_file && (dump_flags & TDF_DETAILS))
1929 fprintf (dump_file, "==== ASGN ");
1930 print_generic_expr (dump_file, lhs, 0);
1931 fprintf (dump_file, " = ");
1932 print_generic_expr (dump_file, rhs, 0);
1933 fprintf (dump_file, "\n");
1936 set_ssa_name_value (lhs, rhs);
1940 /* A memory store, even an aliased store, creates a useful
1941 equivalence. By exchanging the LHS and RHS, creating suitable
1942 vops and recording the result in the available expression table,
1943 we may be able to expose more redundant loads. */
1944 if (!gimple_has_volatile_ops (stmt)
1945 && gimple_references_memory_p (stmt)
1946 && gimple_assign_single_p (stmt)
1947 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1948 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
1949 && !is_gimple_reg (lhs))
1951 tree rhs = gimple_assign_rhs1 (stmt);
1954 /* Build a new statement with the RHS and LHS exchanged. */
1955 if (TREE_CODE (rhs) == SSA_NAME)
1957 /* NOTE tuples. The call to gimple_build_assign below replaced
1958 a call to build_gimple_modify_stmt, which did not set the
1959 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
1960 may cause an SSA validation failure, as the LHS may be a
1961 default-initialized name and should have no definition. I'm
1962 a bit dubious of this, as the artificial statement that we
1963 generate here may in fact be ill-formed, but it is simply
1964 used as an internal device in this pass, and never becomes
1966 gimple defstmt = SSA_NAME_DEF_STMT (rhs);
1967 new_stmt = gimple_build_assign (rhs, lhs);
1968 SSA_NAME_DEF_STMT (rhs) = defstmt;
1971 new_stmt = gimple_build_assign (rhs, lhs);
1973 gimple_set_vuse (new_stmt, gimple_vdef (stmt));
1975 /* Finally enter the statement into the available expression
1977 lookup_avail_expr (new_stmt, true);
1981 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
1982 CONST_AND_COPIES. */
1985 cprop_operand (gimple stmt, use_operand_p op_p)
1988 tree op = USE_FROM_PTR (op_p);
1990 /* If the operand has a known constant value or it is known to be a
1991 copy of some other variable, use the value or copy stored in
1992 CONST_AND_COPIES. */
1993 val = SSA_NAME_VALUE (op);
1994 if (val && val != op)
1996 /* Do not change the base variable in the virtual operand
1997 tables. That would make it impossible to reconstruct
1998 the renamed virtual operand if we later modify this
1999 statement. Also only allow the new value to be an SSA_NAME
2000 for propagation into virtual operands. */
2001 if (!is_gimple_reg (op)
2002 && (TREE_CODE (val) != SSA_NAME
2003 || is_gimple_reg (val)
2004 || get_virtual_var (val) != get_virtual_var (op)))
2007 /* Do not replace hard register operands in asm statements. */
2008 if (gimple_code (stmt) == GIMPLE_ASM
2009 && !may_propagate_copy_into_asm (op))
2012 /* Certain operands are not allowed to be copy propagated due
2013 to their interaction with exception handling and some GCC
2015 if (!may_propagate_copy (op, val))
2018 /* Do not propagate addresses that point to volatiles into memory
2019 stmts without volatile operands. */
2020 if (POINTER_TYPE_P (TREE_TYPE (val))
2021 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val)))
2022 && gimple_has_mem_ops (stmt)
2023 && !gimple_has_volatile_ops (stmt))
2026 /* Do not propagate copies if the propagated value is at a deeper loop
2027 depth than the propagatee. Otherwise, this may move loop variant
2028 variables outside of their loops and prevent coalescing
2029 opportunities. If the value was loop invariant, it will be hoisted
2030 by LICM and exposed for copy propagation. */
2031 if (loop_depth_of_name (val) > loop_depth_of_name (op))
2034 /* Do not propagate copies into simple IV increment statements.
2035 See PR23821 for how this can disturb IV analysis. */
2036 if (TREE_CODE (val) != INTEGER_CST
2037 && simple_iv_increment_p (stmt))
2041 if (dump_file && (dump_flags & TDF_DETAILS))
2043 fprintf (dump_file, " Replaced '");
2044 print_generic_expr (dump_file, op, dump_flags);
2045 fprintf (dump_file, "' with %s '",
2046 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2047 print_generic_expr (dump_file, val, dump_flags);
2048 fprintf (dump_file, "'\n");
2051 if (TREE_CODE (val) != SSA_NAME)
2052 opt_stats.num_const_prop++;
2054 opt_stats.num_copy_prop++;
2056 propagate_value (op_p, val);
2058 /* And note that we modified this statement. This is now
2059 safe, even if we changed virtual operands since we will
2060 rescan the statement and rewrite its operands again. */
2061 gimple_set_modified (stmt, true);
2065 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2066 known value for that SSA_NAME (or NULL if no value is known).
2068 Propagate values from CONST_AND_COPIES into the uses, vuses and
2069 vdef_ops of STMT. */
2072 cprop_into_stmt (gimple stmt)
2077 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_ALL_USES)
2079 if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
2080 cprop_operand (stmt, op_p);
2084 /* Optimize the statement pointed to by iterator SI.
2086 We try to perform some simplistic global redundancy elimination and
2087 constant propagation:
2089 1- To detect global redundancy, we keep track of expressions that have
2090 been computed in this block and its dominators. If we find that the
2091 same expression is computed more than once, we eliminate repeated
2092 computations by using the target of the first one.
2094 2- Constant values and copy assignments. This is used to do very
2095 simplistic constant and copy propagation. When a constant or copy
2096 assignment is found, we map the value on the RHS of the assignment to
2097 the variable in the LHS in the CONST_AND_COPIES table. */
2100 optimize_stmt (basic_block bb, gimple_stmt_iterator si)
2102 gimple stmt, old_stmt;
2103 bool may_optimize_p;
2104 bool modified_p = false;
2106 old_stmt = stmt = gsi_stmt (si);
2108 if (gimple_code (stmt) == GIMPLE_COND)
2109 canonicalize_comparison (stmt);
2111 update_stmt_if_modified (stmt);
2112 opt_stats.num_stmts++;
2114 if (dump_file && (dump_flags & TDF_DETAILS))
2116 fprintf (dump_file, "Optimizing statement ");
2117 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2120 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2121 cprop_into_stmt (stmt);
2123 /* If the statement has been modified with constant replacements,
2124 fold its RHS before checking for redundant computations. */
2125 if (gimple_modified_p (stmt))
2129 /* Try to fold the statement making sure that STMT is kept
2131 if (fold_stmt (&si))
2133 stmt = gsi_stmt (si);
2134 gimple_set_modified (stmt, true);
2136 if (dump_file && (dump_flags & TDF_DETAILS))
2138 fprintf (dump_file, " Folded to: ");
2139 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2143 /* We only need to consider cases that can yield a gimple operand. */
2144 if (gimple_assign_single_p (stmt))
2145 rhs = gimple_assign_rhs1 (stmt);
2146 else if (gimple_code (stmt) == GIMPLE_GOTO)
2147 rhs = gimple_goto_dest (stmt);
2148 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2149 /* This should never be an ADDR_EXPR. */
2150 rhs = gimple_switch_index (stmt);
2152 if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
2153 recompute_tree_invariant_for_addr_expr (rhs);
2155 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2156 even if fold_stmt updated the stmt already and thus cleared
2157 gimple_modified_p flag on it. */
2161 /* Check for redundant computations. Do this optimization only
2162 for assignments that have no volatile ops and conditionals. */
2163 may_optimize_p = (!gimple_has_volatile_ops (stmt)
2164 && ((is_gimple_assign (stmt)
2165 && !gimple_rhs_has_side_effects (stmt))
2166 || (is_gimple_call (stmt)
2167 && gimple_call_lhs (stmt) != NULL_TREE
2168 && !gimple_rhs_has_side_effects (stmt))
2169 || gimple_code (stmt) == GIMPLE_COND
2170 || gimple_code (stmt) == GIMPLE_SWITCH));
2174 if (gimple_code (stmt) == GIMPLE_CALL)
2176 /* Resolve __builtin_constant_p. If it hasn't been
2177 folded to integer_one_node by now, it's fairly
2178 certain that the value simply isn't constant. */
2179 tree callee = gimple_call_fndecl (stmt);
2181 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
2182 && DECL_FUNCTION_CODE (callee) == BUILT_IN_CONSTANT_P)
2184 propagate_tree_value_into_stmt (&si, integer_zero_node);
2185 stmt = gsi_stmt (si);
2189 update_stmt_if_modified (stmt);
2190 eliminate_redundant_computations (&si);
2191 stmt = gsi_stmt (si);
2193 /* Perform simple redundant store elimination. */
2194 if (gimple_assign_single_p (stmt)
2195 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2197 tree lhs = gimple_assign_lhs (stmt);
2198 tree rhs = gimple_assign_rhs1 (stmt);
2201 if (TREE_CODE (rhs) == SSA_NAME)
2203 tree tem = SSA_NAME_VALUE (rhs);
2207 /* Build a new statement with the RHS and LHS exchanged. */
2208 if (TREE_CODE (rhs) == SSA_NAME)
2210 gimple defstmt = SSA_NAME_DEF_STMT (rhs);
2211 new_stmt = gimple_build_assign (rhs, lhs);
2212 SSA_NAME_DEF_STMT (rhs) = defstmt;
2215 new_stmt = gimple_build_assign (rhs, lhs);
2216 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
2217 cached_lhs = lookup_avail_expr (new_stmt, false);
2219 && rhs == cached_lhs)
2221 basic_block bb = gimple_bb (stmt);
2222 int lp_nr = lookup_stmt_eh_lp (stmt);
2223 unlink_stmt_vdef (stmt);
2224 gsi_remove (&si, true);
2227 bitmap_set_bit (need_eh_cleanup, bb->index);
2228 if (dump_file && (dump_flags & TDF_DETAILS))
2229 fprintf (dump_file, " Flagged to clear EH edges.\n");
2236 /* Record any additional equivalences created by this statement. */
2237 if (is_gimple_assign (stmt))
2238 record_equivalences_from_stmt (stmt, may_optimize_p);
2240 /* If STMT is a COND_EXPR and it was modified, then we may know
2241 where it goes. If that is the case, then mark the CFG as altered.
2243 This will cause us to later call remove_unreachable_blocks and
2244 cleanup_tree_cfg when it is safe to do so. It is not safe to
2245 clean things up here since removal of edges and such can trigger
2246 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2249 That's all fine and good, except that once SSA_NAMEs are released
2250 to the manager, we must not call create_ssa_name until all references
2251 to released SSA_NAMEs have been eliminated.
2253 All references to the deleted SSA_NAMEs can not be eliminated until
2254 we remove unreachable blocks.
2256 We can not remove unreachable blocks until after we have completed
2257 any queued jump threading.
2259 We can not complete any queued jump threads until we have taken
2260 appropriate variables out of SSA form. Taking variables out of
2261 SSA form can call create_ssa_name and thus we lose.
2263 Ultimately I suspect we're going to need to change the interface
2264 into the SSA_NAME manager. */
2265 if (gimple_modified_p (stmt) || modified_p)
2269 update_stmt_if_modified (stmt);
2271 if (gimple_code (stmt) == GIMPLE_COND)
2272 val = fold_binary_loc (gimple_location (stmt),
2273 gimple_cond_code (stmt), boolean_type_node,
2274 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
2275 else if (gimple_code (stmt) == GIMPLE_SWITCH)
2276 val = gimple_switch_index (stmt);
2278 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
2281 /* If we simplified a statement in such a way as to be shown that it
2282 cannot trap, update the eh information and the cfg to match. */
2283 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
2285 bitmap_set_bit (need_eh_cleanup, bb->index);
2286 if (dump_file && (dump_flags & TDF_DETAILS))
2287 fprintf (dump_file, " Flagged to clear EH edges.\n");
2292 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
2293 If found, return its LHS. Otherwise insert STMT in the table and
2296 Also, when an expression is first inserted in the table, it is also
2297 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
2298 we finish processing this block and its children. */
2301 lookup_avail_expr (gimple stmt, bool insert)
2306 struct expr_hash_elt element;
2308 /* Get LHS of assignment or call, else NULL_TREE. */
2309 lhs = gimple_get_lhs (stmt);
2311 initialize_hash_element (stmt, lhs, &element);
2313 if (dump_file && (dump_flags & TDF_DETAILS))
2315 fprintf (dump_file, "LKUP ");
2316 print_expr_hash_elt (dump_file, &element);
2319 /* Don't bother remembering constant assignments and copy operations.
2320 Constants and copy operations are handled by the constant/copy propagator
2321 in optimize_stmt. */
2322 if (element.expr.kind == EXPR_SINGLE
2323 && (TREE_CODE (element.expr.ops.single.rhs) == SSA_NAME
2324 || is_gimple_min_invariant (element.expr.ops.single.rhs)))
2327 /* Finally try to find the expression in the main expression hash table. */
2328 slot = htab_find_slot_with_hash (avail_exprs, &element, element.hash,
2329 (insert ? INSERT : NO_INSERT));
2335 struct expr_hash_elt *element2 = XNEW (struct expr_hash_elt);
2336 *element2 = element;
2337 element2->stamp = element2;
2338 *slot = (void *) element2;
2340 if (dump_file && (dump_flags & TDF_DETAILS))
2342 fprintf (dump_file, "2>>> ");
2343 print_expr_hash_elt (dump_file, element2);
2346 VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, element2);
2350 /* Extract the LHS of the assignment so that it can be used as the current
2351 definition of another variable. */
2352 lhs = ((struct expr_hash_elt *)*slot)->lhs;
2354 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2355 use the value from the const_and_copies table. */
2356 if (TREE_CODE (lhs) == SSA_NAME)
2358 temp = SSA_NAME_VALUE (lhs);
2363 if (dump_file && (dump_flags & TDF_DETAILS))
2365 fprintf (dump_file, "FIND: ");
2366 print_generic_expr (dump_file, lhs, 0);
2367 fprintf (dump_file, "\n");
2373 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number
2374 for expressions using the code of the expression and the SSA numbers of
2378 avail_expr_hash (const void *p)
2380 gimple stmt = ((const struct expr_hash_elt *)p)->stmt;
2381 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr;
2385 val = iterative_hash_hashable_expr (expr, val);
2387 /* If the hash table entry is not associated with a statement, then we
2388 can just hash the expression and not worry about virtual operands
2393 /* Add the SSA version numbers of the vuse operand. This is important
2394 because compound variables like arrays are not renamed in the
2395 operands. Rather, the rename is done on the virtual variable
2396 representing all the elements of the array. */
2397 if ((vuse = gimple_vuse (stmt)))
2398 val = iterative_hash_expr (vuse, val);
2404 real_avail_expr_hash (const void *p)
2406 return ((const struct expr_hash_elt *)p)->hash;
2410 avail_expr_eq (const void *p1, const void *p2)
2412 gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt;
2413 const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr;
2414 const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp;
2415 gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt;
2416 const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr;
2417 const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp;
2419 /* This case should apply only when removing entries from the table. */
2420 if (stamp1 == stamp2)
2424 We add stmts to a hash table and them modify them. To detect the case
2425 that we modify a stmt and then search for it, we assume that the hash
2426 is always modified by that change.
2427 We have to fully check why this doesn't happen on trunk or rewrite
2428 this in a more reliable (and easier to understand) way. */
2429 if (((const struct expr_hash_elt *)p1)->hash
2430 != ((const struct expr_hash_elt *)p2)->hash)
2433 /* In case of a collision, both RHS have to be identical and have the
2434 same VUSE operands. */
2435 if (hashable_expr_equal_p (expr1, expr2)
2436 && types_compatible_p (expr1->type, expr2->type))
2438 /* Note that STMT1 and/or STMT2 may be NULL. */
2439 return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE)
2440 == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE));
2446 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2447 up degenerate PHIs created by or exposed by jump threading. */
2449 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2453 degenerate_phi_result (gimple phi)
2455 tree lhs = gimple_phi_result (phi);
2459 /* Ignoring arguments which are the same as LHS, if all the remaining
2460 arguments are the same, then the PHI is a degenerate and has the
2461 value of that common argument. */
2462 for (i = 0; i < gimple_phi_num_args (phi); i++)
2464 tree arg = gimple_phi_arg_def (phi, i);
2472 else if (arg == val)
2474 /* We bring in some of operand_equal_p not only to speed things
2475 up, but also to avoid crashing when dereferencing the type of
2476 a released SSA name. */
2477 else if (TREE_CODE (val) != TREE_CODE (arg)
2478 || TREE_CODE (val) == SSA_NAME
2479 || !operand_equal_p (arg, val, 0))
2482 return (i == gimple_phi_num_args (phi) ? val : NULL);
2485 /* Given a statement STMT, which is either a PHI node or an assignment,
2486 remove it from the IL. */
2489 remove_stmt_or_phi (gimple stmt)
2491 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
2493 if (gimple_code (stmt) == GIMPLE_PHI)
2494 remove_phi_node (&gsi, true);
2497 gsi_remove (&gsi, true);
2498 release_defs (stmt);
2502 /* Given a statement STMT, which is either a PHI node or an assignment,
2503 return the "rhs" of the node, in the case of a non-degenerate
2504 phi, NULL is returned. */
2507 get_rhs_or_phi_arg (gimple stmt)
2509 if (gimple_code (stmt) == GIMPLE_PHI)
2510 return degenerate_phi_result (stmt);
2511 else if (gimple_assign_single_p (stmt))
2512 return gimple_assign_rhs1 (stmt);
2518 /* Given a statement STMT, which is either a PHI node or an assignment,
2519 return the "lhs" of the node. */
2522 get_lhs_or_phi_result (gimple stmt)
2524 if (gimple_code (stmt) == GIMPLE_PHI)
2525 return gimple_phi_result (stmt);
2526 else if (is_gimple_assign (stmt))
2527 return gimple_assign_lhs (stmt);
2532 /* Propagate RHS into all uses of LHS (when possible).
2534 RHS and LHS are derived from STMT, which is passed in solely so
2535 that we can remove it if propagation is successful.
2537 When propagating into a PHI node or into a statement which turns
2538 into a trivial copy or constant initialization, set the
2539 appropriate bit in INTERESTING_NAMEs so that we will visit those
2540 nodes as well in an effort to pick up secondary optimization
2544 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names)
2546 /* First verify that propagation is valid and isn't going to move a
2547 loop variant variable outside its loop. */
2548 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)
2549 && (TREE_CODE (rhs) != SSA_NAME
2550 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
2551 && may_propagate_copy (lhs, rhs)
2552 && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs))
2554 use_operand_p use_p;
2555 imm_use_iterator iter;
2560 if (dump_file && (dump_flags & TDF_DETAILS))
2562 fprintf (dump_file, " Replacing '");
2563 print_generic_expr (dump_file, lhs, dump_flags);
2564 fprintf (dump_file, "' with %s '",
2565 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
2566 print_generic_expr (dump_file, rhs, dump_flags);
2567 fprintf (dump_file, "'\n");
2570 /* Walk over every use of LHS and try to replace the use with RHS.
2571 At this point the only reason why such a propagation would not
2572 be successful would be if the use occurs in an ASM_EXPR. */
2573 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
2575 /* Leave debug stmts alone. If we succeed in propagating
2576 all non-debug uses, we'll drop the DEF, and propagation
2577 into debug stmts will occur then. */
2578 if (gimple_debug_bind_p (use_stmt))
2581 /* It's not always safe to propagate into an ASM_EXPR. */
2582 if (gimple_code (use_stmt) == GIMPLE_ASM
2583 && ! may_propagate_copy_into_asm (lhs))
2589 /* It's not ok to propagate into the definition stmt of RHS.
2591 # prephitmp.12_36 = PHI <g_67.1_6(9)>
2592 g_67.1_6 = prephitmp.12_36;
2594 While this is strictly all dead code we do not want to
2595 deal with this here. */
2596 if (TREE_CODE (rhs) == SSA_NAME
2597 && SSA_NAME_DEF_STMT (rhs) == use_stmt)
2604 if (dump_file && (dump_flags & TDF_DETAILS))
2606 fprintf (dump_file, " Original statement:");
2607 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2610 /* Propagate the RHS into this use of the LHS. */
2611 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
2612 propagate_value (use_p, rhs);
2614 /* Special cases to avoid useless calls into the folding
2615 routines, operand scanning, etc.
2617 First, propagation into a PHI may cause the PHI to become
2618 a degenerate, so mark the PHI as interesting. No other
2619 actions are necessary.
2621 Second, if we're propagating a virtual operand and the
2622 propagation does not change the underlying _DECL node for
2623 the virtual operand, then no further actions are necessary. */
2624 if (gimple_code (use_stmt) == GIMPLE_PHI
2625 || (! is_gimple_reg (lhs)
2626 && TREE_CODE (rhs) == SSA_NAME
2627 && SSA_NAME_VAR (lhs) == SSA_NAME_VAR (rhs)))
2630 if (dump_file && (dump_flags & TDF_DETAILS))
2632 fprintf (dump_file, " Updated statement:");
2633 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2636 /* Propagation into a PHI may expose new degenerate PHIs,
2637 so mark the result of the PHI as interesting. */
2638 if (gimple_code (use_stmt) == GIMPLE_PHI)
2640 tree result = get_lhs_or_phi_result (use_stmt);
2641 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2647 /* From this point onward we are propagating into a
2648 real statement. Folding may (or may not) be possible,
2649 we may expose new operands, expose dead EH edges,
2651 /* NOTE tuples. In the tuples world, fold_stmt_inplace
2652 cannot fold a call that simplifies to a constant,
2653 because the GIMPLE_CALL must be replaced by a
2654 GIMPLE_ASSIGN, and there is no way to effect such a
2655 transformation in-place. We might want to consider
2656 using the more general fold_stmt here. */
2657 fold_stmt_inplace (use_stmt);
2659 /* Sometimes propagation can expose new operands to the
2661 update_stmt (use_stmt);
2664 if (dump_file && (dump_flags & TDF_DETAILS))
2666 fprintf (dump_file, " Updated statement:");
2667 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
2670 /* If we replaced a variable index with a constant, then
2671 we would need to update the invariant flag for ADDR_EXPRs. */
2672 if (gimple_assign_single_p (use_stmt)
2673 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
2674 recompute_tree_invariant_for_addr_expr
2675 (gimple_assign_rhs1 (use_stmt));
2677 /* If we cleaned up EH information from the statement,
2678 mark its containing block as needing EH cleanups. */
2679 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
2681 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
2682 if (dump_file && (dump_flags & TDF_DETAILS))
2683 fprintf (dump_file, " Flagged to clear EH edges.\n");
2686 /* Propagation may expose new trivial copy/constant propagation
2688 if (gimple_assign_single_p (use_stmt)
2689 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
2690 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
2691 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
2693 tree result = get_lhs_or_phi_result (use_stmt);
2694 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
2697 /* Propagation into these nodes may make certain edges in
2698 the CFG unexecutable. We want to identify them as PHI nodes
2699 at the destination of those unexecutable edges may become
2701 else if (gimple_code (use_stmt) == GIMPLE_COND
2702 || gimple_code (use_stmt) == GIMPLE_SWITCH
2703 || gimple_code (use_stmt) == GIMPLE_GOTO)
2707 if (gimple_code (use_stmt) == GIMPLE_COND)
2708 val = fold_binary_loc (gimple_location (use_stmt),
2709 gimple_cond_code (use_stmt),
2711 gimple_cond_lhs (use_stmt),
2712 gimple_cond_rhs (use_stmt));
2713 else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
2714 val = gimple_switch_index (use_stmt);
2716 val = gimple_goto_dest (use_stmt);
2718 if (val && is_gimple_min_invariant (val))
2720 basic_block bb = gimple_bb (use_stmt);
2721 edge te = find_taken_edge (bb, val);
2724 gimple_stmt_iterator gsi, psi;
2726 /* Remove all outgoing edges except TE. */
2727 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
2731 /* Mark all the PHI nodes at the destination of
2732 the unexecutable edge as interesting. */
2733 for (psi = gsi_start_phis (e->dest);
2737 gimple phi = gsi_stmt (psi);
2739 tree result = gimple_phi_result (phi);
2740 int version = SSA_NAME_VERSION (result);
2742 bitmap_set_bit (interesting_names, version);
2745 te->probability += e->probability;
2747 te->count += e->count;
2755 gsi = gsi_last_bb (gimple_bb (use_stmt));
2756 gsi_remove (&gsi, true);
2758 /* And fixup the flags on the single remaining edge. */
2759 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
2760 te->flags &= ~EDGE_ABNORMAL;
2761 te->flags |= EDGE_FALLTHRU;
2762 if (te->probability > REG_BR_PROB_BASE)
2763 te->probability = REG_BR_PROB_BASE;
2768 /* Ensure there is nothing else to do. */
2769 gcc_assert (!all || has_zero_uses (lhs));
2771 /* If we were able to propagate away all uses of LHS, then
2772 we can remove STMT. */
2774 remove_stmt_or_phi (stmt);
2778 /* STMT is either a PHI node (potentially a degenerate PHI node) or
2779 a statement that is a trivial copy or constant initialization.
2781 Attempt to eliminate T by propagating its RHS into all uses of
2782 its LHS. This may in turn set new bits in INTERESTING_NAMES
2783 for nodes we want to revisit later.
2785 All exit paths should clear INTERESTING_NAMES for the result
2789 eliminate_const_or_copy (gimple stmt, bitmap interesting_names)
2791 tree lhs = get_lhs_or_phi_result (stmt);
2793 int version = SSA_NAME_VERSION (lhs);
2795 /* If the LHS of this statement or PHI has no uses, then we can
2796 just eliminate it. This can occur if, for example, the PHI
2797 was created by block duplication due to threading and its only
2798 use was in the conditional at the end of the block which was
2800 if (has_zero_uses (lhs))
2802 bitmap_clear_bit (interesting_names, version);
2803 remove_stmt_or_phi (stmt);
2807 /* Get the RHS of the assignment or PHI node if the PHI is a
2809 rhs = get_rhs_or_phi_arg (stmt);
2812 bitmap_clear_bit (interesting_names, version);
2816 propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
2818 /* Note that STMT may well have been deleted by now, so do
2819 not access it, instead use the saved version # to clear
2820 T's entry in the worklist. */
2821 bitmap_clear_bit (interesting_names, version);
2824 /* The first phase in degenerate PHI elimination.
2826 Eliminate the degenerate PHIs in BB, then recurse on the
2827 dominator children of BB. */
2830 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names)
2832 gimple_stmt_iterator gsi;
2835 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2837 gimple phi = gsi_stmt (gsi);
2839 eliminate_const_or_copy (phi, interesting_names);
2842 /* Recurse into the dominator children of BB. */
2843 for (son = first_dom_son (CDI_DOMINATORS, bb);
2845 son = next_dom_son (CDI_DOMINATORS, son))
2846 eliminate_degenerate_phis_1 (son, interesting_names);
2850 /* A very simple pass to eliminate degenerate PHI nodes from the
2851 IL. This is meant to be fast enough to be able to be run several
2852 times in the optimization pipeline.
2854 Certain optimizations, particularly those which duplicate blocks
2855 or remove edges from the CFG can create or expose PHIs which are
2856 trivial copies or constant initializations.
2858 While we could pick up these optimizations in DOM or with the
2859 combination of copy-prop and CCP, those solutions are far too
2860 heavy-weight for our needs.
2862 This implementation has two phases so that we can efficiently
2863 eliminate the first order degenerate PHIs and second order
2866 The first phase performs a dominator walk to identify and eliminate
2867 the vast majority of the degenerate PHIs. When a degenerate PHI
2868 is identified and eliminated any affected statements or PHIs
2869 are put on a worklist.
2871 The second phase eliminates degenerate PHIs and trivial copies
2872 or constant initializations using the worklist. This is how we
2873 pick up the secondary optimization opportunities with minimal
2877 eliminate_degenerate_phis (void)
2879 bitmap interesting_names;
2880 bitmap interesting_names1;
2882 /* Bitmap of blocks which need EH information updated. We can not
2883 update it on-the-fly as doing so invalidates the dominator tree. */
2884 need_eh_cleanup = BITMAP_ALLOC (NULL);
2886 /* INTERESTING_NAMES is effectively our worklist, indexed by
2889 A set bit indicates that the statement or PHI node which
2890 defines the SSA_NAME should be (re)examined to determine if
2891 it has become a degenerate PHI or trivial const/copy propagation
2894 Experiments have show we generally get better compilation
2895 time behavior with bitmaps rather than sbitmaps. */
2896 interesting_names = BITMAP_ALLOC (NULL);
2897 interesting_names1 = BITMAP_ALLOC (NULL);
2899 calculate_dominance_info (CDI_DOMINATORS);
2900 cfg_altered = false;
2902 /* First phase. Eliminate degenerate PHIs via a dominator
2905 Experiments have indicated that we generally get better
2906 compile-time behavior by visiting blocks in the first
2907 phase in dominator order. Presumably this is because walking
2908 in dominator order leaves fewer PHIs for later examination
2909 by the worklist phase. */
2910 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names);
2912 /* Second phase. Eliminate second order degenerate PHIs as well
2913 as trivial copies or constant initializations identified by
2914 the first phase or this phase. Basically we keep iterating
2915 until our set of INTERESTING_NAMEs is empty. */
2916 while (!bitmap_empty_p (interesting_names))
2921 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2922 changed during the loop. Copy it to another bitmap and
2924 bitmap_copy (interesting_names1, interesting_names);
2926 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
2928 tree name = ssa_name (i);
2930 /* Ignore SSA_NAMEs that have been released because
2931 their defining statement was deleted (unreachable). */
2933 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
2939 free_dominance_info (CDI_DOMINATORS);
2941 /* Propagation of const and copies may make some EH edges dead. Purge
2942 such edges from the CFG as needed. */
2943 if (!bitmap_empty_p (need_eh_cleanup))
2945 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
2946 BITMAP_FREE (need_eh_cleanup);
2949 BITMAP_FREE (interesting_names);
2950 BITMAP_FREE (interesting_names1);
2954 struct gimple_opt_pass pass_phi_only_cprop =
2958 "phicprop", /* name */
2959 gate_dominator, /* gate */
2960 eliminate_degenerate_phis, /* execute */
2963 0, /* static_pass_number */
2964 TV_TREE_PHI_CPROP, /* tv_id */
2965 PROP_cfg | PROP_ssa, /* properties_required */
2966 0, /* properties_provided */
2967 0, /* properties_destroyed */
2968 0, /* todo_flags_start */
2973 | TODO_update_ssa /* todo_flags_finish */