Preliminary: enable "spill on exception path" and "spill on normal path" RS4GC options

[JosephTremoulet]

Summary

Option -rs4gc-spill-on-exceptional-path should use spills/fills rather than gc.relocates on exceptional paths out of a statepoint
Option -rs4gc-spill-on-normal-path should do the same for the normal path

Also included are some changes to deal with joins and PHIs that we'll need to support catchpad-style EH

It's not functional yet, but I think it makes sense to share early so we can have contextualized discussions about where it should go and who should implement what.

[JosephTremoulet]

You can probably ignore the changes in Instructions.h -- I'll split that out and submit upstream before the other pieces land. It just gives us a way to write loops in RS4GC that operate on all an invoke's potential destinations rather than assuming it has a single landingpad.

[JosephTremoulet]

I've added several inline comments to explain my thinking. One thing that I haven't given any real thought to is whether this has implications for how we compute what the live sets are. I know at least for the PHI case that if a value is only live because of a use in a phi in the catchpad, we don't actually need to spill that value for its own sake because we'll be separately spilling it for the PHI. Not sure if there are other issues along those lines for the non-PHI cases.

include/llvm/IR/Statepoint.h

334

I have the code structured to use a flag to decide if it should spill on exceptional paths or not, which is independent of anything else. Of course it's not actually valid to use relocates on catchpad EH because we can't split those predecessors, so I've put assertions in the places that would fall over if the invalid combo is attempted.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

217

I needed some maps that persist as we process each statepoint, but should still be opaque details from the caller's perspective, so I've added a RecordSet type that the caller can allocate and it contains the record vector and the persistent maps.

1571

We want the allocas that we add to hold the spilled pointers to appear to have their contents modified at the statepoints across which they carry a value, and also to be reported as live at those statepoints. I was thinking that simply adding the allocas to the statepoints gc args would accomplish that, but the assertion failures I'm currently running into make me think I may have been wrong about that. This loop is building up the set of allocas and stuffing them into the gc args.

1585

The following two loops insert stores to the spill slots we generate. As you can see, I used the naïve before-each-invoke store placement strategy for both SSA values live across the statepoint and for the stores to the slots that are used to eliminate PHIs. I'm using the naïve placement of those stores (before each invoke) because doing any better for the PHI case requires checking for interferences and I wanted a base working implementation first. However, it's occurred to me that for the non-PHI cases (the loop over LiveVariables here), each slot corresponds exactly to one SSA value, so we wouldn't need any interference analysis to know it's legal to put a single store to that slot immediately after the value is defined, as opposed to putting a store before every invoke it is live across. We'd need another persistent set in the RecordSet to keep track of this so we don't insert multiple stores for the same value. Since you guys don't need to worry about the PHI case, that might be an interesting option for you to pursue.

1648

This is just another place where processing would fail if we tried to use the relocate mechanism on catchpad EH where the pads may be joins.

1700

PHI loads intentionally omitted here because I'm still splitting critical "normal dest" edges, so there can't be PHIs.

2405

Here I was thinking that if you're spilling for the exceptional path anyway, you may as well leave the CFG alone and allow PHIs at the invokes. Which of course contradicts what I said above about how you'll never have PHIs and so can place your stores immediately after their defs. So maybe this should have a separate control bit dictating it, or just always normalize invokes that target landingpads, or something along those lines.

2578

Obviously it was totally bogus of me to disable this assert and maybe if I stop to understand what's broken here I'll fix whatever is also causing the next assert that I'm running into. I was just trying to see if I could see what other issues were lurking behind this.

[JosephTremoulet]

Ok, I migrated my work-so-far over to master and pushed up a diff to Phabricator. Happy to hear your thoughts when you've had a chance to look at it, regarding both direction and coordination of work going forward. As for the latter, my only thoughts are

1. There's the whole business with the PHIs and the invoke dest iterator that's interesting for me and not you. I definitely intend to introduce the iterator as a separate and prior change (though I was thinking to post it at the same time as posting this stuff so that in its review I could point to a use case). I suppose the PHI stuff could be split out and pushed up as a later change.
2. As I describe in some of the inline comments below, if you don't have PHIs at your landingpads you can spill at defs instead of spilling at invokes. That's probably more interesting to you than it is to me since your project is mature enough to care about code quality already (I care enough to do it eventually, but would probably hold off and do it as a subsequent improvement), so if you're eager to do it knock yourself out.

My immediate plans are to (deal with the 3.8-blocker bug that just came my way and) keep trying to get it running correctly on a simple unit test.

Thanks
-Joseph

[reames]

include/llvm/IR/Statepoint.h

334

This seems reasonable as a migration step. I suspect if we go down this path, we should delete all the landing pad special casing here and in the lowering code.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

182

The use of these typedefs might not be a good idea any more. It might be worth looking at whether appropriate use of auto makes them redundant. I introduced them when changing the underlying data structures and never removed them.

211

This may be better as a DenseMap<BasicBlock*, SmallVector<Value*>>

217

I think this is probably over abstraction, but we'll see. Haven't even finished reading through the code yet. :)

1578

I don't think you need ArgBacking containing the LiveVars iff SpillOnNormalPath is true.

p.s. ArgBacking is a confusing name..

1587

Any reason to not insert all the allocas upfront given we know all the values live at any safepoint in the entire function?

1596

I'm confused: Why are you manually updating PHIs at all? Inserting the naive stores/loads on for the relocation path and reusing the same strategy as relocaViaAlloc would seem to get you all of this for free. In fact, we could even share most of the code in question.

1636

I'm really not clear why you're needing to do any transative walks here. I think this is confusing due to the same question as just above.

2405

This should just be removed. If we don't need a distinct landing pad any more because we have a single spill slot used by all the invokes reaching it, this code becomes pointless.

2580

I was really really expecting to see changes in what relocationViaAlloca did and expected. The fact the API stayed roughly the same seems surprising.

What I was expecting was:

1. We assign spill slots globally for a single SSA value.
2. We insert explicit spills before each statepoint if we're spilling in either path.
3. We insert both gc.relocates and fills (depending on options).
4. We use the PromoteMemToReg hack to convert all uses of the original value (including the new ones we introduced), into SSA. AH! The problem is the Alloca's introduced are no longer fully promoteable. I missed that detail originally.

Hm, if we can't rely on PMToReg to solve the general SSA construction problem for us, this becomes a lot more annoying than I'd realized. Still probably the right approach, but the complexity in your patch suddenly makes a lot more sense.

[JosephTremoulet]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1578

Funny, I'd written it that way originally, then later convinced myself it should be this way. Is the idea that the statepoint doesn't need to bother with the original values when we're spilling on all paths because those values aren't live over the statepoint anymore (but instead have uses at the spills)? I'd buy that...

And yes, it was a struggle to name "ArgBacking". The idea was that it's "thing that GCArgs might need to be a ref to if it can't just be a ref to LiveVariables". I'm happy for better suggestions.

1587

No reason, that sounds better, it just hadn't occurred to me.

1596

What makes you think I'm updating PHIs? This is the code that's inserting the naïve stores/loads.

1636

If I've got something like

try {
  code;
  try {
    code;
    try {
      invoke();
    } catch (A) { ...}
      catch (B) {...}
  code;
  } catch (X) { ...}
} finally { ... }

Then the invoke's unwind dest is a "catchswitch", which starts a block and is also a terminator, having successors for catch(A) and catch(B) and yet another "catchswitch". The second catchswitch's successors are catch(X) and the finally. This code needs to visit catch(A) and catch(B) and catch(X) and the finally, which are found by transitively following unwind edges in the CFG.

1918

btw, this bit is the tie-in with the mem2reg thing -- this goes and inserts a store to a new alloca after each reload I inserted above, and the subsequent mem2reg picks up those stores along with any reloc/remat stores for the same ssa value when it rewrites it in SSA.

2405

Supposing that we get to the point that we have intelligent spill placement, I agree with you entirely.

In the meantime, there's a tradeoff to consider:

on the one hand, you could remove this code and use the naïve spill placement and be happy that you've got less codepaths here and that you're more in line with the end goal

on the other hand, you could keep this code, and your naïve spill placement could be "for each SSA value that's live across any statepoints, insert a single store immediately after the def" instead of what I'm stuck with which is "for each SSA value that's live across any statepoints, insert a store for it immediately after the def *and also another store immediately before each statepoint whose landingpad uses it in a PHI*

I'm stuck with the second, so have no stake in which path you want to go down here. I just wanted to make sure you're considering the tradeoff. FWIW, if I were in your shoes, my instinct would be to keep the edge splitting so that I could have less horrible naïve spill placement.

2580

By the end of your comment it sounds like we're on the same page, but just to make sure:

The code here is doing (or at least intending to do) all of 1-3 (my superfluous use of memoization for #1 where a pre-pass would work aside).

We don't want MemToReg to do anything with the new allocas because we want them to stay memory. Running it on the new allocas would exactly put back the SSA values and PHIs that we're trying to spill.

But you've reminded me that we do in fact have the inverse utility in the Reg2Mem pass...

OK, I've just spent the last 10 minutes convincing myself that we just want a bunch of calls to DemoteRegToStack and DemotePHIToStack, only to subsequently unconvinced myself (we want loads right after each landingpad, not at all uses). Hmm, maybe DemotePHIToStack does the right (naïve) thing for the PHIs we may be wanting to eliminate (though I'd have to extend it to handle PHIs on catchpads), so we want that for PHIs and we want our own load/store placement for other things we're spilling...
Curious what your take is.

[reames]

Given this is into brainstorming, would a skype call be better/higher bandwidth?

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1578

Something as simple as "GCArgs" would be a bit more clear. Another option might to track spill slots and explicit relocations separately, then only combine them when actually inserting into the statepoint.

1596

Two bits: one, you're looking through more the immediate successors, and two, you're tracking incoming values from phis. I'm not clear why you need to do that. I thought the entire idea was that you wanted all invokes leading to a shared unwind to share a spill slot for those values. Once that's true, you should need an unconditional reload, and *maybe* to replace a few phis with the new reload. Or am I missing something?

1636

Ah, okay. This is about dealing with MSVC exception handling, not the shared alloca bit. :) That makes a lot more sense now. When you're ready for actual review, I'm definitely going to have you separate the MSVC specific bits first, then follow with the spilling change.

1918

Just to make sure I'm clear, we now have *two* sets of a allocas? One used purely for rewriting, the other the "real" ones that get left? That makes more sense, though I didn't get that from the code on first read through.

Minor: You should change the name of the function if you're going to reuse it in a different way.

2405

I'm not sure I'm following what you're saying at all. The code we're commenting on normalizes invokes to ensure both normal and return paths has a single predecessor.

