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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-phinodes.c] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Generic routines for manipulating PHIs
2
   Copyright (C) 2003, 2005, 2007, 2008, 2009, 2010
3
   Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 3, or (at your option)
10
any later version.
11
 
12
GCC is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public License for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
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"        /* FIXME: Only for ceil_log2, of all things...  */
27
#include "ggc.h"
28
#include "basic-block.h"
29
#include "tree-flow.h"
30
#include "diagnostic-core.h"
31
#include "gimple.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 (""))) VEC(gimple,gc) *free_phinodes[NUM_BUCKETS - 2];
81
static unsigned long free_phinode_count;
82
 
83
static int ideal_phi_node_len (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 gimple
130
allocate_phi_node (size_t len)
131
{
132
  gimple phi;
133
  size_t bucket = NUM_BUCKETS - 2;
134
  size_t size = sizeof (struct gimple_statement_phi)
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
      && gimple_phi_capacity (VEC_index (gimple, free_phinodes[bucket], 0))
145
         >= len)
146
    {
147
      free_phinode_count--;
148
      phi = VEC_pop (gimple, free_phinodes[bucket]);
149
      if (VEC_empty (gimple, free_phinodes[bucket]))
150
        VEC_free (gimple, gc, free_phinodes[bucket]);
151
#ifdef GATHER_STATISTICS
152
      phi_nodes_reused++;
153
#endif
154
    }
155
  else
156
    {
157
      phi = ggc_alloc_gimple_statement_d (size);
158
#ifdef GATHER_STATISTICS
159
      phi_nodes_created++;
160
        {
161
          enum gimple_alloc_kind kind = gimple_alloc_kind (GIMPLE_PHI);
162
          gimple_alloc_counts[(int) kind]++;
163
          gimple_alloc_sizes[(int) kind] += size;
164
        }
165
#endif
166
    }
167
 
168
  return phi;
169
}
170
 
171
/* Given LEN, the original number of requested PHI arguments, return
172
   a new, "ideal" length for the PHI node.  The "ideal" length rounds
173
   the total size of the PHI node up to the next power of two bytes.
174
 
175
   Rounding up will not result in wasting any memory since the size request
176
   will be rounded up by the GC system anyway.  [ Note this is not entirely
177
   true since the original length might have fit on one of the special
178
   GC pages. ]  By rounding up, we may avoid the need to reallocate the
179
   PHI node later if we increase the number of arguments for the PHI.  */
180
 
181
static int
182
ideal_phi_node_len (int len)
183
{
184
  size_t size, new_size;
185
  int log2, new_len;
186
 
187
  /* We do not support allocations of less than two PHI argument slots.  */
188
  if (len < 2)
189
    len = 2;
190
 
191
  /* Compute the number of bytes of the original request.  */
192
  size = sizeof (struct gimple_statement_phi)
193
         + (len - 1) * sizeof (struct phi_arg_d);
194
 
195
  /* Round it up to the next power of two.  */
196
  log2 = ceil_log2 (size);
197
  new_size = 1 << log2;
198
 
199
  /* Now compute and return the number of PHI argument slots given an
200
     ideal size allocation.  */
201
  new_len = len + (new_size - size) / sizeof (struct phi_arg_d);
202
  return new_len;
203
}
204
 
205
/* Return a PHI node with LEN argument slots for variable VAR.  */
206
 
207
static gimple
208
make_phi_node (tree var, int len)
209
{
210
  gimple phi;
211
  int capacity, i;
212
 
213
  capacity = ideal_phi_node_len (len);
214
 
215
  phi = allocate_phi_node (capacity);
216
 
217
  /* We need to clear the entire PHI node, including the argument
218
     portion, because we represent a "missing PHI argument" by placing
219
     NULL_TREE in PHI_ARG_DEF.  */
220
  memset (phi, 0, (sizeof (struct gimple_statement_phi)
221
                   - sizeof (struct phi_arg_d)
222
                   + sizeof (struct phi_arg_d) * len));
223
  phi->gsbase.code = GIMPLE_PHI;
224
  phi->gimple_phi.nargs = len;
225
  phi->gimple_phi.capacity = capacity;
226
  if (TREE_CODE (var) == SSA_NAME)
227
    gimple_phi_set_result (phi, var);
228
  else
229
    gimple_phi_set_result (phi, make_ssa_name (var, phi));
230
 
231
  for (i = 0; i < capacity; i++)
232
    {
233
      use_operand_p  imm;
234
 
235
      gimple_phi_arg_set_location (phi, i, UNKNOWN_LOCATION);
236
      imm = gimple_phi_arg_imm_use_ptr (phi, i);
237
      imm->use = gimple_phi_arg_def_ptr (phi, i);
238
      imm->prev = NULL;
239
      imm->next = NULL;
240
      imm->loc.stmt = phi;
241
    }
242
 
243
  return phi;
244
}
245
 
