6 ms·
We are a bit overwhelmed at the moment, but sure, this is something we'd eventually give an llvm devmtg talk about or something. Broadly speaking, there are th
by chrislattner 3y ago
We are a bit overwhelmed at the moment, but sure, this is something we'd eventually give an llvm devmtg talk about or something. Broadly speaking, there are three kinds of things that matter:
1) Type system. If you go with a constraint based hindly milner (https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_sy...) type system and then add things like overloading etc, you quickly get into exponential behavior. Swift has been fighting this for years now to tamp down the worst cases. This isn't good; don't do that.
2) Mid-level compilation model. "Zero cost abstraction" languages including C++ (but also more recent ones like Swift and Rust and now Mojo) rely in massive inlining and abstraction elimination to get "zero cost" behavior. LLVM can do inlining and simplification and all the other stuff, but it is a very low level of abstraction - generating a TON of IR and then asking LLVM to delete it for you is very slow, and shows up in the profile as "llvm is slow" because you're creating all the llvm ir nodes ("LLVM") and then asking llvm optimization passes to delete them for you. It is far better to not generate it in the first place.
3) Code generation: Reasonable codegen is O(N^2) and worse in core algorithms like register allocation and scheduling. This is unavoidable if you want high quality of results (though of course, llvm is also far from perfect). LLVM is also very old and single threaded. If you don't do anything to address these issues, you'll be bottlenecked in this phase.
These all have good solutions, but you have to architect your compiler in anticipation of them. Mojo isn't just a syntax or PL step forward, it is a massive step forward in compiler architecture.
-Chris
- zengid 3y agoChris, you are so generous for explaining this stuff, thank you. Quick question about #2 that I may not be picking up on, but how is it possible to avoid generating the "TON of IR" in the first place? (I'd live with a link to further reading if you're unable to go into details). Thanks!
- kps 3y ago[Not him of course] — My understanding is that instead of generating a ton of (LLVM) IR, you generate a little (MLIR) IR, because MLIR lets you define operations at higher levels of abstraction, suited to particular tasks. For instance, if you're doing loop optimizations, instead of crawling through a sea of compare and branch and arithmetic operations, you'd just use a higher-level ‘for’ operation¹. Only after you've done everything you can at the high level do you move down to a more concrete representation, so you hope to end up with both less LLVM IR and less work to do on it. ¹ e.g. https://mlir.llvm.org/docs/Dialects/Affine/#affinefor-mliraffineaffineforop https://mlir.llvm.org/docs/Dialects/Affine/#affinefor-mliraf...
- spopejoy 3y agoDo you see overloading as must-have?