An LLVM backend for Sparse

[Posted August 29, 2011 by corbet]

From:		Pekka Enberg <penberg-AT-kernel.org>
To:		linux-sparse-AT-vger.kernel.org
Subject:		[ANNOUNCE] LLVM backend for Sparse
Date:		Sun, 28 Aug 2011 09:08:40 +0300 (EEST)
Message-ID:		<alpine.DEB.2.00.1108280904070.7603@localhost6.localdomain6>
Cc:		Christopher Li <sparse-AT-chrisli.org>, Jeff Garzik <jeff-AT-garzik.org>, Linus Torvalds <torvalds-AT-linux-foundation.org>, Josh Triplett <josh-AT-joshtriplett.org>
Archive‑link:		Article

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
--
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

to post comments

An LLVM backend for Sparse

Posted Aug 29, 2011 18:13 UTC (Mon) by daglwn (guest, #65432) [Link] (30 responses)

What's the goal of this project? It seems a bit odd given the availability of gcc and clang.

An LLVM backend for Sparse

Posted Aug 29, 2011 18:47 UTC (Mon) by penberg (guest, #30234) [Link] (29 responses)

The goal is to be able to compile the kernel with sparse. Dunno why you find that odd.

An LLVM backend for Sparse

Posted Aug 29, 2011 19:01 UTC (Mon) by daglwn (guest, #65432) [Link] (25 responses)

It's odd because we already have two high-quality C compilers with working code generators. If the goal is to get Sparse to recognize more types of code for static analysis, one doesn't need LLVM. In fact I would argue that the clang static analyzer is a better long-term project to work on for that type of tool.

It just seems like a lot of NIH to me.

An LLVM backend for Sparse

Posted Aug 29, 2011 19:07 UTC (Mon) by daglwn (guest, #65432) [Link]

I should clarify that I believe Sparse came on-line before the clang static analyzer, but there still does seem to be a lot of duplication there.

Perhaps I don't understand enough about what Sparse does.

An LLVM backend for Sparse

Posted Aug 29, 2011 19:13 UTC (Mon) by penberg (guest, #30234) [Link] (18 responses)

It seems to me you're just confused. See Linus' post for details if you're interested in why proper backend is important to make sure the 'semantic analysis' part is sane:

http://thread.gmane.org/gmane.comp.parsers.sparse/2600/fo...

Btw, I've heard that "not invented here" thing rather often lately, but I hope you realize that Sparse is older than Clang and that we're *using* LLVM (it's a library, remember).

An LLVM backend for Sparse

Posted Aug 29, 2011 19:42 UTC (Mon) by daglwn (guest, #65432) [Link]

See my post above. Even if Sparse came along first, you can still perpetuate NIH by not acknowledging and having a serious look at what else is out there.

Not saying that's what's happening with Sparse. I don't know nearly enough about it. I'm simply making the point that NIH appears in all sorts of situations, even when the product in question was the first of its kind.

An LLVM backend for Sparse

Posted Aug 29, 2011 19:45 UTC (Mon) by daglwn (guest, #65432) [Link] (16 responses)

Linus' comments make sense, and it's exactly what the clang static analyzer does. It even uses LLVM. It strikes me as wasted effort to do another one when everyone would benefit from a better clang static analyzer.

An LLVM backend for Sparse

Posted Aug 29, 2011 20:35 UTC (Mon) by penberg (guest, #30234) [Link] (15 responses)

You keep bringing up Clang but fail to acknowledge that it's actually not quite there yet for us Linux developers:

http://llvm.org/bugs/show_bug.cgi?id=4068

You also mention duplication without realizing that the Sparse/LLVM backend is just 705 lines of C code! Yes, it will grow over time but it's unlikely to ever be as big as the parser which is 25 KLOC - and that's where the real "duplication" is.

I'm sure Clang will be eventually mature enough to build the Linux kernel but Sparse/LLVM might get there first because Sparse is already able to parse the whole kernel. And who knows, maybe Clang is able to reuse Sparse code (or ideas) in the future.

So I still think you're just confused and are shouting 'NIH' because you don't understand the underlying issues.

An LLVM backend for Sparse

Posted Aug 29, 2011 22:35 UTC (Mon) by PaXTeam (guest, #24616) [Link] (4 responses)

fwiw, i've been building and booting clang built kernels for over a year now (requires patches on both sides), so i think clang 'won' that race already ;). but on a more serious note, have you considered implementing sparse features as clang analyzer passes (and while at it, gcc passes)? both support plugins these days and they could even become mandatory during normal compiles (unlike sparse/checkpatch/etc) and everyone would be forced to produce better code. for the gcc side i already implemented a simple infrastructure to support plugins in PaX, you can start from there (and i'd actually like to implement some of the sparse attributes myself, but free time never seems enough ;).

An LLVM backend for Sparse

Posted Aug 30, 2011 6:37 UTC (Tue) by penberg (guest, #30234) [Link] (3 responses)

> but on a more serious note, have you considered implementing sparse features as
> clang analyzer passes (and while at it, gcc passes)?

Heh, I wouldn't touch GCC with a ten-feet pole... ;-)

Clang sparse-like analyzer pass might be an interesting and useful project,
sure, but I'm not personally that interested in the frontend (which is why I'm
hacking on Sparse/LLVM).

An LLVM backend for Sparse

Posted Aug 30, 2011 6:50 UTC (Tue) by gmaxwell (guest, #30048) [Link] (2 responses)

Have you actually looked at the plugin interface or are you just spreading FUD?

An LLVM backend for Sparse

Posted Aug 30, 2011 7:17 UTC (Tue) by dgm (subscriber, #49227) [Link]

What FUD? The guy is talking about his own preferences, which may or may not match yours.

An LLVM backend for Sparse

Posted Aug 30, 2011 7:24 UTC (Tue) by penberg (guest, #30234) [Link]

What FUD? I didn't say there's anything wrong with GCC's plugin interface. I've only seen the documentation and never written a GCC plugin so I have no idea how the plugin interface works in practice. Maybe it's the coolest thing ever, I don't know.

That doesn't change the fact that GCC is slow and has a huge (and IMHO ugly) codebase. That's why I'd rather not spend my time on GCC.

An LLVM backend for Sparse

Posted Aug 30, 2011 4:15 UTC (Tue) by daglwn (guest, #65432) [Link] (9 responses)

> the Sparse/LLVM backend is just 705 lines of C code!

What does it do, then? Is it an LLVM analysis pass? It can't be a backend in the traditional definition of "backend" as "code generator."

> unlikely to ever be as big as the parser which is 25 KLOC - and that's
> where the real "duplication" is.

Yep. So why are we keeping that around, again?

> So I still think you're just confused and are shouting 'NIH' because you
> don't understand the underlying issues.

I may not know all the fine-grained details about Sparse but I know plenty enough about compilers to understand that they're damn hard to build and maintain. I think in the Open Source world we are at the point where there are just a few good reasons to build a new compiler:

- Learning -- this is a really important reason, BTW, because no one learns this stuff in school anymore

- Domain-specific languages

- Maybe others I can't think of right now?

Note that contributing pieces to existing compiler projects is well worth the investment. As another commenter said, Sparse as an LLVM or Clang static analyzer pass would be fantastic!

An LLVM backend for Sparse

Posted Aug 30, 2011 6:30 UTC (Tue) by penberg (guest, #30234) [Link] (8 responses)

> What does it do, then? Is it an LLVM analysis pass? It can't be a backend in
> the traditional definition of "backend" as "code generator."

So now I'm convinced that you don't know much about LLVM either.

We are using the same LLVM C bindings as Mono, for example, is using in its
LLVM-based JIT compiler. Sparse has actually had a (buggy and incomplete) i386
backend for many years and it already linearizes the parse tree for us. It also
transforms the linearized IR into SSA form and does some optimizations on it.

So the only thing Sparse has been missing is a proper backend (as in "code
generator"). All sparse-llvm needs to do is provide mapping for Sparse's IR and
LLVM's bitcode (or whatever it's called). This happens to be 1:1 in most cases
which also explains why there's so little code.

> > unlikely to ever be as big as the parser which is 25 KLOC - and that's
> > where the real "duplication" is.
>
> Yep. So why are we keeping that around, again?

For example, because...

- it's a nice, clean codebase with established community working on it

- it's useful for Linux kernel developers and we want to make it even more
useful

- I'd much rather hack on Sparse (which I know reasonably well) than Clang
which, btw, also supports C++ and Objective C - two languages I am totally
uninterested in

> I may not know all the fine-grained details about Sparse but I know plenty
> enough about compilers to understand that they're damn hard to build and
> maintain. I think in the Open Source world we are at the point where there are
> just a few good reasons to build a new compiler:

In all honesty, you don't seem to understand the big picture either. LLVM was
_built_ for the sort of thing we are doing. Sure, there's overlap with Clang
(which also uses LLVM) but that's definitely not my fault nor the Sparse
folks.

This may come as a shock to you but even the OpenBSD are working on a C
compiler that's not GCC nor Clang:

http://pcc.ludd.ltu.se/

So it seems to me that the _developers_ in the "Open Source world" don't seem
to agree with your argument that two compilers is more than enough.

[ For a very good reason too. I think many developers have been burned by GCC
and don't necessarily see Clang (which is heavily sponsored by Apple)
changing all that. So they do what they can to have some control over their
toolchain. ]

An LLVM backend for Sparse

Posted Aug 30, 2011 7:32 UTC (Tue) by dgm (subscriber, #49227) [Link]

> So it seems to me that the _developers_ in the "Open Source world" don't seem to agree with your argument that two compilers is more than enough.

"Two is an impossible number, and can't exist" - Isaac Asimov's in The Gods Themselves.

Also, you may find interesting to look up the ZOI (Zero, One, Infinity) Rule.

An LLVM backend for Sparse

Posted Aug 30, 2011 16:10 UTC (Tue) by daglwn (guest, #65432) [Link] (6 responses)

> So now I'm convinced that you don't know much about LLVM either.

Well, that's true of course. Only enough to hack on it every day. :)

> Sparse has actually had a (buggy and incomplete) i386
> backend for many years

> All sparse-llvm needs to do is provide mapping for Sparse's IR and
> LLVM's bitcode

So you dropped a custom, buggy, incomplete code generator for one that's robust and stress tested every day because (wait for it) it's damn hard to build and maintain. ;)

That's good! This is a very good approach. Translating a custom IR into LLVM IR makes good sense.

[Concerning the parser]

> it's a nice, clean codebase with established community working on it

That's a legit reason to keep it around. The question, of course, is whether it's enough of a reason. If Sparse developers think it is, good on them, they should keep hacking on it. But it's an awful big and complicated piece of code.

> it's useful for Linux kernel developers and we want to make it even more
> useful

That sort of goes without saying. :)

What's unfortunate is that the improvements to Sparse won't be widely shared and used by other people not working on the Linux kernel. We're losing some of the power of Open Source.

> I'd much rather hack on Sparse (which I know reasonably well) than Clang

That's a rather weak argument. Familiarity is important and there certainly is a learning cost to switching. But again, one has to weigh the costs and benefits. Maybe the benefits aren't enough. That's totally fine.

> which, btw, also supports C++ and Objective C - two languages I am
> totally uninterested in

Does support for them actually hamper what a clang/LLVM Sparse pass might do?

> This may come as a shock to you but even the OpenBSD are working on a C
> compiler that's not GCC nor Clang:

Yep, I'm aware of it.

> For a very good reason too. I think many developers have been burned by > GCC and don't necessarily see Clang (which is heavily sponsored by Apple)
> changing all that.

Oh I fully understand their concerns. :(

An LLVM backend for Sparse

Posted Aug 30, 2011 17:25 UTC (Tue) by penberg (guest, #30234) [Link] (5 responses)

> Well, that's true of course. Only enough to hack on it every day. :)

So are you really telling me that a LLVM developer wants me to work on
Clang instead of Sparse for the greater good of open source? I want some
of that good stuff you're smoking too!

An LLVM backend for Sparse

Posted Aug 30, 2011 18:20 UTC (Tue) by daglwn (guest, #65432) [Link] (4 responses)

Besides being an _ad_hominem_, you've got the wrong target. I am not an Apple employee and I fully support things like GPLv3. You're barking up the wrong tree.

An LLVM backend for Sparse

Posted Aug 30, 2011 18:51 UTC (Tue) by penberg (guest, #30234) [Link] (3 responses)

It's not ad hominem. You affiliation with LLVM is very relevant for the issue at hand.

That said, I'm not claiming malicious intent on your part but it does undermine the credibility of your "NIH" and "duplication" arguments. Surely you can see that too?

An LLVM backend for Sparse

Posted Aug 30, 2011 22:00 UTC (Tue) by daglwn (guest, #65432) [Link] (2 responses)

> It's not ad hominem.

Actually, it is. You're attacking the messenger, not the message.

> You affiliation with LLVM is very relevant for the issue at hand.

What "affiliation?" I in no way get paid by, represent or otherwise am officially connected to the LLVM development leadership in any way. I contribute code when I can. I just happen to see it and clang as a good platform for something like Sparse as they tackle the same set of problems.

But in any case, this is moot.

> That said, I'm not claiming malicious intent on your part but it does
> undermine the credibility of your "NIH" and "duplication" arguments.
> Surely you can see that too?

No, I can't. I made the exact same argument when the Apple guys started up libc++. I try to be at least somewhat fair in my critiques. :)

It turns out that the Apple guys had some compelling reasons to do libc++. I didn't agree with all of them but I understood them. The same is true for Sparse. If the Sparse people don't see a benefit to doing the clang thing, that's perfectly fine. It's probably a loss for the rest of us but if clang people really want the functionality they can code it up themselves.

An LLVM backend for Sparse

Posted Aug 31, 2011 6:10 UTC (Wed) by penberg (guest, #30234) [Link] (1 responses)

[ This is getting off-topic so I'll make this my last post on this particular
issue. ]

> What "affiliation?" I in no way get paid by, represent or otherwise am
> officially connected to the LLVM development leadership in any way. I
> contribute code when I can. I just happen to see it and clang as a good
> platform for something like Sparse as they tackle the same set of problems

I don't get paid to hack on Linux or Sparse either. That doesn't make me
any less biased compared to the other developers that are getting paid. Look, I
don't have any problem with people being biased toward the projects they work
on. That's pretty much natural. You failed to disclose that early on which
weakens your argument.

Imagine that the Haiku kernel developers were adding, say, NTFS support to
their kernel. Then imagine me as Linux kernel developer accusing them of "NIH"
and "duplication" and asking them why they don't work on Linux instead. Imagine
me telling them that "we in the open source world" are at the point where
there's very few reasons to implement their own kernel.

Now imagine me doing all that without actually telling them I'm a Linux kernel
developer.

See the difference?

An LLVM backend for Sparse

Posted Aug 31, 2011 10:33 UTC (Wed) by pboddie (guest, #50784) [Link]

Now imagine me doing all that without actually telling them I'm a Linux kernel developer.

Personally, I think it can be bad enough even if you do know where someone is coming from.

I'm all for people learning from and reusing the work that's already out there, but I've also seen people encouraging others to join their own projects, initially for reasons of sensible collaboration ("you're working on this too, so maybe we should pool our efforts"), and then becoming more aggressive towards their supposed competitors ("that other project is obsolete, use ours!"), frequently springing from the belief that there's only one way that things should be done in a particular domain and that way is their way.

Discouragement of independent work that may overlap with more well-known projects might seem like it helps all parties, but as everyone should know by now, people aren't always motivated primarily by how useful they are to some larger project or how productive they are at making things for the wider community. Moreover, when heavily-promoted projects that have grown at the expense of other efforts eventually fail or fall into decline, as some do, it's best to have people doing similar things in different ways.

Communities shouldn't put all their eggs in one basket, and they generally don't want to anyway.

An LLVM backend for Sparse

Posted Aug 30, 2011 4:47 UTC (Tue) by jmalcolm (subscriber, #8876) [Link] (4 responses)

Are we really making a fuss because an existing project made an enhancement to their working code-base which is currently enjoyed by an active community (including Linus it seems)?

Really?

Are we (not users of the project) really suggesting that the authors and users of this software are committing some sort of offense for not abandoning their work for something we like better?

Really?

It seems to me that:

- Sparse has existed for a while
- Sparse is in active use
- We are talking about an "enhancement" to Sparse
- This is a user requested feature
- Sparse is smaller and more highly tailored to it's purpose than our suggested alternative
- It sounds like our alternative does not actually work (currently) for the users of Sparse
- We are being pretty arrogant by calling them out with accusations of "NIH"

Just my opinion.

People were against Clang too by the way. I for one am pretty excited that Clang exists.

You might retort that Clang is different than GCC and fills a unique need while Sparse is clearly just duplicated effort.

1) I do not subscribe to the competition is wasted effort school of thought

2) I have no reason to believe the Sparse developers would be working on Clang if Sparse did not exist.

3) If it was true that Sparse did not add anything valuable to the mix then all it's users would abandon ship and we could all safely ignore it. If that is not happening, it probably means us by-standers are simply too ignorant to comprehend what makes it valuable.

An LLVM backend for Sparse

Posted Aug 30, 2011 9:10 UTC (Tue) by tzafrir (subscriber, #11501) [Link] (1 responses)

Also note that Sparse has a slightly odd license (OSL 1.1). Odd enough to keep it out of e.g. the main Debian archive:

From the copyright file of the Debian package:

This package is targetted at the Debian "non-free" section because of the
"Jurisdiction, Venue and Governing Law" clause (11). The "Mutual Termination
for Patent Action" clause (10) is less problematic, especially in the light of
the "Grant of Patent License" clause (2).

An LLVM backend for Sparse

Posted Aug 30, 2011 10:50 UTC (Tue) by penberg (guest, #30234) [Link]

There's people working on getting Sparse re-licensed under the MIT license:

http://lwn.net/Articles/328560/

An LLVM backend for Sparse

Posted Aug 30, 2011 16:33 UTC (Tue) by daglwn (guest, #65432) [Link] (1 responses)

> Are we really making a fuss because an existing project made an
> enhancement to their working code-base which is currently enjoyed by an
> active community (including Linus it seems)?

"Making a fuss" isn't quite a fair characterization. I'm simply asking important questions that should always be asked. Maybe the answer to those questions is, "keep what we have." That's fine. What's not fine is never asking the questions.

An LLVM backend for Sparse

Posted Aug 30, 2011 16:42 UTC (Tue) by dlang (guest, #313) [Link]

so let's turn it around

Sparse is older the CLAN, shouldn't the CLANG people now disband and move over to Sparse?

while it is always good to spot duplication, the extent of your posts (bordering on harassment) complaining that an older project should not exist because it now added a feature that makes it sound like it's overlapping a newer project is far from being reasonable.

An LLVM backend for Sparse

Posted Aug 29, 2011 19:12 UTC (Mon) by davecb (subscriber, #1574) [Link]

One generally wants more than one target for a given compiler or, in this special case, component. That keeps you from writing a compiler that "knows" certain things aren't true, and can thereby hide subtle bugs.

--dave

An LLVM backend for Sparse

Posted Aug 31, 2011 12:23 UTC (Wed) by ortalo (guest, #4654) [Link] (1 responses)

What are the practical improvements you expect (or have already obtained) for sparse analysis results from being able to produce working code? Maybe some examples would help me understand the kind of things you target?

BTW, would these results be generalizable to GCC-produced kernels or not? For example, if you can guarantee that the sparse+LLVM-compiled kernel does not exhibit some specific kind of programming error, would this be applicable to the same kernel compiled by GCC?
I expect a no, but I do not understand all the details.

Rodolphe

PS: I do not want to enter the Clang vs sparse debate. I've listed both on the same course slide for several years; and I am *very* happy to see *both* tools making advances.
Such static analysis topics seem intrinsicly difficult (at least, that's what the students seing the above mentionned slide feedback to me). It would be nice if both of you could provide more details (even 2 articles) on the recent advances and remaining perspectives in their respective projects, instead of well... you see what I mean. That wouldn't be duplicated effort because well, maybe the most difficult in this area is to teach would-be developers how to help.

An LLVM backend for Sparse

Posted Sep 1, 2011 5:44 UTC (Thu) by penberg (guest, #30234) [Link]

> What are the practical improvements you expect (or have already obtained) for
> sparse analysis results from being able to produce working code?

For example, Jeff discovered problems in the linearized IR which were caused by
bugs in the CSE algorithm that were fixed by Kamil Dudka:

https://github.com/penberg/sparse-llvm/commit/556cb86326b...

https://github.com/penberg/sparse-llvm/commit/7ac3e4bd792...

I don't know what practical problems that specific problem caused for the
'semantic analysis' parts but I'd assume it falls into either 'false positive'
or 'false negative' errors in some of the semantic checks. We've also
discovered problems in the way Sparse handles the C99 _Bool data type and
several weaknesses in its floating point support. That said, it's been a pretty
smooth ride so far.

Hopefully the outcome of the project is that sparse's semantic analysis will be
more accurate. I'm also testing sparse-llvm against sparse itself so hopefully
we'll improve support for non-kernel projects as well. I don't know the
frontend side of things so I don't know if there's other things on the semantic
analysis side we'll help with.

> BTW, would these results be generalizable to GCC-produced kernels or not? For
> example, if you can guarantee that the sparse+LLVM-compiled kernel does not
> exhibit some specific kind of programming error, would this be applicable to
> the same kernel compiled by GCC?

Even if the kernel compiles with sparse-llvm, the results with GCC might still
be completely different. Maybe there's a bug in sparse-llvm that masks an error
or maybe there's a bug in GCC. The whole point of semantic analysis on C is to
discover errors, not to prove correctness of the program.

> PS: I do not want to enter the Clang vs sparse debate.

I think it's pointless to even compare the two. Sparse is much smaller and more
limited than Clang and the heavy lifting is being done by LLVM for both.

An LLVM backend for Sparse

Posted Aug 31, 2011 23:28 UTC (Wed) by landley (guest, #6789) [Link] (1 responses)

That is awesome, but what I'd _really_ like to see is sparse coupled to QEMU's TCG (Tiny Code Generator).

Rob

An LLVM backend for Sparse

Posted Sep 1, 2011 5:32 UTC (Thu) by penberg (guest, #30234) [Link]

> That is awesome, but what I'd _really_ like to see is sparse coupled to QEMU's
> TCG (Tiny Code Generator).

Can you elaborate on why?