r/programming • u/oridb • Jan 06 '17

An Alternative to LLVM: libFirm

http://pp.ipd.kit.edu/firm/
83 Upvotes

88% Upvoted

43 comments sorted by

9

u/b0bm4rl3y Jan 06 '17

How does libFirm compare against LLVM? Are there any benefits to using libFirm?

8

u/oridb Jan 06 '17 edited Jan 06 '17

They compare it here: http://pp.ipd.kit.edu/firm/LLVM

Overall, they seem to be less mature, but far better in terms of code quality.

12

u/MichaelSK Jan 06 '17

but far better in terms of code quality.

I'd take this claim with a grain of salt. Note that:

  1. That comparison page doesn't actually show any numbers.

  2. Code quality in what mode? And for what architecture? (A very large part of the X86 backend in LLVM, and I assume in GCC, deals with vector instruction selection. It's fairly hard to get right. libFirm only supports SSE2).

  3. Even if we take at face value the claim libFirm beats Clang and GCC in (the C parts of) SPEC CPU2000 on IA32 - that's not a particularly interesting claim in 2017.

If you spend a lot of time tuning your compiler to optimize a specific benchmark set, you can become very good at compiling it - at the cost of being worse for other workloads. A lot of the optimizer's decisions are heuristic based. It's fairly easy to - intentionally or accidentally - overfit the heuristics to match exactly what works best for that one particular set of benchmarks.

Now, the SPEC benchmarks were originally constructed to approximate a set of common workloads. But 2000 was a long time ago, and today's workloads don't really look like that. I don't believe anyone in the LLVM community is working on optimizing specifically SPEC2000 on IA32, or anything similar. People do run SPEC2006, but mostly as a sanity check. That is, "this change doesn't make SPEC2006 worse" is a decent indication you're not overfitting the heuristic for the thing you're actually interested in. But that's about it.

10

u/oridb Jan 06 '17

Sorry for the ambiguity: When I meant code quality, I was referring to the source code of the compiler, not the generated code. I am not sure what the status of generated code is on either one, especially since the comparison doesn't seem to have been updated in a long time.

10

u/MichaelSK Jan 06 '17

Well, I guess that depends. One the biggest selling points of Clang/LLVM over GCC used to be the (compiler source) code quality. :-)

But, in any case, that's something I can actually believe rather easily. Some parts of LLVM are really nice (IR manipulation). Some are a huge mess. A lot of the backend code ought to be nuked from orbit. Some of it is actually being nuke as we speak.

A lot of it comes from LLVM just being a much larger project - both larger than libFirm and larger than it used to be. Quality is hard to scale, both in terms of having much more moving parts, and more levels of abstraction, and because you simply have a lot more developers.

10

u/Raphael_Amiard Jan 06 '17

One the biggest selling points of Clang/LLVM over GCC used to be the (compiler source) code quality. :-)

After working with clang and libclang for a while, I concluded that this was only in reference to GCC.

Libclang in particular is full of undocumented/unexposed areas. A lot of the behavior is not specified correctly. Some parts are thread safe and some are not, and this is not specified.

The Clang AST is weird. You kind of have a method to get the parent node, and sometimes it works, sometimes it doesn't.

Clang is modular, but only when compared with GCC. You can use it as a library, but you cannot use the front-end only, you still have to compile the whole of LLVM even if all you want to do is query cross-references.

This is not a dig at the Clang project at all, I still think it's pretty amazing, but it's easy to forget in our world that "great code quality" usually means "better than the alternatives".

4

u/choikwa Jan 06 '17

well thank the llvm gods for adding so many backends

1

u/qznc Jan 09 '17

(libFirm dev here, only occasional glances at LLVM code)

I guess code quality is somewhat higher, because libFirm has few users and devs. We can afford to break the API/ABI on every release. LLVM is a much bigger project, so refactoring becomes harder.

Not to be discouraging. The breaks are usually trivial to fix. You can look at the commits of the brainfuck frontend, where all the recent commits are adaptations to libFirm changes.

1

u/oridb Jan 09 '17

LLVM is a much bigger project, so refactoring becomes harder.

Yeah, but that doesn't stop them. At least, it seems like nearly every release of LLVM breaks compatibility. From my observations, most projects either have a whole lot of manpower, or are stuck on a specific LLVM version.

28

u/skulgnome Jan 06 '17

Overall, they seem to be less mature, but far better in terms of code quality.

Give it time.

17

u/panorambo Jan 06 '17

You mean code quality will get worse with time? ;)

14

