[fpc-devel] Optimization for 'mod'

[J. Gareth Moreton]

Hi Ched,

That optimisation actually already exists, 
as does changing unsigned division by a 
power of two into SHR.

Another optimisation I put in... if you're 
doing x mod a, where a is greater than 
half the maximum value for the word size 
(e.g. $80000000 for 32-bit), then it can 
be changed into what effectively amounts 
to a comparison and a subtraction, 
although I used CMOV to avoid branching.

It also seems that Florian was happy with 
the patch, albeit with a couple of changes 
regarding coding style and an issue with 
register allocation. So a happy ending, I 
think!

Kit

On Fri 05/01/18 10:16 , Ched 
charles.edouard.des.vastes.vignes at gmail.co
m sent:
> 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
> 
> 
__________________________________________
_____
> 
> fpc-devel maillist  -  fpc-
devel at lists.freepascal.org
> http://lists.freepascal.org/cgi-
bin/mailman/listinfo/fpc-devel
> 
> 
> 
>