MIPS: Long branch implementation and trampoline improvement.

src/mips/assembler-mips.h

 // Copyright (c) 1994-2006 Sun Microsystems Inc.
 // All Rights Reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 // - Redistributions of source code must retain the above copyright notice,
 // this list of conditions and the following disclaimer.
 //
@@ skipping 462 matching lines @@
   //
   // Label L;    // unbound label
   // j(cc, &L);  // forward branch to unbound label
   // bind(&L);   // bind label to the current pc
   // j(cc, &L);  // backward branch to bound label
   // bind(&L);   // illegal: a label may be bound only once
   //
   // Note: The same Label can be used for forward and backward branches
   // but it may be bound only once.
   void bind(Label* L);  // Binds an unbound label L to current code position.
+  // Determines if Label is bound and near enough so that branch instruction
+  // can be used to reach it, instead of jump instruction.
+  bool is_near(Label* L);
 
   // Returns the branch offset to the given label from the current code
   // position. Links the label to the current position if it is still unbound.
   // Manages the jump elimination optimization if the second parameter is true.
   int32_t branch_offset(Label* L, bool jump_elimination_allowed);
   int32_t shifted_branch_offset(Label* L, bool jump_elimination_allowed) {
     int32_t o = branch_offset(L, jump_elimination_allowed);
     ASSERT((o & 3) == 0);   // Assert the offset is aligned.
     return o >> 2;
   }
+  uint32_t jump_address(Label* L);
 
   // Puts a labels target address at the given position.
   // The high 8 bits are set to zero.
   void label_at_put(Label* L, int at_offset);
 
   // Read/Modify the code target address in the branch/call instruction at pc.
   static Address target_address_at(Address pc);
   static void set_target_address_at(Address pc, Address target);
 
   // This sets the branch destination (which gets loaded at the call address).
@@ skipping 130 matching lines @@
 
   void addiu(Register rd, Register rs, int32_t j);
 
   // Logical.
   void and_(Register rd, Register rs, Register rt);
   void or_(Register rd, Register rs, Register rt);
   void xor_(Register rd, Register rs, Register rt);
   void nor(Register rd, Register rs, Register rt);
 
   void andi(Register rd, Register rs, int32_t j);
-  void ori(Register rd, Register rs, int32_t j);
+  void ori(Register rd, Register rs, int32_t j, bool check_buffer = true);

[Søren Thygesen Gjesse, 2011/06/24 13:05:15]

This boolean flag seems rather obscure - when should it be set to false?

[Paul Lind, 2011/06/28 06:53:14]

Agree that it was confusing. I have removed the flag and used a blocking scope
class & new class member boolean for this purpose, which is to signal the low
level emit() routine to NOT check & grow the assembly buffer.

The big picture of this is that we can now use internal references that are
absolute pointers within the code for very long functions. These need to be
relocated by patching the lui/ori instruction-pair, or optionally a j
instruction. But if the relocation is triggered by buffer check/growth before
those instructions are emitted, there is nothing to patch and it all fails. So
we delay buffer growth during these sequences using BlockGrowBufferScope.

   void xori(Register rd, Register rs, int32_t j);
-  void lui(Register rd, int32_t j);
+  void lui(Register rd, int32_t j, bool check_buffer = true);
 
   // Shifts.
   // Please note: sll(zero_reg, zero_reg, x) instructions are reserved as nop
   // and may cause problems in normal code. coming_from_nop makes sure this
   // doesn't happen.
   void sll(Register rd, Register rt, uint16_t sa, bool coming_from_nop = false);
   void sllv(Register rd, Register rt, Register rs);
   void srl(Register rd, Register rt, uint16_t sa);
   void srlv(Register rd, Register rt, Register rs);
   void sra(Register rt, Register rd, uint16_t sa);
