Branch data Line data Source code
1 : : /* Generic routines for manipulating PHIs
2 : : Copyright (C) 2003-2024 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify
7 : : it under the terms of the GNU General Public License as published by
8 : : the Free Software Foundation; either version 3, or (at your option)
9 : : any later version.
10 : :
11 : : GCC is distributed in the hope that it will be useful,
12 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : : GNU General Public License for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "backend.h"
24 : : #include "tree.h"
25 : : #include "gimple.h"
26 : : #include "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 : 22555275 : allocate_phi_node (size_t len)
95 : : {
96 : 22555275 : gphi *phi;
97 : 22555275 : size_t bucket = NUM_BUCKETS - 2;
98 : 22555275 : size_t size = sizeof (struct gphi)
99 : 22555275 : + (len - 1) * sizeof (struct phi_arg_d);
100 : :
101 : 22555275 : if (free_phinode_count)
102 : 32323021 : for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
103 : 29295603 : if (free_phinodes[bucket])
104 : : break;
105 : :
106 : : /* If our free list has an element, then use it. */
107 : 16084185 : if (bucket < NUM_BUCKETS - 2
108 : 16084185 : && gimple_phi_capacity ((*free_phinodes[bucket])[0]) >= len)
109 : : {
110 : 13056767 : free_phinode_count--;
111 : 13056767 : phi = as_a <gphi *> (free_phinodes[bucket]->pop ());
112 : 13056767 : if (free_phinodes[bucket]->is_empty ())
113 : 582803 : vec_free (free_phinodes[bucket]);
114 : : if (GATHER_STATISTICS)
115 : : phi_nodes_reused++;
116 : : }
117 : : else
118 : : {
119 : 9498508 : phi = static_cast <gphi *> (ggc_internal_alloc (size));
120 : 9498508 : 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 : 22555275 : 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 : 51743670 : ideal_phi_node_len (int len)
144 : : {
145 : 51743670 : size_t size, new_size;
146 : 51743670 : int log2, new_len;
147 : :
148 : : /* We do not support allocations of less than two PHI argument slots. */
149 : 51743670 : if (len < 2)
150 : : len = 2;
151 : :
152 : : /* Compute the number of bytes of the original request. */
153 : 51743670 : size = sizeof (struct gphi)
154 : 51743670 : + (len - 1) * sizeof (struct phi_arg_d);
155 : :
156 : : /* Round it up to the next power of two. */
157 : 51743670 : log2 = ceil_log2 (size);
158 : 51743670 : new_size = 1 << log2;
159 : :
160 : : /* Now compute and return the number of PHI argument slots given an
161 : : ideal size allocation. */
162 : 51743670 : new_len = len + (new_size - size) / sizeof (struct phi_arg_d);
163 : 51743670 : return new_len;
164 : : }
165 : :
166 : : /* Return a PHI node with LEN argument slots for variable VAR. */
167 : :
168 : : static gphi *
169 : 21907878 : make_phi_node (tree var, int len)
170 : : {
171 : 21907878 : gphi *phi;
172 : 21907878 : int capacity, i;
173 : :
174 : 21907878 : capacity = ideal_phi_node_len (len);
175 : :
176 : 21907878 : 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 : 21907878 : memset (phi, 0, (sizeof (struct gphi)
182 : : - sizeof (struct phi_arg_d)
183 : 21907878 : + sizeof (struct phi_arg_d) * len));
184 : 21907878 : phi->code = GIMPLE_PHI;
185 : 21907878 : gimple_init_singleton (phi);
186 : 21907878 : phi->nargs = len;
187 : 21907878 : phi->capacity = capacity;
188 : 21907878 : if (!var)
189 : : ;
190 : 13308618 : else if (TREE_CODE (var) == SSA_NAME)
191 : 7094520 : gimple_phi_set_result (phi, var);
192 : : else
193 : 6214098 : gimple_phi_set_result (phi, make_ssa_name (var, phi));
194 : :
195 : 57722300 : for (i = 0; i < len; i++)
196 : : {
197 : 35814422 : use_operand_p imm;
198 : :
199 : 35814422 : gimple_phi_arg_set_location (phi, i, UNKNOWN_LOCATION);
200 : 35814422 : imm = gimple_phi_arg_imm_use_ptr (phi, i);
201 : 35814422 : imm->use = gimple_phi_arg_def_ptr (phi, i);
202 : 35814422 : imm->prev = NULL;
203 : 35814422 : imm->next = NULL;
204 : 35814422 : imm->loc.stmt = phi;
205 : : }
206 : :
207 : 21907878 : return phi;
208 : : }
209 : :
210 : : /* We no longer need PHI, release it so that it may be reused. */
211 : :
212 : : static void
213 : 18486993 : release_phi_node (gimple *phi)
214 : : {
215 : 18486993 : size_t bucket;
216 : 18486993 : size_t len = gimple_phi_capacity (phi);
217 : 18486993 : size_t x;
218 : :
219 : 46400820 : for (x = 0; x < gimple_phi_num_args (phi); x++)
220 : : {
221 : 27913827 : use_operand_p imm;
222 : 27913827 : imm = gimple_phi_arg_imm_use_ptr (phi, x);
223 : 45574306 : 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 : 18486993 : if (len - 2 >= NUM_BUCKETS - 2)
229 : : {
230 : 160707 : ggc_free (phi);
231 : 160707 : return;
232 : : }
233 : :
234 : 18326286 : bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
235 : 18326286 : bucket -= 2;
236 : 18326286 : vec_safe_push (free_phinodes[bucket], phi);
237 : 18326286 : 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 : 647397 : resize_phi_node (gphi *phi, size_t len)
246 : : {
247 : 647397 : size_t old_size, i;
248 : 647397 : gphi *new_phi;
249 : :
250 : 647397 : 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 : 647397 : old_size = sizeof (struct gphi)
256 : 647397 : + (gimple_phi_num_args (phi) - 1) * sizeof (struct phi_arg_d);
257 : :
258 : 647397 : new_phi = allocate_phi_node (len);
259 : :
260 : 647397 : memcpy (new_phi, phi, old_size);
261 : 647397 : memset ((char *)new_phi + old_size, 0,
262 : : (sizeof (struct gphi)
263 : : - sizeof (struct phi_arg_d)
264 : 647397 : + sizeof (struct phi_arg_d) * len) - old_size);
265 : :
266 : 4553498 : for (i = 0; i < gimple_phi_num_args (new_phi); i++)
267 : : {
268 : 3906101 : use_operand_p imm, old_imm;
269 : 3906101 : imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
270 : 3906101 : old_imm = gimple_phi_arg_imm_use_ptr (phi, i);
271 : 3906101 : imm->use = gimple_phi_arg_def_ptr (new_phi, i);
272 : 3906101 : relink_imm_use_stmt (imm, old_imm, new_phi);
273 : : }
274 : :
275 : 647397 : new_phi->capacity = len;
276 : :
277 : 647397 : return new_phi;
278 : : }
279 : :
280 : : /* Reserve PHI arguments for a new edge to basic block BB. */
281 : :
282 : : void
283 : 29835792 : reserve_phi_args_for_new_edge (basic_block bb)
284 : : {
285 : 29835792 : size_t len = EDGE_COUNT (bb->preds);
286 : 29835792 : size_t cap = ideal_phi_node_len (len + 4);
287 : 29835792 : gphi_iterator gsi;
288 : :
289 : 84101755 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
290 : : {
291 : 54265963 : gphi *stmt = gsi.phi ();
292 : :
293 : 54265963 : if (len > gimple_phi_capacity (stmt))
294 : : {
295 : 647397 : gphi *new_phi = resize_phi_node (stmt, cap);
296 : :
297 : : /* The result of the PHI is defined by this PHI node. */
298 : 647397 : SSA_NAME_DEF_STMT (gimple_phi_result (new_phi)) = new_phi;
299 : 647397 : gsi_set_stmt (&gsi, new_phi);
300 : :
301 : 647397 : release_phi_node (stmt);
302 : 647397 : stmt = new_phi;
303 : : }
304 : :
305 : 54265963 : 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 : 54265963 : use_operand_p imm = gimple_phi_arg_imm_use_ptr (stmt, len - 1);
315 : 54265963 : imm->use = gimple_phi_arg_def_ptr (stmt, len - 1);
316 : 54265963 : imm->prev = NULL;
317 : 54265963 : imm->next = NULL;
318 : 54265963 : imm->loc.stmt = stmt;
319 : 54265963 : SET_PHI_ARG_DEF (stmt, len - 1, NULL_TREE);
320 : 54265963 : gimple_phi_arg_set_location (stmt, len - 1, UNKNOWN_LOCATION);
321 : : }
322 : 29835792 : }
323 : :
324 : : /* Adds PHI to BB. */
325 : :
326 : : static void
327 : 21907878 : add_phi_node_to_bb (gphi *phi, basic_block bb)
328 : : {
329 : 21907878 : gimple_seq seq = phi_nodes (bb);
330 : : /* Add the new PHI node to the list of PHI nodes for block BB. */
331 : 21907878 : if (seq == NULL)
332 : 12230269 : set_phi_nodes (bb, gimple_seq_alloc_with_stmt (phi));
333 : : else
334 : : {
335 : 9677609 : gimple_seq_add_stmt (&seq, phi);
336 : 9677609 : gcc_assert (seq == phi_nodes (bb));
337 : : }
338 : :
339 : : /* Associate BB to the PHI node. */
340 : 21907878 : gimple_set_bb (phi, bb);
341 : 21907878 : }
342 : :
343 : : /* Create a new PHI node for variable VAR at basic block BB. */
344 : :
345 : : gphi *
346 : 21907878 : create_phi_node (tree var, basic_block bb)
347 : : {
348 : 38907386 : gphi *phi = make_phi_node (var, EDGE_COUNT (bb->preds));
349 : :
350 : 21907878 : add_phi_node_to_bb (phi, bb);
351 : 21907878 : 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 : 41382757 : add_phi_arg (gphi *phi, tree def, edge e, location_t locus)
363 : : {
364 : 41382757 : basic_block bb = e->dest;
365 : :
366 : 41382757 : 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 : 41382757 : 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 : 41382757 : 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 : 41382757 : if (e->flags & EDGE_ABNORMAL)
379 : : {
380 : 203929 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
381 : 203929 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
382 : : }
383 : :
384 : 41382757 : SET_PHI_ARG_DEF (phi, e->dest_idx, def);
385 : 41382757 : gimple_phi_arg_set_location (phi, e->dest_idx, locus);
386 : 41382757 : }
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 : 56147540 : remove_phi_arg_num (gphi *phi, int i)
396 : : {
397 : 56147540 : int num_elem = gimple_phi_num_args (phi);
398 : :
399 : 56147540 : gcc_assert (i < num_elem);
400 : :
401 : : /* Delink the item which is being removed. */
402 : 56147540 : 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 : 56147540 : if (i != num_elem - 1)
407 : : {
408 : 50183517 : use_operand_p old_p, new_p;
409 : 50183517 : old_p = gimple_phi_arg_imm_use_ptr (phi, num_elem - 1);
410 : 50183517 : new_p = gimple_phi_arg_imm_use_ptr (phi, i);
411 : : /* Set use on new node, and link into last element's place. */
412 : 50183517 : *(new_p->use) = *(old_p->use);
413 : 50183517 : relink_imm_use (new_p, old_p);
414 : : /* Move the location as well. */
415 : 50183517 : 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 : 56147540 : phi->nargs--;
423 : 56147540 : }
424 : :
425 : :
426 : : /* Remove all PHI arguments associated with edge E. */
427 : :
428 : : void
429 : 32207464 : remove_phi_args (edge e)
430 : : {
431 : 32207464 : gphi_iterator gsi;
432 : :
433 : 88355004 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
434 : 56147540 : remove_phi_arg_num (gsi.phi (),
435 : 56147540 : e->dest_idx);
436 : 32207464 : }
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 : 17839596 : remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p)
446 : : {
447 : 17839596 : gimple *phi = gsi_stmt (*gsi);
448 : :
449 : 17839596 : if (release_lhs_p)
450 : 17704416 : insert_debug_temps_for_defs (gsi);
451 : :
452 : 17839596 : 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 : 17839596 : if (release_lhs_p)
457 : 17704416 : release_ssa_name (gimple_phi_result (phi));
458 : 17839596 : release_phi_node (phi);
459 : 17839596 : }
460 : :
461 : : /* Remove all the phi nodes from BB. */
462 : :
463 : : void
464 : 36581093 : remove_phi_nodes (basic_block bb)
465 : : {
466 : 36581093 : gphi_iterator gsi;
467 : :
468 : 38251262 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
469 : 1670169 : remove_phi_node (&gsi, true);
470 : :
471 : 36581093 : set_phi_nodes (bb, NULL);
472 : 36581093 : }
473 : :
474 : : /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
475 : : NULL. */
476 : :
477 : : tree
478 : 4345425 : degenerate_phi_result (gphi *phi)
479 : : {
480 : 4345425 : tree lhs = gimple_phi_result (phi);
481 : 4345425 : tree val = NULL;
482 : 4345425 : 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 : 8930960 : for (i = 0; i < gimple_phi_num_args (phi); i++)
488 : : {
489 : 8475018 : tree arg = gimple_phi_arg_def (phi, i);
490 : :
491 : 8475018 : if (arg == lhs)
492 : 90374 : continue;
493 : 8384644 : else if (!arg)
494 : : break;
495 : 8384644 : else if (!val)
496 : : val = arg;
497 : 4040360 : else if (arg == val)
498 : 150432 : 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 : 3889928 : else if (TREE_CODE (val) != TREE_CODE (arg)
503 : 1590521 : || TREE_CODE (val) == SSA_NAME
504 : 3964441 : || !operand_equal_p (arg, val, 0))
505 : : break;
506 : : }
507 : 4345425 : 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 : 76636945 : set_phi_nodes (basic_block bb, gimple_seq seq)
514 : : {
515 : 76636945 : gimple_stmt_iterator i;
516 : :
517 : 76636945 : gcc_checking_assert (!(bb->flags & BB_RTL));
518 : 76636945 : bb->il.gimple.phi_nodes = seq;
519 : 76636945 : if (seq)
520 : 24460538 : for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
521 : 12230269 : gimple_set_bb (gsi_stmt (i), bb);
522 : 76636945 : }
523 : :
524 : : #include "gt-tree-phinodes.h"
|
