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