www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 4506] New: -O flag breaks some recursive functions.

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4506

           Summary: -O flag breaks some recursive functions.
           Product: D
           Version: D2
          Platform: x86_64
        OS/Version: Mac OS X
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: peter.alexander.au gmail.com


--- Comment #0 from Peter Alexander <peter.alexander.au gmail.com> 2010-07-25
08:29:05 PDT ---
I wrote a function to count integer partitions. When compiled with dmd test.d,
I get the correct result. Adding the -O flag makes the program return the
incorrect result:

import std.stdio;

auto P(int n)
{
    if (n < 0) return 0;
    if (n == 0) return 1;

    int c = 1;
    int r = 0;
    for (int k = 1; k <= n; ++k)
    {
        r += c * (P(n-k*(3*k-1)/2) + P(n-k*(3*k+1)/2));
        c *= -1;
    }
    return r;
}

void main()
{
    writeln(P(10));
}

$ dmd test.d
$ ./test
42
$ dmd -O test.d
$ ./test
138

Unfortunately I haven't been able find a more minimal reproduction case. In
particular, a basic recursive Fibonacci function works fine in both cases.

Using dmd 2.047 on Mac OS X Snow Leopard.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4506


bearophile_hugs eml.cc changed:

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


--- Comment #1 from bearophile_hugs eml.cc 2010-07-25 09:31:29 PDT ---
This is very ugly. A reduced test case:

void main() {
    int c = 1;
    for (int k = 0; k < 2; k++) {
        assert((k == 0 && c == 1) || (k == 1 && c == -1));
        c *= -1;
    }
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4506



--- Comment #2 from bearophile_hugs eml.cc 2010-07-25 09:33:40 PDT ---
Normal compilation:

__Dmain    comdat
    assume    CS:__Dmain
L0:        enter    8,0
        mov    dword ptr -8[EBP],1
        mov    dword ptr -4[EBP],0
L12:        cmp    dword ptr -4[EBP],2
        jge    L42
        cmp    dword ptr -4[EBP],0
        jne    L24
        cmp    dword ptr -8[EBP],1
        je    L3A
L24:        cmp    dword ptr -4[EBP],1
        jne    L30
        cmp    dword ptr -8[EBP],0FFFFFFFFh
        je    L3A
L30:        mov    EAX,4
        call    near ptr _D4test8__assertFiZv
L3A:        neg    dword ptr -8[EBP]
        inc    dword ptr -4[EBP]
        jmp short    L12
L42:        xor    EAX,EAX
        leave
        ret
__Dmain    ends
_D4test8__assertFiZv    comdat
    assume    CS:_D4test8__assertFiZv
L0:        enter    4,0
        push    EAX
        mov    ECX,offset FLAT:_D4test12__ModuleInfoZ
        push    ECX
        call    near ptr __d_assertm
        leave
        ret



With -O:

__Dmain    comdat
    assume    CS:__Dmain
L0:        push    EAX
        push    EBX
        xor    EBX,EBX
        push    ESI
        mov    ESI,1
LA:        test    EBX,EBX
        je    L18
        mov    EAX,4
        call    near ptr _D4test8__assertFiZv
L18:        neg    ESI
        inc    EBX
        cmp    EBX,2
        jb    LA
        pop    ESI
        xor    EAX,EAX
        pop    EBX
        pop    ECX
        ret
__Dmain    ends
_D4test8__assertFiZv    comdat
    assume    CS:_D4test8__assertFiZv
L0:        push    EAX
        mov    ECX,offset FLAT:_D4test12__ModuleInfoZ
        push    EAX
        push    ECX
        call    near ptr __d_assertm
        pop    EAX
        ret

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4506


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
                 CC|                            |clugdbug yahoo.com.au
           Platform|x86_64                      |All
            Version|D2                          |D1 & D2
            Summary|-O flag breaks some         |Regression(2.034): -O flag
                   |recursive functions.        |breaks some recursive
                   |                            |functions.
         OS/Version|Mac OS X                    |All
           Severity|normal                      |regression


--- Comment #3 from Don <clugdbug yahoo.com.au> 2010-07-25 11:06:14 PDT ---
Great work, bearophile! This worked on 2.032, fails on 2.034 and later. Fails
on D1 as well. This bug goes to the top of the list.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4506


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch


--- Comment #4 from Don <clugdbug yahoo.com.au> 2010-07-25 15:29:54 PDT ---
A one-line change in 2.034 which caused the regression. I think it's because
c *= -1; becomes NEGATE c, which isn't a binary operation. Here's a patch which
undoes the change. I'm not sure which bug it was attempting to fix.

gother.c, line 480, inside chkprop().

        if (d->Eoper == OPasm)          /* OPasm elems ruin everything  */
            goto noprop;
-        if (OTassign(d->Eoper) && EBIN(d))      // if assignment elem
+        if (OTassign(d->Eoper))      // if assignment elem
        {   elem *t = Elvalue(d);

            if (t->Eoper == OPvar)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=4506


Walter Bright <bugzilla digitalmars.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |bugzilla digitalmars.com
         Resolution|                            |FIXED


--- Comment #5 from Walter Bright <bugzilla digitalmars.com> 2010-07-25
22:39:40 PDT ---
http://www.dsource.org/projects/dmd/changeset/588

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