820676 - IonMonkey optimization to remove unreachable control flow

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Niko Matsakis [:nmatsakis]]

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.

Comment 1

[Niko Matsakis [:nmatsakis]]

Attachment: Current implementation.

Comment 2

[Niko Matsakis [:nmatsakis]]

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

Comment 3

[Jan de Mooij [:jandem]]

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

Comment 4

[Niko Matsakis [:nmatsakis]]

Attachment: Patch to remove

Try run pending: http://tbpl.mozilla.org/?tree=Try&rev=1bf5d4e219f6

Comment 5

[Niko Matsakis [:nmatsakis]]

Attachment: Patch to remove unreachable blocks.

Previous patch did not build without #ifdef DEBUG.

Pending try submission: http://tbpl.mozilla.org/?tree=Try&rev=ba877411e098

Comment 6

[Mozilla RelEng Bot]

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/[e-mail]-3719e99961ae

Comment 7

[Jan de Mooij [:jandem]]

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?

Comment 9

[Niko Matsakis [:nmatsakis]]

Attachment: 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

Comment 10

[Luke Wagner [:luke]]

Attachment: tweak

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

Comment 11

[Niko Matsakis [:nmatsakis]]

http://hg.mozilla.org/integration/mozilla-inbound/rev/0fb9ff76a177

Comment 12

[Niko Matsakis [:nmatsakis]]

hg.mozilla.org/integration/mozilla-inbound/rev/d9e54b62a5f5

Comment 13

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/0fb9ff76a177
https://hg.mozilla.org/mozilla-central/rev/d9e54b62a5f5

Comment 14

[Mozilla RelEng Bot]

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/[e-mail]-3719e99961ae

Comment 15

[Mozilla RelEng Bot]

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/[e-mail]-42546cbfcc66

Comment 16

[Mozilla RelEng Bot]

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/[e-mail]-e4e9b876ee87

Comment 17

[Mozilla RelEng Bot]

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/[e-mail]-ba877411e098

Comment 18

[Mozilla RelEng Bot]

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/[e-mail]-e54e496a72a7

Comment 19

[Mozilla RelEng Bot]

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/[e-mail]-1bf5d4e219f6