|
0
|
1 /* Generic routines for manipulating SSA_NAME expressions
|
|
|
2 Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify
|
|
|
7 it under the terms of the GNU General Public License as published by
|
|
|
8 the Free Software Foundation; either version 3, or (at your option)
|
|
|
9 any later version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful,
|
|
|
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
14 GNU General Public License for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "system.h"
|
|
|
22 #include "coretypes.h"
|
|
|
23 #include "tm.h"
|
|
|
24 #include "tree.h"
|
|
|
25 #include "varray.h"
|
|
|
26 #include "ggc.h"
|
|
|
27 #include "tree-flow.h"
|
|
|
28 #include "tree-pass.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 /* Version numbers with special meanings. We start allocating new version
|
|
|
62 numbers after the special ones. */
|
|
|
63 #define UNUSED_NAME_VERSION 0
|
|
|
64
|
|
|
65 #ifdef GATHER_STATISTICS
|
|
|
66 unsigned int ssa_name_nodes_reused;
|
|
|
67 unsigned int ssa_name_nodes_created;
|
|
|
68 #endif
|
|
|
69
|
|
|
70 /* Initialize management of SSA_NAMEs to default SIZE. If SIZE is
|
|
|
71 zero use default. */
|
|
|
72
|
|
|
73 void
|
|
|
74 init_ssanames (struct function *fn, int size)
|
|
|
75 {
|
|
|
76 if (size < 50)
|
|
|
77 size = 50;
|
|
|
78
|
|
|
79 SSANAMES (fn) = VEC_alloc (tree, gc, size);
|
|
|
80
|
|
|
81 /* Version 0 is special, so reserve the first slot in the table. Though
|
|
|
82 currently unused, we may use version 0 in alias analysis as part of
|
|
|
83 the heuristics used to group aliases when the alias sets are too
|
|
|
84 large.
|
|
|
85
|
|
|
86 We use VEC_quick_push here because we know that SSA_NAMES has at
|
|
|
87 least 50 elements reserved in it. */
|
|
|
88 VEC_quick_push (tree, SSANAMES (fn), NULL_TREE);
|
|
|
89 FREE_SSANAMES (fn) = NULL;
|
|
|
90 }
|
|
|
91
|
|
|
92 /* Finalize management of SSA_NAMEs. */
|
|
|
93
|
|
|
94 void
|
|
|
95 fini_ssanames (void)
|
|
|
96 {
|
|
|
97 VEC_free (tree, gc, SSANAMES (cfun));
|
|
|
98 FREE_SSANAMES (cfun) = NULL;
|
|
|
99 }
|
|
|
100
|
|
|
101 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */
|
|
|
102
|
|
|
103 #ifdef GATHER_STATISTICS
|
|
|
104 void
|
|
|
105 ssanames_print_statistics (void)
|
|
|
106 {
|
|
|
107 fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
|
|
|
108 fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
|
|
|
109 }
|
|
|
110 #endif
|
|
|
111
|
|
|
112 /* Return an SSA_NAME node for variable VAR defined in statement STMT
|
|
|
113 in function FN. STMT may be an empty statement for artificial
|
|
|
114 references (e.g., default definitions created when a variable is
|
|
|
115 used without a preceding definition). */
|
|
|
116
|
|
|
117 tree
|
|
|
118 make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
|
|
|
119 {
|
|
|
120 tree t;
|
|
|
121 use_operand_p imm;
|
|
|
122
|
|
|
123 gcc_assert (DECL_P (var));
|
|
|
124
|
|
|
125 /* If our free list has an element, then use it. */
|
|
|
126 if (FREE_SSANAMES (fn))
|
|
|
127 {
|
|
|
128 t = FREE_SSANAMES (fn);
|
|
|
129 FREE_SSANAMES (fn) = TREE_CHAIN (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. */
|
|
|
136 gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL);
|
|
|
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
|
|
|
173 void
|
|
|
174 release_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 #ifdef ENABLE_CHECKING
|
|
|
206 verify_imm_links (stderr, var);
|
|
|
207 #endif
|
|
|
208 while (imm->next != imm)
|
|
|
209 delink_imm_use (imm->next);
|
|
|
210
|
|
|
211 VEC_replace (tree, SSANAMES (cfun),
|
|
|
212 SSA_NAME_VERSION (var), NULL_TREE);
|
|
|
213 memset (var, 0, tree_size (var));
|
|
|
214
|
|
|
215 imm->prev = imm;
|
|
|
216 imm->next = imm;
|
|
|
217 imm->loc.ssa_name = var;
|
|
|
218
|
|
|
219 /* First put back the right tree node so that the tree checking
|
|
|
220 macros do not complain. */
|
|
|
221 TREE_SET_CODE (var, SSA_NAME);
|
|
|
222
|
|
|
223 /* Restore the version number. */
|
|
|
224 SSA_NAME_VERSION (var) = saved_ssa_name_version;
|
|
|
225
|
|
|
226 /* Hopefully this can go away once we have the new incremental
|
|
|
227 SSA updating code installed. */
|
|
|
228 SSA_NAME_VAR (var) = saved_ssa_name_var;
|
|
|
229
|
|
|
230 /* Note this SSA_NAME is now in the first list. */
|
|
|
231 SSA_NAME_IN_FREE_LIST (var) = 1;
|
|
|
232
|
|
|
233 /* And finally link it into the free list. */
|
|
|
234 TREE_CHAIN (var) = FREE_SSANAMES (cfun);
|
|
|
235 FREE_SSANAMES (cfun) = var;
|
|
|
236 }
|
|
|
237 }
|
|
|
238
|
|
|
239 /* Creates a duplicate of a ssa name NAME defined in statement STMT. */
|
|
|
240
|
|
|
241 tree
|
|
|
242 duplicate_ssa_name (tree name, gimple stmt)
|
|
|
243 {
|
|
|
244 tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt);
|
|
|
245 struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
|
|
|
246
|
|
|
247 if (old_ptr_info)
|
|
|
248 duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
|
|
|
249
|
|
|
250 return new_name;
|
|
|
251 }
|
|
|
252
|
|
|
253
|
|
|
254 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
|
|
|
255 the SSA name NAME. */
|
|
|
256
|
|
|
257 void
|
|
|
258 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
|
|
|
259 {
|
|
|
260 struct ptr_info_def *new_ptr_info;
|
|
|
261
|
|
|
262 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
|
|
|
263 gcc_assert (!SSA_NAME_PTR_INFO (name));
|
|
|
264
|
|
|
265 if (!ptr_info)
|
|
|
266 return;
|
|
|
267
|
|
|
268 new_ptr_info = GGC_NEW (struct ptr_info_def);
|
|
|
269 *new_ptr_info = *ptr_info;
|
|
|
270
|
|
|
271 if (ptr_info->pt_vars)
|
|
|
272 {
|
|
|
273 new_ptr_info->pt_vars = BITMAP_GGC_ALLOC ();
|
|
|
274 bitmap_copy (new_ptr_info->pt_vars, ptr_info->pt_vars);
|
|
|
275 }
|
|
|
276
|
|
|
277 SSA_NAME_PTR_INFO (name) = new_ptr_info;
|
|
|
278 }
|
|
|
279
|
|
|
280
|
|
|
281 /* Release all the SSA_NAMEs created by STMT. */
|
|
|
282
|
|
|
283 void
|
|
|
284 release_defs (gimple stmt)
|
|
|
285 {
|
|
|
286 tree def;
|
|
|
287 ssa_op_iter iter;
|
|
|
288
|
|
|
289 /* Make sure that we are in SSA. Otherwise, operand cache may point
|
|
|
290 to garbage. */
|
|
|
291 gcc_assert (gimple_in_ssa_p (cfun));
|
|
|
292
|
|
|
293 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
|
|
|
294 if (TREE_CODE (def) == SSA_NAME)
|
|
|
295 release_ssa_name (def);
|
|
|
296 }
|
|
|
297
|
|
|
298
|
|
|
299 /* Replace the symbol associated with SSA_NAME with SYM. */
|
|
|
300
|
|
|
301 void
|
|
|
302 replace_ssa_name_symbol (tree ssa_name, tree sym)
|
|
|
303 {
|
|
|
304 SSA_NAME_VAR (ssa_name) = sym;
|
|
|
305 TREE_TYPE (ssa_name) = TREE_TYPE (sym);
|
|
|
306 }
|
|
|
307
|
|
|
308 /* Return SSA names that are unused to GGC memory. This is used to keep
|
|
|
309 footprint of compiler during interprocedural optimization.
|
|
|
310 As a side effect the SSA_NAME_VERSION number reuse is reduced
|
|
|
311 so this function should not be used too often. */
|
|
|
312 static unsigned int
|
|
|
313 release_dead_ssa_names (void)
|
|
|
314 {
|
|
|
315 tree t, next;
|
|
|
316 int n = 0;
|
|
|
317 referenced_var_iterator rvi;
|
|
|
318
|
|
|
319 /* Current defs point to various dead SSA names that in turn points to dead
|
|
|
320 statements so bunch of dead memory is held from releasing. */
|
|
|
321 FOR_EACH_REFERENCED_VAR (t, rvi)
|
|
|
322 set_current_def (t, NULL);
|
|
|
323 /* Now release the freelist. */
|
|
|
324 for (t = FREE_SSANAMES (cfun); t; t = next)
|
|
|
325 {
|
|
|
326 next = TREE_CHAIN (t);
|
|
|
327 /* Dangling pointers might make GGC to still see dead SSA names, so it is
|
|
|
328 important to unlink the list and avoid GGC from seeing all subsequent
|
|
|
329 SSA names. In longer run we want to have all dangling pointers here
|
|
|
330 removed (since they usually go through dead statements that consume
|
|
|
331 considerable amounts of memory). */
|
|
|
332 TREE_CHAIN (t) = NULL_TREE;
|
|
|
333 n++;
|
|
|
334 }
|
|
|
335 FREE_SSANAMES (cfun) = NULL;
|
|
|
336
|
|
|
337 /* Cgraph edges has been invalidated and point to dead statement. We need to
|
|
|
338 remove them now and will rebuild it before next IPA pass. */
|
|
|
339 cgraph_node_remove_callees (cgraph_node (current_function_decl));
|
|
|
340
|
|
|
341 if (dump_file)
|
|
|
342 fprintf (dump_file, "Released %i names, %.2f%%\n", n, n * 100.0 / num_ssa_names);
|
|
|
343 return 0;
|
|
|
344 }
|
|
|
345
|
|
|
346 struct gimple_opt_pass pass_release_ssa_names =
|
|
|
347 {
|
|
|
348 {
|
|
|
349 GIMPLE_PASS,
|
|
|
350 "release_ssa", /* name */
|
|
|
351 NULL, /* gate */
|
|
|
352 release_dead_ssa_names, /* execute */
|
|
|
353 NULL, /* sub */
|
|
|
354 NULL, /* next */
|
|
|
355 0, /* static_pass_number */
|
|
|
356 0, /* tv_id */
|
|
|
357 PROP_ssa, /* properties_required */
|
|
|
358 0, /* properties_provided */
|
|
|
359 0, /* properties_destroyed */
|
|
|
360 0, /* todo_flags_start */
|
|
|
361 TODO_dump_func /* todo_flags_finish */
|
|
|
362 }
|
|
|
363 };
|