I thought we were running with the idea that values along the exception edge were always going to be spilled in rs4gc? If so, then we're going to have a single reload in the unwind path for all incoming invokes and one in the normal path. Spill wise, we'll have one store inserted for the exceptional path (at the def you said?), and one store inserted by the current lowering for the normal path (in the incoming block). I don't see how normalizing the exception path or not will matter.

2580

I don't think using DemoteRegToStack is going to be the right approach. For one thing, the current implementation appears to assume it can split the critical edge of the invoke to the landingpad which is exactly what you don't want. DemotePHIToStack might be a useful building block.

Interestingly, if I'd know about that utility originally, the existing relocViaAlloca code probable could have been expressed as "demote value to stack, insert additional relocation stores, promote to reg",

I'm more and more thinking we're trying too hard to solve this within the existing Mem2Reg framework. The entire point of that was to save effort, and it doesn't appear to be doing so.

Might it make sense to switch the existing code over the SSAUpdater as we discussed in the email this morning? Once we'd done that, we can get rid of one set of allocas entirely.

[JosephTremoulet]

Thanks for the feedback. I'm comfortable iterating with this via Phab and supplementing that with using some of our bi-weekly meeting time to talk, but if you'd prefer to discuss over Skype I'm happy to schedule something.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1596

I think this is another catchpad-ism surprising you. I need to walk through an arbitrary number of blocks which are unsplittable in the sense that I can't put any code in them and they can't have anything other than PHIs (and catchswitches) in them. Yes, I'm putting a spill just before each invoke for each PHI in the EH dispatch code, and an unconditional load from the spill at the top of each splittable successor.

1636

It'll have to be the other order because there's no way to represent the MSVC stuff with gc.relocate, but sure I can separate into two patches.

1918

Right. The code I'm adding builds up a set of "real" allocas that we want to stay and through which we spill whatever we need to not be enregistered on whichever paths. Subsequently we have code where we'd like to point SSAUpdater at each relocate/remat/load-from-"real"-alloca, but instead today we create throwaway allocas and put a store at each relocate/remat/load-from-"real"-alloca. I wasn't trying to coalesce the one type of spill slot with the other at all, and in fact in my head I have to pretend we're not using allocas for that second part and just think of it as SsaUpdater, else I get terribly confused...

So e.g. whenever I insert one of those unconditional loads from a "real" alloca at the top of an EH pad, it's immediately followed by a store to one of the "throwaway" allocas (until Mem2Reg removes the store).

2405

we'll have one store inserted for the exceptional path (at the def you said?)

Whether it's at the def or not is the key point here. If we split critical edges, then yes you could always just put it at the def. But if we don't split critical edges and therefore allow PHIs at landingpads that we erase by spilling, then since all the values feeding any one PHI have to share the same spill slot, we're doing coalescing and have to check for interferences. To make it concrete with an example:

start:
  %1 = _
  %2 = _
  br i1 _, label %left, label %right
left:
  invoke @_
    to label _ unwind label %pad
right:
  invoke @_
    to label _ unwind label %pad
pad:
  %phi = PHI ty [ %1, %left ], [ %2, %right ]
  _ = foopad ...

then you have to allocate a spill slot for %phi, and you have to spill both %1 and %2 to that spill slot, and if you put those stores at the defs of %1 and %2, the store of %2 will overwrite the store of %1, so you'll get incorrect behavior on the path through %left.

So, ok, what I'm doing to make things correct in the face of PHIs is putting stores at the tails of the predecessors -- i.e. right before the invokes. In the example above, that's a store of %1 to the slot for %phi in %left, and a store of %2 to the slot for %phi in %right, which is what you want.

But if we switch to a more typical example of what EH code looks like (at least in my experience):

  %1 = _
  invoke @callee1, ...
    to label %cont1 unwind label %pad
cont1:
  ...
  invoke @callee2, ...
    to label %cont2 unwind label %pad
cont2:
  invoke @callee3, ...
    to label %cont3 unwind label %pad
...
cont_n:
  %2 = _
  invoke @callee_n+1, ...
    to label %cont_n+1 unwind label %pad
cont_n+1:
  invoke @callee_n+2, ...
    to label %cont_n+2 unwind label %pad
...
pad:
  %phi = PHI ty [ %1, %start ], [ %1, %cont1 ], [ %1, %cont2], ..., [ %1, %cont_n-1], [ %2, %cont_n], [ %2, %cont_n+1], ...
  _ = foopad
  ...

then we're putting redundant stores before a lot of invokes. Smarter spill placement can of course figure this out, and we'll want smart spill placement at the end of the day one way or another, but it's not exactly trivial and not going to be part of the code on day 1.

So the question is just if you want to avoid all those redundant stores, in the meantime before we have smart spill placement, by "cheating" and leaving this normalization code here, in which case we'd split all the exception edges and being naïve would mean you'd get a ton of loads, but at least the loads would be on the exception path, and maybe we already have a backend tail merge optimization that would clean them up for you?

2580

I don't think using DemoteRegToStack is going to be the right approach ... DemotePHIToStack might be a useful building block

Yeah, I've talked myself back out of it since posting. DemotePHIToStack might match where we'll be putting "real" stores and loads for landingpad PHIs, but it's not something that has a really nice extension to WinEH so I don't think it makes sense to use there, and neither do I think it makes sense for this code to have two different spilling mechanisms depending what kind of EH pad it sees.

Might it make sense to switch the existing code over the SSAUpdater as we discussed in the email this morning?

Yes, I think that would definitely make it easier to follow what's going on (though from my point of view it would make the current ToT code easier to read too, and is orthogonal to this). Since I'm still in a "bring up basic correctness" phase, I'm more interested with the bits here and would be inclined to defer switching to SSAUpdater until later, but if you think it's important to switch to SSAUpdater first you wouldn't have to twist my arm too hard, and of course if one of you wants to switch to SSAUpdater I'm more than happy to rebase these changes on top of that.

[JosephTremoulet]

• rebase
• drop temp use holder insertion, pushing liveness adjustments into liveness calculations

[JosephTremoulet]

I updated the diff just now because I just now got the changes to a point where they do something other than crash. Now they generate reasonable-looking spills/fills on a basic .ll test with catchpad EH. I have yet to verify whether the right thing happens w.r.t. reporting the spill slots as live when we subsequently generate the stackmaps.

The main thing that the update addresses is that the "insert temp placeholders after statepoints" strategy for updating liveness w.r.t. depot arguments and extended base pointer lifetimes is that it conflicts with allowing unsplit critical exception edges. Consider:

  br i1 _, label %left, label %right
left:
  invoke @_
    to label %left.cont unwind label %pad
left.cont:
  _ = <op> ty addrspace(1)* %x
right:
  invoke @_
    to label %right.cont unwind label %pad
right.cont:
  _ = <op> ty addrspace(1)* %y
pad:
 <code that doesn't use %x or %y>

We'd compute that %x (resp. %y) is live across the statepoint in %left (resp. %right), and go to put uses of their base pointers at the head of each successor, which puts uses of both %x's base and %y's base in %pad. Then we'd re-run liveness, and the uses of %x's base and %y's base would propagate not just back to the statepoints they are live across, but also out the other predecessor edge from the pad, making them live across each other's statepoints. There's an assertion that noticed and rejected this because the expectation is that the only lifetime extension that happens is that bases' lifetimes are extended down into regions where their derived pointers are live, but in this case the statepoint in %left (resp. %right) didn't have any uses derived from %y's base (resp. %x's base).

After much deliberation, I arrived at the conclusion that the best thing to do would be to push the two special liveness-processing rules down into the liveness-calculating code itself, which on the one hand is a shame to lose that separation of concerns but on the other hand I think worked out reasonably well. The two rules are:

