An LLVM backend for Sparse

Posted Aug 29, 2011 20:35 UTC (Mon) by penberg (guest, #30234)
In reply to: An LLVM backend for Sparse by daglwn
Parent article: An LLVM backend for Sparse

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.

to post comments

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.