6502 back end for LLVM (2022) [video]
youtube.com
youtube.com
Also, I particularly like how they hacked the LLVM workflow to deal with the registers. I don’t know LLVM at all, its just a toolchain option to me, but it was interesting and engaging.
The doc tells you to use one of the many simulators. But which one I wonder. For example there is a 6502 simulator generated code. Which one I should use? Not telling. And saying one should know is not that helpful. Just one more example link it would be all good.
pic12/16/18 next? (a man gonna dream...)
> So, I wanted to do a little blurb on the topic of upstreaming LLVM. My previous answer to this questions was "yeah, we'd like to, but we have more work to do." This implied that we were working on it. More accurate to reality is that we were keeping it in the back of our heads and doing work to decrease the diff from upstream. The latter is also useful for making merges from upstream easier, and that's closer to the real reason I was doing it.
> Well, I've lost some rather high-profile fights upstream. In particular, upstream now strips out attribute((leaf)) from LTO builds, which is the whole thing that makes our static stack solution work. I personally think this decision was totally bogus, and wasn't alone in this, but the conservative voice won out. My experiences with the LLVM community so far has been one of deep conservativism; the stranger you are, the more you need to justify your strangeness with real-world impact. We're a very strange hobby project, which just doesn't bode well. We could make our backend a lot less strange by making it a lot less good, but then it becomes impossible to compete with incumbents like KickC and cc65.
> Accordingly, I'm not keeping the goal of maintaining llvm-mos entirely upstream in the back of my head anymore. I don't oppose work along those lines, unless it interferes with making llvm-mos the best 6502 compiler we can.
> That being said, LLVM may independently change to be more amenable to us, so this may become easier in the future. This has already happened prior to us, with GlobalISel and AVR making development of the backend far simpler. If that happens, I'll definitely reexamine my opinion on this.
> Alternatively, I'd definitely be open to upstreaming the unobjectionable parts of llvm-mos backend; we could then maintain the actual distribution as an increasingly thin fork from upstream. In fact, we could probably get started on that project today; I haven't yet spent much time considering the idea, but I'm starting to like it more and more, since it gives increased visibility, easier merges, and an excellent reference backend for upstream documentation. (We're really nice once you strip away all the crazy!)
The old semantics also matched GCC's actual behavior; when we brought this up in a GCC issue, those present decided that GCC's behavior was wrong, but the appropriate maintainer couldn't be reached for a final say. The issue is still hung like that.
There were also a few other folks trying to do the same kinds of whole-program call graph analysis this enables, IIRC for GPU purposes. So, there was a lot of conflicting opinions about how this should work, a lot of uncertainty, all the recipe for a big long endless thread.
EDIT: This is of course my extremely biased take on the proceedings. This was also the first and only "open source kerfluffle" I've so far been direct party to; I've seen these come and go on mailing lists before, but I was surprised how different it felt to actually be inside one.
I know that even using C instead of ASM on these 8-bit systems typically results in painful size and performance penalties though. Are there effective tools/techniques for narrowing that gap?
There's nothing in LLVM itself that makes it use larger sizes, it just depends on the ABI and what's fastest when ABI doesn't matter.
It's easy to find a sequence of instructions to implement a program, but the challenge is finding a good, small, fast sequence of instructions. The difference between current compilers and the best possible sequence is often 10x, and that difference is worth tens of billions of dollars - since you can reduce your CPU budget by 10x if all your programs run 10x faster.
Searching all possible sequences is infeasible, but it seems very practical to get AI to assist with some kind of directed search. Either additively (starting with an empty program and adding instructions till it correctly implements the programmers program), or subtractively (use a dumb compiler to make an inefficient program, and then use some ML model to decide how to adjust the instruction sequence to be smaller/faster, while remaining correct).
This would require an algorithm to check if the output program and input program have identical behavior. However, this is impossible as per Rice's theorem.
You moved a _little_ too quickly.
There exist program-pairs which can be proven equal, and those for whom no proof exists. You can organize the production of new programs into finite steps and organize the act of creating a proof-of-equivalence between the input and output into finite steps, then execute one step of creating a new program candidate followed by one step of finding the equivalence proof for each of the (finite number of) candidate programs created so far. In this way you are guaranteed to find an output program and its equivalence proof whenever such an (input-program, output-program, equivalence-proof) tuple exists.
Finding the equivalence proof is recursive enumeration—the same as creating the program candidates—but in some machine verifiable proofing language.
Speeding this up by leaving out syntactically incorrect programs and equivalent programs, as well as defining the proofing language and implementing the checker are left as an exercise to the reader.
Often they find fixes that improve this or that internal workload by 0.2% and consider that a big win.