Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #25546 > unrolled thread

RAFTS-like optimiser; progress report

Back to article view | Back to comp.lang.forth

Contents

  RAFTS-like optimiser; progress report Alex McDonald <blog@rivadpm.com> - 2013-09-06 14:12 -0700
    Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-06 16:54 -0500
      Re: RAFTS-like optimiser; progress report Alex McDonald <blog@rivadpm.com> - 2013-09-06 16:02 -0700
        Re: RAFTS-like optimiser; progress report Bernd Paysan <bernd.paysan@gmx.de> - 2013-09-07 03:01 +0200
          Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-07 03:21 -0500
            Re: RAFTS-like optimiser; progress report albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-09-07 19:56 +0000
      Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-07 15:06 +0000
        Re: RAFTS-like optimiser; progress report "Alex McDonald" <blog@rivadpm.com> - 2013-09-07 19:01 +0100
          Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-09 12:23 +0000
            Re: RAFTS-like optimiser; progress report "Alex McDonald" <blog@rivadpm.com> - 2013-09-10 12:01 +0100
              Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-10 12:45 +0000
                Re: RAFTS-like optimiser; progress report "Alex McDonald" <blog@rivadpm.com> - 2013-09-10 16:33 +0100
                  Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-11 15:02 +0000
                    Re: RAFTS-like optimiser; progress report "Alex McDonald" <blog@rivadpm.com> - 2013-09-11 17:44 +0100
                      Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-13 11:58 +0000
                        Re: RAFTS-like optimiser; progress report "Rod Pemberton" <dont_use_email@nohavenotit.com> - 2013-09-14 22:47 -0400
                          Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-15 16:05 +0000
        Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-07 16:08 -0500
          Re: RAFTS-like optimiser; progress report mhx@iae.nl - 2013-09-08 03:21 -0700
            Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-08 06:42 -0500
              Re: RAFTS-like optimiser; progress report mhx@iae.nl - 2013-09-08 04:51 -0700
                Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-08 07:02 -0500
                  Re: RAFTS-like optimiser; progress report Paul Rubin <no.email@nospam.invalid> - 2013-09-08 10:08 -0700
                    Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-08 12:47 -0500
                      Re: RAFTS-like optimiser; progress report Paul Rubin <no.email@nospam.invalid> - 2013-09-08 11:10 -0700
                        Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-08 15:16 -0500
                          Re: RAFTS-like optimiser; progress report Paul Rubin <no.email@nospam.invalid> - 2013-09-08 16:08 -0700
                            Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-09 04:57 -0500
          Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-09 12:41 +0000
            Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-09 08:56 -0500
              Re: RAFTS-like optimiser; progress report albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-09-09 14:20 +0000
                Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-09 09:27 -0500
                  Re: RAFTS-like optimiser; progress report "Rod Pemberton" <dont_use_email@nohavenotit.com> - 2013-09-10 04:31 -0400
                    Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-10 05:11 -0500
              Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-09 15:08 +0000
                Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-09 10:45 -0500
                  Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-11 15:21 +0000
                    Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-11 12:04 -0500
                      Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-11 17:46 +0000
                        Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-11 14:45 -0500
                          Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-13 13:00 +0000
                            Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-13 10:46 -0500
                            Re: RAFTS-like optimiser; progress report stephenXXX@mpeforth.com (Stephen Pelc) - 2013-09-13 17:44 +0000
                              Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-14 15:31 +0000
                                Re: RAFTS-like optimiser; progress report Paul Rubin <no.email@nospam.invalid> - 2013-09-14 10:33 -0700
                                  Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-14 12:39 -0500
                                    Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-15 15:05 +0000
                                      Re: RAFTS-like optimiser; progress report Alex McDonald <blog@rivadpm.com> - 2013-09-15 08:32 -0700
                                        Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-15 13:20 -0500
                                      Re: RAFTS-like optimiser; progress report stephenXXX@mpeforth.com (Stephen Pelc) - 2013-09-15 16:54 +0000
                                        Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-15 17:02 +0000
                                      Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-15 12:54 -0500
                                        Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-16 09:21 +0000
                                          Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-16 08:39 -0500
                                            Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-16 15:48 +0000
                                              Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-16 15:03 -0500
                                                Re: RAFTS-like optimiser; progress report anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-09-17 10:15 +0000
                                                  Re: RAFTS-like optimiser; progress report "Rod Pemberton" <dont_use_email@nohavenotit.com> - 2013-09-17 17:24 -0400
                                              Re: RAFTS-like optimiser; progress report stephenXXX@mpeforth.com (Stephen Pelc) - 2013-09-17 13:10 +0000
              Re: RAFTS-like optimiser; progress report "Rod Pemberton" <dont_use_email@nohavenotit.com> - 2013-09-10 04:30 -0400
                Re: RAFTS-like optimiser; progress report Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-09-10 05:14 -0500
    Re: RAFTS-like optimiser; progress report mhx@iae.nl - 2013-09-07 03:22 -0700
    Re: RAFTS-like optimiser; progress report mhx@iae.nl - 2013-09-07 03:32 -0700

