* sv.po, zh_CN.po: Update.
[official-gcc.git] / gcc / tree-ssa-uncprop.c
blob4ca90c2bffae0f67557c59016cb057eef4da7792
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)
9 any later version.
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. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "flags.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "ggc.h"
30 #include "basic-block.h"
31 #include "output.h"
32 #include "expr.h"
33 #include "function.h"
34 #include "diagnostic.h"
35 #include "timevar.h"
36 #include "tree-dump.h"
37 #include "tree-flow.h"
38 #include "domwalk.h"
39 #include "real.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
49 tree rhs;
50 tree lhs;
53 /* This routine finds and records edge equivalences for every edge
54 in the CFG.
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. */
60 static void
61 associate_equivalences_with_edges (void)
63 basic_block bb;
65 /* Walk over each block. If the block ends with a control statement,
66 then it might create a useful equivalence. */
67 FOR_EACH_BB (bb)
69 block_stmt_iterator bsi = bsi_last (bb);
70 tree stmt;
72 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
73 then there is nothing to do. */
74 if (bsi_end_p (bsi))
75 continue;
77 stmt = bsi_stmt (bsi);
79 if (!stmt)
80 continue;
82 /* A COND_EXPR may create an equivalency in a variety of different
83 ways. */
84 if (TREE_CODE (stmt) == COND_EXPR)
86 tree cond = COND_EXPR_COND (stmt);
87 edge true_edge;
88 edge false_edge;
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)
125 ? boolean_false_node
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)
132 ? boolean_true_node
133 : boolean_false_node);
134 false_edge->aux = equivalency;
136 else
138 equivalency = xmalloc (sizeof (struct edge_equivalency));
139 equivalency->lhs = op0;
140 equivalency->rhs = (integer_zerop (op1)
141 ? boolean_true_node
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)
148 ? boolean_false_node
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))))
165 continue;
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;
172 else
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
196 a single value. */
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)
204 || !CASE_LOW (label)
205 || info[bb->index])
206 info[bb->index] = error_mark_node;
207 else
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++)
215 tree node = info[i];
217 if (node != NULL
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
224 block I. */
225 equivalency = xmalloc (sizeof (struct edge_equivalency));
226 equivalency->rhs = x;
227 equivalency->lhs = cond;
228 find_edge (bb, BASIC_BLOCK (i))->aux = equivalency;
231 free (info);
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
252 out of SSA form.
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
276 the argument.
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
282 same value. */
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. */
293 static htab_t equiv;
295 /* Main structure for recording equivalences into our hash table. */
296 struct equiv_hash_elt
298 /* The value/key of this entry. */
299 tree value;
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. */
311 static hashval_t
312 equiv_hash (const void *p)
314 tree value = ((struct equiv_hash_elt *)p)->value;
315 return iterative_hash_expr (value, 0);
318 static int
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. */
329 static void
330 equiv_free (void *p)
332 struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
333 VEC_free (tree, heap, elt->equivalences);
334 free (elt);
337 /* Remove the most recently recorded equivalency for VALUE. */
339 static void
340 remove_equivalence (tree value)
342 struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p;
343 void **slot;
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. */
356 static void
357 record_equiv (tree value, tree equivalence)
359 struct equiv_hash_elt *equiv_hash_elt;
360 void **slot;
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);
368 if (*slot == NULL)
369 *slot = (void *) equiv_hash_elt;
370 else
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. */
380 static void
381 tree_ssa_uncprop (void)
383 struct dom_walk_data walk_data;
384 basic_block bb;
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. */
423 htab_delete (equiv);
424 VEC_free (tree, heap, equiv_stack);
425 FOR_EACH_BB (bb)
427 edge e;
428 edge_iterator ei;
430 FOR_EACH_EDGE (e, ei, bb->succs)
432 if (e->aux)
434 free (e->aux);
435 e->aux = NULL;
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. */
447 static void
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. */
456 if (value != NULL)
457 remove_equivalence (value);
460 /* Unpropagate values from PHI nodes in successor blocks of BB. */
462 static void
463 uncprop_into_successor_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
464 basic_block bb)
466 edge e;
467 edge_iterator ei;
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. */
478 if (!phi)
479 continue;
481 /* Record any equivalency associated with E. */
482 if (e->aux)
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;
494 void **slot;
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)))
501 continue;
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);
508 if (slot)
510 struct equiv_hash_elt *elt = *slot;
511 int j;
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);
525 break;
531 /* If we had an equivalence associated with this edge, remove it. */
532 if (e->aux)
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. */
542 static edge
543 single_incoming_edge_ignoring_loop_edges (basic_block bb)
545 edge retval = NULL;
546 edge e;
547 edge_iterator ei;
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))
554 continue;
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. */
558 if (retval)
559 return NULL;
561 /* This is the first non-loop incoming edge we have found. Record
562 it. */
563 retval = e;
566 return retval;
569 static void
570 uncprop_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
571 basic_block bb)
573 basic_block parent;
574 edge e;
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);
581 if (parent)
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);
591 recorded = true;
595 if (!recorded)
596 VEC_safe_push (tree, heap, equiv_stack, NULL_TREE);
599 static bool
600 gate_uncprop (void)
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 */
610 NULL, /* sub */
611 NULL, /* next */
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 */
619 0 /* letter */