From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-vk1-xa2a.google.com (mail-vk1-xa2a.google.com [IPv6:2607:f8b0:4864:20::a2a]) by sourceware.org (Postfix) with ESMTPS id 67A213858D33 for ; Fri, 8 Mar 2024 17:50:05 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 67A213858D33 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=cs.washington.edu Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=cs.washington.edu ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 67A213858D33 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::a2a ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1709920209; cv=none; b=ZnCpEE60xM7FdZzFc0tcy6vJWt6Gk0ITBfbPvSowQTkYlWPF+MPUcWIxk3l5xytHOUalP1cMk78/532TTPzQ1AudPYZoW3t02pNE2WLxHyw7QPP8Yk0uFUpjx4kSt0hDVyeT0CQf9cr+9Gv6U0I7Fpke82jg9LSdrh+fhcSC6Yk= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1709920209; c=relaxed/simple; bh=nDNf3O0gbxjIceWyvgoifN4uVeOpODiIE95a7dtxHIg=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=OcnCoF9Naty4xzY1sKTY02suzjrwA1sjiPt6+xhPTaBAye8M/6t5RjSmAohkwOSzcigq5xEBpbyh9GVgBvsGrxQVruQt2BrSlZzWAVl0IXD3DsKQm6uq22FQEofFwpkJqXISRSSupM5bgTFPxaclCMLV1EDcdpL5mgQHQDkMD/c= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-vk1-xa2a.google.com with SMTP id 71dfb90a1353d-4d33e0c1b3eso349701e0c.2 for ; Fri, 08 Mar 2024 09:50:05 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.washington.edu; s=goo201206; t=1709920205; x=1710525005; 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=gQn0pc2YdDzMKk6p5/VsXxB5mrbhYytuZk0nIqeTsUM=; b=EJx1+vTU7Vk2VFUxophMNSup1Jpsi6tUZKNq5UJB8ZgmdwFBptzxHXqsPG07XoK4Ge cJsutPuiwbwfzy9K3u8mfHG829yQi03ZcLgcMigvZYXFIHKtRgwANRDf9uIg9tGROH0L a+YTFb8vTP9UBJGt7hzRVQ5kvBG4F4oWQ7U2I= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709920205; x=1710525005; 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=gQn0pc2YdDzMKk6p5/VsXxB5mrbhYytuZk0nIqeTsUM=; b=mgtU8X545r4sfFBXdulJoPOuEdibgB3yX6kLvv993+0HLPB5QrDBBPBlnTBm6T73ni TorB8HG6qFXkzDoXDgf4CbAVmt5eJjFBva3FboZtM9Eo0chEcKHSUQ0ztzlnhHdIe0vz sA486Hz83objn3ChpiNFJk2RCD3ONAJoyirMe+fT0jPUd43gajVTwzbjChAva9/E4CuB h1fpp1DlyE+UUWuYrwRsjJaqe7CalkVIeQbH6fop7cJoAfYI3nY3jQdJ6t6T08cqNtYp F60Y5d+KRgSZ19wfXHX25NfFjQiW0aUwKZbK/5vOGgvkD1X388Ye2G+dl0ntm06vlOW1 T0dw== X-Forwarded-Encrypted: i=1; AJvYcCXXQ6TFmw0VMuE2KwHz8nYIJ4eaTMy6/rbXFN2dJ64NSO8ep6nFi3iItO5MxCNWUMnnACBW82XMZ9ZskHnHM7PXkoUv1CpWiw== X-Gm-Message-State: AOJu0YyDsS31g7s/C7vi4860CrSGY0yMd6FJ621hT9lW5sl5lqXjhFyf ZHNlcSMyRfJ0ZRpIefaq75+jwaXMCwhMChFq8LnzV3FcUcf8zPYt0X07oWa/aYf1z8r5Bm4mCMO S3rKTUcw5R4E8AHTNXcBvUz1wphoMri9b4S3y X-Google-Smtp-Source: AGHT+IEhzTwIwvLJDqcSv+J5TPVOzv/mlsLxd2E8y/TeopkSVwPWswg6GRlN1/sjCZsqF+A1+OPOiR3Zoij8CM4Cenw= X-Received: by 2002:a05:6122:16a8:b0:4d3:d135:b028 with SMTP id 40-20020a05612216a800b004d3d135b028mr1599824vkl.11.1709920204454; Fri, 08 Mar 2024 09:50:04 -0800 (PST) MIME-Version: 1.0 References: <20240304203830.3740968-1-kmatsui@gcc.gnu.org> In-Reply-To: From: Ken Matsui Date: Fri, 8 Mar 2024 09:49:28 -0800 Message-ID: Subject: Re: [PATCH] middle-end/113680 - Optimize (x - y) CMP 0 as x CMP y To: Richard Biener 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=-10.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,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 Thu, Mar 7, 2024 at 10:49=E2=80=AFPM Richard Biener wrote: > > On Thu, Mar 7, 2024 at 8:29=E2=80=AFPM Ken Matsui wrote: > > > > On Tue, Mar 5, 2024 at 7:58=E2=80=AFAM Richard Biener > > wrote: > > > > > > 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, th= is > > > > > > equivalence does not hold for types other than signed integers.= When > > > > > > it comes to conditions, the former was translated to a combinat= ion of > > > > > > sub and test, whereas the latter was translated to a single cmp= . > > > > > > Thus, this optimization pass tries to optimize the former to th= e > > > > > > latter. > > > > > > > > > > > > When `-fwrapv` is enabled, GCC treats the overflow of signed in= tegers > > > > > > 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 overflo= w 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 maxim= um value > > > > > > for a `long long`, this calculation overflows in a defined mann= er > > > > > > (wrapping around), which under `-fwrapv` is a legal operation t= hat > > > > > > 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. Henc= e, > > > > > > optimizations that rely on the equivalence of `(x - y) CMP 0` t= o > > > > > > `x CMP y` (and vice versa) cannot be safely applied when `-fwra= pv` is > > > > > > enabled. This is why this optimization pass is disabled under > > > > > > `-fwrapv`. > > > > > > > > > > > > This optimization pass must run before the Jump Threading pass = and the > > > > > > 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 V= RP pass > > > > > > because we know the postcondition of the first condition is dif= f <=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 fo= r 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 a= nd 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. > > > > > > > > > > > > PR middle-end/113680 > > > > > > > > > > This shouldn't be done as a new optimization pass. It fits eithe= r > > > > > the explicit code present in the forwprop pass or a new match.pd > > > > > pattern. There's possible interaction with x - y value being use= d > > > > > 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 multip= le > > > > 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). > > > > > > > I see. When would patterns in match.pd be applied? Around forwprop > > or somewhere else? (Also, could you please tell me a document I can > > learn about these if it exists?) I ask because this optimization > > should be applied before the Jump Threading and VRP passes. > > match.pd patterns get used whenever an expression is simplified. And > yes, the forwprop pass tries to simplify expressions rooted at each stmt. > In general each pass changing a statement or one of its operands should > re-simplify the expression rooted at it, so the theory is that all expres= sions > always remain simplified. > > There's no documentation about the patterns present in match.pd if > you meant that. What I meant was the high-level structure around match.pd and other passes, but it is answered! That makes sense. Thank you for your time! > I'm usually writing small testcases to "query" match.pd > and use -fdump-tree-all-folding looking into .original (when folded at > generic time), .gimple, .ccp and .forwprop which are the usual early > places where simplifications are triggered. This is really helpful, thank you! > > Richard. > > > > > 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 anticipatin= g > > > > > 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 overflo= w > > > 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. > > > > Thank you so much! I will check this out. > > > > > > > > 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-= aliasing > > > > > > -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-dom= inator-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 optimizat= ions. It also saves one jump. This flag > > > > > > is enabled by default at @option{-O1} and higher. It is not e= nabled > > > > > > for @option{-Os}, since it usually increases code size. > > > > > > > > > > > > +@opindex ftree-cmp > > > > > > +@item -ftree-cmp > > > > > > +Perform comparison optimization on trees. This decreases unne= cessary > > > > > > +instructions for comparisons. This flag is enabled by default= at > > > > > > +@option{-O1} and higher. This optimization is automatically d= isabled when > > > > > > +@option{-fwrapv} is specified to ensure correct behavior under= signed integer > > > > > > +overflow wrapping. > > > > > > + > > > > > > @opindex ftree-loop-optimize > > > > > > @item -ftree-loop-optimize > > > > > > Perform loop optimizations on trees. This flag is enabled by = default > > > > > > 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= _options_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 no= t see > > > > > > /* After CCP we rewrite no longer addressed locals in= to 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 tha= t we > > > > > > diff --git a/gcc/testsuite/gcc.dg/pr113680.c b/gcc/testsuite/gc= c.dg/pr113680.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 { targe= t { i?86-*-* x86_64-*-* } } } } */ > > > > > > +/* { dg-final { scan-assembler-not "sub" { target { i?86-*-* x= 86_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 constr= uction") > > > > > > DEFTIMEVAR (TV_TREE_CLEANUP_CFG , "tree CFG cleanu= p") > > > > > > 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::= context *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 *c= txt); > > > > > > extern gimple_opt_pass *make_pass_build_ssa (gcc::context *ctx= t); > > > > > > extern gimple_opt_pass *make_pass_build_alias (gcc::context *c= txt); > > > > > > 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 the > > > > > > +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 WIT= HOUT > > > > > > +ANY WARRANTY; without even the implied warranty of MERCHANTABI= LITY or > > > > > > +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public = License > > > > > > +for more details. > > > > > > + > > > > > > +You should have received a copy of the GNU General Public Lice= nse > > > > > > +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 si= gned integers and > > > > > > + CMP is <, <=3D, >, or >=3D. Similarly, 0 CMP (x - y) is eq= uivalent 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 conditi= ons, the former > > > > > > + was translated to a combination of sub and test, whereas th= e latter was > > > > > > + translated to a single cmp. Thus, this optimization pass t= ries to optimize > > > > > > + the former to the latter. > > > > > > + > > > > > > + When `-fwrapv` is enabled, GCC treats the overflow of signe= d integers as > > > > > > + defined behavior, specifically, wrapping around according t= o two's > > > > > > + complement arithmetic. This has implications for optimizat= ions that > > > > > > + rely on the standard behavior of signed integers, where ove= rflow 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 m= aximum value for > > > > > > + a `long long`, this calculation overflows in a defined mann= er > > > > > > + (wrapping around), which under `-fwrapv` is a legal operati= on that produces > > > > > > + a negative value due to two's complement wraparound. There= fore, > > > > > > + `llmax - llmin < 0` is true. > > > > > > + > > > > > > + However, the direct comparison `llmax < llmin` is false sin= ce `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 i= s why this > > > > > > + optimization pass is disabled under `-fwrapv`. > > > > > > + > > > > > > + This optimization pass must run before the Jump Threading p= ass and > > > > > > + the 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 t= he 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 cm= p for the first > > > > > > + condition. However, if we apply this pass beforehand, we si= mply 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 s= ub 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,= return 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_EXP= R) > > > > > > + 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_c= ond_lhs (stmt)); > > > > > > + if (lhs =3D=3D NULL_TREE) > > > > > > + return; > > > > > > + > > > > > > + const_tree rhs =3D prop_integer_zero_or_minus_expr (gimple_c= ond_rhs (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 MINU= S_EXPR and > > > > > > + 0, and replace them with the equivalent comparison of the o= perands 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 app= lied as 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_ne= xt (&gsi)) > > > > > > + { > > > > > > + 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 > > > > > >