851115 - IonMonkey: make sure loopDepth has the right value

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect)

Description

[Hannes Verschore [:h4writer]]

Running testcase: IONFLAGS=logs $JS/js --ion-eager tests/ion/bug724975.js

I see after "Split Critical Edges" that the loopDepth information is incorrect. This isn't a huge deal, because it is only used by LinearRange.cpp, but I want to reuse that information to fix #884479.

I haven't debugged why it is wrong, though

Comment 1

[Nicolas B. Pierron [:nbp]]

This bug is also block Bug 897606, as for adding post-dominator, we need to compute an identifier such as we visit the loop header first, and so we need to compute an identifier which relies on the loopDepth to shift every id() in the loop.  The problem also exists with NewParBailout, which is introduced to replace an existing basic block, except that it does not keep the original loopDepth.

Hopefully, this is an easy fix and I should have a nice patch ready for review in a few minutes.

Comment 2

[Nicolas B. Pierron [:nbp]]

Attachment: Keep the loopDepth across Basic Block modifications.

Comment 3

[Hannes Verschore [:h4writer]]

Comment on attachment 780818 [details] [diff] [review]
Keep the loopDepth across Basic Block modifications.

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

Patch doesn't apply. And possibly also doesn't fix all issues. The numbers are also incorrect during IonBuilder, since they don't get recovered nicely :(

Comment 4

[Hannes Verschore [:h4writer]]

Comment on attachment 780818 [details] [diff] [review]
Keep the loopDepth across Basic Block modifications.

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

Don't land in this bug!!! Create a new bug depending on this bug.
Since this patch only fixes some of the issues. Still a lot of issues left:

IONFLAGS=logs $JS/js --ion-eager tests/ion/bug724975.js
Still shows in IonBuilder:
1) block 1 (OSR block) is loopdepth: 1 (should be 0)
2) block 2 (preloop) is loopdepth: 2 (should be 0)
3) block 3 (first loop header) is loopdepth: 2 (should be 1)
4) block 6 (backedge of inner-loop) is loopdepth: 1 (should be 2)

I will only allow to get this bug closed if we can add an assert in LICM that for every block the LICM loopdepth <= block->loopdepth_.
That should make sure we don't introduce new issues.

