"Mapping High-Level Constructs to LLVM IR"

Project Infrastructure LLVM Dev List Archives
#1

Hi guys,

I have begun writing on a new document, named “Mapping High-Level Constructs to LLVM IR”, in which I hope to eventually explain how to map pretty much every contemporary high-level imperative and/or OOP language construct to LLVM IR.

I write it for two reasons:

  1. I need to know this stuff myself to be able to continue on my own language project.

  2. I feel that this needs to be documented once and for all, to save tons of time for everybody out there, especially for the language inventors who just want to use LLVM as a backend.

So my plan is to write this document and continue to revise and enhance it as I understand more and helpful people on the list and elsewhere explain to me how these things are done.

Basically, I just want to know if there is any interest in such a document or if I should put it on my own website. If you know of any books or articles that already do this, then please let me know about them.

I’ve attached the result of 30 minutes work, just so that you can see what I mean. Please don’t review the document as it is still in its very early infancy.

Cheers,
Mikael

MappingHighLevelConstructsToLLVMIR.rst (6.85 KB)

#2

Hi guys,

I have begun writing on a new document, named "Mapping High-Level
Constructs to LLVM IR", in which I hope to eventually explain how to map
pretty much every contemporary high-level imperative and/or OOP language
construct to LLVM IR.

I write it for two reasons:

1. I need to know this stuff myself to be able to continue on my own
language project.
2. I feel that this needs to be documented once and for all, to save tons
of time for everybody out there, especially for the language inventors who
just want to use LLVM as a backend.

We get questions like "how do I implement a string type in llvm"
frequently, so something like this is probably useful.

So my plan is to write this document and continue to revise and enhance it
as I understand more and helpful people on the list and elsewhere explain
to me how these things are done.

Basically, I just want to know if there is any interest in such a document
or if I should put it on my own website. If you know of any books or
articles that already do this, then please let me know about them.

I've attached the result of 30 minutes work, just so that you can see what
I mean. Please don't review the document as it is still in its very early
infancy.

