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

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

First result in riscv optimiser

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

Contents

  First result in riscv optimiser albert@spenarnc.xs4all.nl - 2026-09-01 10:49 +0200
    Re: First result in riscv optimiser anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-09-01 15:33 +0000
      Re: First result in riscv optimiser albert@spenarnc.xs4all.nl - 2026-09-01 18:54 +0200
      Re: First result in riscv optimiser albert@spenarnc.xs4all.nl - 2026-09-02 11:18 +0200
      Re: First result in riscv optimiser Kragen Javier Sitaker <kragen@canonical.org> - 2026-09-04 13:14 -0300
        Re: First result in riscv optimiser albert@spenarnc.xs4all.nl - 2026-09-05 13:06 +0200
          Re: First result in riscv optimiser Kragen Javier Sitaker <kragen@canonical.org> - 2026-09-08 02:21 -0300
            Re: First result in riscv optimiser albert@spenarnc.xs4all.nl - 2026-09-08 12:38 +0200
              Re: First result in riscv optimiser Kragen Javier Sitaker <kragen@canonical.org> - 2026-09-11 07:50 -0300
                Re: First result in riscv optimiser Paul Rubin <no.email@nospam.invalid> - 2026-09-11 17:09 -0700
                Re: First result in riscv optimiser albert@spenarnc.xs4all.nl - 2026-09-13 14:03 +0200
              Re: First result in riscv optimiser antispam@fricas.org (Waldek Hebisch) - 2026-09-13 02:53 +0000

#135501 — First result in riscv optimiser

The ciforth works in reverse of the usual optimisers. Peephole is the
last step.

I have completed the first step: adding optimisation information to
all words, including added later.
Now I have completed the second step: if code works on constant data,
execute it at compile time, if possible.
An example:
albert@sinas2:~/PROJECT/optim$ optimiser

: nonsense DUP 'DROP EXECUTE ;
 OK
 : test 2 4 * nonsense 13 + ;
  OK
  'test inline&fold
  2
  LIT
  *
  DUP
  LIT
  EXECUTE
  nonsense
  LIT
  +
  test
   OK
   SEE test

: test
0000,0000,0000,0015
;
 OK
(15 is of course 21 decimal, the correct outcome.)

Groetjes Albert
-- 
The Chinese government is satisfied with its military superiority over USA.
The next 5 year plan has as primary goal to advance life expectancy
over 80 years, like Western Europe.

[toc] | [next] | [standalone]

#135504

albert@spenarnc.xs4all.nl writes:
>The ciforth works in reverse of the usual optimisers. Peephole is the
>last step.

That's exactly like usual optimizers.  Peephole optimization tends to
be used to catch some things that other optimizations have missed,
typically across the boundaries of the other optimizations.

>Now I have completed the second step: if code works on constant data,
>execute it at compile time, if possible.
>An example:
>albert@sinas2:~/PROJECT/optim$ optimiser
>
>: nonsense DUP 'DROP EXECUTE ;
> OK
> : test 2 4 * nonsense 13 + ;
>  OK
>  'test inline&fold
>  2
>  LIT
>  *
>  DUP
>  LIT
>  EXECUTE
>  nonsense
>  LIT
>  +
>  test
>   OK
>   SEE test
>
>: test
>0000,0000,0000,0015
>;

Gforth does not do inlining by itself yet, but it does have a literal
stack for constant folding and more.  See
<2019Aug5.121829@mips.complang.tuwien.ac.at>.  Let's take your
example, but using explicit inlining for NONSENSE:

