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-ssa.h"
32 #include "tree-phinodes.h"
33 #include "ssa-iterators.h"
35 #include "tree-pass.h"
36 #include "tree-ssa-propagate.h"
38 /* The basic structure describing an equivalency created by traversing
39 an edge. Traversing the edge effectively means that we can assume
40 that we've seen an assignment LHS = RHS. */
41 struct edge_equivalency
47 /* This routine finds and records edge equivalences for every edge
50 When complete, each edge that creates an equivalency will have an
51 EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
52 The caller is responsible for freeing the AUX fields. */
55 associate_equivalences_with_edges (void)
59 /* Walk over each block. If the block ends with a control statement,
60 then it might create a useful equivalence. */
63 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
66 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
67 then there is nothing to do. */
71 stmt
= gsi_stmt (gsi
);
76 /* A COND_EXPR may create an equivalency in a variety of different
78 if (gimple_code (stmt
) == GIMPLE_COND
)
82 struct edge_equivalency
*equivalency
;
83 enum tree_code code
= gimple_cond_code (stmt
);
85 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
87 /* Equality tests may create one or two equivalences. */
88 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
90 tree op0
= gimple_cond_lhs (stmt
);
91 tree op1
= gimple_cond_rhs (stmt
);
93 /* Special case comparing booleans against a constant as we
94 know the value of OP0 on both arms of the branch. i.e., we
95 can record an equivalence for OP0 rather than COND. */
96 if (TREE_CODE (op0
) == SSA_NAME
97 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
)
98 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
99 && is_gimple_min_invariant (op1
))
103 equivalency
= XNEW (struct edge_equivalency
);
104 equivalency
->lhs
= op0
;
105 equivalency
->rhs
= (integer_zerop (op1
)
107 : boolean_true_node
);
108 true_edge
->aux
= equivalency
;
110 equivalency
= XNEW (struct edge_equivalency
);
111 equivalency
->lhs
= op0
;
112 equivalency
->rhs
= (integer_zerop (op1
)
114 : boolean_false_node
);
115 false_edge
->aux
= equivalency
;
119 equivalency
= XNEW (struct edge_equivalency
);
120 equivalency
->lhs
= op0
;
121 equivalency
->rhs
= (integer_zerop (op1
)
123 : boolean_false_node
);
124 true_edge
->aux
= equivalency
;
126 equivalency
= XNEW (struct edge_equivalency
);
127 equivalency
->lhs
= op0
;
128 equivalency
->rhs
= (integer_zerop (op1
)
130 : boolean_true_node
);
131 false_edge
->aux
= equivalency
;
135 else if (TREE_CODE (op0
) == SSA_NAME
136 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
)
137 && (is_gimple_min_invariant (op1
)
138 || (TREE_CODE (op1
) == SSA_NAME
139 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1
))))
141 /* For IEEE, -0.0 == 0.0, so we don't necessarily know
142 the sign of a variable compared against zero. If
143 we're honoring signed zeros, then we cannot record
144 this value unless we know that the value is nonzero. */
145 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0
)))
146 && (TREE_CODE (op1
) != REAL_CST
147 || REAL_VALUES_EQUAL (dconst0
, TREE_REAL_CST (op1
))))
150 equivalency
= XNEW (struct edge_equivalency
);
151 equivalency
->lhs
= op0
;
152 equivalency
->rhs
= op1
;
154 true_edge
->aux
= equivalency
;
156 false_edge
->aux
= equivalency
;
161 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
164 /* For a SWITCH_EXPR, a case label which represents a single
165 value and which is the only case label which reaches the
166 target block creates an equivalence. */
167 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
169 tree cond
= gimple_switch_index (stmt
);
171 if (TREE_CODE (cond
) == SSA_NAME
172 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond
))
174 int i
, n_labels
= gimple_switch_num_labels (stmt
);
175 tree
*info
= XCNEWVEC (tree
, last_basic_block
);
177 /* Walk over the case label vector. Record blocks
178 which are reached by a single case label which represents
180 for (i
= 0; i
< n_labels
; i
++)
182 tree label
= gimple_switch_label (stmt
, i
);
183 basic_block bb
= label_to_block (CASE_LABEL (label
));
185 if (CASE_HIGH (label
)
188 info
[bb
->index
] = error_mark_node
;
190 info
[bb
->index
] = label
;
193 /* Now walk over the blocks to determine which ones were
194 marked as being reached by a useful case label. */
195 for (i
= 0; i
< n_basic_blocks
; i
++)
200 && node
!= error_mark_node
)
202 tree x
= fold_convert (TREE_TYPE (cond
), CASE_LOW (node
));
203 struct edge_equivalency
*equivalency
;
205 /* Record an equivalency on the edge from BB to basic
207 equivalency
= XNEW (struct edge_equivalency
);
208 equivalency
->rhs
= x
;
209 equivalency
->lhs
= cond
;
210 find_edge (bb
, BASIC_BLOCK (i
))->aux
= equivalency
;
221 /* Translating out of SSA sometimes requires inserting copies and
222 constant initializations on edges to eliminate PHI nodes.
224 In some cases those copies and constant initializations are
225 redundant because the target already has the value on the
226 RHS of the assignment.
228 We previously tried to catch these cases after translating
229 out of SSA form. However, that code often missed cases. Worse
230 yet, the cases it missed were also often missed by the RTL
231 optimizers. Thus the resulting code had redundant instructions.
233 This pass attempts to detect these situations before translating
236 The key concept that this pass is built upon is that these
237 redundant copies and constant initializations often occur
238 due to constant/copy propagating equivalences resulting from
239 COND_EXPRs and SWITCH_EXPRs.
241 We want to do those propagations as they can sometimes allow
242 the SSA optimizers to do a better job. However, in the cases
243 where such propagations do not result in further optimization,
244 we would like to "undo" the propagation to avoid the redundant
245 copies and constant initializations.
247 This pass works by first associating equivalences with edges in
248 the CFG. For example, the edge leading from a SWITCH_EXPR to
249 its associated CASE_LABEL will have an equivalency between
250 SWITCH_COND and the value in the case label.
252 Once we have found the edge equivalences, we proceed to walk
253 the CFG in dominator order. As we traverse edges we record
254 equivalences associated with those edges we traverse.
256 When we encounter a PHI node, we walk its arguments to see if we
257 have an equivalence for the PHI argument. If so, then we replace
260 Equivalences are looked up based on their value (think of it as
261 the RHS of an assignment). A value may be an SSA_NAME or an
262 invariant. We may have several SSA_NAMEs with the same value,
263 so with each value we have a list of SSA_NAMEs that have the
267 /* Main structure for recording equivalences into our hash table. */
268 struct equiv_hash_elt
270 /* The value/key of this entry. */
273 /* List of SSA_NAMEs which have the same value/key. */
274 vec
<tree
> equivalences
;
277 /* Value to ssa name equivalence hashtable helpers. */
279 struct val_ssa_equiv_hasher
281 typedef equiv_hash_elt value_type
;
282 typedef equiv_hash_elt compare_type
;
283 static inline hashval_t
hash (const value_type
*);
284 static inline bool equal (const value_type
*, const compare_type
*);
285 static inline void remove (value_type
*);
289 val_ssa_equiv_hasher::hash (const value_type
*p
)
291 tree
const value
= p
->value
;
292 return iterative_hash_expr (value
, 0);
296 val_ssa_equiv_hasher::equal (const value_type
*p1
, const compare_type
*p2
)
298 tree value1
= p1
->value
;
299 tree value2
= p2
->value
;
301 return operand_equal_p (value1
, value2
, 0);
304 /* Free an instance of equiv_hash_elt. */
307 val_ssa_equiv_hasher::remove (value_type
*elt
)
309 elt
->equivalences
.release ();
313 /* Global hash table implementing a mapping from invariant values
314 to a list of SSA_NAMEs which have the same value. We might be
315 able to reuse tree-vn for this code. */
316 static hash_table
<val_ssa_equiv_hasher
> val_ssa_equiv
;
318 static void uncprop_into_successor_phis (basic_block
);
320 /* Remove the most recently recorded equivalency for VALUE. */
323 remove_equivalence (tree value
)
325 struct equiv_hash_elt an_equiv_elt
, *an_equiv_elt_p
;
326 equiv_hash_elt
**slot
;
328 an_equiv_elt
.value
= value
;
329 an_equiv_elt
.equivalences
.create (0);
331 slot
= val_ssa_equiv
.find_slot (&an_equiv_elt
, NO_INSERT
);
333 an_equiv_elt_p
= *slot
;
334 an_equiv_elt_p
->equivalences
.pop ();
337 /* Record EQUIVALENCE = VALUE into our hash table. */
340 record_equiv (tree value
, tree equivalence
)
342 equiv_hash_elt
*an_equiv_elt_p
;
343 equiv_hash_elt
**slot
;
345 an_equiv_elt_p
= XNEW (struct equiv_hash_elt
);
346 an_equiv_elt_p
->value
= value
;
347 an_equiv_elt_p
->equivalences
.create (0);
349 slot
= val_ssa_equiv
.find_slot (an_equiv_elt_p
, INSERT
);
352 *slot
= an_equiv_elt_p
;
354 free (an_equiv_elt_p
);
356 an_equiv_elt_p
= *slot
;
358 an_equiv_elt_p
->equivalences
.safe_push (equivalence
);
361 class uncprop_dom_walker
: public dom_walker
364 uncprop_dom_walker (cdi_direction direction
)
365 : dom_walker (direction
)
367 m_equiv_stack
.create (2);
369 ~uncprop_dom_walker ()
371 m_equiv_stack
.release ();
374 virtual void before_dom_children (basic_block
);
375 virtual void after_dom_children (basic_block
);
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 vec
<tree
> m_equiv_stack
;
386 /* Main driver for un-cprop. */
389 tree_ssa_uncprop (void)
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 ();
414 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
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. */
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. */
440 remove_equivalence (value
);
443 /* Unpropagate values from PHI nodes in successor blocks of BB. */
446 uncprop_into_successor_phis (basic_block bb
)
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
))
464 /* Record any equivalency associated with E. */
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
))
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
);
494 struct equiv_hash_elt
*elt
= *slot
;
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
);
515 /* If we had an equivalence associated with this edge, remove it. */
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. */
527 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
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
))
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. */
545 /* This is the first non-loop incoming edge we have found. Record
554 uncprop_dom_walker::before_dom_children (basic_block bb
)
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
);
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
);
579 m_equiv_stack
.safe_push (NULL_TREE
);
581 uncprop_into_successor_phis (bb
);
587 return flag_tree_dom
!= 0;
592 const pass_data pass_data_uncprop
=
594 GIMPLE_PASS
, /* type */
595 "uncprop", /* name */
596 OPTGROUP_NONE
, /* optinfo_flags */
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
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
624 make_pass_uncprop (gcc::context
*ctxt
)
626 return new pass_uncprop (ctxt
);