Use mozilla::BinarySearchIf for baseline's IC-to-pcoffset binary search, rather than hand-rolling it

RESOLVED FIXED

Status

()

defect
RESOLVED FIXED
3 years ago
3 years ago

People

(Reporter: Waldo, Assigned: Waldo)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments)

Assignee

Description

3 years ago
We've had problems with people incorrectly hand-rolling binary-search before; see bug 917918.  Use the centralized algorithm.
Assignee

Comment 1

3 years ago
Posted patch PatchSplinter Review
Attachment #8717730 - Flags: review?(jdemooij)
Comment on attachment 8717730 [details] [diff] [review]
Patch

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

Much more readable!

Can we also use this in BaselineScript::icEntryFromReturnOffset?  Some other potential victims: https://dxr.mozilla.org/mozilla-central/search?q=%22top+-+bottom%22+path%3Ajs%2Fsrc%2F&redirect=false&case=false

::: js/src/jit/BaselineJIT.cpp
@@ +606,5 @@
>  
>  static inline size_t
>  ComputeBinarySearchMid(BaselineScript* baseline, uint32_t pcOffset)
>  {
> +    struct ICEntries

Ugh, I always forget you can declare a class/struct inside a function. Pretty sure I'd have added it outside the function, but this is nicer.

@@ +610,5 @@
> +    struct ICEntries
> +    {
> +        BaselineScript* const baseline_;
> +
> +        ICEntries(BaselineScript* baseline) : baseline_(baseline) {}

Nit: explicit
Attachment #8717730 - Flags: review?(jdemooij) → review+
Assignee

Comment 3

3 years ago
(In reply to Jan de Mooij [:jandem] from comment #2)
> Can we also use this in BaselineScript::icEntryFromReturnOffset?  Some other
> potential victims:
> https://dxr.mozilla.org/mozilla-central/search?q=%22top+-
> +bottom%22+path%3Ajs%2Fsrc%2F&redirect=false&case=false

Will spin up more patches.

> Ugh, I always forget you can declare a class/struct inside a function.
> Pretty sure I'd have added it outside the function, but this is nicer.

To be fair, in-function declarations used in templates only started working in C++11, and of course compiler support usable by us came even more slowly.
Assignee

Updated

3 years ago
Keywords: leave-open
Assignee

Comment 5

3 years ago
Good idea for the search.  This fixes the remaining instances *except* the one in jsscript.cpp.  The per-halving code wants to know the bottom index as it goes, but mozilla::BinarySearchIf doesn't expose that.  Without adding another mozilla::BinarySearch* function that exposes the instantaneous ranges, I'm not sure that last case is rewritable.  But maybe you have a bright idea.
Attachment #8720051 - Flags: review?(jdemooij)
Comment on attachment 8720051 [details] [diff] [review]
Use mozilla::BinarySearch{,If} for more manual binary searches in SpiderMonkey

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

Thanks.

::: js/src/vm/TypeInference-inl.h
@@ +528,3 @@
>  
> +    MOZ_ASSERT_IF(found, bytecodeMap[loc] == offset);
> +    *hint = mozilla::AssertedCast<uint32_t>(loc);

Hm, I was wondering about the !found case, but if I understand this function correctly, the code is correct no matter what *hint is; it's just an optimization.
Attachment #8720051 - Flags: review?(jdemooij) → review+
Assignee

Comment 8

3 years ago
Comment on attachment 8720051 [details] [diff] [review]
Use mozilla::BinarySearch{,If} for more manual binary searches in SpiderMonkey

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

::: js/src/vm/TypeInference-inl.h
@@ +528,3 @@
>  
> +    MOZ_ASSERT_IF(found, bytecodeMap[loc] == offset);
> +    *hint = mozilla::AssertedCast<uint32_t>(loc);

If !found, loc is set to the spot in the container where a match *would* have first been found, if one were found.  This is consistent with the old behavior of continuing until mid == top, then using mid (even tho it wouldn't be the "right" location for a total match).
Assignee

Updated

3 years ago
Status: ASSIGNED → RESOLVED
Last Resolved: 3 years ago
Keywords: leave-open
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.