[Bug tree-optimization/104639] New: Useless loop not fully optimized anymore

[Bug tree-optimization/104639] New: Useless loop not fully optimized anymore

[denis.campredon at gmail dot com]

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

            Bug ID: 104639
           Summary: Useless loop not fully optimized anymore
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: denis.campredon at gmail dot com
  Target Milestone: ---

the following code compiled with -02
-------------------
bool foo(int i) {
    while (i == 4)
        i += 2;
    return i;
}
------------------

Trunk generates the following assembly
---------
foo(int):
        cmp     edi, 4
        mov     eax, 6
        cmove   edi, eax
        test    edi, edi
        setne   al
        ret
---------

whereas 11.2 generate more optimized assembly

---------
foo(int):
        test    edi, edi
        setne   al
        ret
--------

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2022-02-22
   Target Milestone|---                         |12.0
     Ever confirmed|0                           |1
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |jakub at gcc dot gnu.org
            Summary|Useless loop not fully      |[12 Regression] Useless
                   |optimized anymore           |loop not fully optimized
                   |                            |anymore
           Priority|P3                          |P1

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r12-3453-g01b5038718056b024b370b74a874fbd92c5bbab3

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
One thing is not threading through loop latches, but in this case once the loop
is optimized into straight line code in thread2 we don't thread that further,
so end up with
  if (i_2(D) == 4)
    goto <bb 4>; [97.00%]
  else
    goto <bb 3>; [3.00%]

  <bb 3> [local count: 3540129]:

  <bb 4> [local count: 118111600]:
  # i_6 = PHI <i_2(D)(3), 6(2)>
  _3 = i_6 != 0;
  return _3;
For the result, the
 i_6 = i_2(D) == 4 ? 6 : i_2(D);
is equivalent to just i_2(D) because we only care whether it is non-zero and
both 4 and 6 are non-zero.

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
it's odd that VRP doesn't optimize this though.  VRP2 says

Exported global range table:
============================
i_6  : int ~[4, 4]
bool foo (int i)
{
  bool _3;

  <bb 2> [local count: 118111600]:
  if (i_2(D) == 4)
    goto <bb 3>; [97.00%]
  else
    goto <bb 4>; [3.00%]

  <bb 3> [local count: 955630224]:

  <bb 4> [local count: 118111600]:
  # i_6 = PHI <i_2(D)(2), 6(3)>
  _3 = i_6 != 0;
  return _3;

but shouldn't ranger figure that i_2(D) != 0 && 6 != 0 is the same as
i_2(D) != 0?  Alternatively this could be sth for phiopt.  PRE still
sees the loop (I guess it was previously the one optimizing this)

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The ranger itself can't, i_2(D) in the PHI arg is ~[4, 4], and _3 is still [0,
1] aka VARYING.
Yes, phiopt could handle this by seeing a PHI result is only used in an
equality comparison and try to figure out something for it using range info or
so, or vrp2 could.
In GCC 11, it was indeed PRE that optimized that:
  if (i_2(D) == 4)
    goto <bb 4>; [97.00%]
  else
    goto <bb 3>; [3.00%]

  <bb 3> [local count: 3540129]:

  <bb 4> [local count: 118111600]:
  # i_6 = PHI <i_2(D)(3), 6(2)>
  _3 = i_6 != 0;
which is what we have on the trunk until optimized with:
  _Bool _1;
  _Bool prephitmp_7;

  <bb 2> [local count: 118111600]:
  if (i_2(D) == 4)
    goto <bb 4>; [97.00%]
  else
    goto <bb 3>; [3.00%]

  <bb 3> [local count: 3540129]:
  _1 = i_2(D) != 0;

  <bb 4> [local count: 118111600]:
  # i_6 = PHI <i_2(D)(3), 6(2)>
  # prephitmp_7 = PHI <_1(3), 1(2)>
