Backend projects for Sparse

Backend projects for Sparse

[nkavv]

Hi all

i came across Sparse a few months ago and looks really interesting. Now, I have
a few questions regarding the sparse infrastructure:

1) Regarding the intermediate representation dumps that can be generated (via
"test-linearize" i think). Do you support canonical SSA form (as defined in the
classical books/papers)?

2) Is it possible to generate a self-contained IR dump, so that it could be
possible to feed it to external (third-party) code selectors?
In my mind a single C program file (actually read: translation unit) would be
translated to something like the following structure:

struct CTranslationUnit {
  struct GlobalVars; // is a List of global variables (scalars, arrays etc)
  struct ProcedureList;
}

struct ProcedureList
{
  struct LocalVars;  // local variable list
  List   ThreeAddressCodeInstr; // three-address code operations (4-tuples)
}

There a couple of frontends that can do this (the proprietary/no cost for
research only LANCE compiler frontend).

3) What does the c2xml backend exactly do?

4) Is there anyone working on a RISC-like processor backend project. I feel that
 if the entire backend can be contained in something like "compile-i386.c" then
it could be even possible to automate the generation of such file from a more
compact specification file. (plus some hand-written intrinsics probably).

5) Is there any documentation covering the API and linked tools to the sparse
library (something more than the man pages)?

6) Sparse looks good. I like the IR dumps a lot. That's a comment ^_^

Kind regards,
Nikolaos Kavvadias

Re: Backend projects for Sparse

[Christopher Li]

On Nov 28, 2007 1:53 AM,  <nkavv@physics.auth.gr> wrote:
> 1) Regarding the intermediate representation dumps that can be generated (via
> "test-linearize" i think). Do you support canonical SSA form (as defined in the
> classical books/papers)?

It does support SSA from for internal variable(pseudo in
linearization). Not sure
what kind of "canonical SSA" do you have in mind.

>
> 2) Is it possible to generate a self-contained IR dump, so that it could be
> possible to feed it to external (third-party) code selectors?

Not as it is in the git tree. I think the current state, the easiest
way to experiment
your back end is to have third-party code call to sparse lib. Once you have
the linearized byte code, you can start from there.

> In my mind a single C program file (actually read: translation unit) would be
> translated to something like the following structure:

The sparse front end generate list of symbols. Functions is symbol as well.
So it have one single list of symbols that your back end should care about.
You need to look into the symbol type to find out this symbol is a function.
But that is just details.

Inside each function, there is list of symbol access by this functions as well.
I think it is sym->symbol_list.

>
> 3) What does the c2xml backend exactly do?

Dump the symbol table into XML form. It seems it does not support the statement
and expression yet.

> 4) Is there anyone working on a RISC-like processor backend project. I feel that
>  if the entire backend can be contained in something like "compile-i386.c" then
> it could be even possible to automate the generation of such file from a more
> compact specification file. (plus some hand-written intrinsics probably).

It should have some different levels. Some basic back end transformation is
architecture independent. The other is. Emit into platform specific instruction
too early is not ideal either.

There is already compile-i386.c in the project. But it is not a good
place to start.
It does not use the linearized byte code at all. The compile.c written by Linus
is a better place to start.

> 5) Is there any documentation covering the API and linked tools to the sparse
> library (something more than the man pages)?

Not that I know of. If you need that much detail to perform the back end work,
you have to read some source code. I think you can ignore a lot of the parser
details and focus on the linearized byte code.

sparse.c is another example of using those linearized byte code, it
only look for
specific subset in the linearized code though.

Chris

Re: Backend projects for Sparse

[Nikolaos Kavvadias]

Christopher Li wrote:
> It does support SSA from for internal variable(pseudo in
> linearization). Not sure
> what kind of "canonical SSA" do you have in mind.
>   
Hi Christopher

first of all, thanks for your specific answers. The SSA form that i 
think of uses only PHI functions. Guard variables (conditionals for 
selecting a specific usage) may or may not be explicit. Usually, most 
SSA forms just specify which uses are merged. The conditionals can be 
inferred by control-flow analysis.

