1 /* SSA Dominator optimizations for trees
2 Copyright (C) 2001-2014 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
24 #include "hash-table.h"
27 #include "stor-layout.h"
30 #include "basic-block.h"
33 #include "gimple-pretty-print.h"
34 #include "tree-ssa-alias.h"
35 #include "internal-fn.h"
36 #include "gimple-fold.h"
38 #include "gimple-expr.h"
41 #include "gimple-iterator.h"
42 #include "gimple-ssa.h"
44 #include "tree-phinodes.h"
45 #include "ssa-iterators.h"
46 #include "stringpool.h"
47 #include "tree-ssanames.h"
48 #include "tree-into-ssa.h"
50 #include "tree-pass.h"
51 #include "tree-ssa-propagate.h"
52 #include "tree-ssa-threadupdate.h"
53 #include "langhooks.h"
55 #include "tree-ssa-threadedge.h"
56 #include "tree-ssa-dom.h"
58 /* This file implements optimizations on the dominator tree. */
60 /* Representation of a "naked" right-hand-side expression, to be used
61 in recording available expressions in the expression hash table. */
78 struct { tree rhs
; } single
;
79 struct { enum tree_code op
; tree opnd
; } unary
;
80 struct { enum tree_code op
; tree opnd0
, opnd1
; } binary
;
81 struct { enum tree_code op
; tree opnd0
, opnd1
, opnd2
; } ternary
;
82 struct { gimple fn_from
; bool pure
; size_t nargs
; tree
*args
; } call
;
83 struct { size_t nargs
; tree
*args
; } phi
;
87 /* Structure for recording known values of a conditional expression
88 at the exits from its block. */
90 typedef struct cond_equivalence_s
92 struct hashable_expr cond
;
97 /* Structure for recording edge equivalences as well as any pending
98 edge redirections during the dominator optimizer.
100 Computing and storing the edge equivalences instead of creating
101 them on-demand can save significant amounts of time, particularly
102 for pathological cases involving switch statements.
104 These structures live for a single iteration of the dominator
105 optimizer in the edge's AUX field. At the end of an iteration we
106 free each of these structures and update the AUX field to point
107 to any requested redirection target (the code for updating the
108 CFG and SSA graph for edge redirection expects redirection edge
109 targets to be in the AUX field for each edge. */
113 /* If this edge creates a simple equivalence, the LHS and RHS of
114 the equivalence will be stored here. */
118 /* Traversing an edge may also indicate one or more particular conditions
119 are true or false. */
120 vec
<cond_equivalence
> cond_equivalences
;
123 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any
124 expressions it enters into the hash table along with a marker entry
125 (null). When we finish processing the block, we pop off entries and
126 remove the expressions from the global hash table until we hit the
128 typedef struct expr_hash_elt
* expr_hash_elt_t
;
130 static vec
<expr_hash_elt_t
> avail_exprs_stack
;
132 /* Structure for entries in the expression hash table. */
136 /* The value (lhs) of this expression. */
139 /* The expression (rhs) we want to record. */
140 struct hashable_expr expr
;
142 /* The stmt pointer if this element corresponds to a statement. */
145 /* The hash value for RHS. */
148 /* A unique stamp, typically the address of the hash
149 element itself, used in removing entries from the table. */
150 struct expr_hash_elt
*stamp
;
153 /* Hashtable helpers. */
155 static bool hashable_expr_equal_p (const struct hashable_expr
*,
156 const struct hashable_expr
*);
157 static void free_expr_hash_elt (void *);
159 struct expr_elt_hasher
161 typedef expr_hash_elt
*value_type
;
162 typedef expr_hash_elt
*compare_type
;
163 typedef int store_values_directly
;
164 static inline hashval_t
hash (const value_type
&);
165 static inline bool equal (const value_type
&, const compare_type
&);
166 static inline void remove (value_type
&);
170 expr_elt_hasher::hash (const value_type
&p
)
176 expr_elt_hasher::equal (const value_type
&p1
, const compare_type
&p2
)
178 gimple stmt1
= p1
->stmt
;
179 const struct hashable_expr
*expr1
= &p1
->expr
;
180 const struct expr_hash_elt
*stamp1
= p1
->stamp
;
181 gimple stmt2
= p2
->stmt
;
182 const struct hashable_expr
*expr2
= &p2
->expr
;
183 const struct expr_hash_elt
*stamp2
= p2
->stamp
;
185 /* This case should apply only when removing entries from the table. */
186 if (stamp1
== stamp2
)
190 We add stmts to a hash table and them modify them. To detect the case
191 that we modify a stmt and then search for it, we assume that the hash
192 is always modified by that change.
193 We have to fully check why this doesn't happen on trunk or rewrite
194 this in a more reliable (and easier to understand) way. */
195 if (((const struct expr_hash_elt
*)p1
)->hash
196 != ((const struct expr_hash_elt
*)p2
)->hash
)
199 /* In case of a collision, both RHS have to be identical and have the
200 same VUSE operands. */
201 if (hashable_expr_equal_p (expr1
, expr2
)
202 && types_compatible_p (expr1
->type
, expr2
->type
))
204 /* Note that STMT1 and/or STMT2 may be NULL. */
205 return ((stmt1
? gimple_vuse (stmt1
) : NULL_TREE
)
206 == (stmt2
? gimple_vuse (stmt2
) : NULL_TREE
));
212 /* Delete an expr_hash_elt and reclaim its storage. */
215 expr_elt_hasher::remove (value_type
&element
)
217 free_expr_hash_elt (element
);
220 /* Hash table with expressions made available during the renaming process.
221 When an assignment of the form X_i = EXPR is found, the statement is
222 stored in this table. If the same expression EXPR is later found on the
223 RHS of another statement, it is replaced with X_i (thus performing
224 global redundancy elimination). Similarly as we pass through conditionals
225 we record the conditional itself as having either a true or false value
227 static hash_table
<expr_elt_hasher
> *avail_exprs
;
229 /* Stack of dest,src pairs that need to be restored during finalization.
231 A NULL entry is used to mark the end of pairs which need to be
232 restored during finalization of this block. */
233 static vec
<tree
> const_and_copies_stack
;
235 /* Track whether or not we have changed the control flow graph. */
236 static bool cfg_altered
;
238 /* Bitmap of blocks that have had EH statements cleaned. We should
239 remove their dead edges eventually. */
240 static bitmap need_eh_cleanup
;
242 /* Statistics for dominator optimizations. */
246 long num_exprs_considered
;
252 static struct opt_stats_d opt_stats
;
254 /* Local functions. */
255 static void optimize_stmt (basic_block
, gimple_stmt_iterator
);
256 static tree
lookup_avail_expr (gimple
, bool);
257 static hashval_t
avail_expr_hash (const void *);
258 static void htab_statistics (FILE *,
259 const hash_table
<expr_elt_hasher
> &);
260 static void record_cond (cond_equivalence
*);
261 static void record_const_or_copy (tree
, tree
);
262 static void record_equality (tree
, tree
);
263 static void record_equivalences_from_phis (basic_block
);
264 static void record_equivalences_from_incoming_edge (basic_block
);
265 static void eliminate_redundant_computations (gimple_stmt_iterator
*);
266 static void record_equivalences_from_stmt (gimple
, int);
267 static void remove_local_expressions_from_table (void);
268 static void restore_vars_to_original_value (void);
269 static edge
single_incoming_edge_ignoring_loop_edges (basic_block
);
272 /* Given a statement STMT, initialize the hash table element pointed to
276 initialize_hash_element (gimple stmt
, tree lhs
,
277 struct expr_hash_elt
*element
)
279 enum gimple_code code
= gimple_code (stmt
);
280 struct hashable_expr
*expr
= &element
->expr
;
282 if (code
== GIMPLE_ASSIGN
)
284 enum tree_code subcode
= gimple_assign_rhs_code (stmt
);
286 switch (get_gimple_rhs_class (subcode
))
288 case GIMPLE_SINGLE_RHS
:
289 expr
->kind
= EXPR_SINGLE
;
290 expr
->type
= TREE_TYPE (gimple_assign_rhs1 (stmt
));
291 expr
->ops
.single
.rhs
= gimple_assign_rhs1 (stmt
);
293 case GIMPLE_UNARY_RHS
:
294 expr
->kind
= EXPR_UNARY
;
295 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
296 expr
->ops
.unary
.op
= subcode
;
297 expr
->ops
.unary
.opnd
= gimple_assign_rhs1 (stmt
);
299 case GIMPLE_BINARY_RHS
:
300 expr
->kind
= EXPR_BINARY
;
301 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
302 expr
->ops
.binary
.op
= subcode
;
303 expr
->ops
.binary
.opnd0
= gimple_assign_rhs1 (stmt
);
304 expr
->ops
.binary
.opnd1
= gimple_assign_rhs2 (stmt
);
306 case GIMPLE_TERNARY_RHS
:
307 expr
->kind
= EXPR_TERNARY
;
308 expr
->type
= TREE_TYPE (gimple_assign_lhs (stmt
));
309 expr
->ops
.ternary
.op
= subcode
;
310 expr
->ops
.ternary
.opnd0
= gimple_assign_rhs1 (stmt
);
311 expr
->ops
.ternary
.opnd1
= gimple_assign_rhs2 (stmt
);
312 expr
->ops
.ternary
.opnd2
= gimple_assign_rhs3 (stmt
);
318 else if (code
== GIMPLE_COND
)
320 expr
->type
= boolean_type_node
;
321 expr
->kind
= EXPR_BINARY
;
322 expr
->ops
.binary
.op
= gimple_cond_code (stmt
);
323 expr
->ops
.binary
.opnd0
= gimple_cond_lhs (stmt
);
324 expr
->ops
.binary
.opnd1
= gimple_cond_rhs (stmt
);
326 else if (code
== GIMPLE_CALL
)
328 size_t nargs
= gimple_call_num_args (stmt
);
331 gcc_assert (gimple_call_lhs (stmt
));
333 expr
->type
= TREE_TYPE (gimple_call_lhs (stmt
));
334 expr
->kind
= EXPR_CALL
;
335 expr
->ops
.call
.fn_from
= stmt
;
337 if (gimple_call_flags (stmt
) & (ECF_CONST
| ECF_PURE
))
338 expr
->ops
.call
.pure
= true;
340 expr
->ops
.call
.pure
= false;
342 expr
->ops
.call
.nargs
= nargs
;
343 expr
->ops
.call
.args
= XCNEWVEC (tree
, nargs
);
344 for (i
= 0; i
< nargs
; i
++)
345 expr
->ops
.call
.args
[i
] = gimple_call_arg (stmt
, i
);
347 else if (code
== GIMPLE_SWITCH
)
349 expr
->type
= TREE_TYPE (gimple_switch_index (stmt
));
350 expr
->kind
= EXPR_SINGLE
;
351 expr
->ops
.single
.rhs
= gimple_switch_index (stmt
);
353 else if (code
== GIMPLE_GOTO
)
355 expr
->type
= TREE_TYPE (gimple_goto_dest (stmt
));
356 expr
->kind
= EXPR_SINGLE
;
357 expr
->ops
.single
.rhs
= gimple_goto_dest (stmt
);
359 else if (code
== GIMPLE_PHI
)
361 size_t nargs
= gimple_phi_num_args (stmt
);
364 expr
->type
= TREE_TYPE (gimple_phi_result (stmt
));
365 expr
->kind
= EXPR_PHI
;
366 expr
->ops
.phi
.nargs
= nargs
;
367 expr
->ops
.phi
.args
= XCNEWVEC (tree
, nargs
);
369 for (i
= 0; i
< nargs
; i
++)
370 expr
->ops
.phi
.args
[i
] = gimple_phi_arg_def (stmt
, i
);
376 element
->stmt
= stmt
;
377 element
->hash
= avail_expr_hash (element
);
378 element
->stamp
= element
;
381 /* Given a conditional expression COND as a tree, initialize
382 a hashable_expr expression EXPR. The conditional must be a
383 comparison or logical negation. A constant or a variable is
387 initialize_expr_from_cond (tree cond
, struct hashable_expr
*expr
)
389 expr
->type
= boolean_type_node
;
391 if (COMPARISON_CLASS_P (cond
))
393 expr
->kind
= EXPR_BINARY
;
394 expr
->ops
.binary
.op
= TREE_CODE (cond
);
395 expr
->ops
.binary
.opnd0
= TREE_OPERAND (cond
, 0);
396 expr
->ops
.binary
.opnd1
= TREE_OPERAND (cond
, 1);
398 else if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
400 expr
->kind
= EXPR_UNARY
;
401 expr
->ops
.unary
.op
= TRUTH_NOT_EXPR
;
402 expr
->ops
.unary
.opnd
= TREE_OPERAND (cond
, 0);
408 /* Given a hashable_expr expression EXPR and an LHS,
409 initialize the hash table element pointed to by ELEMENT. */
412 initialize_hash_element_from_expr (struct hashable_expr
*expr
,
414 struct expr_hash_elt
*element
)
416 element
->expr
= *expr
;
418 element
->stmt
= NULL
;
419 element
->hash
= avail_expr_hash (element
);
420 element
->stamp
= element
;
423 /* Compare two hashable_expr structures for equivalence.
424 They are considered equivalent when the the expressions
425 they denote must necessarily be equal. The logic is intended
426 to follow that of operand_equal_p in fold-const.c */
429 hashable_expr_equal_p (const struct hashable_expr
*expr0
,
430 const struct hashable_expr
*expr1
)
432 tree type0
= expr0
->type
;
433 tree type1
= expr1
->type
;
435 /* If either type is NULL, there is nothing to check. */
436 if ((type0
== NULL_TREE
) ^ (type1
== NULL_TREE
))
439 /* If both types don't have the same signedness, precision, and mode,
440 then we can't consider them equal. */
442 && (TREE_CODE (type0
) == ERROR_MARK
443 || TREE_CODE (type1
) == ERROR_MARK
444 || TYPE_UNSIGNED (type0
) != TYPE_UNSIGNED (type1
)
445 || TYPE_PRECISION (type0
) != TYPE_PRECISION (type1
)
446 || TYPE_MODE (type0
) != TYPE_MODE (type1
)))
449 if (expr0
->kind
!= expr1
->kind
)
455 return operand_equal_p (expr0
->ops
.single
.rhs
,
456 expr1
->ops
.single
.rhs
, 0);
459 if (expr0
->ops
.unary
.op
!= expr1
->ops
.unary
.op
)
462 if ((CONVERT_EXPR_CODE_P (expr0
->ops
.unary
.op
)
463 || expr0
->ops
.unary
.op
== NON_LVALUE_EXPR
)
464 && TYPE_UNSIGNED (expr0
->type
) != TYPE_UNSIGNED (expr1
->type
))
467 return operand_equal_p (expr0
->ops
.unary
.opnd
,
468 expr1
->ops
.unary
.opnd
, 0);
471 if (expr0
->ops
.binary
.op
!= expr1
->ops
.binary
.op
)
474 if (operand_equal_p (expr0
->ops
.binary
.opnd0
,
475 expr1
->ops
.binary
.opnd0
, 0)
476 && operand_equal_p (expr0
->ops
.binary
.opnd1
,
477 expr1
->ops
.binary
.opnd1
, 0))
480 /* For commutative ops, allow the other order. */
481 return (commutative_tree_code (expr0
->ops
.binary
.op
)
482 && operand_equal_p (expr0
->ops
.binary
.opnd0
,
483 expr1
->ops
.binary
.opnd1
, 0)
484 && operand_equal_p (expr0
->ops
.binary
.opnd1
,
485 expr1
->ops
.binary
.opnd0
, 0));
488 if (expr0
->ops
.ternary
.op
!= expr1
->ops
.ternary
.op
489 || !operand_equal_p (expr0
->ops
.ternary
.opnd2
,
490 expr1
->ops
.ternary
.opnd2
, 0))
493 if (operand_equal_p (expr0
->ops
.ternary
.opnd0
,
494 expr1
->ops
.ternary
.opnd0
, 0)
495 && operand_equal_p (expr0
->ops
.ternary
.opnd1
,
496 expr1
->ops
.ternary
.opnd1
, 0))
499 /* For commutative ops, allow the other order. */
500 return (commutative_ternary_tree_code (expr0
->ops
.ternary
.op
)
501 && operand_equal_p (expr0
->ops
.ternary
.opnd0
,
502 expr1
->ops
.ternary
.opnd1
, 0)
503 && operand_equal_p (expr0
->ops
.ternary
.opnd1
,
504 expr1
->ops
.ternary
.opnd0
, 0));
510 /* If the calls are to different functions, then they
511 clearly cannot be equal. */
512 if (!gimple_call_same_target_p (expr0
->ops
.call
.fn_from
,
513 expr1
->ops
.call
.fn_from
))
516 if (! expr0
->ops
.call
.pure
)
519 if (expr0
->ops
.call
.nargs
!= expr1
->ops
.call
.nargs
)
522 for (i
= 0; i
< expr0
->ops
.call
.nargs
; i
++)
523 if (! operand_equal_p (expr0
->ops
.call
.args
[i
],
524 expr1
->ops
.call
.args
[i
], 0))
527 if (stmt_could_throw_p (expr0
->ops
.call
.fn_from
))
529 int lp0
= lookup_stmt_eh_lp (expr0
->ops
.call
.fn_from
);
530 int lp1
= lookup_stmt_eh_lp (expr1
->ops
.call
.fn_from
);
531 if ((lp0
> 0 || lp1
> 0) && lp0
!= lp1
)
542 if (expr0
->ops
.phi
.nargs
!= expr1
->ops
.phi
.nargs
)
545 for (i
= 0; i
< expr0
->ops
.phi
.nargs
; i
++)
546 if (! operand_equal_p (expr0
->ops
.phi
.args
[i
],
547 expr1
->ops
.phi
.args
[i
], 0))
558 /* Generate a hash value for a pair of expressions. This can be used
559 iteratively by passing a previous result as the VAL argument.
561 The same hash value is always returned for a given pair of expressions,
562 regardless of the order in which they are presented. This is useful in
563 hashing the operands of commutative functions. */
566 iterative_hash_exprs_commutative (const_tree t1
,
567 const_tree t2
, hashval_t val
)
569 hashval_t one
= iterative_hash_expr (t1
, 0);
570 hashval_t two
= iterative_hash_expr (t2
, 0);
574 t
= one
, one
= two
, two
= t
;
575 val
= iterative_hash_hashval_t (one
, val
);
576 val
= iterative_hash_hashval_t (two
, val
);
581 /* Compute a hash value for a hashable_expr value EXPR and a
582 previously accumulated hash value VAL. If two hashable_expr
583 values compare equal with hashable_expr_equal_p, they must
584 hash to the same value, given an identical value of VAL.
585 The logic is intended to follow iterative_hash_expr in tree.c. */
588 iterative_hash_hashable_expr (const struct hashable_expr
*expr
, hashval_t val
)
593 val
= iterative_hash_expr (expr
->ops
.single
.rhs
, val
);
597 val
= iterative_hash_object (expr
->ops
.unary
.op
, val
);
599 /* Make sure to include signedness in the hash computation.
600 Don't hash the type, that can lead to having nodes which
601 compare equal according to operand_equal_p, but which
602 have different hash codes. */
603 if (CONVERT_EXPR_CODE_P (expr
->ops
.unary
.op
)
604 || expr
->ops
.unary
.op
== NON_LVALUE_EXPR
)
605 val
+= TYPE_UNSIGNED (expr
->type
);
607 val
= iterative_hash_expr (expr
->ops
.unary
.opnd
, val
);
611 val
= iterative_hash_object (expr
->ops
.binary
.op
, val
);
612 if (commutative_tree_code (expr
->ops
.binary
.op
))
613 val
= iterative_hash_exprs_commutative (expr
->ops
.binary
.opnd0
,
614 expr
->ops
.binary
.opnd1
, val
);
617 val
= iterative_hash_expr (expr
->ops
.binary
.opnd0
, val
);
618 val
= iterative_hash_expr (expr
->ops
.binary
.opnd1
, val
);
623 val
= iterative_hash_object (expr
->ops
.ternary
.op
, val
);
624 if (commutative_ternary_tree_code (expr
->ops
.ternary
.op
))
625 val
= iterative_hash_exprs_commutative (expr
->ops
.ternary
.opnd0
,
626 expr
->ops
.ternary
.opnd1
, val
);
629 val
= iterative_hash_expr (expr
->ops
.ternary
.opnd0
, val
);
630 val
= iterative_hash_expr (expr
->ops
.ternary
.opnd1
, val
);
632 val
= iterative_hash_expr (expr
->ops
.ternary
.opnd2
, val
);
638 enum tree_code code
= CALL_EXPR
;
641 val
= iterative_hash_object (code
, val
);
642 fn_from
= expr
->ops
.call
.fn_from
;
643 if (gimple_call_internal_p (fn_from
))
644 val
= iterative_hash_hashval_t
645 ((hashval_t
) gimple_call_internal_fn (fn_from
), val
);
647 val
= iterative_hash_expr (gimple_call_fn (fn_from
), val
);
648 for (i
= 0; i
< expr
->ops
.call
.nargs
; i
++)
649 val
= iterative_hash_expr (expr
->ops
.call
.args
[i
], val
);
657 for (i
= 0; i
< expr
->ops
.phi
.nargs
; i
++)
658 val
= iterative_hash_expr (expr
->ops
.phi
.args
[i
], val
);
669 /* Print a diagnostic dump of an expression hash table entry. */
672 print_expr_hash_elt (FILE * stream
, const struct expr_hash_elt
*element
)
675 fprintf (stream
, "STMT ");
677 fprintf (stream
, "COND ");
681 print_generic_expr (stream
, element
->lhs
, 0);
682 fprintf (stream
, " = ");
685 switch (element
->expr
.kind
)
688 print_generic_expr (stream
, element
->expr
.ops
.single
.rhs
, 0);
692 fprintf (stream
, "%s ", get_tree_code_name (element
->expr
.ops
.unary
.op
));
693 print_generic_expr (stream
, element
->expr
.ops
.unary
.opnd
, 0);
697 print_generic_expr (stream
, element
->expr
.ops
.binary
.opnd0
, 0);
698 fprintf (stream
, " %s ", get_tree_code_name (element
->expr
.ops
.binary
.op
));
699 print_generic_expr (stream
, element
->expr
.ops
.binary
.opnd1
, 0);
703 fprintf (stream
, " %s <", get_tree_code_name (element
->expr
.ops
.ternary
.op
));
704 print_generic_expr (stream
, element
->expr
.ops
.ternary
.opnd0
, 0);
705 fputs (", ", stream
);
706 print_generic_expr (stream
, element
->expr
.ops
.ternary
.opnd1
, 0);
707 fputs (", ", stream
);
708 print_generic_expr (stream
, element
->expr
.ops
.ternary
.opnd2
, 0);
715 size_t nargs
= element
->expr
.ops
.call
.nargs
;
718 fn_from
= element
->expr
.ops
.call
.fn_from
;
719 if (gimple_call_internal_p (fn_from
))
720 fputs (internal_fn_name (gimple_call_internal_fn (fn_from
)),
723 print_generic_expr (stream
, gimple_call_fn (fn_from
), 0);
724 fprintf (stream
, " (");
725 for (i
= 0; i
< nargs
; i
++)
727 print_generic_expr (stream
, element
->expr
.ops
.call
.args
[i
], 0);
729 fprintf (stream
, ", ");
731 fprintf (stream
, ")");
738 size_t nargs
= element
->expr
.ops
.phi
.nargs
;
740 fprintf (stream
, "PHI <");
741 for (i
= 0; i
< nargs
; i
++)
743 print_generic_expr (stream
, element
->expr
.ops
.phi
.args
[i
], 0);
745 fprintf (stream
, ", ");
747 fprintf (stream
, ">");
751 fprintf (stream
, "\n");
755 fprintf (stream
, " ");
756 print_gimple_stmt (stream
, element
->stmt
, 0, 0);
760 /* Delete variable sized pieces of the expr_hash_elt ELEMENT. */
763 free_expr_hash_elt_contents (struct expr_hash_elt
*element
)
765 if (element
->expr
.kind
== EXPR_CALL
)
766 free (element
->expr
.ops
.call
.args
);
767 else if (element
->expr
.kind
== EXPR_PHI
)
768 free (element
->expr
.ops
.phi
.args
);
771 /* Delete an expr_hash_elt and reclaim its storage. */
774 free_expr_hash_elt (void *elt
)
776 struct expr_hash_elt
*element
= ((struct expr_hash_elt
*)elt
);
777 free_expr_hash_elt_contents (element
);
781 /* Allocate an EDGE_INFO for edge E and attach it to E.
782 Return the new EDGE_INFO structure. */
784 static struct edge_info
*
785 allocate_edge_info (edge e
)
787 struct edge_info
*edge_info
;
789 edge_info
= XCNEW (struct edge_info
);
795 /* Free all EDGE_INFO structures associated with edges in the CFG.
796 If a particular edge can be threaded, copy the redirection
797 target from the EDGE_INFO structure into the edge's AUX field
798 as required by code to update the CFG and SSA graph for
802 free_all_edge_infos (void)
808 FOR_EACH_BB_FN (bb
, cfun
)
810 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
812 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
816 edge_info
->cond_equivalences
.release ();
824 class dom_opt_dom_walker
: public dom_walker
827 dom_opt_dom_walker (cdi_direction direction
)
828 : dom_walker (direction
), m_dummy_cond (NULL
) {}
830 virtual void before_dom_children (basic_block
);
831 virtual void after_dom_children (basic_block
);
834 void thread_across_edge (edge
);
839 /* Jump threading, redundancy elimination and const/copy propagation.
841 This pass may expose new symbols that need to be renamed into SSA. For
842 every new symbol exposed, its corresponding bit will be set in
847 const pass_data pass_data_dominator
=
849 GIMPLE_PASS
, /* type */
851 OPTGROUP_NONE
, /* optinfo_flags */
852 true, /* has_execute */
853 TV_TREE_SSA_DOMINATOR_OPTS
, /* tv_id */
854 ( PROP_cfg
| PROP_ssa
), /* properties_required */
855 0, /* properties_provided */
856 0, /* properties_destroyed */
857 0, /* todo_flags_start */
858 ( TODO_cleanup_cfg
| TODO_update_ssa
), /* todo_flags_finish */
861 class pass_dominator
: public gimple_opt_pass
864 pass_dominator (gcc::context
*ctxt
)
865 : gimple_opt_pass (pass_data_dominator
, ctxt
)
868 /* opt_pass methods: */
869 opt_pass
* clone () { return new pass_dominator (m_ctxt
); }
870 virtual bool gate (function
*) { return flag_tree_dom
!= 0; }
871 virtual unsigned int execute (function
*);
873 }; // class pass_dominator
876 pass_dominator::execute (function
*fun
)
878 memset (&opt_stats
, 0, sizeof (opt_stats
));
880 /* Create our hash tables. */
881 avail_exprs
= new hash_table
<expr_elt_hasher
> (1024);
882 avail_exprs_stack
.create (20);
883 const_and_copies_stack
.create (20);
884 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
886 calculate_dominance_info (CDI_DOMINATORS
);
889 /* We need to know loop structures in order to avoid destroying them
890 in jump threading. Note that we still can e.g. thread through loop
891 headers to an exit edge, or through loop header to the loop body, assuming
892 that we update the loop info.
894 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due
895 to several overly conservative bail-outs in jump threading, case
896 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is
897 missing. We should improve jump threading in future then
898 LOOPS_HAVE_PREHEADERS won't be needed here. */
899 loop_optimizer_init (LOOPS_HAVE_PREHEADERS
| LOOPS_HAVE_SIMPLE_LATCHES
);
901 /* Initialize the value-handle array. */
902 threadedge_initialize_values ();
904 /* We need accurate information regarding back edges in the CFG
905 for jump threading; this may include back edges that are not part of
907 mark_dfs_back_edges ();
909 /* Recursively walk the dominator tree optimizing statements. */
910 dom_opt_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
913 gimple_stmt_iterator gsi
;
915 FOR_EACH_BB_FN (bb
, fun
)
917 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
918 update_stmt_if_modified (gsi_stmt (gsi
));
922 /* If we exposed any new variables, go ahead and put them into
923 SSA form now, before we handle jump threading. This simplifies
924 interactions between rewriting of _DECL nodes into SSA form
925 and rewriting SSA_NAME nodes into SSA form after block
926 duplication and CFG manipulation. */
927 update_ssa (TODO_update_ssa
);
929 free_all_edge_infos ();
931 /* Thread jumps, creating duplicate blocks as needed. */
932 cfg_altered
|= thread_through_all_blocks (first_pass_instance
);
935 free_dominance_info (CDI_DOMINATORS
);
937 /* Removal of statements may make some EH edges dead. Purge
938 such edges from the CFG as needed. */
939 if (!bitmap_empty_p (need_eh_cleanup
))
944 /* Jump threading may have created forwarder blocks from blocks
945 needing EH cleanup; the new successor of these blocks, which
946 has inherited from the original block, needs the cleanup.
947 Don't clear bits in the bitmap, as that can break the bitmap
949 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup
, 0, i
, bi
)
951 basic_block bb
= BASIC_BLOCK_FOR_FN (fun
, i
);
954 while (single_succ_p (bb
)
955 && (single_succ_edge (bb
)->flags
& EDGE_EH
) == 0)
956 bb
= single_succ (bb
);
957 if (bb
== EXIT_BLOCK_PTR_FOR_FN (fun
))
959 if ((unsigned) bb
->index
!= i
)
960 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
963 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
964 bitmap_clear (need_eh_cleanup
);
967 statistics_counter_event (fun
, "Redundant expressions eliminated",
969 statistics_counter_event (fun
, "Constants propagated",
970 opt_stats
.num_const_prop
);
971 statistics_counter_event (fun
, "Copies propagated",
972 opt_stats
.num_copy_prop
);
974 /* Debugging dumps. */
975 if (dump_file
&& (dump_flags
& TDF_STATS
))
976 dump_dominator_optimization_stats (dump_file
);
978 loop_optimizer_finalize ();
980 /* Delete our main hashtable. */
984 /* Free asserted bitmaps and stacks. */
985 BITMAP_FREE (need_eh_cleanup
);
987 avail_exprs_stack
.release ();
988 const_and_copies_stack
.release ();
990 /* Free the value-handle array. */
991 threadedge_finalize_values ();
999 make_pass_dominator (gcc::context
*ctxt
)
1001 return new pass_dominator (ctxt
);
1005 /* Given a conditional statement CONDSTMT, convert the
1006 condition to a canonical form. */
1009 canonicalize_comparison (gimple condstmt
)
1013 enum tree_code code
;
1015 gcc_assert (gimple_code (condstmt
) == GIMPLE_COND
);
1017 op0
= gimple_cond_lhs (condstmt
);
1018 op1
= gimple_cond_rhs (condstmt
);
1020 code
= gimple_cond_code (condstmt
);
1022 /* If it would be profitable to swap the operands, then do so to
1023 canonicalize the statement, enabling better optimization.
1025 By placing canonicalization of such expressions here we
1026 transparently keep statements in canonical form, even
1027 when the statement is modified. */
1028 if (tree_swap_operands_p (op0
, op1
, false))
1030 /* For relationals we need to swap the operands
1031 and change the code. */
1037 code
= swap_tree_comparison (code
);
1039 gimple_cond_set_code (condstmt
, code
);
1040 gimple_cond_set_lhs (condstmt
, op1
);
1041 gimple_cond_set_rhs (condstmt
, op0
);
1043 update_stmt (condstmt
);
1048 /* Initialize local stacks for this optimizer and record equivalences
1049 upon entry to BB. Equivalences can come from the edge traversed to
1050 reach BB or they may come from PHI nodes at the start of BB. */
1052 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
1053 LIMIT entries left in LOCALs. */
1056 remove_local_expressions_from_table (void)
1058 /* Remove all the expressions made available in this block. */
1059 while (avail_exprs_stack
.length () > 0)
1061 expr_hash_elt_t victim
= avail_exprs_stack
.pop ();
1062 expr_hash_elt
**slot
;
1067 /* This must precede the actual removal from the hash table,
1068 as ELEMENT and the table entry may share a call argument
1069 vector which will be freed during removal. */
1070 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1072 fprintf (dump_file
, "<<<< ");
1073 print_expr_hash_elt (dump_file
, victim
);
1076 slot
= avail_exprs
->find_slot (victim
, NO_INSERT
);
1077 gcc_assert (slot
&& *slot
== victim
);
1078 avail_exprs
->clear_slot (slot
);
1082 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
1083 CONST_AND_COPIES to its original state, stopping when we hit a
1087 restore_vars_to_original_value (void)
1089 while (const_and_copies_stack
.length () > 0)
1091 tree prev_value
, dest
;
1093 dest
= const_and_copies_stack
.pop ();
1098 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1100 fprintf (dump_file
, "<<<< COPY ");
1101 print_generic_expr (dump_file
, dest
, 0);
1102 fprintf (dump_file
, " = ");
1103 print_generic_expr (dump_file
, SSA_NAME_VALUE (dest
), 0);
1104 fprintf (dump_file
, "\n");
1107 prev_value
= const_and_copies_stack
.pop ();
1108 set_ssa_name_value (dest
, prev_value
);
1112 /* A trivial wrapper so that we can present the generic jump
1113 threading code with a simple API for simplifying statements. */
1115 simplify_stmt_for_jump_threading (gimple stmt
,
1116 gimple within_stmt ATTRIBUTE_UNUSED
)
1118 return lookup_avail_expr (stmt
, false);
1121 /* Record into the equivalence tables any equivalences implied by
1122 traversing edge E (which are cached in E->aux).
1124 Callers are responsible for managing the unwinding markers. */
1126 record_temporary_equivalences (edge e
)
1129 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
1131 /* If we have info associated with this edge, record it into
1132 our equivalence tables. */
1135 cond_equivalence
*eq
;
1136 tree lhs
= edge_info
->lhs
;
1137 tree rhs
= edge_info
->rhs
;
1139 /* If we have a simple NAME = VALUE equivalence, record it. */
1140 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1141 record_const_or_copy (lhs
, rhs
);
1143 /* If we have 0 = COND or 1 = COND equivalences, record them
1144 into our expression hash tables. */
1145 for (i
= 0; edge_info
->cond_equivalences
.iterate (i
, &eq
); ++i
)
1150 /* Wrapper for common code to attempt to thread an edge. For example,
1151 it handles lazily building the dummy condition and the bookkeeping
1152 when jump threading is successful. */
1155 dom_opt_dom_walker::thread_across_edge (edge e
)
1159 gimple_build_cond (NE_EXPR
,
1160 integer_zero_node
, integer_zero_node
,
1163 /* Push a marker on both stacks so we can unwind the tables back to their
1165 avail_exprs_stack
.safe_push (NULL
);
1166 const_and_copies_stack
.safe_push (NULL_TREE
);
1168 /* Traversing E may result in equivalences we can utilize. */
1169 record_temporary_equivalences (e
);
1171 /* With all the edge equivalences in the tables, go ahead and attempt
1172 to thread through E->dest. */
1173 ::thread_across_edge (m_dummy_cond
, e
, false,
1174 &const_and_copies_stack
,
1175 simplify_stmt_for_jump_threading
);
1177 /* And restore the various tables to their state before
1178 we threaded this edge.
1180 XXX The code in tree-ssa-threadedge.c will restore the state of
1181 the const_and_copies table. We we just have to restore the expression
1183 remove_local_expressions_from_table ();
1186 /* PHI nodes can create equivalences too.
1188 Ignoring any alternatives which are the same as the result, if
1189 all the alternatives are equal, then the PHI node creates an
1193 record_equivalences_from_phis (basic_block bb
)
1195 gimple_stmt_iterator gsi
;
1197 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1199 gimple phi
= gsi_stmt (gsi
);
1201 tree lhs
= gimple_phi_result (phi
);
1205 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1207 tree t
= gimple_phi_arg_def (phi
, i
);
1209 /* Ignore alternatives which are the same as our LHS. Since
1210 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we
1211 can simply compare pointers. */
1215 /* If we have not processed an alternative yet, then set
1216 RHS to this alternative. */
1219 /* If we have processed an alternative (stored in RHS), then
1220 see if it is equal to this one. If it isn't, then stop
1222 else if (! operand_equal_for_phi_arg_p (rhs
, t
))
1226 /* If we had no interesting alternatives, then all the RHS alternatives
1227 must have been the same as LHS. */
1231 /* If we managed to iterate through each PHI alternative without
1232 breaking out of the loop, then we have a PHI which may create
1233 a useful equivalence. We do not need to record unwind data for
1234 this, since this is a true assignment and not an equivalence
1235 inferred from a comparison. All uses of this ssa name are dominated
1236 by this assignment, so unwinding just costs time and space. */
1237 if (i
== gimple_phi_num_args (phi
)
1238 && may_propagate_copy (lhs
, rhs
)
1239 /* Do not propagate copies if the propagated value is at a deeper loop
1240 depth than the propagatee. Otherwise, this may introduce uses
1241 of loop variant variables outside of their loops and prevent
1242 coalescing opportunities. */
1243 && !(loop_depth_of_name (rhs
) > loop_depth_of_name (lhs
)))
1244 set_ssa_name_value (lhs
, rhs
);
1248 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1249 return that edge. Otherwise return NULL. */
1251 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
1257 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1259 /* A loop back edge can be identified by the destination of
1260 the edge dominating the source of the edge. */
1261 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
1264 /* If we have already seen a non-loop edge, then we must have
1265 multiple incoming non-loop edges and thus we return NULL. */
1269 /* This is the first non-loop incoming edge we have found. Record
1277 /* Record any equivalences created by the incoming edge to BB. If BB
1278 has more than one incoming edge, then no equivalence is created. */
1281 record_equivalences_from_incoming_edge (basic_block bb
)
1285 struct edge_info
*edge_info
;
1287 /* If our parent block ended with a control statement, then we may be
1288 able to record some equivalences based on which outgoing edge from
1289 the parent was followed. */
1290 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1292 e
= single_incoming_edge_ignoring_loop_edges (bb
);
1294 /* If we had a single incoming edge from our parent block, then enter
1295 any data associated with the edge into our tables. */
1296 if (e
&& e
->src
== parent
)
1300 edge_info
= (struct edge_info
*) e
->aux
;
1304 tree lhs
= edge_info
->lhs
;
1305 tree rhs
= edge_info
->rhs
;
1306 cond_equivalence
*eq
;
1309 record_equality (lhs
, rhs
);
1311 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
1312 set via a widening type conversion, then we may be able to record
1313 additional equivalences. */
1315 && TREE_CODE (lhs
) == SSA_NAME
1316 && is_gimple_constant (rhs
)
1317 && TREE_CODE (rhs
) == INTEGER_CST
)
1319 gimple defstmt
= SSA_NAME_DEF_STMT (lhs
);
1322 && is_gimple_assign (defstmt
)
1323 && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (defstmt
)))
1325 tree old_rhs
= gimple_assign_rhs1 (defstmt
);
1327 /* If the conversion widens the original value and
1328 the constant is in the range of the type of OLD_RHS,
1329 then convert the constant and record the equivalence.
1331 Note that int_fits_type_p does not check the precision
1332 if the upper and lower bounds are OK. */
1333 if (INTEGRAL_TYPE_P (TREE_TYPE (old_rhs
))
1334 && (TYPE_PRECISION (TREE_TYPE (lhs
))
1335 > TYPE_PRECISION (TREE_TYPE (old_rhs
)))
1336 && int_fits_type_p (rhs
, TREE_TYPE (old_rhs
)))
1338 tree newval
= fold_convert (TREE_TYPE (old_rhs
), rhs
);
1339 record_equality (old_rhs
, newval
);
1344 for (i
= 0; edge_info
->cond_equivalences
.iterate (i
, &eq
); ++i
)
1350 /* Dump SSA statistics on FILE. */
1353 dump_dominator_optimization_stats (FILE *file
)
1355 fprintf (file
, "Total number of statements: %6ld\n\n",
1356 opt_stats
.num_stmts
);
1357 fprintf (file
, "Exprs considered for dominator optimizations: %6ld\n",
1358 opt_stats
.num_exprs_considered
);
1360 fprintf (file
, "\nHash table statistics:\n");
1362 fprintf (file
, " avail_exprs: ");
1363 htab_statistics (file
, *avail_exprs
);
1367 /* Dump SSA statistics on stderr. */
1370 debug_dominator_optimization_stats (void)
1372 dump_dominator_optimization_stats (stderr
);
1376 /* Dump statistics for the hash table HTAB. */
1379 htab_statistics (FILE *file
, const hash_table
<expr_elt_hasher
> &htab
)
1381 fprintf (file
, "size %ld, %ld elements, %f collision/search ratio\n",
1382 (long) htab
.size (),
1383 (long) htab
.elements (),
1384 htab
.collisions ());
1388 /* Enter condition equivalence into the expression hash table.
1389 This indicates that a conditional expression has a known
1393 record_cond (cond_equivalence
*p
)
1395 struct expr_hash_elt
*element
= XCNEW (struct expr_hash_elt
);
1396 expr_hash_elt
**slot
;
1398 initialize_hash_element_from_expr (&p
->cond
, p
->value
, element
);
1400 slot
= avail_exprs
->find_slot_with_hash (element
, element
->hash
, INSERT
);
1405 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1407 fprintf (dump_file
, "1>>> ");
1408 print_expr_hash_elt (dump_file
, element
);
1411 avail_exprs_stack
.safe_push (element
);
1414 free_expr_hash_elt (element
);
1417 /* Build a cond_equivalence record indicating that the comparison
1418 CODE holds between operands OP0 and OP1 and push it to **P. */
1421 build_and_record_new_cond (enum tree_code code
,
1423 vec
<cond_equivalence
> *p
)
1426 struct hashable_expr
*cond
= &c
.cond
;
1428 gcc_assert (TREE_CODE_CLASS (code
) == tcc_comparison
);
1430 cond
->type
= boolean_type_node
;
1431 cond
->kind
= EXPR_BINARY
;
1432 cond
->ops
.binary
.op
= code
;
1433 cond
->ops
.binary
.opnd0
= op0
;
1434 cond
->ops
.binary
.opnd1
= op1
;
1436 c
.value
= boolean_true_node
;
1440 /* Record that COND is true and INVERTED is false into the edge information
1441 structure. Also record that any conditions dominated by COND are true
1444 For example, if a < b is true, then a <= b must also be true. */
1447 record_conditions (struct edge_info
*edge_info
, tree cond
, tree inverted
)
1452 if (!COMPARISON_CLASS_P (cond
))
1455 op0
= TREE_OPERAND (cond
, 0);
1456 op1
= TREE_OPERAND (cond
, 1);
1458 switch (TREE_CODE (cond
))
1462 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1464 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1465 &edge_info
->cond_equivalences
);
1466 build_and_record_new_cond (LTGT_EXPR
, op0
, op1
,
1467 &edge_info
->cond_equivalences
);
1470 build_and_record_new_cond ((TREE_CODE (cond
) == LT_EXPR
1471 ? LE_EXPR
: GE_EXPR
),
1472 op0
, op1
, &edge_info
->cond_equivalences
);
1473 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1474 &edge_info
->cond_equivalences
);
1479 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1481 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1482 &edge_info
->cond_equivalences
);
1487 if (FLOAT_TYPE_P (TREE_TYPE (op0
)))
1489 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1490 &edge_info
->cond_equivalences
);
1492 build_and_record_new_cond (LE_EXPR
, op0
, op1
,
1493 &edge_info
->cond_equivalences
);
1494 build_and_record_new_cond (GE_EXPR
, op0
, op1
,
1495 &edge_info
->cond_equivalences
);
1498 case UNORDERED_EXPR
:
1499 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1500 &edge_info
->cond_equivalences
);
1501 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1502 &edge_info
->cond_equivalences
);
1503 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1504 &edge_info
->cond_equivalences
);
1505 build_and_record_new_cond (UNEQ_EXPR
, op0
, op1
,
1506 &edge_info
->cond_equivalences
);
1507 build_and_record_new_cond (UNLT_EXPR
, op0
, op1
,
1508 &edge_info
->cond_equivalences
);
1509 build_and_record_new_cond (UNGT_EXPR
, op0
, op1
,
1510 &edge_info
->cond_equivalences
);
1515 build_and_record_new_cond ((TREE_CODE (cond
) == UNLT_EXPR
1516 ? UNLE_EXPR
: UNGE_EXPR
),
1517 op0
, op1
, &edge_info
->cond_equivalences
);
1518 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1519 &edge_info
->cond_equivalences
);
1523 build_and_record_new_cond (UNLE_EXPR
, op0
, op1
,
1524 &edge_info
->cond_equivalences
);
1525 build_and_record_new_cond (UNGE_EXPR
, op0
, op1
,
1526 &edge_info
->cond_equivalences
);
1530 build_and_record_new_cond (NE_EXPR
, op0
, op1
,
1531 &edge_info
->cond_equivalences
);
1532 build_and_record_new_cond (ORDERED_EXPR
, op0
, op1
,
1533 &edge_info
->cond_equivalences
);
1540 /* Now store the original true and false conditions into the first
1542 initialize_expr_from_cond (cond
, &c
.cond
);
1543 c
.value
= boolean_true_node
;
1544 edge_info
->cond_equivalences
.safe_push (c
);
1546 /* It is possible for INVERTED to be the negation of a comparison,
1547 and not a valid RHS or GIMPLE_COND condition. This happens because
1548 invert_truthvalue may return such an expression when asked to invert
1549 a floating-point comparison. These comparisons are not assumed to
1550 obey the trichotomy law. */
1551 initialize_expr_from_cond (inverted
, &c
.cond
);
1552 c
.value
= boolean_false_node
;
1553 edge_info
->cond_equivalences
.safe_push (c
);
1556 /* A helper function for record_const_or_copy and record_equality.
1557 Do the work of recording the value and undo info. */
1560 record_const_or_copy_1 (tree x
, tree y
, tree prev_x
)
1562 set_ssa_name_value (x
, y
);
1564 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1566 fprintf (dump_file
, "0>>> COPY ");
1567 print_generic_expr (dump_file
, x
, 0);
1568 fprintf (dump_file
, " = ");
1569 print_generic_expr (dump_file
, y
, 0);
1570 fprintf (dump_file
, "\n");
1573 const_and_copies_stack
.reserve (2);
1574 const_and_copies_stack
.quick_push (prev_x
);
1575 const_and_copies_stack
.quick_push (x
);
1578 /* Return the loop depth of the basic block of the defining statement of X.
1579 This number should not be treated as absolutely correct because the loop
1580 information may not be completely up-to-date when dom runs. However, it
1581 will be relatively correct, and as more passes are taught to keep loop info
1582 up to date, the result will become more and more accurate. */
1585 loop_depth_of_name (tree x
)
1590 /* If it's not an SSA_NAME, we have no clue where the definition is. */
1591 if (TREE_CODE (x
) != SSA_NAME
)
1594 /* Otherwise return the loop depth of the defining statement's bb.
1595 Note that there may not actually be a bb for this statement, if the
1596 ssa_name is live on entry. */
1597 defstmt
= SSA_NAME_DEF_STMT (x
);
1598 defbb
= gimple_bb (defstmt
);
1602 return bb_loop_depth (defbb
);
1605 /* Record that X is equal to Y in const_and_copies. Record undo
1606 information in the block-local vector. */
1609 record_const_or_copy (tree x
, tree y
)
1611 tree prev_x
= SSA_NAME_VALUE (x
);
1613 gcc_assert (TREE_CODE (x
) == SSA_NAME
);
1615 if (TREE_CODE (y
) == SSA_NAME
)
1617 tree tmp
= SSA_NAME_VALUE (y
);
1622 record_const_or_copy_1 (x
, y
, prev_x
);
1625 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1626 This constrains the cases in which we may treat this as assignment. */
1629 record_equality (tree x
, tree y
)
1631 tree prev_x
= NULL
, prev_y
= NULL
;
1633 if (TREE_CODE (x
) == SSA_NAME
)
1634 prev_x
= SSA_NAME_VALUE (x
);
1635 if (TREE_CODE (y
) == SSA_NAME
)
1636 prev_y
= SSA_NAME_VALUE (y
);
1638 /* If one of the previous values is invariant, or invariant in more loops
1639 (by depth), then use that.
1640 Otherwise it doesn't matter which value we choose, just so
1641 long as we canonicalize on one value. */
1642 if (is_gimple_min_invariant (y
))
1644 else if (is_gimple_min_invariant (x
)
1645 || (loop_depth_of_name (x
) <= loop_depth_of_name (y
)))
1646 prev_x
= x
, x
= y
, y
= prev_x
, prev_x
= prev_y
;
1647 else if (prev_x
&& is_gimple_min_invariant (prev_x
))
1648 x
= y
, y
= prev_x
, prev_x
= prev_y
;
1652 /* After the swapping, we must have one SSA_NAME. */
1653 if (TREE_CODE (x
) != SSA_NAME
)
1656 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1657 variable compared against zero. If we're honoring signed zeros,
1658 then we cannot record this value unless we know that the value is
1660 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x
)))
1661 && (TREE_CODE (y
) != REAL_CST
1662 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (y
))))
1665 record_const_or_copy_1 (x
, y
, prev_x
);
1668 /* Returns true when STMT is a simple iv increment. It detects the
1669 following situation:
1671 i_1 = phi (..., i_2)
1672 i_2 = i_1 +/- ... */
1675 simple_iv_increment_p (gimple stmt
)
1677 enum tree_code code
;
1682 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1685 lhs
= gimple_assign_lhs (stmt
);
1686 if (TREE_CODE (lhs
) != SSA_NAME
)
1689 code
= gimple_assign_rhs_code (stmt
);
1690 if (code
!= PLUS_EXPR
1691 && code
!= MINUS_EXPR
1692 && code
!= POINTER_PLUS_EXPR
)
1695 preinc
= gimple_assign_rhs1 (stmt
);
1696 if (TREE_CODE (preinc
) != SSA_NAME
)
1699 phi
= SSA_NAME_DEF_STMT (preinc
);
1700 if (gimple_code (phi
) != GIMPLE_PHI
)
1703 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
1704 if (gimple_phi_arg_def (phi
, i
) == lhs
)
1710 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
1711 known value for that SSA_NAME (or NULL if no value is known).
1713 Propagate values from CONST_AND_COPIES into the PHI nodes of the
1714 successors of BB. */
1717 cprop_into_successor_phis (basic_block bb
)
1722 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1725 gimple_stmt_iterator gsi
;
1727 /* If this is an abnormal edge, then we do not want to copy propagate
1728 into the PHI alternative associated with this edge. */
1729 if (e
->flags
& EDGE_ABNORMAL
)
1732 gsi
= gsi_start_phis (e
->dest
);
1733 if (gsi_end_p (gsi
))
1736 /* We may have an equivalence associated with this edge. While
1737 we can not propagate it into non-dominated blocks, we can
1738 propagate them into PHIs in non-dominated blocks. */
1740 /* Push the unwind marker so we can reset the const and copies
1741 table back to its original state after processing this edge. */
1742 const_and_copies_stack
.safe_push (NULL_TREE
);
1744 /* Extract and record any simple NAME = VALUE equivalences.
1746 Don't bother with [01] = COND equivalences, they're not useful
1748 struct edge_info
*edge_info
= (struct edge_info
*) e
->aux
;
1751 tree lhs
= edge_info
->lhs
;
1752 tree rhs
= edge_info
->rhs
;
1754 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
1755 record_const_or_copy (lhs
, rhs
);
1759 for ( ; !gsi_end_p (gsi
); gsi_next (&gsi
))
1762 use_operand_p orig_p
;
1764 gimple phi
= gsi_stmt (gsi
);
1766 /* The alternative may be associated with a constant, so verify
1767 it is an SSA_NAME before doing anything with it. */
1768 orig_p
= gimple_phi_arg_imm_use_ptr (phi
, indx
);
1769 orig_val
= get_use_from_ptr (orig_p
);
1770 if (TREE_CODE (orig_val
) != SSA_NAME
)
1773 /* If we have *ORIG_P in our constant/copy table, then replace
1774 ORIG_P with its value in our constant/copy table. */
1775 new_val
= SSA_NAME_VALUE (orig_val
);
1777 && new_val
!= orig_val
1778 && (TREE_CODE (new_val
) == SSA_NAME
1779 || is_gimple_min_invariant (new_val
))
1780 && may_propagate_copy (orig_val
, new_val
))
1781 propagate_value (orig_p
, new_val
);
1784 restore_vars_to_original_value ();
1788 /* We have finished optimizing BB, record any information implied by
1789 taking a specific outgoing edge from BB. */
1792 record_edge_info (basic_block bb
)
1794 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1795 struct edge_info
*edge_info
;
1797 if (! gsi_end_p (gsi
))
1799 gimple stmt
= gsi_stmt (gsi
);
1800 location_t loc
= gimple_location (stmt
);
1802 if (gimple_code (stmt
) == GIMPLE_SWITCH
)
1804 tree index
= gimple_switch_index (stmt
);
1806 if (TREE_CODE (index
) == SSA_NAME
)
1809 int n_labels
= gimple_switch_num_labels (stmt
);
1810 tree
*info
= XCNEWVEC (tree
, last_basic_block_for_fn (cfun
));
1814 for (i
= 0; i
< n_labels
; i
++)
1816 tree label
= gimple_switch_label (stmt
, i
);
1817 basic_block target_bb
= label_to_block (CASE_LABEL (label
));
1818 if (CASE_HIGH (label
)
1819 || !CASE_LOW (label
)
1820 || info
[target_bb
->index
])
1821 info
[target_bb
->index
] = error_mark_node
;
1823 info
[target_bb
->index
] = label
;
1826 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1828 basic_block target_bb
= e
->dest
;
1829 tree label
= info
[target_bb
->index
];
1831 if (label
!= NULL
&& label
!= error_mark_node
)
1833 tree x
= fold_convert_loc (loc
, TREE_TYPE (index
),
1835 edge_info
= allocate_edge_info (e
);
1836 edge_info
->lhs
= index
;
1844 /* A COND_EXPR may create equivalences too. */
1845 if (gimple_code (stmt
) == GIMPLE_COND
)
1850 tree op0
= gimple_cond_lhs (stmt
);
1851 tree op1
= gimple_cond_rhs (stmt
);
1852 enum tree_code code
= gimple_cond_code (stmt
);
1854 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
1856 /* Special case comparing booleans against a constant as we
1857 know the value of OP0 on both arms of the branch. i.e., we
1858 can record an equivalence for OP0 rather than COND. */
1859 if ((code
== EQ_EXPR
|| code
== NE_EXPR
)
1860 && TREE_CODE (op0
) == SSA_NAME
1861 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
1862 && is_gimple_min_invariant (op1
))
1864 if (code
== EQ_EXPR
)
1866 edge_info
= allocate_edge_info (true_edge
);
1867 edge_info
->lhs
= op0
;
1868 edge_info
->rhs
= (integer_zerop (op1
)
1869 ? boolean_false_node
1870 : boolean_true_node
);
1872 edge_info
= allocate_edge_info (false_edge
);
1873 edge_info
->lhs
= op0
;
1874 edge_info
->rhs
= (integer_zerop (op1
)
1876 : boolean_false_node
);
1880 edge_info
= allocate_edge_info (true_edge
);
1881 edge_info
->lhs
= op0
;
1882 edge_info
->rhs
= (integer_zerop (op1
)
1884 : boolean_false_node
);
1886 edge_info
= allocate_edge_info (false_edge
);
1887 edge_info
->lhs
= op0
;
1888 edge_info
->rhs
= (integer_zerop (op1
)
1889 ? boolean_false_node
1890 : boolean_true_node
);
1893 else if (is_gimple_min_invariant (op0
)
1894 && (TREE_CODE (op1
) == SSA_NAME
1895 || is_gimple_min_invariant (op1
)))
1897 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
1898 tree inverted
= invert_truthvalue_loc (loc
, cond
);
1899 bool can_infer_simple_equiv
1900 = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0
)))
1901 && real_zerop (op0
));
1902 struct edge_info
*edge_info
;
1904 edge_info
= allocate_edge_info (true_edge
);
1905 record_conditions (edge_info
, cond
, inverted
);
1907 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
1909 edge_info
->lhs
= op1
;
1910 edge_info
->rhs
= op0
;
1913 edge_info
= allocate_edge_info (false_edge
);
1914 record_conditions (edge_info
, inverted
, cond
);
1916 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
1918 edge_info
->lhs
= op1
;
1919 edge_info
->rhs
= op0
;
1923 else if (TREE_CODE (op0
) == SSA_NAME
1924 && (TREE_CODE (op1
) == SSA_NAME
1925 || is_gimple_min_invariant (op1
)))
1927 tree cond
= build2 (code
, boolean_type_node
, op0
, op1
);
1928 tree inverted
= invert_truthvalue_loc (loc
, cond
);
1929 bool can_infer_simple_equiv
1930 = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op1
)))
1931 && (TREE_CODE (op1
) == SSA_NAME
|| real_zerop (op1
)));
1932 struct edge_info
*edge_info
;
1934 edge_info
= allocate_edge_info (true_edge
);
1935 record_conditions (edge_info
, cond
, inverted
);
1937 if (can_infer_simple_equiv
&& code
== EQ_EXPR
)
1939 edge_info
->lhs
= op0
;
1940 edge_info
->rhs
= op1
;
1943 edge_info
= allocate_edge_info (false_edge
);
1944 record_conditions (edge_info
, inverted
, cond
);
1946 if (can_infer_simple_equiv
&& TREE_CODE (inverted
) == EQ_EXPR
)
1948 edge_info
->lhs
= op0
;
1949 edge_info
->rhs
= op1
;
1954 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
1959 dom_opt_dom_walker::before_dom_children (basic_block bb
)
1961 gimple_stmt_iterator gsi
;
1963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1964 fprintf (dump_file
, "\n\nOptimizing block #%d\n\n", bb
->index
);
1966 /* Push a marker on the stacks of local information so that we know how
1967 far to unwind when we finalize this block. */
1968 avail_exprs_stack
.safe_push (NULL
);
1969 const_and_copies_stack
.safe_push (NULL_TREE
);
1971 record_equivalences_from_incoming_edge (bb
);
1973 /* PHI nodes can create equivalences too. */
1974 record_equivalences_from_phis (bb
);
1976 /* Create equivalences from redundant PHIs. PHIs are only truly
1977 redundant when they exist in the same block, so push another
1978 marker and unwind right afterwards. */
1979 avail_exprs_stack
.safe_push (NULL
);
1980 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1981 eliminate_redundant_computations (&gsi
);
1982 remove_local_expressions_from_table ();
1984 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1985 optimize_stmt (bb
, gsi
);
1987 /* Now prepare to process dominated blocks. */
1988 record_edge_info (bb
);
1989 cprop_into_successor_phis (bb
);
1992 /* We have finished processing the dominator children of BB, perform
1993 any finalization actions in preparation for leaving this node in
1994 the dominator tree. */
1997 dom_opt_dom_walker::after_dom_children (basic_block bb
)
2001 /* If we have an outgoing edge to a block with multiple incoming and
2002 outgoing edges, then we may be able to thread the edge, i.e., we
2003 may be able to statically determine which of the outgoing edges
2004 will be traversed when the incoming edge from BB is traversed. */
2005 if (single_succ_p (bb
)
2006 && (single_succ_edge (bb
)->flags
& EDGE_ABNORMAL
) == 0
2007 && potentially_threadable_block (single_succ (bb
)))
2009 thread_across_edge (single_succ_edge (bb
));
2011 else if ((last
= last_stmt (bb
))
2012 && gimple_code (last
) == GIMPLE_COND
2013 && EDGE_COUNT (bb
->succs
) == 2
2014 && (EDGE_SUCC (bb
, 0)->flags
& EDGE_ABNORMAL
) == 0
2015 && (EDGE_SUCC (bb
, 1)->flags
& EDGE_ABNORMAL
) == 0)
2017 edge true_edge
, false_edge
;
2019 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
2021 /* Only try to thread the edge if it reaches a target block with
2022 more than one predecessor and more than one successor. */
2023 if (potentially_threadable_block (true_edge
->dest
))
2024 thread_across_edge (true_edge
);
2026 /* Similarly for the ELSE arm. */
2027 if (potentially_threadable_block (false_edge
->dest
))
2028 thread_across_edge (false_edge
);
2032 /* These remove expressions local to BB from the tables. */
2033 remove_local_expressions_from_table ();
2034 restore_vars_to_original_value ();
2037 /* Search for redundant computations in STMT. If any are found, then
2038 replace them with the variable holding the result of the computation.
2040 If safe, record this expression into the available expression hash
2044 eliminate_redundant_computations (gimple_stmt_iterator
* gsi
)
2050 bool assigns_var_p
= false;
2052 gimple stmt
= gsi_stmt (*gsi
);
2054 if (gimple_code (stmt
) == GIMPLE_PHI
)
2055 def
= gimple_phi_result (stmt
);
2057 def
= gimple_get_lhs (stmt
);
2059 /* Certain expressions on the RHS can be optimized away, but can not
2060 themselves be entered into the hash tables. */
2062 || TREE_CODE (def
) != SSA_NAME
2063 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
)
2064 || gimple_vdef (stmt
)
2065 /* Do not record equivalences for increments of ivs. This would create
2066 overlapping live ranges for a very questionable gain. */
2067 || simple_iv_increment_p (stmt
))
2070 /* Check if the expression has been computed before. */
2071 cached_lhs
= lookup_avail_expr (stmt
, insert
);
2073 opt_stats
.num_exprs_considered
++;
2075 /* Get the type of the expression we are trying to optimize. */
2076 if (is_gimple_assign (stmt
))
2078 expr_type
= TREE_TYPE (gimple_assign_lhs (stmt
));
2079 assigns_var_p
= true;
2081 else if (gimple_code (stmt
) == GIMPLE_COND
)
2082 expr_type
= boolean_type_node
;
2083 else if (is_gimple_call (stmt
))
2085 gcc_assert (gimple_call_lhs (stmt
));
2086 expr_type
= TREE_TYPE (gimple_call_lhs (stmt
));
2087 assigns_var_p
= true;
2089 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2090 expr_type
= TREE_TYPE (gimple_switch_index (stmt
));
2091 else if (gimple_code (stmt
) == GIMPLE_PHI
)
2092 /* We can't propagate into a phi, so the logic below doesn't apply.
2093 Instead record an equivalence between the cached LHS and the
2094 PHI result of this statement, provided they are in the same block.
2095 This should be sufficient to kill the redundant phi. */
2097 if (def
&& cached_lhs
)
2098 record_const_or_copy (def
, cached_lhs
);
2107 /* It is safe to ignore types here since we have already done
2108 type checking in the hashing and equality routines. In fact
2109 type checking here merely gets in the way of constant
2110 propagation. Also, make sure that it is safe to propagate
2111 CACHED_LHS into the expression in STMT. */
2112 if ((TREE_CODE (cached_lhs
) != SSA_NAME
2114 || useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
))))
2115 || may_propagate_copy_into_stmt (stmt
, cached_lhs
))
2117 gcc_checking_assert (TREE_CODE (cached_lhs
) == SSA_NAME
2118 || is_gimple_min_invariant (cached_lhs
));
2120 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2122 fprintf (dump_file
, " Replaced redundant expr '");
2123 print_gimple_expr (dump_file
, stmt
, 0, dump_flags
);
2124 fprintf (dump_file
, "' with '");
2125 print_generic_expr (dump_file
, cached_lhs
, dump_flags
);
2126 fprintf (dump_file
, "'\n");
2132 && !useless_type_conversion_p (expr_type
, TREE_TYPE (cached_lhs
)))
2133 cached_lhs
= fold_convert (expr_type
, cached_lhs
);
2135 propagate_tree_value_into_stmt (gsi
, cached_lhs
);
2137 /* Since it is always necessary to mark the result as modified,
2138 perhaps we should move this into propagate_tree_value_into_stmt
2140 gimple_set_modified (gsi_stmt (*gsi
), true);
2144 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either
2145 the available expressions table or the const_and_copies table.
2146 Detect and record those equivalences. */
2147 /* We handle only very simple copy equivalences here. The heavy
2148 lifing is done by eliminate_redundant_computations. */
2151 record_equivalences_from_stmt (gimple stmt
, int may_optimize_p
)
2154 enum tree_code lhs_code
;
2156 gcc_assert (is_gimple_assign (stmt
));
2158 lhs
= gimple_assign_lhs (stmt
);
2159 lhs_code
= TREE_CODE (lhs
);
2161 if (lhs_code
== SSA_NAME
2162 && gimple_assign_single_p (stmt
))
2164 tree rhs
= gimple_assign_rhs1 (stmt
);
2166 /* If the RHS of the assignment is a constant or another variable that
2167 may be propagated, register it in the CONST_AND_COPIES table. We
2168 do not need to record unwind data for this, since this is a true
2169 assignment and not an equivalence inferred from a comparison. All
2170 uses of this ssa name are dominated by this assignment, so unwinding
2171 just costs time and space. */
2173 && (TREE_CODE (rhs
) == SSA_NAME
2174 || is_gimple_min_invariant (rhs
)))
2176 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2178 fprintf (dump_file
, "==== ASGN ");
2179 print_generic_expr (dump_file
, lhs
, 0);
2180 fprintf (dump_file
, " = ");
2181 print_generic_expr (dump_file
, rhs
, 0);
2182 fprintf (dump_file
, "\n");
2185 set_ssa_name_value (lhs
, rhs
);
2189 /* A memory store, even an aliased store, creates a useful
2190 equivalence. By exchanging the LHS and RHS, creating suitable
2191 vops and recording the result in the available expression table,
2192 we may be able to expose more redundant loads. */
2193 if (!gimple_has_volatile_ops (stmt
)
2194 && gimple_references_memory_p (stmt
)
2195 && gimple_assign_single_p (stmt
)
2196 && (TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
2197 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt
)))
2198 && !is_gimple_reg (lhs
))
2200 tree rhs
= gimple_assign_rhs1 (stmt
);
2203 /* Build a new statement with the RHS and LHS exchanged. */
2204 if (TREE_CODE (rhs
) == SSA_NAME
)
2206 /* NOTE tuples. The call to gimple_build_assign below replaced
2207 a call to build_gimple_modify_stmt, which did not set the
2208 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so
2209 may cause an SSA validation failure, as the LHS may be a
2210 default-initialized name and should have no definition. I'm
2211 a bit dubious of this, as the artificial statement that we
2212 generate here may in fact be ill-formed, but it is simply
2213 used as an internal device in this pass, and never becomes
2215 gimple defstmt
= SSA_NAME_DEF_STMT (rhs
);
2216 new_stmt
= gimple_build_assign (rhs
, lhs
);
2217 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
2220 new_stmt
= gimple_build_assign (rhs
, lhs
);
2222 gimple_set_vuse (new_stmt
, gimple_vdef (stmt
));
2224 /* Finally enter the statement into the available expression
2226 lookup_avail_expr (new_stmt
, true);
2230 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2231 CONST_AND_COPIES. */
2234 cprop_operand (gimple stmt
, use_operand_p op_p
)
2237 tree op
= USE_FROM_PTR (op_p
);
2239 /* If the operand has a known constant value or it is known to be a
2240 copy of some other variable, use the value or copy stored in
2241 CONST_AND_COPIES. */
2242 val
= SSA_NAME_VALUE (op
);
2243 if (val
&& val
!= op
)
2245 /* Do not replace hard register operands in asm statements. */
2246 if (gimple_code (stmt
) == GIMPLE_ASM
2247 && !may_propagate_copy_into_asm (op
))
2250 /* Certain operands are not allowed to be copy propagated due
2251 to their interaction with exception handling and some GCC
2253 if (!may_propagate_copy (op
, val
))
2256 /* Do not propagate copies into simple IV increment statements.
2257 See PR23821 for how this can disturb IV analysis. */
2258 if (TREE_CODE (val
) != INTEGER_CST
2259 && simple_iv_increment_p (stmt
))
2263 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2265 fprintf (dump_file
, " Replaced '");
2266 print_generic_expr (dump_file
, op
, dump_flags
);
2267 fprintf (dump_file
, "' with %s '",
2268 (TREE_CODE (val
) != SSA_NAME
? "constant" : "variable"));
2269 print_generic_expr (dump_file
, val
, dump_flags
);
2270 fprintf (dump_file
, "'\n");
2273 if (TREE_CODE (val
) != SSA_NAME
)
2274 opt_stats
.num_const_prop
++;
2276 opt_stats
.num_copy_prop
++;
2278 propagate_value (op_p
, val
);
2280 /* And note that we modified this statement. This is now
2281 safe, even if we changed virtual operands since we will
2282 rescan the statement and rewrite its operands again. */
2283 gimple_set_modified (stmt
, true);
2287 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2288 known value for that SSA_NAME (or NULL if no value is known).
2290 Propagate values from CONST_AND_COPIES into the uses, vuses and
2291 vdef_ops of STMT. */
2294 cprop_into_stmt (gimple stmt
)
2299 FOR_EACH_SSA_USE_OPERAND (op_p
, stmt
, iter
, SSA_OP_USE
)
2300 cprop_operand (stmt
, op_p
);
2303 /* Optimize the statement pointed to by iterator SI.
2305 We try to perform some simplistic global redundancy elimination and
2306 constant propagation:
2308 1- To detect global redundancy, we keep track of expressions that have
2309 been computed in this block and its dominators. If we find that the
2310 same expression is computed more than once, we eliminate repeated
2311 computations by using the target of the first one.
2313 2- Constant values and copy assignments. This is used to do very
2314 simplistic constant and copy propagation. When a constant or copy
2315 assignment is found, we map the value on the RHS of the assignment to
2316 the variable in the LHS in the CONST_AND_COPIES table. */
2319 optimize_stmt (basic_block bb
, gimple_stmt_iterator si
)
2321 gimple stmt
, old_stmt
;
2322 bool may_optimize_p
;
2323 bool modified_p
= false;
2325 old_stmt
= stmt
= gsi_stmt (si
);
2327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2329 fprintf (dump_file
, "Optimizing statement ");
2330 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2333 if (gimple_code (stmt
) == GIMPLE_COND
)
2334 canonicalize_comparison (stmt
);
2336 update_stmt_if_modified (stmt
);
2337 opt_stats
.num_stmts
++;
2339 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
2340 cprop_into_stmt (stmt
);
2342 /* If the statement has been modified with constant replacements,
2343 fold its RHS before checking for redundant computations. */
2344 if (gimple_modified_p (stmt
))
2348 /* Try to fold the statement making sure that STMT is kept
2350 if (fold_stmt (&si
))
2352 stmt
= gsi_stmt (si
);
2353 gimple_set_modified (stmt
, true);
2355 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2357 fprintf (dump_file
, " Folded to: ");
2358 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2362 /* We only need to consider cases that can yield a gimple operand. */
2363 if (gimple_assign_single_p (stmt
))
2364 rhs
= gimple_assign_rhs1 (stmt
);
2365 else if (gimple_code (stmt
) == GIMPLE_GOTO
)
2366 rhs
= gimple_goto_dest (stmt
);
2367 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2368 /* This should never be an ADDR_EXPR. */
2369 rhs
= gimple_switch_index (stmt
);
2371 if (rhs
&& TREE_CODE (rhs
) == ADDR_EXPR
)
2372 recompute_tree_invariant_for_addr_expr (rhs
);
2374 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called,
2375 even if fold_stmt updated the stmt already and thus cleared
2376 gimple_modified_p flag on it. */
2380 /* Check for redundant computations. Do this optimization only
2381 for assignments that have no volatile ops and conditionals. */
2382 may_optimize_p
= (!gimple_has_side_effects (stmt
)
2383 && (is_gimple_assign (stmt
)
2384 || (is_gimple_call (stmt
)
2385 && gimple_call_lhs (stmt
) != NULL_TREE
)
2386 || gimple_code (stmt
) == GIMPLE_COND
2387 || gimple_code (stmt
) == GIMPLE_SWITCH
));
2391 if (gimple_code (stmt
) == GIMPLE_CALL
)
2393 /* Resolve __builtin_constant_p. If it hasn't been
2394 folded to integer_one_node by now, it's fairly
2395 certain that the value simply isn't constant. */
2396 tree callee
= gimple_call_fndecl (stmt
);
2398 && DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
2399 && DECL_FUNCTION_CODE (callee
) == BUILT_IN_CONSTANT_P
)
2401 propagate_tree_value_into_stmt (&si
, integer_zero_node
);
2402 stmt
= gsi_stmt (si
);
2406 update_stmt_if_modified (stmt
);
2407 eliminate_redundant_computations (&si
);
2408 stmt
= gsi_stmt (si
);
2410 /* Perform simple redundant store elimination. */
2411 if (gimple_assign_single_p (stmt
)
2412 && TREE_CODE (gimple_assign_lhs (stmt
)) != SSA_NAME
)
2414 tree lhs
= gimple_assign_lhs (stmt
);
2415 tree rhs
= gimple_assign_rhs1 (stmt
);
2418 if (TREE_CODE (rhs
) == SSA_NAME
)
2420 tree tem
= SSA_NAME_VALUE (rhs
);
2424 /* Build a new statement with the RHS and LHS exchanged. */
2425 if (TREE_CODE (rhs
) == SSA_NAME
)
2427 gimple defstmt
= SSA_NAME_DEF_STMT (rhs
);
2428 new_stmt
= gimple_build_assign (rhs
, lhs
);
2429 SSA_NAME_DEF_STMT (rhs
) = defstmt
;
2432 new_stmt
= gimple_build_assign (rhs
, lhs
);
2433 gimple_set_vuse (new_stmt
, gimple_vuse (stmt
));
2434 cached_lhs
= lookup_avail_expr (new_stmt
, false);
2436 && rhs
== cached_lhs
)
2438 basic_block bb
= gimple_bb (stmt
);
2439 unlink_stmt_vdef (stmt
);
2440 if (gsi_remove (&si
, true))
2442 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2443 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2444 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2446 release_defs (stmt
);
2452 /* Record any additional equivalences created by this statement. */
2453 if (is_gimple_assign (stmt
))
2454 record_equivalences_from_stmt (stmt
, may_optimize_p
);
2456 /* If STMT is a COND_EXPR and it was modified, then we may know
2457 where it goes. If that is the case, then mark the CFG as altered.
2459 This will cause us to later call remove_unreachable_blocks and
2460 cleanup_tree_cfg when it is safe to do so. It is not safe to
2461 clean things up here since removal of edges and such can trigger
2462 the removal of PHI nodes, which in turn can release SSA_NAMEs to
2465 That's all fine and good, except that once SSA_NAMEs are released
2466 to the manager, we must not call create_ssa_name until all references
2467 to released SSA_NAMEs have been eliminated.
2469 All references to the deleted SSA_NAMEs can not be eliminated until
2470 we remove unreachable blocks.
2472 We can not remove unreachable blocks until after we have completed
2473 any queued jump threading.
2475 We can not complete any queued jump threads until we have taken
2476 appropriate variables out of SSA form. Taking variables out of
2477 SSA form can call create_ssa_name and thus we lose.
2479 Ultimately I suspect we're going to need to change the interface
2480 into the SSA_NAME manager. */
2481 if (gimple_modified_p (stmt
) || modified_p
)
2485 update_stmt_if_modified (stmt
);
2487 if (gimple_code (stmt
) == GIMPLE_COND
)
2488 val
= fold_binary_loc (gimple_location (stmt
),
2489 gimple_cond_code (stmt
), boolean_type_node
,
2490 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
2491 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
2492 val
= gimple_switch_index (stmt
);
2494 if (val
&& TREE_CODE (val
) == INTEGER_CST
&& find_taken_edge (bb
, val
))
2497 /* If we simplified a statement in such a way as to be shown that it
2498 cannot trap, update the eh information and the cfg to match. */
2499 if (maybe_clean_or_replace_eh_stmt (old_stmt
, stmt
))
2501 bitmap_set_bit (need_eh_cleanup
, bb
->index
);
2502 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2503 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2508 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.
2509 If found, return its LHS. Otherwise insert STMT in the table and
2512 Also, when an expression is first inserted in the table, it is also
2513 is also added to AVAIL_EXPRS_STACK, so that it can be removed when
2514 we finish processing this block and its children. */
2517 lookup_avail_expr (gimple stmt
, bool insert
)
2519 expr_hash_elt
**slot
;
2522 struct expr_hash_elt element
;
2524 /* Get LHS of phi, assignment, or call; else NULL_TREE. */
2525 if (gimple_code (stmt
) == GIMPLE_PHI
)
2526 lhs
= gimple_phi_result (stmt
);
2528 lhs
= gimple_get_lhs (stmt
);
2530 initialize_hash_element (stmt
, lhs
, &element
);
2532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2534 fprintf (dump_file
, "LKUP ");
2535 print_expr_hash_elt (dump_file
, &element
);
2538 /* Don't bother remembering constant assignments and copy operations.
2539 Constants and copy operations are handled by the constant/copy propagator
2540 in optimize_stmt. */
2541 if (element
.expr
.kind
== EXPR_SINGLE
2542 && (TREE_CODE (element
.expr
.ops
.single
.rhs
) == SSA_NAME
2543 || is_gimple_min_invariant (element
.expr
.ops
.single
.rhs
)))
2546 /* Finally try to find the expression in the main expression hash table. */
2547 slot
= avail_exprs
->find_slot (&element
, (insert
? INSERT
: NO_INSERT
));
2550 free_expr_hash_elt_contents (&element
);
2553 else if (*slot
== NULL
)
2555 struct expr_hash_elt
*element2
= XNEW (struct expr_hash_elt
);
2556 *element2
= element
;
2557 element2
->stamp
= element2
;
2560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2562 fprintf (dump_file
, "2>>> ");
2563 print_expr_hash_elt (dump_file
, element2
);
2566 avail_exprs_stack
.safe_push (element2
);
2570 free_expr_hash_elt_contents (&element
);
2572 /* Extract the LHS of the assignment so that it can be used as the current
2573 definition of another variable. */
2574 lhs
= ((struct expr_hash_elt
*)*slot
)->lhs
;
2576 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then
2577 use the value from the const_and_copies table. */
2578 if (TREE_CODE (lhs
) == SSA_NAME
)
2580 temp
= SSA_NAME_VALUE (lhs
);
2585 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2587 fprintf (dump_file
, "FIND: ");
2588 print_generic_expr (dump_file
, lhs
, 0);
2589 fprintf (dump_file
, "\n");
2595 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number
2596 for expressions using the code of the expression and the SSA numbers of
2600 avail_expr_hash (const void *p
)
2602 gimple stmt
= ((const struct expr_hash_elt
*)p
)->stmt
;
2603 const struct hashable_expr
*expr
= &((const struct expr_hash_elt
*)p
)->expr
;
2607 val
= iterative_hash_hashable_expr (expr
, val
);
2609 /* If the hash table entry is not associated with a statement, then we
2610 can just hash the expression and not worry about virtual operands
2615 /* Add the SSA version numbers of the vuse operand. This is important
2616 because compound variables like arrays are not renamed in the
2617 operands. Rather, the rename is done on the virtual variable
2618 representing all the elements of the array. */
2619 if ((vuse
= gimple_vuse (stmt
)))
2620 val
= iterative_hash_expr (vuse
, val
);
2625 /* PHI-ONLY copy and constant propagation. This pass is meant to clean
2626 up degenerate PHIs created by or exposed by jump threading. */
2628 /* Given a statement STMT, which is either a PHI node or an assignment,
2629 remove it from the IL. */
2632 remove_stmt_or_phi (gimple stmt
)
2634 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
2636 if (gimple_code (stmt
) == GIMPLE_PHI
)
2637 remove_phi_node (&gsi
, true);
2640 gsi_remove (&gsi
, true);
2641 release_defs (stmt
);
2645 /* Given a statement STMT, which is either a PHI node or an assignment,
2646 return the "rhs" of the node, in the case of a non-degenerate
2647 phi, NULL is returned. */
2650 get_rhs_or_phi_arg (gimple stmt
)
2652 if (gimple_code (stmt
) == GIMPLE_PHI
)
2653 return degenerate_phi_result (stmt
);
2654 else if (gimple_assign_single_p (stmt
))
2655 return gimple_assign_rhs1 (stmt
);
2661 /* Given a statement STMT, which is either a PHI node or an assignment,
2662 return the "lhs" of the node. */
2665 get_lhs_or_phi_result (gimple stmt
)
2667 if (gimple_code (stmt
) == GIMPLE_PHI
)
2668 return gimple_phi_result (stmt
);
2669 else if (is_gimple_assign (stmt
))
2670 return gimple_assign_lhs (stmt
);
2675 /* Propagate RHS into all uses of LHS (when possible).
2677 RHS and LHS are derived from STMT, which is passed in solely so
2678 that we can remove it if propagation is successful.
2680 When propagating into a PHI node or into a statement which turns
2681 into a trivial copy or constant initialization, set the
2682 appropriate bit in INTERESTING_NAMEs so that we will visit those
2683 nodes as well in an effort to pick up secondary optimization
2687 propagate_rhs_into_lhs (gimple stmt
, tree lhs
, tree rhs
, bitmap interesting_names
)
2689 /* First verify that propagation is valid and isn't going to move a
2690 loop variant variable outside its loop. */
2691 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
)
2692 && (TREE_CODE (rhs
) != SSA_NAME
2693 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
))
2694 && may_propagate_copy (lhs
, rhs
)
2695 && loop_depth_of_name (lhs
) >= loop_depth_of_name (rhs
))
2697 use_operand_p use_p
;
2698 imm_use_iterator iter
;
2703 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2705 fprintf (dump_file
, " Replacing '");
2706 print_generic_expr (dump_file
, lhs
, dump_flags
);
2707 fprintf (dump_file
, "' with %s '",
2708 (TREE_CODE (rhs
) != SSA_NAME
? "constant" : "variable"));
2709 print_generic_expr (dump_file
, rhs
, dump_flags
);
2710 fprintf (dump_file
, "'\n");
2713 /* Walk over every use of LHS and try to replace the use with RHS.
2714 At this point the only reason why such a propagation would not
2715 be successful would be if the use occurs in an ASM_EXPR. */
2716 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
2718 /* Leave debug stmts alone. If we succeed in propagating
2719 all non-debug uses, we'll drop the DEF, and propagation
2720 into debug stmts will occur then. */
2721 if (gimple_debug_bind_p (use_stmt
))
2724 /* It's not always safe to propagate into an ASM_EXPR. */
2725 if (gimple_code (use_stmt
) == GIMPLE_ASM
2726 && ! may_propagate_copy_into_asm (lhs
))
2732 /* It's not ok to propagate into the definition stmt of RHS.
2734 # prephitmp.12_36 = PHI <g_67.1_6(9)>
2735 g_67.1_6 = prephitmp.12_36;
2737 While this is strictly all dead code we do not want to
2738 deal with this here. */
2739 if (TREE_CODE (rhs
) == SSA_NAME
2740 && SSA_NAME_DEF_STMT (rhs
) == use_stmt
)
2747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2749 fprintf (dump_file
, " Original statement:");
2750 print_gimple_stmt (dump_file
, use_stmt
, 0, dump_flags
);
2753 /* Propagate the RHS into this use of the LHS. */
2754 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2755 propagate_value (use_p
, rhs
);
2757 /* Special cases to avoid useless calls into the folding
2758 routines, operand scanning, etc.
2760 Propagation into a PHI may cause the PHI to become
2761 a degenerate, so mark the PHI as interesting. No other
2762 actions are necessary. */
2763 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
2768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2770 fprintf (dump_file
, " Updated statement:");
2771 print_gimple_stmt (dump_file
, use_stmt
, 0, dump_flags
);
2774 result
= get_lhs_or_phi_result (use_stmt
);
2775 bitmap_set_bit (interesting_names
, SSA_NAME_VERSION (result
));
2779 /* From this point onward we are propagating into a
2780 real statement. Folding may (or may not) be possible,
2781 we may expose new operands, expose dead EH edges,
2783 /* NOTE tuples. In the tuples world, fold_stmt_inplace
2784 cannot fold a call that simplifies to a constant,
2785 because the GIMPLE_CALL must be replaced by a
2786 GIMPLE_ASSIGN, and there is no way to effect such a
2787 transformation in-place. We might want to consider
2788 using the more general fold_stmt here. */
2790 gimple_stmt_iterator gsi
= gsi_for_stmt (use_stmt
);
2791 fold_stmt_inplace (&gsi
);
2794 /* Sometimes propagation can expose new operands to the
2796 update_stmt (use_stmt
);
2799 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2801 fprintf (dump_file
, " Updated statement:");
2802 print_gimple_stmt (dump_file
, use_stmt
, 0, dump_flags
);
2805 /* If we replaced a variable index with a constant, then
2806 we would need to update the invariant flag for ADDR_EXPRs. */
2807 if (gimple_assign_single_p (use_stmt
)
2808 && TREE_CODE (gimple_assign_rhs1 (use_stmt
)) == ADDR_EXPR
)
2809 recompute_tree_invariant_for_addr_expr
2810 (gimple_assign_rhs1 (use_stmt
));
2812 /* If we cleaned up EH information from the statement,
2813 mark its containing block as needing EH cleanups. */
2814 if (maybe_clean_or_replace_eh_stmt (use_stmt
, use_stmt
))
2816 bitmap_set_bit (need_eh_cleanup
, gimple_bb (use_stmt
)->index
);
2817 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2818 fprintf (dump_file
, " Flagged to clear EH edges.\n");
2821 /* Propagation may expose new trivial copy/constant propagation
2823 if (gimple_assign_single_p (use_stmt
)
2824 && TREE_CODE (gimple_assign_lhs (use_stmt
)) == SSA_NAME
2825 && (TREE_CODE (gimple_assign_rhs1 (use_stmt
)) == SSA_NAME
2826 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt
))))
2828 tree result
= get_lhs_or_phi_result (use_stmt
);
2829 bitmap_set_bit (interesting_names
, SSA_NAME_VERSION (result
));
2832 /* Propagation into these nodes may make certain edges in
2833 the CFG unexecutable. We want to identify them as PHI nodes
2834 at the destination of those unexecutable edges may become
2836 else if (gimple_code (use_stmt
) == GIMPLE_COND
2837 || gimple_code (use_stmt
) == GIMPLE_SWITCH
2838 || gimple_code (use_stmt
) == GIMPLE_GOTO
)
2842 if (gimple_code (use_stmt
) == GIMPLE_COND
)
2843 val
= fold_binary_loc (gimple_location (use_stmt
),
2844 gimple_cond_code (use_stmt
),
2846 gimple_cond_lhs (use_stmt
),
2847 gimple_cond_rhs (use_stmt
));
2848 else if (gimple_code (use_stmt
) == GIMPLE_SWITCH
)
2849 val
= gimple_switch_index (use_stmt
);
2851 val
= gimple_goto_dest (use_stmt
);
2853 if (val
&& is_gimple_min_invariant (val
))
2855 basic_block bb
= gimple_bb (use_stmt
);
2856 edge te
= find_taken_edge (bb
, val
);
2859 gimple_stmt_iterator gsi
, psi
;
2861 /* Remove all outgoing edges except TE. */
2862 for (ei
= ei_start (bb
->succs
); (e
= ei_safe_edge (ei
));)
2866 /* Mark all the PHI nodes at the destination of
2867 the unexecutable edge as interesting. */
2868 for (psi
= gsi_start_phis (e
->dest
);
2872 gimple phi
= gsi_stmt (psi
);
2874 tree result
= gimple_phi_result (phi
);
2875 int version
= SSA_NAME_VERSION (result
);
2877 bitmap_set_bit (interesting_names
, version
);
2880 te
->probability
+= e
->probability
;
2882 te
->count
+= e
->count
;
2890 gsi
= gsi_last_bb (gimple_bb (use_stmt
));
2891 gsi_remove (&gsi
, true);
2893 /* And fixup the flags on the single remaining edge. */
2894 te
->flags
&= ~(EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
);
2895 te
->flags
&= ~EDGE_ABNORMAL
;
2896 te
->flags
|= EDGE_FALLTHRU
;
2897 if (te
->probability
> REG_BR_PROB_BASE
)
2898 te
->probability
= REG_BR_PROB_BASE
;
2903 /* Ensure there is nothing else to do. */
2904 gcc_assert (!all
|| has_zero_uses (lhs
));
2906 /* If we were able to propagate away all uses of LHS, then
2907 we can remove STMT. */
2909 remove_stmt_or_phi (stmt
);
2913 /* STMT is either a PHI node (potentially a degenerate PHI node) or
2914 a statement that is a trivial copy or constant initialization.
2916 Attempt to eliminate T by propagating its RHS into all uses of
2917 its LHS. This may in turn set new bits in INTERESTING_NAMES
2918 for nodes we want to revisit later.
2920 All exit paths should clear INTERESTING_NAMES for the result
2924 eliminate_const_or_copy (gimple stmt
, bitmap interesting_names
)
2926 tree lhs
= get_lhs_or_phi_result (stmt
);
2928 int version
= SSA_NAME_VERSION (lhs
);
2930 /* If the LHS of this statement or PHI has no uses, then we can
2931 just eliminate it. This can occur if, for example, the PHI
2932 was created by block duplication due to threading and its only
2933 use was in the conditional at the end of the block which was
2935 if (has_zero_uses (lhs
))
2937 bitmap_clear_bit (interesting_names
, version
);
2938 remove_stmt_or_phi (stmt
);
2942 /* Get the RHS of the assignment or PHI node if the PHI is a
2944 rhs
= get_rhs_or_phi_arg (stmt
);
2947 bitmap_clear_bit (interesting_names
, version
);
2951 if (!virtual_operand_p (lhs
))
2952 propagate_rhs_into_lhs (stmt
, lhs
, rhs
, interesting_names
);
2956 imm_use_iterator iter
;
2957 use_operand_p use_p
;
2958 /* For virtual operands we have to propagate into all uses as
2959 otherwise we will create overlapping life-ranges. */
2960 FOR_EACH_IMM_USE_STMT (use_stmt
, iter
, lhs
)
2961 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
2962 SET_USE (use_p
, rhs
);
2963 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
2964 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs
) = 1;
2965 remove_stmt_or_phi (stmt
);
2968 /* Note that STMT may well have been deleted by now, so do
2969 not access it, instead use the saved version # to clear
2970 T's entry in the worklist. */
2971 bitmap_clear_bit (interesting_names
, version
);
2974 /* The first phase in degenerate PHI elimination.
2976 Eliminate the degenerate PHIs in BB, then recurse on the
2977 dominator children of BB. */
2980 eliminate_degenerate_phis_1 (basic_block bb
, bitmap interesting_names
)
2982 gimple_stmt_iterator gsi
;
2985 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2987 gimple phi
= gsi_stmt (gsi
);
2989 eliminate_const_or_copy (phi
, interesting_names
);
2992 /* Recurse into the dominator children of BB. */
2993 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
2995 son
= next_dom_son (CDI_DOMINATORS
, son
))
2996 eliminate_degenerate_phis_1 (son
, interesting_names
);
3000 /* A very simple pass to eliminate degenerate PHI nodes from the
3001 IL. This is meant to be fast enough to be able to be run several
3002 times in the optimization pipeline.
3004 Certain optimizations, particularly those which duplicate blocks
3005 or remove edges from the CFG can create or expose PHIs which are
3006 trivial copies or constant initializations.
3008 While we could pick up these optimizations in DOM or with the
3009 combination of copy-prop and CCP, those solutions are far too
3010 heavy-weight for our needs.
3012 This implementation has two phases so that we can efficiently
3013 eliminate the first order degenerate PHIs and second order
3016 The first phase performs a dominator walk to identify and eliminate
3017 the vast majority of the degenerate PHIs. When a degenerate PHI
3018 is identified and eliminated any affected statements or PHIs
3019 are put on a worklist.
3021 The second phase eliminates degenerate PHIs and trivial copies
3022 or constant initializations using the worklist. This is how we
3023 pick up the secondary optimization opportunities with minimal
3028 const pass_data pass_data_phi_only_cprop
=
3030 GIMPLE_PASS
, /* type */
3031 "phicprop", /* name */
3032 OPTGROUP_NONE
, /* optinfo_flags */
3033 true, /* has_execute */
3034 TV_TREE_PHI_CPROP
, /* tv_id */
3035 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3036 0, /* properties_provided */
3037 0, /* properties_destroyed */
3038 0, /* todo_flags_start */
3039 ( TODO_cleanup_cfg
| TODO_update_ssa
), /* todo_flags_finish */
3042 class pass_phi_only_cprop
: public gimple_opt_pass
3045 pass_phi_only_cprop (gcc::context
*ctxt
)
3046 : gimple_opt_pass (pass_data_phi_only_cprop
, ctxt
)
3049 /* opt_pass methods: */
3050 opt_pass
* clone () { return new pass_phi_only_cprop (m_ctxt
); }
3051 virtual bool gate (function
*) { return flag_tree_dom
!= 0; }
3052 virtual unsigned int execute (function
*);
3054 }; // class pass_phi_only_cprop
3057 pass_phi_only_cprop::execute (function
*fun
)
3059 bitmap interesting_names
;
3060 bitmap interesting_names1
;
3062 /* Bitmap of blocks which need EH information updated. We can not
3063 update it on-the-fly as doing so invalidates the dominator tree. */
3064 need_eh_cleanup
= BITMAP_ALLOC (NULL
);
3066 /* INTERESTING_NAMES is effectively our worklist, indexed by
3069 A set bit indicates that the statement or PHI node which
3070 defines the SSA_NAME should be (re)examined to determine if
3071 it has become a degenerate PHI or trivial const/copy propagation
3074 Experiments have show we generally get better compilation
3075 time behavior with bitmaps rather than sbitmaps. */
3076 interesting_names
= BITMAP_ALLOC (NULL
);
3077 interesting_names1
= BITMAP_ALLOC (NULL
);
3079 calculate_dominance_info (CDI_DOMINATORS
);
3080 cfg_altered
= false;
3082 /* First phase. Eliminate degenerate PHIs via a dominator
3085 Experiments have indicated that we generally get better
3086 compile-time behavior by visiting blocks in the first
3087 phase in dominator order. Presumably this is because walking
3088 in dominator order leaves fewer PHIs for later examination
3089 by the worklist phase. */
3090 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (fun
),
3093 /* Second phase. Eliminate second order degenerate PHIs as well
3094 as trivial copies or constant initializations identified by
3095 the first phase or this phase. Basically we keep iterating
3096 until our set of INTERESTING_NAMEs is empty. */
3097 while (!bitmap_empty_p (interesting_names
))
3102 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
3103 changed during the loop. Copy it to another bitmap and
3105 bitmap_copy (interesting_names1
, interesting_names
);
3107 EXECUTE_IF_SET_IN_BITMAP (interesting_names1
, 0, i
, bi
)
3109 tree name
= ssa_name (i
);
3111 /* Ignore SSA_NAMEs that have been released because
3112 their defining statement was deleted (unreachable). */
3114 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i
)),
3121 free_dominance_info (CDI_DOMINATORS
);
3122 /* If we changed the CFG schedule loops for fixup by cfgcleanup. */
3123 loops_state_set (LOOPS_NEED_FIXUP
);
3126 /* Propagation of const and copies may make some EH edges dead. Purge
3127 such edges from the CFG as needed. */
3128 if (!bitmap_empty_p (need_eh_cleanup
))
3130 gimple_purge_all_dead_eh_edges (need_eh_cleanup
);
3131 BITMAP_FREE (need_eh_cleanup
);
3134 BITMAP_FREE (interesting_names
);
3135 BITMAP_FREE (interesting_names1
);
3142 make_pass_phi_only_cprop (gcc::context
*ctxt
)
3144 return new pass_phi_only_cprop (ctxt
);