807461 - IonMonkey: Add support for JSOP_CONDSWITCH.

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicolas B. Pierron [:nbp]]

This prevent the compilation of one hot function in PdfJS (octane).

[Scripts] Analyzing script pdfjs.js:26618 (0x7f4a00bcb988) (usecount=10246) (maxloopcount=42)
[Abort] Unsupported opcode: condswitch (line 26626)
[Abort] aborted @ pdfjs.js:26626
[Abort] Builder failed to build.
[Abort] Disabling Ion compilation of script pdfjs.js:26618

Comment 1

[Nicolas B. Pierron [:nbp]]

Attachment: IonMonkey: Add support for JSOP_CONDSWITCH

This patch does bring any noticeable performance boost, but it makes functions using JSOP_CONDSWITCH compile with IonMonkey. In addition it opens the field for future optimizations related to sequences of string comparisons, especially important in case of lexers (as used in pdfjs).

Comment 2

[Hannes Verschore [:h4writer]]

Comment on attachment 687475 [details] [diff] [review]
IonMonkey: Add support for JSOP_CONDSWITCH

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

Are there no testcases you encountered why you had to change some logic in this patch? I would prefer to have them added. Just if somebody doesn't get the reason why something was done and does it faulty, hopefully the testcase will trip.

There is a lot of logic in processCondSwitchCase. I would prefer to do more in jsop_condswitch() in order to keep this simpler. 
Also I want only jsop_condswitch to use sourceNotes. Would it be possible to create all blocks in jsop_condswitch and to make processCondSwitchCase resemble processNextLookupSwitchCase?

I would also rename everything you called Case to Cond(ition) and every blockEnd to body. I think this is easier to understand, because "Case" is also used for the body by lookup/table switch and makes it confusing.

::: js/src/ion/IonBuilder.cpp
@@ +32,2 @@
>      backgroundCodegen_(NULL),
> +    recompileInfo(cx->compartment->types.compiledInfo),

Huh? I don't think this need to be in this patch. FYI this is also already the sequence on Mozilla-inbound ... ?

@@ +1190,5 @@
>        case CFGState::LOOKUP_SWITCH:
>          return processNextLookupSwitchCase(state);
>  
> +      case CFGState::COND_SWITCH_CASE:
> +        return processCondSwitchCase(state);

processCondSwitchCond, see comment later on

@@ +1193,5 @@
> +      case CFGState::COND_SWITCH_CASE:
> +        return processCondSwitchCase(state);
> +
> +      case CFGState::COND_SWITCH_BLOCK:
> +        return processCondSwitchBlockEnd(state);

processCondSwitchBody, see comment later on

@@ +1853,5 @@
> +            state.condswitch.exitBlock = newBlock(current, target);
> +            if (!state.condswitch.exitBlock)
> +                return ControlStatus_Error;
> +            current->end(MGoto::New(state.condswitch.exitBlock));
> +        }

If possible I would suggest to use "new DeferredEdge" here, just like table/lookup switch. This would also remove this logic here ...

@@ +2440,2 @@
>          return ControlStatus_Error;
>  

This doesn't look like being part of the implementation of condswitch. If this needs to get fixed, I suggest an separate bug.

@@ +2719,5 @@
> +    FixedList<MBasicBlock *> &bodies = *state.condswitch.bodies;
> +    uint32 &currentIdx = state.condswitch.currentIdx;
> +
> +    // This is not the last block.
> +    if (currentIdx < bodies.length()) {

Add a function processCondSwitchEnd that gets called if (currentIdx >= bodies.length()), just like tableswitch/lookupswitch and put there the logic to terminate cond switch. There should createBreakCatchBlock be called to create the jumps from breaks to block from DeferredEdge's

::: js/src/ion/IonBuilder.h
@@ +71,5 @@
>              FOR_LOOP_UPDATE,    // for (; ; x) { }
>              TABLE_SWITCH,       // switch() { x }
>              LOOKUP_SWITCH,      // switch() { x }
> +            COND_SWITCH_CASE,   // switch() { case X: ... }
> +            COND_SWITCH_BLOCK,  // switch() { case ...: X }

Please rename to the following. Follows the naming the loops get... and I think less confusing ;)
COND_SWITCH_COND
COND_SWITCH_BODY

