Last Comment Bug 701963 - IonMonkey: Compile JSOP_LOOKUPSWITCH
: IonMonkey: Compile JSOP_LOOKUPSWITCH
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: ---
Assigned To: Kannan Vijayan [:djvj]
:
Mentors:
Depends on:
Blocks: 684381
  Show dependency treegraph
 
Reported: 2011-11-11 17:59 PST by Nicolas B. Pierron [:nbp]
Modified: 2012-05-09 08:21 PDT (History)
6 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Patch 1 (29.68 KB, patch)
2012-04-27 10:36 PDT, Kannan Vijayan [:djvj]
no flags Details | Diff | Splinter Review
Patch v2 (19.40 KB, patch)
2012-05-03 11:59 PDT, Kannan Vijayan [:djvj]
jdemooij: review+
Details | Diff | Splinter Review

Description Nicolas B. Pierron [:nbp] 2011-11-11 17:59:01 PST
Necessary for benchmarks.
Comment 1 Kannan Vijayan [:djvj] 2012-04-27 10:36:15 PDT
Created attachment 619095 [details] [diff] [review]
Patch 1

Patch is pretty straightforward.  It follows the overall strategy of TABLESWITCH, with a few changes to account for multiple conditional blocks forming the backbone of the LOOKUPSWITCH.  MLookupSwitch is actually not a distinct MInstruction - it's a subclass of MGoto with some extra bookkeeping info, and it devolves into a GOTO to the first conditional block.

Also adding a test to jit-tests that generates a large number of permutations of possible switch-statement structures, generates 'eval'ed JS code for that test case, and then runs the eval-ed JS code and compares it against a manually-interpreted run of that switch statement.  Jit-test currently takes about 4 seconds to run on my macbook, and tests about 400 different case variants.
Comment 2 Hannes Verschore [:h4writer] 2012-04-27 13:25:56 PDT
As far as I see the struct "state.tableswitch" and "state.lookupswitch" contain the same information. Can't we merge them into the same struct? E.g. state.switch or something?
Comment 3 Kannan Vijayan [:djvj] 2012-04-30 08:39:15 PDT
Structurally they're identical.  I wondered about whether to merge them or not.  I ended up using different structs for them primarily because of the difference in the type of 'ins' (MTableSwitch vs. MLookupSwitch), and what that implied.

They're conceptually different things that happen to have a structural similarity: the first being a compare-and-jump, the second being a series-of-compares and distinct jumps.

I felt that merging the state structure in this case would confuse things.
Comment 4 Jan de Mooij [:jandem] 2012-05-01 06:06:01 PDT
Comment on attachment 619095 [details] [diff] [review]
Patch 1

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

Wow, LOOKUPSWITCH is indeed pretty complicated. I skipped some parts that are likely going to change/move so another review would be good.

::: js/src/ion/IonBuilder.cpp
@@ +1453,5 @@
> +                break;
> +
> +            // Add MTest to cond block, finishing it.
> +            // The failure block is either the next cond, or the default block.
> +            if (i == ins->numConds()-1) {

Nit: spaces around '-'.

@@ +1460,5 @@
> +                else
> +                    condInfo.cond->end(MTest::New(condInfo.cmp, curBody, ins->defaultBody()));
> +            } else {
> +                condInfo.cond->end(MTest::New(condInfo.cmp, curBody, ins->getCond(i+1).cond));
> +            }

Can we add these MTest instructions in IonBuilder::lookupSwitch? It will make integration with chunked compilation a lot easier: if a chunk ends in the middle of a lookupswitch, we can just add outgoing edges/jumps to all body blocks we still have to finish. Furthermore, you no longer have to store a list of condition blocks/instructions when IonBuilder::lookupSwitch is done.

@@ +1471,5 @@
> +    }
> +
> +    curBlock++;
> +    state.lookupswitch.currentBlock = curBlock;
> +    // Test if there are still unprocessed successors (cases/default)

