[ANNOUNCE] LLVM backend for Sparse

[ANNOUNCE] LLVM backend for Sparse

[Pekka Enberg]

Hi everyone,

Jeff Garzik and myself have been hacking on LLVM backed for Sparse. The sources
are available on Github:

   git clone git://github.com/penberg/sparse-llvm.git

You can use sparse-llvm with the 'sparsec' shells script provided in the source
tree. It has a GCC compatible command line interface and uses GCC for linking.
For example, you can try to build sparse with sparse-llvm like this:

   make CC=sparsec

Developers who are interested in looking at the LLVM output can use the
'sparse-llvm' command as follows:

   sparse-llvm foo.c | llvm-dis

The backend is already capable of generating code for simple C code on various
platforms. Supported C features include:

   * Function calls

   * Switch statements

   * if-else statements

   * Arithmetic operations

   * Bitwise operations

   * Floating point arithmetic

There's many features that are not supported so if you see an error message
such as this while compiling a C file:

   sparse-llvm: sparse-llvm.c:165: pseudo_type: Assertion `0' failed.

don't panic because it simply means you're attempting to use an unsupported
feature. Help implementing them is more than welcome!

 			Pekka

Re: [ANNOUNCE] LLVM backend for Sparse

[Christopher Li]

[-- Attachment #1: Type: text/plain, Size: 624 bytes --]

On Sat, Aug 27, 2011 at 11:08 PM, Pekka Enberg <penberg@kernel.org> wrote:
> Hi everyone,
>
> Jeff Garzik and myself have been hacking on LLVM backed for Sparse. The
> sources
> are available on Github:
>
>  git clone git://github.com/penberg/sparse-llvm.git
>

Very impressive. That is some sparse 0.5 material.
I will start merging it as soon as I release 0.4.4

I play around with it a little bit, It seems choke on the hello
world program. Shouldn't be hard to fix though.

I attach a patch to limit g++ usage only to llvm related programs.
Currently it use g++ to link other sparse programs.

Chris

[-- Attachment #2: 0001-Limit-usage-of-g-to-llvm-related-programs.patch --]
[-- Type: text/x-patch, Size: 994 bytes --]

From c00d1020abf52405783fa973da6f28fe700fac3b Mon Sep 17 00:00:00 2001
From: Christopher Li <sparse@chrisli.org>
Date: Sun, 28 Aug 2011 01:04:41 -0700
Subject: [PATCH] Limit usage of g++ to llvm related programs.

Signed-off-by: Christopher Li <sparse@chrisli.org>
---
 Makefile |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/Makefile b/Makefile
index a9f9b35..ab0b186 100644
--- a/Makefile
+++ b/Makefile
@@ -66,11 +66,12 @@ $(warning Your system does not have libgtk2, disabling test-inspect)
 endif
 
 ifeq ($(HAVE_LLVM),yes)
-LD = g++
+LLVM_PROGS := sparse-llvm 
+$(LLVM_PROGS): LD := g++
 LDFLAGS += $(shell llvm-config --ldflags)
 LLVM_CFLAGS := $(shell llvm-config --cflags | sed -e "s/-DNDEBUG//g")
 LLVM_LIBS := $(shell llvm-config --libs)
-PROGRAMS += sparse-llvm
+PROGRAMS += $(LLVM_PROGS)
 INST_PROGRAMS += sparse-llvm sparsec
 sparse-llvm_EXTRA_DEPS := sparse-llvm.o
 sparse-llvm.o $(sparse-llvm_EXTRA_DEPS): BASIC_CFLAGS += $(LLVM_CFLAGS)
-- 
1.7.6

Re: [ANNOUNCE] LLVM backend for Sparse

[Pekka Enberg]

On Sun, 28 Aug 2011, Christopher Li wrote:
> I attach a patch to limit g++ usage only to llvm related programs.
> Currently it use g++ to link other sparse programs.

Applied, thanks!

Re: [ANNOUNCE] LLVM backend for Sparse

[Pekka Enberg]

On Sun, 28 Aug 2011, Christopher Li wrote:
> Very impressive. That is some sparse 0.5 material.
> I will start merging it as soon as I release 0.4.4
>
> I play around with it a little bit, It seems choke on the hello
> world program. Shouldn't be hard to fix though.

It's lack of PSEUDO_SYM support. I haven't quite figured out what kind of 
code to generate for that because, frankly, I'm not completely sure what 
it's all about. ;-)

 			Pekka

Re: [ANNOUNCE] LLVM backend for Sparse

[Linus Torvalds]

On Sun, Aug 28, 2011 at 7:01 AM, Pekka Enberg <penberg@kernel.org> wrote:
>
> It's lack of PSEUDO_SYM support. I haven't quite figured out what kind of
> code to generate for that because, frankly, I'm not completely sure what
> it's all about. ;-)

So "PSEUDO_SYM" is just a "link-time constant".

IOW, it's nothing but a pointer to an in-memory variable, and from a
code generation standpoint generating the symbol should be just about
the same as generating a constant, except rather than an actual value,
it's now a linker reference.

Of course, what complicates them is that you also need to generate the
symbol definition itself (somewhere else). In particular, the
sym->initializer points to the initializer of a symbol, and they can
be *complicated*. Generating the output for some symbols can be a
major pain in the *ss, just think about a complex structure array
initializer.

The PSEUDO_SYM you hit for the "hello world" program is trivial,
though. It's an unnamed symbol of type "char []", and it has a trivial
initializer (the string itself). So symbols can be hard to generate,
but there are simple cases.

So for a PSUEDO_SYM, you need to look up "struct symbol" for it
(pseudo->sym), which then has:

 - name of the symbol (sym->ident). Of course, some symbols don't have
names, like the constant string example.

 - type/size/alignment information (sym->ctype)

 - initializer information (sym->initializer - which can be a really
complex expression). Of course, for external symbols - or symbols with
no initializer - this is just empty.

There's way more to symbol types in sparse than that, but apart from
the initializer expression, most of the symbol complexity has been
handled by earlier stages (ie a *lot* of the front-end of sparse is
about symbols and their types).

                          Linus

Re: [ANNOUNCE] LLVM backend for Sparse

[Pekka Enberg]

On Sun, Aug 28, 2011 at 7:01 AM, Pekka Enberg <penberg@kernel.org> wrote:
>> It's lack of PSEUDO_SYM support. I haven't quite figured out what kind of
>> code to generate for that because, frankly, I'm not completely sure what
>> it's all about. ;-)

On Sun, Aug 28, 2011 at 7:54 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
> So "PSEUDO_SYM" is just a "link-time constant".
>
> IOW, it's nothing but a pointer to an in-memory variable, and from a
> code generation standpoint generating the symbol should be just about
> the same as generating a constant, except rather than an actual value,
> it's now a linker reference.
>
> Of course, what complicates them is that you also need to generate the
> symbol definition itself (somewhere else). In particular, the
> sym->initializer points to the initializer of a symbol, and they can
> be *complicated*. Generating the output for some symbols can be a
> major pain in the *ss, just think about a complex structure array
> initializer.
>
> The PSEUDO_SYM you hit for the "hello world" program is trivial,
> though. It's an unnamed symbol of type "char []", and it has a trivial
> initializer (the string itself). So symbols can be hard to generate,
> but there are simple cases.
>
> So for a PSUEDO_SYM, you need to look up "struct symbol" for it
> (pseudo->sym), which then has:
>
>  - name of the symbol (sym->ident). Of course, some symbols don't have
> names, like the constant string example.
>
>  - type/size/alignment information (sym->ctype)
>
>  - initializer information (sym->initializer - which can be a really
> complex expression). Of course, for external symbols - or symbols with
> no initializer - this is just empty.
>
> There's way more to symbol types in sparse than that, but apart from
> the initializer expression, most of the symbol complexity has been
> handled by earlier stages (ie a *lot* of the front-end of sparse is
> about symbols and their types).

Right. Will the "link time constant" 'struct symbol' be part of the
symbol_list? If it is, then we already do LLVMAddGlobal in
output_data() on it and could probably just stash that into a ->priv
member in 'struct symbol' and use that in pseudo_to_value().
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [ANNOUNCE] LLVM backend for Sparse

[Christopher Li]

On 08/29/2011 12:41 AM, Pekka Enberg wrote:
> Right. Will the "link time constant" 'struct symbol' be part of the 
> symbol_list? If it is, then we already do LLVMAddGlobal in 
> output_data() on it and could probably just stash that into a ->priv 
> member in 'struct symbol' and use that in pseudo_to_value(). 

The link time constant is a LLVMValueRef, it is just the address of the 
symbol.
Yes, it will belong to the function scope's symbol_list but not 
necessary the global one.
Here is some tips that help me a lot on my own llvm branch, which lost 
due to a hard
drive crash. It was able to do hello world back then.

LLVM can output c++ source code that construct the llvm byte code.

# this will emit hello.s as the llvm asm code
$ clang -S -emit-llvm hello.c

# this will generate hello.s.cpp which is the c++ source code to construct
# the llvm byte code above

$ llc -march=cpp hello.s

The hello.s.cpp is a very good reference to build the llvm byte code in C.
It is in C++, but convert to llvm C binding should be easy.
BTW, "-march=c" does not generate C bindings, it generate the
equivalent IR in C code instead.

Hope that helps.

Chris

Re: [ANNOUNCE] LLVM backend for Sparse

[Pekka Enberg]

On 08/29/2011 12:41 AM, Pekka Enberg wrote:
>> Right. Will the "link time constant" 'struct symbol' be part of the
>> symbol_list? If it is, then we already do LLVMAddGlobal in output_data() on
>> it and could probably just stash that into a ->priv member in 'struct
>> symbol' and use that in pseudo_to_value().

On Mon, Aug 29, 2011 at 12:19 PM, Christopher Li <sparse@chrisli.org> wrote:
> The link time constant is a LLVMValueRef, it is just the address of the
> symbol.
> Yes, it will belong to the function scope's symbol_list but not necessary
> the global one.
> Here is some tips that help me a lot on my own llvm branch, which lost due
> to a hard
> drive crash. It was able to do hello world back then.
>
> LLVM can output c++ source code that construct the llvm byte code.
>
> # this will emit hello.s as the llvm asm code
> $ clang -S -emit-llvm hello.c
>
> # this will generate hello.s.cpp which is the c++ source code to construct
> # the llvm byte code above
>
> $ llc -march=cpp hello.s
>
> The hello.s.cpp is a very good reference to build the llvm byte code in C.
> It is in C++, but convert to llvm C binding should be easy.
> BTW, "-march=c" does not generate C bindings, it generate the
> equivalent IR in C code instead.

Yup, I've been doing that online here:

http://llvm.org/demo/test.cgi

Re: [ANNOUNCE] LLVM backend for Sparse

[Pekka Enberg]

On Sat, Aug 27, 2011 at 11:08 PM, Pekka Enberg <penberg@kernel.org> wrote:
>> Jeff Garzik and myself have been hacking on LLVM backed for Sparse. The
>> sources
>> are available on Github:
>>
>>  git clone git://github.com/penberg/sparse-llvm.git

On Sun, Aug 28, 2011 at 11:51 AM, Christopher Li <sparse@chrisli.org> wrote:
> Very impressive. That is some sparse 0.5 material.
> I will start merging it as soon as I release 0.4.4
>
> I play around with it a little bit, It seems choke on the hello
> world program. Shouldn't be hard to fix though.

It's alive!

$ cat validation/backend/hello.c
#include <stdio.h>

int main(int argc, char *argv[])
{
	puts("hello, world");

	return 0;
}

/*
 * check-name: 'hello, world' code generation
 * check-command: ./sparsec -c $file -o tmp.o
 */
$ ./sparsec -c validation/backend/hello.c -o tmp.o && gcc tmp.o && ./a.out
hello, world

You can find details in this commit:

https://github.com/penberg/sparse-llvm/commit/deb11bd4ee6ed46bce6a5e35a69ada519d81a0a8

                        Pekka
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [ANNOUNCE] LLVM backend for Sparse

[Derek M Jones]

Pekka,

>>> Jeff Garzik and myself have been hacking on LLVM backed for Sparse. The
...
> It's alive!

Congratulations.  It is always great to see a compiler generate
executable code for the first time.

It is useful to have a semantic checker generate executable code
because it provides confirmation that lots of internal processing
is working as intended and therefore increases confidence
that the semantic checks are correct.

Can people allay my concern that this work is not on the slippery
slope leading to sparse becoming the recommended compiler for
building the kernel?

-- 
Derek M. Jones                   tel: +44 (0) 1252 520 667
Knowledge Software Ltd           blog:shape-of-code.codingguidelines.com
Source code analysis             http://www.knosof.co.uk

Re: [ANNOUNCE] LLVM backend for Sparse

[Jeff Garzik]

On 08/29/2011 11:14 AM, Derek M Jones wrote:
> Can people allay my concern that this work is not on the slippery
> slope leading to sparse becoming the recommended compiler for
> building the kernel?

I doubt sparse will ever have the testing, support and deployment 
infrastructure of the gcc ecosystem.

	Jeff

Re: [ANNOUNCE] LLVM backend for Sparse

[Derek M Jones]

Jeff,

>> Can people allay my concern that this work is not on the slippery
>> slope leading to sparse becoming the recommended compiler for
>> building the kernel?
>
> I doubt sparse will ever have the testing, support and deployment
> infrastructure of the gcc ecosystem.

Exactly.  Unfortunately people's desire to control their world is often
stronger.

-- 
Derek M. Jones                   tel: +44 (0) 1252 520 667
Knowledge Software Ltd           blog:shape-of-code.codingguidelines.com
Source code analysis             http://www.knosof.co.uk

Re: [ANNOUNCE] LLVM backend for Sparse

[Pekka Enberg]

On Mon, Aug 29, 2011 at 6:42 PM, Derek M Jones <derek@knosof.co.uk> wrote:
>>> Can people allay my concern that this work is not on the slippery
>>> slope leading to sparse becoming the recommended compiler for
>>> building the kernel?
>>
>> I doubt sparse will ever have the testing, support and deployment
>> infrastructure of the gcc ecosystem.

On Mon, Aug 29, 2011 at 6:42 PM, Derek M Jones <derek@knosof.co.uk> wrote:
> Exactly.  Unfortunately people's desire to control their world is often
> stronger.

I doubt sparse will ever become the 'recommended compiler' for Linux
but I fail to see why that would be a bad thing.

                          Pekka
--
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [ANNOUNCE] LLVM backend for Sparse

[Linus Torvalds]

On Mon, Aug 29, 2011 at 8:14 AM, Derek M Jones <derek@knosof.co.uk> wrote:
>
> Can people allay my concern that this work is not on the slippery
> slope leading to sparse becoming the recommended compiler for
> building the kernel?

That was never really a goal.

What *was* a goal for me a long time ago was to make sparse be a
"preprocessor" in front of gcc, because the standard C pre-processor
has always been weak and we've always abused it in nasty ways (look at
all the games we play with "sizeof" and "typeof" to make our
"kernel-C" have a kind of generic programming).

Having a semantically aware preprocessor would allow kernel-specific
type extensions (like the "__user" attribute we already use purely for
checking runs), and allow debug facilities like "trace accesses to
this variable" without having to have ugly and unreadable wrappers
etc.

But even that got put on the back-burner when gcc improved the
pre-processor performance. It used to be a separate phase, and quite
slow, and having a quick semantic analysis in front of cc1 that
replaced the gcc preprocessor wouldn't have been a big slow-down. But
with the new (well, no longer new) built-in pre-processor, a sparse
front-end would slow down kernel compiles noticeably.

The main reason I used to want to have a back-end was that without a
back-end you cannot really verify the front-end. You can read
"test-linearize" output all day long, you'll never really get very
far. Once you generate code, and can use the thing to actually compile
real programs, that gives you *way* more confidence that you're doing
things right.

                          Linus

Re: [ANNOUNCE] LLVM backend for Sparse

[Jeff Garzik]

On 08/29/2011 10:22 AM, Pekka Enberg wrote:
> On Sat, Aug 27, 2011 at 11:08 PM, Pekka Enberg<penberg@kernel.org>  wrote:
>>> Jeff Garzik and myself have been hacking on LLVM backed for Sparse. The
>>> sources
>>> are available on Github:
>>>
>>>   git clone git://github.com/penberg/sparse-llvm.git
>
> On Sun, Aug 28, 2011 at 11:51 AM, Christopher Li<sparse@chrisli.org>  wrote:
>> Very impressive. That is some sparse 0.5 material.
>> I will start merging it as soon as I release 0.4.4
>>
>> I play around with it a little bit, It seems choke on the hello
>> world program. Shouldn't be hard to fix though.
>
> It's alive!
>
> $ cat validation/backend/hello.c
> #include<stdio.h>
>
> int main(int argc, char *argv[])
> {
> 	puts("hello, world");
>
> 	return 0;
> }

you should be more adventurous, and try varargs!  :)

This also works:

[WARNING: it only works if I disable optimization, for some reason]

[jgarzik@bd sparse-llvm]$ ./sparse-llvm foo.c | llc > foo.s
[jgarzik@bd sparse-llvm]$ gcc -o foo foo.s
[jgarzik@bd sparse-llvm]$ ./foo
hello, world!
[jgarzik@bd sparse-llvm]$ cat foo.c

#include <stdio.h>

int main (int argc, char *argv[])
{
	printf("%s\n", "hello, world!");

	return 0;
}