and later reassoc2 optimizes that to just
  _6 = i_2(D) != 0;
  return _6;

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[denis.campredon at gmail dot com]

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

--- Comment #5 from denis.campredon at gmail dot com ---
That peace of code seems related but does not need a loop unlike the original
one. 

------------------
int foo(unsigned i) {
    return i ? i % 2 : 0;
}
------------------

With trunk 12
------------------------
foo(unsigned int):
        mov     eax, edi
        xor     edx, edx
        and     eax, 1
        test    edi, edi
        cmove   eax, edx
        ret
-----------------------

With 11.2
-----------------------
foo(unsigned int):
        mov     eax, edi
        and     eax, 1
        ret
-----------------------

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The #c5 case seems unrelated and started with
r12-5358-g32221357007666124409ec3ee0d3a1cf263ebc9e
Please file a separate PR for that.

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

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

--- Comment #7 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
FWIW, thread2 does thread everything that is threadable.  That is, we thread
5->3->4 from this:

  <bb 3> [local count: 1073741824]:
  # i_1 = PHI <i_2(D)(2), 6(5)>
  if (i_1 == 4)
    goto <bb 5>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 5> [local count: 955630224]:
  goto <bb 3>; [100.00%]

into this:

  <bb 2> [local count: 118111600]:
  if (i_2(D) == 4)
    goto <bb 3>; [97.00%]
  else
    goto <bb 4>; [3.00%]

  <bb 3> [local count: 955630224]:
  # i_5 = PHI <6(2)>

  <bb 4> [local count: 118111600]:
  # i_6 = PHI <i_2(D)(2), i_5(3)>
  _3 = i_6 != 0;
  return _3;

There are no more conditionals we can thread in the final form above.

To my untrained eye, it does seem like phiopt should be able to optimize:

  <bb 4> [local count: 118111600]:
  # i_6 = PHI <i_2(D)(2), 6(3)>
  _3 = i_6 != 0;

into:

  _3 = i_2 != 0;

Then BB2 and BB3 can just be cleaned up as dead?

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[amacleod at redhat dot com]

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

