On Mon, Jun 23, 2003, Scott Dattalo wrote:
> On Mon, 23 Jun 2003, Daniel Serpell wrote:
> > source= http://www.piclist.com/postbot.asp?id=piclist\2003\06\20\201728a
>
> This sounds a lot like the Vertical Adder optimizer that I wrote.

Funny, you said the same when I initially put the first version (two
years ago):

On Thu, 17 May 2001, Scott Dattalo wrote:
|
| Did you see the verticle counter optimizer I wrote? It works much like this
| optimizer (in that it's brute force).
|

> (Incidently, there's a new copy, va_optimizer3.c that I just put on the
> web - this version has comments:
>
> http://www.dattalo.com/technical/software/pic/va_optimizer3.c
> )
>
> I don't have time to look closely at your code, but I can add an
> observation or two (and this may be nothing new to you, Daniel). Searching
> *all* instructions is time consuming. For the 6 instruction case, there
> are theoretically (2^14)^6 = 1.9e25.
[...]
> Even so, the total combinations are daunting 32^6 = 1.07 billion.

Well, my program doesn't try all the possible instructions. You give it
hints, and it makes combinations based on instructions and possible
values. An example:

-------------------- adc16.ins -----------------------
name = Add FF + F3 -> FF
output = [
   FF = FF + F3;
   valid FF;
]
tryflags = STATUS.C, STATUS.Z, F3, FF
tryvalues = 1
options = lastnotskip, lastnotwreg, firstnotwreg
------------------------------------------------------

Then, you run it:

------------------------------------------------------
superopt-0.2.2$ time ./superopt samples/adc16.ins
Processing datafile 'samples/adc16.ins'
Name: 'Add FF + F3 -> FF'
STATE: -n 1 -i 0

PICINST=115
Generating CACHE...
Starting BRUTE-FORCE (TM) (115 instrucciones)...
  0) addwf   F1,F           1) addwf   F1,W           2) addwf   F2,F
  3) addwf   F2,W           4) addwf   F3,F           5) addwf   F3,W
  6) andwf   F1,F           7) andwf   F1,W           8) andwf   F2,F
  9) andwf   F2,W          10) andwf   F3,F          11) andwf   F3,W
 12) comf    F1,F          13) comf    F1,W          14) comf    F2,F
 15) comf    F2,W          16) comf    F3,F          17) comf    F3,W
 18) decf    F1,F          19) decf    F1,W          20) decf    F2,F
 21) decf    F2,W          22) decf    F3,F          23) decf    F3,W
 24) incf    F1,F          25) incf    F1,W          26) incf    F2,F
 27) incf    F2,W          28) incf    F3,F          29) incf    F3,W
 30) iorwf   F1,F          31) iorwf   F1,W          32) iorwf   F2,F
 33) iorwf   F2,W          34) iorwf   F3,F          35) iorwf   F3,W
 36) movf    F1,F          37) movf    F1,W          38) movf    F2,F
 39) movf    F2,W          40) movf    F3,F          41) movf    F3,W
 42) rlf     F1,F          43) rlf     F1,W          44) rlf     F2,F
 45) rlf     F2,W          46) rlf     F3,F          47) rlf     F3,W
 48) rrf     F1,F          49) rrf     F1,W          50) rrf     F2,F
 51) rrf     F2,W          52) rrf     F3,F          53) rrf     F3,W
 54) subwf   F1,F          55) subwf   F1,W          56) subwf   F2,F
 57) subwf   F2,W          58) subwf   F3,F          59) subwf   F3,W
 60) swapf   F1,F          61) swapf   F1,W          62) swapf   F2,F
 63) swapf   F2,W          64) swapf   F3,F          65) swapf   F3,W
 66) xorwf   F1,F          67) xorwf   F1,W          68) xorwf   F2,F
 69) xorwf   F2,W          70) xorwf   F3,F          71) xorwf   F3,W
 72) clrf    F1,F          73) clrf    F1,W          74) clrf    F2,F
 75) clrf    F2,W          76) clrf    F3,F          77) clrf    F3,W
 78) decfsz  F1,F          79) decfsz  F1,W          80) decfsz  F2,F
 81) decfsz  F2,W          82) decfsz  F3,F          83) decfsz  F3,W
 84) incfsz  F1,F          85) incfsz  F1,W          86) incfsz  F2,F
 87) incfsz  F2,W          88) incfsz  F3,F          89) incfsz  F3,W
 90) bcf     STATUS,C      91) bcf     STATUS,Z      92) bsf     STATUS,C
 93) bsf     STATUS,Z      94) btfsc   STATUS,C      95) btfsc   STATUS,Z
 96) btfss   STATUS,C      97) btfss   STATUS,Z      98) addlw   0x01
 99) andlw   0x01         100) iorlw   0x01         101) movlw   0x01
102) sublw   0x01         103) xorlw   0x01         104) movwf   F1
105) movwf   F2           106) movwf   F3           107) goto    *+2
108) goto    *+3          109) goto    *+4          110) goto    *+5
111) goto    *+6          112) goto    *+7          113) goto    *+8
114) goto    *+9

Searching on secuences of lenght 1
Searching on secuences of lenght 2
STATE: -n 2 -i 0,0

Searching on secuences of lenght 3
STATE: -n 3 -i 0,0,0

Searching on secuences of lenght 4091
STATE: -n 4 -i 0,0,0,0

It:35028394 STATE: -n 4 -i 041,000,094,026
        movf    F3,W
        addwf   F1,F
        btfsc   STATUS,C
        incf    F2,F

Searching on secuences of lenght 55,103,106
STATE: -n 5 -i 0,0,0,0,0

Exiting...
Last searched state: -n 5 -i 0,0,0,0,0


real    0m30.768s
user    0m29.550s
sys     0m0.070s
------------------------------------------------------

So, it's not that slow. As you see, in that example, the search
is restricted to 115 instructions. But, not each combination is
tried, the flags give it hints that the last inst. can't write to
thw W register not be a skip instruction and that the first
instruction can't read from the W register. Also, the goto's aren't
tried it they point out of the code.

Total number of combinations visited is is about 175 million.
(the test is in a 1GHz Duron). As you see, it's not much slower than
your vertical adder optimizer ;-)


> Another observation is that 'if' statements waste time in brute force
> optimizers. Many free simulators I've seen perform a brute force decoding
> of the instruction opcode.
[... snip ...]
>

Well, you actually described my program :-). Yes, all that optimizations
are already performed, but I think that more optimizations are stil
possible.

    Daniel.

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email listserv@mitvma.mit.edu with SET PICList DIGEST in the body