1. depot arguments need to be seen as live *across* the statepoints. Conveniently we can pick depot arguments out of their bundles and so explicitly add them in when computing what's live immediately after a statepoint
2. base pointers need to be seen as live across any statepoint that one of their derived pointers is live across. For this I plumbed the DerivedToBase maps all the way down into the base liveness transfer function (opaquely through the intermediate functions) where it simply looks up the bases whenever it encounters a statepoint and adds them to the gens. I also have to explicitly add the bases in the routine that gets the live set after a statepoint to make them live through (and as I'm typing this I realize I forgot to add that part in the current code).

I'm thinking I'll need to split this out into several changes for actual review. I think conceptually stages along these lines would make reviewing easier:
1 - iterators for funclet EH successors (depends on nothing)
2 - allow spilling across statepoints on normal and/or exception paths (depends on nothing)
3 - replace the temp use holder insertion with explicit liveness computation adjustments (depends on nothing)
4 - stop splitting critical unwind edges out of invokes, allow PHIs in EH pads (depends on 2&3)
5 - support funclet EH and walking through catchswitches (depends on 1&4)

I haven't started yet sorting through how painful it would be to separate out those pieces, but fwiw my current thinking is that those are the logical pieces.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

182

I just added a couple because I use them as parameters, which of course can't be auto. But yes your comment still applies to the others.

1224–1234

To get the right liveness gens, the walk needs to realize when it hits a statepoint and add in the bases. So here we build a map whose keys are the statepoint instructions. The values conceptually are really the sets of bases, but I didn't want to create and destroy a bunch of intermediate sets so the keys are actually pointers to the DerivedToBase maps.

2996

This is where I also need to explicitly add in the bases of the parameter statepoint.

[JosephTremoulet]

• add missing base pointer insertion
• remove stale comment

[JosephTremoulet]

I notice that the spills manually inserted by RS4GC with these changes show up as "Direct" slots in the stackmaps, and that those spilled by lowering show up as "indirect". Looking at http://llvm.org/docs/StackMaps.html#stack-map-format, I can imagine either:

1. that this is a problem and I need the new slots to be "Indirect" (since the GC pointers are in the slots, not pointing to the slots), or
2. that this is fine because the runtime wants the slots reported to it (not merely the contents of the slots) so that it can update them

Are either of my conjectures correct? If they need to be reported as "indirect", any suggestions on how to implement that? Seems like annotating the allocas is a non-starter since metadata is droppable, which means we'd need to change the signature of the statepoint intrinsic?

(as far as LLILC is concerned, we only expect one sort of thing, so I could just as easily let the reporting fall out like it's doing and then just have the LLILC code ignore the direct/indirect distinction)

Thanks

[JosephTremoulet]

I went to create the spill slots up-front. Looking at the code after doing that, I realized it makes it more readable to pull all of the spill/fill insertion into the new pass, so that its workings are akin to the rematerialization pass. So I did that.

I also took a stab at incorporating the feedback that I should change the name of insertRematerializationStores if I'm calling it in a new context. The best idea I had was to start using the term reconstitute to mean rematerialize or spill. So for any gc pointer live across a statepoint, we can "relocate" it via gc.relocate, or "rematerialize it" by copying its defining expression to after the statepoint, or "spill" it by storing it to a new alloca before the statepoint and loading it after, and the two options that aren't "relocate" are jointly "reconstitute". I updated some type/method names accordingly.

I also put in some TODOs for some things that we'll almost certainly want to do for CQ but that I think make sense to implement as follow-on changes:

• smarter spill placement
• distinguishing which edge(s) a live pointer is live out of and whether it's live just to be used in a successor phi, to avoid some superfluous spilling

At this point I think the code looks pretty much like I'd like it to look for check-in (barring whatever I discover needs changing as I write/run more tests and get feedback), so I'm going to focus on splitting this into smaller constituent changes that are easier to review, adding appropriate tests with each of them, and putting them up for "real" review, unless somebody objects.

[JosephTremoulet]

cosmetic tidying

[JosephTremoulet]

FYI, I've split this out into constituent changes (locally). I think at this point it makes sense to hold off uploading them individually to Phabricator until they're ready for real review (for fear I'd lose track of things otherwise), but I do have them pushed up to my GitHub fork for my own sake, so if someone happens to want to look at the changes that way, they are:

1 - rename a few "rematerialize"s to "reconstitute"s (split out to minimize noise) [no deps]
2 - enable spilling on normal and/or exception path [depends on 1]
3 - stop using temporary use holders [no deps]
4 - allow critical unwind edges when spilling on exception path [depends on 2 and 3]
5 - add iterators for "transitive" unwind destinations [no deps]
6 - support statepoints over funclet EH [depends on 4 and 5]

I'm currently working through tests (checking for / fixing regressions, adding new tests). The one main open question I still have is whether the spill slots need to be reported as "indirect" in the stack map, in which case I'll need to add a change that updates gc.statepoint's signature to accommodate that and rebase #2 on it.

include/llvm/IR/Instructions.h

 
 namespace llvm {
 
 class APInt;
 class ConstantInt;
 class ConstantRange;
 class DataLayout;
 class LLVMContext;
+template <bool> class UnwindDestIterator;
 
 enum AtomicOrdering {
   NotAtomic = 0,
   Unordered = 1,
   Monotonic = 2,
   // Consume = 3,  // Not specified yet.
   Acquire = 4,
   Release = 5,
public:
   }
   void setNormalDest(BasicBlock *B) {
     Op<-2>() = reinterpret_cast<Value*>(B);
   }
   void setUnwindDest(BasicBlock *B) {
     Op<-1>() = reinterpret_cast<Value*>(B);
   }
 
+  /// getTransitiveUnwindDests - get an iterator that visits all EH pads
+  /// this invoke may reach by unwinding through its unwind edge and any
+  /// ensuing unsplittable blocks, optionally visiting the unsplittable
+  /// blocks themselves.
+  template <bool SkipUnsplittable = true>
+  iterator_range<UnwindDestIterator<SkipUnsplittable>>
+  getTransitiveUnwindDests() const {
+    return UnwindDestIterator<SkipUnsplittable>::range(getUnwindDest());
+  }
+
   /// getLandingPadInst - Get the landingpad instruction from the landing pad
   /// block (the unwind destination).
   LandingPadInst *getLandingPadInst() const;
 
   BasicBlock *getSuccessor(unsigned i) const {
     assert(i < 2 && "Successor # out of range for invoke!");
     return i == 0 ? getNormalDest() : getUnwindDest();
   }
BasicBlock *getUnwindDest() const {
     return nullptr;
   }
   void setUnwindDest(BasicBlock *UnwindDest) {
     assert(UnwindDest);
     assert(hasUnwindDest());
     setOperand(1, UnwindDest);
   }
 
+  /// getTransitiveUnwindDests - get an iterator that visits all EH pads
+  /// this catchswitch may reach by unwinding through its unwind edge and any
+  /// ensuing unsplittable blocks, optionally visiting the unsplittable
+  /// blocks themselves.
+  template <bool SkipUnsplittable = true>
+  iterator_range<UnwindDestIterator<SkipUnsplittable>>
+  getTransitiveUnwindDests() const {
+    return UnwindDestIterator<SkipUnsplittable>::range(getUnwindDest());
+  }
+
   /// getNumHandlers - return the number of 'handlers' in this catchswitch
   /// instruction, except the default handler
   unsigned getNumHandlers() const {
     if (hasUnwindDest())
       return getNumOperands() - 2;
     return getNumOperands() - 1;
   }
 
BasicBlock *getUnwindDest() const {
     return hasUnwindDest() ? cast<BasicBlock>(Op<1>()) : nullptr;
   }
   void setUnwindDest(BasicBlock *NewDest) {
     assert(NewDest);
     assert(hasUnwindDest());
     Op<1>() = NewDest;
   }
 
+  /// getTransitiveUnwindDests - get an iterator that visits all EH pads
+  /// this cleanupret may reach by unwinding through its unwind edge and any
+  /// ensuing unsplittable blocks, optionally visiting the unsplittable
+  /// blocks themselves.
+  template <bool SkipUnsplittable = true>
+  iterator_range<UnwindDestIterator<SkipUnsplittable>>
+  getTransitiveUnwindDests() const {
+    return UnwindDestIterator<SkipUnsplittable>::range(getUnwindDest());
+  }
+
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static inline bool classof(const Instruction *I) {
     return (I->getOpcode() == Instruction::CleanupRet);
   }
   static inline bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }
 
public:
   static inline bool classof(const Instruction *I) {
     return I->getOpcode() == AddrSpaceCast;
   }
   static inline bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }
 };
 
+/// Iterator for visiting all EH pads that an instruction with an unwind
+/// destination may reach by unwinding through its unwind edge and any
+/// ensuing unsplittable blocks, optionally visiting the unsplittable
+/// blocks themselves.  Destinations are visited in depth-first pre-order.
+template <bool SkipUnsplittable> class UnwindDestIterator {
+  /// Construct default iterator, suitable as end() for any iteration.
+  explicit UnwindDestIterator() {}
+
+  /// Construct iterator suitable as begin() for iterating transitive
+  /// unwind dests of an instruction whose immediate unwind dest is
+  /// the given BasicBlock.
+  explicit UnwindDestIterator(BasicBlock *UnwindDest) {
+    visitUnwindDest(UnwindDest);
+  }
+
+  /// CurrentInstr is the first non-PHI of the transitive unwind dest
+  /// at the current position.
+  Instruction *CurrentInstr = nullptr;
+
+  /// If currently visiting a catchpad, CurrentHandler is the handler
+  /// iterator on the parent catchswitch referencing that catchpad.
+  /// Otherwise, CurrentHandler is None.  When visiting a catchswitch
+  /// itself, CurrentInstr is the catchswitch and CurrentHandler is None.
+  llvm::Optional<CatchSwitchInst::handler_iterator> CurrentHandler;
+
+  /// Set the iterator position to the given unwind destination, skipping
+  /// over any unsplittable blocks if SkipUnsplittable is true.
+  /// \param UnwindDest New dest to visit.  May be \p nullptr to set
+  ///                   iterator to end state.
+  void visitUnwindDest(BasicBlock *UnwindDest) {
+    assert(!CurrentHandler);
+    if (!UnwindDest) {
+      CurrentInstr = nullptr;
+      return;
+    }
+    CurrentInstr = UnwindDest->getFirstNonPHI();
+    if (SkipUnsplittable)
+      if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(CurrentInstr))
+        visitFirstHandler(CatchSwitch);
+  }
+
+  /// Begin visiting the catchpads under a catchswitch.
+  void visitFirstHandler(CatchSwitchInst *CatchSwitch) {
+    CurrentHandler = CatchSwitch->handler_begin();
+    CurrentInstr = (**CurrentHandler)->getFirstNonPHI();
+  }
+
+public:
+  BasicBlock *operator*() { return CurrentInstr->getParent(); }
+
+  UnwindDestIterator &operator++() {
+    if (CurrentHandler) {
+      CatchSwitchInst *CatchSwitch =
+          cast<CatchPadInst>(CurrentInstr)->getCatchSwitch();
+      if (++(*CurrentHandler) != CatchSwitch->handler_end()) {
+        CurrentInstr = (**CurrentHandler)->getFirstNonPHI();
+        return *this;
+      }
+      CurrentHandler.reset();
+      visitUnwindDest(CatchSwitch->getUnwindDest());
+      return *this;
+    }
+    if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(CurrentInstr)) {
+      visitFirstHandler(CatchSwitch);
+      return *this;
+    }
+    CurrentInstr = nullptr;
+    return *this;
+  }
+
+  bool operator==(const UnwindDestIterator &Other) const {
+    if (CurrentInstr != Other.CurrentInstr)
+      return false;
+    if (CurrentHandler.hasValue() != Other.CurrentHandler.hasValue())
+      return false;
+    if (CurrentHandler &&
+        (CurrentHandler.getValue() != Other.CurrentHandler.getValue()))
+      return false;
+    return true;
+  }
+
+  bool operator!=(const UnwindDestIterator &Other) const {
+    return !operator==(Other);
+  }
+
+  /// Get the iterator range for visiting transitive unwind destinations of an
+  /// instruction whose immediate unwind destination is \p UnwindDest, in
+  /// depth-first pre-order.
+  /// \param UnwindDest First uwnind destination to visit.  May be null for
+  ///                   empty iteration.
+  static iterator_range<UnwindDestIterator> range(BasicBlock *UnwindDest) {
+    return iterator_range<UnwindDestIterator>(UnwindDestIterator(UnwindDest),
+                                              UnwindDestIterator());
+  }
+};
+
 } // End llvm namespace
 
 #endif

include/llvm/IR/Statepoint.h

