* configure: Regenerated.
[official-gcc.git] / gcc / tree-ssanames.c
blob57a1b482cea4c385963163e4520499ba5ef24ca1
1 /* Generic routines for manipulating SSA_NAME expressions
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
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
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
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.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "tree-flow.h"
27 #include "tree-pass.h"
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
31 were threaded through PHI nodes.
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.
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).
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
45 a compilation unit.
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.
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.
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. */
60 /* Version numbers with special meanings. We start allocating new version
61 numbers after the special ones. */
62 #define UNUSED_NAME_VERSION 0
64 unsigned int ssa_name_nodes_reused;
65 unsigned int ssa_name_nodes_created;
67 /* Initialize management of SSA_NAMEs to default SIZE. If SIZE is
68 zero use default. */
70 void
71 init_ssanames (struct function *fn, int size)
73 if (size < 50)
74 size = 50;
76 SSANAMES (fn) = VEC_alloc (tree, gc, size);
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
81 large.
83 We use VEC_quick_push here because we know that SSA_NAMES has at
84 least 50 elements reserved in it. */
85 VEC_quick_push (tree, SSANAMES (fn), NULL_TREE);
86 FREE_SSANAMES (fn) = NULL;
88 fn->gimple_df->ssa_renaming_needed = 0;
89 fn->gimple_df->rename_vops = 0;
92 /* Finalize management of SSA_NAMEs. */
94 void
95 fini_ssanames (void)
97 VEC_free (tree, gc, SSANAMES (cfun));
98 VEC_free (tree, gc, FREE_SSANAMES (cfun));
101 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */
103 void
104 ssanames_print_statistics (void)
106 fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
107 fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
110 /* Return an SSA_NAME node for variable VAR defined in statement STMT
111 in function FN. STMT may be an empty statement for artificial
112 references (e.g., default definitions created when a variable is
113 used without a preceding definition). */
115 tree
116 make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
118 tree t;
119 use_operand_p imm;
121 gcc_assert (TREE_CODE (var) == VAR_DECL
122 || TREE_CODE (var) == PARM_DECL
123 || TREE_CODE (var) == RESULT_DECL
124 || (TYPE_P (var) && is_gimple_reg_type (var)));
126 /* If our free list has an element, then use it. */
127 if (!VEC_empty (tree, FREE_SSANAMES (fn)))
129 t = VEC_pop (tree, FREE_SSANAMES (fn));
130 if (GATHER_STATISTICS)
131 ssa_name_nodes_reused++;
133 /* The node was cleared out when we put it on the free list, so
134 there is no need to do so again here. */
135 gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL);
136 VEC_replace (tree, SSANAMES (fn), SSA_NAME_VERSION (t), t);
138 else
140 t = make_node (SSA_NAME);
141 SSA_NAME_VERSION (t) = VEC_length (tree, SSANAMES (fn));
142 VEC_safe_push (tree, gc, SSANAMES (fn), t);
143 if (GATHER_STATISTICS)
144 ssa_name_nodes_created++;
147 if (TYPE_P (var))
149 TREE_TYPE (t) = var;
150 SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
152 else
154 TREE_TYPE (t) = TREE_TYPE (var);
155 SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
157 SSA_NAME_DEF_STMT (t) = stmt;
158 SSA_NAME_PTR_INFO (t) = NULL;
159 SSA_NAME_IN_FREE_LIST (t) = 0;
160 SSA_NAME_IS_DEFAULT_DEF (t) = 0;
161 imm = &(SSA_NAME_IMM_USE_NODE (t));
162 imm->use = NULL;
163 imm->prev = imm;
164 imm->next = imm;
165 imm->loc.ssa_name = t;
167 return t;
171 /* We no longer need the SSA_NAME expression VAR, release it so that
172 it may be reused.
174 Note it is assumed that no calls to make_ssa_name will be made
175 until all uses of the ssa name are released and that the only
176 use of the SSA_NAME expression is to check its SSA_NAME_VAR. All
177 other fields must be assumed clobbered. */
179 void
180 release_ssa_name (tree var)
182 if (!var)
183 return;
185 /* Never release the default definition for a symbol. It's a
186 special SSA name that should always exist once it's created. */
187 if (SSA_NAME_IS_DEFAULT_DEF (var))
188 return;
190 /* If VAR has been registered for SSA updating, don't remove it.
191 After update_ssa has run, the name will be released. */
192 if (name_registered_for_update_p (var))
194 release_ssa_name_after_update_ssa (var);
195 return;
198 /* release_ssa_name can be called multiple times on a single SSA_NAME.
199 However, it should only end up on our free list one time. We
200 keep a status bit in the SSA_NAME node itself to indicate it has
201 been put on the free list.
203 Note that once on the freelist you can not reference the SSA_NAME's
204 defining statement. */
205 if (! SSA_NAME_IN_FREE_LIST (var))
207 tree saved_ssa_name_var = SSA_NAME_VAR (var);
208 int saved_ssa_name_version = SSA_NAME_VERSION (var);
209 use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
211 if (MAY_HAVE_DEBUG_STMTS)
212 insert_debug_temp_for_var_def (NULL, var);
214 #ifdef ENABLE_CHECKING
215 verify_imm_links (stderr, var);
216 #endif
217 while (imm->next != imm)
218 delink_imm_use (imm->next);
220 VEC_replace (tree, SSANAMES (cfun),
221 SSA_NAME_VERSION (var), NULL_TREE);
222 memset (var, 0, tree_size (var));
224 imm->prev = imm;
225 imm->next = imm;
226 imm->loc.ssa_name = var;
228 /* First put back the right tree node so that the tree checking
229 macros do not complain. */
230 TREE_SET_CODE (var, SSA_NAME);
232 /* Restore the version number. */
233 SSA_NAME_VERSION (var) = saved_ssa_name_version;
235 /* Hopefully this can go away once we have the new incremental
236 SSA updating code installed. */
237 SET_SSA_NAME_VAR_OR_IDENTIFIER (var, saved_ssa_name_var);
239 /* Note this SSA_NAME is now in the first list. */
240 SSA_NAME_IN_FREE_LIST (var) = 1;
242 /* And finally put it on the free list. */
243 VEC_safe_push (tree, gc, FREE_SSANAMES (cfun), var);
247 /* If the alignment of the pointer described by PI is known, return true and
248 store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
249 respectively. Otherwise return false. */
251 bool
252 get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
253 unsigned int *misalignp)
255 if (pi->align)
257 *alignp = pi->align;
258 *misalignp = pi->misalign;
259 return true;
261 else
262 return false;
265 /* State that the pointer described by PI has unknown alignment. */
267 void
268 mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
270 pi->align = 0;
271 pi->misalign = 0;
274 /* Store the the power-of-two byte alignment and the deviation from that
275 alignment of pointer described by PI to ALIOGN and MISALIGN
276 respectively. */
278 void
279 set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
280 unsigned int misalign)
282 gcc_checking_assert (align != 0);
283 gcc_assert ((align & (align - 1)) == 0);
284 gcc_assert ((misalign & ~(align - 1)) == 0);
286 pi->align = align;
287 pi->misalign = misalign;
290 /* If pointer described by PI has known alignment, increase its known
291 misalignment by INCREMENT modulo its current alignment. */
293 void
294 adjust_ptr_info_misalignment (struct ptr_info_def *pi,
295 unsigned int increment)
297 if (pi->align != 0)
299 pi->misalign += increment;
300 pi->misalign &= (pi->align - 1);
304 /* Return the alias information associated with pointer T. It creates a
305 new instance if none existed. */
307 struct ptr_info_def *
308 get_ptr_info (tree t)
310 struct ptr_info_def *pi;
312 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
314 pi = SSA_NAME_PTR_INFO (t);
315 if (pi == NULL)
317 pi = ggc_alloc_cleared_ptr_info_def ();
318 pt_solution_reset (&pi->pt);
319 mark_ptr_info_alignment_unknown (pi);
320 SSA_NAME_PTR_INFO (t) = pi;
323 return pi;
327 /* Creates a new SSA name using the template NAME tobe defined by
328 statement STMT in function FN. */
330 tree
331 copy_ssa_name_fn (struct function *fn, tree name, gimple stmt)
333 tree new_name;
335 if (SSA_NAME_VAR (name))
336 new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
337 else
339 new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
340 SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
343 return new_name;
347 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
348 the SSA name NAME. */
350 void
351 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
353 struct ptr_info_def *new_ptr_info;
355 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
356 gcc_assert (!SSA_NAME_PTR_INFO (name));
358 if (!ptr_info)
359 return;
361 new_ptr_info = ggc_alloc_ptr_info_def ();
362 *new_ptr_info = *ptr_info;
364 SSA_NAME_PTR_INFO (name) = new_ptr_info;
368 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
369 in function FN. */
371 tree
372 duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt)
374 tree new_name = copy_ssa_name_fn (fn, name, stmt);
375 struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
377 if (old_ptr_info)
378 duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
380 return new_name;
384 /* Release all the SSA_NAMEs created by STMT. */
386 void
387 release_defs (gimple stmt)
389 tree def;
390 ssa_op_iter iter;
392 /* Make sure that we are in SSA. Otherwise, operand cache may point
393 to garbage. */
394 gcc_assert (gimple_in_ssa_p (cfun));
396 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
397 if (TREE_CODE (def) == SSA_NAME)
398 release_ssa_name (def);
402 /* Replace the symbol associated with SSA_NAME with SYM. */
404 void
405 replace_ssa_name_symbol (tree ssa_name, tree sym)
407 SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
408 TREE_TYPE (ssa_name) = TREE_TYPE (sym);
411 /* Return SSA names that are unused to GGC memory and compact the SSA
412 version namespace. This is used to keep footprint of compiler during
413 interprocedural optimization. */
414 static unsigned int
415 release_dead_ssa_names (void)
417 unsigned i, j;
418 int n = VEC_length (tree, FREE_SSANAMES (cfun));
420 /* Now release the freelist. */
421 VEC_free (tree, gc, FREE_SSANAMES (cfun));
422 FREE_SSANAMES (cfun) = NULL;
424 /* And compact the SSA number space. We make sure to not change the
425 relative order of SSA versions. */
426 for (i = 1, j = 1; i < VEC_length (tree, cfun->gimple_df->ssa_names); ++i)
428 tree name = ssa_name (i);
429 if (name)
431 if (i != j)
433 SSA_NAME_VERSION (name) = j;
434 VEC_replace (tree, cfun->gimple_df->ssa_names, j, name);
436 j++;
439 VEC_truncate (tree, cfun->gimple_df->ssa_names, j);
441 statistics_counter_event (cfun, "SSA names released", n);
442 statistics_counter_event (cfun, "SSA name holes removed", i - j);
443 if (dump_file)
444 fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
445 n, n * 100.0 / num_ssa_names, i - j);
446 return 0;
449 struct gimple_opt_pass pass_release_ssa_names =
452 GIMPLE_PASS,
453 "release_ssa", /* name */
454 NULL, /* gate */
455 release_dead_ssa_names, /* execute */
456 NULL, /* sub */
457 NULL, /* next */
458 0, /* static_pass_number */
459 TV_TREE_SSA_OTHER, /* tv_id */
460 PROP_ssa, /* properties_required */
461 0, /* properties_provided */
462 0, /* properties_destroyed */
463 0, /* todo_flags_start */
464 0 /* todo_flags_finish */