From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2001:67c:2178:6::1c]) by sourceware.org (Postfix) with ESMTPS id 4F1B73858D35; Mon, 28 Aug 2023 13:15:00 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4F1B73858D35 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out1.suse.de (Postfix) with ESMTP id 17D1C21116; Mon, 28 Aug 2023 13:14:59 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1693228499; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=GVHwU6VbO30G0uU89ywDPAfesuuiG9bymyvywc5+x7U=; b=UOgi0XWGtlyTPtthUFJl75c8KVou+rtYW6r9+2qdiKEdLbBZxPCT3o3EoiI9RKi5sZWfx3 IedPvDrKKE6FBMOTi2Gkar1h2X6MsBcH0fCoZ9DFJbrh6RQcWR/so1O7x2lnoCoKlAHSOe AsdHVJEgExdj9uko8Zg7l3DugPqpf8E= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1693228499; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=GVHwU6VbO30G0uU89ywDPAfesuuiG9bymyvywc5+x7U=; b=opnIhXUuTM+WTyWK/rNTIgvF0eV2adWcHKM/WcRwQk7CYfOZAM7GGL9i9xZDc8BT4GGB4a P9gCpmNSQC9O8JDw== Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (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 40B4B2C142; Mon, 28 Aug 2023 13:14:58 +0000 (UTC) Date: Mon, 28 Aug 2023 13:14:57 +0000 (UTC) From: Richard Biener To: guojiufu cc: jeffreyalaw@gmail.com, richard.sandiford@arm.com, gcc-patches@gcc.gnu.org, amacleod@redhat.com, aldyh@redhat.com, segher@kernel.crashing.org, dje.gcc@gmail.com, linkw@gcc.gnu.org, bergner@linux.ibm.com Subject: Re: Ping^^ [PATCH V5 2/2] Optimize '(X - N * M) / N' to 'X / N - M' if valid In-Reply-To: <11eab982cf225b32e34e8d9c5f7f1947@linux.ibm.com> Message-ID: References: <20230718140544.3497370-1-guojiufu@linux.ibm.com> <20230718140544.3497370-2-guojiufu@linux.ibm.com> <11eab982cf225b32e34e8d9c5f7f1947@linux.ibm.com> User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-11.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,KAM_SHORT,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Wed, 23 Aug 2023, guojiufu wrote: > Hi, > > I would like to have a gentle ping... > > BR, > Jeff (Jiufu Guo) > > On 2023-08-07 10:45, guojiufu via Gcc-patches wrote: > > Hi, > > > > Gentle ping... > > > > On 2023-07-18 22:05, Jiufu Guo wrote: > >> Hi, > >> > >> Integer expression "(X - N * M) / N" can be optimized to "X / N - M" > >> if there is no wrap/overflow/underflow and "X - N * M" has the same > >> sign with "X". > >> > >> Compare the previous version: > >> https://gcc.gnu.org/pipermail/gcc-patches/2023-July/624067.html > >> - APIs: overflow, nonnegative_p and nonpositive_p are moved close > >> to value range. > >> - Use above APIs in match.pd. > >> > >> Bootstrap & regtest pass on ppc64{,le} and x86_64. > >> Is this patch ok for trunk? > >> > >> BR, > >> Jeff (Jiufu Guo) > >> > >> PR tree-optimization/108757 > >> > >> gcc/ChangeLog: > >> > >> * match.pd ((X - N * M) / N): New pattern. > >> ((X + N * M) / N): New pattern. > >> ((X + C) div_rshift N): New pattern. > >> > >> gcc/testsuite/ChangeLog: > >> > >> * gcc.dg/pr108757-1.c: New test. > >> * gcc.dg/pr108757-2.c: New test. > >> * gcc.dg/pr108757.h: New test. > >> > >> --- > >> gcc/match.pd | 85 +++++++++++ > >> gcc/testsuite/gcc.dg/pr108757-1.c | 18 +++ > >> gcc/testsuite/gcc.dg/pr108757-2.c | 19 +++ > >> gcc/testsuite/gcc.dg/pr108757.h | 233 > >> ++++++++++++++++++++++++++++++ > >> 4 files changed, 355 insertions(+) > >> create mode 100644 gcc/testsuite/gcc.dg/pr108757-1.c > >> create mode 100644 gcc/testsuite/gcc.dg/pr108757-2.c > >> create mode 100644 gcc/testsuite/gcc.dg/pr108757.h > >> > >> diff --git a/gcc/match.pd b/gcc/match.pd > >> index 8543f777a28..39dbb0567dc 100644 > >> --- a/gcc/match.pd > >> +++ b/gcc/match.pd > >> @@ -942,6 +942,91 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > >> #endif > >> )))) > >> > >> +#if GIMPLE > >> +(for div (trunc_div exact_div) > >> + /* Simplify (t + M*N) / N -> t / N + M. */ > >> + (simplify > >> + (div (plus:c@4 @0 (mult:c@3 @1 @2)) @2) The :c on the plus isn't necessary? > >> + (with {value_range vr0, vr1, vr2, vr3, vr4;} > >> + (if (INTEGRAL_TYPE_P (type) > >> + && get_range_query (cfun)->range_of_expr (vr1, @1) > >> + && get_range_query (cfun)->range_of_expr (vr2, @2) > >> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2) the multiplication doesn't overflow > >> + && get_range_query (cfun)->range_of_expr (vr0, @0) > >> + && get_range_query (cfun)->range_of_expr (vr3, @3) > >> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr3) the add doesn't overflow > >> + && get_range_query (cfun)->range_of_expr (vr4, @4) > >> + && (TYPE_UNSIGNED (type) > >> + || (vr0.nonnegative_p () && vr4.nonnegative_p ()) > >> + || (vr0.nonpositive_p () && vr4.nonpositive_p ()))) I don't know what this checks - the add result and the add first argument are not of opposite sign. Huh. At least this part needs an explaining comment. Sorry if we hashed this out before, but you can see I forgot and it's not obvious. > >> + (plus (div @0 @2) @1)))) > >> + > >> + /* Simplify (t - M*N) / N -> t / N - M. */ > >> + (simplify > >> + (div (minus@4 @0 (mult:c@3 @1 @2)) @2) > >> + (with {value_range vr0, vr1, vr2, vr3, vr4;} > >> + (if (INTEGRAL_TYPE_P (type) > >> + && get_range_query (cfun)->range_of_expr (vr1, @1) > >> + && get_range_query (cfun)->range_of_expr (vr2, @2) > >> + && range_op_handler (MULT_EXPR).overflow_free_p (vr1, vr2) > >> + && get_range_query (cfun)->range_of_expr (vr0, @0) > >> + && get_range_query (cfun)->range_of_expr (vr3, @3) > >> + && range_op_handler (MINUS_EXPR).overflow_free_p (vr0, vr3) > >> + && get_range_query (cfun)->range_of_expr (vr4, @4) > >> + && (TYPE_UNSIGNED (type) > >> + || (vr0.nonnegative_p () && vr4.nonnegative_p ()) > >> + || (vr0.nonpositive_p () && vr4.nonpositive_p ()))) > >> + (minus (div @0 @2) @1))))) looks like exactly the same - if you use a (for addsub (plus minus) you should be able to do range_op_handler (addsub). > >> + > >> +/* Simplify > >> + (t + C) / N -> t / N + C / N where C is multiple of N. > >> + (t + C) >> N -> t >> N + C>>N if low N bits of C is 0. */ > >> +(for op (trunc_div exact_div rshift) > >> + (simplify > >> + (op (plus@3 @0 INTEGER_CST@1) INTEGER_CST@2) > >> + (with > >> + { > >> + wide_int c = wi::to_wide (@1); > >> + wide_int n = wi::to_wide (@2); > >> + bool is_rshift = op == RSHIFT_EXPR; > >> + bool neg_c = false; > >> + bool ok = false; > >> + value_range vr0; > >> + if (INTEGRAL_TYPE_P (type) > >> + && get_range_query (cfun)->range_of_expr (vr0, @0)) > >> + { > >> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi () > >> + : wi::multiple_of_p (c, n, TYPE_SIGN (type)); > >> + value_range vr1, vr3; > >> + ok = ok && get_range_query (cfun)->range_of_expr (vr1, @1) > >> + && range_op_handler (PLUS_EXPR).overflow_free_p (vr0, vr1) > >> + && get_range_query (cfun)->range_of_expr (vr3, @3) > >> + && (TYPE_UNSIGNED (type) > >> + || (vr0.nonnegative_p () && vr3.nonnegative_p ()) > >> + || (vr0.nonpositive_p () && vr3.nonpositive_p ())); > >> + > >> + /* Try check 'X + C' as 'X - -C' for unsigned. */ > >> + if (!ok && TYPE_UNSIGNED (type) && c.sign_mask () < 0) > >> + { > >> + neg_c = true; > >> + c = -c; > >> + ok = is_rshift ? wi::ctz (c) >= n.to_shwi () > >> + : wi::multiple_of_p (c, n, UNSIGNED); > >> + ok = ok && wi::geu_p (vr0.lower_bound (), c); > >> + } > >> + } > >> + } > >> + (if (ok) > >> + (with > >> + { > >> + wide_int m; > >> + m = is_rshift ? wi::rshift (c, n, TYPE_SIGN (type)) > >> + : wi::div_trunc (c, n, TYPE_SIGN (type)); > >> + m = neg_c ? -m : m; > >> + } why doesn't this look as nice as the other pattern? I'd put (if (wi::multiple_of_p ( ....)) for @1 and @2 outside, then the rest should follow the pattern of the above patterns? Thanks, Richard. > >> + (plus (op @0 @2) { wide_int_to_tree(type, m); })))))) > >> +#endif > >> + > >> (for op (negate abs) > >> /* Simplify cos(-x) and cos(|x|) -> cos(x). Similarly for cosh. */ > >> (for coss (COS COSH) > >> diff --git a/gcc/testsuite/gcc.dg/pr108757-1.c > >> b/gcc/testsuite/gcc.dg/pr108757-1.c > >> new file mode 100644 > >> index 00000000000..7908f4bdcb8 > >> --- /dev/null > >> +++ b/gcc/testsuite/gcc.dg/pr108757-1.c > >> @@ -0,0 +1,18 @@ > >> +/* PR tree-optimization/108757 */ > >> +/* { dg-do compile } */ > >> +/* { dg-options "-O2 -fdump-tree-optimized" } */ > >> + > >> +#include > >> +#define N 5 > >> +#define M 3 > >> +#define GAP 0 > >> +typedef unsigned int UINT; > >> +typedef int INT; > >> +#define UMAX UINT_MAX > >> +#define IMAX INT_MAX > >> +#define IMIN INT_MIN > >> +#include "pr108757.h" > >> + > >> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\+ " > >> "optimized" } } * > >> +/* { dg-final { scan-tree-dump-not " = x_\[0-9\]+\\(D\\) \\- " > >> "optimized" } } */ > >> +/* { dg-final { scan-tree-dump-not " = b_\[0-9\]+ \\+ " "optimized" } } */ > >> diff --git a/gcc/testsuite/gcc.dg/pr108757-2.c > >> b/gcc/testsuite/gcc.dg/pr108757-2.c > >> new file mode 100644 > >> index 00000000000..82bebd09944 > >> --- /dev/null > >> +++ b/gcc/testsuite/gcc.dg/pr108757-2.c > >> @@ -0,0 +1,19 @@ > >> +/* PR tree-optimization/108757 */ > >> +/* { dg-do compile } */ > >> +/* { dg-options "-O2 -fdump-tree-optimized -fwrapv" } */ > >> + > >> +#include > >> +#define N 4 > >> +#define M 3 > >> +#define GAP 2 > >> +typedef unsigned int UINT; > >> +typedef int INT; > >> +#define UMAX UINT_MAX > >> +#define IMAX INT_MAX > >> +#define IMIN INT_MIN > >> +#include "pr108757.h" > >> + > >> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\+ " 16 > >> "optimized" } } */ > >> +/* { dg-final { scan-tree-dump-times " = x_\[0-9\]+\\(D\\) \\- " 3 > >> "optimized" } } */ > >> +/* { dg-final { scan-tree-dump-times " \\+ x_\[0-9\]+\\(D\\)" 3 > >> "optimized" } } */ > >> + > >> diff --git a/gcc/testsuite/gcc.dg/pr108757.h > >> b/gcc/testsuite/gcc.dg/pr108757.h > >> new file mode 100644 > >> index 00000000000..5550199c1ef > >> --- /dev/null > >> +++ b/gcc/testsuite/gcc.dg/pr108757.h > >> @@ -0,0 +1,233 @@ > >> +#define NOINLINE __attribute__ ((noinline)) > >> +UINT NOINLINE > >> +opt_u1 (UINT x) > >> +{ > >> + if (x < (M * N) - GAP) > >> + return 0; > >> + UINT a = x - (M * N); > >> + UINT b = a / N; > >> + return b + M; > >> +} > >> + > >> +UINT NOINLINE > >> +opt_u2 (UINT x) > >> +{ > >> + if (x > (UMAX - (M * N) + GAP)) > >> + return 0; > >> + UINT a = x + (M * N); > >> + UINT b = a / N; > >> + return b - M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s1 (INT x) > >> +{ > >> + if (x < (M * N) - GAP) > >> + return 0; > >> + INT a = x - (M * N); > >> + INT b = a / N; > >> + return b + M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s2 (INT x) > >> +{ > >> + if (x < IMIN + (M * N) - GAP || x > 0) > >> + return 0; > >> + INT a = x - (M * N); > >> + INT b = a / N; > >> + return b + M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s3 (INT x) > >> +{ > >> + if (x < (M * N) - GAP) > >> + return 0; > >> + INT a = x - (M * N); > >> + INT b = a / -N; > >> + return b + -M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s4 (INT x) > >> +{ > >> + if (x < IMIN + (M * N) - GAP || x > 0) > >> + return 0; > >> + INT a = x - (M * N); > >> + INT b = a / -N; > >> + return b + -M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s5 (INT x) > >> +{ > >> + if (x > (-M * N) + GAP) > >> + return 0; > >> + INT a = x - (-M * N); > >> + INT b = a / N; > >> + return b + -M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s6 (INT x) > >> +{ > >> + if (x > IMAX - (M * N) + GAP || x < 0) > >> + return 0; > >> + INT a = x - (-M * N); > >> + INT b = a / N; > >> + return b + -M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s7 (INT x) > >> +{ > >> + if (x > (M * -N) + GAP) > >> + return 0; > >> + INT a = x - (M * -N); > >> + INT b = a / -N; > >> + return b + M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s8 (INT x) > >> +{ > >> + if (x > IMAX - (M * N) + GAP || x < 0) > >> + return 0; > >> + INT a = x - (M * -N); > >> + INT b = a / -N; > >> + return b + M; > >> +} > >> + > >> +UINT NOINLINE > >> +opt_u3 (UINT x) > >> +{ > >> + if (x < (M << N) - GAP) > >> + return 0; > >> + UINT a = x - (M << N); > >> + UINT b = a >> N; > >> + return b + M; > >> +} > >> + > >> +UINT NOINLINE > >> +opt_u4 (UINT x) > >> +{ > >> + if (x > (UMAX - (M << N)) + GAP) > >> + return 0; > >> + UINT a = x + (M << N); > >> + UINT b = a >> N; > >> + return b - M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s9 (INT x) > >> +{ > >> + if (x < (M << N) - GAP) > >> + return 0; > >> + INT a = x - (M << N); > >> + INT b = a >> N; > >> + return b + M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s10 (INT x) > >> +{ > >> + if (x < IMIN + (M << N) - GAP || x > 0) > >> + return 0; > >> + INT a = x - (M << N); > >> + INT b = a >> N; > >> + return b + M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s11 (INT x) > >> +{ > >> + if (x > (-M << N) + GAP) > >> + return 0; > >> + INT a = x - (-M << N); > >> + INT b = a >> N; > >> + return b + -M; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s12 (INT x) > >> +{ > >> + if (x > IMAX - (M << N) + GAP || x < 0) > >> + return 0; > >> + INT a = x - (-M << N); > >> + INT b = a >> N; > >> + return b + -M; > >> +} > >> + > >> +UINT NOINLINE > >> +opt_u5 (UINT x, UINT n, UINT m) > >> +{ > >> + if (n > N || m > M) > >> + return 0; > >> + if (x < (M*N) - GAP) > >> + return 0; > >> + UINT a = x - (m * n); > >> + UINT b = a / n; > >> + return b + m; > >> +} > >> + > >> +UINT NOINLINE > >> +opt_u6 (UINT x, UINT n, UINT m) > >> +{ > >> + if (n > N || m > M) > >> + return 0; > >> + if (x > (UMAX - M*N) + GAP) > >> + return 0; > >> + UINT a = x + (m * n); > >> + UINT b = a / n; > >> + return b - m; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s13 (INT x, INT n, INT m) > >> +{ > >> + if (n > N || m > M || n < 0 || m < 0) > >> + return 0; > >> + if (x < (M*N) - GAP) > >> + return 0; > >> + INT a = x - (m * n); > >> + INT b = a / n; > >> + return b + m; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s14 (INT x, INT n, INT m) > >> +{ > >> + if (n > N || m > M || n < 0 || m < 0) > >> + return 0; > >> + if (x > -M*N + GAP) > >> + return 0; > >> + INT a = x + (m * n); > >> + INT b = a / n; > >> + return b - m; > >> +} > >> + > >> +INT > >> +opt_s15 (INT x, INT n, INT m) > >> +{ > >> + if (n > 0 || m > 0 || n < -N || m < -M) > >> + return 0; > >> + if (x < (M*N) - GAP) > >> + return 0; > >> + INT a = x - (m * n); > >> + INT b = a / n; > >> + return b + m; > >> +} > >> + > >> +INT NOINLINE > >> +opt_s16 (INT x, INT n, INT m) > >> +{ > >> + if (n > 0 || m > 0 || n < -N || m < -M) > >> + return 0; > >> + if (x < 0 || x > (IMAX - M*N) + GAP) > >> + return 0; > >> + INT a = x + (m * n); > >> + INT b = a / n; > >> + return b - m; > >> +} > >> + > -- Richard Biener SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)