1 /* Routines for discovering and unpropagating edge equivalences.
2 Copyright (C) 2005-2013 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)
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/>. */
22 #include "coretypes.h"
27 #include "basic-block.h"
30 #include "gimple-iterator.h"
31 #include "gimple-ssa.h"
33 #include "tree-phinodes.h"
34 #include "ssa-iterators.h"
36 #include "tree-pass.h"
37 #include "tree-ssa-propagate.h"
39 /* The basic structure describing an equivalency created by traversing
40 an edge. Traversing the edge effectively means that we can assume
41 that we've seen an assignment LHS = RHS. */
42 struct edge_equivalency
48 /* This routine finds and records edge equivalences for every edge
51 When complete, each edge that creates an equivalency will have an
52 EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
53 The caller is responsible for freeing the AUX fields. */
56 associate_equivalences_with_edges (void)
60 /* Walk over each block. If the block ends with a control statement,
61 then it might create a useful equivalence. */
64 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
67 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
68 then there is nothing to do. */
72 stmt
= gsi_stmt (gsi
);
77 /* A COND_EXPR may create an equivalency in a variety of different
79 if (gimple_code (stmt
) == GIMPLE_COND
)
83 struct edge_equivalency
*equivalency
;
84 enum tree_code code
= gimple_cond_code (stmt
);
86 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
88 /* Equality tests may create one or two equivalences. */
89 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
91 tree op0
= gimple_cond_lhs (stmt
);
92 tree op1
= gimple_cond_rhs (stmt
);
94 /* Special case comparing booleans against a constant as we
95 know the value of OP0 on both arms of the branch. i.e., we
96 can record an equivalence for OP0 rather than COND. */
97 if (TREE_CODE (op0
) == SSA_NAME
98 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
)
99 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
100 && is_gimple_min_invariant (op1
))
104 equivalency
= XNEW (struct edge_equivalency
);
105 equivalency
->lhs
= op0
;
106 equivalency
->rhs
= (integer_zerop (op1
)
108 : boolean_true_node
);
109 true_edge
->aux
= equivalency
;
111 equivalency
= XNEW (struct edge_equivalency
);
112 equivalency
->lhs
= op0
;
113 equivalency
->rhs
= (integer_zerop (op1
)
115 : boolean_false_node
);
116 false_edge
->aux
= equivalency
;
120 equivalency
= XNEW (struct edge_equivalency
);
121 equivalency
->lhs
= op0
;
122 equivalency
->rhs
= (integer_zerop (op1
)
124 : boolean_false_node
);
125 true_edge
->aux
= equivalency
;
127 equivalency
= XNEW (struct edge_equivalency
);
128 equivalency
->lhs
= op0
;
129 equivalency
->rhs
= (integer_zerop (op1
)
131 : boolean_true_node
);
132 false_edge
->aux
= equivalency
;
136 else if (TREE_CODE (op0
) == SSA_NAME
137 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
)
138 && (is_gimple_min_invariant (op1
)
139 || (TREE_CODE (op1
) == SSA_NAME
140 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1
))))
142 /* For IEEE, -0.0 == 0.0, so we don't necessarily know
143 the sign of a variable compared against zero. If
144 we're honoring signed zeros, then we cannot record
145 this value unless we know that the value is nonzero. */
146 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0
)))
147 && (TREE_CODE (op1
) != REAL_CST
148 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (op1
))))
151 equivalency
= XNEW (struct edge_equivalency
);
152 equivalency
->lhs
= op0
;
153 equivalency
->rhs
= op1
;
155 true_edge
->aux
= equivalency
;
157 false_edge
->aux
= equivalency
;
162 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
165 /* For a SWITCH_EXPR, a case label which represents a single
166 value and which is the only case label which reaches the
167 target block creates an equivalence. */
168 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
170 tree cond
= gimple_switch_index (stmt
);
172 if (TREE_CODE (cond
) == SSA_NAME
173 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond
))
175 int i
, n_labels
= gimple_switch_num_labels (stmt
);
176 tree
*info
= XCNEWVEC (tree
, last_basic_block
);
178 /* Walk over the case label vector. Record blocks
179 which are reached by a single case label which represents
181 for (i
= 0; i
< n_labels
; i
++)
183 tree label
= gimple_switch_label (stmt
, i
);
184 basic_block bb
= label_to_block (CASE_LABEL (label
));
186 if (CASE_HIGH (label
)
189 info
[bb
->index
] = error_mark_node
;
191 info
[bb
->index
] = label
;
194 /* Now walk over the blocks to determine which ones were
195 marked as being reached by a useful case label. */
196 for (i
= 0; i
< n_basic_blocks_for_fn (cfun
); i
++)
201 && node
!= error_mark_node
)
203 tree x
= fold_convert (TREE_TYPE (cond
), CASE_LOW (node
));
204 struct edge_equivalency
*equivalency
;
206 /* Record an equivalency on the edge from BB to basic
208 equivalency
= XNEW (struct edge_equivalency
);
209 equivalency
->rhs
= x
;
210 equivalency
->lhs
= cond
;
211 find_edge (bb
, BASIC_BLOCK (i
))->aux
= equivalency
;
222 /* Translating out of SSA sometimes requires inserting copies and
223 constant initializations on edges to eliminate PHI nodes.
225 In some cases those copies and constant initializations are
226 redundant because the target already has the value on the
227 RHS of the assignment.
229 We previously tried to catch these cases after translating
230 out of SSA form. However, that code often missed cases. Worse
231 yet, the cases it missed were also often missed by the RTL
232 optimizers. Thus the resulting code had redundant instructions.
234 This pass attempts to detect these situations before translating
237 The key concept that this pass is built upon is that these
238 redundant copies and constant initializations often occur
239 due to constant/copy propagating equivalences resulting from
240 COND_EXPRs and SWITCH_EXPRs.
242 We want to do those propagations as they can sometimes allow
243 the SSA optimizers to do a better job. However, in the cases
244 where such propagations do not result in further optimization,
245 we would like to "undo" the propagation to avoid the redundant
246 copies and constant initializations.
248 This pass works by first associating equivalences with edges in
249 the CFG. For example, the edge leading from a SWITCH_EXPR to
250 its associated CASE_LABEL will have an equivalency between
251 SWITCH_COND and the value in the case label.
253 Once we have found the edge equivalences, we proceed to walk
254 the CFG in dominator order. As we traverse edges we record
255 equivalences associated with those edges we traverse.
257 When we encounter a PHI node, we walk its arguments to see if we
258 have an equivalence for the PHI argument. If so, then we replace
261 Equivalences are looked up based on their value (think of it as
262 the RHS of an assignment). A value may be an SSA_NAME or an
263 invariant. We may have several SSA_NAMEs with the same value,
264 so with each value we have a list of SSA_NAMEs that have the
268 /* Main structure for recording equivalences into our hash table. */
269 struct equiv_hash_elt
271 /* The value/key of this entry. */
274 /* List of SSA_NAMEs which have the same value/key. */
275 vec
<tree
> equivalences
;
278 /* Value to ssa name equivalence hashtable helpers. */
280 struct val_ssa_equiv_hasher
282 typedef equiv_hash_elt value_type
;
283 typedef equiv_hash_elt compare_type
;
284 static inline hashval_t
hash (const value_type
*);
285 static inline bool equal (const value_type
*, const compare_type
*);
286 static inline void remove (value_type
*);
290 val_ssa_equiv_hasher::hash (const value_type
*p
)
292 tree
const value
= p
->value
;
293 return iterative_hash_expr (value
, 0);
297 val_ssa_equiv_hasher::equal (const value_type
*p1
, const compare_type
*p2
)
299 tree value1
= p1
->value
;
300 tree value2
= p2
->value
;
302 return operand_equal_p (value1
, value2
, 0);
305 /* Free an instance of equiv_hash_elt. */
308 val_ssa_equiv_hasher::remove (value_type
*elt
)
310 elt
->equivalences
.release ();
314 /* Global hash table implementing a mapping from invariant values
315 to a list of SSA_NAMEs which have the same value. We might be
316 able to reuse tree-vn for this code. */
317 static hash_table
<val_ssa_equiv_hasher
> val_ssa_equiv
;
319 static void uncprop_into_successor_phis (basic_block
);
321 /* Remove the most recently recorded equivalency for VALUE. */
324 remove_equivalence (tree value
)
326 struct equiv_hash_elt an_equiv_elt
, *an_equiv_elt_p
;
327 equiv_hash_elt
**slot
;
329 an_equiv_elt
.value
= value
;
330 an_equiv_elt
.equivalences
.create (0);
332 slot
= val_ssa_equiv
.find_slot (&an_equiv_elt
, NO_INSERT
);
334 an_equiv_elt_p
= *slot
;
335 an_equiv_elt_p
->equivalences
.pop ();
338 /* Record EQUIVALENCE = VALUE into our hash table. */
341 record_equiv (tree value
, tree equivalence
)
343 equiv_hash_elt
*an_equiv_elt_p
;
344 equiv_hash_elt
**slot
;
346 an_equiv_elt_p
= XNEW (struct equiv_hash_elt
);
347 an_equiv_elt_p
->value
= value
;
348 an_equiv_elt_p
->equivalences
.create (0);
350 slot
= val_ssa_equiv
.find_slot (an_equiv_elt_p
, INSERT
);
353 *slot
= an_equiv_elt_p
;
355 free (an_equiv_elt_p
);
357 an_equiv_elt_p
= *slot
;
359 an_equiv_elt_p
->equivalences
.safe_push (equivalence
);
362 class uncprop_dom_walker
: public dom_walker
365 uncprop_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
367 virtual void before_dom_children (basic_block
);
368 virtual void after_dom_children (basic_block
);
372 /* As we enter each block we record the value for any edge equivalency
373 leading to this block. If no such edge equivalency exists, then we
374 record NULL. These equivalences are live until we leave the dominator
375 subtree rooted at the block where we record the equivalency. */
376 stack_vec
<tree
, 2> m_equiv_stack
;
379 /* Main driver for un-cprop. */
382 tree_ssa_uncprop (void)
386 associate_equivalences_with_edges ();
388 /* Create our global data structures. */
389 val_ssa_equiv
.create (1024);
391 /* We're going to do a dominator walk, so ensure that we have
392 dominance information. */
393 calculate_dominance_info (CDI_DOMINATORS
);
395 /* Recursively walk the dominator tree undoing unprofitable
396 constant/copy propagations. */
397 uncprop_dom_walker (CDI_DOMINATORS
).walk (cfun
->cfg
->x_entry_block_ptr
);
399 /* we just need to empty elements out of the hash table, and cleanup the
400 AUX field on the edges. */
401 val_ssa_equiv
.dispose ();
407 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
420 /* We have finished processing the dominator children of BB, perform
421 any finalization actions in preparation for leaving this node in
422 the dominator tree. */
425 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
427 /* Pop the topmost value off the equiv stack. */
428 tree value
= m_equiv_stack
.pop ();
430 /* If that value was non-null, then pop the topmost equivalency off
431 its equivalency stack. */
433 remove_equivalence (value
);
436 /* Unpropagate values from PHI nodes in successor blocks of BB. */
439 uncprop_into_successor_phis (basic_block bb
)
444 /* For each successor edge, first temporarily record any equivalence
445 on that edge. Then unpropagate values in any PHI nodes at the
446 destination of the edge. Then remove the temporary equivalence. */
447 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
449 gimple_seq phis
= phi_nodes (e
->dest
);
450 gimple_stmt_iterator gsi
;
452 /* If there are no PHI nodes in this destination, then there is
453 no sense in recording any equivalences. */
454 if (gimple_seq_empty_p (phis
))
457 /* Record any equivalency associated with E. */
460 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
461 record_equiv (equiv
->rhs
, equiv
->lhs
);
464 /* Walk over the PHI nodes, unpropagating values. */
465 for (gsi
= gsi_start (phis
) ; !gsi_end_p (gsi
); gsi_next (&gsi
))
467 gimple phi
= gsi_stmt (gsi
);
468 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
469 tree res
= PHI_RESULT (phi
);
470 equiv_hash_elt an_equiv_elt
;
471 equiv_hash_elt
**slot
;
473 /* If the argument is not an invariant and can be potentially
474 coalesced with the result, then there's no point in
475 un-propagating the argument. */
476 if (!is_gimple_min_invariant (arg
)
477 && gimple_can_coalesce_p (arg
, res
))
480 /* Lookup this argument's value in the hash table. */
481 an_equiv_elt
.value
= arg
;
482 an_equiv_elt
.equivalences
.create (0);
483 slot
= val_ssa_equiv
.find_slot (&an_equiv_elt
, NO_INSERT
);
487 struct equiv_hash_elt
*elt
= *slot
;
490 /* Walk every equivalence with the same value. If we find
491 one that can potentially coalesce with the PHI rsult,
492 then replace the value in the argument with its equivalent
493 SSA_NAME. Use the most recent equivalence as hopefully
494 that results in shortest lifetimes. */
495 for (j
= elt
->equivalences
.length () - 1; j
>= 0; j
--)
497 tree equiv
= elt
->equivalences
[j
];
499 if (gimple_can_coalesce_p (equiv
, res
))
501 SET_PHI_ARG_DEF (phi
, e
->dest_idx
, equiv
);
508 /* If we had an equivalence associated with this edge, remove it. */
511 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
512 remove_equivalence (equiv
->rhs
);
517 /* Ignoring loop backedges, if BB has precisely one incoming edge then
518 return that edge. Otherwise return NULL. */
520 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
526 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
528 /* A loop back edge can be identified by the destination of
529 the edge dominating the source of the edge. */
530 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
533 /* If we have already seen a non-loop edge, then we must have
534 multiple incoming non-loop edges and thus we return NULL. */
538 /* This is the first non-loop incoming edge we have found. Record
547 uncprop_dom_walker::before_dom_children (basic_block bb
)
551 bool recorded
= false;
553 /* If this block is dominated by a single incoming edge and that edge
554 has an equivalency, then record the equivalency and push the
555 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
556 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
559 e
= single_incoming_edge_ignoring_loop_edges (bb
);
561 if (e
&& e
->src
== parent
&& e
->aux
)
563 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
565 record_equiv (equiv
->rhs
, equiv
->lhs
);
566 m_equiv_stack
.safe_push (equiv
->rhs
);
572 m_equiv_stack
.safe_push (NULL_TREE
);
574 uncprop_into_successor_phis (bb
);
580 return flag_tree_dom
!= 0;
585 const pass_data pass_data_uncprop
=
587 GIMPLE_PASS
, /* type */
588 "uncprop", /* name */
589 OPTGROUP_NONE
, /* optinfo_flags */
591 true, /* has_execute */
592 TV_TREE_SSA_UNCPROP
, /* tv_id */
593 ( PROP_cfg
| PROP_ssa
), /* properties_required */
594 0, /* properties_provided */
595 0, /* properties_destroyed */
596 0, /* todo_flags_start */
597 TODO_verify_ssa
, /* todo_flags_finish */
600 class pass_uncprop
: public gimple_opt_pass
603 pass_uncprop (gcc::context
*ctxt
)
604 : gimple_opt_pass (pass_data_uncprop
, ctxt
)
607 /* opt_pass methods: */
608 opt_pass
* clone () { return new pass_uncprop (m_ctxt
); }
609 bool gate () { return gate_uncprop (); }
610 unsigned int execute () { return tree_ssa_uncprop (); }
612 }; // class pass_uncprop
617 make_pass_uncprop (gcc::context
*ctxt
)
619 return new pass_uncprop (ctxt
);