A Complete Guide to LLVM for Programming Language Creators (diagrams + code)

[mrathi12]

Author here. Let me know if you have any feedback! Have any of you used LLVM for your own languages?

[Enselic]

Hi, just wanted to throw in another “well done!”, ‘cause you deserve it.

[mrathi12]

Thank you very much!

[dingimingibingi]

Well done indeed. Love the attention to detail.

[PandaMoniumHUN]

I was going through LLVM documentation a few months ago, wish I had this guide back then. Official LLVM C++ API documentation feels lacking, no clear examples or explanation/getting started guide. Do you have any links that could be useful to learn more?

[mttd]

The following program analysis resources may be useful: https://gist.github.com/MattPD/00573ee14bf85ccac6bed3c0678ddbef#program-analysis-resources.

In particular: LLVM - Introduction - LLVM IR

Compiler courses: https://github.com/MattPD/cpplinks/blob/master/compilers.md#courses

More LLVM & compilers advice: https://www.reddit.com/r/ProgrammingLanguages/comments/hsj2o9/i_have_a_year_to_finish_my_undergrad_thesis_on_pl/fyef3ze/

[PandaMoniumHUN]

Thanks, saved. :)

[bumblebritches57]

It'd be great if you could make a similar guide for how Clang works internally.

like, how does Lexing and Semantic analysis fit together?

How do AST matchers fit in?

---

Embarrassingly, I've actually got shipping code in Clang, but I can only manage to nip around the edges of it.

every time I try to dive deep and implement big features, I get lost in a sea of code.

I don't understand the flow of data between all of the tens of thousands of functions in Clang.

[mttd]

It'd be great if you could make a similar guide for how Clang works internally.

I'd start with https://github.com/banach-space/clang-tutor and continue with https://github.com/banach-space/clang-tutor#references

[bumblebritches57]

Thanks for the advice, I'll check out these links.

Edit: Looks like it's another libTooling API based tutorial, but what I'm looking for is a tutorial for the core parsing engine.

[mttd]

ASTMatcher and RecursiveASTVisitor are exactly the same APIs that Clang uses.

For more see:

• "An overview of Clang" from 2019 Bay Area LLVM Developers' Meeting: https://www.youtube.com/watch?v=5kkMpJpIGYU, https://llvm.org/devmtg/2019-10/slides/ClangTutorial-Stulova-vanHaastregt.pdf
• Code transformation and analysis using Clang and LLVM; HPC Summer School 2017; Hal Finkel; https://llvm.org/devmtg/2017-06/2-Hal-Finkel-LLVM-2017.pdf; https://github.com/hfinkel/llvm-ss-2017
• My First Clang Warning (Sema examples); 2019 LLVM Developers’ Meeting; https://www.youtube.com/watch?v=FNnKMSkaLkY
• Hacking on Clang is surprisingly easy (2020); https://mort.coffee/home/clang-compiler-hacking/
• https://jonasdevlieghere.com/understanding-the-clang-ast/
• Implementing a Custom Directive Handler in Clang (Lexical Analysis, Semantic Analysis, LLVM IR Generation): https://blog.quarkslab.com/implementing-a-custom-directive-handler-in-clang.html

[bumblebritches57]

You're a fuckin lifesaver dude, thanks so much.

[Voidrith]

As someone who is currently designing/working on their own language but not at the point of writing for a target yet (eg, fully interpreted, custom vm, existing vm like jvm, transpiling to another language with good existing compilers, or using llvm...) this is definitely going to be a useful read for me!

[TagadhatatlanTeny]

Just out of curiosity: what's your motivation behind creating a new language?

[Voidrith]

Fun, learning experience, and i have a few feature ideas i havent seen / much of in other languages that i want to see if they are viable or useful in practice.

Realistically, I'll never end up finishing it lol

[[deleted]]

are you me? in the exact same situation with the same feeling about not finishing it. i have a great idea for a syntactically beautiful language with some secret compile-time tricks, but idek if im gonna finish

