Merge branch 'vendor/GCC47'
[dragonfly.git] / contrib / gcc-4.7 / gcc / tree-ssanames.c
CommitLineData
e4b17023
JM
1/* Generic routines for manipulating SSA_NAME expressions
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
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 "tree-flow.h"
27#include "tree-pass.h"
28
29/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
30 many of which may be thrown away shortly after their creation if jumps
31 were threaded through PHI nodes.
32
33 While our garbage collection mechanisms will handle this situation, it
34 is extremely wasteful to create nodes and throw them away, especially
35 when the nodes can be reused.
36
37 For PR 8361, we can significantly reduce the number of nodes allocated
38 and thus the total amount of memory allocated by managing SSA_NAMEs a
39 little. This additionally helps reduce the amount of work done by the
40 garbage collector. Similar results have been seen on a wider variety
41 of tests (such as the compiler itself).
42
43 Right now we maintain our free list on a per-function basis. It may
44 or may not make sense to maintain the free list for the duration of
45 a compilation unit.
46
47 External code should rely solely upon HIGHEST_SSA_VERSION and the
48 externally defined functions. External code should not know about
49 the details of the free list management.
50
51 External code should also not assume the version number on nodes is
52 monotonically increasing. We reuse the version number when we
53 reuse an SSA_NAME expression. This helps keep arrays and bitmaps
54 more compact.
55
56 We could also use a zone allocator for these objects since they have
57 a very well defined lifetime. If someone wants to experiment with that
58 this is the place to try it. */
59
60/* Version numbers with special meanings. We start allocating new version
61 numbers after the special ones. */
62#define UNUSED_NAME_VERSION 0
63
64#ifdef GATHER_STATISTICS
65unsigned int ssa_name_nodes_reused;
66unsigned int ssa_name_nodes_created;
67#endif
68
69/* Initialize management of SSA_NAMEs to default SIZE. If SIZE is
70 zero use default. */
71
72void
73init_ssanames (struct function *fn, int size)
74{
75 if (size < 50)
76 size = 50;
77
78 SSANAMES (fn) = VEC_alloc (tree, gc, size);
79
80 /* Version 0 is special, so reserve the first slot in the table. Though
81 currently unused, we may use version 0 in alias analysis as part of
82 the heuristics used to group aliases when the alias sets are too
83 large.
84
85 We use VEC_quick_push here because we know that SSA_NAMES has at
86 least 50 elements reserved in it. */
87 VEC_quick_push (tree, SSANAMES (fn), NULL_TREE);
88 FREE_SSANAMES (fn) = NULL;
89
90 SYMS_TO_RENAME (fn) = BITMAP_GGC_ALLOC ();
91}
92
93/* Finalize management of SSA_NAMEs. */
94
95void
96fini_ssanames (void)
97{
98 VEC_free (tree, gc, SSANAMES (cfun));
99 VEC_free (tree, gc, FREE_SSANAMES (cfun));
100}
101
102/* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */
103
104#ifdef GATHER_STATISTICS
105void
106ssanames_print_statistics (void)
107{
108 fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
109 fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
110}
111#endif
112
113/* Return an SSA_NAME node for variable VAR defined in statement STMT
114 in function FN. STMT may be an empty statement for artificial
115 references (e.g., default definitions created when a variable is
116 used without a preceding definition). */
117
118tree
119make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
120{
121 tree t;
122 use_operand_p imm;
123
124 gcc_assert (DECL_P (var));
125
126 /* If our free list has an element, then use it. */
127 if (!VEC_empty (tree, FREE_SSANAMES (fn)))
128 {
129 t = VEC_pop (tree, FREE_SSANAMES (fn));
130#ifdef GATHER_STATISTICS
131 ssa_name_nodes_reused++;
132#endif
133
134 /* The node was cleared out when we put it on the free list, so
135 there is no need to do so again here. */
95d28233 136 gcc_assert (VEC_index (tree, SSANAMES (fn), SSA_NAME_VERSION (t)) == NULL);
e4b17023
JM
137 VEC_replace (tree, SSANAMES (fn), SSA_NAME_VERSION (t), t);
138 }
139 else
140 {
141 t = make_node (SSA_NAME);
142 SSA_NAME_VERSION (t) = VEC_length (tree, SSANAMES (fn));
143 VEC_safe_push (tree, gc, SSANAMES (fn), t);
144#ifdef GATHER_STATISTICS
145 ssa_name_nodes_created++;
146#endif
147 }
148
149 TREE_TYPE (t) = TREE_TYPE (var);
150 SSA_NAME_VAR (t) = var;
151 SSA_NAME_DEF_STMT (t) = stmt;
152 SSA_NAME_PTR_INFO (t) = NULL;
153 SSA_NAME_IN_FREE_LIST (t) = 0;
154 SSA_NAME_IS_DEFAULT_DEF (t) = 0;
155 imm = &(SSA_NAME_IMM_USE_NODE (t));
156 imm->use = NULL;
157 imm->prev = imm;
158 imm->next = imm;
159 imm->loc.ssa_name = t;
160
161 return t;
162}
163
164
165/* We no longer need the SSA_NAME expression VAR, release it so that
166 it may be reused.
167
168 Note it is assumed that no calls to make_ssa_name will be made
169 until all uses of the ssa name are released and that the only
170 use of the SSA_NAME expression is to check its SSA_NAME_VAR. All
171 other fields must be assumed clobbered. */
172
173void
174release_ssa_name (tree var)
175{
176 if (!var)
177 return;
178
179 /* Never release the default definition for a symbol. It's a
180 special SSA name that should always exist once it's created. */
181 if (SSA_NAME_IS_DEFAULT_DEF (var))
182 return;
183
184 /* If VAR has been registered for SSA updating, don't remove it.
185 After update_ssa has run, the name will be released. */
186 if (name_registered_for_update_p (var))
187 {
188 release_ssa_name_after_update_ssa (var);
189 return;
190 }
191
192 /* release_ssa_name can be called multiple times on a single SSA_NAME.
193 However, it should only end up on our free list one time. We
194 keep a status bit in the SSA_NAME node itself to indicate it has
195 been put on the free list.
196
197 Note that once on the freelist you can not reference the SSA_NAME's
198 defining statement. */
199 if (! SSA_NAME_IN_FREE_LIST (var))
200 {
201 tree saved_ssa_name_var = SSA_NAME_VAR (var);
202 int saved_ssa_name_version = SSA_NAME_VERSION (var);
203 use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
204
205 if (MAY_HAVE_DEBUG_STMTS)
206 insert_debug_temp_for_var_def (NULL, var);
207
208#ifdef ENABLE_CHECKING
209 verify_imm_links (stderr, var);
210#endif
211 while (imm->next != imm)
212 delink_imm_use (imm->next);
213
214 VEC_replace (tree, SSANAMES (cfun),
215 SSA_NAME_VERSION (var), NULL_TREE);
216 memset (var, 0, tree_size (var));
217
218 imm->prev = imm;
219 imm->next = imm;
220 imm->loc.ssa_name = var;
221
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 put it on the free list. */
237 VEC_safe_push (tree, gc, FREE_SSANAMES (cfun), var);
238 }
239}
240
241
242/* Return the alias information associated with pointer T. It creates a
243 new instance if none existed. */
244
245struct ptr_info_def *
246get_ptr_info (tree t)
247{
248 struct ptr_info_def *pi;
249
250 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
251
252 pi = SSA_NAME_PTR_INFO (t);
253 if (pi == NULL)
254 {
255 pi = ggc_alloc_cleared_ptr_info_def ();
256 pt_solution_reset (&pi->pt);
257 pi->align = 1;
258 pi->misalign = 0;
259 SSA_NAME_PTR_INFO (t) = pi;
260 }
261
262 return pi;
263}
264
265/* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
266 the SSA name NAME. */
267
268void
269duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
270{
271 struct ptr_info_def *new_ptr_info;
272
273 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
274 gcc_assert (!SSA_NAME_PTR_INFO (name));
275
276 if (!ptr_info)
277 return;
278
279 new_ptr_info = ggc_alloc_ptr_info_def ();
280 *new_ptr_info = *ptr_info;
281
282 SSA_NAME_PTR_INFO (name) = new_ptr_info;
283}
284
285
286/* Creates a duplicate of a ssa name NAME tobe defined by statement STMT. */
287
288tree
289duplicate_ssa_name (tree name, gimple stmt)
290{
291 tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt);
292 struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
293
294 if (old_ptr_info)
295 duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
296
297 return new_name;
298}
299
300
301/* Release all the SSA_NAMEs created by STMT. */
302
303void
304release_defs (gimple stmt)
305{
306 tree def;
307 ssa_op_iter iter;
308
309 /* Make sure that we are in SSA. Otherwise, operand cache may point
310 to garbage. */
311 gcc_assert (gimple_in_ssa_p (cfun));
312
313 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
314 if (TREE_CODE (def) == SSA_NAME)
315 release_ssa_name (def);
316}
317
318
319/* Replace the symbol associated with SSA_NAME with SYM. */
320
321void
322replace_ssa_name_symbol (tree ssa_name, tree sym)
323{
324 SSA_NAME_VAR (ssa_name) = sym;
325 TREE_TYPE (ssa_name) = TREE_TYPE (sym);
326}
327
328/* Return SSA names that are unused to GGC memory. This is used to keep
329 footprint of compiler during interprocedural optimization.
330 As a side effect the SSA_NAME_VERSION number reuse is reduced
331 so this function should not be used too often. */
332static unsigned int
333release_dead_ssa_names (void)
334{
335 tree t;
336 int n = VEC_length (tree, FREE_SSANAMES (cfun));
337 referenced_var_iterator rvi;
338
339 /* Current defs point to various dead SSA names that in turn point to
340 eventually dead variables so a bunch of memory is held live. */
341 FOR_EACH_REFERENCED_VAR (cfun, t, rvi)
342 set_current_def (t, NULL);
343 /* Now release the freelist. */
344 VEC_free (tree, gc, FREE_SSANAMES (cfun));
345 FREE_SSANAMES (cfun) = NULL;
346
347 statistics_counter_event (cfun, "SSA names released", n);
348 if (dump_file)
349 fprintf (dump_file, "Released %i names, %.2f%%\n",
350 n, n * 100.0 / num_ssa_names);
351 return 0;
352}
353
354struct gimple_opt_pass pass_release_ssa_names =
355{
356 {
357 GIMPLE_PASS,
358 "release_ssa", /* name */
359 NULL, /* gate */
360 release_dead_ssa_names, /* execute */
361 NULL, /* sub */
362 NULL, /* next */
363 0, /* static_pass_number */
364 TV_TREE_SSA_OTHER, /* tv_id */
365 PROP_ssa, /* properties_required */
366 0, /* properties_provided */
367 0, /* properties_destroyed */
368 0, /* todo_flags_start */
369 0 /* todo_flags_finish */
370 }
371};