1801875 - Use AvlTree for profiler's JIT code table

Status: RESOLVED FIXED

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

Description

[Jan de Mooij [:jandem]]

While looking at bug 1799806 I tried to fix some issues and then ended up making larger changes in this area.

We currently use a skip list to implement the profiler's JIT entry table. We can simplify this table a lot by replacing it with the AvlTree class that Julian added recently. My patches also change the profiler entries to use proper constructors/destructors with UniquePtr .

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Bug 1801875 part 1 - Factor out JitCodeRange base class. r?jonco!

This doesn't provide much value now, but will simplify the next patch.

Comment 2

[Jan de Mooij [:jandem]]

Attachment: Bug 1801875 part 2 - Replace skip list for profiler table with AvlTree. r?jonco!

The skip list implementation in JitcodeGlobalTable is hard to work with and
intertwined with the rest of the code. This patch replaces it with the new
js::AvlTree. The way it's used is very similar to how the register allocator
now uses AVL trees to track live ranges.

Entries are now allocated with malloc instead of the LifoAlloc. This should
be fine because there's at most one entry per JIT compilation, and means we don't
need to maintain our own free list. It also makes it easier to move away from
fixed-size entries in the next patch.

Because the AvlTree has some limitations that are hard to fix (supporting
deletions while iterating over the tree, UniquePtr values), the entries are
actually stored in (and owned by) a Vector. The Vector is used for iterating
over all entries and the tree is only used to look up entries by address.

The fake QueryEntry type that was used only for lookups can be removed now
because we can use JitCodeRange instead.

Depends on D162836

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Bug 1801875 part 3 - Tidy up entry data structures. r?jonco!

This patch makes a few changes that have to happen simultaneously.

Profiler entries now use UniquePtr with proper C++ constructors/destructors and
move semantics, replacing the init() and destroy() methods. The raw pointers in
IonEntry can likely be cleaned up more later.

Entries are no longer copied. Once allocated by the compiler, ownership is transfered
to the table's Vector until the entry can be removed from the table. At that point
all data is destroyed automatically by the UniquePtr.

JitcodeGlobalEntry no longer contains a union of all entry types. It's now just the
entry base class (merged with BaseEntry). This means entries no longer have to be
the same size in memory. IonEntry can likely be simplified in the future to get rid
of the separate allocations for the data it points to.

It might be possible to simplify this more in the future by using virtual methods.

Depends on D162837

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Bug 1801875 part 4 - Clean up Kind enum. r?jonco!

Make it an enum class, remove sentinel values we no longer need, and remove
default cases from switch-statements so we get compiler exhaustiveness checking.

Depends on D162838

Comment 5

[Jan de Mooij [:jandem]]

Attachment: Bug 1801875 part 5 - Use class instead of struct for entry types. r?jonco!

Depends on D162839

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Bug 1801875 part 6 - Rename fooEntry() to asFoo(). r?jonco!

This is more consistent with code elsewhere, now that JitcodeGlobalEntry is
just the base class.

Depends on D162840

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/a75fad391eb6
part 1 - Factor out JitCodeRange base class. r=jonco
https://hg.mozilla.org/integration/autoland/rev/ac4c555a1991
part 2 - Replace skip list for profiler table with AvlTree. r=jonco
https://hg.mozilla.org/integration/autoland/rev/85f0bce2cb73
part 3 - Tidy up entry data structures. r=jonco
https://hg.mozilla.org/integration/autoland/rev/ae93de9d3673
part 4 - Clean up Kind enum. r=jonco
https://hg.mozilla.org/integration/autoland/rev/0e482c20ae1c
part 5 - Use class instead of struct for entry types. r=jonco
https://hg.mozilla.org/integration/autoland/rev/4259f3b15c45
part 6 - Rename fooEntry() to asFoo(). r=jonco

Comment 8

[Serban Stanca [:SerbanS]]

https://hg.mozilla.org/mozilla-central/rev/a75fad391eb6
https://hg.mozilla.org/mozilla-central/rev/ac4c555a1991
https://hg.mozilla.org/mozilla-central/rev/85f0bce2cb73
https://hg.mozilla.org/mozilla-central/rev/ae93de9d3673
https://hg.mozilla.org/mozilla-central/rev/0e482c20ae1c
https://hg.mozilla.org/mozilla-central/rev/4259f3b15c45