Page 1 of 4  [1] 2 3 4  Next page →

#25546 — RAFTS-like optimiser; progress report

Rewritten from the ground up from the previous version, I've now got some further progress with my RAFTS based optimiser. The early versions were very specific to my version of Forth, and I'm trying to ANSify it as much as possible.

Features (so far)
1. Duplicate literal elimination. Repeated values all use the same literal node.
2. Constant folding is done now; where the operator can reduce literals by executing the XT, this is done. Example; 1 2 + is reduced to 3.
3. Common subexpression elimination: some sequences generate identical code and these are eliminated.

Still to do, but relatively simple to achieve are
1. Elimination of redundant fetches, such as 10 y1 ! y1 @
2. Elimination of redundant stores, such as 10 y1 ! 20 y1 !
3. Support for more than basic blocks; currently only basic blocks are optimised
4. Code generator

3 and 4 are hard (if 4 is for an x86; for MIPS it would be simple).

Here's an example of the intermediate code generated. The first is an insertion in a doubly linked list, and the second is the same code optimised at the Forth level to reduce fetches. (Comments have been added by me.) The intermediate code for both is identical.

The intermediate code consists of a 3 address code format

$339608 (1) <6> +       <4> <5>

1: address of the structure
2: (n) use count of this element
3: <m> result "name" (if any)
4: op  operator
5: <a> source "name" for first operand
6: <b> source "name" for second operand 


begin-structure node%
    field: node.next        \ next in linked list (or head)
    field: node.prev        \ prev in linked list (or tail)
end-structure

: node-after ( free linked -- ) ( insert free node after linked )
    2dup node.next @      node.prev !
    2dup node.next @ swap node.next !
    2dup node.next ! swap node.prev ! ;

$339514 (1) <1> %benter
$339540 (3) <2> %sfetch S[-1]       \ fetch top of stack ("linked")
$33956C (4) <3> %sfetch S[-2]       \ and "free" into <2> and <3> 
$339598 (2) <4> @       <2>         \ fetch <2> from address <4>
$3395D4 (2) <5> literal $4          \ node.prev is offset 0, node.next 4
$339608 (1) <6> +       <4> <5>         
$33963C (1) <7> !       <3> <6>     \ store <3> in address <6>
$339680 (1) <8> !       <4> <3>
$3396BC (1) <9> !       <3> <2>
$3396F8 (1) <10> +      <3> <5>
$33972C (1) <11> !      <2> <10>
$339768 (1) <12> %sptr+ -2          \ adjust stack
$339794 (1) <13> %bexit

: node-after ( free linked -- ) ( insert free node after linked )
    2dup node.next 2dup @ 2dup
    node.prev ! swap node.next ! ! swap node.prev ! ;

$339514 (1) <1> %benter
$339540 (3) <2> %sfetch S[-1]
$33956C (4) <3> %sfetch S[-2]
$339598 (2) <4> @       <2>
$3395D4 (2) <5> literal $4
$339608 (1) <6> +       <4> <5>
$33963C (1) <7> !       <3> <6>
$339678 (1) <8> !       <4> <3>
$3396B4 (1) <9> !       <3> <2>
$3396F0 (1) <10> +      <3> <5>
$339724 (1) <11> !      <2> <10>
$339760 (1) <12> %sptr+ -2
$33978C (1) <13> %bexit

[toc] | [next] | [standalone]

#25547

Alex McDonald <blog@rivadpm.com> wrote:
> 2. Elimination of redundant stores, such as 10 y1 ! 20 y1 !

