1 /* Generic routines for manipulating PHIs
2 Copyright (C) 2003 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 2, or (at your option)
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 COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
23 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "tree-flow.h"
33 /* Rewriting a function into SSA form can create a huge number of PHIs
34 many of which may be thrown away shortly after their creation if jumps
35 were threaded through PHI nodes.
37 While our garbage collection mechanisms will handle this situation, it
38 is extremely wasteful to create nodes and throw them away, especially
39 when the nodes can be reused.
41 For PR 8361, we can significantly reduce the number of nodes allocated
42 and thus the total amount of memory allocated by managing PHIs a
43 little. This additionally helps reduce the amount of work done by the
44 garbage collector. Similar results have been seen on a wider variety
45 of tests (such as the compiler itself).
47 Right now we maintain our free list on a per-function basis. It may
48 or may not make sense to maintain the free list for the duration of
51 We could also use a zone allocator for these objects since they have
52 a very well defined lifetime. If someone wants to experiment with that
53 this is the place to try it.
55 PHI nodes have different sizes, so we can't have a single list of all
56 the PHI nodes as it would be too expensive to walk down that list to
57 find a PHI of a suitable size.
59 Instead we have an array of lists of free PHI nodes. The array is
60 indexed by the number of PHI alternatives that PHI node can hold.
61 Except for the last array member, which holds all remaining PHI
64 So to find a free PHI node, we compute its index into the free PHI
65 node array and see if there are any elements with an exact match.
66 If so, then we are done. Otherwise, we test the next larger size
67 up and continue until we are in the last array element.
69 We do not actually walk members of the last array element. While it
70 might allow us to pick up a few reusable PHI nodes, it could potentially
71 be very expensive if the program has released a bunch of large PHI nodes,
72 but keeps asking for even larger PHI nodes. Experiments have shown that
73 walking the elements of the last array entry would result in finding less
74 than .1% additional reusable PHI nodes.
76 Note that we can never have less than two PHI argument slots. Thus,
77 the -2 on all the calculations below. */
79 #define NUM_BUCKETS 10
80 static GTY ((deletable (""))) tree free_phinodes
[NUM_BUCKETS
- 2];
81 static unsigned long free_phinode_count
;
83 static int ideal_phi_node_len (int);
84 static void resize_phi_node (tree
*, int);
86 #ifdef GATHER_STATISTICS
87 unsigned int phi_nodes_reused
;
88 unsigned int phi_nodes_created
;
91 /* Initialize management of PHIs. */
98 for (i
= 0; i
< NUM_BUCKETS
- 2; i
++)
99 free_phinodes
[i
] = NULL
;
100 free_phinode_count
= 0;
103 /* Finalize management of PHIs. */
110 for (i
= 0; i
< NUM_BUCKETS
- 2; i
++)
111 free_phinodes
[i
] = NULL
;
112 free_phinode_count
= 0;
115 /* Dump some simple statistics regarding the re-use of PHI nodes. */
117 #ifdef GATHER_STATISTICS
119 phinodes_print_statistics (void)
121 fprintf (stderr
, "PHI nodes allocated: %u\n", phi_nodes_created
);
122 fprintf (stderr
, "PHI nodes reused: %u\n", phi_nodes_reused
);
126 /* Given LEN, the original number of requested PHI arguments, return
127 a new, "ideal" length for the PHI node. The "ideal" length rounds
128 the total size of the PHI node up to the next power of two bytes.
130 Rounding up will not result in wasting any memory since the size request
131 will be rounded up by the GC system anyway. [ Note this is not entirely
132 true since the original length might have fit on one of the special
133 GC pages. ] By rounding up, we may avoid the need to reallocate the
134 PHI node later if we increase the number of arguments for the PHI. */
137 ideal_phi_node_len (int len
)
139 size_t size
, new_size
;
142 /* We do not support allocations of less than two PHI argument slots. */
146 /* Compute the number of bytes of the original request. */
147 size
= sizeof (struct tree_phi_node
) + (len
- 1) * sizeof (struct phi_arg_d
);
149 /* Round it up to the next power of two. */
150 log2
= ceil_log2 (size
);
151 new_size
= 1 << log2
;
153 /* Now compute and return the number of PHI argument slots given an
154 ideal size allocation. */
155 new_len
= len
+ (new_size
- size
) / sizeof (struct phi_arg_d
);
159 /* Return a PHI node for variable VAR defined in statement STMT.
160 STMT may be an empty statement for artificial references (e.g., default
161 definitions created when a variable is used without a preceding
165 make_phi_node (tree var
, int len
)
169 int bucket
= NUM_BUCKETS
- 2;
171 len
= ideal_phi_node_len (len
);
173 size
= sizeof (struct tree_phi_node
) + (len
- 1) * sizeof (struct phi_arg_d
);
175 if (free_phinode_count
)
176 for (bucket
= len
- 2; bucket
< NUM_BUCKETS
- 2; bucket
++)
177 if (free_phinodes
[bucket
])
180 /* If our free list has an element, then use it. */
181 if (bucket
< NUM_BUCKETS
- 2
182 && PHI_ARG_CAPACITY (free_phinodes
[bucket
]) >= len
)
184 free_phinode_count
--;
185 phi
= free_phinodes
[bucket
];
186 free_phinodes
[bucket
] = PHI_CHAIN (free_phinodes
[bucket
]);
187 #ifdef GATHER_STATISTICS
193 phi
= ggc_alloc (size
);
194 #ifdef GATHER_STATISTICS
196 tree_node_counts
[(int) phi_kind
]++;
197 tree_node_sizes
[(int) phi_kind
] += size
;
202 memset (phi
, 0, size
);
203 TREE_SET_CODE (phi
, PHI_NODE
);
204 PHI_ARG_CAPACITY (phi
) = len
;
205 TREE_TYPE (phi
) = TREE_TYPE (var
);
206 if (TREE_CODE (var
) == SSA_NAME
)
207 SET_PHI_RESULT (phi
, var
);
209 SET_PHI_RESULT (phi
, make_ssa_name (var
, phi
));
214 /* We no longer need PHI, release it so that it may be reused. */
217 release_phi_node (tree phi
)
220 int len
= PHI_ARG_CAPACITY (phi
);
222 bucket
= len
> NUM_BUCKETS
- 1 ? NUM_BUCKETS
- 1 : len
;
224 PHI_CHAIN (phi
) = free_phinodes
[bucket
];
225 free_phinodes
[bucket
] = phi
;
226 free_phinode_count
++;
229 /* Resize an existing PHI node. The only way is up. Return the
230 possibly relocated phi. */
233 resize_phi_node (tree
*phi
, int len
)
237 int i
, old_len
, bucket
= NUM_BUCKETS
- 2;
239 gcc_assert (len
>= PHI_ARG_CAPACITY (*phi
));
241 /* Note that OLD_SIZE is guaranteed to be smaller than SIZE. */
242 old_size
= (sizeof (struct tree_phi_node
)
243 + (PHI_ARG_CAPACITY (*phi
) - 1) * sizeof (struct phi_arg_d
));
244 size
= sizeof (struct tree_phi_node
) + (len
- 1) * sizeof (struct phi_arg_d
);
246 if (free_phinode_count
)
247 for (bucket
= len
- 2; bucket
< NUM_BUCKETS
- 2; bucket
++)
248 if (free_phinodes
[bucket
])
251 /* If our free list has an element, then use it. */
252 if (bucket
< NUM_BUCKETS
- 2
253 && PHI_ARG_CAPACITY (free_phinodes
[bucket
]) >= len
)
255 free_phinode_count
--;
256 new_phi
= free_phinodes
[bucket
];
257 free_phinodes
[bucket
] = PHI_CHAIN (free_phinodes
[bucket
]);
258 #ifdef GATHER_STATISTICS
264 new_phi
= ggc_alloc (size
);
265 #ifdef GATHER_STATISTICS
267 tree_node_counts
[(int) phi_kind
]++;
268 tree_node_sizes
[(int) phi_kind
] += size
;
272 memcpy (new_phi
, *phi
, old_size
);
274 old_len
= PHI_ARG_CAPACITY (new_phi
);
275 PHI_ARG_CAPACITY (new_phi
) = len
;
277 for (i
= old_len
; i
< len
; i
++)
279 SET_PHI_ARG_DEF (new_phi
, i
, NULL_TREE
);
280 PHI_ARG_EDGE (new_phi
, i
) = NULL
;
281 PHI_ARG_NONZERO (new_phi
, i
) = false;
287 /* Create a new PHI node for variable VAR at basic block BB. */
290 create_phi_node (tree var
, basic_block bb
)
294 phi
= make_phi_node (var
, EDGE_COUNT (bb
->preds
));
296 /* This is a new phi node, so note that is has not yet been
298 PHI_REWRITTEN (phi
) = 0;
300 /* Add the new PHI node to the list of PHI nodes for block BB. */
301 PHI_CHAIN (phi
) = phi_nodes (bb
);
302 bb_ann (bb
)->phi_nodes
= phi
;
304 /* Associate BB to the PHI node. */
305 set_bb_for_stmt (phi
, bb
);
310 /* Add a new argument to PHI node PHI. DEF is the incoming reaching
311 definition and E is the edge through which DEF reaches PHI. The new
312 argument is added at the end of the argument list.
313 If PHI has reached its maximum capacity, add a few slots. In this case,
314 PHI points to the reallocated phi node when we return. */
317 add_phi_arg (tree
*phi
, tree def
, edge e
)
319 int i
= PHI_NUM_ARGS (*phi
);
321 if (i
>= PHI_ARG_CAPACITY (*phi
))
325 /* Resize the phi. Unfortunately, this may also relocate it. */
326 resize_phi_node (phi
, ideal_phi_node_len (i
+ 4));
328 /* The result of the phi is defined by this phi node. */
329 SSA_NAME_DEF_STMT (PHI_RESULT (*phi
)) = *phi
;
331 /* If the PHI was relocated, update the PHI chains appropriately and
332 release the old PHI node. */
335 /* Extract the basic block for the PHI from the PHI's annotation
336 rather than the edge. This works better as the edge's
337 destination may not currently be the block with the PHI
338 node if we are in the process of threading the edge to
339 a new destination. */
340 basic_block bb
= bb_for_stmt (*phi
);
342 release_phi_node (old_phi
);
344 /* Update the list head if replacing the first listed phi. */
345 if (phi_nodes (bb
) == old_phi
)
346 bb_ann (bb
)->phi_nodes
= *phi
;
349 /* Traverse the list looking for the phi node to chain to. */
352 for (p
= phi_nodes (bb
);
353 p
&& PHI_CHAIN (p
) != old_phi
;
358 PHI_CHAIN (p
) = *phi
;
363 /* Copy propagation needs to know what object occur in abnormal
364 PHI nodes. This is a convenient place to record such information. */
365 if (e
->flags
& EDGE_ABNORMAL
)
367 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
) = 1;
368 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (*phi
)) = 1;
371 SET_PHI_ARG_DEF (*phi
, i
, def
);
372 PHI_ARG_EDGE (*phi
, i
) = e
;
373 PHI_ARG_NONZERO (*phi
, i
) = false;
374 PHI_NUM_ARGS (*phi
)++;
377 /* Remove a PHI argument from PHI. BLOCK is the predecessor block where
378 the PHI argument is coming from. */
381 remove_phi_arg (tree phi
, basic_block block
)
383 int i
, num_elem
= PHI_NUM_ARGS (phi
);
385 for (i
= 0; i
< num_elem
; i
++)
389 src_bb
= PHI_ARG_EDGE (phi
, i
)->src
;
393 remove_phi_arg_num (phi
, i
);
400 /* Remove the Ith argument from PHI's argument list. This routine assumes
401 ordering of alternatives in the vector is not important and implements
402 removal by swapping the last alternative with the alternative we want to
403 delete, then shrinking the vector. */
406 remove_phi_arg_num (tree phi
, int i
)
408 int num_elem
= PHI_NUM_ARGS (phi
);
410 gcc_assert (i
< num_elem
);
412 /* If we are not at the last element, switch the last element
413 with the element we want to delete. */
414 if (i
!= num_elem
- 1)
416 SET_PHI_ARG_DEF (phi
, i
, PHI_ARG_DEF (phi
, num_elem
- 1));
417 PHI_ARG_EDGE (phi
, i
) = PHI_ARG_EDGE (phi
, num_elem
- 1);
418 PHI_ARG_NONZERO (phi
, i
) = PHI_ARG_NONZERO (phi
, num_elem
- 1);
421 /* Shrink the vector and return. */
422 SET_PHI_ARG_DEF (phi
, num_elem
- 1, NULL_TREE
);
423 PHI_ARG_EDGE (phi
, num_elem
- 1) = NULL
;
424 PHI_ARG_NONZERO (phi
, num_elem
- 1) = false;
425 PHI_NUM_ARGS (phi
)--;
428 /* Remove PHI node PHI from basic block BB. If PREV is non-NULL, it is
429 used as the node immediately before PHI in the linked list. */
432 remove_phi_node (tree phi
, tree prev
, basic_block bb
)
436 /* Rewire the list if we are given a PREV pointer. */
437 PHI_CHAIN (prev
) = PHI_CHAIN (phi
);
439 /* If we are deleting the PHI node, then we should release the
440 SSA_NAME node so that it can be reused. */
441 release_ssa_name (PHI_RESULT (phi
));
442 release_phi_node (phi
);
444 else if (phi
== phi_nodes (bb
))
446 /* Update the list head if removing the first element. */
447 bb_ann (bb
)->phi_nodes
= PHI_CHAIN (phi
);
449 /* If we are deleting the PHI node, then we should release the
450 SSA_NAME node so that it can be reused. */
451 release_ssa_name (PHI_RESULT (phi
));
452 release_phi_node (phi
);
456 /* Traverse the list looking for the node to remove. */
459 for (t
= phi_nodes (bb
); t
&& t
!= phi
; t
= PHI_CHAIN (t
))
462 remove_phi_node (t
, prev
, bb
);
467 /* Remove all the PHI nodes for variables in the VARS bitmap. */
470 remove_all_phi_nodes_for (bitmap vars
)
476 /* Build a new PHI list for BB without variables in VARS. */
477 tree phi
, new_phi_list
, last_phi
, next
;
479 last_phi
= new_phi_list
= NULL_TREE
;
480 for (phi
= phi_nodes (bb
), next
= NULL
; phi
; phi
= next
)
482 tree var
= SSA_NAME_VAR (PHI_RESULT (phi
));
484 next
= PHI_CHAIN (phi
);
485 /* Only add PHI nodes for variables not in VARS. */
486 if (!bitmap_bit_p (vars
, var_ann (var
)->uid
))
488 /* If we're not removing this PHI node, then it must have
489 been rewritten by a previous call into the SSA rewriter.
490 Note that fact in PHI_REWRITTEN. */
491 PHI_REWRITTEN (phi
) = 1;
493 if (new_phi_list
== NULL_TREE
)
494 new_phi_list
= last_phi
= phi
;
497 PHI_CHAIN (last_phi
) = phi
;
503 /* If we are deleting the PHI node, then we should release the
504 SSA_NAME node so that it can be reused. */
505 release_ssa_name (PHI_RESULT (phi
));
506 release_phi_node (phi
);
510 /* Make sure the last node in the new list has no successors. */
512 PHI_CHAIN (last_phi
) = NULL_TREE
;
513 bb_ann (bb
)->phi_nodes
= new_phi_list
;
515 #if defined ENABLE_CHECKING
516 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
518 tree var
= SSA_NAME_VAR (PHI_RESULT (phi
));
519 gcc_assert (!bitmap_bit_p (vars
, var_ann (var
)->uid
));
526 #include "gt-tree-phinodes.h"