public:
 
   /// The statepoint with which this gc.relocate is associated.
   const Instruction *getStatepoint() const {
     const Value *Token = getArgOperand(0);
 
     // This takes care both of relocates for call statepoints and relocates
     // on normal path of invoke statepoint.
     if (!isa<LandingPadInst>(Token)) {
+      assert(!cast<Instruction>(Token)->isEHPad() &&
+             "Funclet pads don't support 1:1 relocate:statepoint mapping");
       return cast<Instruction>(Token);
     }
 
     // This relocate is on exceptional path of an invoke statepoint
     const BasicBlock *InvokeBB =
         cast<Instruction>(Token)->getParent()->getUniquePredecessor();
 
     assert(InvokeBB && "safepoints should have unique landingpads");
StatepointBase<FunTy, InstructionTy, ValueTy, CallSiteTy>::getRelocates()
   for (const User *U : getInstruction()->users())
     if (auto *Relocate = dyn_cast<GCRelocateInst>(U))
       Result.push_back(Relocate);
 
   if (!StatepointCS.isInvoke())
     return Result;
 
   // We need to scan thorough exceptional relocations if it is invoke statepoint
+  const InvokeInst *Invoke = cast<InvokeInst>(getInstruction());
+  if (Invoke->getUnwindDest()->isLandingPad()) {
     LandingPadInst *LandingPad =
         cast<InvokeInst>(getInstruction())->getLandingPadInst();
 
     // Search for gc relocates that are attached to this landingpad.
     for (const User *LandingPadUser : LandingPad->users()) {
       if (auto *Relocate = dyn_cast<GCRelocateInst>(LandingPadUser))
         Result.push_back(Relocate);
     }
+#ifndef NDEBUG
+  } else {
+    for (auto *UnwindDest : Invoke->getTransitiveUnwindDests())
+      for (auto *U : UnwindDest->getFirstNonPHI()->users())
+        assert(!isa<GCRelocateInst>(U) &&
+               "Relocates on funclet EH not supported");
+#endif // NDEBUG
+  }
   return Result;
 }
 }
 
 #endif

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

 static bool ClobberNonLive = true;
 #else
 static bool ClobberNonLive = false;
 #endif
 static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",
                                                   cl::location(ClobberNonLive),
                                                   cl::Hidden);
 
+static cl::opt<bool> SpillOnExceptionPath("rs4gc-spill-on-exception-path",
+                                          cl::Hidden, cl::init(false));
+static cl::opt<bool> SpillOnNormalPath("rs4gc-spill-on-normal-path", cl::Hidden,
+                                       cl::init(false));
+
 static cl::opt<bool>
     AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info",
                                    cl::Hidden, cl::init(true));
 
 /// Should we split vectors of pointers into their individual elements?  This
 /// is known to be buggy, but the alternate implementation isn't yet ready.
 /// This is purely to provide a debugging and dianostic hook until the vector
 /// split is replaced with vector relocations.

 // should not be inspected.
 //
 // In the actual implementation this caches two relations:
 // - The base relation itself (i.e. this pointer is based on that one)
 // - The base defining value relation (i.e. before base_phi insertion)
 // Generally, after the execution of a full findBasePointer call, only the
 // base relation will remain.  Internally, we add a mixture of the two
 // types, then update all the second type to the first type
+typedef DenseMap<Value *, Value *> BaseMapTy;
 typedef DenseMap<Value *, Value *> DefiningValueMapTy;
 typedef DenseSet<Value *> StatepointLiveSetTy;
 typedef DenseMap<AssertingVH<Instruction>, AssertingVH<Value>>
-  RematerializedValueMapTy;
+    ReconstitutedValueMapTy;
+typedef DenseMap<Instruction *, BaseMapTy *> BaseMapMapTy;
 
 struct PartiallyConstructedSafepointRecord {
   /// The set of values known to be live across this safepoint
   StatepointLiveSetTy LiveSet;
 
   /// Mapping from live pointers to a base-defining-value
-  DenseMap<Value *, Value *> PointerToBase;
+  BaseMapTy PointerToBase;
 
   /// The *new* gc.statepoint instruction itself.  This produces the token
   /// that normal path gc.relocates and the gc.result are tied to.
   Instruction *StatepointToken;
 
   /// Instruction to which exceptional gc relocates are attached
   /// Makes it easier to iterate through them during relocationViaAlloca.
   Instruction *UnwindToken;
 
   /// Record live values we are rematerialized instead of relocating.
   /// They are not included into 'LiveSet' field.
-  /// Maps rematerialized copy to it's original value.
-  RematerializedValueMapTy RematerializedValues;
+  /// Maps rematerialized copy to its original value.
+  ReconstitutedValueMapTy RematerializedValues;
+
+  /// Record fills where we spilled a live value instead of relocating.
+  /// They are not included into 'LiveSet' field.
+  /// Maps loaded copy to its original value.
+  ReconstitutedValueMapTy ReloadedValues;
+
+  /// Record spill slots holding live values spilled across this statepoint.
+  /// These need to be reported to the GC for relocation.
+  SmallVector<Value *, 16> SpillSlots;
 };
 }
 
 static ArrayRef<Use> GetDeoptBundleOperands(ImmutableCallSite CS) {
   Optional<OperandBundleUse> DeoptBundle =
       CS.getOperandBundle(LLVMContext::OB_deopt);
 
   if (!DeoptBundle.hasValue()) {
     assert(AllowStatepointWithNoDeoptInfo &&
            "Found non-leaf call without deopt info!");
     return None;
   }
 
   return DeoptBundle.getValue().Inputs;
 }
 
 /// Compute the live-in set for every basic block in the function
 static void computeLiveInValues(DominatorTree &DT, Function &F,
-                                GCPtrLivenessData &Data);
+                                GCPtrLivenessData &Data,
+                                const BaseMapMapTy *BaseMaps = nullptr);
 
 /// Given results from the dataflow liveness computation, find the set of live
 /// Values at a particular instruction.
-static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,
+static void findLiveSetAtStatepoint(CallSite Statepoint,
+                                    GCPtrLivenessData &Data,
+                                    const BaseMapMapTy *BaseMaps,
                                     StatepointLiveSetTy &out);
 
 // TODO: Once we can get to the GCStrategy, this becomes
 // Optional<bool> isGCManagedPointer(const Type *Ty) const override {
 
 static bool isGCPointerType(Type *T) {
   if (auto *PT = dyn_cast<PointerType>(T))
     // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
     // GC managed heap.  We know that a pointer into this heap needs to be

 // Return the name of the value suffixed with the provided value, or if the
 // value didn't have a name, the default value specified.
 static std::string suffixed_name_or(Value *V, StringRef Suffix,
                                     StringRef DefaultName) {
   return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.str();
 }
 
 // Conservatively identifies any definitions which might be live at the
-// given instruction. The  analysis is performed immediately before the
-// given instruction. Values defined by that instruction are not considered
-// live.  Values used by that instruction are considered live.
+// given instruction. Deopt arguments are treated specially, and considered
+// live at the given parse point even though they appear in its argument
+// list, to ensure they are reported/relocated.
 static void analyzeParsePointLiveness(
     DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData,
     const CallSite &CS, PartiallyConstructedSafepointRecord &result) {
-  Instruction *inst = CS.getInstruction();
 
   StatepointLiveSetTy LiveSet;
-  findLiveSetAtInst(inst, OriginalLivenessData, LiveSet);
+  assert(result.PointerToBase.empty() &&
+         "Not expecting bases to be computed yet");
+  findLiveSetAtStatepoint(CS, OriginalLivenessData, nullptr, LiveSet);
 
   if (PrintLiveSet) {
     // Note: This output is used by several of the test cases
     // The order of elements in a set is not stable, put them in a vec and sort
     // by name
     SmallVector<Value *, 64> Temp;
     Temp.insert(Temp.end(), LiveSet.begin(), LiveSet.end());
     std::sort(Temp.begin(), Temp.end(), order_by_name);
static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache,
   }
 
   result.PointerToBase = PointerToBase;
 }
 
 /// Given an updated version of the dataflow liveness results, update the
 /// liveset and base pointer maps for the call site CS.
 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
+                                  const BaseMapMapTy &BaseMaps,
                                   const CallSite &CS,
-                                  PartiallyConstructedSafepointRecord &result);
+                                  PartiallyConstructedSafepointRecord &Info);
 
 static void recomputeLiveInValues(
     Function &F, DominatorTree &DT, ArrayRef<CallSite> toUpdate,
     MutableArrayRef<struct PartiallyConstructedSafepointRecord> records) {
   // TODO-PERF: reuse the original liveness, then simply run the dataflow
   // again.  The old values are still live and will help it stabilize quickly.
   GCPtrLivenessData RevisedLivenessData;
-  computeLiveInValues(DT, F, RevisedLivenessData);
+  // The liveness walk needs to recognize when it visits a statepoint, and
+  // add to the live gens the base pointers of any derived pointers which
+  // are live across said statepoint.  Pass it a map it can use to detect
+  // and compute this, whose keys are the statepoint instructions and
+  // whose values point to their PointerToBase maps.
+  BaseMapMapTy BaseMaps;
+  for (size_t I = 0; I < records.size(); I++) {
+    Instruction *Statepoint = toUpdate[I].getInstruction();
+    BaseMaps[Statepoint] = &records[I].PointerToBase;
+  }
+  computeLiveInValues(DT, F, RevisedLivenessData, &BaseMaps);
   for (size_t i = 0; i < records.size(); i++) {
     struct PartiallyConstructedSafepointRecord &info = records[i];
     const CallSite &CS = toUpdate[i];
-    recomputeLiveInValues(RevisedLivenessData, CS, info);
+    recomputeLiveInValues(RevisedLivenessData, BaseMaps, CS, info);
   }
 }
 
 // When inserting gc.relocate and gc.result calls, we need to ensure there are
 // no uses of the original value / return value between the gc.statepoint and
 // the gc.relocate / gc.result call.  One case which can arise is a phi node
 // starting one of the successor blocks.  We also need to be able to insert the
 // gc.relocates only on the path which goes through the statepoint.  We might
void doReplacement() {
 
     if (NewI)
       OldI->replaceAllUsesWith(NewI);
     OldI->eraseFromParent();
   }
 };
 }
 
