[Bug tree-optimization/61734] New: Regression in ABS_EXPR recognition

[Bug tree-optimization/61734] New: Regression in ABS_EXPR recognition

[enkovich.gnu at gmail dot com]

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

            Bug ID: 61734
           Summary: Regression in ABS_EXPR recognition
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: enkovich.gnu at gmail dot com

Recently a performance regression occurred in tests heavily using ABS
computation (observed on x86 and ARM targets).  It is caused by missing
ABS_EXPR recognition which results in sub-optimal code.

Problem appeared after this commit:

commit 32ce9a5c4208411361402f60e672c4830da0bc8f
Author: ebotcazou <ebotcazou@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Tue May 27 19:54:46 2014 +0000

        * fold-const.c (fold_comparison): Clean up and extend X +- C1 CMP C2
        to X CMP C2 -+ C1 transformation to EQ_EXPR/NE_EXPR.
        Add X - Y CMP 0 to X CMP Y transformation.
        (fold_binary_loc) <EQ_EXPR/NE_EXPR>: Remove same transformations.


    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@210979
138bc75d-0d04-0410-961f-82ee72b054a4


Here is a simple test (tested on linux-x86_64):
>cat test.i
unsigned long test (unsigned char a, unsigned char b, unsigned long sum)
{
  sum += ((a - b) > 0 ? (a - b) : -(a - b));
  return sum;
}
>gcc-exp-build/bin/gcc test.i -m32 -O2 -fdump-tree-gimple -c
>cat test.i.004t.gimple
test (unsigned char a, unsigned char b, long unsigned int sum)
{
  long unsigned int iftmp.0;
  int D.1720;
  int D.1721;
  int D.1724;
  int D.1726;
  long unsigned int D.1727;

  D.1720 = (int) a;
  D.1721 = (int) b;
  if (D.1720 > D.1721) goto <D.1722>; else goto <D.1723>;
  <D.1722>:
  D.1720 = (int) a;
  D.1721 = (int) b;
  D.1724 = D.1720 - D.1721;
  iftmp.0 = (long unsigned int) D.1724;
  goto <D.1725>;
  <D.1723>:
  D.1721 = (int) b;
  D.1720 = (int) a;
  D.1726 = D.1721 - D.1720;
  iftmp.0 = (long unsigned int) D.1726;
  <D.1725>:
  sum = iftmp.0 + sum;
  D.1727 = sum;
  return D.1727;
}


With older compiler I have:

>gcc-ref-build/bin/gcc test.i -m32 -O2 -fdump-tree-gimple -c
>cat test.i.004t.gimple
test (unsigned char a, unsigned char b, long unsigned int sum)
{
  int D.1719;
  int D.1720;
  int D.1721;
  int D.1722;
  long unsigned int D.1723;
  long unsigned int D.1724;

  D.1719 = (int) a;
  D.1720 = (int) b;
  D.1721 = D.1719 - D.1720;
  D.1722 = ABS_EXPR <D.1721>;
  D.1723 = (long unsigned int) D.1722;
  sum = D.1723 + sum;
  D.1724 = sum;
  return D.1724;
}


BTW both compilers generate ABS_EXPR when -O0 is used instead of -O2.  Both
compilers fail to generate ABS_EXPR when -m64 is used instead of -m32.

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu.org
          Component|tree-optimization           |middle-end
   Target Milestone|---                         |4.10.0
            Summary|Regression in ABS_EXPR      |[4.10 Regression]
                   |recognition                 |Regression in ABS_EXPR
                   |                            |recognition

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-07-07
     Ever confirmed|0                           |1

--- Comment #1 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Indeed, there is a conflict between fold_cond_expr_with_comparison:

  /* If we have A op 0 ? A : -A, consider applying the following
     transformations:

     A == 0? A : -A    same as -A
     A != 0? A : -A    same as A
     A >= 0? A : -A    same as abs (A)
     A > 0?  A : -A    same as abs (A)
     A <= 0? A : -A    same as -abs (A)
     A < 0?  A : -A    same as -abs (A)

and fold_comparison:

  /* Transform comparisons of the form X - Y CMP 0 to X CMP Y.  */

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So perhaps teach fold also about A CMP B ? A - B : -(A - B) etc.?  Then it will
handle this idiom even if the user writes it that way in the source.

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

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

--- Comment #3 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> So perhaps teach fold also about A CMP B ? A - B : -(A - B) etc.?  Then it
> will handle this idiom even if the user writes it that way in the source.

