Design Considerations of GIMPLE Front End

Design Considerations of GIMPLE Front End

[Sandeep Soni]

Hi,

As part of GSoC 2010, I am developing a front end for GIMPLE.
You can find the basic theme of the project at:
http://gcc.gnu.org/wiki/GimpleFrontEnd

One of the most important components in this GIMPLE Front End is to
convert the GIMPLE tuples into text.
How such a textual representation should be, will obviously dictate
the design and complexity of the
subsequent parsing component. So, as per Diego's suggestion, to have a
view on some of the issues
I have started this thread.

Following are some of the issues/questions that have come  up:

1. What should be the format of representation of the GIMPLE tuples in text?

   Ideally, the textual representation should be satisfying two goals:
Easy to parse and easy for a programmer
   to write by hand.Considering this,what is the best way in which the
GIMPLE tuples be represented.

   For example:
   A textual GIMPLE tuple for the statement a=b+c can be like
   <GIMPLE_ASSIGN<PLUS_EXPR,a,b,c>>  (As demonstrated by the internal
manual also).
   Is such a representation easy to parse?

   The other alternative is to represent the tuples in a C-like syntax
much like what -fdump-tree-gimple flag does.

   Which is more better? In terms of ease in parsing, intuitiveness
for a programmer to code by hand etc.
   Any other alternative?

2. The most important aspect in the representation is that of types.
Since there are many possibilities in
   the types, mapping each in a common representation can be
difficult. An approach suggested by Diego is to
   read what fields are read from 'tree' structures and then lay out
the tuples as follows:

   <TREE_TYPE <name, size, ...>>

   So, we make all the sub-structures into nested tuples. This seems
to be easy to parse.
   Again the question: Are there any ideas from anybody about the way
the types be
   represented so that the parsing becomes simple?

3. Finally, what could be the overall structure of such a textual
gimple file. A possible way could be to have the
    same structure as the sections encoded in the bytestream.So we can
have a section for types, symbols,
    function bodies etc. Such a simple structure will be helpful for
any programmer and be relatively easy to parse.
    Any other ideas? arguments against such a structure?


So, If there are any alternative ideas to any one of these or
arguments in favour of /against the ideas presented
in this mail. Please add it to this thread.

If there are any more vital points which are missing in this mail but
require serious discussions,
please add them to this thread too.
--
Cheers
Sandy

Re: Design Considerations of GIMPLE Front End

[Andrew Haley]

On 05/17/2010 09:15 PM, Sandeep Soni wrote:
> Hi,
> 
> As part of GSoC 2010, I am developing a front end for GIMPLE.
> You can find the basic theme of the project at:
> http://gcc.gnu.org/wiki/GimpleFrontEnd
> 
> One of the most important components in this GIMPLE Front End is to
> convert the GIMPLE tuples into text.
> How such a textual representation should be, will obviously dictate
> the design and complexity of the
> subsequent parsing component. So, as per Diego's suggestion, to have a
> view on some of the issues
> I have started this thread.
> 
> Following are some of the issues/questions that have come  up:
> 
> 1. What should be the format of representation of the GIMPLE tuples in text?
> 
>    Ideally, the textual representation should be satisfying two goals:
> Easy to parse and easy for a programmer
>    to write by hand.Considering this,what is the best way in which the
> GIMPLE tuples be represented.
> 
>    For example:
>    A textual GIMPLE tuple for the statement a=b+c can be like
>    <GIMPLE_ASSIGN<PLUS_EXPR,a,b,c>>  (As demonstrated by the internal
> manual also).
>    Is such a representation easy to parse?

S-expressions are easier to parse and more compact, and are consistent
with gcc's back end.  Also, there are editors that already know how to
edit and indent S-expressions.

Andrew.

Re: Design Considerations of GIMPLE Front End

[Sandeep Soni]

On Tue, May 18, 2010 at 2:34 AM, Andrew Haley <aph@redhat.com> wrote:

>>    For example:
>>    A textual GIMPLE tuple for the statement a=b+c can be like
>>    <GIMPLE_ASSIGN<PLUS_EXPR,a,b,c>>  (As demonstrated by the internal
>> manual also).
>>    Is such a representation easy to parse?
>
> S-expressions are easier to parse and more compact, and are consistent
> with gcc's back end.  Also, there are editors that already know how to
> edit and indent S-expressions.

Thanks Andrew . Any thoughts on the 3rd point?

>
> Andrew.
>



-- 
Cheers
Sandy

Re: Design Considerations of GIMPLE Front End

[Andrew Haley]

On 05/18/2010 04:24 AM, Sandeep Soni wrote:
> On Tue, May 18, 2010 at 2:34 AM, Andrew Haley <aph@redhat.com> wrote:
> 
>>>    For example:
>>>    A textual GIMPLE tuple for the statement a=b+c can be like
>>>    <GIMPLE_ASSIGN<PLUS_EXPR,a,b,c>>  (As demonstrated by the internal
>>> manual also).
>>>    Is such a representation easy to parse?
>>
>> S-expressions are easier to parse and more compact, and are consistent
>> with gcc's back end.  Also, there are editors that already know how to
>> edit and indent S-expressions.
> 
> Thanks Andrew . Any thoughts on the 3rd point?

Your suggestion for 3 is perfectly sensible, and is a good way to
start.

It's quite possible that, whatever you do, you'll find that the file
structure will need to be changed, so it makes sense to do something
as simple and straightforward as possible.  If your code is
well-factored it can be reorganized later.

Andrew.

Re: Design Considerations of GIMPLE Front End

[Diego Novillo]

On Mon, May 17, 2010 at 16:15, Sandeep Soni <soni.sandeepb@gmail.com> wrote:

> 1. What should be the format of representation of the GIMPLE tuples in text?

I liked Andrew's suggestion about S-expressions.  It looks like a good
balance between ease of parsing/writing.  We can always tweak the
format as we go.

As for points 2 and 3, I'd suggest start documenting the grammar for
types and sections on the wiki.  That will expose some shortcomings
early on before any code is written.


Diego.

Re: Design Considerations of GIMPLE Front End

[Michael Matz]

Hi,

On Tue, 18 May 2010, Diego Novillo wrote:

> On Mon, May 17, 2010 at 16:15, Sandeep Soni <soni.sandeepb@gmail.com> wrote:
> 
> > 1. What should be the format of representation of the GIMPLE tuples in 
> >    text?
> 
> I liked Andrew's suggestion about S-expressions.

I can see that for describing types, maybe.  But isn't that artificially 
awkward for representing tuple instructions?  I mean most instructions 
will look like

  (= i_1 (+ k_1 m_1))
or
  (= j_1 (call func arg1 arg2))

I don't see how that is much easier to parse compared to
  i_1 = k_1 + m_1
  j_1 = func (arg1, arg2)

The nice thing with tuples is that there's always only one operator, and 
hence no ambiguity in precedence that needs to be resolved or explicitely 
encoded via a list structure.

Or is the format also intended to be able to represent GENERIC, i.e. 
deeply nested structures?


Ciao,
Michael.

Re: Design Considerations of GIMPLE Front End

[Diego Novillo]

On Tue, May 18, 2010 at 09:59, Michael Matz <matz@suse.de> wrote:

> I don't see how that is much easier to parse compared to
>  i_1 = k_1 + m_1
>  j_1 = func (arg1, arg2)

Well, it would make the parser almost trivial to implement.  But you
have a point, the only structurally complex objects we need to parse
are type declarations.  Everything else should have very uniform
syntax.

> The nice thing with tuples is that there's always only one operator, and
> hence no ambiguity in precedence that needs to be resolved or explicitely
> encoded via a list structure.

That's true.

> Or is the format also intended to be able to represent GENERIC, i.e.
> deeply nested structures?

No, just gimple.


Diego.

Re: Design Considerations of GIMPLE Front End

[Steven Bosscher]

