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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [vec.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Vector API for GNU compiler.
2
   Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
3
   Contributed by Nathan Sidwell <nathan@codesourcery.com>
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
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
/* This file is compiled twice: once for the generator programs
22
   once for the compiler.  */
23
#ifdef GENERATOR_FILE
24
#include "bconfig.h"
25
#else
26
#include "config.h"
27
#endif
28
 
29
#include "system.h"
30
#include "ggc.h"
31
#include "vec.h"
32
#include "coretypes.h"
33
#include "toplev.h"
34
#include "hashtab.h"
35
 
36
struct vec_prefix
37
{
38
  unsigned num;
39
  unsigned alloc;
40
  void *vec[1];
41
};
42
 
43
 
44
#ifdef GATHER_STATISTICS
45
 
46
/* Store information about each particular vector.  */
47
struct vec_descriptor
48
{
49
  const char *function;
50
  const char *file;
51
  int line;
52
  size_t allocated;
53
  size_t times;
54
  size_t peak;
55
};
56
 
57
 
58
/* Hashtable mapping vec addresses to descriptors.  */
59
static htab_t vec_desc_hash;
60
 
61
/* Hashtable helpers.  */
62
static hashval_t
63
hash_descriptor (const void *p)
64
{
65
  const struct vec_descriptor *const d =
66
    (const struct vec_descriptor *) p;
67
  return htab_hash_pointer (d->file) + d->line;
68
}
69
static int
70
eq_descriptor (const void *p1, const void *p2)
71
{
72
  const struct vec_descriptor *const d = (const struct vec_descriptor *) p1;
73
  const struct vec_descriptor *const l = (const struct vec_descriptor *) p2;
74
  return d->file == l->file && d->function == l->function && d->line == l->line;
75
}
76
 
77
/* Hashtable converting address of allocated field to loc descriptor.  */
78
static htab_t ptr_hash;
79
struct ptr_hash_entry
80
{
81
  void *ptr;
82
  struct vec_descriptor *loc;
83
  size_t allocated;
84
};
85
 
86
/* Hash table helpers functions.  */
87
static hashval_t
88
hash_ptr (const void *p)
89
{
90
  const struct ptr_hash_entry *const d = (const struct ptr_hash_entry *) p;
91
 
92
  return htab_hash_pointer (d->ptr);
93
}
94
 
95
static int
96
eq_ptr (const void *p1, const void *p2)
97
{
98
  const struct ptr_hash_entry *const p = (const struct ptr_hash_entry *) p1;
99
 
100
  return (p->ptr == p2);
101
}
102
 
103
/* Return descriptor for given call site, create new one if needed.  */
104
static struct vec_descriptor *
105
vec_descriptor (const char *name, int line, const char *function)
106
{
107
  struct vec_descriptor loc;
108
  struct vec_descriptor **slot;
109
 
110
  loc.file = name;
111
  loc.line = line;
112
  loc.function = function;
113
  if (!vec_desc_hash)
114
    vec_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
115
 
116
  slot = (struct vec_descriptor **) htab_find_slot (vec_desc_hash, &loc,
117
                                                    INSERT);
118
  if (*slot)
119
    return *slot;
120
  *slot = XCNEW (struct vec_descriptor);
121
  (*slot)->file = name;
122
  (*slot)->line = line;
123
  (*slot)->function = function;
124
  (*slot)->allocated = 0;
125
  (*slot)->peak = 0;
126
  return *slot;
127
}
128
 
129
/* Account the overhead.  */
130
static void
131
register_overhead (struct vec_prefix *ptr, size_t size,
132
                   const char *name, int line, const char *function)
133
{
134
  struct vec_descriptor *loc = vec_descriptor (name, line, function);
135
  struct ptr_hash_entry *p = XNEW (struct ptr_hash_entry);
136
  PTR *slot;
137
 
138
  p->ptr = ptr;
139
  p->loc = loc;
140
  p->allocated = size;
141
  if (!ptr_hash)
142
    ptr_hash = htab_create (10, hash_ptr, eq_ptr, NULL);
143
  slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr), INSERT);
