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, use_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);
+void Assembler::GetNextPC(Register dest, Register temp) {
+  if (temp != kNoRegister) {
+    mov(temp, RA);
   }
-  label->BindTo(bound_pc);
-  delay_slot_available_ = false;
+  EmitRegImmType(REGIMM, R0, BGEZAL, 1);
+  mov(dest, RA);
+  if (temp != kNoRegister) {
+    mov(RA, temp);
+  }
 }
 
 
-int32_t Assembler::EncodeBranchOffset(int32_t offset, int32_t instr) {
+static bool CanEncodeBranchOffset(int32_t offset) {
+  ASSERT(Utils::IsAligned(offset, 4));
+  return Utils::IsInt(18, offset);
+}
+
+
+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 ori_instr, int32_t lui_instr) {
+  return (((lui_instr & kBranchOffsetMask) << 16) |
+           (ori_instr & 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);
+  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_use_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_use_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_use_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_use_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_use_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_use_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_use_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_use_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);  // 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);  // 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);  // 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