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, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
30 #include "basic-block.h"
35 #include "diagnostic.h"
37 #include "tree-dump.h"
38 #include "tree-flow.h"
41 #include "tree-pass.h"
42 #include "tree-ssa-propagate.h"
43 #include "langhooks.h"
45 /* The basic structure describing an equivalency created by traversing
46 an edge. Traversing the edge effectively means that we can assume
47 that we've seen an assignment LHS = RHS. */
48 struct edge_equivalency
54 /* This routine finds and records edge equivalences for every edge
57 When complete, each edge that creates an equivalency will have an
58 EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
59 The caller is responsible for freeing the AUX fields. */
62 associate_equivalences_with_edges (void)
66 /* Walk over each block. If the block ends with a control statement,
67 then it might create a useful equivalence. */
70 block_stmt_iterator bsi = bsi_last (bb);
73 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
74 then there is nothing to do. */
78 stmt = bsi_stmt (bsi);
83 /* A COND_EXPR may create an equivalency in a variety of different
85 if (TREE_CODE (stmt) == COND_EXPR)
87 tree cond = COND_EXPR_COND (stmt);
90 struct edge_equivalency *equivalency;
92 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
94 /* If the conditional is a single variable 'X', record 'X = 1'
95 for the true edge and 'X = 0' on the false edge. */
96 if (TREE_CODE (cond) == SSA_NAME)
98 equivalency = xmalloc (sizeof (struct edge_equivalency));
99 equivalency->rhs = constant_boolean_node (1, TREE_TYPE (cond));
100 equivalency->lhs = cond;
101 true_edge->aux = equivalency;
103 equivalency = xmalloc (sizeof (struct edge_equivalency));
104 equivalency->rhs = constant_boolean_node (0, TREE_TYPE (cond));
105 equivalency->lhs = cond;
106 false_edge->aux = equivalency;
108 /* Equality tests may create one or two equivalences. */
109 else if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
111 tree op0 = TREE_OPERAND (cond, 0);
112 tree op1 = TREE_OPERAND (cond, 1);
114 /* Special case comparing booleans against a constant as we
115 know the value of OP0 on both arms of the branch. i.e., we
116 can record an equivalence for OP0 rather than COND. */
117 if (TREE_CODE (op0) == SSA_NAME
118 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
119 && is_gimple_min_invariant (op1))
121 if (TREE_CODE (cond) == EQ_EXPR)
123 equivalency = xmalloc (sizeof (struct edge_equivalency));
124 equivalency->lhs = op0;
125 equivalency->rhs = (integer_zerop (op1)
127 : boolean_true_node);
128 true_edge->aux = equivalency;
130 equivalency = xmalloc (sizeof (struct edge_equivalency));
131 equivalency->lhs = op0;
132 equivalency->rhs = (integer_zerop (op1)
134 : boolean_false_node);
135 false_edge->aux = equivalency;
139 equivalency = xmalloc (sizeof (struct edge_equivalency));
140 equivalency->lhs = op0;
141 equivalency->rhs = (integer_zerop (op1)
143 : boolean_false_node);
144 true_edge->aux = equivalency;
146 equivalency = xmalloc (sizeof (struct edge_equivalency));
147 equivalency->lhs = op0;
148 equivalency->rhs = (integer_zerop (op1)
150 : boolean_true_node);
151 false_edge->aux = equivalency;
155 if (TREE_CODE (op0) == SSA_NAME
156 && (is_gimple_min_invariant (op1)
157 || TREE_CODE (op1) == SSA_NAME))
159 /* For IEEE, -0.0 == 0.0, so we don't necessarily know
160 the sign of a variable compared against zero. If
161 we're honoring signed zeros, then we cannot record
162 this value unless we know that the value is nonzero. */
163 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
164 && (TREE_CODE (op1) != REAL_CST
165 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
168 equivalency = xmalloc (sizeof (struct edge_equivalency));
169 equivalency->lhs = op0;
170 equivalency->rhs = op1;
171 if (TREE_CODE (cond) == EQ_EXPR)
172 true_edge->aux = equivalency;
174 false_edge->aux = equivalency;
179 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
182 /* For a SWITCH_EXPR, a case label which represents a single
183 value and which is the only case label which reaches the
184 target block creates an equivalence. */
185 if (TREE_CODE (stmt) == SWITCH_EXPR)
187 tree cond = SWITCH_COND (stmt);
189 if (TREE_CODE (cond) == SSA_NAME)
191 tree labels = SWITCH_LABELS (stmt);
192 int i, n_labels = TREE_VEC_LENGTH (labels);
193 tree *info = xcalloc (n_basic_blocks, sizeof (tree));
195 /* Walk over the case label vector. Record blocks
196 which are reached by a single case label which represents
198 for (i = 0; i < n_labels; i++)
200 tree label = TREE_VEC_ELT (labels, i);
201 basic_block bb = label_to_block (CASE_LABEL (label));
204 if (CASE_HIGH (label)
207 info[bb->index] = error_mark_node;
209 info[bb->index] = label;
212 /* Now walk over the blocks to determine which ones were
213 marked as being reached by a useful case label. */
214 for (i = 0; i < n_basic_blocks; i++)
219 && node != error_mark_node)
221 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
222 struct edge_equivalency *equivalency;
224 /* Record an equivalency on the edge from BB to basic
226 equivalency = xmalloc (sizeof (struct edge_equivalency));
227 equivalency->rhs = x;
228 equivalency->lhs = cond;
229 find_edge (bb, BASIC_BLOCK (i))->aux = equivalency;
240 /* Translating out of SSA sometimes requires inserting copies and
241 constant initializations on edges to eliminate PHI nodes.
243 In some cases those copies and constant initializations are
244 redundant because the target already has the value on the
245 RHS of the assignment.
247 We previously tried to catch these cases after translating
248 out of SSA form. However, that code often missed cases. Worse
249 yet, the cases it missed were also often missed by the RTL
250 optimizers. Thus the resulting code had redundant instructions.
252 This pass attempts to detect these situations before translating
255 The key concept that this pass is built upon is that these
256 redundant copies and constant initializations often occur
257 due to constant/copy propagating equivalences resulting from
258 COND_EXPRs and SWITCH_EXPRs.
260 We want to do those propagations as they can sometimes allow
261 the SSA optimizers to do a better job. However, in the cases
262 where such propagations do not result in further optimization,
263 we would like to "undo" the propagation to avoid the redundant
264 copies and constant initializations.
266 This pass works by first associating equivalences with edges in
267 the CFG. For example, the edge leading from a SWITCH_EXPR to
268 its associated CASE_LABEL will have an equivalency between
269 SWITCH_COND and the value in the case label.
271 Once we have found the edge equivalences, we proceed to walk
272 the CFG in dominator order. As we traverse edges we record
273 equivalences associated with those edges we traverse.
275 When we encounter a PHI node, we walk its arguments to see if we
276 have an equivalence for the PHI argument. If so, then we replace
279 Equivalences are looked up based on their value (think of it as
280 the RHS of an assignment). A value may be an SSA_NAME or an
281 invariant. We may have several SSA_NAMEs with the same value,
282 so with each value we have a list of SSA_NAMEs that have the
285 /* As we enter each block we record the value for any edge equivalency
286 leading to this block. If no such edge equivalency exists, then we
287 record NULL. These equivalences are live until we leave the dominator
288 subtree rooted at the block where we record the equivalency. */
289 static VEC(tree,heap) *equiv_stack;
291 /* Global hash table implementing a mapping from invariant values
292 to a list of SSA_NAMEs which have the same value. We might be
293 able to reuse tree-vn for this code. */
296 /* Main structure for recording equivalences into our hash table. */
297 struct equiv_hash_elt
299 /* The value/key of this entry. */
302 /* List of SSA_NAMEs which have the same value/key. */
303 VEC(tree,heap) *equivalences;
306 static void uncprop_initialize_block (struct dom_walk_data *, basic_block);
307 static void uncprop_finalize_block (struct dom_walk_data *, basic_block);
308 static void uncprop_into_successor_phis (struct dom_walk_data *, basic_block);
310 /* Hashing and equality routines for the hash table. */
313 equiv_hash (const void *p)
315 tree value = ((struct equiv_hash_elt *)p)->value;
316 return iterative_hash_expr (value, 0);
320 equiv_eq (const void *p1, const void *p2)
322 tree value1 = ((struct equiv_hash_elt *)p1)->value;
323 tree value2 = ((struct equiv_hash_elt *)p2)->value;
325 return operand_equal_p (value1, value2, 0);
328 /* Free an instance of equiv_hash_elt. */
333 struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
334 VEC_free (tree, heap, elt->equivalences);
338 /* Remove the most recently recorded equivalency for VALUE. */
341 remove_equivalence (tree value)
343 struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p;
346 equiv_hash_elt.value = value;
347 equiv_hash_elt.equivalences = NULL;
349 slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
351 equiv_hash_elt_p = (struct equiv_hash_elt *) *slot;
352 VEC_pop (tree, equiv_hash_elt_p->equivalences);
355 /* Record EQUIVALENCE = VALUE into our hash table. */
358 record_equiv (tree value, tree equivalence)
360 struct equiv_hash_elt *equiv_hash_elt;
363 equiv_hash_elt = xmalloc (sizeof (struct equiv_hash_elt));
364 equiv_hash_elt->value = value;
365 equiv_hash_elt->equivalences = NULL;
367 slot = htab_find_slot (equiv, equiv_hash_elt, INSERT);
370 *slot = (void *) equiv_hash_elt;
372 free (equiv_hash_elt);
374 equiv_hash_elt = (struct equiv_hash_elt *) *slot;
376 VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence);
379 /* Main driver for un-cprop. */
382 tree_ssa_uncprop (void)
384 struct dom_walk_data walk_data;
387 associate_equivalences_with_edges ();
389 /* Create our global data structures. */
390 equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free);
391 equiv_stack = VEC_alloc (tree, heap, 2);
393 /* We're going to do a dominator walk, so ensure that we have
394 dominance information. */
395 calculate_dominance_info (CDI_DOMINATORS);
397 /* Setup callbacks for the generic dominator tree walker. */
398 walk_data.walk_stmts_backward = false;
399 walk_data.dom_direction = CDI_DOMINATORS;
400 walk_data.initialize_block_local_data = NULL;
401 walk_data.before_dom_children_before_stmts = uncprop_initialize_block;
402 walk_data.before_dom_children_walk_stmts = NULL;
403 walk_data.before_dom_children_after_stmts = uncprop_into_successor_phis;
404 walk_data.after_dom_children_before_stmts = NULL;
405 walk_data.after_dom_children_walk_stmts = NULL;
406 walk_data.after_dom_children_after_stmts = uncprop_finalize_block;
407 walk_data.global_data = NULL;
408 walk_data.block_local_data_size = 0;
409 walk_data.interesting_blocks = NULL;
411 /* Now initialize the dominator walker. */
412 init_walk_dominator_tree (&walk_data);
414 /* Recursively walk the dominator tree undoing unprofitable
415 constant/copy propagations. */
416 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
418 /* Finalize and clean up. */
419 fini_walk_dominator_tree (&walk_data);
421 /* EQUIV_STACK should already be empty at this point, so we just
422 need to empty elements out of the hash table, free EQUIV_STACK,
423 and cleanup the AUX field on the edges. */
425 VEC_free (tree, heap, equiv_stack);
431 FOR_EACH_EDGE (e, ei, bb->succs)
444 /* We have finished processing the dominator children of BB, perform
445 any finalization actions in preparation for leaving this node in
446 the dominator tree. */
449 uncprop_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
450 basic_block bb ATTRIBUTE_UNUSED)
452 /* Pop the topmost value off the equiv stack. */
453 tree value = VEC_pop (tree, equiv_stack);
455 /* If that value was non-null, then pop the topmost equivalency off
456 its equivalency stack. */
458 remove_equivalence (value);
461 /* Unpropagate values from PHI nodes in successor blocks of BB. */
464 uncprop_into_successor_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
470 /* For each successor edge, first temporarily record any equivalence
471 on that edge. Then unpropagate values in any PHI nodes at the
472 destination of the edge. Then remove the temporary equivalence. */
473 FOR_EACH_EDGE (e, ei, bb->succs)
475 tree phi = phi_nodes (e->dest);
477 /* If there are no PHI nodes in this destination, then there is
478 no sense in recording any equivalences. */
482 /* Record any equivalency associated with E. */
485 struct edge_equivalency *equiv = e->aux;
486 record_equiv (equiv->rhs, equiv->lhs);
489 /* Walk over the PHI nodes, unpropagating values. */
490 for ( ; phi; phi = PHI_CHAIN (phi))
492 /* Sigh. We'll have more efficient access to this one day. */
493 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
494 struct equiv_hash_elt equiv_hash_elt;
497 /* If the argument is not an invariant, or refers to the same
498 underlying variable as the PHI result, then there's no
499 point in un-propagating the argument. */
500 if (!is_gimple_min_invariant (arg)
501 && SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi)))
504 /* Lookup this argument's value in the hash table. */
505 equiv_hash_elt.value = arg;
506 equiv_hash_elt.equivalences = NULL;
507 slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
511 struct equiv_hash_elt *elt = *slot;
514 /* Walk every equivalence with the same value. If we find
515 one with the same underlying variable as the PHI result,
516 then replace the value in the argument with its equivalent
517 SSA_NAME. Use the most recent equivalence as hopefully
518 that results in shortest lifetimes. */
519 for (j = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--)
521 tree equiv = VEC_index (tree, elt->equivalences, j);
523 if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi)))
525 SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
532 /* If we had an equivalence associated with this edge, remove it. */
535 struct edge_equivalency *equiv = e->aux;
536 remove_equivalence (equiv->rhs);
541 /* Ignoring loop backedges, if BB has precisely one incoming edge then
542 return that edge. Otherwise return NULL. */
544 single_incoming_edge_ignoring_loop_edges (basic_block bb)
550 FOR_EACH_EDGE (e, ei, bb->preds)
552 /* A loop back edge can be identified by the destination of
553 the edge dominating the source of the edge. */
554 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
557 /* If we have already seen a non-loop edge, then we must have
558 multiple incoming non-loop edges and thus we return NULL. */
562 /* This is the first non-loop incoming edge we have found. Record
571 uncprop_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
576 bool recorded = false;
578 /* If this block is dominated by a single incoming edge and that edge
579 has an equivalency, then record the equivalency and push the
580 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
581 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
584 e = single_incoming_edge_ignoring_loop_edges (bb);
586 if (e && e->src == parent && e->aux)
588 struct edge_equivalency *equiv = e->aux;
590 record_equiv (equiv->rhs, equiv->lhs);
591 VEC_safe_push (tree, heap, equiv_stack, equiv->rhs);
597 VEC_safe_push (tree, heap, equiv_stack, NULL_TREE);
603 return flag_tree_dom != 0;
606 struct tree_opt_pass pass_uncprop =
608 "uncprop", /* name */
609 gate_uncprop, /* gate */
610 tree_ssa_uncprop, /* execute */
613 0, /* static_pass_number */
614 TV_TREE_SSA_UNCPROP, /* tv_id */
615 PROP_cfg | PROP_ssa, /* properties_required */
616 0, /* properties_provided */
617 0, /* properties_destroyed */
618 0, /* todo_flags_start */
619 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */