Improve code generated for conditional expressions in tests

RESOLVED FIXED in mozilla34

Status

()

RESOLVED FIXED
4 years ago
4 years ago

People

(Reporter: bhackett, Assigned: bhackett)

Tracking

(Blocks: 1 bug)

unspecified
mozilla34
x86
Mac OS X
Points:
---
Dependency tree / graph
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 1 obsolete attachment)

(Assignee)

Description

4 years ago
Created attachment 8443982 [details] [diff] [review]
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);
Attachment #8443982 - Flags: review?(jdemooij)
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.
(Assignee)

Comment 2

4 years ago
Created attachment 8455474 [details] [diff] [review]
patch

Updated patch that also handles && / || patterns, and should fix bug 913935.
Assignee: nobody → bhackett1024
Attachment #8443982 - Attachment is obsolete: true
Attachment #8443982 - Flags: review?(jdemooij)
Attachment #8455474 - Flags: review?(jdemooij)
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.
Attachment #8455474 - Flags: review?(sunfish)
Attachment #8455474 - Flags: review?(jdemooij)
Attachment #8455474 - Flags: review+
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.
Attachment #8455474 - Flags: review?(sunfish) → review+
(Assignee)

Comment 5

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

Comment 6

4 years ago
And a followup to remove some debugging printfs, whoops.

https://hg.mozilla.org/integration/mozilla-inbound/rev/5c157de1ee6c
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)?
https://hg.mozilla.org/mozilla-central/rev/9c80c5b76cf0
https://hg.mozilla.org/mozilla-central/rev/5c157de1ee6c
Status: NEW → RESOLVED
Last Resolved: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla34

Updated

4 years ago
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
(Assignee)

Comment 9

4 years ago
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
https://hg.mozilla.org/mozilla-central/rev/b28ad1718d05
Status: REOPENED → RESOLVED
Last Resolved: 4 years ago4 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
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)
(Assignee)

Comment 13

4 years ago
Created attachment 8463571 [details] [diff] [review]
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
Attachment #8463571 - Flags: review?(sunfish)
(Assignee)

Updated

4 years ago
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Comment on attachment 8463571 [details] [diff] [review]
followup

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

Sounds reasonable.
Attachment #8463571 - Flags: review?(sunfish) → review+
(Assignee)

Updated

4 years ago
Depends on: 1045749
(Assignee)

Comment 16

4 years ago
(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.
https://hg.mozilla.org/mozilla-central/rev/6d31e024845f
Status: REOPENED → RESOLVED
Last Resolved: 4 years ago4 years ago
Resolution: --- → FIXED

Updated

4 years ago
Duplicate of this bug: 913935
(Assignee)

Updated

4 years ago
Blocks: 1136267
You need to log in before you can comment on or make changes to this bug.