www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 3558] New: Optimizer bug results in false if condition being taken

reply d-bugmail puremagic.com writes:
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



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: -------
Nov 29 2009
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3558


Don <clugdbug yahoo.com.au> changed:

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



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: -------
Nov 30 2009
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3558


Walter Bright <bugzilla digitalmars.com> changed:

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



17:36:08 PST ---
Fixed changeset 272.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 30 2009
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3558




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: -------
Nov 30 2009
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3558




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: -------
Feb 10 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3558


Don <clugdbug yahoo.com.au> changed:

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



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: -------
Feb 11 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3558




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: -------
Feb 12 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3558


Walter Bright <bugzilla digitalmars.com> changed:

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



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: -------
Mar 08 2010