From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x632.google.com (mail-ej1-x632.google.com [IPv6:2a00:1450:4864:20::632]) by sourceware.org (Postfix) with ESMTPS id D6700385802A for ; Tue, 27 Apr 2021 08:29:23 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org D6700385802A Received: by mail-ej1-x632.google.com with SMTP id zg3so6719070ejb.8 for ; Tue, 27 Apr 2021 01:29:23 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=GO41x+W+XOlA1F19dxyaFrVopt13jIEXaqpavoOy7zA=; b=rk2Ms6PdW+Rp4TiaZGwIgh4u0vW3E3Fu9aKimQDgQuALJjjXZJW/MUxA/2fZ5RJmz1 X8P1P+yka99oM/XAOBrxKKPd4lT+ujFP20OD5hJPZQv/cnw6hTcHf2h/boA1v9eFqCJp ZPCEOlUdISnImjJYhKeEfuzvolpKECandL3C2GffKxk5LqSzxr0iBJuJ49J+N+RAGZDS ZXh4pjdNOJPcNHIJ55LIDGWuT2Yf5/VYvIGSyu/bJE943c+37v/fO7cUIa2N1u/fW5PR WttAyUyCgx4FjiESd9d0EL7iTLiwX5cyKiYW5sFNK1Le6pwSYxuf+muniX4jTPQB1pxA 6BkA== X-Gm-Message-State: AOAM5325aIxK85cHMkfWzVdY+0g8sRCWL3kTUN+dKCuzuOnlc7biNqBC uvaJW4T8Ux0aFES5hlFhsfFrlNGG4F2oANYLCxU= X-Google-Smtp-Source: ABdhPJwISwWw9K3rWasThPg62jWsoFcxAD1cYo1Y76vnB9YUzduNsWb8vpRefFKrKYViSdSF2cx7rco7rx7DjcBgQHE= X-Received: by 2002:a17:906:36d1:: with SMTP id b17mr23225465ejc.235.1619512162344; Tue, 27 Apr 2021 01:29:22 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Richard Biener Date: Tue, 27 Apr 2021 10:29:11 +0200 Message-ID: Subject: Re: [PATCH] tree-optimization: Optimize division followed by multiply [PR95176] To: Victor Tong Cc: "gcc-patches@gcc.gnu.org" Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-3.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, 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 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: Tue, 27 Apr 2021 08:29:25 -0000 On Thu, Apr 1, 2021 at 1:03 AM Victor Tong via Gcc-patches wrote: > > Hello, > > This patch fixes PR tree-optimization/95176. A new pattern in match.pd wa= s added to transform "a * (b / a)" --> "b - (b % a)". A new test case was a= lso added to cover this scenario. > > The new pattern interfered with the existing pattern of "X - (X / Y) * Y"= . In some cases (such as in fn4() in gcc/testsuite/gcc.dg/fold-minus-6.c), = the new pattern is applied causing the existing pattern to no longer apply.= This results in worse code generation because the expression is left as "X= - (X - Y)". An additional subtraction pattern of "X - (X - Y) --> Y" was a= dded to this patch to avoid this regression. > > I also didn't remove the existing pattern because it triggered in more ca= ses than the new pattern because of a tree_invariant_p check that's inserte= d by genmatch for the new pattern. Yes, we do not handle using Y multiple times when it might contain side-effects in GENERIC folding (comments in genmatch suggest we can use save_expr but we don't implement this [anymore]). On GIMPLE there's also the issue that your new pattern creates a complex expression which makes it failed to be used by value-numbering for example where the old pattern was OK (eventually, if no conversion was required). So indeed it looks OK to preserve both. I wonder why you needed the +/* X - (X - Y) --> Y */ +(simplify + (minus (convert1? @0) (convert2? (minus @@0 @1))) + (if ((INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type)) && TYPE_OVERFLOW_UNDEFINED(type)) + (convert @1))) pattern since it should be handled by /* Match patterns that allow contracting a plus-minus pair irrespective of overflow issues. */ /* (A +- B) - A -> +- B */ /* (A +- B) -+ B -> A */ /* A - (A +- B) -> -+ B */ /* A +- (B -+ A) -> +- B */ in particular (simplify (minus @0 (nop_convert1? (minus (nop_convert2? @0) @1))) (view_convert @1)) if there's supported cases missing I'd rather extend this pattern than replicating it. +/* X * (Y / X) is the same as Y - (Y % X). */ +(simplify + (mult:c (convert1? @0) (convert2? (trunc_div @1 @@0))) + (if (INTEGRAL_TYPE_P (type) || VECTOR_INTEGER_TYPE_P (type)) + (minus (convert @1) (convert (trunc_mod @1 @0))))) note that if you're allowing vector types you have to use (view_convert ...) in the transform and you also need to make sure that the target can expand the modulo - I suspect that's an issue with the existing pattern as well. I don't know of any vector ISA that supports modulo (or integer division, that is). Restricting the patterns to integer types is probably the most sensible solution. Thanks, Richard. > I verified that all "make -k check" tests pass when targeting x86_64-pc-l= inux-gnu. > > 2021-03-31 Victor Tong > > gcc/ChangeLog: > > * match.pd: Two new patterns: One to optimize division followed b= y multiply and the other to avoid a regression as explained above > > gcc/testsuite/ChangeLog: > > * gcc.dg/tree-ssa/20030807-10.c: Update existing test to look for= a subtraction because a shift is no longer emitted > * gcc.dg/pr95176.c: New test to cover optimizing division followe= d by multiply > > I don't have write access to the GCC repo but I've completed the FSF pape= rwork as I plan to make more contributions in the future. I'm looking for a= sponsorship from an existing GCC maintainer before applying for write acce= ss. > > Thanks, > Victor