From patchwork Fri Jan 5 21:06:10 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 856274 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-470267-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="B6npMfrP"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3zD1h55Z6Nz9t2Q for ; Sat, 6 Jan 2018 10:53:07 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:cc:references:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=llMQ2LZMsWMkgDXtO P5/RrFNDgSmTNFj8HpAP4CxGAiDIf8zNGibSOUuQwzwFx9X7IUmwWldaCMHsiW9C BgxNcrswx6zmCewrTWs0OE+K26UEAGxKOmUbc9BIlgebPauKhV2WoeHixskgguku kaD02ShU+r1eGKA4vEydE8ttq4= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:cc:references:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=zn/SCClB3PbaBt6fNeQvyPj kL2c=; b=B6npMfrPo17aNNsPXaiXugZiw2bhGGoEMMhAitFI3AFlW+MmHzHcx4m VdtikD81jJCx6gQA3n3gcb7dB913unB8ayPs4A0GgsYD1Japb1ChLPVsCpf7dK8Q GzTF5AoHQTVLS45VZgterbz2Ius1qHuYidUvkiHdKvx5jUXq3UOk= Received: (qmail 44428 invoked by alias); 5 Jan 2018 21:06:24 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 44418 invoked by uid 89); 5 Jan 2018 21:06:24 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.8 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS, URIBL_RED autolearn=ham version=3.3.2 spammy=cumbersome, sk:unorder X-HELO: relay1.mentorg.com Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 05 Jan 2018 21:06:21 +0000 Received: from nat-ies.mentorg.com ([192.94.31.2] helo=SVR-IES-MBX-04.mgc.mentorg.com) by relay1.mentorg.com with esmtps (TLSv1.2:ECDHE-RSA-AES256-SHA384:256) id 1eXZBy-0001B7-P9 from Tom_deVries@mentor.com ; Fri, 05 Jan 2018 13:06:18 -0800 Received: from [172.30.72.14] (137.202.0.87) by SVR-IES-MBX-04.mgc.mentorg.com (139.181.222.4) with Microsoft SMTP Server (TLS) id 15.0.1320.4; Fri, 5 Jan 2018 21:06:14 +0000 Subject: [PATCH] Add VEC_ORDERED_REMOVE_IF To: Richard Biener CC: Jakub Jelinek , GCC Patches References: <048f596a-75d5-c897-2630-d6230640cf40@mentor.com> <20171228160657.GJ1833@tucnak> <86f69704-0721-a81b-96d9-d98a3bbd53ac@mentor.com> From: Tom de Vries Message-ID: <7d298d9d-690d-e8d9-0b03-50e1de940a20@mentor.com> Date: Fri, 5 Jan 2018 22:06:10 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.5.0 MIME-Version: 1.0 In-Reply-To: X-ClientProxiedBy: svr-ies-mbx-01.mgc.mentorg.com (139.181.222.1) To SVR-IES-MBX-04.mgc.mentorg.com (139.181.222.4) [ 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 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 * 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 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::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. */