]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* Generic routines for manipulating SSA_NAME expressions |
3bb6785a | 2 | Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. |
1fa3a8f6 | 3 | |
4ee9c684 | 4 | This file is part of GCC. |
1fa3a8f6 | 5 | |
4ee9c684 | 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 2, or (at your option) | |
9 | any later version. | |
1fa3a8f6 | 10 | |
4ee9c684 | 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. | |
1fa3a8f6 | 15 | |
4ee9c684 | 16 | You should have received a copy of the GNU General Public License |
17 | along with GCC; see the file COPYING. If not, write to | |
67ce556b | 18 | the Free Software Foundation, 51 Franklin Street, Fifth Floor, |
19 | Boston, MA 02110-1301, USA. */ | |
1fa3a8f6 | 20 | |
4ee9c684 | 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" | |
c211d998 | 28 | #include "tree-flow.h" |
49290934 | 29 | #include "tree-pass.h" |
4ee9c684 | 30 | |
31 | /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs, | |
32 | many of which may be thrown away shortly after their creation if jumps | |
33 | were threaded through PHI nodes. | |
34 | ||
35 | While our garbage collection mechanisms will handle this situation, it | |
36 | is extremely wasteful to create nodes and throw them away, especially | |
37 | when the nodes can be reused. | |
38 | ||
39 | For PR 8361, we can significantly reduce the number of nodes allocated | |
40 | and thus the total amount of memory allocated by managing SSA_NAMEs a | |
41 | little. This additionally helps reduce the amount of work done by the | |
42 | garbage collector. Similar results have been seen on a wider variety | |
43 | of tests (such as the compiler itself). | |
44 | ||
45 | Right now we maintain our free list on a per-function basis. It may | |
46 | or may not make sense to maintain the free list for the duration of | |
47 | a compilation unit. | |
48 | ||
49 | External code should rely solely upon HIGHEST_SSA_VERSION and the | |
50 | externally defined functions. External code should not know about | |
51 | the details of the free list management. | |
52 | ||
53 | External code should also not assume the version number on nodes is | |
54 | monotonically increasing. We reuse the version number when we | |
55 | reuse an SSA_NAME expression. This helps keep arrays and bitmaps | |
56 | more compact. | |
57 | ||
58 | We could also use a zone allocator for these objects since they have | |
59 | a very well defined lifetime. If someone wants to experiment with that | |
60 | this is the place to try it. */ | |
4ee9c684 | 61 | |
62 | /* Version numbers with special meanings. We start allocating new version | |
63 | numbers after the special ones. */ | |
64 | #define UNUSED_NAME_VERSION 0 | |
65 | ||
66 | #ifdef GATHER_STATISTICS | |
67 | unsigned int ssa_name_nodes_reused; | |
68 | unsigned int ssa_name_nodes_created; | |
69 | #endif | |
70 | ||
71 | /* Initialize management of SSA_NAMEs. */ | |
72 | ||
73 | void | |
74 | init_ssanames (void) | |
75 | { | |
2d04fd8d | 76 | SSANAMES (cfun) = VEC_alloc (tree, gc, 50); |
c211d998 | 77 | |
78 | /* Version 0 is special, so reserve the first slot in the table. Though | |
79 | currently unused, we may use version 0 in alias analysis as part of | |
80 | the heuristics used to group aliases when the alias sets are too | |
8b292c7f | 81 | large. |
82 | ||
83 | We use VEC_quick_push here because we know that SSA_NAMES has at | |
b62e1ab2 | 84 | least 50 elements reserved in it. */ |
2d04fd8d | 85 | VEC_quick_push (tree, SSANAMES (cfun), NULL_TREE); |
86 | FREE_SSANAMES (cfun) = NULL; | |
4ee9c684 | 87 | } |
88 | ||
89 | /* Finalize management of SSA_NAMEs. */ | |
90 | ||
91 | void | |
92 | fini_ssanames (void) | |
93 | { | |
2d04fd8d | 94 | VEC_free (tree, gc, SSANAMES (cfun)); |
95 | FREE_SSANAMES (cfun) = NULL; | |
4ee9c684 | 96 | } |
97 | ||
98 | /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */ | |
99 | ||
100 | #ifdef GATHER_STATISTICS | |
101 | void | |
102 | ssanames_print_statistics (void) | |
103 | { | |
104 | fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created); | |
105 | fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused); | |
106 | } | |
107 | #endif | |
108 | ||
109 | /* Return an SSA_NAME node for variable VAR defined in statement STMT. | |
110 | STMT may be an empty statement for artificial references (e.g., default | |
111 | definitions created when a variable is used without a preceding | |
112 | definition). */ | |
113 | ||
114 | tree | |
115 | make_ssa_name (tree var, tree stmt) | |
116 | { | |
117 | tree t; | |
b66731e8 | 118 | use_operand_p imm; |
4ee9c684 | 119 | |
8c0963c4 | 120 | gcc_assert (DECL_P (var) |
121 | || TREE_CODE (var) == INDIRECT_REF); | |
122 | ||
35cc02b5 | 123 | gcc_assert (!stmt |
124 | || EXPR_P (stmt) || GIMPLE_STMT_P (stmt) | |
125 | || TREE_CODE (stmt) == PHI_NODE); | |
4ee9c684 | 126 | |
fa0f49c6 | 127 | /* If our free list has an element, then use it. */ |
2d04fd8d | 128 | if (FREE_SSANAMES (cfun)) |
4ee9c684 | 129 | { |
2d04fd8d | 130 | t = FREE_SSANAMES (cfun); |
131 | FREE_SSANAMES (cfun) = TREE_CHAIN (FREE_SSANAMES (cfun)); | |
4ee9c684 | 132 | #ifdef GATHER_STATISTICS |
133 | ssa_name_nodes_reused++; | |
134 | #endif | |
135 | ||
fa0f49c6 | 136 | /* The node was cleared out when we put it on the free list, so |
137 | there is no need to do so again here. */ | |
138 | gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL); | |
2d04fd8d | 139 | VEC_replace (tree, SSANAMES (cfun), SSA_NAME_VERSION (t), t); |
4ee9c684 | 140 | } |
141 | else | |
142 | { | |
143 | t = make_node (SSA_NAME); | |
c211d998 | 144 | SSA_NAME_VERSION (t) = num_ssa_names; |
2d04fd8d | 145 | VEC_safe_push (tree, gc, SSANAMES (cfun), t); |
4ee9c684 | 146 | #ifdef GATHER_STATISTICS |
147 | ssa_name_nodes_created++; | |
148 | #endif | |
149 | } | |
150 | ||
151 | TREE_TYPE (t) = TREE_TYPE (var); | |
152 | SSA_NAME_VAR (t) = var; | |
153 | SSA_NAME_DEF_STMT (t) = stmt; | |
c211d998 | 154 | SSA_NAME_PTR_INFO (t) = NULL; |
81d08033 | 155 | SSA_NAME_IN_FREE_LIST (t) = 0; |
de6ed584 | 156 | SSA_NAME_IS_DEFAULT_DEF (t) = 0; |
22aa74c4 | 157 | imm = &(SSA_NAME_IMM_USE_NODE (t)); |
158 | imm->use = NULL; | |
159 | imm->prev = imm; | |
160 | imm->next = imm; | |
161 | imm->stmt = t; | |
4ee9c684 | 162 | |
163 | return t; | |
164 | } | |
165 | ||
c211d998 | 166 | |
4ee9c684 | 167 | /* We no longer need the SSA_NAME expression VAR, release it so that |
168 | it may be reused. | |
169 | ||
170 | Note it is assumed that no calls to make_ssa_name will be made | |
171 | until all uses of the ssa name are released and that the only | |
172 | use of the SSA_NAME expression is to check its SSA_NAME_VAR. All | |
173 | other fields must be assumed clobbered. */ | |
174 | ||
175 | void | |
176 | release_ssa_name (tree var) | |
177 | { | |
dec41e98 | 178 | if (!var) |
179 | return; | |
180 | ||
81d08033 | 181 | /* Never release the default definition for a symbol. It's a |
182 | special SSA name that should always exist once it's created. */ | |
de6ed584 | 183 | if (SSA_NAME_IS_DEFAULT_DEF (var)) |
81d08033 | 184 | return; |
185 | ||
095dcfa3 | 186 | /* If VAR has been registered for SSA updating, don't remove it. |
187 | After update_ssa has run, the name will be released. */ | |
188 | if (name_registered_for_update_p (var)) | |
189 | { | |
190 | release_ssa_name_after_update_ssa (var); | |
191 | return; | |
192 | } | |
deb78f9e | 193 | |
4ee9c684 | 194 | /* release_ssa_name can be called multiple times on a single SSA_NAME. |
195 | However, it should only end up on our free list one time. We | |
196 | keep a status bit in the SSA_NAME node itself to indicate it has | |
197 | been put on the free list. | |
198 | ||
199 | Note that once on the freelist you can not reference the SSA_NAME's | |
200 | defining statement. */ | |
201 | if (! SSA_NAME_IN_FREE_LIST (var)) | |
202 | { | |
fa0f49c6 | 203 | tree saved_ssa_name_var = SSA_NAME_VAR (var); |
204 | int saved_ssa_name_version = SSA_NAME_VERSION (var); | |
b66731e8 | 205 | use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var)); |
22aa74c4 | 206 | |
207 | #ifdef ENABLE_CHECKING | |
208 | verify_imm_links (stderr, var); | |
209 | #endif | |
210 | while (imm->next != imm) | |
1fa3a8f6 | 211 | delink_imm_use (imm->next); |
fa0f49c6 | 212 | |
2d04fd8d | 213 | VEC_replace (tree, SSANAMES (cfun), |
214 | SSA_NAME_VERSION (var), NULL_TREE); | |
fa0f49c6 | 215 | memset (var, 0, tree_size (var)); |
216 | ||
22aa74c4 | 217 | imm->prev = imm; |
218 | imm->next = imm; | |
219 | imm->stmt = var; | |
fa0f49c6 | 220 | /* First put back the right tree node so that the tree checking |
221 | macros do not complain. */ | |
222 | TREE_SET_CODE (var, SSA_NAME); | |
223 | ||
224 | /* Restore the version number. */ | |
225 | SSA_NAME_VERSION (var) = saved_ssa_name_version; | |
226 | ||
227 | /* Hopefully this can go away once we have the new incremental | |
228 | SSA updating code installed. */ | |
229 | SSA_NAME_VAR (var) = saved_ssa_name_var; | |
230 | ||
231 | /* Note this SSA_NAME is now in the first list. */ | |
4ee9c684 | 232 | SSA_NAME_IN_FREE_LIST (var) = 1; |
fa0f49c6 | 233 | |
234 | /* And finally link it into the free list. */ | |
2d04fd8d | 235 | TREE_CHAIN (var) = FREE_SSANAMES (cfun); |
236 | FREE_SSANAMES (cfun) = var; | |
4ee9c684 | 237 | } |
238 | } | |
239 | ||
3aaaf63f | 240 | /* Creates a duplicate of a ssa name NAME defined in statement STMT. */ |
241 | ||
242 | tree | |
243 | duplicate_ssa_name (tree name, tree stmt) | |
244 | { | |
245 | tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt); | |
246 | struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); | |
abb91f0b | 247 | |
248 | if (old_ptr_info) | |
249 | duplicate_ssa_name_ptr_info (new_name, old_ptr_info); | |
250 | ||
251 | return new_name; | |
252 | } | |
253 | ||
254 | ||
255 | /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by | |
095dcfa3 | 256 | the SSA name NAME. */ |
abb91f0b | 257 | |
258 | void | |
259 | duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) | |
260 | { | |
3aaaf63f | 261 | struct ptr_info_def *new_ptr_info; |
262 | ||
abb91f0b | 263 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); |
264 | gcc_assert (!SSA_NAME_PTR_INFO (name)); | |
265 | ||
266 | if (!ptr_info) | |
267 | return; | |
3aaaf63f | 268 | |
f0d6e81c | 269 | new_ptr_info = GGC_NEW (struct ptr_info_def); |
abb91f0b | 270 | *new_ptr_info = *ptr_info; |
3aaaf63f | 271 | |
abb91f0b | 272 | if (ptr_info->pt_vars) |
3aaaf63f | 273 | { |
274 | new_ptr_info->pt_vars = BITMAP_GGC_ALLOC (); | |
abb91f0b | 275 | bitmap_copy (new_ptr_info->pt_vars, ptr_info->pt_vars); |
3aaaf63f | 276 | } |
277 | ||
abb91f0b | 278 | SSA_NAME_PTR_INFO (name) = new_ptr_info; |
3aaaf63f | 279 | } |
280 | ||
81d08033 | 281 | |
282 | /* Release all the SSA_NAMEs created by STMT. */ | |
283 | ||
284 | void | |
285 | release_defs (tree stmt) | |
286 | { | |
43daa21e | 287 | tree def; |
288 | ssa_op_iter iter; | |
81d08033 | 289 | |
d7eb56de | 290 | /* Make sure that we are in SSA. Otherwise, operand cache may point |
291 | to garbage. */ | |
2d04fd8d | 292 | gcc_assert (gimple_in_ssa_p (cfun)); |
d7eb56de | 293 | |
43daa21e | 294 | FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) |
ac6db781 | 295 | if (TREE_CODE (def) == SSA_NAME) |
296 | release_ssa_name (def); | |
81d08033 | 297 | } |
298 | ||
cbbefea4 | 299 | |
300 | /* Replace the symbol associated with SSA_NAME with SYM. */ | |
301 | ||
302 | void | |
303 | replace_ssa_name_symbol (tree ssa_name, tree sym) | |
304 | { | |
305 | SSA_NAME_VAR (ssa_name) = sym; | |
306 | TREE_TYPE (ssa_name) = TREE_TYPE (sym); | |
307 | } | |
49290934 | 308 | |
309 | /* Return SSA names that are unused to GGC memory. This is used to keep | |
310 | footprint of compiler during interprocedural optimization. | |
311 | As a side effect the SSA_NAME_VERSION number reuse is reduced | |
312 | so this function should not be used too often. */ | |
313 | static unsigned int | |
314 | release_dead_ssa_names (void) | |
315 | { | |
316 | tree t, next; | |
317 | int n = 0; | |
318 | referenced_var_iterator rvi; | |
319 | ||
320 | /* Current defs point to various dead SSA names that in turn points to dead | |
0d424440 | 321 | statements so bunch of dead memory is held from releasing. */ |
49290934 | 322 | FOR_EACH_REFERENCED_VAR (t, rvi) |
323 | set_current_def (t, NULL); | |
324 | /* Now release the freelist. */ | |
325 | for (t = FREE_SSANAMES (cfun); t; t = next) | |
326 | { | |
327 | next = TREE_CHAIN (t); | |
5fa09f4d | 328 | /* Dangling pointers might make GGC to still see dead SSA names, so it is |
329 | important to unlink the list and avoid GGC from seeing all subsequent | |
330 | SSA names. In longer run we want to have all dangling pointers here | |
0d424440 | 331 | removed (since they usually go through dead statements that consume |
5fa09f4d | 332 | considerable amounts of memory). */ |
333 | TREE_CHAIN (t) = NULL_TREE; | |
49290934 | 334 | n++; |
335 | } | |
336 | FREE_SSANAMES (cfun) = NULL; | |
eb254442 | 337 | |
338 | /* Cgraph edges has been invalidated and point to dead statement. We need to | |
339 | remove them now and will rebuild it before next IPA pass. */ | |
340 | cgraph_node_remove_callees (cgraph_node (current_function_decl)); | |
341 | ||
49290934 | 342 | if (dump_file) |
343 | fprintf (dump_file, "Released %i names, %.2f%%\n", n, n * 100.0 / num_ssa_names); | |
344 | return 0; | |
345 | } | |
346 | ||
347 | struct tree_opt_pass pass_release_ssa_names = | |
348 | { | |
349 | "release_ssa", /* name */ | |
350 | NULL, /* gate */ | |
351 | release_dead_ssa_names, /* execute */ | |
352 | NULL, /* sub */ | |
353 | NULL, /* next */ | |
354 | 0, /* static_pass_number */ | |
355 | 0, /* tv_id */ | |
356 | PROP_ssa, /* properties_required */ | |
357 | 0, /* properties_provided */ | |
358 | 0, /* properties_destroyed */ | |
359 | 0, /* todo_flags_start */ | |
360 | 0, /* todo_flags_finish */ | |
361 | 0 /* letter */ | |
362 | }; |