[Bug optimization/10520] induction variable analysis not used to eliminate comparisons

[Bug optimization/10520] induction variable analysis not used to eliminate comparisons

[dhazeghi@yahoo.com]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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


dhazeghi@yahoo.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
  GCC build triplet|                            |i686-pc-linux-gnu
   GCC host triplet|                            |i686-pc-linux-gnu
 GCC target triplet|                            |i686-linux-pc-gnu


------- Additional Comments From dhazeghi@yahoo.com  2003-06-04 19:18 -------
Hello,

to be able to reproduce this problem, we need a _complete_ testcase, ie code that will compile 
directly. Also you don't specify what options beside -march=pentium4 you use. Could you please 
attach a self-contained testcase, and describe what, if any, other gcc options you used to compile 
this? Note that if you didn't use any options besides -march=pentium4, you are getting 
_extremely_ unoptimized code. Thanks,

Dara



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug optimization/10520] induction variable analysis not used to eliminate comparisons

[pinskia@physics.uc.edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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


pinskia@physics.uc.edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2003-06-04 19:34:14
               date|                            |


------- Additional Comments From pinskia@physics.uc.edu  2003-06-04 19:34 -------
Acutally this problem is know and I can reproduce it with the sample provided (just made it into a 
function):

void f(unsigned int _tmp0, int* buf_fast )
{
unsigned int n_in=0;
unsigned int n_out=0;
unsigned int n_in1=1;
unsigned int n_out1=1;
for(0;((n_in < _tmp0  && n_out < _tmp0) && n_in1 < _tmp0) && n_out1 < _tmp0;(((((n_in 
+=4,n_out +=2)),n_in1 +=4)),n_out1 +=2)){
  buf_fast[(int)n_out]=buf_fast[(int)n_in];
  buf_fast[(int)n_out1]=buf_fast[(int)n_in1];
}
}

Even the tree-ssa branch does not fix this problem



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.

[Bug optimization/10520] induction variable analysis not used to eliminate comparisons

[pinskia at physics dot uc dot edu]

PLEASE REPLY TO gcc-bugzilla@gcc.gnu.org ONLY, *NOT* gcc-bugs@gcc.gnu.org.

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


pinskia at physics dot uc dot edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
   Last reconfirmed|2003-06-04 19:34:14         |2003-08-03 18:34:50
               date|                            |

[Bug tree-optimization/10520] induction variable analysis not used to eliminate comparisons

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-08-09 02:07 -------
There is some hope for this to be done as there is some code on the LNO branch to do it but it is not 
fully done yet.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|rtl-optimization            |tree-optimization
   Last reconfirmed|2004-05-10 16:38:29         |2004-08-09 02:07:55
               date|                            |


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

[Bug tree-optimization/10520] induction variable analysis not used to eliminate comparisons

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=108841

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #6)
> Also? To simplify things a little more?

I filed PR 108841 for that.

[Bug tree-optimization/10520] induction variable analysis not used to eliminate comparisons

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Hmm, shouldn't we convert:
  _24 = MAX_EXPR <n_in_31, n_out_32>;
  if (_24 < _tmp0_27(D))
    goto <bb 4>; [94.50%]
  else
    goto <bb 5>; [5.50%]

  <bb 4> [local count: 906139990]:
  _25 = MAX_EXPR <n_in1_33, n_out1_34>;
  if (_25 < _tmp0_27(D))
    goto <bb 3>; [94.50%]
  else
    goto <bb 5>; [5.50%]
Which is:

if (MAX_EXPR <n_in_31, n_out_32> < _tmp0_27 && MAX_EXPR <n_in1_33, n_out1_34> <
_tmp0_27) goto 3 else goto 5

Into:
if (MAX_EXPR<MAX_EXPR <n_in_31, n_out_32>, MAX_EXPR <n_in1_33, n_out1_34> > <
_tmp0_27)  goto 3 else goto 5

Also? To simplify things a little more?

[Bug tree-optimization/10520] induction variable analysis not used to eliminate comparisons

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Here is the current IR at optimized:
  <bb 3> [local count: 958878296]:
  # n_in_42 = PHI <n_in_31(4), 0(2)>
  # n_out_43 = PHI <n_out_32(4), 0(2)>
  # n_in1_44 = PHI <n_in1_33(4), 1(2)>
  # n_out1_45 = PHI <n_out1_34(4), 1(2)>
  n_in.0_1 = (int) n_in_42;
  _3 = n_in.0_1 w* 4;
  _4 = buf_fast_28(D) + _3;
  n_out.1_5 = (int) n_out_43;
  _7 = n_out.1_5 w* 4;
  _8 = buf_fast_28(D) + _7;
  _9 = *_4;
  *_8 = _9;
  n_in1.2_10 = (int) n_in1_44;
  _12 = n_in1.2_10 w* 4;
  _13 = buf_fast_28(D) + _12;
  n_out1.3_14 = (int) n_out1_45;
  _16 = n_out1.3_14 w* 4;
  _17 = buf_fast_28(D) + _16;
  _18 = *_13;
  *_17 = _18;
  n_in_31 = n_in_42 + 4;
  n_out_32 = n_out_43 + 2;
  n_in1_33 = n_in1_44 + 4;
  n_out1_34 = n_out1_45 + 2;
  _24 = MAX_EXPR <n_in_31, n_out_32>;
  if (_24 < _tmp0_27(D))
    goto <bb 4>; [94.50%]
  else
    goto <bb 5>; [5.50%]

  <bb 4> [local count: 906139990]:
  _25 = MAX_EXPR <n_in1_33, n_out1_34>;
  if (_25 < _tmp0_27(D))
    goto <bb 3>; [94.50%]
  else
    goto <bb 5>; [5.50%]


We should figure out that:
  _24 = MAX_EXPR <n_in_31, n_out_32>;

Is just as n_in_31 is being incremented by 4 each time through the loop while
n_out_32 only by 2
_24 = n_in_31

And:
  _25 = MAX_EXPR <n_in1_33, n_out1_34>;

Is just (same logic as above)
_25 = n_in1_33

And then we have:
  if (n_in_31 < _tmp0_27(D))
    goto <bb 4>; [94.50%]
  else
    goto <bb 5>; [5.50%]

  <bb 4> [local count: 906139990]:
  if (n_in1_33 < _tmp0_27(D))
    goto <bb 3>; [94.50%]
  else
    goto <bb 5>; [5.50%]

Where n_in1_33 = n_in_31+1
There for we should reduce it to just:
  <bb 4> [local count: 906139990]:
  if (n_in1_33 < _tmp0_27(D))
    goto <bb 3>; [94.50%]
  else
    goto <bb 5>; [5.50%]

(hopefully I did this correctly).
Of course this depends on if they are not going to be overflowed .... Which we
know they won't because they are being used for pointer accesses.

[Bug tree-optimization/10520] induction variable analysis not used to eliminate comparisons

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
First of all number-of-iteration analysis would need to figure out that
the vars don't overflow ... (thus that the loop terminates).  It cannot
even compute the number of iterations symbolically.