Baldr: Reduce the number of created basic blocks in br_table

RESOLVED FIXED in Firefox 48

Status

()

Core
JavaScript Engine: JIT
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: bbouvier, Assigned: bbouvier)

Tracking

(Blocks: 1 bug)

Trunk
mozilla48
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox47 affected, firefox48 fixed)

Details

Attachments

(4 attachments, 3 obsolete attachments)

(Assignee)

Description

2 years ago
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.
(Assignee)

Updated

2 years ago
Blocks: 1188259
Depends on: 1246116
(Assignee)

Comment 1

2 years ago
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.
(Assignee)

Comment 2

2 years ago
Created attachment 8731767 [details] [diff] [review]
remove-unused-pushpop-phi.patch

Three unused methods in WasmIonCompile.
Assignee: nobody → bbouvier
Status: NEW → ASSIGNED
Attachment #8731767 - Flags: review?(luke)

Updated

2 years ago
Attachment #8731767 - Flags: review?(luke) → review+
(Assignee)

Comment 3

2 years ago
Created attachment 8733465 [details] [diff] [review]
wip.patch

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.
(Assignee)

Comment 4

2 years ago
Created attachment 8733477 [details] [diff] [review]
1. br_if

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)
(Assignee)

Comment 5

2 years ago
Created attachment 8733478 [details] [diff] [review]
2. tableswitch

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)
(Assignee)

Comment 7

2 years ago
Created attachment 8733879 [details] [diff] [review]
brbrbr.patch

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]
brbrbr.patch

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 @@
>      INSTRUCTION_HEADER(Goto)
>      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+
(Assignee)

Comment 9

2 years ago
Created attachment 8734022 [details] [diff] [review]
interdiff.patch

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.

Changes:
- 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)
(Assignee)

Comment 10

2 years ago
Created attachment 8734023 [details] [diff] [review]
folded.patch

And the folded patch (brbrbr + interdiff)
Comment on attachment 8734022 [details] [diff] [review]
interdiff.patch

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

Looks good. The addControlFlowPatch refactoring is very nice :).
Attachment #8734022 - Flags: review?(sunfish) → review+

Comment 13

2 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/189899f5bdf6
https://hg.mozilla.org/mozilla-central/rev/84196783659e
Status: ASSIGNED → RESOLVED
Last Resolved: 2 years ago
status-firefox48: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla48
You need to log in before you can comment on or make changes to this bug.