Investigating LLVM as a general backend for x86, x64 and arm64 code generation

[christianscheuer]

Per our chat on gitter.im/dotnet/corert today, we are investigating whether or not it makes sense for us to put some work into getting LLVM as a backend for CoreRT. (For a full context of why we need that, please refer to the gitter conversation, or feel free to contact me directly)

Thanks to all the great work that's already been done via LLVM for wasm, perhaps the project wouldn't be as crazy as I immediately think.

With help from @MichalStrehovsky and @yowl, and based on Michal's zerosharp code, I got a tiny little no-corelib Hello world to compile via LLVM an x86 Mac executable:
master...christianscheuer:macllvm

To test it, make sure to install the prerequisites (it needs llvm 10.0 and the MacOS 10.13 SDK installed, see the README for more info), then build CoreRT in Debug and skip the tests: ./build.sh skiptests, then go into the tests/src/llvm directory and run ./build.sh.
It will run CSC to compile to IL, run the modified ILC from the repo to compile to bitcode (which uses the WebAssembly LLVM backend with some hardcoded modifications) - and then use the installed LLVM 10 linker (it needs to be the same major version of LLVM that's used to produce the bitcode, and we're using libLLVM 10 to produce the bitcode) to produce a runnable executable. It then runs it, it prints Hello world and returns 42 :)

--

Now all of this raises a bunch of questions it would be great to get your input to.

• Assuming that we would be going down this path, I expect the first step would be to look at how to refactor the WebAssembly backend so that a new, generic ILToLLVMImporter can be created as a base class, and have ILToWebAssemblyImporter inherit from that, as well as other derived classes for the new x86, x64, arm64 targets (or, some other structure). For example, I suspect many opcode importers, stack management etc. should be the same no matter if the "architecture" is wasm or x64 (accounting for different pointer sizes), so there should be a lot of code that can be reused. Things like the shadow stack however I don't think we'll need for anything but wasm, if I understand the reasons behind it correctly, so there would be a challenge to see how to structure the code so both a shadow stack based and regular stack based version can coexist.
  So the question is - with all of this in mind: How would you approach code structuring of such an endeavor?
  Obviously we can do a clean copy-paste into a different directory, but I thought the two implementations could benefit from each other if they were linked...

• Overall engineering plan
  What would be the best way to approach the rest of the bringup, once that initial refactor has been done? What would be the best order of x64-ifying it (ie. add support for 8 byte pointer sizes, potentially remove the shadow stack, etc.)
  Any other considerations?

[yowl]

