IonMonkey optimization to remove unreachable control flow

RESOLVED FIXED in mozilla20

Status

()

RESOLVED FIXED
6 years ago
6 years ago

People

(Reporter: nmatsakis, Unassigned)

Tracking

Trunk
mozilla20
x86
Mac OS X
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 3 obsolete attachments)

(Reporter)

Description

6 years ago
I've (mostly) implemented an optimization to purge unreachable basic blocks (e.g., "if (false) {...}").  This is useful for the parallel array code because it allows us to write specialized variants of functions and have IM purge those that do not apply to the specific circumstances; it also allows us to have code that only runs in sequential mode which is removed from the CFG during parallel execution.

The current patch passes all jit-tests except for two, which fail during reg alloc.
(Reporter)

Comment 1

6 years ago
Created attachment 691202 [details] [diff] [review]
Current implementation.
(Reporter)

Comment 2

6 years ago
jandem, dvander suggested that you might be able to help me understand what invariant of the linear scan allocator I am violating.  I get failures in v8-v5/check-splay.js and ion/inlining/bug705251.js, both with the same assertion failure:

Assertion failure: loopBlock->id() >= mblock->id(), at js/src/ion/LiveRangeAllocator.cpp:663
Flags: needinfo?(jdemooij)
What the regalloc code does is this: when we see a loop header, find the loop's backedge, then follow the backedge's predecessors until we reach the loop header. It asserts that every block we see must have an id >= the loop header's id.

I looked at the ion/inlining/bug705251.js failure. During regalloc for this function:

function bitsinbyte() {
    var c = 0;
    while (false) c = c * 2;
}

We have these blocks:

Block 0: goto block 1
Block 1: goto block 2
Block 2: return undefined

The problem is that block 1 is still marked as loop header. MBasicBlock::backedge() then does:

MBasicBlock *backedge() const {
    JS_ASSERT(isLoopHeader());
    JS_ASSERT(numPredecessors() == 1 || numPredecessors() == 2);
    return getPredecessor(numPredecessors() - 1);
}

So it thinks block 0 is a loop backedge, but that's not true and confuses the liveness algorithm.

The right fix I think is to change the loop header's kind from LOOP_HEADER to NORMAL when you remove a backedge from the graph.

(And btw, you should run jit-test.py with the --ion flag, it causes it to run every test twice: once with --no-jm and once with --ion-eager. Both of these flags lower the compile threshold so they compile a lot more code. I applied your patch and got some other failures.)
Flags: needinfo?(jdemooij)
(Reporter)

Comment 4

6 years ago
Created attachment 691391 [details] [diff] [review]
Patch to remove

Try run pending: http://tbpl.mozilla.org/?tree=Try&rev=1bf5d4e219f6
Attachment #691202 - Attachment is obsolete: true
Attachment #691391 - Flags: review?(jdemooij)
(Reporter)

Comment 5

6 years ago
Created attachment 691424 [details] [diff] [review]
Patch to remove unreachable blocks.

Previous patch did not build without #ifdef DEBUG.

Pending try submission: http://tbpl.mozilla.org/?tree=Try&rev=ba877411e098
Attachment #691391 - Attachment is obsolete: true
Attachment #691391 - Flags: review?(jdemooij)
Attachment #691424 - Flags: review?(jdemooij)
Try run for 3719e99961ae is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=3719e99961ae
Results (out of 37 total builds):
    exception: 29
    success: 1
    failure: 7
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/nmatsakis@mozilla.com-3719e99961ae
Comment on attachment 691424 [details] [diff] [review]
Patch to remove unreachable blocks.

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

Nice work, thanks for adding this! Great comments and asserts, too. Comments below are mostly minor style nits.

This analysis should have its own class though (expose one public method and make the other methods private) and its own cpp/h file, like EdgeCaseAnalysis, RangeAnalysis etc. Should be good to go with that fixed.