144
  gcc_assert (!*slot);
145
  *slot = p;
146
 
147
  loc->allocated += size;
148
  if (loc->peak < loc->allocated)
149
    loc->peak += loc->allocated;
150
  loc->times++;
151
}
152
 
153
/* Notice that the pointer has been freed.  */
154
static void
155
free_overhead (struct vec_prefix *ptr)
156
{
157
  PTR *slot = htab_find_slot_with_hash (ptr_hash, ptr, htab_hash_pointer (ptr),
158
                                        NO_INSERT);
159
  struct ptr_hash_entry *p = (struct ptr_hash_entry *) *slot;
160
  p->loc->allocated -= p->allocated;
161
  htab_clear_slot (ptr_hash, slot);
162
  free (p);
163
}
164
 
165
void
166
vec_heap_free (void *ptr)
167
{
168
  free_overhead ((struct vec_prefix *)ptr);
169
  free (ptr);
170
}
171
#endif
172
 
173
/* Calculate the new ALLOC value, making sure that RESERVE slots are
174
   free.  If EXACT grow exactly, otherwise grow exponentially.  */
175
 
176
static inline unsigned
177
calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact)
178
{
179
  unsigned alloc = 0;
180
  unsigned num = 0;
181
 
182
  gcc_assert (reserve >= 0);
183
 
184
  if (pfx)
185
    {
186
      alloc = pfx->alloc;
187
      num = pfx->num;
188
    }
189
  else if (!reserve)
190
    /* If there's no prefix, and we've not requested anything, then we
191
       will create a NULL vector.  */
192
    return 0;
193
 
194
  /* We must have run out of room.  */
195
  gcc_assert (alloc - num < (unsigned) reserve);
196
 
197
  if (exact)
198
    /* Exact size.  */
199
    alloc = num + reserve;
200
  else
201
    {
202
      /* Exponential growth. */
203
      if (!alloc)
204
        alloc = 4;
205
      else if (alloc < 16)
206
        /* Double when small.  */
207
        alloc = alloc * 2;
208
      else
209
        /* Grow slower when large.  */
210
        alloc = (alloc * 3 / 2);
211
 
212
      /* If this is still too small, set it to the right size. */
213
      if (alloc < num + reserve)
214
        alloc = num + reserve;
215
    }
216
  return alloc;
217
}
218
 
219
/* Ensure there are at least RESERVE free slots in VEC.  If EXACT grow
220
   exactly, else grow exponentially.  As a special case, if VEC is
221
   NULL and RESERVE is 0, no vector will be created.  The vector's
222
   trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
223
   sized elements.  */
224
 
225
static void *
226
vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size,
227
                    bool exact MEM_STAT_DECL)
228
{
229
  struct vec_prefix *pfx = (struct vec_prefix *) vec;
230
  unsigned alloc = calculate_allocation (pfx, reserve, exact);
231
 
232
  if (!alloc)
233
    {
234
      if (pfx)
235
        ggc_free (pfx);
236
      return NULL;
237
    }
238
 
239
  vec = ggc_realloc_stat (vec, vec_offset + alloc * elt_size PASS_MEM_STAT);
240
  ((struct vec_prefix *)vec)->alloc = alloc;
241
  if (!pfx)
242
    ((struct vec_prefix *)vec)->num = 0;
243
 
244
  return vec;
245
}
246
 
247
/* Ensure there are at least RESERVE free slots in VEC, growing
248
   exponentially.  If RESERVE < 0 grow exactly, else grow
249
   exponentially.  As a special case, if VEC is NULL, and RESERVE is
250
   0, no vector will be created. */
251
 
252
void *
253
vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
254
{
255
  return vec_gc_o_reserve_1 (vec, reserve,
256
                             offsetof (struct vec_prefix, vec),
257
                             sizeof (void *), false
258
                             PASS_MEM_STAT);
259
}
260
 
