From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx2.suse.de (mx2.suse.de [195.135.220.15]) by sourceware.org (Postfix) with ESMTPS id 7F546383580D for ; Fri, 7 May 2021 11:34:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 7F546383580D Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=rguenther@suse.de X-Virus-Scanned: by amavisd-new at test-mx.suse.de Received: from relay2.suse.de (unknown [195.135.221.27]) by mx2.suse.de (Postfix) with ESMTP id 58BF4B14D; Fri, 7 May 2021 11:34:32 +0000 (UTC) Date: Fri, 7 May 2021 13:34:32 +0200 (CEST) From: Richard Biener To: Joel Hutton cc: "gcc-patches@gcc.gnu.org" , Richard Sandiford , Tamar Christina Subject: Re: [vect] Support min/max + index pattern In-Reply-To: Message-ID: References: User-Agent: Alpine 2.21 (LSU 202 2017-01-01) MIME-Version: 1.0 X-Spam-Status: No, score=-5.4 required=5.0 tests=BAYES_00, KAM_DMARC_STATUS, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org Content-Type: text/plain; charset=ISO-8859-15 Content-Transfer-Encoding: 8BIT X-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 07 May 2021 11:34:35 -0000 On Wed, 5 May 2021, Joel Hutton wrote: > Hi all, > > looking for some feedback on this, one thing I would like to draw > attention to is the fact that this pattern requires 2 separate dependent > reductions in the epilogue. The accumulator vector for the > maximum/minimum elements can be reduced to a scalar result trivially > with a min/max, but getting the index from accumulator vector of indices > is more complex and requires using the position of the maximum/minimum > scalar result value within the accumulator vector to create a mask. > > The given solution works but it's slightly messy. > vect_create_epilogue_for_reduction creates the epilogue for one > vectorized scalar stmt at a time. This modification makes one invocation > create the epilogue for both related stmts and marks the other as > 'done'. Alternate suggestions are welcome. So I'm not looking at the very details in the patch but I think a concept of "dependent" reductions might be useful (there might be related patterns that could be vectorized). So during reduction discovery detect unhandled multi-uses and queue those for later re-evaluation (in case we analyze the value reduction first). Discover the index reduction as regular reduction. Upon re-analyzing the value reduction allow multi-uses that are reductions themselves and note the dependence in some new stmt_vinfo field. Then during reduction analysis we can verify if we handle a particular dependence and during code-gen we can ensure to only code-gen one epilogue and have access to the other part. That said, I'd make the thing a bit more generic in appearance but otherwise yes, we do need to handle this together somehow. + /* For handling multi phi reductions. */ + tree scalar_result; + stmt_vec_info reduc_multi_use_related_stmt; + gimple* reduc_multi_use_result; + tree induc_val; + tree initial_def; + bool is_minmax_index; + bool is_minmax; + bool epilog_finished; which should ideally reduce to a single field then. Oh, and make sure an SLP variant is supported. for (int i = 0; i < n; i++) { if (data[2*i] < best1) { best1 = data[2*i]; best_i1 = 2*i; } if (data[2*i+1] < best2) { best2 = data[2*i+1]; best_i2 = 2*i; } } Richard. > Joel > > [vect] Support min/max + index pattern > > Add the capability to vect-loop to support the following pattern. > > for (int i = 0; i < n; i ++) > { > if (data[i] < best) > { > best = data[i]; > best_i = i; > } > } > > gcc/ChangeLog: > > * tree-vect-loop.c (vect_reassociating_reduction_simple_p): New > function. > (vect_recog_minmax_index_pattern): New function. > (vect_is_simple_reduction): Add multi_use_reduction case. > (vect_create_epilog_for_reduction): Add minmax+index epilogue handling. > -- Richard Biener SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg, Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)