http://d.puremagic.com/issues/show_bug.cgi?id=5294

           Summary: loop optimization (-O) gone crazy
           Product: D
           Version: unspecified
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Severity: blocker
          Priority: P2
         Component: DMD
        AssignedTo: nobody@puremagic.com
        ReportedBy: spam@extrawurst.org


--- Comment #0 from Stephan Dilly <spam@extrawurst.org> 2010-12-01 03:30:24 PST ---
void cpv(float x)
{}

void main(){

    int cnt;

    for(int i=0; i<30; i++)
    {
        cnt++;
        cpv(i*60 - 100); // comment this out and it makes 30 loops
    }

    writefln("%s",cnt); // compile with -O and it prints 1
}

tested with dmd2.050 using -O for optimization.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5294


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs@eml.cc


--- Comment #1 from bearophile_hugs@eml.cc 2010-12-01 12:47:01 PST ---
Reduced a little:


import core.stdc.stdio: printf;
void foo(int) {}
void main() {
    int count;
    for (int i = 0; i < 2; i++) {
        count++;
        foo(i * 5 - 6); // comment this out and it makes 2 loops
    }
    printf("%d\n", count); // compile with -O and it prints 1
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5294


Don <clugdbug@yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug@yahoo.com.au
            Version|unspecified                 |D1 & D2


--- Comment #2 from Don <clugdbug@yahoo.com.au> 2010-12-01 16:26:06 PST ---
Applies to all D1 and D2, even prehistoric versions (tested as far back as
DMD0.140).

Very weird. In bearophile's test case, written as

    for (int i = 0; i < A; i++) {
        count++;
        foo(i * 5 - B); // comment this out and it makes 2 loops
    }

it fails for B = (5+1)..(5*A) inclusive (eg, 6, 7, 8, 9, 10 all fail for A==2).

And if it is foo(i*6 - B), it fails for B= 7..6*A.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5294



--- Comment #3 from Stephan Dilly <spam@extrawurst.org> 2010-12-01 16:49:47 PST ---
i get the feeling #5100 is related to this.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5294



--- Comment #4 from Stephan Dilly <spam@extrawurst.org> 2010-12-01 16:50:40 PST ---
(In reply to comment #3)
> i get the feeling #5100 is related to this.

for the lazy #5100 is http://d.puremagic.com/issues/show_bug.cgi?id=5100

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5294



--- Comment #5 from bearophile_hugs@eml.cc 2010-12-06 03:15:42 PST ---
Automatic fuzzy testing like this one allows to discover compiler bugs like that:

http://gcc.gnu.org/wiki/summit2010?action=AttachFile&do=view&target=regehr_gcc_summit_2010.pdf

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5294



--- Comment #6 from Stephan Dilly <spam@extrawurst.org> 2010-12-06 03:32:26 PST ---
(In reply to comment #5)
> Automatic fuzzy testing like this

kidding me ? I wish it would have been found by any test, it appeared in an actual project. while i converted some C code to D i wondered a lot until i finally reduced it to this testcase.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5294



--- Comment #7 from Don <clugdbug@yahoo.com.au> 2010-12-06 11:53:27 PST ---
Bearophile -- That's an interesting link. Currently, DMD back-end bugs are being found at the rate of about 3 per year. So yes, fuzzy testing of DMC could probably flush out some backend bugs a bit faster.
-------------------

Here's what's happening. First, in this code:

    for (int i = 0; i < 10; i++) {
        foo(i * 5 - 6);
    }
it sees that i and 10 are always >=0, so the signed comparison "i < 10" is
replaced with an unsigned one. (This happens in the backend in constprop() ).
Then, while dealing with loop invariants, it rewrites the loop into:

for (int _i2 = -6; _i2 < 10*5 - 6; _i2 += 5)
{
  foo(_i2);
}

Fine. Except that it had changed the comparison into an unsigned one!
Particularly interesting is the case where the call is foo(i*5-50);
Then, the loop becomes:
for (int _i2 = -50; _i2 < 0; _i2 += 5)

Since an unsigned value is NEVER less than zero, it just drops the loop completely!

Nasty.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5294


Walter Bright <bugzilla@digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bugzilla@digitalmars.com


--- Comment #8 from Walter Bright <bugzilla@digitalmars.com> 2010-12-06 22:41:10 PST ---
For optimizer spelunkers, if you compile dmd with debug on, and compile with:

  -O --c

you'll get reports of the various optimizations done.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=5294


Walter Bright <bugzilla@digitalmars.com> changed:

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


--- Comment #9 from Walter Bright <bugzilla@digitalmars.com> 2010-12-07 17:08:55 PST ---
http://www.dsource.org/projects/dmd/changeset/792

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------