And at that point you'll have to decide what to do about volatile.

I think Stephen Pelc turns the optimizer on and off manually when
stores really have to be in that order for other threads to see.  I'm
not sure what other systems do.  It'd be nice to have some agreement
about the Right Thing to do.

Andrew.

[toc] | [prev] | [next] | [standalone]

#25548

On Friday, 6 September 2013 22:54:05 UTC+1, Andrew Haley  wrote:
> Alex McDonald <blog@rivadpm.com> wrote:
> 
> > 2. Elimination of redundant stores, such as 10 y1 ! 20 y1 !
> 
> And at that point you'll have to decide what to do about volatile.
> 
> I think Stephen Pelc turns the optimizer on and off manually when
> stores really have to be in that order for other threads to see.  I'm
> not sure what other systems do.  It'd be nice to have some agreement
> about the Right Thing to do.
> 
> Andrew.

I have considered a variable declared as VOLATILE. That requires extra header information that is impossible to get at when compiling in an ANS compliant system. All that's available is the xt to compile. 

Alternatively, and easier to implement, is !V or !VOLATILE as a volatile store. 

[toc] | [prev] | [next] | [standalone]

#25549

Alex McDonald wrote:
> Alternatively, and easier to implement, is !V or !VOLATILE as a volatile
> store.

Or BARRIER, which implements a memory barrier hint.  The optimizer is not 
allowed move loads or stores past the barrier, and for architectures with 
weak memory ordering, you can insert the necessary barrier instruction.

So

10 V ! BARRIER 20 V !

will make sure there are two stores, just like

V @ BEGIN  BARRIER DUP V @ <> UNTIL

will make sure that the second V is really fetched from.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

[toc] | [prev] | [next] | [standalone]

#25550

Bernd Paysan <bernd.paysan@gmx.de> wrote:
> Alex McDonald wrote:
>> Alternatively, and easier to implement, is !V or !VOLATILE as a volatile
>> store.
> 
> Or BARRIER, which implements a memory barrier hint.  The optimizer is not 
> allowed move loads or stores past the barrier, and for architectures with 
> weak memory ordering, you can insert the necessary barrier instruction.
> 
> So
> 
> 10 V ! BARRIER 20 V !
> 
> will make sure there are two stores, just like
> 
> V @ BEGIN  BARRIER DUP V @ <> UNTIL
> 
> will make sure that the second V is really fetched from.

That's quite nice.

On ARM processors (and others that need it) BARRIER could generate a
DSB instruction or something similar.  However, newer ARMs have 
load acquire/store release instructions, and these are, I suppose, a
better match to !V and @V .

Andrew.

[toc] | [prev] | [next] | [standalone]

#25557

In article <S7CdnfFbYpJhfLfPnZ2dnUVZ_oWdnZ2d@supernews.com>,
Andrew Haley  <andrew29@littlepinkcloud.invalid> wrote:
>Bernd Paysan <bernd.paysan@gmx.de> wrote:
>> Alex McDonald wrote:
>>> Alternatively, and easier to implement, is !V or !VOLATILE as a volatile
>>> store.
>>
>> Or BARRIER, which implements a memory barrier hint.  The optimizer is not
>> allowed move loads or stores past the barrier, and for architectures with
>> weak memory ordering, you can insert the necessary barrier instruction.
>>
>> So
>>
>> 10 V ! BARRIER 20 V !
>>
>> will make sure there are two stores, just like
>>
>> V @ BEGIN  BARRIER DUP V @ <> UNTIL
>>
>> will make sure that the second V is really fetched from.
>
>That's quite nice.
>
>On ARM processors (and others that need it) BARRIER could generate a
>DSB instruction or something similar.  However, newer ARMs have
>load acquire/store release instructions, and these are, I suppose, a
>better match to !V and @V .

My first thought was something like barrier.
But there is no reason that in V volatile Y normal
   Y @  ... BARRIER ... V !  Y !
that the store of Y couldn't be eliminated.
So that would be  a point in favour of V!

>
>Andrew.

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#25553

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Alex McDonald <blog@rivadpm.com> wrote:
>> 2. Elimination of redundant stores, such as 10 y1 ! 20 y1 !
>
>And at that point you'll have to decide what to do about volatile.