@@ +149,5 @@
> +                uint32 defaultIdx;
> +
> +                // Block immediately after the switch.
> +                jsbytecode *exitpc;
> +                MBasicBlock *exitBlock;

If possible I would prefer to have DeferredEdge *breaks here. To be more similar with table/lookup switch

Comment 3

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #2)
> There is a lot of logic in processCondSwitchCase. I would prefer to do more
> in jsop_condswitch() in order to keep this simpler. 
> Also I want only jsop_condswitch to use sourceNotes. Would it be possible to
> create all blocks in jsop_condswitch and to make processCondSwitchCase
> resemble processNextLookupSwitchCase?

Sadly now, I tried to do it by alternating between the case condition and the body block, but the default can be at a location which is not necessary the end of the switch body.  So to maintain RPO all case conditions basic block*s* have to be produced before all bodies, and the easiest way to do so was to first iterate on all cases and then on all bodies.  We need to handle:

switch(x) { 
  case (f() ? 0 : 1):
    print(1);
}

In which case we need to produce complex code for case conditions, so we just cannot follow the lookup siwtch way.

By the processNextLookupSwitchCase only handle the bodies, because the cases are dispatched ahead of time.

> ::: js/src/ion/IonBuilder.cpp
> @@ +32,2 @@
> >      backgroundCodegen_(NULL),
> > +    recompileInfo(cx->compartment->types.compiledInfo),
> 
> Huh? I don't think this need to be in this patch. FYI this is also already
> the sequence on Mozilla-inbound ... ?

I think it is on inbound, but I haven't merge with m-c yet, and these small warning fixes don't need to have their own patch / bug, so I am usually putting them with other patches.

Comment 4

[Nicolas B. Pierron [:nbp]]

Attachment: Add support for JSOP_CONDSWITCH

Delta:
- Use DefferedEdge for the exit block.
- Share the end logic between the 3 switch implementations.
- Add test case in the patch.

Comment 5

[Hannes Verschore [:h4writer]]

Comment on attachment 688073 [details] [diff] [review]
Add support for JSOP_CONDSWITCH

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

Looks much better already.

Still, I'm not totally convinced with the code in jsop_condswitch and processCondSwitchCase,
but now I've got a clear picture of what is required and how to achieve it ;).

1) Use Variable length list for "state.condswitch.bodies"
2) Remove the code that counts "nbBlocks" and "defaultIdx" in jsop_condswitch
3) Remove "state.condswitch.lastTarget" and "state.condswitch.currentIdx"
4) Add "state.condswitch.defaultIdx = -1"

Every time you visit "processCondSwitchCase":
MBasicBlock *prevBody = bodies[bodies.size()-1];
jsbytecode *lastTarget = prevBody.pc();

/* Create/take the body block of this case */

// Take the previous block as the body block
MBasicBlock *bodyBlock = prevBody;

// If this new case doesn't aliases the previous body block, create a new body block
jsbytecode *bodyTarget = pc + GetJumpOffset(pc);
if (lastTarget < bodyTarget) {
   // When the default has a distinct body (i.e. doesn't aliases another case),
   // an extra place should be left open for the default body.
   if (lastTarget < defaultTarget && defaultTarget < bodyTarget) {
      state.condswitch.defaultBlock = bodies.size();
      bodies.append(NULL);
   }

   // If this case aliases the default body, save position
   if (state.condswitch.defaultBlock == -1 && bodyTarget == defaultTarget)
      state.condswitch.defaultBlock = bodies.size();

   bodyBlock = ...;
   bodies.append(bodyBlock);
}

/* Create/take successor of when case condition fails */

MBasicBlock *successor = NULL;
if (successorIsDefault) {
  if (state.condswitch.defaultBlock == -1) {
    state.condswitch.defaultBlock = bodies.size();
    bodies.append(...);
  }
  successor = bodes[state.condswitch.defaultBlock];
} else {
  successor = new ...;
}