+// Generate spill slots for values that get spilled rather than
+// relocated/rematerialized.
+typedef DenseMap<Value *, AllocaInst *> SpillMapTy;
+typedef DenseMap<BasicBlock *, SmallPtrSet<Value *, 4>> FillMapTy;
+static void StabilizeOrder(SmallVectorImpl<Value *> &LiveVec);
+static void generateSpills(SpillMapTy &SpillMap, FillMapTy &FillMap,
+                           CallSite CS,
+                           PartiallyConstructedSafepointRecord &Record) {
+  assert(SpillOnNormalPath || SpillOnExceptionPath);
+
+  // Calls have no exception path.
+  if (CS.isCall() && !SpillOnNormalPath)
+    return;
+
+  Function *F = CS.getInstruction()->getParent()->getParent();
+  Instruction *AllocaInsertBefore = &F->getEntryBlock().front();
+
+  // Copy the live set to a vector for "determinism" (see FIXME at
+  // StabilizeOrder).
+  // Convert to vector for efficient cross referencing.
+  SmallVector<Value *, 64> LiveVec;
+  LiveVec.reserve(Record.LiveSet.size());
+  LiveVec.append(Record.LiveSet.begin(), Record.LiveSet.end());
+  StabilizeOrder(LiveVec);
+
+  // First, generate spills.
+  // TODO: Be smarter about where spills are inserted to avoid redundant
+  // ones (which requires detecting liverange interferences for the PHI case,
+  // and ideally would consult profile weights to minimize store frequency).
+  Instruction *SpillInsertBefore = CS.getInstruction();
+  auto generateSpill = [&](Value *Var, Value *Val) {
+    AllocaInst *&SpillSlot = SpillMap[Var];
+    // When generating new spill slots, walk AllocaInsertBefore back
+    // to avoid mixing with stores if the first instruction in the
+    // function happens to be a statepoint.
+    if (!SpillSlot)
+      AllocaInsertBefore = SpillSlot =
+          new AllocaInst(Var->getType(), suffixed_name_or(Var, ".gc_spill", ""),
+                         AllocaInsertBefore);
+    new StoreInst(Val, SpillSlot, SpillInsertBefore);
+    Record.SpillSlots.push_back(SpillSlot);
+  };
+
+  // TODO: Make the liveness information in the record more verbose so for
+  // invokes we can:
+  // 1) If spilling only across exception edges, spill only the values live
+  //    into the EH pad(s).
+  // 2) If a value is live only until a phi source, spill that value just
+  //    for the phi, instead of once for the phi and once for itself.
+
+  // Spill all live-across values.
+  for (Value *Var : LiveVec)
+    generateSpill(Var, Var);
+
+  // Spill any necessary incoming PHI values
+  MapVector<Value *, Value *> IncomingPHIValueMap;
+  if (CS.isInvoke() && SpillOnExceptionPath) {
+    auto *Invoke = cast<InvokeInst>(CS.getInstruction());
+    BasicBlock *Pred = Invoke->getParent();
+    for (BasicBlock *Pad : Invoke->getTransitiveUnwindDests<false>()) {
+      for (auto I = Pad->begin(); auto *PHI = dyn_cast<PHINode>(&*I); ++I) {
+        // Find the value to store for this PHI
+        Value *IncomingValue = PHI->getIncomingValueForBlock(Pred);
+        // If the incoming value was itself a PHI we've walked over,
+        // recurse to that incoming value
+        auto MapIter = IncomingPHIValueMap.find(IncomingValue);
+        if (MapIter != IncomingPHIValueMap.end())
+          IncomingValue = MapIter->second;
+        // Record the incoming value in case we see a use of it in
+        // a subsequent PHI.
+        IncomingPHIValueMap[PHI] = IncomingValue;
+        // Generate the spill
+        generateSpill(PHI, IncomingValue);
+      }
+      // Update pred if we're going to visit this block's successors,
+      // which we'll do iff it's unsplittable.
+      if (isa<TerminatorInst>(Pad->getFirstNonPHI()))
+        Pred = Pad;
+    }
+  }
+
+  // Next, generate fills.
+  auto generateFill = [&](Value *Var, Instruction *LoadInsertBefore) {
+    auto *Fill =
+        new LoadInst(SpillMap[Var], suffixed_name_or(Var, ".gc_reload", ""),
+                     LoadInsertBefore);
+    Record.ReloadedValues[Fill] = Var;
+  };
+
+  // Generate normal-path fills if necessary
+  if (SpillOnNormalPath) {
+    Instruction *LoadInsertBefore;
+    if (CS.isCall())
+      LoadInsertBefore = CS.getInstruction()->getNextNode();
+    else
+      LoadInsertBefore =
+          &cast<InvokeInst>(CS.getInstruction())->getNormalDest()->front();
+    assert(!isa<PHINode>(LoadInsertBefore) &&
+           "Expected normal critical edges to be split");
+    for (Value *Var : LiveVec)
+      generateFill(Var, LoadInsertBefore);
+  }
+
+  // Generate exception-path fills if necessary
+  if (CS.isInvoke() && SpillOnExceptionPath) {
+    auto ensureFill = [&](Value *Var, BasicBlock *Pad) {
+      // Don't redundantly reload the same var on behalf
+      // of multiple invoke predecessors.
+      auto &PadFills = FillMap[Pad];
+      if (!PadFills.insert(Var).second)
+        return;
+      generateFill(Var, &*Pad->getFirstInsertionPt());
+    };
+    auto *Invoke = cast<InvokeInst>(CS.getInstruction());
+    for (BasicBlock *Pad : Invoke->getTransitiveUnwindDests()) {
+      for (Value *Var : LiveVec)
+        ensureFill(Var, Pad);
+      for (const auto &IncomingValuePair : IncomingPHIValueMap)
+        ensureFill(IncomingValuePair.first, Pad);
+    }
+  }
+
+  // If we've spilled on all paths, we don't need to generate any relocates,
+  // so clear the live set for this statepoint.
+  if (SpillOnNormalPath && (CS.isCall() || SpillOnExceptionPath))
+    Record.LiveSet.clear();
+}
+
 static void
 makeStatepointExplicitImpl(const CallSite CS, /* to replace */
                            const SmallVectorImpl<Value *> &BasePtrs,
                            const SmallVectorImpl<Value *> &LiveVariables,
                            PartiallyConstructedSafepointRecord &Result,
                            std::vector<DeferredReplacement> &Replacements) {
   assert(BasePtrs.size() == LiveVariables.size());
 
   // Then go ahead and use the builder do actually do the inserts.  We insert
   // immediately before the previous instruction under the assumption that all
   // arguments will be available here.  We can't insert afterwards since we may
   // be replacing a terminator.
   Instruction *InsertBefore = CS.getInstruction();
   IRBuilder<> Builder(InsertBefore);
 
-  ArrayRef<Value *> GCArgs(LiveVariables);
+  // The gc args are the concatenation of the live variables and the spill
+  // slots.
+  ArrayRef<Value *> GCArgs;
+  SmallVector<Value *, 64> ConcatenatedArgs;
+  if (Result.SpillSlots.empty()) {
+    GCArgs = ArrayRef<Value *>(LiveVariables);
+  } else if (LiveVariables.empty()) {
+    GCArgs = ArrayRef<Value *>(Result.SpillSlots);
+  } else {
+    ConcatenatedArgs.append(LiveVariables.begin(), LiveVariables.end());
+    ConcatenatedArgs.append(Result.SpillSlots.begin(), Result.SpillSlots.end());
+    GCArgs = ArrayRef<Value *>(ConcatenatedArgs);
+  }
   uint64_t StatepointID = 0xABCDEF00;
   uint32_t NumPatchBytes = 0;
   uint32_t Flags = uint32_t(StatepointFlags::None);
 
   ArrayRef<Use> CallArgs(CS.arg_begin(), CS.arg_end());
   ArrayRef<Use> DeoptArgs = GetDeoptBundleOperands(CS);
   ArrayRef<Use> TransitionArgs;
   if (auto TransitionBundle =
       CS.getOperandBundle(LLVMContext::OB_gc_transition)) {
     Flags |= uint32_t(StatepointFlags::GCTransition);
     TransitionArgs = TransitionBundle->Inputs;
   }
 
   Value *CallTarget = CS.getCalledValue();
   AttributeSet OriginalAttrs = CS.getAttributes();
   Attribute AttrID = OriginalAttrs.getAttribute(AttributeSet::FunctionIndex,
                                                 "statepoint-id");
   if (AttrID.isStringAttribute())
     AttrID.getValueAsString().getAsInteger(10, StatepointID);
 
   Attribute AttrNumPatchBytes = OriginalAttrs.getAttribute(
     AttributeSet::FunctionIndex, "statepoint-num-patch-bytes");
   if (AttrNumPatchBytes.isStringAttribute())
     AttrNumPatchBytes.getValueAsString().getAsInteger(10, NumPatchBytes);
 
   // Create the statepoint given all the arguments
   Instruction *Token = nullptr;
   AttributeSet ReturnAttrs;
   if (CS.isCall()) {
     CallInst *ToReplace = cast<CallInst>(CS.getInstruction());
     CallInst *Call = Builder.CreateGCStatepointCall(
         StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,
         TransitionArgs, DeoptArgs, GCArgs, "safepoint_token");
 
     Call->setTailCall(ToReplace->isTailCall());
     Call->setCallingConv(ToReplace->getCallingConv());
 
     // Currently we will fail on parameter attributes and on certain
     // function attributes.
     AttributeSet NewAttrs = legalizeCallAttributes(ToReplace->getAttributes());
     // In case if we can handle this set of attributes - set up function attrs
     // directly on statepoint and return attrs later for gc_result intrinsic.
     Call->setAttributes(NewAttrs.getFnAttributes());
     ReturnAttrs = NewAttrs.getRetAttributes();
 
if (CS.isCall()) {
     // In case if we can handle this set of attributes - set up function attrs
     // directly on statepoint and return attrs later for gc_result intrinsic.
     Invoke->setAttributes(NewAttrs.getFnAttributes());
     ReturnAttrs = NewAttrs.getRetAttributes();
 
     Token = Invoke;
 
     // Generate gc relocates in exceptional path
-    BasicBlock *UnwindBlock = ToReplace->getUnwindDest();
+    if (SpillOnExceptionPath) {
+      Result.UnwindToken = nullptr;
+    } else {
+      for (BasicBlock *UnwindBlock : ToReplace->getTransitiveUnwindDests()) {
         assert(!isa<PHINode>(UnwindBlock->begin()) &&
                UnwindBlock->getUniquePredecessor() &&
                "can't safely insert in this block!");
 
         Builder.SetInsertPoint(&*UnwindBlock->getFirstInsertionPt());
         Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
 
         // Attach exceptional gc relocates to the landingpad.
         Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();
+        assert(Result.UnwindToken == nullptr &&
+               "Cannot report multiple unwind tokens");
         Result.UnwindToken = ExceptionalToken;
 
         const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx();
-    CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, ExceptionalToken,
-                      Builder);
+        CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs,
+                          ExceptionalToken, Builder);
+      }
+    }
 
     // Generate gc relocates and returns for normal block
     BasicBlock *NormalDest = ToReplace->getNormalDest();
     assert(!isa<PHINode>(NormalDest->begin()) &&
            NormalDest->getUniquePredecessor() &&
            "can't safely insert in this block!");
 
     Builder.SetInsertPoint(&*NormalDest->getFirstInsertionPt());
makeStatepointExplicitImpl(const CallSite CS, /* to replace */
 
   Result.StatepointToken = Token;
 
   // Second, create a gc.relocate for every live variable
   const unsigned LiveStartIdx = Statepoint(Token).gcArgsStartIdx();
   CreateGCRelocates(LiveVariables, LiveStartIdx, BasePtrs, Token, Builder);
 }
 
+// FIXME: This gives nondeterministic output when values are nameless
+static void StabilizeOrder(SmallVectorImpl<Value *> &LiveVec) {
+  std::sort(LiveVec.begin(), LiveVec.end(), [](const Value *L, const Value *R) {
+    return L->getName() < R->getName();
+  });
+}
+// FIXME: This gives nondeterministic output when values are nameless
 static void StabilizeOrder(SmallVectorImpl<Value *> &BaseVec,
                            SmallVectorImpl<Value *> &LiveVec) {
   assert(BaseVec.size() == LiveVec.size());
 
   struct BaseDerivedPair {
     Value *Base;
     Value *Derived;
   };

 
 #ifndef NDEBUG
     VisitedLiveValues.insert(OriginalValue);
 #endif
   }
 }
 
 // Helper function for the "relocationViaAlloca". Similar to the