On Tue, May 18, 2010 at 4:09 PM, Diego Novillo <dnovillo@google.com> wrote:
> On Tue, May 18, 2010 at 09:59, Michael Matz <matz@suse.de> wrote:
>
>> I don't see how that is much easier to parse compared to
>>  i_1 = k_1 + m_1
>>  j_1 = func (arg1, arg2)
>
> Well, it would make the parser almost trivial to implement.  But you
> have a point, the only structurally complex objects we need to parse
> are type declarations.  Everything else should have very uniform
> syntax.
>
>> The nice thing with tuples is that there's always only one operator, and
>> hence no ambiguity in precedence that needs to be resolved or explicitely
>> encoded via a list structure.
>
> That's true.
>
>> Or is the format also intended to be able to represent GENERIC, i.e.
>> deeply nested structures?
>
> No, just gimple.

IMHO, ideally we would have a syntax that is human readable and human
writable. S-expressions are not as easy to read for me as something
that resembles C.

Related subject: Is it possible to have a formal grammar of some kind
for, say, bison? It would be nice if we can generate different tools
from one grammar, e.g. a GIMPLE front end, a syntax checker, maybe
static analyzers, etc. If you make a reader that already constructs
the gimple data structures, it will be harder to construct multiple
tools on top of it that are independent of libbackend.

Ciao!
Steven

Re: Design Considerations of GIMPLE Front End

[Dave Korn]

On 18/05/2010 15:17, Steven Bosscher wrote:

> IMHO, ideally we would have a syntax that is human readable and human
> writable. S-expressions are not as easy to read for me as something
> that resembles C.

  I'd like it that way too, but I acknowledge that it would be more work and
it's not me who'd have to do that extra work...

    cheers,
      DaveK

Re: Design Considerations of GIMPLE Front End

[Andrew Haley]

On 05/18/2010 04:05 PM, Dave Korn wrote:
> On 18/05/2010 15:17, Steven Bosscher wrote:
> 
>> IMHO, ideally we would have a syntax that is human readable and human
>> writable. S-expressions are not as easy to read for me as something
>> that resembles C.
> 
>   I'd like it that way too, but I acknowledge that it would be more work and
> it's not me who'd have to do that extra work...

Well, it can always be changed later, but there's a lot to be said for
not spending time now writing a parser, and getting on with the project.
It's a matter of taste anyway.

Andrew.

Re: Design Considerations of GIMPLE Front End

[Diego Novillo]

[ apologies for the duplicate message.  My previous reply was bounced
by the ML. ]

> On Tue, May 18, 2010 at 10:52, Andrew Haley <aph@redhat.com> wrote:
>>
>> On 05/18/2010 04:05 PM, Dave Korn wrote:
>> > On 18/05/2010 15:17, Steven Bosscher wrote:
>> >
>> >> IMHO, ideally we would have a syntax that is human readable and human
>> >> writable. S-expressions are not as easy to read for me as something
>> >> that resembles C.
>> >
>> >   I'd like it that way too, but I acknowledge that it would be more work and
>> > it's not me who'd have to do that extra work...
>>
>> Well, it can always be changed later, but there's a lot to be said for
>> not spending time now writing a parser, and getting on with the project.
>> It's a matter of taste anyway.
>
Yup.  This shade of blue can be changed later.  Sandi, let's start
with the S-expression syntax for everything.  Richard is correct in
pointing out that even gimple expressions have metadata associated
with them that will need to be represented.


Diego.

Re: Design Considerations of GIMPLE Front End

[Sandeep Soni]

On Tue, May 18, 2010 at 8:33 PM, Diego Novillo <dnovillo@google.com> wrote:

> Yup.  This shade of blue can be changed later.  Sandi, let's start
> with the S-expression syntax for everything.  Richard is correct in
> pointing out that even gimple expressions have metadata associated
> with them that will need to be represented.

Yes. I will start editing the wiki page created to document the S-expression
syntax and the grammar.

This will be an ongoing process though, in parallel with my current work of
getting familiar with the LTO code base, so might take some time earlier on.

>
>
> Diego.
>



-- 
Cheers
Sandy

Re: Design Considerations of GIMPLE Front End

