Re: [avr-gcc-list] Small super-optimizer results

[Paulo Marques]

Georg-Johann Lay wrote:
> Paulo Marques schrieb:
>> [...]
>> I've attached the output of the optimizer. The R1 register is assumed to
>> have zero when starting and R0 has the value to be shifted. As you can
>> see many of the 81 sequences are equivalent.
> 
> Hi Paulo.

Hi, Georg.

> Thanks for the enthusiastic digging :-)

No problem. I'm always curious about what the optimizer will be able to
do to solve a small problem like this one.

> There are weird sequences like
> 
>   SWAP R0
>   ADD R0 R0
>   ADC R0 R1
>   ADC R0 R0
>   ADC R0 R1
> 
> that use knowledge that C=0 in the second ADC. Thus it's just an obfuscated
> version of the next alternative:

Actually, the way the optimizer works, it doesn't use that knowledge
explicitly.

The first version of the optimizer was based on avrtest and was simply a
brute-force approach:

 - generate all possible combinations of N instructions
 - for each combination:
   - for all possible initial states
     - load the initial state into the registers
     - use avrtest to execute the instructions
     - get the final state and check if it is the expected result for
the operation.
     - if the final state is wrong, proceed to the next combination
     - if it is right, proceed to the next state
   - if all states were good, this is a good sequence: print it

In this case, to check the rotation, the initial states are all numbers
from 0x00 to 0xFF loaded into R0, the final state should be that number
rotated by 2 bits in R0 also.

This version was very slow (as it is expected from this description), so
a few tweaks had to be implemented (but there is still room for
improvement):

 - if after one instruction we reach a state that is the same as some
previous state, we don't need to test any further because this sequence
is clearly not optimal

 - try to propagate some "useful bits" information, so that if at some
point you have less bits than what you need to make it work, this
sequence will never be good

This last tweak is more cumbersome, but basically works like this: in
your example you start with 8 useful bits. If the optimizer is testing a
sequence that does something like LSR R0, LSR R0, it now has only 7
useful bits. No matter what instructions it tests next it will never be
able to produce the 8-bit result needed, and a complete testing branch
is discarded early this way.

>   SWAP R0
>   ADD R0 R0
>   ADC R0 R1
>   ADD R0 R0
>   ADC R0 R1
> 
> There are quite some different ways of doing the rotate because rotates are
> commutative.

There sure are...

> Do you use BLD and BST?

I wasn't using, but I added them now and it still can't find a 4
instruction sequence to do the 2 bit rotation...

Also I'm still not using MUL because my initial goal was to find small
instruction sequnces to do multiplications by constants that could be
used on AVR's without MUL instruction. But I can add it to the set of
allowed instructions, if you think that is worth it...

I couldn't resist: I turned on the MUL variants (MUL, MULS, FMUL, etc.)
too and the optimizer found a bunch of 3 instruction variants that are
basically like your version, because the optimizer doesn't do the final
"MOV  R,R0" like in your code. No 2 instruction sequence, though :(

>> If you want me to try different problems, just let me know. I'm always
>> curious about what kind of weird sequences the optimizer will produce :)
> 
> I am preparing a patch for avr-gcc that introduces rotate patterns.
> For the 8-bit rotate I found the 5-insn sequence, but for some reason I though
> there should be a shorter one.  Like: "it cannot be that hard to rotate an
> 8-bit value right by 2..." and remembered your post here.

If you want to try some other rotate patterns let me know, but I guess
the other trivial rotations don't look so bad like the 2 and 6 bit ones...

-- 
Paulo Marques
Software Development Department - Grupo PIE, S.A.
Phone: +351 252 290600, Fax: +351 252 290601
Web: www.grupopie.com

"There cannot be a crisis today; my schedule is already full."