Split hoisting can select unrelated loops / has bad edge cases #273

When splitting lifetimes for register allocations, 'split hoisting' starts with a split at a register conflict. If that point is deeper than the bundle’s earliest range, it scans forward from the bundle start and selects the first block deeper than that start. It checks neither loop membership nor dominance, and ignores intervening uses.

There are a few cases:

Bad: conditional call that rejoins - identical with trimming only

As pseudocode:

acc = 0
for k in 0..n:
    if k == 17:
        helper()
    acc += 1
return acc

Split hoisting decides to put the split before the loop, leading to a store/load around acc += 1. Trimming does the same thing independently.
In both cases this is arguably bad - only the if-branch should spill.

Bad: a later loop can spill in an earlier loop - trimming also unless #272

Slightly contrived example, but it's not implausible either:

if fast_path:
    acc = 0
    while n-- != 0:
        acc += 1
else:
    acc = 1
    while n-- != 0:
        helper() // opaque, clobbers acc
        acc += 1
return acc

here the join at the end puts both loop acc in the same bundle, and hoisting ends up putting the split before the fast-path loop. This leads to spills in both loops, even though only the slow path would need them.

Neutral: loop with one use or a later use - trimming is identical

acc = n * n;
for a in 0..3:
    opaque_call()
return acc;

Here both hoisting and trimming end up with the same logic: store once before, reload once after (of if used after call(), reload in the loop).

Good case: use before a call in a loop - beats trimming (depending)

x = argument
for n 0..times:
    observe(x)
    helper()
return x

Here hoisting leads to a store before the loop and a reload before the observe call. Trimming instead stores before helper and reloads after helper. Note that this leads to hoisting always having at least one store even if times == 0, in my contrived example.

There might be a few more situations, but that's what I found so far. See attachment for CLIF: split-hoisting-repro.md

Hoisting predates trimming in this codebase, so the partial redundancy probably comes from there.

There are a couple possible fixes:

• Remove hoisting. It's slightly faster to run and occasionally a little worse than just trimming, but maybe not enough to really matter?
• Remove hoisting and separately try to improve stores - this would make trimming equivalent to hoisting. Trimming separately probably should be smarter around control-flow, see Avoid trimming spill ranges into deeper loops #272 .
• Restrict hoisting candidates to the loop & its parents. This solves case 2 but not case 1.
• Fancier fix that tries to account for conditionals.
• Maybe other ideas I haven't had.

I ran into both of the early cases while working on a JIT, hence the 'fallback with similar structure' pattern, but none seem that outlandish that common code wouldn't also trigger them to me.