OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[pf3gnuchains/gcc-fork.git] / gcc / tree-phinodes.c
1 /* Generic routines for manipulating PHIs
2    Copyright (C) 2003 Free Software Foundation, Inc.
3                                                                                 
4 This file is part of GCC.
5                                                                                 
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)
9 any later version.
10                                                                                 
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.
15                                                                                 
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.  */
20                                                                                 
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "varray.h"
28 #include "ggc.h"
29 #include "basic-block.h"
30 #include "tree-flow.h"
31 #include "toplev.h"
32
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.  
36
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.
40
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).
46
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
49    a compilation unit. 
50
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.
54    
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.
58
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
62    nodes.
63
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.
68
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. 
75
76    Note that we can never have less than two PHI argument slots.  Thus,
77    the -2 on all the calculations below.  */
78
79 #define NUM_BUCKETS 10
80 static GTY ((deletable (""))) tree free_phinodes[NUM_BUCKETS - 2];
81 static unsigned long free_phinode_count;
82
83 static int ideal_phi_node_len (int);
84 static void resize_phi_node (tree *, int);
85
86 #ifdef GATHER_STATISTICS
87 unsigned int phi_nodes_reused;
88 unsigned int phi_nodes_created;
89 #endif
90
91 /* Initialize management of PHIs.  */
92
93 void
94 init_phinodes (void)
95 {
96   int i;
97
98   for (i = 0; i < NUM_BUCKETS - 2; i++)
99     free_phinodes[i] = NULL;
100   free_phinode_count = 0;
101 }
102
103 /* Finalize management of PHIs.  */
104
105 void
106 fini_phinodes (void)
107 {
108   int i;
109
110   for (i = 0; i < NUM_BUCKETS - 2; i++)
111     free_phinodes[i] = NULL;
112   free_phinode_count = 0;
113 }
114
115 /* Dump some simple statistics regarding the re-use of PHI nodes.  */
116
117 #ifdef GATHER_STATISTICS
118 void
119 phinodes_print_statistics (void)
120 {
121   fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created);
122   fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused);
123 }
124 #endif
125
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.
129
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.  */
135
136 static int
137 ideal_phi_node_len (int len)
138 {
139   size_t size, new_size;
140   int log2, new_len;
141
142   /* We do not support allocations of less than two PHI argument slots.  */
143   if (len < 2)
144     len = 2;
145
146   /* Compute the number of bytes of the original request.  */
147   size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
148
149   /* Round it up to the next power of two.  */
150   log2 = ceil_log2 (size);
151   new_size = 1 << log2;
152   
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);
156   return new_len;
157 }
158
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
162    definition).  */
163
164 tree
165 make_phi_node (tree var, int len)
166 {
167   tree phi;
168   int size;
169   int bucket = NUM_BUCKETS - 2;
170
171   len = ideal_phi_node_len (len);
172
173   size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
174
175   if (free_phinode_count)
176     for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
177       if (free_phinodes[bucket])
178         break;
179
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)
183     {
184       free_phinode_count--;
185       phi = free_phinodes[bucket];
186       free_phinodes[bucket] = PHI_CHAIN (free_phinodes[bucket]);
187 #ifdef GATHER_STATISTICS
188       phi_nodes_reused++;
189 #endif
190     }
191   else
192     {
193       phi = ggc_alloc (size);
194 #ifdef GATHER_STATISTICS
195       phi_nodes_created++;
196       tree_node_counts[(int) phi_kind]++;
197       tree_node_sizes[(int) phi_kind] += size;
198 #endif
199
200     }
201
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);
208   else
209     SET_PHI_RESULT (phi, make_ssa_name (var, phi));
210
211   return phi;
212 }
213
214 /* We no longer need PHI, release it so that it may be reused.  */
215
216 void
217 release_phi_node (tree phi)
218 {
219   int bucket;
220   int len = PHI_ARG_CAPACITY (phi);
221
222   bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
223   bucket -= 2;
224   PHI_CHAIN (phi) = free_phinodes[bucket];
225   free_phinodes[bucket] = phi;
226   free_phinode_count++;
227 }
228
229 /* Resize an existing PHI node.  The only way is up.  Return the
230    possibly relocated phi.  */
231                                                                                 
232 static void
233 resize_phi_node (tree *phi, int len)
234 {
235   int size, old_size;
236   tree new_phi;
237   int i, old_len, bucket = NUM_BUCKETS - 2;
238
239   gcc_assert (len >= PHI_ARG_CAPACITY (*phi));
240
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);
245
246   if (free_phinode_count)
247     for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
248       if (free_phinodes[bucket])
249         break;
250
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)
254     {
255       free_phinode_count--;
256       new_phi = free_phinodes[bucket];
257       free_phinodes[bucket] = PHI_CHAIN (free_phinodes[bucket]);
258 #ifdef GATHER_STATISTICS
259       phi_nodes_reused++;
260 #endif
261     }
262   else
263     {
264       new_phi = ggc_alloc (size);
265 #ifdef GATHER_STATISTICS
266       phi_nodes_created++;
267       tree_node_counts[(int) phi_kind]++;
268       tree_node_sizes[(int) phi_kind] += size;
269 #endif
270     }
271
272   memcpy (new_phi, *phi, old_size);
273
274   old_len = PHI_ARG_CAPACITY (new_phi);
275   PHI_ARG_CAPACITY (new_phi) = len;
276                                                                                 
277   for (i = old_len; i < len; i++)
278     {
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;
282     }
283
284   *phi = new_phi;
285 }
286
287 /* Create a new PHI node for variable VAR at basic block BB.  */
288
289 tree
290 create_phi_node (tree var, basic_block bb)
291 {
292   tree phi;
293
294   phi = make_phi_node (var, bb_ann (bb)->num_preds);
295
296   /* This is a new phi node, so note that is has not yet been
297      rewritten.  */
298   PHI_REWRITTEN (phi) = 0;
299
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;
303
304   /* Associate BB to the PHI node.  */
305   set_bb_for_stmt (phi, bb);
306
307   return phi;
308 }
309
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.  */
315
316 void
317 add_phi_arg (tree *phi, tree def, edge e)
318 {
319   int i = PHI_NUM_ARGS (*phi);
320
321   if (i >= PHI_ARG_CAPACITY (*phi))
322     {
323       tree old_phi = *phi;
324
325       /* Resize the phi.  Unfortunately, this may also relocate it.  */
326       resize_phi_node (phi, ideal_phi_node_len (i + 4));
327
328       /* The result of the phi is defined by this phi node.  */
329       SSA_NAME_DEF_STMT (PHI_RESULT (*phi)) = *phi;
330
331       /* If the PHI was relocated, update the PHI chains appropriately and
332          release the old PHI node.  */
333       if (*phi != old_phi)
334         {
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);
341
342           release_phi_node (old_phi);
343
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;
347           else
348             {
349               /* Traverse the list looking for the phi node to chain to.  */
350               tree p;
351
352               for (p = phi_nodes (bb);
353                    p && PHI_CHAIN (p) != old_phi;
354                    p = PHI_CHAIN (p))
355                 ;
356
357               gcc_assert (p);
358               PHI_CHAIN (p) = *phi;
359             }
360         }
361     }
362
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)
366     {
367       SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
368       SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (*phi)) = 1;
369     }
370
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)++;
375 }
376
377 /* Remove a PHI argument from PHI.  BLOCK is the predecessor block where
378    the PHI argument is coming from.  */
379
380 void
381 remove_phi_arg (tree phi, basic_block block)
382 {
383   int i, num_elem = PHI_NUM_ARGS (phi);
384
385   for (i = 0; i < num_elem; i++)
386     {
387       basic_block src_bb;
388
389       src_bb = PHI_ARG_EDGE (phi, i)->src;
390
391       if (src_bb == block)
392         {
393           remove_phi_arg_num (phi, i);
394           return;
395         }
396     }
397 }
398
399
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.  */
404
405 void
406 remove_phi_arg_num (tree phi, int i)
407 {
408   int num_elem = PHI_NUM_ARGS (phi);
409
410   /* If we are not at the last element, switch the last element
411      with the element we want to delete.  */
412   if (i != num_elem - 1)
413     {
414       SET_PHI_ARG_DEF (phi, i, PHI_ARG_DEF (phi, num_elem - 1));
415       PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1);
416       PHI_ARG_NONZERO (phi, i) = PHI_ARG_NONZERO (phi, num_elem - 1);
417     }
418
419   /* Shrink the vector and return.  */
420   SET_PHI_ARG_DEF (phi, num_elem - 1, NULL_TREE);
421   PHI_ARG_EDGE (phi, num_elem - 1) = NULL;
422   PHI_ARG_NONZERO (phi, num_elem - 1) = false;
423   PHI_NUM_ARGS (phi)--;
424
425   /* If we removed the last PHI argument, then go ahead and
426      remove the PHI node.  */
427   if (PHI_NUM_ARGS (phi) == 0)
428     remove_phi_node (phi, NULL, bb_for_stmt (phi));
429 }
430
431 /* Remove PHI node PHI from basic block BB.  If PREV is non-NULL, it is
432    used as the node immediately before PHI in the linked list.  */
433
434 void
435 remove_phi_node (tree phi, tree prev, basic_block bb)
436 {
437   if (prev)
438     {
439       /* Rewire the list if we are given a PREV pointer.  */
440       PHI_CHAIN (prev) = PHI_CHAIN (phi);
441
442       /* If we are deleting the PHI node, then we should release the
443          SSA_NAME node so that it can be reused.  */
444       release_ssa_name (PHI_RESULT (phi));
445       release_phi_node (phi);
446     }
447   else if (phi == phi_nodes (bb))
448     {
449       /* Update the list head if removing the first element.  */
450       bb_ann (bb)->phi_nodes = PHI_CHAIN (phi);
451
452       /* If we are deleting the PHI node, then we should release the
453          SSA_NAME node so that it can be reused.  */
454       release_ssa_name (PHI_RESULT (phi));
455       release_phi_node (phi);
456     }
457   else
458     {
459       /* Traverse the list looking for the node to remove.  */
460       tree prev, t;
461       prev = NULL_TREE;
462       for (t = phi_nodes (bb); t && t != phi; t = PHI_CHAIN (t))
463         prev = t;
464       if (t)
465         remove_phi_node (t, prev, bb);
466     }
467 }
468
469
470 /* Remove all the PHI nodes for variables in the VARS bitmap.  */
471
472 void
473 remove_all_phi_nodes_for (bitmap vars)
474 {
475   basic_block bb;
476
477   FOR_EACH_BB (bb)
478     {
479       /* Build a new PHI list for BB without variables in VARS.  */
480       tree phi, new_phi_list, last_phi, next;
481
482       last_phi = new_phi_list = NULL_TREE;
483       for (phi = phi_nodes (bb), next = NULL; phi; phi = next)
484         {
485           tree var = SSA_NAME_VAR (PHI_RESULT (phi));
486
487           next = PHI_CHAIN (phi);
488           /* Only add PHI nodes for variables not in VARS.  */
489           if (!bitmap_bit_p (vars, var_ann (var)->uid))
490             {
491               /* If we're not removing this PHI node, then it must have
492                  been rewritten by a previous call into the SSA rewriter.
493                  Note that fact in PHI_REWRITTEN.  */
494               PHI_REWRITTEN (phi) = 1;
495
496               if (new_phi_list == NULL_TREE)
497                 new_phi_list = last_phi = phi;
498               else
499                 {
500                   PHI_CHAIN (last_phi) = phi;
501                   last_phi = phi;
502                 }
503             }
504           else
505             {
506               /* If we are deleting the PHI node, then we should release the
507                  SSA_NAME node so that it can be reused.  */
508               release_ssa_name (PHI_RESULT (phi));
509               release_phi_node (phi);
510             }
511         }
512
513       /* Make sure the last node in the new list has no successors.  */
514       if (last_phi)
515         PHI_CHAIN (last_phi) = NULL_TREE;
516       bb_ann (bb)->phi_nodes = new_phi_list;
517
518 #if defined ENABLE_CHECKING
519       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
520         {
521           tree var = SSA_NAME_VAR (PHI_RESULT (phi));
522           gcc_assert (!bitmap_bit_p (vars, var_ann (var)->uid));
523         }
524 #endif
525     }
526 }
527
528
529 #include "gt-tree-phinodes.h"
530