[Bug tree-optimization/26731] Jump threading gets in the way of loops

[Bug tree-optimization/26731] Jump threading gets in the way of loops

[Joost.VandeVondele at mat dot ethz.ch]

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

Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Joost.VandeVondele at mat dot ethz
                   |                            |.ch

--- Comment #3 from Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> ---
(In reply to Andrew Pinski from comment #0)
> Jump threading causes bad interactions with loops:
> int f(int t, int a, int x)
> {
>   int n, g;
>   if (t)
>    n = a;
>   else
>    n = 4;
>   for (g=0; g<n; g++)
>     x++;
>   return x;
> }
> 
> This should be optimized to:
> int f(int t, int a, int x)
> {
>   int n, g;
>   if (t)
>    n = a;
>   else
>    n = 4;
>   x+=n;
>   return x;
> }
> But is not because of jump threading getting in the way to dect that the
> loop is finite.

actually, it should not, for a<0 and t=1.

[Bug tree-optimization/26731] Jump threading gets in the way of loops

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Indeed x += n needs to be guarded with n > 0 - and we analyze that correctly:

Analyzing # of iterations of loop 1
  exit condition [1, + , 1](no_overflow) < a_10
  bounds on difference of bases: -2147483649 ... 2147483646
  result:
    zero if a_10 <= 0
    # of iterations (unsigned int) a_10 + 4294967295, bounded by 2147483646

but SCEV cprop doesn't handle this as it thinks that

  (x_6(D) + 1) + (a_10 > 0 ? (int) ((unsigned int) a_10 + 4294967295) : 0)

is expensive.

Of course it should have used number_of_iterations_exit instead to be able
to insert the may_be_zero condition properly which its simplistic code
doesn't handle.

Without jump threading the analysis is able to simplify the may_be_zero
condition against the dominating header copy checks.

Thus re-confirmed.

[Bug tree-optimization/26731] Jump threading gets in the way of loops

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
In GCC 9 and above we get:
  _2 = x_6(D) + 1;
  _7 = (unsigned int) n_1;
  _11 = _7 + 4294967295;
  _15 = (int) _11;
  _16 = n_1 > 0 ? _15 : 0;
  x_3 = _2 + _16;

Which is okish, the loop has been removed but the above should be able to
reduce further:
  # RANGE [1, 2147483647] NONZERO 2147483647
  # n_1 = PHI <a_5(D)(3), 4(2)>
  # RANGE [-2147483647, 2147483647]
  _2 = x_6(D) + 1;
  # RANGE [1, 2147483647] NONZERO 2147483647
  _7 = (unsigned int) n_1;
  # RANGE [0, 2147483646] NONZERO 2147483647
  _11 = _7 + 4294967295;
  # RANGE [0, 2147483646] NONZERO 2147483647
  _15 = (intD.9) _11;
  # RANGE [0, 2147483646] NONZERO 2147483647
  _16 = n_1 > 0 ? _15 : 0;
  x_3 = _2 + _16;

The COND_EXPR should just converted into _15 but we don't ...
VRP should have done that ....

[Bug tree-optimization/26731] Jump threading gets in the way of loops

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #5)
> In GCC 9 and above we get:
>   _2 = x_6(D) + 1;
>   _7 = (unsigned int) n_1;
>   _11 = _7 + 4294967295;
>   _15 = (int) _11;
>   _16 = n_1 > 0 ? _15 : 0;
>   x_3 = _2 + _16;
> 
> Which is okish, the loop has been removed but the above should be able to
> reduce further:
>   # RANGE [1, 2147483647] NONZERO 2147483647
>   # n_1 = PHI <a_5(D)(3), 4(2)>
>   # RANGE [-2147483647, 2147483647]
>   _2 = x_6(D) + 1;
>   # RANGE [1, 2147483647] NONZERO 2147483647
>   _7 = (unsigned int) n_1;
>   # RANGE [0, 2147483646] NONZERO 2147483647
>   _11 = _7 + 4294967295;
>   # RANGE [0, 2147483646] NONZERO 2147483647
>   _15 = (intD.9) _11;
>   # RANGE [0, 2147483646] NONZERO 2147483647
>   _16 = n_1 > 0 ? _15 : 0;
>   x_3 = _2 + _16;
> 
> The COND_EXPR should just converted into _15 but we don't ...
> VRP should have done that ....

That was fixed in GCC 13 by not have the COND_EXPR have the comparison in the
first operand (I don't have the revision offhand).

We now get at optimization:
  <bb 2> [local count: 118111600]:
  if (t_4(D) != 0)
    goto <bb 3>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 3> [local count: 59055800]:
  if (a_5(D) > 0)
    goto <bb 4>; [66.92%]
  else
    goto <bb 5>; [33.08%]

  <bb 4> [local count: 105119324]:
  # n_1 = PHI <a_5(D)(3), 4(2)>
  _2 = x_6(D) + 1;
  _11 = (unsigned int) n_1;
  _15 = _11 + 4294967295;
  _16 = (int) _15;
  x_3 = _2 + _16;

  <bb 5> [local count: 118111600]:
  # x_13 = PHI <x_3(4), x_6(D)(3)>
  return x_13;

}

[Bug tree-optimization/26731] Jump threading gets in the way of loops

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=26731
Bug 26731 depends on bug 18940, which changed state.

Bug 18940 Summary: Loop is not vectorized when it should be (VRP)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=18940

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

[Bug tree-optimization/26731] Jump threading gets in the way of loops

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2007-07-01 00:14:40         |2023-8-7

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The last part of the issue here is take:
```
int f1(int i, int n)
{
        int t1 = i + 1;
        unsigned t = n;
        t -= 1;
        t1 = t1 + (int)t;
        return t1;
}
```

This should just be optimized to:
```
int f(int i, int n)
{
  return i + n;
}
```

Note the original f should really transform into:
int f0_(int t, int a, int x)
{
  int n, g;
  if (t)
  {
   n = a;
   if (a <= 0) return x;
  }
  else
   n = 4;
  x+=n;
  return x;
}

[Bug tree-optimization/26731] Jump threading gets in the way of loops

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2006-03-17 20:02 -------
Confirmed.  Though SCEV should be taught to handle this.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2006-03-17 20:02:18
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26731

[Bug tree-optimization/26731] Jump threading gets in the way of loops

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2006-03-17 17:32 -------
I almost think this is also the cause for PR 26727.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |26727
              nThis|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26731