[Bug tree-optimization/17116] New: Missed optimization with loop and % (or ands)

[Bug tree-optimization/17116] New: Missed optimization with loop and % (or ands)

[pinskia at gcc dot gnu dot org]

main()
{
  int  i;
  for (i=0; i < 90; i++)
  {
    if (i%2)
        puts("hello");
  }
}

We get the following thing from .vars:
<bb 0>:
  i = 0;

<L0>:;
  if ((i & 1) != 0) goto <L1>; else goto <L2>;

when we should get:
<bb 0>:
  i = 0;
  goto <L2>;

<L0>:;
  if ((i & 1) != 0) goto <L1>; else goto <L2>;

Or we could just divide 90 by 2.

-- 
           Summary: Missed optimization with loop and % (or ands)
           Product: gcc
           Version: 3.5.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/17116] Missed jump threading/bypassing optimization with loop and % (or ands)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-08-23 04:51 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-08-23 04:51:16
               date|                            |
            Summary|Missed optimization with    |Missed jump
                   |loop and % (or ands)        |threading/bypassing
                   |                            |optimization with loop and %
                   |                            |(or ands)


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

[Bug tree-optimization/17116] Missed jump threading/bypassing optimization with loop and % (or ands)

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-08-23 10:28 -------
IMHO this is not a bug, but a feature.  Jump threading here
would create a loop with two entries, which would make it impossible
for loop optimizers to work with it.

-- 


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

[Bug tree-optimization/17116] Missed jump threading/bypassing optimization with loop and % (or ands)

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-08-23 10:29 -------
Aaargh... sorry, I am of course wrong, since the loop still has one exit.  I 
think the "do not thread over loop header" restriction could be lifted in this 
case quite easily.

-- 


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

[Bug tree-optimization/17116] Missed jump threading/bypassing optimization with loop and % (or ands)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-02-14 20:35 -------
Actually, if the jump threader code really did its job right it would just
emit 45 calls to puts ("hello") since we've got a series of cascading jump
threads here.

As it stands now, the first DOM pass threads the initial loop test, effectively
turning the loop into a "do ... while" loop.

The second DOM pass then comes along and threads the i%2 test for the first
iteration of the loop -- in effect peeling the first iteration of the loop --
which effectively turns the loop back into a while ... do loop (with one
less iteration than before).

The third iteration of DOM threads the initial loop test again which turns the
loop back into a do ... while loop.

Clearly if this contined, we'd just keep peeling off iterations until we had 45
calls to puts ("hello") and a loop which did nothing (which would then be removed).

So I think the real question is do we want DOM's jump threader to peel
off all the iterations or not :-)




-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com


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

[Bug tree-optimization/17116] Missed jump threading/bypassing optimization with loop and % (or ands)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-01 16:29 -------
We now get:
main ()
{
  int i.8;
  int i;

<bb 0>:
Invalid sum of outgoing probabilities 0.0%
  i = 0;
  i.8 = i + 1;

Invalid sum of outgoing probabilities 98.9%
<L0>:;
  if ((i.8 & 1) != 0) goto <L1>; else goto <L10>;

<L1>:;
  puts (&"hello"[0]);

Invalid sum of incoming frequencies 9813, should be 10000
<L10>:;
  i.8 = i.8 + 1;
  if (i.8 != 90) goto <L0>; else goto <L4>;

<L4>:;
  return;

}



-- 


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

[Bug tree-optimization/17116] Missed jump threading/bypassing optimization with loop and % (or ands)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-05-02 16:46 -------
Subject: Re:  Missed jump threading/bypassing
	optimization with loop and % (or ands)

On Sun, 2005-05-01 at 16:29 +0000, pinskia at gcc dot gnu dot org wrote:
> ------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-01 16:29 -------
> We now get:
> main ()
> {
>   int i.8;
>   int i;
> 
> <bb 0>:
> Invalid sum of outgoing probabilities 0.0%
>   i = 0;
>   i.8 = i + 1;
> 
> Invalid sum of outgoing probabilities 98.9%
> <L0>:;
>   if ((i.8 & 1) != 0) goto <L1>; else goto <L10>;
> 
> <L1>:;
>   puts (&"hello"[0]);
> 
> Invalid sum of incoming frequencies 9813, should be 10000
> <L10>:;
>   i.8 = i.8 + 1;
>   if (i.8 != 90) goto <L0>; else goto <L4>;
> 
> <L4>:;
>   return;
> 
> }
Right.  I mentioned earlier that what we need to figure out whether
or not we want to allow the threader to keep threading the loop backedge
over and over and over.

Conceptually we should since potentially it makes the whole loop go
away.  The problem is that doing so can result in a huge compile-time
explosion.  I've got some ideas to deal with the compile-time explosion
but I haven't tested them yet.

Jeff




-- 


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

[Bug tree-optimization/17116] Missed jump threading/bypassing optimization with loop and % (or ands)

[steven at gcc dot gnu dot org]

------- Comment #8 from steven at gcc dot gnu dot org  2008-11-22 11:45 -------
I don't think anyone is interested in fixing this -> WONTFIX.


-- 

steven at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/17116] Missed jump threading/bypassing optimization with loop and % (or ands)

[law at redhat dot com]

------- Comment #7 from law at redhat dot com  2007-03-29 23:18 -------
Subject: Re:  Missed jump threading/bypassing
        optimization with loop and % (or ands)

IMHO, this PR should simply be closed.

This is a case where aggressive threading is going to explode codesize
with  marginal benefits.

Jeff


-- 


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