* gcc.target/i386/387-3.c, gcc.target/i386/387-4.c,
[official-gcc.git] / gcc / tree-ssa-uncprop.c
bloba43dd1a844151c8a96cf2adc23d4c6d3682827e2
1 /* Routines for discovering and unpropagating edge equivalences.
2 Copyright (C) 2005-2014 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "stor-layout.h"
26 #include "flags.h"
27 #include "tm_p.h"
28 #include "basic-block.h"
29 #include "function.h"
30 #include "hash-table.h"
31 #include "tree-ssa-alias.h"
32 #include "internal-fn.h"
33 #include "gimple-expr.h"
34 #include "is-a.h"
35 #include "gimple.h"
36 #include "gimple-iterator.h"
37 #include "gimple-ssa.h"
38 #include "tree-cfg.h"
39 #include "tree-phinodes.h"
40 #include "ssa-iterators.h"
41 #include "domwalk.h"
42 #include "tree-pass.h"
43 #include "tree-ssa-propagate.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
50 tree rhs;
51 tree lhs;
54 /* This routine finds and records edge equivalences for every edge
55 in the CFG.
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. */
61 static void
62 associate_equivalences_with_edges (void)
64 basic_block bb;
66 /* Walk over each block. If the block ends with a control statement,
67 then it might create a useful equivalence. */
68 FOR_EACH_BB_FN (bb, cfun)
70 gimple_stmt_iterator gsi = gsi_last_bb (bb);
71 gimple stmt;
73 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
74 then there is nothing to do. */
75 if (gsi_end_p (gsi))
76 continue;
78 stmt = gsi_stmt (gsi);
80 if (!stmt)
81 continue;
83 /* A COND_EXPR may create an equivalency in a variety of different
84 ways. */
85 if (gimple_code (stmt) == GIMPLE_COND)
87 edge true_edge;
88 edge false_edge;
89 struct edge_equivalency *equivalency;
90 enum tree_code code = gimple_cond_code (stmt);
92 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
94 /* Equality tests may create one or two equivalences. */
95 if (code == EQ_EXPR || code == NE_EXPR)
97 tree op0 = gimple_cond_lhs (stmt);
98 tree op1 = gimple_cond_rhs (stmt);
100 /* Special case comparing booleans against a constant as we
101 know the value of OP0 on both arms of the branch. i.e., we
102 can record an equivalence for OP0 rather than COND. */
103 if (TREE_CODE (op0) == SSA_NAME
104 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
105 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
106 && is_gimple_min_invariant (op1))
108 if (code == EQ_EXPR)
110 equivalency = XNEW (struct edge_equivalency);
111 equivalency->lhs = op0;
112 equivalency->rhs = (integer_zerop (op1)
113 ? boolean_false_node
114 : boolean_true_node);
115 true_edge->aux = equivalency;
117 equivalency = XNEW (struct edge_equivalency);
118 equivalency->lhs = op0;
119 equivalency->rhs = (integer_zerop (op1)
120 ? boolean_true_node
121 : boolean_false_node);
122 false_edge->aux = equivalency;
124 else
126 equivalency = XNEW (struct edge_equivalency);
127 equivalency->lhs = op0;
128 equivalency->rhs = (integer_zerop (op1)
129 ? boolean_true_node
130 : boolean_false_node);
131 true_edge->aux = equivalency;
133 equivalency = XNEW (struct edge_equivalency);
134 equivalency->lhs = op0;
135 equivalency->rhs = (integer_zerop (op1)
136 ? boolean_false_node
137 : boolean_true_node);
138 false_edge->aux = equivalency;
142 else if (TREE_CODE (op0) == SSA_NAME
143 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
144 && (is_gimple_min_invariant (op1)
145 || (TREE_CODE (op1) == SSA_NAME
146 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
148 /* For IEEE, -0.0 == 0.0, so we don't necessarily know
149 the sign of a variable compared against zero. If
150 we're honoring signed zeros, then we cannot record
151 this value unless we know that the value is nonzero. */
152 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
153 && (TREE_CODE (op1) != REAL_CST
154 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
155 continue;
157 equivalency = XNEW (struct edge_equivalency);
158 equivalency->lhs = op0;
159 equivalency->rhs = op1;
160 if (code == EQ_EXPR)
161 true_edge->aux = equivalency;
162 else
163 false_edge->aux = equivalency;
168 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
171 /* For a SWITCH_EXPR, a case label which represents a single
172 value and which is the only case label which reaches the
173 target block creates an equivalence. */
174 else if (gimple_code (stmt) == GIMPLE_SWITCH)
176 tree cond = gimple_switch_index (stmt);
178 if (TREE_CODE (cond) == SSA_NAME
179 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
181 int i, n_labels = gimple_switch_num_labels (stmt);
182 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
184 /* Walk over the case label vector. Record blocks
185 which are reached by a single case label which represents
186 a single value. */
187 for (i = 0; i < n_labels; i++)
189 tree label = gimple_switch_label (stmt, i);
190 basic_block bb = label_to_block (CASE_LABEL (label));
192 if (CASE_HIGH (label)
193 || !CASE_LOW (label)
194 || info[bb->index])
195 info[bb->index] = error_mark_node;
196 else
197 info[bb->index] = label;
200 /* Now walk over the blocks to determine which ones were
201 marked as being reached by a useful case label. */
202 for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
204 tree node = info[i];
206 if (node != NULL
207 && node != error_mark_node)
209 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
210 struct edge_equivalency *equivalency;
212 /* Record an equivalency on the edge from BB to basic
213 block I. */
214 equivalency = XNEW (struct edge_equivalency);
215 equivalency->rhs = x;
216 equivalency->lhs = cond;
217 find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
218 equivalency;
221 free (info);
229 /* Translating out of SSA sometimes requires inserting copies and
230 constant initializations on edges to eliminate PHI nodes.
232 In some cases those copies and constant initializations are
233 redundant because the target already has the value on the
234 RHS of the assignment.
236 We previously tried to catch these cases after translating
237 out of SSA form. However, that code often missed cases. Worse
238 yet, the cases it missed were also often missed by the RTL
239 optimizers. Thus the resulting code had redundant instructions.
241 This pass attempts to detect these situations before translating
242 out of SSA form.
244 The key concept that this pass is built upon is that these
245 redundant copies and constant initializations often occur
246 due to constant/copy propagating equivalences resulting from
247 COND_EXPRs and SWITCH_EXPRs.
249 We want to do those propagations as they can sometimes allow
250 the SSA optimizers to do a better job. However, in the cases
251 where such propagations do not result in further optimization,
252 we would like to "undo" the propagation to avoid the redundant
253 copies and constant initializations.
255 This pass works by first associating equivalences with edges in
256 the CFG. For example, the edge leading from a SWITCH_EXPR to
257 its associated CASE_LABEL will have an equivalency between
258 SWITCH_COND and the value in the case label.
260 Once we have found the edge equivalences, we proceed to walk
261 the CFG in dominator order. As we traverse edges we record
262 equivalences associated with those edges we traverse.
264 When we encounter a PHI node, we walk its arguments to see if we
265 have an equivalence for the PHI argument. If so, then we replace
266 the argument.
268 Equivalences are looked up based on their value (think of it as
269 the RHS of an assignment). A value may be an SSA_NAME or an
270 invariant. We may have several SSA_NAMEs with the same value,
271 so with each value we have a list of SSA_NAMEs that have the
272 same value. */
275 /* Main structure for recording equivalences into our hash table. */
276 struct equiv_hash_elt
278 /* The value/key of this entry. */
279 tree value;
281 /* List of SSA_NAMEs which have the same value/key. */
282 vec<tree> equivalences;
285 /* Value to ssa name equivalence hashtable helpers. */
287 struct val_ssa_equiv_hasher
289 typedef equiv_hash_elt value_type;
290 typedef equiv_hash_elt compare_type;
291 static inline hashval_t hash (const value_type *);
292 static inline bool equal (const value_type *, const compare_type *);
293 static inline void remove (value_type *);
296 inline hashval_t
297 val_ssa_equiv_hasher::hash (const value_type *p)
299 tree const value = p->value;
300 return iterative_hash_expr (value, 0);
303 inline bool
304 val_ssa_equiv_hasher::equal (const value_type *p1, const compare_type *p2)
306 tree value1 = p1->value;
307 tree value2 = p2->value;
309 return operand_equal_p (value1, value2, 0);
312 /* Free an instance of equiv_hash_elt. */
314 inline void
315 val_ssa_equiv_hasher::remove (value_type *elt)
317 elt->equivalences.release ();
318 free (elt);
321 /* Global hash table implementing a mapping from invariant values
322 to a list of SSA_NAMEs which have the same value. We might be
323 able to reuse tree-vn for this code. */
324 static hash_table <val_ssa_equiv_hasher> val_ssa_equiv;
326 static void uncprop_into_successor_phis (basic_block);
328 /* Remove the most recently recorded equivalency for VALUE. */
330 static void
331 remove_equivalence (tree value)
333 struct equiv_hash_elt an_equiv_elt, *an_equiv_elt_p;
334 equiv_hash_elt **slot;
336 an_equiv_elt.value = value;
337 an_equiv_elt.equivalences.create (0);
339 slot = val_ssa_equiv.find_slot (&an_equiv_elt, NO_INSERT);
341 an_equiv_elt_p = *slot;
342 an_equiv_elt_p->equivalences.pop ();
345 /* Record EQUIVALENCE = VALUE into our hash table. */
347 static void
348 record_equiv (tree value, tree equivalence)
350 equiv_hash_elt *an_equiv_elt_p;
351 equiv_hash_elt **slot;
353 an_equiv_elt_p = XNEW (struct equiv_hash_elt);
354 an_equiv_elt_p->value = value;
355 an_equiv_elt_p->equivalences.create (0);
357 slot = val_ssa_equiv.find_slot (an_equiv_elt_p, INSERT);
359 if (*slot == NULL)
360 *slot = an_equiv_elt_p;
361 else
362 free (an_equiv_elt_p);
364 an_equiv_elt_p = *slot;
366 an_equiv_elt_p->equivalences.safe_push (equivalence);
369 class uncprop_dom_walker : public dom_walker
371 public:
372 uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
374 virtual void before_dom_children (basic_block);
375 virtual void after_dom_children (basic_block);
377 private:
379 /* As we enter each block we record the value for any edge equivalency
380 leading to this block. If no such edge equivalency exists, then we
381 record NULL. These equivalences are live until we leave the dominator
382 subtree rooted at the block where we record the equivalency. */
383 auto_vec<tree, 2> m_equiv_stack;
386 /* Main driver for un-cprop. */
388 static unsigned int
389 tree_ssa_uncprop (void)
391 basic_block bb;
393 associate_equivalences_with_edges ();
395 /* Create our global data structures. */
396 val_ssa_equiv.create (1024);
398 /* We're going to do a dominator walk, so ensure that we have
399 dominance information. */
400 calculate_dominance_info (CDI_DOMINATORS);
402 /* Recursively walk the dominator tree undoing unprofitable
403 constant/copy propagations. */
404 uncprop_dom_walker (CDI_DOMINATORS).walk (cfun->cfg->x_entry_block_ptr);
406 /* we just need to empty elements out of the hash table, and cleanup the
407 AUX field on the edges. */
408 val_ssa_equiv.dispose ();
409 FOR_EACH_BB_FN (bb, cfun)
411 edge e;
412 edge_iterator ei;
414 FOR_EACH_EDGE (e, ei, bb->succs)
416 if (e->aux)
418 free (e->aux);
419 e->aux = NULL;
423 return 0;
427 /* We have finished processing the dominator children of BB, perform
428 any finalization actions in preparation for leaving this node in
429 the dominator tree. */
431 void
432 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
434 /* Pop the topmost value off the equiv stack. */
435 tree value = m_equiv_stack.pop ();
437 /* If that value was non-null, then pop the topmost equivalency off
438 its equivalency stack. */
439 if (value != NULL)
440 remove_equivalence (value);
443 /* Unpropagate values from PHI nodes in successor blocks of BB. */
445 static void
446 uncprop_into_successor_phis (basic_block bb)
448 edge e;
449 edge_iterator ei;
451 /* For each successor edge, first temporarily record any equivalence
452 on that edge. Then unpropagate values in any PHI nodes at the
453 destination of the edge. Then remove the temporary equivalence. */
454 FOR_EACH_EDGE (e, ei, bb->succs)
456 gimple_seq phis = phi_nodes (e->dest);
457 gimple_stmt_iterator gsi;
459 /* If there are no PHI nodes in this destination, then there is
460 no sense in recording any equivalences. */
461 if (gimple_seq_empty_p (phis))
462 continue;
464 /* Record any equivalency associated with E. */
465 if (e->aux)
467 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
468 record_equiv (equiv->rhs, equiv->lhs);
471 /* Walk over the PHI nodes, unpropagating values. */
472 for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
474 gimple phi = gsi_stmt (gsi);
475 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
476 tree res = PHI_RESULT (phi);
477 equiv_hash_elt an_equiv_elt;
478 equiv_hash_elt **slot;
480 /* If the argument is not an invariant and can be potentially
481 coalesced with the result, then there's no point in
482 un-propagating the argument. */
483 if (!is_gimple_min_invariant (arg)
484 && gimple_can_coalesce_p (arg, res))
485 continue;
487 /* Lookup this argument's value in the hash table. */
488 an_equiv_elt.value = arg;
489 an_equiv_elt.equivalences.create (0);
490 slot = val_ssa_equiv.find_slot (&an_equiv_elt, NO_INSERT);
492 if (slot)
494 struct equiv_hash_elt *elt = *slot;
495 int j;
497 /* Walk every equivalence with the same value. If we find
498 one that can potentially coalesce with the PHI rsult,
499 then replace the value in the argument with its equivalent
500 SSA_NAME. Use the most recent equivalence as hopefully
501 that results in shortest lifetimes. */
502 for (j = elt->equivalences.length () - 1; j >= 0; j--)
504 tree equiv = elt->equivalences[j];
506 if (gimple_can_coalesce_p (equiv, res))
508 SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
509 break;
515 /* If we had an equivalence associated with this edge, remove it. */
516 if (e->aux)
518 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
519 remove_equivalence (equiv->rhs);
524 /* Ignoring loop backedges, if BB has precisely one incoming edge then
525 return that edge. Otherwise return NULL. */
526 static edge
527 single_incoming_edge_ignoring_loop_edges (basic_block bb)
529 edge retval = NULL;
530 edge e;
531 edge_iterator ei;
533 FOR_EACH_EDGE (e, ei, bb->preds)
535 /* A loop back edge can be identified by the destination of
536 the edge dominating the source of the edge. */
537 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
538 continue;
540 /* If we have already seen a non-loop edge, then we must have
541 multiple incoming non-loop edges and thus we return NULL. */
542 if (retval)
543 return NULL;
545 /* This is the first non-loop incoming edge we have found. Record
546 it. */
547 retval = e;
550 return retval;
553 void
554 uncprop_dom_walker::before_dom_children (basic_block bb)
556 basic_block parent;
557 edge e;
558 bool recorded = false;
560 /* If this block is dominated by a single incoming edge and that edge
561 has an equivalency, then record the equivalency and push the
562 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
563 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
564 if (parent)
566 e = single_incoming_edge_ignoring_loop_edges (bb);
568 if (e && e->src == parent && e->aux)
570 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
572 record_equiv (equiv->rhs, equiv->lhs);
573 m_equiv_stack.safe_push (equiv->rhs);
574 recorded = true;
578 if (!recorded)
579 m_equiv_stack.safe_push (NULL_TREE);
581 uncprop_into_successor_phis (bb);
584 static bool
585 gate_uncprop (void)
587 return flag_tree_dom != 0;
590 namespace {
592 const pass_data pass_data_uncprop =
594 GIMPLE_PASS, /* type */
595 "uncprop", /* name */
596 OPTGROUP_NONE, /* optinfo_flags */
597 true, /* has_gate */
598 true, /* has_execute */
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_verify_ssa, /* todo_flags_finish */
607 class pass_uncprop : public gimple_opt_pass
609 public:
610 pass_uncprop (gcc::context *ctxt)
611 : gimple_opt_pass (pass_data_uncprop, ctxt)
614 /* opt_pass methods: */
615 opt_pass * clone () { return new pass_uncprop (m_ctxt); }
616 bool gate () { return gate_uncprop (); }
617 unsigned int execute () { return tree_ssa_uncprop (); }
619 }; // class pass_uncprop
621 } // anon namespace
623 gimple_opt_pass *
624 make_pass_uncprop (gcc::context *ctxt)
626 return new pass_uncprop (ctxt);