Re: new front-end: ksi + few questions

Re: new front-end: ksi + few questions

[Fergus Henderson]

[I'm cross-posting this to both the c-- and gcc mailing lists]

On 21-Sep-2001, Doug Moen <doug@moens.org> wrote:
> Ksi is pretty cool.  It's just a thin wrapper around the GCC tree language,
> with a lispy syntax.  It's primitive, poorly documented, not quite ready
> for prime time.  It doesn't meet my requirements, because AFAIK GCC still
> doesn't provide a fully general tail call mechanism, so I'd have to use
> the trampoline trick with Ksi.

In GCC >= 3.0, GCC now supports "sibling calls", i.e. tail call optimization
for tail calls that are not directly recursive, but which instead call
a different function.

There are still some limitations, e.g. (1) it doesn't work for varargs
function calls, (2) it doesn't work if you have taken the address of a
local variable, and (3) I think it doesn't always work if the caller
argument types don't match the callee argument types.  But the situation
is a lot better than in GCC < 3.0.

For (2) it is fairly straight-forward to add a hook to GCC's interface
with the language front-end to allow the front-end to tell GCC to do
an optimized tail call even if the optimization appears unsafe, due to
taking the address of local variables.  I have a patch floating around
somewhere against a pre-3.0 version of GCC that implements that, although
I have yet to merge that change into 3.0 or the latest development sources,
or to test it thoroughly.

Problems (1) and (3) are very hard to solve with standard calling
conventions, but someone else on the GCC list said they were working on
implementing a special calling convention that would solve those problems.
(Routines using this calling convention would have to be marked with
a function attribute and would not be compatible with the standard
calling convention.)  I don't know how far that work has progressed.

> What would be cooler is if the GCC internals were extended to provide
> the expressive power of C--.

I proposed on the GCC list a few months ago that GNU C be extended with
support for forcing tail calls even if the address of a local variable
was taken.  There was considerable discussion, some in favour of it, some
against, but the eventual concensus was that it should first be added
as a hook in GCC's interface with the compiler front-end, and only after
that change was integrated into GCC should we consider extending GNU C.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: < http://www.cs.mu.oz.au/~fjh >  |     -- the last words of T. S. Garp.

Re: new front-end: ksi + few questions

[Michal Moskal]

On Wed, Sep 19, 2001 at 03:23:31PM +1000, Fergus Henderson wrote:
> On 10-Sep-2001, Michal Moskal <malekith@pld.org.pl> wrote:
> > I'm writing a new front-end for GCC. My goal is to provide very
> > simple language, suitable as a target for some other compiler,
> > machine-independent assembler.
> 
> How and why does your intermediate language differ from "C--"
> (see < http://www.cminusminus.org >)?

It's more complex. Howver its lexical structure and grammar is simpler.
At the moment Ksi supports structers and unions (C-- does not, and I
guess it won't). While implementing structers in any comiler if target
understands pointers is rather simple, it is crucial for debuger. Ksi is
also capable of outputting line number information, so basic interface to
debuger is simple to create. OTOH C-- is meant os target for functional
languages, possibly regular debugger (as gdb) won't work very well with
them, so there is no need to interface it? I don't know.

And most important thing: Ksi works, its working gcc front end,
while I was even unable to compile c-- compiler written in SML (even
this fact limits it, SML/NJ hasn't been ported to as much hosts as
GCC).

I think whatever it would be good idea to make Ksi type-safe. Arrays
would be absolute must then, but I guess it could be nice to be sure
that this program won't segfault... Maybe it will be just typesafe
version.

> > The language itself is more or less
> > textual representation of syntax trees generated by all front-ends.
> 
> OK, so my next question is how does it differ from "treelang"
> (see < http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01461.html >)?

Of course I didn't know about it, I will check this out extensivly :) 
Anyway treelang seems to be rather referance language, while Ksi is 
meant to be practical.

-- 
: Michal ``,/\/\,       '' Moskal    | |            : GCS {C,UL}++++$
:          |    |alekith      @    |)|(| . org . pl : {E--, W, w-,M}-
:                                  |                : {b,e>+}++ !tv h
: Current project:   ftp://aleph-0.dhs.org/pub/ksi/ : PLD Team member

Re: new front-end: ksi + few questions

[Fergus Henderson]

On 10-Sep-2001, Michal Moskal <malekith@pld.org.pl> wrote:
> I'm writing a new front-end for GCC. My goal is to provide very
> simple language, suitable as a target for some other compiler,
> machine-independent assembler.

How and why does your intermediate language differ from "C--"
(see < http://www.cminusminus.org >)?

> The language itself is more or less
> textual representation of syntax trees generated by all front-ends.

OK, so my next question is how does it differ from "treelang"
(see < http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01461.html >)?

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: < http://www.cs.mu.oz.au/~fjh >  |     -- the last words of T. S. Garp.

new front-end: ksi + few questions

[Michal Moskal]

Hello,

I'm writing a new front-end for GCC. My goal is to provide very
simple language, suitable as a target for some other compiler,
machine-independent assembler. The language itself is more or less
textual representation of syntax trees generated by all front-ends.

Of course somebody might ask why not use tree interface directly?
Hmmm... I'm writing ksi compiler since a week or so. I will spent
few next weeks/months testing it and adding some neat features. 
This is time you won't have to spent :)

Also interfacing trees from, let's say SML, or OCAML can be hard.

Lexical structure of lanuage is verysimple, reasembling mixture
of C (string constants, comments (// was choosen, so we are able
to use cpp, if there are any good reasons to do so)) and Lisp.

Here is an example:

---CUT---
!version 0

[unit
// int excl(int x)
// {
//   if (x == 0)
//     return 1;
//   else
//     return x * excl(x - 1);
// }
  (func public (type int 32) excl
    (parm (var (type int 32) x) (nil))
    (bind (cond (bin eq (ref x) (const (type int 32) 0))
      (return (modify (result) (const (type int 32) 1)))
      (return (modify (result) 
        (bin mult (ref x) (call excl [parm 
          (bin minus (ref x) (const (type int 32) 1))])))))))

// extern int printf(void *, ...);
  (func extern (type int 32) printf 
    (parm (var (type ptr) str) (elipsis)) (nil))

// int main(void)
// {
//   printf("%d\n", excl(5));
//   return 0;
// }
  (func public (type int 32) main (nil)
    (bind [compound
      (call printf [parm 
        (const (type ptr) "5! = %d\n") 
	(call excl (parm (const (type int 32) 5) (nil)))])
      (return (modify (result) (const (type int 32) 0)))]))
]
---CUT---

After running xgcc on this, and running a.out we'll see 5! = 120.

As you can see there are many (), and the language is quite verbose.
However it is not meant to be written by humans. And as you probably
know duming tree generated for code in this form is easy. Also it is
quite easy to parse, I havn't used lex nor yacc.

As of now most useful nodes from tree.def are implemented, not
well tested though.

Front end is available at ftp://aleph-0.dhs.org/pub/ksi/ and
(shortly) at ftp://ftp.pld.org.pl/people/malekith/ksi/ is somebody
wants to look at it. It was tested against gcc-3.0.1 release and
current CVS snapshot.

But let's get to the point, as annoucing ksi is not the reason of
writing this letter :) I use build*() functions to build the tree,
then, once per function, I pass the result to expand_expr() function.
I don't know if this functional in concept way is the best, but I like 
it. Anyway, I would like to have (goto ...) and (label ...) terms.
{LABEL,GOTO}_EXPR seems to be OK for this. However I havn't seen
any actuall usage of them in GCC sources, and expand_expr() hasn't
got a rule for LABEL_EXPR. I wonder if "case LABEL_EXPR: 
expand_label(TREE_OPERAND(exp, 0)); return const0_rtx;" hasn't been
added intentionally or by accident? Anyway, after adding it in
lang_expand_expr() it seems to work fine, however I hasn't extensivly
test it, so maybe there is something more to do then expand_label()...

And the second question: is return value in EXIT_BLOCK_EXPR is going
to get implemented? I have added support for it in ksi, and was
rather supprised with sorry() :)

Third question: can I assign DECL_RESULT(), do some things
(lot of things...) and then expand RETURN_EXPR()? Or the
value (stored in register) will be destroyed by "lot of things",
so it is only safe to use DECL_RESULT() in RETURN_EXPR()
0th operand?

Fourth: can gabage collection occur only at ggc_collect() call
or also at ggc_alloc()? From comments in code and code itself
it seems that only at ggc_collect(), but cobolforgcc manual
(Chapter 14, about GCC internal tree represenatation and
writing own GCC front-end, very halpful thing) states the other way.
As I know the current state, my question is more like: 'is it going
to change' ?

And the last question: what are the conditions for including front-end in
gcc CVS and official releases?  Especially can the code require GCC, has
it to be K&R and indented the GNU way?  It seems that front-ends other
then C are compiled in second stage with freshly built gcc.  I guess
it has to be licensed under GPL :) I would like to obtain localised CVS
write access, who to send ssh key?

Best Regards
-- 
: Michal ``,/\/\,       '' Moskal    | |            : GCS {C,UL}++++$
:          |    |alekith      @    |)|(| . org . pl : {E--, W, w-,M}-
:                                  |                : {b,e>+}++ !tv h
: Current project:  http://aleph-0.dhs.org/ywindow/ : PLD Team member