762095 - IonMonkey: LCompareAndBranch generates an extra branch

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

Consider this testcase:

function f(x) {
    var c = 0;
    for(var i=0; i<10000000; i++) {
	var a = x | 0;
	if (a == 10) { c++; }
    }
}
f(10);

For the if "(a == 10) { c++; }" part Ion generates:

0x1070d8b:	cmp    $0xa,%eax
0x1070d8e:	je     0x1070d99
0x1070d94:	jmp    0x1070da6
0x1070d99:	mov    %ebx,%esi
0x1070d9b:	add    $0x1,%esi
0x1070d9e:	jo     0x10705b8
0x1070da4:	mov    %esi,%ebx

Instead of the je + jmp we should emit a jne.

Comment 1

[Marty Rosenberg [:mjrosenb]]

I've heard that we do this in some cases because forward conditional jumps should be predicted as not-taken, whereas unconditional jumps and backwards conditional jumps should be predicted as taken, and this pattern is used to help the branch predictor.
I'm also pretty sure that the branch predictor is much smarter than we are.

Comment 2

[Sean Stangl [:sstangl]]

(In reply to Marty Rosenberg [:mjrosenb] from comment #1)
> I've heard that we do this in some cases because forward conditional jumps
> should be predicted as not-taken, whereas unconditional jumps and backwards
> conditional jumps should be predicted as taken, and this pattern is used to
> help the branch predictor.
> I'm also pretty sure that the branch predictor is much smarter than we are.

For reference, this structure is a general Intel recommendation for writing code that also behaves well on the Pentium 4.

Would be useful in general to measure:

-How much does this change help processors more recent than the P4?
-How much does this change affect performance with P4?

Comment 3

[Sean Stangl [:sstangl]]

(In reply to Sean Stangl from comment #2)
> For reference, this structure is a general Intel recommendation for writing
> code that also behaves well on the Pentium 4.

Just to clarify -- this particular bug is valid because we have no knowledge of whether the block is likely to be taken or not, and so reducing instruction count is preferable. The same general pattern occurs elsewhere intentionally, though.

Comment 4

[Jan de Mooij [:jandem]]

(In reply to Sean Stangl from comment #3)
> 
> Just to clarify -- this particular bug is valid because we have no knowledge
> of whether the block is likely to be taken or not, and so reducing
> instruction count is preferable.

Yeah, the problem is that critical edge splitting inserts an empty block here. What CS does is right before codegen they mark blocks as empty if they contain only an LLabel, empty gap moves and LGoto. All instructions jumping to this block then jump to the target of the Goto.

The first part would be easy, but we'd have to update all places where we jump to such blocks to skip empty blocks. If anybody has an easier solution that would be nice...

Comment 5

[Dan Gohman [:sunfish]]

The backend now has a pass which eliminates such empty blocks (bug 881412), however it doesn't fix the testcase in this bug because it ignores blocks with resume points, and the relevant block has resume points. I am not yet familiar enough with resume points to say what might be done about this.

Comment 6

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman from comment #5)
> The backend now has a pass which eliminates such empty blocks (bug 881412),
> however it doesn't fix the testcase in this bug because it ignores blocks
> with resume points, and the relevant block has resume points. I am not yet
> familiar enough with resume points to say what might be done about this.

An empty block with an entry resume point can be removed the same way.  The resume points are used for lowering to assign snapshots to fallible instructions.  As an empty block does not have any fallible instructions, we can ignore the fact that it has an entry resume point.

Comment 7

[Dan Gohman [:sunfish]]

Can I assume that the resume point in a block containing nothing but a goto will always be empty? Nothing seems to break when I just remove that check for resumePointsEmpty().

Comment 8

[Nicolas B. Pierron [:nbp]]

(In reply to Dan Gohman from comment #7)
> Can I assume that the resume point in a block containing nothing but a goto
> will always be empty? Nothing seems to break when I just remove that check
> for resumePointsEmpty().

No the resume point will not be empty, but it will not be used for constructing any snapshot.

So even if we had a non-empty list of resume point (!resumePointsEmpty), this should still work if the basic block is only ending with an infallible control instruction such as a goto.

Comment 9

[Dan Gohman [:sunfish]]

The patch to remove the resumePointsEmpty() check is as trivial as it sounds, and it makes empty-block removal quite a bit more effective in non-asm.js code. I'll submit a patch when I'm able to.

Comment 10

[Dan Gohman [:sunfish]]

Attachment: a proposed fix

This fixes the testcase, and makes trivial block elimination much more effective on non-asm.js code in general.

Comment 11

[Nicolas B. Pierron [:nbp]]

Comment on attachment 772198 [details] [diff] [review]
a proposed fix

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

You can prefix your patch title with:
  Bug 762095 -  IonMonkey: …

This is helpful for identifying the impact of the modification ;)

Comment 12

[Dan Gohman [:sunfish]]

Thanks! I sequenced the edit to add the IonMonkey: prefix to this patch wrong with respect to hg commands, but I'll get it right on my future patches.

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

Comment 13

[Ed Morley [:emorley]]

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