Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / tree-ssa-copyrename.c
1 /* Rename SSA copies.
2    Copyright (C) 2004-2015 Free Software Foundation, Inc.
3    Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "hash-set.h"
26 #include "machmode.h"
27 #include "vec.h"
28 #include "double-int.h"
29 #include "input.h"
30 #include "alias.h"
31 #include "symtab.h"
32 #include "wide-int.h"
33 #include "inchash.h"
34 #include "tree.h"
35 #include "fold-const.h"
36 #include "predict.h"
37 #include "hard-reg-set.h"
38 #include "function.h"
39 #include "dominance.h"
40 #include "cfg.h"
41 #include "basic-block.h"
42 #include "tree-ssa-alias.h"
43 #include "internal-fn.h"
44 #include "gimple-expr.h"
45 #include "is-a.h"
46 #include "gimple.h"
47 #include "gimple-iterator.h"
48 #include "flags.h"
49 #include "tree-pretty-print.h"
50 #include "bitmap.h"
51 #include "gimple-ssa.h"
52 #include "stringpool.h"
53 #include "tree-ssanames.h"
54 #include "hashtab.h"
55 #include "rtl.h"
56 #include "statistics.h"
57 #include "real.h"
58 #include "fixed-value.h"
59 #include "insn-config.h"
60 #include "expmed.h"
61 #include "dojump.h"
62 #include "explow.h"
63 #include "calls.h"
64 #include "emit-rtl.h"
65 #include "varasm.h"
66 #include "stmt.h"
67 #include "expr.h"
68 #include "tree-dfa.h"
69 #include "tree-inline.h"
70 #include "tree-ssa-live.h"
71 #include "tree-pass.h"
72 #include "langhooks.h"
73
74 static struct
75 {
76   /* Number of copies coalesced.  */
77   int coalesced;
78 } stats;
79
80 /* The following routines implement the SSA copy renaming phase.
81
82    This optimization looks for copies between 2 SSA_NAMES, either through a
83    direct copy, or an implicit one via a PHI node result and its arguments.
84
85    Each copy is examined to determine if it is possible to rename the base
86    variable of one of the operands to the same variable as the other operand.
87    i.e.
88    T.3_5 = <blah>
89    a_1 = T.3_5
90
91    If this copy couldn't be copy propagated, it could possibly remain in the
92    program throughout the optimization phases.   After SSA->normal, it would
93    become:
94
95    T.3 = <blah>
96    a = T.3
97
98    Since T.3_5 is distinct from all other SSA versions of T.3, there is no
99    fundamental reason why the base variable needs to be T.3, subject to
100    certain restrictions.  This optimization attempts to determine if we can
101    change the base variable on copies like this, and result in code such as:
102
103    a_5 = <blah>
104    a_1 = a_5
105
106    This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
107    possible, the copy goes away completely. If it isn't possible, a new temp
108    will be created for a_5, and you will end up with the exact same code:
109
110    a.8 = <blah>
111    a = a.8
112
113    The other benefit of performing this optimization relates to what variables
114    are chosen in copies.  Gimplification of the program uses temporaries for
115    a lot of things. expressions like
116
117    a_1 = <blah>
118    <blah2> = a_1
119
120    get turned into
121
122    T.3_5 = <blah>
123    a_1 = T.3_5
124    <blah2> = a_1
125
126    Copy propagation is done in a forward direction, and if we can propagate
127    through the copy, we end up with:
128
129    T.3_5 = <blah>
130    <blah2> = T.3_5
131
132    The copy is gone, but so is all reference to the user variable 'a'. By
133    performing this optimization, we would see the sequence:
134
135    a_5 = <blah>
136    a_1 = a_5
137    <blah2> = a_1
138
139    which copy propagation would then turn into:
140
141    a_5 = <blah>
142    <blah2> = a_5
143
144    and so we still retain the user variable whenever possible.  */
145
146
147 /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
148    Choose a representative for the partition, and send debug info to DEBUG.  */
149
150 static void
151 copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
152 {
153   int p1, p2, p3;
154   tree root1, root2;
155   tree rep1, rep2;
156   bool ign1, ign2, abnorm;
157
158   gcc_assert (TREE_CODE (var1) == SSA_NAME);
159   gcc_assert (TREE_CODE (var2) == SSA_NAME);
160
161   register_ssa_partition (map, var1);
162   register_ssa_partition (map, var2);
163
164   p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
165   p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
166
167   if (debug)
168     {
169       fprintf (debug, "Try : ");
170       print_generic_expr (debug, var1, TDF_SLIM);
171       fprintf (debug, "(P%d) & ", p1);
172       print_generic_expr (debug, var2, TDF_SLIM);
173       fprintf (debug, "(P%d)", p2);
174     }
175
176   gcc_assert (p1 != NO_PARTITION);
177   gcc_assert (p2 != NO_PARTITION);
178
179   if (p1 == p2)
180     {
181       if (debug)
182         fprintf (debug, " : Already coalesced.\n");
183       return;
184     }
185
186   rep1 = partition_to_var (map, p1);
187   rep2 = partition_to_var (map, p2);
188   root1 = SSA_NAME_VAR (rep1);
189   root2 = SSA_NAME_VAR (rep2);
190   if (!root1 && !root2)
191     return;
192
193   /* Don't coalesce if one of the variables occurs in an abnormal PHI.  */
194   abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
195             || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
196   if (abnorm)
197     {
198       if (debug)
199         fprintf (debug, " : Abnormal PHI barrier.  No coalesce.\n");
200       return;
201     }
202
203   /* Partitions already have the same root, simply merge them.  */
204   if (root1 == root2)
205     {
206       p1 = partition_union (map->var_partition, p1, p2);
207       if (debug)
208         fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
209       return;
210     }
211
212   /* Never attempt to coalesce 2 different parameters.  */
213   if ((root1 && TREE_CODE (root1) == PARM_DECL)
214       && (root2 && TREE_CODE (root2) == PARM_DECL))
215     {
216       if (debug)
217         fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
218       return;
219     }
220
221   if ((root1 && TREE_CODE (root1) == RESULT_DECL)
222       != (root2 && TREE_CODE (root2) == RESULT_DECL))
223     {
224       if (debug)
225         fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
226       return;
227     }
228
229   ign1 = !root1 || (TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1));
230   ign2 = !root2 || (TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2));
231
232   /* Refrain from coalescing user variables, if requested.  */
233   if (!ign1 && !ign2)
234     {
235       if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root2))
236         ign2 = true;
237       else if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root1))
238         ign1 = true;
239       else if (flag_ssa_coalesce_vars != 2)
240         {
241           if (debug)
242             fprintf (debug, " : 2 different USER vars. No coalesce.\n");
243           return;
244         }
245       else
246         ign2 = true;
247     }
248
249   /* If both values have default defs, we can't coalesce.  If only one has a
250      tag, make sure that variable is the new root partition.  */
251   if (root1 && ssa_default_def (cfun, root1))
252     {
253       if (root2 && ssa_default_def (cfun, root2))
254         {
255           if (debug)
256             fprintf (debug, " : 2 default defs. No coalesce.\n");
257           return;
258         }
259       else
260         {
261           ign2 = true;
262           ign1 = false;
263         }
264     }
265   else if (root2 && ssa_default_def (cfun, root2))
266     {
267       ign1 = true;
268       ign2 = false;
269     }
270
271   /* Do not coalesce if we cannot assign a symbol to the partition.  */
272   if (!(!ign2 && root2)
273       && !(!ign1 && root1))
274     {
275       if (debug)
276         fprintf (debug, " : Choosen variable has no root.  No coalesce.\n");
277       return;
278     }
279
280   /* Don't coalesce if the new chosen root variable would be read-only.
281      If both ign1 && ign2, then the root var of the larger partition
282      wins, so reject in that case if any of the root vars is TREE_READONLY.
283      Otherwise reject only if the root var, on which replace_ssa_name_symbol
284      will be called below, is readonly.  */
285   if (((root1 && TREE_READONLY (root1)) && ign2)
286       || ((root2 && TREE_READONLY (root2)) && ign1))
287     {
288       if (debug)
289         fprintf (debug, " : Readonly variable.  No coalesce.\n");
290       return;
291     }
292
293   /* Don't coalesce if the two variables aren't type compatible .  */
294   if (!types_compatible_p (TREE_TYPE (var1), TREE_TYPE (var2))
295       /* There is a disconnect between the middle-end type-system and
296          VRP, avoid coalescing enum types with different bounds.  */
297       || ((TREE_CODE (TREE_TYPE (var1)) == ENUMERAL_TYPE
298            || TREE_CODE (TREE_TYPE (var2)) == ENUMERAL_TYPE)
299           && TREE_TYPE (var1) != TREE_TYPE (var2)))
300     {
301       if (debug)
302         fprintf (debug, " : Incompatible types.  No coalesce.\n");
303       return;
304     }
305
306   /* Merge the two partitions.  */
307   p3 = partition_union (map->var_partition, p1, p2);
308
309   /* Set the root variable of the partition to the better choice, if there is
310      one.  */
311   if (!ign2 && root2)
312     replace_ssa_name_symbol (partition_to_var (map, p3), root2);
313   else if (!ign1 && root1)
314     replace_ssa_name_symbol (partition_to_var (map, p3), root1);
315   else
316     gcc_unreachable ();
317
318   if (debug)
319     {
320       fprintf (debug, " --> P%d ", p3);
321       print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
322                           TDF_SLIM);
323       fprintf (debug, "\n");
324     }
325 }
326
327
328 namespace {
329
330 const pass_data pass_data_rename_ssa_copies =
331 {
332   GIMPLE_PASS, /* type */
333   "copyrename", /* name */
334   OPTGROUP_NONE, /* optinfo_flags */
335   TV_TREE_COPY_RENAME, /* tv_id */
336   ( PROP_cfg | PROP_ssa ), /* properties_required */
337   0, /* properties_provided */
338   0, /* properties_destroyed */
339   0, /* todo_flags_start */
340   0, /* todo_flags_finish */
341 };
342
343 class pass_rename_ssa_copies : public gimple_opt_pass
344 {
345 public:
346   pass_rename_ssa_copies (gcc::context *ctxt)
347     : gimple_opt_pass (pass_data_rename_ssa_copies, ctxt)
348   {}
349
350   /* opt_pass methods: */
351   opt_pass * clone () { return new pass_rename_ssa_copies (m_ctxt); }
352   virtual bool gate (function *) { return flag_tree_copyrename != 0; }
353   virtual unsigned int execute (function *);
354
355 }; // class pass_rename_ssa_copies
356
357 /* This function will make a pass through the IL, and attempt to coalesce any
358    SSA versions which occur in PHI's or copies.  Coalescing is accomplished by
359    changing the underlying root variable of all coalesced version.  This will
360    then cause the SSA->normal pass to attempt to coalesce them all to the same
361    variable.  */
362
363 unsigned int
364 pass_rename_ssa_copies::execute (function *fun)
365 {
366   var_map map;
367   basic_block bb;
368   tree var, part_var;
369   gimple stmt;
370   unsigned x;
371   FILE *debug;
372
373   memset (&stats, 0, sizeof (stats));
374
375   if (dump_file && (dump_flags & TDF_DETAILS))
376     debug = dump_file;
377   else
378     debug = NULL;
379
380   map = init_var_map (num_ssa_names);
381
382   FOR_EACH_BB_FN (bb, fun)
383     {
384       /* Scan for real copies.  */
385       for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
386            gsi_next (&gsi))
387         {
388           stmt = gsi_stmt (gsi);
389           if (gimple_assign_ssa_name_copy_p (stmt))
390             {
391               tree lhs = gimple_assign_lhs (stmt);
392               tree rhs = gimple_assign_rhs1 (stmt);
393
394               copy_rename_partition_coalesce (map, lhs, rhs, debug);
395             }
396         }
397     }
398
399   FOR_EACH_BB_FN (bb, fun)
400     {
401       /* Treat PHI nodes as copies between the result and each argument.  */
402       for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
403            gsi_next (&gsi))
404         {
405           size_t i;
406           tree res;
407           gphi *phi = gsi.phi ();
408           res = gimple_phi_result (phi);
409
410           /* Do not process virtual SSA_NAMES.  */
411           if (virtual_operand_p (res))
412             continue;
413
414           /* Make sure to only use the same partition for an argument
415              as the result but never the other way around.  */
416           if (SSA_NAME_VAR (res)
417               && !DECL_IGNORED_P (SSA_NAME_VAR (res)))
418             for (i = 0; i < gimple_phi_num_args (phi); i++)
419               {
420                 tree arg = PHI_ARG_DEF (phi, i);
421                 if (TREE_CODE (arg) == SSA_NAME)
422                   copy_rename_partition_coalesce (map, res, arg,
423                                                   debug);
424               }
425           /* Else if all arguments are in the same partition try to merge
426              it with the result.  */
427           else
428             {
429               int all_p_same = -1;
430               int p = -1;
431               for (i = 0; i < gimple_phi_num_args (phi); i++)
432                 {
433                   tree arg = PHI_ARG_DEF (phi, i);
434                   if (TREE_CODE (arg) != SSA_NAME)
435                     {
436                       all_p_same = 0;
437                       break;
438                     }
439                   else if (all_p_same == -1)
440                     {
441                       p = partition_find (map->var_partition,
442                                           SSA_NAME_VERSION (arg));
443                       all_p_same = 1;
444                     }
445                   else if (all_p_same == 1
446                            && p != partition_find (map->var_partition,
447                                                    SSA_NAME_VERSION (arg)))
448                     {
449                       all_p_same = 0;
450                       break;
451                     }
452                 }
453               if (all_p_same == 1)
454                 copy_rename_partition_coalesce (map, res,
455                                                 PHI_ARG_DEF (phi, 0),
456                                                 debug);
457             }
458         }
459     }
460
461   if (debug)
462     dump_var_map (debug, map);
463
464   /* Now one more pass to make all elements of a partition share the same
465      root variable.  */
466
467   for (x = 1; x < num_ssa_names; x++)
468     {
469       part_var = partition_to_var (map, x);
470       if (!part_var)
471         continue;
472       var = ssa_name (x);
473       if (SSA_NAME_VAR (var) == SSA_NAME_VAR (part_var))
474         continue;
475       if (debug)
476         {
477           fprintf (debug, "Coalesced ");
478           print_generic_expr (debug, var, TDF_SLIM);
479           fprintf (debug, " to ");
480           print_generic_expr (debug, part_var, TDF_SLIM);
481           fprintf (debug, "\n");
482         }
483       stats.coalesced++;
484       replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
485     }
486
487   statistics_counter_event (fun, "copies coalesced",
488                             stats.coalesced);
489   delete_var_map (map);
490   return 0;
491 }
492
493 } // anon namespace
494
495 gimple_opt_pass *
496 make_pass_rename_ssa_copies (gcc::context *ctxt)
497 {
498   return new pass_rename_ssa_copies (ctxt);
499 }