Line data Source code
1 : /* Generic routines for manipulating PHIs
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 "ssa.h"
27 : #include "fold-const.h"
28 : #include "gimple-iterator.h"
29 : #include "tree-ssa.h"
30 :
31 : /* Rewriting a function into SSA form can create a huge number of PHIs
32 : many of which may be thrown away shortly after their creation if jumps
33 : were threaded through PHI nodes.
34 :
35 : While our garbage collection mechanisms will handle this situation, it
36 : is extremely wasteful to create nodes and throw them away, especially
37 : when the nodes can be reused.
38 :
39 : For PR 8361, we can significantly reduce the number of nodes allocated
40 : and thus the total amount of memory allocated by managing PHIs a
41 : little. This additionally helps reduce the amount of work done by the
42 : garbage collector. Similar results have been seen on a wider variety
43 : of tests (such as the compiler itself).
44 :
45 : PHI nodes have different sizes, so we can't have a single list of all
46 : the PHI nodes as it would be too expensive to walk down that list to
47 : find a PHI of a suitable size.
48 :
49 : Instead we have an array of lists of free PHI nodes. The array is
50 : indexed by the number of PHI alternatives that PHI node can hold.
51 : Except for the last array member, which holds all remaining PHI
52 : nodes.
53 :
54 : So to find a free PHI node, we compute its index into the free PHI
55 : node array and see if there are any elements with an exact match.
56 : If so, then we are done. Otherwise, we test the next larger size
57 : up and continue until we are in the last array element.
58 :
59 : We do not actually walk members of the last array element. While it
60 : might allow us to pick up a few reusable PHI nodes, it could potentially
61 : be very expensive if the program has released a bunch of large PHI nodes,
62 : but keeps asking for even larger PHI nodes. Experiments have shown that
63 : walking the elements of the last array entry would result in finding less
64 : than .1% additional reusable PHI nodes.
65 :
66 : Note that we can never have less than two PHI argument slots. Thus,
67 : the -2 on all the calculations below. */
68 :
69 : #define NUM_BUCKETS 10
70 : static GTY ((deletable (""))) vec<gimple *, va_gc> *free_phinodes[NUM_BUCKETS - 2];
71 : static unsigned long free_phinode_count;
72 :
73 : static int ideal_phi_node_len (int);
74 :
75 : unsigned int phi_nodes_reused;
76 : unsigned int phi_nodes_created;
77 :
78 : /* Dump some simple statistics regarding the re-use of PHI nodes. */
79 :
80 : void
81 0 : phinodes_print_statistics (void)
82 : {
83 0 : fprintf (stderr, "%-32s" PRsa (11) "\n", "PHI nodes allocated:",
84 0 : SIZE_AMOUNT (phi_nodes_created));
85 0 : fprintf (stderr, "%-32s" PRsa (11) "\n", "PHI nodes reused:",
86 0 : SIZE_AMOUNT (phi_nodes_reused));
87 0 : }
88 :
89 : /* Allocate a PHI node with at least LEN arguments. If the free list
90 : happens to contain a PHI node with LEN arguments or more, return
91 : that one. */
92 :
93 : static inline gphi *
94 23816007 : allocate_phi_node (size_t len)
95 : {
96 23816007 : gphi *phi;
97 23816007 : size_t bucket = NUM_BUCKETS - 2;
98 23816007 : size_t size = sizeof (struct gphi)
99 23816007 : + (len - 1) * sizeof (struct phi_arg_d);
100 :
101 23816007 : if (free_phinode_count)
102 34691211 : for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
103 31354557 : if (free_phinodes[bucket])
104 : break;
105 :
106 : /* If our free list has an element, then use it. */
107 17172436 : if (bucket < NUM_BUCKETS - 2
108 17172436 : && gimple_phi_capacity ((*free_phinodes[bucket])[0]) >= len)
109 : {
110 13835782 : free_phinode_count--;
111 13835782 : phi = as_a <gphi *> (free_phinodes[bucket]->pop ());
112 13835782 : if (free_phinodes[bucket]->is_empty ())
113 534670 : vec_free (free_phinodes[bucket]);
114 : if (GATHER_STATISTICS)
115 : phi_nodes_reused++;
116 : }
117 : else
118 : {
119 9980225 : phi = static_cast <gphi *> (ggc_internal_alloc (size));
120 9980225 : if (GATHER_STATISTICS)
121 : {
122 : enum gimple_alloc_kind kind = gimple_alloc_kind (GIMPLE_PHI);
123 : phi_nodes_created++;
124 : gimple_alloc_counts[(int) kind]++;
125 : gimple_alloc_sizes[(int) kind] += size;
126 : }
127 : }
128 :
129 23816007 : return phi;
130 : }
131 :
132 : /* Given LEN, the original number of requested PHI arguments, return
133 : a new, "ideal" length for the PHI node. The "ideal" length rounds
134 : the total size of the PHI node up to the next power of two bytes.
135 :
136 : Rounding up will not result in wasting any memory since the size request
137 : will be rounded up by the GC system anyway. [ Note this is not entirely
138 : true since the original length might have fit on one of the special
139 : GC pages. ] By rounding up, we may avoid the need to reallocate the
140 : PHI node later if we increase the number of arguments for the PHI. */
141 :
142 : static int
143 53979166 : ideal_phi_node_len (int len)
144 : {
145 53979166 : size_t size, new_size;
146 53979166 : int log2, new_len;
147 :
148 : /* We do not support allocations of less than two PHI argument slots. */
149 53979166 : if (len < 2)
150 : len = 2;
151 :
152 : /* Compute the number of bytes of the original request. */
153 53979166 : size = sizeof (struct gphi)
154 53979166 : + (len - 1) * sizeof (struct phi_arg_d);
155 :
156 : /* Round it up to the next power of two. */
157 53979166 : log2 = ceil_log2 (size);
158 53979166 : new_size = 1 << log2;
159 :
160 : /* Now compute and return the number of PHI argument slots given an
161 : ideal size allocation. */
162 53979166 : new_len = len + (new_size - size) / sizeof (struct phi_arg_d);
163 53979166 : return new_len;
164 : }
165 :
166 : /* Return a PHI node with LEN argument slots for variable VAR. */
167 :
168 : static gphi *
169 23047198 : make_phi_node (tree var, int len)
170 : {
171 23047198 : gphi *phi;
172 23047198 : int capacity, i;
173 :
174 23047198 : capacity = ideal_phi_node_len (len);
175 :
176 23047198 : phi = allocate_phi_node (capacity);
177 :
178 : /* We need to clear the entire PHI node, including the argument
179 : portion, because we represent a "missing PHI argument" by placing
180 : NULL_TREE in PHI_ARG_DEF. */
181 23047198 : memset (phi, 0, (sizeof (struct gphi)
182 : - sizeof (struct phi_arg_d)
183 23047198 : + sizeof (struct phi_arg_d) * len));
184 23047198 : phi->code = GIMPLE_PHI;
185 23047198 : gimple_init_singleton (phi);
186 23047198 : phi->nargs = len;
187 23047198 : phi->capacity = capacity;
188 23047198 : if (!var)
189 : ;
190 13947359 : else if (TREE_CODE (var) == SSA_NAME)
191 7305998 : gimple_phi_set_result (phi, var);
192 : else
193 6641361 : gimple_phi_set_result (phi, make_ssa_name (var, phi));
194 :
195 61096035 : for (i = 0; i < len; i++)
196 : {
197 38048837 : use_operand_p imm;
198 :
199 38048837 : gimple_phi_arg_set_location (phi, i, UNKNOWN_LOCATION);
200 38048837 : imm = gimple_phi_arg_imm_use_ptr (phi, i);
201 38048837 : imm->use = gimple_phi_arg_def_ptr (phi, i);
202 38048837 : imm->prev = NULL;
203 38048837 : imm->next = NULL;
204 38048837 : imm->loc.stmt = phi;
205 : }
206 :
207 23047198 : return phi;
208 : }
209 :
210 : /* We no longer need PHI, release it so that it may be reused. */
211 :
212 : static void
213 19624420 : release_phi_node (gimple *phi)
214 : {
215 19624420 : size_t bucket;
216 19624420 : size_t len = gimple_phi_capacity (phi);
217 19624420 : size_t x;
218 :
219 47746621 : for (x = 0; x < gimple_phi_num_args (phi); x++)
220 : {
221 28122201 : use_operand_p imm;
222 28122201 : imm = gimple_phi_arg_imm_use_ptr (phi, x);
223 28122201 : delink_imm_use (imm);
224 : }
225 :
226 : /* Immediately return the memory to the allocator when we would
227 : only ever re-use it for a smaller size allocation. */
228 19624420 : if (len - 2 >= NUM_BUCKETS - 2)
229 : {
230 197023 : ggc_free (phi);
231 197023 : return;
232 : }
233 :
234 19427397 : bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
235 19427397 : bucket -= 2;
236 19427397 : vec_safe_push (free_phinodes[bucket], phi);
237 19427397 : free_phinode_count++;
238 : }
239 :
240 :
241 : /* Resize an existing PHI node. The only way is up. Return the
242 : possibly relocated phi. */
243 :
244 : static gphi *
245 768809 : resize_phi_node (gphi *phi, size_t len)
246 : {
247 768809 : size_t old_size, i;
248 768809 : gphi *new_phi;
249 :
250 768809 : gcc_assert (len > gimple_phi_capacity (phi));
251 :
252 : /* The garbage collector will not look at the PHI node beyond the
253 : first PHI_NUM_ARGS elements. Therefore, all we have to copy is a
254 : portion of the PHI node currently in use. */
255 768809 : old_size = sizeof (struct gphi)
256 768809 : + (gimple_phi_num_args (phi) - 1) * sizeof (struct phi_arg_d);
257 :
258 768809 : new_phi = allocate_phi_node (len);
259 :
260 768809 : memcpy (new_phi, phi, old_size);
261 768809 : memset ((char *)new_phi + old_size, 0,
262 : (sizeof (struct gphi)
263 : - sizeof (struct phi_arg_d)
264 768809 : + sizeof (struct phi_arg_d) * len) - old_size);
265 :
266 5525949 : for (i = 0; i < gimple_phi_num_args (new_phi); i++)
267 : {
268 4757140 : use_operand_p imm, old_imm;
269 4757140 : imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
270 4757140 : old_imm = gimple_phi_arg_imm_use_ptr (phi, i);
271 4757140 : imm->use = gimple_phi_arg_def_ptr (new_phi, i);
272 4757140 : relink_imm_use_stmt (imm, old_imm, new_phi);
273 : }
274 :
275 768809 : new_phi->capacity = len;
276 :
277 768809 : return new_phi;
278 : }
279 :
280 : /* Reserve PHI arguments for a new edge to basic block BB. */
281 :
282 : void
283 30931968 : reserve_phi_args_for_new_edge (basic_block bb)
284 : {
285 30931968 : size_t len = EDGE_COUNT (bb->preds);
286 30931968 : size_t cap = ideal_phi_node_len (len + 4);
287 30931968 : gphi_iterator gsi;
288 :
289 90331635 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
290 : {
291 59399667 : gphi *stmt = gsi.phi ();
292 :
293 59399667 : if (len > gimple_phi_capacity (stmt))
294 : {
295 768809 : gphi *new_phi = resize_phi_node (stmt, cap);
296 :
297 : /* The result of the PHI is defined by this PHI node. */
298 768809 : SSA_NAME_DEF_STMT (gimple_phi_result (new_phi)) = new_phi;
299 768809 : gsi_set_stmt (&gsi, new_phi);
300 :
301 768809 : release_phi_node (stmt);
302 768809 : stmt = new_phi;
303 : }
304 :
305 59399667 : stmt->nargs++;
306 :
307 : /* We represent a "missing PHI argument" by placing NULL_TREE in
308 : the corresponding slot. If PHI arguments were added
309 : immediately after an edge is created, this zeroing would not
310 : be necessary, but unfortunately this is not the case. For
311 : example, the loop optimizer duplicates several basic blocks,
312 : redirects edges, and then fixes up PHI arguments later in
313 : batch. */
314 59399667 : use_operand_p imm = gimple_phi_arg_imm_use_ptr (stmt, len - 1);
315 59399667 : imm->use = gimple_phi_arg_def_ptr (stmt, len - 1);
316 59399667 : imm->prev = NULL;
317 59399667 : imm->next = NULL;
318 59399667 : imm->loc.stmt = stmt;
319 59399667 : SET_PHI_ARG_DEF (stmt, len - 1, NULL_TREE);
320 59399667 : gimple_phi_arg_set_location (stmt, len - 1, UNKNOWN_LOCATION);
321 : }
322 30931968 : }
323 :
324 : /* Adds PHI to BB. */
325 :
326 : static void
327 23047198 : add_phi_node_to_bb (gphi *phi, basic_block bb)
328 : {
329 23047198 : gimple_seq seq = phi_nodes (bb);
330 : /* Add the new PHI node to the list of PHI nodes for block BB. */
331 23047198 : if (seq == NULL)
332 12837125 : set_phi_nodes (bb, gimple_seq_alloc_with_stmt (phi));
333 : else
334 : {
335 10210073 : gimple_seq_add_stmt (&seq, phi);
336 10210073 : gcc_assert (seq == phi_nodes (bb));
337 : }
338 :
339 : /* Associate BB to the PHI node. */
340 23047198 : gimple_set_bb (phi, bb);
341 23047198 : }
342 :
343 : /* Create a new PHI node for variable VAR at basic block BB. */
344 :
345 : gphi *
346 23047198 : create_phi_node (tree var, basic_block bb)
347 : {
348 40681068 : gphi *phi = make_phi_node (var, EDGE_COUNT (bb->preds));
349 :
350 23047198 : add_phi_node_to_bb (phi, bb);
351 23047198 : return phi;
352 : }
353 :
354 :
355 : /* Add a new argument to PHI node PHI. DEF is the incoming reaching
356 : definition and E is the edge through which DEF reaches PHI. The new
357 : argument is added at the end of the argument list.
358 : If PHI has reached its maximum capacity, add a few slots. In this case,
359 : PHI points to the reallocated phi node when we return. */
360 :
361 : void
362 41559018 : add_phi_arg (gphi *phi, tree def, edge e, location_t locus)
363 : {
364 41559018 : basic_block bb = e->dest;
365 :
366 41559018 : gcc_assert (bb == gimple_bb (phi));
367 :
368 : /* We resize PHI nodes upon edge creation. We should always have
369 : enough room at this point. */
370 41559018 : gcc_assert (gimple_phi_num_args (phi) <= gimple_phi_capacity (phi));
371 :
372 : /* We resize PHI nodes upon edge creation. We should always have
373 : enough room at this point. */
374 41559018 : gcc_assert (e->dest_idx < gimple_phi_num_args (phi));
375 :
376 : /* Copy propagation needs to know what object occur in abnormal
377 : PHI nodes. This is a convenient place to record such information. */
378 41559018 : if (e->flags & EDGE_ABNORMAL)
379 : {
380 205474 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
381 205474 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
382 : }
383 :
384 41559018 : SET_PHI_ARG_DEF (phi, e->dest_idx, def);
385 41559018 : gimple_phi_arg_set_location (phi, e->dest_idx, locus);
386 41559018 : }
387 :
388 :
389 : /* Remove the Ith argument from PHI's argument list. This routine
390 : implements removal by swapping the last alternative with the
391 : alternative we want to delete and then shrinking the vector, which
392 : is consistent with how we remove an edge from the edge vector. */
393 :
394 : static void
395 63893581 : remove_phi_arg_num (gphi *phi, int i)
396 : {
397 63893581 : int num_elem = gimple_phi_num_args (phi);
398 :
399 63893581 : gcc_assert (i < num_elem);
400 :
401 : /* Delink the item which is being removed. */
402 63893581 : delink_imm_use (gimple_phi_arg_imm_use_ptr (phi, i));
403 :
404 : /* If it is not the last element, move the last element
405 : to the element we want to delete, resetting all the links. */
406 63893581 : if (i != num_elem - 1)
407 : {
408 55168708 : use_operand_p old_p, new_p;
409 55168708 : old_p = gimple_phi_arg_imm_use_ptr (phi, num_elem - 1);
410 55168708 : new_p = gimple_phi_arg_imm_use_ptr (phi, i);
411 : /* Set use on new node, and link into last element's place. */
412 55168708 : *(new_p->use) = *(old_p->use);
413 55168708 : relink_imm_use (new_p, old_p);
414 : /* Move the location as well. */
415 55168708 : gimple_phi_arg_set_location (phi, i,
416 : gimple_phi_arg_location (phi, num_elem - 1));
417 : }
418 :
419 : /* Shrink the vector and return. Note that we do not have to clear
420 : PHI_ARG_DEF because the garbage collector will not look at those
421 : elements beyond the first PHI_NUM_ARGS elements of the array. */
422 63893581 : phi->nargs--;
423 63893581 : }
424 :
425 :
426 : /* Remove all PHI arguments associated with edge E. */
427 :
428 : void
429 35238932 : remove_phi_args (edge e)
430 : {
431 35238932 : gphi_iterator gsi;
432 :
433 99132513 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
434 63893581 : remove_phi_arg_num (gsi.phi (),
435 63893581 : e->dest_idx);
436 35238932 : }
437 :
438 :
439 : /* Remove the PHI node pointed-to by iterator GSI from basic block BB. After
440 : removal, iterator GSI is updated to point to the next PHI node in the
441 : sequence. If RELEASE_LHS_P is true, the LHS of this PHI node is released
442 : into the free pool of SSA names. */
443 :
444 : void
445 18855611 : remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p)
446 : {
447 18855611 : gimple *phi = gsi_stmt (*gsi);
448 :
449 18855611 : if (release_lhs_p)
450 18698668 : insert_debug_temps_for_defs (gsi);
451 :
452 18855611 : gsi_remove (gsi, false);
453 :
454 : /* If we are deleting the PHI node, then we should release the
455 : SSA_NAME node so that it can be reused. */
456 18855611 : if (release_lhs_p)
457 18698668 : release_ssa_name (gimple_phi_result (phi));
458 18855611 : release_phi_node (phi);
459 18855611 : }
460 :
461 : /* Remove all the phi nodes from BB. */
462 :
463 : void
464 36217358 : remove_phi_nodes (basic_block bb)
465 : {
466 36217358 : gphi_iterator gsi;
467 :
468 39717104 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
469 3499746 : remove_phi_node (&gsi, true);
470 :
471 36217358 : set_phi_nodes (bb, NULL);
472 36217358 : }
473 :
474 : /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
475 : NULL. */
476 :
477 : tree
478 4370793 : degenerate_phi_result (gphi *phi)
479 : {
480 4370793 : tree lhs = gimple_phi_result (phi);
481 4370793 : tree val = NULL;
482 4370793 : size_t i;
483 :
484 : /* Ignoring arguments which are the same as LHS, if all the remaining
485 : arguments are the same, then the PHI is a degenerate and has the
486 : value of that common argument. */
487 8912367 : for (i = 0; i < gimple_phi_num_args (phi); i++)
488 : {
489 8535410 : tree arg = gimple_phi_arg_def (phi, i);
490 :
491 8535410 : if (arg == lhs)
492 48386 : continue;
493 8487024 : else if (!arg)
494 : break;
495 8487024 : else if (!val)
496 : val = arg;
497 4138974 : else if (arg == val)
498 143861 : continue;
499 : /* We bring in some of operand_equal_p not only to speed things
500 : up, but also to avoid crashing when dereferencing the type of
501 : a released SSA name. */
502 3995113 : else if (TREE_CODE (val) != TREE_CODE (arg)
503 1746663 : || TREE_CODE (val) == SSA_NAME
504 4064153 : || !operand_equal_p (arg, val, 0))
505 : break;
506 : }
507 4370793 : return (i == gimple_phi_num_args (phi) ? val : NULL);
508 : }
509 :
510 : /* Set PHI nodes of a basic block BB to SEQ. */
511 :
512 : void
513 74484676 : set_phi_nodes (basic_block bb, gimple_seq seq)
514 : {
515 74484676 : gimple_stmt_iterator i;
516 :
517 74484676 : gcc_checking_assert (!(bb->flags & BB_RTL));
518 74484676 : bb->il.gimple.phi_nodes = seq;
519 74484676 : if (seq)
520 25674250 : for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
521 12837125 : gimple_set_bb (gsi_stmt (i), bb);
522 74484676 : }
523 :
524 : #include "gt-tree-phinodes.h"
|
