1 /* Routines for discovering and unpropagating edge equivalences.
2 Copyright (C) 2005-2014 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
19
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"
44
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
49 {
50 tree rhs;
51 tree lhs;
52 };
53
54 /* This routine finds and records edge equivalences for every edge
55 in the CFG.
56
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. */
60
61 static void
associate_equivalences_with_edges(void)62 associate_equivalences_with_edges (void)
63 {
64 basic_block bb;
65
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)
69 {
70 gimple_stmt_iterator gsi = gsi_last_bb (bb);
71 gimple stmt;
72
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;
77
78 stmt = gsi_stmt (gsi);
79
80 if (!stmt)
81 continue;
82
83 /* A COND_EXPR may create an equivalency in a variety of different
84 ways. */
85 if (gimple_code (stmt) == GIMPLE_COND)
86 {
87 edge true_edge;
88 edge false_edge;
89 struct edge_equivalency *equivalency;
90 enum tree_code code = gimple_cond_code (stmt);
91
92 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
93
94 /* Equality tests may create one or two equivalences. */
95 if (code == EQ_EXPR || code == NE_EXPR)
96 {
97 tree op0 = gimple_cond_lhs (stmt);
98 tree op1 = gimple_cond_rhs (stmt);
99
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))
107 {
108 if (code == EQ_EXPR)
109 {
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;
116
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;
123 }
124 else
125 {
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;
132
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;
139 }
140 }
141
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))))
147 {
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;
156
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;
164
165 }
166 }
167
168 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
169 }
170
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)
175 {
176 tree cond = gimple_switch_index (stmt);
177
178 if (TREE_CODE (cond) == SSA_NAME
179 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
180 {
181 int i, n_labels = gimple_switch_num_labels (stmt);
182 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
183
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++)
188 {
189 tree label = gimple_switch_label (stmt, i);
190 basic_block bb = label_to_block (CASE_LABEL (label));
191
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;
198 }
199
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++)
203 {
204 tree node = info[i];
205
206 if (node != NULL
207 && node != error_mark_node)
208 {
209 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
210 struct edge_equivalency *equivalency;
211
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;
219 }
220 }
221 free (info);
222 }
223 }
224
225 }
226 }
227
228
229 /* Translating out of SSA sometimes requires inserting copies and
230 constant initializations on edges to eliminate PHI nodes.
231
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.
235
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.
240
241 This pass attempts to detect these situations before translating
242 out of SSA form.
243
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.
248
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.
254
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.
259
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.
263
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.
267
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. */
273
274
275 /* Main structure for recording equivalences into our hash table. */
276 struct equiv_hash_elt
277 {
278 /* The value/key of this entry. */
279 tree value;
280
281 /* List of SSA_NAMEs which have the same value/key. */
282 vec<tree> equivalences;
283 };
284
285 /* Value to ssa name equivalence hashtable helpers. */
286
287 struct val_ssa_equiv_hasher
288 {
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 *);
294 };
295
296 inline hashval_t
hash(const value_type * p)297 val_ssa_equiv_hasher::hash (const value_type *p)
298 {
299 tree const value = p->value;
300 return iterative_hash_expr (value, 0);
301 }
302
303 inline bool
equal(const value_type * p1,const compare_type * p2)304 val_ssa_equiv_hasher::equal (const value_type *p1, const compare_type *p2)
305 {
306 tree value1 = p1->value;
307 tree value2 = p2->value;
308
309 return operand_equal_p (value1, value2, 0);
310 }
311
312 /* Free an instance of equiv_hash_elt. */
313
314 inline void
remove(value_type * elt)315 val_ssa_equiv_hasher::remove (value_type *elt)
316 {
317 elt->equivalences.release ();
318 free (elt);
319 }
320
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;
325
326 static void uncprop_into_successor_phis (basic_block);
327
328 /* Remove the most recently recorded equivalency for VALUE. */
329
330 static void
remove_equivalence(tree value)331 remove_equivalence (tree value)
332 {
333 struct equiv_hash_elt an_equiv_elt, *an_equiv_elt_p;
334 equiv_hash_elt **slot;
335
336 an_equiv_elt.value = value;
337 an_equiv_elt.equivalences.create (0);
338
339 slot = val_ssa_equiv.find_slot (&an_equiv_elt, NO_INSERT);
340
341 an_equiv_elt_p = *slot;
342 an_equiv_elt_p->equivalences.pop ();
343 }
344
345 /* Record EQUIVALENCE = VALUE into our hash table. */
346
347 static void
record_equiv(tree value,tree equivalence)348 record_equiv (tree value, tree equivalence)
349 {
350 equiv_hash_elt *an_equiv_elt_p;
351 equiv_hash_elt **slot;
352
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);
356
357 slot = val_ssa_equiv.find_slot (an_equiv_elt_p, INSERT);
358
359 if (*slot == NULL)
360 *slot = an_equiv_elt_p;
361 else
362 free (an_equiv_elt_p);
363
364 an_equiv_elt_p = *slot;
365
366 an_equiv_elt_p->equivalences.safe_push (equivalence);
367 }
368
369 class uncprop_dom_walker : public dom_walker
370 {
371 public:
uncprop_dom_walker(cdi_direction direction)372 uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
373
374 virtual void before_dom_children (basic_block);
375 virtual void after_dom_children (basic_block);
376
377 private:
378
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;
384 };
385
386 /* Main driver for un-cprop. */
387
388 static unsigned int
tree_ssa_uncprop(void)389 tree_ssa_uncprop (void)
390 {
391 basic_block bb;
392
393 associate_equivalences_with_edges ();
394
395 /* Create our global data structures. */
396 val_ssa_equiv.create (1024);
397
398 /* We're going to do a dominator walk, so ensure that we have
399 dominance information. */
400 calculate_dominance_info (CDI_DOMINATORS);
401
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);
405
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)
410 {
411 edge e;
412 edge_iterator ei;
413
414 FOR_EACH_EDGE (e, ei, bb->succs)
415 {
416 if (e->aux)
417 {
418 free (e->aux);
419 e->aux = NULL;
420 }
421 }
422 }
423 return 0;
424 }
425
426
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. */
430
431 void
after_dom_children(basic_block bb ATTRIBUTE_UNUSED)432 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
433 {
434 /* Pop the topmost value off the equiv stack. */
435 tree value = m_equiv_stack.pop ();
436
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);
441 }
442
443 /* Unpropagate values from PHI nodes in successor blocks of BB. */
444
445 static void
uncprop_into_successor_phis(basic_block bb)446 uncprop_into_successor_phis (basic_block bb)
447 {
448 edge e;
449 edge_iterator ei;
450
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)
455 {
456 gimple_seq phis = phi_nodes (e->dest);
457 gimple_stmt_iterator gsi;
458
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;
463
464 /* Record any equivalency associated with E. */
465 if (e->aux)
466 {
467 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
468 record_equiv (equiv->rhs, equiv->lhs);
469 }
470
471 /* Walk over the PHI nodes, unpropagating values. */
472 for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
473 {
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;
479
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;
486
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);
491
492 if (slot)
493 {
494 struct equiv_hash_elt *elt = *slot;
495 int j;
496
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--)
503 {
504 tree equiv = elt->equivalences[j];
505
506 if (gimple_can_coalesce_p (equiv, res))
507 {
508 SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
509 break;
510 }
511 }
512 }
513 }
514
515 /* If we had an equivalence associated with this edge, remove it. */
516 if (e->aux)
517 {
518 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
519 remove_equivalence (equiv->rhs);
520 }
521 }
522 }
523
524 /* Ignoring loop backedges, if BB has precisely one incoming edge then
525 return that edge. Otherwise return NULL. */
526 static edge
single_incoming_edge_ignoring_loop_edges(basic_block bb)527 single_incoming_edge_ignoring_loop_edges (basic_block bb)
528 {
529 edge retval = NULL;
530 edge e;
531 edge_iterator ei;
532
533 FOR_EACH_EDGE (e, ei, bb->preds)
534 {
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;
539
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;
544
545 /* This is the first non-loop incoming edge we have found. Record
546 it. */
547 retval = e;
548 }
549
550 return retval;
551 }
552
553 void
before_dom_children(basic_block bb)554 uncprop_dom_walker::before_dom_children (basic_block bb)
555 {
556 basic_block parent;
557 edge e;
558 bool recorded = false;
559
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)
565 {
566 e = single_incoming_edge_ignoring_loop_edges (bb);
567
568 if (e && e->src == parent && e->aux)
569 {
570 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
571
572 record_equiv (equiv->rhs, equiv->lhs);
573 m_equiv_stack.safe_push (equiv->rhs);
574 recorded = true;
575 }
576 }
577
578 if (!recorded)
579 m_equiv_stack.safe_push (NULL_TREE);
580
581 uncprop_into_successor_phis (bb);
582 }
583
584 static bool
gate_uncprop(void)585 gate_uncprop (void)
586 {
587 return flag_tree_dom != 0;
588 }
589
590 namespace {
591
592 const pass_data pass_data_uncprop =
593 {
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 */
605 };
606
607 class pass_uncprop : public gimple_opt_pass
608 {
609 public:
pass_uncprop(gcc::context * ctxt)610 pass_uncprop (gcc::context *ctxt)
611 : gimple_opt_pass (pass_data_uncprop, ctxt)
612 {}
613
614 /* opt_pass methods: */
clone()615 opt_pass * clone () { return new pass_uncprop (m_ctxt); }
gate()616 bool gate () { return gate_uncprop (); }
execute()617 unsigned int execute () { return tree_ssa_uncprop (); }
618
619 }; // class pass_uncprop
620
621 } // anon namespace
622
623 gimple_opt_pass *
make_pass_uncprop(gcc::context * ctxt)624 make_pass_uncprop (gcc::context *ctxt)
625 {
626 return new pass_uncprop (ctxt);
627 }
628