I hope you understand it? Else feel free to ping me on irc ;).
Because these are still some big changes, I'm not going to give r+ yet. I want to see it first.
But with these adjustments it almost certainly an r+ ;)

::: js/src/ion/IonBuilder.cpp
@@ +1197,5 @@
>        case CFGState::LOOKUP_SWITCH:
>          return processNextLookupSwitchCase(state);
>  
> +      case CFGState::COND_SWITCH_CASE:
> +        return processCondSwitchCase(state);

Oh right, COND_SWITCH_COND sounds strange, with the double COND in it. I'm fine with the *_CASE

@@ +1786,5 @@
> +        breaks = &state.condswitch.breaks;
> +    else {
> +        JS_NOT_REACHED("Unexpected switch state.");
> +        return ControlStatus_Error;
> +    }

Could this be a switch? (A switch in our switch code :D)

@@ +1797,5 @@
>  }
>  
>  IonBuilder::ControlStatus
> +IonBuilder::processSwitchEnd(DeferredEdge *breaks, jsbytecode *exitpc)
> +{

Cool!

@@ +2460,5 @@
> +    jssrcnote *sn = info().getNote(cx, pc);
> +
> +    // Get the default and exit pc
> +    jsbytecode *exitpc = pc + js_GetSrcNoteOffset(sn, 0);
> +    jsbytecode *firstCase = pc + js_GetSrcNoteOffset(sn, 1);

Code and comment don't agree. Get default pc, but we take first case.

@@ +2515,5 @@
> +        }
> +
> +        if (lastTarget < defaultTarget)
> +            defaultIdx = nbBlocks++;
> +    }

This is a awful lot of code, just to know "nbBlocks" and "defaultIdx". Can we do this differentely?

@@ +2564,5 @@
> +    jssrcnote *sn = info().getNote(cx, pc);
> +    ptrdiff_t off = js_GetSrcNoteOffset(sn, 0);
> +    jsbytecode *nextCasePc = off ? pc + off : GetNextPc(pc);
> +    bool isNextDefault = JSOp(*nextCasePc) == JSOP_DEFAULT;
> +    JS_ASSERT(JSOp(*nextCasePc) == JSOP_CASE || isNextDefault);

I withdraw my earlier statement. This is indeed the right place to get the source note information

@@ +2566,5 @@
> +    jsbytecode *nextCasePc = off ? pc + off : GetNextPc(pc);
> +    bool isNextDefault = JSOp(*nextCasePc) == JSOP_DEFAULT;
> +    JS_ASSERT(JSOp(*nextCasePc) == JSOP_CASE || isNextDefault);
> +
> +    // Allocate the block of the matching case.

// Allocate the block of the matching case. I.e. the body of the case.

@@ +2595,5 @@
> +        return ControlStatus_Error;
> +
> +    state.condswitch.lastTarget = bodyTarget;
> +
> +    // Allocate the non-matching case.

// Allocate the non-matching case. I.e.:
// - The next block containing the condition test of the case 
// - In case of default, the body block of the default case

