OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-phinodes.c] - Blame information for rev 853

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Generic routines for manipulating PHIs
2
   Copyright (C) 2003, 2005, 2007 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 3, 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 COPYING3.  If not see
18
<http://www.gnu.org/licenses/>.  */
19
 
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"
31
 
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.
35
 
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.
39
 
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).
45
 
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.
49
 
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.
53
 
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.
57
 
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.
62
 
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.
67
 
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.
74
 
75
   Note that we can never have less than two PHI argument slots.  Thus,
76
   the -2 on all the calculations below.  */
77
 
78
#define NUM_BUCKETS 10
79
static GTY ((deletable (""))) tree free_phinodes[NUM_BUCKETS - 2];
80
static unsigned long free_phinode_count;
81
 
82
static int ideal_phi_node_len (int);
83
static void resize_phi_node (tree *, int);
84
 
85
#ifdef GATHER_STATISTICS
86
unsigned int phi_nodes_reused;
87
unsigned int phi_nodes_created;
88
#endif
89
 
90
/* Initialize management of PHIs.  */
91
 
92
void
93
init_phinodes (void)
94
{
95
  int i;
96
 
97
  for (i = 0; i < NUM_BUCKETS - 2; i++)
98
    free_phinodes[i] = NULL;
99
  free_phinode_count = 0;
100
}
101
 
102
/* Finalize management of PHIs.  */
103
 
104
void
105
fini_phinodes (void)
106
{
107
  int i;
108
 
109
  for (i = 0; i < NUM_BUCKETS - 2; i++)
110
    free_phinodes[i] = NULL;
111
  free_phinode_count = 0;
112
}
113
 
114
/* Dump some simple statistics regarding the re-use of PHI nodes.  */
115
 
116
#ifdef GATHER_STATISTICS
117
void
118
phinodes_print_statistics (void)
119
{
120
  fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created);
121
  fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused);
122
}
123
#endif
124
 
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.  */
128
 
129
static inline tree
130
allocate_phi_node (int len)
131
{
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));
136
 
137
  if (free_phinode_count)
138
    for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
139
      if (free_phinodes[bucket])
140
        break;
141
 
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)
145
    {
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
152
    }
153
  else
154
    {
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
161
    }
162
 
163
  return phi;
164
}
165
 
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.
169
 
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.  */
175
 
176
static int
177
ideal_phi_node_len (int len)
178
{
179
  size_t size, new_size;
180
  int log2, new_len;
181
 
182
  /* We do not support allocations of less than two PHI argument slots.  */
183
  if (len < 2)
184
    len = 2;
185
 
186
  /* Compute the number of bytes of the original request.  */
187
  size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
188
 
189
  /* Round it up to the next power of two.  */
190
  log2 = ceil_log2 (size);
191
  new_size = 1 << log2;
192
 
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;
197
}
198
 
199
 
200
/* Return a PHI node with LEN argument slots for variable VAR.  */
201
 
202
static tree
203
make_phi_node (tree var, int len)
204
{
205
  tree phi;
206
  int capacity, i;
207
 
208
  capacity = ideal_phi_node_len (len);
209
 
210
  phi = allocate_phi_node (capacity);
211
 
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
  TREE_TYPE (phi) = TREE_TYPE (var);
221
  if (TREE_CODE (var) == SSA_NAME)
222
    SET_PHI_RESULT (phi, var);
223
  else
224
    SET_PHI_RESULT (phi, make_ssa_name (var, phi));
225
 
226
  for (i = 0; i < capacity; i++)
227
    {
228
      use_operand_p  imm;
229
      imm = &(PHI_ARG_IMM_USE_NODE (phi, i));
230
      imm->use = &(PHI_ARG_DEF_TREE (phi, i));
231
      imm->prev = NULL;
232
      imm->next = NULL;
233
      imm->stmt = phi;
234
    }
235
  return phi;
236
}
237
 
238
/* We no longer need PHI, release it so that it may be reused.  */
239
 