[Basile Starynkevitch]

On Tue, 2010-05-18 at 15:59 +0200, Michael Matz wrote:
> Hi,
> 
> On Tue, 18 May 2010, Diego Novillo wrote:
> 
> > On Mon, May 17, 2010 at 16:15, Sandeep Soni <soni.sandeepb@gmail.com> wrote:
> > 
> > > 1. What should be the format of representation of the GIMPLE tuples in 
> > >    text?
> > 
> > I liked Andrew's suggestion about S-expressions.
> 
> I can see that for describing types, maybe.  But isn't that artificially 
> awkward for representing tuple instructions?  I mean most instructions 
> will look like
> 
>   (= i_1 (+ k_1 m_1))
> or
>   (= j_1 (call func arg1 arg2))
> 
> I don't see how that is much easier to parse compared to
>   i_1 = k_1 + m_1
>   j_1 = func (arg1, arg2)

My intuition might be that once a Gimple parser exists, most of its use
would be writing various translators (e.g. external front-ends) to this
syntax, so people might probably code more Gimple-syntax printers than
Gimple-syntax parsers.

Still, I prefer the Lispy S-expression syntax everywhere -including
Gimple- because it is so simple to define and to implement, and because
GCC MELT already have [almost] the infrastructure for it.

However, I tend to think that the Gimple syntax would also [at least
optionally] contain the location information, so it would be instead
   (= (@ "foo.cobol" 23 2) i_1 (+ k_1 m_1)))
or even
   (= (@ "foo.cobol" 23 3) i_1 (+ (@ "foo.cobol" 23 5) k_1 m_1)))
I am using, perhaps wrongly, @ as an "operator" giving the location
information as a file name, line number, column number. I am not sure to
have the syntax right (because I am not sure to remember what exactly
has a location information).

I believe a Gimple-syntax should provide the features (or hooks, or
syntax) to convey all the Gimple information, and this includes the
source file location. This is needed both for external (GPLv3+ or
compatibly licensed) programs producing Gimple (such as an hypothetical
Cobol frontend) and for external (GPLv3+ or compatibly licensed)
programs consuming Gimple (like sophisticated static analyzers) or for
external programs both consuming & producing Gimple (e.g. an
"optimization" implemented by an external program).

Otherwise, what is the purpose of Gimple-syntax? Why making it if it
does not contain all the information inside GCC?


BTW, is it possible today to have a GCC plugin providing a front-end to
GCC? [last time I looked, I believe the answer is no]

Cheers.

Re: Design Considerations of GIMPLE Front End

[Richard Guenther]

On Tue, May 18, 2010 at 4:30 PM, Basile Starynkevitch
<basile@starynkevitch.net> wrote:
> On Tue, 2010-05-18 at 15:59 +0200, Michael Matz wrote:
>> Hi,
>>
>> On Tue, 18 May 2010, Diego Novillo wrote:
>>
>> > On Mon, May 17, 2010 at 16:15, Sandeep Soni <soni.sandeepb@gmail.com> wrote:
>> >
>> > > 1. What should be the format of representation of the GIMPLE tuples in
>> > >    text?
>> >
>> > I liked Andrew's suggestion about S-expressions.
>>
>> I can see that for describing types, maybe.  But isn't that artificially
>> awkward for representing tuple instructions?  I mean most instructions
>> will look like
>>
>>   (= i_1 (+ k_1 m_1))
>> or
>>   (= j_1 (call func arg1 arg2))
>>
>> I don't see how that is much easier to parse compared to
>>   i_1 = k_1 + m_1
>>   j_1 = func (arg1, arg2)
>
> My intuition might be that once a Gimple parser exists, most of its use
> would be writing various translators (e.g. external front-ends) to this
> syntax, so people might probably code more Gimple-syntax printers than
> Gimple-syntax parsers.
>
> Still, I prefer the Lispy S-expression syntax everywhere -including
> Gimple- because it is so simple to define and to implement, and because
> GCC MELT already have [almost] the infrastructure for it.
>
> However, I tend to think that the Gimple syntax would also [at least
> optionally] contain the location information, so it would be instead
>   (= (@ "foo.cobol" 23 2) i_1 (+ k_1 m_1)))
> or even
>   (= (@ "foo.cobol" 23 3) i_1 (+ (@ "foo.cobol" 23 5) k_1 m_1)))
> I am using, perhaps wrongly, @ as an "operator" giving the location
> information as a file name, line number, column number. I am not sure to
> have the syntax right (because I am not sure to remember what exactly
> has a location information).