inline: nonsense dup `drop execute ;inline
: test 2 4 * nonsense 13 + ;
see test
\ output follows:
: test  
  #21 ; ok

Gforth will do that on RISC-V as well as on other architectures,
because these things happen at the threaded-code level.

I don't think that these contrived examples prove much, and in general
I don't think that full constant folding will trigger often, but
partial constant folding (e.g., optimizing "5 -" into lit+ with the
immediate argument -5) is probably relatively frequent, and
occasionally, constant folding works in cases where a much
heavier-weight optimization would otherwise be needed.  E.g.,

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

FOO is compiled to

: foo  
  <x> f! ;

where <X> is the body address of X.  In the process of this
compilation, several levels of partial constant folding are involved.
There may be other ways to achieve this kind of compilation from this
code, but I think they would be substantially more complicated.  IIRC
our EuroForth 2019 paper on the new Gforth header gives an example of
how that works.

- 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: https://forth-standard.org/
EuroForth 2026 CFP: http://www.euroforth.org/ef26/cfp.html

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

#135505

In article <2026Sep1.173341@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>albert@spenarnc.xs4all.nl writes:
<SNIP>
>I don't think that these contrived examples prove much, and in general

I agree. Just reporting on progress.

>- 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: https://forth-standard.org/
>EuroForth 2026 CFP: http://www.euroforth.org/ef26/cfp.html
-- 
The Chinese government is satisfied with its military superiority over USA.
The next 5 year plan has as primary goal to advance life expectancy
over 80 years, like Western Europe.

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

#135525

In article <2026Sep1.173341@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>albert@spenarnc.xs4all.nl writes:
>>The ciforth works in reverse of the usual optimisers. Peephole is the
>>last step.
>
>That's exactly like usual optimizers.  Peephole optimization tends to
>be used to catch some things that other optimizations have missed,
>typically across the boundaries of the other optimizations.

There is no doubt that peephole optimisation is a fruitful last
step.

I phrased it superficially. The use of a separate interpreter and
compile xt I consider a peep hole optimisation.
If you rely on later speed up ("optimisation") there is no need
to do this. So there is only one behaviour associated with a
word, possibly immediate.
OTOH if you don't need speed, dual xt is unnecessary complication.

<SNIP>
>- anton
-- 
The Chinese government is satisfied with its military superiority over USA.
The next 5 year plan has as primary goal to advance life expectancy
over 80 years, like Western Europe.

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

#135556

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> (...) in general I don't think that full constant folding will trigger
> often, but partial constant folding (e.g., optimizing "5 -" into lit+
> with the immediate argument -5) is probably relatively frequent, and
> occasionally, constant folding works in cases where a much
> heavier-weight optimization would otherwise be needed.

This is contextual.  I have no doubt that you are correct in the case of
GForth, but in some compilers, constant folding is one of the most
important and frequently used optimizations.  But that’s because they’re
doing inlining and/or specialization, which create lots more constants
to fold, and dead-code elimination, which prunes conditionals that are
resolved at compile time by constant folding.

I don’t know enough about ciforth to guess how important it will be in
the ciforth context.

Kragen

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

#135566

In article <87ecf96ljg.fsf@debian>,
Kragen Javier Sitaker  <kragen@canonical.org> wrote:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> (...) in general I don't think that full constant folding will trigger
>> often, but partial constant folding (e.g., optimizing "5 -" into lit+
>> with the immediate argument -5) is probably relatively frequent, and
>> occasionally, constant folding works in cases where a much
>> heavier-weight optimization would otherwise be needed.
>
>This is contextual.  I have no doubt that you are correct in the case of
>GForth, but in some compilers, constant folding is one of the most
>important and frequently used optimizations.  But that’s because they’re
>doing inlining and/or specialization, which create lots more constants
>to fold, and dead-code elimination, which prunes conditionals that are
>resolved at compile time by constant folding.
>
>I don’t know enough about ciforth to guess how important it will be in
>the ciforth context.

You bet it is.
This is a test  of the optimiser for i86 (that is unfinished but
partly working)
-------------------------------------
\ Test of annihilating.
: test6 BASE @ IF SWAP THEN 2DROP ;
'test6 SHOW-IT

--------------------------------------

: test6
BASE   @
0BRANCH [ 8 , ] ( between SWAP   2DROP   ) SWAP   2DROP
;
AFTER

: test6
DROP   DROP
;

After inlining of code words:

   POP|X, AX|
   POP|X, AX|
--------------------------------------
\ Annihilator involving a fetch.
: testD IF SWAP ELSE DROP BASE @ THEN 2DROP ;
'testD SHOW-IT
--------------------------------------

: testD

0BRANCH [ 18 , ] ( between ? DROP   ) SWAP
BRANCH  [ 18 , ] ( between @   2DROP   ) DROP   BASE   @   2DROP
;
AFTER

: testD
DROP   DROP   DROP
;
--------------------------------------
Note that example 2 is quite sophisticated.
Each of the two branches are annihilated by the 2DROP.
@ is known to have no output side effect. So BASE @ DROP can be
annihilated.
OTOH
   SPEAKER-PORT P@
(Port @) may have an output side effect,
   SPEAKER-PORT P!
surely has.
So that there is no simplification.

Note that takes places in the high level code realm, so it
is highly portable (as long as you can mark all the Forth words
with properties.)

There are several posts in c.l.f an excerpt is to be found in:
https://home.hccnet.nl/a.w.m.van.der.horst/forthlecture5.html

>
>Kragen

Groetjes Albert
-- 
The Chinese government is satisfied with its military superiority over USA.
The next 5 year plan has as primary goal to advance life expectancy
over 80 years, like Western Europe.

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

#135600

albert@spenarnc.xs4all.nl writes:
> In article <87ecf96ljg.fsf@debian>,
> Kragen Javier Sitaker  <kragen@canonical.org> wrote:
>>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>> (...) in general I don't think that full constant folding will trigger
>>> often, (...)
>>
>>This is contextual.  (...)
>
> You bet it is.
> This is a test  of the optimiser for i86 (that is unfinished but
> partly working)
> -------------------------------------
> \ Test of annihilating.
> : test6 BASE @ IF SWAP THEN 2DROP ;
>
> ...
>
> : test6
> DROP   DROP
> ;
>
> After inlining of code words:
>
>    POP|X, AX|
>    POP|X, AX|

This is not quite constant folding, but it’s a related optimization.  I
don’t remember if it has an accepted name — it’s close to register
allocation, but of course you aren’t allocating any registers.  Clearly
it makes a great improvement in `test6`.  However, how does such code
arise?  You surely wouldn’t intentionally write it that way in
production code.  Conditional compilation with [ifdef] and the like?
Subroutine inlining?

That is, this kind of optimization can be extremely powerful — but
generally only in synergy with other optimizations which create
opportunities for it.

Kragen

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

#135604

In article <87y0dcgvxf.fsf@debian>,
Kragen Javier Sitaker  <kragen@canonical.org> wrote:
<SNIP>
>That is, this kind of optimization can be extremely powerful — but
>generally only in synergy with other optimizations which create
>opportunities for it.

If a word is optimised it is totally inlined.

Of course. There are a lot of stages in the i86 optimiser -- afer this
high level optimiser -- on the assembler level.

\ This sequence represents steps
\ 1. make instructions uniform
INCLUDE optbb_expand.frt
\ 2a. non-controversial transformation
INCLUDE optbb_nobrain.frt
\ 2b. more subtle transformation
INCLUDE optbb_gen.frt
\ 2c. propagation transformation
INCLUDE optbb_propagate.frt
\ 2d. return stack optimisation
INCLUDE optbb_RSP.frt
\ 3. shorten instructions if there are equivalents
INCLUDE optbb_compress.frt

I got to the point that the original (unadulterated to favor
a particular compiler) Byte benchmark performed in the league
of mpe Forth.

I have 106 peephole patterns, some quite complicated.

E.g.
movimovr-pattern DUP matches? IF ?movimovr-replace? ELSE

Each replace transform machine code.

But then look at this:
\ Instruction that have an implied register not apparent from the
\ disassembly in `DISS and not AX/AL.
DATA IMPLIED-CATEGORY  HERE 0 ,
' REPZ,      ,          ' STOS,      ,          ' LODS,      ,
' SHL,       ,          ' SHR,       ,
' SCAS,      ,          ' CMPS,      ,          ' MOVS,      ,
' OUTS,      ,          ' INS,       ,          ' OUT|D,     ,
' IN|D,      ,          ' SCAS,      ,          ' INT,       ,
HERE SWAP !