On the first order I would not let the compiler eliminate any @s and
!s.  If the programmer wants to do that he can do it in the source code.

While I can think of cases where one might want to optimize @, one
would have to determine whether such cases have a significant impact
on performance; and the cases I am thinking of are neither related to
volatile nor can they be optimized without hints by the programmer.

- 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 2013: http://www.euroforth.org/ef13/

[toc] | [prev] | [next] | [standalone]

#25554

on 07/09/2013 16:06:14,  wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Alex McDonald <blog@rivadpm.com> wrote:
>>> 2. Elimination of redundant stores, such as 10 y1 ! 20 y1 !
>>
>>And at that point you'll have to decide what to do about volatile.
> 
> On the first order I would not let the compiler eliminate any @s and
> !s. If the programmer wants to do that he can do it in the source
> code.
> 
> While I can think of cases where one might want to optimize @, one
> would have to determine whether such cases have a significant impact
> on performance; and the cases I am thinking of are neither related to
> volatile nor can they be optimized without hints by the programmer.
> 
> - anton

What cases? 

[toc] | [prev] | [next] | [standalone]

#25590

"Alex McDonald" <blog@rivadpm.com> writes:
>on 07/09/2013 16:06:14,  wrote:
>> While I can think of cases where one might want to optimize @, one
>> would have to determine whether such cases have a significant impact
>> on performance; and the cases I am thinking of are neither related to
>> volatile nor can they be optimized without hints by the programmer.

>What cases? 

The cases I am thinking of have to do with fetching no-longer-changing
cells from a constant address.  A simple example is an implementation
of CONSTANT with CREATE...DOES>:

: constant ( x -- )
  create ,
does> ( -- x )
  @ ;

5 constant foo
: bla foo ;
bla .

The compiler cannot optimize the @ away in BLA, because one could
still do

6 ' foo >body !
bla .

So we may want a way to tell the compiler that ' FOO >BODY @ will
always return the same result.  For this particular case, we can avoid
the problem by defining CONSTANT as

: constant ( x -- )
  >r : r> postpone literal postpone ; ;

but that's not always practical.

- 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 2013: http://www.euroforth.org/ef13/

[toc] | [prev] | [next] | [standalone]

#25608

on 09/09/2013 13:23:31, anton wrote:
> "Alex McDonald" <blog@rivadpm.com> writes:
>>on 07/09/2013 16:06:14,  wrote:
>>> While I can think of cases where one might want to optimize @, one
>>> would have to determine whether such cases have a significant impact
>>> on performance; and the cases I am thinking of are neither related to
>>> volatile nor can they be optimized without hints by the programmer.
> 
>>What cases?

Incidientally, your post caused me to look at the code again. Adding CSE
reintroduced a bug I'd eliminated in the original code.

variable a
: foo1 ( addr1 addr2 -- )
  over @ 0 rot ! 1+ swap ! ;
a a foo

I've corrected it, and the double linked list code I showed no longer
attempts to optimise away the second fetch. 

: node-after ( free linked -- ) ( insert free node after linked )
    2dup node.left @      node.prev !
    2dup node.left @ swap node.left !
    2dup node.left ! swap node.prev ! ;

$11A9514 (1) <1> %benter
$11A9540 (2) <2> %sfetch        S[-1]
$11A956C (4) <3> %sfetch        S[-2]
$11A9598 (2) <4> literal        $8
$11A95CC (3) <5> +      <4> <2>
$11A9600 (1) <6> @      <5>
$11A9634 (2) <7> literal        $4
$11A9668 (1) <8> +      <7> <6>
$11A969C (1) <9> !      <3> <8>
$11A96D8 (1) <10> @     <5>    \ <== doesn't reuse <6>
$11A970C (1) <11> +     <4> <3>
$11A9740 (1) <12> !     <10> <11>
$11A977C (1) <13> !     <3> <5>
$11A97B8 (1) <14> +     <7> <3>
$11A97EC (1) <15> !     <2> <14>
$11A9828 (1) <16> %sptr+        -2
$11A9854 (1) <17> %bexit


