Implement stack maps for unwinding

[pcwalton]

This issue tracks implementation of stack maps in LLVM. The goal is to have stack maps working for unwinding for 0.3 or 0.4.

The idea is to use precise stack maps instead of landing pads to run destructors of unique pointers and resources during task failure. This will allow unwinding to work on Windows and should also lead to dramatic code size reduction. Unwinding performance should be slightly improved as well. Eventually this can be extended to support accurate tracing garbage collection for shared boxes (either as a backup for reference counting or in lieu of reference counting).

This requires fairly invasive changes to LLVM. All optimization passes will be turned off at first, and will be reenabled one by one. They should not be hard to reenable.

At the moment, I believe the LLVM steps needed here are:

1. ☑ Add a llvm.gcregroot intrinsic. Translate it in the fast instruction selector. This needs to be done during call lowering, to make sure that the register roots end up within the call sequence.
2. ☑ Add llvm.gcregroot intrinsics automatically after call sites based on the types of SSA values. This must be done very late in IR transformation, probably right around the CodeGenPrepare pass.
3. ☑ Lower llvm.gcregroot intrinsics properly in the fast instruction selector. This requires creating a new, fake MachineInstr that tracks GC roots and their address spaces.
4. ☑ Add infrastructure to the GC strategy class to support register roots.
5. ☑ Translate llvm.gcroot intrinsics in the fast instruction selector as well.
6. ☑ Add a generic GC strategy and metadata printer. We should be able to use this for Rust.
7. ☑ Track callee-saved registers in the GC metadata object. Update the generic GC strategy to record the locations of these registers.
8. ☑ Allow getelementptr instructions that reference an alloca instruction to be rooted with llvm.gcroot. This allows structs containing pointers to be rooted without complex type encoding schemes.
9. ☑ Implement an LLVM pass that automatically roots allocas that contain traceable pointers with llvm.gcroot, and uses the metadata field to track the locations of the pointers therein. (I have a patch for this that needs to be resurrected.)
10. ☑ Implement a pass in LLVM that computes liveness on the SSA graph. This used to be present in LLVM but was removed due to the lack of use and poor performance. It should be rewritten.
11. ☑ Using this new liveness pass, augment the llvm.gcregroot insertion pass to throw out dead register roots.
12. ☑ Modify the llvm.gcregroot insertion pass to root only pointer origins, not any derived pointers. Consider pointer origins and derived pointers a single value for the purposes of liveness.
13. ☐ Add support to the SelectionDAG-based instruction selector for GC register roots. This requires a new SDNode. We will need to ensure that it is inside the call sequence, so this requires changing the signature of LowerCall and/or LowerCallTo. Thus all targets will need to be updated.

We will eventually need to have a comprehensive LLVM-level test suite before all of this can be sent upstream.

On the rustc side, we will need to tag all shared and unique boxes with addrspace(1). (This currently happens for shared boxes, but not for uniques.) Unique boxes will need to become self-describing; this is not necessary in theory, but in practice it helps the LLVM side of things if all that needs to be tracked for each virtual register is a single address space value. Additionally, we will need to use the llvm.gcroot intrinsics to root (a) every enum that contains shared pointers, unique pointers, or resources; and (b) every resource.

In the Rust runtime, we will need to implement the stack crawler. (I have a prototype of this written already.) We will then need to use it to locate all of the roots during unwinding and then run their destructors. This may require fixes to (or replacement of) the shape code.

I intend to keep this issue up to date with the latest changes to our strategy here.

[pcwalton]

Commit b99038c places boxes in addrspace(1).

I have code working in a branch to root alloca instructions that contain GC pointers at the LLVM level. Note that we still need extra support from rustc to root enums.

Additionally, I discovered that llvm.gcroot intrinsics are only supported in the SelectionDAG-based instruction selector. We need to port the support over to the fast instruction selector.

[pcwalton]

Based on some further conversations with the upstream LLVM maintainers, this approach will not work due to the inability to trace back through getelementptr instructions at code generation time. We need a different approach that annotates the IR instead of performing the analysis late. This rules out moving GC at the present time.

[graydon]

Ouch. Curious how that relates to moving gc.

[pcwalton]

Code generation passes can introduce arbitrary register-to-register copies, which means that we wouldn't be able to find all the copies of each GC root to update for moving GC.

[pcwalton]

Steps (1) through (3) are basically implemented in the noteroots-ir branch of my LLVM fork.

[pcwalton]

Step (4), GC metadata and strategy infrastructure, is now implemented in the noteroots-ir branch.

[pcwalton]

Realized I forgot about callee-saved registers; updated the list above.

[pcwalton]

Realized I'll want GEPs of allocas to be able to be rooted as well. Updated the list.

[pcwalton]

Steps (5) through (7) are now complete in the noteroots-ir branch. Most notably this includes the actual frame table printer.

[pcwalton]

Steps (8) and (9) are implemented in the noteroots-ir branch. This means that the rustc front end can begin to add llvm.gcroot calls to root enums, and tuples and records containing GC pointers that are stored on the stack should be handled properly.

[pcwalton]

Liveness has now been implemented according to the paper and lightly tested in my noteroots-ir branch. This is step (10) above. It's not integrated into the GC passes yet though.

Also, I discovered that LLVM already has support for tracing getelementptr instructions back to their roots. This should save a bit of time.

[pcwalton]

Steps (11) and (12) have now been completed in my noteroots-ir branch; only live pointer origins are rooted. I also changed the fast instruction selector to handle GC roots specially—this is needed to avoid breaking call sequences.

I'm now going to look into getting rustc ready to handle all of this.

[graydon]

applause but not done in time, moving to 0.4.

[nikomatsakis]

Not critical for 0.6; removing milestone

[catamorphism]

@pcwalton What's the status of this?

[brson]

This is not going to happen any time in the near future.

[thestinger]

Unwinding now works fine on Windows, and LLVM does have experimental stack map support. It's not clear if there's anything else needed for a precise Rust garbage collector so I don't see a need to leave this open.