1 /* Routines for discovering and unpropagating edge equivalences.
2 Copyright (C) 2005-2018 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"
26 #include "tree-pass.h"
28 #include "fold-const.h"
30 #include "gimple-iterator.h"
33 #include "tree-hash-traits.h"
34 #include "tree-ssa-live.h"
35 #include "tree-ssa-coalesce.h"
37 /* The basic structure describing an equivalency created by traversing
38 an edge. Traversing the edge effectively means that we can assume
39 that we've seen an assignment LHS = RHS. */
40 struct edge_equivalency
46 /* This routine finds and records edge equivalences for every edge
49 When complete, each edge that creates an equivalency will have an
50 EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
51 The caller is responsible for freeing the AUX fields. */
54 associate_equivalences_with_edges (void)
58 /* Walk over each block. If the block ends with a control statement,
59 then it might create a useful equivalence. */
60 FOR_EACH_BB_FN (bb
, cfun
)
62 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
65 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
66 then there is nothing to do. */
70 stmt
= gsi_stmt (gsi
);
75 /* A COND_EXPR may create an equivalency in a variety of different
77 if (gimple_code (stmt
) == GIMPLE_COND
)
81 struct edge_equivalency
*equivalency
;
82 enum tree_code code
= gimple_cond_code (stmt
);
84 extract_true_false_edges_from_block (bb
, &true_edge
, &false_edge
);
86 /* Equality tests may create one or two equivalences. */
87 if (code
== EQ_EXPR
|| code
== NE_EXPR
)
89 tree op0
= gimple_cond_lhs (stmt
);
90 tree op1
= gimple_cond_rhs (stmt
);
92 /* Special case comparing booleans against a constant as we
93 know the value of OP0 on both arms of the branch. i.e., we
94 can record an equivalence for OP0 rather than COND. */
95 if (TREE_CODE (op0
) == SSA_NAME
96 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
)
97 && ssa_name_has_boolean_range (op0
)
98 && is_gimple_min_invariant (op1
)
99 && (integer_zerop (op1
) || integer_onep (op1
)))
101 tree true_val
= constant_boolean_node (true, TREE_TYPE (op0
));
102 tree false_val
= constant_boolean_node (false,
106 equivalency
= XNEW (struct edge_equivalency
);
107 equivalency
->lhs
= op0
;
108 equivalency
->rhs
= (integer_zerop (op1
)
111 true_edge
->aux
= equivalency
;
113 equivalency
= XNEW (struct edge_equivalency
);
114 equivalency
->lhs
= op0
;
115 equivalency
->rhs
= (integer_zerop (op1
)
118 false_edge
->aux
= equivalency
;
122 equivalency
= XNEW (struct edge_equivalency
);
123 equivalency
->lhs
= op0
;
124 equivalency
->rhs
= (integer_zerop (op1
)
127 true_edge
->aux
= equivalency
;
129 equivalency
= XNEW (struct edge_equivalency
);
130 equivalency
->lhs
= op0
;
131 equivalency
->rhs
= (integer_zerop (op1
)
134 false_edge
->aux
= equivalency
;
138 else if (TREE_CODE (op0
) == SSA_NAME
139 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0
)
140 && (is_gimple_min_invariant (op1
)
141 || (TREE_CODE (op1
) == SSA_NAME
142 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1
))))
144 /* For IEEE, -0.0 == 0.0, so we don't necessarily know
145 the sign of a variable compared against zero. If
146 we're honoring signed zeros, then we cannot record
147 this value unless we know that the value is nonzero. */
148 if (HONOR_SIGNED_ZEROS (op0
)
149 && (TREE_CODE (op1
) != REAL_CST
150 || real_equal (&dconst0
, &TREE_REAL_CST (op1
))))
153 equivalency
= XNEW (struct edge_equivalency
);
154 equivalency
->lhs
= op0
;
155 equivalency
->rhs
= op1
;
157 true_edge
->aux
= equivalency
;
159 false_edge
->aux
= equivalency
;
164 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
167 /* For a SWITCH_EXPR, a case label which represents a single
168 value and which is the only case label which reaches the
169 target block creates an equivalence. */
170 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
172 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
173 tree cond
= gimple_switch_index (switch_stmt
);
175 if (TREE_CODE (cond
) == SSA_NAME
176 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond
))
178 int i
, n_labels
= gimple_switch_num_labels (switch_stmt
);
179 tree
*info
= XCNEWVEC (tree
, last_basic_block_for_fn (cfun
));
181 /* Walk over the case label vector. Record blocks
182 which are reached by a single case label which represents
184 for (i
= 0; i
< n_labels
; i
++)
186 tree label
= gimple_switch_label (switch_stmt
, i
);
187 basic_block bb
= label_to_block (CASE_LABEL (label
));
189 if (CASE_HIGH (label
)
192 info
[bb
->index
] = error_mark_node
;
194 info
[bb
->index
] = label
;
197 /* Now walk over the blocks to determine which ones were
198 marked as being reached by a useful case label. */
199 for (i
= 0; i
< n_basic_blocks_for_fn (cfun
); i
++)
204 && node
!= error_mark_node
)
206 tree x
= fold_convert (TREE_TYPE (cond
), CASE_LOW (node
));
207 struct edge_equivalency
*equivalency
;
209 /* Record an equivalency on the edge from BB to basic
211 equivalency
= XNEW (struct edge_equivalency
);
212 equivalency
->rhs
= x
;
213 equivalency
->lhs
= cond
;
214 find_edge (bb
, BASIC_BLOCK_FOR_FN (cfun
, i
))->aux
=
226 /* Translating out of SSA sometimes requires inserting copies and
227 constant initializations on edges to eliminate PHI nodes.
229 In some cases those copies and constant initializations are
230 redundant because the target already has the value on the
231 RHS of the assignment.
233 We previously tried to catch these cases after translating
234 out of SSA form. However, that code often missed cases. Worse
235 yet, the cases it missed were also often missed by the RTL
236 optimizers. Thus the resulting code had redundant instructions.
238 This pass attempts to detect these situations before translating
241 The key concept that this pass is built upon is that these
242 redundant copies and constant initializations often occur
243 due to constant/copy propagating equivalences resulting from
244 COND_EXPRs and SWITCH_EXPRs.
246 We want to do those propagations as they can sometimes allow
247 the SSA optimizers to do a better job. However, in the cases
248 where such propagations do not result in further optimization,
249 we would like to "undo" the propagation to avoid the redundant
250 copies and constant initializations.
252 This pass works by first associating equivalences with edges in
253 the CFG. For example, the edge leading from a SWITCH_EXPR to
254 its associated CASE_LABEL will have an equivalency between
255 SWITCH_COND and the value in the case label.
257 Once we have found the edge equivalences, we proceed to walk
258 the CFG in dominator order. As we traverse edges we record
259 equivalences associated with those edges we traverse.
261 When we encounter a PHI node, we walk its arguments to see if we
262 have an equivalence for the PHI argument. If so, then we replace
265 Equivalences are looked up based on their value (think of it as
266 the RHS of an assignment). A value may be an SSA_NAME or an
267 invariant. We may have several SSA_NAMEs with the same value,
268 so with each value we have a list of SSA_NAMEs that have the
272 /* Main structure for recording equivalences into our hash table. */
273 struct equiv_hash_elt
275 /* The value/key of this entry. */
278 /* List of SSA_NAMEs which have the same value/key. */
279 vec
<tree
> equivalences
;
282 /* Global hash table implementing a mapping from invariant values
283 to a list of SSA_NAMEs which have the same value. We might be
284 able to reuse tree-vn for this code. */
285 static hash_map
<tree
, auto_vec
<tree
> > *val_ssa_equiv
;
287 static void uncprop_into_successor_phis (basic_block
);
289 /* Remove the most recently recorded equivalency for VALUE. */
292 remove_equivalence (tree value
)
294 val_ssa_equiv
->get (value
)->pop ();
297 /* Record EQUIVALENCE = VALUE into our hash table. */
300 record_equiv (tree value
, tree equivalence
)
302 val_ssa_equiv
->get_or_insert (value
).safe_push (equivalence
);
305 class uncprop_dom_walker
: public dom_walker
308 uncprop_dom_walker (cdi_direction direction
) : dom_walker (direction
) {}
310 virtual edge
before_dom_children (basic_block
);
311 virtual void after_dom_children (basic_block
);
315 /* As we enter each block we record the value for any edge equivalency
316 leading to this block. If no such edge equivalency exists, then we
317 record NULL. These equivalences are live until we leave the dominator
318 subtree rooted at the block where we record the equivalency. */
319 auto_vec
<tree
, 2> m_equiv_stack
;
322 /* We have finished processing the dominator children of BB, perform
323 any finalization actions in preparation for leaving this node in
324 the dominator tree. */
327 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED
)
329 /* Pop the topmost value off the equiv stack. */
330 tree value
= m_equiv_stack
.pop ();
332 /* If that value was non-null, then pop the topmost equivalency off
333 its equivalency stack. */
335 remove_equivalence (value
);
338 /* Unpropagate values from PHI nodes in successor blocks of BB. */
341 uncprop_into_successor_phis (basic_block bb
)
346 /* For each successor edge, first temporarily record any equivalence
347 on that edge. Then unpropagate values in any PHI nodes at the
348 destination of the edge. Then remove the temporary equivalence. */
349 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
351 gimple_seq phis
= phi_nodes (e
->dest
);
352 gimple_stmt_iterator gsi
;
354 /* If there are no PHI nodes in this destination, then there is
355 no sense in recording any equivalences. */
356 if (gimple_seq_empty_p (phis
))
359 /* Record any equivalency associated with E. */
362 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
363 record_equiv (equiv
->rhs
, equiv
->lhs
);
366 /* Walk over the PHI nodes, unpropagating values. */
367 for (gsi
= gsi_start (phis
) ; !gsi_end_p (gsi
); gsi_next (&gsi
))
369 gimple
*phi
= gsi_stmt (gsi
);
370 tree arg
= PHI_ARG_DEF (phi
, e
->dest_idx
);
371 tree res
= PHI_RESULT (phi
);
373 /* If the argument is not an invariant and can be potentially
374 coalesced with the result, then there's no point in
375 un-propagating the argument. */
376 if (!is_gimple_min_invariant (arg
)
377 && gimple_can_coalesce_p (arg
, res
))
380 /* Lookup this argument's value in the hash table. */
381 vec
<tree
> *equivalences
= val_ssa_equiv
->get (arg
);
384 /* Walk every equivalence with the same value. If we find
385 one that can potentially coalesce with the PHI rsult,
386 then replace the value in the argument with its equivalent
387 SSA_NAME. Use the most recent equivalence as hopefully
388 that results in shortest lifetimes. */
389 for (int j
= equivalences
->length () - 1; j
>= 0; j
--)
391 tree equiv
= (*equivalences
)[j
];
393 if (gimple_can_coalesce_p (equiv
, res
))
395 SET_PHI_ARG_DEF (phi
, e
->dest_idx
, equiv
);
402 /* If we had an equivalence associated with this edge, remove it. */
405 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
406 remove_equivalence (equiv
->rhs
);
412 uncprop_dom_walker::before_dom_children (basic_block bb
)
415 bool recorded
= false;
417 /* If this block is dominated by a single incoming edge and that edge
418 has an equivalency, then record the equivalency and push the
419 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
420 parent
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
423 edge e
= single_pred_edge_ignoring_loop_edges (bb
, false);
425 if (e
&& e
->src
== parent
&& e
->aux
)
427 struct edge_equivalency
*equiv
= (struct edge_equivalency
*) e
->aux
;
429 record_equiv (equiv
->rhs
, equiv
->lhs
);
430 m_equiv_stack
.safe_push (equiv
->rhs
);
436 m_equiv_stack
.safe_push (NULL_TREE
);
438 uncprop_into_successor_phis (bb
);
444 const pass_data pass_data_uncprop
=
446 GIMPLE_PASS
, /* type */
447 "uncprop", /* name */
448 OPTGROUP_NONE
, /* optinfo_flags */
449 TV_TREE_SSA_UNCPROP
, /* tv_id */
450 ( PROP_cfg
| PROP_ssa
), /* properties_required */
451 0, /* properties_provided */
452 0, /* properties_destroyed */
453 0, /* todo_flags_start */
454 0, /* todo_flags_finish */
457 class pass_uncprop
: public gimple_opt_pass
460 pass_uncprop (gcc::context
*ctxt
)
461 : gimple_opt_pass (pass_data_uncprop
, ctxt
)
464 /* opt_pass methods: */
465 opt_pass
* clone () { return new pass_uncprop (m_ctxt
); }
466 virtual bool gate (function
*) { return flag_tree_dom
!= 0; }
467 virtual unsigned int execute (function
*);
469 }; // class pass_uncprop
472 pass_uncprop::execute (function
*fun
)
476 associate_equivalences_with_edges ();
478 /* Create our global data structures. */
479 val_ssa_equiv
= new hash_map
<tree
, auto_vec
<tree
> > (1024);
481 /* We're going to do a dominator walk, so ensure that we have
482 dominance information. */
483 calculate_dominance_info (CDI_DOMINATORS
);
485 /* Recursively walk the dominator tree undoing unprofitable
486 constant/copy propagations. */
487 uncprop_dom_walker (CDI_DOMINATORS
).walk (fun
->cfg
->x_entry_block_ptr
);
489 /* we just need to empty elements out of the hash table, and cleanup the
490 AUX field on the edges. */
491 delete val_ssa_equiv
;
492 val_ssa_equiv
= NULL
;
493 FOR_EACH_BB_FN (bb
, fun
)
498 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
513 make_pass_uncprop (gcc::context
*ctxt
)
515 return new pass_uncprop (ctxt
);