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 : 20423105 : allocate_phi_node (size_t len)
95 : : {
96 : 20423105 : gphi *phi;
97 : 20423105 : size_t bucket = NUM_BUCKETS - 2;
98 : 20423105 : size_t size = sizeof (struct gphi)
99 : 20423105 : + (len - 1) * sizeof (struct phi_arg_d);
100 : :
101 : 20423105 : if (free_phinode_count)
102 : 29193772 : for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
103 : 26398803 : if (free_phinodes[bucket])
104 : : break;
105 : :
106 : : /* If our free list has an element, then use it. */
107 : 14324835 : if (bucket < NUM_BUCKETS - 2
108 : 14324835 : && gimple_phi_capacity ((*free_phinodes[bucket])[0]) >= len)
109 : : {
110 : 11529866 : free_phinode_count--;
111 : 11529866 : phi = as_a <gphi *> (free_phinodes[bucket]->pop ());
112 : 11529866 : if (free_phinodes[bucket]->is_empty ())
113 : 466971 : vec_free (free_phinodes[bucket]);
114 : : if (GATHER_STATISTICS)
115 : : phi_nodes_reused++;
116 : : }
117 : : else
118 : : {
119 : 8893239 : phi = static_cast <gphi *> (ggc_internal_alloc (size));
120 : 8893239 : 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 : 20423105 : 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 : 45958670 : ideal_phi_node_len (int len)
144 : : {
145 : 45958670 : size_t size, new_size;
146 : 45958670 : int log2, new_len;
147 : :
148 : : /* We do not support allocations of less than two PHI argument slots. */
149 : 45958670 : if (len < 2)
150 : : len = 2;
151 : :
152 : : /* Compute the number of bytes of the original request. */
153 : 45958670 : size = sizeof (struct gphi)
154 : 45958670 : + (len - 1) * sizeof (struct phi_arg_d);
155 : :
156 : : /* Round it up to the next power of two. */
157 : 45958670 : log2 = ceil_log2 (size);
158 : 45958670 : new_size = 1 << log2;
159 : :
160 : : /* Now compute and return the number of PHI argument slots given an
161 : : ideal size allocation. */
162 : 45958670 : new_len = len + (new_size - size) / sizeof (struct phi_arg_d);
163 : 45958670 : return new_len;
164 : : }
165 : :
166 : : /* Return a PHI node with LEN argument slots for variable VAR. */
167 : :
168 : : static gphi *
169 : 19790332 : make_phi_node (tree var, int len)
170 : : {
171 : 19790332 : gphi *phi;
172 : 19790332 : int capacity, i;
173 : :
174 : 19790332 : capacity = ideal_phi_node_len (len);
175 : :
176 : 19790332 : 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 : 19790332 : memset (phi, 0, (sizeof (struct gphi)
182 : : - sizeof (struct phi_arg_d)
183 : 19790332 : + sizeof (struct phi_arg_d) * len));
184 : 19790332 : phi->code = GIMPLE_PHI;
185 : 19790332 : gimple_init_singleton (phi);
186 : 19790332 : phi->nargs = len;
187 : 19790332 : phi->capacity = capacity;
188 : 19790332 : if (!var)
189 : : ;
190 : 12104774 : else if (TREE_CODE (var) == SSA_NAME)
191 : 6151305 : gimple_phi_set_result (phi, var);
192 : : else
193 : 5953469 : gimple_phi_set_result (phi, make_ssa_name (var, phi));
194 : :
195 : 53049566 : for (i = 0; i < len; i++)
196 : : {
197 : 33259234 : use_operand_p imm;
198 : :
199 : 33259234 : gimple_phi_arg_set_location (phi, i, UNKNOWN_LOCATION);
200 : 33259234 : imm = gimple_phi_arg_imm_use_ptr (phi, i);
201 : 33259234 : imm->use = gimple_phi_arg_def_ptr (phi, i);
202 : 33259234 : imm->prev = NULL;
203 : 33259234 : imm->next = NULL;
204 : 33259234 : imm->loc.stmt = phi;
205 : : }
206 : :
207 : 19790332 : return phi;
208 : : }
209 : :
210 : : /* We no longer need PHI, release it so that it may be reused. */
211 : :
212 : : static void
213 : 16752137 : release_phi_node (gimple *phi)
214 : : {
215 : 16752137 : size_t bucket;
216 : 16752137 : size_t len = gimple_phi_capacity (phi);
217 : 16752137 : size_t x;
218 : :
219 : 42645703 : for (x = 0; x < gimple_phi_num_args (phi); x++)
220 : : {
221 : 25893566 : use_operand_p imm;
222 : 25893566 : imm = gimple_phi_arg_imm_use_ptr (phi, x);
223 : 42544828 : 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 : 16752137 : if (len - 2 >= NUM_BUCKETS - 2)
229 : : {
230 : 157546 : ggc_free (phi);
231 : 157546 : return;
232 : : }
233 : :
234 : 16594591 : bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
235 : 16594591 : bucket -= 2;
236 : 16594591 : vec_safe_push (free_phinodes[bucket], phi);
237 : 16594591 : 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 : 632773 : resize_phi_node (gphi *phi, size_t len)
246 : : {
247 : 632773 : size_t old_size, i;
248 : 632773 : gphi *new_phi;
249 : :
250 : 632773 : 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 : 632773 : old_size = sizeof (struct gphi)
256 : 632773 : + (gimple_phi_num_args (phi) - 1) * sizeof (struct phi_arg_d);
257 : :
258 : 632773 : new_phi = allocate_phi_node (len);
259 : :
260 : 632773 : memcpy (new_phi, phi, old_size);
261 : 632773 : memset ((char *)new_phi + old_size, 0,
262 : : (sizeof (struct gphi)
263 : : - sizeof (struct phi_arg_d)
264 : 632773 : + sizeof (struct phi_arg_d) * len) - old_size);
265 : :
266 : 4710438 : for (i = 0; i < gimple_phi_num_args (new_phi); i++)
267 : : {
268 : 4077665 : use_operand_p imm, old_imm;
269 : 4077665 : imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
270 : 4077665 : old_imm = gimple_phi_arg_imm_use_ptr (phi, i);
271 : 4077665 : imm->use = gimple_phi_arg_def_ptr (new_phi, i);
272 : 4077665 : relink_imm_use_stmt (imm, old_imm, new_phi);
273 : : }
274 : :
275 : 632773 : new_phi->capacity = len;
276 : :
277 : 632773 : return new_phi;
278 : : }
279 : :
280 : : /* Reserve PHI arguments for a new edge to basic block BB. */
281 : :
282 : : void
283 : 26168338 : reserve_phi_args_for_new_edge (basic_block bb)
284 : : {
285 : 26168338 : size_t len = EDGE_COUNT (bb->preds);
286 : 26168338 : size_t cap = ideal_phi_node_len (len + 4);
287 : 26168338 : gphi_iterator gsi;
288 : :
289 : 75376359 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
290 : : {
291 : 49208021 : gphi *stmt = gsi.phi ();
292 : :
293 : 49208021 : if (len > gimple_phi_capacity (stmt))
294 : : {
295 : 632773 : gphi *new_phi = resize_phi_node (stmt, cap);
296 : :
297 : : /* The result of the PHI is defined by this PHI node. */
298 : 632773 : SSA_NAME_DEF_STMT (gimple_phi_result (new_phi)) = new_phi;
299 : 632773 : gsi_set_stmt (&gsi, new_phi);
300 : :
301 : 632773 : release_phi_node (stmt);
302 : 632773 : stmt = new_phi;
303 : : }
304 : :
305 : 49208021 : 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 : 49208021 : use_operand_p imm = gimple_phi_arg_imm_use_ptr (stmt, len - 1);
315 : 49208021 : imm->use = gimple_phi_arg_def_ptr (stmt, len - 1);
316 : 49208021 : imm->prev = NULL;
317 : 49208021 : imm->next = NULL;
318 : 49208021 : imm->loc.stmt = stmt;
319 : 49208021 : SET_PHI_ARG_DEF (stmt, len - 1, NULL_TREE);
320 : 49208021 : gimple_phi_arg_set_location (stmt, len - 1, UNKNOWN_LOCATION);
321 : : }
322 : 26168338 : }
323 : :
324 : : /* Adds PHI to BB. */
325 : :
326 : : static void
327 : 19790332 : add_phi_node_to_bb (gphi *phi, basic_block bb)
328 : : {
329 : 19790332 : gimple_seq seq = phi_nodes (bb);
330 : : /* Add the new PHI node to the list of PHI nodes for block BB. */
331 : 19790332 : if (seq == NULL)
332 : 11090433 : set_phi_nodes (bb, gimple_seq_alloc_with_stmt (phi));
333 : : else
334 : : {
335 : 8699899 : gimple_seq_add_stmt (&seq, phi);
336 : 8699899 : gcc_assert (seq == phi_nodes (bb));
337 : : }
338 : :
339 : : /* Associate BB to the PHI node. */
340 : 19790332 : gimple_set_bb (phi, bb);
341 : 19790332 : }
342 : :
343 : : /* Create a new PHI node for variable VAR at basic block BB. */
344 : :
345 : : gphi *
346 : 19790332 : create_phi_node (tree var, basic_block bb)
347 : : {
348 : 35420871 : gphi *phi = make_phi_node (var, EDGE_COUNT (bb->preds));
349 : :
350 : 19790332 : add_phi_node_to_bb (phi, bb);
351 : 19790332 : 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 : 38022570 : add_phi_arg (gphi *phi, tree def, edge e, location_t locus)
363 : : {
364 : 38022570 : basic_block bb = e->dest;
365 : :
366 : 38022570 : 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 : 38022570 : 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 : 38022570 : 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 : 38022570 : if (e->flags & EDGE_ABNORMAL)
379 : : {
380 : 203535 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
381 : 203535 : SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
382 : : }
383 : :
384 : 38022570 : SET_PHI_ARG_DEF (phi, e->dest_idx, def);
385 : 38022570 : gimple_phi_arg_set_location (phi, e->dest_idx, locus);
386 : 38022570 : }
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 : 51394227 : remove_phi_arg_num (gphi *phi, int i)
396 : : {
397 : 51394227 : int num_elem = gimple_phi_num_args (phi);
398 : :
399 : 51394227 : gcc_assert (i < num_elem);
400 : :
401 : : /* Delink the item which is being removed. */
402 : 51394227 : 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 : 51394227 : if (i != num_elem - 1)
407 : : {
408 : 46023226 : use_operand_p old_p, new_p;
409 : 46023226 : old_p = gimple_phi_arg_imm_use_ptr (phi, num_elem - 1);
410 : 46023226 : new_p = gimple_phi_arg_imm_use_ptr (phi, i);
411 : : /* Set use on new node, and link into last element's place. */
412 : 46023226 : *(new_p->use) = *(old_p->use);
413 : 46023226 : relink_imm_use (new_p, old_p);
414 : : /* Move the location as well. */
415 : 46023226 : 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 : 51394227 : phi->nargs--;
423 : 51394227 : }
424 : :
425 : :
426 : : /* Remove all PHI arguments associated with edge E. */
427 : :
428 : : void
429 : 28725930 : remove_phi_args (edge e)
430 : : {
431 : 28725930 : gphi_iterator gsi;
432 : :
433 : 80120157 : for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
434 : 51394227 : remove_phi_arg_num (gsi.phi (),
435 : 51394227 : e->dest_idx);
436 : 28725930 : }
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 : 16119364 : remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p)
446 : : {
447 : 16119364 : gimple *phi = gsi_stmt (*gsi);
448 : :
449 : 16119364 : if (release_lhs_p)
450 : 16001537 : insert_debug_temps_for_defs (gsi);
451 : :
452 : 16119364 : 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 : 16119364 : if (release_lhs_p)
457 : 16001537 : release_ssa_name (gimple_phi_result (phi));
458 : 16119364 : release_phi_node (phi);
459 : 16119364 : }
460 : :
461 : : /* Remove all the phi nodes from BB. */
462 : :
463 : : void
464 : 32044219 : remove_phi_nodes (basic_block bb)
465 : : {
466 : 32044219 : gphi_iterator gsi;
467 : :
468 : 33662859 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
469 : 1618640 : remove_phi_node (&gsi, true);
470 : :
471 : 32044219 : set_phi_nodes (bb, NULL);
472 : 32044219 : }
473 : :
474 : : /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
475 : : NULL. */
476 : :
477 : : tree
478 : 4167228 : degenerate_phi_result (gphi *phi)
479 : : {
480 : 4167228 : tree lhs = gimple_phi_result (phi);
481 : 4167228 : tree val = NULL;
482 : 4167228 : 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 : 8542969 : for (i = 0; i < gimple_phi_num_args (phi); i++)
488 : : {
489 : 8161820 : tree arg = gimple_phi_arg_def (phi, i);
490 : :
491 : 8161820 : if (arg == lhs)
492 : 86372 : continue;
493 : 8075448 : else if (!arg)
494 : : break;
495 : 8075448 : else if (!val)
496 : : val = arg;
497 : 3909268 : else if (arg == val)
498 : 122816 : 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 : 3786452 : else if (TREE_CODE (val) != TREE_CODE (arg)
503 : 1453047 : || TREE_CODE (val) == SSA_NAME
504 : 3842449 : || !operand_equal_p (arg, val, 0))
505 : : break;
506 : : }
507 : 4167228 : 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 : 66873019 : set_phi_nodes (basic_block bb, gimple_seq seq)
514 : : {
515 : 66873019 : gimple_stmt_iterator i;
516 : :
517 : 66873019 : gcc_checking_assert (!(bb->flags & BB_RTL));
518 : 66873019 : bb->il.gimple.phi_nodes = seq;
519 : 66873019 : if (seq)
520 : 22180866 : for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
521 : 11090433 : gimple_set_bb (gsi_stmt (i), bb);
522 : 66873019 : }
523 : :
524 : : #include "gt-tree-phinodes.h"
|
