]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Generic routines for manipulating SSA_NAME expressions |
d1e082c2 | 2 | Copyright (C) 2003-2013 Free Software Foundation, Inc. |
7072a650 | 3 | |
6de9cd9a | 4 | This file is part of GCC. |
b8698a0f | 5 | |
6de9cd9a DN |
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 | |
9dcd6f09 | 8 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a | 9 | any later version. |
b8698a0f | 10 | |
6de9cd9a DN |
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. | |
b8698a0f | 15 | |
6de9cd9a | 16 | You should have received a copy of the GNU General Public License |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
0e61db61 | 19 | |
6de9cd9a DN |
20 | #include "config.h" |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
23 | #include "tm.h" | |
24 | #include "tree.h" | |
7a300452 | 25 | #include "tree-ssa.h" |
7faade0f | 26 | #include "tree-pass.h" |
6de9cd9a DN |
27 | |
28 | /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs, | |
29 | many of which may be thrown away shortly after their creation if jumps | |
b8698a0f | 30 | were threaded through PHI nodes. |
6de9cd9a DN |
31 | |
32 | While our garbage collection mechanisms will handle this situation, it | |
33 | is extremely wasteful to create nodes and throw them away, especially | |
34 | when the nodes can be reused. | |
35 | ||
36 | For PR 8361, we can significantly reduce the number of nodes allocated | |
37 | and thus the total amount of memory allocated by managing SSA_NAMEs a | |
38 | little. This additionally helps reduce the amount of work done by the | |
39 | garbage collector. Similar results have been seen on a wider variety | |
40 | of tests (such as the compiler itself). | |
41 | ||
42 | Right now we maintain our free list on a per-function basis. It may | |
43 | or may not make sense to maintain the free list for the duration of | |
b8698a0f | 44 | a compilation unit. |
6de9cd9a DN |
45 | |
46 | External code should rely solely upon HIGHEST_SSA_VERSION and the | |
47 | externally defined functions. External code should not know about | |
48 | the details of the free list management. | |
49 | ||
50 | External code should also not assume the version number on nodes is | |
51 | monotonically increasing. We reuse the version number when we | |
52 | reuse an SSA_NAME expression. This helps keep arrays and bitmaps | |
cd030c07 | 53 | more compact. */ |
6de9cd9a | 54 | |
6de9cd9a DN |
55 | |
56 | /* Version numbers with special meanings. We start allocating new version | |
57 | numbers after the special ones. */ | |
58 | #define UNUSED_NAME_VERSION 0 | |
59 | ||
6de9cd9a DN |
60 | unsigned int ssa_name_nodes_reused; |
61 | unsigned int ssa_name_nodes_created; | |
6de9cd9a | 62 | |
5db9ba0c DN |
63 | /* Initialize management of SSA_NAMEs to default SIZE. If SIZE is |
64 | zero use default. */ | |
6de9cd9a DN |
65 | |
66 | void | |
5db9ba0c | 67 | init_ssanames (struct function *fn, int size) |
6de9cd9a | 68 | { |
5db9ba0c DN |
69 | if (size < 50) |
70 | size = 50; | |
71 | ||
9771b263 | 72 | vec_alloc (SSANAMES (fn), size); |
95a3742c DN |
73 | |
74 | /* Version 0 is special, so reserve the first slot in the table. Though | |
75 | currently unused, we may use version 0 in alias analysis as part of | |
76 | the heuristics used to group aliases when the alias sets are too | |
d2fce91b KH |
77 | large. |
78 | ||
9771b263 | 79 | We use vec::quick_push here because we know that SSA_NAMES has at |
078885f2 | 80 | least 50 elements reserved in it. */ |
9771b263 | 81 | SSANAMES (fn)->quick_push (NULL_TREE); |
5db9ba0c | 82 | FREE_SSANAMES (fn) = NULL; |
5006671f | 83 | |
13714310 RG |
84 | fn->gimple_df->ssa_renaming_needed = 0; |
85 | fn->gimple_df->rename_vops = 0; | |
6de9cd9a DN |
86 | } |
87 | ||
88 | /* Finalize management of SSA_NAMEs. */ | |
89 | ||
90 | void | |
91 | fini_ssanames (void) | |
92 | { | |
9771b263 DN |
93 | vec_free (SSANAMES (cfun)); |
94 | vec_free (FREE_SSANAMES (cfun)); | |
6de9cd9a DN |
95 | } |
96 | ||
97 | /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */ | |
98 | ||
6de9cd9a DN |
99 | void |
100 | ssanames_print_statistics (void) | |
101 | { | |
102 | fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created); | |
103 | fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused); | |
104 | } | |
6de9cd9a | 105 | |
5db9ba0c DN |
106 | /* Return an SSA_NAME node for variable VAR defined in statement STMT |
107 | in function FN. STMT may be an empty statement for artificial | |
108 | references (e.g., default definitions created when a variable is | |
109 | used without a preceding definition). */ | |
6de9cd9a DN |
110 | |
111 | tree | |
726a989a | 112 | make_ssa_name_fn (struct function *fn, tree var, gimple stmt) |
6de9cd9a DN |
113 | { |
114 | tree t; | |
f47c96aa | 115 | use_operand_p imm; |
6de9cd9a | 116 | |
67386041 RG |
117 | gcc_assert (TREE_CODE (var) == VAR_DECL |
118 | || TREE_CODE (var) == PARM_DECL | |
70b5e7dc RG |
119 | || TREE_CODE (var) == RESULT_DECL |
120 | || (TYPE_P (var) && is_gimple_reg_type (var))); | |
6de9cd9a | 121 | |
6f2aec07 | 122 | /* If our free list has an element, then use it. */ |
9771b263 | 123 | if (!vec_safe_is_empty (FREE_SSANAMES (fn))) |
6de9cd9a | 124 | { |
9771b263 | 125 | t = FREE_SSANAMES (fn)->pop (); |
7aa6d18a SB |
126 | if (GATHER_STATISTICS) |
127 | ssa_name_nodes_reused++; | |
6de9cd9a | 128 | |
6f2aec07 JL |
129 | /* The node was cleared out when we put it on the free list, so |
130 | there is no need to do so again here. */ | |
131 | gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL); | |
9771b263 | 132 | (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t; |
6de9cd9a DN |
133 | } |
134 | else | |
135 | { | |
136 | t = make_node (SSA_NAME); | |
9771b263 DN |
137 | SSA_NAME_VERSION (t) = SSANAMES (fn)->length (); |
138 | vec_safe_push (SSANAMES (fn), t); | |
7aa6d18a SB |
139 | if (GATHER_STATISTICS) |
140 | ssa_name_nodes_created++; | |
6de9cd9a DN |
141 | } |
142 | ||
70b5e7dc RG |
143 | if (TYPE_P (var)) |
144 | { | |
145 | TREE_TYPE (t) = var; | |
146 | SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE); | |
147 | } | |
148 | else | |
149 | { | |
150 | TREE_TYPE (t) = TREE_TYPE (var); | |
151 | SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var); | |
152 | } | |
6de9cd9a | 153 | SSA_NAME_DEF_STMT (t) = stmt; |
95a3742c | 154 | SSA_NAME_PTR_INFO (t) = NULL; |
53b4bf74 | 155 | SSA_NAME_IN_FREE_LIST (t) = 0; |
cfaab3a9 | 156 | SSA_NAME_IS_DEFAULT_DEF (t) = 0; |
f430bae8 AM |
157 | imm = &(SSA_NAME_IMM_USE_NODE (t)); |
158 | imm->use = NULL; | |
159 | imm->prev = imm; | |
160 | imm->next = imm; | |
726a989a | 161 | imm->loc.ssa_name = t; |
6de9cd9a DN |
162 | |
163 | return t; | |
164 | } | |
165 | ||
95a3742c | 166 | |
6de9cd9a | 167 | /* We no longer need the SSA_NAME expression VAR, release it so that |
b8698a0f | 168 | it may be reused. |
6de9cd9a DN |
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 | { | |
8b11a64c ZD |
178 | if (!var) |
179 | return; | |
180 | ||
53b4bf74 DN |
181 | /* Never release the default definition for a symbol. It's a |
182 | special SSA name that should always exist once it's created. */ | |
cfaab3a9 | 183 | if (SSA_NAME_IS_DEFAULT_DEF (var)) |
53b4bf74 DN |
184 | return; |
185 | ||
84d65814 DN |
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 | } | |
b0382c67 | 193 | |
6de9cd9a DN |
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 | |
b8698a0f | 197 | been put on the free list. |
6de9cd9a DN |
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 | { | |
6f2aec07 JL |
203 | tree saved_ssa_name_var = SSA_NAME_VAR (var); |
204 | int saved_ssa_name_version = SSA_NAME_VERSION (var); | |
f47c96aa | 205 | use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var)); |
f430bae8 | 206 | |
b5b8b0ac | 207 | if (MAY_HAVE_DEBUG_STMTS) |
0ca5af51 | 208 | insert_debug_temp_for_var_def (NULL, var); |
b5b8b0ac | 209 | |
f430bae8 AM |
210 | #ifdef ENABLE_CHECKING |
211 | verify_imm_links (stderr, var); | |
212 | #endif | |
213 | while (imm->next != imm) | |
0e61db61 | 214 | delink_imm_use (imm->next); |
6f2aec07 | 215 | |
9771b263 | 216 | (*SSANAMES (cfun))[SSA_NAME_VERSION (var)] = NULL_TREE; |
6f2aec07 JL |
217 | memset (var, 0, tree_size (var)); |
218 | ||
f430bae8 AM |
219 | imm->prev = imm; |
220 | imm->next = imm; | |
726a989a RB |
221 | imm->loc.ssa_name = var; |
222 | ||
6f2aec07 JL |
223 | /* First put back the right tree node so that the tree checking |
224 | macros do not complain. */ | |
225 | TREE_SET_CODE (var, SSA_NAME); | |
226 | ||
227 | /* Restore the version number. */ | |
228 | SSA_NAME_VERSION (var) = saved_ssa_name_version; | |
229 | ||
230 | /* Hopefully this can go away once we have the new incremental | |
231 | SSA updating code installed. */ | |
70b5e7dc | 232 | SET_SSA_NAME_VAR_OR_IDENTIFIER (var, saved_ssa_name_var); |
6f2aec07 JL |
233 | |
234 | /* Note this SSA_NAME is now in the first list. */ | |
6de9cd9a | 235 | SSA_NAME_IN_FREE_LIST (var) = 1; |
6f2aec07 | 236 | |
4b1a4694 | 237 | /* And finally put it on the free list. */ |
9771b263 | 238 | vec_safe_push (FREE_SSANAMES (cfun), var); |
6de9cd9a DN |
239 | } |
240 | } | |
241 | ||
644ffefd MJ |
242 | /* If the alignment of the pointer described by PI is known, return true and |
243 | store the alignment and the deviation from it into *ALIGNP and *MISALIGNP | |
244 | respectively. Otherwise return false. */ | |
245 | ||
246 | bool | |
247 | get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp, | |
248 | unsigned int *misalignp) | |
249 | { | |
250 | if (pi->align) | |
251 | { | |
252 | *alignp = pi->align; | |
253 | *misalignp = pi->misalign; | |
254 | return true; | |
255 | } | |
256 | else | |
257 | return false; | |
258 | } | |
259 | ||
260 | /* State that the pointer described by PI has unknown alignment. */ | |
261 | ||
262 | void | |
263 | mark_ptr_info_alignment_unknown (struct ptr_info_def *pi) | |
264 | { | |
265 | pi->align = 0; | |
266 | pi->misalign = 0; | |
267 | } | |
268 | ||
269 | /* Store the the power-of-two byte alignment and the deviation from that | |
270 | alignment of pointer described by PI to ALIOGN and MISALIGN | |
271 | respectively. */ | |
272 | ||
273 | void | |
274 | set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align, | |
275 | unsigned int misalign) | |
276 | { | |
277 | gcc_checking_assert (align != 0); | |
278 | gcc_assert ((align & (align - 1)) == 0); | |
279 | gcc_assert ((misalign & ~(align - 1)) == 0); | |
280 | ||
281 | pi->align = align; | |
282 | pi->misalign = misalign; | |
283 | } | |
284 | ||
073a8998 | 285 | /* If pointer described by PI has known alignment, increase its known |
644ffefd MJ |
286 | misalignment by INCREMENT modulo its current alignment. */ |
287 | ||
288 | void | |
289 | adjust_ptr_info_misalignment (struct ptr_info_def *pi, | |
290 | unsigned int increment) | |
291 | { | |
292 | if (pi->align != 0) | |
293 | { | |
294 | pi->misalign += increment; | |
295 | pi->misalign &= (pi->align - 1); | |
296 | } | |
297 | } | |
d7621d3c | 298 | |
1be38ccb RG |
299 | /* Return the alias information associated with pointer T. It creates a |
300 | new instance if none existed. */ | |
301 | ||
302 | struct ptr_info_def * | |
303 | get_ptr_info (tree t) | |
d7621d3c | 304 | { |
1be38ccb | 305 | struct ptr_info_def *pi; |
8bb46326 | 306 | |
1be38ccb | 307 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); |
8bb46326 | 308 | |
1be38ccb RG |
309 | pi = SSA_NAME_PTR_INFO (t); |
310 | if (pi == NULL) | |
311 | { | |
312 | pi = ggc_alloc_cleared_ptr_info_def (); | |
313 | pt_solution_reset (&pi->pt); | |
644ffefd | 314 | mark_ptr_info_alignment_unknown (pi); |
1be38ccb RG |
315 | SSA_NAME_PTR_INFO (t) = pi; |
316 | } | |
8bb46326 | 317 | |
1be38ccb RG |
318 | return pi; |
319 | } | |
8bb46326 | 320 | |
070ecdfd RG |
321 | |
322 | /* Creates a new SSA name using the template NAME tobe defined by | |
323 | statement STMT in function FN. */ | |
324 | ||
325 | tree | |
326 | copy_ssa_name_fn (struct function *fn, tree name, gimple stmt) | |
327 | { | |
70b5e7dc RG |
328 | tree new_name; |
329 | ||
330 | if (SSA_NAME_VAR (name)) | |
331 | new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt); | |
332 | else | |
333 | { | |
334 | new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt); | |
335 | SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name)); | |
336 | } | |
337 | ||
338 | return new_name; | |
070ecdfd RG |
339 | } |
340 | ||
341 | ||
8bb46326 | 342 | /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by |
84d65814 | 343 | the SSA name NAME. */ |
8bb46326 DN |
344 | |
345 | void | |
346 | duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) | |
347 | { | |
d7621d3c ZD |
348 | struct ptr_info_def *new_ptr_info; |
349 | ||
8bb46326 DN |
350 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); |
351 | gcc_assert (!SSA_NAME_PTR_INFO (name)); | |
352 | ||
353 | if (!ptr_info) | |
354 | return; | |
d7621d3c | 355 | |
a9429e29 | 356 | new_ptr_info = ggc_alloc_ptr_info_def (); |
8bb46326 | 357 | *new_ptr_info = *ptr_info; |
d7621d3c | 358 | |
8bb46326 | 359 | SSA_NAME_PTR_INFO (name) = new_ptr_info; |
d7621d3c ZD |
360 | } |
361 | ||
53b4bf74 | 362 | |
070ecdfd RG |
363 | /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT |
364 | in function FN. */ | |
1be38ccb RG |
365 | |
366 | tree | |
070ecdfd | 367 | duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt) |
1be38ccb | 368 | { |
070ecdfd | 369 | tree new_name = copy_ssa_name_fn (fn, name, stmt); |
1be38ccb RG |
370 | struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); |
371 | ||
372 | if (old_ptr_info) | |
373 | duplicate_ssa_name_ptr_info (new_name, old_ptr_info); | |
374 | ||
375 | return new_name; | |
376 | } | |
377 | ||
378 | ||
53b4bf74 DN |
379 | /* Release all the SSA_NAMEs created by STMT. */ |
380 | ||
381 | void | |
726a989a | 382 | release_defs (gimple stmt) |
53b4bf74 | 383 | { |
4c124b4c AM |
384 | tree def; |
385 | ssa_op_iter iter; | |
53b4bf74 | 386 | |
1ff54bfb KH |
387 | /* Make sure that we are in SSA. Otherwise, operand cache may point |
388 | to garbage. */ | |
5cd4ec7f | 389 | gcc_assert (gimple_in_ssa_p (cfun)); |
1ff54bfb | 390 | |
4c124b4c | 391 | FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) |
80d8221e JH |
392 | if (TREE_CODE (def) == SSA_NAME) |
393 | release_ssa_name (def); | |
53b4bf74 DN |
394 | } |
395 | ||
bbc630f5 DN |
396 | |
397 | /* Replace the symbol associated with SSA_NAME with SYM. */ | |
398 | ||
399 | void | |
400 | replace_ssa_name_symbol (tree ssa_name, tree sym) | |
401 | { | |
70b5e7dc | 402 | SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym); |
bbc630f5 DN |
403 | TREE_TYPE (ssa_name) = TREE_TYPE (sym); |
404 | } | |
7faade0f | 405 | |
14f60a5a RG |
406 | /* Return SSA names that are unused to GGC memory and compact the SSA |
407 | version namespace. This is used to keep footprint of compiler during | |
408 | interprocedural optimization. */ | |
7faade0f JH |
409 | static unsigned int |
410 | release_dead_ssa_names (void) | |
411 | { | |
14f60a5a | 412 | unsigned i, j; |
9771b263 | 413 | int n = vec_safe_length (FREE_SSANAMES (cfun)); |
14f60a5a | 414 | |
7faade0f | 415 | /* Now release the freelist. */ |
9771b263 | 416 | vec_free (FREE_SSANAMES (cfun)); |
03b1d134 | 417 | |
14f60a5a RG |
418 | /* And compact the SSA number space. We make sure to not change the |
419 | relative order of SSA versions. */ | |
9771b263 | 420 | for (i = 1, j = 1; i < cfun->gimple_df->ssa_names->length (); ++i) |
14f60a5a RG |
421 | { |
422 | tree name = ssa_name (i); | |
423 | if (name) | |
424 | { | |
425 | if (i != j) | |
426 | { | |
427 | SSA_NAME_VERSION (name) = j; | |
9771b263 | 428 | (*cfun->gimple_df->ssa_names)[j] = name; |
14f60a5a RG |
429 | } |
430 | j++; | |
431 | } | |
432 | } | |
9771b263 | 433 | cfun->gimple_df->ssa_names->truncate (j); |
14f60a5a | 434 | |
736fe2d5 | 435 | statistics_counter_event (cfun, "SSA names released", n); |
14f60a5a | 436 | statistics_counter_event (cfun, "SSA name holes removed", i - j); |
7faade0f | 437 | if (dump_file) |
14f60a5a RG |
438 | fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n", |
439 | n, n * 100.0 / num_ssa_names, i - j); | |
7faade0f JH |
440 | return 0; |
441 | } | |
442 | ||
27a4cd48 DM |
443 | namespace { |
444 | ||
445 | const pass_data pass_data_release_ssa_names = | |
7faade0f | 446 | { |
27a4cd48 DM |
447 | GIMPLE_PASS, /* type */ |
448 | "release_ssa", /* name */ | |
449 | OPTGROUP_NONE, /* optinfo_flags */ | |
450 | false, /* has_gate */ | |
451 | true, /* has_execute */ | |
452 | TV_TREE_SSA_OTHER, /* tv_id */ | |
453 | PROP_ssa, /* properties_required */ | |
454 | 0, /* properties_provided */ | |
455 | 0, /* properties_destroyed */ | |
456 | TODO_remove_unused_locals, /* todo_flags_start */ | |
457 | 0, /* todo_flags_finish */ | |
7faade0f | 458 | }; |
27a4cd48 DM |
459 | |
460 | class pass_release_ssa_names : public gimple_opt_pass | |
461 | { | |
462 | public: | |
463 | pass_release_ssa_names(gcc::context *ctxt) | |
464 | : gimple_opt_pass(pass_data_release_ssa_names, ctxt) | |
465 | {} | |
466 | ||
467 | /* opt_pass methods: */ | |
468 | unsigned int execute () { return release_dead_ssa_names (); } | |
469 | ||
470 | }; // class pass_release_ssa_names | |
471 | ||
472 | } // anon namespace | |
473 | ||
474 | gimple_opt_pass * | |
475 | make_pass_release_ssa_names (gcc::context *ctxt) | |
476 | { | |
477 | return new pass_release_ssa_names (ctxt); | |
478 | } |