1/* Generic routines for manipulating PHIs
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 3, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
70static GTY ((deletable (""))) vec<gimple *, va_gc> *free_phinodes[NUM_BUCKETS - 2];
71static unsigned long free_phinode_count;
72
73static int ideal_phi_node_len (int);
74
75unsigned int phi_nodes_reused;
76unsigned int phi_nodes_created;
77
78/* Dump some simple statistics regarding the re-use of PHI nodes. */
79
80void
81phinodes_print_statistics (void)
82{
83 fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created);
84 fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused);
85}
86
87/* Allocate a PHI node with at least LEN arguments. If the free list
88 happens to contain a PHI node with LEN arguments or more, return
89 that one. */
90
91static inline gphi *
92allocate_phi_node (size_t len)
93{
94 gphi *phi;
95 size_t bucket = NUM_BUCKETS - 2;
96 size_t size = sizeof (struct gphi)
97 + (len - 1) * sizeof (struct phi_arg_d);
98
99 if (free_phinode_count)
100 for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
101 if (free_phinodes[bucket])
102 break;
103
104 /* If our free list has an element, then use it. */
105 if (bucket < NUM_BUCKETS - 2
106 && gimple_phi_capacity ((*free_phinodes[bucket])[0]) >= len)
107 {
108 free_phinode_count--;
109 phi = as_a <gphi *> (free_phinodes[bucket]->pop ());
110 if (free_phinodes[bucket]->is_empty ())
111 vec_free (free_phinodes[bucket]);
112 if (GATHER_STATISTICS)
113 phi_nodes_reused++;
114 }
115 else
116 {
117 phi = static_cast <gphi *> (ggc_internal_alloc (size));
118 if (GATHER_STATISTICS)
119 {
120 enum gimple_alloc_kind kind = gimple_alloc_kind (GIMPLE_PHI);
121 phi_nodes_created++;
122 gimple_alloc_counts[(int) kind]++;
123 gimple_alloc_sizes[(int) kind] += size;
124 }
125 }
126
127 return phi;
128}
129
130/* Given LEN, the original number of requested PHI arguments, return
131 a new, "ideal" length for the PHI node. The "ideal" length rounds
132 the total size of the PHI node up to the next power of two bytes.
133
134 Rounding up will not result in wasting any memory since the size request
135 will be rounded up by the GC system anyway. [ Note this is not entirely
136 true since the original length might have fit on one of the special
137 GC pages. ] By rounding up, we may avoid the need to reallocate the
138 PHI node later if we increase the number of arguments for the PHI. */
139
140static int
141ideal_phi_node_len (int len)
142{
143 size_t size, new_size;
144 int log2, new_len;
145
146 /* We do not support allocations of less than two PHI argument slots. */
147 if (len < 2)
148 len = 2;
149
150 /* Compute the number of bytes of the original request. */
151 size = sizeof (struct gphi)
152 + (len - 1) * sizeof (struct phi_arg_d);
153
154 /* Round it up to the next power of two. */
155 log2 = ceil_log2 (size);
156 new_size = 1 << log2;
157
158 /* Now compute and return the number of PHI argument slots given an
159 ideal size allocation. */
160 new_len = len + (new_size - size) / sizeof (struct phi_arg_d);
161 return new_len;
162}
163
164/* Return a PHI node with LEN argument slots for variable VAR. */
165
166static gphi *
167make_phi_node (tree var, int len)
168{
169 gphi *phi;
170 int capacity, i;
171
172 capacity = ideal_phi_node_len (len);
173
174 phi = allocate_phi_node (capacity);
175
176 /* We need to clear the entire PHI node, including the argument
177 portion, because we represent a "missing PHI argument" by placing
178 NULL_TREE in PHI_ARG_DEF. */
179 memset (phi, 0, (sizeof (struct gphi)
180 - sizeof (struct phi_arg_d)
181 + sizeof (struct phi_arg_d) * len));
182 phi->code = GIMPLE_PHI;
183 gimple_init_singleton (phi);
184 phi->nargs = len;
185 phi->capacity = capacity;
186 if (!var)
187 ;
188 else if (TREE_CODE (var) == SSA_NAME)
189 gimple_phi_set_result (phi, var);
190 else
191 gimple_phi_set_result (phi, make_ssa_name (var, phi));
192
193 for (i = 0; i < len; i++)
194 {
195 use_operand_p imm;
196
197 gimple_phi_arg_set_location (phi, i, UNKNOWN_LOCATION);
198 imm = gimple_phi_arg_imm_use_ptr (phi, i);
199 imm->use = gimple_phi_arg_def_ptr (phi, i);
200 imm->prev = NULL;
201 imm->next = NULL;
202 imm->loc.stmt = phi;
203 }
204
205 return phi;
206}
207
208/* We no longer need PHI, release it so that it may be reused. */
209
210static void
211release_phi_node (gimple *phi)
212{
213 size_t bucket;
214 size_t len = gimple_phi_capacity (phi);
215 size_t x;
216
217 for (x = 0; x < gimple_phi_num_args (phi); x++)
218 {
219 use_operand_p imm;
220 imm = gimple_phi_arg_imm_use_ptr (phi, x);
221 delink_imm_use (imm);
222 }
223
224 bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
225 bucket -= 2;
226 vec_safe_push (free_phinodes[bucket], phi);
227 free_phinode_count++;
228}
229
230
231/* Resize an existing PHI node. The only way is up. Return the
232 possibly relocated phi. */
233
234static gphi *
235resize_phi_node (gphi *phi, size_t len)
236{
237 size_t old_size, i;
238 gphi *new_phi;
239
240 gcc_assert (len > gimple_phi_capacity (phi));
241
242 /* The garbage collector will not look at the PHI node beyond the
243 first PHI_NUM_ARGS elements. Therefore, all we have to copy is a
244 portion of the PHI node currently in use. */
245 old_size = sizeof (struct gphi)
246 + (gimple_phi_num_args (phi) - 1) * sizeof (struct phi_arg_d);
247
248 new_phi = allocate_phi_node (len);
249
250 memcpy (new_phi, phi, old_size);
251 memset ((char *)new_phi + old_size, 0,
252 (sizeof (struct gphi)
253 - sizeof (struct phi_arg_d)
254 + sizeof (struct phi_arg_d) * len) - old_size);
255
256 for (i = 0; i < gimple_phi_num_args (new_phi); i++)
257 {
258 use_operand_p imm, old_imm;
259 imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
260 old_imm = gimple_phi_arg_imm_use_ptr (phi, i);
261 imm->use = gimple_phi_arg_def_ptr (new_phi, i);
262 relink_imm_use_stmt (imm, old_imm, new_phi);
263 }
264
265 new_phi->capacity = len;
266
267 return new_phi;
268}
269
270/* Reserve PHI arguments for a new edge to basic block BB. */
271
272void
273reserve_phi_args_for_new_edge (basic_block bb)
274{
275 size_t len = EDGE_COUNT (bb->preds);
276 size_t cap = ideal_phi_node_len (len + 4);
277 gphi_iterator gsi;
278
279 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
280 {
281 gphi *stmt = gsi.phi ();
282
283 if (len > gimple_phi_capacity (stmt))
284 {
285 gphi *new_phi = resize_phi_node (stmt, cap);
286
287 /* The result of the PHI is defined by this PHI node. */
288 SSA_NAME_DEF_STMT (gimple_phi_result (new_phi)) = new_phi;
289 gsi_set_stmt (&gsi, new_phi);
290
291 release_phi_node (stmt);
292 stmt = new_phi;
293 }
294
295 stmt->nargs++;
296
297 /* We represent a "missing PHI argument" by placing NULL_TREE in
298 the corresponding slot. If PHI arguments were added
299 immediately after an edge is created, this zeroing would not
300 be necessary, but unfortunately this is not the case. For
301 example, the loop optimizer duplicates several basic blocks,
302 redirects edges, and then fixes up PHI arguments later in
303 batch. */
304 use_operand_p imm = gimple_phi_arg_imm_use_ptr (stmt, len - 1);
305 imm->use = gimple_phi_arg_def_ptr (stmt, len - 1);
306 imm->prev = NULL;
307 imm->next = NULL;
308 imm->loc.stmt = stmt;
309 SET_PHI_ARG_DEF (stmt, len - 1, NULL_TREE);
310 gimple_phi_arg_set_location (stmt, len - 1, UNKNOWN_LOCATION);
311 }
312}
313
314/* Adds PHI to BB. */
315
316void
317add_phi_node_to_bb (gphi *phi, basic_block bb)
318{
319 gimple_seq seq = phi_nodes (bb);
320 /* Add the new PHI node to the list of PHI nodes for block BB. */
321 if (seq == NULL)
322 set_phi_nodes (bb, gimple_seq_alloc_with_stmt (phi));
323 else
324 {
325 gimple_seq_add_stmt (&seq, phi);
326 gcc_assert (seq == phi_nodes (bb));
327 }
328
329 /* Associate BB to the PHI node. */
330 gimple_set_bb (phi, bb);
331
332}
333
334/* Create a new PHI node for variable VAR at basic block BB. */
335
336gphi *
337create_phi_node (tree var, basic_block bb)
338{
339 gphi *phi = make_phi_node (var, EDGE_COUNT (bb->preds));
340
341 add_phi_node_to_bb (phi, bb);
342 return phi;
343}
344
345
346/* Add a new argument to PHI node PHI. DEF is the incoming reaching
347 definition and E is the edge through which DEF reaches PHI. The new
348 argument is added at the end of the argument list.
349 If PHI has reached its maximum capacity, add a few slots. In this case,
350 PHI points to the reallocated phi node when we return. */
351
352void
353add_phi_arg (gphi *phi, tree def, edge e, source_location locus)
354{
355 basic_block bb = e->dest;
356
357 gcc_assert (bb == gimple_bb (phi));
358
359 /* We resize PHI nodes upon edge creation. We should always have
360 enough room at this point. */
361 gcc_assert (gimple_phi_num_args (phi) <= gimple_phi_capacity (phi));
362
363 /* We resize PHI nodes upon edge creation. We should always have
364 enough room at this point. */
365 gcc_assert (e->dest_idx < gimple_phi_num_args (phi));
366
367 /* Copy propagation needs to know what object occur in abnormal
368 PHI nodes. This is a convenient place to record such information. */
369 if (e->flags & EDGE_ABNORMAL)
370 {
371 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
372 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
373 }
374
375 SET_PHI_ARG_DEF (phi, e->dest_idx, def);
376 gimple_phi_arg_set_location (phi, e->dest_idx, locus);
377}
378
379
380/* Remove the Ith argument from PHI's argument list. This routine
381 implements removal by swapping the last alternative with the
382 alternative we want to delete and then shrinking the vector, which
383 is consistent with how we remove an edge from the edge vector. */
384
385static void
386remove_phi_arg_num (gphi *phi, int i)
387{
388 int num_elem = gimple_phi_num_args (phi);
389
390 gcc_assert (i < num_elem);
391
392 /* Delink the item which is being removed. */
393 delink_imm_use (gimple_phi_arg_imm_use_ptr (phi, i));
394
395 /* If it is not the last element, move the last element
396 to the element we want to delete, resetting all the links. */
397 if (i != num_elem - 1)
398 {
399 use_operand_p old_p, new_p;
400 old_p = gimple_phi_arg_imm_use_ptr (phi, num_elem - 1);
401 new_p = gimple_phi_arg_imm_use_ptr (phi, i);
402 /* Set use on new node, and link into last element's place. */
403 *(new_p->use) = *(old_p->use);
404 relink_imm_use (new_p, old_p);
405 /* Move the location as well. */
406 gimple_phi_arg_set_location (phi, i,
407 gimple_phi_arg_location (phi, num_elem - 1));
408 }
409
410 /* Shrink the vector and return. Note that we do not have to clear
411 PHI_ARG_DEF because the garbage collector will not look at those
412 elements beyond the first PHI_NUM_ARGS elements of the array. */
413 phi->nargs--;
414}
415
416
417/* Remove all PHI arguments associated with edge E. */
418
419void
420remove_phi_args (edge e)
421{
422 gphi_iterator gsi;
423
424 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
425 remove_phi_arg_num (gsi.phi (),
426 e->dest_idx);
427}
428
429
430/* Remove the PHI node pointed-to by iterator GSI from basic block BB. After
431 removal, iterator GSI is updated to point to the next PHI node in the
432 sequence. If RELEASE_LHS_P is true, the LHS of this PHI node is released
433 into the free pool of SSA names. */
434
435void
436remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p)
437{
438 gimple *phi = gsi_stmt (*gsi);
439
440 if (release_lhs_p)
441 insert_debug_temps_for_defs (gsi);
442
443 gsi_remove (gsi, false);
444
445 /* If we are deleting the PHI node, then we should release the
446 SSA_NAME node so that it can be reused. */
447 release_phi_node (phi);
448 if (release_lhs_p)
449 release_ssa_name (gimple_phi_result (phi));
450}
451
452/* Remove all the phi nodes from BB. */
453
454void
455remove_phi_nodes (basic_block bb)
456{
457 gphi_iterator gsi;
458
459 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
460 remove_phi_node (&gsi, true);
461
462 set_phi_nodes (bb, NULL);
463}
464
465/* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
466 NULL. */
467
468tree
469degenerate_phi_result (gphi *phi)
470{
471 tree lhs = gimple_phi_result (phi);
472 tree val = NULL;
473 size_t i;
474
475 /* Ignoring arguments which are the same as LHS, if all the remaining
476 arguments are the same, then the PHI is a degenerate and has the
477 value of that common argument. */
478 for (i = 0; i < gimple_phi_num_args (phi); i++)
479 {
480 tree arg = gimple_phi_arg_def (phi, i);
481
482 if (arg == lhs)
483 continue;
484 else if (!arg)
485 break;
486 else if (!val)
487 val = arg;
488 else if (arg == val)
489 continue;
490 /* We bring in some of operand_equal_p not only to speed things
491 up, but also to avoid crashing when dereferencing the type of
492 a released SSA name. */
493 else if (TREE_CODE (val) != TREE_CODE (arg)
494 || TREE_CODE (val) == SSA_NAME
495 || !operand_equal_p (arg, val, 0))
496 break;
497 }
498 return (i == gimple_phi_num_args (phi) ? val : NULL);
499}
500
501/* Set PHI nodes of a basic block BB to SEQ. */
502
503void
504set_phi_nodes (basic_block bb, gimple_seq seq)
505{
506 gimple_stmt_iterator i;
507
508 gcc_checking_assert (!(bb->flags & BB_RTL));
509 bb->il.gimple.phi_nodes = seq;
510 if (seq)
511 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
512 gimple_set_bb (gsi_stmt (i), bb);
513}
514
515#include "gt-tree-phinodes.h"
516