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

           Summary: Optimizer bug results in false if condition being
                    taken
           Product: D
           Version: unspecified
          Platform: x86
        OS/Version: Linux
            Status: NEW
          Severity: critical
          Priority: P2
         Component: DMD
        AssignedTo: nobody@puremagic.com
        ReportedBy: janzert@janzert.com


--- Comment #0 from Janzert <janzert@janzert.com> 2009-11-29 05:28:04 PST ---
I've been chasing a bug for a few days and finally have it narrowed down to the following example. Basically a condition that should evaluate to false is taken anyway.

The printf line below should never be executed, but it is if compiled under linux with "dmd -release -O -inline badbranch.d".

I first started chasing this while using 1.043 but have since upgraded to 1.052 and still see it. Not surprisingly I also see it with phobos or tango. It has also been reported to behave the same with 2.034.

badbranch.d:

extern(C) int printf(char*, ...);

struct Container
{
    ulong[2] bits = [0UL, 1];
}

int called(ulong value)
{
    value = value * 3;
    return value;
}

int test(Container* c, int[] shift)
{
    int count = 0;
    if (c.bits[0])
        count = 1;
    count |= called(c.bits[1]) << shift[0];
    // This is always false, but is taken anyway.
    if (c.bits[0])
        printf("Impossible output %lld\n", c.bits[0]);

    return count;
}

int main(char[][] args)
{
    int[] shift = [0];
    Container c;
    return test(&c, shift);
}

-- 
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=3558


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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug@yahoo.com.au


--- Comment #1 from Don <clugdbug@yahoo.com.au> 2009-11-30 17:15:12 PST ---
Reduced test case only requires -O. It's a bit peculiar.

int main()
{
    long[1] c = [0]; // must be long

    int [1] d = [1];
    int k = 0;
    if (!d[0])
       k = 1;
    k = d[0] + k + k;

    if (c[0]) assert(c[0]);

    return k;
}

-- 
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=3558


Walter Bright <bugzilla@digitalmars.com> changed:

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


--- Comment #2 from Walter Bright <bugzilla@digitalmars.com> 2009-11-30 17:36:08 PST ---
Fixed changeset 272.

-- 
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=3558



--- Comment #3 from Walter Bright <bugzilla@digitalmars.com> 2009-11-30 17:39:13 PST ---
Oops, I meant 3521 was fixed!

-- 
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=3558



--- Comment #4 from Don <clugdbug@yahoo.com.au> 2010-02-10 01:25:37 PST ---
Test case for DMC 8.42n. Hits the breakpoint when compiled with -O.
=======================================
const static int d[1] = {1};
const static long long c[1] = {0};

void crash()
{
  _asm  int 3;
}
int main()
{
    int k = 1;
    if (d[0])
       k = 0;
    k = 2*d[0] + k;
    if (c[0]) crash();
    return k;
}
=======================================

-- 
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=3558


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

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


--- Comment #5 from Don <clugdbug@yahoo.com.au> 2010-02-11 14:24:13 PST ---
This was hard to track down! I had to delve into most of the back-end to work out what's going on here. As usual with these nightmare bugs, the fix is simple:

PATCH: cod1.c, loaddata(), line 3365.

    else if (sz == 8)
    {   code *c1;
        int i;

        c = allocreg(&regm,&reg,TYoffset);    /* get a register */
        i = sz - REGSIZE;
        ce = loadea(e,&cs,0x8B,reg,i,0,0);    /* MOV reg,data+6 */
        if (tyfloating(tym))        // TYdouble or TYdouble_alias
        gen2(ce,0xD1,modregrm(3,4,reg));    // SHL reg,1
        c = cat(c,ce);

        while ((i -= REGSIZE) >= 0)
        {
        c1 = loadea(e,&cs,0x0B,reg,i,regm,0);    // OR reg,data+i
+        if (i == 0)
+            c1->Iflags |= CFpsw;   // We need the flags
        c = cat(c,c1);
        }
    }
    else if (sz == LNGDBLSIZE)            // TYldouble

ROOT CAUSE:
A condition of the form 'if (x)', where x is long or ulong, is coded as:  asm {
mov reg, low_dword; OR reg, high_dword; } But, the code needs to mark the flags
as needing to be preserved. (CFpsw, I have no idea what that stands for!).
Then, later on, in cgsched.c, the Pentium scheduler thinks it can move this
instruction behind other flag-modifying instructions, and it wants to do that
in this case in order to do instruction pairing for the U and V pipes.

In the original test case, there's an ADD which gets moved after the OR. Then, the branch instruction which follows this gets the flags from the ADD instead of the OR, and so it branches incorrectly. The bug is only manifested in weird cases where pairing opportunities arise, so it is extremely fragile. It's not really an optimiser bug, but it only happens when there are pairing advantages when instructions are moved around, which only happens when many registers are being used and modified, and this in turn only happens when variables are in registers.

BTW: This bug probably also affects the 16-bit C compiler in the 4-byte int case; the flags aren't marked as required for any of the comparisons.

That's a long explanation, but it took me ages to track this down. I think I need a beer.

-- 
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=3558



--- Comment #6 from Janzert <janzert@janzert.com> 2010-02-12 02:35:40 PST ---
Wow, that's amazing that you were able and persistent enough to track that down. Thanks for finding the cause. Hopefully it can be applied and make it into a release quickly.

-- 
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=3558


Walter Bright <bugzilla@digitalmars.com> changed:

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


--- Comment #7 from Walter Bright <bugzilla@digitalmars.com> 2010-03-08 22:21:27 PST ---
Fixed dmd 1.057 and 2.041

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