From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 37F653858D20 for ; Fri, 4 Feb 2022 11:01:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 37F653858D20 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 27C9821901; Fri, 4 Feb 2022 11:01:25 +0000 (UTC) Received: from murzim.suse.de (murzim.suse.de [10.160.4.192]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id E4FD4A3B83; Fri, 4 Feb 2022 11:01:24 +0000 (UTC) Date: Fri, 4 Feb 2022 12:01:24 +0100 (CET) From: Richard Biener To: Richard Sandiford cc: Richard Biener via Gcc-patches , bin.cheng@linux.alibaba.com Subject: Re: [PATCH] tree-optimization/100499 - niter analysis and multiple_of_p In-Reply-To: Message-ID: <11q58414-qs1s-55pq-rp8-sqn9p90p67r@fhfr.qr> References: <20220126130458.A362B13DF9@imap2.suse-dmz.suse.de> MIME-Version: 1.0 X-Spam-Status: No, score=-11.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org Content-Type: text/plain; charset=utf-8 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, 04 Feb 2022 11:01:28 -0000 On Fri, 4 Feb 2022, Richard Sandiford wrote: > Richard Biener writes: > > On Fri, 4 Feb 2022, Richard Sandiford wrote: > >> Richard Biener via Gcc-patches writes: > >> > niter analysis uses multiple_of_p which currently assumes > >> > operations like MULT_EXPR do not wrap. We've got to rely on this > >> > for optimizing size expressions like those in DECL_SIZE and those > >> > generally use unsigned arithmetic with no indication that they > >> > are not expected to wrap. To preserve that the following adds > >> > a parameter to multiple_of_p, defaulted to true, indicating that > >> > the TOP expression is not expected to wrap for outer computations > >> > in TYPE. This mostly follows a patch proposed by Bin last year > >> > with the conversion behavior added. > >> > > >> > Applying to all users the new effect is that upon type conversions > >> > in the TOP expression the behavior will switch to honor > >> > TYPE_OVERFLOW_UNDEFINED for the converted sub-expressions. > >> > > >> > The patch also changes the occurance in niter analysis that we > >> > know is problematic and we have testcases for to pass false > >> > to multiple_of_p. The patch also contains a change to the > >> > PR72817 fix from Bin to avoid regressing gcc.dg/tree-ssa/loop-42.c. > >> > > >> > The intent for stage1 is to introduce a size_multiple_of_p and > >> > internalize the added parameter so all multiple_of_p users will > >> > honor TYPE_OVERFLOW_UNDEFINED and users dealing with size expressions > >> > need to be switched to size_multiple_of_p. > >> > > >> > Bootstrapped and tested on x86_64-unknown-linux-gnu with all languages > >> > and {,-m32} testing. > >> > > >> > The patch applies ontop of the three earlier posted ones that touch > >> > multiple_of_p but have not yet been reviewed/pushed. > >> > > >> > OK? > >> > > >> > Thanks, > >> > Richard. > >> > > >> > 2022-01-26 Richard Biener > >> > > >> > PR tree-optimization/100499 > >> > * fold-const.h (multiple_of_p): Add nowrap parameter, defaulted > >> > to true. > >> > * fold-const.cc (multiple_of_p): Likewise. Honor it for > >> > MULT_EXPR, PLUS_EXPR and MINUS_EXPR and pass it along, > >> > switching to false for conversions. > >> > * tree-ssa-loop-niter.cc (number_of_iterations_ne): Do not > >> > claim the outermost expression does not wrap when calling > >> > multiple_of_p. Refactor the check done to check the > >> > original IV, avoiding a bias that might wrap. > >> > > >> > * gcc.dg/torture/pr100499-1.c: New testcase. > >> > * gcc.dg/torture/pr100499-2.c: Likewise. > >> > * gcc.dg/torture/pr100499-3.c: Likewise. > >> > > >> > Co-authored-by: Bin Cheng > >> > --- > >> > gcc/fold-const.cc | 81 +++++++++++++++-------- > >> > gcc/fold-const.h | 2 +- > >> > gcc/testsuite/gcc.dg/torture/pr100499-1.c | 27 ++++++++ > >> > gcc/testsuite/gcc.dg/torture/pr100499-2.c | 16 +++++ > >> > gcc/testsuite/gcc.dg/torture/pr100499-3.c | 14 ++++ > >> > gcc/tree-ssa-loop-niter.cc | 52 ++++++--------- > >> > 6 files changed, 131 insertions(+), 61 deletions(-) > >> > create mode 100644 gcc/testsuite/gcc.dg/torture/pr100499-1.c > >> > create mode 100644 gcc/testsuite/gcc.dg/torture/pr100499-2.c > >> > create mode 100644 gcc/testsuite/gcc.dg/torture/pr100499-3.c > >> > > >> > diff --git a/gcc/fold-const.cc b/gcc/fold-const.cc > >> > index a0a4913c45e..7c204fb6265 100644 > >> > --- a/gcc/fold-const.cc > >> > +++ b/gcc/fold-const.cc > >> > @@ -14062,10 +14062,16 @@ fold_binary_initializer_loc (location_t loc, tree_code code, tree type, > >> > SAVE_EXPR (I) * SAVE_EXPR (J) > >> > > >> > (where the same SAVE_EXPR (J) is used in the original and the > >> > - transformed version). */ > >> > + transformed version). > >> > + > >> > + NOWRAP specifies whether all outer operations in TYPE should > >> > + be considered not wrapping. Any type conversion within TOP acts > >> > + as a barrier and we will fall back to NOWRAP being false. > >> > + NOWRAP is mostly used to treat expressions in TYPE_SIZE and friends > >> > + as not wrapping even though they are generally using unsigned arithmetic. */ > >> > > >> > int > >> > -multiple_of_p (tree type, const_tree top, const_tree bottom) > >> > +multiple_of_p (tree type, const_tree top, const_tree bottom, bool nowrap) > >> > { > >> > gimple *stmt; > >> > tree op1, op2; > >> > @@ -14083,10 +14089,17 @@ multiple_of_p (tree type, const_tree top, const_tree bottom) > >> > a multiple of BOTTOM then TOP is a multiple of BOTTOM. */ > >> > if (!integer_pow2p (bottom)) > >> > return 0; > >> > - return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom) > >> > - || multiple_of_p (type, TREE_OPERAND (top, 0), bottom)); > >> > + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom, nowrap) > >> > + || multiple_of_p (type, TREE_OPERAND (top, 0), bottom, nowrap)); > >> > > >> > case MULT_EXPR: > >> > + /* If the multiplication can wrap we cannot recurse further unless > >> > + the second operand is a power of two which is where wrapping > >> > + does not matter. */ > >> > + if (!nowrap > >> > + && !TYPE_OVERFLOW_UNDEFINED (type) > >> > + && !integer_pow2p (TREE_OPERAND (top, 1))) > >> > + return 0; > >> > >> I think I'm missing something, but isn't the key thing whether bottom > >> is a power of 2? E.g. as it stands it looks like we'd still say that a > >> wrapping x * 2 is a multiple of 3 based purely on x being a multiple of 3, > >> thanks to… > > > > I had to think about this as well but the logic is that (as you noted), > > we below test ... > > > >> > if (TREE_CODE (bottom) == INTEGER_CST) > >> > { > >> > op1 = TREE_OPERAND (top, 0); > >> > @@ -14095,24 +14108,24 @@ multiple_of_p (tree type, const_tree top, const_tree bottom) > >> > std::swap (op1, op2); > >> > if (TREE_CODE (op2) == INTEGER_CST) > >> > { > >> > - if (multiple_of_p (type, op2, bottom)) > >> > + if (multiple_of_p (type, op2, bottom, nowrap)) > >> > return 1; > >> > /* Handle multiple_of_p ((x * 2 + 2) * 4, 8). */ > >> > - if (multiple_of_p (type, bottom, op2)) > >> > + if (multiple_of_p (type, bottom, op2, nowrap)) > >> > { > >> > widest_int w = wi::sdiv_trunc (wi::to_widest (bottom), > >> > wi::to_widest (op2)); > >> > if (wi::fits_to_tree_p (w, TREE_TYPE (bottom))) > >> > { > >> > op2 = wide_int_to_tree (TREE_TYPE (bottom), w); > >> > - return multiple_of_p (type, op1, op2); > >> > + return multiple_of_p (type, op1, op2, nowrap); > >> > } > >> > } > >> > - return multiple_of_p (type, op1, bottom); > >> > + return multiple_of_p (type, op1, bottom, nowrap); > >> > } > >> > } > >> > - return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom) > >> > - || multiple_of_p (type, TREE_OPERAND (top, 0), bottom)); > >> > + return (multiple_of_p (type, TREE_OPERAND (top, 1), bottom, nowrap) > >> > + || multiple_of_p (type, TREE_OPERAND (top, 0), bottom, nowrap)); > >> > >> …the second arm of the || here. > > > > .. oh, we use ||, I thought about this again for the plus case > > and there we use && which means we'll have bottom a power of two. > > > > I think back last year when we discussed this Bin said having > > bottom a power of two is unnecessarily restrictive. > > > >> On the other hand, a wrapping x * 6 is a multiple of 2 even though 6 > >> isn't a power of 2. > > > > Yes, for bottom being a power of two the logic would definitely apply. > > > > So, changing it to > > > > if (!nowrap > > && !TYPE_OVERFLOW_UNDEFINED (type) > > && !integer_pow2p (bottom)) > > return 0; > > > > would work. > > > > I suppose for consistency we should change the condition on the > > plus/minus case in the same way. > > Yeah, agreed. > > Like you were discussing in the PR trail, it would be great if ranger > could help to cut down the false negatives here… Yes. Note that the patch leaves nowrap = true on all but one caller so we have something to backport to fix the case we have a testcase for. For GCC 13 I plan to drop the defaulting as indicated and then we can also look to either just honor global ranges or do even more fancy things. I intentionally tried to come up with the most simplistic and obviously correct patch at this point. I'm re-testing currently and will post the updated patch. Richard.