261
/* Ensure there are at least RESERVE free slots in VEC, growing
262
   exactly.  If RESERVE < 0 grow exactly, else grow exponentially.  As
263
   a special case, if VEC is NULL, and RESERVE is 0, no vector will be
264
   created. */
265
 
266
void *
267
vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
268
{
269
  return vec_gc_o_reserve_1 (vec, reserve,
270
                             offsetof (struct vec_prefix, vec),
271
                             sizeof (void *), true
272
                             PASS_MEM_STAT);
273
}
274
 
275
/* As for vec_gc_p_reserve, but for object vectors.  The vector's
276
   trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
277
   sized elements.  */
278
 
279
void *
280
vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
281
                  MEM_STAT_DECL)
282
{
283
  return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
284
                             PASS_MEM_STAT);
285
}
286
 
287
/* As for vec_gc_p_reserve_exact, but for object vectors.  The
288
   vector's trailing array is at VEC_OFFSET offset and consists of
289
   ELT_SIZE sized elements.  */
290
 
291
void *
292
vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
293
                        size_t elt_size MEM_STAT_DECL)
294
{
295
  return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
296
                             PASS_MEM_STAT);
297
}
298
 
299
/* As for vec_gc_o_reserve_1, but for heap allocated vectors.  */
300
 
301
static void *
302
vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
303
                      size_t elt_size, bool exact MEM_STAT_DECL)
304
{
305
  struct vec_prefix *pfx = (struct vec_prefix *) vec;
306
  unsigned alloc = calculate_allocation (pfx, reserve, exact);
307
 
308
  if (!alloc)
309
    {
310
      if (pfx)
311
        vec_heap_free (pfx);
312
      return NULL;
313
    }
314
 
315
#ifdef GATHER_STATISTICS
316
  if (vec)
317
    free_overhead (pfx);
318
#endif
319
 
320
  vec = xrealloc (vec, vec_offset + alloc * elt_size);
321
  ((struct vec_prefix *)vec)->alloc = alloc;
322
  if (!pfx)
323
    ((struct vec_prefix *)vec)->num = 0;
324
#ifdef GATHER_STATISTICS
325
  if (vec)
326
    register_overhead ((struct vec_prefix *)vec,
327
                       vec_offset + alloc * elt_size PASS_MEM_STAT);
328
#endif
329
 
330
  return vec;
331
}
332
 
333
/* As for vec_gc_p_reserve, but for heap allocated vectors.  */
334
 
335
void *
336
vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
337
{
338
  return vec_heap_o_reserve_1 (vec, reserve,
339
                               offsetof (struct vec_prefix, vec),
340
                               sizeof (void *), false
341
                               PASS_MEM_STAT);
342
}
343
 
344
/* As for vec_gc_p_reserve_exact, but for heap allocated vectors.  */
345
 
346
void *
347
vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
348
{
349
  return vec_heap_o_reserve_1 (vec, reserve,
350
                               offsetof (struct vec_prefix, vec),
351
                               sizeof (void *), true
352
                               PASS_MEM_STAT);
353
}
354
 
355
/* As for vec_gc_o_reserve, but for heap allocated vectors.  */
356
 
357
void *
358
vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
359
                    MEM_STAT_DECL)
360
{
361
  return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
362
                               PASS_MEM_STAT);
363
}
364
 
365
/* As for vec_gc_o_reserve_exact, but for heap allocated vectors.  */
366
 
367
void *
368
vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
369
                          size_t elt_size MEM_STAT_DECL)
370
{
371
  return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
372
                               PASS_MEM_STAT);
373
}
374
 
375
/* Stack vectors are a little different.  VEC_alloc turns into a call
376
   to vec_stack_p_reserve_exact1 and passes in space allocated via a
377
   call to alloca.  We record that pointer so that we know that we
378
   shouldn't free it.  If the vector is resized, we resize it on the
379
   heap.  We record the pointers in a vector and search it in LIFO
380
   order--i.e., we look for the newest stack vectors first.  We don't
381
   expect too many stack vectors at any one level, and searching from
382
   the end should normally be efficient even if they are used in a
383
   recursive function.  */
