OSDN Git Service

2010-01-17 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-uncprop.c
1 /* Routines for discovering and unpropagating edge equivalences.
2    Copyright (C) 2005, 2007, 2008 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       gimple_stmt_iterator gsi = gsi_last_bb (bb);
69       gimple 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 (gsi_end_p (gsi))
74         continue;
75
76       stmt = gsi_stmt (gsi);
77
78       if (!stmt)
79         continue;
80
81       /* A COND_EXPR may create an equivalency in a variety of different
82          ways.  */
83       if (gimple_code (stmt) == GIMPLE_COND)
84         {
85           edge true_edge;
86           edge false_edge;
87           struct edge_equivalency *equivalency;
88           enum tree_code code = gimple_cond_code (stmt);
89
90           extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
91
92           /* Equality tests may create one or two equivalences.  */
93           if (code == EQ_EXPR || code == NE_EXPR)
94             {
95               tree op0 = gimple_cond_lhs (stmt);
96               tree op1 = gimple_cond_rhs (stmt);
97
98               /* Special case comparing booleans against a constant as we
99                  know the value of OP0 on both arms of the branch.  i.e., we
100                  can record an equivalence for OP0 rather than COND.  */
101               if (TREE_CODE (op0) == SSA_NAME
102                   && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
103                   && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
104                   && is_gimple_min_invariant (op1))
105                 {
106                   if (code == EQ_EXPR)
107                     {
108                       equivalency = XNEW (struct edge_equivalency);
109                       equivalency->lhs = op0;
110                       equivalency->rhs = (integer_zerop (op1)
111                                           ? boolean_false_node
112                                           : boolean_true_node);
113                       true_edge->aux = equivalency;
114
115                       equivalency = XNEW (struct edge_equivalency);
116                       equivalency->lhs = op0;
117                       equivalency->rhs = (integer_zerop (op1)
118                                           ? boolean_true_node
119                                           : boolean_false_node);
120                       false_edge->aux = equivalency;
121                     }
122                   else
123                     {
124                       equivalency = XNEW (struct edge_equivalency);
125                       equivalency->lhs = op0;
126                       equivalency->rhs = (integer_zerop (op1)
127                                           ? boolean_true_node
128                                           : boolean_false_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_false_node
135                                           : boolean_true_node);
136                       false_edge->aux = equivalency;
137                     }
138                 }
139
140               else if (TREE_CODE (op0) == SSA_NAME
141                        && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
142                        && (is_gimple_min_invariant (op1)
143                            || (TREE_CODE (op1) == SSA_NAME
144                                && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
145                 {
146                   /* For IEEE, -0.0 == 0.0, so we don't necessarily know
147                      the sign of a variable compared against zero.  If
148                      we're honoring signed zeros, then we cannot record
149                      this value unless we know that the value is nonzero.  */
150                   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0)))
151                       && (TREE_CODE (op1) != REAL_CST
152                           || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (op1))))
153                     continue;
154
155                   equivalency = XNEW (struct edge_equivalency);
156                   equivalency->lhs = op0;
157                   equivalency->rhs = op1;
158                   if (code == EQ_EXPR)
159                     true_edge->aux = equivalency;
160                   else
161                     false_edge->aux = equivalency;
162
163                 }
164             }
165
166           /* ??? TRUTH_NOT_EXPR can create an equivalence too.  */
167         }
168
169       /* For a SWITCH_EXPR, a case label which represents a single
170          value and which is the only case label which reaches the
171          target block creates an equivalence.  */
172       else if (gimple_code (stmt) == GIMPLE_SWITCH)
173         {
174           tree cond = gimple_switch_index (stmt);
175
176           if (TREE_CODE (cond) == SSA_NAME
177               && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
178             {
179               int i, n_labels = gimple_switch_num_labels (stmt);
180               tree *info = XCNEWVEC (tree, last_basic_block);
181
182               /* Walk over the case label vector.  Record blocks
183                  which are reached by a single case label which represents
184                  a single value.  */
185               for (i = 0; i < n_labels; i++)
186                 {
187                   tree label = gimple_switch_label (stmt, i);
188                   basic_block bb = label_to_block (CASE_LABEL (label));
189
190                   if (CASE_HIGH (label)
191                       || !CASE_LOW (label)
192                       || info[bb->index])
193                     info[bb->index] = error_mark_node;
194                   else
195                     info[bb->index] = label;
196                 }
197
198               /* Now walk over the blocks to determine which ones were
199                  marked as being reached by a useful case label.  */
200               for (i = 0; i < n_basic_blocks; i++)
201                 {
202                   tree node = info[i];
203
204                   if (node != NULL
205                       && node != error_mark_node)
206                     {
207                       tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
208                       struct edge_equivalency *equivalency;
209
210                       /* Record an equivalency on the edge from BB to basic
211                          block I.  */
212                       equivalency = XNEW (struct edge_equivalency);
213                       equivalency->rhs = x;
214                       equivalency->lhs = cond;
215                       find_edge (bb, BASIC_BLOCK (i))->aux = equivalency;
216                     }
217                 }
218               free (info);
219             }
220         }
221
222     }
223 }
224
225
226 /* Translating out of SSA sometimes requires inserting copies and
227    constant initializations on edges to eliminate PHI nodes.
228
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.
232
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.
237
238    This pass attempts to detect these situations before translating
239    out of SSA form.
240
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.
245
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.
251
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.
256
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.
260
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
263    the argument.
264
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
269    same value.  */
270
271 /* As we enter each block we record the value for any edge equivalency
272    leading to this block.  If no such edge equivalency exists, then we
273    record NULL.  These equivalences are live until we leave the dominator
274    subtree rooted at the block where we record the equivalency.  */
275 static VEC(tree,heap) *equiv_stack;
276
277 /* Global hash table implementing a mapping from invariant values
278    to a list of SSA_NAMEs which have the same value.  We might be
279    able to reuse tree-vn for this code.  */
280 static htab_t equiv;
281
282 /* Main structure for recording equivalences into our hash table.  */
283 struct equiv_hash_elt
284 {
285   /* The value/key of this entry.  */
286   tree value;
287
288   /* List of SSA_NAMEs which have the same value/key.  */
289   VEC(tree,heap) *equivalences;
290 };
291
292 static void uncprop_enter_block (struct dom_walk_data *, basic_block);
293 static void uncprop_leave_block (struct dom_walk_data *, basic_block);
294 static void uncprop_into_successor_phis (basic_block);
295
296 /* Hashing and equality routines for the hash table.  */
297
298 static hashval_t
299 equiv_hash (const void *p)
300 {
301   tree const value = ((const struct equiv_hash_elt *)p)->value;
302   return iterative_hash_expr (value, 0);
303 }
304
305 static int
306 equiv_eq (const void *p1, const void *p2)
307 {
308   tree value1 = ((const struct equiv_hash_elt *)p1)->value;
309   tree value2 = ((const struct equiv_hash_elt *)p2)->value;
310
311   return operand_equal_p (value1, value2, 0);
312 }
313
314 /* Free an instance of equiv_hash_elt.  */
315
316 static void
317 equiv_free (void *p)
318 {
319   struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
320   VEC_free (tree, heap, elt->equivalences);
321   free (elt);
322 }
323
324 /* Remove the most recently recorded equivalency for VALUE.  */
325
326 static void
327 remove_equivalence (tree value)
328 {
329   struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p;
330   void **slot;
331
332   equiv_hash_elt.value = value;
333   equiv_hash_elt.equivalences = NULL;
334
335   slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
336
337   equiv_hash_elt_p = (struct equiv_hash_elt *) *slot;
338   VEC_pop (tree, equiv_hash_elt_p->equivalences);
339 }
340
341 /* Record EQUIVALENCE = VALUE into our hash table.  */
342
343 static void
344 record_equiv (tree value, tree equivalence)
345 {
346   struct equiv_hash_elt *equiv_hash_elt;
347   void **slot;
348
349   equiv_hash_elt = XNEW (struct equiv_hash_elt);
350   equiv_hash_elt->value = value;
351   equiv_hash_elt->equivalences = NULL;
352
353   slot = htab_find_slot (equiv, equiv_hash_elt, INSERT);
354
355   if (*slot == NULL)
356     *slot = (void *) equiv_hash_elt;
357   else
358      free (equiv_hash_elt);
359
360   equiv_hash_elt = (struct equiv_hash_elt *) *slot;
361
362   VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence);
363 }
364
365 /* Main driver for un-cprop.  */
366
367 static unsigned int
368 tree_ssa_uncprop (void)
369 {
370   struct dom_walk_data walk_data;
371   basic_block bb;
372
373   associate_equivalences_with_edges ();
374
375   /* Create our global data structures.  */
376   equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free);
377   equiv_stack = VEC_alloc (tree, heap, 2);
378
379   /* We're going to do a dominator walk, so ensure that we have
380      dominance information.  */
381   calculate_dominance_info (CDI_DOMINATORS);
382
383   /* Setup callbacks for the generic dominator tree walker.  */
384   walk_data.dom_direction = CDI_DOMINATORS;
385   walk_data.initialize_block_local_data = NULL;
386   walk_data.before_dom_children = uncprop_enter_block;
387   walk_data.after_dom_children = uncprop_leave_block;
388   walk_data.global_data = NULL;
389   walk_data.block_local_data_size = 0;
390
391   /* Now initialize the dominator walker.  */
392   init_walk_dominator_tree (&walk_data);
393
394   /* Recursively walk the dominator tree undoing unprofitable
395      constant/copy propagations.  */
396   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
397
398   /* Finalize and clean up.  */
399   fini_walk_dominator_tree (&walk_data);
400
401   /* EQUIV_STACK should already be empty at this point, so we just
402      need to empty elements out of the hash table, free EQUIV_STACK,
403      and cleanup the AUX field on the edges.  */
404   htab_delete (equiv);
405   VEC_free (tree, heap, equiv_stack);
406   FOR_EACH_BB (bb)
407     {
408       edge e;
409       edge_iterator ei;
410
411       FOR_EACH_EDGE (e, ei, bb->succs)
412         {
413           if (e->aux)
414             {
415               free (e->aux);
416               e->aux = NULL;
417             }
418         }
419     }
420   return 0;
421 }
422
423
424 /* We have finished processing the dominator children of BB, perform
425    any finalization actions in preparation for leaving this node in
426    the dominator tree.  */
427
428 static void
429 uncprop_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
430                      basic_block bb ATTRIBUTE_UNUSED)
431 {
432   /* Pop the topmost value off the equiv stack.  */
433   tree value = VEC_pop (tree, equiv_stack);
434
435   /* If that value was non-null, then pop the topmost equivalency off
436      its equivalency stack.  */
437   if (value != NULL)
438     remove_equivalence (value);
439 }
440
441 /* Unpropagate values from PHI nodes in successor blocks of BB.  */
442
443 static void
444 uncprop_into_successor_phis (basic_block bb)
445 {
446   edge e;
447   edge_iterator ei;
448
449   /* For each successor edge, first temporarily record any equivalence
450      on that edge.  Then unpropagate values in any PHI nodes at the
451      destination of the edge.  Then remove the temporary equivalence.  */
452   FOR_EACH_EDGE (e, ei, bb->succs)
453     {
454       gimple_seq phis = phi_nodes (e->dest);
455       gimple_stmt_iterator gsi;
456
457       /* If there are no PHI nodes in this destination, then there is
458          no sense in recording any equivalences.  */
459       if (gimple_seq_empty_p (phis))
460         continue;
461
462       /* Record any equivalency associated with E.  */
463       if (e->aux)
464         {
465           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
466           record_equiv (equiv->rhs, equiv->lhs);
467         }
468
469       /* Walk over the PHI nodes, unpropagating values.  */
470       for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
471         {
472           gimple phi = gsi_stmt (gsi);
473           tree arg = PHI_ARG_DEF (phi, e->dest_idx);
474           struct equiv_hash_elt equiv_hash_elt;
475           void **slot;
476
477           /* If the argument is not an invariant, or refers to the same
478              underlying variable as the PHI result, then there's no
479              point in un-propagating the argument.  */
480           if (!is_gimple_min_invariant (arg)
481               && SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi)))
482             continue;
483
484           /* Lookup this argument's value in the hash table.  */
485           equiv_hash_elt.value = arg;
486           equiv_hash_elt.equivalences = NULL;
487           slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
488
489           if (slot)
490             {
491               struct equiv_hash_elt *elt = (struct equiv_hash_elt *) *slot;
492               int j;
493
494               /* Walk every equivalence with the same value.  If we find
495                  one with the same underlying variable as the PHI result,
496                  then replace the value in the argument with its equivalent
497                  SSA_NAME.  Use the most recent equivalence as hopefully
498                  that results in shortest lifetimes.  */
499               for (j = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--)
500                 {
501                   tree equiv = VEC_index (tree, elt->equivalences, j);
502
503                   if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi)))
504                     {
505                       SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
506                       break;
507                     }
508                 }
509             }
510         }
511
512       /* If we had an equivalence associated with this edge, remove it.  */
513       if (e->aux)
514         {
515           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
516           remove_equivalence (equiv->rhs);
517         }
518     }
519 }
520
521 /* Ignoring loop backedges, if BB has precisely one incoming edge then
522    return that edge.  Otherwise return NULL.  */
523 static edge
524 single_incoming_edge_ignoring_loop_edges (basic_block bb)
525 {
526   edge retval = NULL;
527   edge e;
528   edge_iterator ei;
529
530   FOR_EACH_EDGE (e, ei, bb->preds)
531     {
532       /* A loop back edge can be identified by the destination of
533          the edge dominating the source of the edge.  */
534       if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
535         continue;
536
537       /* If we have already seen a non-loop edge, then we must have
538          multiple incoming non-loop edges and thus we return NULL.  */
539       if (retval)
540         return NULL;
541
542       /* This is the first non-loop incoming edge we have found.  Record
543          it.  */
544       retval = e;
545     }
546
547   return retval;
548 }
549
550 static void
551 uncprop_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
552                      basic_block bb)
553 {
554   basic_block parent;
555   edge e;
556   bool recorded = false;
557
558   /* If this block is dominated by a single incoming edge and that edge
559      has an equivalency, then record the equivalency and push the
560      VALUE onto EQUIV_STACK.  Else push a NULL entry on EQUIV_STACK.  */
561   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
562   if (parent)
563     {
564       e = single_incoming_edge_ignoring_loop_edges (bb);
565
566       if (e && e->src == parent && e->aux)
567         {
568           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
569
570           record_equiv (equiv->rhs, equiv->lhs);
571           VEC_safe_push (tree, heap, equiv_stack, equiv->rhs);
572           recorded = true;
573         }
574     }
575
576   if (!recorded)
577     VEC_safe_push (tree, heap, equiv_stack, NULL_TREE);
578
579   uncprop_into_successor_phis (bb);
580 }
581
582 static bool
583 gate_uncprop (void)
584 {
585   return flag_tree_dom != 0;
586 }
587
588 struct gimple_opt_pass pass_uncprop =
589 {
590  {
591   GIMPLE_PASS,
592   "uncprop",                            /* name */
593   gate_uncprop,                         /* gate */
594   tree_ssa_uncprop,                     /* execute */
595   NULL,                                 /* sub */
596   NULL,                                 /* next */
597   0,                                    /* static_pass_number */
598   TV_TREE_SSA_UNCPROP,                  /* tv_id */
599   PROP_cfg | PROP_ssa,                  /* properties_required */
600   0,                                    /* properties_provided */
601   0,                                    /* properties_destroyed */
602   0,                                    /* todo_flags_start */
603   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
604  }
605 };
606