240
void
241
release_phi_node (tree phi)
242
{
243
  int bucket;
244
  int len = PHI_ARG_CAPACITY (phi);
245
  int x;
246
 
247
  for (x = 0; x < PHI_NUM_ARGS (phi); x++)
248
    {
249
      use_operand_p  imm;
250
      imm = &(PHI_ARG_IMM_USE_NODE (phi, x));
251
      delink_imm_use (imm);
252
    }
253
 
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++;
259
}
260
 
261
/* Resize an existing PHI node.  The only way is up.  Return the
262
   possibly relocated phi.  */
263
 
264
static void
265
resize_phi_node (tree *phi, int len)
266
{
267
  int old_size, i;
268
  tree new_phi;
269
 
270
  gcc_assert (len > PHI_ARG_CAPACITY (*phi));
271
 
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));
277
 
278
  new_phi = allocate_phi_node (len);
279
 
280
  memcpy (new_phi, *phi, old_size);
281
 
282
  for (i = 0; i < PHI_NUM_ARGS (new_phi); i++)
283
    {
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);
289
    }
290
 
291
  PHI_ARG_CAPACITY (new_phi) = len;
292
 
293
  for (i = PHI_NUM_ARGS (new_phi); i < len; i++)
294
    {
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;
301
    }
302
 
303
 
304
  *phi = new_phi;
305
}
306
 
307
/* Reserve PHI arguments for a new edge to basic block BB.  */
308
 
309
void
310
reserve_phi_args_for_new_edge (basic_block bb)
311
{
312
  tree *loc;
313
  int len = EDGE_COUNT (bb->preds);
314
  int cap = ideal_phi_node_len (len + 4);
315
 
316
  for (loc = &(bb->phi_nodes);
317
       *loc;
318
       loc = &PHI_CHAIN (*loc))
319
    {
320
      if (len > PHI_ARG_CAPACITY (*loc))
321
        {
322
          tree old_phi = *loc;
323
 
324
          resize_phi_node (loc, cap);
325
 
326
          /* The result of the phi is defined by this phi node.  */
327
          SSA_NAME_DEF_STMT (PHI_RESULT (*loc)) = *loc;
328
 
329
          release_phi_node (old_phi);
330
        }
331
 
332
      /* We represent a "missing PHI argument" by placing NULL_TREE in
333
         the corresponding slot.  If PHI arguments were added
334
         immediately after an edge is created, this zeroing would not
335
         be necessary, but unfortunately this is not the case.  For
336
         example, the loop optimizer duplicates several basic blocks,
337
         redirects edges, and then fixes up PHI arguments later in
338
         batch.  */
339
      SET_PHI_ARG_DEF (*loc, len - 1, NULL_TREE);
340
 
341
      PHI_NUM_ARGS (*loc)++;
342
    }
343
}
344
 
345
/* Create a new PHI node for variable VAR at basic block BB.  */
346
 
347
tree
348
create_phi_node (tree var, basic_block bb)
349
{
350
  tree phi;
351
 
352
  phi = make_phi_node (var, EDGE_COUNT (bb->preds));
353
 
354
  /* Add the new PHI node to the list of PHI nodes for block BB.  */
355
  PHI_CHAIN (phi) = phi_nodes (bb);
356
  bb->phi_nodes = phi;
357
 
358
  /* Associate BB to the PHI node.  */
359
  set_bb_for_stmt (phi, bb);
360
 
361
  return phi;
362
}
363
 
364
/* Add a new argument to PHI node PHI.  DEF is the incoming reaching
365
   definition and E is the edge through which DEF reaches PHI.  The new
366
   argument is added at the end of the argument list.
367
   If PHI has reached its maximum capacity, add a few slots.  In this case,
368
   PHI points to the reallocated phi node when we return.  */
369
 
