Commit | Line | Data |
---|---|---|
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 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify | |
8 | it under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 3, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, | |
13 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | GNU General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along 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 | |
65 | unsigned int ssa_name_nodes_reused; | |
66 | unsigned 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 | ||
72 | void | |
73 | init_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 | ||
95 | void | |
96 | fini_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 | |
105 | void | |
106 | ssanames_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 | ||
118 | tree | |
119 | make_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 | ||
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 | 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 | ||
245 | struct ptr_info_def * | |
246 | get_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 | ||
268 | void | |
269 | duplicate_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 | ||
288 | tree | |
289 | duplicate_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 | ||
303 | void | |
304 | release_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 | ||
321 | void | |
322 | replace_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. */ | |
332 | static unsigned int | |
333 | release_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 | ||
354 | struct 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 | }; |