• d-bugmail puremagic.com (59/59) Jan 14 2019 https://issues.dlang.org/show_bug.cgi?id=19584

d-bugmail puremagic.com writes:

https://issues.dlang.org/show_bug.cgi?id=19584

          Issue ID: 19584
           Summary: Illegal optimization: Shift-or -> imul
           Product: D
           Version: D2
          Hardware: x86_64
                OS: Windows
            Status: NEW
          Severity: major
          Priority: P1
         Component: dmd
          Assignee: nobody puremagic.com
          Reporter: voidstar gmx.com

$ dmd --help | head -1
DMD32 D Compiler v2.084.0

$ cat test.d
ulong interleave(uint x, uint y) pure {

    ulong expand(uint a) pure {
            ulong x = a;
            x = ((x << 16) | x) & 0x0000ffff0000ffffuL;
            x = ((x <<  8) | x) & 0x00ff00ff00ff00ffuL;
            x = ((x <<  4) | x) & 0x0f0f0f0f0f0f0f0fuL;
            x = ((x <<  2) | x) & 0x3333333333333333uL;
            x = ((x <<  1) | x) & 0x5555555555555555uL;
            return x;
    }

    auto x2 = expand(x);
    auto y2 = expand(y);
    assert(!(x2 & (y2 << 1)));
    return x2 + (y2 << 1);
}



void main(string[] args) {
        import std.conv, std.stdio;
        writeln(interleave(to!uint(args[1]), to!uint(args[2])));
}



$ rdmd -O test.d 711 31
264515

$ rdmd test.d 711 31
283327

Oops.

Then:
$ dmd -g -O test.d

Objdump shows:
  4022a3:       56                      push   %esi
  4022a4:       57                      push   %edi
  4022a5:       69 ca 01 00 01 00       imul   $0x10001,%edx,%ecx
  4022ab:       ba 01 00 01 00          mov    $0x10001,%edx
  4022b0:       f7 e2                   mul    %edx
  4022b2:       03 d1                   add    %ecx,%edx
  4022b4:       81 e2 ff ff 00 00       and    $0xffff,%edx

Using imul here to implement '(x << 16) | x' isn't right, because x might be >
16-bits.

The -m64 build shows a similar output.

(Similar argument for the other imuls to implement the other (x << y) | x
operations).

You can also see this on an older compiler version with Compiler Explorer:
https://godbolt.org/z/cWBV_z


ldc & gdc do not seem to have this bug.

--