Yep, we also need to be able to specify the various flags on
gimple statements and information such as alias info.

At least if we eventually want to use this as a framework for
real unit-testing.  So I'm not too concerned about using
s-expressions even for the statements.

Richard.

Re: Design Considerations of GIMPLE Front End

[Steven Bosscher]

On Tue, May 18, 2010 at 4:30 PM, Basile Starynkevitch
<basile@starynkevitch.net> wrote:
> BTW, is it possible today to have a GCC plugin providing a front-end to
> GCC? [last time I looked, I believe the answer is no]

This is one of the reasons for my patches to better hide the
middle-end details from the front ends.

Ciao!
Steven

Re: Design Considerations of GIMPLE Front End

[Sebastian Pop]

Hi,

On Mon, May 17, 2010 at 15:15, Sandeep Soni <soni.sandeepb@gmail.com> wrote:
> Hi,
>
> As part of GSoC 2010, I am developing a front end for GIMPLE.
> You can find the basic theme of the project at:
> http://gcc.gnu.org/wiki/GimpleFrontEnd
>
> One of the most important components in this GIMPLE Front End is to
> convert the GIMPLE tuples into text.
> How such a textual representation should be, will obviously dictate
> the design and complexity of the
> subsequent parsing component. So, as per Diego's suggestion, to have a
> view on some of the issues
> I have started this thread.
>
> Following are some of the issues/questions that have come  up:
>
> 1. What should be the format of representation of the GIMPLE tuples in text?
>
>   Ideally, the textual representation should be satisfying two goals:
> Easy to parse and easy for a programmer
>   to write by hand.Considering this,what is the best way in which the
> GIMPLE tuples be represented.
>
>   For example:
>   A textual GIMPLE tuple for the statement a=b+c can be like
>   <GIMPLE_ASSIGN<PLUS_EXPR,a,b,c>>  (As demonstrated by the internal
> manual also).
>   Is such a representation easy to parse?
>
>   The other alternative is to represent the tuples in a C-like syntax
> much like what -fdump-tree-gimple flag does.
>
>   Which is more better? In terms of ease in parsing, intuitiveness
> for a programmer to code by hand etc.
>   Any other alternative?
>
> 2. The most important aspect in the representation is that of types.
> Since there are many possibilities in
>   the types, mapping each in a common representation can be
> difficult. An approach suggested by Diego is to
>   read what fields are read from 'tree' structures and then lay out
> the tuples as follows:
>
>   <TREE_TYPE <name, size, ...>>
>
>   So, we make all the sub-structures into nested tuples. This seems
> to be easy to parse.
>   Again the question: Are there any ideas from anybody about the way
> the types be
>   represented so that the parsing becomes simple?
>
> 3. Finally, what could be the overall structure of such a textual
> gimple file. A possible way could be to have the
>    same structure as the sections encoded in the bytestream.So we can
> have a section for types, symbols,
>    function bodies etc. Such a simple structure will be helpful for
> any programmer and be relatively easy to parse.
>    Any other ideas? arguments against such a structure?
>
>
> So, If there are any alternative ideas to any one of these or
> arguments in favour of /against the ideas presented
> in this mail. Please add it to this thread.

Please have a look at the LLVM language specification:
http://llvm.org/docs/LangRef.html
that should give you a good intuition of what you need to represent
for GIMPLE, and how the LLVM file format is structured.

Would LLVM be acceptable to dump the GIMPLE representation?
In which case you would have an implementation of the pretty printer,
and you would need a parser of LLVM to get that representation back
to GCC.

Sebastian