1/* Rename SSA copies.
2   Copyright (C) 2004, 2006, 2007, 2008 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 "tree.h"
26#include "gimple.h"
27#include "flags.h"
28#include "basic-block.h"
29#include "function.h"
30#include "diagnostic.h"
31#include "bitmap.h"
32#include "tree-flow.h"
33#include "gimple.h"
34#include "tree-inline.h"
35#include "timevar.h"
36#include "hashtab.h"
37#include "tree-dump.h"
38#include "tree-ssa-live.h"
39#include "tree-pass.h"
40#include "langhooks.h"
41
42/* The following routines implement the SSA copy renaming phase.
43
44   This optimization looks for copies between 2 SSA_NAMES, either through a
45   direct copy, or an implicit one via a PHI node result and its arguments.
46
47   Each copy is examined to determine if it is possible to rename the base
48   variable of one of the operands to the same variable as the other operand.
49   i.e.
50   T.3_5 = <blah>
51   a_1 = T.3_5
52
53   If this copy couldn't be copy propagated, it could possibly remain in the
54   program throughout the optimization phases.   After SSA->normal, it would
55   become:
56
57   T.3 = <blah>
58   a = T.3
59
60   Since T.3_5 is distinct from all other SSA versions of T.3, there is no
61   fundamental reason why the base variable needs to be T.3, subject to
62   certain restrictions.  This optimization attempts to determine if we can
63   change the base variable on copies like this, and result in code such as:
64
65   a_5 = <blah>
66   a_1 = a_5
67
68   This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
69   possible, the copy goes away completely. If it isn't possible, a new temp
70   will be created for a_5, and you will end up with the exact same code:
71
72   a.8 = <blah>
73   a = a.8
74
75   The other benefit of performing this optimization relates to what variables
76   are chosen in copies.  Gimplification of the program uses temporaries for
77   a lot of things. expressions like
78
79   a_1 = <blah>
80   <blah2> = a_1
81
82   get turned into
83
84   T.3_5 = <blah>
85   a_1 = T.3_5
86   <blah2> = a_1
87
88   Copy propagation is done in a forward direction, and if we can propagate
89   through the copy, we end up with:
90
91   T.3_5 = <blah>
92   <blah2> = T.3_5
93
94   The copy is gone, but so is all reference to the user variable 'a'. By
95   performing this optimization, we would see the sequence:
96
97   a_5 = <blah>
98   a_1 = a_5
99   <blah2> = a_1
100
101   which copy propagation would then turn into:
102
103   a_5 = <blah>
104   <blah2> = a_5
105
106   and so we still retain the user variable whenever possible.  */
107
108
109/* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
110   Choose a representative for the partition, and send debug info to DEBUG.  */
111
112static bool
113copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
114{
115  int p1, p2, p3;
116  tree root1, root2;
117  tree rep1, rep2;
118  bool ign1, ign2, abnorm;
119
120  gcc_assert (TREE_CODE (var1) == SSA_NAME);
121  gcc_assert (TREE_CODE (var2) == SSA_NAME);
122
123  register_ssa_partition (map, var1);
124  register_ssa_partition (map, var2);
125
126  p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
127  p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
128
129  if (debug)
130    {
131      fprintf (debug, "Try : ");
132      print_generic_expr (debug, var1, TDF_SLIM);
133      fprintf (debug, "(P%d) & ", p1);
134      print_generic_expr (debug, var2, TDF_SLIM);
135      fprintf (debug, "(P%d)", p2);
136    }
137
138  gcc_assert (p1 != NO_PARTITION);
139  gcc_assert (p2 != NO_PARTITION);
140
141  rep1 = partition_to_var (map, p1);
142  rep2 = partition_to_var (map, p2);
143  root1 = SSA_NAME_VAR (rep1);
144  root2 = SSA_NAME_VAR (rep2);
145
146  if (p1 == p2)
147    {
148      if (debug)
149	fprintf (debug, " : Already coalesced.\n");
150      return false;
151    }
152
153  /* Don't coalesce if one of the variables occurs in an abnormal PHI.  */
154  abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
155	    || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
156  if (abnorm)
157    {
158      if (debug)
159	fprintf (debug, " : Abnormal PHI barrier.  No coalesce.\n");
160      return false;
161    }
162
163  /* Partitions already have the same root, simply merge them.  */
164  if (root1 == root2)
165    {
166      p1 = partition_union (map->var_partition, p1, p2);
167      if (debug)
168	fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
169      return false;
170    }
171
172  /* Never attempt to coalesce 2 difference parameters.  */
173  if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
174    {
175      if (debug)
176        fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
177      return false;
178    }
179
180  if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
181    {
182      if (debug)
183        fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
184      return false;
185    }
186
187  ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
188  ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
189
190  /* Never attempt to coalesce 2 user variables unless one is an inline
191     variable.  */
192  if (!ign1 && !ign2)
193    {
194      if (DECL_FROM_INLINE (root2))
195        ign2 = true;
196      else if (DECL_FROM_INLINE (root1))
197	ign1 = true;
198      else
199	{
200	  if (debug)
201	    fprintf (debug, " : 2 different USER vars. No coalesce.\n");
202	  return false;
203	}
204    }
205
206  /* If both values have default defs, we can't coalesce.  If only one has a
207     tag, make sure that variable is the new root partition.  */
208  if (gimple_default_def (cfun, root1))
209    {
210      if (gimple_default_def (cfun, root2))
211	{
212	  if (debug)
213	    fprintf (debug, " : 2 default defs. No coalesce.\n");
214	  return false;
215	}
216      else
217        {
218	  ign2 = true;
219	  ign1 = false;
220	}
221    }
222  else if (gimple_default_def (cfun, root2))
223    {
224      ign1 = true;
225      ign2 = false;
226    }
227
228  /* Don't coalesce if the two variables aren't type compatible .  */
229  if (!types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2))
230      /* There is a disconnect between the middle-end type-system and
231         VRP, avoid coalescing enum types with different bounds.  */
232      || ((TREE_CODE (TREE_TYPE (root1)) == ENUMERAL_TYPE
233	   || TREE_CODE (TREE_TYPE (root2)) == ENUMERAL_TYPE)
234	  && TREE_TYPE (root1) != TREE_TYPE (root2)))
235    {
236      if (debug)
237	fprintf (debug, " : Incompatible types.  No coalesce.\n");
238      return false;
239    }
240
241  /* Merge the two partitions.  */
242  p3 = partition_union (map->var_partition, p1, p2);
243
244  /* Set the root variable of the partition to the better choice, if there is
245     one.  */
246  if (!ign2)
247    replace_ssa_name_symbol (partition_to_var (map, p3), root2);
248  else if (!ign1)
249    replace_ssa_name_symbol (partition_to_var (map, p3), root1);
250
251  if (debug)
252    {
253      fprintf (debug, " --> P%d ", p3);
254      print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
255			  TDF_SLIM);
256      fprintf (debug, "\n");
257    }
258  return true;
259}
260
261
262/* This function will make a pass through the IL, and attempt to coalesce any
263   SSA versions which occur in PHI's or copies.  Coalescing is accomplished by
264   changing the underlying root variable of all coalesced version.  This will
265   then cause the SSA->normal pass to attempt to coalesce them all to the same
266   variable.  */
267
268static unsigned int
269rename_ssa_copies (void)
270{
271  var_map map;
272  basic_block bb;
273  gimple_stmt_iterator gsi;
274  tree var, part_var;
275  gimple stmt, phi;
276  unsigned x;
277  FILE *debug;
278  bool updated = false;
279
280  if (dump_file && (dump_flags & TDF_DETAILS))
281    debug = dump_file;
282  else
283    debug = NULL;
284
285  map = init_var_map (num_ssa_names);
286
287  FOR_EACH_BB (bb)
288    {
289      /* Scan for real copies.  */
290      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
291	{
292	  stmt = gsi_stmt (gsi);
293	  if (gimple_assign_ssa_name_copy_p (stmt))
294	    {
295	      tree lhs = gimple_assign_lhs (stmt);
296	      tree rhs = gimple_assign_rhs1 (stmt);
297
298	      updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
299	    }
300	}
301    }
302
303  FOR_EACH_BB (bb)
304    {
305      /* Treat PHI nodes as copies between the result and each argument.  */
306      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
307        {
308          size_t i;
309	  tree res;
310
311	  phi = gsi_stmt (gsi);
312	  res = gimple_phi_result (phi);
313
314	  /* Do not process virtual SSA_NAMES.  */
315	  if (!is_gimple_reg (SSA_NAME_VAR (res)))
316	    continue;
317
318          for (i = 0; i < gimple_phi_num_args (phi); i++)
319            {
320              tree arg = gimple_phi_arg (phi, i)->def;
321              if (TREE_CODE (arg) == SSA_NAME)
322		updated |= copy_rename_partition_coalesce (map, res, arg, debug);
323            }
324        }
325    }
326
327  if (debug)
328    dump_var_map (debug, map);
329
330  /* Now one more pass to make all elements of a partition share the same
331     root variable.  */
332
333  for (x = 1; x < num_ssa_names; x++)
334    {
335      part_var = partition_to_var (map, x);
336      if (!part_var)
337        continue;
338      var = ssa_name (x);
339      if (debug)
340        {
341	  if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
342	    {
343	      fprintf (debug, "Coalesced ");
344	      print_generic_expr (debug, var, TDF_SLIM);
345	      fprintf (debug, " to ");
346	      print_generic_expr (debug, part_var, TDF_SLIM);
347	      fprintf (debug, "\n");
348	    }
349	}
350      replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
351    }
352
353  delete_var_map (map);
354  return updated ? TODO_remove_unused_locals : 0;
355}
356
357/* Return true if copy rename is to be performed.  */
358
359static bool
360gate_copyrename (void)
361{
362  return flag_tree_copyrename != 0;
363}
364
365struct gimple_opt_pass pass_rename_ssa_copies =
366{
367 {
368  GIMPLE_PASS,
369  "copyrename",				/* name */
370  gate_copyrename,			/* gate */
371  rename_ssa_copies,			/* execute */
372  NULL,					/* sub */
373  NULL,					/* next */
374  0,					/* static_pass_number */
375  TV_TREE_COPY_RENAME,			/* tv_id */
376  PROP_cfg | PROP_ssa,			/* properties_required */
377  0,					/* properties_provided */
378  0,					/* properties_destroyed */
379  0,					/* todo_flags_start */
380  TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
381 }
382};
383