1028580 - Improve code generated for conditional expressions in tests

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Brian Hackett [Laid off!]]

Attachment: patch

When conditional expressions are used in a script's tests, like 'if (a ? b : c)', the code which Ion generates could use some improvements.  Several basic blocks are introduced to compute a phi for the value produced by the condition, which is then fed into a test.  The phi can be eliminated by having the branches of the condition jump directly to the test's successors.  This is especially important when one of the branches is a constant, in which case the initial test could jump directly to a successor of the final test and skip executing two blocks.

asm.js code contains this pattern a lot and the asm.js frontend already optimizes this pattern.  The attached patch makes the above changes and now the Ion and asm.js generated code on e.g. zlib match up pretty well with each other.  With --no-asmjs I get a 3% or so improvement on zlib and a substantial (e.g. 40%) improvement on microbenchmarks like the one below.

function f(a, b) {
    for (var i = 0; i < 100000000; i++) {
	if (i & 1 ? a : 0)
	    a = 1;
    }
}
f(1, 2);

Comment 1

[Dan Gohman [:sunfish]]

There's a compile error with this patch caused by recent changes on trunk; the fix is to change JS_ASSERT(pred->lastIns_) to JS_ASSERT(pred->hasLastIns()).

In case anyone's curious, this bug is similar to bug 913935, which is about && and ||, but the CFG pattern for those is a little different, so the current patch here doesn't match it.

Comment 2

[Brian Hackett [Laid off!]]

Attachment: patch

Updated patch that also handles && / || patterns, and should fix bug 913935.

Comment 3

[Jan de Mooij [:jandem]]

Comment on attachment 8455474 [details] [diff] [review]
patch

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

Looks good. Removing blocks is tricky though and sunfish worked on that recently for the GVN/UCE refactoring, so I'll request an additional review.

Comment 4

[Dan Gohman [:sunfish]]

Comment on attachment 8455474 [details] [diff] [review]
patch

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

This patch does optimize the testcase in bug 913935, though it doesn't quite get optimal code. We get:

  cmpl       $0xa, %eax
  setl       %dl
  movzbl     %dl, %edx
  testl      %edx, %edx
  je         ((462))
  cmpl       $0x14, %ecx
  jge        ((471))

instead of:

  cmpl       $0xa, %eax
  jge        ((462))
  cmpl       $0x14, %ecx
  jge        ((471))


This appears to be because the first MCompare is used by a resumepoint before the second compare, which disqualifies it in CanEmitCompareAtUses. Would it be possible and practical to eliminate that resumepoint use?

::: js/src/jit/MIRGraph.cpp
@@ +937,5 @@
> +    JS_ASSERT(!pred->successorWithPhis());
> +
> +    if (!phisEmpty()) {
> +        // This should only be called before critical edge splitting.
> +        JS_ASSERT(!existingPred->successorWithPhis());

Does it make sense for the new indexForPredecessor function to have this assert?

@@ +945,5 @@
> +            if (existingPred == predecessors_[i]) {
> +                existingPosition = i;
> +                break;
> +            }
> +        }

This should just call indexForPredecessor here.

Comment 5

[Brian Hackett [Laid off!]]

I think we can remove that resume point use but it would be better to do that in another bug.

https://hg.mozilla.org/integration/mozilla-inbound/rev/9c80c5b76cf0

Comment 6

[Brian Hackett [Laid off!]]

And a followup to remove some debugging printfs, whoops.

https://hg.mozilla.org/integration/mozilla-inbound/rev/5c157de1ee6c

Comment 7

[Hannes Verschore [:h4writer]]

Backed this out:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b2a0854d295e

This was crashing octane-typescript:
#0  js::jit::LinearScanAllocator::resolveControlFlow (this=this@entry=0xb77fed90) at /home/h4writer/Build/mozilla-inbound/js/src/jit/LinearScan.cpp:275
#1  0x0829d9aa in js::jit::LinearScanAllocator::go (this=0xb77fed90) at /home/h4writer/Build/mozilla-inbound/js/src/jit/LinearScan.cpp:1311
#2  0x081afdfd in js::jit::GenerateLIR (mir=mir@entry=0x88fb2e8) at /home/h4writer/Build/mozilla-inbound/js/src/jit/Ion.cpp:1634
#3  0x081f266c in js::jit::CompileBackEnd (mir=0x88fb2e8) at /home/h4writer/Build/mozilla-inbound/js/src/jit/Ion.cpp:1722
#4  0x084474fb in js::HelperThread::handleIonWorkload (this=this@entry=0x866f930) at /home/h4writer/Build/mozilla-inbound/js/src/vm/HelperThreads.cpp:934
#5  0x08447e09 in js::HelperThread::threadLoop (this=0x866f930) at /home/h4writer/Build/mozilla-inbound/js/src/vm/HelperThreads.cpp:1233
#6  0xb7f8d393 in ?? () from /usr/lib/i386-linux-gnu/libnspr4.so
#7  0xb7faad4c in start_thread (arg=0xb77ffb40) at pthread_create.c:308
#8  0xb7d5ebae in clone () at ../sysdeps/unix/sysv/linux/i386/clone.S:130

Would it be possible to add a testcase for this, since the testsuite didn't catch this (AWFY did)?

Comment 8

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/9c80c5b76cf0
https://hg.mozilla.org/mozilla-central/rev/5c157de1ee6c

Comment 9

[Brian Hackett [Laid off!]]

This should fix the TypeScript crash, and includes a test.  When one of the test successors was a backedge we could end up with multiple backedges in the loop, which confused later code.  I fixed this by moving this optimization after critical edge splitting, when the loop backedge will be a goto.

https://hg.mozilla.org/integration/mozilla-inbound/rev/b28ad1718d05

Comment 10

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/b28ad1718d05

Comment 11

[Benjamin Bouvier [:bbouvier] (inactive)]

This introduced a build warning:

In file included from /home/ben/code/moz/builds/wd64/js/src/Unified_cpp_js_src3.cpp:197:0:
/home/ben/code/moz/inbound/js/src/jit/IonAnalysis.cpp:180:5: warning: multi-line comment [-Wcomment]
     //         /     \
     ^

https://hg.mozilla.org/integration/mozilla-inbound/rev/e0f5ea8e9082 (r? over irc)

Comment 12

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/e0f5ea8e9082

Comment 13

[Brian Hackett [Laid off!]]

Attachment: followup

Unfortunately, doing this optimization after critical edge splitting breaks the pattern matching for and/or blocks, which I didn't notice (the example I was using actually ended up being matched by the condition pattern matching, and UCE later simplified the result to what we got with and/or matching, but this isn't something that happens reliably.)

The attached patch moves condition and and/or folding back before critical edge splitting, and makes sure there aren't any loop backedges involved when performing the optimization (I don't think this is possible except for the final test, but there's no harm in checking.)  Critical edges outgoing from the test block are split eagerly, so that we can still optimize the condition in 'do { } while (a && b)' loops

Comment 14

[Dan Gohman [:sunfish]]

Comment on attachment 8463571 [details] [diff] [review]
followup

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

Sounds reasonable.

Comment 15

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/6d31e024845f

Comment 16

[Brian Hackett [Laid off!]]

(In reply to Dan Gohman [:sunfish] from comment #4)
> This appears to be because the first MCompare is used by a resumepoint
> before the second compare, which disqualifies it in CanEmitCompareAtUses.
> Would it be possible and practical to eliminate that resumepoint use?

I filed bug 1045749 for eliminating this resume point use, which is pretty simple to do.

Comment 17

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/6d31e024845f