Daily bump.
[official-gcc.git] / gcc / tree-phinodes.c
blob90d60efc6b7f2339a04e7d5919fee5aa29691ad3
1 /* Generic routines for manipulating PHIs
2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "tree.h"
25 #include "predict.h"
26 #include "vec.h"
27 #include "hashtab.h"
28 #include "hash-set.h"
29 #include "machmode.h"
30 #include "hard-reg-set.h"
31 #include "input.h"
32 #include "function.h"
33 #include "basic-block.h"
34 #include "tree-ssa-alias.h"
35 #include "internal-fn.h"
36 #include "gimple-expr.h"
37 #include "is-a.h"
38 #include "gimple.h"
39 #include "gimple-iterator.h"
40 #include "gimple-ssa.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "stringpool.h"
44 #include "tree-ssanames.h"
45 #include "tree-ssa.h"
46 #include "diagnostic-core.h"
48 /* Rewriting a function into SSA form can create a huge number of PHIs
49 many of which may be thrown away shortly after their creation if jumps
50 were threaded through PHI nodes.
52 While our garbage collection mechanisms will handle this situation, it
53 is extremely wasteful to create nodes and throw them away, especially
54 when the nodes can be reused.
56 For PR 8361, we can significantly reduce the number of nodes allocated
57 and thus the total amount of memory allocated by managing PHIs a
58 little. This additionally helps reduce the amount of work done by the
59 garbage collector. Similar results have been seen on a wider variety
60 of tests (such as the compiler itself).
62 PHI nodes have different sizes, so we can't have a single list of all
63 the PHI nodes as it would be too expensive to walk down that list to
64 find a PHI of a suitable size.
66 Instead we have an array of lists of free PHI nodes. The array is
67 indexed by the number of PHI alternatives that PHI node can hold.
68 Except for the last array member, which holds all remaining PHI
69 nodes.
71 So to find a free PHI node, we compute its index into the free PHI
72 node array and see if there are any elements with an exact match.
73 If so, then we are done. Otherwise, we test the next larger size
74 up and continue until we are in the last array element.
76 We do not actually walk members of the last array element. While it
77 might allow us to pick up a few reusable PHI nodes, it could potentially
78 be very expensive if the program has released a bunch of large PHI nodes,
79 but keeps asking for even larger PHI nodes. Experiments have shown that
80 walking the elements of the last array entry would result in finding less
81 than .1% additional reusable PHI nodes.
83 Note that we can never have less than two PHI argument slots. Thus,
84 the -2 on all the calculations below. */
86 #define NUM_BUCKETS 10
87 static GTY ((deletable (""))) vec<gimple, va_gc> *free_phinodes[NUM_BUCKETS - 2];
88 static unsigned long free_phinode_count;
90 static int ideal_phi_node_len (int);
92 unsigned int phi_nodes_reused;
93 unsigned int phi_nodes_created;
95 /* Dump some simple statistics regarding the re-use of PHI nodes. */
97 void
98 phinodes_print_statistics (void)
100 fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created);
101 fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused);
104 /* Allocate a PHI node with at least LEN arguments. If the free list
105 happens to contain a PHI node with LEN arguments or more, return
106 that one. */
108 static inline gphi *
109 allocate_phi_node (size_t len)
111 gphi *phi;
112 size_t bucket = NUM_BUCKETS - 2;
113 size_t size = sizeof (struct gphi)
114 + (len - 1) * sizeof (struct phi_arg_d);
116 if (free_phinode_count)
117 for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
118 if (free_phinodes[bucket])
119 break;
121 /* If our free list has an element, then use it. */
122 if (bucket < NUM_BUCKETS - 2
123 && gimple_phi_capacity ((*free_phinodes[bucket])[0]) >= len)
125 free_phinode_count--;
126 phi = as_a <gphi *> (free_phinodes[bucket]->pop ());
127 if (free_phinodes[bucket]->is_empty ())
128 vec_free (free_phinodes[bucket]);
129 if (GATHER_STATISTICS)
130 phi_nodes_reused++;
132 else
134 phi = static_cast <gphi *> (ggc_internal_alloc (size));
135 if (GATHER_STATISTICS)
137 enum gimple_alloc_kind kind = gimple_alloc_kind (GIMPLE_PHI);
138 phi_nodes_created++;
139 gimple_alloc_counts[(int) kind]++;
140 gimple_alloc_sizes[(int) kind] += size;
144 return phi;
147 /* Given LEN, the original number of requested PHI arguments, return
148 a new, "ideal" length for the PHI node. The "ideal" length rounds
149 the total size of the PHI node up to the next power of two bytes.
151 Rounding up will not result in wasting any memory since the size request
152 will be rounded up by the GC system anyway. [ Note this is not entirely
153 true since the original length might have fit on one of the special
154 GC pages. ] By rounding up, we may avoid the need to reallocate the
155 PHI node later if we increase the number of arguments for the PHI. */
157 static int
158 ideal_phi_node_len (int len)
160 size_t size, new_size;
161 int log2, new_len;
163 /* We do not support allocations of less than two PHI argument slots. */
164 if (len < 2)
165 len = 2;
167 /* Compute the number of bytes of the original request. */
168 size = sizeof (struct gphi)
169 + (len - 1) * sizeof (struct phi_arg_d);
171 /* Round it up to the next power of two. */
172 log2 = ceil_log2 (size);
173 new_size = 1 << log2;
175 /* Now compute and return the number of PHI argument slots given an
176 ideal size allocation. */
177 new_len = len + (new_size - size) / sizeof (struct phi_arg_d);
178 return new_len;
181 /* Return a PHI node with LEN argument slots for variable VAR. */
183 static gphi *
184 make_phi_node (tree var, int len)
186 gphi *phi;
187 int capacity, i;
189 capacity = ideal_phi_node_len (len);
191 phi = allocate_phi_node (capacity);
193 /* We need to clear the entire PHI node, including the argument
194 portion, because we represent a "missing PHI argument" by placing
195 NULL_TREE in PHI_ARG_DEF. */
196 memset (phi, 0, (sizeof (struct gphi)
197 - sizeof (struct phi_arg_d)
198 + sizeof (struct phi_arg_d) * len));
199 phi->code = GIMPLE_PHI;
200 gimple_init_singleton (phi);
201 phi->nargs = len;
202 phi->capacity = capacity;
203 if (!var)
205 else if (TREE_CODE (var) == SSA_NAME)
206 gimple_phi_set_result (phi, var);
207 else
208 gimple_phi_set_result (phi, make_ssa_name (var, phi));
210 for (i = 0; i < capacity; i++)
212 use_operand_p imm;
214 gimple_phi_arg_set_location (phi, i, UNKNOWN_LOCATION);
215 imm = gimple_phi_arg_imm_use_ptr (phi, i);
216 imm->use = gimple_phi_arg_def_ptr (phi, i);
217 imm->prev = NULL;
218 imm->next = NULL;
219 imm->loc.stmt = phi;
222 return phi;
225 /* We no longer need PHI, release it so that it may be reused. */
227 void
228 release_phi_node (gimple phi)
230 size_t bucket;
231 size_t len = gimple_phi_capacity (phi);
232 size_t x;
234 for (x = 0; x < gimple_phi_num_args (phi); x++)
236 use_operand_p imm;
237 imm = gimple_phi_arg_imm_use_ptr (phi, x);
238 delink_imm_use (imm);
241 bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
242 bucket -= 2;
243 vec_safe_push (free_phinodes[bucket], phi);
244 free_phinode_count++;
248 /* Resize an existing PHI node. The only way is up. Return the
249 possibly relocated phi. */
251 static gphi *
252 resize_phi_node (gphi *phi, size_t len)
254 size_t old_size, i;
255 gphi *new_phi;
257 gcc_assert (len > gimple_phi_capacity (phi));
259 /* The garbage collector will not look at the PHI node beyond the
260 first PHI_NUM_ARGS elements. Therefore, all we have to copy is a
261 portion of the PHI node currently in use. */
262 old_size = sizeof (struct gphi)
263 + (gimple_phi_num_args (phi) - 1) * sizeof (struct phi_arg_d);
265 new_phi = allocate_phi_node (len);
267 memcpy (new_phi, phi, old_size);
269 for (i = 0; i < gimple_phi_num_args (new_phi); i++)
271 use_operand_p imm, old_imm;
272 imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
273 old_imm = gimple_phi_arg_imm_use_ptr (phi, i);
274 imm->use = gimple_phi_arg_def_ptr (new_phi, i);
275 relink_imm_use_stmt (imm, old_imm, new_phi);
278 new_phi->capacity = len;
280 for (i = gimple_phi_num_args (new_phi); i < len; i++)
282 use_operand_p imm;
284 gimple_phi_arg_set_location (new_phi, i, UNKNOWN_LOCATION);
285 imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
286 imm->use = gimple_phi_arg_def_ptr (new_phi, i);
287 imm->prev = NULL;
288 imm->next = NULL;
289 imm->loc.stmt = new_phi;
292 return new_phi;
295 /* Reserve PHI arguments for a new edge to basic block BB. */
297 void
298 reserve_phi_args_for_new_edge (basic_block bb)
300 size_t len = EDGE_COUNT (bb->preds);
301 size_t cap = ideal_phi_node_len (len + 4);
302 gphi_iterator gsi;
304 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
306 gphi *stmt = gsi.phi ();
308 if (len > gimple_phi_capacity (stmt))
310 gphi *new_phi = resize_phi_node (stmt, cap);
312 /* The result of the PHI is defined by this PHI node. */
313 SSA_NAME_DEF_STMT (gimple_phi_result (new_phi)) = new_phi;
314 gsi_set_stmt (&gsi, new_phi);
316 release_phi_node (stmt);
317 stmt = new_phi;
320 /* We represent a "missing PHI argument" by placing NULL_TREE in
321 the corresponding slot. If PHI arguments were added
322 immediately after an edge is created, this zeroing would not
323 be necessary, but unfortunately this is not the case. For
324 example, the loop optimizer duplicates several basic blocks,
325 redirects edges, and then fixes up PHI arguments later in
326 batch. */
327 SET_PHI_ARG_DEF (stmt, len - 1, NULL_TREE);
328 gimple_phi_arg_set_location (stmt, len - 1, UNKNOWN_LOCATION);
330 stmt->nargs++;
334 /* Adds PHI to BB. */
336 void
337 add_phi_node_to_bb (gphi *phi, basic_block bb)
339 gimple_seq seq = phi_nodes (bb);
340 /* Add the new PHI node to the list of PHI nodes for block BB. */
341 if (seq == NULL)
342 set_phi_nodes (bb, gimple_seq_alloc_with_stmt (phi));
343 else
345 gimple_seq_add_stmt (&seq, phi);
346 gcc_assert (seq == phi_nodes (bb));
349 /* Associate BB to the PHI node. */
350 gimple_set_bb (phi, bb);
354 /* Create a new PHI node for variable VAR at basic block BB. */
356 gphi *
357 create_phi_node (tree var, basic_block bb)
359 gphi *phi = make_phi_node (var, EDGE_COUNT (bb->preds));
361 add_phi_node_to_bb (phi, bb);
362 return phi;
366 /* Add a new argument to PHI node PHI. DEF is the incoming reaching
367 definition and E is the edge through which DEF reaches PHI. The new
368 argument is added at the end of the argument list.
369 If PHI has reached its maximum capacity, add a few slots. In this case,
370 PHI points to the reallocated phi node when we return. */
372 void
373 add_phi_arg (gphi *phi, tree def, edge e, source_location locus)
375 basic_block bb = e->dest;
377 gcc_assert (bb == gimple_bb (phi));
379 /* We resize PHI nodes upon edge creation. We should always have
380 enough room at this point. */
381 gcc_assert (gimple_phi_num_args (phi) <= gimple_phi_capacity (phi));
383 /* We resize PHI nodes upon edge creation. We should always have
384 enough room at this point. */
385 gcc_assert (e->dest_idx < gimple_phi_num_args (phi));
387 /* Copy propagation needs to know what object occur in abnormal
388 PHI nodes. This is a convenient place to record such information. */
389 if (e->flags & EDGE_ABNORMAL)
391 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
392 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
395 SET_PHI_ARG_DEF (phi, e->dest_idx, def);
396 gimple_phi_arg_set_location (phi, e->dest_idx, locus);
400 /* Remove the Ith argument from PHI's argument list. This routine
401 implements removal by swapping the last alternative with the
402 alternative we want to delete and then shrinking the vector, which
403 is consistent with how we remove an edge from the edge vector. */
405 static void
406 remove_phi_arg_num (gphi *phi, int i)
408 int num_elem = gimple_phi_num_args (phi);
410 gcc_assert (i < num_elem);
412 /* Delink the item which is being removed. */
413 delink_imm_use (gimple_phi_arg_imm_use_ptr (phi, i));
415 /* If it is not the last element, move the last element
416 to the element we want to delete, resetting all the links. */
417 if (i != num_elem - 1)
419 use_operand_p old_p, new_p;
420 old_p = gimple_phi_arg_imm_use_ptr (phi, num_elem - 1);
421 new_p = gimple_phi_arg_imm_use_ptr (phi, i);
422 /* Set use on new node, and link into last element's place. */
423 *(new_p->use) = *(old_p->use);
424 relink_imm_use (new_p, old_p);
425 /* Move the location as well. */
426 gimple_phi_arg_set_location (phi, i,
427 gimple_phi_arg_location (phi, num_elem - 1));
430 /* Shrink the vector and return. Note that we do not have to clear
431 PHI_ARG_DEF because the garbage collector will not look at those
432 elements beyond the first PHI_NUM_ARGS elements of the array. */
433 phi->nargs--;
437 /* Remove all PHI arguments associated with edge E. */
439 void
440 remove_phi_args (edge e)
442 gphi_iterator gsi;
444 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
445 remove_phi_arg_num (gsi.phi (),
446 e->dest_idx);
450 /* Remove the PHI node pointed-to by iterator GSI from basic block BB. After
451 removal, iterator GSI is updated to point to the next PHI node in the
452 sequence. If RELEASE_LHS_P is true, the LHS of this PHI node is released
453 into the free pool of SSA names. */
455 void
456 remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p)
458 gimple phi = gsi_stmt (*gsi);
460 if (release_lhs_p)
461 insert_debug_temps_for_defs (gsi);
463 gsi_remove (gsi, false);
465 /* If we are deleting the PHI node, then we should release the
466 SSA_NAME node so that it can be reused. */
467 release_phi_node (phi);
468 if (release_lhs_p)
469 release_ssa_name (gimple_phi_result (phi));
472 /* Remove all the phi nodes from BB. */
474 void
475 remove_phi_nodes (basic_block bb)
477 gphi_iterator gsi;
479 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
480 remove_phi_node (&gsi, true);
482 set_phi_nodes (bb, NULL);
485 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return
486 NULL. */
488 tree
489 degenerate_phi_result (gphi *phi)
491 tree lhs = gimple_phi_result (phi);
492 tree val = NULL;
493 size_t i;
495 /* Ignoring arguments which are the same as LHS, if all the remaining
496 arguments are the same, then the PHI is a degenerate and has the
497 value of that common argument. */
498 for (i = 0; i < gimple_phi_num_args (phi); i++)
500 tree arg = gimple_phi_arg_def (phi, i);
502 if (arg == lhs)
503 continue;
504 else if (!arg)
505 break;
506 else if (!val)
507 val = arg;
508 else if (arg == val)
509 continue;
510 /* We bring in some of operand_equal_p not only to speed things
511 up, but also to avoid crashing when dereferencing the type of
512 a released SSA name. */
513 else if (TREE_CODE (val) != TREE_CODE (arg)
514 || TREE_CODE (val) == SSA_NAME
515 || !operand_equal_p (arg, val, 0))
516 break;
518 return (i == gimple_phi_num_args (phi) ? val : NULL);
521 /* Set PHI nodes of a basic block BB to SEQ. */
523 void
524 set_phi_nodes (basic_block bb, gimple_seq seq)
526 gimple_stmt_iterator i;
528 gcc_checking_assert (!(bb->flags & BB_RTL));
529 bb->il.gimple.phi_nodes = seq;
530 if (seq)
531 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i))
532 gimple_set_bb (gsi_stmt (i), bb);
535 #include "gt-tree-phinodes.h"