Path: eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.lang.forth
Subject: (Generalized) constant folding in Mecrisp and Gforth
Date: Mon, 05 Aug 2019 10:18:29 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 124
Message-ID: <2019Aug5.121829@mips.complang.tuwien.ac.at>
Injection-Info: reader02.eternal-september.org; posting-host="3da9cce0aa426406efc7595956831b5a";
	logging-data="14706"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/H2yyEiBPob6TxalNXtZdY"
Cancel-Lock: sha1:aIX0p0q+r4eGkE0dal3fiKAoqic=
X-newsreader: xrn 10.00-beta-3

I used to be sceptical that the benefit of constant folding merits the
implementation effort.  But the benefits of (generalized) constant
folding and the relatively simple implementation have convinced me
that it is worthwhile.

Benefits:

The obvious benefit is that we can optimize sequences like

A 5 CELLS +

into a single literal, but we could also do this by writing

[ A 5 CELLS + ] LITERAL

That's why I did not consider it worthwhile.  But with generalized
constant folding, we get additional benefits.  E.g., we can optimize
"1 PICK" into OVER (which I used recently
<2019Aug1.101155@mips.complang.tuwien.ac.at>).

Or consider an object-oriented system where the object is passed on
the stack:

<object> <method-selector>

If <object> is a constant, the optimizer for <method-selector> can
resolve the method dispatch at compile time and compile the method
implementation.  Then the optimizer for the method implementation can
perform further optimizations specific to this constant <object>.  As
an example, consider:

5e fvalue x
synonym y x
: foo to y ;

In the new Gforth header implementation, TO Y is implemented as if it
compiled

<nt-of-y> (to)

(TO) is a method selector, with the implementation being dependent on
the the type of Y.  Through several levels of generalized constant
folding, the eventual code is equivalent to

[ ' x >body ] literal f!


Implementation:

The basic implementation in Gforth can be found in
<http://git.savannah.gnu.org/cgit/gforth.git/commit/?id=a7d95ce8521aa1a6a72757103c245915e2e649df>
(unfortunately mixed up with some other stuff; the relevant changes
are in fold.fs glocals.fs kernel/comp.fs kernel/cond.fs).

It introduces a literal stack.  Every call to LITERAL pushes the value
on the literal stack.  When a primitive is compiled eventually (with
PEEPHOLE-COMPILE,), or on a control flow join (BEGIN or THEN), all the
pending literals on the literal stack are compiled first.  But in the
meantime, the optimizer of a word can check if there are enough
literals for generalized constant folding on the literal stack, and
perform an optimization.

E.g., the optimizer for + checks if there are at least 2 items on the
literal stack.  If not, it just compiles the primitive + (which in
turn first compiles any pending literals).  But if there are two items
on the literal stack, it pops them, adds them, and pushes the result
on the literal stack without generating any code; the result may be
processed further by the optimizer of later words, or be compiled into
code when the next primitive is compiled.

The optimizer for + could also check for exactly one literal, check
the value of the literal, and compile a special primitive like 1+ or
CELL+ instead.  For the moment, this optimization is not implemented
for +, but this generalized constant folding is applied for PICK and
(TO).


References:

Matthias Koch implemented this approach in Mecrisp and published it in 

@Article{koch15,
  author = 	 {Matthias Koch},
  title = 	 {{Flags, Konstantenfaltung und Optimierungen}},
  journal = 	 {Vierte Dimension},
  year = 	 {2015},
  volume =	 {31},
  number =	 {arm},
  pages =	 {16--18},
  OPTmonth = 	 {},
  url = 	 {https://wiki.forth-ev.de/lib/exe/fetch.php/vd-archiv:4d2015-arm.pdf},
  OPTannote = 	 {}
}

Bernd Paysan picked up this idea and implemented it in Gforth.  He
published it in

@Article{paysan19,
  author = 	 {Bernd Paysan},
  title = 	 {Constant Folding f\"ur Gforth},
  journal = 	 {Vierte Dimension},
  year = 	 {2019},
  OPTkey = 	 {},
  volume =	 {35},
  number =	 {2},
  pages =	 {17--18},
  OPTmonth = 	 {},
  url = 	 {https://wiki.forth-ev.de/lib/exe/fetch.php/vd-archiv:4d2019-02.pdf},
  OPTannote = 	 {}
}

This is the latest issue of Vierte Dimension, and the url will not
work for a few months (in order to encourage you to become a member of
Forth-Gesellschaft and get the paper version).

Both articles are in German, so I wrote this posting for those who
prefer to read about it in English.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2019: http://euro.theforth.net/