The first step  in i86 to replace all duplicate instruction with a canonical
instruction ( there are a dozen ways to move AX to BX), totally
unnecessary on RISCV.
I decided to give up on i86 and concentrate on RISCV.
I handled the regular stack in i86 with push and pops, but
I succeeded to replace all return stack access with registers.
If in RISCV I handle the regular stack to move to registers
in a similar fashion with the return stack I have a feasible
optimiser with little effort.

>Kragen
-- 
The Chinese government is satisfied with its military superiority over USA.
The next 5 year plan has as primary goal to advance life expectancy
over 80 years, like Western Europe.

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

#135658

albert@spenarnc.xs4all.nl writes:
> If a word is optimised it is totally inlined.

As well as being a powerful optimization in its own right, I am guessing
that that opens up a lot of opportunities for the stack-manipulation-
annihilation optimization you were talking about in your previous post.

> [...]
>
> I got to the point that the original (unadulterated to favor
> a particular compiler) Byte benchmark performed in the league
> of mpe Forth.

That’s very impressive!

> I have 106 peephole patterns, some quite complicated.

How confident are you that all 106 are correct?

> [...]
> I decided to give up on i86 and concentrate on RISCV.

This kind of thing seems like it could be a significant advantage for
RISC-V, if people find that the cost-benefit ratio for writing compilers
for it is better than for 8086, i386, or amd64 (not sure which ISA you
meant by “i86”).

