blob: 1c4b958871b474da0a98b8695d9fb3f134fa2426 [file] [log] [blame]
/* Vector API for GNU compiler.
Copyright (C) 2004-2020 Free Software Foundation, Inc.
Contributed by Nathan Sidwell <nathan@codesourcery.com>
Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
/* This file is compiled twice: once for the generator programs
once for the compiler. */
#ifdef GENERATOR_FILE
#include "bconfig.h"
#else
#include "config.h"
#endif
#include "system.h"
#include "coretypes.h"
#include "hash-table.h"
#include "selftest.h"
#ifdef GENERATOR_FILE
#include "errors.h"
#else
#include "input.h"
#include "diagnostic-core.h"
#endif
/* vNULL is an empty type with a template cast operation that returns
a zero-initialized vec<T, A, L> instance. Use this when you want
to assign nil values to new vec instances or pass a nil vector as
a function call argument.
We use this technique because vec<T, A, L> must be PODs (they are
stored in unions and passed in vararg functions), this means that
they cannot have ctors/dtors. */
vnull vNULL;
/* Vector memory usage. */
class vec_usage: public mem_usage
{
public:
/* Default constructor. */
vec_usage (): m_items (0), m_items_peak (0), m_element_size (0) {}
/* Constructor. */
vec_usage (size_t allocated, size_t times, size_t peak,
size_t items, size_t items_peak, size_t element_size)
: mem_usage (allocated, times, peak),
m_items (items), m_items_peak (items_peak),
m_element_size (element_size) {}
/* Sum the usage with SECOND usage. */
vec_usage
operator+ (const vec_usage &second)
{
return vec_usage (m_allocated + second.m_allocated,
m_times + second.m_times,
m_peak + second.m_peak,
m_items + second.m_items,
m_items_peak + second.m_items_peak, 0);
}
/* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
inline void
dump (mem_location *loc, mem_usage &total) const
{
char s[4096];
sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (),
loc->m_line, loc->m_function);
s[48] = '\0';
fprintf (stderr,
"%-48s %10" PRIu64 PRsa (10) ":%4.1f%%" PRsa (9) "%10" PRIu64
":%4.1f%%" PRsa (10) PRsa (10) "\n",
s,
(uint64_t)m_element_size,
SIZE_AMOUNT (m_allocated),
m_allocated * 100.0 / total.m_allocated,
SIZE_AMOUNT (m_peak), (uint64_t)m_times,
m_times * 100.0 / total.m_times,
SIZE_AMOUNT (m_items), SIZE_AMOUNT (m_items_peak));
}
/* Dump footer. */
inline void
dump_footer ()
{
fprintf (stderr, "%s" PRsa (64) PRsa (25) PRsa (16) "\n",
"Total", SIZE_AMOUNT (m_allocated),
SIZE_AMOUNT (m_times), SIZE_AMOUNT (m_items));
}
/* Dump header with NAME. */
static inline void
dump_header (const char *name)
{
fprintf (stderr, "%-48s %10s%11s%16s%10s%17s%11s\n", name, "sizeof(T)",
"Leak", "Peak", "Times", "Leak items", "Peak items");
}
/* Current number of items allocated. */
size_t m_items;
/* Peak value of number of allocated items. */
size_t m_items_peak;
/* Size of element of the vector. */
size_t m_element_size;
};
/* Vector memory description. */
static mem_alloc_description <vec_usage> vec_mem_desc;
/* Account the overhead. */
void
vec_prefix::register_overhead (void *ptr, size_t elements,
size_t element_size MEM_STAT_DECL)
{
vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false
FINAL_PASS_MEM_STAT);
vec_usage *usage
= vec_mem_desc.register_instance_overhead (elements * element_size, ptr);
usage->m_element_size = element_size;
usage->m_items += elements;
if (usage->m_items_peak < usage->m_items)
usage->m_items_peak = usage->m_items;
}
/* Notice that the memory allocated for the vector has been freed. */
void
vec_prefix::release_overhead (void *ptr, size_t size, size_t elements,
bool in_dtor MEM_STAT_DECL)
{
if (!vec_mem_desc.contains_descriptor_for_instance (ptr))
vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN,
false FINAL_PASS_MEM_STAT);
vec_usage *usage = vec_mem_desc.release_instance_overhead (ptr, size,
in_dtor);
usage->m_items -= elements;
}
/* Calculate the number of slots to reserve a vector, making sure that
it is of at least DESIRED size by growing ALLOC exponentially. */
unsigned
vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
{
/* We must have run out of room. */
gcc_assert (alloc < desired);
/* Exponential growth. */
if (!alloc)
alloc = 4;
else if (alloc < 16)
/* Double when small. */
alloc = alloc * 2;
else
/* Grow slower when large. */
alloc = (alloc * 3 / 2);
/* If this is still too small, set it to the right size. */
if (alloc < desired)
alloc = desired;
return alloc;
}
/* Dump per-site memory statistics. */
void
dump_vec_loc_statistics (void)
{
vec_mem_desc.dump (VEC_ORIGIN);
}
#if CHECKING_P
/* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
witness elements. */
ATTRIBUTE_NORETURN ATTRIBUTE_COLD
static void
qsort_chk_error (const void *p1, const void *p2, const void *p3,
sort_r_cmp_fn *cmp, void *data)
{
if (!p3)
{
int r1 = cmp (p1, p2, data), r2 = cmp (p2, p1, data);
error ("qsort comparator not anti-symmetric: %d, %d", r1, r2);
}
else if (p1 == p2)
{
int r = cmp (p1, p3, data);
error ("qsort comparator non-negative on sorted output: %d", r);
}
else
{
int r1 = cmp (p1, p2, data);
int r2 = cmp (p2, p3, data);
int r3 = cmp (p1, p3, data);
error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
}
internal_error ("qsort checking failed");
}
/* Verify anti-symmetry and transitivity for comparator CMP on sorted array
of N SIZE-sized elements pointed to by BASE. */
void
qsort_chk (void *base, size_t n, size_t size, sort_r_cmp_fn *cmp, void *data)
{
#if 0
#define LIM(n) (n)
#else
/* Limit overall time complexity to O(n log n). */
#define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
#endif
#define ELT(i) ((const char *) base + (i) * size)
#define CMP(i, j) cmp (ELT (i), ELT (j), data)
#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp, data)
#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp, data)
size_t i1, i2, i, j;
/* This outer loop iterates over maximum spans [i1, i2) such that
elements within each span compare equal to each other. */
for (i1 = 0; i1 < n; i1 = i2)
{
/* Position i2 one past last element that compares equal to i1'th. */
for (i2 = i1 + 1; i2 < n; i2++)
if (CMP (i1, i2))
break;
else if (CMP (i2, i1))
return ERR2 (i1, i2);
size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
/* Verify that other pairs within current span compare equal. */
for (i = i1 + 1; i + 1 < i2; i++)
for (j = i + 1; j < i1 + lim1; j++)
if (CMP (i, j))
return ERR3 (i, i1, j);
else if (CMP (j, i))
return ERR2 (i, j);
/* Verify that elements within this span compare less than
elements beyond the span. */
for (i = i1; i < i2; i++)
for (j = i2; j < i2 + lim2; j++)
if (CMP (i, j) >= 0)
return ERR3 (i, i1, j);
else if (CMP (j, i) <= 0)
return ERR2 (i, j);
}
#undef ERR3
#undef ERR2
#undef CMP
#undef ELT
#undef LIM
}
#endif /* #if CHECKING_P */
#ifndef GENERATOR_FILE
#if CHECKING_P
namespace selftest {
/* Selftests. */
/* Call V.safe_push for all ints from START up to, but not including LIMIT.
Helper function for selftests. */
static void
safe_push_range (vec <int>&v, int start, int limit)
{
for (int i = start; i < limit; i++)
v.safe_push (i);
}
/* Verify that vec::quick_push works correctly. */
static void
test_quick_push ()
{
auto_vec <int> v;
ASSERT_EQ (0, v.length ());
v.reserve (3);
ASSERT_EQ (0, v.length ());
ASSERT_TRUE (v.space (3));
v.quick_push (5);
v.quick_push (6);
v.quick_push (7);
ASSERT_EQ (3, v.length ());
ASSERT_EQ (5, v[0]);
ASSERT_EQ (6, v[1]);
ASSERT_EQ (7, v[2]);
}
/* Verify that vec::safe_push works correctly. */
static void
test_safe_push ()
{
auto_vec <int> v;
ASSERT_EQ (0, v.length ());
v.safe_push (5);
v.safe_push (6);
v.safe_push (7);
ASSERT_EQ (3, v.length ());
ASSERT_EQ (5, v[0]);
ASSERT_EQ (6, v[1]);
ASSERT_EQ (7, v[2]);
}
/* Verify that vec::truncate works correctly. */
static void
test_truncate ()
{
auto_vec <int> v;
ASSERT_EQ (0, v.length ());
safe_push_range (v, 0, 10);
ASSERT_EQ (10, v.length ());
v.truncate (5);
ASSERT_EQ (5, v.length ());
}
/* Verify that vec::safe_grow_cleared works correctly. */
static void
test_safe_grow_cleared ()
{
auto_vec <int> v;
ASSERT_EQ (0, v.length ());
v.safe_grow_cleared (50);
ASSERT_EQ (50, v.length ());
ASSERT_EQ (0, v[0]);
ASSERT_EQ (0, v[49]);
}
/* Verify that vec::pop works correctly. */
static void
test_pop ()
{
auto_vec <int> v;
safe_push_range (v, 5, 20);
ASSERT_EQ (15, v.length ());
int last = v.pop ();
ASSERT_EQ (19, last);
ASSERT_EQ (14, v.length ());
}
/* Verify that vec::safe_insert works correctly. */
static void
test_safe_insert ()
{
auto_vec <int> v;
safe_push_range (v, 0, 10);
v.safe_insert (5, 42);
ASSERT_EQ (4, v[4]);
ASSERT_EQ (42, v[5]);
ASSERT_EQ (5, v[6]);
ASSERT_EQ (11, v.length ());
}
/* Verify that vec::ordered_remove works correctly. */
static void
test_ordered_remove ()
{
auto_vec <int> v;
safe_push_range (v, 0, 10);
v.ordered_remove (5);
ASSERT_EQ (4, v[4]);
ASSERT_EQ (6, v[5]);
ASSERT_EQ (9, v.length ());
}
/* Verify that vec::ordered_remove_if works correctly. */
static void
test_ordered_remove_if (void)
{
auto_vec <int> v;
safe_push_range (v, 0, 10);
unsigned ix, ix2;
int *elem_ptr;
VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr,
*elem_ptr == 5 || *elem_ptr == 7);
ASSERT_EQ (4, v[4]);
ASSERT_EQ (6, v[5]);
ASSERT_EQ (8, v[6]);
ASSERT_EQ (8, v.length ());
v.truncate (0);
safe_push_range (v, 0, 10);
VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 6,
*elem_ptr == 5 || *elem_ptr == 7);
ASSERT_EQ (4, v[4]);
ASSERT_EQ (6, v[5]);
ASSERT_EQ (7, v[6]);
ASSERT_EQ (9, v.length ());
v.truncate (0);
safe_push_range (v, 0, 10);
VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 5,
*elem_ptr == 5 || *elem_ptr == 7);
VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 8, 10,
*elem_ptr == 5 || *elem_ptr == 7);
ASSERT_EQ (4, v[4]);
ASSERT_EQ (5, v[5]);
ASSERT_EQ (6, v[6]);
ASSERT_EQ (10, v.length ());
v.truncate (0);
safe_push_range (v, 0, 10);
VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, *elem_ptr == 5);
ASSERT_EQ (4, v[4]);
ASSERT_EQ (6, v[5]);
ASSERT_EQ (7, v[6]);
ASSERT_EQ (9, v.length ());
}
/* Verify that vec::unordered_remove works correctly. */
static void
test_unordered_remove ()
{
auto_vec <int> v;
safe_push_range (v, 0, 10);
v.unordered_remove (5);
ASSERT_EQ (9, v.length ());
}
/* Verify that vec::block_remove works correctly. */
static void
test_block_remove ()
{
auto_vec <int> v;
safe_push_range (v, 0, 10);
v.block_remove (5, 3);
ASSERT_EQ (3, v[3]);
ASSERT_EQ (4, v[4]);
ASSERT_EQ (8, v[5]);
ASSERT_EQ (9, v[6]);
ASSERT_EQ (7, v.length ());
}
/* Comparator for use by test_qsort. */
static int
reverse_cmp (const void *p_i, const void *p_j)
{
return *(const int *)p_j - *(const int *)p_i;
}
/* Verify that vec::qsort works correctly. */
static void
test_qsort ()
{
auto_vec <int> v;
safe_push_range (v, 0, 10);
v.qsort (reverse_cmp);
ASSERT_EQ (9, v[0]);
ASSERT_EQ (8, v[1]);
ASSERT_EQ (1, v[8]);
ASSERT_EQ (0, v[9]);
ASSERT_EQ (10, v.length ());
}
/* Verify that vec::reverse works correctly. */
static void
test_reverse ()
{
/* Reversing an empty vec ought to be a no-op. */
{
auto_vec <int> v;
ASSERT_EQ (0, v.length ());
v.reverse ();
ASSERT_EQ (0, v.length ());
}
/* Verify reversing a vec with even length. */
{
auto_vec <int> v;
safe_push_range (v, 0, 4);
v.reverse ();
ASSERT_EQ (3, v[0]);
ASSERT_EQ (2, v[1]);
ASSERT_EQ (1, v[2]);
ASSERT_EQ (0, v[3]);
ASSERT_EQ (4, v.length ());
}
/* Verify reversing a vec with odd length. */
{
auto_vec <int> v;
safe_push_range (v, 0, 3);
v.reverse ();
ASSERT_EQ (2, v[0]);
ASSERT_EQ (1, v[1]);
ASSERT_EQ (0, v[2]);
ASSERT_EQ (3, v.length ());
}
}
/* A test class that increments a counter every time its dtor is called. */
class count_dtor
{
public:
count_dtor (int *counter) : m_counter (counter) {}
~count_dtor () { (*m_counter)++; }
private:
int *m_counter;
};
/* Verify that auto_delete_vec deletes the elements within it. */
static void
test_auto_delete_vec ()
{
int dtor_count = 0;
{
auto_delete_vec <count_dtor> v;
v.safe_push (new count_dtor (&dtor_count));
v.safe_push (new count_dtor (&dtor_count));
}
ASSERT_EQ (dtor_count, 2);
}
/* Run all of the selftests within this file. */
void
vec_c_tests ()
{
test_quick_push ();
test_safe_push ();
test_truncate ();
test_safe_grow_cleared ();
test_pop ();
test_safe_insert ();
test_ordered_remove ();
test_ordered_remove_if ();
test_unordered_remove ();
test_block_remove ();
test_qsort ();
test_reverse ();
test_auto_delete_vec ();
}
} // namespace selftest
#endif /* #if CHECKING_P */
#endif /* #ifndef GENERATOR_FILE */