384
 
385
typedef void *void_p;
386
DEF_VEC_P(void_p);
387
DEF_VEC_ALLOC_P(void_p,heap);
388
 
389
static VEC(void_p,heap) *stack_vecs;
390
 
391
/* Allocate a vector which uses alloca for the initial allocation.
392
   SPACE is space allocated using alloca, ALLOC is the number of
393
   entries allocated.  */
394
 
395
void *
396
vec_stack_p_reserve_exact_1 (int alloc, void *space)
397
{
398
  struct vec_prefix *pfx = (struct vec_prefix *) space;
399
 
400
  VEC_safe_push (void_p, heap, stack_vecs, space);
401
 
402
  pfx->num = 0;
403
  pfx->alloc = alloc;
404
 
405
  return space;
406
}
407
 
408
/* Grow a vector allocated using alloca.  When this happens, we switch
409
   back to heap allocation.  We remove the vector from stack_vecs, if
410
   it is there, since we no longer need to avoid freeing it.  */
411
 
412
static void *
413
vec_stack_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
414
                       size_t elt_size, bool exact MEM_STAT_DECL)
415
{
416
  bool found;
417
  unsigned int ix;
418
  void *newvec;
419
 
420
  found = false;
421
  for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
422
    {
423
      if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
424
        {
425
          VEC_unordered_remove (void_p, stack_vecs, ix - 1);
426
          found = true;
427
          break;
428
        }
429
    }
430
 
431
  if (!found)
432
    {
433
      /* VEC is already on the heap.  */
434
      return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size,
435
                                   exact PASS_MEM_STAT);
436
    }
437
 
438
  /* Move VEC to the heap.  */
439
  reserve += ((struct vec_prefix *) vec)->num;
440
  newvec = vec_heap_o_reserve_1 (NULL, reserve, vec_offset, elt_size,
441
                                 exact PASS_MEM_STAT);
442
  if (newvec && vec)
443
    {
444
      ((struct vec_prefix *) newvec)->num = ((struct vec_prefix *) vec)->num;
445
      memcpy (((struct vec_prefix *) newvec)->vec,
446
              ((struct vec_prefix *) vec)->vec,
447
              ((struct vec_prefix *) vec)->num * elt_size);
448
    }
449
  return newvec;
450
}
451
 
452
/* Grow a vector allocated on the stack.  */
453
 
454
void *
455
vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL)
456
{
457
  return vec_stack_o_reserve_1 (vec, reserve,
458
                                offsetof (struct vec_prefix, vec),
459
                                sizeof (void *), false
460
                                PASS_MEM_STAT);
461
}
462
 
463
/* Exact version of vec_stack_p_reserve.  */
464
 
465
void *
466
vec_stack_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
467
{
468
  return vec_stack_o_reserve_1 (vec, reserve,
469
                                offsetof (struct vec_prefix, vec),
470
                                sizeof (void *), true
471
                                PASS_MEM_STAT);
472
}
473
 
474
/* Like vec_stack_p_reserve, but for objects.  */
475
 
476
void *
477
vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset,
478
                     size_t elt_size MEM_STAT_DECL)
479
{
480
  return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
481
                                PASS_MEM_STAT);
482
}
483
 
484
/* Like vec_stack_p_reserve_exact, but for objects.  */
485
 
486
void *
487
vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
488
                            size_t elt_size MEM_STAT_DECL)
489
{
490
  return vec_stack_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
491
                                PASS_MEM_STAT);
492
}
493
 
494
/* Free a vector allocated on the stack.  Don't actually free it if we
495
   find it in the hash table.  */
496
 
