[ was: Re: [libgomp, openacc, openmp, PR83046] Prune removed funcs from
offload table ]
On 12/28/2017 05:06 PM, Jakub Jelinek wrote:
On Thu, Dec 28, 2017 at 04:53:29PM +0100, Tom de Vries wrote:
--- a/gcc/lto-cgraph.c
+++ b/gcc/lto-cgraph.c
@@ -1111,6 +1111,16 @@ output_offload_tables (void)
struct lto_simple_output_block *ob
= lto_create_simple_output_block (LTO_section_offload_table);
+ for (unsigned i = 0; i < vec_safe_length (offload_funcs);)
+ {
+ if (!cgraph_node::get ((*offload_funcs)[i]))
+ {
+ offload_funcs->ordered_remove (i);
+ continue;
+ }
+ i++;
+ }
This has O(n^2) complexity for n == vec_safe_length (offload_funcs).
Can't you instead just have 2 IVs, one for where we read the vector elt and
one for where we write it if the 2 are different, then truncate the vector
if needed at the end?
I wonder if it makes sense to add this function to the vec interface.
Any comments?
Thanks,
- Tom
Add vec::ordered_remove_if
---
gcc/vec.c | 21 +++++++++++++++++++++
gcc/vec.h | 39 +++++++++++++++++++++++++++++++++++++++
2 files changed, 60 insertions(+)
diff --git a/gcc/vec.c b/gcc/vec.c
index 9a80f34..91e2464 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -403,6 +403,26 @@ test_ordered_remove ()
ASSERT_EQ (9, v.length ());
}
+static bool
+remove_5_7_p (const int &a)
+{
+ return a == 5 || a == 7;
+}
+
+/* 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);
+ v.ordered_remove_if (remove_5_7_p);
+ ASSERT_EQ (4, v[4]);
+ ASSERT_EQ (6, v[5]);
+ ASSERT_EQ (8, v[6]);
+ ASSERT_EQ (8, v.length ());
+}
+
/* Verify that vec::unordered_remove works correctly. */
static void
@@ -464,6 +484,7 @@ vec_c_tests ()
test_pop ();
test_safe_insert ();
test_ordered_remove ();
+ test_ordered_remove_if ();
test_unordered_remove ();
test_block_remove ();
test_qsort ();
diff --git a/gcc/vec.h b/gcc/vec.h
index f55a41f..857e4f4 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -571,6 +571,7 @@ public:
void truncate (unsigned);
void quick_insert (unsigned, const T &);
void ordered_remove (unsigned);
+ void ordered_remove_if (bool (*) (const T &));
void unordered_remove (unsigned);
void block_remove (unsigned, unsigned);
void qsort (int (*) (const void *, const void *));
@@ -1013,6 +1014,31 @@ vec<T, A, vl_embed>::ordered_remove (unsigned ix)
}
+/* Remove all elements from this vector for which REMOVE_ELEM_P (elem) holds.
+ Ordering of remaining elements is preserved. This is an an O(N)
+ operation. */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::ordered_remove_if (bool (*remove_elem_p) (const T &))
+{
+ unsigned int n = length ();
+ unsigned int write_index = 0;
+ for (unsigned int read_index = 0; read_index < n; ++read_index)
+ {
+ bool remove_p = remove_elem_p (read_index);
+ if (remove_p)
+ continue;
+
+ if (read_index != write_index)
+ m_vecdata[write_index] = m_vecdata[read_index];
+
+ write_index++;
+ }
+ truncate (write_index);
+}
+
+
/* Remove an element from the IXth position of this vector. Ordering of
remaining elements is destroyed. This is an O(1) operation. */
@@ -1334,6 +1360,7 @@ public:
void quick_insert (unsigned, const T &);
void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO);
void ordered_remove (unsigned);
+ void ordered_remove_if (bool (*) (const T &));
void unordered_remove (unsigned);
void block_remove (unsigned, unsigned);
void qsort (int (*) (const void *, const void *));
@@ -1779,6 +1806,18 @@ vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix)
}
+/* Remove all elements from this vector for which REMOVE_ELEM_P (elem) holds.
+ Ordering of remaining elements is preserved. This is an an O(N)
+ operation. */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::ordered_remove_if (bool (*remove_elem_p) (const T &))
+{
+ m_vec->ordered_remove_if (remove_elem_p);
+}
+
+
/* Remove an element from the IXth position of this vector. Ordering
of remaining elements is destroyed. This is an O(1) operation. */