Nit: empty line before the comment.

@@ +1492,5 @@
> +
> +    // If this is the last successor the block should stop at the end of the tableswitch
> +    // Else it should stop at the start of the next successor
> +    if (curBlock+1 < ins->numBodies())
> +        state.stopAt = ins->getBody(curBlock+1)->pc();

Nit: spaces around '+'.

@@ +2056,4 @@
>          return ControlStatus_Error;
>  
>      // Use a state to retrieve some information
> +    CFGState state = CFGState::TableSwitch(exitpc, tableswitch);

Nice.

@@ +2103,5 @@
> +    // Get ncases, which will be >= 1, since a zero-case switch
> +    // will get byte-compiled into a TABLESWITCH.
> +    jsbytecode *pc2 = pc;
> +    pc2 += JUMP_OFFSET_LEN;
> +    int ncases = GET_UINT16(pc2);

Nit: "unsigned ncases".

@@ +2112,5 @@
> +    // Iterate through all cases, and fill 'bodies' with MBasicBlocks corresponding to
> +    // distinct bodies, and 'conds' with CondInfos corresponding to every non-default
> +    // "case" statement.
> +    MBasicBlock *bodies[ncases+1];
> +    MLookupSwitch::CondInfo conds[ncases];

G++ accepts variable-length arrays as an extension but it's not standard C++ (though valid C99) and won't work with MSVC (http://stackoverflow.com/a/7627265). If you use a FixedList<MBasicBlock *> here we also don't have to worry about stack overflow and get free bounds check asserts in debug builds.

@@ +2114,5 @@
> +    // "case" statement.
> +    MBasicBlock *bodies[ncases+1];
> +    MLookupSwitch::CondInfo conds[ncases];
> +    int default_body_idx = -1;
> +    bool default_shared = false;

Style nit: camelCase for these and other variables.

@@ +2116,5 @@
> +    MLookupSwitch::CondInfo conds[ncases];
> +    int default_body_idx = -1;
> +    bool default_shared = false;
> +    int nbodies = 0;
> +    for (int i = 0; i < ncases; i++) {

Nit: i and nbodies should be unsigned.

@@ +2123,5 @@
> +        jsbytecode *casepc = pc + GET_JUMP_OFFSET(pc2);
> +        pc2 += JUMP_OFFSET_LEN;
> +        JS_ASSERT(casepc > pc && casepc <= exitpc);
> +        JS_ASSERT(i == 0 || bodies[conds[i-1].bodyIndex]->pc() <= casepc);
> +        JS_ASSERT(i == 0 || conds[i-1].bodyIndex == nbodies-1);

Nit: JS_ASSERT_IF(i > 0, bodies...);

@@ +2133,5 @@
> +
> +        MConstant *rval_ins = MConstant::New(rval);
> +        cond->add(rval_ins);
> +
> +        MCompare *cmp_ins = MCompare::New(ins, rval_ins, JSOP_EQ);

s/JSOP_EQ/JSOP_STRICTEQ since the comparison should be strict. The difference is observable in some cases (no pun intended..), can you add the following tests?

1) JSOP_EQ may be effectful is the value is an object:
--
function f(o) {
    switch (o) {
      case "foo":
        break;
    }
}
for (var i=0; i<50; i++)
    f({valueOf: function() { assertEq(0, 1); }});
--
2) String "123" should not match integer 123.
--
function f(x) {
    switch (x) {
      case "123":
        assertEq(0, 1);
        break;
    }
}
for (var i=0; i<50; i++)
    f(123);
--

@@ +2135,5 @@
> +        cond->add(rval_ins);
> +
> +        MCompare *cmp_ins = MCompare::New(ins, rval_ins, JSOP_EQ);
> +        cond->add(cmp_ins);
> +        resumeAfter(cmp_ins);