-// "insertRelocationStores" but works for rematerialized values.
+// "insertRelocationStores" but works for reconstituted values
+// (i.e. rematerialized values and reloads of spilled values).
 static void
-insertRematerializationStores(
-  RematerializedValueMapTy RematerializedValues,
+insertReconstitutionStores(const ReconstitutedValueMapTy &ReconstitutedValues,
                            DenseMap<Value *, Value *> &AllocaMap,
                            DenseSet<Value *> &VisitedLiveValues) {
 
-  for (auto RematerializedValuePair: RematerializedValues) {
-    Instruction *RematerializedValue = RematerializedValuePair.first;
-    Value *OriginalValue = RematerializedValuePair.second;
+  for (auto ReconstitutedValuePair : ReconstitutedValues) {
+    Instruction *ReconstitutedValue = ReconstitutedValuePair.first;
+    Value *OriginalValue = ReconstitutedValuePair.second;
 
     assert(AllocaMap.count(OriginalValue) &&
-           "Can not find alloca for rematerialized value");
+           "Can not find alloca for reconstituted value");
     Value *Alloca = AllocaMap[OriginalValue];
 
-    StoreInst *Store = new StoreInst(RematerializedValue, Alloca);
-    Store->insertAfter(RematerializedValue);
+    StoreInst *Store = new StoreInst(ReconstitutedValue, Alloca);
+    Store->insertAfter(ReconstitutedValue);
 
 #ifndef NDEBUG
     VisitedLiveValues.insert(OriginalValue);
 #endif
   }
 }
 
 /// Do all the relocation update via allocas and mem2reg
if (isa<AllocaInst>(*I))
       InitialAllocaNum++;
 #endif
 
   // TODO-PERF: change data structures, reserve
   DenseMap<Value *, Value *> AllocaMap;
   SmallVector<AllocaInst *, 200> PromotableAllocas;
   // Used later to chack that we have enough allocas to store all values
   std::size_t NumRematerializedValues = 0;
+  std::size_t NumSpilledValues = 0;
   PromotableAllocas.reserve(Live.size());
 
   // Emit alloca for "LiveValue" and record it in "allocaMap" and
   // "PromotableAllocas"
   auto emitAllocaFor = [&](Value *LiveValue) {
     AllocaInst *Alloca = new AllocaInst(LiveValue->getType(), "",
                                         F.getEntryBlock().getFirstNonPHI());
     AllocaMap[LiveValue] = Alloca;
     PromotableAllocas.push_back(Alloca);
   };
 
   // Emit alloca for each live gc pointer
   for (Value *V : Live)
     emitAllocaFor(V);
 
-  // Emit allocas for rematerialized values
-  for (const auto &Info : Records)
+  // Emit allocas for reconstituted values
+  for (const auto &Info : Records) {
     for (auto RematerializedValuePair : Info.RematerializedValues) {
       Value *OriginalValue = RematerializedValuePair.second;
       if (AllocaMap.count(OriginalValue) != 0)
         continue;
 
       emitAllocaFor(OriginalValue);
       ++NumRematerializedValues;
     }
 
+    for (auto SpilledValuePair : Info.ReloadedValues) {
+      Value *OriginalValue = SpilledValuePair.second;
+      if (AllocaMap.count(OriginalValue) != 0)
+        continue;
+
+      emitAllocaFor(OriginalValue);
+      ++NumSpilledValues;
+    }
+  }
+
   // The next two loops are part of the same conceptual operation.  We need to
   // insert a store to the alloca after the original def and at each
   // redefinition.  We need to insert a load before each use.  These are split
   // into distinct loops for performance reasons.
 
   // Update gc pointer after each statepoint: either store a relocated value or
   // null (if no relocated value was found for this gc pointer and it is not a
   // gc_result).  This must happen before we update the statepoint with load of
   // alloca otherwise we lose the link between statepoint and old def.
   for (const auto &Info : Records) {
     Value *Statepoint = Info.StatepointToken;
 
     // This will be used for consistency check
     DenseSet<Value *> VisitedLiveValues;
 
     // Insert stores for normal statepoint gc relocates
     insertRelocationStores(Statepoint->users(), AllocaMap, VisitedLiveValues);
 
     // In case if it was invoke statepoint
     // we will insert stores for exceptional path gc relocates.
-    if (isa<InvokeInst>(Statepoint)) {
+    if (isa<InvokeInst>(Statepoint) && Info.UnwindToken) {
       insertRelocationStores(Info.UnwindToken->users(), AllocaMap,
                              VisitedLiveValues);
     }
 
     // Do similar thing with rematerialized values
-    insertRematerializationStores(Info.RematerializedValues, AllocaMap,
-                                  VisitedLiveValues);
+    insertReconstitutionStores(Info.RematerializedValues, AllocaMap,
+                               VisitedLiveValues);
+
+    // And with reloads
+    insertReconstitutionStores(Info.ReloadedValues, AllocaMap,
 
     if (ClobberNonLive) {
       // As a debugging aid, pretend that an unrelocated pointer becomes null at
       // the gc.statepoint.  This will turn some subtle GC problems into
       // slightly easier to debug SEGVs.  Note that on large IR files with
       // lots of gc.statepoints this is extremely costly both memory and time
       // wise.
       SmallVector<AllocaInst *, 64> ToClobber;
       for (auto Pair : AllocaMap) {
         Value *Def = Pair.first;
         AllocaInst *Alloca = cast<AllocaInst>(Pair.second);
if (ClobberNonLive) {
           Store->insertBefore(IP);
         }
       };
 
       // Insert the clobbering stores.  These may get intermixed with the
       // gc.results and gc.relocates, but that's fine.
       if (auto II = dyn_cast<InvokeInst>(Statepoint)) {
         InsertClobbersAt(&*II->getNormalDest()->getFirstInsertionPt());
-        InsertClobbersAt(&*II->getUnwindDest()->getFirstInsertionPt());
+        for (BasicBlock *UnwindDest : II->getTransitiveUnwindDests())
+          InsertClobbersAt(&*UnwindDest->getFirstInsertionPt());
       } else {
         InsertClobbersAt(cast<Instruction>(Statepoint)->getNextNode());
       }
     }
   }
 
   // Update use with load allocas and add store for gc_relocated.
   for (auto Pair : AllocaMap) {
if (Instruction *Inst = dyn_cast<Instruction>(Def)) {
         Store->insertAfter(Inst);
       }
     } else {
       assert(isa<Argument>(Def));
       Store->insertAfter(cast<Instruction>(Alloca));
     }
   }
 
-  assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&
+  assert(PromotableAllocas.size() ==
+             Live.size() + NumRematerializedValues + NumSpilledValues &&
          "we must have the same allocas with lives");
   if (!PromotableAllocas.empty()) {
     // Apply mem2reg to promote alloca to SSA
     PromoteMemToReg(PromotableAllocas, DT);
   }
 
 #ifndef NDEBUG
   for (auto &I : F.getEntryBlock())
     if (isa<AllocaInst>(I))
       InitialAllocaNum--;
   assert(InitialAllocaNum == 0 && "We must not introduce any extra allocas");
 #endif
 }
 
 /// Implement a unique function which doesn't require we sort the input
 /// vector.  Doing so has the effect of changing the output of a couple of
 /// tests in ways which make them less useful in testing fused safepoints.
 template <typename T> static void unique_unsorted(SmallVectorImpl<T> &Vec) {
   SmallSet<T, 8> Seen;
   Vec.erase(std::remove_if(Vec.begin(), Vec.end(), [&](const T &V) {
               return !Seen.insert(V).second;
             }), Vec.end());
 }
 
-/// Insert holders so that each Value is obviously live through the entire
-/// lifetime of the call.
-static void insertUseHolderAfter(CallSite &CS, const ArrayRef<Value *> Values,
-                                 SmallVectorImpl<CallInst *> &Holders) {
-  if (Values.empty())
-    // No values to hold live, might as well not insert the empty holder
-    return;
-
-  Module *M = CS.getInstruction()->getModule();
-  // Use a dummy vararg function to actually hold the values live
-  Function *Func = cast<Function>(M->getOrInsertFunction(
-      "__tmp_use", FunctionType::get(Type::getVoidTy(M->getContext()), true)));
-  if (CS.isCall()) {
-    // For call safepoints insert dummy calls right after safepoint
-    Holders.push_back(CallInst::Create(Func, Values, "",
-                                       &*++CS.getInstruction()->getIterator()));
-    return;
-  }
-  // For invoke safepooints insert dummy calls both in normal and
-  // exceptional destination blocks
-  auto *II = cast<InvokeInst>(CS.getInstruction());
-  Holders.push_back(CallInst::Create(
-      Func, Values, "", &*II->getNormalDest()->getFirstInsertionPt()));
-  Holders.push_back(CallInst::Create(
-      Func, Values, "", &*II->getUnwindDest()->getFirstInsertionPt()));
-}
-
 static void findLiveReferences(
     Function &F, DominatorTree &DT, ArrayRef<CallSite> toUpdate,
     MutableArrayRef<struct PartiallyConstructedSafepointRecord> records) {
   GCPtrLivenessData OriginalLivenessData;
   computeLiveInValues(DT, F, OriginalLivenessData);
   for (size_t i = 0; i < records.size(); i++) {
     struct PartiallyConstructedSafepointRecord &info = records[i];
     const CallSite &CS = toUpdate[i];
if (CS.isCall()) {
       assert(InsertBefore);
       Instruction *RematerializedValue = rematerializeChain(InsertBefore);
       Info.RematerializedValues[RematerializedValue] = LiveValue;
     } else {
       InvokeInst *Invoke = cast<InvokeInst>(CS.getInstruction());
 
       Instruction *NormalInsertBefore =
           &*Invoke->getNormalDest()->getFirstInsertionPt();
-      Instruction *UnwindInsertBefore =
-          &*Invoke->getUnwindDest()->getFirstInsertionPt();
-
       Instruction *NormalRematerializedValue =
           rematerializeChain(NormalInsertBefore);
+      Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
+
+      for (BasicBlock *UnwindDest : Invoke->getTransitiveUnwindDests()) {
+        Instruction *UnwindInsertBefore = &*UnwindDest->getFirstInsertionPt();
         Instruction *UnwindRematerializedValue =
             rematerializeChain(UnwindInsertBefore);
-
-      Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
         Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
       }
     }
+  }
 
   // Remove rematerializaed values from the live set
   for (auto LiveValue: LiveValuesToBeDeleted) {
     Info.LiveSet.erase(LiveValue);
   }
 }
 
 static bool insertParsePoints(Function &F, DominatorTree &DT,
                               TargetTransformInfo &TTI,
                               SmallVectorImpl<CallSite> &ToUpdate) {
 #ifndef NDEBUG
   // sanity check the input
   std::set<CallSite> Uniqued;
   Uniqued.insert(ToUpdate.begin(), ToUpdate.end());
   assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");
 
   for (CallSite CS : ToUpdate)
     assert(CS.getInstruction()->getFunction() == &F);
 #endif
 
   // When inserting gc.relocates for invokes, we need to be able to insert at
   // the top of the successor blocks.  See the comment on
-  // normalForInvokeSafepoint on exactly what is needed.  Note that this step
+  // normalizeForInvokeSafepoint on exactly what is needed.  Note that this step
   // may restructure the CFG.
   for (CallSite CS : ToUpdate) {
     if (!CS.isInvoke())
       continue;
     auto *II = cast<InvokeInst>(CS.getInstruction());
     normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT);
+    if (!SpillOnExceptionPath)
       normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT);
   }
 