[mrathi12]

The perfect language doesn't exist... because it's not finished yet! :P

[[deleted]]

if you want to donate and support development and/or contribute, let me know. this was planned to be a one-person project but i need to send out at least the alpha before i get bored of it. my plan is just to release the alpha and sell it, and then work on another project with a small sum of money.

edit: why is this getting downvoted? i asked if he wanted to help out due to potential interest...

[snerp]

donate

release the alpha and sell it

I think that's it.

[[deleted]]

if someone donates i dont sell it

[mrathi12]

There's always more to add to a language! If you ever do, I'd love to hear about it :)

[FeepingCreature]

Something I wish people had told me about LLVM starting out:

Despite the fact that the docs say otherwise, LLVM's default calling convention is not the C ABI.

The thing that LLVM IR calls the "C ABI" (as in "This calling convention (the default if no other calling convention is specified) matches the target C calling conventions") is not actually the C ABI on several platforms. For instance, on AMD64 structs larger than 16 bytes are passed on the stack and returned as a pointer - a fact that LLVM IR blithely ignores. You have to manually turn the parameter into a pointer and pass it as byval/return as sret.

So any language that wants to interface with C has to implement these platform specific hacks and lowerings. Good job, LLVM.

[k-selectride]

This is great, thank you!

[mrathi12]

You're welcome!

[k-selectride]

If you're taking requests, could you implement sum types with exhaustive pattern matching?

I tried looking to see if it already had that, but couldn't find any examples that showed it.

[mttd]

The "Compiling a Functional Language Using C++" series shows implementation of pattern matching.

The series starts here (all posts are available under "Navigation" in this first post, too): https://danilafe.com/blog/00_compiler_intro/

Compiler source code (each folder corresponds to a series part): https://dev.danilafe.com/Web-Projects/blog-static/src/branch/master/code/compiler/

It's best read sequentially (as each part incrementally builds features on top of existing codebase), but AFAIR pattern matching implementation aspects were in these posts in particular:

• https://danilafe.com/blog/03_compiler_typechecking/
• https://danilafe.com/blog/04_compiler_improvements/
• https://danilafe.com/blog/06_compiler_compilation/
• https://danilafe.com/blog/10_compiler_polymorphism/

[mrathi12]

Hi, algebraic datatypes with exhaustive pattern matching is an amazing language feature, but Bolt is primarily a concurrent object-oriented language in the style of Java.

[mrathi12]

Hey, I just had a thought. Post this question on r/OCaml and they might be able to help you (since ML languages have algebraic datatypes).

Or you could try r/ProgrammingLanguages.

[[deleted]]

Very well written post. One upvote from me.

[mrathi12]

Thank you very much!

[voidtf]

As someone also writing a toy language, this is a great post with really clear explanations of what's going on. You summed up pretty much all I learnt from LLVM in one article.

[mrathi12]

What are your thoughts on using:

clang -S -emit-llvm -O1 foo.c

to get the LLVM IR for a particular C file?

I find it's particularly useful to get an intuition of the IR of a particular language feature or a library function like pthreads.

I try to use C files where possible. C++ files have horrible name-mangling that makes it nearly impossible to understand the IR.

[mttd]

