From: Eugene Rozenfeld <Eugene.Rozenfeld@microsoft.com>
To: Richard Biener <richard.guenther@gmail.com>
Cc: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>
Subject: RE: [EXTERNAL] Re: [PATCH] [tree-optimization] Fix for PR97223
Date: Thu, 29 Oct 2020 19:45:36 +0000 [thread overview]
Message-ID: <BYAPR21MB1351B8D7019DA0391825850191140@BYAPR21MB1351.namprd21.prod.outlook.com> (raw)
In-Reply-To: <CAFiYyc1ehFNz5i2MYNCdOse0jeEjoiakEqrF4nXGc38VO0cgtQ@mail.gmail.com>
[-- Attachment #1: Type: text/plain, Size: 3284 bytes --]
Thank you for the review Richard!
I re-worked the patch based on your suggestions. I combined the two patterns. Neither one requires a signedness check as long as the type of the 'add' has overflow wrap semantics.
I had to modify the regular expression in no-strict-overflow-4.c test. In that test the following function is compiled with -fno-strict-overflow :
int
foo (int i)
{
return i + 1 > i;
}
We now optimize this function so that the tree-optimized dump has
;; Function foo (foo, funcdef_no=0, decl_uid=1931, cgraph_uid=1, symbol_order=0)
foo (int i)
{
_Bool _1;
int _3;
<bb 2> [local count: 1073741824]:
_1 = i_2(D) != 2147483647;
_3 = (int) _1;
return _3;
}
This is a correct optimization since -fno-strict-overflow implies -fwrapv.
Eugene
-----Original Message-----
From: Richard Biener <richard.guenther@gmail.com>
Sent: Tuesday, October 27, 2020 2:23 AM
To: Eugene Rozenfeld <Eugene.Rozenfeld@microsoft.com>
Cc: gcc-patches@gcc.gnu.org
Subject: [EXTERNAL] Re: [PATCH] [tree-optimization] Fix for PR97223
On Sat, Oct 24, 2020 at 2:20 AM Eugene Rozenfeld via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:
>
> This patch adds a pattern for folding
> x < (short) ((unsigned short)x + const) to
> x <= SHORT_MAX - const
> (and similarly for other integral types) if const is not 0.
> as described in PR97223.
>
> For example, without this patch the x86_64-pc-linux code generated for
> this function
>
> bool f(char x)
> {
> return x < (char)(x + 12);
> }
>
> is
>
> lea eax,[rdi+0xc]
> cmp al,dil
> setg al
> ret
>
> With the patch the code is
>
> cmp dil,0x73
> setle al
> ret
>
> Tested on x86_64-pc-linux.
+/* Similar to the previous pattern but with additional casts. */ (for
+cmp (lt le ge gt)
+ out (gt gt le le)
+ (simplify
+ (cmp:c (convert@3 (plus@2 (convert@4 @0) INTEGER_CST@1)) @0)
+ (if (!TYPE_UNSIGNED (TREE_TYPE (@0))
+ && types_match (TREE_TYPE (@0), TREE_TYPE (@3))
+ && types_match (TREE_TYPE (@4), unsigned_type_for (TREE_TYPE (@0)))
+ && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@4))
+ && wi::to_wide (@1) != 0
+ && single_use (@2))
+ (with { unsigned int prec = TYPE_PRECISION (TREE_TYPE (@0)); }
+ (out @0 { wide_int_to_tree (TREE_TYPE (@0),
+ wi::max_value (prec, SIGNED)
+ - wi::to_wide (@1)); })))))
I think it's reasonable but the comment can be made more precise.
In particular I wonder why we require a signed comparison here while the previous pattern requires an unsigned comparison. It might be an artifact and the restriction instead only applies to the plus?
Note that
+ && types_match (TREE_TYPE (@4), unsigned_type_for (TREE_TYPE
+ (@0)))
unsigned_type_for should be avoided since it's quite expensive. May I suggest
&& TYPE_UNSIGNED (TREE_TYPE (@4))
&& tree_nop_conversion_p (TREE_TYPE (@4), TREE_TYPE (@0))
instead?
I originally wondered if "but with additional casts" could be done in a single pattern via (convert? ...) uses but then I noticed the strange difference in the comparison signedness requirement ...
Richard.
> Eugene
>
[-- Attachment #2: 0001-Add-a-tree-optimization-described-in-PR97223.patch --]
[-- Type: application/octet-stream, Size: 3049 bytes --]
From 973942122522bbf2e9de54cff17de59de5955547 Mon Sep 17 00:00:00 2001
From: Eugene Rozenfeld <erozen@microsoft.com>
Date: Fri, 23 Oct 2020 16:47:01 -0700
Subject: [PATCH] Add a tree optimization described in PR97223.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Convert
x < (short) ((unsigned short)x + const)
to
x <= SHORT_MAX – const
(and similarly for other integral types) if const is not 0.
For example, without this patch the x86_64-pc-linux code generated for this function
bool f(char x)
{
return x < (char)(x + 12);
}
is
lea eax,[rdi+0xc]
cmp al,dil
setg al
ret
With the patch the code is
cmp dil,0x73
setle al
ret
---
gcc/match.pd | 16 ++++++++++------
gcc/testsuite/gcc.dg/no-strict-overflow-4.c | 5 +++--
2 files changed, 13 insertions(+), 8 deletions(-)
diff --git a/gcc/match.pd b/gcc/match.pd
index 17ba04100c7..412e21faf86 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -4940,18 +4940,22 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
/* When one argument is a constant, overflow detection can be simplified.
Currently restricted to single use so as not to interfere too much with
ADD_OVERFLOW detection in tree-ssa-math-opts.c.
- A + CST CMP A -> A CMP' CST' */
+ CONVERT?(CONVERT?(A) + CST) CMP A -> A CMP' CST' */
(for cmp (lt le ge gt)
out (gt gt le le)
(simplify
- (cmp:c (plus@2 @0 INTEGER_CST@1) @0)
- (if (TYPE_UNSIGNED (TREE_TYPE (@0))
- && TYPE_OVERFLOW_WRAPS (TREE_TYPE (@0))
+ (cmp:c (convert?@3 (plus@2 (convert?@4 @0) INTEGER_CST@1)) @0)
+ (if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (@2))
+ && types_match (TREE_TYPE (@0), TREE_TYPE (@3))
+ && tree_nop_conversion_p (TREE_TYPE (@4), TREE_TYPE (@0))
&& wi::to_wide (@1) != 0
&& single_use (@2))
- (with { unsigned int prec = TYPE_PRECISION (TREE_TYPE (@0)); }
+ (with {
+ unsigned int prec = TYPE_PRECISION (TREE_TYPE (@0));
+ signop sign = TYPE_SIGN (TREE_TYPE (@0));
+ }
(out @0 { wide_int_to_tree (TREE_TYPE (@0),
- wi::max_value (prec, UNSIGNED)
+ wi::max_value (prec, sign)
- wi::to_wide (@1)); })))))
/* To detect overflow in unsigned A - B, A < B is simpler than A - B > A.
diff --git a/gcc/testsuite/gcc.dg/no-strict-overflow-4.c b/gcc/testsuite/gcc.dg/no-strict-overflow-4.c
index b6d3da3f831..90145ff9422 100644
--- a/gcc/testsuite/gcc.dg/no-strict-overflow-4.c
+++ b/gcc/testsuite/gcc.dg/no-strict-overflow-4.c
@@ -4,7 +4,8 @@
/* Source: Ian Lance Taylor. Dual of strict-overflow-4.c. */
/* We can only simplify the conditional when using strict overflow
- semantics. */
+ semantics or when using wrap overflow semantics. -fno-strict-overflow is
+ equivalent to -fwrapv. */
int
foo (int i)
@@ -12,4 +13,4 @@ foo (int i)
return i + 1 > i;
}
-/* { dg-final { scan-tree-dump "\[^ \]*_.(\\\(D\\\))? (>|<) \[^ \]*_." "optimized" } } */
+/* { dg-final { scan-tree-dump "\[^ \]*_.(\\\(D\\\))? != \[0-9]+" "optimized" } } */
--
2.17.1
next prev parent reply other threads:[~2020-10-29 19:45 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-10-24 0:19 Eugene Rozenfeld
2020-10-27 9:23 ` Richard Biener
2020-10-29 19:45 ` Eugene Rozenfeld [this message]
2020-10-30 8:24 ` [EXTERNAL] " Richard Biener
2020-11-06 3:46 ` Jeff Law
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=BYAPR21MB1351B8D7019DA0391825850191140@BYAPR21MB1351.namprd21.prod.outlook.com \
--to=eugene.rozenfeld@microsoft.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=richard.guenther@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).