Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #4703
| From | mlg3 <m_l_g3@yahoo.com> |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: multi-threading in Forth? |
| Date | 2011-08-11 01:10 +0400 |
| Organization | A noiseless patient Spider |
| Message-ID | <j1us4b$api$1@dont-email.me> (permalink) |
| References | (7 earlier) <b5SdnSwRyaUTbqbTnZ2dnUVZ8sidnZ2d@supernews.com> <j1hofk$g8o$1@dont-email.me> <t_6dndJzyNwCaqHTnZ2dnUVZ7oudnZ2d@supernews.com> <j1pvnb$1n8$1@dont-email.me> <uMmdncpD8awdEt_TnZ2dnUVZ8uCdnZ2d@supernews.com> |
Andrew Haley wrote:
> mlg3 <m_l_g3@yahoo.com> wrote:
>> Andrew Haley wrote:
>>> mlg3 <m_l_g3@yahoo.com> wrote:
>>>> Andrew Haley wrote:
>>> <formalism elided>
>> :-(
>>
>>>> (that is, if words in a colon definition do not read or modify the
>>>> return stack, a call of the definition is equivalent to inline
>>>> substitution of the definition's body).
>>> Quite so: this also means that fiddling with the return stack may
>>> destroy this property. For example,
>> [sigh]
>>
>> The context was important.
>
> As far as I could see the formalism told us in a formal way what we
> already knew. Perhaps I missed something, though. Were there some
> uncommon insights?
>
>>> *** The result of return address manipulations may be predicted
>> at compile-time ***
>>
>> And this is why the formalism is possible.
>
> But what is it for? I don't understand where this is going.
>
> Andrew.
ok,
>>> Theorem
>>>
>>> x == nest[ R1( x ) exit ]
(again that theorem)
Reminder.
ForAll N:
N >R R1( x ) == x N >R
Consequence 2: the correct algorithm of inlining
It requires that you track the return stack values
inside the colon definition's body.
The colon definition looks as
: foo z ;
The following cases are possible:
1. The return stack is left in the original state,
the return address and the values beneath it are not
read or written. It is ok to move the definition's
body into the calling definition as is.
It is the case that z == R1( z )
2. The return stack top is moved off the return stack and
later placed back, after something is done with the return
stack items beneath it. (Finally, the return stack top is
consumed by EXIT compiled by ; (semi-colon).)
It is easy to generate code for such y that
R1( y ) == z
(This y is the code that must be placed in the calling
definition's body in place of foo.
Indeed,
y == nest[ R1( y ) exit ] == nest[ z exit ] == foo
)
For r-stack primitives that access (that is, move)
the return address (the top return stack item),
no code is generated.
For r-stack primitives that access other return stack
items, the code is generated as if the top return stack
item did not exist.
For example,
: rswap r> r> r> swap >r >r >r ;
rswap == r> r> swap >r >r
One mode example.
( x -- y ) ( r: y -- x )
: >r> r> swap r> swap >r swap >r ;
The generated code will be:
( r> ) ( swap ) r> swap >r ( swap ) ( >r )
The removed words are shown in parens; they are removed
because they had to manipulate the return address that
is eliminated. The effect of R> was ( x -- x ra ) but
without ra it is just ( x -- x ), that is, NOOP.
The same applies to SWAP ( x ra -- ra x ), without
ra it becomes NOOP.
Alternative definition of the same word:
( x -- y ) ( r: y -- x )
: >r> r> r> swap rot >r >r ;
The generated code will be:
( r> ) r> ( swap ) swap >r ( >r )
The first SWAP disappears because it has to swap
the return address with another value, and the
return address disappears, so SWAP becomes a NOOP.
ROT becomes SWAP because it originally did
( x y ra -- y ra x ) and after ra disappears,
what must be done becomes ( x y -- y x ).
I think you already have mentioned that
>r> == nest[ r> r> swap rot >r >r ; ] ==
r[ ... ] r> r> swap rot >r >r ; ==
r> r[ ... ] rot >r >r ; ==
r> swap >r r[ ... ] >r ; == r> swap >r
3. The return stack is left in the original state
up to the moment that the return address is passed
to EXIT inside z. You may either not inline such
definition or transform it into an equivalent
single-exit form. (And the transformed code will
fall into category 1.)
Example.
: MAX 2dup > if drop exit then nip ;
To inline MAX, you first need to transform it into
an equivalent of
: max 2dup > if drop else nip then ;
4. All other cases. That is, the return address
is not what is passed to EXIT. Or it is passed,
but not to EXIT (and EXIT may never receive control).
There is a control transfer. You may generate optimized
code even for this case, but you will have to do code
transformations. Note that in many cases it is not
possible to completely eliminate the call (for example,
you may eliminate control transfer, but will still
have to push an address onto the return stack).
In this text, I recommend not to inline such
definitions. (Because else I would have to
give an exhaustive explanation of how to
generate control transfers for such stuff.)
Example.
: branch r> @ >r ;
You may either leave this definition as it is (that
is, call it rather than inline), or transform it into
a control transfer.
For subroutine-threaded code, the result might be
something like
jmp [address]
address: dw destination
Example.
: give> r> ;
I think, now you see why I am not willing to give
recommendations for the general case.
Better leave this definition as it is.
The generated native code might look as:
\ give> bar baz quz
spush address
exit
address:
bar
baz
qux
Example.
: enter >r ;
The easiest thing is to leave it as it is.
If you nevertheless want to generate optimized code,
you will have to generate an equivalent of a call
(the 'nest' action), and then transfer control to the
address at the stack top.
\ foo enter bar
foo
rpush address
spop R1
jump R1
address:
bar
Note that in the last two examples you can generate
inline code, but you cannot completely eliminate
the call: the RPUSH ADDRESS command is a piece
of that call.
Are definitions that use return address manipulations
worth generating optimized code? Such words likely
implement control structures, and the control structures
tend to be executed in loops. On the other hand, in
many cases custom control structures are not needed.
(As least, until we begin to implement custom control
structures for parallel execution on multi-core
processors.)
Anyway, whether or not you choose to generate optimized
code, the return address manipulations _do_ deserve
generation of _correct_ code.
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
multi-threading in Forth? Michael L Gassanenko <m_l_g3@yahoo.com> - 2011-08-02 02:01 -0700
Re: multi-threading in Forth? mhx@iae.nl (Marcel Hendrix) - 2011-08-02 11:22 +0200
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-02 15:26 +0200
Re: multi-threading in Forth? mlg3 <m_l_g3@yahoo.com> - 2011-08-04 01:06 +0400
Re: multi-threading in Forth? mhx@iae.nl (Marcel Hendrix) - 2011-08-04 06:36 +0200
Re: multi-threading in Forth? Mark Wills <markrobertwills@yahoo.co.uk> - 2011-08-04 08:25 +0100
Re: multi-threading in Forth? coos haak <chforth@hccnet.nl> - 2011-08-04 13:42 +0200
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-04 14:35 +0200
Re: multi-threading in Forth? Elizabeth D Rather <erather@forth.com> - 2011-08-04 08:30 -0500
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-04 15:38 +0200
Re: multi-threading in Forth? Elizabeth D Rather <erather@forth.com> - 2011-08-04 09:12 -0500
Re: multi-threading in Forth? Mark Wills <markrobertwills@yahoo.co.uk> - 2011-08-04 16:50 +0100
Re: multi-threading in Forth? mlg3 <m_l_g3@yahoo.com> - 2011-08-04 23:52 +0400
Re: multi-threading in Forth? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-05 08:50 -0500
Re: multi-threading in Forth? Mark Wills <markrobertwills@yahoo.co.uk> - 2011-08-04 16:49 +0100
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-04 19:23 +0200
Re: multi-threading in Forth? Elizabeth D Rather <erather@forth.com> - 2011-08-05 10:57 -0500
Re: multi-threading in Forth? stephenXXX@mpeforth.com (Stephen Pelc) - 2011-08-04 14:16 +0000
Re: multi-threading in Forth? Mark Wills <markrobertwills@yahoo.co.uk> - 2011-08-04 16:51 +0100
Re: multi-threading in Forth? stephenXXX@mpeforth.com (Stephen Pelc) - 2011-08-04 17:14 +0000
Re: multi-threading in Forth? "Rod Pemberton" <do_not_have@noavailemail.cmm> - 2011-08-06 03:46 -0400
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-04 19:11 +0200
Re: multi-threading in Forth? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-05 08:43 -0500
Re: multi-threading in Forth? mlg3 <m_l_g3@yahoo.com> - 2011-08-06 01:49 +0400
Re: multi-threading in Forth? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-06 03:13 -0500
Re: multi-threading in Forth? mlg3 <m_l_g3@yahoo.com> - 2011-08-09 04:41 +0400
Re: multi-threading in Forth? mlg3 <m_l_g3@yahoo.com> - 2011-08-09 11:01 +0400
Re: multi-threading in Forth? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-10 09:02 -0500
Re: multi-threading in Forth? mlg3 <m_l_g3@yahoo.com> - 2011-08-11 01:10 +0400
Re: multi-threading in Forth? Ouatu Bogdan <ouatubi@gmail.com> - 2011-08-10 13:22 +0000
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-06 01:12 +0200
Re: multi-threading in Forth? coos haak <chforth@hccnet.nl> - 2011-08-06 02:37 +0200
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-06 12:54 +0200
Re: multi-threading in Forth? alextangent <blog@rivadpm.com> - 2011-08-06 12:15 +0100
Re: multi-threading in Forth? Elizabeth D Rather <erather@forth.com> - 2011-08-05 22:23 -0500
Re: multi-threading in Forth? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-06 03:17 -0500
Re: multi-threading in Forth? Julian Fondren <ayrnieu@gmail.com> - 2011-08-05 19:02 -0500
Re: multi-threading in Forth? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-06 04:01 -0500
return-address manipulation (was: multi-threading in Forth?) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-08-06 16:35 +0000
Re: return-address manipulation Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2011-08-07 11:45 +0100
Re: return-address manipulation Josh Grams <josh@qualdan.com> - 2011-08-08 09:40 +0000
Re: return-address manipulation Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2011-08-08 12:17 +0100
Re: return-address manipulation Josh Grams <josh@qualdan.com> - 2011-08-08 12:29 +0000
Re: return-address manipulation mlg3 <m_l_g3@yahoo.com> - 2011-08-09 03:54 +0400
Re: return-address manipulation mlg3 <m_l_g3@yahoo.com> - 2011-08-09 02:52 +0400
Re: return-address manipulation Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2011-08-09 20:54 +0100
Re: return-address manipulation mlg3 <m_l_g3@yahoo.com> - 2011-08-11 09:00 +0400
Re: return-address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-09 14:49 -0500
Re: return-address manipulation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-08-10 09:03 +0000
Re: return-address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-10 05:13 -0500
Re: return-address manipulation mlg3 <m_l_g3@yahoo.com> - 2011-08-11 09:24 +0400
Re: return-address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-11 04:09 -0500
Re: return-address manipulation mlg3 <m_l_g3@yahoo.com> - 2011-08-11 09:36 +0400
Re: return-address manipulation mlg3 <m_l_g3@yahoo.com> - 2011-08-11 09:54 +0400
Re: return-address manipulation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-11 04:16 -0500
Re: multi-threading in Forth? Julian Fondren <ayrnieu@gmail.com> - 2011-08-07 01:43 -0500
Re: multi-threading in Forth? Spam@ControlQ.com - 2011-08-06 12:36 -0400
Re: multi-threading in Forth? Julian Fondren <ayrnieu@gmail.com> - 2011-08-07 01:13 -0500
Re: multi-threading in Forth? mlg3 <m_l_g3@yahoo.com> - 2011-08-09 02:35 +0400
Re: multi-threading in Forth? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2011-08-07 10:08 +0000
Re: multi-threading in Forth? Josh Grams <josh@qualdan.com> - 2011-08-07 13:45 +0000
Re: multi-threading in Forth? mhx@iae.nl (Marcel Hendrix) - 2011-08-05 17:17 +0200
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-05 19:23 +0200
Re: multi-threading in Forth? Elizabeth D Rather <erather@forth.com> - 2011-08-05 10:53 -0500
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-05 19:18 +0200
Re: multi-threading in Forth? Elizabeth D Rather <erather@forth.com> - 2011-08-06 09:59 -0500
Re: multi-threading in Forth? Spam@ControlQ.com - 2011-08-06 12:28 -0400
Re: multi-threading in Forth? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2011-08-06 11:29 +0000
Re: multi-threading in Forth? Mark Wills <markrobertwills@yahoo.co.uk> - 2011-08-04 16:47 +0100
Re: multi-threading in Forth? Julian Fondren <ayrnieu@gmail.com> - 2011-08-04 13:54 -0500
Re: multi-threading in Forth? coos haak <chforth@hccnet.nl> - 2011-08-04 22:02 +0200
Re: multi-threading in Forth? Elizabeth D Rather <erather@forth.com> - 2011-08-02 08:23 -0500
Re: multi-threading in Forth? Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2011-08-02 15:30 +0200
Re: multi-threading in Forth? Elizabeth D Rather <erather@forth.com> - 2011-08-02 08:53 -0500
Re: multi-threading in Forth? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-08-03 03:53 -0500
csiph-web