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)
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/>. */
23 #include "coretypes.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
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
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
71 init_ssanames (struct function
*fn
, int size
)
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
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 SYMS_TO_RENAME (fn
) = BITMAP_GGC_ALLOC ();
91 /* Finalize management of SSA_NAMEs. */
96 VEC_free (tree
, gc
, SSANAMES (cfun
));
97 VEC_free (tree
, gc
, FREE_SSANAMES (cfun
));
100 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */
103 ssanames_print_statistics (void)
105 fprintf (stderr
, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created
);
106 fprintf (stderr
, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused
);
109 /* Return an SSA_NAME node for variable VAR defined in statement STMT
110 in function FN. STMT may be an empty statement for artificial
111 references (e.g., default definitions created when a variable is
112 used without a preceding definition). */
115 make_ssa_name_fn (struct function
*fn
, tree var
, gimple stmt
)
120 gcc_assert (DECL_P (var
));
122 /* If our free list has an element, then use it. */
123 if (!VEC_empty (tree
, FREE_SSANAMES (fn
)))
125 t
= VEC_pop (tree
, FREE_SSANAMES (fn
));
126 if (GATHER_STATISTICS
)
127 ssa_name_nodes_reused
++;
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
);
132 VEC_replace (tree
, SSANAMES (fn
), SSA_NAME_VERSION (t
), t
);
136 t
= make_node (SSA_NAME
);
137 SSA_NAME_VERSION (t
) = VEC_length (tree
, SSANAMES (fn
));
138 VEC_safe_push (tree
, gc
, SSANAMES (fn
), t
);
139 if (GATHER_STATISTICS
)
140 ssa_name_nodes_created
++;
143 TREE_TYPE (t
) = TREE_TYPE (var
);
144 SSA_NAME_VAR (t
) = var
;
145 SSA_NAME_DEF_STMT (t
) = stmt
;
146 SSA_NAME_PTR_INFO (t
) = NULL
;
147 SSA_NAME_IN_FREE_LIST (t
) = 0;
148 SSA_NAME_IS_DEFAULT_DEF (t
) = 0;
149 imm
= &(SSA_NAME_IMM_USE_NODE (t
));
153 imm
->loc
.ssa_name
= t
;
159 /* We no longer need the SSA_NAME expression VAR, release it so that
162 Note it is assumed that no calls to make_ssa_name will be made
163 until all uses of the ssa name are released and that the only
164 use of the SSA_NAME expression is to check its SSA_NAME_VAR. All
165 other fields must be assumed clobbered. */
168 release_ssa_name (tree var
)
173 /* Never release the default definition for a symbol. It's a
174 special SSA name that should always exist once it's created. */
175 if (SSA_NAME_IS_DEFAULT_DEF (var
))
178 /* If VAR has been registered for SSA updating, don't remove it.
179 After update_ssa has run, the name will be released. */
180 if (name_registered_for_update_p (var
))
182 release_ssa_name_after_update_ssa (var
);
186 /* release_ssa_name can be called multiple times on a single SSA_NAME.
187 However, it should only end up on our free list one time. We
188 keep a status bit in the SSA_NAME node itself to indicate it has
189 been put on the free list.
191 Note that once on the freelist you can not reference the SSA_NAME's
192 defining statement. */
193 if (! SSA_NAME_IN_FREE_LIST (var
))
195 tree saved_ssa_name_var
= SSA_NAME_VAR (var
);
196 int saved_ssa_name_version
= SSA_NAME_VERSION (var
);
197 use_operand_p imm
= &(SSA_NAME_IMM_USE_NODE (var
));
199 if (MAY_HAVE_DEBUG_STMTS
)
200 insert_debug_temp_for_var_def (NULL
, var
);
202 #ifdef ENABLE_CHECKING
203 verify_imm_links (stderr
, var
);
205 while (imm
->next
!= imm
)
206 delink_imm_use (imm
->next
);
208 VEC_replace (tree
, SSANAMES (cfun
),
209 SSA_NAME_VERSION (var
), NULL_TREE
);
210 memset (var
, 0, tree_size (var
));
214 imm
->loc
.ssa_name
= var
;
216 /* First put back the right tree node so that the tree checking
217 macros do not complain. */
218 TREE_SET_CODE (var
, SSA_NAME
);
220 /* Restore the version number. */
221 SSA_NAME_VERSION (var
) = saved_ssa_name_version
;
223 /* Hopefully this can go away once we have the new incremental
224 SSA updating code installed. */
225 SSA_NAME_VAR (var
) = saved_ssa_name_var
;
227 /* Note this SSA_NAME is now in the first list. */
228 SSA_NAME_IN_FREE_LIST (var
) = 1;
230 /* And finally put it on the free list. */
231 VEC_safe_push (tree
, gc
, FREE_SSANAMES (cfun
), var
);
235 /* If the alignment of the pointer described by PI is known, return true and
236 store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
237 respectively. Otherwise return false. */
240 get_ptr_info_alignment (struct ptr_info_def
*pi
, unsigned int *alignp
,
241 unsigned int *misalignp
)
246 *misalignp
= pi
->misalign
;
253 /* State that the pointer described by PI has unknown alignment. */
256 mark_ptr_info_alignment_unknown (struct ptr_info_def
*pi
)
262 /* Store the the power-of-two byte alignment and the deviation from that
263 alignment of pointer described by PI to ALIOGN and MISALIGN
267 set_ptr_info_alignment (struct ptr_info_def
*pi
, unsigned int align
,
268 unsigned int misalign
)
270 gcc_checking_assert (align
!= 0);
271 gcc_assert ((align
& (align
- 1)) == 0);
272 gcc_assert ((misalign
& ~(align
- 1)) == 0);
275 pi
->misalign
= misalign
;
278 /* If pointer described by PI has known alignment, increase its known
279 misalignment by INCREMENT modulo its current alignment. */
282 adjust_ptr_info_misalignment (struct ptr_info_def
*pi
,
283 unsigned int increment
)
287 pi
->misalign
+= increment
;
288 pi
->misalign
&= (pi
->align
- 1);
292 /* Return the alias information associated with pointer T. It creates a
293 new instance if none existed. */
295 struct ptr_info_def
*
296 get_ptr_info (tree t
)
298 struct ptr_info_def
*pi
;
300 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t
)));
302 pi
= SSA_NAME_PTR_INFO (t
);
305 pi
= ggc_alloc_cleared_ptr_info_def ();
306 pt_solution_reset (&pi
->pt
);
307 mark_ptr_info_alignment_unknown (pi
);
308 SSA_NAME_PTR_INFO (t
) = pi
;
314 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
315 the SSA name NAME. */
318 duplicate_ssa_name_ptr_info (tree name
, struct ptr_info_def
*ptr_info
)
320 struct ptr_info_def
*new_ptr_info
;
322 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name
)));
323 gcc_assert (!SSA_NAME_PTR_INFO (name
));
328 new_ptr_info
= ggc_alloc_ptr_info_def ();
329 *new_ptr_info
= *ptr_info
;
331 SSA_NAME_PTR_INFO (name
) = new_ptr_info
;
335 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT. */
338 duplicate_ssa_name (tree name
, gimple stmt
)
340 tree new_name
= make_ssa_name (SSA_NAME_VAR (name
), stmt
);
341 struct ptr_info_def
*old_ptr_info
= SSA_NAME_PTR_INFO (name
);
344 duplicate_ssa_name_ptr_info (new_name
, old_ptr_info
);
350 /* Release all the SSA_NAMEs created by STMT. */
353 release_defs (gimple stmt
)
358 /* Make sure that we are in SSA. Otherwise, operand cache may point
360 gcc_assert (gimple_in_ssa_p (cfun
));
362 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_ALL_DEFS
)
363 if (TREE_CODE (def
) == SSA_NAME
)
364 release_ssa_name (def
);
368 /* Replace the symbol associated with SSA_NAME with SYM. */
371 replace_ssa_name_symbol (tree ssa_name
, tree sym
)
373 SSA_NAME_VAR (ssa_name
) = sym
;
374 TREE_TYPE (ssa_name
) = TREE_TYPE (sym
);
377 /* Return SSA names that are unused to GGC memory and compact the SSA
378 version namespace. This is used to keep footprint of compiler during
379 interprocedural optimization. */
381 release_dead_ssa_names (void)
385 int n
= VEC_length (tree
, FREE_SSANAMES (cfun
));
386 referenced_var_iterator rvi
;
388 /* Current defs point to various dead SSA names that in turn point to
389 eventually dead variables so a bunch of memory is held live. */
390 FOR_EACH_REFERENCED_VAR (cfun
, t
, rvi
)
391 set_current_def (t
, NULL
);
393 /* Now release the freelist. */
394 VEC_free (tree
, gc
, FREE_SSANAMES (cfun
));
395 FREE_SSANAMES (cfun
) = NULL
;
397 /* And compact the SSA number space. We make sure to not change the
398 relative order of SSA versions. */
399 for (i
= 1, j
= 1; i
< VEC_length (tree
, cfun
->gimple_df
->ssa_names
); ++i
)
401 tree name
= ssa_name (i
);
406 SSA_NAME_VERSION (name
) = j
;
407 VEC_replace (tree
, cfun
->gimple_df
->ssa_names
, j
, name
);
412 VEC_truncate (tree
, cfun
->gimple_df
->ssa_names
, j
);
414 statistics_counter_event (cfun
, "SSA names released", n
);
415 statistics_counter_event (cfun
, "SSA name holes removed", i
- j
);
417 fprintf (dump_file
, "Released %i names, %.2f%%, removed %i holes\n",
418 n
, n
* 100.0 / num_ssa_names
, i
- j
);
422 struct gimple_opt_pass pass_release_ssa_names
=
426 "release_ssa", /* name */
428 release_dead_ssa_names
, /* execute */
431 0, /* static_pass_number */
432 TV_TREE_SSA_OTHER
, /* tv_id */
433 PROP_ssa
, /* properties_required */
434 0, /* properties_provided */
435 0, /* properties_destroyed */
436 0, /* todo_flags_start */
437 0 /* todo_flags_finish */