]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/tree-ssanames.c
tree-ssa.h: New.
[thirdparty/gcc.git] / gcc / tree-ssanames.c
CommitLineData
6de9cd9a 1/* Generic routines for manipulating SSA_NAME expressions
d1e082c2 2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
7072a650 3
6de9cd9a 4This file is part of GCC.
b8698a0f 5
6de9cd9a
DN
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
9dcd6f09 8the Free Software Foundation; either version 3, or (at your option)
6de9cd9a 9any later version.
b8698a0f 10
6de9cd9a
DN
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
b8698a0f 15
6de9cd9a 16You should have received a copy of the GNU General Public License
9dcd6f09
NC
17along 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
60unsigned int ssa_name_nodes_reused;
61unsigned 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
66void
5db9ba0c 67init_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
90void
91fini_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
99void
100ssanames_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
111tree
726a989a 112make_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
175void
176release_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
246bool
247get_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
262void
263mark_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
273void
274set_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
288void
289adjust_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
302struct ptr_info_def *
303get_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
325tree
326copy_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
345void
346duplicate_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
366tree
070ecdfd 367duplicate_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
381void
726a989a 382release_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
399void
400replace_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
409static unsigned int
410release_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
443namespace {
444
445const 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
460class pass_release_ssa_names : public gimple_opt_pass
461{
462public:
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
474gimple_opt_pass *
475make_pass_release_ssa_names (gcc::context *ctxt)
476{
477 return new pass_release_ssa_names (ctxt);
478}