370
void
371
add_phi_arg (tree phi, tree def, edge e)
372
{
373
  basic_block bb = e->dest;
374
 
375
  gcc_assert (bb == bb_for_stmt (phi));
376
 
377
  /* We resize PHI nodes upon edge creation.  We should always have
378
     enough room at this point.  */
379
  gcc_assert (PHI_NUM_ARGS (phi) <= PHI_ARG_CAPACITY (phi));
380
 
381
  /* We resize PHI nodes upon edge creation.  We should always have
382
     enough room at this point.  */
383
  gcc_assert (e->dest_idx < (unsigned int) PHI_NUM_ARGS (phi));
384
 
385
  /* Copy propagation needs to know what object occur in abnormal
386
     PHI nodes.  This is a convenient place to record such information.  */
387
  if (e->flags & EDGE_ABNORMAL)
388
    {
389
      SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
390
      SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
391
    }
392
 
393
  SET_PHI_ARG_DEF (phi, e->dest_idx, def);
394
}
395
 
396
/* Remove the Ith argument from PHI's argument list.  This routine
397
   implements removal by swapping the last alternative with the
398
   alternative we want to delete and then shrinking the vector, which
399
   is consistent with how we remove an edge from the edge vector.  */
400
 
401
static void
402
remove_phi_arg_num (tree phi, int i)
403
{
404
  int num_elem = PHI_NUM_ARGS (phi);
405
 
406
  gcc_assert (i < num_elem);
407
 
408
 
409
  /* Delink the item which is being removed.  */
410
  delink_imm_use (&(PHI_ARG_IMM_USE_NODE (phi, i)));
411
 
412
  /* If it is not the last element, move the last element
413
     to the element we want to delete, resetting all the links. */
414
  if (i != num_elem - 1)
415
    {
416
      use_operand_p old_p, new_p;
417
      old_p = &PHI_ARG_IMM_USE_NODE (phi, num_elem - 1);
418
      new_p = &PHI_ARG_IMM_USE_NODE (phi, i);
419
      /* Set use on new node, and link into last element's place.  */
420
      *(new_p->use) = *(old_p->use);
421
      relink_imm_use (new_p, old_p);
422
    }
423
 
424
  /* Shrink the vector and return.  Note that we do not have to clear
425
     PHI_ARG_DEF because the garbage collector will not look at those
426
     elements beyond the first PHI_NUM_ARGS elements of the array.  */
427
  PHI_NUM_ARGS (phi)--;
428
}
429
 
430
/* Remove all PHI arguments associated with edge E.  */
431
 
432
void
433
remove_phi_args (edge e)
434
{
435
  tree phi;
436
 
437
  for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
438
    remove_phi_arg_num (phi, e->dest_idx);
439
}
440
 
441
/* Remove PHI node PHI from basic block BB.  If PREV is non-NULL, it is
442
   used as the node immediately before PHI in the linked list.  */
443
 
444
void
445
remove_phi_node (tree phi, tree prev)
446
{
447
  tree *loc;
448
 
449
  if (prev)
450
    {
451
      loc = &PHI_CHAIN (prev);
452
    }
453
  else
454
    {
455
      for (loc = &(bb_for_stmt (phi)->phi_nodes);
456
           *loc != phi;
457
           loc = &PHI_CHAIN (*loc))
458
        ;
459
    }
460
 
461
  /* Remove PHI from the chain.  */
462
  *loc = PHI_CHAIN (phi);
463
 
464
  /* If we are deleting the PHI node, then we should release the
465
     SSA_NAME node so that it can be reused.  */
466
  release_phi_node (phi);
467
  release_ssa_name (PHI_RESULT (phi));
468
}
469
 
470
 
471
/* Reverse the order of PHI nodes in the chain PHI.
472
   Return the new head of the chain (old last PHI node).  */
473
 
474
tree
475
phi_reverse (tree phi)
476
{
477
  tree prev = NULL_TREE, next;
478
  for (; phi; phi = next)
479
    {
480
      next = PHI_CHAIN (phi);
481
      PHI_CHAIN (phi) = prev;
482
      prev = phi;
483
    }
484
  return prev;
485
}
486
 
487
#include "gt-tree-phinodes.h"

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.