]>
git.ipfire.org Git - thirdparty/gcc.git/blob - gcc/tree-phinodes.c
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 /* We do not have to clear a part of the PHI node that stores PHI
203 arguments, which is safe because we tell the garbage collector to
204 scan up to num_args elements in the array of PHI arguments. In
205 other words, the garbage collector will not follow garbage
206 pointers in the unused portion of the array. */
207 memset (phi
, 0, sizeof (struct tree_phi_node
) - sizeof (struct phi_arg_d
));
208 TREE_SET_CODE (phi
, PHI_NODE
);
209 PHI_ARG_CAPACITY (phi
) = len
;
210 TREE_TYPE (phi
) = TREE_TYPE (var
);
211 if (TREE_CODE (var
) == SSA_NAME
)
212 SET_PHI_RESULT (phi
, var
);
214 SET_PHI_RESULT (phi
, make_ssa_name (var
, phi
));
219 /* We no longer need PHI, release it so that it may be reused. */
222 release_phi_node (tree phi
)
225 int len
= PHI_ARG_CAPACITY (phi
);
227 bucket
= len
> NUM_BUCKETS
- 1 ? NUM_BUCKETS
- 1 : len
;
229 PHI_CHAIN (phi
) = free_phinodes
[bucket
];
230 free_phinodes
[bucket
] = phi
;
231 free_phinode_count
++;
234 /* Resize an existing PHI node. The only way is up. Return the
235 possibly relocated phi. */
238 resize_phi_node (tree
*phi
, int len
)
242 int bucket
= NUM_BUCKETS
- 2;
244 gcc_assert (len
>= PHI_ARG_CAPACITY (*phi
));
246 /* Note that OLD_SIZE is guaranteed to be smaller than SIZE. */
247 old_size
= (sizeof (struct tree_phi_node
)
248 + (PHI_ARG_CAPACITY (*phi
) - 1) * sizeof (struct phi_arg_d
));
249 size
= sizeof (struct tree_phi_node
) + (len
- 1) * sizeof (struct phi_arg_d
);
251 if (free_phinode_count
)
252 for (bucket
= len
- 2; bucket
< NUM_BUCKETS
- 2; bucket
++)
253 if (free_phinodes
[bucket
])
256 /* If our free list has an element, then use it. */
257 if (bucket
< NUM_BUCKETS
- 2
258 && PHI_ARG_CAPACITY (free_phinodes
[bucket
]) >= len
)
260 free_phinode_count
--;
261 new_phi
= free_phinodes
[bucket
];
262 free_phinodes
[bucket
] = PHI_CHAIN (free_phinodes
[bucket
]);
263 #ifdef GATHER_STATISTICS
269 new_phi
= ggc_alloc (size
);
270 #ifdef GATHER_STATISTICS
272 tree_node_counts
[(int) phi_kind
]++;
273 tree_node_sizes
[(int) phi_kind
] += size
;
277 memcpy (new_phi
, *phi
, old_size
);
279 PHI_ARG_CAPACITY (new_phi
) = len
;
284 /* Create a new PHI node for variable VAR at basic block BB. */
287 create_phi_node (tree var
, basic_block bb
)
291 phi
= make_phi_node (var
, EDGE_COUNT (bb
->preds
));
293 /* This is a new phi node, so note that is has not yet been
295 PHI_REWRITTEN (phi
) = 0;
297 /* Add the new PHI node to the list of PHI nodes for block BB. */
298 PHI_CHAIN (phi
) = phi_nodes (bb
);
299 bb_ann (bb
)->phi_nodes
= phi
;
301 /* Associate BB to the PHI node. */
302 set_bb_for_stmt (phi
, bb
);
307 /* Add a new argument to PHI node PHI. DEF is the incoming reaching
308 definition and E is the edge through which DEF reaches PHI. The new
309 argument is added at the end of the argument list.
310 If PHI has reached its maximum capacity, add a few slots. In this case,
311 PHI points to the reallocated phi node when we return. */
314 add_phi_arg (tree
*phi
, tree def
, edge e
)
316 int i
= PHI_NUM_ARGS (*phi
);
318 if (i
>= PHI_ARG_CAPACITY (*phi
))
323 /* Resize the phi. Unfortunately, this will relocate it. */
324 resize_phi_node (phi
, ideal_phi_node_len (i
+ 4));
326 /* resize_phi_node will necessarily relocate the phi. */
327 gcc_assert (*phi
!= old_phi
);
329 /* The result of the phi is defined by this phi node. */
330 SSA_NAME_DEF_STMT (PHI_RESULT (*phi
)) = *phi
;
332 /* Extract the basic block for the PHI from the PHI's annotation
333 rather than the edge. This works better as the edge's
334 destination may not currently be the block with the PHI node
335 if we are in the process of threading the edge to a new
337 bb
= bb_for_stmt (*phi
);
339 release_phi_node (old_phi
);
341 /* Update the list head if replacing the first listed phi. */
342 if (phi_nodes (bb
) == old_phi
)
343 bb_ann (bb
)->phi_nodes
= *phi
;
346 /* Traverse the list looking for the phi node to chain to. */
349 for (p
= phi_nodes (bb
);
350 p
&& PHI_CHAIN (p
) != old_phi
;
355 PHI_CHAIN (p
) = *phi
;
359 /* Copy propagation needs to know what object occur in abnormal
360 PHI nodes. This is a convenient place to record such information. */
361 if (e
->flags
& EDGE_ABNORMAL
)
363 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def
) = 1;
364 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (*phi
)) = 1;
367 SET_PHI_ARG_DEF (*phi
, i
, def
);
368 PHI_ARG_EDGE (*phi
, i
) = e
;
369 PHI_ARG_NONZERO (*phi
, i
) = false;
370 PHI_NUM_ARGS (*phi
)++;
373 /* Remove a PHI argument from PHI. BLOCK is the predecessor block where
374 the PHI argument is coming from. */
377 remove_phi_arg (tree phi
, basic_block block
)
379 int i
, num_elem
= PHI_NUM_ARGS (phi
);
381 for (i
= 0; i
< num_elem
; i
++)
385 src_bb
= PHI_ARG_EDGE (phi
, i
)->src
;
389 remove_phi_arg_num (phi
, i
);
396 /* Remove the Ith argument from PHI's argument list. This routine assumes
397 ordering of alternatives in the vector is not important and implements
398 removal by swapping the last alternative with the alternative we want to
399 delete, then shrinking the vector. */
402 remove_phi_arg_num (tree phi
, int i
)
404 int num_elem
= PHI_NUM_ARGS (phi
);
406 gcc_assert (i
< num_elem
);
408 /* If we are not at the last element, switch the last element
409 with the element we want to delete. */
410 if (i
!= num_elem
- 1)
412 SET_PHI_ARG_DEF (phi
, i
, PHI_ARG_DEF (phi
, num_elem
- 1));
413 PHI_ARG_EDGE (phi
, i
) = PHI_ARG_EDGE (phi
, num_elem
- 1);
414 PHI_ARG_NONZERO (phi
, i
) = PHI_ARG_NONZERO (phi
, num_elem
- 1);
417 /* Shrink the vector and return. */
418 SET_PHI_ARG_DEF (phi
, num_elem
- 1, NULL_TREE
);
419 PHI_ARG_EDGE (phi
, num_elem
- 1) = NULL
;
420 PHI_ARG_NONZERO (phi
, num_elem
- 1) = false;
421 PHI_NUM_ARGS (phi
)--;
424 /* Remove PHI node PHI from basic block BB. If PREV is non-NULL, it is
425 used as the node immediately before PHI in the linked list. */
428 remove_phi_node (tree phi
, tree prev
, basic_block bb
)
432 /* Rewire the list if we are given a PREV pointer. */
433 PHI_CHAIN (prev
) = PHI_CHAIN (phi
);
435 /* If we are deleting the PHI node, then we should release the
436 SSA_NAME node so that it can be reused. */
437 release_ssa_name (PHI_RESULT (phi
));
438 release_phi_node (phi
);
440 else if (phi
== phi_nodes (bb
))
442 /* Update the list head if removing the first element. */
443 bb_ann (bb
)->phi_nodes
= PHI_CHAIN (phi
);
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_ssa_name (PHI_RESULT (phi
));
448 release_phi_node (phi
);
452 /* Traverse the list looking for the node to remove. */
455 for (t
= phi_nodes (bb
); t
&& t
!= phi
; t
= PHI_CHAIN (t
))
458 remove_phi_node (t
, prev
, bb
);
463 /* Remove all the PHI nodes for variables in the VARS bitmap. */
466 remove_all_phi_nodes_for (bitmap vars
)
472 /* Build a new PHI list for BB without variables in VARS. */
473 tree phi
, new_phi_list
, last_phi
, next
;
475 last_phi
= new_phi_list
= NULL_TREE
;
476 for (phi
= phi_nodes (bb
), next
= NULL
; phi
; phi
= next
)
478 tree var
= SSA_NAME_VAR (PHI_RESULT (phi
));
480 next
= PHI_CHAIN (phi
);
481 /* Only add PHI nodes for variables not in VARS. */
482 if (!bitmap_bit_p (vars
, var_ann (var
)->uid
))
484 /* If we're not removing this PHI node, then it must have
485 been rewritten by a previous call into the SSA rewriter.
486 Note that fact in PHI_REWRITTEN. */
487 PHI_REWRITTEN (phi
) = 1;
489 if (new_phi_list
== NULL_TREE
)
490 new_phi_list
= last_phi
= phi
;
493 PHI_CHAIN (last_phi
) = phi
;
499 /* If we are deleting the PHI node, then we should release the
500 SSA_NAME node so that it can be reused. */
501 release_ssa_name (PHI_RESULT (phi
));
502 release_phi_node (phi
);
506 /* Make sure the last node in the new list has no successors. */
508 PHI_CHAIN (last_phi
) = NULL_TREE
;
509 bb_ann (bb
)->phi_nodes
= new_phi_list
;
511 #if defined ENABLE_CHECKING
512 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
514 tree var
= SSA_NAME_VAR (PHI_RESULT (phi
));
515 gcc_assert (!bitmap_bit_p (vars
, var_ann (var
)->uid
));
522 #include "gt-tree-phinodes.h"