1/* Generic routines for manipulating SSA_NAME expressions
2   Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 2, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING.  If not, write to
18the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19Boston, MA 02110-1301, USA.  */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "tree.h"
26#include "varray.h"
27#include "ggc.h"
28#include "tree-flow.h"
29
30/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
31   many of which may be thrown away shortly after their creation if jumps
32   were threaded through PHI nodes.
33
34   While our garbage collection mechanisms will handle this situation, it
35   is extremely wasteful to create nodes and throw them away, especially
36   when the nodes can be reused.
37
38   For PR 8361, we can significantly reduce the number of nodes allocated
39   and thus the total amount of memory allocated by managing SSA_NAMEs a
40   little.  This additionally helps reduce the amount of work done by the
41   garbage collector.  Similar results have been seen on a wider variety
42   of tests (such as the compiler itself).
43
44   Right now we maintain our free list on a per-function basis.  It may
45   or may not make sense to maintain the free list for the duration of
46   a compilation unit.
47
48   External code should rely solely upon HIGHEST_SSA_VERSION and the
49   externally defined functions.  External code should not know about
50   the details of the free list management.
51
52   External code should also not assume the version number on nodes is
53   monotonically increasing.  We reuse the version number when we
54   reuse an SSA_NAME expression.  This helps keep arrays and bitmaps
55   more compact.
56
57   We could also use a zone allocator for these objects since they have
58   a very well defined lifetime.  If someone wants to experiment with that
59   this is the place to try it.  */
60
61/* Array of all SSA_NAMEs used in the function.  */
62VEC(tree,gc) *ssa_names;
63
64/* Free list of SSA_NAMEs.  This list is wiped at the end of each function
65   after we leave SSA form.  */
66static GTY (()) tree free_ssanames;
67
68/* Version numbers with special meanings.  We start allocating new version
69   numbers after the special ones.  */
70#define UNUSED_NAME_VERSION 0
71
72#ifdef GATHER_STATISTICS
73unsigned int ssa_name_nodes_reused;
74unsigned int ssa_name_nodes_created;
75#endif
76
77/* Initialize management of SSA_NAMEs.  */
78
79void
80init_ssanames (void)
81{
82  ssa_names = VEC_alloc (tree, gc, 50);
83
84  /* Version 0 is special, so reserve the first slot in the table.  Though
85     currently unused, we may use version 0 in alias analysis as part of
86     the heuristics used to group aliases when the alias sets are too
87     large.
88
89     We use VEC_quick_push here because we know that SSA_NAMES has at
90     least 50 elements reserved in it.  */
91  VEC_quick_push (tree, ssa_names, NULL_TREE);
92  free_ssanames = NULL;
93}
94
95/* Finalize management of SSA_NAMEs.  */
96
97void
98fini_ssanames (void)
99{
100  VEC_free (tree, gc, ssa_names);
101  free_ssanames = NULL;
102}
103
104/* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
105
106#ifdef GATHER_STATISTICS
107void
108ssanames_print_statistics (void)
109{
110  fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
111  fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
112}
113#endif
114
115/* Return an SSA_NAME node for variable VAR defined in statement STMT.
116   STMT may be an empty statement for artificial references (e.g., default
117   definitions created when a variable is used without a preceding
118   definition).  */
119
120tree
121make_ssa_name (tree var, tree stmt)
122{
123  tree t;
124  use_operand_p imm;
125
126  gcc_assert (DECL_P (var)
127	      || TREE_CODE (var) == INDIRECT_REF);
128
129  gcc_assert (!stmt || EXPR_P (stmt) || TREE_CODE (stmt) == PHI_NODE);
130
131  /* If our free list has an element, then use it.  */
132  if (free_ssanames)
133    {
134      t = free_ssanames;
135      free_ssanames = TREE_CHAIN (free_ssanames);
136#ifdef GATHER_STATISTICS
137      ssa_name_nodes_reused++;
138#endif
139
140      /* The node was cleared out when we put it on the free list, so
141	 there is no need to do so again here.  */
142      gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL);
143      VEC_replace (tree, ssa_names, SSA_NAME_VERSION (t), t);
144    }
145  else
146    {
147      t = make_node (SSA_NAME);
148      SSA_NAME_VERSION (t) = num_ssa_names;
149      VEC_safe_push (tree, gc, ssa_names, t);
150#ifdef GATHER_STATISTICS
151      ssa_name_nodes_created++;
152#endif
153    }
154
155  TREE_TYPE (t) = TREE_TYPE (var);
156  SSA_NAME_VAR (t) = var;
157  SSA_NAME_DEF_STMT (t) = stmt;
158  SSA_NAME_PTR_INFO (t) = NULL;
159  SSA_NAME_IN_FREE_LIST (t) = 0;
160  imm = &(SSA_NAME_IMM_USE_NODE (t));
161  imm->use = NULL;
162  imm->prev = imm;
163  imm->next = imm;
164  imm->stmt = t;
165
166  return t;
167}
168
169
170/* We no longer need the SSA_NAME expression VAR, release it so that
171   it may be reused.
172
173   Note it is assumed that no calls to make_ssa_name will be made
174   until all uses of the ssa name are released and that the only
175   use of the SSA_NAME expression is to check its SSA_NAME_VAR.  All
176   other fields must be assumed clobbered.  */
177
178void
179release_ssa_name (tree var)
180{
181  if (!var)
182    return;
183
184  /* Never release the default definition for a symbol.  It's a
185     special SSA name that should always exist once it's created.  */
186  if (var == default_def (SSA_NAME_VAR (var)))
187    return;
188
189  /* If VAR has been registered for SSA updating, don't remove it.
190     After update_ssa has run, the name will be released.  */
191  if (name_registered_for_update_p (var))
192    {
193      release_ssa_name_after_update_ssa (var);
194      return;
195    }
196
197  /* release_ssa_name can be called multiple times on a single SSA_NAME.
198     However, it should only end up on our free list one time.   We
199     keep a status bit in the SSA_NAME node itself to indicate it has
200     been put on the free list.
201
202     Note that once on the freelist you can not reference the SSA_NAME's
203     defining statement.  */
204  if (! SSA_NAME_IN_FREE_LIST (var))
205    {
206      tree saved_ssa_name_var = SSA_NAME_VAR (var);
207      int saved_ssa_name_version = SSA_NAME_VERSION (var);
208      use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
209
210#ifdef ENABLE_CHECKING
211      verify_imm_links (stderr, var);
212#endif
213      while (imm->next != imm)
214	delink_imm_use (imm->next);
215
216      VEC_replace (tree, ssa_names, SSA_NAME_VERSION (var), NULL_TREE);
217      memset (var, 0, tree_size (var));
218
219      imm->prev = imm;
220      imm->next = imm;
221      imm->stmt = var;
222      /* First put back the right tree node so that the tree checking
223	 macros do not complain.  */
224      TREE_SET_CODE (var, SSA_NAME);
225
226      /* Restore the version number.  */
227      SSA_NAME_VERSION (var) = saved_ssa_name_version;
228
229      /* Hopefully this can go away once we have the new incremental
230         SSA updating code installed.  */
231      SSA_NAME_VAR (var) = saved_ssa_name_var;
232
233      /* Note this SSA_NAME is now in the first list.  */
234      SSA_NAME_IN_FREE_LIST (var) = 1;
235
236      /* And finally link it into the free list.  */
237      TREE_CHAIN (var) = free_ssanames;
238      free_ssanames = var;
239    }
240}
241
242/* Creates a duplicate of a ssa name NAME defined in statement STMT.  */
243
244tree
245duplicate_ssa_name (tree name, tree stmt)
246{
247  tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt);
248  struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
249
250  if (old_ptr_info)
251    duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
252
253  return new_name;
254}
255
256
257/* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
258   the SSA name NAME.  */
259
260void
261duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
262{
263  struct ptr_info_def *new_ptr_info;
264
265  gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
266  gcc_assert (!SSA_NAME_PTR_INFO (name));
267
268  if (!ptr_info)
269    return;
270
271  new_ptr_info = ggc_alloc (sizeof (struct ptr_info_def));
272  *new_ptr_info = *ptr_info;
273
274  if (ptr_info->pt_vars)
275    {
276      new_ptr_info->pt_vars = BITMAP_GGC_ALLOC ();
277      bitmap_copy (new_ptr_info->pt_vars, ptr_info->pt_vars);
278    }
279
280  SSA_NAME_PTR_INFO (name) = new_ptr_info;
281}
282
283
284/* Release all the SSA_NAMEs created by STMT.  */
285
286void
287release_defs (tree stmt)
288{
289  tree def;
290  ssa_op_iter iter;
291
292  /* Make sure that we are in SSA.  Otherwise, operand cache may point
293     to garbage.  */
294  gcc_assert (in_ssa_p);
295
296  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
297    if (TREE_CODE (def) == SSA_NAME)
298      release_ssa_name (def);
299}
300
301
302/* Replace the symbol associated with SSA_NAME with SYM.  */
303
304void
305replace_ssa_name_symbol (tree ssa_name, tree sym)
306{
307  SSA_NAME_VAR (ssa_name) = sym;
308  TREE_TYPE (ssa_name) = TREE_TYPE (sym);
309}
310
311#include "gt-tree-ssanames.h"
312