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