Daily bump.
[official-gcc.git] / gcc / tree-phinodes.c
blob5d74765e090f04a99ec599c7a9d16acd1e4a33a2
1 /* Generic routines for manipulating PHIs
2 Copyright (C) 2003, 2005, 2007 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 "rtl.h"
26 #include "varray.h"
27 #include "ggc.h"
28 #include "basic-block.h"
29 #include "tree-flow.h"
30 #include "toplev.h"
32 /* Rewriting a function into SSA form can create a huge number of PHIs
33 many of which may be thrown away shortly after their creation if jumps
34 were threaded through PHI nodes.
36 While our garbage collection mechanisms will handle this situation, it
37 is extremely wasteful to create nodes and throw them away, especially
38 when the nodes can be reused.
40 For PR 8361, we can significantly reduce the number of nodes allocated
41 and thus the total amount of memory allocated by managing PHIs a
42 little. This additionally helps reduce the amount of work done by the
43 garbage collector. Similar results have been seen on a wider variety
44 of tests (such as the compiler itself).
46 Right now we maintain our free list on a per-function basis. It may
47 or may not make sense to maintain the free list for the duration of
48 a compilation unit.
50 We could also use a zone allocator for these objects since they have
51 a very well defined lifetime. If someone wants to experiment with that
52 this is the place to try it.
54 PHI nodes have different sizes, so we can't have a single list of all
55 the PHI nodes as it would be too expensive to walk down that list to
56 find a PHI of a suitable size.
58 Instead we have an array of lists of free PHI nodes. The array is
59 indexed by the number of PHI alternatives that PHI node can hold.
60 Except for the last array member, which holds all remaining PHI
61 nodes.
63 So to find a free PHI node, we compute its index into the free PHI
64 node array and see if there are any elements with an exact match.
65 If so, then we are done. Otherwise, we test the next larger size
66 up and continue until we are in the last array element.
68 We do not actually walk members of the last array element. While it
69 might allow us to pick up a few reusable PHI nodes, it could potentially
70 be very expensive if the program has released a bunch of large PHI nodes,
71 but keeps asking for even larger PHI nodes. Experiments have shown that
72 walking the elements of the last array entry would result in finding less
73 than .1% additional reusable PHI nodes.
75 Note that we can never have less than two PHI argument slots. Thus,
76 the -2 on all the calculations below. */
78 #define NUM_BUCKETS 10
79 static GTY ((deletable (""))) tree free_phinodes[NUM_BUCKETS - 2];
80 static unsigned long free_phinode_count;
82 static int ideal_phi_node_len (int);
83 static void resize_phi_node (tree *, int);
85 #ifdef GATHER_STATISTICS
86 unsigned int phi_nodes_reused;
87 unsigned int phi_nodes_created;
88 #endif
90 /* Initialize management of PHIs. */
92 void
93 init_phinodes (void)
95 int i;
97 for (i = 0; i < NUM_BUCKETS - 2; i++)
98 free_phinodes[i] = NULL;
99 free_phinode_count = 0;
102 /* Finalize management of PHIs. */
104 void
105 fini_phinodes (void)
107 int i;
109 for (i = 0; i < NUM_BUCKETS - 2; i++)
110 free_phinodes[i] = NULL;
111 free_phinode_count = 0;
114 /* Dump some simple statistics regarding the re-use of PHI nodes. */
116 #ifdef GATHER_STATISTICS
117 void
118 phinodes_print_statistics (void)
120 fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created);
121 fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused);
123 #endif
125 /* Allocate a PHI node with at least LEN arguments. If the free list
126 happens to contain a PHI node with LEN arguments or more, return
127 that one. */
129 static inline tree
130 allocate_phi_node (int len)
132 tree phi;
133 int bucket = NUM_BUCKETS - 2;
134 int size = (sizeof (struct tree_phi_node)
135 + (len - 1) * sizeof (struct phi_arg_d));
137 if (free_phinode_count)
138 for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
139 if (free_phinodes[bucket])
140 break;
142 /* If our free list has an element, then use it. */
143 if (bucket < NUM_BUCKETS - 2
144 && PHI_ARG_CAPACITY (free_phinodes[bucket]) >= len)
146 free_phinode_count--;
147 phi = free_phinodes[bucket];
148 free_phinodes[bucket] = PHI_CHAIN (free_phinodes[bucket]);
149 #ifdef GATHER_STATISTICS
150 phi_nodes_reused++;
151 #endif
153 else
155 phi = ggc_alloc (size);
156 #ifdef GATHER_STATISTICS
157 phi_nodes_created++;
158 tree_node_counts[(int) phi_kind]++;
159 tree_node_sizes[(int) phi_kind] += size;
160 #endif
163 return phi;
166 /* Given LEN, the original number of requested PHI arguments, return
167 a new, "ideal" length for the PHI node. The "ideal" length rounds
168 the total size of the PHI node up to the next power of two bytes.
170 Rounding up will not result in wasting any memory since the size request
171 will be rounded up by the GC system anyway. [ Note this is not entirely
172 true since the original length might have fit on one of the special
173 GC pages. ] By rounding up, we may avoid the need to reallocate the
174 PHI node later if we increase the number of arguments for the PHI. */
176 static int
177 ideal_phi_node_len (int len)
179 size_t size, new_size;
180 int log2, new_len;
182 /* We do not support allocations of less than two PHI argument slots. */
183 if (len < 2)
184 len = 2;
186 /* Compute the number of bytes of the original request. */
187 size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
189 /* Round it up to the next power of two. */
190 log2 = ceil_log2 (size);
191 new_size = 1 << log2;
193 /* Now compute and return the number of PHI argument slots given an
194 ideal size allocation. */
195 new_len = len + (new_size - size) / sizeof (struct phi_arg_d);
196 return new_len;
200 /* Return a PHI node with LEN argument slots for variable VAR. */
202 static tree
203 make_phi_node (tree var, int len)
205 tree phi;
206 int capacity, i;
208 capacity = ideal_phi_node_len (len);
210 phi = allocate_phi_node (capacity);
212 /* We need to clear the entire PHI node, including the argument
213 portion, because we represent a "missing PHI argument" by placing
214 NULL_TREE in PHI_ARG_DEF. */
215 memset (phi, 0, (sizeof (struct tree_phi_node) - sizeof (struct phi_arg_d)
216 + sizeof (struct phi_arg_d) * len));
217 TREE_SET_CODE (phi, PHI_NODE);
218 PHI_NUM_ARGS (phi) = len;
219 PHI_ARG_CAPACITY (phi) = capacity;
220 if (TREE_CODE (var) == SSA_NAME)
221 SET_PHI_RESULT (phi, var);
222 else
223 SET_PHI_RESULT (phi, make_ssa_name (var, phi));
225 for (i = 0; i < capacity; i++)
227 use_operand_p imm;
228 imm = &(PHI_ARG_IMM_USE_NODE (phi, i));
229 imm->use = &(PHI_ARG_DEF_TREE (phi, i));
230 imm->prev = NULL;
231 imm->next = NULL;
232 imm->stmt = phi;
235 return phi;
238 /* We no longer need PHI, release it so that it may be reused. */
240 void
241 release_phi_node (tree phi)
243 int bucket;
244 int len = PHI_ARG_CAPACITY (phi);
245 int x;
247 for (x = 0; x < PHI_NUM_ARGS (phi); x++)
249 use_operand_p imm;
250 imm = &(PHI_ARG_IMM_USE_NODE (phi, x));
251 delink_imm_use (imm);
254 bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
255 bucket -= 2;
256 PHI_CHAIN (phi) = free_phinodes[bucket];
257 free_phinodes[bucket] = phi;
258 free_phinode_count++;
261 /* Resize an existing PHI node. The only way is up. Return the
262 possibly relocated phi. */
264 static void
265 resize_phi_node (tree *phi, int len)
267 int old_size, i;
268 tree new_phi;
270 gcc_assert (len > PHI_ARG_CAPACITY (*phi));
272 /* The garbage collector will not look at the PHI node beyond the
273 first PHI_NUM_ARGS elements. Therefore, all we have to copy is a
274 portion of the PHI node currently in use. */
275 old_size = (sizeof (struct tree_phi_node)
276 + (PHI_NUM_ARGS (*phi) - 1) * sizeof (struct phi_arg_d));
278 new_phi = allocate_phi_node (len);
280 memcpy (new_phi, *phi, old_size);
282 for (i = 0; i < PHI_NUM_ARGS (new_phi); i++)
284 use_operand_p imm, old_imm;
285 imm = &(PHI_ARG_IMM_USE_NODE (new_phi, i));
286 old_imm = &(PHI_ARG_IMM_USE_NODE (*phi, i));
287 imm->use = &(PHI_ARG_DEF_TREE (new_phi, i));
288 relink_imm_use_stmt (imm, old_imm, new_phi);
291 PHI_ARG_CAPACITY (new_phi) = len;
293 for (i = PHI_NUM_ARGS (new_phi); i < len; i++)
295 use_operand_p imm;
296 imm = &(PHI_ARG_IMM_USE_NODE (new_phi, i));
297 imm->use = &(PHI_ARG_DEF_TREE (new_phi, i));
298 imm->prev = NULL;
299 imm->next = NULL;
300 imm->stmt = new_phi;
303 *phi = new_phi;
306 /* Reserve PHI arguments for a new edge to basic block BB. */
308 void
309 reserve_phi_args_for_new_edge (basic_block bb)
311 tree *loc;
312 int len = EDGE_COUNT (bb->preds);
313 int cap = ideal_phi_node_len (len + 4);
315 for (loc = phi_nodes_ptr (bb);
316 *loc;
317 loc = &PHI_CHAIN (*loc))
319 if (len > PHI_ARG_CAPACITY (*loc))
321 tree old_phi = *loc;
323 resize_phi_node (loc, cap);
325 /* The result of the phi is defined by this phi node. */
326 SSA_NAME_DEF_STMT (PHI_RESULT (*loc)) = *loc;
328 release_phi_node (old_phi);
331 /* We represent a "missing PHI argument" by placing NULL_TREE in
332 the corresponding slot. If PHI arguments were added
333 immediately after an edge is created, this zeroing would not
334 be necessary, but unfortunately this is not the case. For
335 example, the loop optimizer duplicates several basic blocks,
336 redirects edges, and then fixes up PHI arguments later in
337 batch. */
338 SET_PHI_ARG_DEF (*loc, len - 1, NULL_TREE);
340 PHI_NUM_ARGS (*loc)++;
345 /* Create a new PHI node for variable VAR at basic block BB. */
347 tree
348 create_phi_node (tree var, basic_block bb)
350 tree phi;
352 phi = make_phi_node (var, EDGE_COUNT (bb->preds));
354 /* Add the new PHI node to the list of PHI nodes for block BB. */
355 PHI_CHAIN (phi) = phi_nodes (bb);
356 set_phi_nodes (bb, phi);
358 /* Associate BB to the PHI node. */
359 set_bb_for_stmt (phi, bb);
361 return phi;
365 /* Add a new argument to PHI node PHI. DEF is the incoming reaching
366 definition and E is the edge through which DEF reaches PHI. The new
367 argument is added at the end of the argument list.
368 If PHI has reached its maximum capacity, add a few slots. In this case,
369 PHI points to the reallocated phi node when we return. */
371 void
372 add_phi_arg (tree phi, tree def, edge e)
374 basic_block bb = e->dest;
376 gcc_assert (bb == bb_for_stmt (phi));
378 /* We resize PHI nodes upon edge creation. We should always have
379 enough room at this point. */
380 gcc_assert (PHI_NUM_ARGS (phi) <= PHI_ARG_CAPACITY (phi));
382 /* We resize PHI nodes upon edge creation. We should always have
383 enough room at this point. */
384 gcc_assert (e->dest_idx < (unsigned int) PHI_NUM_ARGS (phi));
386 /* Copy propagation needs to know what object occur in abnormal
387 PHI nodes. This is a convenient place to record such information. */
388 if (e->flags & EDGE_ABNORMAL)
390 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
391 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
394 SET_PHI_ARG_DEF (phi, e->dest_idx, def);
398 /* Remove the Ith argument from PHI's argument list. This routine
399 implements removal by swapping the last alternative with the
400 alternative we want to delete and then shrinking the vector, which
401 is consistent with how we remove an edge from the edge vector. */
403 static void
404 remove_phi_arg_num (tree phi, int i)
406 int num_elem = PHI_NUM_ARGS (phi);
408 gcc_assert (i < num_elem);
410 /* Delink the item which is being removed. */
411 delink_imm_use (&(PHI_ARG_IMM_USE_NODE (phi, i)));
413 /* If it is not the last element, move the last element
414 to the element we want to delete, resetting all the links. */
415 if (i != num_elem - 1)
417 use_operand_p old_p, new_p;
418 old_p = &PHI_ARG_IMM_USE_NODE (phi, num_elem - 1);
419 new_p = &PHI_ARG_IMM_USE_NODE (phi, i);
420 /* Set use on new node, and link into last element's place. */
421 *(new_p->use) = *(old_p->use);
422 relink_imm_use (new_p, old_p);
425 /* Shrink the vector and return. Note that we do not have to clear
426 PHI_ARG_DEF because the garbage collector will not look at those
427 elements beyond the first PHI_NUM_ARGS elements of the array. */
428 PHI_NUM_ARGS (phi)--;
432 /* Remove all PHI arguments associated with edge E. */
434 void
435 remove_phi_args (edge e)
437 tree phi;
439 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
440 remove_phi_arg_num (phi, e->dest_idx);
444 /* Remove PHI node PHI from basic block BB. If PREV is non-NULL, it is
445 used as the node immediately before PHI in the linked list. If
446 RELEASE_LHS_P is true, the LHS of this PHI node is released into
447 the free pool of SSA names. */
449 void
450 remove_phi_node (tree phi, tree prev, bool release_lhs_p)
452 tree *loc;
454 if (prev)
456 loc = &PHI_CHAIN (prev);
458 else
460 for (loc = phi_nodes_ptr (bb_for_stmt (phi));
461 *loc != phi;
462 loc = &PHI_CHAIN (*loc))
466 /* Remove PHI from the chain. */
467 *loc = PHI_CHAIN (phi);
469 /* If we are deleting the PHI node, then we should release the
470 SSA_NAME node so that it can be reused. */
471 release_phi_node (phi);
472 if (release_lhs_p)
473 release_ssa_name (PHI_RESULT (phi));
477 /* Reverse the order of PHI nodes in the chain PHI.
478 Return the new head of the chain (old last PHI node). */
480 tree
481 phi_reverse (tree phi)
483 tree prev = NULL_TREE, next;
484 for (; phi; phi = next)
486 next = PHI_CHAIN (phi);
487 PHI_CHAIN (phi) = prev;
488 prev = phi;
490 return prev;
493 #include "gt-tree-phinodes.h"