@@ +2641,5 @@
> +        if (!isCaseNew && !caseBlock->addPredecessorPopN(current, (isNextDefault ? 1 : 0)))
> +            return ControlStatus_Error;
> +    }
> +
> +    if (isNextDefault) {

Can this be factored out to processCondSwitchBodyStart

@@ +2672,5 @@
> +}
> +
> +IonBuilder::ControlStatus
> +IonBuilder::processCondSwitchBody(CFGState &state)
> +{

Looks fine

Comment 6

[Hannes Verschore [:h4writer]]

Comment on attachment 688073 [details] [diff] [review]
Add support for JSOP_CONDSWITCH

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

Two notes got lost in my previous review ...

::: js/src/ion/IonBuilder.cpp
@@ +2563,5 @@
> +    // Fetch the next case.
> +    jssrcnote *sn = info().getNote(cx, pc);
> +    ptrdiff_t off = js_GetSrcNoteOffset(sn, 0);
> +    jsbytecode *nextCasePc = off ? pc + off : GetNextPc(pc);
> +    bool isNextDefault = JSOp(*nextCasePc) == JSOP_DEFAULT;

s/isNextDefault/successorIsDefault/ or "nextCaseIsDefault"

@@ +2597,5 @@
> +    state.condswitch.lastTarget = bodyTarget;
> +
> +    // Allocate the non-matching case.
> +    bool isCaseNew = false;
> +    MBasicBlock *caseBlock = NULL;

I think "successor" would be a better name, because "case conditions" and also the "default block" get's here.
Or "notMatchingSuccessor" or something.

Comment 7

[Nicolas B. Pierron [:nbp]]

Attachment: Add support for JSOP_CONDSWITCH

Delta:
- Replace the second loop which was trying to identify precisely the number of bodies by an over estimation which is at most off by 1 compared to the real number of bodies.  This estimation is computed in the first loop which is looking up the default target.
- Use the currentIdx as bodiesSize in processCondSwitchCase, to fill the body vector and assert that we are correctly off-by-1, as recommended in previous reviews.
- Call processCondSwitchBody at the end of processCondSwitchCase to handle the first case instead of duplicating everything.  This makes a correct RPO by moving the first block to the end when there is only one body. (*)
- Do not do a strict equality when the default case is aliasing the last case body.  This cause some issues in later phases because the block has 2 times the same predecessor. (*)

(*) Test cases are already present in the test suite.

Comment 8

[Hannes Verschore [:h4writer]]

Comment on attachment 688489 [details] [diff] [review]
Add support for JSOP_CONDSWITCH

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

Looks good!  Almost all comments are variable name changes and comment adjustments.

Can you also add a testcase has a condswitch with a function in it's case that get's inlined?
I think the code handles this correct, but it can't hurt to have such a testcase in the tree.

::: js/src/ion/IonBuilder.cpp
@@ +1624,5 @@
>      JS_ASSERT(state.state == CFGState::LOOKUP_SWITCH);
>  
>      size_t curBlock = state.lookupswitch.currentBlock;
>      IonSpew(IonSpew_MIR, "processNextLookupSwitchCase curBlock=%d", curBlock);
>      

Nit: remove white space (not added by this commit)

@@ +2463,5 @@
> +    jsbytecode *exitpc = pc + js_GetSrcNoteOffset(sn, 0);
> +    jsbytecode *firstCase = pc + js_GetSrcNoteOffset(sn, 1);
> +
> +    // Get the pc of the default case by reading the source notes of all case
> +    // statements, and over-estimate by at most 1 the number of bodies.

Change comment to something like:
// Iterate all cases in the condswitch
// - to get the default case. (is always emitted as the last case)
// - to get an estimate of needed body blocks 
//   (will be correct or 1 to much, when default get's aliased by another case)

@@ +2464,5 @@
> +    jsbytecode *firstCase = pc + js_GetSrcNoteOffset(sn, 1);
> +
> +    // Get the pc of the default case by reading the source notes of all case
> +    // statements, and over-estimate by at most 1 the number of bodies.
> +    jsbytecode *defaultCase = firstCase;

Use "curCase" or something. It is strange to read the while loop, because it actually never is the default case.

@@ +2479,5 @@
> +        JS_ASSERT(pc < defaultCase && defaultCase <= exitpc);
> +
> +        // Count non-aliased cases.
> +        jsbytecode *curTarget = GetJumpOffset(defaultCase) + defaultCase;
> +        nbBodies += (lastTarget < curTarget);

I would prefer an

@@ +2484,5 @@
> +        lastTarget = curTarget;
> +    }
> +    JS_ASSERT(JSOp(*defaultCase) == JSOP_DEFAULT);
> +    jsbytecode *defaultTarget = GetJumpOffset(defaultCase) + defaultCase;
> +    JS_ASSERT(defaultCase < defaultTarget && defaultTarget <= exitpc);

Add comment above the first assert:
// The current case points now to the default case