-  // A list of dummy calls added to the IR to keep various values obviously
-  // live in the IR.  We'll remove all of these when done.
-  SmallVector<CallInst *, 64> Holders;
-
-  // Insert a dummy call with all of the arguments to the vm_state we'll need
-  // for the actual safepoint insertion.  This ensures reference arguments in
-  // the deopt argument list are considered live through the safepoint (and
-  // thus makes sure they get relocated.)
-  for (CallSite CS : ToUpdate) {
-    SmallVector<Value *, 64> DeoptValues;
-
-    for (Value *Arg : GetDeoptBundleOperands(CS)) {
-      assert(!isUnhandledGCPointerType(Arg->getType()) &&
-             "support for FCA unimplemented");
-      if (isHandledGCPointerType(Arg->getType()))
-        DeoptValues.push_back(Arg);
-    }
-
-    insertUseHolderAfter(CS, DeoptValues, Holders);
-  }
-
   SmallVector<PartiallyConstructedSafepointRecord, 64> Records(ToUpdate.size());
 
   // A) Identify all gc pointers which are statically live at the given call
   // site.
   findLiveReferences(F, DT, ToUpdate, Records);
 
   // B) Find the base pointers for each live pointer
   /* scope for caching */ {
     // Cache the 'defining value' relation used in the computation and
     // insertion of base phis and selects.  This ensures that we don't insert
     // large numbers of duplicate base_phis.
     DefiningValueMapTy DVCache;
 
     for (size_t i = 0; i < Records.size(); i++) {
       PartiallyConstructedSafepointRecord &info = Records[i];
       findBasePointers(DT, DVCache, ToUpdate[i], info);
     }
   } // end of cache scope
 
-  // The base phi insertion logic (for any safepoint) may have inserted new
+  // By selecting base pointers, we've effectively inserted new uses, because
+  // the base phi insertion logic (for any safepoint) may have inserted new
   // instructions which are now live at some safepoint.  The simplest such
   // example is:
   // loop:
   //   phi a  <-- will be a new base_phi here
   //   safepoint 1 <-- that needs to be live here
   //   gep a + 1
   //   safepoint 2
   //   br loop