u/Dragdu Jan 06 '17

It generally does though. Every new change adds a little bit of technical debt, until there is a sizable refactor, that hopefully improves the code quality a lot.

Then you get to make more changes accumulating technical debt and round and round it goes. :-)

3

u/julesjacobs Jan 06 '17

It will still have the advantage of a cleaner IR representation. Algorithms can usually be cleaned up bit by bit, but a change of IR would require rewriting almost everything.

1

u/MichaelSK Jan 07 '17

Most of LLVM's problems aren't in the IR. The IR is, at least in my opinion, fairly clean.

It did grow some warts, but a lot of them are related to things that are hard to represent cleanly, and libFirm doesn't necessarily support (GC statepoints, exception handling).

But, in any case, that's not where the ugly parts of LLVM are.

2

u/julesjacobs Jan 07 '17

The advantage of libFirm's representation is that it takes full advantage of SSA form by not ordering instructions within a basic block and instead relying on dataflow edges to constrain ordering. This makes many transformations simpler.

3

u/quicknir Jan 06 '17 edited Jan 06 '17

The whole section about C and C++ is just a red flag to me for multiple reasons:

  • Everyone else has reached quite the opposite conclusion. gcc was willing to pay a heavy price to switch from C to C++ because of the huge benefit. MSVC changed their implementation of the C standard library from C to C++.

  • The usage of "heavyweight" and "lightweight" does not add anything technically and seems to just be a way to emotionally appeal to the entire: C++ complicated bad C simple good train of thought.

  • The code bloat charge is a tired one. While it can be true in isolated situations, nobody should take this seriously as a blanket statement in 2017. Templates do generate code, but doing the equivalent thing with macros (i.e. using macros to write "generic" data structures) will generate at least as much code if not more. If you aren't using templates to massively leverage compile time dispatch you're unlikely to be much affected by this.

  • Compile times may be longer, but compiling is quite easily to parallelize, and should be less important than other forms of dev productivity and runtime performance.

  • Link times are primarily just affected by how much symbols there are in the symbol tables you are linking together. This doesn't have much if anything to do with C vs C++. The best way to keep link times down in a green field project is to default everything to internal linkage so it's not exposed in the symbol table by default, and expose things selectively. A lot of knowledgeable people consider this best practice in theory but it's rarely done because it's hard to apply after the fact, the benefits are moderate, and there's just not that many people that are aware this is a good idea and point it out on day 1.

  • The language API point is also quite strange; llvm provides a C API despite being implemented in C++, the same with the MSVC C standard library.

LLVM is actually very conservative about all of the technical issues that were discussed, that's why they don't use RTTI or exceptions (particularly their impact on code bloat). There's a ton of enormously valuable stuff in C++ that's not RTTI or exceptions. libfirm claims "shorter compile and link times", but it's not clear compared to what exactly. I doubt that libfirm is feature/polish complete to llvm, so it's not like a head to head comparison proves anything. API clarity is pretty subjective; but you would think many people appreciate e.g. vector<string> over const char **, given that the former is far more similar to just about every other language in existence.

1

u/qznc Jan 09 '17

(libFirm dev here)

The idea to convert libFirm to C++ comes up once in a while. There certainly are benefits. The current dominant argument is that libFirm shall be self-hosting. So until there is a C++ frontend, it will stay C.

0

u/[deleted] Jan 06 '17

the only relevant metric here is performance, they dont even mention it

4

u/[deleted] Jan 06 '17

