At an OSR exit, FTL should select from all legal exit origins based on which one involves the least live state

• Component: JavaScriptCore
• Status: NEW ---

[Filip Pizlo]

If you have multiple exit origins in a row and none of them involves non-SideState effects, then FTL OSR exit could pick any one of them.  So, FTL should pick the one that requires the least live state.

[Filip Pizlo]

To address https://bugs.webkit.org/show_bug.cgi?id=152106, we want to ensure that if we have:

a: BitRShift(@address, 2)
b: CheckInBounds(@address, @length)

Then we usually exit to before @a, since @b is likely to require both @address and @a to be live while @a won't need itself. Unless @address dies at @a, @a will have one fewer live things than @b.

[Filip Pizlo]

We don't just want the smallest live set.  We need to give special treatment to things that are live only for OSR.  So for each exit we can have three counts:

NumZombies: number of children that are not otherwise live.
NumLive: number of children that are otherwise live.
NumChildren: NumZombies + NumLive.

We can use a HashSet<Node*> to track live things in FTL::LowerDFGToLLVM.  When emitting an OSR exit, we can evaluate NumZombies and NumLive for each available exit site.

So the question is how to rank the exit sites. One possibility is to minimize NumChildren. That sort of makes sense since the one with the smallest number of children is likely to keep the least amount of stuff alive. However, the things it's keeping alive might be otherwise dead while some other exit with more total children might only refer to children that are already live anyway.

The best heuristic is probably to minimize NumZombies, and then use NumLive only as a tie-breaker.

It's not totally clear what the best algorithm is for doing this. If we're armed with a live set and each exit site has a node set, then we could just do the O(numExitSites * exitSiteSize) work to compute the counts for each exit site and then pick the smallest.

Another option is that we keep a mapping from Node* to all of its exit sites. When it dies, we tell those sites to increment numZombies.  That seems quite cheap.

So then there is the question of what makes an exit site. We should probably just create an exit state - i.e. the exit origin paired with the exit arguments - every time we see ExitOK or we change exit origins.  Anytime we clobber things that are observable to the user, we blow away our list of exit states.