]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Generic routines for manipulating SSA_NAME expressions |
6615c446 | 2 | Copyright (C) 2003, 2004 Free Software Foundation, Inc. |
6de9cd9a DN |
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 2, 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 COPYING. If not, write to | |
18 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
19 | Boston, MA 02111-1307, USA. */ | |
20 | ||
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" | |
95a3742c | 28 | #include "tree-flow.h" |
6de9cd9a DN |
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 | ||
95a3742c DN |
61 | /* Array of all SSA_NAMEs used in the function. */ |
62 | varray_type ssa_names; | |
b0382c67 ZD |
63 | |
64 | /* Bitmap of ssa names marked for rewriting. */ | |
7932a3db | 65 | static bitmap ssa_names_to_rewrite; |
b0382c67 | 66 | |
6de9cd9a DN |
67 | /* Free list of SSA_NAMEs. This list is wiped at the end of each function |
68 | after we leave SSA form. */ | |
69 | static GTY (()) tree free_ssanames; | |
70 | ||
71 | /* Version numbers with special meanings. We start allocating new version | |
72 | numbers after the special ones. */ | |
73 | #define UNUSED_NAME_VERSION 0 | |
74 | ||
75 | #ifdef GATHER_STATISTICS | |
76 | unsigned int ssa_name_nodes_reused; | |
77 | unsigned int ssa_name_nodes_created; | |
78 | #endif | |
79 | ||
b0382c67 ZD |
80 | /* Returns true if ssa name VAR is marked for rewrite. */ |
81 | ||
82 | bool | |
83 | marked_for_rewrite_p (tree var) | |
84 | { | |
7932a3db | 85 | return bitmap_bit_p (ssa_names_to_rewrite, SSA_NAME_VERSION (var)); |
b0382c67 ZD |
86 | } |
87 | ||
88 | /* Returns true if any ssa name is marked for rewrite. */ | |
89 | ||
90 | bool | |
91 | any_marked_for_rewrite_p (void) | |
92 | { | |
93 | if (!ssa_names_to_rewrite) | |
94 | return false; | |
95 | ||
eb59b8de | 96 | return !bitmap_empty_p (ssa_names_to_rewrite); |
b0382c67 ZD |
97 | } |
98 | ||
99 | /* Mark ssa name VAR for rewriting. */ | |
100 | ||
101 | void | |
102 | mark_for_rewrite (tree var) | |
103 | { | |
b0382c67 ZD |
104 | bitmap_set_bit (ssa_names_to_rewrite, SSA_NAME_VERSION (var)); |
105 | } | |
106 | ||
107 | /* Unmark all ssa names marked for rewrite. */ | |
108 | ||
109 | void | |
110 | unmark_all_for_rewrite (void) | |
111 | { | |
b0382c67 ZD |
112 | bitmap_clear (ssa_names_to_rewrite); |
113 | } | |
114 | ||
115 | /* Return the bitmap of ssa names to rewrite. Copy the bitmap, | |
116 | so that the optimizers cannot access internals directly */ | |
117 | ||
118 | bitmap | |
119 | marked_ssa_names (void) | |
120 | { | |
121 | bitmap ret = BITMAP_XMALLOC (); | |
7932a3db NS |
122 | |
123 | bitmap_copy (ret, ssa_names_to_rewrite); | |
b0382c67 ZD |
124 | |
125 | return ret; | |
126 | } | |
127 | ||
6de9cd9a DN |
128 | /* Initialize management of SSA_NAMEs. */ |
129 | ||
130 | void | |
131 | init_ssanames (void) | |
132 | { | |
95a3742c DN |
133 | VARRAY_TREE_INIT (ssa_names, 50, "ssa_names table"); |
134 | ||
135 | /* Version 0 is special, so reserve the first slot in the table. Though | |
136 | currently unused, we may use version 0 in alias analysis as part of | |
137 | the heuristics used to group aliases when the alias sets are too | |
138 | large. */ | |
139 | VARRAY_PUSH_TREE (ssa_names, NULL_TREE); | |
6de9cd9a | 140 | free_ssanames = NULL; |
7932a3db | 141 | ssa_names_to_rewrite = BITMAP_XMALLOC (); |
6de9cd9a DN |
142 | } |
143 | ||
144 | /* Finalize management of SSA_NAMEs. */ | |
145 | ||
146 | void | |
147 | fini_ssanames (void) | |
148 | { | |
7932a3db | 149 | BITMAP_XFREE (ssa_names_to_rewrite); |
1e3e17d3 JH |
150 | ggc_free (ssa_names); |
151 | ssa_names = NULL; | |
6de9cd9a DN |
152 | free_ssanames = NULL; |
153 | } | |
154 | ||
155 | /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */ | |
156 | ||
157 | #ifdef GATHER_STATISTICS | |
158 | void | |
159 | ssanames_print_statistics (void) | |
160 | { | |
161 | fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created); | |
162 | fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused); | |
163 | } | |
164 | #endif | |
165 | ||
166 | /* Return an SSA_NAME node for variable VAR defined in statement STMT. | |
167 | STMT may be an empty statement for artificial references (e.g., default | |
168 | definitions created when a variable is used without a preceding | |
169 | definition). */ | |
170 | ||
171 | tree | |
172 | make_ssa_name (tree var, tree stmt) | |
173 | { | |
174 | tree t; | |
175 | ||
1e128c5f GB |
176 | gcc_assert (DECL_P (var) |
177 | || TREE_CODE (var) == INDIRECT_REF); | |
178 | ||
6615c446 | 179 | gcc_assert (!stmt || EXPR_P (stmt) || TREE_CODE (stmt) == PHI_NODE); |
6de9cd9a | 180 | |
6f2aec07 | 181 | /* If our free list has an element, then use it. */ |
6de9cd9a DN |
182 | if (free_ssanames) |
183 | { | |
6de9cd9a DN |
184 | t = free_ssanames; |
185 | free_ssanames = TREE_CHAIN (free_ssanames); | |
186 | #ifdef GATHER_STATISTICS | |
187 | ssa_name_nodes_reused++; | |
188 | #endif | |
189 | ||
6f2aec07 JL |
190 | /* The node was cleared out when we put it on the free list, so |
191 | there is no need to do so again here. */ | |
192 | gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL); | |
193 | VARRAY_TREE (ssa_names, SSA_NAME_VERSION (t)) = t; | |
6de9cd9a DN |
194 | } |
195 | else | |
196 | { | |
197 | t = make_node (SSA_NAME); | |
95a3742c DN |
198 | SSA_NAME_VERSION (t) = num_ssa_names; |
199 | VARRAY_PUSH_TREE (ssa_names, t); | |
6de9cd9a DN |
200 | #ifdef GATHER_STATISTICS |
201 | ssa_name_nodes_created++; | |
202 | #endif | |
203 | } | |
204 | ||
205 | TREE_TYPE (t) = TREE_TYPE (var); | |
206 | SSA_NAME_VAR (t) = var; | |
207 | SSA_NAME_DEF_STMT (t) = stmt; | |
95a3742c | 208 | SSA_NAME_PTR_INFO (t) = NULL; |
53b4bf74 | 209 | SSA_NAME_IN_FREE_LIST (t) = 0; |
6de9cd9a DN |
210 | |
211 | return t; | |
212 | } | |
213 | ||
95a3742c | 214 | |
6de9cd9a DN |
215 | /* We no longer need the SSA_NAME expression VAR, release it so that |
216 | it may be reused. | |
217 | ||
218 | Note it is assumed that no calls to make_ssa_name will be made | |
219 | until all uses of the ssa name are released and that the only | |
220 | use of the SSA_NAME expression is to check its SSA_NAME_VAR. All | |
221 | other fields must be assumed clobbered. */ | |
222 | ||
223 | void | |
224 | release_ssa_name (tree var) | |
225 | { | |
8b11a64c ZD |
226 | if (!var) |
227 | return; | |
228 | ||
53b4bf74 DN |
229 | /* Never release the default definition for a symbol. It's a |
230 | special SSA name that should always exist once it's created. */ | |
231 | if (var == var_ann (SSA_NAME_VAR (var))->default_def) | |
232 | return; | |
233 | ||
b0382c67 ZD |
234 | /* If the ssa name is marked for rewriting, it may have multiple definitions, |
235 | but we may happen to remove just one of them. So do not remove the | |
236 | ssa name now. */ | |
237 | if (marked_for_rewrite_p (var)) | |
238 | return; | |
239 | ||
6de9cd9a DN |
240 | /* release_ssa_name can be called multiple times on a single SSA_NAME. |
241 | However, it should only end up on our free list one time. We | |
242 | keep a status bit in the SSA_NAME node itself to indicate it has | |
243 | been put on the free list. | |
244 | ||
245 | Note that once on the freelist you can not reference the SSA_NAME's | |
246 | defining statement. */ | |
247 | if (! SSA_NAME_IN_FREE_LIST (var)) | |
248 | { | |
6f2aec07 JL |
249 | tree saved_ssa_name_var = SSA_NAME_VAR (var); |
250 | int saved_ssa_name_version = SSA_NAME_VERSION (var); | |
251 | ||
8b547e44 | 252 | VARRAY_TREE (ssa_names, SSA_NAME_VERSION (var)) = NULL; |
6f2aec07 JL |
253 | memset (var, 0, tree_size (var)); |
254 | ||
255 | /* First put back the right tree node so that the tree checking | |
256 | macros do not complain. */ | |
257 | TREE_SET_CODE (var, SSA_NAME); | |
258 | ||
259 | /* Restore the version number. */ | |
260 | SSA_NAME_VERSION (var) = saved_ssa_name_version; | |
261 | ||
262 | /* Hopefully this can go away once we have the new incremental | |
263 | SSA updating code installed. */ | |
264 | SSA_NAME_VAR (var) = saved_ssa_name_var; | |
265 | ||
266 | /* Note this SSA_NAME is now in the first list. */ | |
6de9cd9a | 267 | SSA_NAME_IN_FREE_LIST (var) = 1; |
6f2aec07 JL |
268 | |
269 | /* And finally link it into the free list. */ | |
6de9cd9a DN |
270 | TREE_CHAIN (var) = free_ssanames; |
271 | free_ssanames = var; | |
272 | } | |
273 | } | |
274 | ||
d7621d3c ZD |
275 | /* Creates a duplicate of a ssa name NAME defined in statement STMT. */ |
276 | ||
277 | tree | |
278 | duplicate_ssa_name (tree name, tree stmt) | |
279 | { | |
280 | tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt); | |
281 | struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); | |
282 | struct ptr_info_def *new_ptr_info; | |
283 | ||
284 | if (!old_ptr_info) | |
285 | return new_name; | |
286 | ||
287 | new_ptr_info = ggc_alloc (sizeof (struct ptr_info_def)); | |
288 | *new_ptr_info = *old_ptr_info; | |
289 | ||
290 | if (old_ptr_info->pt_vars) | |
291 | { | |
292 | new_ptr_info->pt_vars = BITMAP_GGC_ALLOC (); | |
293 | bitmap_copy (new_ptr_info->pt_vars, old_ptr_info->pt_vars); | |
294 | } | |
295 | ||
296 | SSA_NAME_PTR_INFO (new_name) = new_ptr_info; | |
297 | return new_name; | |
298 | } | |
299 | ||
53b4bf74 DN |
300 | |
301 | /* Release all the SSA_NAMEs created by STMT. */ | |
302 | ||
303 | void | |
304 | release_defs (tree stmt) | |
305 | { | |
4c124b4c AM |
306 | tree def; |
307 | ssa_op_iter iter; | |
53b4bf74 | 308 | |
4c124b4c | 309 | FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) |
80d8221e JH |
310 | if (TREE_CODE (def) == SSA_NAME) |
311 | release_ssa_name (def); | |
53b4bf74 DN |
312 | } |
313 | ||
bbc630f5 DN |
314 | |
315 | /* Replace the symbol associated with SSA_NAME with SYM. */ | |
316 | ||
317 | void | |
318 | replace_ssa_name_symbol (tree ssa_name, tree sym) | |
319 | { | |
320 | SSA_NAME_VAR (ssa_name) = sym; | |
321 | TREE_TYPE (ssa_name) = TREE_TYPE (sym); | |
322 | } | |
323 | ||
6de9cd9a | 324 | #include "gt-tree-ssanames.h" |