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
) : dom_walker (direction
) {}
366 virtual void before_dom_children (basic_block
);
367 virtual void after_dom_children (basic_block
);
371 /* As we enter each block we record the value for any edge equivalency
372 leading to this block. If no such edge equivalency exists, then we
373 record NULL. These equivalences are live until we leave the dominator
374 subtree rooted at the block where we record the equivalency. */
375 stack_vec
<tree
, 2> m_equiv_stack
;
378 /* Main driver for un-cprop. */
381 tree_ssa_uncprop (void)
385 associate_equivalences_with_edges ();
387 /* Create our global data structures. */
388 val_ssa_equiv
.create (1024);
390 /* We're going to do a dominator walk, so ensure that we have
391 dominance information. */
392 calculate_dominance_info (CDI_DOMINATORS
);
394 /* Recursively walk the dominator tree undoing unprofitable
395 constant/copy propagations. */
396 uncprop_dom_walker (CDI_DOMINATORS
).walk (cfun
->cfg
->x_entry_block_ptr
);
398 /* we just need to empty elements out of the hash table, and cleanup the
399 AUX field on the edges. */
400 val_ssa_equiv
.dispose ();
406 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
419 /* We have finished processing the dominator children of BB, perform
420 any finalization actions in preparation for leaving this node in
421 the dominator tree. */
424 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
426 /* Pop the topmost value off the equiv stack. */
427 tree value
= m_equiv_stack
.pop ();
429 /* If that value was non-null, then pop the topmost equivalency off
430 its equivalency stack. */
432 remove_equivalence (value
);
435 /* Unpropagate values from PHI nodes in successor blocks of BB. */
438 uncprop_into_successor_phis (basic_block bb
)
443 /* For each successor edge, first temporarily record any equivalence
444 on that edge. Then unpropagate values in any PHI nodes at the
445 destination of the edge. Then remove the temporary equivalence. */
446 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
448 gimple_seq phis
= phi_nodes (e
->dest
);
449 gimple_stmt_iterator gsi
;
451 /* If there are no PHI nodes in this destination, then there is
452 no sense in recording any equivalences. */
453 if (gimple_seq_empty_p (phis
))
456 /* Record any equivalency associated with E. */
459 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
460 record_equiv (equiv
->rhs
, equiv
->lhs
);
463 /* Walk over the PHI nodes, unpropagating values. */
464 for (gsi
= gsi_start (phis
) ; !gsi_end_p (gsi
); gsi_next (&gsi
))
466 gimple phi
= gsi_stmt (gsi
);
467 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
468 tree res
= PHI_RESULT (phi
);
469 equiv_hash_elt an_equiv_elt
;
470 equiv_hash_elt
**slot
;
472 /* If the argument is not an invariant and can be potentially
473 coalesced with the result, then there's no point in
474 un-propagating the argument. */
475 if (!is_gimple_min_invariant (arg
)
476 && gimple_can_coalesce_p (arg
, res
))
479 /* Lookup this argument's value in the hash table. */
480 an_equiv_elt
.value
= arg
;
481 an_equiv_elt
.equivalences
.create (0);
482 slot
= val_ssa_equiv
.find_slot (&an_equiv_elt
, NO_INSERT
);
486 struct equiv_hash_elt
*elt
= *slot
;
489 /* Walk every equivalence with the same value. If we find
490 one that can potentially coalesce with the PHI rsult,
491 then replace the value in the argument with its equivalent
492 SSA_NAME. Use the most recent equivalence as hopefully
493 that results in shortest lifetimes. */
494 for (j
= elt
->equivalences
.length () - 1; j
>= 0; j
--)
496 tree equiv
= elt
->equivalences
[j
];
498 if (gimple_can_coalesce_p (equiv
, res
))
500 SET_PHI_ARG_DEF (phi
, e
->dest_idx
, equiv
);
507 /* If we had an equivalence associated with this edge, remove it. */
510 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
511 remove_equivalence (equiv
->rhs
);
516 /* Ignoring loop backedges, if BB has precisely one incoming edge then
517 return that edge. Otherwise return NULL. */
519 single_incoming_edge_ignoring_loop_edges (basic_block bb
)
525 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
527 /* A loop back edge can be identified by the destination of
528 the edge dominating the source of the edge. */
529 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, e
->dest
))
532 /* If we have already seen a non-loop edge, then we must have
533 multiple incoming non-loop edges and thus we return NULL. */
537 /* This is the first non-loop incoming edge we have found. Record
546 uncprop_dom_walker::before_dom_children (basic_block bb
)
550 bool recorded
= false;
552 /* If this block is dominated by a single incoming edge and that edge
553 has an equivalency, then record the equivalency and push the
554 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
555 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
558 e
= single_incoming_edge_ignoring_loop_edges (bb
);
560 if (e
&& e
->src
== parent
&& e
->aux
)
562 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
564 record_equiv (equiv
->rhs
, equiv
->lhs
);
565 m_equiv_stack
.safe_push (equiv
->rhs
);
571 m_equiv_stack
.safe_push (NULL_TREE
);
573 uncprop_into_successor_phis (bb
);
579 return flag_tree_dom
!= 0;
584 const pass_data pass_data_uncprop
=
586 GIMPLE_PASS
, /* type */
587 "uncprop", /* name */
588 OPTGROUP_NONE
, /* optinfo_flags */
590 true, /* has_execute */
591 TV_TREE_SSA_UNCPROP
, /* tv_id */
592 ( PROP_cfg
| PROP_ssa
), /* properties_required */
593 0, /* properties_provided */
594 0, /* properties_destroyed */
595 0, /* todo_flags_start */
596 TODO_verify_ssa
, /* todo_flags_finish */
599 class pass_uncprop
: public gimple_opt_pass
602 pass_uncprop (gcc::context
*ctxt
)
603 : gimple_opt_pass (pass_data_uncprop
, ctxt
)
606 /* opt_pass methods: */
607 opt_pass
* clone () { return new pass_uncprop (m_ctxt
); }
608 bool gate () { return gate_uncprop (); }
609 unsigned int execute () { return tree_ssa_uncprop (); }
611 }; // class pass_uncprop
616 make_pass_uncprop (gcc::context
*ctxt
)
618 return new pass_uncprop (ctxt
);