@@ skipping 147 matching lines @@
   void RecordDebugBreakSlot();
 
   // Record the AST id of the CallIC being compiled, so that it can be placed
   // in the relocation information.
   void RecordAstId(unsigned ast_id) { ast_id_for_reloc_info_ = ast_id; }
 
   // Record a comment relocation entry that can be used by a disassembler.
   // Use --code-comments to enable.
   void RecordComment(const char* msg);
 
+  static void RelocateInternalReference(byte* pc, intptr_t pc_delta);
+
   // Writes a single byte or word of data in the code stream.  Used for
   // inline tables, e.g., jump-tables.
   void db(uint8_t data);
   void dd(uint32_t data);
 
   int32_t pc_offset() const { return pc_ - buffer_; }
 
   PositionsRecorder* positions_recorder() { return &positions_recorder_; }
 
   // Postpone the generation of the trampoline pool for the specified number of
@@ skipping 16 matching lines @@
   Instr instr_at(int pos) { return *reinterpret_cast<Instr*>(buffer_ + pos); }
   void instr_at_put(int pos, Instr instr) {
     *reinterpret_cast<Instr*>(buffer_ + pos) = instr;
   }
 
   // Check if an instruction is a branch of some kind.
   static bool IsBranch(Instr instr);
   static bool IsBeq(Instr instr);
   static bool IsBne(Instr instr);
 
+  static bool IsJump(Instr instr);
+  static bool IsJ(Instr instr);
+  static bool IsLui(Instr instr);
+  static bool IsOri(Instr instr);
+
   static bool IsNop(Instr instr, unsigned int type);
   static bool IsPop(Instr instr);
   static bool IsPush(Instr instr);
   static bool IsLwRegFpOffset(Instr instr);
   static bool IsSwRegFpOffset(Instr instr);
   static bool IsLwRegFpNegOffset(Instr instr);
   static bool IsSwRegFpNegOffset(Instr instr);
 
   static Register GetRtReg(Instr instr);
   static Register GetRsReg(Instr instr);
   static Register GetRdReg(Instr instr);
 
   static uint32_t GetRt(Instr instr);
   static uint32_t GetRtField(Instr instr);
   static uint32_t GetRs(Instr instr);
   static uint32_t GetRsField(Instr instr);
   static uint32_t GetRd(Instr instr);
   static uint32_t GetRdField(Instr instr);
   static uint32_t GetSa(Instr instr);
   static uint32_t GetSaField(Instr instr);
   static uint32_t GetOpcodeField(Instr instr);
+  static uint32_t GetFunction(Instr instr);
+  static uint32_t GetFunctionField(Instr instr);
   static uint32_t GetImmediate16(Instr instr);
   static uint32_t GetLabelConst(Instr instr);
 
   static int32_t GetBranchOffset(Instr instr);
   static bool IsLw(Instr instr);
   static int16_t GetLwOffset(Instr instr);
   static Instr SetLwOffset(Instr instr, int16_t offset);
 
   static bool IsSw(Instr instr);
   static Instr SetSwOffset(Instr instr, int16_t offset);
   static bool IsAddImmediate(Instr instr);
   static Instr SetAddImmediateOffset(Instr instr, int16_t offset);
 
   static bool IsAndImmediate(Instr instr);
 
-  void CheckTrampolinePool(bool force_emit = false);
+  void CheckTrampolinePool();
 
  protected:
   // Relocation for a type-recording IC has the AST id added to it.  This
   // member variable is a way to pass the information from the call site to
   // the relocation info.
   unsigned ast_id_for_reloc_info_;
 
   bool emit_debug_code() const { return emit_debug_code_; }
 
   int32_t buffer_space() const { return reloc_info_writer.pos() - pc_; }
@@ skipping 24 matching lines @@
   }
 
   bool is_trampoline_pool_blocked() const {
     return trampoline_pool_blocked_nesting_ > 0;
   }
 
   bool has_exception() const {
     return internal_trampoline_exception_;
   }
 
