1/* Rename SSA copies.
2   Copyright (C) 2004-2015 Free Software Foundation, Inc.
3   Contributed by Andrew MacLeod <amacleod@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
74static 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
150static void
151copy_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
328namespace {
329
330const 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
343class pass_rename_ssa_copies : public gimple_opt_pass
344{
345public:
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
363unsigned int
364pass_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
495gimple_opt_pass *
496make_pass_rename_ssa_copies (gcc::context *ctxt)
497{
498  return new pass_rename_ssa_copies (ctxt);
499}
500