Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: "Rod Pemberton" Newsgroups: comp.lang.forth Subject: Re: Static Single Assignment form to Stack allocation Date: Sat, 07 Feb 2015 21:04:07 -0500 Organization: Aioe.org NNTP Server Lines: 119 Message-ID: References: <82c4c3dc-7692-4d03-a447-9bdd54ff9387@googlegroups.com> <2015Feb6.142225@mips.complang.tuwien.ac.at> <26b59aed-f1a6-4ccb-90ad-69c36b1abb89@googlegroups.com> <45da3660-ad44-4d81-9142-e8582e5d66d2@googlegroups.com> <2fWdnbgKv_RXH0vJnZ2dnUU7-TGdnZ2d@supernews.com> <9b851120-bcf2-41ba-851a-49dcf5654736@googlegroups.com> NNTP-Posting-Host: n4wpt9zq8xR26Ttf9mo2BA.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: Opera Mail/12.16 (Linux) X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.lang.forth:36377 On Sat, 07 Feb 2015 17:51:57 -0500, Aliaksei Chapyzhenka wrote: > : SWAP OVER >R >R DROP R> R> ; This is probably not what you want. OVER usually requires more code in assembly than other operations. I.e., you've slowed down SWAP by using OVER and made SWAP dependent on OVER being implemented as a "primitive" or low-level Forth word or operation. You want to minimize use of ROT and OVER because they're complicated operations on most microprocessors relative to other simpler stack operations. They don't work well with LIFO stacks and direct access of stack items. > : DUP >R R@ R> ; This isn't a good idea either. Instead of being able to fetch the top data item on the data stack directly, you've migrated the operation to where you can, i.e., the return stack using R@ . It's better to have DUP be implemented as a "primitive" or low-level Forth word or operation. DUP is a heavily used word in Forth, at least. You can look at Philip Koopman's instruction frequencies: http://users.ece.cmu.edu/~koopman/stack_computers/sec6_3.html Anton Ertl also has Forth instruction frequencies, somewhere. > : DROP DUP XOR XOR ; That doesn't do what you think it does. DUP creates two stack items. XOR XOR converts one of them to zero. But, you still have two items on the stack, the second one being a zero. DROP needs to _reduce_ the number of items on the stack. Reducing or increasing the number of items on a stack usually requires a "primitive" or low-level Forth word or operation. I'd recommend implementing these as "primitives" or low-level Forth words or operations: > R R> DUP DROP SWAP OVER ROT Those aren't the absolute minimum since a couple of those can be eliminated, but it's close to it. Eliminating more slows down Forth code and would like slow down your code too. Optionally, you may want R@ too. R@ is not generally needed, except maybe for implementations of I and J . If you're directly accessing the stack, similar to parameters in C, you'll need PICK and the reverse operation, i.e., perhaps named PLACE . IIRC, Alex McDonald is using an optimizer, Rafts, that can determine optimal sequences for Forth words. I'm using an optimizer also. It's a highly modified, private version of Peter Sovietov's Forth Wizard: http://www.sovietov.com/app/forthwiz.html I've added a huge number of stack operations. I can select most any set of Forth stack operations, x86 style stack operations, Rob Chapman's "Stack Quarks", or use of temporary variables, etc to determine optimal sequences. I also updated it to use the return stack, so more complicated operations can be solved. E.g., for 2NIP (a b c d -- c d ), in terms of R> >R R@ DUP DROP SWAP OVER ROT -ROT rot drop rot drop > r -rot drop drop r> rot drop -rot -rot drop -rot -rot drop rot drop > r >r drop drop r> r>r swap drop r> rot dropr swap drop swap drop r> (keeps on going ...) If I don't want ROT or OVER etc I can unselect them and re-run. If you want 2NIP in terms of 2R> 2>R 2R@ 2DUP 2DROP 2SWAP 2OVER 2ROT -2ROT 2swap 2drop 2>r 2drop 2r> 2dup 2rot 2drop 2drop 2dup -2rot 2drop 2drop 2over 2rot 2drop 2drop 2>r 2drop 2r@ 2r> 2drop 2dup 2>r 2drop 2drop 2r> 2dup 2rot 2swap 2drop 2drop 2dup 2rot 2rot 2drop 2drop 2dup -2rot 2swap 2drop 2drop (keeps on going ...) An example using the return stack, e.g., 2R> (a b -- ) (R: -- a b) swap >r >r over >r >r drop dup rot >r >r drop dup rot >r drop >r dup -rot drop >r >r swap >r dup >r drop swap dup >r drop >r over >r swap drop >r over rot >r drop >r (keeps on going ...) I didn't post other solutions in terms of stack operators that I defined since you wouldn't understand what my naming means, but they're available also. E.g., directly retrieving from specific locations to specific data or return stack locations. Obviously, this optimizer doesn't find solutions using arithmetic operations or other Forth words. The Rafts optimizer Alex McDonald is using should. Rod Pemberton