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 984052404 : range_info_p (const_tree name)
80 : {
81 984052404 : 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 4115246 : range_info_fits_p (tree name, const vrange &r)
88 : {
89 4115246 : gcc_checking_assert (range_info_p (name));
90 4115246 : vrange_storage *mem = SSA_NAME_RANGE_INFO (name);
91 4115246 : 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 16903982 : range_info_alloc (tree name, const vrange &r)
99 : {
100 16903982 : vrange_storage *mem = ggc_alloc_vrange_storage (r);
101 16903982 : SSA_NAME_RANGE_INFO (name) = mem;
102 16903982 : return mem;
103 : }
104 :
105 : /* Free storage allocated for the global range for NAME. */
106 :
107 : inline void
108 591625 : range_info_free (tree name)
109 : {
110 591625 : vrange_storage *mem = SSA_NAME_RANGE_INFO (name);
111 591625 : ggc_free (mem);
112 591625 : }
113 :
114 : /* Return the global range for NAME in R. */
115 :
116 : inline void
117 303739679 : range_info_get_range (const_tree name, vrange &r)
118 : {
119 303739679 : SSA_NAME_RANGE_INFO (name)->get_vrange (r, TREE_TYPE (name));
120 303739679 : }
121 :
122 : /* Set the global range for NAME from R. Return TRUE if successfull,
123 : or FALSE if we can't set a range of NAME's type. */
124 :
125 : inline bool
126 20427603 : range_info_set_range (tree name, const vrange &r)
127 : {
128 20427603 : if (!range_info_p (name) || !range_info_fits_p (name, r))
129 : {
130 16903982 : if (range_info_p (name))
131 591625 : range_info_free (name);
132 :
133 16903982 : return range_info_alloc (name, r);
134 : }
135 : else
136 : {
137 3523621 : SSA_NAME_RANGE_INFO (name)->set_vrange (r);
138 3523621 : 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 3257665 : init_ssanames (struct function *fn, int size)
147 : {
148 3257665 : if (!size)
149 3174212 : vec_alloc (SSANAMES (fn), 50);
150 : else
151 83453 : 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 3257665 : SSANAMES (fn)->quick_push (NULL_TREE);
161 3257665 : FREE_SSANAMES (fn) = NULL;
162 3257665 : FREE_SSANAMES_QUEUE (fn) = NULL;
163 :
164 3257665 : fn->gimple_df->ssa_renaming_needed = 0;
165 3257665 : fn->gimple_df->rename_vops = 0;
166 3257665 : }
167 :
168 : /* Finalize management of SSA_NAMEs. */
169 :
170 : void
171 3152021 : fini_ssanames (struct function *fn)
172 : {
173 3152021 : unsigned i;
174 3152021 : 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 94091976 : FOR_EACH_VEC_SAFE_ELT (SSANAMES (fn), i, name)
179 90939955 : if (name)
180 64950397 : SSA_NAME_DEF_STMT (name) = NULL;
181 3152021 : vec_free (SSANAMES (fn));
182 3152021 : vec_free (FREE_SSANAMES (fn));
183 3152021 : vec_free (FREE_SSANAMES_QUEUE (fn));
184 3152021 : }
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 629221838 : flush_ssaname_freelist (void)
323 : {
324 : /* If there were any SSA names released reset the SCEV cache. */
325 629221838 : if (! vec_safe_is_empty (FREE_SSANAMES_QUEUE (cfun)))
326 10511417 : scev_reset_htab ();
327 629221838 : vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun));
328 629221838 : vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun), 0);
329 629221838 : }
330 :
331 : /* Initialize SSA_NAME_IMM_USE_NODE of a SSA NAME. */
332 :
333 : void
334 149930048 : init_ssa_name_imm_use (tree name)
335 : {
336 149930048 : use_operand_p imm;
337 149930048 : imm = &(SSA_NAME_IMM_USE_NODE (name));
338 149930048 : imm->use = NULL;
339 149930048 : imm->prev = imm;
340 149930048 : imm->next = imm;
341 149930048 : imm->loc.ssa_name = name;
342 149930048 : }
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 148193004 : make_ssa_name_fn (struct function *fn, tree var, gimple *stmt,
352 : unsigned int version)
353 : {
354 148193004 : tree t;
355 148193004 : 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 148193004 : if (version != 0)
362 : {
363 6850 : t = make_node (SSA_NAME);
364 6850 : SSA_NAME_VERSION (t) = version;
365 6850 : if (version >= SSANAMES (fn)->length ())
366 1470 : vec_safe_grow_cleared (SSANAMES (fn), version + 1, true);
367 6850 : gcc_assert ((*SSANAMES (fn))[version] == NULL);
368 6850 : (*SSANAMES (fn))[version] = t;
369 6850 : ssa_name_nodes_created++;
370 : }
371 : /* If our free list has an element, then use it. */
372 148186154 : else if (!vec_safe_is_empty (FREE_SSANAMES (fn)))
373 : {
374 31168081 : t = FREE_SSANAMES (fn)->pop ();
375 31168081 : 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 31168081 : gcc_assert ((*SSANAMES (fn))[SSA_NAME_VERSION (t)] == NULL);
380 31168081 : (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t;
381 : }
382 : else
383 : {
384 117018073 : t = make_node (SSA_NAME);
385 117018073 : SSA_NAME_VERSION (t) = SSANAMES (fn)->length ();
386 117018073 : vec_safe_push (SSANAMES (fn), t);
387 117018073 : ssa_name_nodes_created++;
388 : }
389 :
390 148193004 : if (TYPE_P (var))
391 : {
392 56659060 : TREE_TYPE (t) = TYPE_MAIN_VARIANT (var);
393 56659060 : SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE);
394 : }
395 : else
396 : {
397 91533944 : TREE_TYPE (t) = TREE_TYPE (var);
398 134919463 : SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var);
399 : }
400 148193004 : SSA_NAME_DEF_STMT (t) = stmt;
401 148193004 : if (POINTER_TYPE_P (TREE_TYPE (t)))
402 30001420 : SSA_NAME_PTR_INFO (t) = NULL;
403 : else
404 118191584 : SSA_NAME_RANGE_INFO (t) = NULL;
405 :
406 148193004 : SSA_NAME_IN_FREE_LIST (t) = 0;
407 148193004 : SSA_NAME_IS_DEFAULT_DEF (t) = 0;
408 148193004 : init_ssa_name_imm_use (t);
409 : #if defined ENABLE_GIMPLE_CHECKING
410 148193004 : t->ssa_name.active_iterated_stmt = NULL;
411 148193004 : t->ssa_name.fast_iteration_depth = 0;
412 : #endif
413 :
414 148193004 : 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 44437983 : set_range_info (tree name, const vrange &r)
422 : {
423 44437983 : if (r.undefined_p () || r.varying_p ())
424 : return false;
425 :
426 : // Pick up the current range, or VARYING if none.
427 44288856 : tree type = TREE_TYPE (name);
428 44288856 : if (POINTER_TYPE_P (type))
429 : {
430 6490415 : struct ptr_info_def *pi = get_ptr_info (name);
431 : // If R is nonnull and pi is not, set nonnull.
432 6490415 : if (r.nonzero_p () && (!pi || pi->pt.null))
433 2482718 : set_ptr_nonnull (name);
434 : else
435 : return false;
436 : }
437 : else
438 : {
439 37798441 : value_range tmp (type);
440 37798441 : if (range_info_p (name))
441 29653298 : range_info_get_range (name, tmp);
442 : else
443 8145143 : tmp.set_varying (type);
444 : // If the result doesn't change, or is undefined, return false.
445 37798441 : if (!tmp.intersect (r) || tmp.undefined_p ())
446 : return false;
447 12260389 : if (!range_info_set_range (name, tmp))
448 : return false;
449 37798441 : }
450 14743107 : if (dump_file)
451 : {
452 4368 : value_range tmp (type);
453 4368 : fprintf (dump_file, "Global Exported: ");
454 4368 : print_generic_expr (dump_file, name, TDF_SLIM);
455 4368 : fprintf (dump_file, " = ");
456 4368 : gimple_range_global (tmp, name);
457 4368 : tmp.dump (dump_file);
458 4368 : fputc ('\n', dump_file);
459 4368 : }
460 : // Update the active query, if needed.
461 14743107 : get_range_query (cfun)->update_range_info (name, r);
462 14743107 : return true;
463 : }
464 :
465 : /* Set nonnull attribute to pointer NAME. */
466 :
467 : void
468 6037751 : set_ptr_nonnull (tree name)
469 : {
470 6037751 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
471 6037751 : struct ptr_info_def *pi = get_ptr_info (name);
472 6037751 : pi->pt.null = 0;
473 6037751 : }
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 13314583 : set_bitmask (tree name, const wide_int &value, const wide_int &mask)
494 : {
495 13314583 : gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
496 :
497 13314583 : int_range_max r (TREE_TYPE (name));
498 13314583 : r.update_bitmask (irange_bitmask (value, mask));
499 13314583 : set_range_info (name, r);
500 13314583 : }
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 899292965 : get_nonzero_bits_1 (const_tree name)
507 : {
508 899292965 : if (TREE_CODE (name) == INTEGER_CST)
509 163415871 : return wi::to_wide (name);
510 :
511 735877094 : 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 735877094 : unsigned int precision = element_precision (TREE_TYPE (name));
517 :
518 735877094 : 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 735877094 : if (TREE_CODE (name) != SSA_NAME)
526 1128114 : return wi::shwi (-1, precision);
527 :
528 734748980 : if (POINTER_TYPE_P (TREE_TYPE (name)))
529 : {
530 61171306 : struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
531 61171306 : if (pi && pi->align)
532 3266459 : return wi::shwi (-(HOST_WIDE_INT) pi->align
533 6532918 : | (HOST_WIDE_INT) pi->misalign, precision);
534 57904847 : return wi::shwi (-1, precision);
535 : }
536 :
537 673577674 : if (!range_info_p (name) || !irange::supports_p (TREE_TYPE (name)))
538 452648008 : return wi::shwi (-1, precision);
539 :
540 220929666 : int_range_max tmp;
541 220929666 : range_info_get_range (name, tmp);
542 220929666 : return tmp.get_nonzero_bits ();
543 220929666 : }
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 845394886 : get_nonzero_bits (const_tree name)
552 : {
553 845394886 : if (TREE_CODE (name) == BIT_AND_EXPR)
554 3825114 : return (get_nonzero_bits_1 (TREE_OPERAND (name, 0))
555 5737671 : & get_nonzero_bits_1 (TREE_OPERAND (name, 1)));
556 843482329 : if (TREE_CODE (name) == SSA_NAME)
557 : {
558 696833366 : gimple *g = SSA_NAME_DEF_STMT (name);
559 696833366 : if (g
560 696831910 : && is_gimple_assign (g)
561 1206373953 : && gimple_assign_rhs_code (g) == BIT_AND_EXPR)
562 51985522 : return (get_nonzero_bits_1 (name)
563 103971044 : & get_nonzero_bits_1 (gimple_assign_rhs1 (g))
564 77978283 : & get_nonzero_bits_1 (gimple_assign_rhs2 (g)));
565 : }
566 817489568 : 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 375046938 : get_known_nonzero_bits_1 (const_tree name)
575 : {
576 375046938 : if (TREE_CODE (name) == INTEGER_CST)
577 175479456 : 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 199567482 : unsigned int precision = element_precision (TREE_TYPE (name));
582 199567482 : if (TREE_CODE (name) != SSA_NAME || POINTER_TYPE_P (TREE_TYPE (name)))
583 14071 : return wi::shwi (0, precision);
584 :
585 199553411 : if (!range_info_p (name) || !irange::supports_p (TREE_TYPE (name)))
586 154563910 : return wi::shwi (0, precision);
587 :
588 44989501 : int_range_max tmp;
589 44989501 : range_info_get_range (name, tmp);
590 44989501 : if (tmp.undefined_p ())
591 0 : return wi::shwi (0, precision);
592 44989501 : irange_bitmask bm = tmp.get_bitmask ();
593 44989539 : return wi::bit_and_not (bm.value (), bm.mask ());
594 44989501 : }
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 367277102 : get_known_nonzero_bits (const_tree name)
603 : {
604 367277102 : if (TREE_CODE (name) == BIT_IOR_EXPR)
605 525948 : return (get_known_nonzero_bits_1 (TREE_OPERAND (name, 0))
606 788922 : | get_known_nonzero_bits_1 (TREE_OPERAND (name, 1)));
607 367014128 : if (TREE_CODE (name) == SSA_NAME)
608 : {
609 191562759 : gimple *g = SSA_NAME_DEF_STMT (name);
610 191562759 : if (g
611 191562759 : && is_gimple_assign (g)
612 318924936 : && gimple_assign_rhs_code (g) == BIT_IOR_EXPR)
613 7506862 : return (get_known_nonzero_bits_1 (name)
614 15013724 : | get_known_nonzero_bits_1 (gimple_assign_rhs1 (g))
615 11260293 : | get_known_nonzero_bits_1 (gimple_assign_rhs2 (g)));
616 : }
617 363260697 : 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 28774775 : ssa_name_has_boolean_range (tree op, gimple *stmt)
629 : {
630 28774775 : gcc_assert (TREE_CODE (op) == SSA_NAME);
631 :
632 : /* An integral type with a single bit of precision. */
633 57007273 : if (INTEGRAL_TYPE_P (TREE_TYPE (op))
634 22140504 : && TYPE_UNSIGNED (TREE_TYPE (op))
635 41553620 : && 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 49949523 : if (INTEGRAL_TYPE_P (TREE_TYPE (op))
642 43315252 : && (TYPE_PRECISION (TREE_TYPE (op)) > 1))
643 : {
644 18610480 : int_range<2> r;
645 37220960 : if (get_range_query (cfun)->range_of_expr (r, op, stmt)
646 18610480 : && r == range_true_and_false (TREE_TYPE (op)))
647 : return true;
648 :
649 18092976 : if (wi::eq_p (get_nonzero_bits (op), 1))
650 : return true;
651 18610480 : }
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 83431602 : release_ssa_name_fn (struct function *fn, tree var)
666 : {
667 83431602 : 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 83431602 : 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 83431602 : if (name_registered_for_update_p (var))
678 : {
679 894617 : release_ssa_name_after_update_ssa (var);
680 894617 : 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 82536985 : if (! SSA_NAME_IN_FREE_LIST (var))
691 : {
692 82536985 : int saved_ssa_name_version = SSA_NAME_VERSION (var);
693 82536985 : use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
694 :
695 82536985 : if (MAY_HAVE_DEBUG_BIND_STMTS)
696 54272916 : insert_debug_temp_for_var_def (NULL, var);
697 :
698 82536985 : if (flag_checking)
699 82536376 : verify_imm_links (stderr, var);
700 93487069 : while (imm->next != imm)
701 10950084 : delink_imm_use (imm->next);
702 :
703 82536985 : (*SSANAMES (fn))[SSA_NAME_VERSION (var)] = NULL_TREE;
704 82536985 : memset (var, 0, tree_size (var));
705 :
706 82536985 : imm->prev = imm;
707 82536985 : imm->next = imm;
708 82536985 : 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 82536985 : TREE_SET_CODE (var, SSA_NAME);
713 :
714 : /* Restore the version number. */
715 82536985 : SSA_NAME_VERSION (var) = saved_ssa_name_version;
716 :
717 : /* Note this SSA_NAME is now in the first list. */
718 82536985 : 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 82536985 : TREE_TYPE (var) = error_mark_node;
724 :
725 : /* And finally queue it so that it will be put on the free list. */
726 82536985 : 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 49109116 : get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp,
736 : unsigned int *misalignp)
737 : {
738 49109116 : if (pi->align)
739 : {
740 6026870 : *alignp = pi->align;
741 6026870 : *misalignp = pi->misalign;
742 6026870 : 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 15403372 : mark_ptr_info_alignment_unknown (struct ptr_info_def *pi)
752 : {
753 15403372 : pi->align = 0;
754 15403372 : pi->misalign = 0;
755 15403372 : }
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 1686516 : set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align,
763 : unsigned int misalign)
764 : {
765 1686516 : gcc_checking_assert (align != 0);
766 1686516 : gcc_assert ((align & (align - 1)) == 0);
767 1686516 : gcc_assert ((misalign & ~(align - 1)) == 0);
768 :
769 1686516 : pi->align = align;
770 1686516 : pi->misalign = misalign;
771 1686516 : }
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 37400047 : get_ptr_info (tree t)
795 : {
796 37400047 : struct ptr_info_def *pi;
797 :
798 37400047 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
799 :
800 37400047 : pi = SSA_NAME_PTR_INFO (t);
801 37400047 : if (pi == NULL)
802 : {
803 14702853 : pi = ggc_cleared_alloc<ptr_info_def> ();
804 14702853 : pt_solution_reset (&pi->pt);
805 14702853 : mark_ptr_info_alignment_unknown (pi);
806 14702853 : SSA_NAME_PTR_INFO (t) = pi;
807 : }
808 :
809 37400047 : 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 19225588 : copy_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
818 : {
819 19225588 : tree new_name;
820 :
821 19225588 : if (SSA_NAME_VAR (name))
822 12382356 : new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt);
823 : else
824 : {
825 6843232 : new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt);
826 13686464 : SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name));
827 : }
828 :
829 19225588 : 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 3049854 : duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
838 : {
839 3049854 : struct ptr_info_def *new_ptr_info;
840 :
841 3049854 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
842 3049854 : gcc_assert (!SSA_NAME_PTR_INFO (name));
843 :
844 3049854 : if (!ptr_info)
845 : return;
846 :
847 3049801 : new_ptr_info = ggc_alloc<ptr_info_def> ();
848 3049801 : *new_ptr_info = *ptr_info;
849 :
850 3049801 : SSA_NAME_PTR_INFO (name) = new_ptr_info;
851 : }
852 :
853 : void
854 8167214 : duplicate_ssa_name_range_info (tree name, tree src)
855 : {
856 8167214 : gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (src)));
857 8167214 : gcc_checking_assert (!range_info_p (name));
858 :
859 8167214 : if (range_info_p (src))
860 : {
861 8167214 : value_range src_range (TREE_TYPE (src));
862 8167214 : range_info_get_range (src, src_range);
863 8167214 : range_info_set_range (name, src_range);
864 8167214 : }
865 8167214 : }
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 52343062 : 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 52343062 : if (gimple_bb (SSA_NAME_DEF_STMT (src))
876 52343062 : != gimple_bb (SSA_NAME_DEF_STMT (dest)))
877 : return;
878 :
879 65303093 : if (POINTER_TYPE_P (TREE_TYPE (dest))
880 18101726 : && SSA_NAME_PTR_INFO (dest)
881 50072548 : && ! SSA_NAME_PTR_INFO (src))
882 424981 : duplicate_ssa_name_ptr_info (src, SSA_NAME_PTR_INFO (dest));
883 81139363 : else if (INTEGRAL_TYPE_P (TREE_TYPE (dest))
884 19478200 : && SSA_NAME_RANGE_INFO (dest)
885 41788936 : && ! SSA_NAME_RANGE_INFO (src))
886 88165 : 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 17558811 : duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt)
895 : {
896 17558811 : tree new_name = copy_ssa_name_fn (fn, name, stmt);
897 17558811 : if (POINTER_TYPE_P (TREE_TYPE (name)))
898 : {
899 2217192 : struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
900 :
901 2217192 : if (old_ptr_info)
902 1972500 : duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
903 : }
904 15341619 : else if (range_info_p (name))
905 4180044 : duplicate_ssa_name_range_info (new_name, name);
906 :
907 17558811 : 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 2050474 : reset_flow_sensitive_info (tree name)
916 : {
917 2050474 : if (POINTER_TYPE_P (TREE_TYPE (name)))
918 : {
919 : /* points-to info is not flow-sensitive. */
920 333002 : 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 330593 : mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
925 330593 : SSA_NAME_PTR_INFO (name)->pt.null = 1;
926 : }
927 : }
928 : else
929 1717472 : SSA_NAME_RANGE_INFO (name) = NULL;
930 2050474 : }
931 :
932 : /* Clear all flow sensitive data from all statements and PHI definitions
933 : in BB. */
934 :
935 : void
936 1385397 : reset_flow_sensitive_info_in_bb (basic_block bb)
937 : {
938 3943378 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
939 1172584 : gsi_next (&gsi))
940 : {
941 1172584 : gimple *stmt = gsi_stmt (gsi);
942 1172584 : ssa_op_iter i;
943 1172584 : tree op;
944 1422884 : FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
945 250300 : reset_flow_sensitive_info (op);
946 : }
947 :
948 1397191 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
949 11794 : gsi_next (&gsi))
950 : {
951 11794 : tree phi_def = gimple_phi_result (gsi.phi ());
952 11794 : reset_flow_sensitive_info (phi_def);
953 : }
954 1385397 : }
955 :
956 : /* Release all the SSA_NAMEs created by STMT. */
957 :
958 : void
959 73405679 : release_defs (gimple *stmt)
960 : {
961 73405679 : tree def;
962 73405679 : ssa_op_iter iter;
963 :
964 124600280 : FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
965 51194601 : if (TREE_CODE (def) == SSA_NAME)
966 50582216 : release_ssa_name (def);
967 73405679 : }
968 :
969 :
970 : /* Replace the symbol associated with SSA_NAME with SYM. */
971 :
972 : void
973 12406 : replace_ssa_name_symbol (tree ssa_name, tree sym)
974 : {
975 12406 : SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym);
976 12406 : TREE_TYPE (ssa_name) = TREE_TYPE (sym);
977 12406 : }
978 :
979 : /* Release the vector of free SSA_NAMEs and compact the vector of SSA_NAMEs
980 : that are live. */
981 :
982 : static void
983 2848395 : release_free_names_and_compact_live_names (function *fun)
984 : {
985 2848395 : unsigned i, j;
986 2848395 : int n = vec_safe_length (FREE_SSANAMES (fun));
987 :
988 : /* Now release the freelist. */
989 2848395 : vec_free (FREE_SSANAMES (fun));
990 :
991 : /* And compact the SSA number space. We make sure to not change the
992 : relative order of SSA versions. */
993 81778650 : for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
994 : {
995 78930255 : tree name = ssa_name (i);
996 78930255 : if (name)
997 : {
998 50212343 : if (i != j)
999 : {
1000 31199765 : SSA_NAME_VERSION (name) = j;
1001 31199765 : (*fun->gimple_df->ssa_names)[j] = name;
1002 : }
1003 50212343 : j++;
1004 : }
1005 : }
1006 2848395 : fun->gimple_df->ssa_names->truncate (j);
1007 :
1008 2848395 : statistics_counter_event (fun, "SSA names released", n);
1009 2848395 : statistics_counter_event (fun, "SSA name holes removed", i - j);
1010 2848395 : if (dump_file)
1011 270 : fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n",
1012 270 : n, n * 100.0 / num_ssa_names, i - j);
1013 2848395 : }
1014 :
1015 : /* Return SSA names that are unused to GGC memory and compact the SSA
1016 : version namespace. This is used to keep footprint of compiler during
1017 : interprocedural optimization. */
1018 :
1019 : namespace {
1020 :
1021 : const pass_data pass_data_release_ssa_names =
1022 : {
1023 : GIMPLE_PASS, /* type */
1024 : "release_ssa", /* name */
1025 : OPTGROUP_NONE, /* optinfo_flags */
1026 : TV_TREE_SSA_OTHER, /* tv_id */
1027 : PROP_ssa, /* properties_required */
1028 : 0, /* properties_provided */
1029 : 0, /* properties_destroyed */
1030 : TODO_remove_unused_locals, /* todo_flags_start */
1031 : 0, /* todo_flags_finish */
1032 : };
1033 :
1034 : class pass_release_ssa_names : public gimple_opt_pass
1035 : {
1036 : public:
1037 285722 : pass_release_ssa_names (gcc::context *ctxt)
1038 571444 : : gimple_opt_pass (pass_data_release_ssa_names, ctxt)
1039 : {}
1040 :
1041 : /* opt_pass methods: */
1042 : unsigned int execute (function *) final override;
1043 :
1044 : }; // class pass_release_ssa_names
1045 :
1046 : unsigned int
1047 2848395 : pass_release_ssa_names::execute (function *fun)
1048 : {
1049 2848395 : release_free_names_and_compact_live_names (fun);
1050 2848395 : return 0;
1051 : }
1052 :
1053 : } // anon namespace
1054 :
1055 : gimple_opt_pass *
1056 285722 : make_pass_release_ssa_names (gcc::context *ctxt)
1057 : {
1058 285722 : return new pass_release_ssa_names (ctxt);
1059 : }
1060 :
1061 : /* Save and restore of flow sensitive information. */
1062 :
1063 : /* Save off the flow sensitive info from NAME. */
1064 :
1065 : void
1066 1229137 : flow_sensitive_info_storage::save (tree name)
1067 : {
1068 1229137 : gcc_assert (state == 0);
1069 1229137 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
1070 : {
1071 1214865 : range_info = SSA_NAME_RANGE_INFO (name);
1072 1214865 : state = 1;
1073 1214865 : return;
1074 : }
1075 14272 : state = -1;
1076 14272 : auto ptr_info = SSA_NAME_PTR_INFO (name);
1077 14272 : if (ptr_info)
1078 : {
1079 13675 : align = ptr_info->align;
1080 13675 : misalign = ptr_info->misalign;
1081 13675 : null = SSA_NAME_PTR_INFO (name)->pt.null;
1082 : }
1083 : else
1084 : {
1085 597 : align = 0;
1086 597 : misalign = 0;
1087 597 : null = true;
1088 : }
1089 : }
1090 :
1091 : /* Restore the flow sensitive info from NAME. */
1092 :
1093 : void
1094 1229137 : flow_sensitive_info_storage::restore (tree name)
1095 : {
1096 1229137 : gcc_assert (state != 0);
1097 1229137 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
1098 : {
1099 1214865 : gcc_assert (state == 1);
1100 1214865 : SSA_NAME_RANGE_INFO (name) = range_info;
1101 1214865 : return;
1102 : }
1103 14272 : gcc_assert (state == -1);
1104 14272 : auto ptr_info = SSA_NAME_PTR_INFO (name);
1105 : /* If there was no flow sensitive info on the pointer
1106 : just return, there is nothing to restore to. */
1107 14272 : if (!ptr_info)
1108 : return;
1109 13675 : if (align != 0)
1110 309 : set_ptr_info_alignment (ptr_info, align, misalign);
1111 : else
1112 13366 : mark_ptr_info_alignment_unknown (ptr_info);
1113 13675 : SSA_NAME_PTR_INFO (name)->pt.null = null;
1114 : }
1115 :
1116 : /* Save off the flow sensitive info from NAME.
1117 : And reset the flow sensitive info of NAME. */
1118 :
1119 : void
1120 1229137 : flow_sensitive_info_storage::save_and_clear (tree name)
1121 : {
1122 1229137 : save (name);
1123 1229137 : reset_flow_sensitive_info (name);
1124 1229137 : }
1125 :
1126 : /* Clear the storage. */
1127 : void
1128 0 : flow_sensitive_info_storage::clear_storage (void)
1129 : {
1130 0 : state = 0;
1131 0 : }
|
