Optimisation in Forth.

Introduction
============

   You may wonder why an optimizer for a computer language would be
considered an AI application.  This optimizer is not so much for a
particular language as well related to a Computer Intelligence that has
insight in her own code.

   Different types of optimisations interfere and finding ones way
through this certainly requires some heuristics. The bottom line is
that an optimiser qualifies as an AI application.

Properties
----------

   A Forth system is a database of small programs. It is worthwhile to
investigate what properties these small programs (words) might have.
The flag field of a word allow to add this information to the header.
A certain combination of flags allow a particular optimisation.

Definitions
-----------

   An annihilator is a word that only deletes an item from the stack.
Examples are DROP 2DROP NIP RDROP.

   A juggler reorders the stack without adding or removing items.
Examples are SWAP 2SWAP ROT.

   A duplicator copies an item from the stack.  Examples are DUP OVER
2DUP.

Optimisations
-------------

   Optimisations are manipulations on a program source or intermediate
code to improve the speed of the resulting program.  In other respect
the result is inferior. Symbolic debugging - one of Forth's strong
points - goes through the drain.  (The name "optimisation" is a
misnomer.)

    * Constant folding is a well known technique in optimisation.  It
     means that if an operator works on constants the result may be
     replaced by a constant that is calculated at compile time.  In
     Forth we generalise this to folding.  Folding refers to all words
     that can be replaced by simpler words in case they receive
     constant data on the stack.

   * Reordering is not so much an optimisation per se, but it allows
     other optimisations to kick in. As a rule of thumb constants are
     moved to the top of the stack, where they fall prey to folding.
     Reordering might also eliminate a juggler.

   * Annihilation is the elimination of e a whole sequence of
     operations.  In Forth sometimes the result of a calculation is
     dropped.  Depending on the properties of the calculation, the
     calculation itself can be removed.  This type of annihilation is
     related to an annihilator.  Another type is related to conditional
     branching where the condition is known at compile time. Code known
     to be skipped is removed.

   * Inlining means replacing a Forth word with its constituents.  This
     technique is very important in Forth, more so than in other
     languages, due to the small size of Forth words.  Inlining is
     always a winner in speed, and mostly even also a winner with
     regard to space.

     Even more important is the fact that inlining allows folding to be
     applied across constituent words. This applies to high level and
     low level code alike.

     Inlining high level code is trivial.  A further inlining stage
     replaces a high level definition that only calls code words, by a
     code definition which concatenates the code words.

Data collecting
---------------

   In order to add introspective information to a Forth, in the first
place the machine code words must be analysed, because ultimately
everything is defined in terms of code words.  For this purpose the
code words are disassembled using a disassembler that allows to readily
inspect the parts of a disassembled instruction.  A Postit-Fixup
assembler and disassembler is well suited.

   * By inspecting register words in the disassembly, registers usage
     can be accumulated.  This information is then added to the header.

   * At the same time information about whether memory or I/O ports are
     accessed for read or write can be collected.  It turns out to be
     useful make a difference between input and output side effects.
     Here the words to look out for are the MOVE and IN/OUT
     instructions, operations that access memory (in fact all
     operations that not target registers) and special instructions
     like the string operations on Pentia.

   * Finally the stack effect can be deduced from the number of POP's
     and PUSH'es.  And the use of the return stack can be marked, which
     mostly warrants a special treatment.

   After all code words have been analysed, the stack effects and
register usage can be concluded for all high level words.  The stack
effect of a high level words is the concatenation of the stack effect
of its constituents.  The register usage of a high level word is the
logical or of the register usage of the constituents, as are its side
effects.

   There will no doubt be exceptions.  It is wrong to cater for too
many exceptional situation in such a heuristic tool.  Instead, the
exception are filled in by hand before the automated collection is
started, it fills in only as yet unknown items.  Of course it helps to
have a simple and straightforward Forth to begin with.

Purpose
-------

   A \ci in general will use optimisation to generate a temporary
definition that is much faster, and retain all the valuable partial
information about words.

   In normal non-AI applications, words are recursively replaced by
faster words, and those eventually by code definitions. Meanwhile words
that are no longer directly used in the final application are
eliminated.  For space conservation headers may be removed as well,
provided in the application no dictionary lookup is needed.

Implementation
==============

   The following implementation notes apply to a 32 bits Pentium Forth
where a full cell (4 bytes, 0..3) is reserved for the flags.  They must
be considered as an example.  The information about a word,
optimisation opportunities and stack effect, sits in the flag field.
Whenever nothing is filled in in the flag field, it means unknown.
This applies equally to the stack effect as to the optimisation flags.

Stack effects
-------------

   The information about the stack effects sits in the byte 3 of the
