Unfortunately, it appears to represent pointers as addresses, which means it will need significant rewriting to be able to support a CHERI system (yay, we have a Wikipedia article now). The documentation is also lacking and I’m quite nervous of any project like this that doesn’t start with a specification of their IR.
One of the issues with LLVM is that optimisations are sound or not with respect to the IR semantics, but the IR is under specified. If I were doing this today, I’d start with an executable formal semantics of the IR that could be used in conjunction with formal models of ISAs and source languages to prove abstraction, used to prove correctness of optimisations, and used as a gold model to test the implementation.
It doesn’t really represent pointers as addresses? I have a limited understanding of CHERI so please bare with me, what things would be necessary to make CHERI possible within the semantics of my IR? The main operations you can apply onto pointers are offsetting them by some number of bytes and bitcasting them in and out of integers (this need not return an address, just the raw bits of an address). I suppose pointer diff should have an explicit operation but other than that… is there anything else necessary for the core of the IR which needs to be redone?
From what I saw in the code (there isn’t any documentation that I could find for the type system), pointers are represented as 64-bit integers in a tagged union with a type identifier called address. In LLVM, they’re abstract. You rarely want to represent the, as concrete addresses anyway because they will have relocations and so on applied. You want to be able to track provenance.
In CHERI, you can:
Adjust the address, which looks a lot like the Rust strict provenance mode: get address, do some arithmetic, put address back, though we treat adding to the address as a special case (both in the hardware and IR) because it’s so common.
Reduce the bounds.
Reduce permissions.
Seal with another capability and subsequently unseal.
All of these are easy to model as pure functions on a pointer when the pointer is an opaque value, as are things like applying relocations (which don’t happen until link time and require the compiler to model the pointer as abstract).
My pointers aren’t just 64bit integers, they do technically have provenance because it’s useful in a variety of cases. They are for the purposes of something like CHERI “opaque”, you could bitcast into an integer but that’ll give you back whatever tagged goop the CHERI pointers had. I tried to maintain room for that for later which seems like it’s the case.
Thanks. It would really help understanding if you could document this. I doubt I’ll ever want to use a compiler back end written in C, but at least with some IR docs I’d be able to make more informed comparisons than trying to find things in barely commented headers.
I personally find attempts to create new SSA-based backends to be a little misguided, especially if you’re not approaching it from a theoretically strong and novel research based approach. LLVM is slow and complicated almost as a necessity, and if you want a faster backend you have to cull a large amount of optimizations. You might as well use something like Cranelift at that point. Of course, these things are not binary and a I wish the authors the best of luck in creating something cool and useful.
A small nit-pick from the blog:
Other important caveats are that LLVM doesn’t consider IR generation to be backend here
I think you’ll find this is the distinction between a compiler frontend and backend. The frontend produces the IR, which is optimized and turned into machine code (or assembly, object files, whatever) by the backend
Assuming it’s the same Yasser I know who’s writing an LLVM replacement, he doesn’t just have a theoretically strong approach, he has lots of input from “the guy” himself (Cliff Click, author of the Sea of Nodes paper in the 1990s, and the author of the SSA-based Hotspot Java Virtual Machine that billions of people rely on every day).
Yasser is young, and knows no limitations to his own abilities. In other words, he’s like most of us are – or were! – and while his success is not guaranteed, it’s people like him who know no limits that eventually will change the world. Hopefully for the better.
LLVM is slow and complicated almost as a necessity
No, I don’t believe this to be true. LLVM is slow and complicated mainly because it was a early learning experience for its young author. And instead of incorporating the things that were already known, and the things learned in the writing of it, it simply accepted those inefficiencies as “unavoidable” and didn’t bother to correct any of them. Inertia is a great ally, and also a horrible foe.
Assuming it’s the same Yasser I know who’s writing an LLVM replacement, he doesn’t just have a theoretically strong approach, he has lots of input from “the guy” himself (Cliff Click, author of the Sea of Nodes paper in the 1990s, and the author of the SSA-based Hotspot Java Virtual Machine that billions of people rely on every day).
Yasser is young, and knows no limitations to his own abilities. In other words, he’s like most of us are – or were! – and while his success is not guaranteed, it’s people like him who know no limits that eventually will change the world. Hopefully for the better.
That’s not really what I mean, I’m sure that Yasser is very talented. My contention is that creating a faster LLVM with comparable output is a research problem, and research problems should be approached scientifically. What is the hypothesis of this project? “A SSA backend based on sea of nodes can produce comparable output and significantly faster speeds”? This would be a significant advancement to Combining Analysis, Combining Optimizations, but as of right now there’s very little evidence to point to this being the case. I prefer smaller results that show promising signs, that can be used to build more significant results. Contrast this with the development of Copy and Patch by Haoran Xu, which is being developed into a remake of lua jit with significantly interesting results. I find his approach much more rigorous and also much more narrowly scoped and therefore much more interesting to follow.
As an aside, I think that some “pop” programmers have popularized the idea that all code is bloated and slow and needs to be completely re-written, and a lot of people have taken it on themselves to re-write huge portions of the stack themselves. And I think that’s great! As a fun personal project, but not the basis of a big serious project that I need to consider using. At least, I remain pretty skeptical of them early on.
No, I don’t believe this to be true. LLVM is slow and complicated mainly because it was a early learning experience for its young author. And instead of incorporating the things that were already known, and the things learned in the writing of it, it simply accepted those inefficiencies as “unavoidable” and didn’t bother to correct any of them. Inertia is a great ally, and also a horrible foe.
I find this to be a miss-characterization of the development of LLVM, Chris Lattner was 25 but he was also a PhD student, and he wasn’t the only author - Vikram Adve, his doctoral advisor was 37. Yes, it was a learning experience for Chris, because it was his PhD thesis, so it was still quite a significant advancement over the state of the art.
Also, LLVM developed inertia because it had a license that made it appealing for Apple to fund the development of. I think it will be quite hard for any new project to achieve half of the features of LLVM, and you might as well therefore attempt to modify LLVM if you have ideas on how to improve it.
My contention is that creating a faster LLVM with comparable output is a research problem, and research problems should be approached scientifically.
It’s not a research problem, it’s an engineering problem. He’s building something practical and useful to many, not exploring a novel concept and explaining it to a niche audience.
I find this to be a miss-characterization of the development of LLVM, Chris Lattner was 25 but he was also a PhD student, and he wasn’t the only author - Vikram Adve, his doctoral advisor was 37.
PhD students are notoriously terrible programmers, advisors even more so. They’re known for writing sloppy, hacky code that barely functions enough to get their thesis done. They embrace paradigms like Object-Oriented Programming which are popular among academics living in a bubble, but have been long outdated in the software engineering industry.
It’s not a research problem, it’s an engineering problem. He’s building something practical and useful to many, not exploring a novel concept and explaining it to a niche audience.
Writing an SSA backend that is faster and produces comparable output to LLVM is absolutely a research problem, and research does not have to be “exploring a novel concept and explaining it to a niche audience”.
Additionally, I will argue that all sufficiently sized engineering problems are research problems. You can’t just engineer your way through sufficiently large problems without research.
Again, I hope it does become practical and useful to many. But I think the foundations of the project make it unlikely to succeed in this front. I hope I’m wrong.
PhD students are notoriously terrible programmers, advisors even more so. They’re known for writing sloppy, hacky code that barely functions enough to get their thesis done. They embrace paradigms like Object-Oriented Programming which are popular among academics living in a bubble, but have been long outdated in the software engineering industry.
To me this feels just like something people say with no real evidence to back it up or disprove it. At best the evidence is anecdotal. I’ve met plenty of Drs of CS who write pretty good code, so I’m not sure why being a PhD would make you a poor coder besides other external factors like the stress of meeting the deadline for your thesis.
I’m not really trying to say anything about Chris Lattner, I’m just responding to your implied premise that being a PhD student means being a better programmer:
Chris Lattner was 25 but he was also a PhD student
This is the initial claim being made and therefore the one that has the burden of proof. My comment only serves to point out that this claim is not a valid premise because it is not widely accepted as fact.
It feels like saying “well Linus was 22 when he created Linux, and 22 year olds are notoriously terrible programmers”. Yes, there’s plenty to criticize from today’s POV, but that also just means the field has progressed, which is good.
Sure, the average Ph.D. student or their advisor is not a good programmer, but we’re talking about the people who created LLVM
Which Julia, Rust, Zig, Swift, and Odin all built on … It enabled a lot of open source to exist, which wouldn’t otherwise exist
If they were such horrible programmers, then surely it wouldn’t be a big deal to just ignore them and build something better. Why even build on top of something from these programmers?
Yet it will probably take a decade to build a good alternative (considering the targets, code gen speed, and runtime speed). And that will no doubt be done with lots of knowledge created by the LLVM project in the first place
LLVM also encouraged GCC to be more modular. AFAIK there were virtually no projects built on top of GCC – everything significant had to be maintained upstream in GCC because there were no public APIs
I’m not really trying to say anything about Chris Lattner, I’m just responding to [the] implied premise that being a PhD student means being a better programmer
We probably agree on a lot more of this than we disagree on. Any compiler back-end is a significant project of multiple man-years to do a half decent basic job of, let alone something that could replace LLVM. LLVM may not be optimal, but it has one significant advantage over most projects: It is available for use. That said, LLVM does have design flaws that have been pointed out over the years by people who have successfully built back-ends (i.e. not me – I’ve only done compiler front ends), and I have to assume that at least some portion of those criticisms are valid. Even Chris has admitted to various things that he wished he had done differently, so this isn’t some sort of blame game. I’m sure when Chris was building LLVM, a number of gatekeeping people were rolling their eyes at the audacity, but he pulled it off – criticisms notwithstanding. And I’m just trying avoid becoming one of those gatekeepers.
I agree with you on all the things stated here. I don’t intend to be unduly harsh or dismissive, and I do by no means wish to gatekeep the effort of anyone to do cool stuff.
LLVM is slow and complicated almost as a necessity
https://home.cit.tum.de/~engelke/pubs/2403-cgo.pdf notes a lot of bottlenecks that are architectural rather than algorithmic. The ir encoding is memory-heavy, is expensive to build, and requires a lot of pointer-chasing. Extensibility at every stage is implemented by virtual function calls per ir node, which are expensive even if you don’t override them. The linker first builds a complete elf object and then immediately parses it again. Etc.
A new codebase that does the exact same optimizations but is architected for current hardware could potentially be a lot faster. Memory density and access patterns matter a lot more now than they did 20 years ago. Same for multi-threading.
Is there something particular about SSA, that you find misguided, or do you mean that not being novel would have a hard time competing with an already developed, industry-standard implementation?
What other alternatives are there? I know that GraalVM uses a graph-based IR, for example, which I found very interesting. Do you (or someone else) have perhaps some option on how these compare?
Nothing about SSA is misguided. You hit it on the head - without being novel or strongly researched based into LLVMs deficiencies (a good example of what this would look like is pointed to in another comment), you’re unlikely to compete with LLVM
This would have benefitted from a date on the post, because that minivm link is already dead - the repo exists with the main branch being 7 months old.
Other than that I have no real opinion, I like LLVM but don’t claim to be anything but an occsional user.
As a test case i wrote a C compiler
I liked that sentence though, just casually wrote a C compiler, as one does.
QBE could be promising if it gets a couple more full-time maintainers but as of now is alpha-quality software. It doesn’t support 32-bit targets (and would require some architectural-level changes to do so), does essentially no optimizations, and has one of the more incomprehensible C codebases I’ve seen in open-source.
I notice a severe lack of comments on fields that could use them.
Some of the coding style also strikes me as not very readable, such as the identifier spelling convention being wordword instead of wordWord or word_word, and function vars all being declared up front (and without comments). I have little experience with pure C, so not sure how much of this is C convention (or compliance with an old C standard).
most of the fields are self-explanatory to me from their names. a few (like link, dlink, nlive) are not (and i don’t think it would be bad to comment them) but it seems likely their function is probably somewhat localised and fairly clear in context. i don’t think i would have difficulty finding out what those fields are for if i just read the code a bit, and so they are probably all obvious to anyone who is doing any meaningful amount of work on the codebase
i’m not saying there shouldn’t be comments, but i don’t think it’s that bad that they’re not there. a compiler is usually a lot of special-purpose code and data structures (optimisation and analysis passes) organised around a single general-purpose data structure (being the core ir). it doesn’t seem unreasonable to keep the entirety of the latter in your head
i am not commenting at all on whether i think this is a good design for a compiler, whether c is a good language for writing compilers in, or whether the rest of the code is readable
Unfortunately, it appears to represent pointers as addresses, which means it will need significant rewriting to be able to support a CHERI system (yay, we have a Wikipedia article now). The documentation is also lacking and I’m quite nervous of any project like this that doesn’t start with a specification of their IR.
One of the issues with LLVM is that optimisations are sound or not with respect to the IR semantics, but the IR is under specified. If I were doing this today, I’d start with an executable formal semantics of the IR that could be used in conjunction with formal models of ISAs and source languages to prove abstraction, used to prove correctness of optimisations, and used as a gold model to test the implementation.
Yeah! Would be so great to have a sound, well specified compiler backend, even if it is not as fancy as LLVM.
It doesn’t really represent pointers as addresses? I have a limited understanding of CHERI so please bare with me, what things would be necessary to make CHERI possible within the semantics of my IR? The main operations you can apply onto pointers are offsetting them by some number of bytes and bitcasting them in and out of integers (this need not return an address, just the raw bits of an address). I suppose pointer diff should have an explicit operation but other than that… is there anything else necessary for the core of the IR which needs to be redone?
From what I saw in the code (there isn’t any documentation that I could find for the type system), pointers are represented as 64-bit integers in a tagged union with a type identifier called address. In LLVM, they’re abstract. You rarely want to represent the, as concrete addresses anyway because they will have relocations and so on applied. You want to be able to track provenance.
In CHERI, you can:
All of these are easy to model as pure functions on a pointer when the pointer is an opaque value, as are things like applying relocations (which don’t happen until link time and require the compiler to model the pointer as abstract).
My pointers aren’t just 64bit integers, they do technically have provenance because it’s useful in a variety of cases. They are for the purposes of something like CHERI “opaque”, you could bitcast into an integer but that’ll give you back whatever tagged goop the CHERI pointers had. I tried to maintain room for that for later which seems like it’s the case.
Thanks. It would really help understanding if you could document this. I doubt I’ll ever want to use a compiler back end written in C, but at least with some IR docs I’d be able to make more informed comparisons than trying to find things in barely commented headers.
I personally find attempts to create new SSA-based backends to be a little misguided, especially if you’re not approaching it from a theoretically strong and novel research based approach. LLVM is slow and complicated almost as a necessity, and if you want a faster backend you have to cull a large amount of optimizations. You might as well use something like Cranelift at that point. Of course, these things are not binary and a I wish the authors the best of luck in creating something cool and useful.
A small nit-pick from the blog:
I think you’ll find this is the distinction between a compiler frontend and backend. The frontend produces the IR, which is optimized and turned into machine code (or assembly, object files, whatever) by the backend
Assuming it’s the same Yasser I know who’s writing an LLVM replacement, he doesn’t just have a theoretically strong approach, he has lots of input from “the guy” himself (Cliff Click, author of the Sea of Nodes paper in the 1990s, and the author of the SSA-based Hotspot Java Virtual Machine that billions of people rely on every day).
Yasser is young, and knows no limitations to his own abilities. In other words, he’s like most of us are – or were! – and while his success is not guaranteed, it’s people like him who know no limits that eventually will change the world. Hopefully for the better.
No, I don’t believe this to be true. LLVM is slow and complicated mainly because it was a early learning experience for its young author. And instead of incorporating the things that were already known, and the things learned in the writing of it, it simply accepted those inefficiencies as “unavoidable” and didn’t bother to correct any of them. Inertia is a great ally, and also a horrible foe.
That’s not really what I mean, I’m sure that Yasser is very talented. My contention is that creating a faster LLVM with comparable output is a research problem, and research problems should be approached scientifically. What is the hypothesis of this project? “A SSA backend based on sea of nodes can produce comparable output and significantly faster speeds”? This would be a significant advancement to Combining Analysis, Combining Optimizations, but as of right now there’s very little evidence to point to this being the case. I prefer smaller results that show promising signs, that can be used to build more significant results. Contrast this with the development of Copy and Patch by Haoran Xu, which is being developed into a remake of lua jit with significantly interesting results. I find his approach much more rigorous and also much more narrowly scoped and therefore much more interesting to follow.
As an aside, I think that some “pop” programmers have popularized the idea that all code is bloated and slow and needs to be completely re-written, and a lot of people have taken it on themselves to re-write huge portions of the stack themselves. And I think that’s great! As a fun personal project, but not the basis of a big serious project that I need to consider using. At least, I remain pretty skeptical of them early on.
I find this to be a miss-characterization of the development of LLVM, Chris Lattner was 25 but he was also a PhD student, and he wasn’t the only author - Vikram Adve, his doctoral advisor was 37. Yes, it was a learning experience for Chris, because it was his PhD thesis, so it was still quite a significant advancement over the state of the art.
Also, LLVM developed inertia because it had a license that made it appealing for Apple to fund the development of. I think it will be quite hard for any new project to achieve half of the features of LLVM, and you might as well therefore attempt to modify LLVM if you have ideas on how to improve it.
It’s not a research problem, it’s an engineering problem. He’s building something practical and useful to many, not exploring a novel concept and explaining it to a niche audience.
PhD students are notoriously terrible programmers, advisors even more so. They’re known for writing sloppy, hacky code that barely functions enough to get their thesis done. They embrace paradigms like Object-Oriented Programming which are popular among academics living in a bubble, but have been long outdated in the software engineering industry.
Writing an SSA backend that is faster and produces comparable output to LLVM is absolutely a research problem, and research does not have to be “exploring a novel concept and explaining it to a niche audience”.
Additionally, I will argue that all sufficiently sized engineering problems are research problems. You can’t just engineer your way through sufficiently large problems without research.
Again, I hope it does become practical and useful to many. But I think the foundations of the project make it unlikely to succeed in this front. I hope I’m wrong.
To me this feels just like something people say with no real evidence to back it up or disprove it. At best the evidence is anecdotal. I’ve met plenty of Drs of CS who write pretty good code, so I’m not sure why being a PhD would make you a poor coder besides other external factors like the stress of meeting the deadline for your thesis.
I’m not really trying to say anything about Chris Lattner, I’m just responding to your implied premise that being a PhD student means being a better programmer:
This is the initial claim being made and therefore the one that has the burden of proof. My comment only serves to point out that this claim is not a valid premise because it is not widely accepted as fact.
I wasn’t trying to imply that being a PhD student makes you a better programmer. I was just pushing back on the inexperience thing I guess.
This is very ungracious
It feels like saying “well Linus was 22 when he created Linux, and 22 year olds are notoriously terrible programmers”. Yes, there’s plenty to criticize from today’s POV, but that also just means the field has progressed, which is good.
Sure, the average Ph.D. student or their advisor is not a good programmer, but we’re talking about the people who created LLVM
Which Julia, Rust, Zig, Swift, and Odin all built on … It enabled a lot of open source to exist, which wouldn’t otherwise exist
If they were such horrible programmers, then surely it wouldn’t be a big deal to just ignore them and build something better. Why even build on top of something from these programmers?
Yet it will probably take a decade to build a good alternative (considering the targets, code gen speed, and runtime speed). And that will no doubt be done with lots of knowledge created by the LLVM project in the first place
LLVM also encouraged GCC to be more modular. AFAIK there were virtually no projects built on top of GCC – everything significant had to be maintained upstream in GCC because there were no public APIs
https://lobste.rs/s/jvruyj/tilde_my_llvm_alternative#c_8ardvl
We probably agree on a lot more of this than we disagree on. Any compiler back-end is a significant project of multiple man-years to do a half decent basic job of, let alone something that could replace LLVM. LLVM may not be optimal, but it has one significant advantage over most projects: It is available for use. That said, LLVM does have design flaws that have been pointed out over the years by people who have successfully built back-ends (i.e. not me – I’ve only done compiler front ends), and I have to assume that at least some portion of those criticisms are valid. Even Chris has admitted to various things that he wished he had done differently, so this isn’t some sort of blame game. I’m sure when Chris was building LLVM, a number of gatekeeping people were rolling their eyes at the audacity, but he pulled it off – criticisms notwithstanding. And I’m just trying avoid becoming one of those gatekeepers.
I agree with you on all the things stated here. I don’t intend to be unduly harsh or dismissive, and I do by no means wish to gatekeep the effort of anyone to do cool stuff.
https://home.cit.tum.de/~engelke/pubs/2403-cgo.pdf notes a lot of bottlenecks that are architectural rather than algorithmic. The ir encoding is memory-heavy, is expensive to build, and requires a lot of pointer-chasing. Extensibility at every stage is implemented by virtual function calls per ir node, which are expensive even if you don’t override them. The linker first builds a complete elf object and then immediately parses it again. Etc.
A new codebase that does the exact same optimizations but is architected for current hardware could potentially be a lot faster. Memory density and access patterns matter a lot more now than they did 20 years ago. Same for multi-threading.
Undoubtedly, I think this is an extremely good stand point for which to build a replacement (or large refactor) of LLVM. Thanks so much for the link!
Is there something particular about SSA, that you find misguided, or do you mean that not being novel would have a hard time competing with an already developed, industry-standard implementation?
What other alternatives are there? I know that GraalVM uses a graph-based IR, for example, which I found very interesting. Do you (or someone else) have perhaps some option on how these compare?
Nothing about SSA is misguided. You hit it on the head - without being novel or strongly researched based into LLVMs deficiencies (a good example of what this would look like is pointed to in another comment), you’re unlikely to compete with LLVM
This would have benefitted from a date on the post, because that minivm link is already dead - the repo exists with the main branch being 7 months old.
Other than that I have no real opinion, I like LLVM but don’t claim to be anything but an occsional user.
I liked that sentence though, just casually wrote a C compiler, as one does.
Relevant talk from the Yasser at Handmade Seattle last year.
try qbe.
QBE could be promising if it gets a couple more full-time maintainers but as of now is alpha-quality software. It doesn’t support 32-bit targets (and would require some architectural-level changes to do so), does essentially no optimizations, and has one of the more incomprehensible C codebases I’ve seen in open-source.
Isn’t one of the points of QBE that it is small and understandable? I haven’t looked into it, but what makes it incomprehensible?
I was curious, so I browsed around at random a bit. Here’s the definition of a commonly used type:
I notice a severe lack of comments on fields that could use them.
Some of the coding style also strikes me as not very readable, such as the identifier spelling convention being wordword instead of wordWord or word_word, and function vars all being declared up front (and without comments). I have little experience with pure C, so not sure how much of this is C convention (or compliance with an old C standard).
most of the fields are self-explanatory to me from their names. a few (like link, dlink, nlive) are not (and i don’t think it would be bad to comment them) but it seems likely their function is probably somewhat localised and fairly clear in context. i don’t think i would have difficulty finding out what those fields are for if i just read the code a bit, and so they are probably all obvious to anyone who is doing any meaningful amount of work on the codebase
i’m not saying there shouldn’t be comments, but i don’t think it’s that bad that they’re not there. a compiler is usually a lot of special-purpose code and data structures (optimisation and analysis passes) organised around a single general-purpose data structure (being the core ir). it doesn’t seem unreasonable to keep the entirety of the latter in your head
i am not commenting at all on whether i think this is a good design for a compiler, whether c is a good language for writing compilers in, or whether the rest of the code is readable
Name overloading. “Tilde” is also the name of my preferred console text editor for Linux.
https://github.com/gphalkes/tilde