-  // We insert some dummy calls after each safepoint to definitely hold live
-  // the base pointers which were identified for that safepoint.  We'll then
-  // ask liveness for _every_ base inserted to see what is now live.  Then we
-  // remove the dummy calls.
-  Holders.reserve(Holders.size() + Records.size());
-  for (size_t i = 0; i < Records.size(); i++) {
-    PartiallyConstructedSafepointRecord &Info = Records[i];
-
-    SmallVector<Value *, 128> Bases;
-    for (auto Pair : Info.PointerToBase)
-      Bases.push_back(Pair.second);
-
-    insertUseHolderAfter(ToUpdate[i], Bases, Holders);
-  }
-
-  // By selecting base pointers, we've effectively inserted new uses. Thus, we
-  // need to rerun liveness.  We may *also* have inserted new defs, but that's
-  // not the key issue.
+  // Thus, we need to rerun liveness.  We may *also* have inserted new defs,
+  // but that's not the key issue.
   recomputeLiveInValues(F, DT, ToUpdate, Records);
 
   if (PrintBasePointers) {
     for (auto &Info : Records) {
       errs() << "Base Pairs: (w/Relocation)\n";
       for (auto Pair : Info.PointerToBase) {
         errs() << " derived ";
         Pair.first->printAsOperand(errs(), false);
#endif
   // Note that the relocation placement code relies on this filtering for
   // correctness as it expects the base to be in the liveset, which isn't true
   // if the base is constant.
   for (auto &Info : Records)
     for (auto &BasePair : Info.PointerToBase)
       if (isa<Constant>(BasePair.second))
         Info.LiveSet.erase(BasePair.first);
 
-  for (CallInst *CI : Holders)
-    CI->eraseFromParent();
-
-  Holders.clear();
-
   // Do a limited scalarization of any live at safepoint vector values which
   // contain pointers.  This enables this pass to run after vectorization at
   // the cost of some possible performance loss.  Note: This is known to not
   // handle updating of the side tables correctly which can lead to relocation
   // bugs when the same vector is live at multiple statepoints.  We're in the
   // process of implementing the alternate lowering - relocating the
   // vector-of-pointers as first class item and updating the backend to
   // understand that - but that's not yet complete.  
   if (UseVectorSplit)
     for (size_t i = 0; i < Records.size(); i++) {
       PartiallyConstructedSafepointRecord &Info = Records[i];
       Instruction *Statepoint = ToUpdate[i].getInstruction();
       splitVectorValues(cast<Instruction>(Statepoint), Info.LiveSet,
                         Info.PointerToBase, DT);
     }
 
   // In order to reduce live set of statepoint we might choose to rematerialize
   // some values instead of relocating them. This is purely an optimization and
   // does not influence correctness.
   for (size_t i = 0; i < Records.size(); i++)
     rematerializeLiveValues(ToUpdate[i], Records[i], TTI);
 
+  // Generate spills/fills dictated by the strategy.
+  if (SpillOnNormalPath || SpillOnExceptionPath) {
+    SpillMapTy SpillMap;
+    FillMapTy FillMap;
+    for (size_t I = 0; I < Records.size(); ++I)
+      generateSpills(SpillMap, FillMap, ToUpdate[I], Records[I]);
+  }
+
   // We need this to safely RAUW and delete call or invoke return values that
   // may themselves be live over a statepoint.  For details, please see usage in
   // makeStatepointExplicitImpl.
   std::vector<DeferredReplacement> Replacements;
 
   // Now run through and replace the existing statepoints with new ones with
   // the live variables listed.  We do not yet update uses of the values being
   // relocated. We have references to live variables that need to
#endif
   SmallVector<Value *, 128> Live;
   for (size_t i = 0; i < Records.size(); i++) {
     PartiallyConstructedSafepointRecord &Info = Records[i];
 
     // We can't simply save the live set from the original insertion.  One of
     // the live values might be the result of a call which needs a safepoint.
     // That Value* no longer exists and we need to use the new gc_result.
     // Thankfully, the live set is embedded in the statepoint (and updated), so
-    // we just grab that.
+    // we just grab that.  The only bit of trickery is that the "gc args" of
+    // the statepoint are the concatenation of the relocated values (which need
+    // to be inserted in the "live" set and the spill slots for spilled values
+    // (which should *not* be inserted in the "live" set), so we have to find
+    // the split point.
     Statepoint Statepoint(Info.StatepointToken);
-    Live.insert(Live.end(), Statepoint.gc_args_begin(),
-                Statepoint.gc_args_end());
+    auto LiveArgsBegin = Statepoint.gc_args_begin();
+    auto GcArgsEnd = Statepoint.gc_args_end();
+    auto LiveArgsEnd = LiveArgsBegin;
+    while (LiveArgsEnd != GcArgsEnd && !isa<AllocaInst>(*LiveArgsEnd))
+      ++LiveArgsEnd;
+    Live.insert(Live.end(), LiveArgsBegin, LiveArgsEnd);
 #ifndef NDEBUG
     // Do some basic sanity checks on our liveness results before performing
     // relocation.  Relocation can and will turn mistakes in liveness results
     // into non-sensical code which is must harder to debug.
     // TODO: It would be nice to test consistency as well
     assert(DT.isReachableFromEntry(Info.StatepointToken->getParent()) &&
            "statepoint must be reachable or liveness is meaningless");
     for (Value *V : Statepoint.gc_args()) {
#endif
   }
   unique_unsorted(Live);
 
 #ifndef NDEBUG
   // sanity check
   for (auto *Ptr : Live)
     assert(isHandledGCPointerType(Ptr->getType()) &&
            "must be a gc pointer type");
 #endif
 
   relocationViaAlloca(F, DT, Live, Records);
   return !Records.empty();
 }
 
 // Handles both return values and arguments for Functions and CallSites.
 template <typename AttrHolder>
 static void RemoveNonValidAttrAtIndex(LLVMContext &Ctx, AttrHolder &AH,
                                       unsigned Index) {
   AttrBuilder R;

 }
 
 // liveness computation via standard dataflow
 // -------------------------------------------------------------------
 
 // TODO: Consider using bitvectors for liveness, the set of potentially
 // interesting values should be small and easy to pre-compute.
 
+/// Add the base pointers from the given base map to the given live set.
+static void insertBases(BaseMapTy &BaseMap, StatepointLiveSetTy &LiveSet) {
+  for (auto &Pair : BaseMap)
+    LiveSet.insert(Pair.second);
+}
+
 /// Compute the live-in set for the location rbegin starting from
 /// the live-out set of the basic block
 static void computeLiveInValues(BasicBlock::reverse_iterator rbegin,
                                 BasicBlock::reverse_iterator rend,
-                                DenseSet<Value *> &LiveTmp) {
+                                const BaseMapMapTy *BaseMaps,
+                                StatepointLiveSetTy &LiveTmp) {
 
   for (BasicBlock::reverse_iterator ritr = rbegin; ritr != rend; ritr++) {
     Instruction *I = &*ritr;
 
     // KILL/Def - Remove this definition from LiveIn
     LiveTmp.erase(I);
 
     // Don't consider *uses* in PHI nodes, we handle their contribution to
for (Value *V : I->operands()) {
         // - Second, we can't disallow arbitrary inttoptr constants even
         // if the language frontend does.  Optimization passes are free to
         // locally exploit facts without respect to global reachability.  This
         // can create sections of code which are dynamically unreachable and
         // contain just about anything.  (see constants.ll in tests)
         LiveTmp.insert(V);
       }
     }
+
+    // If we've computed live references and the current instruction happens
+    // to be a statepoint, add its bases to the live set.
+    if (BaseMaps && CallSite(I)) {
+      auto BaseMapIter = BaseMaps->find(I);
+      if (BaseMapIter != BaseMaps->end())
+        insertBases(*BaseMapIter->second, LiveTmp);
+    }
   }
 }
 
 static void computeLiveOutSeed(BasicBlock *BB, DenseSet<Value *> &LiveTmp) {
 
   for (BasicBlock *Succ : successors(BB)) {
     const BasicBlock::iterator E(Succ->getFirstNonPHI());
     for (BasicBlock::iterator I = Succ->begin(); I != E; I++) {
static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data,
                           BasicBlock &BB) {
   checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator());
   checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true);
   checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator());
 }
 #endif
 
 static void computeLiveInValues(DominatorTree &DT, Function &F,
-                                GCPtrLivenessData &Data) {
+                                GCPtrLivenessData &Data,
+                                const BaseMapMapTy *BaseMaps) {
 
   SmallSetVector<BasicBlock *, 32> Worklist;
   auto AddPredsToWorklist = [&](BasicBlock *BB) {
     // We use a SetVector so that we don't have duplicates in the worklist.
     Worklist.insert(pred_begin(BB), pred_end(BB));
   };
   auto NextItem = [&]() {
     BasicBlock *BB = Worklist.back();
     Worklist.pop_back();
     return BB;
   };
 
   // Seed the liveness for each individual block
   for (BasicBlock &BB : F) {
     Data.KillSet[&BB] = computeKillSet(&BB);
     Data.LiveSet[&BB].clear();
-    computeLiveInValues(BB.rbegin(), BB.rend(), Data.LiveSet[&BB]);
+    computeLiveInValues(BB.rbegin(), BB.rend(), BaseMaps, Data.LiveSet[&BB]);
 
 #ifndef NDEBUG
     for (Value *Kill : Data.KillSet[&BB])
       assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill");
 #endif
 
     Data.LiveOut[&BB] = DenseSet<Value *>();
     computeLiveOutSeed(&BB, Data.LiveOut[&BB]);
#ifndef NDEBUG
   // Sanity check our output against SSA properties.  This helps catch any
   // missing kills during the above iteration.
   for (BasicBlock &BB : F) {
     checkBasicSSA(DT, Data, BB);
   }
 #endif
 }
 
-static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data,
+static void findLiveSetAtStatepoint(CallSite Statepoint,
+                                    GCPtrLivenessData &Data,
+                                    const BaseMapMapTy *BaseMaps,
                                     StatepointLiveSetTy &Out) {
-
+  Instruction *Inst = Statepoint.getInstruction();
   BasicBlock *BB = Inst->getParent();
 
   // Note: The copy is intentional and required
   assert(Data.LiveOut.count(BB));
   DenseSet<Value *> LiveOut = Data.LiveOut[BB];
 
-  // We want to handle the statepoint itself oddly.  It's
-  // call result is not live (normal), nor are it's arguments
-  // (unless they're used again later).  This adjustment is
-  // specifically what we need to relocate
+  // We want to handle the statepoint itself oddly.  Its
+  // call result is not live (normal), nor are its non-deopt
+  // arguments (unless they're used again later).  This
+  // adjustment is specifically what we need to relocate.
   BasicBlock::reverse_iterator rend(Inst->getIterator());
-  computeLiveInValues(BB->rbegin(), rend, LiveOut);
+  computeLiveInValues(BB->rbegin(), rend, BaseMaps, LiveOut);
   LiveOut.erase(Inst);
   Out.insert(LiveOut.begin(), LiveOut.end());
+
+  // Ensure reference arguments in the deopt argument list are considered live
+  // through the safepoint (and thus make sure they get relocated.)
+  for (Value *Arg : GetDeoptBundleOperands(Statepoint)) {
+    assert(!isUnhandledGCPointerType(Arg->getType()) &&
+           "support for FCA unimplemented");
+    if (isHandledGCPointerType(Arg->getType()))
+      Out.insert(Arg);
+  }
+
+  // Likewise ensure that bases of derived pointers live through
+  // the statepoint are considered live through it as well.
+  if (BaseMaps)
+    insertBases(*BaseMaps->lookup(Inst), Out);
 }
 
 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
+                                  const BaseMapMapTy &BaseMaps,
                                   const CallSite &CS,
                                   PartiallyConstructedSafepointRecord &Info) {
-  Instruction *Inst = CS.getInstruction();
+  // TODO: update this to collect separate live sets for normal and exception
+  // paths; when spilling on exception path but not normal path, this lets us
+  // skip spilling values that are live only on the normal path.
   StatepointLiveSetTy Updated;
-  findLiveSetAtInst(Inst, RevisedLivenessData, Updated);
+  findLiveSetAtStatepoint(CS, RevisedLivenessData, &BaseMaps, Updated);
 
 #ifndef NDEBUG
   DenseSet<Value *> Bases;
   for (auto KVPair : Info.PointerToBase) {
     Bases.insert(KVPair.second);
   }
 #endif
   // We may have base pointers which are now live that weren't before.  We need

unittests/IR/InstructionsTest.cpp

TEST(InstructionsTest, BranchInst) {
   // clean up
   delete b0;
   delete b1;
 
   delete bb0;
   delete bb1;
 }
 
+template <typename ItRange>
+static void checkBlockIteration(ArrayRef<BasicBlock *> Expected,
+                                ItRange Range) {
+  auto Begin = Range.begin(), End = Range.end();
+  size_t I = 0;
+  for (auto Iter = Begin; Iter != End; ++Iter)
+    EXPECT_EQ(Expected[I++], *Iter);
+  EXPECT_EQ(Expected.size(), I);
+};
+
+TEST(InstructionsTest, UnwindDestIterator) {
+  LLVMContext &C(getGlobalContext());
+
+  // Make BasicBlocks to model exceptional flow.
+  std::unique_ptr<BasicBlock> SwitchBlock1(BasicBlock::Create(C));
+  std::unique_ptr<BasicBlock> SwitchBlock2(BasicBlock::Create(C));
+  std::unique_ptr<BasicBlock> CatchBlock1(BasicBlock::Create(C));
+  std::unique_ptr<BasicBlock> CatchBlock2(BasicBlock::Create(C));
+  std::unique_ptr<BasicBlock> CatchBlock3(BasicBlock::Create(C));
+  std::unique_ptr<BasicBlock> CleanupBlock(BasicBlock::Create(C));
+
+  // Generate EH pads in the BasicBlocks.
+  auto *NoToken = ConstantTokenNone::get(C);
+  auto *Switch1 = CatchSwitchInst::Create(NoToken, SwitchBlock2.get(), 1,
+                                          "switch1", SwitchBlock1.get());
+  auto *Switch2 = CatchSwitchInst::Create(NoToken, CleanupBlock.get(), 2,
+                                          "switch2", SwitchBlock2.get());
+  CleanupPadInst::Create(NoToken, {}, "cleanup", CleanupBlock.get());
+  CatchPadInst::Create(Switch1, {}, "catch1", CatchBlock1.get());
+  CatchPadInst::Create(Switch2, {}, "catch2", CatchBlock2.get());
+  CatchPadInst::Create(Switch2, {}, "catch3", CatchBlock3.get());
+
+  // Hook up the handlers to the switches.
+  Switch1->addHandler(CatchBlock1.get());
+  Switch2->addHandler(CatchBlock2.get());
+  Switch2->addHandler(CatchBlock3.get());
+
+  // Note the expected visit order with and without visiting unsplittable
+  // blocks.
+  BasicBlock *SplittableDests[] = {CatchBlock1.get(), CatchBlock2.get(),
+                                   CatchBlock3.get(), CleanupBlock.get()};
+  BasicBlock *AllDests[] = {SwitchBlock1.get(), CatchBlock1.get(),
+                            SwitchBlock2.get(), CatchBlock2.get(),
+                            CatchBlock3.get(),  CleanupBlock.get()};
+
+  // Give all the blocks terminators to make them well-formed.
+  for (BasicBlock *Block : SplittableDests)
+    new UnreachableInst(C, Block);
+
+  // Create and test an invoke.
+  auto *FnTy = FunctionType::get(Type::getVoidTy(C), false);
+  auto *FnPtr = ConstantPointerNull::get(FnTy->getPointerTo());
+  std::unique_ptr<BasicBlock> NormalDest(BasicBlock::Create(C));
+  std::unique_ptr<InvokeInst> Invoke(InvokeInst::Create(
+      FnTy, FnPtr, NormalDest.get(), SwitchBlock1.get(), {}));
+  checkBlockIteration(SplittableDests, Invoke->getTransitiveUnwindDests());
+  checkBlockIteration(AllDests, Invoke->getTransitiveUnwindDests<false>());
+
+  // Create and test a cleanupret.
+  std::unique_ptr<CleanupPadInst> DummyPad(CleanupPadInst::Create(NoToken, {}));
+  std::unique_ptr<CleanupReturnInst> CleanupRet(
+      CleanupReturnInst::Create(DummyPad.get(), SwitchBlock1.get()));
+  checkBlockIteration(SplittableDests, CleanupRet->getTransitiveUnwindDests());
+  checkBlockIteration(AllDests, CleanupRet->getTransitiveUnwindDests<false>());
+
+  // Create and test a catchswitch.
+  std::unique_ptr<CatchSwitchInst> TestSwitch(
+      CatchSwitchInst::Create(NoToken, SwitchBlock1.get(), 1));
+  std::unique_ptr<BasicBlock> TestCatchBlock(BasicBlock::Create(C));
+  CatchPadInst::Create(TestSwitch.get(), {}, "testcatch", TestCatchBlock.get());
+  TestSwitch->addHandler(TestCatchBlock.get());
+  checkBlockIteration(SplittableDests, TestSwitch->getTransitiveUnwindDests());
+  checkBlockIteration(AllDests, TestSwitch->getTransitiveUnwindDests<false>());
+
+  // Break reference cycles before deleting IR.
+  for (auto *Block : AllDests)
+    Block->dropAllReferences();
+  TestSwitch->dropAllReferences();
+}
+
 TEST(InstructionsTest, CastInst) {
   LLVMContext &C(getGlobalContext());
 
   Type *Int8Ty = Type::getInt8Ty(C);
   Type *Int16Ty = Type::getInt16Ty(C);
   Type *Int32Ty = Type::getInt32Ty(C);
   Type *Int64Ty = Type::getInt64Ty(C);
   Type *V8x8Ty = VectorType::get(Int8Ty, 8);