677774 - IM: Implement conditional operators

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andrew Scheff]

I will implement conditional operators like <, >, <=, ==, you get the idea in IonMonkey

Comment 1

[Andrew Scheff]

Attachment: Adds MRelationalCompare. lt, gt, le, ge now supported in MIR

No type inference/specialization yet, this patch just adds classes and constructors mostly

Comment 2

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

Comment on attachment 552537 [details] [diff] [review]
Adds MRelationalCompare. lt, gt, le, ge now supported in MIR

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

Should we call this MCompare instead? RelationalCompare is kind of long and we probably want it to include == and != later

Comment 3

[Andrew Scheff]

I was going under the assumption that they would require fairly different TypePolicys.. I guess its a tradeoff between longer class names and some extra casing in type analysis.  I could shorten class names to MRelCompare and MEqCompare?

Comment 4

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

That seems okay. Another option would be passing in the TypePolicy to the constructor, and saving it in the node. Up to you.

Comment 5

[Andrew Scheff]

After actually figuring out what the type policy for != and == would look like, I think they can go together in the same class

Comment 6

[Andrew Scheff]

Attachment: MCompare now with type analysis stuff

Adds MCompare and ComparePolicy. I *think* this is how it should look...

Comment 7

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

Comment on attachment 552821 [details] [diff] [review]
MCompare now with type analysis stuff

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

