Implements far branch targets for MIPS.

runtime/vm/assembler_mips.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/globals.h"
 #if defined(TARGET_ARCH_MIPS)
 
 #include "vm/assembler.h"
 #include "vm/runtime_entry.h"
 #include "vm/simulator.h"
 #include "vm/stack_frame.h"
 #include "vm/stub_code.h"
 
 namespace dart {
 
 #if defined(USING_SIMULATOR)
 DECLARE_FLAG(bool, trace_sim);
 #endif
 DEFINE_FLAG(bool, print_stop_message, false, "Print stop message.");
+DEFINE_FLAG(bool, mips_far_branches, false, "Enable far branches on MIPS");
 DECLARE_FLAG(bool, inline_alloc);
 
 void Assembler::InitializeMemoryWithBreakpoints(uword data, int length) {
   ASSERT(Utils::IsAligned(data, 4));
   ASSERT(Utils::IsAligned(length, 4));
   const uword end = data + length;
   while (data < end) {
     *reinterpret_cast<int32_t*>(data) = Instr::kBreakPointInstruction;
     data += 4;
   }
 }
 
 
-void Assembler::Bind(Label* label) {
-  ASSERT(!label->IsBound());
-  int bound_pc = buffer_.Size();
-  while (label->IsLinked()) {
-    const int32_t position = label->Position();
-    const int32_t next = buffer_.Load<int32_t>(position);
-    // Relative destination from an instruction after the branch.
-    const int32_t dest = bound_pc - (position + Instr::kInstrSize);
-    const int32_t encoded = Assembler::EncodeBranchOffset(dest, next);
-    buffer_.Store<int32_t>(position, encoded);
-    label->position_ = Assembler::DecodeBranchOffset(next);
-  }
-  label->BindTo(bound_pc);
-  delay_slot_available_ = false;
+static bool CanEncodeBranchOffset(int32_t offset) {
+  ASSERT(Utils::IsAligned(offset, 4));
+  return Utils::IsInt(18, offset);
 }
 
 
-int32_t Assembler::EncodeBranchOffset(int32_t offset, int32_t instr) {
+static int32_t EncodeBranchOffset(int32_t offset, int32_t instr) {
   ASSERT(Utils::IsAligned(offset, 4));
   ASSERT(Utils::IsInt(18, offset));
 
   // Properly preserve only the bits supported in the instruction.
   offset >>= 2;
   offset &= kBranchOffsetMask;
   return (instr & ~kBranchOffsetMask) | offset;
 }
 
 
-int Assembler::DecodeBranchOffset(int32_t instr) {
+static int DecodeBranchOffset(int32_t instr) {
   // Sign-extend, left-shift by 2.
   return (((instr & kBranchOffsetMask) << 16) >> 14);
 }
 
 
+static int32_t DecodeLoadImmediate(int32_t low, int32_t high) {

[regis, 2013/07/26 22:30:38]

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.

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

I chose ori_instr and lui_instr

+  return (((high & kBranchOffsetMask) << 16) | (low & kBranchOffsetMask));
+}
+
+
+static int32_t EncodeLoadImmediate(int32_t dest, int32_t instr) {
+  return ((instr & ~kBranchOffsetMask) | (dest & kBranchOffsetMask));
+}
+
+
+class PatchFarJump : public AssemblerFixup {
+ public:
+  PatchFarJump() {}
+
+  void Process(const MemoryRegion& region, int position) {
+    const int32_t high = region.Load<int32_t>(position);
+    const int32_t low = region.Load<int32_t>(position + Instr::kInstrSize);
+    const int32_t offset = DecodeLoadImmediate(low, high);
+    const int32_t dest = region.start() + offset;
+
+    if ((Instr::At(reinterpret_cast<uword>(&high))->OpcodeField() == LUI) &&
+        (Instr::At(reinterpret_cast<uword>(&low))->OpcodeField() == ORI)) {
+      // Change the offset to the absolute value.
+      const int32_t encoded_low =
+          EncodeLoadImmediate(dest & kBranchOffsetMask, low);
+      const int32_t encoded_high =
+          EncodeLoadImmediate(dest >> 16, high);
+
+      region.Store<int32_t>(position, encoded_high);
+      region.Store<int32_t>(position + Instr::kInstrSize, encoded_low);
+      return;
+    }
+    // If the offset loading instructions aren't there, we must have replaced
+    // the far branch with a near one, and so these instructions should be NOPs.
+    ASSERT((high == Instr::kNopInstruction) && (low == Instr::kNopInstruction));
+  }
+};
+
+
+void Assembler::EmitFarJump(int32_t offset, bool link) {
+  const uint16_t low = Utils::Low16Bits(offset);
+  const uint16_t high = Utils::High16Bits(offset);
+  buffer_.EmitFixup(new PatchFarJump());
+  lui(TMP, Immediate(high));
+  ori(TMP, TMP, Immediate(low));
+  if (link) {
+    EmitRType(SPECIAL, TMP, R0, RA, 0, JALR);
+  } else {
+    EmitRType(SPECIAL, TMP, R0, R0, 0, JR);
+  }
+}
+
+
+static Opcode OppositeBranchOpcode(Opcode b) {
+  switch (b) {
+    case BEQ: return BNE;
+    case BNE: return BEQ;
+    case BGTZ: return BLEZ;
+    case BLEZ: return BGTZ;
+    case BEQL: return BNEL;
+    case BNEL: return BEQL;
+    case BGTZL: return BLEZL;
+    case BLEZL: return BGTZL;
+    default:
+      UNREACHABLE();
+      break;
+  }
+  return BNE;
+}
+
+
+void Assembler::EmitFarBranch(Opcode b, Register rs, Register rt,
+                              int32_t offset) {
+  EmitIType(b, rs, rt, 4);

[regis, 2013/07/26 22:30:38]

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.

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

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.

+  nop();
+  EmitFarJump(offset, false);
+}
+
+
+static RtRegImm OppositeBranchNoLink(RtRegImm b) {
+  switch (b) {
+    case BLTZ: return BGEZ;
+    case BGEZ: return BLTZ;
+    case BLTZAL: return BGEZ;
+    case BGEZAL: return BLTZ;
+    default:
+      UNREACHABLE();
+      break;
+  }
+  return BLTZ;
+}
+
+
+void Assembler::EmitFarRegImmBranch(RtRegImm b, Register rs, int32_t offset) {
+  EmitRegImmType(REGIMM, rs, b, 4);
+  nop();
+  EmitFarJump(offset, (b == BLTZAL) || (b == BGEZAL));
+}
+
+
+void Assembler::EmitFarFpuBranch(bool kind, int32_t offset) {
+  const uint32_t b16 = kind ? (1 << 16) : 0;
+  Emit(COP1 << kOpcodeShift | COP1_BC << kCop1SubShift | b16 | 4);
+  nop();
+  EmitFarJump(offset, false);
+}
+
+
+void Assembler::EmitBranch(Opcode b, Register rs, Register rt, Label* label) {
+  if (label->IsBound()) {
+    // Relative destination from an instruction after the branch.
+    const int32_t dest =
+        label->Position() - (buffer_.Size() + Instr::kInstrSize);
+    if (FLAG_mips_far_branches && !CanEncodeBranchOffset(dest)) {
+      EmitFarBranch(b, rs, rt, label->Position());
+    } else {
+      const uint16_t dest_off = EncodeBranchOffset(dest, 0);
+      EmitIType(b, rs, rt, dest_off);
+    }
+  } else {
+    const int position = buffer_.Size();
+    if (FLAG_mips_far_branches) {
+      const uint32_t dest_off = label->position_;
+      EmitFarBranch(b, rs, rt, dest_off);
+    } else {
+      const uint16_t dest_off = EncodeBranchOffset(label->position_, 0);
+      EmitIType(b, rs, rt, dest_off);
+    }
+    label->LinkTo(position);
+  }
+}
+
+
+void Assembler::EmitRegImmBranch(RtRegImm b, Register rs, Label* label) {
+  if (label->IsBound()) {
+    // Relative destination from an instruction after the branch.
+    const int32_t dest =
+        label->Position() - (buffer_.Size() + Instr::kInstrSize);
+    if (FLAG_mips_far_branches && !CanEncodeBranchOffset(dest)) {
+      EmitFarRegImmBranch(b, rs, label->Position());
+    } else {
+      const uint16_t dest_off = EncodeBranchOffset(dest, 0);
+      EmitRegImmType(REGIMM, rs, b, dest_off);
+    }
+  } else {
+    const int position = buffer_.Size();
+    if (FLAG_mips_far_branches) {
+      const uint32_t dest_off = label->position_;
+      EmitFarRegImmBranch(b, rs, dest_off);
+    } else {
+      const uint16_t dest_off = EncodeBranchOffset(label->position_, 0);
+      EmitRegImmType(REGIMM, rs, b, dest_off);
+    }
+    label->LinkTo(position);
+  }
+}
+
+
+void Assembler::EmitFpuBranch(bool kind, Label *label) {
+  const int32_t b16 = kind ? (1 << 16) : 0;  // Bit 16 set for branch on true.
+  if (label->IsBound()) {
+    // Relative destination from an instruction after the branch.
+    const int32_t dest =
+        label->Position() - (buffer_.Size() + Instr::kInstrSize);
+    if (FLAG_mips_far_branches && !CanEncodeBranchOffset(dest)) {
+      EmitFarFpuBranch(kind, label->Position());
+    } else {
+      const uint16_t dest_off = EncodeBranchOffset(dest, 0);
+      Emit(COP1 << kOpcodeShift |
+           COP1_BC << kCop1SubShift |
+           b16 |
+           dest_off);
+    }
+  } else {
+    const int position = buffer_.Size();
+    if (FLAG_mips_far_branches) {
+      const uint32_t dest_off = label->position_;
+      EmitFarFpuBranch(kind, dest_off);
+    } else {
+      const uint16_t dest_off = EncodeBranchOffset(label->position_, 0);
+      Emit(COP1 << kOpcodeShift |
+           COP1_BC << kCop1SubShift |
+           b16 |
+           dest_off);
+    }
+    label->LinkTo(position);
+  }
+}
+
+
+static int32_t FlipBranchInstruction(int32_t instr) {
+  Instr* i = Instr::At(reinterpret_cast<uword>(&instr));
+  if (i->OpcodeField() == REGIMM) {
+    RtRegImm b = OppositeBranchNoLink(i->RegImmFnField());
+    i->SetRegImmFnField(b);
+    return i->InstructionBits();
+  } else if (i->OpcodeField() == COP1) {
+    return instr ^ (1 << 16);
+  }
+  Opcode b = OppositeBranchOpcode(i->OpcodeField());
+  i->SetOpcodeField(b);
+  return i->InstructionBits();
+}
+
+
+void Assembler::Bind(Label* label) {
+  ASSERT(!label->IsBound());
+  int bound_pc = buffer_.Size();
+
+  while (label->IsLinked()) {
+    int32_t position = label->Position();
+    int32_t dest = bound_pc - (position + Instr::kInstrSize);
+
+    if (FLAG_mips_far_branches && !CanEncodeBranchOffset(dest)) {
+      // Far branches are enabled and we can't encode the branch offset.
+
+      // Grab the branch instruction. We'll need to flip it later.
+      const int32_t branch = buffer_.Load<int32_t>(position);
+
+      // Grab instructions that load the offset.
+      const int32_t high =
+          buffer_.Load<int32_t>(position + 2 * Instr::kInstrSize);
+      const int32_t low =
+          buffer_.Load<int32_t>(position + 3 * Instr::kInstrSize);
+
+      // Change from relative to the branch to relative to the assembler buffer.
+      dest = buffer_.Size();
+      const int32_t encoded_low =
+          EncodeLoadImmediate(dest & kBranchOffsetMask, low);
+      const int32_t encoded_high =
+          EncodeLoadImmediate(dest >> 16, high);
+
+      // Skip the unconditional far jump if the test fails by flipping the
+      // sense of the branch instruction.
+      buffer_.Store<int32_t>(position, FlipBranchInstruction(branch));
+      buffer_.Store<int32_t>(position + 2 * Instr::kInstrSize, encoded_high);
+      buffer_.Store<int32_t>(position + 3 * Instr::kInstrSize, encoded_low);
+      label->position_ = DecodeLoadImmediate(low, high);
+    } else if (FLAG_mips_far_branches && CanEncodeBranchOffset(dest)) {
+      // We assembled a far branch, but we don't need it. Replace with a near
+      // branch.
+
+      // Grab the link to the next branch.
+      const int32_t high =
+          buffer_.Load<int32_t>(position + 2 * Instr::kInstrSize);
+      const int32_t low =
+          buffer_.Load<int32_t>(position + 3 * Instr::kInstrSize);
+
+      // Grab the original branch instruction.
+      int32_t branch = buffer_.Load<int32_t>(position);
+
+      // Clear out the old (far) branch.
+      for (int i = 0; i < 5; i++) {
+        buffer_.Store<int32_t>(position + i * Instr::kInstrSize,
+            Instr::kNopInstruction);
+      }
+
+      // Calculate the new offset.
+      dest = dest - 4 * Instr::kInstrSize;
+      const int32_t encoded = EncodeBranchOffset(dest, branch);
+      buffer_.Store<int32_t>(position + 4 * Instr::kInstrSize, encoded);
+      label->position_ = DecodeLoadImmediate(low, high);
+    } else {
+      const int32_t next = buffer_.Load<int32_t>(position);
+      const int32_t encoded = EncodeBranchOffset(dest, next);
+      buffer_.Store<int32_t>(position, encoded);
+      label->position_ = DecodeBranchOffset(next);
+    }
+  }
+  label->BindTo(bound_pc);
+  delay_slot_available_ = false;
+}
+
+
 void Assembler::LoadWordFromPoolOffset(Register rd, int32_t offset) {
   ASSERT(rd != PP);
   if (Address::CanHoldOffset(offset)) {
     lw(rd, Address(PP, offset));
   } else {
     const int16_t offset_low = Utils::Low16Bits(offset);  // Signed.
     offset -= offset_low;
     const uint16_t offset_high = Utils::High16Bits(offset);  // Unsigned.
     if (offset_high != 0) {
       lui(rd, Immediate(offset_high));
@@ skipping 147 matching lines @@
                                            Label* no_update) {
   COMPILE_ASSERT((kNewObjectAlignmentOffset == kWordSize) &&
                  (kOldObjectAlignmentOffset == 0), young_alignment);
 
   // Write-barrier triggers if the value is in the new space (has bit set) and
   // the object is in the old space (has bit cleared).
   // To check that, we compute value & ~object and skip the write barrier
   // if the bit is not set. We can't destroy the object.
   nor(TMP1, ZR, object);
   and_(TMP1, value, TMP1);
-  andi(TMP1, TMP1, Immediate(kNewObjectAlignmentOffset));
-  beq(TMP1, ZR, no_update);
+  andi(CMPRES1, TMP1, Immediate(kNewObjectAlignmentOffset));
+  beq(CMPRES1, ZR, no_update);
 }
 
 
 // Preserves object and value registers.
 void Assembler::StoreIntoObjectFilter(Register object,
                                       Register value,
                                       Label* no_update) {
   // For the value we are only interested in the new/old bit and the tag bit.
   // And the new bit with the tag bit. The resulting bit will be 0 for a Smi.
   sll(TMP1, value, kObjectAlignmentLog2 - 1);
   and_(TMP1, value, TMP1);
   // And the result with the negated space bit of the object.
-  nor(CMPRES, ZR, object);
-  and_(TMP1, TMP1, CMPRES);
-  andi(TMP1, TMP1, Immediate(kNewObjectAlignmentOffset));
-  beq(TMP1, ZR, no_update);
+  nor(CMPRES1, ZR, object);
+  and_(TMP1, TMP1, CMPRES1);
+  andi(CMPRES1, TMP1, Immediate(kNewObjectAlignmentOffset));
+  beq(CMPRES1, ZR, no_update);
 }
 
 
 void Assembler::StoreIntoObject(Register object,
                                 const Address& dest,
                                 Register value,
                                 bool can_value_be_smi) {
   ASSERT(object != value);
   sw(value, dest);
   Label done;
@@ skipping 90 matching lines @@
 void Assembler::EnterStubFrame(bool uses_pp) {
   SetPrologueOffset();
   if (uses_pp) {
     addiu(SP, SP, Immediate(-4 * kWordSize));
     sw(ZR, Address(SP, 3 * kWordSize));  // PC marker is 0 in stubs.
     sw(RA, Address(SP, 2 * kWordSize));
     sw(FP, Address(SP, 1 * kWordSize));
     sw(PP, Address(SP, 0 * kWordSize));
     addiu(FP, SP, Immediate(1 * kWordSize));
     // Setup pool pointer for this stub.
-    Label next;
-    bal(&next);
-    delay_slot()->mov(TMP1, RA);
+
+    GetNextPC(TMP1, false);  // TMP1 gets the address of the next instruction.
 
     const intptr_t object_pool_pc_dist =
         Instructions::HeaderSize() - Instructions::object_pool_offset() +
         CodeSize();
 
-    Bind(&next);
     lw(PP, Address(TMP1, -object_pool_pc_dist));
   } else {
     addiu(SP, SP, Immediate(-3 * kWordSize));
     sw(ZR, Address(SP, 2 * kWordSize));  // PC marker is 0 in stubs.
     sw(RA, Address(SP, 1 * kWordSize));
     sw(FP, Address(SP, 0 * kWordSize));
     mov(FP, SP);
   }
 }
 
@@ skipping 77 matching lines @@
 void Assembler::EnterDartFrame(intptr_t frame_size) {
   const intptr_t offset = CodeSize();
 
   SetPrologueOffset();
 
   addiu(SP, SP, Immediate(-4 * kWordSize));
   sw(RA, Address(SP, 2 * kWordSize));
   sw(FP, Address(SP, 1 * kWordSize));
   sw(PP, Address(SP, 0 * kWordSize));
 
-  Label next;
-  // Branch and link to the instruction after the delay slot to get the PC.
-  bal(&next);
-  // RA is the address of the sw instruction below. Save it in T0.
-  delay_slot()->mov(TMP1, RA);
+  GetNextPC(TMP1, false);  // TMP1 gets the address of the next instruction.
 
   // Calculate the offset of the pool pointer from the PC.
   const intptr_t object_pool_pc_dist =
       Instructions::HeaderSize() - Instructions::object_pool_offset() +
       CodeSize();
 
-  // TMP1 has the address of the next instruction.
-  Bind(&next);
-
   // Save PC in frame for fast identification of corresponding code.
   AddImmediate(TMP1, -offset);
   sw(TMP1, Address(SP, 3 * kWordSize));
 
   // Set FP to the saved previous FP.
   addiu(FP, SP, Immediate(kWordSize));
 
   // Load the pool pointer. offset has already been subtracted from TMP1.
   lw(PP, Address(TMP1, -object_pool_pc_dist + offset));
 
   // Reserve space for locals.
   AddImmediate(SP, -frame_size);
 }
 
 
 // On entry to a function compiled for OSR, the caller's frame pointer, the
 // stack locals, and any copied parameters are already in place.  The frame
 // pointer is already set up.  The PC marker is not correct for the
 // optimized function and there may be extra space for spill slots to
 // allocate. We must also set up the pool pointer for the function.
 void Assembler::EnterOsrFrame(intptr_t extra_size) {
   Comment("EnterOsrFrame");
-  Label next;
-  // Branch and link to the instruction after the delay slot to get the PC.
-  bal(&next);
-  // RA is the address of the sw instruction below. Save it in T0.
-  delay_slot()->mov(TMP, RA);
+
+  GetNextPC(TMP, false);  // TMP gets the address of the next instruction.
 
   // The runtime system assumes that the code marker address is
   // kEntryPointToPcMarkerOffset bytes from the entry.  Since there is no
   // code to set up the frame pointer, etc., the address needs to be adjusted.
   const intptr_t offset = kEntryPointToPcMarkerOffset - CodeSize();
   // Calculate the offset of the pool pointer from the PC.
   const intptr_t object_pool_pc_dist =
       Instructions::HeaderSize() - Instructions::object_pool_offset() +
       CodeSize();
 
-  // temp has the address of the next instruction.
-  Bind(&next);
-
   // Adjust PC by the offset, and store it in the stack frame.
   AddImmediate(TMP, TMP, offset);
   sw(TMP, Address(FP, kPcMarkerSlotFromFp * kWordSize));
 
   // Restore return address.
   lw(RA, Address(FP, 1 * kWordSize));
 
   // Load the pool pointer. offset has already been subtracted from temp.
   lw(PP, Address(TMP, -object_pool_pc_dist - offset));
 
@@ skipping 179 matching lines @@
     Bind(&msg);
     break_(Instr::kMsgMessageCode);
   }
 #endif
 }
 
 }  // namespace dart
 
 #endif  // defined TARGET_ARCH_MIPS