From b94c2dc138c60636e3898b04c1026cbb1b868b26 Mon Sep 17 00:00:00 2001 From: Tom de Vries Date: Tue, 1 May 2018 19:16:43 +0000 Subject: [PATCH] Add VEC_ORDERED_REMOVE_IF 2018-05-01 Tom de Vries PR other/83786 * 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. From-SVN: r259808 --- gcc/ChangeLog | 11 ++++++++++ gcc/dwarf2cfi.c | 19 ++++++----------- gcc/lto-streamer-out.c | 26 +++++++---------------- gcc/tree-vect-patterns.c | 10 +++++---- gcc/vec.c | 46 ++++++++++++++++++++++++++++++++++++++++ gcc/vec.h | 34 +++++++++++++++++++++++++++++ 6 files changed, 112 insertions(+), 34 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 2afdd79b158..5d319c8d588 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2018-05-01 Tom de Vries + + PR other/83786 + * 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. + 2018-05-01 Prathamesh Kulkarni PR tree-optimization/82665 diff --git a/gcc/dwarf2cfi.c b/gcc/dwarf2cfi.c index 07e6a5a2887..4cfb91b8d40 100644 --- a/gcc/dwarf2cfi.c +++ b/gcc/dwarf2cfi.c @@ -2719,7 +2719,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. @@ -2730,20 +2730,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 70476dc6da8..f614aef201f 100644 --- a/gcc/lto-streamer-out.c +++ b/gcc/lto-streamer-out.c @@ -2360,24 +2360,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 621ed07758f..5c2578f0465 100644 --- a/gcc/tree-vect-patterns.c +++ b/gcc/tree-vect-patterns.c @@ -4483,7 +4483,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); @@ -4545,9 +4544,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 695cd1eba5a..11924a80a2d 100644 --- a/gcc/vec.c +++ b/gcc/vec.c @@ -382,6 +382,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 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 @@ -443,6 +488,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 4d2046c04af..2d1f468ca1c 100644 --- a/gcc/vec.h +++ b/gcc/vec.h @@ -1028,6 +1028,40 @@ vec::ordered_remove (unsigned ix) } +/* Remove elements in [START, END) from VEC for which COND holds. Ordering of + remaining elements is preserved. This is 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 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. */ -- 2.30.2