[Bug tree-optimization/91384] [8/9/10 Regression] Compare with negation is not eliminated

[Bug tree-optimization/91384] [8/9/10 Regression] Compare with negation is not eliminated

[law at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com

--- Comment #6 from Jeffrey A. Law <law at redhat dot com> ---
Couldn't cmpelim realize insn6 sets the condition codes in a useful way in this
RTL:

(insn 29 3 6 2 (set (reg/v:SI 40 r12 [orig:82 <retval> ] [82])
        (reg/v:SI 5 di [orig:83 a ] [83])) "j.c":9:9 67 {*movsi_internal}
     (nil))
(insn 6 29 7 2 (parallel [
            (set (reg/v:SI 40 r12 [orig:82 <retval> ] [82])
                (neg:SI (reg/v:SI 40 r12 [orig:82 <retval> ] [82])))
            (clobber (reg:CC 17 flags))
        ]) "j.c":9:9 525 {*negsi2_1}
     (nil))
(insn 7 6 8 2 (set (reg:CCZ 17 flags)
        (compare:CCZ (reg/v:SI 5 di [orig:83 a ] [83])
            (const_int 0 [0]))) "j.c":9:6 7 {*cmpsi_ccno_1}
     (nil))
(jump_insn 8 7 9 2 (set (pc)
        (if_then_else (eq (reg:CCZ 17 flags)
                (const_int 0 [0]))
            (label_ref 13)
            (pc))) "j.c":9:6 736 {*jcc}

If we're just interested in CC_Z, then we could use the output of insn 7 rather
than needing a distinct test insn.

[Bug tree-optimization/91384] [8/9/10/11 Regression] Compare with negation is not eliminated

[ubizjak at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

--- Comment #7 from Uroš Bizjak <ubizjak at gmail dot com> ---
Still happens on trunk.

[Bug tree-optimization/91384] [8/9/10/11 Regression] Compare with negation is not eliminated

[ubizjak at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

--- Comment #8 from Uroš Bizjak <ubizjak at gmail dot com> ---
(In reply to Jakub Jelinek from comment #1)
> Started with r223689.  Though, generally that change looks like a useful
> GIMPLE canonicalization.


How about we amend the above change to:

diff --git a/gcc/match.pd b/gcc/match.pd
index 43bacb4f68e..1370ba7302d 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -4506,6 +4506,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (cmp (negate @0) CONSTANT_CLASS_P@1)
   (if (FLOAT_TYPE_P (TREE_TYPE (@0))
        || (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
+           && integer_nonzerop (@0)
           && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))))
    (with { tree tem = const_unop (NEGATE_EXPR, TREE_TYPE (@0), @1); }
     (if (tem && !TREE_OVERFLOW (tem))

so we simplify (cmp (negate @0) CONSTANT_CLASS_P@1)) only for non-zero integer
arguments. For the original testcase, the compare is eliminated:

test:
        negl    %edi
        pushq   %r12
        movl    %edi, %r12d
        je      .L2
        call    foo
        movl    %r12d, %eax
        popq    %r12
        ret
.L2:
        call    bar
        movl    %r12d, %eax
        popq    %r12
        ret

Please also note that for the slightly changed original testcase:

--cut here--
void f1 (void);
void f2 (void);

void
foo (int a)
{
  int r = -a;
  if (r)
    f1 ();
  else
    f2 ();
}
--cut here--

combine RTL pass manages to remove the negation without problems:

Trying 6 -> 7:
    6: {r84:SI=-r85:SI;clobber flags:CC;}
      REG_DEAD r85:SI
      REG_UNUSED flags:CC
    7: flags:CCZ=cmp(r84:SI,0)
      REG_DEAD r84:SI
Successfully matched this instruction:
(set (reg:CCZ 17 flags)
    (compare:CCZ (reg:SI 85)
        (const_int 0 [0])))

so the compilation (-O2) results in the same assembly:

foo:
        testl   %edi, %edi
        je      .L2
        jmp     f1
.L2:
        jmp     f2

[Bug tree-optimization/91384] [8/9/10/11 Regression] Compare with negation is not eliminated

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
The local gimple transform is not right or wrong, it depends on the
surroundings
and unless we have a way to assess those in a good way doing it in one or the
other way is going to hurt either case.

The usual "fix" is to stick single-use restrictions onto the patterns involving
uses in compares, we're not very consistent with that.

Like the following

diff --git a/gcc/match.pd b/gcc/match.pd
index 43bacb4f68e..c5582021b0e 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -4503,10 +4503,11 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
           && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))))
    (scmp @0 @1)))
  (simplify
-  (cmp (negate @0) CONSTANT_CLASS_P@1)
+  (cmp (negate@2 @0) CONSTANT_CLASS_P@1)
   (if (FLOAT_TYPE_P (TREE_TYPE (@0))
        || (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
-          && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))))
+          && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))
+          && single_use (@2)))
    (with { tree tem = const_unop (NEGATE_EXPR, TREE_TYPE (@0), @1); }
     (if (tem && !TREE_OVERFLOW (tem))
      (scmp @0 { tem; }))))))

[Bug tree-optimization/91384] [8/9/10/11 Regression] Compare with negation is not eliminated

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
But then

void foo (void);
void bar (void);

