939824 - Factor out the backtracking allocator's splitting logic

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, enhancement)

Description

[Dan Gohman [:sunfish]]

Attachment: regalloc-refactor-splitat.patch

The backtracking allocator has several different splitting methods: trySplitAcrossHotcode, trySplitAfterLastRegisterUse, and splitAcrossCalls, and there is a fair amount of code which is common between them which could be factored out. It would also help the development of new splitting heuristics to avoid needing to re-implement a lot of the mechanics.

Comment 1

[Dan Gohman [:sunfish]]

Attachment: regalloc-splitat-nicely.patch

This patch improves up the new splitAt routine to avoid splitting the LiveInterval at range boundaries. This is a minor optimization, at it reduces unnecessary spilling at range boundaries.

Comment 2

[Dan Gohman [:sunfish]]

Attachment: regalloc-refactor-splitat.patch

Comment 3

[Dan Gohman [:sunfish]]

Attachment: regalloc-splitat-nicely.patch

Comment 4

[Dan Gohman [:sunfish]]

Comment on attachment 8333892 [details] [diff] [review]
regalloc-refactor-splitat.patch

This patch separates most of the mechanism from the policy of trySplitAcrossCalls.

Comment 5

[Dan Gohman [:sunfish]]

Comment on attachment 8336050 [details] [diff] [review]
regalloc-refactor-splitat.patch

Oops, here is the updated version of the patch.

Comment 6

[Dan Gohman [:sunfish]]

Comment on attachment 8336051 [details] [diff] [review]
regalloc-splitat-nicely.patch

Previously, this code created new LiveIntervals at every Range boundary, which led to unnecessary spilling. This patch introduces new LiveIntervals only at the specified split points.

Comment 7

[Dan Gohman [:sunfish]]

Attachment: regalloc-splitat-hotcode.patch

This patch converts trySplitAcrossHotcode to use the new splitAt, which is a nice demonstration of its utility.

Comment 8

[Brian Hackett [Laid off!]]

Comment on attachment 8336050 [details] [diff] [review]
regalloc-refactor-splitat.patch

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

Thanks!

::: js/src/jit/BacktrackingAllocator.cpp
@@ +1715,5 @@
>  }
>  
> +// Find the next split position after the current position.
> +static size_t NextSplitPosition(size_t activeSplitPosition,
> +                                const Vector<CodePosition, 4, SystemAllocPolicy> &splitPositions,

This Vector<...> (and, generally, any Vector<...> that otherwise would have to be typed twice) should be a typedef.

Comment 9

[Dan Gohman [:sunfish]]

(In reply to Brian Hackett (:bhackett) from comment #8)
> Comment on attachment 8336050 [details] [diff] [review]
> regalloc-refactor-splitat.patch
> 
> Review of attachment 8336050 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Thanks!

Thanks for the reviews!

> ::: js/src/jit/BacktrackingAllocator.cpp
> @@ +1715,5 @@
> >  }
> >  
> > +// Find the next split position after the current position.
> > +static size_t NextSplitPosition(size_t activeSplitPosition,
> > +                                const Vector<CodePosition, 4, SystemAllocPolicy> &splitPositions,
> 
> This Vector<...> (and, generally, any Vector<...> that otherwise would have
> to be typed twice) should be a typedef.

Ok. Typedef added and code updated to use it.

https://hg.mozilla.org/integration/mozilla-inbound/rev/f3333afffd24
https://hg.mozilla.org/integration/mozilla-inbound/rev/01333a597b9a
https://hg.mozilla.org/integration/mozilla-inbound/rev/2dc657af3475

Comment 10

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/f3333afffd24
https://hg.mozilla.org/mozilla-central/rev/01333a597b9a
https://hg.mozilla.org/mozilla-central/rev/2dc657af3475