I feel like the "lowering it to C" part is part of the typical "low level
curriculum" that is unfortunately not taught anywhere really, but I feel is
common knowledge among ... I'm not sure who, but I'm pretty sure that
almost all LLVM developers picked it up somehow, somewhere (I honestly
don't know where I did...). I would try to investigate if there is an
alternative place where these things are discussed better, since I feel
like this is not very LLVM-specific knowledge.

For covering this sort of thing inside the LLVM docs, the best way I can
think to do so is to improve docs/tutorial/ to just add those features.

If you are implementing a language, a good topic for a document that you
can probably help with is the following:
LLVM doesn't provide a "complete portable runtime environment"; you still
need to know how to e.g. get access to malloc, or link with system
libraries for basic functionality, etc. What sorts of "glue" work like the
above does a language implementor typically have to do in order to make a
runnable language?

-- Sean Silva

#3

Yes, it is sort of scary that there seems to be no definite resource to consult for information on especially advanced OOP things. I have something like 20 compiler books on my shelves and yet none of them mention a single word on how to implement multiple inheritance, exception handling, or interfaces. It seems like they are all happy about presenting a subset of Pascal, or Java, with an integer and boolean type, and then let the reader figure out all the hard stuff by himself or herself. I know I picked most of my knowledge up from doing lots of debug info converters back when C++ was just coming to market - the early C-only debuggers didn’t understand C++ so the quick solution was to convert C++ debug info into lowered C debug info :slight_smile: If you know of any compiler book that covers advanced OOP topics, please feel free to let me know the title/ISBN of it.

I was thinking of making a tutorial sometime down the road when I have myself grasped sufficient about LLVM. For the time being, I think it makes a lot of sense to first transform into C (a language known by most) and then take it one level further by transforming into LLVM IR. I cannot promise that I will make such a tutorial, but the outcome of this sub-project should definitely make it much easier to make such a tutorial. Personally, I think the lowering into C makes the difficult topics very easy to understand: Once you’ve understood how to lower a C++ class into a C structure with associated functions, almost all of the magic of the C++ class vanishes and you’re set to go.

I envision LLVM as a sort of “compiler builders’ power toolbox” and along with that vision goes a lot of great documentation that makes you fly in no time. To be honest, I personally feel that the learning curve is a bit steep. From building using a non-Microsoft compiler (on Windows) over to making a buildbot slave over to implementing an actual language using LLVM, I think the path is rather difficult. It may just be me, or it may also be that you LLVM gurus have breathed LLVM for so long that you no longer remember that not everybody getting in touch with LLVM actually wants to code on LLVM.

I’ll add a section on “How to Interface to the Operating System” to the article. I’ll focus on interfacing directly with the host operating system as I personally dislike the C run-time library for a lot of reasons (ever met a programmer who routinely checked errno? - I haven’t, although I have once or twice in my life seen Unix code that actually did bother to check errno).

Perhaps it is better if I already now plan to release this article on my own web site? I don’t want to impose it on you guys, but I definitely want to do it. I know there are more than 5.000 programming languages in the world and if only half the developers were to adopt LLVM, things would surely look much brighter with respect to the number of contributors of builders, documentation, and actual code patches.

– Mikael

#4

There is a strong bias towards C++ in the document, which isn't a particularly strong slice of higher-level constructs. For example, C++'s RTTI constructs serve three distinct purposes: exception handling, dynamic casts, and reflection (although C++'s reflection capabilities are extremely weak). You'll need to talk about inheritance in the three cases: single, multiple, and virtual (to use C++'s terminology) (note that Java's interfaces can be implemented as virtual inheritance). Boxing is another important topic. Lambdas, closures, and generators (yield keyword) are becoming increasingly common in modern programming languages, and should not be ignored.

Finally, calling propagated return values "exception handling" does an extreme disservice to your readers. LLVM IR explicitly models exception handling, and attempting to describe it lowered as return values is not how anyone should implement it. If you badly want to describe it in C terms, you could at least use C's setjmp/longjmp to describe it; the truth is, this is a feature which doesn't exist cleanly in C.

Trying to describe mapping higher-level languages to C and then C to IR is a poor idea. C is in some ways an extremely limited language (no native exception handling constructs, e.g.). If you want to be a guide to how to lower languages to LLVM IR, you need to also explain how to take advantage of features in the IR to optimize code better (e.g., TBAA). Cfront-like C++ compilers are extremely rare-to-nonexistent (in part because it is difficult to map some features, most notably exception handling, cleanly and efficiently into C); if your guide is describing such an approach, it reads like an implicit endorsement. It is possible to describe some aspects of the IR in C, but if the goal is to lower to IR, then the description should be lowering to IR, not lowering to C.

#5

Thanks, you have a lot of valid points there. I have myself long ago abandoned the path of using C as a backend language due to the very factors you mention.

However, as I said, the document was put together in 30 minutes. Not exactly ready for prime time :slight_smile:

I do agree that all of the things you mention should be described, including Lambdas, closures, and generators, but I must admit up front that I don’t know how to implement half of them. But I suppose I could do a lot of research and perhaps occasionally ask you guys for specifics.

We are not going to find much common ground on the issue of “calling propagated return values for exception handling”, I think :slight_smile: See https://www.lyngvig.org/Teknik/A-Proposal-for-Exception-Handling-in-C for the details.

I started out with C++ as the example language because a lot of people know that language - and most certainly the majority of the LLVM user base. Obviously, you’d have to add source code from other languages than C++ when C++ does not provide features to illustrate the process.

I now agree that the lowering into C is not such a good idea after all. So I’ll go straight from source language to LLVM IR, which is not that difficult after all, and won’t be very different for the reader. In fact, I think it will be much better than my original approach.

Thanks again for your valid objections.

– Mikael

#6

That appears to be comparing return value propagation to setjmp/longjmp, which is not considered a good exception handling model. Most low-cost (or no-cost!) exception handling mechanisms are based on an unwind approach, where a thrown exception causes the stack trace to be inspected to find the appropriate catch block. If exceptions are not thrown, there is no execution cost to setting up a try/catch block, although this is paid for by a relatively expensive throw implementation. Details of such an implementation can be found in the Itanium ABI <http://mentorembedded.github.io/cxx-abi/abi-eh.html> (which, despite its name, is the ABI used by gcc and clang).

#7

There are overviews of Dwarf EH in the gcc wiki

http://gcc.gnu.org/wiki/Dwarf2EHNewbiesHowto

#8

Yes, it is sort of scary that there seems to be no definite resource to
consult for information on especially advanced OOP things. I have
something like 20 compiler books on my shelves and yet none of them mention
a single word on how to implement multiple inheritance, exception handling,
or interfaces. It seems like they are all happy about presenting a subset
of Pascal, or Java, with an integer and boolean type, and then let the
reader figure out all the hard stuff by himself or herself. I know I
picked most of my knowledge up from doing lots of debug info converters
back when C++ was just coming to market - the early C-only debuggers didn't
understand C++ so the quick solution was to convert C++ debug info into
lowered C debug info :slight_smile: If you know of any compiler book that covers
advanced OOP topics, please feel free to let me know the title/ISBN of it.

Probably the best I know of as a learning resource would be this "C/C++ Low
Level Curriculum" series by Alex Darby on #AltDevBlog. The first post is <
http://www.altdevblogaday.com/2011/11/09/a-low-level-curriculum-for-c-and-c/>,
but there are a lot of them.

I was thinking of making a tutorial sometime down the road when I have
myself grasped sufficient about LLVM. For the time being, I think it makes
a lot of sense to first transform into C (a language known by most) and
then take it one level further by transforming into LLVM IR. I cannot
promise that I will make such a tutorial, but the outcome of this
sub-project should definitely make it much easier to make such a tutorial.
Personally, I think the lowering into C makes the difficult topics very
easy to understand: Once you've understood how to lower a C++ class into a
C structure with associated functions, almost all of the magic of the C++
class vanishes and you're set to go.

I envision LLVM as a sort of "compiler builders' power toolbox" and along
with that vision goes a lot of great documentation that makes you fly in no
time.

I wouldn't consider LLVM to be such a toolbox. LLVM's functionality covers
a lot, but it's mostly just the last leg of the compilation pipeline
(lowering to machine code, in object files, etc.; what is usually called
the "backend"). We have a handful of things that might be useful to a
frontend like SourceMgr, SMLoc, SMDiagnostic, et al, but those are really
very secondary and mostly incidental; maybe if someday clang's
SourceManager and diagnostics infrastructure are unified into LLVM core,
then we would be able to provide clients with that part, but it's still
mostly a "utility", and not really a huge amount of functionality.

To be honest, I personally feel that the learning curve is a bit steep.
From building using a non-Microsoft compiler (on Windows) over to making a
buildbot slave over to implementing an actual language using LLVM, I think
the path is rather difficult. It may just be me, or it may also be that
you LLVM gurus have breathed LLVM for so long that you no longer remember
that not everybody getting in touch with LLVM actually wants to code on
LLVM.

I'm pretty sure that the pain of building LLVM and all the related issues
remains a big annoyance even for seasoned LLVM developers.

I'll add a section on "How to Interface to the Operating System" to the
article. I'll focus on interfacing directly with the host operating system
as I personally dislike the C run-time library for a lot of reasons (ever
met a programmer who routinely checked errno? - I haven't, although I have
once or twice in my life seen Unix code that actually did bother to check
errno).

Perhaps it is better if I already now plan to release this article on my
own web site? I don't want to impose it on you guys, but I definitely want
to do it.

May a 1000 flowers bloom. Go for it.

I know there are more than 5.000 programming languages in the world and
if only half the developers were to adopt LLVM, things would surely look
much brighter with respect to the number of contributors of builders,
documentation, and actual code patches.

LLVM is a big dependency. Not all languages want or need that. For example,
just libLLVMX86CodeGen.a is like 8 times larger than the entirety of
LuaJIT. Also, although some recent work is helping to make LLVM better for
dynamic language compilation, LLVM is still far from being well suited for
general dynamic language compilation (and I don't think that's really a
goal for the project), except maybe for the last leg when lowering to
machine code.

-- Sean Silva

#9

Hi, documentation is always good and this is a great idea. It’ll be particularly useful as a place where additional examples of constructs from non-C-family languages could be added (since most compiler tutorials inevitably focus on languages that are a lot like C/C++/Obj-C).

I’d imagine you’ve already thought of this, but it might be something where using pseudo-LLVM-IR is of the most pedagogical use. (For example, writing code that accesses complex structured memory using multiple levels of GEP’s and then loads is quite tricky, but for a lot of the constructs it’s only a detail so you could probably express those bits using some pseudo instruction (going another step in to fully explicit LLVM-IR if necessary.)

Cheers,

Dave

#10

Hi David,

I’m glad you like the idea :slight_smile:

I’ve been busy and so far only lack about three or four things in the C++ area of features: Proper exception handling (which I need to understand myself first), closures (which I don’t think I’ve ever used), and generators (which I always wondered how they were implemented). I think you are absolutely right - some day, this document will be routinely be extended with new and wonderful language constructs and this will help these features to propagate much faster into existing and new languages as people will quickly come to realize how simple it is to do this or that feature. Besides, I think it is an awesome way of teaching people how to use LLVM IR: They can use their knowledge of familiar structures and constructs to see how it can be done in LLVM IR.

So far, it hasn’t been too bad with GEPs and loads. The most advanced example uses like two or three GEPs/loads in a row and I have already explained at the top of the document that the user should not worry - most commonly two or three LLVM IR instructions will be coalesced into a single instruction after optimization.

I’ll let your idea simmer a bit and see what comes up. For now, I have had the joy of coding up quite a few snippets in LLVM IR. I am learning to swim as I am sinking into all the intricacies of LLVM IR. So far is has only been pleasant working with LLVM IR, albeit I am a tad tired of typing types because LLVM IR demands explicit types on most expressions and arguments. But I do understand that LLVM IR is meant to be automatically generated by a compiler, not hand-crafted by a tech writer.

I’ve attached my current draft. If you are busy, don’t care, or prefer to wait for the final result, please don’t waste time on looking at it. There’s still a quite a bit to do. Comments are more than welcome, though. And feel free to suggest new language features and so on: Even if I cannot document them, I can always ask the list for help and together we can make up a great document, which I personally suspect will one day be almost as popular as the Language Reference.

– Mikael

MappingHighLevelConstructsToLLVMIR.rst (38.1 KB)

#11

Wow: that’s a lot of text to have written in a short time. I’ll try to have a detailed look later, but one borderline thing is you mention there are 6 different casts. It might be worth pointing out there’s a 7th, the addrspacecast which is beyond the scope of the document but is used with address spaces describing devices which (may) have different address spaces which are used for different things (either for performance or security reasons).

http://llvm.org/docs/LangRef.html#i-addrspacecast

Cheers,
Dave

#12

For now, I have had the joy of coding up quite a few snippets in LLVM IR.
I am learning to swim as I am sinking into all the intricacies of LLVM IR.
So far is has only been pleasant working with LLVM IR, albeit I am a tad
tired of typing types because LLVM IR demands explicit types on most
expressions and arguments. But I do understand that LLVM IR is meant to be
automatically generated by a compiler, not hand-crafted by a tech writer.

One thing you could do is just use an existing frontend (Clang, or whatever
frontend you're developing) to emit IR for simple examples - it might
require a little further massaging to simplify it down to pithy examples
without extraneous junk, but may still be faster than writing the IR out
entirely by hand.

- David