11 ms·
QBE vs. LLVM
- chx 6y agoThis needs a (2016) in the title. It's not evident from the text but it is from the announcement: https://www.reddit.com/r/programming/comments/4fysrk/qbe_my_homegrown_simple_compiler_backend/ https://www.reddit.com/r/programming/comments/4fysrk/qbe_my_...
- ashton314 6y agoI’m going to be building a compiler over Christmas break, and I was thinking of targeting the LLVM toolset. This will be my second compiler; first one emitted x86 directly. Should I consider switching to QBE? I’m more focused on compiler passes that I want to write; register allocation, etc. is not my thing. I’m going to be working with CPS-conversion ans stuff like that. Does anyone have any good tutorials for using either system?
- siraben 6y agoSounds like you want to compile a functional language. The best tutorial (in terms of being self-contained and being understandable in entirety) I've seen to compile FP to C is[0], I'd imagine that retargeting to LLVM wouldn't be that difficult either. [0] https://github.com/jozefg/pcf https://github.com/jozefg/pcf
- arcticbull 6y agoThat’s a great idea honestly. Even Rust would make a good compile target, the strong typing could help debug the compiler as you go. Although LLVM assembly is a good choice too!
- worldsayshi 6y agoAre there any big downsides to compiling to C instead of LLVM? I would assume that it would be less performant but it feels like a shallow preconception.
- arc-in-space 6y agoIt's somewhat more constricting, certain types of compiler magic are hard to reproduce in plain C. For instance, dealing with things that need to be stack-aware, such as a GC or tail recursion, takes epic hacks like the Boehm GC or the "Cheney on the MTA" trick. You're also stuck with the C calling convention. Plus, while generating C is simple, you're entirely on your own. With LLVM IR, you benefit from its infrastructure, the optimization passes and other LLVM-based tools, so you don't need to reinvent the wheel as much. In the end, you'll need some kind of IR anyway, and LLVM is a good place to start.
- jcranmer 6y ago> Are there any big downsides to compiling to C instead of LLVM? Well, for starters, you have to import all of C's undefined behavior, so it would be basically impossible to implement, e.g., 2's complement signed integer arithmetic.
- badsectoracula 6y agoStrictly speaking it isn't impossible, just much slower since you'd have to implement on software what the hardware does. In practice though pretty much every compiler that uses that as an optimization has a flag to disable it and chances are you'll be needing to use other system and/or compiler specific stuff anyway.
- ashton314 6y agoThis looks great! I’m taking a different approach than this compiler, but this looks like a good resource. Thanks!
- latenightcoding 6y agocranelift is a better alternative.
- Rochus 6y agowhy?
- rurban 6y agoBecause llvm is unusable for a dynamic language VM. The compile-times are too slow, it's way too big. cranelift is also big, but has sensible staged optimizers. I.e. it doesn't behave like java or llvm.
- freemint 6y agoThis depends on your usecase i guess. For long running numerical code (Julia) LLVM is fine but needs some work by highly skilled individuals to make it feel like a interpreted REPL when importing big code bases.
- cesaref 6y agoWe've been JITing using LLVM for a number of years without an obvious problem. It obviously depends on the size of the code you are wanting to JIT, but the OP was discussing a toy language as a side project, and LLVM is certainly perfect for that use case.
- Rochus 6y ago> cranelift is also big, but has sensible staged optimizers LLVM gives you the freedom to decide what optimizers to use. But it's true it is too big for many applications, even if there are build options for different sizes.
- mhh__ 6y agoLLVM is much better documented than any other compiler system, so I would just KISS and use it. LLVM is a beast, though, but to get started I'd want to focus on the my side of the compiler first (the sema is where the pain is imo) Remember that there's no reason why you can't have an IR in between your language and the backend. If your language fits, (based on the CPS it probably won't but still) you can use a subset of it as a representation of that IR and use lowering to rewrite expensive constructs into smaller ones, greatly reducing the surface area you have to work with.
- hollerith 6y agoKISS is an acronym for 'keep it simple', which is an surprising choice of word when advocating for the much more complicated choice.
- mhh__ 6y agoWould you rather use a project you can at very least copy and paste from another codebase with, or - for what is basically the easy bit of the compiler - fiddle around with getting a (possibly more suitable backend in the long run, but you don't know that yet) much less mature project working.
- ahaferburg 6y agoBetter documented doesn't mean the documentation is perfect. My experience two years ago was: You're going to have questions, and it's going to be difficult to find answers. LLVM is not KISS. Very, very far from it.
- jart 6y agoTry https://github.com/rui314/chibicc https://github.com/rui314/chibicc
- MaxBarraclough 6y agoWhat was your first compiler?
- ashton314 6y agoThis little lisp to x86: https://github.com/ashton314/lambda-x86 https://github.com/ashton314/lambda-x86 New one: https://github.com/ashton314/christmas-compiler https://github.com/ashton314/christmas-compiler
- jules 6y agoConsider generating WASM.
- ahaferburg 6y agoYou have other options. You could design your own bytecode, and write an interpreter. You could emit C, and use a C compiler. If you use LLVM, you also need to decide whether you want to link against LLVM and use the C++ API. Or you can use bindings for another language. Or you can emit IR as plain text, then feed that into the LLVM compiler. I have done the latter, and would advise against it. The IR is powerful, but quite involved. The documentation is sometimes lacking. It's an interesting project, but you probably won't get far. Linking against LLVM means you have to use their C++ interface, and every time you rebuild your compiler, it's going to be slow, with all the templates they use. Your compiler will be a large executable (clang and zig are about 90 MB), and you'd have to rebuild that every time you change your compiler. I would hate having to do that in my spare time, which is why I went the other route. LLVM is very powerful. There's all these optimizations you get, and debug info. But it's not free. The integration is going to be hard and you'll have to spend quite some time on it. The next time I would start a language project I would build an interpreter in a dynamic language, and possibly even use a parser generator. https://craftinginterpreters.com/ https://craftinginterpreters.com/ has a nice path laid out. Focus on what you actually want to do. Once you get somewhere, once you actually like your language, once you actually start a project in your own language, and have an actual need for more, you can write another compiler with more bells and whistles.
- siraben 6y agoI wanted to write an LLVM backend for various instruction sets (e.g. Z80, R216[0]), since those would deal with the problems of optimization passes and register allocation for me, but the LLVM tutorial[1] makes it look so goddamn hard. Does anyone know of a tutorial or of a declarative way to write such backends for either QBE or LLVM? The QBE git repository[2] has a few backends but also looks similarly involved. Comparatively, writing frontends is quite easy these days and many examples of compiling to IR exist. [0] https://trigraph.net/powdertoy/R216/manual.md https://trigraph.net/powdertoy/R216/manual.md [1] https://llvm.org/docs/WritingAnLLVMBackend.html https://llvm.org/docs/WritingAnLLVMBackend.html [2] https://c9x.me/git/qbe.git/tree/amd64 https://c9x.me/git/qbe.git/tree/amd64
- mhh__ 6y agoWriting compiler backend in a declarative manner is something I've been toying with for a while now, and I don't think it's realistically possible with current technology. Backends are hard, unfortunately. However, since you are targeting the Z80, you might be able to just take the IR and transform it yourself? I haven't touched an LLVM backend for a while, so I don't know what the process is atm, but if you imagine that a lot of a modern compiler is dealing with instruction scheduling and the like , which the Z80 doesn't really have a need for. LLVM is very good for the industry, but it is a little over-engineered(?). Maybe that's a bit harsh, but the difficulty is definitely thrown at you earlier than hacking on most compilers.
- beagle3 6y agoIt is not purely declarative, but Fraser & Hanson's lcc comes close while still delivering good optimization -- and has a book describing it (IIRC it was written literate-programming style). It's been 20 years or more, I played with an older version that required an Icon interpreter as part of the build chain, and I think they had a later one that did away with that requirement. The code generator is basically built from a declarative description of tree matching/rwriting templates with a cost model, and the compiler will find the optimal cost match.
- vmchale 6y ago
- pjmlp 6y agoAlso to note, LLVM isn't the first compiler toolchain of its kind. Notable mentions, IBM's research project on PL.8 while developing their first RISC designs. https://rsim.cs.uiuc.edu/arch/qual_papers/compilers/auslander82.pdf https://rsim.cs.uiuc.edu/arch/qual_papers/compilers/auslande... https://pdfs.semanticscholar.org/3288/fc042cd474f0ec93d67753565d0cc83ac575.pdf https://pdfs.semanticscholar.org/3288/fc042cd474f0ec93d67753... https://rishiheerasing.net/modules/hca2102/paper/cocke.pdf https://rishiheerasing.net/modules/hca2102/paper/cocke.pdf The Amsterdam Compiler Toolkit, http://tack.sourceforge.net/ http://tack.sourceforge.net/ https://github.com/davidgiven/ack https://github.com/davidgiven/ack https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.4591&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12... The more the merrier.
- phendrenad2 6y agoInteresting. Programmers today do tend to think that LLVM is a revolutionary miracle, and border on worshipping it's creator.
- mhh__ 6y agoLLVM does seem to be explicitly designed from the start to be "industry"-worthy rather than just academic research, though. It was actually offered to GNU years ago but (if I read the thread correctly) rms didn't get the email because of the unique way he does email. It's a shame it's not under the GPL, you can already see a sign of the future (present?) in apple not upstreaming their backends.
- Mutjake 6y agoIf it was licensed under GPL, my bet is that Apple would not have adopted it at all.
- mhh__ 6y agoThat's entirely possible, but does it hurt their bottom line? They switched from GCC, because LLVM was available (to grow and eventually use). Their aversion to the GPL seems mostly cultural, which is interesting given that we skewer microsoft for their sins along those lines 20 years ago now.
- tjansen 6y agoI am also working on a compiler and need to decide on a backend soon. I currently plan to use C (clang) as IL in the first iteration, with the option to upgrade to LLVM IL later. I wonder whether there is any easier alternative. I definitely need to start with a framework that takes text input, because everything else would be hard to integrate with the TypeScript-based interpreter of my language. And it needs to work with a runtime written in C. QBE looks nicer than LLVM's IL, but I wonder whether it would cause more trouble in the end.
- lattay 6y agoSince this version of your language will never be used by thousands of users (if you ever hit sucess you’ll want to rewrite your compiler anyway) QBE is a lot simpler to use than LLVM. The main limitation is the limited set of target architecture, and probably the dlow development. In effect Linux AMD64 and ARM64 are the only well supported architectures. Also you may be able to compile to windows using mingw assembler.
- winter_blue 6y agoWhat I’d like something similar to QBE, but that actually compiles/targets LLVM. So, essentially, a beginner-friendly intermediate layer on top of LLVM.
- Rochus 6y agoYou could transpile to C and feed that to LLVM/Clang or e.g. to TCC (https://github.com/TinyCC/tinycc https://github.com/TinyCC/tinycc).
- rurban 6y agoSure, but the idea is to avoid C and compile to a simplier IR, like qbe. And then compile that to native code in 1/10 of the time and memory LLVM or GCC do.
- Rochus 6y agoThe question was "a beginner-friendly intermediate layer on top of LLVM". If you use TCC instead of Clang or GCC compilation speed is very fast.
- MaxBarraclough 6y agoIt's for ahead-of-time compilation only, right? I gather it always outputs assembly files.
- kohlerm 6y agoI only hope that by we don't get a lot of new languages, which are not only not production ready but also poorly designed. ;)
- dTal 6y agoWhat's the harm? Just don't use them.
- sligor 6y ago> "Implementing a complete C ABI (with struct arguments and returns) is incredibly tricky, and not really a lot of fun." This sounds like it should be wrapped as an helper library on top of LLVM and embedded inside LLVM. Why it is not the case ?
- sanxiyn 6y ago> Implementing a complete C ABI (with struct arguments and returns) is incredibly tricky, and not really a lot of fun. This is so true. Rust does it here: https://github.com/rust-lang/rust/tree/master/compiler/rustc_target/src/abi/call https://github.com/rust-lang/rust/tree/master/compiler/rustc... and it's a lot of code for no good reasons.
- randomNumber7 6y ago+1 I plan to write a toy compiler and considered llvm. This one thing is the reason I will never use llvm for a hobby project. Even for non-toy compilers, I think it's a waste of human resources that every frontend has to implement the C ABI.
- burlesona 6y agoWhy does LLVM work that way?
- parkovski 6y agoThis is surprising for me, I thought LLVM abstracted away platform ABIs.
- billconan 6y agoIs it a good idea to use BNF for documentation? This form of document doesn't seem to be very useful for people who want to use the language. Both WASM and javascript docs do this, and it is also the same here https://c9x.me/compile/doc/il.html https://c9x.me/compile/doc/il.html I think LLVM's IR document is not easy to read, this one is not better. I don't want to reimplement a compiler for the IR language, I want to know how to use it, how to generate code using it. I need to see examples, i.e. how to implement threading, coroutine, weakly typed variables, reflection ... not the BNF.
- piinbinary 6y agoI wish something like this existed for garbage-collected languages. The closest thing I know of is the JVM (and other similar VMs), but I'm hoping for ahead-of-time compilation. The key difficulty in adding garbage collection to code emitted with tools like this is being able to accurately tell what the root set is. (I know LLVM has support for this in theory, but I have found nothing that tells how to actually use it)
- jeremyjh 6y agoThere are LLVM backed languages that provide garbage collection; Julia and Crystal are the first two that come to mind. Haskell also has an LLVM back-end.
- biryani_chicken 6y agoSomething like the CIL[0]? I know there was a python and a ruby implementation on top of it. [0] https://en.wikipedia.org/wiki/Common_Intermediate_Language https://en.wikipedia.org/wiki/Common_Intermediate_Language
- csharptwdec19 6y agoThat's about viable nowadays. Elaborating: Until recently, your best option for running CIL in an AOT type environment would be Mono AOT, which has it's own limitations. Nowadays, however, we do have CoreRT in a state that lets you do AOT, still with limitations around things like reflection. But, it's fairly doable nowadays, I would think.
- erlend_sh 6y agoThe Mu Micro Virtual Machine might interest you: https://news.ycombinator.com/item?id=25278568 https://news.ycombinator.com/item?id=25278568
- yarg 6y agoThere's a version of the JDK that provides AOT.
- yarg 6y ago
- fefe23 6y agoI would love to have a way to bootstrap LLVM. This looks promising but I'm guessing a C++ frontend is much more challenging than writing this backend. gcc used to be the missing link, but they switched to C++ and now you can't bootstrap it with something like tcc.
- MayeulC 6y agoCan't you still bootstrap LLVM from GCC, and GCC from the last C version, and that from tcc? GNU GUIX works on the boostraping issue, they strive to reduce the seed size as much as possible: https://guix.gnu.org/blog/tags/bootstrapping/ https://guix.gnu.org/blog/tags/bootstrapping/
- prirun 6y agohttps://github.com/vnmakarov/mir https://github.com/vnmakarov/mir
- tln 6y agoAnother similar project is https://github.com/vnmakarov/mir https://github.com/vnmakarov/mir
- waynecochran 6y agoDoesn't allowing non-SSA forms like %v =w add %v, 1. defeat the purpose of using SSA in the first place? If this form is allowed, then I can not rely on `%v` having an immutable value which is much of the reason why we use SSA in the first place.
- elcritch 6y agoNot if the framework can readily create v0, v1 from the temporaries. It'll still end up as a full SSA according to what they describe.
- donpdonp 6y agoQBE https://c9x.me/compile/ https://c9x.me/compile/ "QBE aims to be a pure C embeddable backend that provides 70% of the performance of advanced compilers in 10% of the code"
- AndyKelley 6y agoOne important thing to note is that QBE emits text-based assembly and relies on a system-installed assembler. Meanwhile LLVM produces object files.
- mlindner 6y ago> QBE is extremely hackable. and > it is programmed in non-fancy C99 without any dependencies. These are contradictions. C99 is not a "very hackable" language. If the compiler isn't designed to make fast binaries then they should have written it in a higher level language that has less foot guns.