[Bug tree-optimization/113265] New: [Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[Bug tree-optimization/113265] New: [Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[652023330028 at smail dot nju.edu.cn]

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

            Bug ID: 113265
           Summary: [Regression] Missed optimization for redundancy
                    computation elimination may be due to constant
                    propagation about 0 too late
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: 652023330028 at smail dot nju.edu.cn
  Target Milestone: ---

Hello, we noticed that maybe there is a missed optimization for redundancy
computation elimination.

https://godbolt.org/z/drfejE5cP

int x,y,z;
void func(int a, int b){
    a=b-x;
    b=a;
    y=0;
    z=(y+a)/(-b);
}

GCC -O3 :
func(int, int):
        mov     ecx, DWORD PTR x[rip]
        mov     eax, esi
        mov     DWORD PTR y[rip], 0
        sub     eax, ecx
        sub     ecx, esi
        cdq
        idiv    ecx
        mov     DWORD PTR z[rip], eax
        ret

Earlier GCC versions get the expected optimizations:
Expected code (GCC 7.5):
func(int, int):
        mov     DWORD PTR y[rip], 0
        mov     DWORD PTR z[rip], -1
        ret

The following code is optimized by gcc as expected:
void func2(int a, int b){
    a=b-x;
    b=a;
    y=0;
    z=(0+a)/(-b);
}

Comparing the code for func and func2 and their ccp1(tree), we suspect that
this issue may be caused by too late propagation about y=0.

Thank you very much for your time and effort! We look forward to hearing from
you

[Bug tree-optimization/113265] [Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2024-01-09

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
We're somehow expanding -b as x - b.  That's done by forwprop seeing

  <bb 2> :
  x.0_1 = x;
  a_8 = b_7(D) - x.0_1;
  y = 0;
  y.1_2 = y;
  _3 = a_8 + y.1_2;
  _4 = -a_8;
  _5 = _3 / _4;
  z = _5;

this transform is done irrespectively of whether the non-negated expression
is still used (its a 1:1 replacement, though unary to binary).  We're
thn missing folding of

  a_8 = b_7(D) - x.0_1;
  _4 = x.0_1 - b_7(D);
  _5 = a_8 / _4;

failing to realize this is a_8 / -a_8.

Reduced testcase which isn't optimized by GCC 7 either:

int z;
void func(int a, int b){
    z=(a-b)/-(a-b);
}
void func1(int a, int b){
    z=(a-b)/(b-a);
}

[Bug tree-optimization/113265] [Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
We have

 /* X / -X is -1.  */
 (simplify
   (div:C @0 (negate @0))
...

which doesn't use (negate_expr_p @0) but that wouldn't help because

(match negate_expr_p
 (minus @0 @1)
 (if ((ANY_INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_WRAPS (type))
      || (FLOAT_TYPE_P (type)
          && !HONOR_SIGN_DEPENDENT_ROUNDING (type)
          && !HONOR_SIGNED_ZEROS (type)))))

as (a - b) might be INT_MIN which we can't negate w/o invoking undefined
behavior.  We also don't have (negate_expr_p @0), a way to match the
then negated form.

VN might come to the rescue to turn b - a to -(a - b) if that is available.

[Bug tree-optimization/113265] [Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Thinking on how to solve this would be have a match which says
maybe_negative_expr which matches - and minus expressions and then have an
external function which checks if -@0 matches @1 .

Though that would be gcc 15 material and should be replacing where we already
match (a-b) and (b-a) manually and that might simplify things too ...

[Bug tree-optimization/113265] [11/12/13/14 Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |8.1.0
            Summary|[Regression] Missed         |[11/12/13/14 Regression]
                   |optimization for redundancy |Missed optimization for
                   |computation elimination may |redundancy computation
                   |be due to constant          |elimination may be due to
                   |propagation about 0 too     |constant propagation about
                   |late                        |0 too late
   Target Milestone|---                         |11.5
      Known to work|                            |7.5.0

[Bug tree-optimization/113265] [11/12/13/14 Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Started with r8-4394-g81bd903a6aa903 which added the `-(a - b)` -> `b - a`
simplification to match.

Anyways I am going to fix this for GCC 15.


Note
 /* (A - B) == 0 ? (A - B) : (B - A)    same as (B - A) */

Could be represented via:
@0 == 0 ? @0 : (maybe_neg @1)
if (expr_is_negative (@0, @1))
...

Too.

This would be merged into:
 /* A == 0 ? A : -A    same as -A */
even.

[Bug tree-optimization/113265] [11/12/13/14 Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[law at gcc dot gnu.org]

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

Jeffrey A. Law <law at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
                 CC|                            |law at gcc dot gnu.org

[Bug tree-optimization/113265] [11/12/13/14/15 Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 113433 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/113265] [11/12/13/14/15 Regression] Missed optimization for redundancy computation elimination may be due to constant propagation about 0 too late

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58289
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58289&action=edit
Patch without testcase

Just need to add testcases but the patch was able to bootstrap/test without any
regressions.