246
/* We no longer need PHI, release it so that it may be reused.  */
247
 
248
void
249
release_phi_node (gimple phi)
250
{
251
  size_t bucket;
252
  size_t len = gimple_phi_capacity (phi);
253
  size_t x;
254
 
255
  for (x = 0; x < gimple_phi_num_args (phi); x++)
256
    {
257
      use_operand_p  imm;
258
      imm = gimple_phi_arg_imm_use_ptr (phi, x);
259
      delink_imm_use (imm);
260
    }
261
 
262
  bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
263
  bucket -= 2;
264
  VEC_safe_push (gimple, gc, free_phinodes[bucket], phi);
265
  free_phinode_count++;
266
}
267
 
268
 
269
/* Resize an existing PHI node.  The only way is up.  Return the
270
   possibly relocated phi.  */
271
 
272
static void
273
resize_phi_node (gimple *phi, size_t len)
274
{
275
  size_t old_size, i;
276
  gimple new_phi;
277
 
278
  gcc_assert (len > gimple_phi_capacity (*phi));
279
 
280
  /* The garbage collector will not look at the PHI node beyond the
281
     first PHI_NUM_ARGS elements.  Therefore, all we have to copy is a
282
     portion of the PHI node currently in use.  */
283
  old_size = sizeof (struct gimple_statement_phi)
284
             + (gimple_phi_num_args (*phi) - 1) * sizeof (struct phi_arg_d);
285
 
286
  new_phi = allocate_phi_node (len);
287
 
288
  memcpy (new_phi, *phi, old_size);
289
 
290
  for (i = 0; i < gimple_phi_num_args (new_phi); i++)
291
    {
292
      use_operand_p imm, old_imm;
293
      imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
294
      old_imm = gimple_phi_arg_imm_use_ptr (*phi, i);
295
      imm->use = gimple_phi_arg_def_ptr (new_phi, i);
296
      relink_imm_use_stmt (imm, old_imm, new_phi);
297
    }
298
 
299
  new_phi->gimple_phi.capacity = len;
300
 
301
  for (i = gimple_phi_num_args (new_phi); i < len; i++)
302
    {
303
      use_operand_p imm;
304
 
305
      gimple_phi_arg_set_location (new_phi, i, UNKNOWN_LOCATION);
306
      imm = gimple_phi_arg_imm_use_ptr (new_phi, i);
307
      imm->use = gimple_phi_arg_def_ptr (new_phi, i);
308
      imm->prev = NULL;
309
      imm->next = NULL;
310
      imm->loc.stmt = new_phi;
311
    }
312
 
313
  *phi = new_phi;
314
}
315
 
316
/* Reserve PHI arguments for a new edge to basic block BB.  */
317
 
318
void
319
reserve_phi_args_for_new_edge (basic_block bb)
320
{
321
  size_t len = EDGE_COUNT (bb->preds);
322
  size_t cap = ideal_phi_node_len (len + 4);
323
  gimple_stmt_iterator gsi;
324
 
325
  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
326
    {
327
      gimple *loc = gsi_stmt_ptr (&gsi);
328
 
329
      if (len > gimple_phi_capacity (*loc))
330
        {
331
          gimple old_phi = *loc;
332
 
333
          resize_phi_node (loc, cap);
334
 
335
          /* The result of the PHI is defined by this PHI node.  */
336
          SSA_NAME_DEF_STMT (gimple_phi_result (*loc)) = *loc;
337
 
338
          release_phi_node (old_phi);
339
        }
340
 
341
      /* We represent a "missing PHI argument" by placing NULL_TREE in
342
         the corresponding slot.  If PHI arguments were added
343
         immediately after an edge is created, this zeroing would not
344
         be necessary, but unfortunately this is not the case.  For
345
         example, the loop optimizer duplicates several basic blocks,
346
         redirects edges, and then fixes up PHI arguments later in
347
         batch.  */
348
      SET_PHI_ARG_DEF (*loc, len - 1, NULL_TREE);
349
 
350
      (*loc)->gimple_phi.nargs++;
351
    }
352
}
353
 
354
/* Adds PHI to BB.  */
355
 
356
void
357
add_phi_node_to_bb (gimple phi, basic_block bb)
358
{
359
  gimple_stmt_iterator gsi;
360
  /* Add the new PHI node to the list of PHI nodes for block BB.  */
361
  if (phi_nodes (bb) == NULL)
362
    set_phi_nodes (bb, gimple_seq_alloc ());
363
 
364
  gsi = gsi_last (phi_nodes (bb));
365
  gsi_insert_after (&gsi, phi, GSI_NEW_STMT);
366
 
367
  /* Associate BB to the PHI node.  */
368
  gimple_set_bb (phi, bb);
369
 
370
}
371
 
372
/* Create a new PHI node for variable VAR at basic block BB.  */
373
 
