Целочисленное переполнение при умножении - ошибка компилятора?

Question

Рассмотрим следующий код, который является наивным способом генерации целочисленного идентификатора на основе текущего времени, где Result равно Int64:

  dtRef  := Now;

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

Например, сгенерированный сегодня идентификатор дает 20190503163412142 (<2 ^ 55), что находится в пределах диапазона Int64 (2 ^ 63 - 1).</p>

Однако это дает целочисленное переполнение как в Берлине, так и в Рио.Он компилируется в:

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

В первом умножении используется _llmulo (64-разрядное умножение со знаком, с проверкой переполнения), в то время как во втором используется обычный mul.Ниже приведено второе умножение, которое я прокомментировал:

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!)

Я думал, что флаг переполнения установлен на _llmulo из-за этого сообщения об ошибке о проблемах с _llmulo (есть такжекомментарий к источнику о том, что проверка переполнения не работает).

Однако при отладке флаг переполнения фактически устанавливается после mul!Согласно Руководству Intel :

Флаги OF и CF устанавливаются в 0, если верхняя половина результата равна 0;в противном случае они устанавливаются на 1.

В этом случае EDX равно 0x2A05F200, а EAX равно 0x00000001 после mul, поэтому кажется, что флаг OF должен быть установленв самом деле.Вопрос в том, правильна ли здесь mul?Это проблема с компилятором или проблема с моим кодом?

Я заметил, что если я приписываю результат MonthOf и т. Д. Переменным Int64 до умножения на 1000 ..., все умножения выполняются с использованием _llmulo и работает нормально.

Answer 1

Вывод OF / CF

mul не означает переполнения 64-битного результата; это невозможно. Это означает, что результат не помещается в нижние 32, что может быть полезно для кода, использующего результат, который имеет особый случай, который быстрее для чисел, которые помещаются в один регистр. Если 32-битный mul выдает edx=0x2A05F200, то да, верхняя половина не равна нулю, поэтому CF = OF = 1 является правильным. (Кстати, https://www.felixcloutier.com/x86/mul содержит HTML-выдержки из тома 2 в формате Intel).

---

Если Delphi похож на C, 100000000000 уже является Int64, потому что он слишком большой, чтобы поместиться в 32-разрядное целое число. Таким образом, компилятор выполняет 64x64 => 64-битное умножение, проверяя переполнение 64-битного результата.

Но 1000000000 вмещает в 32-разрядное целое число, поэтому ваш источник выполняет 32 × 32 => 32-разрядное умножение , а компилятор - правильно проверка на переполнение 32-битного результата перед повышением этого 32-битного результата до 64 для добавления с другим 64-битным результатом.

Я заметил, что если я приписываю результат MonthOf и т. Д. Переменным Int64 до умножения на 1000 ..., все умножения выполняются с использованием _llmulo, и это прекрасно работает.

Ну, это пропущенная оптимизация, может быть, с включенной оптимизацией компилятор заметит, что он может на самом деле упростить последующие умножения 64x64 => 64 на 32x32 => 64, используя только mul или imul, потому что входные данные известны быть узким.

---

Компиляторы C делают эту оптимизацию, например, ( на Годболте )

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

Сначала я подумал, что это ошибка компилятора, о которой я сообщил:

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

Система .__ llmulo возвращает неправильный флаг переполнения

Но это, очевидно, не та ошибка (ни ошибка, которую вы обнаружили в QC, для Delphi 7, которая была исправлена ​​в Delphi 2005). В любом случае, эта ошибка была исправлена ​​в Delphi 10.2 Tokyo.

Если вы хотите избежать переполнения при умножении, тогда приведите константы к Int64. Это автоматически расширит другой операнд до Int64, гарантируя, что весь промежуточный результат будет 64-битным:

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

Для более старых версий Delphi также следует отключить проверку переполнения:

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