::: js/src/ion/MIR.cpp
@@ +462,5 @@
> +void
> +MCompare::infer(const TypeOracle::Binary &b)
> +{
> +    // Always a Boolean
> +    setResultType(MIRType_Boolean);

Set this in the constructor of the node, since the output doesn't change based on inference.

@@ +465,5 @@
> +    // Always a Boolean
> +    setResultType(MIRType_Boolean);
> +
> +    // If neither operand is an object, then we are idempotent
> +    if (!(b.lhs == MIRType_Object) && !(b.rhs == MIRType_Object))

simpler: (b.lhs != MIRTypeObject && b.rhs != MIRType_Object)

@@ +471,5 @@
> +
> +    // Set specialization
> +    if (b.lhs == MIRType_Int32 && b.rhs == MIRType_Int32) {
> +        specialization_ = MIRType_Int32;
> +    } else if (CoercesToDouble(b.lhs) && CoercesToDouble(b.rhs)) {

This check probably exists elsewhere too but it seems a little aggressive. For now we probably want ||, so (5.5 < 2) will specialize.

@@ +475,5 @@
> +    } else if (CoercesToDouble(b.lhs) && CoercesToDouble(b.rhs)) {
> +        specialization_ = MIRType_Double;
> +    } else {
> +        specialization_ = MIRType_None;
> +    }

No braces needed here, since all bodies are one-liners

::: js/src/ion/TypePolicy.cpp
@@ +152,5 @@
> +
> +    // If either input coerces to a double, we should respecialize to double
> +    if (CoercesToDouble(lhs->type()) || CoercesToDouble(rhs->type())) {
> +        specialization_ = MIRType_Double;
> +    }

No braces needed here

@@ +184,5 @@
> +
> +        // The type of the input must be an integer if it doesn't match
> +        // our specialization (which must be double).
> +        JS_ASSERT(in->type() == MIRType_Int32);
> +        MInstruction *replace = MToDouble::New(in);

This assert would trigger if you had (3.5 > 5). Here you want something similar to the Add policy:

  * If the input is a string or object, box it, then
  * If the input is not the specialization, insert ToInt32 or ToDouble
    depending on the specialization.

Comment 8

[Andrew Scheff]

Attachment: Comments addressed

I made use of: blah < MIRType_String... I think this is much more meaningful than the CoercesToDouble function.  Perhaps CoercesToDouble(type) should return type < MIRType_String?

Comment 9

[Andrew Scheff]

Attachment: Made changes to type policy that we discussed

how about now?

Comment 10

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

Comment on attachment 553307 [details] [diff] [review]
Made changes to type policy that we discussed

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

::: js/src/ion/TypePolicy.cpp
@@ +152,5 @@
> +
> +    // Check if any input would coerce to a double.
> +    if (CoercesToDouble(lhs->type()) || CoercesToDouble(rhs->type())) {
> +        specialization_ = MIRType_Double;
> +    }

No braces needed here.

@@ +186,5 @@
> +            replace = MUnbox::New(in, specialization_);
> +        else if (specialization_ == MIRType_Double)
> +            replace = MToDouble::New(in);
> +        else
> +            replace = MToInt32::New(in);

This won't work if the incoming type is an object, since MToInt32/Double() can't handle that. You want something like BinaryArithPolicy: if the type is object or string, box it. *then*, insert the conversion.

For example,
(obj < 5) should become: MCompare(MToInt32(MBox(obj)), MConstant(5))
(6.3 < 5) should become: MCompare(MConstant(6.3), MToDouble(MConstant(5)))

Sorry if this is confusing. The MToBlah opcodes weren't spec'd as of your patch since I forgot to land bug 677339, which I'll do now.

MToInt32: obj, string, undefined: not allowed
          null -> 0
          int32, bool -> int
          double -> int if fits in int
          value: deoptimize if obj, string, or undef

MToDouble: obj, string not allowed
           int32, double, bool -> double
           null -> 0
           undef -> NaN
           value: deoptimize if obj or string

The reason the box is necessary is just to make the IR cleaner. Otherwise, we would need an instruction which returns something but always deoptimizes, which is weird.

Comment 11

[Andrew Scheff]

Attachment: possibly last round of corrections

Now, adjust inputs looks almost exactly like BinaryArithPolicy's

Comment 12

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

Comment on attachment 553590 [details] [diff] [review]
possibly last round of corrections

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

Looks good, r=me with some nits

::: js/src/ion/MIR.cpp
@@ +462,5 @@
> +void
> +MCompare::infer(const TypeOracle::Binary &b)
> +{
> +    // Always a Boolean
> +    setResultType(MIRType_Boolean);

Not needed since it's in the ctor

@@ +466,5 @@
> +    setResultType(MIRType_Boolean);
> +
> +    // If neither operand is an object, then we are idempotent
> +    if (b.lhs != MIRType_Object && b.rhs != MIRType_Object)
> +        setIdempotent();

Would it be simpler to move setIdempotent() to...

@@ +473,5 @@
> +    if (b.lhs < MIRType_String && b.rhs < MIRType_String) {
> +        if (CoercesToDouble(b.lhs) || CoercesToDouble(b.rhs))
> +            specialization_ = MIRType_Double;
> +        else
> +            specialization_ = MIRType_Int32;

Here? And then you don't need the extra check.

@@ +476,5 @@
> +        else
> +            specialization_ = MIRType_Int32;
> +    }
> +    else
> +        specialization_ = MIRType_None;

House style is to brace all branches if one branch is braced,

  if (...) {
    ...
  } else {
    one-liner
  }

Comment 13

[Andrew Scheff]

Landed that patch, lowering comes next

http://hg.mozilla.org/projects/ionmonkey/rev/e029a3cf6a64

Comment 14

[Andrew Scheff]

Attachment: Lowering pass for MCompare

This patch adds a lowering pass and the discussed peephole optimization for the common case in which a compare is the input to a test instruction.

Comment 15

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

Comment on attachment 553648 [details] [diff] [review]
Lowering pass for MCompare

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

::: js/src/ion/Lowering.cpp
@@ +144,5 @@
>      if (opd->type() == MIRType_Undefined || opd->type() == MIRType_Null)
>          return add(new LGoto(ifFalse));
>  
> +    // Check if the operand for this test is a compare operation. If it is, we need to emit
> +    // an LCompare*AndBranch rather than an LTest*AndBranch

I would say s/need/want/, and note that it's to fuse the compare and jump.

@@ +156,5 @@
> +                                              ifTrue, ifFalse));
> +        else if (comp->specialization() == MIRType_Double)
> +            JS_ASSERT("LCompareDAndBranch NYI");
> +        else
> +            JS_ASSERT("LCompareVAndBranch NYI");

