Implements far branch targets for MIPS.

Implements far branch targets for MIPS.

This change adds a flag --mips-far-branches, which when set causes
relative branches to be converted to absolute branches by determining
the PC, adding the branch offset to it, and using the jr or jalr
instruction to jump if the branch test passes.

This procedure clobbers the assembler temporary TMP, so TMP can no
longer be used in a branch test or in the branch delay slot of a
relative branch. Because TMP can't be used in a branch test, a
new temporary is introduced CMPRES2. This change replaces TMP with
CMPRES1 or another register where TMP can no longer be used.

Tests that were failing due to a too-far relative have the
--mips-far-branches flag set.

R=regis@google.com

Committed: https://code.google.com/p/dart/source/detail?r=25543

[zra, 2013-07-25 18:15:26]

Sorry this ended up a bit big, but most of it is just switching around
registers. I wonder if it would be more clear to rename {TMP, CMPRES1, CMPRES2}
-> {TMP1, TMP2, TMP3}.

[regis, 2013-07-25 20:07:43]

Mmm, this is quite expensive.
See my comments about preserving RA in the frame, done in the function prologue.

Also, did you consider that PC is preserved in the frame? I am not sure if a
memory load is more efficient than a bal instruction, but it could well be.

The far branch code would look like this:
lw ra, saved_pc[fp]
lui tmp, dist_hi
addiu tmp, tmp, dist_lo
add ra, ra, tmp
jr ra

The dist offset would be relative to the function entry, of course.

Another possibility would be to store the absolute target address in the
constant pool:
lw tmp, offset[pp]
jr tmp