flag field.  The highest nibble of this third byte applies to input.
It is the number of stack items popped plus one.  The lowest nibble
thusly indicates the number of pushed items.  0 means an unknown (not
yet analysed) stack effect.  0FH indicates a variable number of items.

   The stack effect is added in three steps.  For all low level words
the stack effect is found by counting pops and pushes.  Irregular stack
effects are corrected as well as filled in for high level words.  All
high level stack effects are derived from the stack effect of their
constituents.

   Code words are analysed by disassembling the code that is pointed to
by the code field to the first "next" code encountered. For each
instruction the opcode, which is the first part of its disassembly, is
looked up in a set of possible pop and push instructions.

   Irregularities are just tabulated in the source code of the analyser.

   Words are recognized by their code field.  High level words are
either created by ":" or by a "CREATE .. DOES>" construction .  They
are recognised by the code field containing DOCOL or DODOES
respectively.  For both the data field points to a chain of high level
calls, i.e. a number of such calls possibly with inlined data and
ending in a "(;)", the word compiled by ";".  (The result of this "high
level next" is to return control is returned to the word that called
this one.)  For a linear chain of calls the stack effect is calculated
as follows:

   * Start with a effect of ( 0 - 0 ).

   * For each constituent
     Subtract the pops from the left (output) nibble.      If the
     output nibble is negative, add its (absolute) value to inputs, and
     make it zero.      Add the pushes to the left (output) nibble.
     (Correction by 11H is not yet done).

     The following exceptions to a linear chain have special treatment:

   * LIT BRANCH'es and SKIP are followed by inline data that must be
     taken care off

   * A BRANCH or 0BRANCH forward is always taken, analysing just one
     path through a definition: the shortest one. A more sophisticated
     way is to analyse all paths and conclude a variable outcome if it
     is not consistent or any of the paths contains a variable
     constituent.

   * If the stack effect of a constituent is variable, the result is
     variable, overruling any other outcome

   * If the stack effect of a constituent is unknown, the result is
     unknown, overruling any other outcome except variable.

   *  For a CREATE .. DOES> word the linear chain pointed to by the
     DOES> pointer is analysed. However the stack effect is initialised
     to ( 0 - 1) to reflect the passing of the data pointer to the
     DOES> part.

   * ' EXECUTE has the stack effect of  .  Other
     occurrences of EXECUTE lead to a variable stack effect.  Lateron
     we will leave this to the optimiser, but at the stage of analysing
     the kernel this is useful, especially because all usage of EXECUTE
     in the kernel is of this type.

   * ' CATCH has the stack effect of  plus an
     extra output.  Other occurrences of CATCH lead to a variable stack
     effect.  So a word is treated as if exceptions do not occur.  This
     is okay because the stack effect is not relevant in case of
     exceptions.

   A high level word is recognised by its code field address containing
DOCOL , i.e. the nesting routine for the interpreter.  A CREATE ..
DOES> word is detected by is code field address containing DODOES ,
i.e. the common code that starts up words defined by compiler extension.
All other words are treated as code.

   The whole of Forth is treated as follows:
   * Fill in the exception

   * Fill in the code words

   * Sweep repeatedly through the dictionary, from early to latest:
     For each unknown stack effect, try to find it by discriminating
     between     DODOES DOCOL and other words,   Stop if no progress is
     made any more.

   Hopefully everything is known now, but maybe we must add to the
exceptions.  And repeat the above process.

   The notion of a simple sequence is one that doesn't reach to the
stack outside what is defined within the sequence.

Optimisation classes
--------------------

   As has been pointed out, the optimisation class of a word is
indicated by a bit set in the flags field. Each bit set to true opens
up a particular opportunity for optimisation.  Further a sequence has a
certain class if each constituent has that class.  For example, if one
of the words called does a store, the sequence is found to do a store
and the optimisations that would be allowed by "no stores" are blocked.
So the optimisation class of a sequence is the logical or of the oc's
of the constituents.  This can be done efficiently by bit-wise or
operations.

The no store bit.
.................

   The "no store" bit would better be named "no output side effect" bit.
