Re: I found a FORTH stack optimzer, but could use a better version.

"Jenny Brien" <jennifer@[EMAIL PROTECTED]
> wrote in message
news:op.t4r035zcaozhuq@[EMAIL PROTECTED]
> On Fri, 11 Jan 2008 08:34:02 -0000, Rod Pemberton
> <do_not_have@[EMAIL PROTECTED]
> wrote:
> > "Jenny Brien" <jennybrien@[EMAIL PROTECTED]
> wrote in message
> >
news:ab815318-9e67-4709-a479-a5fdae1bd429@[EMAIL PROTECTED]
> >> I'm interested in the minimal set needed to implement the normal
Forth
> >> stack operators.
> >
> > Then these might be of use which use rstack:
> >
> I'm thinking more of minimal hardware requirement in terms of registers
> and opcodes. I know that it's /possible/ to do any manipulation with
just
> the two stacks and a single register, but it's not very efficient.
>

What is your background EE or CS, etc.?  Is this for an existing cpu? new
cpu? virtual machine?

> I'm thinking more of minimal hardware requirement in terms of registers
> and opcodes.

What do you have or are considering so far?  I've been mentioning x86
(80486
or later actually) since that's what I'm currently using.  As shown
throughout this thread, some of the FORTH words map directly to the
instructions of x86 which are somewhat "****table", e.g., more RISC like
than
CISC (push,pop,mov).  While others can be built from those, and probably
only a few require the more "non-****table" x86 CISC instructions.

Although I'm mildy familiar with programming in FORTH, I'm by no means a
FORTH programmer.  I know much more about the internals of FORTH than
programming in it - which is why I've kept asking _you_ questions about
used
words, etc...  And, why I'm a bit surprised no one has referred me to the
c.l.f. FAQ.  Anyway, there is much in this thread, and probably other
c.l.f.
posts searchable via Google Groups.

I've mentioned Koopman a few times in this thread, but without indication
of
familiarity or lack of from you.  Are you familiar with FORTH related
works
of Charles Moore, Leo Brodie, Anton Ertl, Brad Rodriquez, Phil Koopman,
Jim
Brooks, Byte magazine articles?  E.g., have you reviewed Charles Moore's
various cpu's such as the F21? Or, his Machine or Color FORTH for his
cpu's?
I'm sure they did much work trying to find the optimal set of registers
needed for FORTH.  They may have even tried to optimize the FORTH words.
What about Phil Koopman's analysis on FORTH instruction usage?  The
dynamic
instruction frequencies, while out of date, should still be somewhat valid
today.  Are you familiar with a basic FORTH virtual machine as presented
by
Brad Rodriquez in "Moving FORTH", e.g., W, IP, PSP, RSP, UP, and/or X,
TOS?
Differences between "threading" types: STC, DTC, ITC, TTC?  I'm familiar
with much of that, but what I learned of it was many years ago... roughly
'88 and '92 - so I've probably forgotten much - perhaps even some things
critical to this discussion...  But, fortunately, almost all of it is
online
today and I can review.  :-)

Some links related to what we've been discussing:

"A STUDY OF FORTH INSTRUCTION FREQUENCIES" in "Stack Computers" by Phil
Koopman
http://www.ece.cmu.edu/~koopman/stack_computers/sec6_3.html

"Stack Computers" main index
http://www.ece.cmu.edu/~koopman/stack_computers/index.html

Chuck Moore's F21 cpu, MachineFORTH et. al...
http://www.ultratechnology.com/

Brad Rodriquez's "Moving FORTH" series on older FORTH implementations.
http://www.zetetics.com/bj/papers/

Jim Brooks "Fig-FORTH internals"
http://www.jimbrooks.org/web/forth/forthInternals.php

> The fastest code needs at least n+1 registers or stacks to re-sort n
> items. If all were are on the hardware stack to begin with then 2SWAP
> would take 8 moves (pop all to registers, push all back in order),
reduced
> to 6 with the top two items cached. Using a second stack instead of
> multiple registers hurts more than I thought at first; using my rcheme I
> cannot implement 2SWAP in fewer than 13 moves.

Is this for an existing cpu?  If not, then you just renumber or reorder
the
registers using electronic circuitry for a SWAP,ROLL,ROT.  You don't have
to
actually move the values around...  If so, then a fast native ROT or ROLL
would help for 2SWAP.

:2SWAP ROT >R ROT R>;
:2SWAP 3 ROLL 3 ROLL;

For ****fting more than just a few stack items on x86, i.e., you need ROLL
or
more than one ROT - like for 2SWAP, you might consider using one of x86's
underused CISC string instructions, rep movsb, instead of a sequence of
push's, pop's, and mov's.  It requires some overhead to setup, so it's
probably not good for smaller moves... i.e., good for n ROLL, if n is
large
enough.


Rod Pemberton