497
void
498
vec_stack_free (void *vec)
499
{
500
  unsigned int ix;
501
 
502
  for (ix = VEC_length (void_p, stack_vecs); ix > 0; --ix)
503
    {
504
      if (VEC_index (void_p, stack_vecs, ix - 1) == vec)
505
        {
506
          VEC_unordered_remove (void_p, stack_vecs, ix - 1);
507
          return;
508
        }
509
    }
510
 
511
  /* VEC was not on the list of vecs allocated on the stack, so it
512
     must be allocated on the heap.  */
513
  vec_heap_free (vec);
514
}
515
 
516
#if ENABLE_CHECKING
517
/* Issue a vector domain error, and then fall over.  */
518
 
519
void
520
vec_assert_fail (const char *op, const char *struct_name,
521
                 const char *file, unsigned int line, const char *function)
522
{
523
  internal_error ("vector %s %s domain error, in %s at %s:%u",
524
                  struct_name, op, function, trim_filename (file), line);
525
}
526
#endif
527
 
528
#ifdef GATHER_STATISTICS
529
/* Helper for qsort; sort descriptors by amount of memory consumed.  */
530
static int
531
cmp_statistic (const void *loc1, const void *loc2)
532
{
533
  const struct vec_descriptor *const l1 =
534
    *(const struct vec_descriptor *const *) loc1;
535
  const struct vec_descriptor *const l2 =
536
    *(const struct vec_descriptor *const *) loc2;
537
  long diff;
538
  diff = l1->allocated - l2->allocated;
539
  if (!diff)
540
    diff = l1->peak - l2->peak;
541
  if (!diff)
542
    diff = l1->times - l2->times;
543
  return diff > 0 ? 1 : diff < 0 ? -1 : 0;
544
}
545
/* Collect array of the descriptors from hashtable.  */
546
static struct vec_descriptor **loc_array;
547
static int
548
add_statistics (void **slot, void *b)
549
{
550
  int *n = (int *)b;
551
  loc_array[*n] = (struct vec_descriptor *) *slot;
552
  (*n)++;
553
  return 1;
554
}
555
 
556
/* Dump per-site memory statistics.  */
557
#endif
558
void
559
dump_vec_loc_statistics (void)
560
{
561
#ifdef GATHER_STATISTICS
562
  int nentries = 0;
563
  char s[4096];
564
  size_t allocated = 0;
565
  size_t times = 0;
566
  int i;
567
 
568
  loc_array = XCNEWVEC (struct vec_descriptor *, vec_desc_hash->n_elements);
569
  fprintf (stderr, "Heap vectors:\n");
570
  fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
571
           "source location", "Leak", "Peak", "Times");
572
  fprintf (stderr, "-------------------------------------------------------\n");
573
  htab_traverse (vec_desc_hash, add_statistics, &nentries);
574
  qsort (loc_array, nentries, sizeof (*loc_array), cmp_statistic);
575
  for (i = 0; i < nentries; i++)
576
    {
577
      struct vec_descriptor *d = loc_array[i];
578
      allocated += d->allocated;
579
      times += d->times;
580
    }
581
  for (i = 0; i < nentries; i++)
582
    {
583
      struct vec_descriptor *d = loc_array[i];
584
      const char *s1 = d->file;
585
      const char *s2;
586
      while ((s2 = strstr (s1, "gcc/")))
587
        s1 = s2 + 4;
588
      sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
589
      s[48] = 0;
590
      fprintf (stderr, "%-48s %10li:%4.1f%% %10li      %10li:%4.1f%% \n", s,
591
               (long)d->allocated,
592
               (d->allocated) * 100.0 / allocated,
593
               (long)d->peak,
594
               (long)d->times,
595
               (d->times) * 100.0 / times);
596
    }
597
  fprintf (stderr, "%-48s %10ld                        %10ld\n",
598
           "Total", (long)allocated, (long)times);
599
  fprintf (stderr, "\n%-48s %10s       %10s       %10s\n",
600
           "source location", "Leak", "Peak", "Times");
601
  fprintf (stderr, "-------------------------------------------------------\n");
602
#endif
603
}

powered by: WebSVN 2.1.0

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