Line data Source code
1 : /* Generic routines for manipulating SSA_NAME expressions
2 : Copyright (C) 2003-2026 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-pretty-print.h"
29 : #include "gimple-iterator.h"
30 : #include "stor-layout.h"
31 : #include "tree-into-ssa.h"
32 : #include "tree-ssa.h"
33 : #include "cfgloop.h"
34 : #include "tree-scalar-evolution.h"
35 : #include "value-query.h"
36 : #include "value-range-storage.h"
37 :
38 : /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
39 : many of which may be thrown away shortly after their creation if jumps
40 : were threaded through PHI nodes.
41 :
42 : While our garbage collection mechanisms will handle this situation, it
43 : is extremely wasteful to create nodes and throw them away, especially
44 : when the nodes can be reused.
45 :
46 : For PR 8361, we can significantly reduce the number of nodes allocated
47 : and thus the total amount of memory allocated by managing SSA_NAMEs a
48 : little. This additionally helps reduce the amount of work done by the
49 : garbage collector. Similar results have been seen on a wider variety
50 : of tests (such as the compiler itself).
51 :
52 : Right now we maintain our free list on a per-function basis. It may
53 : or may not make sense to maintain the free list for the duration of
54 : a compilation unit.
55 :
56 : External code should rely solely upon HIGHEST_SSA_VERSION and the
57 : externally defined functions. External code should not know about
58 : the details of the free list management.
59 :
60 : External code should also not assume the version number on nodes is
61 : monotonically increasing. We reuse the version number when we
62 : reuse an SSA_NAME expression. This helps keep arrays and bitmaps
63 : more compact. */
64 :
65 :
66 : /* Version numbers with special meanings. We start allocating new version
67 : numbers after the special ones. */
68 : #define UNUSED_NAME_VERSION 0
69 :
70 : unsigned int ssa_name_nodes_reused;
71 : unsigned int ssa_name_nodes_created;
72 :
73 : #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames
74 : #define FREE_SSANAMES_QUEUE(fun) (fun)->gimple_df->free_ssanames_queue
75 :
76 : /* Return TRUE if NAME has global range info. */
77 :
78 : inline bool
79 1020962925 : range_info_p (const_tree name)
80 : {
81 1020962925 : return SSA_NAME_RANGE_INFO (name);
82 : }
83 :
84 : /* Return TRUE if R fits in the global range of NAME. */
85 :
86 : inline bool
87 4207830 : range_info_fits_p (tree name, const vrange &r)
88 : {
89 4207830 : gcc_checking_assert (range_info_p (name));
90 4207830 : vrange_storage *mem = SSA_NAME_RANGE_INFO (name);
91 4207830 : return mem->fits_p (r);
92 : }
93 :
94 : /* Allocate a new global range for NAME and set it to R. Return the
95 : allocation slot. */
96 :
97 : inline void *
98 17597709 : range_info_alloc (tree name, const vrange &r)
99 : {
100 17597709 : vrange_storage *mem = ggc_alloc_vrange_storage (r);
101 17597709 : SSA_NAME_RANGE_INFO (name) = mem;
102 17597709 : return mem;
103 : }
104 :
105 : /* Free storage allocated for the global range for NAME. */
106 :
107 : inline void
108 562253 : range_info_free (tree name)
109 : {
110 562253 : vrange_storage *mem = SSA_NAME_RANGE_INFO (name);
111 562253 : ggc_free (mem);
112 562253 : }
113 :
114 : /* Return the global range for NAME in R. */
115 :
116 : inline void
117 313552503 : range_info_get_range (const_tree name, vrange &r)
118 : {
119 313552503 : SSA_NAME_RANGE_INFO (name)->get_vrange (r, TREE_TYPE (name));
120 313552503 : }
121 :
122 : /* Set the global range for NAME from R. Return TRUE if successful,
123 : or FALSE if we can't set a range of NAME's type. */
124 :
125 : inline bool
126 21243286 : range_info_set_range (tree name, const vrange &r)
127 : {
128 21243286 : if (!range_info_p (name) || !range_info_fits_p (name, r))
129 : {
130 17597709 : if (range_info_p (name))
131 562253 : range_info_free (name);
132 :
133 17597709 : return range_info_alloc (name, r);
134 : }
135 : else
136 : {
137 3645577 : SSA_NAME_RANGE_INFO (name)->set_vrange (r);
138 3645577 : return true;
139 : }
140 : }
141 :
142 : /* Initialize management of SSA_NAMEs to default SIZE. If SIZE is
143 : zero use default. */
144 :
145 : void
146 3441589 : init_ssanames (struct function *fn, int size)
147 : {
148 3441589 : if (!size)
149 3357401 : vec_alloc (SSANAMES (fn), 50);
150 : else
151 84188 : vec_safe_reserve (SSANAMES (fn), size, true);
152 :
153 : /* Version 0 is special, so reserve the first slot in the table. Though
154 : currently unused, we may use version 0 in alias analysis as part of
155 : the heuristics used to group aliases when the alias sets are too
156 : large.
157 :
158 : We use vec::quick_push here because we know that SSA_NAMES has at
159 : least 50 elements reserved in it. */
160 3441589 : SSANAMES (fn)->quick_push (NULL_TREE);
161 3441589 : FREE_SSANAMES (fn) = NULL;
162 3441589 : FREE_SSANAMES_QUEUE (fn) = NULL;
163 :
164 3441589 : fn->gimple_df->ssa_renaming_needed = 0;
165 3441589 : fn->gimple_df->rename_vops = 0;
166 3441589 : }
167 :
168 : /* Finalize management of SSA_NAMEs. */
169 :
170 : void
171 3332764 : fini_ssanames (struct function *fn)
172 : {
173 3332764 : unsigned i;
174 3332764 : tree name;
175 : /* Some SSA names leak into global tree data structures so we can't simply
176 : ggc_free them. But make sure to clear references to stmts since we now
177 : ggc_free the CFG itself. */
178 98607705 : FOR_EACH_VEC_SAFE_ELT (SSANAMES (fn), i, name)
179 95274941 : if (name)
180 68216083 : SSA_NAME_DEF_STMT (name) = NULL;
181 3332764 : vec_free (SSANAMES (fn));
182 3332764 : vec_free (FREE_SSANAMES (fn));
183 3332764 : vec_free (FREE_SSANAMES_QUEUE (fn));
184 3332764 : }
185 :
186 : /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */
187 :
188 : void
189 0 : ssanames_print_statistics (void)
190 : {
191 0 : fprintf (stderr, "%-32s" PRsa (11) "\n", "SSA_NAME nodes allocated:",
192 0 : SIZE_AMOUNT (ssa_name_nodes_created));
193 0 : fprintf (stderr, "%-32s" PRsa (11) "\n", "SSA_NAME nodes reused:",
194 0 : SIZE_AMOUNT (ssa_name_nodes_reused));
195 0 : }
196 :
197 : /* Verify the state of the SSA_NAME lists.
198 :
199 : There must be no duplicates on the free list.
200 : Every name on the free list must be marked as on the free list.
201 : Any name on the free list must not appear in the IL.
202 : No names can be leaked. */
203 :
204 : DEBUG_FUNCTION void
205 0 : verify_ssaname_freelists (struct function *fun)
206 : {
207 0 : if (!gimple_in_ssa_p (fun))
208 0 : return;
209 :
210 0 : auto_bitmap names_in_il;
211 :
212 : /* Walk the entire IL noting every SSA_NAME we see. */
213 0 : basic_block bb;
214 0 : FOR_EACH_BB_FN (bb, fun)
215 : {
216 0 : tree t;
217 : /* First note the result and arguments of PHI nodes. */
218 0 : for (gphi_iterator gsi = gsi_start_phis (bb);
219 0 : !gsi_end_p (gsi);
220 0 : gsi_next (&gsi))
221 : {
222 0 : gphi *phi = gsi.phi ();
223 0 : t = gimple_phi_result (phi);
224 0 : bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
225 :
226 0 : for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
227 : {
228 0 : t = gimple_phi_arg_def (phi, i);
229 0 : if (TREE_CODE (t) == SSA_NAME)
230 0 : bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
231 : }
232 : }
233 :
234 : /* Then note the operands of each statement. */
235 0 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
236 0 : !gsi_end_p (gsi);
237 0 : gsi_next (&gsi))
238 : {
239 0 : ssa_op_iter iter;
240 0 : gimple *stmt = gsi_stmt (gsi);
241 0 : FOR_EACH_SSA_TREE_OPERAND (t, stmt, iter, SSA_OP_ALL_OPERANDS)
242 0 : bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t));
243 : }
244 : }
245 :
246 : /* Now walk the free list noting what we find there and verifying
247 : there are no duplicates. */
248 0 : auto_bitmap names_in_freelists;
249 0 : if (FREE_SSANAMES (fun))
250 : {
251 0 : for (unsigned int i = 0; i < FREE_SSANAMES (fun)->length (); i++)
252 : {
253 0 : tree t = (*FREE_SSANAMES (fun))[i];
254 :
255 : /* Verify that the name is marked as being in the free list. */
256 0 : gcc_assert (SSA_NAME_IN_FREE_LIST (t));
257 :
258 : /* Verify the name has not already appeared in the free list and
259 : note it in the list of names found in the free list. */
260 0 : gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
261 0 : bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
262 : }
263 : }
264 :
265 : /* Similarly for the names in the pending free list. */
266 0 : if (FREE_SSANAMES_QUEUE (fun))
267 : {
268 0 : for (unsigned int i = 0; i < FREE_SSANAMES_QUEUE (fun)->length (); i++)
269 : {
270 0 : tree t = (*FREE_SSANAMES_QUEUE (fun))[i];
271 :
272 : /* Verify that the name is marked as being in the free list. */
273 0 : gcc_assert (SSA_NAME_IN_FREE_LIST (t));
274 :
275 : /* Verify the name has not already appeared in the free list and
276 : note it in the list of names found in the free list. */
277 0 : gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t)));
278 0 : bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t));
279 : }
280 : }
281 :
282 : /* If any name appears in both the IL and the freelists, then
283 : something horrible has happened. */
284 0 : bool intersect_p = bitmap_intersect_p (names_in_il, names_in_freelists);
285 0 : gcc_assert (!intersect_p);
286 :
287 : /* Names can be queued up for release if there is an ssa update
288 : pending. Pretend we saw them in the IL. */
289 0 : if (names_to_release)
290 0 : bitmap_ior_into (names_in_il, names_to_release);
291 :
292 : /* Function splitting can "lose" SSA_NAMEs in an effort to ensure that
293 : debug/non-debug compilations have the same SSA_NAMEs. So for each
294 : lost SSA_NAME, see if it's likely one from that wart. These will always
295 : be marked as default definitions. So we loosely assume that anything
296 : marked as a default definition isn't leaked by pretending they are
297 : in the IL. */
298 0 : for (unsigned int i = UNUSED_NAME_VERSION + 1; i < num_ssa_names; i++)
299 0 : if (ssa_name (i) && SSA_NAME_IS_DEFAULT_DEF (ssa_name (i)))
300 0 : bitmap_set_bit (names_in_il, i);
301 :
302 0 : unsigned int i;
303 0 : bitmap_iterator bi;
304 0 : auto_bitmap all_names;
305 0 : bitmap_set_range (all_names, UNUSED_NAME_VERSION + 1, num_ssa_names - 1);
306 0 : bitmap_ior_into (names_in_il, names_in_freelists);
307 :
308 : /* Any name not mentioned in the IL and not in the feelists
309 : has been leaked. */
310 0 : EXECUTE_IF_AND_COMPL_IN_BITMAP(all_names, names_in_il,
311 : UNUSED_NAME_VERSION + 1, i, bi)
312 0 : gcc_assert (!ssa_name (i));
313 0 : }
314 :
315 : /* Move all SSA_NAMEs from FREE_SSA_NAMES_QUEUE to FREE_SSA_NAMES.
316 :
317 : We do not, but should have a mode to verify the state of the SSA_NAMEs
318 : lists. In particular at this point every name must be in the IL,
319 : on the free list or in the queue. Anything else is an error. */
320 :
321 : void
322 650914759 : flush_ssaname_freelist (void)
323 : {
324 : /* If there were any SSA names released reset the SCEV cache. */
325 650914759 : if (! vec_safe_is_empty (FREE_SSANAMES_QUEUE (cfun)))
326 10991798 : scev_reset_htab ();
327 650914759 : vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun));
328 650914759 : vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun), 0);
329 650914759 : }
330 :
331 : /* Initialize SSA_NAME_IMM_USE_NODE of a SSA NAME. */
332 :
333 : void
334 157500969 : init_ssa_name_imm_use (tree name)
335 : {
336 157500969 : use_operand_p imm;
337 157500969 : imm = &(SSA_NAME_IMM_USE_NODE (name));
338 157500969 : imm->use = NULL;
339 157500969 : imm->prev = imm;
340 157500969 : imm->next = imm;
341 157500969 : imm->loc.ssa_name = name;
342 157500969 : }
343 :
344 : /* Return an SSA_NAME node for variable VAR defined in statement STMT
345 : in function FN. STMT may be an empty statement for artificial
346 : references (e.g., default definitions created when a variable is
347 : used without a preceding definition). If VERISON is not zero then
348 : allocate the SSA name with that version. */
349 :
350 : tree
351 155030105 : make_ssa_name_fn (struct function *fn, tree var, gimple *stmt,
352 : unsigned int version)
353 : {
354 155030105 : tree t;
355 155030105 : gcc_assert (VAR_P (var)
356 : || TREE_CODE (var) == PARM_DECL
357 : || TREE_CODE (var) == RESULT_DECL
358 : || (TYPE_P (var) && is_gimple_reg_type (var)));
359 :
360 : /* Get the specified SSA name version. */
361 155030105 : if (version != 0)
362 : {
363 7617 : t = make_node (SSA_NAME);
364 7617 : SSA_NAME_VERSION (t) = version;
365 7617 : if (version >= SSANAMES (fn)->length ())
366 1704 : vec_safe_grow_cleared (SSANAMES (fn), version + 1, true);
367 7617 : gcc_assert ((*SSANAMES (fn))[version] == NULL);
368 7617 : (*SSANAMES (fn))[version] = t;
369 7617 : ssa_name_nodes_created++;
370 : }
371 : /* If our free list has an element, then use it. */
372 155022488 : else if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
373 : {
374 32423051 : t = FREE_SSANAMES (fn)->pop ();
375 32423051 : ssa_name_nodes_reused++;
376 :
377 : /* The node was cleared out when we put it on the free list, so
378 : there is no need to do so again here. */
379 32423051 : gcc_assert ((*SSANAMES (fn))[SSA_NAME_VERSION (t)] == NULL);
380 32423051 : (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
381 : }
382 : else
383 : {
384 122599437 : t = make_node (SSA_NAME);
385 122599437 : SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
386 122599437 : vec_safe_push (SSANAMES (fn), t);
387 122599437 : ssa_name_nodes_created++;
388 : }
389 :
390 155030105 : if (TYPE_P (var))
391 : {
392 59500779 : TREE_TYPE (t) = TYPE_MAIN_VARIANT (var);
393 59500779 : SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
394 : }
395 : else
396 : {
397 95529326 : TREE_TYPE (t) = TREE_TYPE (var);
398 140297901 : SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
399 : }
400 155030105 : SSA_NAME_DEF_STMT (t) = stmt;
401 155030105 : if (POINTER_TYPE_P (TREE_TYPE (t)))
402 31133249 : SSA_NAME_PTR_INFO (t) = NULL;
403 : else
404 123896856 : SSA_NAME_RANGE_INFO (t) = NULL;
405 :
406 155030105 : SSA_NAME_IN_FREE_LIST (t) = 0;
407 155030105 : SSA_NAME_IS_DEFAULT_DEF (t) = 0;
408 155030105 : init_ssa_name_imm_use (t);
409 : #if defined ENABLE_GIMPLE_CHECKING
410 155030105 : t->ssa_name.active_iterated_stmt = NULL;
411 155030105 : t->ssa_name.fast_iteration_depth = 0;
412 : #endif
413 :
414 155030105 : return t;
415 : }
416 :
417 : /* Update the range information for NAME, intersecting into an existing
418 : range if applicable. Return TRUE if the range was updated. */
419 :
420 : bool
421 45702113 : set_range_info (tree name, const vrange &r)
422 : {
423 45702113 : if (r.undefined_p () || r.varying_p ())
424 : return false;
425 :
426 : // Pick up the current range, or VARYING if none.
427 45541209 : tree type = TREE_TYPE (name);
428 45541209 : if (POINTER_TYPE_P (type))
429 : {
430 6623980 : struct ptr_info_def *pi = get_ptr_info (name);
431 : // If R is nonnull and pi is not, set nonnull.
432 6623980 : if (!r.contains_zero_p () && (!pi || pi->pt.null))
433 2556421 : set_ptr_nonnull (name);
434 : else
435 : return false;
436 : }
437 : else
438 : {
439 38917229 : value_range tmp (type);
440 38917229 : if (range_info_p (name))
441 30593928 : range_info_get_range (name, tmp);
442 : else
443 8323301 : tmp.set_varying (type);
444 : // If the result doesn't change, or is undefined, return false.
445 38917229 : if (!tmp.intersect (r) || tmp.undefined_p ())
446 : return false;
447 12531131 : if (!range_info_set_range (name, tmp))
448 : return false;
449 38917229 : }
450 15087552 : if (dump_file)
451 : {
452 4627 : value_range tmp (type);
453 4627 : fprintf (dump_file, "Global Exported: ");
454 4627 : print_generic_expr (dump_file, name, TDF_SLIM);
455 4627 : fprintf (dump_file, " = ");
456 4627 : gimple_range_global (tmp, name);
457 4627 : tmp.dump (dump_file);
458 4627 : fputc ('\n', dump_file);
459 4627 : }
460 : // Update the active query, if needed.
461 15087552 : get_range_query (cfun)->update_range_info (name, r);
462 15087552 : return true;
463 : }
464 :
465 : /* Set nonnull attribute to pointer NAME. */
466 :
467 : void
468 6265227 : set_ptr_nonnull (tree name)
469 : {
470 6265227 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
471 6265227 : struct ptr_info_def *pi = get_ptr_info (name);
472 6265227 : pi->pt.null = 0;
473 6265227 : }
474 :
475 : /* Update the non-zero bits bitmask of NAME. */
476 :
477 : void
478 0 : set_nonzero_bits (tree name, const wide_int &mask)
479 : {
480 0 : gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
481 :
482 0 : int_range<2> r (TREE_TYPE (name));
483 0 : r.set_nonzero_bits (mask);
484 0 : set_range_info (name, r);
485 0 : }
486 :
487 : /* Update the known bits of NAME.
488 :
489 : Zero bits in MASK cover constant values. Set bits in MASK cover
490 : unknown values. VALUE are the known bits. */
491 :
492 : void
493 13723754 : set_bitmask (tree name, const wide_int &value, const wide_int &mask)
494 : {
495 13723754 : gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
496 :
497 13723754 : int_range_max r (TREE_TYPE (name));
498 13723754 : r.update_bitmask (irange_bitmask (value, mask));
499 13723754 : set_range_info (name, r);
500 13723754 : }
501 :
502 : /* Return a wide_int with potentially non-zero bits in SSA_NAME
503 : NAME, the constant for INTEGER_CST, or -1 if unknown. */
504 :
505 : static wide_int
506 931935823 : get_nonzero_bits_1 (const_tree name)
507 : {
508 931935823 : if (TREE_CODE (name) == INTEGER_CST)
509 167929893 : return wi::to_wide (name);
510 :
511 764005930 : if (POLY_INT_CST_P (name))
512 : return -known_alignment (wi::to_poly_wide (name));
513 :
514 : /* Use element_precision instead of TYPE_PRECISION so complex and
515 : vector types get a non-zero precision. */
516 764005930 : unsigned int precision = element_precision (TREE_TYPE (name));
517 :
518 764005930 : if (VECTOR_TYPE_P (TREE_TYPE (name)))
519 : {
520 0 : tree elem = uniform_vector_p (name);
521 0 : if (elem)
522 0 : return get_nonzero_bits_1 (elem);
523 : }
524 :
525 764005930 : if (TREE_CODE (name) != SSA_NAME)
526 1071296 : return wi::shwi (-1, precision);
527 :
528 762934634 : if (POINTER_TYPE_P (TREE_TYPE (name)))
529 : {
530 62901041 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
531 62901041 : if (pi && pi->align)
532 3318484 : return wi::shwi (-(HOST_WIDE_INT) pi->align
533 6636968 : | (HOST_WIDE_INT) pi->misalign, precision);
534 59582557 : return wi::shwi (-1, precision);
535 : }
536 :
537 700033593 : if (!range_info_p (name) || !irange::supports_p (TREE_TYPE (name)))
538 471751486 : return wi::shwi (-1, precision);
539 :
540 228282107 : int_range_max tmp;
541 228282107 : range_info_get_range (name, tmp);
542 228282107 : return tmp.get_nonzero_bits ();
543 228282107 : }
544 :
545 : /* Return a wide_int with potentially non-zero bits in SSA_NAME
546 : NAME, the constant for INTEGER_CST, or -1 if unknown.
547 : In addition to what get_nonzero_bits_1 handles, this handles one
548 : level of BIT_AND_EXPR, either as a def_stmt or tree directly. */
549 :
550 : wide_int
551 876821140 : get_nonzero_bits (const_tree name)
552 : {
553 876821140 : if (TREE_CODE (name) == BIT_AND_EXPR)
554 3693394 : return (get_nonzero_bits_1 (TREE_OPERAND (name, 0))
555 5540091 : & get_nonzero_bits_1 (TREE_OPERAND (name, 1)));
556 874974443 : if (TREE_CODE (name) == SSA_NAME)
557 : {
558 723344617 : gimple *g = SSA_NAME_DEF_STMT (name);
559 723344617 : if (g
560 723344503 : && is_gimple_assign (g)
561 1253389298 : && gimple_assign_rhs_code (g) == BIT_AND_EXPR)
562 53267986 : return (get_nonzero_bits_1 (name)
563 106535972 : & get_nonzero_bits_1 (gimple_assign_rhs1 (g))
564 79901979 : & get_nonzero_bits_1 (gimple_assign_rhs2 (g)));
565 : }
566 848340450 : return get_nonzero_bits_1 (name);
567 : }
568 :
569 : /* Return a wide_int with known non-zero bits in SSA_NAME
570 : NAME (bits whose values aren't known are also clear), the constant
571 : for INTEGER_CST, or 0 if unknown. */
572 :
573 : static wide_int
574 386729086 : get_known_nonzero_bits_1 (const_tree name)
575 : {
576 386729086 : if (TREE_CODE (name) == INTEGER_CST)
577 181145527 : return wi::to_wide (name);
578 :
579 : /* Use element_precision instead of TYPE_PRECISION so complex and
580 : vector types get a non-zero precision. */
581 205583559 : unsigned int precision = element_precision (TREE_TYPE (name));
582 205583559 : if (TREE_CODE (name) != SSA_NAME || POINTER_TYPE_P (TREE_TYPE (name)))
583 14595 : return wi::shwi (0, precision);
584 :
585 205568964 : if (!range_info_p (name) || !irange::supports_p (TREE_TYPE (name)))
586 159604651 : return wi::shwi (0, precision);
587 :
588 45964313 : int_range_max tmp;
589 45964313 : range_info_get_range (name, tmp);
590 45964313 : if (tmp.undefined_p ())
591 0 : return wi::shwi (0, precision);
592 45964313 : irange_bitmask bm = tmp.get_bitmask ();
593 45964351 : return wi::bit_and_not (bm.value (), bm.mask ());
594 45964313 : }
595 :
596 : /* Return a wide_int with known non-zero bits in SSA_NAME
597 : NAME, the constant for INTEGER_CST, or 0 if unknown.
598 : In addition to what get_known_nonzero_bits_1 handles, this handles one
599 : level of BIT_IOR_EXPR, either as a def_stmt or tree directly. */
600 :
601 : wide_int
602 378708171 : get_known_nonzero_bits (const_tree name)
603 : {
604 378708171 : if (TREE_CODE (name) == BIT_IOR_EXPR)
605 537222 : return (get_known_nonzero_bits_1 (TREE_OPERAND (name, 0))
606 805833 : | get_known_nonzero_bits_1 (TREE_OPERAND (name, 1)));
607 378439560 : if (TREE_CODE (name) == SSA_NAME)
608 : {
609 197320006 : gimple *g = SSA_NAME_DEF_STMT (name);
610 197320006 : if (g
611 197320006 : && is_gimple_assign (g)
612 328623798 : && gimple_assign_rhs_code (g) == BIT_IOR_EXPR)
613 7752304 : return (get_known_nonzero_bits_1 (name)
614 15504608 : | get_known_nonzero_bits_1 (gimple_assign_rhs1 (g))
615 11628456 : | get_known_nonzero_bits_1 (gimple_assign_rhs2 (g)));
616 : }
617 374563408 : return get_known_nonzero_bits_1 (name);
618 : }
619 :
620 : /* Return TRUE is OP, an SSA_NAME has a range of values [0..1] at the
621 : STMT, false otherwise.
622 :
623 : This can be because it is a boolean type, any unsigned integral
624 : type with a single bit of precision, or has known range of [0..1]
625 : via range analysis. */
626 :
627 : bool
628 29367904 : ssa_name_has_boolean_range (tree op, gimple *stmt)
629 : {
630 29367904 : gcc_assert (TREE_CODE (op) == SSA_NAME);
631 :
632 : /* An integral type with a single bit of precision. */
633 58207313 : if (INTEGRAL_TYPE_P (TREE_TYPE (op))
634 22603244 : && TYPE_UNSIGNED (TREE_TYPE (op))
635 42328729 : && TYPE_PRECISION (TREE_TYPE (op)) == 1)
636 : return true;
637 :
638 : /* An integral type with more precision, but the object
639 : only takes on values [0..1] as determined by range
640 : analysis. */
641 50901251 : if (INTEGRAL_TYPE_P (TREE_TYPE (op))
642 44136591 : && (TYPE_PRECISION (TREE_TYPE (op)) > 1))
643 : {
644 18948476 : int_range<2> r;
645 37896952 : if (get_range_query (cfun)->range_of_expr (r, op, stmt)
646 18948476 : && r == range_true_and_false (TREE_TYPE (op)))
647 : return true;
648 :
649 18441758 : if (wi::eq_p (get_nonzero_bits (op), 1))
650 : return true;
651 18948476 : }
652 :
653 : return false;
654 : }
655 :
656 : /* We no longer need the SSA_NAME expression VAR, release it so that
657 : it may be reused.
658 :
659 : Note it is assumed that no calls to make_ssa_name will be made
660 : until all uses of the ssa name are released and that the only
661 : use of the SSA_NAME expression is to check its SSA_NAME_VAR. All
662 : other fields must be assumed clobbered. */
663 :
664 : void
665 86952800 : release_ssa_name_fn (struct function *fn, tree var)
666 : {
667 86952800 : if (!var)
668 : return;
669 :
670 : /* Never release the default definition for a symbol. It's a
671 : special SSA name that should always exist once it's created. */
672 86952800 : if (SSA_NAME_IS_DEFAULT_DEF (var))
673 : return;
674 :
675 : /* If VAR has been registered for SSA updating, don't remove it.
676 : After update_ssa has run, the name will be released. */
677 86952772 : if (name_registered_for_update_p (var))
678 : {
679 852302 : release_ssa_name_after_update_ssa (var);
680 852302 : return;
681 : }
682 :
683 : /* release_ssa_name can be called multiple times on a single SSA_NAME.
684 : However, it should only end up on our free list one time. We
685 : keep a status bit in the SSA_NAME node itself to indicate it has
686 : been put on the free list.
687 :
688 : Note that once on the freelist you cannot reference the SSA_NAME's
689 : defining statement. */
690 86100470 : if (! SSA_NAME_IN_FREE_LIST (var))
691 : {
692 86100470 : int saved_ssa_name_version = SSA_NAME_VERSION (var);
693 86100470 : use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
694 :
695 86100470 : if (MAY_HAVE_DEBUG_BIND_STMTS)
696 56938588 : insert_debug_temp_for_var_def (NULL, var);
697 :
698 86100470 : if (flag_checking)
699 86099889 : verify_imm_links (stderr, var);
700 97128533 : while (imm->next != imm)
701 11028063 : delink_imm_use (imm->next);
702 :
703 86100470 : (*SSANAMES (fn))[SSA_NAME_VERSION (var)] = NULL_TREE;
704 86100470 : memset (var, 0, tree_size (var));
705 :
706 86100470 : imm->prev = imm;
707 86100470 : imm->next = imm;
708 86100470 : imm->loc.ssa_name = var;
709 :
710 : /* First put back the right tree node so that the tree checking
711 : macros do not complain. */
712 86100470 : TREE_SET_CODE (var, SSA_NAME);
713 :
714 : /* Restore the version number. */
715 86100470 : SSA_NAME_VERSION (var) = saved_ssa_name_version;
716 :
717 : /* Note this SSA_NAME is now in the first list. */
718 86100470 : SSA_NAME_IN_FREE_LIST (var) = 1;
719 :
720 : /* Put in a non-NULL TREE_TYPE so dumping code will not ICE
721 : if it happens to come along a released SSA name and tries
722 : to inspect its type. */
723 86100470 : TREE_TYPE (var) = error_mark_node;
724 :
725 : /* And finally queue it so that it will be put on the free list. */
726 86100470 : vec_safe_push (FREE_SSANAMES_QUEUE (fn), var);
727 : }
728 : }
729 :
730 : /* If the alignment of the pointer described by PI is known, return true and
731 : store the alignment and the deviation from it into *ALIGNP and *MISALIGNP
732 : respectively. Otherwise return false. */
733 :
734 : bool
735 50885222 : get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
736 : unsigned int *misalignp)
737 : {
738 50885222 : if (pi->align)
739 : {
740 6441123 : *alignp = pi->align;
741 6441123 : *misalignp = pi->misalign;
742 6441123 : return true;
743 : }
744 : else
745 : return false;
746 : }
747 :
748 : /* State that the pointer described by PI has unknown alignment. */
749 :
750 : void
751 16754595 : mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
752 : {
753 16754595 : pi->align = 0;
754 16754595 : pi->misalign = 0;
755 16754595 : }
756 :
757 : /* Store the power-of-two byte alignment and the deviation from that
758 : alignment of pointer described by PI to ALIOGN and MISALIGN
759 : respectively. */
760 :
761 : void
762 1723735 : set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
763 : unsigned int misalign)
764 : {
765 1723735 : gcc_checking_assert (align != 0);
766 1723735 : gcc_assert ((align & (align - 1)) == 0);
767 1723735 : gcc_assert ((misalign & ~(align - 1)) == 0);
768 :
769 1723735 : pi->align = align;
770 1723735 : pi->misalign = misalign;
771 1723735 : }
772 :
773 : /* If pointer described by PI has known alignment, increase its known
774 : misalignment by INCREMENT modulo its current alignment. */
775 :
776 : void
777 0 : adjust_ptr_info_misalignment (struct ptr_info_def *pi, poly_uint64 increment)
778 : {
779 0 : if (pi->align != 0)
780 : {
781 0 : increment += pi->misalign;
782 0 : if (!known_misalignment (increment, pi->align, &pi->misalign))
783 : {
784 : pi->align = known_alignment (increment);
785 : pi->misalign = 0;
786 : }
787 : }
788 0 : }
789 :
790 : /* Return the alias information associated with pointer T. It creates a
791 : new instance if none existed. */
792 :
793 : struct ptr_info_def *
794 38731532 : get_ptr_info (tree t)
795 : {
796 38731532 : struct ptr_info_def *pi;
797 :
798 38731532 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
799 :
800 38731532 : pi = SSA_NAME_PTR_INFO (t);
801 38731532 : if (pi == NULL)
802 : {
803 15403182 : pi = ggc_cleared_alloc<ptr_info_def> ();
804 15403182 : pt_solution_reset (&pi->pt);
805 15403182 : mark_ptr_info_alignment_unknown (pi);
806 15403182 : SSA_NAME_PTR_INFO (t) = pi;
807 : }
808 :
809 38731532 : return pi;
810 : }
811 :
812 :
813 : /* Creates a new SSA name using the template NAME tobe defined by
814 : statement STMT in function FN. */
815 :
816 : tree
817 19986003 : copy_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
818 : {
819 19986003 : tree new_name;
820 :
821 19986003 : if (SSA_NAME_VAR (name))
822 12702110 : new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
823 : else
824 : {
825 7283893 : new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
826 14567786 : SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
827 : }
828 :
829 19986003 : return new_name;
830 : }
831 :
832 :
833 : /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
834 : the SSA name NAME. */
835 :
836 : void
837 3225611 : duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
838 : {
839 3225611 : struct ptr_info_def *new_ptr_info;
840 :
841 3225611 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
842 3225611 : gcc_assert (!SSA_NAME_PTR_INFO (name));
843 :
844 3225611 : if (!ptr_info)
845 : return;
846 :
847 3184795 : new_ptr_info = ggc_alloc<ptr_info_def> ();
848 3184795 : *new_ptr_info = *ptr_info;
849 :
850 3184795 : SSA_NAME_PTR_INFO (name) = new_ptr_info;
851 : }
852 :
853 : void
854 8712155 : duplicate_ssa_name_range_info (tree name, tree src)
855 : {
856 8712155 : gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (src)));
857 8712155 : gcc_checking_assert (!range_info_p (name));
858 :
859 8712155 : if (range_info_p (src))
860 : {
861 8712155 : value_range src_range (TREE_TYPE (src));
862 8712155 : range_info_get_range (src, src_range);
863 8712155 : range_info_set_range (name, src_range);
864 8712155 : }
865 8712155 : }
866 :
867 : /* For a SSA copy DEST = SRC duplicate SSA info present on DEST to SRC
868 : to preserve it in case DEST is eliminated to SRC. */
869 :
870 : void
871 55463175 : maybe_duplicate_ssa_info_at_copy (tree dest, tree src)
872 : {
873 : /* While points-to info is flow-insensitive we have to avoid copying
874 : info from not executed regions invoking UB to dominating defs. */
875 55463175 : if (gimple_bb (SSA_NAME_DEF_STMT (src))
876 55463175 : != gimple_bb (SSA_NAME_DEF_STMT (dest)))
877 : return;
878 :
879 68403291 : if (POINTER_TYPE_P (TREE_TYPE (dest))
880 18707480 : && SSA_NAME_PTR_INFO (dest)
881 52109901 : && ! SSA_NAME_PTR_INFO (src))
882 429674 : duplicate_ssa_name_ptr_info (src, SSA_NAME_PTR_INFO (dest));
883 84709347 : else if (INTEGRAL_TYPE_P (TREE_TYPE (dest))
884 20448450 : && SSA_NAME_RANGE_INFO (dest)
885 43602684 : && ! SSA_NAME_RANGE_INFO (src))
886 96290 : duplicate_ssa_name_range_info (src, dest);
887 : }
888 :
889 :
890 : /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT
891 : in function FN. */
892 :
893 : tree
894 18296318 : duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
895 : {
896 18296318 : tree new_name = copy_ssa_name_fn (fn, name, stmt);
897 18296318 : if (POINTER_TYPE_P (TREE_TYPE (name)))
898 : {
899 2326314 : struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
900 :
901 2326314 : if (old_ptr_info)
902 2082261 : duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
903 : }
904 15970004 : else if (range_info_p (name))
905 4417793 : duplicate_ssa_name_range_info (new_name, name);
906 :
907 18296318 : return new_name;
908 : }
909 :
910 :
911 : /* Reset all flow sensitive data on NAME such as range-info, nonzero
912 : bits and alignment. */
913 :
914 : void
915 7880577 : reset_flow_sensitive_info (tree name)
916 : {
917 7880577 : if (POINTER_TYPE_P (TREE_TYPE (name)))
918 : {
919 : /* points-to info is not flow-sensitive. */
920 692948 : if (SSA_NAME_PTR_INFO (name))
921 : {
922 : /* [E]VRP can derive context sensitive alignment info and
923 : non-nullness properties. We must reset both. */
924 690815 : mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
925 690815 : SSA_NAME_PTR_INFO (name)->pt.null = 1;
926 : }
927 : }
928 : else
929 7187629 : SSA_NAME_RANGE_INFO (name) = NULL;
930 :
931 : // Clear range info in the current range query.
932 15761154 : get_range_query (cfun)->reset_range_info (name);
933 7880577 : }
934 :
935 : /* Clear all flow sensitive data from all statements and PHI definitions
936 : in BB. */
937 :
938 : void
939 1433522 : reset_flow_sensitive_info_in_bb (basic_block bb)
940 : {
941 4210561 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
942 1343517 : gsi_next (&gsi))
943 : {
944 1343517 : gimple *stmt = gsi_stmt (gsi);
945 1343517 : ssa_op_iter i;
946 1343517 : tree op;
947 1626511 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
948 282994 : reset_flow_sensitive_info (op);
949 : }
950 :
951 1445120 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
952 11598 : gsi_next (&gsi))
953 : {
954 11598 : tree phi_def = gimple_phi_result (gsi.phi ());
955 11598 : reset_flow_sensitive_info (phi_def);
956 : }
957 1433522 : }
958 :
959 : /* Release all the SSA_NAMEs created by STMT. */
960 :
961 : void
962 78861672 : release_defs (gimple *stmt)
963 : {
964 78861672 : tree def;
965 78861672 : ssa_op_iter iter;
966 :
967 132454205 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
968 53592533 : if (TREE_CODE (def) == SSA_NAME)
969 53041357 : release_ssa_name (def);
970 78861672 : }
971 :
972 :
973 : /* Replace the symbol associated with SSA_NAME with SYM. */
974 :
975 : void
976 12584 : replace_ssa_name_symbol (tree ssa_name, tree sym)
977 : {
978 12584 : SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
979 12584 : TREE_TYPE (ssa_name) = TREE_TYPE (sym);
980 12584 : }
981 :
982 : /* Release the vector of free SSA_NAMEs and compact the vector of SSA_NAMEs
983 : that are live. */
984 :
985 : static void
986 3003737 : release_free_names_and_compact_live_names (function *fun)
987 : {
988 3003737 : unsigned i, j;
989 3003737 : int n = vec_safe_length (FREE_SSANAMES (fun));
990 :
991 : /* Now release the freelist. */
992 3003737 : vec_free (FREE_SSANAMES (fun));
993 :
994 : /* And compact the SSA number space. We make sure to not change the
995 : relative order of SSA versions. */
996 85453347 : for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
997 : {
998 82449610 : tree name = ssa_name (i);
999 82449610 : if (name)
1000 : {
1001 52310663 : if (i != j)
1002 : {
1003 32565675 : SSA_NAME_VERSION (name) = j;
1004 32565675 : (*fun->gimple_df->ssa_names)[j] = name;
1005 : }
1006 52310663 : j++;
1007 : }
1008 : }
1009 3003737 : fun->gimple_df->ssa_names->truncate (j);
1010 :
1011 3003737 : statistics_counter_event (fun, "SSA names released", n);
1012 3003737 : statistics_counter_event (fun, "SSA name holes removed", i - j);
1013 3003737 : if (dump_file)
1014 350 : fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
1015 350 : n, n * 100.0 / num_ssa_names, i - j);
1016 3003737 : }
1017 :
1018 : /* Return SSA names that are unused to GGC memory and compact the SSA
1019 : version namespace. This is used to keep footprint of compiler during
1020 : interprocedural optimization. */
1021 :
1022 : namespace {
1023 :
1024 : const pass_data pass_data_release_ssa_names =
1025 : {
1026 : GIMPLE_PASS, /* type */
1027 : "release_ssa", /* name */
1028 : OPTGROUP_NONE, /* optinfo_flags */
1029 : TV_TREE_SSA_OTHER, /* tv_id */
1030 : PROP_ssa, /* properties_required */
1031 : 0, /* properties_provided */
1032 : 0, /* properties_destroyed */
1033 : TODO_remove_unused_locals, /* todo_flags_start */
1034 : 0, /* todo_flags_finish */
1035 : };
1036 :
1037 : class pass_release_ssa_names : public gimple_opt_pass
1038 : {
1039 : public:
1040 294196 : pass_release_ssa_names (gcc::context *ctxt)
1041 588392 : : gimple_opt_pass (pass_data_release_ssa_names, ctxt)
1042 : {}
1043 :
1044 : /* opt_pass methods: */
1045 : unsigned int execute (function *) final override;
1046 :
1047 : }; // class pass_release_ssa_names
1048 :
1049 : unsigned int
1050 3003737 : pass_release_ssa_names::execute (function *fun)
1051 : {
1052 3003737 : release_free_names_and_compact_live_names (fun);
1053 3003737 : return 0;
1054 : }
1055 :
1056 : } // anon namespace
1057 :
1058 : gimple_opt_pass *
1059 294196 : make_pass_release_ssa_names (gcc::context *ctxt)
1060 : {
1061 294196 : return new pass_release_ssa_names (ctxt);
1062 : }
1063 :
1064 : /* Save and restore of flow sensitive information. */
1065 :
1066 : /* Save off the flow sensitive info from NAME. */
1067 :
1068 : void
1069 7030315 : flow_sensitive_info_storage::save (tree name)
1070 : {
1071 7030315 : gcc_assert (state == 0);
1072 7030315 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
1073 : {
1074 6663715 : range_info = SSA_NAME_RANGE_INFO (name);
1075 6663715 : state = 1;
1076 6663715 : return;
1077 : }
1078 366600 : state = -1;
1079 366600 : auto ptr_info = SSA_NAME_PTR_INFO (name);
1080 366600 : if (ptr_info)
1081 : {
1082 366003 : align = ptr_info->align;
1083 366003 : misalign = ptr_info->misalign;
1084 366003 : null = SSA_NAME_PTR_INFO (name)->pt.null;
1085 : }
1086 : else
1087 : {
1088 597 : align = 0;
1089 597 : misalign = 0;
1090 597 : null = true;
1091 : }
1092 : }
1093 :
1094 : /* Restore the flow sensitive info from NAME. */
1095 :
1096 : void
1097 7030315 : flow_sensitive_info_storage::restore (tree name)
1098 : {
1099 7030315 : gcc_assert (state != 0);
1100 7030315 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
1101 : {
1102 6663715 : gcc_assert (state == 1);
1103 6663715 : SSA_NAME_RANGE_INFO (name) = range_info;
1104 6663715 : return;
1105 : }
1106 366600 : gcc_assert (state == -1);
1107 366600 : auto ptr_info = SSA_NAME_PTR_INFO (name);
1108 : /* If there was no flow sensitive info on the pointer
1109 : just return, there is nothing to restore to. */
1110 366600 : if (!ptr_info)
1111 : return;
1112 366003 : if (align != 0)
1113 339 : set_ptr_info_alignment (ptr_info, align, misalign);
1114 : else
1115 365664 : mark_ptr_info_alignment_unknown (ptr_info);
1116 366003 : SSA_NAME_PTR_INFO (name)->pt.null = null;
1117 : }
1118 :
1119 : /* Save off the flow sensitive info from NAME.
1120 : And reset the flow sensitive info of NAME. */
1121 :
1122 : void
1123 7030315 : flow_sensitive_info_storage::save_and_clear (tree name)
1124 : {
1125 7030315 : save (name);
1126 7030315 : reset_flow_sensitive_info (name);
1127 7030315 : }
1128 :
1129 : /* Clear the storage. */
1130 : void
1131 0 : flow_sensitive_info_storage::clear_storage (void)
1132 : {
1133 0 : state = 0;
1134 0 : }
|