Kragen

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

#135677

Kragen Javier Sitaker <kragen@canonical.org> writes:
>> I have 106 peephole patterns, some quite complicated.
> How confident are you that all 106 are correct?

It's sometimes possible to use SAT solvers to prove that two code
sequences are equivalent, without much human input.  There are also
formal models of RISC-V that you can put into a proof assistant.  Or
these days maybe you can throw the whole set into an LLM and ask for
formal proofs.

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

#135693

In article <877bksdpui.fsf@debian>,
Kragen Javier Sitaker  <kragen@canonical.org> wrote:
>albert@spenarnc.xs4all.nl writes:
>> If a word is optimised it is totally inlined.
>
>As well as being a powerful optimization in its own right, I am guessing
>that that opens up a lot of opportunities for the stack-manipulation-
>annihilation optimization you were talking about in your previous post.
>
>> [...]
>>
>> I got to the point that the original (unadulterated to favor
>> a particular compiler) Byte benchmark performed in the league
>> of mpe Forth.
>
>That’s very impressive!

Note that this is a rigged benchmark. All optimisations were
inspired by the Byte sieve.

>
>> I have 106 peephole patterns, some quite complicated.
>
>How confident are you that all 106 are correct?

Not very. I took precautions however. REGRESS is a sort of a
compile time ASSERT, an alternative for strong typing.
If a REGRESS fails, the compilation fails.
This is an example. It takes myself half an hour to
understand the meticulous comment. All peep hole
optimisation lean heavily on my disassembly that turns
one assembler instruction into a list of component objects.
.code prints out the optimisation result that is manually
inspected if need be.
optimisation is a class that takes three parameters.
movimoviq-pattern is an object.

\ A movi reg, is up till now during optimisation has a 32 bit value.
\ That works as long as there is no ghost register, because the Q:
\ prefix is removed. For those cases where the immediate value must be 64 bit,
\ this expansion is needed in the compression phase.

<! !Q  MOVI|X, !!T  0 {L,} ~!!T !>
<A  Q: MOVI|X, 0 , !TALLY A>
{ bufv 2 + L@  L>S bufc 2 + !
  bufv C@  bufc OR!U
  bufv 1+ C@  bufc 1+ OR!U
}
optimisation movimoviq-pattern
REGRESS movimoviq-pattern  DUMPO S:
REGRESS original matches? S: TRUE
REGRESS original 1+ matches? S: FALSE
REGRESS HERE Q: MOVI|X, BX| 1234 IL, matches? S: TRUE

