1312147 - Improve the encoding of jump instructions on x86.

Status: NEW

(Core :: JavaScript Engine: JIT, defect, P5)

Description

[Michael Bebenita [:mbx]]

There are 329,594 jump instructions in AngryBots.

* 12,797 of which are encoded with a 1 byte immediate.
* 316,797 of which are encoded with a 4 byte immediate.
  - 213,674 of which are conditional jumps
    * 136,400 can be encoded with a 1 byte immediate but are not
    * 77,275 need to be encoded with a 4 byte immediate

  - 103,123 of which are unconditional jumps
	  * 70,603 can be encoded with a 1 byte immediate but are not
	  * 32,521 need to be encoded with a 4 byte immediate

Jumps with 1 byte immediates are encoded as 2 bytes, jumps with 4 byte immediates 
are encoded wth 6 bytes, so there's a 4 byte savings to be had. If we were to magically 
emit the proper encoding, we'd save (136,400 + 70,603) * 4 bytes, or 418,812 bytes, 
~5% of AngryBots. Reducing code size may of course cause other jump targets to be within a
1 byte offset.

Comment 1

[Nicolas B. Pierron [:nbp]]

(In reply to Michael Bebenita [:mbx] from comment #0)
> * 12,797 of which are encoded with a 1 byte immediate.

I was not aware we had the ability to generate such branches.

> * 316,797 of which are encoded with a 4 byte immediate.
  - 207,003 can be encoded with 1 byte immediate.
  - 109,796 need to be encoded with a 4 byte immediate.

We have multiple problem, and the main one is that we commit the space for the instructions as we append the jump instructions.  We already have a mechanism in place, made for handling constant pools on ARM/MIPS, which would gives us the ability to update the offsets of such branches.

I do not know for WASM, but I will also note that some branches have to be patchable, and such branches should remain as a 4 bytes offsets, even if the current offset would fit in less.

Comment 2

[Michael Bebenita [:mbx]]

One simple thing we can do that would help (that sunfish suggested) is create a new kind of Label that optimistically assumes the branch offset is encodable with 1 byte, and then asserts when it is bound. This would work when we macro-expand high-level opcodes into machine code:

void
CodeGeneratorX86Shared::visitAsmSelect(LAsmSelect* ins) {
    ...

    Label done;
    masm.j(Assembler::NonZero, &done);

    if (mirType == MIRType::Float32) {
        if (falseExpr.kind() == Operand::FPREG)
            masm.moveFloat32(ToFloatRegister(ins->falseExpr()), out);
        else
            masm.loadFloat32(falseExpr, out);
    } else if (mirType == MIRType::Double) {
        if (falseExpr.kind() == Operand::FPREG)
            masm.moveDouble(ToFloatRegister(ins->falseExpr()), out);
        else
            masm.loadDouble(falseExpr, out);
    } else {
        MOZ_CRASH("unhandled type in visitAsmSelect!");
    }

    masm.bind(&done); // <-- This is likely be a 1 byte encodable offset.
    
    ...
}

Comment 3

[Nicolas B. Pierron [:nbp]]

Branislav Rankov made patches on MIPS to add such flags ~3 years ago[1][2].

Note, that ARM (& MIPS) should probably be the first targets of such optimizations, as this problem might be even worse on these architecture.

Still, I see multiple issues for CodeGenerator.cpp:
 - Instructions and jump-distances are not the same on all platforms. (x86: -128/+127, arm: -4096/+4095)
 - Constant pools can be added in the middle of the code, breaking any static branch-size assumption.

I think we should record the changes and only apply them at the end when we serialize the code in the executable buffer, and fixup the offsets in the executable buffer.

[1] https://bugzilla.mozilla.org/show_bug.cgi?id=969375
[2] http://searchfox.org/mozilla-central/search?q=ShortJump

Comment 4

[Hannes Verschore [:h4writer]]

(In reply to Nicolas B. Pierron [:nbp] from comment #3)
> I think we should record the changes and only apply them at the end when we
> serialize the code in the executable buffer, and fixup the offsets in the
> executable buffer.

I think that would indeed be the better way.

Was really torn between putting P3 or P5. Decided to mark this as P5.
It would be very nice to have this! Would be great if somebody volunteered to do this