From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lj1-x22a.google.com (mail-lj1-x22a.google.com [IPv6:2a00:1450:4864:20::22a]) by sourceware.org (Postfix) with ESMTPS id 9DEE23858D20; Tue, 5 Mar 2024 15:58:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9DEE23858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 9DEE23858D20 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::22a ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1709654334; cv=none; b=Y8nbMYzN9AoyVBU0chYVjZJs6qAYTP95cWu5e7spRtX0XcOywekX2V7dzb0lTlcQQkTGpcH1sxkdGZHlf9ICmojEWShiYoChwEgSjXpLiA+tPs8yGndC3xQQXtFc8XzR+WMvuDtE5GNBq6oPmSaUXkpaUa6JZyGGM7Pxhvuuie4= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1709654334; c=relaxed/simple; bh=btJrpvdZKEgJrSYFf+isKe1NTvKrykeR4mHuyi2ixA4=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=dpRED+se4VoBsNkFF77Wf+Lt/qHqpaMri4jl9HWdZrxSriUgbl4wbZQH2kfVf1KIUvMqjhOJq1CNxJquMglsQf0fvFAS9AJpz0rdJJXJSuiFTc5yqhUJjGuczhHUhiQinPvqKHTiIxFwvvqne0pIXBTsirjmldNkhbAq3aNlOIM= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-lj1-x22a.google.com with SMTP id 38308e7fff4ca-2d382a78c38so37265321fa.1; Tue, 05 Mar 2024 07:58:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1709654329; x=1710259129; darn=gcc.gnu.org; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=OCoRzis69PIAr3qnkPgo/HBsuCW3IOeUC8yod8tpmOI=; b=AmvdXa6msrwno8nXUVCG+mhJwtwN2MVhHc6/eywHtn+EKaX7iTe0t0CbkgnfYsP0LI B2cPVJ3nSc3G0v2neNl8jzZyTNz9vCHcNjVqzPrVxMRY5detJqhnyRIsEplPnSv1Wbu5 PpsM2qREUN7CLderwS3qclc8nstb3MnyD0v0oE4Y6FEpAKz6YPtZeWMTkO+4xMw9e0QD IYj+yUEdaDLZ9rWw8FB9z2mO2cAW0y8ZBEkCGlpd9wDoJM5aM5Ecfx/zjQxhydEJzPXn xnU3aHQIwm088QcJrksNH0Iqt4IH5fYK5s6Qfw22X9wrsIOiKtkwMcUgalg6cY6f7gg/ Aagw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709654329; x=1710259129; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=OCoRzis69PIAr3qnkPgo/HBsuCW3IOeUC8yod8tpmOI=; b=p6pA3NATAnJW9POCD3aJ76I6azj410hxLuy+i5cqmBfEmwqnNQdi0pxpZtCPQ18ukA 4WWixd2y1V00oc1IPK36Gzos973qgVrXnL73jVoZi1x8MBKnKzk7CLjHutrhsBVPtoTp 4kjmjXgyVOVtTBRLDDi0xm9bl5EHvJSV+8RADjfWtAW1jttvSvbxn+bsZyNX7g1sfthv K/U/ga0zDOx3mdMc8ZYGGFl0nuNtllgvKzFUzTlRD01Svtu13PTa0tG/hu4TqFgjePHM yOpcOM2n6I5SY4XnXF5o5MexPiEMWywVKvG7eyex7kxxg6EOO53KSlN2tI6Wh/RgBN93 +L1w== X-Forwarded-Encrypted: i=1; AJvYcCX/8r1NS8s6EAPgWqbOJ8oBEC7+68J89jlB8Fnz/Zj2DZSv9v6kR6SDlvBghC7/A/XEfu9yKXfn1Cnh78oJjTnDKHFD6LxP1g== X-Gm-Message-State: AOJu0YzudOTMiAIznKrheAUGjAEynFwlVUqfjMsqSFzn2dKUuY1DtVP6 U1Oeir40ts6fEMSeeiYsODg2fPEEJWYhduml/cdO45voCvQp2LTJFiRB4ul/9gRhxmI1jMoRDAR 8oexhkP4f760JH3LU7h6jCuwDfsMebfUhJQo= X-Google-Smtp-Source: AGHT+IEVjETJ2vUcScorSb5CcWzAwWPHy5RTtpSEKzETAVXF+PUrN2a8t7QtF4URq6jsZ4VWTaE24vCYqCxXjkDWtnI= X-Received: by 2002:a2e:8043:0:b0:2d3:2ecf:c26a with SMTP id p3-20020a2e8043000000b002d32ecfc26amr1485992ljg.13.1709654328240; Tue, 05 Mar 2024 07:58:48 -0800 (PST) MIME-Version: 1.0 References: <20240304203830.3740968-1-kmatsui@gcc.gnu.org> In-Reply-To: From: Richard Biener Date: Tue, 5 Mar 2024 16:58:36 +0100 Message-ID: Subject: Re: [PATCH] middle-end/113680 - Optimize (x - y) CMP 0 as x CMP y To: Ken Matsui Cc: Ken Matsui , gcc-patches@gcc.gnu.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-7.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE 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 Tue, Mar 5, 2024 at 1:51=E2=80=AFPM Ken Matsui wrote: > > On Tue, Mar 5, 2024 at 12:38=E2=80=AFAM Richard Biener > wrote: > > > > On Mon, Mar 4, 2024 at 9:40=E2=80=AFPM Ken Matsui = wrote: > > > > > > (x - y) CMP 0 is equivalent to x CMP y where x and y are signed > > > integers and CMP is <, <=3D, >, or >=3D. Similarly, 0 CMP (x - y) is > > > equivalent to y CMP x. As reported in PR middle-end/113680, this > > > equivalence does not hold for types other than signed integers. When > > > it comes to conditions, the former was translated to a combination of > > > sub and test, whereas the latter was translated to a single cmp. > > > Thus, this optimization pass tries to optimize the former to the > > > latter. > > > > > > When `-fwrapv` is enabled, GCC treats the overflow of signed integers > > > as defined behavior, specifically, wrapping around according to two's > > > complement arithmetic. This has implications for optimizations that > > > rely on the standard behavior of signed integers, where overflow is > > > undefined. Consider the example given: > > > > > > long long llmax =3D __LONG_LONG_MAX__; > > > long long llmin =3D -llmax - 1; > > > > > > Here, `llmax - llmin` effectively becomes `llmax - (-llmax - 1)`, whi= ch > > > simplifies to `2 * llmax + 1`. Given that `llmax` is the maximum val= ue > > > for a `long long`, this calculation overflows in a defined manner > > > (wrapping around), which under `-fwrapv` is a legal operation that > > > produces a negative value due to two's complement wraparound. > > > Therefore, `llmax - llmin < 0` is true. > > > > > > However, the direct comparison `llmax < llmin` is false since `llmax` > > > is the maximum possible value and `llmin` is the minimum. Hence, > > > optimizations that rely on the equivalence of `(x - y) CMP 0` to > > > `x CMP y` (and vice versa) cannot be safely applied when `-fwrapv` is > > > enabled. This is why this optimization pass is disabled under > > > `-fwrapv`. > > > > > > This optimization pass must run before the Jump Threading pass and th= e > > > VRP pass, as it may modify conditions. For example, in the VRP pass: > > > > > > (1) > > > int diff =3D x - y; > > > if (diff > 0) > > > foo(); > > > if (diff < 0) > > > bar(); > > > > > > The second condition would be converted to diff !=3D 0 in the VRP pas= s > > > because we know the postcondition of the first condition is diff <=3D= 0, > > > and then diff !=3D 0 is cheaper than diff < 0. If we apply this pass > > > after this VRP, we get: > > > > > > (2) > > > int diff =3D x - y; > > > if (x > y) > > > foo(); > > > if (diff !=3D 0) > > > bar(); > > > > > > This generates sub and test for the second condition and cmp for the > > > first condition. However, if we apply this pass beforehand, we simply > > > get: > > > > > > (3) > > > int diff =3D x - y; > > > if (x > y) > > > foo(); > > > if (x < y) > > > bar(); > > > > > > In this code, diff will be eliminated as a dead code, and sub and tes= t > > > will not be generated, which is more efficient. > > > > > > For the Jump Threading pass, without this optimization pass, (1) and > > > (3) above are recognized as different, which prevents TCO. > > > > > > PR middle-end/113680 > > > > This shouldn't be done as a new optimization pass. It fits either > > the explicit code present in the forwprop pass or a new match.pd > > pattern. There's possible interaction with x - y value being used > > elsewhere and thus exposing a CSE opportunity as well as > > a comparison against zero being possibly implemented by > > a flag setting subtraction instruction. > > > > Thank you so much for your review! Although the forwprop pass runs > multiple times, we might not need to apply this optimization multiple > times. Would it be acceptable to add such optimization? More > generally, I would like to know how to determine where to put > optimization in the future. This kind of pattern matching expression simplification is best addressed by patterns in match.pd though historically the forwprop pass still catches cases not in match.pd in its forward_propagate_into_comparison_1 (and callers). > FYI, I read this page: https://gcc.gnu.org/wiki/OptimizationCourse > > > Our VN pass has some tricks to anticipate CSE opportunities > > like this, but it's not done "properly" in the way of anticipating > > both forms during PRE. > > > > I'll note we have > > > > /* (A - B) !=3D 0 ? (A - B) : (B - A) same as (A - B) */ > > (for cmp (ne ltgt) > > > > and similar which might be confused by canonicalizing to A !=3D B. > > I will investigate and update my patch (after my final exam ends...)! > > > I'm also surprised we don't already have the pattern you add. > > Hmm, so am I. It looks like we do it for equality compares which can also handle types where overflow is undefined. -fdump-tree-all-folding shows in the 005t.original dump we simplify a - b !=3D 0 via match.pd:6105: /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. ??? The transformation is valid for the other operators if overflow is undefined for the type, but performing it here badly interacts with the transformation in fold_cond_expr_with_comparison which attempts to synthetize ABS_EXPR. */ (for cmp (eq ne) (for sub (minus pointer_diff) (simplify (cmp (sub@2 @0 @1) integer_zerop) (if (single_use (@2)) (cmp @0 @1))))) and the comment explains why we don't perform the transform it the way you intend. That comment might no longer apply but I would guess there's testsuite fallout when you amend this pattern. Richard. > I saw that this optimization sometimes messes up VRP > while sometimes helping it (as I described in my comment). I also > need to research this. > > > > > Richard. > > > > > gcc/ChangeLog: > > > > > > * Makefile.in: Add tree-ssa-cmp.o to OBJS. > > > * common.opt: Define ftree-cmp > > > * doc/invoke.texi: Document ftree-cmp. > > > * opts.cc (default_options_table): Handle OPT_ftree_cmp. > > > * passes.def (pass_cmp): New optimization pass. > > > * timevar.def (TV_TREE_CMP): New variable for timing. > > > * tree-pass.h (make_pass_cmp): New declaration. > > > * tree-ssa-cmp.cc: New file. > > > > > > gcc/testsuite/ChangeLog: > > > > > > * gcc.dg/pr113680.c: New test. > > > > > > Signed-off-by: Ken Matsui > > > --- > > > gcc/Makefile.in | 1 + > > > gcc/common.opt | 4 + > > > gcc/doc/invoke.texi | 11 +- > > > gcc/opts.cc | 1 + > > > gcc/passes.def | 3 + > > > gcc/testsuite/gcc.dg/pr113680.c | 47 ++++++ > > > gcc/timevar.def | 1 + > > > gcc/tree-pass.h | 1 + > > > gcc/tree-ssa-cmp.cc | 262 ++++++++++++++++++++++++++++++= ++ > > > 9 files changed, 330 insertions(+), 1 deletion(-) > > > create mode 100644 gcc/testsuite/gcc.dg/pr113680.c > > > create mode 100644 gcc/tree-ssa-cmp.cc > > > > > > diff --git a/gcc/Makefile.in b/gcc/Makefile.in > > > index a74761b7ab3..935b80b6947 100644 > > > --- a/gcc/Makefile.in > > > +++ b/gcc/Makefile.in > > > @@ -1731,6 +1731,7 @@ OBJS =3D \ > > > tree-ssa-address.o \ > > > tree-ssa-alias.o \ > > > tree-ssa-ccp.o \ > > > + tree-ssa-cmp.o \ > > > tree-ssa-coalesce.o \ > > > tree-ssa-copy.o \ > > > tree-ssa-dce.o \ > > > diff --git a/gcc/common.opt b/gcc/common.opt > > > index 51c4a17da83..7c853224458 100644 > > > --- a/gcc/common.opt > > > +++ b/gcc/common.opt > > > @@ -3053,6 +3053,10 @@ ftree-ch > > > Common Var(flag_tree_ch) Optimization > > > Enable loop header copying on trees. > > > > > > +ftree-cmp > > > +Common Var(flag_tree_cmp) Optimization > > > +Enable SSA comparison optimization on trees. > > > + > > > ftree-coalesce-inlined-vars > > > Common Ignore RejectNegative > > > Does nothing. Preserved for backward compatibility. > > > diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi > > > index bdf05be387d..04762d490a3 100644 > > > --- a/gcc/doc/invoke.texi > > > +++ b/gcc/doc/invoke.texi > > > @@ -619,7 +619,7 @@ Objective-C and Objective-C++ Dialects}. > > > -fsplit-wide-types -fsplit-wide-types-early -fssa-backprop -fssa-= phiopt > > > -fstdarg-opt -fstore-merging -fstrict-aliasing -fipa-strict-aliasi= ng > > > -fthread-jumps -ftracer -ftree-bit-ccp > > > --ftree-builtin-call-dce -ftree-ccp -ftree-ch > > > +-ftree-builtin-call-dce -ftree-ccp -ftree-ch -ftree-cmp > > > -ftree-coalesce-vars -ftree-copy-prop -ftree-dce -ftree-dominator= -opts > > > -ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting > > > -ftree-loop-if-convert -ftree-loop-im > > > @@ -12377,6 +12377,7 @@ compilation time. > > > -ftree-bit-ccp > > > -ftree-ccp > > > -ftree-ch > > > +-ftree-cmp > > > -ftree-coalesce-vars > > > -ftree-copy-prop > > > -ftree-dce > > > @@ -13707,6 +13708,14 @@ effectiveness of code motion optimizations. = It also saves one jump. This flag > > > is enabled by default at @option{-O1} and higher. It is not enabled > > > for @option{-Os}, since it usually increases code size. > > > > > > +@opindex ftree-cmp > > > +@item -ftree-cmp > > > +Perform comparison optimization on trees. This decreases unnecessar= y > > > +instructions for comparisons. This flag is enabled by default at > > > +@option{-O1} and higher. This optimization is automatically disable= d when > > > +@option{-fwrapv} is specified to ensure correct behavior under signe= d integer > > > +overflow wrapping. > > > + > > > @opindex ftree-loop-optimize > > > @item -ftree-loop-optimize > > > Perform loop optimizations on trees. This flag is enabled by defaul= t > > > diff --git a/gcc/opts.cc b/gcc/opts.cc > > > index 3333600e0ea..9ee64a48313 100644 > > > --- a/gcc/opts.cc > > > +++ b/gcc/opts.cc > > > @@ -589,6 +589,7 @@ static const struct default_options default_optio= ns_table[] =3D > > > { OPT_LEVELS_1_PLUS, OPT_ftree_builtin_call_dce, NULL, 1 }, > > > { OPT_LEVELS_1_PLUS, OPT_ftree_ccp, NULL, 1 }, > > > { OPT_LEVELS_1_PLUS, OPT_ftree_ch, NULL, 1 }, > > > + { OPT_LEVELS_1_PLUS, OPT_ftree_cmp, NULL, 1 }, > > > { OPT_LEVELS_1_PLUS, OPT_ftree_coalesce_vars, NULL, 1 }, > > > { OPT_LEVELS_1_PLUS, OPT_ftree_copy_prop, NULL, 1 }, > > > { OPT_LEVELS_1_PLUS, OPT_ftree_dce, NULL, 1 }, > > > diff --git a/gcc/passes.def b/gcc/passes.def > > > index 1cbbd413097..e28a2d3c309 100644 > > > --- a/gcc/passes.def > > > +++ b/gcc/passes.def > > > @@ -84,6 +84,9 @@ along with GCC; see the file COPYING3. If not see > > > /* After CCP we rewrite no longer addressed locals into SSA > > > form if possible. */ > > > NEXT_PASS (pass_forwprop); > > > + /* Do cmp before early_thread_jumps and vrp since it may > > > + modify conditions. */ > > > + NEXT_PASS (pass_cmp); > > > NEXT_PASS (pass_early_thread_jumps, /*first=3D*/true); > > > NEXT_PASS (pass_sra_early); > > > /* pass_build_ealias is a dummy pass that ensures that we > > > diff --git a/gcc/testsuite/gcc.dg/pr113680.c b/gcc/testsuite/gcc.dg/p= r113680.c > > > new file mode 100644 > > > index 00000000000..59cd865aa21 > > > --- /dev/null > > > +++ b/gcc/testsuite/gcc.dg/pr113680.c > > > @@ -0,0 +1,47 @@ > > > +/* { dg-do compile } */ > > > +/* { dg-options "-Os -fdump-tree-optimized" } */ > > > + > > > +volatile int i =3D 0; > > > + > > > +void foo() { i =3D 1; } > > > +void bar() { i =3D 2; } > > > + > > > +void f1(int x, int y) > > > +{ > > > + int diff =3D x - y; > > > + if (diff > 0) > > > + foo(); > > > + if (diff < 0) > > > + bar(); > > > +} > > > + > > > +void f2(int x, int y) > > > +{ > > > + if ((x - y) > 0) > > > + foo(); > > > + if ((x - y) < 0) > > > + bar(); > > > +} > > > + > > > +void f3(int x, int y) > > > +{ > > > + if (x > y) > > > + foo(); > > > + if (x < y) > > > + bar(); > > > +} > > > + > > > +void f4(int x, int y) > > > +{ > > > + int diff =3D x - y; > > > + if (diff > 0) > > > + foo(); > > > + if (x < y) > > > + bar(); > > > +} > > > + > > > +/* { dg-final { scan-tree-dump-not " - " "optimized" } } */ > > > +/* { dg-final { scan-assembler-times "cmp" 1 { target { i?86-*-* x86= _64-*-* } } } } */ > > > +/* { dg-final { scan-assembler-times "jmp\[ \t\]+f1" 3 { target { i?= 86-*-* x86_64-*-* } } } } */ > > > +/* { dg-final { scan-assembler-not "sub" { target { i?86-*-* x86_64-= *-* } } } } */ > > > +/* { dg-final { scan-assembler-not "test" { target { i?86-*-* x86_64= -*-* } } } } */ > > > diff --git a/gcc/timevar.def b/gcc/timevar.def > > > index 8e2168e0817..468266d0c56 100644 > > > --- a/gcc/timevar.def > > > +++ b/gcc/timevar.def > > > @@ -157,6 +157,7 @@ DEFTIMEVAR (TV_TREE_EH , "tree = eh") > > > DEFTIMEVAR (TV_TREE_CFG , "tree CFG construction= ") > > > DEFTIMEVAR (TV_TREE_CLEANUP_CFG , "tree CFG cleanup") > > > DEFTIMEVAR (TV_TREE_TAIL_MERGE , "tree tail merge") > > > +DEFTIMEVAR (TV_TREE_CMP , "tree cmp") > > > DEFTIMEVAR (TV_TREE_VRP , "tree VRP") > > > DEFTIMEVAR (TV_TREE_VRP_THREADER , "tree VRP threader") > > > DEFTIMEVAR (TV_TREE_EARLY_VRP , "tree Early VRP") > > > diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h > > > index 29267589eeb..71789a279c0 100644 > > > --- a/gcc/tree-pass.h > > > +++ b/gcc/tree-pass.h > > > @@ -401,6 +401,7 @@ extern gimple_opt_pass *make_pass_ch (gcc::contex= t *ctxt); > > > extern gimple_opt_pass *make_pass_ch_vect (gcc::context *ctxt); > > > extern gimple_opt_pass *make_pass_sccopy (gcc::context *ctxt); > > > extern gimple_opt_pass *make_pass_ccp (gcc::context *ctxt); > > > +extern gimple_opt_pass *make_pass_cmp (gcc::context *ctxt); > > > extern gimple_opt_pass *make_pass_split_paths (gcc::context *ctxt); > > > extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctxt); > > > extern gimple_opt_pass *make_pass_build_alias (gcc::context *ctxt); > > > diff --git a/gcc/tree-ssa-cmp.cc b/gcc/tree-ssa-cmp.cc > > > new file mode 100644 > > > index 00000000000..41d4a58a5b5 > > > --- /dev/null > > > +++ b/gcc/tree-ssa-cmp.cc > > > @@ -0,0 +1,262 @@ > > > +/* Global, SSA-based optimizations using comparison identities. > > > + Copyright (C) 2024 Free Software Foundation, Inc. > > > + > > > +This file is part of GCC. > > > + > > > +GCC is free software; you can redistribute it and/or modify it > > > +under the terms of the GNU General Public License as published by th= e > > > +Free Software Foundation; either version 3, or (at your option) any > > > +later version. > > > + > > > +GCC is distributed in the hope that it will be useful, but WITHOUT > > > +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY o= r > > > +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public Licens= e > > > +for more details. > > > + > > > +You should have received a copy of the GNU General Public License > > > +along with GCC; see the file COPYING3. If not see > > > +. */ > > > + > > > +/* (x - y) CMP 0 is equivalent to x CMP y where x and y are signed i= ntegers and > > > + CMP is <, <=3D, >, or >=3D. Similarly, 0 CMP (x - y) is equivale= nt to y CMP x. > > > + As reported in PR middle-end/113680, this equivalence does not ho= ld for > > > + types other than signed integers. When it comes to conditions, t= he former > > > + was translated to a combination of sub and test, whereas the latt= er was > > > + translated to a single cmp. Thus, this optimization pass tries t= o optimize > > > + the former to the latter. > > > + > > > + When `-fwrapv` is enabled, GCC treats the overflow of signed inte= gers as > > > + defined behavior, specifically, wrapping around according to two'= s > > > + complement arithmetic. This has implications for optimizations t= hat > > > + rely on the standard behavior of signed integers, where overflow = is > > > + undefined. Consider the example given: > > > + > > > + long long llmax =3D __LONG_LONG_MAX__; > > > + long long llmin =3D -llmax - 1; > > > + > > > + Here, `llmax - llmin` effectively becomes `llmax - (-llmax - 1)`,= which > > > + simplifies to `2 * llmax + 1`. Given that `llmax` is the maximum= value for > > > + a `long long`, this calculation overflows in a defined manner > > > + (wrapping around), which under `-fwrapv` is a legal operation tha= t produces > > > + a negative value due to two's complement wraparound. Therefore, > > > + `llmax - llmin < 0` is true. > > > + > > > + However, the direct comparison `llmax < llmin` is false since `ll= max` is the > > > + maximum possible value and `llmin` is the minimum. Hence, optimi= zations > > > + that rely on the equivalence of `(x - y) CMP 0` to `x CMP y` (and= vice versa) > > > + cannot be safely applied when `-fwrapv` is enabled. This is why = this > > > + optimization pass is disabled under `-fwrapv`. > > > + > > > + This optimization pass must run before the Jump Threading pass an= d > > > + the VRP pass, as it may modify conditions. For example, in the VR= P pass: > > > + > > > + (1) > > > + int diff =3D x - y; > > > + if (diff > 0) > > > + foo(); > > > + if (diff < 0) > > > + bar(); > > > + > > > + The second condition would be converted to diff !=3D 0 in the VRP= pass because > > > + we know the postcondition of the first condition is diff <=3D 0, = and then > > > + diff !=3D 0 is cheaper than diff < 0. If we apply this pass after= this VRP, > > > + we get: > > > + > > > + (2) > > > + int diff =3D x - y; > > > + if (x > y) > > > + foo(); > > > + if (diff !=3D 0) > > > + bar(); > > > + > > > + This generates sub and test for the second condition and cmp for = the first > > > + condition. However, if we apply this pass beforehand, we simply g= et: > > > + > > > + (3) > > > + int diff =3D x - y; > > > + if (x > y) > > > + foo(); > > > + if (x < y) > > > + bar(); > > > + > > > + In this code, diff will be eliminated as a dead code, and sub and= test will > > > + not be generated, which is more efficient. > > > + > > > + For the Jump Threading pass, without this optimization pass, (1) = and (3) > > > + above are recognized as different, which prevents TCO. */ > > > + > > > +#include "config.h" > > > +#include "system.h" > > > +#include "coretypes.h" > > > +#include "backend.h" > > > +#include "tree.h" > > > +#include "gimple.h" > > > +#include "tree-pass.h" > > > +#include "ssa.h" > > > +#include "gimple-iterator.h" > > > +#include "domwalk.h" > > > + > > > +/* True if VAR is a signed integer, false otherwise. */ > > > + > > > +static bool > > > +is_signed_integer(const_tree var) > > > +{ > > > + return (TREE_CODE (TREE_TYPE (var)) =3D=3D INTEGER_TYPE > > > + && !TYPE_UNSIGNED (TREE_TYPE (var))); > > > +} > > > + > > > +/* If EXPR is an integer zero, return it. If EXPR is SSA_NAME, and = its > > > + defining statement is a subtraction of two signed integers, retur= n the > > > + MINUS_EXPR. Otherwise, return NULL_TREE. */ > > > + > > > +static const_tree > > > +prop_integer_zero_or_minus_expr (const_tree expr) > > > +{ > > > + if (integer_zerop (expr)) > > > + return expr; > > > + > > > + if (TREE_CODE (expr) !=3D SSA_NAME) > > > + return NULL_TREE; > > > + > > > + gimple *defining_stmt =3D SSA_NAME_DEF_STMT (expr); > > > + if (!is_gimple_assign (defining_stmt) > > > + || gimple_assign_rhs_code (defining_stmt) !=3D MINUS_EXPR) > > > + return NULL_TREE; > > > + > > > + tree rhs1 =3D gimple_assign_rhs1 (defining_stmt); > > > + if (!is_signed_integer (rhs1)) > > > + return NULL_TREE; > > > + > > > + tree rhs2 =3D gimple_assign_rhs2 (defining_stmt); > > > + if (!is_signed_integer (rhs2)) > > > + return NULL_TREE; > > > + > > > + return build2 (MINUS_EXPR, TREE_TYPE (expr), rhs1, rhs2); > > > +} > > > + > > > +/* Optimize: > > > + > > > + 1. (x - y) CMP 0 > > > + 2. 0 CMP (x - y) > > > + > > > + to: > > > + > > > + 1. x CMP y > > > + 2. y CMP x > > > + > > > + where CMP is either <, <=3D, >, or >=3D. */ > > > + > > > +static void > > > +optimize_signed_comparison (gcond *stmt) > > > +{ > > > + const enum tree_code code =3D gimple_cond_code (stmt); > > > + if (code < LT_EXPR || GE_EXPR < code) > > > + return; > > > + > > > + const_tree lhs =3D prop_integer_zero_or_minus_expr (gimple_cond_lh= s (stmt)); > > > + if (lhs =3D=3D NULL_TREE) > > > + return; > > > + > > > + const_tree rhs =3D prop_integer_zero_or_minus_expr (gimple_cond_rh= s (stmt)); > > > + if (rhs =3D=3D NULL_TREE) > > > + return; > > > + > > > + if (TREE_CODE (lhs) =3D=3D MINUS_EXPR && integer_zerop (rhs)) > > > + { > > > + /* Case 1: (x - y) CMP 0 */ > > > + tree x =3D TREE_OPERAND (lhs, 0); > > > + tree y =3D TREE_OPERAND (lhs, 1); > > > + > > > + /* =3D> x CMP y */ > > > + gimple_cond_set_lhs (stmt, x); > > > + gimple_cond_set_rhs (stmt, y); > > > + update_stmt (stmt); > > > + } > > > + else if (integer_zerop (lhs) && TREE_CODE (rhs) =3D=3D MINUS_EXPR) > > > + { > > > + /* Case 2: 0 CMP (x - y) */ > > > + tree x =3D TREE_OPERAND (rhs, 0); > > > + tree y =3D TREE_OPERAND (rhs, 1); > > > + > > > + /* =3D> y CMP x */ > > > + gimple_cond_set_lhs (stmt, y); > > > + gimple_cond_set_rhs (stmt, x); > > > + update_stmt (stmt); > > > + } > > > +} > > > + > > > +/* Find signed integer comparisons where the operands are MINUS_EXPR= and > > > + 0, and replace them with the equivalent comparison of the operand= s of > > > + the MINUS_EXPR without the subtraction. */ > > > + > > > +namespace { > > > + > > > +const pass_data pass_data_cmp =3D > > > +{ > > > + GIMPLE_PASS, /* type */ > > > + "cmp", /* name */ > > > + OPTGROUP_NONE, /* optinfo_flags */ > > > + TV_TREE_CMP, /* tv_id */ > > > + PROP_ssa, /* properties_required */ > > > + 0, /* properties_provided */ > > > + 0, /* properties_destroyed */ > > > + 0, /* todo_flags_start */ > > > + TODO_remove_unused_locals, /* todo_flags_finish */ > > > +}; > > > + > > > +class pass_cmp : public gimple_opt_pass > > > +{ > > > +public: > > > + pass_cmp (gcc::context *ctxt) > > > + : gimple_opt_pass (pass_data_cmp, ctxt) > > > + {} > > > + > > > + /* opt_pass methods: */ > > > + bool gate (function *) final override > > > + { > > > + /* If -fwrapv is enabled, this pass cannot be safely applied a= s described > > > + in the comment at the top of this file. */ > > > + return flag_tree_cmp !=3D 0 && flag_wrapv =3D=3D 0; > > > + } > > > + > > > + unsigned int execute (function *) final override; > > > + > > > +}; // class pass_cmp > > > + > > > +class cmp_dom_walker : public dom_walker > > > +{ > > > +public: > > > + cmp_dom_walker () : dom_walker (CDI_DOMINATORS) {} > > > + > > > + void after_dom_children (basic_block) final override; > > > +}; > > > + > > > +void > > > +cmp_dom_walker::after_dom_children (basic_block bb) > > > +{ > > > + gimple_stmt_iterator gsi; > > > + > > > + for (gsi =3D gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&g= si)) > > > + { > > > + gimple *stmt =3D gsi_stmt (gsi); > > > + if (gimple_code (stmt) =3D=3D GIMPLE_COND) > > > + optimize_signed_comparison (as_a (stmt)); > > > + } > > > +} > > > + > > > + > > > +unsigned int > > > +pass_cmp::execute (function *) > > > +{ > > > + calculate_dominance_info (CDI_DOMINATORS); > > > + cmp_dom_walker ().walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); > > > + return 0; > > > +} > > > + > > > +} // anon namespace > > > + > > > +gimple_opt_pass * > > > +make_pass_cmp (gcc::context *ctxt) > > > +{ > > > + return new pass_cmp (ctxt); > > > +} > > > -- > > > 2.44.0 > > >