1 /* Routines for discovering and unpropagating edge equivalences.
2 Copyright (C) 2005 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 2, 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 COPYING. If not, write to
18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19 Boston, MA 02110-1301, USA. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "flags.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "ggc.h"
30 #include "basic-block.h"
31 #include "output.h"
32 #include "expr.h"
33 #include "function.h"
34 #include "diagnostic.h"
35 #include "timevar.h"
36 #include "tree-dump.h"
37 #include "tree-flow.h"
38 #include "domwalk.h"
39 #include "real.h"
40 #include "tree-pass.h"
41 #include "tree-ssa-propagate.h"
42 #include "langhooks.h"
43
44 /* The basic structure describing an equivalency created by traversing
45 an edge. Traversing the edge effectively means that we can assume
46 that we've seen an assignment LHS = RHS. */
47 struct edge_equivalency
48 {
49 tree rhs;
50 tree lhs;
51 };
52
53 /* This routine finds and records edge equivalences for every edge
54 in the CFG.
55
56 When complete, each edge that creates an equivalency will have an
57 EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
58 The caller is responsible for freeing the AUX fields. */
59
60 static void
associate_equivalences_with_edges(void)61 associate_equivalences_with_edges (void)
62 {
63 basic_block bb;
64
65 /* Walk over each block. If the block ends with a control statement,
66 then it might create a useful equivalence. */
67 FOR_EACH_BB (bb)
68 {
69 block_stmt_iterator bsi = bsi_last (bb);
70 tree stmt;
71
72 /* If the block does not end with a COND_EXPR or SWITCH_EXPR
73 then there is nothing to do. */
74 if (bsi_end_p (bsi))
75 continue;
76
77 stmt = bsi_stmt (bsi);
78
79 if (!stmt)
80 continue;
81
82 /* A COND_EXPR may create an equivalency in a variety of different
83 ways. */
84 if (TREE_CODE (stmt) == COND_EXPR)
85 {
86 tree cond = COND_EXPR_COND (stmt);
87 edge true_edge;
88 edge false_edge;
89 struct edge_equivalency *equivalency;
90
91 extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
92
93 /* If the conditional is a single variable 'X', record 'X = 1'
94 for the true edge and 'X = 0' on the false edge. */
95 if (TREE_CODE (cond) == SSA_NAME
96 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
97 {
98 equivalency = XNEW (struct edge_equivalency);
99 equivalency->rhs = constant_boolean_node (1, TREE_TYPE (cond));
100 equivalency->lhs = cond;
101 true_edge->aux = equivalency;
102
103 equivalency = XNEW (struct edge_equivalency);
104 equivalency->rhs = constant_boolean_node (0, TREE_TYPE (cond));
105 equivalency->lhs = cond;
106 false_edge->aux = equivalency;
107 }
108 /* Equality tests may create one or two equivalences. */
109 else if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
110 {
111 tree op0 = TREE_OPERAND (cond, 0);
112 tree op1 = TREE_OPERAND (cond, 1);
113
114 /* Special case comparing booleans against a constant as we
115 know the value of OP0 on both arms of the branch. i.e., we
116 can record an equivalence for OP0 rather than COND. */
117 if (TREE_CODE (op0) == SSA_NAME
118 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
119 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
120 && is_gimple_min_invariant (op1))
121 {
122 if (TREE_CODE (cond) == EQ_EXPR)
123 {
124 equivalency = XNEW (struct edge_equivalency);
125 equivalency->lhs = op0;
126 equivalency->rhs = (integer_zerop (op1)
127 ? boolean_false_node
128 : boolean_true_node);
129 true_edge->aux = equivalency;
130
131 equivalency = XNEW (struct edge_equivalency);
132 equivalency->lhs = op0;
133 equivalency->rhs = (integer_zerop (op1)
134 ? boolean_true_node
135 : boolean_false_node);
136 false_edge->aux = equivalency;
137 }
138 else
139 {
140 equivalency = XNEW (struct edge_equivalency);
141 equivalency->lhs = op0;
142 equivalency->rhs = (integer_zerop (op1)
143 ? boolean_true_node
144 : boolean_false_node);
145 true_edge->aux = equivalency;
146
147 equivalency = XNEW (struct edge_equivalency);
148 equivalency->lhs = op0;
149 equivalency->rhs = (integer_zerop (op1)
150 ? boolean_false_node
151 : boolean_true_node);
152 false_edge->aux = equivalency;
153 }
154 }
155
156 if (TREE_CODE (op0) == SSA_NAME
157 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
158 && (is_gimple_min_invariant (op1)
159 || (TREE_CODE (op1) == SSA_NAME
160 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
161 {
162 /* For IEEE, -0.0 == 0.0, so we don't necessarily know
163 the sign of a variable compared against zero. If
164 we're honoring signed zeros, then we cannot record
165 this value unless we know that the value is nonzero. */
166 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
167 && (TREE_CODE (op1) != REAL_CST
168 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
169 continue;
170
171 equivalency = XNEW (struct edge_equivalency);
172 equivalency->lhs = op0;
173 equivalency->rhs = op1;
174 if (TREE_CODE (cond) == EQ_EXPR)
175 true_edge->aux = equivalency;
176 else
177 false_edge->aux = equivalency;
178
179 }
180 }
181
182 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */
183 }
184
185 /* For a SWITCH_EXPR, a case label which represents a single
186 value and which is the only case label which reaches the
187 target block creates an equivalence. */
188 if (TREE_CODE (stmt) == SWITCH_EXPR)
189 {
190 tree cond = SWITCH_COND (stmt);
191
192 if (TREE_CODE (cond) == SSA_NAME
193 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
194 {
195 tree labels = SWITCH_LABELS (stmt);
196 int i, n_labels = TREE_VEC_LENGTH (labels);
197 tree *info = XCNEWVEC (tree, n_basic_blocks);
198
199 /* Walk over the case label vector. Record blocks
200 which are reached by a single case label which represents
201 a single value. */
202 for (i = 0; i < n_labels; i++)
203 {
204 tree label = TREE_VEC_ELT (labels, i);
205 basic_block bb = label_to_block (CASE_LABEL (label));
206
207
208 if (CASE_HIGH (label)
209 || !CASE_LOW (label)
210 || info[bb->index])
211 info[bb->index] = error_mark_node;
212 else
213 info[bb->index] = label;
214 }
215
216 /* Now walk over the blocks to determine which ones were
217 marked as being reached by a useful case label. */
218 for (i = 0; i < n_basic_blocks; i++)
219 {
220 tree node = info[i];
221
222 if (node != NULL
223 && node != error_mark_node)
224 {
225 tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
226 struct edge_equivalency *equivalency;
227
228 /* Record an equivalency on the edge from BB to basic
229 block I. */
230 equivalency = XNEW (struct edge_equivalency);
231 equivalency->rhs = x;
232 equivalency->lhs = cond;
233 find_edge (bb, BASIC_BLOCK (i))->aux = equivalency;
234 }
235 }
236 free (info);
237 }
238 }
239
240 }
241 }
242
243
244 /* Translating out of SSA sometimes requires inserting copies and
245 constant initializations on edges to eliminate PHI nodes.
246
247 In some cases those copies and constant initializations are
248 redundant because the target already has the value on the
249 RHS of the assignment.
250
251 We previously tried to catch these cases after translating
252 out of SSA form. However, that code often missed cases. Worse
253 yet, the cases it missed were also often missed by the RTL
254 optimizers. Thus the resulting code had redundant instructions.
255
256 This pass attempts to detect these situations before translating
257 out of SSA form.
258
259 The key concept that this pass is built upon is that these
260 redundant copies and constant initializations often occur
261 due to constant/copy propagating equivalences resulting from
262 COND_EXPRs and SWITCH_EXPRs.
263
264 We want to do those propagations as they can sometimes allow
265 the SSA optimizers to do a better job. However, in the cases
266 where such propagations do not result in further optimization,
267 we would like to "undo" the propagation to avoid the redundant
268 copies and constant initializations.
269
270 This pass works by first associating equivalences with edges in
271 the CFG. For example, the edge leading from a SWITCH_EXPR to
272 its associated CASE_LABEL will have an equivalency between
273 SWITCH_COND and the value in the case label.
274
275 Once we have found the edge equivalences, we proceed to walk
276 the CFG in dominator order. As we traverse edges we record
277 equivalences associated with those edges we traverse.
278
279 When we encounter a PHI node, we walk its arguments to see if we
280 have an equivalence for the PHI argument. If so, then we replace
281 the argument.
282
283 Equivalences are looked up based on their value (think of it as
284 the RHS of an assignment). A value may be an SSA_NAME or an
285 invariant. We may have several SSA_NAMEs with the same value,
286 so with each value we have a list of SSA_NAMEs that have the
287 same value. */
288
289 /* As we enter each block we record the value for any edge equivalency
290 leading to this block. If no such edge equivalency exists, then we
291 record NULL. These equivalences are live until we leave the dominator
292 subtree rooted at the block where we record the equivalency. */
VEC(tree,heap)293 static VEC(tree,heap) *equiv_stack;
294
295 /* Global hash table implementing a mapping from invariant values
296 to a list of SSA_NAMEs which have the same value. We might be
297 able to reuse tree-vn for this code. */
298 static htab_t equiv;
299
300 /* Main structure for recording equivalences into our hash table. */
301 struct equiv_hash_elt
302 {
303 /* The value/key of this entry. */
304 tree value;
305
306 /* List of SSA_NAMEs which have the same value/key. */
307 VEC(tree,heap) *equivalences;
308 };
309
310 static void uncprop_initialize_block (struct dom_walk_data *, basic_block);
311 static void uncprop_finalize_block (struct dom_walk_data *, basic_block);
312 static void uncprop_into_successor_phis (struct dom_walk_data *, basic_block);
313
314 /* Hashing and equality routines for the hash table. */
315
316 static hashval_t
equiv_hash(const void * p)317 equiv_hash (const void *p)
318 {
319 tree value = ((struct equiv_hash_elt *)p)->value;
320 return iterative_hash_expr (value, 0);
321 }
322
323 static int
equiv_eq(const void * p1,const void * p2)324 equiv_eq (const void *p1, const void *p2)
325 {
326 tree value1 = ((struct equiv_hash_elt *)p1)->value;
327 tree value2 = ((struct equiv_hash_elt *)p2)->value;
328
329 return operand_equal_p (value1, value2, 0);
330 }
331
332 /* Free an instance of equiv_hash_elt. */
333
334 static void
equiv_free(void * p)335 equiv_free (void *p)
336 {
337 struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
338 VEC_free (tree, heap, elt->equivalences);
339 free (elt);
340 }
341
342 /* Remove the most recently recorded equivalency for VALUE. */
343
344 static void
remove_equivalence(tree value)345 remove_equivalence (tree value)
346 {
347 struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p;
348 void **slot;
349
350 equiv_hash_elt.value = value;
351 equiv_hash_elt.equivalences = NULL;
352
353 slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
354
355 equiv_hash_elt_p = (struct equiv_hash_elt *) *slot;
356 VEC_pop (tree, equiv_hash_elt_p->equivalences);
357 }
358
359 /* Record EQUIVALENCE = VALUE into our hash table. */
360
361 static void
record_equiv(tree value,tree equivalence)362 record_equiv (tree value, tree equivalence)
363 {
364 struct equiv_hash_elt *equiv_hash_elt;
365 void **slot;
366
367 equiv_hash_elt = XNEW (struct equiv_hash_elt);
368 equiv_hash_elt->value = value;
369 equiv_hash_elt->equivalences = NULL;
370
371 slot = htab_find_slot (equiv, equiv_hash_elt, INSERT);
372
373 if (*slot == NULL)
374 *slot = (void *) equiv_hash_elt;
375 else
376 free (equiv_hash_elt);
377
378 equiv_hash_elt = (struct equiv_hash_elt *) *slot;
379
380 VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence);
381 }
382
383 /* Main driver for un-cprop. */
384
385 static unsigned int
tree_ssa_uncprop(void)386 tree_ssa_uncprop (void)
387 {
388 struct dom_walk_data walk_data;
389 basic_block bb;
390
391 associate_equivalences_with_edges ();
392
393 /* Create our global data structures. */
394 equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free);
395 equiv_stack = VEC_alloc (tree, heap, 2);
396
397 /* We're going to do a dominator walk, so ensure that we have
398 dominance information. */
399 calculate_dominance_info (CDI_DOMINATORS);
400
401 /* Setup callbacks for the generic dominator tree walker. */
402 walk_data.walk_stmts_backward = false;
403 walk_data.dom_direction = CDI_DOMINATORS;
404 walk_data.initialize_block_local_data = NULL;
405 walk_data.before_dom_children_before_stmts = uncprop_initialize_block;
406 walk_data.before_dom_children_walk_stmts = NULL;
407 walk_data.before_dom_children_after_stmts = uncprop_into_successor_phis;
408 walk_data.after_dom_children_before_stmts = NULL;
409 walk_data.after_dom_children_walk_stmts = NULL;
410 walk_data.after_dom_children_after_stmts = uncprop_finalize_block;
411 walk_data.global_data = NULL;
412 walk_data.block_local_data_size = 0;
413 walk_data.interesting_blocks = NULL;
414
415 /* Now initialize the dominator walker. */
416 init_walk_dominator_tree (&walk_data);
417
418 /* Recursively walk the dominator tree undoing unprofitable
419 constant/copy propagations. */
420 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
421
422 /* Finalize and clean up. */
423 fini_walk_dominator_tree (&walk_data);
424
425 /* EQUIV_STACK should already be empty at this point, so we just
426 need to empty elements out of the hash table, free EQUIV_STACK,
427 and cleanup the AUX field on the edges. */
428 htab_delete (equiv);
429 VEC_free (tree, heap, equiv_stack);
430 FOR_EACH_BB (bb)
431 {
432 edge e;
433 edge_iterator ei;
434
435 FOR_EACH_EDGE (e, ei, bb->succs)
436 {
437 if (e->aux)
438 {
439 free (e->aux);
440 e->aux = NULL;
441 }
442 }
443 }
444 return 0;
445 }
446
447
448 /* We have finished processing the dominator children of BB, perform
449 any finalization actions in preparation for leaving this node in
450 the dominator tree. */
451
452 static void
uncprop_finalize_block(struct dom_walk_data * walk_data ATTRIBUTE_UNUSED,basic_block bb ATTRIBUTE_UNUSED)453 uncprop_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
454 basic_block bb ATTRIBUTE_UNUSED)
455 {
456 /* Pop the topmost value off the equiv stack. */
457 tree value = VEC_pop (tree, equiv_stack);
458
459 /* If that value was non-null, then pop the topmost equivalency off
460 its equivalency stack. */
461 if (value != NULL)
462 remove_equivalence (value);
463 }
464
465 /* Unpropagate values from PHI nodes in successor blocks of BB. */
466
467 static void
uncprop_into_successor_phis(struct dom_walk_data * walk_data ATTRIBUTE_UNUSED,basic_block bb)468 uncprop_into_successor_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
469 basic_block bb)
470 {
471 edge e;
472 edge_iterator ei;
473
474 /* For each successor edge, first temporarily record any equivalence
475 on that edge. Then unpropagate values in any PHI nodes at the
476 destination of the edge. Then remove the temporary equivalence. */
477 FOR_EACH_EDGE (e, ei, bb->succs)
478 {
479 tree phi = phi_nodes (e->dest);
480
481 /* If there are no PHI nodes in this destination, then there is
482 no sense in recording any equivalences. */
483 if (!phi)
484 continue;
485
486 /* Record any equivalency associated with E. */
487 if (e->aux)
488 {
489 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
490 record_equiv (equiv->rhs, equiv->lhs);
491 }
492
493 /* Walk over the PHI nodes, unpropagating values. */
494 for ( ; phi; phi = PHI_CHAIN (phi))
495 {
496 /* Sigh. We'll have more efficient access to this one day. */
497 tree arg = PHI_ARG_DEF (phi, e->dest_idx);
498 struct equiv_hash_elt equiv_hash_elt;
499 void **slot;
500
501 /* If the argument is not an invariant, or refers to the same
502 underlying variable as the PHI result, then there's no
503 point in un-propagating the argument. */
504 if (!is_gimple_min_invariant (arg)
505 && SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi)))
506 continue;
507
508 /* Lookup this argument's value in the hash table. */
509 equiv_hash_elt.value = arg;
510 equiv_hash_elt.equivalences = NULL;
511 slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
512
513 if (slot)
514 {
515 struct equiv_hash_elt *elt = (struct equiv_hash_elt *) *slot;
516 int j;
517
518 /* Walk every equivalence with the same value. If we find
519 one with the same underlying variable as the PHI result,
520 then replace the value in the argument with its equivalent
521 SSA_NAME. Use the most recent equivalence as hopefully
522 that results in shortest lifetimes. */
523 for (j = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--)
524 {
525 tree equiv = VEC_index (tree, elt->equivalences, j);
526
527 if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi)))
528 {
529 SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
530 break;
531 }
532 }
533 }
534 }
535
536 /* If we had an equivalence associated with this edge, remove it. */
537 if (e->aux)
538 {
539 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
540 remove_equivalence (equiv->rhs);
541 }
542 }
543 }
544
545 /* Ignoring loop backedges, if BB has precisely one incoming edge then
546 return that edge. Otherwise return NULL. */
547 static edge
single_incoming_edge_ignoring_loop_edges(basic_block bb)548 single_incoming_edge_ignoring_loop_edges (basic_block bb)
549 {
550 edge retval = NULL;
551 edge e;
552 edge_iterator ei;
553
554 FOR_EACH_EDGE (e, ei, bb->preds)
555 {
556 /* A loop back edge can be identified by the destination of
557 the edge dominating the source of the edge. */
558 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
559 continue;
560
561 /* If we have already seen a non-loop edge, then we must have
562 multiple incoming non-loop edges and thus we return NULL. */
563 if (retval)
564 return NULL;
565
566 /* This is the first non-loop incoming edge we have found. Record
567 it. */
568 retval = e;
569 }
570
571 return retval;
572 }
573
574 static void
uncprop_initialize_block(struct dom_walk_data * walk_data ATTRIBUTE_UNUSED,basic_block bb)575 uncprop_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
576 basic_block bb)
577 {
578 basic_block parent;
579 edge e;
580 bool recorded = false;
581
582 /* If this block is dominated by a single incoming edge and that edge
583 has an equivalency, then record the equivalency and push the
584 VALUE onto EQUIV_STACK. Else push a NULL entry on EQUIV_STACK. */
585 parent = get_immediate_dominator (CDI_DOMINATORS, bb);
586 if (parent)
587 {
588 e = single_incoming_edge_ignoring_loop_edges (bb);
589
590 if (e && e->src == parent && e->aux)
591 {
592 struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
593
594 record_equiv (equiv->rhs, equiv->lhs);
595 VEC_safe_push (tree, heap, equiv_stack, equiv->rhs);
596 recorded = true;
597 }
598 }
599
600 if (!recorded)
601 VEC_safe_push (tree, heap, equiv_stack, NULL_TREE);
602 }
603
604 static bool
gate_uncprop(void)605 gate_uncprop (void)
606 {
607 return flag_tree_dom != 0;
608 }
609
610 struct tree_opt_pass pass_uncprop =
611 {
612 "uncprop", /* name */
613 gate_uncprop, /* gate */
614 tree_ssa_uncprop, /* execute */
615 NULL, /* sub */
616 NULL, /* next */
617 0, /* static_pass_number */
618 TV_TREE_SSA_UNCPROP, /* tv_id */
619 PROP_cfg | PROP_ssa, /* properties_required */
620 0, /* properties_provided */
621 0, /* properties_destroyed */
622 0, /* todo_flags_start */
623 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */
624 0 /* letter */
625 };
626