1246116 - wasm: implement loop/break control flow opcodes

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Benjamin Bouvier [:bbouvier] (inactive)]

This includes:

- loop
- br
- brIf
- switch

The plan is:
1) to implement them in wasm
2) then to change the asm.js frontend to emit those instead of the current numerous JS specific opcodes

Comment 1

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: wip.patch

Just posting a first WIP, that can handle an infinite loop in wasm (loop) or an infinite while loop in asm.js. Still a lot of untested things, NYI things, TODO and things to fix to make it work properly. In the future, this patch will be split into 3 parts: asm.js / wasm text / wasmIonCompile, to make reviewing "easier".

Comment 2

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: wip.patch

This works for simple loops/breaks/continues, but there are issues whenever there's a nested loops and labels. Sigh.

Comment 3

[Benjamin Bouvier [:bbouvier] (inactive)]

Thinking a bit out loud:

- for labels, the previous WIP patch uses a feature of wasm which isn't in asm.js: each wasm block has a label to break out of it. So a labelled statement is generated as a Block containing a single statement, which is the labelled statement. There is then a one-to-one matching between Block and MBasicBlock.
- in most cases, this works fine, although 1) it sometimes creates empty unused blocks, if the statement is actually a block. 2) This doesn't work well with labelled continues, as we need to get the closest loop top's label for a continue label. This is done with a simple linear search that tries to find the loop top's label which is the closest to the label statement. It might be costly, though.
- do/while loops are much harder, as a "continue" (labelled or not) in a do/while loop goes to the condition before getting back to the body of the do/while loop. Solutions I could think of to this problem:
  - if the original code is `do $body while ($cond);`, then translate that to `($body) (loop $body $cond)`, but we don't have a way to copy expressions when generating the wasm bytecode; plus it doesn't solve the labelled continue issue.
  - I think the `break` / `continue` in a do/while loop need to have special labels, so this could be somehow handled with `(loop (block $body) $cond)` and a `continue` would be a break outside of the body block. But this brings other issues: how to handle labelled continues into this do/while loop, or into outer do/while loops?

The plan is also to remove the block associated to a label, as it seems a bit overkill in most cases (when the labelled expression is a comma or a block or control flow, it will get its own block anyways).

Comment 4

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: Folded WIP

It's a been hard to follow, but passes all asm.js tests, so it's a nice time to ask for feedback.

Comment 5

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1. Changes in AsmJS

Comment 6

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 2. Changes in WasmIonCompile

Comment 7

[Luke Wagner [:luke]]

Comment on attachment 8720925 [details] [diff] [review]
1. Changes in AsmJS

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

Skimming the patch, it looks great!

Comment 8

[Luke Wagner [:luke]]

Comment on attachment 8720926 [details] [diff] [review]
2. Changes in WasmIonCompile

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

Again, looks great from a skim.  It's great to have the JS-y logic in AsmJS.cpp instead of here.  Just one general naming nit:

::: js/src/asmjs/WasmIonCompile.cpp
@@ +51,5 @@
>      MBasicBlock*               curBlock_;
>  
> +    uint32_t                   loopDepth_;
> +    uint32_t                   blockDepth_;
> +    BlocksVector               breaks_;

In WasmIonCompile.cpp let's only refer to "branches" ("br" abbreviates "branch" since it can go either forward or back).  In this case, though, maybe "branchTargets_" or just "targets_"?

Comment 9

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1. Changes in AsmJS

Comment 10

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 2. Changes in WasmIonCompile

Comment 11

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1a. Changes in AsmJS

Diff:

- TableSwitch renamed to BrTable
- the default value is now the default depth, not the default index in the arrays of depths. It makes emitting even simpler (we get rid of one loop!).

Comment 12

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1b. Changes in WasmIonCompile

Comment 13

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1c. Renaming Tableswitch to BrTable in WasmText

Comment 14

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1a. Changes in AsmJS

Diff: just a tweak on the order of br_table. Former version was doing (expr) (default) (num_cases); this version does (default) (num_cases) (expr).

Comment 15

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1b. Changes in WasmIonCompile

Sorry for the churn.

Comment 16

[Luke Wagner [:luke]]

Comment on attachment 8724788 [details] [diff] [review]
1a. Changes in AsmJS

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

Overall, looking pretty good, nice and simple patch.  One high-level change necessary is that Expr::Loop needs to change to not implicitly branch back to the top; each of the loops needs to include an explicit br to the backedge.