\  :" move  is  needs 64bits data"
: movimoviq-okay   bufv get1-reg-QN 7 > ;
REGRESS HERE Q: MOVI|X, DX| 1 IL, matches? movimoviq-okay   S: TRUE FALSE
REGRESS HERE Q: MOVI|X, AX| 0 IL, matches? movimoviq-okay   S: TRUE FALSE
REGRESS HERE QN: MOVI|X, AX| 0 IL, 0 {L,} matches? movimoviq-okay   S: TRUE TRUE

\ Optional replace, leave " was  replaced".
: ?movimoviq-replace? movimoviq-okay DUP IF replace THEN ;
REGRESS HERE QN: MOVI|X, DI| 1234 IL, matches? S: TRUE
REGRESS  ?movimoviq-replace? bufv$ @ S: TRUE 6
REGRESS bufc$ $@ .code bufc$ @ S: 10

This example illustrates why I gave up.

>
>> [...]
>> I decided to give up on i86 and concentrate on RISCV.
>
>This kind of thing seems like it could be a significant advantage for
>RISC-V, if people find that the cost-benefit ratio for writing compilers
>for it is better than for 8086, i386, or amd64 (not sure which ISA you
>meant by “i86”).

My compiler source for Intel is generic. It is adjusted by macros for
8086, 80386 and amd64 (and for linux windows etc.)
The  optimiser handles amd64 primarily.

>
>Kragen
-- 
The Chinese government is satisfied with its military superiority over USA.
The next 5 year plan has as primary goal to advance life expectancy
over 80 years, like Western Europe.

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

#135689

albert@spenarnc.xs4all.nl wrote:
> 
> Each replace transform machine code.
> 
> But then look at this:
> \ Instruction that have an implied register not apparent from the
> \ disassembly in `DISS and not AX/AL.
> DATA IMPLIED-CATEGORY  HERE 0 ,
> ' REPZ,      ,          ' STOS,      ,          ' LODS,      ,
> ' SHL,       ,          ' SHR,       ,
> ' SCAS,      ,          ' CMPS,      ,          ' MOVS,      ,
> ' OUTS,      ,          ' INS,       ,          ' OUT|D,     ,
> ' IN|D,      ,          ' SCAS,      ,          ' INT,       ,
> HERE SWAP !
> 
> The first step  in i86 to replace all duplicate instruction with a canonical
> instruction ( there are a dozen ways to move AX to BX), totally
> unnecessary on RISCV.

Hmm.  There are least 4 different ways to provide a constant to
a Risc-V instruction, which are applicable depends on the size of
the constant.  And for several constants size is known only after
code is linked, that is when all addresses are resolved.  And one
may need two extra registers to generate 64-bit constant.  On x86
one can put 32-bit constant in almost any instruction and one
register is enough to load into it arbitrary 64-bit constant.

Concerning moves, AFAICS all the following preform move from
s0 to s1:

     add s1, x0, s0
     or s1, x0, s0
     xor s1, x0, s0
     addi s1, s0, 0
     ori s1, s0, 0
     xori s1, s0, 0
     andi s1, s0, -1
     slli s1, s0, 0

If you add to that possibility of using compressed enconding
you get several additional possiblities (which are available
or not depending on exact registers that you use).

> I decided to give up on i86 and concentrate on RISCV.
> I handled the regular stack in i86 with push and pops, but
> I succeeded to replace all return stack access with registers.
> If in RISCV I handle the regular stack to move to registers
> in a similar fashion with the return stack I have a feasible
> optimiser with little effort.

On Amd64 one can do a lot with a single instruction.  Chosing
efficient instructions takes effort, but it pays. AFAICS on
Risc-V push and pop needs two instructions, not bad from size
point of view as both can be 16-bit instructions.  But there
is a question how much time is needed by the CPU to execute
them.  On Amd64 one can usefully delay updates to data stack
pointer.  Theortically one could try the same game on Risc-V,
but currently I am just dully generating 2 instructions for
every pop or push.

-- 
                              Waldek Hebisch

[toc] | [prev] | [standalone]

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

csiph-web