> 
> The cases I am thinking of have to do with fetching no-longer-changing
> cells from a constant address. A simple example is an implementation
> of CONSTANT with CREATE...DOES>:
> 
>: constant ( x -- )
> create ,
> does> ( -- x )
> @ ;
> 
> 5 constant foo
>: bla foo ;
> bla .
> 
> The compiler cannot optimize the @ away in BLA, because one could
> still do
> 
> 6 ' foo >body !
> bla .

My second reaction (actually, it may have been my first) was "EEEKK!!".
Modifying a constant this way ranks just below 10 CONSTANT 5 . The latter
is a lesser sin in that optimisation will do exactly the insanity that is
requested.

This strikes me as not ANS Forth. Only the children of CREATE must have a
body. In my Forth, this blows up. However, it doesn't stop a definition
like

: myval , does> >body @ ;
: foo myval [ 6 ' myval >body ! ] myval ;

But that's OK, since this generates 2 basic blocks; [ ends the first and
] starts a second.  

> 
> So we may want a way to tell the compiler that ' FOO >BODY @ will
> always return the same result. For this particular case, we can avoid
> the problem by defining CONSTANT as
> 
>: constant ( x -- )
> >r : r> postpone literal postpone ; ;
> 
> but that's not always practical.
> 
> - anton

[toc] | [prev] | [next] | [standalone]

#25609

"Alex McDonald" <blog@rivadpm.com> writes:
>on 09/09/2013 13:23:31, anton wrote:
>> The cases I am thinking of have to do with fetching no-longer-changing
>> cells from a constant address. A simple example is an implementation
>> of CONSTANT with CREATE...DOES>:
>> 
>>: constant ( x -- )
>> create ,
>> does> ( -- x )
>> @ ;
>> 
>> 5 constant foo
>>: bla foo ;
>> bla .
>> 
>> The compiler cannot optimize the @ away in BLA, because one could
>> still do
>> 
>> 6 ' foo >body !
>> bla .
>
>My second reaction (actually, it may have been my first) was "EEEKK!!".
>Modifying a constant this way ranks just below 10 CONSTANT 5 .

Just because the defining word is called CONSTANT does not mean that
the compiler can assume that it behaves like the standard word
CONSTANT.  Consider:

: aword ( x -- )
 create ,
 does> ( -- x )
 @ ;
 
 5 aword foo
: bla foo ;
 bla .

and

: value ( x -- )
 create ,
 does> ( -- x )
 @ ;
 
 5 value foo
: bla foo ;
 bla .

The compiler cannot know the intent of the programmer and has to
assume that the program may change FOO later.

>This strikes me as not ANS Forth. Only the children of CREATE must have a
>body.  In my Forth, this blows up.

FOO is a child of CREATE, and this is a standard program.  If it blows
up in your compiler, your compiler has a bug.

- 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 2013: http://www.euroforth.org/ef13/

[toc] | [prev] | [next] | [standalone]

#25610

on 10/09/2013 13:45:50,  wrote:
> "Alex McDonald" <blog@rivadpm.com> writes:
>>on 09/09/2013 13:23:31, anton wrote:
>>> The cases I am thinking of have to do with fetching no-longer-changing
>>> cells from a constant address. A simple example is an implementation
>>> of CONSTANT with CREATE...DOES>:
>>>
>>>: constant ( x -- )
>>> create ,
>>> does> ( -- x )
>>> @ ;
>>>
>>> 5 constant foo
>>>: bla foo ;
>>> bla .
>>>
>>> The compiler cannot optimize the @ away in BLA, because one could
>>> still do
>>>
>>> 6 ' foo >body !
>>> bla .
>>
>>My second reaction (actually, it may have been my first) was "EEEKK!!".
>>Modifying a constant this way ranks just below 10 CONSTANT 5 .
> 
> Just because the defining word is called CONSTANT does not mean that
> the compiler can assume that it behaves like the standard word
> CONSTANT.  Consider:
> 
>: aword ( x -- )
> create ,
> does> ( -- x )
> @ ;
> 
> 5 aword foo
>: bla foo ;
> bla .
> 
> and
> 
>: value ( x -- )
> create ,
> does> ( -- x )
> @ ;
> 
> 5 value foo
>: bla foo ;
> bla .
> 
> The compiler cannot know the intent of the programmer and has to
> assume that the program may change FOO later.
> 
>>This strikes me as not ANS Forth. Only the children of CREATE must have a
>>body.  In my Forth, this blows up.
> 
> FOO is a child of CREATE, and this is a standard program. If it blows
> up in your compiler, your compiler has a bug.