>> In my mind a single C program file (actually read: translation unit) would be
>> translated to something like the following structure:
>>     
>
> The sparse front end generate list of symbols. Functions is symbol as well.
> So it have one single list of symbols that your back end should care about.
> You need to look into the symbol type to find out this symbol is a function.
> But that is just details.
>
> Inside each function, there is list of symbol access by this functions as well.
> I think it is sym->symbol_list.
>   
OK.

>> 4) Is there anyone working on a RISC-like processor backend project. I feel that
>>  if the entire backend can be contained in something like "compile-i386.c" then
>> it could be even possible to automate the generation of such file from a more
>> compact specification file. (plus some hand-written intrinsics probably).
>>     
>
>   

OK, thank you for this one. I'll have a good look to "compile.c".

>> 5) Is there any documentation covering the API and linked tools to the sparse
>> library (something more than the man pages)?
>>     
>
> Not that I know of. If you need that much detail to perform the back end work,
> you have to read some source code. I think you can ignore a lot of the parser
> details and focus on the linearized byte code.
>
> sparse.c is another example of using those linearized byte code, it
> only look for
> specific subset in the linearized code though.
>
> Chris
>   

Kind regards
Nikolaos Kavvadias

Re: Backend projects for Sparse

[Christopher Li]

On Nov 28, 2007 11:00 AM, Nikolaos Kavvadias <nkavv@physics.auth.gr> wrote:
> first of all, thanks for your specific answers. The SSA form that i
> think of uses only PHI functions. Guard variables (conditionals for
> selecting a specific usage) may or may not be explicit. Usually, most
> SSA forms just specify which uses are merged. The conditionals can be
> inferred by control-flow analysis.

We have PHI node embed in the instruction list as one of the fake instruction.
Then we have the PHI source node to indicate the output edge of the PHI node.

It seems that should fit your need.

Chris

Re: Backend projects for Sparse

[nkavv]

Quoting Christopher Li <sparse@chrisli.org>:

> On Nov 28, 2007 11:00 AM, Nikolaos Kavvadias <nkavv@physics.auth.gr> wrote:
> > first of all, thanks for your specific answers. The SSA form that i
> > think of uses only PHI functions. Guard variables (conditionals for
> > selecting a specific usage) may or may not be explicit. Usually, most
> > SSA forms just specify which uses are merged. The conditionals can be
> > inferred by control-flow analysis.
>
> We have PHI node embed in the instruction list as one of the fake
> instruction.
> Then we have the PHI source node to indicate the output edge of the PHI node.
>
> It seems that should fit your need.
>
> Chris

OK, so it marks where the uses are merged.

Jeff: thanks for clearing up the "linearize" issue.

Nikolaos Kavvadias

Re: Backend projects for Sparse

[Jeff Garzik]

Christopher Li wrote:
> There is already compile-i386.c in the project. But it is not a good
> place to start.

Agreed.  That was generating code directly from the parse tree, rather 
than from the linearized form.


> It does not use the linearized byte code at all. The compile.c written by Linus
> is a better place to start.

test-linearize.c maybe?  compile.c is part of compile-i386.


>> 5) Is there any documentation covering the API and linked tools to the sparse
>> library (something more than the man pages)?
> 
> Not that I know of. If you need that much detail to perform the back end work,
> you have to read some source code. I think you can ignore a lot of the parser
> details and focus on the linearized byte code.

Agreed.

	Jeff

Re: Backend projects for Sparse

[Christopher Li]

On Nov 28, 2007 11:45 AM, Jeff Garzik <jeff@garzik.org> wrote:
> Christopher Li wrote:
> > It does not use the linearized byte code at all. The compile.c written by Linus
> > is a better place to start.
>
> test-linearize.c maybe?  compile.c is part of compile-i386.

Ah, you are right. I mix it up. It should be the "example.c" instead.
test-linearize.c just print out the linearized byte codes.

Chris