::: js/src/asmjs/AsmJS.cpp
@@ +2579,5 @@
>  #undef B32CASE
>  #undef ENUMERATE
>  
> +enum BlockKind {
> +    NORMAL,

Perhaps rename to BLOCK?

@@ +2722,5 @@
> +            blockDepth_++;
> +            return true;
> +          case CONTINUABLE_LOOP:
> +            return continuableStack_.append(blockDepth_++) &&
> +                   breakableStack_.append(blockDepth_++);

I think you need to reverse the order of these two: the breakable block is logically outside the inner continuable loop.

@@ +2746,5 @@
> +            --blockDepth_;
> +            return;
> +          case CONTINUABLE_LOOP:
> +            JS_ALWAYS_TRUE(breakableStack_.popCopy() == --blockDepth_);
> +            MOZ_ASSERT(blockDepth_);

MOZ_FALLTHROUGH and probably don't need this assert given the JS_ALWAYS_TRUE below.

@@ +2772,5 @@
> +        uint32_t absolute = labels_.lookup(label)->value();
> +        MOZ_ASSERT(continuableStack_.length());
> +        size_t i = continuableStack_.length() - 1;
> +        while (i && continuableStack_[i - 1] >= absolute)
> +            i--;

I wouldn't think this loop would be necessary: the parser has already ensured that the given label definitely points at a loop so it seems like labels_.lookup(label)->value() would be the right so you could just writeBr(p->value()) and continuableStack_ wouldn't be used at all.

@@ +2784,5 @@
> +        MOZ_CRASH("unexisting label");
> +    }
> +
> +    bool addLabel(PropertyName* label) {
> +        return labels_.putNew(label, blockDepth_);

I think these methods should also take care of in pushBlockOrLoop/popBlockOrLoop since the correctness of pointing a label at blockDepth_ (which is currently out-of-bounds) is only evident when you assume that blockDepth_ is immediately incremented.

@@ +6106,5 @@
> +AddLoopTest(FunctionValidator& f, ParseNode* cond)
> +{
> +    uint32_t maybeLit;
> +    if (IsLiteralInt(f.m(), cond, &maybeLit) && maybeLit)
> +        return f.encoder().writeExpr(Expr::Nop);

Perhaps add comment: "TODO: will not need to generate nop when blocks switch from number-of-statements immediate to end marker".

@@ +6109,5 @@
> +    if (IsLiteralInt(f.m(), cond, &maybeLit) && maybeLit)
> +        return f.encoder().writeExpr(Expr::Nop);
> +
> +    // if (i32.eq 0 $f) OUT
> +    if (!f.encoder().writeExpr(Expr::If))

I think this would be smaller and faster to decode if you used br_if (removing the unlabeled break below).

@@ +6113,5 @@
> +    if (!f.encoder().writeExpr(Expr::If))
> +        return false;
> +
> +    // i32.eq 0 $f
> +    if (!f.encoder().writeExpr(Expr::I32Eq))

Perhaps put in a "TODO: change to i32.eqz"?

@@ +6134,5 @@
>      MOZ_ASSERT(whileStmt->isKind(PNK_WHILE));
>      ParseNode* cond = BinaryLeft(whileStmt);
>      ParseNode* body = BinaryRight(whileStmt);
>  
> +    // While($f) $g <=> (loop (if (i32.eq 0 $f) (br OUT)) ($g))

Can you uncapitalize 'While' and change the target text to:
  (loop $after $back (br_if $after (eq 0 $f)) ($g) (br $back))
and a comment saying that breaks in $g branch to $after and continues branch to $back.

@@ +6135,5 @@
>      ParseNode* cond = BinaryLeft(whileStmt);
>      ParseNode* body = BinaryRight(whileStmt);
>  
> +    // While($f) $g <=> (loop (if (i32.eq 0 $f) (br OUT)) ($g))
> +    if (!f.pushBlockOrLoop(2 /* test + $g */, CONTINUABLE_LOOP))

I had incorrectly guessed this number was "block depth" so maybe have /* numStmts = test + $g */?

@@ +6143,5 @@
> +        return false;
> +    if (!CheckStatement(f, body))
> +        return false;
> +
> +    f.popBlockOrLoop(CONTINUABLE_LOOP);

Need to unconditionally branch back up to the loop header (as well as changing the semantics of Expr::Loop to fallthrough, not branch).

@@ +6161,5 @@
>      ParseNode* maybeInit = TernaryKid1(forHead);
>      ParseNode* maybeCond = TernaryKid2(forHead);
>      ParseNode* maybeInc = TernaryKid3(forHead);
>  
> +    // for ($a; $b; $c) $d; <=> (block ($a) (loop (if (eq 0 $b) br OUT) $d $c))

I think the target pattern should be:
  (block ($a) (loop $after $back (br_if $after (eq 0 $b)) (block $inc $d) (br $back)))
and a comment that continue inside $d branch to $inc and breaks branch to $after.

@@ +6162,5 @@
>      ParseNode* maybeCond = TernaryKid2(forHead);
>      ParseNode* maybeInc = TernaryKid3(forHead);
>  
> +    // for ($a; $b; $c) $d; <=> (block ($a) (loop (if (eq 0 $b) br OUT) $d $c))
> +    if (!f.pushBlockOrLoop(2 /* $a + loop */))

Same numStmts comment as above.

@@ +6171,5 @@
> +
> +    {
> +        // Continue statements in the body break after the body, before the
> +        // condition.
> +        if (!f.pushBlockOrLoop(3 /* test + $d + $c */, NON_CONTINUABLE_LOOP))

I think we should be able to remove NON_CONINUABLE_LOOP/CONTINUABLE and just use a CONTINUABLE_LOOP which is pushed before adding the loop test.  Given that simplification, I think it'd be nicer to just have 3 distinct functions: pushUnbreakableBlock/pushBreakableBlock/pushLoop (and their pop equivalents).

@@ +6176,5 @@
> +            return false;
> +
> +        if (maybeCond ? !AddLoopTest(f, maybeCond) : !f.encoder().writeExpr(Expr::Nop))
> +            return false;
> +        {

\n before {

@@ +6201,5 @@
>      MOZ_ASSERT(whileStmt->isKind(PNK_DOWHILE));
>      ParseNode* body = BinaryLeft(whileStmt);
>      ParseNode* cond = BinaryRight(whileStmt);
>  
> +    // do { $b } while ($c) <=> (loop (block $b) (if (eq 0 $b) (br TOP)))

I think the target text should be:
  (loop $after $back (block $inc $b) (br_if $back ($c))
with a comment saying breaks in $b branch to $after and continues branch to $inc.

@@ +6369,5 @@
> +// - one main block wrapping all the other blocks, just to be able to break
> +// out of the switch with an unlabeled break statement.
> +// - one block per case between low and high; undefined cases just jump to
> +// the default case. Each of these blocks contain two statements: an inner
> +// block and maybe a statements list. These blocks are ordered in the same

Instead of "inner block", how about "the next case's block" and instead of "maybe a statement list", how about "the (possibly empty) statement list comprising the case body"?

@@ +6374,5 @@
> +// way as they appear in the JS source code, so that relative depth of a block
> +// and its order are naturally equal.
> +// - one block for the default case, always created. It also has two
> +// statements. It is always at the last position.
> +// - one block for the br_table itself, which only contains it.

This inner br_table block shouldn't be necessary: br_table doesn't introduce a block.

@@ +6384,5 @@
>      ParseNode* switchExpr = BinaryLeft(switchStmt);
>      ParseNode* switchBody = BinaryRight(switchStmt);
>  
> +    // Check for static properties. Make sure to not write anything in the
> +    // wasm stream before the switch is statically known.

I don't quite follow the last sentence: if it's a validation error, shouldn't everything get properly aborted?

@@ +6405,1 @@
>      if (!CheckSwitchRange(f, stmt, &low, &high, &tableLength))

I'd move CheckDefaultAtEnd() and CheckSwitchRange() above the f.pushBlockOrLoop(1, BREAKABLE).

Comment 17

[Luke Wagner [:luke]]

Comment on attachment 8724777 [details] [diff] [review]
1c. Renaming Tableswitch to BrTable in WasmText

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

::: js/src/asmjs/WasmText.cpp
@@ +3319,5 @@
>      return !ret.maybeExpr() || ResolveExpr(r, *ret.maybeExpr());
>  }
>  
>  static bool
> +ResolveBranchTable(Resolver& r, WasmAstBranchTable& ts)

s/ts/bt/

@@ +3637,5 @@
>             (!r.maybeExpr() || EncodeExpr(e, *r.maybeExpr()));
>  }
>  
>  static bool
> +EncodeBranchTable(Encoder& e, WasmAstBranchTable& ts)

s/ts/bt/

Comment 18

[Luke Wagner [:luke]]

Comment on attachment 8724789 [details] [diff] [review]
1b. Changes in WasmIonCompile

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

Looks great; so much simpler with Loop!  Mostly just need that loop change mentioned in the last patch.

::: js/src/asmjs/WasmIonCompile.cpp
@@ +937,2 @@
>      {
> +        blockDepth_++;

Can you add (before the ++):
 MOZ_ASSERT_IF(blockDepth_ < targets_.length(); targets_[blockDepth_].empty());

@@ +941,5 @@
> +        // Coalesce trivial blocks.
> +        if (!curBlock_->hasAnyIns())
> +            return true;
> +        MBasicBlock* next;
> +        if (!goToNewBlock(curBlock_, &next))

Do we need to start a new block?  I can see why, in finishBlock() we need to cut off the current block to pull in any forward jumps, but not why when entering.

@@ +1033,5 @@
> +        MOZ_ASSERT(blockDepth_ >= 2);
> +        MOZ_ASSERT(loopDepth_);
> +
> +        uint32_t headerLabel = blockDepth_ - 1 - LOOP_CONTINUE_LABEL_DEPTH;
> +        uint32_t afterLabel = blockDepth_ - 1 - LOOP_OUT_LABEL_DEPTH;

I'm not sure these constants really clear anything up.  Since this is basically just a fundamental design of loop, I'd just hardcode the folded constants here and it should be fairly readable.

@@ +1088,5 @@
>          }
>          if (!newBlock(switchBlock, next))
>              return false;
> +        if (curBlock_ && !goToExistingBlock(*next, curBlock_))
> +            return false;

Since every switch/default case ends with an unconditional branch, could this function MOZ_ASSERT(inDeadCode())?

@@ +1119,3 @@
>          if (curBlock_) {
>              MBasicBlock* next;
> +            if (!goToNewBlock(curBlock_, &next))

Based on similar reasoning above, could we MOZ_ASSERT(inDeadCode()) and remove this branch?

@@ +1127,3 @@
>      }
>  
> +    bool addBreak(uint32_t relativeDepth)

Can you rename this 'br' (for symmetry with brIf, suggested below)?

@@ +1215,5 @@
> +        prev->end(MGoto::New(alloc(), next));
> +        return next->addPredecessor(alloc(), prev);
> +    }
> +
> +    bool bindBranches(uint32_t absolute, MBasicBlock* next)

I think you can remove this 'next' parameter and use curBlock_ inline.

@@ +2341,5 @@
>  
> +    uint32_t numStmts = f.readVarU32();
> +    if (numStmts) {
> +        for (uint32_t i = 0; i < numStmts - 1; i++) {
> +            // Fine to clobber def, we only want the last use.

Pre-existing: could you change here and EmitBlock to remove this comment and use an "MDefinition* _;" instead?  (The unconditional EmitExpr at the end initializes def.  Also, could you "if (uint32_t numStmts = f.readVarU32())"?

@@ +2428,5 @@
>  
> +    // Empty table
> +    if (!numCases) {
> +        MDefinition* index;
> +        return EmitExpr(f, ExprType::I32, &index);

Don't we need to jump to defaultDepth in this case?  (I guess with asm.js we can't hit this case in an interesting way.)

@@ +2467,2 @@
>              return false;
> +        if (!f.addBreak(depth))

For the default and cases, I think we'll get more efficient codegen (unless our jump-folding is better than I remember) and N fewer MBasicBlocks if you can make the table-switch jump directly to the right target_.

That being said, I think that'd be a bit harder and I'd expect you'd have to generalize targets_ to record (MBasicBlock, case-index) pairs so that when you go and close those blocks, you can patch the MTableSwitch.  So perhaps we can keep it like this but file a bug to remove the indirection?

@@ +2528,5 @@
> +    MBasicBlock* joinBlock = nullptr;
> +    if (!f.branchAndStartThen(condition, &thenBlock, &joinBlock))
> +        return false;
> +
> +    if (!f.addBreak(relativeDepth))

Even though technically this is able to reuse if/else, I was hoping that to simply have a new f.brIf(relativeDepth) that jumped directly to relativeDepth and advanced to the join-block.  This would avoid creating a whole MBasicBlock just to hold that one unconditional branch.

Comment 19

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: wip.patch

Folded WIP addressing some review comments (but not all yet). Diff:

- fixed fallthrough semantics for loops.
- use br_if rather than (if ... br) at several places.
- don't use a loop in writeLabeledContinue. I had to re-add pushContinuableBlock because of for loops (that want "continue" stmts to go to the increment) and do-while loops (that want "continue" stmts to go to the condition). There are also two maps instead of one for labels (1 for continue labels, 1 for break labels), as loop labels may not be strictly following each other, because of loop constructs.

Comment 20

[Benjamin Bouvier [:bbouvier] (inactive)]

(In reply to Luke Wagner [:luke] from comment #18)
> @@ +2467,2 @@
> >              return false;
> > +        if (!f.addBreak(depth))
> 
> For the default and cases, I think we'll get more efficient codegen (unless
> our jump-folding is better than I remember) and N fewer MBasicBlocks if you
> can make the table-switch jump directly to the right target_.
> 
> That being said, I think that'd be a bit harder and I'd expect you'd have to
> generalize targets_ to record (MBasicBlock, case-index) pairs so that when
> you go and close those blocks, you can patch the MTableSwitch.  So perhaps
> we can keep it like this but file a bug to remove the indirection?

Good news, everyone! As these basic blocks are actually empty (they just have a control instruction to go to the right block), they don't get compiled to a jump (see skipTrivialBlocks in CodeGenerator).

That being said, we do end up having more MBasicBlock, indeed, which is likely to make some compiler algorithms slower. Opening a follow up.

Comment 21

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1a. Changes in AsmJS

Comment 22

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1b. Changes in WasmIonCompile

Comment 23

[Luke Wagner [:luke]]

Comment on attachment 8726305 [details] [diff] [review]
1a. Changes in AsmJS

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

Great; very clean code (as much as can be expected given all the crazy rules)!  Just some minor refactoring/comment comments:

::: js/src/asmjs/AsmJS.cpp
@@ +2578,5 @@
>  #undef F32CASE
>  #undef B32CASE
>  #undef ENUMERATE
>  
> +typedef Vector<PropertyName*, 4, SystemAllocPolicy> NamesVector;

Convention would be NameVector.

@@ +2761,5 @@
> +    bool writeUnlabeledBreakOrContinue(bool isBreak) {
> +        return writeBr(isBreak? breakableStack_.back() : continuableStack_.back());
> +    }
> +    bool writeContinue() {
> +        return writeUnlabeledBreakOrContinue(false);

How about 'writeBr(continuableStack_.back())'?

@@ +2781,5 @@
> +            removeLabel(label, &breakLabels_);
> +            removeLabel(label, &continueLabels_);
> +        }
> +    }
> +    bool addBreakableLabels(const NamesVector& labels, uint32_t numStmts) {

How about merge this with pushUnbreakableBlock by giving pushUnbreakableBlock a 'const NamesVector* labels = nullptr' argument?  That would simplify the CheckStatementList logic below by taking out the branch.

@@ +2797,5 @@
> +    bool writeLabeledBreakOrContinue(PropertyName* label, bool isBreak) {
> +        LabelMap& map = isBreak ? breakLabels_ : continueLabels_;
> +        if (LabelMap::Ptr p = map.lookup(label))
> +            return writeBr(p->value());
> +        MOZ_CRASH("unexisting label");

s/unexisting/nonexistent/

@@ +6110,5 @@
>      return CheckAsExprStatement(f, expr);
>  }
>  
> +static bool
> +AddLoopTest(FunctionValidator& f, ParseNode* cond)

How about `CheckLoopConditionOnEntry`:
 - "Check" b/c it recursively calls Check
 - "OnEntry" b/c this isn't used by DoWhile and so we don't need to think about what it means in that context.

@@ +6147,5 @@
>      ParseNode* cond = BinaryLeft(whileStmt);
>      ParseNode* body = BinaryRight(whileStmt);
>  
> +    // A while loop `while(#cond) #body` is equivalent to:
> +    // (loop $after_loop $top

Need to sync after_loop/after and top/back

@@ +6190,5 @@
> +    // (block                                               // depth X
> +    //   (#init)
> +    //   (loop $after_loop $loop_top                        // depth X+2 (loop)
> +    //     (brIf $after (eq 0 #cond))
> +    //     (block #body) $after_body                        // depth X+3

To match s-expr syntax, I'd put "$after_body" inside the block before #body.

@@ +6208,5 @@
> +    if (maybeInit ? !CheckAsExprStatement(f, maybeInit) : !f.encoder().writeExpr(Expr::Nop))
> +        return false;
> +
> +    {
> +        if (!f.pushLoop(/* numStmts = */ 4))

How about `/* numStmts = */ 2 + !!maybeCond + !!maybeInc` and avoid the nops below?

@@ +6247,5 @@
>      ParseNode* body = BinaryLeft(whileStmt);
>      ParseNode* cond = BinaryRight(whileStmt);
>  
> +    uint32_t maybeLit;
> +    if (IsLiteralInt(f.m(), cond, &maybeLit) && maybeLit) {

I don't think Emscripten ever emits do{...}while(1) (it emits while(1){...}) so unless this is necessary for correctness (in which case comment), I'd remove it.

@@ +6317,5 @@
> +    } while (innermost->getKind() == PNK_LABEL);
> +
> +    switch (innermost->getKind()) {
> +      case PNK_LABEL:
> +        MOZ_CRASH("impossible because of the above loop");

Correct, but probably doesn't need the special case since it's syntactically evident.

@@ +6470,5 @@
> +// - one block per case between low and high; undefined cases just jump to the
> +// default case. Each of these blocks contain two statements: the next case's
> +// block and the possibly empty statement list comprising the case body. These
> +// blocks are ordered in the same way as they appear in the JS source code, so
> +// that relative depth of a block and its order are naturally equal.

I'd change the last sentence to: "The last block pushed is the first case so the (relative) branch target therefore matches the sequential order of the cases."

@@ +6472,5 @@
> +// block and the possibly empty statement list comprising the case body. These
> +// blocks are ordered in the same way as they appear in the JS source code, so
> +// that relative depth of a block and its order are naturally equal.
> +// - one block for the default case, always created. It also has two
> +// statements. It is always at the last position.

Given comment below, can you move this up to be the second bullet?  Also, I'd change the last sentence to: "asm.js rules require default to be at the end, so the default block always encloses all the case blocks.".

@@ +6473,5 @@
> +// blocks are ordered in the same way as they appear in the JS source code, so
> +// that relative depth of a block and its order are naturally equal.
> +// - one block for the default case, always created. It also has two
> +// statements. It is always at the last position.
> +// - one block for the br_table itself, so we can simply break.

Given comment below, I think you can remove the last bullet.

@@ +6523,5 @@
> +            return false;
> +    }
> +
> +    // The default block is at the end, at depth `numDefined`.
> +    uint32_t defaultDepth = numDefined;

The default block is actually the second block (after the break block).  Also, in the above loop, caseDepth[i] isn't actually branching to the block it's pushing (the first case targets the last block pushed).  These are all pushUnbreakableBlock()s so you this is all just a matter of how we comment/organize the code.  How about this:
 - Start with the for loop which assigns to caseDepths and accumulates numDefined (renamed to numCases).  This makes sense by itself when you just think that the first case has relative depth 0.
 - Then have "uint32_t numBlocks = 1 /* for break */ + 1 /* for default */ + numCases;".  Note that this is 1 less than the number currently pushed -- I think the current scheme pushes a superfluous block which is fine because the outermost break uses an absolute target that skips right over the dead block, but we should kill it.
 - Then have "f.pushBreakableBlock(1); for (i=1; i < numBlocks) { f.pushUnbreakableBlock(2) }" so we can see them stack.
 - Then everything the same as now
 - Remove the final f.popUnbreakableBlock(); before f.popBreakableBlock() for the reason above.

Comment 24

[Luke Wagner [:luke]]

Comment on attachment 8726306 [details] [diff] [review]
1b. Changes in WasmIonCompile

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

Great work!  Compiling br is sooo much nicer...

::: js/src/asmjs/WasmIonCompile.cpp
@@ +951,5 @@
> +        // Coalesce trivial blocks.
> +        if (!curBlock_->hasAnyIns())
> +            return true;
> +        MBasicBlock* next;
> +        if (!goToNewBlock(curBlock_, &next))

If we don't have any preds to add for 'next', is it really necessary to goToNewBock or can we just 'return bindBranches()'?

@@ +1054,5 @@
> +
> +        MBasicBlock* loopBody = curBlock_;
> +
> +        // The current block will be assigned the loop backedge block.
> +        curBlock_ = nullptr;

How about:
  // Expr::Loop doesn't have an implicit backedge so temporarily set aside 
  // the end of the loop body to bind backedges.
  MBasicBody* loopBodyEnd = curBlock_;
  curBlock_ = nullptr;
?

@@ +1055,5 @@
> +        MBasicBlock* loopBody = curBlock_;
> +
> +        // The current block will be assigned the loop backedge block.
> +        curBlock_ = nullptr;
> +        if (!bindBranches(headerLabel))

I think this is pre-existing, but could you file a follow-up bug (blocking wasm) and put a TODO comment here to make all these backedges real loop backedges with setLoopBackedge instead of jumping forward to 1 backedge?  This might help codegen, depending on how smart we are in Ion.

@@ +1266,3 @@
>              if (!mirGen_.ensureBallast())
>                  return false;
> +            if (!goToExistingBlock(preds[i], curBlock_))

What about changing 'curBlock_' to 'join' and moving up to be right under the gotToNewBlock(preds[0], &join) so that all preds are linked to join at once?

Comment 25

[Dan Gohman [:sunfish]]

Attachment: wasm-block-loop-validation.patch

This patch adds wasm validation support for block and loop. With this, the factorial function testcase now works!

Comment 26

[Luke Wagner [:luke]]

Comment on attachment 8726551 [details] [diff] [review]
wasm-block-loop-validation.patch

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

Turing Complete!  Our work here is done.

::: js/src/asmjs/Wasm.cpp
@@ +90,5 @@
> +        *depth = labelStackDepth_;
> +        ++labelStackDepth_;
> +        return labelStackDepth_ != 0;
> +    }
> +    MOZ_WARN_UNUSED_RESULT bool popLabel(uint32_t depth) {

Is it possible for popLabel to fail in practice?  It seems like we're enforcing the balancing ourselves by our recursive validation.  Certainly in a postorder iterative future this won't be the case, but I think we can take out the 'depth' out/in-param from pushLabel/popLabel.

@@ +434,5 @@
> +{
> +    uint32_t relativeDepth;
> +    return f.d().readVarU32(&relativeDepth) &&
> +           f.isLabelInBounds(relativeDepth) &&
> +           DecodeExpr(f, ExprType::Void);

ExprType::Void -> I32

@@ +475,5 @@
>          return DecodeSetLocal(f, expected);
>        case Expr::Block:
> +        return DecodeBlock(f, /* isLoop */false, expected);
> +      case Expr::Loop:
> +        return DecodeBlock(f, /* isLoop */true, expected);

Can you put a space between '/' and true/false?

::: js/src/jit-test/tests/wasm/fac.js
@@ +1,4 @@
> +load(libdir + "wasm.js");
> +
> +if (!wasmIsSupported())
> +    quit();

bbouvier put one of these in wasm.js, so you don't need it here

Comment 27

[Dan Gohman [:sunfish]]

Attachment: wasm-block-loop-validation.patch

(In reply to Luke Wagner [:luke] from comment #26)
> ::: js/src/asmjs/Wasm.cpp
> @@ +90,5 @@
> > +        *depth = labelStackDepth_;
> > +        ++labelStackDepth_;
> > +        return labelStackDepth_ != 0;
> > +    }
> > +    MOZ_WARN_UNUSED_RESULT bool popLabel(uint32_t depth) {
> 
> Is it possible for popLabel to fail in practice?  It seems like we're
> enforcing the balancing ourselves by our recursive validation.  Certainly in
> a postorder iterative future this won't be the case, but I think we can take
> out the 'depth' out/in-param from pushLabel/popLabel.

No, you're right. I was thinking about what we'll need to validate in postorder.

> @@ +434,5 @@
> > +{
> > +    uint32_t relativeDepth;
> > +    return f.d().readVarU32(&relativeDepth) &&
> > +           f.isLabelInBounds(relativeDepth) &&
> > +           DecodeExpr(f, ExprType::Void);
> 
> ExprType::Void -> I32

Right. The thing we need to do with Void is CheckType with the expected type (for now; type checking for br_if is on ongoing discussion in the spec).

Attached is an updated patch which addresses the comments here.

Comment 28

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8726579 [details] [diff] [review]
wasm-block-loop-validation.patch

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

Nice! But a drive-by review is what you get for taking the most fun part of this bug :-)

::: js/src/asmjs/Wasm.cpp
@@ +67,5 @@
>      Decoder& d_;
>      ModuleGenerator& mg_;
>      FunctionGenerator& fg_;
>      uint32_t funcIndex_;
> +    uint32_t labelStackDepth_;

I'd have named this blockDepth_, for symmetry with WasmIonCompile/AsmJS.cpp, but well :-)

@@ +415,5 @@
> +DecodeBr(FunctionDecoder& f)
> +{
> +    uint32_t relativeDepth;
> +    return f.d().readVarU32(&relativeDepth) &&
> +           f.isLabelInBounds(relativeDepth);

isLabelInBounds doesn't return an error message, so this will silently fail with "out of memory" if the label actually isn't in bounds, so I think you need an explicit error message here.

@@ +423,5 @@
> +DecodeBrIf(FunctionDecoder& f, ExprType expected)
> +{
> +    uint32_t relativeDepth;
> +    return f.d().readVarU32(&relativeDepth) &&
> +           f.isLabelInBounds(relativeDepth) &&

ditto

Comment 29

[Benjamin Bouvier [:bbouvier] (inactive)]

Thank you for the review!

(In reply to Luke Wagner [:luke] from comment #23)
> Comment on attachment 8726305 [details] [diff] [review]
> 1a. Changes in AsmJS
> @@ +6523,5 @@
> > +            return false;
> > +    }
> > +
> > +    // The default block is at the end, at depth `numDefined`.
> > +    uint32_t defaultDepth = numDefined;
> 
> The default block is actually the second block (after the break block). 
> Also, in the above loop, caseDepth[i] isn't actually branching to the block
> it's pushing (the first case targets the last block pushed).  These are all
> pushUnbreakableBlock()s so you this is all just a matter of how we
> comment/organize the code.  How about this:
>  - Start with the for loop which assigns to caseDepths and accumulates
> numDefined (renamed to numCases).  This makes sense by itself when you just
> think that the first case has relative depth 0.
>  - Then have "uint32_t numBlocks = 1 /* for break */ + 1 /* for default */ +
> numCases;".  Note that this is 1 less than the number currently pushed -- I
> think the current scheme pushes a superfluous block which is fine because
> the outermost break uses an absolute target that skips right over the dead
> block, but we should kill it.
>  - Then have "f.pushBreakableBlock(1); for (i=1; i < numBlocks) {
> f.pushUnbreakableBlock(2) }" so we can see them stack.
>  - Then everything the same as now
>  - Remove the final f.popUnbreakableBlock(); before f.popBreakableBlock()
> for the reason above.

Actually, we can indeed remove one block, but not the way you say:
- we can use the breakable block as the default block: f.pushBreakableBlock(2 /* inner block + default expr */);
- each case needs its block: for (i = 0; i < numCases; i++) f.pushUnbreakableBlock(2 /* inner block + case expr */)
- the br_table needs its block, to be able to break out of it: f.pushUnbreakableBlock(1).

So still numCases + 2 blocks, but not arranged the same way :-) The default block remains at numCases now. I've updated the comment too.

Comment 30

[Dan Gohman [:sunfish]]

Attachment: 2. Validate loop in wasm

Renamed labelStackDepth_ to blockDepth_ for consistency, added error messages, and some accompanying testcases.

Comment 31

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/67c48a1e8414
https://hg.mozilla.org/integration/mozilla-inbound/rev/249cbccd3ad3

Comment 32

[Benjamin Bouvier [:bbouvier] (inactive)]

Folded the first 3 patches I made into a single one (so that fuzzers can still compile and test from one to the other); pushed it and sunfish's patch.

Comment 33

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 1. Implement br/br_if/loop opcodes in WasmIonCompile and use them in AsmJS

For the record.

Comment 34

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 3. Validate BrTable and add a bunch of tests

This:
- implements br_table validation
- adds a few tests for br / br_if / loop / br_table
- fixes an issue when resolving branch targets in the parser (relative depths are inverted to the stack index!)

Comment 35

[Benjamin Bouvier [:bbouvier] (inactive)]

We're not done yet; we still have to yield sub-expressions values.

Comment 36

[Benjamin Bouvier [:bbouvier] (inactive)]

Dear fuzzer people: just a heads up that Wasm can now iloop, so you might need more instrumentation in your code to provoke timeouts. Cheers!

Comment 37

[Benjamin Bouvier [:bbouvier] (inactive)]

For what it's worth, I could have Alon's hello world wast module validating and compiling if I'd comment out the load/store offsets assertions in the code (bug 1253115). I could have it running, but it doesn't do a single thing (probably because we need to expose memory so that it can be merged with emscripten runtime's memory + load/store offsets; or there's a bug in our code). However, I can see calls into WasmCall when breaking under gdb \o/

Comment 38

[Hannes Verschore [:h4writer]]

I assume this caused a regression on asmjs benchmarks:
https://arewefastyet.com/#machine=28&view=single&suite=asmjs-ubench&subtest=skinning&start=1457075748&end=1457104811

(only look at the asmjs=on line. The improvement on noasmjs is unrelated)

Comment 39

[Dan Gohman [:sunfish]]

Comment on attachment 8726696 [details] [diff] [review]
3. Validate BrTable and add a bunch of tests

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

Great! One comment:

::: js/src/asmjs/Wasm.cpp
@@ +457,5 @@
> +        return f.fail("too many br_table entries");
> +
> +    for (uint32_t i = 0; i < tableLength; i++) {
> +        if (!f.d().readVarU32())
> +            return f.fail("missing br_table entry");

We also need to do an isLabelInBounds check for each table entry.

Comment 40

[Luke Wagner [:luke]]

Hrm, looks like also for fannkuch, fbirds-native, maybe mandlebrot (although primes got a bit better).  No effect on the macro benchmarks, though.  Probably best to file a followup bug to investigate.

bbouvier: my suspicion is that hard-coded CFG-folding we had for while(1)/do{}while(0) are actually helping loop codegen.  I thought about commenting on these but I had thought that someone had implemented the general case in Ion so I thought it would be handled for us.  That would explain why particular microbenchmarks (that just pound on one loop) feel it acutely and others not at all.

Comment 41

[Luke Wagner [:luke]]

Looks like BinaryEncoding.md will be updated to put the default branch target after the case target list:
  https://github.com/WebAssembly/design/pull/586
Since it's a trivial change, perhaps you want to roll that tweak into this br_table patch.

Comment 42

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/7ce3d296a3fa

Comment 43

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/51bdc254e936

Comment 44

[Luke Wagner [:luke]]

I had to remove the two timeout tests to avoid a backout: on arm64 there is no wasm support so the tests exit without error.

Comment 45

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/67c48a1e8414
https://hg.mozilla.org/mozilla-central/rev/249cbccd3ad3
https://hg.mozilla.org/mozilla-central/rev/7ce3d296a3fa
https://hg.mozilla.org/mozilla-central/rev/51bdc254e936

Comment 46

[Luke Wagner [:luke]]

Attachment: loosen-br-table-limit

Tweak the constant to match asm.js (which I'm assuming was the original intent).

Comment 47

[Benjamin Bouvier [:bbouvier] (inactive)]

Comment on attachment 8727126 [details] [diff] [review]
loosen-br-table-limit

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

Stealing, it's trivial. Yes it was the original intent, thanks!

Comment 48

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/a18101cf1a45

Comment 49

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/a18101cf1a45