]>
Commit | Line | Data |
---|---|---|
4ee9c684 | 1 | /* Generic routines for manipulating SSA_NAME expressions |
2 | Copyright (C) 2003 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 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" | |
c211d998 | 28 | #include "tree-flow.h" |
4ee9c684 | 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 | ||
c211d998 | 61 | /* Array of all SSA_NAMEs used in the function. */ |
62 | varray_type ssa_names; | |
deb78f9e | 63 | |
64 | /* Bitmap of ssa names marked for rewriting. */ | |
65 | bitmap ssa_names_to_rewrite; | |
66 | ||
4ee9c684 | 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 | ||
deb78f9e | 80 | /* Returns true if ssa name VAR is marked for rewrite. */ |
81 | ||
82 | bool | |
83 | marked_for_rewrite_p (tree var) | |
84 | { | |
85 | if (ssa_names_to_rewrite | |
86 | && bitmap_bit_p (ssa_names_to_rewrite, SSA_NAME_VERSION (var))) | |
87 | return true; | |
88 | ||
89 | return false; | |
90 | } | |
91 | ||
92 | /* Returns true if any ssa name is marked for rewrite. */ | |
93 | ||
94 | bool | |
95 | any_marked_for_rewrite_p (void) | |
96 | { | |
97 | if (!ssa_names_to_rewrite) | |
98 | return false; | |
99 | ||
100 | return bitmap_first_set_bit (ssa_names_to_rewrite) != -1; | |
101 | } | |
102 | ||
103 | /* Mark ssa name VAR for rewriting. */ | |
104 | ||
105 | void | |
106 | mark_for_rewrite (tree var) | |
107 | { | |
108 | if (!ssa_names_to_rewrite) | |
109 | ssa_names_to_rewrite = BITMAP_XMALLOC (); | |
110 | ||
111 | bitmap_set_bit (ssa_names_to_rewrite, SSA_NAME_VERSION (var)); | |
112 | } | |
113 | ||
114 | /* Unmark all ssa names marked for rewrite. */ | |
115 | ||
116 | void | |
117 | unmark_all_for_rewrite (void) | |
118 | { | |
119 | if (!ssa_names_to_rewrite) | |
120 | return; | |
121 | ||
122 | bitmap_clear (ssa_names_to_rewrite); | |
123 | } | |
124 | ||
125 | /* Return the bitmap of ssa names to rewrite. Copy the bitmap, | |
126 | so that the optimizers cannot access internals directly */ | |
127 | ||
128 | bitmap | |
129 | marked_ssa_names (void) | |
130 | { | |
131 | bitmap ret = BITMAP_XMALLOC (); | |
132 | if (ssa_names_to_rewrite) | |
133 | bitmap_copy (ret, ssa_names_to_rewrite); | |
134 | ||
135 | return ret; | |
136 | } | |
137 | ||
4ee9c684 | 138 | /* Initialize management of SSA_NAMEs. */ |
139 | ||
140 | void | |
141 | init_ssanames (void) | |
142 | { | |
c211d998 | 143 | VARRAY_TREE_INIT (ssa_names, 50, "ssa_names table"); |
144 | ||
145 | /* Version 0 is special, so reserve the first slot in the table. Though | |
146 | currently unused, we may use version 0 in alias analysis as part of | |
147 | the heuristics used to group aliases when the alias sets are too | |
148 | large. */ | |
149 | VARRAY_PUSH_TREE (ssa_names, NULL_TREE); | |
4ee9c684 | 150 | free_ssanames = NULL; |
151 | } | |
152 | ||
153 | /* Finalize management of SSA_NAMEs. */ | |
154 | ||
155 | void | |
156 | fini_ssanames (void) | |
157 | { | |
4ba32638 | 158 | ggc_free (ssa_names); |
159 | ssa_names = NULL; | |
4ee9c684 | 160 | free_ssanames = NULL; |
161 | } | |
162 | ||
163 | /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */ | |
164 | ||
165 | #ifdef GATHER_STATISTICS | |
166 | void | |
167 | ssanames_print_statistics (void) | |
168 | { | |
169 | fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created); | |
170 | fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused); | |
171 | } | |
172 | #endif | |
173 | ||
174 | /* Return an SSA_NAME node for variable VAR defined in statement STMT. | |
175 | STMT may be an empty statement for artificial references (e.g., default | |
176 | definitions created when a variable is used without a preceding | |
177 | definition). */ | |
178 | ||
179 | tree | |
180 | make_ssa_name (tree var, tree stmt) | |
181 | { | |
182 | tree t; | |
183 | ||
184 | #if defined ENABLE_CHECKING | |
185 | if ((!DECL_P (var) | |
186 | && TREE_CODE (var) != INDIRECT_REF) | |
bb445479 | 187 | || (stmt |
188 | && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (TREE_CODE (stmt))) | |
4ee9c684 | 189 | && TREE_CODE (stmt) != PHI_NODE)) |
190 | abort (); | |
191 | #endif | |
192 | ||
193 | /* If our free list has an element, then use it. Also reuse the | |
194 | SSA version number of the element on the free list which helps | |
195 | keep sbitmaps and arrays sized HIGHEST_SSA_VERSION smaller. */ | |
196 | if (free_ssanames) | |
197 | { | |
198 | unsigned int save_version; | |
199 | ||
200 | t = free_ssanames; | |
201 | free_ssanames = TREE_CHAIN (free_ssanames); | |
202 | #ifdef GATHER_STATISTICS | |
203 | ssa_name_nodes_reused++; | |
204 | #endif | |
205 | ||
206 | /* Clear the node so that it looks just like one we would have | |
207 | received from make_node. */ | |
208 | save_version = SSA_NAME_VERSION (t); | |
209 | memset (t, 0, tree_size (t)); | |
210 | TREE_SET_CODE (t, SSA_NAME); | |
211 | SSA_NAME_VERSION (t) = save_version; | |
212 | } | |
213 | else | |
214 | { | |
215 | t = make_node (SSA_NAME); | |
c211d998 | 216 | SSA_NAME_VERSION (t) = num_ssa_names; |
217 | VARRAY_PUSH_TREE (ssa_names, t); | |
4ee9c684 | 218 | #ifdef GATHER_STATISTICS |
219 | ssa_name_nodes_created++; | |
220 | #endif | |
221 | } | |
222 | ||
223 | TREE_TYPE (t) = TREE_TYPE (var); | |
224 | SSA_NAME_VAR (t) = var; | |
225 | SSA_NAME_DEF_STMT (t) = stmt; | |
c211d998 | 226 | SSA_NAME_PTR_INFO (t) = NULL; |
81d08033 | 227 | SSA_NAME_IN_FREE_LIST (t) = 0; |
4ee9c684 | 228 | |
229 | return t; | |
230 | } | |
231 | ||
c211d998 | 232 | |
4ee9c684 | 233 | /* We no longer need the SSA_NAME expression VAR, release it so that |
234 | it may be reused. | |
235 | ||
236 | Note it is assumed that no calls to make_ssa_name will be made | |
237 | until all uses of the ssa name are released and that the only | |
238 | use of the SSA_NAME expression is to check its SSA_NAME_VAR. All | |
239 | other fields must be assumed clobbered. */ | |
240 | ||
241 | void | |
242 | release_ssa_name (tree var) | |
243 | { | |
81d08033 | 244 | /* Never release the default definition for a symbol. It's a |
245 | special SSA name that should always exist once it's created. */ | |
246 | if (var == var_ann (SSA_NAME_VAR (var))->default_def) | |
247 | return; | |
248 | ||
deb78f9e | 249 | /* If the ssa name is marked for rewriting, it may have multiple definitions, |
250 | but we may happen to remove just one of them. So do not remove the | |
251 | ssa name now. */ | |
252 | if (marked_for_rewrite_p (var)) | |
253 | return; | |
254 | ||
4ee9c684 | 255 | /* release_ssa_name can be called multiple times on a single SSA_NAME. |
256 | However, it should only end up on our free list one time. We | |
257 | keep a status bit in the SSA_NAME node itself to indicate it has | |
258 | been put on the free list. | |
259 | ||
260 | Note that once on the freelist you can not reference the SSA_NAME's | |
261 | defining statement. */ | |
262 | if (! SSA_NAME_IN_FREE_LIST (var)) | |
263 | { | |
264 | SSA_NAME_IN_FREE_LIST (var) = 1; | |
265 | TREE_CHAIN (var) = free_ssanames; | |
266 | free_ssanames = var; | |
267 | } | |
268 | } | |
269 | ||
3aaaf63f | 270 | /* Creates a duplicate of a ssa name NAME defined in statement STMT. */ |
271 | ||
272 | tree | |
273 | duplicate_ssa_name (tree name, tree stmt) | |
274 | { | |
275 | tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt); | |
276 | struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); | |
277 | struct ptr_info_def *new_ptr_info; | |
278 | ||
279 | if (!old_ptr_info) | |
280 | return new_name; | |
281 | ||
282 | new_ptr_info = ggc_alloc (sizeof (struct ptr_info_def)); | |
283 | *new_ptr_info = *old_ptr_info; | |
284 | ||
285 | if (old_ptr_info->pt_vars) | |
286 | { | |
287 | new_ptr_info->pt_vars = BITMAP_GGC_ALLOC (); | |
288 | bitmap_copy (new_ptr_info->pt_vars, old_ptr_info->pt_vars); | |
289 | } | |
290 | ||
291 | SSA_NAME_PTR_INFO (new_name) = new_ptr_info; | |
292 | return new_name; | |
293 | } | |
294 | ||
81d08033 | 295 | |
296 | /* Release all the SSA_NAMEs created by STMT. */ | |
297 | ||
298 | void | |
299 | release_defs (tree stmt) | |
300 | { | |
43daa21e | 301 | tree def; |
302 | ssa_op_iter iter; | |
81d08033 | 303 | |
43daa21e | 304 | FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) |
ac6db781 | 305 | if (TREE_CODE (def) == SSA_NAME) |
306 | release_ssa_name (def); | |
81d08033 | 307 | } |
308 | ||
cbbefea4 | 309 | |
310 | /* Replace the symbol associated with SSA_NAME with SYM. */ | |
311 | ||
312 | void | |
313 | replace_ssa_name_symbol (tree ssa_name, tree sym) | |
314 | { | |
315 | SSA_NAME_VAR (ssa_name) = sym; | |
316 | TREE_TYPE (ssa_name) = TREE_TYPE (sym); | |
317 | } | |
318 | ||
4ee9c684 | 319 | #include "gt-tree-ssanames.h" |