Brace this if-chain since one block is a multi-liner. You also might want to remove the elseif/else and just let it fall through for now - better to have worse codegen than an assert, file a follow-up bug, and reference it in a :TODO: comment.

@@ +193,5 @@
> +        return define(new LCompareI(comp->compareOp(), useRegister(left), use(right)), comp);
> +    else if (comp->specialization() == MIRType_Double)
> +        JS_ASSERT("LCompareD NYI");
> +    else
> +        JS_ASSERT("LCompareV NYI");

Here, I would remove the else if/else and just put a JS_NOT_REACHED("NYI"). In the interest of not adding more NYIs, would it be hard to do double comparisons as well? :)

::: js/src/ion/MIR.h
@@ +846,5 @@
> +    MIRType specialization() const {
> +        return specialization_;
> +    }
> +
> +    JSOp compareOp() const {

I think this is "jsop()" elsewhere - if so, probably want to use that for consistency.

Comment 16

[Andrew Scheff]

Lowering landed.  Code generation for CompareI and CompareIAndBranch is next

http://hg.mozilla.org/projects/ionmonkey/rev/0c863aeb0f75

Comment 17

[Andrew Scheff]

Attachment: First iteration of code generation for conditional operators

Here is a working implementation of code generation for LCompareI and LCompareIAndBranch with nothing fancy.  Looking for some feedback.  The todo list has optimizations with conditional set and predicting branches in loops.  Equality and doubles to come as well.

Comment 18

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

Comment on attachment 554482 [details] [diff] [review]
First iteration of code generation for conditional operators

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

::: js/src/ion/LIR-Common.h
@@ +244,5 @@
>  };
>  
>  class LCompareI : public LInstructionHelper<1, 2, 0>
>  {
> +    AssemblerX86Shared::Condition cond_;

This is in LIR-Common so this should be Assembler. I think it's safe to assume every architecture's Assembler will provide flags like "Equal" and "GreaterThan". So everywhere in this file you reference AssemblerX86Shared, just use Assembler instead.

::: js/src/ion/shared/CodeGenerator-x86-shared.cpp
@@ +143,5 @@
> +    const LAllocation *left = comp->getOperand(0);
> +    const LAllocation *right = comp->getOperand(1);
> +    LBlock *ifTrue = comp->ifTrue()->lir();
> +    LBlock *ifFalse = comp->ifFalse()->lir();
> +    AssemblerX86Shared::Condition cond = comp->condition();

You can just use "Assembler::"

@@ +152,5 @@
> +    // Take advantage of block fallthrough when possible
> +    if (isNextBlock(ifFalse)) {
> +        masm.j(cond, ifTrue->label());
> +    } else if (isNextBlock(ifTrue)) {
> +        masm.j(AssemblerX86Shared::inverseCondition(cond), ifFalse->label());

Same

Comment 19

[Andrew Scheff]

Pushed.

http://hg.mozilla.org/projects/ionmonkey/rev/93a37c92967e

Comment 20

[Andrew Scheff]

A couple quick fixes, added test cases as well.

http://hg.mozilla.org/projects/ionmonkey/rev/7732904d4c8d

Comment 21

[Andrew Scheff]

Attachment: Use conditional set to optimize compares with no branches

tiny optimization, use conditional set when possible.  Also this diff has the test cases which I forgot to include with the last patch

Comment 22

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

Comment on attachment 555001 [details] [diff] [review]
Use conditional set to optimize compares with no branches

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

::: js/src/ion/shared/CodeGenerator-x86-shared.cpp
@@ +131,5 @@
> +    masm.cmpl(ToRegister(left), ToOperand(right));
> +
> +    // If the register we're defining is a single byte register,
> +    // take advantage of the setCC instruction
> +    if (ToRegister(def).code() & Registers::SingleByteRegs) {

This test won't work because code() does not return a mask. You want something like:

GeneralRegisterSet(Registers::SingleByteRegs).has(ToRegister(def))

Comment 23

[Andrew Scheff]

Attachment: Use conditional set to optimize compares with no branches

With fixes we discuessed