Last Comment Bug 677774 - IM: Implement conditional operators
: IM: Implement conditional operators
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: x86 Mac OS X
: -- normal (vote)
: ---
Assigned To: Andrew Scheff
:
Mentors:
Depends on: 679804 721438
Blocks: 682060
  Show dependency treegraph
 
Reported: 2011-08-09 17:05 PDT by Andrew Scheff
Modified: 2012-01-26 09:59 PST (History)
3 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Adds MRelationalCompare. lt, gt, le, ge now supported in MIR (5.12 KB, patch)
2011-08-11 16:20 PDT, Andrew Scheff
dvander: review+
Details | Diff | Review
MCompare now with type analysis stuff (8.96 KB, patch)
2011-08-12 19:06 PDT, Andrew Scheff
no flags Details | Diff | Review
Comments addressed (9.46 KB, patch)
2011-08-12 21:51 PDT, Andrew Scheff
no flags Details | Diff | Review
Made changes to type policy that we discussed (9.60 KB, patch)
2011-08-15 16:44 PDT, Andrew Scheff
no flags Details | Diff | Review
possibly last round of corrections (9.52 KB, patch)
2011-08-16 14:32 PDT, Andrew Scheff
dvander: review+
Details | Diff | Review
Lowering pass for MCompare (8.85 KB, patch)
2011-08-16 18:25 PDT, Andrew Scheff
dvander: review+
Details | Diff | Review
First iteration of code generation for conditional operators (12.79 KB, patch)
2011-08-19 11:35 PDT, Andrew Scheff
dvander: review+
Details | Diff | Review
Use conditional set to optimize compares with no branches (2.75 KB, patch)
2011-08-22 17:48 PDT, Andrew Scheff
no flags Details | Diff | Review
Use conditional set to optimize compares with no branches (4.68 KB, patch)
2011-08-23 15:52 PDT, Andrew Scheff
dvander: review+
Details | Diff | Review

Description Andrew Scheff 2011-08-09 17:05:11 PDT
I will implement conditional operators like <, >, <=, ==, you get the idea in IonMonkey
Comment 1 Andrew Scheff 2011-08-11 16:20:56 PDT
Created attachment 552537 [details] [diff] [review]
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] 2011-08-12 00:48:16 PDT
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 2011-08-12 11:51:00 PDT
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] 2011-08-12 11:59:09 PDT
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 2011-08-12 12:09:51 PDT
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 2011-08-12 19:06:42 PDT
Created attachment 552821 [details] [diff] [review]
MCompare now with type analysis stuff

Adds MCompare and ComparePolicy. I *think* this is how it should look...
Comment 7 David Anderson [:dvander] 2011-08-12 19:21:35 PDT
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 2011-08-12 21:51:57 PDT
Created attachment 552832 [details] [diff] [review]
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 2011-08-15 16:44:54 PDT
Created attachment 553307 [details] [diff] [review]
Made changes to type policy that we discussed

how about now?
Comment 10 David Anderson [:dvander] 2011-08-15 19:08:17 PDT
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 2011-08-16 14:32:25 PDT
Created attachment 553590 [details] [diff] [review]
possibly last round of corrections

Now, adjust inputs looks almost exactly like BinaryArithPolicy's
Comment 12 David Anderson [:dvander] 2011-08-16 14:40:35 PDT
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 2011-08-16 15:11:49 PDT
Landed that patch, lowering comes next

http://hg.mozilla.org/projects/ionmonkey/rev/e029a3cf6a64
Comment 14 Andrew Scheff 2011-08-16 18:25:08 PDT
Created attachment 553648 [details] [diff] [review]
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] 2011-08-16 18:53:15 PDT
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 2011-08-17 15:27:52 PDT
Lowering landed.  Code generation for CompareI and CompareIAndBranch is next

http://hg.mozilla.org/projects/ionmonkey/rev/0c863aeb0f75
Comment 17 Andrew Scheff 2011-08-19 11:35:16 PDT
Created attachment 554482 [details] [diff] [review]
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] 2011-08-19 12:50:57 PDT
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 2011-08-19 13:41:57 PDT
Pushed.

http://hg.mozilla.org/projects/ionmonkey/rev/93a37c92967e
Comment 20 Andrew Scheff 2011-08-19 15:19:42 PDT
A couple quick fixes, added test cases as well.

http://hg.mozilla.org/projects/ionmonkey/rev/7732904d4c8d
Comment 21 Andrew Scheff 2011-08-22 17:48:52 PDT
Created attachment 555001 [details] [diff] [review]
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] 2011-08-22 19:24:42 PDT
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 2011-08-23 15:52:07 PDT
Created attachment 555234 [details] [diff] [review]
Use conditional set to optimize compares with no branches

With fixes we discuessed

Note You need to log in before you can comment on or make changes to this bug.