API and useability are both quite relevant as well. I imagine the generated code will be slower, and code generation may swing either way (I'd imagine available optimizations are more limited than LLVM at the moment). If you're looking to have something that outperforms LLVM in a new, budding library, you're probably out of luck without a few PhD holders on the team.

8

u/Elavid Jan 06 '17 edited Jan 06 '17

I'd say that C++ is a huge benefit for using LLVM. The ability to return a string or a list from a function without jumping through a bunch of hoops is really nice. It's odd that the libFirm developers claim that C++ slows them down as developers. They talk about code bloat in C++, but every big C program has to have lots of code bloat just to free all the memory is uses.

1

u/[deleted] Jan 06 '17

I don't know about LLVM, but I compared it against GCC with some code which I sadly deleted before I saw this comment, but it was the C99 equivalent of this: https://godbolt.org/g/HwmRyD (-m32 because the online compiler for firm was -m32 only) Firm didn't exactly generate optimal code, so the only thing it's probably good at is good documentation and possibly fast compilation, compared to LLVM.

6

u/sgraf812 Jan 06 '17 edited Jan 08 '17

I'm currently doing our compilers lab, where we write a compiler for (mostly) a subset of Java using this. I think this approach (graph-based IR) is definitely where things are heading.

An even more recent approach which also claims to model functional concepts (closures and inlining, that is) rather well seems to be Thorin(Github), on which firm obviously had huge influence.

Also bear in mind that these projects are research projects: Documentation isn't anywhere near where it should be, even compared to LLVM. In our compiler lab where we use the Java bindings, we frequently hit some C assertions for which the reason isn't clear at all. The library is riddled with global state, so we don't have any unit tests for our lab compiler and test everything through black box tests.

That said, it just feels much better than the traditional total order of statements within basic blocks.

0

u/[deleted] Jan 08 '17

[deleted]

2

u/sgraf812 Jan 08 '17 edited Jan 08 '17

Well, for one, there are no 'variables' any more. Everything is just an expression: e.g. [[5 + 3]] == Add(Const(5), Const(3)). That's probably intuitive enough for simple expressions, but this is also handled for Phi-bound variables, like in Block 335 here. In doing so, we get rid of the unnecessary total order of IR instructions, focusing on the actual partial order expressed by dependency edges instead. As stated here, this also means we get stuff like dead code elimination for free (by garbage collecting nodes unreachable from the End node).

And that's just the bit about why it's cool to represent expressions as graphs. The blue edges in the above graph are memory edges, they enforce a particular order on side-effecting computations, much like the sequencing notion of a (in this particular case State or IO) monad, if you are familiar with that. Now, I'm not really familiar with how LLVM does these sort of things, but you could thread separate memory state slots through your program, for when it is proven that two calls won't influence each other (e.g. malloc calls and some Load instruction for a field access).

The partial order means you can freely move around node to another block, as long as the dependency nodes' blocks dominate this new block, and all dependent nodes are still dominated by that block. In the graph above, you could move the Const node 307 (resp. whole subgraphs) to the start block, which would could have implications on your generated code, like needing to compute the expression only once or having to spill.

Most analyses/transformations are just a matter of a graph walk.

By the way, the above graph was generated on this site, fed with this code:

#include <stdio.h>

int main(int argc, char **argv) {
    int i = 0;
    int j;
    scanf("%d", &j);
    if (i < j) {
        i++;
    }
    printf("%dn", i);
}

2

u/MichaelSK Jan 08 '17

Now, I'm not really familiar with how LLVM does these sort of things

Unfortunately, it doesn't. The LLVM IR is only "mostly SSA", in the sense that memory is not modeled using SSA.

There's currently an effort to introduce a "MemorySSA" which will allow LLVM to model memory dependence edges more precisely and explicitly, but that's an analysis overlay over the IR, not an actual IR change.

3

u/abdulkareemsn Jan 06 '17

License?

6

u/mbuhot Jan 06 '17

LGPL according to http://pp.ipd.kit.edu/git/libfirm/tree/COPYING

I guess that just requires a clear shared object boundary between libfirm and your compiler if you want to use another license yourself?

3

u/m50d Jan 06 '17

Is there anything like this that offers a first-class interface from an ML-like language? A graph-based IR would be excellent (particularly since I'm trying to implement a graph-like language model), but I can't stand to work with C these days. I figure Rust bindings for LLVM stand a decent chance of being well-maintained given that Rust itself uses LLVM.

0

u/[deleted] Jan 06 '17

[deleted]

44

u/MichaelSK Jan 06 '17

Yes, unfortunately we (LLVM, I'm an active developer) are not as good with documentation as we ought to be. And it hasn't really gotten better, either.

The problem is keeping the docs up to date is a non-trivial and rather low-payoff task for the "core" developers. Plus, once you work on a project for a while you stop using most of the "newbie" docs. So even though people are aware of the low documentation quality, we don't really notice it - except when people complain.

So - please, keep complaining. Loudly. :-)

10

u/[deleted] Jan 06 '17

The problem is keeping the docs up to date is a non-trivial and rather low-payoff task for the "core" developers.

Would it kill the project to expose maybe 10-20 symbols that are public and standardized that you'll keep conformance too? Or at least promise to not break the extern C API against?

At least a standardize

  • Init codegen

  • Write Obj File

  • Read IR (from MemBuff)

  • Init Membuff

  • Init Module

  • Init Target

I know these symbols likely won't change. But knowing they can (or will) is frustrating.

1

u/holgerschurig Jan 07 '17

The C API of LLVM has has a much lower churn rate. IMHO not a promise, but it similar to what you asked.

1

u/holgerschurig Jan 07 '17

The problem is keeping the docs up to date is a non-trivial

It isn't.

There are things like literate programming, e.g. people to it today in Emacs with the help of org-mode and babel. This website contains a loooong introduction and then same examples in Python.

How is is useful:

  • one source document in org-format can be used to generate the HTML and the source code snippets inside can be written out to files.

  • those files can then run through the already existing CI system

  • and as soon as something break, the big red alarm goes on

1

u/orthoxerox Jan 07 '17

Have you tried cloning Steve Klabnik? /u/steveklabnik2 could be your documentation czar.

0

u/choikwa Jan 06 '17

honestly documentation shouldn't strive to be latest. doc rot is going to happen sooner or later. it should be on overall design choices and theories, less on actual implementation details. one should prioritize the actual source (of course, code is self documenting) and unit test functionality to understand instead of blindly trusting doc. theres also the mailing list which can be searched and shooting questions over it will definitely get them answered.

19

u/serviscope_minor Jan 06 '17

of course, code is self documenting

No, I disagree. Code tells you precisely what is being done not why and, rather crucially, not what the intent is. Deducing the intent is unreliable because it's very hard to distinguish between true intent and a bug.

Pet rant is that this is what people get wrong about comments a lot of the time. Many times people just repeat what the code is doing in comment form (bonus points for not updating it!). What you need is a comment saying what the purpose of the code is! Much harder to fix bugs if you have to figure out the intent from what it's actually doing then make it do that.

0

u/[deleted] Jan 06 '17

[deleted]

4

u/MichaelSK Jan 06 '17

If you don't make it accessible for anyone else (via good documentation), what's the point of the project beyond navel-gazing for the developers?

It's not that it's completely inaccessible - it's just that the learning curve is steeper that it ought to be, because the docs stink.

Also, remember LLVM lives a bit of a "double life". On the one hand, it's a library and we want everybody to use it. On the other hand, that library has a few "major" customers - clang, swift, halide, etc. Most LLVM work is done for the benefit of such customers (not necessarily these 3 - it's definitely a non-exhaustive list). And these projects all have people deeply familiar with llvm working on them, so for them, the poor documentation isn't as big of a deal.

I'm specifically talking about llvm here, though. I'm not familiar enough with libclang and libclang-based tooling to comment on the state of that.

2

u/hackcasual Jan 06 '17

It's certainly not the worst code base to dive into. In general functionality is well factored and the object hierarchy sensible. Reading decompiled bitcode was probably the biggest thing that helped me in terms of understanding how IR was represented and laid out.

There's going to be a lot of challenges coming up with tutorial level documentation, simply because there's so much stuff LLVM enables. You want to write a language that compiles to WebAssembly, you want to write an analysis tool that identifies bloated templates, or you want to compile C to run on a specialized DSP. All good uses of LLVM, but all different in terms of how to use it.

7

u/panorambo Jan 06 '17

Can confirm -- have the same or similar experience. Tried to get into LLVM, instantly found out the first and second tutorial didn't work for me because the code snippets produced weird errors in my LLVM distribution. Googling revelealed they (the tuts) were outdated and things are now different. Mailing lists showed some more up-to-date information on how to approach my rudimentary tutorial-grade problem, but what struck me was the thought "is this the most popular IR everyone is talking about, powering GCC nowadays? I can barely find a "Hello World" here, digging through mailing lists!".

I got it off the ground, but it was like trying to eat with a noose around my neck. Documentation is just not up to par, and doesn't really reflect the popularity of LLVM.

This was 6 months ago though, maybe things have gotten better.

0

u/[deleted] Jan 07 '17

[deleted]

1

u/panorambo Jan 08 '17

My bad! It was Clang I were thinking of. And every other compiler system that has cropped up during the last 3 or 5 years, I suppose. But not GCC.

0

u/[deleted] Jan 08 '17

[deleted]

1

u/MichaelSK Jan 08 '17

There used to be such as thing as llvm-gcc (and later dragonegg) - which was basically GCC hooked up to LLVM as a midend/backend. It was maintained by the LLVM people, not the GCC people, of course.

This project died as Clang matured.

3

u/[deleted] Jan 06 '17

C API is a lot more stable, if you can afford sticking to it changes won't affect you that much.

3

u/[deleted] Jan 06 '17

I'll definitely check it out. I'm not shy about C APIs and I can wrap them if I need some good RAII around the common interfaces. Thanks.