[fpc-devel] AVR specific RTL routines for div, mod, shl, shr

[Christo Crause]

I have evaluated generated code size for a simple test case.  The
following code is used as template where the variable type and math
operator is adapted for the specific test case::


program test;

var ans, x, d: byte; // or int64, etc.

begin

  x := 127;

  d := 1;

  ans := x div d;  // or shl etc.

end;


With the standard RTL compiled for AVR the generated binary size for
byte div byte is 2258 bytes of which 148 bytes is code for the
algorithm (fpc_div_byte + BSRbyte),
296 bytes of data and 1588 bytes associated with
HandleErrorAddrFrameInd to raise a divide by zero error.  Clearly the
existing error handling code is very bulky

for this particular target and this simple program wouldn't fit on
some of the supported controller such as attiny13 & attiny25.


The binary size for int64 div int64 is 5214 bytes, with the same error
handling overhead as above and a total of 2840 bytes of code for the
actual algorithm
(the generic code pulls in shl, shr and fpc_div_dword).


I've rewritten the routines for div and mod for both unsigned and
signed operands from 8 bits to 64 bits in assembler to minimize code
size.
My starting point for the division algorithm was the restoring
division algorithm as described in wiki and lecture notes from UCLA
(https://www.seas.ucla.edu/~ingrid/ee213a/lectures/division_presentV2.pdf).
I just want to make it clear that this code is not related to the
first patch
 I've submitted in issue 32103 which was based on an application note
from Atmel.

With rewritten assembler routines the size of the binary for byte div
byte drops to 234 bytes and the size of the fpc_div_byte routine is 26
bytes.

With rewritten assembler routines the size of the binary for int64 div
smallint drops to 534 bytes and the size of the fpc_div_int64
(+fpc_div_qword) routine
 is 120 (+176) bytes.


I've also written assembler routines to implement shl/shr for 64 bit operands.

The binary size for int64 shr smallint is 538 bytes of which 306 bytes
is for the fpc_shr_int64 implementation.

Rewritten shl/shr : binary size is 300 bytes and size of fpc_shl_int64
(+fpc_shl_qword) routine is 14 (+54) bytes.


I submit for consideration a zip file containing the following files
(to be extracted into rt/avr folder):

avr.inc - I've added an include directive at the end to include intmath.inc

intmath.inc - 8 - 32 bit routines

int64p.inc - 64 bit routines


I also have a test program that runs several tests but since I use
simavr to run it it is probably not so useful to most people.


Note that the div&mod routines do not include error handling code, I
can add that once a sensible embedded error handling protocol is
decided on.


Best regards,

Christo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20180306/5df220aa/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: avr-rtl.zip
Type: application/zip
Size: 6261 bytes
Desc: not available
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20180306/5df220aa/attachment.zip>