GCC front-end for FORTH?
Enquirer
GCC, the GNU Compiler Collection currently has front ends for:
C
C++
Objective-C
Fortran
Java
Ada
Macro Assembly
Under develobment are GCC front ends for:
BASIC (FreeBASIC project)
Pascal
Cobol
Modula-2
PL/1
Unified Parallel C (UPC).
VHDL
Mercury
My question is, why no GCC front-end for FORTH?
How hard can it be?
Jerry Avins
Very. Forth is compiles according to an entirely different paradigm. It
BNF is a poor fit to Forth.
Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
John Passaniti
>> My question is, why no GCC front-end for FORTH?
>> How hard can it be?
>
> Very. Forth is compiles according to an entirely different paradigm. It
> BNF is a poor fit to Forth.
The purpose of a GCC front end is to take some language and build a
representation of the program that is suitable for optimization and
finally compiling into a target machine code. There is no requirement
that a GCC front end depend on a BNF representation to drive compilation.
I can easily imagine someone creating a GCC front-end for Forth. The
front end would be, essentially, a Forth interpreter that emitted data
declarations that built a dictionary and code declarations that after
going through the various passes would generate code for the target
machine. There is nothing magical about this-- a GCC front end can
freely parse anything using any method it wishes. What matters is the
output of the front end, not the parsing strategy.
The resulting code would be a static application that couldn't be
extended at runtime, but that covers quite a lot of real-world Forth
applications. For Forth applications that needed runtime extension, the
runtime library could (again) have a small Forth embedded.
The Beez'
> I can easily imagine someone creating a GCC front-end for Forth. The
> front end would be, essentially, a Forth interpreter that emitted data
> declarations that built a dictionary and code declarations that after
> going through the various passes would generate code for the target
> machine. There is nothing magical about this-- a GCC front end can
> freely parse anything using any method it wishes. What matters is the
> output of the front end, not the parsing strategy.
>
> The resulting code would be a static application that couldn't be
> extended at runtime, but that covers quite a lot of real-world Forth
> applications. For Forth applications that needed runtime extension, the
> runtime library could (again) have a small Forth embedded.
static program, since it has no dictionary (just a symbol table) and
no text interpreter. I've thought a long time about using the 4tH way
to create a GCC frontend, just never found the time. I really think it
could be done.
Hans Bezemer
Andrew Haley
OK, as a gcc maintainer I suppose I should respond.
Firstly, it's technically very difficult. gcc does use the stack, but
it doesn't expose it to the programmer. Getting the gcc back ends to
generate efficient code for Forth would be hard.
Secondly, it's pointless: we already have gforth.
Thirdly, Forth is an interactive language, whereas gcc is an ahead of
time batch compiler. You'd lose interaction.
Andrew.
John Passaniti
> OK, as a gcc maintainer I suppose I should respond.
>
> Firstly, it's technically very difficult. gcc does use the stack, but
> it doesn't expose it to the programmer. Getting the gcc back ends to
> generate efficient code for Forth would be hard.
This doesn't make sense to me so I'd like additional detail. The
language compiled by a front end to GCC may not expose the stack to the
programmer. But the front end's output (trees and eventually RTL)
certainly does express operations that manipulate the stack. What
specifically is the difficulty.
> Secondly, it's pointless: we already have gforth.
gforth doesn't generate machine code. The benefit of using the GCC
optimizer and code generators is the point.
> Thirdly, Forth is an interactive language, whereas gcc is an ahead of
> time batch compiler. You'd lose interaction.
No, you wouldn't. Just as any C program can gain interaction by adding
on an interpreter, the runtime library can provide a run-time compiler.
The code generated by the interpreter doesn't need to be the same
quality as the ahead-of-time compiled code.
Andrew Haley
> Andrew Haley wrote:
>> OK, as a gcc maintainer I suppose I should respond.
>>
>> Firstly, it's technically very difficult. gcc does use the stack,
>> but it doesn't expose it to the programmer. Getting the gcc back
>> ends to generate efficient code for Forth would be hard.
> This doesn't make sense to me so I'd like additional detail. The
> language compiled by a front end to GCC may not expose the stack to
> the programmer. But the front end's output (trees and eventually
> RTL) certainly does express operations that manipulate the stack.
> What specifically is the difficulty.
Trees don't express operations that directly manipulate the stack:
they don't refer to stacks at all. They are, more or less, a somewhat
lowered form of C. To generate code for DUP, for example, you'd do
more or less the same as generating C from Forth and then compiling
that. You'd generate something like:
sp--; *sp = tos;
You'd have to manipulate the return stack in a similar way. While
this undoubtedly would work, it wouldn't generate particularly
efficient code.
Also, Forth words can consume and generate arbitrary numbers of
argumentsm so the usual call conventions probably wouldn't work. I
guess the best way to handle that would be to pass SP as an argument,
but that would require some experimenting to determine what would work
best.
It is possible, of course, to do optimization in the Forth front end,
and this would allow you to generate trees that didn't touch memory so
much. This would help, but I suspect you might as well generate C and
compile that.
>> Thirdly, Forth is an interactive language, whereas gcc is an ahead
>> of time batch compiler. You'd lose interaction.
> No, you wouldn't. Just as any C program can gain interaction by
> adding on an interpreter, the runtime library can provide a run-time
> compiler.
OK.
Andrew.
John Passaniti
>> This doesn't make sense to me so I'd like additional detail. The
>> language compiled by a front end to GCC may not expose the stack to
>> the programmer. But the front end's output (trees and eventually
>> RTL) certainly does express operations that manipulate the stack.
>> What specifically is the difficulty.
>
> Trees don't express operations that directly manipulate the stack:
> they don't refer to stacks at all. They are, more or less, a somewhat
> lowered form of C.
It was my understanding that the trees generated by the front-end have
the ability to create arbitrary extensions. For example, the Java
front-end presumably has a tree-level method call, even though no such
concept exists in C. Another example would be the Mercury front-end,
which would seem to need new tree extensions to support the declarative
model and unification operations.
> Also, Forth words can consume and generate arbitrary numbers of
> argumentsm so the usual call conventions probably wouldn't work. I
> guess the best way to handle that would be to pass SP as an argument,
> but that would require some experimenting to determine what would work
> best.
I don't think this matters. Many C compilers produce code for other
calling conventions. Windows C compilers can produce code for a Pascal
calling convention. Some embedded C compilers produce code that uses
"compiled stack" calling conventions. All of these place various limits
on the code the programmer writes, but those limits are driven by some
need-- such as to interface with a different language or to reduce
memory footprint.
In much the same way, I can easily see a Forth based on a GCC front-end
placing limits on the Forth programmer. Those limits would likely be
driven by some expected benefit-- such as the ability to call C
functions easily from Forth or the reverse. Whatever.
> It is possible, of course, to do optimization in the Forth front end,
> and this would allow you to generate trees that didn't touch memory so
> much. This would help, but I suspect you might as well generate C and
> compile that.
I think the primary goal of a Forth front-end for GCC would be that the
Forth used as the front-end wouldn't have to invest much (if any) effort
optimizing the code. The goal here would be to take a really simple
tree representation of a Forth program, and leverage the years of
experience behind data flow analysis, optimization, and code generation
that GCC has. When you look at native optimizing Forths, you see (in
general) a lot of optimization effort that is, at least in part,
duplicated by the mechanisms of GCC.
The biggest problem with all this isn't that it can't be done or that
Forth's model presents some huge obstacle to working with a system like
GCC. The biggest problem is GCC itself, which is big, complex, and not
always documented well. At least that was my experience when I looked
at trying to create a back-end for GCC 2.95. Things have hopefully
gotten better now, and the growth of new language front-ends points to a
trend of making GCC far less C-centric than in the past. A Forth
front-end could only help that.
Anton Ertl
>John Passaniti <put-my-firs...@japanisshinto.com> wrote:
>> Andrew Haley wrote:
>>> Firstly, it's technically very difficult. gcc does use the stack,
>>> but it doesn't expose it to the programmer. Getting the gcc back
>>> ends to generate efficient code for Forth would be hard.
>Trees don't express operations that directly manipulate the stack:
>they don't refer to stacks at all. They are, more or less, a somewhat
>lowered form of C. To generate code for DUP, for example, you'd do
>more or less the same as generating C from Forth and then compiling
>that. You'd generate something like:
>
> sp--; *sp = tos;
Come on, you know better. Do you generate such code in GCJ when you
compile a JVM dup? So, no reason to do it in Forth, either. If you
need more inspiration, you could read
<http://www.complang.tuwien.ac.at/projects/rafts.html> and the papers
cited there.
>You'd have to manipulate the return stack in a similar way. While
>this undoubtedly would work, it wouldn't generate particularly
>efficient code.
The return stack is particularly easy, because it has to be balanced
on exiting colon definitions. In any case, once you can deal with an
unbalanced data and FP stack, you can also deal with an unbalanced
return stack.
>Also, Forth words can consume and generate arbitrary numbers of
>argumentsm so the usual call conventions probably wouldn't work. I
>guess the best way to handle that would be to pass SP as an argument,
>but that would require some experimenting to determine what would work
>best.
As long as you don't want to call other languages, there is no need to
use the usual calling conventions. Since Forth requires called words
to be defined first, you need not use a calling convention for most
calls anyway: you can do the calls as is convenient for the callee.
You only need a calling convention for EXECUTE and the like; for that
a calling convention might be to pass most of the stacks in memory,
except the top few elements, and likewise on returning; the stack
pointer would point to the logical top-of-stack.
>It is possible, of course, to do optimization in the Forth front end,
>and this would allow you to generate trees that didn't touch memory so
>much. This would help, but I suspect you might as well generate C and
>compile that.
Yes, that's a project I have on my agenda. The disadvantage over
doing it in a compiler is that the register allocation will be worse
than for what I suggested above.
>>> Thirdly, Forth is an interactive language, whereas gcc is an ahead
>>> of time batch compiler. You'd lose interaction.
>
>> No, you wouldn't. Just as any C program can gain interaction by
>> adding on an interpreter, the runtime library can provide a run-time
>> compiler.
GCJ/CIJ-style. Does not appear attractive to me; I don't want to have
to deal with ahead-of-time complexities.
- 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 2007: http://www.complang.tuwien.ac.at/anton/euroforth2007/
Anton Ertl
>In much the same way, I can easily see a Forth based on a GCC front-end
>placing limits on the Forth programmer. Those limits would likely be
>driven by some expected benefit-- such as the ability to call C
>functions easily from Forth or the reverse.
There is no need to place limits on the Forth programmer for that.
Most Forth systems can do that already.
>I think the primary goal of a Forth front-end for GCC would be that the
>Forth used as the front-end wouldn't have to invest much (if any) effort
>optimizing the code. The goal here would be to take a really simple
>tree representation of a Forth program, and leverage the years of
>experience behind data flow analysis, optimization, and code generation
>that GCC has. When you look at native optimizing Forths, you see (in
>general) a lot of optimization effort that is, at least in part,
>duplicated by the mechanisms of GCC.
I doubt that. AFAIK even the better Forth native-code compilers
(i.e., VFX and iForth) don't do much of what is done by the optimizer
part of GCC; a lot of what they do would have to be done in the front
end; the rest is in the back end. I also doubt that the optimizer
will buy much for Forth code. One benefit of doing a front end for
GCC would be that one would get a large number of back-ends.
Andrew Haley
> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>John Passaniti <put-my-firs...@japanisshinto.com> wrote:
>>> Andrew Haley wrote:
>>>> Firstly, it's technically very difficult. gcc does use the stack,
>>>> but it doesn't expose it to the programmer. Getting the gcc back
>>>> ends to generate efficient code for Forth would be hard.
> ...
>>Trees don't express operations that directly manipulate the stack:
>>they don't refer to stacks at all. They are, more or less, a somewhat
>>lowered form of C. To generate code for DUP, for example, you'd do
>>more or less the same as generating C from Forth and then compiling
>>that. You'd generate something like:
>>
>> sp--; *sp = tos;
> Come on, you know better. Do you generate such code in GCJ when you
> compile a JVM dup?
No, of course not, but Java's stack is local to the function, and Java
stack operations can trivially be converted to a bunch of local
variables. A stack that is unbounded and shared between functions has
to be represented somehow.
>>Also, Forth words can consume and generate arbitrary numbers of
>>argumentsm so the usual call conventions probably wouldn't work. I
>>guess the best way to handle that would be to pass SP as an argument,
>>but that would require some experimenting to determine what would work
>>best.
> As long as you don't want to call other languages, there is no need
> to use the usual calling conventions.
Well, I already answered that: I'm assuming we're not writing a new
back end.
Andrew.
Anton Ertl
>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>>To generate code for DUP, for example, you'd do
>>>more or less the same as generating C from Forth and then compiling
>>>that. You'd generate something like:
>>>
>>> sp--; *sp = tos;
>
>> Come on, you know better. Do you generate such code in GCJ when you
>> compile a JVM dup?
>
>No, of course not, but Java's stack is local to the function, and Java
>stack operations can trivially be converted to a bunch of local
>variables. A stack that is unbounded and shared between functions has
>to be represented somehow.
Yes, but the common case is that the stack depth is statically known
and stack accesses can be trivially converted to pseudo-variables. In
the few cases where this does not hold, the front end has to insert
some stores/loads to the unbounded stack in memory; it's all explained
in <http://www.complang.tuwien.ac.at/projects/rafts.html>.
>> As long as you don't want to call other languages, there is no need
>> to use the usual calling conventions.
>
>Well, I already answered that: I'm assuming we're not writing a new
>back end.
I don't know gcc well enough to comment on the dependencies between
the back end and the calling convention; but even if they are strong,
it should be possible to treat calls between Forth words as something
lighter-weight than a calling-convention call, no?
Andrew Haley
> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>>> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>>>To generate code for DUP, for example, you'd do
>>>>more or less the same as generating C from Forth and then compiling
>>>>that. You'd generate something like:
>>>>
>>>> sp--; *sp = tos;
>>
>>> Come on, you know better. Do you generate such code in GCJ when you
>>> compile a JVM dup?
>>
>>No, of course not, but Java's stack is local to the function, and Java
>>stack operations can trivially be converted to a bunch of local
>>variables. A stack that is unbounded and shared between functions has
>>to be represented somehow.
> Yes, but the common case is that the stack depth is statically known
> and stack accesses can be trivially converted to pseudo-variables.
> In the few cases where this does not hold, the front end has to
> insert some stores/loads to the unbounded stack in memory; it's all
> explained in <http://www.complang.tuwien.ac.at/projects/rafts.html>.
I already said
> It is possible, of course, to do optimization in the Forth front
> end, and this would allow you to generate trees that didn't touch
> memory so much. This would help,
which is another way to say exactly the same thing. I was explaining
to John why the naive approach won't give top-quality results.
>>> As long as you don't want to call other languages, there is no need
>>> to use the usual calling conventions.
>>
>>Well, I already answered that: I'm assuming we're not writing a new
>>back end.
> I don't know gcc well enough to comment on the dependencies between
> the back end and the calling convention;
The back end contains the code that handles the particular hardware
and the particular calling conventions. In the case where a processor
(such as the x86) has more than one calling convention, alternative
routines to generate entry and exit sequences are provided. This
logic has to be in the back-end, really, because it's generally
impossible to describe a calling convention without machine
dependencies. Some common parts of the logic are in the core
compiler, but there are such great differences between the various
calling conventions and hardware architectures that's not generally
possible.
> but even if they are strong, it should be possible to treat calls
> between Forth words as something lighter-weight than a
> calling-convention call, no?
I guess this question amounts to "is it possible to stop the back-end
from generating ABI-compliant entry and exit sequences without
altering the back-end?", to which I suspect the answer is no.
There is a trick where you can call a subroutine within the context of
the current function by doing something like
tmp = &&bar;
goto foo;
bar:
...
foo:
...
goto tmp;
and this does indeed get you a super-lightweight call: no prologue,
epilogue, or local variables. However, if you were to do this very
much I think code quality would suffer because of the complex data
flow and the large number of temporaries.
Andrew.
Guy Macon
John Passaniti wrote:
>I think the primary goal of a Forth front-end for GCC would be that the
>Forth used as the front-end wouldn't have to invest much (if any) effort
>optimizing the code. The goal here would be to take a really simple
>tree representation of a Forth program, and leverage the years of
>experience behind data flow analysis, optimization, and code generation
>that GCC has. When you look at native optimizing Forths, you see (in
>general) a lot of optimization effort that is, at least in part,
>duplicated by the mechanisms of GCC.
>
>The biggest problem with all this isn't that it can't be done or that
>Forth's model presents some huge obstacle to working with a system like
>GCC. The biggest problem is GCC itself, which is big, complex, and not
>always documented well. At least that was my experience when I looked
>at trying to create a back-end for GCC 2.95. Things have hopefully
>gotten better now, and the growth of new language front-ends points to a
>trend of making GCC far less C-centric than in the past. A Forth
>front-end could only help that.
It would also help me to sell the idea of using Forth to management.
having a Forth front end for GCC would do a lot to legitimize Forth
in the minds of those who are already using the GCC toolchain.
References:
Writing a GCC Front End ("Language designers rejoice! Now
it's easier to put a front end for your language onto GCC.")
[ http://www.linuxjournal.com/article/7884 ]
Toy Example Language ("a small language intended to demonstrate
some of the basic concepts in programming a language front-end.")
[ http://www.eskimo.com/~johnnyb/computers/toy/ ]
Gcc frontend links
[ http://projects.almad.net/gcc-algol/wiki/GccFrontendLinks ]
GCC Frontend HOWTO (From 2002 -- may be obsolete)
http://tldp.org/HOWTO/GCC-Frontend-HOWTO.html
http://www.linux.org/docs/ldp/howto/GCC-Frontend-HOWTO.html#toc1
--
Guy Macon
<http://www.guymacon.com/>
Anton Ertl
>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>> but even if they are strong, it should be possible to treat calls
>> between Forth words as something lighter-weight than a
>> calling-convention call, no?
>
>I guess this question amounts to "is it possible to stop the back-end
>from generating ABI-compliant entry and exit sequences without
>altering the back-end?", to which I suspect the answer is no.
I don't mind the back-end generating this stuff somewhere, but it
would lead to far-from-optimal performance if it generated that stuff
for every call and return.
>There is a trick where you can call a subroutine within the context of
>the current function by doing something like
>
> tmp = &&bar;
> goto foo;
> bar:
>
> ...
>
> foo:
> ...
> goto tmp;
>
>and this does indeed get you a super-lightweight call: no prologue,
>epilogue, or local variables.
I would prefer it if one could get the backend to use the native call
and return instructions; that would save the expense of the
"tmp=&&bar", and more importantly, would use the CPU's return stack to
predict the return address (rather than using the general indirect
branch predictor which generally misses much more often).
>However, if you were to do this very
>much I think code quality would suffer because of the complex data
>flow and the large number of temporaries.
Yes, I guess this would only work if there was a way for the front end
to specify the live range. Hmm, I know how to kill a variable in gcc,
but I am not sure this could scale.
Getting away from this probably pretty theoretical discussion, you
claimed that you have Gforth, which reminded me of the discussion on
gcc progress we had in June/July
(<2007Jun2...@mips.complang.tuwien.ac.at> ff.).
I have recently become aware of the paper "Towards GCC as a compiler
for multiple VMs" by G. Prokopski and C. Verbrugge, that was presented
shortly after our discussion at the GCC Summit 2007
<https://ols2006.108.redhat.com/2007/GCC-Reprints/GCC2007-Proceedings.pdf>.
This paper presents a solution to the main problem we have had with
gcc in the last few years. Do you know how the paper was received,
and if there is any chance that an extension like that proposed in the
paper will make it into gcc?
Andrew Haley
> Getting away from this probably pretty theoretical discussion, you
> claimed that you have Gforth, which reminded me of the discussion on
> gcc progress we had in June/July
> (<2007Jun2...@mips.complang.tuwien.ac.at> ff.).
> I have recently become aware of the paper "Towards GCC as a compiler
> for multiple VMs" by G. Prokopski and C. Verbrugge, that was presented
> shortly after our discussion at the GCC Summit 2007
> <https://ols2006.108.redhat.com/2007/GCC-Reprints/GCC2007-Proceedings.pdf>.
> This paper presents a solution to the main problem we have had with
> gcc in the last few years. Do you know how the paper was received,
I have newer heard a mention of that paper from any gcc maintainer. I
suppose the reason for that is that it is somewhat remote from the
day-to-day maintenance of the compiler, and not really relevant to
what most maintainers do.
> and if there is any chance that an extension like that proposed in
> the paper will make it into gcc?
That's an interesting question, and probably has as many answers as
there are gcc maintainers. Thanks for the reference: I haven't had
time to study the paper yet.
Andrew.
Andrew Haley
> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
> Getting away from this probably pretty theoretical discussion, you
> claimed that you have Gforth,
I'm not sure what you mean by this.
> which reminded me of the discussion on gcc progress we had in
> June/July (<2007Jun2...@mips.complang.tuwien.ac.at> ff.).
> I have recently become aware of the paper "Towards GCC as a compiler
> for multiple VMs" by G. Prokopski and C. Verbrugge, that was presented
> shortly after our discussion at the GCC Summit 2007
> <https://ols2006.108.redhat.com/2007/GCC-Reprints/GCC2007-Proceedings.pdf>.
> This paper presents a solution to the main problem we have had with
> gcc in the last few years. Do you know how the paper was received,
> and if there is any chance that an extension like that proposed in
> the paper will make it into gcc?
OK, I've read it now, IMO the solution provided is incomplete. I'll
mention two problems.
Firstly, there is no way presented to solve the problem of PC-relative
access to data. gcc uses this a great deal: for position-independent
code on most targets and as the only way to load address constants on
some.
Secondly, the paper is almost entirely about control flow issues but
there are data flow issues that must also be solved if the technique
is to be generally reliable.
In particular, say you have a source variable V. At any point in the
generated code, loc(V) is the location where the value of the source
variable is stored. loc(V) is not constant: it may be in different
memory locations at different points in the code, it may be a
register, or it may not exist at all if the compiler eliminates V.
The compiler can do all of these things because it has an accurate
data flow graph of the function. When chunks of code are concatenated
to form a superinstruction, the data flow graph is no longer valid.
Also, gcc's attempts to re-use stack slots may result in broken code
when concatenated because its knowledge about variable lifetimes is
incorrect.
It is possible partially to solve this second problem by placing all
the variables used in explicitly named register variables (which by
definition cannot move) but this is not a general solution.
Assuming that I'm right about the problems, the question boils down to
whether a partially-broken implementation of this idea could be
checked into the mainline sources, and whether gcc maintainers would
agree to be bound by any guarantees not to break it. I expect that
there would be some reluctance.
Andrew.
Anton Ertl
>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>
>> Getting away from this probably pretty theoretical discussion, you
>> claimed that you have Gforth,
>
>I'm not sure what you mean by this.
You wrote <13ie003...@news.supernews.com>:
|Secondly, it's pointless: we already have gforth.
>> I have recently become aware of the paper "Towards GCC as a compiler
>> for multiple VMs" by G. Prokopski and C. Verbrugge, that was presented
>> shortly after our discussion at the GCC Summit 2007
>> <https://ols2006.108.redhat.com/2007/GCC-Reprints/GCC2007-Proceedings.pdf>.
>> This paper presents a solution to the main problem we have had with
>> gcc in the last few years. Do you know how the paper was received,
>> and if there is any chance that an extension like that proposed in
>> the paper will make it into gcc?
>
>OK, I've read it now, IMO the solution provided is incomplete. I'll
>mention two problems.
>
>Firstly, there is no way presented to solve the problem of PC-relative
>access to data. gcc uses this a great deal: for position-independent
>code on most targets and as the only way to load address constants on
>some.
On nearly all targets that I have had contact with, gcc does so-called
position-independent code through a global pointer, and there is no
PC-relative access to data. The only exception I know is AMD64. Even
there, this is not a problem as long as we don't use global variables.
Apart from not using globals at all, we could work around this by
turning the global variables into thread-local variables, which is
probably the right thing to do in a multi-threading variant of Gforth
anyway.
If there are architectures/ABIs that are worse in this respect than
AMD64, I have not encountered them. And I guess that the code-copying
techniques for speeding up Gforth are not as interesting on those
architectures, because they have a lower branch misprediction penalty
than desktop and server CPUs (making the benefit of code-copying
techniqes smaller) and the systems have probably less memory (making
the cost of code-copying techniques more significant).
In any case, if it does not work on some architecture, we can easily
fall back to regular threaded code. But it would be very useful to
have this feature on architectures where it would work.
>Secondly, the paper is almost entirely about control flow issues but
>there are data flow issues that must also be solved if the technique
>is to be generally reliable.
My guess is that the paper has concentrated on control-flow, because
gcc "progress" has made problems there. Data flow has not broken by
changes in gcc in any of the versions that we have tried these
techniques with (about 2.7.2-4.2.0).
>In particular, say you have a source variable V. At any point in the
>generated code, loc(V) is the location where the value of the source
>variable is stored. loc(V) is not constant: it may be in different
>memory locations at different points in the code, it may be a
>register, or it may not exist at all if the compiler eliminates V.
>The compiler can do all of these things because it has an accurate
>data flow graph of the function. When chunks of code are concatenated
>to form a superinstruction, the data flow graph is no longer valid.
>Also, gcc's attempts to re-use stack slots may result in broken code
>when concatenated because its knowledge about variable lifetimes is
>incorrect.
That's not a problem: Consider the VM instruction:
plus:
ip++;
tos += *sp++;
end_plus:
goto *(*ip);
The addresses of both plus and end_plus are taken, so any goto * can
jump to either, so if variables are alive at any of these labels, they
have to reside at the same location. Since end_plus is directly
followed by a goto * without any variable writes in between, any
variable that is alive at any start of a VM instruction, is also alive
at end_plus; therefore the relevant variables reside in the same
locations at all these labels, and one can concatenate the code
safely (wrt variable locations).
In other words: the data flow information of the compiler is reflected
in the way we use this code. We just eliminate some "goto *"s with
our technique, the data flow does not change.
Andrew Haley
> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>>> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>>>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>>
>>> Getting away from this probably pretty theoretical discussion, you
>>> claimed that you have Gforth,
>>
>>I'm not sure what you mean by this.
> You wrote <13ie003...@news.supernews.com>:
> |Secondly, it's pointless: we already have gforth.
Oh, I see. By "we", I meant "the community", not me personally or any
organization to which I belong.
>>> I have recently become aware of the paper "Towards GCC as a compiler
>>> for multiple VMs" by G. Prokopski and C. Verbrugge, that was presented
>>> shortly after our discussion at the GCC Summit 2007
>>> <https://ols2006.108.redhat.com/2007/GCC-Reprints/GCC2007-Proceedings.pdf>.
>>> This paper presents a solution to the main problem we have had with
>>> gcc in the last few years. Do you know how the paper was received,
>>> and if there is any chance that an extension like that proposed in
>>> the paper will make it into gcc?
>>
>>OK, I've read it now, IMO the solution provided is incomplete. I'll
>>mention two problems.
>>
>>Firstly, there is no way presented to solve the problem of PC-relative
>>access to data. gcc uses this a great deal: for position-independent
>>code on most targets and as the only way to load address constants on
>>some.
> On nearly all targets that I have had contact with, gcc does
> so-called position-independent code through a global pointer, and
> there is no PC-relative access to data.
Yes, but you have to get that global pointer, and that's through a
PC-relative load in most cases. The only way to avoid that is though
some (Power PC style) heroics involving fat function pointers. I see
your point, though: we'd hope that loading the global pointer is never
done inside a copyable chunk.
> The only exception I know is AMD64. Even there, this is not a
> problem as long as we don't use global variables.
Or string constants, or exception handlers, etc. But yes, if you're
willing to forego all data refs it might work on some architectures.
With that caveat ...
> Apart from not using globals at all, we could work around this by
> turning the global variables into thread-local variables, which is
> probably the right thing to do in a multi-threading variant of
> Gforth anyway.
In some cases it will be, yes. Except that thread-local variables
also use PC-relative loads on some targets! :-)
> If there are architectures/ABIs that are worse in this respect than
> AMD64, I have not encountered them. And I guess that the
> code-copying techniques for speeding up Gforth are not as
> interesting on those architectures, because they have a lower branch
> misprediction penalty than desktop and server CPUs (making the
> benefit of code-copying techniqes smaller) and the systems have
> probably less memory (making the cost of code-copying techniques
> more significant).
Perhaps so, but I was rather hoping that this technique might be
useful on those architectures where the community doesn't have ready
access to free JITs. Such as ARM, for example, where
return 0xff001234;
generates:
0: e59f0000 ldr r0, [pc, #0] ; 8 <xx+0x8>
4: e12fff1e bx lr
8: ff001234 .word 0xff001234
> In any case, if it does not work on some architecture, we can easily
> fall back to regular threaded code. But it would be very useful to
> have this feature on architectures where it would work.
OK. But you see what I'm getting at: this isn't a general solution to
the problem, and the fact that there is a number of ifs, buts, and
gotchas and things that aren't allowed is a serious impediment to it
being accepted.
Right, I see. To put it in data flow analysis terminology, if V has a
definition in a chunk, that definition of V reaches every other chunk.
This is because there is an execution path from the final definition
of V in every chunk to every other chunk that has a use of V.
Andrew.
Anton Ertl
>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>>Firstly, there is no way presented to solve the problem of PC-relative
>>>access to data. gcc uses this a great deal: for position-independent
>>>code on most targets and as the only way to load address constants on
>>>some.
>
>> On nearly all targets that I have had contact with, gcc does
>> so-called position-independent code through a global pointer, and
>> there is no PC-relative access to data.
>
>Yes, but you have to get that global pointer, and that's through a
>PC-relative load in most cases. The only way to avoid that is though
>some (Power PC style) heroics involving fat function pointers. I see
>your point, though: we'd hope that loading the global pointer is never
>done inside a copyable chunk.
Well looking at Alpha code, it actually does happen now and then,
e.g., in the code for MOVE:
Gforth's examination of this primitive says (gforth --debug):
move 0-0 43 0x12000585c 0x12000b19c 0x12000585c len= 44 rest= 4 send=0
non_reloc: engine1!=engine2 offset 32
Let's look at these two code fragments:
0x12000585c: 0x12000b19c:
31 14 18 bis, 31 14 18 bis,
17 16 11 ldq, 17 16 11 ldq,
16 8 11 ldq, 16 8 11 ldq,
1 24 11 lda, 1 24 11 lda,
27 -32200 29 ldq, 27 -32200 29 ldq,
10 8 10 lda, 10 8 10 lda,
31 1 11 bis, 31 1 11 bis,
26 27 0 jsr, 26 27 0 jsr,
29 4 26 ldah, 29 3 26 ldah, \ difference
29 -16948 29 lda, 29 25740 29 lda, \ difference
14 0 11 ldq, 14 0 11 ldq,
1 -8 10 ldq, 1 -8 10 ldq,
So yes, the two instructions that reload the global pointer are
PC-relative of a kind (they are relative to the return address of the
jsr). Gforth notices that and does not copy this fragment, but uses
ordinary threaded code to execute it instead.
Still, Gforth uses code-copying for those primitives that don't have
this problem, resulting in a nice speedup: On an 800MHz 21264a:
sieve bubble matrix fib
0.911 1.167 1.235 1.031 gforth-fast
3.384 3.601 2.582 3.874 gforth-fast --no-dynamic
>Except that thread-local variables
>also use PC-relative loads on some targets! :-)
How does that work?
>Perhaps so, but I was rather hoping that this technique might be
>useful on those architectures where the community doesn't have ready
>access to free JITs. Such as ARM
Code-copying works pretty nicely for Gforth on ARM, similar to other
architectures: basically, primitives that call a function are not
copyable, most others are. Here are some speed results from a 600MHz
XScale-IOP80321 rev 2 (v5l):
sieve bubble matrix fib
1.860 2.320 1.820 2.140 gforth-fast
3.430 3.840 3.530 4.000 gforth-fast --no-dynamic
The lower speed factor compared to the 21264a is due to the lower
branch misprediction penalty on this CPU, not due to less stuff being
copyable.
>OK. But you see what I'm getting at: this isn't a general solution to
>the problem, and the fact that there is a number of ifs, buts, and
>gotchas and things that aren't allowed is a serious impediment to it
>being accepted.
The same (except the thing about the impediment) can be said of asm
statements, explicit register allocation, and other good features of
gcc.
Actually, the control-flow part of the extension was implicitly
present in gcc before 3.1. Only then gcc acquired "optimizations"
that broke that.
Andrew Haley
> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>>> Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>>>>Firstly, there is no way presented to solve the problem of PC-relative
>>>>access to data. gcc uses this a great deal: for position-independent
>>>>code on most targets and as the only way to load address constants on
>>>>some.
>>
> PC-relative of a kind (they are relative to the return address of the
> jsr). Gforth notices that and does not copy this fragment, but uses
> ordinary threaded code to execute it instead.
OK, but now I'm confused. How does Gforth notice that the fragment
isn't copyable? Does it disassemble the generated code?
>>Except that thread-local variables
>>also use PC-relative loads on some targets! :-)
> How does that work?
Some targets (ARM again) use PC-relative loads to get integer
constants: in this case the constant is an offset from the thread-local
base pointer.
>>Perhaps so, but I was rather hoping that this technique might be
>>useful on those architectures where the community doesn't have ready
>>access to free JITs. Such as ARM
> Code-copying works pretty nicely for Gforth on ARM, similar to other
> architectures: basically, primitives that call a function are not
> copyable, most others are.
OK, but how do you know if gcc has done something that makes a chunk
not copyable? Again, disassembly?
Andrew.
Anton Ertl
>Anton Ertl <an...@mips.complang.tuwien.ac.at> wrote:
>> the two [ Alpha ] instructions that reload the global pointer are
>> PC-relative of a kind (they are relative to the return address of the
>> jsr). Gforth notices that and does not copy this fragment, but uses
>> ordinary threaded code to execute it instead.
>
>OK, but now I'm confused. How does Gforth notice that the fragment
>isn't copyable? Does it disassemble the generated code?
No. It generates two copies of the code, one with some spacing
between the code of each primitive, the other without that spacing.
If the two instances of the code for the primitive are equal, it is
relocatable, if not, Gforth treats it as non-relocatable.
That's what the lines
move 0-0 43 0x12000585c 0x12000b19c 0x12000585c len= 44 rest= 4 send=0
non_reloc: engine1!=engine2 offset 32
were about: The first address given is of the first instance, the
second of the second instance (and then we get the first instance
again; in some further work we are using a third instance to notice
where the literals are in the code). The part to be copied (without
dispatch) is 44 bytes long, but at byte 32 Gforth noticed a difference
between the two instances.
Guy Macon
It seems to me that much of this discussion assumes that efficiency
is a requirement for a GCC front-end supporting FORTH. How hard
would it be if you optimized for ease of development rather than
execution speed?