The MCompare has no observable side-effects since the comparison is strict and the case-value is always a number or string. In this case we want MCompare::getAliasSet to return None so that LICM/GVN can optimize more. Maybe check for strict equality op + known-primitive lhs/rhs type in MCompare::getAliasSet and remove the resumeAfter call here.

@@ +2139,5 @@
> +        resumeAfter(cmp_ins);
> +
> +        // create body block
> +        size_t body_idx;
> +        if (i == 0 || bodies[conds[i-1].bodyIndex]->pc() != casepc) {

Nit: spaces around '-' (and below).

::: js/src/ion/MIR.h
@@ +889,5 @@
>  
> +// LookupSwitch basically functions as a GOTO, as it'll just forward
> +// the computation onto the first conditional block in the switch
> +// statement.
> +class MLookupSwitch : public MGoto

Since IonBuilder is the only place where we need the extra data, it seems better to add it to CFGState (maybe add a pointer to a new struct if it increases "sizeof CFGState" a lot).

@@ +954,5 @@
> +        bodies_.append(body);
> +    }
> +
> +    void addDefault(int bodyIndex, bool shared) {
> +        JS_ASSERT(bodyIndex < (int)bodies_.length());

Looks like you can remove some casts if bodyIndex/defaultBodyIndex_ were unsigned/size_t.

@@ +971,5 @@
> +        conds_.append(info);
> +        if (cond_i == 0)
> +            setSuccessor(0, info.cond);
> +
> +        if (cond_i == 0 || conds_[cond_i-1].bodyIndex != info.bodyIndex) {

Nit: spaces around '-'.

::: js/src/jit-test/tests/ion/lookupswitch.js
@@ +1,1 @@
> +

I like the idea of generating tests for the various edge cases and combinations of them. However, for debugging test failures it would be a lot easier if we had a number of JS files (like tests/ion/lookupswitch/001.js). Adding 400 test files may be a bit excessive but maybe you can add multiple tests per file or something.

@@ +1,5 @@
> +
> +/** HELPERS **/
> +
> +function ASSERT(cond, msg) {
> +    if(!cond) { throw new Error("ASSERT FAILED: " + msg); }

Nit: assertEq(cond, true, msg);
Comment 5 Kannan Vijayan [:djvj] 2012-05-03 11:59:51 PDT
Created attachment 620801 [details] [diff] [review]
Patch v2

Second run.  Most of the logic has been pushed into the front-end IonBuilder::lookupSwitch() procedure.  Here's a sketch of some of the design decisions on this code.

1. Blocks may be shared, e.g.:
  case FOO:
  case BAR:
    // code
    // code
  case BAZ:
    // code

  In these cases we want to build a single codeblock for the conditionals of FOO and BAR.

2. The ending MTest can only be added to a conditional block once the next conditional block has been created, and ending MTest on the final conditional block can only be added after the default body block has been created.

For the above two reasons, the loop keeps track of the previous iteration's major components (cond block, body block, cmp instruction, body start pc, whether the previous case had a shared body, etc.) and uses them in the next iteration.

3. The default body block may be shared with the body of a 'case'.  This is tested for within the iteration loop in IonBuilder::lookupSwitch.  Also, the default body block may not occur at the end of the switch statements, and instead may occur in between.

For this reason, the default body may be created within the loop (when a regular body block is created, because the default body IS the regular body), or it will be created after the loop.  It must then still be inserted into the right location into the list of body blocks to process, which is done later in lookupSwitch.
Comment 6 Jan de Mooij [:jandem] 2012-05-08 05:06:34 PDT
Comment on attachment 620801 [details] [diff] [review]
Patch v2

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

Nice work, I like how IonBuilder::lookupSwitch does most of the work now, without getting too complicated.

r=me with comments below addressed + tests added.

::: js/src/ion/IonBuilder.cpp
@@ +1631,1 @@
>      state.tableswitch.breaks = new DeferredEdge(current, state.tableswitch.breaks);

Nit: indent the if body

@@ +2040,5 @@
> +    // CONST_1  : UINT32_INDEX          # case 1 constant index
> +    // OFFSET_1 : JUMP_OFFSET           # case 1 offset
> +    // ...
> +    // CONST_N  : UINT32_INDEX          # case N constant index
> +    // OFFSET_N : JUMP_OFFSET           # case N offset

Can you add (something like) comment 5 as a comment here? It gives a good overview and will help readers understand the meaning of prevShared etc.

@@ +2166,5 @@
> +    // Add edge from last conditional block to the default block
> +    if (defaultBody == prevBody) {
> +        // Last conditional block goes to default body on both comparison
> +        // success and comparison failure.
> +        prevCond->end(MGoto::New(defaultBody));

What happens to prevCmpIns in this case? I think the (unused) compare will be removed by DCE, but it would be good to check this.

@@ +2178,5 @@
> +    // it needs to be explicitly added as a predecessor now that it's finished.
> +    if (prevShared)
> +        prevBody->addPredecessor(prevCond);
> +
> +    // Walk through bodies in lookupswitch CFGState and uniqify them

It may be simpler to use a Vector in this function, so that we don't need this step. Before you add a new body to the vector we can check if it's equal to the last body, and at the end of the function we can copy all blocks from the Vector to CFGState's FixedList. This also allows us to remove state.uniqueBodies since we can use state.bodies.length() instead.

@@ +2179,5 @@
> +    if (prevShared)
> +        prevBody->addPredecessor(prevCond);
> +
> +    // Walk through bodies in lookupswitch CFGState and uniqify them
> +    unsigned int bodyI = 0;

Nit: bodyIdx or bodyIndex.

@@ +2200,5 @@
> +        // Move all the elements over to accomondate default body
> +        for (unsigned int i = uniqueBodies-1; i >= defaultBodyI; i++)
> +            (*state.lookupswitch.bodies)[i+1] = (*state.lookupswitch.bodies)[i];
> +        (*state.lookupswitch.bodies)[defaultBodyI] = defaultBody;
> +        uniqueBodies++;

If we use a Vector, we can just call insert() here.

::: js/src/ion/IonBuilder.h
@@ +160,5 @@
> +                // Deferred break and continue targets.
> +                DeferredEdge *breaks;
> +
> +                // Vector of body blocks to process
> +                FixedList<MBasicBlock *> *bodies;

This can be "FixedList<MBasicBlock *> bodies". FixedList is a pointer + size_t; if we remove the uniqueBodies member, "sizeof CFGState" stays the same.
Comment 7 Kannan Vijayan [:djvj] 2012-05-09 08:20:41 PDT
In answer to some questions:

(In reply to Jan de Mooij (:jandem) from comment #6)
> 
> What happens to prevCmpIns in this case? I think the (unused) compare will
> be removed by DCE, but it would be good to check this.

The MCompare in the case where it's unused (followed by a MGoto instead of MTest on the last conditional block) does NOT get eliminated by DCE.  I'm pretty sure this is because MCompare advertises itself as effectful even in the case where we're doing a JSOP_STRICTEQ.  This also forced me to throw in a resumeAfter after the cmp.

The question of whether MCompare is effectful with STRICTEQ is independent of this patch, so I chose not to address the problem in this case.

> This can be "FixedList<MBasicBlock *> bodies". FixedList is a pointer +
> size_t; if we remove the uniqueBodies member, "sizeof CFGState" stays the
> same.

I can't put a direct reference to FixedList<...> in the CFGState union because of C++'s whole no classes-with-nontrivial-constructors in unions rule.  I'm still keeping a pointer and doing an alloc in the CFGState::LookupSwitch constructor code.

--
On another note, thanks for the Vector suggestion.  That did, in fact, clean up the code, and eliminate several extraneous lines of crap.

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