- intermediate language e.g. program as database of instruction lists
Historically Forth features a single-pass compiler that is triggered e.g. >when the interpreter hits a : colon. Some control flows require code >back-patching to resolve jump targets. This can be awkward.
OTOH by going over the code in several passes offers easy paths for >simplification and optimization. e.g.
- elimination of comments
- resolving of labels for jump targets
- intermediate language e.g. program as database of instruction lists
- peephole optimization, superinstructions
- tail call elimination
Is there any Forth out there that compiles high-level definitions in this way? >Anybody willing to share some other experience in this field?
OTOH by going over the code in several passes offers easy paths for simplification and optimization. e.g.I can't think of a Forth compiler that DOESN'T. It simply ignores the stuff:
- elimination of comments
- resolving of labels for jump targetsAgain - I can't think of a Forth compiler that doesn't. References are placed on
- peephole optimization, superinstructions4tH has a peephole optimizer used for strength reduction, constant folding and dead code elimination. It only looks back a single instruction, but can in some circumstances work recursive.
- tail call elimination4tH's optimizer does that one as well.
Is there any Forth out there that compiles high-level definitions in this way?It works fine and transparent - unless you insist to meddle with the return stack
Anybody willing to share some other experience in this field?
Historically Forth features a single-pass compiler that is triggered e.g. when the interpreter hits a : colon. Some control flows require code back-patching to resolve jump targets. This can be awkward.[..]
OTOH by going over the code in several passes offers easy paths for simplification and optimization. e.g.
Is there any Forth out there that compiles high-level definitions in this way?
On Monday, January 16, 2023 at 12:50:28 PM UTC+1, minf...@arcor.de wrote:
Historically Forth features a single-pass compiler that is triggered e.g. when the interpreter hits a : colon. Some control flows require code back-patching to resolve jump targets. This can be awkward.
OTOH by going over the code in several passes offers easy paths for simplification and optimization. e.g.[..]
Is there any Forth out there that compiles high-level definitions in this way?Using an intermediate representation is far more powerful, as one can
do recursive 'context-sensitive' inlining (delay compiling as long as possible).
In iForth's iSPICE package I'll eventually use run-time code generation (e.g. to eliminate pointer-chasing). This delays instruction selection to the limit.
However, it only works if the target application is sufficiently unsophisticated,
or has predictable execution behavior (like SPICE). I'm sure that there would be many snags would I try it for Forth itself.
<type 'list'>i = range(100)
type(i)
<class 'range'>i = range(100)
type(i)
On Mon, 16 Jan 2023 03:50:26 -0800 (PST)
"minf...@arcor.de" <minf...@arcor.de> wrote:
- intermediate language e.g. program as database of instruction listsMaybe this one in 'Holon Forth' and 'Fifth':
Planet Holonforth Wolf Wejgaard EuroForth 2016 http://www.euroforth.org/ef16/papers/wejgaard.pdf
1989-09-00 Paper presented at the EuroFORML conference 1989
Not Screens nor Files but Words Wolf Wejgaard https://holonforth.com/ef89.html
Further papers at:
https://www.holonforth.com/papers.html
Ref to Fifth was in:
A Fresh Look at the Forth Dictionary
Wolf Wejgaard
Presented at the EuroFORTH conference 1995 https://www.holonforth.com/ef95.html
Historically Forth features a single-pass compiler that is triggered e.g. when the interpreter hits a : colon. Some control flows require code back-patching to resolve jump targets. This can be awkward.
OTOH by going over the code in several passes offers easy paths for simplification and optimization. e.g.
- elimination of comments
- resolving of labels for jump targets
- intermediate language e.g. program as database of instruction lists
- peephole optimization, superinstructions
- tail call elimination
Is there any Forth out there that compiles high-level definitions in this way?
Anybody willing to share some other experience in this field?
On Monday, January 16, 2023 at 12:50:28 PM UTC+1, minf...@arcor.de wrote:
Historically Forth features a single-pass compiler that is triggered e.g.[..]
when the interpreter hits a : colon. Some control flows require code
back-patching to resolve jump targets. This can be awkward.
OTOH by going over the code in several passes offers easy paths for
simplification and optimization. e.g.
Is there any Forth out there that compiles high-level definitions in this way?
Using an intermediate representation is far more powerful, as one can
do recursive 'context-sensitive' inlining (delay compiling as long as possible).
In iForth's iSPICE package I'll eventually use run-time code generation (e.g. >to eliminate pointer-chasing). This delays instruction selection to the limit.
-marcel--
My sytem, that has never been released (and won't be), which was
developed from about 2005, compiles Forth code to an intermediate form, carries out some optimisations, then generates the executable code. I
did it this way (I think) to:
- widen the range of optimisations beyond simple peephole optimisation
- making it more readily portable to different processors and OS's (one
front end, n back ends).
- generating different types of executable code including machine code.
and probably other reasons that I've forgotten.
I did peephole optimisations and super-instructions but then found other things took priority e.g. using the system, so I've never got round to getting on with other aims.
It did make things such as quotations easier as it just involves
suspending the outer definition, compiling the quotation, then resuming
the suspended definition. Nested as much as desired.
Historically Forth features a single-pass compiler that is triggered e.g. >when the interpreter hits a : colon. Some control flows require code >back-patching to resolve jump targets. This can be awkward.
OTOH by going over the code in several passes offers easy paths for >simplification and optimization. e.g.
- elimination of comments
- resolving of labels for jump targets
- intermediate language e.g. program as database of instruction lists
- peephole optimization, superinstructions
- tail call elimination
Is there any Forth out there that compiles high-level definitions in this way? >Anybody willing to share some other experience in this field?
iForth and VFX have an intermediate representation that they use for inlining. AFAIK they don't use it for elimination of comments, jump
target resolution, peephole optimization, superinstructions, or
tail-call elimination.
Gforth uses the threaded-code representation (and its relocatable
variant) either directly, or as a step to a mixture of native code and threaded-code. It also buffers the threaded code for a straight-line
piece of code before generating native code, to allow better code
generation.
Anton Ertl schrieb am Montag, 16. Januar 2023 um 17:41:20 UTC+1:
iForth and VFX have an intermediate representation that they use for
inlining. AFAIK they don't use it for elimination of comments, jump
target resolution, peephole optimization, superinstructions, or
tail-call elimination.
Gforth uses the threaded-code representation (and its relocatable
variant) either directly, or as a step to a mixture of native code and
threaded-code. It also buffers the threaded code for a straight-line
piece of code before generating native code, to allow better code
generation.
The VFX docs speak of code inlining vs source inlining, the latter now >improved through tokenizing.
This looks similar to gforth's inlining method.
"minf...@arcor.de" <minf...@arcor.de> writes:
Anton Ertl schrieb am Montag, 16. Januar 2023 um 17:41:20 UTC+1:
iForth and VFX have an intermediate representation that they use for
inlining. AFAIK they don't use it for elimination of comments, jump
target resolution, peephole optimization, superinstructions, or
tail-call elimination.
Gforth uses the threaded-code representation (and its relocatable
variant) either directly, or as a step to a mixture of native code and
threaded-code. It also buffers the threaded code for a straight-line
piece of code before generating native code, to allow better code
generation.
The VFX docs speak of code inlining vs source inlining, the latter now >improved through tokenizing.The original source inliner of VFX had the same correctness problem as EVALUATE-based macros. AFAIK The "tokenizing" resolves the names,
BASE etc. when the code is tokenized and therefore does not have this problem.
Gerry Jackson schrieb am Montag, 16. Januar 2023 um 21:29:24 UTC+1:
My sytem, that has never been released (and won't be), which was
developed from about 2005, compiles Forth code to an intermediate form,
carries out some optimisations, then generates the executable code. I
did it this way (I think) to:
- widen the range of optimisations beyond simple peephole optimisation
- making it more readily portable to different processors and OS's (one
front end, n back ends).
- generating different types of executable code including machine code.
and probably other reasons that I've forgotten.
I did peephole optimisations and super-instructions but then found other
things took priority e.g. using the system, so I've never got round to
getting on with other aims.
It did make things such as quotations easier as it just involves
suspending the outer definition, compiling the quotation, then resuming
the suspended definition. Nested as much as desired.
So it compiles the innermost definitions/quotations first before compiling outer definitions?
The "classic" way is to jump over quotations, nesting included.
From the reference test:
T{ : q1 [: 1 ;] ; q1 EXECUTE -> 1 }T
T{ : q2 [: [: 2 ;] ;] ; q2 EXECUTE EXECUTE -> 2 }T
Did you experiment with enclosures?
Historically Forth features a single-pass compiler that is triggered e.g. when the interpreter hits a : colon. Some control flows require code back-patching to resolve jump targets. This can be awkward.
On 17/01/2023 08:11, minf...@arcor.de wrote:
Gerry Jackson schrieb am Montag, 16. Januar 2023 um 21:29:24 UTC+1:
My sytem, that has never been released (and won't be), which was
developed from about 2005, compiles Forth code to an intermediate form,
carries out some optimisations, then generates the executable code. I
did it this way (I think) to:
- widen the range of optimisations beyond simple peephole optimisation
- making it more readily portable to different processors and OS's (one
front end, n back ends).
- generating different types of executable code including machine code.
and probably other reasons that I've forgotten.
I did peephole optimisations and super-instructions but then found other >> things took priority e.g. using the system, so I've never got round to
getting on with other aims.
It did make things such as quotations easier as it just involves
suspending the outer definition, compiling the quotation, then resuming
the suspended definition. Nested as much as desired.
So it compiles the innermost definitions/quotations first before compiling outer definitions?
The "classic" way is to jump over quotations, nesting included.Yes a crude, but effective, solution imposed by the traditional single
pass compilation.
From the reference test:
T{ : q1 [: 1 ;] ; q1 EXECUTE -> 1 }T
T{ : q2 [: [: 2 ;] ;] ; q2 EXECUTE EXECUTE -> 2 }T
Did you experiment with enclosures?Not with the built in quotations. But before quotations were
standardised I did develop an ANS Forth implementation of closures in
2011 that I can let you have if you are interested.
I found multiple passes necessary in Mecrisp-Across to re-join different control flow branches that use a different local register allocation without relying on canonical fallback. If the number of stack elements held in registers at the joint differ,one needs to use the smaller number of stack elements, which may require additional passes to achieve.
Using the larger number of elements causes non-existing elements to be popped from the stack, at least temporarily. Of course, in valid Forth code, these elements will be pushed back, but may cause reads/writes beyond the beginning of the stack area inmemory. Simply adding a guard space at the beginning of the stack would be a solution to keep it single-pass, but in combination with nested interrupts, this may be riscy. I solved this with multiple passes in the compiler, and generate elegant code
Note this compiler is capable of register allocation across ?dup and similiar constructs.
Matthias Koch schrieb am Mittwoch, 18. Januar 2023 um 11:16:21 UTC+1:subsequent reshuffling of the common numer of elements in registers) when I have a larger total amount of stack elements in registers than in the other branch, as different branches may have different depth stack effects, and these elements do not exist
Can you point me to a text describing the solution or existing implementation? I am reshuffling registers as much as possible without spilling them to the stack, but I do not know on how to handle the situation without partial spilling (and
I am certainly much less experienced than you are in this field. I just happen to know
that Chaitin's algortihm includes spilling until new liveliness analysis comes up with
an acceptably colored graph. But AFAIK optimal spilling is still a thing for heuristics
or brute force iteration. Until today there is no known 'formula' for it.
Hence my question out of curiosity whether you have gained new insights. It had not
been clear whether you do liveliness analysis at all.
Add to this that spilling costs are not constant, given the caching effects in many CPUs.
I found only one lecture note that at least mentions this (but does not deal with it later on):
https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/17/Slides17.pdf
Of course it remains also a design decision of where for a small Forth compiler for
embedded systems reasonable usability ends and where overkill starts.
Can you point me to a text describing the solution or existing implementation? I am reshuffling registers as much as possible without spilling them to the stack, but I do not know on how to handle the situation without partial spilling (and subsequentreshuffling of the common numer of elements in registers) when I have a larger total amount of stack elements in registers than in the other branch, as different branches may have different depth stack effects, and these elements do not exist on the
P.S. since you won't do graph coloring, perhaps this paper may be of more interest because
it also treats with data flow analysis: http://www.christianwimmer.at/Publications/Wimmer10a/Wimmer10a.pdf
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 300 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 36:39:17 |
| Calls: | 6,707 |
| Files: | 12,239 |
| Messages: | 5,353,438 |