1 /* Routines for discovering and unpropagating edge equivalences.
2 Copyright (C) 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to
18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA. */
23 #include "coretypes.h"
30 #include "basic-block.h"
34 #include "diagnostic.h"
36 #include "tree-dump.h"
37 #include "tree-flow.h"
40 #include "tree-pass.h"
41 #include "tree-ssa-propagate.h"
42 #include "langhooks.h"
44 /* The basic structure describing an equivalency created by traversing
45 an edge. Traversing the edge effectively means that we can assume
46 that we've seen an assignment LHS = RHS. */
47 struct edge_equivalency
53 /* This routine finds and records edge equivalences for every edge
56 When complete, each edge that creates an equivalency will have an
57 EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
58 The caller is responsible for freeing the AUX fields. */
61 associate_equivalences_with_edges (void)
65 /* Walk over each block. If the block ends with a control statement,
66 then it might create a useful equivalence. */
69 block_stmt_iterator bsi
= bsi_last (bb
);
72 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
73 then there is nothing to do. */
77 stmt
= bsi_stmt (bsi
);
82 /* A COND_EXPR may create an equivalency in a variety of different
84 if (TREE_CODE (stmt
) == COND_EXPR
)
86 tree cond
= COND_EXPR_COND (stmt
);
89 struct edge_equivalency
*equivalency
;
91 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
93 /* If the conditional is a single variable 'X', record 'X = 1'
94 for the true edge and 'X = 0' on the false edge. */
95 if (TREE_CODE (cond
) == SSA_NAME
)
97 equivalency
= xmalloc (sizeof (struct edge_equivalency
));
98 equivalency
->rhs
= constant_boolean_node (1, TREE_TYPE (cond
));
99 equivalency
->lhs
= cond
;
100 true_edge
->aux
= equivalency
;
102 equivalency
= xmalloc (sizeof (struct edge_equivalency
));
103 equivalency
->rhs
= constant_boolean_node (0, TREE_TYPE (cond
));
104 equivalency
->lhs
= cond
;
105 false_edge
->aux
= equivalency
;
107 /* Equality tests may create one or two equivalences. */
108 else if (TREE_CODE (cond
) == EQ_EXPR
|| TREE_CODE (cond
) == NE_EXPR
)
110 tree op0
= TREE_OPERAND (cond
, 0);
111 tree op1
= TREE_OPERAND (cond
, 1);
113 /* Special case comparing booleans against a constant as we
114 know the value of OP0 on both arms of the branch. i.e., we
115 can record an equivalence for OP0 rather than COND. */
116 if (TREE_CODE (op0
) == SSA_NAME
117 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
118 && is_gimple_min_invariant (op1
))
120 if (TREE_CODE (cond
) == EQ_EXPR
)
122 equivalency
= xmalloc (sizeof (struct edge_equivalency
));
123 equivalency
->lhs
= op0
;
124 equivalency
->rhs
= (integer_zerop (op1
)
126 : boolean_true_node
);
127 true_edge
->aux
= equivalency
;
129 equivalency
= xmalloc (sizeof (struct edge_equivalency
));
130 equivalency
->lhs
= op0
;
131 equivalency
->rhs
= (integer_zerop (op1
)
133 : boolean_false_node
);
134 false_edge
->aux
= equivalency
;
138 equivalency
= xmalloc (sizeof (struct edge_equivalency
));
139 equivalency
->lhs
= op0
;
140 equivalency
->rhs
= (integer_zerop (op1
)
142 : boolean_false_node
);
143 true_edge
->aux
= equivalency
;
145 equivalency
= xmalloc (sizeof (struct edge_equivalency
));
146 equivalency
->lhs
= op0
;
147 equivalency
->rhs
= (integer_zerop (op1
)
149 : boolean_true_node
);
150 false_edge
->aux
= equivalency
;
154 if (TREE_CODE (op0
) == SSA_NAME
155 && (is_gimple_min_invariant (op1
)
156 || TREE_CODE (op1
) == SSA_NAME
))
158 /* For IEEE, -0.0 == 0.0, so we don't necessarily know
159 the sign of a variable compared against zero. If
160 we're honoring signed zeros, then we cannot record
161 this value unless we know that the value is nonzero. */
162 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0
)))
163 && (TREE_CODE (op1
) != REAL_CST
164 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (op1
))))
167 equivalency
= xmalloc (sizeof (struct edge_equivalency
));
168 equivalency
->lhs
= op0
;
169 equivalency
->rhs
= op1
;
170 if (TREE_CODE (cond
) == EQ_EXPR
)
171 true_edge
->aux
= equivalency
;
173 false_edge
->aux
= equivalency
;
178 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
181 /* For a SWITCH_EXPR, a case label which represents a single
182 value and which is the only case label which reaches the
183 target block creates an equivalence. */
184 if (TREE_CODE (stmt
) == SWITCH_EXPR
)
186 tree cond
= SWITCH_COND (stmt
);
188 if (TREE_CODE (cond
) == SSA_NAME
)
190 tree labels
= SWITCH_LABELS (stmt
);
191 int i
, n_labels
= TREE_VEC_LENGTH (labels
);
192 tree
*info
= xcalloc (n_basic_blocks
, sizeof (tree
));
194 /* Walk over the case label vector. Record blocks
195 which are reached by a single case label which represents
197 for (i
= 0; i
< n_labels
; i
++)
199 tree label
= TREE_VEC_ELT (labels
, i
);
200 basic_block bb
= label_to_block (CASE_LABEL (label
));
203 if (CASE_HIGH (label
)
206 info
[bb
->index
] = error_mark_node
;
208 info
[bb
->index
] = label
;
211 /* Now walk over the blocks to determine which ones were
212 marked as being reached by a useful case label. */
213 for (i
= 0; i
< n_basic_blocks
; i
++)
218 && node
!= error_mark_node
)
220 tree x
= fold_convert (TREE_TYPE (cond
), CASE_LOW (node
));
221 struct edge_equivalency
*equivalency
;
223 /* Record an equivalency on the edge from BB to basic
225 equivalency
= xmalloc (sizeof (struct edge_equivalency
));
226 equivalency
->rhs
= x
;
227 equivalency
->lhs
= cond
;
228 find_edge (bb
, BASIC_BLOCK (i
))->aux
= equivalency
;
239 /* Translating out of SSA sometimes requires inserting copies and
240 constant initializations on edges to eliminate PHI nodes.
242 In some cases those copies and constant initializations are
243 redundant because the target already has the value on the
244 RHS of the assignment.
246 We previously tried to catch these cases after translating
247 out of SSA form. However, that code often missed cases. Worse
248 yet, the cases it missed were also often missed by the RTL
249 optimizers. Thus the resulting code had redundant instructions.
251 This pass attempts to detect these situations before translating
254 The key concept that this pass is built upon is that these
255 redundant copies and constant initializations often occur
256 due to constant/copy propagating equivalences resulting from
257 COND_EXPRs and SWITCH_EXPRs.
259 We want to do those propagations as they can sometimes allow
260 the SSA optimizers to do a better job. However, in the cases
261 where such propagations do not result in further optimization,
262 we would like to "undo" the propagation to avoid the redundant
263 copies and constant initializations.
265 This pass works by first associating equivalences with edges in
266 the CFG. For example, the edge leading from a SWITCH_EXPR to
267 its associated CASE_LABEL will have an equivalency between
268 SWITCH_COND and the value in the case label.
270 Once we have found the edge equivalences, we proceed to walk
271 the CFG in dominator order. As we traverse edges we record
272 equivalences associated with those edges we traverse.
274 When we encounter a PHI node, we walk its arguments to see if we
275 have an equivalence for the PHI argument. If so, then we replace
278 Equivalences are looked up based on their value (think of it as
279 the RHS of an assignment). A value may be an SSA_NAME or an
280 invariant. We may have several SSA_NAMEs with the same value,
281 so with each value we have a list of SSA_NAMEs that have the
284 /* As we enter each block we record the value for any edge equivalency
285 leading to this block. If no such edge equivalency exists, then we
286 record NULL. These equivalences are live until we leave the dominator
287 subtree rooted at the block where we record the equivalency. */
288 static VEC(tree
,heap
) *equiv_stack
;
290 /* Global hash table implementing a mapping from invariant values
291 to a list of SSA_NAMEs which have the same value. We might be
292 able to reuse tree-vn for this code. */
295 /* Main structure for recording equivalences into our hash table. */
296 struct equiv_hash_elt
298 /* The value/key of this entry. */
301 /* List of SSA_NAMEs which have the same value/key. */
302 VEC(tree
,heap
) *equivalences
;
305 static void uncprop_initialize_block (struct dom_walk_data
*, basic_block
);
306 static void uncprop_finalize_block (struct dom_walk_data
*, basic_block
);
307 static void uncprop_into_successor_phis (struct dom_walk_data
*, basic_block
);
309 /* Hashing and equality routines for the hash table. */
312 equiv_hash (const void *p
)
314 tree value
= ((struct equiv_hash_elt
*)p
)->value
;
315 return iterative_hash_expr (value
, 0);
319 equiv_eq (const void *p1
, const void *p2
)
321 tree value1
= ((struct equiv_hash_elt
*)p1
)->value
;
322 tree value2
= ((struct equiv_hash_elt
*)p2
)->value
;
324 return operand_equal_p (value1
, value2
, 0);
327 /* Free an instance of equiv_hash_elt. */
332 struct equiv_hash_elt
*elt
= (struct equiv_hash_elt
*) p
;
333 VEC_free (tree
, heap
, elt
->equivalences
);
337 /* Remove the most recently recorded equivalency for VALUE. */
340 remove_equivalence (tree value
)
342 struct equiv_hash_elt equiv_hash_elt
, *equiv_hash_elt_p
;
345 equiv_hash_elt
.value
= value
;
346 equiv_hash_elt
.equivalences
= NULL
;
348 slot
= htab_find_slot (equiv
, &equiv_hash_elt
, NO_INSERT
);
350 equiv_hash_elt_p
= (struct equiv_hash_elt
*) *slot
;
351 VEC_pop (tree
, equiv_hash_elt_p
->equivalences
);
354 /* Record EQUIVALENCE = VALUE into our hash table. */
357 record_equiv (tree value
, tree equivalence
)
359 struct equiv_hash_elt
*equiv_hash_elt
;
362 equiv_hash_elt
= xmalloc (sizeof (struct equiv_hash_elt
));
363 equiv_hash_elt
->value
= value
;
364 equiv_hash_elt
->equivalences
= NULL
;
366 slot
= htab_find_slot (equiv
, equiv_hash_elt
, INSERT
);
369 *slot
= (void *) equiv_hash_elt
;
371 free (equiv_hash_elt
);
373 equiv_hash_elt
= (struct equiv_hash_elt
*) *slot
;
375 VEC_safe_push (tree
, heap
, equiv_hash_elt
->equivalences
, equivalence
);
378 /* Main driver for un-cprop. */
381 tree_ssa_uncprop (void)
383 struct dom_walk_data walk_data
;
386 associate_equivalences_with_edges ();
388 /* Create our global data structures. */
389 equiv
= htab_create (1024, equiv_hash
, equiv_eq
, equiv_free
);
390 equiv_stack
= VEC_alloc (tree
, heap
, 2);
392 /* We're going to do a dominator walk, so ensure that we have
393 dominance information. */
394 calculate_dominance_info (CDI_DOMINATORS
);
396 /* Setup callbacks for the generic dominator tree walker. */
397 walk_data
.walk_stmts_backward
= false;
398 walk_data
.dom_direction
= CDI_DOMINATORS
;
399 walk_data
.initialize_block_local_data
= NULL
;
400 walk_data
.before_dom_children_before_stmts
= uncprop_initialize_block
;
401 walk_data
.before_dom_children_walk_stmts
= NULL
;
402 walk_data
.before_dom_children_after_stmts
= uncprop_into_successor_phis
;
403 walk_data
.after_dom_children_before_stmts
= NULL
;
404 walk_data
.after_dom_children_walk_stmts
= NULL
;
405 walk_data
.after_dom_children_after_stmts
= uncprop_finalize_block
;
406 walk_data
.global_data
= NULL
;
407 walk_data
.block_local_data_size
= 0;
408 walk_data
.interesting_blocks
= NULL
;
410 /* Now initialize the dominator walker. */
411 init_walk_dominator_tree (&walk_data
);
413 /* Recursively walk the dominator tree undoing unprofitable
414 constant/copy propagations. */
415 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
417 /* Finalize and clean up. */
418 fini_walk_dominator_tree (&walk_data
);
420 /* EQUIV_STACK should already be empty at this point, so we just
421 need to empty elements out of the hash table, free EQUIV_STACK,
422 and cleanup the AUX field on the edges. */
424 VEC_free (tree
, heap
, equiv_stack
);
430 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
443 /* We have finished processing the dominator children of BB, perform
444 any finalization actions in preparation for leaving this node in
445 the dominator tree. */
448 uncprop_finalize_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
449 basic_block bb ATTRIBUTE_UNUSED
)
451 /* Pop the topmost value off the equiv stack. */
452 tree value
= VEC_pop (tree
, equiv_stack
);
454 /* If that value was non-null, then pop the topmost equivalency off
455 its equivalency stack. */
457 remove_equivalence (value
);
460 /* Unpropagate values from PHI nodes in successor blocks of BB. */
463 uncprop_into_successor_phis (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
469 /* For each successor edge, first temporarily record any equivalence
470 on that edge. Then unpropagate values in any PHI nodes at the
471 destination of the edge. Then remove the temporary equivalence. */
472 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
474 tree phi
= phi_nodes (e
->dest
);
476 /* If there are no PHI nodes in this destination, then there is
477 no sense in recording any equivalences. */
481 /* Record any equivalency associated with E. */
484 struct edge_equivalency
*equiv
= e
->aux
;
485 record_equiv (equiv
->rhs
, equiv
->lhs
);
488 /* Walk over the PHI nodes, unpropagating values. */
489 for ( ; phi
; phi
= PHI_CHAIN (phi
))
491 /* Sigh. We'll have more efficient access to this one day. */
492 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
493 struct equiv_hash_elt equiv_hash_elt
;
496 /* If the argument is not an invariant, or refers to the same
497 underlying variable as the PHI result, then there's no
498 point in un-propagating the argument. */
499 if (!is_gimple_min_invariant (arg
)
500 && SSA_NAME_VAR (arg
) != SSA_NAME_VAR (PHI_RESULT (phi
)))
503 /* Lookup this argument's value in the hash table. */
504 equiv_hash_elt
.value
= arg
;
505 equiv_hash_elt
.equivalences
= NULL
;
506 slot
= htab_find_slot (equiv
, &equiv_hash_elt
, NO_INSERT
);
510 struct equiv_hash_elt
*elt
= *slot
;
513 /* Walk every equivalence with the same value. If we find
514 one with the same underlying variable as the PHI result,
515 then replace the value in the argument with its equivalent
516 SSA_NAME. Use the most recent equivalence as hopefully
517 that results in shortest lifetimes. */
518 for (j
= VEC_length (tree
, elt
->equivalences
) - 1; j
>= 0; j
--)
520 tree equiv
= VEC_index (tree
, elt
->equivalences
, j
);
522 if (SSA_NAME_VAR (equiv
) == SSA_NAME_VAR (PHI_RESULT (phi
)))
524 SET_PHI_ARG_DEF (phi
, e
->dest_idx
, equiv
);
531 /* If we had an equivalence associated with this edge, remove it. */
534 struct edge_equivalency
*equiv
= e
->aux
;
535 remove_equivalence (equiv
->rhs
);
540 /* Ignoring loop backedges, if BB has precisely one incoming edge then
541 return that edge. Otherwise return NULL. */
543 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
549 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
551 /* A loop back edge can be identified by the destination of
552 the edge dominating the source of the edge. */
553 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
556 /* If we have already seen a non-loop edge, then we must have
557 multiple incoming non-loop edges and thus we return NULL. */
561 /* This is the first non-loop incoming edge we have found. Record
570 uncprop_initialize_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
575 bool recorded
= false;
577 /* If this block is dominated by a single incoming edge and that edge
578 has an equivalency, then record the equivalency and push the
579 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
580 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
583 e
= single_incoming_edge_ignoring_loop_edges (bb
);
585 if (e
&& e
->src
== parent
&& e
->aux
)
587 struct edge_equivalency
*equiv
= e
->aux
;
589 record_equiv (equiv
->rhs
, equiv
->lhs
);
590 VEC_safe_push (tree
, heap
, equiv_stack
, equiv
->rhs
);
596 VEC_safe_push (tree
, heap
, equiv_stack
, NULL_TREE
);
602 return flag_tree_dom
!= 0;
605 struct tree_opt_pass pass_uncprop
=
607 "uncprop", /* name */
608 gate_uncprop
, /* gate */
609 tree_ssa_uncprop
, /* execute */
612 0, /* static_pass_number */
613 TV_TREE_SSA_UNCPROP
, /* tv_id */
614 PROP_cfg
| PROP_ssa
, /* properties_required */
615 0, /* properties_provided */
616 0, /* properties_destroyed */
617 0, /* todo_flags_start */
618 TODO_dump_func
| TODO_verify_ssa
, /* todo_flags_finish */