845866 - BaselineCompiler: Speed up lookup of IC entries

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Kannan Vijayan [:djvj]]

Originated from bhackett's comment on bug 844515.

Ion will be querying BaseineScript's IC entry tables frequently.  IC entry lookups by PC are currently linear.  These should be made into a binary search.

Furthermore, BaselineInspector should cache its last lookup result and if the next lookup is within a small distance of the original lookup, then perform a linear search from the last cached lookup instead of a full binary search.

Comment 1

[Kannan Vijayan [:djvj]]

Attachment: Patch

Makes icEntryFromReturnOffset and icEntryFromPCOffset use binary search to find the IC entries in question.

Also adds a variant of icEntryFromPCOffset that does a linear search from a previously returned entry if the new pcOffset being looked up occurs shortly after the pcOffset for the previous entry that was looked up.  BaselineInspector is altered to use this method to make most PC lookups into constant-time operations.

Comment 2

[Brian Hackett [Laid off!]]

Comment on attachment 720362 [details] [diff] [review]
Patch

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

::: js/src/ion/BaselineJIT.cpp
@@ +448,5 @@
> +ICEntry &
> +BaselineScript::icEntryFromPCOffset(uint32_t pcOffset, ICEntry *prevLookedUpEntry)
> +{
> +    // If pcOffset is far from to previous looked up entry's pcOffset, then forget about
> +    // scan.

This should have a better comment.  "Do a linear forward search from the last queried PC offset, or fallback to a binary search if the last offset is too far away." or somesuch.

Comment 3

[Kannan Vijayan [:djvj]]

Addressed and pushed: https://hg.mozilla.org/projects/ionmonkey/rev/3dae7de5f6ff
Waiting for tbpl green before closing.