1 /* Routines for discovering and unpropagating edge equivalences.
2 Copyright (C) 2005, 2007, 2008, 2010
3 Free Software Foundation, Inc.
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"
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 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
72 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
73 then there is nothing to do. */
77 stmt
= gsi_stmt (gsi
);
82 /* A COND_EXPR may create an equivalency in a variety of different
84 if (gimple_code (stmt
) == GIMPLE_COND
)
88 struct edge_equivalency
*equivalency
;
89 enum tree_code code
= gimple_cond_code (stmt
);
91 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
93 /* Equality tests may create one or two equivalences. */
94 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
96 tree op0
= gimple_cond_lhs (stmt
);
97 tree op1
= gimple_cond_rhs (stmt
);
99 /* Special case comparing booleans against a constant as we
100 know the value of OP0 on both arms of the branch. i.e., we
101 can record an equivalence for OP0 rather than COND. */
102 if (TREE_CODE (op0
) == SSA_NAME
103 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
)
104 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
105 && is_gimple_min_invariant (op1
))
109 equivalency
= XNEW (struct edge_equivalency
);
110 equivalency
->lhs
= op0
;
111 equivalency
->rhs
= (integer_zerop (op1
)
113 : boolean_true_node
);
114 true_edge
->aux
= equivalency
;
116 equivalency
= XNEW (struct edge_equivalency
);
117 equivalency
->lhs
= op0
;
118 equivalency
->rhs
= (integer_zerop (op1
)
120 : boolean_false_node
);
121 false_edge
->aux
= equivalency
;
125 equivalency
= XNEW (struct edge_equivalency
);
126 equivalency
->lhs
= op0
;
127 equivalency
->rhs
= (integer_zerop (op1
)
129 : boolean_false_node
);
130 true_edge
->aux
= equivalency
;
132 equivalency
= XNEW (struct edge_equivalency
);
133 equivalency
->lhs
= op0
;
134 equivalency
->rhs
= (integer_zerop (op1
)
136 : boolean_true_node
);
137 false_edge
->aux
= equivalency
;
141 else if (TREE_CODE (op0
) == SSA_NAME
142 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
)
143 && (is_gimple_min_invariant (op1
)
144 || (TREE_CODE (op1
) == SSA_NAME
145 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1
))))
147 /* For IEEE, -0.0 == 0.0, so we don't necessarily know
148 the sign of a variable compared against zero. If
149 we're honoring signed zeros, then we cannot record
150 this value unless we know that the value is nonzero. */
151 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0
)))
152 && (TREE_CODE (op1
) != REAL_CST
153 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (op1
))))
156 equivalency
= XNEW (struct edge_equivalency
);
157 equivalency
->lhs
= op0
;
158 equivalency
->rhs
= op1
;
160 true_edge
->aux
= equivalency
;
162 false_edge
->aux
= equivalency
;
167 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
170 /* For a SWITCH_EXPR, a case label which represents a single
171 value and which is the only case label which reaches the
172 target block creates an equivalence. */
173 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
175 tree cond
= gimple_switch_index (stmt
);
177 if (TREE_CODE (cond
) == SSA_NAME
178 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond
))
180 int i
, n_labels
= gimple_switch_num_labels (stmt
);
181 tree
*info
= XCNEWVEC (tree
, last_basic_block
);
183 /* Walk over the case label vector. Record blocks
184 which are reached by a single case label which represents
186 for (i
= 0; i
< n_labels
; i
++)
188 tree label
= gimple_switch_label (stmt
, i
);
189 basic_block bb
= label_to_block (CASE_LABEL (label
));
191 if (CASE_HIGH (label
)
194 info
[bb
->index
] = error_mark_node
;
196 info
[bb
->index
] = label
;
199 /* Now walk over the blocks to determine which ones were
200 marked as being reached by a useful case label. */
201 for (i
= 0; i
< n_basic_blocks
; i
++)
206 && node
!= error_mark_node
)
208 tree x
= fold_convert (TREE_TYPE (cond
), CASE_LOW (node
));
209 struct edge_equivalency
*equivalency
;
211 /* Record an equivalency on the edge from BB to basic
213 equivalency
= XNEW (struct edge_equivalency
);
214 equivalency
->rhs
= x
;
215 equivalency
->lhs
= cond
;
216 find_edge (bb
, BASIC_BLOCK (i
))->aux
= equivalency
;
227 /* Translating out of SSA sometimes requires inserting copies and
228 constant initializations on edges to eliminate PHI nodes.
230 In some cases those copies and constant initializations are
231 redundant because the target already has the value on the
232 RHS of the assignment.
234 We previously tried to catch these cases after translating
235 out of SSA form. However, that code often missed cases. Worse
236 yet, the cases it missed were also often missed by the RTL
237 optimizers. Thus the resulting code had redundant instructions.
239 This pass attempts to detect these situations before translating
242 The key concept that this pass is built upon is that these
243 redundant copies and constant initializations often occur
244 due to constant/copy propagating equivalences resulting from
245 COND_EXPRs and SWITCH_EXPRs.
247 We want to do those propagations as they can sometimes allow
248 the SSA optimizers to do a better job. However, in the cases
249 where such propagations do not result in further optimization,
250 we would like to "undo" the propagation to avoid the redundant
251 copies and constant initializations.
253 This pass works by first associating equivalences with edges in
254 the CFG. For example, the edge leading from a SWITCH_EXPR to
255 its associated CASE_LABEL will have an equivalency between
256 SWITCH_COND and the value in the case label.
258 Once we have found the edge equivalences, we proceed to walk
259 the CFG in dominator order. As we traverse edges we record
260 equivalences associated with those edges we traverse.
262 When we encounter a PHI node, we walk its arguments to see if we
263 have an equivalence for the PHI argument. If so, then we replace
266 Equivalences are looked up based on their value (think of it as
267 the RHS of an assignment). A value may be an SSA_NAME or an
268 invariant. We may have several SSA_NAMEs with the same value,
269 so with each value we have a list of SSA_NAMEs that have the
272 /* As we enter each block we record the value for any edge equivalency
273 leading to this block. If no such edge equivalency exists, then we
274 record NULL. These equivalences are live until we leave the dominator
275 subtree rooted at the block where we record the equivalency. */
276 static VEC(tree
,heap
) *equiv_stack
;
278 /* Global hash table implementing a mapping from invariant values
279 to a list of SSA_NAMEs which have the same value. We might be
280 able to reuse tree-vn for this code. */
283 /* Main structure for recording equivalences into our hash table. */
284 struct equiv_hash_elt
286 /* The value/key of this entry. */
289 /* List of SSA_NAMEs which have the same value/key. */
290 VEC(tree
,heap
) *equivalences
;
293 static void uncprop_enter_block (struct dom_walk_data
*, basic_block
);
294 static void uncprop_leave_block (struct dom_walk_data
*, basic_block
);
295 static void uncprop_into_successor_phis (basic_block
);
297 /* Hashing and equality routines for the hash table. */
300 equiv_hash (const void *p
)
302 tree
const value
= ((const struct equiv_hash_elt
*)p
)->value
;
303 return iterative_hash_expr (value
, 0);
307 equiv_eq (const void *p1
, const void *p2
)
309 tree value1
= ((const struct equiv_hash_elt
*)p1
)->value
;
310 tree value2
= ((const struct equiv_hash_elt
*)p2
)->value
;
312 return operand_equal_p (value1
, value2
, 0);
315 /* Free an instance of equiv_hash_elt. */
320 struct equiv_hash_elt
*elt
= (struct equiv_hash_elt
*) p
;
321 VEC_free (tree
, heap
, elt
->equivalences
);
325 /* Remove the most recently recorded equivalency for VALUE. */
328 remove_equivalence (tree value
)
330 struct equiv_hash_elt equiv_hash_elt
, *equiv_hash_elt_p
;
333 equiv_hash_elt
.value
= value
;
334 equiv_hash_elt
.equivalences
= NULL
;
336 slot
= htab_find_slot (equiv
, &equiv_hash_elt
, NO_INSERT
);
338 equiv_hash_elt_p
= (struct equiv_hash_elt
*) *slot
;
339 VEC_pop (tree
, equiv_hash_elt_p
->equivalences
);
342 /* Record EQUIVALENCE = VALUE into our hash table. */
345 record_equiv (tree value
, tree equivalence
)
347 struct equiv_hash_elt
*equiv_hash_elt
;
350 equiv_hash_elt
= XNEW (struct equiv_hash_elt
);
351 equiv_hash_elt
->value
= value
;
352 equiv_hash_elt
->equivalences
= NULL
;
354 slot
= htab_find_slot (equiv
, equiv_hash_elt
, INSERT
);
357 *slot
= (void *) equiv_hash_elt
;
359 free (equiv_hash_elt
);
361 equiv_hash_elt
= (struct equiv_hash_elt
*) *slot
;
363 VEC_safe_push (tree
, heap
, equiv_hash_elt
->equivalences
, equivalence
);
366 /* Main driver for un-cprop. */
369 tree_ssa_uncprop (void)
371 struct dom_walk_data walk_data
;
374 associate_equivalences_with_edges ();
376 /* Create our global data structures. */
377 equiv
= htab_create (1024, equiv_hash
, equiv_eq
, equiv_free
);
378 equiv_stack
= VEC_alloc (tree
, heap
, 2);
380 /* We're going to do a dominator walk, so ensure that we have
381 dominance information. */
382 calculate_dominance_info (CDI_DOMINATORS
);
384 /* Setup callbacks for the generic dominator tree walker. */
385 walk_data
.dom_direction
= CDI_DOMINATORS
;
386 walk_data
.initialize_block_local_data
= NULL
;
387 walk_data
.before_dom_children
= uncprop_enter_block
;
388 walk_data
.after_dom_children
= uncprop_leave_block
;
389 walk_data
.global_data
= NULL
;
390 walk_data
.block_local_data_size
= 0;
392 /* Now initialize the dominator walker. */
393 init_walk_dominator_tree (&walk_data
);
395 /* Recursively walk the dominator tree undoing unprofitable
396 constant/copy propagations. */
397 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
399 /* Finalize and clean up. */
400 fini_walk_dominator_tree (&walk_data
);
402 /* EQUIV_STACK should already be empty at this point, so we just
403 need to empty elements out of the hash table, free EQUIV_STACK,
404 and cleanup the AUX field on the edges. */
406 VEC_free (tree
, heap
, equiv_stack
);
412 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
425 /* We have finished processing the dominator children of BB, perform
426 any finalization actions in preparation for leaving this node in
427 the dominator tree. */
430 uncprop_leave_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
431 basic_block bb ATTRIBUTE_UNUSED
)
433 /* Pop the topmost value off the equiv stack. */
434 tree value
= VEC_pop (tree
, equiv_stack
);
436 /* If that value was non-null, then pop the topmost equivalency off
437 its equivalency stack. */
439 remove_equivalence (value
);
442 /* Unpropagate values from PHI nodes in successor blocks of BB. */
445 uncprop_into_successor_phis (basic_block bb
)
450 /* For each successor edge, first temporarily record any equivalence
451 on that edge. Then unpropagate values in any PHI nodes at the
452 destination of the edge. Then remove the temporary equivalence. */
453 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
455 gimple_seq phis
= phi_nodes (e
->dest
);
456 gimple_stmt_iterator gsi
;
458 /* If there are no PHI nodes in this destination, then there is
459 no sense in recording any equivalences. */
460 if (gimple_seq_empty_p (phis
))
463 /* Record any equivalency associated with E. */
466 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
467 record_equiv (equiv
->rhs
, equiv
->lhs
);
470 /* Walk over the PHI nodes, unpropagating values. */
471 for (gsi
= gsi_start (phis
) ; !gsi_end_p (gsi
); gsi_next (&gsi
))
473 gimple phi
= gsi_stmt (gsi
);
474 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
475 struct equiv_hash_elt equiv_hash_elt
;
478 /* If the argument is not an invariant, or refers to the same
479 underlying variable as the PHI result, then there's no
480 point in un-propagating the argument. */
481 if (!is_gimple_min_invariant (arg
)
482 && SSA_NAME_VAR (arg
) != SSA_NAME_VAR (PHI_RESULT (phi
)))
485 /* Lookup this argument's value in the hash table. */
486 equiv_hash_elt
.value
= arg
;
487 equiv_hash_elt
.equivalences
= NULL
;
488 slot
= htab_find_slot (equiv
, &equiv_hash_elt
, NO_INSERT
);
492 struct equiv_hash_elt
*elt
= (struct equiv_hash_elt
*) *slot
;
495 /* Walk every equivalence with the same value. If we find
496 one with the same underlying variable as the PHI result,
497 then replace the value in the argument with its equivalent
498 SSA_NAME. Use the most recent equivalence as hopefully
499 that results in shortest lifetimes. */
500 for (j
= VEC_length (tree
, elt
->equivalences
) - 1; j
>= 0; j
--)
502 tree equiv
= VEC_index (tree
, elt
->equivalences
, j
);
504 if (SSA_NAME_VAR (equiv
) == SSA_NAME_VAR (PHI_RESULT (phi
)))
506 SET_PHI_ARG_DEF (phi
, e
->dest_idx
, equiv
);
513 /* If we had an equivalence associated with this edge, remove it. */
516 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
517 remove_equivalence (equiv
->rhs
);
522 /* Ignoring loop backedges, if BB has precisely one incoming edge then
523 return that edge. Otherwise return NULL. */
525 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
531 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
533 /* A loop back edge can be identified by the destination of
534 the edge dominating the source of the edge. */
535 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
538 /* If we have already seen a non-loop edge, then we must have
539 multiple incoming non-loop edges and thus we return NULL. */
543 /* This is the first non-loop incoming edge we have found. Record
552 uncprop_enter_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
557 bool recorded
= false;
559 /* If this block is dominated by a single incoming edge and that edge
560 has an equivalency, then record the equivalency and push the
561 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
562 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
565 e
= single_incoming_edge_ignoring_loop_edges (bb
);
567 if (e
&& e
->src
== parent
&& e
->aux
)
569 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
571 record_equiv (equiv
->rhs
, equiv
->lhs
);
572 VEC_safe_push (tree
, heap
, equiv_stack
, equiv
->rhs
);
578 VEC_safe_push (tree
, heap
, equiv_stack
, NULL_TREE
);
580 uncprop_into_successor_phis (bb
);
586 return flag_tree_dom
!= 0;
589 struct gimple_opt_pass pass_uncprop
=
593 "uncprop", /* name */
594 gate_uncprop
, /* gate */
595 tree_ssa_uncprop
, /* execute */
598 0, /* static_pass_number */
599 TV_TREE_SSA_UNCPROP
, /* tv_id */
600 PROP_cfg
| PROP_ssa
, /* properties_required */
601 0, /* properties_provided */
602 0, /* properties_destroyed */
603 0, /* todo_flags_start */
604 TODO_dump_func
| TODO_verify_ssa
/* todo_flags_finish */