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"
32 #include "gimple-pretty-print.h"
33 #include "tree-flow.h"
35 #include "tree-pass.h"
36 #include "tree-ssa-propagate.h"
37 #include "langhooks.h"
40 /* This file implements optimizations on the dominator tree. */
42 /* Representation of a "naked" right-hand-side expression, to be used
43 in recording available expressions in the expression hash table. */
60 struct { tree rhs
; } single
;
61 struct { enum tree_code op
; tree opnd
; } unary
;
62 struct { enum tree_code op
; tree opnd0
, opnd1
; } binary
;
63 struct { enum tree_code op
; tree opnd0
, opnd1
, opnd2
; } ternary
;
64 struct { gimple fn_from
; bool pure
; size_t nargs
; tree
*args
; } call
;
65 struct { size_t nargs
; tree
*args
; } phi
;
69 /* Structure for recording known values of a conditional expression
70 at the exits from its block. */
72 typedef struct cond_equivalence_s
74 struct hashable_expr cond
;
78 DEF_VEC_O(cond_equivalence
);
79 DEF_VEC_ALLOC_O(cond_equivalence
,heap
);
81 /* Structure for recording edge equivalences as well as any pending
82 edge redirections during the dominator optimizer.
84 Computing and storing the edge equivalences instead of creating
85 them on-demand can save significant amounts of time, particularly
86 for pathological cases involving switch statements.
88 These structures live for a single iteration of the dominator
89 optimizer in the edge's AUX field. At the end of an iteration we
90 free each of these structures and update the AUX field to point
91 to any requested redirection target (the code for updating the
92 CFG and SSA graph for edge redirection expects redirection edge
93 targets to be in the AUX field for each edge. */
97 /* If this edge creates a simple equivalence, the LHS and RHS of
98 the equivalence will be stored here. */
102 /* Traversing an edge may also indicate one or more particular conditions
103 are true or false. */
104 VEC(cond_equivalence
, heap
) *cond_equivalences
;
107 /* Hash table with expressions made available during the renaming process.
108 When an assignment of the form X_i = EXPR is found, the statement is
109 stored in this table. If the same expression EXPR is later found on the
110 RHS of another statement, it is replaced with X_i (thus performing
111 global redundancy elimination). Similarly as we pass through conditionals
112 we record the conditional itself as having either a true or false value
114 static htab_t avail_exprs
;
116 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
117 expressions it enters into the hash table along with a marker entry
118 (null). When we finish processing the block, we pop off entries and
119 remove the expressions from the global hash table until we hit the
121 typedef struct expr_hash_elt
* expr_hash_elt_t
;
122 DEF_VEC_P(expr_hash_elt_t
);
123 DEF_VEC_ALLOC_P(expr_hash_elt_t
,heap
);
125 static VEC(expr_hash_elt_t
,heap
) *avail_exprs_stack
;
127 /* Structure for entries in the expression hash table. */
131 /* The value (lhs) of this expression. */
134 /* The expression (rhs) we want to record. */
135 struct hashable_expr expr
;
137 /* The stmt pointer if this element corresponds to a statement. */
140 /* The hash value for RHS. */
143 /* A unique stamp, typically the address of the hash
144 element itself, used in removing entries from the table. */
145 struct expr_hash_elt
*stamp
;
148 /* Stack of dest,src pairs that need to be restored during finalization.
150 A NULL entry is used to mark the end of pairs which need to be
151 restored during finalization of this block. */
152 static VEC(tree
,heap
) *const_and_copies_stack
;
154 /* Track whether or not we have changed the control flow graph. */
155 static bool cfg_altered
;
157 /* Bitmap of blocks that have had EH statements cleaned. We should
158 remove their dead edges eventually. */
159 static bitmap need_eh_cleanup
;
161 /* Statistics for dominator optimizations. */
165 long num_exprs_considered
;
171 static struct opt_stats_d opt_stats
;
173 /* Local functions. */
174 static void optimize_stmt (basic_block
, gimple_stmt_iterator
);
175 static tree
lookup_avail_expr (gimple
, bool);
176 static hashval_t
avail_expr_hash (const void *);
177 static hashval_t
real_avail_expr_hash (const void *);
178 static int avail_expr_eq (const void *, const void *);
179 static void htab_statistics (FILE *, htab_t
);
180 static void record_cond (cond_equivalence
*);
181 static void record_const_or_copy (tree
, tree
);
182 static void record_equality (tree
, tree
);
183 static void record_equivalences_from_phis (basic_block
);
184 static void record_equivalences_from_incoming_edge (basic_block
);
185 static void eliminate_redundant_computations (gimple_stmt_iterator
*);
186 static void record_equivalences_from_stmt (gimple
, int);
187 static void dom_thread_across_edge (struct dom_walk_data
*, edge
);
188 static void dom_opt_leave_block (struct dom_walk_data
*, basic_block
);
189 static void dom_opt_enter_block (struct dom_walk_data
*, basic_block
);
190 static void remove_local_expressions_from_table (void);
191 static void restore_vars_to_original_value (void);
192 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
195 /* Given a statement STMT, initialize the hash table element pointed to
199 initialize_hash_element (gimple stmt
, tree lhs
,
200 struct expr_hash_elt
*element
)
202 enum gimple_code code
= gimple_code (stmt
);
203 struct hashable_expr
*expr
= &element
->expr
;
205 if (code
== GIMPLE_ASSIGN
)
207 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
209 switch (get_gimple_rhs_class (subcode
))
211 case GIMPLE_SINGLE_RHS
:
212 expr
->kind
= EXPR_SINGLE
;
213 expr
->type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
214 expr
->ops
.single
.rhs
= gimple_assign_rhs1 (stmt
);
216 case GIMPLE_UNARY_RHS
:
217 expr
->kind
= EXPR_UNARY
;
218 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
219 expr
->ops
.unary
.op
= subcode
;
220 expr
->ops
.unary
.opnd
= gimple_assign_rhs1 (stmt
);
222 case GIMPLE_BINARY_RHS
:
223 expr
->kind
= EXPR_BINARY
;
224 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
225 expr
->ops
.binary
.op
= subcode
;
226 expr
->ops
.binary
.opnd0
= gimple_assign_rhs1 (stmt
);
227 expr
->ops
.binary
.opnd1
= gimple_assign_rhs2 (stmt
);
229 case GIMPLE_TERNARY_RHS
:
230 expr
->kind
= EXPR_TERNARY
;
231 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
232 expr
->ops
.ternary
.op
= subcode
;
233 expr
->ops
.ternary
.opnd0
= gimple_assign_rhs1 (stmt
);
234 expr
->ops
.ternary
.opnd1
= gimple_assign_rhs2 (stmt
);
235 expr
->ops
.ternary
.opnd2
= gimple_assign_rhs3 (stmt
);
241 else if (code
== GIMPLE_COND
)
243 expr
->type
= boolean_type_node
;
244 expr
->kind
= EXPR_BINARY
;
245 expr
->ops
.binary
.op
= gimple_cond_code (stmt
);
246 expr
->ops
.binary
.opnd0
= gimple_cond_lhs (stmt
);
247 expr
->ops
.binary
.opnd1
= gimple_cond_rhs (stmt
);
249 else if (code
== GIMPLE_CALL
)
251 size_t nargs
= gimple_call_num_args (stmt
);
254 gcc_assert (gimple_call_lhs (stmt
));
256 expr
->type
= TREE_TYPE (gimple_call_lhs (stmt
));
257 expr
->kind
= EXPR_CALL
;
258 expr
->ops
.call
.fn_from
= stmt
;
260 if (gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
))
261 expr
->ops
.call
.pure
= true;
263 expr
->ops
.call
.pure
= false;
265 expr
->ops
.call
.nargs
= nargs
;
266 expr
->ops
.call
.args
= XCNEWVEC (tree
, nargs
);
267 for (i
= 0; i
< nargs
; i
++)
268 expr
->ops
.call
.args
[i
] = gimple_call_arg (stmt
, i
);
270 else if (code
== GIMPLE_SWITCH
)
272 expr
->type
= TREE_TYPE (gimple_switch_index (stmt
));
273 expr
->kind
= EXPR_SINGLE
;
274 expr
->ops
.single
.rhs
= gimple_switch_index (stmt
);
276 else if (code
== GIMPLE_GOTO
)
278 expr
->type
= TREE_TYPE (gimple_goto_dest (stmt
));
279 expr
->kind
= EXPR_SINGLE
;
280 expr
->ops
.single
.rhs
= gimple_goto_dest (stmt
);
282 else if (code
== GIMPLE_PHI
)
284 size_t nargs
= gimple_phi_num_args (stmt
);
287 expr
->type
= TREE_TYPE (gimple_phi_result (stmt
));
288 expr
->kind
= EXPR_PHI
;
289 expr
->ops
.phi
.nargs
= nargs
;
290 expr
->ops
.phi
.args
= XCNEWVEC (tree
, nargs
);
292 for (i
= 0; i
< nargs
; i
++)
293 expr
->ops
.phi
.args
[i
] = gimple_phi_arg_def (stmt
, i
);
299 element
->stmt
= stmt
;
300 element
->hash
= avail_expr_hash (element
);
301 element
->stamp
= element
;
304 /* Given a conditional expression COND as a tree, initialize
305 a hashable_expr expression EXPR. The conditional must be a
306 comparison or logical negation. A constant or a variable is
310 initialize_expr_from_cond (tree cond
, struct hashable_expr
*expr
)
312 expr
->type
= boolean_type_node
;
314 if (COMPARISON_CLASS_P (cond
))
316 expr
->kind
= EXPR_BINARY
;
317 expr
->ops
.binary
.op
= TREE_CODE (cond
);
318 expr
->ops
.binary
.opnd0
= TREE_OPERAND (cond
, 0);
319 expr
->ops
.binary
.opnd1
= TREE_OPERAND (cond
, 1);
321 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
323 expr
->kind
= EXPR_UNARY
;
324 expr
->ops
.unary
.op
= TRUTH_NOT_EXPR
;
325 expr
->ops
.unary
.opnd
= TREE_OPERAND (cond
, 0);
331 /* Given a hashable_expr expression EXPR and an LHS,
332 initialize the hash table element pointed to by ELEMENT. */
335 initialize_hash_element_from_expr (struct hashable_expr
*expr
,
337 struct expr_hash_elt
*element
)
339 element
->expr
= *expr
;
341 element
->stmt
= NULL
;
342 element
->hash
= avail_expr_hash (element
);
343 element
->stamp
= element
;
346 /* Compare two hashable_expr structures for equivalence.
347 They are considered equivalent when the the expressions
348 they denote must necessarily be equal. The logic is intended
349 to follow that of operand_equal_p in fold-const.c */
352 hashable_expr_equal_p (const struct hashable_expr
*expr0
,
353 const struct hashable_expr
*expr1
)
355 tree type0
= expr0
->type
;
356 tree type1
= expr1
->type
;
358 /* If either type is NULL, there is nothing to check. */
359 if ((type0
== NULL_TREE
) ^ (type1
== NULL_TREE
))
362 /* If both types don't have the same signedness, precision, and mode,
363 then we can't consider them equal. */
365 && (TREE_CODE (type0
) == ERROR_MARK
366 || TREE_CODE (type1
) == ERROR_MARK
367 || TYPE_UNSIGNED (type0
) != TYPE_UNSIGNED (type1
)
368 || TYPE_PRECISION (type0
) != TYPE_PRECISION (type1
)
369 || TYPE_MODE (type0
) != TYPE_MODE (type1
)))
372 if (expr0
->kind
!= expr1
->kind
)
378 return operand_equal_p (expr0
->ops
.single
.rhs
,
379 expr1
->ops
.single
.rhs
, 0);
382 if (expr0
->ops
.unary
.op
!= expr1
->ops
.unary
.op
)
385 if ((CONVERT_EXPR_CODE_P (expr0
->ops
.unary
.op
)
386 || expr0
->ops
.unary
.op
== NON_LVALUE_EXPR
)
387 && TYPE_UNSIGNED (expr0
->type
) != TYPE_UNSIGNED (expr1
->type
))
390 return operand_equal_p (expr0
->ops
.unary
.opnd
,
391 expr1
->ops
.unary
.opnd
, 0);
394 if (expr0
->ops
.binary
.op
!= expr1
->ops
.binary
.op
)
397 if (operand_equal_p (expr0
->ops
.binary
.opnd0
,
398 expr1
->ops
.binary
.opnd0
, 0)
399 && operand_equal_p (expr0
->ops
.binary
.opnd1
,
400 expr1
->ops
.binary
.opnd1
, 0))
403 /* For commutative ops, allow the other order. */
404 return (commutative_tree_code (expr0
->ops
.binary
.op
)
405 && operand_equal_p (expr0
->ops
.binary
.opnd0
,
406 expr1
->ops
.binary
.opnd1
, 0)
407 && operand_equal_p (expr0
->ops
.binary
.opnd1
,
408 expr1
->ops
.binary
.opnd0
, 0));
411 if (expr0
->ops
.ternary
.op
!= expr1
->ops
.ternary
.op
412 || !operand_equal_p (expr0
->ops
.ternary
.opnd2
,
413 expr1
->ops
.ternary
.opnd2
, 0))
416 if (operand_equal_p (expr0
->ops
.ternary
.opnd0
,
417 expr1
->ops
.ternary
.opnd0
, 0)
418 && operand_equal_p (expr0
->ops
.ternary
.opnd1
,
419 expr1
->ops
.ternary
.opnd1
, 0))
422 /* For commutative ops, allow the other order. */
423 return (commutative_ternary_tree_code (expr0
->ops
.ternary
.op
)
424 && operand_equal_p (expr0
->ops
.ternary
.opnd0
,
425 expr1
->ops
.ternary
.opnd1
, 0)
426 && operand_equal_p (expr0
->ops
.ternary
.opnd1
,
427 expr1
->ops
.ternary
.opnd0
, 0));
433 /* If the calls are to different functions, then they
434 clearly cannot be equal. */
435 if (!gimple_call_same_target_p (expr0
->ops
.call
.fn_from
,
436 expr1
->ops
.call
.fn_from
))
439 if (! expr0
->ops
.call
.pure
)
442 if (expr0
->ops
.call
.nargs
!= expr1
->ops
.call
.nargs
)
445 for (i
= 0; i
< expr0
->ops
.call
.nargs
; i
++)
446 if (! operand_equal_p (expr0
->ops
.call
.args
[i
],
447 expr1
->ops
.call
.args
[i
], 0))
457 if (expr0
->ops
.phi
.nargs
!= expr1
->ops
.phi
.nargs
)
460 for (i
= 0; i
< expr0
->ops
.phi
.nargs
; i
++)
461 if (! operand_equal_p (expr0
->ops
.phi
.args
[i
],
462 expr1
->ops
.phi
.args
[i
], 0))
473 /* Compute a hash value for a hashable_expr value EXPR and a
474 previously accumulated hash value VAL. If two hashable_expr
475 values compare equal with hashable_expr_equal_p, they must
476 hash to the same value, given an identical value of VAL.
477 The logic is intended to follow iterative_hash_expr in tree.c. */
480 iterative_hash_hashable_expr (const struct hashable_expr
*expr
, hashval_t val
)
485 val
= iterative_hash_expr (expr
->ops
.single
.rhs
, val
);
489 val
= iterative_hash_object (expr
->ops
.unary
.op
, val
);
491 /* Make sure to include signedness in the hash computation.
492 Don't hash the type, that can lead to having nodes which
493 compare equal according to operand_equal_p, but which
494 have different hash codes. */
495 if (CONVERT_EXPR_CODE_P (expr
->ops
.unary
.op
)
496 || expr
->ops
.unary
.op
== NON_LVALUE_EXPR
)
497 val
+= TYPE_UNSIGNED (expr
->type
);
499 val
= iterative_hash_expr (expr
->ops
.unary
.opnd
, val
);
503 val
= iterative_hash_object (expr
->ops
.binary
.op
, val
);
504 if (commutative_tree_code (expr
->ops
.binary
.op
))
505 val
= iterative_hash_exprs_commutative (expr
->ops
.binary
.opnd0
,
506 expr
->ops
.binary
.opnd1
, val
);
509 val
= iterative_hash_expr (expr
->ops
.binary
.opnd0
, val
);
510 val
= iterative_hash_expr (expr
->ops
.binary
.opnd1
, val
);
515 val
= iterative_hash_object (expr
->ops
.ternary
.op
, val
);
516 if (commutative_ternary_tree_code (expr
->ops
.ternary
.op
))
517 val
= iterative_hash_exprs_commutative (expr
->ops
.ternary
.opnd0
,
518 expr
->ops
.ternary
.opnd1
, val
);
521 val
= iterative_hash_expr (expr
->ops
.ternary
.opnd0
, val
);
522 val
= iterative_hash_expr (expr
->ops
.ternary
.opnd1
, val
);
524 val
= iterative_hash_expr (expr
->ops
.ternary
.opnd2
, val
);
530 enum tree_code code
= CALL_EXPR
;
533 val
= iterative_hash_object (code
, val
);
534 fn_from
= expr
->ops
.call
.fn_from
;
535 if (gimple_call_internal_p (fn_from
))
536 val
= iterative_hash_hashval_t
537 ((hashval_t
) gimple_call_internal_fn (fn_from
), val
);
539 val
= iterative_hash_expr (gimple_call_fn (fn_from
), val
);
540 for (i
= 0; i
< expr
->ops
.call
.nargs
; i
++)
541 val
= iterative_hash_expr (expr
->ops
.call
.args
[i
], val
);
549 for (i
= 0; i
< expr
->ops
.phi
.nargs
; i
++)
550 val
= iterative_hash_expr (expr
->ops
.phi
.args
[i
], val
);
561 /* Print a diagnostic dump of an expression hash table entry. */
564 print_expr_hash_elt (FILE * stream
, const struct expr_hash_elt
*element
)
567 fprintf (stream
, "STMT ");
569 fprintf (stream
, "COND ");
573 print_generic_expr (stream
, element
->lhs
, 0);
574 fprintf (stream
, " = ");
577 switch (element
->expr
.kind
)
580 print_generic_expr (stream
, element
->expr
.ops
.single
.rhs
, 0);
584 fprintf (stream
, "%s ", tree_code_name
[element
->expr
.ops
.unary
.op
]);
585 print_generic_expr (stream
, element
->expr
.ops
.unary
.opnd
, 0);
589 print_generic_expr (stream
, element
->expr
.ops
.binary
.opnd0
, 0);
590 fprintf (stream
, " %s ", tree_code_name
[element
->expr
.ops
.binary
.op
]);
591 print_generic_expr (stream
, element
->expr
.ops
.binary
.opnd1
, 0);
595 fprintf (stream
, " %s <", tree_code_name
[element
->expr
.ops
.ternary
.op
]);
596 print_generic_expr (stream
, element
->expr
.ops
.ternary
.opnd0
, 0);
597 fputs (", ", stream
);
598 print_generic_expr (stream
, element
->expr
.ops
.ternary
.opnd1
, 0);
599 fputs (", ", stream
);
600 print_generic_expr (stream
, element
->expr
.ops
.ternary
.opnd2
, 0);
607 size_t nargs
= element
->expr
.ops
.call
.nargs
;
610 fn_from
= element
->expr
.ops
.call
.fn_from
;
611 if (gimple_call_internal_p (fn_from
))
612 fputs (internal_fn_name (gimple_call_internal_fn (fn_from
)),
615 print_generic_expr (stream
, gimple_call_fn (fn_from
), 0);
616 fprintf (stream
, " (");
617 for (i
= 0; i
< nargs
; i
++)
619 print_generic_expr (stream
, element
->expr
.ops
.call
.args
[i
], 0);
621 fprintf (stream
, ", ");
623 fprintf (stream
, ")");
630 size_t nargs
= element
->expr
.ops
.phi
.nargs
;
632 fprintf (stream
, "PHI <");
633 for (i
= 0; i
< nargs
; i
++)
635 print_generic_expr (stream
, element
->expr
.ops
.phi
.args
[i
], 0);
637 fprintf (stream
, ", ");
639 fprintf (stream
, ">");
643 fprintf (stream
, "\n");
647 fprintf (stream
, " ");
648 print_gimple_stmt (stream
, element
->stmt
, 0, 0);
652 /* Delete variable sized pieces of the expr_hash_elt ELEMENT. */
655 free_expr_hash_elt_contents (struct expr_hash_elt
*element
)
657 if (element
->expr
.kind
== EXPR_CALL
)
658 free (element
->expr
.ops
.call
.args
);
659 else if (element
->expr
.kind
== EXPR_PHI
)
660 free (element
->expr
.ops
.phi
.args
);
663 /* Delete an expr_hash_elt and reclaim its storage. */
666 free_expr_hash_elt (void *elt
)
668 struct expr_hash_elt
*element
= ((struct expr_hash_elt
*)elt
);
669 free_expr_hash_elt_contents (element
);
673 /* Allocate an EDGE_INFO for edge E and attach it to E.
674 Return the new EDGE_INFO structure. */
676 static struct edge_info
*
677 allocate_edge_info (edge e
)
679 struct edge_info
*edge_info
;
681 edge_info
= XCNEW (struct edge_info
);
687 /* Free all EDGE_INFO structures associated with edges in the CFG.
688 If a particular edge can be threaded, copy the redirection
689 target from the EDGE_INFO structure into the edge's AUX field
690 as required by code to update the CFG and SSA graph for
694 free_all_edge_infos (void)
702 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
704 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
708 if (edge_info
->cond_equivalences
)
709 VEC_free (cond_equivalence
, heap
, edge_info
->cond_equivalences
);
717 /* Jump threading, redundancy elimination and const/copy propagation.
719 This pass may expose new symbols that need to be renamed into SSA. For
720 every new symbol exposed, its corresponding bit will be set in
724 tree_ssa_dominator_optimize (void)
726 struct dom_walk_data walk_data
;
728 memset (&opt_stats
, 0, sizeof (opt_stats
));
730 /* Create our hash tables. */
731 avail_exprs
= htab_create (1024, real_avail_expr_hash
, avail_expr_eq
, free_expr_hash_elt
);
732 avail_exprs_stack
= VEC_alloc (expr_hash_elt_t
, heap
, 20);
733 const_and_copies_stack
= VEC_alloc (tree
, heap
, 20);
734 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
736 /* Setup callbacks for the generic dominator tree walker. */
737 walk_data
.dom_direction
= CDI_DOMINATORS
;
738 walk_data
.initialize_block_local_data
= NULL
;
739 walk_data
.before_dom_children
= dom_opt_enter_block
;
740 walk_data
.after_dom_children
= dom_opt_leave_block
;
741 /* Right now we only attach a dummy COND_EXPR to the global data pointer.
742 When we attach more stuff we'll need to fill this out with a real
744 walk_data
.global_data
= NULL
;
745 walk_data
.block_local_data_size
= 0;
747 /* Now initialize the dominator walker. */
748 init_walk_dominator_tree (&walk_data
);
750 calculate_dominance_info (CDI_DOMINATORS
);
753 /* We need to know loop structures in order to avoid destroying them
754 in jump threading. Note that we still can e.g. thread through loop
755 headers to an exit edge, or through loop header to the loop body, assuming
756 that we update the loop info. */
757 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES
);
759 /* Initialize the value-handle array. */
760 threadedge_initialize_values ();
762 /* We need accurate information regarding back edges in the CFG
763 for jump threading; this may include back edges that are not part of
765 mark_dfs_back_edges ();
767 /* Recursively walk the dominator tree optimizing statements. */
768 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
771 gimple_stmt_iterator gsi
;
775 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
776 update_stmt_if_modified (gsi_stmt (gsi
));
780 /* If we exposed any new variables, go ahead and put them into
781 SSA form now, before we handle jump threading. This simplifies
782 interactions between rewriting of _DECL nodes into SSA form
783 and rewriting SSA_NAME nodes into SSA form after block
784 duplication and CFG manipulation. */
785 update_ssa (TODO_update_ssa
);
787 free_all_edge_infos ();
789 /* Thread jumps, creating duplicate blocks as needed. */
790 cfg_altered
|= thread_through_all_blocks (first_pass_instance
);
793 free_dominance_info (CDI_DOMINATORS
);
795 /* Removal of statements may make some EH edges dead. Purge
796 such edges from the CFG as needed. */
797 if (!bitmap_empty_p (need_eh_cleanup
))
802 /* Jump threading may have created forwarder blocks from blocks
803 needing EH cleanup; the new successor of these blocks, which
804 has inherited from the original block, needs the cleanup. */
805 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup
, 0, i
, bi
)
807 basic_block bb
= BASIC_BLOCK (i
);
809 && single_succ_p (bb
)
810 && (single_succ_edge (bb
)->flags
& EDGE_EH
) == 0)
812 bitmap_clear_bit (need_eh_cleanup
, i
);
813 bitmap_set_bit (need_eh_cleanup
, single_succ (bb
)->index
);
817 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
818 bitmap_clear (need_eh_cleanup
);
821 statistics_counter_event (cfun
, "Redundant expressions eliminated",
823 statistics_counter_event (cfun
, "Constants propagated",
824 opt_stats
.num_const_prop
);
825 statistics_counter_event (cfun
, "Copies propagated",
826 opt_stats
.num_copy_prop
);
828 /* Debugging dumps. */
829 if (dump_file
&& (dump_flags
& TDF_STATS
))
830 dump_dominator_optimization_stats (dump_file
);
832 loop_optimizer_finalize ();
834 /* Delete our main hashtable. */
835 htab_delete (avail_exprs
);
837 /* And finalize the dominator walker. */
838 fini_walk_dominator_tree (&walk_data
);
840 /* Free asserted bitmaps and stacks. */
841 BITMAP_FREE (need_eh_cleanup
);
843 VEC_free (expr_hash_elt_t
, heap
, avail_exprs_stack
);
844 VEC_free (tree
, heap
, const_and_copies_stack
);
846 /* Free the value-handle array. */
847 threadedge_finalize_values ();
848 ssa_name_values
= NULL
;
854 gate_dominator (void)
856 return flag_tree_dom
!= 0;
859 struct gimple_opt_pass pass_dominator
=
864 gate_dominator
, /* gate */
865 tree_ssa_dominator_optimize
, /* execute */
868 0, /* static_pass_number */
869 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
870 PROP_cfg
| PROP_ssa
, /* properties_required */
871 0, /* properties_provided */
872 0, /* properties_destroyed */
873 0, /* todo_flags_start */
877 | TODO_verify_flow
/* todo_flags_finish */
882 /* Given a conditional statement CONDSTMT, convert the
883 condition to a canonical form. */
886 canonicalize_comparison (gimple condstmt
)
892 gcc_assert (gimple_code (condstmt
) == GIMPLE_COND
);
894 op0
= gimple_cond_lhs (condstmt
);
895 op1
= gimple_cond_rhs (condstmt
);
897 code
= gimple_cond_code (condstmt
);
899 /* If it would be profitable to swap the operands, then do so to
900 canonicalize the statement, enabling better optimization.
902 By placing canonicalization of such expressions here we
903 transparently keep statements in canonical form, even
904 when the statement is modified. */
905 if (tree_swap_operands_p (op0
, op1
, false))
907 /* For relationals we need to swap the operands
908 and change the code. */
914 code
= swap_tree_comparison (code
);
916 gimple_cond_set_code (condstmt
, code
);
917 gimple_cond_set_lhs (condstmt
, op1
);
918 gimple_cond_set_rhs (condstmt
, op0
);
920 update_stmt (condstmt
);
925 /* Initialize local stacks for this optimizer and record equivalences
926 upon entry to BB. Equivalences can come from the edge traversed to
927 reach BB or they may come from PHI nodes at the start of BB. */
929 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
930 LIMIT entries left in LOCALs. */
933 remove_local_expressions_from_table (void)
935 /* Remove all the expressions made available in this block. */
936 while (VEC_length (expr_hash_elt_t
, avail_exprs_stack
) > 0)
938 expr_hash_elt_t victim
= VEC_pop (expr_hash_elt_t
, avail_exprs_stack
);
944 /* This must precede the actual removal from the hash table,
945 as ELEMENT and the table entry may share a call argument
946 vector which will be freed during removal. */
947 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
949 fprintf (dump_file
, "<<<< ");
950 print_expr_hash_elt (dump_file
, victim
);
953 slot
= htab_find_slot_with_hash (avail_exprs
,
954 victim
, victim
->hash
, NO_INSERT
);
955 gcc_assert (slot
&& *slot
== (void *) victim
);
956 htab_clear_slot (avail_exprs
, slot
);
960 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
961 CONST_AND_COPIES to its original state, stopping when we hit a
965 restore_vars_to_original_value (void)
967 while (VEC_length (tree
, const_and_copies_stack
) > 0)
969 tree prev_value
, dest
;
971 dest
= VEC_pop (tree
, const_and_copies_stack
);
976 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
978 fprintf (dump_file
, "<<<< COPY ");
979 print_generic_expr (dump_file
, dest
, 0);
980 fprintf (dump_file
, " = ");
981 print_generic_expr (dump_file
, SSA_NAME_VALUE (dest
), 0);
982 fprintf (dump_file
, "\n");
985 prev_value
= VEC_pop (tree
, const_and_copies_stack
);
986 set_ssa_name_value (dest
, prev_value
);
990 /* A trivial wrapper so that we can present the generic jump
991 threading code with a simple API for simplifying statements. */
993 simplify_stmt_for_jump_threading (gimple stmt
,
994 gimple within_stmt ATTRIBUTE_UNUSED
)
996 return lookup_avail_expr (stmt
, false);
999 /* Wrapper for common code to attempt to thread an edge. For example,
1000 it handles lazily building the dummy condition and the bookkeeping
1001 when jump threading is successful. */
1004 dom_thread_across_edge (struct dom_walk_data
*walk_data
, edge e
)
1006 if (! walk_data
->global_data
)
1009 gimple_build_cond (NE_EXPR
,
1010 integer_zero_node
, integer_zero_node
,
1012 walk_data
->global_data
= dummy_cond
;
1015 thread_across_edge ((gimple
) walk_data
->global_data
, e
, false,
1016 &const_and_copies_stack
,
1017 simplify_stmt_for_jump_threading
);
1020 /* PHI nodes can create equivalences too.
1022 Ignoring any alternatives which are the same as the result, if
1023 all the alternatives are equal, then the PHI node creates an
1027 record_equivalences_from_phis (basic_block bb
)
1029 gimple_stmt_iterator gsi
;
1031 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1033 gimple phi
= gsi_stmt (gsi
);
1035 tree lhs
= gimple_phi_result (phi
);
1039 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1041 tree t
= gimple_phi_arg_def (phi
, i
);
1043 /* Ignore alternatives which are the same as our LHS. Since
1044 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1045 can simply compare pointers. */
1049 /* If we have not processed an alternative yet, then set
1050 RHS to this alternative. */
1053 /* If we have processed an alternative (stored in RHS), then
1054 see if it is equal to this one. If it isn't, then stop
1056 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
1060 /* If we had no interesting alternatives, then all the RHS alternatives
1061 must have been the same as LHS. */
1065 /* If we managed to iterate through each PHI alternative without
1066 breaking out of the loop, then we have a PHI which may create
1067 a useful equivalence. We do not need to record unwind data for
1068 this, since this is a true assignment and not an equivalence
1069 inferred from a comparison. All uses of this ssa name are dominated
1070 by this assignment, so unwinding just costs time and space. */
1071 if (i
== gimple_phi_num_args (phi
) && may_propagate_copy (lhs
, rhs
))
1072 set_ssa_name_value (lhs
, rhs
);
1076 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1077 return that edge. Otherwise return NULL. */
1079 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
1085 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1087 /* A loop back edge can be identified by the destination of
1088 the edge dominating the source of the edge. */
1089 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
1092 /* If we have already seen a non-loop edge, then we must have
1093 multiple incoming non-loop edges and thus we return NULL. */
1097 /* This is the first non-loop incoming edge we have found. Record
1105 /* Record any equivalences created by the incoming edge to BB. If BB
1106 has more than one incoming edge, then no equivalence is created. */
1109 record_equivalences_from_incoming_edge (basic_block bb
)
1113 struct edge_info
*edge_info
;
1115 /* If our parent block ended with a control statement, then we may be
1116 able to record some equivalences based on which outgoing edge from
1117 the parent was followed. */
1118 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1120 e
= single_incoming_edge_ignoring_loop_edges (bb
);
1122 /* If we had a single incoming edge from our parent block, then enter
1123 any data associated with the edge into our tables. */
1124 if (e
&& e
->src
== parent
)
1128 edge_info
= (struct edge_info
*) e
->aux
;
1132 tree lhs
= edge_info
->lhs
;
1133 tree rhs
= edge_info
->rhs
;
1134 cond_equivalence
*eq
;
1137 record_equality (lhs
, rhs
);
1139 for (i
= 0; VEC_iterate (cond_equivalence
,
1140 edge_info
->cond_equivalences
, i
, eq
); ++i
)
1146 /* Dump SSA statistics on FILE. */
1149 dump_dominator_optimization_stats (FILE *file
)
1151 fprintf (file
, "Total number of statements: %6ld\n\n",
1152 opt_stats
.num_stmts
);
1153 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1154 opt_stats
.num_exprs_considered
);
1156 fprintf (file
, "\nHash table statistics:\n");
1158 fprintf (file
, " avail_exprs: ");
1159 htab_statistics (file
, avail_exprs
);
1163 /* Dump SSA statistics on stderr. */
1166 debug_dominator_optimization_stats (void)
1168 dump_dominator_optimization_stats (stderr
);
1172 /* Dump statistics for the hash table HTAB. */
1175 htab_statistics (FILE *file
, htab_t htab
)
1177 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1178 (long) htab_size (htab
),
1179 (long) htab_elements (htab
),
1180 htab_collisions (htab
));
1184 /* Enter condition equivalence into the expression hash table.
1185 This indicates that a conditional expression has a known
1189 record_cond (cond_equivalence
*p
)
1191 struct expr_hash_elt
*element
= XCNEW (struct expr_hash_elt
);
1194 initialize_hash_element_from_expr (&p
->cond
, p
->value
, element
);
1196 slot
= htab_find_slot_with_hash (avail_exprs
, (void *)element
,
1197 element
->hash
, INSERT
);
1200 *slot
= (void *) element
;
1202 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1204 fprintf (dump_file
, "1>>> ");
1205 print_expr_hash_elt (dump_file
, element
);
1208 VEC_safe_push (expr_hash_elt_t
, heap
, avail_exprs_stack
, element
);
1211 free_expr_hash_elt (element
);
1214 /* Build a cond_equivalence record indicating that the comparison
1215 CODE holds between operands OP0 and OP1 and push it to **P. */
1218 build_and_record_new_cond (enum tree_code code
,
1220 VEC(cond_equivalence
, heap
) **p
)
1223 struct hashable_expr
*cond
= &c
.cond
;
1225 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
1227 cond
->type
= boolean_type_node
;
1228 cond
->kind
= EXPR_BINARY
;
1229 cond
->ops
.binary
.op
= code
;
1230 cond
->ops
.binary
.opnd0
= op0
;
1231 cond
->ops
.binary
.opnd1
= op1
;
1233 c
.value
= boolean_true_node
;
1234 VEC_safe_push (cond_equivalence
, heap
, *p
, c
);
1237 /* Record that COND is true and INVERTED is false into the edge information
1238 structure. Also record that any conditions dominated by COND are true
1241 For example, if a < b is true, then a <= b must also be true. */
1244 record_conditions (struct edge_info
*edge_info
, tree cond
, tree inverted
)
1249 if (!COMPARISON_CLASS_P (cond
))
1252 op0
= TREE_OPERAND (cond
, 0);
1253 op1
= TREE_OPERAND (cond
, 1);
1255 switch (TREE_CODE (cond
))
1259 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1261 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1262 &edge_info
->cond_equivalences
);
1263 build_and_record_new_cond (LTGT_EXPR
, op0
, op1
,
1264 &edge_info
->cond_equivalences
);
1267 build_and_record_new_cond ((TREE_CODE (cond
) == LT_EXPR
1268 ? LE_EXPR
: GE_EXPR
),
1269 op0
, op1
, &edge_info
->cond_equivalences
);
1270 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1271 &edge_info
->cond_equivalences
);
1276 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1278 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1279 &edge_info
->cond_equivalences
);
1284 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1286 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1287 &edge_info
->cond_equivalences
);
1289 build_and_record_new_cond (LE_EXPR
, op0
, op1
,
1290 &edge_info
->cond_equivalences
);
1291 build_and_record_new_cond (GE_EXPR
, op0
, op1
,
1292 &edge_info
->cond_equivalences
);
1295 case UNORDERED_EXPR
:
1296 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1297 &edge_info
->cond_equivalences
);
1298 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1299 &edge_info
->cond_equivalences
);
1300 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1301 &edge_info
->cond_equivalences
);
1302 build_and_record_new_cond (UNEQ_EXPR
, op0
, op1
,
1303 &edge_info
->cond_equivalences
);
1304 build_and_record_new_cond (UNLT_EXPR
, op0
, op1
,
1305 &edge_info
->cond_equivalences
);
1306 build_and_record_new_cond (UNGT_EXPR
, op0
, op1
,
1307 &edge_info
->cond_equivalences
);
1312 build_and_record_new_cond ((TREE_CODE (cond
) == UNLT_EXPR
1313 ? UNLE_EXPR
: UNGE_EXPR
),
1314 op0
, op1
, &edge_info
->cond_equivalences
);
1315 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1316 &edge_info
->cond_equivalences
);
1320 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1321 &edge_info
->cond_equivalences
);
1322 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1323 &edge_info
->cond_equivalences
);
1327 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1328 &edge_info
->cond_equivalences
);
1329 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1330 &edge_info
->cond_equivalences
);
1337 /* Now store the original true and false conditions into the first
1339 initialize_expr_from_cond (cond
, &c
.cond
);
1340 c
.value
= boolean_true_node
;
1341 VEC_safe_push (cond_equivalence
, heap
, edge_info
->cond_equivalences
, c
);
1343 /* It is possible for INVERTED to be the negation of a comparison,
1344 and not a valid RHS or GIMPLE_COND condition. This happens because
1345 invert_truthvalue may return such an expression when asked to invert
1346 a floating-point comparison. These comparisons are not assumed to
1347 obey the trichotomy law. */
1348 initialize_expr_from_cond (inverted
, &c
.cond
);
1349 c
.value
= boolean_false_node
;
1350 VEC_safe_push (cond_equivalence
, heap
, edge_info
->cond_equivalences
, c
);
1353 /* A helper function for record_const_or_copy and record_equality.
1354 Do the work of recording the value and undo info. */
1357 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
)
1359 set_ssa_name_value (x
, y
);
1361 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1363 fprintf (dump_file
, "0>>> COPY ");
1364 print_generic_expr (dump_file
, x
, 0);
1365 fprintf (dump_file
, " = ");
1366 print_generic_expr (dump_file
, y
, 0);
1367 fprintf (dump_file
, "\n");
1370 VEC_reserve (tree
, heap
, const_and_copies_stack
, 2);
1371 VEC_quick_push (tree
, const_and_copies_stack
, prev_x
);
1372 VEC_quick_push (tree
, const_and_copies_stack
, x
);
1375 /* Return the loop depth of the basic block of the defining statement of X.
1376 This number should not be treated as absolutely correct because the loop
1377 information may not be completely up-to-date when dom runs. However, it
1378 will be relatively correct, and as more passes are taught to keep loop info
1379 up to date, the result will become more and more accurate. */
1382 loop_depth_of_name (tree x
)
1387 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1388 if (TREE_CODE (x
) != SSA_NAME
)
1391 /* Otherwise return the loop depth of the defining statement's bb.
1392 Note that there may not actually be a bb for this statement, if the
1393 ssa_name is live on entry. */
1394 defstmt
= SSA_NAME_DEF_STMT (x
);
1395 defbb
= gimple_bb (defstmt
);
1399 return bb_loop_depth (defbb
);
1402 /* Record that X is equal to Y in const_and_copies. Record undo
1403 information in the block-local vector. */
1406 record_const_or_copy (tree x
, tree y
)
1408 tree prev_x
= SSA_NAME_VALUE (x
);
1410 gcc_assert (TREE_CODE (x
) == SSA_NAME
);
1412 if (TREE_CODE (y
) == SSA_NAME
)
1414 tree tmp
= SSA_NAME_VALUE (y
);
1419 record_const_or_copy_1 (x
, y
, prev_x
);
1422 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1423 This constrains the cases in which we may treat this as assignment. */
1426 record_equality (tree x
, tree y
)
1428 tree prev_x
= NULL
, prev_y
= NULL
;
1430 if (TREE_CODE (x
) == SSA_NAME
)
1431 prev_x
= SSA_NAME_VALUE (x
);
1432 if (TREE_CODE (y
) == SSA_NAME
)
1433 prev_y
= SSA_NAME_VALUE (y
);
1435 /* If one of the previous values is invariant, or invariant in more loops
1436 (by depth), then use that.
1437 Otherwise it doesn't matter which value we choose, just so
1438 long as we canonicalize on one value. */
1439 if (is_gimple_min_invariant (y
))
1441 else if (is_gimple_min_invariant (x
)
1442 || (loop_depth_of_name (x
) <= loop_depth_of_name (y
)))
1443 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1444 else if (prev_x
&& is_gimple_min_invariant (prev_x
))
1445 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1449 /* After the swapping, we must have one SSA_NAME. */
1450 if (TREE_CODE (x
) != SSA_NAME
)
1453 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1454 variable compared against zero. If we're honoring signed zeros,
1455 then we cannot record this value unless we know that the value is
1457 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1458 && (TREE_CODE (y
) != REAL_CST
1459 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1462 record_const_or_copy_1 (x
, y
, prev_x
);
1465 /* Returns true when STMT is a simple iv increment. It detects the
1466 following situation:
1468 i_1 = phi (..., i_2)
1469 i_2 = i_1 +/- ... */
1472 simple_iv_increment_p (gimple stmt
)
1474 enum tree_code code
;
1479 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1482 lhs
= gimple_assign_lhs (stmt
);
1483 if (TREE_CODE (lhs
) != SSA_NAME
)
1486 code
= gimple_assign_rhs_code (stmt
);
1487 if (code
!= PLUS_EXPR
1488 && code
!= MINUS_EXPR
1489 && code
!= POINTER_PLUS_EXPR
)
1492 preinc
= gimple_assign_rhs1 (stmt
);
1493 if (TREE_CODE (preinc
) != SSA_NAME
)
1496 phi
= SSA_NAME_DEF_STMT (preinc
);
1497 if (gimple_code (phi
) != GIMPLE_PHI
)
1500 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1501 if (gimple_phi_arg_def (phi
, i
) == lhs
)
1507 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1508 known value for that SSA_NAME (or NULL if no value is known).
1510 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1511 successors of BB. */
1514 cprop_into_successor_phis (basic_block bb
)
1519 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1522 gimple_stmt_iterator gsi
;
1524 /* If this is an abnormal edge, then we do not want to copy propagate
1525 into the PHI alternative associated with this edge. */
1526 if (e
->flags
& EDGE_ABNORMAL
)
1529 gsi
= gsi_start_phis (e
->dest
);
1530 if (gsi_end_p (gsi
))
1534 for ( ; !gsi_end_p (gsi
); gsi_next (&gsi
))
1537 use_operand_p orig_p
;
1539 gimple phi
= gsi_stmt (gsi
);
1541 /* The alternative may be associated with a constant, so verify
1542 it is an SSA_NAME before doing anything with it. */
1543 orig_p
= gimple_phi_arg_imm_use_ptr (phi
, indx
);
1544 orig_val
= get_use_from_ptr (orig_p
);
1545 if (TREE_CODE (orig_val
) != SSA_NAME
)
1548 /* If we have *ORIG_P in our constant/copy table, then replace
1549 ORIG_P with its value in our constant/copy table. */
1550 new_val
= SSA_NAME_VALUE (orig_val
);
1552 && new_val
!= orig_val
1553 && (TREE_CODE (new_val
) == SSA_NAME
1554 || is_gimple_min_invariant (new_val
))
1555 && may_propagate_copy (orig_val
, new_val
))
1556 propagate_value (orig_p
, new_val
);
1561 /* We have finished optimizing BB, record any information implied by
1562 taking a specific outgoing edge from BB. */
1565 record_edge_info (basic_block bb
)
1567 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1568 struct edge_info
*edge_info
;
1570 if (! gsi_end_p (gsi
))
1572 gimple stmt
= gsi_stmt (gsi
);
1573 location_t loc
= gimple_location (stmt
);
1575 if (gimple_code (stmt
) == GIMPLE_SWITCH
)
1577 tree index
= gimple_switch_index (stmt
);
1579 if (TREE_CODE (index
) == SSA_NAME
)
1582 int n_labels
= gimple_switch_num_labels (stmt
);
1583 tree
*info
= XCNEWVEC (tree
, last_basic_block
);
1587 for (i
= 0; i
< n_labels
; i
++)
1589 tree label
= gimple_switch_label (stmt
, i
);
1590 basic_block target_bb
= label_to_block (CASE_LABEL (label
));
1591 if (CASE_HIGH (label
)
1592 || !CASE_LOW (label
)
1593 || info
[target_bb
->index
])
1594 info
[target_bb
->index
] = error_mark_node
;
1596 info
[target_bb
->index
] = label
;
1599 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1601 basic_block target_bb
= e
->dest
;
1602 tree label
= info
[target_bb
->index
];
1604 if (label
!= NULL
&& label
!= error_mark_node
)
1606 tree x
= fold_convert_loc (loc
, TREE_TYPE (index
),
1608 edge_info
= allocate_edge_info (e
);
1609 edge_info
->lhs
= index
;
1617 /* A COND_EXPR may create equivalences too. */
1618 if (gimple_code (stmt
) == GIMPLE_COND
)
1623 tree op0
= gimple_cond_lhs (stmt
);
1624 tree op1
= gimple_cond_rhs (stmt
);
1625 enum tree_code code
= gimple_cond_code (stmt
);
1627 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1629 /* Special case comparing booleans against a constant as we
1630 know the value of OP0 on both arms of the branch. i.e., we
1631 can record an equivalence for OP0 rather than COND. */
1632 if ((code
== EQ_EXPR
|| code
== NE_EXPR
)
1633 && TREE_CODE (op0
) == SSA_NAME
1634 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
1635 && is_gimple_min_invariant (op1
))
1637 if (code
== EQ_EXPR
)
1639 edge_info
= allocate_edge_info (true_edge
);
1640 edge_info
->lhs
= op0
;
1641 edge_info
->rhs
= (integer_zerop (op1
)
1642 ? boolean_false_node
1643 : boolean_true_node
);
1645 edge_info
= allocate_edge_info (false_edge
);
1646 edge_info
->lhs
= op0
;
1647 edge_info
->rhs
= (integer_zerop (op1
)
1649 : boolean_false_node
);
1653 edge_info
= allocate_edge_info (true_edge
);
1654 edge_info
->lhs
= op0
;
1655 edge_info
->rhs
= (integer_zerop (op1
)
1657 : boolean_false_node
);
1659 edge_info
= allocate_edge_info (false_edge
);
1660 edge_info
->lhs
= op0
;
1661 edge_info
->rhs
= (integer_zerop (op1
)
1662 ? boolean_false_node
1663 : boolean_true_node
);
1666 else if (is_gimple_min_invariant (op0
)
1667 && (TREE_CODE (op1
) == SSA_NAME
1668 || is_gimple_min_invariant (op1
)))
1670 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
1671 tree inverted
= invert_truthvalue_loc (loc
, cond
);
1672 bool can_infer_simple_equiv
1673 = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0
)))
1674 && real_zerop (op0
));
1675 struct edge_info
*edge_info
;
1677 edge_info
= allocate_edge_info (true_edge
);
1678 record_conditions (edge_info
, cond
, inverted
);
1680 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
1682 edge_info
->lhs
= op1
;
1683 edge_info
->rhs
= op0
;
1686 edge_info
= allocate_edge_info (false_edge
);
1687 record_conditions (edge_info
, inverted
, cond
);
1689 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
1691 edge_info
->lhs
= op1
;
1692 edge_info
->rhs
= op0
;
1696 else if (TREE_CODE (op0
) == SSA_NAME
1697 && (TREE_CODE (op1
) == SSA_NAME
1698 || is_gimple_min_invariant (op1
)))
1700 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
1701 tree inverted
= invert_truthvalue_loc (loc
, cond
);
1702 bool can_infer_simple_equiv
1703 = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op1
)))
1704 && (TREE_CODE (op1
) == SSA_NAME
|| real_zerop (op1
)));
1705 struct edge_info
*edge_info
;
1707 edge_info
= allocate_edge_info (true_edge
);
1708 record_conditions (edge_info
, cond
, inverted
);
1710 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
1712 edge_info
->lhs
= op0
;
1713 edge_info
->rhs
= op1
;
1716 edge_info
= allocate_edge_info (false_edge
);
1717 record_conditions (edge_info
, inverted
, cond
);
1719 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
1721 edge_info
->lhs
= op0
;
1722 edge_info
->rhs
= op1
;
1727 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1732 dom_opt_enter_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1735 gimple_stmt_iterator gsi
;
1737 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1738 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1740 /* Push a marker on the stacks of local information so that we know how
1741 far to unwind when we finalize this block. */
1742 VEC_safe_push (expr_hash_elt_t
, heap
, avail_exprs_stack
,
1743 (expr_hash_elt_t
)NULL
);
1744 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
1746 record_equivalences_from_incoming_edge (bb
);
1748 /* PHI nodes can create equivalences too. */
1749 record_equivalences_from_phis (bb
);
1751 /* Create equivalences from redundant PHIs. PHIs are only truly
1752 redundant when they exist in the same block, so push another
1753 marker and unwind right afterwards. */
1754 VEC_safe_push (expr_hash_elt_t
, heap
, avail_exprs_stack
,
1755 (expr_hash_elt_t
)NULL
);
1756 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1757 eliminate_redundant_computations (&gsi
);
1758 remove_local_expressions_from_table ();
1760 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1761 optimize_stmt (bb
, gsi
);
1763 /* Now prepare to process dominated blocks. */
1764 record_edge_info (bb
);
1765 cprop_into_successor_phis (bb
);
1768 /* We have finished processing the dominator children of BB, perform
1769 any finalization actions in preparation for leaving this node in
1770 the dominator tree. */
1773 dom_opt_leave_block (struct dom_walk_data
*walk_data
, basic_block bb
)
1777 /* If we have an outgoing edge to a block with multiple incoming and
1778 outgoing edges, then we may be able to thread the edge, i.e., we
1779 may be able to statically determine which of the outgoing edges
1780 will be traversed when the incoming edge from BB is traversed. */
1781 if (single_succ_p (bb
)
1782 && (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
) == 0
1783 && potentially_threadable_block (single_succ (bb
)))
1785 /* Push a marker on the stack, which thread_across_edge expects
1787 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
1788 dom_thread_across_edge (walk_data
, single_succ_edge (bb
));
1790 else if ((last
= last_stmt (bb
))
1791 && gimple_code (last
) == GIMPLE_COND
1792 && EDGE_COUNT (bb
->succs
) == 2
1793 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
1794 && (EDGE_SUCC (bb
, 1)->flags
& EDGE_ABNORMAL
) == 0)
1796 edge true_edge
, false_edge
;
1798 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1800 /* Only try to thread the edge if it reaches a target block with
1801 more than one predecessor and more than one successor. */
1802 if (potentially_threadable_block (true_edge
->dest
))
1804 struct edge_info
*edge_info
;
1807 /* Push a marker onto the available expression stack so that we
1808 unwind any expressions related to the TRUE arm before processing
1809 the false arm below. */
1810 VEC_safe_push (expr_hash_elt_t
, heap
, avail_exprs_stack
,
1811 (expr_hash_elt_t
)NULL
);
1812 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
1814 edge_info
= (struct edge_info
*) true_edge
->aux
;
1816 /* If we have info associated with this edge, record it into
1817 our equivalence tables. */
1820 cond_equivalence
*eq
;
1821 tree lhs
= edge_info
->lhs
;
1822 tree rhs
= edge_info
->rhs
;
1824 /* If we have a simple NAME = VALUE equivalence, record it. */
1825 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1826 record_const_or_copy (lhs
, rhs
);
1828 /* If we have 0 = COND or 1 = COND equivalences, record them
1829 into our expression hash tables. */
1830 for (i
= 0; VEC_iterate (cond_equivalence
,
1831 edge_info
->cond_equivalences
, i
, eq
); ++i
)
1835 dom_thread_across_edge (walk_data
, true_edge
);
1837 /* And restore the various tables to their state before
1838 we threaded this edge. */
1839 remove_local_expressions_from_table ();
1842 /* Similarly for the ELSE arm. */
1843 if (potentially_threadable_block (false_edge
->dest
))
1845 struct edge_info
*edge_info
;
1848 VEC_safe_push (tree
, heap
, const_and_copies_stack
, NULL_TREE
);
1849 edge_info
= (struct edge_info
*) false_edge
->aux
;
1851 /* If we have info associated with this edge, record it into
1852 our equivalence tables. */
1855 cond_equivalence
*eq
;
1856 tree lhs
= edge_info
->lhs
;
1857 tree rhs
= edge_info
->rhs
;
1859 /* If we have a simple NAME = VALUE equivalence, record it. */
1860 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1861 record_const_or_copy (lhs
, rhs
);
1863 /* If we have 0 = COND or 1 = COND equivalences, record them
1864 into our expression hash tables. */
1865 for (i
= 0; VEC_iterate (cond_equivalence
,
1866 edge_info
->cond_equivalences
, i
, eq
); ++i
)
1870 /* Now thread the edge. */
1871 dom_thread_across_edge (walk_data
, false_edge
);
1873 /* No need to remove local expressions from our tables
1874 or restore vars to their original value as that will
1875 be done immediately below. */
1879 remove_local_expressions_from_table ();
1880 restore_vars_to_original_value ();
1883 /* Search for redundant computations in STMT. If any are found, then
1884 replace them with the variable holding the result of the computation.
1886 If safe, record this expression into the available expression hash
1890 eliminate_redundant_computations (gimple_stmt_iterator
* gsi
)
1896 bool assigns_var_p
= false;
1898 gimple stmt
= gsi_stmt (*gsi
);
1900 if (gimple_code (stmt
) == GIMPLE_PHI
)
1901 def
= gimple_phi_result (stmt
);
1903 def
= gimple_get_lhs (stmt
);
1905 /* Certain expressions on the RHS can be optimized away, but can not
1906 themselves be entered into the hash tables. */
1908 || TREE_CODE (def
) != SSA_NAME
1909 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
1910 || gimple_vdef (stmt
)
1911 /* Do not record equivalences for increments of ivs. This would create
1912 overlapping live ranges for a very questionable gain. */
1913 || simple_iv_increment_p (stmt
))
1916 /* Check if the expression has been computed before. */
1917 cached_lhs
= lookup_avail_expr (stmt
, insert
);
1919 opt_stats
.num_exprs_considered
++;
1921 /* Get the type of the expression we are trying to optimize. */
1922 if (is_gimple_assign (stmt
))
1924 expr_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1925 assigns_var_p
= true;
1927 else if (gimple_code (stmt
) == GIMPLE_COND
)
1928 expr_type
= boolean_type_node
;
1929 else if (is_gimple_call (stmt
))
1931 gcc_assert (gimple_call_lhs (stmt
));
1932 expr_type
= TREE_TYPE (gimple_call_lhs (stmt
));
1933 assigns_var_p
= true;
1935 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
1936 expr_type
= TREE_TYPE (gimple_switch_index (stmt
));
1937 else if (gimple_code (stmt
) == GIMPLE_PHI
)
1938 /* We can't propagate into a phi, so the logic below doesn't apply.
1939 Instead record an equivalence between the cached LHS and the
1940 PHI result of this statement, provided they are in the same block.
1941 This should be sufficient to kill the redundant phi. */
1943 if (def
&& cached_lhs
)
1944 record_const_or_copy (def
, cached_lhs
);
1953 /* It is safe to ignore types here since we have already done
1954 type checking in the hashing and equality routines. In fact
1955 type checking here merely gets in the way of constant
1956 propagation. Also, make sure that it is safe to propagate
1957 CACHED_LHS into the expression in STMT. */
1958 if ((TREE_CODE (cached_lhs
) != SSA_NAME
1960 || useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
))))
1961 || may_propagate_copy_into_stmt (stmt
, cached_lhs
))
1963 gcc_checking_assert (TREE_CODE (cached_lhs
) == SSA_NAME
1964 || is_gimple_min_invariant (cached_lhs
));
1966 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1968 fprintf (dump_file
, " Replaced redundant expr '");
1969 print_gimple_expr (dump_file
, stmt
, 0, dump_flags
);
1970 fprintf (dump_file
, "' with '");
1971 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
1972 fprintf (dump_file
, "'\n");
1978 && !useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
)))
1979 cached_lhs
= fold_convert (expr_type
, cached_lhs
);
1981 propagate_tree_value_into_stmt (gsi
, cached_lhs
);
1983 /* Since it is always necessary to mark the result as modified,
1984 perhaps we should move this into propagate_tree_value_into_stmt
1986 gimple_set_modified (gsi_stmt (*gsi
), true);
1990 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
1991 the available expressions table or the const_and_copies table.
1992 Detect and record those equivalences. */
1993 /* We handle only very simple copy equivalences here. The heavy
1994 lifing is done by eliminate_redundant_computations. */
1997 record_equivalences_from_stmt (gimple stmt
, int may_optimize_p
)
2000 enum tree_code lhs_code
;
2002 gcc_assert (is_gimple_assign (stmt
));
2004 lhs
= gimple_assign_lhs (stmt
);
2005 lhs_code
= TREE_CODE (lhs
);
2007 if (lhs_code
== SSA_NAME
2008 && gimple_assign_single_p (stmt
))
2010 tree rhs
= gimple_assign_rhs1 (stmt
);
2012 /* If the RHS of the assignment is a constant or another variable that
2013 may be propagated, register it in the CONST_AND_COPIES table. We
2014 do not need to record unwind data for this, since this is a true
2015 assignment and not an equivalence inferred from a comparison. All
2016 uses of this ssa name are dominated by this assignment, so unwinding
2017 just costs time and space. */
2019 && (TREE_CODE (rhs
) == SSA_NAME
2020 || is_gimple_min_invariant (rhs
)))
2022 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2024 fprintf (dump_file
, "==== ASGN ");
2025 print_generic_expr (dump_file
, lhs
, 0);
2026 fprintf (dump_file
, " = ");
2027 print_generic_expr (dump_file
, rhs
, 0);
2028 fprintf (dump_file
, "\n");
2031 set_ssa_name_value (lhs
, rhs
);
2035 /* A memory store, even an aliased store, creates a useful
2036 equivalence. By exchanging the LHS and RHS, creating suitable
2037 vops and recording the result in the available expression table,
2038 we may be able to expose more redundant loads. */
2039 if (!gimple_has_volatile_ops (stmt
)
2040 && gimple_references_memory_p (stmt
)
2041 && gimple_assign_single_p (stmt
)
2042 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
2043 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
2044 && !is_gimple_reg (lhs
))
2046 tree rhs
= gimple_assign_rhs1 (stmt
);
2049 /* Build a new statement with the RHS and LHS exchanged. */
2050 if (TREE_CODE (rhs
) == SSA_NAME
)
2052 /* NOTE tuples. The call to gimple_build_assign below replaced
2053 a call to build_gimple_modify_stmt, which did not set the
2054 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
2055 may cause an SSA validation failure, as the LHS may be a
2056 default-initialized name and should have no definition. I'm
2057 a bit dubious of this, as the artificial statement that we
2058 generate here may in fact be ill-formed, but it is simply
2059 used as an internal device in this pass, and never becomes
2061 gimple defstmt
= SSA_NAME_DEF_STMT (rhs
);
2062 new_stmt
= gimple_build_assign (rhs
, lhs
);
2063 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
2066 new_stmt
= gimple_build_assign (rhs
, lhs
);
2068 gimple_set_vuse (new_stmt
, gimple_vdef (stmt
));
2070 /* Finally enter the statement into the available expression
2072 lookup_avail_expr (new_stmt
, true);
2076 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2077 CONST_AND_COPIES. */
2080 cprop_operand (gimple stmt
, use_operand_p op_p
)
2083 tree op
= USE_FROM_PTR (op_p
);
2085 /* If the operand has a known constant value or it is known to be a
2086 copy of some other variable, use the value or copy stored in
2087 CONST_AND_COPIES. */
2088 val
= SSA_NAME_VALUE (op
);
2089 if (val
&& val
!= op
)
2091 /* Do not replace hard register operands in asm statements. */
2092 if (gimple_code (stmt
) == GIMPLE_ASM
2093 && !may_propagate_copy_into_asm (op
))
2096 /* Certain operands are not allowed to be copy propagated due
2097 to their interaction with exception handling and some GCC
2099 if (!may_propagate_copy (op
, val
))
2102 /* Do not propagate addresses that point to volatiles into memory
2103 stmts without volatile operands. */
2104 if (POINTER_TYPE_P (TREE_TYPE (val
))
2105 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val
)))
2106 && gimple_has_mem_ops (stmt
)
2107 && !gimple_has_volatile_ops (stmt
))
2110 /* Do not propagate copies if the propagated value is at a deeper loop
2111 depth than the propagatee. Otherwise, this may move loop variant
2112 variables outside of their loops and prevent coalescing
2113 opportunities. If the value was loop invariant, it will be hoisted
2114 by LICM and exposed for copy propagation. */
2115 if (loop_depth_of_name (val
) > loop_depth_of_name (op
))
2118 /* Do not propagate copies into simple IV increment statements.
2119 See PR23821 for how this can disturb IV analysis. */
2120 if (TREE_CODE (val
) != INTEGER_CST
2121 && simple_iv_increment_p (stmt
))
2125 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2127 fprintf (dump_file
, " Replaced '");
2128 print_generic_expr (dump_file
, op
, dump_flags
);
2129 fprintf (dump_file
, "' with %s '",
2130 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
2131 print_generic_expr (dump_file
, val
, dump_flags
);
2132 fprintf (dump_file
, "'\n");
2135 if (TREE_CODE (val
) != SSA_NAME
)
2136 opt_stats
.num_const_prop
++;
2138 opt_stats
.num_copy_prop
++;
2140 propagate_value (op_p
, val
);
2142 /* And note that we modified this statement. This is now
2143 safe, even if we changed virtual operands since we will
2144 rescan the statement and rewrite its operands again. */
2145 gimple_set_modified (stmt
, true);
2149 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2150 known value for that SSA_NAME (or NULL if no value is known).
2152 Propagate values from CONST_AND_COPIES into the uses, vuses and
2153 vdef_ops of STMT. */
2156 cprop_into_stmt (gimple stmt
)
2161 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_USE
)
2162 cprop_operand (stmt
, op_p
);
2165 /* Optimize the statement pointed to by iterator SI.
2167 We try to perform some simplistic global redundancy elimination and
2168 constant propagation:
2170 1- To detect global redundancy, we keep track of expressions that have
2171 been computed in this block and its dominators. If we find that the
2172 same expression is computed more than once, we eliminate repeated
2173 computations by using the target of the first one.
2175 2- Constant values and copy assignments. This is used to do very
2176 simplistic constant and copy propagation. When a constant or copy
2177 assignment is found, we map the value on the RHS of the assignment to
2178 the variable in the LHS in the CONST_AND_COPIES table. */
2181 optimize_stmt (basic_block bb
, gimple_stmt_iterator si
)
2183 gimple stmt
, old_stmt
;
2184 bool may_optimize_p
;
2185 bool modified_p
= false;
2187 old_stmt
= stmt
= gsi_stmt (si
);
2189 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2191 fprintf (dump_file
, "Optimizing statement ");
2192 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2195 if (gimple_code (stmt
) == GIMPLE_COND
)
2196 canonicalize_comparison (stmt
);
2198 update_stmt_if_modified (stmt
);
2199 opt_stats
.num_stmts
++;
2201 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2202 cprop_into_stmt (stmt
);
2204 /* If the statement has been modified with constant replacements,
2205 fold its RHS before checking for redundant computations. */
2206 if (gimple_modified_p (stmt
))
2210 /* Try to fold the statement making sure that STMT is kept
2212 if (fold_stmt (&si
))
2214 stmt
= gsi_stmt (si
);
2215 gimple_set_modified (stmt
, true);
2217 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2219 fprintf (dump_file
, " Folded to: ");
2220 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2224 /* We only need to consider cases that can yield a gimple operand. */
2225 if (gimple_assign_single_p (stmt
))
2226 rhs
= gimple_assign_rhs1 (stmt
);
2227 else if (gimple_code (stmt
) == GIMPLE_GOTO
)
2228 rhs
= gimple_goto_dest (stmt
);
2229 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2230 /* This should never be an ADDR_EXPR. */
2231 rhs
= gimple_switch_index (stmt
);
2233 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
2234 recompute_tree_invariant_for_addr_expr (rhs
);
2236 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2237 even if fold_stmt updated the stmt already and thus cleared
2238 gimple_modified_p flag on it. */
2242 /* Check for redundant computations. Do this optimization only
2243 for assignments that have no volatile ops and conditionals. */
2244 may_optimize_p
= (!gimple_has_side_effects (stmt
)
2245 && (is_gimple_assign (stmt
)
2246 || (is_gimple_call (stmt
)
2247 && gimple_call_lhs (stmt
) != NULL_TREE
)
2248 || gimple_code (stmt
) == GIMPLE_COND
2249 || gimple_code (stmt
) == GIMPLE_SWITCH
));
2253 if (gimple_code (stmt
) == GIMPLE_CALL
)
2255 /* Resolve __builtin_constant_p. If it hasn't been
2256 folded to integer_one_node by now, it's fairly
2257 certain that the value simply isn't constant. */
2258 tree callee
= gimple_call_fndecl (stmt
);
2260 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
2261 && DECL_FUNCTION_CODE (callee
) == BUILT_IN_CONSTANT_P
)
2263 propagate_tree_value_into_stmt (&si
, integer_zero_node
);
2264 stmt
= gsi_stmt (si
);
2268 update_stmt_if_modified (stmt
);
2269 eliminate_redundant_computations (&si
);
2270 stmt
= gsi_stmt (si
);
2272 /* Perform simple redundant store elimination. */
2273 if (gimple_assign_single_p (stmt
)
2274 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
2276 tree lhs
= gimple_assign_lhs (stmt
);
2277 tree rhs
= gimple_assign_rhs1 (stmt
);
2280 if (TREE_CODE (rhs
) == SSA_NAME
)
2282 tree tem
= SSA_NAME_VALUE (rhs
);
2286 /* Build a new statement with the RHS and LHS exchanged. */
2287 if (TREE_CODE (rhs
) == SSA_NAME
)
2289 gimple defstmt
= SSA_NAME_DEF_STMT (rhs
);
2290 new_stmt
= gimple_build_assign (rhs
, lhs
);
2291 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
2294 new_stmt
= gimple_build_assign (rhs
, lhs
);
2295 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
2296 cached_lhs
= lookup_avail_expr (new_stmt
, false);
2298 && rhs
== cached_lhs
)
2300 basic_block bb
= gimple_bb (stmt
);
2301 unlink_stmt_vdef (stmt
);
2302 if (gsi_remove (&si
, true))
2304 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2305 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2306 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2308 release_defs (stmt
);
2314 /* Record any additional equivalences created by this statement. */
2315 if (is_gimple_assign (stmt
))
2316 record_equivalences_from_stmt (stmt
, may_optimize_p
);
2318 /* If STMT is a COND_EXPR and it was modified, then we may know
2319 where it goes. If that is the case, then mark the CFG as altered.
2321 This will cause us to later call remove_unreachable_blocks and
2322 cleanup_tree_cfg when it is safe to do so. It is not safe to
2323 clean things up here since removal of edges and such can trigger
2324 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2327 That's all fine and good, except that once SSA_NAMEs are released
2328 to the manager, we must not call create_ssa_name until all references
2329 to released SSA_NAMEs have been eliminated.
2331 All references to the deleted SSA_NAMEs can not be eliminated until
2332 we remove unreachable blocks.
2334 We can not remove unreachable blocks until after we have completed
2335 any queued jump threading.
2337 We can not complete any queued jump threads until we have taken
2338 appropriate variables out of SSA form. Taking variables out of
2339 SSA form can call create_ssa_name and thus we lose.
2341 Ultimately I suspect we're going to need to change the interface
2342 into the SSA_NAME manager. */
2343 if (gimple_modified_p (stmt
) || modified_p
)
2347 update_stmt_if_modified (stmt
);
2349 if (gimple_code (stmt
) == GIMPLE_COND
)
2350 val
= fold_binary_loc (gimple_location (stmt
),
2351 gimple_cond_code (stmt
), boolean_type_node
,
2352 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
2353 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2354 val
= gimple_switch_index (stmt
);
2356 if (val
&& TREE_CODE (val
) == INTEGER_CST
&& find_taken_edge (bb
, val
))
2359 /* If we simplified a statement in such a way as to be shown that it
2360 cannot trap, update the eh information and the cfg to match. */
2361 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
2363 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2364 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2365 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2370 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
2371 If found, return its LHS. Otherwise insert STMT in the table and
2374 Also, when an expression is first inserted in the table, it is also
2375 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
2376 we finish processing this block and its children. */
2379 lookup_avail_expr (gimple stmt
, bool insert
)
2384 struct expr_hash_elt element
;
2386 /* Get LHS of phi, assignment, or call; else NULL_TREE. */
2387 if (gimple_code (stmt
) == GIMPLE_PHI
)
2388 lhs
= gimple_phi_result (stmt
);
2390 lhs
= gimple_get_lhs (stmt
);
2392 initialize_hash_element (stmt
, lhs
, &element
);
2394 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2396 fprintf (dump_file
, "LKUP ");
2397 print_expr_hash_elt (dump_file
, &element
);
2400 /* Don't bother remembering constant assignments and copy operations.
2401 Constants and copy operations are handled by the constant/copy propagator
2402 in optimize_stmt. */
2403 if (element
.expr
.kind
== EXPR_SINGLE
2404 && (TREE_CODE (element
.expr
.ops
.single
.rhs
) == SSA_NAME
2405 || is_gimple_min_invariant (element
.expr
.ops
.single
.rhs
)))
2408 /* Finally try to find the expression in the main expression hash table. */
2409 slot
= htab_find_slot_with_hash (avail_exprs
, &element
, element
.hash
,
2410 (insert
? INSERT
: NO_INSERT
));
2413 free_expr_hash_elt_contents (&element
);
2416 else if (*slot
== NULL
)
2418 struct expr_hash_elt
*element2
= XNEW (struct expr_hash_elt
);
2419 *element2
= element
;
2420 element2
->stamp
= element2
;
2421 *slot
= (void *) element2
;
2423 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2425 fprintf (dump_file
, "2>>> ");
2426 print_expr_hash_elt (dump_file
, element2
);
2429 VEC_safe_push (expr_hash_elt_t
, heap
, avail_exprs_stack
, element2
);
2433 free_expr_hash_elt_contents (&element
);
2435 /* Extract the LHS of the assignment so that it can be used as the current
2436 definition of another variable. */
2437 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
2439 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2440 use the value from the const_and_copies table. */
2441 if (TREE_CODE (lhs
) == SSA_NAME
)
2443 temp
= SSA_NAME_VALUE (lhs
);
2448 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2450 fprintf (dump_file
, "FIND: ");
2451 print_generic_expr (dump_file
, lhs
, 0);
2452 fprintf (dump_file
, "\n");
2458 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number
2459 for expressions using the code of the expression and the SSA numbers of
2463 avail_expr_hash (const void *p
)
2465 gimple stmt
= ((const struct expr_hash_elt
*)p
)->stmt
;
2466 const struct hashable_expr
*expr
= &((const struct expr_hash_elt
*)p
)->expr
;
2470 val
= iterative_hash_hashable_expr (expr
, val
);
2472 /* If the hash table entry is not associated with a statement, then we
2473 can just hash the expression and not worry about virtual operands
2478 /* Add the SSA version numbers of the vuse operand. This is important
2479 because compound variables like arrays are not renamed in the
2480 operands. Rather, the rename is done on the virtual variable
2481 representing all the elements of the array. */
2482 if ((vuse
= gimple_vuse (stmt
)))
2483 val
= iterative_hash_expr (vuse
, val
);
2489 real_avail_expr_hash (const void *p
)
2491 return ((const struct expr_hash_elt
*)p
)->hash
;
2495 avail_expr_eq (const void *p1
, const void *p2
)
2497 gimple stmt1
= ((const struct expr_hash_elt
*)p1
)->stmt
;
2498 const struct hashable_expr
*expr1
= &((const struct expr_hash_elt
*)p1
)->expr
;
2499 const struct expr_hash_elt
*stamp1
= ((const struct expr_hash_elt
*)p1
)->stamp
;
2500 gimple stmt2
= ((const struct expr_hash_elt
*)p2
)->stmt
;
2501 const struct hashable_expr
*expr2
= &((const struct expr_hash_elt
*)p2
)->expr
;
2502 const struct expr_hash_elt
*stamp2
= ((const struct expr_hash_elt
*)p2
)->stamp
;
2504 /* This case should apply only when removing entries from the table. */
2505 if (stamp1
== stamp2
)
2509 We add stmts to a hash table and them modify them. To detect the case
2510 that we modify a stmt and then search for it, we assume that the hash
2511 is always modified by that change.
2512 We have to fully check why this doesn't happen on trunk or rewrite
2513 this in a more reliable (and easier to understand) way. */
2514 if (((const struct expr_hash_elt
*)p1
)->hash
2515 != ((const struct expr_hash_elt
*)p2
)->hash
)
2518 /* In case of a collision, both RHS have to be identical and have the
2519 same VUSE operands. */
2520 if (hashable_expr_equal_p (expr1
, expr2
)
2521 && types_compatible_p (expr1
->type
, expr2
->type
))
2523 /* Note that STMT1 and/or STMT2 may be NULL. */
2524 return ((stmt1
? gimple_vuse (stmt1
) : NULL_TREE
)
2525 == (stmt2
? gimple_vuse (stmt2
) : NULL_TREE
));
2531 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2532 up degenerate PHIs created by or exposed by jump threading. */
2534 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
2538 degenerate_phi_result (gimple phi
)
2540 tree lhs
= gimple_phi_result (phi
);
2544 /* Ignoring arguments which are the same as LHS, if all the remaining
2545 arguments are the same, then the PHI is a degenerate and has the
2546 value of that common argument. */
2547 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2549 tree arg
= gimple_phi_arg_def (phi
, i
);
2557 else if (arg
== val
)
2559 /* We bring in some of operand_equal_p not only to speed things
2560 up, but also to avoid crashing when dereferencing the type of
2561 a released SSA name. */
2562 else if (TREE_CODE (val
) != TREE_CODE (arg
)
2563 || TREE_CODE (val
) == SSA_NAME
2564 || !operand_equal_p (arg
, val
, 0))
2567 return (i
== gimple_phi_num_args (phi
) ? val
: NULL
);
2570 /* Given a statement STMT, which is either a PHI node or an assignment,
2571 remove it from the IL. */
2574 remove_stmt_or_phi (gimple stmt
)
2576 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
2578 if (gimple_code (stmt
) == GIMPLE_PHI
)
2579 remove_phi_node (&gsi
, true);
2582 gsi_remove (&gsi
, true);
2583 release_defs (stmt
);
2587 /* Given a statement STMT, which is either a PHI node or an assignment,
2588 return the "rhs" of the node, in the case of a non-degenerate
2589 phi, NULL is returned. */
2592 get_rhs_or_phi_arg (gimple stmt
)
2594 if (gimple_code (stmt
) == GIMPLE_PHI
)
2595 return degenerate_phi_result (stmt
);
2596 else if (gimple_assign_single_p (stmt
))
2597 return gimple_assign_rhs1 (stmt
);
2603 /* Given a statement STMT, which is either a PHI node or an assignment,
2604 return the "lhs" of the node. */
2607 get_lhs_or_phi_result (gimple stmt
)
2609 if (gimple_code (stmt
) == GIMPLE_PHI
)
2610 return gimple_phi_result (stmt
);
2611 else if (is_gimple_assign (stmt
))
2612 return gimple_assign_lhs (stmt
);
2617 /* Propagate RHS into all uses of LHS (when possible).
2619 RHS and LHS are derived from STMT, which is passed in solely so
2620 that we can remove it if propagation is successful.
2622 When propagating into a PHI node or into a statement which turns
2623 into a trivial copy or constant initialization, set the
2624 appropriate bit in INTERESTING_NAMEs so that we will visit those
2625 nodes as well in an effort to pick up secondary optimization
2629 propagate_rhs_into_lhs (gimple stmt
, tree lhs
, tree rhs
, bitmap interesting_names
)
2631 /* First verify that propagation is valid and isn't going to move a
2632 loop variant variable outside its loop. */
2633 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
)
2634 && (TREE_CODE (rhs
) != SSA_NAME
2635 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
2636 && may_propagate_copy (lhs
, rhs
)
2637 && loop_depth_of_name (lhs
) >= loop_depth_of_name (rhs
))
2639 use_operand_p use_p
;
2640 imm_use_iterator iter
;
2645 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2647 fprintf (dump_file
, " Replacing '");
2648 print_generic_expr (dump_file
, lhs
, dump_flags
);
2649 fprintf (dump_file
, "' with %s '",
2650 (TREE_CODE (rhs
) != SSA_NAME
? "constant" : "variable"));
2651 print_generic_expr (dump_file
, rhs
, dump_flags
);
2652 fprintf (dump_file
, "'\n");
2655 /* Walk over every use of LHS and try to replace the use with RHS.
2656 At this point the only reason why such a propagation would not
2657 be successful would be if the use occurs in an ASM_EXPR. */
2658 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
2660 /* Leave debug stmts alone. If we succeed in propagating
2661 all non-debug uses, we'll drop the DEF, and propagation
2662 into debug stmts will occur then. */
2663 if (gimple_debug_bind_p (use_stmt
))
2666 /* It's not always safe to propagate into an ASM_EXPR. */
2667 if (gimple_code (use_stmt
) == GIMPLE_ASM
2668 && ! may_propagate_copy_into_asm (lhs
))
2674 /* It's not ok to propagate into the definition stmt of RHS.
2676 # prephitmp.12_36 = PHI <g_67.1_6(9)>
2677 g_67.1_6 = prephitmp.12_36;
2679 While this is strictly all dead code we do not want to
2680 deal with this here. */
2681 if (TREE_CODE (rhs
) == SSA_NAME
2682 && SSA_NAME_DEF_STMT (rhs
) == use_stmt
)
2689 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2691 fprintf (dump_file
, " Original statement:");
2692 print_gimple_stmt (dump_file
, use_stmt
, 0, dump_flags
);
2695 /* Propagate the RHS into this use of the LHS. */
2696 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2697 propagate_value (use_p
, rhs
);
2699 /* Special cases to avoid useless calls into the folding
2700 routines, operand scanning, etc.
2702 Propagation into a PHI may cause the PHI to become
2703 a degenerate, so mark the PHI as interesting. No other
2704 actions are necessary. */
2705 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
2710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2712 fprintf (dump_file
, " Updated statement:");
2713 print_gimple_stmt (dump_file
, use_stmt
, 0, dump_flags
);
2716 result
= get_lhs_or_phi_result (use_stmt
);
2717 bitmap_set_bit (interesting_names
, SSA_NAME_VERSION (result
));
2721 /* From this point onward we are propagating into a
2722 real statement. Folding may (or may not) be possible,
2723 we may expose new operands, expose dead EH edges,
2725 /* NOTE tuples. In the tuples world, fold_stmt_inplace
2726 cannot fold a call that simplifies to a constant,
2727 because the GIMPLE_CALL must be replaced by a
2728 GIMPLE_ASSIGN, and there is no way to effect such a
2729 transformation in-place. We might want to consider
2730 using the more general fold_stmt here. */
2732 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
2733 fold_stmt_inplace (&gsi
);
2736 /* Sometimes propagation can expose new operands to the
2738 update_stmt (use_stmt
);
2741 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2743 fprintf (dump_file
, " Updated statement:");
2744 print_gimple_stmt (dump_file
, use_stmt
, 0, dump_flags
);
2747 /* If we replaced a variable index with a constant, then
2748 we would need to update the invariant flag for ADDR_EXPRs. */
2749 if (gimple_assign_single_p (use_stmt
)
2750 && TREE_CODE (gimple_assign_rhs1 (use_stmt
)) == ADDR_EXPR
)
2751 recompute_tree_invariant_for_addr_expr
2752 (gimple_assign_rhs1 (use_stmt
));
2754 /* If we cleaned up EH information from the statement,
2755 mark its containing block as needing EH cleanups. */
2756 if (maybe_clean_or_replace_eh_stmt (use_stmt
, use_stmt
))
2758 bitmap_set_bit (need_eh_cleanup
, gimple_bb (use_stmt
)->index
);
2759 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2760 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2763 /* Propagation may expose new trivial copy/constant propagation
2765 if (gimple_assign_single_p (use_stmt
)
2766 && TREE_CODE (gimple_assign_lhs (use_stmt
)) == SSA_NAME
2767 && (TREE_CODE (gimple_assign_rhs1 (use_stmt
)) == SSA_NAME
2768 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt
))))
2770 tree result
= get_lhs_or_phi_result (use_stmt
);
2771 bitmap_set_bit (interesting_names
, SSA_NAME_VERSION (result
));
2774 /* Propagation into these nodes may make certain edges in
2775 the CFG unexecutable. We want to identify them as PHI nodes
2776 at the destination of those unexecutable edges may become
2778 else if (gimple_code (use_stmt
) == GIMPLE_COND
2779 || gimple_code (use_stmt
) == GIMPLE_SWITCH
2780 || gimple_code (use_stmt
) == GIMPLE_GOTO
)
2784 if (gimple_code (use_stmt
) == GIMPLE_COND
)
2785 val
= fold_binary_loc (gimple_location (use_stmt
),
2786 gimple_cond_code (use_stmt
),
2788 gimple_cond_lhs (use_stmt
),
2789 gimple_cond_rhs (use_stmt
));
2790 else if (gimple_code (use_stmt
) == GIMPLE_SWITCH
)
2791 val
= gimple_switch_index (use_stmt
);
2793 val
= gimple_goto_dest (use_stmt
);
2795 if (val
&& is_gimple_min_invariant (val
))
2797 basic_block bb
= gimple_bb (use_stmt
);
2798 edge te
= find_taken_edge (bb
, val
);
2801 gimple_stmt_iterator gsi
, psi
;
2803 /* Remove all outgoing edges except TE. */
2804 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
));)
2808 /* Mark all the PHI nodes at the destination of
2809 the unexecutable edge as interesting. */
2810 for (psi
= gsi_start_phis (e
->dest
);
2814 gimple phi
= gsi_stmt (psi
);
2816 tree result
= gimple_phi_result (phi
);
2817 int version
= SSA_NAME_VERSION (result
);
2819 bitmap_set_bit (interesting_names
, version
);
2822 te
->probability
+= e
->probability
;
2824 te
->count
+= e
->count
;
2832 gsi
= gsi_last_bb (gimple_bb (use_stmt
));
2833 gsi_remove (&gsi
, true);
2835 /* And fixup the flags on the single remaining edge. */
2836 te
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
2837 te
->flags
&= ~EDGE_ABNORMAL
;
2838 te
->flags
|= EDGE_FALLTHRU
;
2839 if (te
->probability
> REG_BR_PROB_BASE
)
2840 te
->probability
= REG_BR_PROB_BASE
;
2845 /* Ensure there is nothing else to do. */
2846 gcc_assert (!all
|| has_zero_uses (lhs
));
2848 /* If we were able to propagate away all uses of LHS, then
2849 we can remove STMT. */
2851 remove_stmt_or_phi (stmt
);
2855 /* STMT is either a PHI node (potentially a degenerate PHI node) or
2856 a statement that is a trivial copy or constant initialization.
2858 Attempt to eliminate T by propagating its RHS into all uses of
2859 its LHS. This may in turn set new bits in INTERESTING_NAMES
2860 for nodes we want to revisit later.
2862 All exit paths should clear INTERESTING_NAMES for the result
2866 eliminate_const_or_copy (gimple stmt
, bitmap interesting_names
)
2868 tree lhs
= get_lhs_or_phi_result (stmt
);
2870 int version
= SSA_NAME_VERSION (lhs
);
2872 /* If the LHS of this statement or PHI has no uses, then we can
2873 just eliminate it. This can occur if, for example, the PHI
2874 was created by block duplication due to threading and its only
2875 use was in the conditional at the end of the block which was
2877 if (has_zero_uses (lhs
))
2879 bitmap_clear_bit (interesting_names
, version
);
2880 remove_stmt_or_phi (stmt
);
2884 /* Get the RHS of the assignment or PHI node if the PHI is a
2886 rhs
= get_rhs_or_phi_arg (stmt
);
2889 bitmap_clear_bit (interesting_names
, version
);
2893 propagate_rhs_into_lhs (stmt
, lhs
, rhs
, interesting_names
);
2895 /* Note that STMT may well have been deleted by now, so do
2896 not access it, instead use the saved version # to clear
2897 T's entry in the worklist. */
2898 bitmap_clear_bit (interesting_names
, version
);
2901 /* The first phase in degenerate PHI elimination.
2903 Eliminate the degenerate PHIs in BB, then recurse on the
2904 dominator children of BB. */
2907 eliminate_degenerate_phis_1 (basic_block bb
, bitmap interesting_names
)
2909 gimple_stmt_iterator gsi
;
2912 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2914 gimple phi
= gsi_stmt (gsi
);
2916 eliminate_const_or_copy (phi
, interesting_names
);
2919 /* Recurse into the dominator children of BB. */
2920 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2922 son
= next_dom_son (CDI_DOMINATORS
, son
))
2923 eliminate_degenerate_phis_1 (son
, interesting_names
);
2927 /* A very simple pass to eliminate degenerate PHI nodes from the
2928 IL. This is meant to be fast enough to be able to be run several
2929 times in the optimization pipeline.
2931 Certain optimizations, particularly those which duplicate blocks
2932 or remove edges from the CFG can create or expose PHIs which are
2933 trivial copies or constant initializations.
2935 While we could pick up these optimizations in DOM or with the
2936 combination of copy-prop and CCP, those solutions are far too
2937 heavy-weight for our needs.
2939 This implementation has two phases so that we can efficiently
2940 eliminate the first order degenerate PHIs and second order
2943 The first phase performs a dominator walk to identify and eliminate
2944 the vast majority of the degenerate PHIs. When a degenerate PHI
2945 is identified and eliminated any affected statements or PHIs
2946 are put on a worklist.
2948 The second phase eliminates degenerate PHIs and trivial copies
2949 or constant initializations using the worklist. This is how we
2950 pick up the secondary optimization opportunities with minimal
2954 eliminate_degenerate_phis (void)
2956 bitmap interesting_names
;
2957 bitmap interesting_names1
;
2959 /* Bitmap of blocks which need EH information updated. We can not
2960 update it on-the-fly as doing so invalidates the dominator tree. */
2961 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
2963 /* INTERESTING_NAMES is effectively our worklist, indexed by
2966 A set bit indicates that the statement or PHI node which
2967 defines the SSA_NAME should be (re)examined to determine if
2968 it has become a degenerate PHI or trivial const/copy propagation
2971 Experiments have show we generally get better compilation
2972 time behavior with bitmaps rather than sbitmaps. */
2973 interesting_names
= BITMAP_ALLOC (NULL
);
2974 interesting_names1
= BITMAP_ALLOC (NULL
);
2976 calculate_dominance_info (CDI_DOMINATORS
);
2977 cfg_altered
= false;
2979 /* First phase. Eliminate degenerate PHIs via a dominator
2982 Experiments have indicated that we generally get better
2983 compile-time behavior by visiting blocks in the first
2984 phase in dominator order. Presumably this is because walking
2985 in dominator order leaves fewer PHIs for later examination
2986 by the worklist phase. */
2987 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR
, interesting_names
);
2989 /* Second phase. Eliminate second order degenerate PHIs as well
2990 as trivial copies or constant initializations identified by
2991 the first phase or this phase. Basically we keep iterating
2992 until our set of INTERESTING_NAMEs is empty. */
2993 while (!bitmap_empty_p (interesting_names
))
2998 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
2999 changed during the loop. Copy it to another bitmap and
3001 bitmap_copy (interesting_names1
, interesting_names
);
3003 EXECUTE_IF_SET_IN_BITMAP (interesting_names1
, 0, i
, bi
)
3005 tree name
= ssa_name (i
);
3007 /* Ignore SSA_NAMEs that have been released because
3008 their defining statement was deleted (unreachable). */
3010 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i
)),
3016 free_dominance_info (CDI_DOMINATORS
);
3018 /* Propagation of const and copies may make some EH edges dead. Purge
3019 such edges from the CFG as needed. */
3020 if (!bitmap_empty_p (need_eh_cleanup
))
3022 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
3023 BITMAP_FREE (need_eh_cleanup
);
3026 BITMAP_FREE (interesting_names
);
3027 BITMAP_FREE (interesting_names1
);
3031 struct gimple_opt_pass pass_phi_only_cprop
=
3035 "phicprop", /* name */
3036 gate_dominator
, /* gate */
3037 eliminate_degenerate_phis
, /* execute */
3040 0, /* static_pass_number */
3041 TV_TREE_PHI_CPROP
, /* tv_id */
3042 PROP_cfg
| PROP_ssa
, /* properties_required */
3043 0, /* properties_provided */
3044 0, /* properties_destroyed */
3045 0, /* todo_flags_start */
3050 | TODO_update_ssa
/* todo_flags_finish */