[ was: Re: [RFC] Add vec::ordered_remove_if ]
On 01/02/2018 03:08 PM, Richard Biener wrote:
On Fri, Dec 29, 2017 at 2:55 PM, Tom de Vries <tom_devr...@mentor.com> wrote:
[ 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?
Hmm. We do have quite some cases in the tree doing this kind of
operation - can you try finding one or two and see if it fits?
Done.
[ I wonder though whether skipping element 0 in connect_traces is
intentional or not. ]
If we only could use lambdas here...
I found having to write a separate function cumbersome, so I rewrote the
function into macros VEC_ORDERED_REMOVE_IF and
VEC_ORDERED_REMOVE_IF_FROM_TO, which gives a syntax somewhat similar to
a lambda.
Oh, and I somehow miss a start/end index for operating on a vector part?
Done.
Bootstrapped and reg-tested on x86_64.
OK for trunk?
Thanks,
- Tom
Add VEC_ORDERED_REMOVE_IF
2018-01-03 Tom de Vries <t...@codesourcery.com>
* vec.h (VEC_ORDERED_REMOVE_IF, VEC_ORDERED_REMOVE_IF_FROM_TO): Define.
* vec.c (test_ordered_remove_if): New function.
(vec_c_tests): Call test_ordered_remove_if.
* dwarf2cfi.c (connect_traces): Use VEC_ORDERED_REMOVE_IF_FROM_TO.
* lto-streamer-out.c (prune_offload_funcs): Use VEC_ORDERED_REMOVE_IF.
* tree-vect-patterns.c (vect_pattern_recog_1): Use
VEC_ORDERED_REMOVE_IF.
---
gcc/dwarf2cfi.c | 19 +++++++------------
gcc/lto-streamer-out.c | 26 ++++++++------------------
gcc/tree-vect-patterns.c | 10 ++++++----
gcc/vec.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++
gcc/vec.h | 34 ++++++++++++++++++++++++++++++++++
5 files changed, 101 insertions(+), 34 deletions(-)
diff --git a/gcc/dwarf2cfi.c b/gcc/dwarf2cfi.c
index 7a70639..7732ab2 100644
--- a/gcc/dwarf2cfi.c
+++ b/gcc/dwarf2cfi.c
@@ -2703,7 +2703,7 @@ before_next_cfi_note (rtx_insn *start)
static void
connect_traces (void)
{
- unsigned i, n = trace_info.length ();
+ unsigned i, n;
dw_trace_info *prev_ti, *ti;
/* ??? Ideally, we should have both queued and processed every trace.
@@ -2714,20 +2714,15 @@ connect_traces (void)
these are not "real" instructions, and should not be considered.
This could be generically useful for tablejump data as well. */
/* Remove all unprocessed traces from the list. */
- for (i = n - 1; i > 0; --i)
- {
- ti = &trace_info[i];
- if (ti->beg_row == NULL)
- {
- trace_info.ordered_remove (i);
- n -= 1;
- }
- else
- gcc_assert (ti->end_row != NULL);
- }
+ unsigned ix, ix2;
+ VEC_ORDERED_REMOVE_IF_FROM_TO (trace_info, ix, ix2, ti, 1,
+ trace_info.length (), ti->beg_row == NULL);
+ FOR_EACH_VEC_ELT (trace_info, ix, ti)
+ gcc_assert (ti->end_row != NULL);
/* Work from the end back to the beginning. This lets us easily insert
remember/restore_state notes in the correct order wrt other notes. */
+ n = trace_info.length ();
prev_ti = &trace_info[n - 1];
for (i = n - 1; i > 0; --i)
{
diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c
index ef17083..b0993c7 100644
--- a/gcc/lto-streamer-out.c
+++ b/gcc/lto-streamer-out.c
@@ -2355,24 +2355,14 @@ prune_offload_funcs (void)
if (!offload_funcs)
return;
- unsigned int write_index = 0;
- for (unsigned read_index = 0; read_index < vec_safe_length (offload_funcs);
- read_index++)
- {
- tree fn_decl = (*offload_funcs)[read_index];
- bool remove_p = cgraph_node::get (fn_decl) == NULL;
- if (remove_p)
- continue;
-
- DECL_PRESERVE_P (fn_decl) = 1;
-
- if (write_index != read_index)
- (*offload_funcs)[write_index] = (*offload_funcs)[read_index];
-
- write_index++;
- }
-
- offload_funcs->truncate (write_index);
+ unsigned ix, ix2;
+ tree *elem_ptr;
+ VEC_ORDERED_REMOVE_IF (*offload_funcs, ix, ix2, elem_ptr,
+ cgraph_node::get (*elem_ptr) == NULL);
+
+ tree fn_decl;
+ FOR_EACH_VEC_ELT (*offload_funcs, ix, fn_decl)
+ DECL_PRESERVE_P (fn_decl) = 1;
}
/* Main entry point from the pass manager. */
diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c
index a2c6293..2a5d056 100644
--- a/gcc/tree-vect-patterns.c
+++ b/gcc/tree-vect-patterns.c
@@ -4165,7 +4165,6 @@ vect_pattern_recog_1 (vect_recog_func *recog_func,
tree type_in, type_out;
enum tree_code code;
int i;
- gimple *next;
stmts_to_replace->truncate (0);
stmts_to_replace->quick_push (stmt);
@@ -4232,9 +4231,12 @@ vect_pattern_recog_1 (vect_recog_func *recog_func,
/* Patterns cannot be vectorized using SLP, because they change the order of
computation. */
if (loop_vinfo)
- FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next)
- if (next == stmt)
- LOOP_VINFO_REDUCTIONS (loop_vinfo).ordered_remove (i);
+ {
+ unsigned ix, ix2;
+ gimple **elem_ptr;
+ VEC_ORDERED_REMOVE_IF (LOOP_VINFO_REDUCTIONS (loop_vinfo), ix, ix2,
+ elem_ptr, *elem_ptr == stmt);
+ }
/* It is possible that additional pattern stmts are created and inserted in
STMTS_TO_REPLACE. We create a stmt_info for each of them, and mark the
diff --git a/gcc/vec.c b/gcc/vec.c
index 9a80f34..eb382f5 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -403,6 +403,51 @@ test_ordered_remove ()
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
@@ -464,6 +509,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..dd914f8 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -1013,6 +1013,40 @@ vec<T, A, vl_embed>::ordered_remove (unsigned ix)
}
+/* Remove elements in [START, END) from VEC for which COND holds. Ordering of
+ remaining elements is preserved. This is an an O(N) operation. */
+
+#define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \
+ elem_ptr, start, end, cond) \
+ { \
+ gcc_assert ((end) <= (vec).length ()); \
+ for (read_index = write_index = (start); read_index < (end); \
+ ++read_index) \
+ { \
+ elem_ptr = &(vec)[read_index]; \
+ bool remove_p = (cond); \
+ if (remove_p) \
+ continue; \
+ \
+ if (read_index != write_index) \
+ (vec)[write_index] = (vec)[read_index]; \
+ \
+ write_index++; \
+ } \
+ \
+ if (read_index - write_index > 0) \
+ (vec).block_remove (write_index, read_index - write_index); \
+ }
+
+
+/* Remove elements from VEC for which COND holds. Ordering of remaining
+ elements is preserved. This is an an O(N) operation. */
+
+#define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \
+ cond) \
+ VEC_ORDERED_REMOVE_IF_FROM_TO (vec, read_index, write_index, \
+ elem_ptr, 0, (vec).length (), cond)
+
/* Remove an element from the IXth position of this vector. Ordering of
remaining elements is destroyed. This is an O(1) operation. */
