999538 - Backtracking allocator should reuse stack slots

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement)

Description

[Dan Gohman [:sunfish]]

Attachment: reuse-stack-slots.js

Attached is a contrived testcase which demands 16 registers, releases them all, and then demands 16 registers again. Since x64 for example doesn't have 16 allocatable registers, both sets of demands require some spilling. Ideally, the register allocator should notice that the register lifetimes are non-overlapping, and reuse the stack slots, to minimize stack usage.

Comment 1

[Brian Hackett [Laid off!]]

Attachment: patch

Patch to try to reuse physical stack slots.  This is done by adding another pass to backtracking allocation (trying to fit this into the initial interval allocation/eviction seems like a waste of CPU time).  When doing the initial allocation we use virtual stack slots, and replace these with physical stack slots in a pass that tries to reuse physical stack slots when there is no overlap in usage between the intervals being allocated.

On octane-mandreel x86, this reduces the total stack size of all compiled scripts from ~22k bytes to 13.8k, which is somewhat better than how LSRA does.  This doesn't seem to move our mandreel score much one way or the other, but the cost of the extra pass is minimal (less than 1% of regalloc time on mandreel) and it's always nice to be using less stack space.

Comment 2

[Dan Gohman [:sunfish]]

Comment on attachment 8551540 [details] [diff] [review]
patch

Review of attachment 8551540 [details] [diff] [review]:
-----------------------------------------------------------------

It's always nice when a simple algorithm delivers nice results :-).

I wonder if sorting the live intervals by some criteria (spill weight?) could help here too.

::: js/src/jit/BacktrackingAllocator.h
@@ +180,5 @@
>      // register to use for a given interval.
>      size_t registerStart;
>  
> +    // During register allocation, virtual stack slots are used for spills.
> +    // These are converted to actual spill locations 

Trailing whitespace

Comment 3

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/efe76955cea5

Comment 4

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/efe76955cea5