721438 - IM: Implement LCompareS

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicolas B. Pierron [:nbp]]

+++ This bug was initially created as a clone of Bug #679804 +++

Inline comparisons of Strings.  This is blocking the compilation of the main function of string-validate-input (a < b) and we don't want to work in a boxed world after the comparison.

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: Implement CompareS

I am not fully conviced by this implementation yet because it needs a lot of registers and I wonder how costly it would be to just rely on a VM call for it.
I will check it's performances against CompareV and see if it is worth landing it.

This patch is made on top of Attachment 591798 [details] [diff] (cf Bug 718853).

Comment 2

[David Anderson [:dvander] - inactive, e-mail if emergency]

Yeah, you can probably simplify this a lot. For the relational cases, a VM call is fine. For ==, != there's an easy fast path: if both sides are atoms, you only need pointer equality. Otherwise, you can call js_CompareStrings or whatever.

Comment 3

[David Anderson [:dvander] - inactive, e-mail if emergency]

Also note that if the pointers are equal, no call is needed, and you can also test length as another fast-path.

Comment 4

[Jan de Mooij [:jandem]]

Comment on attachment 592162 [details] [diff] [review]
Implement CompareS

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

I'm not sure whether this is worth the complexity vs. calling js::CompareStrings, especially if we can make VM calls faster (bug 721810 etc). Would you mind implementing the CompareStrings call and benchmarking the two? C++ compilers may be able to compile the loop in CompareChars to something more efficient, so ideally we'd have a micro-benchmark for both short strings and very long strings (for instance two strings with 7000 chars where the first 6990 are equal).

JM has a string equality IC which compares atoms (suggesting this case is common, |hg blame| may tell you more), so comment 2 may be worth investigating.

If we decide to do the comparison inline, this needs lots of tests for all cases/operators (ropes, atoms, "abc" > "abd", "" <= "" etc).

::: js/src/ion/CodeGenerator.cpp
@@ +821,5 @@
>      return callVM(FunctionInfo<Stub>(stub), lir);
>  }
>  
> +static inline Assembler::Condition
> +JSOpToCondition(JSOp op)

Please move this to CodeGenerator-shared-inl.h, and remove the versions in CodeGenerator-arm.cpp and CodeGenerator-x86-shared.cpp

@@ +859,5 @@
> +    OutOfLineEnsureLinear *ool;
> +
> +    masm.movePtr(lhs, output);
> +    masm.subPtr(rhs, output);
> +    masm.j(Assembler::Equal, &loopEnd);

Assembler::Zero is the same (right?) and may be a bit clearer.

@@ +863,5 @@
> +    masm.j(Assembler::Equal, &loopEnd);
> +
> +    // FIXME: check for Rope.
> +
> +    // output = l1; result = l1

This seems more readable:

// output = lhsLength, lhsChar = lhsLengthAndFlags

@@ +884,5 @@
> +#else
> +    Label lhsGErhs;
> +    masm.j(Assembler::GreaterThanOrEqual, &lhsGErhs);
> +    masm.addPtr(output, length);
> +    masm.bind(&lhsGErhs);