--- Comment #8 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Richard Biener from comment #3)
> it's odd that VRP doesn't optimize this though.  VRP2 says
> 
> Exported global range table:
> ============================
> i_6  : int ~[4, 4]
> bool foo (int i)
> {
>   bool _3;
> 
>   <bb 2> [local count: 118111600]:
>   if (i_2(D) == 4)
>     goto <bb 3>; [97.00%]
>   else
>     goto <bb 4>; [3.00%]
>   
>   <bb 3> [local count: 955630224]:
>   
>   <bb 4> [local count: 118111600]:
>   # i_6 = PHI <i_2(D)(2), 6(3)>
>   _3 = i_6 != 0;
>   return _3;
> 
> but shouldn't ranger figure that i_2(D) != 0 && 6 != 0 is the same as
> i_2(D) != 0?  Alternatively this could be sth for phiopt.  PRE still
> sees the loop (I guess it was previously the one optimizing this)

Ranger itself isn't going to see that, All we can tell by ranges directly is
that it is ~[4, 4].    You have to look back at the def from the use to come to
this conclusion, so it would be a simplification or  PHI-opt thing.  

Curious question, if that was an 'if' instead of a return using _3, the
threader would probably thread the PHI away?  ie:
  <bb 4> [local count: 118111600]:
  # i_6 = PHI <i_2(D)(2), 6(3)>
  _3 = i_6 != 0;
  if (_3 != 0)
    goto <bb7>
  else
    goto <bb8>

I don't suppose there is any possible future enhancement that would let us
thread into returns like this?  Or maybe its not common enough?

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[aldyh at gcc dot gnu.org]

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

--- Comment #9 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #8)
> (In reply to Richard Biener from comment #3)

> Curious question, if that was an 'if' instead of a return using _3, the
> threader would probably thread the PHI away?  ie:
>   <bb 4> [local count: 118111600]:
>   # i_6 = PHI <i_2(D)(2), 6(3)>
>   _3 = i_6 != 0;
>   if (_3 != 0)
>     goto <bb7>
>   else
>     goto <bb8>
> 
> I don't suppose there is any possible future enhancement that would let us
> thread into returns like this?  Or maybe its not common enough?

Sure, the threader can't thread the current situation because it only does
conditionals not PHIs.  If that were an if, it should be able to thread it.

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[amacleod at redhat dot com]

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

--- Comment #10 from Andrew Macleod <amacleod at redhat dot com> ---
I was thinking less about phis and more that its a "return" instead of an "if"
ending the block preventing the threader from doing anything.

  _3 = i_6 != 0;
  return _3;

Ie, so if a return uses a condition, we could act like its a branch.. if that
were viewed as
  if (_3)
    return 1
  else
    return 0
the threader would do what we are looking for?

I don't know if that would be easy or hard or even worthwhile, but I seem to
vaguely recall another situation a few months ago that was similar... with a
block that ended in a return not triggering threads thru a PHI in the block
that could have been helpful.

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[aldyh at gcc dot gnu.org]

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

--- Comment #11 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #10)
> I was thinking less about phis and more that its a "return" instead of an
> "if" ending the block preventing the threader from doing anything.
> 
>   _3 = i_6 != 0;
>   return _3;
> 
> Ie, so if a return uses a condition, we could act like its a branch.. if
> that were viewed as
>   if (_3)
>     return 1
>   else
>     return 0
> the threader would do what we are looking for?
> 
> I don't know if that would be easy or hard or even worthwhile, but I seem to
> vaguely recall another situation a few months ago that was similar... with a
> block that ended in a return not triggering threads thru a PHI in the block
> that could have been helpful.

I don't know.  I thought return's were special.  Can there be more than one per
function?

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[jakub at gcc dot gnu.org]

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

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Aldy Hernandez from comment #11)
> I don't know.  I thought return's were special.  Can there be more than one
> per function?

I think high gimple (what before lower pass) allows multiple GIMPLE_RETURN
stmts, but low gimple does not.
But gimple-low.cc comment only says:
   3- Multiple identical return statements are grouped into a single
      return and gotos to the unique return site.
so perhaps it isn't guaranteed either.

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[jakub at gcc dot gnu.org]

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

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 52774
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52774&action=edit
gcc12-pr104639.patch

Untested patch to optimize this in phiopt.

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:a42aa68bf1ad745a6b36ab9beed1fc2e77ac3f88

commit r12-8078-ga42aa68bf1ad745a6b36ab9beed1fc2e77ac3f88
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Apr 11 10:44:28 2022 +0200

    phiopt: Optimize (x != cst1 ? x : cst2) != cst3 [PR104639]

    Here is an attempt to resolve a P1 regression, where due to threading
    changes we no longer optimize
    bool foo(int i) {
        while (i == 4)
            i += 2;
        return i;
    }
    to just return i != 0; by enhancing the phiopt value_replacement
    optimization.  Normally it will optimize x != cst1 ? x : cst1 to x.
    Here we extend it to also optimize x != cst1 ? x : cst2 to x if
    it (phi result) has a single immediate use which is a comparison
    with some INTEGER_CST cst3 and we can prove that we don't care
    whether x is cst1 or cst2 because both compare the same against cst3.

    2022-04-11  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/104639
            * tree-ssa-phiopt.cc: Include tree-ssa-propagate.h.
            (value_replacement): Optimize (x != cst1 ? x : cst2) != cst3
            into x != cst3.

            * gcc.dg/tree-ssa/pr104639-1.c: New test.
            * gcc.dg/tree-ssa/pr104639-2.c: New test.

[Bug tree-optimization/104639] [12 Regression] Useless loop not fully optimized anymore

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Regression fixed, but for GCC 13 we as Richi noted we want some better
approach.