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"
28 #include "basic-block.h"
32 #include "diagnostic.h"
34 #include "tree-dump.h"
35 #include "tree-flow.h"
37 #include "tree-pass.h"
38 #include "tree-ssa-propagate.h"
39 #include "langhooks.h"
41 /* The basic structure describing an equivalency created by traversing
42 an edge. Traversing the edge effectively means that we can assume
43 that we've seen an assignment LHS = RHS. */
44 struct edge_equivalency
50 /* This routine finds and records edge equivalences for every edge
53 When complete, each edge that creates an equivalency will have an
54 EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
55 The caller is responsible for freeing the AUX fields. */
58 associate_equivalences_with_edges (void)
62 /* Walk over each block. If the block ends with a control statement,
63 then it might create a useful equivalence. */
66 gimple_stmt_iterator gsi = gsi_last_bb (bb);
69 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
70 then there is nothing to do. */
74 stmt = gsi_stmt (gsi);
79 /* A COND_EXPR may create an equivalency in a variety of different
81 if (gimple_code (stmt) == GIMPLE_COND)
85 struct edge_equivalency *equivalency;
86 enum tree_code code = gimple_cond_code (stmt);
88 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
90 /* Equality tests may create one or two equivalences. */
91 if (code == EQ_EXPR || code == NE_EXPR)
93 tree op0 = gimple_cond_lhs (stmt);
94 tree op1 = gimple_cond_rhs (stmt);
96 /* Special case comparing booleans against a constant as we
97 know the value of OP0 on both arms of the branch. i.e., we
98 can record an equivalence for OP0 rather than COND. */
99 if (TREE_CODE (op0) == SSA_NAME
100 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
101 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
102 && is_gimple_min_invariant (op1))
106 equivalency = XNEW (struct edge_equivalency);
107 equivalency->lhs = op0;
108 equivalency->rhs = (integer_zerop (op1)
110 : boolean_true_node);
111 true_edge->aux = equivalency;
113 equivalency = XNEW (struct edge_equivalency);
114 equivalency->lhs = op0;
115 equivalency->rhs = (integer_zerop (op1)
117 : boolean_false_node);
118 false_edge->aux = equivalency;
122 equivalency = XNEW (struct edge_equivalency);
123 equivalency->lhs = op0;
124 equivalency->rhs = (integer_zerop (op1)
126 : boolean_false_node);
127 true_edge->aux = equivalency;
129 equivalency = XNEW (struct edge_equivalency);
130 equivalency->lhs = op0;
131 equivalency->rhs = (integer_zerop (op1)
133 : boolean_true_node);
134 false_edge->aux = equivalency;
138 else if (TREE_CODE (op0) == SSA_NAME
139 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
140 && (is_gimple_min_invariant (op1)
141 || (TREE_CODE (op1) == SSA_NAME
142 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
144 /* For IEEE, -0.0 == 0.0, so we don't necessarily know
145 the sign of a variable compared against zero. If
146 we're honoring signed zeros, then we cannot record
147 this value unless we know that the value is nonzero. */
148 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
149 && (TREE_CODE (op1) != REAL_CST
150 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
153 equivalency = XNEW (struct edge_equivalency);
154 equivalency->lhs = op0;
155 equivalency->rhs = op1;
157 true_edge->aux = equivalency;
159 false_edge->aux = equivalency;
164 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
167 /* For a SWITCH_EXPR, a case label which represents a single
168 value and which is the only case label which reaches the
169 target block creates an equivalence. */
170 else if (gimple_code (stmt) == GIMPLE_SWITCH)
172 tree cond = gimple_switch_index (stmt);
174 if (TREE_CODE (cond) == SSA_NAME
175 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
177 int i, n_labels = gimple_switch_num_labels (stmt);
178 tree *info = XCNEWVEC (tree, last_basic_block);
180 /* Walk over the case label vector. Record blocks
181 which are reached by a single case label which represents
183 for (i = 0; i < n_labels; i++)
185 tree label = gimple_switch_label (stmt, i);
186 basic_block bb = label_to_block (CASE_LABEL (label));
188 if (CASE_HIGH (label)
191 info[bb->index] = error_mark_node;
193 info[bb->index] = label;
196 /* Now walk over the blocks to determine which ones were
197 marked as being reached by a useful case label. */
198 for (i = 0; i < n_basic_blocks; i++)
203 && node != error_mark_node)
205 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
206 struct edge_equivalency *equivalency;
208 /* Record an equivalency on the edge from BB to basic
210 equivalency = XNEW (struct edge_equivalency);
211 equivalency->rhs = x;
212 equivalency->lhs = cond;
213 find_edge (bb, BASIC_BLOCK (i))->aux = equivalency;
224 /* Translating out of SSA sometimes requires inserting copies and
225 constant initializations on edges to eliminate PHI nodes.
227 In some cases those copies and constant initializations are
228 redundant because the target already has the value on the
229 RHS of the assignment.
231 We previously tried to catch these cases after translating
232 out of SSA form. However, that code often missed cases. Worse
233 yet, the cases it missed were also often missed by the RTL
234 optimizers. Thus the resulting code had redundant instructions.
236 This pass attempts to detect these situations before translating
239 The key concept that this pass is built upon is that these
240 redundant copies and constant initializations often occur
241 due to constant/copy propagating equivalences resulting from
242 COND_EXPRs and SWITCH_EXPRs.
244 We want to do those propagations as they can sometimes allow
245 the SSA optimizers to do a better job. However, in the cases
246 where such propagations do not result in further optimization,
247 we would like to "undo" the propagation to avoid the redundant
248 copies and constant initializations.
250 This pass works by first associating equivalences with edges in
251 the CFG. For example, the edge leading from a SWITCH_EXPR to
252 its associated CASE_LABEL will have an equivalency between
253 SWITCH_COND and the value in the case label.
255 Once we have found the edge equivalences, we proceed to walk
256 the CFG in dominator order. As we traverse edges we record
257 equivalences associated with those edges we traverse.
259 When we encounter a PHI node, we walk its arguments to see if we
260 have an equivalence for the PHI argument. If so, then we replace
263 Equivalences are looked up based on their value (think of it as
264 the RHS of an assignment). A value may be an SSA_NAME or an
265 invariant. We may have several SSA_NAMEs with the same value,
266 so with each value we have a list of SSA_NAMEs that have the
269 /* As we enter each block we record the value for any edge equivalency
270 leading to this block. If no such edge equivalency exists, then we
271 record NULL. These equivalences are live until we leave the dominator
272 subtree rooted at the block where we record the equivalency. */
273 static VEC(tree,heap) *equiv_stack;
275 /* Global hash table implementing a mapping from invariant values
276 to a list of SSA_NAMEs which have the same value. We might be
277 able to reuse tree-vn for this code. */
280 /* Main structure for recording equivalences into our hash table. */
281 struct equiv_hash_elt
283 /* The value/key of this entry. */
286 /* List of SSA_NAMEs which have the same value/key. */
287 VEC(tree,heap) *equivalences;
290 static void uncprop_enter_block (struct dom_walk_data *, basic_block);
291 static void uncprop_leave_block (struct dom_walk_data *, basic_block);
292 static void uncprop_into_successor_phis (basic_block);
294 /* Hashing and equality routines for the hash table. */
297 equiv_hash (const void *p)
299 tree const value = ((const struct equiv_hash_elt *)p)->value;
300 return iterative_hash_expr (value, 0);
304 equiv_eq (const void *p1, const void *p2)
306 tree value1 = ((const struct equiv_hash_elt *)p1)->value;
307 tree value2 = ((const struct equiv_hash_elt *)p2)->value;
309 return operand_equal_p (value1, value2, 0);
312 /* Free an instance of equiv_hash_elt. */
317 struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
318 VEC_free (tree, heap, elt->equivalences);
322 /* Remove the most recently recorded equivalency for VALUE. */
325 remove_equivalence (tree value)
327 struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p;
330 equiv_hash_elt.value = value;
331 equiv_hash_elt.equivalences = NULL;
333 slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
335 equiv_hash_elt_p = (struct equiv_hash_elt *) *slot;
336 VEC_pop (tree, equiv_hash_elt_p->equivalences);
339 /* Record EQUIVALENCE = VALUE into our hash table. */
342 record_equiv (tree value, tree equivalence)
344 struct equiv_hash_elt *equiv_hash_elt;
347 equiv_hash_elt = XNEW (struct equiv_hash_elt);
348 equiv_hash_elt->value = value;
349 equiv_hash_elt->equivalences = NULL;
351 slot = htab_find_slot (equiv, equiv_hash_elt, INSERT);
354 *slot = (void *) equiv_hash_elt;
356 free (equiv_hash_elt);
358 equiv_hash_elt = (struct equiv_hash_elt *) *slot;
360 VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence);
363 /* Main driver for un-cprop. */
366 tree_ssa_uncprop (void)
368 struct dom_walk_data walk_data;
371 associate_equivalences_with_edges ();
373 /* Create our global data structures. */
374 equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free);
375 equiv_stack = VEC_alloc (tree, heap, 2);
377 /* We're going to do a dominator walk, so ensure that we have
378 dominance information. */
379 calculate_dominance_info (CDI_DOMINATORS);
381 /* Setup callbacks for the generic dominator tree walker. */
382 walk_data.dom_direction = CDI_DOMINATORS;
383 walk_data.initialize_block_local_data = NULL;
384 walk_data.before_dom_children = uncprop_enter_block;
385 walk_data.after_dom_children = uncprop_leave_block;
386 walk_data.global_data = NULL;
387 walk_data.block_local_data_size = 0;
389 /* Now initialize the dominator walker. */
390 init_walk_dominator_tree (&walk_data);
392 /* Recursively walk the dominator tree undoing unprofitable
393 constant/copy propagations. */
394 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
396 /* Finalize and clean up. */
397 fini_walk_dominator_tree (&walk_data);
399 /* EQUIV_STACK should already be empty at this point, so we just
400 need to empty elements out of the hash table, free EQUIV_STACK,
401 and cleanup the AUX field on the edges. */
403 VEC_free (tree, heap, equiv_stack);
409 FOR_EACH_EDGE (e, ei, bb->succs)
422 /* We have finished processing the dominator children of BB, perform
423 any finalization actions in preparation for leaving this node in
424 the dominator tree. */
427 uncprop_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
428 basic_block bb ATTRIBUTE_UNUSED)
430 /* Pop the topmost value off the equiv stack. */
431 tree value = VEC_pop (tree, equiv_stack);
433 /* If that value was non-null, then pop the topmost equivalency off
434 its equivalency stack. */
436 remove_equivalence (value);
439 /* Unpropagate values from PHI nodes in successor blocks of BB. */
442 uncprop_into_successor_phis (basic_block bb)
447 /* For each successor edge, first temporarily record any equivalence
448 on that edge. Then unpropagate values in any PHI nodes at the
449 destination of the edge. Then remove the temporary equivalence. */
450 FOR_EACH_EDGE (e, ei, bb->succs)
452 gimple_seq phis = phi_nodes (e->dest);
453 gimple_stmt_iterator gsi;
455 /* If there are no PHI nodes in this destination, then there is
456 no sense in recording any equivalences. */
457 if (gimple_seq_empty_p (phis))
460 /* Record any equivalency associated with E. */
463 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
464 record_equiv (equiv->rhs, equiv->lhs);
467 /* Walk over the PHI nodes, unpropagating values. */
468 for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
470 gimple phi = gsi_stmt (gsi);
471 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
472 struct equiv_hash_elt equiv_hash_elt;
475 /* If the argument is not an invariant, or refers to the same
476 underlying variable as the PHI result, then there's no
477 point in un-propagating the argument. */
478 if (!is_gimple_min_invariant (arg)
479 && SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi)))
482 /* Lookup this argument's value in the hash table. */
483 equiv_hash_elt.value = arg;
484 equiv_hash_elt.equivalences = NULL;
485 slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
489 struct equiv_hash_elt *elt = (struct equiv_hash_elt *) *slot;
492 /* Walk every equivalence with the same value. If we find
493 one with the same underlying variable as the PHI result,
494 then replace the value in the argument with its equivalent
495 SSA_NAME. Use the most recent equivalence as hopefully
496 that results in shortest lifetimes. */
497 for (j = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--)
499 tree equiv = VEC_index (tree, elt->equivalences, j);
501 if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi)))
503 SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
510 /* If we had an equivalence associated with this edge, remove it. */
513 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
514 remove_equivalence (equiv->rhs);
519 /* Ignoring loop backedges, if BB has precisely one incoming edge then
520 return that edge. Otherwise return NULL. */
522 single_incoming_edge_ignoring_loop_edges (basic_block bb)
528 FOR_EACH_EDGE (e, ei, bb->preds)
530 /* A loop back edge can be identified by the destination of
531 the edge dominating the source of the edge. */
532 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
535 /* If we have already seen a non-loop edge, then we must have
536 multiple incoming non-loop edges and thus we return NULL. */
540 /* This is the first non-loop incoming edge we have found. Record
549 uncprop_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
554 bool recorded = false;
556 /* If this block is dominated by a single incoming edge and that edge
557 has an equivalency, then record the equivalency and push the
558 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
559 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
562 e = single_incoming_edge_ignoring_loop_edges (bb);
564 if (e && e->src == parent && e->aux)
566 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
568 record_equiv (equiv->rhs, equiv->lhs);
569 VEC_safe_push (tree, heap, equiv_stack, equiv->rhs);
575 VEC_safe_push (tree, heap, equiv_stack, NULL_TREE);
577 uncprop_into_successor_phis (bb);
583 return flag_tree_dom != 0;
586 struct gimple_opt_pass pass_uncprop =
590 "uncprop", /* name */
591 gate_uncprop, /* gate */
592 tree_ssa_uncprop, /* execute */
595 0, /* static_pass_number */
596 TV_TREE_SSA_UNCPROP, /* tv_id */
597 PROP_cfg | PROP_ssa, /* properties_required */
598 0, /* properties_provided */
599 0, /* properties_destroyed */
600 0, /* todo_flags_start */
601 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */