1958280 - Add a very simple Ion register allocator

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, task, P3)

Description

[Jan de Mooij [:jandem]]

Register allocation is usually the slowest part of the Ion compiler backend. To help us experiment with future Ion changes (multiple tiers, backend improvements etc) and to document the LIR => register allocator interface, I've written a second very simple register allocator this week.

We used to have the 'stupid allocator' for this, but we removed it in bug 1617593 because (IIRC) it didn't support Wasm stack results. This allocator also didn't attempt to generate good code: it pre-allocated a 16-byte stack slot for each virtual register and spilled temps or unused/short-lived outputs. It also didn't support safepoints (it didn't have enough information for this) so it relied on the register allocation verifier code to fill the safepoints.

The 'simple allocator' I've written is inspired by the stupid allocator, but it does two passes over the LIR:

1. Scan the LIR instructions (last to first) to identify the last-use of each vreg and create a liveIn bit set for each basic block. This is a simplified version of the backtracking allocator's buildLivenessInfo code.
2. Iterate over all LIR instructions (first to last) and allocate registers for each instruction's uses and defs. This also fills the safepoints and allocates/frees/reuses stack slots. Virtual registers that are used in other blocks are spilled but in a lot of cases we can carry live registers to successor blocks with a single predecessor.

With a few simple heuristics this results in pretty decent code within basic blocks. Because it allocates and frees stack slots using the StackSlotAllocator class, it was also easy to support Wasm stack result areas in this allocator.

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 1 - Move some fields and methods from RegisterAllocator to BacktrackingAllocator. r?iain!

RegisterAllocator is the base class for all register allocators. The backtracking
allocator needs this data but my simple allocator doesn't.

Comment 2

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 2 - Move safepoint vectors to backtracking allocator class. r?iain!

This is more efficient too because lowering records how many entries there are
so we can now pre-allocate these vectors without having to reallocate.

Minor fix: in findFirstNonCallSafepoint the assertion was using getSafepoint
instead of getNonCallSafepoint.

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 3 - Tidy up the code for adding GC allocations to safepoints. r?iain!

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 4 - Add LInstruction input iterator specialization that avoids snapshot inputs. r?iain!

Also renames LInstruction::InputIterator to LInstruction::InputIter to be
less verbose.

Comment 5

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 5 - Add iterators for LInstruction outputs and temps. r?iain!

The boilerplate for this (including skipping BogusTemp definitions) is a bit tedious
so add an iterator for this.

The term 'definition' is used for both outputs and temps so use OutputIter for outputs
to be more specific.

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 6 - Add missing RegisterSet::Subtract method. r?iain!

Comment 7

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 7 - Add StackSlotAllocator::freeSlot method. r?jseward!

StackSlotAllocator already has normalSlots and doubleSlots vectors so we just
need to add a quadSlots vector and a freeSlot method to support returning slots to
the slot allocator.

This is nice for the simple register allocator because it then doesn't need to track
available stack slots itself.

Comment 8

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 8 - Improve safepoint checks in the regalloc verifier. r?jseward!

The backtracking allocator also adds registers for at-start uses to safepoints,
so change the verifier to check these uses too.

Also remove the early return for THIS_FRAME_ARGSLOT allocations in checkSafepointAllocation.
It's not clear why that's there so it's safer to check these allocations too.

Comment 9

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 9 - Fix minor regression in addLiveRegistersForRange. r?jseward!

This fixes a regression from bug 1938317 part 3 that I noticed while reading the code.

We'd incorrectly mark an instruction's output register as a live-register and
save/restore it while we didn't before that change.

We can't easily check for this in the regalloc verifier because the same register
could also be added to the safepoint's live-regs for a different vreg that was live
at the start of the instruction.

Comment 10

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 10 - Simplify clobberedRegs code a bit in the backtracking allocator. r?jseward!

This is used to mark a subset of liveRegs as 'clobbered' for some debug checks.

Calls always have an empty liveRegs set, so check in the verifier that clobberedRegs
is empty for calls too.

Comment 11

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 11 - Add LInstruction::changePolicyOfReusedInputToAny. r?jseward!

The simple allocator wants to do the same thing.

Longer-term maybe this should be handled during lowering so that we don't need to
rewrite the LUse here.

Comment 12

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 12 - Add LStackSlot::SlotAndWidth. r?iain!

This lets us get the slot-and-width data out as uint32_t and we can create a
SlotAndWidth and LStackSlot from that later.