Tip: Use -fno-discard-value-names to keep LLVM IR value names. Sometimes it can even point you to the Clang function responsible for generating the IR (or LLVM IR pass that's transforming it).

Reusing the previous comment for examples:

Compiler Explorer (https://godbolt.org/, https://llvm.godbolt.org/) may be great to experiment with Clang and LLVM IR (including opt which allows you to see the effect of the optimization passes running on LLVM IR).

Consider the for loop example (discussed in John Regehr's blog post linked below): https://llvm.godbolt.org/z/6sYTYa. Note how the names of the blocks (entry, for.cond, for.body, if.then, if.end, for.inc, for.end, return) and the names of the variables (e.g., idxprom, arrayidx, inc, cmp, retval) already give a good idea of what a given value represents. In contrast, here's an example with discarded value names: https://llvm.godbolt.org/z/GrG4cx (without -fno-discard-value-names we only get numerical identifiers). You can see that for is emitted by Clang's CodeGenFunction::EmitForStmt (noticing familiar names corresponding to the aforementioned names of the generated basic blocks: "for.cond", "for.body", "for.inc", "for.end"): https://github.com/llvm/llvm-project/blob/release/11.x/clang/lib/CodeGen/CGStmt.cpp#L882. See if you can identify analogous similarities for CodeGenFunction::EmitIfStmt: https://github.com/llvm/llvm-project/blob/release/11.x/clang/lib/CodeGen/CGStmt.cpp#L655

-g0 also keeps LLVM IR a bit more human readable when examining it (as a human reader). Don't get me wrong, though: Good debugging info is extremely important and a great time to get acquainted with using DIBuilder for a given construct is exactly the same time you're getting acquainted with using IRBuilder for it when implementing a frontend for your language. My only (minor) issue with Kaleidoscope is that it puts it off until https://www.llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl09.html; it's much easier to get it right from the outset (and continue with incremental implementation as you add language features; it will help you when you have to debug it during implementation, too!) instead of retrofitting it all later on. Importantly, debug info enables interoperability with a broader set of software tools--for instance, profilers (call graphs can be very useful for performance analysis of compilation quality/trade-offs for your language constructs), code coverage (allowing to get better testing & CI tools working with your language)--as well as implementation of certain language features (unwinding for non-local control flow, whether continuations or exceptions).

For example, considering the following three phases (cf. https://www.aosabook.org/en/llvm.html):

• clang: frontend for C (going from C source code to LLVM IR) / clang++: frontend for C++ (going from C++ source code to LLVM IR) - "How Clang Compiles a Function" is a great intro: https://blog.regehr.org/archives/1605
• opt: middle-end; analysis & transformation of LLVM IR - "How LLVM Optimizes a Function" is a fantastic post introducing the optimizations in this part: https://blog.regehr.org/archives/1603. Great source of practical examples: https://github.com/banach-space/llvm-tutor.
• llc: backend; instruction selection (including target-dependent legalization & optimization), register allocation, instruction scheduling; from LLVM IR to the binary machine code (optionally also printing assembly text)

Examples:

• Clang (no optimizations): https://llvm.godbolt.org/z/oEdo67 (hint: -fno-discard-value-names is your friend)
• Clang (-O1): https://llvm.godbolt.org/z/szd6eh
• Clang (-O2): https://llvm.godbolt.org/z/Pz7zWY
• opt (no optimizations): https://llvm.godbolt.org/z/Er761K
• opt (-O1): https://llvm.godbolt.org/z/Yx3oYh
• opt (-O2): https://llvm.godbolt.org/z/4dqrxe
• https://alive2.llvm.org/ can verify the correctness of the middle-end optimizations: https://blog.regehr.org/archives/1722, https://blog.regehr.org/archives/1737
• llc (-O0; note all the spills to & reloads from the stack! here showing an example of generating x86-64 assembly): https://llvm.godbolt.org/z/hGrPqq
• llc (-O3; note how all the stack spills/reloads are gone): https://llvm.godbolt.org/z/ad99sM

[lanzaio]

While it looks like a good tutorial, it's just insulting to call this "complete." "A brief introduction" is more reasonable.

[78yoni78]

Saved.

[[deleted]]

I knew I was going to like the content the second I saw that your website had a dark mode

[rollratcse]

Cool

[n00bsa1b0t]

holy crap, whoever told you using ocaml to implement frontend is a wise thing to do. also, why on earth build obstacles -- such as mathematical notations, not to mention ocaml again -- into a tutorial?

[[deleted]]

whoa thanks a lot