1922227 - Use a Vector instead of linked list + AvlTree for call positions

Status: RESOLVED FIXED

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

Description

[Jan de Mooij [:jandem]]

The register allocator is a bit wasteful with how it tracks the position of call instructions:

• CallRange is always a length-one range and we only look at its from position.
• These call ranges are stored in both a linked list (callRangesList) and in an AvlTree.

It's simpler and more efficient to store the list of positions in a Vector and do a binary search on that. It's a little faster for some large Wasm modules but also uses less memory and should be more cache friendly.

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Bug 1922227 - Store call positions in a Vector instead of a linked list + AvlTree. r?jseward!

CallRange was always a length-1 range and in splitAcrossCalls we only looked at its
from position. This patch removes CallRange and only stores the from position.

Store this list of positions in a Vector instead of a linked list + AvlTree. Because
the Vector is sorted, we can do a binary search on it to find the first position within
a range.

LIR generation now tracks the number of call instructions so that the register allocator
can grow the Vector to the right size.

This speeds up Ion compilation of some large Wasm modules by 1-2%, but it's also simpler
and should use less memory.

Comment 2

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/3be712f2e110
Store call positions in a Vector instead of a linked list + AvlTree. r=jseward

Comment 3

[Serban Stanca [:SerbanS]]

https://hg.mozilla.org/mozilla-central/rev/3be712f2e110