I'd just get rid of the ARM path. It's not super-hot code (since it's outside the loop) and I don't think it'd be measurable.

@@ +893,5 @@
> +    masm.j(Assembler::Equal, &lhsSkipEnsureLinear);
> +    ool = new OutOfLineEnsureLinear(lir, lhs);
> +    if (!addOutOfLineCode(ool))
> +        return false;
> +    masm.bind(&lhsSkipEnsureLinear);

You can get rid of the lhsSkipEnsureLinear/rhsSkipEnsureLinear label and directly jump to the OOL path instead:

masm.j(Assembler::NotEqual, ool->entry());

@@ +903,5 @@
> +    ool = new OutOfLineEnsureLinear(lir, rhs);
> +    if (!addOutOfLineCode(ool))
> +        return false;
> +    masm.bind(&rhsSkipEnsureLinear);
> +    masm.loadPtr(Address(rhs, JSString::offsetOfChars()), rhs);

It's not safe to clobber lhs and rhs, other instructions may use these registers too. Not sure if there's an easy fix without requiring more temps, maybe you could load into lhsChar/rhsChar instead and then in the loop use

masm.load16(Address(lhsChar, 0), output);
masm.subPtr(Address(rhsChar, 0), output);

or something. Then you also don't need the movePtr(lhsChar, output)

@@ +913,5 @@
> +    masm.ma_ldrh(EDtrAddr(lhs, EDtrOffImm(0)), lhsChar);
> +    masm.ma_ldrh(EDtrAddr(rhs, EDtrOffImm(0)), rhsChar);
> +#else
> +    masm.load16(Address(lhs, 0), lhsChar);
> +    masm.load16(Address(rhs, 0), rhsChar);

Please get rid of the ARM special-case by implementing load16 on ARM (if it doesn't already exist).

@@ +923,5 @@
> +    masm.subPtr(rhsChar, lhsChar);
> +    masm.j(Assembler::NotEqual, &loopRes);
> +
> +    masm.subPtr(Imm32(1), length);
> +    masm.j(Assembler::NotEqual, &loopStart);

Can you use Assembler::NonZero here? It seems a bit more readable.

::: js/src/ion/TypePolicy.cpp
@@ +140,5 @@
>          MInstruction *replace;
>  
>          // See BinaryArithPolicy::adjustInputs for an explanation of the following
> +        if (specialization_ == MIRType_String)
> +            return false;

This seems wrong, you'll probably want to use something like this instead:

if (specialization_ == MIRType_String) {
    JS_ASSERT(in->type() == MIRType_Value);
    replace = MUnbox::New(in, MIRType_String, MUnbox::Infallible)
} else {
    // ... handle the int/double case ...
}
// ... insert replace ...

Comment 5

[Tom S [:evilpie]]

Stealing, because I need that to simplify 725966.

Comment 6

[Tom S [:evilpie]]

Attachment: WIP

I went a totally different way. I only handle equality comparisons, because they are simpler, but you could easily extend my current approach for the relational case. I am also not doing any inline compares, because JM doesn't have them, and this is not really meant for speed improvements.

Local jit-tests are totally busted here, because of e4x it seems.

Comment 7

[Tom S [:evilpie]]

Comment on attachment 631063 [details] [diff] [review]
WIP

After this passed make check locally asking for review. One thing, I wanted to mention, the JM implementation of this optimized for constant strings, this might be a reasonable thing to do, but it makes the code more complex and only avoids one test and jump.

Comment 8

[Jan de Mooij [:jandem]]

Comment on attachment 631063 [details] [diff] [review]
WIP

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

Nice work, r=me with comments addressed. Please add some atom/non-atom tests to jit-test/tests/ion/*.

::: js/src/ion/CodeGenerator.cpp
@@ +1218,5 @@
> +
> +    OutOfLineCode *ool = NULL;
> +    if (op == JSOP_EQ || op == JSOP_STRICTEQ) {
> +        ool = oolCallVM(stringsEqualInfo, lir, (ArgList(), left, right),  StoreRegisterTo(output));
> +    } else {

JS_ASSERT(op == JSOP_NE || op == JSOP_STRICTNE);

To ensure we don't end up with JSOP_GT or something here.

@@ +1228,5 @@
> +
> +    Label notPointerEqual, done;
> +    // Fast path for identical strings
> +    masm.cmpPtr(left, right);
> +    masm.j(Assembler::NotEqual, &notPointerEqual);

This can be masm.branchPtr(Assembler::NotEqual, left, right, &notPointerEqual);

@@ +1230,5 @@
> +    // Fast path for identical strings
> +    masm.cmpPtr(left, right);
> +    masm.j(Assembler::NotEqual, &notPointerEqual);
> +    masm.move32(Imm32(op == JSOP_EQ || op == JSOP_STRICTEQ), output);
> +    masm.jmp(&done);

s/jmp/jump, to avoid breaking ARM.

@@ +1248,5 @@
> +                      atomMask, ool->entry());
> +
> +    masm.cmpPtr(left, right);
> +
> +    Label notEqual;

You can just do 

masm.cmpPtr(left, right);
emitSet(Assembler::Equal, output);

On x86/x64, emitSet can use setcc in some cases (and the ARM implementation is also pretty neat).

Comment 9

[Tom S [:evilpie]]

http://hg.mozilla.org/projects/ionmonkey/rev/2235fddebe47

Fixed two small problems and discussed these with jandem on IRC. (Some unboxing was needed in the ComparePolicy, and we made some comment/code a little bit easier to understand in visitCompare)

Comment 10

[David Anderson [:dvander] - inactive, e-mail if emergency]

backing out due to red: https://hg.mozilla.org/projects/ionmonkey/rev/2235fddebe47

Comment 11

[Tom S [:evilpie]]

https://hg.mozilla.org/projects/ionmonkey/rev/c786d52a0e61
Okay fixed the obvious problems with x86 and arm.