::: js/src/ion/MIRGraph.cpp
@@ +211,5 @@
>  MBasicBlock *
>  MBasicBlock::NewSplitEdge(MIRGraph &graph, CompileInfo &info, MBasicBlock *pred)
>  {
> +    MBasicBlock *block = MBasicBlock::New(graph, info, pred, pred->pc(), SPLIT_EDGE);
> +    block->loopDepth_ = pred->loopDepth;

Apparently here is the culprit. pred->loopDepth_

Comment 5

[Nicolas B. Pierron [:nbp]]

Attachment: Ensure loopDepth is coherent with RPO.

This patch add a check to AssertCoherencyGraph to ensure that the loopDepth is coherent (even if it is not right, esp. with AsmJS do-while loops).  To simplify the life I added a function which recover it after the UCE, by iterating in RPO to fixup the loop depths of all basic blocks.

AsmJS issues are all visible in the control flow and are related to the fact that the following assertion does not pass:

  JS_ASSERT(block->isLoopHeader() && block->hasUniqueBackedge(),
            block->backedge()->isLoopBackedge());

This assertion should be added as part of the graph coherency assertions.  And fixing this issue should help removing the 2 fixup done only in the context of AsmJS.

Comment 6

[Hannes Verschore [:h4writer]]

Comment on attachment 781139 [details] [diff] [review]
Ensure loopDepth is coherent with RPO.

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

I have a small feeling you didn't test this patch to look if it indeed fixes the issue ?!
I see you only do the fixloopdepth for asm.js compiled code. So that means the added asserts should fail with the jit-tests tests/ion/bug724975.js for reasons given in comment 4.
(Or I have missed something, I didn't run it myself either).

Please test jit-tests with this patch applied

::: js/src/ion/Ion.cpp
@@ +956,5 @@
> +    // any block within the loop is off-by-1.
> +    if (mir->compilingAsmJS()) {
> +        if (!FixLoopDepths(graph))
> +            return false;
> +    }

Can we do the loopdepth fix after splitcriticaledges. Than we only have to do it once...

@@ +973,5 @@
> +    // it again to get the graph coherency assertion pass again.
> +    if (mir->compilingAsmJS()) {
> +        if (!FixLoopDepths(graph))
> +            return false;
> +    }

Why only when compiling AsmJS code? The testcase I gave is definitely not asm.js code ...

::: js/src/ion/JSONSpewer.cpp
@@ +294,5 @@
>      for (MBasicBlockIterator block(mir->begin()); block != mir->end(); block++) {
>          beginObject();
>  
>          integerProperty("number", block->id());
> +        integerProperty("loopDepth", block->loopDepth());

nbp++

::: js/src/ion/UnreachableCodeElimination.cpp
@@ +65,5 @@
> +    // As we might have remove branches, and remove the loop headers, we need to
> +    // iterate over all the block to fix their loop depth.  This is needed to
> +    // ensure that post-dominator are correctly computed.
> +    if (!FixLoopDepths(graph_))
> +        return false;

Pass 3/4 are done conditionally when it is actually needed. Could you also test during removal if a loopheader is removed and conditionally run fixLoopDepths

Comment 7

[Nicolas B. Pierron [:nbp]]

(In reply to Hannes Verschore [:h4writer] from comment #6)
> I have a small feeling you didn't test this patch to look if it indeed fixes
> the issue ?!

I did otherwise I would not have noticed AsmJS errors.

> I see you only do the fixloopdepth for asm.js compiled code. So that means
> the added asserts should fail with the jit-tests tests/ion/bug724975.js for
> reasons given in comment 4.

I did not notice those while checking with this patch.  The assertion did not fail with the code produced by IonBuilder.  So I am not sure I can reproduce what you mention.

> Please test jit-tests with this patch applied

I already did, and this patch pass the jit-test.

> ::: js/src/ion/Ion.cpp
> @@ +956,5 @@
> > +    // any block within the loop is off-by-1.
> > +    if (mir->compilingAsmJS()) {
> > +        if (!FixLoopDepths(graph))
> > +            return false;
> > +    }
> 
> Can we do the loopdepth fix after splitcriticaledges. Than we only have to
> do it once...

Only if we remove the assertion which ensure that the graph has no inconsistent loop depth.

> @@ +973,5 @@
> > +    // it again to get the graph coherency assertion pass again.
> > +    if (mir->compilingAsmJS()) {
> > +        if (!FixLoopDepths(graph))
> > +            return false;
> > +    }
> 
> Why only when compiling AsmJS code? The testcase I gave is definitely not
> asm.js code ...

Because I haven't seen any issues in the jit-test where this is failing.  I don't know why this is failing on the test case that you mention on comment 4, but I cannot reproduce it.

Maybe you can run the patch locally and find that your VCS failed you?

(In reply to Nicolas B. Pierron [:nbp] from comment #1)
> This bug is also block Bug 897606, as for adding post-dominator, […]

This is no longer the case, as we can have return/break/throw within loops, which means we cannot compute the post-dominator with the loopDepth as the re-entry point is not necessary the loop header.

Comment 8

[Hannes Verschore [:h4writer]]

(In reply to Nicolas B. Pierron [:nbp] from comment #7)
> (In reply to Hannes Verschore [:h4writer] from comment #6)
> > I see you only do the fixloopdepth for asm.js compiled code. So that means
> > the added asserts should fail with the jit-tests tests/ion/bug724975.js for
> > reasons given in comment 4.
> 
> I did not notice those while checking with this patch.  The assertion did
> not fail with the code produced by IonBuilder.  So I am not sure I can
> reproduce what you mention.

Right, just tested it myself. I don't know the original revision anymore and I cannot see this issue anymore on cleverly randomly chosen revisions. Could be I messed up or maybe it was only intermediate and already fixed. Not sure.

Though by testing today I found a new issue (or rediscovered why in bug 844779, I decided to recompute the loopdepth always according to how LICM works):

IONFLAGS=logs $JS/js --ion-eager tests/ion/bug724975.js
Third compilation:

Issue 1: block 5 should be loopdepth 1 (is now 2)

Issue 2: block 8 is discussable:
> example 1:
> for (var i=0; i<10; i++) {
>     if (i == 9) {
>         return 1;
>     }
> }
> 
> example 2:
> for (var i=0; i<10; i++) {
> }
> return 1;
> 
> In example 1 the block containing "return 1" could be 1. In example 2 the block containing "return 1" should be 0. But in IonBuilder there is not really a way to distinguish both. That's the reason LICM decides that all paths that don't return to the loop are not part of the loop. So in both examples LICM will take 0.

So block 8 is a similar case. It could be 0/1 depending on the source code and interpretation.
- Now if we want to do it like LICM, we need a 0 here.
- If we decide 1 is fine. Then block 10 should be 1 too. (This is just a block following block 8. So this is just a MGoto from 8 to 10. No other blocks entering).

The reason is that our blocks are not nicely put. (That's also bug 844779). Blocks not part of the loop can be interleaved to blocks in the loop... So I think it might be bad to use RPO ordering to compute the loopdepth...

Comment 9

[Wei Wu [:wuwei UTC+8]]

Hi, is this bug fixed?

Comment 10

[Hannes Verschore [:h4writer]]

I don't think so. Also not sure how important this is. In most cases these are for heuristics. It is not too bad if in most cases this is kinda good. If you are thinking about using the "loopDepth" for something where it need to be very precise (like initial version of bug 844779, fyi second version doesn't use it anymore) it might be good to fix it. Else I would just leave it like it is currently.

Comment 11

[Nicolas B. Pierron [:nbp]]

I am going to discard these changes, because we now have a CFG built out of the bytecode.  This does not garantee that we maintain a proper loop-depth, but ensure that IonBuilder CFG reconstruction is sane-ish.