+  bool is_trampoline_emitted() const {
+    return trampoline_emitted_;
+  }
+
  private:
   // Code buffer:
   // The buffer into which code and relocation info are generated.
   byte* buffer_;
   int buffer_size_;
   // True if the assembler owns the buffer, false if buffer is external.
   bool own_buffer_;
 
   // Buffer size and constant pool distance are checked together at regular
   // intervals of kBufferCheckInterval emitted bytes.
   static const int kBufferCheckInterval = 1*KB/2;
 
   // Code generation.
   // The relocation writer's position is at least kGap bytes below the end of
   // the generated instructions. This is so that multi-instruction sequences do
   // not have to check for overflow. The same is true for writes of large
-  // relocation info entries.
-  static const int kGap = 32;
+  // relocation info entries. MIPS uses 8 bytes more than other architectures,
+  // because it does not check for this gap when instructions with internal
+  // reference relocation info are emitted.
+  static const int kGap = 40;
   byte* pc_;  // The program counter - moves forward.
 
 
   // Repeated checking whether the trampoline pool should be emitted is rather
   // expensive. By default we only check again once a number of instructions
   // has been generated.
   static const int kCheckConstIntervalInst = 32;
   static const int kCheckConstInterval = kCheckConstIntervalInst * kInstrSize;
 
   int next_buffer_check_;  // pc offset of next buffer check.
 
   // Emission of the trampoline pool may be blocked in some code sequences.
   int trampoline_pool_blocked_nesting_;  // Block emission if this is not zero.
   int no_trampoline_pool_before_;  // Block emission before this pc offset.
 
   // Keep track of the last emitted pool to guarantee a maximal distance.
   int last_trampoline_pool_end_;  // pc offset of the end of the last pool.
 
   // Relocation information generation.
   // Each relocation is encoded as a variable size value.
   static const int kMaxRelocSize = RelocInfoWriter::kMaxSize;
   RelocInfoWriter reloc_info_writer;
 
   // The bound position, before this we cannot do instruction elimination.
   int last_bound_pos_;
 
   // Code emission.
   inline void CheckBuffer();
   void GrowBuffer();
-  inline void emit(Instr x);
+  inline void emit(Instr x, bool check_buffer = true);
   inline void CheckTrampolinePoolQuick();
 
   // Instruction generation.
   // We have 3 different kind of encoding layout on MIPS.
   // However due to many different types of objects encoded in the same fields
   // we have quite a few aliases for each mode.
   // Using the same structure to refer to Register and FPURegister would spare a
   // few aliases, but mixing both does not look clean to me.
   // Anyway we could surely implement this differently.
 
@@ skipping 28 matching lines @@
   void GenInstrRegister(Opcode opcode,
                         SecondaryField fmt,
                         Register rt,
                         FPUControlRegister fs,
                         SecondaryField func = NULLSF);
 
 
   void GenInstrImmediate(Opcode opcode,
                          Register rs,
                          Register rt,
-                         int32_t  j);
+                         int32_t  j,
+                         bool check_buffer = true);
   void GenInstrImmediate(Opcode opcode,
                          Register rs,
                          SecondaryField SF,
                          int32_t  j);
   void GenInstrImmediate(Opcode opcode,
                          Register r1,
                          FPURegister r2,
                          int32_t  j);
 
 
   void GenInstrJump(Opcode opcode,
                      uint32_t address);
 
   // Helpers.
   void LoadRegPlusOffsetToAt(const MemOperand& src);
 
   // Labels.
   void print(Label* L);
   void bind_to(Label* L, int pos);