::: js/src/ion/IonAnalysis.cpp
@@ +303,5 @@
> +PrunePointlessBranchesAndMarkReachableBlocks(MIRGraph &graph, uint32_t *marked)
> +{
> +    Vector<MBasicBlock *, 16, SystemAllocPolicy> worklist;
> +
> +    // Seed with the two entry points:

Nit: s/:/. here and a few times below.

@@ +305,5 @@
> +    Vector<MBasicBlock *, 16, SystemAllocPolicy> worklist;
> +
> +    // Seed with the two entry points:
> +    MBasicBlock *entries[] = { graph.entryBlock(), graph.osrBlock() };
> +    for (uint i = 0; i < sizeof(entries) / sizeof(entries[0]); i++) {

Nit: s/uint/size_t

@@ +315,5 @@
> +        }
> +    }
> +
> +    // Process everything reachable from there:
> +    while (!worklist.empty()) {

This loop should have something like

if (mir->shouldCancel("Eliminate Unreachable Code"))
    return false;

@@ +352,5 @@
> +    return true;
> +}
> +
> +static void
> +RemoveUsesFromUnmarkedBlocks(MDefinition *instr) {

Nit: { should go on its own line

@@ +364,5 @@
> +
> +static bool
> +RemoveUnmarkedBlocksAndClearDominators(MIRGraph &graph,
> +                                       size_t marked,
> +                                       bool *redundantPhis)

Nit: arguments should fit on one line (limit is 99 characters for code, 80 for comments).

@@ +372,5 @@
> +    // new value.  Also adds blocks that are immediately reachable
> +    // from an unmarked block to the frontier.
> +
> +    size_t id = marked;
> +    for (PostorderIterator iter(graph.poBegin()); iter != graph.poEnd();) {

Add a mir->shouldCancel(..) check here too.

@@ +435,5 @@
> +            graph.removeBlock(block);
> +        }
> +    }
> +
> +    return true;

Nit: can we JS_ASSERT(id == 0); here?

@@ +477,5 @@
> +    graph.unmarkBlocks();
> +
> +    // Pass 3: Recompute dominators and tweak phis.
> +    BuildDominatorTree(graph);
> +    return !redundantPhis || EliminatePhis(mir, graph);

Nit: this may be slightly clearer (and easier to extend later) as:

if (redundantPhis && !EliminatePhis(mir, graph))
    return false;

return true;

@@ +1090,5 @@
> +        JS_ASSERT(block->id() == idx++);
> +
> +        // No critical edges:
> +        if (block->numSuccessors() > 1) {
> +            for (size_t i = 0; i < block->numSuccessors(); i++) {

Nit: no braces.

@@ +1113,5 @@
> +        }
> +
> +        uint32_t successorWithPhis = 0;
> +        for (size_t i = 0; i < block->numSuccessors(); i++) {
> +            if (!block->getSuccessor(i)->phisEmpty()) {

Nit: no braces

::: js/src/ion/MIR.cpp
@@ +444,5 @@
> +    // on removing a, then first shift downward so that we have
> +    // phi(..., b, c, d, ..., z, z):
> +    size_t length = inputs_.length();
> +    for (size_t i = index + 1; i < length; i++) {
> +        replaceOperand(i - 1, getOperand(i));

Nit: single line body so no braces

@@ +447,5 @@
> +    for (size_t i = index + 1; i < length; i++) {
> +        replaceOperand(i - 1, getOperand(i));
> +    }
> +
> +    // remove the final operand that now appears twice:

Nit: Capitalize first letter and s/:/, same for the comment below.

::: js/src/ion/MIRGraph.cpp
@@ +757,5 @@
> +        if (!phisEmpty()) {
> +            JS_ASSERT(pred->successorWithPhis());
> +            JS_ASSERT(pred->positionInPhiSuccessor() == i);
> +            for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++) {
> +                iter->removeOperand(i);

Style nit: single-line body doesn't need braces

@@ +760,5 @@
> +            for (MPhiIterator iter = phisBegin(); iter != phisEnd(); iter++) {
> +                iter->removeOperand(i);
> +            }
> +            for (size_t j = i+1; j < numPredecessors(); j++) {
> +                getPredecessor(j)->setSuccessorWithPhis(this, j - 1);

Same here.

::: js/src/jit-test/tests/ion/eliminate-unreachable-1.js
@@ +27,5 @@
> +  assertEq(test1(true), 1000101);
> +  assertEq(test1(false), 1110000);
> +}
> +
> +for (var i = 0; i < 100000; i++)

Nit: 100000 is a lot, you can make it 100 or so. We should still Ion-compile it with --ion-eager and --no-jm (many other tests depend on this too)

::: js/src/jit-test/tests/ion/eliminate-unreachable-2.js
@@ +23,5 @@
> +  test1(true);
> +  test1(false);
> +}
> +
> +for (var i = 0; i < 100000; i++)

Same here. Also note that we don't compare stdout, so I don't know how useful this test is compared to eliminate-unreachable-1.js. Maybe change print("hi") to assertEq(v, true) or something?
Attachment #691424 - Flags: review?(jdemooij)
Duplicate of this bug: 820726
(Reporter)

Comment 9

6 years ago
Created attachment 692060 [details] [diff] [review]
Latest version of patch to remove unreachable blocks.

Incorporates jandem's feedback and fixes the failure I was seeing in try runs.

Pending try run for this patch:

http://tbpl.mozilla.org/?tree=Try&rev=42546cbfcc66
(Reporter)

Updated

6 years ago
Attachment #692060 - Attachment description: Latest version of path to remove unreachable blocks. → Latest version of patch to remove unreachable blocks.
(Reporter)

Updated

6 years ago
Attachment #691424 - Attachment is obsolete: true
Created attachment 692127 [details] [diff] [review]
tweak

Niko, your patch works like a charm!  Could I request that you slightly generalize your value testing like so?
(Reporter)

Comment 12

6 years ago
hg.mozilla.org/integration/mozilla-inbound/rev/d9e54b62a5f5
https://hg.mozilla.org/mozilla-central/rev/0fb9ff76a177
https://hg.mozilla.org/mozilla-central/rev/d9e54b62a5f5
Status: NEW → RESOLVED
Last Resolved: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla20
Try run for 3719e99961ae is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=3719e99961ae
Results (out of 38 total builds):
    exception: 30
    success: 1
    failure: 7
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/nmatsakis@mozilla.com-3719e99961ae
Try run for 42546cbfcc66 is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=42546cbfcc66
Results (out of 315 total builds):
    exception: 3
    success: 282
    warnings: 30
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/nmatsakis@mozilla.com-42546cbfcc66
Try run for e4e9b876ee87 is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=e4e9b876ee87
Results (out of 315 total builds):
    exception: 3
    success: 286
    warnings: 25
    failure: 1
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/nmatsakis@mozilla.com-e4e9b876ee87
Try run for ba877411e098 is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=ba877411e098
Results (out of 246 total builds):
    exception: 2
    success: 215
    warnings: 24
    failure: 5
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/nmatsakis@mozilla.com-ba877411e098
Try run for e54e496a72a7 is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=e54e496a72a7
Results (out of 316 total builds):
    exception: 2
    success: 277
    warnings: 36
    failure: 1
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/nmatsakis@mozilla.com-e54e496a72a7
Try run for 1bf5d4e219f6 is complete.
Detailed breakdown of the results available here:
    https://tbpl.mozilla.org/?tree=Try&rev=1bf5d4e219f6
Results (out of 129 total builds):
    exception: 1
    success: 107
    warnings: 13
    failure: 8
Builds (or logs if builds failed) available at:
http://ftp.mozilla.org/pub/mozilla.org/firefox/try-builds/nmatsakis@mozilla.com-1bf5d4e219f6
Depends on: 879727
No longer depends on: 879727
You need to log in before you can comment on or make changes to this bug.