675342 - Redundant Branches are Redundant

Status: NEW

(Core :: JavaScript Engine, defect)

Description

[Marty Rosenberg [:mjrosenb]]

With a small test case on arm, I've observed a bunch of branches being created such as:
[jaeger] Insns            >  ##linkJump         ((0x60)) jumps to ((0x64))
[jaeger] Insns            >  ##linkJump         ((0xd0)) jumps to ((0xd4))
[jaeger] Insns            >  ##linkJump         ((0xa8)) jumps to ((0xac))
[jaeger] Insns            >  ##linkJump         ((0x264)) jumps to ((0x268))
[jaeger] Insns            >  ##linkJump         ((0x2d4)) jumps to ((0x2d8))
[jaeger] Insns            >  ##linkJump         ((0x3f0)) jumps to ((0x3f4))
[jaeger] Insns            >  ##linkJump         ((0x464)) jumps to ((0x468))
[jaeger] Insns            >  ##linkJump         ((0x4c4)) jumps to ((0x4c8))
[jaeger] Insns            >  ##linkJump         ((0x558)) jumps to ((0x55c))
[jaeger] Insns            >  ##linkJump         ((0x5cc)) jumps to ((0x5d0))
[jaeger] Insns            >  ##linkJump         ((0x404)) jumps to ((0x408))
[jaeger] Insns            >  ##linkJump         ((0x580)) jumps to ((0x584))
[jaeger] Insns            >  ##linkJump         ((0xb48)) jumps to ((0xb4c))
[jaeger] Insns            >  ##linkJump         ((0xf90)) jumps to ((0xf94))

At least one or two of these branches looked like it would never be patched.
If this is in fact the case, we should not do that.

Comment 1

[Jacob Bramley [:jbramley]]

Firstly, I like your title. Secondly, I have covered this in bug 586297. It was really trivial to add to that patch, so in it went.

Comment 2

[Marty Rosenberg [:mjrosenb]]

Good to see that it helped!
After poking at it a bit more, I noticed some other things that can be optimized, but with a bit more effort.

[jaeger] Insns            >  ##linkJump         ((0x48)) jumps to ((0xa8))
[jaeger] Insns            >  ##linkJump         ((0xa8)) jumps to ((0xac))

[jaeger] Insns            >  ##linkJump         ((0x5c)) jumps to ((0xa8))
[jaeger] Insns            >  ##linkJump         ((0xa8)) jumps to ((0xac))

[jaeger] Insns            >  ##linkJump         ((0x98)) jumps to ((0xdc))
[jaeger] Insns            ##linkJump         ((0xdc)) jumps to ((0x238))
[jaeger] Insns            >  ##linkJump         ((0x238)) jumps to ((0x2a4))

where in every group of instructions, we have a branch that branches directly to another branch.  If we can get better information about which branches won't be patched later (I believe this was mentioned in bug 586297), we can simply replace all branches in a chain with the last address that will never be patched.  We should also be careful that all intermediate branches are unconditional, but I suspect that if we are branching to an instruction, it will not be a conditional instruction.

All in all, there are about 15 chains of branches in this simple program (the same one I used for the previous analysis).

If it is more than a trivial patch on top of the current patch for 586297, I'd like to take a stab at writing it myself after that patch lands.

Comment 3

[Jacob Bramley [:jbramley]]

(In reply to comment #2)
> If we can get better information about which
> branches won't be patched later (I believe this was mentioned in bug
> 586297), we can simply replace all branches in a chain with the last address
> that will never be patched.

Information about which branches will be repatched is determined in ARMAssembler::fixUpOffsets, but I think all branches are considered patchable. Historically, it was just used because patchable loads (including branches) can't share a literal pool slot with anything else. This might not give you all the information you want. For example, I think all branches are patchable because the branch is generated _before_ it is linked to its target.

It is all much simpler in NanoJIT, where code is generated backwards.

> We should also be careful that all intermediate
> branches are unconditional [...]

You could just check that the other branches have the same condition as the first. Alternatively, if the other branches have the opposite condition, you could branch to the instruction after it, though keeping track of that might be tricky.

> but I suspect that if we are branching to an
> instruction, it will not be a conditional instruction.

I wouldn't want to make that assumption :-) All sorts of unexpected things turn up in the generated code sometimes. That doesn't mean it should be fixed, of course.

I suspect that a few of these come about due to literal pools. When the pool size reaches a certain threshold (or it is flushed manually for ICs), we emit an unconditional branch to jump over the literal pool, which sits inline in the instruction stream. If this happens in the middle of a compare-and-branch sequence, you'll end up with an unconditional branch to a conditional branch. That doesn't mean that it can't be optimized, of course.

> If it is more than a trivial patch on top of the current patch for 586297,
> I'd like to take a stab at writing it myself after that patch lands.

I don't think this would be trivial to implement, and it certainly doesn't fit trivially on top of 586297.