1 | /* Generic routines for manipulating SSA_NAME expressions |
2 | Copyright (C) 2003-2023 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 | range_info_p (const_tree name) |
79 | { |
80 | 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 | range_info_fits_p (tree name, const vrange &r) |
87 | { |
88 | gcc_checking_assert (range_info_p (name)); |
89 | vrange_storage *mem = SSA_NAME_RANGE_INFO (name); |
90 | 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 | range_info_alloc (tree name, const vrange &r) |
98 | { |
99 | vrange_storage *mem = ggc_alloc_vrange_storage (r); |
100 | SSA_NAME_RANGE_INFO (name) = mem; |
101 | return mem; |
102 | } |
103 | |
104 | /* Free storage allocated for the global range for NAME. */ |
105 | |
106 | inline void |
107 | range_info_free (tree name) |
108 | { |
109 | vrange_storage *mem = SSA_NAME_RANGE_INFO (name); |
110 | ggc_free (mem); |
111 | } |
112 | |
113 | /* Return the global range for NAME in R. */ |
114 | |
115 | inline void |
116 | range_info_get_range (const_tree name, vrange &r) |
117 | { |
118 | SSA_NAME_RANGE_INFO (name)->get_vrange (r, TREE_TYPE (name)); |
119 | } |
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 | range_info_set_range (tree name, const vrange &r) |
126 | { |
127 | if (!range_info_p (name) || !range_info_fits_p (name, r)) |
128 | { |
129 | if (range_info_p (name)) |
130 | range_info_free (name); |
131 | |
132 | return range_info_alloc (name, r); |
133 | } |
134 | else |
135 | { |
136 | SSA_NAME_RANGE_INFO (name)->set_vrange (r); |
137 | 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 | init_ssanames (struct function *fn, int size) |
146 | { |
147 | if (!size) |
148 | vec_alloc (SSANAMES (fn), nelems: 50); |
149 | else |
150 | vec_safe_reserve (SSANAMES (fn), nelems: size, exact: 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 | SSANAMES (fn)->quick_push (NULL_TREE); |
160 | FREE_SSANAMES (fn) = NULL; |
161 | FREE_SSANAMES_QUEUE (fn) = NULL; |
162 | |
163 | fn->gimple_df->ssa_renaming_needed = 0; |
164 | fn->gimple_df->rename_vops = 0; |
165 | } |
166 | |
167 | /* Finalize management of SSA_NAMEs. */ |
168 | |
169 | void |
170 | fini_ssanames (struct function *fn) |
171 | { |
172 | unsigned i; |
173 | 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 | FOR_EACH_VEC_SAFE_ELT (SSANAMES (fn), i, name) |
178 | if (name) |
179 | SSA_NAME_DEF_STMT (name) = NULL; |
180 | vec_free (SSANAMES (fn)); |
181 | vec_free (FREE_SSANAMES (fn)); |
182 | vec_free (FREE_SSANAMES_QUEUE (fn)); |
183 | } |
184 | |
185 | /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */ |
186 | |
187 | void |
188 | ssanames_print_statistics (void) |
189 | { |
190 | fprintf (stderr, format: "%-32s" PRsa (11) "\n" , "SSA_NAME nodes allocated:" , |
191 | SIZE_AMOUNT (ssa_name_nodes_created)); |
192 | fprintf (stderr, format: "%-32s" PRsa (11) "\n" , "SSA_NAME nodes reused:" , |
193 | SIZE_AMOUNT (ssa_name_nodes_reused)); |
194 | } |
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 | verify_ssaname_freelists (struct function *fun) |
205 | { |
206 | if (!gimple_in_ssa_p (fun)) |
207 | return; |
208 | |
209 | auto_bitmap names_in_il; |
210 | |
211 | /* Walk the entire IL noting every SSA_NAME we see. */ |
212 | basic_block bb; |
213 | FOR_EACH_BB_FN (bb, fun) |
214 | { |
215 | tree t; |
216 | /* First note the result and arguments of PHI nodes. */ |
217 | for (gphi_iterator gsi = gsi_start_phis (bb); |
218 | !gsi_end_p (i: gsi); |
219 | gsi_next (i: &gsi)) |
220 | { |
221 | gphi *phi = gsi.phi (); |
222 | t = gimple_phi_result (gs: phi); |
223 | bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t)); |
224 | |
225 | for (unsigned int i = 0; i < gimple_phi_num_args (gs: phi); i++) |
226 | { |
227 | t = gimple_phi_arg_def (gs: phi, index: i); |
228 | if (TREE_CODE (t) == SSA_NAME) |
229 | bitmap_set_bit (names_in_il, SSA_NAME_VERSION (t)); |
230 | } |
231 | } |
232 | |
233 | /* Then note the operands of each statement. */ |
234 | for (gimple_stmt_iterator gsi = gsi_start_bb (bb); |
235 | !gsi_end_p (i: gsi); |
236 | gsi_next (i: &gsi)) |
237 | { |
238 | ssa_op_iter iter; |
239 | gimple *stmt = gsi_stmt (i: gsi); |
240 | FOR_EACH_SSA_TREE_OPERAND (t, stmt, iter, SSA_OP_ALL_OPERANDS) |
241 | 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 | auto_bitmap names_in_freelists; |
248 | if (FREE_SSANAMES (fun)) |
249 | { |
250 | for (unsigned int i = 0; i < FREE_SSANAMES (fun)->length (); i++) |
251 | { |
252 | tree t = (*FREE_SSANAMES (fun))[i]; |
253 | |
254 | /* Verify that the name is marked as being in the free list. */ |
255 | 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 | gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t))); |
260 | bitmap_set_bit (names_in_freelists, SSA_NAME_VERSION (t)); |
261 | } |
262 | } |
263 | |
264 | /* Similarly for the names in the pending free list. */ |
265 | if (FREE_SSANAMES_QUEUE (fun)) |
266 | { |
267 | for (unsigned int i = 0; i < FREE_SSANAMES_QUEUE (fun)->length (); i++) |
268 | { |
269 | tree t = (*FREE_SSANAMES_QUEUE (fun))[i]; |
270 | |
271 | /* Verify that the name is marked as being in the free list. */ |
272 | 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 | gcc_assert (!bitmap_bit_p (names_in_freelists, SSA_NAME_VERSION (t))); |
277 | 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 | bool intersect_p = bitmap_intersect_p (names_in_il, names_in_freelists); |
284 | 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 | if (names_to_release) |
289 | 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 | for (unsigned int i = UNUSED_NAME_VERSION + 1; i < num_ssa_names; i++) |
298 | if (ssa_name (i) && SSA_NAME_IS_DEFAULT_DEF (ssa_name (i))) |
299 | bitmap_set_bit (names_in_il, i); |
300 | |
301 | unsigned int i; |
302 | bitmap_iterator bi; |
303 | auto_bitmap all_names; |
304 | bitmap_set_range (all_names, UNUSED_NAME_VERSION + 1, num_ssa_names - 1); |
305 | 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 | EXECUTE_IF_AND_COMPL_IN_BITMAP(all_names, names_in_il, |
310 | UNUSED_NAME_VERSION + 1, i, bi) |
311 | gcc_assert (!ssa_name (i)); |
312 | } |
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 | flush_ssaname_freelist (void) |
322 | { |
323 | /* If there were any SSA names released reset the SCEV cache. */ |
324 | if (! vec_safe_is_empty (FREE_SSANAMES_QUEUE (cfun))) |
325 | scev_reset_htab (); |
326 | vec_safe_splice (FREE_SSANAMES (cfun), FREE_SSANAMES_QUEUE (cfun)); |
327 | vec_safe_truncate (FREE_SSANAMES_QUEUE (cfun), size: 0); |
328 | } |
329 | |
330 | /* Initialize SSA_NAME_IMM_USE_NODE of a SSA NAME. */ |
331 | |
332 | void |
333 | init_ssa_name_imm_use (tree name) |
334 | { |
335 | use_operand_p imm; |
336 | imm = &(SSA_NAME_IMM_USE_NODE (name)); |
337 | imm->use = NULL; |
338 | imm->prev = imm; |
339 | imm->next = imm; |
340 | imm->loc.ssa_name = name; |
341 | } |
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 | make_ssa_name_fn (struct function *fn, tree var, gimple *stmt, |
351 | unsigned int version) |
352 | { |
353 | tree t; |
354 | 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 | if (version != 0) |
361 | { |
362 | t = make_node (SSA_NAME); |
363 | SSA_NAME_VERSION (t) = version; |
364 | if (version >= SSANAMES (fn)->length ()) |
365 | vec_safe_grow_cleared (SSANAMES (fn), len: version + 1, exact: true); |
366 | gcc_assert ((*SSANAMES (fn))[version] == NULL); |
367 | (*SSANAMES (fn))[version] = t; |
368 | ssa_name_nodes_created++; |
369 | } |
370 | /* If our free list has an element, then use it. */ |
371 | else if (!vec_safe_is_empty (FREE_SSANAMES (fn))) |
372 | { |
373 | t = FREE_SSANAMES (fn)->pop (); |
374 | 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 | gcc_assert ((*SSANAMES (fn))[SSA_NAME_VERSION (t)] == NULL); |
379 | (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t; |
380 | } |
381 | else |
382 | { |
383 | t = make_node (SSA_NAME); |
384 | SSA_NAME_VERSION (t) = SSANAMES (fn)->length (); |
385 | vec_safe_push (SSANAMES (fn), obj: t); |
386 | ssa_name_nodes_created++; |
387 | } |
388 | |
389 | if (TYPE_P (var)) |
390 | { |
391 | TREE_TYPE (t) = TYPE_MAIN_VARIANT (var); |
392 | SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE); |
393 | } |
394 | else |
395 | { |
396 | TREE_TYPE (t) = TREE_TYPE (var); |
397 | SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var); |
398 | } |
399 | SSA_NAME_DEF_STMT (t) = stmt; |
400 | if (POINTER_TYPE_P (TREE_TYPE (t))) |
401 | SSA_NAME_PTR_INFO (t) = NULL; |
402 | else |
403 | SSA_NAME_RANGE_INFO (t) = NULL; |
404 | |
405 | SSA_NAME_IN_FREE_LIST (t) = 0; |
406 | SSA_NAME_IS_DEFAULT_DEF (t) = 0; |
407 | init_ssa_name_imm_use (name: t); |
408 | |
409 | 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 | set_range_info (tree name, const vrange &r) |
417 | { |
418 | if (r.undefined_p () || r.varying_p ()) |
419 | return false; |
420 | |
421 | // Pick up the current range, or VARYING if none. |
422 | tree type = TREE_TYPE (name); |
423 | if (POINTER_TYPE_P (type)) |
424 | { |
425 | struct ptr_info_def *pi = get_ptr_info (name); |
426 | // If R is nonnull and pi is not, set nonnull. |
427 | if (r.nonzero_p () && (!pi || pi->pt.null)) |
428 | { |
429 | set_ptr_nonnull (name); |
430 | return true; |
431 | } |
432 | return false; |
433 | } |
434 | |
435 | Value_Range tmp (type); |
436 | if (range_info_p (name)) |
437 | range_info_get_range (name, r&: tmp); |
438 | else |
439 | tmp.set_varying (type); |
440 | // If the result doesn't change, or is undefined, return false. |
441 | if (!tmp.intersect (r) || tmp.undefined_p ()) |
442 | return false; |
443 | |
444 | return range_info_set_range (name, r: tmp); |
445 | } |
446 | |
447 | /* Set nonnull attribute to pointer NAME. */ |
448 | |
449 | void |
450 | set_ptr_nonnull (tree name) |
451 | { |
452 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); |
453 | struct ptr_info_def *pi = get_ptr_info (name); |
454 | pi->pt.null = 0; |
455 | } |
456 | |
457 | /* Update the non-zero bits bitmask of NAME. */ |
458 | |
459 | void |
460 | set_nonzero_bits (tree name, const wide_int &mask) |
461 | { |
462 | gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); |
463 | |
464 | int_range<2> r (TREE_TYPE (name)); |
465 | r.set_nonzero_bits (mask); |
466 | set_range_info (name, r); |
467 | } |
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 | set_bitmask (tree name, const wide_int &value, const wide_int &mask) |
476 | { |
477 | gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); |
478 | |
479 | int_range<2> r (TREE_TYPE (name)); |
480 | r.update_bitmask (irange_bitmask (value, mask)); |
481 | set_range_info (name, r); |
482 | } |
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 | get_nonzero_bits (const_tree name) |
489 | { |
490 | if (TREE_CODE (name) == INTEGER_CST) |
491 | return wi::to_wide (t: name); |
492 | |
493 | /* Use element_precision instead of TYPE_PRECISION so complex and |
494 | vector types get a non-zero precision. */ |
495 | unsigned int precision = element_precision (TREE_TYPE (name)); |
496 | if (POINTER_TYPE_P (TREE_TYPE (name))) |
497 | { |
498 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); |
499 | if (pi && pi->align) |
500 | return wi::shwi (val: -(HOST_WIDE_INT) pi->align |
501 | | (HOST_WIDE_INT) pi->misalign, precision); |
502 | return wi::shwi (val: -1, precision); |
503 | } |
504 | |
505 | if (!range_info_p (name) || !irange::supports_p (TREE_TYPE (name))) |
506 | return wi::shwi (val: -1, precision); |
507 | |
508 | int_range_max tmp; |
509 | range_info_get_range (name, r&: tmp); |
510 | return tmp.get_nonzero_bits (); |
511 | } |
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 | ssa_name_has_boolean_range (tree op) |
522 | { |
523 | gcc_assert (TREE_CODE (op) == SSA_NAME); |
524 | |
525 | /* An integral type with a single bit of precision. */ |
526 | if (INTEGRAL_TYPE_P (TREE_TYPE (op)) |
527 | && TYPE_UNSIGNED (TREE_TYPE (op)) |
528 | && 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 | if (INTEGRAL_TYPE_P (TREE_TYPE (op)) |
535 | && (TYPE_PRECISION (TREE_TYPE (op)) > 1)) |
536 | { |
537 | int_range<2> r; |
538 | if (get_range_query (cfun)->range_of_expr (r, expr: op) |
539 | && r == range_true_and_false (TREE_TYPE (op))) |
540 | return true; |
541 | |
542 | if (wi::eq_p (x: get_nonzero_bits (name: op), y: 1)) |
543 | return true; |
544 | } |
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 | release_ssa_name_fn (struct function *fn, tree var) |
559 | { |
560 | 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 | 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 | if (name_registered_for_update_p (var)) |
571 | { |
572 | release_ssa_name_after_update_ssa (var); |
573 | 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 | if (! SSA_NAME_IN_FREE_LIST (var)) |
584 | { |
585 | int saved_ssa_name_version = SSA_NAME_VERSION (var); |
586 | use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var)); |
587 | |
588 | if (MAY_HAVE_DEBUG_BIND_STMTS) |
589 | insert_debug_temp_for_var_def (NULL, var); |
590 | |
591 | if (flag_checking) |
592 | verify_imm_links (stderr, var); |
593 | while (imm->next != imm) |
594 | delink_imm_use (linknode: imm->next); |
595 | |
596 | (*SSANAMES (fn))[SSA_NAME_VERSION (var)] = NULL_TREE; |
597 | memset (s: var, c: 0, n: tree_size (var)); |
598 | |
599 | imm->prev = imm; |
600 | imm->next = imm; |
601 | 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 | TREE_SET_CODE (var, SSA_NAME); |
606 | |
607 | /* Restore the version number. */ |
608 | SSA_NAME_VERSION (var) = saved_ssa_name_version; |
609 | |
610 | /* Note this SSA_NAME is now in the first list. */ |
611 | 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 | TREE_TYPE (var) = error_mark_node; |
617 | |
618 | /* And finally queue it so that it will be put on the free list. */ |
619 | vec_safe_push (FREE_SSANAMES_QUEUE (fn), obj: 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 | get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp, |
629 | unsigned int *misalignp) |
630 | { |
631 | if (pi->align) |
632 | { |
633 | *alignp = pi->align; |
634 | *misalignp = pi->misalign; |
635 | 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 | mark_ptr_info_alignment_unknown (struct ptr_info_def *pi) |
645 | { |
646 | pi->align = 0; |
647 | pi->misalign = 0; |
648 | } |
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 | set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align, |
656 | unsigned int misalign) |
657 | { |
658 | gcc_checking_assert (align != 0); |
659 | gcc_assert ((align & (align - 1)) == 0); |
660 | gcc_assert ((misalign & ~(align - 1)) == 0); |
661 | |
662 | pi->align = align; |
663 | pi->misalign = misalign; |
664 | } |
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 | adjust_ptr_info_misalignment (struct ptr_info_def *pi, poly_uint64 increment) |
671 | { |
672 | if (pi->align != 0) |
673 | { |
674 | increment += pi->misalign; |
675 | if (!known_misalignment (value: increment, align: pi->align, misalign: &pi->misalign)) |
676 | { |
677 | pi->align = known_alignment (a: increment); |
678 | pi->misalign = 0; |
679 | } |
680 | } |
681 | } |
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 | get_ptr_info (tree t) |
688 | { |
689 | struct ptr_info_def *pi; |
690 | |
691 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); |
692 | |
693 | pi = SSA_NAME_PTR_INFO (t); |
694 | if (pi == NULL) |
695 | { |
696 | pi = ggc_cleared_alloc<ptr_info_def> (); |
697 | pt_solution_reset (&pi->pt); |
698 | mark_ptr_info_alignment_unknown (pi); |
699 | SSA_NAME_PTR_INFO (t) = pi; |
700 | } |
701 | |
702 | 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 | copy_ssa_name_fn (struct function *fn, tree name, gimple *stmt) |
711 | { |
712 | tree new_name; |
713 | |
714 | if (SSA_NAME_VAR (name)) |
715 | new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt); |
716 | else |
717 | { |
718 | new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt); |
719 | SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name)); |
720 | } |
721 | |
722 | 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 | duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) |
731 | { |
732 | struct ptr_info_def *new_ptr_info; |
733 | |
734 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); |
735 | gcc_assert (!SSA_NAME_PTR_INFO (name)); |
736 | |
737 | if (!ptr_info) |
738 | return; |
739 | |
740 | new_ptr_info = ggc_alloc<ptr_info_def> (); |
741 | *new_ptr_info = *ptr_info; |
742 | |
743 | SSA_NAME_PTR_INFO (name) = new_ptr_info; |
744 | } |
745 | |
746 | void |
747 | duplicate_ssa_name_range_info (tree name, tree src) |
748 | { |
749 | gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (src))); |
750 | gcc_checking_assert (!range_info_p (name)); |
751 | |
752 | if (range_info_p (name: src)) |
753 | { |
754 | Value_Range src_range (TREE_TYPE (src)); |
755 | range_info_get_range (name: src, r&: src_range); |
756 | range_info_set_range (name, r: src_range); |
757 | } |
758 | } |
759 | |
760 | |
761 | /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT |
762 | in function FN. */ |
763 | |
764 | tree |
765 | duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt) |
766 | { |
767 | tree new_name = copy_ssa_name_fn (fn, name, stmt); |
768 | if (POINTER_TYPE_P (TREE_TYPE (name))) |
769 | { |
770 | struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); |
771 | |
772 | if (old_ptr_info) |
773 | duplicate_ssa_name_ptr_info (name: new_name, ptr_info: old_ptr_info); |
774 | } |
775 | else if (range_info_p (name)) |
776 | duplicate_ssa_name_range_info (name: new_name, src: name); |
777 | |
778 | 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 | reset_flow_sensitive_info (tree name) |
787 | { |
788 | if (POINTER_TYPE_P (TREE_TYPE (name))) |
789 | { |
790 | /* points-to info is not flow-sensitive. */ |
791 | 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 | mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name)); |
796 | SSA_NAME_PTR_INFO (name)->pt.null = 1; |
797 | } |
798 | } |
799 | else |
800 | SSA_NAME_RANGE_INFO (name) = NULL; |
801 | } |
802 | |
803 | /* Clear all flow sensitive data from all statements and PHI definitions |
804 | in BB. */ |
805 | |
806 | void |
807 | reset_flow_sensitive_info_in_bb (basic_block bb) |
808 | { |
809 | for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); |
810 | gsi_next (i: &gsi)) |
811 | { |
812 | gimple *stmt = gsi_stmt (i: gsi); |
813 | ssa_op_iter i; |
814 | tree op; |
815 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF) |
816 | reset_flow_sensitive_info (name: op); |
817 | } |
818 | |
819 | for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi); |
820 | gsi_next (i: &gsi)) |
821 | { |
822 | tree phi_def = gimple_phi_result (gs: gsi.phi ()); |
823 | reset_flow_sensitive_info (name: phi_def); |
824 | } |
825 | } |
826 | |
827 | /* Release all the SSA_NAMEs created by STMT. */ |
828 | |
829 | void |
830 | release_defs (gimple *stmt) |
831 | { |
832 | tree def; |
833 | ssa_op_iter iter; |
834 | |
835 | FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) |
836 | if (TREE_CODE (def) == SSA_NAME) |
837 | release_ssa_name (name: def); |
838 | } |
839 | |
840 | |
841 | /* Replace the symbol associated with SSA_NAME with SYM. */ |
842 | |
843 | void |
844 | replace_ssa_name_symbol (tree ssa_name, tree sym) |
845 | { |
846 | SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym); |
847 | TREE_TYPE (ssa_name) = TREE_TYPE (sym); |
848 | } |
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 | release_free_names_and_compact_live_names (function *fun) |
855 | { |
856 | unsigned i, j; |
857 | int n = vec_safe_length (FREE_SSANAMES (fun)); |
858 | |
859 | /* Now release the freelist. */ |
860 | 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 | for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i) |
865 | { |
866 | tree name = ssa_name (i); |
867 | if (name) |
868 | { |
869 | if (i != j) |
870 | { |
871 | SSA_NAME_VERSION (name) = j; |
872 | (*fun->gimple_df->ssa_names)[j] = name; |
873 | } |
874 | j++; |
875 | } |
876 | } |
877 | fun->gimple_df->ssa_names->truncate (size: j); |
878 | |
879 | statistics_counter_event (fun, "SSA names released" , n); |
880 | statistics_counter_event (fun, "SSA name holes removed" , i - j); |
881 | if (dump_file) |
882 | fprintf (stream: dump_file, format: "Released %i names, %.2f%%, removed %i holes\n" , |
883 | n, n * 100.0 / num_ssa_names, i - j); |
884 | } |
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 | .type: GIMPLE_PASS, /* type */ |
895 | .name: "release_ssa" , /* name */ |
896 | .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */ |
897 | .tv_id: TV_TREE_SSA_OTHER, /* tv_id */ |
898 | PROP_ssa, /* properties_required */ |
899 | .properties_provided: 0, /* properties_provided */ |
900 | .properties_destroyed: 0, /* properties_destroyed */ |
901 | TODO_remove_unused_locals, /* todo_flags_start */ |
902 | .todo_flags_finish: 0, /* todo_flags_finish */ |
903 | }; |
904 | |
905 | class pass_release_ssa_names : public gimple_opt_pass |
906 | { |
907 | public: |
908 | pass_release_ssa_names (gcc::context *ctxt) |
909 | : 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 | pass_release_ssa_names::execute (function *fun) |
919 | { |
920 | release_free_names_and_compact_live_names (fun); |
921 | return 0; |
922 | } |
923 | |
924 | } // anon namespace |
925 | |
926 | gimple_opt_pass * |
927 | make_pass_release_ssa_names (gcc::context *ctxt) |
928 | { |
929 | 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 | flow_sensitive_info_storage::save (tree name) |
938 | { |
939 | gcc_assert (state == 0); |
940 | if (!POINTER_TYPE_P (TREE_TYPE (name))) |
941 | { |
942 | range_info = SSA_NAME_RANGE_INFO (name); |
943 | state = 1; |
944 | return; |
945 | } |
946 | state = -1; |
947 | auto ptr_info = SSA_NAME_PTR_INFO (name); |
948 | if (ptr_info) |
949 | { |
950 | align = ptr_info->align; |
951 | misalign = ptr_info->misalign; |
952 | null = SSA_NAME_PTR_INFO (name)->pt.null; |
953 | } |
954 | else |
955 | { |
956 | align = 0; |
957 | misalign = 0; |
958 | null = true; |
959 | } |
960 | } |
961 | |
962 | /* Restore the flow sensitive info from NAME. */ |
963 | |
964 | void |
965 | flow_sensitive_info_storage::restore (tree name) |
966 | { |
967 | gcc_assert (state != 0); |
968 | if (!POINTER_TYPE_P (TREE_TYPE (name))) |
969 | { |
970 | gcc_assert (state == 1); |
971 | SSA_NAME_RANGE_INFO (name) = range_info; |
972 | return; |
973 | } |
974 | gcc_assert (state == -1); |
975 | 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 | if (!ptr_info) |
979 | return; |
980 | if (align != 0) |
981 | set_ptr_info_alignment (pi: ptr_info, align, misalign); |
982 | else |
983 | mark_ptr_info_alignment_unknown (pi: ptr_info); |
984 | 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 | flow_sensitive_info_storage::save_and_clear (tree name) |
992 | { |
993 | save (name); |
994 | reset_flow_sensitive_info (name); |
995 | } |
996 | |
997 | /* Clear the storage. */ |
998 | void |
999 | flow_sensitive_info_storage::clear_storage (void) |
1000 | { |
1001 | state = 0; |
1002 | } |
1003 | |