Skip to content

[x86 / AArch64 / PowerPC 64] Bug fix to integer division reciprocal algorithm

J. Gareth "Kit" Moreton requested to merge CuriousKit/optimisations:i39834 into main

Summary

This merge request fixes a subtle bug in the calc_divconst_magic_signed function that was the cause of incorrect quotients first identified in #39834 (closed). The calculated magic number was not sign-extended to the size of aint; if the target size was less than the CPU word size (the size of aint), this would cause the compiler to execute incorrect logic.

For example, when calculating a signed divisor of +60 for 32-bit on x86_64, the calculated magic number is $88888889, which is correct, but internally this gets stored as $00000000 88888889 instead of $FFFFFFFF 88888889. When a later condition checks to see if this value is negative, it fails ($88888889 represents a negative number under signed 32-bit logic).

System

  • Processor architecture: i386, x86_64, AArch64, PowerPC 64

What is the current bug behavior?

The following short program produces an incorrect quotient (it should return 100):

program DivTest;

function fquotient(a, b: integer): integer; inline;
begin
  result := a div b;
end;

procedure test;
var seconds, min: integer;
begin
  seconds := 3600 + 60 * 40 + 52;
  min      := fquotient(seconds, 60);
  WriteLn(min);
end;

begin
  test;
end.

Replacing fquotient(seconds, 60); with seconds div 60 produces the correct quotient of 100.

What is the behavior after applying this patch?

The above program should output 100 as expected.

Additional Notes

AArch64 and PowerPC 64 have not been directly tested, but these platforms are known to use calc_divconst_magic_signed so it stands to reason that this bug exists on those platforms in some form.

Additionally, presumably due to blindly copying and converting C code, the calc_divconst_magic_signed contained an assert statement. This is inconsistent with code semantics within the compiler (it is the only assert to exist). An additional commit replaces this with an internal error.

Edited by J. Gareth "Kit" Moreton

Merge request reports