[fpc-devel] Optimization for 'mod'

[J. Gareth Moreton]

Hi everyone,

During my exploration of FPC, I noticed that the 'mod' operator is not optimized in the same way 'div' is.  
Though not deeply tested on other platforms yet, I have developed a patch for 3.1.1 that implements the 
algorithm that calculates a reciprocal constant for unsigned 'mod' operations with a constant denominator.  
Just my little contribution to the compiler - I hope it is sound.

https://bugs.freepascal.org/view.php?id=32945

I attached a couple of test projects that contain numerous 32-bit constants (testfile2.pp) and 64-bit 
constants (testfile3.pp) and a means to output timing metrics.  A sample of such is shown in the bug report.

Note that I unfortunately made a slight mistake that I only noticed after uploading the patch. The line:

m := qword(-aint(d)); { Two's complement of d }

...should be...

m := aword(-aint(d)); { Two's complement of d }


NOTE: One of the optimised algorithms, specifically for 32-bit divisors greater than $80000000, makes use of 
CMOV to avoid jumps.  If CMOV is not available (it checks "CPUX86_HAS_CMOV in 
cpu_capabilities[current_settings.cputype]"), then the code will fall back to the default 'mod' 
implementation that was already present.

I should note that there's still a lot of room for improvement.  For example, code such as this:

Minutes := t div 60;
Seconds := t mod 60;

... is badly optimised, because the division is calculated twice (without the patch, 't div 60' uses a 
reciprocal constant, while 't mod 60' just uses 'DIV'), whereas, ideally, it should only be calculated once 
since the numerator and denominator are the same... either a single call to DIV, or calculating the quotient 
via the reciprocal multiplication method, then obtaining the remainder by multiplying the quotient by the 
original denominator (60 in this case) and subtracting the product from the original numerator.

Gareth aka. Kit