I dont believe Emscripten nor LLVM (https://reviews.llvm.org/D68254) support wasm64 yet, but it is planned so would be good to make any 64 bit refactoring available to Wasm also.

[MichalStrehovsky]

There are short term, medium term, and long term aspects to this work.

The short term aspect is that the CoreRT repo is getting migrated to the runtimelab repo (dotnet/runtimelab#4) and this work is likely to happen this summer (I just got green light to spend ~20% of my worktime on this in the coming weeks). As part of the move we will be switching build tooling to the one used to build the official runtime. This is mostly a good thing: the CoreRT repo is currently built using tools that were current as of .NET Core 2.0 and are starting to hit limits (we can no longer update CoreLib because it now uses prerelease C# 9.0 and we cannot consume that compiler in this repo anymore without significant build work). Once the move to runtimelab is done, it will be much easier to keep CoreRT current (just integrate from runtime master branch). The impact is that there will be churn in how the product is built/tested in the coming months. In the first phase we would be moving the more mature parts of the project (i.e. RyuJIT-based codegen). The more experimental parts of the project (CppCodegen, LLVM-WASM, Interpreter, JIT, etc.) would come later, potentially to separate branches of the official runtimelab repo (we would have a dialog on this in the coming months).

The medium term aspect is how to organize codesharing between LLVM backends targeting physical architectures vs WASM in the CoreRT AOT compiler. My gut feel would be to shoot for a ILCompiler.LLVM assembly where most of ILCompiler.WebAssembly would move to. Then build a structure where the bare LLVM importer has some virtual methods that the WebAssembly-specific backend can override. I expect the main differences would be around parameter passing and stack management. We might even just consider renaming ILCompiler.WebAssembly to ILCompiler.LLVM and have ifs in places. We definitely want to share as much as possible.

The long term aspect is also about sharing. .NET (especially code in CoreLib) is getting excessively reliant on optimization RyuJIT can do. For example, to get good performance with C# async, the code generator needs to do devirtualization and boxing elimination. Most of these managed optimizations happen in RyuJIT’s importer (the part of the code generator that reads IL and transforms it to RyuJIT’s IR) – a possible different route for LLVM would be to plug into RyuJIT’s IR to take advantage of all the managed optimizations that RyuJIT does while importing IL into IR. The existing LLVM optimization passes are not capable of doing the kind of managed-code-specific optimizations that RyuJIT does in the importer (e.g. optimize typeof(X).IsValueType into a compile-time constant, etc.). Without plugging into RyuJIT’s importer, any high performance LLVM backend will be playing catch-up to RyuJIT’s managed optimizations. There are years worth of work in RyuJIT to catch up to and more of these managed-code-specific optimizations are going into RyuJIT all the time. The current approach with the LLVM-WASM is good, clean, green-field architecture, but it will have hard time achieving same or better performance compared to RyuJIT on platforms that RyuJIT targets.

[AndyAyersMS]

A RyuJit to LLVM bridge would be interesting (similar to how mono bridges to LLVM) for a number of reasons.

It would nice to be able to run this as an optional mode for the regular runtime as well. LLILC has some of the tech needed to go from LLVM back to the data structures the runtime expects.

My guess is you'd want to bridge over fairly late, at the lower/codegen stages of the RyuJit pipeline.

I'd be happy to consult/help with this, though not sure how much time I'll have available.

[christianscheuer]

Thank you both for the thorough answers.

@MichalStrehovsky wrt the medium term aspect vs the long term (ie. LLVM based off of importing IL straight from the source, vs. reading RyuJit IR): Is there any possible path you can see where the medium term work (furthering IL->LLVM for x64+ARM64) wouldn't be in vain? For example, would it make sense to have the RyuJit IR be represented/converted back to IL, as a way to be able to share the code with how we do IL->LLVM in the current wasm backend - or would that defeat the purpose somewhat by losing potentially valuable information from the RyuJit IR?

@AndyAyersMS just out of curiosity and trying to understand how all this works - why would there be / is there a need to go from LLVM back to the runtime data structures? What's the tech LLILC has that helps with this?

On another note, it sounds to me like we should wait while the repo migration gets done before embarking on any further LLVM experimentation / prep of the refactor needed for LLVM sharing both wasm and physical archs, if I'm reading you correctly.

My completely unsolicited 2 cents on repo structuring for runtimelab would be to not rely on branches for experiments, as it quite effectively makes it needed to do tons of git-hackery in order to potentially combine experiments. (Although I understand the sentiment from a collaboration perspective).

[jkotas]

would it make sense to have the RyuJit IR be represented/converted back to IL

That is very hard / impossible. We tried this in the past with a different compiler and it did not work well.

What's the tech LLILC has that helps with this?

gcinfo encoding, for example.

[MichalStrehovsky]

My completely unsolicited 2 cents on repo structuring for runtimelab would be to not rely on branches for experiments, as it quite effectively makes it needed to do tons of git-hackery in order to potentially combine experiments.

What git hackery are you concerned about? The NativeAOT branch that we're setting up for CoreRT is basically just another fork of the dotnet/runtime master branch - I expect most experiments in the runtime space would follow that pattern - integrating between those is really just about integrating two branches. There are other branches, like the DllImportGenerator branch that would require hackery to merge, but those have different characteristics.

Eventually, once an experiment graduates, it would be simply copied over to the runtime repo, per dotnet/runtime#35609.

[christianscheuer]

Maybe I misunderstood the definition of an experiment. It just sounded like CoreRT-regular, CoreRT with JIT, CoreRT-LLVM-wasm, CoreRT-LLVM-physical etc. all would end up on separate branches, so if I wanted to consume a combination of say the experimental JIT and experimental LLVM, I'd have no way to point to a single commit or version, but would have to maintain my own branch integrating those together. Not sure if that would be easy or complex, it just sounds a bit like busywork and moving complexity to the consumer.
I guess I'm also basing this off of that it appears experiments are experiments for a very long while before graduating, even if they're already usable :) So my point was just that however you do it that I hope it's not gonna be more complex to consume the "experimental" builds. For example, we really like the fact that we can consume ready-built CoreRT packages today, and I think such a scheme is very good for adoption. If now I could just add a flag in the .csproj to include say JIT or LLVM that would be my preferred scheme, if they co-existed. I'm sure there are good reasons for why you cannot do it, but there's a big difference from consuming the experiments by enabling a flag somewhere to having to maintain our own branch merging other branches together and understanding potential conflicts between such branches.
But again I might be misunderstanding - so I'll just watch what you do and I'm sure you've thought of these things.

[MichalStrehovsky]

I see. I would expect LLVM-wasm and LLVM-physical to be in the same branch if they're both based on LLVMSharp (and not the RyuJIT IR plan). Whether that branch is NativeAOT or some "NativeAOT-LLVM", we'll decide/discuss based on practicality. The practical consideration includes things like "the runtime repo already handles Emscripten-based builds and we should definitely hook into that, but that also means that whenever dotnet/runtime repo upgrades emscripten and there's fallout from that, fixing the fallout is a prerequisite to a successful refresh from dotnet/runtime" (and similarly, whenever there's a RyuJIT change that requires followup, resolving that is blocking successful integrations). I don't have a good sense right now on how many difficulties we would be facing in integrations and that's why I don't have much to say. We'll want to keep NativeAOT pretty up-to-date with dotnet/runtime master because it proved useful in the past to root cause unexpected regressions.

We'll definitely have NuGet packages for all runtimelab experiments.

[jkotas]

The practical consideration includes

Another factor to consider is level of maturity of different experiments. CoreRT repo kept experiments with very different maturity levels in the same branch and build that did not help with clarity.

[yowl]

@jkotas Did you mean "did not help with clarity"?

[jkotas]

Yes, fixed.