[Bug tree-optimization/108757] New: We do not simplify (a - (N*M)) / N + M -> a / N

[Bug tree-optimization/108757] New: We do not simplify (a - (N*M)) / N + M -> a / N

[bergner at gcc dot gnu.org]

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

            Bug ID: 108757
           Summary: We do not simplify (a - (N*M)) / N + M -> a / N
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: bergner at gcc dot gnu.org
  Target Milestone: ---

The Eigen project code has a missed optimization that basically simplifies down
to the following test case:

linux$ cat bug.c 
#define N 32
#define M 2

unsigned long int
foo (unsigned long int a)
{
  return (a - (N*M)) / N + M;
}

linux$ gcc -O2 -S bug.c 

linux$ cat bug.s 
foo:
        addi 3,3,-64
        srdi 3,3,5
        addi 3,3,2
        blr

We should be able to simplify this down to just 'a / N', which for power-of-2
N, results in just the srdi...although, I don't think N is required to be a
power-of-2 to fold this down to just 'a / N'.  Can we also simplify this for
non-constant N & M?  Maybe under -fast-math or something similar?

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[bergner at gcc dot gnu.org]

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

Peter Bergner <bergner at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-02-10
                 CC|                            |chip.kerchner at ibm dot com
             Target|                            |powerpc64le-linux
             Status|UNCONFIRMED                 |NEW

--- Comment #1 from Peter Bergner <bergner at gcc dot gnu.org> ---
Reported by our Eigen developers and confirmed by me.

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I am not sure this can be done in the normal case unless you know the range of
a to be [64...INF] .
The wrap around case might be an issue ...
But I am not 100% sure.

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[anlauf at gcc dot gnu.org]

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

