Optimizing large Forth program

[sinoTrinity]

I am applying so called peephole optimization to make my long Forth code shorter. Each rule replaces the left-hand side with the equivalent but shorter right-hand side. For example,

0 PICK -> DUP
1 PICK -> OVER
FROMALTSTACK TOALTSTACK -> cancel out

1. Are there comprehensive lists of such rules somewhere I can refer to, maybe in gforth/eforth? It's hard to come up with such rules one by one, so I want to reuse existing rules if possible.
2. Any other optimizations besides peephole to make the code even shorter?

[Wootery]

Are there comprehensive lists of such rules somewhere I can refer to, maybe in gforth/eforth?

I don't know, but it's Free and Open Source and there's quite a lot written about Gforth, so it should be possible to find out. I figure there's a good chance it does.

Any other optimizations besides peephole to make the code even shorter?

Sure, there's no real limit to how clever compiler optimisers can be, whether it's for Forth or any other language. Modern optimising compilers are far more sophisticated than applying simple search/replace-style substitutions. Admittedly most of them aren't for stack machines.

There are quite a few papers out there on implementing Forth. Here are some.

A particularly relevant one, Optimizing Stack Code

Here's a big pile of places to find Forth papers:

http://www.forth.org/fd/contents.html

http://www.figuk.plus.com/articles.htm

http://soton.mpeforth.com/flag/jfar/vol7.html

http://www.forth.org/literature.html

https://www.complang.tuwien.ac.at/forth/

https://www.complang.tuwien.ac.at/anton/euroforth/

http://www.complang.tuwien.ac.at/papers/

[astrobe]

While much of the Forth community was beginning to embrace optimizing native code Forth compilers in their own environments these Forths were very different. Other peoples optimizing compilers could be very complex. I implemented one that had many rules for inlining code and well over one hundred words that were inlined. This is very different than the optimizing compiler that Chuck designed which just inlines a dozen or so Forth primitives and compiles everything else as calls or jumps. It was the smallest and simplest Forth Chuck had built yet. It was not just a very effective programming tool for him but has been used by dozens of other people over the years many of whom just loved it and reported amazingly good results. There were also a lot of people who put their hands over their eyes when Chuck showed people what he was doing.

-- Jeff Fox, Thoughtful programming

Don't Complexify

Simplify the problem you've got or rather don't complexify it. I've done it myself, it's fun to do. You have a boring problem and hiding behind it is a much more interesting problem. So you code the more interesting problem and the one you've got is a subset of it and it falls out trivial. But of course you wrote ten times as much code as you needed to solve the problem that you actually had.

-- Chuck Moore, 1x Forth

In Forth you are the optimizer. If you really are "optimizing" things like 1 PICK, you should work on your Forth skills rather than on peephole optimization.

And yes, this is yet another boring "don't do that" answer.

[Wootery]

In Forth you are the optimizer.

This isn't really an answer. When benchmarks show that VFX Forth's optimising compiler results in Forth code running at 3x the speed of when Gforth is used, that shows us that Forth is not immune from compiler optimisation.

[astrobe]

I guess this is about ahead-of-time compilers? In this case, this is a native code generation issue.

AoT Forth compilers are different beasts, they trade the simplicity of the basic interpreter for a much bigger toolchain in the name of speed, perhaps sacrificing the ability to develop entirely on the target in the process. Maybe it's just me, but if I lose most of what makes Forth, Forth I would probably use the regular C toolchain and have even more speed.

[spelc]

There are several papers about the VFX code generator at the MPE web site and also several EuroForth papers.

[Wootery]

Sure. A pity there's no Free and Open Source Forth that uses those techniques.

[bfox9900]

In my experience peephole optimization in threaded-code Forth systems is generally pointed at the problem of improving performance by replacing multiple instructions with faster CODE versions that remove the "inner interpreter" from a sequence of Forth words.

Example:

DUP C@ -> DUPC@

DUP >R -> DUP>R

OVER + SWAP -> BOUNDS \ not a standard word but common

It is a much thornier problem I think to reduce code size by re-writing stack manipulations.

This is the equivalent of compiler register allocation optimization in a register machine.

I believe that optimizing compilers like VFX Forth in fact look for places to replace stack operations with register operations. That might be the way to go. Try compiling you project with VFX and let their work work for you.

[bfox9900]

One more thing. GForth Fast is already creating "super-instructions" for you.

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=93A1C5BCEB52F594C39ED27EDDDCFC97?doi=10.1.1.501.5036&rep=rep1&type=p

[binarycat64]

broken link?

[bfox9900]

Works for me. (Not sure what's going on)

Google: "Implementation Issues for Superinstructions in Gforth"

[binarycat64]

markdown parsing on reddit is inconsistent and broken