Branch data Line data Source code
1 : : /* Generic routines for manipulating SSA_NAME expressions
2 : : Copyright (C) 2003-2024 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 3, 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 COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "backend.h"
24 : : #include "tree.h"
25 : : #include "gimple.h"
26 : : #include "tree-pass.h"
27 : : #include "ssa.h"
28 : : #include "gimple-iterator.h"
29 : : #include "stor-layout.h"
30 : : #include "tree-into-ssa.h"
31 : : #include "tree-ssa.h"
32 : : #include "cfgloop.h"
33 : : #include "tree-scalar-evolution.h"
34 : : #include "value-query.h"
35 : : #include "value-range-storage.h"
36 : :
37 : : /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
38 : : many of which may be thrown away shortly after their creation if jumps
39 : : were threaded through PHI nodes.
40 : :
41 : : While our garbage collection mechanisms will handle this situation, it
42 : : is extremely wasteful to create nodes and throw them away, especially
43 : : when the nodes can be reused.
44 : :
45 : : For PR 8361, we can significantly reduce the number of nodes allocated
46 : : and thus the total amount of memory allocated by managing SSA_NAMEs a
47 : : little. This additionally helps reduce the amount of work done by the
48 : : garbage collector. Similar results have been seen on a wider variety
49 : : of tests (such as the compiler itself).
50 : :
51 : : Right now we maintain our free list on a per-function basis. It may
52 : : or may not make sense to maintain the free list for the duration of
53 : : a compilation unit.
54 : :
55 : : External code should rely solely upon HIGHEST_SSA_VERSION and the
56 : : externally defined functions. External code should not know about
57 : : the details of the free list management.
58 : :
59 : : External code should also not assume the version number on nodes is
60 : : monotonically increasing. We reuse the version number when we
61 : : reuse an SSA_NAME expression. This helps keep arrays and bitmaps
62 : : more compact. */
63 : :
64 : :
65 : : /* Version numbers with special meanings. We start allocating new version
66 : : numbers after the special ones. */
67 : : #define UNUSED_NAME_VERSION 0
68 : :
69 : : unsigned int ssa_name_nodes_reused;
70 : : unsigned int ssa_name_nodes_created;
71 : :
72 : : #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
73 : : #define FREE_SSANAMES_QUEUE(fun) (fun)->gimple_df->free_ssanames_queue
74 : :
75 : : /* Return TRUE if NAME has global range info. */
76 : :
77 : : inline bool
78 : 606157296 : range_info_p (const_tree name)
79 : : {
80 : 606157296 : return SSA_NAME_RANGE_INFO (name);
81 : : }
82 : :
83 : : /* Return TRUE if R fits in the global range of NAME. */
84 : :
85 : : inline bool
86 : 2608501 : range_info_fits_p (tree name, const vrange &r)
87 : : {
88 : 2608501 : gcc_checking_assert (range_info_p (name));
89 : 2608501 : vrange_storage *mem = SSA_NAME_RANGE_INFO (name);
90 : 2608501 : return mem->fits_p (r);
91 : : }
92 : :
93 : : /* Allocate a new global range for NAME and set it to R. Return the
94 : : allocation slot. */
95 : :
96 : : inline void *
97 : 13675849 : range_info_alloc (tree name, const vrange &r)
98 : : {
99 : 13675849 : vrange_storage *mem = ggc_alloc_vrange_storage (r);
100 : 13675849 : SSA_NAME_RANGE_INFO (name) = mem;
101 : 13675849 : return mem;
102 : : }
103 : :
104 : : /* Free storage allocated for the global range for NAME. */
105 : :
106 : : inline void
107 : 591426 : range_info_free (tree name)
108 : : {
109 : 591426 : vrange_storage *mem = SSA_NAME_RANGE_INFO (name);
110 : 591426 : ggc_free (mem);
111 : 591426 : }
112 : :
113 : : /* Return the global range for NAME in R. */
114 : :
115 : : inline void
116 : 195787898 : range_info_get_range (const_tree name, vrange &r)
117 : : {
118 : 195787898 : SSA_NAME_RANGE_INFO (name)->get_vrange (r, TREE_TYPE (name));
119 : 195787898 : }
120 : :
121 : : /* Set the global range for NAME from R. Return TRUE if successfull,
122 : : or FALSE if we can't set a range of NAME's type. */
123 : :
124 : : inline bool
125 : 15692924 : range_info_set_range (tree name, const vrange &r)
126 : : {
127 : 15692924 : if (!range_info_p (name) || !range_info_fits_p (name, r))
128 : : {
129 : 13675849 : if (range_info_p (name))
130 : 591426 : range_info_free (name);
131 : :
132 : 13675849 : return range_info_alloc (name, r);
133 : : }
134 : : else
135 : : {
136 : 2017075 : SSA_NAME_RANGE_INFO (name)->set_vrange (r);
137 : 2017075 : return true;
138 : : }
139 : : }
140 : :
141 : : /* Initialize management of SSA_NAMEs to default SIZE. If SIZE is
142 : : zero use default. */
143 : :
144 : : void
145 : 2944191 : init_ssanames (struct function *fn, int size)
146 : : {
147 : 2944191 : if (!size)
148 : 2862399 : vec_alloc (SSANAMES (fn), 50);
149 : : else
150 : 81792 : vec_safe_reserve (SSANAMES (fn), size, true);
151 : :
152 : : /* Version 0 is special, so reserve the first slot in the table. Though
153 : : currently unused, we may use version 0 in alias analysis as part of
154 : : the heuristics used to group aliases when the alias sets are too
155 : : large.
156 : :
157 : : We use vec::quick_push here because we know that SSA_NAMES has at
158 : : least 50 elements reserved in it. */
159 : 2944191 : SSANAMES (fn)->quick_push (NULL_TREE);
160 : 2944191 : FREE_SSANAMES (fn) = NULL;
161 : 2944191 : FREE_SSANAMES_QUEUE (fn) = NULL;
162 : :
163 : 2944191 : fn->gimple_df->ssa_renaming_needed = 0;
164 : 2944191 : fn->gimple_df->rename_vops = 0;
165 : 2944191 : }
166 : :
167 : : /* Finalize management of SSA_NAMEs. */
168 : :
169 : : void
170 : 2839552 : fini_ssanames (struct function *fn)
171 : : {
172 : 2839552 : unsigned i;
173 : 2839552 : tree name;
174 : : /* Some SSA names leak into global tree data structures so we can't simply
175 : : ggc_free them. But make sure to clear references to stmts since we now
176 : : ggc_free the CFG itself. */
177 : 83407550 : FOR_EACH_VEC_SAFE_ELT (SSANAMES (fn), i, name)
178 : 80567998 : if (name)
179 : 58748127 : SSA_NAME_DEF_STMT (name) = NULL;
180 : 2839552 : vec_free (SSANAMES (fn));
181 : 2839552 : vec_free (FREE_SSANAMES (fn));
182 : 2839552 : vec_free (FREE_SSANAMES_QUEUE (fn));
183 : 2839552 : }
184 : :
185 : : /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */
186 : :
187 : : void
188 : 0 : ssanames_print_statistics (void)
189 : : {
190 : 0 : fprintf (stderr, "%-32s" PRsa (11) "\n", "SSA_NAME nodes allocated:",
191 : 0 : SIZE_AMOUNT (ssa_name_nodes_created));
192 : 0 : fprintf (stderr, "%-32s" PRsa (11) "\n", "SSA_NAME nodes reused:",
193 : 0 : SIZE_AMOUNT (ssa_name_nodes_reused));
194 : 0 : }
195 : :
196 : : /* Verify the state of the SSA_NAME lists.
197 : :
198 : : There must be no duplicates on the free list.
199 : : Every name on the free list must be marked as on the free list.
200 : : Any name on the free list must not appear in the IL.
201 : : No names can be leaked. */
202 : :
203 : : DEBUG_FUNCTION void
204 : 0 : verify_ssaname_freelists (struct function *fun)
205 : : {
206 : 0 : if (!gimple_in_ssa_p (fun))
207 : 0 : return;
208 : :
209 : 0 : auto_bitmap names_in_il;
210 : :
211 : : /* Walk the entire IL noting every SSA_NAME we see. */
212 : 0 : basic_block bb;
213 : 0 : FOR_EACH_BB_FN (bb, fun)
214 : : {
215 : 0 : tree t;
216 : : /* First note the result and arguments of PHI nodes. */
217 : 0 : for (gphi_iterator gsi = gsi_start_phis (bb);
218 : 0 : !gsi_end_p (gsi);
219 : 0 : gsi_next (&gsi))
220 : : {
221 : 0 : gphi *phi = gsi.phi ();
222 : 0 : t = gimple_phi_result (phi);
223 : 0 : bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
224 : :
225 : 0 : for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
226 : : {
227 : 0 : t = gimple_phi_arg_def (phi, i);
228 : 0 : if (TREE_CODE (t) == SSA_NAME)
229 : 0 : bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
230 : : }
231 : : }
232 : :
233 : : /* Then note the operands of each statement. */
234 : 0 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
235 : 0 : !gsi_end_p (gsi);
236 : 0 : gsi_next (&gsi))
237 : : {
238 : 0 : ssa_op_iter iter;
239 : 0 : gimple *stmt = gsi_stmt (gsi);
240 : 0 : FOR_EACH_SSA_TREE_OPERAND (t, stmt, iter, SSA_OP_ALL_OPERANDS)
241 : 0 : bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
242 : : }
243 : : }
244 : :
245 : : /* Now walk the free list noting what we find there and verifying
246 : : there are no duplicates. */
247 : 0 : auto_bitmap names_in_freelists;
248 : 0 : if (FREE_SSANAMES (fun))
249 : : {
250 : 0 : for (unsigned int i = 0; i < FREE_SSANAMES (fun)->length (); i++)
251 : : {
252 : 0 : tree t = (*FREE_SSANAMES (fun))[i];
253 : :
254 : : /* Verify that the name is marked as being in the free list. */
255 : 0 : gcc_assert (SSA_NAME_IN_FREE_LIST (t));
256 : :
257 : : /* Verify the name has not already appeared in the free list and
258 : : note it in the list of names found in the free list. */
259 : 0 : gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
260 : 0 : bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
261 : : }
262 : : }
263 : :
264 : : /* Similarly for the names in the pending free list. */
265 : 0 : if (FREE_SSANAMES_QUEUE (fun))
266 : : {
267 : 0 : for (unsigned int i = 0; i < FREE_SSANAMES_QUEUE (fun)->length (); i++)
268 : : {
269 : 0 : tree t = (*FREE_SSANAMES_QUEUE (fun))[i];
270 : :
271 : : /* Verify that the name is marked as being in the free list. */
272 : 0 : gcc_assert (SSA_NAME_IN_FREE_LIST (t));
273 : :
274 : : /* Verify the name has not already appeared in the free list and
275 : : note it in the list of names found in the free list. */
276 : 0 : gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
277 : 0 : bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
278 : : }
279 : : }
280 : :
281 : : /* If any name appears in both the IL and the freelists, then
282 : : something horrible has happened. */
283 : 0 : bool intersect_p = bitmap_intersect_p (names_in_il, names_in_freelists);
284 : 0 : gcc_assert (!intersect_p);
285 : :
286 : : /* Names can be queued up for release if there is an ssa update
287 : : pending. Pretend we saw them in the IL. */
288 : 0 : if (names_to_release)
289 : 0 : bitmap_ior_into (names_in_il, names_to_release);
290 : :
291 : : /* Function splitting can "lose" SSA_NAMEs in an effort to ensure that
292 : : debug/non-debug compilations have the same SSA_NAMEs. So for each
293 : : lost SSA_NAME, see if it's likely one from that wart. These will always
294 : : be marked as default definitions. So we loosely assume that anything
295 : : marked as a default definition isn't leaked by pretending they are
296 : : in the IL. */
297 : 0 : for (unsigned int i = UNUSED_NAME_VERSION + 1; i < num_ssa_names; i++)
298 : 0 : if (ssa_name (i) && SSA_NAME_IS_DEFAULT_DEF (ssa_name (i)))
299 : 0 : bitmap_set_bit (names_in_il, i);
300 : :
301 : 0 : unsigned int i;
302 : 0 : bitmap_iterator bi;
303 : 0 : auto_bitmap all_names;
304 : 0 : bitmap_set_range (all_names, UNUSED_NAME_VERSION + 1, num_ssa_names - 1);
305 : 0 : bitmap_ior_into (names_in_il, names_in_freelists);
306 : :
307 : : /* Any name not mentioned in the IL and not in the feelists
308 : : has been leaked. */
309 : 0 : EXECUTE_IF_AND_COMPL_IN_BITMAP(all_names, names_in_il,
310 : : UNUSED_NAME_VERSION + 1, i, bi)
311 : 0 : gcc_assert (!ssa_name (i));
312 : 0 : }
313 : :
314 : : /* Move all SSA_NAMEs from FREE_SSA_NAMES_QUEUE to FREE_SSA_NAMES.
315 : :
316 : : We do not, but should have a mode to verify the state of the SSA_NAMEs
317 : : lists. In particular at this point every name must be in the IL,
318 : : on the free list or in the queue. Anything else is an error. */
319 : :
320 : : void
321 : 566882703 : flush_ssaname_freelist (void)
322 : : {
323 : : /* If there were any SSA names released reset the SCEV cache. */
324 : 566882703 : if (! vec_safe_is_empty (FREE_SSANAMES_QUEUE (cfun)))
325 : 9413943 : scev_reset_htab ();
326 : 566882703 : vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun));
327 : 566882703 : vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun), 0);
328 : 566882703 : }
329 : :
330 : : /* Initialize SSA_NAME_IMM_USE_NODE of a SSA NAME. */
331 : :
332 : : void
333 : 130665220 : init_ssa_name_imm_use (tree name)
334 : : {
335 : 130665220 : use_operand_p imm;
336 : 130665220 : imm = &(SSA_NAME_IMM_USE_NODE (name));
337 : 130665220 : imm->use = NULL;
338 : 130665220 : imm->prev = imm;
339 : 130665220 : imm->next = imm;
340 : 130665220 : imm->loc.ssa_name = name;
341 : 130665220 : }
342 : :
343 : : /* Return an SSA_NAME node for variable VAR defined in statement STMT
344 : : in function FN. STMT may be an empty statement for artificial
345 : : references (e.g., default definitions created when a variable is
346 : : used without a preceding definition). If VERISON is not zero then
347 : : allocate the SSA name with that version. */
348 : :
349 : : tree
350 : 129168374 : make_ssa_name_fn (struct function *fn, tree var, gimple *stmt,
351 : : unsigned int version)
352 : : {
353 : 129168374 : tree t;
354 : 129168374 : gcc_assert (VAR_P (var)
355 : : || TREE_CODE (var) == PARM_DECL
356 : : || TREE_CODE (var) == RESULT_DECL
357 : : || (TYPE_P (var) && is_gimple_reg_type (var)));
358 : :
359 : : /* Get the specified SSA name version. */
360 : 129168374 : if (version != 0)
361 : : {
362 : 3555 : t = make_node (SSA_NAME);
363 : 3555 : SSA_NAME_VERSION (t) = version;
364 : 3555 : if (version >= SSANAMES (fn)->length ())
365 : 615 : vec_safe_grow_cleared (SSANAMES (fn), version + 1, true);
366 : 3555 : gcc_assert ((*SSANAMES (fn))[version] == NULL);
367 : 3555 : (*SSANAMES (fn))[version] = t;
368 : 3555 : ssa_name_nodes_created++;
369 : : }
370 : : /* If our free list has an element, then use it. */
371 : 129164819 : else if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
372 : : {
373 : 25482695 : t = FREE_SSANAMES (fn)->pop ();
374 : 25482695 : ssa_name_nodes_reused++;
375 : :
376 : : /* The node was cleared out when we put it on the free list, so
377 : : there is no need to do so again here. */
378 : 25482695 : gcc_assert ((*SSANAMES (fn))[SSA_NAME_VERSION (t)] == NULL);
379 : 25482695 : (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
380 : : }
381 : : else
382 : : {
383 : 103682124 : t = make_node (SSA_NAME);
384 : 103682124 : SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
385 : 103682124 : vec_safe_push (SSANAMES (fn), t);
386 : 103682124 : ssa_name_nodes_created++;
387 : : }
388 : :
389 : 129168374 : if (TYPE_P (var))
390 : : {
391 : 48219954 : TREE_TYPE (t) = TYPE_MAIN_VARIANT (var);
392 : 48219954 : SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
393 : : }
394 : : else
395 : : {
396 : 80948420 : TREE_TYPE (t) = TREE_TYPE (var);
397 : 119710697 : SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
398 : : }
399 : 129168374 : SSA_NAME_DEF_STMT (t) = stmt;
400 : 129168374 : if (POINTER_TYPE_P (TREE_TYPE (t)))
401 : 26121159 : SSA_NAME_PTR_INFO (t) = NULL;
402 : : else
403 : 103047215 : SSA_NAME_RANGE_INFO (t) = NULL;
404 : :
405 : 129168374 : SSA_NAME_IN_FREE_LIST (t) = 0;
406 : 129168374 : SSA_NAME_IS_DEFAULT_DEF (t) = 0;
407 : 129168374 : init_ssa_name_imm_use (t);
408 : :
409 : 129168374 : return t;
410 : : }
411 : :
412 : : /* Update the range information for NAME, intersecting into an existing
413 : : range if applicable. Return TRUE if the range was updated. */
414 : :
415 : : bool
416 : 37060483 : set_range_info (tree name, const vrange &r)
417 : : {
418 : 37060483 : if (r.undefined_p () || r.varying_p ())
419 : : return false;
420 : :
421 : : // Pick up the current range, or VARYING if none.
422 : 36925886 : tree type = TREE_TYPE (name);
423 : 36925886 : if (POINTER_TYPE_P (type))
424 : : {
425 : 5421333 : struct ptr_info_def *pi = get_ptr_info (name);
426 : : // If R is nonnull and pi is not, set nonnull.
427 : 5421333 : if (r.nonzero_p () && (!pi || pi->pt.null))
428 : : {
429 : 2039614 : set_ptr_nonnull (name);
430 : 2039614 : return true;
431 : : }
432 : : return false;
433 : : }
434 : :
435 : 31504553 : Value_Range tmp (type);
436 : 31504553 : if (range_info_p (name))
437 : 24576992 : range_info_get_range (name, tmp);
438 : : else
439 : 6927561 : tmp.set_varying (type);
440 : : // If the result doesn't change, or is undefined, return false.
441 : 31504553 : if (!tmp.intersect (r) || tmp.undefined_p ())
442 : : return false;
443 : :
444 : 9536062 : return range_info_set_range (name, tmp);
445 : 31504553 : }
446 : :
447 : : /* Set nonnull attribute to pointer NAME. */
448 : :
449 : : void
450 : 5028056 : set_ptr_nonnull (tree name)
451 : : {
452 : 5028056 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
453 : 5028056 : struct ptr_info_def *pi = get_ptr_info (name);
454 : 5028056 : pi->pt.null = 0;
455 : 5028056 : }
456 : :
457 : : /* Update the non-zero bits bitmask of NAME. */
458 : :
459 : : void
460 : 0 : set_nonzero_bits (tree name, const wide_int &mask)
461 : : {
462 : 0 : gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
463 : :
464 : 0 : int_range<2> r (TREE_TYPE (name));
465 : 0 : r.set_nonzero_bits (mask);
466 : 0 : set_range_info (name, r);
467 : 0 : }
468 : :
469 : : /* Update the known bits of NAME.
470 : :
471 : : Zero bits in MASK cover constant values. Set bits in MASK cover
472 : : unknown values. VALUE are the known bits. */
473 : :
474 : : void
475 : 11383172 : set_bitmask (tree name, const wide_int &value, const wide_int &mask)
476 : : {
477 : 11383172 : gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
478 : :
479 : 11383172 : int_range<2> r (TREE_TYPE (name));
480 : 11383172 : r.update_bitmask (irange_bitmask (value, mask));
481 : 11383172 : set_range_info (name, r);
482 : 11383172 : }
483 : :
484 : : /* Return a widest_int with potentially non-zero bits in SSA_NAME
485 : : NAME, the constant for INTEGER_CST, or -1 if unknown. */
486 : :
487 : : wide_int
488 : 572676595 : get_nonzero_bits (const_tree name)
489 : : {
490 : 572676595 : if (TREE_CODE (name) == INTEGER_CST)
491 : 757081 : return wi::to_wide (name);
492 : :
493 : : /* Use element_precision instead of TYPE_PRECISION so complex and
494 : : vector types get a non-zero precision. */
495 : 571919514 : unsigned int precision = element_precision (TREE_TYPE (name));
496 : 571919514 : if (POINTER_TYPE_P (TREE_TYPE (name)))
497 : : {
498 : 53885577 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
499 : 53885577 : if (pi && pi->align)
500 : 2857758 : return wi::shwi (-(HOST_WIDE_INT) pi->align
501 : 5715516 : | (HOST_WIDE_INT) pi->misalign, precision);
502 : 51027819 : return wi::shwi (-1, precision);
503 : : }
504 : :
505 : 518033937 : if (!range_info_p (name) || !irange::supports_p (TREE_TYPE (name)))
506 : 352979893 : return wi::shwi (-1, precision);
507 : :
508 : 165054044 : int_range_max tmp;
509 : 165054044 : range_info_get_range (name, tmp);
510 : 165054044 : return tmp.get_nonzero_bits ();
511 : 165054044 : }
512 : :
513 : : /* Return TRUE is OP, an SSA_NAME has a range of values [0..1], false
514 : : otherwise.
515 : :
516 : : This can be because it is a boolean type, any unsigned integral
517 : : type with a single bit of precision, or has known range of [0..1]
518 : : via range analysis. */
519 : :
520 : : bool
521 : 23967996 : ssa_name_has_boolean_range (tree op)
522 : : {
523 : 23967996 : gcc_assert (TREE_CODE (op) == SSA_NAME);
524 : :
525 : : /* An integral type with a single bit of precision. */
526 : 47424789 : if (INTEGRAL_TYPE_P (TREE_TYPE (op))
527 : 18896220 : && TYPE_UNSIGNED (TREE_TYPE (op))
528 : 34574388 : && TYPE_PRECISION (TREE_TYPE (op)) == 1)
529 : : return true;
530 : :
531 : : /* An integral type with more precision, but the object
532 : : only takes on values [0..1] as determined by range
533 : : analysis. */
534 : 40934227 : if (INTEGRAL_TYPE_P (TREE_TYPE (op))
535 : 35862451 : && (TYPE_PRECISION (TREE_TYPE (op)) > 1))
536 : : {
537 : 15649952 : int_range<2> r;
538 : 31299904 : if (get_range_query (cfun)->range_of_expr (r, op)
539 : 15649952 : && r == range_true_and_false (TREE_TYPE (op)))
540 : : return true;
541 : :
542 : 15170901 : if (wi::eq_p (get_nonzero_bits (op), 1))
543 : : return true;
544 : 15649952 : }
545 : :
546 : : return false;
547 : : }
548 : :
549 : : /* We no longer need the SSA_NAME expression VAR, release it so that
550 : : it may be reused.
551 : :
552 : : Note it is assumed that no calls to make_ssa_name will be made
553 : : until all uses of the ssa name are released and that the only
554 : : use of the SSA_NAME expression is to check its SSA_NAME_VAR. All
555 : : other fields must be assumed clobbered. */
556 : :
557 : : void
558 : 70354307 : release_ssa_name_fn (struct function *fn, tree var)
559 : : {
560 : 70354307 : if (!var)
561 : : return;
562 : :
563 : : /* Never release the default definition for a symbol. It's a
564 : : special SSA name that should always exist once it's created. */
565 : 70354307 : if (SSA_NAME_IS_DEFAULT_DEF (var))
566 : : return;
567 : :
568 : : /* If VAR has been registered for SSA updating, don't remove it.
569 : : After update_ssa has run, the name will be released. */
570 : 70354307 : if (name_registered_for_update_p (var))
571 : : {
572 : 612092 : release_ssa_name_after_update_ssa (var);
573 : 612092 : return;
574 : : }
575 : :
576 : : /* release_ssa_name can be called multiple times on a single SSA_NAME.
577 : : However, it should only end up on our free list one time. We
578 : : keep a status bit in the SSA_NAME node itself to indicate it has
579 : : been put on the free list.
580 : :
581 : : Note that once on the freelist you cannot reference the SSA_NAME's
582 : : defining statement. */
583 : 69742215 : if (! SSA_NAME_IN_FREE_LIST (var))
584 : : {
585 : 69742215 : int saved_ssa_name_version = SSA_NAME_VERSION (var);
586 : 69742215 : use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
587 : :
588 : 69742215 : if (MAY_HAVE_DEBUG_BIND_STMTS)
589 : 45770469 : insert_debug_temp_for_var_def (NULL, var);
590 : :
591 : 69742215 : if (flag_checking)
592 : 69741623 : verify_imm_links (stderr, var);
593 : 78064042 : while (imm->next != imm)
594 : 78064042 : delink_imm_use (imm->next);
595 : :
596 : 69742215 : (*SSANAMES (fn))[SSA_NAME_VERSION (var)] = NULL_TREE;
597 : 69742215 : memset (var, 0, tree_size (var));
598 : :
599 : 69742215 : imm->prev = imm;
600 : 69742215 : imm->next = imm;
601 : 69742215 : imm->loc.ssa_name = var;
602 : :
603 : : /* First put back the right tree node so that the tree checking
604 : : macros do not complain. */
605 : 69742215 : TREE_SET_CODE (var, SSA_NAME);
606 : :
607 : : /* Restore the version number. */
608 : 69742215 : SSA_NAME_VERSION (var) = saved_ssa_name_version;
609 : :
610 : : /* Note this SSA_NAME is now in the first list. */
611 : 69742215 : SSA_NAME_IN_FREE_LIST (var) = 1;
612 : :
613 : : /* Put in a non-NULL TREE_TYPE so dumping code will not ICE
614 : : if it happens to come along a released SSA name and tries
615 : : to inspect its type. */
616 : 69742215 : TREE_TYPE (var) = error_mark_node;
617 : :
618 : : /* And finally queue it so that it will be put on the free list. */
619 : 69742215 : vec_safe_push (FREE_SSANAMES_QUEUE (fn), var);
620 : : }
621 : : }
622 : :
623 : : /* If the alignment of the pointer described by PI is known, return true and
624 : : store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
625 : : respectively. Otherwise return false. */
626 : :
627 : : bool
628 : 40742938 : get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
629 : : unsigned int *misalignp)
630 : : {
631 : 40742938 : if (pi->align)
632 : : {
633 : 4254682 : *alignp = pi->align;
634 : 4254682 : *misalignp = pi->misalign;
635 : 4254682 : return true;
636 : : }
637 : : else
638 : : return false;
639 : : }
640 : :
641 : : /* State that the pointer described by PI has unknown alignment. */
642 : :
643 : : void
644 : 13588406 : mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
645 : : {
646 : 13588406 : pi->align = 0;
647 : 13588406 : pi->misalign = 0;
648 : 13588406 : }
649 : :
650 : : /* Store the power-of-two byte alignment and the deviation from that
651 : : alignment of pointer described by PI to ALIOGN and MISALIGN
652 : : respectively. */
653 : :
654 : : void
655 : 1402104 : set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
656 : : unsigned int misalign)
657 : : {
658 : 1402104 : gcc_checking_assert (align != 0);
659 : 1402104 : gcc_assert ((align & (align - 1)) == 0);
660 : 1402104 : gcc_assert ((misalign & ~(align - 1)) == 0);
661 : :
662 : 1402104 : pi->align = align;
663 : 1402104 : pi->misalign = misalign;
664 : 1402104 : }
665 : :
666 : : /* If pointer described by PI has known alignment, increase its known
667 : : misalignment by INCREMENT modulo its current alignment. */
668 : :
669 : : void
670 : 0 : adjust_ptr_info_misalignment (struct ptr_info_def *pi, poly_uint64 increment)
671 : : {
672 : 0 : if (pi->align != 0)
673 : : {
674 : 0 : increment += pi->misalign;
675 : 0 : if (!known_misalignment (increment, pi->align, &pi->misalign))
676 : : {
677 : 0 : pi->align = known_alignment (increment);
678 : 0 : pi->misalign = 0;
679 : : }
680 : : }
681 : 0 : }
682 : :
683 : : /* Return the alias information associated with pointer T. It creates a
684 : : new instance if none existed. */
685 : :
686 : : struct ptr_info_def *
687 : 32596039 : get_ptr_info (tree t)
688 : : {
689 : 32596039 : struct ptr_info_def *pi;
690 : :
691 : 32596039 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
692 : :
693 : 32596039 : pi = SSA_NAME_PTR_INFO (t);
694 : 32596039 : if (pi == NULL)
695 : : {
696 : 12964403 : pi = ggc_cleared_alloc<ptr_info_def> ();
697 : 12964403 : pt_solution_reset (&pi->pt);
698 : 12964403 : mark_ptr_info_alignment_unknown (pi);
699 : 12964403 : SSA_NAME_PTR_INFO (t) = pi;
700 : : }
701 : :
702 : 32596039 : return pi;
703 : : }
704 : :
705 : :
706 : : /* Creates a new SSA name using the template NAME tobe defined by
707 : : statement STMT in function FN. */
708 : :
709 : : tree
710 : 15680879 : copy_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
711 : : {
712 : 15680879 : tree new_name;
713 : :
714 : 15680879 : if (SSA_NAME_VAR (name))
715 : 10410789 : new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
716 : : else
717 : : {
718 : 5270090 : new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
719 : 10540180 : SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
720 : : }
721 : :
722 : 15680879 : return new_name;
723 : : }
724 : :
725 : :
726 : : /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
727 : : the SSA name NAME. */
728 : :
729 : : void
730 : 2462153 : duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
731 : : {
732 : 2462153 : struct ptr_info_def *new_ptr_info;
733 : :
734 : 2462153 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
735 : 2462153 : gcc_assert (!SSA_NAME_PTR_INFO (name));
736 : :
737 : 2462153 : if (!ptr_info)
738 : : return;
739 : :
740 : 2462097 : new_ptr_info = ggc_alloc<ptr_info_def> ();
741 : 2462097 : *new_ptr_info = *ptr_info;
742 : :
743 : 2462097 : SSA_NAME_PTR_INFO (name) = new_ptr_info;
744 : : }
745 : :
746 : : void
747 : 6156862 : duplicate_ssa_name_range_info (tree name, tree src)
748 : : {
749 : 6156862 : gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (src)));
750 : 6156862 : gcc_checking_assert (!range_info_p (name));
751 : :
752 : 6156862 : if (range_info_p (src))
753 : : {
754 : 6156862 : Value_Range src_range (TREE_TYPE (src));
755 : 6156862 : range_info_get_range (src, src_range);
756 : 6156862 : range_info_set_range (name, src_range);
757 : 6156862 : }
758 : 6156862 : }
759 : :
760 : :
761 : : /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
762 : : in function FN. */
763 : :
764 : : tree
765 : 14033055 : duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
766 : : {
767 : 14033055 : tree new_name = copy_ssa_name_fn (fn, name, stmt);
768 : 14033055 : if (POINTER_TYPE_P (TREE_TYPE (name)))
769 : : {
770 : 1705247 : struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
771 : :
772 : 1705247 : if (old_ptr_info)
773 : 1509869 : duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
774 : : }
775 : 12327808 : else if (range_info_p (name))
776 : 3024581 : duplicate_ssa_name_range_info (new_name, name);
777 : :
778 : 14033055 : return new_name;
779 : : }
780 : :
781 : :
782 : : /* Reset all flow sensitive data on NAME such as range-info, nonzero
783 : : bits and alignment. */
784 : :
785 : : void
786 : 1112173 : reset_flow_sensitive_info (tree name)
787 : : {
788 : 1112173 : if (POINTER_TYPE_P (TREE_TYPE (name)))
789 : : {
790 : : /* points-to info is not flow-sensitive. */
791 : 345369 : if (SSA_NAME_PTR_INFO (name))
792 : : {
793 : : /* [E]VRP can derive context sensitive alignment info and
794 : : non-nullness properties. We must reset both. */
795 : 341740 : mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
796 : 341740 : SSA_NAME_PTR_INFO (name)->pt.null = 1;
797 : : }
798 : : }
799 : : else
800 : 766804 : SSA_NAME_RANGE_INFO (name) = NULL;
801 : 1112173 : }
802 : :
803 : : /* Clear all flow sensitive data from all statements and PHI definitions
804 : : in BB. */
805 : :
806 : : void
807 : 1125561 : reset_flow_sensitive_info_in_bb (basic_block bb)
808 : : {
809 : 3279946 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
810 : 1028824 : gsi_next (&gsi))
811 : : {
812 : 1028824 : gimple *stmt = gsi_stmt (gsi);
813 : 1028824 : ssa_op_iter i;
814 : 1028824 : tree op;
815 : 1240492 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
816 : 211668 : reset_flow_sensitive_info (op);
817 : : }
818 : :
819 : 1144061 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
820 : 18500 : gsi_next (&gsi))
821 : : {
822 : 18500 : tree phi_def = gimple_phi_result (gsi.phi ());
823 : 18500 : reset_flow_sensitive_info (phi_def);
824 : : }
825 : 1125561 : }
826 : :
827 : : /* Release all the SSA_NAMEs created by STMT. */
828 : :
829 : : void
830 : 57747653 : release_defs (gimple *stmt)
831 : : {
832 : 57747653 : tree def;
833 : 57747653 : ssa_op_iter iter;
834 : :
835 : 101307525 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
836 : 43559872 : if (TREE_CODE (def) == SSA_NAME)
837 : 43068914 : release_ssa_name (def);
838 : 57747653 : }
839 : :
840 : :
841 : : /* Replace the symbol associated with SSA_NAME with SYM. */
842 : :
843 : : void
844 : 12488 : replace_ssa_name_symbol (tree ssa_name, tree sym)
845 : : {
846 : 12488 : SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
847 : 12488 : TREE_TYPE (ssa_name) = TREE_TYPE (sym);
848 : 12488 : }
849 : :
850 : : /* Release the vector of free SSA_NAMEs and compact the vector of SSA_NAMEs
851 : : that are live. */
852 : :
853 : : static void
854 : 2580401 : release_free_names_and_compact_live_names (function *fun)
855 : : {
856 : 2580401 : unsigned i, j;
857 : 2580401 : int n = vec_safe_length (FREE_SSANAMES (fun));
858 : :
859 : : /* Now release the freelist. */
860 : 2580401 : vec_free (FREE_SSANAMES (fun));
861 : :
862 : : /* And compact the SSA number space. We make sure to not change the
863 : : relative order of SSA versions. */
864 : 74447480 : for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
865 : : {
866 : 71867079 : tree name = ssa_name (i);
867 : 71867079 : if (name)
868 : : {
869 : 46416187 : if (i != j)
870 : : {
871 : 28307218 : SSA_NAME_VERSION (name) = j;
872 : 28307218 : (*fun->gimple_df->ssa_names)[j] = name;
873 : : }
874 : 46416187 : j++;
875 : : }
876 : : }
877 : 2580401 : fun->gimple_df->ssa_names->truncate (j);
878 : :
879 : 2580401 : statistics_counter_event (fun, "SSA names released", n);
880 : 2580401 : statistics_counter_event (fun, "SSA name holes removed", i - j);
881 : 2580401 : if (dump_file)
882 : 282 : fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
883 : 282 : n, n * 100.0 / num_ssa_names, i - j);
884 : 2580401 : }
885 : :
886 : : /* Return SSA names that are unused to GGC memory and compact the SSA
887 : : version namespace. This is used to keep footprint of compiler during
888 : : interprocedural optimization. */
889 : :
890 : : namespace {
891 : :
892 : : const pass_data pass_data_release_ssa_names =
893 : : {
894 : : GIMPLE_PASS, /* type */
895 : : "release_ssa", /* name */
896 : : OPTGROUP_NONE, /* optinfo_flags */
897 : : TV_TREE_SSA_OTHER, /* tv_id */
898 : : PROP_ssa, /* properties_required */
899 : : 0, /* properties_provided */
900 : : 0, /* properties_destroyed */
901 : : TODO_remove_unused_locals, /* todo_flags_start */
902 : : 0, /* todo_flags_finish */
903 : : };
904 : :
905 : : class pass_release_ssa_names : public gimple_opt_pass
906 : : {
907 : : public:
908 : 280455 : pass_release_ssa_names (gcc::context *ctxt)
909 : 560910 : : gimple_opt_pass (pass_data_release_ssa_names, ctxt)
910 : : {}
911 : :
912 : : /* opt_pass methods: */
913 : : unsigned int execute (function *) final override;
914 : :
915 : : }; // class pass_release_ssa_names
916 : :
917 : : unsigned int
918 : 2580401 : pass_release_ssa_names::execute (function *fun)
919 : : {
920 : 2580401 : release_free_names_and_compact_live_names (fun);
921 : 2580401 : return 0;
922 : : }
923 : :
924 : : } // anon namespace
925 : :
926 : : gimple_opt_pass *
927 : 280455 : make_pass_release_ssa_names (gcc::context *ctxt)
928 : : {
929 : 280455 : return new pass_release_ssa_names (ctxt);
930 : : }
931 : :
932 : : /* Save and restore of flow sensitive information. */
933 : :
934 : : /* Save off the flow sensitive info from NAME. */
935 : :
936 : : void
937 : 334866 : flow_sensitive_info_storage::save (tree name)
938 : : {
939 : 334866 : gcc_assert (state == 0);
940 : 334866 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
941 : : {
942 : 322976 : range_info = SSA_NAME_RANGE_INFO (name);
943 : 322976 : state = 1;
944 : 322976 : return;
945 : : }
946 : 11890 : state = -1;
947 : 11890 : auto ptr_info = SSA_NAME_PTR_INFO (name);
948 : 11890 : if (ptr_info)
949 : : {
950 : 11262 : align = ptr_info->align;
951 : 11262 : misalign = ptr_info->misalign;
952 : 11262 : null = SSA_NAME_PTR_INFO (name)->pt.null;
953 : : }
954 : : else
955 : : {
956 : 628 : align = 0;
957 : 628 : misalign = 0;
958 : 628 : null = true;
959 : : }
960 : : }
961 : :
962 : : /* Restore the flow sensitive info from NAME. */
963 : :
964 : : void
965 : 334866 : flow_sensitive_info_storage::restore (tree name)
966 : : {
967 : 334866 : gcc_assert (state != 0);
968 : 334866 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
969 : : {
970 : 322976 : gcc_assert (state == 1);
971 : 322976 : SSA_NAME_RANGE_INFO (name) = range_info;
972 : 322976 : return;
973 : : }
974 : 11890 : gcc_assert (state == -1);
975 : 11890 : auto ptr_info = SSA_NAME_PTR_INFO (name);
976 : : /* If there was no flow sensitive info on the pointer
977 : : just return, there is nothing to restore to. */
978 : 11890 : if (!ptr_info)
979 : : return;
980 : 11262 : if (align != 0)
981 : 336 : set_ptr_info_alignment (ptr_info, align, misalign);
982 : : else
983 : 10926 : mark_ptr_info_alignment_unknown (ptr_info);
984 : 11262 : SSA_NAME_PTR_INFO (name)->pt.null = null;
985 : : }
986 : :
987 : : /* Save off the flow sensitive info from NAME.
988 : : And reset the flow sensitive info of NAME. */
989 : :
990 : : void
991 : 334866 : flow_sensitive_info_storage::save_and_clear (tree name)
992 : : {
993 : 334866 : save (name);
994 : 334866 : reset_flow_sensitive_info (name);
995 : 334866 : }
996 : :
997 : : /* Clear the storage. */
998 : : void
999 : 0 : flow_sensitive_info_storage::clear_storage (void)
1000 : : {
1001 : 0 : state = 0;
1002 : 0 : }
|