@@ +2524,5 @@
> +    JS_ASSERT(current);
> +    JS_ASSERT(JSOp(*pc) == JSOP_CASE);
> +    FixedList<MBasicBlock *> &bodies = *state.condswitch.bodies;
> +    jsbytecode *defaultTarget = state.condswitch.defaultTarget;
> +    uint32 &bodiesSize = state.condswitch.currentIdx;

I still would call it currentBody or currentIdx ;)

@@ +2535,5 @@
> +    bool nextCaseIsDefault = JSOp(*nextCasePc) == JSOP_DEFAULT;
> +    JS_ASSERT(JSOp(*nextCasePc) == JSOP_CASE || nextCaseIsDefault);
> +
> +    // Allocate the block of the matching case.
> +    bool isBodyNew = false;

s/isBodyNew/addedNewBodyBlock/

@@ +2548,5 @@
> +            // If the default body does not alias any and it would be allocated
> +            // later and stored in the defaultIdx location.
> +            if (defaultTarget < bodyTarget)
> +                bodiesSize++;
> +        }

Could this case be separated?
- An if for when default body is in the middle (and an empty body get's added)
- An if for when default body is aliasing (and when we only set state.condswitch.defaultIdx)

I find it confusing how it is done here.

@@ +2567,5 @@
> +
> +    lastTarget = bodyTarget;
> +
> +    // Allocate the non-matching case.
> +    bool isCaseNew = false;

s/isCaseNew/addedCaseBlock/

@@ +2568,5 @@
> +    lastTarget = bodyTarget;
> +
> +    // Allocate the non-matching case.
> +    bool isCaseNew = false;
> +    MBasicBlock *caseBlock = NULL;

s/caseBlock/nonMatchingBlock/

@@ +2573,5 @@
> +    if (!nextCaseIsDefault) {
> +        isCaseNew = true;
> +        // Pop the case operand.
> +        caseBlock = newBlockPopN(current, GetNextPc(pc), 1);
> +    } else {

Add comment:
// nonMatchingBlock will directly go to the body of the default case.
// Create the default body if that hasn't been done yet.

Comment 9

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #8)
> @@ +2479,5 @@
> > +        JS_ASSERT(pc < defaultCase && defaultCase <= exitpc);
> > +
> > +        // Count non-aliased cases.
> > +        jsbytecode *curTarget = GetJumpOffset(defaultCase) + defaultCase;
> > +        nbBodies += (lastTarget < curTarget);
> 
> I would prefer an

an if? I've put an if in the final patch.

> @@ +2535,5 @@
> > +    bool nextCaseIsDefault = JSOp(*nextCasePc) == JSOP_DEFAULT;
> > +    JS_ASSERT(JSOp(*nextCasePc) == JSOP_CASE || nextCaseIsDefault);
> > +
> > +    // Allocate the block of the matching case.
> > +    bool isBodyNew = false;
> 
> s/isBodyNew/addedNewBodyBlock/

I am not a big fan of this naming. I changed it to bodyIsNew, such as all variables related to the body are starting with body.

> @@ +2567,5 @@
> > +
> > +    lastTarget = bodyTarget;
> > +
> > +    // Allocate the non-matching case.
> > +    bool isCaseNew = false;
> 
> s/isCaseNew/addedCaseBlock/

same thing, I changed it to caseIsNew, which seems more readable in the if statements.

> @@ +2568,5 @@
> > +    lastTarget = bodyTarget;
> > +
> > +    // Allocate the non-matching case.
> > +    bool isCaseNew = false;
> > +    MBasicBlock *caseBlock = NULL;
> 
> s/caseBlock/nonMatchingBlock/

The caseBlock block is by default the non-matching block.  And the “default” case is also a caseBlock. I don't think we need a longer name, which I find more confusing for understanding the loop. I added the following comments to clarify:

    // Allocate the block of the non-matching case.  This can either be a normal
    // case or the default case.
    …

    } else {
        // The non-matching case is the default case, which jump directly to its
        // body. Skip the creation of a default case block and directly create
        // the default body if it does not alias any previous body.

Comment 10

[Nicolas B. Pierron [:nbp]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/550fa41ac371

Comment 11

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/550fa41ac371