374
gimple
375
create_phi_node (tree var, basic_block bb)
376
{
377
  gimple phi = make_phi_node (var, EDGE_COUNT (bb->preds));
378
 
379
  add_phi_node_to_bb (phi, bb);
380
  return phi;
381
}
382
 
383
 
384
/* Add a new argument to PHI node PHI.  DEF is the incoming reaching
385
   definition and E is the edge through which DEF reaches PHI.  The new
386
   argument is added at the end of the argument list.
387
   If PHI has reached its maximum capacity, add a few slots.  In this case,
388
   PHI points to the reallocated phi node when we return.  */
389
 
390
void
391
add_phi_arg (gimple phi, tree def, edge e, source_location locus)
392
{
393
  basic_block bb = e->dest;
394
 
395
  gcc_assert (bb == gimple_bb (phi));
396
 
397
  /* We resize PHI nodes upon edge creation.  We should always have
398
     enough room at this point.  */
399
  gcc_assert (gimple_phi_num_args (phi) <= gimple_phi_capacity (phi));
400
 
401
  /* We resize PHI nodes upon edge creation.  We should always have
402
     enough room at this point.  */
403
  gcc_assert (e->dest_idx < gimple_phi_num_args (phi));
404
 
405
  /* Copy propagation needs to know what object occur in abnormal
406
     PHI nodes.  This is a convenient place to record such information.  */
407
  if (e->flags & EDGE_ABNORMAL)
408
    {
409
      SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
410
      SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (phi)) = 1;
411
    }
412
 
413
  SET_PHI_ARG_DEF (phi, e->dest_idx, def);
414
  gimple_phi_arg_set_location (phi, e->dest_idx, locus);
415
}
416
 
417
 
418
/* Remove the Ith argument from PHI's argument list.  This routine
419
   implements removal by swapping the last alternative with the
420
   alternative we want to delete and then shrinking the vector, which
421
   is consistent with how we remove an edge from the edge vector.  */
422
 
423
static void
424
remove_phi_arg_num (gimple phi, int i)
425
{
426
  int num_elem = gimple_phi_num_args (phi);
427
 
428
  gcc_assert (i < num_elem);
429
 
430
  /* Delink the item which is being removed.  */
431
  delink_imm_use (gimple_phi_arg_imm_use_ptr (phi, i));
432
 
433
  /* If it is not the last element, move the last element
434
     to the element we want to delete, resetting all the links. */
435
  if (i != num_elem - 1)
436
    {
437
      use_operand_p old_p, new_p;
438
      old_p = gimple_phi_arg_imm_use_ptr (phi, num_elem - 1);
439
      new_p = gimple_phi_arg_imm_use_ptr (phi, i);
440
      /* Set use on new node, and link into last element's place.  */
441
      *(new_p->use) = *(old_p->use);
442
      relink_imm_use (new_p, old_p);
443
      /* Move the location as well.  */
444
      gimple_phi_arg_set_location (phi, i,
445
                                   gimple_phi_arg_location (phi, num_elem - 1));
446
    }
447
 
448
  /* Shrink the vector and return.  Note that we do not have to clear
449
     PHI_ARG_DEF because the garbage collector will not look at those
450
     elements beyond the first PHI_NUM_ARGS elements of the array.  */
451
  phi->gimple_phi.nargs--;
452
}
453
 
454
 
455
/* Remove all PHI arguments associated with edge E.  */
456
 
457
void
458
remove_phi_args (edge e)
459
{
460
  gimple_stmt_iterator gsi;
461
 
462
  for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
463
    remove_phi_arg_num (gsi_stmt (gsi), e->dest_idx);
464
}
465
 
466
 
467
/* Remove the PHI node pointed-to by iterator GSI from basic block BB.  After
468
   removal, iterator GSI is updated to point to the next PHI node in the
469
   sequence. If RELEASE_LHS_P is true, the LHS of this PHI node is released
470
   into the free pool of SSA names.  */
471
 
472
void
473
remove_phi_node (gimple_stmt_iterator *gsi, bool release_lhs_p)
474
{
475
  gimple phi = gsi_stmt (*gsi);
476
 
477
  if (release_lhs_p)
478
    insert_debug_temps_for_defs (gsi);
479
 
480
  gsi_remove (gsi, false);
481
 
482
  /* If we are deleting the PHI node, then we should release the
483
     SSA_NAME node so that it can be reused.  */
484
  release_phi_node (phi);
485
  if (release_lhs_p)
486
    release_ssa_name (gimple_phi_result (phi));
487
}
488
 
489
/* Remove all the phi nodes from BB.  */
490
 
491
void
492
remove_phi_nodes (basic_block bb)
493
{
494
  gimple_stmt_iterator gsi;
495
 
496
  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
497
    remove_phi_node (&gsi, true);
498
 
499
  set_phi_nodes (bb, NULL);
500
}
501
 
502
#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.