[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [avr-gcc-list] Small super-optimizer results
From: |
Bob Paddock |
Subject: |
Re: [avr-gcc-list] Small super-optimizer results |
Date: |
Mon, 11 Jul 2011 15:40:04 -0400 |
On Mon, Jul 11, 2011 at 2:02 PM, Paulo Marques <address@hidden> wrote:
> Some time ago I toyed with trying to build a super-optimizer for the
> avr. The project didn't went very far, but it produced a few small bits
> of code that I think are worth sharing.
>
> Basically I was trying to produce functions to multiply an 8 bit value
> by 8 bit constants with a 16 bit result in avr families without a mul
> instruction.
Your results looked similar to what I've seen out of the
"star-chain" multiplication routine from Doctor Dobb's Journal #125, March 1987.
[The old multiplication one is not on line, but the newer division one
is, with broken formatting:
http://drdobbs.com/high-performance-computing/184408499 ]
Curious if you were doing the some thing similar?
> multiply x129:
> MOV r2, r0
> ADD r0, r0
> ADC r1, r2
> ROR r1
> ROR r0
[Output from the 'starchain.exe' I hacked together long ago:]
/* The factors of 129 are: 3 43 */
Star-Chain Multiply of 129:
/* Multiplier = 129 */
Rw = R1 = /* Your Multiplicand */
Rw <<= 7;
Rw += R1;
Star-Chain Division by 129:
R1 = /* Your divisor */
Rw = R1;
Rw <<= 7;
Rw -= R1;
Rw <<= 2;
Rw += 511;
Rw >>= 16;
> multiply x254
> NEG r0
> SBC r1, r0
> SBC r0, r1
> SBC r1, r2
/* The factors of 254 are: 2 127 */
Star-Chain Multiply of 254:
/* Multiplier = 254 */
Rw = R1 = /* Your Multiplicand */
Rw <<= 7;
Rw -= R1;
Rw <<= 1;
Star-Chain Division by 254:
R1 = /* Your divisor */
R1 >>= 1;
Rw = R1;
Rw <<= 7;
Rw += R1;
Rw <<= 2;
Rw += 519;
Rw >>= 16;
> multiply x255
> NEG r0
> SBC r1, r0
/* The factors of 255 are: 3 5 17 */
Star-Chain Multiply of 255:
/* Multiplier = 255 */
Rw = R1 = /* Your Multiplicand */
Rw <<= 8;
Rw -= R1;
Star-Chain Division by 255:
R1 = /* Your divisor */
Rw = R1;
Rw <<= 8;
Rw += R1;
Rw += 257;
Rw >>= 16;