Closed Bug 1253344 Opened 6 years ago Closed 6 years ago

Baldr: Reduce the number of created basic blocks in br_table


(Core :: JavaScript Engine: JIT, defect)

Not set



Tracking Status
firefox47 --- affected
firefox48 --- fixed


(Reporter: bbouvier, Assigned: bbouvier)




(4 files, 3 obsolete files)

Currently, our br_table emitting in WasmIonCompile does:

- tableswitch over the expression
- once in the target block, jump to the enclosing wrapping block.

That's two indirections where we could only have a single one.
Blocks: wasm
Depends on: 1246116
With brIf, we also could do the same thing: we currently generate it almost as an if/else, but we could just use a MTest. If the branch target is backwards, we already know the "then" target. Else we can just keep on going through the basic blocks, and when we encounter the target, we can patch the MTest. That would make brIf more efficient.
Three unused methods in WasmIonCompile.
Assignee: nobody → bbouvier
Attachment #8731767 - Flags: review?(luke)
Attachment #8731767 - Flags: review?(luke) → review+
Attached patch wip.patch (obsolete) — Splinter Review
After a few trials, I've realized my approach was wrong: I was trying to make br/br_if directly redirect to the target block if it's known. But that's not what we want in terms of semantics: a break breaks *out of* the target block (except for loop backedges).

Instead, this WIP patch pushes br_if tests onto a stack, so as to patch them later in bindBranches. This works like a charm, and probably the same approach could be taken for table switches.
Attached patch 1. br_if (obsolete) — Splinter Review
It works great even for table switch. Let's flip this to a review flag.
Attachment #8733465 - Attachment is obsolete: true
Attachment #8733477 - Flags: review?(sunfish)
Attached patch 2. tableswitch (obsolete) — Splinter Review
Ditto for tableswitches. Overall, this reduces the number of lines of code \o/

1 file changed, 84 insertions(+), 87 deletions(-)
Attachment #8733478 - Flags: review?(sunfish)
Comment on attachment 8733477 [details] [diff] [review]
1. br_if

Review of attachment 8733477 [details] [diff] [review]:

I find it a little surprising that br is handled differently from br_if: for br, the MGoto isn't created until the destination is known, and for br_if, it's created up front with a null successor, and patched later. Would it be feasible to create the MGoto for br up front too, with a null successor, and then unify the blocks and tests vectors into a single fixups vector, something like Vector<pair<MBasicBlock *, size_t>>? Patching would be something like fixups[i].first->replaceSuccessor(fixups[i].second, join). This would mean it'd work for br_table too without having to add a separate Vector for it.

(perhaps replacing pair with a dedicated class for readability)

Also, if MControlInstructions can (temporarily) have null successors, can you teach MControlInstruction::printOpcode to handle them gracefully?

Also, it may make sense to add a check to AssertBasicGraphCoherency where it's looking at an MControlInstruction instruction to verify that all the successors of the instruction are non-null, which should be the case once MIR building is complete. Null successors are likely to get caught by something downstream eventually, but having it in the verification code means it'll be easier to identify the culprit when it happens.

::: js/src/asmjs/WasmIonCompile.cpp
@@ +1237,5 @@
>          return true;
>      }
> +    uint32_t computeAbsolute(uint32_t relative) {

This member function can be const.

@@ +1272,4 @@
>          if (!newBlock(curBlock_, &joinBlock))
>              return false;
> +        MTest* test = MTest::New(alloc(), condition, nullptr, joinBlock);

The computeAbsolute call just after this doesn't depend on the MTest existing, right? If so, I'd find this a little clearer with the MTest creation moved down to just before its first use.
Attachment #8733477 - Flags: review?(sunfish)
Attached patch brbrbr.patchSplinter Review
Wow, it's a nice generalization and simplification at the same time! Thank you for suggesting this. I was also worried about the control flow instructions potentially having null successors but I forgot about it yesterday. I've added the check now in AssertBasicGraphCoherency.
Attachment #8733477 - Attachment is obsolete: true
Attachment #8733478 - Attachment is obsolete: true
Attachment #8733478 - Flags: review?(sunfish)
Attachment #8733879 - Flags: review?(sunfish)
Comment on attachment 8733879 [details] [diff] [review]

Review of attachment 8733879 [details] [diff] [review]:

Looks great!

::: js/src/jit/IonAnalysis.cpp
@@ +2352,5 @@
> +            if (iter->isControlInstruction()) {
> +                MControlInstruction* ins = iter->toControlInstruction();
> +                for (size_t i = 0; i < ins->numSuccessors(); i++)
> +                    MOZ_ASSERT(ins->getSuccessor(i));
> +            }

This code should go after the loop, in the code below that's already checking the MControlInstruction, because the loop uses MDefinitionIterator which doesn't visit control instructions.

::: js/src/jit/MIR.h
@@ +2813,5 @@
>      static MGoto* New(TempAllocator& alloc, MBasicBlock* target);
> +    // Factory for asm, which may patch the target later.
> +    static MGoto* NewAsm(TempAllocator& alloc);

In the case of MTest, we're just using the regular factory and passing in a nullptr. I think it'd be nice to be consistent between MTest and MGoto and either use an Asm-specific factory for both, or for neither, but I'll defer to your judgement here.
Attachment #8733879 - Flags: review?(sunfish) → review+
Attached patch interdiff.patchSplinter Review
Thank you for the review! Just before pushing, I've given it another look and found that we could even refactor more. Hence a new patch to review, sorry about that.

- renamed PendingTarget into ControlFlowPatch, as it seems to better describe what it is.
- as a matter of fact, renamed targets_ -> blockPatches_ (this is a vector of patches for each block), and all instances of "target" to "patches".
- adding a ControlFlowPatch can be done in a private method of FunctionCompiler, sparing some code duplications.

This is the interdiff, whole patch coming thereafter (won't ask for review on the folded one, but feel free to prefer reviewing one form or the other).
Attachment #8734022 - Flags: review?(sunfish)
Attached patch folded.patchSplinter Review
And the folded patch (brbrbr + interdiff)
Comment on attachment 8734022 [details] [diff] [review]

Review of attachment 8734022 [details] [diff] [review]:

Looks good. The addControlFlowPatch refactoring is very nice :).
Attachment #8734022 - Flags: review?(sunfish) → review+
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla48
You need to log in before you can comment on or make changes to this bug.