Interesting idea, although it doesn't fit into fold_cond_expr_with_comparison.

Maybe the X - Y CMP 0 to X CMP Y transformation should simply be disabled again
(except for EQ/NE) and the missing comment giving the rationale for this added.

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Sure, I wouldn't change fold_cond_expr_with_comparison itself.
Instead, next to the two spots that call fold_cond_expr_with_comparison add
another two, which would if arg1 or op2 is a MINUS_EXPR where the first
MINUS_EXPR operand is equal to one comparison operand and the other to the
other one, basically undo your transformation for the purpose of the
fold_cond_expr_with_comparison call; if that returns non-NULL, we'd fold to
that, essentially undoing your transformation, but otherwise we wouldn't undo
anything.

Perhaps in addition to MINUS_EXPR we should handle PLUS_EXPR with INTEGER_CST
second operand, so
 A >= 5 ? (A + (-5)) : -(A + (-5)) and similar cases.

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[glisse at gcc dot gnu.org]

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

--- Comment #5 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #2)
> So perhaps teach fold also about A CMP B ? A - B : -(A - B) etc.?

Or teach phiopt about A CMP B ? (U)((T)A - (T)B) : (U)((T)B - (T)A)? Hmm, it is
starting to be a bit big, with a number of variations depending on where the
casts are. fold may be easier indeed.

(In reply to Jakub Jelinek from comment #4)
> Perhaps in addition to MINUS_EXPR we should handle PLUS_EXPR with
> INTEGER_CST second operand, so
>  A >= 5 ? (A + (-5)) : -(A + (-5)) and similar cases.

I believe we canonicalize A+(-5) to A-5, but A >= -5 ? (A + 5) : -(A + 5) is
the same idea.

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[ebotcazou at gcc dot gnu.org]

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

--- Comment #7 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> Eric, dou you have any plans regarding this issue?

Sure, see comment #3.

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[ebotcazou at gcc dot gnu.org]

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

--- Comment #8 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
Author: ebotcazou
Date: Mon Jul 28 08:55:17 2014
New Revision: 213118

URL: https://gcc.gnu.org/viewcvs?rev=213118&root=gcc&view=rev
Log:
    PR middle-end/61734
    * fold-const.c (fold_comparison): Disable X - Y CMP 0 to X CMP Y for
    operators other than the equality operators.

Added:
    trunk/gcc/testsuite/gcc.dg/fold-abs-5.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/Wstrict-overflow-25.c
    trunk/gcc/testsuite/gcc.dg/fold-compare-8.c

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

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

--- Comment #9 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
.

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[enkovich.gnu at gmail dot com]

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

--- Comment #10 from Ilya Enkovich <enkovich.gnu at gmail dot com> ---
Thanks for the fix!

Is there any reason for ABS_EXPR detection for not working on 64bit target for
the same test? The only difference should be the long long type size. How does
it affect optimizations?

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[ebotcazou at gcc dot gnu.org]

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

--- Comment #11 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> Is there any reason for ABS_EXPR detection for not working on 64bit target
> for the same test?

It is probably visible in the .original dump.

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[enkovich.gnu at gmail dot com]

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

--- Comment #12 from Ilya Enkovich <enkovich.gnu at gmail dot com> ---
Before your last fix both 32bit and 64bit versions of .original look similar
except a condition. We have (a - b > 0) for 64 bit and (a > b) for 32bit.

64bit version (before and after the patch)

{
  sum = ((int) a - (int) b > 0 ? (long unsigned int) ((int) a - (int) b) :
(long unsigned int) ((int) b - (int) a)) + sum;
  return sum;
}

32bit version (before the patch):

{
  sum = ((int) a > (int) b ? (long unsigned int) ((int) a - (int) b) : (long
unsigned int) ((int) b - (int) a)) + sum;
  return sum;
}

It is not clear why such difference exists though.

[Bug middle-end/61734] [4.10 Regression] Regression in ABS_EXPR recognition

[ebotcazou at gcc dot gnu.org]

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

--- Comment #13 from Eric Botcazou <ebotcazou at gcc dot gnu.org> ---
> Before your last fix both 32bit and 64bit versions of .original look similar
> except a condition. We have (a - b > 0) for 64 bit and (a > b) for 32bit.

That's obsolete though, you should look at what happens after the fix, which
should be equivalent to what happened before r210979.  But the reason is very
likely the cast to (long unsigned int), which can be stripped for 32-bit but
not for 64-bit long ints, which blocks the pattern matching in the latter case.