It works OK as long as you redefine CONSTANT or define FOO as a CREATE;
but it doesn't work if you try and get the body of the compiler defined
CONSTANT. It doesn't have one and isn't obliged to have one.

This is where the optimisation is intended;

variable foo
: bla 6 foo ! foo @ ;

COMPILE, sees 6 <literal> ! <literal> @ . The second FOO doesn't require
to be refetched. 

If VALUE (or CONSTANT) is defined as CREATE , DOES> @ and compiles that
way, then, yes, no optimisation can be done. My compiler gets round that
by having <literal> as the compile time behaviour of CONSTANT,
<addr-of-val> @ as the compile time behaviour of VALUE. TO at compile
time generates <addr-of-val> ! .

6 constant six
5 value foo
: bla six to foo foo ;

COMPILE, sees 6 <addr-of-foo> ! <addr-of-foo> @ . Here we can work out
that the <foo> @ is redundant. 

: bla foo [ ( anything including ) six to foo ] foo ;

All bets are off after [. We have to refetch. I'm also leaving DOES>
clauses well alone right now, and treating them as calls with unknown
stack effects.

In short, defining CONSTANT as a CREATE , DOES> @ makes it not a
constant, and it needs to treated as a non-constant. That much I agree
with.


> 
> - anton

[toc] | [prev] | [next] | [standalone]

#25628

"Alex McDonald" <blog@rivadpm.com> writes:
>If VALUE (or CONSTANT) is defined as CREATE , DOES> @ and compiles that
>way, then, yes, no optimisation can be done.

Yes, now that we are on the same page, the CONSTANT case is an example
of a case where the addressed data will not change (that's the intent
of the programmer); how can the programmer let the compiler know about
that?  In this case one can define the word with : instead of
CREATE...DOES>, but in general, we may want a way to tell the
compiler that the data in an area is not going to change.

- 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 2013: http://www.euroforth.org/ef13/

[toc] | [prev] | [next] | [standalone]

#25631

on 11/09/2013 16:02:29,  wrote:
> "Alex McDonald" <blog@rivadpm.com> writes:
>>If VALUE (or CONSTANT) is defined as CREATE , DOES> @ and compiles that
>>way, then, yes, no optimisation can be done.
> 
> Yes, now that we are on the same page, the CONSTANT case is an example
> of a case where the addressed data will not change (that's the intent
> of the programmer); how can the programmer let the compiler know about
> that? In this case one can define the word with : instead of
> CREATE...DOES>, but in general, we may want a way to tell the compiler
> that the data in an area is not going to change.
> 
> - anton

Here's your proposal to that effect (at least, for the DOES> clause): 
http://www.complang.tuwien.ac.at/anton/euroforth/ef00/ertl00.pdf

[toc] | [prev] | [next] | [standalone]

#25651

"Alex McDonald" <blog@rivadpm.com> writes:
>on 11/09/2013 16:02:29,  wrote:
>> Yes, now that we are on the same page, the CONSTANT case is an example
>> of a case where the addressed data will not change (that's the intent
>> of the programmer); how can the programmer let the compiler know about
>> that? In this case one can define the word with : instead of
>> CREATE...DOES>, but in general, we may want a way to tell the compiler
>> that the data in an area is not going to change.
...
>Here's your proposal to that effect (at least, for the DOES> clause): 
>http://www.complang.tuwien.ac.at/anton/euroforth/ef00/ertl00.pdf

That's one proposal, but I am no longer very convinced that that's the
best way to attack the problem, for the following reasons:

1) Stephen Pelc has suggested declaring a memory range read-only,
which can solve this problem and more, so it is a more general
solution to the same problem.

2) We can already use : to do the things that one can do with
CONST-DOES>.  There is a little problem here that this is less space
efficient than using DOES> (or a space-efficient CONST-DOES>) on many
Forth systems, but does that justify adding CONST-DOES>?

- 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 2013: http://www.euroforth.org/ef13/

[toc] | [prev] | [next] | [standalone]

#25669

On Fri, 13 Sep 2013 07:58:29 -0400, Anton Ertl  
<anton@mips.complang.tuwien.ac.at> wrote:

> 1) Stephen Pelc has suggested declaring a memory range read-only,
> which can solve this problem and more, so it is a more general
> solution to the same problem.

Without hardware support, implementing read-only memory using
read-write memory can be problematic.  E.g., it can require artificial
fixes like using paging to unmap memory.  Code checks to prevent
writes is probably the worst possible solution.  Yet, that would have
to be the solution used on many older platforms that have no ability
to make memory range read-only via programmatic methods or hardware.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#25677

"Rod Pemberton" <dont_use_email@nohavenotit.com> writes:
>On Fri, 13 Sep 2013 07:58:29 -0400, Anton Ertl  
><anton@mips.complang.tuwien.ac.at> wrote:
>
>> 1) Stephen Pelc has suggested declaring a memory range read-only,
>> which can solve this problem and more, so it is a more general
>> solution to the same problem.
>
>Without hardware support, implementing read-only memory using
>read-write memory can be problematic.  E.g., it can require artificial
>fixes like using paging to unmap memory.  Code checks to prevent
>writes is probably the worst possible solution.  Yet, that would have
>to be the solution used on many older platforms that have no ability
>to make memory range read-only via programmatic methods or hardware.

Such a declaration is there to communicate the programmer's intent to
the compiler; the intent is "the program does not change the memory
range".  Actually enforcing that the program does not change the
memory range will help debugging, but is not essential.

E.g., usually the value of constants is stored in read-write memory,
and nothing prevents the programmer from changing that value.  I have
not heard of problems caused by that.

- 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 2013: http://www.euroforth.org/ef13/

[toc] | [prev] | [next] | [standalone]

#25559

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Alex McDonald <blog@rivadpm.com> wrote:
>>> 2. Elimination of redundant stores, such as 10 y1 ! 20 y1 !
>>
>>And at that point you'll have to decide what to do about volatile.
> 
> On the first order I would not let the compiler eliminate any @s and
> !s.  If the programmer wants to do that he can do it in the source code.

Well, then you have to wonder about visiblity to other threads.  Do
you really want every store to have a store barrier to ensure that it
actually becomes visible to other threads?  There's a performance
penalty to pay.  There are no realy easy answers.

Andrew.

[toc] | [prev] | [next] | [standalone]

#25571

On Saturday, September 7, 2013 11:08:54 PM UTC+2, Andrew Haley wrote:
> Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> 
> > Andrew Haley <andrew29@littlepinkcloud.invalid> writes: 
> >>Alex McDonald <blog@rivadpm.com> wrote:
> >>> 2. Elimination of redundant stores, such as 10 y1 ! 20 y1 !
> >>
> >>And at that point you'll have to decide what to do about volatile.
> > 
> > On the first order I would not let the compiler eliminate any @s and
> > !s.  If the programmer wants to do that he can do it in the source code.
> 
> Well, then you have to wonder about visiblity to other threads.  Do
> you really want every store to have a store barrier to ensure that it
> actually becomes visible to other threads?  There's a performance
> penalty to pay.  There are no realy easy answers.

Which Forth has this problem?

-marcel

[toc] | [prev] | [next] | [standalone]

#25572

mhx@iae.nl wrote:
> On Saturday, September 7, 2013 11:08:54 PM UTC+2, Andrew Haley wrote:
>> Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> 
>> > Andrew Haley <andrew29@littlepinkcloud.invalid> writes: 
>> >>Alex McDonald <blog@rivadpm.com> wrote:
>> >>> 2. Elimination of redundant stores, such as 10 y1 ! 20 y1 !
>> >>
>> >>And at that point you'll have to decide what to do about volatile.
>> > 
>> > On the first order I would not let the compiler eliminate any @s and
>> > !s.  If the programmer wants to do that he can do it in the source code.
>> 
>> Well, then you have to wonder about visiblity to other threads.  Do
>> you really want every store to have a store barrier to ensure that it
>> actually becomes visible to other threads?  There's a performance
>> penalty to pay.  There are no realy easy answers.
> 
> Which Forth has this problem?

Any Forth that does dead store elimination.

Andrew.

[toc] | [prev] | [next] | [standalone]

Page 1 of 4  [1] 2 3 4  Next page →

Back to top | Article view | comp.lang.forth

csiph-web