It indicates that the outside world doesn't change by executing this
word.  Again not that the stacks and internal registers are inside.
Note that fetching from an input port has an output side effect, (as
well as an input side effect.)

   The following optimisation are opened up:
   * In combination with an annihilator. If the output of a "no store"
     sequence is annihilated, the whole sequence and the annihilator
     may be left out.  Example: BASE CELL+  XX  NIP becomes XX

   * In combination with a juggler. If the outputs of "no store"
     sequence are juggled, the sequences itself may be juggled,
     eliminating the juggler.  Example: XX CELL+  BASE  SWAP becomes
     BASE  XX CELL+

   * In combination with a duplicator. Again a sequence may be
     duplicated and the duplicator eliminated. This is not an
     optimisation, except for the duplication of constants.  Going the
     other direction can be an optimisation.  Two identical sequences
     with no output side effect can be replaced by one and a duplicator.
     Example: (for a recursive definition with stack effect ( 1 - 1 )
     and no side effects) 12 RECURSE OVER RECURSE becomes 12 RECURSE 12
     RECURSE  (elimination duplicator)
     12 RECURSE 12 RECURSE becomes 12 RECURSE DUP. (introducing
     duplicator)

The no fetch property.
......................

   The "no fetch" bit would better be named "no input side effect" bit.
It indicates that the outside world affects the outcome of this word.
Input side effects are weaker than output side effects and the
knowledge that they are absent allows less optimisation.

The no stack effect property.
.............................

   The "no stack effect fetch" bit refers to absolute accesses of the
stacks, i.e. where the data or return stack are not used as stacks.
Typical examples are DEPTH and RSP.  These words are rare but prevent
considerable optimisation.

The no side effect property.
............................

   The combination of the "no store ", "no fetch " and "no stack effect
" properties is quite common. Such a word is said to have the "no side
effect" property.  The combination allows substantially more
optimisation than each alone. We will use the abbreviation NS for this
important concept.  Examples are CONSTANT's, VARIABLE's, operators like
+ or NEGATE, and all stack manipulations: jugglers, annihilator,
duplicators.

   NS-words are amenable to folding:
   * If a NS-sequence has only constant inputs, it may be run at
     compile time.  Its inputs and the code sequence may be replaced by
     the resulting constant outputs.  Example: After "12 4 3 SWAP * +"
     is replaced by 24.

   * If a NS-sequence has no inputs, it may be run at compile time and
     replaced by the resulting constant outputs.  The difference with
     the preceeding example is that the sequence starts with 12 instead
     of *. Any literals are of course NS.

   On closer inspection the second condition is equivalent to the first.
It is the more easy one to implement.

Associativity.
..............

   An operator with two inputs and one output, so called "binary
operators" can have, in addition to NS, the property of associativity.
This refers to a situation where three operands are involved. Examples
are OR and + . However not F+ .  In the following we will denote an
associative operator by %.  Associativity allows to replace the
sequence "x % y %" with "x y % %" where it may be that "x y %" can be
folded into a constant.  Example: (assuming a 64-bit Forth) "CELL+
CELL+" is first inlined to "8 + 8 +" then associated to "8 8 + +" then
folded to "16 +".
Note that it is not necessary to look for other patterns, in view of
other transformation that are done.

Short circuit evaluation.
.........................

   Another optimisation aplicable to binary NS-operators is short
circuit evaluation. This is the situation where the result is known,
while only one of the operands is known, such as "FFFF AND" "FFFF OR"
"0 +" "0 XOR" and "0 *". Some of these operations can be just dropped,
while in other cases the result is known and the other operand
(possibly non-constant) can be dropped.

Optimisation by recursive inlining
----------------------------------

   A word is optimized by first optimizing its constituents, then
inlining the constituents and apply any optimisation opportunities like
folding that open up.

In more detail we have the following steps:
   * Check First of all check whether the item has been optimised
     already.  We do in fact a "depth first" optimisation, so the words
     lowest in the call hierarchy are optimised first. It is important
     to only attempt optimisation once. This cuts the recursion short.

   * Recurse For all constituent words of this definition, do an
     optimisation, such as defined in these steps.

   * Inline Build up an executable sequence in the dictionary.  Inline
     a constituents word, keeping track of all opportunities to
     optimise. Try to build up a sequence  of NS-words that starts with
     constants and where each word following doesn't consume more
     inputs than are available. Consequently the outputs are available
     as constants.

   * Breakdown When a sequence of NS-words breaks down, we have
     identified a sequence that can be run at compile time. This
     sequence is run, and removed from the output sequence. Then the
     output of the run is compiled, as a sequence of constants.

   * Special opportunities.  After each inlining the constituent is
     checked whether it allows special optimisations. Here the likes of
     the associativity optimisation is done, by looking for a "operand
     % operand %" pattern.  In a fashion similar to the breakdown of a
     NS-sequence the tail of the sequence that is being built up is, is
     replaced.

   * Replace After inlining is finished, the sequence is now attached
     to the word we are optimizing to replace the original sequence.
     Maybe the original code is kept if no folding took place and the
     sequence is longer that a certain limit.

   * Mark properties The current word is marked as optimised. Its stack
     effect and its optimization classes are derived from its
     constituents and added to the flags header.