1752582 - Ion's RA: investigate invariants related to live-range splitting

Status: NEW

(Core :: JavaScript Engine: JIT, enhancement, P2)

Description

[Julian Seward [:jseward]]

Ion's RA relies heavily on bundle-splitting to work, mostly as an optimisation,
to generate allocations with less spilling/reloading, but occasionally
critically, to resolve otherwise unresolvable fixed-register conflicts within a
single bundle.

Given how important splitting is, it would be nice to establish (checkable!)
invariants for it. One appealing candidate -- let's call it "exact-split" --
is that the result of a split, when recombined, produce the original bundle
exactly, with no holes and no overlaps.

However, bug 1752520 shows a very simple example where there is an overlap.
That raises the question of whether that case is an obscure corner case handled
wrongly, or whether there is a more general breach of exact-split.

The checker attached as a diff does that, checking every split. For every
failure it prints a string summarising the split, consisting of one character
per code point -- that is, two characters per LIR, one for the INPUT position,
one for the OUTPUT position.

If a point in the original is covered by exactly one fragment it prints a dot.
If it's covered twice, 2 is printed, and zero times 0, etc. For the
example in bug 1752520 we get

VerifySplit atAllRUses: FAIL delta =    3-7    ...22

This shows that 2 frags cover the original at points 6 and 7, as described in
bug 1752520 comment 0.

The summary lines also include a short bit of text indicating which of the
splitting routines (atAllRUses in the above example), so as to facilitate
identifying any per-heuristic patterns.

---

When run on larger inputs, the checker shows that almost all splits don't
observe the exact-split invariant. A simple JS input requires 298 splits, of
which 287 fail the invariant. In the majority of cases there are regions where
two fragments cover each original point:

VerifySplit atAllRUses: FAIL delta =    9-36   .....2...2.....2...2.......2
VerifySplit    saCalls: FAIL delta =   13-43   .22222.........2...............
VerifySplit    saCalls: FAIL delta =    3-28   .222222222222222.........2

In others there are points not covered by any frag. One wonders why the
allocator works at all when that happens. These often result from splitting
across calls (saCalls):

VerifySplit    saCalls: FAIL delta = 1194-1212 .00000000000000000.
VerifySplit    saCalls: FAIL delta = 1306-1323 .000000000000000..

Splitting at all reg uses (atAllRUses) often produces an overlap just at the
last position:

VerifySplit atAllRUses: FAIL delta =   11-22   ...........2
VerifySplit atAllRUses: FAIL delta =    7-18   ...........2

Comment 1

[Julian Seward [:jseward]]

Attachment: bug1752582-split-invariants.diff

Invariant-checking code as described in comment 0.