This would require a relocation if the code moves around.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h
File runtime/vm/assembler_mips.h (right):

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:883: slt(CMPRES1, rs, rd);  // CMPRES1 = rd > rs ? 1
: 0.
It's awkward that some branch instructions use CMPRES1 while others use CMPRES2.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1239: EmitRegImmType(REGIMM, R0, BGEZAL, 1);
You are not using GetNextPC. Still needed?
OK, I see now that you use it in other places.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1244: addiu(SP, SP, Immediate(1 * kWordSize));
Preserving and restoring CMPRES1 in order to, in turn, preserve and restore RA
is too expensive. You may as well preserve and restore RA directly. Better, you
should make sure that RA is saved in the prologue of functions that are compiled
using far branches. RA is then free to be used and you will save 6 instructions.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1246: EmitIType(OppositeBranchOpcode(b), rs, rt, 2);
You should have an unconditional EmitFarBranch(offset), so that you do not have
to emit this instruction. Or you should eliminate it here if possible.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1319: if (label->IsBound()) {
If the label is bound, you know the offset and you should not use the far branch
unless necessary.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1345: if (label->IsBound()) {
ditto

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1372: if (label->IsBound()) {
ditto

[zra, 2013-07-26 21:26:15]

I have changed the far branch so that it is how we discussed. That is, it loads
the absolute target address as an immediate and jumps to it. Also, this is only
done when needed (but still only when the --mips-far-branches flag is present).

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h
File runtime/vm/assembler_mips.h (right):

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:883: slt(CMPRES1, rs, rd);  // CMPRES1 = rd > rs ? 1
: 0.
On 2013/07/25 20:07:43, regis wrote:
> It's awkward that some branch instructions use CMPRES1 while others use
CMPRES2.

Done.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1246: EmitIType(OppositeBranchOpcode(b), rs, rt, 2);
On 2013/07/25 20:07:43, regis wrote:
> You should have an unconditional EmitFarBranch(offset), so that you do not
have
> to emit this instruction. Or you should eliminate it here if possible.

Done.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1319: if (label->IsBound()) {
On 2013/07/25 20:07:43, regis wrote:
> If the label is bound, you know the offset and you should not use the far
branch
> unless necessary.

Done.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1345: if (label->IsBound()) {
On 2013/07/25 20:07:43, regis wrote:
> ditto

Done.

https://codereview.chromium.org/20369003/diff/1/runtime/vm/assembler_mips.h#n...
runtime/vm/assembler_mips.h:1372: if (label->IsBound()) {
On 2013/07/25 20:07:43, regis wrote:
> ditto

Done.

[regis, 2013-07-26 22:30:37]

LGTM

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips.cc
File runtime/vm/assembler_mips.cc (right):

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips...
runtime/vm/assembler_mips.cc:57: static int32_t DecodeLoadImmediate(int32_t low,
int32_t high) {
int32_t low_instr, int32_t high_instr
or
int32_t ori_instr, int32_t lui_instr

or even
Instr ori_instr, Instr lui_instr
but the latter may be overkill.

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips...
runtime/vm/assembler_mips.cc:130: EmitIType(b, rs, rt, 4);
Either assert that the condition is not always true, or skip the EmitIType if it
is. Or does it complicate patching to skip an instruction?

You could also introduce an unconditional EmitBranch and EmitFarBranch.

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips.h
File runtime/vm/assembler_mips.h (right):

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips...
runtime/vm/assembler_mips.h:25: DECLARE_FLAG(bool, mips_far_branches);
'mips_' is not really needed, but since I understand it is a temporary flag, it
does not matter.

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips...
runtime/vm/assembler_mips.h:1044: void GetNextPC(Register dest, bool
preserve_ra) {
The caller does not see that CMPRES1 is trashed. It would be better to pass an
explicit register in case RA needs to be preserved and kNoRegister if it does
not need to be preserved. This would replace the bool parameter.

[zra, 2013-07-26 23:29:03]

Thanks for the review!

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips.cc
File runtime/vm/assembler_mips.cc (right):

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips...
runtime/vm/assembler_mips.cc:57: static int32_t DecodeLoadImmediate(int32_t low,
int32_t high) {
On 2013/07/26 22:30:38, regis wrote:
> int32_t low_instr, int32_t high_instr
> or
> int32_t ori_instr, int32_t lui_instr
> 
> or even
> Instr ori_instr, Instr lui_instr
> but the latter may be overkill.
> 

I chose ori_instr and lui_instr

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips...
runtime/vm/assembler_mips.cc:130: EmitIType(b, rs, rt, 4);
On 2013/07/26 22:30:38, regis wrote:
> Either assert that the condition is not always true, or skip the EmitIType if
it
> is. Or does it complicate patching to skip an instruction?
> 
> You could also introduce an unconditional EmitBranch and EmitFarBranch.

Most of the unconditional branches are probably near anyway, and so already
getting reduced to a single branch instruction (and some NOPs) in Bind. The only
difference I think this would make would be sometimes eliminating two NOPs in
those cases. On the other hand, it would add two new cases to Bind depending on
which instruction comes first in the far branch sequence. I would prefer to see
what the performance impact of far branches is after they are enabled only
per-function before making small fixes like this.

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips.h
File runtime/vm/assembler_mips.h (right):

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips...
runtime/vm/assembler_mips.h:25: DECLARE_FLAG(bool, mips_far_branches);
On 2013/07/26 22:30:38, regis wrote:
> 'mips_' is not really needed, but since I understand it is a temporary flag,
it
> does not matter.

Changed to use_far_branches, and I'll use the same flag for ARM.

https://codereview.chromium.org/20369003/diff/18002/runtime/vm/assembler_mips...
runtime/vm/assembler_mips.h:1044: void GetNextPC(Register dest, bool
preserve_ra) {
On 2013/07/26 22:30:38, regis wrote:
> The caller does not see that CMPRES1 is trashed. It would be better to pass an
> explicit register in case RA needs to be preserved and kNoRegister if it does
> not need to be preserved. This would replace the bool parameter.

Done.

[zra, 2013-07-26 23:30:44]

Committed patchset #4 manually as r25543 (presubmit successful).