[fpc-devel] Optimization for 'mod'

[Ched]

Hi,

I haven't done the check if already implemented, but there are some interesting optimisations possible like:
if a is a non-negative integer and t is a non-negative integer power of two, then
    a mod t
can be translated at compile time to
    a and (t-1)

Cheers, Ched'




Le 05.01.2018 à 04:32, J. Gareth Moreton a écrit :
> 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