The simple allocator will use that to represent stack slots so that it doesn't
need to compute the width from the type each time it works with stack slots.

Comment 13

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 13 - Add a simple register allocator for Ion. r?jseward!

Register allocation is usually the slowest part of the Ion compiler backend.
This patch adds the Simple Allocator, a register allocator that results in worse
JIT code but is a lot faster than Backtracking. It's often faster than codegen
and/or GVN.

This allocator lets us experiment with different compilation strategies in the future
and it provides a useful baseline for measuring and optimizing the performance of
the backtracking allocator. It also helps document our LIR => Register Allocator
interface.

Comment 14

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 14 - Add --ion-regalloc=simple to fuzz-flags.txt and some jit-tests. r?jseward!

This is just to have some smoke tests for now to help catch regressions.

Comment 15

[Jan de Mooij [:jandem]]

Attachment: Bug 1958280 part 15 - Add a browser pref for the register allocator. r?iain!

This converts the JitOption to a pref so that it can also be set from the browser.

Comment 16

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/16486f3c512a
part 1 - Move some fields and methods from RegisterAllocator to BacktrackingAllocator. r=iain
https://hg.mozilla.org/integration/autoland/rev/f553fab31d68
part 2 - Move safepoint vectors to backtracking allocator class. r=iain
https://hg.mozilla.org/integration/autoland/rev/e554e29defee
part 3 - Tidy up the code for adding GC allocations to safepoints. r=iain
https://hg.mozilla.org/integration/autoland/rev/96be331c17cd
part 4 - Add LInstruction input iterator specialization that avoids snapshot inputs. r=iain
https://hg.mozilla.org/integration/autoland/rev/8d60ccbe17b3
part 5 - Add iterators for LInstruction outputs and temps. r=iain
https://hg.mozilla.org/integration/autoland/rev/e666541e11e5
part 6 - Add missing RegisterSet::Subtract method. r=iain
https://hg.mozilla.org/integration/autoland/rev/142f85de20cf
part 7 - Add StackSlotAllocator::freeSlot method. r=jseward
https://hg.mozilla.org/integration/autoland/rev/9d66932d0f3f
part 8 - Improve safepoint checks in the regalloc verifier. r=jseward
https://hg.mozilla.org/integration/autoland/rev/621f05dd87a6
part 9 - Fix minor regression in addLiveRegistersForRange. r=jseward
https://hg.mozilla.org/integration/autoland/rev/e907796231d8
part 10 - Simplify clobberedRegs code a bit in the backtracking allocator. r=jseward

Comment 17

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/dcd9496c1da4
part 11 - Add LInstruction::changePolicyOfReusedInputToAny. r=jseward
https://hg.mozilla.org/integration/autoland/rev/4cdacf348de8
part 12 - Add LStackSlot::SlotAndWidth. r=iain
https://hg.mozilla.org/integration/autoland/rev/91c0929b0d84
part 13 - Add a simple register allocator for Ion. r=jseward
https://hg.mozilla.org/integration/autoland/rev/2514b6dd41ae
part 14 - Add --ion-regalloc=simple to fuzz-flags.txt and some jit-tests. r=jseward
https://hg.mozilla.org/integration/autoland/rev/16111ec3bf26
part 15 - Add a browser pref for the register allocator. r=iain

Comment 18

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/16486f3c512a
https://hg.mozilla.org/mozilla-central/rev/f553fab31d68
https://hg.mozilla.org/mozilla-central/rev/e554e29defee
https://hg.mozilla.org/mozilla-central/rev/96be331c17cd
https://hg.mozilla.org/mozilla-central/rev/8d60ccbe17b3
https://hg.mozilla.org/mozilla-central/rev/e666541e11e5
https://hg.mozilla.org/mozilla-central/rev/142f85de20cf
https://hg.mozilla.org/mozilla-central/rev/9d66932d0f3f
https://hg.mozilla.org/mozilla-central/rev/621f05dd87a6
https://hg.mozilla.org/mozilla-central/rev/e907796231d8
https://hg.mozilla.org/mozilla-central/rev/dcd9496c1da4
https://hg.mozilla.org/mozilla-central/rev/4cdacf348de8
https://hg.mozilla.org/mozilla-central/rev/91c0929b0d84
https://hg.mozilla.org/mozilla-central/rev/2514b6dd41ae
https://hg.mozilla.org/mozilla-central/rev/16111ec3bf26