Integer overflow on multiplication - compiler bug?

Question

Consider the following code, which is a naive way of generating an integer identifier based on the current time, where Result is Int64:

  dtRef  := Now;

  Result := YearOf(dtRef)   * 100000000000 +
            MonthOf(dtRef)  * 1000000000   +
            DayOf(dtRef)    * 10000000     +
            HourOf(dtRef)   * 100000       +
            MinuteOf(dtRef) * 1000         +
            SecondOf(dtRef) * 10           +
            m_nLastTaskID;

For instance, an ID generated today gives 20190503163412142 (< 2^55), which is well within range of Int64 (2^63 - 1).

However, this gives an integer overflow on both Berlin and Rio. It compiles to:

MyUnitU.pas.580: Result := YearOf(dtRef)   * 100000000000 +
007BCEAE 6A17             push $17
007BCEB0 6800E87648       push $4876e800
007BCEB5 FF75EC           push dword ptr [ebp-$14]
007BCEB8 FF75E8           push dword ptr [ebp-$18]
007BCEBB E84CF2D3FF       call YearOf
007BCEC0 0FB7C0           movzx eax,ax
007BCEC3 33D2             xor edx,edx
007BCEC5 E8FA0AC5FF       call @_llmulo
007BCECA 7105             jno $007bced1
007BCECC E83FC7C4FF       call @IntOver
007BCED1 52               push edx
007BCED2 50               push eax
007BCED3 FF75EC           push dword ptr [ebp-$14]
007BCED6 FF75E8           push dword ptr [ebp-$18]
007BCED9 E852F2D3FF       call MonthOf
007BCEDE 0FB7C0           movzx eax,ax
007BCEE1 BA00CA9A3B       mov edx,$3b9aca00
007BCEE6 F7E2             mul edx
007BCEE8 7105             jno $007bceef
007BCEEA E821C7C4FF       call @IntOver

The first multiplication uses _llmulo (64-bit signed multiply, with overflow check), whereas the second uses plain mul. Below is the second multiplication commented by me:

007BCED9 E852F2D3FF       call MonthOf       // Put the month (word) on AX
007BCEDE 0FB7C0           movzx eax,ax       // EAX <- AX as a double word
007BCEE1 BA00CA9A3B       mov edx,$3b9aca00  // EDX <- 1000000000
007BCEE6 F7E2             mul edx            // EDX:EAX <- EAX * EDX
007BCEE8 7105             jno $007bceef      // Jump if overflow flag not set
007BCEEA E821C7C4FF       call @IntOver      // Called (overflow flag set!)

I thought the overflow flag was being set on _llmulo because of this bug report on problems with _llmulo (there's also a comment on the source stating that overflow checking is not working).

However, when debugging the overflow flag is actually set after mul! According to Intel's manual:

The OF and CF flags are set to 0 if the upper half of the result is 0; otherwise, they are set to 1.

In this case EDX is 0x2A05F200 and EAX is 0x00000001 after mul, so it seems the OF flag should have been set indeed. The question is, is mul correct here? Is this a problem with the compiler or a problem with my code?

I noticed that if I attribute the result of MonthOf etc to Int64 variables before multiplying by 1000..., all multiplications are done using _llmulo and it works fine.

Answer 1

mul's OF/CF output doesn't mean overflow of the 64-bit result; that's impossible. It means the result didn't fit in the low 32, which might be useful for code using the result that has a special case that's faster for numbers that fit in one register. If 32-bit mul produces edx=0x2A05F200 , then yes, the upper half is non-zero so CF=OF=1 is correct. (BTW, https://www.felixcloutier.com/x86/mul has HTML extracts of Intel's vol.2 PDF).

---

If Delphi is anything like C, 100000000000 is already an Int64 because it's too big to fit in a 32-bit integer. So the compiler does 64x64 => 64-bit multiplication, checking for overflow of the 64-bit result.

But 1000000000 does fit in a 32-bit integer, so your source is doing a 32 x 32 => 32-bit multiply, and the compiler is correctly checking for overflow of the 32-bit result before promoting that 32-bit result to 64 for addition with the other 64-bit result.

I noticed that if I attribute the result of MonthOf etc to Int64 variables before multiplying by 1000..., all multiplications are done using _llmulo and it works fine.

Well that's a missed optimization, maybe with optimization enabled the compiler will notice that it can actually simplify the later 64x64 => 64 multiplies into 32x32 => 64 using just mul or imul, because the inputs are known to be narrow.

---

C compilers do this optimization, e.g. (on Godbolt)

uint64_t foo_widen(uint32_t a, uint32_t b) {
    return a * (uint64_t)b;
}

# gcc9.1 -m32 -O3
foo_widen:
    mov     eax, DWORD PTR [esp+8]    # load 2nd arg
    mul     DWORD PTR [esp+4]         # multiply into EDX:EAX return value
    ret

Answer 2

I also first thought it was this compiler bug reported by me:

https://quality.embarcadero.com/browse/RSP-16617

System.__llmulo returns wrong overflow flag

But this is obviously not that bug (nor the bug you found on QC, for Delphi 7, which was fixed in Delphi 2005). Anyway, that bug was fixed in Delphi 10.2 Tokyo.

If you want to avoid the overflow on the multiplication, then cast the constants to Int64. This will automatically widen the other operand to Int64 too, ensuring that the entire intermediate result will be 64 bit:

Result := YearOf(dtRef)  * Int64(100000000000) + 
          MonthOf(dtRef) * Int64(10000000000) +
          etc...

For older versions of Delphi, you should also turn off overflow checks:

{$UNDEF OVFL} 
...
{$IFOPT Q+} {$DEFINE OVFL} {$Q-} {$ENDIF}
Result := YearOf(dtRef)  * Int64(100000000000) + 
          MonthOf(dtRef) * Int64(10000000000) +
          etc...
{$IFDEF OVFL} {$Q+} {$UNDEF OVFL} {$ENDIF}