--- Comment #3 from anlauf at gcc dot gnu.org ---
(In reply to Andrew Pinski from comment #2)
> I am not sure this can be done in the normal case unless you know the range
> of a to be [64...INF] .
> The wrap around case might be an issue ...
> But I am not 100% sure.

It is.  Just print foo(0).

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[segher at gcc dot gnu.org]

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

Segher Boessenkool <segher at gcc dot gnu.org> changed:

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

--- Comment #4 from Segher Boessenkool <segher at gcc dot gnu.org> ---
If N is a power of two optimising this to a/N is valid, but for other values
of N it is not (division is not the inverse of multiplication in C).  It also
only works for unsigned of course.

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[bergner at gcc dot gnu.org]

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

--- Comment #5 from Peter Bergner <bergner at gcc dot gnu.org> ---
(In reply to Segher Boessenkool from comment #4)
> If N is a power of two optimising this to a/N is valid, but for other values
> of N it is not (division is not the inverse of multiplication in C).  It also
> only works for unsigned of course.

Isn't this valid for any N & M, such that M is a factor of N?  Meaning, as long
as N / M has no remainder, it seems like this should be ok.  For example, N =
30 & M = 2 should be just as ok as the N = 32 & M = 2 case, correct?

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[segher at gcc dot gnu.org]

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

--- Comment #6 from Segher Boessenkool <segher at gcc dot gnu.org> ---
No?  Take a=59 as counterexample:

(a - (N*M)) / N + M = (59 - 2*30)/30 + 2 = ~0UL/30 + 2

but

a / N = 59/30 = 1

Integer division in C is division towards zero, almost no normal algebraic
simplifications apply there.

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[bergner at gcc dot gnu.org]

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

--- Comment #7 from Peter Bergner <bergner at gcc dot gnu.org> ---
(In reply to Segher Boessenkool from comment #6)
> No?  Take a=59 as counterexample:
> 
> (a - (N*M)) / N + M = (59 - 2*30)/30 + 2 = ~0UL/30 + 2

For unsigned integers, isn't having a < N*M UB so we're free to do as we wish
for either the optimized and non-optimized sequences?  Meaning, can't we assume
here that a >= N*M?

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[segher at gcc dot gnu.org]

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

--- Comment #8 from Segher Boessenkool <segher at gcc dot gnu.org> ---
No, addition and subtraction are well defined for all inputs, for unsigned
integers.

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[chip.kerchner at ibm dot com]

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

--- Comment #9 from Chip Kerchner <chip.kerchner at ibm dot com> ---
Doesn't this work for powers of two (N) and signed values (for A, N and M)?

(59 - (33 * -2)) / -2 + 31 = -62 + 31 = -29

and

59 / -2 = -29

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[chip.kerchner at ibm dot com]

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

--- Comment #10 from Chip Kerchner <chip.kerchner at ibm dot com> ---
Oops that should be 31 * -2, not 33.

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[chip.kerchner at ibm dot com]

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

--- Comment #11 from Chip Kerchner <chip.kerchner at ibm dot com> ---
Nevermind, using a similar example that Segher gave, it would failed too.

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[chip.kerchner at ibm dot com]

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

--- Comment #12 from Chip Kerchner <chip.kerchner at ibm dot com> ---
Here is an example of the original problem

#define EIGEN_ALWAYS_INLINE __attribute__((always_inline)) inline

typedef __vector float Packet4f;
typedef size_t Index;

EIGEN_ALWAYS_INLINE Packet4f ploadu(const float* from)
{
  return vec_xl(0, const_cast<float*>(from));
}

EIGEN_ALWAYS_INLINE void pstoreu(float* to, const Packet4f &from)
{
  vec_xst(from, 0, to);
}

void convert(Index rows, float*src, float *result)
{
  for(Index i = 0; i + 4 <= rows; i+=4) {
    Packet4f r32_0 = ploadu(src + i +  0);
    pstoreu(result + i +  0, r32_0);
  }
}

And the output (with notation on the lines in question)

    cmpldi 0,3,3
    blelr 0
    addi 3,3,-4  <- i = rows - 4
    li 9,0
    srdi 3,3,2   <- i >>= 2
    addi 8,3,1   <- i = i + 1
    andi. 7,8,0x3
    mr 10,8
    beq 0,.L10
    cmpdi 0,7,1
    beq 0,.L14
    cmpdi 0,7,2
    beq 0,.L15
    lxv 0,0(4)
    mr 8,3
    li 9,16
    stxv 0,0(5)
.L15:
    lxvx 0,4,9
    addi 8,8,-1
    stxvx 0,5,9
    addi 9,9,16
.L14:
    lxvx 0,4,9
    cmpdi 0,8,1
    stxvx 0,5,9
    addi 9,9,16
    beqlr 0
.L10:
    srdi 10,10,2
    mtctr 10
.L3:
    lxvx 0,4,9
    addi 10,9,16
    addi 7,9,32
    addi 8,9,48
    stxvx 0,5,9
    lxvx 0,4,10
    addi 9,9,64
    stxvx 0,5,10
    lxvx 0,4,7
    stxvx 0,5,7
    lxvx 0,4,8
    stxvx 0,5,8
    bdnz .L3
    blr

In this case the 3 lines notated can be replaced a simple `srdi 8,3,2`

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[pinskia at gcc dot gnu.org]

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

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
IIRC this is a doloop issue and has been reported before. Maybe even by myself
while I was working at Sony. I think I tried to fix it too.

[Bug rtl-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=37451
          Component|tree-optimization           |rtl-optimization

--- Comment #14 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Oh yes pr 37451 . There are a few other related ones referenced now too. But
basically it is doloop which is introducing this.
The original example does not correspond to the example in given by the eigen
folks either..

[Bug rtl-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[chip.kerchner at ibm dot com]

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

--- Comment #15 from Chip Kerchner <chip.kerchner at ibm dot com> ---
How about this (from Peter's testcase)?  Does it still have issues?  It
produces the same assembly.

#define N 32
#define M 2

unsigned long int
foo (unsigned long int a)
{
  return (a - (N*M)) / N + M;
}

[Bug rtl-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[chip.kerchner at ibm dot com]

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

--- Comment #16 from Chip Kerchner <chip.kerchner at ibm dot com> ---
Dang copy and paste issue...  This is what I meant.

unsigned long int
foo (unsigned long int a)
{
  return (a + (N*M)) / N - M;
}

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|rtl-optimization            |tree-optimization

--- Comment #17 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
  _13 = rows_8(D) + 18446744073709551612;
  _15 = _13 >> 2;
  doloop.8_5 = _15 + 1;


This is what IV-OPTS produces.

Reduced testcase:
typedef __SIZE_TYPE__ size_t;

void convert(size_t rows, float*src, float *result)
{
  for(size_t i = 0; i + 4 <= rows; i+=4) {
    float t = src[i];
    result[i] = t;
  }
}

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|powerpc64le-linux           |powerpc64le-linux,
                   |                            |aarch64-*-*

--- Comment #18 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note this shows up on aarch64 too with my reduced testcase.

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[pinskia at gcc dot gnu.org]

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

--- Comment #19 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note in the loop case we know it does not wrap because there is a check
already:
  <bb 2> [local count: 118111600]:
  if (rows_8(D) > 3)
    goto <bb 5>; [89.00%]
  else
    goto <bb 4>; [11.00%]

  <bb 5> [local count: 105119324]:
  _13 = rows_8(D) + 18446744073709551612;
  _15 = _13 / 4;
  doloop.6_5 = _15 + 1;

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[guojiufu at gcc dot gnu.org]

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

Jiu Fu Guo <guojiufu at gcc dot gnu.org> changed:

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

--- Comment #20 from Jiu Fu Guo <guojiufu at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #19)
> Note in the loop case we know it does not wrap because there is a check
> already:
>   <bb 2> [local count: 118111600]:
>   if (rows_8(D) > 3)
>     goto <bb 5>; [89.00%]
>   else
>     goto <bb 4>; [11.00%]
> 
>   <bb 5> [local count: 105119324]:
>   _13 = rows_8(D) + 18446744073709551612;
>   _15 = _13 / 4;
>   doloop.6_5 = _15 + 1;

Checking why below code does not work:
/* Simplify ((t + -N*M) / N + M) -> t / N: (t + -C) >> N + (C>>N) ==> t >> N */
(for div (trunc_div round_div)
 (simplify
  (plus (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3)
  (if (ANY_INTEGRAL_TYPE_P (type) &&
       (wi::to_wide (@3) << wi::to_wide (@2)) == -wi::to_wide (@1))
   (if (TYPE_OVERFLOW_UNDEFINED (type))
    (div @0 @2)
#if GIMPLE
    (with
     {
       bool overflowed = true;
       value_range vr0;
       if (INTEGRAL_TYPE_P (type)
           && get_global_range_query ()->range_of_expr (vr0, @0)
           && !vr0.varying_p () && !vr0.undefined_p ())
         {
           wide_int wmin0 = vr0.lower_bound ();
           wide_int wmax0 = vr0.upper_bound ();
           wide_int w1 = -wi::to_wide (@1);
           wi::overflow_type min_ovf, max_ovf;
           wi::add (wmin0, w1, TYPE_SIGN (type), &min_ovf);
           wi::add (wmax0, w1, TYPE_SIGN (type), &max_ovf);
           if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
             overflowed = false;
         }
     }
    (if (!overflowed)
     (div @0 @2)))
#endif
   ))))


Interesting thing:
the VR is always VR_VARYING, even for the below simple case:

typedef unsigned long INT;
INT __attribute__ ((noinline)) foo (INT x)
{
  if (x < 4)
    return 0;
  INT a = x + 18446744073709551612ULL;
  INT b = a >> 2;
  return b + 1;
}

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[pinskia at gcc dot gnu.org]

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

--- Comment #21 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Jiu Fu Guo from comment #20)
> Interesting thing:
> the VR is always VR_VARYING, even for the below simple case:
> 
> typedef unsigned long INT;
> INT __attribute__ ((noinline)) foo (INT x)
> {
>   if (x < 4)
>     return 0;
>   INT a = x + 18446744073709551612ULL;
>   INT b = a >> 2;
>   return b + 1;
> }

Yes that is because x does not have a "global" range.

You could try the following testcase:
```
typedef unsigned long INT;
INT __attribute__ ((noinline)) foo (INT x)
{
  if (x < 4)
    __builtin_unreachable();
  INT a = x + 18446744073709551612ULL;
  INT b = a >> 2;
  return b + 1;
}
```

Which gets a (global) range for x_1(D) during forwprop3:
  # RANGE [irange] INT [4, +INF]
  INTD.2750 x_1(D) = xD.2751;

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[guojiufu at gcc dot gnu.org]

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

--- Comment #22 from Jiu Fu Guo <guojiufu at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #21)
> (In reply to Jiu Fu Guo from comment #20)
> > Interesting thing:
> > the VR is always VR_VARYING, even for the below simple case:
> > 
> > typedef unsigned long INT;
> > INT __attribute__ ((noinline)) foo (INT x)
> > {
> >   if (x < 4)
> >     return 0;
> >   INT a = x + 18446744073709551612ULL;
> >   INT b = a >> 2;
> >   return b + 1;
> > }
> 
> Yes that is because x does not have a "global" range.

I also tried "get_range_query (cfun)->range_of_expr (vr0, @0)", 
> 
> You could try the following testcase:
> ```
> typedef unsigned long INT;
> INT __attribute__ ((noinline)) foo (INT x)
> {
>   if (x < 4)
>     __builtin_unreachable();
>   INT a = x + 18446744073709551612ULL;
>   INT b = a >> 2;
>   return b + 1;
> }
> ```
> 
> Which gets a (global) range for x_1(D) during forwprop3:
>   # RANGE [irange] INT [4, +INF]
>   INTD.2750 x_1(D) = xD.2751;

(In reply to Andrew Pinski from comment #21)
> (In reply to Jiu Fu Guo from comment #20)
> > Interesting thing:
> > the VR is always VR_VARYING, even for the below simple case:
> > 
> > typedef unsigned long INT;
> > INT __attribute__ ((noinline)) foo (INT x)
> > {
> >   if (x < 4)
> >     return 0;
> >   INT a = x + 18446744073709551612ULL;
> >   INT b = a >> 2;
> >   return b + 1;
> > }
> 
> Yes that is because x does not have a "global" range.
> 
> You could try the following testcase:
> ```
> typedef unsigned long INT;
> INT __attribute__ ((noinline)) foo (INT x)
> {
>   if (x < 4)
>     __builtin_unreachable();
>   INT a = x + 18446744073709551612ULL;
>   INT b = a >> 2;
>   return b + 1;
> }
> ```
> 
> Which gets a (global) range for x_1(D) during forwprop3:
>   # RANGE [irange] INT [4, +INF]
>   INTD.2750 x_1(D) = xD.2751;

Thanks so much!
"get_range_query (cfun)->range_of_expr (vr0, @0)" works for both the case!

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[guojiufu at gcc dot gnu.org]

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

--- Comment #23 from Jiu Fu Guo <guojiufu at gcc dot gnu.org> ---
/* Simplify ((t + -N*M) / N + M) -> t / N: (t + -C) >> N + (C>>N) ==> t >> N */
(for div (trunc_div exact_div)
 (simplify
  (plus (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3)
  (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type) &&
       (wi::to_wide (@3) << wi::to_wide (@2)) == -wi::to_wide (@1))
   (if (TYPE_OVERFLOW_UNDEFINED (type))
    (div @0 @2)
#if GIMPLE
    (with
     {
       bool overflowed = true;
       value_range vr0;
       if (get_range_query (cfun)->range_of_expr (vr0, @0)
           && !vr0.varying_p () && !vr0.undefined_p ())
         {
           wide_int wmin0 = vr0.lower_bound ();
           wide_int wmax0 = vr0.upper_bound ();
           wide_int w1 = -wi::to_wide (@1);
           wi::overflow_type min_ovf, max_ovf;
           wi::sub (wmin0, w1, TYPE_SIGN (type), &min_ovf);
           wi::sub (wmax0, w1, TYPE_SIGN (type), &max_ovf);
           if (min_ovf == wi::OVF_NONE && max_ovf == wi::OVF_NONE)
             overflowed = false;
         }
     }
    (if (!overflowed)
     (rshift @0 @2)))
#endif
   ))))

Got one match for the case.
Checking if it is safe(condition) or how to support other forms:
signed type, negative N, non-power2 N, negative M ...

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[guojiufu at gcc dot gnu.org]

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

--- Comment #24 from Jiu Fu Guo <guojiufu at gcc dot gnu.org> ---
(In reply to Jiu Fu Guo from comment #23)
> /* Simplify ((t + -N*M) / N + M) -> t / N: (t + -C) >> N + (C>>N) ==> t >> N
> */
> (for div (trunc_div exact_div)
div was not used in this matcher, yet.  Here rshift is used:  t/(1<<N) could be
optimized to "t>>N".

>  (simplify
>   (plus (rshift (plus @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3)
>   (if (INTEGRAL_TYPE_P (type) && TYPE_UNSIGNED (type) &&
>        (wi::to_wide (@3) << wi::to_wide (@2)) == -wi::to_wide (@1))
>    (if (TYPE_OVERFLOW_UNDEFINED (type))
>     (div @0 @2)
This should be "(rshift @0 @2)", otherwise it will be error if relax
"TYPE_UNSIGNED (type)"

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[cvs-commit at gcc dot gnu.org]

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

--- Comment #25 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jiu Fu Guo <guojiufu@gcc.gnu.org>:

https://gcc.gnu.org/g:1aceceb1e2d6e86ce183c8cc448750fa03b6f79e

commit r14-3644-g1aceceb1e2d6e86ce183c8cc448750fa03b6f79e
Author: Jiufu Guo <guojiufu@linux.ibm.com>
Date:   Mon Sep 4 10:31:04 2023 +0800

    Optimize '(X - N * M) / N' to 'X / N - M' if valid

    Integer expression "(X - N * M) / N" can be optimized to "X / N - M" with
    the below conditions:
    1. There is no wrap/overflow/underflow.
       wrap/overflow/underflow breaks the arithmetic operation.
    2. "X - N * M" and "X" are not of opposite sign.
       Here, the operation "/" would be "trunc_div", the fractional part is
       discarded. If "X - N * M" and "X" are in different signs, then trunc_div
       discards the fractional parts (of /N) in different directions.

            PR tree-optimization/108757

    gcc/ChangeLog:

            * match.pd ((X - N * M) / N): New pattern.
            ((X + N * M) / N): New pattern.
            ((X + C) div_rshift N): New pattern.

    gcc/testsuite/ChangeLog:

            * gcc.dg/pr108757-1.c: New test.
            * gcc.dg/pr108757-2.c: New test.
            * gcc.dg/pr108757.h: New test.

[Bug tree-optimization/108757] We do not simplify (a - (N*M)) / N + M -> a / N

[guojiufu at gcc dot gnu.org]

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

Jiu Fu Guo <guojiufu at gcc dot gnu.org> changed:

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

--- Comment #26 from Jiu Fu Guo <guojiufu at gcc dot gnu.org> ---
Patch was committed.