int
test (int a)
{
  if (a)
    foo ();
  else
    bar ();

  return -a;
}

is not optimized either (the usual argument - the user could have written it
in the way the compiler canonicalizes).

On RTL where the CCs are appearant that's a LCM / PRE problem with the
compare anticipating the zero flag here and the negate computing it.
That makes it profitable to move the negate and eliminate the CC flag
compute with it (for the testcase above).

On the original case where we have

int
test (int a)
{
  int r = -a;
  if (a)
    foo ();
  else
    bar ();

  return r;
}

that's more a local CSE opportunity (though of course for this modified
testcase we sink the -a compute to the return, re-creating the first
case in this comment).

As it is only RTL representing CC at all this is really a RTL global
optimization issue in the end.  GIMPLE can only help to a limited extent
and all missed canonicalization (like if we add a single_use check)
eventually leads to missed global CSE opportunities.

[Bug middle-end/91384] [9/10/11/12 Regression] Compare with negation is not eliminated

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|8.5                         |9.4

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 8 branch is being closed.

[Bug middle-end/91384] [9/10/11/12 Regression] Compare with negation is not eliminated

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.4                         |9.5

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9.4 is being released, retargeting bugs to GCC 9.5.

[Bug tree-optimization/91384] [9/10/11/12 Regression] Compare with negation is not eliminated

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|middle-end                  |tree-optimization

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So looking at what other compilers do here.
ICC and MSVC do what GCC did in GCC 4.1.2.
LLVM does similar to what GCC does now except they also push the -a to below
the if statement.

If we have:
void foo (int);
void bar (void);
int g(int, int);

int
test (int a)
{
  int r;

  if (r = -a)
    foo (r);
  else
    bar ();

  return r;
}

----- CUT ----
LLVM is able to produce the neg/branch combo now while GCC is not.

[Bug tree-optimization/91384] [9/10/11/12 Regression] Compare with negation is not eliminated

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

--- Comment #14 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #13)
> LLVM is able to produce the neg/branch combo now while GCC is not.

One more testcase:
void foo (void);
void bar (void);
int g(int, int);

int
test (int a)
{
  int r;

  if (r = -a)
    foo ();
  else
    bar ();

  return g(a,r);
}
---- CUT ----
LLVM is able to move the -a past the if statement still.
So it is not as simple as a single usage either for LLVM.

[Bug tree-optimization/91384] [9/10/11/12 Regression] Compare with negation is not eliminated

[roger at nextmovesoftware dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

Roger Sayle <roger at nextmovesoftware dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |roger at nextmovesoftware dot com
           Assignee|unassigned at gcc dot gnu.org      |roger at nextmovesoftware dot com

--- Comment #15 from Roger Sayle <roger at nextmovesoftware dot com> ---
Patch proposed.
https://gcc.gnu.org/pipermail/gcc-patches/2022-February/591013.html

[Bug tree-optimization/91384] [9/10/11/12 Regression] Compare with negation is not eliminated

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

--- Comment #16 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Roger Sayle <sayle@gcc.gnu.org>:

https://gcc.gnu.org/g:28068d1115648adcc08ae57372170f3277915a0d

commit r12-7417-g28068d1115648adcc08ae57372170f3277915a0d
Author: Roger Sayle <roger@nextmovesoftware.com>
Date:   Mon Feb 28 22:30:27 2022 +0000

    PR tree-optimization/91384: peephole2 to eliminate testl after negl.

    This patch is my proposed solution to PR tree-optimization/91384 which is
    a missed-optimization/code quality regression on x86_64.  The problematic
    idiom is "if (r = -a)" which is equivalent to both "r = -a; if (r != 0)"
    and alternatively "r = -a; if (a != 0)".  In this particular case, on
    x86_64, we prefer to use the condition codes from the negation, rather
    than require an explicit testl instruction.

    Unfortunately, combine can't help, as it doesn't attempt to merge pairs
    of instructions that share the same operand(s), only pairs/triples of
    instructions where the result of each instruction feeds the next.  But
    I doubt there's sufficient benefit to attempt this kind of "combination"
    (that wouldn't already be caught by the tree-ssa passes).

    Fortunately, it's relatively easy to fix this up (addressing the
    regression) during peephole2 to eliminate the unnecessary testl in:

            movl    %edi, %ebx
            negl    %ebx
            testl   %edi, %edi
            je      .L2

    2022-02-28  Roger Sayle  <roger@nextmovesoftware.com>

    gcc/ChangeLog
            PR tree-optimization/91384
            * config/i386/i386.md (peephole2): Eliminate final testl insn
            from the sequence *movsi_internal, *negsi_1, *cmpsi_ccno_1 by
            transforming using *negsi_2 for the negation.

    gcc/testsuite/ChangeLog
            PR tree-optimization/91384
            * gcc.target/i386/pr91384.c: New test case.

[Bug tree-optimization/91384] [9/10/11/12 Regression] Compare with negation is not eliminated

[roger at nextmovesoftware dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91384

Roger Sayle <roger at nextmovesoftware dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
   Target Milestone|9.5                         |12.0
         Resolution|---                         |FIXED

--- Comment #17 from Roger Sayle <roger at nextmovesoftware dot com> ---
This should now be fixed on mainline.