14

Why is LLVM's intermediate representation (LLVM IR) assembly-like rather than tree-like?

Alternatively, why do language implementations target LLVM IR rather than clang's AST?

I'm not trying to ask two different questions at once if it seems that way. To me, it simply seems like both client and library programmers have come to the consensus that LLVM's API, nothing more and nothing less, is obviously good software design and my question is "why?".

The reason I ask is that it seems like LLVM could provide more functionality to frontends if it's IR was AST-like because then clang's AST-based tools could be used for any frontend. Alternatively, languages that target LLVM IR could get more functionality if they targeted clang's AST.

Clang has classes and functions for creating and working with ASTs and it's the only frontend project that's strongly tied to the LLVM project so why is clang's AST-functionality external to LLVM?

Off the top of my head, I know that Rust (rustc), D (ldc), and Haskell (GHC) can all use LLVM as a backend but they don't use the Clang AST (as far as I know, I could be wrong). I don't know all the internal details of these compilers but at least Rust and D certainly seem like they could be compiled to clang's AST. Maybe Haskell could too, but I'm much less certain about that.

Is this because of historical reasons (LLVM originally being a "low-level virtual machine" and clang coming along later)? Is this because other frontends want to have as much control as possible over what they feed to LLVM? Are there fundamental reasons that clang's AST is inappropriate for "non-C-like" languages?

I don't intend this question to be an exercise in mindreading. I just want it to be helpful to those of us who are curious about, but not already fluent in, compiler design. Since the LLVM and clang projects are developed in public, I'm hoping that someone familiar with the development of these projects can answer or that the answer is obvious enough to some compile nerds that they feel confident enough to answer.


To pre-empt some obvious but unsatisfactory answers:

Yes, having an assembly-like IR gives more control to whoever crafts the IR (perhaps X lang has a better codebase and AST format than clang) but if that's the only answer, then the question becomes "why does LLVM only have an assembly-like IR instead of a high level tree-like IR and a low-level assembly-like IR?".

Yes, it's not that hard to parse a programming language into an AST (at least compared to the other steps of compiling). Even so, why use separate ASTs? If nothing else, using the same AST allows you to use tools that operate on ASTs (even just simple things like AST printers).

Yes, I strongly agree that being more modular is a good thing, but if that's the only reason, then why do other language implementations tend to target LLVM IR instead of clang's AST?

These pre-emptions might be erroneous or overlook details, so do feel free to give these answers if you have more details or my assumptions are mistaken.


For anyone wanting to answer a more definitively answerable question: what are the advantages and disadvantages of an assembly-like IR vs a tree-like IR?

  • 1
    I'm not an LLVM expert, but I think there is a little misunderstanding on your side. LLVM does not have asm like IR. In fact, its IR is more like a graph than a tree. I assume that by 'asm-like' you are referring to the human readable IR (*.ll files), if so then it is done just for convenience. But, let's wait for a real expert who can give more comprehensive answer :) – AlexDenisov Aug 16 '17 at 10:36
  • 1
    One important aspect may be history: LLVM was originally designed to decouple compiler backends from compiler frontends. The idea was that compiler vendors would compete on language optimizations, and CPU vendors would compete on low-level optimizations. E.g. Microsoft and Apple would compete against each other whose C compiler produces the "best" bitcode from C, and Intel and AMD would compete against each other whose LLVM backend produces the "best" machine code from bitcode. Application vendors would ship their applications in bitcode, and the final compilation would be done on the user's … – Jörg W Mittag Aug 16 '17 at 12:33
  • 1
    … machine. LLVM started at a time, where it was not at all clear that everybody would be using Intel. Apple was still on PowerPC, Intel was still pushing Itanium, and so on. AFAIK, Apple still uses LLVM in this way, in some of its 3D frameworks, where code is shipped as bitcode and then compiled for either nVidia or ATI depending on what kind of card is installed. – Jörg W Mittag Aug 16 '17 at 12:36
  • 1
    Forgive me, but what is an IR? – Adam Copley Aug 16 '17 at 17:59
  • 1
    @AdamCopley intermediate representation – Praxeolitic Aug 16 '17 at 19:02
13

There's a number of inter-related questions here, I'll try to separate them as best I can.

Why do other languages build on LLVM IR and not clang AST?

This is simply because clang is a C/C++ front end and the AST it produces is tightly coupled to C/C++. Another language could use it but it would need near identical semantics to some subset of C/C++ which is very limiting. As you point out, parsing to an AST is fairly straightforward so restricting your semantic choices is unlikely to be worth the small saving.

However, if you're writing tooling for C/C++ e.g. static analysers, then re-using the AST makes a lot of sense as it's a lot easier to work with the AST than the raw text iff you're working with C/C++.

Why is LLVM IR the form it is?

LLVM IR was chosen as an appropriate form to write compiler optimisations. As such, it's primary feature is that it's in SSA form. It's quite a low level IR so that it is applicable to a wide range of languages e.g. it doesn't type memory as this varies a lot across languages.

Now, it happens to be the case that writing compiler optimisations is quite a specialist task and is often orthogonal to language feature design. However, having a compiled language run fast is a fairly general requirement. Also, the conversion from LLVM IR to ASM is fairly mechanical and not generally interesting to language designers either.

Therefore, lowering a language to LLVM IR gives a language designer a lot of "free stuff" that is very useful in practice leaving them to concentrate on the language itself.

Would a different IR be useful (OK, not asked but sort of implied)?

Absolutely! ASTs are quite good for certain transformations on the program structure but are very hard to use if you want to transform program flow. An SSA form is generally better. However, LLVM IR is very low level so a lot of the high level structure is lost (on purpose so it's more generally applicable). Having an IR between the AST and the low level IR can be beneficial here. Both Rust and Swift take this approach and have a high level IR between the two.

  • Haskell has a number of IRs before it gets to LLVM, as well. – DylanSp Aug 16 '17 at 13:41
  • 1
    @ DylanSp Indeed. It's starting to become de facto best practice for complex languages. For example, Rust didn't do this initially and has refactored to include a high level IR. I also believe there has been some talk about doing this for clang but I'm not sure where that went. – Alex Aug 16 '17 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.