]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* Generic routines for manipulating SSA_NAME expressions |
d91f7526 | 2 | Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010 |
0b1615c1 | 3 | Free Software Foundation, Inc. |
4 | ||
4ee9c684 | 5 | This file is part of GCC. |
48e1416a | 6 | |
4ee9c684 | 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 | |
8c4c00c1 | 9 | the Free Software Foundation; either version 3, or (at your option) |
4ee9c684 | 10 | any later version. |
48e1416a | 11 | |
4ee9c684 | 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. | |
48e1416a | 16 | |
4ee9c684 | 17 | You should have received a copy of the GNU General Public License |
8c4c00c1 | 18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
1fa3a8f6 | 20 | |
4ee9c684 | 21 | #include "config.h" |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
c211d998 | 26 | #include "tree-flow.h" |
49290934 | 27 | #include "tree-pass.h" |
4ee9c684 | 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 | |
48e1416a | 31 | were threaded through PHI nodes. |
4ee9c684 | 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 | |
48e1416a | 45 | a compilation unit. |
4ee9c684 | 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. */ | |
4ee9c684 | 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 | ||
bcaa2770 | 69 | /* Initialize management of SSA_NAMEs to default SIZE. If SIZE is |
70 | zero use default. */ | |
4ee9c684 | 71 | |
72 | void | |
bcaa2770 | 73 | init_ssanames (struct function *fn, int size) |
4ee9c684 | 74 | { |
bcaa2770 | 75 | if (size < 50) |
76 | size = 50; | |
77 | ||
78 | SSANAMES (fn) = VEC_alloc (tree, gc, size); | |
c211d998 | 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 | |
8b292c7f | 83 | large. |
84 | ||
85 | We use VEC_quick_push here because we know that SSA_NAMES has at | |
b62e1ab2 | 86 | least 50 elements reserved in it. */ |
bcaa2770 | 87 | VEC_quick_push (tree, SSANAMES (fn), NULL_TREE); |
88 | FREE_SSANAMES (fn) = NULL; | |
dd277d48 | 89 | |
90 | SYMS_TO_RENAME (fn) = BITMAP_GGC_ALLOC (); | |
4ee9c684 | 91 | } |
92 | ||
93 | /* Finalize management of SSA_NAMEs. */ | |
94 | ||
95 | void | |
96 | fini_ssanames (void) | |
97 | { | |
2d04fd8d | 98 | VEC_free (tree, gc, SSANAMES (cfun)); |
acb5ba8c | 99 | VEC_free (tree, gc, FREE_SSANAMES (cfun)); |
4ee9c684 | 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 | ||
bcaa2770 | 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). */ | |
4ee9c684 | 117 | |
118 | tree | |
75a70cf9 | 119 | make_ssa_name_fn (struct function *fn, tree var, gimple stmt) |
4ee9c684 | 120 | { |
121 | tree t; | |
b66731e8 | 122 | use_operand_p imm; |
4ee9c684 | 123 | |
75a70cf9 | 124 | gcc_assert (DECL_P (var)); |
4ee9c684 | 125 | |
fa0f49c6 | 126 | /* If our free list has an element, then use it. */ |
acb5ba8c | 127 | if (!VEC_empty (tree, FREE_SSANAMES (fn))) |
4ee9c684 | 128 | { |
acb5ba8c | 129 | t = VEC_pop (tree, FREE_SSANAMES (fn)); |
4ee9c684 | 130 | #ifdef GATHER_STATISTICS |
131 | ssa_name_nodes_reused++; | |
132 | #endif | |
133 | ||
fa0f49c6 | 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); | |
bcaa2770 | 137 | VEC_replace (tree, SSANAMES (fn), SSA_NAME_VERSION (t), t); |
4ee9c684 | 138 | } |
139 | else | |
140 | { | |
141 | t = make_node (SSA_NAME); | |
bcaa2770 | 142 | SSA_NAME_VERSION (t) = VEC_length (tree, SSANAMES (fn)); |
143 | VEC_safe_push (tree, gc, SSANAMES (fn), t); | |
4ee9c684 | 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; | |
c211d998 | 152 | SSA_NAME_PTR_INFO (t) = NULL; |
81d08033 | 153 | SSA_NAME_IN_FREE_LIST (t) = 0; |
de6ed584 | 154 | SSA_NAME_IS_DEFAULT_DEF (t) = 0; |
22aa74c4 | 155 | imm = &(SSA_NAME_IMM_USE_NODE (t)); |
156 | imm->use = NULL; | |
157 | imm->prev = imm; | |
158 | imm->next = imm; | |
75a70cf9 | 159 | imm->loc.ssa_name = t; |
4ee9c684 | 160 | |
161 | return t; | |
162 | } | |
163 | ||
c211d998 | 164 | |
4ee9c684 | 165 | /* We no longer need the SSA_NAME expression VAR, release it so that |
48e1416a | 166 | it may be reused. |
4ee9c684 | 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 | { | |
dec41e98 | 176 | if (!var) |
177 | return; | |
178 | ||
81d08033 | 179 | /* Never release the default definition for a symbol. It's a |
180 | special SSA name that should always exist once it's created. */ | |
de6ed584 | 181 | if (SSA_NAME_IS_DEFAULT_DEF (var)) |
81d08033 | 182 | return; |
183 | ||
095dcfa3 | 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 | } | |
deb78f9e | 191 | |
4ee9c684 | 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 | |
48e1416a | 195 | been put on the free list. |
4ee9c684 | 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 | { | |
fa0f49c6 | 201 | tree saved_ssa_name_var = SSA_NAME_VAR (var); |
202 | int saved_ssa_name_version = SSA_NAME_VERSION (var); | |
b66731e8 | 203 | use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var)); |
22aa74c4 | 204 | |
9845d120 | 205 | if (MAY_HAVE_DEBUG_STMTS) |
688ff29b | 206 | insert_debug_temp_for_var_def (NULL, var); |
9845d120 | 207 | |
22aa74c4 | 208 | #ifdef ENABLE_CHECKING |
209 | verify_imm_links (stderr, var); | |
210 | #endif | |
211 | while (imm->next != imm) | |
1fa3a8f6 | 212 | delink_imm_use (imm->next); |
fa0f49c6 | 213 | |
2d04fd8d | 214 | VEC_replace (tree, SSANAMES (cfun), |
215 | SSA_NAME_VERSION (var), NULL_TREE); | |
fa0f49c6 | 216 | memset (var, 0, tree_size (var)); |
217 | ||
22aa74c4 | 218 | imm->prev = imm; |
219 | imm->next = imm; | |
75a70cf9 | 220 | imm->loc.ssa_name = var; |
221 | ||
fa0f49c6 | 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. */ | |
4ee9c684 | 234 | SSA_NAME_IN_FREE_LIST (var) = 1; |
fa0f49c6 | 235 | |
acb5ba8c | 236 | /* And finally put it on the free list. */ |
237 | VEC_safe_push (tree, gc, FREE_SSANAMES (cfun), var); | |
4ee9c684 | 238 | } |
239 | } | |
240 | ||
3aaaf63f | 241 | |
153c3b50 | 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) | |
3aaaf63f | 247 | { |
153c3b50 | 248 | struct ptr_info_def *pi; |
abb91f0b | 249 | |
153c3b50 | 250 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); |
abb91f0b | 251 | |
153c3b50 | 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 | } | |
abb91f0b | 261 | |
153c3b50 | 262 | return pi; |
263 | } | |
abb91f0b | 264 | |
265 | /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by | |
095dcfa3 | 266 | the SSA name NAME. */ |
abb91f0b | 267 | |
268 | void | |
269 | duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) | |
270 | { | |
3aaaf63f | 271 | struct ptr_info_def *new_ptr_info; |
272 | ||
abb91f0b | 273 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); |
274 | gcc_assert (!SSA_NAME_PTR_INFO (name)); | |
275 | ||
276 | if (!ptr_info) | |
277 | return; | |
3aaaf63f | 278 | |
ba72912a | 279 | new_ptr_info = ggc_alloc_ptr_info_def (); |
abb91f0b | 280 | *new_ptr_info = *ptr_info; |
3aaaf63f | 281 | |
abb91f0b | 282 | SSA_NAME_PTR_INFO (name) = new_ptr_info; |
3aaaf63f | 283 | } |
284 | ||
81d08033 | 285 | |
153c3b50 | 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 | ||
81d08033 | 301 | /* Release all the SSA_NAMEs created by STMT. */ |
302 | ||
303 | void | |
75a70cf9 | 304 | release_defs (gimple stmt) |
81d08033 | 305 | { |
43daa21e | 306 | tree def; |
307 | ssa_op_iter iter; | |
81d08033 | 308 | |
d7eb56de | 309 | /* Make sure that we are in SSA. Otherwise, operand cache may point |
310 | to garbage. */ | |
2d04fd8d | 311 | gcc_assert (gimple_in_ssa_p (cfun)); |
d7eb56de | 312 | |
43daa21e | 313 | FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) |
ac6db781 | 314 | if (TREE_CODE (def) == SSA_NAME) |
315 | release_ssa_name (def); | |
81d08033 | 316 | } |
317 | ||
cbbefea4 | 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 | } | |
49290934 | 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 | { | |
acb5ba8c | 335 | tree t; |
336 | int n = VEC_length (tree, FREE_SSANAMES (cfun)); | |
49290934 | 337 | referenced_var_iterator rvi; |
338 | ||
778cbf2b | 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. */ | |
a23e00ae | 341 | FOR_EACH_REFERENCED_VAR (cfun, t, rvi) |
49290934 | 342 | set_current_def (t, NULL); |
343 | /* Now release the freelist. */ | |
acb5ba8c | 344 | VEC_free (tree, gc, FREE_SSANAMES (cfun)); |
49290934 | 345 | FREE_SSANAMES (cfun) = NULL; |
eb254442 | 346 | |
778cbf2b | 347 | statistics_counter_event (cfun, "SSA names released", n); |
49290934 | 348 | if (dump_file) |
778cbf2b | 349 | fprintf (dump_file, "Released %i names, %.2f%%\n", |
350 | n, n * 100.0 / num_ssa_names); | |
49290934 | 351 | return 0; |
352 | } | |
353 | ||
20099e35 | 354 | struct gimple_opt_pass pass_release_ssa_names = |
49290934 | 355 | { |
20099e35 | 356 | { |
357 | GIMPLE_PASS, | |
49290934 | 358 | "release_ssa", /* name */ |
359 | NULL, /* gate */ | |
360 | release_dead_ssa_names, /* execute */ | |
361 | NULL, /* sub */ | |
362 | NULL, /* next */ | |
363 | 0, /* static_pass_number */ | |
4b366dd3 | 364 | TV_TREE_SSA_OTHER, /* tv_id */ |
49290934 | 365 | PROP_ssa, /* properties_required */ |
366 | 0, /* properties_provided */ | |
367 | 0, /* properties_destroyed */ | |
368 | 0, /* todo_flags_start */ | |
771e2890 | 369 | 0 /* todo_flags_finish */ |
20099e35 | 370 | } |
49290934 | 371 | }; |