JIT: maybe reconsider multiple def CSEs

Start with CSE candidate formation and its forward dataflow, then examine how candidate member trees are rescanned and how LSRA handles the resulting common temporary. Measure cases with disjoint CSE lifetimes and differing exception sets; done means non-reaching defs no longer create CSEs and viable cases preserve correctness and allocation quality.

Have been looking at CSE behavior and noticed some examples where multiple-def CSEs are a bit strange.

Here's one, where the two defs are in the gray blocks and the use is in the yellow. A closer look reveals that only one of the two defs can reach the use.

This really should just be a single-def CSE.

We get to this point because CSE candidate formation (for the most part) is just keyed on the liberal VN. If two trees in the method have the same liberal VN then they belong to the same CSE candidate set. We then do a forward dataflow using these CSE trees. The only way a CSE is killed is at a join.

We then revisit the candidate member trees, and if the CSE is available at that point then the tree is marked as a use; if not, it is marked as a def. So in the example above the candidate set has 3 trees, but the BB15 tree is available at BB31 so the latter is marked as a use. The BB02 tree does not reach any uses and is also considered a def.

There are at least two issues here -- one potential and one we see in the above case:

• if the CSE defs don't agree on exception sets, the entire candidate may become non-viable, if some of the uses need stronger exception guarantees than intersection of all defs provides.
• each def turns into a (cse-temp def, use) pair, so none of the defs are dead, and CSE runs late enough that nothing gets rid of this temp, and there is now a common temp tying together disjoint lifetimes, which may confuse LSRA and produce worse allocation

In the case above the CSE is a class handle, and the last problem potentially leads to a lower perf score than if no CSE was done, as there is an extra callee save used (to be fair it seems plausible this would happen even without the common temp, as the path from 15->31 is live across a call).

It's not clear how often we see the case where two CSE defs reach some CSE use, and the way the algorithm is structured it's not obvious how to figure this out. Here's one half-baked idea, perhaps worth measuring sometime.

• We do the initial CSE location like we do now, looking for multiple distinct trees with the same liberal (ish) VN. We then give each of those trees its own candidate number, and propagate availability. Note as currently constructed the algorithm is limited to 64 candidates so this limit might need to be raised.
• Then, rescanning each candidate, we do a union find where the "leaders" are defs, trees that have no available expressions, and the set members are uses, trees with one or more of the leaders as available expressions (if there are multiple leaders than at least one use has to be reachable from more than one def; discovering one such is what leads to union-ing).

In the above case this would lead to CSE#02 being its own use-less set, so it would drop out of CSE.

category:cq
theme:cse
skill-level:expert
cost:medium
impact:medium