-  void link_to(Label* L, Label* appendix);
   void next(Label* L);
 
   // One trampoline consists of:
   // - space for trampoline slots,
   // - space for labels.
   //
   // Space for trampoline slots is equal to slot_count * 2 * kInstrSize.
   // Space for trampoline slots preceeds space for labels. Each label is of one
   // instruction size, so total amount for labels is equal to
   // label_count *  kInstrSize.
   class Trampoline {
    public:
-    Trampoline(int start, int slot_count, int label_count) {
+    Trampoline() {
+      start_ = 0;
+      next_slot_ = 0;
+      free_slot_count_ = 0;
+      end_ = 0;
+    }
+    Trampoline(int start, int slot_count) {
       start_ = start;
       next_slot_ = start;
       free_slot_count_ = slot_count;
-      next_label_ = start + slot_count * 2 * kInstrSize;
-      free_label_count_ = label_count;
-      end_ = next_label_ + (label_count - 1) * kInstrSize;
+      end_ = start + slot_count * kTrampolineSlotsSize;
     }
     int start() {
       return start_;
     }
     int end() {
       return end_;
     }
     int take_slot() {
       int trampoline_slot = kInvalidSlotPos;
       if (free_slot_count_ <= 0) {
         // We have run out of space on trampolines.
         // Make sure we fail in debug mode, so we become aware of each case
         // when this happens.
         ASSERT(0);
         // Internal exception will be caught.
       } else {
         trampoline_slot = next_slot_;
         free_slot_count_--;
-        next_slot_ += 2*kInstrSize;
+        next_slot_ += kTrampolineSlotsSize;
       }
       return trampoline_slot;
     }
-    int take_label() {
-      int label_pos = next_label_;
-      ASSERT(free_label_count_ > 0);
-      free_label_count_--;
-      next_label_ += kInstrSize;
-      return label_pos;
-    }
-
    private:
     int start_;
     int end_;
     int next_slot_;
     int free_slot_count_;
-    int next_label_;
-    int free_label_count_;
   };
 
-  int32_t get_label_entry(int32_t pos, bool next_pool = true);
-  int32_t get_trampoline_entry(int32_t pos, bool next_pool = true);
-
-  static const int kSlotsPerTrampoline = 2304;
-  static const int kLabelsPerTrampoline = 8;
-  static const int kTrampolineInst =
-      2 * kSlotsPerTrampoline + kLabelsPerTrampoline;
-  static const int kTrampolineSize = kTrampolineInst * kInstrSize;
+  int32_t get_trampoline_entry(int32_t pos);
+  int unbound_labels_count;
+  // If trampoline is emitted, generated code is becoming large. As this is
+  // already a slow case which can possibly break our code generation for

[Søren Thygesen Gjesse, 2011/06/24 13:05:15]

for -> for the / in the

[Paul Lind, 2011/06/28 06:53:14]

Done.

+  // extreme case, we use this information to trigger different mode for

[Søren Thygesen Gjesse, 2011/06/24 13:05:15]

for -> of

[Paul Lind, 2011/06/28 06:53:14]

Done.

+  // branch instruction generation, where we use jump instructions rather
+  // than regular branch instructions.
+  bool trampoline_emitted_;
+  static const int kTrampolineSlotsSize = 4 * kInstrSize;
   static const int kMaxBranchOffset = (1 << (18 - 1)) - 1;
-  static const int kMaxDistBetweenPools =
-      kMaxBranchOffset - 2 * kTrampolineSize;
   static const int kInvalidSlotPos = -1;
 
-  List<Trampoline> trampolines_;
+  Trampoline trampoline_;
   bool internal_trampoline_exception_;
 
   friend class RegExpMacroAssemblerMIPS;
   friend class RelocInfo;
   friend class CodePatcher;
   friend class BlockTrampolinePoolScope;
 
   PositionsRecorder positions_recorder_;
   bool emit_debug_code_;
   friend class PositionsRecorder;
   friend class EnsureSpace;
 };
 
 
 class EnsureSpace BASE_EMBEDDED {
  public:
   explicit EnsureSpace(Assembler* assembler) {
     assembler->CheckBuffer();
   }
 };
 
 } }  // namespace v8::internal
 
 #endif  // V8_ARM_ASSEMBLER_MIPS_H_